005.c

用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->data<min->data)
         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->data<min->data)
         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();
}