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

Question

Я пишу программу для односвязного списка в 'c' без использования динамического c выделения памяти. Но он уходит в бесконечность l oop. Вся программа:

#include <stdio.h>

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

typedef struct SingleLinkedList sll;

void insertAtStart(sll** head, int data)
{
    sll newNode = { data, NULL };
    newNode.data = data;
    if (*head == NULL)
    {
        *head = &newNode;
        return;
    }
    newNode.next = *head;
    *head = &newNode;
}

void insertAtEnd(sll** head, int data)
{
    sll newNode = { data, NULL };
    newNode.data = data;
    if (*head == NULL)
    {
        *head = &newNode;
        return;
    }
    sll* node = *head;
    while (node -> next != NULL)
    {
        node = node -> next;
    }
    node -> next = &newNode;
}

void insertAfterNode(sll **head, int data)
{
    int nodeNum, count = 1;
    printf("\nEnter the node number to insert after: ");
    scanf("%d", &nodeNum);
    if (*head == NULL)
    {
        printf("\nThe List is empty!\n");
        return;
    }
    sll *prevNode = *head;
    while (count < nodeNum && prevNode -> next != NULL)
    {
        prevNode = prevNode -> next;
        count++;
    }
    if (count < nodeNum)
    {
        printf("\nThere are only %d nodes in the list\n", count);
        return;
    }

    sll newNode = { data, NULL };
    newNode.next = prevNode -> next;
    prevNode -> next = &newNode;
}

int choiceSelection()
{
    int choice;
    printf("\nSelect an Option:\n");
    printf("1. Insert At Beginning\n");
    printf("2. Insert At Last\n");
    printf("3. Insert After Certain Node\n");
    printf("4. Print all nodes\n");
    printf("5. Exit\n");
    scanf("%d", &choice);
    return choice;
}

int dataEntry()
{
    int data;
    printf("\nEnter the data: ");
    scanf("%d", &data);
    return data;
}

void print(sll* node)
{
    int count = 1;
    while(node != NULL)
    {
        printf("\n----------------%d----------------\n", count);
        printf("Data: %d", node -> data);
        printf("\tAddress: %p", node);
        printf("\tNext: %p\n", node -> next);
        node = node -> next;
        count++;
    }
}

int main()
{
    sll *head = NULL;
    enum option {
        InsertAtStart = 1,
        InsertAtEnd = 2,
        InsertAfterNode = 3,
        Print = 4,
        Exit = 5,
    } choice;

    while (choice != Exit)
    {
        choice = choiceSelection();
        switch (choice)
        {
            case InsertAtStart:
                insertAtStart(&head, dataEntry());
                break;
            case InsertAtEnd:
                insertAtEnd(&head, dataEntry());
                break;
            case InsertAfterNode:
                insertAfterNode(&head, dataEntry());
                break;
            case Print:
                print(head);
                break;
            case Exit:
                break;

            default:
                printf("\nIncorrect Choice..Please choose among 1, 2, 3, 4, 5\n");
                break;
        }
    }
    printf("\nExiting!");
    return 0;
}

Результат:

Select an Option:
1. Insert At Beginning
2. Insert At Last
3. Insert After Certain Node
4. Print all nodes
5. Exit
1

Enter the data: 2

Select an Option:
1. Insert At Beginning
2. Insert At Last
3. Insert After Certain Node
4. Print all nodes
5. Exit
4

----------------1----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------2----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------3----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------4----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------5----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------6----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------7----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------8----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------9----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------10----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------11----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0

----------------12----------------
Data: 0 Address: 0x7ffe2e94c0c0 Next: 0x7ffe2e94c0c0
--------^C

Ее нужно было завершить вручную.
Кто-нибудь может сказать мне, в чем проблема? Или это невозможно без использования динамического c выделения памяти?

Answer 1

Это невозможно без динамического c распределения. Если вы не хотите использовать malloc, вы можете использовать свою собственную реализацию области распределения.

Но вы не можете использовать висячие указатели, что и делает ваша реализация.

void insertAtStart(sll** head, int data)
{
    sll newNode = { data, NULL };

newNode - это переменная со сроком хранения automati c, что означает, что она существует только до тех пор, пока функция, в которой она объявлена, не вернется (или не будет завершена иным образом).

    newNode.data = data;
    if (*head == NULL)
    {
        *head = &newNode;

Итак, теперь *head указывает на объект с автоматической c продолжительностью хранения. Но посмотрите, что происходит дальше:

        return;

Как только этот return выполняется, insertAtStart завершается, и время жизни всех его локальных переменных, включая newNode, внезапно заканчивается. И когда время жизни объекта заканчивается, так же как и удобство использования указателя на этот объект. чтобы обеспечить их соблюдение. Все просто загадочным образом терпят неудачу.

Сказать, что время жизни объекта закончилось, не означает, что память, в которой этот объект хранился, перестает существовать. На вашем компьютере нет маленьких нанороботов, которые могут создавать и разбирать физическую память. Это означает, что память больше не содержит этот объект и может (будет) использоваться повторно для других целей.

Аналогично, хотя стандарт C ясно, что указатель на завершенный объект перестает быть быть пригодным для использования («Значение указателя становится неопределенным, когда объект, на который он указывает… достигает конца своего жизненного цикла»), ничто на самом деле не мешает вам попытаться использовать указатель; проблема в том, что он может указывать на другой объект, расположенный в той же памяти. И вот что здесь происходит: в результате ваш связанный список становится круговым списком мусора.