欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

单链表的选择排序

程序员文章站 2022-07-02 12:54:45
给定一个无序单链表,实现单链表的选择排序(按升序排序)。 代码注释挺详细,直接上代码! ......

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

代码注释挺详细,直接上代码!

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