ITKeyword,专注技术干货聚合推荐

注册 | 登录

数据结构之查找算法

feng1790291543 分享于 2014-06-19

推荐:数据结构基本查找算法

1.概述   查找表的概念:由同一类型的数据元素(或者记录)构成的集合。由于集合中的数据元素之间存在完全松散耦合的关系,因此,查找表是一种非常灵便的数据

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1053

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

转载请注明出处:http://blog.csdn.net/feng1790291543


顺序查找过程:从表中的最后一个记录开始,逐个进行记录的关键字与给定值进行比较,若某个记录的关键字与给定值相等,则查找成功,找到所查的记录;反之,若直到第一个记录,其关键字和给定值比较都不相等,则表明表中没有所查的记录,查找失败。


二分查找又称折半查找,它是一种效率较高的查找方法。

算法思想: 首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

C++中Find001项目工程

推荐:数据结构与算法:链表

数组和链表的区别是什么 找出单链表中的倒数第k个元素 如何检测一个较大的单链表是否有环 判断两个单链表无环是否交叉 删除单链表中的重复结点 如何在不知道头指

Find001.h

// Find001.h: interface for the CFind001 class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_FIND001_H__88949A11_A06B_439B_87BF_D58A5AC8FCCA__INCLUDED_)
#define AFX_FIND001_H__88949A11_A06B_439B_87BF_D58A5AC8FCCA__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <iostream>
using namespace std;

class CFind001  
{
public:
	CFind001();
	virtual ~CFind001();

	void BullonSort(int a[],int length);              //事先冒泡排序,在进行二分查找
	int orderFind(int a[],int num,int length);        //顺序查找
	int halfFind(int a[],int num,int length);         //二份查找

};

#endif // !defined(AFX_FIND001_H__88949A11_A06B_439B_87BF_D58A5AC8FCCA__INCLUDED_)

Find.cpp

// Find001.cpp: implementation of the CFind001 class.
//
//////////////////////////////////////////////////////////////////////

#include "Find001.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CFind001::CFind001()
{

}

CFind001::~CFind001()
{

}

int  CFind001::orderFind(int a[],int num,int length)
{
    int i;
    int count=0;

	for(i=0;i<length;i++)
	{
	   ++count;
	   if(a[i]==num)
	   {
		   cout<<"it is finded--->\t"<<(i+1)<<"\t"<<a[i]<<endl;
		   break;
	   }
	   if(count==length)
	   {
            cout<<"it is not finded!!!"<<endl;
	   }
	}
    return a[i];
}

void CFind001::BullonSort(int a[],int length)
{
	if(a==NULL)
	{
        return ;
	}
    int maopao;

	for(int i=0;i<length-1;i++)
	{
         for(int j=i+1;j<length;j++)
		 {
		     if(a[i]>a[j])
			 {
                 maopao=a[i];
				 a[i]=a[j];
				 a[j]=maopao;
			 }
		 }
	}
    cout<<"Bullon ends!!!"<<endl;
}

int CFind001::halfFind(int a[],int num,int length)
{
	int i;
	int low=0;
	int high=length-1;
	int mid=(low+high)/2;
    int temp=-1;
    int count=0;
    
	int *p=a;
	while(*p!=NULL)
	{
		count++;
		*p++;
	}
    
    count=count-4;
    //count=sizeof(a)/sizeof(int);
	cout<<count<<endl;

    if(a==NULL||count!=length)                                //防止数组数据和长度不一致问题
	{
        return -2;
	}

    cout<<"halfFind begins!!!"<<endl;
    if(num==a[mid])
	{
        temp=mid;

	}
	else if(num>a[mid])
	{
        /*
		temp=halfFind(a+mid+1,num,length-mid-1);   //方法二:递归调用
		if(temp!=-1)
		{
             temp=temp+mid+1;
		}
	    */
		for(i=mid+1;i<length;i++)
        {
            ++count;
			if(a[i]==num)
			{
				cout<<"(1) it is finded--->\t"<<(i+1)<<"\t"<<a[i]<<endl;
				temp=i;	
			
			}

			if(count==(length-(mid+1)))
			{
				cout<<"it is not finded!!!"<<endl;
				break;
			}
		}
		
	}
	else
	{
		//temp=halfFind(a+low,num,mid);           //方法二:递归调用
		
		for(i=0;i<mid;i++)
        {
            ++count;
			if(a[i]==num)
			{
				cout<<"(2) it is finded--->\t"<<(i+1)<<"\t"<<a[i]<<endl;
				temp=i;	
				
			}
			if(count==mid)
			{
				cout<<"it is not finded!!!"<<endl;
				return count;
			}
		}
	}
	cout<<"halfFind ends!!!"<<endl;
	return temp;              //返回序号下标
	
}

mian.cpp

#include <iostream>
#include "Find001.h"
using namespace std;

int main()
{
    
	CFind001 find001;
	int num=10;
	int arr[]={3,4,8,10,23,7,1};
	find001.orderFind(arr,num,7);
    
    CFind001 find002;
	int num=5;
	int arr2[]={5,1,3,2,8,4,7};
    int a_size=sizeof(arr2)/4;
	cout<<a_size<<endl;

	find002.BullonSort(arr2,a_size);
	for(int i=0;i<7;i++)
	{
		cout<<"\t"<<arr2[i];
	}
	cout<<endl;
    
	int num2=find002.halfFind(arr2,num,a_size);
	cout<<"get number is\t"<<(num2)<<endl;
	return 0;
}


推荐:数据结构-Prim算法

#include<stdio.h> #include<string.h> #define maxn 21 #define inf 1000000 int n,m; int edge[maxn][maxn]; int lowcost[maxn]; int nearvex[maxn];

转载请注明出处:http://blog.csdn.net/feng1790291543 顺序查找过程:从表中的最后一个记录开始,逐个进行记录的关键字与给定值进行比较,若某个记录的关键字与给定值相等,则查找成功,找到所

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。