用C++删除单链表中值为0的节点

hxzsmxv2  于 2023-01-03  发布在  其他
关注(0)|答案(4)|浏览(170)

我一辈子都弄不明白,我花了好几天做这个练习,但无济于事。
我正在尝试从单赞列表中删除值为0的节点。
假设我有|1| 3| 0| 4| 0| 5| 0| 0|。结果应该是|1| 3| 4| 5|
下面是所有的代码供参考

#include <iostream>
#include <fstream>

using namespace std;

struct node {
    int data;
    node* next;
};
node* head, *last;
int n;
void creating_list()
{
    node* aux;
    ifstream f("in.txt");
    f >> n;
    for(int i=0;i<n;i++)
    {
        if (head == NULL)
        {
            head = new node;
            f >> head->data;
            head->next = NULL;
            last = head;
        }
        else
        {
            aux = new node;
            f >> aux->data;
            last->next = aux;
            aux->next = NULL;
            last = aux;
            
        }
    }
    
}

void displaying_list() 
{
    node* a;
    a = head;
    if (a == NULL)
        cout << "List is empty! ";
    else
    {
        cout << "Elements of list are: | ";
        while (a)
        {
            cout << a->data<<" | ";
            a = a->next;
        }
    }
}

void delete_first_node()
{
    if (head == NULL)
        cout << "List is empty";
    else
    {
        cout << "Deleting first node\n";
        node* aux;
        aux = head;
        head = head->next;
        delete aux;
    }
}
void delete_last_node()
{
    if (head == NULL)
        cout << "List is empty";
    else
    {
        if (head == last)
        {
            delete head;
            head = last = NULL;

        }
        else
        {
            node* current;
            current = head;
            while (current->next != last)
                current = current->next;
            delete current->next;
            current->next = NULL;
            last = current;
        }
    }
}
void delete_value_0()
{
    node* aux;
    if (head == NULL)
        cout << "List is empty. Can't delete! ";
    else
    
    //  if (head->data == 0)
    //      delete_first_node();
    //  if (last->data == 0)
    //      delete_last_node();
    //  else
        {
            node* a;
            a = head;
            while (a)
                if (a->next->data != 0)
                { 
                    a = a->next;
                    cout << a->data<<" | ";
                }
                else
                    if (a->next != last)
                    {
                        aux = a->next;
                        a->next = a->next->next;
                        delete aux;
                        break;
                    }
        }

    
}

int main()
{
    creating_list();
    displaying_list(); cout <<endl;
    delete_value_0();
    
    return 0;
}

这是金属问题,我试着移动一个节点,远离值为0的节点,把值存储在另一个节点,这里是aux,然后删除aux;
我在这些行上加了注解,因为如果我不加注解,并且满足了条件,它就不会执行其余的代码...
如果我把break放在末尾,它只显示前几个数字,直到0,然后在短时间内停止,不移动整个列表。
如果我不输入break,程序就不会停止,它处于无限循环中,它不会以代码0退出

void delete_value_0()
{
    node* aux;
    if (head == NULL)
        cout << "List is empty. Can't delete! ";
    else
    
    //  if (head->data == 0)
    //      delete_first_node();
    //  if (last->data == 0)
    //      delete_last_node();
    //  else
        {
            node* a;
            a = head;
            while (a)
                if (a->next->data != 0)
                { 
                    a = a->next;
                    cout << a->data<<" | ";
                }
                else
                    if (a->next != last)
                    {
                        aux = a->next;
                        a->next = a->next->next;
                        delete aux;
                        break;
                    }
        }

    
}

老实说,我很困惑,我花了这么多时间试图弄清楚这一点,这应该是一个非常简单的练习。我觉得像回答真的很简单,但我不知道该怎么做了,也许这是不适合我。

vjhs03f7

vjhs03f71#

这比第一眼看到的要简单得多,这个任务的诀窍是不使用指向当前节点的指针,而是使用指向当前节点的指针,整个任务变得可笑而琐碎:只有一个循环和一个if语句,该语句负责所有可能性:列表为空;要删除的节点是列表中的第一个节点;不是列表中的最后一个节点;或者在它中间的任何地方。

