Verkettete Listen in C ohne malloc

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

Ich versuche, eine verknüpfte Liste zu erstellen, ohne malloc zu verwenden. Die Programmierung druckt nur die Wurzel und keine darauf folgenden Knoten. Ich konnte den Fehler nicht finden. Hätte es ein Speicherproblem gegeben, hätte der gcc-Compiler einen Segmentierungsfehler ausgelöst. (?) Bitte ignorieren Sie den schlechten Programmierstil.

Beim Initialisieren temp.nextwas ist der Wert des Zeigers, den Sie ihm zuweisen?

temp.next=&newtemp;

Warum, es ist jedes Mal dasselbe! (Zeichnen Sie ein Bild, wenn Sie nicht überzeugt sind.)

Es aufgeben. Wenn Sie eine unbestimmte Menge an Speicher benötigen (was bei einer unbestimmten Anzahl von Knoten der Fall ist), müssen Sie Speicher zuweisen.

Sie können Malloc vermeiden, aber nicht kostenlos:

• Unter Linux/UNIX könnten Sie brk() aufrufen und Ihren eigenen Speicherzuordner schreiben.
• Auf jedem System können Sie Ihren eigenen Zuordner schreiben, indem Sie ein Array fester Größe als Speicherquelle verwenden.
• Ich sehe nicht, was die Alternativen über einfach malloc/free direkt kaufen würden. Sie sind aus einem bestimmten Grund da.
• Lokale Variablen zurückzugeben, die außerhalb verwendet werden sollen, wäre einfach, ist aber ein Fehler und funktioniert nicht.

Sie haben nur zwei Speicherplätze, die Sie zum Speichern von Knoten verwenden können, und das sind root und newtemp. Wenn Sie einen neuen Knoten zuweisen newtemp der alte Knoten existiert nicht mehr.

Angenommen, Sie haben die Nummer eingegeben 5 am scanf, vor der ersten Iteration der Schleife, haben Sie:

5 -> NULL

Nach der ersten Iteration der Schleife haben Sie

5 -> 4 -> NULL

Nach der zweiten Iteration der Schleife haben Sie

5 -> 3 -> NULL

(Der Knoten, der 4 wurde vollständig durch den Knoten enthaltend ersetzt 3).

Die einzige Lösung ist zu verwenden mallocund mache getnode Rückkehr a node*.

Sie können ein Array von Knotenstrukturen statisch deklarieren und neue Knoten aus diesem Array auswählen. Aber dann hätten Sie einen lahmen, jämmerlich spezialisierten benutzerdefinierten Allokator implementiert. Und die maximale Anzahl verfügbarer Knoten entspricht der Größe dieses Arrays.

Alternativ können Sie die Rekursion als Zuordnungsmechanismus verwenden und Dinge mit der Liste am Ende des Rekursionsstapels tun.

Beide Ansätze sind ungefähr gleich klobig.

Natürlich können Sie eine verkettete Liste oder jede andere Datenstruktur ohne dynamische Speicherzuweisung erstellen. Sie können es jedoch nicht bauen, egal wie sehr Sie es versuchen, und überhaupt keinen Speicher zuweisen.

Alternative:

Erstellen Sie einen globalen oder statischen Speicherpool, in dem Sie Ihre Objekte ablegen können, indem Sie heap/malloc/free imitieren. FreeRTOS macht so etwas wie. In dieser Situation wird Ihnen seit Beginn Ihres Programms ein großer Speicherblock statisch zugewiesen und ist dafür verantwortlich, ihn zu verwalten, die richtigen Zeiger zurückzugeben, wenn ein neuer Knoten benötigt wird, und diesen Speicher als verwendet zu markieren.

PS: Ich werde nicht hinterfragen, warum Sie malloc vermeiden wollen. Ich nehme an, Sie haben einen guten Grund dafür.

In Ihrem Programm, wenn Sie dies tun, in Zeile 20:

     node newtemp,root,temp; 

Sie weisen drei Knoten zu, einer davon “newtemp”. Dann machst du in Zeile 28:

     newtemp=getnode(i); 

Es gerade Kopien den Inhalt des zurückgegebenen Knotens über Ihren alten “newnode” (umstritten, nicht wahr?)

Also tun Sie es, einfach unten:

     temp.next=&newtemp; 

Das setzt einen Zeiger, der anfänglich von “root.next” auf Ihren “newnode” kommt.

     if(root.next==NULL) 

Wird beim ersten Durchgang “NULL” sein, aber dann nur denselben Inhalt ersetzen.

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

Ist wieder, Kopieren Daten von einem einzelnen zugewiesenen Objekt, “*(temp.next)”, zu einem anderen, “temp”. Es erstellt keinen neuen Knoten.

Es funktioniert, wenn Sie so vorgehen:

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

Die Ausgabe:

        $ 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->weiter->i = 1
[node   next_node = 2; i = 2)]
temp->i = 1 temp->weiter->i = 2
[node   next_node = 3; i = 3)]
temp->i = 2 temp->weiter->i = 3
[node   next_node = 4; i = 4)]
temp->i = 3 temp->weiter->i = 4
[node   next_node = 5; i = 5)]
temp->i = 4 temp->weiter->i = 5
[node   next_node = 6; i = 6)]
temp->i = 5 temp->weiter->i = 6
[node   next_node = 7; i = 7)]
temp->i = 6 temp->weiter->i = 7
[node   next_node = 8; i = 8)]
temp->i = 7 temp->weiter->i = 8
[node   next_node = 9; i = 9)]
temp->i = 8 temp->weiter->i = 9
[node   next_node = 10; i = 10
Out of memory!
 0  1  2  3  4  5  6  7  8  9 

A linked list is something of indeterminate length, and anything of indeterminate length cannot be created without malloc.

I suggest you simply use malloc to allocate the next link in the chain.

When malloc is used, the ‘pointer’ to that location is passed on to the variable (which is a pointer).

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

Every time this code is used a “new” location is pointed to. On the contrary, you are using normal variables, which have ‘statically’ allocated memory. That implies, whenever you refer to ‘temp’ or ‘newtemp’, you are referring to the same location EACH TIME.

Now you tell me how can you store a 10 element long list using just 3 (root, temp, newtemp) memory locations. You might want to draw out memory locations to imagine what is happening. But remember, each time you call ‘temp’ its the SAME memory location. For that we must use malloc (or calloc), for dynamically allocating memory.

In that case, we can make do with few pointers (far lesser than the memory used by the list).