【Weiss】【第03章】练习3.3：通过交换指针交换单/双链表元素

【练习3.3】

通过之调整指针（而不是数据）来交换两个相邻的元素，使用

a.单链表

b.双链表

Answer：

先放测试代码，折叠标题可以看到分别是哪种链表的测试。

实测可满足题意，但单链表和双链表的两段代码是分开实现的，所以需要分开测试。

如果要合在一起的话，需要改一下头文件包含以及命名空间。

单链表测试代码：

 1 #include <iostream>
 2 #include "linklist.cpp"
 3 using namespace std;
 4 using namespace linklist;
 5 template class List<int>;
 6 int main(void)
 7 {
 8     List<int> number;
 9 
10     //原始链表
11     cout << "/*additem()*/" << endl;
12     number.additem(2);
13     number.additem(3);
14     number.additem(5);
15     number.additem(7);
16     number.additem(11);
17     number.additem(13);
18     number.additem(17);
19     number.traverse();
20     cout << "
/*end*/

" << endl;
21 
22     //测试交换顺序，头节点与中间节点各一
23     cout << "/*swappos()*/" << endl;
24     number.swappos(number.find(11));
25     number.swappos(number.find(2));
26     number.traverse();
27     cout << "/*end*/

" << endl;
28 
29     system("pause");
30 }

View Code

双链表测试代码：

 1 #include <iostream>
 2 #include "double_linklist.cpp"
 3 using namespace std;
 4 using namespace doublelinklist;
 5 template class DList<int>;
 6 int main(void)
 7 {
 8     DList<int> number;
 9 
10     //测试插入
11     cout << "/*additem()*/" << endl;
12     number.additem(2);
13     number.additem(3);
14     number.additem(5);
15     number.additem(7);
16     number.additem(11);
17     number.additem(13);
18     number.additem(17);
19     number.traverse();
20     cout << "
/*end*/

" << flush;
21 
22     //测试交换函数
23     cout << "/*swappos*/" << endl;
24     //测试头节点
25     number.swappos(number.find(2));
26     number.traverse();
27     cout << endl;
28     //测试邻接尾节点的中间节点
29     number.swappos(number.find(13));
30     number.traverse();
31     cout << endl;
32     //测试中间节点
33     number.swappos(number.find(7));
34     number.traverse();
35     cout << endl;
36     //测试尾节点
37     number.swappos(number.find(13));
38     cout << "/*end*/

" << flush;
39 
40     system("pause");
41 }

View Code

通过交换指针交换节点直观上还是比较容易的，但是需要比较细致否则容易做错。

因为注释不太好解释，所以代码上就不放注释了，直接上图比较直观。

首先以单链表为例，pos是头节点的情形可以当做一种特殊情况，处理方法比一般情况要简单。

更一般地，通过迭代找到pos的前驱，在后面的实现代码里记为iter变量，然后几个指针的变化关系如下图。

最后的问号代表该处可能是一个节点，也可能是nullptr，但是对于单链表而言没有影响。

考虑双链表时，同样不考虑pos是头指针的情况（当然在代码里还是要表现的），有三点细微的不一致

①、不需从链表头迭代寻找pos的前驱iter，在没有修改前向指针的情况下，可以把单链表书写中的iter全部写成pos->prev

②、按单链表的方法，修改完后向指针后，需要调整前向指针

③、尾部的问号节点如果为空，则会对rear的位置产生影响；如果不为空，则需调整该问号节点的前向指针

简图如下：

最后是实现代码，将其分别复制进此前对应的例程中，函数的声明请自行补充。

单链表实现代码：

 1 //练习3.3新增，交换相邻节点
 2 template <typename T> bool List<T>::swappos(Node<T>* pos)
 3 {
 4     if (pos->next == nullptr)
 5     {
 6         cout << ("Illegal!") << endl;
 7         return false;
 8     }
 9     if (pos == front)
10     {
11         front = front->next;
12         pos->next = front->next;
13         front->next = pos;
14     }
15     else
16     {
17         Node<T>* iter = front;
18         while (iter->next != pos)
19             iter = iter->next;
20         if (iter == nullptr)
21         {
22             cout << ("Illegal!") << endl;
23             return false;
24         }
25         else
26         {
27             iter->next = pos->next;
28             pos->next = pos->next->next;
29             iter->next->next = pos;
30         }
31     }
32     return true;
33 }

双链表实现代码：

 1 //练习3.3新增，通过交换指针交换节点
 2 //不检测pos位置是否确实在双链表中（否则速度比单链表更慢，失去意义）
 3 template <typename T> bool DList<T>::swappos(Node<T>* pos)
 4 {
 5     if (pos->next == nullptr)
 6     {
 7         cout << "Illegal" << endl;
 8         return false;
 9     }
10     if (pos == front)
11     {
12         front = front->next;
13         front->prev = nullptr;
14         pos->next = front->next;
15         pos->prev = front;
16         front->next = pos;
17     }
18     else
19     {
20         //后向指针调整
21         pos->prev->next = pos->next;
22         pos->next = pos->next->next;
23         pos->prev->next->next = pos;
24         //前向指针调整
25         pos->prev->next->prev = pos->prev;
26         pos->prev = pos->prev->next;
27         
28     }
29     //判断尾指针是否为空
30     if (pos->next == nullptr)
31         rear = pos;
32     else
33         pos->next->prev = pos;
34     return true;
35 }