数据结构实验二链表

《数据结构实验二链表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验二1、实验目的·熟练掌握线性表的链式存储结构定义及基本操作·理解循环链表和双链表的特点和基本运算2、实验内容：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。1．问题描述：利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作：·初始化一个带表头结点的空链表;·创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。又分为逆位序(插在表头)输入n个

2、元素的值和正位序(插在表尾)输入n个元素的值;·插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入），且保持结点的数据按原来的递增次序排列，形成有序链表。·删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部删除（值删除）;·输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点;·求前驱结点是根据给定结点的值，在单链表中搜索其当前结点的后继结点值为给定的值，将当前结点返回;·求后继结点是根据给定结点的值，在单链表中搜索其当前结点的值为给定的值，将后继结点返回;·两个有序链表的合并是分别将两个单链表的结

3、点依次插入到第3个单链表中，继续保持结点有序;编写主程序，实现对各不同的算法调用。其它的操作算法描述略。2．实现要求：对链表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价。·“初始化算法”的操作结果：构造一个空的线性表L，产生头结点,并使L指向此头结点;·“建立链表算法”初始条件：空链存在;操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的结果;·“链表（位置）插入算法”初始条件：已知单链表L存在;操作结果：在带头结点的单链线性表L中第i个位置之前插入元素e;·“链表（位置）删除算法”初始条件：已知

4、单链表L存在;操作结果：在带头结点的单链线性表L中，删除第i个元素,并由e返回其值;·“输出算法”初始条件：链表L已存在;操作结果：依次输出链表的各个结点的值;·“求前驱算法”初始条件:线性表L已存在;操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱;·“求后继算法”初始条件:线性表L已存在;操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继;·“两个有序链表的合并算法”初始条件:线性表单链线性表La和Lb的元素按值非递减排列;操作结果:归并La和Lb得到新的单链表。3、实验指导1．根据一个完整的C语言组成，将实验内容组合成如上

5、所述的三个组成部分，功能清晰明了，其常量定义和常用系统函数原型声明的文件“pubuse.h”代码复用，不需另行建立。2．建立一个单链表类型定义的头文件，如取名为：linklistDef.h，以后凡使用该文件定义的类型，就只需使用包含语句#include“linklistDef.h”即可。3．关于实验内容要完成的操作，一般都以独立的算法出现，建立一个单链表的基本算法文件,将各种不同算法组合在一个文件之中，存储为一个头文件如取名为：linklistAlgo.h，后凡涉及到要使用本文件中的单链表算法，一定要在你的文件的前面加上一条#include“linklistAlgo.h”即可，实现的算法函

6、数，如ListInit_Link、ListInsert_Link、ListDelete_Link、ListTraverse_Link、PriorElem_Link、NextElem_Link、GetElem_Link、MergeList_Link等;4．还应包含一个main函数，作为整个程序的执行入口处，定义测试的数据，完成各种算法的调用执行，对算法的执行过程和结果进行判断和输出控制，存储为一个源文件（如取名为linklistUse.cpp）。4、基本实验的参考程序1．文件linklistDef.h是线性表的单链表存储结构的定义structLNode{ElemTypedata;struct

7、LNode*next;};typedefstructLNode*LinkList;/*另一种定义LinkList的方法*/2．文件linklistAlgo.h是单链表的基本算法描述/*以下的算法均是针对带表头结点的单链表*/StatusListInit_Link(LinkList&L){/*操作结果：构造一个空的线性表L*/L=(LinkList)malloc(sizeof(structLNode));/*产生头结点,并