首页 > 开发技术 > 六种查找算法效率比较

六种查找算法效率比较

2010年5月4日 Terence 4,147 次阅读 发表评论 阅读评论

  接着上次的排序算法讨论,这次谈的是六种查找算法,分别是:顺序查找、折半查找、二叉树查找、索引查找、开地址哈希查找方法、拉链法哈希查找方法。

  由于查找一个数的过程,无论运用哪种算法对于电脑来说速度都是非常快的,都在1ms之内,无法用计时函数测试出来。所以为了能够直观准确地表示出各个算法间的差异,此程序用了循环查找的方法,具体的思想是:先随机生成3000个数作为查找的数据源,再随机生成3000(也可以少一点)个数作为被查找的数,让当前的查找算法运行一趟,这样就相当于运行了3000次。

  这样还不具有一定的客观性,用flag标记出刚刚运行完查找后的结果,从数据源中找到目标的数标记为1,没找到的标记为0,并以此存为两个数组,最后我们就可以使用这两个数组再次分别进行循环查找,同时开始计时。如此一来就可以计算出各个算法在查找成功的情况下需要多少时间,反之在没查找到的情况下需多长时间了。代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
 
#define ListSize 3000
#define TableSize ListSize*5/4
#define  NULLKEY  0
 
typedef int KeyType;
 
typedef struct
{
	KeyType key;
}RecordType;
 
typedef struct node
{
	KeyType key;
	struct node *lchild,*rchild;
}BSTNode,*BSTree;
 
typedef struct
{
    KeyType r[ListSize+1];
	int Length;
}RecordList;
 
typedef struct  //索引表结点
{
	int key;     //最大关键字域
	int link;    //指向本块第一个结点的位置
}Index;
 
typedef struct   //顺序表结点
{  
	int key;     //关键字域
}Dexlist;
 
typedef struct Node{	
	int data;
	struct Node *next;
}Node;
 
typedef RecordType HashTable[TableSize];
Dexlist dexlist[ListSize+1];
Index index[10];
RecordList list;
HashTable hashtable;
BSTree *bst;
Node **A;
 
int SeqSearch(RecordList l,KeyType k);
void InSort(RecordList *l,int length);
int BinSrch(RecordList l,KeyType k);
void InsertBST(BSTree *bst, KeyType x);
void CreateBST(BSTree *bst,RecordList list);
int SearchBST(BSTree bst,KeyType key);
int CreatIndex(Dexlist dl[],Index index[],RecordList list);
int IndexSearch(Dexlist r[],Index index[],int key);
int Hash(KeyType k);
void CreatHashTable(RecordList l,int SIZE);
int  HashSearch(HashTable ht, KeyType K,int SIZE);
void InitHash(Node **Q);
void InsertHash(Node **Q,int value);
int SearchHash(Node **Q,int value);
 
int CaseChoice(int choice,int x)
{
	int i,k=0,flag=0;
		bst=(BSTree *)malloc(sizeof(BSTree));
	if(choice==1)
	{
		k=SeqSearch(list,x);
		return k;
	}
	else if(choice==2)
	{
		InSort(&list,ListSize); 
		k=BinSrch(list,x);
		return k;
	}
	else if(choice==3)
	{
		CreateBST(bst,list);
		k=SearchBST(*bst,x);
		return k;
	}
	else if(choice==4)
	{
		flag=CreatIndex(dexlist,index,list);
		if(!flag) 
		{
			printf("\n\n对不起!索引表创建失败\n");
			exit(0);
		}
		k=IndexSearch(dexlist,index,x);
		return k;
	}
	else if(choice==5)
	{
		CreatHashTable(list,TableSize);
		k=HashSearch(hashtable,x,TableSize);
		return k;
	}
	else if(choice==6)
	{
		A=(Node **)malloc(sizeof(Node*)*10); //申请一个指针型数组A[n]
		InitHash(A);//初始化数组A
		for(i=1;i<=ListSize;i++)
			InsertHash(A,list.r[i]);//print_hash(A,n);
		k=SearchHash(A,x);
		return k;
	}
	else if(choice==7)
		exit(0);
	else
	{
		printf("\n    输入错误!\n");
		exit(0);
	}
 }
 
