一、實驗?zāi)康?/p>

掌握折半查找算法的基本思想

掌握折半查找算法的實現(xiàn)方法

掌握折半查找的時間性能

掌握折半查找類的定義和使用

二、實驗要求

熟悉C++語言編程

了解折半查找的原理

了解折半查找類的定義、應(yīng)用

三、實驗內(nèi)容

1、問題描述

在一個有序序列中，折半查找一個關(guān)鍵字

返回查找是否成功，如果成功，輸出關(guān)鍵字所在的位置和查找次數(shù)。

2、折半查找算法

1.n個從小到大存放在有序順序表ST中，k為給定值

2.設(shè)low、high指向待查元素所在區(qū)間的下界、上界，即low=1，high=n

3.設(shè)mid指向待查區(qū)間的中點，即mid=（low+high）/2

4.讓k與mid指向的記錄比較

若k=ST[mid].key,查找成功，結(jié)束

若k<ST[mid].key,則high=mid-1? ? [上半?yún)^(qū)間]

若k>ST[mid].key,則low=mid+1? ? [下半?yún)^(qū)間]

5.重復(fù)3,4操作，直至low>high時，查找失敗。

舉例：

3、輸入

第一行：測試次數(shù)

每個樣本分兩行：

第一行：第一個數(shù)字n表示樣本數(shù)目，其后跟n個樣本；

第二行：查找的關(guān)鍵字的值。

4、輸入樣本

2

5 2 3 4 5 7

4?

6 1 2 3 4 6 8

7

5、輸出

查找是否成功（1-表示成功，0表示不成功）

所在位置（0-表示不成功）

查找次數(shù)

6、輸出樣本

1 3 1

0 0 3

四、實驗步驟

1、折半查找變量的定義

2、生成順序有序表函數(shù)

3、折半查找函數(shù)

4、主程序

五、詳細代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-480962.html

#include<stdio.h>

/*折半查找實驗*/



int BinSuccess; ?// 查找是否成功（1-成功，0-不成功）

int BinPos; ?????// ?查找位置（0表示不成功）

int BinCount; ???// ?查找次數(shù)???

int BinList[32]; // ????有序表

int BinListLen; ?// ??????有序表長度



int BinSearchKey(int Key);

void CreateSequence(int *r, int n);



int main()

{

????int r[32], i, j, Key, TestNum, SampleNum;

????printf(" 輸入測試次數(shù)");

????scanf("%d", &TestNum);

????for(i = 0; i < TestNum; i++)

????{

????????printf("輸入樣本數(shù)目");

????????scanf("%d", &SampleNum);

????????printf("輸入樣本數(shù)據(jù): ");

????????for(j = 1; j <= SampleNum; j++)

????????????scanf("%d", &r[j]);

????????CreateSequence(r, SampleNum);

????????printf("輸入1個查找數(shù)據(jù)");

????????scanf("%d", &Key);

????????BinSearchKey(Key);

????????printf("%d %d %d\n", BinSuccess, BinPos, BinCount);

????}

????return 0;

}

void CreateSequence(int *r, int n)

{

????int i, j, temp;

????BinListLen = n;

for(i = 1; i < n; i++)

//利用直接插入排序?qū)㈨樞虮碓嘏懦缮蛐蛄?
????{

????????if(r[i+1] < r[i])

????????{

????????????temp = r[i+1];

????????????for(j = i; j >= 1; j -= 1)

????????????????if(temp<r[j])

????????????????????r[j+1] = r[j];

????????????????else break;

????????????r[j+1] = temp;

????????}

????}

????for(i = 1; i <= n; i++)

????????BinList[i] = r[i];// 數(shù)據(jù)放到有序順序表中???

}

int BinSearchKey(int Key)

{

????int Low, Mid = 0, High;

????Low = 1;//low指向待查元素所在區(qū)間的下界

????High = BinListLen;//high指向待查元素所在區(qū)間的上界

????BinSuccess = 0;

????BinPos = 0;

????BinCount = 0;

????while(Low <= High)

????{

???? BinCount++;// 執(zhí)行循環(huán)查找的記數(shù)???

????????Mid =(High + Low)/2;

????????if(Key == BinList[Mid])

????????{

????????????BinSuccess = 1;// 查找成功

BinPos = Mid;

????????????break;

????????} ?????????????

????????if(Key > BinList[Mid])// 關(guān)鍵字大于折半查找所取的中間數(shù)

????????{

????????????Low = Mid + 1;

????????}

????????if(Key < BinList[Mid])// 關(guān)鍵字小于折半查找所取的中間數(shù)

????????{

????????????High = Mid - 1;

????????}

???????

????} ???

????return BinCount;// 返回查找次數(shù)

}



?

到了這里，關(guān)于折半查找實驗 （數(shù)據(jù)結(jié)構(gòu)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！