考研王道数据结构-顺序表（综合应用2）
本节代码主要来自王道单科18页的综合应用题。
四、从有序顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素。如果s与t不合理或者顺序表为空则显示出错信息并退出运行
找到第一个比s大的元素的位置。（和下面那道题的区别就是是否有序）
核心代码：
bool DeleteElemBetweenST(Sqlist &L,int s,int t){ if(L.length==0||t<=s)return false; int i=0,j; while(i<=L.length-1&&L.data[i]<s)i++; //找到第一个>=s的位置 ，即为i if(i>L.length-1)return false; j=i; while(j<=L.length-1&&L.data[j]<=t)j++; //找到第一个>t的位置 ，即为j //也可以用for循环 for(j=i;j<=L.length-1&&L.data[j]<=t;j++); int count=j-i; for(int k=j;k<=L.length-1;k++){ L.data[k-count]=L.data[k]; } L.length-=count; }
也可以不用count统计个数，不用新定义k来遍历。
for(;j<=L.length-1;j++){
L.data[i]=L.data[j];
}
L.length=i+1;
五、从顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素。如果s与t不合理或者顺序表为空则显示出错信息并退出运行
找到第一个比s大的元素的位置。
这道题一看就和第三道题差不多。
核心代码：
bool DeleteElemBetweenST2(Sqlist &L,int s,int t){ if(L.length==0||t<=s)return false; int count=0; for(int i=0;i<L.length;i++){ if(L.data[i]>=s&&L.data[i]<=t) count++; else L.data[i-count]=L.data[i]; } L.length-=count; return true; }
六、从有序顺序表中删除所有其值重复的元素，使表中所有的值均不同。
我的做法：从上面删除值为x的元素得到启示，用count来指代所要删除元素的个数。不符合要求时运行L.data[i-count]=L.data[i]。
当元素与后一个元素相同时，说明存在相同元素，count++。
第一种：（与书上的做法不同）
bool DeleteSameElem1(Sqlist &L){ if(L.length==0)return false; int count=0; for(int i=0;i<=L.length-1;i++){ if(L.data[i]==L.data[i+1]){ count++; } else{ L.data[i-count]=L.data[i]; } } L.length-=count; return true; }
第二种：与书上的做法基本可以说一样，只是变量不同而已
bool DeleteSameElem2(Sqlist &L){ if(L.length==0)return false; int count=0; for(int i=0;i<L.length-1;i++){ if(L.data[i]!=L.data[i+1]){ L.data[++count]=L.data[i+1]; //注意覆盖位置要从L.data[1]开始，否则第一个元素会被覆盖掉。 //而且覆盖的元素应该来自后一个。否则最后面的元素会与倒数第二个一样。 } } L.length=count+1; //注意count会被少算一次，因为假设不相同的元素有5个，但它比较的次数只有4 个 return true; }
第三种：即书上的做法
bool DeleteSameElem3(Sqlist &L){ if(L.length==0)return false; int i,j; for(i=0,j=1;j<L.length;j++){ if(L.data[i]!=L.data[j]){ L.data[++i]=L.data[j]; } } L.length=i+1; return true; }
思维扩展：如果把只要存在相同元素的就全部删除，如2 2 3 3 4 5删除以后为4 5。
bool DeleteSameElem1(Sqlist &L){ if(L.length==0)return false; int count=0; ElemType x; for(int i=0;i<=L.length-1;i++){ if(L.data[i]==L.data[i+1]){ x=L.data[i]; count++; } else if(L.data[i]==x)count++; else{ L.data[i-count]=L.data[i]; } } L.length-=count; return true; }
以下是以上三道题的全部测试代码（可直接运行）：
#include<stdio.h> #define true 1 #define false 0 #define MaxSize 100 //定义线性表的最大长度 #define ElemType int #define Status int typedef struct{ ElemType data[MaxSize]; //动态分配数组的指针 int length; //当前个数 }Sqlist; //构造一个空的线性表L void InitList(Sqlist &L){ L.length=0; } bool ListInsert(Sqlist &L,int i,ElemType e){ //将元素e插到顺序表L中第i个位置 if(i<1||i>L.length+1) return false; if(L.length>=MaxSize) return false; for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length++; return true; } void ListLoad(Sqlist L){ if(L.length==0){ printf("当前顺序表为空\n"); return; } printf("当前顺序表元素为："); for(int i=0;i<L.length;i++) printf("%d ",L.data[i]); printf("\n"); return; } bool DeleteElemBetweenST1(Sqlist &L,int s,int t){ if(L.length==0||t<=s)return false; int i=0,j; while(i<=L.length-1&&L.data[i]<s)i++; //找到第一个>=s的位置 ，即为i if(i>L.length-1)return false; j=i; while(j<=L.length-1&&L.data[j]<=t)j++; //找到第一个>t的位置 ，即为j //也可以用for循环 for(j=i;j<=L.length-1&&L.data[j]<=t;j++); int count=j-i; for(int k=j;k<=L.length-1;k++){ L.data[k-count]=L.data[k]; } L.length-=count; //也可以不用count统计个数。 // for(;j<=L.length-1;j++){ // L.data[i]=L.data[j]; // } // L.length=i+1; } bool DeleteElemBetweenST2(Sqlist &L,int s,int t){ if(L.length==0||t<=s)return false; int count=0;//计算元素等于x的个数 for(int i=0;i<L.length;i++){ if(L.data[i]>=s&&L.data[i]<=t) count++; else L.data[i-count]=L.data[i]; } L.length-=count; return true; } //我的做法：从上面删除值为x的元素得到启示，用count来指代所要删除元素的个数。不符合要求时运行L.data[i-count]=L.data[i]。 //当元素与后一个元素相同时，说明存在相同元素，count++,并先记录这个元素，便于统计最后一个与后面的值不相同的元素。 bool DeleteSameElem1(Sqlist &L){ if(L.length==0)return false; int count=0; ElemType x; for(int i=0;i<=L.length-1;i++){ if(L.data[i]==L.data[i+1]){ x=L.data[i]; count++; } else if(L.data[i]==x)count++; else{ L.data[i-count]=L.data[i]; } } L.length-=count; return true; } bool DeleteSameElem2(Sqlist &L){ if(L.length==0)return false; int count=0; for(int i=0;i<L.length-1;i++){ if(L.data[i]!=L.data[i+1]){ L.data[++count]=L.data[i+1]; //注意覆盖位置要从L.data[1]开始，否则第一个元素会被覆盖掉。 //而且覆盖的元素应该来自后一个。否则最后面的元素会与倒数第二个一样。 } } L.length=count+1; //注意count会被少算一次，因为假设不相同的元素有5个，但它比较的次数只有4 个 return true; } bool DeleteSameElem3(Sqlist &L){ if(L.length==0)return false; int i,j; for(i=0,j=1;j<L.length;j++){ if(L.data[i]!=L.data[j]){ L.data[++i]=L.data[j]; } } L.length=i+1; return true; } int main(){ Sqlist T; ElemType e,s,t; int a,i; InitList(T); ListInsert(T,1,5); ListInsert(T,1,5); ListInsert(T,1,5); ListInsert(T,1,4); ListInsert(T,1,4); ListInsert(T,1,4); ListInsert(T,1,2); ListInsert(T,1,1); ListInsert(T,1,1); ListLoad(T); while(1){ printf("1:删除值在s与t之间的元素(有序)\n"); //DeleteElemBetweenST1 printf("2:删除值在s与t之间的元素(无序)\n"); //DeleteElemBetweenST2 printf("3:删除所有的相同元素(方法1)\n"); //DeleteSameElem1 printf("4:删除所有的相同元素(方法2)\n"); //DeleteSameElem2 printf("5:删除所有的相同元素(方法3)\n"); //DeleteSameElem3 printf("请选择:"); scanf("%d",&a); switch(a){ case 1:scanf("%d %d",&s,&t); if(DeleteElemBetweenST1(T,s,t))printf("删除成功\n"); else printf("删除失败\n"); break; case 2:scanf("%d %d",&s,&t); if(DeleteElemBetweenST2(T,s,t))printf("删除成功\n"); else printf("删除失败\n"); break; case 3:if(DeleteSameElem1(T)) printf("删除成功\n"); else printf("删除失败\n"); break; case 4:if(DeleteSameElem2(T)) printf("删除成功\n"); else printf("删除失败\n"); break; case 5:if(DeleteSameElem3(T)) printf("删除成功\n"); else printf("删除失败\n"); break; default:return 1; } ListLoad(T); } }
删除值在s与t之间的元素(有序)：
删除值在s与t之间的元素(无序)：
删除所有的相同元素（方法1）：
删除所有的相同元素（方法2）：
删除所有的相同元素（方法3）：
版权声明：本文为double891原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。