在链表尾部插入

Question

我正在编写一个程序来熟悉 linked 列表，当试图在列表末尾插入一个新的 link 时，该值似乎没有存储。我认为这与局部变量有关，不会保存到传递给函数的变量。

有问题的函数：

int insertAtTail(int intBeingAdded, List *userList){
    while(userList->next != NULL){
        userList = userList->next;
    }
    List *newLink = (List *)malloc(sizeof(List));
    userList->next = newLink;
    newLink->next = NULL;
    newLink->value = intBeingAdded;
    return 1;
}

整个文件：

#include "stdio.h"
#include "stdlib.h"

typedef struct list{
    int value;
    struct list * next;
} List;

List * initIntegerList(void);
int insertAtHead(int intBeingAdded, List *userList);
int insertAtTail(int intBeingAdded, List *userList);
void printList(List *userList);

int main(void){
    List *myList;
    myList = initIntegerList();
    insertAtHead(2, myList);
    insertAtHead(1, myList);
    insertAtTail(6, myList);
    printList(myList);
    freeList(myList);
}

List * initIntegerList(void){
    List * listPointer = (List *)malloc(sizeof(List));
    if(listPointer != NULL){
        listPointer->next = NULL;
        return listPointer;
    }else{
        printf("Memory not available for allocation\n");
        return listPointer;
    }
}

int insertAtHead(int intBeingAdded, List *userList){
    List *previousHead = (List *)malloc(sizeof(List));
    if(previousHead != NULL){
        previousHead->value = intBeingAdded;
        previousHead->next = userList->next;
        userList->next = previousHead;
        return 1;
    }
    return 0;
}

int insertAtTail(int intBeingAdded, List *userList){
    while(userList->next != NULL){
        userList = userList->next;
    }
    List *newLink = (List *)malloc(sizeof(List));
    userList->next = newLink;
    newLink->next = NULL;
    newLink->value = intBeingAdded;
    return 1;
}

void printList(List *userList){
    printf("Values in list: ");
    List *currentLink = userList;
    while(currentLink->next != NULL){
        printf(" %d", currentLink->value);
        currentLink = currentLink->next;
    }
    printf("\n");
}

我看到的输出仅存储了 0、1、2，而 6 没有成功。

Answer 1

打印列表时：

while(currentLink->next != NULL){

到达最后一个节点时停止，不打印其内容。你反而想要：

while(currentLink != NULL){

此外，您的列表开头有一个虚拟条目。当您打印列表时，您想跳过那个。

List *currentLink = userList->next;

Answer 2

您的列表以头节点不包含值的方式构建。它是一个虚拟节点。另一方面，最后一个节点总是包含等于 NULL 的数据成员 next。

所以函数中的这个条件printList

while(currentLink->next != NULL){

不输出最后一个节点的值。

函数可以这样写

void printList( const List *userList )
{
    printf("Values in list: ");

    if ( userList != NULL )
    {
        for ( const List *currentLink = userList->next; 
              currentLink != NULL;
              currentLink = currentLink->next )
        {
            printf( " %d", currentLink->value );
        }
    }

    printf("\n");
}

注意，将虚拟节点作为头节点是个坏主意。头节点应该设置为 NULL。

在链表尾部插入

Inserting at tail of linked list

c

struct

linked-list

singly-linked-list