中国地质大学数据结构实习报告

1、中国地质大学数据结构实习报告简介第一篇：中国地质大学数据结构实习报告practice report for data structures and algorithm analysis data structures course report candidate: student number: major: communication engineering supervisor: wu rangzhong china university of geosciences(wuhan) wuhan, hubei 430074, p. r. china may 18, 2013 china u

2、niversity of geosciences, faculty of mechanics and electronic information - 1 删除程序代码 void deletekth(int position, pnode l) pnode tmp=l, tmppre=null; int i=0; for(i=0; i if(tmp->next!=null ) tmppre = tmp; tmp=tmp->next; else if(tmp->next=null && i printf("the deletion position i

3、s invalid!n"); return; tmppre->next=tmp->next; free(tmp); 这是程序主函数，以此来完成以上子函数的功能 #include #include #include "lianbiao.h" int main() int i,x,position;pnode m; pnode linklists; printf("输入元素来建立链表，0为结束输入的标志"); linklists = createlinklists(); printf("链表为:"); printli

4、sts(linklists); printf("选择你需要的操作，输入序号：n"); printf(" 1.建立一个链表n"); printf(" 2.输出链表 n"); - 3 2.数组实现线性表 用数组实现的功能和用链表表示的相同 部分子函数如下 /初始化顺序表：给出初始化长度 int initialarray(arraylist arrlst,int len) arrlst->length=0; arrlst->size=len; arrlst->array=(elemtype*)malloc(len*size

5、of(elemtype); if(arrlst->array=null) return 0; else return 1; /删除顺序表void deletearray(arraylist arrlst) arrlst->length=0; arrlst->size=0; free(arrlst->array); arrlst->array=null; /清空顺序表void cleararray(arraylist arrlst) - 5 printf("n"); /判断某个元素的位置int locateelem(arraylist arrls

6、t,elemtype e) int i; for(i=0;i if(e=arrlst->arrayi) return i; return -1; 堆栈主要是实现元素的进栈、出栈、判断栈中元素个数堆栈的源函数 #include #include #include"duizhan.h" stack creatstack() stack s; s=(stack)malloc(sizeof(struct stack); if(s=null) printf("无法建立堆栈!"); return 0; s->top=-1; return s; int i

7、sfull(stack s) return(s->top=max-1); int isempty(stack s) - 7 int stacklen(stack s) if(!isempty(s) return s->top; else return 0; 堆栈的主函数 #include #include #include"duizhan.h" void main() stack lilis; lilis=creatstack(); push(1,lilis); push(2,lilis); push(3,lilis); pop(lilis); pop(lili

8、s); disposestack(lilis); 设置断点可以看到栈中的元素 - 9主函数 void main() string *str, *pat; int position=0; str=(string *) malloc(sizeof(string); pat=(string *) malloc(sizeof(string); char s_str20="ababcabcacbab" char p_str20="abcac" str->p_str = s_str; str->length = strlen(s_str); pat-&g

9、t;p_str = p_str; pat->length = strlen(p_str); int *next= (int *) malloc(sizeof(int) * (pat->length +1); getnext(pat, next); position=indexkmp(str, pat, next); printf("%dn",position); 显示两个字符串是在第6个元素开匹配的。 - 11 /插入新元素m->datap.i=row; m->datap.j=col; m->datap.e=e; m->tu+; retu

10、rn ok; 稀疏矩阵的的转置 status transposesmatrix(const tsmatrix *m,tsmatrix *t) int col,p,q; t->mu=m->nu; t->nu=m->mu; t->tu=m->tu; if(t->tu) q=1; for(col=1;colmu;col+) for(p=1;ptu;p+) if(m->datap.j=col) t->dataq.i=m->datap.j; t->dataq.j=m->datap.i; t->dataq.e=m->dat

11、ap.e; q+; return ok; 稀疏矩阵的乘法 status multsmatrix(const tsmatrix *m,const tsmatrix *t,tsmatrix *q) int i,j,k,p; elemtype m,t,s; if(m->nu!=t->mu) printf("sorry,these two matrice can't multiply.n"); return error; q->mu=m->mu; q->nu=t->nu; q->tu=0; p=1; for(i=1;imu;i+)

12、for(j=1;jnu;j+) s=0; for(k=1;knu;k+) if(false=findelem(m,i,k,&m) - 13 查找 采用的是快速查找法 源程序 #include #include "chazhao.h" int sequencesearch(int array,int n,int x) int i=0; while(i i+; if(i=n) return -1; else return i; 建立一个数组后查找元素，输入元素后，返回元素所在数组的下标。 - 15用数组储存数据，在用冒泡法排序后将排序好的数组输出。 avl树 程序主要是

13、在向二叉树插入节点后，最终生成avl树 avl树中的单旋转 static position srl(position k2) position k1 = null; k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = max(height(k2->left), height(k2->right) + 1; k1->height = max(height(k1->left), height(k2) + 1; return k1; static position s

14、rr(position k2) position k1 = null; - 17 #else position k1 = null; position k2 = null; k1 = k3->right; k2 = k1->left; k1->left = k2->right; k2->right = k1; k3->right = k2->left; k2->left = k3; return k2; #endif 主程序 #include #include "avltree.h" void printtree(avltre

15、e t) if(t != null) printtree(t->left); printf("h=%d, e=%dn", t->height, t->ele); printtree(t->right); int main(void) avltree t = null; t = makeempty(t); t = insert(3, t); t = insert(2, t); t = insert(1, t); t = insert(4, t); t = insert(5, t); t = insert(6, t); t = insert(7, t);

16、 t = insert(16, t); t = insert(15, t); t = insert(14, t); t = insert(13, t); - 19s->bottom=0; s->top=0; memset(s->printout,0,sizeof(int)*max_len); void push(mstack *s,int m) s->printouts->top+=m; int pop(mstack *s) return s->printout-s->top; void initgraph(graph *g,int n) int i,

17、j; for(i=1;imatrixij=0; else g->matrixij=infinite; for(i=1;i=indexi+1) flag=i; else flag=i+1; void decompressionfile(file *ifp,file *ofp) unsigned char i_c=' ' char o_c=' ' /*/ /读取压缩文件信息fseek(ifp,0,seek_set); int orignflen=0; int maxsize=0; int keynum=0; fread(&orignflen,sizeo

18、f(int),1,ifp); char *depressfile; depressfile=new charorignflen+1; fread(&maxsize,sizeof(int),1,ifp); c_file file(maxsize); fread(&file.keynum,sizeof(int),1,ifp); for(int i=1;i fread(&file.keyi.data,sizeof(char),1,ifp); fread(&file.keyi.count,sizeof(int),1,ifp); /*/ /重构huffman树和编码fil

19、e.createhufftree(); file.createhuffcode(); fseek(ifp, 12+(file.keynum-1)*5), seek_end); long flen = ftell(ifp); char *compressfile=new char flen+1; fseek(ifp,0,seek_set); fseek(ifp, 12+(file.keynum-1)*5), seek_set); char t_buff255,z_buff255; t_buff0=0; z_buff0=0; /获取最长编码的长度int *index; index=new int

20、file.keynum-1; int flag=0; for (int i=1;i indexi=file.huffman_nodei.count; findmax(index,file.keynum-1,flag); int p=file.huffman_nodeflag.count; int curr_index=0; int l=0; while (true) int i; while (strlen(z_buff)/保证能够取到最长编码的全部内容 fread(&i_c,1,1,ifp); itoa(i_c,t_buff,2); /将读取的一个（字符型）字节的内容转换为char型

21、字符数组 strcat(z_buff,t_buff); 【参考资料】 for (i=1;iif(memcmp(file.huffman_nodei.bits,z_buff,file.huffman_nodei.count)=0) break; strcpy(z_buff,z_buff+file.huffman_nodei.count); /获得目标字符并存入目标数组 o_c=file.keyi.data; depressfilel+=o_c; if (l=orignflen) break; fseek(ofp,0,seek_set); fwrite(depressfile,1,l,ofp);/

22、将解压后的文件一次性地写入文件fclose(ifp); fclose(ofp); coutdata=x; if(i=1) q->next=p; l=q; else 定义结构体。 插入函数。 删除函数。 输出长度。 输出线性表内容。 while(-i>1) p=p->next; q->next=p->next;p->next=q; 3、运行过程： 二、堆栈和队列 1、目的： 通过程序的运用，使得队列的插入、删除等功能更加容易实现，节约了时间和精力。 2、程序说明： struct my_queue int elementmaxlength; int length

23、; int head; int rear; ; 定义结构体。 int head_queue(my_queue &que); 功能：返回队列头结点的值 参数：que，引用类型，指向队列的头。 void print_queue(my_queue &que); 输出队列的内容。 void in_queue(my_queue &que,int element); 输入队列。 void out_queue(my_queue &que, int &element); 输出队列。 主函数： void main() my_queue my_fst_que; my_fst

24、_que.length = 0; int data = 0; my_fst_que.head = my_fst_que.rear =0; input_queue(my_fst_que, 2); print_queue(my_fst_que); input_queue(my_fst_que, 4); print_queue(my_fst_que); input_queue(my_fst_que, 6); print_queue(my_fst_que); input_queue(my_fst_que, 8); print_queue(my_fst_que); input_queue(my_fst_

25、que, 10); print_queue(my_fst_que); out_queue(my_fst_que, data); print_queue(my_fst_que); out_queue(my_fst_que, data); print_queue(my_fst_que); out_queue(my_fst_que, data); print_queue(my_fst_que); out_queue(my_fst_que, data); data = head_queue(my_fst_que); print_queue(my_fst_que); 3、运行过程： 三、字符串的模式匹配

26、 1、目的： 输入目标串和模式串，运用kmp算法判断是否匹配。 2、程序说明： typedef struct string string_kmp; struct string char * data; int length; ; 定义结构体。 int kmpmatch (string_kmp &s, string_kmp &t , int next); 功能：用于检测返回值情况。 主函数： void main() string_kmp s, p1; int *next_kmp, position=0; p1.data = "&&aaaaa"

27、p1.length = strlen(p1.data); s.data ="&&&aaaaabaabcwwww" s.length = strlen(s.data); next_kmp=(int *) malloc(sizeof(int) * strlen(p1.data); next( p1, next_kmp); position = kmpmatch (s, p1 , next_kmp); if (position = 0) printf("no match!n"); else printf("the match

28、position is %dn", position); 3、运行过程： 1、匹配成功： 2、不能匹配： 四、稀疏矩阵（表示转置和乘法） 1、目的： 通过对矩阵的基本操作，了解多维数组的逻辑结构和存储结构。本程序是用三元数组表示矩阵，并进行相关的操作，将矩阵表示出来，以及快速转置的应用。 2、程序说明： typedef struct triple datamaxsize+1; int mu,nu,tu; tsmatrix; int inputmatrix(tsmatrix &m); void printm(tsmatrix m); void printm3(tsmatrix

29、m); void trantup(tsmatrix m, tsmatrix &t); 主函数： void main() int a; tsmatrix m,t; a=inputmatrix(m); printf("n按三元组方式输出:n"); printm3(m); printf("n下面进行矩阵转置的操作：n"); system("pause"); system("cls"); printf("n要转置的矩阵为:n"); printm(m); trantup(m,t); printf(

30、"n转置后的矩阵为:n"); printm(t); 3、运行过程： 五 avl树实现 1、目的： 通过程序的运用，使得树的相关功能更加容易实现，节约了时间和精力。 2、程序说明： 求根深度的实现所用到的： status initbitree(sqbitree t); status createbitree(sqbitree t); status bitreeempty(sqbitree t); int bitreedepth(sqbitree t); status root(sqbitree t,telemtype *e); 3、运行过程： 六、图的实现： 1、目的： 通过

31、程序的运用，使得图的有关功能更加容易实现，节约了时间和精力。 2、程序说明： 实现图的输出和遍历用到的: void creategraph(graph *ga) ; void dfs(graph g,int i,bool visited) ; void dfstraverse(graph g) ; void bfstraverse(graph g,queue *que) ; 3、运行过程： 七、排序（希尔排序与归并排序）： 1、目的： 通过程序的运用，使得数据的排序更加容易实现，节约了时间和精力。 2、程序说明： 1)希尔排序的具体实现: void shellsort(rectype r,in

32、t n) int i,j,gap,k; rectype tmp; gap=n/2; while (gap>0) for (i=gap;i tmp=ri; j=i-gap; while (j>=0 && tmp.key rj+gap=rj; j=j-gap; rj+gap=tmp; j=j-gap; printf("gap=%d:",gap); for (k=0;k printf("%d ",rk.key); printf("n"); gap=gap/2; 2)归并排序： 归并排序的实现所用到的： int r

33、andgenerator(double varray,int n); int merge(double varray,double lr,int i,int m,int n); int msort(double varray,double lr,int s,int t); 3、运行过程： 总结 通过本次的实习，使我掌握了模块化设计方法，理解和运用结构化程序设计的思想和方法。提高了利用c语言进行程序设计能力。 第一次设计这么多程序，感觉压力很大，很难完成，虽然看起来设计流程感觉很轻松，但是正真完成的时候并不能通过程序表达出来。通过同学和老师的帮助最终还是完成了自己的程序设计，虽然程序还不是很完美

34、，但能满足题目的各项要求，相信以后再次进行程序设计的时候会得心应手。 第五篇：地质实习实习报告中国石油大学中国石油大学地质实习报告第一章 绪言本次实习野外路线观察时间为7天，具体时间为7月8-14日，早上7点30分从润洁公寓上车，晚上5点前回来本次主要观察路线有9条线路1：下苇甸寒武-奥陶纪地层观察；线路2：野溪构造地质观察线路3：延庆燕山天池西侏罗纪碎屑岩、火成岩特征观察线路4：延庆燕山天池东侧地质构造观察线路5：十三陵天池-三合村岩性、构造观察线路6：沟崖水库-十三陵水库地层接触关系、现代河流沉积作用观察线路7：房山太平山南坡石炭-二叠系岩性组成、接触关系观察线路8、房山燕山晚期侵入岩特征

35、观察线路9：周口店遗址参观自然地理概况北京的整个地形和山势的骨架，基本形成于距今6000-7000万年的燕山凿山运动。北京的西部山地，从南口的关沟至拒马河一带，统称为西山。它是由一系列成北东南西走向，并且大致平行的褶皱山脉所组成，属太行山脉。北京北部的山地，统称为军都山，属燕山山脉，这是一个镶嵌着若干个山间盆地的断块山地。在地势上，则是由平原呈阶梯逐级上升，尔后进入蒙古高原。北京市地理坐标为：北纬经度39°2841°05，东经117°30115°25，南北跨纬度约1°37，东西跨经度约2°05。天安门地理坐标为：北纬39°5

36、427，东经116°2317，是北京的标准中心坐标点。天安门广场海拔高度为44.4米。第二章 地层一、太古界在线路6，沟崖水库西侧有一组太古界变质岩，细观察可看到片麻岩，麻砾岩，可以看到的矿物有斜长岩、角闪岩，所以可命名为斜长角闪片麻岩。颜色灰白，其表面有重结晶现象，岩石致密，有定向排列的特点。说明这个岩层在形成过程中经历了高温高压环境，生成了新的矿物。和下层的元古界石英砂岩存在地层缺失，且两个岩层的倾向不同，可判断出地层接触关系为角度不整合接触。接触面倾向为140，倾角为54。图二、元古界在线路6，出现了一组中上元古界石英砂岩。颜色为灰白色，表面不含辉绿岩。属常州沟组，距今有17-

37、18亿年。在线路4，永宁至天池分岔路西侧约3公里处，有距今8-10亿年前的中元古界地层，其成分主要为白云岩、灰岩。推测白云岩是在古老地层中灰岩通过交代作用形成。在这些岩层表面发现了砂状颗粒、泥晶及鲕粒构造。其中鲕粒为同心圆，呈眼球状。其原因可能为有生物活动产生碎屑的关系，也可能为已固结的碳酸钙沉积被压扁压断产生碎屑。本地层还出现了初期小规模熔岩现象，有1-2米厚，原理是环境产生的hco3-及h2co3使碳酸型岩发生溶解。其成因有本身岩石关系，还有节理断层产生的裂缝，潮湿的气候天气等外因加速这种现象的发生。继续下去就会变成溶洞。这种以化学溶蚀为主，机械冲刷为辅的地质作用以及这些地质作用所产生的地

38、貌，称为喀斯特。沿公路不远处有中元古界长城系石英砂岩（石英纯度>95%），生成于17亿年前左右，层状结构。其石英颗粒呈粒状。有些岩石含发绿部分为海绿石。判断为海洋相，因如果为河流相，石英的纯度达不到如此高，且由此途径形成的砂岩受到河流形态的影响，这里观察到的为一大整块岩石。岩层上有些长度为7公分左右的条状物，是由泥裂形成，里面充满了石英颗粒。但规模不大，且无规律。同样线路距溪水湾一公里处出现了中上元古界海相灰岩地层沉积，以波痕、印模现象为主。形成原因可能为海上碳酸盐发生造山作用形成。沉积面倾角为65，层面光滑，呈水平状。印模形成原因是下层岩石软，上层较硬，上层有痕迹的岩石压下岩形成。波痕

39、可能是流水或风冲刷自然形成，也可能是压成，此时和印模类似。波痕如对称为双向水流，不对称为单向。波痕与印模区别为波痕具有方向感和定向性。（照片）三、古生界（一） 寒武系在线路1，沿铁路方向依次出现寒武系下统、中统和上统。1、 下统该地层由上层毛庄组，中层馒头组，下层府君山组构成。厚度约80-100米。由紫红色泥岩和灰黄色泥质泥晶白云岩组成三个沉积旋回。每个旋回下层为含三价铁的紫红色页岩和泥岩，具有砂质结构，中层岩层显红、白色，上层岩层以灰色为主，为灰质泥岩，白云岩等碳酸盐类。从下到上岩层粉砂质增多。2、 中统该地层由徐庄组、张夏组、崮山组构成。与下寒武统的接触部分主要以灰色鲕粒石灰岩和绿色粉砂质

40、页岩作为分界。鲕粒呈鱼子状，粒径0.2mm-0.6mm，含量60%-80%，发育较大，填隙物为亮晶方解石。该地层含泥质条带灰岩、鲕粒灰岩和竹叶状灰岩，竹叶状灰岩砾屑周围没有红色氧化圈。照片3、 上统该地层由长山组、凤山组构成。含白云质条带灰岩和竹叶石灰岩：前者在风化面上呈褐或褐红色，新鲜面呈深灰色。后者竹叶状砾屑常具有氧化圈，最长可达10cm，呈放射状、梅花状排列或平行层面排列。竹叶状石灰岩横向上呈透镜状，可能在形成过程中结实打碎、搬运、沉积，受到了风暴作用的影响。（照片）（二） 奥陶系（距今438-505年）线路1出现下奥陶统，位置：下苇甸东南永定河东侧铁路旁。此处为冶里组，厚度有30-80厘米左右，主要由灰岩构成，与下层的上寒武统地层称整合接触关系。与上寒武统相比，这里灰岩的块状性增强。对冶里组灰岩进行细分为厚层块状灰泥石灰岩、豹皮石灰岩、白云质条带灰泥石灰岩。其中第一种灰岩岩质较纯，在当地常被开采作为石灰和水泥原料。豹皮灰岩其岩面呈斑点状（此处画图）线路7同样为下奥陶统。在太平山南坡的马家沟组，厚度少则几十米，多达二百米多。岩性：底部主要为同生角砾状灰岩，下、中部主要为青灰色的中厚层状灰岩、结晶灰岩，上部主要为泥质条纹带灰岩或白云质灰岩。本统各个地层呈整合接