首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

怎么通过更改指针的指向来实现单向链表排序,而不是交换数据

2012-09-02 
如何通过更改指针的指向来实现单向链表排序,而不是交换数据希望能写个简单易懂的方法(按从小到大)比如下面

如何通过更改指针的指向来实现单向链表排序,而不是交换数据
希望能写个简单易懂的方法(按从小到大)
比如下面这样的结构吧
typedef struct
{
 int data;
struct *next;
}student;
有一个头指针head,指向一个未排好充的链表,请帮忙写一下排序方法

[解决办法]
单链表排序呢:

①,简单的就是冒泡排序,很轻松愉快的 。 

过程就是冒泡,需要操作:
1,修改前驱的后继
2,互换当前结点与下一个结点。

需要的变量:pre,cur,next

②,就是快速排序,很快很easy。

过程主要就是Partition函数了,Partition的复杂度是O(n)的,即便这是一个链表。

这个Partition函数需要参考《算法导论》里那种写法,自己去学习。

由于是链表,Partition过程中原本的交换过程变成了插入过程,自己学习之后思考。

热点排行