数据结构课程设计报告一元多项式的计算.
题目:一元多项式的计算
——链表
摘要(题目) 一元多项式计算
任务:能够按照指数降序排列建立并输出多项式;
能够完成两个多项式的相加、相减,并将结果输入;
目录
1.引言
2.需求分析
3.概要设计
4.详细设计
5.测试结果
6.调试分析
7.设计体会
8.结束语
参考文献
一:引言:
通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。基本算法:
1、输入输出
(1)功能:将要进行运算的多项式输入输出。
(2)数据流入:要输入的多项式的系数与指数。
(3)数据流出:合并同类项后的多项式。
(4)程序流程图:多项式输入流程图如图1所示。
(5)测试要点:输入的多项式是否正确,若输入错误则重新输入
2、多项式的加法
(1)功能:将两多项式相加。
(2)数据流入:输入函数。
(3)数据流出:多项式相加后的结果。
(4)程序流程图:多项式的加法流程图如图2所示。
(5)测试要点:两多项式是否为空,为空则提示重新输入,否则,进行运算。
图表 2
3、多项式的减法
(1)功能:将两多项式相减。
(2)数据流入:调用输入函数。
(3)数据流出:多项式相减后的结果。
(4)程序流程图:多项式的减法流程图如图3所示。
(5)测试要点:两多项式是否为空,为空则提示重新输入,否则,进行运算。
四.详细设计
1. 根据题目要求采用单连表存储结构
typedef struct LNode //定义单链表
{
}LNode,*LinkList;
void InitList(LinkList &L) //定义一个空表
{ }
void CreatPolyn(LinkList &L) //用单链表定义一个多项式
{ }
void DispPolyn(LinkList L) //显示输入的多项式
{ }
void Polyn(LinkList &pa,LinkList &pb)
{}
2.主函数 main
void main()
{
LNode *L1,*L2;
Polyn(L1,L2);
}
2. 函数的调用关系层次结构
多项式 Polyn 用单链表定义多项式 CreatPolyn 定义一个空表 InitList 显示输入的多项式 DispPolyn
}
五. 调试分析
采用单连表形式按照指数降序排列建立并输出多项式;在相加,相减的过程 中如果指数相同就执行系数相加,相减,否则就把大的项直接写入。完成两个多 项式的相加、相减;将从新得到的单连表结果输出;该算法的时间复杂度为两个 多项式的项式之和
六:调试结果
测试的数据及结果
算法的时间复杂度及改进
算法的时间复杂度:一元多项式的加法运算的时间复杂度为O(m+n),减法运算的时间复杂度为O(m-n),其中m,n分别表示二个一元多项式的项数。
问题和改进思想:在设计该算法时,出现了一些问题,例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值,不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果,而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列,可在数据的输入后先做一个节点的排序函数,通过对链表排序后再进行之后加减运算。
七. 心得体会:一元多项式计算是一个的单链表的运用, 通过这个程序可以测我们以前的学习情 况,看看我们是否对单链表真正的理解。
一元多项式计算器的基本功能定为:
(1) 建立多项式
(2) 输出多项式
(3) 两个多项式相加,建立并输出和多项式
(4) 两 个多项式相减,建立并输出差多项式能够按照指数降序排列建立并输出多项式;
能够完成两个多项式的相加、相减,并将结果输出;
结束语:
时间过的很快,,课程设计也接近尾声.说起课程设计,我认为最重要的就是做好设计的预习,认真的研究老师给的题目,老师对题目的讲解要一丝不苟的去听去想,因为只有都明白了,做起设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,它能充分锻炼实践能力的重要环节,是对学生实际工作能力的具体和考 察过程#include
#include
typedef struct Polynomial{
float coef;
int expn;
struct Polynomial