单链表的建立、删除、及建立递增的单链表.doc

《单链表的建立、删除、及建立递增的单链表.doc》由会员分享，可在线阅读，更多相关《单链表的建立、删除、及建立递增的单链表.doc（13页珍藏版）》请在三一办公上搜索。

1、班级： 数学112班 学号：201112010222姓名： 吕文辉 报告日期： 2012/12/9 试验一：单链表一、实验目的（1）掌握单链表的存储结构形式及其描述。（2）掌握单链表的建立、查找、插入和删除操作。二、实验要求（1）编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序）。（2）编写函数,实现遍历单链表。（3） 编写函数,实现把单向链表中元素逆置（不允许申请新的结点空间）。（4） 编写函数,建立一个非递减有序单链表。（5） 编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。（6） 编写函数,在非递减有序单链表中插入一个元素使链表仍然有序

2、。（7） 编写函数,实现在非递减有序链表中删除值为x的结点。（8）编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。三、实验代码：#include #include#include/typedef char elemtype;#define null 0const int n=20;int i=1;typedefstruct nodeelemtype data;struct node *p;node,*linklist;/void initlist(linklist L);/初始化单链表void createfromhead(linklist L); /利用头插法建立单链表；vo

3、id textlinklist(linklist L); / 检测单链表；void createfromtail(linklist L);/尾插法建立单链表；void linklistnizhi(linklist k);/单链表的逆置；void Lorder(elemtype an,int n);/给数组中元素排序；void increaselinklist(linklist k); /给单链表中的元素排序；linklist unittwolinklist(linklist k1,linklist k2); / 建立两个非递减有序单链表,然后合并成一个非递减链表。void DeleteIncr

4、easelinklist(linklist k); /编写函数,实现在非递减有序链表中删除值为x的结点void Insertelemtypelinklist(linklist k); /编写函数,在非递减有序单链表中插入一个元素使链表仍然有序void alllinklistfunctionlwh(char s); /将所有函数的整合在一个函数里面；void textlwhplinklist(linklist lwhp);/int main() cout*endl; cout头插法建立程序的眼演示实例endl当输入&符号的时候就默认(单链表的字符已经输完)退出endl; cout*endl;ch

5、ar s; cout如果执行程序请输入Ls; alllinklistfunctionlwh(s); /调试程序时要用到的代码； /* node lwh; linklist lwhp; lwhp=&lwh; initlist(lwhp);coutsizeof(node) sizeof(node)endl; coutsizeof(lwhp)sizeof(lwhp)endlsizeof(char)sizeof(char)endl; cout第一个为表头指针，不放数据，由于用的头插法，故输出链表的顺序和输入的顺序恰好相反endl; createfromhead(lwhp); createfromtai

6、l(lwhp); linklistnizhi(lwhp); 1逆置单链表； increaselinklist(lwhp);/给单链表中的元素排序； /建立另外一个单链表； node lwh1; linklist lwhp1; lwhp1=&lwh1; initlist(lwhp1); createfromtail(lwhp1); linklist lwhp2;lwhp2=unittwolinklist(lwhp,lwhp1);DeleteIncreaselinklist(lwhp); Insertelemtypelinklist(lwhp);char w; cout如果想检验是否成功建立单链表

7、，如果想检验就请输入y或Yw; if(w=y|w=Y) textlinklist(lwhp); */调试程序时要用到的代码；/return 0;/void alllinklistfunctionlwh(char s) int lwhf=1;if(L=s) cout如果想运行 初始化单链表函数 请输入0 endl;cout如果想运行 利用头插法建立单链表函数 请输入1 endl;cout如果想运行 尾插法建立单链表单链表 请输入2 endl; cout如果想运行 单链表的逆置函数 请输入3 endl; cout如果想运行 给数组中元素排序函数 请输入4 endl;cout如果想运行 建立两个非递

