线性起点
数据元素
ai的直接前趋
ai的直接后继
下标，是元素的 序号，表示元素 在表中的位置
n=0时称为 空表
线性终点
n为元素总个
数，即表长
5
03/03/2021
线性表特性
1. 线性表中元素之间的关系是线性关系： 2. 存在唯一的第一个元素； 3. 存在唯一的最后一个元素； 4. 除第一个元素之外，每个元素均只有一个直接
1. struct bookinfo
2. {
3.
int No;
// 图书编号
4.
char *name; // 图书名称
5.
char *auther; // 作者名称
6. ...;
7. }
9
03/03/2021
抽象数据类型线性表定义
ADT List
{
数据对象：D = {ai|ai∈ElemSet, i=1,2,...,n,n≥0} 数据关系：R ={<ai,ai+1>| ai,ai+1 ∈ D, i=1,2,...,n,n≥0}} 基本操作：
引
IsEmpty(L)
// 若线性表为空，返回true，否则返回false
用
ListLength(L)
// 返回线性表L的元素个数
型
LocateElem(L, e) // 将线性表L中查找与给定值e相等的元素，若成功返回该
操 作
// 元素在表中的序号，否则返回 0
GetElem(L, i, &e) // 将线性表L中的第i个位置元素返回给e
【注意】 L为每个数据元素占据
的存储单元数目； LOC(ai)为数据元素ai的地
址 则 LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+(i-1)*L
14
03/03/2021
线性表的顺序存储结构例题
【例】一个一维数组Ｍ，下标的范围是０到９，每个数 组元素用相邻的５个字节存储。存储器按字节编址， 设存储数组元素Ｍ[０]的第一个字节的地址是98，则 Ｍ[３]的第一个字节的地址是________。
（１）原子类型： 如整数、字符等。
（２）结构类型： 如表示一个学生信息的数据元素，
包含学号、姓名、性别等数据项。
8
03/03/2021
线性表举例
1. La=（34，89，765，12，90，-34，22） 数据元素类型为int。 2. Ls=(Hello,World, China, Welcome) 数据元素类型为string。 3. Lb=(book1,book2,...,book100) 数据元素类型为下列所示的结构类型：
/*La中不存在和e相同数据元素*/
10.
ListInsert(La, ++La_len, e); /*插入*/
11.
}
12. }
11
03/03/2021
线性表怎么在计算机里存储？
12
03/03/2021
内容提要
❖ 线性表的定义和基本操作 ❖ 线性表的顺序存储结构 ❖ 线性表的链式存储结构（单链表）
16ห้องสมุดไป่ตู้
03/03/2021
怎样用C语言实现线性表的顺序存储结构？
17
03/03/2021
线性表顺序存储类型的C语言定义
5.
La_len = ListLength(La); /* 求线性表的长度 */
6.
Lb_len = ListLength(Lb);
7.
for (i = 1; i <= Lb_len; i++)
8.
{
GetElem(Lb, i, e);
/* 取Lb中第i个数据元素赋给e */
9.
if (!LocateElem(La, e))
}ADT List
10
03/03/2021
实现两个线性集合的并集
/* 将所有的在线性表Lb中但不在La中的数据元素插入到La中 */
1. void ListUnion (List &La, List Lb)
2. {
3.
int La_len, Lb_len, i;
4.
ElemType e;
/* 声明与La和Lb相同的数据元素e */
数据结构 与 算法
第二讲：线性表（一）
内容提要
❖ 线性表的定义和基本操作 ❖ 线性表的顺序存储结构 ❖ 线性表的链式存储结构（单链表）
2
03/03/2021
什么叫线性表？
3
03/03/2021
线性表的定义和基本操作
❖ 线性表的定义
线性表是由n (n ≥ 0) 个类型相同的数据元素组成的有限 序列。通常表示成下列形式：
L=( a1, a2,..., ai-1, ai, ai+1,..., an)
其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度， 当n=0时，线性表为空，又称为空线性表。
4
03/03/2021
线性表的结构分析
（a1, a2, … ai-1，ai, ai＋1 ，…, an）
前驱； 5. 除最后一个元素之外，每个元素均只有一个直
接后继。
6
03/03/2021
现实生活中的线性表
【思考】下列哪些关系属于线性关系呢？
家族的亲戚关系？ 同学之间的友谊？ 恋人之间的爱情？ 班级同学的名册？ 食堂窗口前排队？ 自习教室里占座？
7
03/03/2021
线性表中的元素类型
解：地址计算通式为： LOC(ai) = LOC(a1) + L *（i-1） 因此：LOC( M[3] ) = 98 + 5 ×(4-1) =113
15
03/03/2021
顺序存储结构的特点
❖ 存储单元地址连续（需要一段连续空间） ❖ 逻辑上相邻的数据元素其物理位置也相邻。 ❖ 存储密度大（100%）。 ❖ 随机存取，知道地址即可直接访问。
13
03/03/2021
线性表的顺序存储结构
用一组连续的存储单元依次存储线性表中的每个数据元素。
地址
b = LOC(a1)
b=b+L
L
b = b + (i-1)L
b = b + (n-1)L b = b + (maxLen-1)L
内容
a1 a2
ai ai+1
an
元素在表中的位序
1 2
i i+1
n 空闲区
改
InitList(&L)
// 初始化操作，建立一个空的线性表L
进
DestroyList(&L) // 销毁已存在的线性表L
型
ClearList(&L)
// 将线性表清空
操 作
ListInsert(&L, i, e) // 在线性表L中第i个位置插入新元素e
ListDelete(&L, i, &e) // 删除线性表L中第i个位置元素，并用e返回其值