在 C 中创建没有 malloc 的链表

Question

我正在尝试创建一个没有动态分配的链表，并用 0-8 的数字填充它，然后打印它们，但每次我尝试它都会给我随机值。

#include <stdio.h>

struct listNode
{
    int value;
    struct listNode *next;
};

int main()
{
    struct listNode list;
    struct listNode *head = &list;
    int i;

    for (i = 0; i < 9; i++)
    {
        list.value = i;
        struct listNode new;
        list.next = &new;
        list = *(list.next);
    }

    for (i = 0; i < 9; i++)
    {
        printf("%d, ", (*head).value);
        head = (*head).next;
    }

    return 0;
}

看起来它应该可以工作，但没有，我错过了什么？

Answer 1

要在没有 malloc 的情况下分配节点，也可以为此目的使用堆栈。这只是作为一个小练习很有趣，但在实际代码中是个坏主意。

这个想法是，每当必须分配一个新节点时，您就进行递归调用，然后在那里继续程序的其余逻辑，而不从该递归调用返回。只有当程序可以退出时，您才能退出递归。这不是很方便使用，会导致内存浪费，因为不仅分配的节点在该堆栈上，而且还有一些其他不再使用的数据。此外，除非您还维护一个空闲列表，否则无论何时从列表中删除节点，都不会重用 space。

再说一次，这不是最佳实践，应该真正使用堆来进行这种动态分配。我希望这个免责声明足够强大，仍然允许我 post 实现这个想法的这段代码：

#include <stdio.h>

struct listNode
{
    int value;
    struct listNode *next;
};

void printList(struct listNode *head) {
    while (head != NULL) {
        printf("%d -> ", head->value);
        head = head->next;
    }
    printf("NULL\n");
}

void deleteFromList(struct listNode **headPtr, struct listNode **tailPtr, int value) {
    while (*headPtr != NULL && (*headPtr)->value == value) {
        *headPtr = (*headPtr)->next;
    }
    if (*headPtr == NULL) {
        *tailPtr = NULL;
        return;
    }
    struct listNode *current = *headPtr;
    while (current->next != NULL) {
        if (current->next->value == value) {
            current->next = current->next->next;
        } else {
            current = current->next;
        }
    }
    *tailPtr = current;
}

void appendToList(struct listNode **headPtr, struct listNode **tailPtr, struct listNode *new) {
    new->next = NULL;
    if (*tailPtr != NULL) {
        (*tailPtr)->next = new;
    } else {
        *headPtr = new;
    }
    *tailPtr = new;
}

// This is the main program's logic, but it gets called recursively whenever a node
//   is inserted into the list:
void menu(struct listNode *head, struct listNode *tail) {
    struct listNode new;
    char choice;
    while (1) {
        printf("[i]nsert, [d]elete, [p]rint, [e]xit: ");
        scanf(" %c", &choice);
        switch(choice) {
            case 'p':
                printList(head);
                break;
            case 'i':
                printf("insert value: ");
                scanf(" %d", &new.value);
                appendToList(&head, &tail, &new);
                menu(head, tail); // Recursion
                return;
            case 'd':
                printf("delete value: ");
                scanf(" %d", &new.value);
                deleteFromList(&head, &tail, new.value); 
                break;
            case 'e':
                return;
        } 
    }
}
    
int main()
{
    menu(NULL, NULL);
    return 0;
}

在 C 中创建没有 malloc 的链表

Creating a linked list without malloc in C

c

linked-list