稀疏多项式的乘法实现

学 号： 课 程 设 计 目 稀疏多项式的乘法实现 学 院 计算机科学与技术学院 专 业 软件工程专业 班 级 姓 名 指导教师 夏红霞 2010年7月9日 课程任务书 学生 专业班级： 指导教师： 夏红霞 工作单位：计算机科学与技术学院 题 目: 稀疏多项式的乘法实现 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1、系统应具备的功能： （1）设计稀疏多项式的存储结构 （2）实现稀疏多项式的乘法 （3）输出运算结果 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等； （4）结束语； （5）参考文献。 时间安排： 2010年7月5日－9日 （第19周） 7月5日 查阅资料 7月6日 系统设计，数据结构设计，算法设计 7月7日 -8日 编程并上机调试 7月9日 撰写报告 7月10日 验收程序，提交设计报告书。 指导教师签名： 2010年7月4日 系主任（或责任教师）签名： 2010年7月4日 稀疏多项式的乘法实现 摘要：该程序主要部分有：①首先定义多项式再用链表表示稀疏多项式的存储结构；②多项式的输入并对其各项按照幂从大到小排列；③实现稀疏多项式的加法运算；④再加法运算的基础上对多项式进行乘法运算。 关键字：稀疏多项式，链表，排列，乘法运算 0.引言 在科学技术日新月异的今天，计算机技术广泛的应用于人们的日常生活中。其中数据结构就是比较突出的一种，数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。而多项式的乘法在日常生活和学习中具有什么重要的作用，本程序就是用数据结构里的算法思想加上c++语言写的，用于处理稀疏多项式的乘法问题。 1.需求分析 系统应具备的功能，具体如下： 设计稀疏多项式的存储结构 实现稀疏多项式的乘法 输出运算结果 2.数据结构设计 struct poly{ int c; int e; poly * next;} 3.算法设计 3.1创建链表 void createpoly(poly * head) { int a,n; poly *s,*p; p=head; do { cin>>a>>n; if(a!=10000) { s=new poly; s->next=NULL; s->c=a; s->e=n; p->next=s; p=s; } }while(a!=10000); 3.2合并同类项，如果合并后的系数为零，则删除此节点 void hebing(poly *head) { poly *p,*q,*h,*j,*i； for(p=head->next;p->next!=NULL;p=p->next) { for(q=p,h=p->next;h!=NULL;) { if(h->e==p->e) { p->c+=h->c; q->next=h->next; h=q->next; } else { h=h->next; q=q->next; } } } for(i=head,j=head->next;j!=NULL;) { if(j->c==0) { i->next=j->next; delete(j); j=i->next; } else { j=j->next; i=i->next; } } } 3.3 对多项式中各项按照幂从大到小排列 void pailie(poly *head) //对多项式中各项按照幂从大到小排列 { int i,j; poly *p,*q; for(p=head->next;p->next!=NULL;p=p->next) { i=p->c; j=p->e; for(q=p->next;q!=NULL;q=q->next) { if(q->e>j) { i=q->c; j=q->e; } } if(p->e!=j) { for(q=p->next;q->e!=j;q=q->next); q->c=p->c; q->e=p->e; p->c=i; p->e=j; } } } 3.4打印多项式 void printpoly(poly *head) { int m=1,n=0; poly *p; hebing(head); pailie(head); for(p=head->next;p!= NULL;p=p->next) n++; cout<next;p!= NULL;p=p->next) { cout<c<<","<e<<","; } cout<next; p=pb->next; while(s!=NULL&&p!=NULL) { if(i->next->e==j->next->e) { s->c+=p->c; if(s->c!=0) { i=i->next; s=s->next; delete(j); j=new poly; p=p->next; j->next=p; } else { i->next=s->next; delete s; s=i->next; delete j; j=new poly; p=p->next; j->next=p; } } else if(i->next->enext->e) { delete(j); j=new poly; j->next=p->next; i->next=p; p->next=s; p=j->next; i=i->next; } else { i=i->next; s=s->next; } } if(p!=NULL) { delete(j); i->next=p; } return (pa);} 3.6在加法的基础上实现乘法运算 poly *multiply(poly *pa,poly *pb) //在加法的基础上实现乘法运算 { int k=0; poly *str[100],*p,*s,*sum,*i,*j; i=pa->next; j=pb->next; for(i;i!=NULL;i=i->next,k++) { str[k]=new poly; str[k]->next=NULL; p=str[k]; j=pb->next; for(j;j!=NULL;j=j->next ) { s=new poly; s->next=NULL; s->e=i->e+j->e; s->c=i->c*j->c; p->next=s; p=s; } } sum=str[0]; for(int m=1;mnext=NULL; p1=new poly; p1->next=NULL; cout<<"在输入多项式的时候要注意："<方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载