5

Cのジェネリックリスト操作関数とは何ですか? （これは、資料を調べているときに見ました。）

この関数と、あらゆる種類の要素を受け入れることができる関数の違いは何ですか?

同じですか…？それらが同じでない場合、どうすればそれらを個別に実装できますか?

4

7 に答える 7

7

Cには、「汎用」ポインターまたはオブジェクトの概念はありません。最も近いのは、void*ポインターを使用することです。1つのコードで任意のデータ型を処理できるようにする場合は、ほとんどの場合、void*ポインターを使用する必要があります。サイズがポインタ以下のデータ型の場合、型とvoid*;の間でキャストできます。より大きなデータ型の場合は、ダイナミックメモリを使用し、void*メンバーがダイナミックメモリを指すようにする必要があります。メモリリークに注意してください！

typedef struct list_node {
  struct list_node *next;
  void *data;
} list_node;

void list_insert(list_node *node, void *data) {
  // ...
}

一方、可能なデータ型ごとにコードを生成する場合は、マクロを使用してコードを生成してから、使用する可能性のあるデータ型ごとにマクロをインスタンス化する必要があります。例えば：

#define DEFINE_LIST(type) \
  typedef struct list_node_##type { \
    struct list_node_##type *next; \
    type data; \
  }

#define IMPLEMENT_LIST_INSERT(type) \
  void list_##type##_insert(list_node_##type *node, type data) { \
    ... \
  }

DEFINE_LIST(int);     // defines struct list_node_int
DEFINE_LIST(double);  // defines struct list_node_double
IMPLEMENT_LIST_INSERT(int);    // defines list_int_insert
IMPLEMENT_LIST_INSERT(double); // defines list_double_insert
于 2008-11-28T17:06:55.723 に答える
5

一般的なリストは単一リンクである可能性が高く、おそらくリスト内の項目が次のような構造を持っていると想定しています。

typedef struct list_item list_item;

struct list_item
{
    list_item *next;
    ...data for node...
};

このレイアウトを使用すると、次のポインターのみを使用してリストを操作する関数を作成できます。

場合によっては、' ...data for node...' が単純な ' ' になることがありvoid *ます。つまり、リスト項目には、リスト内の次のノードへのポインター (次のノードがない場合は NULL) とデータへのポインターが含まれます。

typedef struct list list;

struct list
{
    list *next;
    void *data;
};

任意のポインターを ' void *' にキャストできるため、リスト内に任意のデータ型を混在させることができますが、コードはそれらを処理する方法を知っている必要があります。

あなたは「一般的なリスト関数」について尋ねますが、おそらく単一の関数ですべてを行う設計はなく、単純な設計も確かにありません。汎用リスト関数を作成できる関数のセットは多数あります。Lispに触発された1つのセットは、次のもので構成されます。

void *car(list *lp);    // Return the data for the first item on the list
list *cdr(list *lp);    // Return the tail of the list
list *cons(list *lp1, list *lp2);   // Construct a list from lists lp1 and lp2

list *cond(list *lp, void *data);  // Append data item to list

おそらく、リストが空かどうかをテストする機能と、その他のいくつかの項目を提供する必要があります。

確かに C++ での 1 つの優れた説明は、Koenig の「C++ に関する反省」にあります。このアイデアは非常に簡単に C に適用できます。それほど難しくはありません (ただし、C でのストレージ管理は C++ よりも困難です)。

于 2008-11-28T16:53:54.547 に答える
3

Linux カーネルのlinux/list.hヘッダーには、C で書かれた一般的なリンク リストの興味深い実装があります。これは、次のように使用される、ヘッド ノードを持つ双方向リンク リストです。

struct mystruct {
    ...
    /* Contains the next and prev pointers */
    struct list_head mylist;
    ...
    /* A single struct can be in several lists */
    struct list_head another_list;
    ...
};

struct list_head mylist_head;
struct list_head another_list_head;

この小さな例のいくつかの興味深い点:

  • リスト ノードは、データ ポインターを必要とせず、ターゲット構造体に埋め込まれます。
  • リスト ノードは、ターゲット構造体の先頭にある必要はありません。
  • 1 つの構造体は、同時に複数のリンクされたリストに含めることができます。
  • リスト内の next および prev ポインターはstruct list_head、ターゲット構造体ではなく、 を指します (上記の例で&(foo->mylist)は、最初のリストと&(foo->another_list)2 番目のリストを指します)。

