2

POSIXバイナリツリー関数のマンページには、次のステートメントが含まれています。

tdelete()削除されたアイテムの親へのポインタを返すNULLか、アイテムが見つからなかった場合に返します。

tdelete()ツリー内のノードに必要なメモリを解放します。ユーザーは、対応するデータ用にメモリを解放する責任があります。

これは、呼び出しから特定のキーのノードのデータにアクセスする方法がないことを意味しtdelete()ます。tfind()（指定されたキーを追加しないためではなく）呼び出しtsearch()、ノードのデータの破棄を実行してから、同じキーで呼び出しtdelete()て、バイナリツリーからノードを削除する必要があります。

私はこれを正しく解釈しましたか？このアプローチの制限であると私が感じるものを回避する方法はありますか？

  1. キーがヒープに割り当てられている場合、ノードが削除される前にキーを解放することはできません（または使用中の比較機能で使用できなくなります）。これにはtfind()、データへのポインタを取得するために呼び出しtdelete()、ノードを削除してから、呼び出しから取得したデータを破棄する必要がありtfind()ます。
  2. ノードを削除し、囲まれたデータを破棄するには、2回のルックアップが必要です。
4

3 に答える 3

2

マット、あなたの解釈は正しいと思います。要素を個別に削除する場合、これは避けられないようです。（しかし、とにかく、\ Omega \ log Nコストの操作では2倍にすぎません;）

長い間、これらの関数を使用していませんでしたが、古いコードを見ると、次の2つの呼び出しを使用して、ツリーを一度に破棄すると（この場合）、オーバーヘッドの一部を回避できるようですtwalk。

  1. Nを適切に呼び出して、ツリー内の要素の数を数えますtwalk
  2. Nポインタのサイズの配列をツリーアイテムに割り当てます
  3. この配列をtwalk ツリー全体に1秒で埋めます
  4. この配列を実行し、ツリーノードごとに最初にデータを削除してからノード自体を削除します

本当にそのようなものが必要な場合は、ディレクトリ内のライブラリparXXLで、これらの呼び出しのスレッドセーフなC++カプセル化を見つけることができますpar/sys。

于 2010-09-11T16:01:29.850 に答える
1

私はこれまでこの一連の関数を使用したことがありませんが、あなたは正しいようです。ただし、から返されたポインタをへの引数tfind()として使用してみます。これにより、2番目の検索は基本的にノーオペレーションになります。AFAICT、データ構造により、任意のノードをルートとして扱うことができるため、ノードを見つけて、見つけたノードをルートとするサブツリーから削除します。rootptdelete()

于 2010-09-11T14:36:12.723 に答える
0

D.Shawleyのように、私はこれまでこれらの関数を使用したことがないので、メモリリークを引き起こす小さなテストプログラムを作成しました。

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

int fx(const void *a, const void *b) {
  if (*(int*)a < *(int*)b) return -1;
  return (*(int*)a > *(int*)b);
}

int main(void) {
  int i, *elem;
  void *root = NULL, *val;

  for (i = 0; i < 10; i++) {
    elem = malloc(sizeof *elem); /* LEAK, leak, leak */
    *elem = i/2;
    val = tsearch(elem, &root, fx); /* assume all OK */
    printf("i: %d; elem: %p (%d); val: %p (%x)\n",
           i, (void*)elem, *elem, val, *(int*)val);
  }

  for (i = -1; i < 6; i++) {
    val = tfind(&i, &root, fx);
    printf("i: %d; ", i);
    if (val) {
      printf("@%p (%x)\n", val, *(int*)val);
    } else {
      printf("NOT FOUND\n");
    }
  }

  return 0;
}

それを実行すると出力

i：0; elem：0xcb8010（0）; val：0xcb8030（cb8010）
i：1; elem：0xcb8060（0）; val：0xcb8030（cb8010）
i：2; elem：0xcb8080（1）; val：0xcb80a0（cb8080）
i：3; elem：0xcb80d0（1）; val：0xcb80a0（cb8080）
i：4; elem：0xcb80f0（2）; val：0xcb8110（cb80f0）
i：5; elem：0xcb8140（2）; val：0xcb8110（cb80f0）
i：6; elem：0xcb8160（3）; val：0xcb8180（cb8160）
i：7; elem：0xcb81b0（3）; val：0xcb8180（cb8160）
i：8; elem：0xcb81d0（4）; val：0xcb81f0（cb81d0）
i：9; elem：0xcb8220（4）; val：0xcb81f0（cb81d0）
i：-1; 見つかりません
i：0; @ 0xcb8030（cb8010）
i：1; @ 0xcb80a0（cb8080）
i：2; @ 0xcb8110（cb80f0）
i：3; @ 0xcb8180（cb8160）
i：4; @ 0xcb81f0（cb81d0）
i：5; 見つかりません

どうやら「二分木の中」の値はデータへのポインタのコピーです。コピーは<search.h>関数によって管理され、データはプログラムによって管理される必要があります。

メモリ0xcb8030はへの呼び出しによって解放される必要がありtdelete()、対応する0xcb8010（値0のelem）はプログラム（および以前に失われた0xcb8060）によって解放される必要があります。

于 2010-09-11T15:24:00.797 に答える