循环链表、双链表及链表应用试验试验报告试验目的(1)理解单循环链表及双循环链表的特点。(2)把握这两种构造的算法设计。(3) 运用链表存储数据并设计有关算法。(4) 理解头结点、头指针概念以及设置头结点的优点试验运行环境Visual C+试验任务为使试验程序简洁直观, 同样是将试验程序中将所需要的函数以调用库函数的形式给出, 并假设将库函数放在程序文件 “linklist.h“中, 同时假设该库函数文件中定义了链表构造中的指针类型为 link, 结点类型为 node, 双链表中结点的类型为 dunode, 其中有 data、next 和 prior 等字段, data 的类型为 int, 而 next 和 prior 分别为指示其下一个和前一个结点的指针, 类型为 dulink即dunode *。类似地, 定义了局部常用运算, 如构建链表、显示链表等。各运算的名称较为直观, 并有相应的注释, 因而易于理解和实现。读者在上机试验时, 需要自己设计出所涉及到的库函数 , 或者将函数放在试验程序中, 以便利试验程序的调试。试验要求1. 求链表中第 i 个结点的指针函数，假设不存在，那么返回 NULL。 2在第 i 个结点前插入值为x 的结点。3. 删除链表中第 i 个元素结点。4. 在一个递增有序的链表 L 中插入一个值为 x 的元素，并保持其递增有序特性。5. 将单链表中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保存原链表的显示结果，以便比照求解结果。6. 求两个递增有序链表 L1 和 L2 中的公共元素，并以同样方式连接成链表 L3。试验内容第一题：依次访问无头结点的单循环链表的各结点。试验测试数据根本要求：第一组数据：链表元素为 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40,50, 60其次组数据：链表元素为 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 试验预备：p=head;/由于没有首位，所以输入一点，令为首位do/*访问节点的语句*/；p=p-next;while(p！=head); /只让循环进展一次，避开进入死循环，所以用 p！=head/作为推断条件其次题：设计算法以推断一个带头结点的单循环链表是否满足这样的条件：其中每个结点的元素值与其序号的差确实定值不大于。假设成立, 返回 TRUE, 否那么返回FALSE。试验测试数据根本要求： 第一组数据：链表元素为1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18其次组数据：链表元素为1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 20, 18试验预备：If(p-data-idata-i=-3) return TRUE;/推断每个结点的元素值与其序号的差确实定值是否不大于 else return FALSE;第三题：利用递增有序的单循环链表表示集合, 分别求两个链表表示的集合的交、并集所构成的链表。试验测试数据根本要求： 第一组第一个链表元素为1,3,6,10, 15, 16,17, 18, 19, 20其次个链表元素为1,2,3,4, 5, 6, 7,8, 9, 10, 18, 20, 30其次组第一个链表元素为1,3,6,10, 15, 16,17, 18, 19, 20其次个链表元素为2,4,5,7, 8, 9, 12, 22第三组第一个链表元素为其次个链表元素为1,2,3,4, 5, 6, 7, 8, 9, 10试验预备：C=xy,node*px,*py;/建立一个表C 和指针px pypx-data=py-data;px=px-next;py=py-next; /假设px 指向的数据/等于py 指向的数据，px 和 px 就同时向后连续px-datapy-data;py=py-next; / 假设px 指向的元素假设大于py，依据递增/有序，那么只需 py 向后搜寻比当前 py 指向的数据大的/数据来和当前px 指向的数据推断是否相等px-datadata;px=px-next; / 假设 px 指向的元素假设小于 py，依据递/增有序，那么只需 px 向后搜寻比当前 px 指向的数据大/的数据来和当前py 指向的数据推断是否相等x=xUy;/取表 x,将y 与x 元素做同样比较py-data!=px-data;将 py-data 插入x 表；第四题：编写算法以构造带头结点的双循环链表。试验测试数据根本要求：第一组数据：链表元素为 1,2,3,4,5,6,7,8,9,10其次组数据：链表元素为 10,30,40,55,60,70,88,99,100试验预备：struct dnodeelementtype data;dnode*prior,*next;/先建立空表head=new dnode;指针指向null;p 指向当前节点；/然后进展尾插入；p-next=s;s-prior=p;p=head;首尾相接；第五题：编写算法以推断一个带头结点的双循环链表是否是对称的 , 假设成立, 返回TRUE, 否那么返回 FALSE。试验测试数据根本要求：第一组数据：链表元素为1,2,3,4,5,4,3,2,1其次组数据：链表元素为1,2,3,4,5,5,4,3,2, 1第三组数据：链表元素为1,2,3,4,5,6,3,2,1第四组数据：链表元素为试验预备：1,2,3,4,5,5,6,4,3, 2, 1px=head-next;py=head-prior; /指针 px 指向后一数据，/指针py 指向头元素的前一数据while(px!=py)/假设指针 px 和 py 指向的不是同一数/以此来作为完毕循环的条件if(px-data!=py-data) /只要有任意px 和 py 指向数据不相等，return false; /那么该链表是不对称的px=px-next;py=py-prior; /只要任意px 和 py 指向/数据未消灭不相等，那么连续向后查找return ture;试验程序#include #include structNodeintdata1;Node*next1;structDnodeintdata2;Dnode*prior,*next2;classlistprivate:Node*head1,*rear1; public:list();voidfirst();/第一题函数boolsecond();/其次题函数voidthird_1(list&L1,list&L2);/第三题函数交集voidthird_2(list&L1,list&L2);/第三题函数并集voidcreat();/创立单链表;classdouble_listprivate:Dnode*head2,*rear2; public:double_list();voidfourth();/第四题函数boolfifth();/第五题函数voidcreat_d();/创立双链表;list:list()head1=newNode; head1-next1=NULL; rear1=head1;voidlist:creat()/创立单链表函数Node*u; intx;cout“请输入单循环链表的数据，输入-1 完成输入“x;while(x!=-1)u=newNode; u-data1=x;rear1-next1=u; rear1=u; cinx;rear1-next1=head1;double_list:double_list()head2=newDnode; head2-next2=NULL; head2-prior=NULL;rear2=head2;voiddouble_list:creat_d()/创立双链表函数Dnode*u; intx;cout“请输入双循环链表的数据，输入-1 完成输入“x;while(x!=-1)u=newDnode; u-data2=x;rear2-next2=u; u-prior=rear2; rear2=u; cinx;rear2-next2=head2; head2-prior=rear2;void list:first()/第一题函数:访问无头结点的单循环链表的各结点Node*u=head1; head1=u-next1; rear1-next1=head1; deleteu; Node*p=head1;docoutdata1next1;while(p!=head1); coutnext1;booln=true; for(inti=1;p!=head1&n!=false;i+,p=p-next1)if(i-p-data1data1-inext1; pb=L2.head1-next1;while(pa!=L1.head1&pb!=L2.head1)if(pa-data1data1)pa=pa-next1; elseif(pa-data1pb-data1)pb=pb-next1; elseu=newNode;u-data1=pa-data1; rear1-next1=u; rear1=u;pa=pa-next1; pb=pb-next1;c