反轉列表導致Seg錯誤

我想要遞歸地反轉鏈接列表。我有這些結構：反轉列表導致Seg錯誤

typedef Test test; 

typedef struct Node { 
    test t; 
    struct Node *nxt; 
} LNode; 

typedef struct { 
    int size; 
    LNode *first; 
} L;

其中Test是一個包含學生名稱和等級（測試成績）的結構。

void recursiveReverse(L * r) { 
     LNode * first; 
     first = r->first; //first node in list 

     reverseList(first); 
} 

void reverseList(LNode * first) { 
    LNode * rest; 
    rest = first->nxt; 

    reverseList(r,rest); 

    first->nxt->nxt = first; 
    first->nxt = NULL; 

    first = rest; 
}

但是，我似乎在嘗試這個時候得到一個段錯誤。我不允許更改函數recursiveReverse的參數參數，我被告知必須調用另一個函數，並將其用作遞歸調用函數（我有）。任何幫助將非常感激。

來源

2015-11-05 user3739406

如何進行遞歸結束了嗎？ –

從找到導致問題的最短列表（其中2或3個項目）開始。然後用調試器遍歷代碼，看看發生了什麼問題。 – user3386109

它不完全清楚爲什麼你的reverseList需要'r'參數。目前還不清楚你是如何試圖遵循鏈接的算法。您目前的計劃與此不相似。 –

編寫遞歸函數最重要的規則是它們必須終止。簡而言之，必須有一個條件，在該條件下，遞歸函數不是自己調用。這就是所謂的「基本案例」。

對於您的列表反轉函數，基本情況是當您必須反轉的列表部分恰好包含一個節點時，因爲單節點列表本身是一個微不足道的反轉。因此，需要在這裏你說的是裏面reverseList的情況是這樣的：

if (first->nxt == NULL) { 
    // Do not go into recursive invocation 
    return; // This is not complete yet 
}

是從你的代碼中缺少另一件事是，反向名單將有一個新的頭，這是用來節點成爲尾巴。你的reverseList應該返回它。

一個有用的技巧來編寫遞歸函數的其餘部分是想象的功能已經寫好給你，並與知識它做什麼稱呼它，遺忘了的一時間，如何做它。在列表反轉的情況下，遞歸步驟相對容易：獲取反轉列表的頭部，然後將當前節點的下一個更改爲指向當前節點。

LNode* reverseList(LNode* list) { 
    if (list->nxt == null) { 
     return list; 
    } 
    // Reverse the tail 
    LNode *head = reverseList(list->nxt); 
    // Invert this node 
    list->nxt->nxt = list; 
    // Return the result of tail reversal 
    return head; 
}

在這一點上唯一缺少的是設置了新的尾部的nxt到NULL。你應該做你recursiveReverse函數中：

void recursiveReverse(L * r) { 
    LNode *first = r->first; 
    LNode *newHead = reverseList(first); 
    first->nxt = NULL; 
    r->first = newHead; 
}

Demo.

來源

2015-11-05 18:50:01 dasblinkenlight

嗯，不應該頭調用反向列表，而不是反向？ – user3739406

另外我似乎仍然錯誤與此實施 – user3739406

@ user3739406是的，它需要是'reverseList'，而不是'reverse'。我修正了這一點。奇怪的是，你看到了這個實現的段錯誤。您是否能夠在演示中遵循實施？還要確保你正在構建你的列表。 – dasblinkenlight

反轉列表導致Seg錯誤

回答

相關問題