2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】

本文涉及的产品
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,分割抠图1万点
视觉智能开放平台,图像资源包5000点
简介: 数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!

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

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

image.gif

专栏跑道二

➡️ 24 Network Security -LJS

image.gif

image.gif

image.gif

专栏跑道三


➡️ MYSQL REDIS Advance operation

image.gif

专栏跑道四

➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

image.gif

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

image.png

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

image.gif

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

image.gif

image.gif

上节回顾







回溯数据结构与算法系列学习之栈和队列精题汇总

(1)题目:设计一个递归算法,删除不带头结点的单链表L 中所有值为 x 的结点。

解题思路:

>利用递归,不断将节点的下个节点传入函数
>每个函数执行对应删除操作
image.gif

实现代码:

#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); // 打印链表中的节点
}
image.gif

image.gif 编辑

(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; // 栈顶节点的下一个指针初始化为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; // 再次输出栈顶元素
}
image.gif

运行截图:

image.gif 编辑

(3)题目:栈的应用Q——实现括号匹配利用栈实现括号匹配C、C++完整实现(可直接运行)

解题思路:

>遇到左括号将其压入栈中
>当遇到右括号,则判断此时栈是否为空
>如果是空栈,则不匹配
>如果非空,则弹出栈顶元素,与当前右括号进行匹配
>如果不对应,则不匹配
>最后,如果栈为空,则表示括号匹配
>不空表示有多余括号,则不匹配
image.gif

实现代码:

#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); // 调用括号匹配函数
}
image.gif

(4)题目:稀疏 数组Q利用三元组存储

解题思路:

image.gif 编辑

实现代码:

#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); // 打印恢复后的稀疏矩阵
}
image.gif

(5)题目:二维数组Q按列存储

解题思路: image.gif

实现代码:

#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); // 输出从一维数组中取出的特定元素
}
image.gif


相关文章
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
14天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
1天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
|
1天前
|
机器学习/深度学习 算法 信息无障碍
基于GoogleNet深度学习网络的手语识别算法matlab仿真
本项目展示了基于GoogleNet的深度学习手语识别算法,使用Matlab2022a实现。通过卷积神经网络(CNN)识别手语手势,如&quot;How are you&quot;、&quot;I am fine&quot;、&quot;I love you&quot;等。核心在于Inception模块,通过多尺度处理和1x1卷积减少计算量,提高效率。项目附带完整代码及操作视频。
|
10天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
7天前
|
算法
基于WOA鲸鱼优化的购售电收益与风险评估算法matlab仿真
本研究提出了一种基于鲸鱼优化算法(WOA)的购售电收益与风险评估算法。通过将售电公司购售电收益风险计算公式作为WOA的目标函数,经过迭代优化计算出最优购电策略。实验结果表明,在迭代次数超过10次后,风险价值收益优化值达到1715.1万元的最大值。WOA还确定了中长期市场、现货市场及可再生能源等不同市场的最优购电量,验证了算法的有效性。核心程序使用MATLAB2022a实现,通过多次迭代优化,实现了售电公司收益最大化和风险最小化的目标。
|
11天前
|
算法
通过matlab分别对比PSO,反向学习PSO,多策略改进反向学习PSO三种优化算法
本项目使用MATLAB2022A版本,对比分析了PSO、反向学习PSO及多策略改进反向学习PSO三种优化算法的性能,主要通过优化收敛曲线进行直观展示。核心代码实现了标准PSO算法流程,加入反向学习机制及多种改进策略,以提升算法跳出局部最优的能力,增强全局搜索效率。

热门文章

最新文章