在不使用动态内存分配的情况下在c中执行单链表的问题

Question

我在'c'中编写单链表程序，没有使用动态内存分配。但它正在进入无限循环。整个程序：

#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

It needed to be terminated manually.
Can someone tell me where the problem lies? Or is it not possible without using dynamic memory allocation?

Answer 1

没有某种动态分配是不可能的。如果您不想使用 malloc，您可以使用自己的分配区域实现。

但是您不能使用悬挂指针，这是您的实现所做的。

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

newNode 是一个具有自动存储持续时间的变量，这意味着它只存在到声明它的函数 returns （或者是否则退出）。

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

所以现在*head指向一个具有自动存储期限的对象。但看看接下来会发生什么：

        return;

一旦 return 执行，insertAtStart 终止并且其所有局部变量的生命周期，包括 newNode 突然结束。当对象的生命周期结束时，指向该对象的指针的可用性也会结束。

    }
    newNode.next = *head;
    *head = &newNode;
}

我应该指出，虽然有一些规则反对您在这里所做的事情，但实际上没有任何东西试图强制执行它们。事情就是以神秘的方式失败了。

说对象的生命周期结束并不意味着存储对象的内存不复存在。您的计算机没有配备可以构建和拆卸物理内存的小型纳米机器人。这意味着内存不再包含该对象，并且可能（将）被重用于其他目的。

同样，尽管 C 标准明确指出指向已终止对象的指针不再可用 ("The value of a pointer becomes indeterminate when the object it points to… reaches the end of its lifetime.")，但实际上并没有什么能阻止您尝试使用该指针；问题是它可能指向放置在同一内存中的不同对象。这就是这里发生的事情：结果是您的链接列表最终成为垃圾循环列表。

在不使用动态内存分配的情况下在c中执行单链表的问题

Problem in executing single-linked-list in c without using dynamic memory allocation

c

memory-management

structure

linked-list

data-structures