读书人

怎么通过更改指针的指向来实现单向链表

发布时间: 2012-09-02 21:00:34 作者: rapoo

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

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

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

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

需要的变量:pre,cur,next

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

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

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

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

读书人网 >C语言

热点推荐