一、概念
（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
?
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; } 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; }
//链表结点结构
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）有哨兵的情况
[cpp]
view plain
copy
print
?
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; } 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; }
//链表结点结构
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;
}
三、练习
[cpp]
view plain
copy
print
?
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-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
10.2-6
使用带尾指针的链表，令A的尾指针为tail，tail->next=B
10.2-7
[cpp]
view plain
copy
print
?
void Reverse(list *L) { node *p = NULL, *q = L->Head, *r;
while(1) { r = q->next; q->next = p;
if(r == NULL) { L->Head = q;
break; } p = q; q = r; } }
