純粋な C での「多目的」リンクリストの実装

https://stackoverflow.com/questions/736307

09-09-2019
|

質問

これは正確には技術的な質問ではありません。私は必要なことを行うのに十分な程度の C の知識があるからです (つまり、「言語を邪魔しない」という点で) この質問は基本的に「どのような方向に進むべきか」ということです。質問を受けます。

状況は次のとおりです。私は現在、高度なアルゴリズムのコースを受講しています。「プログラマーとして成長する」ために、実践的な課題を実装するために純粋な C を使用する必要があります (これはうまく機能します:小さな間違いを犯すと、それを修正するには自分が何をしているのかを完全に理解する必要があります)。実装の過程で、明らかに、「基本的な」データ構造をゼロから実装しなければならないという問題に遭遇します。実際には、リンクされたリストだけでなく、スタック、ツリーなども含まれます。

このトピックではリストに焦点を当てます。リストは通常、「メイン」構造として、または他のより大きな構造の「ヘルパー」構造として、プログラム内で頻繁に使用することになる構造だからです (たとえば、リンクリストを使用することで競合を回避します)。

これには、リストにさまざまなタイプの要素を格納する必要があります。 ここでは、すべての型のリストを再コーディングしたくないことを前提としています。したがって、次のような代替案が考えられます。

void ポインターのリストを作成する (ちょっと洗練されていない;デバッグが難しくなります)
リストを 1 つだけ作成しますが、連合「要素タイプ」として、プログラムで使用するすべての要素タイプを含みます（デバッグが容易です。要素がすべて同じサイズでない場合、スペースが無駄になります)
プリプロセッサマクロを使用して、次のスタイルですべての型のコードを再生成します。 SGLIB, 、C++ の STL を「模倣」します (創造的なソリューション;スペースを無駄にしません。要素は、実際に返されるときの明示的な型を持ちます。 リストコードの変更は非常に劇的になる可能性があります)
あなたのアイデア/解決策

質問を明確にするには:上記のどれが一番良いですか?

追伸：私は基本的に学術的な文脈にいるので、業界で純粋な C を使って作業している人々の意見にも非常に興味があります。純粋な C プログラマのほとんどは組み込みデバイス分野に属していることを私は理解していますが、そこで私が直面しているこの種の問題は一般的ではないと思います。ただし、「現実の世界で」それがどのように行われるかを知っている人がいたら、あなたの意見に非常に興味があります。

解決

あ void * リンクされたリストでは、リスト自体とは別に割り当てを管理する必要があるため、少し面倒です。私が過去に使用したアプローチの 1 つは、次のような「可変サイズ」の構造を持つことです。

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

今はそうではないことが分かりました見てサイズは可変ですが、次のように構造体を割り当てましょう。

typedef struct {
    char Name[30];
    char Addr[50];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

これで、全体的に次のようなノードが完成しました。

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char Name[30];
    char Addr[50];
} tNode;

または、グラフィック形式で (ここで、 [n] 手段 n バイト):

+----------------+
|    prev[4]     |
+----------------+
|    next[4]     |
+----------------+
| payloadType[4] |                
+----------------+                +----------+
|   payload[1]   | <- overlap ->  | Name[30] |
+----------------+                +----------+
                                  | Addr[50] |
                                  +----------+

つまり、ペイロードを正しくアドレス指定する方法を知っていると仮定します。これは次のようにして実行できます。

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

このキャスト行は、単に次のアドレスをキャストします。 payload キャラクター（ tNode type) を実際のアドレスにします。 tPerson ペイロードのタイプ。

この方法を使用すると、ノード内で必要なペイロードタイプを運ぶことができます。 各ノードの異なるペイロードタイプ, 、ユニオンの無駄なスペースなし。この無駄は次のことからわかります。

union {
    int x;
    char y[100];
} u;

ここで、リストに整数型を格納するたびに 96 バイトが無駄になります (4 バイト整数の場合)。

のペイロードタイプ tNode を使用すると、このノードが運んでいるペイロードの種類を簡単に検出できるため、コードでそれを処理する方法を決定できます。次のようなものを使用できます。

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

または (おそらくもっと良いでしょう):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

他のヒント

私の$.002:

void ポインターのリストを作成する (ちょっと上品ではありません。デバッグが難しくなります)

私の意見では、C で書かなければならない場合、これはそれほど悪い選択ではありません。API メソッドを追加して、デバッグを容易にするためにアプリケーションが print() メソッドを提供できるようにすることもできます。(たとえば) 項目がリストに追加またはリストから削除されるときに、同様のメソッドを呼び出すことができます。(リンクリストの場合、これは通常必要ありませんが、より複雑なデータ構造 (ハッシュテーブルなど) の場合は、場合によっては命の恩人になることがあります。)

作成するリストは 1 つだけですが、プログラムで使用するすべての要素タイプを含む「要素タイプ」として共用体を作成します (デバッグが容易です)。要素がすべて同じサイズでない場合、スペースが無駄になります)

