一元稀疏多项式计算器doc.doc

 PAGE \* MERGEFORMAT 17 课程名称 数据结构课程设计 课题名称 一元稀疏多项式计算器 目录 一、课题的主要功能………………………………………………4 二、课题的功能模块的划分………………………………………6 三、主要功能的实现………………………………………………7 四、程序调试………………………………………………………9 五、总结（程序设计心得与体会）…………………………………11 六、附件（所有程序的原代码）……………………………………12 七、评分表…………………………………………………………18 一、课题的主要功能 a、课程题目 一元稀疏多项式计算器 b、需求分析 1、一元稀疏多项式简单计算器的功能是： 1.1 输入并建立多项式； 1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,??……cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 1.5多项式a和b相加，建立多项式a+b； 1.6 多项式a和b相减，建立多项式a-b； 1.7 计算多项式在x处的值。 2、设计思路: 2.1 定义线性表的动态分配顺序存储结构； 2.2 建立多项式存储结构，定义指针*next 2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式 2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en 3、设计思路分析 要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为 序数coef指数expn指针域next 运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。 为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则： ① 若p-expnq-expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。 ② 若p-expn=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。 ③ 若p-expnq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。 二、课题的功能模块的划分 内容包括： 函数CreatePolyn建立一个头指针为head、项数为m的一元多项式，然后调运函数Insert向生成链表中保存多项式项数及每项的指数、系数。函数CreatePolyn生成多项式a和多项式b。 通过函数compare和函数PrintPolyn对多项式a和多项式b指数、系数进行分析。当多项式a指数指数大于多项式b指数时，链表保存多项式a系数；当多项式b指数指数大于多项式a指数时，链表保存多项式b系数；当多项式b指数指数等于多项式a指数时，对多项式a和多项式b系数进行加减运算，之后将系数保存在链表中。 函数Polyn AddPolyn对多项式a和多项式b进行加运算，调运函数compare、函数PrintPolyn、函数CreatePolyn。 函数SubtractPolyn对多项式a和多项式b进行减运算，其对多项式b中各系数正负取反，然后调用函数Polyn AddPolyn进行a+(-b)。 主函数运行分别输入多项式和多项式的项数、系数和指数，然后选择对多项式操作A：a+b或 B：a-b，从而实现对多项式的加减运算。 函数的调用关系图： 三、主要功能的实现 1、元素类型、结点类型和指针类型： typedef struct Polynomial{ float coef; //系数 int expn; //指数 struct Polynomial *next; }*Polyn,Polynomial; 2、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点: Polyn CreatePolyn(Polyn head,int m){ int i;