线性表的逻辑结构

《线性表的逻辑结构》由会员分享，可在线阅读，更多相关《线性表的逻辑结构（51页珍藏版）》请在金锄头文库上搜索。

1、数据结构(C语言版)第第2 2章章 线性表线性表 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构 2.2 线性表的顺序存储结构及运算实现线性表的顺序存储结构及运算实现线性表的顺序存储结构及运算实现线性表的顺序存储结构及运算实现 2.3 线性表的线性表的线性表的线性表的链式链式链式链式存储结构及运算实现存储结构及运算实现存储结构及运算实现存储结构及运算实现 2.4 线性表的典型应用线性表的典型应用线性表的典型应用线性表的典型应用 小结小结小结小结2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表本章学习目标本章学习目标 线性表线性表是最简单、最基本、最常用

2、的一种数据结构是最简单、最基本、最常用的一种数据结构通过本章学习，应掌握如下内容：通过本章学习，应掌握如下内容：线性表的概念及表示方法线性表的概念及表示方法线性表的线性表的两种两种存储方式：存储方式：顺序存储顺序存储和和链式存储链式存储 线性表的基本运算及其实现算法线性表的基本运算及其实现算法 线性表的典型应用线性表的典型应用2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表 例例2 2:奇数序列奇数序列 (1,3,5,7,9,11)(1,3,5,7,9,11)例例1 1:字母序列字母序列 (A,B,C,D,E,F)A,B,C,D,E,F)例例3 3：随机的学生成绩序列：随机的学

3、生成绩序列2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.1.1 线性表的定义线性表的定义 问题的引入学学 号号姓姓 名名性性 别别成成 绩绩20050601张张 三三男男51820050602李一宁李一宁女女49620050603吴吴 磊磊女女581.520050636梁梁 磊磊男男5292022/7/7数据结构(C语言版)第第2 2章章 线性表线性表3.3.举例：举例：A=(,)该线性表的长度为该线性表的长度为 5 5B=(a1,a2,a3,，am)该线性表的长度为该线性表的长度为 m mC=(b1,b2,b3,，bn)该线性表的长度为该线性表的长度为 n n1.1.定义：具有定义：

4、具有相同类型相同类型的的 n n 个个数据元素组成的数据元素组成的有限序列有限序列。记为记为 (a1，a2，ai-1，ai，ai+1，an)其中其中n n为表长，当为表长，当n=0 n=0 时称为空表。时称为空表。关键点关键点:(1)(1)相同类型相同类型(2)(2)线性表的长度线性表的长度 n (n0)n (n0)(3)(3)有限序列有限序列2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表1.1.线性表的长度线性表的长度线性表中所包含的元素个数线性表中所包含的元素个数 n(n0)n(n0)；2.2.空线性表空线性表线性表的长度线性表的长度 n=0 n=0；3.3.（直接）前驱

5、和后继直接）前驱和后继在相邻元素中，在相邻元素中，a ai i 是是a ai+1i+1的前驱（第一个元素的前驱（第一个元素 a a1 1无前驱）无前驱）在相邻元素中，在相邻元素中，a ai+1i+1是是a ai i的后继（最后一个元素的后继（最后一个元素a an n无后继）无后继）4.4.举例：举例：长度为长度为1010的奇数序列的奇数序列 (1,3,5,7,9,11,13,15,17,19)线性表可以看作是除线性表可以看作是除第一个元素第一个元素无前驱，无前驱，最后一个元素最后一个元素无后无后继外，其余元素都有唯一的直接前驱和直接后继的一组元素构成继外，其余元素都有唯一的直接前驱和直接后继的

6、一组元素构成的有序集合。的有序集合。2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表通通常常将将ai的的数数据据类类型型抽抽象象为为ElemType。例例如如，学学生生信信息息表表中中数据元素可以定义为一个结构类型：数据元素可以定义为一个结构类型：typedefstructstd_infolongintNum;/*学号域学号域*/charName8;/*姓名域姓名域*/charSex;/*性别域性别域*/floatScore;/*成绩域成绩域*/ElemType;学学 号号姓姓 名名性性 别别成成 绩绩20050601张张 三三男男51820050602李一宁李一宁女女4962

7、0050603吴吴 磊磊女女581.520050636梁梁 磊磊男男5292022/7/7数据结构(C语言版)第第2 2章章 线性表线性表2.1.2 线性表的基本操作线性表的基本操作 线性表初始化线性表初始化：Init_List(L)；建立一个空的线性表；建立一个空的线性表；求线性表的长度求线性表的长度：Length_List(L)；返回线性表中数据元素的个数。返回线性表中数据元素的个数。取表中元素取表中元素：Get_Elem(L,i)；返回线性表返回线性表L中第个数据元素的值或地址。中第个数据元素的值或地址。按值查找按值查找：Locate_List(L,x)；在表在表L中查找值为的数据元素的

8、位置。中查找值为的数据元素的位置。插入操作插入操作：Insert_List(L,i,x)；在线性表在线性表L的的第第i个位置上插入一个值为个位置上插入一个值为x的数据元素。的数据元素。删除操作删除操作：Delete_List(L,i)；在线性表在线性表L中删除序号为中删除序号为i的数据元素的数据元素。2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表ADT List ADT List 数据对象数据对象：D=ai|ai ELEMTP i=1,2,n ,n 0 数据关系数据关系：R=|ai,ai+1 D i=1,2,n-1 ,n 0 基本操作基本操作：InitList（&L）：）：线

