资源描述：
《线性表的存储结构定义及基本操作(实验报告)-2011600724-何俊林》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、姓名：何俊林学号：201160072411软件工程1线性表的存储结构定义及基本操作（实验报告）一、实验目的：.掌握线性表的逻辑特征.掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算.熟练掌握线性表的链式存储结构定义及基本操作.理解循环链表和双链表的特点和基本运算.加深对顺序存储数据结构的理解和链式存储数据结构的理解,逐步培养解决实际问题的编程能力二、实验内容(一)基本实验内容(顺序表)：建立顺序表,完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁,置空表、求表长、查找元素、判线性表是否为空;1.问题描述：.利用顺序表,设计一组输入数据
2、(假定为一组整数),能够对顺序表进行如下操作：.创建一个新的顺序表,实现动态空间分配的初始化;.根据顺序表结点的位置插入一个新结点(位置插入),也可以根据给定的值进行插入(值插入),形成有序顺序表;.根据顺序表结点的位置删除一个结点(位置删除),也可以根据给定的值删除对应的第一个结点,或者删除指定值的所有结点(值删除);.利用最少的空间实现顺序表元素的逆转;.实现顺序表的各个元素的输出;.彻底销毁顺序线性表,回收所分配的空间;.对顺序线性表的所有元素删除,置为空表;.返回其数据元素个数;.按序号查找,根据顺序表的特点,可以随机存取,直接可以定位于第i
3、个结点,查找该元素的值,对查找结果进行返回;.按值查找,根据给定数据元素的值,只能顺序比较,查找该元素的位置,对查找结果进行返回;.判断顺序表中是否有元素存在,对判断结果进行返回;.编写主程序,实现对各不同的算法调用。2.实现要求对顺序表的各项操作一定要编写成为C(C++)语言函数,组合成模块化的形式,每个算法的实现要从时间复杂度和空间复杂度上进行评价;.“初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进行动态管理,实现动态分配、回收和增加存储空间;.“位置插入算法”的初始条件：顺序线性表L已存在,给定的元素位置为i,且1≤i≤Lis
4、tLength(L)+1;操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1;.“位置删除算法”的初始条件：顺序线性表L已存在,1≤i≤ListLength(L);操作结果：删除L的第i个数据元素,并用e返回其值,L的长度减1;.“逆转算法”的初始条件：顺序线性表L已存在;.操作结果：依次对L的每个数据元素进行交换,为了使用最少的额外空间,对顺序表的元素进行交换;.“输出算法”的初始条件：顺序线性表L已存在;操作结果：依次对L的每个数据元素进行输出;.“销毁算法”初始条件：顺序线性表L已存在;操作结果：销毁顺序线性表L;.“置空表算法”初
5、始条件：顺序线性表L已存在;操作结果：将L重置为空表;.“求表长算法”初始条件：顺序线性表L已存在;操作结果：返回L中数据元素个数;.“按序号查找算法”初始条件：顺序线性表L已存在,元素位置为i,且1≤i≤ListLength(L)操作结果：返回L中第i个数据元素的值.“按值查找算法”初始条件：顺序线性表L已存在,元素值为e;操作结果：返回L中数据元素值为e的元素位置;.“判表空算法”初始条件：顺序线性表L已存在;.操作结果：若L为空表,则返回TRUE,否则返回FALSE;分析：修改输入数据,预期输出并验证输出的结果,加深对有关算法的理解。(二)基本
6、实验内容(单链表)：建立单链表,完成链表(带表头结点)的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。1.问题描述：利用线性表的链式存储结构,设计一组输入数据(假定为一组整数),能够对单链表进行如下操作：.初始化一个带表头结点的空链表;.创建一个单链表是从无到有地建立起一个链表,即一个一个地输入各结点数据,并建立起前后相互链接的关系。又分为逆位序(插在表头)输入n个元素的值和正位序(插在表尾)输入n个元素的值;.插入结点可以根
7、据给定位置进行插入(位置插入),也可以根据结点的值插入到已知的链表中(值插入),且保持结点的数据按原来的递增次序排列,形成有序链表。.删除结点可以根据给定位置进行删除(位置删除),也可以把链表中查找结点的值为搜索对象的结点全部删除(值删除);.输出单链表的内容是将链表中各结点的数据依次显示,直到链表尾结点;.编写主程序,实现对各不同的算法调用。其它的操作算法描述略。2.实现要求：对链表的各项操作一定要编写成为C(C++)语言函数,组合成模块化的形式,还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价。.“初始化算法”的操作结果：构造一个空的线性
8、表L,产生头结点,并使L指向此头结点;.“建立链表算法”初始条件：空链存在;操作结果：选择逆位序或正位序的方
