精华内容
下载资源
问答
  • //请写出对有序表进行折半查找的非递归算法,并将对应的程序调试运行通过 #include #include #define N 100 typedef int Status; typedef int ElemType;typedef struct {//创建有序表 ElemType *list; int length;...
    //请写出对有序表进行折半查找的非递归算法,并将对应的程序调试运行通过
    #include<stdio.h>
    #include<stdlib.h>
    #define N 100
    typedef int Status;
    typedef int ElemType;
    
    typedef struct {//创建有序表
        ElemType *list;
        int length;
    }SqList;
    
    Status Creat_SearchTable(SqList &st){//创建查找表
        ElemType a[N];
        printf("请输入您要输入的数据总数:(不大于100)");
        scanf("%d",&st.length);
        st.list=(ElemType*)malloc(st.length*sizeof(ElemType));
        if(!st.list)
            exit(-1);
        for(int i=0;i<st.length;i++){
            printf("请输入第%d个数据",i+1);
            scanf("%d",&a[i]);
        }
        int j,k,t,p;
        for(j=0;j<st.length-1;j++){//选择法对数据进行排序
            p=j;
            for(k=j;k<st.length;k++){
                if(a[k]<a[p])
                    p=k;
                t=a[p];a[p]=a[j];a[j]=t;
            }
        }
        for(int i=0;i<st.length;i++){//把已经排好序的数据放入表中
            st.list[i]=a[i];
        }
    }
    Status Binary_Search(SqList st,ElemType key){//非递归的折半查找
        int low,mid,high;
        low=0;high=st.length-1;
        while(low<=high){
            mid=(low+high)/2;
            if(key==st.list[mid])
                return mid;
            else if(key<st.list[mid])
                high=mid-1;
            else
                low=mid+1;
        }
        return 0;
    }
    Status Binary_Search_recur(SqList st,int low,int high,ElemType key){
        //递归的折半查找
        int mid=(low+high)/2;
        if(low>high)
            return 0;
        if(key==st.list[mid])
            return mid;
        else if(key<st.list[mid])
            Binary_Search_recur(st,low,mid-1,key);
        else
            Binary_Search_recur(st,mid+1,high,key);
    }
    int main(){
        ElemType key;
        int flag,p=0;
        SqList st;
        if(!Creat_SearchTable(st))
            return 0;
        printf("请输入您要查找的数据:");
        scanf("%d",&key);
        while(!p){
            printf("请选择您想使用的折半查找方式,“1”代表非递归的折半查找方式,“2”表示递归的折半查找方式。“0”表示退出");
                scanf("%d",&flag);
            if(flag==0||flag==1||flag==2)p=1;
        }
        if(flag=1){
            if(!Binary_Search(st,key))
                printf("您要查找的数据不存在");
            else
                printf("值为%d的数据在表中",key);
            }
        if(flag=2){
            if(!Binary_Search_recur(st,0,st.length,key))
                printf("您要查找的数据不存在");
            else
                printf("值为%d的数据在表中",key);
        }
        system("pause");
        return 0;
    }
    
    展开全文
  • //a[]是数组,n是数组长度,key是查找的关键字 int BinSearch(int a[],int n,int key) { int l=0,r=n-1; int mid; while(l<=r){ mid=(1+r)/2; if(a[mid]==key) return mid; else if(a[mid]<key) l=...
    • 非递归
    //a[]是数组,n是数组长度,key是查找的关键字
    int BinSearch(int a[],int n,int key) {
    	int l=0,r=n-1;
    	int mid;
    	while(l<=r){
    		mid=(1+r)/2;
    		if(a[mid]==key) return mid;
    		else if(a[mid]<key) l=mid+1;
    			 else r=mid-1;
    	}
    	return -1;
    }
    
    • 递归
    //函数头和非递归的不一样,是为了递归的时候传参
    int mid;
    int BinSearchRec(int a[],int key,int l,int r){
    	//递归出口1
    	if (l>r) return -1;
    	//递归出口2
    	mid=(l+r)/2;
    	if (a[mid]==key) return mid;
    	//递归体
    	if (a[mid]<key) BinSearchRec(a[],key,mid+1,r);
    	else BinSearchRec(a[],key,l,mid-1);
    }
    

    非递归和递归是可以通过while循环来转换的。

    展开全文
  • NULL 博文链接:https://128kj.iteye.com/blog/1744446
  • 折半查找递归与非递归算法

    千次阅读 2015-06-16 09:27:53
    #include "stdio.h" int Bisearch(int a[],int low,int high,int k); int main() { int pos,s;... int a[10]={23,25,27,29,31,33,35,37,39,41};... printf("请输入你要查找的数\n");... printf("待查找的
    #include "stdio.h"
    int Bisearch(int a[],int low,int high,int k);
    int main()
    {
    	int pos,s;
    	int a[10]={23,25,27,29,31,33,35,37,39,41};
    	printf("请输入你要查找的数\n");
    	scanf("%d",&s);
    	printf("待查找的数   %d\n",s);
    	pos=Bisearch(a,0,9,s);//参数传递弄错了,k和s。
    	if(pos==-1)
    		printf("没有找到该数\n");
    	else
    		printf("%d在数组中位置是%d\n",s,pos);
    	return 0;
    }
    
    /*int Bisearch(int a[],int low,int high,int k)
    {
    	int mid;
    	while(low<=high)
    	{
    	 mid=(low+high)/2;
    	 if(k==a[mid])return mid;
    	 else if(k<a[mid])high=mid-1;
    	 else low=mid+1;
    	}
    	return -1;
    	
    }*/
    
    
    int Bisearch(int a[],int low,int high,int k)
    {
    	int mid;
    	if(low>high)
    		return -1;
    	else
    	{
    		mid=(low+high)/2;
    		if(a[mid]==k)
    			return mid;
    		if(a[mid]<k)	
    			return Bisearch(a,mid+1,high,k);		
    		else
    			return Bisearch(a,low,mid-1,k);	
    	}
    	
    }
    


    函数调用参数之间关系还是把握不是太好。

    同时要分辨好数组下标值和数组值的区别。

    展开全文
  • 折半查找的递归算法非递归

    千次阅读 2016-11-24 19:19:56
    设计一个算法,实现折半查找,很简单问题。在这里列举下递归和非递归 递归实现 #include #include #include #include #include #include #include using namespace std; int n,a[105]; int Search_Bin...

    设计一个算法,实现折半查找,很简单的问题。在这里列举下递归和非递归

    递归实现

    #include <iostream>
    #include <cstdio>
    #include <ctime>
    #include <cstdlib>
    #include <stack>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    int n,a[105];
    
    int Search_Bin(int stat,int end,int tmp)
    {
    	int i,j;
    	
    	if(stat>end)
    		return -1;
    	if(stat==end)
    	{
    		return stat;
    	}
    	
    	if(tmp==a[(stat+end)/2])
    	{
    		return (stat+end)/2;
    	}
    	if(tmp>a[(stat+end)/2])
    	{
    		return Search_Bin((stat+end)/2+1,end,tmp);
    	}
    	else if (tmp<a[(stat+end)/2])
    	{
    		return Search_Bin(stat,(stat+end)/2-1,tmp);
    	}
    }
    
    int main()
    {
    	int i,j,tmp;
    	
    	printf("请输入你要随机产生的数的个数\n");	
    	scanf("%d",&n);
    	srand(time(0));
    	for(i=0;i<n;i++)
    	{
    		a[i]=rand()%1000;
    	}
    	sort(a,a+n);
    	printf("随机产生的数排序后的answer是\n");
    	for(i=0;i<n;i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    	printf("请输入你要查找的数\n");
    	scanf("%d",&tmp);
    	printf("该数所在的位置是%d个\n",Search_Bin(0,n-1,tmp)+1);
    	
    	return 0;
    }

    非递归实现

    #include <iostream>
    #include <cstdio>
    #include <ctime>
    #include <cstdlib>
    #include <stack>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    int n,a[105];
    
    int Search_Bin(int stat,int end,int tmp)
    {
    	int i,j;
    	
    	printf("该数所在的位置是");
    	while(stat<=end)
    	{
    		if(stat==end)
    		{
    			printf("%d\n",stat+1);
    			break;
    		}
    		
    		if(tmp==a[(stat+end)/2])
    		{
    			printf("%d\n",stat+1);
    			break;
    		}
    		if(tmp>a[(stat+end)/2])
    			stat=(stat+end)/2+1;
    		else if(tmp<a[(stat+end)/2])
    			end=(stat+end)/2-1;
    	}
    	
    }
    
    int main()
    {
    	int i,j,tmp;
    	
    	printf("请输入你要随机产生的数的个数\n");	
    	scanf("%d",&n);
    	srand(time(0));
    	for(i=0;i<n;i++)
    	{
    		a[i]=rand()%1000;
    	}
    	sort(a,a+n);
    	printf("随机产生的数排序后的answer是\n");
    	for(i=0;i<n;i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    	printf("请输入你要查找的数\n");
    	scanf("%d",&tmp);
    	Search_Bin(0,n-1,tmp)+1;
    	//printf("该数所在的位置是%d个\n",Search_Bin(0,n-1,tmp)+1);
    	
    	return 0;
    }


    展开全文
  • 折半查找--当查找表是有序表时,可采用折半查找; 基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功; 若给定值K小于中间记录关键字,则在表左半区继续查找; ...
  • [code="... 折半查找--当查找表是有序表时,可采用折半查找; 基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功; 若给定值K小于中间记录关键...
  • *功能:实现了折半查找(二分查找)的递归和非递归算法. *说明: * 1、要求所查找的数组已有序,并且其中元素已实现Comparable<T>接口,如Integer、String等. *2、非递归查找使用search();,递归查找使用...
  • 折半查找的基本思想 折半查找也称为二分查找(Binary search),要求线性表中的节点必须己按关键字值的递增或递减顺序排列。...折半查找的非递归算法 int BinSearch(int str,int n,int k) { int lo
  • * 折半查找(二分查找)的递归和非递归算法. 说明: * 1、要求所查找的数组已有序,并且其中元素已实现Comparable接口,如Integer、String等. * 2、非递归查找使用search();,递归查找使用searchRecursively(); **...
  • #include <stdio.h>.../**非递归算法**/ int binary_search(int a[],int n,int m) //a为数组,n为数组大小,m为要查数 { int low=0,high=n-1; //查找区间[low,high] while(low<=high) { ...
  • 原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。...*功能:实现了折半查找(二分查找)的递归和非递归算法. *说明: * 1、要求所查找的数组已
  • * 折半搜索算法 * @param array $arr 已经排序好的数组 * @param int $value 要查找的值 * @param int $left 数组开始下标 * @param int $right 数组结束下标 * @return 返回要查找的值在数组里的下标,不存在...
  • 1步骤描述 使用前提:有序数组中查找关键词所在位置。 1.首先确定整个查找区间中间位置 mid = start+(end-start)/2。...2 非递归二分查找算法 int bin_search1(int key,int arr[],int length){ int start
  • 原创作品,允许转载,转载时请务必以超链接形式标明文章原始出处、作者信息和本声明。否则将追究法律责任。... ...Java二分查找实现,欢迎大家提出...*功能:实现了折半查找(二分查找)递归和非递归算法. *说明: * ...
  • *功能:实现了折半查找(二分查找)的递归和非递归算法. *说明: * 1、要求所查找的数组已有序,并且其中元素已实现Comparable&lt;T&gt;接口,如Integer、String等. * 2、非递归查找使用search();,递归查找使用...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 266
精华内容 106
关键字:

折半查找的非递归算法