8、减有序单链表,然后合并成一个非递减链表函数 请输入5 endl; cout如果想运行 实现在非递减有序链表中删除值为x的结点 请输入6 endl;cout如果想运行 在非递减有序单链表中插入一个元素使链表仍然有序表函数 请输入7 endl; cout如果想运行 退出该层函数 请输入8 endl; cout请输入序号：i; while(lwhf) switch(i) case 0: cout初始化单链表函数endl; node lwh0; linklist lwhp0; lwhp0=&lwh0; initlist(lwhp0); textlwhplinklist(lwhp0); cout执行成功

9、endl; break; case 1:cout利用头插法建立单链表函数endl;cout请输入字符endl; node lwh1; linklist lwhp1; lwhp1=&lwh1; initlist(lwhp1); createfromhead(lwhp1); textlwhplinklist(lwhp1); break; case 2: cout 尾插法建立单链表单链表endl; cout请输入字符endl; node lwh2; linklist lwhp2; lwhp2=&lwh2; initlist(lwhp2); createfromtail(lwhp2); textlwh

10、plinklist(lwhp2); break; case 3:cout单链表的逆置函数 endl;cout请输入字符endl; node lwh3; linklist lwhp3; lwhp3=&lwh3; initlist(lwhp3); createfromtail(lwhp3); linklistnizhi(lwhp3); textlwhplinklist(lwhp3); break; case 4: cout给数组中元素排序函数endl; cout请输入字符endl; node lwh4; linklist lwhp4; lwhp4=&lwh4; initlist(lwhp4); c

11、reatefromtail(lwhp4); increaselinklist(lwhp4); textlwhplinklist(lwhp4); break; case 5: cout建立两个非递减有序单链表,然后合并成一个非递减链表函数endl; cout请输入第一个单链表的字符endl; node lwh50; linklist lwhp50; lwhp50=&lwh50; initlist(lwhp50); createfromtail(lwhp50); cout请输入第二个单链表的字符endl; node lwh51; linklist lwhp51; lwhp51=&lwh51; in

12、itlist(lwhp51); createfromtail(lwhp51); linklist lwhp52; lwhp52=unittwolinklist(lwhp50,lwhp51); textlwhplinklist(lwhp52); break; case 6: cout实现在非递减有序链表中删除值为x的结点 endl; cout请输入字符endl; node lwh6; linklist lwhp6; lwhp6=&lwh6; initlist(lwhp6); createfromtail(lwhp6); DeleteIncreaselinklist(lwhp6); textlwh

13、plinklist(lwhp6); break; case 7: cout在非递减有序单链表中插入一个元素使链表仍然有序表函数endl; cout请输入字符endl; node lwh7; linklist lwhp7; lwhp7=&lwh7; initlist(lwhp7); createfromtail(lwhp7); Insertelemtypelinklist(lwhp7); textlwhplinklist(lwhp7); break; default: break; cout请重新选择序号i;if(i!=1&i!=2&i!=3&i!=4&i!=5&i!=6&i!=7&i!=8)c

