# 一、概念 （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)