对双向链表进行排序 C++

2022-01-01 00:00:00 linked-list sorting c++

尝试通过遍历列表的循环来实现.

Trying to do it through a loop that traverses through the list.

在循环中，我将头节点提供给我定义的排序函数，然后我使用 strcmp 找出节点中的哪个名称应该排在最前面.

In the loop I'm feeding the head node into a sorting function that I have defined and then I'm using strcmp to find out if which name in the node should come first.

它不起作用，因为写名字太早了.

It is not working because writing the names too early.

我通过一次一个节点向下列表来线性比较它们，而不是回头看看第一个是否应该在最后一个之前.解释的那部分会很有帮助.

Im comparing them all linearly by going down the list one node at a time and not going back to see if the first should come before the last. That part explained would be helpful.

现在对我来说最重要的两个函数定义如下:我已尽力去做我认为适合排序功能的事情.

The two functions that are most important to me now are defined as follows: I have tried my best to do what I think is right for the sorting function.

void list::displayByName(ostream& out) const
{
    list *ListPtr = NULL;
    node *current_node = headByName;
    winery *wine_t = new winery(); 
    // winery is another class object type
    // im allocating it to prevent a crash when I call it.

    while ( current_node != NULL )
    {
        *(wine_t) = current_node->item;
        wine_t = ListPtr->sort( current_node );
        out << wine_t << endl;
        current_node = current_node->nextByName;
    }
    delete wine_t;
}

winery * const list::sort( node * current_node ) const
{
    // current_node is the first node.
    const char *SecondName = NULL, *FirstName  = NULL;
    winery *wine_t   = new winery();

    if ( current_node != NULL )
    {
        SecondName   = current_node->item.getName();            
        current_node = current_node->nextByName;
        FirstName    = current_node->item.getName();
    }

    if ( strcmp( FirstName, SecondName ) == -1 )
    {
        *(wine_t)  = current_node->item;
        FirstName  = NULL;
        SecondName = NULL;
        return wine_t;
    }
    else if ( strcmp( FirstName, SecondName ) == 1 )
    {
        *(wine_t) = current_node->item;
        FirstName = NULL;
        SecondName = NULL;
        return wine_t;
    }
    else return wine_t;// then the strings are equal

    FirstName  = NULL;
    SecondName = NULL;
    return wine_t;
}

然后我开始在这里开发我的节点:

And I started to develop my nodes here:

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

    if ( headByName == NULL )
    {
        headByName   = current_node;
        headByRating = current_node;
        tail         = headByName;
        current_node->prev = current_node;
    }
    else
    {
        current_node->prev = tail;
        tail->nextByName   = current_node;
    }

    tail = current_node;
    current_node = NULL;
}

我认为它在上面的函数中是正确的.我可以在那里分类吗?

I think its correct in that function above. Could I possibly get away with sorting it there?

以下是我正在使用的变量:

Below are my varaibles that I am working with:

public list
{
         ...
    void insert(const winery& winery);
    void displayByName(ostream& out) const;
}
private:
    struct node
    {
        node(const winery& winery);     // constructor
        winery item;
        node * prev;
        node * nextByName;
        node * nextByRating;
    };

    winery * const sort(node*) const;
    node * headByName;
    node * headByRating;
    node * tail;
};

感谢任何帮助.非常感谢 =)

Any help is appreciated. Thanks very much =)

推荐答案

据我所知，您希望 list::sort 找到列表中大于输入的最小节点.

From what I understand, you want list::sort to find the least node in the list which is greater than the input.

为此，您需要遍历所有元素并保留找到的当前最小但更大的节点.

To do this, you need to iterate through all the elements and keep the current least-but-greater node found.

像这样:

node * const list::sort( node * given_node ) const
{
    if ( given_node == NULL )
    {
        return NULL;
    }

    // Smallest node found which is greater than given_node.
    node * least_found_node = NULL;

    // Node we are looking at right now.
    node * current_node = given_node->nextByName;

    // Go through all nodes.
    while ( current_node && current_node != given_node )
    {
        // Is this node bigger than the given node?
        if ( strcmp( current_node->item.getName(), given_node->item.getName() ) < 0 )
        {
            // Is this node smaller than the smallest node we know of?
            if ( least_found_node == NULL ||
               ((strcmp( current_node->item.getName(), least_found_node->item.getName() ) > 0) )
            {
                // We found a better node.
                least_found_node = current_node;
            }
        }

        current_node = current_node->nextByName;
    }

    return least_found_node;
}

现在改变你的显示功能，像这样使用它:

Now change your display function to use it like this:

void list::displayByName(ostream& out) const
{
    // Find first node initially.
    node * current_node = sort( NULL );

    while ( current_node != NULL )
    {
        // Print node.
        out << current_node->item.getName();

        // Find next node in sorted output.
        current_node = sort( current_node );
    }
}

这部分不断调用sort，直到sort返回NULL.对 sort 的第一次调用是使用 NULL 来找到最低的项目(即排序列表中的第一个).如果没有大于 current_node 的节点，sort 返回 NULL，从而终止循环.

This part keeps calling sort until sort returns NULL. The first call to sort is with NULL so the lowest item is found (that is, the first in the sorted list). sort returns NULL if there are no more nodes larger than current_node, thus terminating the loop.

相关文章