王道2019数据结构第二章线性表综合应用题笔记

今天药忘吃喽~ 2022-05-25 23:41 160阅读 0赞

#include<iostream> using namespace std; #define MAXSIZE 50 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; }SqList; //1、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除的元素的值，空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行 bool Del_Min(SqList &L, ElemType &value) { //删除顺序表L中的最小值元素节点，并通过引用型参数value返回其值 //如果删除成功，返回true，否则，返回false； 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]; pos = i; } } L.data[pos] = L.data[L.length - 1]; L.length--; return true; } //2、设计一个高效的算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1) void Reverse(SqList &L) { ElemType temp; for (int i = 0; i < L.length / 2; i++) { temp = L.data[i]; L.data[i] = L.data[L.length - 1 - i]; L.data[L.length - 1 - i] = temp; } } //3、长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素 void delete_(SqList &L, ElemType x) { int k = 0; for (int i = 0; i < L.length; i++) {//记录等于x的元素的下标，用不相等的元素进行覆盖 if (L.data[i] != x) { L.data[k] = L.data[i]; k++; } } L.length = k; } //4、从有序顺序表中删除其值在给定值s与t之间（要求s<t)的所有元素，如果s不合理或者顺序表为空则显示出错信息并退出运行。 bool delete_1(SqList &L, ElemType s, ElemType t) { if (s >= t || 0 == L.length) { return false; } int l, r, length; for (l = 0; s > L.data[l]; l++);//l停在第一个大于等于s的元素处，所以进行移动时，从l处开始覆盖即可 for (r = L.length - 1; t < L.data[r]; r--);//r停在第一个小于等于t的元素处，所以进行移动时需要从r+1个元素处开始 length = r - l + 1;//l 到 r 共包含r-l+1个元素 for (int k = r + 1; k < L.length; k++) { L.data[l++] = L.data[k]; } L.length -= length;//有序表中进行删除操作后的新元素数量 return true; } //5、从顺序表中删除其值在给定值s与t之间（包含s和t要求s<t)的所有元素，如果s不合理或者顺序表为空则显示出错信息并退出运行。 bool delete_2(SqList &L, ElemType s, ElemType t) { if (s >= t || 0 == L.length) { return false; } int i, k = 0; //算法思想：从前往后扫描L，用k记录下元素值在s到t之间的元素的个数，对于当前扫描的元素，如果i其值不在s到t之间就前移k个位置，否则执行k++ //每个不在s到t之间的元素仅移动了一次 算法效率高 for (i = 0; i < L.length; i++) { if (L.data[i] >= s && L.data[i] <= t) { k++; } else { L.data[i - k] = L.data[i]; } } L.length = k; return true; } //6、从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同 void delete_6(SqList &L) { int k = 0; for (int i = 1; i < L.length; i++) { if (L.data[i] == L.data[i - 1]) { k++; continue; } L.data[i - k] = L.data[i]; } L.length -= k; } //7、将两个有序顺序表合成一个新的有序顺序表，并且由函数返回结果顺序表 （归并排序) bool Ques7(SqList sqList1, SqList sqList2, SqList &newSqList) { //此处默认两个有序表的顺序是一致的 若是一表升序一表降序需要找到其统一的一头 if (size(newSqList.data) < sqList1.length + sqList2.length) { //判断是否合并起来的顺序表长度大于最大长度 size()表示的是新顺序表数组的长度 return false; } int i = 0, j = 0, k = 0; while (i < sqList1.length && j < sqList2.length) { if (sqList1.data[i] <= sqList2.data[j]) { newSqList.data[k++] = sqList1.data[i++]; } else { newSqList.data[k++] = sqList2.data[j++]; } } while (i < sqList1.length) { newSqList.data[k++] = sqList1.data[i++]; } while (j < sqList1.length) { newSqList.data[k++] = sqList2.data[j++]; } newSqList.length = k + 1; return true; } //8、已知在一维数组A[m+n]中一次存放着两个线性表（a1,a2,....,am)和(b1,b2,...,bn)。试编写一个函数，将数组中的两个顺序表的位置互换 void Que8(ElemType A[], int m, int n) { //思路:将两个线性表分别逆置，最后将整个数组逆置 ElemType temp; int i = 0; for (i = 0; i < m / 2; i++) {//逆置前半部分 temp = A[i]; A[i] = A[m - 1 - i]; A[m - 1 - i] = temp; } for (i = 0; i < (n - m) / 2; i++) {//逆置后半部分 temp = A[i+m]; A[i+m] = A[n-i-1]; A[n - i-1] = temp; } for (i = 0; i < n / 2; i++) {//整体逆置 temp = A[i]; A[i] = A[n - 1 - i]; A[n - 1 - i] = temp; } } int main() { /*SqList sqList; for (int i = 0; i < 20; i++) { sqList.data[i] = i/2; } sqList.length = 20; for (int i = 0; i < sqList.length; i++) { cout << sqList.data[i] << " "; } cout << endl; cout << sizeof(sqList.data) << endl; cout << sizeof(sqList.data[0]) << endl; cout << size(sqList.data)<< endl; cout << endl << "len" << sqList.length << endl; delete_6(sqList); for (int i = 0; i < sqList.length; i++) { cout << sqList.data[i] << " "; } cout << endl << "len" << sqList.length << endl; system("pause"); */ ElemType a[10]; for (int i = 0; i < 10; i++) { a[i] = rand() % 99; cout << a[i] << " "; } cout << endl; Que8(a, 4, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; system("pause"); return 0; }