欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
回溯数据结构与算法系列学习之栈和队列精题汇总
(6)题目：三角矩阵Q按行存储
-
编
解题思路：
TwoMapOneDim 函数将下三角矩阵的元素存储在一维数组中。 OneDimIndex 函数用于根据行列索引从一维数组中获取对应的值，但为了正确性，需确保处理上三角的情况。 PrintTwoDim 和 PrintOneDim 函数用于分别打印二维和一维数组的内容。 在 main 函数中，首先定义了并打印了一个下三角矩阵，然后调用转换函数，将其存储到一维数组中并打印，最后获取特定位置的值并打印
代码实现：
using namespace std; // 将下三角矩阵按行存储在一维数组中 void TwoMapOneDim(int arr[][3], int array[], int row, int col) { int k = 0; // 用于一维数组的索引 // 遍历二维数组的每一行 for (int i = 0; i < row; i++) { // 遍历当前行的有效列（即下三角部分） for (int j = 0; j <= i; j++) { array[k++] = arr[i][j]; // 将下三角元素存入一维数组 } } // 在一维数组的最后一个位置存储该二维数组的右上角元素（示例中为999） array[k] = arr[0][col - 1]; } // 按照索引从一维数组取值 int OneDimIndex(int *array, int i, int j) { // 如果 i 大于等于 j，说明在下三角区域 if (i >= j) { return array[i * (i - 1) / 2 + j - 1]; // 根据公式计算下三角矩阵的一维索引 } else { // 如果不在下三角区域，返回上三角部分的某个值（此处逻辑有误，应该是返回错误处理） return array[3 * (3 + 1) / 2]; // 这里应该是返回无效值，实际可能需要调整 } } // 打印二维数组 void PrintTwoDim(int arr[][3], int row, int col) { for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { cout << arr[i][j] << '\t'; // 按行打印每个元素 } cout << endl; // 每行结束后换行 } } // 打印一维数组 void PrintOneDim(int *arr, int n) { for (int i = 0; i < n; i++) { cout << arr[i] << '\t'; // 打印每个元素 } cout << endl; // 打印结束后换行 } int main() { // 初始化一个3x3的下三角矩阵 int arr[3][3] = {{1, 999, 999}, {4, 2, 999}, {5, 6, 3}}; // 创建一维数组以存储下三角矩阵的元素 int array[3 * (3 + 1) / 2 + 1]; // 打印原始二维数组 PrintTwoDim(arr, 3, 3); // 将二维数组的下三角部分存储到一维数组中 TwoMapOneDim(arr, array, 3, 3); // 打印存储下三角元素的一维数组 PrintOneDim(array, 3 * (3 + 1) / 2 + 1); // 从一维数组中获取给定索引的值并输出（示例：获取坐标(1, 3)的值） cout << OneDimIndex(array, 1, 3); // 输出结果应该是999 }
编辑
(7)题目：二维数组按行存储
-
编辑
解题思路：
TwoMapOneDim 函数： 输入参数：二维数组 arr、一维数组 array、行数 row 和列数 col。 目的是将二维数组的所有元素按行存储到一维数组中。 使用嵌套循环逐行逐列遍历二维数组，将每个元素赋值给一维数组。 OneDimIndex 函数： 输入参数：一维数组 array 和索引 i, j（表示二维数组的行和列）。 目的是根据给定的行列索引计算在一维数组中的位置，并返回该位置的值。 计算公式为 (i - 1) * 3 + (j - 1)，其中 3 是列数，考虑到数组索引从0开始。 PrintTwoDim 函数： 输入参数：二维数组 arr、行数 row 和列数 col。 目的是打印整个二维数组，每个元素之间用制表符分隔，行末换行。 PrintOneDim 函数： 输入参数：一维数组 arr 和元素个数 n。 目的是打印一维数组的所有元素，元素之间用制表符分隔，最后换行。 main 函数： 定义了一个3x3的二维数组并初始化。 创建了一维数组 array 存储元素。 调用 PrintTwoDim 打印原始二维数组。 调用 TwoMapOneDim 将二维数组元素存入一维数组。 调用 PrintOneDim 打印一维数组的内容。 最后调用 OneDimIndex 获取并打印一维数组在行3列2位置的值（应该为6）
代码实现：
using namespace std; // 将二维数组按行存储到一维数组中 void TwoMapOneDim(int arr[][3], int array[], int row, int col) { int k = 0; // 用于一维数组的索引 // 遍历二维数组的每一行 for (int i = 0; i < row; i++) { // 遍历当前行的每一列 for (int j = 0; j < col; j++) { array[k++] = arr[i][j]; // 将二维数组的元素存入一维数组 } } } // 按照索引从一维数组取值 int OneDimIndex(int *array, int i, int j) { return array[(i - 1) * 3 + j - 1]; // 根据行列索引计算一维数组的索引并返回对应的值 } // 打印二维数组 void PrintTwoDim(int arr[][3], int row, int col) { for (int i = 0; i < row; i++) // 遍历每一行 { for (int j = 0; j < col; j++) // 遍历当前行的每一列 { cout << arr[i][j] << '\t'; // 打印当前元素，使用制表符分隔 } cout << endl; // 每行结束后换行 } } // 打印一维数组 void PrintOneDim(int *arr, int n) { for (int i = 0; i < n; i++) // 遍历一维数组的每个元素 { cout << arr[i] << '\t'; // 打印当前元素，使用制表符分隔 } cout << endl; // 打印结束后换行 } int main() { // 初始化一个3x3的二维数组 int arr[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; int array[9]; // 创建一维数组以存储9个元素（3x3） // 打印原始二维数组 PrintTwoDim(arr, 3, 3); // 将二维数组的元素存储到一维数组中 TwoMapOneDim(arr, array, 3, 3); // 打印存储在一维数组中的元素 PrintOneDim(array, 9); // 获取并打印一维数组中指定位置的值（行3，列2） cout << OneDimIndex(array, 3, 2); // 输出结果应该是6 }
(8)题目：栈的应用Q——中缀表达式转成后缀表达式
解题思路：
>遇到操作数，将其直接加入后缀表达式 >遇到界限符：如果是(，直接入栈 如果是)，则依次弹出栈内运算符将其加入后缀表达式直到遇到左括号 >遇到运算符，依次弹出优先级高于或等于当前运算符的所有运算符，并加入后缀表达式 直到遇到左括号或者是栈空 >将栈中剩余运算符依次弹出，并加入后缀表达式
代码实现：
using namespace std; // 定义栈的最大容量 // 定义栈的结构体 typedef struct { char data[MAXSIZE]; // 存放栈元素的数组 int top1 = -1; // 栈顶指针，初始值为-1表示栈为空 } Stack; // 判断栈是否为空 bool StackEmpty(Stack s) { return s.top1 == -1; // 如果栈顶指针为-1，说明栈为空 } // 判断栈是否溢出 bool StackOverflow(Stack s) { return s.top1 >= MAXSIZE; // 如果栈顶指针大于等于最大容量，说明栈已满 } // 压栈操作 void Push(Stack &s, char x) { if (!StackOverflow(s)) // 检查栈是否溢出 { s.data[++s.top1] = x; // 将元素压入栈中，并更新栈顶指针 } else { cout << "当前栈已满" << endl; // 如果栈满，输出提示信息 } } // 弹栈操作 char Pop(Stack &s) { if (StackEmpty(s)) // 检查栈是否为空 { return '\0'; // 返回'\0'表示栈为空 } else { return s.data[s.top1--]; // 返回栈顶元素并更新栈顶指针 } } // 将中缀表达式转为后缀表达式 string InfixToSuffix(string infix) { Stack s; // 创建一个栈用于存放运算符 string suffix = ""; // 用于存放后缀表达式 char op; // 临时变量用于存放弹出的运算符 // 遍历中缀表达式中的每个字符 for (int i = 0; i < infix.length(); i++) { // 遇到操作数（A-Z）直接加入后缀表达式 if (infix[i] >= 'A' && infix[i] <= 'Z') { suffix += infix[i]; } // 遇到左括号，直接入栈 else if (infix[i] == '(') { Push(s, infix[i]); } // 遇到右括号，依次弹出运算符直至遇到左括号 else if (infix[i] == ')') { while (!StackEmpty(s)) { op = Pop(s); if (op != '(') // 如果不是左括号，将运算符加入后缀表达式 { suffix += op; } else { break; // 遇到左括号，停止弹栈 } } } else { // 如果是乘号或者除号，只弹出优先级相同或更高的运算符 if (infix[i] == '*' || infix[i] == '/') { while (!StackEmpty(s)) { op = Pop(s); if (op == '(') // 遇到左括号，停止弹栈 { break; } else { // 碰到低级运算符（+ 或 -），弹出后再压回去 if (op == '+' || op == '-') { Push(s, op); // 将低级运算符压回栈中 break; } else { suffix += op; // 将高优先级运算符加入后缀表达式 } } } } // 遇到加号或减号，将所有运算符弹出 else if (infix[i] == '+' || infix[i] == '-') { while (!StackEmpty(s)) { op = Pop(s); if (op == '(') // 遇到左括号，停止弹栈 { break; } else { suffix += op; // 将运算符加入后缀表达式 } } } // 将当前运算符压入栈中 Push(s, infix[i]); } } // 将栈中剩余的运算符依次弹出 while (!StackEmpty(s)) { suffix += Pop(s); } return suffix; // 返回生成的后缀表达式 } int main() { string infix = "A+B*(C-D)-E/F"; // 示例中缀表达式 cout << InfixToSuffix(infix); // 输出转换后的后缀表达式 }
(9)题目：利用栈实现斐波那契数列Q
-
编辑
解题思路：
斐波那契数列两种实现： >利用递归，无需多说 >利用栈，就是找二叉树的叶子结点个数，不断将子节点压入栈中
代码实现：
using namespace std; // 定义栈的最大容量 // 定义栈的结构体 typedef struct { int data[MAXSIZE]; // 存储栈元素的数组 int top1 = -1; // 栈顶指针，初始值为-1表示栈为空 } Stack; // 判断栈是否为空 bool StackEmpty(Stack s) { return (s.top1 == -1); // 如果栈顶指针为-1，说明栈为空 } // 判断栈是否溢出 bool StackOverflow(Stack s) { return (s.top1 >= MAXSIZE); // 如果栈顶指针大于等于最大容量，说明栈已满 } // 压栈操作 void Push(Stack &s, int x) { if (!StackOverflow(s)) // 检查栈是否溢出 { s.data[++s.top1] = x; // 将元素压入栈中，并更新栈顶指针 } else { cout << "当前栈已满" << endl; // 如果栈满，输出提示信息 } } // 弹栈操作 int Pop(Stack &s) { if (StackEmpty(s)) // 检查栈是否为空 { cout << "当前栈已空" << endl; // 输出提示信息 return '\0'; // 返回'\0'表示栈为空 } else { return s.data[s.top1--]; // 返回栈顶元素并更新栈顶指针 } } // 利用递归实现斐波那契数列 int FibRecursion(int n) { if (n == 1 || n == 2) // 基本情况：当 n 为 1 或 2 时，返回 1 { return 1; } return FibRecursion(n - 1) + FibRecursion(n - 2); // 递归调用计算斐波那契数 } // 利用栈实现斐波那契数列 int FibStack(int n) { Stack s; // 初始化栈 int result = 0; // 用于存放结果 Push(s, n); // 将根节点压入栈中 while (!StackEmpty(s)) // 当栈不为空时循环 { int value = Pop(s); // 将栈顶元素弹出 // 计算叶子节点个数 if (value == 1 || value == 2) // 如果是基本情况 { result += 1; // 结果加一 } // 将根节点的两个子节点压入栈中 else { Push(s, value - 1); // 将 n-1 压入栈 Push(s, value - 2); // 将 n-2 压入栈 } } return result; // 返回计算的结果 } int main() { cout << FibRecursion(7) << endl; // 输出递归方式计算的第 7 个斐波那契数 cout << FibStack(7) << endl; // 输出栈方式计算的第 7 个斐波那契数 }
(10)题目：栈的应用Q—后缀表达式的计算
解题思路：
>从左往右扫描下一个元素，直到处理完所有元素 >若扫描到操作数则压入栈，并回到操作1，否则执行3 >若扫描到运算符，则弹出两个栈顶元素，执行相应计算，运算结果压回栈顶，回到1
代码实现：
using namespace std; // 定义栈的最大容量 // 定义栈的结构体 typedef struct { double data[MAXSIZE] = {0.0}; // 存储栈元素的数组，初始值为0.0 int top1 = -1; // 栈顶指针，初始值为-1表示栈为空 } Stack; // 判断栈是否为空 bool StackEmpty(Stack s) { return (s.top1 == -1); // 如果栈顶指针为-1，说明栈为空，返回true } // 判断栈是否溢出 bool StackOverflow(Stack s) { return (s.top1 >= MAXSIZE); // 如果栈顶指针大于等于最大容量，说明栈已满，返回true } // 压栈操作 void Push(Stack &s, double x) { if (!StackOverflow(s)) // 检查栈是否溢出 { s.data[++s.top1] = x; // 将元素压入栈中，并更新栈顶指针 } else { cout << "当前栈已满" << endl; // 如果栈满，输出提示信息 } } // 弹栈操作 double Pop(Stack &s) { if (StackEmpty(s)) // 检查栈是否为空 { return '\0'; // 返回'\0'表示栈为空 } else { return s.data[s.top1--]; // 返回栈顶元素并更新栈顶指针 } } // 计算后缀表达式 void CalSuffix(string suffix[]) { Stack s; // 创建栈，用于保存操作数 for (int i = 0; i < 15; i++) // 遍历后缀表达式中的每个元素 { // 如果是运算数，将其压入栈 if (suffix[i] != "+" && suffix[i] != "-" && suffix[i] != "*" && suffix[i] != "/") { Push(s, atoi(suffix[i].c_str())); // 将字符串转换为整数并压入栈 } // 如果是操作符，依次弹出两个操作数 else { double oper1 = Pop(s); // 右操作数 double oper2 = Pop(s); // 左操作数 // 执行相应运算，将运算结果压入栈中 if (suffix[i] == "+") { Push(s, oper2 + oper1); // 加法 } else if (suffix[i] == "-") { Push(s, oper2 - oper1); // 减法 } else if (suffix[i] == "*") { Push(s, oper2 * oper1); // 乘法 } else if (suffix[i] == "/") { Push(s, oper2 / oper1); // 除法 } } } // 最终栈顶元素即为结果 cout << "最终结果为：" << Pop(s) << endl; // 输出计算结果 } int main() { // 待计算的后缀表达式 string suffix[] = {"15", "7", "1", "1", "+", "-", "/", "3", "*", "2", "1", "1", "+", "+", "-"}; CalSuffix(suffix); // 调用计算后缀表达式的函数 }
(11)题目：将对称矩阵压缩保存到一维数组
编辑
- 解题思路：
将二维数组转换为一维数组： TwoMapOneDim 函数接收一个二维数组，将其下三角矩阵的元素存储到传入的一维数组中。 根据索引从一维数组获取值： OneDimIndex 函数根据行和列的索引计算出在一维数组中的位置，并返回该位置的值。 打印二维数组： PrintTwoDim 函数用于打印传入的二维数组，格式化输出每个元素。 打印一维数组： PrintOneDim 函数用于打印传入的一维数组，输出所有元素。 主函数： 在 main 中定义了一个 3x3 的二维数组，并创建一个足够大的数组来存储下三角矩阵的元素。 调用打印函数展示二维数组，调用转换函数将下三角元素存入一维数组，再打印一维数组。 最后，通过 OneDimIndex 函数输出特定位置的值。
代码实现：
using namespace std; // 将二维数组按行存储在一维数组中，保存下三角矩阵 void TwoMapOneDim(int arr[][3], int array[], int row, int col) { int k = 0; // 一维数组的索引 for (int i = 0; i < row; i++) // 遍历行 { for (int j = 0; j <= i; j++) // 遍历列，j的范围是从0到i（包括i），以获取下三角元素 { array[k++] = arr[i][j]; // 将下三角元素存入一维数组中 } } } // 按照索引从一维数组取值 int OneDimIndex(int *array, int i, int j) { // 根据行和列的索引计算一维数组中的位置并返回该值 if (i >= j) { return array[i * (i - 1) / 2 + j - 1]; // 当i >= j时，使用这个公式 } else { return array[j * (j - 1) / 2 + i - 1]; // 当i < j时，使用这个公式 } } // 打印二维数组 void PrintTwoDim(int arr[][3], int row, int col) { for (int i = 0; i < row; i++) // 遍历每一行 { for (int j = 0; j < col; j++) // 遍历每一列 { cout << arr[i][j] << '\t'; // 输出当前元素 } cout << endl; // 换行 } } // 打印一维数组 void PrintOneDim(int *arr, int n) { for (int i = 0; i < n; i++) // 遍历一维数组 { cout << arr[i] << '\t'; // 输出当前元素 } cout << endl; // 换行 } int main() { int arr[3][3] = {{1, 4, 5}, {4, 2, 6}, {5, 6, 3}}; // 定义一个3x3的二维数组 int array[3 * (3 + 1) / 2]; // 定义一维数组，大小为下三角矩阵的元素个数 PrintTwoDim(arr, 3, 3); // 打印二维数组 TwoMapOneDim(arr, array, 3, 3); // 将下三角矩阵元素存入一维数组 PrintOneDim(array, 3 * (3 + 1) / 2); // 打印一维数组 cout << OneDimIndex(array, 1, 3); // 输出一维数组中(1, 3)对应的值 }
