데이터 구조 - 이분 검색 (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; }

좋은 웹페이지 즐겨찾기