设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 请教一下这个数据结构算法题
返回列表 发新帖
查看: 2315|回复: 4

[已解决]请教一下这个数据结构算法题

[复制链接]
赛酱想学编程
发表于 2023-4-30 23:12:10 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
题目：在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法实现上述操作

问题/疑惑：我使用的编译器为vs2022，程序编译运行之后没有输出删除元素x后的链表元素，程序没有报错，我重复看了几遍代码也没找出问题，望大佬指点一下，告诉我怎么改这一段代码才正确？？


代码如下：
#include <iostream>
#include<stdlib.h>
using namespace std;
#define MAX 50

typedef struct LNode
{
        int data;
        struct LNode* next;
}LNode, * Linklist;

int a[MAX] = { 1,3,3,4 };
int length = 4;

void buildlist(Linklist& L)//把数组中的值放入新建的链表中
{
        L = (LNode*)malloc(sizeof(LNode));
        LNode* s, * r = L;
        for (int i = 0; i < length; i++)
        {
                s = (LNode*)malloc(sizeof(LNode));
                s->data = a[i];
                r->next = s;
                r = r->next;
        }
}

void disp(Linklist L)//输出链表的值
{
        LNode* s = L->next;
        while (s)
        {
                cout << s->data;
                s = s->next;
        }
}

void deletex(Linklist& L, int x)//删除所有为x的元素
{
        LNode* p = L->next, * r = L, * q;
        while (p)
        {
                if (p->data != x)
                {
                        r->next = p;
                        r = p;
                        p = p->next;
                }
                else
                {
                        q = p;
                        p = p->next;
                        r->next = p;
                        free(q);
                }
        }
}

int main()
{
        Linklist L;
        buildlist(L);
        cout << "删除前的链表为：" << endl;
        disp(L);
        cout << "删除后的链表为：" << endl;
        deletex(L, 3);
        disp(L);
}
最佳答案
月排行榜 / 总排行榜
sfqxx
2023-5-2 11:27:27
根据你给出的代码，存在以下问题：

1. 在 `buildlist` 函数中，没有将最后一个结点的 next 置为 NULL，使得在后面遍历链表时，会遍历到一些未知区域，可能导致程序出错。

2. 在 `deletex` 函数中，当需要删除值为 x 的结点时，没有更新 r 的指向，使得在下一次循环迭代中，r 和 p 间隔了一个值为 x 的结点。这个问题可以通过在 if 语句块开始处新增 else if (p->next == NULL) { r = p; break; } 来解决，在判断当前结点是否是需要删除的结点时，如果是最后一个结点，则需要令 r 指向它，然后跳出循环。

修改后的代码如下：

  2. void buildlist(Linklist& L)//把数组中的值放入新建的链表中
  3. {
  4.     L = (LNode*)malloc(sizeof(LNode));
  5.     LNode* s, * r = L;
  6.     for (int i = 0; i < length; i++)
  7.     {
  8.         s = (LNode*)malloc(sizeof(LNode));
  9.         s->data = a[i];
  10.         r->next = s;
  11.         r = s;
  12.     }
  13.     r->next = NULL; // 将最后一个结点的 next 置为 NULL
  14. }

  16. void deletex(Linklist& L, int x)//删除所有为x的元素
  17. {
  18.     LNode* p = L->next, * r = L, * q;
  19.     while (p)
  20.     {
  21.         if (p->data != x)
  22.         {
  23.             r->next = p;
  24.             r = p;
  25.             p = p->next;
  26.         }
  27.         else
  28.         {
  29.             q = p;
  30.             p = p->next;
  31.             r->next = p;
  32.             free(q);
  33.         }
  34.         // 新增代码，判断是否需要更新 r
  35.         if (p == NULL) { r = p; break; }
  36.     }
  37. }
复制代码

你可以试着编译并运行一下这份代码
有用请设置最佳答案
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

