实现多项式的加法和乘法运算

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 /*使用链表实习多项式的加法运算*/
  4 typedef struct linkList{
  5     int xiShu;
  6     int ciShu;
  7     struct linkList *next;
  8 }list,*pList;
  9 
 10 
 11 pList init_linkList(){
 12     pList head;
 13     head = (pList)malloc(sizeof(list));
 14     if(head){
 15         head->next = NULL;
 16     }
 17     return head;
 18 }
 19 
 20 int insert(pList *rear,int xiShu,int ciShu){
 21     if((*rear)==NULL){
 22        printf("head node is null,don't allow insert element
");
 23        return 0;
 24     }else{
 25         pList newNode = (pList)malloc(sizeof(list));
 26         newNode->xiShu=xiShu;
 27         newNode->ciShu=ciShu;
 28         newNode->next = (*rear)->next;
 29         (*rear)->next = newNode;
 30         *rear = newNode;
 31         return 1;
 32     }
 33 }
 34 
 35 
 36 void toString(pList list){
 37     pList p = list->next;
 38     printf("
toString:");
 39     while(p!=NULL){
 40         printf("%dx^%d ",p->xiShu,p->ciShu);
 41         p=p->next;
 42     }
 43     printf("
");
 44 }
 45 
 46 void print(pList list){
 47     pList p = list->next;
 48     int flag=0;
 49     if(!list){
 50         print("0 0
");
 51         return;
 52     }
 53     while(p!=NULL){
 54         if(!flag){
 55             flag=1;
 56         }else{
 57             printf(" ");
 58         }
 59         printf("%d %d",p->xiShu,p->ciShu);
 60         p=p->next;
 61     }
 62     printf("
");
 63 }
 64 
 65 int compare(pList p1,pList p2){
 66     if(p1->ciShu>p2->ciShu){
 67         return 1;
 68     }else if(p1->ciShu<p2->ciShu){
 69         return -1;
 70     }else{
 71         return 0;
 72     }
 73 }
 74 
 75 void attach(int xiShu,int ciShu,pList *rear){
 76     pList p = (pList)malloc(sizeof(list));
 77     p->ciShu=ciShu;
 78     p->xiShu=xiShu;
 79     p->next=(*rear)->next;
 80     (*rear)->next=p;
 81     (*rear)=p;
 82 }
 83 
 84 
 85 
 86 pList polyAdd(pList list1,pList list2){
 87     int sum;
 88     pList rear = init_linkList();
 89     pList font = rear;
 90     pList p1 =list1->next;
 91     pList p2 = list2->next;
 92     while(p1 && p2){
 93         switch(compare(p1,p2)){
 94             case 1:
 95                 attach(p1->xiShu,p1->ciShu,&rear);
 96                 p1=p1->next;
 97                 break;
 98 
 99             case -1:
100                 attach(p2->xiShu,p2->ciShu,&rear);
101                 p2 = p2->next;
102                 break;
103             case 0:
104                 sum = p1->xiShu+p2->xiShu;
105                 if(sum){
106                     attach(sum,p1->ciShu,&rear);
107                 }
108                 p1 = p1->next;
109                 p2 = p2->next;
110                 break;
111         }
112 
113     }
114 
115     for(;p1;p1=p1->next){
116         attach(p1->xiShu,p1->ciShu,&rear);
117     }
118 
119     for(;p2;p2=p2->next){
120         attach(p2->xiShu,p2->ciShu,&rear);
121     }
122     rear->next=NULL;
123     return font;
124 }
125 
126 pList mult(pList p1,pList p2){
127     pList p,rear,t1,t2,t;
128     int c,e;
129     if(!p1 || !p2){
130         return NULL;
131     }
132     t1=p1;
133     t2=p2;
134     p = (pList)malloc(sizeof(list));
135     p->next = NULL;
136     rear =p;
137     while(t2){//先用p1的第一项乘以p2,得到p
138         attach(t1->xiShu*t2->xiShu,t1->ciShu+t2->ciShu,&rear);
139         t2 = t2->next;
140     }
141     t1=t1->next;
142     while(t1){
143         t2=p2;
144         rear=p;
145         while(t2){
146             e=t1->ciShu+t2->ciShu;
147             c=t1->xiShu*t2->xiShu;
148             while(rear->next && rear->next->ciShu>e){
149                 rear=rear->next;
150             }
151             if(rear->next && rear->next->ciShu==e){
152                 if(rear->next->xiShu+c){
153                     rear->next->xiShu+=c;
154                 }else{
155                     t=rear->next;
156                     rear->next = t->next;
157                     free(t);
158                 }
159             }else{
160                 t = (pList)malloc(sizeof(list));
161                 t->ciShu=e;
162                 t->xiShu=c;
163                 t->next=rear->next;
164                 rear->next=t;
165                 rear=rear->next;
166             }
167             t2 = t2->next;
168         }
169         t1=t1->next;
170     }
171 
172     return p;
173 }
174 
175 pList readLine(){
176     int n,i,xiShu,ciShu;
177     scanf("%d",&n);
178     pList list = init_linkList();
179     pList listRear = list;
180     for(i=0;i<n;i++){
181         scanf("%d %d",&xiShu,&ciShu);
182         insert(&listRear,xiShu,ciShu);
183     }
184 
185     return list;
186 }
187 
188 
189 void main(){
190     /*
191     pList list1 = init_linkList();
192     pList list2 = init_linkList();
193     pList list1Rear = list1;
194     pList list2Rear = list2;
195     insert(&list1Rear,3,4);
196     insert(&list1Rear,-5,2);
197     insert(&list1Rear,6,1);
198     insert(&list1Rear,-2,0);
199     //insert(&list1Rear,-1,0);
200 
201     insert(&list2Rear,5,20);
202     insert(&list2Rear,-7,4);
203     insert(&list2Rear,3,1);
204     //insert(&list2Rear,1,1);
205     //toString(list1);
206     //toString(list2);
207     */
208     pList list1 = readLine();
209     //toString(list1);
210     pList list2 = readLine();
211     pList result = polyAdd(list1,list2);
212     pList p = mult(list1->next,list2->next);
213     print(p);
214     print(result);
215 }