//錯誤大概有三：頭文件後邊要有using namespace std；main函數要有返回值；
//建表函數的第壹個參數應該是ST的引用，不能是新建的ST表。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//#include <stdio.h>
//#include <cstdlib>
//#include "malloc.h"
using namespace std;
typedef struct//元素定義
{
int key;
}ElemType;
typedef struct{ //定義靜態查找表類型
ElemType *elem;//表基址,elem[0]留空
int n; //表長
}SSTable;
void CreateTable(SSTable &ST, ElemType *A, int n)
{ //建立靜態查找表
int i;
unsigned int Size;
Size = (n+1) * sizeof(ElemType); //分配空間字節數(因elem[0]留空，故需n+1個空間)
ST.elem = (ElemType *)malloc(Size);
ST.n = n;
for (i = 1; i <= n; i++)
ST.elem[i] = A[i-1];
}
int Search_Seq(SSTable ST, int k)
{ //順序查找：在順序表ST中找關鍵字為k的記錄，若成功則返回記錄位置，否則返回0
int j;
j = ST.n; //從表高端開始查找
ST.elem[0].key = k; //崗哨
while(ST.elem[j].key != k)
{
j--;
}
return j;
}
int Search_Bin(SSTable ST, int k)
{ //二分查找：在升序表ST中查找鍵值等於k的元素，若查找成功，返回該元素的位置號，否則返回0
int low, hig, mid;
low = 1; //低
hig = ST.n; //高
while(low <= hig)
{
mid = (low + hig) / 2;//MID
if(k == ST.elem[mid].key)
return mid;
else if(k < ST.elem [mid].key)
hig = mid - 1;
else
low = mid + 1;
}
return 0;
}
void ShowTable(SSTable ST)
{//顯示表
int i, n;
n = ST.n;
printf("\n位置: ");
for (i = 1; i <= n; i++)
printf("%4d", i);
printf("\n元素: ");
for (i = 1; i <= n; i++)
printf("%4d", ST.elem[i]);
printf("\n表長: %4d\n", ST.n);
}
int main()
{
int k1,k2;
int i,i1,i2;
SSTable ST;
ElemType A[4];
int n=4; //表長為4
printf("輸入表元素A[1..4]: ");
for(i=0;i<n;i++)
scanf("%d",&A[i]);
CreateTable(ST, A, n); //建立靜態查找表ST
printf("關鍵字表: ");
ShowTable(ST);
printf("\n");
printf("輸入查詢的關鍵字k:");
scanf("%d",&k1);
i1 = Search_Seq(ST, k1);
printf("關鍵字為%2d的位置為%2d\n", k1, i1);
printf("輸入查詢的關鍵字k:");
scanf("%d",&k2);
i2 = Search_Bin(ST, k2);
printf("關鍵字為%2d的位置為%2d\n", k2, i2);
return 0;
}