将兩個單向有序連結清單合并成一個單向有序連結清單

1 #include <stdio.h>  
  2 #include <stdlib.h>  
  3 #include <string.h>  
  4 typedef struct student                                                          //聲明結構體  
  5 {  
  6     int num;  
  7     struct student *pnext;  
  8 }stu,*pstu;  
  9 void link_sort_insert(pstu *,pstu *,int);                                       //建立有序連結清單  
 10 void link_show(pstu );                                                           
 11 void link1_merge_link2(pstu *phead1,pstu *ptail1,pstu *phead2,pstu *ptail2);    //把連結清單2合并到1  
 12 void main(){  
 13     pstu phead1,ptail1,phead2,ptail2;  
 14     int i;  
 15     phead1 = NULL;  
 16     ptail1 = NULL;  
 17     phead2 = NULL;  
 18     ptail2 = NULL;    
 19     while(scanf("%d",&i) != EOF){                                               //建立連結清單1  
 20         link_sort_insert(&phead1,&ptail1,i);  
 21           
 22     }  
 23     link_show(phead1);  
 24     while(scanf("%d",&i) != EOF){                                               //建立連結清單2  
 25         link_sort_insert(&phead2,&ptail2,i);  
 26           
 27     }  
 28     link_show(phead2);  
 29     link1_merge_link2(&phead1,&ptail1,&phead2,&ptail2);                        //合并  
 30     link_show(phead1);                                                           
 31     system("pause");  
 32   
 33 }  
 34 void link_sort_insert(pstu *phead,pstu *ptail,int i){                            //建立有序連結清單  
 35     pstu pnew,pcur,ppre;  
 36     pnew = (pstu)malloc(sizeof(stu));  
 37     memset(pnew,0,sizeof(stu));  
 38     pnew->num = i;  
 39     if(*phead == NULL){  
 40         *phead = pnew;  
 41         *ptail = pnew;  
 42     }  
 43     else if((*phead)->num > i){  
 44         pnew->pnext = *phead;  
 45         *phead = pnew;  
 46           
 47     }  
 48     else{  
 49         pcur = *phead;  
 50         ppre = *phead;  
 51         while(pcur != NULL){  
 52             if(pcur->num > i){  
 53                 pnew->pnext = ppre->pnext;  
 54                 ppre->pnext = pnew;  
 55                 break;  
 56             }  
 57             ppre = pcur;  
 58             pcur = pcur->pnext;  
 59         }  
 60         if(pcur == NULL){  
 61         (*ptail)->pnext = pnew;  
 62         *ptail = pnew;  
 63         }  
 64     }  
 65       
 66 }  
 67 void link1_merge_link2(pstu *phead1,pstu *ptail1,pstu *phead2,pstu *ptail2){                   //把連結清單2合并到1  
 68     pstu i,ppre,pcur;  
 69     pcur = *phead1;                                                                         //pcur ppre 指向連結清單1頭結點  
 70     ppre = *phead1;   
 71     while(*phead2 != NULL){      
 72         i = *phead2;                                                                      //記錄連結清單2頭結點的目前位置  
 73         *phead2 = (*phead2)->pnext;                                                       //連結清單頭結點指向下1個結點  
 74         if((*phead1)->num > i->num){                                                      //判斷連結清單1頭結點是否大于i  
 75             i->pnext = *phead1;                                                       //如果大于，插入頭結點  
 76             *phead1 = i;  
 77             pcur = *phead1;                                                           //pcur ppre 重新指向連結清單1頭結點  
 78             ppre = *phead1;  
 79         }  
 80         else{                                                                             //連結清單1頭結點不大于i  
 81             while(pcur != NULL){                                                           
 82                 if(pcur->num > i->num){                                           //判斷連結清單1目前節點pcur是否大于i  
 83                     i->pnext = ppre->pnext;                                    //若大于i 則插入，循環結束，pcur不動  
 84                     ppre->pnext = i;  
 85                     break;  
 86                 }  
 87                 ppre = pcur;                                                        //若cur <=i 記錄目前pcur，pcur指向下一個位置  
 88                 pcur = pcur->pnext;  
 89             }  
 90             if(pcur == NULL){                                                          //如果連結清單1達到尾結點，i插入到連結清單1尾節點  
 91                 (*ptail1)->pnext = i;   
 92                 *ptail1 = i;  
 93             }  
 94         }  
 95     }  
 96     *phead2 = NULL;                                                                           //釋放  
 97     *ptail2 = NULL;  
 98 }  
 99 void link_show(pstu phead){  
100     pstu pshow;  
101     pshow = phead;  
102     if(phead == NULL)  
103     {  
104         printf("no exsit\n");  
105         return;  
106     }  
107     while(pshow != NULL){  
108         printf("%d ",pshow->num);  
109         pshow = pshow->pnext;  
110     }  
111     putchar('\n');  
112 }