第2章线性表(1)

1、第2章 线性表(一)主要内容主要内容2.1 线性表引例线性表引例 2.2 线性表的定义和逻辑结构线性表的定义和逻辑结构2.3 线性表的顺序存储结构线性表的顺序存储结构 2.1 线性表引例线性表引例 例 某大学欲进行一次数学竞赛，约有200名学生报名参赛。现将报名登记表(如下表所示)存入计算机以便完成如下工作： (1) 能正确录入学生记录； (2) 按成绩对该表进行重新排序； (3) 按学号或姓名查询学生成绩。报报 名名 登登 记记 表表学 号姓 名性 别成 绩2003张三男842024 李四男792035王五女752.2 线性表的定义和逻辑结构线性表的定义和逻辑结构线性表的概念线性表的概念 线

2、性表是指n(n0)个具有相同类型数据元素(或称结点)的有限序列，可表示为(a1,a2,.,ai,.,an)。其中，ai代表一个数据元素，a1称为表头(或头结点)，an称为表尾(或尾结点)，ai(0in)称为ai+1的直接前驱，ai+1称为ai的直接后继。线性表中数据元素的个数称为线性表的长度，长度为0的线性表称为空表，记为()。 （a1, a2, ai-1，ai, ai1 ，, an）线性表的逻辑结构线性表的逻辑结构 用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号

3、，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级012002009524刘禹圻刘禹圻男男 182003级材料级材料01班班012002009613武武 锐锐男男 182003级材料级材料01班班012002009710彭彭 隽隽男男 172003级材料级材料01班班012002009801郭郭 芳芳女女 182003级材料级材料02班班012002009904

4、张珍珍女18182003级材料级材料02班班： ：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。线性表的特征线性表的特征对于非空的线性表: 有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2； 有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1； 其余的内部结点ai（2in-1）都有且仅有一个直接前趋ai-1和一个ai+1。

5、a1a2a3a4a5a6 线性表的特点线性表的特点 同一性：同一性：线性表由同类数据元素组成，线性表由同类数据元素组成，每一个每一个ai 必须属于同一数据对象。必须属于同一数据对象。 有穷性：有穷性：线性表由有限个数据元素组线性表由有限个数据元素组成，表长度就是表中数据元素的个数。成，表长度就是表中数据元素的个数。 有序性：有序性：线性表中相邻数据元素之间线性表中相邻数据元素之间存在着序偶关系存在着序偶关系。 在不同的问题中，数据元素代表的具体含义不同，它可以是一个数字一个字符，也可以是一句话，甚至其他更复杂的信息。例如: 线性表L1: (12, 58, 45, 2, 45, 46), 其元素

6、为数字； 线性表L2: (a, g, r, d, s, t), 其元素为字母。 表1也是一个线性表，其数据元素较为复杂，每个学生的学号姓名性别成绩构成一个数据元素。这种由若干数据项构成的数据元素常称为记录，含有大量记录的线性表称为文件。线性表的逻辑结构表示线性表的逻辑结构表示 在任何问题中，数据元素之间可以存在多种关系。从数据结构的观点来看，重要的是数据元素之间的逻辑关系。所谓逻辑关系，是指数据元素之间的关联方式或称“邻接关系”。上表中数据的逻辑结构如下图(b)所示，其中的圆圈称为结点。一个结点代表一个数据元素(有时也把结点和数据元素当作同义词)，结点之间的连线代表逻辑关系，即相应数据元素之间

7、的邻接关系。图(b)中的逻辑结构反映了表中表格作为一个数据的组织形式，这种组织形式就是数据元素(记录)“一个接一个地排列”。 四种基本逻辑结构(a)集合； (b) 线性结构；(c)树形结构；(d)图状结构ABDCEFABCDEF(a)(b)ABCDEF(c)ABDCEF(d)2.3 线性表的顺序存储结构线性表的顺序存储结构1. 顺序表的存储特点2. 顺序表的基本运算 用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示

8、又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之：简言之： 逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现。来实现。注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-11. 顺序表的存储特点顺序表的存储特点1). 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2). 若已知表中首元素在存储器中的位置，则其他若已知表中首元素在存

9、储器中的位置，则其他元素存放位置亦可求出元素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。 设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为K字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC ( ai+1 ) = LOC( ai ) + K 对上述公式的解释如下图所示对上述公式的解释如下图所示 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址存储地址 内存空间状态 逻辑地址 Loc(a1) a11

