r=true;∥设置删除正常标志 return r, 算法的时间复杂度分析: 设表长LSze记为n。元素前移语句的频度是n-i,因此 元素的移动次数也是由表长n和位置快定的。 若i=n,则由于循环变量的初值大于终值,前移语句将 不执行,无需移动元素;若==1,则前移语句将循环执 行n-1次,需移动表中除开始元素外的所有元素。这两 种情况下算法的时间复杂度分别是01)厢和O(n)
r = true; // 设置删除正常标志 } return r; } 算法的时间复杂度分析： 设表长L.Size记为n。元素前移语句的频度是n-i，因此 元素的移动次数也是由表长n和位置i决定的。 若i==n，则由于循环变量的初值大于终值，前移语句将 不执行，无需移动元素；若i==1，则前移语句将循环执 行n-1次，需移动表中除开始元素外的所有元素。这两 种情况下算法的时间复杂度分别是O(1)和O(n)
令E(mn表示在长度为n的线性表中删除一个元素所需移动 元素的平均次数,则 qim de i=1 其中,q表示删除表中第个元素的概率;n是删除表中第个 元素时所需要移动元素的次数,即n;=n-,在等概率的假设 下q1=q2=…qn=,因此得到 de qimi l=1 l=1 即,顺序表的删除与插入类似,约需移动一半元素 ,其平均时间复杂度也是on
令Ede(n)表示在长度为n的线性表中删除一个元素所需移动 元素的平均次数，则 = = n i 1 E de qi mi 其中，q i表示删除表中第i个元素的概率；n i是删除表中第i个 元素时所需要移动元素的次数，即n i = n-i，在等概率的假设 下 q1=q2=…qn = ，因此得到 2 n 1 n i 1 n 1 n i 1 i i q m (n i) de E − = = = = − = 即，顺序表的删除与插入类似，约需移动一半元素 ，其平均时间复杂度也是O(n)
3.查找 线性表的查找操作可分为: 按序号查找 Getnode(L,e)和 按内容查找 Locate node(L,e)两种。 当然,还可以不在整个表查找元素e,只在给定 loW-up区间查找值为e的元素。 下面给出按内容查找的算法描述
线性表的查找操作可分为： 按序号查找GetNode (L, i,e) 和 按内容查找LocateNode(L, e)两种。 ⒊ 查找 当然，还可以不在整个表查找元素e，只在给定 low-up区间查找值为e的元素。 下面给出按内容查找的算法描述：
int LocateNode(sqlist &L, int e) ∥查找表L中值为e的数据元素 ∥返回值为1表示没找到,否则是被查找结点的序号 I int i=0; while(i<L Size&&L elem(l=e )i++ if(is l size)return i+1 else return -1
int LocateNode(sqList &L,int e) // 查找表L中值为e的数据元素; // 返回值为-1表示没找到，否则是被查找结点的序号 { int i=0; while( i<L.Size && L.elem[i]!= e )i++; if(i< L.Size) return i+1; else return -1; }
4.顺序表的应用例 【例21】设表la和b分别表示整数集合A和B, 且用数组存储,求:A=AUB。 算法思路:集合中的元素是无重复的,可将Lb表中 的元素从表尾起逐个删除,并在La表查找被删元素 b,若找不到,则将元素b插入La表,否则不必插入 完成后集合B为空
⒋ 顺序表的应用例 【例2.1】设表la和lb分别表示整数集合A和B， 且用数组存储，求：A=A∪B。 算法思路：集合中的元素是无重复的，可将Lb表中 的元素从表尾起逐个删除，并在La表查找被删元素 b，若找不到，则将元素b插入La表，否则不必插入， 完成后集合B为空