电子斜技大学 软件技术基础 3.2线性结构之线性表-1 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
1、什么是线性结构 定义：有且仅有一个起始元素（无直接前趋，仅有一个直接后 继)，一个终点元素（无直接后继，仅有一个直接前趋），其余内 部元素各有一个直接前趋和一个直接后继的有限有序序列。 B 3 E ·常见类型：线性表、堆栈、队列、数组、串等 电子科技大学刘民岷 线性表 2
电子科技大学 刘民岷 线性表 2 • 定义：有且仅有一个起始元素(无直接前趋，仅有一个直接后 继)，一个终点元素(无直接后继，仅有一个直接前趋)，其余内 部元素各有一个直接前趋和一个直接后继的有限有序序列。 • 常见类型：线性表、堆栈、队列、数组、串等 B 1 2 3 E
2、 线性表-逻辑结构 是指数据元素之间的关系为一一对应的线性关系的数据结 构。 例如：一星期七天的英文缩写表示： (Sun、Mon、The、Wed、Thu、Fri、Sat) 是一个线性表， 其中的元素是字符串，表的长度为7。 线性表虽然简单，但是应用范围非常广泛。 线性表通常表示为：a,a2,a3,,am 中n为线性表的长度，a(1<i<n)是线性表中第i个序号的数据元 素 例如： (1,12,123,1234,321,21,22)是一个线性表，表中元素a为整数，表长为7 电子科技大学刘民岷 线性表 3
电子科技大学 刘民岷 线性表 3 • 是指数据元素之间的关系为一一对应的线性关系的数据结 构。 • 例如：一星期七天的英文缩写表示： （Sun、Mon、The、Wed、Thu、Fri、Sat）是一个线性表， 其中的元素是字符串，表的长度为7。 • 线性表虽然简单，但是应用范围非常广泛。 • 线性表通常表示为：a1 ,a2 ,a3 ,…,an 其中n为线性表的长度，ai (1≤i≤n)是线性表中第i个序号的数据元 素。 例如： (1,12,123,1234,321,21,22)是一个线性表，表中元素ai为整数，表长为7
3、线性表-物理存储结构 顺序存储结构 逻辑上连续，物理上也连续 数据域 dl d2 dn ·链式存储结构 一物理上可以不连续，逻辑关系由指针表示 数据域 指针域 dl d2 dn 电子科技大学刘民岷 线性表 4
电子科技大学 刘民岷 线性表 4 • 顺序存储结构 – 逻辑上连续，物理上也连续 • 链式存储结构 – 物理上可以不连续，逻辑关系由指针表示 d1 d2 …… dn 数据域 d1 d2 ... dn ^ 数据域 指针域
3.1线性表物理存储结构之顺序存储 将表中元素一个接一个的存入一组连续的存储单元中，这 种存储结构是顺序结构。 。 采用顺序存储结构的线性表简称为“顺序表”。顺序表的 存储特点是：只要确定了起始位置，表中任一元素的地址 都通过下列公式得到： Loc(a)=Loc(a)+(i-1)Xk (1≤i≤n) 其中，k是元素占用存储单元的长度。显然，顺序表中每个元素的存 储地址是该元素在表中索引号的线性函数。 电子科技大学刘民岷 线性表 5
电子科技大学 刘民岷 线性表 5 • 将表中元素一个接一个的存入一组连续的存储单元中，这 种存储结构是顺序结构。 • 采用顺序存储结构的线性表简称为“顺序表”。顺序表的 存储特点是：只要确定了起始位置，表中任一元素的地址 都通过下列公式得到： Loc(ai ) = Loc(a1 ) + (i-1)×k (1 i n) 其中，k是元素占用存储单元的长度。显然，顺序表中每个元素的存 储地址是该元素在表中索引号的线性函数