顺序表

顺序表删除最小元素 从顺序表中删除具有最小值的元素（假设唯一），并由函数返回被删除元素的值。 删除后空出的位置由最后一个元素填补， 若顺序表为空则显示错误信息并退出运行。 preset.h12345678910111213141516171819202122232425#ifndef _PRESET_H#define _PRESET_H#include <iostream>using namespace std;#define MAXLENGTH 50typedef struct { int elem[MAXLENGTH]; int length;} SqList;void print(SqList sql) { if (sql.length == 0) { cout << "null" << endl; return; } for (int i = 0; i < sql.length; ++i) { cout << sql.elem[i] << " "; } cout << endl;}#endif 参考代码123456789101112131415161718192021222324252627282930313233343536#include "preset.h"//删除最小的元素bool listDelete(SqList &sql, int &e) { if (sql.length == 0) return false; int index = 0; int min = sql.elem[0]; for (int i = 1; i < sql.length; ++i) { if (sql.elem[i] < min) { min = sql.elem[i]; index = i; } ...

顺序表子表右移 2010 将n个整数存放到一维数组R中，设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置。 顺序序列中的元素 循环左移p个位置 将一维数组R中保存的序列 循环左移p个位置（要求在时间和空间两方面 都尽可能高效的算法） 即将R中的数据(X0, X1, X2… Xn-1)变换为(Xp, Xp+1, Xp+2…Xp-1) 12345678910111213141516171819202122232425262728293031323334#include "preset.h"//顺序序列中的元素 循环左移p个位置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 p) { cout << "Reverse all: " << endl; listReverse(sql, 0, sql.length - 1); print(sql); cout << "Reverse the first " << p << " elements:" << endl; listReverse(sql, 0, p - 1); print(sql); cout << "Reverse the last " << sql.length - p << " ...

有序顺序表合并求中位数 2011 寻找序列A和B的中位数 一个长度为L的升序序列S，处于第[L/2]个位置的数称为S序列的中位数。 现有两个等长的升序序列A和B，试设计一个在时间和空间复杂度都尽可能高效的算法，找出两个序列A和B的中位数，要求： 12345678910111213141516171819202122232425262728293031323334#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 main() { SqList a = {{11, 13, 15, 17, 19}, 5}; print(a); SqList ...

寻找主元素 2013 已知一个整数序列A=(a0, a1,… an-1)其中0 ≤ ai ≤ n，若存在ap1=ap2= … =apm=x且 m > n/2则称x为A的主元素。 假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法找出A的主元素（存在输出该元素否则输出-1）。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include "preset.h"#include <map>//主元素抵消思路bool half(SqList sql, int &res) { int temp = sql.elem[0]; int count = 1; for (int i = 1; i < sql.length; ++i) { if (sql.elem[i] == temp) count++; else { if (count > 0) { count--; } else { temp = sql.elem[i]; count = 1; } } } int k = 0; for (int i = 0; i < sql.length; ++i) { if (sql.elem[i] == temp) ++k; } if (k > (sql.length / 2)) { res = temp; return true; } return false;}//哈希map思路bool hashmapp(SqList sql ...

寻找最小正整数 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" < ...