11

私は C 職の面接を受けていましたが、そこで彼らは私が以前に遭遇したことのないイディオムを提示されました。これは、リンクされたリストを含むさまざまなアルゴリズムの実装を簡素化するトリックであり、他の誰かがこれに遭遇したかどうか疑問に思っています.

次のように定義されたリンク リスト レコードがあるとします。

typedef struct _record
{
    char* value;
    struct _record* next;
} record;

リスト全体がレコード内の値に関してソートされたままになるように、新しいレコードを挿入する関数が必要です。次の実装は、読みにくいとはいえ、私が使用したどの実装よりも単純です。

void insert_sorted(record** r, const char* value)
{
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0)
        r = &((*r)->next); /* move r to point to the next field of the record */
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
}

関数が呼び出されると、r はリストの先頭ポインターを指します。while ループの間、r が更新されてnext、新しいレコードを挿入したいポイントの直前にあるレコードのフィールドを指すようになります。関数の最後の行は、リストのヘッド ポインターを更新します (挿入がが最初に発生する) またはnext前のレコードのフィールド、これは非常にクールです。

いくつかの質問:

  • このイディオムには名前がありますか、それとも文献で言及されていますか?

  • C言語で似たようなものは他にありますか?

私は C をかなりよく知っていて、ポインターと間接参照をかなりよく理解していると思っていましたが、これは完全に理解するのに時間がかかりました。

4

11 に答える 11

8

慣用句は「「c」に悪い名前を付けた種類のコード」だと思います

  • 不当に賢い
  • 不当にコンパクト
  • 呼び出し元に対する驚くべき副作用
  • malloc でのエラー処理なし
  • 米国英語の文字列でのみ機能します
于 2008-12-01T22:38:43.070 に答える
6

これに似たものを使用して、二分木に挿入しました。ツリーを反復するとき、通常、ポインターがNULL(ツリーから逃げた) になったときに停止するためです。

挿入するには、3つのオプションがあります。

1: 反復ポインターの前の値を追跡する変数を使用します。

2: フォローするポインターが NULL の場合は、フォローする前に停止します。機能しますが、私の意見ではエレガントではありません。

3: または、より洗練された解決策は、単純にポインターへのポインターを使用することです。そのため、次のように実行するだけで、ツリー内*it = new_node();の以前の場所に追加されます。NULL

リンクされたリストの場合、このコードはうまく機能しますが、通常は二重にリンクされたリストを使用するだけで、任意の場所に簡単に挿入できます。

于 2008-12-01T23:52:49.693 に答える
4

それ自体イディオムと呼べるものは何もありません。Cでデータ構造を扱うときの標準的なコーディングのようです。

私の唯一の不満は、呼び出し元のポインター (*r) が変更されていることです。関数の使用方法によっては、予期しない副作用が予想されます。予期しない副作用を取り除くだけでなく、ローカル変数を使用して *r の役割を果たすと、コードが読みやすくなります。

于 2008-12-01T22:29:28.487 に答える
3

ここのイディオムは何でしょう？確かに、リンクされたリストの実装ではありません。ポインター構造へのポインターの使用? コンパクトループ？

個人的には、入力値を操作する代わりにポインターの戻り値を使用します。この入力データ型を見るとベルが鳴るので、関数に渡す前に値をコピーする必要があります。

于 2008-12-01T22:29:55.977 に答える
3

これはよく知られていることです - ダブルポインター反復 (これは私の名前です。正式な名前はわかりません)。目標は、単一のリンクされたリスト内の位置を見つけて、その位置の前に挿入できるようにすることです (後の挿入は簡単です)。単純に実装すると、これには 2 つのポインター (current と prev) と、リストの開始用の特別なコード (prev == NULL の場合) が必要です。

私が通常書いているコードは、次の行に沿ったものです

void insertIntoSorted(Element *&head, Element *newOne)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && less(curr, newOne)) {
    pp = &(pp->next);
  }
  newOne->next = *pp;
  *pp = newOne;
}

