1
第二章 线性表
线性表的定义
线性表的顺序表示
线性表的链式表示
一元多项式的运算
数
据
结
构
之
线
性
表
2
2.1 线性表的类型定义
?线性表
? 定义： n 个数据元素的有限序列。
( A , B , C , ...... , X , Y , Z )
( a 1 , a 2 , ... , a i -1 , a i , a i + 1, ... , a n - 1 , a n )
? 线性表的逻辑特性：
?线性表中的所有数据元素，其数据类型是
一致的；
?数据元素在表中的位置只取决于它们自己
的序号，数据元素之间的相对位置是线性
的
2
数
据
结
构
之
线
性
表
3
?基本术语
? 直接前驱： a i - 1 针对 a i
? 直接后继： a i + 1,
?线性表的长度： 是指线性表中数据
元素的个数， n = 0 时为空表。
?位序： 下标i是数据元素 ai ， 在线
性表中的位序。
数
据
结
构
之
线
性
表
4
?线性表抽象数据类型的定义
? ADT List {数据对象 :D= {a i | a i ∈ ElemSet , i
= 1,2,...,n, n ≥ 0}
数据关系 :R1={<a i -1 ,a i >|a i -1 ,a i ∈D, i = 1,2,...,n }
? 基本操作： & 符号说明函数参数是引用型
InitList(&L) ListLength(L)
DestroyList(&L) GetElem(L , i , &e)
ClearList(&L) LocateElem(L , e)
ListEmpty(&L) PriorElem(L , cur_e , &pre_e)
ListInsert(&L , i , e) ListDelete(&L , i , &e)
.......}
3
数
据
结
构
之
线
性
表
5
? 求 A = A ∪ B 的算法
? 分析：建立线性表 La、 Lb，将 La中不存在
的 bi插入 La中，因此，本算法的基本操作是
查找 (比较 )
? 基于逻辑结构的算法描述：
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); /* O(1) */
if(!LocateElem(La,e)) /* O(La_len ) */
ListInsert(La,+ +La_len,e); /* O(1 ) */
} }
? 算法分析：考虑算法的最费时执行状况，作
为算法的时间复杂度 O(La_len*Lb_len)
数
据
结
构
之
线
性
表
6
?求 LC = LA+ LB 的算法 :La和 Lb的元素按升序
排列，将 La和 Lb归并为 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)) {
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); } }
算法分析：时间复杂度 O(La_len+Lb_len)
4
数
据
结
构
之
线
性
表
7
?线性表的存储结构
?顺序存储的线性表，叫
顺序表
?链式存储的线性表，叫
链表
数
据
结
构
之
线
性
表
8
2.2 线性表的顺序表示和实现
? 概念
? 用一组地址连续的存储单元依次存储线性
表的数据元素。
? 顺序表的特点是：逻辑关系上相邻的两个
元素在物理位置上也相邻。
? 顺序表是随机存取的存储结构：
可以随机存取（所需时间相同）表中任一
元素，因为它的存储位置可用一个简单、直观
的公式（位序的线性函数）来表示。
5
数
据
结
构
之
线
性
表
9
? 数据元素 a i 的存储位置（内存地址）：
（不同于位序 i ）
Loc ( a i )=Loc ( a i -1 ) + L
Loc ( a i )=Loc ( a 1 ) +( i -1 )*L
Loc(a i )是 a i 在内存中的第一个字节的
地址。
L 是一个元素的字节数。
例如：整型线性表存储在内存中的地址是
C000，表中的第7个元素的存储地址是
C000+2*6=C00C
数
据
结
构
之
线
性
表
10
?顺序存储结构
? 定义
typedef int ElemType ;
typedef Elemtype ET;
typedef struct{
ElemType *elem ; //动态空间基址
int length ; //实际元素个数
int listsize ; //当前分配的存储
}SqList ; //容量 (以 sizeof(ElemType)为单位 )
SqList 是顺序表的类型名。
6
数
据
结
构
之
线
性
表
11
存储地址 内存状态 元素序号
空闲
a
a
a
a
1
2
i
n
:
:
:
:
:
:
:
b
b+L
b+(i-1)L
b+(n-1)L
B+(maxlen-1)L
1
2
i
n
线性表的顺序存储结构示意图
数
据
结
构
之
线
性
表
12
?重新分配动态存储空间的函数
realloc(原动态区首址，字节数 )
?其功能为：
?申请新的动态存储空间(成功或失败);
?将原动态区的数据拷贝到新动态区;
?释放原动态存储区;
?返回新存储区首地址（无类型）。
?用途：当原动态区不够用时，追加动态
存储区；
7
数
据
结
构
之
线
性
表
13
?顺序表的操作
? 构造一个空的线性表 L
#define List_Init_Size 100
#define ListIncrement 10
Status InitList_Sq( SqList &L){
L.elem=(ET*)malloc(List_Init_Size*sizeof(ET));
if(L.elem==NULL)
exit(OVERFLOW); /*存储分配失败 */
L.length=0; /* 空表的长度 */
L.listsize=List_Init_Size; /* 初始存储容量 */
return OK;
}
数
据
结
构
之
线
性
表
14
? 插入操作： 在顺序表L中第i个位置上插
入一个新的元素e。
?形式参数为：&L ,i , e ；
?算法步骤如下：
?对输入参数的安全性检查: 插入位置 i 应落在
表长＋１范围内，即： 1 ≤ i ≤ L.length+1
?存储空间的处理：若原表的存储空间已满，应追
加存储空间的分配；
?数据块的搬移：将表中从i到L.length位置上的
所有元素往后移动一个位置；
?在第i个位置上存储新的元素e,表长增１;
?注意：逻辑位置（序号）i 对应的存储下
标是i-1。
8
数
据
结
构
之
线
性
表
15
?顺序表 ----插入操作算法描述之一
Status ListInsert_Sq(SqList &L , int i , ET e){
if ( i<1 || i>L.length+1) return ERROR;
if(L.length >= L.listsize){
p=(ET*)realloc(L.elem,(L.listsize+10)*sizeof(ET));
if (p==NULL) exit(OVERFLOW);
L.elem=p; L.listsize+=ListIncrement;
}
for( j=L.length ; j>=i ; --j )
L.elem[j]=L.elem[j-1];
L.elem[j]=e ; ++L.length ;
return OK; }
数
据
结
构
之
线
性
表
16
?顺序表 ----插入操作算法描述之二
Status ListInsert_Sq(SqList &L , int i , ET e){
if ( i<1 || i>L.length+1) return ERROR;
if (L.length >= L.listsize){
p=(ET*)realloc(L.elem,(L.listsize+10)*sizeof(ET));
if (p==NULL) exit(OVERFLOW);
L.elem=p; L.listsize+=ListIncrement;
}
q=&(L.elem[i-1]); /* q=L.elem+(i-1) 插入位置 */
for (p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p;
*q=e ; ++L.length ;
return OK;
}
9
数
据
结
构
之
线
性
表
17
?插入操作的算法性能分析
?空间复杂度是 O( 1 )
?时间复杂度： O(n) , 其中 n= L.length
?步骤（１）、（２）、（４）的时
间复杂度都是常数，即： O ( 1 );
?步骤（３）的基本操作是数据移动，
最坏的情况下(在第一个位置上插入元素)，
需要移动n个元素；
平均情况下（等概率），需移动表中 n/2
个元素，最好的情况是不移动元素。
因此，插入操作算法的时间复杂度是 O(n);
数
据
结
构
之
线
性
表
18
? 删除操作：长为n的线性表L(a
1
,a
2
, … ,
a
n
), 删除a
i
，并把它送入某单元e
e
a
i
a
1
a
2
a
3
a
i-1
a
i
a
n
:
:
1
2
3
i-1
i
n-1
i+1
n
:
:
a
1
a
2
a
3
a
i-1
a
n
:
:
1
2
3
i-1
i
n-1
i+1
n
:
:
a
i+1
顺序存储结构的删除操作
10
数
据
结
构
之
线
性
表
19
?形式参数为 ： &L ,i , &e ；
?算法步骤如下：
?对输入参数的安全性检查: 删除位置 i
应落在表长范围内，即： 1≤ i ≤ L.length
?取出元素值赋给 e：
?数据块的搬移： 将表中从 i+1到 L.length
位置上的所有元素往前移动一个位置；
?表长减１ ： --L.length;
数
据
结
构
之
线
性
表
20
?算法
Status ListDelete_Sq(SqList &L , int i , ET &e){
if(i<1 || i>L.length) return ERROR;
e=L.elem[i-1];
for( j=i ; j<L.length;j++)
L.elem[j-1]=L.elem[j];
L.length--;
}
算法分析 ：基本操作是什么？时间复杂度
是多少？
11
数
据
结
构
之
线
性
表
21
? 线性链表
? 概念
?顺序表的特点：可以随机存取表中的任一元素；
在作插入和删除操作时,需移动大量的元素。
?线性表的链式存储结构：用任意的存储单元存储
线性表的数据元素；
?用链指针体现线性表中数据元素之间的逻辑关系：
?逻辑结构中的数据元素ai对应存储结构中的结点
ai （数据域）
ai+1结点的地址 （指针域）
2.3 线性表的链式表示和实现
数
据
结
构
之
线
性
表
22
?N个结点连成一个链
表：
?假设元素类型是字符
型，每个结点占用 3
个字节存储空间。
?单链表可由头指针唯
一确定；
地址 数据域指针域
0300 A 0605
0303 B 0306
0306 C NULL
030F D 0303
......
0600 E 060A
0605 F 030F
060A G 0300
......
0800 H 0600
Head
Head H E G A F D B C ^
12
数
据
结
构
之
线
性
表
23
?线性表的单链表存储结构
/*typedef char ElemType;*/
typedef struct LNode{
ElemType data;
struct LNode *next;
} Lnode, *LinkList;
Lnode 是结点类型名，
LinkList是结点指针类型名；
数
据
结
构
之
线
性
表
24
?头结点
头指针 L 是 LinkList类型，头结点是
Lnode类型；
非空表：
空表：
头结点的位序为0，它不是线性表中的
元素，头结点的数据域可用于存储线性
表的长度；
?单链表是非随机存取的存储结构。
头 5 8 3 6 ^L
头 ^L
13
数
据
结
构
之
线
性
表
25
? 单链表基本操作的算法
?在链表 L中， 读取 第 i个元素的值赋给参数 e
Status GetElem_L(LinkList L,int i,ElemType &e){
p=L → next ; j=1 ; /* O(1) */
while ( p && j < i ){ p=p → next ; j++;} /* O(n)
if ( p==NULL || j > i ) return ERROR; /* O(1)
e = p → data; /* O(1)
return OK;
}
时间复杂度为： O(n)
问题：在顺序表中， GetElem_Sq时间复杂度？
数
据
结
构
之
线
性
表
26
?构造一个空的单链表 , 算法描述： L 必须是
引用型
Status InitList_L(LinkList &L){
L=( LinkList ) malloc ( sizeof ( Lnode ) );
if (L==NULL) exit (OVERFLOW);
L → next=NULL; L → data=0;
return OK; }
对应的 C程序如下： L指向主函数中链表头指针变量
Status InitList_L(LinkList *L){ // 程序中,L是双指针
*L=( LinkList ) malloc ( sizeof ( Lnode ) );
if ( *L==NULL) exit (OVERFLOW);
(*L) → next=NULL; (*L) → data=0;
return OK ; }
14
数
据
结
构
之
线
性
表
27
?单链表算法中的关键步骤描述：
?指针 p在链表上依次滑动： p=head;
while( p->next ) {p=p->next; }
?前驱指针 q 和指针 p在链表上同步滑动：
q=head ; p=q->next;
while( p){q=p ; p=q->next;}
例如： int ListLength_L( LinkList L) {p=L;j=0;
while(p->next){j++;p=p->next;} return(j);}
Status PriorElem_L(LinkList L,ET e, ET &pre){
q=L; p=q->next;
while(p && p->data!=e){q=p;p=q->next;} …}
Status NextElem_L(LinkList L,ET e, ET &next){…}
数
据
结
构
之
线
性
表
28
?在单链表 L中的第 i 个结点之前的插
入操作
?步骤如下： ( i > 0 )
?寻找第 i-1个结点； //O(n)
?测试 已知量的合法性； //O(1)
?申请一个结点存储空间，并给其数据域
赋值； // O(1)
?新结点插入链表中。 //O(1)
?该算法的时间复杂度是： O(n)
15
数
据
结
构
之
线
性
表
29
?单链表的插入操作算法描述
参数 L可以不是引用型，因为， L指向头结点
Status ListInsert_L(LinkList L,int i,ElemType e){
p=L, j=0;
while ( p && j< i -1 ){p=p → next; j++;} //寻找
if (p==NULL || i<1) return ERROR;
s = ( LinkList ) malloc ( sizeof ( Lnode ) );
if (s == NULL) exit (OVERFLOW);
s → data=e;
s → next=p → next ; // 在 p结点之后插入结点 s
p → next = s ; /* L → data++ ;链表长度计数 */
return OK; }
数
据
结
构
之
线
性
表
30
? 单链表的删除操作： 删除第i个结点
?步骤
?若头指针为空，则退出；否则执行下面的操作。
?找到要删除结点的直接前驱，将该结点的指针域指向它
的直接后继。若不能找到，则返回。
?释放该结点所占用的内存空间。
BAT CAT
HAT WAT
L
q
^
第 i个结点
p
16
数
据
结
构
之
线
性
表
31
?算法描述
void delete(LinkList L, int i, char *e){
p=L;
j=0;
while(p->next && j<i-1){
p=p->next;
++j;
}
if(!(p->next)|| j>i-1)
return ERROR;
q=p->next;
p->next=q->next;
e=q->data;
free(q);
return OK; }
数
据
结
构
之
线
性
表
32
? 将指针 s所指的一串结点链接在线性
链表 L 的最后一个结点之后
?问题分析
?找到链表 L的最后一个结点；
?进行链接。
?算法描述：
Status Append(LinkList L , LinkList s ){
…/* L 带表头结点， s 不带表头结点 */
}
?算法分析
17
数
据
结
构
之
线
性
表
33
Status Append(LinkList L , LinkList s ){
if (s) {
p=L;
while(p->next) p=p->next;
p->next=s;
}
}
数
据
结
构
之
线
性
表
34
? 更合理的线性链表类型定义
typedef struct LNode{ //结点类型
ElemType data ;
struct LNode *next ;
} *Link , *Position ;
typedef struct{//
Link head ,tail ;//分别指向链表的 头结点 和 最后一
个结点
int len ; // 链表中数据元素的个数
} LinkL ;
参阅 Page 37， 请同学们自行完成该类型定义的第
37-38页所列各基本操作的算法。
18
数
据
结
构
之
线
性
表
35
? 基于 LinkL类型，将线性链表 s 链接在
线性链表 L 的最后一个结点之后
?解题分析：链表头尾已知，只需直接链接 .
?算法描述：
Status Append(LinkL &L , LinkL &s ){
if (s.head != s.tail){
L.tail → next =s.head → next;
L.tail=s.tail;L.len+=s.len;
s.head → next=NULL;
s.tail=s.head; } }
?算法分析：时间复杂度 O(1)
数
据
结
构
之
线
性
表
36
? 基于 LinkL类型，将指针 s 所指的一串
结点链接在线性链表 L 的最后一个结点
之后
?解题分析：链接之后，需找出 s 的最后一个结点 .
?算法描述：
Status Append(LinkL &L , Link s ){
L.tail → next =s;
while(s → next){
s =s → next ;L.len++; } // O(s_len)
L.tail=s ;
}
?算法分析：时间复杂度 O(s_len)
19
数
据
结
构
之
线
性
表
37
? 静态链表
?用数组描述的链表，表示链的是数组下标
（整型）。
?结构类型定义：
#define MaxSize 13
typedef struct{
ElemType data ;
int cur;
}SLinkList [MaxSize];
SLinkList space;//space是有 13个元素的数组名
数
据
结
构
之
线
性
表
38
?循环链表和双向链表
? 循环链表：
非空循环链表：
空循环链表：
头 5 8 3 6L
头L
20
数
据
结
构
之
线
性
表
39
? 双向链表
?定义
结点的物理形式
空双向循环链表
prior data next
H
ABC
P
非空双向循环链表
^ 头 8 3 6 ^L
数
据
结
构
之
线
性
表
40
?用 C语言描述如下：
typedef struct Dulnode{
ElemType data; /*定义数据类型 *；
struct Dulnode *prior; /*指向直接前驱 */
struct Dulnode *next; /*指向直接后继 */
}DuLNode, *DuLinkList; /*定义该双向链表 */
21
数
据
结
构
之
线
性
表
41
?删除操作： 删除指针P所指向的结点
?步骤
?判断 p是否为头结点，若是，则退出。
?将 p的直接前驱的直接后继指向 p的直接后继。
?将 p的直接后继的直接前驱指向 p的直接前驱。
?释放该结点所占用的存储空间。
^
L
^
……
p
1
2
数
据
结
构
之
线
性
表
42
?算法描述
void delete(DuLinkList L, DuLinkList P)
{
if (p= =L)
return;
else{
p->prior->next=p->next;
p->next->prior=p->prior;
}
free(p);
return;
}
22
数
据
结
构
之
线
性
表
43
?插入操作： 在某双向链表的第i个结点
前插入元素e
?步骤
?取第 i个结点的指针 p；若该元素不存在，
则返回；
?建立新的结点 q，并赋值；
?将 q的前驱指向 p的前驱 , q的后继指向 p;
?将 p的前驱的后继指向 q， p的前驱指向 q;
?返回。
^
p
^
……
L
e
q
第 i个结点
数
据
结
构
之
线
性
表
44
void ListInsert_DuL(DuLinkList L,int i, ElemType e){
if(!(p=GetElem_DuL(L,i))) /*取第 i个元素的地址 p*/
return ERROR;
if(!(q=(DuLinkList)malloc(sizeof(DuLNode))))
return ERROR;
q->data=e; /*新结点赋值 */
q->prior=p->prior; /*q的前驱指向 p的前驱 */
q->next=p; /*q的后继指向 p*/
p->prior->next=q; /*p的前驱的后继指向 q*/
p->prior=q; /*p的前驱指向 q*/
return OK; }
23
数
据
结
构
之
线
性
表
45
1. 3 一元多项式的表示及相加
? 不缺项的一元多项式 Pn( x )
? 数学式： Pn( x )= p0 + p1 x +p2 x +……+ pn x
用线性表： P = (p0 , p1, p2 , … ,pn) 存储每项系数。
例如： P5( x )= 3+6.7x+5.2x + 4x +0x +9x
P=( 3 , 6.7 , 5.2 , 4 , 0 , 9 )
? 两个一元多项式相加
m < n , 求 Rn( x)= Pn(x) + Qm(x)
R=(p0+q0, p1+q1, p2+q2, ... , pm + qm , pm+1, ... , pn)
? 采用顺序存储结构，可以方便地解决不缺项
的一元多项式相加的问题。
2
n
234 5
数
据
结
构
之
线
性
表
46
? 特殊的一元多项式 :大幅度缺项的一元多项式
S(x)=1+3x + 2x
? 数学式： Pn( x )= p1 xa1 + p2 xa2 +... + pm xa
0≤ a1 ≤ a2 ≤ a3 ≤……≤ am
? 线性表： P=( ( p1, a1 ) , ( p2 , a2 ) , ... ,( pm ,
am) )
?顺序存储结构：用于对多项式进行“求值”；
?链式存储结构：用于两个多项式相加。
m
1000
2500
24
数
据
结
构
之
线
性
表
47
? 特殊的一元多项式链式存储结构类型定义：
typedef struct{float coef; //表元素类型定义
int expn;}ElemType;
typedef struct LNode{ //结点及其指针类型定义
ElemType data ;
struct LNode *next ;
}*Link, Lnode ;
typedef struct{ //链表类型定义
Link head , tail ;
int len ; } LinkPoly;
数
据
结
构
之
线
性
表
48
A(x)=7+3x+9x +5x
head
tail
4
A
head
tail
3
B
head
tail
4
C
+
||
B(x)=8x+22x - 9x
C(x)=7+11x+22x +5x
78
717
8.0 1 22.0 7 -9.0 8 ^头结点
7.0 0 3.0 1 9.0 8
5.0 17 ^
817
头结点
7.0 0 11.0 1 5.0 17 ^22.0 7头
25
数
据
结
构
之
线
性
表
49
Void AddPoly(LinkPoly &Pa , LinkPoly &Pb) {
ha=Pa.head; hb=Pb. head; qa=ha->next;qb=hb->next;
while (!Empty(Pa) && !Empty(Pb)){
a=qa->data;b=qb->data;
switch(compare(a.expn , b.expn)){
case 0: sum=a.coef+b.coef;
if(sum) {qa->data.coef=sum; ha=qa;}
else{ DelFirst(Pa, ha,qa);free(qa);}
DelFirst(Pb,hb,qb);free(qb);
qa=ha->next;qb=hb->next;} break;
case -1:ha=qa;qa=ha->next;break;
case 1:DelFirst(Pb,hb,qb);InsFirst(Pa, ha,qb);
ha=qb; qb=hb->next;}
if(!Empty(Pb)) Append(Pa,qb); Free(hb);}
数
据
结
构
之
线
性
表
50
? 本章重点
? 线性表的逻辑结构
? 线性表的物理结构
?顺序表：创建、插入、删除等操作的实现
?链表
?单链表：创建、插入、删除等操作的实现
?循环链表
?双向链表：插入、删除等操作的实现
? 一元多项式的表示和运算
