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

Question

[在此处输入 link 描述][1]所以，我正在处理的这个程序一直存在问题。我是编程新手，但我下定决心要真正学习这门语言。

我必须在程序中使用这 3 个不同的结构，所以指针真的开始让我感到困惑。该函数还必须 return 新更新 songList。这就是我到目前为止所写的内容。问题是实际上没有任何东西被删除，所以它只是在函数中被覆盖。如果有人可以展示您如何做到这一点，将不胜感激。我已经取出了一些函数和 switch 语句来压缩这个 post。主要目标是当删除功能被选中时，它会要求用户选择要删除的歌曲的索引。然后，当函数被调用时，它会将索引和歌曲列表作为参数。它将删除节点和 return 列表。

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 class，并让它为您管理指针。

The function must also return the new updated songList.

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

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

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

此外，您的 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();
}

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

Double Linked List Deleting Node with Index C++

c++

nodes

doubly-linked-list