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

本文涉及的产品
视觉智能开放平台,分割抠图1万点
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,图像资源包5000点
简介: 数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、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章节之线性表精题汇总四

(6)题目:试编写算法将带头节点的单链表Q就地逆置,所谓“就地”是指辅助空间复杂度为0(1)。

解题思路:

链表节点结构体 (LNode):
data 用于存储节点的数据。
next 是一个指针,用于指向下一个节点。
头插法 (HeadInsert):
通过不断读取输入,将新节点插入到链表的头部。
使用 L->next 来维护链表的结构。
尾插法 (TailInsert):
持续读取输入,将新节点追加到链表末尾。
r 用于跟踪当前尾部节点,更新尾部指针。
打印函数 (Print):
遍历链表,从头节点开始输出每个节点的数据。
反转链表 (fn):
将链表中的节点顺序反转。
使用三个指针:p 用于当前节点,r 用于暂存下一个节点,L->next 用于构建反转后的链表。
主函数 (main):
创建链表头节点,调用 TailInsert 进行数据插入,然后调用 fn 反转链表,最后输出反转后的链表。
  • 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;   // 新节点指向当前链表的第一个节点
        L->next = s;         // 更新头指针,指向新节点
        // 判断是否为输入结束
        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; // 输出换行
}
// 反转链表
void fn(LinkList &L)
{
    LNode *p, *r;
    p = L->next; // 从链表的第一个节点开始
    L->next = NULL; // 清空链表
    // 反转链表
    while (p)
    {
        r = p->next; // 暂存当前节点的下一个节点
        p->next = L->next; // 当前节点的next指向新的头节点
        L->next = p; // 更新链表头,指向当前节点
        p = r; // 移动到下一个节点
    }
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    TailInsert(L); // 调用尾插法插入数据
    fn(L); // 反转链表
    Print(L); // 打印链表
}
  • image.gif

(7)题目:设在一个带表头节点的 单链表Q中所有元素节点的数据值无序,试编写一个函数,删除表中所有介于给定的两个值(作为函数参数给出)之间的元素的元素(若存在) 。

解题思路:

>定义工作指针p、前驱指针q
>遍历链表删除节点
链表节点结构体 (LNode):
data:用于存储节点的数据。
next:指向下一个节点的指针。
头插法 (HeadInsert):
通过不断读取输入,将新节点插入到链表的头部。
使用 L->next 来维护链表的结构。
尾插法 (TailInsert):
持续读取输入,将新节点追加到链表末尾。
r 用于跟踪当前尾部节点,更新尾部指针。
打印函数 (Print):
遍历链表,从头节点开始输出每个节点的数据。
删除指定范围内的节点 (DelValue):
该函数用于删除链表中数据值在 left 和 right 之间的所有节点。
使用两个指针 p 和 pre 来维护当前节点和前驱节点,判断并删除符合条件的节点。
主函数 (main):
  • 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;   // 新节点指向当前链表的第一个节点
        L->next = s;         // 更新头指针,指向新节点
        // 判断是否为输入结束
        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; // 输出换行
}
// 删除指定范围内的节点
void DelValue(LinkList &L, int left, int right)
{
    LNode *p, *pre; // p用于当前节点,pre用于前驱节点
    p = L->next; // 从链表的第一个节点开始
    pre = L; // pre初始化为头节点
    while (p) // 当当前节点不为空时循环
    {
        // 检查节点数据是否在指定范围内
        if (p->data > left && p->data < right)
        {
            LNode *q = p; // 暂存待删除节点
            p = p->next; // 移动到下一个节点
            pre->next = p; // 前驱节点的next指向当前节点的下一个节点
            delete q; // 删除旧节点,释放内存
        }
        else // 若不在指定范围内
        {
            pre = p; // 更新前驱节点
            p = p->next; // 移动到下一个节点
        }
    }
}
int main()
{
    LinkList L = new LNode; // 创建链表头节点
    TailInsert(L); // 调用尾插法插入数据
    DelValue(L, 3, 5); // 删除数据在3和5之间的节点
    Print(L); // 打印链表
}
  • image.gif

(8)题目:给定两个单链表Q,编写算法找出两个链表的公共结点。

解题思路:

