c++ - 链表析构函数与 Valgrind 一起执行，但不单独执行

Question

我有以下结构:

class List{
public: //Functions go here
    typedef struct node{
    string data;
    node* prev;
    node* next;
}* nodePtr;

nodePtr head;
nodePtr curr;
nodePtr temp;
nodePtr tail;

List();
//~List();
    void addToEnd(string addData);
    void addToBeg(string addData);
    void DeleteList();
    //More functions not included//
};

构造函数:

List::List(){
    head = NULL;
    curr = NULL;
    temp = NULL;
    tail = NULL;
}

并删除节点:

void List::DeleteList(){
    temp = head;
    curr = head;
    while(curr != NULL){
        temp = curr->next;
        delete curr;
        curr = temp;
    }
}

其余代码接收数字并通过将数字划分为节点来对它们执行加法和乘法。我在每个列表的每个函数的末尾调用 DeleteList()。当我使用 Valgrind 运行代码时，我的输出以正确的答案完成，即使它在一些函数调用中显示“条件跳转或移动取决于未初始化的值”。

当我使用 gcc 执行程序时，我得到一个“正在释放的指针未分配”。这两种执行方式有什么区别？为什么 gcc 说指针没有分配？

添加一个节点看起来像:

void List::addToEnd(string addData){ //adds to end of linked list
    //nodePtr n = (nodePtr)malloc(sizeof(node));
    nodePtr n = new node;
    n->next = NULL;
    n->data = addData;

    if(head != NULL){
        curr = head;
        while(curr->next != NULL){
            curr = curr->next;
        }
        curr->next = n;
        n->prev = curr;
        tail = n;
    }
    else{
        n->prev = NULL;
        head = n;
        tail = n;
    }
}

编辑:完整代码供引用:

//structure for assembling doubly linked list.
#include <cstdlib>
#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <math.h>
#include <fstream>
#include <sstream>
#include <stdio.h>
#include <ctype.h>
#include <unistd.h>
using namespace std;

class List{
public: //Functions go here
    typedef struct node{
        string data;
        node* prev;
        node* next;
    }* nodePtr;

    nodePtr head;
    nodePtr curr;
    nodePtr temp;
    nodePtr tail;

    List();
    ~List();
    void addToEnd(string addData);
    void addToBeg(string addData);
    List::nodePtr returnHead();
    List::nodePtr returnNext(List::nodePtr n);
    List::nodePtr returnPrev(List::nodePtr n);
    List::nodePtr returnTail();
    void DeleteList();
    void PrintList();
    void ConvertHead();
    void DeleteNode(string delData);
    string ListValue();
    string returnValue(List::nodePtr n);
};
//Functions
List addLists(List a, List b, long long nodeLength);
List multLists(List a, List b, long long nodeLength);
string doArithmetic(string num1, string num2, string op, long long nodSiz);
string removeSpaces(string input);


int main(int argc, char** argv){

  string sentence, sent2, operation, arg1, arg2;
  long long digitCount;
  int op;

  //Takes in the first argument and finds the first double quote
  //Uses what is in the quotes as the filename
  string str (argv[1]);

  size_t firstEqual = 6;

  size_t semicolon = str.find_first_of(";");

  size_t secondEqual = semicolon + 17;

  std::string file = str.substr(firstEqual, semicolon - firstEqual);
  digitCount = stoll(str.substr(secondEqual, str.length()));

  //Opens the file designated in the argument  
  ifstream inputFile (file.c_str());

  while(getline(inputFile, sentence)){
    sent2 = removeSpaces(sentence);
    op = sent2.find_first_of("+*");
    arg1 = sent2.substr(0,op);
    arg2 = sent2.substr(op+1,string::npos);
    //cout << "arg1: " << arg1 << " arg2: " << arg2 << " Operation: " << sent2.substr(op,1) << endl;
    cout << sent2 << "=";
    cout << doArithmetic(arg1, arg2, sent2.substr(op,1), digitCount) << endl;
    }
    return 0;
}


