文档介绍：数据结构线性表A
2
(2，3，4，…，J，Q，K，A）
学号
姓名
性别
年龄
班级
2001011810205
管春燕
女
18
2001级电信016班
2001011810260
周 刚
男
18
2001级电信017班
2001011810284
石文娟
女
18
2001级通信011班
2001011810360
杨 扬
男
18
2001级通信012班
：
：
：
：
：
生活实例：
第1页/共33页
3
简言之，线性结构反映结点间的逻辑关系是 一对一(1:1) 的
线性结构特点：在数据元素的非空有限集中
存在唯一的一个被称作“第一个”的数据元素
存在唯一的一个被称作“最后一个”的数据元素
除第一个元素外，集合中的每个数据元素均只有一个前驱
除最后一个元素外，集合中的每个数据元素均只有一个后继
若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
可表示为：（a1 , a2 , ……, an）
线性结构的定义：
第2页/共33页
4
（逻辑、存储和运算）
线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是---
线性表
第2章
第3页/共33页
第2章 线性表
线性表的逻辑结构
线性表的顺序表示和实现
线性表的链式表示和实现
应用举例
第4页/共33页
6
（a1, a2, … ai-1，ai, ai＋1 ，…, an）
线性表的逻辑结构
线性表的定义：用数据元素的有限序列表示
n=0时称为
数据元素
线性起点
ai的直接前趋
ai的直接后继
下标，是元素的序号，表示元素在表中的位置
n为元素总个数，即表长
空表
线性终点
第5页/共33页
7
例1 分析一副***的点数组成的英文表
(2，3，4，…，J，Q，K，A）
例2 分析学生情况登记表
数据元素都是记录; 元素间关系是线性
数据元素都是牌面点数; 元素间关系是线性
同一线性表中的元素必定具有相同特性
学号
姓名
性别
年龄
班级
2001011810205
管春燕
女
18
2001级电信016班
2001011810260
周 刚
男
18
2001级电信017班
2001011810284
石文娟
女
18
2001级通信011班
2001011810360
杨 扬
男
18
2001级通信012班
：
：
：
：
：
第6页/共33页
8
练：判断下列叙述的正误：
1. 线性表的逻辑结构定义是唯一的，不依赖于计算机。
2. 线性结构反映结点间的逻辑关系是一对一的。
3. 一维数组是线性表，但二维或N维数组不是。
4. “同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。
√
×
√
×
第7页/共33页
9
线性表的顺序表示和实现
顺序表的表示
顺序表的实现
顺序表的运算效率分析
顺序表小结
第8页/共33页
10
顺序表的表示
用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。
把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义：
顺序存储方法：
简言之，逻辑上相邻，物理上也相邻
第9页/共33页