数据结构课程设计实习报告
数据结构课程设计实习报告
（排序操作）
学 院：计算机学院
专 业：
班 级：
学 号：
姓 名：
指导教师：
完成日期：
目录
一、 需求分析……………………………………………… 1
1. 运行环境…………………………………………… 1
2. 程序所实现的功能………………………………… 1
3. 程序的输入………………………………………… 1
4. 程序的输出………………………………………… 1
二、 设计说明……………………………………………… 1
1. 算法设计的思想…………………………………… 1
2. 主要的数据结构设计说明………………………… 2
3. 程序的主要流程图………………………………… 3
4. 程序的主要模块 ………………………………… 3
5. 程序的主要函数及其伪代码说明………………… 4
三、 上机结果及体会……………………………………… 7
1. 实际完成的情况说明……………………………… 7
2. 程序算法的性能分析……………………………… 7
3. 程序运行时的初值和运行结果…………………… 8
4. 程序中可以改进的地方说明……………………… 11
5. 收获及体会………………………………………… 11
6. 源程序及注释……………………………………… 12
四、 参考文献……………………………………………… 19
一、需求分析
1. 运行环境：
软件环境：Microsoft Visual C++ 6.0。
2. 程序所实现的功能
本程序实现了直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序等多种排序算法的功能，并且对每一种而言，都能输出每一趟的排序结果。
3. 程序的输入：
本程序的输入的格式为：元素+空格+元素，并按回车键结束输入。如（49_38_65_97_76_13_27_49回车键），且本程序仅适用于整形数据。
4. 程序的输出：
本程序能输出每一趟的排序结果，且输出的格式和输入的格式基本一致。
二、设计说明
1. 算法设计的思想：
(1)直接插入排序的算法设计思想为：将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列R[1...i-1]中插入一个记录R[i]后，变成含有i个记录的有序的子序列R[1...i]；并且，和顺序表类似，为了在查找插入位置的过程中避免数组下标出界，在R[0]出设置监视哨。
(2)折半插入排序的算法思想为：在一个有序表中进行折半查找和插入。
(3)冒泡排序的算法思想为：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L->R[1].key>L->R[2].key），则将两个记录交换之，然后比较第二个记录的关键字和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。一般地，第i趟冒泡排序是从L->R[1]到L->R[n-i+1]依次比较相邻事物两个记录的关键字，并在“逆序”是交换记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。
(4)简单选择排序的算法设计思想为：通过n-i次关键字之间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换之。
(5)快速排序的算法设计思想为：通过每一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
(6)堆排序的算法设计思想为：将初始序列建成一个堆，若在输出堆顶的最小值后，使得剩余的n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反复执行，便能得到一个有序的序列。
(7)归并排序的算法设计思想为：假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[
]个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止。
2. 主要的数据结构设计说明：
(1)本程序的储存结构主要采用顺序表储存结构：
typedef struct{
int key; //关键字
}RedType; //记录类型
typedef struct{
RedType R[MAXSIZE+1];//R[0]闲置为哨兵
int length; //顺序表长度
}*SqList,sq; //顺序表类型
(2)本程序的输入与输出均采用了“do-while”语句，而主函数的功能选择采用了“case”语句。如下是输入函数的一段代码：
do {
i++;
scanf("%d%c",&L->R[i].key,&ch);
}while(ch!='\n');
3. 程序的主要流程图：
4. 程序的主要模块：
(1)菜单模块由Menu()函数实现。
(2)各排序功能：直接插入排序模块由InsertSort(SqList L)函数实现，折半插入排序模块由BInsertSort(SqList L)函数实现，冒泡排序模块由BubbleSort(SqList L)函数实现，简单选择排序模块由SelectSort(SqList L)函数和SelectMinKey(SqList L,int i)函数实现，快速排序模块由QSort(SqList L,int low ,int high)函数、QuickSort(SqList L)函数和Partition(SqList L,int low ,int high)函数实现，堆排序模块由HeapAdjust(SqList L,int s,int m)函数和HeapSort(SqList L)函数实现，归并排序模块由MergeSort(SqList L, int length)函数实现。
(3)输入与输出模块：输入模块由CreatSqList(SqList L)函数实现，输出模块由PrintSort(SqList L)函数和FiPrintSort(SqList L)函数实现。
5. 程序的主要函数及其伪代码说明：
(1)直接插入排序：
void InsertSort(SqList L){ //⑴直接插入排序
int i,j;
for(i=2;i<=L->length;++i){
if(L->R[i].key<L->R[i-1].key) //需将L->R[i]插入有序子表
{ L->R[0]=L->R[i]; //复制为哨兵
L->R[i]=L->R[i-1];
for(j=i-2;(L->R[0].key<L->R[j].key);--j)
L->R[j+1]=L->R[j]; //记录后移
L->R[j+1]=L->R[0]; //插入到正确的位置
}PrintSort(L); //输出排序结果
}a=1;}
(2)折半插入排序：
void BInsertSort(SqList L){ //折半插入排序
int i,j,m,low,high;
for(i=2;i<=L->length;++i){
L->R[0]=L->R[i]; //将L->R[i]暂存到L->R[0]
low=1;high=i-1;
while(low<=high) //在R[low..high]中折半查找有序插入的位置
{ m=(low+high)/2; //折半
if(L->R[0].key<L->R[m].key) high=m-1; //插入点在低区
else low=m+1; //插入点在高区 }
for(j=i-1;j>=high+1;--j)
L->R[j+1]=L->R[j]; //记录后移
L->R[high+1]=L->R[0]; //插入
PrintSort(L); //输出排序结果}
a=1; //将a重新初始化为}
(3)冒泡排序：
void BubbleSort(SqList L){ //冒泡排序；
int i,j,m;
for(i=1;i<L->length;i++){
for(j=0;j<L->length;j++)
{ //选择表L中最大的依次放到最后面的位置中去 if(L->R[j].key>L->R[j+1].key&&j<L->length){
m=L->R[j].key;L->R[j].key=L->R[j+1].key; L->R[j+1].key=m;}}
PrintSort(L); //输出排序结果 }
a=1;}
(4)简单选择排序：
void SelectSort(SqList L){ //简单选择排序
int i,j,m;
int SelectMinKey(SqList L,int i);
for(i=1;i<L->length;++i){ //选择第i小的记录，并交换到位
j=SelectMinKey(L,i); //在L->R[i..L->length]中选择key最小记录
if(i!=j){ //与第i个记录交换
m=L->R[i].key;L->R[i].key=L->R[j].key;L->R[j].key=m;}
PrintSort(L);}
a=1;}
(5)快速排序：
void QuickSort(SqList L){ //快速排序
QSort(L,1,L->length); //对顺序表L调用快速排序
a=1;}
void QSort(SqList L,int low ,int high){
int pivotloc;
if(low<high){
pivotloc=Partition(L,low,high);//L表一分为二
QSort(L,low,pivotloc-1); //对低位子表递归排序
QSort(L,pivotloc+1,high);//对高位子表递归排序}
(6)堆排序：
void HeapSort(SqList L){ //堆排序
int i,m;
for(i=L->length/2;i>0;--i) //把L->R[1..L->length]建成大顶堆
HeapAdjust(L,i,L->length);
for(i=L->length;i>1;--i){
m=L->R[1].key; //将堆顶记录和当前未经排序子序列L->R[1..i]中
L->R[1].key=L->R[i].key; //最后一个记录相互交换
L->R[i].key=m;
PrintSort(L);
HeapAdjust(L,1,i-1); //将L->R[1..i-1]重新调整为大顶堆 }
a=1;}
(7)归并排序：
void MergeSort(SqList L, int length){ //归并排序
int i, left_min, left_max, right_min, right_max, next;
int *tmp = (int*)malloc(sizeof(int) * length);
if (tmp == NULL) {
fputs("Error: out of memory\n", stderr);}
for (i = 1; i < length; i *= 2) {// i为步长，1,2,4,8……
for (left_min = 1; left_min <= length-i; left_min = right_max){
right_min=left_max = left_min+i; right_max=left_max + i;
if (right_max > length){ right_max = length+1;}
next = 1;
while (left_min < left_max && right_min < right_max){
tmp[next++] = L->R[left_min].key >L->R[right_min].key ? L->R[right_min++].key : L->R[left_min++].key;}
while (left_min < left_max){
L->R[--right_min].key = L->R[--left_max].key; }
while (next > 1){ L->R[--right_min].key = tmp[--next];} }
PrintSort(L);}
a=1; free(tmp);}
三、上机结果及体会
1. 实际完成的情况说明：
本程序基本完成了直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序以及归并排序的算法功能，并能输出各种排序算法的每一趟排序结果。
本程序仅支持整形数据（int 类型）。
2. 程序算法的性能分析：
3. 程序运行时的初值和运行结果：
(1)直接插入排序：
(2)折半插入排序：
(3)冒泡排序：
(4)简单选择排序：
(5)快速排序：
(6)堆排序：
(7)归并排序：
4. 程序中可以改进的地方说明
本程序对误操作的处理不是很理想，而且对数据的要求也比较严格，只能是int类型的数据才行，另外，堆排序不能将生成的堆以二叉树的形式输出。以上这些都是可以改进的地方。
5. 收获及体会：
通过这次课程设计的学习让我学会了许多。让我对数据结构知识有了很大理解！在这次课程设计中，我独立完成了直接插入排序、折半插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序等几种排序算法。虽然在算法完成的过程中出现了好多问题，但我对这次课程设计的成果还是非常满意的。
这次的课程设计还有很多不足之处，如用指针代替函数的调用。在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。我撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。 但我还是认为自己有些不足，希望以后能弥补这些不足。所以，这次的课程设计我学会了很多，不光让我认识了数据结构知识，还让我学会了一些道理，那就是做事情的时候即使不会做也不能慌张，要慢慢放下心来，不要光想着自己怎么、怎么不会了！不要去想不会，而是冷下心来慢慢思考、思考。这样你就会有了思路的。
6. 源程序及注释：
#include<stdio.h>
#include<windows.h>
# define MAXSIZE 30 //顺序表的最大长度
int a=1; //全局变量，用于标记排序的趟数
typedef struct{
int key; //关键字
}RedType; //记录类型
typedef struct{
RedType R[MAXSIZE+1];//R[0]闲置为哨兵
int length; //顺序表长度
}*SqList,sq; //顺序表类型
Void PrintSort(SqList L){ //输出函数
int i=1;
printf("########################################################################\n");printf("第%d 趟排序结果为:",a++);
while(i<=L->length){ printf("%d ",L->R[i].key);i++;} printf("\n"); }
void FiPrintSort(SqList L) { //输出最终结果
int i=1;
printf("########################################################################\n");printf("最终的排序结果为:");
while(i<=L->length){ printf("%d ",L->R[i].key); i++;} printf("\n"); }
int CreatSqList(SqList L){ //顺序表的创建
int i=0; int j=1; char ch;
printf("########################################################################\n"); printf("请输入待排整数(整数之间用空格隔开,按回车结束):");
do{ i++; scanf("%d%c",&L->R[i].key,&ch); }while(ch!='\n');
L->length=i;
printf("########################################################################\n"); printf("初始的待排序列为:");
while(j<=L->length){ printf("%d ",L->R[j].key); j++; } printf("\n"); return 1; }
int artition(SqList L,int low ,int high){
int key; //枢纽记录
L->R[0]=L->R[low]; //表的第一元素记录枢纽关键字
key=L->R[low].key;
while(low<high){
while(low<high&&L->R[high].key>=key)--high;//将比枢纽记录小的移到低端
L->R[low]=L->R[high];
while(low<high&&L->R[low].key<=key)++low; //将比枢纽记录大的移到高端
L->R[high]=L->R[low];}
L->R[low]=L->R[0]; //枢纽记录到位
PrintSort(L); //输出排序结果
return low;
void sertSort(SqList L){ //直接插入排序
int i,j;
for(i=2;i<=L->length;++i){
if(L->R[i].key<L->R[i-1].key) //需将L->R[i]插入有序子表
{ L->R[0]=L->R[i]; //复制为哨兵
L->R[i]=L->R[i-1];
for(j=i-2;(L->R[0].key<L->R[j].key);--j) L->R[j+1]=L->R[j];//记录后移
L->R[j+1]=L->R[0]; //插入到正确的位置}
PrintSort(L); //输出排序结果}
a=1;
void BInsertSort(SqList L){ //折半插入排序
int i,j,m,low,high;
for(i=2;i<=L->length;++i){
L->R[0]=L->R[i]; //将L->R[i]暂存到L->R[0]
low=1;high=i-1;
while(low<=high){ //在R[low..high]中折半查找有序插入的位置
m=(low+high)/2; //折半
if(L->R[0].key<L->R[m].key) high=m-1; //插入点在低区
else low=m+1; //插入点在高区}
for(j=i-1;j>=high+1;--j)
L->R[j+1]=L->R[j]; //记录后移
L->R[high+1]=L->R[0]; //插入
PrintSort(L); //输出排序结果}
a=1; //将a重新初始化为1}
void BubbleSort(SqList L){ //冒泡排序
int i,j,m;
for(i=1;i<L->length;i++){
for(j=0;j<L->length;j++){ //选择表L中最大的依次放到最后面的位置中去 if(L->R[j].key>L->R[j+1].key&&j<L->length){
m=L->R[j].key; L->R[j].key=L->R[j+1].key; L->R[j+1].key=m;}}
PrintSort(L); //输出排序结果 }
a=1;}
void SelectSort(SqList L){ //简单选择排序
int i,j,m;
int SelectMinKey(SqList L,int i);
for(i=1;i<L->length;++i){ //选择第i小的记录，并交换到位
j=SelectMinKey(L,i); //在L->R[i..L->length]中选择key最小记录
if(i!=j){ //与第i个记录交换
m=L->R[i].key; L->R[i].key=L->R[j].key; L->R[j].key=m; }
PrintSort(L);}
a=1;}
int SelectMinKey(SqList L,int i){ //在L->R[i..L->length]中选择key最小记录
int m=i,n=L->R[i].key;
for(;i<=L->length;i++){
if(n>=L->R[i].key){ n=L->R[i].key;m=i;}}
return m;}
void QSort(SqList L,int low ,int high){
int pivotloc;
if(low<high){
pivotloc=Partition(L,low,high);//L表一分为二
QSort(L,low,pivotloc-1); //对低位子表递归排序
QSort(L,pivotloc+1,high);//对高位子表递归排序}}
Void QuickSort(SqList L){ //快速排序
QSort(L,1,L->length); //对顺序表L调用快速排序
a=1;}
void HeapAdjust(SqList L,int s,int m){ //已知L->R[s..m]中记录的关键字除
int i,j; //L->[s].key之外均满足堆的定义，本函数调整
![i=L->R[s].key;](https://upload2.fanwen118.com/wk001/2743233/2743233_img_026.png)
//L->R[s] 的关键字，使L->R[s..m]成为一个大顶堆(对其中记录的关键字而言)
for(j=2*s;j<=m;j*=2){ //沿key较大的孩子结点向下筛选
if(j<m&&(L->R[j].key<L->R[j+1].key))
++j; //j为key较大的记录的下标
if(!(i<L->R[j].key)) //i应插入在位置上
break;L->R[s].key=L->R[j].key; s=j;} //插入
L->R[s].key=i;}
void HeapSort(SqList L){ //堆排序
int i,m;
for(i=L->length/2;i>0;--i) //把L->R[1..L->length]建成大顶堆
HeapAdjust(L,i,L->length);
for(i=L->length;i>1;--i){
m=L->R[1].key; //将堆顶记录和当前未经排序子序列L->R[1..i]中
L->R[1].key=L->R[i].key; //最后一个记录相互交换
L->R[i].key=m; PrintSort(L);
HeapAdjust(L,1,i-1); //将L->R[1..i-1]重新调整为大顶堆 }
a=1; }
void MergeSort(SqList L, int length){ //归并排序
int i, left_min, left_max, right_min, right_max, next;
int *tmp = (int*)malloc(sizeof(int) * length);
if (tmp == NULL){ fputs("Error: out of memory\n", stderr); }
for (i = 1; i < length; i *= 2){ // i为步长，1,2,4,8……
for (left_min = 1; left_min <= length-i; left_min = right_max){
right_min=left_max = left_min+i;
right_max=left_max + i;
if (right_max > length){ right_max = length+1; }
next = 1;
while (left_min < left_max && right_min < right_max){
tmp[next++]=L->R[left_min].key>L->R[right_min].key? L->R[right_min++].key : L->R[left_min++].key; }
while (left_min < left_max){
L->R[--right_min].key = L->R[--left_max].key; }
while (next > 1){
L->R[--right_min].key = tmp[--next]; } } PrintSort(L);}
a=1; free(tmp); }
void Menu(){ //菜单
printf("\t*********************欢迎使用本排序系统*********************\n");
printf("\t************************************************************\n\n");
printf("\t☆★ 直接插入排序 (InsertSort)-----------------请输入1 ★☆\n\n");
printf("\t☆★ 折半插入排序 (BinaryInsertSort)-----------请输入2 ★☆\n\n");
printf("\t☆★ 冒泡排序 (BubbleSort)-----------------请输入3 ★☆\n\n");
printf("\t☆★ 选择排序 (SelectSort)-----------------请输入4 ★☆\n\n");
printf("\t☆★ 快速排序 (QuickSort)------------------请输入5 ★☆\n\n");
printf("\t☆★ 堆排序 (HeapSort)-------------------请输入6 ★☆\n\n");
printf("\t☆★ 归并排序 (MergetSort)-----------------请输入7 ★☆\n\n");
printf("\t☆★ 退出 (Exit)-----------------------请输入8 ★☆\n\n");
printf("\t************************************************************\n"); }
void main(){ //主函数
int n,b=0; sq list={{0},0}; //初始化
SqList L=&list;
system("cls"); //清屏
Menu();
do{
printf("\t请您选择(1--8)(^_^):"); scanf("%d",&n); getchar();
if(n>=1&&n<=8){ b=1; break; }
else{ b=0;printf("\t您输入有误，请重新选择!\n"); }
}while(b==0);
while(b==1){
switch(n) { //用于菜单功能选择
case 1:system("cls"); //清屏
printf("\t\t◆◇◆◇直接插入排序(InsertSort)◆◇◆◇\n\n");
CreatSqList(L); InsertSort(L); FiPrintSort(L);
printf("########################################################################\n"); system("pause"); main(); break;
case 2:system("cls");
printf("\t\t◆◇◆◇折半插入排序(BinaryInsertSort)◆◇◆◇\n\n");
CreatSqList(L); BInsertSort(L); FiPrintSort(L);
printf("########################################################################\n"); system("pause"); main(); break;
case 3:system("cls");
printf("\t\t◆◇◆◇冒泡排序(BubbleSort)◆◇◆◇\n\n");
CreatSqList(L); BubbleSort(L); FiPrintSort(L);
printf("########################################################################\n"); system("pause"); main(); break;
case 4:system("cls");
printf("\t\t◆◇◆◇选择排序(SelectSort)◆◇◆◇\n\n");
CreatSqList(L); SelectSort(L); FiPrintSort(L);
printf("########################################################################\n"); system("pause"); main(); break;
case 5:system("cls");
printf("\t\t◆◇◆◇快速排序(QuickSort)◆◇◆◇\n\n");
CreatSqList(L); QuickSort(L); FiPrintSort(L);
printf("########################################################################\n"); system("pause"); main(); break;
case 6:system("cls");
printf("\t\t◆◇◆◇堆排序(HeapSort)◆◇◆◇\n\n");
CreatSqList(L); HeapSort(L); FiPrintSort(L);
printf("########################################################################\n"); system("pause"); main(); break;
case 7:system("cls");
printf("\t\t◆◇◆◇归并排序(MergeSort)◆◇◆◇\n\n");
CreatSqList(L); MergeSort(L,L->length); FiPrintSort(L);
printf("########################################################################\n"); system("pause"); main(); break;
case 8:system("cls"); exit(0); break;
default :break; } }
}
四、参考文献
1.数据结构（C语言版） 严蔚敏 吴伟民 编著 清华大学出版社 20##年5月第36次印刷。
-
数据结构课程设计报告模板
课程设计说明书课程名称：数据结构与算法专业：计算机科学与技术班级：103013姓名：XXX学号：03指导教师：XXX完成日期：20…
-
数据结构课程设计报告(含代码)
西安郵電學院数据结构课程设计报告题目校园导航系统院系名称计算机学院专业名称计算机科学与技术班级学生姓名学号8位指导教师设计起止时间…
-
《数据结构课程设计报告》
安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称课题名称用三元组实现稀疏矩阵的转置相加相乘专业计算机科学与技术班级学号AA姓…
-
数据结构课程设计报告
扬州大学信息工程学院数据结构课程设计报告题目井字棋小游戏班级学号姓名指导教师一课程题目井字棋小游戏二需求分析计算机和人对弈问题计算…
-
数据结构课程设计报告(模版)
攀枝花学院学生课程设计论文题目学生姓名学号20xx108010所在院系数学与计算机学院专业计算机科学与技术专业班级20xx级计算机…
-
课程设计实践报告
中南大学本科生课程设计(实践)任务书、设计报告(大学计算机基础)题目时间旅行学生姓名龙辰指导教师刘光瑜学院化学化工学院高级工程人才…
-
大学计算机基础课程设计实践报告
中南大学本科生课程设计(实践)任务书、设计报告(大学计算机基础)题目学生姓名指导教师学院专业班级学生学号课程设计实践报告计算机基础…
-
课程设计实训总结
钢筋混凝土结构课程设计说明书题目钢筋混凝土整体式单向板肋形楼盖设计基础工程一班谢世瀚111102143广东水利电力职业技术学院市政…
-
课程设计(实训)报告模板
广州航海高等专科学校课程设计实训报告课程ASPNET程序设计基础与实训教程题目网络课程生成系统专业计算机应用技术指导教师王琢成绩班…
-
电子课程设计实习报告
河南科技学院机电学院电子课程设计报告题目声光控制器设计专业班级应用电子技术教育111姓名张胜林20xx0325117时间20xx1…
-
数据库课程设计实践报告
中南大学本科生课程设计(实践)任务书、设计报告（SQL数据库程序设计）题目学生姓名指导教师学院专业班级学生学号网吧会员管理系统戴云…