[项目005] 顺序表的综合应用 显示答案 | 返回首页

作者：欧新宇（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){
    // 在此处填入代码
}

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

算法提示： 扫描顺序表L的前半部分元素，对于这部分的元素 L.data[i] (0 <= i < L.length/2)，使用后半部分的对应元素 L.data[L.length-1-i] 与之进行位置互换。

bool Reverse(SqList &L){
    // 在此处填入代码
}

‍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){
    // 在此处填入代码
}

【扩展练习】

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

算法提示：
1.在递增顺序表中，值相同的元素在逻辑上一定是连续的
2.初始时，将线性表的第一个元素定义非重复序列的flag元素
3.从第二个元素开始，依次判断当前元素与flag元素是否相同，若相同，则继续向后判断，若不同，则将当前元素插入到flag元素之后
4.依次扫描顺序表，直到表尾结束

bool DeleteDuplicate(SqList &L){
    // 在此处填入代码
}

‍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){
    // 在此处填入代码
}

‍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)

Delete_s2tB(SqList &L, ElemType s, ElemType t){
    // 在此处填入代码
}

‍4. 给定一个含 $n(n \geq 1)$ 个整数的数组，请设计一个在时间上尽可能高效的算算法，找出数组中未出现的最小正整数。例如，数组 {-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){
    // 在此处填入代码
}