数据结构课设.docx
- 文档编号:13954565
- 上传时间:2023-06-19
- 格式:DOCX
- 页数:44
- 大小:183.88KB
数据结构课设.docx
《数据结构课设.docx》由会员分享,可在线阅读,更多相关《数据结构课设.docx(44页珍藏版)》请在冰点文库上搜索。
数据结构课设
《数据结构》课程设计报告
报告(论文)题目:
迷宫问题与排序算法的比较
作者所在系部:
计算机科学工程系
作者所在专业:
计算应用技术
作者所在班级:
作者学号:
作者姓名:
指导教师姓名:
贾振华
完成时间:
2013/1/3
北华航天工业学院教务处制
课题名称
《数据结构》课程设计
完成时间
2013.1.3
指导教师
贾振华
职称
教授
学生姓名
班级
总体设计要求
总体设计要求:
课程设计内容共给定6个题目,从中选2个题目。
每个题目都按课程设计详细要求,在规定的两周时间内完成。
选题要求:
1、2和3选一,4、5和6选一。
题目:
1、求集合的并、交、差集
2、迷宫问题
3、模拟停车场管理
4、简易家谱系统
5、交通咨询系统设计
6、排序算法的比较
工作内容及时间进度安排
第一周、周1:
设计动员,分组,布置课程设计任务。
第一周、周2:
查阅资料,制定方案,进行程序总体设计。
第一周、周3~第二周2:
详细设计,系统调试。
第二周、周3:
整理,撰写设计报告。
第二周、周3~周5:
验收,提交设计报告,评定成绩。
课程设计成果
1、课程设计报告书一份
2、源程序清单一份
摘要
本次课设目的在于检验学生在《数据结构》课程一学期中的学习成果,从而加深学生对所学知识的进一步理解与巩固。
本次课程设计过程中我主要根据课本中的实现思想及算法编写程序,体现以课本知识的应用为主,在学习了线性表、栈、队列、二叉树、树和图等结构的基础上,以能够更加熟练的应用所学知识,并能结合一些著名算法来实现对一些实际问题的应用,从而更为深刻理解数据结构的内涵,熟悉它们各自的应用场合及方法。
有些在平时课程中并没有掌握的内容在这次课程设计中都是先通过看课本学懂了,然后再在课程设计中加深印象,实现算法的应用和扩展。
这次课程设计的设计内容主要是通过实际的例子和程序来实现课本中所学习的算法的应用。
我主要做了迷宫问题、排序算法比较两个题目。
本文利用C++语言编写程序,分别实现了对自定义的迷宫有无路径的判定和几种排序算法的比较次数与移动次数的比较。
其中,迷宫问题以栈的应用为基础,随机生成迷宫,然后寻找所以路径并输出,对没有路径的迷宫,继续随机生成,直到生成存在路径的迷宫。
排序算法的比较是。
两个系统均已经过全面的测试,能够很好的运行,达到了预期的效果。
关键词:
数据结构迷宫直接插入、折半插入、冒泡、快速、选择等排序算法
目录
第1章绪论1
1.1课程设计选题的目的1
1.2课程设计选题的背景和意义1
1.2.1课程设计选题的背景1
1.2.2课程设计选题的意义2
1.3课题研究的主要内容2
第2章需求分析3
2.1功能说明3
2.1.1迷宫问题3
2.1.2排序算法的比较3
2.2输入说明4
2.2.1迷宫问题4
2.2.2排序算法的比较4
2.3输出说明4
2.3.1迷宫问题4
2.3.2排序算法的比较4
2.4测试数据4
2.4.1迷宫问题4
2.4.2排序算法的比较4
第3章概要设计5
3.1程序模块结构5
3.1.1迷宫问题5
3.1.2排序算法的比较5
第4章详细设计6
4.1定义的数据类型6
4.1.1迷宫问题6
4.1.2排序算法的比较10
第5章测试结果14
5.1迷宫问题14
5.2排序算法的比较15
总结17
致谢18
参考文献19
附录20
第1章绪论
随着信息产业的飞速发展,信息化管理及查询已经引入并应用到各行业管理领域,各
种形式的百货商场、大型仓储超市、便利店、连锁超市和专卖店等形式的零售业鳞次栉比不断改变、影响着人们的价值观念和生活方式。
因此,要提升企业竞争力,就要大力推进企业信息化建设,利用先进的办公自动化系统来实现企业内部信息管理、共享及交流,才能使企业在竞争激烈的21世纪取得先机。
1.1课程设计选题的目的
为大家解决一些生活中实际的问题,在这个过程中,编程人员自身的能力也在不断地提高。
此次程序设计综合运用所学知识解决实际问题,将课堂的书本知识有效的在程序中体现出来,让学生更理解了C++功能之强大,进一步让学生对面向对象的方法以及C++的编程思想有了较好了解和认识。
此外,此次设计培养独立开发、设计、调试、运行程序的能力,激发了学生较强的自学兴趣,锻炼学生之间以及学生与老师的交通能力,培养学生合作精神,让学生更好的认识到合作的重要性,使学生在今后的学习中加强对合作精神的培养。
1.2课程设计选题的背景和意义
1.2.1课程设计选题的背景
(1)迷宫问题
这是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫,迷宫中设置了很多隔壁,对前进方向形成了多出障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。
(2)排序算法的比较
编程实现直接插入、折半插入、冒泡、快速、选择等排序算法,并计算每种算法的比较、移动次数。
1.2.2课程设计选题的意义
一般来说,课程设计要比教学实验复杂一些,涉及的深度深,而且更加实用些。
其目的是通过课程设计的综合训练,培养学生分析解决实际问题和编程等动手能力,最终目标是想通过这种形式,帮助同学系统掌握C++这门课程的主要内容,使老师更好的完成教学任务。
结合实际应用的要求,使课程设计既覆盖教学所要求的知识点,又接近工程的实际需要,训练自己实际分析问题和解决问题以及编程的能力。
通过详细的实例分析,循环渐进的描述,启发学生顺利的完成设计。
课程设计将设计要求、需求分析、算法设计、编程和实例测试运行分开,为学生创造分析问题、独立思考的条件。
只要学生在吃透要求和算法的前提下,完全可以不按书中提示的参考程序,自己设计出更具有特色的程序。
1.3课题研究的主要内容
(1)迷宫问题
设计一个迷宫,实现以下功能:
1.试探方向限定为上、下、左、右四个方向。
2.迷宫要随机生成。
3.生成从迷宫入口到出口的最短和最长路径。
4.迷宫的入口和出口由键盘输入。
(2)排序算法的比较
编程实现直接插入、折半插入、冒泡、快速、选择等排序算法,并计算每种算法的比较、移动次数。
完成功能的详细说明:
1.要求由键盘输入待排序数据的个数和待排序数据。
2.实现直接插入、折半插入、冒泡、快速、选择等排序算法。
3.比较每种排序算法在排序码个数相同的情况下,排序过程中排序码的比较次数和元素的移动次数。
4.待排序数据量分别取n=10,30,50,100时,比较同一个算法在排序过程中排序码的比较次数和元素的移动次数。
5.输出结果中,给出各算法按两种方式进行比较后的结果。
第2章需求分析
2.1功能说明
2.1.1迷宫问题
系统总体说明:
这是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫,迷宫中设置了很多隔壁,对前进方向形成了多出障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。
完成功能的详细说明:
1.试探方向限定为上、下、左、右四个方向。
2.迷宫要随机生成。
3.生成从迷宫入口到出口的最短和最长路径。
4.迷宫的入口和出口由键盘输入。
2.1.2排序算法的比较
系统总体说明:
编程实现直接插入、折半插入、冒泡、快速、选择等排序算法,并计算每种算法的比较、移动次数。
完成功能的详细说明:
1.要求由键盘输入待排序数据的个数和待排序数据。
2.实现直接插入、折半插入、冒泡、快速、选择等排序算法。
3.比较每种排序算法在排序码个数相同的情况下,排序过程中排序码的比较次数和元素的移动次数。
4.待排序数据量分别取n=10,30,50,100时,比较同一个算法在排序过程中排序码的比较次数和元素的移动次数。
5.输出结果中,给出各算法按两种方式进行比较后的结果。
2.2输入说明
2.2.1迷宫问题
随机生成迷宫,由用户输入迷宫的行和列,入口出口由用户输入。
2.2.2排序算法的比较
用户输入待排序数据个数以及待排序的数据,选择排序方法。
2.3输出说明
2.3.1迷宫问题
用户输入数据完毕,程序将输出迷宫出口的路径
2.3.2排序算法的比较
用户输入完毕,程序根据指令输出相应的结果。
2.4测试数据
2.4.1迷宫问题
用户输入迷宫的行与列,迷宫入口及迷宫出口,程序输出结果
2.4.2排序算法的比较
用户输入测试数据及指令,程序根据指令输出相应的结果。
第3章概要设计
3.1程序模块结构
3.1.1迷宫问题
本程序包含主程序、入栈算法、出栈算法等。
(如下图)
3.1.2排序算法的比较
本程序包括主函数,顺序表的建立,直接插入排序算法,折半插入排序算法,冒泡排序算法,快速排序算法,选择排序算法。
(如下图)
第4章详细设计
4.1定义的数据类型
4.1.1迷宫问题
typedefstruct
{
intyuansu;//迷宫值
intx,y;
intflag;//进栈标志
intf;//方向
}nodetype;//迷宫信息的类型
nodetypedata[Maxsize][Maxsize];//迷宫数组
typedefstruct
{
intx,y;
}item;//移动方向的结构体
itemmove[4]={-1,0,0,1,1,0,0,-1};//移动方向的数组
typedefstruct
{
intx,y,f;
}DataType;//栈结点的类型
typedefstruct
{
DataTyped[Maxnum];//栈结点数组
inttop;
}path;//路径栈的结构体
2.栈的初始化及各函数的实现
voiddisplay_migong(inta,intb)
{
inti,j;
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
cout< cout< } } voidcreat(inta,intb,intr1,ints1,intr2,ints2) { inti,j; srand(time(NULL));//以当前时间为种子产生随意数,time(NULL)用来获取当前时间 for(i=1;i<=a;i++) { for(j=1;j<=b;j++)//对迷宫随机赋值 { data[i][j].yuansu=rand()%2; data[i][j].x=i; data[i][j].y=j; data[i][j].flag=0; data[i][j].f=-1;//将方向初值设为-1 } data[r1][s1].yuansu=data[r2][s2].yuansu=0;//出口入口设为0 } } voidpush(nodetype&n)//n是迷宫元素的类型 { p.top++; p.d[p.top].x=n.x; p.d[p.top].y=n.y; p.d[p.top].f=n.f; n.flag=1; } voidpop(DataType&t) { t.x=p.d[p.top].x; t.y=p.d[p.top].y; t.f=p.d[p.top].f; data[t.x][t.y].flag=0; p.top--; } voiddisplay() { inti=0; cout<<"路径为: "; while(i<=p.top) { cout<<"-->("< i++; } cout< } voidfind(inta,intb,intr1,ints1,intr2,ints2) { p.top=-1;//栈的初始化 inti,j; DataTypez;//栈的结点类型,有三个元素,返回z push(data[r1][s1]);//入栈 while(p.top! =-1) { while(p.d[p.top].f<4) { i=p.d[p.top].x+move[p.d[p.top].f].x;//改变搜索方向 j=p.d[p.top].y+move[p.d[p.top].f].y; if(data[i][j].yuansu==0&&data[i][j].flag==0)//若是通路则前进 { push(data[i][j]);//入栈,top增加1 data[i][j].f=0;//下一点搜索方向初始化 if(i==r2&&j==s2) { cout<<"-------------------------"< display(); pop(z);//出栈 p.d[p.top].f++; } } else p.d[p.top].f++; } pop(z);//出栈 p.d[p.top].f++; } cout<<"寻找结束! "< } 3.主函数 intmain() { intp,q; inta,b,r1,s1,r2,s2; q=1; cout<<"-------------------------"< cout<<"欢迎使用迷宫问题求解系统! "< cout<<"-------------------------"< while(q==1) { cout<<" (1)创建迷宫\n"; cout<<" (2)退出"< cin>>p; if(p==1) { cout<<"输入迷宫的宽度和长度格式为: (ab)"< cin>>a; cin>>b; cout<<"输入迷宫入口 cin>>r1>>s1; cout<<"输入迷宫出口 cin>>r2>>s2; if(a>100||b>100) { cout<<"对不起,迷宫长度或宽度过大,请重新输入! "< cout<<"《本系统最多处理"< q=1; } else { creat(a,b,r1,s1,r2,s2);//创建迷宫 cout<<"-------------------------"< display_migong(a,b);//输出迷宫 cout<<"-------------------------"< find(a,b,r1,s1,r2,s2);//搜索迷宫路径 q=1; } } elseif(p==2) { cout<<"谢谢使用迷宫求解系统! "< q=0; } else { cout<<"请输入正确操作! "< q=1; } } return0; } 4.1.2排序算法的比较 1.结点类型 typedefintDataType; intm=0,n=0;//定义全局变量比较次数和移动次数 2.顺序表的定义 typedefstruct { DataTypedata[MAXSIZE+10]; intlen;//顺序表的长度 }SeqList; voidInit_SeqList(SeqList&L)//初始化 { L.len=0; } 3.部分排序算法 voidSelectSort(SeqListL)//直接选择排序 { n=0; inti,j,s; DataTypetemp; for(i=1;i { s=i; for(j=i+1;j<=L.len;j++) if(L.data[j] { //m++; s=j; } if(s! =i) { n++; temp=L.data[i]; L.data[i]=L.data[s]; L.data[s]=temp; } } for(i=1;i<=L.len;i++) { cout< } cout< cout<<"直接选择排序的排序码的比较次数为: "<<((i*i-i)/2)<<""<<"元素的移动次数为: "< } voidBubbleSort(SeqListL)//冒泡排序 { inti,j,flag=1; m=0,n=0; DataTypex; for(i=1;((i<=L.len)&&(flag==1));i++) { m++; flag=0; for(j=1;j { m++; if(L.data[j]>L.data[j+1]) { n++; x=L.data[j]; L.data[j]=L.data[j+1]; L.data[j+1]=x; flag=1; } } } for(i=1;i<=L.len;i++) { cout< } cout< cout<<"冒泡排序的排序码的比较次数为: "< "< } 4主函数调用 switch(k) { case1: cout<<"用户自己输入数据来进行排序: "< Init_SeqList(L); set_SeqList(L); cout< break; case2: cout<<"排序前为: \n"; output_SeqList(L); cout<<"\n排序后为: \n"; SelectSort(L); break; case3: cout<<"排序前为: \n"; output_SeqList(L); cout<<"\n排序后为: \n"; BubbleSort(L); break; case4: cout<<"排序前为: \n"; output_SeqList(L); cout<<"\n排序后为: \n"; InsertSort(L); break; case5: cout<<"排序前为: \n"; output_SeqList(L); cout<<"\n排序后为: \n"; Binsertsort(L); break; case6: low=1,high=L.len; cout<<"排序前为: \n"; output_SeqList(L); cout<<"\n排序后为: \n"; QSort(L,low,high); Partition(L,low,high); for(i=1;i<=L.len;i++) { cout< } cout< cout<<"快速排序的排序码的比较次数为: "< "< break; case7: bijiao(L); break; case0: cout<<"您已安全退出系统."< break; default: cout<<"\n没有此选项.请重选: "< break; } } while(k! =0); } 第5章测试结果 5.1迷宫问题 第一个命令 输入1创建迷宫、指定出入口并输出路径 运行结果如图 第二个命令 输入2退出系统 运行结果如图 5.2排序算法的比较 主程序界面 输入1创建顺序表 选择各种排序算法运行结果 比较各种排序方法并输出结果 总结 本设计使用本学期学习的数据结构和C++的知识 课程设计是《数据结构》课程教学必不可缺的一个重要环节,可加深学生对该课程所学内容的进一步的理解与巩固,是将计算机课程与实际问题相联接的关键步骤。 通过课程设计,能够提高学生分析问题、解决问题,从而运用所学知识解决实际问题的能力,因而必须给予足够的重视。 本文实现了迷宫问题求所有路径;直接插入、折半插入、冒泡、快速、选择等排序算法的比较,但由于时间等各方面原因,仍有一些问没有解决,例如迷宫问题没有输出最短及最长路径等。 致谢 通过本次课程设计,我学会了利用线性表、栈、等数据结构来实现一些具体问题。 这次课程设计使我对本学期所学的知识有了更深刻的理解,体会到了各种数据结构优越性。 回顾本次课程设计,所用到的数据结构有线性表、栈、等,算法主要有直接插入、折半插入、冒泡、快速、选择等排序算法等。 通过这次课程设计,我还明白了实际进行程序设计时,应考虑各种数据的有效性、注意操作的方便,综合全面考虑,以达到方便用户使用的目的。 也学到了一些解决常见问题的方法。 非常感谢贾老师在这次课设中给予我的帮助,老师所教授的一些解决问题和分析问题的方法将使我终生受益。 参考文献 [1]李春葆,尹为民,李蓉蓉,蒋晶珏,喻丹丹,安杨。 数据结构教程(第三版)。 清华大学出版社。 2009年3月。 [2]刘振鹏,罗文劼,石强。 数据结构(第三版)。 中国铁道出版社。 2010年6月。 [3]严蔚敏,吴伟民。 数据结构(C语言版)。 清华大学出版社。 2009年9月。 [4]谭浩强。 C++面向对象程序设计。 清华大学出版社2006年1月。 [5]谭浩强。 C程序设计(第三版)。 北京: 清华大学出版社。 2005年。 附录
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构