#include<stdio.h>

#include<stdlib.h>

typedef int KeyType;//查找表中關(guān)鍵字的類型

typedef struct{

? ? ?KeyType key;

}ElemType;

//靜態(tài)表查找

typedef struct{

? ElemType *elem;

? int length;

}SSTable;

//創(chuàng)建靜態(tài)鏈表

int Creat(SSTable *ST)

{

int i,n;

printf("\n 請(qǐng)輸入表長：");

scanf("%d",&n);

ST->elem=(ElemType*)malloc(sizeof(ElemType)*(n+1) ? );

if(!ST->elem )return 0;

printf("請(qǐng)輸入%d個(gè)數(shù)據(jù)",n);

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

scanf("%d",&(ST->elem[i].key ?));

ST->length=n;

return 1;

}

//實(shí)現(xiàn)順序查找，折半查找

int Search(SSTable ST,KeyType key,int *time){

int i;

ST.elem[0].key =key;//哨兵

*time=1;

for(i=ST.length;ST.elem[i].key != key ;i--)//利用循環(huán)完成查找

++(*time);

return ?i ? ;

}

int Search_Bin(SSTable ST,KeyType key,int *time)//折半查找

{

int low,high,mid;

low=1; ?high=ST.length ;

*time=0;

while(low<=high)

{

mid=(low+high)/2 ? ? ?;

? ?++(*time);

? ?if(key==ST.elem [mid].key )return mid;

? ?else if(key>ST.elem[mid].key) low=mid+1 ? ? ? ? ? ? ?;//到右子表中進(jìn)行查找

else ? high=mid-1 ? ? ? ? ? ;//到左子表中進(jìn)行查找

}

return 0;

}

void main()

{

int i, n,time, loc;

? KeyType key;

SSTable ST;

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

{

printf("\n\n\t******輸入下列序號(hào)，選用查詢算法*******");

printf("\n\n\t ? 1.順序查找 ? 2.折半查找");

printf("\n\n ?本次查尋為第%d次查詢，請(qǐng)按上面的提示輸入對(duì)應(yīng)序號(hào)",i);

scanf("%d",&n);

switch(n)

{

case 1:

Creat(&ST);

printf("\n 請(qǐng)輸入一個(gè)要查找元素的關(guān)鍵字");

scanf("%d",&key);

if(loc=Search(ST,key,&time))

printf("\n 順序查找成功，共比較了%d次，要找的數(shù)據(jù)%d在第%d個(gè)數(shù)的位置上",time,key,loc);

else printf("\n 順序查找失敗");

? ? ?break;

case 2:

Creat(&ST);

printf("\n 請(qǐng)輸入一個(gè)要查找元素的關(guān)鍵字");

scanf("%d",&key);

? if(loc=Search_Bin(ST,key,&time))

? ?printf("\n 折半查找成功，共比較了%d次，要找的數(shù)據(jù)%d在第%d個(gè)數(shù)的位置上",time,key,loc);

else printf("\n 折半查找失敗");

}}

printf("\n\n 查找結(jié)束 ?\n\n");

system("pause");

}