数据结构课程设计报告设计一个一元多项式计算器.doc

报告评分批改老师 数据结构课程设计报告 题 目 设计一个一元多项式计算器班 级 20090201 学生姓名 学 号 2009031327 专 业 电类强化班 指导教师 提交日期 2011/1/4 南京航空航天大学金城学院目录一、 题目要求及内容二、 函数模块及功能三、 技术要点四、 源代码五、 举例六、 调试心得一 题目要求及内容 1.题目：设计一个一元多项式计算器 2.要求 用带头结点的单链表存储多项式 Typedef struct lnode Float coef; Int expn; Struct lnode *next; lnode,*linklist; Typedef linklist polynominal; 输入时，构成的多项式链表按指数项大小递增有序排列 输出格式要求如： 3x2+6x8+7x12-9x15 3.基本功能输入并且建立一元多项式 输出多项式 多项式相加a+b 多项式相减a-b 多项式相乘a*b 二 函数模块及功能 1 void Insert( linklist p,linklist h)；链表插入 void Insert( linklist p,linklist h) if(p->coef=0) free(p);/系数为0的话释放结点 else linklist q1,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; 2linklist Createlinklist(linklist head)；创建链表 linklist Createlinklist(linklist head) /建立一个头指针为head的一元多项式 linklist p; float a;int b; p=head=(linklist)malloc(sizeof(struct lnode); p->next=NULL; scanf("%f %d",&a,&b); while(a!=0 | b!=0) /当输入为0 0时停止输入 p=(linklist)malloc(sizeof(struct lnode); p->coef=a; p->expn=b; Insert(p,head); /调用Insert函数插入结点 scanf("%f %d",&a,&b); return head; 3void Destroylinklist(linklist p)；销毁链表 void Destroylinklist(linklist p) /销毁多项式linklist linklist q1,q2; q1=p->next; q2=q1->next; while(q2) free(q1); q1=q2; q2=q2->next; 4void Printlinklist(linklist P)；打印链表 void Printlinklist(linklist P) linklist q=P->next; int flag=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'); else if(q->expn) printf("X%d",q->expn); else if(q->coef=1) if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d",q->expn); if(q->coef=-1) if(!q->expn) printf("-1"); else if(q->expn=1) printf("-X"); else printf("-X%d",q->expn); q=q->next; flag+; printf("n"); 5int compare(linklist a,linklist b)；链表非空判断int compare(linklist a,linklist b) if(a&&b) if(!b|a->expn>b->expn) return -1; else if(!a|a->expn<b->expn) return 1; else return 0; else if(!a&&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空6linklist Addlinklist(linklist pa,linklist pb)；链表合并多项式相加linklist Addlinklist(linklist pa,linklist pb)/求解并建立多项式a+b，返回其头指针 linklist qa=pa->next; linklist qb=pb->next; linklist headc,hc,qc; hc=(linklist)malloc(sizeof(struct lnode);/建立头结点 hc->next=NULL; headc=hc; while(qa|qb) qc=(linklist)malloc(sizeof(struct lnode); switch(compare(qa,qb) case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: 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; else free(qc);/当相加系数为0时，释放该结点 return headc; 7linklist Subtractlinklist(linklist pa,linklist pb)；链表合并 多项式相减 linklist Subtractlinklist(linklist pa,linklist pb)/求解并建立多项式a-b，返回其 头指针 linklist h=pb; linklist p=pb->next; linklist pd; while(p) /将pb的系数取反 p->coef*=-1; p=p->next; pd=Addlinklist(pa,h); for(p=h->next;p;p=p->next) /恢复pb的系数 p->coef*=-1; return pd; 8linklist Multiplylinklist(linklist pa,linklist pb)；多项式相乘 linklist Multiplylinklist(linklist pa,linklist pb) /求解并建立多项式a*b，返回其头指针 linklist hf,pf; linklist qa=pa->next; linklist qb=pb->next; hf=(linklist)malloc(sizeof(struct lnode);/建立头结点 hf->next=NULL; for(;qa;qa=qa->next) for(qb=pb->next;qb;qb=qb->next) pf=(linklist)malloc(sizeof(struct lnode); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);/调用Insert函数以合并指数相同的项 return hf; 9int Valuelinklist(linklist head,int x)；多项式带值函数 int Valuelinklist(linklist head,int x)/输入x值，计算并返回多项式的值 linklist p; int i; int sum=0;int t; for(p=head->next;p;p=p->next) t=1; for(i=p->expn;i!=0;) if(i<0)t/=x;i+;/指数小于0，进行除法 elset*=x;i-;/指数大于0，进行乘法 sum+=int(p->coef)*t; return sum; 10void main（）；主函数 void main() int s,x; char flag; linklist pa=0,pb=0,pc; printf(" 欢迎使用多项式操作程序nn"); /输出菜单 printf(" *n"); printf(" * 一元多项式操作程序 *n"); printf(" * *n"); printf(" * *n"); printf(" * 1:输入多项式a 2:输入多项式b *n"); printf(" * *n"); printf(" * *n"); printf(" * a:输出多项式a b:输出多项式b *n"); printf(" * *n"); printf(" * *n"); printf(" * c:代入x的值计算a d:代入x的值计算b *n"); printf(" * *n"); printf(" * *n"); printf(" * +:输出a+b -:输出a-b *n"); printf(" * *n"); printf(" * *n"); printf(" * *:输出a*b q:退出程序 *n"); printf(" * *n"); printf(" *n"); printf("n 请选择操作："); while(s) scanf(" %c",&flag);/空格符号一定要注意 switch(flag) case '1': printf("请输入多项式a各项系数和指数（系数，指数）输入0 0为结束:"); pa=Createlinklist(pa);/建立多项式a printf(" n"); printf("请继续操作: "); break; case '2': printf("请输入多项式b各项系数和指数（系数，指数）输入0 0为结束: "); pb=Createlinklist(pb);/建立多项式b printf(" n"); printf("请继续操作: "); break; case'a': printf("n 多项式a="); Printlinklist(pa); break; case'b': printf("n 多项式b="); Printlinklist(pb); break; case'c': printf("输入x的值：x="); scanf("%d",&x); printf("n x=%d时，a=%dn",x,Valuelinklist(pa,x); break; case'd': printf("输入x的值：x="); scanf("%d",&x); printf("n x=%d时，b=%dn",x,Valuelinklist(pb,x); break; case'+': pc=Addlinklist(pa,pb); printf("n a+b="); Printlinklist(pc); break; case'-': pc=Subtractlinklist(pa,pb); printf("n a-b="); Printlinklist(pc); break; case'*': pc=Multiplylinklist(pa,pb); printf("n a*b="); Printlinklist(pc); break; case'q': printf("n 感谢使用此程序！n"); Destroylinklist(pa); Destroylinklist(pb); s=0; break; default: printf("n 操作错误，请重新选择! n"); 三 技术要点这两个链表的交叉合并运算主要用到的是链表的基本操作，定义节点，将链表的创建（输入0 0为结束）、链表的交叉组合、链表内容升序排列、销毁链表、多项式的插入、多项式相加、多项式相减、多项式相乘、以及带值计算多项式等算法写成独立函数，通过主函数调用。这样大大精简了主函数的操作。而且在主函数中创建菜单，用了switch语句比if语句和while语句简洁明了得多。四 源代码#include<stdio.h>#include<malloc.h>#include<stdlib.h>/定义多项式的项typedef struct lnode float coef; int expn; struct lnode *next;lnode,*linklist;typedef linklist polynominal;void Insert( linklist p,linklist h) if(p->coef=0) free(p);/系数为0的话释放结点 else linklist q1,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; linklist Createlinklist(linklist head)/建立一个头指针为head的一元多项式linklist p;float a;int b; p=head=(linklist)malloc(sizeof(struct lnode); p->next=NULL; scanf("%f %d",&a,&b); while(a!=0 | b!=0) /当输入为0 0时停止输入 p=(linklist)malloc(sizeof(struct lnode); p->coef=a; p->expn=b; Insert(p,head); /调用Insert函数插入结点 scanf("%f %d",&a,&b);return head;void Destroylinklist(linklist p)/销毁多项式linklist linklist q1,q2; q1=p->next; q2=q1->next; while(q2) free(q1); q1=q2; q2=q2->next; void Printlinklist(linklist P) linklist q=P->next; int flag=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'); else if(q->expn) printf("X%d",q->expn); else if(q->coef=1) if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d",q->expn); if(q->coef=-1) if(!q->expn) printf("-1"); else if(q->expn=1) printf("-X"); else printf("-X%d",q->expn); q=q->next; flag+; printf("n");int compare(linklist a,linklist b) if(a&&b) if(!b|a->expn>b->expn) return -1; else if(!a|a->expn<b->expn) return 1; else return 0; else if(!a&&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空linklist Addlinklist(linklist pa,linklist pb)/求解并建立多项式a+b，返回其头指针 linklist qa=pa->next; linklist qb=pb->next; linklist headc,hc,qc; hc=(linklist)malloc(sizeof(struct lnode);/建立头结点 hc->next=NULL; headc=hc; while(qa|qb) qc=(linklist)malloc(sizeof(struct lnode); switch(compare(qa,qb) case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: 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; else free(qc);/当相加系数为0时，释放该结点 return headc;linklist Subtractlinklist(linklist pa,linklist pb)/求解并建立多项式a-b，返回其头指针 linklist h=pb; linklist p=pb->next; linklist pd; while(p) /将pb的系数取反 p->coef*=-1; p=p->next; pd=Addlinklist(pa,h); for(p=h->next;p;p=p->next) /恢复pb的系数 p->coef*=-1; return pd;linklist Multiplylinklist(linklist pa,linklist pb)/求解并建立多项式a*b，返回其头指针 linklist hf,pf; linklist qa=pa->next; linklist qb=pb->next; hf=(linklist)malloc(sizeof(struct lnode);/建立头结点 hf->next=NULL; for(;qa;qa=qa->next) for(qb=pb->next;qb;qb=qb->next) pf=(linklist)malloc(sizeof(struct lnode); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);/调用Insert函数以合并指数相同的项 return hf;int Valuelinklist(linklist head,int x)/输入x值，计算并返回多项式的值 linklist p; int i; int sum=0;int t; for(p=head->next;p;p=p->next) t=1; for(i=p->expn;i!=0;) if(i<0)t/=x;i+;/指数小于0，进行除法 elset*=x;i-;/指数大于0，进行乘法 sum+=int(p->coef)*t; return sum;void main() int s,x; char flag; linklist pa=0,pb=0,pc; printf(" 欢迎使用多项式操作程序nn"); /输出菜单printf(" *n");printf(" * 一元多项式操作程序 *n");printf(" *