void main()
{
	int i,j,x,choice,k=0;
	list.Length=ListSize;
	srand((unsigned)time(NULL));
	double runtime;
	int T=0,F=0;
	int success[ListSize],fail[ListSize];
	long dwStart,dwEnd;
	do{
		printf("\n\n=========六种查找算法效率比较=========");//
		printf("\n\n	1. 顺序查找");
		printf("\n\n        2. 折半查找");
		printf("\n\n        3. 二叉树查找");
		printf("\n\n        4. 索引查找");
		printf("\n\n        5. 开地址法哈希查找(α=0.8)");
		printf("\n\n        6. 拉链法哈希查找");
		printf("\n\n        7. 退出\n");
		printf("\n======================================");
		printf("\n    请输入您的选择 (1,2,3,4,5,6,7):");
		scanf("%d",&choice);
		for(i=0;i<ListSize;i++)
		{
			j=1+(unsigned)(10000.0*rand()/(RAND_MAX+1.0));
			list.r[i]=j;
		}
		bst=(BSTree *)malloc(sizeof(BSTree));
		srand((unsigned)time(NULL));
		for(i=0;i<ListSize;i++)
		{
			j=1+(unsigned)(10000.0*rand()/(RAND_MAX+1.0));
			x=j;
			k=CaseChoice(choice,x);
			if(k==0)
			{
				fail[F]=x;
				F++;
			}
			else
			{
				success[T]=x;
				T++;
			}
		}
 
		dwStart=GetTickCount();
		for(i=0;i<F;i++)
			k=CaseChoice(choice,fail[i]);
		dwEnd=GetTickCount();
		runtime=(double)(dwEnd-dwStart)/F;
		printf("\n     查找了%d个数的数组,该种查找算法的平均查找失败时间是:%lf ms\n",ListSize,runtime);
 
		dwStart=GetTickCount();
		for(i=0;i<T;i++)
			k=CaseChoice(choice,success[i]);
		dwEnd=GetTickCount();
		runtime=(double)(dwEnd-dwStart)/T;
		printf("\n     查找了%d个数的数组,该种查找算法的平均查找成功时间是:%lf ms\n\n",ListSize,runtime);
	}while(choice!=7);
}
 
 
int SeqSearch(RecordList l,KeyType k)
/*在顺序表l中顺序查找其关键字等于k的元素,若找到,则函数值为该元素在表中的位置,否则为0*/
{
	int i;
	l.r[0]=k;
	i=l.Length;
	while(l.r[i]!=k)
		i--;
	return(i);
}   //顺序查找
 
void InSort(RecordList *l,int length)
/* 对记录数组r做直接插入排序,length为数组中待排序记录的数目*///直接插入排序
{
	int i,j;
	for(i=2;i<=length;i++)
	{
		l->r[0]=l->r[i];//将待插入记录存放到监视哨r[0]中
		j=i-1;
		while(l->r[0]<l->r[j])/* 寻找插入位置 */
		{
			l->r[j+1]= l->r[j];
			j=j-1;
		}
		l->r[j+1]=l->r[0]; /*将待插入记录插入到已排序的序列中*/
	}
}   //插入排序
 
int BinSrch(RecordList l,KeyType k)
/*在有序表l中折半查找其关键字等于k的元素,若找到,则函数值为该元素在表中的位置*/
{
	int low,high,mid;
	low=1;
	high=l.Length;/*置区间初值*/
	while(low<=high)
	{
		mid=(low+high)/2;
		if(k==l.r[mid])
			return(mid);/*找到待查元素*/
		else
			if(k<l.r[mid])
				high=mid-1;/*未找到,则继续在前半区间进行查找*/
			else
				low=mid+1;/*继续在后半区间进行查找*/
	}
	return (0);
}   //折半查找
 
