newplan

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<conio.h>
  4 //============================================== 
  5 typedef struct PolyNode
  6 {
  7       int coef;//多項式項的系數 
  8       int exp;//多項式項的指數 
  9       struct PolyNode *next;
 10 }PolyNode;   //聲明了多項式項結構 
 11 //===============================================
 12 int PolyList_Init(PolyNode **head)//初始化表頭 (注意參數head的寫法)
 13 {
 14      *head =(PolyNode *)malloc(sizeof(PolyNode));
 15      if(NULL==*head)
 16      return 0;
 17      else{(*head)->next=NULL; 
 18            return 1;}
 19 }
 20 //================================================ 
 21 int PolyList_Empty(PolyNode *head)//判斷連表示是否為空 
 22 {
 23  if(head==NULL)
 24         return 1;//當鏈表頭節點都沒有的時候返回 1； 
 25  if(head->next==NULL)
 26         return 2;//當鏈表只存在頭節點的時候返回 2； 
 27         else return 0; //當鏈表即存在頭節點又存在實節點的時候返回 0； 
 28 }
 29 //=================================================
 30 int PolyNode_Insert(PolyNode *head,PolyNode *Insertor)//在多項式鏈表的適當位置插入鏈表 
 31 {
 32     if(PolyList_Empty(head)==1)
 33          {
 34                            printf("No PolyList Exist! Can not do Insert\n");
 35                            return 0;
 36          }
 37     PolyNode *p_front=head;
 38     PolyNode *p=head->next;
 39     if(PolyList_Empty(head)==2)
 40          {
 41                             Insertor->next=head->next;
 42                             head->next=Insertor; 
 43                             return 1;
 44          }
 45     int sum=0;
 46     while(p)
 47     {       
 48             if(p->exp == Insertor->exp)
 49                  {
 50                  if(sum=(p->coef+Insertor->coef))
 51                     {
 52                         p->coef=sum;
 53                         free(Insertor); 
 54                         return 1;
 55                     }
 56                  else{
 57                          p_front->next=p->next;
 58                          free(p);
 59                          free(Insertor);
 60                          return 1;
 61                     }
 62                  }
 63             else if(p->exp > Insertor->exp)
 64                  {
 65                      Insertor->next=p;
 66                      p_front->next=Insertor;
 67                      return 1;
 68                  }
 69             else {p_front=p;
 70                   p=p->next;}
 71     } 
 72     if(!p)
 73         {
 74                   p_front->next=Insertor;
 75                   Insertor->next=NULL;
 76                   return 1;
 77         }
 78 }
 79 //========================================= 
 80 void PolyList_Free(PolyNode *head)//釋放鏈表 
 81 {
 82     PolyNode *p,*q;
 83     for(p=head;p!=NULL;)
 84         {q=p;
 85          p=p->next;
 86          free(q);
 87         }
 88         
 89 }
 90 //==========================================
 91 PolyNode* PolyList_Create(PolyNode *head)//創建一個多項式鏈表 
 92 {
 93           
 94     if(!PolyList_Init(&head))
 95    {  
 96       printf("Init PolyLIst Fail!\n");
 97       exit(1);
 98    }
 99    PolyNode *tmp=NULL;
100    int coef_tmp;
101    do{  
102       tmp=(PolyNode*)malloc(sizeof(PolyNode));
103       if(!tmp)
104          {  PolyList_Free(head);
105              printf("malloc fail\n");
106               exit(1);
107           }
108        printf("coef=");
109        scanf("%d",&(tmp->coef));
110        coef_tmp=tmp->coef;
111        printf("exp=");
112        scanf("%d",&(tmp->exp));
113        if(0!=tmp->coef)
114          PolyNode_Insert(head,tmp);
115     }while(0!=coef_tmp);
116    free(tmp);
117    return head;
118 }
119 //========================================================== 
120 PolyNode *PolyList_Copy(PolyNode *head)// 復制多項式（鏈表）
121 {
122    if(PolyList_Empty(head)==1)
123      {
124                  printf("No PolyList Exist!\n");
125                  return NULL;
126      }
127    PolyNode *head_copy=head;
128    if(PolyList_Empty(head)==2)
129          {
130                          if(!PolyList_Init(&head_copy))
131                               {  
132                                printf("Init PolyLIst Fail!\n");
133                                    exit(1);
134                                }
135                           return head_copy;
136          }
137     if(!PolyList_Init(&head_copy))
138     {  
139       printf("Init PolyLIst Fail!\n");
140       exit(1);
141     }
142     PolyNode *p_copy=head_copy->next; 
143     PolyNode *p_copy_front=head_copy; //定義一個指在p_copy前面節點的指針，完成復制鏈表的鏈接工作； 
144     PolyNode *p=head->next;
145     while(p)
146     {
147          {  
148             p_copy=(PolyNode*)malloc(sizeof(PolyNode));
149             p_copy_front->next=p_copy;//使p_copy_front->next指向p_copy剛剛申請到的新節點； 
150             p_copy_front=p_copy;//指針跟隨P_copy向前移動 
151             p_copy->coef=p->coef;
152             p_copy->exp=p->exp;    
153         }
154         p=p->next;
155     }
156     p_copy->next=NULL; 
157     return head_copy;
158 }
159 //================================================= 
160 int  PolyList_View(PolyNode *head)//版本低的多項式訪問 
161 {
162      if(PolyList_Empty(head))
163        {printf("No PolyList Exist or Poly Empty! Can not do View\n");
164         return 0;
165        }
166         PolyNode *p;
167         printf("Poly=");
168         int count=0; 
169      for(p=head->next;p->next!=NULL;)
170       {
171         count++;
172         printf("(%dx^%d)+",p->coef,p->exp);
173         p=p->next;
174      }
175         count++; 
176         printf("(%dx^%d)  ##多項式的項數為%d\n",p->coef,p->exp,count);
177         
178         return 1;
179 }
180 //===================================================
181 int  PolyList_View_2(PolyNode *head)//版本高的多項式訪問 
182 {
183      if(PolyList_Empty(head)==1)
184        {printf("No PolyList Exist! Can not do View\n");
185         return 0;
186        }
187      if(PolyList_Empty(head)==2)
188        {
189         printf("Poly=0\n");
190         return 1;
191        }
192      PolyNode *p;
193      printf("Poly=");
194      for(p=head->next;p!=NULL;)
195      {
196       if(p->coef<0)
197         if(0==p->exp)
198            printf("%d",p->coef);
199         else{  if(-1==p->coef)
200                   printf("-x^%d",p->exp);
201                else
202                   printf("%dx^%d",p->coef,p->exp);
203             }
204       if(p->coef>0)
205         if(0==p->exp)
206            {if(p==head->next)
207               printf("%d",p->coef);
208             else
209                printf("+%d",p->coef);
210             }
211         else{ if(1==p->coef)
212                  {if(p==head->next)
213                      printf("x^%d",p->exp);
214                  else
215                      printf("+x^%d",p->exp);
216                      }
217                else
218                {if(p==head->next)
219                   printf("%dx^%d",p->coef,p->exp);
220                 else
221                   printf("+%dx^%d",p->coef,p->exp);
222                }
223             }
224       p=p->next;
225      }
226      printf("\n");
227      return 1;
228 }
229 //========================================================
230 PolyNode* PolyList_Add(PolyNode *lhead,PolyNode *rhead)//多項式相加，rhead將被清空 
231 {  if(PolyList_Empty(lhead)==1||PolyList_Empty(rhead)==1)
232       {
233          printf("No PolyNode Exist,can not do Add\n");
234          return lhead;
235       }
236    PolyNode *p1_front=lhead;
237    PolyNode *p1=lhead->next,*p2=rhead->next;
238    free(rhead);
239    int sum;
240    PolyNode *p2_tmp;
241    while(p1&&p2)
242    {      
243           if(p2->exp == p1->exp)
244                {
245                 if(sum=(p1->coef+p2->coef))
246                     {
247                 
248                          p1->coef=sum;
249                          
250                          p2_tmp=p2->next; 
251                          free(p2);
252                          p2=p2_tmp;   
253                  
254                          p1_front=p1;
255                          p1=p1->next;
256                         
257                     }
258                  else{
259                          p1_front->next=p1->next;
260                          p2_tmp=p2->next;
261                          free(p2);
262                          p2=p2_tmp;
263                          free(p1);
264                          p1=p1->next;
265                     }
266                }
267                else if(p2->exp < p1->exp )
268                {
269                      p1_front->next=p2;
270                  
271                      p2=p2->next;
272                      p1_front=p1_front->next;
273                      p1_front->next=p1;
274               
275                     
276                }
277                else 
278                {
279                     p1_front=p1;
280                     p1=p1->next;
281                }
282              
283    }
284    if(!p1)
285        p1_front->next=p2;
286  return lhead;
287    
288 } 
289 //======================================================================
290 PolyNode* PolyList_Dec(PolyNode *lhead,PolyNode *rhead)//多項式減法運算 ，rhead將被清空 
291 {
292    if(PolyList_Empty(lhead)==1||PolyList_Empty(rhead)==1)
293       {
294          printf("No PolyNode Exist,can not do Dec\n");
295          return lhead;
296       }
297    PolyNode *p1_front=lhead;
298    PolyNode *p1=lhead->next,*p2=rhead->next;
299    free(rhead);//將rhead對應的頭節點釋放掉 
300    int sum;
301    PolyNode *p2_tmp;
302    while(p1&&p2)
303    {      
304           if(p2->exp == p1->exp)
305                {
306                 if(sum=(p1->coef-p2->coef))
307                     {
308                 
309                          p1->coef=sum;
310                          
311                          p2_tmp=p2->next; 
312                          free(p2);
313                          p2=p2_tmp;   
314                  
315                          p1_front=p1;
316                          p1=p1->next;
317                         
318                     }
319                  else{
320                          p1_front->next=p1->next;
321                          p2_tmp=p2->next;
322                          free(p2);
323                          p2=p2_tmp;
324                          free(p1);
325                          p1=p1->next;
326                         
327                     }
328                }
329                else if(p2->exp < p1->exp )
330                {
331                      p1_front->next=p2;
332                      p2->coef=-p2->coef; 
333                      p2=p2->next;
334                      p1_front=p1_front->next;
335                      p1_front->next=p1;
336               
337                     
338                }
339                else 
340                {
341                     p1_front=p1;
342                     p1=p1->next;
343                }
344              
345    }
346    if(!p1)
347    p1_front->next=p2;
348    while(p2)
349       { 
350             p2->coef=-p2->coef;
351             p2=p2->next;
352       }   
353  return lhead;
354  } 
355  //===============================================================
356 float Poly_X_Sum(PolyNode *head,float x)//求任意的X對應的多項式所得的值 
357 {
358     if( PolyList_Empty(head)){
359        printf("No Poly exist or Poly Empty! Can not do X_Sum\n");
360        getch();
361        return 0;
362       }
363     PolyNode *p=head->next; 
364     float sum=0;
365     float xsum=1;
366     int i=0; 
367     while(p)
368     {
369       // printf("p->exp=%d\n",p->exp);
370        if(p->exp>0)
371        for( i=0,xsum=1;i!=p->exp;i++)//注意xsum還原為 1！ 
372          {  xsum*=x;
373         // printf("xsum --- %f\n",xsum);
374          }
375        if(p->exp<0)
376        for(i=0,xsum=1;i!=p->exp;i--)
377            xsum/=x;
378        if(p->exp==0)
379            xsum=1.0;
380        sum+=(float)p->coef*xsum;   
381     //   printf("xsum=%f\n",xsum); 
382      //  printf("sum=%f\n",sum); 
383             p=p->next;
384         }
385        return sum;
386 }
387 //=================================================
388 PolyNode *PolyList_Der(PolyNode * head)//對多項式求一般的一階導數 
389 {
390   if(PolyList_Empty(head)==1){
391        printf("No Poly Exist! Can not do Der\n");
392        getch();
393        return NULL;
394       }
395   if(PolyList_Empty(head)==2){
396        
397        return head;  //對0求導數還是0，所以返回頭節點就可以 
398        }
399   PolyNode *p_front=head;
400   PolyNode *p=head->next;
401   while(p)
402   {
403           if(0==p->exp)
404           {
405              p_front->next=p->next;
406              free(p);
407              p=p_front->next;
408           }
409           else{
410                p->coef*=p->exp; 
411                p->exp--; 
412                p_front=p;
413                p=p->next;
414                }
415   }       
416   return head;
417 }
418 //==================================================
419 PolyNode *PolyList_Der_N(PolyNode * head,int N)//對多項式求N階導數 
420 {//這邊再寫空鏈表的判斷語句是有好處的，以防當鏈表為空時進入循環消耗時間 
421  
422   if(PolyList_Empty(head)==1){ 
423        printf("No Poly Exist!Can not do Der_N\n");
424        getch();
425        return head;
426       }
427   if(PolyList_Empty(head)==2){
428     
429        return head;  //對0求導數還是0，所以返回頭節點就可以 
430        }
431      int i;
432      for( i=0;i!=N;i++)
433          head=PolyList_Der(head); 
434      return head;   
435 }
436 //===============================================================
437 PolyNode *PolyList_Mul(PolyNode *lhead,PolyNode * rhead)//多項式的乘法實現（內部采用復制多項式） 
438 {
439     if(PolyList_Empty(lhead)==1||PolyList_Empty(rhead)==1){
440        printf("No Poly Exist! Can not do Mul\n");
441        getch();
442        return lhead;
443       }
444    if(PolyList_Empty(lhead)==2) {//此處讓結果返回頭節點的意思是若兩個節點其中有一個是空的，則相乘后的結果應該為0. 
445        PolyList_Free(rhead); //同時還要將其中的一個鏈表清除，因為這已經是做了乘法運算了。 
446        return lhead;
447    }
448    if(PolyList_Empty(rhead)==2){//同上 
449        PolyList_Free(lhead); 
450        return rhead;  
451    }
452     PolyNode *p_copy_from_lhead=PolyList_Copy(lhead);//這里已經把第一個多項式的原型給拷貝到一個新的鏈表中； 
453     PolyNode *p_copy_from_lhead_2=NULL;//等會講使用這個指針來從上面的指針拷貝鏈表 
454     PolyNode *p_copy_tmp=NULL;
455     PolyNode *p2_front=rhead;
456     PolyNode *p2=rhead->next;
457     PolyNode *p1=lhead->next;
458     free(p2_front); //將rhead的頭節點處理掉 
459     while(p1)
460     {
461              p1->coef*=p2->coef;
462              p1->exp+=p2->exp;
463              p1=p1->next;
464     }//到此處完成第一個多項式與第二個多項式的第一項的乘法，但是此時的第一個多項式已經被破壞； 
465     //PolyList_View(lhead);
466     p2_front=p2;  
467     p2=p2->next;
468     free(p2_front);//處理掉rhead的第一個節點 
469     while(p2)
470     {
471              p_copy_from_lhead_2=PolyList_Copy(p_copy_from_lhead);
472              p_copy_tmp=p_copy_from_lhead_2->next;
473              while(p_copy_tmp)
474               {
475                      p_copy_tmp->coef*=p2->coef;
476                      p_copy_tmp->exp+=p2->exp;
477                      p_copy_tmp= p_copy_tmp->next;
478               }
479              lhead=PolyList_Add(lhead,p_copy_from_lhead_2);
480              p2_front=p2; 
481              p2=p2->next;
482              free(p2_front);//處理掉p2_front所對應的節點，這樣當循環完成后rhead的所有節點就被清除完畢 
483               //  PolyList_View(lhead);
484             
485     } 
486     PolyList_Free(p_copy_from_lhead);//將拷貝lhead的第一個版本釋放掉 
487     return lhead;
488 }
489 //=====================================================================
490 int main(void)
491 {   printf("輸入多項式1：格式：coef表示任意項的系數 exp表示對應coef項的指數（輸入ceof=0結束exp任意）\n");
492     PolyNode *head_1=NULL;
493     head_1=PolyList_Create(head_1);
494     PolyList_View_2(head_1);
495     printf("輸入多項式2：格式：coef表示任意項的系數 exp表示對應coef項的指數（輸入ceof=0結束exp任意）\n");
496     PolyNode *head_2=NULL;
497     head_2=PolyList_Create(head_1);
498     PolyList_View_2(head_2);
499     PolyNode *head_4=PolyList_Copy(head_2);  
500     printf("得到兩個多項式相加之后的多項式\n");
501     head_1=PolyList_Add(head_1,head_2);
502     PolyList_View_2(head_1);  
503     printf("得到兩個多項式相減之后的多項式\n");
504     
505     head_1=PolyList_Dec(head_1,head_4);
506     PolyList_View_2(head_1);    
507     printf("復制產生一個新的完全一樣的多項式\n");
508     PolyNode *head_3=PolyList_Copy(head_1);  
509     PolyList_View(head_3);  
510     printf("兩個多項式相乘head_1*head_3:\n");
511     head_1=PolyList_Mul(head_1,head_3); 
512     PolyList_View(head_1); 
513     printf("對多項式求一次導數\n");
514     head_1=PolyList_Der(head_1);
515     PolyList_View(head_1);
516     printf("再對多項式求兩次導數\n");//求幾次導就給函數的第二個參數賦多少（例如3就是球三次導數！） 
517     head_1=PolyList_Der_N(head_1,2);
518     PolyList_View_2(head_1);
519     printf("令X=9.0，得到多項式的和\n"); 
520     float  sum=0;
521     float x=9.89;
522     printf("按任意鍵繼續\n"); 
523     getch();
524     sum=Poly_X_Sum(head_1,x);
525     printf("多項式的和為%f\n",sum); 
526     PolyList_Free(head_1);
527     printf("按任意鍵繼續\n"); 
528     getch();
529     return 0;
530 }
531