0

我正在尝试编写一个函数，该函数使用双向链表计算第 N 个斐波那契数，但由于某种原因，当我编译和运行链表并没有停止增长时，它会一遍又一遍地添加 1 个数字而没有结束。

这应该是 SSCCE：

#include <iostream>
using namespace std;


class node {
    public:
        int value;
        node* previous;
        node* next;
};//node

class number {
    public:
        node* start;
        node* end;
        node* add (int value);
        void show (int K);
        number ();
        void destroy ();

        void copy (number gg1);
        void addition (number gg1, number gg2, int K);

        void fibonacci (int K, int times);

};//number

number::number () {
    start = NULL;
    end = NULL;
}

int power (int K) {
    int L = 1;
    for (int i = (K-1); i > 0; i--) {
        L = L*10;
    }
    return L;
}

int checksize (int value) {
    int counter = 0;
    while (value != 0) {
        value = value / 10;
        counter += 1;
    }
    return counter;
}

void number::show (int K) {
    node* current;
    cout << "\nValue:" << endl;
    if (start == NULL) {
        cout << "\nNothing\n" << endl;
    }
    if (start != NULL) {
        current = start;
        while (current != NULL) {
            if (current->value == 0) {
                for (int i = 0; i < K; i++) {
                    cout << "0";
                }
            cout << "\n";
            }
            else {
                int size = checksize (current->value);
                for (int j = size; j < K; j++) {
                    cout << "0";
                }
            cout << current->value << endl;
            }
            current = current->next;
        }   
    }
    //cout << "\n";
}

int main () {
    number gg1;
    number gg2;
    number gg3;
    const int K = 5;

    gg1.fibonacci (K, 10);
}

node* number::add(int value) {   
        node* currentcode;                   
        if (start == NULL){                    
            currentcode = new node;      
            start = currentcode;               
            end = currentcode;            
            currentcode->next =  NULL;    
            currentcode->previous = NULL;    
            currentcode->value = value;
            return currentcode;
        }
        if (start != NULL) {                    
            currentcode = new node;    
            currentcode->next = NULL;   
            end->next = currentcode;  
            currentcode->previous = end;  
            end = currentcode;          
            currentcode->value = value;
            return currentcode;
        }
         return NULL;
}

void number::addition (number gg1, number gg2, int K) {
    int value1, value2, value3;
    int carry = 0;
    node* current1;
    node* current2;
    current1 = gg1.start;
    current2 = gg2.start;
    while (current1 != NULL || current2 != NULL) {
        if (current1 != NULL && current2 !=NULL) {
            value1 = current1->value;
            value2 = current2->value;
            value3 = value1 + value2 + carry;
            current1 = current1->next;
            current2 = current2->next;
        }
        else if (current1 == NULL && current2 != NULL) {
            value3 = current2->value + carry;
            current2 = current2->next;
        }
        else if (current1 != NULL && current2 == NULL) {
            value3 = current1->value + carry;
            current1 = current1->next;
        }

        checksize(value3);
        if (value3 > power(K)) {
            value3 = value3 - 10*(power(K));
            carry = 1;
        }
        else 
            carry = 0;

        add(value3);

        if ((current1 == NULL && current2 == NULL) && (carry == 1))
            add(1);
    }
}

void number::destroy () {
    node* current;
    node* current2;
    if (start != NULL) {
        current = start;
        current2 = current->next;
        while (current2 != NULL) {
            delete current;
            current = current2;
            current2 = current->next;
        }
        delete current;
    }
}   

void number::fibonacci (int K, int times) {
    number g1;
    number g2;
    number g3;
    destroy ();

    g1.add (1);
    g2.add (1);

    g3.addition (g1, g2, K);
    g2.copy(g1);

    g1.show(K);
    g2.show(K);

        //g1.copy(g3);

        //g1.show(K);
        //g2.show(K);
        //g3.show(K);

        //g3.addition (g1, g2, K);
        //g3.show(K);
        //g2.copy(g1);
        //g1.copy(g3);

    /*for (int i = 0; i < 2; i++) {
        g3.addition (g1, g2, K);
        g3.show(K);
        g2.copy(g1);
        g1.copy(g3);
    }*/

    copy(g3);
}

void number::copy (number gg1) {
    int value;
    destroy ();
    node* current = gg1.start;
    while (current != NULL) {
        value = current->value;
        add(value);
        current = current->next;
    }
}

每当我运行斐波那契函数时，它都会在终端中给我无穷无尽的 1。数字类只是一个基本的双向链接指针列表。

添加功能独立工作得很好，副本也是如此。事实上，在此之前一切都运行良好。使用 for 循环很容易完成该功能，但这个错误阻止了我这样做。有谁知道我的错误是什么？提前致谢。

4

1 回答 1

0

现在，您有无效的内存访问，因为调用delete每个节点destroy()并不会将内存清空，而只会将内存标记为空闲。

建议修正：

void number::destroy () {
    node* current;
    node* current2;
    if (start != NULL) {
        current = start;
        current2 = current->next;
        while (current2 != NULL) {
            delete current;
            current = current2;
            current2 = current->next;
        }
        delete current;
    }
    start = NULL; // so you can't access the now non-existing list anymore.
    end = NULL;
}

评论：

  • 根据广泛采用的约定，类名应该是大写的。
  • 您不应该在复制和添加函数中按值传递类，而是通过 const-ref。
  • 在这种情况下更好地使用operator=而不是copy. copy可以是copy_fromor copy_to，调用函数copy是模棱两可的，真的。
  • 尽可能最好使用 for 循环。
  • Node不是类而是结构体，最好称其为结构体。

新代码也可以如下所示：

Number& Number::operator=(const Number& n)
{
  destroy();
  for(Node* current = gg1.start; current; current = current->next)
    add(current->value);
}

void Number::destroy() 
{
    Node* temp;
    for(Node* current = start; current; current = current->next, delete temp)
      temp = current;
    start = NULL;
    end = NULL;
}
于 2012-12-31T07:42:22.347 回答