本算法的主要时间花在元素移动上,元素移动的次数也与 表长n和删除元素的位置有关,共有n个位置可以删除元素:当 i=n时,移动次数为0;当=1时,移动次数为n-1。假设表示删 除第个个位置上元素的概率,则=1,所以在长度为n的线性表 中删除一个元素时所需移动元素的平均次数为: P(n-1) n(n-1)_n P2(n-)
本算法的主要时间花在元素移动上，元素移动的次数也与 表长n和删除元素的位置i有关，共有n个位置可以删除元素：当 i=n时，移动次数为0；当i=1时，移动次数为n-1。假设pi表示删 除第i个位置上元素的概率，则pi=1/n，所以在长度为n的线性表 中删除一个元素时所需移动元素的平均次数为：
【例2.1】对于含有n个元素的顺序表L,设计一个算法 将其中所有元素逆置,并分析算法的时间复杂度和空间复杂 解:遍历L的前一半元素,对于每个元素 Ldata,将其 与后半部分的元素L.data|m-i-1交换即可。对应的算法如下: public void reverse(refsqlistClass d) int i: string tmp; for (i=0; i<L length/2; i++) i tmp=L datai; L data i=Ldata L.length-i-1i data L.length-i-1=tmp;
【例2.1】 对于含有n个元素的顺序表L，设计一个算法 将其中所有元素逆置，并分析算法的时间复杂度和空间复杂 度。 解：遍历L的前一半元素，对于每个元素L.data[i]，将其 与后半部分的元素L.data[n-i-1]交换即可。对应的算法如下： public void Reverse(refSqListClassL) { int i; string tmp; for (i=0;i<L.length/2;i++) { tmp=L.data[i]; L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=tmp; } }
该算法的一次执行结果如下图所示。 围例2.1 操作步骤1-建立顺序表 输入元素:123456,78,9 建立顺序表 例如输入:a,b,e,d 操作步骤2-产生两个顺序表 置顺序表 逆置后的顺序表:987654321 操作提示:成功逆置顺序表
该算法的一次执行结果如下图所示
【例22】对于含有n个元素的顺序表L,设计一个算法删除 其中第一个值为x的元素,并分析算法的时间复杂度和空间复杂 度。 解:遍历L的元素,若找到值为x的元素L. datai,将其后 面的元素均前移一个位置覆盖以 L datai,并返回true,若找不 到值为x的元素,则返回 false。对应的算法如下 public bool Delaelem(refsqlistClass L, string x) int i=0 while(i<Llength & string Compare(L datai], x)=0) I++ /查找元素x (i>=Llength) 未找到时返回fae return false: else {for(=ij< Llength:j++)将 datai+1之后的元素前移一个位置 data jl=L data lj+1] Llength 顺序表长度减1 return true; ∥功删除返回rue
【例2.2】 对于含有n个元素的顺序表L，设计一个算法删除 其中第一个值为x的元素，并分析算法的时间复杂度和空间复杂 度。 解：遍历L的元素，若找到值为x的元素L.data[i]，将其后 面的元素均前移一个位置覆盖以L.data[i]，并返回true，若找不 到值为x的元素，则返回false。对应的算法如下： public bool Delaelem(ref SqListClassL,string x) { int i=0,j; while (i<L.length && string.Compare(L.data[i],x)!=0) i++; //查找元素x if (i>=L.length) //未找到时返回false return false; else { for (j=i;j<L.length;j++) //将data[i+1]之后的元素前移一个位置 L.data[j]=L.data[j+1]; L.length--; //顺序表长度减1 return true; //成功删除返回true } }
【例23】若线性表中的数据元素相互之间可以比较,并且 数据元素在线性表中依元素值非递减或非递增増有序排列,即 a≥a1或≤1n1(i2,3,…,n),则称该线性表为有序表。若 个有序表采用顺序表存储,称为有序顺序表。假设两个递增 有序顺序表L1和L2,分别含有n和m个元素,设计一个算法将 它们的所有元素归并为一个递增有序顺序表L3。这一过程称为 有序表的二路归并。分析该算法的时间复杂度和空间复杂度
【例2.3】 若线性表中的数据元素相互之间可以比较，并且 数据元素在线性表中依元素值非递减或非递增有序排列，即 ai≥ai-1或ai≤ai-1（i=2，3，…，n），则称该线性表为有序表。若 一个有序表采用顺序表存储，称为有序顺序表。假设两个递增 有序顺序表L1和L2，分别含有n和m个元素，设计一个算法将 它们的所有元素归并为一个递增有序顺序表L3。这一过程称为 有序表的二路归并。分析该算法的时间复杂度和空间复杂度