admin管理员组

文章数量:1794759

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

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

（10）题目:

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

解题思路：

代码语言：javascript代码运行次数：0运行复制
1>定义位置变量,用于指示节点序号

2>然后定义两个尾指针，分别判断节点序号奇偶

3>使用尾插法进行插入

实现代码：

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    int data;            // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList是指向LNode的指针类型

// 头插法
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;         // 将新节点链接到当前链表的最后
        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 BreakList(LinkList &LA, LinkList &LB)
{
    int i = 1; // 计数器
    LNode *p, *ra, *rb; // p指向原链表，ra和rb分别指向新链表的尾部
    p = LA->next; // 从LA的第一个节点开始
    ra = LA; // ra初始化为LA
    rb = LB; // rb初始化为LB
    ra->next = NULL; // 初始化LA的next为NULL
    rb->next = NULL; // 初始化LB的next为NULL

    while (p) // 遍历原链表
    {
        if (i % 2 == 1) // 如果是奇数节点
        {
            ra->next = p; // 将节点p链接到LA
            ra = p; // 更新ra为当前节点
        }
        else // 如果是偶数节点
        {
            rb->next = p; // 将节点p链接到LB
            rb = p; // 更新rb为当前节点
        }
        p = p->next; // 移动到下一个节点
        i++; // 计数器加1
    }
    ra->next = NULL; // 将LA的最后一个节点的next指针置为NULL
    rb->next = NULL; // 将LB的最后一个节点的next指针置为NULL
}

int main()
{
    LinkList LA = new LNode; // 创建链表A的头节点
    LinkList LB = new LNode; // 创建链表B的头节点
    TailInsert(LA); // 通过尾插法输入链表A的数据

    BreakList(LA, LB); // 将链表A分为链表LA和LB

    Print(LA); // 输出链表A的内容
    Print(LB); // 输出链表B的内容
}

（11）题目：

设 C= {a，by，a2，b2…，amb}为线性表，采用带头结点的 hc 单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a,a2, ,a}, B={bm…,b2,b}.设C={a1,b1,a2,b2}为线性表，采用带头节点的hc单链表Q存放，设计一个就地算法，将其拆分为两个线性表,使得A={a1,a2,an), B={bn,b2,b1}。

解题思路：

代码语言：javascript代码运行次数：0运行复制
>问题的关键就是采用何种方式构建链表
>A采用尾插保持原顺序
>B采用前插法将其逆序

实现代码：

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    int data;            // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList是指向LNode的指针类型

// 头插法
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;         // 将新节点链接到当前链表的最后
        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 BreakList(LinkList &LA, LinkList &LB)
{
    LNode *p, *q, *ra; // p为工作指针，q保存后继指针，ra为LA的尾指针
    LB->next = NULL;   // 将LB链表置空
    p = LA->next; // 从LA的第一个节点开始
    ra = LA; // 初始化LA的尾指针

    while (p) // 遍历原链表
    {
        // 将当前节点p插入到LA
        ra->next = p;
        ra = p; // 更新ra为当前节点
        p = p->next; // 移动到下一个节点

        // 如果p不为空，继续将其前插到LB
        if (p)
        {
            q = p->next; // 保存p的后继，防止断链
            p->next = LB->next; // 将p插入到LB的头部
            LB->next = p; // 更新LB的头指针
            p = q; // 移动到下一个节点
        }
    }
    ra->next = NULL; // 将LA的尾节点的next指针置为NULL
}

int main()
{
    LinkList LA = new LNode; // 创建链表A的头节点
    LinkList LB = new LNode; // 创建链表B的头节点
    TailInsert(LA); // 通过尾插法输入链表A的数据

    BreakList(LA, LB); // 将链表A分为链表LA和LB

    Print(LA); // 输出链表A的内容
    Print(LB); // 输出链表B的内容
}

（12）题目：

在一个递增有序的线性表中,有数值相同的元素存在。若存储方式为单链表,设计算法去掉数值相同的元素，使表中不再有重复的元素，例如(7, 10, 10,21,30,42,42,42,51,70)将变为(7,10,21, 30,42, 51,70).

