数据结构与算法设计
实验报告
（2016 — 2017 学年第1 学期）
实验名称：
年级：
专业：
班级：
学号：
姓名：
指导教师：
成都信息工程大学通信工程学院
一、实验目的
验证各种简单的排序算法。
在调试中体会排序过程。
二、实验要求
（1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。
（2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。
三、实验步骤
1、创建工程（附带截图说明）
2、根据算法编写程序（参见第六部分源代码）
3、编译
4、调试
四、实验结果图
图1-直接输入排序
图2-冒泡排序
图3-直接选择排序
五、心得体会
与哈希表的操作实验相比，本次实验遇到的问题较大。
由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。
虽然在理清思路后成功解决了直接输入和直接选择两种算法，但
冒泡排序的算法仍未设计成功。
虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。
而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。
本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。
六、源代码
要求：粘贴个人代码，以便检查。
#include <stdio.h>
#define MAXSIZE 100
typedef int KeyType;
typedef int DataType;
typedef struct{
KeyType key;
DataType data;
}SortItem,SqList[MAXSIZE];
/*******直接插入顺序表*******/
void InsertSort(SqList L,int n)
{
int i,j,x;
SortItem p;
for(i=1;i<n;i++)
{
p=L[i];
for(j=i-1;j>=0&&p.key<L[j].key;j--)
{
L[j+1]=L[j];
}
L[j+1]=p;
printf("\n第%d次排序为：",i);
for(x=0;x<n;x++)
{
printf("%d\t",L[x].key);
}
printf("\n");
}
}
/*******冒泡排序*******/
void BubbleSort(SqList L,int n)
{
int i,j,over,x;
SortItem p;
for(i=0;i<n-1;i++)
{
over=1;
for(j=1;j<n-i;j++)
{
if(L[j].key<L[j-1].key)
{
p=L[j];
L[j]=L[j-1];
L[j-1]=p;
over=0;
}
}
if(over)
{
break;
}
printf("\n第%d次排序为：",i+1);
for(x=0;x<n;x++)
{
printf("%d\t",L[x].key);
}
printf("\n");
}
}
/*******直接选择排序*******/
void SelectSort(SqList L,int n)
{
int i,j,min,x;
SortItem p;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(L[j].key<L[min].key)
{
min=j;
}
}
if(min!=i)
{
p=L[i];
L[i]=L[min];
L[min]=p;
}
printf("\n第%d次排序为：",i+1);
for(x=0;x<n;x++)
{
printf("%d\t",L[x].key);
}
printf("\n");
}
}
void main()
{
SqList L;
int i,n=0;
KeyType items[MAXSIZE]={'\0'};
printf("\n--------排序算法---------\n");
printf("\n请输入要排序的数组，输入-1结束\n"); for(i=0;i<MAXSIZE;i++)
{
scanf("%d",&items[i]);
if(items[i]==-1)
{
break;
}
n++;
}
while(1)
{
for(i=0;i<n;i++)
{
L[i].key=items[i];
}
printf("\n-------主菜单-------\n");
printf("1.直接输入排序\n");
printf("2.冒泡排序\n");
printf("3.直接选择排序\n");
printf("0.退出\n");
printf("-----------------------\n");
scanf("%d",&i);
switch(i)
{
case 1:
InsertSort(L,n);
break;
case 2:
BubbleSort(L,n);
break;
case 3:
SelectSort(L,n);
break;
case 0:
exit(0);
default:
printf("\n错误！请重新输入...\n");
break;
}
}
}。