作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。
最后更新：2023年9月12日
作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。
1. 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
算法提示：
1.搜索整个顺序表，查找最小值元素并记住其位置；
2.搜索结束后，用最后一个元素填补空出的最小值元素的位置。
bool DeleteMin(SqList &L, ElemType &e){
// 在此处填入代码
}
【参考代码】
bool DeleteMin(SqList &L, ElemType &e){
// 删除顺序表中的最小元素，并用引用参数e返回其值
// 若删除成功，则返回true；否则返回false
if (L.length == 0) // 1. 如果线性表为空，则返回Error
return false;
e = L.data[0]; // 2.1 初始化flag变量，使其等于线性表的第一个元素
int pos = 0; // 2.2 初始化位置变量，使其指向线性表的第一个元素怒
for (int i = 1; i < L.length; i++) // 3. 按元素依次扫描线性表
if (L.data[i] < e){ // 若当前元素值小于flag变量 e，则：
e = L.data[i]; // 3.1 将当前值复制给flag变量e
pos = i; // 3.2 更新位置变量pos为当前元素的位置
}
L.data[pos] = L.data[L.length - 1]; // 4. 使用最后一个元素填补空出的位置
L.length--; // 5. 表长减一
return true; // 6. 删除成功，返回true
}
2. 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
算法提示： 扫描顺序表L的前半部分元素，对于这部分的元素 L.data[i] (0 <= i < L.length/2)，使用后半部分的对应元素 L.data[L.length-1-i] 与之进行位置互换。
bool Reverse(SqList &L){
// 在此处填入代码
}
【参考代码】
void Reverse(SqList &L){
ElemTpye tmp; // 1. 定义中间变量，用于实现元素值互换
for (int i = 0; i < L.length/2; i++) // 2. 依次扫描顺序表前半部分的元素
tmp = L.data[i]; // 3. 以中位数为对称轴，将前后对应位置的元素进行互换
L.data[i] = L.data[L.length-1-i];
L.data[L.length-1-i] = tmp;
}
3. 从有序（递增）顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
算法提示：
1.在递增顺序表中，处于s与t之间的元素必然是连续的，所以只需要删除区间[s,t]之间的元素即可。
2.查找区间下限s的位置，即第一个大于等于s的元素的位置ps
3.查找区间上限t的位置，即第一个大于t的元素的前一个位置pt
4.删除ps和pt之间的元素，并将pt后面的元素整体往前移动到位置ps
bool Delete_s2t(SqList &L, ElemType s, ElemType t){
// 在此处填入代码
}
【参考代码】
bool Delete_s2t(SqList &L, ElemType s, ElemType t){
// 删除有序顺序表L中所有值在s与t之间的所有元素
int i j;
if (s > t || L.length==0) // 1. 判断[s,t]区间的合理性及顺序表是否为空
return false;
for (i = 0; i < L.length && L.data[i]<s; i++); // 2. 依次遍历顺序表，并查找第一个大于或等于s的元素
if(i >= L.length) // 2.1 若所有元素均小于s，则直接返回Error，否则i被作为s的flag保存
return false;
for (j = i; j < L.length && L.data[j]<=t; j++); // 3. 从j=i开始继续扫描顺序表，查找第一个大于t的元素，若找到则退出循环，j作为t的flag保存，若未找到，则将L.length的值复制给j，并作为t的flag保存
for (int k = j; k < L.length; k++) // 4. 从j开始，依次将位置为j,j+1,...的元素赋值到位置为i,i+1,..
L.data[i++] = L.data[k]; // 前移替换相当于从s开始删除元素，直到t结束
L.length = i; // 5. 更新表长到i的新位置，此处i的长度为 s+(n-t)+1
return true; // 6. 操作完毕，返回true
}
1. 从有序递增顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
算法提示：
1.在递增顺序表中，值相同的元素在逻辑上一定是连续的
2.初始时，将线性表的第一个元素定义非重复序列的flag元素
3.从第二个元素开始，依次判断当前元素与flag元素是否相同，若相同，则继续向后判断，若不同，则将当前元素插入到flag元素之后
4.依次扫描顺序表，直到表尾结束
bool DeleteDuplicate(SqList &L){
// 在此处填入代码
}
【参考代码】
bool DeleteDuplicate(SqList &L){
if (L.length == 0)
return false;
int i, j; // 1. 定义两个flag一个是非重复序列的尾元素i，另一个是检查元素指针j
for (i=0, j=1; j<L.length; j++) // 2. 逐元素扫描线性表
if (L.data[i] != L.data[j]) // 2.1 若检查元素j不等于flag元素
L.data[++i] = L.data[j]; // 则将检查元素j赋给flag元素，并将flag元素后移，否则继续向后扫描
L.length = i+1; // 3. 更新表长
return true;
}
2. 将两个有序递增顺序表合并为一个新的有序递增顺序表，并由函数返回结果顺序表。
算法提示：
1.本题的目标是将两个已知序列La和Lb合并到新顺序表Lc中，因此首先需要判断输入的线性表Lc的长度是否足够长，以满足La和Lb的输入
2.定义三个flag指针，分别指向La和Lb的第一个元素和新表Lc的第一个元素
3.从表头开始执行扫描，依次比较La和Lb的指针所指向的元素，将较小的一个插入到新表Lc中，同时将指向被移动元素的指针向后移动一位
4.当某个表线性表完成扫描后，将另外一个线性表中的元素依次插入到新表Lc中，直到表尾结束
bool MergeList(SqList La, SqList Lb, SqList &Lc){
// 在此处填入代码
}
【参考代码】
bool MergeList(SqList La, SqList Lb, SqList &Lc){
// 将有序顺序表La与Lb合并为一个新的有序顺序表Lc
if (La.Length + Lb.Length > Lc.MaxSize) // 1. 判断空表Lc的长度是否足够长，能够容纳La和Lb中的所有元素
return;
int i=0, j=0, k=0; // 2. 定义两个flag，一个是指向La的当前元素i，一个是指向Lb的当前元素j
while (i<La.Length && j<Lb.Length){ // 3. 当La,Lb均未到达相应的表尾时，则依次比较i,j所指向的元素，并将较小的一个插入到Lc之后
if (La.data[i] < Lb.data[j]) // 3.1 将i指向的值插入到Lc的末尾
Lc.data[k++] = La.data[i++];
else
Lc.data[k++] = Lb.data[j++]; // 3.2 将j指向的值插入到Lc的末尾
}
while (i<La.Length) // 4.1 若Lb先到达表尾，则依次将La剩余的元素插入到Lc的末尾
Lc.data[k++] = La.data[i++];
while (j<Lb.Length) // 4.2 若La先到达表尾，则依次将Lb剩余的元素插入到Lc的末尾
Lc.data[k++] = Lb.data[j++];
Lc.length = k;
return true;
}
3. 从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
算法提示：
1.依次扫描顺序表L，并使用k记录元素值在[s,t]之间的元素值的个数，默认k=0
2.对于当前扫描的元素，若其值不在[s,t]之间，则前移k个位置；否则执行k++
3.扫描结束后，将顺序表L的长度更新为L.length-k
4.每个元素只需要执行一次移动，因此算法复杂度为O(n)
bool Delete_s2tB(SqList &L, ElemType s, ElemType t){
// 在此处填入代码
}
【参考代码】
bool Delete_s2tB(SqList &L, ElemType s, ElemType t){
// 从顺序表L中删除其值在给定值s与t之间（包含s和t）的所有元素
int i, k = 0;
if (L.length == 0 || s>=t) // 1. 判断[s,t]区间的合理性及顺序表是否为空
return false;
for (i = 0; i < L.length; i++){ // 2. 依次扫描顺序表L
if (L.data[i] >= s && L.data[i] <= t) // 2.1 若当前元素不在[s,t]之间，则k++
k++;
else
L.data[i-k] = L.data[i]; // 2.2 若当前元素在[s,t]之间，则将当前元素前移k个位置
}
L.length -= k; // 2.3 更新线性表长度
return true;
}
4. 给定一个含 个整数的数组，请设计一个在时间上尽可能高效的算算法，找出数组中未出现的最小正整数。例如，数组 {-5, 3, 2, 3} 中未出现的最小正整数时 1；数组 {1, 2, 3} 中未出现的最小正整数时4。要求：
1). 给出算法的基本设计思想；
2). 根据设计思想，采用C或C++语言描述算法，并给出关键注释；
3). 说明你所设计算法的时间复杂度和空间复杂度。
算法提示：
1.要求在时间上尽可能高效，因此可以采用空间换时间的方法。
2.初始化一个全为零的数组B，其长度与原数组A相同。
3.检查数组A中的每一个元素，若存在正整数n，则将数组B[n-1]的值置为1。
4.待数组A中的每个元素都检查完后，遍历数组B。若能查找到以一个元素B[i]=0，则i+1即为目标最小正整数。
int FindMissMin(int A[], int n){
// 在此处填入代码
}
【参考代码】
int FindMissMin(int A[], int n){
int i, *B; // 标记一个新数组B
B = (int *)malloc(sizeof(int)*n); // 为新数组分配空间，其大小与原数组相同
memset (B, 0, sizeof(int)*n); // 初始化数组B，全部元素值为0
for (i=0; i<n; i++){ // 扫描原数组A
if (A[i] > 0 && A[i] <= n) // 判断A[i]是否在[1,n]之间，若成立，则将新数组B的对应位置置为1
B[A[i]-1] = 1;
for (i=0; i<n; i++) // 扫描新数组B，找到第一个值为0的下标i，并返回i+1即为结果
if (B[i] == 0)
break;
return i+1
}