0

我使用以下源代码创建了一个链表程序，

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
};

struct HeadNode
{
    int count;
    Node *headPtr;
};

class LinkedList
{
    public:
            LinkedList();
            ~LinkedList();

            void addToHead( int );
            bool removeFromHead();

//          bool addToTail ( int );
//          bool removeFromTail();

            void addNode ( int );
            bool deleteNode ( int );
            void deleteAllNodes();

            bool isEmpty();
            int getNoOfNodes();

            void displayAllNodes();

    private:
        int dataCmp ( int, int );
        void displayNode ( Node* );

        HeadNode head;
};

LinkedList::LinkedList()
{
    head.count = 0;
    head.headPtr = NULL;
    return;
}

LinkedList::~LinkedList()
{
    deleteAllNodes();
    return;
}

void LinkedList::addToHead ( int newData )
{
    Node *pNew = new Node;
    pNew -> data = newData;
    pNew -> next = head.headPtr;
    head.headPtr = pNew;
    head.count++;
}

bool LinkedList::removeFromHead()
{
    bool exit;
    Node *temp;

    if ( head.headPtr )
    {
        temp = head.headPtr;
        head.headPtr = head.headPtr -> next;
        delete temp;
        head.count--;
        exit = true;        // returns true if it's successful
    }
    else
        exit = false;       // returns false if it's not successful
    return exit;
}

/*
bool LinkedList::addToTail( int )
{

}
bool Linked::removeFromTail();
{

}
*/

void LinkedList::addNode ( int newData )
{
    Node *pNew = new Node,
         *pPre = NULL,
         *pCur = head.headPtr;
    pNew -> data = newData;

    while ( pCur && dataCmp( pNew -> data, pCur -> data ) >= 0 )
        {
            pPre = pCur;
            pCur = pCur -> next;
        }

    if ( pPre )
    {
        pNew -> next = pPre -> next;
        pPre -> next = pNew;
        head.count++;
    }
    else
    {
        pNew -> next = head.headPtr;
        head.headPtr = pNew;
        head.count++;
    }
}

