1.搜索顺序表,查找最小值元素,用最后的元素代替它
思路:先找到最小值,再替换
bool DelMin(sqlList &L,Elemtype &value){
if(L.length == 0)return false;
int min = L.data[0];
int index = 0;
for(int i=1; i<L.length; i++){
if(L.data[i] < min){
min = L.data[i];
index = i;
}
}
L.data[index] = L.data[L.length-1];
L.length--;
return true;
}
2.顺训表逆序
思路:二分法前后调换
void Rever(sqlList &L){
int i=0;
int j=L.length-1;
for(int i=0; i<L.length/2; i++){
int t = L.data[i];
L.data[i] = L.data[j];
L.data[j] = t;
}
}
3.删除顺序表中所有特定值的元素
要求:时间复杂O(n),空间复杂O(1)
思路:在原数组上操作
void DelX(sqlList &L,int x){
int k=0;
for(int i=0; i<L.length; i++){
if(L.data[i] != x){
L.data[k] = L.data[i]; //相当于数组值存储除了x以为的数字,忽略x
k++; //新的长度递增
}
L.length = k;
}
}
4.删除有序表在s、t之间的所有数值,s<t
思路:找到两百边的边界,然后前移
voide Del_S_T(sqlList &L,int s,int t){
if(s>=t || L.length==0)return false;
int i,j;
for(int i=0; i<L.length && L.data<s; i++){ //找到第一个大于等于S的值
if(i > L.length)return false;
}
for(int j=0; j<L.length && L.data<=t; j++){ //找到第一个大于t的值
if(j > L.length)return false;
}
for(; j<L.length; j++,i++){
L.data[i] = L.data[j]; //将s到t的数值进行覆盖(前移)
}
L.length = i; //当前i的值就是数组的长度
}
5.在顺序表中删除给定值s到t之间左右元素
思路和第四题类似,但是注意这个没有说有序哦!
voide Del_S_T(sqlList &L,int s,int t){
int k=0; //用于记录s到t中的元素的个数
for(int 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个位置
}
L.length -= k; //除去s-t之间的元素,就是删除后的数组长度
}
}
6.删除有序表中重复元素。
维护不重复序列,将不重复的数字查到序列后方
voide Del_S_T(sqlList &L,int s,int t){
for(int 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;
}
}
7.合并两个表
思路:谁小先存谁
sqlList Del_S_T(sqlList a,sqlList b,sqlList &c){
int i=0,j=0,k=0; //分别为a b c当前的下表
while(i<a.length && j<b.length){
if(a.data[i] <= b.data[j]){
c.data[k++] = a.data[i++]; //谁小谁先来
}else{
c.data[k++] = b.data[j++];
}
}
while(i < a.length){
c.data[k++] = a.data[i++];
}
while(j < b.length){
c.data[k++] = b.data[j++];
}
c.length = k;
return c;
}