数据结构实验：有序列表与栈的实现与应用

### 数据结构实验：有序列表与栈的实现与应用 #### 1. 有序列表ADT测试 在有序列表抽象数据类型（ADT）的实现中，我们可以使用`test4.cpp`文件中的测试程序进行交互式测试。该程序支持以下命令： | 命令 | 操作 | | ---- | ---- | | +key | 插入（或更新）指定键的数据项 | |?key | 检索并输出指定键的数据项 | | - | 删除光标标记的数据项 | | @ | 显示光标标记的数据项 | | =key | 替换光标标记的数据项 | | N | 移动到下一个数据项 | | P | 移动到前一个数据项 | | < | 移动到列表开头 | | > | 移动到列表结尾 | | E | 报告列表是否为空 | | F | 报告列表是否已满 | | C | 清空列表 | | Q | 退出测试程序 | 测试步骤如下： 1. 准备有序列表ADT实现的测试计划，确保覆盖列表开头、中间和结尾的数据项操作。 2. 执行测试计划，若发现实现中的错误，进行修正并重新执行测试计划。 #### 2. 消息包重组程序 在通信中，消息通过分组交换网络传输时会被拆分为多个数据包。为了让接收端正确重组消息，每个数据包需要包含其在消息中的相对位置。例如，将消息 “A SHORT MESSAGE” 按每5个字符一组拆分，并为每个数据包添加位置编号，结果如下： ```plaintext 1 A SHO 2 RT ME 3 SSAGE ``` 实现步骤如下： 1. 创建一个程序，使用有序列表ADT辅助重组文本文件中的数据包并输出消息。假设消息文件中的每个数据包包含一个位置编号和5个字符。程序基于以下声明： ```cpp const int packetSize = 6; // 包括空字符('\0')终止符的数据包字符数 struct DataType { int position; // 数据包在消息中的位置 char body[packetSize]; // 数据包中的字符 int key () const { return position; } // 返回键字段 }; ``` 将程序保存为`packet.cpp`。 2. 使用`message.dat`文件中的消息测试程序。 #### 3. 有序列表合并操作 当需要合并两个大小相似的有序列表时，重复调用插入操作效率较低。更有效的方法是使用专门的合并操作： ```cpp void merge ( const OrdList &fromL ); ``` 要求：两个列表没有共同的键。 结果：将`fromL`中的数据项合并到当前列表，不改变`fromL`。 实现步骤如下： 1. 在`ordlist.cpp`文件中实现该操作，其原型已包含在`ordlist.h`文件的有序列表类声明中。 2. 通过移除`test4two.cpp`文件中以 “//M” 开头的行的注释分隔符（和字符 ‘M’）来激活 ‘M’（合并）命令。 3. 准备合并操作的测试计划，覆盖不同长度的列表，包括空列表和合并后为满列表的情况。 4. 执行测试计划，若发现实现中的错误，进行修正并重新执行测试计划。 #### 4. 有序列表子集操作 使用无序列表表示集合时，执行交集、并集、差集和子集等操作的时间复杂度可达$O(N^2)$。而使用有序列表可以将这些操作的执行时间降低到$O(N)$。 子集操作函数如下： ```cpp bool isSubset ( const OrdList &subL ) const; ``` 要求：无。 结果：如果`subL`中的每个键都在当前列表中，则返回`true`，否则返回`false`。 实现步骤如下： 1. 在`ordlist.cpp`文件中实现该操作，其原型已包含在`ordlist.h`文件的有序列表类声明中。 2. 通过移除`test4two.cpp`文件中以 “//S” 开头的行的注释分隔符（和字符 ‘S’）来激活 ‘S’（子集）命令。 3. 准备子集操作的测试计划，覆盖不同长度的列表，包括空列表。 4. 执行测试计划，若发现实现中的错误，进行修正并重新执行测试计划。 #### 5. 有序列表插入操作复杂度分析 ##### 5.1 数组实现（结合二分查找） | 步骤 | 时间复杂度 | | ---- | ---- | | 查找插入点 | $O(log N)$ | | 插入数据项 | $O(N)$ | | 整个操作 | $O(N)$ | 解释：二分查找的时间复杂度为$O(log N)$，但插入数据项时可能需要移动后续元素，时间复杂度为$O(N)$，因此整个操作的时间复杂度为$O(N)$。 ##### 5.2 链表实现（线性查找） | 步骤 | 时间复杂度 | | ---- | ---- | | 查找插入点 | $O(N)$ | | 插入数据项 | $O(1)$ | | 整个操作 | $O(N)$ | 解释：线性查找需要遍历链表，时间复杂度为$O(N)$，而链表插入操作的时间复杂度为$O(1)$，因此整个操作的时间复杂度为$O(N)$。 #### 6. 支持重复键的有序列表ADT 在最初定义有序列表ADT时，假设列表中没有两个数据项具有相同的键。若要支持多个数据项具有相同键的有序列表，需要对实现进行修改。具体修改可能包括在插入操作时处理重复键的情况，例如允许插入重复键的数据项，并在查找和删除操作中考虑重复键的影响。 #### 7. 栈ADT概述 栈是一种受限的