newplan

阿基米德在洗澡時發現浮力原理,高興得來不及穿㆖褲子,跑到街㆖大喊:Eureka(我找到了)。
posts - 39, comments - 26, trackbacks - 0, articles - 4
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

多项式单向链表实现

Posted on 2007-10-05 20:21 山泉弯延 阅读(1098) 评论(4)  编辑 收藏 引用 所属分类: 数据结构实验集
  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         elseif(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 

Feedback

# re: 多项式单向链表实现  回复  更多评论   

2007-10-05 21:20 by chenzhenqiang
加油

# re: 多项式单向链表实现  回复  更多评论   

2007-10-06 16:46 by AMXTSHMF
都是代码撒

# 7170  回复  更多评论   

2008-08-02 15:09 by 7170
7170

# 7170  回复  更多评论   

2008-08-02 15:10 by 7170
0550

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理