如何插入到排序链表中？ [英] How do you insert into a sorted linked list?

问题描述

可能重复：

LinkedListnode jump

我只需要一个链表按名称排序。我只能得到它一直到第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;
}

我可以使用的指针：

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是正确的，你应该分别处理名称和评级（换句话说，一个'纯'实现会有一个通用列表类的两个实例不知道'名称'和'评级'的意思），但是我假设列表，节点和函数的接口（如果没有，忽略我的回答:)）。

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屋！