c语言链表插入排序函数,链表选择排序c语言

对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，

(1) L-next=NULL

创新互联公司2013年开创至今，是专业互联网技术服务公司，拥有项目做网站、成都网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元白银区做网站,已为上家服务,为白银区各地企业和个人服务,联系电话:028-86922220

(2) p (或p!=NULL)

(3) q (或q!=NULL)

(4) p-next=r-next

(5) r-next=p // (4) 和 (5)是将p结点插入到 r 结点和q 结点之间

C语言链表插入排序问题

//修改如下

#include stdio.h

#include stdlib.h

typedef struct node

{

int xh;

char sname[8];

int sx;

int yw;

int zf;

int mc;

struct node *next;

}linklist;

void main()

{

linklist *head;

linklist *s=NULL; //创建 链表时所用的指针。。

linklist *p=NULL;// 输出 链表时所用的指针。。

linklist *q=NULL;

linklist *g=NULL;

char ch;

head = NULL;//开始时 链表的头为空；

printf(" 输入 y 进入循环\n");

scanf("%c",ch);

while(ch =='y'||ch=='Y')

{

s=(linklist*)malloc(sizeof(linklist));//给链表建立个空间

printf("输入学号");

scanf("%d",s-xh);

printf("输入姓名");

scanf("%s",s-sname);

printf("输入数学成绩");

scanf("%d",s-sx);

printf("输入语文成绩");

scanf("%d",s-yw);

s-zf=s-sx+s-yw;

s-next = NULL;

if(head == NULL||head-zfs-zf)

{

s-next=head;

head=s;

}

else

{

p=head;

q=p-next;

while(q!=NULLs-zf = q-zf)

{

p=q;

q=q-next;

}

s-next=q;

p-next=s;

}

getchar();//修改

printf(" 继续输入按y\n");//修改

scanf("%c",ch);

}

//输出链表

g=head;

while(g!=NULL)

{

printf("%4d",g-xh);

printf("%4s",g-sname);

printf("%4d",g-sx);

printf("%4d",g-yw);

printf("%4d",g-zf);

printf("\n ");

g=g-next;//修改

}

}

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就是最常用的状态码），主调函数可以通过返回值判断被调函数的执行情况。

对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处。

这个算法有两个循环，我们姑且称其为外循环和内循环，诚如其他楼的一位网友所言，其内循环在第一次判断时进不去是正常的，但后面会进去。为什么呢？首先我们来理一下这个算法的大体思路：这是一个针对单链表的排序算法，就是说给定一个单链表，我们要把按照结点（这里不对头结点进行排序，即这里讨论的结点不包括头结点）的数据域中的data值的大小从小到大进行排序，得到新的排序后的有序链表。我们先把链表的头结点之后的部分链表拆下来，即p=L-next，L-next=NULL，这样我们就拆分原来的链表变成了现在的两个链表（我们称只有一个头结点的链表为L1，另一个全为数据项结点的链表为L2）。接下来我们一个一个从L2剥下单独的结点，放到L1中，其中如果L1中已经有数据项结点，则要先进行data项比较再找到合适的地方插入。直到最后L2中的结点全部拆下来并装到了L1上，于是排序完毕，此时的L1拥有与原来的单链表相同的头结点，但是排列有序的数据项结点。

理完了整个算法的思路后再回去看代码就很明显，外循环判断“p!=NULL”的意义在于判断L2链表中是否还有没有剥完的结点，而内循环中要先判断“q!=NULL”的第一层意义在于判断L1链表是不是一个只有头结点的空表（即无数据项结点），如果是，则直接插入，如果不是，则判断目前L1头结点的下一个结点q的data值是否小于等于刚从L2剥下来的结点p的data值，如果是，则说明这个p结点应该安放的位置还在q结点之后，我们还要继续往下找，直到找到q-data p-data的结点q或者已经到了链表的末尾（这也是q!=NULL的第二层意义），则停止寻找，并将p结点就放在这个位置。

说了半天忘了回答楼主的疑问，为什么内循环永远不会进去吗？不是，只是第一次不会进去（当然，如果原单链表本身就是一个只有头结点的链表时那么后面也不会再进去了，因为空表根本不需要排序），而后面就会进去，具体原因见我上述分析即可知。

C语言 单向链表如何排序？

void link_order(STU *p_head)

{

STU *pb, *pf, temp;

pf = p_head;

if(p_head == NULL) {//链表为空

printf("needn't order.\n");

return ;

}

if(p_head-next == NULL) {//链表有1个节点

printf("only one print, needn't order.\n");

return ;

}

while(pf-next != NULL) {//以pf指向的节点为基准节点

pb = pf-next;//pb从基准点的下一个节点开始

while(pb != NULL) {

if(pf-num pb-num) {

temp = *pf;

*pf = *pb;

*pb = temp;

temp.next = pf-next;

pf-next = pb-next;

pb-next = temp.next;

}

pb = pb-next;

}

pf = pf-next;

}

return ;

}

扩展资料：

链表的排序有三种情况：

1、链表为空时：不用排序；

2、链表中有一个节点：不用排序；

3、链表中两个及其以上节点时：排序。

return 0代表程序正常退出。return是C++预定义的语句，它提供了终止函数执行的一种方式。当return语句提供了一个值时，这个值就成为函数的返回值。

return语句用来结束循环，或返回一个函数的值。

1、return 0，说明程序正常退出，返回到主程序继续往下执行。

2、return 1，说明程序异常退出，返回主调函数来处理，继续往下执行。return 0或return 1对程序执行的顺序没有影响，只是大家习惯于使用return(0)退出子程序而已。

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循环，就是找到了插入的位置*/

/*注意：按道理来说，这句话可以放到下面注释了的那个位置也应该对的，但是就是不能。原因：你若理解了上面的第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博客，转载请标明出处：