c - C Generic Double Linked List 各ノードが複数のアイテムを保持

Question

各ノードが色、形状、サイズなどの複数の項目を格納できる汎用リンクリストを設計しようとしています。

これは私の.hファイルがどのように見えるかです

typedef struct linked{
    char type;
    void * item;
    struct linked * next;
    struct linked * prev;
}LinkedList;

LinkedList * NewLinkedList();
LinkedList * next(Iterator **I);
int hasNext(Iterator *I);
void insertion(LinkedList **a, void *b);
void printStringList(LinkedList *L);
void printIntList(LinkedList *L);
void printDoubleList(LinkedList *L);
void delete(LinkedList *L, void *n);

void * item2 と void * item3 ... を追加して構造体を変更する必要がありますか? または、それを行うためのより良い方法があります。

2 番目の質問は、void ポインターを使用するたびに型キャストする必要があるかどうかです。これは私のコードですprintIntList

void printList(LinkedList *L)
{
    LinkedList *tmp = NULL;
    tmp = L;
    while(L)
    {
        printf("%d\n",*(int*)L->item);
        L=L->next;
    }
}

そして私はprintIntList、printDoubleListそしてを持っていprintStringListます。それらを組み合わせる方法はありますか？

ありがとう！

score 1 · Accepted Answer

次のようなことができます。

typedef struct links {
    struct links * next;
    struct links * prev;
} links;

typedef struct outer_node {
  links l; // links to outer_node.l
  struct inner_node * children;
} outer_node;

typedef struct inner_node {
  links l; // links to inner_node.l
  char type;
  void * item;
} inner_node;

基本的に、連結リストがあり、その各ノードは独自の連結リストです。

どちらのリストも同じ種類のリンクを使用して編成されているため、リンク/リンク解除コードを複製する必要はありません。

マクロを使用してoffsetof()、ポインターからlinksそのコンテナーinner_nodeまたはouter_node.

完全なデモは次のとおりです。

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

typedef struct links {
    struct links * next;
    struct links * prev;
} links;

typedef struct outer_node {
  links l; // links to outer_node.l
  struct inner_node * children;
} outer_node;

typedef struct inner_node {
  links l; // links to inner_node.l
  char type;
  void * item;
} inner_node;

void linkNodes(links* l1, links* l2)
{
  links* tmp = l1->prev;
  l1->next->prev = l2->prev;
  l1->next = l2;

  l2->prev->next = tmp;
  l2->prev = l1;
}

inner_node* createNode(char type, void* item, inner_node* sibling)
{
  inner_node* n = malloc(sizeof(*n));
  n->type = type;
  n->item = item;
  n->l.prev = &n->l;
  n->l.next = &n->l;
  if (sibling != NULL)
    linkNodes(&n->l, &sibling->l);
  return n;
}

outer_node* createOuterNode(inner_node* child, outer_node* sibling)
{
  outer_node* n = malloc(sizeof(*n));
  n->l.prev = &n->l;
  n->l.next = &n->l;
  n->children = child;
  if (sibling != NULL)
    linkNodes(&n->l, &sibling->l);
  return n;  
}

void PrintList(links* l, int level)
{
  links* l2 = l;
  do
  {
    if (level == 0)
    {
      outer_node* n = (void*)((char*)l2 + offsetof(outer_node, l));
      printf("{\n");
      PrintList(&n->children->l, level + 1);
      printf("}\n");
    }
    else
    {
      inner_node* n = (void*)((char*)l2 + offsetof(inner_node, l));
      printf("  type: %d, item: %s\n", n->type, (char*)n->item);
    }
    l2 = l2->next;
  } while (l2 != l);
}

