c++ - 双链表删除带索引的节点 C++

Question

<分区>

Answer 1

I have to use these 3 different structs in the program, so the pointers are really starting to trip me up.

好吧，对于初学者来说，在 C++ 中，您确实应该使用 std::list 类，并让它为您管理指针。

The function must also return the new updated songList.

您没有返回更新列表，而是返回更新列表中的第一个节点。这本身就是多余的，因为您返回的字段与您随后将返回值分配回的字段相同。返回值不是必需的，因为调用者知道正在修改哪个列表。

The problem is nothing is actually getting deleted, so it's just being overwritten within the function.

您的 removeSong() 实现对于它需要做的事情来说过于复杂。它没有正确管理节点指针，也没有删除内存中的任何内容。

此外，您的 f 案例实际上根本没有清除列表，只是删除了第一个节点，而不考虑可能存在的后续节点，因此它们都在内存中泄漏。一个合适的清除算法需要遍历整个列表，删除每个节点。

If anyone could please show how you could do this it would be greatly appreciated.

试试这个:

#include <iostream>
#include <string>

using namespace std;

struct Song
{
    int id;
    string name;
    string singerName;
};

struct SongNode
{
    Song sg;
    SongNode *previousNode;
    SongNode *nextNode;
};

struct SongDoublyLinkedList
{
    SongNode *firstElement;
    SongNode *lastElement;
};

void addSong(SongDoublyLinkedList *songList);
void displayListElements(SongDoublyLinkedList *songList);
void displayLastElement(SongDoublyLinkedList *songList);
void removeSong(SongDoublyLinkedList *songList, int index);
void clearList(SongDoublyLinkedList *songList);

int main()
{
    SongDoublyLinkedList songList;
    songList.firstElement = NULL; 
    songList.lastElement = NULL; 
    bool question = true;

    while (question == true)
    {
        char letter;
        cout << "\nEnter the letter of what you'd like to do next: " << endl;
        cout << " a = Add a New Song" << endl;
        cout << " b = Display List of Songs" << endl;
        cout << " c = Terminate Program" << endl;
        cout << " d = Display the Last Song in the List" << endl;
        cout << " e = Delete a Certain Song" << endl;
        cout << " f = Clear all Songs" << endl;
        cin >> letter;

        switch (letter)
        {
            case 'a':
            { 
                addSong(&songList);
                break;
            }

            case 'b': 
            {
                displayListElements(&songList);
                break;
            }

            case 'c':
            {
                question = false;
                break;
            }

            case 'd':
            {
                displayLastElement(&songList);
                break;
            }

            case 'e':
            {
                int indexNumber;
                cout << "Here is ";
                displayListElements(&songList);
                cout << "Enter the index of the song you'd like to delete ";
                cout << "(First Song = 0)" << endl;
                cout << "Enter Here: ";
                cin >> indexNumber;
                removeSong(&songList, indexNumber);
                break;
            }

            case 'f':
            {
                clearList(&songList);
                break;
            }
        }
    }
    return 0;
}

void addSong(SongDoublyLinkedList *songList)
{
    SongNode *songTemp = new SongNode;
    songTemp->previousNode = NULL; // Note: Important!
    songTemp->nextNode = NULL; // Note: Important!

    cout << "Enter The New Song's ID: ";
    cin >> songTemp->sg.id;
    cout << "Enter The New Song's Name: ";
    cin >> songTemp->sg.name;
    cout << "Enter The Singer's Name: ";
    cin >> songTemp->sg.singerName;

    if (songList->firstElement == NULL)
        songList->firstElement = songTemp;

    if (songList->lastElement != NULL)
    {
        songList->lastElement->nextNode = songTemp;
        songTemp->previousNode = songList->lastElement;
    }

    songList->lastElement = songTemp;
}

void displayListElements(SongDoublyLinkedList *songList)
{
    cout << "Your List: " << endl;

    SongNode *temp = songList->firstElement;
    while (temp != NULL)
    {
        cout << temp->sg.id << endl;
        cout << temp->sg.name << endl;
        cout << temp->sg.singerName << "\n" << endl;
        temp = temp->nextNode;
    }

    cout << endl;
}

void displayLastElement(SongDoublyLinkedList *songList)
{
    SongNode *lastSong = songList->lastElement;
    if (lastSong == NULL)
    {
        cout << "Your Song List is Empty. " << endl;
        return;
    }

    cout << "Your last song was : " << endl;
    cout << lastSong->sg.id << endl;
    cout << lastSong->sg.name << endl;
    cout << lastSong->sg.singerName << endl;
}

