C语言内部结构.docx

信息工程学院设计性实验报告

专业：计算机科学与技术 班级：15级计科二班 2016-2017-1
课程名称
数据结构与算法实验
指导教师
朱振伸
本组成员
学号姓名
学号： 1501110241 姓名：刘翱寒
实验地点
XK2-413
实验时间
2016.12.22
实验名称
内部排序
实验类型
设计性
一、 实验目的
1.掌握排序的有关概念和特点。
2.掌握常见的排序算法的思想及其适用条件。
3.掌握常见的排序算法的程序实现。
二、实验设备
Microsoft Visual C++6.0
三、实验内容
输入一组关键字序列分别实现直接插入排序、折半插入排序和希尔排序算法。实现冒泡排序和快速排序算法。实现简单选择排序和堆排序算法.实现归并排序算法。试用各种排序算法进行排序。
四、实验步骤
#include<stdio.h>
#include<stdlib.h>
#include<process.h>
typedef struct datatype{
int node,data;
}dtype;
dtype a[1000];
int n,sum1,sum2;//sum1记录比较次数，sum2移动次数
void readln(){//用文件读入待排序数据
int i;
FILE *f1;
f1=fopen("a300.txt","r");
fscanf(f1,"%d",&n);
for(i=1;i<=n;i++){
a[i].node=i;
fscanf(f1,"%d",&a[i].data);
}
fclose(f1);
}
void bubblesort(){//冒泡排序
int i,j;
dtype t;
for(i=n-1;i;i--)
for(j=i;j<n;j++){
sum1++;
if(a[j].data>a[j+1].data){
t=a[j];a[j]=a[j+1];a[j+1]=t;sum2++;
}
}
}
void qsort(int l,int r){//快速排序
int i,j,m;
dtype t;
i=l;j=r;m=a[l].data;sum2++;
while(i<=j){
while(a[i].data<m)i++,sum1++;
while(a[j].data>m)j--,sum1++;
if(i<=j){
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;sum2++;
}
}
if(j>l)qsort(l,j);
if(i<r)qsort(i,r);
} void insertsort(){//插入排序
int i,j,m;
for(i=2;i<=n;i++){
a[0]=a[i];
m=a[0].data;
j=i-1;sum2++;
}while(a[j].data>m)
a[j+1]=a[0];
sum2++;
}
}
void shellsort(int d){//隔了d个数的插入排序
int i,j,m,k;
for(i=1;i
for(j=i+d;j<=n;j+=d){
a[0]=a[j];
m=a[0].data;
k=j-d;sum2++;
while(k>0&&a[k].data>m){
a[k+d]=a[k];
k-=d;sum2++;sum1++;
}
a[k+d]=a[0];sum2++;
}
}
void shells(){//希尔排序
int i,m,d[100];
printf("Input the sum of your shellarray:\n");
scanf("%d",&m);
printf("Input your shellarray:\n");
for(i=1;i<=m;i++)
scanf("%d",&d[i]);
while(getchar()!=10);
for(i=m;i;i--)shellsort(d[i]);
}
void selectsort(){//选择排序
int i,j,k,m;
dtype t;
for(i=1;i<n;i++){
m=a[i].data;k=i;sum2++;
for(j=i+1;j<=n;j++){
sum1++;
if(a[j].data<m){
m=a[j].data;k=j;
sum2++;
}
}
t=a[k];a[k]=a[i];a[i]=t;
sum2++;
}
}
void create(int i){//创建堆
Int m;
a[0]=a[i];m=a[0].data;sum2++;
while(a[i/2].data<m){
a[i]=a[i/2];
i/=2;//a[0]起了哨兵作用保证i值不为0
sum1++;sum2++;
}
a[i]=a[0];sum2++;
}
void treesort(int i){//排序的一步并维护堆
int j,m; a[0]=a[i];m=a[0].data;a[i]=a[1];j=1;i--;sum2++
while(2*j<i){
sum1++;sum2++;
}
if(a[2*j].data>m)
if(a[2*j+1].data>a[2*j].data){a[j]=a[2*j+1];j=2*j+1;}
else{a[j]=a[2*j];j=2*j;}
Else
if(a[2*j+1].data>m){a[j]=a[2*j+1];j=2*j+1;}
else break;
} if(2*j==i)
if(a[2*j].data>m){a[j]=a[2*j];j=2*j;sum2++;}
a[j]=a[0];sum2++;sum1++; }
void pilesort(){//堆排序
int i;
for(i=2;i<=n;i++) create(i);
for(i=n;i>1;i--) treesort(i);
}
void msort(int l,int r){//归并排序
int i,m,mid;
mid=(l+r+1)/2;
if(mid-1>l)msort(l,mid-1);
if(mid<r)msort(mid,r);
while(l<mid){
m=a[mid].data;
a[0]=a[mid];
while(a[l].data<a[mid].data){l++;sum1++;}
for(i=mid;i>l;i--)a[i]=a[i-1];//移动(跟插入排序一样)
a[l]=a[0];
l++;mid++;if(mid>r)break;
sum1++;sum2++;
}
}
main(){
int c,num,i;
while(1){
sum1=0;sum2=0;
readln();
printf("======================================main======================================");
printf("Press 0 to down sort and else to up sort:\n");
scanf("%d",&c);while(getchar()!=10);
printf("Choose the number to the sorts\n");
printf("0.nosort\n");
printf("1.bubblesort\n");printf("2.quicksort\n");
printf("3.insertsort\n");printf("4.shellsort\n");
printf("5.selectsort\n");printf("6.pilesort\n");
printf("7.mergesort\n");printf("else to exit\n");
scanf("%d",&num);while(getchar()!=10);
switch(num){
case 0:break;
case 1:bubblesort();break;
case 2:qsort(1,n);break;
case 3:insertsort();break;
case 4:shells();break;
case 5:selectsort();break;
case 6:pilesort();break;
case 7:msort(1,n);break;
default:exit(1); }
printf("======================================data======================================");
if(c)
for(i=1;i<=n;i++)printf("%d\t",a[i].data);
else for(i=n;i;i--)
printf("%d\t",a[i].data);
putchar(10);
printf("Here is the times of the compare:\n%d\n",sum1);
printf("Here is the times of the movement:\n%d\n",sum2);
while(getchar()!=10);
system("CLS");
}
}
运行如下：

六、实验总结
这次试验是我对排序运算有了深刻的理解， 在程序编译和链接时还报了一些错，最后我对排序运算有了更深刻的理解，对我们课堂上的知识进行回顾。 在程序编译和链接时还报了一些错，最后通过一步一步的测试，也很快解决了问题。通过这次程序我感觉我对C++调试有个很深的理解，对程序的调试有了很多心得，也对我的程序调试和编写有了进一步的提高。
同时对C++编程进一步熟悉，对数据结构有了一个整体的认识，对各种排序中函数成员实现的原理、代码进一步了解。对各种排序的优缺点有了进一步的认识和了解。 在这个程序中，我觉得下一步程序可以进一步对时间复杂度进行优化，通过将程序的冗长的代码删除，优化算法等，让程序得到结果所需要的时间更短、更快，删除一些代码，让程序的空间复杂度和时间复杂度都减小。

教师签名：

年 月 日