数据结构课程设计报告模板Word文档下载推荐.docx
《数据结构课程设计报告模板Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告模板Word文档下载推荐.docx（10页珍藏版）》请在冰点文库上搜索。
年月日
目录
1需求分析4
2概要设计4
3详细设计4
4调试分析4
5测试结果4
6课设总结5
7参考文献5
数据结构课程设计报告
1需求分析
1.1程序的功能快速排序
分别用直接插入排序、折半插入排序、希尔排序、2-路插入排序、快速排序、选择排序、堆排序、归并排序、二叉排序树排序、冒泡排序、LSD基数排序对数据文件student.txt的内容根据学号进行升序排序
直接插入排序：
将某一个元素与顺序表中元素进行比较，然后插入到相应的位置，使整个顺序表处于有序状态。
折半插入排序：
是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变。
希尔排序：
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
2-路插入排序：
是一种在折半插入排序的基础上进行的改进，目的是减少排序过程中记录移动的次数的排序。
快速排序：
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
选择排序:
选择排序（Selectionsort）是一种简单直观的排序算法。
它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
堆排序：
堆排序就是把堆顶的最大数取出,将剩余的堆继续调整为最大堆,具体过程在第二块有介绍,以递归实现剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束的排序。
归并排序：
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DivideandConquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
二叉排序树排序
1.输出形式
程序中所涉及到的输入数据和输出数据简单说明。
（测试数据及结果数据以什么样的文件存放。
）
2概要设计
1.子函数功能介绍
把n个待排序的元素看成为一个有序表和一个无需表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素。
排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次即可完成排序过程。
折半插入排序
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=（low+high）/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域（即high=m-1），否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<
=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；
然后，取第二个增量d2<
d1重复上述的分组和排序，直至所取的增量
=1（
<
…<
d2<
d1），即所有记录放在同一组中进行直接插入排序为止。
设一个和原始待排序列L相同的数组D，首先将L[1]复制给D[1]，并把D[1]看成是已排好序的序列中处于中间位置的元素，之后将L中的从第二个元素开始依次插入到数组D中，大于D[1]的插入到D[1]之后的序列（此处我称为右半边序列，用的是数组左半部分空间），小于D[1]的插入到D[1]之前的序列（左半边序列，用的是数组右半部分空间）。
快速排序是找出一个元素（理论上可以随便找一个）作为基准（pivot）,然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。
递归快速排序，将其他n-1个元素也调整到排序后的正确位置。
最后每个元素都是在排序后的正确位置，排序完成。
所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
选择排序：
首先以一个元素为基准，从一个方向开始扫描，比如从左到右扫描，以A[0]为基准，接下来从A[0]….A[9]中找出最小的元素，将其与A[0]交换。
然后将其基准位置右移一位，重复上面的动作，比如，以A[1]为基准，找出A[1]~A[9]中最小的，将其与A[1]交换。
一直进行到将基准位置移到数组最后一个元素时排序结束。
利用大顶堆（小顶堆）堆顶记录的是最大关键字（最小关键字）这一特性，使得每次从无序中选择最大记录（最小记录）变得简单。
1）将初始待排序关键字序列（R1,R2....Rn）构建成大顶堆，此堆为初始的无须区；
2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区（R1,R2,......Rn-1）和新的有序区（Rn）,且满足R[1,2...n-1]<
=R[n];
3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区（R1,R2,......Rn-1）调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区（R1,R2....Rn-2）和新的有序区（Rn-1,Rn）。
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；
否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
二叉排序树排序：
2．函数的调用关系
3详细设计
1.主函数流程图
2.所用到的数据结构的知识及相关数据结构的描述形式
3.详细介绍本人所承担部分的函数实现过程
4调试分析
测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？
问题如何解决？
），算法的改进设想。
5测试结果
说明输入的数据，看到的结果。
（结果用截图展示！
6课设总结
1.收获
2.心得体会
总结可以包括:
课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。
7参考文献
为了反映论文的科学依据和作者尊重他人研究成果的严肃态度以及向读者提供有关信息的出处，应列出本课程设计所涉及的主要参考文献。
正文格式要求：
1.首行空二个汉字；
2.字体为“宋体，小四号，行距固定值20磅”，数字、西文字母等用TimesNewRoman字体；
3.文中的图形，在图下用图号和图名说明。
图1二叉树
参考文献格式：
1.参考文献要求不少于5篇，且确实参考了其中的内容，切忌虚列；
2.首行空二个汉字；
3.字体为“宋体，小四号，行距固定值20磅”，数字、西文字母等用TimesNewRoman字体；
4.参考示例：
1刘国钧，陈绍业，王凤翥.图书馆目录.第1版.北京：
高等教育出版社，1957
2傅承义，陈运泰，祁贵中.地球物理学基础.北京：
科学出版社，1985，447
3华罗庚，王元.论一致分布与近似分析.中国科学，1973（4）：
339~357
4张筑生.微分半动力系统的不变集研究[学位论文].北京：
数学系统学研究所，1983
5BorkoH，BernierCL．Indexingconceptsandmethods.NewYork:
AcademicPr,1978
课设考核内容
序号
评价内容
权重（%）
得分
1
考勤记录、学习态度、工作作风与表现。
5
2
自学情况：
上网检索机时数、文献阅读情况（笔记）。
10
3
课设选题是否先进，是否具有前沿性或前瞻性。
4
成果验收：
是否完成设计任务；
能否运行、可操作性如何等。
20
报告的格式规范程度、是否图文并茂、语言规范及流畅程度；
主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；
是否提出了自己的独到见解。
30
6
文献引用是否合理、充分、真实。
7
答辩情况：
自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。
25
合计
特别要求：
1.每位同学上交的最终报告包括打印版和电子版。
1）打印版要求用标有“课程设计”的专用档案袋上交，并且是每位同学单独装袋，并贴好相关的封条。
2）电子版以小组为单位上交，也就是组员交给组长，由组长收齐后放在一个文件夹里，另外在文件夹里还要放一个文件：
调试通过的源程序。
再交到学委处，最后由学委交给我。
2.要求每位同学必须在机房完成课设，如有笔记本的可带到机房。
升级会员 