正文
c语言单向链表排序函数 c语言单向链表实现快速排序
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
C语言的链表怎么排序
==========================
功能：选择排序(由小到大)
返回：指向链表表头的指针
==========================
*/
/*
选择排序的基本思想就是反复从还未排好序的那些节点中c语言单向链表排序函数，
选出键值（就是用它排序的字段c语言单向链表排序函数，我们取学号num为键值）最小的节点，
依次重新组合成一个链表。
我认为写链表这类程序，关键是理解：
head存储的是第一个节点的地址，head-next存储的是第二个节点的地址；
任意一个节点p的地址，只能通过它前一个节点的next来求得。
单向链表的选择排序图示：
----[1]----[3]----[2]...----[n]----[NULL]（原链表）
head 1-next 3-next 2-next n-next
----[NULL]（空链表）
first
tail
----[1]----[2]----[3]...----[n]----[NULL]（排序后链表）
first 1-next 2-next 3-next tail-next
图10：有N个节点的链表选择排序
1、先在原链表中找最小的，找到一个后就把它放到另一个空的链表中；
2、空链表中安放第一个进来的节点，产生一个有序链表,并且让它在原链表中分离出来（此时要注意原链表中出来的是第一个节点还是中间其它节点）；
3、继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针；
*/
struct student *SelectSort(struct student *head)
{
struct student *first; /*排列后有序链的表头指针*/
struct student *tail; /*排列后有序链的表尾指针*/
struct student *p_min; /*保留键值更小的节点的前驱节点的指针*/
struct student *min; /*存储最小节点*/
struct student *p; /*当前比较的节点*/
first = NULL;
while (head != NULL) /*在链表中找键值最小的节点。*/
{
/*注意：这里for语句就是体现选择排序思想的地方*/
for (p=head,min=head; p-next!=NULL; p=p-next) /*循环遍历链表中的节点，找出此时最小的节点。*/
{
if (p-next-num min-num) /*找到一个比当前min小的节点。*/
{
p_min = p; /*保存找到节点的前驱节点：显然p-next的前驱节点是p。*/
min = p-next; /*保存键值更小的节点。*/
}
}
/*上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表。*/
/*第一件事*/
if (first == NULL) /*如果有序链表目前还是一个空链表*/
{
first = min; /*第一次找到键值最小的节点。*/
tail = min; /*注意：尾指针让它指向最后的一个节点。*/
}
else /*有序链表中已经有节点*/
{
tail-next = min; /*把刚找到的最小节点放到最后，即让尾指针的next指向它。*/
tail = min; /*尾指针也要指向它。*/
}
/*第二件事*/
if (min == head) /*如果找到的最小节点就是第一个节点*/
{
head = head-next; /*显然让head指向原head-next,即第二个节点，就OK*/
}
else /*如果不是第一个节点*/
{
p_min-next = min-next; /*前次最小节点的next指向当前min的next,这样就让min离开了原链表。*/
}
}
if (first != NULL) /*循环结束得到有序链表first*/
{
tail-next = NULL; /*单向链表的最后一个节点的next应该指向NULL*/
}
head = first;
return head;
}
/*
==========================
功能：直接插入排序(由小到大)
返回：指向链表表头的指针
==========================
*/
/*
直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值
（就是用它排序的字段，我们取学号num为键值）排好序的，对于节点n在
这个序列中找插入位置，使得n插入后新序列仍然有序。按照这种思想，依次
对链表从头到尾执行一遍，就可以使无序链表变为有序链表。
单向链表的直接插入排序图示：
----[1]----[3]----[2]...----[n]----[NULL]（原链表）
head 1-next 3-next 2-next n-next
----[1]----[NULL]（从原链表中取第1个节点作为只有一个节点的有序链表）
head
图11
----[3]----[2]...----[n]----[NULL]（原链表剩下用于直接插入排序的节点）
first 3-next 2-next n-next
图12
----[1]----[2]----[3]...----[n]----[NULL]（排序后链表）
head 1-next 2-next 3-next n-next
图13：有N个节点的链表直接插入排序
1、先在原链表中以第一个节点为一个有序链表，其余节点为待定节点。
2、从图12链表中取节点，到图11链表中定位插入。
3、上面图示虽说画了两条链表，其实只有一条链表。在排序中，实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。
这一点请读者务必搞清楚，要不然就可能认为它和上面的选择排序法一样了。
*/
struct student *InsertSort(struct student *head)
{
struct student *first; /*为原链表剩下用于直接插入排序的节点头指针*/
struct student *t; /*临时指针变量：插入节点*/
struct student *p; /*临时指针变量*/
struct student *q; /*临时指针变量*/
first = head-next; /*原链表剩下用于直接插入排序的节点链表：可根据图12来理解。*/
head-next = NULL; /*只含有一个节点的链表的有序链表：可根据图11来理解。*/
while (first != NULL) /*遍历剩下无序的链表*/
{
/*注意：这里for语句就是体现直接插入排序思想的地方*/
for (t=first, q=head; ((q!=NULL) (q-num t-num)); p=q, q=q-next); /*无序节点在有序链表中找插入的位置*/
/*退出for循环，就是找到了插入的位置*/
/*注意：按道理来说，这句话可以放到下面注释了的那个位置也应该对的，但是就是不能。原因：c语言单向链表排序函数你若理解了上面的第3条，就知道了。*/
first = first-next; /*无序链表中的节点离开，以便它插入到有序链表中。*/
if (q == head) /*插在第一个节点之前*/
{
head = t;
}
else /*p是q的前驱*/
{
p-next = t;
}
t-next = q; /*完成插入动作*/
/*first = first-next;*/
}
return head;
}
/*
==========================
功能：冒泡排序(由小到大)
返回：指向链表表头的指针
==========================
*/
/*
冒泡排序的基本思想就是对当前还未排好序的范围内的全部节点，
自上而下对相邻的两个节点依次进行比较和调整，让键值（就是用它排
序的字段，我们取学号num为键值）较大的节点往下沉，键值较小的往
上冒。即：每当两相邻的节点比较后发现它们的排序与排序要求相反时，
就将它们互换。
单向链表的冒泡排序图示：
----[1]----[3]----[2]...----[n]----[NULL]（原链表）
head 1-next 3-next 2-next n-next
----[1]----[2]----[3]...----[n]----[NULL]（排序后链表）
head 1-next 2-next 3-next n-next
图14：有N个节点的链表冒泡排序
任意两个相邻节点p、q位置互换图示:
假设p1-next指向p，那么显然p1-next-next就指向q,
p1-next-next-next就指向q的后继节点，我们用p2保存
p1-next-next指针。即：p2=p1-next-next，则有：
[ ]----[p]----------[q]----[ ]（排序前）
p1-next p1-next-next p2-next
图15
[ ]----[q]----------[p]----[ ]（排序后）
图16
1、排序后q节点指向p节点，在调整指向之前，我们要保存原p的指向节点地址，即：p2=p1-next-next；
2、顺着这一步一步往下推,排序后图16中p1-next-next要指的是p2-next,所以p1-next-next=p2-next;
3、在图15中p2-next原是q发出来的指向，排序后图16中q的指向要变为指向p的，而原来p1-next是指向p的，所以p2-next=p1-next;
4、在图15中p1-next原是指向p的，排序后图16中p1-next要指向q,原来p1-next-next（即p2)是指向q的，所以p1-next=p2;
5、至此，我们完成了相邻两节点的顺序交换。
6、下面的程序描述改进了一点就是记录了每次最后一次节点下沉的位置，这样我们不必每次都从头到尾的扫描，只需要扫描到记录点为止。
因为后面的都已经是排好序的了。
*/
struct student *BubbleSort(struct student *head)
{
struct student *endpt; /*控制循环比较*/
struct student *p; /*临时指针变量*/
struct student *p1;
struct student *p2;
p1 = (struct student *)malloc(LEN);
p1-next = head; /*注意理解：我们增加一个节点，放在第一个节点的前面，主要是为了便于比较。因为第一个节点没有前驱，我们不能交换地址。*/
head = p1; /*让head指向p1节点，排序完成后，我们再把p1节点释放掉*/
for (endpt=NULL; endpt!=head; endpt=p) /*结合第6点理解*/
{
for (p=p1=head; p1-next-next!=endpt; p1=p1-next)
{
if (p1-next-num p1-next-next-num) /*如果前面的节点键值比后面节点的键值大，则交换*/
{
p2 = p1-next-next; /*结合第1点理解*/
p1-next-next = p2-next; /*结合第2点理解*/
p2-next = p1-next; /*结合第3点理解*/
p1-next = p2; /*结合第4点理解*/
p = p1-next-next; /*结合第6点理解*/
}
}
}
p1 = head; /*把p1的信息去掉*/
head = head-next; /*让head指向排序后的第一个节点*/
free(p1); /*释放p1*/
p1 = NULL; /*p1置为NULL，保证不产生“野指针”，即地址不确定的指针变量*/
return head;
}
/*
==========================
功能：插入有序链表的某个节点的后面(从小到大)
返回：指向链表表头的指针
==========================
*/
/*
有序链表插入节点示意图：
----[NULL]（空有序链表）
head
图18：空有序链表（空有序链表好解决，直接让head指向它就是了。）
以下讨论不为空的有序链表。
----[1]----[2]----[3]...----[n]----[NULL]（有序链表）
head 1-next 2-next 3-next n-next
图18：有N个节点的有序链表
插入node节点的位置有两种情况：一是第一个节点前，二是其它节点前或后。
----[node]----[1]----[2]----[3]...----[n]----[NULL]
head node-next 1-next 2-next 3-next n-next
图19：node节点插在第一个节点前
----[1]----[2]----[3]...----[node]...----[n]----[NULL]
head 1-next 2-next 3-next node-next n-next
图20：node节点插在其它节点后
*/
struct student *SortInsert(struct student *head, struct student *node)
{
struct student *p; /*p保存当前需要检查的节点的地址*/
struct student *t; /*临时指针变量*/
if (head == NULL) /*处理空的有序链表*/
{
head = node;
node-next = NULL;
n += 1; /*插入完毕，节点总数加1*/
return head;
}
p = head; /*有序链表不为空*/
while (p-num node-num p != NULL) /*p指向的节点的学号比插入节点的学号小，并且它不等于NULL*/
{
t = p; /*保存当前节点的前驱，以便后面判断后处理*/
p = p-next; /*后移一个节点*/
}
if (p == head) /*刚好插入第一个节点之前*/
{
node-next = p;
head = node;
}
else /*插入其它节点之后*/
{
t-next = node; /*把node节点加进去*/
node-next = p;
}
n += 1; /*插入完毕，节点总数加1*/
return head;
}
/*
测试代码如下：
*/
/*测试SelectSort():请编译时去掉注释块*/
/*
head = SelectSort(head);
Print(head);
*/
/*测试InsertSort():请编译时去掉注释块*/
/*
head = InsertSort(head);
Print(head);
*/
/*测试BubbleSort():请编译时去掉注释块*/
/*
head = BubbleSort(head);
Print(head);
*/
/*测试SortInsert():上面创建链表，输入节点时请注意学号num从小到大的顺序。请编译时去掉注释块*/
/*
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%ld,%f",stu-num,stu-score);
head = SortInsert(head,stu);
free(stu);
stu = NULL;
Print(head);
*/
本文来自CSDN博客，转载请标明出处：
相关问答
Q1: C语言如何对链表的数进行排序？
同学c语言单向链表排序函数，给c语言单向链表排序函数你一段代码，里面涵盖c语言单向链表排序函数了链表c语言单向链表排序函数的冒泡排序！
#includestdio.h
#includemalloc.h
typedef struct node
{
int data;/*data代表成绩分数*/
struct node *next;
}LNode,*LinkList;
LinkList Creat(void)/*创建链表，结束标志为当输入的数据为0!*/
{
LinkList H,p1,p2;
int n;
n=0;
p1=p2=(LinkList)malloc(sizeof(LNode));
printf("输入数据：");
scanf("%d",p1-data);
H=NULL;
while(p1-data!=0)
{
n=n+1;
if(n==1)
H=p1;
else
p2-next=p1;
p2=p1;
p1=(LinkList)malloc(sizeof(LNode));
scanf("%d",p1-data);
}
p2-next=NULL;
return(H);
}
LinkList Sort(LinkList SL)/*递增排序函数：入口参数：链表的头指针，此为链表中的排序函数*/
{
LinkList p,q;
int temp;
for(p=SL;p!=NULL;p=p-next)
{
for(q=p-next;q!=NULL;q=q-next)
{
if(p-dataq-data)
{
temp=q-data;
q-data=p-data;
p-data=temp;
}
}
}
return SL;
}
int main()
{
LinkList L,S,K;
L=Creat();
printf("初始化的单链表数据序列为:\n");
for(S=L;S!=NULL;S=S-next)
printf("%d ",S-data);
Sort(L);
printf("\n按递增顺序排序后的序列为:\n");
for(K=L;K!=NULL;K=K-next)
printf("%d==",K-data);
return 0;
}
Q2: C语言做链表的排序
＃include＂stdafx．h＂
＃include＜stdlib．h＞
／／创建一个节点，data为value，指向NULL
Node＊Create（intvalue）｛
Node＊head＝（Node＊）malloc（sizeof（Node））；
head－＞data＝value；
head－＞next＝NULL；
returnhead；
｝
／／销毁链表
boolDestroy＿List（Node＊head）｛
Node＊temp；
while（head）｛
temp＝head－＞next；
free（head）；
head＝temp；
｝
head＝NULL；
returntrue；
｝
／／表后添加一个节点，Create（value）
boolAppend（Node＊head，intvalue）｛
Node＊n＝Create（value）；
Node＊temp＝head；
while（temp－＞next）｛
temp＝temp－＞next；
｝
temp－＞next＝n；
return0；
｝
／／打印链表
voidPrint＿List（Node＊head）｛
Node＊temp＝head－＞next；
while（temp）｛
printf（＂％d－＞＂，temp－＞data）；
temp＝temp－＞next；
｝
printf（＂＼n＂）；
｝
／／在链表的第locate个节点后（头节点为0）插入创建的节点Create（value）
boolInsert＿List（Node＊head，intlocate，intvalue）｛
Node＊temp＝head；
Node＊p；
Node＊n＝Create（value）；
if（locate＜0）
returnfalse；
while（locate－－）｛
if（temp－＞next＝＝NULL）｛
temp－＞next＝Create（value）；
returntrue；
｝
temp＝temp－＞next；
｝
p＝temp－＞next；
temp－＞next＝n；
n－＞next＝p；
returntrue；
｝
／／删除第locate个节点后（头节点为0）的节点
boolDelete＿List（Node＊head，intlocate）｛
Node＊temp＝head；
Node＊p；
if（locate＜0）
returnfalse；
while（locate－－）｛
if（temp＝＝NULL）｛
returnfalse；
｝
temp＝temp－＞next；
｝
p＝temp－＞next－＞next；
free（temp－＞next）；
temp－＞next＝NULL；
temp－＞next＝p；
returntrue；
｝
／／获取链表长度（不包括头节点）
intSize＿List（Node＊head）｛
Node＊temp＝head；
intsize＝0；
while（temp－＞next）｛
temp＝temp－＞next；
size＋＋；
｝
returnsize；
｝
／／链表的三种排序（选择，插入，冒泡）
boolSort＿List（Node＊head）｛
intt＝0；
intsize＝Size＿List（head）；
／／选择排序
／＊for（Node＊temp＝head－＞next；temp！＝NULL；temp＝temp－＞next）｛
for（Node＊p＝temp；p！＝NULL；p＝p－＞next）｛
if（temp－＞data＞p－＞data）｛
printf（＂换％d和％d＼n＂，temp－＞data，p－＞data）；
t＝temp－＞data；
temp－＞data＝p－＞data；
p－＞data＝t；
｝
｝
｝＊／
／／插入排序
／＊for（Node＊temp＝head－＞next－＞next；temp！＝NULL；temp＝temp－＞next）｛
for（Node＊p＝head；p－＞next！＝NULL；p＝p－＞next）｛
if（p－＞next－＞data＞temp－＞data）
｛
printf（＂换％d和％d＼n＂，temp－＞data，p－＞next－＞data）；
t＝temp－＞data；
temp－＞data＝p－＞next－＞data；
p－＞next－＞data＝t；
｝
｝
｝＊／
／／冒泡排序
for（Node＊temp＝head－＞next；temp－＞next！＝NULL；temp＝temp－＞next）｛
for（Node＊p＝head－＞next；p－＞next！＝NULL；p＝p－＞next）｛
if（p－＞data＞p－＞next－＞data）｛
t＝p－＞data；
p－＞data＝p－＞next－＞data；
p－＞next－＞data＝t；
｝
｝
｝
return0；
｝
扩展资料：
return表示把程序流程从被调函数转向主调函数并把表达式的值带回主调函数，实现函数值的返回，返回时可附带一个返回值，由return后面的参数指定。
return通常是必要的，因为函数调用的时候计算结果通常是通过返回值带出的。如果函数执行不需要返回计算结果，也经常需要返回一个状态码来表示函数执行的顺利与否（-1和0就是最常用的状态码），主调函数可以通过返回值判断被调函数的执行情况。
Q3: C语言单向链表排序如何实现？
struct student* printf_sort(struct student *head)
{
struct student *p1,*p2,*ptemp,*pfinished=NULL;
for(p1=head;p1-next!=pfinished;)//对链表进行从大到小排序（这里用冒泡法）
//p1使之总是指向头结点，pfinished使之总是指向已排序好的最前面的结点
//ptemp作为中介，保存p2的上一个结点
{
for(p2=p1;p2-next!=pfinished;)
{
if(p2-nump2-next-num)//p2的值小于p2-next的值，交换 {
if(p2==p1)//头结点要交换
{
p1=p2-next;
p2-next=p1-next;
p1-next=p2;
ptemp=p1;
}
else
{
ptemp-next=p2-next;
ptemp=p2-next;
p2-next=ptemp-next;
ptemp-next=p2;
}
}
else//不需要交换，则p2、ptemp前进1位
{
ptemp=p2;
p2=p2-next;
}
}
pfinished=p2;
}
}
c语言单向链表排序函数的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于c语言单向链表实现快速排序、c语言单向链表排序函数的信息别忘了在本站进行查找喔。
