在沒有malloc的C中的鏈接列表

Question

#include <stdio.h> 

typedef struct node 
{ 
     int i; 
     struct node *next; 
}node; 

node getnode(int a) 
{ 
     struct node n; 
     n.i=a; 
     n.next=NULL; 
     return n; 
} 

main() 
{ 
    int i; 
    node newtemp,root,temp; 

    scanf("%d",&i); 
    root=getnode(i); 
    temp=root; 

    while(i--) 
    { 
     newtemp=getnode(i); 

     temp.next=&newtemp; 
     if(root.next==NULL) 
     { 
      root=temp; 
     } 
     temp=*(temp.next); 
    } 


    temp=root; 

    while(temp.next != NULL) 
    { 
     printf(" %d ",temp.i); 
     temp=*(temp.next); 
    } 
} 

我想創建一個不使用malloc的鏈接列表。該編程僅打印後面的根節點和沒有節點。我找不到這個bug。如果有任何內存問題，gcc編譯器會拋出一個分段錯誤。（？）請忽略不良的編程風格。

Answer 1

初始化temp.next時，指定給它的指針的值是多少？

temp.next=&newtemp; 

爲什麼，每次都是一樣的！ （如果你不服氣，畫一張圖片。）

放棄它。如果你需要一個不確定數量的內存（其中，你擁有不確定數量的節點），那麼你需要分配內存。

Answer 2

鏈接列表是不確定的長度，任何不確定的長度都不能創建malloc的。

我建議你只需使用malloc來分配鏈中的下一個鏈接。

Answer 3

您只有兩個可用於存儲節點的內存空間，它們分別是root和newtemp。當您將新節點分配給newtemp時，舊節點不再存在。

假設您輸入的號碼5在scanf函數，循環的第一次迭代之前，你必須：

5 -> NULL 

循環的第一次迭代之後，你有

5 -> 4 -> NULL 

後，第二次循環，你有

5 -> 3 -> NULL 

（節點con taining 4已被包含3的節點完全取代）。

唯一的解決辦法是使用malloc，並使getnode返回node*。

Answer 4

你能避免malloc的，但不是免費的：

• 在Linux/UNIX上，您可以調用BRK（）和寫自己的內存分配器。
• 在每個系統上，您都可以使用固定大小的數組作爲內存源來編寫自己的分配器。
• 我確實沒有看到替代品會直接購買malloc/free。他們在那裏是有原因的。
• 返回要在外部使用的局部變量將是簡單的，但是是一個錯誤，不起作用。

Answer 5

您可以靜態聲明一個節點結構數組，並從該數組中選取新節點。但是，那麼你會實施一個蹩腳的，可悲的專門的自定義分配器。可用節點的最大數量將是該數組的大小。

或者，你可以使用遞歸作爲一種分配機制，以及做事情的清單上的遞歸堆棧的底部。

這兩種方法大致相同。

Answer 6

由於還沒有人回答了有關現代C（又名C99）的精神malloc一部分這個問題。如果你的編譯器是符合你有變長數組：

node myNodes[n]; 

其中n有隻在運行時確定一定的價值。你可能不應該用這種方法過度使用它，因爲這隻限於堆棧的大小，否則你可能會遇到一個stackoverflow。

Answer 7

當然，您可以構建鏈接列表或任何其他數據結構，而無需動態內存分配。 儘管如此，不管你怎麼努力都不能分配內存。

備選：

創建一個全局或靜態存儲器池，你可以把你的對象，模仿堆/的malloc /免費。 FreeRTOS做類似的事情。 在這種情況下，你將不得不因爲你的程序和的開頭靜態分配的大內存塊將負責管理它，需要一個新的節點時返回正確的指針，並標記內存使用。

P.S .:我不會質疑你爲什麼要避免malloc。我認爲你有一個很好的理由。

在你的程序，當你這樣做，在第20行：

 node newtemp,root,temp; 

