数据结构课程设计报告一元多项式的计算

I数据结构课程设计报告题目：一元多项式计算院（系）：计算机与信息科学学院专业：软件工程班级：软件1202班学号：020540姓名：陈潇潇刘敏易庆鹏指导教师：彭代文2013年12月2目录一、课程设计介绍........................错误!未定义书签。1.1课程设计目的.........................................31.2课程设计内容.........................................31.2课程设计要求.........................................3二、需求设计............................错误!未定义书签。2.1课设题目粗略分析.....................................32.2原理图介绍...........................错误!未定义书签。2.2.1功能模块图.......................错误!未定义书签。2.2.2流程图分析.......................................4三、需求分析.............................错误!未定义书签。3.1存储结构.............................................53.2算法描述.............................................6四、调试与分析...........................错误!未定义书签。（1）调试过程...........................错误!未定义书签。（2）程序执行过程.......................错误!未定义书签。参考文献.................................错误!未定义书签。总结.....................................错误!未定义书签。附录（关键部分程序清单）...............错误!未定义书签。3一、课程设计介绍1.1课程设计目的⑴熟悉使用c语言编码程序，解决实际问题；⑵了解数据结构与算法的设计方法，具备初步的独立分析和设计能力。⑶初步掌握软件开发过程的分析能力，系统设计，程序编码，测试等基本能力。⑷提高综合运用的能力，运用所学理论知识与独立分析能力。1.2课程设计内容一元多项式计算任务：⑴能够按照指数降序排列建立并输出多项式⑵能够完成两个多项式的相加，并将结果输入⑶在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法1.3课程设计要求⑴学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。⑵学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。⑶课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。⑷课程设计在期末考试之前交。最好一起上交。⑸同班同学之间最好不要相同。源代码可以打印，但是下面模块要求的内容必须手写。二、需求设计2.1课设题目粗略分析建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果42.2流程图分析1、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入图表12、多项式的加法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）程序流程图：多项式的加法流程图如图2所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。图表1开始申请结点空间+++++++++++++++++++++++++++++++++++++++++++++++++++++++输入多项式的项数输入多项式各项的系数x,指数y输出已输入的多项式合并同类项结束否是是否输入正确5三、需求分析3.1存储结构一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。开始定义存储结果的空链r是否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项63.2算法描述#includestdio.h#includemalloc.htypedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;//Polyn为结点指针类型voidInsert(Polynp,Polynh){if(p-coef==0)free(p);//系数为0的话释放结点else{Polynq1,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;}7}}//InsertPolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head-next=NULL;for(i=0;im;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据printf(请输入第%d项的系数与指数:,i+1);scanf(%f%d,&p-coef,&p-expn);Insert(p,head);//调用Insert函数插入结点}returnhead;}//CreatePolynvoidDestroyPolyn(Polynp){//销毁多项式pPolynq1,q2;q1=p-next;q2=q1-next;while(q1-next){free(q1);q1=q2;//指针后移q2=q2-next;}}voidPrintPolyn(PolynP){Polynq=P-next;8intflag=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);9}//PrintPolynintcompare(Polyna,Polynb){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多项式非空}//comparePolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynqa=pa-next;Polynqb=pb-next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc-next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;}case0:10{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){qc-next=hc-next;hc-next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynh=pb;Polynp=pb-next;Polynpd;11while(p){//将pb的系数取反p-coef*=-1;p=p-next;}pd=AddPolyn(pa,h);for(p=h-next;p;p=p-next)//恢复pb的系数p-coef*=-1;returnpd;}//SubtractPolynintmain(){intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULLprintf(请输入a的项数:);scanf(%d,&m);pa=CreatePolyn(pa,m);//建立多项式aprintf(请输入b的项数:);scanf(%d,&n);pb=CreatePolyn(pb,n);//建立多项式a//输出菜单printf(**********************************************\n);printf(操作提示：\n\t1.输出多项式a和b\n\t2.建立多项式a+b\n\t3.建立多项式a-b\n);printf(\t4.退出\n**********************************************\n);for(;;flag=0){printf(执行操作：);scanf(%d,&flag)