Elegante Umsetzung der zirkularen Liste in C-einzeln verknüpft?

Question

Wenn man durch klassische Datenstrukturen und haben an den verlinkten lists.Just gestoppt implementiert eine kreisförmige einfach verknüpften Liste, aber ich bin unter Eindruck überwältigend, dass diese Liste in einer elegantere Art und Weise zum Ausdruck gebracht werden könnte, remove_node Funktion im Besonderen. Wenn man bedenkt, Effizienz und die Lesbarkeit des Codes, könnte jemand anwesend eine präzise und effiziente Lösung für die einfach verkettete Kreis Liste?

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


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


struct list{
    struct node* head;
};


struct node* init_node(int value){
    struct node* pnode;
    if (!(pnode = (struct node*)malloc(sizeof(struct node)))){
        return NULL;
    }
    else{
        pnode->value = value;   
    }
    return pnode;
}

struct list* init_list(){
    struct list* plist;
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){
        return NULL;        
    }
    plist->head = NULL;
    return plist;
}


void remove_node(struct list*a plist, int value){

    struct node* current, *temp;
    current = plist->head;
    if (!(current)) return; 
    if ( current->value == value ){
        if (current==current->next){
            plist->head = NULL; 
            free(current);
        }
        else {
            temp = current;
            do {    
                current = current->next;    
            } while (current->next != plist->head);

            current->next = plist->head->next;
            plist->head = current->next;
            free(temp);
        }
    }
    else {
        do {
            if (current->next->value == value){
                temp = current->next;
                current->next = current->next->next;
                free(temp);
            }
            current = current->next;
        } while (current != plist->head);
    }
}

void print_node(struct node* pnode){
    printf("%d %p %p\n", pnode->value, pnode, pnode->next); 
}
void print_list(struct list* plist){

    struct node * current = plist->head;

    if (!(current)) return;
    if (current == plist->head->next){
        print_node(current);
    }
    else{
        do {
            print_node(current);
            current = current->next;

        } while (current != plist->head);
    }

}

void add_node(struct node* pnode,struct list* plist){

    struct node* current;
    struct node* temp;
    if (plist->head == NULL){
        plist->head = pnode;
        plist->head->next = pnode;
    }
    else {
        current = plist->head;
        if (current == plist->head->next){
            plist->head->next = pnode;
            pnode->next = plist->head;      
        }
        else {
            while(current->next!=plist->head)
                current = current->next;

            current->next = pnode;
            pnode->next = plist->head;
        }

    }
}

Answer 1

Werfen Sie einen Blick auf die kreisförmige verkettete Liste in der Linux-Kernel-Quelle:

Answer 2

Listenverarbeitung (insbesondere von Kreislisten) wird viel einfacher, wenn Sie die Liste Kopf wie ein Element der Liste (ein so genannten „Sentinel“) zu behandeln. Viele Sonderfälle einfach verschwinden. Sie können einen Dummy-Knoten für den Sentinel verwenden, aber wenn der nächste Zeiger zunächst in der Struktur ist, müssen Sie nicht einmal das tun müssen. Der andere große Trick ist, einen Zeiger auf den nächsten Zeiger des vorherigen Knoten zu halten (so können Sie es später ändern), wenn Sie die Liste ändern. Dass sie alle zusammen, Sie erhalten diese:

struct node* get_sentinel(struct list* plist)
{
    // use &plist->head itself as sentinel!
    // (works because struct node starts with the next pointer)
    return (struct node*) &plist->head;
}

struct list* init_list(){
    struct list* plist;
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){
        return NULL;        
    }
    plist->head = get_sentinel(plist);
    return plist;
}

void add_node_at_front(struct node* pnode,struct list* plist){
    pnode->next = plist->head;
    plist->head = pnode;
}

void add_node_at_back(struct node* pnode,struct list* plist){
    struct node *current, *sentinel = get_sentinel(plist);

    // search for last element
    current = plist->head;
    while (current->next != sentinel)
        current = current->next;

    // insert node
    pnode->next = sentinel;
    current->next = pnode;
}

void remove_node(struct list* plist, int value){
    struct node **prevnext, *sentinel = get_sentinel(plist);
    prevnext = &plist->head; // ptr to next pointer of previous node
    while (*prevnext != sentinel) {
        struct node *current = *prevnext;
        if (current->value == value) {
            *prevnext = current->next; // remove current from list
            free(current); // and free it
            break; // we're done!
        }
        prevnext = &current->next;
    }
}

void print_list(struct list* plist){
    struct node *current, *sentinel = get_sentinel(plist);
    for (current = plist->head; current != sentinel; current = current->next)
        print_node(current);
}

Ein paar Anmerkungen:

• Ich denke, die Funktion remove einstellen nicht richtig die Kreislistenzeiger, wenn Sie den Knoten Kopf löschen und die Liste ist größer als 3 Elemente. Da die Liste kreisförmig haben Sie den letzten Knoten in der Liste auf den neuen Kopf zeigen.
• könnten Sie in der Lage sein, die Funktion remove etwas zu verkürzen, indem eine „find_node“ Funktion zu schaffen. Da die Liste kreisförmig ist, wird es jedoch immer noch der Fall sein Rand der Kopfknoten des Löschens, die als in einer nicht-zirkularen Liste komplexer sein wird.
• -Code „Schönheit“ ist im Auge des Betrachters. Als Code geht bei Sie sind leicht zu lesen und zu verstehen, was eine Menge Code in der freien Natur schlägt.

