Chinaunix首页 | 论坛 | 博客
  • 博客访问: 821019
  • 博文数量: 97
  • 博客积分: 3042
  • 博客等级: 中校
  • 技术积分: 1610
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-21 11:48
文章存档

2015年(1)

2014年(3)

2013年(4)

2012年(43)

2011年(44)

2010年(2)

分类:

2011-10-15 11:00:02

原文地址:链表的排序<一> 作者:xuemling

链表排序

链表的排序,这和冒泡,交换类的排序不一样

点击(此处)折叠或打开

  1. /****************************************************
  2.  * FileName: sort_list.c
  3.  * Usage: insert to the list_node
  4.  * sort the list
  5.  * **************************************************
  6.  */
  7. #include<stdio.h>
  8. #include<stdlib.h>

  9. struct List
  10. {
  11.     int number;
  12.     struct List *next;
  13. };

  14. typedef struct List Node;
  15. typedef Node *Link;

  16. Link Create_List(Link ead);
  17. Link insert_rank(Link head);
  18. void Print_List(Link head);
  19. void Free_List(Link head);
  20. /*----------------------------------*/
  21. /* main */
  22. /*----------------------------------*/
  23. int main(void)
  24. {
  25.     Link head=NULL;
  26.     head=Create_List(head);
  27.     if(head != NULL) {
  28.         Print_List(head);
  29.         insert_rank(head); /* sort the rank */
  30.         printf("\n======= after ranking the list =======\n");
  31.         Print_List(head);
  32.         Free_List(head);
  33.     }

  34.     return 0;
  35. }

  36. /* Create the list */
  37. Link Create_List(Link head)
  38. {
  39.     Link New=NULL;
  40.     Link Pointer=NULL;
  41.     Link r=NULL;

  42.     head=(Link)malloc(sizeof(Node));
  43.     head->next=NULL;
  44.     r=head;
  45.     if(head == NULL) {
  46.         printf("memory allocate failure!\n");
  47.     }
  48.     New=(Link)malloc(sizeof(Node));
  49.     if(New == NULL){
  50.         printf("memory allocate failure!\n");
  51.     }
  52.     printf("*** Input DataNumber exit for 0 ***\n");
  53.     scanf("%d",&New->number);
  54.     while(New->number != 0){
  55.         r->next=New;
  56.         r=New;
  57.         New=(Link)malloc(sizeof(Node));
  58.         if(New == NULL){
  59.             printf("memory allocate failure!\n");
  60.         }
  61.         scanf("%d",&New->number);
  62.         New->next=NULL;
  63.     }

  64.     return head;
  65. }

  66. Link insert_rank(Link head)
  67. {
  68.     int flag;
  69.     Link L=NULL;
  70.     Link point=NULL;
  71.     Link New=NULL;
  72.     Link q=NULL;
  73.     Link p=NULL;
  74.     Link s=NULL;

  75.     L=head; /* storage the head point */
  76.     for( point=L->next; point!=NULL; ) {
  77.         flag=0;
  78.         q=point->next;
  79.         p=L;
  80.         while( q!=NULL && p!=q ) {
  81.             s=p;
  82.             p=p->next;
  83.             if(q->number < p->number) {
  84.                 flag=1;
  85.                 New=(Link)malloc(sizeof(Node));
  86.                 if(New == NULL){
  87.                     printf("memory allocate failure!\n");
  88.                 }
  89.                 New->number=q->number;
  90.                 New->next=p;
  91.                 s->next=New;
  92.                 /* delete the node */
  93.                 point->next=q->next;
  94.                 free(q);
  95.                 break;
  96.             }
  97.         }
  98.         if(flag == 1)
  99.             continue;
  100.         else
  101.             point=point->next;
  102.     }
  103.     return head;
  104. }
  105. void Print_List(Link head)
  106. {
  107.     Link Pointer=NULL;
  108.     Pointer=head->next;
  109.     printf("*** Output Data ***\n");
  110.     while(Pointer != NULL) {
  111.         printf("number is: %d\n",Pointer->number);
  112.         Pointer=Pointer->next;
  113.     }
  114. }
  115. void Free_List(Link head)
  116. {
  117.     Link Pointer=NULL;
  118.     while(head != NULL){
  119.         Pointer=head;
  120.         head=head->next;
  121.         printf("Wait...............\n");
  122.         free(Pointer);
  123.     }
  124. }


转载请注明出处!!! 谢谢!!!



阅读(628) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~