《数据结构精品教学》线性表（顺序存储）.ppt

第2章 线性表 编程任务——火车售票系统 要求实现的功能： 输入列车的班次信息，包括：班次号、起点、终点、开车时间、余票量等 查询列车基本信息：可根据班次号或起点、终点查询 订票功能：可输入班次号和订票数 退票功能 编程任务——火车售票系统 编程任务——火车售票系统 编程任务——火车售票系统 2.1.1 线性表的定义 1. 定义：线性表是具有相同属性的数据元素的一个有限序列。 线性表中的各元素都具有同种数据类型。 线性表的长度可用n(n=0)表示。表中所含元素个数即为线性表的长度。特殊情况n=0。且线性表的长度可变。 表中各元素在位置上有序。有序性就是一种线性关系。 2. 表示法： 1) 一般表示 2) 二元组表示 3) 图示法 3. 线性表的应用： 任何一种线性的结构都可以用线性表的形式表示出来，只要按照元素之间的逻辑关系把它们排列起来即可。如日常生活中碰到的各种各样的表。 有序表和无序表：一个线性表中若存在有序（升序或降序）排列的字段，则称该字段为有序字段，该线性表为有序表。 若表中不存在任何有序字段，则为无序表。 2.2.1 线性表的顺序存储 特点：在内存中开辟一块连续空间，按照表中元素的逻辑排列顺序依次存储。 顺序存储的实现：数组 要求：1) 类型一致 2) 数组的大小 线性表长度 顺序表的定义： 2.2 线性表的顺序存储和操作实现 struct List{ ElemType list[MaxSize];  int size;  }; 成员一：数组list： 1）数组的作用是存放线性表中元素。线性表中的ai元素被存放在数组list中下标为i-1的位置上，即list[i-1]位置对应ai元素。 2）其中数组元素类型ElemType是事先通过typedef语句定义好的一种数据类型，它可以代表任何一种数据类型。 3）其中MaxSize是事先通过const常量定义语句定义好的一个常量，用它表示数组的大小，也就是可以存放线性表的最大长度。 例： const int MaxSize=20; typedef int ElemType; 成员二：整型变量size 表示当前线性表的长度（此长度可变）。 说明：定义为List类型的任一变量就表示一个顺序表。该顺序表的长度为size。当size＝0时，则表空，不能进行删除操作；当size＝MaxSize时，则表满，不能进行插入操作。 struct List{ ElemType list[MaxSize];  int size;  }; 2.2.2 顺序表上的操作（各项操作的函数定义部分） 1、函数名：InitList 形参：顺序表L 返回值：无 功能：初始化表L，即将顺序表L的长度置为0。 2、函数名：ClearList 形参：顺序表L 返回值：无 功能：清空表中所有元素，即将顺序表L的长度置为0。 3、函数名：LenthList 形参：顺序表L 返回值：表的长度，即表中元素个数。 功能：获取顺序表L中元素个数，即L.size。 4、函数名：EmptyList 形参：顺序表L 返回值：true（当表为空）或 false（当表非空） 功能：判断顺序表L是否空，即表中元素个数是否为0。 5、函数名：GetList 形参：顺序表L，要取元素的位置pos 返回值：表L中第pos个元素的值。 功能：从顺序表L中取出第pos个元素。 说明：首先判断pos是否越界。取元素时要注意第pos个元素对应数组下标为pos-1 6、函数名：TraverseList 形参：顺序表L 返回值：无 功能：遍历顺序表L，并在屏幕上逐个输出表L中每个元素的值。