C语言从有序顺序表中删除其值在给定值s与t之间的所有元素
这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识,请查看:数据结构 -> 线性表
从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素,如果s或t 不合理或者顺序表为空则显示出错信息并退出运行。
问题2):
从顺序表中删除其值在给定值s与t之间(包含s和t,要求s<t)的所有元素,如果 s或t不合理或者顺序表为空则显示出错信息并退出运行。
问题1):
算法思想:先寻找值大于等于s的第一个元素(第一个删除的元素),然后寻找值>t 的第一个元素(最后一个删除的元素的下一个元素),要将这段元素删除,则只需直接将后面的元素前移即可。
问题2):
算法思想:从前向后扫描顺序表L,用k记录下元素值在s到t之间元素的个数(初始时k=0)。对于当前扫描的元素,若其值不在s到t之间,则前移k个位置;否则,删除该元素,并执行k++。由于这样每个不在s到t之间的元素仅移动一次,所以算法效率高。
本题代码如下:
问题描述:
问题1):从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素,如果s或t 不合理或者顺序表为空则显示出错信息并退出运行。
问题2):
从顺序表中删除其值在给定值s与t之间(包含s和t,要求s<t)的所有元素,如果 s或t不合理或者顺序表为空则显示出错信息并退出运行。
问题解答:
注意,因为是有序表,所以删除的元素必然是相连的整体。问题1):
算法思想:先寻找值大于等于s的第一个元素(第一个删除的元素),然后寻找值>t 的第一个元素(最后一个删除的元素的下一个元素),要将这段元素删除,则只需直接将后面的元素前移即可。
bool Del_s_t2(sqList &L, ElemType s, ElemType t){ //删除有序顺序表L中值在给定值s与t之间的所有元素 int i,j; if(s>=t) || L.length==0) return false; for (i=0; i<L.length && L.data[i] <s; i++) ; //寻找值>=s 的第一个元素 if(i>=L.length) return false; //所有元素值均小于s,则返回 for(j=i; j<L.length && L.data[j] <=t; j++) ; //寻找值>t 的第一个元素 for(;j<L.length;i++, j++) L.data[i]=L.data[j]; //前移,填补被删元素位置 L.length=i; return true; }
问题2):
算法思想:从前向后扫描顺序表L,用k记录下元素值在s到t之间元素的个数(初始时k=0)。对于当前扫描的元素,若其值不在s到t之间,则前移k个位置;否则,删除该元素,并执行k++。由于这样每个不在s到t之间的元素仅移动一次,所以算法效率高。
本题代码如下:
bool Del_s_t (sqList &Lf ElemType s, ElemType t) { //删除顺序表L中值在给定值s与t之间(要求s<t)的所有元素 int i,k=0; if (L.length==0 || s>=t) return false; //线性表为空或s、t不合法,返回 for(i=0;i<L.length;i++){ if (L.data[i] >= s && L.data[i] <= t) k++; else L.data [i-k] = L.data[i]; //当前元素前移 k 个置 } //for L.length-=k; // 长度减小 return true; }注意:本题也可以从后向前扫描顺序表,每遇到一个值在S到t之间的元素,则删除该元素,其后的所有元素全部前移。但移动次数远大于前者,效率不够高。