电子科技大学：《软件技术基础 Fundamental of Software Technology》课程教学资源（课件讲稿）第三章 数据结构 3.2 线性结构之线性表（一）

电子斜技大学 软件技术基础 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是元素占用存储单元的长度。显然，顺序表中每个元素的存 储地址是该元素在表中索引号的线性函数

3.1线性表物理存储结构之顺序存储续 顺序表存储结构示意图 存储地址 内存状态 元素索引号 Loc (a) 1 a1 Loc (a)+k a2 2 Loc(a)+(i-1)Xk a; i Loc(a)+(n-1)Xk an n 电子科技大学刘民岷 线性表 6

电子科技大学 刘民岷 线性表 6 • 顺序表存储结构示意图 存储地址 内存状态 元素索引号 Loc (a1 ) Loc (a1 )+k … Loc(a1 )+(i-1)×k … Loc(a1 )+(n-1)×k 1 2 … i … n a1 a2 … ai … an

3.1.1顺序表插入算法 用结构类型对顺序表进行说明如下： define struct elemtype data[MAXNUM]; //elemtype为顺序表中的元素类型， /MAXNUM为其最大元素个数； int num; /表中元素个数 listtype; /类型名 listtype list; /类型的一个实例 电子科技大学刘民岷 线性表 7

电子科技大学 刘民岷 线性表 7 用结构类型对顺序表进行说明如下： define struct {elemtype data[MAXNUM]; //elemtype为顺序表中的元素类型， //MAXNUM为其最大元素个数； int num; //表中元素个数 }listtype; //类型名 listtype list; //类型的一个实例

3.1.1顺序表插入算洁（续） 00001: /*算法步螺 00002: step1将第n至 00003: step2将】 蕾个营后移一个存储位蛋； 插入 00004: step3 表的长度+1。 00005: *川 00006: //========= 00007: define true 1 00008: define false o 00009: int insert1(listtype*l,int i,elemtype x) 00010: int j; 00011: if(I->num>=MAXNUM) /1培误湾况之 00012: printf(" the list is full,can not insert.") 00013: return(false); 00014: 00015: if(il>num) /川话误情况之三 00016: {printf(”i is invalid value”)i 00017: return(false); 00018: 00019: for (j=l->num-1;j>=i;j--) /1入元 00020: I->data[j+1]=l->data[j]; 00021: l->data[i]=x对 00022: l->num++; 00023: return(true); 00024: 电子科技大学刘民岷 线性表 8

电子科技大学 刘民岷 线性表 8

3.1.2顺序表删除算法 00001:/*算法步骡： 00002: 00003: stepi step2 寝最 百童速的元素 00004: 前移 个存 储位置； 00005: step3 表的长度-1。 00006: * 00007: /======== 00008: define etrue 1 00009: define false o 00010: 00011: int delete_l(listtype *l,int i) 00012: 1 i int j; 00013: ifil->num-1) 00014: printf("not exist" 00015: return(false); 00016: 00017: for (j=i+1;jnum;j++) 00018: I->data[j-1]=l->data[j]; 00019: 1>num--; 00020: return(true); 00021: 电子科技大学刘民岷 线性表 9

电子科技大学 刘民岷 线性表 9

3.1.3线性表顺序存储的特点 >数据连续存放、随机存取 >逻辑上相邻，物理上也相邻 >存储结构简单、易实现 >插入、删除操作不便 >存储密度大，空间利用率高 结论： 顺序存储结构适合于表中元素变动较少的情况。 电子科技大学刘民岷 线性表 10

电子科技大学 刘民岷 线性表 10 ➢ 数据连续存放、随机存取 ➢ 逻辑上相邻，物理上也相邻 ➢ 存储结构简单、易实现 ➢ 插入、删除操作不便 ➢ 存储密度大，空间利用率高 结论： 顺序存储结构适合于表中元素变动较少的情况