1

すでに体験された方もいらっしゃると思います。異なるタイプの 2 つのリンクされたリストがあり、それらによって使用されたメモリを解放する 2 つの異なる関数があります。これらの 2 つの機能は、1 つのことを除いて同一です。

通常、リストを解放する関数は次のようになります。

void free_list(T *p)
{
    T *next;    /* here */
    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }
}

はTノード タイプです。これらの機能の唯一の違いは、マークされた行です。
リンクされたリストの先頭へのポインターを取得して解放する関数/マクロを作成する方法はありますか?

私はいくつかのアイデアを試しましたが、それらは間違っていて失敗したため、詳細を負担しないため、省略します。

4

7 に答える 7

3

のような構造を作成できます。

struct my_item
{
    void * item; // put pointer to your generic item here
    struct my_item * next; // NULL = end of list
};

そして、機能を持っています

void free_my_list (struct my_item * first)
{
    struct my_item * cur = first;
    while (cur != NULL)
    {
         cur = cur->next;
         free(cur->item);
         free(cur);
    }
}
于 2009-07-30T13:17:21.280 に答える
3

「C」の制限を考えると、私の最初のショットは次のようなマクロになります

#define FREE_LIST(T, p)\
do {\
    T *next;\
    while (p != NULL) {\
        next = p->next;\
        free(p);\
        p = next;\
    }\
} while(0)

つまり、1990 年頃 (テンプレートの前) に C++ 汎用コードを書かなければならなかった方法です。

(編集) 歴史的なメモ -- 病的に好奇心旺盛な、 C++の一種の K&R になろうとした C++ でのデューハースト & スタークプログラミングについては、マクロを使用して (執筆時点ではまだ投機的な) テンプレートをエミュレートする方法について詳しく説明しています。私たちが今楽しんでいる行動。ほとんどの原則は自然に「C」に移植されます。

于 2009-07-30T13:17:23.167 に答える
1

別のアプローチを提案したいと思います。さまざまな種類のデータに対して複数のリストタイプを作成し、キャストまたはマクロ体操を使用して同じアルゴリズムをそれらに適用する代わりに、タイプ固有の動作をさまざまな関数に委任する単一のジェネリックリストタイプを作成し、それらの関数を関数付きのリストタイプにアタッチしますポインタ。例えば：

struct generic_node {
  void                *data;
  struct generic_node *next;
};
struct generic_list {
  struct generic_node head;
  int   (*cmp)(void * const a, void * const b);
  void *(*cpy)(void * const);
  void  (*del)(void *);
};

cmpは、* a <* bの場合は-1、* a == * bの場合は0、* a> * bの場合は1を返す関数を指します。ここで、aとbはvoid*から適切なポインター型に変換されています。 。例えば、

int compareInts(void * const a, void * const b)
{
  int * const la = a;
  int * const lb = b;
  if (*a < *b) return -1;
  if (*a == *b) return 0;
  if (*a > *b) return 1;
}

int compareMyStruct(void * const a, void * const b)
{
  struct myStruct * const la = a;
  struct myStruct * const lb = b;

  if (la->foo < lb->foo && strcmp(la->bar,lb->bar) < 0 && ...) return -1;
  if (la->foo == lb->foo && strcmp(la->bar,lb->bar) == 0 && ...) return 0;
  if (la->foo > lb->foo && strcmp(la->bar, lb->bar) > 0 && ...) return 1;
}

cpyは、入力パラメーターのディープコピーを作成する関数を指します。

void *copyInt(void * const data)
{
  int *theCopy = malloc(sizeof *theCopy);
  *theCopy = *((int *) data);
  return theCopy;
}

void *copyMyStruct(void * const data)
{
  struct myStruct * const lData = data;
  struct myStruct *newStruct = malloc(sizeof *newStruct);
  newStruct->foo = lData->foo;
  newStruct->bar = malloc(strlen(lData->bar) + 1);
  strcpy(newStruct->bar, lData->bar);
  ...
  return newStruct;
}

そして最後に、delはデータ項目の割り当てを解除する関数を指します。

void delInt(void * data)
{
  free(data);
}

void delMyStruct(void * data)
{
  struct myStruct * lData = data;
  free(lData->bar);
  ...
  free(lData);
}

これで、リストアルゴリズムは、タイプ固有の動作について心配する必要がなくなりました。関数ポインタを介して適切な関数を呼び出すだけです。

void listAdd(struct generic_list * const theList, void * const data)
{
  struct generic_node *cur = &(theList->head);
  struct generic_node *entry = malloc(sizeof *entry);
  entry->data = theList->cpy(data);
  while (cur->next != NULL && theList->cmp(cur->next->data, entry->data) < 0)
    cur = cur->next;
  entry->next = cur->next;
  cur->next = entry;
}
/** */
void listClear(struct generic_list * const theList)
{
  struct generic_node *cur = theList->head.next;
  while (cur != NULL)
  {
    struct generic_node *entry = cur;
    cur = cur->next;
    theList->del(entry->data);
    free(entry);
  }
}
于 2009-07-30T16:05:59.827 に答える
1

すべてのノード タイプが次のポインターで始まる限り、次のような一般的な解放関数を作成できます。

struct generic_node {
    struct generic_node *next;
};

void free_list(void *head)
{
    struct generic_node *p = head, *next;
    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }
}

struct t_node {
    struct t_node *next;

    /* members of thing t */
};

struct q_node {
    struct q_node *next;

    /* different members of thing q */
};

/* Can happily pass t_node or q_node lists to free_list() */
于 2009-07-30T13:39:54.130 に答える
1

すべての Node 構造体が「next」ポインターを最初の「メンバー」として宣言されている場合、次のようにします。

struct _Node{
    struct _Node *next;
    /* more data */
};

次に、このような関数を持つことができます

void free_list(void *p)
{
    void *next;
    while (p != NULL) {
        /*getting the content of the first field, assuming that
          sizeof(void*)==sizeof(unsigned long)*/
        next = (void*)*((unsigned long*)p); 
        free(p);
        p = next;
    }
}

free_list(head_of_list)このようにして、このパターンに従う任意のリストを呼び出すことができます。

于 2009-07-30T13:26:47.777 に答える
0

必要なのは、まさに C++ テンプレートが提供するものです。C では、void ポインターとマクロを使ってやっかいなことをすることに行き詰まっています。

于 2009-07-30T13:14:33.447 に答える
0

リンクされたリストを使用している場合は、マネージ メモリを使用したいと考えています。リンクされたリストを使用する効果的な方法は、構造の共有です。プログラムが複雑になるにつれて、何百万もの共有リストや部分共有リストが作成されることになります。他の多くのリストの一部を共有するリストが作成されます...面倒です。

Lisp は早い段階でガベージ コレクションを使用してこれに対処する方法を開発しましたが、C/C#/Java 環境でガベージ コレクションを使用できるようになった今、元に戻す必要はありません。

本当にできない場合は、ポインターの周りに参照カウント ラッパーを配置することで、貧弱なガベージ コレクションを実行できます。「スマート ポインター」を参照してください。しかし、これはマネージド メモリよりもはるかに厄介です。

于 2009-07-30T13:51:03.820 に答える