すべてのリスト操作関数は、へのポインターを受け取りますstruct list_head(そして、ほとんどの関数は、それが別のヘッド ノードであるか、組み込みノードの 1 つであるかをまったく気にしません)。からstruct list_headターゲット構造体に到達するには、単純なポインター減算に展開されるマクロ ( linux/kernel.hヘッダーのマクロlist_entryと同じ) を使用します。containter_of

これは、ヘッド ノードを持つ双方向リンク リストであるため、次のことができますO(1)。

  • リストが空かどうか、またはノードがどのリストにもないかどうかを確認してください。
  • 他のノードの後または前にノードを取得します (ノードがヘッドの場合、リストの最初または最後の要素を取得します)。
  • 他のノードの後または前にノードを挿入します (ノードが先頭の場合は、リストの最初または最後に挿入します)。
  • リストからノードを削除します (これを行うには、ノード自体へのポインターのみが必要です)。
  • その他のいくつかの操作。
于 2008-11-29T16:12:02.947 に答える
2

私の教えのために、私はこの「一般的な」リストモジュールを開発するようになりました。これはおそらく Linux カーネルのものの単純化されたバージョンであり、追加のまだ発見されていないバグが含まれており、gcc 拡張機能を使用しています...コメントは大歓迎です!

#ifndef _LISTE
#define _LISTE
#include <stdlib.h>
typedef struct liste_s {
  struct liste_s * suivant ;
} * liste ;


#define newl(t) ( (liste) malloc ( sizeof ( struct liste_s ) + sizeof ( t ) ) )
#define elt(l,t) ( * ( ( t * ) ( l + 1 ) ) )

#define liste_vide NULL
#define videp(l) ( l == liste_vide )
#define lvide() liste_vide
#define cons(e,l) \
  ({ liste res = newl(typeof(e)) ;      \
     res->suivant = l ; \
     elt(res,typeof(e)) = e ;           \
    res ; }) 

#define hd(l,t) ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; elt(res,t) ; })
#define tl(l)   ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; res->suivant ;})


#endif
于 2012-12-06T11:02:36.483 に答える
1

Cとその標準ライブラリは、リスト固有の機能を提供していません。

しかし、他のプログラミング言語から知られているデータ型をサポートするCの多くの便利な関数を備えたライブラリがあります：http：//library.gnome.org/devel/glib/2.18/glib-data-types.html

于 2008-11-30T03:32:20.437 に答える
0

上記のように、リスト操作関数を作成するために MACROS アプローチを使用してみました。INSERT 操作ルーチンを作成するのは簡単ですが、Delete 操作とトラバース操作を作成するのは困難です。それに続いて、リスト構造と INSERT ルーチン シグネチャが続きます。

#define LIST_DEFINE(type) \
    struct list_node_##type \
    { \
        type *data; \`
        struct list_node_##type *next; \
   };

LIST_INSERT(&ListHead,&Data, DataType);

ここで:
ListHead- リンクされたリストの先頭
Data- 新しいノードが作成され、データがノードに挿入される DataTypeデータ - 渡されるデータのデータ型です

参考までに、関数にメモリを割り当て、新しく作成されたノードに渡されたすべてのデータをコピーして、リンクされたリストにノードを追加します。

これで、LIST_DELETEルーチンが作成されると、削除する必要があるノードは、データ内の一意の識別子を使用して識別されます。その識別子は、展開MACROで置き換えられるキーとしてルーチンでも渡されます。MACROルーチンの署名は次のようになります。

LIST_DELETE(&ListHead, DataType, myvar->data->str, char*);

ここで:
ListHead- リンクされたリストの先頭
DataType- データのデータ型
myvar->data->str- 一意のキー
char*- キーの型

ここで、キーが展開されると、その同じキーを次のように比較に使用することはできません

if((keytype)ListHead->data->key == (keytype)key)

に展開します。

ListHead->data->myvar->data->str == myvar->data->str

そして、ここには次のような変数はありません:ListHead->data->myvar->data->str

したがって、この方法では削除ルーチンを作成することはできず、トラバーサル ルーチンと検索ルーチンも一意のキーを使用するため、同様の問題が発生します。

また、無関係なメモとして、一意のキーは何でもかまいませんので、一意のキーの一致ロジックを決定する方法について説明します。

于 2012-06-18T05:30:13.360 に答える