数据结构课程设计_数据结构课程设计全
数据结构课程设计由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计全”。
一、课程题目：一元稀疏多项式计算器
二、需求分析
1、一元稀疏多项式简单计算器的功能是：
1.1 输入并建立多项式；
1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,„„„cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；
1.3多项式a和b相加，建立多项式a+b；
1.4 多项式a和b相减，建立多项式a-b。
2、设计思路:
2、设计思路：
2.1 定义线性表的动态分配顺序存储结构； 2.2 建立多项式存储结构，定义指针*next 2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式
2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令； 根据相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。
3、程序执行的命令包括：
1）输入多项式a；2）输入多项式b;3）求a+b;4)求a-b；5）求a*b；6）求a的导数；7）求b的导数；8）退出程序。
4、测试数据：
1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);
2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x);
3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);
4、(x+x^3)+(-x-x^3)=0;
5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);
6、(x+x^2+x^3)+0=x+x^2+x^3.7、互换上述测试数据中的前后两个多项式
三、概要设计
为了实现上述功能需用带表头结点的单链表存储多项式。为此需要两个抽象的数据类型：线性表和多项式。
1.有序表的抽象数据类型定义为： ADT List{ 数据对象：D={ai|ai∈Elemset,i=1,2,„，n,n≥0} 数据关系：R1={|ai-1,ai∈D,i=2,„,n} 基本操作： PolyNode *p,*q,*r,*head;操作结果:构造一个空的线性表。Listinsert(&L,i,e)初始条件:线性表L存在，0≤i≤L的元素个数。操作结果:在L中第i个位置之后插入新的结点e。}ADT List2、多数据类型定义为： ADT Polynomial { 数据对象:D={ai,bi|ai为不为0的实数，bi为整数，i=2,„,n} 数据关系:R1={ai，bi} 基本操作：
PrintPolyn(Polyn p)操作结果:输出多项式p。DestroyPolyn(Polyn p)操作结果:销毁多项式p。
Polyn CreatePolyn(Polyn head,int m)操作结果:创建一个m项的多项式。Polyn AddPolyn(Polyn pa,Polyn pb)初始条件:多项式链表pa,pb存在。
操作结果:创建一新多项式链表p，其结点为pa，pb相加。Polyn SubtractPolyn(Polyn pa,Polyn pb)初始条件:多项式链表pa，pb存在。
操作结果:创建一新多项式链表p，其结点为怕pa，pb相减。ValuePolyn(Polyn head,int x)操作结果:输入x值，计算并返回多项式的值 }ADT Polynomial
四、详细设计
1、元素类型、结点类型和指针类型 typedef int Status;typedef struct{ int coef;int expn;}Term;typedef Term ElemType;typedef struct LNode{ ElemType data;//数据域 struct LNode *next;//指针域 }LNode,* LinkList;
2、主函数和其他函数 void main(){ int m,n,a,x;int flag;Polynomial pa,pb,pc;printf(“ 欢迎使用多项式操作程序n”);
//输出菜单
printf(“n 1: 创建多项式a n”);printf(“n 2: 创建多项式b n”);printf(“n 3: 输出多项式a n”);printf(“n 4: 输出多项式b n”);printf(“n 5: 输出a+b n”);printf(“n 6: 输出a-b n”);printf(“n 7: 输出a的导数 n”);printf(“n 8: 输出b的导数 n”);printf(“n 9: 代入x的值计算a n”);printf(“n 10: 代入x的值计算b n”);printf(“n 11: 输出a*b n”);printf(“n 12:退出程序 n”);while(a){ printf(“n请选择操作：”);scanf(“ %d”,&flag);
switch(flag)
{
case 1 :
{
printf(“请输入a的项数:”);scanf(“%d”,&m);CreatePolyn(pa,m);
break;
}
case 2 :
{
printf(“请输入b的项数:”);scanf(“%d”,&n);CreatePolyn(pb,n);
break;
}
case 3 :
{
printf(“n 多项式a=”);
PrintPolyn(pa);
break;
}
case 4 :
{
printf(“n 多项式b=”);
PrintPolyn(pb);
break;
} case 5 :
{
AddPolyn(pa,pb,pc);printf(“n a+b=”);
PrintPolyn(pc);
break;
} case 6 :
{
SubtractPolyn(pa,pb,pc);printf(“n a-b=”);
PrintPolyn(pc);
break;
} case 7 :
{
Polynomial_derivatePolyn(pa,pc);
printf(“n 多项式a的导函数为：a'=”);
PrintPolyn(pc);
break;
} case 8 :
{
Polynomial_derivatePolyn(pb,pc);
printf(“n 多项式b的导函数为：b'=”);
PrintPolyn(pc);
break;
} case 9 :
{
printf(“输入x的值：x=”);
scanf(“%d”,&x);
printf(“n
x=%da=%.3fn”,x,ValuePolyn(pa,x));
break;
} case 10 :
{
printf(“输入x的值：x=”);
scanf(“%d”,&x);
printf(“n
x=%d，时
时b=%.3fn”,x,ValuePolyn(pb,x));
break;
}
case 11 :
{
MultiplyPolyn(pa,pb,pc);printf(“n a*b=”);
PrintPolyn(pc);
break;
}
case'12':
{
printf(“n 感谢使用此程序！n”);
DestroyPolyn(pa);
DestroyPolyn(pb);
a=0;
break;
} default:
printf(“n 您的选择错误，请重新选择!n”);
} } }
3、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点
Status CreatePolyn(Polynomial &head,int m){ //建立一个头指针为head、项数为m的一元多项式 int i;LNode *p;p=head=(Polynomial)malloc(sizeof(struct LNode));head->next=NULL;for(i=0;i
printf(“请输入第%d项的系数与指数:”,i+1);scanf(“%d %d”,&p->data.coef,&p->data.expn);Insert(p,head);//调用Insert函数插入结点 } return OK;}//CreatePolyn
4、求解并建立多项式a+b Status AddPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a+b，返回其头指针 LNode *qa=pa->next;LNode *qb=pb->next;LNode *headc,*hc,*qc;hc=(Polynomial)malloc(sizeof(struct LNode));//建立头结点 hc->next=NULL;headc=hc;while(qa||qb){ qc=(Polynomial)malloc(sizeof(struct LNode));switch(compare(qa,qb)){ case 1:
{ qc->data.coef=qa->data.coef;qc->data.expn=qa->data.expn;qa=qa->next;break;
} case 0:
{ qc->data.coef=qa->data.coef+qb->data.coef;qc->data.expn=qa->data.expn;qa=qa->next;qb=qb->next;break;
} case-1:
{ qc->data.coef=qb->data.coef;qc->data.expn=qb->data.expn;qb=qb->next;break;
}
} if(qc->data.coef!=0)
{ qc->next=hc->next;hc->next=qc;hc=qc;
} else free(qc);//当相加系数为0时，释放该结点
} pc=headc;return OK;}
5、求解并建立多项式a-b Status SubtractPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a-b，返回其头指针 LNode *h=pb;LNode *p=pb->next;LNode *pd,*pf;while(p){ //将pb的系数取反 p->data.coef*=-1;p=p->next;} AddPolyn(pa,h,pf);pd=pf;for(p=h->next;p;p=p->next)//恢复pb的系数 p->data.coef*=-1;pc=pd;return OK;} float ValuePolyn(Polynomial head,int x){ //输入x值，计算并返回多项式的值
LNode *p;int i,t;float sum=0;for(p=head->next;p;p=p->next){ t=1;for(i=p->data.expn;i!=0;)
{ if(i
} sum+=p->data.coef*t;} return sum;}
6、求解并建立导函数多项式
Status Polynomial_derivatePolyn(Polynomial P,Polynomial &pc)//求导 {
LNode *p,*pf,*ph;//用于遍历结点
p=P->next;
ph=(Polynomial)malloc(sizeof(struct LNode));
ph->next=NULL;
//pre=P;
while(p!=NULL)
{
pf=(Polynomial)malloc(sizeof(struct LNode));
if(p->data.expn==0)
{
p=p->next;
//free(p);
//p=pre->next;
}
else
{
pf->data.coef=p->data.coef*p->data.expn;
pf->data.expn=p->data.expn-1;
Insert(pf,ph);
p=p->next;
}
}
pc=ph;return OK;}
7、求解并建立多项式a*b Status MultiplyPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a*b，返回其头指针 LNode *hf,*pf;LNode *qa=pa->next;LNode *qb=pb->next;hf=(Polynomial)malloc(sizeof(struct LNode));//建立头结点 hf->next=NULL;for(;qa;qa=qa->next){ for(qb=pb->next;qb;qb=qb->next)
{ pf=(Polynomial)malloc(sizeof(struct LNode));pf->data.coef=qa->data.coef*qb->data.coef;pf->data.expn=qa->data.expn+qb->data.expn;Insert(pf,hf);//调用Insert函数以合并指数相同的项
} } pc=hf;return OK;}
8、函数的调用关系图
主函数Pa pb pc数meadreturn headc*h项回*h 建立链表Polyn CreatePolyn(Polyn head,int m)多项式相加Polyn AddPolyn(Polyn pa,Polyn pb)返回*hc返输出多项式While{Printf(“”);
四、调试分析
5.1 运行该程序的操作平台： 5.1.1 硬件要求：
此程序需在一台PC机上运行,要用INTER或AMD的CPU,其他没多大要求。5.1.2 软件要求：
本程序能在Visual C++ 6.0下运行。5.2 错误分析：
1、函数名拼写错误
2、括号匹配错误
3、变量类型名定义错误
4、分号没有在英文环境下输出，导致运行出错
5、参数表出现语法错误，函数调用的一组参数之间没有以逗号隔开，并以一个右括号结束
六、用户手册
1、本程序的执行文件为：Cpp1.exe。
2、进入演示程序后即显示文本方式的用户界面。
3、根据提示数字执行操作。如输入数字“1”
4、执行相应命令后显示操作结果。
七、测试结果
1、最初的界面
2、选择操作“1”、“2”“3”、“4”，输入数字得到的结果，即创建多项式a和b3、a+b4、a-b5、a*b6、求导
7、带入x值求a，b
八、心得体会
通过这次课程设计，我觉得我们对于《数据结构》的学习不仅包括理论部分的学习，还要勤动手，多实践。真正将这个程序做出来很不容易，但只要只要用心去做，总会有收获,特别是当我遇到问题时，通过向同学请教,最后终于找到方法时,并理解代码的含义时，心中是无比喜悦的。编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。
课 程 设 计 任 务 书信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏一、二、课程设计题目： 迷宫求解、一元多项式 课程设计主要参考资料： 数据结构（C语言版） 严蔚敏、吴伟......
数据结构课程设计题目（2013年）一、必做题 1、图书管理系统（线性表） [问题描述]设计一个程序，记录并统计图书使用情况。 [基本要求] （1）图书信息包括图书ID号，图书名，出版社名，出版年月......
课程设计题目1、运动会分数统计任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或......
《数据结构》课程设计报告学 号 姓 名 班 级 指导教师XXX XXX XXX XXX 安徽工业大学计算机学院2014年6月利用栈实现迷宫问题的求解一、问题描述以一个M*N的长方阵表示迷宫，0......
数据结构课程设计计算机科学与技术2008级1班课程设计题目：图书借阅管理系统 姓名：学号：一．需求分析说明图书借阅处理过程简述处理过程主要包含：新增图书上架、办理图证、图书查询......
