9

従来のデータ構造を調べて、リンクリストで停止しました。循環型の単一リンクリストを実装しただけですが、このリストをよりエレガントな方法で表現できる、特に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

4 に答える 4

5

Linux カーネル ソースの循環リンク リストを見てみましょう: http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

その美しさは、データをリストに収めるための特別な構造体を持っていないという事実に由来しますstruct list_head *。リストとして保持したい構造体に を含めるだけで済みます。リスト内のアイテムにアクセスするためのマクロは、オフセット計算を処理して、struct list_headポインターからデータを取得します。

カーネルで使用されるリンク リストの詳細な説明は、kernelnewbies.org/FAQ/LinkedLists にあります (申し訳ありませんが、ハイパーリンクを 2 つ投稿するのに十分なカルマがありません)。

編集：リストは二重リンクリストであり、あなたが持っているような単一リンクリストではありませんが、概念を採用して独自の単一リンクリストを作成できます.

于 2010-11-21T01:52:32.620 に答える
2

リストの処理 (特に循環リスト) は、リストの先頭をリストの要素 (いわゆる「センチネル」) のように扱うと、はるかに簡単になります。多くの特殊なケースが消えていきます。センチネルにダミー ノードを使用できますが、ネクスト ポインターが構造体の最初にある場合は、その必要さえありません。もう 1 つの大きなトリックは、リストを変更するたびに、前のノードの次のポインターへのポインターを保持することです (後で変更できるようにするため)。すべてをまとめると、次のようになります。

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);
}
于 2010-11-21T04:21:11.243 に答える
1

いくつかのコメント:

  • ヘッドノードを削除し、リストが3要素より大きい場合、削除機能は循環リストポインターを正しく調整しないと思います。リストは循環しているため、リストの最後のノードを新しいヘッドに向ける必要があります。
  • 「find_node」関数を作成することで、削除関数を少し短縮できる場合があります。ただし、リストは循環しているため、非循環リストよりも複雑なヘッド ノードを削除するエッジ ケースが依然として存在します。
  • コード「美しさ」は見る人の目にあります。コードが進むにつれて、実際の多くのコードよりも読みやすく理解しやすいものになります。
于 2010-11-21T01:54:11.617 に答える