数据结构 华中科技大学计算机学院 (3)
------------------------------------------------
2001-3-12
2.3 线性表的链式存储结构
2.3.1单链表
1 单链表的结点结构,
data next
前驱 a(i-1) ─→ a i ─→ 后继 a(i+1)
结点类型说明例 1 C语言的,结构,类型,
struct node
{ ElemType data； //data为抽象元素类型
struct node *next； //next为指针类型
}；
指向结点的指针变量 head,p,q说明,
struct node *head,*p,*q；
例 2 用 typedef定义指针类型,
typedef struct Lnode
{ ElemType data； //data为抽象元素类型
struct node *next； //next为指针类型
} *Linklist；
指针变量 head,p,q的说明,
Linklist head,p,q；
2.单链表的一般形式,
(1)不带表头结点的单链表,
data next
head ---→ a1 ---→ a2 --→,.,--→ an ∧
头指针 首结点 尾结点其中,data称为数据域,next称为指针域 /链域当 head==NULL,为空表；否则为非空表
(2)带表头结点的单链表,
a.非空表,
data next
head ---→ /// --→ a1 --→..,--→ an ∧
头指针 表头结点 首结点 尾结点
b.空表,
data next
head ---→ /// ∧
头指针 表头结点其中,head指向表头结点，
head->data不放元素，
head->next指向首结点 a1,
当 head->next==NULL,为空表；否则为非空表。
3.单链表操作和算法举例：
(1) 生成单链表 。
例 1 输入一列整数，以 0为结束标志,生成,先进先出,单链表。
若输入,2,8,5,0，则生成：
tail
↓
head -→ /// --→ 2 --→ 8 --→ 5 --→ 0 ∧
#define NULL 0 //定义符号常量 NULL
#define LENG sizeof(struct Lnode) //结点所占的单元数
struct Lnode //定义结点类型
{ int data； //data为整型
struct node *next； //next为指针类型
}；
//// ^初始化,head ////输入 2,head
tail tail
2 ^
p
①
③
②
每次输入新元素后：
生成新结点； p=malloc(结点大小） ; p->data=e; p->next=NULL;
② 添加到表尾； tail->next=p;
③ 设置新表尾。 tail=p;
////head
tail
8 ^
①
③
②
2输入 8：
p
先进先出表的产生过程 (1,2,3,4,0)：
head
p
/// 1 2 3 4 0
p p p p
头指针 头结点
tail
head=malloc(sizeof(struct node))
tail=head
tail
p=malloc(sizeof(struct node))
tail->next=p
tail=p
p=malloc(sizeof(struct node))
tail
tail->next=p
tail=p
tail tail tail
tail->next=NULL;
^
算法：生成,先进先出,单链表（ 链式队列 ）
struct Lnode *creat1( )
{ struct Lnode *head,*tail,*p； //变量说明
int e；
head=(struct Lnode *)malloc(LENG)； //生成表头结点
tail=head； //尾指针指向表头
do{ p=(struct Lnode *)malloc(LENG)； //生成新结点
scanf(“%d”,&e)； //输入一个数
p->data=e； //装入输入的元素 e
tail->next=p； //新结点链接到表尾
tail=p； //尾指针指向新结点
}
while (e!=0)； //不为 0
tail->next=NULL； //尾结点的 next置为空指针
return head； //返回头指针
}
例 2 生成,后进先出,单链表 (链式栈 )。输入,2,8,5,0,生成：
head --→ /// --→ 0 --→ 5 --→ 8 --→ 2 ∧
算法：
struct Lnode *creat2( ) //生成,后进先出,单链表
{ struct Lnode *head,*p；
head=(struct Lnode *)malloc(LENG)； //生成表头结点
head->next=NULL； //置为空表
do
{ p=(struct Lnode *)malloc(LENG)； //生成新结点
scanf(“%d”,&(p->data))； //输入数,送新结点的 data
p->next=head->next； //新结点插入表头结点之后
head->next=p； //尾指针指向新结点
} while (p->data!=0)； //不为 0
return head； //返回头指针
}
//// ^初始化,head ////输入 2,head 2 ^
p
①
②
每次输入新元素后：
生成新结点； p=malloc(结点大小） ; p->data=e;
② 新结点指针指向首元素； p->next=head->next;
③ 新结点作为首元素,head->next=p;
////head 2 ^
①
②8
输入 8：
p
③
③
(2) 插入 一个结点例 1 在递增有序单链表 (0,2,5,10)中插入元素 4：
head --→ /// --→ 0 --→ 2 --→ 5 --→ 10 ∧
q ↗ ↖ p
f --→ 4
执行：
f=(struct Lnode *)malloc(LENG)； //生成新结点
f->data=4； //装入元素 4
f->next=p； //结点 5的地址送入结点 4的 next
q->next=f； //结点 4的地址送入结点 2的 next
变为：
head-→ /// -→ 0 -→ 2 -→ 4 -→ 5 -→ 10 ∧
q ↗ f ↗ p ↗
例 2 输入一列整数,以 0为结束标志,生成 递增有序单链表 。 (不包括 0）
///// 1 4 7 10 17 ^
1 4 7 10 17 ^
head
head
p!=NULL&&
e>p->data
真假插入算法返回 head
head?p
p?q
p->next?p
NULL?q new(f) e?f->data
p==NULL
p==headhead==NULL
假 真
f?head f?q->next
NULL?f->next
f?q->next
q?f->next
p?f->next
f?head
假假真 真
① ② ③ ④
① 空表插入；
② 尾部插入；
③ 首部插入；
④ 一般插入。
e为新元素值不带头结点算法例 2 生成不带头结点的 递增有序单链表 。 (不包括 0）
struct Lnode * creat3_1(struct Lnode *head,int e)
{ q=NULL； p=head； //q,p扫描,查找插入位置
while (p && e>p->data) //未扫描完,且 e大于当前结点
{ q=p； p=p->next； } //q,p后移,查下一个位置
f=(struct Lnode *)malloc(LENG)； //生成新结点
f->data=e； //装入元素 e
if (p==NULL){
f->next=NULL;
if (head=NULL) //(1)对空表的插入
head=f;
else q->next=f;} //(2)作为最后一个结点插入
else if (q==NULL) //(3)作为第一个结点插入
{f->next=p; head=f;}
else
{f->next=p； q->next=f； } //(4)一般情况插入新结点
return head;
}
p!=NULL&&
e>p->data
真假插入算法返回 head
head?p
p?q
p->next?p
NULL?q new(f) e?f->data
q==NULL
假 真
NULL?f->next
f?q->next
① ②
① 作为第一元素或首元素插入；
②一般插入或作为尾元素插入；
e为新元素值
f?head
p?f->next
main()
{
struct Lnode *head； //定义头指针
head=NULL； //置为空表
scanf(“%d”,&e)； //输入整数
while (e!=0)； //不为 0，未结束
{
head=creat3_1(head,e); //插入 递增有序单链表
scanf(“%d”,&e)； //输入整数
}
}
p!=NULL&&
e>p->data
真插入算法返回
head->next?p
p?q
p->next?p
head?q
假
f?q->next
q?f->next
带头结点算法
new(f) e?f->data
例 2 生成带头结点的 递增有序单链表 。 (不包括 0）
算法：
void creat3_2(struct Lnode *head,int e)
{ q=head； p=head->next； //q,p扫描,查找插入位置
while (p && e>p->data) //未扫描完,且 e大于当前结点
{ q=p； p=p->next； //q,p后移,查下一个位置
}
f=(struct Lnode *)malloc(LENG)； //生成新结点
f->data=e； //装入元素 e
f->next=p； q->next=f； //插入新结点
}
main()
{
head=(struct Lnode *)malloc(LENG)； //生成表头结点
head->next=NULL； //置为空表
scanf(“%d”,&e)； //输入整数
while (e!=0)； //不为 0，未结束
{
creat3_2(head,e); //插入 递增有序单链表 head
scanf(“%d”,&e)； //输入整数
}
}
(3) 在单链表中 删除 一个结点例 q p
↘ data next ↘ next
..,----→ A ------→ B -----→ C ----→,..
删除 B
执行,q->next=p->next； //A的 next域 =C的地址 (B的 next域 )
q p
↘ data next ↘ next
..,----→ A B -----→ C ----→,..
执行,free(p)； //释放 p所指向的结点空间
q p
↘ data next
..,----→ A C ----→,.,
算法：在带表头结点的单链表中 删除元素为 e的结点
struct Lnode *delet_e(struct Lnode *head,int e)
//head为头指针，删除结点 e
{ struct Lnode *q,*p；
q=head； p=head->next； //q,p扫描
while (p && p->data!=e) //查找元素为 e的结点
{ q=p； //记住前一个结点
p=p->next； //查找下一个结点
}
if (p) //有元素为 e的结点
{ q->next=p->next； //删除该结点
free(p)； //释放结点所占的空间
}
return head； //返回头头指针
}
(4) 将两个有序单链表 La和 Lb合并 为有序单链表 Lc:
例,pa
↘
La -→ // → 2 → 5 ∧
pb
↘
Lb -→ // → 3 → 8 → 20 ∧
pc
↘
Lc -→ // → 2 → 3 → 5 → 8 → 20 ∧
算法：
void merge(La,Lb,Lc)
struct Lnode *La,*Lb,**Lc；
{ struct Lnode *pa,*pb,*pc；
pa=La->next； //pa指向表 La的首结点
pb=Lb->next； //pb指向表 Lb的首结点
pc=*Lc=La； //使用表 La的头结点,pc为尾指针
free(Lb)； //释放表 Lb的头结点
while (pa && pb) //表 La表 Lb均有结点
if (pa->data<=pb->data) //取表 La的一个结点
{ pc->next=pa； //插在表 Lc的尾结点之后
pc=pa； //变为表 Lc新的尾结点
pa=pa->next； //移向表 La下一个结点
}
else //取表 Lb的一个结点
{ pc->next=pb； //插在表 Lc的尾结点之后
pc=pb； //变为表 Lc新的尾结点
pb=pb->next； //移向表 Lb下一个结点
}
if (pa) pc->next=pa； //插入表 La的剩余段
else pc->next=pb； //插入表 Lb的剩余段
}
A12(x)=1+3x5-7x12
// -1A 1 0 3 5 7 12 ^
B17 (x) =6+3x3 -3x5+12x17
// -1B 6 0 3 3 -3 5 12 17 ^
pa
pb
coef expn next
多项式的链表表示：
// -1C 7 0 3 3 7 12 12 17 ^
pcC(x)=A(x)+B(x)
C(x)=A(x)+B(x)的算法步骤：
1。 pa,pb分别指向首元素结点，产生 C(x)的空链表,pc指向头结点；
2。 pa不为空并且 pb不为空,重复下列操作：
2-1 pa->expn等于 pb->expn
（ a） pa->coef+pb->coef不等于零,产生新结点，添加到
pc后,pc指向新结点。 pa,pb后移
（ b） pa->coef+pb->coef等于零,pa,pb后移
2-2 pa->expn小于 pb->expn：根据 pa产生新结点，添加到 pc
后,pc指向新结点 pa后移
2-3 pa->expn大于 pb->expn：根据 pb产生新结点，添加到 pc
后,pc指向新结点 pb后移
3。 pa为空，取 pb剩余结点产生新结点,pb为空，取 pa剩余结点产生新结点，
4.静态链表 ----用一维数组描述的链表例 序号 data next
0 // 1
1 A 2
2 B 3
3 C 4
4 D 5
5 E 0
6 // //
7 // //
head -→ // 1 → A 2 → B 3 → C 4 → D 5 → E 0
0 1 2 3 4 5
头指针 表头结点 首结点 尾结点
2.3.2 循环链表
1.一般形式
(1) 带表头结点的非空循环单链表
H -→ // → a1 → a2 →...→ an
头指针 表头结点 首结点 尾结点有,H->next≠H,H≠NULL
(2) 带表头结点的空循环单链表
H -→ //
头指针 表头结点有,H->next==H,H≠NULL
2.只设尾指针的循环链表
(1)非空表
/// → a1 → a2 →...→ an tail
表头结点 首结点 尾结点 尾指针有,tail指向 表尾结点
tail->data==an
tail->next 指向 表头结点
tail->next->next指向首 结点
tail->next->next->data==a1
(2) 空表
/// tail
表头结点 尾指针有,tail->next==tail
例,两循环链表首尾相连。
///// 1 4 10 17head1
///// 11 5 20head2
///// 1 4 10 17
///// 11 5 20
tail1
tail2
(1) p2=tail2->next; (2) tail2->next=tail1->next;
(3) tail1->next=p2->next; (4) free(pb); 时间复杂度,O（ 1）
p2
时间复杂度,O（ m+n）
…
…
…
…
…
…
…
…
3.循环链表算法举例例,求以 head为头指针的循环单链表的长度,
并依次输出结点的值。
算法：
int length(struct Lnode *head)
{ int leng=0； //长度变量初值为 0
struct Lnode *p；
p=head->next； //p指向首结点
while (p!=head) //p未移回到表头结点
{ printf(“%d”,p->data)； //输出
leng++； //计数
p=p->next； //p移向下一结点
}
return leng； //返回长度值
}
2.3.4 双向链表
1.双向链表 的结点结构,
prior data next
前驱 a(i-1) ←─ ai ─→ 后继 a(i+1)
结点类型定义
struct Dnode
{ ElemType data； //data为抽象元素类型
struct Dnode *prior,*next； //prior,next为指针类型
}；
或者
typedef struct Dnode
{ ElemType data； //data为抽象元素类型
struct Dnode *prior,*next； //prior,next为指针类型
}*DLList //DLList为指针类型
2.双向链表的一般形式
(1)非空表
prior data next
L ─→ // ─→ ∧ a1 ─→ a2 ─→,..─→ an ∧
表头结点 首结点 尾结点有,L为头指针,L指向表头结点,L->next指向首结点
L->next->data==a1
L->prior指向尾结点,L->prior->data==an
L->next->prior== L->prior->next==NULL
(2)空表
L ─→ ∧ // ∧
表头结点有,L->next==L->prior==NULL
3.双向循环链表
(1)空表
L ─→ // 有,L->next==L->prior==L
表头结点
(2)非空表
prior data next
L ─→ // ─→ a1 ─→,.,─→ an
表头结点 p 尾结点设 p指向 a1,有：
p->next指向 a2,p->next->prior指向 a1,
所以,p==p->next->prior
同理,p==p->prior->next
3.已知指针 p指向结点 B，删除 B
p
..,──→ A ──→ B ──→ C ──→,..
执行：
p->prior->next=p->next； //结点 A的 next指向结点 C
p->next->prior=p->prior； //结点 C的 prior指向结点 A
free(p)； //释放结点 A占有的空间得,p
..,──→ A C ──→,..
4.已知指针 p指向结点 C，在 A,C之间插入结点 B
P
..,──→ A ─────→ C ──→,..
f ──→ B
执行：
① f->prior=p->prior； //结点 B的 prior指向结点 A
② f->next=p； //结点 B的 next指向结点 C
③ p->prior->next=f； //结点 A的 next指向结点 B
④ p->priot=f； //结点 C的 prior指向结点 B
得：
..,──→ A C ──→,..
① ②③ ④
B
作业
1.已知指针 p指向结点 A，在 A,C之间插入结点 B，写出 要执行的操作：
P
… ──→ A ─────→ C ──→,..
f ──→ B
2.试比较单链表、双链表、循环链表的优、缺点。
3.线性表的存储结构在什么情况下,使用顺序结构？
为什么？
在什么情况下,使用链表结构？为什么？
上机作业：
1.输入一个数列（以回车为结束标志），生成,先进先出,
单链表，再输出表中的各个结点，求表的长度值、表中结点的最大值和最小值。
2.输入一个数列（以回车为结束标志），生成,后进先出,
单链表，再输出表中的各个结点，求表的长度值。
3.输入一个数列（以回车为结束标志），生成,递增有序,
单链表，再输出表中的各个结点，求表的长度值。
4.输入两个数列（以回车为结束标志），分别生成,递增有序,单链表，再合并为一个,递增有序,单链表，输出表中的各个结点，求表的长度值。
5.输入一个数列（以回车为结束标志），生成,递增有序,
单链表，输出表中的各个结点；再逆置为,递减有序,单链表，
输出表中的各个结点。
------------------------------------------------
2001-3-12
2.3 线性表的链式存储结构
2.3.1单链表
1 单链表的结点结构,
data next
前驱 a(i-1) ─→ a i ─→ 后继 a(i+1)
结点类型说明例 1 C语言的,结构,类型,
struct node
{ ElemType data； //data为抽象元素类型
struct node *next； //next为指针类型
}；
指向结点的指针变量 head,p,q说明,
struct node *head,*p,*q；
例 2 用 typedef定义指针类型,
typedef struct Lnode
{ ElemType data； //data为抽象元素类型
struct node *next； //next为指针类型
} *Linklist；
指针变量 head,p,q的说明,
Linklist head,p,q；
2.单链表的一般形式,
(1)不带表头结点的单链表,
data next
head ---→ a1 ---→ a2 --→,.,--→ an ∧
头指针 首结点 尾结点其中,data称为数据域,next称为指针域 /链域当 head==NULL,为空表；否则为非空表
(2)带表头结点的单链表,
a.非空表,
data next
head ---→ /// --→ a1 --→..,--→ an ∧
头指针 表头结点 首结点 尾结点
b.空表,
data next
head ---→ /// ∧
头指针 表头结点其中,head指向表头结点，
head->data不放元素，
head->next指向首结点 a1,
当 head->next==NULL,为空表；否则为非空表。
3.单链表操作和算法举例：
(1) 生成单链表 。
例 1 输入一列整数，以 0为结束标志,生成,先进先出,单链表。
若输入,2,8,5,0，则生成：
tail
↓
head -→ /// --→ 2 --→ 8 --→ 5 --→ 0 ∧
#define NULL 0 //定义符号常量 NULL
#define LENG sizeof(struct Lnode) //结点所占的单元数
struct Lnode //定义结点类型
{ int data； //data为整型
struct node *next； //next为指针类型
}；
//// ^初始化,head ////输入 2,head
tail tail
2 ^
p
①
③
②
每次输入新元素后：
生成新结点； p=malloc(结点大小） ; p->data=e; p->next=NULL;
② 添加到表尾； tail->next=p;
③ 设置新表尾。 tail=p;
////head
tail
8 ^
①
③
②
2输入 8：
p
先进先出表的产生过程 (1,2,3,4,0)：
head
p
/// 1 2 3 4 0
p p p p
头指针 头结点
tail
head=malloc(sizeof(struct node))
tail=head
tail
p=malloc(sizeof(struct node))
tail->next=p
tail=p
p=malloc(sizeof(struct node))
tail
tail->next=p
tail=p
tail tail tail
tail->next=NULL;
^
算法：生成,先进先出,单链表（ 链式队列 ）
struct Lnode *creat1( )
{ struct Lnode *head,*tail,*p； //变量说明
int e；
head=(struct Lnode *)malloc(LENG)； //生成表头结点
tail=head； //尾指针指向表头
do{ p=(struct Lnode *)malloc(LENG)； //生成新结点
scanf(“%d”,&e)； //输入一个数
p->data=e； //装入输入的元素 e
tail->next=p； //新结点链接到表尾
tail=p； //尾指针指向新结点
}
while (e!=0)； //不为 0
tail->next=NULL； //尾结点的 next置为空指针
return head； //返回头指针
}
例 2 生成,后进先出,单链表 (链式栈 )。输入,2,8,5,0,生成：
head --→ /// --→ 0 --→ 5 --→ 8 --→ 2 ∧
算法：
struct Lnode *creat2( ) //生成,后进先出,单链表
{ struct Lnode *head,*p；
head=(struct Lnode *)malloc(LENG)； //生成表头结点
head->next=NULL； //置为空表
do
{ p=(struct Lnode *)malloc(LENG)； //生成新结点
scanf(“%d”,&(p->data))； //输入数,送新结点的 data
p->next=head->next； //新结点插入表头结点之后
head->next=p； //尾指针指向新结点
} while (p->data!=0)； //不为 0
return head； //返回头指针
}
//// ^初始化,head ////输入 2,head 2 ^
p
①
②
每次输入新元素后：
生成新结点； p=malloc(结点大小） ; p->data=e;
② 新结点指针指向首元素； p->next=head->next;
③ 新结点作为首元素,head->next=p;
////head 2 ^
①
②8
输入 8：
p
③
③
(2) 插入 一个结点例 1 在递增有序单链表 (0,2,5,10)中插入元素 4：
head --→ /// --→ 0 --→ 2 --→ 5 --→ 10 ∧
q ↗ ↖ p
f --→ 4
执行：
f=(struct Lnode *)malloc(LENG)； //生成新结点
f->data=4； //装入元素 4
f->next=p； //结点 5的地址送入结点 4的 next
q->next=f； //结点 4的地址送入结点 2的 next
变为：
head-→ /// -→ 0 -→ 2 -→ 4 -→ 5 -→ 10 ∧
q ↗ f ↗ p ↗
例 2 输入一列整数,以 0为结束标志,生成 递增有序单链表 。 (不包括 0）
///// 1 4 7 10 17 ^
1 4 7 10 17 ^
head
head
p!=NULL&&
e>p->data
真假插入算法返回 head
head?p
p?q
p->next?p
NULL?q new(f) e?f->data
p==NULL
p==headhead==NULL
假 真
f?head f?q->next
NULL?f->next
f?q->next
q?f->next
p?f->next
f?head
假假真 真
① ② ③ ④
① 空表插入；
② 尾部插入；
③ 首部插入；
④ 一般插入。
e为新元素值不带头结点算法例 2 生成不带头结点的 递增有序单链表 。 (不包括 0）
struct Lnode * creat3_1(struct Lnode *head,int e)
{ q=NULL； p=head； //q,p扫描,查找插入位置
while (p && e>p->data) //未扫描完,且 e大于当前结点
{ q=p； p=p->next； } //q,p后移,查下一个位置
f=(struct Lnode *)malloc(LENG)； //生成新结点
f->data=e； //装入元素 e
if (p==NULL){
f->next=NULL;
if (head=NULL) //(1)对空表的插入
head=f;
else q->next=f;} //(2)作为最后一个结点插入
else if (q==NULL) //(3)作为第一个结点插入
{f->next=p; head=f;}
else
{f->next=p； q->next=f； } //(4)一般情况插入新结点
return head;
}
p!=NULL&&
e>p->data
真假插入算法返回 head
head?p
p?q
p->next?p
NULL?q new(f) e?f->data
q==NULL
假 真
NULL?f->next
f?q->next
① ②
① 作为第一元素或首元素插入；
②一般插入或作为尾元素插入；
e为新元素值
f?head
p?f->next
main()
{
struct Lnode *head； //定义头指针
head=NULL； //置为空表
scanf(“%d”,&e)； //输入整数
while (e!=0)； //不为 0，未结束
{
head=creat3_1(head,e); //插入 递增有序单链表
scanf(“%d”,&e)； //输入整数
}
}
p!=NULL&&
e>p->data
真插入算法返回
head->next?p
p?q
p->next?p
head?q
假
f?q->next
q?f->next
带头结点算法
new(f) e?f->data
例 2 生成带头结点的 递增有序单链表 。 (不包括 0）
算法：
void creat3_2(struct Lnode *head,int e)
{ q=head； p=head->next； //q,p扫描,查找插入位置
while (p && e>p->data) //未扫描完,且 e大于当前结点
{ q=p； p=p->next； //q,p后移,查下一个位置
}
f=(struct Lnode *)malloc(LENG)； //生成新结点
f->data=e； //装入元素 e
f->next=p； q->next=f； //插入新结点
}
main()
{
head=(struct Lnode *)malloc(LENG)； //生成表头结点
head->next=NULL； //置为空表
scanf(“%d”,&e)； //输入整数
while (e!=0)； //不为 0，未结束
{
creat3_2(head,e); //插入 递增有序单链表 head
scanf(“%d”,&e)； //输入整数
}
}
(3) 在单链表中 删除 一个结点例 q p
↘ data next ↘ next
..,----→ A ------→ B -----→ C ----→,..
删除 B
执行,q->next=p->next； //A的 next域 =C的地址 (B的 next域 )
q p
↘ data next ↘ next
..,----→ A B -----→ C ----→,..
执行,free(p)； //释放 p所指向的结点空间
q p
↘ data next
..,----→ A C ----→,.,
算法：在带表头结点的单链表中 删除元素为 e的结点
struct Lnode *delet_e(struct Lnode *head,int e)
//head为头指针，删除结点 e
{ struct Lnode *q,*p；
q=head； p=head->next； //q,p扫描
while (p && p->data!=e) //查找元素为 e的结点
{ q=p； //记住前一个结点
p=p->next； //查找下一个结点
}
if (p) //有元素为 e的结点
{ q->next=p->next； //删除该结点
free(p)； //释放结点所占的空间
}
return head； //返回头头指针
}
(4) 将两个有序单链表 La和 Lb合并 为有序单链表 Lc:
例,pa
↘
La -→ // → 2 → 5 ∧
pb
↘
Lb -→ // → 3 → 8 → 20 ∧
pc
↘
Lc -→ // → 2 → 3 → 5 → 8 → 20 ∧
算法：
void merge(La,Lb,Lc)
struct Lnode *La,*Lb,**Lc；
{ struct Lnode *pa,*pb,*pc；
pa=La->next； //pa指向表 La的首结点
pb=Lb->next； //pb指向表 Lb的首结点
pc=*Lc=La； //使用表 La的头结点,pc为尾指针
free(Lb)； //释放表 Lb的头结点
while (pa && pb) //表 La表 Lb均有结点
if (pa->data<=pb->data) //取表 La的一个结点
{ pc->next=pa； //插在表 Lc的尾结点之后
pc=pa； //变为表 Lc新的尾结点
pa=pa->next； //移向表 La下一个结点
}
else //取表 Lb的一个结点
{ pc->next=pb； //插在表 Lc的尾结点之后
pc=pb； //变为表 Lc新的尾结点
pb=pb->next； //移向表 Lb下一个结点
}
if (pa) pc->next=pa； //插入表 La的剩余段
else pc->next=pb； //插入表 Lb的剩余段
}
A12(x)=1+3x5-7x12
// -1A 1 0 3 5 7 12 ^
B17 (x) =6+3x3 -3x5+12x17
// -1B 6 0 3 3 -3 5 12 17 ^
pa
pb
coef expn next
多项式的链表表示：
// -1C 7 0 3 3 7 12 12 17 ^
pcC(x)=A(x)+B(x)
C(x)=A(x)+B(x)的算法步骤：
1。 pa,pb分别指向首元素结点，产生 C(x)的空链表,pc指向头结点；
2。 pa不为空并且 pb不为空,重复下列操作：
2-1 pa->expn等于 pb->expn
（ a） pa->coef+pb->coef不等于零,产生新结点，添加到
pc后,pc指向新结点。 pa,pb后移
（ b） pa->coef+pb->coef等于零,pa,pb后移
2-2 pa->expn小于 pb->expn：根据 pa产生新结点，添加到 pc
后,pc指向新结点 pa后移
2-3 pa->expn大于 pb->expn：根据 pb产生新结点，添加到 pc
后,pc指向新结点 pb后移
3。 pa为空，取 pb剩余结点产生新结点,pb为空，取 pa剩余结点产生新结点，
4.静态链表 ----用一维数组描述的链表例 序号 data next
0 // 1
1 A 2
2 B 3
3 C 4
4 D 5
5 E 0
6 // //
7 // //
head -→ // 1 → A 2 → B 3 → C 4 → D 5 → E 0
0 1 2 3 4 5
头指针 表头结点 首结点 尾结点
2.3.2 循环链表
1.一般形式
(1) 带表头结点的非空循环单链表
H -→ // → a1 → a2 →...→ an
头指针 表头结点 首结点 尾结点有,H->next≠H,H≠NULL
(2) 带表头结点的空循环单链表
H -→ //
头指针 表头结点有,H->next==H,H≠NULL
2.只设尾指针的循环链表
(1)非空表
/// → a1 → a2 →...→ an tail
表头结点 首结点 尾结点 尾指针有,tail指向 表尾结点
tail->data==an
tail->next 指向 表头结点
tail->next->next指向首 结点
tail->next->next->data==a1
(2) 空表
/// tail
表头结点 尾指针有,tail->next==tail
例,两循环链表首尾相连。
///// 1 4 10 17head1
///// 11 5 20head2
///// 1 4 10 17
///// 11 5 20
tail1
tail2
(1) p2=tail2->next; (2) tail2->next=tail1->next;
(3) tail1->next=p2->next; (4) free(pb); 时间复杂度,O（ 1）
p2
时间复杂度,O（ m+n）
…
…
…
…
…
…
…
…
3.循环链表算法举例例,求以 head为头指针的循环单链表的长度,
并依次输出结点的值。
算法：
int length(struct Lnode *head)
{ int leng=0； //长度变量初值为 0
struct Lnode *p；
p=head->next； //p指向首结点
while (p!=head) //p未移回到表头结点
{ printf(“%d”,p->data)； //输出
leng++； //计数
p=p->next； //p移向下一结点
}
return leng； //返回长度值
}
2.3.4 双向链表
1.双向链表 的结点结构,
prior data next
前驱 a(i-1) ←─ ai ─→ 后继 a(i+1)
结点类型定义
struct Dnode
{ ElemType data； //data为抽象元素类型
struct Dnode *prior,*next； //prior,next为指针类型
}；
或者
typedef struct Dnode
{ ElemType data； //data为抽象元素类型
struct Dnode *prior,*next； //prior,next为指针类型
}*DLList //DLList为指针类型
2.双向链表的一般形式
(1)非空表
prior data next
L ─→ // ─→ ∧ a1 ─→ a2 ─→,..─→ an ∧
表头结点 首结点 尾结点有,L为头指针,L指向表头结点,L->next指向首结点
L->next->data==a1
L->prior指向尾结点,L->prior->data==an
L->next->prior== L->prior->next==NULL
(2)空表
L ─→ ∧ // ∧
表头结点有,L->next==L->prior==NULL
3.双向循环链表
(1)空表
L ─→ // 有,L->next==L->prior==L
表头结点
(2)非空表
prior data next
L ─→ // ─→ a1 ─→,.,─→ an
表头结点 p 尾结点设 p指向 a1,有：
p->next指向 a2,p->next->prior指向 a1,
所以,p==p->next->prior
同理,p==p->prior->next
3.已知指针 p指向结点 B，删除 B
p
..,──→ A ──→ B ──→ C ──→,..
执行：
p->prior->next=p->next； //结点 A的 next指向结点 C
p->next->prior=p->prior； //结点 C的 prior指向结点 A
free(p)； //释放结点 A占有的空间得,p
..,──→ A C ──→,..
4.已知指针 p指向结点 C，在 A,C之间插入结点 B
P
..,──→ A ─────→ C ──→,..
f ──→ B
执行：
① f->prior=p->prior； //结点 B的 prior指向结点 A
② f->next=p； //结点 B的 next指向结点 C
③ p->prior->next=f； //结点 A的 next指向结点 B
④ p->priot=f； //结点 C的 prior指向结点 B
得：
..,──→ A C ──→,..
① ②③ ④
B
作业
1.已知指针 p指向结点 A，在 A,C之间插入结点 B，写出 要执行的操作：
P
… ──→ A ─────→ C ──→,..
f ──→ B
2.试比较单链表、双链表、循环链表的优、缺点。
3.线性表的存储结构在什么情况下,使用顺序结构？
为什么？
在什么情况下,使用链表结构？为什么？
上机作业：
1.输入一个数列（以回车为结束标志），生成,先进先出,
单链表，再输出表中的各个结点，求表的长度值、表中结点的最大值和最小值。
2.输入一个数列（以回车为结束标志），生成,后进先出,
单链表，再输出表中的各个结点，求表的长度值。
3.输入一个数列（以回车为结束标志），生成,递增有序,
单链表，再输出表中的各个结点，求表的长度值。
4.输入两个数列（以回车为结束标志），分别生成,递增有序,单链表，再合并为一个,递增有序,单链表，输出表中的各个结点，求表的长度值。
5.输入一个数列（以回车为结束标志），生成,递增有序,
单链表，输出表中的各个结点；再逆置为,递减有序,单链表，
输出表中的各个结点。