アップデート：

このトリックのもう 1 つの目的、つまりもっと重要な目的を忘れてしまいました。単一のリンクされたリストから要素を削除するために使用されます。

// returns deleted element or NULL when key not found
Element *deleteFromList(Element *&head, const ElementKey &key)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && !keyMatches(curr, key)) {
    pp = &(pp->next);
  }
  if (curr == NULL) return NULL;
  *pp = (*pp)->next; // here is the actual delete
  return curr;
}
于 2008-12-01T23:07:52.950 に答える
2

これに名前があるのか​​、それとも特別なイディオムなのかはわかりませんが、最近ではメモリが比較的豊富になっているため、リンクされたリスト (言語ライブラリがそれらを利用できない場合) は、コードを大幅に簡素化する特別なバリアントです。 .

まず、これらは常に二重にリンクされています。これにより、処理と挿入/削除操作の両方で、双方向のトラバーサルが容易になります。

「空の」リストは、実際には、ヘッドとテールの 2 つのノードで構成されます。これにより、挿入と削除では、削除するノードが先頭か末尾かを気にする必要がなくなり、中間ノードと見なすことができます。

ノード x の前に新しいノード y を挿入すると、次のようになります。

x -> prev -> next = y
y -> next = x
y -> prev = x -> prev
x -> prev = y

ノード x の削除は簡単です。

x -> prev -> next = x -> next
x -> next -> prev = x -> prev
free x

余分な頭と尾を無視するようにトラバーサルが調整されます。

n = head -> next
while n != tail
    process n
    n = n -> next

これはすべて、いくつかのメモリノードを犠牲にして、エッジケースの特別な処理をすべて行わなくても、コードを理解しやすくするのに役立ちます。

于 2008-12-01T22:32:10.917 に答える
1

新しいノードの値を in/out パラメータとして返す代わりに、それを関数の戻り値にする方がよいでしょう。これにより、呼び出しコードと関数内のコードの両方が簡素化されます (これらの見苦しい二重間接参照をすべて取り除くことができます)。

record* insert_sorted(const record* head, const char* value)

malloc/strdup が失敗した場合のエラー処理がありません。

于 2008-12-01T22:52:22.687 に答える
1

このイディオムは、「C 上のポインター」の第 12 章に記載されています。これは、リスト ヘッドのないリンク リストにノードを挿入するために使用されます。

于 2013-09-01T14:22:46.413 に答える
1

元の質問に答えるために、これは単純なノード中心のアプローチではなく、ポインター中心のアプローチとして知られています。amazon.comで入手可能な Rex Barzee による「Advanced Programming Techniques」の第 3 章には、ポインター中心のアプローチのより優れた実装例が含まれています。

于 2008-12-10T02:29:21.913 に答える
0

トリックにもかかわらず、変数 "r" の役割は変更されていませんか? 電話をかけた後、発信者は「*r」が何であるかをどのように伝えますか? または実行後、リストのヘッダーは何ですか?

これが例証できるとは信じられませんでした（本でさえ?!）。何か見逃しましたか？

（他の人が提案したように）ポインターを返さない場合は、入力の役割を維持するために次の変更をお勧めします。

void insert_sorted(record** head, const char* value)
{
    record** r = head;
    bool isSameHead = false;
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0) {
        r = &((*r)->next); isSameHead = true; }
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
    if (!isSameHead) *head = newrec;
}

実際には、おそらくそれを行う別のより良い方法は、「ダミーヘッドノード」を使用することです。これは、次をリストの先頭にリンクします。

    void insert_sorted(record** head, const char* value)
    {
        record dummyHead;
        dummyHead.next = *head;
        record* r = &dummyHead;
        while(r->next) {
           if(strcmp(value, r->next->value) < 0) 
              break;
           r = r->next;}
        newrec = malloc(sizeof(record));
        newrec->value = strdup(value);
        newrec->next = r->next;
        r->next = newrec;
        *head = dummyHead.next;
    }
于 2014-02-02T17:20:00.487 に答える