厦门大学：《数据结构》课程教学课件（PPT讲稿）第二章 线性表

数据结构 庄朝晖 chzhuang@jingxian.xmu.edu.cn

数据结构 庄朝晖 chzhuang@jingxian.xmu.edu.cn

第二章 线性表 ■2.1线性表的类型定义 ■2.2线性表的顺序表示和实现 ■2.3线性表的链式表示和实现 2.3.1线性链表 2.3.2循环链表 2.3.3双向链表 2.4一元多项式的表示及相加

第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加

■2.1线性表的逻辑结构 线性表(Linear List)：由nn2)个数据元素（结点）a, a2,.an组成的有限序列。其中数据元素的个数 n定义为表的长度。当n=0时称为空表，常常将非 空的线性表(n>0)记作： (a1,a2,.an) ■这里的数据元素a(1≤≤n)只是一个抽象的符号， 其具体含义在不同的情况下可以不同。 ■例1、26个英文字母组成的字母表 (A,B,C、.、Z) ■例2、某校从1978年到1983年各种型号的计算机 拥有量的变化情况。 (6,17,28,50,92,188)

2.1 线性表的逻辑结构 线性表(Linear List) ：由n(n≧)个数据元素(结点)a1， a2， .an组成的有限序列。其中数据元素的个数 n定义为表的长度。当n=0时称为空表，常常将非 空的线性表(n>0)记作： (a1，a2，.an ) 这里的数据元素ai (1≦i≦n)只是一个抽象的符号， 其具体含义在不同的情况下可以不同。 例1、26个英文字母组成的字母表 （A，B，C、.、Z） 例2、某校从1978年到1983年各种型号的计算机 拥有量的变化情况。 （6，17，28，50，92，188）

例3、学生健康情况登记表如下： 姓名 学号 性别 年龄 健康情况 王小林 790631 男 18 健康 陈红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 ”。 。n ”。1。

例3、学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 . . . .

例4、一副扑克的点数 (2,3,4,yJ,Q,K,A) 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点©4 它没有直接前趋，而仅有一个直接后继©2： 有且仅有一个终端结点©n:它没有直接后继， 而仅有一个直接前趋an- 其余的内部结点a(2≤sn-1)都有且仅有一个直接 前趋a和一个直接后继a计 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的 具体实现则是在存储结构上进行的。 抽象数据类型的定义为：P9

例4、一副扑克的点数 （2，3，4，.，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是： ➢ 在非空的线性表，有且仅有一个开始结点a1， 它没有直接前趋，而仅有一个直接后继a2； ➢ 有且仅有一个终端结点an，它没有直接后继， 而仅有一个直接前趋a n-1； ➢ 其余的内部结点ai (2≦i≦n-1)都有且仅有一个直接 前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的 具体实现则是在存储结构上进行的。 抽象数据类型的定义为：P19

算法2.1 ■ 例2-1利用两个线性表LA和LB分别表示两个集合 A和B,现要求一个新的集合A=AUB。 1.[初值] 获取线性表LA和LB 2.[合并线性表] 对于LB中的每一个元素做x如下操作： 若(x不属于LA)则将x插入到LA的末尾 3.[算法结束]

算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合 A和B，现要求一个新的集合A=A∪B。 1.[初值] 获取线性表LA和LB 2.[合并线性表] 对于LB中的每一个元素做x如下操作： 若 （x不属于LA） 则 将x插入到LA的末尾 3.[算法结束]

算法2.2 例2-2已知线性表LA和线性表LB中的数据 元素按值非递减有序排列，现要求将LA和 LB归并为一个新的线性表LC,且LC中的元 素仍按值非递减有序排列。 此问题的算法如下：

算法2.2 例2-2 巳知线性表LA和线性表LB中的数据 元素按值非递减有序排列，现要求将LA和 LB归并为一个新的线性表LC，且LC中的元 素仍按值非递减有序排列。 此问题的算法如下：

1.[初值] 获取线性表LA和LB,并构造空线性表LC 2.[选择插入元素] 对于线性表LA和LB,都从其第一个元素开始做如下操作直到其中一个线性表元素全 部遍历完毕： 若(LA的元素a<=LB的元素b) 则 将元素a插入到LC的末尾，并选择A中的下一个元素a 否则 将元素b插入到LC的末尾，并选择LB中的下一个元素b 3.[补充剩下的元素] 若(LA还有剩余元素)则将LA的剩余元素全部插入到LC末尾 若(LB还有剩余元素)则将LB的剩余元素全部插入到LC末尾 4.[算法结束]

1.[初值] 获取线性表LA和LB，并构造空线性表LC 2.[选择插入元素] 对于线性表LA和LB，都从其第一个元素开始做如下操作直到其中一个线性表元素全 部遍历完毕： 若 （LA的元素a<=LB的元素b） 则 将元素a插入到LC的末尾，并选择LA中的下一个元素a 否则 将元素b插入到LC的末尾，并选择LB中的下一个元素b 3.[补充剩下的元素] 若 （LA还有剩余元素） 则 将LA的剩余元素全部插入到LC末尾 若 （LB还有剩余元素） 则 将LB的剩余元素全部插入到LC末尾 4.[算法结束]

2.2线性表的顺序存储结构 ■2.2.1线性表 把线性表的结点按逻辑顺序依次存放在一组地 址连续的存储单元里。用这种方法存储的线性表 简称顺序表。 假设线性表的每个元素需占用个存储单元，并 以所占的第一个单元的存储地址作为数据元素的 存储位置。则线性表中第+1个数据元素的存储位 置LOC(a+)和第i个数据元素的存储位置LOC(a) 之间满足下列关系： LOC(a i+1)=LOC(a )+l 线性表的第i个数据元素a的存储位置为： LOC(aj)=LOC(a)+(i-1)*I

2.2 线性表的顺序存储结构 2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地 址连续的存储单元里。用这种方法存储的线性表 简称顺序表。 假设线性表的每个元素需占用l个存储单元，并 以所占的第一个单元的存储地址作为数据元素的 存储位置。则线性表中第I+1个数据元素的存储位 置LOC( a i+1)和第i个数据元素的存储位置LOC(ai ) 之间满足下列关系： LOC(a i+1)=LOC(a i )+l 线性表的第i个数据元素ai的存储位置为： LOC(ai )=LOC(a1 )+(i-1)*l

由于C语言中的一维数组也是采用顺序存储 表示，故可以用数组类型来描述顺序表。 又因为除了用数组来存储线性表的元素之 外，顺序表还应该用一个变量来表示线性 表的长度属性，所以我们用结构类型来定 义顺序表类型。 define ListSize 100 typedef int DataType; typedef strucf DataType data[ListSize]; int length; Sqlist;

由于C语言中的一维数组也是采用顺序存储 表示，故可以用数组类型来描述顺序表。 又因为除了用数组来存储线性表的元素之 外，顺序表还应该用一个变量来表示线性 表的长度属性，所以我们用结构类型来定 义顺序表类型。 # define ListSize 100 typedef int DataType; typedef struc{ DataType data[ListSize]; int length; } Sqlist;