一、实验目的:
. 掌握线性表的逻辑特征
. 掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算
. 熟练掌握线性表的链式存储结构定义及基本操作
. 理解循环链表和双链表的特点和基本运算
. 加深对顺序存储数据结构的理解和链式存储数据结构的理解,逐步培养解决实际问题的编程能力
二、实验内容:
(一)基本实验内容(顺序表):
建立顺序表,完成顺序表的基本操作:初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、
查找元素、判线性表是否为空;
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 的每个数据元素进行交换,为了使用最少的额外空间,对顺序
表的元素进行交换;