>公共结点之后的所有结点地址均一致
>所以只需要比较结点即可
>但是需要二者从同一倒数长度开始
>所以长的链表需要先向后偏移链表长度之差
链表结构: 使用 LNode 结构体定义链表节点,包括数据和指向下一个节点的指针。
链表操作:
HeadInsert: 使用头插法插入数据。
TailInsert: 使用尾插法插入数据。
Print: 输出链表中所有节点的数据。
PublicNode: 查找两个链表的公共节点,并输出该节点的数据。
主函数: 创建两个链表,构建公共节点,并调用 PublicNode 函数查找和打印公共节点的数据。

实现代码:

#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;   // 新节点指向当前链表的第一个节点
        L->next = s;         // 更新头节点的指针指向新节点
        // 检测是否为换行符
        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; // p指向链表的第一个节点
    while (p)
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl;
}
// 查找两个链表的公共节点
void PublicNode(LinkList &LA, LinkList &LB)
{
    int lena = 0, lenb = 0;
    LNode *p = LA->next;
    
    // 计算链表A的长度
    while (p)
    {
        lena++;
        p = p->next;
    }
    p = LB->next;
    // 计算链表B的长度
    while (p)
    {
        lenb++;
        p = p->next;
    }
    LNode *longList, *shortList;
    int dist = 0;
    // 确定较长和较短的链表
    if (lena > lenb)
    {
        longList = LA->next; // 链表A较长
        shortList = LB->next; // 链表B较短
        dist = lena - lenb;   // 计算长度差
    }
    else
    {
        longList = LB->next; // 链表B较长
        shortList = LA->next; // 链表A较短
        dist = lenb - lena;   // 计算长度差
    }
    // 移动较长链表的指针,使其与较短链表对齐
    while (dist--)
    {
        longList = longList->next;
    }
    // 同时遍历两个链表,寻找公共节点
    while (longList != NULL)
    {
        if (longList == shortList) // 找到公共节点
        {
            cout << longList->data; // 输出公共节点数据
            return;
        }
        else
        {
            longList = longList->next; // 移动到下一个节点
            shortList = shortList->next;
        }
    }
}
int main()
{
    LNode *p1 = new LNode; // 创建链表A的头结点
    LNode *q1 = new LNode; // 创建链表B的头结点
    LNode *q2 = new LNode; // 链表B的节点
    LNode *q3 = new LNode; // 链表B的节点
    // 公共结点
    LNode *m1 = new LNode;
    m1->data = 99999; // 公共节点的数据
    LNode *m2 = new LNode; // 公共节点的下一个节点
    m1->next = m2; // 设置公共节点的下一个节点
    m2->next = NULL; // 公共节点的下一节点指向NULL
    p1->next = m1; // 链表A连接公共节点
    // 构建链表B
    q1->next = q2; // q1指向q2
    q2->next = q3; // q2指向q3
    q3->next = m1; // q3指向公共节点m1
    // 查找并输出公共节点
    PublicNode(p1, q1);
}
  • image.gif

(9)题目:给定一个带表头结点的单链表,设head为头指针,结点结构为(data,next),data为整型元素,next为指针,试写出算法:按递增次序输出单链表中各节点的数据元素,并释放结点所占的存储空间(要求:不允许使用数组作为辅助空间)。

解题思路:


>遍历链表找到最小值将其输入
>然后将其删除,重复该过程
>直到表为空
链表结构: 使用 LNode 结构体定义链表节点,包括数据和指向下一个节点的指针。
链表操作:
HeadInsert: 头插法创建链表(未在 main 中调用)。
TailInsert: 尾插法创建链表,从标准输入读取整数,直到遇到换行符。
Print: 遍历链表,输出所有节点的数据(未在 main 中调用)。
PrintValue: 遍历链表,找到并输出每次遍历中的最小值,并删除该节点。
主函数: 创建一个链表,调用 TailInsert 函数添加数据,然后调用 PrintValue 函数输出并删除链表中的最小值。

实现代码:

