1.1.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除的元素的值,空出的位置由最后一个元素填补,若顺序表为空则显示出错信息并退出运行 。
bool Del_Min(SqList &L, ElemType &value) {
if (L.length == NULL)
return false;
value = L.data[0]; //假设0号元素的值最小
int pos = 0;
for (int i = 1;i < L.length;i++) {
if (L.data[i] < value) {
value = L.data[i];
pos = i;
}
}
L.data[pos] = L.data[L.length - 1]; //空出的位置由最后一个元素填补
L.length--;
return true;
}
1.2.设计一个高效的算法,将顺序表的所有元素逆置,要求算法的空间复杂度为O(1)
算法思想:扫描顺序表L的前半部分元素,对于元素L.data[i],将其余后半部分对应元素L.data[L.length-i-1]进行交换。
void Reverse(SqList &L) {
ElemType temp;
for (int i = 0;i < L.length;i++) {
temp = L.data[i];
L.data[i] = L.data[L.length - i - 1];
L.data[L.length - i - 1] = temp;
}
}
1.3长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素
//解法一:用k标记不等于x的元素,将不等于x的元素向前放到k的位置上,修改L的长度
void del_x_1(SqList &L, ElemType x) {
int k = 0;
for (int i = 0;i < L.length;i++) {
if (L.data[i] != x) {
L.data[k] = L.data[i];
k++; //用k记录不等于x的元素的个数
}
}
L.length = k; //顺序表长度等于k
}
//解法二:用k记录顺序表中等于x的元素个数,边扫描边统计k,并将不等于k的元素向前移动k个位置。
void del_x_2(SqList &L, ElemType x) {
int k = 0;
for (int i = 0;i < L.length;i++) {
if (L.data[i] == x)
k++;
else
L.data[i - k] = L.data[i]; //当前元素前移k个位置
i++;
}
L.length = L.length - k; //顺序表长度递减
}
1.4. 从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素,如果s或t不合理或者顺序表为空则显示出错信息并退出运行
//先找出>=s的第一个元素,再找出>t的第一个元素,将后面元素前移
bool del_s_t2(SqList &L, ElemType s, ElemType t) {
int i, j;
if (i > L.length || s >= t)
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 + 1;
return true;
}