演算法思想
1、折半查找：在給定的一張有序表中，先確定待查記錄的所在范圍，然后逐步縮小范圍直到找到或找不到該記錄為止，
流程圖
代碼如下
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define FALSE 0
#define OVERFLOW -2
#define ERROR 0
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
}SSTable;
int Search_Bin(SSTable ST,int key,int *count)
{
int low,high,mid;
low=1;
high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
*count+=1; //計數器
if(ST.elem[mid]==key)
return mid;
else if(key<ST.elem[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
}
void main()
{
int count=0,key,x,i;
SSTable ST;
srand((unsigned)time(NULL) + (unsigned)rand()); //以time()為種子生成亂數
ST.elem=(int*)malloc(81*sizeof(int));
ST.elem[0]=rand()%10+1;
ST.length=80;
for(i=1;i<81;i++)
ST.elem[i]=ST.elem[i-1]+rand()%10+1;
printf("有序數如下\n");
for(i=1;i<81;i++)
{
if(i%9)
printf("%4d",ST.elem[i]);
else
{
printf("%4d",ST.elem[i]);
printf("\n");
}
}
printf("\n請選擇一個數用來查找!\n");
scanf("%d",&key);
x=Search_Bin(ST,key,&count);
if(x)
printf("該元素的下標是:%d\n",x);
else
printf("該元素不存在！\n");
printf("比較次數是:%d",count);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/238109.html
標籤：其他
上一篇：C語言資料結構