插入鏈接列表問題

Question

問題出現在我寫的插入函數中。

3個條件必須工作，我測試了b/w 1和2，b/w 2和3，並且作爲最後一個元素，他們的工作。

---

編輯; 這是我自己的問題。我沒有意識到我把MAXINPUT = 3（而不是4）。我感謝所有幫助我成爲一個更好的程序員，採用更先進和C++的更簡潔特點的努力。

基本上，問題已經解決了。

---

效率不是我關心的（尚未）。請指導我完成這個調試過程。

非常感謝。

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

    struct List // we create a structure called List 
    { 
     string name; 
     string tele; 
     List *nextAddr; 
    }; 

    void populate(List *); 
    void display(List *); 
    void insert(List *); 

    int main() 
    { 
     const int MAXINPUT = 3; 
     char ans; 

     List * data, * current, * point; // create two pointers 
     data = new List; 
     current = data; 

     for (int i = 0; i < (MAXINPUT - 1); i++) 
     { 
     populate(current); 
     current->nextAddr = new List; 
     current = current->nextAddr; 
     } 

    // last record we want to do it sepeartely 

     populate(current); 
     current->nextAddr = NULL; 
     cout << "The current list consists of the following data records: " << endl; 
     display(data); 

    // now ask whether user wants to insert new record or not 

     cout << "Do you want to add a new record (Y/N)?"; 

     cin >> ans; 

     if (ans == 'Y' || ans == 'y') 
     { 
    /* 

    To insert b/w first and second, use point as parameter 
    between second and third uses point->nextAddr 
    between third and fourth uses point->nextAddr->nextAddr 
    and insert as last element, uses current instead 

    */  
    point = data; 
    insert(()); 
     display(data); 
     } 

     return 0; 
    } 


    void populate(List *data) 
    { 
     cout << "Enter a name: "; 
     cin >> data->name; 
     cout << "Enter a phone number: "; 
     cin >> data->tele; 

     return; 
    } 

    void display(List *content) 
    { 
     while (content != NULL) 
     { 
     cout << content->name << "  " << content->tele; 
     content = content->nextAddr; 
     cout << endl; // we skip to next line 
     } 

     return; 
    } 

    void insert(List *last) 
    { 
     List * temp = last->nextAddr; //save the next address to temp 
    last->nextAddr = new List; // now modify the address pointed to new allocation 
     last = last->nextAddr; 
     populate(last); 
     last->nextAddr = temp; // now link all three together, eg 1-NEW-2 

     return; 
    } 

Answer 1

您的代碼在我的機器上正常工作（一旦insert(())語句按照代碼註釋中的說明正確「填充」）。插入工作在所有位置。

---

別的東西，雖然：我最初看了一下您的insert功能。我想我給你如何讓它短一點，更容易理解的提示是怎麼回事：

void insert(List *last) 
{ 
    // create a new item and populate it: 
    List* new_item = new List; 
    populate(new_item); 

    // insert it between 'last' and the item succeeding 'last': 
    new_item->nextAddr = last->nextAddr; 
    last->nextAddr = new_item; 
} 

這將是可取的，因爲它首先創建一個新的，單獨的項目，用於插入做準備，只有這樣，當這個工作成功的時候，函數纔會與鏈表「混亂」。也就是說，不會受到影響，除了在最後陳述的鏈接列表，讓您的功能「更安全」。在您的實際插入的建設新的項目混合代碼與你的insert，版本對比這一點。如果在這個函數內出現問題，那麼鏈接列表的機會也會大大增加。

（什麼是人仍下落不明BTW是一個初步檢查所傳遞的參數last是否實際上是有效的，即不是一個空指針。）

---

PS：當然，你可以只使用一個標準C++ std::list容器而不是構建自己的鏈表，但看到你標記了你的問題beginner，我假設你想知道它是如何工作的。

Answer 2

第一步應該是將列表變成一個對象，而不是僅僅在main()中保留一堆指針。你想叫List一個對象，它知道它自己的第一個（也許是最後一個）元素。它也應該有像List.append()和List.insert()方法。

您目前的代碼幾乎不可讀。

Answer 3

使用std :: list，除非這是作業，在這種情況下它需要標記。

Answer 4

以我的經驗，我已經學會了從小開始測試，然後建立起來。我會引導你完成這些步驟。

順便說一句，鏈表是一個節點的容器。所以我們首先從節點類開始。

微創，節點必須有一個指針到另一個節點：

#include <iostream> 
#include <cstdlib> // for EXIT_SUCCESS 
#include <string> 

using std::cout; 
using std::endl; 
using std::cerr; 
using std::cin; 
using std::string; 

struct Node 
{ 
    // Add a default constructor to set pointer to null. 
    Node() 
    : p_next(NULL) 
    { ; } 

    Node * p_next; 
}; 

// And the testing framework 
int main(void) 
{ 
    Node * p_list_start(NULL); 

    // Allocate first node. 
    p_list_start = new Node; 

    // Test the allocation. 
    // ALWAYS test dynamic allocation for success. 
    if (!p_list_start) 
    { 
    cerr << "Error allocating memory for first node." << endl; 
    return EXIT_FAILURE; 
    } 

    // Validate the constructor 
    ASSERT(p_list_start->p_next == 0); 

    // Announce to user that test is successful. 
    cout << "Test successful." << endl; 

    // Delete the allocated object. 
    delete p_list_start; 

    // Pause if necessary. 
    cin.ignore(100000, '\n'); // Ignore input chars until limit of 100,000 or '\n' 

    return EXIT_SUCCESS; 
} 

編譯和運行這個簡單的測試。修正錯誤，直到它正確運行。

接下來，修改測試儀連接兩個節點：

INT主（無效） { 節點* p_list_start（NULL）; Node * p_node（NULL）; // < - 這是第二個節點的新聲明。 // ...

// Validate the constructor 
    ASSERT(p_list_start->p_next == 0); 

    // Allocate a second node. 
    p_node = new Node; 
    if (!p_node) 
    { 
     cerr << "Error allocating memory for 2nd node." << endl; 

     // Remember to delete the previously allocated objects here. 
     delete p_list start; 

     return EXIT_FAILURE; 
    } 

    // Link the first node to the second. 
    p_list_start->Link_To(p_node); 

    // Test the link 
    ASSERT(p_list_start.p_next == &p_node); 

    //... 

    // Delete the allocated object(s) 
    delete p_list_start; 
    delete p_node; 

    //... 

}

編譯修改。
它未能編譯，未定義的方法：Node :: Link_To
不用擔心，這是預期的。告訴我們編譯器正在工作。 :-)

的Link_To方法添加到Node結構：

struct Node 
{ 
    // ... 
    void Link_To(const Node& n) 
    { 
    p_next = &n; 
    return; 
    } 
    //... 
}; 

編譯和運行。測試應該通過。

此時鏈接過程已被驗證。將內容添加到節點。

由於Node對象已經過測試，我們不想去碰它。因此，讓我們從它繼承來創建內容的節點：

struct Name_Node 
: public Node // Inherit from the tested object. 
{  
    std::string name; 
    std::string phone; 
}; 

如果你還沒有學會繼承的是，您可以附加到現有的節點：

struct Node 
{ 
    //... 
    std::string name; 
    std::string phone; 
} 

在這一點上，你可以添加功能用於設置和顯示內容。添加測試語句。運行並驗證。

下一步將創建兩個內容節點並將它們鏈接在一起。在建立時，保留測試代碼。此外，如果東西有效，您可能希望將功能分成不同的功能。

欲瞭解此過程的更多信息，請查看Test Driven Development。