0

https://hotfile.com/dl/253309046/133284f/4_SinglyLinkedList.rar.htmlのプロジェクトがあり ます

この関数insertOrdered()はスコアを順番に挿入します。

私の質問は、「前の」変数を使用せずにこのループを書き直すことはできますか?

SinglyNode* current = head;
SinglyNode* previous= NULL;
while (current != NULL)
{
    if(newNode->score >= current->score)
        previous = current; 
    else
        break;
    current = current->next;
}

newNode->next   = previous->next;
previous->next  = newNode;
4

5 に答える 5

0

簡単な解決策は、頭の前に挿入する必要があるかどうかを最初に確認することです。current->nextそうでない場合は、あなたと同様のループを使用しますが、 （そうでない場合）と比較するとNULL、ループが終了すると、新しいノードが と の間に挿入されますcurrent。current->nextつまり、現在のコードのようにcurrent使用されます。previousの場合current->nextはNULL最後に挿入します。

于 2013-11-02T15:17:13.143 に答える
0

これをテストすることはできませんが、新しいノード設定コードを if ブロックに移動すると、以前の変数を削除できるはずです。

SinglyNode* current = head;
while (current != NULL)
{
    if(newNode->score >= current->score) {
        newNode->next  = current->next;
        current->next  = newNode; 
    }
    else break;
    current     = current->next;
}
if(current == NULL) { // got to end of list
    current->next  = newNode;
    newNode->next  = NULL;
}
于 2013-11-02T15:17:33.253 に答える
0

「前の」変数を削除することはできませんが、偽装することはできます。さらに、それが唯一の反復変数になるようにループを構成できます。

もちろん、新しいものを挿入するには、前のノードを更新してそれを指すようにする必要があります。

リストを先読みしてさまざまなケースを処理することにより、現在のノードからそれを行うことができます。

もう 1 つの方法は、前のノードのポインター フィールドへのポインターを保持することです。

node **ppnode;

for (ppnode = &head;
     *ppnode != NULL && (*ppnode)->value >= newnode->value;
     ppnode = &(*ppnode)->next) 
   ; /* empty body */

newnode->next = (*ppnode) ? (*ppnode)->next : NULL;
*ppnode = newnode;

ここでは、現在のノードを指すポインターを使用する代わりに、現在のノードを間接的に指すポインターcurrentを使用します。ppnodeそのノードを指す代わりに、そのノードを指すポインターを指します (したがって、適切に入力する必要があります: ポインターへのポインター: 二重星)。

最初のノードへのポインターはリストhead変数であるため、最初はppnodeその変数を指しheadます。その後の他のすべてのノードへのポインターnextは、前のノードのフィールドです。これらのnextフィールドのそれぞれheadは、リストの残りの部分のようです。したがって、この 1 つのppnode変数を使用して、前のノード自体を追跡することなく、更新する必要がある前のノード内の場所を追跡します。これにより、前のノードがない場合のリストの先頭を処理できます。

headnull の場合 (リストが空)をたどってみましょう。

ppnodeを指しheadます。しかし*ppnodenull であるため、ループ本体は実行されません。

ppnodeを指しているためhead、行は次のとおりです。

newnode->next = (*ppnode) ? (*ppnode)->next : NULL;
*ppnode = newnode;

次と同じ意味です。

newnode->next = head ? head->next : NULL;
head = newnode;

これらの行の条件チェックは、新しいノードが空のリストまたは空でないリストの末尾に追加された場合を処理します。リストが空であるか、その中のすべての値が新しい値よりも小さい場合、ループppnodeはリストの null ターミネータ (headリストが空の場合)、またはnext末尾ノードのフィールドを指して終了します。は null であるため*ppnode、 を参照することはできません(*ppnode)->next。次はありません。新しいノードは最後のノードであり、nextnull にする必要があります。

ここで、ヘッド ノードがあり、その値が大きいため、新しいノードを先頭に挿入する必要がある場合に何が起こるかを見てみましょう。この場合、前と同様に をppnode指し、条件は true です。ただし、条件が失敗するため、ループは実行されません。head*ppnode != NULL(*ppnode)->value >= newnode->value

ここでも、次のコードと同等のコードを実行しています。

newnode->next = head ? head->next : NULL;
head = newnode;

しかし、今回headは null ではないためnewnode->next = head->next、以前のようにnewnodeと が新しい になりheadます。

他のすべてのケースは、これら 2 つから進行します。ただし、 の代わりに、リストの残りのヘッドのような前のノードheadのポインターを使用してアクションが実行されます。next

于 2013-11-02T15:26:04.430 に答える