第2章线性表.ppt

《第2章线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第2章线性表第2章线性表2.1线性表的定义及基本运算2.2线性表的顺序存储结构及其运算2.3线性表的链接存储结构及其运算2.4顺序表和链表的比较2.5线性表的简单应用举例线性结构的特点：（1)存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个元素之外，结构中的每一个数据元素均只有一个前驱；（4）除最后一个之外，结构中每个数据元素均只有一个后继。根据上述特点，线性结构中的所有元素按它们之间的关系可以排成一个线性序列：k1,k2,…,kn。这样的线性序列称为线性表。2.1线性表的定义及基本运算

2、2.1.1线性表的定义2.1.2线性表的基本运算2.1.1线性表的定义线性表是由n（n≥0）个数据元素（结点）a1,a2,a3,…,an组成的有限序列。通常，我们把非空的线性表（n＞0）记为：A=（a1,a2,a3,…,an）①A是线性表的表名。一个线性表可以用一个标识符来命名。②ai（1≤i≤n）是表中的数据元素。③n是线性表中数据元素的个数，也称为线性表的长度。n=0的线性表称为空表，此时，表中不包含任何数据元素。【例2.1】26个大写英文字母组成的字母表（A,B,C,D,…,Z）就是一个线性表。其中字母表中的“A”是第一个数据元素，“Z”是最后

3、一个数据元素；“A”是“B”的直接前驱，“B”是“A”的直接后继……该线性表的长度为26。【例2.2】有一组实验数据（41,21,34,53,62,71,75,81,76,45），这也是一个线性表，数据之间有着一定的顺序（可能是随时间推移取得的实验数据）。这个线性表的长度为10。数据元素34的直接前驱是21，而直接后继是53。在一定的意义下，这些元素之间的相互位置关系是不能变动的。【例2.3】学生成绩统计表也是一个线性表，见表2.1。在线性表中每个学生的成绩是一个数据元素，它由学号、姓名、数学、外语、物理、总分这6个数据项组成。该线性表的长度为5。2

4、.1.2线性表的基本运算线性表上常用的基本运算有以下9种：①线性表的初始化（initiate）：将线性表设置成一个空表。②求表的长度（length）：求线性表的长度。③取出表的元素（getdata）：访问线性表中的第i个元素。④查找运算（search）：查找线性表中具有某个特征值的数据元素。⑤插入运算（insert）：在线性表中的第i个元素之前或之后插入一个新元素。⑥删除运算（delete）：删除线性表中第i个元素或满足给定条件的第一个元素。⑦排序运算（sort）：将线性表中的所有元素按给定的关键字进行排序。⑧归并运算（catenate）：把两个线性

5、表合并为一个线性表。⑨分离运算（separate）：将线性表按某一要求分解成两个或几个线性表。线性表常用的存储方式有两种：顺序存储方式和链接存储方式（见第1章中例题1-7和例题1-8）。用顺序存储方式实现的线性表称为顺序表(或称为向量)；用链接存储方式实现的线性表称为链表。本节将分别介绍这两种存储结构，以及在这两种存储结构上如何实现线性表的基本运算。注意：每种数据结构的运算，都与其存储结构有着密切的关系。这是学习数据结构要牢记的要点。线性表的基本运算和数据存储方式是密切相关的。2.2线性表的顺序存储结构及运算2.2.1线性表的顺序存储结构2.2.2顺

6、序表的基本运算2.2.3插入和删除运算的时间分析2.2.4顺序表的优点和缺点【例1.7】请用顺序存储方式表示一周7天，假设一周7天的数据结构为：B=(D,R)D={Sun,Mon,Tue,Wed,Thu,Fri,Sat}R={，，，，，}若采用顺序存储方法将一周7天存储在计算机中，其顺序存储结构如图1.7所示。图1.7线性结构的顺序存储结构示例2.2.1线性表的顺序存储结构线性表的顺序存储方法是：将线性表的所有元素按其逻辑顺序依次存放在内存中一

7、组连续的存储单元中，也就是将线性表的所有元素连续地存放到计算机中相邻的内存单元中，以保证线性表元素逻辑上的有序性。顺序表的特点是：其逻辑关系相邻的两个结点在物理位置上也相邻，结点的逻辑次序和物理次序一致。线性表的顺序存储结构可用数组来实现。线性表的顺序存储结构可用数组来实现。数组元素的类型就是线性表中数据元素的类型，数组的大小，最好大于线性表的长度。因此，顺序存储结构是把线性表中每个元素a1,a2,a3,…,an依次存放到数组下标为0,1,2,…,n1的位置上。假设用数组data［MAXSIZE］存储线性表A=（a1,a2,a3,…,an）其顺序存

8、储结构如图2.1所示。图2.1顺序存储结构示意图nlastsequenlist由于线性表中所有结点的数据类型