-1

编辑:

好的,这是列表的正确实现。我想很多人会发现它很有用。谢谢你们,特别是 Agent_L,他们在通讯器上帮助了我。

正确的链表实现

    #include <cstdio>
#include <cmath>
#include<iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

class Node{
 friend class List;
public:
    Node(Node* next, int wrt){
        this->next = next;
        this->wrt = wrt;
    }

    Node(const Node& obiekt){
        this->wrt = obiekt.wrt;
        this->next = obiekt.next;
    }
     //NIE MA DESTRUKTORA BO NIE ALOKUJE ZADNYCH DANYCH !!!

    void show(){
        cout<<this->wrt<<endl;
    }




 private:
    Node* next;
    int wrt;

};


class List{

public:
List(int wrt){
    this->root = new Node(NULL, wrt);
}


    List(const List& list)
{
    // jesli pusty kopiujemy
    if (list.root == NULL)
    {
        this->root = NULL;
        return;
    }

    //tworzenie nowego korzenia
    this->root = new Node(NULL, list.root->wrt);

    Node* list_currentNode = list.root;
    Node* this_currentNode = this->root;
    while (list_currentNode->next != NULL)
    {
        // tworzenie nastepnika
        Node* newNode = new Node(NULL, list_currentNode->next->wrt);
        this_currentNode->next = newNode;
        this_currentNode = this_currentNode->next;
        list_currentNode = list_currentNode->next;
    }
}


void add(int wrt){
    Node* node = new Node(NULL, wrt);
    Node* el = this->root;
    while(el->next != NULL){
        //el->show();
        el = el->next;
    }
    el->next = node;
}

void remove(int index){
    Node* el = this->root;
    if(index == 0){
       this->root = el->next;
       delete el;
    }
   else{
    int i  = 0;
    while(el != NULL && i < index - 1){

        el = el->next;
        i++;
    }
     if(el!=NULL){
        Node* toRem = el->next;
        Node* newNext = toRem->next;
        el->next = newNext;
       delete toRem;
    }
}
}

void show(){
    Node* el = this->root;
    while(el != NULL){
        el->show();
        el = el->next;
    }
}

~List(){
    Node* currentNode = this->root;
    while (currentNode != NULL)
    {
        Node* nextNode = currentNode->next;
        delete currentNode;
        currentNode = nextNode;
    }
}


private:
    Node* root;

};

int main(){
    List* l = new List(11);
    l->add(22); l->add(33);
    l->show();
    cout<<endl;
    List* lala = new List(*l);
    lala->show();
    cout<<endl;
    lala->add(44);
    cout<<"lala before remove"<<endl;
    lala->show();
    lala->remove(1);
    cout<<"l before delete"<<endl;
    l->show();
    cout<<"lala before delete"<<endl;
    lala->show();
    delete l;
  /*  cout<<"l after delete   "<<endl;
    l->show(); */
    cout<<"lala after delete"<<endl;
    lala->show();
    return 0;
   }

我已经实现了 List 并且有一个问题。我在 List 中的析构函数不能正常工作:请查看 main 并查看“l after delete”它确实向后打印 l 列表。更大的问题是内部没有删除的删除方法可以正常工作,但是当我尝试将删除 el/delete 取消注释到 Rem 时,我进入了无限循环。我已经尝试修复它 4 小时。请看一眼。

为什么当我调用 l->remove(0) 时,这些行尤其是 87(忘记 100)会导致程序崩溃?

http://wklej.org/id/761056/第 87 和 100 行

remove 方法和 List 析构函数很重要

void remove(int index){
    Node* el = this->root;
    if(index == 0){
       this->root = el->next;
    //   delete el;
    }
   else{
    int i  = 0;
    while(el != NULL && i < index - 1){

        el = el->next;
        i++;
    }
     if(el!=NULL){
        Node* toRem = el->next;
        Node* newNext = toRem->next;
        el->next = newNext;
       // delete toRem;
    }
}
}

 ~List(){
    Node* currentNode = this->root;
    while (currentNode != NULL)
    {
        Node* nextNode = currentNode->next;
        delete currentNode;
        currentNode = nextNode;
    }
}

整个代码

    #include <cstdio>
#include <cmath>
#include<iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

class Node{
 friend class List;
public:
    Node(Node* next, int wrt){
        this->next = next;
        this->wrt = wrt;
    }

    Node(const Node& obiekt){
        this->wrt = obiekt.wrt;
        this->next = obiekt.next;
    }
     //NIE MA DESTRUKTORA BO NIE ALOKUJE ZADNYCH DANYCH !!!

    void show(){
        cout<<this->wrt<<endl;
    }




 private:
    Node* next;
    int wrt;

};


class List{

public:
List(int wrt){
    this->root = new Node(NULL, wrt);
}


    List(const List& list)
{
    // jesli pusty kopiujemy
    if (list.root == NULL)
    {
        this->root = NULL;
        return;
    }

    //tworzenie nowego korzenia
    this->root = new Node(NULL, list.root->wrt);

    Node* list_currentNode = list.root;
    Node* this_currentNode = this->root;
    while (list_currentNode->next != NULL)
    {
        // tworzenie nastepnika
        Node* newNode = new Node(NULL, list_currentNode->next->wrt);
        this_currentNode->next = newNode;
        this_currentNode = this_currentNode->next;
        list_currentNode = list_currentNode->next;
    }
}


void add(int wrt){
    Node* node = new Node(NULL, wrt);
    Node* el = this->root;
    while(el->next != NULL){
        //el->show();
        el = el->next;
    }
    el->next = node;
}

void remove(int index){
    Node* el = this->root;
    if(index == 0){
       this->root = el->next;
    //   delete el;
    }
   else{
    int i  = 0;
    while(el != NULL && i < index - 1){

        el = el->next;
        i++;
    }
     if(el!=NULL){
        Node* toRem = el->next;
        Node* newNext = toRem->next;
        el->next = newNext;
       // delete toRem;
    }
}
}

void show(){
    Node* el = this->root;
    while(el != NULL){
        el->show();
        el = el->next;
    }
}

~List(){
    Node* currentNode = this->root;
    while (currentNode != NULL)
    {
        Node* nextNode = currentNode->next;
        delete currentNode;
        currentNode = nextNode;
    }
}


private:
    Node* root;

};