string doArithmetic(string num1, string num2, string op, long long nodSiz){

    long long nodeSize = nodSiz;
    string numberOne = num1; //14
    string numberTwo = num2;
    string answer;

    List value1, value2, result;

    //cout << numberOne << endl;
    //assigns values as strings to value1
    if(strlen(numberOne.c_str())%nodeSize != 0){
        value1.addToEnd(numberOne.substr(0,strlen(numberOne.c_str())%nodeSize));

        for(int i=0; i < strlen(numberOne.c_str())/nodeSize; i++){
            value1.addToEnd(numberOne.substr(strlen(numberOne.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    else{
        for(int i=0; i < strlen(numberOne.c_str())/nodeSize; i++){
            value1.addToEnd(numberOne.substr(strlen(numberOne.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    //value1.PrintList();

    //cout <<numberTwo<<endl;
    //assigns values as strings to value2
    if(strlen(numberTwo.c_str())%nodeSize != 0){
        value2.addToEnd(numberTwo.substr(0,strlen(numberTwo.c_str())%nodeSize));

        for(int i=0; i < strlen(numberTwo.c_str())/nodeSize; i++){
            value2.addToEnd(numberTwo.substr(strlen(numberTwo.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    else{
        for(int i=0; i < strlen(numberTwo.c_str())/nodeSize; i++){
            value2.addToEnd(numberTwo.substr(strlen(numberTwo.c_str())%nodeSize + i*nodeSize,nodeSize));
        }
    }
    //value2.PrintList();

    if(op == "+"){ 
        result = addLists(value1, value2, nodeSize);
    }
    else{
        result = multLists(value1, value2, nodeSize);
    }

    result.ConvertHead();
    answer = result.ListValue();

    value1.DeleteList();
    value2.DeleteList();
    result.DeleteList();
    return answer;
}

List multLists(List a, List b, long long nodeLength){
    List n;
    List::nodePtr aPoint, bPoint;
    long long valueA, valueB, product;
    long long leftover = 0;
    string filler;
    long long lengthDiff;
    int counterA = 0;
    int counterB = 0;

    for(int i=0; i < nodeLength;i++) filler = "0" + filler;

    bPoint = b.returnTail();
    while(bPoint != NULL){
        //cout << "B Point" << endl;
        valueB = stoll(b.returnValue(bPoint));
        leftover = 0;
        aPoint = a.returnTail();
        counterA = 0;
        while(aPoint != NULL){
            //cout << "A Point" << endl;
            List temp;
            valueA = stoll(a.returnValue(aPoint));
            product = valueA * valueB + leftover;

            lengthDiff = to_string(product).length() - nodeLength;

            if(to_string(product).length() > nodeLength){
                temp.addToBeg(to_string(product).substr(to_string(product).length()-nodeLength,nodeLength));
                leftover = stoll(to_string(product).substr(0,lengthDiff));
            }
            else{
                temp.addToBeg(to_string(product));
                leftover = 0;
            }

            for(int i = 0; i < counterA + counterB; i++){
                temp.addToEnd(filler);
            }
            n = addLists(n,temp,nodeLength);
            temp.DeleteList();  
            aPoint = a.returnPrev(aPoint);
            counterA = counterA + 1;
        }
        bPoint = b.returnPrev(bPoint);
        counterB = counterB + 1;
    }
    if(leftover != 0) n.addToBeg(to_string(leftover));

    return n;
}



List addLists(List a, List b, long long nodeLength){
    List n;
    List::nodePtr aPoint, bPoint;
    long long valueA, valueB, sum;
    long long leftover = 0;
    long long lengthDiff;
    string input;

    aPoint = a.returnTail();
    bPoint = b.returnTail();

    while(aPoint != NULL || bPoint != NULL){
        if(aPoint != NULL) valueA = stoll(a.returnValue(aPoint));
        else valueA = 0;

        if(bPoint != NULL) valueB = stoll(b.returnValue(bPoint));
        else valueB = 0;

        sum = valueA + valueB + leftover;
        if(to_string(sum).length() > nodeLength){ 
            input = to_string(sum).substr(to_string(sum).length()-nodeLength,nodeLength);
        }
        else {
            input = to_string(sum);
        }

        lengthDiff = nodeLength-to_string(sum).length();

        if(nodeLength > to_string(sum).length()){
            for(int i=0; i < nodeLength-to_string(sum).length();i++){
                // cout << "sumLength: " << to_string(sum).length() << endl;
                input = "0" + input;
            }
        }
        n.addToBeg(input);

        if(to_string(sum).length() > nodeLength){
            leftover = stoll(to_string(sum).substr(0,to_string(sum).length() - nodeLength));
        }
        else leftover = 0;

        if(aPoint != NULL) aPoint = a.returnPrev(aPoint);
        if(bPoint != NULL) bPoint = b.returnPrev(bPoint);
        // cout << "sum: " << sum << " sum.length(): " << to_string(sum).length() << " leftover: " << leftover << endl;
        // cout << "lengthDiff: " << to_string(sum).substr(0,to_string(sum).length() - nodeLength) << endl;
    }

    if(leftover != 0) n.addToBeg(to_string(leftover));

    return n;
}

List::List(){
    head = NULL;
    curr = NULL;
    temp = NULL;
    tail = NULL;
}

List::~List(){
    temp = head;
    curr = head;
    while(curr != NULL){
        temp = curr->next;
        delete curr;
        //free(curr);
        curr = temp;
    }
    head = curr = temp = tail = NULL;
}

void List::addToEnd(string addData){ //adds to end of linked list
    //nodePtr n = (nodePtr)malloc(sizeof(node));
    nodePtr n = new node;
    n->next = NULL;
    n->data = addData;

    if(head != NULL){
        curr = head;
        while(curr->next != NULL){
            curr = curr->next;
        }
        curr->next = n;
        n->prev = curr;
        tail = n;
    }
    else{
        n->prev = NULL;
        head = n;
        tail = n;
    }
}

void List::addToBeg(string addData){ //adds to beginning of linked list
    //nodePtr n = (nodePtr)malloc(sizeof(node));
    nodePtr n = new node;
    n->prev = NULL;
    n->data = addData;

    if(head != NULL){
        curr = head;
        while(curr->prev!= NULL){
            curr = curr->prev;
        }
        curr->prev = n;
        n->next = curr;
        head = n;
    }
    else{
        n->prev = NULL;
        head = n;
        tail = n;
    }
}

List::nodePtr List::returnHead(){
    return head;
}

List::nodePtr List::returnNext(List::nodePtr n){
    return n->next;
}

List::nodePtr List::returnPrev(List::nodePtr n){
    return n->prev;
}

List::nodePtr List::returnTail(){
    return tail;
}

string List::returnValue(List::nodePtr n){
    return n->data;
}

void List::DeleteList(){
    temp = head;
    curr = head;
    while(curr != NULL){
        temp = curr->next;
        delete curr;
        //free(curr);
        curr = temp;
    }
    head = curr = tail = temp = NULL;
}

void List::ConvertHead(){
    long long convert;
    curr = head;
    convert = stoll(curr->data);
    curr->data = to_string(convert); 
}


void List::PrintList(){
    curr = head;
    while(curr != NULL){
        cout << curr->data << endl;
        curr = curr->next;
    }
}

string List::ListValue(){
    string value;
    curr = head;
    while(curr != NULL){
        value = value + curr->data;
        curr = curr->next;
    }
    return value;
}

string removeSpaces(string input){ //found on cplusplus.com
  int length = input.length();
  for (int i = 0; i < length; i++) {
     if(input[i] == ' ') input.erase(i, 1);
  }
  return input;
}

示例命令行提示符:

./a.out "input=test0.txt; digitsPerNode =3"

使用名为 test0.txt 的示例输入文件:

0*0
0+1
2*3
2*2000000000000000
2*3
1+10
10000000000000000+1
12345667890123456789 + 8765432109876543210
999999999999999999999 + 1

Answer 1

此类需要复制构造函数和赋值运算符，因为它包含指针。默认复制构造函数只复制类成员。

因此，如果从函数返回本地类实例，则结果包含指向无效节点的指针，这些节点在本地对象的销毁过程中被删除:

List multLists(List a, List b, long long nodeLength)
{
    List n;
    //... construct nodes of n      
    return n;
}

// result holds only body of returned n; nodes are already deleted
result = multLists(value1, value2, nodeSize);

具有深层对象复制的复制构造函数和赋值运算符解决了该问题:

// copy constructor
List::List(const List& l) :
    head(nullptr), curr(nullptr), temp(nullptr), tail(nullptr)
{
    for (nodePtr i = l.head; i; i = i->next)
        addToEnd(i->data);
}

// C++11 move constructor
List::List(List&& l) :
    head(l.head), curr(l.curr), temp(l.temp), tail(l.tail)
{
    // keep original object in consistent state
    l.head = nullptr;
    l.curr = nullptr;
    l.temp = nullptr;
    l.tail = nullptr;
}

// assignment operator
List& List::operator=(const List& l)
{
    if (this == &l)
        return *this;

    // for exception safety at first copy to temporary
    List tmp(l);

    // move temporary to this
    *this = move(tmp);

    return *this;
}

// C++11 move assignment operator
List& List::operator=(List&& l)
{
    if (this == &l)
        return *this;

    // free current list
    DeleteList();
    // move to this
    head = l.head;
    curr = l.curr;
    temp = l.temp;
    tail = l.tail;
    // keep original object in consistent state
    l.head = nullptr;
    l.curr = nullptr;
    l.temp = nullptr;
    l.tail = nullptr;

    return *this;
}

开始添加也应该是固定的:

void List::addToBeg(string addData){ //adds to beginning of linked list
    nodePtr n = new node;
    n->prev = NULL;
    n->data = addData;

    if(head != NULL){
        n->next = head;
        head->prev = n;
        head = n;
    }
    else{
        n->next = NULL;
        head = n;
        tail = n;
    }
}

---

其他备注

由于项目编译需要 C++11，因此使用 nullptr 而不是 NULL。

看起来 addToEnd() 可能会被优化。不需要 while 循环来查找最后一个列表项，因为有 tail 指针。

在函数调用期间避免深度对象复制是有意义的。最好传递常量引用:

List multLists(const List& a, const List& b, long long nodeLength)

当然，这里的代码应该调整为正确使用 const 限定符。