数据结构课程设计报告-设计一个一元多项式计算器.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-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; 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-coef0&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-expnb-expn) return -1; else if(!a|a-expnexpn) 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(icoef)*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; casea: printf(n 多项式a=); printlinklist(pa); break; caseb: printf(n 多项式b=); printlinklist(pb); break; casec: printf(输入x的值：x=); scanf(%d,&x); printf(n x=%d时，a=%dn,x,valuelinklist(pa,x); break; cased: 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; caseq: printf(n 感谢使用此程序！n); destroylinklist(pa); destroylinklist(pb); s=0; break; default: printf(n 操作错误，请重新选择! n); 三 技术要点这两个链表的交叉合并运算主要用到的是链表的基本操作，定义节点，将链表的创建（输入0 0为结束）、链表的交叉组合、链表内容升序排列、销毁链表、多项式的插入、多项式相加、多项式相减、多项式相乘、以及带值计算多项式等算法写成独立函数，通过主函数调用。这样大大精简了主函数的操作。而且在主函数中创建菜单，用了switch语句比if语句和while语句简洁明了得多。四 源代码#include#include#include/定义多项式的项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-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; 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-coef0&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-expnb-expn) return -1; else if(!a|a-expnexpn) 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(icoef)*t; return sum;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);/建立多项式aprintf( n);printf(请继续操作: ); break; case 2: printf(请输入多项式b各项系数和指数（系数，指数）输入0 0为结束: ); pb=createlinklist(pb);/建立多项式b printf( n);printf(请继续操作: ); break; casea: printf(n 多项式a=); printlinklist(pa); break; caseb: printf(n 多项式b=); printlinklist(pb); break; casec: printf(输入x的值：x=); scanf(%d,&x); printf(n x=%d时，a=%dn,x,valuelink