admin管理员组文章数量:1794759
2024重生之回溯数据结构与算法系列学习(11)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
回溯数据结构与算法系列学习之栈和队列精题汇总
(6)题目:三角矩阵Q按行存储
解题思路:
代码语言:javascript代码运行次数:0运行复制TwoMapOneDim 函数将下三角矩阵的元素存储在一维数组中。
OneDimIndex 函数用于根据行列索引从一维数组中获取对应的值,但为了正确性,需确保处理上三角的情况。
PrintTwoDim 和 PrintOneDim 函数用于分别打印二维和一维数组的内容。
在 main 函数中,首先定义了并打印了一个下三角矩阵,然后调用转换函数,将其存储到一维数组中并打印,最后获取特定位置的值并打印
代码实现:
代码语言:javascript代码运行次数:0运行复制#include <iostream>
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)题目:二维数组按行存储
解题思路:
代码语言:javascript代码运行次数:0运行复制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)
代码实现:
代码语言:javascript代码运行次数:0运行复制#include <iostream>
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——中缀表达式转成后缀表达式
解题思路:
代码语言:javascript代码运行次数:0运行复制>遇到操作数,将其直接加入后缀表达式
>遇到界限符:如果是(,直接入栈
如果是),则依次弹出栈内运算符将其加入后缀表达式直到遇到左括号
>遇到运算符,依次弹出优先级高于或等于当前运算符的所有运算符,并加入后缀表达式
直到遇到左括号或者是栈空
>将栈中剩余运算符依次弹出,并加入后缀表达式
代码实现:
代码语言:javascript代码运行次数:0运行复制#include <iostream>
using namespace std;
#define MAXSIZE 100 // 定义栈的最大容量
// 定义栈的结构体
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
解题思路:
代码语言:javascript代码运行次数:0运行复制斐波那契数列两种实现:
>利用递归,无需多说
>利用栈,就是找二叉树的叶子结点个数,不断将子节点压入栈中
代码实现:
代码语言:javascript代码运行次数:0运行复制#include <iostream>
using namespace std;
#define MAXSIZE 100 // 定义栈的最大容量
// 定义栈的结构体
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—后缀表达式的计算
解题思路:
代码语言:javascript代码运行次数:0运行复制>从左往右扫描下一个元素,直到处理完所有元素
>若扫描到操作数则压入栈,并回到操作1,否则执行3
>若扫描到运算符,则弹出两个栈顶元素,执行相应计算,运算结果压回栈顶,回到1
代码实现:
代码语言:javascript代码运行次数:0运行复制#include <iostream>
using namespace std;
#define MAXSIZE 100 // 定义栈的最大容量
// 定义栈的结构体
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)题目:将对称矩阵压缩保存到一维数组
解题思路:
代码语言:javascript代码运行次数:0运行复制将二维数组转换为一维数组:
TwoMapOneDim 函数接收一个二维数组,将其下三角矩阵的元素存储到传入的一维数组中。
根据索引从一维数组获取值:
OneDimIndex 函数根据行和列的索引计算出在一维数组中的位置,并返回该位置的值。
打印二维数组:
PrintTwoDim 函数用于打印传入的二维数组,格式化输出每个元素。
打印一维数组:
PrintOneDim 函数用于打印传入的一维数组,输出所有元素。
主函数:
在 main 中定义了一个 3x3 的二维数组,并创建一个足够大的数组来存储下三角矩阵的元素。
调用打印函数展示二维数组,调用转换函数将下三角元素存入一维数组,再打印一维数组。
最后,通过 OneDimIndex 函数输出特定位置的值。
代码实现:
代码语言:javascript代码运行次数:0运行复制#include <iostream>
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)对应的值
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。 原始发表:2024-10-18,如有侵权请联系 cloudcommunity@tencent 删除索引存储函数数据结构与算法数组本文标签: 2024重生之回溯数据结构与算法系列学习(11)无论是王道考研人还是IKUN都能包会的不然别给我家鸽鸽丟脸好嘛
版权声明:本文标题:2024重生之回溯数据结构与算法系列学习(11)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】 内容由林淑君副主任自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.xiehuijuan.com/baike/1754674397a1705049.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论