资源描述：
《第2章 线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表(一)教学要求1．了解：线性表的定义和基本运算。2．掌握：线性表的两种存储结构：顺序存储结构和链式存储结构的描述方式，以及这两种存储结构上的基本运算的实现算法。3．掌握：线性表的两种存储结构的特点及其具体实现。主要内容1线性表引例2线性表的定义和逻辑结构3线性表的顺序存储结构4顺序表应用5小结线性表引例例某大学欲进行一次数学竞赛，约有200名学生报名参赛。现将报名登记表(如下表所示)存入计算机以便完成如下工作：(1)能正确录入学生记录；(2)按成绩对该表进行重新排序；(3)按学号或姓名查询学生成绩。报名登记表学号姓名性别成绩2003张三男842024李四男792035王五女75线性
2、表的定义和逻辑结构线性表的概念线性表是指n(n≥0)个具有相同类型数据元素(或称结点)的有限序列，可表示为(a1,a2,...,ai,...,an)。其中，ai代表一个数据元素，a1称为表头(或头结点)，an称为表尾(或尾结点)，ai(0≤i＜n)称为ai+1的直接前驱，ai+1称为ai的直接后继。线性表中数据元素的个数称为线性表的长度，长度为0的线性表称为空表，记为()。线性表的定义和逻辑结构（a1,a2,…ai-1，ai,ai＋1，…,an）线性表用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。
3、n≥0空表线性终点例1分析26个英文字母组成的英文表是什么结构。（A,B,C,D,……,Z）学号姓名性别年龄班级012002009524刘禹圻男182003级材料01班012002009613武锐男182003级材料01班012002009710彭隽男172003级材料01班012002009801郭芳女182003级材料02班012002009904张珍珍女182003级材料02班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！线性表的特征对于非空
4、的线性表:①有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；②有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1；③其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个ai+1。a1a2a3a4a5a6圆圈称为结点。一个结点代表一个数据元素，结点之间的连线代表逻辑关系，即相应数据元素之间的邻接关系。线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。在不同的问题中，数据元素代表的具体
5、含义不同，它可以是一个数字﹑一个字符，也可以是一句话，甚至其他更复杂的信息。例如:线性表L1:(12,58,45,2,45,46),其元素为数字；线性表L2:(a,g,r,d,s,t),其元素为字母。表1也是一个线性表，其数据元素较为复杂，每个学生的学号﹑姓名﹑性别﹑成绩构成一个数据元素。这种由若干数据项构成的数据元素常称为记录，含有大量记录的线性表称为文件。线性表的逻辑结构表示在任何问题中，数据元素之间可以存在多种关系。从数据结构的观点来看，重要的是数据元素之间的逻辑关系。所谓逻辑关系，是指数据元素之间的关联方式或称“邻接关系”。在数据的逻辑结构图中，圆圈称为结点。一个结点代表一个数据元素，
6、结点之间的连线代表逻辑关系，即相应数据元素之间的邻接关系。线性表的顺序存储结构顺序表的存储特点顺序表的基本运算线性表的顺序存储结构用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现。注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]顺序表的存储特点1).逻辑上相邻的数据元素，其物理上也相邻；2).若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组
7、V[n]的下标）。在C语言中，可以用一维数组来描述向量。#definemaxsizeN;/*设置线性表的最大长度为N,N为整数*/typedefstruct{datatypedata[maxsize+1];/*datatype为元素的数据类型*/intlast;/*记录当前表中元素的个数*/}Sqlist；上述描述方法，将线性表顺序存储结构中的信息封装隐藏在类型Sqlist结构中。data数组描述
