数据结构课程设计 一元稀疏多项式的计算.doc

《数据结构课程设计 一元稀疏多项式的计算.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、//头文件#include#include#include//定义多项式的项typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系数为0的话释放结点else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->expnexpn){//查找插入位置

2、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;}}}PolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(st

3、ructPolynomial));head->next=NULL;for(i=0;icoef,&p->expn);Insert(p,head);//调用Insert函数插入结点}returnhead;}voidDestroyPolyn(Polynp){//销毁多项式pPolynq1,q2;q1=p->next;q2=q1->next;wh

4、ile(q1->next){free(q1);q1=q2;q2=q2->next;}}voidPrintPolyn(PolynP){Polynq=P->next;intflag=1;//项数计数器if(!q){//若多项式为空，输出0putchar('0');printf("");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->e

5、xpn==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;fla

6、g++;}printf("");}intcompare(Polyna,Polynb){if(a&&b){if(!b

7、

8、a->expn>b->expn)return1;elseif(!a

9、

10、a->expnexpn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}PolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynqa=pa->next;Polynqb=p

11、b->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc->next=NULL;headc=hc;while(qa

12、

13、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->

14、expn=qa->expn;qa=qa->next;qb=qb->next;break;}case-1:{q