bool LinkedList::deleteNode( int data )
{
    bool exit;
    Node *pPre = NULL,
         *pCur = head.headPtr;

    while ( pCur && dataCmp( pCur -> data, data ) < 0 )
    {
        pPre = pCur;
        pCur = pCur -> next;
    }

    if ( pCur && dataCmp( pCur -> data, data ) == 0 )
    {
        if ( pPre )
        {
            pPre -> next = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
        else
        {
            head.headPtr = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
    }
    else
        exit = false; // return false if unsuccessful

    return exit;
}

void LinkedList::deleteAllNodes()
{
    Node *temp;

    while ( head.headPtr )
    {
        temp = head.headPtr;
        head.headPtr = head.headPtr -> next;
        delete temp;
        head.count--;
    }

    return;
}

bool LinkedList::isEmpty()
{
    return head.count == 0;
}


int LinkedList::getNoOfNodes()
{
    return head.count;
}

void LinkedList::displayAllNodes()
{
    Node *pCur = head.headPtr;
    int nodeCount = 1;

    while ( pCur )
    {
        cout << "Node " << nodeCount << ": ";
        displayNode( pCur );
        cout << endl;

        nodeCount++;
        pCur = pCur -> next;
    }

    return;
}

int LinkedList::dataCmp( int value0, int value1 )
{
    int exit = 0;

    if ( value0 < value1 )
        exit = -1;
    else if ( value0 > value1 )
        exit = 1;

    return exit;
}

void LinkedList::displayNode( Node *node )
{
    cout << node -> data;
    return;
}

void printMenu()
{
    cout << "1. Add to head" << endl;
    cout << "2. Remove from head" << endl;
    cout << "3. Add node " << endl;
    cout << "4. Delete node" << endl;
    cout << "5. Delete all nodes" << endl;
    cout << "6. Is the list empty?" << endl;
    cout << "7. Get number of nodes" << endl;
    cout << "8. Display all nodes" << endl;
    cout << "9. Quit" << endl;
}

int getChoice()
{
    int choice;

    cout << "Select choice: ";
    cin >> choice;
    cin.clear();
    cin.ignore( 200, '\n' );
    return choice;
}

int getData()
{
    int data;

    cout << "Enter data: ";
    cin >> data;
    cin.clear();
    cin.ignore( 200, '\n' );

    return data;
}

void processChoice( int choice, LinkedList& list )
{
    int data;
    bool opStatus;

    switch ( choice )
    {
        case 1: data = getData();
            list.addToHead( data );
            break;
        case 2: if ( list.removeFromHead() )
            {
                cout << "Removed node from head" << endl;
            }
            else
                cerr << "List is empty" << endl;
            break;
        case 3: data = getData();
            list.addNode( data );
            cout << "Node " << data
                 << " added";
            cout << endl;
            break;
        case 4: if ( !list.isEmpty() )
            {
                data = getData();
                if ( list.deleteNode( data ) )
                {
                    cout << "Node " << data
                         << " deleted";
                    cout << endl;
                }
                else
                    cerr << "Node not found" << endl;
            }
            else
                cerr << "List is empty" << endl;
            break;
        case 5: list.deleteAllNodes();
            cout << "All nodes deleted" << endl;
            break;
        case 6: cout << ( list.isEmpty() ? 
                      "List is empty" : "List is not empty" );
            cout << endl;
            break;
        case 7: cout << "No. of nodes: "
                 << list.getNoOfNodes();
            cout << endl;
            break;
        case 8: list.displayAllNodes();
            break;
        default: cout << "Invalid choice" << endl;
    }

}

int main()
{
    LinkedList list;
    int choice;
    do
    {
        printMenu();
        choice = getChoice();

        if ( choice != 9 )
            processChoice( choice, list );

    } while ( choice != 9 );



    return 0;
}

我怎样才能修改我的代码，而不是按值删除，以便按索引删除节点？

4

3 回答 3

4

添加一个deleteNodeByIndex接受索引值的函数，然后您可以执行相同的删除操作，除了删除给定索引处的项目而不是测试值匹配。

编辑：

您已经通过其数据删除了一个节点，您已经完成了一半。唯一的区别是，不是遍历每个项目并测试数据值，而是计算在到达要删除的索引之前迭代了多少项目。

bool LinkedList::deleteNodeByIndex( int index )
{
    bool exit;
    Node *pPre = NULL,
         *pCur = head.headPtr;
    int currentIndex = 0;

    while ( pCur )
    {
        // Here we just loop until we reach our desired index.
        if (currentIndex == index)
        {
            break;
        }

        // Increment the current index and pCur to the next item.
        currentIndex++;
        pPre = pCur;
        pCur = pCur -> next;
    }

    // If pCur is still valid at this point, it means we broke at the
    // proper place and pCur should be at the proper index.
    if ( pCur )
    {
        if ( pPre )
        {
            pPre -> next = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
        else
        {
            head.headPtr = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
    }
    else
        exit = false; // return false if unsuccessful

    return exit;
}
于 2013-08-15T17:11:50.987 回答
1

如何修改我的代码，以便按索引删除节点？

除非您从列表的头部开始计算节点，否则您无法知道链表中节点的索引。例如，如果要删除列表中的第五个节点，则需要从头部开始并按照next指针，直到到达第四个节点。然后你只需要保存一个指向第五个节点的指针，将next第四个节点的设置next为第五个节点的 ，然后使用你刚刚保存的指针删除第五个节点。

于 2013-08-15T17:19:33.607 回答
1

它与按节点删除的方法相同，只是您还需要实现索引系统。

例如....在此处输入图像描述

增加大小并在每个新值之后。添加时根据大小添加新索引。

您必须了解这将是一个 0(n) 操作。与真正的链接列表 O(1) 相比，但无论如何您都在使用删除操作进行 O(n) 操作，所以谁在乎！

只是把它放在这里，因为它是一些关于使用链接列表进行索引的好信息。

链接列表信息

于 2013-08-15T17:23:45.270 回答