数据结构

寻找最小正整数 2018 给定一个含n个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。 1.试解123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960//烂代码#include "preset.h"int listMax(SqList sql) { int res = sql.elem[0]; for (int i = 1; i < sql.length; ++i) { if (sql.elem[i] > res) { res = sql.elem[i]; } } return res;}int listMin(SqList sql) { int res = sql.elem[0]; for (int i = 1; i < sql.length; ++i) { if (sql.elem[i] < res) { res = sql.elem[i]; } } return res;}//listDelete删除指定元素void listDelete(SqList &sql, int x) { int k = 0; for (int i = 0; i < sql.length; ++i) { if (sql.elem[i] == x) { k++; } else { sql.elem[i - k] = sql.elem[i]; } } sql.length = sql.length - k;}int maxPositiveInt(SqList sql) { ...

寻找三元组的最小距离 2020 定义三元组(a,b,c)的距离为D=|a-b|+|b-c|+|c-a|，给定3个非空整数集合S1、S2、S3按照升序分别存储在3个数组中。 请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)中的最小距离。 1.枚举123456789101112131415161718192021222324252627282930313233343536373839404142/*给定3个非空整数集合S1、S2和S3、按照升序分别存储在3个数组中设计一个算法计算出 所有可能的三元组 中的最小距离*/#include "preset.h"#define Max 0x7fffffff//计算绝对值int cul(int a, int b, int c) { return abs(a - b) + abs(b - c) + abs(c - a);}//判定是否为最小值bool isMin(int a, int b, int c) { if (min(a, min(b, c)) == a) { return true; } return false;}int minTri(SqList a, SqList b, SqList c) { int i = 0, j = 0, k = 0; int ans = Max; while (i < a.length && j < b.length && k < c.length && ans >= 0) { int temp = cul(a.elem[i], b.elem[j], c.elem[k]); if (temp < ans) ans = temp; if (isMin(a.elem[i], b.elem[j], c.elem[k])) i++; else if (isMin(b.elem[i], a.elem[j], c.elem[k])) j++; else k++; ...

顺序表元素逆置 设计一个高效的算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。 记录起始下标的位置 记录结束下标的位置 起始下标与结束下标的元素互换 起始位置++，结束位置– 循环以上操作，直到起始位置>=结束位置 1234567891011121314151617181920212223//顺序表逆置：设计一个高效的算法 将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)#include "preset.h"void listReverse(SqList &sql) { int p = 0; int q = sql.length - 1; while (p < q) { int temp = sql.elem[p]; sql.elem[p] = sql.elem[q]; sql.elem[q] = temp; p++; q--; }}int main () { SqList sql = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 10}; cout << "Current SqList: "; print(sql); listReverse(sql); cout << "Reverse the SqList: "; print(sql); return 0;}

顺序表删除指定元素 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。 注意删除元素后，不要忘记需要将顺序表后方的元素前移。 1.思路设置一个变量k用于记录已经删除元素的个数，当遍历到后方的元素时，只需要将该元素向前移动k个位置即可。 2.参考代码12345678910111213141516171819202122#include "preset.h"//listDelete十分巧妙的操作技巧void listDelete(SqList &sql, int x) { int k = 0; for (int i = 0; i < sql.length; ++i) { if (sql.elem[i] == x) { k++; } else { sql.elem[i - k] = sql.elem[i]; } } sql.length = sql.length - k;}int main () { SqList sql = {{1, 7, 2, 1, 4, 1, 6, 5, 1, 9}, 10}; cout << "Current SqList: "; print(sql); listDelete(sql, 1); cout << "AfterDeletion : "; print(sql); return 0;}

有序顺序表的范围删除 从有序表中删除其值在给定值s与t之间的所有元素， 若s或t不合理或顺序表为空，则显示出错信息并退出运行。 1234567891011121314151617181920212223242526272829#include "preset.h"//listBatchDelete范围删除bool listBatchDelete(SqList &sql, int s, int t) { if (s > t || sql.length == 0 || t < sql.elem[0] || s > sql.elem[sql.length - 1]) { return false; } int p = 0, q = 0; while (sql.elem[p] < s) p++; cout << p; while (sql.elem[q] <= t && q <= sql.length - 1) q++; cout << q;//注意需要特判，for循环写法无需 while (q <= sql.length) { sql.elem[p] = sql.elem[q]; p++; q++; } sql.length = sql.length - (q - p); return true;}int main () { SqList sql = {{1, 2, 2, 3, 4, 5, 6, 6, 7, 9}, 10}; cout << "Current SqList: "; print(sql); int s, t; cin >> s >> t; if (listBatchDelete(sql, s, t)) cout << "batchDelete the SqList: "; print(sql); else cout ...

