c++ - 为链表创建 "void InsertNode(int a)"和 "void DeleteNode(int a)"

Question

我正在制作一个代码，我必须插入一个带有随机数的节点并按顺序删除每个数字。我已经完成了其他功能，我正在尝试编写 void InsertNode(int a) 和 void DeleteNode(int a) 代码。当我运行它时，我得到以下结果。

50 30 20 10 70 80 60 90 100 40
50 is inserted
30 is inserted
20 is inserted
...
100 is inserted
50 is inserted
30 is inserted
20 is inserted
...
100 is inserted 50 is inserted
30 is inserted
20 is inserted
...
100 is inserted 50 is inserted
30 is inserted
20 is inserted
...
100 is inserted
Good Job!

但是结果应该是这样的:

50 30 20 10 70 80 60 90 100 40
50 is inserted
30 is inserted
20 is inserted
...
100 is inserted
10 20 30 40 50 60 70 80 90 100
Good Job!
50 is deleted
10 20 30 40 60 70 80 90 100
30 is deleted
10 20 40 60 70 80 90 100
20 is deleted
10 40 60 70 80 90 100
10 is deleted
40 60 70 80 90 100
70 is deleted
40 60 80 90 100
80 is deleted
40 60 90 100
60 is deleted
40 90 100
90 is deleted
40 100
100 is deleted
40
40 is deleted

这是全部代码。

#include <iostream>
#include <cstdlib>
#include <ctime>  
using namespace std;

class Node{
   public:
      int value;
      Node *next;
}; 

class LinkedList{ //Singly Linked List
public:
   LinkedList(){
   head=NULL;
   } 
   void SubMain(){
      bool result;   
      UniqueRandomData(10);
      CallInsertNode();
      PrintNode();
      result=CheckNode();
      CallDeleteNode(); 
   }
   void UniqueRandomData(int n){
      int i, j, k, temp;
      this->n=n;   
      x=new int[n]; 
      for(i=0; i<n; i++)x[i]=(i+1)*10; 
      for(i=0; i<n; i++){
          j=rand()%n;
          k=rand()%n;

          temp=x[j];
          x[j]=x[k];
          x[k]=temp;
      } 

      for(i=0; i<n; i++)
          cout<<x[i]<<" ";
      cout<<endl;
    }
   void InsertNode(int a){
      if (head == NULL) {
          head =  new Node();
      }
      else{
          head->next = new Node();
          head = head->next;
      }
      for(int i=0; i<n; i++){
          cout<<x[i]<<" is inserted."<<endl;
      }
   }
   void PrintNode(){
      Node *cur=head; 
      while(cur!=0){
          cout<<cur->value<<" "; 
          cur=cur->next; 
      } 
      cout<<endl;
   }
   void CallInsertNode(){
      int i;
      for(i=0; i<n; i++)      
         InsertNode(x[i]);   
   }
   bool CheckNode(){
      Node *cur=head;
      while(cur !=NULL && cur->next !=NULL)
      if(cur->value > cur->next->value){
          cout<<"Error!"<<endl;
          cout<<cur->value<<", "<<cur->next->value<<endl;
          return false;
      }
      else 
          cur=cur->next;

      cout<<"Good job!"<<endl;
      return true;
   } 
    void CallDeleteNode(){
        int i;
        for(i=0; i<n; i++){  
            DeleteNode(x[i]); 
            this->PrintNode(); 
        }
    }
     void DeleteNode(int a){
         Node* prev = this->head;
         Node* current = this->head->next;
         while(current->value != a){
             current = current->next;
             prev = prev->next;
         }
         if(current->value == a){
             prev->next = current->next;
             delete current;
         }
         for(int i=0; i<n; i++){
             cout<<x[i]<<" is deleted.";
         }
   }

   private:
       Node *head;
       int *x;
       int n;
}; 

int main(){
    LinkedList x; 
    x.SubMain(); 
    return 0; 
    //system("pause");
}

我应该如何处理 void InsertNode(int a) 和 void DeleteNode(int a) 函数？

Answer 1

这里有个bug:

      head->next = new Node();
      head = head->next;

您在 head 之后添加了一个节点(因此丢失了曾经存在的所有节点)。然后你将头向下移动一个位置。

      Before Insert is called:

            *********   *********   *********
      head->*  10   *-->*  20   *-->*  50   *--|
            *********   *********   *********

      After Insert(15) is called:

                          head
                            |
                            \/
            *********   *********         *********   *********
            *  10   *-->*   15  *--|      *  20   *-->*  50   *--|
            *********   *********         *********   *********

DeleteNote() 的另一个错误

      Before DeleteNode is called:

            *********   *********   *********
      head->*  10   *-->*  20   *-->*  50   *--|
            *********   *********   *********

然后调用 DeleteNode(10) 将不会删除头项。

另一个错误

您的类(class)没有实现三原则。

建议

以下成员确实与列表无关。

   void SubMain(){
   void UniqueRandomData(int n){
   void CallInsertNode(){
    void CallDeleteNode(){

       int *x;
       int n;

你应该把他们带出类。独立功能很好。但如果您愿意，可以将它们放在测试类中。