设计一个一元稀疏多项式计算器论文1.docx
- 文档编号:3377961
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:29
- 大小:256.75KB
设计一个一元稀疏多项式计算器论文1.docx
《设计一个一元稀疏多项式计算器论文1.docx》由会员分享,可在线阅读,更多相关《设计一个一元稀疏多项式计算器论文1.docx(29页珍藏版)》请在冰点文库上搜索。
设计一个一元稀疏多项式计算器论文1
课程设计(论文)
课程名称:
数据结构课程设计
题目:
一元稀疏多项式简单计算器
院(系):
信息与控制工程学院
专业班级:
计算机0901
姓名:
张强
学号:
090620119
指导教师:
李智杰
2011年9月9日
西安建筑科技大学课程设计(论文)任务书
专业班级:
计算机0901学生姓名:
张强指导教师(签名):
一、课程设计(论文)题目
问题描述:
设计一个一元稀疏多项式简单计算器。
二、本次课程设计(论文)应达到的目的
数据结构是实践性很强的课程。
课程设计是加强学生实践能力的一个强有力手段。
课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。
严格实施课程设计这一环节,对于学生基本程序设计素养的培养和软件工作者工作作风的训练,将起到显著的促进作用。
本题目要达到目的:
熟练掌握数组、链表的各种应用。
三、本次课程设计(论文)任务的主要内容和要求(包括原始数据、技术参数、设计要求等)
[基本要求]
(1)输入并建立多项式;
(2)输出多项式,输出形式为整数序列:
n,c1,e1,c2,e2,,,,,,,cn,en,其中n是多项式的项数,ci,ei,分别是第i项的系数和指数,序列按指数降序排序;
(3)多项式a和b相加,建立多项式a+b;
(4)多项式a和b相减,建立多项式a-b;
(5)计算多项式在x处的值。
(6)计算器的仿真界面。
四、应收集的资料及主要参考文献:
由于本课程没有安排“课内上机”学时,因此,在课程设计之前必须自己已经上机练习了“数组、线性表”及其有关的基本操作。
参考文献:
1.本年级用的教材:
数据结构与算法分析(C++版)(第二版)影印版2005,7;
2.C++程序设计技能百练,中国铁道出版社,2004,1蒋立翔编著;
3.数据结构与C++,西安交通大学出版社,1999,11周叶著;
4.C/C++与数据结构,清华大学出版社,2002,3,1王立柱;
5.数据结构使用C++语言描述,东南大学出版社,2001,1,1陈慧南;
五、审核批准意见
教研室主任(签字)
设计总说明
本文介绍了用C++语言编写一个一元稀疏多项式计算器。
其内容包括输入并建立多项式,两个多项式相加以及输出多项式:
n,c1,e1,c2,e2,…cn,en,其中,n是多项式项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列。
利用这个程序可以方便的计算简单的一元稀疏多项式的基本运算。
本课程设计就是对这样一个简单的计算器进行设计,用以实现一元稀疏多项式基本的运算问题。
设计从小处着手,以小见大。
运用所学的一些c++知识,构成整个计算器的形成框架。
并在程序中定义了各种类型的运算的模块,本程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后,能够进行多项式输出、多项式相加、多项式相减、多项式求值、多项式求积,多项式求商的运算,通过主程序的调用来完成他们之间的配合。
来实现输入并建立多项式,两多项式的相加以及多项式的输出。
目录
一.问题描述················1
二.需求分析················1
三.概要设计················2
四.详细设计················3
五.源代码·················4
六.程序测试················17
七.使用说明················21
八.课设总结················22
九.参考文献················23
数据结构课程设计
——一元稀疏多项式简单计算器
一、问题描述
1、基本要求
(1)输入并建立多项式;
(2)输出多项式,输出形式为整数序列:
n,c1,e1,c2,e2,,,,,,,cn,en,其中n是多项式的项数,ci,ei,分别是第i项的系数和指数,序列按指数降序排序;
(3)多项式a和b相加,建立多项式a+b;
(4)多项式a和b相减,建立多项式a-b;
(5)计算多项式在x处的值。
(6)计算器的仿真界面。
2、设计目的
数据结构是实践性很强的课程。
课程设计是加强学生实践能力的一个强有力手段。
课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。
严格实施课程设计这一环节,对于学生基本程序设计素养的培养和软件工作者工作作风的训练,将起到显著的促进作用
二、需求分析
1、设计开发环境:
软件方面:
系统windowsxp编程软件:
VC++6.0
2、思路分析:
①一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+……+pmxem
其中,p1是指数为ei的项的非零系数,且满足0≦e1 ②用两个带表头结点的单链表分别存储两个多项式 ③根据一元多项式相加的运算规则: 对于两个一元多项式中所有指数相同的项,对应系数相加,若其和不为零,则构成“和多项式”中的一项; ④只需要将第二个多项式的系数改为其相反数,然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式” 三、概要设计 图3-1功能模块图 为实现上述程序功能,用带表头结点的单链表存储多项式。 元素类型,节点类型,和指针类型: typedefstructPolynomial{ intcoe;//系数 intexp;//指数 structPolynomial*next; }*Polyn,Polynomial; 各个模块之间的调用如图3-1所示,调用insert()函数将输入的多项式按降幂排列,通过主函数main()中swith语句,选择用户所选择的对应的模块,然后又模块对应的功能函数对用户输入的数据进行相应的操作,最后通过desktop()模块将最后结果输出。 四、详细设计 图4-1功能实现流程图 4.1输入模块 用户可通过本模块来输入一个多项式,在每次输入一个多项式时,本模块会先判断谁否是第一次输入,如果是,创建节点,如果不是则模块会通过判断本次输入的数的指数与第一项输入的指数的大小,如果第一项的指数较大,则刚输入的这一项继续与第二项比较指数,以此类推,如果发现刚输入的这一项的指数比比较的这一项的指数要大,则插入比较项的前面。 4.2求和、差模块 用户通过本模块可以实现两个多项式的求和或差值,此模块先调用输入模块,进行对两个要运算的多项式进行初始化,并按降幂排列。 然后将两个多项式的幂进行一个对比,如果第一个数的第一项的系数大于第二个多项式的第一个项的系数,那么直接将第一项赋值于刚开始创建的链表的第一项,作为答案的最后一项,反之亦然,如果第一个数的第一项,与第二个数的第一项的系数相同,那么将两个数的系数与指数分别相加或者相减并将对应值赋值给答案相对应的项。 以此类推。 最后有输出模块输出最后答案。 4.3求积、商模块 用户可通过该模块实现两个多项式的相乘(相除),此模块先调用输入模块,进行对两个要运算的多项式的初始化,并按降幂排列。 然后将第一个数的系数、指数与第二个数的系数、指数分别相乘(相除),相加(相减),并且赋值给答案相应的系数、指数。 完成后执行第一个数的第一项与第二个数的第二项进行相应的操作…….执行完之后最后调用输出模块将结果输出到屏幕上。 4.4求值模块 用户可通过此模块实现多项式的求值,此模块调用输入模块,完成相对应的操作,然后需要用户输入此时变量的值,并且将变量的值赋值给变量,最后将答案通过输出模块输出到屏幕上。 五、源代码 我真诚地保证: 我自己独立地完成了整个程序从分析、设计到编码的全过程。 如果在上述过程中,我遇到了困难而求教于人,那么,我将在程序报告中详细地列举我所遇到的问题,以及别人给我的提示。 在此,我感谢同学老师对我的启发和帮助。 下面的报告中,我还会具体地提到他们在各个方法对我的帮助。 我的程序里中凡是引用到其他程序或文档之处,例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,我都已经在程序的注释里很清楚地注明了引用的出处。 我从未抄袭过别人的程序,也没有盗用别人的程序,无论是修改式地抄袭还是原封不动地抄袭。 我编写这个程序,从来没有想过要去破坏或妨碍其他计算机系统的正常运转。 <张强> #include #include #include typedefstructPolynomial{ intcoe;//系数 intexp;//指数 structPolynomial*next; }*Polyn,Polynomial; Polynma,mb; voidInsert(Polynp,Polynh) { if(p->coe==0)deletep; else{ Polynq1,q2; q1=h;q2=h->next; while(q2&&p->exp { q1=q2; q2=q2->next; } if(q2&&p->exp==q2->exp) { q2->coe+=p->coe; deletep; if(! q2->coe) { q1->next=q2->next; deleteq2;} } else { p->next=q2; q1->next=p; } } } PolynCreatePolyn(Polynhead,intm) { inti; Polynp; p=head=newPolynomial; head->next=NULL; for(i=0;i p=newPolynomial;; cout<<"请输入第"< "; cin>>p->coe; cout<<"指数: "; cin>>p->exp; Insert(p,head); } returnhead; } voidDestroyPolyn(Polynp) { Polynt; while(p! =NULL) { t=p; p=p->next; deletet; } } voidPrintPolyn(PolynPm) { Polynqa=Pm->next; intflag=1; if(! qa) { cout<<"0"; cout< return; } while(qa) { if(qa->coe>0&&flag! =1)cout<<"+"; if(qa->coe! =1&&qa->coe! =-1) { cout< if(qa->exp==1)cout<<"X"; elseif(qa->exp)cout<<"X^"< } else { if(qa->coe==1) { if(! qa->exp)cout<<"1"; elseif(qa->exp==1)cout<<"X"; elsecout<<"X^"< } if(qa->coe==-1) { if(! qa->exp)cout<<"-1"; elseif(qa->exp==1)cout<<"-X"; elsecout<<"-X^"< } } qa=qa->next; flag++; } cout< } intcompare(Polyna,Polynb) { if(a&&b) { if(! b||a->exp>b->exp)return1; elseif(! a||a->exp elsereturn0; } elseif(! a&&b)return-1; elsereturn1; } PolynAddPolyn(Polynpa,Polynpb) { Polynqa=pa->next; Polynqb=pb->next; Polynheadc,hc,qc; hc=newPolynomial; hc->next=NULL; headc=hc; while(qa||qb) { qc=newPolynomial; switch(compare(qa,qb)) { case1: { qc->coe=qa->coe; qc->exp=qa->exp; qa=qa->next; break; } case0: { qc->coe=qa->coe+qb->coe; qc->exp=qa->exp; qa=qa->next; qb=qb->next; break; } case-1: { qc->coe=qb->coe; qc->exp=qb->exp; qb=qb->next; break; } } if(qc->coe! =0) { qc->next=hc->next; hc->next=qc; hc=qc; } elsedeleteqc; } returnheadc; } PolynSubtractPolyn(Polynpa,Polynpb) { Polynh=pb; Polynp=pb->next; Polynpd; while(p) { p->coe*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) p->coe*=-1; returnpd; } PolynMultiplyPolyn(Polynpa,Polynpb) { Polynhf,pf;// Polynqa=pa->next;//新建一个结点作为pa的后继结点 Polynqb=pb->next;//新建一个结点作为pb的后继结点 hf=newPolynomial; hf->next=NULL; while(qa)//使用while循环,使得多项式的每项得以运算 { qb=pb->next; while(qb) { pf=newPolynomial; pf->coe=qa->coe*qb->coe; pf->exp=qa->exp+qb->exp; Insert(pf,hf);//调用插入函数,将新的结点插入到新建链表中,并合并同类项 qb=qb->next; } qa=qa->next; } returnhf;//返回所得链表的头指针 } voidDevicePolyn(Polynpa,Polynpb) { Polynquotient,remainder,temp1,temp2; Polynqa=pa->next; Polynqb=pb->next; quotient=newPolynomial;//建立头结点,存储商 quotient->next=NULL; remainder=newPolynomial;//建立头结点,存储余数 remainder->next=NULL; temp1=newPolynomial; temp1->next=NULL; temp2=newPolynomial; temp2->next=NULL; temp1=AddPolyn(temp1,pa); while(qa! =NULL&&qa->exp>=qb->exp) { temp2->next=newPolynomial; temp2->next->coe=(qa->coe)/(qb->coe); temp2->next->exp=(qa->exp)-(qb->exp); Insert(temp2->next,quotient); pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2)); qa=pa->next; temp2->next=NULL; } remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb)); pb=temp1; cout< "); PrintPolyn(quotient); cout<<"yushu"< "); PrintPolyn(remainder); } floatValuePolyn(Polynhead,floatx) { Polynp; p=head->next; floatresult=0; while(p! =NULL) { result+=(p->coe)*(float)pow(x,p->exp); p=p->next; } returnresult; } voiddesktop() { system("cls"); cout< cout<<"**********************************************"< cout<<"**1.输出多项式a和b**"< cout<<"**2.建立多项式a+b**"< cout<<"**3.建立多项式a-b**"< cout<<"**4.建立多项式a*b**"< cout<<"**5.建立多项式a/b**"< cout<<"**6.计算多项式a的值**"< cout<<"**7.退出**"< cout<<"**********************************************"< cout<<"执行操作: "; } voidinput(){ intm,n; //Polynpa,pb; cout<<"请输入多项式a的项数: "; cin>>m; ma=CreatePolyn(ma,m); cout< cout<<"请输入多项式b的项数: "; cin>>n; mb=CreatePolyn(mb,n);} voidmain() { //intm,n; floatx,result; charkey; //Polynpa,pb; cout< "< cout<<"系统正在初始化数据,请稍后..."< _sleep(3*1000); system("cls"); while(key) { desktop(); cin>>key; switch(key) { case'1': input(); cout<<"多项式a: "; PrintPolyn(ma); cout<<"多项式b: "; PrintPolyn(mb); break; case'2': input(); //pc=AddPolyn(pa,pb); cout<<"多项式a: "; PrintPolyn(ma); cout<<"多项式b: "; PrintPolyn(mb); cout<<"多项式a+b: "; PrintPolyn(AddPolyn(ma,mb)); //DestroyPolyn(pc); break; case'3': input(); //pd=SubtractPolyn(pa,pb); cout<<"多项式a: "; PrintPolyn(ma); cout<<"多项式b: "; PrintPolyn(mb); cout<<"多项式a-b: "; PrintPolyn(SubtractPolyn(ma,mb)); //DestroyPolyn(pd); break; case'4': input(); //pd=SubtractPolyn(pa,pb); cout<<"多项式a: "; PrintPolyn(ma); cout<<"多项式b: "; PrintPolyn(mb); cout<<"多项式a*b: "; PrintPolyn(MultiplyPolyn(ma,mb)); //DestroyPolyn(pd); break; case'5': input(); //pd=SubtractPolyn(pa,pb); cout<<"多项式a: "; PrintPolyn(ma); cout<<"多项式b: "; PrintPolyn(mb); cout<<"多项式a/b: "; DevicePolyn(ma,mb); //DestroyPolyn(pd); break; case'6': input(); cout<<"多项式a: "; PrintPolyn(ma); cout<<"输入x的值: x="; cin>>x; result=ValuePolyn(ma,x); cout<<"多项式a的值: "< break; case'7': DestroyPolyn(ma); Destroy
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 设计 一个 一元 稀疏 多项式 计算器 论文