,数据结构,
第二章
数据结构
tjm
第二章 线性表
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
数据结构
tjm
线性结构是,一个数据元素的有序集。
线性结构的基本特征：
在数据元素的非空有限集合中，
1、存在 唯一的 一个被称做“第一个”的数据元素
2、存在 唯一的 一个被称做“最后一个”的数据元
素
3、除第一个之外，集合中的每个数据元素均 只有
一个前驱
4、除最后一个之外，集合中每个数据元素均 只有
一个后继
例 1,26个英文字母组成的字母表（ A,B，
C,…,Z）
数据结构
tjm
例 2,学生健康情况登记表如下：
姓 名 学 号 性别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
((王小林,790631、男,18、健康 )，
(陈 红,790632、女,20、一般 ),… )
数据结构
tjm
线性表 (Linear List), 由 n(n≧ 0)个数据元
素 (结点 )a1,a2,…,an组成的有限序列。其
中数据元素的个数 n定义为表的长度。当 n=0
时称为空表，常常将非空的线性表 (n>0)记作：
(a1,a2,…,an)
这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符
号，其具体含义在不同的情况下可以不同。
2.1 线性表的类型定义
数据结构
tjm
线性表的 逻辑特征 是：
在 非空的线性表 中，有且仅有一个开始结点 a1，
它没有直接前趋，而仅有一个直接后继 a2；有
且仅有一个终端结点 an，它没有直接后继，而
仅有一个直接前趋 an-1；其余的内部结点
ai(2≦ i≦ n-1)都有且仅有一个直接前趋 a i-1
和一个直接后继 ai+1。
结论,线性表是一种典型的线性结构。
数据的运算 是定义在逻辑结构上的，而运算的具
体实现则是在存储结构上进行的。
线性表的 抽象数据类型的定义,P19
数据结构
tjm
例 2-1 利用两个线性表 LA和 LB分别表示两个集合 A
和 B（即线性表中的数据元素即为集合中的成员），
现要求一个新的集合 A=A∪ B。
void union(List &La,List Lb)
{ La_len=ListLength(La);
Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++)
{ GetElem(Lb,i,e);
if(!LocateElem(La,e,equal))
ListInsert(la,++La_len,e)
}
}
数据结构
tjm
扩展 1,利用两个线性表 LA和 LB分别表示两个集合
A和 B，现要求一个新的集合 A=A∩ B。
void JiHeJiao(List &La,List Lb)
{ La_len=ListLength(La);
Lb_len=ListLength(Lb);
for(i=1;i<=La_len;i++)
{ GetElem(La,i,e);
if(!LocateElem(Lb,e,equal))
{ ListDelete(la,i,e);
--i; --La_len;
}
}
}
数据结构
tjm
例 2-2 已知线性表 LA和线性表 LB中的数据元素按
值非递减有序排列，现要求将 LA和 LB归并为一
个新的线性表 LC，且 LC中的元素仍按值非递减
有序排列。 此问题的算法如下：
void MergeList(List La,List Lb,List
&Lc)
{ InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);
Lb_len=ListLength(Lb);
while((i<=La_len)&&(j<=Lb_len))
{
数据结构
tjm
GetElem(La,i,ai);getElem(Lb,j,bj);
if(ai<=bj)
{ ListInsert(Lc,++k,ai);++i; }
else { ListInsert(Lc,++k,bj);++j; }
}
while(i<=La_len)
{ GetElem((La,i++,ai);
ListInsert(Lc,++k,ai); }
while(j<=Lb_len)
{ GetElem((Lb,j++,bj);
ListInsert(Lc,++k,bj); }
}
数据结构
tjm
2.2 线性表的顺序表示和实现
2.2.1 顺序存储的线性表 (Sequential Lists)
把线性表的结点 按逻辑顺序依次存放在一组
地址连续的存储单元 里。用这种方法存储的线性
表简称 顺序表 。线性表的起始地址称作线性表的
基地址。
假设线性表的每个元素需占用 L个存储单元，
则线性表中第 i+1个数据元素的存储位置
LOC( ai+1)和第 i个数据元素的存储位置 LOC(ai)
之间满足下列关系：
LOC(ai+1)=LOC(ai)+ L
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)* L
数据结构
tjm
a1
a2
…
ai
…
an
例：有一线性表为：
(a1,a2,…,a i,…,a n)
由于 C语言中的一维数
组也是采用顺序存储表
示，故可以用数组类型
来描述顺序表。
b
b+L
…
b+(i-1)L
…
b+(n-1)L
b+nL
a[0]
a[1]
…
a[i-1]
…
a[n-1]
数据结构
tjm
线性表的顺序存储的 c语言描述：
# define List_Init_Size 100
typedef LISTINCREMENT 10;
typedef struct
{ ElemType *elem;
int length;
int listsize;
} Sqlist;
数据结构
tjm
2.2.2 顺序表上实现的基本操作
线性表的初始化操作 InitList(&L)
Status InitList_Sq(SqList &L){
L.elem=(ElemType
*)malloc(LIST_INIT_SIZE
*sizeof(ElemType));
If(!L.elem) exit(OVERFLOW);
L.length=0;
L.Listsize=LIST_INIT_SIZE;
return ok;
}//InitList_Sq
数据结构
tjm
以下主要讨论线性表的插入和删除两种运算。
1、插入
线性表的插入运算是指在表的第
i(1≦ i≦ n+1)个位置上，插入一个新结点 x，使
长度为 n的线性表
(a1,…,a i-1,ai,…,an)
变成长度为 n+1的线性表
(a1,…,a i-1,x,ai,…,an)
线性表的查找操作：
LocateElem(L,e,compare())
算法参见 P25。
数据结构
tjm
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4]
王五
数据结构
tjm
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4] 王五
数据结构
tjm
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
数据结构
tjm
王一
赵二
李四
张三
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
数据结构
tjm
问题规模是表的长度，设它的值为 n。
该算法的时间主要花费在循环的结点后移语句上，
移动结点的次数 是 n-i+1。依赖于表的长度与插
入位置。
当 i=n+1时，结点后移语句将不进行；
这是最好情况，其时间复杂度 O（ 1）；
当 i=1时,需移动表中所有结点，即 n次。
这是最坏情况，其时间复杂度为 O（ n）。
插入算法 ListInsert(&L,i,e)的实现 （参见 P24）。
分析算法的复杂度：
数据结构
tjm
王一
赵二
李四
张三
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二,张三,李四，
王五 )
现要变为：
(王一，赵二，李四，王五 )
数据结构
tjm
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二,张三,李四，
王五 )
现要变为：
(王一，赵二，李四，王五 )
数据结构
tjm
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4]
王五
例：有一线性表为：
(王一，赵二,张三,李四，
王五 )
现要变为：
(王一，赵二，李四，王五 )
数据结构
tjm
删除算法 ListInsert(&L,i,&e)的实现 （参见 P24）。
该算法的时间分析与插入算法相似,结点的移动次数
也是由表长 n和位置 i决定。
若 i=n，无需移动结点；
若 i=1，则前移语句将循环执行 n-1次。
两种情况下算法的时间复杂度分别为 O(1)和 O(n)。
删除算法的平均性能分析：在长度为 n的线性表
中删除一个结点，令 Edl(n)表示所需移动结点的平
均次数,pi表示删除表中第 i个结点的概率。删除表
中第 i个结点的移动次数为 n-i，故
Edl(n)= (n-i) pi
数据结构
tjm
在等概率的假设下，
p1=p2=p3=…=pn=1/n
由此可得：
Edl(n)= (n-i)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约一半
的结点，平均时间复杂度也是 O(n)。
小结：
1、在顺序表上插入、删除一个结点，需要移动大量
元素。
2、具有随机访问的特点。
数据结构
tjm
2.3 线性表的链式表示和实现
线性表的顺序表示的 特点 是 用物理位置上的邻接
关系来表示结点间的逻辑关系,这一特点使我们
可以随机存取表中的任一结点，但它也使得 插入
和删除操作会移动大量的结点,
为避免大量结点的移动，介绍线性表的另一种存
储方式,链式存储结构,简称为 链表。
数据结构
tjm
2.3.1 线性链表
链表 是 指用一组任意的存储单元来依次存放线性
表的结点,这组存储单元即可以是连续的，也可
以是不连续的，甚至是零散分布在内存中的任意
位置上的。因此，链表中结点的逻辑次序和物理
次序不一定相同。为了能正确表示结点间的逻辑
关系，在存储每个结点值的同时，还必须存储指
示其后继结点的地址（或位置）信息，这个信息
称为指针或链。这两部分组成了链表中的结点结
构：
data next
数据结构
tjm
其中,data域是数据域,用来存放结点的值。
next是指针域 （亦称链域），用来存放结点的直
接后继的地址（或位置）。由于上述链表的每一个
结只有一个链域，故将这种链表称为 单链表 。
开始结点无前趋，应设头指针 head指向开始结点。
终端结点无后继，终端结点的指针域为空，即 NULL
（ 图示中也可用 ^表示 )。
数据结构
tjm
例 1、线性表,
(bat,cat,eat,fat，
hat,jat,lat,mat)
单
链
表
示
意
图
……… ……
hat 200
……,……
cat 135
eat 170
…,……
mat Null
bat 130
fat 110
…… ……
jat 205
lat 160
…… ……
165
……
110
……
130
135
……
160
165
170
……
200
205
……
头指针 head
数据结构
tjm
head
bat cat eat mat ^…
单链表是由表头唯一确定，因此单链表可以用头指
针的名字来命名。
例如：若头指针名是 head，则把链表称为表 head
用 C语言描述的单链表如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
数据结构
tjm
假设 p为指向结点的指针变量，则它通过标准函数
生成的，即
p=(LNode*)malloc(sizeof(LNode));
函数 malloc分配了一个类型为 LNode的结点变
量的空间，并将其首地址放入指针变量 p中。一旦
p所指的结点不再需要了，又可通过标准函数
free(p)释放所指的结点空间。
注意：三个概念：
头结点的概念
头指针
首元结点
数据结构
tjm
单链表的基本操作：
一、查找运算
1、在单链表中，即使知道被访问结点的序号 i，
也不能象顺序表中那样直接按序号 i访问结点，
而只能从单链表的头指针出发，顺链域 next逐
个结点往下搜索，直到搜索到第 i个结点为止。
因此，链表不是随机存取结构。
设单链表的长度为 n，要查找表中第 i个结点，
仅当 1<=i<=n时,i的值是合法的。
其算法参见 P29
? ? ? ?nOnT ??
算法的平均时间复杂度：
数据结构
tjm
a b
步骤 1,生成一个数据域为 x的结点。
p
xs
data next
在线性表的两个数据元素 a和 b之间插入一个
数据元素 x，已知 p为其单链表存储结构中指向
结点 a的指针。
二、单链表的插入
数据结构
tjm
用 C语句描述为：
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
数据结构
tjm
a b
步骤 2,将数据元素 x插在 a和 b元素之间。
p
xs
data next
数据结构
tjm
a bp
xs
data next
步骤 2,将数据元素 x插在 a和 b元素之间。
数据结构
tjm
a b
步骤 2,将数据元素 x插在 a和 b元素之间。
p
xs
data next
数据结构
tjm
a b
用 C语言描述为：
s->next = p->next;
p->next = s;
p
xs
data next
数据结构
tjm
a bp
xs
data next
即：
p->next = s;
s->next = p->next;
注意语句的顺序，如改为以下顺序，什么
情况会发生？
b结点的地址？
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
…
ai-1 ai…p
j = 0
a1
an^
L
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
…
ai-1 ai…
j = 1
a1
an^
pL
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
p
j = …
…
ai-1 ai…a1
an^
L
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
j = i-1
…
ai-1 ai…a1
an^
pL
数据结构
tjm
…
ai-1 ai…a1
an^
p
es
L
关键语句：
s=(LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
其算法参见 P29
数据结构
tjm
删除元素 b：
a bp c
data next…
…
三、单链表的删除
数据结构
tjm
a bp c
data next…
…
删除元素 b：
三、单链表的删除
数据结构
tjm
a bp c
data next…
…
用 C语言语句描述为：
p->next=p->next->next;
删除元素 b：
三、单链表的删除
数据结构
tjm
删除元素 b并释放之：
a bp c
data next…
…
步骤 1：将 b的地址记录下来
即,q=p->next;
q
数据结构
tjm
a bp c
data next…
…
删除元素 b并释放之：
步骤 2：让 p->next指向 b后第一个结点
即,p->next=q->next;
q
数据结构
tjm
a bp c
data next…
…
删除元素 b并释放之：
q
步骤 3：释放 b结点
即,free(q)
数据结构
tjm
ap c
data next…
…
删除元素 b并释放之：
b
q
步骤 3：释放 b结点
即,free(q)
其算法参见 P30
数据结构
tjm
四、单链表的建立（头插法）
动态建立单链表算法,设线性表 n个元素已存
放在数组 a中，建立一个单链表,L为头指针 。
L
头结点
an ^
L
头结点
^
数据结构
tjm
? ? ? ?nOnT ?
L
头结点
an-1 an ^
a2 …...L
头结点
an-1 an ^
L a1 a2
头结点
an ^…...
……
其算法参见 P30
数据结构
tjm
小结
3、链式存储的优点,插入删除效率高
4、链式存储的缺点,访问某个数据效率低
1、在单链表上插入、删除一个结点，必须知道其前
驱结点。
2、单链表不具有按序号随机访问的特点，只能从
头指针开始一个个顺序进行。
数据结构
tjm
2.3.2 循环链表
循环链表是一种头尾相接的链表。其 特点 是
无需增加存储量，仅对表的链接方式稍作改变，
即可使得表处理更加方便灵活。
单循环链表,在单链表中，将终端结点的指针
域 NULL改为指向第一个结点，就得到了单链
形式的循环链表，并简称为单循环链表。
循环链表中也可设置一个 头结点 。这样，空循
环链表仅有一个自成循环的头结点表示。如下
图所示：
数据结构
tjm
a1 an….head
⑴ 非空表
⑵ 空表
数据结构
tjm
在用头指针表示的单链表中，找开始结点 a1的时间
是 O(1)，然而要找到终端结点 an，则需从头指针
开始遍历整个链表，其时间是 O(n)。在很多实际
问题中，表的操作常常是在表的首尾位置上进行，
此时头指针表示的单循环链表就显得不够方便,如果
改用 尾指针 rear来表示单循环链表，则查找开始结
点 a1和终端结点 an都很方便，它们的存储位置分别
是 (rear–>next) —>next和 rear，显然，查
找时间都是 O(1)。因此，实际中多采用尾指针表
示单循环链表。
由于循环链表中没有 NULL指针，故涉及遍历操
作时，其终止条件就不再像非循环链表那样判断 p
或 p—>next是否为空，而是判断它们是否等于某
一指定指针。
数据结构
tjm
2.3.3 双向链表
双向链表,在单链表的每个结点里再增加一个
指向其直接前趋的指针域 prior。这样形成的
链表中有两个方向不同的链,故称为 双向链
表 。形式描述为：
typedef struct DulNode{
ElemType data; 数据域
struct DulNode *prior;
指向前驱元素的指针
struct DulNode *next;
指向后继元素的指针
} DulNode,*DuLinkList;
数据结构
tjm
设指针 p指向某一结点，则有：
(p—>prior)—>next=p
=(p—>next)—>prior
即结点 *p的存储位置既存放在其前趋结点
*(p—>prior)的直接后继指针域中，也存放 在
它的后继结点 *(p—>next)的直接前趋指针域
中。 a1 a
n….head
⑴ 非空表
^
^
⑵ 空表
^
^ 双向链表
数据结构
tjm
a b
x
p
q
在 p所指结点前插入值为 x的结点，
应怎样修改指针？
q= (DulNode *) malloc(sizeof(DulNode));
q—>data=x;
q—>prior=p—>prior;
q—>next=p;
p—>prior—>next=q;
p—>prior=q;
数据结构
tjm
a b
p
c
双向链表中删除结点 p,应怎样修改指针？
p–>prior–>next=p–>next;
p–>next–>prior=p–>prior;
free(p);
注意：与单链表的插入和删除操作不同的是，在双
链表中插入和删除必须同时修改两个方向上的指针。
上述两个算法的时间复杂度均为 O(1)。
数据结构
tjm
2.4 一元多项式的表示及相加
因此一元多项式：
Pm(x)=p1xe1+ p2xe2+ …...+pmxem
可用线性表：
((p1,e1),(p2,e2),……(pm,em)) 表示
一元多项式：
Pm(x)=p1xe1+ p2xe2+ …...+pmxem
可用系数线性表 P表示,p=(p1,p2,… pm)
但对 S (x) = 1 + 3 x 1000 + 2 x 2000 这样的多项式
浪费空间 系数线性表 ( 1,0,…0,3,0,…0,2)
可用非零系数指数线性表, ((1,0),(3,1000),
(2,2000))
数据结构
tjm
例：求两多项式的和多项式
A (x) = 7 +3 x + 9 x 8 + 5 x 17
B (x) = 8 x + 22 x 7 – 9 x 8
C (x) = A (x) + B (x) = 7 + 11x +22 x 7
+ 5 x 17
A=( (7,0),(3,1),(9,8),(5,17))
B=( (8,1),(22,7),(-9,8))
C=((7,0),(11,1),(22,7),(5,17))
数据结构
tjm
结点：
一元多项式的链式存储结构
coef exp next
抽象数据类型 Polynomial的实现 参见 P42。
h
-1 1 0 3 1000 2 2000 ∧
头结点
例,S (x) = 1 + 3 x 1000 + 2 x 2000 的
单链表存储示意图
数据结构
tjm
pa
-1 7 0 3 1 9 8 5 17 ∧
pb
-1 8 1 22 7 -9 8 ∧
pa
22 7
-1 7 0 11 1 5 17 ∧
和多项式链表：
AddPolyn算法 (类似于两个有序表的
归并，仅有一些细微差别。）
设多项式 A (x), B (x)分别用带表头结点的单链
表 pa, pb表示，和多项式仍用带表头结点的单
链表 pa表示。
数据结构
tjm
设 p,q分别指向 A,B中某一结点,p,q初值是第一结点
运算规则：
比较
p->exp
与 q->exp
p->exp < q->exp,p结点是和多项式中的一项，
p后移,q不动
p->exp > q->exp,q结点是和多项式中的一项，
将 q插在 p之前,q后移,p不动
p->exp = q->exp,系数相加
0：从 A表中删去 p,
释放 p,q； p,q
后移
?0：修改 p系数域,
释放 q； p,q
后移直到 p或 q为 NULL 若 q==NULL,结束
若 p==NULL,将 B中剩余部分连到 A上即可
数据结构
tjm
qaha
算法示意：
qb
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qaha
hb
qb
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
hb
数据结构
tjm
qb
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qaha
hb
qa
qb
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
hahb
数据结构
tjm
-1pa 7 0 11 1 22 7 5 17 ^
qb=NULL
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qa
hahb
qb=NULL
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qa
ha最后：
第二章
数据结构
tjm
第二章 线性表
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
数据结构
tjm
线性结构是,一个数据元素的有序集。
线性结构的基本特征：
在数据元素的非空有限集合中，
1、存在 唯一的 一个被称做“第一个”的数据元素
2、存在 唯一的 一个被称做“最后一个”的数据元
素
3、除第一个之外，集合中的每个数据元素均 只有
一个前驱
4、除最后一个之外，集合中每个数据元素均 只有
一个后继
例 1,26个英文字母组成的字母表（ A,B，
C,…,Z）
数据结构
tjm
例 2,学生健康情况登记表如下：
姓 名 学 号 性别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
((王小林,790631、男,18、健康 )，
(陈 红,790632、女,20、一般 ),… )
数据结构
tjm
线性表 (Linear List), 由 n(n≧ 0)个数据元
素 (结点 )a1,a2,…,an组成的有限序列。其
中数据元素的个数 n定义为表的长度。当 n=0
时称为空表，常常将非空的线性表 (n>0)记作：
(a1,a2,…,an)
这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符
号，其具体含义在不同的情况下可以不同。
2.1 线性表的类型定义
数据结构
tjm
线性表的 逻辑特征 是：
在 非空的线性表 中，有且仅有一个开始结点 a1，
它没有直接前趋，而仅有一个直接后继 a2；有
且仅有一个终端结点 an，它没有直接后继，而
仅有一个直接前趋 an-1；其余的内部结点
ai(2≦ i≦ n-1)都有且仅有一个直接前趋 a i-1
和一个直接后继 ai+1。
结论,线性表是一种典型的线性结构。
数据的运算 是定义在逻辑结构上的，而运算的具
体实现则是在存储结构上进行的。
线性表的 抽象数据类型的定义,P19
数据结构
tjm
例 2-1 利用两个线性表 LA和 LB分别表示两个集合 A
和 B（即线性表中的数据元素即为集合中的成员），
现要求一个新的集合 A=A∪ B。
void union(List &La,List Lb)
{ La_len=ListLength(La);
Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++)
{ GetElem(Lb,i,e);
if(!LocateElem(La,e,equal))
ListInsert(la,++La_len,e)
}
}
数据结构
tjm
扩展 1,利用两个线性表 LA和 LB分别表示两个集合
A和 B，现要求一个新的集合 A=A∩ B。
void JiHeJiao(List &La,List Lb)
{ La_len=ListLength(La);
Lb_len=ListLength(Lb);
for(i=1;i<=La_len;i++)
{ GetElem(La,i,e);
if(!LocateElem(Lb,e,equal))
{ ListDelete(la,i,e);
--i; --La_len;
}
}
}
数据结构
tjm
例 2-2 已知线性表 LA和线性表 LB中的数据元素按
值非递减有序排列，现要求将 LA和 LB归并为一
个新的线性表 LC，且 LC中的元素仍按值非递减
有序排列。 此问题的算法如下：
void MergeList(List La,List Lb,List
&Lc)
{ InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);
Lb_len=ListLength(Lb);
while((i<=La_len)&&(j<=Lb_len))
{
数据结构
tjm
GetElem(La,i,ai);getElem(Lb,j,bj);
if(ai<=bj)
{ ListInsert(Lc,++k,ai);++i; }
else { ListInsert(Lc,++k,bj);++j; }
}
while(i<=La_len)
{ GetElem((La,i++,ai);
ListInsert(Lc,++k,ai); }
while(j<=Lb_len)
{ GetElem((Lb,j++,bj);
ListInsert(Lc,++k,bj); }
}
数据结构
tjm
2.2 线性表的顺序表示和实现
2.2.1 顺序存储的线性表 (Sequential Lists)
把线性表的结点 按逻辑顺序依次存放在一组
地址连续的存储单元 里。用这种方法存储的线性
表简称 顺序表 。线性表的起始地址称作线性表的
基地址。
假设线性表的每个元素需占用 L个存储单元，
则线性表中第 i+1个数据元素的存储位置
LOC( ai+1)和第 i个数据元素的存储位置 LOC(ai)
之间满足下列关系：
LOC(ai+1)=LOC(ai)+ L
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)* L
数据结构
tjm
a1
a2
…
ai
…
an
例：有一线性表为：
(a1,a2,…,a i,…,a n)
由于 C语言中的一维数
组也是采用顺序存储表
示，故可以用数组类型
来描述顺序表。
b
b+L
…
b+(i-1)L
…
b+(n-1)L
b+nL
a[0]
a[1]
…
a[i-1]
…
a[n-1]
数据结构
tjm
线性表的顺序存储的 c语言描述：
# define List_Init_Size 100
typedef LISTINCREMENT 10;
typedef struct
{ ElemType *elem;
int length;
int listsize;
} Sqlist;
数据结构
tjm
2.2.2 顺序表上实现的基本操作
线性表的初始化操作 InitList(&L)
Status InitList_Sq(SqList &L){
L.elem=(ElemType
*)malloc(LIST_INIT_SIZE
*sizeof(ElemType));
If(!L.elem) exit(OVERFLOW);
L.length=0;
L.Listsize=LIST_INIT_SIZE;
return ok;
}//InitList_Sq
数据结构
tjm
以下主要讨论线性表的插入和删除两种运算。
1、插入
线性表的插入运算是指在表的第
i(1≦ i≦ n+1)个位置上，插入一个新结点 x，使
长度为 n的线性表
(a1,…,a i-1,ai,…,an)
变成长度为 n+1的线性表
(a1,…,a i-1,x,ai,…,an)
线性表的查找操作：
LocateElem(L,e,compare())
算法参见 P25。
数据结构
tjm
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4]
王五
数据结构
tjm
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4] 王五
数据结构
tjm
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
数据结构
tjm
王一
赵二
李四
张三
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二，李四，王五 )
现要变为：
(王一，赵二,张三,李四，
王五 )
数据结构
tjm
问题规模是表的长度，设它的值为 n。
该算法的时间主要花费在循环的结点后移语句上，
移动结点的次数 是 n-i+1。依赖于表的长度与插
入位置。
当 i=n+1时，结点后移语句将不进行；
这是最好情况，其时间复杂度 O（ 1）；
当 i=1时,需移动表中所有结点，即 n次。
这是最坏情况，其时间复杂度为 O（ n）。
插入算法 ListInsert(&L,i,e)的实现 （参见 P24）。
分析算法的复杂度：
数据结构
tjm
王一
赵二
李四
张三
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二,张三,李四，
王五 )
现要变为：
(王一，赵二，李四，王五 )
数据结构
tjm
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4] 王五
例：有一线性表为：
(王一，赵二,张三,李四，
王五 )
现要变为：
(王一，赵二，李四，王五 )
数据结构
tjm
王一
赵二
李四
a[0]
a[1]
a[2]
a[3]
a[4]
王五
例：有一线性表为：
(王一，赵二,张三,李四，
王五 )
现要变为：
(王一，赵二，李四，王五 )
数据结构
tjm
删除算法 ListInsert(&L,i,&e)的实现 （参见 P24）。
该算法的时间分析与插入算法相似,结点的移动次数
也是由表长 n和位置 i决定。
若 i=n，无需移动结点；
若 i=1，则前移语句将循环执行 n-1次。
两种情况下算法的时间复杂度分别为 O(1)和 O(n)。
删除算法的平均性能分析：在长度为 n的线性表
中删除一个结点，令 Edl(n)表示所需移动结点的平
均次数,pi表示删除表中第 i个结点的概率。删除表
中第 i个结点的移动次数为 n-i，故
Edl(n)= (n-i) pi
数据结构
tjm
在等概率的假设下，
p1=p2=p3=…=pn=1/n
由此可得：
Edl(n)= (n-i)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约一半
的结点，平均时间复杂度也是 O(n)。
小结：
1、在顺序表上插入、删除一个结点，需要移动大量
元素。
2、具有随机访问的特点。
数据结构
tjm
2.3 线性表的链式表示和实现
线性表的顺序表示的 特点 是 用物理位置上的邻接
关系来表示结点间的逻辑关系,这一特点使我们
可以随机存取表中的任一结点，但它也使得 插入
和删除操作会移动大量的结点,
为避免大量结点的移动，介绍线性表的另一种存
储方式,链式存储结构,简称为 链表。
数据结构
tjm
2.3.1 线性链表
链表 是 指用一组任意的存储单元来依次存放线性
表的结点,这组存储单元即可以是连续的，也可
以是不连续的，甚至是零散分布在内存中的任意
位置上的。因此，链表中结点的逻辑次序和物理
次序不一定相同。为了能正确表示结点间的逻辑
关系，在存储每个结点值的同时，还必须存储指
示其后继结点的地址（或位置）信息，这个信息
称为指针或链。这两部分组成了链表中的结点结
构：
data next
数据结构
tjm
其中,data域是数据域,用来存放结点的值。
next是指针域 （亦称链域），用来存放结点的直
接后继的地址（或位置）。由于上述链表的每一个
结只有一个链域，故将这种链表称为 单链表 。
开始结点无前趋，应设头指针 head指向开始结点。
终端结点无后继，终端结点的指针域为空，即 NULL
（ 图示中也可用 ^表示 )。
数据结构
tjm
例 1、线性表,
(bat,cat,eat,fat，
hat,jat,lat,mat)
单
链
表
示
意
图
……… ……
hat 200
……,……
cat 135
eat 170
…,……
mat Null
bat 130
fat 110
…… ……
jat 205
lat 160
…… ……
165
……
110
……
130
135
……
160
165
170
……
200
205
……
头指针 head
数据结构
tjm
head
bat cat eat mat ^…
单链表是由表头唯一确定，因此单链表可以用头指
针的名字来命名。
例如：若头指针名是 head，则把链表称为表 head
用 C语言描述的单链表如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
数据结构
tjm
假设 p为指向结点的指针变量，则它通过标准函数
生成的，即
p=(LNode*)malloc(sizeof(LNode));
函数 malloc分配了一个类型为 LNode的结点变
量的空间，并将其首地址放入指针变量 p中。一旦
p所指的结点不再需要了，又可通过标准函数
free(p)释放所指的结点空间。
注意：三个概念：
头结点的概念
头指针
首元结点
数据结构
tjm
单链表的基本操作：
一、查找运算
1、在单链表中，即使知道被访问结点的序号 i，
也不能象顺序表中那样直接按序号 i访问结点，
而只能从单链表的头指针出发，顺链域 next逐
个结点往下搜索，直到搜索到第 i个结点为止。
因此，链表不是随机存取结构。
设单链表的长度为 n，要查找表中第 i个结点，
仅当 1<=i<=n时,i的值是合法的。
其算法参见 P29
? ? ? ?nOnT ??
算法的平均时间复杂度：
数据结构
tjm
a b
步骤 1,生成一个数据域为 x的结点。
p
xs
data next
在线性表的两个数据元素 a和 b之间插入一个
数据元素 x，已知 p为其单链表存储结构中指向
结点 a的指针。
二、单链表的插入
数据结构
tjm
用 C语句描述为：
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
数据结构
tjm
a b
步骤 2,将数据元素 x插在 a和 b元素之间。
p
xs
data next
数据结构
tjm
a bp
xs
data next
步骤 2,将数据元素 x插在 a和 b元素之间。
数据结构
tjm
a b
步骤 2,将数据元素 x插在 a和 b元素之间。
p
xs
data next
数据结构
tjm
a b
用 C语言描述为：
s->next = p->next;
p->next = s;
p
xs
data next
数据结构
tjm
a bp
xs
data next
即：
p->next = s;
s->next = p->next;
注意语句的顺序，如改为以下顺序，什么
情况会发生？
b结点的地址？
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
…
ai-1 ai…p
j = 0
a1
an^
L
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
…
ai-1 ai…
j = 1
a1
an^
pL
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
p
j = …
…
ai-1 ai…a1
an^
L
数据结构
tjm
在带头结点单链表 L中第 i个位置之前插入
元素 e：
j = i-1
…
ai-1 ai…a1
an^
pL
数据结构
tjm
…
ai-1 ai…a1
an^
p
es
L
关键语句：
s=(LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
其算法参见 P29
数据结构
tjm
删除元素 b：
a bp c
data next…
…
三、单链表的删除
数据结构
tjm
a bp c
data next…
…
删除元素 b：
三、单链表的删除
数据结构
tjm
a bp c
data next…
…
用 C语言语句描述为：
p->next=p->next->next;
删除元素 b：
三、单链表的删除
数据结构
tjm
删除元素 b并释放之：
a bp c
data next…
…
步骤 1：将 b的地址记录下来
即,q=p->next;
q
数据结构
tjm
a bp c
data next…
…
删除元素 b并释放之：
步骤 2：让 p->next指向 b后第一个结点
即,p->next=q->next;
q
数据结构
tjm
a bp c
data next…
…
删除元素 b并释放之：
q
步骤 3：释放 b结点
即,free(q)
数据结构
tjm
ap c
data next…
…
删除元素 b并释放之：
b
q
步骤 3：释放 b结点
即,free(q)
其算法参见 P30
数据结构
tjm
四、单链表的建立（头插法）
动态建立单链表算法,设线性表 n个元素已存
放在数组 a中，建立一个单链表,L为头指针 。
L
头结点
an ^
L
头结点
^
数据结构
tjm
? ? ? ?nOnT ?
L
头结点
an-1 an ^
a2 …...L
头结点
an-1 an ^
L a1 a2
头结点
an ^…...
……
其算法参见 P30
数据结构
tjm
小结
3、链式存储的优点,插入删除效率高
4、链式存储的缺点,访问某个数据效率低
1、在单链表上插入、删除一个结点，必须知道其前
驱结点。
2、单链表不具有按序号随机访问的特点，只能从
头指针开始一个个顺序进行。
数据结构
tjm
2.3.2 循环链表
循环链表是一种头尾相接的链表。其 特点 是
无需增加存储量，仅对表的链接方式稍作改变，
即可使得表处理更加方便灵活。
单循环链表,在单链表中，将终端结点的指针
域 NULL改为指向第一个结点，就得到了单链
形式的循环链表，并简称为单循环链表。
循环链表中也可设置一个 头结点 。这样，空循
环链表仅有一个自成循环的头结点表示。如下
图所示：
数据结构
tjm
a1 an….head
⑴ 非空表
⑵ 空表
数据结构
tjm
在用头指针表示的单链表中，找开始结点 a1的时间
是 O(1)，然而要找到终端结点 an，则需从头指针
开始遍历整个链表，其时间是 O(n)。在很多实际
问题中，表的操作常常是在表的首尾位置上进行，
此时头指针表示的单循环链表就显得不够方便,如果
改用 尾指针 rear来表示单循环链表，则查找开始结
点 a1和终端结点 an都很方便，它们的存储位置分别
是 (rear–>next) —>next和 rear，显然，查
找时间都是 O(1)。因此，实际中多采用尾指针表
示单循环链表。
由于循环链表中没有 NULL指针，故涉及遍历操
作时，其终止条件就不再像非循环链表那样判断 p
或 p—>next是否为空，而是判断它们是否等于某
一指定指针。
数据结构
tjm
2.3.3 双向链表
双向链表,在单链表的每个结点里再增加一个
指向其直接前趋的指针域 prior。这样形成的
链表中有两个方向不同的链,故称为 双向链
表 。形式描述为：
typedef struct DulNode{
ElemType data; 数据域
struct DulNode *prior;
指向前驱元素的指针
struct DulNode *next;
指向后继元素的指针
} DulNode,*DuLinkList;
数据结构
tjm
设指针 p指向某一结点，则有：
(p—>prior)—>next=p
=(p—>next)—>prior
即结点 *p的存储位置既存放在其前趋结点
*(p—>prior)的直接后继指针域中，也存放 在
它的后继结点 *(p—>next)的直接前趋指针域
中。 a1 a
n….head
⑴ 非空表
^
^
⑵ 空表
^
^ 双向链表
数据结构
tjm
a b
x
p
q
在 p所指结点前插入值为 x的结点，
应怎样修改指针？
q= (DulNode *) malloc(sizeof(DulNode));
q—>data=x;
q—>prior=p—>prior;
q—>next=p;
p—>prior—>next=q;
p—>prior=q;
数据结构
tjm
a b
p
c
双向链表中删除结点 p,应怎样修改指针？
p–>prior–>next=p–>next;
p–>next–>prior=p–>prior;
free(p);
注意：与单链表的插入和删除操作不同的是，在双
链表中插入和删除必须同时修改两个方向上的指针。
上述两个算法的时间复杂度均为 O(1)。
数据结构
tjm
2.4 一元多项式的表示及相加
因此一元多项式：
Pm(x)=p1xe1+ p2xe2+ …...+pmxem
可用线性表：
((p1,e1),(p2,e2),……(pm,em)) 表示
一元多项式：
Pm(x)=p1xe1+ p2xe2+ …...+pmxem
可用系数线性表 P表示,p=(p1,p2,… pm)
但对 S (x) = 1 + 3 x 1000 + 2 x 2000 这样的多项式
浪费空间 系数线性表 ( 1,0,…0,3,0,…0,2)
可用非零系数指数线性表, ((1,0),(3,1000),
(2,2000))
数据结构
tjm
例：求两多项式的和多项式
A (x) = 7 +3 x + 9 x 8 + 5 x 17
B (x) = 8 x + 22 x 7 – 9 x 8
C (x) = A (x) + B (x) = 7 + 11x +22 x 7
+ 5 x 17
A=( (7,0),(3,1),(9,8),(5,17))
B=( (8,1),(22,7),(-9,8))
C=((7,0),(11,1),(22,7),(5,17))
数据结构
tjm
结点：
一元多项式的链式存储结构
coef exp next
抽象数据类型 Polynomial的实现 参见 P42。
h
-1 1 0 3 1000 2 2000 ∧
头结点
例,S (x) = 1 + 3 x 1000 + 2 x 2000 的
单链表存储示意图
数据结构
tjm
pa
-1 7 0 3 1 9 8 5 17 ∧
pb
-1 8 1 22 7 -9 8 ∧
pa
22 7
-1 7 0 11 1 5 17 ∧
和多项式链表：
AddPolyn算法 (类似于两个有序表的
归并，仅有一些细微差别。）
设多项式 A (x), B (x)分别用带表头结点的单链
表 pa, pb表示，和多项式仍用带表头结点的单
链表 pa表示。
数据结构
tjm
设 p,q分别指向 A,B中某一结点,p,q初值是第一结点
运算规则：
比较
p->exp
与 q->exp
p->exp < q->exp,p结点是和多项式中的一项，
p后移,q不动
p->exp > q->exp,q结点是和多项式中的一项，
将 q插在 p之前,q后移,p不动
p->exp = q->exp,系数相加
0：从 A表中删去 p,
释放 p,q； p,q
后移
?0：修改 p系数域,
释放 q； p,q
后移直到 p或 q为 NULL 若 q==NULL,结束
若 p==NULL,将 B中剩余部分连到 A上即可
数据结构
tjm
qaha
算法示意：
qb
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qaha
hb
qb
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
hb
数据结构
tjm
qb
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qaha
hb
qa
qb
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
hahb
数据结构
tjm
-1pa 7 0 11 1 22 7 5 17 ^
qb=NULL
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qa
hahb
qb=NULL
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
qa
ha最后：
