单链表排序

 

/**编写一个程序，根据test_data[]数组中给定的整数序列建立一个单链表，
然后对该单链表进行排序(元素数值从大到小排列)，最后显示排序后的结果
**/

/**算法思路
 本程序由两个函数组成，create()函数用于根据数组的元素建立一个单链表；sort()函数对该链表进行排序，其原理是：
 用p指针遍历所有结点，其前是已排序好的结点，其后是待排序的结点，从该链表中找出一个data值最小的结点并删除之，
 将删除结点插入到p所指结点的后面。 采用两重循环完成排序工作，外层while判定是否还有待排序的结点，没有则退出循环，
 排序工作完成，有待排序结点时，则执行循环体一次，进行排序。实现本题功能的程序如下：
**/

#include <stdio.h>
#include <stdlib.h>
typedef struct linknode
{
   int data;
   struct linknode *next;
}node;

node *create(int a[],int n)
{
        node *h,*q;
        for(h=NULL;n;n--)
        {
             q=(node*)malloc(sizeof(node));
             q->data=a[n-1];
             q->next=h;
             h=q;
        }
        return h;
}

void sort(node **h)
{
   node *p,*q,*r,*s,*h1;
   h1=p=(node*)malloc(sizeof(node));
   p->next=*h;
   while(p->next!=NULL)
   {
     q=p->next;
     r=p;
     while(q->next!=NULL)
     {
     if(q->next->data<r->next->data)
         r=q;
     q=q->next;
     }
       if(r!=p)
     {
         s=r->next;
         r->next=s->next;
         s->next=p->next;
         p->next=s;
     }
        p=p->next;
   }
*h1->next;
free(h1);
}

int test_data[]={5,9,3,1,2,7,8,6,4};

main()
{
   node *h,*p;
   h=create(test_data,sizeof(test_data)/sizeof(int));

    printf("排序前：\n");
    for(p=h;p;p=p->next)
      printf("%2d",p->data);
    printf("\n");
    sort(&h);
    printf("排序后：\n");
    for(p=h;p;p=p->next)
         printf("%2d",p->data);
     printf("\n");
     return 0;
}

输出结果：

排序前：

5 9 3 1 2 7 8 6 4

排序后：

5 6 7 8 9