顺序表中基本操作的实现算法2.3初始化操作InitListSq算法2.4销毁操作DestroyList Sq算法2.5√是否为空ListEmpy_Sq算法2.6是否满ListFull_Sq算法2.7求长度 ListLength_sq算法2.8查找元素操作LocateElemSq算法2.9获取元素操作GetItemSq插入元素操作ListInsertSg算法2.10时间复杂度0(n）删除元素操作ListDeleteSq算法2.11时间复杂度O(n)插入和删除操作的时间分析：Ein=Zpi(n-i+1)=n/2Edl=Zqi(n-i)=(n-1)/26中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 • 顺序表中基本操作的实现 初始化操作 InitList_Sq 算法2.3 销毁操作 DestroyList_Sq 算法2.4 是否为空 ListEmpy_Sq 算法2.5 是否满 ListFull_Sq 算法2.6 求长度 ListLength_sq 算法2.7 查找元素操作 LocateElem_Sq 算法2.8 获取元素操作 GetItem_Sq 算法2.9 插入元素操作 ListInsert_Sq 算法2.10 时间复杂度O(n) 删除元素操作 ListDelete_Sq 算法2.11时间复杂度O(n) • 插入和删除操作的时间分析： Ein=Σpi(n-i+1)=n/2 Edl=Σqi(n-i)=(n-1)/2
查找元素操作算法2.8时间复杂度O(m）例如：顺序表LlistsizeL.elem237541385462117pL.length = 7838e==4返回值50e=返回值=0中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 查找元素操作 算法2.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
算法2.10时间复杂度0(n)插入元素操作(ai,.., a, ai,.., an)改变为(ai, ..., a, e, a, .., an)<ai-1, a><ai-1, e>, <e, a,>aiaiazai-1aiaea,aza;-1表的长度增加8中国科学技术大学ypb@ustc.edu.cn
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 ) 插入元素操作 算法2.10 时间复杂度O(n)
删除元素操作算法2.12时间复杂度0(n）(aj, .., ai-1, ai, ai1, .., an)改变为(a, .., ai1, ai1, ..., an)<ai-1, a,>, <aj, a;+1><a;-1a:aaiaza.ai-1ailna2ai-1a;+1a.1表的长度减少309中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 9 中国科学技术大学 删除元素操作 算法2.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 )
顺序表其它算法举例例2.6用顺序表表示集合，完成例2.4。算法2.13时间复杂度O(n2)例2.10用尽量少得辅助空间将前m个元素和后n个元素互换一算法2.25exchangel时间复杂度：O(mxn)一算法2.26invert 时间复杂度：O(t-s+1)-算法2.27exchange2时间复杂度：O(m+n)10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 例2.6 用顺序表表示集合，完成例2.4。 算法2.13 时间复杂度O(n2 ) 例2.10 用尽量少得辅助空间将前m个元素和后n 个元素互换 – 算法2.25 exchange1 时间复杂度：O(m×n) – 算法2.26 invert 时间复杂度：O(t-s+1) – 算法2.27 exchange2 时间复杂度：O(m+n) 顺序表其它算法举例