实验名称：一元多项式相加
 // multiply.cpp : 定义控制台应用程序的入口点。

 //

 #include "stdafx.h"

 #include<iostream>

 #include "stdio.h"

 using namespace std;

 /***********************定义多形式的数据结构*************************/

 typedef struct Node

 {

   int coef;      //多项式系数

   int exp;         //多项式指数

   struct Node *next;//指向下一项的指针

 } Node,*LinkList;   //定义了一个Node型指针的别名LinkList;

 /***********************多项式初始化*************************/

 void initpoly (LinkList &px)

 {

    px = new Node;

    px ->next = NULL;

 }

 /***********************多项式创建*************************/

 void creatpoly (LinkList &px,int n )

 {

     LinkList p=NULL,q=NULL;  //q是用来开辟空间的。

     p = px;      //p是用来存储整个链表的。    这里px相当于一个全局的指针变量一样。

     for(int i = ; i < n; i++)

     {

         q = new Node;

         cout << "请输入第" << i << "项的系数："<< endl;

         cin >> q ->coef;

         cout << "请输入第" << i << "项的指数："<< endl;

         cin >> q ->exp;

         q ->next = NULL;

         p ->next = q;//链表向前一直在扩大。

         p = q;

     }

 }

 int lengthpoly(LinkList &px) //计算多项式的项数。

 {

     LinkList p = NULL;

     int count = ;

     p = px ->next;

     while(p != NULL)

     {

         p = p ->next;

         count++;

     }

     return count;

 }

 /***********************多项式输出*************************/

 void outputpoly(LinkList &px)

 {

     LinkList p = NULL;

     p = px ->next;

     for(int i = ;i < lengthpoly(px);i++)

     {

         cout << p ->coef << "*X^" << p->exp << "+";

         p = p ->next;

     }

     cout << "" << endl;

 }

 /***********************多项式相加*************************/

 //void addpoly(LinkList &pa,LinkList &pb,LinkList &pc)

 //{

 //    LinkList la=NULL,lb=NULL,lc=NULL,r=NULL;

 //    la = pa ->next;

 //    lb = pb ->next;

 //    lc = pc;     //prep是用来存储整个a+b的链表的。

 //    while(la&&lb)//a与b其中一个不为0

 //    {

 //        if(la ->exp < lb ->exp)  //a的指数小

 //        {

 //            r = new Node;

 //            r ->coef = la ->coef;

 //            r ->exp = la ->exp;

 //            lc ->next = r;

 //            lc = r;

 //            r ->next = NULL;

 //            la = la ->next;

 //        }

 //        else if(la ->exp > lb ->exp)

 //        {

 //            r = new Node;

 //            r ->coef = lb ->coef;

 //            r ->exp = lb ->exp;

 //            lc ->next = r;

 //            r ->next = NULL;

 //           lc = r;

 //           lb = lb ->next;

 //        }

 //        else

 //        {

 //            int sum = la ->coef + lb ->coef;

 //            if(sum != 0)

 //            {

 //                r = new Node;

 //                r ->coef = sum;

 //                r ->exp = la ->exp;

 //                lc ->next = r;

 //                r ->next = NULL;

 //                lc = r;

 //                la = la ->next;

 //                lb = lb ->next;

 //            }

 //            else

 //            {

 //                la = la ->next;

 //                lb = lb ->next;

 //            }

 //        }

 //

 //    }

 //    while(la != NULL)

 //        {

 //            r = new Node;

 //            r ->coef = la ->coef;

 //            r ->exp = la ->exp;

 //            lc ->next = r;

 //            lc = r;

 //            r ->next = NULL;

 //            la = la ->next;

 //        }

 //   while(lb != NULL)

 //        {

 //            r = new Node;

 //            r ->coef = lb ->coef;

 //            r ->exp = lb ->exp;

 //            lc ->next = r;

 //            lc = r;

 //            r ->next = NULL;

 //            lb = lb ->next;

 //        }

 //}

 Node * addDuoX(LinkList &Pa,LinkList &Pb)//关键部分，A与B相加

 {

     Node *p,*q;

     Node *prep;

     Node *u;

     p = Pa->next;

     q = Pb->next;

     prep=Pa;

     while (p&&q)//Ａ与Ｂ都不等于０

     {

         if(p->exp<q->exp)//A的指数小于B的指数

         {

             prep=p;

             p=p->next;

         }

         else if(p->exp > q->exp)//A的指数大的话

         {

             u=q->next;

             q->next=p;

             prep->next=q;

             prep=q;

             q=u;

         }

         else//A与B的指数相等的话

         {

             p->coef=p->coef+q->coef;

             if(p->coef==)//A与B的指数相等的话,且其中A的系数为0

             {

                 Node *temp1;

                 Node *temp2;

                 temp1=p;

                 temp2=q;

                 prep->next=p->next;//删除该项数

                 p=p->next;

                 q=q->next;

                 delete temp1;

                 delete temp2;

             }

             else//A与B的指数相等的话,且其中A的系数为0，B的系数为0

             {

                 Node *temp2;

                 temp2=q;

                 prep=p;

                 p=p->next;

                 q=q->next;

                 delete temp2;

             }

         }

     }

     if(q)

         prep->next=q;

     delete Pb;

     return Pa;

 }

 //再做一个小的处理，先合并同类型。对指数相同的进行相加，并删去其中一个，合并同类项

 void hebing(Node *px)

 {

     Node *p = NULL,*q = NULL;

     p = px ->next;

     q = new Node;

     while(p->next!=NULL)

     {

         q = p ->next;

         if(p ->exp == q ->exp)

         {

             p ->coef = p->coef + q->coef;

             p -> next = q -> next;

              //p 不在受q约束,一直不受其约束。

             delete(q);

         }

         p = p ->next;

     }

 }

 /*** 程序中用了选择排序 ***/

 void paixu(Node *px)

 {

     //用选择排序怎么做

     Node *p = NULL,*q = NULL;

     p = px ->next; //此时开辟了内存空间。

     q = px ->next;

     int temp; //注：类初始化化时需要加上（），而结构体初始化不需要。

     for(p ;p!= NULL;p = p ->next)  //这玩意就相当于i++,

     {

         for(q = p ->next; q!= NULL; q = q ->next ) //为什么不用q -> next，因为q = p -> next 了。

         {

             if(p ->exp > q ->exp)   //我真是弄错啦，我现在只需要把结点里面的值换掉就行了，何必换掉整个的结点，这样位置肯定出问题。

             {

                 temp = p ->exp;

                 p ->exp = q ->exp;

                 q ->exp = temp;

                 temp = p ->coef;

                 p ->coef= q ->coef;

                 q ->coef = temp;

             }

         }

     }

 }

 int main()

 {

     LinkList pa = NULL,pb = NULL,pc = NULL;

     initpoly(pa);

     initpoly(pb);

     initpoly(pc);

     int a,b;

     cout << "输入第一个多项式的项数："<<endl;

     cin >> a;

     cout << "输入第二个多项式的项数："<<endl;

     cin >> b;

     cout << "请按升序输入："<<endl;

     cout << "请输入第一个多项式的系数与指数"<<endl;

     creatpoly(pa,a);

     hebing(pa);

     paixu(pa);

     outputpoly(pa);

     cout << "请按升序输入："<<endl;

     cout << "请输入第二个多项式的系数与指数"<<endl;

     creatpoly(pb,b);

     paixu(pb);

     outputpoly(pb);

     //addpoly(pa,pb,pc);

     pc = addDuoX(pa,pb);

     outputpoly(pc);

     cin >> b;

     delete(pa);

     delete(pb);

     delete(pc);

     return ;

 }
 

