第2章 线性表-20060307-5-HB.ppt

第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示与实现 2.3 线性表的链式表示与实现 2.4 线性表应用举例 2.1 线性表的类型定义 线性表是一种最基本的数据结构，在各种程序里应用广泛，还常作为实现更复杂的数据结构的基础。 线性表是一种线性结构，非空线性表中： 存在唯一的称为“第一个”的元素； 存在唯一的称为“最后一个”的元素； 除第一个之外，表中的每个元素都有且只有一个 前驱元素； 除最后一个之外，表中的每个元素都有且只有一 个后继元素。 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。 线性表的一般表示为: (a1,a2,…ai,ai+1,…,an) 当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1≤i≤n)。 关系：a0, a1,a1,a2 ,…,an-2, an-1。是一种顺序关系（线性关系） 2.1 线性表的类型定义 线性表的运算 初始化线性表InitList(L):构造一个空的线性表L。 销毁线性表DestroyList(L):释放线性表L占用的内存空间。 判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。 求线性表的长度ListLength(L):返回L中元素个数。 输出线性表DispList(L):当线性表L不为空时,顺序显示L中各结点的值域。 求线性表L中指定位置的某个数据元素GetElem(L,i,e):用e返回L中第 i(1≤i≤ListLength(L))个元素的值。 2.1 线性表的类型定义 线性表的运算 定位查找LocateElem(L,e):返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。 插入数据元素ListInsert(L,i,e):在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。 删除数据元素ListDelete(L,i,e):删除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。 还可以有其它操作，ClearList(), PriorElem(), NextElem()…… 线性表与数组比较 2.2 线性表的顺序表示和实现 线性表的一种可能实现方式是顺序存放其元素 把元素顺序存在一片连续存储区域中，形成的结构称为顺序表。借助元素在内存的“物理位置相邻”表示表中元素间的顺序逻辑关系（隐式表示元素间的关系） 顺序表中任一数据元素的位置都可以算出，因此可在O(1)时间直接存取。 元素ai的地址计算公式： Locate (ai) = Locate(a1) ＋ c * (i-1) 其中c = sizeof (ElemType)为每个元素需占用的存储单元个数 顺序表，可看作是以数组作为基础实现线性表 数组的元素个数固定，线性表的元素个数可以随操作改变，需设法弥合两者差异。 需记录表中元素个数。必须维持元素个数记录和表中实际元素个数一致 顺序表的C实现——类型定义 (注意两个要素：线性表的基地址，表长度) 定义1： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 ElemType elem[LIST_INIT_SIZE]; int length; //没有反映elements 和length的内在联系;引进SeqList类型 定义2：（用结构将相关数据成分包装起来） struct SeqList { int length; ElemType elem [LIST_INIT_SIZE]; }SeqList; 线性表的顺序存储结构的特点 优点 构造原理简单、直观，易理解。 元素的存储地址可以通过一个简单的解析式计算出来。 缺点 存储分配需要事先进行。 需要一片地址连续的存储空间 基本操作(如插入删除)的时间效率较低 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 线性表的链式存储结构的特点 用一组任意的存储单元存储线性表的数据元素（这组元素可以是连续的，也可以是不连续的） 为了表示数据元素之间的逻辑关系，是通过在元素相关位置存放对其他元素的引用，显式指明元素间关系。这样建起的结构称为链接结构，用这种方式实现的表称为链接表（链表） 最简单的链表是单链表：为每个元素关联一个链接，表示后继关系（没有表示前驱关系的信息） 结点：元素的存储映象，包括数据域和指针域 单链表：与表中n个元素对