数据结构实验二链表.doc

数据结构实验二
1、实验目的
熟练掌握线性表的链式存储结构定义及基本操作
理解循环链表和双链表的特点和基本运算

2、实验内容：
建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。
其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。
1．问题描述：
利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作：
初始化一个带表头结点的空链表;
创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。又分为逆位序(插在表头)输入n个元素的值和正位序(插在表尾)输入n个元素的值;
插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入），且保持结点的数据按原来的递增次序排列，形成有序链表。
删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部删除（值删除）;
输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点;
求前驱结点是根据给定结点的值，在单链表中搜索其当前结点的后继结点值为给定的值，将当前结点返回;
求后继结点是根据给定结点的值，在单链表中搜索其当前结点的值为给定的值，将后继结点返回;
两个有序链表的合并是分别将两个单链表的结点依次插入到第3个单链表中，继续保持结点有序;
编写主程序，实现对各不同的算法调用。
其它的操作算法描述略。

2．实现要求：
对链表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价。
“初始化算法”的操作结果：构造一个空的线性表L，产生头结点,并使L指向此头结点;
“建立链表算法”初始条件：空链存在;
操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的结果;
“链表（位置）插入算法”初始条件：已知单链表L存在;
操作结果：在带头结点的单链线性表L中第i个位置之前插入元素e;
“链表（位置）删除算法”初始条件：已知单链表L存在;
操作结果：在带头结点的单链线性表L中，删除第i个元素,并由e返回其值;
“输出算法”初始条件：链表L已存在;
操作结果：依次输出链表的各个结点的值;
“求前驱算法”初始条件:线性表L已存在;
操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱;
“求后继算法”初始条件:线性表L已存在;
操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继;
“两个有序链表的合并算法”初始条件:线性表单链线性表La和Lb的元素按值非递减排列;
操作结果:归并La和Lb得到新的单链表。

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

2．文件linklistAlgo.h是单链表的基本算法描述
/*以下的算法均是针对带表头结点的单链表*/
StatusListInit_Link(LinkList&L)
{/*操作结果：构造一个空的线性表L*/
L=(LinkLi