数据结构课设—一元多项式的表示及其运算的实现以及算数表达式的求值问题.docx

Heilongjiang Institute of Science and Technology数据结构课程设计报告姓 名： 麻凯旋 班 级： 软件10-2班 学 号： 26号 指导教师： 刘文强 2011 年 12 月23日课程设计综合成绩评定设计题目一： 一元多项式的表示及其运算的实现 设计题目二： 算数表达式的求值问题 考核项目分值AC得分设计情况（共70分）设计工作量与难度20设计工作量大与设计有一定难度设计工作量与难度一般，基本达到了要求设计方案15设计方案正确、合理设计方案较正确、基本合理，但不是最优设计完成情况35完成了选题的设计内容，设计功能完整，相关算法设计正确，程序结果正确、直观性好基本完成了选题的设计内容及主要选题功能，相关算法设计基本正确，程序结果正确设计报告（共15分）报告组织结构及内容10内容组织及结构合理、内容充实、层次清晰、图表得当内容组织及结构较合理、内容较充实、层次较清晰、图表应用基本得当报告排版格式5格式规范，完全符合要求格式基本规范，基本符合要求设计态度（共15分）15设计态度认真、积极设计态度比较认真综合得分课程设计综合成绩（折合为优、良、中、及格与不及格计）其它说明：目 录1. 一元多项式的表示及其运算的实现11.1 问题描述11.2 设计方案与概要设计11.3 详细设计21.4 程序运行说明与结果112.算术表达式的求值问题122.1 问题描述122.2 设计方案与概要设计122.3 详细设计142.4 程序运行说明与结果203.总结与分析22数据结构课程设计1. 一元多项式的表示及其运算的实现1.1 问题描述 要求选用线性表的一种合适的存储结构来表示一个一元多项式，并在此结构上实现一元多项式的加法，减法和乘法操作。1.程序的输入在设计程序的要求输入两个多项式。2.程序的输出输出两个多项式相加，想减，相乘的结果。1.2 设计方案与概要设计1.多项式的存储结构此程序采用线性表存储结构中的单链表存储一元多项式的各项2.方案设计创建一个带头结点的单链表并且对其进行初始化。输入多项式，通过调用程序中的add,sub,以及mulp三个函数分别实现多项式的相加运算、相减运算和相乘运算，再通过print函数将结果输出。3.设计程序的整体功能结构程序结构模块（1）main选择先关操作，调用相关函数（2）创建并初始化多项式链表模块（3）加法模块对两个多项式进行相加操作（4）减法模块对两个多项式进行想减操作（5）乘法模块对两个多项式进行相乘操作（6）打印模块将多项式进行相关操作的的结果输出1.3 详细设计#include#includetypedef struct float xishu; /系数 int zhishu; /指数term;typedef struct LNode /定义单链表 term data; struct LNode *next;LNode,*LinkList;typedef LinkList duoxiangshi;int cmp(term a,term b) if(a.zhishub.zhishu) return 1; if(a.zhishu=b.zhishu) return 0; if(a.zhishunext=NULL) printf(Y=0n); else printf(多项式为Y=);q=P-next;i=1; if(q-data.xishu!=0&q-data.zhishu!=0) printf(%.2fX%d,q-data.xishu,q-data.zhishu); i+; if(q-data.zhishu=0&q-data.xishu!=0) printf(%.2f,q-data.xishu);/打印第一项 q=q-next; if(q=NULL) printf(n); return 1; while(1)/while中，打印剩下项中系数非零的项， if(q-data.xishu!=0&q-data.zhishu!=0) if(q-data.xishu0) printf(+); printf(%.2fX%d,q-data.xishu,q-data.zhishu); i+; if(q-data.zhishu=0&q-data.xishu!=0) if(q-data.xishu0) printf(+); printf(%f,q-data.xishu); q=q-next; if(q=NULL) printf(n); break; return 1;/*1、创建并初始化多项式链表*/duoxiangshi creatpolyn(duoxiangshi P,int m) duoxiangshi r,q,p,s,Q; int i; P=(LNode*)malloc(sizeof(LNode);/申请头节点 r=P; for(i=0;idata.xishu,&s-data.zhishu); r-next=s; r=s; r-next=NULL; if(P-next-next!=NULL) for(q=P-next;q!=NULL;q=q-next)/合并同类项q-next!=NULL for(p=q-next,r=q;p!=NULL;) if(q-data.zhishu=p-data.zhishu)/指数相同进行系数相加操作 q-data.xishu=q-data.xishu+p-data.xishu; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next; p=p-next; return P;/*2加*/duoxiangshi addpolyn(duoxiangshi pa,duoxiangshi pb) duoxiangshi s,newp,q,p,r;int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; break; case 0: s-data.xishu=p-data.xishu+q-data.xishu; if(s-data.xishu!=0.0) s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.xishu=q-data.xishu; s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; break; /switch对齐 /while对齐 while(p) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=q-data.xishu; s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; r-next=NULL; for(q=newp-next;q-next!=NULL;q=q-next)/合并同类项 for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.zhishu=p-next-data.zhishu) q-data.xishu=q-data.xishu+p-next-data.xishu; r=p-next; p-next=p-next-next; free(r); return newp;/*3减*/duoxiangshi subpolyn(duoxiangshi pa,duoxiangshi pb) duoxiangshi s,newp,q,p,r,Q; int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; break; case 0: s-data.xishu=p-data.xishu-q-data.xishu; if(s-data.xishu!=0.0) s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next；q=q-next;break;case 1: s-data.xishu=-q-data.xishu;s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=-q-data.xishu; s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; r-next=NULL; if(newp-next!=NULL&newp-next-next!=NULL)/合并同类项 for(q=newp-next;q!=NULL;q=q-next) for(p=q-next,r=q;p!=NULL;) if(q-data.zhishu=p-data.zhishu)/如果指数相等 q-data.xishu=q-data.xishu+p-data.xishu;/系数相加 r-next=p-next; Q=p; p=p-next; free(Q); else r=r-next; p=p-next; return newp;/*4乘*/duoxiangshi mulppolyn(duoxiangshi pa,duoxiangshi pb) duoxiangshi s,newp,q,p,r; int i=20,j; newp=(LNode*)malloc(sizeof(LNode); r=newp; for(p=pa-next;p!=NULL;p=p-next) for(q=pb-next;q!=NULL;q=q-next) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=p-data.xishu*q-data.xishu;/系数相乘 s-data.zhishu=p-data.zhishu+q-data.zhishu;/指数相加 r-next=s; r=s; r-next=NULL; for(;i!=0;i-) for(q=newp-next;q-next!=NULL;q=q-next)/合并同类项 for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.zhishu=p-next-data.zhishu)/指数相等 则 系数相加 q-data.xishu=q-data.xishu+p-next-data.xishu; r=p-next; p-next=p-next-next; free(r); return newp;main() duoxiangshi pa=NULL,pb=NULL; duoxiangshi p,q; duoxiangshi addp=NULL,subp=NULL,mulp=NULL; int n,m; int sign=y; printf(1创建两个一元多项式n); printf(2多项式相加n); printf(3多项式相减n); printf(4多项式相乘n); printf(5退出n); printf(n); while(sign!=n) printf(选择：); scanf(%d,&n); switch(n) case 1: if(pa!=NULL) printf(已经创建两个多项式，继续其他操作！); break; printf(输入第一个多项式：n); printf(要输入几项：); scanf(%d,&m); while(m=0) printf(m不能为0，重新输入m:); scanf(%d,&m); pa=creatpolyn(pa,m); printpolyn(pa); printf(输入第二个多项式：n); printf(要输入几项：); scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb); break; case 2: if(pa=NULL) printf(先创建两个一元多项式！n); break; addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa=NULL) printf(先创建两个一元多项式！n); break; subp=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa=NULL) printf(先创建两个一元多项式！n); break; mulp=mulppolyn(pa,pb); printpolyn(mulp); break; case 5: if(addp!=NULL) p=addp; while(p!=NULL) q=p; p=p-next; free(q); if(subp!=NULL) p=subp; while(p!=NULL) q=p; p=p-next; free(q); exit(-2); 1.4 程序运行说明与结果有两个多项式f(x1)=2x3+4x和f(x2)=4x2,分别对进行两式相加、想减、和相乘的运算，输出其结果。程序结果如下：222. 算术表达式的求值问题2.1 问题描述 根据算术运算符的优先级，根据输入的算术表达式，求表达式的值。 2.2 设计方案与概要设计 1.存储结构此程序采用栈进行相关操作。 2.方案设计 定义一个主函数，通过调用不同的函数进行相关的操作。首先需要对输入的符号的优先级进转行相关的判断，进一步将输入的表达式进行中缀转为后缀表达式的操作。转置后进行无括号的求值操作，最终将结果导出。3.设计程序的整体功能结构此程序包含五个模块 （1）main( ) 初始化； while(命令=“继续”) 接受数据； 处理数据； 接受命令； （2）判断运算符优先级模块（3）转置模块中缀转换为后缀（4）无括号表示式求值运算模块通过转置后的后缀表达式求值，并输出结果（5） 结果输出模块输出表达式的值 中缀转后缀算法分析（1） 首先将左括号“(”压进栈，作为栈底元素;（2） 从左而右对算数表达式进行扫描，每次读入一个字符s1i；（3） 遇到左括号“(”则压栈；（4） 若遇算术运算符，如果它们的优先级比栈顶元素高，则直接进栈，否则弹出栈顶元素输出到s2i，直到新栈顶元素的优先级比它低，然后将它压栈；（5） 若遇到右括号“）”，则将栈顶元素输出到s2i，直到栈顶元素为“（”，然后相互抵消；（6） 当扫描到“#”符号，表明表达式串已全部输入，将栈中的运算符全部输出到s2i，并删栈顶元素。中缀转后缀的算法代码void zhuanzhi (char *s1)/中转后缀 char s2100;SqStack_b Optr;int i=0,j=0;char t;InitStack_b(&Optr);/初始化一个存储字符型的空栈Push_b(&Optr,();/ 首先将左括号(压进栈，作为栈底元素while(s1i!=#)/不是#，输入没有结束 if(s1i=0 & s1i=9 | s1i=.)/若果是数字或小数点则将其输出给s2is2j+=s1i;if(s1i+19) & s1i+1!=.)s2j+= ;elseswitch(s1i) /扫描到运算符 case(:Push_b(&Optr,s1i);break;/ 遇到左括号(则压栈case):Pop_b(&Optr,&t);/若遇到右括号），则将栈顶元素输出到s2iwhile(t!=()/直到栈顶元素为（，然后相互抵消s2j+=t;Pop_b(&Optr,&t);break;default:while(GetTop_b(&Optr,&t),youxianji (t,s1i)/遇到运算符比较优先级Pop_b(&Optr,&t);/栈顶元素优先级高，则弹出到s2is2j+=t;Push_b(&Optr,s1i);/栈顶元素优先级低，直接压栈i+;Pop_b(&Optr,&t);while(t!=()/表达式串结束，栈中的运算符全部输出到s2i，并删除栈顶元素s2j+=t;Pop_b(&Optr,&t);for(i=0;ij;i+)/将s2复制给s1s1i=s2i;s1i=#;2.3 详细设计#include#include#define TTACK_INIT_SIZE 100000#define STACKINCREMENT 10000typedef structfloat *base ;/存储实型数据元素的一位数组float *top;/栈顶指针 int stacksize;/栈数组容量 SqStack_a;/顺序表的栈类型 顺序栈typedef structchar *base;char *top;int stacksize;SqStack_b;void InitStack_a(SqStack_a *s)/构建存储实型的空栈 s-base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float);if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;void InitStack_b(SqStack_b *s)s-base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char);if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;void GetTop_a(SqStack_a *s,float *e)if(s-top=s-base)/栈空显示错误退出，不空E带值返回栈顶元素。 printf(错误!n);exit(1);*e=*(s-top-1);void GetTop_b(SqStack_b *s,char *e)if(s-top=s-base)printf(错误!n);exit(1);*e=*(s-top-1); void Push_a(SqStack_a *s,float e)/在S栈顶插入新的栈顶元素，若空间已满追加存储空间 if(s-top-s-base=s-stacksize)s-base=(float *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(float);if(!s-base)exit(1);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void Push_b(SqStack_b *s,char e)if(s-top-s-base=s-stacksize)s-base=(char *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char);if(!s-base) exit(1);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void Pop_a(SqStack_a *s,float *e)/若栈不空删除S的栈顶元素E，空则退出程序 if(s-top=s-base)exit(1);*e=*-s-top;void Pop_b(SqStack_b *s,char *e)if(s-top=s-base)exit(1);*e=*-s-top;int youxianji (char Top_char,char s1_char)/栈顶的运算符赋给Top_char，新读入运算符赋给s1_char。判断优