10、 Loc(a1)+(2-1)k a2 2 loc(a1)+(i-1)k ai i loc(a1)+(n-1)k an n . loc(a1)+(maxlen-1)k 线性表的顺序存储结构示意图设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数组元素用相邻的每个数组元素用相邻的个字节个字节存储。存储存储。存储器按字节编址，设存储数组元素器按字节编址，设存储数组元素 的第的第一个字节的地址是一个字节的地址是，则，则 的第一个的第一个字节的地址是多少？字节的地址是多少？113例例1但此题要注意下标起点略有不同：但此题要注意下标起点略有不同：LOC( M3 ) = 98 + 5 (3-0

11、) =113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1） 用数组用数组V来存放来存放26个英文字母组成的线个英文字母组成的线性表（性表（a，b，c，z），写出在顺序结），写出在顺序结构上构上生成生成和和显示显示该表的该表的C语言程序。语言程序。 char V30;void build() /*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/ int i; V0=a; for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心语句：核心语句：例例2void main(void) /*主函数主函数，字母线性表的，字

12、母线性表的生成和输出生成和输出*/ n=26; /* n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build( );display( );void display( ) /*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/ int i; for( i=0; i=n-1; i+ ) printf( %c, vi ); printf( n );执行结果：执行结果： a b c d e f g h i j k l m n o p q r s t u v w x y z 在C语言中，可以用一维数组来描述向量。 # define ma

13、xsize N; /*设置线性表的最大长度为N, N为整数*/ typedef struct datatype datamaxsize+1; /*datatype为元素的数据类型*/ int last; /*记录当前表中元素的个数*/ Sqlist； 上述描述方法，将线性表顺序存储结构中的信息封装隐藏在类型Sqlist结构中。data数组描述了线性表中数据元素占用的空间，数组中第i个分量就是线性表中第i个数据元素。last描述了当前表中数据元素的个数即表长。 说明：在C语言中，数组的下标是从0开始的，但为了算法描述方便，凡涉及数组的算法，规定下标从1开始，这样，可不必考虑下标为0的数组元素。2

14、 顺序表的基本运算顺序表的基本运算1. 线性表元素插入操作 插入一个记录，对有序线性表结构的影响可以从以下两个方面分析。(1) 若插入记录关键字的值比表中所有的数据元素的关键字值都大，那么只需在表后添加一个新记录元素，同时使表的当前长度修正为n+1即可。(2) 若插入记录的位置出现在线性表的中间，则情况比较复杂。从下图所示的线性表插入过程可以看出，插入的步骤和插入完成后仍保持了记录关键字值的有序性。 (a1, , ai-1, ai, , an) 变为变为(a1, , ai-1, e, ai, , an)关系关系, 线性表逻辑结构线性表逻辑结构的变化的变化:线性表存储结构的变化线性表存储结构的变

15、化:a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的长度增加21 18 30 75jjj87564266jL.last21 18 30 75 42 56 87L.last0i有序线性表的插入算法步骤：(1) 检测线性表是否有空间可供插入；(2) 从最末一个元素an到ai逐个后移，腾出一个空位或空的存储单元i；(3) 插入一个新的元素，修正线性表的当前长度。 2. 线性表元素删除操作 (a1, , ai-1, ai, ai+1, , an) 改变为改变为 (a1, , ai-1, ai+1, , an), 线性表逻辑结构的变化：线性表逻辑结构的变化：ai+1 an表的长度减

16、少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 线性表存储结构的变化线性表存储结构的变化:21 18 30 75kk8756kL- -last21 18 30 75 42 56 87L- -last0i3. 线性表元素定位操作下图(a)所示的是无序线性表，其数据元素在线性表中的存放是任意的；图(b)所示的是有序线性表，其数据元素的排列按英文字母的字母顺序从小到大存放。有序线性表有如下特点，设V为有序线性表，数据元素ai值的相邻关系为ai-1aiai+1。 无序和有序线性表(a) 无序线性表；(b) 有序线性表1c2a3f4m5n6e7h(a)(b)1a2c3e4f5h6m7n

17、无序表查找操作无序表查找操作: ESEARCH(v,n,t) 算法分析算法分析:23 75 41 38 54 62 17V1 Vnt =38ppppp序号序号i1 2 3 4 1 850p原操作是：将顺序表中的元素逐个和给定值t相比较。无序线性表的查找算法框图开始读入一个查找的记录t末尾增加一个查找的记录t 从表首开始1i 第i个记录的值是否等于t？in?查找成功查找失败结束1 iiNYYN无序线性表的查找算法如下：/* 无序线性表的查找算法 */ ESEARCH(v,n,t)/* v是无序线性表，n是线性表的长度，t是被查找的记录 */ int i; vn+1=t; /* 建立无序查找的结束

18、标志 */ i=1; while(vi!=t) i+; if(i=n) return(search, true); else return(search, false);有序线性表的查找算法框图开始读入一个查找的记录t末尾增加一个最大值 从表首开始1i 第i个记录的值小于t？相等否？查找失败查找成功结束1iiNYYN有序线性表的查找算法如下： /* 有序线性表的查找算法 */EGSEARCH(v, n,t )/* v是有序线性表，n是线性表的长度，t是被查找的记录 */char search6; int i; vn+1=;/* 设置查找的结束标志 */ i=1; while(vit) i+; if(vi=t) printf(search,true); else printf(search, false);优点：优点：1.无需为表示结点间的逻辑关系而增加额外的存储无需为表示结点间的逻辑关系而增加额外的存储空间；空间； 2.可方便地随机存取表中的任一元素。可方便地随机存取表中的任一元素。 缺点：缺点：1.插入