你如何插入一个排序的链表? [英] How do you insert into a sorted linked list?

问题描述

可能的重复:
LinkedList节点跳转"

我只需要一个按名称顺序排列的链表.我只能得到第 1、3、5、.. 节点.我只是想不到这么远.我想成为一名 C++ 程序员，但如果我不明白这是他们的希望吗?作为一名学生，STL 容器 std::lists 在这一点上对我来说不是一个选择.您在列表功能中看到的正是我正在尝试理解的内容.

I just need to have a linked list in order by name. I can only get it as far as 1st, 3rd, 5th, .. nodes. I just can't think this far. I want to be a C++ programmer but if I can't understand this is their any hope? STL containers std::lists are not an option for me at this point as a student. What you see in the list function is what I am TRYING to understanding.

list::node::node(const winery &winery) : item( winery.getName(), winery.getLocation(),
    winery.getAcres(), winery.getRating() ), nextByName( NULL ), nextByRating( NULL )
{

}

void list::insert(const winery& winery)
{
    node *current_node  = new node( winery ); // but came here and did this so it has new info!
    node *next_node     = NULL;
    node *tail_node     = current_node;

    if ( headByName == NULL ) // then we are here for the first item
    {       
        headByName   = current_node; // the list ptrs will have the first node's address. 
        headByRating = current_node; 
    }
    while ( headByName->nextByName != NULL )
    {
        headByName->nextByName = tail_node;
        tail_node = next_node;
        //next_node = current_node;
    }
    tail_node = new node( winery ); 
    headByName->nextByName = tail_node;
}

以及可供我使用的指针:

And the pointers that are available to me:

struct node
{
    winery  item;
    node *  nextByName;
    node *  nextByRating;
};

class list
{
    ...
private:
    node * headByName;
    node * headByRating;
};

推荐答案

当然有希望，我们都必须从某个地方开始！:)

Of course there's hope, we all have to start somewhere! :)

首先，我必须指出我自己的学生在你的实现中使用的一个危险的做法，它通常会导致很多人挠头才能找到问题:

First of all, I must point out a dangerous practice in your implementation that my own students used, and it usually resulted in lots of head scratching to find the problem:

while ( headByName->nextByName != NULL )
{
     headByName->nextByName = tail_node;
     tail_node = next_node;
     //next_node = current_node;
}

除非绝对必要，否则不要使用像 headByName 这样的列表成员作为循环中的迭代变量.您应该首先使用局部变量找到合适的节点，然后修改该节点.

Don't use a list member like headByName as your iterating variable within your loop unless it is absolutely necessary. You should find the appropriate node first using a local variable, and then modify that node.

也就是说，Rob Kennedy 是对的，您应该分别处理名称和评级(换句话说，纯"实现将有一个通用列表类的两个实例，它不知道什么是"name' 和 'rating' 的意思)，但是我假设上面的列表、节点和函数的接口是在作业中提供给您的(如果没有，请忽略我的其余答案:)).

That said, Rob Kennedy is right that you should handle the name and rating separately (in other words a 'pure' implementation would have two instances of a generic list class that is unaware of what 'name' and 'rating' mean), however I assume the interfaces for list, node and function above were given to you in the assignment (if not, disregard the rest of my answer :) ).

鉴于上述接口，我的方法如下:

Given the above interfaces, my approach would be as follows:

void list::insert(const winery& winery)
{
    node* wineryNode = new node(winery);
    assert (wineryNode);

    // Find  a node in the list with a name greater than wineryNode's
    node* prevNode = NULL;
    node* searchNode = headByName; // Note: not using the list member itself to iterate but a local variable
    while (NULL != searchNode && 
        searchNode.winery.getName() < wineryNode.winery.getName())
    {
        // Keep iterating through the list until there are no more items, or the right node is found
        prevNode = searchNode;
        searchNode = searchNode->nextByName;
    }   

    /* At this point searchNode is either NULL 
       or it's name is greater than or equal to wineryNode's */

    // Check for the case where the list was empty, or the first item was what we wanted
    if (NULL == prevNode)
    {
        headByName = wineryNode;
    }
    else
    {
        // prevNode is not NULL, and it's Name is less wineryNode's
        prevNode-> nextByName = wineryNode;
    }
    wineryNode->nextByName = searchNode;    

    /*  Now you just need to insert sorted by rating using the same approach as above, except initialize searchNode to headByRating, 
    and compare and iterate by ratings in the while loop. Don't forget to reset prevNode to NULL */
}

这篇关于你如何插入一个排序的链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！