当列表中有两个以上的项目时，链表的函数 add 会崩溃

Question

下面列出的是我对使用链表概念的模板化类的添加函数。出于某种原因，列表中有两个对象会导致程序在运行时崩溃，而只有一个项目则不会导致问题。我已经查看代码一段时间了，但我仍然没有设法弄清楚出了什么问题。我确保为新项目动态分配内存，这样我的指针就不会指向垃圾内存。下面列出的是 MapItem 的结构以及函数 add，让你们有一个想法。

template <class keyType, class valueType>
void Map<keyType, valueType>::add(const keyType &key, const valueType &value)
{
    struct MapItem<keyType, valueType> *newItem; //create pointer to new map item
    newItem = new MapItem<keyType, valueType>; //dynamically allocate a new item on the heap
    newItem->key = key; //assign the key
    newItem->value = value; //assign the value
    if(sizeList == 0) //if linked list is empty, make newItem the HEAD
    {
        sizeList++; //increment size
        head = newItem; //set the HEAD of the list to newItem
        tail = newItem; //set the TAIL of the list to newItem
        newItem->prev = head; //previous item is the head (itself)
        newItem->next = head; //next item is the head (itself)
    }
    else //if the linked list is not empty, add it in
    {
        struct MapItem<keyType, valueType> *temp = head; //store the first element in the linked list in temp variable
        if(sizeList == 1) //if there is only one element in the list, check if they equal eachother
        {
            if(head->key != key)
            {
                tail = newItem; //assign newItem as the TAIL                
                head->next = tail; //assign the next of HEAD to the new map item
                head->prev = tail; //assign the previous of HEAD as the newItem (tail)
                tail->prev = head; //assign head to PREV of newItem (tail)
                tail->next = head; //assign HEAD to NEXT of newItem (tail)
                sizeList++; //increment size of list
            }
        //  else
        //      cout<<"Same key already exists"<<endl;
        }
        else
        {
            bool sameKey = false; //boolean value to check if the same key already exists, and if it does it will stop the loop
            int i = 1; //which item we are looking at in the list
            while(i <= sizeList && !sameKey) //while not past the end of the list, keep checking if a similar key exists
            {
                if(temp->key == newItem->key)
                    sameKey = true;
                else
                {
                    temp = temp->next; //go to the next map item
                    i++;
                }
            }
            if(!sameKey) //if the same key has not been found
            {
                temp->next = newItem; //assign newItem to NEXT of last node (temp) in our list
                newItem->prev = temp; //assign temp to PREV of newItem
                newItem->next = head; //assign HEAD to NEXT of newItem
                head->prev = newItem; //assign newItem to PREV of head
                tail = newItem; //assign newItem as the TAIL
                sizeList++;
            }
            else
                delete newItem; //deallocate memory of newItem
        }
    }
}

这是MapItem的结构：

template <class keyType, class valueType>
struct MapItem
{
    keyType key;
    valueType value;
    MapItem<keyType, valueType> *prev, *next;
};

破坏者：

template <class keyType, class valueType>
Map<keyType, valueType>::~Map()
{
    struct MapItem<keyType, valueType> *temp; //create temp variable to hold which item we are looking at in the list
    temp = head; //start at the head
    for(int i = 1; i <=sizeList; i++)
    {
        delete temp; //delete memory to pointed by temp
        if(i != sizeList) //if we are not at the last node
            temp = temp->next;
    }
}

Answer 1

我想

我明白了 - 替换行

temp->next = newItem; //assign newItem to NEXT of last node (temp) in our list

跟

tail->next = newItem; //assign newItem to NEXT of last node (temp) in our list

因为当您循环浏览项目以查找密钥时，您会回到头部 - 因此在循环完成后，"temp"指向"头部"。但是你想在最后添加。

在此更改之前，我确实在销毁过程中遇到了内存访问违规(即使我不明白为什么在删除析构函数代码后仍然出现一些错误(。

为清楚起见，析构函数代码：

~Map()
{
    struct MapItem<keyType, valueType> *temp; //create temp variable to hold which item we are looking at in the list
    temp = head; //start at the head
    for(int i = 1; i <=sizeList; i++)
    {
        MapItem<keyType, valueType> *next = temp->next;
        delete temp; //delete memory to pointed by temp
        if(i != sizeList) //if we are not at the last node
            temp = next;
    }
}