请写出对有序表进行折半查找的非递归算法

1. 请写出对有序表进行折半查找的非递归算法。 2. 试将上述算法改写成递归算法。

#include #include

#define OK 1 #define ERROR 0

#define OVERFLOW -1

typedef int Status; typedef int ElemType;

typedef struct{ //有序表的定义 ElemType *elem; int length; }SSTable;

Status Binary_search(SSTable st, int key) { //非递归的折半查找

int low, mid, high;

low = 0; high = st.length-1; while (low<=high) { mid = (low+high)/2; if (key==st.elem[mid]) return mid;

else if (key

low = mid + 1; }

return ERROR; }

Status Binary_search_recur(SSTable st, int low, int high, int key) 折半查找

int mid= (low+high)/2; if (low > high) return ERROR;

{//递归的

}

if (key==st.elem[mid]) return mid;

else if (key

Binary_search_recur(st, low, mid-1, key); else

Binary_search_recur(st, mid+1, high, key);

Status SSTable_creation(SSTable &st)

{//创建查找表

printf(\ \ ); scanf(\, &st.length);

st.elem = (ElemType *)malloc(st.length * sizeof(ElemType)); if (!st.elem)

exit(OVERFLOW); ElemType pre = -1;

for (int i = 0; i < st.length; i ++) {

printf(\ element is : \, (1+i)); scanf(\, &pre );

if ((i > 0) && (st.elem[i-1] >= pre)) {//确保该查找表的内容是按整型

数递增次序排列

printf(\\\n\\n\);

return ERROR; }

st.elem[i]=pre; }

for (int i= 0; i

void Screen_prompt() { int key; SSTable st; while (true) {

if (!SSTable_creation(st)) continue;

printf(\table : \);

scanf(\, &key);

// if (!Binary_search_recur(st, 0, st.length -1, key)) //执行递归调用,

使用时去掉前面的\并注解掉下面一行即可

if (!Binary_search(st, key)) //执行非递归调用

printf(\, key); else

printf(\, key); printf(\); char ch=getchar(); ch = getchar();

if (('n' ==ch) || ('N'==ch)) break; } }

void main() {

Screen_prompt(); getchar(); getchar(); }