데이터 구조 - 이분 검색 (Binary Search)
2854 단어 자신 에 게 쓰다
#include
#include
#include
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define TRUE 1
#define FALSE 0
#define true 1
#define false 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define OPSETSIZE 7
#define MAXQSIZE 100
#define EQ(a, b) ((a) == (b))
#define LT(a, b) ((a) < (b))
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
} SSTable;
int CreatSST(SSTable *sst, int n, ElemType key);
int Search_Seq(SSTable *ST, ElemType key);
int Search_Bin(SSTable ST, ElemType key);
int sort(SSTable *s, int n);
int main()
{
printf("Please input the number of the static search table:
");
int n, i;
scanf("%d",&n);
printf("Please input a table:
");
SSTable sst;
ElemType key;
CreatSST(&sst, n, key);
for(i= 0; i< n; i++)
scanf("%d",&sst.elem[i+1]);
printf("The static search table is:
");
for(i= 0; i< n ;i++)
printf("%d%c", sst.elem[i+1], i== n- 1? '
': ' ');
printf("Please input the element to search:
");
scanf("%d", &key);
printf("The position is %d
", Search_Seq(&sst, key));
printf("Next,using binary search->
");
printf("After sort,the static search table is:
");
sort(&sst, n);
for(i= 0; i< n ;i++)
printf("%d%c", sst.elem[i+1], i== n- 1? '
': ' ');
printf("Please input the element to search:
");
scanf("%d", &key);
printf("The position is: %d
", Search_Bin(sst, key));
return 0;
}
int CreatSST(SSTable *sst, int n, ElemType key)
{
int i= 0;
sst->elem = (ElemType*)malloc((n + 1) * sizeof(ElemType));
if(!sst->elem)
exit(OVERFLOW);
sst->elem[0] = key;
sst->length = n;
if(!sst->length)
exit(OVERFLOW);
return OK;
}
int Search_Seq(SSTable *ST, ElemType key)
{
int i;
ST->elem[0] = key;
for (i=ST->length; !EQ(ST->elem[i], key); --i);
return i;
}
int Search_Bin(SSTable ST,ElemType key)
{
int low=1;
int high=ST.length;
while (low<=high)
{
int mid=(low+high)/2;
if (EQ(key,ST.elem[mid])) return mid;
else if (LT(key, ST.elem[mid])) high=mid-1;
else low=mid+1;
}
return 0;
}
int sort(SSTable *s, int n)
{
int i, j;
ElemType temp;
for(i = 1; i<= n; i++)
for(j = 1; j<= n- i; j++)
if(s->elem[j] > s->elem[j+1])
temp = s->elem[j], s->elem[j] = s->elem[j+1], s->elem[j+1] = temp;
}