DS02-线性表 课程教案.pptVIP

第2章 线性表 线性表的顺序存储 线性表的链式存储 线性表两种不同存储结构的比较 线性表的应用 2.1 线性表的基本概念 线性结构的基本特征是： ①有而且只有一个“第一元素”； ②有而且只有一个“最后元素”； ③除第一元素之外，其他元素都有唯一的直接前趋； ④除最后元素之外，其他元素都有唯一的直接后继。 线性表是一种常用的简单的数据结构，它属于线性结构的范畴。 线性表（Linear List）是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记为： ( a1， a2， … ai-1， ai， ai+1，… an) 其中，数据元素的个数n称为线性表的长度。当n＝0 时称为空表。 例2.3 26个大写英文字母表（A,B,C,…,Z）的表长是26，起始结点A没有直接前趋，A的唯一的直接后继是B；终端结点Z没有直接后继， Z的唯一的直接前趋是Y；而对于B,C,D, …,Y中的任意一个字母，都有一个唯一的直接前趋和一个唯一的直接后继。 线性表的基本操作 initList(L)：初始化操作，构造一个空线性表L ClearList(L)：清除线性表L的内容，将L置为空表 ListLength(L)：求表长(表中元素个数) ins(L，i，Item)：插入数据 Del(L，i)：删除数据 线性表的基本操作（续） GetNode(L，i)：获取表L中位置i的结点值 Loc(L，Item)：定位(按值查找) GetPrior(L，Item，p)：获取值为Item的结点的前趋结点 GetNext(L，Item，p) :获取值为Item的结点的后继结点 2.2 线性表的顺序存储 线性表的顺序存储方式，就是利用一段连续的内存地址来存储线性表的数据元素。在C语言中，是用一个数组来实现的。 线性表的这种机内表示称作线性表的顺序存储结构或顺序映象。同时，我们把这种顺序存储结构的线性表称为顺序表。 例2.4 一个顺序存储结构的线性表（顺序表）的例子。 typedef struct { char name[20]; /*姓名*/ char no[10]; /*学号*/ float score; /*成绩*/ }STUDENT； STUDENT s[20]; 则s就是一个以STUDENT类型为数据元素的线性表。 线性表L中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足如下关系： LOC(ai+1)=LOC(ai)+m 线性表L的第i个元素的存储位置和第一个元素的存储位置的关系为： LOC(ai)=LOC(a1)+(i-1)*m 其中LOC(a1)是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基地址。 顺序表的基本操作 顺序表的C语言描述 typedef int datatype; /*定义表元素类型*/ #define maxsize 1024 /*线性表的最大长度*/ typedef struct { datatype elem[maxsize];/*存放表结点的数组*/ int length; /*表长*/ }sequenlist; 顺序表的基本操作 顺序表的初始化 算法2.1 构造一个空的顺序表 void InitList(sequenlist *L) { L- length=0; } 顺序表的基本操作 清除一个线性表的内容 要清除一个已经存在的线性表的内容，只需要把该线性表设置为空表，也就是把表长置为0。 算法2.2 清除一个线性表的内容 void ClearList(sequenlist *L) { L-length=0; } 本算法时间复杂度为O（1）。 顺序表的基本操作 定位(按值查找)： 要查找一个值，只需要从头到尾的遍历线性表，如果找到，则返回找到的位置，否则继续，如果一直到最后一个位置都没有找到，则返回0。 本算法中，可能找到Item，这时候，平均比较次数为O(n/2)，其中，n是线性表的长度；也可能找不到Item，这时候，算法的比较次数为O(n)。因此，总结起来，本算法的时间复杂度为O(n)。 算法2.3 定位（按值查找） int Loc(sequenlist L，datatype Item) { int i,j; j=L.length; /*表的长度*