数学数据结构.pptxVIP

第2章 线性表 ;图2.1 线性表的逻辑结构 ; 例如： 英文字母表(A, B, …, Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素， 每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A， 而字母B的后面是字母C。 在较为复杂的线性表中，数据元素(data elements) 可由若干数据项组成，如学生成绩表中，每个学生及其各科成绩是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item) 组成， 常被称为一个记录(record) ，含有大量记录的线性表称为文件(file)。数据对象（data object）是性质相同的数据元素集合。 ;表2-1 车辆登记表 ; 线性表(Linear List)是由n (n≥0)个类型相同的数据元素a1, a2, …， an组成的有限序列，记作（a1, a2, …，ai-1，ai，ai+1， …，an）。这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同情况下可以不同， 它既可以是原子类型，也可以是结构类型但同一线性表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1, a2, …，ai-1, ai, ai+1, …, an）， 表中ai-1 领先于ai，称ai-1 是ai的直接前驱，而称ai是 ai-1的直接后继。除了第一个元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。 线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。 ; 线性表的特点可概括如下：  同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。  有穷性：线性表由有限个数据元素组成， 表长度就是表中数据元素的个数。  有序性：线性表中表中相邻数据元素之间存在着序偶关系ai, ai+1。  由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。 ;2.1.2 线性表的抽象数据类型定义;（2） DestroyList(L) 操作前提： 线性表L已存在。  操作结果： 将L销毁。  （3） ClearList(L) 操作前提： 线性表L已存在 。  操作结果： 将表L置为空表。  （4） EmptyList（L） 操作前提： 线性表L已存在。  操作结果： 如果L为空表则返回真， 否则返回假。 ; （5） ListLength（L） 操作前提： 线性表L已存在。  操作结果： 如果L为空表则返回0， 否则返回表中的元素个数。 （6） Locate(L, e) 操作前提： 表L已存在， e为合法元素值。  操作结果： 如果L中存在元素e， 则将“当前指针”指向元素e所在位置并返回真， 否则返回假。  （7） GetData(L, i) 操作前提： 表L存在， 且i值合法， 即1≤i≤ListLength（L）。 操作结果： 返回线性表L中第i个元素的值。 ; （8） InsList(L, i, e) 操作前提：表L已存在，e为合法元素值且1≤i≤ListLength(L)+1。  操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。 （9） DelList(L, i, e) 操作前提： 表L已存在且非空， 1≤i≤ListLength(L)。 操作结果： 删除L的第i个数据元素， 并用e返回其值， L的长度减1。  } ADT LinearList ;2.2 线性表的顺序存储; 假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(a -i)：  loc(ai) =loc(a1)+(i-1)×k 其中loc(a -1)称为基地址。 ;图2.2 顺序表存储示意图 ; 顺序存储结构可以借助于高级程序设计语言中的一堆数组来表示，一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言定义如下： ;2.2.2 线性表顺序存储