C语言中的链表排序问题

Question

*用选择法排序*/
link sort(link head)
{
link beforep,p,p1,k,beforek,temp;
if(head==NULL)printf("信息系统为空!!!按任意键回到主菜单!\n");
else
{p=head;
while(p->next!=NULL)
{
k=p;
p1=p->next;
while(p1!=NULL)
{
if(k->aver<p1->aver)k=p1;
p1=p1->next;
}
if(k!=p)
{
beforek=head;
while(beforek->next!=k)beforek=beforek->next;
if(p==head)head=k;
else beforep->next=k;
beforek->next=p;
temp=k->next;
k->next=p->next;
p->next=temp;
p=k;
}
beforep=p;
p=p->next;
}
printf("排序成功,按任意键回到主菜单!\n");
}
return(head);
}

这段代码能给我注释下吗？ 说得越明白越好~

Answer 1

link sort(link head) //head为表头结点
{
link beforep,p,p1,k,beforek,temp;
if(head==NULL)printf("信息系统为空!!!按任意键回到主菜单!\n"); //表头节点为空即链表为空
else
{p=head; //指针p指向表头
while(p->next!=NULL) //当链表没有遍历完执行循环体
{
k=p; //指针k指向指针p
p1=p->next; //指针p1指向指针p的下一个节点
while(p1!=NULL) //当指针p1不为空，执行循环体
{
if(k->aver<p1->aver)k=p1; //这里的k->表示k所指向对象的aver成员
p1=p1->next; //当k指向的aver成员小于p1指向的aver成员，k指向p1
} //这个循环结束后，k将指向链表中p之后所有节点的aver成员最小的那个节点，这是插入排序的搜索过程
if(k!=p) //如果aver成员最小的节点不是p所指向的节点
{
beforek=head; //beforek从头结点往后寻找
while(beforek->next!=k)beforek=beforek->next; //循环结束后，beforek指针将指向k指针的前一个节点，因为条件beforek->next==k 才结束循环
if(p==head)head=k; //如果p是头结点，头结点指向k（k是成员aver最小的，排在第一个节点作为头结点）?
else beforep->next=k; //否则beforep->next指向k，（请注意这里的beforep与刚才的beforek不一样）
beforek->next=p; //beforek->next指向指针p
temp=k->next;
k->next=p->next;
p->next=temp; //交换k->next和p->next指针
p=k; //p指向k
} //这个函数体运行结束后，p指针指向链表aver成员最小的那个节点，这也就是插入排序的交换过程
beforep=p; //指针回指
p=p->next; // 遍历下一个节点
}
printf("排序成功,按任意键回到主菜单!\n");
}
return(head); //返回头结点
}

如果还是看不懂，你就留Q追问我追问

看得有点懂了吧，那个排序应该是按最大的在前面吧~其他的倒是没什么问题了

追答

应该是最小的在最前面

Answer 2

link sort(link head)
{
link beforep,p,p1,k,beforek,temp;
if(head==NULL)printf("信息系统为空!!!按任意键回到主菜单!\n");
else
{p=head;
while(p->next!=NULL)
{
k=p;
p1=p->next; // 获取下一个值
// 遍历列表，挑出最大值，放到k中
while(p1!=NULL)
{
if(k->aver<p1->aver)k=p1;
p1=p1->next;
}
// 如果当前值不是最大值，则
if(k!=p)
{
beforek=head;
while(beforek->next!=k)beforek=beforek->next; // 设置beforek为最大值的前一个值
if(p==head)head=k; // 如果p为第一个，则把head设置为最大值
else beforep->next=k; // 否则设置beforep的下一个值为k
beforek->next=p; // 开始交换，把最大值放到最前
temp=k->next;
k->next=p->next;
p->next=temp;
p=k;
}
beforep=p; // 更新循环变量，指向下一个值
p=p->next;
}
printf("排序成功,按任意键回到主菜单!\n");
}
return(head);
}追问

能再详细点吗？我加分了。

追答

给个建议，你可以用debug调试看一遍，就会更明白了。
哪里还有不明白？
整个算法就是：
1. 遍历链表，找出最大值；
2. 把当前最大值依次放到链表的前面【头】；
3. 循环上面两个步骤，直到链表最后。

Answer 3

楼上已经解释的很明白了，我就不解释了，下面是选择排序的另一个程序，可以参考学习。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 16
typedef struct node *link;
struct node { int item; link next; };
link NODE(int item, link next)
{
link t = malloc(sizeof *t);
t->item = item; t->next = next;
return t;
}
void show_list(link head)
{
link t;
for (t=head; t; t=t->next) printf("%3d", t->item);
printf("\n");
}
link selection(link head)
{
link s = NULL;
head = NODE(-1, head);
while (head->next)
{
link t, m = head;
for (t=head->next; t->next; t=t->next)
if (t->next->item > m->next->item) m = t;
t = m->next; m->next = t->next;
t->next = s; s = t;
}
free(head);
return s;
}
int main()
{
int i; link head = NULL;
srand(time(NULL));
for (i=0; i<N; i++) head = NODE(rand()%100, head);
show_list(head);
head = selection(head);
show_list(head);
return 0;
}