シーヶンステーブルスタティックルックアップ
18399 ワード
シーケンシャル・テーブルの静的検索の実装(SeqSearch、BinarySearch、GoldenSectionSearch、)
how many elements in your list:20
Please enter the 1th number:1
Please enter the 2th number:11
Please enter the 3th number:2
Please enter the 4th number:22
Please enter the 5th number:3
Please enter the 6th number:33
Please enter the 7th number:4
Please enter the 8th number:44
Please enter the 9th number:5
Please enter the 10th number:55
Please enter the 11th number:6
Please enter the 12th number:66
Please enter the 13th number:7
Please enter the 14th number:77
Please enter the 15th number:8
Please enter the 16th number:88
Please enter the 17th number:9
Please enter the 18th number:99
Please enter the 19th number:10
Please enter the 20th number:111
The list you create is:
1 11 2 22 3 33 4 44 5 55 6 66 7 77 8 88 9 99 10 111
The list after sorting is:
1 2 3 4 5 6 7 8 9 10 11 22 33 44 55 66 77 88 99 111
Please enter the number you want to search:3
SeqSearch=======18
the number's position is:3
BinarySearch=======4
the number's position is:3
GoldenSectionSearch=======5
the number's position is:3
. . .#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define GOLD 0.618
#define MAX_SIZE 100
typedef int ElementType;
typedef int KeyType;
typedef struct
{
ElementType elem[MAX_SIZE];
int length;
}SSTable;
int Search(SSTable *ST,KeyType key);
void ListInit(SSTable *ST);
void ListCreate(SSTable *ST, int count);
void ListSort(SSTable *ST);
int BinarySearch(SSTable *ST,KeyType key);
void ListDisplay(SSTable *ST);
int GoldenSectionSearch(SSTable *ST,KeyType key);
void main()
{
int i,count, num;
SSTable ST;
ListInit(&ST);
printf_s("how many elements in your list:");
scanf_s("%d",&count);
ListCreate(&ST,count);
printf_s("The list you create is:
");
ListDisplay(&ST);
ListSort(&ST);
printf_s("The list after sorting is:
");
ListDisplay(&ST);
printf_s("Please enter the number you want to search:");
scanf_s("%d",&num);
printf_s("SeqSearch");
i = Search(&ST,num);
printf_s("the number's position is:%d
",i);
printf_s("BinarySearch");
i = BinarySearch(&ST,num);
printf_s("the number's position is:%d
",i);
printf_s("GoldenSectionSearch");
i = GoldenSectionSearch(&ST,num);
printf_s("the number's position is:%d
",i);
system("pause");
}
void ListInit(SSTable *ST)
{
ST->length=0;
}
void ListCreate(SSTable *ST, int count)
{
int i,num;
ST->length=count;
for(i=1;i<=count;++i)
{
printf_s("Please enter the %dth number:",i);
scanf_s("%d",&num);
ST->elem[i]=num;
}
}
void ListSort(SSTable *ST)
{
int i,j,temp;
for(j=1;j<=ST->length-1;++j)
{
for(i=1;i<=ST->length-j;++i)
{
if(ST->elem[i]>ST->elem[i+1])
{
temp=ST->elem[i];
ST->elem[i]=ST->elem[i+1];
ST->elem[i+1]=temp;
}
}
}
}
int Search(SSTable *ST,KeyType key)
{
int i, counter;
counter = 0;
ST->elem[0]=key;
for(i = ST->length; i > 0; --i)
{
++counter;
if(key==ST->elem[i])
{
printf_s("=======%d
",counter);
return i;
}
}
printf_s("=======%d
",counter);
return i;
}
int BinarySearch(SSTable *ST,KeyType key)
{
int low,high,mid,counter;
low=1;
counter=1;
high=ST->length;
while(low<=high)
{
mid=(low+high)/2;
if(key==ST->elem[mid])
{
printf_s("=======%d
",counter);
return mid;
}else if(key<ST->elem[mid])
{
++counter;
high=mid-1;
}else
{
++counter;
low=mid+1;
}
}
printf_s("=======%d
",counter);
return 0;
}
int GoldenSectionSearch(SSTable *ST,KeyType key)
{
int low,high,mid,counter;
low=1;
counter=1;
high=ST->length;
while(low<=high)
{
mid=(high -low)*GOLD +low;
//mid = high * GOLD + low*(1-GOLD);
if(key==ST->elem[mid])
{
printf_s("=======%d
",counter);
return mid;
}else if(key<ST->elem[mid])
{
++counter;
high=mid-1;
}else
{
++counter;
low=mid+1;
}
}
printf_s("=======%d
",counter);
return 0;
}
void ListDisplay(SSTable *ST)
{
int i;
for (i = 1; i <= ST->length; ++i)
{
printf_s("%d ", ST->elem[i]);
}
printf_s("
");
}