c - 動的データ型を持つ C のモジュラーデータ構造

Question

私の今後の大学の C プロジェクトでは、C で許可されているモジュールコードを使用するように求められています。基本的に、リンクリスト、バイナリツリー、ハッシュテーブルなどのデータ構造に対応する .c ファイルとそれに対応する .h ファイルを用意します。

リンクされたリストを例として使用すると、次のようになります。

typedef struct sLinkedList {
    int value;
    struct sLinkedList *next;
} List;

しかし、これは強制的valueなものでintあり、このリンクリストライブラリを使用するユーザーは、ライブラリのソースコードを直接変更する必要があります。私はそれを避けたい、ライブラリを変更する必要を避けたい、コードを可能な限りモジュール化したい.

私のプロジェクトでは、整数のリスト、または何らかの構造のリストにリンクされたリストを使用する必要がある場合があります。ただし、ライブラリファイル/コードを複製して、それに応じてコードを変更するつもりはありません。

どうすればこれを解決できますか?

score 4 · Accepted Answer

残念ながら、これを解決する簡単な方法はありません。このタイプの状況に対する最も一般的な純粋な C のアプローチは、を使用void*し、ポインタに割り当てられたメモリに値をコピーすることです。ただし、これにより使用が難しくなり、エラーが発生しやすくなります。

score 1 · Accepted Answer

まだ誰も言及していない別の代替手段は、Linux カーネルのlist.h一般的なリンクリストの実装で見つけることができます。原則は次のとおりです。

/* generic definition */
struct list {
  strict list *next, *prev;
};

// some more code

/* specific version */
struct intlist {
  struct list list;
  int i;
};

ポインターを作成するstruct intlist*と、(C で) ポインターに安全にキャストできるため、データ型に関係なくstruct list*動作する汎用関数を記述できます。struct list*

実装は、特定のリスト内の任意の配置をサポートするためにいくつかのlist.hマクロトリックを使用しstruct listますが、私自身は struct-cast-to-first-member トリックに依存することを好みます。これにより、呼び出しコードが読みやすくなります。確かに、「複数の継承」を無効にします (これをある種の継承と見なすと仮定します) が、next(mylist)より見栄えがよくなりnext(mylist, list)ます。さらに、ハッカーを掘り下げることを避けることができれば、offsetofおそらくより良い形で終わるでしょう.

score 0 · Accepted Answer

int の代わりに Void* を使用できます。これにより、データを任意のタイプにすることができます。ただし、ユーザーはデータの種類に注意する必要があります。

そのために、必要に応じて、Type を表す別のメンバーを持つことができます。列挙型{INT、CHAR、float ...}のものです

score 0 · Accepted Answer

C でのリンクリストユーティリティの例を次に示します。

struct Single_List_Node
{
    struct Single_List * p_next;
    void *               p_data;
};

struct Double_List_Node
{
    struct Double_List *    p_next;
    struct Double_List *    p_prev; // pointer to previous node
    void *                  p_data;
};

struct Single_List_Data_Type
{
    size_t                         size; // Number of elements in list
    struct Single_List_Node *      p_first_node;
    struct Single_List_Node *      p_last_node; // To make appending faster.
};

いくつかの一般的な機能:

void    Single_List_Create(struct Single_List_Data_Type * p_list)
{
    if (p_list)
    {
        p_list->size = 0;
        p_list->first_node = 0;
        p_list->last_node = p_list->first_node;
    }
    return;
}


void    Single_List_Append(struct Single_List_Data_Type *   p_list,
                           void *                           p_data)
{
    if (p_list)
    {
        struct Single_List_Node * p_new_node = malloc(sizeof(struct Single_List_Node));
        if (p_new_node)
        {
            p_new_node->p_data = p_data;
            p_new_node->p_next = 0;
            if (p_list->last_node)
            {
                p_list->last_node->p_next = p_new_node;
            }
            else
            {
                if (p_list->first_node == 0)
                {
                    p_list->first_node = p_new_node;
                    p_list->last_node = p_new_node;
                }
                else
                {
                    struct Single_List_Node * p_last_node = 0;
                    p_last_node = p_list->first_node;
                    while (p_last_node->p_next)
                    {
                        p_last_node = p_last_node->p_next;
                    }
                    p_list->last_node->p_next = p_new_node;
                    p_list->last_node = p_new_node;
                }
            }
            ++(p_list->size);
        }
    }
    return;
}

これらすべての関数を 1 つのソースファイルに入れ、関数宣言をヘッダーファイルに入れることができます。これにより、他のプログラムで関数を使用できるようになり、常に再コンパイルする必要がなくなります。データへのvoid *ポインターを使用すると、さまざまなデータ型でリストを使用できます。

(上記のコードはそのままの状態で提供され、コンパイラでテストされていません。バグ修正の責任は、例のユーザーにあります。)

score 0 · Accepted Answer

これは大学のプロジェクトなので、ただ答えを出すことはできません。代わりに、C の 2 つの機能、void ポインター (以前に遭遇した可能性が高い) とトークン貼り付け演算子(持っていない可能性があります) について熟考することをお勧めします。

score 0 · Accepted Answer

value をとして定義することで、これを回避できますvoid* value;。この方法で任意の型のデータにポインターを割り当てることができますが、呼び出し元のコードでは、ポインターを正しい型にキャストして逆参照する必要があります。これを追跡する 1 つの方法は、短いchar配列をに追加しstructて型名を記録することです。

score 0 · Accepted Answer

この問題こそが、テンプレートが C++ 用に開発された理由です。私が C で 1 回か 2 回使用したアプローチは、値フィールドを void* にし、挿入時に値をそこにキャストし、検索時にキャストし直すというものです。もちろん、これはタイプセーフとはほど遠いものです。モジュール性を高めるために、これを使用する型ごとに insert_int()、get_mystruct() などの関数を記述し、そこでキャストを行うことがあります。

score 0 · Accepted Answer

を使用できる C++ とは異なりtemplate、void *は事実上の C ソリューションです。

また、リンクされたリストの要素を別の構造体に入れることもできます。

typedef struct sLinkedListElem {
    int value; /* or "void * value" */
} ListElem;

typedef struct sLinkedList {
    ListElem data;
    struct sLinkedList *next;
} List;

リンクコードに影響を与えずに要素を変更できるようにします。

c - 動的データ型を持つ C のモジュラー データ構造

8 に答える 8

Related

Reference

c - 動的データ型を持つ C のモジュラーデータ構造