C语言中的链表排序问题

C语言中的链表排序问题

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追问我

楼上已经解释的很明白了，我就不解释了，下面是选择排序的另一个程序，可以参考学习。 #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; }

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); }

同学，给你一段代码，里面涵盖了链表的冒泡排序！ #include #include typedef struct node { int data; struct node *next; }lnode,*linklist; linklist creat(void) { 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->data>q->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; } 希望对你有帮助，如果有问题可以继续找我！