私はこれを疫病のように避けたいと思います。(まあ、あなたは尋ねました。) データ構造からそれに含まれる型まで手動で構成されたコンパイル時の依存関係があることは、最も最悪です。繰り返しますが、私見です。

プリプロセッサマクロを使用して、SGLIB (sglib.sourceforge.net) のスタイルですべての型のコードを再生成し、C++ の STL を「模倣」します (創造的なソリューション。スペースを無駄にしません。要素は、実際に返されるときの明示的な型を持ちます。リストのコードに変更を加えると、非常に劇的な変更になる可能性があります)

興味深いアイデアですが、SGLIB については詳しくないので、それ以上のことは言えません。

あなたのアイデア/解決策

私なら最初の選択肢を選びます。

私は過去にコード (その後 C++ に変換されました) でこれを実行したことがありますが、そのときは void* アプローチを選択しました。私は柔軟性を高めるためにこれを行っただけです。とにかく、ほとんどの場合、リストにポインターを格納していたため、ソリューションの単純さと使いやすさが、他のアプローチの欠点を (私にとっては) 上回っていました。

そうは言っても、デバッグが難しい厄介なバグが発生したことがありましたので、完全な解決策ではありません。でも、もし今またこれをやるとしたら、まだそれを選択すると思います。

プリプロセッサマクロを使用することが最良のオプションです。の Linux カーネルのリンクリストこれは、C における循環リンクリストの効率的な実装として優れています。非常に持ち運びやすく、使いやすいです。ここ Linux カーネル 2.6.29 list.h ヘッダーのスタンドアロンバージョン。

FreeBSD/OpenBSD システム/キュー一般的なマクロベースのリンクリストのもう 1 つの良いオプションです

私は何年もCをコーディングしていませんでしたが、 GLib は、「文字列と一般的なデータ構造のためのユーティリティ関数の大規模なセット」を提供すると主張しており、その中にはリンクリストも含まれます。

この種の問題を別の言語のテクニック (ジェネリックなど) を使用して解決することを考えたくなりますが、実際にはそれがうまくいくことはほとんどありません。おそらく、ほとんどの場合正しく解決する既定の解決策がいくつかあるでしょう (そして、間違っている場合はドキュメントで知らせます)。それを使用すると、課題の要点を逸脱する可能性があるため、よく考えてみます。非常に少数のケースでは、独自に開発することも可能かもしれませんが、妥当な規模のプロジェクトの場合、デバッグの労力を費やす価値はあまりありません。

むしろ、言語 x でプログラミングする場合は、言語 x のイディオムを使用する必要があります。Python を使用しているときは Java を書かないでください。スキームを使用する場合は C を記述しないでください。C99 を使用している場合は、C++ を作成しないでください。

私自身は、最終的には Pax の提案のようなものを使用することになるでしょうが、実際には、一般的なケースを便利にするために、char[1]、void*、および int の共用体 (および列挙型フラグ) を使用します。

(私はおそらくフィボナッチツリーを実装することになるでしょう。それはきれいに聞こえるからです。RB ツリーを実装できるのは、その風味が失われるまでに何度も限られます。たとえそれが使用される一般的なケースではその方が良いとしても) 。）

編集： コメントによると、缶詰のソリューションを使用するためのかなり良いケースがあるようです。インストラクターが許可しており、その構文が快適であると感じる場合は、試してみてください。

これは良い問題です。私が気に入っている解決策は 2 つあります。

デイブ・ハンソンの C インターフェイスと実装のリストを使用します void * 私にとってはこれで十分です。
私のために学生, 、と書きました。 タイプ固有のリスト関数を生成する awk スクリプト. 。プリプロセッサマクロと比較すると、追加のビルド手順が必要ですが、システムの操作は、経験の浅いプログラマにとってもはるかに透過的です。そして、これは、カリキュラムの後半で登場するパラメトリックポリモーフィズムの根拠を示すのに非常に役立ちます。

1 つの関数セットは次のようになります。
```
int      lengthEL (Explist *l);
Exp*     nthEL    (Explist *l, unsigned n);
Explist *mkEL     (Exp *hd, Explist *tl);
```
awk スクリプトは 150 行の恐ろしいものです。Cコードを検索します typedefs を作成し、それぞれに対して一連のリスト関数を生成します。それはとても古いものです。おそらく今ならもっとうまくできるはずです:-)

私なら、ユニオンのリストに時刻 (またはハードドライブ上のスペース) を与えたくありません。これは安全ではなく、拡張性もないので、単に使用したほうがよいでしょう。 void * そしてそれで終わりです。

void* のリストにする場合の 1 つの改善点は、void* と、その型やサイズなど、void* が指すものに関するメタデータを含む構造体のリストにすることです。

その他のアイデア:Perl または Lisp インタプリタを埋め込みます。

または、途中まで進みます。Perl ライブラリとリンクして、Perl SV のリストなどにします。

私自身はおそらく void* アプローチを採用するでしょうが、データを XML として保存できることに思いつきました。次に、リストにはデータの char* だけを含めることができます (必要なサブ要素についてはオンデマンドで解析します)。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

純粋な C での「多目的」リンク リストの実装

純粋な C での「多目的」リンクリストの実装