数据结构 华中科技大学计算机学院 (1)
-------------------------------------------------
第二章 线性表
2.1 线性表的定义
2.1.1 线性表的 逻辑结构
1.线性表 ──
由 n(n≥0) 个数据元素 (a1,a2,...,an)构成的有限序列。
记作,L=(a1,a2,...,an)
a1── 首元素
an── 尾元素
2.表的 长度 (表长 )── 线性表中数据元素的数目。
3.空表 ── 不含数据元素的线性表。
线性表举例例 1,字母表 L1=(A,B,C,...,Z)
表长 26
例 2,姓名表 L2=(李明,陈小平,王林,周爱玲 )
表长 4
例 3,图书登记表序号 书 名 作 者 单价 (元 ) 数量 (册 )
1 程序设计语言 李 明 10.50 500
2 数据结构 陈小平 9.80 450
...,.....,....,....,..
n DOS使用手册 周爱玲 20.50 945
表长 n
线性表的特征对于 L=(a1,a2,...,ai-1,ai,ai+1,...,an)
1.ai-1在 ai之前,称 ai-1是 ai的 直接前驱
(1＜ i≤n)
2.ai+1在 ai之后,称 ai+1是 ai的 直接后继
(1≤i ＜ n)
3.a1没有前驱
4.an没有后继
5.ai(1＜ i＜ n)有且仅有一个直接前驱和一个直接后继
2.1.2抽象数据类型线性表的定义
ADJ List
{ 数据对象,L={ai|ai∈ElemSet,i=1,2,,...n,n>=0}
数据关系,R1={<ai-1,ai>|ai-1∈D,i=1,2,,...n}
基本操作：
1.IiniList(&L) //构造空表 L。
2.LengthList(L) //求表 L的长度
3.GetElem(L,i,&e) //取元素 ai,由 e返回 ai
4.PriorElem(L,ce,&pre_e) //求 ce的前驱,由 pre_e返回
5.InsertElem(&L,i,e) //在元素 ai之前插入新元素 e
6.DeleteElem(&L,i) //删除第 i个元素
7.EmptyList(L) //判断 L是否为空表
8.ClearList(&L) //置 L为空表
......
}ADJ List
说 明
1.删除 表 L中 第 i个数据元素 (1<=i<=n),记作,
DeleteElem(&L,i)
L=(a1,a2,...,ai-1,ai,ai+1,...,an)
指定序号 i,删除 ai ↑
L=(a1,a2,...,ai-1,ai+1,...,an)
2.指定元素值 x,删除 表 L中的 值为 x的元素,记作,
DeleteElem(&L,x)；
3.在元素 ai之前插入新元素 e(1<=i<=n+1)
L=(a1,a2,...,ai-1,ai,...,an)
插入 e ↑
L=(a1,a2,...,ai-1,e,ai,...,an)
4.查找 ----确定元素值 (或数据项的值 )为 e的元素。
给定,L=(a1,a2,...,ai,...,an)和元素 e
若有一个 ai=e，则称,查找成功,,i=1,2,...,n
否则，称,查找失败,。
5.排序 ----按元素值或某个数据项值的递增（或递减）次序重新排列表中各元素的位置。
例,排序前,L=(90,60,80,10,20,30)
排序后,L=(10,20,30,60,80,90)
L变为有序表
6.将表 La和表 Lb合并 为表 Lc
例,设有序表：
La=(2,14,20,45,80)
Lb=(8,10,19,20,22,85,90)
合并为表
Lc=(2,8,10,14,19,20,20,22,45,80,85,90)
7.将表 La复制 为表 Lb
La= (2,14,20,45,80)
Lb= (2,14,20,45,80)
可利用现有操作组成更复杂的操作：
void union(List &La,List &Lb)
{
La_len=List_length(La); //求线性表 La的长度
Lb_len=List_length(Lb); //求线性表 Lb的长度
for (i=1;i<= Lb_len;i++)
{
GetElem(Lb,i,e); //取 Lb的的第 i个数据元素赋给 e
if (!LocateElem(La,e,equal)) //判断 e在 La中是否存在
ListInsert(La,++La_len,e); //不存在则插入
}
}
2.2 线性表的 顺序表示（顺序存储结构 ）
2.2.1.顺序分配 ── 将线性表中的数据元素依次存放到计算机存储器中一组地址连续的存储单元中,这种分配方式称为顺序分配或顺序映像 。由此得到的存储结构称为 顺序存储结构或向量 (一维数组）。
例,a=(30,40,10,55,24,80,66)
内存状态
C语言中静态一维数组的定义：
int a[11]；
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
30 40 10 55 24 80 66
(a1,a1,a2,...an)顺序存储结构的一般形式序号 存储状态 存储地址
1 b
2 b+p
i b+(i-1)*p
n b+(n-1)*p
自由区
maxleng b+(maxleng-1)*p
其中,b----表的首地址 /基地址 /元素 a1的地址。
p----1个数据元素所占存储单元的数目。
maxleng----最大长度,为某个常数。
a1
a2
..,
ai
...
an
//
//
//
2.2.2 线性表顺序结构在 C语言中的定义例 1.分别定义元素所占空间、表长、尾元素的位置
#define maxleng 100
{ ElemType la[maxleng+1]； //下标,0,1,…,maxleng
int length； //当前长度
int last； //an的位置
}
或：
a1 a2,.,ai,.,an
a1 a2,.,ai,.,an
0 1 i–1 n-1 n maxleng
0 1 2 i n maxleng
last=length=n
last=length-1=n-1
线性表顺序结构在 C语言中的定义（一）
例 2.元素所占空间和表长合并为 C语言的一个结构类型：
#define maxleng 100
{ typedef struct
{ ElemType elem[maxleng]； //下标,0,1,...,maxleng-1
int length； //表长
} SqList；
SqList La；
..........
}
其中,typedef---别名定义,SqList----结构类型名
La----结构类型变量名
La.length---表长
La.elem[0]----a1
La.elem[La.length-1]---an
线性表顺序结构在 C语言中的定义（二）
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{ ElemType *elem； //存储空间基地址
int length； //表长
int listsize; //当前分配的存储容量
//（以 sizeof(ElemType)为单位
} SqList；
SqList Lb；
其中,typedef---别名定义,SqList----结构类型名
Lb----结构类型变量名
Lb.length---表长
Lb.elem[0]----a1
Lb.elem[Lb.length-1]---bn
2.2.3 顺序存储结构的 寻址公式
i= 1 2,.,i..,n
地址 = b b+1*p b+(i-1)p b+(n-1)p
假设,线性表的首地址为 b,每个数据元素占 p个存储单元,则表中任意元素 ai(1≤i≤n) 的存储地址是,
LOC(i)=LOC(1)+(i-1)*p
=b+(i-1)*p (1≤i≤n)
例,假设 b=1024,p=4,i=35
LOC(i)=b+(i-1)*p
=1024+(35-1)*4
=1024+34*4
=1160
a1 a2,.,ai,.,an // // //
2.2.4 插入算法实现举例设 L.elem[0..maxleng-1]中有 legth个元素，在
L.elem[i-1]之插入新元素 e,1<=i<=length
例,i=3,e=6,length=6
插入 6之前：
→ → → →
2 5 8 20 30 35 // // //
0 1 2 3 4 5 6 7 8
35,30,20,8 依次后移一个位置插入 6之后：
2 5 6 8 20 30 35 // //
0 1 2 3 4 5 6 7 8
a1 a2,.,ai,.,an // // //
0 1 2,..i-1,.,n-1 maxleng-1
插入操作,类 C”算法,
//设 L.elem[0..maxleng-1]中有 legth个元素，在
L.elem[i-1]之前插入新元素 e,(1<=i<=length)
void Insert(SqList *L,int i,ElemType e)
{ if (i<1||i>L->length+1) return ERROR //i值不合法
if (L->length>=maxleng) exit(OVERFLOW) //溢出
for (j=L->length-1； j>=i-1； j--； )
L->elem[j+1]=L->elem[j]； //向后移动元素
L->elem[i-1]=e； //插入新元素
L->length++； //长度变量增 1
return OK //插入成功
}
a1 a2,.,ai,.,an // // //
0 1 2,..i-1,.,n-1 maxleng-1
插入操作,类 C”算法,
//设 L.elem[0..maxleng-1]中有 legth个元素，在
L.elem[i-1]之前插入新元素 e,(1<=i<=length)
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{ if (i<1||i>L.length+1) return ERROR //i值不合法
if (L.length>=maxleng) exit(OVERFLOW) //溢出
for (j=L.length-1； j>=i-1； j--； )
L.elem[j+1]=L.elem[j]； //向后移动元素
L.elem[i-1]=e； //插入新元素
L.length++； //长度变量增 1
return OK //插入成功
}
a1 a2,.,ai,.,an // // //
0 1 2,..i-1,.,n-1 maxleng-1
插入操作,标准 C”算法,
//设 L->elem[0..maxleng-1]中有 legth个元素，在
L->elem[i-1]之前插入新元素 e,(1<=i<=length)
Status ListInsert_Sq(SqList *L,int i,ElemType e)
{ if (i<1||i>L->length+1) return ERROR //i值不合法
if (L->length>=maxleng) exit(OVERFLOW) //溢出
for (j=L->length-1； j>=i-1； j--； )
L->elem[j+1]=L->elem[j]； //向后移动元素
L->elem[i-1]=e； //插入新元素
L->length++； //长度变量增 1
return OK //插入成功
}
2.2.5 插入操作移动元素次数的分析在（ a1,a2,...,ai,...an)中 ai之前插入新元素 e
( 1<=i<=n+1 )
→ → →
当 i=1 2 3 j n n+1
移动元素次数个数,n n-1 n-2 n-i+1 1 0
假定 pi是在各位置插入元素的概率相同，则插入一个元素时移动元素的平均值是：
n+1
Eis=∑pi(n -i+1)=1/(n+1)*(n+(n-1)+...+1+0)=n/2
i=1
其中,p1=p2=...=pn=p(n+1)=1/(n+1)
a1 a2,,ai,,an
1 2 i n n+1
2.2.6 删除操作及移动元素次数的分析
← ← ←
void delete(SqList *L,int i) /*假定 elem[0]未用 */
{int j;
if (i<1 ||i>L->length) printf(“not exist”);
else { for(j=i;j<=L->length-1;j++)
L->elem[j]=L->elem[j+1];
L->length--;
}
}
1 2 i-1 i i+1 n
a1 a2 … a i-1 ai ai+1 … a n // //
a1 a2 … a i-1 ai+1 … a n // // //
2.2.6 删除操作移动元素次数的分析
← ← ←
当 i=1 2 3,.,i,.,n
移动元素次数个数 = n-1 n-2,.,n-i,.,0
假定 qi是在各位置插入元素的概率相同，则删除一个元素时移动元素的平均值是,
n
Edl=∑qi(n -i)=1/n*((n-1)+...+1+0)=(n-1)/2
i=1
其中,q1=q2=...=qn=1/n
1 2 i-1 i i+1 n
a1 a2 … a i-1 ai ai+1 … a n // //
a1 a2 … a i-1 ai+1 … a n // // //
2.2.7 顺序存储结构的评价
1.优点,
(1)是一种随机存取结构，存取任何元素的时间是一个常数，速度快；
(2)结构简单，逻辑上相邻的元素在物理上也是相邻的；
(3)不使用指针，节省存储空间。
2.缺点,
(1)插入和删除元素要移动大量元素，消耗大量时间；
(2)需要一个连续的存储空间；
(3)插入元素可能发生,溢出,；
(4)自由区中的存储空间不能被其它数据占用 (共享 )。
内存,2k 占用 5k 占用 3k
课外作业：
一、单项选择题 (从下列各题四个备选答案中选出一个正确答案,将其代号 (A,B,C,D)写在题干前面的括号内）
( )1.一个数据对象是 ____的集合。
A.相同类型的数据项 B.相同类型的数据元素
C.不同类型的数据项 D.不同类型的数据元素
( )2.____是一个线性表。
A.(1,3,5,7) B.(1,2,3,4,...)
C.{A,B,C,D,E} D.{'a','b','c'}
二、简要回答,线性表的顺序存储结构有什么优点和缺点?
三,已知线性表 L=(a1,a2,...,an)存放在一维数组 A[0..n-1]
中,将线性表 L就地逆置为 L=(an,...,a2,a1),试写出算法。
-------------------------------------------------
第二章 线性表
2.1 线性表的定义
2.1.1 线性表的 逻辑结构
1.线性表 ──
由 n(n≥0) 个数据元素 (a1,a2,...,an)构成的有限序列。
记作,L=(a1,a2,...,an)
a1── 首元素
an── 尾元素
2.表的 长度 (表长 )── 线性表中数据元素的数目。
3.空表 ── 不含数据元素的线性表。
线性表举例例 1,字母表 L1=(A,B,C,...,Z)
表长 26
例 2,姓名表 L2=(李明,陈小平,王林,周爱玲 )
表长 4
例 3,图书登记表序号 书 名 作 者 单价 (元 ) 数量 (册 )
1 程序设计语言 李 明 10.50 500
2 数据结构 陈小平 9.80 450
...,.....,....,....,..
n DOS使用手册 周爱玲 20.50 945
表长 n
线性表的特征对于 L=(a1,a2,...,ai-1,ai,ai+1,...,an)
1.ai-1在 ai之前,称 ai-1是 ai的 直接前驱
(1＜ i≤n)
2.ai+1在 ai之后,称 ai+1是 ai的 直接后继
(1≤i ＜ n)
3.a1没有前驱
4.an没有后继
5.ai(1＜ i＜ n)有且仅有一个直接前驱和一个直接后继
2.1.2抽象数据类型线性表的定义
ADJ List
{ 数据对象,L={ai|ai∈ElemSet,i=1,2,,...n,n>=0}
数据关系,R1={<ai-1,ai>|ai-1∈D,i=1,2,,...n}
基本操作：
1.IiniList(&L) //构造空表 L。
2.LengthList(L) //求表 L的长度
3.GetElem(L,i,&e) //取元素 ai,由 e返回 ai
4.PriorElem(L,ce,&pre_e) //求 ce的前驱,由 pre_e返回
5.InsertElem(&L,i,e) //在元素 ai之前插入新元素 e
6.DeleteElem(&L,i) //删除第 i个元素
7.EmptyList(L) //判断 L是否为空表
8.ClearList(&L) //置 L为空表
......
}ADJ List
说 明
1.删除 表 L中 第 i个数据元素 (1<=i<=n),记作,
DeleteElem(&L,i)
L=(a1,a2,...,ai-1,ai,ai+1,...,an)
指定序号 i,删除 ai ↑
L=(a1,a2,...,ai-1,ai+1,...,an)
2.指定元素值 x,删除 表 L中的 值为 x的元素,记作,
DeleteElem(&L,x)；
3.在元素 ai之前插入新元素 e(1<=i<=n+1)
L=(a1,a2,...,ai-1,ai,...,an)
插入 e ↑
L=(a1,a2,...,ai-1,e,ai,...,an)
4.查找 ----确定元素值 (或数据项的值 )为 e的元素。
给定,L=(a1,a2,...,ai,...,an)和元素 e
若有一个 ai=e，则称,查找成功,,i=1,2,...,n
否则，称,查找失败,。
5.排序 ----按元素值或某个数据项值的递增（或递减）次序重新排列表中各元素的位置。
例,排序前,L=(90,60,80,10,20,30)
排序后,L=(10,20,30,60,80,90)
L变为有序表
6.将表 La和表 Lb合并 为表 Lc
例,设有序表：
La=(2,14,20,45,80)
Lb=(8,10,19,20,22,85,90)
合并为表
Lc=(2,8,10,14,19,20,20,22,45,80,85,90)
7.将表 La复制 为表 Lb
La= (2,14,20,45,80)
Lb= (2,14,20,45,80)
可利用现有操作组成更复杂的操作：
void union(List &La,List &Lb)
{
La_len=List_length(La); //求线性表 La的长度
Lb_len=List_length(Lb); //求线性表 Lb的长度
for (i=1;i<= Lb_len;i++)
{
GetElem(Lb,i,e); //取 Lb的的第 i个数据元素赋给 e
if (!LocateElem(La,e,equal)) //判断 e在 La中是否存在
ListInsert(La,++La_len,e); //不存在则插入
}
}
2.2 线性表的 顺序表示（顺序存储结构 ）
2.2.1.顺序分配 ── 将线性表中的数据元素依次存放到计算机存储器中一组地址连续的存储单元中,这种分配方式称为顺序分配或顺序映像 。由此得到的存储结构称为 顺序存储结构或向量 (一维数组）。
例,a=(30,40,10,55,24,80,66)
内存状态
C语言中静态一维数组的定义：
int a[11]；
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
30 40 10 55 24 80 66
(a1,a1,a2,...an)顺序存储结构的一般形式序号 存储状态 存储地址
1 b
2 b+p
i b+(i-1)*p
n b+(n-1)*p
自由区
maxleng b+(maxleng-1)*p
其中,b----表的首地址 /基地址 /元素 a1的地址。
p----1个数据元素所占存储单元的数目。
maxleng----最大长度,为某个常数。
a1
a2
..,
ai
...
an
//
//
//
2.2.2 线性表顺序结构在 C语言中的定义例 1.分别定义元素所占空间、表长、尾元素的位置
#define maxleng 100
{ ElemType la[maxleng+1]； //下标,0,1,…,maxleng
int length； //当前长度
int last； //an的位置
}
或：
a1 a2,.,ai,.,an
a1 a2,.,ai,.,an
0 1 i–1 n-1 n maxleng
0 1 2 i n maxleng
last=length=n
last=length-1=n-1
线性表顺序结构在 C语言中的定义（一）
例 2.元素所占空间和表长合并为 C语言的一个结构类型：
#define maxleng 100
{ typedef struct
{ ElemType elem[maxleng]； //下标,0,1,...,maxleng-1
int length； //表长
} SqList；
SqList La；
..........
}
其中,typedef---别名定义,SqList----结构类型名
La----结构类型变量名
La.length---表长
La.elem[0]----a1
La.elem[La.length-1]---an
线性表顺序结构在 C语言中的定义（二）
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{ ElemType *elem； //存储空间基地址
int length； //表长
int listsize; //当前分配的存储容量
//（以 sizeof(ElemType)为单位
} SqList；
SqList Lb；
其中,typedef---别名定义,SqList----结构类型名
Lb----结构类型变量名
Lb.length---表长
Lb.elem[0]----a1
Lb.elem[Lb.length-1]---bn
2.2.3 顺序存储结构的 寻址公式
i= 1 2,.,i..,n
地址 = b b+1*p b+(i-1)p b+(n-1)p
假设,线性表的首地址为 b,每个数据元素占 p个存储单元,则表中任意元素 ai(1≤i≤n) 的存储地址是,
LOC(i)=LOC(1)+(i-1)*p
=b+(i-1)*p (1≤i≤n)
例,假设 b=1024,p=4,i=35
LOC(i)=b+(i-1)*p
=1024+(35-1)*4
=1024+34*4
=1160
a1 a2,.,ai,.,an // // //
2.2.4 插入算法实现举例设 L.elem[0..maxleng-1]中有 legth个元素，在
L.elem[i-1]之插入新元素 e,1<=i<=length
例,i=3,e=6,length=6
插入 6之前：
→ → → →
2 5 8 20 30 35 // // //
0 1 2 3 4 5 6 7 8
35,30,20,8 依次后移一个位置插入 6之后：
2 5 6 8 20 30 35 // //
0 1 2 3 4 5 6 7 8
a1 a2,.,ai,.,an // // //
0 1 2,..i-1,.,n-1 maxleng-1
插入操作,类 C”算法,
//设 L.elem[0..maxleng-1]中有 legth个元素，在
L.elem[i-1]之前插入新元素 e,(1<=i<=length)
void Insert(SqList *L,int i,ElemType e)
{ if (i<1||i>L->length+1) return ERROR //i值不合法
if (L->length>=maxleng) exit(OVERFLOW) //溢出
for (j=L->length-1； j>=i-1； j--； )
L->elem[j+1]=L->elem[j]； //向后移动元素
L->elem[i-1]=e； //插入新元素
L->length++； //长度变量增 1
return OK //插入成功
}
a1 a2,.,ai,.,an // // //
0 1 2,..i-1,.,n-1 maxleng-1
插入操作,类 C”算法,
//设 L.elem[0..maxleng-1]中有 legth个元素，在
L.elem[i-1]之前插入新元素 e,(1<=i<=length)
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{ if (i<1||i>L.length+1) return ERROR //i值不合法
if (L.length>=maxleng) exit(OVERFLOW) //溢出
for (j=L.length-1； j>=i-1； j--； )
L.elem[j+1]=L.elem[j]； //向后移动元素
L.elem[i-1]=e； //插入新元素
L.length++； //长度变量增 1
return OK //插入成功
}
a1 a2,.,ai,.,an // // //
0 1 2,..i-1,.,n-1 maxleng-1
插入操作,标准 C”算法,
//设 L->elem[0..maxleng-1]中有 legth个元素，在
L->elem[i-1]之前插入新元素 e,(1<=i<=length)
Status ListInsert_Sq(SqList *L,int i,ElemType e)
{ if (i<1||i>L->length+1) return ERROR //i值不合法
if (L->length>=maxleng) exit(OVERFLOW) //溢出
for (j=L->length-1； j>=i-1； j--； )
L->elem[j+1]=L->elem[j]； //向后移动元素
L->elem[i-1]=e； //插入新元素
L->length++； //长度变量增 1
return OK //插入成功
}
2.2.5 插入操作移动元素次数的分析在（ a1,a2,...,ai,...an)中 ai之前插入新元素 e
( 1<=i<=n+1 )
→ → →
当 i=1 2 3 j n n+1
移动元素次数个数,n n-1 n-2 n-i+1 1 0
假定 pi是在各位置插入元素的概率相同，则插入一个元素时移动元素的平均值是：
n+1
Eis=∑pi(n -i+1)=1/(n+1)*(n+(n-1)+...+1+0)=n/2
i=1
其中,p1=p2=...=pn=p(n+1)=1/(n+1)
a1 a2,,ai,,an
1 2 i n n+1
2.2.6 删除操作及移动元素次数的分析
← ← ←
void delete(SqList *L,int i) /*假定 elem[0]未用 */
{int j;
if (i<1 ||i>L->length) printf(“not exist”);
else { for(j=i;j<=L->length-1;j++)
L->elem[j]=L->elem[j+1];
L->length--;
}
}
1 2 i-1 i i+1 n
a1 a2 … a i-1 ai ai+1 … a n // //
a1 a2 … a i-1 ai+1 … a n // // //
2.2.6 删除操作移动元素次数的分析
← ← ←
当 i=1 2 3,.,i,.,n
移动元素次数个数 = n-1 n-2,.,n-i,.,0
假定 qi是在各位置插入元素的概率相同，则删除一个元素时移动元素的平均值是,
n
Edl=∑qi(n -i)=1/n*((n-1)+...+1+0)=(n-1)/2
i=1
其中,q1=q2=...=qn=1/n
1 2 i-1 i i+1 n
a1 a2 … a i-1 ai ai+1 … a n // //
a1 a2 … a i-1 ai+1 … a n // // //
2.2.7 顺序存储结构的评价
1.优点,
(1)是一种随机存取结构，存取任何元素的时间是一个常数，速度快；
(2)结构简单，逻辑上相邻的元素在物理上也是相邻的；
(3)不使用指针，节省存储空间。
2.缺点,
(1)插入和删除元素要移动大量元素，消耗大量时间；
(2)需要一个连续的存储空间；
(3)插入元素可能发生,溢出,；
(4)自由区中的存储空间不能被其它数据占用 (共享 )。
内存,2k 占用 5k 占用 3k
课外作业：
一、单项选择题 (从下列各题四个备选答案中选出一个正确答案,将其代号 (A,B,C,D)写在题干前面的括号内）
( )1.一个数据对象是 ____的集合。
A.相同类型的数据项 B.相同类型的数据元素
C.不同类型的数据项 D.不同类型的数据元素
( )2.____是一个线性表。
A.(1,3,5,7) B.(1,2,3,4,...)
C.{A,B,C,D,E} D.{'a','b','c'}
二、简要回答,线性表的顺序存储结构有什么优点和缺点?
三,已知线性表 L=(a1,a2,...,an)存放在一维数组 A[0..n-1]
中,将线性表 L就地逆置为 L=(an,...,a2,a1),试写出算法。
