首页 > 代码库 > 双链表&链表合并&多项式相加算法

双链表&链表合并&多项式相加算法

 //单链表的合并

//链表合并
//两个链表必须是有序的
#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 =http://www.mamicode.com/2*i;
q= (Linklist  *)malloc(sizeof(Linklist)); 
q->data=http://www.mamicode.com/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 =http://www.mamicode.com/2*i+1; //减10,两个链表不等
q= (Linklist  *)malloc(sizeof(Linklist)); 
q->data=http://www.mamicode.com/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 =http://www.mamicode.com/= 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=http://www.mamicode.com/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) ;  
}