删除算法的时间性能分析 ◆与插入运算相同,其时间主要消耗在了移动表中元素上, 删除第个元素时,其后面的元素aan都要向上移动 个位置,共移动了n个元素,所以平均移动数据元素的次 数 e de ∑P 在等概率情况下,p1=1/n,则: E ∑P ∑ 2 ◆这说明顺序表上作删除运算时大约需要移动表中一半的元 素,显然该算法的时间复杂度为O(n)。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 11 删除算法的时间性能分析 与插入运算相同，其时间主要消耗在了移动表中元素上， 删除第i个元素时，其后面的元素 ai+1 ～an 都要向上移动一 个位置，共移动了 n-i 个元素，所以平均移动数据元素的次 数： 在等概率情况下，pi =1/ n，则： 这说明顺序表上作删除运算时大约需要移动表中一半的元 素，显然该算法的时间复杂度为Ｏ(n)。 = = − n i de i p n i 1 E ( ) + = = − == − = − = 1 1 1 2 1 ( ) 1 E ( ) n i n i de i n n i n p n i
4按值查找 线性表中的按值查找是指在线性表中查找与给定值x相等 的数据元素。算法如下: int Location_SeqList(SeqList L, datatype x) t int i=0; while(<=Llast & L->datal!=X) ++ if (iL->last) return-1; else return /*返回的是存储位置* ◆本算法的主要运算是比较。显然比较的次数与ⅹ在表中 的位置有关,也与表长有关。平均比较次数为(n+1)/2, 时间性能为O(n) 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 12 ⒋按值查找 线性表中的按值查找是指在线性表中查找与给定值x相等 的数据元素。算法如下： int Location_SeqList(SeqList *L, datatype x) { int i=0; while(i<=L.last && L->data[i]!= x) i++; if (i>L->last) return -1; else return i; /*返回的是存储位置*/ } 本算法的主要运算是比较。显然比较的次数与x在表中 的位置有关，也与表长有关。平均比较次数为（n+1）/2， 时间性能为O(n)
2.2.3顺序表应用举例 例21将顺序表(a,a2…,an)重新排列为以a1为 界的两部分:a1前面的值均比a1小,a1后面的值都 比a1大。 ◆划分的方法有多种,下面介绍的划分算法其思路简单, 性能较差。基本思路: 从第二个元素开始到最后一个元素,逐一向后扫描: (1)当前数据元素a比a1大时,表明它已经在a1 的后面,不必改变它与a1之间的位置,继续比较下一 个 (2)当前结点若比a1小,说明它应该在a1的前面, 此时将它上面的元素都依次向下移动一个位置,然后 将它置入最上方。 2021年1月21日 数据结构讲义 13
2021年1月21日 数据结构讲义 13 2.2.3 顺序表应用举例 例2.1 将顺序表 (a1，a2，... ，an ) 重新排列为以 a1 为 界的两部分：a1 前面的值均比 a1 小，a1 后面的值都 比 a1 大。 划分的方法有多种，下面介绍的划分算法其思路简单， 性能较差。 基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： ⑴当前数据元素 aI 比 a1 大时，表明它已经在 a1 的后面，不必改变它与 a1 之间的位置，继续比较下一 个。 ⑵当前结点若比 a1 小，说明它应该在 a1 的前面， 此时将它上面的元素都依次向下移动一个位置，然后 将它置入最上方
算法如下: void part( Seqlist料) t int i,j; datatype x,: X=L->data[o] /*将基准置入X中* (i=1;i<=L->kast;i++) if(L->datai<X /*当前元素小于基准* dy=L->datal] forGj=i-1;j>=0jj 移动* >data[j+1]=L->datalj L->data[0]=y;y ◆总的移动次数为: 1+2) ∑ (+1) H*( 2 ◆即最坏情况下移动数据时间性能为O(n2)。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 14 算法如下： void part(SeqList *L) { int i,j; datatype x,y; x=L->data[0]; /* 将基准置入 x 中*/ for (i=1; i<=L->last; i++) if (L->data[i]<x) /*当前元素小于基准*/ { y = L->data[i]; for(j=i-1;j>=0;j--) /*移动*/ L－>data[j+1]=L->data[j]; L->data[0]=y; } } 总的移动次数为 ： 即最坏情况下移动数据时间性能为Ｏ(ｎ２)。 2 * ( 3 ) ( 1 2 ) ( 1) 2 2 + − + = + = = = n n i i n i n i
例22有顺序表A和B,其元素均按从小到大的升序排列, 编写一个算法将它们合并成一个顺序表C,要求C的元素 也是从小到大的升序排列 ◆算法思路:依次扫描通过A和B的元素,比较当前的元 素的值,将较小值的元素赋给C,如此直到一个线性表 扫描完毕,然后将未完的那个顺序表中余下部分赋给C 即可。C的容量要能够容纳A、B两个线性表相加的长度 2021年1月21日 数据结构讲义 15
2021年1月21日 数据结构讲义 15 例2.2 有顺序表A和B，其元素均按从小到大的升序排列， 编写一个算法将它们合并成一个顺序表C，要求C的元素 也是从小到大的升序排列。 算法思路：依次扫描通过A和B的元素，比较当前的元 素的值，将较小值的元素赋给C，如此直到一个线性表 扫描完毕，然后将未完的那个顺序表中余下部分赋给C 即可。C的容量要能够容纳A、B两个线性表相加的长度