数据结构实验：ADT复制、比较与双向链表实现

# 数据结构实验：ADT 复制、比较与双向链表实现 ## 1. 复制与比较 ADT 实验 ### 1.1 In - lab Exercise 2：复制与比较 ADT 在 C++ 中，默认的复制构造函数和赋值运算符的行为可能会导致运行时错误，使程序在执行过程中中断。同时，一些其他的默认 C++ 运算符在需要使用数据结构的深版本而非浅版本时，也会出现不可接受的行为。例如，比较运算符（`==`）在比较两个等价但不同的单链表时会给出无效结果，因为它比较的是头指针和游标指针的值，而不是链表中的数据项。 #### 操作实现步骤 1. **实现比较操作**：实现 `bool operator == ( const List &rightList )` 操作，并将其添加到 `listlnk2.cpp` 文件中。该操作的原型已包含在 `listlnk2.h` 文件的 `List` 类声明中。 2. **激活测试命令**：在 `test8.cpp` 文件的测试程序中，移除以 `//?` 开头的行中的注释分隔符（和字符 `?`），激活 `?`（相等比较）命令。 3. **准备测试计划**：准备一个测试计划，涵盖各种列表，包括空列表和包含单个数据项的列表。可以使用 `=` 命令设置测试程序中第二个列表的值。 4. **执行测试计划**：执行测试计划，如果发现反向操作实现中的错误，进行修正并再次执行测试计划。 #### 测试计划表格 | 测试用例 | 命令 | 预期结果 | 检查情况 | | --- | --- | --- | --- | | | | | | ### 1.2 In - lab Exercise 3：自赋值问题处理 在复杂的指针程序中，可能会出现将对象赋值给自己的情况。例如 `list1 = list1;` 这样的语句，虽然不太可能由程序员编写，并且很可能会被优化编译器作为无用语句移除，但在某些情况下，如下面的代码： ```cpp List<int> *listPtr; listPtr = &list1; // Intermediate statements ... *listPtr = list1; ``` 可能会绕过优化器，导致将列表赋值给自己。 #### 操作步骤 1. **激活测试命令**：在 `test8.cpp` 文件的测试程序中，移除以 `//S` 开头的行中的注释分隔符（和字符 `S`），激活 `S`（测试自赋值）命令。 2. **编译并运行程序**：编译 `test8.cpp` 并运行可执行文件，向列表中添加一些数据，然后选择 `S` 命令，观察发生的情况并分析原因。 3. **完成测试计划**：添加测试用例，检查赋值操作的实现是否正确处理了自赋值问题。 4. **修改赋值运算符函数**：修改 `listlnk2.cpp` 中的 `operator=()` 函数，确保列表将自身作为初始化模型传递时不会造成损害。 5. **执行测试计划**：执行测试计划，如果发现操作实现中的错误，进行修正并再次执行测试计划。 #### 测试计划表格 | 测试用例 | 命令 | 预期结果 | 检查情况 | | --- | --- | --- | --- | | | | | | ### 1.3 Postlab Exercise 1：重载赋值运算符的原型选择 重载赋值运算符有两种可能的原型： - `void operator = ( const List<DT> &rightList )`：可以将 `list2` 和 `list3` 设置为与 `list1` 相同的值，如 `list2 = list1; list3 = list1;` - `List<DT>& operator = ( const List<DT> &rightList )`：返回类型为 `List<DT>&`，可以用于更复杂的表达式，如 `list3 = list2 = list1;` 和 `if (( list2 = list1 ) == list3 )` 两种版本的函数代码除了第二个版本的最后一行 `return *this;` 外完全相同。需要思考哪种版本的赋值运算符函数更可取，并说明理由。 ### 1.4 Postlab Exercise 2：ADT 复制构造函数和重载赋值运算符需求分析 考虑之前涉及的所有抽象数据类型（ADT），如日志（Logbook）、点列表（Point List）、列表的数组实现（Array implementation of the List）、有序列表（Ordered List）、栈（Stack）、队列（Queue）和单链表实现的列表（Singly linked Implementation of the List），分析哪些需要有复制构造函数和重载赋值运算符，并说明理由。 ## 2. 双向链表实现列表 ADT 实验 ### 2.1 实验目标与概述 之前在实验 7 中创建的单链表实现的列表 ADT 在插入和从一个节点移动到下一个节点时效率较高，但在删除和向后移动列表时效率较低。在本次实验中，将使用循环双向链表创建列表 ADT 的实现，该实现可以在常数时间内执行大多数列表 ADT 操作。 ### 2.2 列表 ADT 定义 #### 2.2.1 数据项 列表中的数据项为通用类型 `DT`。 #### 2.2.2 结构 数据项形成线性结构，列表数据项从列表的开头到结尾依次排列。数据项的顺序由每个数据项插入列表的时间和位置决定，而不是由列表数据项中包含的数据决定。在任何非空列表中，任何时刻都有一个数据项被列表的游标标记，可以使用改变游标位置的操作遍历列表。 #### 2.2.3 操作 | 操作 | 要求 | 结果 | | --- | --- | --- | | `List ( int ignored = 0 )` | 无 | 构造函数，创建一个空列表。参数用于与数组实现的调用兼容性，被忽略。 | | `~List ()` | 无 | 析构函数，释放用于存储列表的内存。 | | `void insert ( const DT &newDataItem ) throw ( bad_alloc )` | 列表未满 | 将 `newDataItem` 插入列表。如果列表不为空，则在游标之后插入；否则，将其作为列表的第一个（也是唯一的）数据项插入。在任何情况下，将游标移动到 `newDataItem`。 | | `void remove () throw ( logic_error )` | 列表不为空 | 从列表中移除游标标记的数据项。如果结果列表不为空，则将游标移动到被删除数据项之后的数据项；如果被删除的数据项在列表末尾，则将游标移动到列表开头。 | | `void replace ( const DT &newDataItem ) throw ( logic_error )` | 列表不为空 | 用 `newDataItem` 替换游标标记的数据项，游标保持在 `newDataItem` 处。 | | `void clear ()` | 无 | 移除列表中的所有数据项。 | | `bool isEm