欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
回溯数据结构与算法系列学习之栈和队列精题汇总
（1）题目：设计一个递归算法，删除不带头结点的单链表L 中所有值为 x 的结点。
解题思路：
>利用递归，不断将节点的下个节点传入函数 >每个函数执行对应删除操作
实现代码：
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
实现代码：
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++完整实现（可直接运行）
解题思路：
>遇到左括号将其压入栈中 >当遇到右括号，则判断此时栈是否为空 >如果是空栈，则不匹配 >如果非空，则弹出栈顶元素，与当前右括号进行匹配 >如果不对应，则不匹配 >最后，如果栈为空，则表示括号匹配 >不空表示有多余括号，则不匹配
实现代码：
using namespace std; // 定义栈的最大容量 // 定义栈结构 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利用三元组存储
解题思路：
编辑
实现代码：
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按列存储
解题思路： 
实现代码：
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); // 输出从一维数组中取出的特定元素 }
