C 链表使用指针removeLast

Question

我正在学习如何用c语言创建链表，我遇到了一个我不知道如何解决的问题。我的链表的 removeLast(link * ptr) 方法遇到问题，我相信这与我使用指针有关，但我真的不明白为什么程序无法从列表中删除下一个最后一个元素，不知怎的，我的 list 被毁了。这是我的代码:

#include <stdio.h>
#include <stdlib.h>

// typedef is used to give a data type a new name
typedef struct node * link ;// link is now type struct node pointer

/*
    typedef allows us to say "link ptr"
    instead of "struct node * ptr"
*/

struct node{
    int item ;// this is the data
    link next ;//same as struct node * next, next is a pointer
};

//prints the link
void printAll(link ptr){
    printf("\nPrinting Linked List:\n");
    while(ptr != NULL){
        printf(" %d ", (*ptr).item);
        ptr = (*ptr).next;// same as ptr->next
    }
    printf("\n");
}

//adds to the head of the link
// link * ptr so that we may modify the head pointer
void addFirst(link * ptr, int val ){
    link tmp = malloc(sizeof(struct node));// allocates memory for new node
    tmp->item = val;
    tmp->next = * ptr;
    * ptr = tmp;
}

// removes and returns the last element in the link
// link * ptr so that we may modify the head pointer
link removeLast(link * ptr){

    if(ptr == NULL) return NULL;

    // traverse the link
    link prev = NULL;// prev is pointer
    while((*ptr)->next != NULL){
        prev = *ptr;
        *ptr = (*ptr)->next;
    }

    // if only one node on list
    if(prev == NULL){
        link tmp = malloc(sizeof(struct node));// allocates memory for new node
        tmp = *ptr;
        *ptr = NULL;
        return tmp;
    }

    // if more than one node
    prev->next = NULL;
    return *ptr;
}

// testing
int main(void) {

    link head = NULL;// same as struct node * head, head is a pointer type

    //populating list
    for(int i = 0; i<10; i++){
        addFirst(&head, i);// "&" is needed to pass address of head
    }

    printAll(head);

    while(head != NULL){
        link tmp = removeLast(&head);
        if(tmp != NULL)
            printf(" %d ", tmp->item);
    }

    return 0;
}

这是我的输出:

    Printing Linked List:
     9  8  7  6  5  4  3  2  1 
    prev = 9
    prev = 8
    prev = 7
    prev = 6
    prev = 5
    prev = 4
    prev = 3
    prev = 2
     0  0 
    RUN SUCCESSFUL (total time: 136ms)

感谢您的时间和帮助。

Answer 1

您将指针传递给 head至removeLast() (参数ptr)。在该函数中，您修改 *ptr .

自 ptr指向 head 所在的内存位置变量生命，修改*ptr修改head的内容。由于head的内容通过函数调用修改它并不引用函数返回后列表的实际头部。

为了避免这种情况，您应该在 removeLast() 中使用单独的局部变量遍历列表并仅修改 *ptr当你真正想要改变时head .