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

数据结构实习报告 题目：一元稀疏多项式计算器 运行环境：mingwstudio一 需求分析1. 输入的形式和输入值范围：本程序只需进行一元稀疏多项式的加减（选做乘法），所以只需根据指示输入一元稀疏多项式的各项系数与指数，多项式的项数，通过scanf语句实现。系数范围为浮点型数据范围，指数范围为无符号型整型，项数范围为有符号整型。2. 输出的形式：用户根据计算机指示输入系数与指数，通过printf语句实现，计算机在程序运行后输出结果。3. 程序所能达到的功能: (1).输入并建立多项式。(2).输出多项式，输出形式为整数序列n,c1,e1,c2,e2cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序数按指数降序排列；（3）.多项式a和b相加，建立多项式a+b; (4).多项式a和b相减，建立多项式a-b;即输入输出多项式，求和并输出结果，求差并输出结果 (5)补充部分：多项式相乘；多项式求导；多项式求值4. 测试数据：（1）（2x5x83.1x11）（75x811x9）（-3.1x1111x92x7）（2）（6x-3x4.4x21.2x9）（-6x-35.4x2x27.8x15）(-7.8x151.2x912x-3x)（3）（1xx2x3x4x5）（x3x4）（1xx2x5）（4）（xx3）（xx3）0（5）（xx100）+(x100+x200)=(x+2x100+x200)（6）（xx2x3）0xx2x3（7）互换上述测试数据中的前后两个多项式 二 概要设计:1. 抽象数据类型的定义：adt polynomial 数据对象：d=ai|aitermset,i=1,2,m, m0 termset中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系：r1= ai-1, aid,且ai-1中的指数值ai中的指数值，i=1,2, , 基本操作： create(name *pname) 操作结果：建立一元多项式 printpoly(name *pname) 初始条件：一元多项式已经存在操作结果：输出一元多项式plus(name *pname)初始条件：一元多项式已经存在操作结果：完成多项式的相加运算 minus(name *pname)初始条件：一元多项式已经存在操作结果：完成多项式的相减运算delete(name *pname)初始条件：一元多项式已经存在操作结果：在多项式名链表中删除该多项式qiuzhi(name *pname)初始条件：一元多项式已经存在操作结果：求多项式某点的值daoshu(name *pname)初始条件：一元多项式已经存在操作结果：求多项式的导数multiply(name *pname)初始条件：一元多项式已经存在操作结果：多项式相乘 adt polynomial2. 主程序流程：本程序包括2个模块：（1）主程序模块：status main( ) 初始化；switch ( ) case 1：接受命令； 处理命令；break; case 2：接受命令； 处理命令；break; case 3：接受命令； 处理命令；break; . （2）一元多项式类型模块实现一元多项式的抽象数据类型；3. 各个模块之间调用关系如下： 主程序模块 一元多项式类型模块a.因为这是一个计算器，所以需要能够连续进行各项功能，不能进行了一个功能之后，程序就自动关闭了。所以需要设计一个循环，在每进行完一个功能之后，都能显示一串功能供用户选择。这是该计算器的框架，最外层的结构，按照自上而下，逐步求精的方法设计该计算器。另外，为了减小主函数的长度，将供用户选择的这部分用一个函数choose来实现，返回所要操作的代号。而在主函数中，用switchcase语句来转换到各个功能函数。加法函数plus，减法函数minus，乘法函数multiply，创建函数create，删除函数delete，求值函数qiuzhi，求导函数daoshu. b接下来就是编写各个功能函数了。首先要考虑的问题是，这些多项式是否要保存，怎样保存的问题。为了能够保存这些多项式，我们把这些多项式保存在一个链表中，构成一个多项式名链表ps，链表具有头结点。链表的每一个结点为typedef struct namechar sn;/s用于保存多项式名struct node *point;/指向多项式struct name *next;/指向下一多项式名结点name;每次创建一个多项式则采用头插法保存在链表ps的头部，为了节省执行时间。c多项式的结点则为：typedef struct nodeint ee;/指数double cc;/系数struct node *next;/指向下一结点的指针node;d.创建多项式只需要将每一项加到多项式链表中即可。需要考虑的问题是：如果新创建多项式的多项式名与原先已有的多项式名有冲突的话，能够提示。因此设计了一个do while循环。以后的所有需要创建多项式的函数都采用这一结构提示是否有冲突。e.多项式相加的函数因为要先输入两个多项式，如果不小心输入的多项式名在已创建的多项式中不存在的话，程序就会终止了，为了克服这一bug，有必要设计一个结构。仍采用dowhile结构，这一结构有两重作用，一是提示出错，二是找到这两个多项式的位置。分别用两个指针p0,p1指向他们。在多项式相减，相乘也采用这一结构。f.多项式相乘，用两个for循环，将每一个相乘得到的项插入到多项式链中。将指数相同的项直接把系数相加，指数不同的插入一个新的结点在表头。g.求导求值均是先找到该多项式，在进行操作。三 详细设计：1.元素类型、系数、指数、结点类型和指针类型：typedef struct nodeint ee;/指数double cc;/系数struct node *next;/指向下一结点的指针node;typedef struct namechar sn; /存放多项式名 struct node *point;/指向多项式struct name *next;/指向下一多项式名name;2.主函数的源码：int main()int select=1;/count用于统计多项式名的个数name *ps;/ps为多项式名链表ps=(name *)malloc(sizeof(name);ps-next=null;strcpy(ps-s,);/头结点多项式名置为空printf(请创建多项式：n);create(ps);/创建多项式while(select!=9)select=choose();switch (select)case 1:create(ps);break;case 2:plus(ps);break;case 3:minus(ps);break;case 4:multiply(ps);break;case 5:qiuzhi(ps);break;case 6:daoshu(ps);break;case 7:delete(ps);break;default:exit(0);/switch/while4.一元多项式类型模块源码：void printpoly(name *pname)/输出所有的多项式name *p;node *a;printf(n已创建的所有多项式为：);for(p=pname-next;p;p=p-next)printf(n%s ,p-s);/输出多项式名for(a=p-point;a;a=a-next)if(a-cc=1&a-ee=1) printf( x);else if(a-cc=0) printf( 0);else if(a-ee=0) printf( %6.4lf,a-cc);else if(a-ee=1) printf( %6.4lfx,a-cc);else if(a-cc=1) printf( x%d,a-ee);else printf( %6.4lfx%d,a-cc,a-ee);void create(name *pname)/创建多项式name *p,*q;node *a,*b;char sn;int i,tag=0,number;printf(请输入要创建的多项式名（15个字母以下的英文或数字字符串，如a,bc）：);p=(name *)malloc(sizeof(name);p-next=pname-next;/链成多项式链pname-next=p;scanf(%s,s);/输入多项式名dotag=0;for(q=pname-next;q;q=q-next)if(strcmp(q-s,s)=0)printf(多项式名有冲突，请重新输入:);scanf(%s,s);tag=1;break;while(tag=1);/考虑多项式名重复情况strcpy(p-s,s);printf(请输入多项式的项数（输入数字）：);scanf(%d,&number);printf(请输入多项式的系数和指数（如3x2+4x就输入3 2 4 1）：);a=(node *)malloc(sizeof(node);p-point=a;/多项式名节点指向多项式链scanf(%lf %d,&a-cc,&a-ee);a-next=null;for(i=1;icc,&b-ee);a-next=b;b-next=null;a=b;/forprintpoly(pname);/输出所有的多项式void plus(name *pname)/多项式相加char s2n,s2n;name *p2,*q;node *pp,*qq,*rr,*ss;int tag,i;printpoly(pname);/输出所有多项式printf(n请输入所要相加的两个多项式名（如：a bc）：);dotag=0;scanf(%s%s,s0,s1);/读入两个多项式for(i=0;inext;pi;pi=pi-next)if(strcmp(pi-s,si)=0) break;if(pi=null)tag=1;printf(多项式%s不存在,请重新输入两个多项式名：,si);break;while(tag=1);/考虑输入不存在的情况printf(请指定相加后生成的多项式名（如：bc）：);scanf(%s,s2);dotag=0;for(q=pname-next;q;q=q-next)if(strcmp(q-s,s2)=0) printf(多项式名与已有多项式冲突，请重新输入：);scanf(%s,s2);tag=1;break;while(tag=1);/考虑多项式名重复情况q=(name *)malloc(sizeof(name);strcpy(q-s,s2);q-next=pname-next;pname-next=q;/头插法q-point=(node *)malloc(sizeof(node);qq=q-point;pp=p0-point;qq-cc=pp-cc;qq-ee=pp-ee;for(pp=pp-next;pp;pp=pp-next)qq-next=(node *)malloc(sizeof(node);qq=qq-next;qq-cc=pp-cc;qq-ee=pp-ee;qq-next=null;/将s0链拷贝到加法链中for(pp=p1-point;pp;pp=pp-next)for(qq=q-point;qq&qq-ee!=pp-ee;qq=qq-next);/查找指数是否一样if(qq=null)/指数不一样rr=(node *)malloc(sizeof(node);rr-cc=pp-cc;rr-ee=pp-ee;rr-next=q-point;q-point=rr;/头部插入else /指数一样qq-cc=qq-cc+pp-cc;/直接把系数相加if(q-point-cc=0)rr=q-point;q-point=rr-next;free(rr);/如果q-point的结点系数为零，释放该结点for(rr=q-point-next;rr;rr=rr-next)if(rr-cc=0)for(ss=q-point;ss-next!=rr;ss=ss-next);/查找rr前一个结点ss-next=rr-next;free(rr);/把其他系数为零的结点释放printpoly(pname);/输出所有的多项式void delete(name *pname)name *pre,*p;node *ppre,*pp;int tag;char sn;printf(n请输入要销毁的多项式名（如：bc）：);dotag=0;scanf(%s,s);for(p=pname-next;p;p=p-next)if(strcmp(p-s,s)=0) break;if(p=null)tag=1;printf(该多项式不存在，请重新输入一个已有的多项式名：);while(tag=1);/考虑要删除的多项式不存在的情况for(pre=pname;pre-next!=p⪯pre=pre-next);/寻找p的前一个节点pre-next=p-next;/在多项式名链表中删除该多项式pp=p-point;while(pp)ppre=pp;pp=ppre-next;free(ppre);/释放该多项式的各个节点free(p);printpoly(pname);/输出所有的多项式void minus(name *pname)/多项式相减char s2n,s2n;name *p2,*q;node *pp,*qq,*rr,*ss;int tag,i;printpoly(pname);/输出所有多项式printf(n请输入所要相减的两个多项式名（前者减后者）（如：a bc）：);dotag=0;scanf(%s%s,s0,s1);/读入两个多项式for(i=0;inext;pi;pi=pi-next)if(strcmp(pi-s,si)=0) break;if(pi=null)tag=1;printf(多项式%s不存在,请重新输入两个多项式名：,si);break;while(tag=1);/考虑输入不存在的情况printf(请指定相加后生成的多项式名（如：aa）：);scanf(%s,s2);dotag=0;for(q=pname-next;q;q=q-next)if(strcmp(q-s,s2)=0) printf(该多项式名与已有多项式冲突，请重新输入一个多项式名：);scanf(%s,s2);tag=1;break;while(tag=1);/考虑多项式名重复情况q=(name *)malloc(sizeof(name);strcpy(q-s,s2);q-next=pname-next;pname-next=q;/头插法q-point=(node *)malloc(sizeof(node);qq=q-point;pp=p0-point;qq-cc=pp-cc;qq-ee=pp-ee;for(pp=pp-next;pp;pp=pp-next)qq-next=(node *)malloc(sizeof(node);qq=qq-next;qq-cc=pp-cc;qq-ee=pp-ee;qq-next=null;/将s0链拷贝到减法链中for(pp=p1-point;pp;pp=pp-next)for(qq=q-point;qq&qq-ee!=pp-ee;qq=qq-next);/查找指数是否一样if(qq=null)/指数不一样rr=(node *)malloc(sizeof(node);rr-cc=0-pp-cc;rr-ee=pp-ee;rr-next=q-point;q-point=rr;/头部插入else/指数一样qq-cc=qq-cc-pp-cc;if(q-point-cc=0)rr=q-point;q-point=rr-next;free(rr);for(rr=q-point-next;rr;rr=rr-next)if(rr-cc=0)for(ss=q-point;ss-next!=rr;ss=ss-next);/查找qq前一个结点ss-next=rr-next;free(rr);/把系数为零的节点释放printpoly(pname);/输出所有的多项式void qiuzhi(name *pname)/求多项式某点的值name *p;node *pp;int tag;double x,sum=0;char sn;printf(n请输入所要求值的多项式名：);dotag=0;scanf(%s,s);for(p=pname-next;p;p=p-next)if(strcmp(p-s,s)=0) break;if(p=null)tag=1;printf(该多项式不存在，请重新输入一个多项式名：);while(tag=1);printf(请输入一个x值：);scanf(%lf,&x);for(pp=p-point;pp;pp=pp-next)sum=sum+(pp-cc)*pow(x,pp-ee);printf(多项式%s在%2.1lf处的值为 %8.4lf,s,x,sum);printpoly(pname);/输出所有的多项式void daoshu(name *pname)/求多项式的导数name *p,*q;node *pp,*ppre,*qq;int tag;char sn,s2n;printf(请输入所要求导数的多项式名（如：aa）：);dotag=0;scanf(%s,s);for(p=pname-next;p;p=p-next)if(strcmp(p-s,s)=0) break;if(p=null)tag=1;printf(该多项式不存在，请重新输入一个多项式名（如：aa）：);while(tag=1);printf(请输入求导后的多项式名（如：aa）：);scanf(%s,s2);dotag=0;for(q=pname-next;q;q=q-next)if(strcmp(q-s,s2)=0)printf(该多项式名与已有多项式冲突，请重新输入一个多项式名：);scanf(%s,s2);tag=1;break;while(tag=1);/考虑多项式名重复情况q=(name *)malloc(sizeof(name);strcpy(q-s,s2);q-next=pname-next;pname-next=q;/头插法q-point=(node *)malloc(sizeof(node);qq=q-point;pp=p-point;qq-cc=pp-cc*pp-ee;qq-ee=pp-ee-1;for(pp=pp-next;pp;pp=pp-next)qq-next=(node *)malloc(sizeof(node);qq=qq-next;qq-cc=pp-cc*pp-ee;qq-ee=pp-ee-1;qq-next=null;/pp=q-point;while(pp)if(pp-cc=0)ppre-next=pp-next;free(pp);break;ppre=pp;pp=pp-next;/删去系数为零的结点printpoly(pname);/输出所有的多项式void multiply(name *pname)/多项式相乘name *p2,*q,*mul;node *pp,*qq,*rr,*ss;int tag,i,b;char s2n,s2n;double a;printpoly(pname);/输出所有多项式printf(n请输入所要相乘的两个多项式名(形如：a b)：);dotag=0;scanf(%s%s,s0,s1);/读入两个多项式for(i=0;inext;pi;pi=pi-next)if(strcmp(pi-s,si)=0) break;if(pi=null)tag=1;printf(多项式%s不存在,请重新输入两个多项式名：,si);break;while(tag=1);/考虑输入不存在的情况printf(请输入相乘后的多项式名：);scanf(%s,s2);dotag=0;for(q=pname-next;q;q=q-next)if(strcmp(q-s,s2)=0)printf(该多项式名与已有多项式冲突，请重新输入一个多项式名：);scanf(%s,s2);tag=1;break;while(tag=1);/考虑多项式名重复情况mul=(name *)malloc(sizeof(name);strcpy(mul-s,s2);/将多项式名拷贝进入mul-next=pname-next;pname-next=mul;/头插法插入多项式名链mul-point=(node *)malloc(sizeof(node);mul-point-next=null;mul-point-cc=0;mul-point-ee=0;for(pp=p1-point;pp;pp=pp-next)for(qq=p0-point;qq;qq=qq-next)a=qq-cc*pp-cc;b=qq-ee+pp-ee;/将后一个多项式的每一项与前一个多项式的每个多项式相乘for(rr=mul-point;rr&rr-ee!=b;rr=rr-next);if(rr=null)rr=(node *)malloc(sizeof(node);rr-next=mul-point;mul-point=rr;rr-cc=a;rr-ee=b;elserr-cc+=a;/将每次得到的项累加到