鱼C论坛

 找回密码
 立即注册
查看: 2308|回复: 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);
}
最佳答案
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 指向它,然后跳出循环。

修改后的代码如下:

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

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

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

使用道具 举报

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

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

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

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

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

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

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

  55. int main()
  56. {
  57.     Linklist L;
  58.     buildlist(L);
  59.     cout << "删除前的链表为:" << endl;
  60.     disp(L);
  61.     cout << "删除后的链表为:" << endl;
  62.     deletex(L, 3);
  63.     disp(L);
  64. }
复制代码


在这个修改后的代码中,我添加了一行代码( 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
回复 支持 反对

使用道具 举报

发表于 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 指向它,然后跳出循环。

修改后的代码如下:

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

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

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

使用道具 举报

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

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2025-6-10 15:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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