合工大宣城校区数据结构实验报告——单链表

《合工大宣城校区数据结构实验报告——单链表》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Word下载可编辑资源共享数据结构实验报告姓名学号专业班级指导教师实验时间11月9日实验地点计算中心实验二单链表实验1.实验目标①熟练掌握线性表的链式存储结构。②熟练掌握单链表的有关算法设计。③根据具体问题的需要，设计出合理的表示数据的链式存储结构，并设计相关算法。2.实验内容和要求Ⅰ.实验要求①本次实验中的链表结构指带头结点的单链表②单链表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；比如存储、算法实现放入文件：linkedList.h③实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；④程序有适当的注释。Ⅱ.

2、实验内容<1>尾插法创建单链表，打印创建结果。专业资料资源共享Word下载可编辑资源共享<2>头插法创建单链表，打印创建结果。<3>销毁单链表。<4>求链表长度。<5>求单链表中第i个元素（函数），若不存在，报错。<6>在第i个结点前插入值为x的结点<7>链表中查找元素值为x的结点，成功返回结点指针，失败报错<8>删除单链表中第i个元素结点<9>在一个递增有序的单链表L中插入一个值为x的元素，并保持其递增有序特性<10>将单链表Ｌ中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的单链表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果<

3、11>求两个递增有序单链表L1和L2中的公共元素，放入新的单链表L3中<12>删除递增有序单链表中的重复元素，要求时间性能最好<13>递增有序单链表L1、L2，不申请新结点，利用原表结点对2表进行合并，并使得合并后成为一个集合，合并后用L1的头结点作为头结点，删除L2的头结点，要求时间性能最好扩展实验：<1>（递增有序）单链表表示集合A、B，实现：C=AÇB，C=AÈB，C=A-BA=AÇB，A=AÈB，A=A-B专业资料资源共享Word下载可编辑资源共享<2>（递增有序）单链表表示集合A、B，判定A是否B的子集<3>已知一个带有表头结点的单链表，结点结构

4、如下图。假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。<4>(2011)（15分）一个长度为L（L≥1）的升序序列S，处在第个位置的数称为S的中位数。例如，若序列S1=(11,13,15,17,19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高

5、效的算法，找出两个序列A和B的中位数1.数据结构设计structNode{intvalue;Node*next;Node(intvalue=0,Node*pNext=0){this->value=value;this->next=pNext;}};classlinkedList{public:linkedList()；//构造函数~linkedList()；//<3>析构函数,销毁单链表intlength()；//<4>求链表长度专业资料资源共享Word下载可编辑资源共享Node*listLocateI(inti)；//<5>求单链表中第i个元素booll

6、istInsert(inti,intx)；//<6>在第i个结点前插入值为x的结点Node*listLocateX(intx)；//<7>链表中查找元素值为x的结点，成功返回结点指针，失败报错。boollistDelete(inti)；//<8>删除单链表中第i个元素结点Node*head;};1.算法设计<1>~<8>为书中已经给出的基本算法，<9>.定义一个指针p指向头结点，当p->next!=NULL，循环比较p->next->value与x的值之间的大小，若p->next->valuenext，当申请新结点，存储x，将新结点插入

7、在p之后，完成插入。<10>.定义两个链表L1，L2，定义指针*p，*u，*r，分别指向L的首元素结点，L1，L2的头结点上，循环判断，如果p->value%2!=0，就插入到表L1中，否则，就插入到表L2中，然后令p=p->next，直至p!=NULL结束循环，输出L1，L2，其中L1表示奇结点，L2表示偶结点<11>.定义两个链表L3，定义指针*p，*u，*r，分别指向L3的头结点，L1，L2的首元素结点上，循环判断，如果u->value==r->value，就把该值插入到表L3中，如果u->value>r->value，让r=r->next，否则让u

8、=u->next；当u==NULL或者r==NULL，结束循环，输