第二章_线性表

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

1、第二章线性表9/9/2021北京联合大学信息学院本章导读本章要点：线性表的基本概念、线性表的顺序存储、链式存储、线性表的两种不同存储比较，线性表的应用。通过本章的学习，掌握线性表的基本概念、顺序表和单链表上的基本运算。掌握循环链表、双向链表和静态链表的概念。能够利用线性表解决实际问题。9/9/2021北京联合大学信息学院2.1线性表的基本概念线性表（Linearlist）是最简单且最常用的一种数据结构。线性表是具有相同类型的n（n≥0）个数据元素（结点）a1,a2,…,an组成的有限序列。其中数据元素的个

2、数n定义为表的长度。当n=0时称为空表，常常将非空的线性表（n>0）记作：（a1,a2,…,an)这里的数据元素ai(1≤i≤n)只是一个抽象符号，具体含义视情况而不同。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。9/9/2021北京联合大学信息学院2.1线性表的逻辑结构例如：英文字母表（A，B，C，…，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；某公司2003年每月产

3、值表（400，420，500，…，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录(record)含用大量记录的线性表又称为文件例如，图2.1学生成绩表就是一个线性表，表中每一个学生的成绩就是一个记录，每个记录包含六个数据项：学号、姓名、高等代数……。9/9/2021北京联合大学信息学院2.1线性表的逻辑结构图2.1学生成绩表

4、9/9/2021北京联合大学信息学院2.1线性表的逻辑结构矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。因此，线性表或者是一个空表（n=0），或者可以写成：（a1，a2，a3，…，ai-1，ai，ai+1，…，an）。9/9/2021北京联合大学信息学院2.1线性表的基本操作数据的运算(线性表的基本操作）是定义在逻辑结构上的，而运算的具体实现则是在存储结构上。线性表的基本运算：（1）置空表I

5、nitList(L):将线性表L置成空表（2）求长度ListLength(L):求线性表L中结点个数（3）取结点GetNode(L,i):取出线性表L中第i个结点（4）定位Locate(L,x):在线性表L中查找x的位置（5）插入Insert(L,x,i):在线性表L的第i个位置插入一值为x的新结点（6）删除Delete(L,i):删除线性表L的第i个结点9/9/2021北京联合大学信息学院2.2线性表的顺序存储结构和实现在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储

6、结构，线性表称为顺序表。2.2.1线性表的顺序存储结构在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为Loc(a1)，每一个数据元素占d字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：Loc(ai)=Loc(a1)+(i-1)*d9/9/2021北京联合大学信息学院只要确定了

7、存储线性表的起始位置，线性表中任一元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特点:(1)数据中的元素间的地址是连续的；(2)数组中所有元素的数据类型相同。这两特点与线性表的顺序存储结构类似。9/9/2021北京联合大学信息学院2.2线性表的顺序存储结构顺序表数据类型描述typedefintdatatype#definemaxsize1024typedefstruct{datatypedata[maxsi

8、ze];intlength;}sequenlist;9/9/2021北京联合大学信息学院2.2线性表的顺序存储结构顺序表是用向量实现的线性表，向量的下标可以看成是结点的相对地址。它的特点是逻辑上相邻的结点其物理上亦相邻。2.2.2顺序表上的基本运算1.顺序表的插入操作线性表的插入运算是指在表的第i（1≤i<≤n)个位置上，插入新结点x,使长度为n的线性表：（a1，…，ai-1，ai，…，an）变成长度为n+1的线性表：（a1，