void delete_value_0()
{
    node **p= &head;

    while (*p)
    {
        if ((*p)->data == 0)
        {
           node *nextptr=*p;

           *p=(*p)->next;
           delete nextptr;
        }
        else
        {
            p= &(*p)->next;
        }
    }
}
m1m5dgzv

m1m5dgzv2#

最简单的解决方案是这样的:

void delete_value_0()
{
    while (head && head->data == 0)
        delete_first_node();

    if (head == nullptr)
        return;

    node *cur = head->next;
    node *pre = head;
    while (cur)
    {
        if (cur->data == 0)
        {
            pre->next = cur->next;
            delete cur;
            cur = pre->next;
        }
        else
        {
            pre = cur;
            cur = cur->next;
        }
    }
}

关键是需要有一个指针指向要检查的元素和列表中的前一个元素,这样就可以在当前元素有data == 0时将其拉出。
这样做的问题是,您必须特殊对待第一个元素(因为它没有前一个元素)。
我的建议是研究这个解决方案,直到你理解它是如何工作的,然后转到@Sam Varshavchik的(更好的)解决方案并研究它--它基本上是一样的,但是以一种聪明的方式使用指针到指针,使这里的特殊情况无关紧要。

tez616oj

tez616oj3#

我在这些行上加了注解,因为如果我不加注解,并且满足了条件,它就不会执行其余的代码...
为什么if (last->data == 0)的粗略迭代出现在else中?您的输入似乎将0作为最后一项,因此在本例中它将永远不会被触发。此外,如果您希望将第一项/最后一项作为特殊情况,而不是

if (head->data == 0)
        delete_first_node();

你会想要这样的东西

while (head && head->data == 0)
        delete_first_node();

也就是说,真正的WTF是特别对待第一项/最后一项,而不是只使用一次迭代。而且,在试图访问内容之前,你并不真正检查指针是否为非空。使用C(或C++,如果你在某个时候尝试使用它),你需要在处理指针时注意内存访问。
一些随机的帮助:

  • break为0时,您需要从最后一项返回break,以退出循环,这仅仅是因为在本例中,您没有将a赋值给下一项。
  • 如果这是你的作业,这可能不是你的错,在实际项目之前从输入文件中读取大量的项目(假设它是分配的一部分)是巨大的WTF,因为你正在读取 * 一个链表 *。没有必要为任何n项目循环,当你可以简单地读取一行输入,直到文件用完。
  • 参数和返回值。你应该学习这些。
58wvjzkj

58wvjzkj4#

#include <iostream>

struct Node {
  int data;
  Node* next;
};

// Function to delete nodes with the value 0 in a singly linked list
void deleteNodes(Node** head) {
  // Edge case: empty list
  if (*head == nullptr) {
    return;
  }

  // Delete all nodes with the value 0 at the beginning of the list
  while (*head != nullptr && (*head)->data == 0) {
    Node* temp = *head;
    *head = (*head)->next;
    delete temp;
  }

  // Edge case: list with only one node
  if (*head == nullptr) {
    return;
  }

  // Delete nodes with the value 0 in the rest of the list
  Node* current = *head;
  while (current->next != nullptr) {
    if (current->next->data == 0) {
      Node* temp = current->next;
      current->next = temp->next;
      delete temp;
    } else {
      current = current->next;
    }
  }
}

int main() {
  // Create a singly linked list: 1 -> 0 -> 2 -> 0 -> 3 -> 0 -> 4
  Node* head = new Node{1, new Node{0, new Node{2, new Node{0, new Node{3, new Node{0, new Node{4, nullptr}}}}}};

  // Delete nodes with the value 0
  deleteNodes(&head);

  // Print the resulting list: 1 -> 2 -> 3 -> 4
  Node* current = head;
  while (current != nullptr) {
    std::cout << current->data << " ";
    current = current->next;
  }
  std::cout << std::endl;


  return 0;
}

希望能有所帮助

相关问题