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

 

相关文章
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
137 9
|
25天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
12天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
30 5
|
28天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
50 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
39 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10

热门文章

最新文章