资源描述：
《数据结构（C语言描述） 马秋菊 第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2.1线性表的逻辑结构2.2线性表的顺序存储结构及运算实现2.3线性表的链式存储结构及运算实现2.4线性表的典型应用小结第2章线性表2021/7/14第页本章学习目标线性表是最简单、最基本、最常用的一种数据结构通过本章学习，应掌握如下内容：线性表的概念及表示方法线性表的两种存储方式：顺序存储和链式存储线性表的基本运算及其实现算法线性表的典型应用2021/7/14第页例2:奇数序列(1,3,5,7,9,11)例1:字母序列(A,B,C,D,E,F)例3：随机的学生成绩序列2.1线性表的逻辑结构2.1.1线性表的定义问题
2、的引入学号姓名性别成绩20050601张三男51820050602李一宁女49620050603吴磊女581.5……………20050636梁磊男5292021/7/14第页3.举例：A=(１,３,５,７,９)该线性表的长度为5B=(a1,a2,a3,···，am)该线性表的长度为mC=(b1,b2,b3,···，bn)该线性表的长度为n1.定义：具有相同类型的n个数据元素组成的有限序列。记为(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，当n=0时称为空表。关键点:(1)相同类型(2)线性表的长度n(
3、n≥0)(3)有限序列2021/7/14第页1.线性表的长度线性表中所包含的元素个数n(n≥0)；2.空线性表线性表的长度n=0；3.（直接）前驱和后继在相邻元素中，ai是ai+1的前驱（第一个元素a1无前驱）在相邻元素中，ai+1是ai的后继（最后一个元素an无后继）4.举例：长度为10的奇数序列(1,3,5,7,9,11,13,15,17,19)线性表可以看作是除第一个元素无前驱，最后一个元素无后继外，其余元素都有唯一的直接前驱和直接后继的一组元素构成的有序集合。2021/7/14第页通常将ai的数据类型抽象为E
4、lemType。例如，学生信息表中数据元素可以定义为一个结构类型：typedefstructstd_info{longintNum;/*学号域*/charName[8];/*姓名域*/charSex;/*性别域*/floatScore;/*成绩域*/}ElemType;学号姓名性别成绩20050601张三男51820050602李一宁女49620050603吴磊女581.5……………20050636梁磊男5292021/7/14第页2.1.2线性表的基本操作⑴线性表初始化：Init_List(L)；——建立一个空的线
5、性表；⑵求线性表的长度：Length_List(L)；——返回线性表中数据元素的个数。⑶取表中元素：Get_Elem(L,i)；——返回线性表L中第ｉ个数据元素的值或地址。⑷按值查找：Locate_List(L,x)；——在表L中查找值为ｘ的数据元素的位置。⑸插入操作：Insert_List(L,i,x)；——在线性表L的第i个位置上插入一个值为x的数据元素。⑹删除操作：Delete_List(L,i)；——在线性表L中删除序号为i的数据元素。2021/7/14第页ADTList{数据对象：D={ai
6、ai∈ELEM
7、TPi=1,2,···,n,n≥0}数据关系：R={
8、ai,ai+1∈Di=1,2,···,n-1,n≥0}基本操作：InitList（&L）：线性表的初始化；ListLength（L）：求线性表的长度；ListInsert（&L,i,e）：在第i个位置插入元素e；ListDelete（&L,i,e）：在线性表第i个位置删除元素e；··· ··· ··· ··· ···}2021/7/14第页2.2线性表的顺序存储结构及运算实现2.2.1顺序表是指在内存中用一块地址连续的存储空间按顺序存储线性表的各
9、个数据元素。特点：采用连续的空间来存储线性表——顺序表。顺序存储结构可描述如下：typedefstruct{ElemTypeelem[MAXSIZE];intlength;/*线性表长度*/}SeqList;data数组下标a1a2…ai-1aiai+1…an…12…i-1ii+1…length...MAXSIZE-1bb+d……b+(i-1)d…b+(length-1)d存储地址2021/7/14第页线性表的长度及元素在线性表中的位置已知该线性表的首地址(a1)为Ｂ，那么任意一个元素的地址为:ai＝Ｂ＋(i-1)×
10、d（其中d为该类型元素所占空间）定义一个顺序表：SeqList*L；顺序表的长度为L->length;数据元素是L->data[1]～L->data[L->length]。因为在C语言中数组的下标是从0开始的，为了与线性表中元素的序号保持一致，不使用数组下标为“0”的单元，下标的取值范围1≤i≤MAXSIZE-1。data数组下标a1a2…ai
