算法设计与分析排序
- 格式：doc
- 大小：769.50 KB
- 文档页数：5
《算法设计与分析》实验报告
实验序号：2 实验项目名称：排序
一、实验目的及要求
1. 了解排序的定义
2．掌握合并排序、堆排序算法的实现和时间复杂度的分析
3．理解基数排序算法的思想
二、实验设备（环境）及要求
Turbo C 、VC或相近的环境
三、实验内容与步骤
1. 对给定的n个元素的数组，编写一个程序，判断该数组是否是最大堆或最小堆，所编写的算法时间复杂性是多少？
提高题（选做）：
2. 学生排队问题1：
学生分散地站在操场上。假设操场的坐标由(x,y)表示，每个学生的x坐标都不相同，学生可以沿着网格上下移动，但每个格子上只能有一个学生。要求学生最后要水平的排成一排，请问学生的最少移动步数。
3. 学生排队问题2
学生分散地站在操场上。假设操场的坐标由(x,y)表示，学生可以沿着网格上下左右移动，但每个格子上只能有一个学生。要求学生最后要水平的排成一排，请问学生的最少移动步数。
四、实验结果与数据处理
实验一：
实验结果
结论 时间复杂性：O(2)
实验二：
实验结果
实验三：
详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果。
五、分析与讨论
对上机实践结果进行分析，上机的心得体会。
六、教师评语
签名：
日期： 成绩
附源程序清单：
实验1：
#include
#define MAX 100
int test(int array[],int n)
{
int i,m,right1=0,right2=0;
for(i=1;i { if (i%2==0) { m=(i-2)/2; if (array[m]>array[i]) right1++; else right2++; } else { m=(i-1)/2; if (array[m]>array[i]) right1++; else right2++; } } if(right1==(n-1)) return 0; if(right2==(n-1)) return 1; } void main() { int i,n,a[MAX],right; printf("How many number do you want to Input:\n"); scanf("%d",&n); printf("Input %n number you want to sort\n"); for(i=0;i scanf("%d",&a[i]); printf("The answer.\n"); right=test(a,n); if (right==0) printf("it is max heap\n"); else if(right==1) printf("it is min heap\n"); else printf("neither max heap or min heap\n"); } 实验2： #include #include #define MAX 100 struct student { int x; int y; }; struct student stu[MAX]; void main() { int n,i,j,len1,len,sum=10000; printf("How many number do you want to Input:\n"); scanf("%d",&n); for(i=0;i { printf("the number %d student:\n",i+1); scanf("%d,%d",&stu[i].x,&stu[i].y); } for(i=0;i { len=0; for(j=0;j { len1=abs(stu[i].y-stu[j].y); len=len+len1; } if(sum>len) sum=len; } printf("min steps:%d\n",sum); }
