Dynamische Datenstrukturen in C

Dynamische Datenstrukturen in C (1)

Ursprünglich veröffentlicht auf Medium

Ich habe C vor über zehn Jahren verwendet, als ich mit dem Programmieren anfing, bin aber schnell zu anderen Sprachen gewechselt – jetzt bin ich zurück bei C.

Selbstreferenzierende Strukturen

Eine Struktur kann keine Instanzen von sich selbst enthalten, aber sie kann Zeiger auf Instanzen von sich selbst enthalten, siehe:

struct Wolf {
    int id;
    char name[32];
    struct Wolf *next;
};

Diese Struktur wird als selbstreferenzierende Struktur bezeichnet, die ein Element enthält, das ein Zeiger auf eine Instanz von sich selbst ist. Um dynamische Datenstrukturen wie eine einfach verkettete Liste zu implementieren, werde ich selbstreferenzierende Strukturen verwenden.

Beispiel: Selbstreferenzierende Strukturen

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Wolf {
    int id;
    char name[32];
    struct Wolf *next;
};

struct Wolf *AddWolf(int id, char *name){
    struct Wolf *wolf;
    wolf = (struct Wolf *)malloc(sizeof(struct Wolf));
    wolf->id = id;             /*set id*/
    strcpy(wolf->name, name);  /*set name*/
    wolf->next = NULL;         /*set next, point to NULL*/
    return wolf;
}

int main(){
    struct Wolf *alpha, *node;
    alpha = AddWolf(1, "Balto");
    alpha->next = AddWolf(2, "Steele");
    alpha->next->next = AddWolf(3, "Boris");
                  /*i know - boris isn't a dog/husky/wolf :) */
    node = alpha; /*point to alpha*/

    while(node != NULL){/*process all nodes*/
        printf("id = %d\n", node->id);
        printf("name = %s\n", node->name);
        node = node->next;
    }

    while(alpha != NULL){ /*memory handling*/
        node = alpha;
        alpha = node->next;
        free(node);
    }
    return 0;
}

Die Ausgabe dieses Beispiels für selbstreferenzierende Strukturen ist:

id = 1
name = Balto
id = 2
name = Steele
id = 3
name = Boris

Der Nullzeiger wolf->next = NULL; wird als Markierungswert verwendet, um das Ende einer Liste zu erkennen. Die erste while-Schleife verwendet die node-Variable, um einen Knoten der verketteten Liste zu erhalten. Der Wert NULL des Members next des letzten Knotens wird verwendet, um die Iteration der Schleife zu stoppen.

Einfach verkettete Liste

Wie zuvor illustriert, besteht eine verkettete Liste aus Knoten. Benachbarte Knoten sind miteinander verknüpft. Schreiben wir eine Bibliothek von Funktionen zur Verarbeitung verketteter Listen mit folgenden Listenfunktionen:

Einen Knoten erstellen Speicher verwalten Knoten voranstellen, anhängen, einfügen, finden und entfernen Die Liste leeren Ich habe die Implementierung der Liste abgeschlossen, aber die Beschreibungen fehlen noch. Ich werde sie in den nächsten Tagen hinzufügen. Stück für Stück.

list.h

/*list.h*/
#ifndef LIST_LIST_H
#define LIST_LIST_H

struct ListNode{
    int id;
    char *name;
    struct ListNode *next;
};

typedef struct ListNode *Node;

extern Node CreateNode(int id, const char *name);
extern void FreeNode(Node node);
extern void Prepend(Node *head, Node node);
extern void Append(Node *head, Node node);
extern int Insert(Node *head, Node node, int pos);
extern Node Find(Node head, int id, const char *name);
extern void Remove(Node *head, Node node);
extern void Print(Node node);
extern void PrintList(Node head);
extern void Clear(Node head);

#ifdef _CH_
#pragma importf <list.c>
#endif

#endif //LIST_LIST_H

Implementierung

CreateNode

Die Funktion CreateNode wird verwendet, um ein Listenelement – einen Knoten – zu erstellen. Der Speicher eines Knotens wird dynamisch mit malloc allokiert.

Node CreateNode(int id, const char *name){
    Node node;
    node = (Node) malloc(sizeof(struct ListNode));
    if(node == NULL){
        fprintf(stderr, "Error: not enough memory.\n");
        return NULL;
    }
    node->id = id;
    node->name = strdup(name);
    node->next = NULL;
    return node;
}

FreeNode

Diese Funktion wird verwendet, um den Speicher freizugeben, der von einem Knoten verwendet wird, der zuvor mit CreateNode erstellt wurde. Sie gibt den allokierten Speicher für name und den Knoten selbst frei.

void FreeNode(Node node){
    if(node){
        if(node->name){
            free(node->name);
        }
        free(node);
    }
}

Prepend

Die Prepend-Funktion fügt ein Element am Anfang einer Liste hinzu.

