当前位置：VC爱好者 → 一般性编程 → Data Structure(数据结构) → 正文
单链表实现一元多项式相加
本文适合中级读者阅读  作者：郭郭    来源：vcLover.com    日期: 2008/01/31    浏览：

单链表 用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象)

+ 指针(指示后继元素存储位置)

= 结点

(表示数据元素 或 数据元素的映象)

以“结点的序列”表示线性表

称作线性链表（单链表）

单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i
可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。
因此，在单链表中第 i 个结点之前进行插入的基本操作为:
找到线性表中第i-1个结点，然后修改其指向后继的指针。

本文实现了一元多项式的运算。运行结果如下：
 

折叠 C/C++ Code
  1. //VC爱*好-者vclover.com   
  2. //www.vcLover.com   
  3. #include <iostream.h>   
  4. #include<stdio.h>   
  5. #include<malloc.h>   
  6. #include<stdlib.h>   
  7. #define  LEN  sizeof(node)    
  8.   
  9. //用单链表存储多项式的结点结构   
  10. typedef struct polynode      
  11. {   
  12.       int coef;  //多项式的系数   
  13.       int exp;   //指数   
  14.       struct polynode *next;   
  15. }node;   
  16. //指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数   
  17. node * create(void)    
  18. {   
  19.      node *h,*r,*s;   
  20.      int c,e;   
  21.      //建立多项式的头结点，为头结点分配存储空间   
  22.      h=(node *)malloc(LEN);    
  23.      r=h; //r指针始终动态指向链表的当前表尾   
  24.      cout<<"系数: ";   
  25.      cin>>c;   
  26.      cout<<"指数: ";   
  27.      cin>>e;   
  28.      //输入系数为0时，表示多项式的输入结束   
  29.      while(c!=0)     
  30.     {   
  31.           s=(node *)malloc(LEN); /*申请新结点*/  
  32.           s->coef=c;  /*申请新结点后赋值*/  
  33.           s->exp=e;   /*申请新结点后赋值*/  
  34.           r->next=s; /*做尾插，插入新结点*/  
  35.           r=s;  /*r始终指向单链表的表尾*/  
  36.           cout<<"系数: ";   
  37.           cin>>c;   
  38.           cout<<"指数: ";   
  39.           cin>>e;   
  40.     }   
  41.     r->next=NULL;   
  42.     return(h);   
  43. }   
  44. //一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除   
  45. void polyadd(node *polya, node *polyb)   
  46. {   
  47.        node *p,*q,*pre,*temp;   
  48.        int sum;   
  49.        p=polya->next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/  
  50.        q=polyb->next;   
  51.        pre=polya;    /*位置指针，指向和多项式polya*/  
  52.        while(p!=NULL&&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/  
  53.       {   
  54.             if(p->exp<q->exp)           /*若p指向的多项式指数小于q指的指数*/  
  55.             {   
  56.                    pre->next=p;      /*将p结点加入到和多项式中*/  
  57.                    pre=pre->next;   
  58.                    p=p->next;   
  59.             }   
  60.             else if(p->exp==q->exp)    /*若指数相等，则相应的系数相加*/  
  61.             {   
  62.                    sum=p->coef+q->coef;   
  63.                    if(sum!=0)   
  64.                    {   
  65.                         p->coef=sum;   
  66.                         pre->next=p;pre=pre->next;p=p->next;   
  67.                         temp=q;q=q->next;free(temp);   
  68.                     }   
  69.                   else     /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/  
  70.                  {   
  71.                        temp=p->next;free(p);p=temp;   
  72.                        temp=q->next;free(q);q=temp;   
  73.                  }   
  74.            }   
  75.           else                      /*若p指数大于q指数*/    
  76.           {   
  77.                 pre->next=q;  /*p结点不动，将q结点加入到和多项式中*/  
  78.                 pre=pre->next;   
  79.                 q=q->next;   
  80.           }   
  81.     }   
  82.     if(p!=NULL)  /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/  
  83.            pre->next=p;   
  84.     else        /*否则将B的结点加入到和多项式中*/    
  85.            pre->next=q;                                                            
  86. }   
  87.   
  88. void print(node * p) /*输出函数，打印出一元多项式*/  
  89. {                                                                                                         
  90.     while(p->next!=NULL)   
  91.     {      
  92.         p=p->next;   
  93.         cout<<p->coef<<"*x^"<<p->exp;   
  94.         if(p->next != NULL) cout<<"+";   
  95.     }   
  96. }      
  97.   
  98. void main()    
  99. {   
  100.       node * polya,* polyb;   
  101.       cout<<"输入第一个多项式的系数和指数，以系数为0结束:"<<endl;   
  102.       polya=create();  /*调用建立链表函数，创建多项式A*/  
  103.       print(polya);   
  104.       cout<<endl<<"输入第二个多项式的系数和指数，以系数为0结束:"<<endl;   
  105.       polyb=create();   
  106.       print(polyb);   
  107.       cout<<endl<<"相加的结果是:";   
  108.       polyadd(polya,polyb);    /*调用一元多项式相加函数*/  
  109.       print(polya);            /*调用输出函数，打印结果*/  
  110.       cout<<endl;   
  111. }  

 

[打印] [关闭]
上一篇：逆波兰表达式_数据结构作业   下一篇：C++求解八皇后问题_数据结构作业
相关文章
查看全部评论相关评论
评论内容：
昵称： 验证码：验证码
What's New?
What's Hot?
Google Adsense!