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

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

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

3、单链表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<2>（递增有序）单链表表示集合A、B，判定A是否B的子集<3>已知一个带有表头结点的单链表，结点结构

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

5、能高效的算法，找出两个序列A 和B 的中位数3. 数据结构设计struct Node int value; Node *next; Node(int value = 0, Node *pNext = 0) this->value = value; this->next = pNext; ;class linkedListpublic : linkedList()；/构造函数 linkedList()；/<3>析构函数,销毁单链表 int length()；/<4>求链表长度 Node *listLocateI(int i)；/<5>求单链表中第i

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

7、gt;next->value<x，就令p = p->next，当申请新结点，存储x，将新结点插入在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->val

8、ue=r->value，就把该值插入到表L3中，如果u->value>r->value，让r=r->next，否则让u=u->next；当u=NULL或者r=NULL，结束循环，输出L3；<12>.将元素分为两部分，一部分是已经处理元素，和待处理元素。用r指向最后一个已经处理元素，用u指向还未处理的元素，如果u->value < r->value，就让u->next=r，删除中间的重复元素，否则就令r=r->next，当r=NULL结束循环，令u->next=NULL，输出L<13>.定义指针*p1

9、,*p2,*u；p1,p2分别指向L1的头结点和L2的首元素结点，判断p1->next->value与p2->value大小，前者大，则将p2插入到p1后面，后者大则让p1=p1->next，相等则p2=p2->next，p1=p1->next，当p1->next =NULL或p2=NULL结束循环。若p2 !=NULL，直接将其接到p1之后，删除L2.head，输出L1.扩展实验：<1>. 对于采用集合C的运算，将符合要求的元素插入到新链表C中，对于不采用链表C的运算，就对链表A中元素进行插入与删除操作。<2>.使用两个指针*

10、u，*r，分别指向A，B的首元素结点，对A中元素按顺序进行判断，如果出现u->value<r->value，则表示A不为B的子集，如果u->value>r->value，则r = r->next，如果u->value=r->value,则u = u->next，r = r->next，如果对A中每个元素进行判断，均可在B中找到，则A为B的子集。<3>.采用两个指针*u = L.head，*r = L.head->next，加入一个计数器i，i表示已经经过的结点，r每移动一次，i+，当i>k，u开始移动，当

11、r移动到表尾时，u即指向倒数第k个位置上的结点；若u为头结点，则其未移动，表示无倒数第k个位置上的结点。<4>.因为两个序列A 和B等长升序，故只需按照递增有序的顺序找到第A.length()即可，可以对A，B元素进行排序，到第A.length()结束即可输出该值为中位数。5. 运行和测试菜单：<9><10><11><12><13>扩展实验：<1>C=AÈB，C=AÇBC=A-BA=AÈBA=AÇBA=A-B<2><3><4>6. 总结和心得在此次程序编写的过程中，我总结第一次的经验教训，对程序整体先进行了构建，避免了重复输出的问题。然而，在编写过程中，针对此次实验又出现了不少新的问题，下面进行相关总结：1. 在重置链表时，开始未将头结点的后继设为NULL，导致输出时出现异常，花费大量时间才找到这一错误；2. 在完成向新链表中传入元素时，直接采用原来的结点，导致出现原链表异常，影响实验功能，最后采用创建新结点解决；3. 删除重复元素时，一开始采用逐个删除，时间复杂度过高，后采用两个结点，一次性删除所有重复元素，提高了时间性能；4. 在处理扩展实验三时，