Я пишу код на C ++ для двусвязного списка. Я новичок в C ++, так что прости меня за этот вопрос. Я заполняю двусвязный список числами (1,2,3, ..., n). Сначала я использую функцию поиска и нахожу узел, содержащий значение, которое я хочу удалить. Затем я вызываю функцию удаления, чтобы удалить узел. Кажется, моя функция удаления удаляет больше, чем один узел, и я ломал голову, пытаясь понять это. Я думаю, это может быть потому, что в моем классе 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;
}