2012数据结构课程设计

PAGEPAGE2数据结构课程设计报告题目：一元多项式计算专业：信息管理与信息系统班级：2012级普本班学号：201201011367姓名：左帅帅指导老师：郝慎学时间：一、课程设计题目分析本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。二、设计思路 本程序采用C语言来完成课程设计。1、首先，利用顺序存储结构来构造两个存储多项式A(x)和B(x)的结构。2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。设计算法分析1、相关函数说明：(1)定义数据结构类型为线性表的链式存储结构类型变量typedefstructPolynomial{}(2)其他功能函数插入函数voidInsert(Polynp,Polynh)比较函数intcompare(Polyna,Polynb)建立一元多项式函数PolynCreate(Polynhead,intm)求解并建立多项式a+b，PolynAdd(Polynpa,Polynpb)求解并建立多项式a-b，PolynSubtract(Polynpa,Polynpb)求解并建立多项式a*b，PolynMultiply(Polynpa,Polynpb)求解并建立多项式a/b，voidDevice(Polynpa,Polynpb)输出函数输出多项式，voidPrint(PolynP)销毁多项式函数释放内存，voidDestroy(Polynp)主函数，voidmain（）2、主程序的流程基函数调用说明

(1)typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。(2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下：PolynCreatePolyn(Polynhead,intm)建立一个头指针为head、项数为m的一元多项式p=head=(Polyn)malloc(sizeof(structPolynomial));为输入的多项式申请足够的存储空间p=(Polyn)malloc(sizeof(structPolynomial));建立新结点以接收数据Insert(p,head);调用Insert函数插入结点这就建立一元多项式的关键步骤(3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void

Insert(Polyn

p,Polyn

h)进行插入操作。(4)加、减、乘、除、的算法实现：

在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。(5)另一个子函数是输出函数

PrintPolyn（）；输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。程序新点通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system("ColorE0");可以函数解决，这里“E0”，E是控制台背景颜色，0是控制台输出字体颜色。五、设计中遇到的问题及解决办法首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行代码编写。其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。六、测试（程序截图）1.数据输入及主菜单2.加法和减法模块3.乘法和除法模块七、总结 通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。八、指导老师评语及成绩附录：（课程设计代码）#include<stdio.h>#include<malloc.h>#include<stdlib.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)//查找插入位置{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;}//指数为新时将结点插入 }}//建立一个头指针为head、项数为m的一元多项式PolynCreate(Polynhead,intm){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;}//销毁多项式pvoidDestroy(Polynp){Polynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指针后移q2=q2->next;}}//输出多项式pintPrint(PolynP){Polynq=P->next;intflag=1;//项数计数器if(!q)//若多项式为空，输出0{putchar('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');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++;}printf("\n");}intcompare(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多项式非空}//求解并建立多项式a+b，返回其头指针PolynAdd(Polynpa,Polynpb){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: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;}if(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}returnheadc;}//求解并建立多项式a-b，返回其头指针PolynSubtract(Polynpa,Polynpb){Polynh=pb;Polynp=pb->next;Polynpd;while(p)//将pb的系数取反{p->coef*=-1;p=p->next;}pd=Add(pa,h);for(p=h->next;p;p=p->next)//恢复pb的系数p->coef*=-1;returnpd;}//求解并建立多项式a*b，返回其头指针PolynMultiply(Polynpa,Polynpb){Polynhf,pf;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hf->next=NULL;for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(Polyn)malloc(sizeof(structPolynomial));pf->coef=qa->coef*qb->coef;pf->expn=qa->expn+qb->expn;Insert(pf,hf);//调用Insert函数以合并指数相同的项}}returnhf;}//求解并建立多项式a/b，返回其头指针voidDevice(Polynpa,Polynpb){Polynhf,pf,temp1,temp2;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点,存储商hf->next=NULL;pf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点，存储余数pf->next=NULL;temp1=(Polyn)malloc(sizeof(structPolynomial));temp1->next=NULL;temp2=(Polyn)malloc(sizeof(structPolynomial));temp2->next=NULL;temp1=Add(temp1,pa);while(qa!=NULL&&qa->expn>=qb->expn){temp2->next=(Polyn)malloc(sizeof(structPolynomial));temp2->next->coef=(qa->coef)/(qb->coef);temp2->next->expn=(qa->expn)-(qb->expn);Insert(temp2->next,hf);pa=Subtract(pa,Multiply(pb,temp2));qa=pa->next;temp2->next=NULL;}pf=Subtract(temp1,Multiply(hf,pb));pb=temp1;printf("商是:");Print(hf);printf("余数是:");Print(pf);}voidmain(){intchoose=1;intm,n,flag=0;system("ColorE0");Polynpa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULLprintf("请输入A(x)的项数:");scanf("%d",&m);printf("\n");pa=Create(pa,m);//建立多项式Aprintf("\n");printf("请输入B(x)的项数:");scanf("%d",&n);printf("\n");pb=Create(pb,n);//建立多项式Bprintf("\n");printf("**********************************************\n");printf("*多项式操作菜单*\n");printf("**********************************************\n");printf("\t\t