③第三章线性表 3.1线性表的类型定义 32顺序存储的线性表 3.3链式存储的线性表 34有序表 3.5顺序表和链表的综合比较 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较
(B3.1线性表的类型定义 3.1线性表的定义 线性表是n(n>=0)个数据元素的有限序列,表中 各个元素具有相同地属性,表中相邻元素间存 在“序偶”关系。 记做:(a1,a2,a1a1a11…,an1an) a1称为a1的直接前驱元素,a*1是a的直接后继 元素 线性表的长度:表中的元素个数n 位序:i元素a在线性表中的位序 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 3.1线性表的类型定义 3.1.1线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中 各个元素具有相同地属性，表中相邻元素间存 在“序偶”关系。 记做：(a1 ,a2 ,…….ai-1 ,ai ,ai+1 ,…,an-1 ,an ) ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继 元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序
G3.12线性表的基本操作 Initlist(&l) Destroy(&l) Clearlist(&l Listempty(l ListLength(L GetElem(l,i, &e 1 ListLength(l Locateltem(l,e) PriorElem(l, cur e, &pre e) NextElem l, cur e, &next e) ListInsert(&l,i, e) 1<=i<= ListLength(l)+ ListDelete(&l, i, &e)1<=k<= Listlength l) ListTraverse(l pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 InitList(&L) Destroy(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) 1<=i<= ListLength (L) LocateItem(L,e) PriorElem(L,Cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) 1<=i<= ListLength (L)+1 ListDelete(&L,i,&e) 1<=i<= ListLength (L) ListTraverse(L) 3.1.2线性表的基本操作
【例3.4】对两个线性表La、Lb表示的集合A和B,求 一个新集合A=AUB算法3.1四 a)从Lb中取一个元素,并删除 b)在La中查询 c)若La中不存在,则将其插入La,重复直至Lb空 【例3.5】对两个线性表La、Lb表示的集合A和B,求 A=A-B算法3.2D a)从Lb中取一个元素,并删除 b)在La中查询 c)若La中存在,则将从La删除,重复直至Lb空 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 【例3.4】对两个线性表La、Lb表示的集合A和B，求 一个新集合A＝AUB 算法3.1 a) 从Lb中取一个元素，并删除 b) 在La中查询 c) 若La中不存在，则将其插入La，重复直至Lb空 【例3.5】对两个线性表La、Lb表示的集合A和B ，求 A=A-B 算法3.2 a) 从Lb中取一个元素，并删除 b) 在La中查询 c) 若La中存在，则将从La删除，重复直至Lb空
③32线性表的顺序表示和实现 321顺序表线性表的顺序存储表示 Const List INit size=100;(C++规范) Const LIStincrement=10 # define listⅠ NIT SIZE100(C规范) typ pede struct Elemtype elem int length int listsIze Incrementsize ISalist pboustc. edu. cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 3.2线性表的顺序表示和实现 3.2.1顺序表——线性表的顺序存储表示 Const LIST_INIT_SIZE=100; (C++规范) Const LISTINCREMENT=10; #define LIST_INIT_SIZE 100 (C规范) typedef struct { Elemtype * elem; int length; int listsize; int incrementsize; }SqList;
③3.22顺序表中基本操作的实现 初始化操作 Initlist Sq 算法3.3四 销毁操作 Destroylist sq 算法34 是否为空 ListEmpy sc 算法3.5心 是否满 ListFull Sq 算法36 求长度 ListLength sq 算法3.7 查找元素操作 LocateElem Sq 算法38 获取元素操作 GetItem Sq 算法3.9 插入元素操作 ListInsert Sq算法3.10时间复杂度O(n 删除元素操作 List Delete Sq算法3.11时间复杂度O(n) 插入和删除操作的时间分析: Ein=2pi(n-i+1)=n/2 Edl-=2qi(n-1=(n-1)/2 pboustc. edu. cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 初始化操作 InitList_Sq 算法3.3 销毁操作 DestroyList_Sq 算法3.4 是否为空 ListEmpy_Sq 算法3.5 是否满 ListFull_Sq 算法3.6 求长度 ListLength_sq 算法3.7 查找元素操作LocateElem_Sq 算法3.8 获取元素操作GetItem_Sq 算法3.9 插入元素操作ListInsert_Sq 算法3.10 时间复杂度O(n) 删除元素操作ListDelete_Sq 算法3.11 时间复杂度O(n) 插入和删除操作的时间分析： Ein=Σpi(n-i+1)=n/2 Edl=Σqi(n-i)=(n-1)/2 3.2.2顺序表中基本操作的实现
③ 查找元素操作算法3时间复杂度Om) 例如:顺序表 Lelem listsize 23754138546217 length =7 i|8 e=38 返回值=4 e=50 返回值=0 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 查找元素操作 算法3.8 时间复杂度O(n) 例如：顺序表 23 75 41 38 54 62 17 L.elem L.length = 7 L.listsize e = 38 p p p p p i 12348 e = 50 p 返回值 = 4 返回值 = 0
③插入元素操作时间复杂度O(n 1>…ai-19“i;… an)改变为 a e. a i-1c9 1 , a 1a2 a ●● n a a 1a2 ●●● e a ●●● 表的长度增加 pboustc. edu. cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 (a1 , …, ai-1 , ai , …, an ) 改变为 a1 a2 … ai-1 ai … an a1 a2 … ai-1 e ai … an , 表的长度增加 (a1 , …, ai-1 , e, ai , …, an ) 插入元素操作 算法3.10 时间复杂度O(n)
③删除元素操作算法时间复杂度om) 19i9 i+12 ,an)改变为 ∠8;-1 a: 9 i+l a;1;a g i+l a a:1 a: a i+1 ●●● a2 a: 1 a 1ai+1 n 表的长度减少 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 删除元素操作 算法3.12 时间复杂度O(n) (a1 , …, ai-1 , ai , ai+1, …, an ) 改变为 ai+1 … an , 表的长度减少 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 (a1 , …, ai-1 , ai+1, …, an )
③3.3顺序表其它算法举例 例36用顺序表表示集合,完成例3.4。 算法3.3时间复杂度O(n2) 例3.10用尽量少得辅助空间将前m个元素和后n 个元素互换 算法325 exchange l时间复杂度:Om×n)四 算法3.26 invert时间复杂度:O(ts+1) 算法3.27 exchange2时间复杂度:Omn)D pboustc. edu. cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 例3.6 用顺序表表示集合，完成例3.4。 算法3.13 时间复杂度O(n2 ) 例3.10 用尽量少得辅助空间将前m个元素和后n 个元素互换 – 算法3.25 exchange1 时间复杂度：O(m×n) – 算法3.26 invert 时间复杂度：O(t-s+1) – 算法3.27 exchange2 时间复杂度：O(m+n) 3.2.3顺序表其它算法举例