admin管理员组文章数量:1794759
2024重生之回溯数据结构与算法系列学习（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
溯数据结构与算法系列学习之栈和队列精题汇总
（1）题目：设计一个递归算法，删除不带头结点的单链表L 中所有值为 x 的结点。
解题思路：
代码语言：javascript代码运行次数：0运行复制>利用递归，不断将节点的下个节点传入函数
>每个函数执行对应删除操作实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
int data; // 节点数据
struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是指向 LNode 的指针类型
// 头插法插入节点
void HeadInsert(LinkList &L)
{
int val = 0; // 用于存储用户输入的值
while (cin >> val) // 循环读取输入的值
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 将输入的值赋给新节点
s->next = L->next; // 新节点的下一个指针指向当前链表的第一个节点
L->next = s; // 链表头指针的下一个指针指向新节点
if (cin.get() == '\n') // 检查是否读取到换行符
{
break; // 如果是换行符，结束输入
}
}
}
// 尾插法插入节点
void TailInsert(LinkList &L)
{
int val = 0; // 用于存储用户输入的值
LNode *r = L; // r指向链表的尾部
while (cin >> val) // 循环读取输入的值
{
LNode *s = new LNode; // 创建新节点
s->data = val; // 将输入的值赋给新节点
r->next = s; // 当前尾节点的下一个指针指向新节点
r = s; // 更新尾指针为新节点
r->next = NULL; // 新节点的下一个指针设为NULL
if (cin.get() == '\n') // 检查是否读取到换行符
{
break; // 如果是换行符，结束输入
}
}
}
// 遍历输出链表元素
void Print(LinkList L)
{
LNode *p = L->next; // 从链表的第一个节点开始遍历
while (p) // 当当前节点不为空时
{
cout << p->data << '\t'; // 输出当前节点的数据
p = p->next; // 移动到下一个节点
}
cout << endl; // 输出换行
}
// 删除链表中所有值为 x 的节点
void DelValue(LinkList &L, int x)
{
if (L == NULL) // 如果链表为空，直接返回
{
return;
}
LNode *p; // 用于保存待删除的节点
// 如果头节点的值等于 x
if (L->data == x)
{
p = L; // 保存当前节点
L = L->next; // 头指针指向下一个节点
delete p; // 删除当前节点
DelValue(L, x); // 递归调用删除函数
}
else
{
DelValue(L->next, x); // 否则继续递归检查下一个节点
}
}
int main()
{
LinkList L = new LNode; // 创建一个新的链表头节点
TailInsert(L); // 尾插法插入节点
DelValue(L, 2); // 删除链表中所有值为 2 的节点
Print(L); // 打印链表中的节点
}（2）题目：通过C++实现链栈Q ChainStack
实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义每个节点结构
typedef struct Node
{
int data; // 节点数据
struct Node *next; // 指向下一个节点的指针
} Node;
// 定义链栈结构
typedef struct
{
Node *top; // 栈顶指针
int size; // 栈中元素数量
} ChainStack;
// 将元素v压入栈中
void Push(ChainStack &s, int v)
{
/***********************************
* description: 将元素v压入栈中
* input:
* @s: 链栈结构
* @v: 待压入的值
* return:
***********************************/
Node *p = new Node; // 创建一个新节点
p->data = v; // 设置节点的数据
p->next = s.top->next; // 新节点指向当前栈顶的下一个节点
s.top->next = p; // 更新栈顶指针，指向新节点
s.size++; // 增加栈的大小
}
// 判断链栈是否为空
bool IsEmpty(ChainStack s)
{
/***********************************
* description: 判断链栈是否为空
* input:
* @s: 链栈结构
* return:
***********************************/
if (s.top->next) // 如果栈顶的下一个节点不为空
{
return false; // 栈不为空
}
return true; // 否则栈为空
}
// 将栈顶元素弹出
void Pop(ChainStack &s)
{
/***********************************
* description: 将栈顶元素弹出
* input:
* @s: 链栈结构
* return:
***********************************/
if (IsEmpty(s)) // 如果栈为空，无法弹出
{
return;
}
Node *p = s.top->next; // 保存当前栈顶节点
s.top->next = p->next; // 栈顶指针移向下一个节点
delete p; // 释放栈顶元素节点空间
s.size--; // 减少栈的大小
}
// 获取栈顶元素
int GetTop(ChainStack s)
{
/***********************************
* description: 获取栈顶元素
* input:
* @s: 链栈
* return:
***********************************/
if (IsEmpty(s)) // 如果栈为空
{
return -1; // 返回-1表示无栈顶元素
}
return s.top->next->data; // 返回栈顶节点的数据
}
// 获取栈中元素数量
int GetSize(ChainStack s)
{
/***********************************
* description: 获取栈中元素数量
* input:
* @s: 链栈
* return:
***********************************/
return s.size; // 返回栈的大小
}
// 初始化一个链栈
ChainStack *InitStack()
{
/***********************************
* description: 初始化一个链栈
* input:
* return: 返回一个初始化好的链栈指针
***********************************/
ChainStack *s = new ChainStack; // 创建新的链栈
s->top = new Node; // 创建栈顶节点
s->top->next = nullptr; // 栈顶节点的下一个指针初始化为nullptr
s->size = 0; // 初始化栈大小为0
return s; // 返回初始化好的链栈
}
int main()
{
ChainStack *s = InitStack(); // 初始化链栈
Push(*s, 5); // 压入元素5
Push(*s, 4); // 压入元素4
Push(*s, 3); // 压入元素3
Push(*s, 2); // 压入元素2
cout << GetSize(*s) << endl; // 输出栈的大小
cout << GetTop(*s) << endl; // 输出栈顶元素
Pop(*s); // 弹出栈顶元素
cout << GetTop(*s) << endl; // 再次输出栈顶元素
}运行截图：
（3）题目：栈的应用Q——实现括号匹配利用栈实现括号匹配C、C++完整实现（可直接运行）
解题思路：
代码语言：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)
{
if (s.top1 == -1) // 若栈顶指针为-1，表示栈为空
{
return true; // 返回true，栈为空
}
return false; // 否则返回false，栈不为空
}
// 判断栈是否溢出
bool StackOverflow(Stack s)
{
if (s.top1 >= MAXSIZE - 1) // 若栈顶指针大于等于最大容量减1，表示栈已满
{
return true; // 返回true，栈溢出
}
return false; // 否则返回false，栈未满
}
// 压栈操作
void Push(Stack &s, char x)
{
if (!StackOverflow(s)) // 检查栈是否溢出
{
s.data[++s.top1] = x; // 将元素压入栈中，并更新栈顶指针
}
else
{
cout << "当前栈已满" << endl; // 输出栈满提示
}
}
// 弹栈操作
char Pop(Stack &s)
{
if (StackEmpty(s)) // 检查栈是否为空
{
cout << "当前栈已空" << endl; // 输出栈空提示
return '\0'; // 返回空字符表示无元素可弹出
}
else
{
return s.data[s.top1--]; // 返回栈顶元素，并更新栈顶指针
}
}
// 实现括号匹配
void BracketMatch(Stack &s, string str)
{
for (int i = 0; i < str.length(); i++) // 遍历输入字符串
{
// 如果是左括号，将其压入栈中
if (str[i] == '[' || str[i] == '{' || str[i] == '(')
{
Push(s, str[i]); // 压入栈
}
else
{
// 如果此时是右括号，而栈为空，则括号不匹配
if (StackEmpty(s))
{
cout << "括号不匹配" << endl; // 输出不匹配提示
return; // 结束函数
}
else
{
char chr = Pop(s); // 弹出栈顶元素
// 如果栈不为空，但是栈顶元素与当前右括号不匹配
if (!((str[i] == ']' && chr == '[') ||
(str[i] == '}' && chr == '{') ||
(str[i] == ')' && chr == '(')))
{
cout << "括号不匹配" << endl; // 输出不匹配提示
return; // 结束函数
}
}
}
}
// 如果全部匹配后，栈为空表示括号匹配成功
if (StackEmpty(s))
{
cout << "括号匹配" << endl; // 输出匹配成功提示
return; // 结束函数
}
// 栈中有多余的括号，则不匹配
cout << "括号不匹配" << endl; // 输出不匹配提示
}
int main()
{
Stack s; // 创建栈实例
string str = "({})"; // 测试字符串
BracketMatch(s, str); // 调用括号匹配函数
}（4）题目：稀疏 数组Q利用三元组存储
解题思路：
实现代码：
代码语言：javascript代码运行次数：0运行复制#include <iostream>
using namespace std;
// 定义三元组结构体
typedef struct
{
int row; // 行索引
int col; // 列索引
int value; // 非零值
} Triple[100]; // 定义三元组数组，最多存储100个三元组
// 将稀疏数组存储到三元组
void ArrToTriple(int arr[][3], Triple t, int &len)
{
for (int i = 0; i < 3; i++) // 遍历行
{
for (int j = 0; j < 3; j++) // 遍历列
{
if (arr[i][j] != 0) // 如果当前元素不为零
{
t[len].row = i; // 将行索引存入三元组
t[len].col = j; // 将列索引存入三元组
t[len].value = arr[i][j]; // 将非零值存入三元组
len++; // 增加三元组的计数
}
}
}
}
// 将三元组恢复成稀疏数组
void TripleToArr(int arr[][3], Triple t, int len)
{
for (int i = 0; i < len; i++) // 遍历三元组
{
arr[t[i].row][t[i].col] = t[i].value; // 根据三元组信息重建稀疏数组
}
}
// 打印二维数组
void Print(int arr[][3])
{
for (int i = 0; i < 3; i++) // 遍历行
{
for (int j = 0; j < 3; j++) // 遍历列
{
cout << arr[i][j] << '\t'; // 打印数组元素并用制表符分隔
}
cout << endl; // 打印完一行后换行
}
}
int main()
{
int arr[3][3] = {{1, 0, 0}, {4, 0, 6}, {0, 8, 0}}; // 定义稀疏矩阵
Triple t; // 创建三元组数组
int len = 0; // 三元组的计数初始化为0
int new_arr[3][3] = {0}; // 初始化恢复后的数组为全零
ArrToTriple(arr, t, len); // 将稀疏矩阵转换为三元组
TripleToArr(new_arr, t, len); // 将三元组恢复为稀疏矩阵
Print(new_arr); // 打印恢复后的稀疏矩阵
}（5）题目：二维数组Q按列存储
解题思路：
实现代码：
代码语言：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[j][i]; // 将二维数组按列存入一维数组
}
}
}
// 按照索引从一维数组取值
int OneDimIndex(int *array, int i, int j)
{
return array[(j - 1) * 3 + i - 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()
{
int arr[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // 定义一个3x3的二维数组
int array[9]; // 定义一个一维数组用于存储转换后的元素
PrintTwoDim(arr, 3, 3); // 打印原始的二维数组
TwoMapOneDim(arr, array, 3, 3); // 将二维数组按列存储到一维数组
PrintOneDim(array, 9); // 打印存储的结果的一维数组
cout << OneDimIndex(array, 3, 2); // 输出从一维数组中取出的特定元素
}本文标签： 2024重生之回溯数据结构与算法系列学习（10）无论是王道考研人还是IKUN都能包会的不然别给我家鸽鸽丢脸好嘛
版权声明：本文标题：2024重生之回溯数据结构与算法系列学习（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754674458a1705050.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论