北邮数据结构上机元多项式.docVIP

数据结构实验报告 实验名称： 实验1——线性表 学生姓名： 班 级： 班内序号： 学 号： 日 期： 1．实验要求 实验目的： 熟悉C++语言的基本编程方法，掌握集成编译环境的测试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作实现方法 培养使用线性表解决实际问题的能力 实验内容： 利用线性表实现一个一元多项式Polynomial; f(x)=a0+a1x+a2x2+a3x3+…+anxn 提示：Polynomial的结点结构如下： struct term { float coef;\\系数 int expn;\\指数 }； 可以使用链表实现，也可以使用顺序表实现 具体要求如下： 能够实现一元多项式的输入和输出 能够进行一元多项式相加 能够进行一元多项式相减 能够计算一元多项式在x处的值 能够计算一元多项式的导数（选作） 能够进行一元多项式相乘（选作） 编写main ()函数测试算法的正确性 2. 程序分析 由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。 本程序完成的主要功能： 1、输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。 2、多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。 3、多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。 4、多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。 5、多项式的乘法：根据输入信息八两多项式计算，并输出一个新的多项式。 2.1 存储结构 本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下： 2.2 关键算法分析 1、多项式的输入： 自然语言描述： 设置多项式的项数n； 按照多项式的项数申请动态结构数组element *e=new element[n]存储多项式的系数和指数； 按照指数递增的次序输入各项的系数以及指数，分别存入coef和exp； 再将输入的系数以及指数赋给每一个结点的coef和exp域； 利用头插法将每个结点加入链表。 ·伪代码： 输入项数n； element *e=new element[n]; 运用for循环，循环n次 3.1 element *e=new element[n]; 3.2 cine[i].exp; 3.3 cine[i].coef; 3.4 return e; 4. 运用头插法将结点插入链表。 2、n-1次（n为多项式的项数） 2.1将指针的指向后移； 2.2依照多项式的各种情况，设置输出方式 2.2.1 系数为1且指数不为1和0，输出Xexpn+； 2.2.2 系数不为0且指数为0，输出（coef）+（coef）+； 2.2.4 系数不为0和1，指数不为0和1，输出(coef)X(expn)+； 3.将指针指向移到最后一个节点。重复2.2中判断，但不输出+号。 源代码如下： Node element *p= GetFirst()-next; if(p==NULL) { cout0; } while(p) { if(p-data.exp==0) { coutp-data.coef; } else { coutp-data.coefXp-data.exp; } p=p-next; if((p!=0)(p-data.coef0)) { cout+; } } 3、p和q分别指向a和b两个多项式的头结点的下一个节点； 将结果多项式的项数置为0； 只有p或q非空，进行以下循环： 申请一个term* 型的指针d，将其next域赋为NULL；进行判断： 如果p和q均非空 如果p和q的指数相等 将d的系数赋为p、q系数之和，指数不变，将p、q指向后移； 如果p-expn