线性表 实验报告.docx

选题1：（易）实现顺序表各种基本运算的算法 参考实验指导书“实验题 1：实现顺序表各种基本运算的算法实现”。 选题2：（易）实现单链表各种基本运算的算法 参考实验指导书“实验题 2：实现单链表各种基本运算的算法实现”。 选题3：（易）编写算法实现二个有序的线性表的合并问题（存储结构可选：顺序表/单链表）。 参考课件“chap002线性表.ppt”相关例题。 选题4：（难）运用单向循环链表实现约瑟夫环的问题。 参考实验指导书“实验题 4：运用单向循环链表实现约瑟夫环的问题”。 选题5：（易）将元素X插入到链表中合适的位置。 完成习题集中的算法并编程实现：2.11。参考课件“chap002线性表习题讲解.ppt”2.11。 带头结点的单链表L，其中有n 个元素非递减有序排列，将元素X插入到链表中合适的位置。 提示：先创建链表，其中的元素值可由随机函数按阶段生成或键盘输入，先打印初始链表数据，然后插入新结点，再打印结果链表。 插入前： 插入后： 选题6：（易）删除表中所有大于mink且小于maxk的元素。 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 参考实验指导书“实验题 5：删除有序单链表中所有大于 mink 且小于 maxk的元素”。 选题7：（中等）删除单链表中多余元素。 完成习题集中的算法并编程实现：2.20。参考课件“chap002线性表习题讲解.ppt”2.20。 已知单链表中的元素有序，写一算法，删除表中所有值相同的多余元素（使操作后线性表中的元素值均不相同），同时释放被删结点空间。 选题8：（易）实现单链表的就地逆置。 完成习题集中的算法并编程实现：2.22。参考课件“chap002线性表习题讲解.ppt”2.22。 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。 选题9：（难）单链表拆分。 将带头结点的单链表LA中分拆成LB和LC两条单链表，LA中的data域为奇数的节点依次进入LB，而为偶数的节点进入LC。 参考课件“chap002线性表习题讲解.ppt”第35页例题。 线性表是数据结构中的一种基础结构，它是由n（n>=0）个相同类型元素构成的有限序列。本实验报告涉及线性表的各种操作，包括顺序表和单链表的实现，以及相关的算法设计与分析。以下是这些操作的详细说明： 1. **顺序表**： - **实现基本运算**：顺序表是用数组来存储线性表的数据结构，支持的基本运算包括初始化、插入、删除、查找等。例如，`InitList_Sq()`用于创建空的顺序表，`ListEmpty()`检查表是否为空，`ListLength()`返回表的长度，`GetElem()`获取指定位置的元素，`LocateElem()`定位元素，`ListInsert()`在指定位置插入元素，`ListDelete()`删除指定位置元素，`PrintList()`打印表，以及`DestroyList()`销毁表。 2. **单链表**： - **实现基本运算**：单链表用指针链接相邻元素，同样支持类似顺序表的基本操作。例如，创建和初始化链表，插入元素，删除元素，查找元素，打印链表，以及销毁链表。此外，还需要考虑非递减有序的链表，如在选题5中，需要将元素X插入到已排序的链表中适当的位置。 3. **有序线性表的合并**： - **合并算法**：选题3中提到，可以使用顺序表或单链表存储的两个有序线性表进行合并，一般采用双指针法，从两个表的头开始比较，较小的元素进入新表，直到其中一个表遍历完，再将另一个表剩余部分追加到新表尾部。 4. **约瑟夫环问题**： - **循环链表的应用**：约瑟夫环问题是一种著名的算法问题，选题4中要求用单向循环链表实现。这个问题涉及到从一个循环链表中按照特定规则（例如，每隔一定数量的节点删除一个节点）删除节点，直至链表只剩下一个节点。 5. **元素插入**： - **插入策略**：选题5要求在非递减有序的单链表中插入元素X，需要找到正确的位置以保持顺序。这可能涉及到遍历链表，找到第一个大于X的元素，然后在前一个元素后插入。 6. **删除指定范围元素**： - **高效删除**：选题6中要删除所有大于mink且小于maxk的元素。由于链表已排序，可以一次遍历完成删除操作，时间复杂度为O(n)，其中n为链表长度。 7. **删除重复元素**： - **去重操作**：选题7要求删除所有相同值的元素，保持线性表中的元素唯一。这可以通过遍历链表，比较相邻元素，当发现重复时删除前一个元素实现。 8. **链表的就地逆置**： - **逆置算法**：选题8的就地逆置操作不改变链表的原始存储空间，通常通过交换相邻节点的next指针来实现，整个过程可以在O(n)时间内完成。 9. **链表拆分**： - **按条件拆分**：选题9中，根据data域的奇偶性将单链表拆分为两个链表。可以使用两个指针遍历链表，将奇数元素节点插入一个链表，偶数元素节点插入另一个链表。 通过这些实验，学生能够深入理解线性表的不同存储结构及其操作，提高对数据结构的理解和实际编程能力。