第二章线性表 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={<a-1->|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的基本操作：