活動(dòng)地址：CSDN21天學(xué)習(xí)挑戰(zhàn)賽

??作者簡介：大家好我是小唐同學(xué)(?>?<?），為夢想而奮斗的小唐，讓我們一起加油?。?！

個(gè)人主頁：小唐同學(xué)(?>?<?）的博客主頁

系列專欄：數(shù)據(jù)結(jié)構(gòu)

博友們?nèi)绻彩切率秩腴T數(shù)據(jù)結(jié)構(gòu)我希望大家可以多加練習(xí) 數(shù)據(jù)結(jié)構(gòu)題庫在?？途W(wǎng)就有已經(jīng)給大家附上鏈接，可以直接點(diǎn)擊跳轉(zhuǎn)：刷題點(diǎn)這里

?？途W(wǎng)支持ACM模式哦，刷算法題也很推薦哦?。?！

下面上文章------》

?

目錄

刷題圖示：

索引查找介紹：

?索引查找的核心思想：

索引查找代碼實(shí)現(xiàn)：

復(fù)雜度：

?????????時(shí)間復(fù)雜度：

刷題圖示：

?

索引查找介紹：

索引查找也稱為分塊查找，也是順序查找的一種改進(jìn)方法，在索引查找法中，除表本身之外還需要建立一個(gè)索引表。由分塊查找可知，它要分開進(jìn)行，塊內(nèi)元素之間無大小關(guān)系，塊與塊之間有大小關(guān)系（比如說：第二塊中的元素肯定要比第一塊中大，第三塊中元素肯定要比前兩塊中的元素大）所以索引表是有序的，可以進(jìn)行二分查找進(jìn)行查找由于要有索引所以要用到結(jié)構(gòu)體。

?索引查找的核心思想：

準(zhǔn)備工作：

本文索引查找是在一定條件下使用（給索引表開值為3，所以查找表中元素個(gè)數(shù)要是3的倍數(shù)），則每個(gè)塊中的元素個(gè)數(shù)為n/3,則在每個(gè)塊中找出塊中最大值，賦值給索引表，在對索引表的關(guān)鍵字進(jìn)行比較排序

索引查找是先找到確定的塊（這個(gè)過程可以進(jìn)行二分也可以進(jìn)行順序查找（下邊代碼實(shí)現(xiàn)的是順序查找））

確定塊之后在塊中進(jìn)行順序查找

索引查找代碼實(shí)現(xiàn)：

# include <stdio.h>
# include <stdlib.h>
struct Lnode
{
	int start;
	int key;
}index_table[3];
int cmp(const void *a,const void *b)
{
	return (*(struct Lnode*)a).key> (*(struct Lnode*)b).key?1:-1;
}
int fenkuai(int key,int a[],int n)//傳參  給出關(guān)鍵字和數(shù)組  n是來確定塊的大小 
{
	int i,j;
	i=0;
	while(i<3&&key>index_table[i].key)
	{
		i++;
	 } 
	 if (i>3)
	 {
	 	return 0; 
	 } 
	  j=index_table[i].start;
	   for(j=index_table[i].start;j<index_table[i].start+n/3;j++)
	   {
	   if(a[j]==key)
	   {
	   	return j;
	   }
	   }
	   return 0;
}
int main()
{
	 int i,j=0,k;
   int n;
   printf("請輸入3的倍數(shù)的個(gè)數(shù)") 
   scanf("%d",&n);
    int a[n];
   for(i=0;i<n;i++)
{
scanf("%d",&a[i]);   	
} 
    int key;
    printf("請輸入要查找的值"); 
    scanf("%d",&key);
    for(i=0;i<3;i++)
    {
    	index_table[i].start=j;
    	j+=n/3;
   	 	for(int k=index_table[i].start;k<=j;k++)
   	 	{
   	 	if(index_table[i].key<a[k])
			{
			index_table[i].key=a[k];	
			}	
		}
	
	}
	qsort(index_table,3,sizeof(index_table[0]),cmp);
//	printf("請輸入你想查找的數(shù)");
	k= fenkuai(key,a,n);
	if(k>0)
	{
		printf("查找成功下標(biāo)為： %d ",k);
	}
	else
	printf("失敗"); 
	return 0; 
}

復(fù)雜度：

?????????時(shí)間復(fù)雜度：

? ? ? ? ? ? ? ? ? ?查找索引表時(shí)采用順序查找：

ASL=L1+LS=（b+1）/2+（s+1）/2=(s^2+2*s+n)/2*s

? ? ? ? ? ? ? ? 對索引表進(jìn)行折半查找時(shí)：

ASL=L1+LS=?log2(b+1)?+(s+1)/2文章來源地址http://www.zghlxwxcb.cn/news/detail-786230.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之索引查找（分塊查找）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！