void InsertBST(BSTree *bst,KeyType x)
/*若在二叉排序树中不存在关键字等于key的元素,插入该元素*/
{
	BSTree s;
	if(*bst==NULL)/*递归结束条件*/
	{
		s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/
		s->key=x;
		s->lchild=NULL; 
		s->rchild=NULL;
		*bst=s;
	}
	else 
		if(x<(*bst)->key)
			InsertBST(&((*bst)->lchild),x);/*将s插入左子树*/
		else
			if(x>(*bst)->key)
				InsertBST(&((*bst)->rchild), x); /*将s插入右子树*/
}
void CreateBST(BSTree *bst,RecordList list)
{
	int i;
	*bst = NULL;
	for(i=1;i<=ListSize;i++)
	{
		InsertBST(bst,list.r[i]);
	}
}
int SearchBST(BSTree bst,KeyType key)/*返回1成功,返回0失败*/
{
	BSTree q;
	q=bst;
	while(q)
	{
		if(q->key==key)
			return 1;
		if(q->key>key)
			q=q->lchild;
		else
			q=q->rchild;
	}
	return 0;
}   //二叉查找
 
int CreatIndex(Dexlist dexlist[],Index index[],RecordList list)
{
	int m,n,i;
	int number[10];
	for(i=1;i<=10;i++)
		index[i-1].key=1000*i;
	for(i=1;i<=10;i++)
		number[i-1]=0;
	index[0].link=1;
	for(m=1;m<=ListSize;m++)
	{
		i=0;
		while((list.r[m]>index[i].key)&&(i<10))
			i++;
		number[i]++;
	}
	for(n=1;n<10;n++)
		index[n].link=index[n-1].link+number[n-1];
 
    for(m=1;m<=ListSize;m++)
	{
		i=0;
		while((list.r[m]>index[i].key)&&(i<10))
			i++;
		n=index[i].link;
		dexlist[n].key=list.r[m];
		index[i].link++;
	}
	m--;
	if(m==ListSize)
		return 1;
	else
		return 0;
}
int IndexSearch(Dexlist r[],Index index[],int key)//key 为给定值,索引表为index[1]..index[b]    
{
	int i,j;
	i=0;
	while((key>index[i].key)&&(i<10))
		i++;
	if(i>=10)
	{
		return 0;
	}
	if(i>0)
		j=index[i-1].link;
	else
		j=index[0].link;
	while((j<ListSize)&&(key!=r[j].key)&&(r[j].key<=index[i].key))
			j++;
	if(key==r[j].key)
		return 1;
	else
		return 0;
}   //索引查找
 
int Hash(KeyType k)
{
	int h;
	h=k%(TableSize);
	return h;
}
void CreatHashTable(RecordList l,int SIZE)
{
	int i,j,hj,t;
	int p;
	for(i=0;i<SIZE;i++)
	{
		hashtable[i].key=NULLKEY;
	}
	for(i=1;i<=ListSize;i++)
	{
		fflush(stdin);
		p=l.r[i];
		j=Hash(p);
		if(hashtable[j].key==NULLKEY)
			hashtable[j].key=p;
		else
		{
			for(t=1;t<SIZE;t++)
			{
				hj=(j+t)%(SIZE);
				if(hashtable[hj].key==NULLKEY)
				{
					hashtable[hj].key=p;
					t=SIZE;
				}
			}
 
		}
	}
}
int HashSearch(HashTable ht, KeyType K,int SIZE)
{
	int h0;
	int i;
	int hi;
	h0=Hash(K);
	if(ht[h0].key==NULLKEY)
		return 0;
	else
		if(ht[h0].key==K)
			return 1;
		else/* 用线性探测再散列解决冲突 */
		{
			for(i=0;i<SIZE-1;i++)
			{
				hi=(h0+i)%SIZE;
				if(ht[hi].key==NULLKEY)
					return 0;
				else
					if(ht[hi].key==K)
						return 1;
			}
			return 0;
		}
}   //开地址法哈希查找
 
