徐长稳2013508058一元稀疏多项式计算器.doc

信息科学与技术学院 《数据结构》课程设计报告 题目名称： 一元稀疏多项式计算器 完成日期：2014-12 目 录 一、需求分析 2 （1）问题描述 2 （2）基本要求 2 二、概要设计 2 （1）多项式的输入与存储 3 （2）多项式数据链表结点的定义 3 （3）. 本程序包含六个模块 3 三、详细设计 4 （1） 创建链表 5 （2） 减法时多项式的建立 6 （3）输出 8 （4）多项式相加减 8 （5）主函数 10 四、调试分析 12 五、用户手册 12 六、测试结果 13 （1）输入： 13 （2）输出： 13 七、总结 13 一、需求分析 （1）问题描述 设计一个一元稀疏多项式简单计算器。 （2）基本要求 一元稀疏多项式简单计算器的基本功能是(1) 输入并建立多项式 ； (2) 输出多项式，输出形式为整数序列n，l，el，c2，，…，cn，其中n是多项式的项数，ci 和e，分别是第 i 项的系数和指数，序列按指数降序排列； (3) 多项式和b相加，建立多项式 +b； (4) 多项式a和b相减，建立多项式 -b 。 【测试数据】 (1)(2+5x8－3.1x11) + (7－5x8+11x9)=(－3.lx11+11x9+2x+7) (2)(6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15) =(-7.8x15-1.2x9+12x-3-x) (3)(1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5) (4)(x+x3)+(-x－x3)=0 (5)(x+x100)+(x100 +x200)=(x+2x100+x200) (6)(x+x2+x3)+0=x+x2+x3 二、概要设计 根据一元多项式的相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则作“和多项式”中的一项插入到“和多项式”链表中去；对于两个一元多项式中指数不同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式的链表中摘取。 定义线性表 typedef int ElemType; （1）多项式的输入与存储 用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数），可对应建立链表的一个结点。建立两个链表，并将结果保存在其中一条链表中。 （2）多项式数据链表结点的定义 ?struct LNode *next; } LNode,*LinkList; （3）. 本程序包含六个模块 1) 主程序模块 void main() { 初始化： 输入三创建两个链表，分别存放多项式1和多项式2，然后逐个输入各项通过比较找到第一个大于该输入项指数的项将输入项插到此项的前面这样既可保证多项式链表的有序性 ②多项式相加或相减，下面给出多项式相加的部分实现 /* （3）指针p所指结点的指数值大于指针q所指的结点的指数值，则应当摘取q所指结点插入到“和多项式”链表中。 最后，当有一个多项式链表为空时，则将另一个非空多项式的剩余段直接链在“和多项式”的链表后面。 */ （1） 创建链表 void InitList(LinkList q) { q=(LNode*)malloc(sizeof(struct LNode)); q-next=NULL;//建立一个带节点的单链表 } 加法时的多项式的建立 LinkList InsertList(LinkList L) { LinkList p;//生成一个新结点 while(L-next==NULL) { p=(LNode*)malloc(sizeof(struct LNode)); printf(\n输入各项系数和指数（系数，指数）输入0，0为结束: ); scanf(%f,%d,p-coef,p-exp); p-next=L-next;//运用前插法将新结点插入到头结点后面 L-next=p; } Do { p=(LNode*)malloc(sizeof(struct LNode)); printf(\n输入各项系数和指数（系数，指数）输入0，0为结束: ); scanf(%f,%d,p-coef,p-exp); LinkList r=L,q=L-next;//定义r用于保存L的前驱，初值为头结点 while (q!=NULL) {//通过比较指数找到第一个大于输入项指数的项p if(p-expq-exp) { p-next=q; r-next=p; break; } else if(p-exp==q-exp) {//如果两个指数相等，则归并两个有序表 q