Элегантная реализация кругового односвязного списка в C? - PullRequest
9 голосов
/ 21 ноября 2010

Перебирая классические структуры данных и остановившись на связанных списках. Просто реализовал круговой односвязный список, но у меня сложилось впечатление, что этот список можно выразить более элегантным образом, в частности, функцией remove_node.Учитывая эффективность и читабельность кода, кто-нибудь может представить более краткое и эффективное решение для односвязного кругового списка?

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

    }
}

Ответы [ 4 ]

5 голосов
/ 21 ноября 2010

Взгляните на круговой связанный список в исходном коде ядра Linux: http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

Его прелесть заключается в том, что у вас нет специальной структуры для ваших данных, чтобы поместиться в список,вам нужно только включить struct list_head * в структуру, которую вы хотите иметь в виде списка.Макросы для доступа к элементам в списке будут обрабатывать вычисление смещения для получения от указателя struct list_head на ваши данные.

Более подробное объяснение связанного списка, используемого в ядре, можно найти на kernelnewbies.org/ FAQ / LinkedLists (Извините, у меня недостаточно кармы для публикации двух гиперссылок).

Редактировать: Ну, список представляет собой список с двумя связями, а не один, как у вас, но вы могли быпринять концепцию и создать свой собственный односвязный список.

2 голосов
/ 21 ноября 2010

Обработка списка (особенно циклических списков) становится намного проще, когда вы рассматриваете заголовок списка как элемент списка (так называемый «страж»).Многие особые случаи просто исчезают.Вы можете использовать фиктивный узел для стража, но если следующий указатель является первым в структуре, вам даже не нужно это делать.Другой большой трюк - сохранять указатель на следующий указатель предыдущего узла (чтобы вы могли изменить его позже) всякий раз, когда вы изменяете список.Собрав все воедино, вы получите:

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);
}
1 голос
/ 21 ноября 2010

Несколько комментариев:

  • Я думаю, что функция удаления не корректно корректирует указатели кругового списка, когда вы удаляете головной узел, и список превышает 3 элемента. Поскольку список является круглым, вы должны указать последний узел в списке на новую голову.
  • Возможно, вы сможете немного сократить функцию удаления, создав функцию "find_node". Однако, поскольку список является круглым, все равно будет крайний случай удаления головного узла, который будет более сложным, чем в некруглом списке.
  • Код "красота" в глазах смотрящего. Поскольку код работает, ваш легко читается и понимается, что намного лучше, чем просто в коде.
0 голосов
/ 14 марта 2017

Я использую следующее для создания динамического кругового односвязного списка.Все, что для этого требуется, это размер.

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
}

И я определяю Node ADT так:

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