单链表的选择排序

给定一个无序单链表，实现单链表的选择排序(按升序排序)。

代码注释挺详细，直接上代码！

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;
    struct node *next;
}; 
void printList(struct node *head){
    struct node *t=head;
    while(t){
        printf("%d ",t->data);
        t=t->next;
    }
}
struct node * selectSort(struct node *head)
/*选择排序 
在原链表中一轮轮地找最大的那个结点，找到之后就把它从原链表中抽出来用头插法加到新的链表中。 
需要注意这个最大的结点是否为头结点 
*/
{
    struct node *head1,*max,*premax,*t,*pret;
    //head1：新链表的头指针；max：原链表中最大的结点；premax：最大结点的前驱结点；t：用于遍历原链表寻找最大结点;pret:t的前驱结点
    head1=NULL;
    while(head)//一遍遍地找原链表中当前最大结点 
    {
        max=head;
        premax=NULL;
        pret=head;
        t=head->next;
        //1、寻找最大结点 
        while(t){
            if(t->data>max->data){
                max=t;
                premax=pret;
            }
            pret=t;
            t=t->next;    
        }
        //2、让这个结点离开原链表
        if(max==head)//如果找到的结点是第一个结点
            head=head->next;//让头指针向后移一位就行
        else
            premax->next=max->next;
        //3、把此结点头插法插入新链表
        max->next=head1;
        head1=max;
    }
    return head1;
}
int main()
{
    struct node *head,*p,*q;
    int i,n,a;
    scanf("%d",&n);
    head=NULL;
    for(i=0;i<n;i++){
        p=(struct node *)malloc(sizeof(struct node));
        scanf("%d",&a);
        p->data=a;
        p->next=NULL;
        if(!head){
            head=p;
        }else{
            q->next=p;
        }
        q=p;
    }
    printList(selectSort(head));
 } 

 

原文链接:https://www.cnblogs.com/littleLittleTiger/p/11524166.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有