无序顺序表的范围删除 从无序顺序表中删除其值在给定值s到t之间的所有元素（包含s与t并要求s<t）， 若s或t不合理或顺序表为空，则显示出错信息并退出运行。 12345678910111213141516171819202122232425262728#include "preset.h"//listBatchDelete范围删除bool listBatchDelete(SqList &sql, int s, int t) { if (s > t || sql.length == 0 || t < sql.elem[0] || s > sql.elem[sql.length - 1]) { return false; } int k = 0; for (int i = 0; i < sql.length; ++i) { if (s <= sql.elem[i] && sql.elem[i] <= t) { k++; } else { sql.elem[i - k] = sql.elem[i]; } } sql.length = sql.length - k; return true;}int main () { SqList sql = {{1, 7, 2, 1, 4, 1, 6, 5, 1, 9}, 10}; cout << "Current SqList: "; print(sql); int s, t; cin >> s >> t; if (listBatchDelete(sql, s, t)) cout << "batchDelete the SqList: "; print(sql); else cout << "error" < ...

有序顺序表去重 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。 1.思路指针遇到不同的元素时开始操作，遇到相同的元素时不变化。i指针为不同元素的个数， 2.参考代码12345678910111213141516171819202122#include "preset.h"//listRedundantRemove冗余数据去除bool listRedundantRemove(SqList &sql) { int black = 0; for (int red = 1; red < sql.length; ++red) { if (sql.elem[red] != sql.elem[red - 1]) { sql.elem[black + 1] = sql.elem[red]; black++; } } sql.length = black + 1; return true;}int main () { SqList sql = {{1, 2, 2, 3, 4, 4, 4, 5, 5, 9}, 10}; cout << "Current SqList: "; print(sql); if (listRedundantRemove(sql)) cout << "Remove Redundant Elements in SqList: "; print(sql); else cout << "error" << endl; return 0;}

有序顺序表合并 将两个有序表合并为一个新的有序顺序表，并由函数返回结果顺序表。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263//[顺序表合并]将两个（有序）顺序表 合并为一个 新的（有序）顺序表，并由函数返回结果顺序表#include "preset.h"//顺序表合并（利用三个int类型指针i\j\k）bool merge(SqList a, SqList b, SqList &c) { if (c.length < a.length + b.length) return false; int i = 0, j = 0, k = 0; //逐个比较 将较小的插入顺序表c中 while (i < a.length && j < b.length) { if (a.elem[i] <= b.elem[j]) { c.elem[k] = a.elem[i]; i++; k++; } else { c.elem[k] = b.elem[j]; j++; k++; } } //剩余元素直接插入结果 while (i < a.length) { c.elem[k] = a.elem[i]; k++; i++; } while (j < b.length) { c.elem[k] = b.elem[j]; k++; j++; } //修改顺序表c的长度 c.length = a.length + b.length; return true;}//顺序表合并（利用三个int*类型指针pa\pb\pc）bool mergeList(SqList La, SqList Lb, SqList &Lc) &# ...

顺序表子表逆置 已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3…,am)和(b1,b2,b3…bn)，编写函数将数组中两个顺序表的位置互换。 顺序表 内部块序 更改 已知一个一维数组A[m+n]中依次存放着 两个线性表(a1,a2,a3…am)和(b1,b2,b3…bn) 编写一个函数将数组中两个顺序表的位置互换，即将(b1,b2,b3…bn)放在(a1,a2,a3…am)的前面 123456789101112131415161718192021222324252627282930313233#include "preset.h"//顺序表逆置void listReverse(SqList &sql, int left, int right) { //int p = 0; //int q = sql.length - 1; while (left < right) { int temp = sql.elem[left]; sql.elem[left] = sql.elem[right]; sql.elem[right] = temp; left++; right--; }}//逆置前n个元素、逆置后m个元素void test(SqList &sql, int n, int m) { cout << "Reverse all: " << endl; listReverse(sql, 0, sql.length - 1); print(sql); cout << "Reverse the first " << n << " elements:" << endl; listReverse(sql, 0, n - 1); print(sql); cout << "Reverse the last " << m << " elements:&quo ...

顺序表综合操作 线性表(a1,a2,a3…an)中的元素递增有序且按顺序存储与计算机内， 要求设计一个算法完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相互交换，若找不到则将其插入表中并使表中元素仍然递增有序 1.二分查找递归12345678910111213141516171819202122232425#include "preset.h"//有序顺序表查找（二分查找）递归写法int binSearch(SqList sql, int target, int low, int high) { if (low > high) return -1; int mid = (low + high) / 2; cout << "low : " << low << " high : " << high << " mid : " << mid << endl; if (target == sql.elem[mid]) { return mid; } else if (target < sql.elem[mid]) { high = mid - 1; binSearch(sql, target, low, high); } else { low = mid + 1; binSearch(sql, target, low, high); }}int main() { SqList sql = {{1, 3, 5, 7, 8, 10, 11}, 7}; cout << "current List:" << endl; print(sql); int target; cin >> target; cout << binSearch(sql, target, 0 ...