数据结构课程设计-链表操作.docx

数据结构课程设计报告题 目： 链表操作 专 业： 软件工程 班 级： 09级（2）班 姓 名： 学 号： 指导老师： 设计时间：2011年12月5日 2011年 12月 18日 目 录1. 设计题目2. 设计目的3. 设计内容和要求4. 运行环境（软和硬件）5. 算法设计的思想6. 算法流程图7. 算法设计分析8. 源代码9. 运行结果及分析10. 收获及体会一、 设计题目链表的基本操作二、 设计目的1掌握线性链表的建立。 2掌握线性链表的基本操作。三、 设计内容和要求利用链表的插入运算建立线性链表，然后实现链表的查找、删除、计数、输出、排序、逆置等运算，插入、删除、查找、计数、输出、排序、逆置要单独写成函数，并能在屏幕上输出操作前后的结果。四、 运行环境（软、硬件环境）Visual C+6.0Win9x/NT/2000/XP/2003/7环境下均可以运行。五、 算法设计的思想1.数据结构定义了一个lian的结构体int num;struct lian *next;。2.链表的建立是利用尾插法来完成的；q=(llink)malloc(sizeof(node);q-num=arrayi;q-next=NULL;p-next=q;p=p-next;3.遍历算法是从头开始遍历，找到了就输出该数，没有就显示没有找到；4.计数链表中的节点个数是用一个循环p-next!=NULL时就继续计数；5.链表的输出，通过p=p-next一个个进行遍历输出。6.链表的排序算法，从小到大进行排序，通过循环来达到。保持head结点不变，p指向第一个结点，q=p-next,p所指结点依次和后面的结点比较，比它大则交换，否则继续后移动q=q-next; for(i=0;inext;q=p-next;for(j=i+1;jnump-num)temp=p-num;p-num=q-num;q-num=temp;q=q-next;7.链表的插入llink insert(llink head,llink ptr,int m)和删除llink delet(llink head,llink ptr)设计比较简单没什么技巧8.链表的倒置输出，保持head头结点不动，p指针指向第一个结点，p向后流动，q指针指向p的后一个结点，把q所指结点插在head和p之间。p=llist-next;llist-next=NULL;while(p!=NULL) q=p-next;p-next=llist-next;llist-next=p;p=q;六、 算法的流程图开 始main函数Int arrayn;llist p;P=create(array,len);While(choice)Print(p);Choice=11delet(p,ptr);Choice=2insert(p,ptr,m);Choice=3Choice=4sort(p,5);search(p,m);Choice=5count(p);Choice=6Daozhi(p);Choice=7Choice=0结 束七、 算法设计分析算法设计较为简单，时间复杂度O(n*n);八、 源代码 #include#include#includetypedef struct lian /*单个链表节点的结构体*/int num;struct lian *next;node;typedef node *llink;/*建立链表函数*/llink Creat(int array,int len)llink head;llink p,q;int i;head=(llink)malloc(sizeof(node);head-next=NULL;p=head;for(i=0;inum=arrayi;q-next=NULL;p-next=q;p=p-next;return head;/*遍历操作函数*/void Print(llink head) llink p;p=head-next;printf(n输出链表: );while(p!=NULL)printf(%5d,p-num);p=p-next;printf(n);/*计数输出函数*/count(llink llist)int i=0;llink p;p=llist;Print(p);while(p-next)!=NULL) i+;p=p-next;printf(链表的节点个数为%d,i);printf(n);llink Daozhi(llink llist)llink p,q;p=llist-next;llist-next=NULL;while(p!=NULL)q=p-next;p-next=llist-next;llist-next=p;p=q;return llist;llink search(llink head,int m) llink p;p=head;while(p!=NULL)if(p-num=m)return p;p=p-next;return p;llink delet(llink head,llink ptr)llink pevious;if(ptr=head)return head-next;elsepevious=head;while(pevious-next!=ptr)pevious=pevious-next;if(ptr-next=NULL)pevious-next=NULL;elsepevious-next=ptr-next; free(ptr);return head;llink insert(llink head,llink ptr,int m)llink p1;p1=(llink)malloc(sizeof(node);if(!p1)return p1;p1-num=m;p1-next=NULL;if(ptr=NULL)p1-next=head;return p1;elseif(ptr-next=NULL)ptr-next=p1;elsep1-next=ptr-next;ptr-next=p1;return head;llink sort(llink llist,int len)llink p,q;int i,j,temp;p=llist;Print(llist);for(i=0;inext;q=p-next;for(j=i+1;jnump-num)temp=p-num;p-num=q-num;q-num=temp;q=q-next;return llist;printf(输出排序后的链表);printf(n);int main()llink p,llist,ptr;int choice,m,n;int array5=5,4,1,6,3;p=Creat(array,5);while(choice!=0)printf( - nn);printf( | _ | nn);printf(| | 数据结构课程设计 | nn);printf(| | 0:退出 1:输出元素 | nn);printf(| | 2:删除元素 3:插入元素 | nn);printf(| | 4:排序元素 5:查找元素 | nn);printf(| | 6:计数 7:倒置 | nn); printf(| _ nn);printf( | | nn);printf( - nn);printf(请选择功能：);scanf(%d,&choice);switch(choice)case 0:break;case 1: Print(p);break;case 2:printf(请输入要删除的数据);scanf(%d,&m);if(m!=0)ptr=search(p,m);if(!ptr)printf(没有找到!n);elsellist=delet(p,ptr);printf(删除后的链表为);Print(llist);break;case 3: printf(请输入要插入的数据位置);scanf(%d,&n);if(n=0)ptr=search(p,n);printf(请输入要插入的数据);scanf(%d,&m);if(!p)printf(没有找到!n);elsellist=insert(p,ptr,m);printf(插入后的链表为);Print(llist);break;case 4:llist=sort(p,5);Print(llist);break;case 5:printf(请输入要查找的数据);scanf(%d,&m);if(m!=0)ptr=search(p,m);if(!ptr)printf(没有找到!n);elseprintf(%d,ptr-num);printf(n);break;/*对链表进行计数输出*/case 6:count(p);break;/*对链表进行倒置输出函数*/case 7:llist=Daozhi(p);Print(llist);break;return 0;九、 运行结果及分析主菜单中显示各个功能块，提示用户选择相应的序号进行操作。功能1实现输出创建的链表的各个结点，从主函数输入的数组元素，通过链表的创建函数，最后由输出函数输出。功能2实现删除链表中的结点功能3实现向链表中插入数据结点。功能4实现对链表的结点进行排序，从小到大，最后输出排序后的链表。功能5实现查找某一个结点，若找到将输出此结点，若没有则显示没有找到！功能6实现对链表中结点个数进行统计，输出统计个数。功能7实现对链表中结点进行倒置输出。十、 收获及体会 总体来说，该程序实现了课程设计的算法和功能,链表相关的基本操作。我觉得首先得把基本算法弄懂，这是基础，然后建立结构体的模型。对于指针和地址的传递得好好弄清楚，每个细节弄清楚,弄明白。 在程序调试过程遇到了一些问题。但是我并没有气垒，在实验中发现问题，自己进行测试看是在哪儿出现了问题，独立思考，最终解决问题，从而也就加深我对理论知识的理解，达到了“双赢”的效果。 我觉得自己独立的思考过程很重要，否则要自己写程序、 写算法的时候根本写不出来，所以我想如果真的想学好数据结构的话，最好是能够自己思考问题，不要刚想了一会就觉得做不出来，然后就去