C ++泡泡分类双重链接列表 [英] C++ Bubble sorting a Doubly Linked List

问题描述

我知道气泡排序可能不是最快的方式做到这一点，但它可以接受。

我的双链表有一个类型int和一个类型字符串来保存一个数字和一个数字。字。

我的麻烦点是怎样的运行这个循环，以便它被彻底正确排序，而不只是一次。

这里是我到目前为止所做的：

  void DblLinkedList :: ReorderListNumeric（）
 {
 dummy = new Node（）; 
 temphead = head; 
 temp = head-> next; 
 
 while（tempTwo-> next！= NULL）
 {
 if（temp-> wordCount< tempTwo-> wordCount）
 {
 dummy-> word = tempTwo-> word; 
 dummy-> wordCount = tempTwo-> wordCount; 
 
 tempTwo-> word = temp-> word; 
 tempTwo-> wordCount = temp-> wordCount; 
 
 temp-> word = dummy-> word; 
 temp-> wordCount = dummy-> wordCount; 
} 
 temp = tempTwo; 
 tempTwo = tempTwo-> next; 
} 
} 
  

解决方案

我的麻烦是如何运行这个循环，以便它被正确排序，而不只是一次。

如果你已经有一个循环，将成功做一个通行证和交换是好的，通常的方式做多个通行证相对有效率是：

  set swapped = true 
当交换时：
 set swapped = false 
执行你的一遍，设置在交换
时交换为true 
  

这避免了初级n ² 解决方案，初学者将始终开始。

这真的。

您设置交换到 true ，以便初始输入列表，然后立即在循环中将其设置为 false 。 >

只有当交换发生时，您的单程将设置交换。

如果任何交换发生，

code> swapped 标志设置，您将需要运行另一个pass。这是因为交换可能在列表的结尾，并使先前的订单无效，例如：

 初始：1 2 3 4 6 7 5 
 Pass1：1 2 3 4 6 5< => 7（swap）
 Pass2：1 2 3 4 5< = 6 7（swap）
 Pass3：1 2 3 4 5 6 7（没有交换，所以退出循环）
  

代码是正确的，开头是类似：

  void DblLinkedList :: ReorderListNumeric（）{
 Node * ptr， dummy = new Node（）; 
 
 //零个或一个元素，不需要排序。 
 
 if（head == NULL）return; 
 if（head-> next == NULL）return; 
 
 //强制初始条目。 
 
 int swapped = 1; 
 while（swapped）{
 //标记为最后一次，然后一次通过。 
 
 swapped = 0; 
 
 ptr = head; 
 while（ptr-> next！= NULL）{
 if（ptr-> wordCount< ptr-> next-> wordCount）{
 //交换，通过。 
 
 swapped = 1; 
 
 dummy-> word = ptr-> word; 
 ptr-> word = ptr-> next-> word; 
 ptr-> next-> word = dummy-> word; 
 
 dummy-> wordCount = ptr-> wordCount; 
 ptr-> wordCount = ptr-> next-> wordCount; 
 ptr-> next-> wordCount = dummy-> wordCount; 
} 
 ptr = ptr-> next; 
} 
} 
} 
  

I know bubble sort is probably not the fastest way to do this but its acceptable. i'm just having trouble with adjusting the algorithm to double link lists from arrays.

My double linked lists have a type int and a type string to hold a number and a word. My list was sorted with an insertion sort that I wrote to sort alphabetically, now I need to reorder my double linked list numerically, greatest to least.

My trouble spot is how to run this loop so that it is properly sorted thoroughly and not just one time.

here's what i've managed to get down so far:

void DblLinkedList::ReorderListNumeric()
{
dummy = new Node();
temphead = head;
temp = head->next;

while(tempTwo->next != NULL)
{
    if(temp->wordCount < tempTwo->wordCount)
    {               
        dummy->word = tempTwo->word;
        dummy->wordCount = tempTwo->wordCount;

        tempTwo->word = temp->word;
        tempTwo->wordCount = temp->wordCount;

        temp->word = dummy->word;
        temp->wordCount = dummy->wordCount;
    }
    temp = tempTwo;
    tempTwo = tempTwo->next;
}
}

解决方案

My trouble spot is how to run this loop so that it is properly sorted thoroughly and not just one time.

If you already have a loop that will successfully do one pass and swap is okay, the usual way to do multiple passes relatively efficiently is:

set swapped = true
while swapped:
    set swapped = false
    do your one pass, setting swapped to true whenever you swap

This avoids the naive n² solution that beginners will invariably start with.

And that's it really.

You set swapped to true so that you initially enter the list then set it to false immediately, inside the loop.

Your single pass will set swapped only if a swap takes place. If no swap takes place in your pass, then the list is sorted and you exit the loop.

If any swap takes place, the swapped flag is set and you will need to run another pass. This is because the swap could be at the end of the list and invalidate the order earlier on, such as:

Initial: 1   2   3   4   6   7   5
  Pass1: 1   2   3   4   6   5<=>7 (swap)
  Pass2: 1   2   3   4   5<=>6   7 (swap)
  Pass3: 1   2   3   4   5   6   7 (no swap, so exit loop)

So, assuming your code is correct, start with something like:

void DblLinkedList::ReorderListNumeric() {
    Node *ptr, *dummy = new Node();

    // Zero or one element, no sort required.

    if (head == NULL) return;
    if (head->next == NULL) return;

    // Force initial entry.

    int swapped = 1;
    while (swapped) {
        // Flag as last time, then do one pass.

        swapped = 0;

        ptr = head;
        while (ptr->next != NULL) {
            if (ptr->wordCount < ptr->next->wordCount) {
                // Swapping, need another pass.

                swapped = 1;

                dummy->word = ptr->word;
                ptr->word = ptr->next->word;
                ptr->next->word = dummy->word;

                dummy->wordCount = ptr->wordCount;
                ptr->wordCount = ptr->next->wordCount;
                ptr->next->wordCount = dummy->wordCount;
            }
            ptr = ptr->next;
        }
    }
}

这篇关于C ++泡泡分类双重链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！