欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色
专栏跑道一
➡️ MYSQL REDIS Advance operation
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道四
➡️RHCE-LJS[Linux高端骚骚操作实战篇]
专栏跑道五
➡️数据结构与算法[考研+实际工作应用+C程序设计]
上节回顾
https://netsecur-cloud-ljs.blog.csdn.net/article/details/142568658
目录
欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
专栏跑道一 ➡️ MYSQL REDIS Advance operation
专栏跑道二➡️ 24 Network Security -LJS
专栏跑道三
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道四➡️RHCE-LJS[Linux高端骚骚操作实战篇]编辑
专栏跑道五
➡️数据结构与算法[考研+实际工作应用+C程序设计]
上节回顾https://netsecur-cloud-ljs.blog.csdn.net/article/details/142568658
溯数据结构与算法系列学习之栈和队列精题汇总
（1）题目：设计一个递归算法，删除不带头结点的单链表L 中所有值为 x 的结点。
解题思路：
实现代码：
（2）题目：通过C++实现链栈Q ChainStack
实现代码：
运行截图：
（3）题目：栈的应用Q——实现括号匹配利用栈实现括号匹配C、C++完整实现（可直接运行）
解题思路：
实现代码：
（4）题目：稀疏 数组Q利用三元组存储
解题思路：
实现代码：
（5）题目：二维数组Q按列存储
解题思路：编辑
实现代码：
溯数据结构与算法系列学习之栈和队列精题汇总
（1）题目：设计一个递归算法，删除不带头结点的单链表L 中所有值为 x 的结点。
解题思路：
>利用递归，不断将节点的下个节点传入函数>每个函数执行对应删除操作实现代码：
#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; // 新节点的下一个指针设为NULLif (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; // 用于保存待删除的节点// 如果头节点的值等于 xif (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
实现代码：
#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; // 栈顶节点的下一个指针初始化为nullptrs->size = 0; // 初始化栈大小为0return s; // 返回初始化好的链栈 }int main() {ChainStack *s = InitStack(); // 初始化链栈Push(*s, 5); // 压入元素5Push(*s, 4); // 压入元素4Push(*s, 3); // 压入元素3Push(*s, 2); // 压入元素2cout << GetSize(*s) << endl; // 输出栈的大小cout << GetTop(*s) << endl; // 输出栈顶元素Pop(*s); // 弹出栈顶元素cout << GetTop(*s) << endl; // 再次输出栈顶元素 }运行截图：
（3）题目：栈的应用Q——实现括号匹配利用栈实现括号匹配C、C++完整实现（可直接运行）
解题思路：
>遇到左括号将其压入栈中>当遇到右括号，则判断此时栈是否为空>如果是空栈，则不匹配>如果非空，则弹出栈顶元素，与当前右括号进行匹配>如果不对应，则不匹配>最后，如果栈为空，则表示括号匹配>不空表示有多余括号，则不匹配实现代码：
#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利用三元组存储
解题思路：
实现代码：
#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; // 三元组的计数初始化为0int new_arr[3][3] = {0}; // 初始化恢复后的数组为全零ArrToTriple(arr, t, len); // 将稀疏矩阵转换为三元组TripleToArr(new_arr, t, len); // 将三元组恢复为稀疏矩阵Print(new_arr); // 打印恢复后的稀疏矩阵 }
（5）题目：二维数组Q按列存储
解题思路：
实现代码：
#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); // 输出从一维数组中取出的特定元素 }
