2024重生之回溯数据结构与算法系列学习（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 

专栏跑道一
 ➡️ 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); // 输出从一维数组中取出的特定元素
}