14、out如果不想选择序号就 输入字符f; if(f=y|f=Y) lwhf=1; else lwhf=0; void textlwhplinklist(linklist lwhp) char w; cout如果想检验是否成功建立单链表，如果想检验就请输入y或Yw; if(w=y|w=Y) textlinklist(lwhp);/ 所有函数的代码定义：void initlist(linklist L) / L=(linklist)malloc(sizeof(node); L-p=null;/头插法建立单链表；void createfromhead(linklist L) node *jiedian

15、; / jiedian=L; char zimu; bool flag=true; / cinzimu; /* if(zimu!=&) L-data=zimu; */ while(flag) cinzimu; if(zimu!=&) jiedian=(linklist)malloc(sizeof(node); jiedian-data=zimu; jiedian-p=L-p; L-p=jiedian;/ coutdatadatap; /建立指向单链表的第一个节点的指针； while(p1!=null) cout这是第i个节点data=data p=p p; i+; /利用尾插法建立单链表voi

16、d createfromtail(linklist L) linklist s,r; bool flag=true; r=L; char c; while(flag) cinc; if(c!=&) s=(linklist)malloc(sizeof(node); s-data=c; r-p=s; r=s; else r-p=null; flag=false; /单链表中元素逆置；void linklistnizhi(linklist k)/假设k是个由尾插法建立起来的单链表；/*算法思想：只交换元素的位置，不改变节点的指针*/ linklist k1,k2,k3; k1=k-p; k2=k1;

17、 k3=k1; int i=0,w; elemtype an; while(k1!=null) ai=k1-data; k1=k1-p; i+; w=i; for(i=0;iw;i+) coutaidata=aw-1; k3=k3-p; w=w-1;/编写函数,建立一个非递减有序单链表/编一个函数实现一个数组里的元素的逆置，该函数有2/参数一个是指针，一个就是，数组的个数，void Lorder(elemtype an,int n)int i,j,k; elemtype temp,*p; p=a;for(i=0;in-1;i+) k=i;for(j=i+1;jn;j+) if(*(p+j)p;

18、 k2=k1; k3=k1; int i=0,w; elemtype an; while(k1!=null) ai=k1-data; k1=k1-p; i+; w=i; Lorder(a,w); for(i=0;iw;i+) coutai ; int j=0; while(k3!=null&jdata=aj; k3=k3-p; j+; /编写函数,建立一个非递减有序单链表/建立两个非递减有序单链表,然后合并成一个非递减链表。/*思路：想想办法把2个单链表中的元素先排成有序的然后去出来在和并*/linklist unittwolinklist(linklist k1,linklist k2) i

19、ncreaselinklist(k2); increaselinklist(k1); linklist k3,p0,k4; k3=(linklist)malloc(sizeof(node); k4=k3; /*由于让k3不停的向链表的末尾跑 所以设置一个k4把它的值保留下来，最后当函数的返回值*/ k2=k2-p; k1=k1-p; while(k1!=null&k2!=null) p0=(linklist)malloc(sizeof(node); k3-p=p0; if(k1-datak2-data) p0-data=k2-data; k2=k2-p; else p0-data=k1-dat

20、a; k1=k1-p; k3=p0; while(k1!=null) p0=(linklist)malloc(sizeof(node); k3-p=p0; p0-data=k1-data; k1=k1-p; k3=p0;while(k2!=null)p0=(linklist)malloc(sizeof(node); k3-p=p0; p0-data=k2-data; k2=k2-p; k3=p0; k3-p=null; /* 当k3跑完时已经指向链表的最后一个单元 由于在把p0的值往单链表里连的时候用的 k3-p=p0; 及每次在k3指向的那个单元赋值，当为最后一个单元的时候应该给 其富nul

21、l，这是为了单链表能通过 textlinklist函数的检验 */ k3=k4; coutendl; textlinklist(k4); coutendl; return k4; /编写函数,在非递减有序单链表中插入一个元素使链表仍然有序void Insertelemtypelinklist(linklist k) increaselinklist(k);linklist k2,k3,k4;k4=k; int i=0; elemtype a1,a2; cout请输入要插入的元素a2; k2=(linklist)malloc(sizeof(node); k2-data=a2; while(k-p

22、!=null)&i=0) a1=k-p-data; if(a2p; k2-p=k3; k-p=k2; k=k-p; if(i=0) while(k-p=null) k-p=k2;k2-p=null;k=k4;/编写函数,实现在非递减有序链表中删除值为x的结点void DeleteIncreaselinklist(linklist k)increaselinklist(k); linklist k2; /*引入i的作用是为了判断是否成功删除 如果成功删除后，就终止while循环 及目的已经达到，可以退出循环了 */ int i=0; elemtype a,b,c; bool flag=true; while(flag) cout输入你想删除的元素a; while(k-p!=null)&(i=0) b=k-p-data; if(a=b) k2=k-p-p; free(k-p); k-p=k2; i=1; cout删除成功p; if(i=0)cout删除失败！endl; cout是否再次输入删除的元素如果想继续删除的话;cout就输入y或者Yc;if(c=y|c=Y)flag=true;else flag=false;