void removeSong(SongDoublyLinkedList *songList, int index)
{
    if (songList->firstElement == NULL)
    {
        cout << "Your Song List is Empty. " << endl;
        return;
    }

    SongNode *node = songList->firstElement;
    for(int i = 0; i < index; ++i)
    {
        node = node->nextNode;
        if (node == NULL)
        {
            cout << "Invalid index. " << endl;
            return;
        }
    }

    if (node->previousNode != NULL)
        node->previousNode->nextNode = node->nextNode;

    if (node->nextNode != NULL)
        node->nextNode->previousNode = node->previousNode;

    if (songList->firstElement == node)
        songList->firstElement = node->nextNode;

    if (songList->lastElement == node)
        songList->lastElement = node->previousNode;

    delete node;
}

void clearList(SongDoublyLinkedList *songList)
{
    SongNode *node = songList->firstElement;
    songList->firstElement = NULL;
    songList->lastElement = NULL;

    while (node != NULL)
    {
        SongNode *temp = node->nextNode;
        delete node;
        node = temp;
    }
}

或者，使用 std::list:

#include <iostream>
#include <string>
#include <list>
#include <algorithm>

using namespace std;

struct Song
{
    int id;
    string name;
    string singerName;
};

typedef std::list<Song> SongList;

void addSong(SongList *songList);
void displayListElements(SongList *songList);
void displayLastElement(SongList *songList);
void removeSong(SongList *songList, int index);
void clearList(SongList *songList);

int main()
{
    SongList songList;
    bool question = true;

    while (question == true)
    {
        char letter;
        cout << "\nEnter the letter of what you'd like to do next: " << endl;
        cout << " a = Add a New Song" << endl;
        cout << " b = Display List of Songs" << endl;
        cout << " c = Terminate Program" << endl;
        cout << " d = Display the Last Song in the List" << endl;
        cout << " e = Delete a Certain Song" << endl;
        cout << " f = Clear all Songs" << endl;
        cin >> letter;

        switch (letter)
        {
            case 'a':
            { 
                addSong(&songList);
                break;
            }

            case 'b': 
            {
                displayListElements(&songList);
                break;
            }

            case 'c':
            {
                question = false;
                break;
            }

            case 'd':
            {
                displayLastElement(&songList);
                break;
            }

            case 'e':
            {
                int indexNumber;
                cout << "Here is ";
                displayListElements(&songList);
                cout << "Enter the index of the song you'd like to delete ";
                cout << "(First Song = 0)" << endl;
                cout << "Enter Here: ";
                cin >> indexNumber;
                removeSong(&songList, indexNumber);
                break;
            }

            case 'f':
            {
                clearList(&songList);
                break;
            }
        }
    }
    return 0;
}

void addSong(SongList *songList)
{
    Song songTemp;

    cout << "Enter The New Song's ID: ";
    cin >> songTemp.id;
    cout << "Enter The New Song's Name: ";
    cin >> songTemp.name;
    cout << "Enter The Singer's Name: ";
    cin >> songTemp.singerName;

    songList->push_back(songTemp);
}

void displayListElements(SongList *songList)
{
    cout << "Your List: " << endl;

    SongList::iterator iter = songList->begin();
    while (iter != songList->end())
    {
        cout << iter->id << endl;
        cout << iter->name << endl;
        cout << iter->singerName << "\n" << endl;
        ++iter;
    }

    cout << endl;
}

void displayLastElement(SongList *songList)
{
    if (songList->empty())
    {
        cout << "Your Song List is Empty. " << endl;
        return;
    }

    SongList::reverse_iterator iter = songList->rbegin();
    cout << "Your last song was : " << endl;
    cout << iter->id << endl;
    cout << iter->name << endl;
    cout << iter->singerName << endl;
}

void removeSong(SongList *songList, int index)
{
    if (songList->empty())
    {
        cout << "Your Song List is Empty. " << endl;
        return;
    }

    SongList::iterator iter = std::advance(songList->begin(), index);
    if (iter == songList->end())
    {
        cout << "Invalid index. " << endl;
        return;
    }

    songList->erase(iter);
}

void clearList(SongList *songList)
{
    songList->clear();
}