Download presentation
Presentation is loading. Please wait.
1
顺序表的删除
2
线性表的将长度为n的线性表 (a1,…,ai-1 ,ai,ai+1…,an) 变成长度为n-1的线性表 (a1,…,ai-1 , ai+1…,an)
顺序表的删除 数据元素ai-1、ai和ai+1之间的逻辑关系发生了变化。为了在存储结构上反映这种变化，同样需要移动元素。
3
数据元素 数据元素 序号 序号 1 12 2 13 3 21 4 24 5 28 6 30 7 42 8 77 1 12 2 13 3 21 4 5 6 7 顺序表的删除 插入24 28 30 42 77
4
一般情况下，删除第i(1<=i<=n)个元素时需将第n至第i+1个元素依次向前移动一个位置，共需要移动n-i个元素。 当删除第一个元素时，需要移动n-1个元素，当删除第n个元素时，需要移动0个元素。 所以，在删除任何位置元素都是等概率的前提下，顺序表中删除一个元素平均需要移动(n-1)/2个元素。 顺序表的删除
5
算法思想如下所示： (1)判断删除位置i是否合法； (2)将欲删除的元素保留在e中； (3)将第i+1至第n个的元素依次向前移动一个位置。 (4)表长减1。
删除一个新的元素
6
Status ListDelete_Sq(SqList &L,int i,ElemType &e){ if((i<1)||(i>L.length)) return ERROR; //i值不合法 e=L.elem[i-1]; //将欲删除的元素保留在e中 for (j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移 --L.length; //表长减1 return OK; } 参考算法代码 该算法的时间复杂度为O(n)。
![Status ListDelete_Sq(SqList &L,int i,ElemType &e){ if((i<1)||(i>L.length)) return ERROR; //i值不合法 e=L.elem[i-1]; //将欲删除的元素保留在e中 for (j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移 --L.length; //表长减1 return OK; }](http://slidesplayer.com/slide/16383724/95/images/6/Status+ListDelete_Sq%28SqList+%26L%2Cint+i%2CElemType+%26e%29%7B+if%28%28i%3C1%29%7C%7C%28i%3EL.length%29%29+return+ERROR%3B+%2F%2Fi%E5%80%BC%E4%B8%8D%E5%90%88%E6%B3%95+e%3DL.elem%5Bi-1%5D%3B+%2F%2F%E5%B0%86%E6%AC%B2%E5%88%A0%E9%99%A4%E7%9A%84%E5%85%83%E7%B4%A0%E4%BF%9D%E7%95%99%E5%9C%A8e%E4%B8%AD+for+%28j%3Di%3Bj%3C%3DL.length-1%3Bj%2B%2B%29+L.elem%5Bj-1%5D%3DL.elem%5Bj%5D%3B+%2F%2F%E8%A2%AB%E5%88%A0%E9%99%A4%E5%85%83%E7%B4%A0%E4%B9%8B%E5%90%8E%E7%9A%84%E5%85%83%E7%B4%A0%E5%89%8D%E7%A7%BB+--L.length%3B+%2F%2F%E8%A1%A8%E9%95%BF%E5%87%8F1+return+OK%3B+%7D.jpg "参考算法代码. 该算法的时间复杂度为O(n)。")
Similar presentations
