数据结构之链表
一、概念
（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
print?01.//链表结点结构
02.struct node
03.{
04. node *pre;
05. node *next;
06. int key;
07. //构造函数
08. node(int x):pre(NULL),next(NULL),key(x){}
09.};
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<key<<' ';
23. p = p->next;
24. }
25. cout<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 copy print?
01.//链表结点结构
02.struct node
03.{
04. node *pre;
05. node *next;
06. int key;
07. //构造函数
08. node(int x):pre(NULL),next(NULL),key(x){}
09.};
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<key<<' ';
23. p = p->next;
24. }
25. cout<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.}
（2）有哨兵的情况
[cpp] view plain copy
print?01.//链表结点结构
02.struct node
03.{
04. node *pre;
05. node *next;
06. int key;
07. //构造函数
08. node(int x):pre(NULL),next(NULL),key(x){}
09.};
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<key<<' ';
28. p = p->next;
29. }
30. cout<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 print?
01.//链表结点结构
02.struct node
03.{
04. node *pre;
05. node *next;
06. int key;
07. //构造函数
08. node(int x):pre(NULL),next(NULL),key(x){}
09.};
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<key<<' ';
28. p = p->next;
29. }
30. cout<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
print?01.10.2-1
02.能，能
03.10.2-2
04.//结点
05.struct node
06.{
07. node *pre;//为了方便实现出栈操作
08. node *next;
09. 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<key<<' ';
26. p = p->next;
27. }
28. cout<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"<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<key<<' ';
79. p = p->next;
80. }
81. cout<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"<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 copy print?
01.10.2-1
02.能，能
03.10.2-2
04.//结点
05.struct node
06.{
07. node *pre;//为了方便实现出栈操作
08. node *next;
09. 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<key<<' ';
26. p = p->next;
27. }
28. cout<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"<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<key<<' ';
79. p = p->next;
80. }
81. cout<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"<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相等的值
10.2-5
见算法导论 10.2-5 环形链表实现字典操作INSERT、DELETE、SEARCH
10.2-6
使用带尾指针的链表，令A的尾指针为tail，tail->next=B
10.2-7
[cpp] view plain copy
print?01.//逆转
02.void Reverse(list *L)
03.{
04. node *p = NULL, *q = L->Head, *r;
05. //依次修改指针，让q是p->next,令q->next=p
06. while(1)
07. {
08. r = q->next;
09. q->next = p;
10. if(r == NULL)
11. {
12. L->Head = q;
13. break;
14. }
15. p = q;
16. q = r;
17. }
18.}