二重リンクリストの実装

Question

私はC ++のバックグラウンドを持っており、最近Cに移行しました。最初に作成したもののひとつは、ポインタとメモリ割り当てを使用することをお勧めしますが、二重リンクリストでした。それほど複雑ではありませんが、いくつかの基本的な機能を備えているだけです。

これが私のリストの概要です：

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

typedef struct Node
{
    int val;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

double_list* create_list(); // constructor
void destroy_list(double_list* const list); // destructor

void insert_pos(double_list* const list, int index, int val);
void insert_front(double_list* const list, int val);
void insert_back(double_list* const list, int val);

void remove_pos(double_list* const list, int index);
void remove_front(double_list* const list);
void remove_back(double_list* const list);

void sort_list(double_list* const list); // selection sort
void reverse_list(double_list* const list);

基本的な挿入と削除に加えて、コンストラクタ、デストラクタ、ソート、およびリバース関数があります。

関数の実際の定義は次のとおりです。

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

typedef struct Node
{
    int val;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

double_list* create_list()
{
    double_list* list = malloc(sizeof(*list));

    list->length = 0;
    list->head = NULL;
    list->tail = NULL;

    return list;
}

void destroy_list(double_list* const list)
{
    list->length = 0;

    Node* node_ptr = list->head;
    while (node_ptr != NULL)
    {
        node_ptr = node_ptr->next;
        free(list->head);
        list->head = node_ptr;
    }
}

void insert_pos(double_list* const list, int index, int val)
{
    if (index < 0 || index > list->length)
        return;

    list->length += 1;

    if (list->head == NULL)
    {
        list->head = malloc(sizeof(*(list->head)));

        list->head->val = val;
        list->head->prev = NULL;
        list->head->next = NULL;

        list->tail = list->head;

        return;
    }

    if (index == 0)
    {
        Node* new_node = malloc(sizeof(*new_node));

        new_node->val = val;
        new_node->prev = NULL;
        new_node->next = list->head;

        list->head->prev = new_node;
        list->head = new_node;

        return;
    }

    if (index == list->length - 1)
    {
        Node* new_node = malloc(sizeof(*new_node));

        new_node->val = val;
        new_node->prev = list->tail;
        new_node->next = NULL;

        list->tail->next = new_node;
        list->tail = new_node;

        return;
    }
    
    Node* node_ptr = list->head;
    for (int a = 0; a < index; ++a)
        node_ptr = node_ptr->next;

    Node* new_node = malloc(sizeof(*new_node));

    new_node->val = val;
    new_node->next = node_ptr;
    new_node->prev = node_ptr->prev;

    node_ptr->prev->next = new_node;
    node_ptr->prev = new_node;
}

void insert_front(double_list* const list, int val)
{
    insert_pos(list, 0, val);
}

void insert_back(double_list* const list, int val)
{
    insert_pos(list, list->length, val);
}

void remove_pos(double_list* const list, int index)
{
    if (index < 0 || index >= list->length)
        return;

    list->length -= 1;

    if (index == 0)
    {
        Node* node_ptr = list->head;
        list->head = list->head->next;
        list->head->prev = NULL;

        free(node_ptr);
        return;
    }

    if (index == list->length)
    {
        Node* node_ptr = list->tail;
        list->tail = list->tail->prev;
        list->tail->next = NULL;

        free(node_ptr);
        return;
    }
    
    Node* node_ptr = list->head;
    for (int a = 0; a < index; ++a)
        node_ptr = node_ptr->next;

    node_ptr->prev->next = node_ptr->next;
    node_ptr->next->prev = node_ptr->prev;

    free(node_ptr);
}

void remove_front(double_list* const list)
{
    remove_pos(list, 0);
}

void remove_back(double_list* const list)
{
    remove_pos(list, list->length - 1);
}

void sort_list(double_list* const list)
{
    Node* index_ptr = list->head;
    Node* small_ptr = list->head;
    Node* node_ptr = list->head;
    while (index_ptr->next != NULL)
    {
        while (node_ptr != NULL)
        {
            if (node_ptr->val < small_ptr->val)
                small_ptr = node_ptr;

            node_ptr = node_ptr->next;
        }

        int hold = index_ptr->val;
        index_ptr->val = small_ptr->val;
        small_ptr->val = hold;

        index_ptr = index_ptr->next;
        node_ptr = index_ptr;
        small_ptr = index_ptr;
    }
}

void reverse_list(double_list* const list)
{
    Node* node_ptr = list->head;

    list->head = list->tail;
    list->tail = node_ptr;

    while (node_ptr != NULL)
    {
        Node* temp = node_ptr->prev;
        node_ptr->prev = node_ptr->next;
        node_ptr->next = temp;

        node_ptr = node_ptr->prev;
    }
}

そして、これが私のリストがどのように使われるかの小さなサンプルです：

double_list* list = create_list();

insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);

sort_list(list);

destroy_list(list);

私の主な関心事は次のとおりです。

1. コンストラクタとデストラクタは適切に仕事をしていますか？デストラクタがメモリリークを起こしていませんか？コンストラクタを実行するためのより良い方法はありますか？

2. あるremove()とinsert()機能に効率的ですか？より汎用的なremove()関数を作成して、インデックス0などの特別なテストケースを用意する必要がないようにするなど、これを行うためのより良い方法はありますか？

3. あるsort()とreverse()の機能は、少なくとも大丈夫？選択ソートは使用するのに最適なアルゴリズムではないことを私は知っています。そして、reverse()機能は正しく実装されていますか？リストを逆にするより良い方法はありますか？

申し訳ありませんが、質問が少し広すぎます。必要に応じて、より具体的な質問に焦点を当てるように編集できます。

ありがとう

Answer 1

良い質問で、よくフォーマットされ、うまく機能していて、実装はうまくいくようです！

最初にあなたの質問に答えてください：

Q1：

コンストラクタ：

• mallocの戻り値を確認してください。NULL失敗した場合（メモリ不足）の可能性があります。

デストラクタ：

• 合格するだけdouble_list *listで、const意味がありません（なぜそこに置くのかわかりません）。
• listコンストラクターで割り当てたメモリを解放しないため、メモリがリークします

編集1：

これを渡すとdouble_list *const list、リストの値（ポインター）を変更できなくなります。これは、このインターフェイスのユーザーがポインターを保持しているため、ここでは意味がありません。

constがタイプの前にある場合、const double_list *listこれはリストが指している場所の内容を変更できないことを意味します。

たとえば、文字列を受け取る関数があり、この関数のユーザーに文字列の内容が変更されないことを伝えたい場合は、を実行する必要がありますvoid foo(const char *bar)。関数が唯一foo(char *bar)の場合、ユーザーは文字列の内容がbarその後も同じであることを確認できません。

Q2：

• removeとinsert機能のパフォーマンスに問題はありません。真ん中の挿入は常にO（n）になります。頭と尾の取り外し/挿入は、コードで達成するO（1）です。
• 関数remove_front/でヘッド/テールを削除する単純なケースを実装し、remove_backこれらの関数をジェネリックremove_pos関数で使用すると、もう少し直感的になります。

Q3：

並べ替え

• sort_list：リストが並べ替えられたときにフラグを設定して、リストが再度並べ替えられた場合に高速になるようにすることができます（要素が追加されたときにフラグの設定を解除します）
• それ以外の場合、並べ替えの実装に問題はありません

逆行する

リストの逆実装はO（n）ですが、二重にリンクされたリストがあるので、これを簡単に利用できます。リストに2セットの操作を含めることができます。1つは順方向に操作し、もう1つは逆方向に操作します。reverse_listが呼び出されるたびに、関数セットを交換します。以下の例を参照してください。

struct list_operations
{
    void (*insert_front)(double_list* const list, int val);
    // more functions
};

static const struct list_operations list_operations_forward = 
{
    .insert_front = insert_front_forward,
    // more functions
};

static const struct list_operations list_operations_reverse = 
{
    .insert_front = insert_front_reverse,
    // more functions
};

void reverse_list(double_list* list)
{
    if (NULL == list)
    {
        return
    }

    list->operations = (list->operations == &list_operations_forward)?&list_operations_reverse:&list_operations_forward;
}

より一般的なフィードバック：

個人情報を隠す

hファイルの詳細の一部をリークします。double_listライブラリのユーザーがノードを混乱させたくない場合は、ノードを非表示にし、関数を追加して値を取得する必要があります。hファイルは次のようになります。

typedef struct double_list_s double_list_t;

double_list* create_list();
void destroy_list(double_list* list);

void insert_pos(double_list *list, int index, int val);
void insert_front(double_list *list, int val);
void insert_back(double_list *list, int val);

void remove_pos(double_list *list, int index);
void remove_front(double_list *list);
void remove_back(double_list *list);

int get_pos(double_list *list, pos);
int get_front(double_list *list);
int get_back(double_list *list);

void sort_list(double_list *list); // selection sort
void reverse_list(double_list *list);

constを削除します

あなたは合格double_list* const listしています、あなたは正確に何を達成しようとしていconstますか？

インクルージョンガードがありません

以下を追加する必要があります。

#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__

// snip

#endif

hファイルのインクルードを削除します

インクルードはcファイルにのみ含める必要があります。そうしないと、周期的な包含に遭遇する可能性があります。

ポインタの星は変数に固執します

例：良くない： char* b

より良い： char *b

それ以外の場合、次の宣言があると奇妙に見えます。

char* b, *avs（char *b, *a）

NULLを確認してください

list関数のNULLの引数を確認してください

割り当て後にNULLを確認します

ノードを割り当てるときは、malloc返されるかどうかも確認する必要がありますNULL。

テスト

リストに追加するときは、要素を1、2、3の順序で追加するため、sort_listあまり機能しません。

関数に名前を付ける

関数の命名に関しては、確かに個人的な好みになりますが、私は一般的な表現に固執します。例えば、backおよびfrontビットまれである、私は思うheadし、tailより良いものを関数に記述します。

また、一貫して名前を付けると、インターフェイスが少しすっきりします。

list_create()
list_destroy()

list_pos_insert()
list_head_insert()
list_tail_insert()

list_pos_remove()
list_head_remove()
list_tail_remove()

list_sort()
list_reverse()

何か不明な点がある場合はお知らせください。コードレビューでテキストの半分が「忘れられた」ので、少し急いで書き直しました。

Answer 2

に関して：

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

ほとんどのデバッガーは、構造体の「タグ」名を使用して、個々のフィールドにアクセスできるようにします。「タグ」名の挿入を提案する

main()機能が不足しています。おそらくそれはあなたが電話をかける場所です：

double_list* list = create_list();
insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);
sort_list(list);
destroy_list(list);

個別の操作としてではなく、「insert（）」でリストをソートしておくことを強くお勧めします

Answer 3

あなたがしたNodeように、私はクラスとして扱いますdouble_list。つまりは、関数を作成node_create()、node_destroy()など
してみましょうnode_...()機能変更/正気ノードの内容を確認してください。