数据结构郝春梅C语言版第2章.ppt

第2章 线 性 表 学习目标与要求： 了解线性表的逻辑定义。 熟练掌握线性表的顺序存储结构及顺序表的基本操作，并能够分析顺序表上各基本操作的时间复杂度。 熟练掌握线性表的链式存储结构——单链表以及单链表上的各基本操作的实现，并能够分析单链表上各基本操作的时间复杂度。 掌握循环链表和双向链表两种存储结构。 掌握顺序表和单链表各自的特点及各自适用的场合。 能够利用顺序表和单链表的基本操作实现关于线性表复杂算法的设计。 2.1 线性表的定义及其基本操作 2.1.1 线性表的引例 某学校大一学生的成绩表如表2.1所示，表中每个学生的情况为一个数据元素或称为记录，它由学号、姓名、英语、高数、计算机5个数据项组成。 2.1.2 线性表的定义 一个线性表是由零个或多个具有相同类型的数据元素组成的一个有序集合。通常把线性表记作： L: (a1, a2, a3, …, ai, …, an) 元素的个数n称为线性表的长度，n=0时，线性表为空表。线性表中每个元素的位置都是确定的，a1是第一个数据元素，an是最后一个数据元素。每个元素ai都有一个直接前驱ai-1，一个直接后继ai+1。线性表的特征为数据元素之间具有一对一的线性关系。 2.1.3 线性表的基本操作 (1) INITIATE(L)：初始化操作，生成一个空的线性表L。 (2) LENGTH(L)：求表长度的操作。函数的返回值为线性表L中数据元素的个数。 (3) GET(L, i)：取表中位置i处的元素。当1≤i≤LENGTH(L)时，函数值为线性表L中位置i处的数据元素，否则返回一个空值。 (4) LOCATE(L, x)：定位操作。给定值x，在线性表L中若存在和x相等的数据元素，则函数返回该数据元素的位置值，否则返回0。若线性表中存在一个以上和x相等的数据元素，则函数返回第一个和x相等的数据元素的位置值。 2.1.3 线性表的基本操作 (5) INSERT(L, I, b)：插入操作。在给定的线性表L中的位置i(1≤i≤LENGTH(L)+1)处插入数据元素b。 (6) DELETE(L, i)：删除操作。在线性表L中删除位置i(1≤i≤LENGTH(L))处的数据元素。 (7) EMPTY(L)：判断线性表L是否为空。若L为空，则函数返回1，否则函数返回0。 (8) CLEAR(L)：置空操作。将线性表L置成空表。 2.2 线性表的顺序存储结构 2.2.1 顺序表结构 线性表的实现包括以下两部分。 (1) 选择适当的形式来存储线性表。 (2) 用相应的函数实现线性表的基本操作。 在计算机中可以用不同的方式来存储线性表，主要的存储结构有两种：顺序存储结构和链式存储结构。 2.2 线性表的顺序存储结构 线性表的顺序存储是指在用一组地址连续的存储单元依次存储线性表的数据元素，我们把用这种存储形式存储的线性表称为顺序表。顺序表的逻辑顺序和物理顺序是一致的。 设 a 1 的存储地址LOC(a 1)为首地址B，每个数据元素占d个存储单元，则第i个数据元素的地址为： LOC(ai)=LOC(a 1)+(i-1)*d 1=i=n 即： LOC(ai)=B+(i-1)*d 这就是说只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。 2.2 线性表的顺序存储结构 图2.1所示为线性表在计算机内的顺序存储结构示意图。 2.2 线性表的顺序存储结构 顺序表使用C语言的一维数组描述如下： #define DATATYPE1 int #define MAXTSIZE 100 typedef struct { DATATYPE1 data[MAXSIZE]; int len; }SEQUENLIST; 2.2.2 顺序表的基本操作 1. 初始化操作 初始化操作的算法描述如下： void INITIATE(SEQUENLIST *L) { L-len=0; return; } 2. 求表长度的操作 求表长度操作的算法描述如下： int LENGTH(SEQUENLIST *L) { return(L-len); } 2.2.2 顺序表的基本操作 3. 取元素操作 取元素操作的算法描述如下： DATATYPE1 GET( SEQUENLIST *L,int i) { if( i1||iL-len) return(NULL); else return(L-data[i-1]); } 2.2.2 顺序表的基本操作 4. 定位操作 定位操作的函数描述如下： int LOCATE( SEQ