#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;   // 新节点指向当前链表的第一个节点
        L->next = s;         // 更新头节点的指针指向新节点
        // 检测是否为换行符
        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; // p指向链表的第一个节点
    while (p)
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl;
}
// 输出链表中的最小值并删除
void PrintValue(LinkList &L)
{
    LNode *p, *pre;
    LNode *minP, *minPre;
    // 当链表还有节点时循环
    while (L->next)
    {
        p = L->next; // 从第一个节点开始
        pre = L;     // pre指向当前节点的前驱
        minP = L->next; // 初始最小节点为第一个节点
        minPre = L;     // 最小节点的前驱为头节点
        // 遍历链表查找最小值节点
        while (p)
        {
            if (p->data < minP->data) // 找到更小的值
            {
                minP = p;        // 更新最小节点
                minPre = pre;    // 更新最小节点前驱
            }
            pre = p; // 移动前驱指针
            p = p->next; // 移动当前指针
        }
        // 输出最小值
        cout << minP->data << '\t';
        
        // 删除最小值节点
        LNode *q = minP;          // 临时保存最小节点
        minPre->next = minP->next; // 更新前驱节点的next指针
        delete q;                // 删除最小节点
    }
}
int main()
{
    LinkList L = new LNode; // 创建链表的头结点
    TailInsert(L);          // 调用尾插法插入数据
    PrintValue(L);         // 打印链表中的最小值并删除
}
  • image.gif

(10)题目:将一个带头节点的单链表QA分解为两个带头节点的单链表A和B,使得A表中含有原表中序号为奇数的元素,而B表中含有原表中序号为偶数的元素,且保持其相对顺序不变。


解题思路:

>定义位置变量,用于指示节点序号
>然后定义两个尾指针,分别判断节点序号奇偶
>使用尾插法进行插入
链表结构: 使用 LNode 结构体定义链表节点,包括数据和指向下一个节点的指针。
链表操作:
HeadInsert: 头插法创建链表(未在 main 中调用)。
TailInsert: 尾插法创建链表,从标准输入读取整数,直到遇到换行符。
Print: 遍历链表,输出所有节点的数据。
BreakList: 将原链表中的节点分成两个链表,奇数位置的节点放入链表 LA,偶数位置的节点放入链表 LB。
主函数:
创建两个链表 LA 和 LB 的头节点。
调用 TailInsert 函数添加数据到链表 LA。
调用 BreakList 函数将链表 LA 分割成两个链表 LA 和 LB。
打印两个链表的内容。

实现代码:

#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;    // 新节点指向当前链表的第一个节点
        L->next = s;          // 更新头节点的指针指向新节点
        // 检测是否为换行符
        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; // p指向链表的第一个节点
    while (p) // 当p不为空时
    {
        cout << p->data << '\t'; // 输出节点数据
        p = p->next;             // 移动到下一个节点
    }
    cout << endl; // 输出换行
}
// 将链表分成两个链表,奇数节点进入LA,偶数节点进入LB
void BreakList(LinkList &LA, LinkList &LB)
{
    int i = 1; // 节点计数器
    LNode *p, *ra, *rb;
    p = LA->next; // 从LA的第一个节点开始
    ra = LA;      // ra指向LA链表的当前末尾
    rb = LB;      // rb指向LB链表的当前末尾
    ra->next = NULL; // 初始化LA的next为空
    rb->next = NULL; // 初始化LB的next为空
    // 遍历原链表
    while (p)
    {
        if (i % 2 == 1) // 如果是奇数位置的节点
        {
            ra->next = p; // 将当前节点链接到LA
            ra = p;       // 更新ra指向当前节点
        }
        else // 如果是偶数位置的节点
        {
            rb->next = p; // 将当前节点链接到LB
            rb = p;       // 更新rb指向当前节点
        }
        p = p->next; // 移动到下一个节点
        i++;         // 计数器加一
    }
    ra->next = NULL; // 结束LA链表
    rb->next = NULL; // 结束LB链表
}
int main()
{
    LinkList LA = new LNode; // 创建链表LA的头节点
    LinkList LB = new LNode; // 创建链表LB的头节点
    TailInsert(LA);          // 使用尾插法创建链表LA
    BreakList(LA, LB);      // 将链表LA分成两个链表LA和LB
    Print(LA);              // 打印链表LA
    Print(LB);              // 打印链表LB
}


相关文章
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
84 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
33 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
22 0
数据结构与算法学习十四:常用排序算法总结和对比
|
2月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
37 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
2月前
|
机器学习/深度学习 存储 算法
【数据结构与算法基础】——算法复杂度
【数据结构与算法基础】——算法复杂度
|
6月前
|
算法 C++ Python
数据结构与算法===贪心算法
数据结构与算法===贪心算法
|
2月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
25 0
|
6月前
|
算法 Java
Java数据结构与算法:最短路径算法
Java数据结构与算法:最短路径算法