【数据结构与算法】线性表1.pptVIP

第二章 线性表 2．1 线性表的类型定义 2．2 线性表的顺序表示与实现 2．3 线性表的链式表示与实现 2．3．1 线性链表 2．3．2 循环链表 2．3．3 双向链表 第二章 线性表 线性结构的特点是: 存在唯一的”第一个”数据元素; 存在唯一的”最后一个”数据元素; 除第一个外,每个数据元素均有且只有一个前驱元素; 除最后一个外,每个数据元素均有且只有一个后继元素。 实验要求与习题 理论习题 2.2, 2.10, 2.11 实验题: ①写一个主程序来上机验证算法2.3、算法2.4、算法2.5； ②2.12 * * 2．1 线性表的类型定义 线性表举例: 字母表 (A,B,C,…,X,Y,Z) 数据序列 (6,17,28,50,92,188) n个元素的线性表: （a1, a2 ,…, ai, ai+1, …, an） 第一个元素 (没有前驱) 第i个元素 (有唯一的前驱 和唯一的后继) 最后一个元素 (没有后继) 线性表的抽象数据类型(ADT) ADT List{ 数据对象：D = {ai | ai属于Elemset, (i=1,2,…,n, n≥0)} 数据关系：R1 = {＜ai-1,ai＞|ai-1,ai属于D,(i=2,3,…,n)} 基本操作： InitList(L); DestroyList(L); ListInsert(L,i,e); ListDelete(L,i,e); 等等 } ADT List InitList(L); DestroyList(L); ClearList(L); ListEmpty(L); ListLength(L); GetElem(L, i, e); LocateElem(L, e, compare()); PriorElem(L, cur_e, pre_e); NextElem(L, cur_e, next_e); ListInsert(L, i, e); ListDelete(L, i, e); ListTraverse(L, visited()) 线性表ADT的基本操作： InitList(L) 操作结果:构造一个空的线性表L。 DestroyList(L) 初始条件: 线性表L已经存在。 操作结果: 销毁线性表L。 ClearList(L) 初始条件: 线性表L已经存在。 操作结果: 将线性表L重置为空表。 基本操作(一)： ListEmpty(L) 初始条件: 线性表L已经存在。 操作结果: 若线性表L为空表，则返回TURE;否则返回FALSE。 ListLength(L) 初始条件: 线性表L已经存在。 操作结果: 返回线性表L中的数据元素个数。 基本操作(二)： GetElem(L, i, e)； 初始条件: 线性表L已经存在，1=i= ListLength(L)。 操作结果: 用e返回线性表L中第i个数据元素的值。 LocateElem(L, e, compare()) 初始条件: 线性表L已经存在，compare()是数据元素判定函数。 操作结果: 返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。 基本操作(三)： PriorElem(L, cur_e, pre_e) 初始条件: 线性表L已经存在。 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败; pre_e无意义。 NextElem(L, cur_e, next_e) 初始条件: 线性表L已经存在。 操作结果:若cur_e是L的数据元素, 且不是第最后个,则用next_e返回它的后继,否则操作失 败, next_e无意义。 基本操作(四)： ListInsert(L, i, e) 初始条件: 线性表L已经存在，1=i= ListLength(L)+1。 操作结果: 在L的第i个位置之前插入新的数据元素e, L的长度加一。 插入前（长度为n） : （a1,a2,…, ai-1 , ai,…,an） 插入后（长度为n+1） : （a1,a2,…, ai-1,e,ai, …,an） 基本操作(五)： ListDelete(L,i,e) 初始条件: 线性表L已经存在，1=i= ListLength(L)。 操作结果: 删除L的第i个数据元素,并用e返回其值, L的长度减一。 删除前（长度为n ） : （ a1,a2,…, ai-1, ai, ai+1