1

我正在尝试创建一个从用户那里获取单词的链接列表，直到输入为空白，并且每个单词都被添加，因此列表保持字母顺序。但是，只打印第一个节点。有什么我做错了吗？这是我所拥有的（减去标题和声明）：

    //put in additional nodes until the input is blank
while(in != " "){
    cin >> in;
    newPtr->data = in;
    prevPtr->data = "";
    prevPtr->next = NULL;
    nextPtr = list;
    //shift the prevPtr and nextPtr until newPtr is alphabetically between them
    while(!(prevPtr->data<=in && nextPtr->data>in)){
        prevPtr = nextPtr;
        nextPtr = prevPtr->next;
    }
    //make newPtr point to the next node
    if(nextPtr != NULL){
        newPtr->next = nextPtr;
    }
    //make newPtr the "next" pointer of the previous node, if any
    if(prevPtr != NULL){
        prevPtr->next = newPtr;
    }
    //if there's nothing before newPtr, make it the first node
    else{
        list = newPtr;
    }
    printList(list);
};

}

4

2 回答 2

1

我会将此作为评论发布，因为我担心我可能会遗漏一些东西，但我还不能这样做，所以这里没有答案：

是什么让您无法使用std::list？您可以插入一个单词，检查它是否为非空，立即应用标准排序算法（它依赖于排序对象的比较运算符）并打印它。它速度快，您的代码简短易读，而且您无需花费时间重新发明轮子。

PS：如果你想测试一个空字符串，我认为它应该是""，而不是。" "

于 2012-10-16T22:56:51.767 回答
0

我认为这里有很多问题。

对于初始迭代中的一个，prevPtr->data 指向什么？如果它没有指向任何内容或尚未分配给任何内存，则您不应该将其设置为任何内容。

另外，您需要在每次迭代时为 newPtr 分配内存，否则您只是在覆盖列表中它指向的最后一个内存位置。

其次，假设 prevPtr 指向某个东西，在此 while 循环的第二次迭代（或更多）中，prevPtr 已在列表中向下移动（prevPtr = nextPtr），这将导致 prevPtr->data = "" 擦除其中的任何数据那个元素。所以你可以在之后打印第一个节点加上一堆空格。

第三，您应该首先在循环中检查 list 是否为 NULL，因为如果循环为 NULL，nextPtr->data 将指向垃圾，这是不好的。这个对列表的 NULL 检查可能是第一个元素的极端情况。

尝试这样的事情，我没有时间测试它，但它应该朝着正确的方向发展：

Node *list = NULL; 

while(in != " "){
    cin >> in;
    Node *newPtr = new Node();
    newPtr->data = in;
    newPtr->next = NULL;

    prevPtr = list;
    nextPtr = list;

    // Do we have an empty list
    if(list != NULL)
    {
        // Corner Case: First on the list
        if(newPtr->data <= prevPtr->data)
        {
            list = newPtr;
            newPtr->next = prevPtr;
        }
        else
        {
            // CASE: Somewhere between the first and the list
            while(nextPtr->next != NULL)
            {
                nextPtr = nextPtr->next;
                if(newPtr->data >= prevPtr->data && newPtr->data <= nextPtr->data)
                {
                    prevPtr->next = newPtr;
                    newPtr->next = nextPtr;
                    break;
                }
                prevPtr = prevPtr->next;
            }

            // Corner Case: end of list
            if(nextPtr->next == NULL)
            {
                nextPtr->next = newPtr;
            }
        }
    }
    else 
    {
        // Corner Case: We had an empty list
        list = newPtr;
    }
    printList(list);
于 2012-10-16T23:08:02.667 回答