您allocatin THRE節點，其中之一， 「newtemp」。 那麼你在第28行做：

 newtemp=getnode(i); 

它只是副本在你的老「newnode」返回的節點的內容（controversal，是不是？）

所以你做什麼，只是波紋管：

 temp.next=&newtemp; 

設置一個指針，最初來自「root.next」到你的「newnode」。

 if(root.next==NULL) 

第一遍會是「NULL」，但是隻能替換相同的內容。

temp=*(temp.next); 
    { 
     root=temp; 
    } 

是，再次，複製從單一的分配對象數據， 「*（temp.next）」，另一個 「溫度」。 它不創建任何新節點。

，如果你不喜歡這一點，將工作：

#include <stdio.h> 

typedef struct node 
{ 
    int i; 
    struct node *next; 
} 
    node; 

#define MAX_NODES 10 

node *create_node(int a) 
{ 
    // Memory space to put your nodes. Note that is is just a MAX_NODES * sizeof(node) memory array. 
    static node node_pool[ MAX_NODES ]; 
    static int next_node = 0; 

    printf("[node *create_node(int a)]\r\tnext_node = %d; i = %d\n", next_node, a); 
    if (next_node >= MAX_NODES) 
    { 
     printf("Out of memory!\n"); 
     return (node *)NULL; 
    } 

    node *n = &(node_pool[ next_node++ ]); 

    n->i = a; 
    n->next = NULL; 

    return n; 
} 

int main() 
{ 
    int i; 
    node *newtemp, *root, *temp; 

    root = create_node(0); 
    temp = root; 

    for (i = 1; (newtemp = create_node(i)) && i < MAX_NODES; ++i) 
    { 
     temp->next = newtemp; 

     if (newtemp) 
     { 
      printf("temp->i = %d\n", temp->i); 
      printf("temp->next->i = %d\n", temp->next->i); 
      temp = temp->next; 
     } 
    } 


    for (temp = root; temp != NULL; temp = temp->next) 
     printf(" %d ", temp->i); 

    return 0; 
} 

輸出：

$ gcc -Wall -o list_no_malloc list_no_malloc.c 

$ ./list_no_malloc 
[node next_node = 0; i = 0)] 
[node next_node = 1; i = 1)] 
temp->i = 0 
temp->next->i = 1 
[node next_node = 2; i = 2)] 
temp->i = 1 
temp->next->i = 2 
[node next_node = 3; i = 3)] 
temp->i = 2 
temp->next->i = 3 
[node next_node = 4; i = 4)] 
temp->i = 3 
temp->next->i = 4 
[node next_node = 5; i = 5)] 
temp->i = 4 
temp->next->i = 5 
[node next_node = 6; i = 6)] 
temp->i = 5 
temp->next->i = 6 
[node next_node = 7; i = 7)] 
temp->i = 6 
temp->next->i = 7 
[node next_node = 8; i = 8)] 
temp->i = 7 
temp->next->i = 8 
[node next_node = 9; i = 9)] 
temp->i = 8 
temp->next->i = 9 
[node next_node = 10; i = 10 
Out of memory! 
0 1 2 3 4 5 6 7 8 9 

Answer 8

當使用malloc的，該「指針」到該位置被傳遞到變量（是一個指針）。

node* new = (node*)malloc(sizeof(node)); 

每次使用該代碼時都會指向一個「新」位置。相反，您使用的是正態變量，它具有「靜態」分配的內存。這意味着，無論何時您提到'temp'或'newtemp'，您都指的是每次相同的位置。

現在你告訴我如何使用3（root，temp，newtemp）內存位置來存儲10個元素的長列表。您可能想要繪製內存位置來想象發生了什麼。但請記住，每次您將「temp」稱爲同一個內存位置時。爲此，我們必須使用malloc（或calloc）來動態分配內存。在這種情況下，我們可以用少數指針（遠遠小於列表使用的內存）來做。