c++ - 通过引用调用时链表头指针未更新

Question

我编写了两个函数来在链表中插入节点。当一个函数 (insertNth) 更新头指针时，第二个函数 (sortedInsert) 不会在函数调用之间更新头指针。 push 函数正在引用头指针。

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

void printList(node *head)
{
    node *current = head;

    while(current!=NULL)
    {
        cout<<current->data<<" ";
        current = current->next;
    }

}

void push(node* &head, int data)
{
    node *newNode = new node();

    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

void insertNth(node *&head, int index, int val)
{
    node *current = head;

    int cnt = 0;

    while(current!=NULL)
    {
        if(cnt == index)
        {
            if(cnt==0)
            {
                push(head, val);
            }
            else
            {
                push(current->next, val);
            }
        }
        current=current->next;
        cnt++;
    }
}

void sortedInsert(node *head, int val)
{
    node *current = head;

    if(head != NULL && val < head->data)
    {
        node *newNode = new node();

        push(head,val);

        return;
    }

    while(current!=NULL)
    {
        if(current->data < val && current->next->data > val)
        {
            push(current->next, val);
            return;

        }
        current = current->next;
    }
}

int main()
{
    node *head;

    push(head, 3);
    cout<<"\n";
    printList(head);

    cout<<"\nInsertNth: ";
    insertNth(head,0, 2);
    printList(head);

    cout<<"\nsortedInsert: ";
    sortedInsert(head, 1);
    printList(head);

    return 0;
}

我得到以下输出:

3 
InsertNth: 2 3 
sortedInsert: 2 3 

为什么第三行不打印1 2 3？

//更新//

正确的 SortedInsert 如下:

void sortedInsert(node *&head, node *newNode)
{
    node *current = head;

    if(head == NULL || newNode->data < head->data)
    {

        newNode->next = head;
        head = newNode;

        return;
    }

    while(current!=NULL && current->next != NULL)
    {
        if(current->data < newNode->data && current->next->data > newNode->data)
        {

            newNode->next = current->next;
            current->next = newNode;

            return;

        }

        current = current->next;
    }
    if(current->next == NULL)
    {
        current->next = newNode;
        newNode->next = NULL;
    }
}

Answer 1

要求 sample 。请注意，我是作为模板来做的，但是您可以跳过模板业务，您可以使用 struct node * 而不是 T*。这不是通用目的，但可能更容易理解。

template <class T>
class MyLinkedList {
    class Entry {
    public:
        Entry * previous;
        Entry * next;
        T * node;
    }

    Entry * head;
    Entry * tail;

    void push(T * nodeToPush) { pushBefore(head, nodeToPush); }
    void insertNth(int whereToInsert, T * nodeToInsert) {
         ... find the nth Entry pointer
         pushBefore(head, nodeToPush);
    }

private:
    void pushBefore(Entry *entry, T * nodeToPush) {
        Entry *newEntry = new Entry();
        newEntry->node = nodeToPush;
        if (entry != NULL) {
            newEntry->previous = entry->previous;
        }
        newEntry->next = entry;
        entry->previous = newEntry;
        if (head == entry) {
            head = newEntry;
        }
        if (tail == NULL) {
            tail = newEntry;
        }
    }

    // Other methods as necessary, such as append, etc.
}

除了传递指向您要插入到链表中的对象的指针之外，在任何时候您都不必以您的方法也会对这些指针产生副作用的方式来传递指针。该类应该知道如何管理一个类，并且没有奇怪的变量传递。

对你的论点进行副作用应该非常谨慎。如果您将一个对象传递给一个方法，那么操作该对象是公平的。但我真的不喜欢传递指针和让方法自己修改指针。

这会导致(充其量)困惑。

注意:我没有测试这段代码。它可能不是很完美。