实验目的：练习并掌握如何使用C++语言实现链表的说明、创建等操作。

实验要求：能实现一元多项式的输入、输出，以及两个一元多项式相加及结果显示。（具体内容请参照数据结构实验内容）

实验步骤及内容：

1、首先建立一个定义多项式的结构体Node，及结构体指针LinkList，该结构体包含一个指数exp，一个系数coef，一个指向下一项的指针*next,代码如下：

typedef struct Node

{

int coef;      //多项式系数

int exp;         //多项式指数

struct Node *next;//指向下一项的指针

} Node,*LinkList;   //定义了一个Node型指针的别名LinkList;

2、初始化多项式，代码如下：

void initpoly (LinkList &px)

{

px = new Node;

px ->next = NULL;

}

3、建立多项式，用来指导用户输入程序运行时所需要的必须得数据，两个一元多项式的项数、系数、指数。具体的代码如下：

void creatpoly (LinkList &px,int n )

{

LinkList p=NULL,q=NULL;  //q是用来开辟空间的。

p = px;      //p是用来存储整个链表的。

for(int i = 0; i < n; i++)

{

q = new Node;

cout << "请输入第" << i << "项的系数："<< endl;

cin >> q ->coef;

cout << "请输入第" << i << "项的指数："<< endl;

cin >> q ->exp;

q ->next = NULL;

p ->next = q;

p = q;

}

}

4、求一个多形式的长度，主要用来获取一个多形式的长度，便于输出。

int lengthpoly(LinkList &px) //计算多项式的项数

{

LinkList p = NULL;

int count = 0;

p = px ->next;

while(p != NULL)

{

p = p ->next;

count++;

}

return count;

}

5、输出多形式，此函数用来对多项式进行输出验证。

void outputpoly(LinkList &px)

{

LinkList p = NULL;

p = px ->next;

for(int i = 0;i < lengthpoly(px);i++)

{

cout << p ->coef << "^" << p->exp << "+";

p = p ->next;

}

cout << "0" << endl;

}

6、多项式相加，输出也是按序排列。当两个多项式都不为0时，进行相加，然后剩下的部分直接赋给相加后的多项式，前提是输入的多形式必须是按顺序排列的。代码如下：

