③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 15 as a;u,e>,<e,a;> 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 <ai-1 , ai > <ai-1 , e>, <e, ai > 表的长度增加 (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 <ai-1 , ai >, <ai , ai+1> <ai-1 , ai+1> 表的长度减少 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顺序表其它算法举例