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

本文涉及的产品
视觉智能开放平台,分割抠图1万点
视觉智能开放平台,图像通用资源包5000点
视觉智能开放平台,视频通用资源包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

 

相关文章
|
1月前
|
机器学习/深度学习 算法 C++
【DFS/回溯算法】2016年蓝桥杯真题之路径之谜详解
题目要求根据城堡北墙和西墙箭靶上的箭数,推断骑士从西北角到东南角的唯一路径。每步移动时向正北和正西各射一箭,同一格不重复经过。通过DFS回溯模拟“拔箭”过程,验证路径合法性。已知箭数约束路径唯一,最终按编号输出行走顺序。
|
3月前
|
机器学习/深度学习 算法 数据挖掘
没发论文的注意啦!重磅更新!GWO-BP-AdaBoost预测!灰狼优化、人工神经网络与AdaBoost集成学习算法预测研究(Matlab代码实现)
没发论文的注意啦!重磅更新!GWO-BP-AdaBoost预测!灰狼优化、人工神经网络与AdaBoost集成学习算法预测研究(Matlab代码实现)
151 0
|
3月前
|
算法
回溯算法的基本思想
本节介绍回溯算法,通过图1中从A到K的路径查找示例,说明其与穷举法的异同。回溯算法通过“回退”机制高效试探各种路径,适用于决策、优化和枚举问题。
112 0
|
2月前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
207 1
|
4月前
|
存储 缓存 算法
什么是回溯算法
回溯算法是一种通过尝试所有可能路径寻找问题解的策略,采用深度优先搜索与状态重置机制。它适用于组合、排列、棋盘等需枚举所有可能解的问题,核心思想包括DFS遍历、剪枝优化与状态恢复。尽管时间复杂度较高,但通过合理剪枝可显著提升效率,是解决复杂搜索问题的重要方法。
236 0
|
8月前
|
算法 数据可视化 开发者
为什么要学习数据结构与算法
今天,我向大家介绍一门非常重要的课程——《数据结构与算法》。这门课不仅是计算机学科的核心,更是每一位开发者从“小白”迈向“高手”的必经之路。
为什么要学习数据结构与算法
|
8月前
|
算法 Java
算法系列之回溯算法求解数独及所有可能解
数独求解的核心算法是回溯算法。回溯算法是一种通过逐步构建解决方案并在遇到冲突时回退的算法。具体来说,我们尝试在空格中填入一个数字,然后递归地继续填充下一个空格。如果在某个步骤中发现无法继续填充,则回退到上一步并尝试其他数字。
340 11
算法系列之回溯算法求解数独及所有可能解
|
9月前
|
算法 Java
算法系列之回溯算法
回溯算法(Backtracking Algorithm)是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,遇到正确解将其记录,直到找到了所有的解或者尝试了所有的可能为止。
324 4
算法系列之回溯算法
|
10月前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
2242 11
架构学习:7种负载均衡算法策略
|
10月前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
309 7

热门文章

最新文章