0

出于学术目的，我正在尝试开发一个小小的“文字冒险游戏”。我必须自己实现所有数据结构。现在，我在实现通用（模板）LinkedList 时遇到了一些问题。

具体来说，此数据结构适用于所有内容（原始数据类型和自定义对象）但字符串！（标准库字符串）。

当我尝试将字符串添加到列表时，应用程序崩溃并出现以下错误（在控制台中）：

“在抛出 'std::logic_error' what() 的实例后调用终止：basic_string::_S_constructor null 无效”

该列表被实现为使用头节点作为首尾节点的“双链表”

这里的代码（“抽象”列表接口）：

#ifndef LIST_H_
#define LIST_H_

template <class T>
class List
{
public:
 virtual ~List() {}
 virtual T get(int position) = 0;
 virtual List* add(T item) = 0;
 virtual List* insert(T item, int position) = 0;
 virtual List* remove(int position) = 0;
 virtual int size() const = 0;
 virtual bool isEmpty() const = 0;

protected:

private:

};

#endif /* LIST_H_ */

这是 LinkedList 实现（“节点”类）：

#include "List.h"
#include <stdlib.h>

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

template <class T>
class ListNode
{
public:
ListNode(T item)
{
    mItem = item;
    mNext = NULL;
    mPrev = NULL;
}

ListNode(T item, ListNode<T>* next, ListNode<T>* prev)
{
    mItem = item;
    mNext = next;
    mPrev = prev;
}


~ListNode()
{
    delete &mItem;
}


T getItem()
{
    return mItem;
}


ListNode<T>* getNext()
{
    return mNext;
}


ListNode<T>* getPrev()
{
    return mPrev;
}


void setItem(T item)
{
    mItem = item;
}


void setNext(ListNode<T>* next)
{
    mNext = next;
}


void setPrev(ListNode<T>* prev)
{
    mPrev = prev;
}

protected:
private:
T mItem;
ListNode<T> *mNext, *mPrev;
};

链表类：

template <class K>
class LinkedList : public List<K>
{
public:
LinkedList()
{
    mSize = 0;
    mFirstNode = NULL;
}

~LinkedList()
{
    // implementazione distruttore tramite ciclo sui nodi
}

K get(int position)
{
    K item = NULL;

    ListNode<K>* targetNode = getNodeAtPosition(position);
    if (targetNode != NULL) item = targetNode->getItem();

    return item;
}

List<K>* add(K item)
{
    if (mFirstNode == NULL)
    {
        mFirstNode = new ListNode<K>(item);
        mFirstNode->setNext(mFirstNode);
        mFirstNode->setPrev(mFirstNode);
    }
    else
    {
        ListNode<K>* newNode = new ListNode<K>(item, mFirstNode, mFirstNode->getPrev());
        mFirstNode->getPrev()->setNext(newNode);
        mFirstNode->setPrev(newNode);
    }

    mSize++;
    return this;
}

List<K>* insert(K item, int position)
{
    ListNode<K>* targetNode = getNodeAtPosition(position);

    if (targetNode != NULL)
    {
        ListNode<K>* newNode = new ListNode<K>(targetNode->getItem(), targetNode->getNext(), targetNode);
        targetNode->setItem(item);
        targetNode->setNext(newNode);

        mSize++;
    }

    return this;
}

List<K>* remove(int position)
{
    ListNode<K>* targetNode = getNodeAtPosition(position);
    if (targetNode != NULL)
    {
        targetNode->setItem(targetNode->getNext()->getItem());
        targetNode->setNext(targetNode->getNext()->getNext());

        //delete targetNode->getNext();
        mSize--;
    }

    return this;
}

int size() const
{
    return mSize;
}

bool isEmpty() const
{
    return (mFirstNode == NULL) ? true : false;
}

protected:
ListNode<K>* getNodeAtPosition(int position)
{
    ListNode<K>* current = NULL;

    if (mFirstNode != NULL && position < mSize)
    {
        current = mFirstNode;

        for (int i = 0; i < position; i++)
        {
            current = current->getNext();
        }
    }

    return current;
}

private:
     int mSize;
     ListNode<K>* mFirstNode;
};

 #endif /* LINKEDLIST_H_ */

建议？

4

3 回答 3

5

Part of your problem is here:

ListNode(T item)
{
    mItem = item; // for a std::string, this will be a class member, non-pointer
    mNext = NULL;
    mPrev = NULL;
}

ListNode(T item, ListNode<T>* next, ListNode<T>* prev)
{
    mItem = item; // same here
    mNext = next;
    mPrev = prev;
}


~ListNode()
{
    delete &mItem; // you are attempting to delete an item you never created
}

You should either change your constructors to create a T* object on the heap (which will then be deleted in your destructor), or remove the delete line from your destructor.

This problem will be evident with far more than just std::string, by the way.

于 2013-08-20T19:38:49.073 回答
3

Somewhere in your program you are doing this:

std::string s(nullptr);

Calling std::string's constructor with a null pointer is causing it to throw a std::logic_error exception.

From the standard:

§ 21.4.2

basic_string(const charT* s, size_type n, const Allocator& a = Allocator());

Requires: s shall not be a null pointer and n < npos.

于 2013-08-20T19:37:50.733 回答
0

似乎不可能将 std::string 作为模板参数传递......

字符串作为模板参数

现在我使用“旧” - char const* - 来实现预期的结果，即使我现在必须实现我个人的“utils”方法来处理这些指针......

于 2013-08-21T17:33:07.027 回答