两个一元多项式的相乘

  1 //两个一元多项式的相乘
  2 
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 
  6 struct PolyNode {
  7     int coefficient;
  8     int exponent;
  9     struct PolyNode* next;
 10 };
 11 
 12 typedef struct PolyNode*  Polynomial;
 13 
 14 
 15 //初始化一元链表多项式
 16 Polynomial InitPoly()
 17 {
 18     Polynomial P, rear, temp;
 19     P = rear = (Polynomial)malloc(sizeof(struct PolyNode));
 20     int cnt, coef, expon;        //cnt是多项式的项数 
 21     printf("Please enter the number of items in the polynomial: ");
 22     scanf_s("%d", &cnt);
 23     while (cnt--)
 24     {
 25         scanf_s("%d%d", &coef, &expon);
 26         Polynomial temp = (Polynomial)malloc(sizeof(struct PolyNode));
 27         temp->coefficient = coef;
 28         temp->exponent = expon;
 29         temp->next = NULL;
 30         rear->next = temp;
 31         rear = temp;
 32     }
 33     temp = P;
 34     P = P->next;
 35     free(temp);
 36     return P;
 37 }
 38 
 39 //类似尾插法创建链表
 40 void Attach(int coef, int expon, Polynomial *pRear)
 41 {
 42     Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode));
 43     P->coefficient = coef;
 44     P->exponent = expon;
 45     P->next = NULL;
 46     (*pRear)->next = P;
 47     (*pRear) = P;
 48 }
 49 
 50 Polynomial PolyMult(Polynomial P1, Polynomial P2)
 51 {
 52     Polynomial front, rear, temp;
 53     int c, e;
 54     if (!P1 || !P2)
 55         return NULL;
 56     struct PolyNode* t1, *t2;
 57     t1 = P1, t2 = P2;
 58     front = rear = (Polynomial)malloc(sizeof(struct PolyNode));
 59     while (t2)
 60     {
 61         Attach(t1->coefficient * t2->coefficient,
 62             t1->exponent + t2->exponent, &rear);
 63         t2 = t2->next;
 64     }
 65     t1 = t1->next;
 66     while (t1)
 67     {
 68         t2 = P2;
 69         rear = front;
 70         while (t2)
 71         {
 72             e = t1->exponent + t2->exponent;
 73             c = t1->coefficient + t2->coefficient;
 74             while (rear->next && rear->next->exponent > e)
 75                 rear = rear -> next;
 76             if (rear->next && rear->next->exponent == e)
 77             {
 78                 if (rear->next->coefficient + c)
 79                     rear->next->coefficient += c;
 80                 else
 81                 {
 82                     temp = rear ->next;
 83                     rear -> next = rear->next->next;
 84                     free(temp);
 85                 }
 86             }
 87             else
 88             {
 89                 temp = (Polynomial)malloc(sizeof(struct PolyNode));
 90                 temp -> coefficient = c;
 91                 temp->exponent = e;
 92                 temp->next = rear->next;
 93                 rear->next= temp;
 94                 rear = rear -> next;
 95             }
 96             t2 = t2->next;
 97         }
 98         t1 = t1->next;
 99     }
100     temp = front;
101     front = front->next;
102     free(temp);
103     return front;
104 }
105 
106 void PrintPoly(Polynomial P)
107 {
108     int flag = 0;        //辅助调整输出格式用
109     if (!P)
110     {
111         printf("0 0\n");
112         return;
113     }
114     while (P)
115     {
116         if (!flag)
117             flag = 1;
118         else
119             printf(" ");
120         printf("%dX^%d", P->coefficient, P->exponent);
121         P = P -> next;
122     }
123     printf("\n");
124         
125 }
126 
127 
128 
129 int main()
130 {
131     Polynomial P1 = InitPoly();
132     Polynomial P2 = InitPoly();
133     PrintPoly(P1);
134     PrintPoly(P2);
135     Polynomial P3 = PolyMult(P1, P2);
136     PrintPoly(P3);
137 
138     return 0;
139 }