求助链表的排序方法
试过用单链表不行,用双链表好像也不行, 除非是head->下一个->再下一个"下一个" "再下一个"可以做到交换以外,远离head的数据就好像办不到,
请问根据数据由大到小进行排序应该怎么实现呢? 好多种办法...
最简单的,拿个TempData值保存HeadData,从头到尾遍历,把TempDate和目标指针的data比较,把大的data赋值给TempData并删除指针指向的结点,这样一次下来,TempData必然是最大的,把他放在链表头,这样的话,前面的数字区就是有序区间,之后永不检查,仅仅进行添加..
然后对2...i的区间进行上述遍历,直到*Temp = *Tail.即所有区间都是有序区间,就完成了. 不是听得很懂,我用的是泡沫排序法,这样也可以实现吗? void sore()
{
struct node *p1,*p2,*change;
int i,j;
p1=head;
for(i=1;i<count;i++)
{
p1=head;
for(j=0;j<count-i;j++) //这里用的是冒泡排序
{
p2=p1->next;
if(p1->ave<p2->ave)
{
if(p1==head)
{
p1->next=p2->next;
p1->left=p2;
p2->next=p1;
head=p2;
}
else //当P1不是由head指向时使指针change由头指针出发
{ //当change->next==p1就不再指向下一地址
change=head; //即change 在p1的前一个地址
while(change->next!=p1)
change=change->next;
p1->next=p2->next;
p2->next->left=p1;
p1->left=p2;
p2->next=p1;
change->next=p2;
p2->left=change;
}
}
p1=p1->next;
}
}
}
为什么这样也不能实现排序呢? 先估计一下算法,单链表的话只能够对单方向操作比较合适,即必须先确定比较的符号,假定LZ的需要从大到小排列,就是说,一个任意的链表必须是从头向尾部进行冒泡,举个例子
3 4 1 5 2的列表那么就是利用 "当前数字一旦小于后面的数字那么就把这个数字断开并且插入到后面一个的next域"+"如果大于下一个值,直接把指针指向下一个结点,对更小的值进行移动", 实现上自然需要两个指针(一个是curr,另外一个就是curr->next)操作,至于起始和结束条件,冒泡的方法条件有点忘了……最笨的方法: 每次从最尾部向前进行移动,直到curr运行到终点,然后重新再一次,直到任何一次运行中没有数据交换为止:
3 4 1 5 2 -> 4 3 1 5 2 -> 4 3 5 1 2 -> 4 3 5 2 1 (changed)
4 3 5 1 2 -> 4 3 5 1 2 -> 4 5 3 1 2 -> 4 5 3 2 1 (changed)
4 5 3 2 1 -> 5 4 3 2 1 -> 5 4 3 2 1 -> 5 4 3 2 1 (changed)
5 4 3 2 1 -> 5 4 3 2 1 -> 5 4 3 2 1 -> 5 4 3 2 1 (end)
以上纯纸上谈兵……没有实验 ||| 兴许有一定的复杂性,但是100%是可以实现的……
页:
[1]