void outputpoly(LinkList &px)

{

LinkList p = NULL;

p = px ->next;

for(int i = 0;i < lengthpoly(px);i++)

{

cout << p ->coef << "*X^" << p->exp << "+";

p = p ->next;

}

cout << "0" << endl;

}

void addpoly(LinkList &pa,LinkList &pb,LinkList &pc)

{

LinkList la=NULL,lb=NULL,lc=NULL,r=NULL;

la = pa ->next;

lb = pb ->next;

lc = pc;     //prep是用来存储整个a+b的链表的。

while(la&&lb)//a与b其中一个不为

{

if(la ->exp < lb ->exp)  //a的指数小

{

r = new Node;

r ->coef = la ->coef;

r ->exp = la ->exp;

lc ->next = r;

lc = r;

r ->next = NULL;

la = la ->next;

}

else if(la ->exp > lb ->exp)

{

r = new Node;

r ->coef = lb ->coef;

r ->exp = lb ->exp;

lc ->next = r;

r ->next = NULL;

lc = r;

lb = lb ->next;

}

else

{

int sum = la ->coef + lb ->coef;

if(sum != 0)

{

r = new Node;

r ->coef = sum;

r ->exp = la ->exp;

lc ->next = r;

r ->next = NULL;

lc = r;

la = la ->next;

lb = lb ->next;

}

else

{

la = la ->next;

lb = lb ->next;

}

}

}

while(la != NULL)

{

r = new Node;

r ->coef = la ->coef;

r ->exp = la ->exp;

lc ->next = r;

lc = r;

r ->next = NULL;

la = la ->next;

}

while(lb != NULL)

{

r = new Node;

r ->coef = lb ->coef;

r ->exp = lb ->exp;

lc ->next = r;

lc = r;

r ->next = NULL;

lb = lb ->next;

}

}

7、主函数代码如下，为了便于交互，所以增加了好些用户提示符：

int main()

{

LinkList pa = NULL,pb = NULL,pc = NULL;

initpoly(pa);

initpoly(pb);

initpoly(pc);

int a,b;

cout << "输入第一个多项式的项数："<<endl;

cin >> a;

cout << "输入第二个多项式的项数："<<endl;

cin >> b;

cout << "请输入第一个多项式的系数与指数"<<endl;

creatpoly(pa,a);

cout << "请输入第二个多项式的系数与指数"<<endl;

creatpoly(pb,b);

addpoly(pa,pb,pc);

outputpoly(pc);

cin >> b;

delete(pa);

delete(pb);

delete(pc);

return 0;

}

当然我们可以在人性化一点，加上while实现，连续操作。

实验总结：

1、刚开始编的时候，老是出现不能访问内存错，说是没有初始化，不能访问。通过查找资料发现，在开辟一个新节点时，必须给其开辟空间，在c++里面用new语句，在c中用malloc语句即可。在定义结构体指针的时候，最好给其赋值为空，谨防出现野指针的情况。

2、  多项式相加的函数中，定义了一个返回LinkList的返回值，不过一直出错，直到我把返回值去掉的时候，才不会出错，具体什么原因，我现在还不清楚。

最新文章

  1. iOS的生命周期
  2. paip.语义分析--分词--常见的单音节字词 2_deDuli 单字词 774个
  3. 【BZOJ-4591】超能粒子炮&#183;改 数论 + 组合数 + Lucas定理
  4. Flex 加载dxf
  5. Linux：环境变量
  6. Check Mysql Database Size
  7. git stash 保存修改现场
  8. Week 5a - Mouse input and more lists----learning notes
  9. MATLAB描绘极坐标图像——polar
  10. MVC 5 - 查询Details和Delete方法
  11. &#127827; vue循环渲染本地图片不显示？ &#127827;
  12. SQL Server 主库DML操作慢故障处理过程
  13. python url监控 并邮件报警
  14. react中如何使用动画效果
  15. python打印log重复问题
  16. [Codeforces394B]Very Beautiful Number(逆推)
  17. Linux：echo中，&gt;和&gt;&gt;的区别（保存结果和追加结果）
  18. C#对Mongodb数组对象操作
  19. 102/107. Binary Tree Level Order Traversal/II
  20. [疯狂Java]JDBC：PreparedStatement预编译执行SQL语句

热门文章

  1. 做一个APP
  2. HDU 5875 Function（RMQ-ST+二分）
  3. 在做展开功能的时候，字体变多了，字体会变大的bug的解决方案
  4. regression
  5. 所驼门王的宝藏（bzoj 1924）
  6. 《Linux命令行与shell脚本编程大全 第3版》Linux命令行---34
  7. AC日记——石子归并 51nod 1021
  8. AC日记——【模板】树链剖分 洛谷 P3384
  9. 怎样在action中获得值栈ValueStack中的值
  10. IE6~IE7 bugs