为什么我的双向链表删除功能会删除多个节点?

我正在用C ++语言编写一个双向链表的代码。我是C ++的初学者,所以请原谅我提出这个要求。我正在用数字(1,2,3,...,n)填充双向链表。我首先使用搜索功能,然后找到包含要删除的值的节点。然后,我调用remove函数以删除节点。我的删除功能似乎要删除多个节点,而我一直在努力寻找答案。我认为这可能是因为我的DList类没有析构函数,但由于要删除的结构是ListNode,因此我不确定如何实现它。任何见解将不胜感激。谢谢。

例如。测试用例n = 8

删除前列表:1 2 3 4 5 6 7 8

删除后列表:7

DLIST.H

#ifndef DLIST_H
#define DLIST_H

struct ListNode 
{
  /* define your list node type */
  int val;
  ListNode* next;
  ListNode* prev;
};

class DList
{
  public:
  DList();
  /* implement copy constructor, assignment, destructor if needed */
  void add_to_front(int value);
  void add_to_back(int value);
  int first();
  int last();
  void remove(ListNode* node);
  void display();
  ListNode* previous(ListNode* node);
  ListNode* next(ListNode* node);
  ListNode* search_value(int value);

  private:
  /* declare your data */
  ListNode* head;
  ListNode* tail;
};

#endif

DLIST.CC

#include "dlist.h"
#include <cstddef>
#include <cstdlib>
#include <cstdio>
#include <iostream>

      //ListNode* head;
      //ListNode* tail;

      DList::DList(){
         head = NULL;
         tail = NULL;
      }

      void DList::add_to_front(int value){ 
         if (head != NULL){
            //std::cout<<"addfront1\n";
            ListNode *newhead = new ListNode();
            newhead->val = value;
            //std::cout<<"addfront1 val" << newhead->val << "\n";
            newhead->next = head;
            newhead->prev = NULL;
            head->prev = newhead;
            head = newhead;
         }else{
            //std::cout<<"addfront2\n";
            ListNode *newhead = new ListNode();
            newhead->val  = value; 
            //std::cout<<"addfront2 val" << newhead->val << "\n";
            newhead->prev = NULL; 
            newhead->next = NULL;
            head = newhead;   
            tail = newhead;
         }
      }    

      void DList::add_to_back(int value){
         if (tail != NULL){
            //std::cout<<"addback1\n";
            ListNode *newtail = new ListNode();
            newtail->val = value;
            //std::cout<<"addback1 val" << newtail->val << "\n";
            newtail->next = NULL;
            newtail->prev = tail;
            tail->next = newtail;
            tail = newtail;
         }else{
            //std::cout<<"addback2\n";
            ListNode *newtail = new ListNode();
            newtail->val = value;
            //std::cout<<"addback2 val" << newtail->val << "\n";
            newtail->prev = NULL;
            newtail->next = NULL;
            tail = newtail;
            head = newtail;
         }
      }

      int DList::first(){
         return head->val;
      }

      int DList::last(){
         return tail->val;
      }

      void DList::remove(ListNode* node){

         std::cout << "want to del value is " << node->val  << "\n";
         ListNode *toDelete = new ListNode();
         if (head == NULL || tail == NULL){
            return;
         }

         if(head->val == node->val){
            toDelete = head;
            head = node->next;
            if (head != NULL){
               head->prev = NULL;
            }
            std::cout << "del1 value is " << toDelete->val  << "\n";
            delete(toDelete);
         }else if(tail->val == node->val){
            toDelete = tail;
            tail = node->prev;
            std::cout << "del2 newtail value is " << node->prev->val  << "\n";
            if (tail != NULL){
               tail->next = NULL;
            }
            std::cout << "del2 value is " << toDelete->val  << "\n";
            delete(toDelete);
         }else if (node != NULL){
            std::cout << "node1 value is " << node->val  << "\n";
            node->prev->next = node->next;
            node->next->prev = node->prev;
            std::cout << "node2 value is " << node->val  << "\n";
            delete(node);
         }
      }

      ListNode* DList::previous(ListNode* node){
         if(node->prev != NULL){
            return node->prev;
         }else{
            return node;
         }
      }

      ListNode* DList::next(ListNode* node){
         if(node->next != NULL){
            return node->next;
         }else{
            return node;
         }
      }

      ListNode* DList::search_value(int value){
         //std::cout << "head.0\n";
         //std::cout << "head value is " << head->val  << "\n";
         while(head->next != NULL){
            //std::cout << "head.1\n";
            if(head->next->val == value){
               //std::cout << "head.2\n";
               return head->next;
            }else{
               //std::cout << "head.3\n";
               head = head->next;
            }
         }
         if (head->next == NULL){
            if (head->val == value){
               return head;
            }else{
               //std::cout << "error\n";
            }
         }

      }

      void DList::display(){
         std::cout<<"Element In The Linked List Are : ";
         ListNode *disp= new ListNode;
         disp = head;
         while(disp!=NULL)
         {
             std::cout<<" "<<disp->val;
             if(disp->next==NULL)
             {
                 std::cout<<"\n";
                 break;
             }
             disp=disp->next;
         }
      }

DLIST_TEST.CC

#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <iomanip>
#include "dlist.h"
using namespace std;

int main (int argc, char* argv[])
{
  int N = -1;
  if (argc == 2) {
    N = atoi (argv[1]);
    assert (N > 0);
  } 
  //cout << "N is " << N << "\n";
  DList testList = DList();
  int i = 0;
  while(i<N){
    //cout << "i value is "<< i << "\n";
    testList.add_to_back(i+1);
    //cout << "second\n";
    i++;
  }
  int randn = rand() % N + 1;// randn in the range 1 to N
  cout << "randn is "<< randn <<"\n";
  testList.display();
  clock_t t1,t2;
  t1=clock();

  ListNode* loc = testList.search_value(randn);
  cout << "loc value is "<< loc->val <<"\n";
  testList.remove(loc);

  t2=clock();

  float diff ((float)t2-(float)t1);
  float seconds = diff / CLOCKS_PER_SEC;
  cout<<"\nTime taken by function: "<<seconds<<" seconds\n" << endl;  

  testList.display();
  testList.add_to_front(N);
  testList.display();


  return 0;
}
评论