4

リンクされたリストを逆にする反復的および再帰的な方法を書きたいと思います。

残念ながら、どちらの場合も同様の問題が発生しています。1 つのノードのポインターを別のノードに変更することができず、場合によってはリストを繰り返し処理するのに苦労しています。たとえば、これが私の再帰的逆関数です。

node *reverse(node *initial){
    node *prev = initial;
    node *nextNode;
    nextNode = (node *)malloc(sizeof(struct node));
    nextNode = initial->next;
    if(nextNode->next == NULL){
        return  prev;
    }
    else{
        nextNode = reverse(nextNode);
        nextNode->next = prev;
    }
}

行nextNode = initial->next;はプログラムをクラッシュさせます。このコードには他にも多くの問題があると確信しています。致命的な欠陥がある場合は提案を受け付けていますが、ほとんどの場合、このエラーを解決して残りを自分でデバッグできるようにしたいと考えています。反復バージョンで、プログラムをクラッシュさせる同様の行のいくつかは次のとおりです。

startA = startA->next; // startA is a node pointer
backNode = startB; // backNode and startB are both node pointers
backNode->data = frontNode->data; //both ints
frontNode->data = temp; //again both ints

リクエストに応じて、コードの残りの部分:

main(){
node *  start = buildList();
int i;
int nodeSize = sizeof(struct node);
reverse(start);
}

そしてbuildList：

node *buildList(){
node *head = NULL;
node *second = NULL;
node *third = NULL;
node *fourth = NULL;
node *fifth = NULL;

head = (node *)malloc(sizeof(struct node));
second = (node *)malloc(sizeof(struct node));
third = (node *)malloc(sizeof(struct node));
fourth = (node *)malloc(sizeof(struct node));
fifth = (node *)malloc(sizeof(struct node));

head->data = 1;
head->next = second;

second->data  =2;
second->next = third;

third->data = 3;
third->next = fourth;

fourth->data =4;
fourth->next = fifth;

fifth->data = 5;
fifth->next = NULL;

return head;    
}
4

2 に答える 2

3

nextNode->nextステートメントで逆参照するときifは、 をチェックしていないことに注意してくださいnextNode == NULL。

基本的にあなたがやっている：

if (initial->next->next == NULL)

の場合、ここで何が起こりますかinitial->next == NULL? これは、再帰base-caseの問題でもあります。

さらに、あなたmallocは無駄になり、メモリリークを引き起こします:新しいメモリブロックに割り当ててから、次の行でnextNode何か他のものを割り当てると、そのブロックへの参照が失われます: Aはここでは不要です: 新しいメモリを追加していませんノードをリストに追加し、所有しているノードのみを並べ替えます。nextNodenextNode = initial->next;malloc

再帰を実装するときは、 base-caseを慎重に検討してください。コードを使用して、再帰的にリストを最後のノードまで走査し、 を使用returnして逆方向にリストを再度作成します。リストの最後のノードにいることをどのように知ることができますか? これはbase-caseであり、再帰関数はそこから開始する必要があります。関数の引数だけを使用してこれを判断できますか?

これはあなたの現在のコードと大差ありませんが、あなたが投稿したコードにはいくつかの間違いがあります。

于 2012-06-18T21:35:55.333 に答える
1

簡単なチュートリアルを次に示します。

node *reverse(node *initial){

    if (initial is NULL)
        /* this is an empty list so return */
        return a null pointer;

    if (initial->next is NULL)
        /* this is the recursion base case under normal operation - one elem left */
        return initial;

    node *prev = initial;
    node *nextNode = initial->next;

    /* reverse the rest of the list starting at the next node */
    nextNode = reverse(nextNode);

    /* now just reverse the pointers */
    initial->next->next = prev;
    /*
     * but remember that prev->next still points to the wrong node,
     * we need to clear that 
     */
    prev->next = NULL;

    /* you were also missing the return case here */
    /* we want to keep track of the last element (the new head element) */
    /* keep passing this back up through the recursive steps */
    return nextNode;

}
于 2012-06-19T00:58:10.503 に答える