C语言数据结构课程设计(可运行)

#include
#define MAXSIZE 30
typedef struct
{
int key;//关键字项
char data;//其他数据项
}RecordType;//记录类型
//插入排序
void D_Insert(RecordType R[],int n)
{ //对n个记录序列R[1]~R[n]进行直接插入排序
int i,j;
for(i=2;i<=n;i++) //进行n-1趟排序
if(R[i].key
{//R[i].key小于R[i-].key时，需将R[i]插入到有序序列R[1]~R[i-1]中
R[0]=R[i];//设置查找监视哨R[0]并保存待插入记录R[i]值
j=i-1; //j定位于有序序列的最后一个记录R[i-1]处
while(R[j].key>R[0].key)//在有序序列中寻找R[i]的插入位置
{/将有序序列中关键字值大于R[i].key(即此刻的R[0].key)的所有Rj
由后向前顺序后移一个记录位置/
R[j+1]=R[j];
j–;
}
R[j+1]=R[0]; //将Ri插入到有序序列中应插位置上
}
}
void Interposition()
{
int i=1,j,x;
RecordType R[MAXSIZE];//定义记录类型数组R
printf(“输入所需排序的值直至-1结束：\n”);
scanf("%d",&x);
while(x!=-1)
{
R[i].key=x;
scanf("%d",&x);
i++;
}
printf(“输出表中记录的字：\n”);
for(j=1;j
printf("%4d",R[j].key);
printf("\n排序\n");
D_Insert(R,i-1); //进行直接插入排序
printf(“输出直接插入排序后的结果：\n”);
for(j=1;j
printf("%4d",R[j].key);
printf("\n");
}
//折半插入排序
void B_InsertSort(RecordType R[],int n)
{ //对n个记录序列R[1]~R[n]进行折半插入排序
int i,j,low,high,mid;
for(i=2;i<=n;i++) //进行n-1趟排序
{
R[0]=R[i]; //设置查找监视哨R[0]并保存待插入记录的R[i]值
low=1,high=i-1;//设置初始化查找区间
while(low<=high)//寻找插入位置
{
mid=(low+high)/2;
if(R[0].key>R[mid].key)
low=mid+1;//插入位置在右半区
else
high=mid-1;//插入位置在左半区
}
for(j=i-1;j>=high;j–)
/high+1为插入位置，将R[i-1]，R[i-2]，…，R[high+1]顺序后移一个位置R[j+1]=R[j]/
R[high+1]=R[0];//将Ri放入应插入位置high+1
}
}
void Binary_insert()
{
int i=1,j,x;
RecordType R[MAXSIZE];//定义记录类型数组R
printf(“输入所需排序的值直至-1结束：\n”);
scanf("%d",&x);
while(x!=-1)
{
R[i].key=x;
scanf("%d",&x);
i++;
}
printf(“输出表中记录的关键字：\n”);
for(j=1;j
printf("%4d",R[j].key);
printf("\n排序\n");
B_InsertSort(R,i-1); //进行折半插入排序
printf("\n输出折半插入排序后的结果：\n");
for(j=1;j
printf("%4d",R[j].key);
printf("\n");
}
//冒泡排序
void BubbleSort(RecordType R[],int n)
{ //对R[1]~R[n]这n个记录进行冒泡排序
int i,j,swap;
for(i=1;i
{
swap=0; //设置未发生交换标志
for(j=1;j<=n-i;j++) //R[1]~R[n-i]记录进行俩俩比较
if(R[j].key>R[j+1].key)
//如果R[j].key大于R[j+1].key,则交换R[j]和R[j+1]
{
R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];
swap=1;//有交换发生
}
if(swap==0)
break; //本躺比较中未出现交换，则结束排序(序已排好)
}
}
void Bubbing()
{
int i=1,j,x;
RecordType R[MAXSIZE];//定义记录类型数组R
printf(“输入你要进行排序的数字直到-1结束：\n”);
scanf("%d",&x);
while(x!=-1)
{
R[i].key=x;
scanf("%d",&x);
i++;
}
printf(“输出表中各记录的关键字：\n”);
for(j=1;j
printf("%4d",R[j].key);
BubbleSort(R,i-1); //进行冒泡排序
printf("\n输出冒泡排序后的结果\n");
for(j=1;j
printf("%4d",R[j].key);
printf("\n");
}
//快速排序
int Partition(RecordType R[], int i, int j)//划分算法
{ //对R[i]~R[j], 以R1为基准记录进行划分并返回划分后R[i]的正确位置
R[0]=R[i]; //暂存基准记录R[i]于R[0]
while(i
{
while (i=R[0].key)
//(从右向左扫描查找第一个关键字小于R[0].key时将R[0].key的记录R[j]
j–;
if(i
{
R[i]=R[j];
i++;
}
while (i
//从左到右扫描查找第一个关键字大于R[0].key的记录R[i]
i++;
if(i
{
R[j]=R[i];
j–;
}
}
R[i]=R[0];//将基准记录R[O]送入最终(指排好序时)应放置的位置
return i; //返回基准记录R[O]最终放置的位置
}
void QuickSort(RecordType R[], int s, int t)
{ //进行快速排序
int i;
if(s
{
i=Partition(R,s,t);//i为基准记录的位置并由此将表分为R[s]~R[i - 1]和R[i + 1]~R[t]两部分
QuickSort(R,s,i-1);//对表R[s]~R[i-1]进行快速排序
QuickSort(R,i+1,t);//对表R[i+1]~R[t]进行快速排序
}
}
void Speediness()
{
int i=1,j,x;
RecordType R[MAXSIZE];//定义记录类型数组R
printf(“输入所需要排序的数据直到输入-1结束:\n”);
scanf("%d",&x);
while(x!=-1)
{
R[i].key=x;
scanf("%d",&x);
i++;
}
printf(“输出表中各记录的关键字:\n”);
for(j=1;j
printf("%4d",R[j].key);
QuickSort(R,1,i-1); //进行快速排序
printf("\n输入快速排序后的结果:\n");
for (j=1;j
printf("%4d", R[j].key);
printf("\n");
}
//选择排序
void SelectSort(RecordType R[], int n)
{
int i,j,k;
for (i=1;i
{
k=i; //假设关键字最小的记录为第i个记录
for(j=i+1;j<=n;j++)//从第i个记录开始的n-i+1个无序记录中选出关键字最小的记录
if(R[j].key
k=j; //保存最小关键字记录的存放位置
if (i!=k) //将找到的最小关键字记录与第i个记录交换
{
R[0]=R[k];
R[k]=R[i];
R[i]=R[0];
}
}
}
void Select()
{
int i=1,j,x;
RecordType R[MAXSIZE]; //定义记录类型数组R
printf(“输入需要排序的数据直到输入-1结束:\n”);
scanf("%d", &x);
while(x!=-1)
{
R[i].key = x;
scanf("%d", &x);
i++;
}
printf(“输出表中各记录的关键字:\n”);
for (j = 1; j < i; j++)
printf("%4d", R[j].key);
printf("\n排序:\n");
SelectSort(R,i-1); //进行选择排序
printf("\n输出选择排序后的结果 : \n");
for (j = 1; j < i; j++)
printf("%4d", R[j].key);
printf("\n");
}
//堆排序
void HeapAdjust(RecordType R[], int s, int t)//基于大根堆的堆排序
{ /对R[s]~R[t]除R[s]外均满足堆的定义, 即只对Rs进行调整,
使R[s]为根的完全二叉树成为一个堆/
int i,j;
R[0]=R[s]; //R[s]暂存于R[0]
i=s;
for(j=2i;j<=t;j=2j)//沿关键字较大的孩子向下调整, 先假定为左孩子
{
if(j
j = j + 1;//右孩子结点的关键字大则沿右孩子向下调整
if(R[0].key>R[j].key)//即已满足堆的定义, 故不再向下调整
break;
R[i]=R[j];//将关键字大的孩子结点R[j]调整至双亲结点R[i]
i=j; //定位于孩子结点继续向下调整
}
R[i]=R[0];//找到满足堆定义的R[0](即R[s]放置位置i, 将R[s]调整于此
}
void HeapSort(RecordType R[], int n)
{ //对R[1]~R[n]这n个记录进行堆排序
int i;
for(i=n/2;i>0;i–)
//将完全二叉树非终端结点按R[n/2,R[n/2-1,…, R[1]的顺序建立初始堆
HeapAdjust(R,i,n);
for(i=n;i>1;i–) //对初始堆进行n-1趟堆排序
{
R[0] = R[1]; //堆顶的R[1]与堆底的R[i]交换
R[1] = R[i];
R[i] = R[0];
HeapAdjust(R, 1, i - 1);//将未排序的前i-1个的点重新调整为堆
}
}
void Pile()
{
int i = 1,j,x;
RecordType R[MAXSIZE]; //定义记录类型数组R
printf(“输入需要排序的数据直到结束输入-1:\n”);
scanf("%d",&x);
while(x!=-1)
{
R[i].key=x;
scanf("%d",&x);
i++;
}
printf(“输出表中各记录的关键字:\n”);
for(j=1;j
printf("%4d",R[j].key);
printf("\nSort:\n");
HeapSort(R,i-1); //进行堆排序
printf("\n输出堆排序后的结果:\n");
for(j=1;j
printf("%4d",R[j].key);
printf("\n");
}
int main()
{
int select; //选择
//首界面
{
printf("\n数据结构排序实践\n");
printf(" 1、插入排序\n");
printf(" 2、折半插入排序\n");
printf(" 3、冒泡排序\n");
printf(" 4、快速排序\n");
printf(" 5、选择排序\n");
printf(" 6、堆排序\n");
printf("***请选择(1-6)😊;
scanf("%d",&select);
getchar();
switch (select)
{
case 1:Interposition(); //插入排序
break;
case 2:Binary_insert(); //折半插入排序
break;
case 3:Bubbing(); //冒泡排序
break;
case 4:Speediness(); //快速排序
break;
case 5:Select(); //选择排序
break;
case 6:Pile(); //堆排序
break;
}
}
}