解题思路：

代码语言：javascript代码运行次数：0运行复制
>定义工作结点、待删除结点前驱
>如果发现某一结点值等于后继结点的值，将其删除

实现代码：

代码语言：javascript代码运行次数：0运行复制
#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 Duplicate(LinkList &L)
{
    LNode *p, *pre; // p用于遍历链表，pre用于记录前驱节点
    p = L->next; // p指向第一个实际数据节点
    pre = L;     // pre初始化为头节点

    while (p) // 遍历链表
    {
        // 检查当前节点和下一个节点是否值相同
        if (p->next && p->data == p->next->data)
        {
            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); // 使用尾插法插入节点

    Duplicate(L); // 删除重复元素

    Print(L); // 打印链表
}

（13）题目：

假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表.

解题思路：

代码语言：javascript代码运行次数：0运行复制
>归并排序

实现代码：

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    int data;            // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是指向 LNode 的指针类型

// 头插法
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;         // 将新节点链接到当前链表的最后
        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; // 输出换行
}

// 找到两个链表的公共节点并将其插入到链表 LC
void PublicNode(LinkList &LA, LinkList &LB, LinkList &LC)
{
    LNode *pa, *pb, *r; // 定义两个链表的工作节点和尾插指针
    pa = LA->next; // pa 初始化为链表 A 的第一个节点
    pb = LB->next; // pb 初始化为链表 B 的第一个节点
    r = LC; // r 指向链表 C 的头节点

    while (pa && pb) // 遍历两个链表
    {
        // 小节点的链表向后移
        if (pa->data < pb->data) // 如果 pa 指向的节点数据小于 pb
        {
            pa = pa->next; // pa 向后移动
        }
        else if (pa->data > pb->data) // 如果 pa 指向的节点数据大于 pb
        {
            pb = pb->next; // pb 向后移动
        }
        // 新建节点插入到 LC 尾部
        else // 如果 pa 和 pb 数据相等，即为公共节点
        {
            LNode *s = new LNode; // 创建新节点
            s->data = pa->data;   // 设置新节点的数据为公共节点的数据
            r->next = s;          // 将新节点插入到 LC 的尾部
            r = s;                // 更新 r 为新节点
            pa = pa->next;        // 移动到下一个节点
            pb = pb->next;        // 移动到下一个节点
        }
    }
    r->next = NULL; // 最后将 LC 的尾节点的 next 指针设为 NULL
}

int main()
{
    LinkList LA = new LNode; // 创建链表 A 的头节点
    LinkList LB = new LNode; // 创建链表 B 的头节点
    LinkList LC = new LNode; // 创建链表 C 的头节点
    TailInsert(LA); // 通过尾插法输入链表 A 的数据
    TailInsert(LB); // 通过尾插法输入链表 B 的数据

    PublicNode(LA, LB, LC); // 找到公共节点并插入到链表 C
    Print(LC); // 输出链表 C
}

​

（14）题目：

设 A 和 B 是两个单链表（带头结点），其中元素递增有序。设计一个算法从 A 和 B 中的公共元素产生单链表 C，要求不破坏 A、B 的结点。

解题思路：

代码语言：javascript代码运行次数：0运行复制
>类似于归并排序
>将相等结点插入LC

实现代码：

代码语言：javascript代码运行次数：0运行复制
#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; // 输出换行
}

// 找到两个链表的公共节点并存入LC
void PublicNode(LinkList &LA, LinkList &LB, LinkList &LC)
{
    LNode *pa, *pb, *r; // 定义两个链表的工作节点和尾插指针
    pa = LA->next; // pa指向链表LA的第一个数据节点
    pb = LB->next; // pb指向链表LB的第一个数据节点
    r = LC;        // r指向链表LC的头节点

    while (pa && pb) // 当两个链表都有节点时
    {
        // 比较当前节点的值
        if (pa->data < pb->data) // 如果LA的当前节点小于LB的当前节点
        {
            pa = pa->next; // LA向后移动
        }
        else if (pa->data > pb->data) // 如果LA的当前节点大于LB的当前节点
        {
            pb = pb->next; // LB向后移动
        }
        // 如果当前节点相等，说明找到公共节点
        else
        {
            LNode *s = new LNode; // 创建新节点
            s->data = pa->data;   // 将公共节点的值赋给新节点
            r->next = s;          // 将新节点插入到LC的尾部
            r = s;                // 更新尾指针r，指向新节点
            pa = pa->next;       // LA和LB都向后移动
            pb = pb->next;
        }
    }
    r->next = NULL; // 最后设置LC的尾指针的next为NULL
}

