第二章 线性表线性结构 特点,在数据元素的非空有限集中
存在 唯一 的一个被称作,第一个,的数据元素
存在 唯一 的一个被称作,最后一个,的数据元素
除第一个外，集合中的每个数据元素均 只有一个前驱
除最后一个外，集合中的每个数据元素均 只有一个后继
§ 2.1 线性表的逻辑结构
定义：一个线性表是 n个数据元素的有限序列
ni aaaa,,,,21如例 英文字母表（ A,B,C,…..Z) 是一个线性表例学号 姓名 年龄
001 张三 18
002 李四 19
…… …… ……
数据元素
特征：
元素个数 n— 表长度,n=0空表
1<i<n时
ai的直接 前驱 是 ai-1,a1无直接前驱
ai的直接 后继 是 ai+1,an无直接后继
元素同构，且不能出现缺项
§ 2.2 线性表的顺序存储结构
顺序表：
定义：用一组地址连续的存储单元存放一个线性表叫 ~
元素地址计算方法：
LOC(ai)=LOC(a1)+(i-1)*L
LOC(ai+1)=LOC(ai)+L
其中：
L— 一个元素占用的存储单元个数
LOC(ai)— 线性表第 i个元素的地址
特点：
实现 逻辑上相邻 — 物理地址相邻
实现 随机存取
实现,可用 C语言的一维数组实现
a1
a2
an
0
1
n-1
1
2
n
内存V数组下标 元素序号
M-1
typedef int DATATYPE;
#define M 1000
DATATYPE data[M];
例 typedef struct card
{ int num;
char name[20];
char author[10];
char publisher[30];
float price;
}DATATYPE;
DATATYPE library[M];
备用空间数据元素不是简单类型时,可定义 结构体数组或动态申请和释放内存
DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE));
free(pData);
插入
定义：线性表的插入是指在第 I（ 1?i? n+1） 个元素之前插入一个新的数据元素 x,使长度为 n的线性表
nii aaaaa,,,,1,21?
变成 长度为 n+1的线性表
nii aaxaaa,,,,,1,21?
需将第 i至第 n共 （ n-i+1)个元素后移
算法
Ch2_1.c
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
an-1
x
算法时间复杂度 T(n)
设 Pi是在第 i个元素之前插入一个元素的概率，则在长度为 n
的线性表中插入一个元素时，所需移动的元素次数的平均次数为：
1
1
)1(
n
i
i inPE is
nOnT
n
in
n
E is
n
P
n
i
i
1
1 2
)1(
1
1
1
1
则若认为
删除
定义：线性表的删除是指将第 i（ 1?i? n） 个元素删除，
使长度为 n的线性表
nii aaaaa,,,,1,21?
变成 长度为 n-1的线性表
nii aaaaa,,,,11,21
需将第 i+1至第 n共 （ n-i)个元素前移
算法
Ch2_2.c
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai+1
V数组下标
0
1
i-1
n-2
i
n-1
1
2
i
元素序号
i+1
n-1
n
an
ai+2
算法评价
设 Qi是删除第 i个元素的概率，则在长度为 n的线性表中删除一个元素所需移动的元素次数的平均次数为：
n
i
ide inQE
1
)(
nOnT
n
in
n
E
n
Q
n
i
de
i
1 2
1
)(
1
1
则若认为故在 顺序表中插入或删除 一个元素时，平均移动表的一半元素，当 n很大时,效率很低
顺序存储结构的优缺点
优点
逻辑相邻，物理相邻
可随机存取任一元素
存储空间使用紧凑
缺点
插入、删除操作需要移动大量的元素
预先分配空间需按最大空间分配，利用不充分
表容量难以扩充
§ 2.3 线性表的链式存储结构特点：
用一组 任意 的存储单元存储线性表的数据元素
利用 指针 实现了用不相邻的存储单元存放逻辑上相邻的元素
每个数据元素 ai,除存储本身信息外，还需存储其直接后继的信息
结点
数据域：元素本身信息
指针域：指示直接后继的存储位置数据域 指针域结点
ZHAO QIAN SUN LI
ZHOU WU ZHENG WANG ^
H
例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
43
13
1
NULL
37
7
19
25
数据域 指针域
LI
QIAN
SUN
WANG
WU
ZHAO
ZHENG
ZHOU
存储地址
1
7
13
19
25
31
37
43
31
H
头指针
实现 typedef struct node {
datatype data;
struct node *link;
}JD;
JD *h,*p;
data link
p 结点（ *p）
(*p)表示 p所指向的结点
(*p).data?p->data表示 p指向结点的数据域
(*p).link?p->link表示 p指向结点的指针域生成一个 JD型 新结点,p=(JD *)malloc(sizeof(JD));
系统回收 p结点,free(p)
线性链表
定义：结点中只含一个指针域的链表叫 ~，也叫单链表头结点：在单链表第一个结点前附设一个结点叫 ~
头结点指针域为空表示线性表为空
h a1 a2
头结点
an ^…...
h 空表^
单链表的基本运算
查找：查找单链表中是否存在结点 X，若有则返回指向 X结点的指针；否则返回 NULL
算法描述
While循环中语句频度为若找到结点 X,为结点 X在表中的序号否则，为 n
nOnT
p a b
xs
算法评价
插入：在线性表两个数据元素 a和 b间插入 x,已知 p指向 a
s->link=p->link;p->link=s;
1OnT?
算法描述
算法评价
算法描述
p a b c
1OnT?
算法评价
删除：单链表中删除 b,设 p指向 a
p->link=p->link->link;
nOnT?
动态建立单链表算法,设线性表 n个元素已存放在数组 a中，
建立一个单链表,h为头指针
算法描述
算法评价
h
头结点
an ^0
头结点
an-1 an ^a2 …...
头结点
an-1 an ^a1 a2
头结点
an ^…...0
Ch2_3.c
头结点
^
单链表特点
它是一种 动态结构,整个存储空间为多个链表共用
不需预先分配 空间
指针占用 额外 存储空间
不能随机存取,查找速度慢
循环链表 (circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表构成环状
特点：从表中任一结点出发均可找到表中其他结点，
提高查找效率
操作与单链表基本一致,循环条件不同
单链表 p或 p->link=NULL
循环链表 p或 p->link=H
h
h 空表
双向链表（ double linked list）
单链表具有单向性的缺点
结点定义
typedef struct node {
datatype element;
struct node *prior,*next;
}JD;
prior element next
L空双向循环链表：
非空双向循环链表,L A Bb ca
p
p->prior->next= p= p->next->proir;
b ca
P
void del_dulist(JD *p)
{p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
}
删除
算法描述
算法评价,T(n)=O(1)
p->prior->next=p->next;
p->next->prior=p->prior;
void ins_dulist(JD* p,int x)
{JD *s;
s=(JD*)malloc(sizeof(JD));
s->element=x;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
}
算法描述
算法评价,T(n)=O(1)
xS
ba
P?插入
§ 2.4 线性表的应用举例一元多项式的表示及相加
一元多项式的表示：
nnn xPxPxPPxP2210)(
),,,,( 210 nPPPPP可用线性表 P表示
2 0 0 0 01 0 0 0 231)( xxxS但对 S(x)这样的多项式浪费空间一般
emmn xPxPxPxP ee21 21)(
其中 为非零系数）（
iPemee210
用数据域含两个数据项的线性表表示
emPePeP m,，，，,21 21
其存储结构可以用顺序存储结构，也可以用单链表
单链表的结点定义
typedef struct node
{ int coef,exp;
struct node *next;
}JD;
coef exp next
177
87
172
522117)()()(
9228)(
5937)(
xxxxBxAxC
xxxxB
xxxxA
-1A 7 0 3 1 9 8 5 17 ^
-1B 8 1 22 7 -9 8 ^
-1C 7 0 11 1 22 7 5 17 ^
一元多项式相加设 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上即可
运算规则
q
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
ppre
-
- -
ppre
q
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
p
preq
11 1
ppre
q=NULL
p
-1pa 7 0 11 1 22 7 5 17 ^
Ch2_7.c
算法描述
存在 唯一 的一个被称作,第一个,的数据元素
存在 唯一 的一个被称作,最后一个,的数据元素
除第一个外，集合中的每个数据元素均 只有一个前驱
除最后一个外，集合中的每个数据元素均 只有一个后继
§ 2.1 线性表的逻辑结构
定义：一个线性表是 n个数据元素的有限序列
ni aaaa,,,,21如例 英文字母表（ A,B,C,…..Z) 是一个线性表例学号 姓名 年龄
001 张三 18
002 李四 19
…… …… ……
数据元素
特征：
元素个数 n— 表长度,n=0空表
1<i<n时
ai的直接 前驱 是 ai-1,a1无直接前驱
ai的直接 后继 是 ai+1,an无直接后继
元素同构，且不能出现缺项
§ 2.2 线性表的顺序存储结构
顺序表：
定义：用一组地址连续的存储单元存放一个线性表叫 ~
元素地址计算方法：
LOC(ai)=LOC(a1)+(i-1)*L
LOC(ai+1)=LOC(ai)+L
其中：
L— 一个元素占用的存储单元个数
LOC(ai)— 线性表第 i个元素的地址
特点：
实现 逻辑上相邻 — 物理地址相邻
实现 随机存取
实现,可用 C语言的一维数组实现
a1
a2
an
0
1
n-1
1
2
n
内存V数组下标 元素序号
M-1
typedef int DATATYPE;
#define M 1000
DATATYPE data[M];
例 typedef struct card
{ int num;
char name[20];
char author[10];
char publisher[30];
float price;
}DATATYPE;
DATATYPE library[M];
备用空间数据元素不是简单类型时,可定义 结构体数组或动态申请和释放内存
DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE));
free(pData);
插入
定义：线性表的插入是指在第 I（ 1?i? n+1） 个元素之前插入一个新的数据元素 x,使长度为 n的线性表
nii aaaaa,,,,1,21?
变成 长度为 n+1的线性表
nii aaxaaa,,,,,1,21?
需将第 i至第 n共 （ n-i+1)个元素后移
算法
Ch2_1.c
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
an-1
x
算法时间复杂度 T(n)
设 Pi是在第 i个元素之前插入一个元素的概率，则在长度为 n
的线性表中插入一个元素时，所需移动的元素次数的平均次数为：
1
1
)1(
n
i
i inPE is
nOnT
n
in
n
E is
n
P
n
i
i
1
1 2
)1(
1
1
1
1
则若认为
删除
定义：线性表的删除是指将第 i（ 1?i? n） 个元素删除，
使长度为 n的线性表
nii aaaaa,,,,1,21?
变成 长度为 n-1的线性表
nii aaaaa,,,,11,21
需将第 i+1至第 n共 （ n-i)个元素前移
算法
Ch2_2.c
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai+1
V数组下标
0
1
i-1
n-2
i
n-1
1
2
i
元素序号
i+1
n-1
n
an
ai+2
算法评价
设 Qi是删除第 i个元素的概率，则在长度为 n的线性表中删除一个元素所需移动的元素次数的平均次数为：
n
i
ide inQE
1
)(
nOnT
n
in
n
E
n
Q
n
i
de
i
1 2
1
)(
1
1
则若认为故在 顺序表中插入或删除 一个元素时，平均移动表的一半元素，当 n很大时,效率很低
顺序存储结构的优缺点
优点
逻辑相邻，物理相邻
可随机存取任一元素
存储空间使用紧凑
缺点
插入、删除操作需要移动大量的元素
预先分配空间需按最大空间分配，利用不充分
表容量难以扩充
§ 2.3 线性表的链式存储结构特点：
用一组 任意 的存储单元存储线性表的数据元素
利用 指针 实现了用不相邻的存储单元存放逻辑上相邻的元素
每个数据元素 ai,除存储本身信息外，还需存储其直接后继的信息
结点
数据域：元素本身信息
指针域：指示直接后继的存储位置数据域 指针域结点
ZHAO QIAN SUN LI
ZHOU WU ZHENG WANG ^
H
例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
43
13
1
NULL
37
7
19
25
数据域 指针域
LI
QIAN
SUN
WANG
WU
ZHAO
ZHENG
ZHOU
存储地址
1
7
13
19
25
31
37
43
31
H
头指针
实现 typedef struct node {
datatype data;
struct node *link;
}JD;
JD *h,*p;
data link
p 结点（ *p）
(*p)表示 p所指向的结点
(*p).data?p->data表示 p指向结点的数据域
(*p).link?p->link表示 p指向结点的指针域生成一个 JD型 新结点,p=(JD *)malloc(sizeof(JD));
系统回收 p结点,free(p)
线性链表
定义：结点中只含一个指针域的链表叫 ~，也叫单链表头结点：在单链表第一个结点前附设一个结点叫 ~
头结点指针域为空表示线性表为空
h a1 a2
头结点
an ^…...
h 空表^
单链表的基本运算
查找：查找单链表中是否存在结点 X，若有则返回指向 X结点的指针；否则返回 NULL
算法描述
While循环中语句频度为若找到结点 X,为结点 X在表中的序号否则，为 n
nOnT
p a b
xs
算法评价
插入：在线性表两个数据元素 a和 b间插入 x,已知 p指向 a
s->link=p->link;p->link=s;
1OnT?
算法描述
算法评价
算法描述
p a b c
1OnT?
算法评价
删除：单链表中删除 b,设 p指向 a
p->link=p->link->link;
nOnT?
动态建立单链表算法,设线性表 n个元素已存放在数组 a中，
建立一个单链表,h为头指针
算法描述
算法评价
h
头结点
an ^0
头结点
an-1 an ^a2 …...
头结点
an-1 an ^a1 a2
头结点
an ^…...0
Ch2_3.c
头结点
^
单链表特点
它是一种 动态结构,整个存储空间为多个链表共用
不需预先分配 空间
指针占用 额外 存储空间
不能随机存取,查找速度慢
循环链表 (circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表构成环状
特点：从表中任一结点出发均可找到表中其他结点，
提高查找效率
操作与单链表基本一致,循环条件不同
单链表 p或 p->link=NULL
循环链表 p或 p->link=H
h
h 空表
双向链表（ double linked list）
单链表具有单向性的缺点
结点定义
typedef struct node {
datatype element;
struct node *prior,*next;
}JD;
prior element next
L空双向循环链表：
非空双向循环链表,L A Bb ca
p
p->prior->next= p= p->next->proir;
b ca
P
void del_dulist(JD *p)
{p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
}
删除
算法描述
算法评价,T(n)=O(1)
p->prior->next=p->next;
p->next->prior=p->prior;
void ins_dulist(JD* p,int x)
{JD *s;
s=(JD*)malloc(sizeof(JD));
s->element=x;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
}
算法描述
算法评价,T(n)=O(1)
xS
ba
P?插入
§ 2.4 线性表的应用举例一元多项式的表示及相加
一元多项式的表示：
nnn xPxPxPPxP2210)(
),,,,( 210 nPPPPP可用线性表 P表示
2 0 0 0 01 0 0 0 231)( xxxS但对 S(x)这样的多项式浪费空间一般
emmn xPxPxPxP ee21 21)(
其中 为非零系数）（
iPemee210
用数据域含两个数据项的线性表表示
emPePeP m,，，，,21 21
其存储结构可以用顺序存储结构，也可以用单链表
单链表的结点定义
typedef struct node
{ int coef,exp;
struct node *next;
}JD;
coef exp next
177
87
172
522117)()()(
9228)(
5937)(
xxxxBxAxC
xxxxB
xxxxA
-1A 7 0 3 1 9 8 5 17 ^
-1B 8 1 22 7 -9 8 ^
-1C 7 0 11 1 22 7 5 17 ^
一元多项式相加设 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上即可
运算规则
q
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
ppre
-
- -
ppre
q
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
p
preq
11 1
ppre
q=NULL
p
-1pa 7 0 11 1 22 7 5 17 ^
Ch2_7.c
算法描述
