线性表的存储结构定义及基本操作(实验报告)2022600724何俊林.

线性表的存储构造定义及根本操作(实验报告)-2022600724-何俊林. - 姓名：何俊林 学号：2022600724 11软件工程1 线性表的存储构造定义及根本操作实验报告 一、 实验目的： . 掌握线性表的逻辑特征 . 掌握线性表顺序存储构造的特点,纯熟掌握顺序表的根本运算 . 纯熟掌握线性表的链式存储构造定义及根本操作 . 理解循环链表和双链表的特点和根本运算 . 加深对顺序存储数据构造的理解和链式存储数据构造的理解,逐步培养解决实际问题的编程才能 二、 实验内容 (一) 根本实验内容(顺序表)： 建立顺序表,完成顺序表的根本操作：初始化、插入、删除、逆转、输出、销毁,置空表、求表长、查找元素、判线性表是否为空; 1. 问题描绘： . 利用顺序表,设计一组输入数据(假定为一组整数),可以对顺序表进展如下操作： . 创立一个新的顺序表,实现动态空间分配的初始化; . 根据顺序表结点的位置插入一个新结点(位置插入),也可以根据给定的值进展插入(值插入),形成有序顺序表; . 根据顺序表结点的位置删除一个结点(位置删除),也可以根据给定的值删除对应的第一个结点,或者删除指定值的所有结点(值删除); . 利用最少的空间实现顺序表元素的逆转; . 实现顺序表的各个元素的输出; . 彻底销毁顺序线性表,回收所分配的空间; . 对顺序线性表的所有元素删除,置为空表; . 返回其数据元素个数; . 按序号查找,根据顺序表的特点,可以随机存取,直接可以定位于第 i 个结点,查找该元素的值,对查找结果进展返回; . 按值查找,根据给定数据元素的值,只能顺序比拟,查找该元素的位置,对查找结果进展返回; . 判断顺序表中是否有元素存在,对判断结果进展返回; . 编写主程序,实现对各不同的算法调用。 2. 实现要求 对顺序表的各项操作一定要编写成为C(C+)语言函数,组合成模块化的形式,每个算法的实现要从时间复杂度和空间复杂度上进展评价; . “初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进展动态管理,实现动态分配、回收和增加存储空间; . “位置插入算法”的初始条件：顺序线性表L已存在,给定的元素位置为i,且1iListLength(L)+1;操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1; . “位置删除算法”的初始条件：顺序线性表L已存在,1iListLength(L); 操作结果：删除L的第i个数据元素,并用e返回其值,L的长度减1; . “逆转算法”的初始条件：顺序线性表L已存在; . 操作结果：依次对L的每个数据元素进展交换,为了使用最少的额外空间,对顺序表的元素进展交换; . “输出算法”的初始条件：顺序线性表L已存在;操作结果：依次对L的每个数据元素进展输出; . “销毁算法”初始条件：顺序线性表L已存在;操作结果：销毁顺序线性表 L; . “置空表算法”初始条件：顺序线性表L已存在;操作结果：将L重置为空表; . “求表长算法”初始条件：顺序线性表L已存在; 操作结果：返回L中数据元素个数; . “按序号查找算法”初始条件：顺序线性表 L 已存在,元素位置为 i,且 1iListLength(L) 操作结果：返回 L 中第 i 个数据元素的值 . “按值查找算法”初始条件：顺序线性表 L 已存在,元素值为 e; 操作结果：返回 L 中数据元素值为 e 的元素位置; . “判表空算法”初始条件：顺序线性表 L 已存在; . 操作结果：假设 L 为空表,那么返回 TRUE,否那么返回 FALSE; 分析p ：修改输入数据,预期输出并验证输出的结果,加深对有关算法的理解。 (二) 根本实验内容(单链表)： 建立单链表,完成链表(带表头结点)的根本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。 其他根本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。 1. 问题描绘： 利用线性表的链式存储构造,设计一组输入数据(假定为一组整数),可以对单链表进展如下操作： . 初始化一个带表头结点的空链表; . 创立一个单链表是从无到有地建立起一个链表,即一个一个地输入各结点数据,并建立起前后互相链接的关系。又分为逆位序(插在表头)输入 n 个元素的值和正位序(插在表尾)输入 n 个元素的值; . 插入结点可以根据给定位置进展插入(位置插入),也可以根据结点的值插入到的链表中(值插入),且保持结点的数据按原来的递增次序排列,形成有序链表。 . 删除结点可以根据给定位置进展删除(位置删除),也可以把链表中查找结点的值为搜索对象的结点全部删除(值删除); . 输出单链表的内容是将链表中各结点的数据依次显示,直到链表尾结点; . 编写主程序,实现对各不同的算法调用。其它的操作算法描绘略。 2. 实现要求： 对链表的各项操作一定要编写成为 C(C+) 语言函数,组合成模块化的形式,还要针对每个算法的 实现从时间复杂度和空间复杂度上进展评价。 . “初始化算法”的操作结果：构造一个空的线性表 L,产生头结点,并使 L 指向此头结点; . “建立链表算法”初始条件：空链存在; 操作结果：选择逆位序或正位序的方法,建立一个单链表,并且返回完成的结果; . “链表(位置)插入算法”初始条件：单链表 L 存在; 操作结果：在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e; . “链表(位置)删除算法”初始条件：单链表 L 存在; . 操作结果：在带头结点的单链线性表 L 中,删除第 i 个元素,并由 e 返回其值; . “输出算法”初始条件：链表 L 已存在;操作结果：依次输出链表的各个结点的值; (三) 扩展实验内容(顺序表) 查前驱元素、查后继元素、顺序表合并等. 1. 问题描绘： . 根据给定元素的值,求出前驱元素; . 根据给定元素的值,求出后继元素; . 对已建好的两个顺序表进展合并操作,假设原线性表中元素非递减有序排列,要求合并后的结果还是有序(有序合并);对于原顺序表中元素无序排列的合并只是完成 A=AB (无序合并),要求同样的数据元素只出现一次。 . 修改主程序,实现对各不同的算法调用。 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 得到新的单链表。 三、 实验环境和实验步骤 实验环境：利用CodeBlocks10.05集成开发环境进展本实验的操作。 实验步骤顺序表的定义与操作： 1.启动CodeBlocks10.5; 2.按“Create a new project”, 通过”file”, 按“C/C+ source”,选择”c”,然后GO.储存文件“D:c语言顺序表.c “， 3.进展编代码。 4、编好之后，搞ctrl+shift+F9进展编译。然后按ctrl+F10. 5.假如编译出问题，然后进展调试。 实验步骤链表的定义与操作： 1.启动CodeBlocks10.5; 第 9 页 共 9 页