两个多项式相加运算

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. typedef struct node
  5. {      float coef;            /*序数*/
  6.        int expn;              /*指数*/
  7.        struct node *next;    /*指向下一个结点的指针*/
  8. } PolyNode;
  10. void InitList(PolyNode *&L)        /*初始化多项式单链表*/
  11. {
  12.     L=(PolyNode *)malloc(sizeof(PolyNode));    /*建立头结点*/
  13.     L->next=NULL;
  14. }
  16. int GetLength(PolyNode *L)        /*求多项式单链表的长度*/
  17. {
  18.     int i=0;
  19.     PolyNode *p=L->next;
  20.     while (p!=NULL)        /*扫描单链表L,用i累计数据结点个数*/
  21.     {
  22.         i++;p=p->next;
  23.     }
  24.     return i;
  25. }
  27. PolyNode *GetElem(PolyNode *L,int i)    /*返回多项式单链表中第i个结点的指针*/
  28. {
  29.     int j=1;
  30.     PolyNode *p=L->next;
  31.     if (i<1 || i>GetLength(L)) 
  32.            return NULL;
  33.     while (j<i)                /*沿next域找第i个结点*/
  34.     {
  35.            p=p->next;j++;
  36.     }
  37.     return p;
  38. }
  40. PolyNode *Locate(PolyNode *L,float c,int e)    /*在多项式单链表中按值查找*/
  41. {
  42.     PolyNode *p=L->next;
  43.     while (p!=NULL && (p->coef!=c ||p->expn!=e))
  44.             p=p->next;
  45.     return p;
  46. }
  48. int InsElem(PolyNode *&L,float c,int e,int i)  /*在多项式单链表中插入一个结点*/
  49. {
  50.     int j=1;
  51.     PolyNode *p=L,*s;
  52.     s=(PolyNode *)malloc(sizeof(PolyNode));
  53.     s->coef=c;s->expn=e;s->next=NULL;
  54.     if (i<1 || i>GetLength(L)+1) 
  55.         return 0;
  56.     while (j<i)        /*查找第i-1个结点*p*/
  57.     {
  58.         p=p->next;j++;
  59.     }
  60.     s->next=p->next;
  61.     p->next=s;
  62.     return 1;
  63. }
  65. int DelElem(PolyNode *L,int i)        /*在多项式单链表中删除一个结点*/
  66. {
  67.     int j=1;
  68.     PolyNode *p=L,*q;
  69.     if (i<1 || i>GetLength(L)) 
  70.         return 0;
  71.     while (j<i)        /*在单链表中查找第i-1个结点*p*/
  72.     {
  73.         p=p->next;j++;
  74.     }
  75.     q=p->next;
  76.     p->next=q->next;
  77.     free(q);
  78.     return 1;
  79. }
  81. void DispList(PolyNode *L)        /*输出多项式单链表的元素值*/
  82. {
  83.     PolyNode *p=L->next;
  84.     while (p!=NULL)
  85.     {
  86.         printf("(%g,%d) ",p->coef,p->expn);
  87.         p=p->next;
  88.     }
  89.     printf("\n");
  90. }
  91. void CreaPolyList(PolyNode *&L,float C[],int E[],int n)
  92. {
  93.     int i;
  94.     InitList(L);
  95.     for (i=0;i<n;i++)
  96.         InsElem(L,C[i],E[i],i+1);
  97. }
  99. void SortPloy(PolyNode *&L)    /*对L的多项式单链表按expn域递增排序*/
  100. {
  101.     PolyNode *p=L->next,*q,*pre;
  102.     L->next=NULL;
  103.     while (p!=NULL) 
  104.     {
  105.         if (L->next==NULL)                     /*处理第1个结点*/
  106.         {
  107.             L->next=p;p=p->next;
  108.             L->next->next=NULL;
  109.            }
  110.         else                                  /*处理其余结点*/
  111.         {
  112.             pre=L;q=pre->next;
  113.             while (q!=NULL && p->expn>q->expn)     /*找q->expn刚大于或等于p->expn的结点*q的前驱结点*pre*/
  114.             {
  115.                 pre=q;q=q->next;
  116.             }
  117.             q=p->next;                      /*在*pre结点之后插入*p*/
  118.             p->next=pre->next;
  119.             pre->next=p;
  120.             p=q;
  121.         }    
  122.     }
  123. }
  125. PolyNode *AddPoly(PolyNode *pa,PolyNode *pb)
  126. {
  127.     PolyNode *pc,*p1=pa->next,*p2=pb->next,*p,*tc,*s;
  128.     pc=(PolyNode *)malloc(sizeof(PolyNode));    /*新建头结点*/
  129.     pc->next=NULL;                    /*pc为新建单链表的头结点*/
  130.     tc=pc;                            /*tc始终指向新建单链表的最后结点*/
  131.     while (p1!=NULL && p2!=NULL) 
  132.     {
  133.         if (p1->expn<p2->expn)        /*将*p1结点复制到*s并链到pc尾*/
  134.         {
  135.             s=(PolyNode *)malloc(sizeof(PolyNode));
  136.             s->coef=p1->coef;s->expn=p1->expn;s->next=NULL;
  137.             tc->next=s;tc=s;
  138.             p1=p1->next;
  139.         }
  140.         else if (p1->expn>p2->expn)    /*将*p2结点复制到*s并链到pc尾*/
  141.         {
  142.             s=(PolyNode *)malloc(sizeof(PolyNode));
  143.             s->coef=p2->coef;s->expn=p2->expn;s->next=NULL;
  144.             tc->next=s;tc=s;
  145.             p2=p2->next;
  146.         }
  147.         else   /*p1->expn=p2->expn的情况*/
  148.         {
  149.             if (p1->coef+p2->coef!=0) /*序数相加不为0时新建结点*s并链到pc尾*/
  150.             {
  151.                 s=(PolyNode *)malloc(sizeof(PolyNode));
  152.                 s->coef=p1->coef+p2->coef;s->expn=p1->expn;
  153.                 s->next=NULL;
  154.                 tc->next=s;tc=s;
  155.             }
  156.             p1=p1->next;p2=p2->next;
  157.         }
  158.     }
  159.     if (p1!=NULL) p=p1;  /*将尚未扫描完的余下结点复制并链接到pc单链表之后*/
  160.     else p=p2;
  161.     while (p!=NULL) 
  162.     {
  163.         s=(PolyNode *)malloc(sizeof(PolyNode));
  164.         s->coef=p->coef;s->expn=p->expn;s->next=NULL;
  165.         tc->next=s;tc=s;
  166.         p=p->next;
  167.     }
  168.     tc->next=NULL;        /*新建单链表最后结点的next域置空*/
  169.     return pc;
  170. }
  172. void main()
  173. {
  174.     PolyNode *L1,*L2,*L3;
  175.     float C1[]={3,7,5,9},C2[]={-9,8,22};
  176.     int E1[]={1,0,17,8},E2[]={8,1,7};
  177.     InitList(L1);
  178.     InitList(L2);
  179.     InitList(L3);
  180.     CreaPolyList(L1,C1,E1,4);
  181.     CreaPolyList(L2,C2,E2,3);
  182.     printf("两多项式相加运算\n");
  183.     printf("     原多项式A:");DispList(L1);
  184.     printf("     原多项式B:");DispList(L2);
  185.     SortPloy(L1);
  186.     SortPloy(L2);
  187.     printf("排序后的多项式A:");DispList(L1);
  188.     printf("排序后的多项式B:");DispList(L2);
  189.     L3=AddPoly(L1,L2);
  190.     printf("多项式相加结果:");DispList(L3);
  191. }