【Weiss】【第03章】练习3.15：自调整链表

【练习3.15】

a.写出自调整表的数组实现。自调整表如同一个规则的表，但是所有的插入都在表头进行。

当一个元素被Find访问时，它就被移到表头而并不改变其余的项的相对顺序。

b.写出自调整表的链表实现

c.设每个元素都有其被访问的固定概率p_i。证明那些具有最高访问概率的元素都靠近表头。

Answer:

a简单得令人发指，所以不写了。

b只需要在原链表上加一个自适应的Find访问版本find_selfadj就行，很简单，如下代码。

c在摊还分析那里会频繁遇到的，这儿超纲了。

测试代码：

 1 #include <iostream>
 2 #include "linklist.h"
 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.traverse();
19     cout << "\n/*end*/\n\n" << flush;
20 
21     number.find_selfadj(13);
22     number.traverse();
23     cout << "\n/*end*/\n\n" << flush;
24 
25     number.find_selfadj(7);
26     number.traverse();
27     cout << "\n/*end*/\n\n" << flush;
28     
29     system("pause");
30 }

View Code

实现代码：

 1 //练习3.15新增，自调整表链表实现
 2 template <typename T> Node<T>* List<T>::find_selfadj(const T &item)
 3 {
 4     Node<T>* iter = find_prev(item);
 5     //如元素不存在或元素为头元素，则操作与一般查找完全一致
 6     if (length == 0)
 7         return nullptr;
 8     else if (front->data == item)
 9         return front;
10     //否则，调整指针将元素放到头部
11     else
12     {
13         //保存断开位置的后继
14         Node<T>* temp = iter->next->next;
15         //断开节点后继为头节点
16         iter->next->next = front;
17         //头节点更换
18         front = iter->next;
19         //接上断开位置
20         iter->next = temp;
21         //如果断开处为链表尾则调整尾节点
22         if (temp == nullptr)
23             rear = iter;
24         return front;
25     }
26 }

【Weiss】【第03章】练习3.15：自调整链表

推荐阅读