设计一个算法void swap(SqList &L),将存储在一个顺序表中的数按相反的顺序存储。编写一个测试程序,以测试以上算法的正确性。
时间: 2024-10-12 21:13:30 浏览: 5
设计一个名为`swap`的算法,用于将顺序列表(`SqList`)中的元素按相反的顺序排列,可以按照以下步骤实现:
```cpp
// 假设SqList是一个双向链表节点,包含数据成员data和指向下一个节点的指针next
struct ListNode {
int data;
ListNode* next;
};
void reverseList(ListNode*& head) { // 使用引用参数避免复制整个链表
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* temp = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点的next指向前一个节点
prev = curr; // 更新前一个节点为当前节点
curr = temp; // 移动到下一个节点
}
head = prev; // 更新头节点为反转后的最后一个节点
}
void swap(SqList& L) {
if (L.isEmpty()) return; // 如果链表为空,无需操作
reverseList(L.head); // 反转列表
reverseList(L.head); // 再次反转,恢复原顺序
}
```
为了测试这个`swap`函数的正确性,你可以创建一个简单的测试程序,例如:
```cpp
int main() {
SqList list; // 初始化一个空的顺序列表
// 添加一些元素到列表
for (int i = 0; i < 5; ++i) {
list.push_back(i);
}
// 打印原始列表
cout << "Original List: ";
printList(list);
swap(list); // 调用swap函数
// 再次打印列表,检查是否按相反的顺序排列
cout << "\nReversed List after swapping: ";
printList(list);
return 0;
}
// 辅助函数,用于打印链表
void printList(const SqList& L) {
ListNode* curr = L.head;
while (curr != nullptr) {
cout << curr->data << " -> ";
curr = curr->next;
}
cout << "nullptr" << endl;
}
```
运行这个测试程序,你会看到原始列表和经过`swap`函数处理后的列表,确认它们的顺序是否相反。