文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >2024重生之回溯数据结构与算法系列学习（5）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】

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

作者头像
盛透侧视攻城狮
发布于 2024-12-25 09:34:13
发布于 2024-12-25 09:34:13
2280
举报
文章被收录于专栏：超前沿网络空间安全全栈学习宝典超前沿网络空间安全全栈学习宝典

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

解题思路：

代码语言：javascript
复制
>KMP字符串比较算法

实现代码：

代码语言：javascript
复制
#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;         // 将头节点的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为新节点
        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; // 输出换行
}

// 判断链表LB是否为链表LA的子序列
void SubNode(LinkList &LA, LinkList &LB)
{
    LNode *p, *q, *pre; // LA、LB的工作节点和前一个节点
    p = LA->next; // p指向LA的第一个节点
    q = LB->next; // q指向LB的第一个节点
    pre = p;      // pre指向p的初始位置

    while (p && q)
    {
        // 如果两个节点的值相等，继续比较下一个节点
        if (p->data == q->data)
        {
            p = p->next; // 移动p指针
            q = q->next; // 移动q指针
        }
        // 如果不相等，pre向后移动一位，q重新开始
        else
        {
            pre = pre->next; // pre指向下一个节点
            p = pre;         // 更新p指针
            q = LB->next;    // 重新开始比较LB的链表
        }
    }

    // 如果q没有到达链表尾部，说明LB不是LA的子序列
    if (q)
    {
        cout << "B不是A的子序列" << endl;
        return; // 结束函数
    }

    // 如果q到达链表尾部，说明LB是LA的子序列
    cout << "B是A的子序列" << endl;
}

// 主函数
int main()
{
    LinkList LA = new LNode; // 创建链表A的头节点
    LinkList LB = new LNode; // 创建链表B的头节点

    // 通过尾插法输入链表元素
    TailInsert(LA);
    TailInsert(LB);

    // 判断LB是否为LA的子序列
    SubNode(LA, LB);

    return 0; // 程序结束
}

（17）题目：设计一个算法用于判断带头结点的循环双链表是否对称

解题思路：

代码语言：javascript
复制
>定义两个工作指针，一个从前向后扫描
>一个从后向前扫描

实现代码：

代码语言：javascript
复制
#include <iostream>
using namespace std;

// 定义双向循环链表的节点结构体
typedef struct LNode
{
    int data;              // 节点存储的数据
    struct LNode *prior;  // 指向前驱节点的指针
    struct LNode *next;   // 指向后继节点的指针
} LNode, *LinkList; // LinkList为指向LNode的指针类型

// 尾插法插入节点
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; // 结束输入
        }
    }

    // 形成循环链表，将新尾节点的next指向头节点L
    r->next = L;             // 尾节点指向头节点
    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指向头节点的下一个，q指向头节点的前驱
    p = L->next;  // p指向第一个数据节点
    q = L->prior; // q指向最后一个数据节点

    // 当p和q未重合时继续判断
    while (p != q)
    {
        // 偶数元素情况
        if (p->next == q && p->data == q->data)
        {
            cout << "该循环链表对称" << endl; // 若p和q相遇且数据相等
            return; // 返回
        }

        // 奇数情况
        if (p->data != q->data)
        {
            cout << "该循环链表不对称" << endl; // 若数据不相等，链表不对称
            return; // 返回
        }
        else
        {
            p = p->next; // p向后移动一位
            q = q->prior; // q向前移动一位
        }
    }
    cout << "该循环链表对称" << endl; // 若p和q重合，链表对称
}

// 主函数
int main()
{
    LinkList L = new LNode; // 创建一个链表的头节点

    TailInsert(L); // 通过尾插法插入节点
    Print(L);      // 打印链表中的元素

    JudgeSymmetry(L); // 判断链表是否对称
}

（18）题目：有两个循环单链表，链表头指针分别为h1 和 h2，编写一个函数将链表 h2 链接到链表h1 之后,要求链接后的链表仍保持循环链表形式.

解题思路：

代码语言：javascript
复制
>问题关键就是找到两个链表的尾指针
>然后修改指针指向

实现代码：

代码语言：javascript
复制
#include <iostream>
using namespace std;

// 定义链表节点结构体
typedef struct LNode
{
    int data;              // 节点存储的数据
    struct LNode *next;   // 指向下一个节点的指针
} LNode, *LinkList; // LinkList为指向LNode的指针类型

// 尾插法插入节点
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;             // 尾节点指向头节点，形成循环链表
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != L)      // 当未回到头节点时继续
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}

