数据结构与算法实验报告

《数据结构与算法》综合实验报告系别：专业：学生姓名：指导教师：2011年11月25日实验目的掌握线性表的建立、插入、删除算法；掌握查找算法；掌握排序算法；实验要求使用C语言（环境任意）开发程序，能够对用户输入的任意一组数据，建立一个线性表，可以输出此线性表。并且能够对此线性表进行插入、删除、查找、排序等操作。程序流程建表如下：定义一个整型的数据类型data和next指针：定义头指针和当前结点指针，申请连续空间将单个字节大小复制给头指针，把头指针赋值给当前节点指针：若输入的数是0，则若输入不为0，把输入的数赋值给已申请的新结点，把新结点赋给当前节点的next域，再把新结点赋值给当前结点，以此方法重复执行得到如下链表：输出函数：把头指针赋值给当前结点指针，当当前节点的next域不为空时输出当前节点所指向的数据，把当前结点的next域赋值给当前节点，否则输出链表为空对此线性表进行插入、删除、查询、排序操作把已申请的结点数据域指向所输入的数再把插入w结点赋值头结点，是插入的位置，如果w=0则插入结点的next域赋值给头结点否则如果w表长，则输出超出范围代码及运行结果（主要语句要求有注释）#includestdafx.h#includestdio.h#includemalloc.h#defineNULL0typedefstructlinknode{intdata;structlinknode*next;}node;node*head;node*creat(){node*currnode,*newnode;intx;head=(node*)malloc(sizeof(node));currnode=head;do{scanf(%d,&x);newnode=(node*)malloc(sizeof(node));newnode-data=x;currnode-next=newnode;currnode=newnode;}while(x!=NULL);head=head-next;currnode-next=NULL;returnhead;};intlength(){node*currnode;inti=0;currnode=head;while(currnode-data!=NULL){currnode=currnode-next;i++;};returni;};voidprint(){node*currnode;currnode=head;printf(链表如下....linklist);while(currnode-data!=NULL){printf(%d--,currnode-data);currnode=currnode-next;};printf(NULL\n);printf(链表长度为........linklistlength%d\n,length());};voiddelete1(){intx;node*delnode,*currnode;printf(输入要删除的数据......inputdeletedata：);scanf(%d,&x);if(head-data==NULL)printf(此链表为空无法删除.....thislinklistempty！\n);if(head-data==x){delnode=head;head=head-next;free(delnode);if(head==NULL)printf(此链表为空.......thislinklistenpty！);}else{currnode=head;delnode=currnode-next;while(delnode-data!=x&&delnode!=NULL){currnode=currnode-next;delnode=currnode-next;};if(delnode==NULL)printf(无此数据......nothisdata！\n);else{currnode-next=delnode-next;free(delnode);};};};voidfind(){node*currnode;intcount=1,x;currnode=head;printf(输入要查找的数据.......inputsearchdata:);scanf(%d,&x);while(currnode-data!=NULL&&currnode-data!=x){currnode=currnode-next;count++;};if(currnode-data!=NULL){printf(\n%d为第........isno.,currnode-data);printf(%d个数据........data。\n,count);}elseprintf(\n无此数据.......notthisdata!\n);};voidinsert(){intx,w,i;node*insertnode,*afternode,*currnode;printf(输入要插入的数据Y........inputinsertedata：);scanf(%d,&x);printf(插入n结点后.........insertafterno.datan=:(0，1，…));scanf(%d,&w);insertnode=(node*)malloc(sizeof(node));insertnode-data=x;if(w==0){insertnode-next=head;head=insertnode;}elseif(wlength()){printf(超出范围.........overflow!\n);}else{currnode=head;afternode=currnode-next;for(i=1;iw;i++){afternode=afternode-next;currnode=currnode-next;};currnode-next=insertnode;insertnode-next=afternode;};};voidsort(node**head){node*p,*q,*r,*s,*h1;h1=p=(node*)malloc(sizeof(node));p-next=*head;while(p-next-data!=NULL){q=p-next;r=p;while(q-next-data!=NULL){if(q-next-datar-next-data)r=q;q=q-next;}if(r!=p){s=r-next;r-next=s-next;s-next=p-next;p-next=s;}p=p-next;}*head=h1-next;free(h1);};voidoperation(){printf(\n\n删除数据输入........delete1:1\n);printf(\n查找数据输入........search:2\n);printf(\n插入数据输入.......insert:3\n);printf(\n排序数据输入..........sort:4\n);printf(\n结束操作...........end:5\n);printf(\n?:);};voidmain(){intchoic;printf(\n输入数据以0结束..........inputdata0end:\n);head=creat();print();operation();do{scanf(%d,&choic);switch(choic){case1:delete1();print();operation();break;case2:find();operation();break;case3:insert();print();operation();break;case4:sort(&head);print();operation();break;default:printf(操作结束........operateend!);break;};}while(choic!=5);}个人总结（要求1000字以上）数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。