课程设计 一元稀疏多项式简单计数器

.绪论1.1前言计算机是随着社会的发展应运而生，它贯穿了人们生活的方方面面。其中，在科学计算方面，由于算法的高精确和高复杂度，对于计算机的依赖不可言喻。在这里，我设计了一个一元稀疏多项式简单计数器，科学计算算不上，但作为学习性的实践，对自己却很重要。当前计算机软件技术和网络技术飞速发展，软件系统日趋大型化、复杂化。因此社会对软件开发者日出了比以往更高的要求。相应的系统要求也有了很大的提高。本系统用C语言作为程序语言，设计出的系统功能完善，操作方便灵活。1.2问题的提出一元稀疏多项式简单计数器基本功能要求：(1)输入并建立多项式(2)输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。(3)多项式a和b相加，建立多项式a+b，输出相加的多项式。(4)多项式a和b相减，建立多项式a-b，输出相减的多项式。用带表头结点的单链表存储多项式。学院课程设计（论文）课程设计目的2.课程设计目的使我们进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。使我们掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。使我们掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。熟练掌握数据结构这门课程，掌握线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用。进一步熟悉抽象数据类型的定义和实现、如何利用数组的动态分酚实现顺序结构、继承的实现方式。学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、想念结构及基相应的算法并初步掌握算法的时间分析和空间分析的技术。基本掌握程序设计的基本思路和方法。利用所学的基本知识和技能，解决简单的程序设计问题各算法描述培养我们的数据抽象能力。学院课程设计（论文）需求分析3.需求分析3.1功能分析本程序要求输入并建立多项式，能够降幂显示出多项式，实现多项式相加相减的计算问题，输出结果。3.2设计思路采用链表的方式存储链表，定义结点结构体。运用尾差法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b。为实现处理，社p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项。①若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。②若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。③若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。学院课程设计（论文）概要设计4.概要设计4.1数据结构的选用typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;4.2多项式的输入PolynCreatePolyn(Polynhead,intm){for(i=0;i<m;i++) {p=(Polyn)malloc(sizeof(structPolynomial));printf("请输入第%d项的系数与指数:",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head); }returnhead;}4.3主函数和其它函数voidmain(){intm,n,a,x; charflag;Polynpa=0,pb=0,pc;}voidDestroyPolyn(Polynp)voidPrintPolyn(PolynP)intcompare(Polyna,Polynb)PolynAddPolyn(Polynpa,Polynpb)PolynSubtractPolyn(Polynpa,Polynpb)学院课程设计（论文）流程图设计5.流程图设计5.1函数调用关系5.2程序流程图学院课程设计（论文）程序代码6.程序代码#include<stdio.h>#include<malloc.h>typedefstructPolynomial{//项的表示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->expn<q2->expn){//查找插入位置p与h项一次比较指数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->expn>q2expn情况p->next=q2;q1->next=p;}}}//InsertPolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;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);//释放q1q1=q2;//指针后移，循环继续释放，直至销毁q2=q2->next;}}voidPrintPolyn(PolynP){//输出多项式Polynq=P->next;intflag=1;//项数计数器if(!q){//若多项式为空，输出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况printf("%g",q->coef);if(q->expn==1)putchar('X');//系数为1的情况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");}//PrintPolynintcompare(Polyna,Polynb){if(a&&b){if(!b||a->expn>b->expn)return1;elseif(!a||a->expn<b->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)){//调用compare返回值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){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a-b，返回其头指针Polynh=pb;Polynp=pb->next;Polynpd;while(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\t4.退出\n");for(;;flag=0){printf("执行操作");scanf("%d",&flag);if(flag==1){//输出多项式printf("多项式a：");PrintPolyn(pa);printf("多项式b：");PrintPolyn(pb);continue;}if(flag==2){//多项式相加pc=AddPolyn(pa,pb);//调用函数，实现相加printf("多项式a+b：");PrintPolyn(pc);DestroyPolyn(pc);continue;}if(flag==3){//多项式相减pd=SubtractPolyn(pa,pb);printf("多项式a-b：");PrintPolyn(pd);DestroyPolyn(pd);continue;}if(flag==4)break;//结束循环，退出DestroyPolyn(pa);//销毁多项式，释放内存DestroyPolyn(pb);return0;}}学院课程设计（论文）调试运行7.调试运行7.1运行程序操作平台：硬件要求：PC机一台软件要求：windowsXP以上操作系统VC++软件7.2程序的载入7.3程序的编译7.4程序运行测试数据(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)学院课程设计（论文）总结8.总结这次课程设计是对数据结构掌握的一次很有分量的测试。确实自己在这次课程设计中认识到自己很多的不足。想了很多，思考了很多。对于知识的把握和编程的经验自己真的是差的太远。编程是个细致活。不温不火，不急不躁。在五天的编程过程中，这点深有体会。想法太成熟，笔快容易失误；知识太生疏，笔慢错误多。当然，不能强求不出现错误。在编程过程要善于发现程序中的错误，并且能很快地排除这些错误，使程序能正确运行。经验丰富的人在错误出现时，能很快的判断出错误的所在，并改之；经验少的人，则往往要花费大量的时间和气力。我相信老师说的，很多程序的编写都有灵感的参与，下次再次看自己程序的时候，也许不能很好的明白当初某些地方的初衷。因此，在编程中，在思想灵感爆发的时候，最好的做法就是在旁边写上注释。这次设计自己就走了很多弯路，程序一长，没有注释，整理调试的时候就很难快速找到问题所在。当然我不避讳自己知识的把握太差，反而应该更加惊醒。C语言虽然是最基础的语言，但是其价值性却不容忽视。简单的说，学会了C语言，很多语言的上手就显得很容易。当初对于C的学习确实有诸多的忽略，以为掌握了基本的语法过了二级就行。现在看来，C部分最精华最难的指针和结构体，指针和数组自己都掌握的一塌糊涂。这学期的数据结构课程又是C语言版的，在学习的过程中难免要咀嚼和回顾C知识。因此学起来其实不是很舒服的。很多知识点自己都是知其表而不懂其用。加之课程又紧，一知半解的半年过去了。