欢迎来到天天文库
浏览记录
ID:1472462
大小:606.57 KB
页数:44页
时间:2017-11-11
《数据结构课程设计模板》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构课程设计报告学院计算机科学与工程学院专业班级13312学号11303010234姓名王韬指导教师苟光磊,董世都,张宜浩编写时间2014.12.27一.课程设计概述共完成4个题目:1.一元稀疏多项式计算器2.成绩分析问题3.背包问题4.八皇后问题编程语言:VC6.0运行环境:Windows8.0二.一元稀疏多项式计算器问题描述:1.1输入并建立多项式;1.2输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,………cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;
2、1.3多项式a和b相加,建立多项式a+b;1.4多项式a和b相减,建立多项式a-b。1.5多项式a和b相乘,建立乘积多项式ab。需求分析:2.1定义线性表的动态分配顺序存储结构;2.2建立多项式存储结构,定义指针*next2.3利用链表实现队列的构造。每次输入一项的系数和指数,可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行,即在计算机终站上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运行命令;最后根据相应的输入数据(滤去输入中的非法字符)建立的多项式以及多项式相加的运行结果在屏幕上显示
3、。多项式显示的格式为:c1x^e1+c2x^e2+…+cnx^en设计思路:要解决多项式相加,必须要有多项式,所以必须首先建立两个多项式,在这里采用链表的方式存储链表,所以我将结点结构体定义为序数coef指数expn指针域next运用尾插法建立两条单链表,以单链表polynp和polynh分别表示两个一元多项式a和b,a+b的求和运算等同于单链表的插入问题(将单链表polynp中的结点插入到单链表polynh中),因此“和多项式”中的结点无须另生成。为了实现处理,设p、q分别指向单链表polya和polyb的当前项,
4、比较p、q结点的指数项,由此得到下列运算规则:①若p->expnexpn,则结点p所指的结点应是“和多项式”中的一项,令指针p后移。②若p->expn=q->expn,则将两个结点中的系数相加,当和不为0时修改结点p的系数。③若p->expn>q->expn,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移。4、数据测试(1)、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);(2)、(2x+5x^8
5、-3.1x^11)-(7-5x^8+11x^9)=-3.1x^11-11x^9+10x^8+12x-7;(3)(2x+5x^8-3.1x^11)*(7-5x^8+11x^9)=34.1x^20+15.5x^19+55x^17-25x^16-21.7x^11+22x^10-10x^9+35x^8+14x概要设计1.元素类型、结点类型和指针类型:typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomia
6、l;2、建立一个头指针为head、项数为m的一元多项式,建立新结点以接收数据,调用Insert函数插入结点:PolynCreatePolyn(Polynhead,intm){inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i7、",&p->coef,&p->expn);Insert(p,head);}returnhead;}3、主函数和其他函数:voidmain(){intm,n,a,x;charflag;Polynpa=0,pb=0,pc;}数据结构:带头结点单链表抽象数据类型的结点结构定义如下:typedefstructPolynode//多项式结点{intcoef;//系数intexp;//指数Polynode*next;}Polynode,*Polylist;模块划分:(1)带头结点的多项式的建立函数PolylistPolycrea8、te()(2)带头结点的多项式的降幂输出函数voidprintf(Polylistpoly)(3)带头结点的多项式的相加函数PolylistPolyadd(Polylista,Polylistb)(4)带头结点的多项式的相减函数PolylistPolysub(Polylista,Polylistb)(5)主函数voidmain()流程图:源代码
7、",&p->coef,&p->expn);Insert(p,head);}returnhead;}3、主函数和其他函数:voidmain(){intm,n,a,x;charflag;Polynpa=0,pb=0,pc;}数据结构:带头结点单链表抽象数据类型的结点结构定义如下:typedefstructPolynode//多项式结点{intcoef;//系数intexp;//指数Polynode*next;}Polynode,*Polylist;模块划分:(1)带头结点的多项式的建立函数PolylistPolycrea
8、te()(2)带头结点的多项式的降幂输出函数voidprintf(Polylistpoly)(3)带头结点的多项式的相加函数PolylistPolyadd(Polylista,Polylistb)(4)带头结点的多项式的相减函数PolylistPolysub(Polylista,Polylistb)(5)主函数voidmain()流程图:源代码
此文档下载收益归作者所有