第二章 线性表
? 2,1 线性表的类型定义
? 2,2 线性表的顺序表示与实现
? 2,3 线性表的链式表示与实现
? 2,3,1 线性链表
? 2,3,2 循环链表
? 2,3,3 双向链表
第二章 线性表
? 线性结构的特点是,
? 存在唯一的, 第一个, 数据元素 ;
? 存在唯一的, 最后一个, 数据元素 ;
? 除第一个外,每个数据元素均有且只有一个前驱
元素 ;
? 除最后一个外,每个数据元素均有且只有一个后
继元素。
2,1 线性表的类型定义
? 线性表举例,
? 字母表 (A,B,C,…,X,Y,Z)
? 数据序列 (6,17,28,50,92,188)
? n个元素的线性表,
? （ a1,a2,…,a i,ai+1,…,a n）
第一个元素
(没有前驱 )
第 i个元素
(有唯一的前驱
和唯一的后继 )
最后一个元素
(没有后继 )
线性表的抽象数据类型 (ADT)
? ADT List{
? 数据对象, D = {ai | ai属于 Elemset,(i=1,2,…,n,
n≥ 0)}
? 数据关系, R1 = {＜ ai-1,ai＞ |ai-1,ai属于 D,(i=2,3,…,n)}
? 基本操作,
? InitList(&L); DestroyList(&L);
? ListInsert(&L,i,e); ListDelete(&L,i,&e);
? 等等
? } ADT List
? InitList(&L); DestroyList(&L);
? ClearList(&L); ListEmpty(L);
? ListLength(L); GetElem(L,i,&e);
? LocateElem(L,e,compare());
? PriorElem(L,cur_e,&pre_e);
? NextElem(L,cur_e,&next_e);
? ListInsert(&L,i,e); ListDelete(&L,i,&e);
? ListTraverse(&L,visited())
线性表 ADT的基本操作,
? InitList(&L)
? 操作结果,构造一个空的线性表 L。
? DestroyList(&L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 销毁线性表 L。
? ClearList(&L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 将线性表 L重置为空表 。
基本操作 (一 )：
? ListEmpty(L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 若线性表 L为空表, 则返回
TURE;否则返回 FALSE。
? ListLength(L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 返回线性表 L中的数据元素个数 。
基本操作 (二 )：
? GetElem(L,i,&e)； 初始条件, 线性表 L已经存
在, 1<=i<= ListLength(L)。
? 操作结果, 用 e返回线性表 L中第 i个数据元素的值 。
? LocateElem(L,e,compare())
? 初始条件, 线性表 L已经存在,compare()是数据元
素判定函数。
? 操作结果, 返回 L中第 1个与 e满足 compare()的数据
元素的位序。若这样的数据元素不存在则返回值为
0。
基本操作 (三 )：
? PriorElem(L,cur_e,&pre_e)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 若 cur_e是 L的数据元素,且不是第一个,则
用 pre_e返回它的前驱,否则操作失败 ; pre_e无意义 。
? NextElem(L,cur_e,&next_e)
? 初始条件, 线性表 L已经存在。
? 操作结果,若 cur_e是 L的数据元素,且不是第最后个,
则用 next_e返回它的后继,否则操作失 败,next_e无
意义。
基本操作 (四 )：
? ListInsert(&L,i,e)
? 初始条件, 线性表 L已经存在,1<=i<=
ListLength(L)+1。
? 操作结果, 在 L的第 i个位置之前插入新的数据元素 e,
L的长度加一。
? 插入前 （ 长度为 n）,
? （ a1,a2,…,ai-1,ai,…,an）
? 插入后 （ 长度为 n+1）,
? （ a1,a2,…,ai-1,e,ai,…,an）
基本操作 (五 )：
? ListDelete(&L,i,&e)
? 初始条件, 线性表 L已经存在,1<=i<=
ListLength(L)。
? 操作结果, 删除 L的第 i个数据元素,并用 e返回其值,
L的长度减一。
? 删除前 （ 长度为 n ）,
? （ a1,a2,…,a i-1,ai,ai+1,…,a n）
? 删除后 （ 长度为 n -1 ）,
? （ a1,a2,…,a i-1,ai+1,…,a n）
? ListTraverse(&L,visited())
基本操作 (六 )：
例 2-1 线性表 La,Lb的合并,
La=La∪ Lb,(算法 2.1)
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);
}
}//union
例 2-1 线性表 La,Lb的合并,
La = (2,5,7,9) Lb=(4,5,6,7)
合并结果,La=(2,5,7,9,4,6)
由本节最后知, 算法 2.1的时间复杂度为
O(ListLength(La)× ListLength(Lb));
例 2-2 非递减线性表 La,Lb的合
并, Lc=La∪ Lb.( 算法 2.2)
La = (3,5,8,11) Lb=(2,6,8,9,11,15,20)
合并结果,Lc=(2,3,5,6,8,8,9,11,11,15,20)
void MergeList(List La,List Lb,List &Lc){
// 已知非递减线性表 La,Lb
//将所有 La和 Lb中的数据元素归并到 Lc中,使 Lc
的数据元素也是非递减的,
}// MergeList 时间复杂度为,
O(ListLength(La)+ ListLength(Lb));
非递减线性表 La,Lb的合并的 C
程序 (一 )
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;}
}
非递减线性表 La,Lb的合并的 C
程序 (续 )
while (i<=La_len) {
GetElem(La,i++,ai); ListInsert(Lc,++k,ai);
}
while (j<=Lb_len) {
GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj);
}
? 线性表 （ a1,a2,…,ai,ai+1,…,an）
的顺序表示 ----
? 用一组地址连续的存贮单元依次存贮线性表
的数据元素,
? Loc(ai+1) = Loc(ai)+ι
? Loc(ai) = Loc(a1)+(i-1)*ι
? 设 ι 为每个数据元素所需的存储大小
2,2 线性表的顺序表示与实现
(物理结构 )
线性表的顺序表示 (图示 )′? ′￠ μ? ?· ?ú ′? ×ì? ?? Dò
b a1 1
b+ |é a2 2
?- ?- ?- ?-
b+(i-1)*| é ai i
?- ?-
b+(n-1)*| é an n
b---为 a1数据元素的存储地址
ι---为 为每个数据元素所需的存储大小
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
Status ListInsert_Sq(Sqlist &L,int i,ElemType e)
{ // 在顺序线性表 L的第 i个位置之前插入新的元素 e
// i的合法值为 1<=i<=ListLength_Sq(L) + 1
ElemType *q,*p,*newbase;
if(i<1 || i>L.length+1) return ERROR;
// i 值不合法
if(L.length>=L.listsize){
// 当前存储空间已满,增加分配
newbase=(ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
// 算法 2.4
if(!newbase)exit(OVERFLOW);
// 存储分配失败
L.elem=newbase;
L.listsize+=LISTINCREMENT;
// 增加存储容量
}
q=&(L.elem[i-1]); // q为插入位置
for(p=&(L.elem[L.length-1]); p>=q; --p)
*(p+1)=*p;
// 插入位置及之后的元素后移
*q=e; // 插入 e
++L.length; // 表长增 1
return OK;
}
Status ListDelete_Sq(Sqlist &L,int i,ElemType *e)
{ // 在顺序线性表 L中删除第 i个元素,并用 e返回其值
// i的合法值为 1<=i<=ListLength_Sq(L)
ElemType *p,*q;
if((i<1)||(i>L.length)) return ERROR;//i值不合法
p=&(L.elem[i-1]); // p为被删除元素的位置
*e=*p; // 被删除元素的值赋给 e
q=(L.elem+L.length-1); // 表尾元素的位置
for(++p;p<=q;++p)
*(p-1)=*p; // 被删除元素之后的元素左移
--L.length; // 表长减 1
return OK;
}
// 算法 2.5
算法 2.4的时间复杂度：
? Eis:插入一个元素所需平均 移动次数,
? n+1
Eis = ∑ 1/(n+1) ( n – i + 1) 则
? i=1
n+1 nEis = 1/(n+1) ∑ ( n – i + 1) = 1/(n+1) ∑ i
? i=1 i=1
? = 1/(n+1) * n(n+1)/2 = n/2
? 因此,算法 2.4的时间复杂度为 O(n) 。
算法 2.5的时间复杂度：
? Eds,删除一个元素所需 平均移动次数
? n n
? Eds = ∑ 1/n( n – i) = 1/n ∑ ( n – i)
? i=1 i=1
? n-1
? = 1/n ∑ i = 1/n * n(n-1)/2 = (n-1)/2
? i=1
? 因此,算法 2.5的时间复杂度为 O(n) 。
实验要求与习题
? 理论习题 2.2,2.10,2.11
? 实验题, ① 写一个主程序来 上机验证算
法 2.3、算法 2.4、算法 2.5； ② 2.12
? 2,1 线性表的类型定义
? 2,2 线性表的顺序表示与实现
? 2,3 线性表的链式表示与实现
? 2,3,1 线性链表
? 2,3,2 循环链表
? 2,3,3 双向链表
第二章 线性表
? 线性结构的特点是,
? 存在唯一的, 第一个, 数据元素 ;
? 存在唯一的, 最后一个, 数据元素 ;
? 除第一个外,每个数据元素均有且只有一个前驱
元素 ;
? 除最后一个外,每个数据元素均有且只有一个后
继元素。
2,1 线性表的类型定义
? 线性表举例,
? 字母表 (A,B,C,…,X,Y,Z)
? 数据序列 (6,17,28,50,92,188)
? n个元素的线性表,
? （ a1,a2,…,a i,ai+1,…,a n）
第一个元素
(没有前驱 )
第 i个元素
(有唯一的前驱
和唯一的后继 )
最后一个元素
(没有后继 )
线性表的抽象数据类型 (ADT)
? ADT List{
? 数据对象, D = {ai | ai属于 Elemset,(i=1,2,…,n,
n≥ 0)}
? 数据关系, R1 = {＜ ai-1,ai＞ |ai-1,ai属于 D,(i=2,3,…,n)}
? 基本操作,
? InitList(&L); DestroyList(&L);
? ListInsert(&L,i,e); ListDelete(&L,i,&e);
? 等等
? } ADT List
? InitList(&L); DestroyList(&L);
? ClearList(&L); ListEmpty(L);
? ListLength(L); GetElem(L,i,&e);
? LocateElem(L,e,compare());
? PriorElem(L,cur_e,&pre_e);
? NextElem(L,cur_e,&next_e);
? ListInsert(&L,i,e); ListDelete(&L,i,&e);
? ListTraverse(&L,visited())
线性表 ADT的基本操作,
? InitList(&L)
? 操作结果,构造一个空的线性表 L。
? DestroyList(&L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 销毁线性表 L。
? ClearList(&L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 将线性表 L重置为空表 。
基本操作 (一 )：
? ListEmpty(L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 若线性表 L为空表, 则返回
TURE;否则返回 FALSE。
? ListLength(L)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 返回线性表 L中的数据元素个数 。
基本操作 (二 )：
? GetElem(L,i,&e)； 初始条件, 线性表 L已经存
在, 1<=i<= ListLength(L)。
? 操作结果, 用 e返回线性表 L中第 i个数据元素的值 。
? LocateElem(L,e,compare())
? 初始条件, 线性表 L已经存在,compare()是数据元
素判定函数。
? 操作结果, 返回 L中第 1个与 e满足 compare()的数据
元素的位序。若这样的数据元素不存在则返回值为
0。
基本操作 (三 )：
? PriorElem(L,cur_e,&pre_e)
? 初始条件, 线性表 L已经存在 。
? 操作结果, 若 cur_e是 L的数据元素,且不是第一个,则
用 pre_e返回它的前驱,否则操作失败 ; pre_e无意义 。
? NextElem(L,cur_e,&next_e)
? 初始条件, 线性表 L已经存在。
? 操作结果,若 cur_e是 L的数据元素,且不是第最后个,
则用 next_e返回它的后继,否则操作失 败,next_e无
意义。
基本操作 (四 )：
? ListInsert(&L,i,e)
? 初始条件, 线性表 L已经存在,1<=i<=
ListLength(L)+1。
? 操作结果, 在 L的第 i个位置之前插入新的数据元素 e,
L的长度加一。
? 插入前 （ 长度为 n）,
? （ a1,a2,…,ai-1,ai,…,an）
? 插入后 （ 长度为 n+1）,
? （ a1,a2,…,ai-1,e,ai,…,an）
基本操作 (五 )：
? ListDelete(&L,i,&e)
? 初始条件, 线性表 L已经存在,1<=i<=
ListLength(L)。
? 操作结果, 删除 L的第 i个数据元素,并用 e返回其值,
L的长度减一。
? 删除前 （ 长度为 n ）,
? （ a1,a2,…,a i-1,ai,ai+1,…,a n）
? 删除后 （ 长度为 n -1 ）,
? （ a1,a2,…,a i-1,ai+1,…,a n）
? ListTraverse(&L,visited())
基本操作 (六 )：
例 2-1 线性表 La,Lb的合并,
La=La∪ Lb,(算法 2.1)
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);
}
}//union
例 2-1 线性表 La,Lb的合并,
La = (2,5,7,9) Lb=(4,5,6,7)
合并结果,La=(2,5,7,9,4,6)
由本节最后知, 算法 2.1的时间复杂度为
O(ListLength(La)× ListLength(Lb));
例 2-2 非递减线性表 La,Lb的合
并, Lc=La∪ Lb.( 算法 2.2)
La = (3,5,8,11) Lb=(2,6,8,9,11,15,20)
合并结果,Lc=(2,3,5,6,8,8,9,11,11,15,20)
void MergeList(List La,List Lb,List &Lc){
// 已知非递减线性表 La,Lb
//将所有 La和 Lb中的数据元素归并到 Lc中,使 Lc
的数据元素也是非递减的,
}// MergeList 时间复杂度为,
O(ListLength(La)+ ListLength(Lb));
非递减线性表 La,Lb的合并的 C
程序 (一 )
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;}
}
非递减线性表 La,Lb的合并的 C
程序 (续 )
while (i<=La_len) {
GetElem(La,i++,ai); ListInsert(Lc,++k,ai);
}
while (j<=Lb_len) {
GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj);
}
? 线性表 （ a1,a2,…,ai,ai+1,…,an）
的顺序表示 ----
? 用一组地址连续的存贮单元依次存贮线性表
的数据元素,
? Loc(ai+1) = Loc(ai)+ι
? Loc(ai) = Loc(a1)+(i-1)*ι
? 设 ι 为每个数据元素所需的存储大小
2,2 线性表的顺序表示与实现
(物理结构 )
线性表的顺序表示 (图示 )′? ′￠ μ? ?· ?ú ′? ×ì? ?? Dò
b a1 1
b+ |é a2 2
?- ?- ?- ?-
b+(i-1)*| é ai i
?- ?-
b+(n-1)*| é an n
b---为 a1数据元素的存储地址
ι---为 为每个数据元素所需的存储大小
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
Status ListInsert_Sq(Sqlist &L,int i,ElemType e)
{ // 在顺序线性表 L的第 i个位置之前插入新的元素 e
// i的合法值为 1<=i<=ListLength_Sq(L) + 1
ElemType *q,*p,*newbase;
if(i<1 || i>L.length+1) return ERROR;
// i 值不合法
if(L.length>=L.listsize){
// 当前存储空间已满,增加分配
newbase=(ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
// 算法 2.4
if(!newbase)exit(OVERFLOW);
// 存储分配失败
L.elem=newbase;
L.listsize+=LISTINCREMENT;
// 增加存储容量
}
q=&(L.elem[i-1]); // q为插入位置
for(p=&(L.elem[L.length-1]); p>=q; --p)
*(p+1)=*p;
// 插入位置及之后的元素后移
*q=e; // 插入 e
++L.length; // 表长增 1
return OK;
}
Status ListDelete_Sq(Sqlist &L,int i,ElemType *e)
{ // 在顺序线性表 L中删除第 i个元素,并用 e返回其值
// i的合法值为 1<=i<=ListLength_Sq(L)
ElemType *p,*q;
if((i<1)||(i>L.length)) return ERROR;//i值不合法
p=&(L.elem[i-1]); // p为被删除元素的位置
*e=*p; // 被删除元素的值赋给 e
q=(L.elem+L.length-1); // 表尾元素的位置
for(++p;p<=q;++p)
*(p-1)=*p; // 被删除元素之后的元素左移
--L.length; // 表长减 1
return OK;
}
// 算法 2.5
算法 2.4的时间复杂度：
? Eis:插入一个元素所需平均 移动次数,
? n+1
Eis = ∑ 1/(n+1) ( n – i + 1) 则
? i=1
n+1 nEis = 1/(n+1) ∑ ( n – i + 1) = 1/(n+1) ∑ i
? i=1 i=1
? = 1/(n+1) * n(n+1)/2 = n/2
? 因此,算法 2.4的时间复杂度为 O(n) 。
算法 2.5的时间复杂度：
? Eds,删除一个元素所需 平均移动次数
? n n
? Eds = ∑ 1/n( n – i) = 1/n ∑ ( n – i)
? i=1 i=1
? n-1
? = 1/n ∑ i = 1/n * n(n-1)/2 = (n-1)/2
? i=1
? 因此,算法 2.5的时间复杂度为 O(n) 。
实验要求与习题
? 理论习题 2.2,2.10,2.11
? 实验题, ① 写一个主程序来 上机验证算
法 2.3、算法 2.4、算法 2.5； ② 2.12
