3数据结构实验链表答案

1、实验报告院（系）：信息科学与技术学院课程名称：数据结构日期:班级专业学号实验室姓名计算机号实 验 名 称所 用 软 件 实 验 目 的线性链表的运算V C 或 TC1.2.3.掌握线性链表的基本概念掌握线性链表的建立、插入和删除等方法。 掌握线性链表的基本算法。成绩评定教师签名实 验 总 结#i nclude stdio.h#i nclude stdlib.htyp edef char elemt ype;typ edef struct no deelemt ype data;struct node *n ext; NODE,*NODE PTR;NODEPTR一、程序:createlistf(

2、) char ch;NODE PTR head;NODE *p; head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;ch=getchar(); while(ch!=n) p=(NODE *)malloc(sizeof(NODE); p-data=ch;p-n ext=head-n ext; head-n ext=p;ch=getchar();return (head);/* q指向p的后继结点*/*修改P结点的指针域*/*删除并释放结点*/int In sLi nkList(NODE *p, char x)NODE *s;/*定义指向结点类型的

3、指针*/s=(NODE *)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-n ext =p-n ext;p-n ext=s;return 1;void DelL in kList(NODE *p) NODE *q;if(p- next!=0) q=p-n ext;p-n ext=q-n ext; free(q); NODE *lbcz(NODE *h,i nt x) NODE *p;p=h;while (p!=0 & p-data!=x) p=p-n ext;return( p);void prin tl in k(NODE *h)NODE *p;p=h-n

4、ext;prin tf(n);while (p !=0)prin tf(%c, p-data);p=p-n ext;prin tf(n);void mai n()NODE *h,* p;charx;printf(n头插法建立单链表，应包含字符a,以回车作为结束符n);h=createlistf();printf(n建立的单链表为n);prin tl in k(h);printf(n在链表中查找字符an);p=lbcz(h,a);printf(n将字符k插入到字符a后面n);In sLi nkList( p,k);printf(n插入字符后的链表为n);prin tl in k(h);print

5、f(n输入链表中被删除字符的前一个字符n);scan f(%c, &x);p=lbcz(h,x);printf(n删除该字符后的一个字符n);DelLi nkList( p);printf(n删除字符后的链表为n);prin tl in k(h);知甜建立单班衷.应包含宇弘.呃M作宠结朿利 ocbriiruhbairhf brR腼入宇符后射坯衷为Hirhfhck输入钵表中被刑璨三蔚的前一八字符lA州除该字轩G的一字符删矗字符后閑缝表为二、源代码以及输入数据输出结果为:#in clude stdio.h#i nclude stdlib.htyp edef int elemt ype;typ ed

6、ef struct no deelemt ype data; struct node *n ext; NODE,*NODE PTR;NODE PTRcreatelistf()int ch;NODE PTR head;NODE *p;head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;sca nf(%d,&ch);while(ch!=0) p=(NODE *)malloc(sizeof(NODE); p-data=ch;p-n ext=head-n ext;head-n ext=p;/*定义指向结点类型的指针 */scan f(%d，& ch);r

7、eturn (head);int In sLi nkList(NODE *h, i nt x)NODE *s,*q,* p;p=h;q=p;while( p-n ext!=NULL & p-data next;0作为结束n”);用先傭法建廿序镀龛 注意输入数字的顺序与得到烦序相民 如忙勺结束98 87 34 76 65 52 41 32 0a立的链表为32 41 52 65 7& 4 87 99血诟的链表为32 41 52 55 65 76 84 37 ?S三、已知单链表L,写一算法，删除其重复结点。算法思路：用指针P指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之

8、；P指向下一个；依此类推，P指向最后结点时算法结束。源程序如下：#in elude stdio.h#i nclude stdlib.htyp edef char elemt ype;typ edef struct no de elemt ype data; struct node *n ext; NODE,*NODE PTR;NODE PTR createlistf() char ch;NODE PTRNODE *p;printf(”printf(”head;头插法建立链表n);请输入字符串，以回车键结束:head=(NODE PTR )malloc(sizeof(NODE);head-n e

9、xt=0; ch=getchar();while(ch!=n) p=(NODE *)malloc(sizeof(NODE);p-data=ch;p-n ext=head-n ext;head-n ext=p;ch=getchar();return (head);void deLi nkList(NODE PTR H) NODE *p ,*q,*r;p=H-n ext;while (p !=NULL) q=p;while (q- next!=NULL)/ if (q-n ext-data=p-data) r=q-n ext;/q-n ext=r- n ext;free(r);else q=q-n

10、 ext;/while(q- next)p”);指向第一个结点从*p的后继开始找重复结点找到重复结点，用r指向，删除*rp=p-n ext;/p指向下一个，继续/while( p-n ext)void pli nk(NODE *h)NODE *p;p=h-n ext;prin tf(n);while (p !=NULL)prin tf(%c, p-data);p=p-n ext;prin tf(n);void mai n()NODE *h;h=createlistf();printf(建立的链表为);pli nk(h);deLi nkList(h);printf(”删除了重复结点的链表为”)；

11、pli nk(h);St C;enl s and Sett ingsAdsinist ratd斗袖法建缩表请输人罕W串.以回车镶结fiSDFflSPEEFRS 建立的链表齐SAFEEDSAFDSA删除了重复结点的链表为SflFEDFres3 any Fey to continue四、设有两个单链表 A、B,其中元素递增有序，编写算法将A B归并成一个按元素值递减（允许有相同值）有序的链表C,要求用A、B中的原结点形成，不能重新申请结点。#i nclude stdio.h#in elude stdlib.htyp edef int elemt ype; typ edef struct node

12、elemt ype data; struct node *n ext; NODE,*NODE PTR;NODE PTR createlistfO/使用尾插法建立线性链表 int x;NODE PTR head,r;NODE *p;head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;r=head;/rprin tf(请输入整型数据到线性表中，scan f(%d, &x);while(x!=-1)作为尾指针-1作为结束符n);/ p=(NODE *)malloc(sizeof(NODE); p-data=x;r-n ext =p;r=p;scan f

13、(%d，& x);r-n ext=0;return (head);NODE PTR merge(NODE PTR A,NODE PTR B) NODE PTR C;NODE *p ,*q,*s;p=A-n ext;q=B-n ext;C=A;C- next=NULL;free(B);while (p&q) if (p-datadata) s=p;p=p- next; elses=q;q=q- next; s-n ext=C-n ext; C-n ext=s;if (p=NULL) p=q; while (p)/ s=p;p=p-n ext; s-n ext=C-n ext; C-n ext=s

14、; return C;void pli nk(NODE *h)c/while使用-1作为输入结束符/ 线性链表的合并表的头结点从原AB表上摘下较小者 插入到C表的头部将剩余的结点一个个摘下插入到C表的头部*/线性链表的输出047774別Press any kew to contiNODE *p;p=h-n ext;prin tf(n);while (p !=0)prin tf(%d ”,p-data);p=p-n ext;prin tf(n);void mai n()NODE *a,*b;printf(建立有序线性链表a和线性链表b (升序)n);a=createlistf();b=creat

15、elistf();printf(所建立的线性链表a和线性链表b分别为：n);pli nk(a);pli nk(b);a=merge(a,b);printf(”合并后的线性链表为：n);pli nk(a);841113 IE 3545合并后的线性锥表为;55453635 iS 131211inue五、已知单链表表示的线性表中含有两类的数据元素（字母字符，数字字符）。试设计算法，按结点的值将单链表拆分成两个循环链表，分别只含有数字或字母。要求：利用 原表中的结点空间作为这两个表的结点空间，头结点可另开辟空间。#i nclude stdio.h#in elude stdlib.h typ edef

16、char elemt ype; typ edef struct nodeelemt ype data; struct node *n ext; NODE,*NODE PTR;/单链表的输出/使用尾插法建立线性单链表NODE PTR createlistfO char x;NODE PTR head,r;NODE *p;head=(NODE PTR )malloc(sizeof(NODE); head-n ext=0;r=head;/r作为尾指针printf(”请输入字符到线性表中，以回车作为结束符n);x=getchar();使用回车作为输入结束符while(x!=n)/ p=(NODE *)

17、malloc(sizeof(NODE);p-data=x;r-n ext =p;r=p；x=getchar();r-n ext=NULL;return (head);void pli nk(NODE *a)NODE *p;p=a-n ext;prin tf(n);while (p !=NULL)prin tf(%c ”,p-data);p=p-n ext;prin tf(n);void ploo plin k(NODE *a)NODE *p;p=a-n ext;prin tf(n);while (p !=a)prin tf(%c ”,p-data);p=p-n ext;prin tf(n);循

18、环单链表的输出/线性链表的拆分/void chaife n(NODE PTR h) NODE PTR a,b;NODE *ar,*br,* p;if(h-n ext =NULL) retur n ;a=(NODE PTR )malloc(sizeof(NODE);a-n ext=a;/ar=a;b=(NODE PTR )malloc(sizeof(NODE);/b-n ext=b;br=b;p=h-n ext;while( p!=NULL)if(p-data=0 & p-datan ext=p; ar=ar- n ext;else申请a头结点申请b头结点br-n ext=p ;br=br- n

19、 ext; p=p-n ext;ar-n ext=a;br-n ext=b;printf(”拆分后的线性链表为：n);ploop li nk(a);ploop li nk(b);prin tf(n); void mai n()NODE *a;printf(”建立线性链表an);a=createlistf();printf(”所建立的线性链表a为：n);pli nk(a);prin tf(对线性链表进行拆分n);chaife n( a);建立践性铠表岂请输入字符到践性表中，以回车作为结束符12讦6七5石S日WSfdGh?所建立的线性犍表我为：8ffk5fd61i7fPvessan即 keytoc

20、 0 n t: in lie用参数传递方式：/*已知单循环链表表示的线性表中含有两类的数据元素(字母字符，数字字 符)。试设计算法，按结点的值将单链表拆分成两个循环链表，分别只含有数字或 字母。要求：利用原表中的结点空间作为这两个表的结点空间，头结点可另开辟空 间。*/#i nclude stdio.h#i nclude stdlib.h#defi ne NULL 0typ edef char elemt ype;typ edef struct nodeelemt ype data;struct node *next;/头插法建立循环单链表 NODE,*NODE PTR;NODE PTR cr

21、eatelistfOchar ch;NODE PTR head;NODE *p;head=(NODE PTR )malloc(sizeof(NODE);head- next=head;/建立循环空链表ch=getchar();while(ch!=n) p=(NODE *)malloc(sizeof(NODE);p-data=ch;p-n ext=head-n ext;head-n ext=p;ch=getchar();return(head);void chaife n(N ODE PTR h,NODE PTR *a,NODE PTR *b) II 线性链表的拆分 NODE *ar,*br,* p;if(h-n ext=h) return ;II 空表返回(*a)=(NODEPTR )malloc(sizeof(NODE);