数据结构之链表

╰半橙微兮° 2022-06-15 01:15 190阅读 0赞

# 一、概念 #

（1）数组的线性序是由数组的下标决定的，链表中的顺序是由各对象中的指针所决定的

（2）链表结点结构

node \*prev;

node \*next;

int key;

（3）链表结点

node \*head;

node \*nil;//哨兵

（4）对链表的操作

LIST-SEARCH(L, k)

LIST-INSERT(L, x)

LIST-DELETE(L, x)

（5）哨兵是个哑对象，可以简化边界条件

# 二、代码 #

## （1）没有哨兵的情况 ##

**\[cpp\]**  [view plain][]  [copy][view plain]

[print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  //链表结点结构  
2.  **struct** node  
3.  \{  
4.      node \*pre;  
5.      node \*next;  
6.      **int** key;  
7.      //构造函数  
8.      node(**int** x):pre(NULL),next(NULL),key(x)\{\}  
9.  \};  
10. //链表结构  
11. **struct** List  
12. \{  
13.     node \*head;  
14.     List():head(NULL)\{\}  
15. \};  
16. //打印  
17. **void** List\_Print(List \*L)  
18. \{  
19.     node \*p = L->head;  
20.     **while**(p)  
21.     \{  
22.         cout<<p->key<<' ';  
23.         p = p->next;  
24.     \}  
25.     cout<<endl;  
26. \}  
27. //搜索，找出L中第一个关键字为k的结点，没有则返回NULL  
28. node \*List\_Search(List \*L, **int** k)  
29. \{  
30.     node \*x = L->head;  
31.     **while**(x != NULL && x->key!=k)  
32.         x = x->next;  
33.     **return** x;  
34. \}  
35. //插入  
36. **void** List\_Insert(List \*L, node \*x)  
37. \{  
38.     //插入到表的前端  
39.     x->next = L->head;  
40.     **if**(L->head != NULL)  
41.         L->head->pre = x;  
42.     L->head = x;  
43.     x->pre = NULL;  
44. \}  
45. //删除  
46. **void** List\_Delete(List \*L, node\* x)  
47. \{  
48.     **if**(x->pre != NULL)  
49.         x->pre->next = x->next;  
50.     **else**  
51.         L->head = x->next;  
52.     **if**(x->next != NULL)  
53.         x->next->pre = x->pre;  
54.     **delete** x;  
55. \}

**\[cpp\]**  [view plain][view plain 1]   [copy][view plain 1]

[print][view plain 1] [?][view plain 1]

## （2）有哨兵的情况 ##

**\[cpp\]**  [view plain][]  [copy][view plain]

[print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  //链表结点结构  
2.  **struct** node  
3.  \{  
4.      node \*pre;  
5.      node \*next;  
6.      **int** key;  
7.      //构造函数  
8.      node(**int** x):pre(NULL),next(NULL),key(x)\{\}  
9.  \};  
10. //链表结构  
11. **struct** List  
12. \{  
13.     node \*nil;//哨兵  
14.     List()  
15.     \{  
16.         nil = **new** node(0);  
17.         nil->next = nil;  
18.         nil->pre = nil;  
19.     \}  
20. \};  
21. //打印  
22. **void** List\_Print(List \*L)  
23. \{  
24.     node \*p = L->nil->next;  
25.     **while**(p != L->nil)  
26.     \{  
27.         cout<<p->key<<' ';  
28.         p = p->next;  
29.     \}  
30.     cout<<endl;  
31. \}  
32. //搜索，找出L中第一个关键字为k的结点，没有则返回NULL  
33. node \*List\_Search(List \*L, **int** k)  
34. \{  
35.     node \*x = L->nil->next;  
36.     **while**(x != L->nil && x->key!=k)  
37.         x = x->next;  
38.     **return** x;  
39. \}  
40. //插入  
41. **void** List\_Insert(List \*L, node \*x)  
42. \{  
43.     //插入到表的前端  
44.     x->next = L->nil->next;  
45.     L->nil->next->pre = x;  
46.     L->nil->next = x;  
47.     x->pre = L->nil;  
48. \}  
49. //删除  
50. **void** List\_Delete(List \*L, node\* x)  
51. \{  
52.     x->pre->next = x->next;  
53.     x->next->pre = x->pre;  
54.     **delete** x;  
55. \}

**\[cpp\]**  [view plain][view plain 1]   [copy][view plain 1]

[print][view plain 1] [?][view plain 1]

1.  //链表结点结构  
2.  **struct** node  
3.  \{  
4.      node \*pre;  
5.      node \*next;  
6.      **int** key;  
7.      //构造函数  
8.      node(**int** x):pre(NULL),next(NULL),key(x)\{\}  
9.  \};  
10. //链表结构  
11. **struct** List  
12. \{  
13.     node \*nil;//哨兵  
14.     List()  
15.     \{  
16.         nil = **new** node(0);  
17.         nil->next = nil;  
18.         nil->pre = nil;  
19.     \}  
20. \};  
21. //打印  
22. **void** List\_Print(List \*L)  
23. \{  
24.     node \*p = L->nil->next;  
25.     **while**(p != L->nil)  
26.     \{  
27.         cout<<p->key<<' ';  
28.         p = p->next;  
29.     \}  
30.     cout<<endl;  
31. \}  
32. //搜索，找出L中第一个关键字为k的结点，没有则返回NULL  
33. node \*List\_Search(List \*L, **int** k)  
34. \{  
35.     node \*x = L->nil->next;  
36.     **while**(x != L->nil && x->key!=k)  
37.         x = x->next;  
38.     **return** x;  
39. \}  
40. //插入  
41. **void** List\_Insert(List \*L, node \*x)  
42. \{  
43.     //插入到表的前端  
44.     x->next = L->nil->next;  
45.     L->nil->next->pre = x;  
46.     L->nil->next = x;  
47.     x->pre = L->nil;  
48. \}  
49. //删除  
50. **void** List\_Delete(List \*L, node\* x)  
51. \{  
52.     x->pre->next = x->next;  
53.     x->next->pre = x->pre;  
54.     **delete** x;  
55. \}

# 三、练习 #

**\[cpp\]**  [view plain][]  [copy][view plain]

[print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  10.2-1  
2.  能，能  
3.  10.2-2  
4.  //结点  
5.  **struct** node  
6.  \{  
7.      node \*pre;//为了方便实现出栈操作  
8.      node \*next;  
9.      **int** key;  
10.     node(**int** x):pre(NULL),next(NULL),key(x)\{\}  
11. \};  
12. //链式栈  
13. **struct** list  
14. \{  
15.     node \*Head;//栈的起始结点  
16.     node \*Top;//栈顶指针  
17.     list()\{Head = **new** node(0);Top = Head;\}  
18. \};  
19. //打印栈中的元素  
20. **void** Print(list \*L)  
21. \{  
22.     node \*p = L->Head->next;  
23.     **while**(p)  
24.     \{  
25.         cout<<p->key<<' ';  
26.         p = p->next;  
27.     \}  
28.     cout<<endl;  
29. \}  
30. //入栈  
31. **void** Push(list \*L, **int** x)  
32. \{  
33.     //构造一个新的结点  
34.     node \*A = **new** node(x);  
35.     //链入到栈顶位置，修改指针  
36.     L->Top->next = A;  
37.     A->pre = L->Top;  
38.     L->Top = A;  
39. \}  
40. //出栈  
41. **int** Pop(list \*L)  
42. \{  
43.     **if**(L->Head == L->Top)  
44.     \{  
45.         cout<<"error:underflow"<<endl;  
46.         **return** -1;  
47.     \}  
48.     //取出栈顶元素  
49.     **int** ret = L->Top->key;  
50.     //修改指针  
51.     node \*A = L->Top;  
52.     L->Top = A->pre;  
53.     L->Top->next = NULL;  
54.     **delete** A;  
55.     **return** ret;  
56. \}  
57. 10.2-3  
58. //结点  
59. **struct** node  
60. \{  
61.     node \*next;  
62.     **int** key;  
63.     node(**int** x):next(NULL),key(x)\{\}  
64. \};  
65. //链式队列  
66. **struct** list  
67. \{  
68.     node \*Head;//头指针  
69.     node \*Tail;//尾指针  
70.     list()\{Head = **new** node(0);Tail = Head;\}  
71. \};  
72. //打印  
73. **void** Print(list \*L)  
74. \{  
75.     node \*p = L->Head->next;  
76.     **while**(p)  
77.     \{  
78.         cout<<p->key<<' ';  
79.         p = p->next;  
80.     \}  
81.     cout<<endl;  
82. \}  
83. //入队列  
84. **void** Enqueue(list \*L, **int** x)  
85. \{  
86.     //构造一个新的结点  
87.     node \*A = **new** node(x);  
88.     //链入尾部，修改指针  
89.     L->Tail->next = A;  
90.     L->Tail = A;  
91. \}  
92. //出队列  
93. **int** Dequeue(list \*L)  
94. \{  
95.     **if**(L->Head == L->Tail)  
96.     \{  
97.         cout<<"error:underflow"<<endl;  
98.         **return** -1;  
99.     \}  
100.     //取出队头结点，修改指针  
101.     node \*A = L->Head->next;  
102.     **int** ret = A->key;  
103.     L->Head->next = A->next;  
104.     **if**(A == L->Tail)  
105.         L->Tail = L->Head;  
106.     **delete** A;  
107.     **return** ret;  
108. \}  
109. 10.2-4  
110. 把哨兵的值置为一个不可能与x相等的值

**\[cpp\]**  [view plain][view plain 1]   [copy][view plain 1]

[print][view plain 1] [?][view plain 1]

10.2-5

见 [算法导论 10.2-5 环形链表实现字典操作INSERT、DELETE、SEARCH][10.2-5 _INSERT_DELETE_SEARCH]

10.2-6

使用带尾指针的链表，令A的尾指针为tail，tail->next=B

10.2-7

**\[cpp\]**  [view plain][]  [copy][view plain]

[print][view plain] [?][view plain]

1.  //逆转  
2.  **void** Reverse(list \*L)  
3.  \{  
4.      node \*p = NULL, \*q = L->Head, \*r;  
5.      //依次修改指针，让q是p->next,令q->next=p  
6.      **while**(1)  
7.      \{  
8.          r = q->next;  
9.          q->next = p;  
10.         **if**(r == NULL)  
11.         \{  
12.             L->Head = q;  
13.             **break**;  
14.         \}  
15.         p = q;  
16.         q = r;  
17.     \}  
18. \}

[view plain]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7701376#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/1708189
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/1708189/fork
[view plain 1]: http://blog.csdn.net/xiangzhihong8/article/details/51589184#
[10.2-5 _INSERT_DELETE_SEARCH]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7993190