双重链接列表Bubblesort，反向方法现在打破

因此，我最近更新了我的Bubblesort（按字母顺序排序）以使用链接列表。双重链接列表Bubblesort，反向方法现在打破

虽然现在我以前的工作反向方法打破了名单。（以前工作，如果我没有先做单列表冒泡排序）

冒泡排序和交换。

void bubbleSort() { 
    City *temp = NULL; 
    City *current = head; 
    while (current != NULL) { //for the rest in list 
     if (current->getName().compare(current->next->getName()) > 0) { //compare distance 
      if (current == head) { 
       head = current->next; 
      } 
      swap(current, current->next); 
     } 
     current = current->next; 
    } 
}

交换

void swap(City* i, City* j) { 
    if (i->previous) i->previous->next = j; 
    if (j->previous) j->previous->next = i; 
    if (i->next) i->next->previous = j; 
    if (j->next) j->next->previous = i; 
    City* temp; 
    temp = i->previous; 
    i->previous = j->previous; 
    j->previous = temp; 
    temp = i->next; 
    i->next = j->next; 
    j->next = temp; 
}

这是打破现在反向列表。

void reverseList() { 
    City *temp = NULL; 
    City *current = head; 

    while (current != NULL) { 
     temp = current->previous; 
     current->previous = current->next; 
     current->next = temp; 
     current = current->previous; 

    } 
    if (temp != NULL) { 
     head = temp->previous; 
    } 
}

问题我有什么遗漏了我的冒泡排序，打破名单？

来源

2014-11-24 jackdh

为什么不交换数据并保留指针？ – PaulMcKenzie 2014-11-24 15:47:24

因为City有大量的数据，回想一下，如果我将它们包装在NODE中，它会起作用，尽管这不是一种选择，除非我根本无法完成这项工作。 – jackdh 2014-11-24 15:48:27

什么是“大量数据”？所有你需要做的就是重写'swap'来交换数据，并且这样做你可以利用'std :: swap'而不是用'temp'变量写所有的代码。另外，冒泡排序是一个'O（n^2）'循环，但我只看到一个while循环。它应该是两个循环，一个嵌套在另一个循环中。 – PaulMcKenzie 2014-11-24 15:52:16

一个错误是您的气泡排序实现。它应该对数据进行多次传递，因为冒泡排序具有O(n*n)的复杂性，其中n是要排序的项目的数量。

换句话说，您需要执行while循环bubbleSort，直到您检测到数据已排序。这可以通过使用仅在发生swap时设置的布尔标志来完成，然后测试该标志或仅使n通过数据。

来源

2014-11-24 16:15:43 PaulMcKenzie

双重链接列表Bubblesort，反向方法现在打破

回答

相关问题