数据结构课程设计实习报告。
题目：几种排序算法的演示。
一、需求分析。
1. 运行环境（软、硬件环境）
visual studio 2005；
2. 程序所实现的功能：
运用相关排序算法实现一组数据重排（按从小到大显示）；
3. 程序的输入：
本程序要求使用者先选择输入测试数的个数，再输入对应数目的一组整形数据；
输入数据过程中请以空格分隔各元素并以回车键结尾；
4. 程序的输出：
本程序将根据不同算法输出每一趟排序所对应的结果；
每个选择运行完成之后将会有提示选择是否继续；
5. 测试数据，如果程序输入的数据量比较大，需要给出测试数据：
8 -4 6 5 9 0 2（7个）
二、 设计说明。
1. 算法设计的思想。
冒泡排序。
将第1个记录的关键字与第2个记录的关键字进行比较，若为逆序，即arr[0].key>arr[1].key，则交换；然后比较第2个记录与第3个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果是关键字最大的记录被安置在最后一个记录位置上。
将第1个记录的关键字与第2个记录的关键字进行比较，若为逆序，即arr[0].key>arr[1].key，则交换；然后比较第2个记录与第3个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果是关键字最大的记录被安置在最后一个记录位置上。
重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。
快速排序。
任取排序表中的某个数据元素(例如取第一个数据元素)作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表：左侧子表中所有数据元素的关键字都小于基准数据元素的关键字，右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个子表中间(这也是该数据元素最终应安放的位置)， 然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为1，则排序结束。
直接插入排序。
每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。
开始时建立一个初始的有序序列，它只包含一个数据元素。
然后，从这个的初始序列开始不断进行插入数据元素，直到最后一个数据元素插入到有序序列后，整个排序工作就完成了。
折半插入排序。
每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。
开始时建立一个初始的有序序列，它只包含一个数据元素。
然后，从这个的初始序列开始不断利用折半查找方法寻找arr[i]的插入位置。进行插入数据元素，直到最后一个数据元素插入到有序序列后，整个排序工作就完成了。
简单选择排序。
第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下n-1个数据元素中再选取关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟(例如第i趟，i＝1，…，n-1)总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。
等到第n-1趟选择结束，待排序数据元素仅剩下1个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。
堆排序。1）对排序表中的数据元素，利用堆的调整算法形成初始堆。
2）输出堆顶元素。
3）对剩余元素重新调整形成堆。
4）重复执行第（2)、(3)步，直到所有数据元素被输出。
归并排序。
假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表(以后称它们为归并项)，先做两两归并，得 n/2 个长度为2的归并项(如果n为奇数，则最后一个归并项的长度为1)；
再做两两归并，……如此重复，最后得到一个长度为n的有序序列。
2. 主要的数据结构设计说明。
用顺序表作为排序表的抽象数据类型；另外还包括7个排序函数的模板类。
3. 程序的主要流程图。
4. 程序的主要模块，要求对主要流程图**现的模块进行说明。
templateclass sortlist;//对函数的操作。
templateclass element;//数据元素关键字及其他信息。
voidmerge(sortlist&sourcetable,sortlist&mergedtable,constintleft,constintmid,constint right);/归并。
voidmergepass(sortlist&sourcetable,sortlist&mergedtable,constintlen);/一趟归并。
void mergesort(sortlist&table);/两路归并。
templatevoid bubblesort(sortlist& table)//冒泡排序。
templatevoid quicksort(sortlist&table,intlow,int high)//快速排序。
templatevoid insertion(sortlist&table)//直接插入排序。
templatevoid binaryinsert(sortlist&table)//折半插入排序。
templatevoid selectsort(sortlist&table)//选择排序。
templatevoid sift(sortlist&table, int low, int high)//堆排序调整。
templatevoid heapsort(sortlist&table, int n)//堆排序。
5. 程序的主要函数及其伪**说明 (不需要完整的**)
sortlist构造函数。
sortlist(type a,int d)
currentsize=d;
交换函数。void swap(element&x,element&y)
输出函数。void print()
cout< }
归并排序模板类。
a) 归并。
void merge(sortlist&sourcetable,sortlist&
mergedtable,constintleft,constintmid,constint right)
else j++;k++;
if(i<=mid)else
b)一趟归并。
voidmergepass(sortlist&sourcetable,sortlist&
mergedtable,constintlen)
if(i+len<=currentsize-1)
merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);
elsefor(intj=i;j<=currentsize-1;j++)
for(int j=0;j<=currentsize-1;j++)
c)二路归并。
voidmergesort(sortlist&table)
冒泡排序。templatevoid bubblesort(sortlist& table)
cout<<"冒泡排序：" int s=0,t=0; while(i< t++;finish=1; for(int j=0;j< if(> 课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2... 数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。... 班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...数据结构课程设计
数据结构课程设计
数据结构课程设计