int main(void)
{
  outer_node* root = 
    createOuterNode(
      createNode(0, "something",
        NULL
      ),
      createOuterNode(
        createNode(1, "foo",
          createNode(2, "bar",
            NULL
          )
        ),
        createOuterNode(
          createNode(3, "red",
            createNode(3, "green",
              createNode(3, "blue",
                NULL
              )
            )
          ),
          createOuterNode(
            createNode(4, "cat",
              createNode(5, "dog",
                createNode(6, "raven",
                  createNode(7, "shark",
                    NULL
                  )
                )
              )
            ),
            NULL
          )
        )
      )
    );

  PrintList(&root->l, 0);

  return 0;
}

出力 ( ideone ):

{
  type: 0, item: something
}
{
  type: 1, item: foo
  type: 2, item: bar
}
{
  type: 3, item: red
  type: 3, item: green
  type: 3, item: blue
}
{
  type: 4, item: cat
  type: 5, item: dog
  type: 6, item: raven
  type: 7, item: shark
}

score 1 · Accepted Answer

要素ごとに定義されたアイテムが本当に動的かどうかを考慮する必要があります。色、サイズ、形は、保管する必要があるものに制限がありますか?

それが本当に必要な場合は、シンプルに保ち、間接/メモリ割り当てを最小限に抑えてみませんか。

enum ShapeFlags { sizeDefined = 0x01, colorDefined = 0x02, shapeDefined = 0x04 };

typedef struct shapeList {
    ShapeFlags shapeFlags;
    Size  size;
    Color color;
    Shape shape;
    struct Linked * next;
    struct Linked * prev;
} ShapeList;

一方、実際に非常に動的なプロパティのセットがある場合、リストのリストの代わりに、センチネルを含む単一のリストを作成することもできます。

enum FieldFlag { terminator = 0x01, size = 0x02, color = 0x04, shape = 0x08 };

typedef struct list
{
  FieldFlag type;
  void* value;
  struct list* next;
  struct list* previous;
} List;

その後、通常どおり反復し、terminatorフラグを使用してオブジェクトの終わりを知ることができます。

score 1 · Accepted Answer

はい、おそらく 3 つのポインターを使用する必要がありますか、それとも色やサイズのない形状がありますか? そうでない場合は、それぞれが指すものの型を持つ 3 つのポインターを作成することを検討する必要があります。これにより、型をキャストして削除する必要がなくなります。

構造は次のようになります。

typedef struct linked{
    Size * size;
    Color* color;
    Shape* shape;
    struct linked * next;
    struct linked * prev;
}LinkedList;

1 つのノード(2 つの色など)に同じタイプのアイテムをさらに格納したい場合は、unionの使用を検討する必要があります。

2番目の質問に答えるには...はい、voidポインターを使用するたびにキャストする必要があります（少なくともあなたの場合は=）。よりきれいなコードを得るには、ユニオンをもう一度検討する必要があります...

score 1 · Accepted Answer

void * item2 と void * item3 ... を追加して構造体を変更する必要がありますか? または、それを行うためのより良い方法があります。

それは、リストがどの程度一般的であるかによって異なります。いくつかの特定の値を保持するために使用される場合は、それらすべてを作成するか、それらの構造体を作成することができます。異なるタイプの値を保持する可能性がある場合は、ユニオンを作成することができ、1 つのノードに多くの値を保持する可能性がある場合は、おそらく、値の配列を作成したほうがよいでしょう。

void ポインターを使用するたびに型キャストする必要がありますか?

それらに/から割り当てる場合 ( int * a = a_void_pointer/ a_void_pointer = an_int_pointer)- いいえ

そのようなポインターを逆参照する場合 ( *a_void_pointer) - はい。

score 1 · Accepted Answer

判別共用体型を使用して一般的なリストを作成できます。

typedef struct listitem
{
  char type;
  union
  {
    integer i;
    double d;
    char *s;
    // etc.
  } u;
} Listitem;

LinkedList でこの listitem を使用します。

c - C Generic Double Linked List 各ノードが複数のアイテムを保持

5 に答える 5

Related

Reference