首页 / 操作系统 / Linux / 双链表&链表合并&多项式相加算法

双链表&链表合并&多项式相加算法 //单链表的合并
 
//链表合并
 //两个链表必须是有序的
 #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） ; 
 }本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-08/105671.htm