数据结构课程设计-一元稀疏多项式简单计数器

数据结构课程设计1数据结构课程设计说明书题目：一元稀疏多项式简单计数器学生姓名：学号：院（系）：理学院专业：数学与应用数学指导教师：张洲平2011年12月23日一元稀疏多项式简单计数器2陕西科技大学数据结构课程设计任务书理学院数学与应用数学专业班级学生：题目：一元稀疏多项式简单计数器课程设计从2011年12月19日起到2011年12月23日1、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）：一元稀疏多项式简单计数器（1）输入并建立多项式（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。用带头结点的单链表存储多项式。数据结构课程设计32、对课程设计成果的要求〔包括图表、实物等硬件要求〕：1）根据课程设计题目要求编写所需程序代码要求可以实现多项式的建立，以及两个多项式的相加、减，并且输出相加、减后所得的结果，同时用手算也可验证实验结果是否符合要求。2）提交课程设计报告按照具体要求完成课程设计报告，其中包括问题的描述、算法思想、程序实现结果、数据验证和实验总结等部分。3、课程设计工作进度计划：时间设计任务及要求1-10搜集学习相关资料，明确实验要求、目的1-11分析课题，理清编程思路1-12编写程序，修改程序1-13代入数据，进行整体调试，运行，再修改1-14性能分析，撰写设计说明书指导教师：日期：2011-11-15教研室主任：日期：一元稀疏多项式简单计数器4目录一、问题描述…………………………………………………………………………1二、算法思想…………………………………………………………………………2三、数据结构…………………………………………………………………………3四、设计模块划分……………………………………………………………………4五、源程序……………………………………………………………………………5六、算法分析…………………………………………………………………………10七、运行结果…………………………………………………………………………11八、设计总结与体会…………………………………………………………………13参考文献……………………………………………………………………………14数据结构课程设计51.问题描述：一元稀疏多项式简单计数器基本要求：（1）输入并建立多项式（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。用带头结点的单链表存储多项式。测试数据：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)一元稀疏多项式简单计数器62.算法思想：（1）建立多项式一元多项式是由多个项的和组成的，将一元多项式的每个项用一结点表示，该结点中应包括该项的系数、该项的指数、指向下一项的指针，可以用线性表来依次输入各项结点，从而完成多项式链表的建立，为了使原多项式各项顺序不变，故采用尾插法建表。（2）降幂输出多项式我们可以先设一个幂指数i为可输入的最大幂指数，然后从首元结点开始顺次查询每一结点的指数和i，若相等则输出该结点，否则，i--,继续从首元结点开始查询，重复上述过程，直到i为可输入的最小幂指数。这样，就按指数降幂输出了多项式。多项式的项数统计可以通过头结点的next来实现，若非空，count++,直到结点的指针域为空，这样，count就统计出了项数。（3）多项式相加多项式的相加过程，其实就是相同指数的项的系数相加，不同指数的项复制到和多项式中，将结果用降幂输出函数输出。（4）多项式相减多项式的相减过程，其实就是相同指数的项的系数相减，对于不同指数的项，若是被减多项式，则将该结点复制输出，若是减多项式，则将该结点的系数变为原系数的相反数输出，将结果用降幂输出函数输出。数据结构课程设计73.数据结构：带头结点单链表抽象数据类型的结点结构定义如下：typedefstructPolynode//多项式结点{intcoef;//系数intexp;//指数Polynode*next;}Polynode,*Polylist;一元稀疏多项式简单计数器84.模块划分：(1)带头结点的多项式的建立函数PolylistPolycreate()(2)带头结点的多项式的降幂输出函数voidprintf(Polylistpoly)(3)带头结点的多项式的相加函数PolylistPolyadd(Polylista,Polylistb)(4)带头结点的多项式的相减函数PolylistPolysub(Polylista,Polylistb)(5)主函数voidmain()数据结构课程设计95.源程序：#includestdio.h#includemalloc.htypedefstructPolyomial{floatcoef;intexpn;structPolyomial*next;}*Poly,Polyomial;//Poly为结点指针类型voidInsert(Polyp,Polyh){if(p-coef==0)free(p);//系数为0时释放结点else{Polyq1,q2;q1=h;q2=h-next;while(q2&&p-expnq2-expn){//查找插入位置q1=q2;q2=q2-next;}if(q2&&p-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;}}}//InsertPolyCreatePoly(Polyhead,intm){//建立一个头指针为head、项数为m的一元多项式inti;Polyp;p=head=(Poly)malloc(sizeof(structPolyomial));head-next=NULL;for(i=0;im;i++){p=(Poly)malloc(sizeof(structPolyomial));//建立新结点以接收数据printf(输入第%d项的系数与指数:,i+1);scanf(%f%d,&p-coef,&p-expn);Insert(p,head);//调用Insert函数插入结点一元稀疏多项式简单计数器10}returnhead;}//CreatePolyvoidDestroyPoly(Polyp){//销毁多项式pPolyq1,q2;q1=p-next;q2=q1-next;while(q1-next){free(q1);q1=q2;//指针后移q2=q2-next;}}voidPrintPoly(PolyP){Polyq=P-next;intflag=1;//项数计数器if(!q){//若多项式为空，输出0putchar('0');printf(\n);return;}while(q){if(q-coef0&&flag!=1)putchar('+');//系数大于0且不是第一项if(q-coef!=1&&q-coef!=-1){//系数非1或-1的普通情况printf(%g,q-coef);if(q-expn==1)putchar('X');elseif(q-expn)printf(X^%d,q-expn);}else{if(q-coef==1){if(!q-expn)putchar('1');elseif(q-expn==1)putchar('X');elseprintf(X^%d,q-expn);}if(q-coef==-1){if(!q-expn)printf(-1);elseif(q-expn==1)printf(-X);elseprintf(-X^%d,q-expn);}}q=q-next;flag++;}//whileprintf(\n);数据结构课程设计11}//PrintPolyintcompare(Polya,Polyb){if(a&&b){if(!b||a-expnb-expn)return1;elseif(!a||a-expnb-expn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}//comparePolyAddPoly(Polypa,Polypb){//求解并建立多项式a+b，返回其头指针Polyqa=pa-next;Polyqb=pb-next;Polyheadc,hc,qc;hc=(Poly)malloc(sizeof(structPolyomial));//建立头结点hc-next=NULL;headc=hc;while(qa||qb){qc=(Poly)malloc(sizeof(structPolyomial));switch(compare(qa,qb)){case1:{qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;}case0:{qc-coef=qa-coef+qb-coef;qc-expn=qa-expn;qa=qa-next;qb=qb-next;break;}case-1:{qc-coef=qb-coef;qc-expn=qb-expn;qb=qb-next;break;}}//switchif(qc-coef!=0){一元稀疏多项式简单计数器12qc-next=hc-next;hc-next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}//whilereturnheadc;}//AddPolyPolySubtractPoly(Polypa,Polypb){//求解并建立多项式a+b，返回其头指针Polyh=pb;Polyp=pb-next;Polypd;while(p){//将pb的系数取反p-coef*=-1;p=p-next;}pd=AddPoly(pa,h);for(p=h-next;p;p=p-next)//恢复pb的系数p-coef*=-1;returnpd;}//SubtractPolyintmain(){intm,n,flag=0;floatx;Polypa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULLprintf(输入a的项数:);scanf(%d,&m);pa=CreatePoly(pa,m);//建立多项式aprintf(输入b的项数:);scanf(%d,&n);pb=CreatePoly(pb,n);//建立多项式bfor(;;flag=0){printf(执行操作);scanf(%d,&flag);if(flag==1){printf(多项式a：);PrintPoly(pa);printf(多项式b：);PrintPoly(pb);continue;}if(flag==2){pc=AddPoly(pa,pb);printf(多项式a+b：);PrintPoly(pc);DestroyPoly(pc);continue;数据结构课程设计13