折半查找冒泡排序堆排序
- 格式：wps
- 大小：267.00 KB
- 文档页数：5
数据与结构实验报告
折半查找法、冒泡法与堆排序一实验设计：
（1）用折半查找法找到需要查找目标的位置
（2）用冒泡法把输入数据从小到大排列
（3）用堆排序法把输入的数据从小到大排列
二算法设计：
1.冒泡排序与折半查找的共同应用
#include<stdio.h>
#include<string.h>
void maopao(int a[])/*冒泡排序*/
{
int k,i,j,t;
for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
if(a[i]==0)
break;
}
k=i;
for(i=0;i<k;i++)
{
for(j=i;j<k;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
for(i=0;i<k;i++)
{
printf("%d\t",a[i]);
}
}
int chazhao(int a[],int _value,int n)
{ // 二分法(也称折半查找法)
int index=0; // 当前数组的首元素下标
int current=n-1; // 数组当前的大小
int k; // 当前数组中间的数的下标
while (index<=current)
{
// 开始二分法查找
k=(index+current)/2; // 除以2代表得到当前数组中间的数的下标
if(a[k]==_value)
return k+1; // 返回要查找的值_value所在的下标
// 否则比较要查找的值_value是在折半后的前半部分还是后半部分
if(a[k]<_value)// 说明要查找的值在折半后的后半部分
index=k+1; // 令index指向后半部分数组的首元素
else // 说明要查找的值在折半后的前半部分
current=k-1; // 令current等于前半部分数组的长度}
return -1; // 返回-1代表没有查找到该值(_value)
}
void main()
{
int a[10],c;
maopao(a);
scanf("%d",&c);
printf("%d",chazhao(a,c,10));
}
2.堆查找的单独应用
#include <iostream.h>
#include<string.h>
#include<stdio.h>
void BigHeapAdjust(int *p, int r, int len);
void BigHeapSort(int *p, int len);
int main()
{
int array[1000] = {0};
int n;
printf("请输入排序元素的个数：\n");
scanf("%d", &n);
printf("请输入要排序的元素：\n");
for(int i=0; i<n; ++i)
scanf("%d", array+i);
BigHeapSort(array, n);
printf("结果是：\n");
for(int k=0; k<n; ++k)
printf("%d ", array[k]);
getchar();
getchar();
getchar();
return 0;
}
void BigHeapAdjust(int *p, int r, int len) {
int tmp = p[r];
int j;
for(j=2*r+1; j<=len-1; j=2*j+1)
{
if(j<len-1 && p[j+1]>=p[j])
++j;
if(tmp >= p[j])
break;
p[r] = p[j];
r = j;
}
p[r] = tmp;
}
void BigHeapSort(int *p, int len)
{
int i,j;
for(i=len/2-1; i>=0; --i)
BigHeapAdjust(p, i, len);
p[0] ^= p[len-1];
p[len-1] ^= p[0];
p[0] ^= p[len-1];
for(j=len-1; j>1; --j)
{
BigHeapAdjust(p, 0, j);
p[0] ^= p[j-1];
p[j-1] ^= p[0];
p[0] ^= p[j-1];
}
}
三实验结果
冒泡排序与折半查找
输入10个数（78 90 30 29 10 74 2 6 5 7）先冒泡排序从小到大排列输入查找7这个数据
显示在从小到大的数组中排第4位
2.堆排序
先输入要输入的数据个数（8）
让后输入数据（3 5 44 6 8 7 3 2）
让后得出从小到大的结果
四实验分析
对于冒泡排序和折半查找发比较简单，没有什么太大的问题，而堆排序相对较复杂，在网上找了较多的资料后才有点明白，运用了堆排序的基本原理，在首先了解什么事堆的情况下，然后结合所学的知识进行编程，在编程的过程中，首先要了解大顶堆，小顶堆的定义，以及如何利用堆排序的原理进行排序，在设计程序之前，应先画出流程图，在画图的过程中，应该正确了解各个图形的意义，不能错用，对于经常使用的选择，判断等的特殊图形要正确使用，以及箭头所指的方向，都要仔细，在完成了对流程图的设计后，就要根据流程图进行编程，在编程的时候，首先要明白程序的主题函数，先从主函数开始，结合流程图进行编译，正确使用特殊语句，以及关键字，在这过程要用到for循环语句，最重要的就是要写出正确的判断语句，搞清楚程序的结束的点，在完成主函数的编译之后，就要进行子函数的编译，次函数包括两个子函数，一个是大顶堆的筛选，另一个是大顶堆的排序，在大顶堆的筛选的时候，要明白堆排序的实质，就是从最后一个非叶子节点开始，从它的左右子树开始比较，顺着子树较大的方向往父节点平移，最后和序列的最后一个数据进行交换，把它放置在闲置的空间内，在进行大顶堆的排序的时候，对上面的交换完成之后，先找出一个最大的，然后对其余的数据进行重复的比较，方法和大顶堆的筛选一样，直至待排序的数据按顺序输出。
在编程的完成之后，要进行仔细的检验，找出错误，进行多次验证，确保此程序准确无误，并且要使程序简单明了，便于操作者使用方便。
在进行了此次程序设计之后，明白了如何利用堆排序原理进行对数据的排序，对以前所学的知识进行了巩固，增加了实践的经验。
