1
线性结构的定义：
若结构是非空有限集, 则有且仅有一个开始结点和一个
终端结点, 并且所有结点都最多只有一个直接前趋和一个直
接后继 。 → 可表示为,（ a1,a2,……,an）
简言之，线性结构反映结点间的逻辑关系是 的。
特点 ① 只有一个首结点和尾结点；
特点 ② 除首尾结点外, 其他结点只有一个直接前驱和一个
直接后继 。
线性结构包括,线性表、堆栈、队列、字符串、数组
等，其中最典型、最常用的是 ------ 线性表
一对一 (1:1)
2
第 2章 线性表
2.1 线性表的基本概念
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 应用举例
3
2.1 线性表的基本概念
１、线性表
它是一种最简单的线性结构。是一种可以在任
意位置进行插入和删除数据元素操作的，由 n（ n≥0)
个相同类型数据元素 a0,a1,…,a n-1组成的线性结
构。
4
（ a0,a1,… ai-1,ai,ai＋ 1, …,an-1）
线性表的逻辑结构：
n=0时称为
数据元素
线性起点 ai的直接前趋 ai的直接后继
下标,是元素的
序号，表示元素
在表中的位置
n为元素总
个数，即表
长。 n≥0空表
线性终点
5
（ A,B,C,D,……,Z ）
学号 姓名 性别 年龄 班级
012003010622 陈建武 男 19 2003级电信 0301班
012003010704 赵玉凤 女 18 2003级电信 0302班
012003010813 王 泽 男 19 2003级电信 0303班
012003010906 薛 荃 男 19 2003级电信 0304班
012003011018 王 春 男 19 2003级电信 0305班
：,,,,
例 2 分析学生情况登记表是什么结构。
分析,数据元素都是同类型（ 记录 ），元素间关系是线性的。
分析,数据元素都是同类型（ 字母 ）,元素间关系是线性的。
注意：同一线性表中的元素必定具有相同特性 ！
例 1 分析 26 个英文字母组成的英文表是什么结构。
6
２、线性表抽象数据类型
它包括两个方面：
数据集合：｛ a0,a1,…,a n-1 ｝ ai的数据类型为
DataType
操作集合, (1)ListInitiate(L) 初始化线性表
(2)ListInsert(L,i,x) 插入数据元素
(3)ListLength(L) 求当前数据元素个数
(4)ListDelete(L,i,x) 删除数据元素
(5)ListGet(L,i,x) 取数据元素
等
7
3、线性表的存储结构
(1)顺序存储结构,它是使用一片 地址连续 的有限内存单
元空间存储数据元素的一种计算机存储数据方法。
特点,(任意两个在逻辑上相邻的数据元素在物理位置
上也必然相邻 )逻辑上相邻的元素，物理上也相邻。
(2)链式存储结构,它是把数据元素和指针定义成一个
存储体，使用指针把发生联系的数据元素链接起来
的一种计算机存储数据方法。
特点,任意两个在 逻辑上相邻 的数据元素在 物理上不
一定相邻,数据元素的逻辑次序是通过链中的指针
链接实现的。
8
2.2 线性表的顺序表示和实现
一, 顺序表的存储结构
二,顺序表的实现
三,顺序表的运算效率分析
9
一,顺序表的存储结构表示
1,顺序表, 用一组 地址连续 的存储单元依次存储线
性表的各个数据元素。即采用顺序存储结构的线性
表。它通常采用静态数组实现数据元素的存储。
可以利用 数组 V[n]来实现
注意：在 C语言中数组的下标是从 0开始，即：
V[n]的有效范围是从 V[0]～ V[n-1]
10
(1) 逻辑上相邻的数据元素，其物理上也相邻；
(2) 若已知表中首元素在存储器中的位置，则其他元
素存放位置亦可求出 （ 利用数组 V[n]的 下标 ）。
设首元素 a0的存放地址为 LOC(a0)（ 称为 首地址 ），
设每个元素占用存储空间（地址长度）为 L字节，
则表中任一数据元素的 存放地址 为：
LOC ( ai+1 ) = LOC( ai ) + L
LOC ( ai ) = LOC( a0 ) + L *i
对上述公式的解释如图所示
2、线性表顺序存储特点：
11
a0
a1
……
ai
ai+1
……
an-1
地址 内容 元素在表中的位序
0
i
1
n-1
空闲区
i+1
Lb=LOC(a0)
b + L
b +iL
b +(n-1)L
b +(MaxSize-1)L
LOC ( ai ) = LOC( a0 ) + L *i
3、线性表的顺序存储结构示意图
12
4、用 C语言描述
typedef struct
{
DateType list[MaxSize];
int size;
}SeqList;
/* MaxSize表示数组的最大元素个数,list表示顺序表
的数组名,size表示顺序表中当前存储的数据元素个
数，它必须满足 size≤ MaxSize,SeqList是该结构体
的名字。 */
13
设有一维数组 Ｍ,下标的范围是 ０到９,
每个数组元素用相邻的 ５个字节 存储。存储器
按字节编址，设存储数组元素 Ｍ [０ ]的第一个
字节的地址是 ９８,则 Ｍ [３ ]的第一个字节的
地址是多少？ 113
LOC( M[3] ) = 98 + 5 × 3 =113
解,已知地址计算通式为：
LOC(ai) = LOC(a0) + L *i
例 1
14
char V[30];
void build() /*字母线性表的生成, 即 建表操作
*/
{ int i;
V[0]='a';
for( i=1; i<=n-1; i++ )
V[i]=V[i-1]+1;
}
核心语句：
方法 1 V[i]= V[i-1]+1;
方法 2 V[i]=’a’+i;
方法 3 V[i]=97+i;
例 2 用数组 V来存放 26个英文字母组成的线性表
（ a,b,c,…, z），写出在顺序结构上 生成 和
显示 该表的 C语言程序。
15
void main(void) /*主函数, 字母线性表的 生成和输出 */
{ n=26; /* n是表长, 是数据元素的个数, 而不是 V的
实际下标 */
build( );
display( );
}
void display( ) /*字母线性表的显示, 即 读表操作 */
{ int i;
for( i=0; i<=n-1; i++ )
printf( "%c",v[i] );
printf( "\n " );
}
执行结果,a b c d e f g h i j k l m n o p q r s t u v w x y z
16
二,顺序表的实现（或操作）
数据结构的基本运算：
修改、插入、删除,查找、排序
1) 修改 通过数组的下标便可访问某个特定元素并
修改之。
核心语句, V[i]=x;
显然，顺序表修改操作的时间效率是 O(1)
17
在线性表（ n个元素）的第 i个位置 前 插入一个元素
实现步骤：
? 将第 n至第 i 位的元素向后移动一个位置；
? 将要插入的元素写到第 i个位置；
? 表长加 1。
注意,事先应判断, 插入位置 i 是否合法?表是否已满?
for (j=n-1; j>=i; j--)
a[j+1]=a[ j ];
a[ i ]=x;
n++;
// 元素后移一个位置
// 插入 x
// 表长加 1
核
心
语
句：
2)插入
18
在线性表的第 i个位置前插入一个元素的示意图如下：
12
13
21
24
28
30
42
77
12
13
21
24
25
28
30
42
77
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
9
插入 25?
19
实现步骤：
? 将第 i+1至第 n 位的元素向前移动一个位置；
? 表长减 1。
注意：事先需要判断,删除位置 i 是否合法?
删除线性表的第 i个位置上的元素
for ( j=i+1; j<=n-1; j++ )
a[j-1]=a[j];
n--;
// 元素前移一个位置
// 表长减 1
核心语句：
3)删除
20
1
2
3
4
5
6
7
8
9
12
13
21
24
25
28
30
42
77
1
2
3
4
5
6
7
8
12
13
21
24
28
30
42
77
删除顺序表中某个指定的元素的示意图如下：
21
例：建立一个线性表，先依次输入数据元素 1,2，
3,4,…, 10，然后删除５，最后依次显示当前
线性表中的数据元素。假设该线性的数据元素个
数最坏情况下不会超过 100个。
实现方法：
1、采用直接编写 一个主函数 实现。
2、利用已设计实现的 抽象数据类型模块 。（存
放在头文件名为 SeqList.h中，通过 #include
“SeqList.h” ）
22
三,顺序表操作的效率分析
? 算法时间主要耗费在 移动元素 的操作上，因此
计算时间复杂度的基本操作（最深层语句频度）
T(n)= O (移动 元素次数 )
而移动元素的个数取决于插入或删除元素的位置,
思考,若插入在尾结点之后，则根本无需移动（特别快）；
若插入在首结点之前，则表中元素全部要后移（特别慢）；
应当考虑在各种位置插入（共 n+1种可能）的 平均 移动次数才合理。
时间效率分析,
23
推导,假定在每个元素位置上插入 x的可能性都一样 （ 即
概率 P相同 ）, 则应当这样来计算平均执行时间：
将所有位置的执行时间相加，然后取平均。
若在首结点前插入, 需要移动的元素最多, 后移 n次；
若在 a1后面插入, 要后移 n-1个元素, 后移次数为 n-1;
……
若在 an-1后面插入, 要后移 1个元素；
若在尾结点 an之后插入, 则后移 0个元素；
所有可能的元素移动次数合计, 0+1+… +n = n(n+1)/2
故插入时的平均移动次数为,n(n+1)/2÷ （ n+1） ＝ n/2≈ O(n)
共有多少种插入形式?—— 连头带尾有 n+1种 !
24
同理可证,顺序表删除一元素的时间效率为,
T（ n)=(n-1)/2 ≈ O(n)
插入
效率：
删除
效率：
11 1
( 1 ) ( 1 )12
nn
i s i
ii
nE p n i n i
n
??
??
? ? ? ? ? ? ????
11
11( ) ( )
2
nn
d l i
ii
nE q n i n i
n??
?? ? ? ? ???
教材 P33有对执行效率的推导,（与课本略有区别）
即插入、删除算法的平均
时间复杂度为 O(n)
25
链式存储结构
本节小结
线性表 顺序存储结构特点,逻辑关系上相邻的两个元素
在物理存储位置上也相邻；
优点,可以随机存取表中任一元素，方便快捷；
缺点,在插入或删除某一元素时，需要移动大量元素。
解决问题的思路,改用另一种线性存储方式：
26
作业：
P55 2-1,2-2,2-11,2-15
线性结构的定义：
若结构是非空有限集, 则有且仅有一个开始结点和一个
终端结点, 并且所有结点都最多只有一个直接前趋和一个直
接后继 。 → 可表示为,（ a1,a2,……,an）
简言之，线性结构反映结点间的逻辑关系是 的。
特点 ① 只有一个首结点和尾结点；
特点 ② 除首尾结点外, 其他结点只有一个直接前驱和一个
直接后继 。
线性结构包括,线性表、堆栈、队列、字符串、数组
等，其中最典型、最常用的是 ------ 线性表
一对一 (1:1)
2
第 2章 线性表
2.1 线性表的基本概念
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 应用举例
3
2.1 线性表的基本概念
１、线性表
它是一种最简单的线性结构。是一种可以在任
意位置进行插入和删除数据元素操作的，由 n（ n≥0)
个相同类型数据元素 a0,a1,…,a n-1组成的线性结
构。
4
（ a0,a1,… ai-1,ai,ai＋ 1, …,an-1）
线性表的逻辑结构：
n=0时称为
数据元素
线性起点 ai的直接前趋 ai的直接后继
下标,是元素的
序号，表示元素
在表中的位置
n为元素总
个数，即表
长。 n≥0空表
线性终点
5
（ A,B,C,D,……,Z ）
学号 姓名 性别 年龄 班级
012003010622 陈建武 男 19 2003级电信 0301班
012003010704 赵玉凤 女 18 2003级电信 0302班
012003010813 王 泽 男 19 2003级电信 0303班
012003010906 薛 荃 男 19 2003级电信 0304班
012003011018 王 春 男 19 2003级电信 0305班
：,,,,
例 2 分析学生情况登记表是什么结构。
分析,数据元素都是同类型（ 记录 ），元素间关系是线性的。
分析,数据元素都是同类型（ 字母 ）,元素间关系是线性的。
注意：同一线性表中的元素必定具有相同特性 ！
例 1 分析 26 个英文字母组成的英文表是什么结构。
6
２、线性表抽象数据类型
它包括两个方面：
数据集合：｛ a0,a1,…,a n-1 ｝ ai的数据类型为
DataType
操作集合, (1)ListInitiate(L) 初始化线性表
(2)ListInsert(L,i,x) 插入数据元素
(3)ListLength(L) 求当前数据元素个数
(4)ListDelete(L,i,x) 删除数据元素
(5)ListGet(L,i,x) 取数据元素
等
7
3、线性表的存储结构
(1)顺序存储结构,它是使用一片 地址连续 的有限内存单
元空间存储数据元素的一种计算机存储数据方法。
特点,(任意两个在逻辑上相邻的数据元素在物理位置
上也必然相邻 )逻辑上相邻的元素，物理上也相邻。
(2)链式存储结构,它是把数据元素和指针定义成一个
存储体，使用指针把发生联系的数据元素链接起来
的一种计算机存储数据方法。
特点,任意两个在 逻辑上相邻 的数据元素在 物理上不
一定相邻,数据元素的逻辑次序是通过链中的指针
链接实现的。
8
2.2 线性表的顺序表示和实现
一, 顺序表的存储结构
二,顺序表的实现
三,顺序表的运算效率分析
9
一,顺序表的存储结构表示
1,顺序表, 用一组 地址连续 的存储单元依次存储线
性表的各个数据元素。即采用顺序存储结构的线性
表。它通常采用静态数组实现数据元素的存储。
可以利用 数组 V[n]来实现
注意：在 C语言中数组的下标是从 0开始，即：
V[n]的有效范围是从 V[0]～ V[n-1]
10
(1) 逻辑上相邻的数据元素，其物理上也相邻；
(2) 若已知表中首元素在存储器中的位置，则其他元
素存放位置亦可求出 （ 利用数组 V[n]的 下标 ）。
设首元素 a0的存放地址为 LOC(a0)（ 称为 首地址 ），
设每个元素占用存储空间（地址长度）为 L字节，
则表中任一数据元素的 存放地址 为：
LOC ( ai+1 ) = LOC( ai ) + L
LOC ( ai ) = LOC( a0 ) + L *i
对上述公式的解释如图所示
2、线性表顺序存储特点：
11
a0
a1
……
ai
ai+1
……
an-1
地址 内容 元素在表中的位序
0
i
1
n-1
空闲区
i+1
Lb=LOC(a0)
b + L
b +iL
b +(n-1)L
b +(MaxSize-1)L
LOC ( ai ) = LOC( a0 ) + L *i
3、线性表的顺序存储结构示意图
12
4、用 C语言描述
typedef struct
{
DateType list[MaxSize];
int size;
}SeqList;
/* MaxSize表示数组的最大元素个数,list表示顺序表
的数组名,size表示顺序表中当前存储的数据元素个
数，它必须满足 size≤ MaxSize,SeqList是该结构体
的名字。 */
13
设有一维数组 Ｍ,下标的范围是 ０到９,
每个数组元素用相邻的 ５个字节 存储。存储器
按字节编址，设存储数组元素 Ｍ [０ ]的第一个
字节的地址是 ９８,则 Ｍ [３ ]的第一个字节的
地址是多少？ 113
LOC( M[3] ) = 98 + 5 × 3 =113
解,已知地址计算通式为：
LOC(ai) = LOC(a0) + L *i
例 1
14
char V[30];
void build() /*字母线性表的生成, 即 建表操作
*/
{ int i;
V[0]='a';
for( i=1; i<=n-1; i++ )
V[i]=V[i-1]+1;
}
核心语句：
方法 1 V[i]= V[i-1]+1;
方法 2 V[i]=’a’+i;
方法 3 V[i]=97+i;
例 2 用数组 V来存放 26个英文字母组成的线性表
（ a,b,c,…, z），写出在顺序结构上 生成 和
显示 该表的 C语言程序。
15
void main(void) /*主函数, 字母线性表的 生成和输出 */
{ n=26; /* n是表长, 是数据元素的个数, 而不是 V的
实际下标 */
build( );
display( );
}
void display( ) /*字母线性表的显示, 即 读表操作 */
{ int i;
for( i=0; i<=n-1; i++ )
printf( "%c",v[i] );
printf( "\n " );
}
执行结果,a b c d e f g h i j k l m n o p q r s t u v w x y z
16
二,顺序表的实现（或操作）
数据结构的基本运算：
修改、插入、删除,查找、排序
1) 修改 通过数组的下标便可访问某个特定元素并
修改之。
核心语句, V[i]=x;
显然，顺序表修改操作的时间效率是 O(1)
17
在线性表（ n个元素）的第 i个位置 前 插入一个元素
实现步骤：
? 将第 n至第 i 位的元素向后移动一个位置；
? 将要插入的元素写到第 i个位置；
? 表长加 1。
注意,事先应判断, 插入位置 i 是否合法?表是否已满?
for (j=n-1; j>=i; j--)
a[j+1]=a[ j ];
a[ i ]=x;
n++;
// 元素后移一个位置
// 插入 x
// 表长加 1
核
心
语
句：
2)插入
18
在线性表的第 i个位置前插入一个元素的示意图如下：
12
13
21
24
28
30
42
77
12
13
21
24
25
28
30
42
77
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
9
插入 25?
19
实现步骤：
? 将第 i+1至第 n 位的元素向前移动一个位置；
? 表长减 1。
注意：事先需要判断,删除位置 i 是否合法?
删除线性表的第 i个位置上的元素
for ( j=i+1; j<=n-1; j++ )
a[j-1]=a[j];
n--;
// 元素前移一个位置
// 表长减 1
核心语句：
3)删除
20
1
2
3
4
5
6
7
8
9
12
13
21
24
25
28
30
42
77
1
2
3
4
5
6
7
8
12
13
21
24
28
30
42
77
删除顺序表中某个指定的元素的示意图如下：
21
例：建立一个线性表，先依次输入数据元素 1,2，
3,4,…, 10，然后删除５，最后依次显示当前
线性表中的数据元素。假设该线性的数据元素个
数最坏情况下不会超过 100个。
实现方法：
1、采用直接编写 一个主函数 实现。
2、利用已设计实现的 抽象数据类型模块 。（存
放在头文件名为 SeqList.h中，通过 #include
“SeqList.h” ）
22
三,顺序表操作的效率分析
? 算法时间主要耗费在 移动元素 的操作上，因此
计算时间复杂度的基本操作（最深层语句频度）
T(n)= O (移动 元素次数 )
而移动元素的个数取决于插入或删除元素的位置,
思考,若插入在尾结点之后，则根本无需移动（特别快）；
若插入在首结点之前，则表中元素全部要后移（特别慢）；
应当考虑在各种位置插入（共 n+1种可能）的 平均 移动次数才合理。
时间效率分析,
23
推导,假定在每个元素位置上插入 x的可能性都一样 （ 即
概率 P相同 ）, 则应当这样来计算平均执行时间：
将所有位置的执行时间相加，然后取平均。
若在首结点前插入, 需要移动的元素最多, 后移 n次；
若在 a1后面插入, 要后移 n-1个元素, 后移次数为 n-1;
……
若在 an-1后面插入, 要后移 1个元素；
若在尾结点 an之后插入, 则后移 0个元素；
所有可能的元素移动次数合计, 0+1+… +n = n(n+1)/2
故插入时的平均移动次数为,n(n+1)/2÷ （ n+1） ＝ n/2≈ O(n)
共有多少种插入形式?—— 连头带尾有 n+1种 !
24
同理可证,顺序表删除一元素的时间效率为,
T（ n)=(n-1)/2 ≈ O(n)
插入
效率：
删除
效率：
11 1
( 1 ) ( 1 )12
nn
i s i
ii
nE p n i n i
n
??
??
? ? ? ? ? ? ????
11
11( ) ( )
2
nn
d l i
ii
nE q n i n i
n??
?? ? ? ? ???
教材 P33有对执行效率的推导,（与课本略有区别）
即插入、删除算法的平均
时间复杂度为 O(n)
25
链式存储结构
本节小结
线性表 顺序存储结构特点,逻辑关系上相邻的两个元素
在物理存储位置上也相邻；
优点,可以随机存取表中任一元素，方便快捷；
缺点,在插入或删除某一元素时，需要移动大量元素。
解决问题的思路,改用另一种线性存储方式：
26
作业：
P55 2-1,2-2,2-11,2-15
