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

 

相关文章
|
12天前
|
算法 Java
算法系列之回溯算法
回溯算法(Backtracking Algorithm)是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,遇到正确解将其记录,直到找到了所有的解或者尝试了所有的可能为止。
26 4
算法系列之回溯算法
|
2月前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
69 7
|
2月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
80 5
|
2月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
68 5
|
4月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
4月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
5月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
135 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
5月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
108 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
5月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
64 0
数据结构与算法学习十四:常用排序算法总结和对比
|
5月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
68 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题

热门文章

最新文章