isdkz
发表于 2023-4-30 23:25:59 | 显示全部楼层
您好！根据您提供的代码，我发现您在 buildlist 函数中遗漏了一步：在循环结束后，需要将链表的最后一个结点的 next 指针设置为 NULL 。这样，当我们遍历链表时，就能找到链表的末尾。请参考下面的修改后的代码：

  1. #include <iostream>
  2. #include<stdlib.h>
  3. using namespace std;
  4. #define MAX 50

  6. typedef struct LNode
  7. {
  8.     int data;
  9.     struct LNode* next;
  10. }LNode, * Linklist;

  12. int a[MAX] = { 1,3,3,4 };
  13. int length = 4;

  15. void buildlist(Linklist& L)//把数组中的值放入新建的链表中
  16. {
  17.     L = (LNode*)malloc(sizeof(LNode));
  18.     LNode* s, * r = L;
  19.     for (int i = 0; i < length; i++)
  20.     {
  21.         s = (LNode*)malloc(sizeof(LNode));
  22.         s->data = a[i];
  23.         r->next = s;
  24.         r = r->next;
  25.     }
  26.     r->next = NULL; // 添加这一行代码
  27. }

  29. void disp(Linklist L)//输出链表的值
  30. {
  31.     LNode* s = L->next;
  32.     while (s)
  33.     {
  34.         cout << s->data << " "; // 添加一个空格，使输出更易于阅读
  35.         s = s->next;
  36.     }
  37.     cout << endl; // 输出换行，使结果更易于阅读
  38. }

  40. void deletex(Linklist& L, int x)//删除所有为x的元素
  41. {
  42.     LNode* p = L->next, * r = L, * q;
  43.     while (p)
  44.     {
  45.         if (p->data != x)
  46.         {
  47.             r->next = p;
  48.             r = p;
  49.             p = p->next;
  50.         }
  51.         else
  52.         {
  53.             q = p;
  54.             p = p->next;
  55.             r->next = p;
  56.             free(q);
  57.         }
  58.     }
  59. }

  61. int main()
  62. {
  63.     Linklist L;
  64.     buildlist(L);
  65.     cout << "删除前的链表为：" << endl;
  66.     disp(L);
  67.     cout << "删除后的链表为：" << endl;
  68.     deletex(L, 3);
  69.     disp(L);
  70. }
复制代码


在这个修改后的代码中，我添加了一行代码（ r->next = NULL; ）以在 buildlist 函数中设置链表的末尾。另外，我还对 disp 函数进行了轻微修改，使输出结果更易于阅读。现在这个代码应该可以按照预期运行，正确输出删除元素x后的链表元素。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

陶远航
发表于 2023-5-1 09:21:37 | 显示全部楼层
你的代码在函数deletex()中，当p指针指向值为x的结点时，没有更新r的值，导致新的结点插入到了上一个不为x的结点的后面，而不是插入到链表中，因此程序没有输出正确的链表元素。

你需要在p指向的结点的值不为x时，更新r的值。修改deletex()函数如下：

void deletex(Linklist& L, int x)
{
    LNode* p = L->next, * r = L, * q;
    while (p)
    {
        if (p->data != x)
        {
            r = p;
            p = p->next;
        }
        else
        {
            q = p;
            p = p->next;
            r->next = p;
            free(q);
        }
    }
}

请注意，这里是在p指向的结点的值不为x时，更新r的值，而不是在p指向的结点的值为x时更新r的值。这样可以保证当找到值为x的结点时，r指向的是上一个不为x的结点，方便后续删除操作。

修改后，你可以重新编译运行程序，并查看输出结果。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

sfqxx
发表于 2023-5-2 11:27:27 | 显示全部楼层    本楼为最佳答案   
根据你给出的代码，存在以下问题：

1. 在 `buildlist` 函数中，没有将最后一个结点的 next 置为 NULL，使得在后面遍历链表时，会遍历到一些未知区域，可能导致程序出错。

2. 在 `deletex` 函数中，当需要删除值为 x 的结点时，没有更新 r 的指向，使得在下一次循环迭代中，r 和 p 间隔了一个值为 x 的结点。这个问题可以通过在 if 语句块开始处新增 else if (p->next == NULL) { r = p; break; } 来解决，在判断当前结点是否是需要删除的结点时，如果是最后一个结点，则需要令 r 指向它，然后跳出循环。

修改后的代码如下：

  2. void buildlist(Linklist& L)//把数组中的值放入新建的链表中
  3. {
  4.     L = (LNode*)malloc(sizeof(LNode));
  5.     LNode* s, * r = L;
  6.     for (int i = 0; i < length; i++)
  7.     {
  8.         s = (LNode*)malloc(sizeof(LNode));
  9.         s->data = a[i];
  10.         r->next = s;
  11.         r = s;
  12.     }
  13.     r->next = NULL; // 将最后一个结点的 next 置为 NULL
  14. }

  16. void deletex(Linklist& L, int x)//删除所有为x的元素
  17. {
  18.     LNode* p = L->next, * r = L, * q;
  19.     while (p)
  20.     {
  21.         if (p->data != x)
  22.         {
  23.             r->next = p;
  24.             r = p;
  25.             p = p->next;
  26.         }
  27.         else
  28.         {
  29.             q = p;
  30.             p = p->next;
  31.             r->next = p;
  32.             free(q);
  33.         }
  34.         // 新增代码，判断是否需要更新 r
  35.         if (p == NULL) { r = p; break; }
  36.     }
  37. }
复制代码

你可以试着编译并运行一下这份代码
有用请设置最佳答案
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

赛酱想学编程
 楼主| 发表于 2023-5-2 19:06:41 | 显示全部楼层
sfqxx 发表于 2023-5-2 11:27
根据你给出的代码，存在以下问题：

1. 在 `buildlist` 函数中，没有将最后一个结点的 next 置为 NULL， ...

谢谢捏！
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-12 15:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表