《数据结构》课程实验报告二

数据结构课程实验报告二 单链表班级： 学号： 姓名：一、实验目的和要求： 1掌握动态链表结构及有关算法的设计。 2理解带头结点和不带头结点的单链表的特点，掌握使用相应结构 的算法设计。二、实验内容（给出具体的说明文字和操作图片）已知不带头结点的链表结构定义及头插法建表、尾插法建表和打印链表等函数定义在linklist.h文件），基于该文件完成实验题。1.编写函数删除不带头结点单链表head中的第一个值为x的结点，并构造测试用例进行测试。# include # include /*请将本函数补充完整，并进行测试*/typedef int datatype;/datatype 等价于 inttypedef struct link_nodedatatype data;struct link_node *next;node;/node 等价于 st rue t link_node typedef node *linklist;/linklist 等 价 于 struct link_node*/创建单链表(不带头结点)linklist creatfromrear(void)linklist head,r,s;/datatype x;/x 为 data 域的值head=r=NULL;/structlink_node*head=NULL / 不同 之处，不需要创建头结点prin tf(请输入若干整数序列:n);scanf(%d,&x);while (x!=0) /*以0结束输入*/s=(linklis t)malloc(sizeof(node);/分配动态内存，s-data=x;if (head二二NULL)/如果首节点为空，则新节点就是下一循环的首节点head=s;elser-next=s; /将旧的尾节点指向新节点r=s;/此时新节点为下一循环的尾节点 scanf(%d,&x);if (r!= NULL) r-next二NULL;/(r)代表 r! = NULLreturn head;/*返回建立的单链表*/输出链表void print(linklist head)linklis t p;/创建一个新节点/int i=0;p=head;/ 新节点指向首节点if(p=NULL)prin tf(空链表n);elseprintf(List is: n);while(p)/p 等价于 p!二NULLt比if省事/*i+;(i%10=0)printf(%dt,p-data);/ p=p-next;ifprintf(n);*/ while 循环输出链表的值printf(n);void delLis t(linklis t head)/定义释放函数 linklist p=head;while (p) head=p-next;free(p);p=head;linklist delx(linklist head,datatype x)linklist q;linklist t= head;if( t-da ta=x)/可别丢了q=t-next;free(head);head=q;elseq=t-next;while(q-next!= NULL&q-data!=x) t=t-next;q=q-next;if(x=q-data)t-next=q-next;free(q);return head int main()/完成本算法的答题思路是根据main函数的流程一 个一个去定义好函数就okdatatype x;/ int x;linklis t head;/ st rue t link_node *head 定义一个结构 体指针变量head= ereatfromrear (); /*尾插入法建立单链表*/print(head);printf(请输入要删除的值：);seanf(%d,&x);head=delx(head,x); /*删除单链表的第一个值为 x 的结点*/print(head);delList(head); /*释放单链表空间*/定 义释放函数*/return 0;I CiXU sersAdm i ri i stratorD esktopD ebu1. exe|请输入若干整数序列:9 201874410 90List is:92018744109请输入要删除的值：9List is:2018744109Press any key to continue.2. 已知带头结点的单链表的存储结构定义同实验 1，修改 linklist.h 头文件中头插法、尾插法建表函数及链表输出函数，使 其能正确应用于带头结点的单链表，在此基础上，完成实验题 2,编 写函数，删除带头结点单链表 head 中第一个值为 x 的结点。并构 造测试用例进行测试。# include # include /*请将本函数补充完整，并进行测试*/typedef int datatype;typedef struct link_nodedatatype data;struct link_node *next;node;ty pedef node *linklis t; /linklis t 等价于 st rue t link_node*/创建单链表(带头结点)linklist ereatfromrear(void)linklist head,r,s;/head=(linklist)malloc(sizeof(node);/ 1不同之处，分配动 态内存创建一个头结点head-next=NULL;datatype x;r=head;prin tf(请输入若干整数序列:n);scanf(%d,&x);while (x!=0) /*以0结束输入*/s=(linklist)malloc(sizeof(node);s-data二x;/把x赋给新节点的data域r-next二s;/把旧的尾结点的next域指向新节点(s) s-next=NULL;r=s;/此时新节点就是下一循环的尾节点scanf(%d, &x);/就因为少了一个scanf花了我一个晚上都没弄出来 - -return head;/*返回建立的单链表*/输出链表void print(linklist head)linklist p;p=head-next;/int i=0;if(p=NULL)prin tf(空链表n);elseprintf(List is: n);while(p)printf(%dt,p-data);p=p-next;/i+;/ if (i%10=0) printf(n);printf(n);void delLis t(linklis t head)/定义释放函数 linklist p=head-next;while (p) head=p-next;free(p);p=head;linklist delx(linklist head,datatype x)linklist q;linklist t= head-next;if(t-data=x)/考虑删除x为第一个时的情况q=t-next;free(t);head-next=q;elseq=t-next;while(q-next!= NULL&q-data!=x) t=t-next;q=q-next;if(x=q-data)t-next=q-next;free(q);return head ;int main()/完成本算法的答题思路是根据main函数的流程一个一 个去定义好函数就okdatatype x;/ int x;linklist head;/ struct link_node *head 定义一个结构体指 针变量head= creatfromrear (); /*尾插入法建立单链表*/print(head);printf(请输入要删除的值：)；scanf(%d,&x);print(head);delList(head);函数*/*释放单链表空间*/定义释放return 0; C:LJ s er sAd mini strato reslktop Debu舌 2 1.exeI请输入若干整数序列:20 7 18 7 44 109 0Lit is:20718744109请输入要删除的值：7List is:2018744109Press any key to continue3. 假设单链表 head 是升序排列的， 设计算法函数将值为 x 的结 点插入到链表 head 中，并保持链表有序性。分别构造插入到表头、 表中和表尾三种情况的测试用例进行测试(在不带头结点和带头结点 单链表head两种结构中任选一种算法设计，并说明原因)。/选择带头结点的单链表 因为带头结点的单链表操作更简单，插入 表头操作更容易实现#include stdio.h# include /*请将本函数补充完整，并进行测试*/typedef int datatype;typedef struct link_nodedatatype data;struct link_node *next;node;typedef node *linklist;/*请将本函数补充完整，并进行测试*/linklist creatfromrear(void)linklist head,r,s;/head=(linklist)malloc(sizeof(node);head-next=NULL;datatype x;r=head;prin tf(请输入若干整数序列:n);scanf(%d,&x);while (x!=0) /*以0结束输入*/s=(linklist)malloc(sizeof(node);s-data=x;r-next=s;s-next=NULL;r=s;scanf(%d,&x);return head; void print(linklist head)linklist p;p=head-next;/int i=0;if(p=NULL)prin tf( 空链表n)；elseprintf(List is: n);while(p)printf(%dt,p-data);p=p-next;/i+;/ if (i%10=0) printf(n);printf(n);linklist insert(linklist head,datatype x)/linklist s,p;p=head;s=(linklist)malloc(sizeof(node);s-data=x;s-next=p-next;p-next=s;return head;void delLis t(linklis t head)/定义释放函数 linklist p=head-next;while (p) head=p-next;free(p);p=head;int main()datatype x;linklist head;printf(输入一组升序排列的整数：)；head= creatfromrear(); /*尾插入法建立单链表*/print(head);printf(请输入要在表头插入的值：)；scanf(%d,&x);head=insert(head,x); /*将输入的值插入到单链表适当位置*/print(head);delList(head);return 0;C:U sersAd minis-trat orD e-sktopD eb u 日峯漏為舌 2.3.1.exe-输入一组升序排列的整数：请输入若干整数序列：10 100 1000 10000 100000 0List is:10 100 1000 10000 100000 请输入要在表头插入的值：1List is:1 10 100 1000 10000 100000 Press any key to continile插入表中算法实现：#include # include /*请将本函数补充完整，并进行测试*/typedef int datatype;typedef struct link_nodedatatype data;struct link_node *next;node;/*请将本函数补充完整，并进行测试*/linklist creatfromrear(void)linklist head,r,s;/head=(linklist)malloc(sizeof(node);head-next=NULL;datatype x;r=head;printf(请输入若干整数序列:n);scanf(%d,&x);while (x!=0)s-data=x;r-next=s;第一次r是head的next指向s, 其他的r-next都是上次循环的生成的节点s,s-next=NULL;r=s;这里把s赋给r的目的是好使s指向下一循环的新节点sscanf(%d,&x);return head;linklist p;p=head-next;/int i=0;if(p=NULL)printf(空链表 n);elseprintf(List is: n);while(p)printf(%dt,p-data);p=p-next;/i+;/ if (i%10=0) printf(n);printf(n);linklist insert(linklist head,datatype x ,datatype loc) linklist s,p;p=head;int j=0;while( p & jnext;j+;s=(linklist)malloc(sizeof(node);s-data=x;s-next=p-next;把 p-next 地址赋给 s-nextp-next=s;/p-next 指向 sreturn head;void delList(linklist head) linklist p=head;while (p) head=p-next;free(p);p=head;int main()datatype x,loc;linklist head;printf（-输入一组升序排列的整数：）;head= creatfromrear();print(head);printf（请输入要在表中插入的值和插在哪一位数后面：）;scanf(%d %d,&x,&loc);head=insert(head,x,loc);print(head);delList(head);return 0;II 0 谓0寻花A逝S怙屮出ugj黑浹岂232冲h齣入一组升序排列的整数；请输入若干整数序列:9 99 999 99999 999999 99999999 999999999 0List i s 9的9999999999999399399999999999999请输入建在去中插入的柱和插在哪一位数石面：9999 3List is:99999999999999999999999999999999999999Press any key to continue在表尾实现：#include # include /*请将本函数补充完整，并进行测试*/ typedef int datatype;typedef struct link_nodedatatype data;struct link_node *next;node;typedef node *linklist;/*请将本函数补充完整，并进行测试*/ linklist creatfromrear(void)linklist head,r,s;/head=(linklist)malloc(sizeof(node);head-next=NULL;datatype x;r=head;printf(”请输入若干整数序列:n);scanf(%d,&x);while (x!=0)s=(linklist)malloc(sizeof(node);s-data=x;r-next=s;s-next=NULL;r=s;scanf(%d,&x);return head;void print(linklist head)linklist p;p=head-next;/int i=0;printf(List is: n);while(p)printf(%dt,p-data); p=p-next;/ i+;/ if (i%10=0) printf(n);printf(n);linklist insert(linklist head,datatype x )linklist q,p;q=head;p=(linklist)malloc(sizeof(node);p-data=x;p-next=NULL;while(1)if(q-next=NULL)q-next=p;break;elseq=q-next;return head;void delList(linklist head) linklist p=head-next;while (p) head=p-next;free(p);p=head;int main()datatype x;linklist head;printf(”输入一组升序排列的整数：”);head= creatfromrear();print(head);printf（”请输入要在表尾插入的值：”）;scanf(%d,&x);head=insert(head,x);print(head);delList(head);return 0;l-.!llU5en5iniin|5rr6n：oniLr05KI0Pi1LWD1jg*.S.tead.5,i.ra输入一纠.升丿衬t列的整数：请转入若十整数1苹列:44 77 444 777 4444 7777 44444 77777 444444 0List is:4477444777444477774444477777444444请输入要在表尾插入的值:777777Li st Is:4477444777444477774444477777444444777777Press any key to continue.三、实验过程中遇到的问题及解决办法。四、实验总结。