数据结构程序设计报告
班级：计科1001
姓名：
学号： 2010070101**
完成日期： 2012年5月9日
1．设计题目与要求：
折半查找问题：
1：生成10000个递增的int类型的数据元素，存放到数组array中。
2：设计折半查找问题的递归函数。
3：设计折半查找问题的循环结构函数。
4：设计测试主程序，测试例子至少包括一个查找成功的和一个查找不成功的例子。
5：分析递归函数和循环结构函数的时间复杂度。
2：设计思想：
对于递归函数实现过程是设计finder函数，在满足条件下使其对自己进行调用，直至所调用为已知为止。
并将所找到的数组下标返回，最后以该地址数据为依据分别输出是否找到，如果找到就把数据打印，同时打印其下标。
对于循环结构函数设计finder2函数，在函数之中再设计while判断语句，首先如果满足所已经列出的三个特例，再判断如果array[mid]<x，就将min=mid+1；如果所设mid值判断出array[mid]>x,就将max=mid-1；均不满足即最终返回-1（以后类似上述递归调用函数）。
3:代码以及四种情况的截图：
<一>递归函数实现代码以及两种情况下的截图：
#include<stdio.h>
void main()
{ int j,x,y;
int array[10000];
int min,max;
int finder(int array[],int x,int min,int max);
min=0,max=9999;
for(j=0;j<10000;j++)
{
array[j]=j+5;
}
printf("输入你要查找的整数形数据x的值(该数值须介于5到10005之间)：\n");
scanf("%d",&x);
printf("接收到的数据是%d\n",x);
y=finder(array,x,min,max);
if(y==-1)
printf("\n灰常抱歉，您的输入有误，请核实后重新输入。
\n");
else
printf("\n数据%d找到\n\n下标是%d\n\n",array[y],y);
}
int finder(int array[],int x,int min,int max)
{
int mid=(min+max)/2;
if(x==array[min])
return min;
if(x==array[max])
return max;
if(x==array[mid])
return mid;
else if(x<array[mid]&&x>array[min]) {
return finder(array,x,min,mid-1);
}
else if(x>array[mid]&&x<array[max]) {
return finder(array,x,mid+1,max); }
else
return -1;
}
A: 查找成功的例子截图：
B: 查找不成功的例子截图：
<二>循环结构函数实现代码以及两种情况下的截图：
#include<stdio.h>
void main()
{ int j,x,y;
int array[10000];
int finder2(int array[],int x,int min,int max);
int min=0,max=9999;
for(j=0;j<10000;j++)
{ array[j]=j+5;
}
printf("输入你要查找的整数形数据x的值(该数值须介于5到10005之间)：\n");
scanf("%d",&x);
printf("接收到的数据是%d\n",x);
y=finder2(array,x,min,max);
if(y==-1)
printf("\n灰常抱歉，您的输入有误，请核实后重新输入。
\n\n");
else
printf("\n数据找到%d\n\n下标是%d\n\n",array[y],y);
}
int finder2(int array[],int x,int min,int max)
{
while(min<max)
{ int mid=(min+max)/2;
if(array[mid]==x)
return mid;
if(x==array[min])
return min;
if(x==array[max])
return max;
if(array[mid]<x)
min=mid+1;
if(array[mid]>x)
max=mid-1;
}
return -1;
}
A: 查找成功的例子截图：
B: 查找不成功的例子截图：
4：时间复杂度分析：
(A)递归函数调用时时间复杂度：
递归函数的时间复杂度是O(2n/2)，因为每次出现的都是与2有关的递归调用自己，出现的次数为平均n/2次，所以时间复杂度是O(2n/2)。
(B)循环结构函数调用时时间复杂度:
循环结构函数调用时时间复杂度为O(n)，这是因为从该数组循环了n/2次，所以其时间复杂度是O（n）。