顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现.doc

课 程 设 计（数据结构）班 级姓 名学 号 指导教师二一年七月十日课程设计任务书及成绩评定课题名称顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 、题目的目的和要求 1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求（给出你所选择的题目的要求描述）1) 首先判定多项式是否稀疏2) 分别采用顺序和动态存储结构实现；3) 结果M(x)中无重复阶项和无零系数项；4) 要求输出结果的升幂和降幂两种排列情况；、设计进度及完成情况日 期内 容2010.6.28-6.30选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。2010.7.17.3创建相关数据结构,录入源程序。2010.7.57.7调试程序并记录调试中的问题，初步完成课程设计报告。2009.7.87.9上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏数据结构（C语言版）清华大学出版社，20072 严蔚敏数据结构题集（C语言版）清华大学出版社，20073 谭浩强C语言程序设计清华大学出版社，20054 与所用编程环境相配套的C语言或C+相关的资料、成绩评定设计成绩： （教师填写）指导老师： （签字）二一年 七 月 十 日目 录第一章 概述1第二章 系统分析2第三章 概要设计3第四章 详细设计4第五章 运行与测试5第六章 总结与心得6参考文献7本目录是根据正文文档自动生成的，请在报告完成后，更新目录的页码，更新方法如下：1.鼠标单击目录任意部分选中目录；2.单击鼠标右键选择“更新域”；3.在出现的“更新目录”的对话框中选择“只更新页码”， 见图1-3，单击“确定”按钮，目录页码将被更新。更新完成后，最好再核对一下。图1-3 更新目录页码示意图第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。分别采用顺序结构和链式存储结构，利用多项得结果，最后得多项式中不含有重复阶项和零系数得项。除此之外，还得分为降幂和升幂两种排序方式。第二章 系统分析1 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。2 在程序过程中加入汉字提示符，让读者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。3 程序执行时的命令：选择创建两个一元多项式输入第一个一元多项式的项数依次输入一元多项式的系数和指数以相同方式输入第二个一元多项式选择操作方式选择降幂或升幂排序输出结果是否退出4.测试数据。输入的一元多项式系数指数分别为7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法结果为；升幂 降幂减法结果为：升幂 降幂乘法结果为：升幂 降幂 第三章 概要设计1、数据结构的设计 在该程序中分别分为顺序存储和链式存储结构。2、算法的设计本程序主要分为四大模块主程序模块输入模块：通过Getpolyn函数输入输出模块（升幂降幂）：PrintPolyn函数实现输出数据处理模块（多项式的加减乘）：通过一元多项式的Polynomial基本操作实现3、抽象数据类型的设计一元多项式抽象数据类型的定义：抽象数据类型Polynomial的定义：第四章 详细设计#include<stdio.h>#include<stdlib.h>typedef struct float coef; /系数 int expn; /指数term;typedef struct LNode term data; /term多项式值 struct LNode *next;LNode,*LinkList;typedef LinkList polynomail;/*比较指数*/int cmp(term a,term b) if(a.expn>b.expn) return 1; if(a.expn=b.expn) return 0; if(a.expn<b.expn) return -1; else exit(-2);/*又小到大排列*/void arrange1(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p->next!=NULL;p=p->next); r=p; for(h=pa;h->next!=r;)/大的沉底 for(p=h;p->next!=r&&p!=r;p=p->next) if(cmp(p->next->data,p->next->next->data)=1) q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; r=p;/r指向参与比较的最后一个，不断向前移动 /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p->next!=NULL;p=p->next); r=p; for(h=pa;h->next!=r;)/小的沉底 for(p=h;p->next!=r&&p!=r;p=p->next) if(cmp(p->next->next->data,p->next->data)=1) q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; r=p;/r指向参与比较的最后一个，不断向前移动 /*打印多项式,求项数*/int printpolyn(polynomail P) int i; polynomail q; if(P=NULL) printf("无项！n"); else if(P->next=NULL) printf("Y=0n"); else printf("该多项式为Y=");q=P->next;i=1; if(q->data.coef!=0&&q->data.expn!=0) printf("%.2fX%d",q->data.coef,q->data.expn); i+; if(q->data.expn=0&&q->data.coef!=0) printf("%.2f",q->data.coef);/打印第一项 q=q->next; if(q=NULL) printf("n");return 1; while(1)/while中，打印剩下项中系数非零的项， if(q->data.coef!=0&&q->data.expn!=0) if(q->data.coef>0) printf("+"); printf("%.2fX%d",q->data.coef,q->data.expn); i+; if(q->data.expn=0&&q->data.coef!=0) if(q->data.coef>0) printf("+"); printf("%f",q->data.coef); q=q->next; if(q=NULL) printf("n"); break; return 1;/*1、创建并初始化多项式链表*/polynomail creatpolyn(polynomail P,int m) polynomail r,q,p,s,Q; int i; P=(LNode*)malloc(sizeof(LNode); r=P; for(i=0;i<m;i+) s=(LNode*)malloc(sizeof(LNode); printf("请输入第%d项的系数和指数：",i+1); scanf("%f%d",&s->data.coef,&s->data.expn); r->next=s; r=s; r->next=NULL; if(P->next->next!=NULL) for(q=P->next;q!=NULL/*&&q->next!=NULL*/;q=q->next)/合并同类项 for(p=q->next,r=q;p!=NULL;) if(q->data.expn=p->data.expn) q->data.coef=q->data.coef+p->data.coef; r->next=p->next; Q=p;p=p->next; free(Q); else r=r->next; p=p->next; return P;/*2、两多项式相加*/polynomail addpolyn(polynomail pa,polynomail pb) polynomail 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.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef+q->data.coef; if(s->data.coef!=0.0) s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; q=q->next; break; case 1: s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; while(q) s=(LNode*)malloc(sizeof(LNode); s->data.coef=q->data.coef; s->data.expn=q->data.expn; 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.expn=p->next->data.expn) q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); printf("升序 1 , 降序 2n"); printf("选择:"); scanf("%d",&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb) polynomail 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.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef-q->data.coef; if(s->data.coef!=0.0) s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; q=q->next; break; case 1: s->data.coef=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; while(q) s=(LNode*)malloc(sizeof(LNode); s->data.coef=-q->data.coef; s->data.expn=q->data.expn; 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.expn=p->data.expn) q->data.coef=q->data.coef+p->data.coef; r->next=p->next; Q=p;p=p->next; free(Q); else r=r->next; p=p->next; printf("升序 1 , 降序 2n"); printf("选择:"); scanf("%d",&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*4两多项式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail 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.coef=p->data.coef*q->data.coef; s->data.expn=p->data.expn+q->data.expn; r->next=s; r=s; r->next=NULL; printf("升序 1 , 降序 2n"); printf("选择:"); scanf("%d",&j); if(j=1) arrange1(newp); else arrange2(newp); 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.expn=p->next->data.expn) q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); return newp;/*5、销毁已建立的两个多项式*/void delpolyn(polynomail pa,polynomail pb) polynomail p,q; p=pa; while(p!=NULL) q=p; p=p->next; free(q); p=pb; while(p!=NULL) q=p; p=p->next; free(q); printf("两个多项式已经销毁n");void main() polynomail pa=NULL,pb=NULL; polynomail p,q; polynomail 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("6、退出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=mulpolyn(pa,pb); printpolyn(mulp); break; case 5: if(pa=NULL) printf("请先创建两个一元多项式！n"); break; delpolyn(pa,pb); pa=pb=NULL; break; case 6: 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); /switch /while第五章 运行与测试本章主要说明：1、算法的性能分析2、设计了哪些测试数据？测试结果是什么？请考虑选取有代表性的界面贴图说明。3、在调试程序的过程中遇到什么问题，是如何解决的？程序开始界面分别输入两个多项式第六章 总结与心得本章主要说明：设计完成后的总结与思考，完成任务情况，收获、意见和建议等。参考文献1 严蔚敏，吴伟民数据结构（C语言版）清华大学出版社，20072 殷人昆数据结构（C+版）清华大学出版社，20013 金远平数据结构（C+描述）清华大学出版社，20054 许卓群数据结构与算法高等教育出版社，20045 Frank M.Carrano数据结构与C+高级教程清华大学出版社，20046 严蔚敏，吴伟民数据结构习题集（C语言版）清华大学出版社，2007请根据自己的情况列出参考文献，格式同上。特别注意：1. 标点符号的格式为“全角英文”的逗号和句号。2. 多个作者间用逗号分隔，最多列出前三个作者。3. 最后一个作者和书名之间，书名和出版社之间用句号分隔。4. 出版社和出版年之间用逗号分隔。5. 每行的末尾没有任何的标点符号。