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

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

//单链表的合并
 
//链表合并
 //两个链表必须是有序的
 #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) ; 
 }