int main()
{
    LinkList LA = new LNode; // 创建链表LA的头节点
    LinkList LB = new LNode; // 创建链表LB的头节点
    LinkList LC = new LNode; // 创建链表LC的头节点
    TailInsert(LA); // 使用尾插法插入LA的节点
    TailInsert(LB); // 使用尾插法插入LB的节点

    PublicNode(LA, LB, LC); // 找到LA和LB的公共节点并存入LC
    Print(LC); // 打印链表LC
}

​

（15）题目：

已知两个链表A和B分别表示两个集合,其元素递增排列。编制函数,求A与B的交集，并存放于 A 链表中

解题思路：

代码语言：javascript代码运行次数：0运行复制
>类似归并排序
>将不等结点释放，相等结点进行尾插

实现代码：

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
using namespace std;

// 定义链表节点结构
typedef struct LNode
{
    int data;            // 节点数据
    struct LNode *next; // 指向下一个节点的指针
} LNode, *LinkList; // LinkList 是指向 LNode 的指针类型

// 头插法
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;         // 将新节点链接到当前链表的最后
        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 PublicNode(LinkList &LA, LinkList &LB)
{
    LNode *pa, *pb, *r, *q; // 定义工作节点和尾插指针
    pa = LA->next; // pa 初始化为链表 A 的第一个节点
    pb = LB->next; // pb 初始化为链表 B 的第一个节点
    r = LA; // r 初始化为链表 A 的头节点

    while (pa && pb) // 遍历两个链表
    {
        // 如果 pa 数据小于 pb，则删除 pa，指针后移
        if (pa->data < pb->data)
        {
            q = pa; // 记录要删除的节点
            pa = pa->next; // pa 后移
            delete q; // 释放内存
        }
        // 如果 pa 数据大于 pb，则删除 pb，指针后移
        else if (pa->data > pb->data)
        {
            q = pb; // 记录要删除的节点
            pb = pb->next; // pb 后移
            delete q; // 释放内存
        }
        // 如果相等，将 pa 尾插，删除 pb
        else
        {
            r->next = pa; // 将 pa 插入到链表 A
            r = pa; // 更新尾插指针
            pa = pa->next; // pa 后移
            q = pb; // 记录要删除的节点
            pb = pb->next; // pb 后移
            delete q; // 释放内存
        }
    }

    // 将剩余所有节点全部释放
    while (pa) // 如果 pa 还有剩余节点
    {
        q = pa; // 记录要删除的节点
        pa = pa->next; // pa 后移
        delete q; // 释放内存
    }

    while (pb) // 如果 pb 还有剩余节点
    {
        q = pb; // 记录要删除的节点
        pb = pb->next; // pb 后移
        delete q; // 释放内存
    }

    r->next = NULL; // 将链表 A 的最后一个节点指向 NULL
    delete LB; // 释放链表 B 的头节点
}

int main()
{
    LinkList LA = new LNode; // 创建链表 A 的头节点
    LinkList LB = new LNode; // 创建链表 B 的头节点

    TailInsert(LA); // 通过尾插法输入链表 A 的数据
    TailInsert(LB); // 通过尾插法输入链表 B 的数据

    PublicNode(LA, LB); // 合并链表 A 和 B 的公共节点
    Print(LA); // 输出链表 A
}

​

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-21，如有侵权请联系 cloudcommunity@tencent 删除数据数据结构与算法指针遍历链表

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

版权声明：本文标题：2024重生之回溯数据结构与算法系列学习（4）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754674940a1705056.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。