9、性表的初始化；线性表的初始化；ListLength（L）：求线性表的长度；求线性表的长度；ListInsert（&L,i,e）：）：在第在第 i i 个位置插入元素个位置插入元素 e e；ListDelete（&L,i,e）：）：在线性表第在线性表第 i i 个位置删除元素个位置删除元素 e；2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表2.2 2.2 线性表的顺序存储结构及运算实现线性表的顺序存储结构及运算实现2.2.1 顺序表顺序表 是指在内存中用一块地址连续的是指在内存中用一块地址连续的存储空间按顺序存储线性表的存储空间按顺序存储线性表的各个数据元素。各个数据元素。特点

10、特点：采用连续的空间来存储线：采用连续的空间来存储线性表性表顺序表顺序表。顺序存储结构可描述如下：顺序存储结构可描述如下：typedefstructElemTypeelemMAXSIZE;intlength;/*/*线性表长度线性表长度 */*/SeqList;data数组下标数组下标a1a2ai-1aiai+1an12i-1ii+1length.MAXSIZE-1bb+db+(i-1)db+(length-1)d存储地址存储地址2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表线性表的线性表的长度长度及元素在线性表中的及元素在线性表中的位置位置 已知该线性表的首地址已知该线性表

11、的首地址(a a1 1)为，那么任意一个元素的地址为为，那么任意一个元素的地址为:ai(i-1)d （其中其中d d为该类型元素所占空间）为该类型元素所占空间）定义一个顺序表：定义一个顺序表：SeqList *L SeqList *L；顺序表的长度为顺序表的长度为L-length;L-length;数据元素是数据元素是L-data1L-data1L-L-dataL-lengthdataL-length。因为在因为在 C C语言中数组的下标是从语言中数组的下标是从0 0开始的，为了与线性表中元素的开始的，为了与线性表中元素的序号保持一致，不使用数组下标序号保持一致，不使用数组下标为为“0”“0”

12、的单元，下标的取值范围的单元，下标的取值范围11iMAXSIZE-1iMAXSIZE-1。data数组下标数组下标a1a2ai-1aiai+1an12i-1ii+1length.MAXSIZE-1bb+db+(i-1)db+(length-1)d存储地址存储地址2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表(1)将将anai按从后向前的按从后向前的顺序向下移动，为新元素让顺序向下移动，为新元素让出位置；出位置；(2)将将x置入空出的第置入空出的第i个个位置；位置；(3)修改修改length值。值。Length+12.2.2 顺序表上基本运算的实现顺序表上基本运算的实现 1顺序

13、表的初始化顺序表的初始化-构造一个空表构造一个空表 voidinit_SeqList(SeqList*L)L-length=0;L-length=0;2.2.插入运算插入运算 a1a2ai-1aiai+1ana1aai-1xaiai+1an12i-1ii+1nn+12022/7/7数据结构(C语言版)第第2 2章章 线性表线性表【算法【算法2.2】在顺序表的第】在顺序表的第i个位置上插入一个值为个位置上插入一个值为x的新元素。的新元素。intInsert_SeqList(SeqList*L，inti，ElemTypex)intj;if(L-length=MAXSIZE-1)printf(表满表

14、满);returnOVERFLOW;if(iL-length+1)/*检查插位置的正确性检查插位置的正确性*/printf(位置错位置错);returnERROR;for(j=L-length;j=i;j-)L-elemj+1=L-elemj;L-elemi=x;L-length+;returnOK;/*插入成功，返回插入成功，返回*/2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表8660787555909055786086例如：插入元素75，插入位置为4，则90和55两个元素应向后移。算法说明算法说明：在线性表中，按照某顺：在线性表中，按照某顺序查找与其给定一致的元素是否存

15、序查找与其给定一致的元素是否存在，如果存在返回其位置，否则给在，如果存在返回其位置，否则给出相关信息。出相关信息。i的取值范围为的取值范围为：1in+1即有即有n1个位置可以插入。个位置可以插入。2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表插入算法的时间性能分析：插入算法的时间性能分析：在第在第i个位置上插入个位置上插入x，从从ai到到an都要向下移动一个位置，共都要向下移动一个位置，共需要移动需要移动ni1个元素，而个元素，而i的取值范围为的取值范围为：1=i=n+1，即有即有n1个位置可以插入。设在第个位置可以插入。设在第i个位置上作个位置上作插入的概率为插入的概率为P

16、i，则平均移动数据元素的次数：则平均移动数据元素的次数：设：设：Pi=1/(n+1)，即为等概率情况，则：即为等概率情况，则：这说明：在顺序表上做插入操作需移动表中一半的数据元素。这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为显然时间复杂度为(n)。2022/7/7数据结构(C语言版)第第2 2章章 线性表线性表3.3.删除运算删除运算 删除第删除第i i个元素，个元素，i i 的取值范围为：的取值范围为：11inin。运算的步骤为：先将运算的步骤为：先将a ai+1i+1a an n 依依次向上移动，然后将次向上移动，然后将length length 值减值减1 1。a1a2ai-1aiai+1ana1aai-1ai+1an12i-1ii+1n-1nn+1删除算法删除算法intDelete_SeqList(SeqList*L,inti)intj;if(iL-length)printf(不存在第不存在第i个元素个元素);returnERROR;for(j=i;jlength-1;j+)L-elemj=L-elemj+1;L-length-;returnOK;20