实习一 【一元稀疏多项式简单计算器】.doc

PAGE 15 实习一 需求分析： 【问题描述】：设计一个一元稀疏多项式简单计算器。 【基本要求】：（1）输入并建立两个多项式； （2）多项式a与b相加，建立和多项式c； （3）多项式a与b相减，建立和多项式d； （4）输出多项式a,b,c,d。输出格式：比如多项式a为： ，其中，和分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤＜＜…＜。 【开发环境】： 系统：windows7 编程软件：VC++6.0 2.设计： 在数学上，一个n次一元多项式可表示为 =+++…+ 它由(n+1)个系数序列、、…、唯一确定。 因此，在计算机中，可用一个线性表P表示： P=(,,…,) 其中，代表中的i次项系数。 一般情况下，一元n次多项式写成： 其中，0≤＜＜…＜且,, 记作线性表P=（(,),(,)…()） 其中，元素为二元组（系数，指数） 多项式的单链表示意图: 图示分别为多项式 A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8 两个多项式相加运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复制到“和多项式”中。 两个多项式相减运算规则：两个多项式中所有指数相同的项对应系数相减，若差不为零，则构成“减多项式”中的一项；对于指数不同的项，A中项复制到“减多项式”中，B中各项符号变化（原来为“+”的项符号变为“-”；为“-”的项符号变为“+”）复制到“减多项式”中。 模块图： 具体思想： 设p和q分别指示多项式A和B中某一结点， 当p和q均非空时，比较p-exp与q-exp： 若p-exp q-exp，加法则p所指结点是“和多项式”中的一项，令指 针p后移；减法则p所指结点是“减多项式”中的一项，令指针p后移。 若p-expq-exp， 加法则q所指结点是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；减法则将q-coef=-q-coef,将q其插入结点p之前，且令指针q在原来的链表上后移。 若p-exp==q-exp， 加法则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。减法则将两个结点中的系数相减，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。 if (q==null) A即为“和多项式”结果（加法）；A即为“减多项式”结果（减法）。 if (p==null)（加法）将剩余的q表全部链接至原A最后一个结点的后继；（减法）将剩余的q并且令q-coef=-q-coef全部链接至原A最后一个结点的后继。 其中结点结构体定义如下： typedef struct Linklistomial{ float coef; int expn; struct Linklistomial *next; }*Linklist; 建立链表函数如下： void Insert(Linklist p,Linklist h){ if(p-coef==0) free(p);//系数为0的话释放结点 else { Linklist q1,q2; q1=h; q2=h-next; while(q2p-expnq2-expn) { //查找插入位置 q1=q2; q2=q2-next; } if(q2p-expn==q2-expn) { //将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) {//系数为0的话释放结点 q1-next=q2-next; free(q2); } } else { //指数为新时将结点插入 p-next=q2; q1-next=p; } } } Linklist CreateLinklist(Linklist head,int m){ //建立一个头指针为head、项数为m的一元多项式 int i; Linklist p; head=(Linklist)malloc(sizeof(struct Linklistomial)); head-next=NULL;