链表的操作.doc

链表的操作1.课程设计的目的1掌握线性链表的基本性质。2掌握线性链表的存储结构与基本操作的实现。2.课程设计的要求1. 利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。2. 利用线性链表实现对用户输入的一组数据进行插入排序。3.课程设计报告内容3.1运行环境联想计算机，WindowsXP操作系统，MS-DOS窗口，borland c+ builder 6.03.2算法设计的思想ADT list isOperations:*createlist():Input: a linklistPreconditions: data input from operator；end up with *Process: scanf(%d,&ch);/读人新数据； p=(linklist*)malloc(sizeof(linklist); /申请新结点； p-data=ch; p-next=NULL; r-next=p; r=r-next; ch=getchar( );Output:a linklistPostconditions: none*insertnode(linklist *head,char x,int i)Input: list,x,iPreconditions: creat a linklistProcess: s=(linklist*)malloc(sizeof(linklist);s-data=x;s-next=p-next;p-next=s; p=head;Output: pPostconditions:none*deletelist(linklist *head,int i)Input: An infix expressionPreconditions: NoneProcess:Output:Postconditions:*deletelist(linklist *head,int i)Input: list,iPreconditions: creat a linklistProcess: r=p-next; p-next=r-next; free(r) ;Output:pPostconditions:nonelocatelist(linklist *head,char x):Input: list,xPreconditions: creat a linklistProcess: while(p!=NULL)&(p-data!=x) p=p-next; i+; Output:iPostconditions:none lengthlist(linklist *head):Input: listPreconditions: creat a linklistProcess: while(p-next!=NULL) p=p-next; i+; Output:iPostconditions:nonevoid out_put(linklist *p):Input:listPreconditions: NoneProcess: while(p!=NULL) printf(%c,p-data); p=p-next; Output:pPostconditions:void insertsorting(linklist *head):Input: listPreconditions: creat a linklistProcess: while(s!=NULL) q=p; while(q!=s) if(s-datadata) i=s-data; s-data=q-data; q-data=i; q=q-next; s=s-next; Output:Postconditions:End ADT list3.3算法流程图1.在主函数中提供用户输入的提示信息，根据用户的需求，调用相应的函数。输入创建链表1.插入*insertnode()2.删除 *deletelist()找 n 4.计数 n 5.输出 n 6.进行插入排序3.查找 Locatel（）ist(选择相应的操作4.计数lengthlist()5.输出Out_put()6.排序Insertsorting()(2.各函数具体算法请见算法分析；3.4算法设计分析1.建立链表：动态的申请新的结点，不断地将新的结点插入表尾，修改表尾指针；最后返回表头指针；2.插入：此程序采用前插，需要*p的前趋*q，然后再完成在*q之后插入*s的后插。SP3.删除：删除*p需要先找到*p的前趋结点*q,然后完成指针的变化操作即可；qp4.查找：此程序采用按值查找法，从第一个结点起判断当前结点的值是否等于给定值，若找到则返回该结点地址，否则继续下一个结点；若整个表中未找到则返回NULL；5.计数：只要设一个移动指针扫描整个链表，就可以统计出元素个数即表长；6.输出：类似求表长，设一个移动指针扫描整个链表，将扫描到的值逐个输出，并且在其余几个函数中可反复调用此函数；7.插入排序：从第一个结点开始逐个比较交换；3.5源代码#include #includetypedef char datatype;typedef structnodedatatype data;struct node *next; linklist;linklist *p;linklist *createlist(void) /建立链表； char ch; linklist *head; linklist *p,*r; head=(linklist*)malloc(sizeof(linklist); /申请头结点； head-next=NULL; r=head; ch=getchar( ); /ch为建立与否标志； while (ch!=*)/*为输入数据结束符号； scanf(%d,&ch);/读人新数据； p=(linklist*)malloc(sizeof(linklist); /申请新结点； p-data=ch; p-next=NULL; r-next=p; r=r-next; ch=getchar( ); return (head);linklist *insertnode(linklist *head,char x,int i) /在链表第i位插入值为x的结点int j=0;linklist * p,*s;p=head; while(p&jnext;+j;if(!p|ji-1)exit(1);s=(linklist*)malloc(sizeof(linklist);s-data=x;s-next=p-next;p-next=s; p=head; return p;linklist *deletelist(linklist *head,int i) /删除链表第i位的结点 int j=0; linklist * p,*r; p=head; while(p&jnext;+j; if(p-next!= NULL) r=p-next; p-next=r-next; free(r) ; p=head; return p;int locatelist(linklist *head,char x) /查找； int i=1; linklist *p; p=head-next; while(p!=NULL)&(p-data!=x) p=p-next; i+; return i;int lengthlist(linklist *head) /求表长； int i=0; linklist *p; p=head; while(p-next!=NULL) p=p-next; i+; return i;void out_put(linklist *p) /输出链表； while(p!=NULL) printf(%c,p-data); p=p-next; printf(n);void insertsorting(linklist *head) /利用利用线性链表实现插入排序 linklist *p,*s,*q; char i; p=head-next; s=p-next; while(s!=NULL) q=p; while(q!=s) if(s-datadata) i=s-data; s-data=q-data; q-data=i; q=q-next; s=s-next; out_put(p);void main()linklist *list; int y,i;char x; linklist *p; cout输入字符建立一个单链表并以*号结尾:n;list=createlist(); cout-; coutn 1.插入 n 2.删除 n 3.查找 n 4.计数 n 5.输出 n 6.进行插入排序 n; cout-; couty; if(y=1) couti; coutx; cout原链表为：; out_put(list); p=insertnode(list,x,i); cout在第i位插入字符：; out_put(p); else if(y=2) couti; cout原链表为：; out_put(list); p=deletelist(list,i); cout在第i位删除一个字符: ; out_put(p); else if(y=3) coutx; i=locatelist(list,x); cout您要查找的字符位置是： i; else if(y=4) i=lengthlist(list); cout此链表的表长为： i; else if(y=5) cout输出建立的链表： ; out_put(list); else if(y=6) coutnext|ji-1) exit(1); 这句多余，永远访问不到 3. 在输出打印中判断条件 while(p-data!=*)越界了，因为p可能为NULL，改为while(p!=NULL)或者while(p)4.总结通过实验更清楚的了解到在单链表中插入和删除元素只需修改有关结点的指针域内容，不需要像顺序表那样移动元素，很好的降低了运算的时间复杂度。同时复习动态指针的生成，并注意到运行过程中指针的逻辑位置。将课本知识转化为自己的理解和概念。只有真正理解整个流程，才能很好的运用到设计中，在写程序之前先想好方案，画流程图，不仅让自己的思路更清楚，还能节省不少的时间。在参阅参考资料中设计的程序时，通过对实例的分析，更加了解循环语句的应用，同时也了解系统提供的一些子程序的功能，能更好的将这些功能应用于自己的设计中。将程序设计好以后，很大一部分时间在调试，不断思考和修改程序。此设计是在实验报告的基础上进行修改和优化，像是判断时用的if else语句，在原来的报告中对每个用户操作的判断都用if这样使得已经找到符合条件的语句进行操作后还得进行下面语句的判断，加长了程序运行中不必要的时间，因此在此设计中适当加入else就减少了不必要的判断时间。当程序