《算法与数据结构》实验指导书实验一：线性表的存储结构定义及基本操作（必做：基本2学时，扩展4学时）一、实验目的：掌握线性表的逻辑特征，掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算：熟练掌握线性表的链式存储结构定义及基本操作·理解循环链表和双链表的特点和基本运算，加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁，置空表、求表长、查找元素、判线性表是否为空；1.问题描述：利用顺序表，设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：创建一个新的顺序表，实现动态空间分配的初始化；：根据顺序表结点的位置插入一个新结点（位置插入），也可以根据给定的值进行插入（值插入），形成有序顺序表；根据顺序表结点的位置删除一个结点（位置删除），也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点（值删除）：：利用最少的空间实现顺序表元素的逆转；：实现顺序表的各个元素的输出；：彻底销毁顺序线性表，回收所分配的空间；：对顺序线性表的所有元素删除，置为空表；：返回其数据元素个数；：按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i个结点，查找该元素的值，对查找结果进行返回：：按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；：判断顺序表中是否有元素存在，对判断结果进行返回：。编写主程序，实现对各不同的算法调用。6
《算法与数据结构》实验指导书 6 实验一：线性表的存储结构定义及基本操作（必做：基本 2 学时，扩展 4 学时） 一、实验目的： 一、实验目的： 一、实验目的： 一、实验目的： . 掌握线性表的逻辑特征 . 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算 . 熟练掌握线性表的链式存储结构定义及基本操作 . 理解循环链表和双链表的特点和基本运算 . 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力 二、实验内容： 二、实验内容： 二、实验内容： 二、实验内容： （一）基本实验内容（顺序表）： 建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、 查找元素、判线性表是否为空； 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的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；·“输出算法”的初始条件：顺序线性表L已存在操作结果：依次对L的每个数据元素进行输出：：“销毁算法”初始条件：顺序线性表L已存在；操作结果：销毁顺序线性表L；：“置空表算法”初始条件：顺序线性表L已存在：操作结果：将L重置为空表；：“求表长算法”初始条件：顺序线性表L已存在；操作结果：返回L中数据元素个数；：“按序号查找算法”初始条件：顺序线性表L已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L中第i个数据元素的值：“按值查找算法”初始条件：顺序线性表L已存在，元素值为e；操作结果：返回L中数据元素值为e的元素位置“判表空算法”初始条件：顺序线性表L已存在操作结果：若L为空表，则返回TRUE，否则返回FALSE分析：修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。（二）基本实验内容（链表）：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出、求前驱、7
《算法与数据结构》实验指导书 7 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 的每个数据元素进行交换，为了使用最少的额外空间，对顺序 表的元素进行交换； . “输出算法”的初始条件：顺序线性表 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已存在；操作结果：依次输出链表的各个结点的值：（三）扩展实验内容（顺序表）查前驱元素、查后继元素、顺序表合并等1.问题描述：：根据给定元素的值，求出前驱元素；：根据给定元素的值，求出后继元素；80
《算法与数据结构》实验指导书 8 求后继、两个有序链表的合并操作。 其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。 1． 问题描述： 利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作： . 初始化一个带表头结点的空链表； . 创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接 的关系。又分为逆位序(插在表头)输入 n 个元素的值和正位序(插在表尾)输入 n 个元素的值； . 插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入）， 且保持结点的数据按原来的递增次序排列，形成有序链表。 . 删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部 删除（值删除）； . 输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点； . 编写主程序，实现对各不同的算法调用。 其它的操作算法描述略。 2．实现要求： 对链表的各项操作一定要编写成为 C（C++）语言函数，组合成模块化的形式，还要针对每个算法的 实现从时间复杂度和空间复杂度上进行评价。 . “初始化算法”的操作结果：构造一个空的线性表 L，产生头结点,并使 L 指向此头结点； . “建立链表算法” 初始条件：空链存在； 操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的结果； . “链表（位置）插入算法”初始条件：已知单链表 L 存在； 操作结果：在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e； . “链表（位置）删除算法”初始条件：已知单链表 L 存在； 操作结果：在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值； . “输出算法”初始条件：链表 L 已存在； 操作结果：依次输出链表的各个结点的值； （三）扩展实验内容（顺序表） 查前驱元素、查后继元素、顺序表合并等. 1．问题描述： . 根据给定元素的值，求出前驱元素； . 根据给定元素的值，求出后继元素；
《算法与数据结构》实验指导书：对已建好的两个顺序表进行合并操作，若原线性表中元素非递减有序排列，要求合并后的结果还是有序（有序合并）：对于原顺序表中元素无序排列的合并只是完成A=AUB（无序合并），要求同样的数据元素只出现一次。，修改主程序，实现对各不同的算法调用。2.实现要求：：“查前驱元素算法”初始条件：顺序线性表L已存在；操作结果：若数据元素存在且不是第一个，则返回前驱，否则操作失败；：“查后继元素算法”初始条件：顺序线性表L已存在：操作结果：若数据元素存在且不是最后一个，则返回后继，否则操作失败；：“无序合并算法”的初始条件：已知线性表La和Lb；操作结果：将所有在线性表Lb中但不在La中的数据元素插入到La中：：“有序合并算法”的初始条件：已知线性表La和Lb中的数据元素按值非递减排列；操作结果：归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列；（四）扩展实验内容（链表）1.问题描述：。求前驱结点是根据给定结点的值，在单链表中搜索其当前结点的后继结点值为给定的值，将当前结点返回;：求后继结点是根据给定结点的值，在单链表中搜索其当前结点的值为给定的值，将后继结点返回；两个有序链表的合并是分别将两个单链表的结点依次插入到第3个单链表中，继续保持结点有序；2.实现要求：：“求前驱算法”初始条件：线性表L已存在；操作结果：若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱；、“求后继算法”初始条件：线性表L已存在；操作结果：若cure是L的数据元素,且不是最后一个，则用nexte返回它的后继：：“两个有序链表的合并算法”初始条件：线性表单链线性表La和Lb的元素按值非递减排列操作结果：归并La和Lb得到新的单链表。三、实验指导一个简单程序通常主要由三部分构成：1、常量定义（#define），类型重定义（typedef）及函数原型（#include）声明：还有针对每一种数据结9
《算法与数据结构》实验指导书 9 . 对已建好的两个顺序表进行合并操作，若原线性表中元素非递减有序排列,要求合并后的结果还是有序 (有序合并）；对于原顺序表中元素无序排列的合并只是完成 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、常量定义（#define），类型重定义(typedef)及函数原型(#include)声明；还有针对每一种数据结
《算法与数据结构》实验指导书构的类型定义，由于本实验是要求实现对线性表的顺序存储和链式存储两种存储结构的定义，因此不同的物理存储结构的定义和其基本操作最好是以独立的文件存在，因此本实验将顺序表和链表可分解为两个不同的实验部分。2、算法函数，对于顺序表，每一个函数具有独立的功能，组合成为模块的形式，如ListInit_Sq、ListInsert_Sq、ListDelete_Sq、ListReverse_Sq、ListPrint_Sq等；对于链表，每一个函数具有独立的功能，组合成为模块的形式，如ListInit_Link、ListInsert_Link、ListDelete_Link、ListTraverse_Link，PriorElem_Link，NextElem_Link，GetElem_Link，MergeList_Link等3、主函数（main）。【说明1】一一顺序表的定义与操作1.可以将这三部分组合在一个文件中，也可以按照项目的方式（多个不同的文件组合在一起，共同完成一个功能）进行组织（本课程的实验强烈推荐这种形式），如将本课程后续所有算法几乎都要使用的常量定义（#define）和系统函数原型定义(#include)声明组合成一个文件，存储为一个头文件（名为pubuse回)，只需建立一次，以后凡涉及到相关的内容，只需在你的文件的前面加上一条#include“pubuse.h”即可，无需重复输入。2．对于类型定义，由于每一种数据结构的定义都不一样，因此要进行专门的类型定义，也可以将数据结构的定义组合成为一个文件，存储为一个头文件（如线性表的顺序存储结构定义取名为seqlistDef.h）只需建立一次，以后凡涉及到关于顺序表操作的相关内容，一定要在你的文件的前面加上一条#include“seqlistDef.h”即可，无需重复进行顺序存储结构的定义。3．关于实验内容要完成的操作，一般都以独立的算法出现，关于某类数据结构的各种不同算法函数组合在一个文件之中，存储为一个头文件（如取名为seqlistAlgo.h），以后凡涉及到要使用本文件中的顺序表算法，一定要在你的文件的前面加上一条#include“seqlistAlgo.h”即可，无需重复定义类似的算法，就象使用系统函数一样，只需进行函数原型的声明即可。4.还应包含一个main函数，作为整个程序的执行入口处，定义测试的数据，完成各种算法的调用执行，对算法的执行过程和结果进行判断和输出控制，存储为一个源文件（如取名为seqlistUse.cpp）。5.为了对实际问题更加通用和适应，在算法中使用的数据类型为ElemType，为了与实际数据类型一致，一般要将ElemType用typedef重定义：如实际问题中顺序表的每个元素是整型，则使用typedefintElemType；定义语句；如实际问题中顺序表的每个元素是单精度实数的话，使用typedeffloatElemType；定义语句。【说明2】一一链表的定义与操作1.根据一个完整的C语言组成，将实验内容组合成如上所述的三个组成部分，功能清晰明了，其常10
《算法与数据结构》实验指导书 10 构的类型定义，由于本实验是要求实现对线性表的顺序存储和链式存储两种存储结构的定义，因此不同的 物理存储结构的定义和其基本操作最好是以独立的文件存在，因此本实验将顺序表和链表可分解为两个不 同的实验部分。 2、算法函数，对于顺序表，每一个函数具有独立的功能，组合成为模块的形式，如 ListInit_Sq、 ListInsert_Sq、ListDelete_Sq、 ListReverse_Sq、ListPrint_Sq 等；对于链表，每一个函数具有 独立的功能，组合成为模块的形式，如 ListInit_Link、ListInsert_Link、ListDelete_Link、 ListTraverse_Link、PriorElem_Link、NextElem_Link、GetElem_Link、MergeList_Link 等； 3、主函数（main）。 【说明 1】――顺序表的定义与操作 1．可以将这三部分组合在一个文件中，也可以按照项目的方式（多个不同的文件组合在一起，共同 完成一个功能）进行组织（本课程的实验强烈推荐这种形式 ），如将本课程后续所有算法几乎都要使用的 常量定义（#define）和系统函数原型定义(#include)声明组合成一个文件，存储为一个头文件（取名为 pubuse. pubuse. pubuse. pubuse. h），只需建立一次，以后凡涉及到相关的内容，只需在你的文件的前面加上一条#include “pubuse. h” 即可， 无需重复输入。 2．对于类型定义，由于每一种数据结构的定义都不一样，因此要进行专门的类型定义，也可以将数 据结构的定义组合成为一个文件，存储为一个头文件（如线性表的顺序存储结构定义取名为 seqlistDef. h）， 只需建立一次，以后凡涉及到关于顺序表操作的相关内容，一定要在你的文件的前面加上一条#include “seqlistDef. h” 即可，无需重复进行顺序存储结构的定义。 3．关于实验内容要完成的操作，一般都以独立的算法出现，关于某类数据结构的各种不同算法函数 组合在一个文件之中，存储为一个头文件（如取名为 seqlistAlgo. h），以后凡涉及到要使用本文件中的顺序 表算法，一定要在你的文件的前面加上一条#include “seqlistAlgo. h” 即可，无需重复定义类似的算法，就 象使用系统函数一样，只需进行函数原型的声明即可。 4．还应包含一个 main 函数，作为整个程序的执行入口处，定义测试的数据，完成各种算法的调用执 行，对算法的执行过程和结果进行判断和输出控制，存储为一个源文件（如取名为 seqlistUse. cpp）。 5．为了对实际问题更加通用和适应，在算法中使用的数据类型为 ElemType，为了与实际数据类型一 致，一般要将 ElemType 用 typedef 重定义：如实际问题中顺序表的每个元素是整型，则使用 typedef int ElemType；定义语句；如实际问题中顺序表的每个元素是单精度实数的话，使用 typedef float ElemType； 定义语句。 【说明 2】――链表的定义与操作 1．根据一个完整的 C 语言组成，将实验内容组合成如上所述的三个组成部分，功能清晰明了，其常