数据结构课程设计.docx
- 文档编号:2697300
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:18
- 大小:59.59KB
数据结构课程设计.docx
《数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构课程设计
目录
1.绪论2
1.1前言2
1.2问题的提出2
2.课程设计目的3
3.需求分析4
3.1功能分析4
3.2设计思路4
4.概要设计5
4.1数据结构的选用5
4.2多项式的输入5
4.3主函数和其它函数5
5.流程图设计6
5.1函数调用关系6
5.2程序流程图7
6.程序代码8
7.调试运行15
8.总结17
参考文献18
摘要
在计算机科学中,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象(数据元素)以及它们之间的关系和运算等的学科,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
在许多类型的程序的设计中,数据结构的选择是一个基本的设计考虑因素。
许多大型系统的构造经验表明,系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。
许多时候,确定了数据结构后,算法就容易得到了。
有些时候事情也会反过来,我们根据特定算法来选择数据结构与之适应。
不论哪种情况,选择合适的数据结构都是非常重要的。
选择了数据结构,算法也随之确定,是数据而不是算法是系统构造的关键因素。
这种洞见导致了许多种软件设计方法和程序设计语言的出现,面向对象的程序设计语言就是其中之一。
经过一学期的学习我对数据结构的知识有所了解,运用我所学的知识来完成这个课程设计。
采用C语言编写,在对于多项式的存储和计算操作中大量依赖于指针和结构体。
通过尾插法建立链表,指数的比较来实现结点元素的相加减。
关键字数据结构多项式链表指针结构体
1.绪论
1.1前言
算机的应用已渗透到社会的各个领域,正在改变着人们的工作、学习和生活的方式,推动着社会的发展。
归纳起来可分为以下几个方面:
如科学计算(数值计算)、数据处理(信息处理)、自动控制、计算机辅助、人工智能、多媒体应用、计算机网络本系统用C语言作为程序语言,设计出的系统功能完善,操作方便灵活。
1.2问题的提出
一元稀疏多项式简单计数器基本功能要求:
(1)输入并建立多项式
(2)输出多项式,输出形式为整数序列:
n,c1,e1,c2,e2……cn,en,其中n是多项式的项数,ci,ei分别为第i项的系数和指数。
序列按指数降序排列。
(3)多项式a和b相加,建立多项式a+b,输出相加的多项式。
(4)多项式a和b相减,建立多项式a-b,输出相减的多项式。
用带表头结点的单链表存储多项式。
2.课程设计目的
使我们进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法,以及它们在程序中的使用方法。
使我们掌握软件设计的基本内容和设计方法,并培养学生进行规范化软件设计的能力。
使我们掌握使用各种计算机资料和有关参考资料,提高学生进行程序设计的基本能力。
熟练掌握数据结构这门课程,掌握线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用.进一步熟悉抽象数据类型的定义和实现、如何利用数组的动态分酚实现顺序结构、继承的实现方式。
学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适当的逻辑结构、想念结构及基相应的算法并初步掌握算法的时间分析和空间分析的技术。
基本掌握程序设计的基本思路和方法。
利用所学的基本知识和技能,解决简单的程序设计问题各算法描述培养我们的数据抽象能力。
3.需求分析
3.1功能分析
本程序要求输入并建立多项式,能够降幂显示出多项式,实现多项式相加相减的计算问题,输出结果。
3.2设计思路
采用链表的方式存储链表,定义结点结构体。
运用尾差法建立两条单链表,以单链表polynp和polynh分别表示两个一元多项式a和b。
为实现处理,社p、q分别指向单链表polya和polyb的当前项,比较p、q结点的指数项。
①若p->expn
②若p->expn=q->expn,则将两个结点中的系数相加,当和不为0时修改结点p的系数。
③若p->expn>q->expn,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移。
4.概要设计
4.1数据结构的选用
typedefstructPolynomial{
floatcoef;//系数
intexpn;//指数
structPolynomial*next;
}*Polyn,Polynomial;
4.2多项式的输入
PolynCreatePolyn(Polynhead,intm){
......
for(i=0;i { p=(Polyn)malloc(sizeof(structPolynomial)); printf("请输入第%d项的系数与指数: ",i+1); scanf("%f%d",&p->coef,&p->expn); Insert(p,head); } returnhead; } 4.3主函数和其它函数 voidmain() { intm,n,a,x; charflag; Polynpa=0,pb=0,pc; } voidDestroyPolyn(Polynp) voidPrintPolyn(PolynP) intcompare(Polyna,Polynb) PolynAddPolyn(Polynpa,Polynpb) PolynSubtractPolyn(Polynpa,Polynpb) 5.流程图设计 5.1函数调用关系 5.2程序流程图 6.程序代码 #include #include typedefstructPolynomial{//项的表示 floatcoef;//系数 intexpn;//指数 structPolynomial*next;//指针域 }*Polyn,Polynomial;//Polyn为结点指针类型 voidInsert(Polynp,Polynh){//插入或者合并 if(p->coef==0)free(p);//系数为0的话释放结点 else{ Polynq1,q2; q1=h;q2=h->next; while(q2&&p->expn q1=q2; q2=q2->next; } if(q2&&p->expn==q2->expn){//将指数相同相合并 q2->coef+=p->coef; free(p); if(! q2->coef){//系数为0的话释放结点 q1->next=q2->next; free(q2); } } else{//指数为新时将结点插入即p->expn>q2expn情况 p->next=q2; q1->next=p; } } }//Insert PolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式 inti; Polynp; p=head=(Polyn)malloc(sizeof(structPolynomial)); head->next=NULL; for(i=0;i p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据 printf("请输入第%d项的系数与指数: ",i+1); scanf("%f%d",&p->coef,&p->expn); Insert(p,head);//调用Insert函数插入结点 } returnhead; }//CreatePolyn voidDestroyPolyn(Polynp){//销毁多项式p Polynq1,q2; q1=p->next; q2=q1->next; while(q1->next){ free(q1);//释放q1 q1=q2;//指针后移,循环继续释放,直至销毁 q2=q2->next; } } voidPrintPolyn(PolynP){//输出多项式 Polynq=P->next; intflag=1;//项数计数器 if(! q){//若多项式为空,输出0 putchar('0'); printf("\n"); return; } while(q){ if(q->coef>0&&flag! =1)putchar('+');//系数大于0且不是第一项 if(q->coef! =1&&q->coef! =-1){//系数非1或-1的普通情况 printf("%g",q->coef); if(q->expn==1)putchar('X');//系数为1的情况 elseif(q->expn)printf("X^%d",q->expn); } else{ if(q->coef==1){ if(! q->expn)putchar('1'); elseif(q->expn==1)putchar('X'); elseprintf("X^%d",q->expn); } if(q->coef==-1){ if(! q->expn)printf("-1"); elseif(q->expn==1)printf("-X"); elseprintf("-X^%d",q->expn); } } q=q->next; flag++; }//while printf("\n"); }//PrintPolyn intcompare(Polyna,Polynb){ if(a&&b){ if(! b||a->expn>b->expn)return1; elseif(! a||a->expn elsereturn0; } elseif(! a&&b)return-1;//a多项式已空,但b多项式非空 elsereturn1;//b多项式已空,但a多项式非空 }//compare PolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b,返回其头指针 Polynqa=pa->next; Polynqb=pb->next; Polynheadc,hc,qc; hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(structPolynomial)); switch(compare(qa,qb)){//调用compare返回值 case1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case-1: { qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } }//switch if(qc->coef! =0){ qc->next=hc->next; hc->next=qc; hc=qc; } elsefree(qc);//当相加系数为0时,释放该结点 }//while returnheadc; }//AddPolyn PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a-b,返回其头指针 Polynh=pb; Polynp=pb->next; Polynpd; while(p){//将pb的系数取反 p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next)//恢复pb的系数 p->coef*=-1; returnpd; }//SubtractPolyn intmain(){//主函数 intm,n,flag=0; floatx; Polynpa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针,pa与pb在使用前付初值NULL printf("请输入a的项数: "); scanf("%d",&m); pa=CreatePolyn(pa,m);//建立多项式a printf("请输入b的项数: "); scanf("%d",&n); pb=CreatePolyn(pb,n);//建立多项式a //输出菜单 printf("**********************************************\n"); printf("操作提示: \n\t1.输出多项式a和b\n\t2.建立多项式a+b\n\t3.建立多项式a-b\n\t4.退出\n"); for(;;flag=0){ printf("执行操作"); scanf("%d",&flag); if(flag==1){//输出多项式 printf("多项式a: ");PrintPolyn(pa); printf("多项式b: ");PrintPolyn(pb);continue; } if(flag==2){//多项式相加 pc=AddPolyn(pa,pb);//调用函数,实现相加 printf("多项式a+b: ");PrintPolyn(pc); DestroyPolyn(pc);continue; } if(flag==3){//多项式相减 pd=SubtractPolyn(pa,pb); printf("多项式a-b: ");PrintPolyn(pd); DestroyPolyn(pd);continue; } if(flag==4)break;//结束循环,退出 DestroyPolyn(pa);//销毁多项式,释放内存 DestroyPolyn(pb); return0; } } 7.调试运行 (1)(2x+5x8-3.1x11)+(7-5x8+11x9) (2)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15) (3)(x+x2+x3)+0 (4)(x+x3)-(-x-x-3) 8.总结 我觉得写程序,应该先找到该程序中的核心地方,用多种方法来实现该核心,这才可能避免逻辑上或者编译器不支持上的错误。 这样花费大量时间在改程序上是很不值得的。 实践是检验真理的唯一标准,这句话很正确,如果没有实践,就不会发现和深刻体会它的真实所在。 只有通过检验的真理,在自己的心里,才会认可它的真实性。 面向对象程序设计的完成,使我们懂得了真理的重要性,理论和实际的相结合,才能真正把握所学和所掌握的知识。 埋头苦干的过程是苦涩的,在书山中查找资料的过程是疲倦的,但当课程设计完成时,那感觉是甜蜜的,没有耕耘,哪来得收获的喜悦,不懂付出怎么能知道回报的快乐,一分耕耘一分收获,有付出才会有回报,就在这样的痛与快乐的交换中,我学到了知识,学到了道理,学到了做人的道理。 总之,在这次的课程设计过程中,我收获了很多,既为我的以后学习设计有很大的帮助,也为将来的人生之路做好了一个很好的铺垫。 参考文献 严蔚敏,吴伟民著.数据结构(C语言版).北京: 清华大学出版社,2004. 谭浩强著.C语言程序设计.北京: 清华大学出版社,2005. 徐孝凯著.数据结构课程实验.北京: 清华大学出版社,2001 严蔚敏著.数据结构题集.北京: 清华大学出版社,2005. 刘大有著.数据结构(C语言版).高等教育出版社,2004.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计