这是我用冒泡排序排序链表的程序。当我使用while时,它是OK的,但是当我使用for循环时,它有一个无限循环,所以我的程序意外停止。另一方面,对于第一个元素和第二个元素的第一次交换,我将指针的头指向第二个元素,但这可能不适用于整个程序。
例如,例1:输入:3,2,4,1,5输出:2、3、4、5
Ex2:输入:4、3、2、1,5输出:3、4、5
要是输入:3、2、1输出:2、3
我认为它只是改变了头指针第一次指向的地址,所以头在Ex1中指向2,在Ex2中指向3,在Ex3中指向2。
void Swap(Node *p1, Node *p2)
{
Node *t;
t=p2->next;
p2->next=p1;
p1->next=t;
}
Node *BubbleSort(Node *head,int n) //pass the address of the first element in linked list and the linked list size
{
Node *tmp=head;
int swap=1;
for(int i=0;i<n-1;i++)
{
tmp=a; swap=0;
for(int j=0;j<n-1;j++)
{
if((tmp->data)>(tmp->next->data))
{
if(j==0) //if this is the first and second element I will change the address of the pointer
a=tmp->next;
Swap(tmp,tmp->next);
swap=1;
}
else tmp=tmp->next; //If the element I focus on is not greater than its folowing I will move the tmp pointer to the next.
}
if(swap==0)
return head;
}
return head;
}
int main()
{
Node*head;
//Assume I have a linked list with n elements
head=BubbleSort(head,n);
}
我在GeekforGeek中搜索了另一种方法,但我仍然想知道为什么我的代码不起作用。我想了几乎一整天。请帮帮我!
Swap
关闭1。因此,在最内层的循环体中,您需要Swap(tmp->prev, tmp)
而不是Swap(tmp, tmp->next)
。
你需要比较和交换相同的元素,不是比较当前和下一个元素,而是交换下一个和第二个元素。if( (tmp->data) > (tmp->next->data) )
,那么tmp->prev->next
应该指向tmp->next
,tmp->next->next
应该指向tmp
。但是,有一件事需要注意:当您创建Swap(tmp->prev, tmp)
时,还需要进一步启动一个元素。从头部指向第一个元素但不包含任何数据的事实也可以清楚地看出这一点。first->prev
应该指向头部,头部应该是rw。
可以让顶层代码维护头,但最好所有代码都维护自己的头。