/* 顺序表 */ #include<iostream> //clang.diagnostic.enable using namespace std; #define MaxSize 50 #define InitSize 100 typedef struct{ ElemType data[MaxSize]; int length; }SqList; typedef struct{ ElemType *data; int MaxSize, length; }SeqList; InitList(&L); Length(L); LocateElem(L, e); GetElem(L, i); ListInsert(&L, i, e); ListDelete(&L, i, &e); //e 返回被删除元素的值 PrintList(L); Empty(L); DestroyList(&L); /* 1. 顺序表中删除最小元素（唯一），并由函数返回被删除的元素, 用最后一个元素代替被删除的元素 */ bool Min_Dele(SqList &L, int &value){ //删除顺序表L中的最小元素节点，并通过引用参数value返回其值 //表空返回false， 删除成功返回true if (L.length == 0) return false; value = L.data[0]; int pos = 0; //标记最小元素位置 for (int i = 0; i < L.length; i++) //遍历，找出最小值 if (L.data[i] < value){ value = L.data[i]; //更新value pos = i; //更新pos } L.data[pos] = L.data[L.length - 1]; //最后元素补上空出位置 L.length--; return true; } /* 2. 逆置顺序表，要求空间复杂度为 O(1) */ void Reverse(SqList &L){ for (int i = 0; i < L.length / 2, i++) swap(L.data[i], L.data[L.length - 1 - i]); //交换 } /* 3. 删除长度为 n 的线性表 L 中所有值为 x 的元素， 要求 O(n), S(1) */ void Dele_x(SqList &L, int x){ int k = 0; //记录不等于 x 元素的个数 for (int i = 0; i < L.length; i++) if (L.data[i] != x){ L.data[k] = L.data[i]; k++; } L.length = k; } /* 4. 删除有序顺序表中元素值在给定 s 与 t (s<t)之间的所有元素， s 或 t 不合理或顺序表为空， 则显示错误信息并返回 */ bool Dele_s_t(SeqList &L, int s, int t){ if (s >= t || L.length == 0) return false; int i, j; for (i = 0; i < L.length && L.data[i] < s; i++); //寻找 >= s 的第一个数 if (i >= L.length) return false; //所有元素均 < s 返回 for (j = i, j < L.length && L.data[j] <= t; j++); //寻找 > t 的第一个数 for ( ; j < L.length; j++) L.data[i++] = L.data[j]; //前移，填补被删除的数 L.length = i; return true; } /* 5. 删除顺序表中元素值在给定 s 与 t (s<t)之间的所有元素， s 或 t 不合理或顺序表为空， 则显示错误信息并返回 */ bool Dele_s_t(SqList &L, int s, int t){ int k = 0; //k 为元素值不在s，t之间元素的个数 if (s >= t || L.length == 0) return false; for (int i = 0; i < L.length; i++) if (L.data[i] < s || L.data[i] > t){ L.data[k] = L[i]; k++; } L.length = k; return true; } /* 6. 有序顺序表中删除所有值重复的元素 */ bool Dele_Same(SqList &L){ if (L.length == 0) return false; int k = 0; //记录不重复的元素值的元素的个数 for (int i = 0; i < L.length; i++){ L.data[k] = L.data[i]; k++; while(i+1 < L.length && L.data[i] == L.data[i+1]) i++; } L.length = k; return true; } /* 7. 将两个有序表合成一个新的有序表， 并返回该顺序表*/ bool Merge(SqList A, SqList B, SqList &L){ if (A.length + B.length > L.Maxsize) return false; //大于线性表的最大长度 int i = 0, j = 0, k = 0; while (i < A.length && j < B.length){ //循环，比较，较小的存入结果表 if (A.data[i] < B.data[j]) L.data[k++] = A.data[i++]; else L.data[k++] = B.data[j++]; } while (i < A.length) //将剩余的元素加入结果表 L.data[k++] = A.data[i++]; while (j < B.length) L.data[k++] = B.data[j++]; L.length = k; return false; } /* 8. 一维数组A[m+n]中依次存放两个线性表(a1, ... ,am )和(b1, ... ,bn)， 要求将数组中的两个线性表位置互换 */ void Reverse(int A[], int left, int right){ if (left >= right) return; int mid = (left + right) / 2; for (int i = 0; i < mid - left; i++) swap(a[left+i], a[right-i]); } void Exchange(int A[], int m, int n){ Reverse(A, 0, m+n-1); Reverse(A, 0, n-1); Reverse(A, n, m+n-1); } /* 9. 递增线性表，最少时间内从中查找出值为 x 的元素，然后将其与后继元素互换，如果找不到，就按序插入表中 */ void Search_Exchange_Insert(int A[], int x, int n){ // n 为线性表长度 int left = 0, right = n-1, mid; while(left <= right){ mid = (left + right) / 2; if (x < A[mid]) right = mid - 1; else left = mid + 1; } if (A[mid] == x && mid != n - 1) swap(A[mid], A[n-1]); if (left > right){ for (int i = n-1; i > right; i--) A[i+1] = A[i]; A[left] = x; } } /* 10. 将 R 一维数组中保存的序列循环左移 p 个位置 (A0, A1, ..., An) --> (Ap, ..., An, A0, ...,Ap-1)*/ /* 基本设计思想：（此题实际上就上第8题） 该问题可视为将数组 ab 转成 ba，先将 ab 整体逆置为b-1 a-1,然后再分别逆置 b-1 , a-1 */ void Reverse(int R[], int left, int right){ for (int i = 0; i <= (right - left)/2; i++) swap(R[left+i], R[right-i]); } void Converse(int R[], int n, int p){ Reverse(R, 0, n-1); Reverse(R, 0, p-1); Reverse(R, p, n-1); } /* 三个Reverse的时间复杂度分别为O(n/2), O(p/2), O( (n-p)/2 ). 该算法的时间复杂度为O(n), 空间复杂度为O(1) */ /* 11. 找到两个等长上升序列 merge 的中位数 */ /* 设计思想：分别求两个升序序列A，B的中位数，记为a，b。求中位数的过程如下： 1. 若 a = b, 则a 或 b 即为所求中位数； 2. 若 a < b, 则舍弃 A 中较小的一半 和 B 中较大的一半，要求舍弃的长度一致； 3. 若 a > b, 则舍弃 B 中较小的一半 和 A 中较大的一半，要求舍弃的长度一致； 在保留的两个升序序列中重复 1,2,3过程，直到两个序列中只含一个元素时，较小者即为所求的中位数 */ int Mean(int A[], int B[], int n){ int a, b, aL = 0, aR = n-1, bL = 0, bR = n-1; //分别表示A，B的中位数，首位数和末位数的下标 while(aL < aR || bL < bR){ a = (aL + aR) / 2; b = (bL + bR) / 2; if (A[a] == B[b]) return A[a]; //满足条件 1 if (A[a] < B[b]){ //满足条件2 if ((aL + aR) % 2 == 0){ //如果个数为奇数 aL = a; //舍弃 A 中间点之前的部分并保留中间数 e.g {1,4,5}, {2, 3, 7} bR = b; //舍弃 B 中间点之后的部分并保留中间数 } else{ //满足条件3 aL = a+1; //舍弃 A 中间点之前的部分和中间数 bR = b; //舍弃 B 中间点之后的部分并保留中间数 } } else{ if ((aL + aR) % 2 == 0){ //如果个数为奇数 aR = a; //舍弃 A 中间点之前的部分并保留中间数 e.g {1,4,5}, {2, 3, 7} bL = b; //舍弃 B 中间点之后的部分并保留中间数 } else{ aR = a; //舍弃 A 中间点之后的部分并保留中间数 bL = b+1; //舍弃 B 中间点之前的部分和中间数 } } } return A[a] < B[b] ? A[a] : B[b]; } /* 时间复杂度为(log2n) 空间复杂度为O(1)*/ /* 12. 找到一个长度为n的整数序列A的主元素（即为数量最多的那个数，且数量m > n/2）， 若存在则输出，否则输出-1 */ /* 设计思想：从前向后扫描数组元素 1. 选取候选的主元素 依次扫描数组的每个数，将第一个遇到的数num保存到c中，记录num出现的次数为1；若遇到的下个数 仍是num，则计数+1，否则-1；当计数为0时，将遇到的下一个数保存在c中，重新计数为1，重复上述步骤。 2. 判断c是否为真正的主元素 再次扫描数组，统计c中元素出现的次数，若 > n/2,则为主元素，否则不是。 */ int Majority(int A[], int n){ int c, count = 1; c = A[0]; for (int i = 1; i < n; i++) if (A[i] == c) count++; else if (count > 0) count--; else{ //更换主元，重新计数 c = A[i]; count = 1; } if (count > 0) for(int i = 0; i < n; i++) //统计主元出现的实际次数 if (A[i] == c) count++; return count > n/2 ? c : -1; } /* 时间复杂度O(n), 空间复杂度O(1) */ /* 13. 找到 n 个整数的数组A中未出现的最小正整数 */ /* 设计思想：用一个数组B[n]来标记数组A中是否出现了1~n的整数，B[0] = 1; */ void findMissMin(int A[], int n){ int *B; //标记数组B B = (int *)malloc(sizeof(int) * n); memset(B, 0, sizeof(B)); //将数组B赋初值为0 for (int i = 0; i < n; i++) if (A[i] > 0 && A[i] <= n) //若A[i]的值在 1~n 之间，则标记数组B B[A[i]-1] = 1; for (int i = 0; i < n; i++) //扫描数组B，返回目标值 if (B[i] == 0) return i+1; } /* 时间复杂度为O(n), 空间复杂度为(n) */ int main(){ SqList L; SeqList S; //C的动态分配 L.data = (ElemType*) malloc (sizeof(ElemType) * InitSize); //C++的动态分配 S.data = new ElemType[InitSize]; return 0; }