数据结构课程设计(一元稀疏多项式计算器).docVIP

实习报告：1.5题 一元稀疏多项式计算器 题目：设计一个一元稀疏多项式简单计算器 班级：计科一班 姓名：康宇 学号 完成日期：2013.4.15 一、需求分析 1、一元稀疏多项式简单计算器的功能是： 1） 输入并建立多项式； 2） 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 3） 多项式a和b相加，建立多项式a+b； 4） 多项式a和b相减，建立多项式a-b。 5） 计算多项式在x处的值； 6） 求多项式a、b的导函数； 2、测试数据： 1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7); 2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15) =(-7.8x^15-1.2x^9+12x^-3-x); 3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5); 4、(x+x^3)+(-x-x^3)=0; 5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200); 6、(x+x^2+x^3)+0=x+x^2+x^3. 二、概要设计 为实现上述程序功能，应以有序链表来表示多项式的系数和指数。定义线性表的动态分配顺序存储结构；建立多项式存储结构，定义指针*next利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式 演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。 1、元素类型、结点类型和指针类型： typedef struct LNode { float xishu; //系数 int zhishu; //指数 struct LNode *next; } LNode,*Linklist; 2、建立两个全局链表指针， Linklist List1=NULL; Linklist List2=NULL; 用来存放两个多项式，然后在main（）函数里调用输入函数。 3、本程序包括7个模块 1）主程序： Void main() { While(1) { 输出菜单； 接受命令； 处理命令； If（命令==退出） 则程序退出； } 释放链表；} 2）输入函数： Void Input() { 调用插值函数In（List1）处理链表一； 调用插值函数In（List2）处理链表二； } 3)输出函数： Void Output() { 调用输值函数Out（List1）处理链表一； 调用输值函数Out（List2）处理链表一；} 4）相加函数： Void Add() { if(List1节点指数 List2节点指数) 输出List1节点; 指针后移； else if(List1节点指数 List2节点指数) 输出List2节点; 指针后移； else 输出两节点相加后的值； 两链表指针都后移； if(链表1到头) 输出链表2剩余的节点； else(即链表二到头) 输出链表1剩余的节点；} 5）相减函数： Void Sub() { if(List1节点指数 List2节点指数) 输出List1节点; 指针后移； else if(List1节点指数 List2节点指数) 输出List2节点;(系数要取负再输出) 指针后移； Else 两链表指针都后移； if(链表1到头) 输出链表2剩余的节点； else(即链表二到头) 输出链表1剩余的节点；} 6）求值函数： void Calc() { 输入x的值； 依次调用链表一的节点，求出单项式的值相加后输出； } 7）求导函数： void Daohansh