1

Cで二重にリンクされたdequeリスト（バックセンチネルのみ）を元に戻すのに問題があります。ポインターを切り替えてアプローチしています。これまでのコードは次のとおりです。

/* Reverse the deque

 param:  q  pointer to the deque
 pre: q is not null and q is not empty
 post:  the deque is reversed
*/
/* reverseCirListDeque */
void reverseCirListDeque(struct cirListDeque *q)
{
 struct DLink *back = q->backSentinel;
 struct DLink *second = q->backSentinel->prev;
 struct DLink *third = q->backSentinel->next;

 while (second != q->backSentinel->next){
  back->next = second;
  third = back->prev;
  back->next->prev = back;
  back = second;
  second = third;
 }
}

しかし、機能していないようです。次のような両端キューを使用してテストしています。1、2、3出力は次のとおりです。3このプロセスは、数値の実際の値を台無しにしているようです。すなわち。2は2.90085e-309になります...ポインタの切り替えがめちゃくちゃだと思いますが、問題が見つかりません。そして、それは私のコードが正しいという意味ではありませんが、正常にコンパイルされます。

4

3 に答える 3

2

deque のようなリンクされた構造は再帰に適しているため、リンクされた構造を扱うときは再帰的なスタイルを好む傾向があります。これにより、各関数を簡単にテストできるように、段階的に記述することもできます。関数のループには多くの欠点があります。簡単にフェンスポスト エラーが発生する可能性があり、混乱を招く大きな関数になりがちです。

まず、ポインターを交換することでこれを行うことにしましたよね? したがって、ポインターを交換する関数を作成します。

void swapCirListDequePointers(
    struct cirListDeque** left,
    struct cirListDeque** right)
{
    struct cirListDeque* temp = *left;
    *left = *right;
    *right = temp;
}

次に、1 つのノードでポインターを反転する関数を作成します。

void swapPointersInCirListDeque(struct cirListDeque* q)
{
    swapCirListDequePointers(&(q->prev),&(q->next));
}

さて、再帰的にまとめます：

void reverseCirListDeque(struct cirListDeque* q)
{
    if(q == q->backSentinel)
        return;

    swapPointersInCirListDeque(q);

    // Leave this call in tail position so that compiler can optimize it
    reverseCirListDeque(q->prev); // Tricky; this used to be q->next
}

あなたの構造体がどのように設計されているか正確にはわかりません。私の関数は、両端キューが循環的であり、番兵でこれを呼び出すことを前提としています。

編集:両端キューが循環的でない場合はswapPointersInCirListDeque(q)、センチネルも呼び出す必要があるため、ステートメントswapPointersInCirListDeque(q)の前に移動します。if

この後に backSentinel を使用する予定がある場合は、これも変更する必要があります。これは、リストの先頭になっているためです。frontSentinel がある場合は、 に追加swapCirListDequePointers(&(q->frontSentinel),&(q->backSentinel));するだけswapPointersInCirListDequeです。それ以外の場合は、最初のノードを一緒に渡し、それにq設定q->backSentinelする必要があります。

于 2010-07-20T03:54:12.410 に答える
1

二重にリンクされたリストの場合は、ポインタをまったく変更する必要はありません。ペイロードを交換するだけです。

pointer1 = first
pointer2 = last
while pointer1 != pointer2 and pointer2->next != pointer1:
    temp = pointer1->payload
    pointer1->payload = pointer2->payload
    pointer2->payload = temp
    pointer1 = pointer1->next
    pointer2 = pointer2->prev

バックセンチネルがポインターを意味する場合last（最初のポインターが使用できない場合など）、それを見つけるために両端キューをスローする必要があります。ただし、これはかなり非効率的なdeque（両端キューであると想定されている）であるため、これが当てはまるとは信じがたいです。

于 2010-07-20T03:31:03.040 に答える
0

すでにいくつかの提案が与えられています。ここに別の可能性があります：

// Assumes a node something like:
typedef struct node { 
    struct node *next, *prev;
    int data;
} node;

また、両端キューの先頭と末尾をそれぞれ指すheadとという名前の変数 (当面はグローバル) を想定しています。tail

void reverse()  {
    node *pos = head;
    node *temp = pos->next;

    head = tail;
    tail = pos;

    while (pos != NULL) {
        node *t = pos->prev;
        pos->prev = pos->next;
        pos->next = t;
        pos = temp;
        if (temp)
            temp = temp->next;
    }   
}

少なくとも現時点では、これはセンチネルを想定していません。リストの終わりを知らせる NULL ポインタだけです。

両端キューに s を格納するだけの場合int、Paxdiablo の提案は適切です (ただし、an のみを保持するために二重にリンクされたノードを作成するのintは非常に無駄です)。実際には、二重にリンクされたノードが意味をなすのに十分な大きさの何かを保存していると仮定すると、少なくとも一般的なルールとして、必要以上にそのデータを移動することを避けることもできます。

于 2010-07-20T04:05:07.233 に答える