顺序表中基本操作的实现初始化操作InitList Sq查找元素操作LocateltemSqO(n)插入元素操作ListInsert Sq.O(n)删除元素操作ListDeleteSqO(n)归并操作MergeList_Sq//算法2.7O(n+m)对比算法2.2.2.72.12插入和删除操作的时间分析：Ein=Zp;(n-i+1)=n/2Edl=Zp;(n-i)=(n-1)/2T6中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 初始化操作 InitList_Sq 查找元素操作 LocateItem_Sq O(n) 插入元素操作 ListInsert_Sq O(n) 删除元素操作 ListDelete_Sq O(n) 归并操作MergeList_Sq O(n+m) //算法2.7 插入和删除操作的时间分析： Ein=Σpi (n-i+1)=n/2 Edl=Σpi (n-i)=(n-1)/2 顺序表中基本操作的实现 对比算法2.2 2.7 2.12
查找元素操作时间复杂度O(n）例如：顺序表L.listsizeL.elem23|7541|38|5416217L.length = 7838e=返回值=450=返回值0e中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 查找元素操作 时间复杂度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）(ai, ., ai-, a;, .. , an) 改变为(ai, .., ai., e, ai, .., an)<ai-1, a;><ai-1, e>, <e, a,>anaiaai-1a:a;aa1a2ai-1eh表的长度增加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 ) 插入元素操作 时间复杂度O(n)
删除元素操作时间复杂度O(n）国(a, ..., ai, aj, ai+1, , an) 改变为(ai, ..., aii, ai1, .., an)<ai-1, a,>, <a;, ai+1><ai-1, ai+1aa:aiai-lait1anaiazai-1ai+1a表的长度减少89中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 9 中国科学技术大学 删除元素操作 时间复杂度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 )
顺序表其它算法举例>比较两个顺序表的大小（逐个比较元素字符）时间复杂度O(Min(A.length,B.length))>用尽量少得辅助空间将前m个元素和后n个元素互换一exchangel时间复杂度：O(mxn)一invert时间复杂度：O(t-s+l)一exchange2时间复杂度：O(m+n注意：代码简洁和效率是两回事10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 ➢比较两个顺序表的大小 (逐个比较元素字符) 时间复杂度O(Min(A.length,B.length)) ➢用尽量少得辅助空间将前m个元素和后n个元 素互换 – exchange1 时间复杂度：O(m×n) – invert 时间复杂度：O(t-s+1) – exchange2 时间复杂度：O(m+n) 顺序表其它算法举例* 注意：代码简洁和效率是两回事