C++ 二分查找

<code>#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
 

#define TRUE 1
#define FALSE 0
#define OK 1
#define OVERFLOW -2

#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) <  (b)) 

typedef int Status;

typedef int KeyType; //整型 

typedef struct {
\tKeyType key; //關鍵字域 
} ElemType;

typedef struct {
\t//數據元素存儲空間基址，
\t//建表時按實際長度分配，0號單元留空
\tElemType *elem; \t 
\tint length; //表長度 
} SSTable;

Status Create(SSTable &ST, int n) {
\t
\tST.length = n;
\t
\tST.elem = (ElemType *) malloc((n+1)*sizeof(ElemType));
\t
\tif(!ST.elem)
\t\texit(OVERFLOW);
\t
\tprintf("請輸入%d個數：\\n", ST.length); 
\tint i;
\tfor(i=1; i<=ST.length; i++) {
\t\tscanf("%d", &ST.elem[i].key);
\t}
\t
\treturn OK;
}

Status Print(SSTable ST) {
\tint i;
\tfor(i=1; i<st.length>\t\tprintf("%d ", ST.elem[i].key);
\tprintf("%d\\n", ST.elem[i].key);
\t 

\treturn OK;
}

int Search_Seq(SSTable ST, KeyType key); 

//在有序表ST中折半查找其關鍵字等於key的數據元素。
//若找到，則函數值為該元素在表中的位置，否則為0。
int Search_Bin (SSTable ST, KeyType key);

void bubble_sort(SSTable &ST, int n); 

int main(void) {
\t
\tSSTable ST;
\tint n;
\t
\tprintf("輸入要建立順序表的長度：\\n");
\tscanf("%d", &n);
\t
\tCreate(ST, n);

\tPrint(ST);
\t
\tKeyType key;
\tprintf("請輸入要查的數：\\n");
\tscanf("%d", &key); 
\t
\tprintf("您要查的數是%d\\n", key);
\tint position = Search_Seq(ST, key);
\tif(position)
\t\tprintf("%d在順序表中的位置是%d\\n", key, position);
\telse
\t\tprintf("%d不在順序表中\\n", key);
\t
\t//對無序表排序，以便二分查找\t
\tbubble_sort(ST, n);
\t
\tprintf("===================二分查找===================\\n");
\tPrint(ST);
\tint position1 = Search_Bin(ST, key); 

\tif(position1)
\t\tprintf("%d在順序表中的位置是%d\\n", key, position1);
\telse
\t\tprintf("%d不在順序表中\\n", key);
\t
\treturn 0;
} 


int Search_Seq(SSTable ST, KeyType key) {
\tST.elem[0].key = key;
\tint i;
\tfor(i=ST.length; !EQ(ST.elem[i].key, key); --i)
\t\t;
\t
\treturn i;
} //Search_Seq

void bubble_sort(SSTable &ST, int n) {
\tElemType temp;
\tbool change;
\tint i, j;
\tfor(i=n,change=TRUE; i>=2 && change; --i) {
\t\tchange = FALSE;
\t\tfor(j=1; j\t\t\tif(ST.elem[j].key > ST.elem[j+1].key) {
\t\t\t\ttemp = ST.elem[j];
\t\t\t\tST.elem[j] = ST.elem[j+1];
\t\t\t\tST.elem[j+1] = temp;
\t\t\t\t
\t\t\t\tchange =TRUE;
\t\t\t}
\t}
}

int Search_Bin (SSTable ST, KeyType key) {
\t//在有序表ST中折半查找其關鍵字等於key的數據元素。
\t//若找到，則函數值為該元素在表中的位置，否則為0。
\tint low = 1;
\tint high = ST.length;
\tint mid;
\t
\twhile(low <= high) {
\t\tmid = (low + high) / 2;
\t\tprintf("mid=%d\\n", mid); 

\t\t
\t\tif(EQ(key, ST.elem[mid].key))
\t\t\treturn mid;
\t\telse if(LT(key, ST.elem[mid].key))
\t\t\thigh = mid - 1;
\t\telse
\t\t\tlow = mid + 1;
\t}
\t
\treturn 0;
} //Search_Bin

/<st.length>/<stdlib.h>/<stdio.h>/<malloc.h>/<code>

閱讀更多 zhexuewei 的文章

關鍵字: define tprintf 二分