// 连接两个循环链表
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 = pa->next; // 移动pa指针
    }

    // 找到LB的尾指针
    while (pb->next != LB) // 当pb未到达尾节点时
    {
        pb = pb->next; // 移动pb指针
    }

    // 修改指针指向
    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中的元素
}

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

解题思路：

代码语言：javascript
复制
>定义几个工作指针
>每次遍历找到最小值将其删除
>直到表为空

实现代码：

代码语言：javascript
复制
#include <iostream>
using namespace std;

// 定义链表节点结构体
typedef struct LNode
{
    int data;              // 节点存储的数据
    struct LNode *next;   // 指向下一个节点的指针
} LNode, *LinkList; // LinkList为指向LNode的指针类型

// 尾插法插入节点
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;             // 尾节点指向头节点，形成循环链表
}

// 遍历输出链表元素
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); // 删除链表中的最小值
}

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

解题思路：

代码语言：javascript
复制
>不要被其复杂度吓到了；其实也就那样；freq 就是查找+1嘛然后按序递减

>双链表的插入、删除

实现代码：

代码语言：javascript
复制
#include <iostream>
using namespace std;

// 定义链表节点结构体
typedef struct LNode
{
    int data;              // 节点存储的数据
    int freq = 0;         // 节点访问频率
    struct LNode *pred;   // 指向前驱节点的指针
    struct LNode *next;   // 指向后继节点的指针
} LNode, *LinkList; // LinkList为指向LNode的指针类型

// 尾插法插入节点
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->pred = r;         // 设置新节点的前驱为当前尾节点
        r = s;               // 更新r为新节点

        // 如果遇到换行，停止输入
        if (cin.get() == '\n')
        {
            break; // 结束输入
        }
    }

    r->next = L;             // 尾节点指向头节点，形成循环链表
    L->pred = r;             // 头节点的前驱指向尾节点
}

// 遍历输出链表元素
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; // 从头节点的下一个节点开始查找

    // 查找数据为x的节点
    while (p && p->data != x)
    {
        p = p->next; // 移动到下一个节点
    }

    if (!p) // 如果未找到，返回NULL
    {
        return NULL;
    }
    else
    {
        p->freq++; // 找到节点，增加访问频率
        // 如果当前节点是头节点的下一个节点，或者其前驱的频率大于当前频率
        if (p->pred == L || p->pred->freq > p->freq)
        {
            return p; // 返回当前节点
        }

        // 如果有后继节点，更新其前驱
        if (p->next != NULL)
        {
            p->next->pred = p->pred; // 更新后继节点的前驱指向当前节点的前驱
        }
        p->pred->next = p->next; // 更新前驱节点的后继指向当前节点的后继
        q = p->pred; // q指向当前节点的前驱

        // 在前驱节点中寻找合适的位置插入当前节点
        while (q != L && q->freq <= p->freq)
        {
            q = q->pred; // 向前遍历，寻找更高频率的节点
        }
        // 插入当前节点到新位置
        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的节点
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-12-25，如有侵权请联系 cloudcommunity@tencent.com 删除
数据结构与算法
指针
遍历
链表
数据

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数据结构与算法
指针
遍历
链表
数据
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • （16）题目：两个整数序列A= ay,a2, a3, , am和B=b, b2, b3, , b,已经存入两个单链表中,设计一个算法，判断序列B是否是序列A的连续子序列。
    • 解题思路：
    • 实现代码：
  • （17）题目：设计一个算法用于判断带头结点的循环双链表是否对称
    • 解题思路：
    • 实现代码：
  • （18）题目：有两个循环单链表，链表头指针分别为h1 和 h2，编写一个函数将链表 h2 链接到链表h1 之后,要求链接后的链表仍保持循环链表形式.
    • 解题思路：
    • 实现代码：
  • （19）题目：设有一个带头结点的循环单链表,其结点值均为正整数。设计一个算法,反复找出单链表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止,再删除表头灶占
    • 解题思路：
    • 实现代码：
  • （20）题目：设头指针为L的带有表头结点的非循环双向链表,其每个结点中除有pred(前驱指针).data （数据)和 next （后继指针)域外,还有一个访问频度域freq.在链表被启用前，其值均初始化为零。每当在链表中进行一次 Locate (L,x)运算时，令元素值为的结点中freq域的值增1,并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点前面，以使使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate (L,x)运算的算法,该运算为函数过程,返回找到结点的地址，类型为指针型。
    • 解题思路：
    • 实现代码：
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论