数据结构_多项式_实验报告北邮.docVIP

北京邮电大学信息与通信工程学院 第 PAGE 9页 北京邮电大学电信工程学院 第 PAGE 1页 数据结构实验报告 实验名称： 实验一——多项式的实现 学生姓名： 班 级： 班内序号： 学 号： 日 期： 2012年11月08日 1．实验要求 实验目的： 1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 2.学习指针、模板类、异常处理的使用 3.掌握线性表的操作的实现方法 4.学习使用线性表解决实际问题的能力 实验内容： 利用线性表实现一个一元多项式Polynomial f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn 要求： 能够实现一元多项式的输入和输出 能够进行一元多项式相加 能够进行一元多项式相减 能够计算一元多项式在x处的值 能够计算一元多项式的导数（选作） 能够进行一元多项式相乘（选作） 编写测试main()函数测试线性表的正确性 2. 程序分析 由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度，求和或者求差操作结束后，两个链表将合并在一起，。 本程序完成的主要功能： 输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。并将B表按具体情况合并到A表中，形成结果多项式。 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。 2.1 存储结构 本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个???点的地址。示意图如下： front …… coef1 expn1 next coef1 expn1 next coef1 expn1 next 2.2 关键算法分析 输入多项式 设置多项式的项数n； 按照多项式的项数申请动态数组ea[]和eb[]存储两个多项式的结点,c1[]、d1[]、c2[]、d2[]分别存储两个多项式的系数和指数； 再将输入的系数以及指数赋给每一个结点的coef和expn域； 利用尾插法将每个结点加入链表。 时间复杂度： 空间复杂度： 输出多项式 获取头结点,并将其赋给结点指针p； 当p不为零时循环 2.1如果p结点的系数为正数且p结点不为头结点,则在输出这一项前加”＋”,即输出”+coef*x^exp”， p指针后移； 2.2否则直接输出p结点的”coef*x^exp”,p指针后移； 时间复杂度：O(1) 空间复杂度：S(1) 多项式的相加 1.若p-data.expq-data.exp 1.1 q结点不变 1.2 p结点向下移 1.2.1 p_prior=p; 1.2.2 p=p-next; 2.若p-data.expq-data.exp执行一下主要操作步骤 2.1 p_prior-next=q; 2.2 p_prior=q; 2.3 q=q-next; 2.4 p_prior-next=p; 示意图: 3.若p-data.exp==q-data.exp执行以下操作步骤: 3.1 若合并系数为零,则删除p结点,主要步骤: 3.1.1 p_prior-next=p-next; 3.1.2 delete p; 3.1.3 p=p_prior-next; 3.1.4 Nodeelement*temp=q; 3.1.5 q=q-next; 3.1.6 delete temp; 示意图: 3.2 合并系数不为零,将其从新赋予p结点,主要步骤: 3.2.1 p_prior=p; 3.2.2 p=p_prior-next; 3.2.3 Nodeelement*temp=q; 3.2.4 q=q-next; 3.2.5 delete temp; 示意图: 4.若p为空且q不为空的情况 p_prior-next=q; 示意图: 5. 将B链表置成空链表 时间复杂度：O(n) 空间复杂度：O(2)