verwende ich die folgende dynamische Kreis einzeln verknüpfte Liste zu erstellen. Alles was es braucht ist die Größe.

Node* createCircularLList(int size)
{
    Node *it; // to iterate through the LList
    Node *head;

    // Create the head /1st Node of the list
    head = it = (Node*)malloc(sizeof(Node));
    head->id = 1;

    // Create the remaining Nodes (from 2 to size)
    int i;
    for (i = 2; i <= size; ++i) {
        it->next = (Node*)malloc(sizeof(Node)); // create next Node
        it = it->next;                          // point to it
        it->id = i;                             // assign its value / id
        if (i == 2)
            head->next = it; // head Node points to the 2nd Node
    }
    // close the llist by having the last Node point to the head Node
    it->next = head;

    return head;    // return pointer to start of the list
}

Und ich definieren Node ADT etwa so:

typedef struct Node {
    int id;
    struct Node *next;
} Node;

Answer 3

Listenverarbeitung (insbesondere von Kreislisten) wird viel einfacher, wenn Sie die Liste Kopf wie ein Element der Liste (ein so genannten „Sentinel“) zu behandeln. Viele Sonderfälle einfach verschwinden. Sie können einen Dummy-Knoten für den Sentinel verwenden, aber wenn der nächste Zeiger zunächst in der Struktur ist, müssen Sie nicht einmal das tun müssen. Der andere große Trick ist, einen Zeiger auf den nächsten Zeiger des vorherigen Knoten zu halten (so können Sie es später ändern), wenn Sie die Liste ändern. Dass sie alle zusammen, Sie erhalten diese:

struct node* get_sentinel(struct list* plist)
{
    // use &plist->head itself as sentinel!
    // (works because struct node starts with the next pointer)
    return (struct node*) &plist->head;
}

struct list* init_list(){
    struct list* plist;
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){
        return NULL;        
    }
    plist->head = get_sentinel(plist);
    return plist;
}

void add_node_at_front(struct node* pnode,struct list* plist){
    pnode->next = plist->head;
    plist->head = pnode;
}

void add_node_at_back(struct node* pnode,struct list* plist){
    struct node *current, *sentinel = get_sentinel(plist);

    // search for last element
    current = plist->head;
    while (current->next != sentinel)
        current = current->next;

    // insert node
    pnode->next = sentinel;
    current->next = pnode;
}

void remove_node(struct list* plist, int value){
    struct node **prevnext, *sentinel = get_sentinel(plist);
    prevnext = &plist->head; // ptr to next pointer of previous node
    while (*prevnext != sentinel) {
        struct node *current = *prevnext;
        if (current->value == value) {
            *prevnext = current->next; // remove current from list
            free(current); // and free it
            break; // we're done!
        }
        prevnext = &current->next;
    }
}

void print_list(struct list* plist){
    struct node *current, *sentinel = get_sentinel(plist);
    for (current = plist->head; current != sentinel; current = current->next)
        print_node(current);
}

Answer 4

Ein paar Anmerkungen:

• Ich denke, die Funktion remove einstellen nicht richtig die Kreislistenzeiger, wenn Sie den Knoten Kopf löschen und die Liste ist größer als 3 Elemente. Da die Liste kreisförmig haben Sie den letzten Knoten in der Liste auf den neuen Kopf zeigen.
• könnten Sie in der Lage sein, die Funktion remove etwas zu verkürzen, indem eine „find_node“ Funktion zu schaffen. Da die Liste kreisförmig ist, wird es jedoch immer noch der Fall sein Rand der Kopfknoten des Löschens, die als in einer nicht-zirkularen Liste komplexer sein wird.
• -Code „Schönheit“ ist im Auge des Betrachters. Als Code geht bei Sie sind leicht zu lesen und zu verstehen, was eine Menge Code in der freien Natur schlägt.

Answer 5

verwende ich die folgende dynamische Kreis einzeln verknüpfte Liste zu erstellen. Alles was es braucht ist die Größe.

Node* createCircularLList(int size)
{
    Node *it; // to iterate through the LList
    Node *head;

    // Create the head /1st Node of the list
    head = it = (Node*)malloc(sizeof(Node));
    head->id = 1;

    // Create the remaining Nodes (from 2 to size)
    int i;
    for (i = 2; i <= size; ++i) {
        it->next = (Node*)malloc(sizeof(Node)); // create next Node
        it = it->next;                          // point to it
        it->id = i;                             // assign its value / id
        if (i == 2)
            head->next = it; // head Node points to the 2nd Node
    }
    // close the llist by having the last Node point to the head Node
    it->next = head;

    return head;    // return pointer to start of the list
}

Und ich definieren Node ADT etwa so:

typedef struct Node {
    int id;
    struct Node *next;
} Node;