28

これは厳密には技術的な質問ではありません。Cが必要なことを実行するのに十分なことを知っているので（つまり、「言語を邪魔させない」という意味で）、この質問は基本的に「どの方向」です。質問をします。

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

このトピックのリストに焦点を当てています。これは通常、プログラムで「メイン」構造として、または他の大きな構造（たとえば、解決するハッシュツリー）の「ヘルパー」構造として多く使用する構造だからです。リンクリストを使用して競合します）。

これには、リストにさまざまなタイプの要素が格納されている必要があります。ここでは、すべてのタイプのリストを再コーディングしたくないという前提として想定しています。だから、私はこれらの選択肢を思い付くことができます：

  • voidポインタのリストを作成する（ちょっとエレガントではない;デバッグが難しい）
  • リストを1つだけ作成しますが、 「要素タイプ」として結合を持ち、プログラムで使用するすべての要素タイプを含みます（デバッグが簡単です。要素がすべて同じサイズでない場合はスペースを浪費します）
  • プリプロセッサマクロを使用して、SGLIBのスタイルですべてのタイプのコードを再生成します。コードは本当に劇的になる可能性があります）
  • あなたのアイデア/解決策

質問を明確にするために：上記のどれが最良ですか？

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

4

9 に答える 9

33

Avoid *は、リスト自体への割り当てを個別に管理する必要があるため、リンクリストでは少し面倒です。私が過去に使用したアプローチの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のアドレスを実際の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;
于 2009-04-10T00:49:31.667 に答える
8

私の$.002：

  • voidポインタのリストを作成する（ちょっとエレガントではない;デバッグが難しい）

Cで記述する必要がある場合、これはそれほど悪い選択ではありません。デバッグを容易にするために、アプリケーションがprint（）メソッドを提供できるようにするAPIメソッドを追加することができます。（例）アイテムがリストに追加またはリストから削除されると、同様のメソッドが呼び出される可能性があります。（リンクリストの場合、これは通常は必要ありませんが、より複雑なデータ構造（ハッシュテーブルなど）の場合は、命の恩人になることがあります。）

  • リストを1つだけ作成しますが、「要素タイプ」として結合を持ち、プログラムで使用するすべての要素タイプを含みます（デバッグが簡単です。要素がすべて同じサイズでない場合はスペースを浪費します）

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

  • プリプロセッサマクロを使用して、SGLIB（sglib.sourceforge.net）のスタイルですべてのタイプのコードを再生成し、C ++のSTLを模倣します（創造的なソリューション。スペースを無駄にしません。要素には、実際のタイプの明示的なタイプがあります。リストコードの変更は本当に劇的なものになる可能性があります）

面白いアイデアですが、SGLIBを知らないので、それ以上のことは言えません。

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

私は最初の選択肢で行きます。

于 2009-04-10T00:22:02.857 に答える
6

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

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

于 2009-04-10T00:24:04.957 に答える
6

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

FreeBSD / OpenBSD sys / queueは、一般的なマクロベースのリンクリストのもう1つの優れたオプションです。

于 2009-06-07T07:53:38.877 に答える
4

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

于 2009-04-10T01:05:37.867 に答える
1

これは良い問題です。私が好きな2つの解決策があります：

  • DaveHansonのCInterfacesand Implementationsは、ポインターのリストを使用しvoid *ています。これは私にとっては十分です。

  • 学生のために、タイプ固有のリスト関数を生成するawkスクリプトを作成しました。プリプロセッサマクロと比較すると、追加のビルドステップが必要ですが、システムの操作は、多くの経験がなくてもプログラマーにとってはるかに透過的です。そして、それは彼らがカリキュラムの後半で見るパラメトリック多型の主張をするのに本当に役立ちます。

    1セットの関数は次のようになります。

    int      lengthEL (Explist *l);
Exp*     nthEL    (Explist *l, unsigned n);
Explist *mkEL     (Exp *hd, Explist *tl);

    awkスクリプトは150行のホラーです。Cコードでtypedefsを検索し、それぞれのリスト関数のセットを生成します。とても古いです。私はおそらく今より良くすることができます:-)

組合のリストは、時刻（またはハードドライブのスペース）は提供しません。それは安全ではなく、拡張可能でもないので、それを使用void *してそれで済ませた方がよいでしょう。

于 2009-04-10T01:22:41.167 に答える
1

ジェネリックなどの別の言語の手法を使用してこの種の問題を解決することを考えたくなりますが、実際にはそれが成功することはめったにありません。おそらく、ほとんどの場合それを正しくする（そしてそれらが間違っているときはドキュメントであなたに伝える）いくつかの缶詰の解決策があり、それを使用すると割り当てのポイントを逃す可能性があるので、私はそれについて2度考えます。ごく少数のケースでは、自分でロールすることは可能かもしれませんが、妥当なサイズのプロジェクトの場合、デバッグ作業の価値はないでしょう。

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

私自身、おそらくPaxの提案のようなものを使用することになりますが、実際には、char[1]とvoid*およびintの和集合を使用して、一般的なケース（および列挙型フラグ）を便利にします。

（私はおそらくフィボナッチツリーを実装することになります、それはきちんと聞こえるだけです、そしてそれが使用される一般的なケースにはそれがより良いとしても、それが味を失う前にあなたはRBツリーを何度も実装することができます。）

編集： あなたのコメントに基づくと、缶詰のソリューションを使用するためのかなり良いケースがあるようです。インストラクターがそれを許可し、それが提供する構文が快適であると感じたら、それを回転させてください。

于 2009-04-10T01:23:23.223 に答える
0

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

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

または、途中まで進んでください。Perlライブラリとリンクして、PerlSVなどのリストにします。

于 2009-04-10T02:19:55.350 に答える
0

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

于 2009-04-10T02:22:43.410 に答える