遞歸反向字符串鏈表

我想首先用用戶輸入的字符串創建一個鏈表（直到用戶輸入一個句號），然後遞歸地反轉它，然後打印新的列表。下面的程序是我到目前爲止：它正在編譯，但只顯示最後一個字。我認爲，在某些時候，我將一個新的字符串分配給以前某個字符串的內存位置。我對C++比較陌生，想不起我出錯的那一刻。任何意見或提示將不勝感激！謝謝遞歸反向字符串鏈表

#include <iostream> 
#include <string> 
using namespace std; 

//create a node that reads a string and points to next one 
struct Node 
{ 
    string word; 
    Node * next; 
}; 

//create current and temporary pointers for Node 
Node * current; 
Node * temp; 

//function to reverse Node 
void Reverse(struct Node * p, Node * hdr) 
{ 
    if (p->next == NULL) 
    { 
     hdr = p; 
     return; 
    } 
    Reverse(p->next, hdr); 
    struct Node * q = p->next; 
    q->next = p; 
    p->next = NULL; 
    return; 
    } 

//function to print linked list 
void print(Node * header) 
{ 
    cout << "The reversed linked list is: " << endl; 
    Node * ptr = header; 
    while(ptr!=NULL) 
    { 
     cout << ptr->word << " "; 
     ptr = ptr->next; 
    } 
} 

int main() 
{ 
    //Ask user to input keyboard strings 
    cout << "Please insert strings seperated by white spaces (isolated full-stop to finish): " << endl; 
    string input; 

    //create head pointer 
    Node * head = new Node; 
    head->next = NULL; 

    //create loop to read words and insert them into linked list 
    while(true) 
    { 
     cin >> input; 
     if (input == ".") 
      break; 
     current = new Node; 
     current->word = input; 
     current->next = head->next; 
     head->next = current; 
    } 

    //get and output reversed linked list 
    Reverse(current, head); 
    print(head); 
    cout << " ." << endl; 

    return 0; 
}

來源

2015-11-28 Melanie

似乎在生成鏈接列表，你已經扭轉你的列表。如果你跟蹤列表的頭部和尾部（尾部插入，頭部指向第一個元素） – Stefan

所以你的意思是我的錯誤是在第一個鏈接列表中創建鏈接列表時地點？我怎樣才能最好地保持標題不斷指向第一個輸入（循環外），同時獲得新的輸入（循環內）？謝謝Stefan！ – Melanie

我認爲反向功能也有問題。您正確地瀏覽列表，但我認爲在您返回時會丟棄信息。我認爲最好的分析方法是使用3個節點的例子在紙上繪製列表。至於標題，你可以在循環之前創建一個新節點，然後在循環中填入信息，然後創建下一個節點，仍然在循環中 – Stefan

試試這個：

void recursiveReverse(struct node** head_ref) 
{ 
    struct node* first; 
    struct node* rest; 

    /* empty list */ 
    if (*head_ref == NULL) 
     return; 

    /* suppose first = {1, 2, 3}, rest = {2, 3} */ 
    first = *head_ref; 
    rest = first->next; 

    /* List has only one node */ 
    if (rest == NULL) 
     return; 

    /* reverse the rest list and put the first element at the end */ 
    recursiveReverse(&rest); 
    first->next->next = first; 

    /* tricky step -- see the diagram */ 
    first->next = NULL;   

    /* fix the head pointer */ 
    *head_ref = rest;    
}

參考http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/

來源

2015-11-28 14:58:37

如果你想遞歸地反轉一個鏈表，你將不得不使用一個雙指針。 –

因此，如果我稍後在主函數中使用recursiveReverse函數，我可以插入哪個參數？我用「頭」試過，但它不兼容。 – Melanie

發送和頭。請投票答案，如果它幫助你:) –

遞歸反向字符串鏈表

回答

相關問題