Почему односвязный список вставляется неправильно - PullRequest
Новая
       33

Почему односвязный список вставляется неправильно

0 голосов
/ 29 мая 2020

У меня есть один связанный список, в который я могу вставить до 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); 
}

Итак, если бы я запустил код и ввел в KQLR, вы бы увидели 

 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

Почему это происходит и как Я чиню это?

Ответы [ 2 ]

1 голос
/ 29 мая 2020

Когда вы вставляете новый узел вперед, вы обновляете заголовок: sPtr = newPtr;. Однако изменение sPtr не будет замечено вызывающим.

Для этого вам нужно объявить void insert(ListNode **sPtr, char value), и где бы вы ни использовали sPtr, теперь напишите *sPtr.

Теперь вызовите функцию, например: 

insert(&headPtr, item);
0 голосов
/ 29 мая 2020

Попробуйте это 

#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;
}
...