# 一、概念 （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）沒有哨兵的情況 ~~~ //鏈表結點結構 struct node { node *pre; node *next; int key; //構造函數 node(int x):pre(NULL),next(NULL),key(x){} }; //鏈表結構 struct List { node *head; List():head(NULL){} }; //打印 void List_Print(List *L) { node *p = L->head; while(p) { cout<<p->key<<' '; p = p->next; } cout<<endl; } //搜索，找出L中第一個關鍵字為k的結點，沒有則返回NULL node *List_Search(List *L, int k) { node *x = L->head; while(x != NULL && x->key!=k) x = x->next; return x; } //插入 void List_Insert(List *L, node *x) { //插入到表的前端 x->next = L->head; if(L->head != NULL) L->head->pre = x; L->head = x; x->pre = NULL; } //刪除 void List_Delete(List *L, node* x) { if(x->pre != NULL) x->pre->next = x->next; else L->head = x->next; if(x->next != NULL) x->next->pre = x->pre; delete x; } ~~~ ### （2）有哨兵的情況 ~~~ //鏈表結點結構 struct node { node *pre; node *next; int key; //構造函數 node(int x):pre(NULL),next(NULL),key(x){} }; //鏈表結構 struct List { node *nil;//哨兵 List() { nil = new node(0); nil->next = nil; nil->pre = nil; } }; //打印 void List_Print(List *L) { node *p = L->nil->next; while(p != L->nil) { cout<<p->key<<' '; p = p->next; } cout<<endl; } //搜索，找出L中第一個關鍵字為k的結點，沒有則返回NULL node *List_Search(List *L, int k) { node *x = L->nil->next; while(x != L->nil && x->key!=k) x = x->next; return x; } //插入 void List_Insert(List *L, node *x) { //插入到表的前端 x->next = L->nil->next; L->nil->next->pre = x; L->nil->next = x; x->pre = L->nil; } //刪除 void List_Delete(List *L, node* x) { x->pre->next = x->next; x->next->pre = x->pre; delete x; } ~~~ # 三、練習 ~~~ 10.2-1 能，能 10.2-2 //結點 struct node { node *pre;//為了方便實現出棧操作 node *next; int key; node(int x):pre(NULL),next(NULL),key(x){} }; //鏈式棧 struct list { node *Head;//棧的起始結點 node *Top;//棧頂指針 list(){Head = new node(0);Top = Head;} }; //打印棧中的元素 void Print(list *L) { node *p = L->Head->next; while(p) { cout<<p->key<<' '; p = p->next; } cout<<endl; } //入棧 void Push(list *L, int x) { //構造一個新的結點 node *A = new node(x); //鏈入到棧頂位置，修改指針 L->Top->next = A; A->pre = L->Top; L->Top = A; } //出棧 int Pop(list *L) { if(L->Head == L->Top) { cout<<"error:underflow"<<endl; return -1; } //取出棧頂元素 int ret = L->Top->key; //修改指針 node *A = L->Top; L->Top = A->pre; L->Top->next = NULL; delete A; return ret; } 10.2-3 //結點 struct node { node *next; int key; node(int x):next(NULL),key(x){} }; //鏈式隊列 struct list { node *Head;//頭指針 node *Tail;//尾指針 list(){Head = new node(0);Tail = Head;} }; //打印 void Print(list *L) { node *p = L->Head->next; while(p) { cout<<p->key<<' '; p = p->next; } cout<<endl; } //入隊列 void Enqueue(list *L, int x) { //構造一個新的結點 node *A = new node(x); //鏈入尾部，修改指針 L->Tail->next = A; L->Tail = A; } //出隊列 int Dequeue(list *L) { if(L->Head == L->Tail) { cout<<"error:underflow"<<endl; return -1; } //取出隊頭結點，修改指針 node *A = L->Head->next; int ret = A->key; L->Head->next = A->next; if(A == L->Tail) L->Tail = L->Head; delete A; return ret; } 10.2-4 把哨兵的值置為一個不可能與x相等的值 ~~~ 10.2-5 見[算法導論 10.2-5 環形鏈表實現字典操作INSERT、DELETE、SEARCH](http://blog.csdn.net/mishifangxiangdefeng/article/details/7993190) 10.2-6 使用帶尾指針的鏈表，令A的尾指針為tail，tail->next=B 10.2-7 ~~~ //逆轉 void Reverse(list *L) { node *p = NULL, *q = L->Head, *r; //依次修改指針，讓q是p->next,令q->next=p while(1) { r = q->next; q->next = p; if(r == NULL) { L->Head = q; break; } p = q; q = r; } } ~~~ 10.2-8 見[算法導論-10.2-8](http://blog.csdn.net/mishifangxiangdefeng/article/details/7706631)