欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

专栏跑道二

➡️ 24 Network Security -LJS

专栏跑道三

➡️ MYSQL REDIS Advance operation

专栏跑道四

➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

上节回顾

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

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

专栏跑道二

➡️ 24 Network Security -LJS

专栏跑道三

➡️ MYSQL REDIS Advance operation

专栏跑道四

➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

上节回顾

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

解题思路：

实现代码：

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

实现代码：

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

解题思路：

解题思路：

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

解题思路：

实现代码：

视觉智能

热门文章

最新文章

相关课程

相关电子书

相关实验场景

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

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

专栏跑道二

➡️ 24 Network Security -LJS

专栏跑道三

➡️ MYSQL REDIS Advance operation

专栏跑道四

➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

上节回顾

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

解题思路：

实现代码：

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

实现代码：

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

解题思路：

解题思路：

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

解题思路：

实现代码：

视觉智能

热门文章

最新文章

相关课程

相关电子书

相关实验场景

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