为什么单个链接的列表不能正确插入？

Question

我有一个单一的链接列表，我可以插入最多4个字符值。我的目标是让插入工作，我确实有工作，但问题是，如果链接列表的头部比其他值更大，它只会用头部来填充。

我的结构是

struct listNode {
char data; /
struct listNode *nextPtr; 
};

我有一个插入功能

    void insert(ListNode *sPtr, char value)
    {
    ListNode *newPtr; 
    ListNode *previousPtr; 
    ListNode *currentPtr; 

    newPtr = malloc(sizeof(ListNode)); // create node

    if (newPtr != NULL) { 
        newPtr->data = value; 
        newPtr->nextPtr = NULL; 
        previousPtr = NULL;
        currentPtr = sPtr;


        while (currentPtr != NULL && value >= currentPtr->data) {
            previousPtr = currentPtr; 
            currentPtr = currentPtr->nextPtr; 

        } // end while

        // insert new node at beginning of list
        if (previousPtr == NULL) {
            newPtr->nextPtr = sPtr;
            sPtr = newPtr;
        } // end if
        else { // insert new node between previousPtr and currentPtr
            previousPtr->nextPtr = newPtr;
            newPtr->nextPtr = currentPtr;
        } // end else
    } // end if
    else {
        printf("%c not inserted. No memory available.\n", value);
    } // end else
    } // end function insert

在我的打印列表中

    void printList(ListNode *currentPtr)
{
    puts("The list is:");

    // while not the end of the list
    while (currentPtr != NULL) {
        printf("%c --> ", currentPtr->data);
        currentPtr = currentPtr->nextPtr;
    } // end while

    puts("NULL\n");
} // end function printList

在我的主

int main(void)
{
ListNode *startPtr = NULL; 
ListNode *newPtr = NULL; 
ListNode *headPtr = NULL; 
unsigned int choice = 4; 
char item; 



printf("%s", "Enter a character: ");
scanf("\n%c", &item);

newPtr = malloc(sizeof(ListNode)); // create node

headPtr = newPtr; 


if (newPtr != NULL) { // is space available
    newPtr->data = item; 
    newPtr->nextPtr = NULL; 
    startPtr = newPtr;
}


printList(headPtr);

printf("%s", "Enter a character: ");
scanf("\n%c", &item);


insert(headPtr, item);


printList(headPtr);


printf("%s", "Enter a character: ");
scanf("\n%c", &item);

insert(headPtr, item);


printList(headPtr);


printf("%s", "Enter a character: ");
scanf("\n%c", &item);

insert(headPtr, item);


printList(headPtr); 
}

因此，如果我运行代码并输入K Q L R，你会看到。

 Input order:   K Q L R
 Output order:  K L Q R

但如果我输入 R Q L K 我会得到

 Input order:   R Q L K
 Output order:     R

为什么会发生这种情况，我该如何解决？

Answer 1

当你在前面插入新的节点时，你会更新头部。sPtr = newPtr;. 然而，改变的 sPtr 将不会被调用者看到。

为此，你需要声明 void insert(ListNode **sPtr, char value) 以及在任何地方使用 sPtr，现在写 *sPtr.

现在调用这样的函数。

insert(&headPtr, item);

Answer 2

试试这个

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

struct ListNode {
    char data;
    struct ListNode *next;
};

void insert(struct ListNode *head, char value) {
    // Find tail
    struct ListNode *tail = head;
    while(tail->next != NULL)
        tail = tail->next;

    tail->next = malloc(sizeof(struct ListNode));
    if(tail->next == NULL) {
        // Handle memory allocation error
        abort();
    }

    // Setup value
    tail->next->data = value;
    tail->next->next = NULL;
}

int main() {
    struct ListNode *head = malloc(sizeof(struct ListNode));
    head->data = 0;
    head->next = NULL;

    // Read in data
    for(int i = 0; i < 3; i += 1) {
        fputs("Enter a character: ", stdout); // More efficient than printf in this case

        char c;
        scanf("\n%c", &c);

        if(c == EOF) {
            fputs("Error: Invalid input\n", stderr);
            return 1;
        }

        // First iteration
        if(i == 0) {
            head->data = c;
        } else {
            insert(head, c);
        }
    }

    // Print list
    struct ListNode *current = head;
    while(current != NULL) {
        printf("%c ", current->data);
        current = current->next;
    }

    // Free list
    current = head;
    while(1) {
        if(current->next == NULL) {
            // Last item
            free(current);
            break;
        }

        struct ListNode *next = current->next;
        free(current);
        current = next;
    }

    return 0;
}