void InitHash(Node **A)
{
	int i;
	for(i=0;i<15;i++)
	{
		A[i]=(Node *)malloc(sizeof(Node));
		A[i]->data=0;
		A[i]->next=NULL;
	}
}
void InsertHash(Node **Q,int value)
{
	int key;
	Node *p,*q;
	key=value%15;
	if(Q[key]->next!=NULL)
	{
		p=Q[key]->next;
		while(p->next!=NULL)
			p=p->next;
		q=(Node *)malloc(sizeof(Node));
		q->data=value;
		q->next=NULL;
		p->next=q;
	}
	else
	{
		q=(Node *)malloc(sizeof(Node));
		q->data=value;
		q->next=NULL;
		Q[key]->next=q;
	}
}
int SearchHash(Node **Q,int value)
{
	int key;
	Node *p;
	key=value%15;
	if(Q[key]->next==NULL)
	return 0;
	else
	{
		p=Q[key]->next;
		while(p!=NULL)
		{
			if(p->data==value)
			return 1;
			p=p->next;
		}
		return 0;
	}
}     //拉链法哈希查找

  可能大家已经发现了,为了实现上述思路,并把代码冗余量减少,我把各个函数的引用又单独放到了一个CaseChoice函数里,主函数就负责循环。虽然简洁了不少,但如此一来有个问题:就是计时的时候把查找之前的一些动作都计算进去了,比如折半查找中包含了插入排序、二叉树查找包含了树的建立、哈希查找包含了建立哈希表的过程等等,应该有比较好的解决方法,但实在不想深究,于是乎放弃了 :mrgreen: 但不管怎么说,把运行后的数据结果处理成图表后明显感觉到了各个算法间效率的差异。

  顺便提一句,数据结构课程设计(基于C语言)终于随着本次作业的完成而结束了,痛苦啊,如果再给我一个题目的话我要疯了。。。





 » 转载请注明来源:Terence的窝 » 《六种查找算法效率比较》
分类: 开发技术 标签: ,
  1. 枪骑兵叔叔
    2015年4月1日00:05 | #1
    Google Chrome 41.0.2272.101 Google Chrome 41.0.2272.101 Windows 7 x64 Edition Windows 7 x64 Edition

    main函数的do while循环中用了malloc,没有free。
    CaseChoice函数中的两处malloc,没有free。会报段错误的少年

    [回复]

  2. nbjsw
    2010年5月7日12:38 | #2
    Firefox 3.6.3 Firefox 3.6.3 Windows Vista Windows Vista

    还有fflush(stdin);这东西linux下应该不认的吧,最好少用 :roll:

    [回复]

    Terence

    2010年5月7日12:46
    Internet Explorer 8.0 Internet Explorer 8.0 Windows XP Windows XP

    @nbjsw, 这问题我还真没注意过,你怎么知道的?还有我觉得这应该和编译器有关的吧,gcc编译出来后不行吗?你试过没?

    [回复]

  3. nbjsw
    2010年5月7日06:05 | #3
    Firefox 3.6.3 Firefox 3.6.3 Windows Vista Windows Vista

    说两点
    1.使用 拉链法哈希查找 ,程序出错(多款编译器验证)

    2. 非法输入后,不会循环

    [回复]

    Terence

    2010年5月7日12:29
    Internet Explorer 8.0 Internet Explorer 8.0 Windows XP Windows XP

    @nbjsw, 1.忘了说一点,此程序有个问题,就是单趟跑一遍的情况下,不断让它做循环若干次后的确会出现报错现象,解决办法就是关闭程序后重新选择= =!我也不知道是什么原因,能帮忙修改不?
    2.关于这一点问题,我是因为考虑到CaseChoice函数的原因,做成循环的话会在非法输入后也会统计其运行时间,很不好看,干脆就做成不循环了。

    [回复]

    枪骑兵叔叔

    2015年4月1日00:06
    Google Chrome 41.0.2272.101 Google Chrome 41.0.2272.101 Windows 7 x64 Edition Windows 7 x64 Edition

    @Terence,
    因为你大量的malloc,没有free。

    [回复]

  4. apple
    2010年5月5日12:41 | #4
    Internet Explorer 8.0 Internet Explorer 8.0 Windows XP Windows XP

    留下点痕迹 ;-)

    [回复]

    Terence

    2010年5月7日12:33
    Internet Explorer 8.0 Internet Explorer 8.0 Windows XP Windows XP

    @apple, :mrgreen:

    [回复]