void Prepend(Node *head, Node node){
    node->next = *head;
    *head = node;
}

Append

Append kann auch verwendet werden, um ein Element zu einer Liste hinzuzufügen. Der Unterschied zwischen Append und Prepend ist, dass Append das Element am Ende der Liste hinzufügt, anstatt am Anfang. Dies ist die normale Add-Funktion, die Sie vielleicht von C#, Java oder anderen Sprachen kennen.

void Append(Node *head, Node node){
    Node tmp = *head;
    if(*head == NULL) { /*no node (empty)*/
        *head = node;
    }else{
        while(tmp->next){
            tmp = tmp->next;
        }
        tmp->next = node;
    }
}

Insert

Meiner Meinung nach ist die Insert-Funktion eine der kompliziertesten Operationen, die auf einer verketteten Liste durchgeführt werden können. Bevor Sie einfügen können, müssen Sie nach der Stelle suchen, an der der neue Knoten hinzugefügt wird, und die next-Zeiger manipulieren, damit die Verknüpfung nicht unterbrochen wird. Das Einfügen an der ersten Position wird zuerst behandelt, das ist der einfache Teil. Wenn die Einfügestelle woanders ist, führt insert() eine Suche durch, um zu prüfen, wo das neue Element eingefügt werden soll, unter Verwendung der while-Schleife. Wenn eine Einfügestelle gefunden wird, muss der Link (next-Zeiger) auf den entsprechenden Knoten gerichtet werden. Der andere Link, der ursprünglich auf diesen Knoten zeigte, muss getrennt und an das neue Element angehängt werden. Der neue Knoten ist das nächste Element von node tmp. Wenn alles gut funktioniert hat, gibt die Funktion 0 zurück, andernfalls -1.

int Insert(Node *head, Node node, int pos){
    int i = 0;
    /*tmp is the head*/
    Node tmp = *head;

    /*insert at the beginning of the list*/
    if(pos == 1){
        *head = node;
        (*head)->next = tmp;
        return 0;
    }
    /*get position*/
    while(tmp){
        /*invalid or matching position*/
        if(++i >= pos-1){
            break;
        }
        tmp = tmp->next;
    }
    if(i != pos-1){
        fprintf(stderr, "Error: can not insert at pos %d", pos);
        return -1;
    }
    /*update all links*/
    node->next = tmp->next;
    tmp->next = node;
    return 0;
}

Find

Node Find(Node head, int id, const char *name){
    while(head != NULL && /*reached last element*/
            !(head->id == id &&
                    !strcmp(head->name, name))){
        head = head->next;
    }
    /*found it: return it*/
    return head;
}

Remove

void Remove(Node *head, Node node){
    Node tmp = *head;

    /*handle empty list*/
    if(*head == NULL){
        return;
    } else if (*head == node) {
        *head = (*head)->next;
        /*give memory back to its owner (free)*/
        FreeNode(node);
    } else {
        while(tmp->next){
            /*we found the node*/
            if(tmp->next == node){
                /*unlink it*/
                tmp->next = tmp->next->next;
                /*give memory back*/
                FreeNode(node);
                return;
            }
            tmp = tmp->next;
        }
    }
}

Clear

void Clear(Node head){
    Node node;

    while(head){
        node = head;
        head = head->next;
        FreeNode(node);
    }
}

Ausgabe

void Print(Node node){
    if(node){
        printf("id = %d, name = %s\n", node->id, node->name);
    }
}

void PrintList(Node head){
    while(head){
        Print(head);
        head = head->next;
    }
}

main.c – das finale Demo-Programm

#include <stdio.h>
#include "list.h"

int main() {
    Node head, node;

    Node n1 = CreateNode(1, "A"),
         n2 = CreateNode(2, "B"),
         n3 = CreateNode(3, "C"),
         n4 = CreateNode(4, "D");

    head = NULL;
    Prepend(&head, n1);
    printf("List with one element: \n");
    PrintList(head);
    Prepend(&head, n2);
    printf("List with two elements: \n");
    PrintList(head);
    Append(&head, n3);
    printf("List with three elements: \n");
    PrintList(head);
    Insert(&head, n4, 2);
    printf("List with four elements: \n");
    PrintList(head);

    node = Find(head, 1, "A");
    Remove(&head, node);
    printf("List without A\n");
    PrintList(head);
    Clear(head);

    return 0;
}

Ausgabe:

List with one element:
id = 1, name = A
List with two elements:
id = 2, name = B
id = 1, name = A
List with three elements:
id = 2, name = B
id = 1, name = A
id = 3, name = C
List with four elements:
id = 2, name = B
id = 4, name = D
id = 1, name = A
id = 3, name = C
List without A
id = 2, name = B
id = 4, name = D
id = 3, name = C
Das nächste Thema wird die Implementierung einer doppelt verketteten Liste sein. Sie fragen vielleicht warum, aber warum nicht?