【王道数据结构-第二章-线性表算法题】

1.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

#include <iostream>
#define MAXSIZE 5
typedef struct {int data[MAXSIZE];int length;
} SeqList;/**
* 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
* 解析:记录最小值和最小值位置然后进行置换就行*/
bool deleteMinElement(SeqList &seqList, int &value) {if (seqList.length == 0) {return false;}int pos = 0;int minValue = seqList.data[0];for (int i = 1; i < seqList.length; i++) {if (seqList.data[i] < minValue) {minValue = seqList.data[i];pos = i;}}seqList.data[pos] = seqList.data[seqList.length - 1];value=minValue;seqList.length--;return true;
}int main() {SeqList seqList;seqList.length = 5;srand((unsigned) time(NULL));for (int i = 0; i < seqList.length; i++) {seqList.data[i] = rand() % 100;printf("%d ", seqList.data[i]);}int value=0;//输出最小值if (deleteMinElement(seqList, value)) {printf("\n");for (int i = 0; i < seqList.length; i++) {printf("%d ", seqList.data[i]);}printf("\n");printf("最小值:%d", value);} else {printf("没有最小值\n");}return 0;
}

2. 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

#include <iostream>
#define MAXSIZE 5
typedef struct {int data[MAXSIZE];int length;
} SeqList;
/*** 计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。* 解析:就是对调元素位置*/
void invert(SeqList &seqList) {for (int i = 0; i < seqList.length / 2; i++) {int temp = seqList.data[i];seqList.data[i] = seqList.data[seqList.length - 1 - i];seqList.data[seqList.length - 1 - i] = temp;}
}int main() {SeqList seqList;seqList.length = 5;srand((unsigned) time(NULL));for (int i = 0; i < seqList.length; i++) {seqList.data[i] = rand() % 100;printf("%d ", seqList.data[i]);}invert(seqList);printf("\n");for (int i = 0; i < seqList.length; i++) {printf("%d ", seqList.data[i]);}return 0;
}

3. 对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为 O(1)的算法，该算法删除顺序表中所有值为x的数据元素。

#include <iostream>
#define MAXSIZE 5
typedef struct {int data[MAXSIZE];int length;
} SeqList;
/**
* 对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为 O(1)的算法，该算法删除顺序表中所有值为x的数据元素。
* 解析:相当于再来一个标记位，从头开始重新赋值不是x的元素到列表中*/
void deleteX(SeqList &seqList, int x) {int k = 0;for (int i = 0; i < seqList.length; i++) {if (seqList.data[i] != x) {seqList.data[k++] = seqList.data[i];}}seqList.length = k;
}/*** * @param seqList * @param x* 解析: 每次移动都记录k的个数，到下一个不是k元素时向前移动k个元素*/
void deleteX2(SeqList &seqList, int x) {int k = 0, i = 0;;while (i < seqList.length) {if (seqList.data[i] == x) {k++;} else {//当前元素不是x,将当前元素移动k个元素的距离seqList.data[i - k] = seqList.data[i];}i++;}seqList.length -= k;
}
int main() {SeqList seqList;seqList.length = 5;srand((unsigned) time(NULL));for (int i = 0; i < seqList.length; i++) {seqList.data[i] = rand() % 10;printf("%d ", seqList.data[i]);}deleteX(seqList, 5);printf("\n");for (int i = 0; i < seqList.length; i++) {printf("%d ", seqList.data[i]);}return 0;
}

4. 从顺序表中删除其值在给定值s和t之间(包含s和t,要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

#include <iostream>
#define MAXSIZE 5typedef struct {int data[MAXSIZE];int length;
} SeqList;
/**
* 从顺序表中删除其值在给定值s和t之间(包含s和t,要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
* 解析:与第3题类似，用k做标记为从头开始扫，仅把不需要删除的赋值到列表中*/
bool deleteRange(SeqList &seqList, int s, int t) {if (s >= t || seqList.length == 0) {return false;}int k = 0;for (int i = 0; i < seqList.length; i++) {if (seqList.data[i] < s || seqList.data[i] > t) {seqList.data[k++] = seqList.data[i];}}seqList.length = k;return true;
}/**** @param seqList* @param s* @param t* 解析:记录删除的个数，从第一个开始扫，遇到需要删除的元素，记录个数，否则赋值到列表中*/
bool deleteRange2(SeqList &seqList, int s, int t) {int k = 0, i = 0;if (s >= t || seqList.length == 0) {return false;}for (int i = 0; i < seqList.length; i++) {if (seqList.data[i] >= s && seqList.data[i] <= t) {k++;} else {seqList.data[i - k] = seqList.data[i];}}seqList.length -= k;return true;
}int main() {SeqList seqList;seqList.length = 5;srand((unsigned) time(NULL));for (int i = 0; i < seqList.length; i++) {seqList.data[i] = rand() % 10;printf("%d ", seqList.data[i]);}deleteRange(seqList, 2, 5);printf("\n");for (int i = 0; i < seqList.length; i++) {printf("%d ", seqList.data[i]);}return 0;
}

5. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

#include <iostream>
#define MAXSIZE 50typedef struct {int data[MAXSIZE];int length;
} SeqList;/*** 5.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。* 解析:题目说有序的，所以用两个指针，一个指向当前元素，一个指向下一个元素，如果当前元素和下一个元素相等，则删除下一个元素，否则当前元素向后移动* 与第3题类似，用k做标记为从头开始扫，仅把不需要删除的赋值到列表中* 其次注意这里要先++,也就是++k因为我们默认第一个元素就是不重复列表的第一个所以遇到下一个要从第二个开始放置，所以是++k*/
bool deleteRepeat(SeqList &seqList) {if (seqList.length == 0) {return false;}int k=0;for (int i=1; i < seqList.length; i++) {if (seqList.data[k] != seqList.data[i]) {seqList.data[++k] = seqList.data[i];}}seqList.length = k + 1;return true;
}int main() {SeqList seqList={1, 1, 1, 2, 2, 3, 3, 3, 4, 4};seqList.length = 10;deleteRepeat(seqList);printf("\n");for (int i = 0; i < seqList.length; i++) {printf("%d ", seqList.data[i]);}return 0;
}