顺序查找和折半查找

小鱼儿 2022-06-03 00:53 182阅读 0赞

/****************************************************
      @title: 数据结构实验
      @name: <实验9-1> 顺序查找和折半查找
      @object:
          [实验目的]
              实现顺序查找和折半查找，
              对两种查找方法作比较
          [实验提示]
              1. 编写顺序查找和折半查找算法
              2. 修改算法把查找过程中所作比较及其结果
                 打印出来，观察并对比查找过程
              3. 分析并计算两种算法的平均查找长度
      @include:
      @usage:
          请查看"TO-DO列表",根据要求完成代码
      @copyright: BTC 2004, Zhuang Bo
      @author: Zhuang Bo
      @date: 2004
      @description:
    *****************************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ElemType int
    
    //顺序查找
    int SqSearch(ElemType a[],int n,ElemType x);
    int SqSearch2(ElemType a[],int n,ElemType x); //打印查找过程 
    //折半查找
    int BinSearch(ElemType a[],int n,ElemType x);
    int BinSearch2(ElemType a[],int n,ElemType x); //打印查找过程
    //打印数组数据
    void PrintArray(ElemType a[],int n);
    
    int main()
    {
    	int i,x;
    	//测试数据
    	const int N = 9;
    	ElemType a1[N+1]={0,34,23,12,56,90,78,89,45,67};
    	ElemType a2[N+1]={0,12,23,34,45,56,67,78,89,90};
    
    	//顺序查找
    	printf("\n顺序查找\n");
    	printf("a1[]="); 
    	PrintArray(a1,N);
    	
    	printf("\n输入要查找的数据: ");
    	scanf("%d",&x);
    	
    	if((i=SqSearch(a1,N,x))>0) //找到 
    		printf("\n找到 x==a1[%d]\n",i);
    	else //未找到 
    		printf("\n找不到 %d \n",x);
    	
    	printf("\n查找过程:");
    	SqSearch2(a1,N,x);
    	printf("\n完成\n");
    
    	//折半查找
    	printf("\n折半查找\n");
    	printf("a2[]=");
    	PrintArray(a2,N);
    	
    	//进行折半查找，并输出结果
    	printf("\n输入要查找的数据: ");
    	scanf("%d",&x);
    	
    	if((i=BinSearch(a2,N,x))>0) //找到 
    		printf("\n找到 x==a2[%d]\n",i);
    	else //未找到
    		printf("\n找不到 %d \n",x);
    	
    	printf("\n查找过程:");
    	BinSearch2(a2,N,x);
    	printf("\n完成\n");
    
    	system("pause");
    	return 0;
    }
    
    //在数组a[1..n]中顺序查找x
    //  找到时返回元素下标，否则返回0 
    int SqSearch(ElemType a[],int n,ElemType x)
    {
        //-------------------------------------
        // TODO (#1#): 顺序查找算法
        int i;
    	for(i=1;i<=n;i++){
    	   if(a[i]==x)
    		   return i;
    	}
        //-------------------------------------
    	return 0; //找不到 
    }
    
    int SqSearch2(ElemType a[],int n,ElemType x)
    {
        //-------------------------------------
        // TODO (#1#): 顺序查找算法，打印每次比较结果 
         int i,j=1;
    	for(i=1;i<=n;i++){
    		if(a[i]==x){
    			 printf("第%d次比较",j++);
    			 j++;
    		    return i;
    		}else{
    		   printf("第%d次比较",j++);
    		}		 
    		  
    	}
        //-------------------------------------
    	return 0;
    }
    
    //在数组a[1..n]中折半查找x
    //  找到时返回元素下标，否则返回0 
    //前提：a[1..n]是非递减有序的 
    int BinSearch(ElemType a[],int n,ElemType x)
    {
        //-------------------------------------
        // TODO (#1#): 折半查找算法
        int low=1,high=n,mid;
    	while(low<=high){
    	   mid=(low+high)/2;
    	   if(a[mid]==x){
    	     return mid;
    	   }else if(a[mid]>x){
    	     high= mid-1;
    	   }else
    		   low=mid+1;
    	}
        //-------------------------------------
    	return 0; //找不到 
    }
    
    int BinSearch2(ElemType a[],int n,ElemType x)
    {
        //-------------------------------------
        // TODO (#1#): 折半查找算法，打印每次比较结果
          int low=1,high=n,mid;
    	while(low<=high){
    	   mid=(low+high)/2;
    	   if(a[mid]==x){
    	     return mid;
    		  printf("%d,%d,%d,%d\n",low,high,mid,a[mid]);
    	   }else if(a[mid]>x){
    	     high= mid-1;
    		  printf("%d,%d,%d,%d\n",low,high,mid,a[mid]);
    	   }else
    		   low=mid+1;
    	   printf("%d,%d,%d,%d\n",low,high,mid,a[mid]);
    	}
        //-------------------------------------
    	return 0;
    }
    
    //打印数组数据a[1..n]
    void PrintArray(int a[],int n)
    {
    	int i;
    	printf("{ ");
    	for(i=1; i<=n; i++)
    		printf("%d ",a[i]);
    	printf("}\n");
    }

![Center][]

[Center]: /images/20220603/0ac78c14852042eca89f9624ee552e81.png