www.pudn.com > zb.rar > 005.c

#include "stdio.h" 
#include "conio.h" 
#define  NULL     0 
struct list 
{int data; 
 struct list *next; 
}; 
typedef struct list lnode; 
typedef lnode *list; 
 
int n,m; 
 
list create()     /*建立链表*/ 
{list L,p; 
 int data; 
 L=(list)malloc(sizeof(lnode)); 
 L->next=NULL; 
 printf("please input the data for a list(end by -999):\n"); 
 do{p=(list)malloc(sizeof(lnode)); 
    scanf("%d",&data); 
    p->data=data; 
    p->next=L->next; 
    L->next=p; 
   } 
 while(data!=-999); 
 L->next=p->next; 
 return(L); 
} 
 
list fpre(list p,list L)               /*在L中找P的前趋*/ 
{list q; 
 q=L; 
 while(q->next!=p) 
 q=q->next; 
 return(q); 
} 
 
list ylist(list L)                /*找链表中从L开始的最小结点*/ 
{list p,min; 
 p=L; 
 min=L; 
 while(p->next!=NULL) 
     {n++; 
      p=p->next; 
      if(p->datadata) 
         min=p; 
     } 
return(min); 
} 
 
list xlist(list L)            /*排序链表（按递增排序）*/ 
{list min,q,i,p; 
 p=L->next; 
 i=L; 
 do{ 
    min=ylist(p); 
    q=fpre(min,L); 
    q->next=min->next; 
    min->next=i->next; 
    i->next=min; 
    i=min; 
    p=i->next; 
    } 
 while(i->next->data!=NULL); 
return(L); 
} 
 
list ylist2(list L)                /*找链表中从L开始的最小结点2*/ 
{list p,min; 
 p=L; 
 min=L; 
 while(p->next!=NULL) 
     {m++; 
      p=p->next; 
      if(p->datadata) 
         min=p; 
     } 
return(min); 
} 
 
list xlist2(list L)            /*排序链表2（按递增排序）*/ 
{list min,q,i,p; 
 p=L->next; 
 i=L; 
 do{ 
    min=ylist2(p); 
    q=fpre(min,L); 
    q->next=min->next; 
    min->next=i->next; 
    i->next=min; 
    i=min; 
    p=i->next; 
    } 
 while(i->next->data!=NULL); 
return(L); 
} 
 
 
list breaklist(list L)        /*把链表一分为二*/ 
{list L2,p; 
 int n,m; 
 p=L; 
 n=0; 
 while(p->next!=NULL) 
      {p=p->next; 
       n++; 
       } 
 m=n/2; 
 n=0; 
 while(n!=m) 
      {p=p->next; 
       n++; 
      } 
 L2=(list)malloc(sizeof(lnode)); 
 L2->next=p->next; 
 p->next=NULL; 
 return(L2); 
} 
 
list mergelist(list La,list Lb)             /*将La和Lb合并为链表Lc*/ 
{list pa,pb,pc,Lc; 
 pa=La->next; 
 pb=Lb->next; 
 pc=Lc=La; 
 while((pa->data!=NULL)&&(pb->data!=NULL)) 
    {if(pa->data<=pb->data) 
        {pc->next=pa; 
         pc=pa; 
         pa=pa->next; 
         } 
     else 
        {pc->next=pb; 
         pc=pb; 
         pb=pb->next; 
         } 
      m++; 
     } 
  if(pa->data==NULL) 
    pc->next=pb; 
  else 
    pc->next=pa; 
return(Lc); 
} 
 
 
void plist(list L)               /*打印链表*/ 
{list p; 
 p=L; 
 p=p->next; 
 while(p->next!=NULL) 
     {printf("%d\t",p->data); 
      p=p->next; 
     } 
 printf("%d\n",p->data); 
 
} 
 
 
 
pai() 
{list La,Lb,Lc,pa,pb; 
 La=create(); 
 pa=xlist(La); 
 printf("La:\t"); 
 plist(pa); 
 printf("O(n)=%d\n",n); 
 Lb=breaklist(La); 
 pa=xlist2(La); 
 pb=xlist2(Lb); 
 Lc=mergelist(pa,pb); 
 printf("Lc:\t"); 
 plist(Lc); 
 printf("O(m)=%d\n",m); 
 
 getch(); 
}