请给出具体代码比较各种查找算法的效率,包括顺序查找,二分查找,分块查找,hash查找
时间: 2024-06-04 07:13:34 浏览: 18
对于您的第一个问题,我可以提供以下代码来比较不同查找算法的效率:
//顺序查找
int Sequential_Search(int *a,int n,int key)
{
for(int i=0;i<n;i++)
{
if(a[i]==key)
{
return i;
}
}
return -1;
}
//二分查找
int Binary_Search(int *a,int n,int key)
{
int left=0,right=n-1,mid;
while(left<=right)
{
mid=(left+right)/2;
if(a[mid]==key)
{
return mid;
}
else if(a[mid]>key)
{
right=mid-1;
}
else
{
left=mid+1;
}
}
return -1;
}
//分块查找
int Block_Search(int *a,int *index,int n,int key)
{
int i;
for(i=0;i<n-1;i++)
{
if(a[index[i]]<=key&&a[index[i+1]]>key)
{
break;
}
}
if(i==n-1)
{
return -1;
}
int j;
for(j=index[i];j<index[i+1];j++)
{
if(a[j]==key)
{
return j;
}
}
return -1;
}
//hash查找
#define NULLKEY -32768
typedef struct
{
int *elem;
int count;
}HashTable;
int InitHashTable(HashTable *hashTable,int maxsize)
{
hashTable->elem=(int*)malloc(maxsize*sizeof(int));
hashTable->count=maxsize;
for(int i=0;i<maxsize;i++)
{
hashTable->elem[i]=NULLKEY;
}
return 0;
}
int Hash(int key,int p)
{
return key%p;
}
int InsertHash(HashTable *hashTable,int key,int p)
{
int addr=Hash(key,p);
while(hashTable->elem[addr]!=NULLKEY)
{
addr=(addr+1)%p;
}
hashTable->elem[addr]=key;
return 0;
}
int SearchHash(HashTable hashTable,int key,int p)
{
int addr=Hash(key,p);
while(hashTable.elem[addr]!=key)
{
addr=(addr+1)%p;
if(hashTable.elem[addr]==NULLKEY||addr==Hash(key,p))
{
return -1;
}
}
return addr;
}
int main()
{
int a[]={1,3,5,7,9,11,13,15,17,19};
int n=10,key=7;
printf("顺序查找结果:%d\n",Sequential_Search(a,n,key));
printf("二分查找结果:%d\n",Binary_Search(a,n,key));
int m=3;
int index[]={0,4,7,10};
printf("分块查找结果:%d\n",Block_Search(a,index,m,key));
HashTable hashTable;
int p=13;
InitHashTable(&hashTable,p);
for(int i=0;i<n;i++)
{
InsertHash(&hashTable,a[i],p);
}
printf("hash查找结果:%d\n",SearchHash(hashTable,key,p));
return 0;
}
请注意,这是一个基础示例,实际情况下,不同的查找算法的效率会受到许多因素的影响,例如数据大小、数据分布、实现细节等。具体而言,当数据量较小或有序时,顺序查找可能会更快,而当数据量较大且随机分布时,二分查找、分块查找或hash查找可能更有效。因此,在实际应用中,我们需要根据具体情况来选择最合适的查找算法。