浙江大学：《数据结构与算法》第二章（2-1） 线性表的类型定义

第二章线性表 2.1线性表的类型定义 2.2线性表的顺序表示与实现 2.3线性表的链式表示与实现 2.3.1线性链表 2.3.2循环链表 2.3.3双向链表

第二章 线性表 ◼ 2．1 线性表的类型定义 ◼ 2．2 线性表的顺序表示与实现 ◼ 2．3 线性表的链式表示与实现 ◼ 2．3．1 线性链表 ◼ 2．3．2 循环链表 ◼ 2．3．3 双向链表

第二章线性表 ■线性结构的特点是 存在唯一的”第一个”数据元素; 存在唯一的”最后一个”数据元素; 除第一个外,每个数据元素均有且只有一个前驱 元素; n除最后一个外每个数据元素均有且只有一个后 继元素

第二章 线性表 ◼ 线性结构的特点是: ◼ 存在唯一的”第一个”数据元素; ◼ 存在唯一的”最后一个”数据元素; ◼ 除第一个外,每个数据元素均有且只有一个前驱 元素; ◼ 除最后一个外,每个数据元素均有且只有一个后 继元素

2.1线性表的类型定义 ■线性表举例 字母表(A,B,C,,X,Y,Z ■数据序列(6,17,28,50,92,188) n个元素的线性表: a 15a2··aiai+19·9an 第一个元素 第i个元素 (没有前驱) 最后一个元素 有唯一的前驱(没有后继) 和唯一的后继)

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={a1a1属于 Elemnet,(i=1,2,…,n, n≥0) n数据关系:R1={|a1,a,属于D(i=2,3,,n)} 基本操作: InitList(&l); Destroylist(&l); ListInsert(&L, i,e); ListDelete (&l, i, &e); 等等 ■} ADT List

线性表的抽象数据类型(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

线性表ADT的基本操作: Initlist(&l); Destroy list(&l); Clearlist(&l); listempty l); Listlength L); GetElem(L, i, &e); LocateElem(l, e, compareD PriorElem(L, cur e, &pre e) NextElem(L, cur e, &next e); ListInsert(&l, i, e); ListDelete(&l, i, &e) ListTraverse(&l, visited

◼ 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重置为空表

◼ InitList(&L) ◼ 操作结果:构造一个空的线性表L。 ◼ DestroyList(&L) ◼ 初始条件: 线性表L已经存在。 ◼ 操作结果: 销毁线性表L。 ◼ ClearList(&L) ◼ 初始条件: 线性表L已经存在。 ◼ 操作结果: 将线性表L重置为空表。 基本操作(一)：

基本操作(二) ListEmpty( L) 初始条件:线性表L已经存在。 操作结果:若线性表L为空表,则返回 TURE否则返回 FALSE。 Listlength(l) 初始条件:线性表L已经存在 操作结果:返回线性表L中的数据元素个数

◼ ListEmpty(L) ◼ 初始条件: 线性表L已经存在。 ◼ 操作结果: 若线性表L为空表，则返回 TURE;否则返回FALSE。 ◼ ListLength(L) ◼ 初始条件: 线性表L已经存在。 ◼ 操作结果: 返回线性表L中的数据元素个数。 基本操作(二)：

基本操作(三 Getelen(L,i,&e);初始条件:线性表L已经存 在,1<== ListLength(L)。 ■操作结果:用e返回线性表L中第i个数据元素的值。 Locateelem(L, e, compare) 初始条件:线性表L已经存在, compare()是数据元 素判定函数。 ■操作结果:返L中第1个与e满足 compare()的数据 元素的位序。若这样的数据元素不存在则返回值为 0

◼ 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已经存在。 操作结果:若cure是L的数据元素,且不是第一个,则 用pree返回它的前驱否则操作失败;pree无意义。 NextElem L, cur e, &next e ■初始条件:线性表L已经存在 操作结果:若cure是L的数据元素,且不是第最后个 则用 next e返回它的后继否则操作失败, next e无 意义

◼ 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<=<= Listlength(L)+1。 操作结果:在L的第i个位置之前插入新的数据元素e L的长度加 插入前(长度为n) a1.a a-1 插入后(长度为n+1) a1.a 25···ai-1

◼ 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） 基本操作(五)：