雙鏈表&鏈表合並&多項式相加算法

雙鏈表&鏈表合並&多項式相加算法

 //單鏈表的合並
 
//鏈表合並
 //兩個鏈表必須是有序的
 #define Maxsize 5
 typedef  int elemtype;
 typedef struct linklist
 {
  elemtype data;
    struct linklist *next;
 }Linklist;
 

 //建立鏈表1
 Linklist *CreateList1 ()
 {
 int i,data ;
 Linklist *head, *p, *q;
 head=p=(Linklist  *)malloc(sizeof(Linklist));
 p->next=NULL;        //創建單鏈表的表頭結點head 
 

    for(i=0;i<Maxsize;i++)
 {   
        data =2*i;
 q= (Linklist  *)malloc(sizeof(Linklist));
 q->data=data;   
 q->next=p->next;
 p->next=q;
 p=q;
    }
    return (head); 
 }
 

//建立鏈表2
 Linklist *CreateList2 ()
 {
 int i,data ;
 Linklist *head, *p, *q;
 head=p=(Linklist  *)malloc(sizeof(Linklist));
 p->next=NULL;        //創建單鏈表的表頭結點head 
 

    for(i=0;i<Maxsize;i++)
 {   
        data =2*i+1;  //減10,兩個鏈表不等
 q= (Linklist  *)malloc(sizeof(Linklist));
 q->data=data;   
 q->next=p->next;
 p->next=q;
 p=q;
 
}
    return (head); 
 }
 

int main()
 {
    linklist *La=CreateList1();
    linklist *Lb=CreateList2();
 

  linklist *Lc,*L1,*L2,*Lp;
    Lc=(Linklist *)malloc(sizeof(Linklist));
    Lc->next=NULL;
    Lc->next=La->data < Lb->data ? La:Lb;
    L1=La;
    L2=Lb;
    Lp=Lc;
    while(L1->next!= NULL && L2->next!=NULL)
    {
  if(L1->data < L2->data )
  { 
  Lp->next=L1;
  L1=L1->next;
  }
  if(L1->data > L2->data )
  { 
  Lp->next=L2;
  L2=L2->next;
  }
        if(L1->data == L2->data )
  { 
  Lp->next=L1;
  L1=L1->next;
  L2=L2->next;
  }
    }
    if(L1->next= NULL)
  Lp->next=L2;
    else
  Lp->next=L1;
 

  while(1);
    return 0;
 }
 
//循環鏈表的條件： p->next=head;
               
  //雙向鏈表
 ADT:
    typedef struct dullinklist
 {
  elemtype data;
  struct dullinklist *prior,*next;
 }                     
 ADP:
 //添加一個結點：假設在p,q中間添加一個結點add：
 dullinklist *add;
 add=(dullinklist *)malloc(sizeof(dullinklist));
 add.data=data;
 p->next=add;
 add->next=q;
 q->prior=add
 add->next=p;
 //刪除一個結點：
 

p->prior->next=p->next;
 p->next->prior=p->prior;
 free(p);
 

//線性表和鏈表的應用——多項式的加減法
 1）線性表表示法：
 typedef struct linearlist
 {
  elemtypefloat factor; //系數
  elemtypeint series;  //級數
 }
 多項式的每一項都由級數和系數唯一確定，但是對於某些系數為0的項，會占用內存浪費資源
 因此使用鏈表
 

2）鏈表表示法
 typedef struct linklist
 {
  elemtypefloat factor; //系數
  elemtypeint series;  //級數
  struct linearlist *next；
 }
 3)多項式相加：兩個鏈表合並，系數為0的項刪掉
 linklist *add(linklist *la,linklist *lb)
 {
  linklist *lc,*pc,*pa,*pb,*flag;
  lc=(linklist *)malloc(sizeof(linklist));
  pc=(linklist *)malloc(sizeof(linklist));
  pa=(linklist *)malloc(sizeof(linklist));
  pb=(linklist *)malloc(sizeof(linklist));
 
  lc=pc;
  lc->next=pa;
  pa=la;
  pb=lb;
  while(pa->next!=NULL && pb->next!=NULL)
  {
    if(pa->series < pb=series)
    {
    pc-next=pa;
    pc=pa;
    pa=pa-next; 
    }
    if(pa->series > pb->series)
    {
    pc-next=pb;
    pc=pb;
    pb=pb-next; 
    }
    if(pa->series = pb->series)
    {
      elemtype x=pa->factor+pb->factor;
      if(x<=1e-6)
        {
          flag=pa;
          pa=pa->next;
          pb=pb->next;
          free(pa);
          free(pb);
          }
        else
        {
          pc->factor=x;
          pc-next=pa;
          pc=pa;
          pa=pa-next; 
          flag=pb;
          pb=pb->next;
          free(pb);
        }
    }
  }
  if(pa==NULL) 
    pc->next=pb ;
  else 
    pc->next=pa ;
  return (Lc) ; 
 }