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

盛透侧视攻城狮

发布于 2024-10-22 10:29:18

2230

文章被收录于专栏：超前沿网络空间安全全栈学习宝典超前沿网络空间安全全栈学习宝典

上节回顾

https://cloud.tencent.com/developer/article/2460768

前节回顾

王道第2.3章节之线性表精题汇总四

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

解题思路：

链表节点结构体 (LNode):

data 用于存储节点的数据。
next 是一个指针，用于指向下一个节点。
头插法 (HeadInsert):

通过不断读取输入，将新节点插入到链表的头部。
使用 L->next 来维护链表的结构。
尾插法 (TailInsert):

持续读取输入，将新节点追加到链表末尾。
r 用于跟踪当前尾部节点，更新尾部指针。
打印函数 (Print):

遍历链表，从头节点开始输出每个节点的数据。
反转链表 (fn):

将链表中的节点顺序反转。
使用三个指针：p 用于当前节点，r 用于暂存下一个节点，L->next 用于构建反转后的链表。
主函数 (main):

创建链表头节点，调用 TailInsert 进行数据插入，然后调用 fn 反转链表，最后输出反转后的链表。

实现代码：

#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); // 打印链表
}

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

解题思路：

>定义工作指针p、前驱指针q
>遍历链表删除节点




链表节点结构体 (LNode):

data：用于存储节点的数据。
next：指向下一个节点的指针。
头插法 (HeadInsert):

通过不断读取输入，将新节点插入到链表的头部。
使用 L->next 来维护链表的结构。
尾插法 (TailInsert):

持续读取输入，将新节点追加到链表末尾。
r 用于跟踪当前尾部节点，更新尾部指针。
打印函数 (Print):

遍历链表，从头节点开始输出每个节点的数据。
删除指定范围内的节点 (DelValue):

该函数用于删除链表中数据值在 left 和 right 之间的所有节点。
使用两个指针 p 和 pre 来维护当前节点和前驱节点，判断并删除符合条件的节点。
主函数 (main):

实现代码：

#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); // 打印链表
}

（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);
}

（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);         // 打印链表中的最小值并删除
}

（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
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-18，如有侵权请联系 cloudcommunity@tencent.com 删除

指针

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

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

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

登录后参与评论

0 条评论

热度

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

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

上节回顾

前节回顾

王道第2.3章节之线性表精题汇总四

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

解题思路：

实现代码：

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

解题思路：

实现代码：

（8）题目：给定两个单链表Q，编写算法找出两个链表的公共结点。

解题思路：

实现代码：

解题思路：

实现代码：

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

解题思路：

实现代码：

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

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

上节回顾

前节回顾

王道第2.3章节之线性表精题汇总四

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

解题思路：

实现代码：

​

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

解题思路：

实现代码：

​

（8）题目：给定两个单链表Q，编写算法找出两个链表的公共结点。

解题思路：

实现代码：

解题思路：

实现代码：

​

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

解题思路：

实现代码：

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

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