我尝试使用冒泡排序来排序一个链表。我使用Curr和trail来遍历链表。curr应该总是比trail领先一步。这是我到目前为止的代码:
void linked_list::sort ()
{
int i,j=0;
int counter=0;
node *curr=head;
node *trail=head;
node *temp=NULL;
while (curr !=NULL)
{
curr=curr->next; //couting the number of items I have in my list.
counter++; //this works fine.
}
curr=head->next; // reseting the curr value for the 2nd position.
for (i=0; i<counter; i++)
{
while (curr != NULL)
{
if (trail->data > curr->data)
{
temp=curr->next; //bubble sort for the pointers.
curr->next=trail;
trail->next=temp;
temp=curr; //reseting trail and curr. curr gets back to be infront.
curr=trail;
trail=temp;
if (j==0) //i'm using j to determine the start of the loop so i won't loose the head pointer.
{
head=trail;
}
}
j++;
trail=curr;
curr=curr->next; //traversing thru the list. nested loop.
}
trail=head;
curr=trail->next;
curr->next=trail->next->next; //traversing thru the list. outer loop.
j=0;
}
}
我错过了什么?
5条答案
按热度按时间a7qyws3x1#
你漏掉了几样东西最重要的是链表不是数组,因此你不能很容易地做某些算法与两者互换.与此请考虑以下几点:
next
可供后藤)。现在来看看下面的不同方法。其中有些东西对于理解整个算法至关重要,但我会在代码之后保存它:
这可能与你预期的完全不同。这个简单的练习的目的是建立我们正在评估数据,但实际上我们正在对指针进行排序。注意,除了
p
,它总是列表的头部,我们没有使用额外的指向节点的指针。相反,我们使用指针到指针来操作隐藏在列表中的指针。为了演示这个算法是如何工作的,我写了一个小的测试应用程序,它生成一个随机的整数列表,然后在这个列表上执行上述操作。我还写了一个简单的打印实用程序,可以从任何节点打印列表到末尾。
我还修改了原来的算法,在每次交换内容后打印:
输出示例
其他样本
请注意,一旦在不断减少的源列表中剩下一个已经排序的片段,我们就完成了。
摘要
我 * 强烈 * 建议使用调试器遍历上述算法,以更好地理解它是如何工作的。事实上,我建议使用大多数算法,但执行指针到指针操作的算法可能有点令人生畏,直到您了解它的功能有多强大。这不是完成此任务的唯一方法,但如果您考虑如何管理链表,这是一种直观的方法。而你实际上所做的只是在可预测的地方改变指针中存储的值。
pvcm50d12#
基本上这是一个修改后的排序。你的想法基本上是正确的。主要是你搞砸了节点指针的交换。这里是一个稍微简单一点的修改后的算法。在外部循环中是一个
for
列表中元素的数量。然后内部循环是将值逐步推到列表的末尾。我们跟踪两个指针trail
和curr
。并对curr
和curr->next
进行了比较。nuypyhwy3#
我想这就是你要找的:
dgiusagp4#
使用数组的冒泡排序可以很容易地修改为使用链表的冒泡排序
1aaf6o9v5#
以下是链表上冒泡排序的Java实现: