线性表的存储结构定义及基本操作
一、实验目的：
. 掌握线性表的逻辑特征
. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算 . 熟练掌握线性表的链式存储结构定义及基本操作 . 理解循环链表和双链表的特点和基本运算
. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力
二、实验内容：
（一）基本实验内容（顺序表）：
建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、 查找元素、判线性表是否为空；
1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作： . 创建一个新的顺序表，实现动态空间分配的初始化；
. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序 顺序表；
. 根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删 除指定值的所有结点(值删除)；
. 利用最少的空间实现顺序表元素的逆转； . 实现顺序表的各个元素的输出；
. 彻底销毁顺序线性表，回收所分配的空间； . 对顺序线性表的所有元素删除，置为空表； . 返回其数据元素个数；
. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对 查找结果进行返回；
. 按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回； . 判断顺序表中是否有元素存在，对判断结果进行返回； . 编写主程序，实现对各不同的算法调用。 2．实现要求：
对顺序表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要 从时间复杂度和空间复杂度上进行评价；
. “初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进行动态管理，实现动态分配、 回收和增加存储空间；
. “位置插入算法” 的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ； 操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；
. “位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ； 操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ； . “逆转算法”的初始条件：顺序线性表L 已存在；
操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序 表的元素进行交换；
1
线性表的存储结构定义及基本操作
. “输出算法”的初始条件：顺序线性表L 已存在； 操作结果：依次对L 的每个数据元素进行输出； . “销毁算法”初始条件：顺序线性表L 已存在； 操作结果：销毁顺序线性表L；
. “置空表算法”初始条件：顺序线性表L 已存在； 操作结果：将L 重置为空表；
. “求表长算法”初始条件：顺序线性表L 已存在； 操作结果：返回L 中数据元素个数；
. “按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L) 操作结果：返回L 中第i 个数据元素的值
. “按值查找算法”初始条件：顺序线性表L 已存在，元素值为e； 操作结果：返回L 中数据元素值为e 的元素位置； . “判表空算法”初始条件：顺序线性表L 已存在； 操作结果：若L 为空表，则返回TRUE，否则返回FALSE；
分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
(二）基本实验内容（链表）：
建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。
其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。 1． 问题描述：
利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作： . 初始化一个带表头结点的空链表；
. 创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接 的关系。又分为逆位序(插在表头)输入n 个元素的值和正位序(插在表尾)输入n 个元素的值；
. 插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入）， 且保持结点的数据按原来的递增次序排列，形成有序链表。
. 删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部 删除（值删除）；
. 输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点； . 编写主程序，实现对各不同的算法调用。 其它的操作算法描述略。 2．实现要求：
对链表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，还要针对每个算法的 实现从时间复杂度和空间复杂度上进行评价。
. “初始化算法”的操作结果：构造一个空的线性表L，产生头结点,并使L 指向此头结点； . “建立链表算法” 初始条件：空链存在；
操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的结果； . “链表（位置）插入算法”初始条件：已知单链表L 存在；
操作结果：在带头结点的单链线性表L 中第i 个位置之前插入元素e； . “链表（位置）删除算法”初始条件：已知单链表L 存在；
操作结果：在带头结点的单链线性表L 中，删除第i 个元素,并由e 返回其值； . “输出算法”初始条件：链表L 已存在； 操作结果：依次输出链表的各个结点的值；
2
线性表的存储结构定义及基本操作
（三）扩展实验内容（顺序表）
查前驱元素、查后继元素、顺序表合并等. 1．问题描述：
. 根据给定元素的值，求出前驱元素； . 根据给定元素的值，求出后继元素；
. 对已建好的两个顺序表进行合并操作，若原线性表中元素非递减有序排列,要求合并后的结果还是有序 (有序合并）；对于原顺序表中元素无序排列的合并只是完成A=A∪B（无序合并)，要求同样的数据元素只 出现一次。
. 修改主程序，实现对各不同的算法调用。 2．实现要求：
. “查前驱元素算法” 初始条件：顺序线性表L 已存在；
操作结果：若数据元素存在且不是第一个，则返回前驱，否则操作失败； . “查后继元素算法” 初始条件：顺序线性表L 已存在；
操作结果：若数据元素存在且不是最后一个，则返回后继，否则操作失败； . “无序合并算法”的初始条件：已知线性表La 和Lb；
操作结果：将所有在线性表Lb 中但不在La 中的数据元素插入到La 中；
. “有序合并算法”的初始条件： 已知线性表La 和Lb 中的数据元素按值非递减排列； 操作结果： 归并La 和Lb 得到新的线性表Lc,Lc 的数据元素也按值非递减排列； （四）扩展实验内容（链表） 1．问题描述：
. 求前驱结点是根据给定结点的值，在单链表中搜索其当前结点的后继结点值为给定的值，将当前结点返 回；
. 求后继结点是根据给定结点的值，在单链表中搜索其当前结点的值为给定的值，将后继结点返回； . 两个有序链表的合并是分别将两个单链表的结点依次插入到第3 个单链表中，继续保持结点有序； 2．实现要求：
. “求前驱算法”初始条件: 线性表L 已存在；
操作结果: 若cur_e 是L 的数据元素,且不是第一个,则用pre_e 返回它的前驱； . “求后继算法”初始条件: 线性表L 已存在；
操作结果: 若cur_e 是L 的数据元素,且不是最后一个,则用next_e 返回它的后继；
. “两个有序链表的合并算法”初始条件: 线性表单链线性表La 和Lb 的元素按值非递减排列； 操作结果:归并La 和Lb 得到新的单链表。
线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）
(1) 文件1： pubuse. h 是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都涉及到此文 件。
#include
#include
#include
#include
3
线性表的存储结构定义及基本操作
#include
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math. h 中已定义OVERFLOW 的值为3,故去掉此行*/ typedef int Status； /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ typedef int Boolean； /* Boolean 是布尔类型,其值是TRUE 或FALSE */
(2) 文件2：seqlistDef. h 进行线性表的动态分配顺序存储结构的表示
#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量*/ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量*/ typedef struct {
ElemType *elem； /* 存储空间基址*/ int length； /* 当前长度*/
int listsize； /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList；
(3)文件3：seqlistAlgo. h 进行线性表顺序存储结构的基本实验算法定义 Status ListInit_Sq(SqList &L) /* 算法2. 3 */ { /* 操作结果：构造一个空的顺序线性表*/
L. elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))； if(!L. elem)
exit(OVERFLOW)； /* 存储分配失败*/ L. length=0； /* 空表长度为0 */
L. listsize=LIST_INIT_SIZE； /* 初始存储容量*/ return OK； }
Status ListInsert_Sq(SqList &L,int i,ElemType e) /* 算法2. 4 */ { /* 初始条件：顺序线性表L 已存在，1≤i≤ListLength(L)+1 */
/* 操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1 */ ElemType *newbase,*q,*p；
if(i<1||i>L. length+1) /* i 值不合法*/ return ERROR；
if(L. length>=L. listsize) /* 当前存储空间已满,增加分配*/ {
newbase=(ElemType *)realloc(L. elem,(L. listsize+LISTINCREMENT)*sizeof(ElemType))；if(!newbase)
exit(OVERFLOW)； /* 存储分配失败*/ L. elem=newbase； /* 新基址*/
L. listsize+=LISTINCREMENT； /* 增加存储容量*/ }
q=L. elem+i-1； /* q 为插入位置*/
4
线性表的存储结构定义及基本操作
for(p=L. elem+L. length-1；p>=q；--p) /* 插入位置及之后的元素右移*/
*(p+1)=*p；
*q=e； /* 插入e */
++L. length； /* 表长增1 */ return OK； }
Status ListDelete_Sq(SqList &L,int i,ElemType *e) /* 算法2. 5 */ { /* 初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 */ ElemType *p,*q；
if(i<1||i>L. length) /* i 值不合法*/ return ERROR；
p=L. elem+i-1； /* p 为被删除元素的位置*/ *e=*p； /* 被删除元素的值赋给e */
q=L. elem+L. length-1； /* 表尾元素的位置*/
for(++p；p<=q；++p) /* 被删除元素之后的元素左移*/
*(p-1)=*p；
L. length--； /* 表长减1 */ return OK； }
Status ListReverse_Sq(SqList &L) { /* 初始条件：顺序线性表L 已存在*/
/* 操作结果：依次对L 的数据元素成对交换*/ ElemType t； int i；
for(i=0；i {t=L. elem[i]； L. elem[i]= L. elem[L. length-i-1]； L. elem[L. length-i-1]=t； } printf(\； return OK； } Status ListPrint_Sq(SqList L) { /* 初始条件：顺序线性表L 已存在*/ /* 操作结果：依次对L 的数据元素输出*/ int i； printf(\； for(i=0；i (4)文件4：seqlistUse. cpp 进行线性表顺序存储结构的基本算法验证 #include\实现通用常量的定义，常用系统函数的声明*/ typedef int ElemType； /*实现一组整数的操作,将int 型特定义为通用的ElemType 类型名*/ #include\采用线性表的动态分配顺序存储结构定义*/ #include\采用顺序表的基本算法定义*/ 5 线性表的存储结构定义及基本操作 void main() { SqList L； Status i； int j； ElemType t； /* 首先一定要初始化顺序表*/ i=ListInit_Sq(L)；if(i==1) /* 创建空表L 成功*/ for(j=1；j<=5；j++) /* 在表L 中插入5 个元素，每个元素的值分别为2，4，6，8，10 */ i=ListInsert_Sq(L,j,2*j)； ListPrint_Sq(L)； /*检验一下插入的结果，输出表L 的内容*/ ListInsert_Sq(L,2,20)；/* 随机指定插入点位置，假设在第二个元素前插入新的元素，其值为20 */ ListDelete_Sq(L,4,&t)；/* 随机指定删除点位置，假设对第四个元素进行删除*/ printf(\；/* 检验一下删除点元素的值*/ ListPrint_Sq(L)；/* 检验一下插入和删除后的结果，输出表La 的内容*/ ListReverse_Sq(L)；/* 将顺序表La 的所有元素进行逆序*/ ListPrint_Sq(L)；/* 检验一下逆序的结果，输出表L 的内容*/ } 三、实验结果 四、实验分析 1) for(p=L. elem+L. length-1；p>=q；--p) /* 插入位置及之后的元素右移*/ 在此处应该填上代码：*(p+1)=*p； 2) for(++p；p<=q；++p) /* 被删除元素之后的元素左移*/ 在此处应该填上代码：*(p-1)=*p； 五、实验总结 此次试验比较难，考察了线性表的逻辑特征，线性表顺序存储结构的特点，线性表的链式存储结构定义 6 线性表的存储结构定义及基本操作 及基本操作，循环链表和双链表的特点和基本运算。 通过此次线性表的存储结构实验，让我明白了线性表的逻辑特征、线性表顺序存储结构的特点，顺序表的基本运算、线性表的链式存储结构定义及基本操作、理解循环链表和双链表的特点和基本运算、加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力。 7