int main(){
    List* l = new List(10);
    l->add(12); l->add(13);
    l->show();
    cout<<endl;
    List* lala = new List(*l);
    lala->show();
    cout<<endl;
    lala->add(4);
    cout<<"lala before remove"<<endl;
    lala->show();
    lala->remove(0);
    cout<<"l before delete"<<endl;
    l->show();
    cout<<"lala before delete"<<endl;
    lala->show();
    delete l;
    cout<<"l after"<<endl;
    l->show();
    cout<<"lala after delete"<<endl;
    lala->show();
    return 0;
   }
4

3 回答 3

1

第一部分

以下三个语句导致无限循环..

l->~List();
cout<<"l after"<<endl;
l->show();

因为你的析构函数~List()错过了一个重要的声明,那就是......

this->root = NULL;

这是主要原因infinite loop。所以你的完整析构函数在这里..

 ~List()
 {
    Node* currentNode = this->root;
    while (currentNode != NULL)
    {
        Node* nextNode = currentNode->next;
        delete currentNode;
        currentNode = nextNode;
    }

    this->root = NULL;
}

第二部分

现在,您已将以上三行更新为以下...

delete l;
cout<<"l after"<<endl;
l->show;              // We should never write this line in general practice..

并考虑到您正在使用上述~List()功能。仍然程序进入 an 的原因infinite loopdelete l它将取消分配分配给 的内存l。然后你调用l->show()(并且l仍然指向一个可访问的线性地址),所以现在this->root指向一些垃圾位置,这就是为什么直到它幸运地发现while(el != NULL)条件为 NULL 之前,它将保持无限循环。

于 2012-05-27T11:34:00.470 回答
0

Ok so this is correct implementation of the List. I think many people can find it useful. Thank you guys especcially Agent_L who helped me on comunicator.

CORRECT LINKED LIST IMPLEMENTATION

    #include <cstdio>
#include <cmath>
#include<iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

class Node{
 friend class List;
public:
    Node(Node* next, int wrt){
        this->next = next;
        this->wrt = wrt;
    }

    Node(const Node& obiekt){
        this->wrt = obiekt.wrt;
        this->next = obiekt.next;
    }
     //NIE MA DESTRUKTORA BO NIE ALOKUJE ZADNYCH DANYCH !!!

    void show(){
        cout<<this->wrt<<endl;
    }




 private:
    Node* next;
    int wrt;

};


class List{

public:
List(int wrt){
    this->root = new Node(NULL, wrt);
}


    List(const List& list)
{
    // jesli pusty kopiujemy
    if (list.root == NULL)
    {
        this->root = NULL;
        return;
    }

    //tworzenie nowego korzenia
    this->root = new Node(NULL, list.root->wrt);

    Node* list_currentNode = list.root;
    Node* this_currentNode = this->root;
    while (list_currentNode->next != NULL)
    {
        // tworzenie nastepnika
        Node* newNode = new Node(NULL, list_currentNode->next->wrt);
        this_currentNode->next = newNode;
        this_currentNode = this_currentNode->next;
        list_currentNode = list_currentNode->next;
    }
}


void add(int wrt){
    Node* node = new Node(NULL, wrt);
    Node* el = this->root;
    while(el->next != NULL){
        //el->show();
        el = el->next;
    }
    el->next = node;
}

void remove(int index){
    Node* el = this->root;
    if(index == 0){
       this->root = el->next;
       delete el;
    }
   else{
    int i  = 0;
    while(el != NULL && i < index - 1){

        el = el->next;
        i++;
    }
     if(el!=NULL){
        Node* toRem = el->next;
        Node* newNext = toRem->next;
        el->next = newNext;
       delete toRem;
    }
}
}

void show(){
    Node* el = this->root;
    while(el != NULL){
        el->show();
        el = el->next;
    }
}

~List(){
    Node* currentNode = this->root;
    while (currentNode != NULL)
    {
        Node* nextNode = currentNode->next;
        delete currentNode;
        currentNode = nextNode;
    }
}


private:
    Node* root;

};

int main(){
    List* l = new List(11);
    l->add(22); l->add(33);
    l->show();
    cout<<endl;
    List* lala = new List(*l);
    lala->show();
    cout<<endl;
    lala->add(44);
    cout<<"lala before remove"<<endl;
    lala->show();
    lala->remove(1);
    cout<<"l before delete"<<endl;
    l->show();
    cout<<"lala before delete"<<endl;
    lala->show();
    delete l;
  /*  cout<<"l after delete   "<<endl;
    l->show(); */
    cout<<"lala after delete"<<endl;
    lala->show();
    return 0;
   }
于 2012-05-27T12:01:24.000 回答
0

在某些地方,您的代码不会考虑项目是否为 NULL。例如什么是根是NULL?或者这里的 toRem is NULL 是什么?(节点* toRem = el->next;节点* newNext = toRem->next;)

可能还有更多问题,但它是一个开始......

于 2012-05-27T11:25:25.067 回答