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

本文涉及的产品
视觉智能开放平台,图像资源包5000点
视觉智能开放平台,分割抠图1万点
视觉智能开放平台,视频资源包5000点
简介: IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、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

上节回顾





 目录

王道第2.3章节之线性表精题汇总二

(16)题目:两个整数序列A= ay, a2, a3, , am和B= b, b2, b3, , b,已经存入两个单链表中,设计一个算法,判断序列 B 是否是序列 A 的连续子序列。编辑

解题思路:

实现代码:

(17)题目:设计一个算法用于判断带头结点的循环双 链表Q是否对称。编辑

解题思路:

实现代码:

(18)题目:有两个循环 单链表Q,链表头指针分别为h1和h2,编写一个函数将链表h2链接到链表h1之后,要求链接后的链表仍保持循环链表形式。

解题思路:

实现代码:

(19)题目:设有一个带头结点的循环单链表Q,其结点值均为正整数,设计一个算法,反复找出单链表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止,再删除表头结点。

解题思路:

实现代码:

(20)题目:设头指针为L的带有表头结点的非循环双向链表,其每个结点中除有pred(前驱指针)、data(数据)和 next(后继指针)城外,还有一个访问频度域 freq。在链表被启用前,其值均初始化为零。每当在链表中进行一次Locate (L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非增(递减)的顺序排列,同时最近访问的结点排在频度相同的结点前面,以使使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate (L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。

解题思路:

实现代码:


(16)题目:两个整数序列A= ay, a2, a3, , am和B= b, b2, b3, , b,已经存入两个单链表中,设计一个算法,判断序列 B 是否是序列 A 的连续子序列。 image.gif 编辑

解题思路:

>KMP字符串比较算法
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义链表节点结构体
typedef struct LNode
{
    int data;          // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList;
// 头插法
void HeadInsert(LinkList &L)
{
    int val = 0;
    while (cin >> val) // 从标准输入读取整数值
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        s->next = L->next;   // 将新节点的next指向当前链表的第一个节点
        L->next = s;         // 将头节点的next指向新节点
        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;         // 尾节点的next指向新节点
        r = s;               // 更新尾节点为新节点
        r->next = NULL;      // 新节点的next指针为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; // 输出换行
}
// 判断链表B是否是链表A的子序列
void SubNode(LinkList &LA, LinkList &LB)
{
    LNode *p, *q, *pre; // LA、LB的工作结点,和每次开始的比较结点
    p = LA->next; // A链表的第一个节点
    q = LB->next; // B链表的第一个节点
    pre = p;      // pre用于记录当前匹配的位置
    while (p && q) // 当A和B都未遍历完时
    {
        // 如果二者相等,指针后移继续匹配
        if (p->data == q->data)
        {
            p = p->next; // A链表指针后移
            q = q->next; // B链表指针后移
        }
        // 不等,将pre开始指针向后偏移一位,q重新开始
        else
        {
            pre = pre->next; // pre后移
            p = pre;         // p指向pre
            q = LB->next;    // q重新指向B链表的头
        }
    }
    // 检查B链表是否完全遍历
    if (q)
    {
        cout << "B不是A的子序列" << endl; // 如果q没有遍历完,说明B不是A的子序列
        return;
    }
    cout << "B是A的子序列" << endl; // 如果q遍历完了,说明B是A的子序列
}
int main()
{
    LinkList LA = new LNode; // 创建链表A的头节点
    LinkList LB = new LNode; // 创建链表B的头节点
    TailInsert(LA); // 插入链表A的元素
    TailInsert(LB); // 插入链表B的元素
    SubNode(LA, LB); // 判断链表B是否是链表A的子序列
}
image.gif

(17)题目:设计一个算法用于判断带头结点的循环双 链表Q是否对称。 image.gif 编辑

解题思路:

>定义两个工作指针,一个从前向后扫描
>一个从后向前扫描
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义双向链表节点结构体
typedef struct LNode
{
    int data;                // 节点数据
    struct LNode *prior;    // 指向前一个节点的指针
    struct LNode *next;     // 指向下一个节点的指针
} LNode, *LinkList;
// 尾插法
void TailInsert(LinkList &L)
{
    int val = 0; // 用于存储输入的值
    LNode *r = L; // r指向链表的尾部
    while (cin >> val) // 从标准输入读取整数值
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 当前尾节点的next指向新节点
        s->prior = r;        // 新节点的prior指向当前尾节点
        r = s;               // 更新r为新节点
        if (cin.get() == '\n') // 如果输入回车,则结束输入
        {
            break;
        }
    }
    // 建立循环关系
    r->next = L; // 尾节点的next指向头节点
    L->prior = r; // 头节点的prior指向尾节点
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从链表第一个节点开始
    while (p != L) // 当未到达头节点时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 判断循环链表是否对称
void JudgeSymmetry(LinkList &L)
{
    LNode *p, *q; // 定义工作结点,分别保存对应的前驱和后继
    p = L->next; // p指向链表的第一个节点
    q = L->prior; // q指向链表的最后一个节点
    // 二者不重合继续判断
    while (p != q)
    {
        // 偶数元素情况
        if (p->next == q && p->data == q->data)
        {
            cout << "该循环链表对称" << endl;
            return; // 找到对称,返回
        }
        // 奇数情况
        if (p->data != q->data)
        {
            cout << "该循环链表不对称" << endl;
            return; // 找到不对称,返回
        }
        else
        {
            p = p->next; // p指向下一个节点
            q = q->prior; // q指向前一个节点
        }
    }
    cout << "该循环链表对称" << endl; // 如果所有节点都匹配,说明对称
}
int main()
{
    LinkList L = new LNode; // 创建链表的头节点
    TailInsert(L); // 尾插法插入节点
    Print(L); // 打印链表
    JudgeSymmetry(L); // 判断链表是否对称
}
image.gif

(18)题目:有两个循环 单链表Q,链表头指针分别为h1和h2,编写一个函数将链表h2链接到链表h1之后,要求链接后的链表仍保持循环链表形式。

image.gif 编辑

解题思路:

>问题关键就是找到两个链表的尾指针
>然后修改指针指向
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义单向链表节点结构体
typedef struct LNode
{
    int data;               // 节点数据
    struct LNode *next;    // 指向下一个节点的指针
} LNode, *LinkList;
// 尾插法插入节点
void TailInsert(LinkList &L)
{
    int val = 0;           // 用于存储输入的值
    LNode *r = L;         // r指向链表的尾部
    while (cin >> val)    // 从标准输入读取整数值
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 当前尾节点的next指向新节点
        r = s;               // 更新r为新节点
        if (cin.get() == '\n') // 如果输入回车,则结束输入
        {
            break;
        }
    }
    r->next = L; // 尾节点的next指向头节点,形成循环链表
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从链表第一个节点开始
    while (p != L)      // 当未到达头节点时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 连接两个循环链表 LA 和 LB
void ConnectList(LinkList &LA, LinkList &LB)
{
    LNode *pa, *pb; // 定义两个工作指针
    pa = LA->next; // pa 指向链表 LA 的第一个节点
    pb = LB->next; // pb 指向链表 LB 的第一个节点
    // 找到 LA 的尾指针
    while (pa->next != LA) // 遍历直到找到尾节点
    {
        pa = pa->next; // 移动到下一个节点
    }
    // 找到 LB 的尾指针
    while (pb->next != LB) // 遍历直到找到尾节点
    {
        pb = pb->next; // 移动到下一个节点
    }
    // 修改指针指向以连接两个链表
    pa->next = LB->next; // 将 LA 的尾节点连接到 LB 的第一个节点
    pb->next = LA;       // 将 LB 的尾节点连接到 LA
}
int main()
{
    LinkList LA = new LNode; // 创建链表 LA 的头节点
    LinkList LB = new LNode; // 创建链表 LB 的头节点
    TailInsert(LA); // 调用尾插法插入节点到 LA
    TailInsert(LB); // 调用尾插法插入节点到 LB
    ConnectList(LA, LB); // 连接两个链表 LA 和 LB
    Print(LA); // 打印连接后的链表 LA
}
image.gif

(19)题目:设有一个带头结点的循环单链表Q,其结点值均为正整数,设计一个算法,反复找出单链表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止,再删除表头结点。

image.gif 编辑

解题思路:

>定义几个工作指针
>每次遍历找到最小值将其删除
>直到表为空
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义单向链表节点结构体
typedef struct LNode
{
    int data;               // 节点数据
    struct LNode *next;    // 指向下一个节点的指针
} LNode, *LinkList;
// 尾插法插入节点
void TailInsert(LinkList &L)
{
    int val = 0;           // 用于存储输入的值
    LNode *r = L;         // r指向链表的尾部(初始为头节点)
    
    // 循环读取整数值
    while (cin >> val) 
    {
        LNode *s = new LNode; // 创建新节点
        s->data = val;        // 设置节点数据
        r->next = s;         // 当前尾节点的 next 指向新节点
        r = s;               // 更新 r 为新节点
        // 如果输入回车,则结束输入
        if (cin.get() == '\n') 
        {
            break;
        }
    }
    r->next = L; // 尾节点的 next 指向头节点,形成循环链表
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从链表第一个节点开始
    while (p != L)      // 当未到达头节点时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 删除链表中最小值节点
void DelValue(LinkList &L)
{
    LNode *p, *pre, *minP, *minPre; // 定义工作节点和保存最小值及其前驱的指针
    // 只要链表不为空就搜索最小值
    while (L->next != L) 
    {
        // 重置指针
        p = minP = L->next; // p 和 minP 指向链表的第一个节点
        pre = minPre = L;   // pre 和 minPre 初始化为头节点
        // 遍历链表查找最小值
        while (p != L) 
        {
            if (p->data < minP->data) // 如果当前节点数据小于当前最小值
            {
                minP = p;            // 更新最小值节点
                minPre = pre;        // 更新最小值节点的前驱
            }
            pre = p;                   // 移动前驱指针
            p = p->next;              // 移动到下一个节点
        }
        cout << minP->data << '\t'; // 输出最小值
        minPre->next = minP->next; // 删除最小值节点
        delete minP;               // 释放内存
    }
    delete L; // 删除头节点
}
int main()
{
    LinkList L = new LNode; // 创建链表的头节点
    TailInsert(L); // 调用尾插法插入节点
    DelValue(L);   // 删除链表中的所有最小值节点
}
image.gif

(20)题目:设头指针为L的带有表头结点的非循环双向链表,其每个结点中除有pred(前驱指针)、data(数据)和 next(后继指针)城外,还有一个访问频度域 freq。在链表被启用前,其值均初始化为零。每当在链表中进行一次Locate (L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非增(递减)的顺序排列,同时最近访问的结点排在频度相同的结点前面,以使使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate (L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。

image.gif 编辑

解题思路:

>双链表的插入、删除
image.gif

实现代码:

#include <iostream>
using namespace std;
// 定义链表节点结构
typedef struct LNode
{
    int data;              // 节点数据
    int freq = 0;         // 节点频率,默认值为0
    struct LNode *pred;   // 前驱指针
    struct LNode *next;   // 后继指针
} LNode, *LinkList;
// 尾插法插入节点
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指向新节点
        if (cin.get() == '\n') // 如果读取到换行符,结束输入
        {
            break;
        }
    }
    r->next = L;           // 形成循环链表
}
// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next;   // 从第一个有效节点开始
    while (p != L)        // 当未回到头节点时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;          // 移动到下一个节点
    }
    cout << endl;          // 输出换行
}
// 定位节点并更新频率
LNode *Locate(LinkList &L, int x)
{
    LNode *p, *q;
    p = L->next;         // 从第一个有效节点开始
    while (p && p->data != x) // 查找数据为x的节点
    {
        p = p->next;
    }
    if (!p)              // 如果没有找到,返回NULL
    {
        return NULL;
    }
    else
    {
        p->freq++;       // 找到节点,频率加1
        // 如果该节点在链表头或前驱频率更大,直接返回
        if (p->pred == L || p->pred->freq > p->freq)
        {
            return p;
        }
        // 断开p节点与其前驱的链接
        if (p->next != NULL)
        {
            p->next->pred = p->pred;
        }
        p->pred->next = p->next;
        // 在前驱节点中寻找合适的位置插入p节点
        q = p->pred;
        while (q != L && q->freq <= p->freq)
        {
            q = q->pred;
        }
        // 更新p的前驱和后继指针
        p->next = q->next;
        if (q->next != NULL)
        {
            q->next->pred = p;
        }
        p->pred = q;
        q->next = p;
    }
    return p;            // 返回更新后的节点
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    TailInsert(L);         // 尾插法插入节点
    LNode *p = Locate(L, 3); // 定位值为3的节点
}
image.gif

 

相关文章
|
10天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
10天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
2天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
3天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
4天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
3天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。
|
3天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
18 3
|
14天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
15天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。

热门文章

最新文章

下一篇
无影云桌面