插入链接列表问题

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。