赛酱想学编程 发表于 2023-4-30 23:12:10

请教一下这个数据结构算法题

题目：在带头结点的单链表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 = { 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;
                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);
}

isdkz 发表于 2023-4-30 23:25:59

您好！根据您提供的代码，我发现您在 buildlist 函数中遗漏了一步：在循环结束后，需要将链表的最后一个结点的 next 指针设置为 NULL 。这样，当我们遍历链表时，就能找到链表的末尾。请参考下面的修改后的代码：

#include <iostream>
#include<stdlib.h>
using namespace std;
#define MAX 50

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

int a = { 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;
      r->next = s;
      r = r->next;
    }
    r->next = NULL; // 添加这一行代码
}

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

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


在这个修改后的代码中，我添加了一行代码（ r->next = NULL; ）以在 buildlist 函数中设置链表的末尾。另外，我还对 disp 函数进行了轻微修改，使输出结果更易于阅读。现在这个代码应该可以按照预期运行，正确输出删除元素x后的链表元素。

陶远航 发表于 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的结点，方便后续删除操作。

修改后，你可以重新编译运行程序，并查看输出结果。

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 指向它，然后跳出循环。

修改后的代码如下：

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;
      r->next = s;
      r = s;
    }
    r->next = NULL; // 将最后一个结点的 next 置为 NULL
}

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);
      }
      // 新增代码，判断是否需要更新 r
      if (p == NULL) { r = p; break; }
    }
}
你可以试着编译并运行一下这份代码
有用请设置最佳答案

赛酱想学编程 发表于 2023-5-2 19:06:41

sfqxx 发表于 2023-5-2 11:27
根据你给出的代码，存在以下问题：

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

谢谢捏！
页: [1]
查看完整版本: 请教一下这个数据结构算法题