/* bo9-1.c 靜態查找表(順序表和有序表)的基本操作(7個) */
 Status Creat_Seq(SSTable *ST,int n)
 { /* 操作結果: 構造一個含n個數據元素的靜態順序查找表ST(數據來自全局數組r) */
   int i;
   (*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType)); /* 動態生成n個數據元素空間(0號單元不用) */
   if(!(*ST).elem)
     return ERROR;
   for(i=1;i<=n;i++)
     *((*ST).elem+i)=r[i-1]; /* 將全局數組r的值依次賦給ST */
   (*ST).length=n;
   return OK;
 }

 void Ascend(SSTable *ST)
 { /* 重建靜態查找表為按關鍵字非降序排序 */
   int i,j,k;
   for(i=1;i<(*ST).length;i++)
   {
     k=i;
     (*ST).elem[0]=(*ST).elem[i]; /* 待比較值存[0]單元 */
     for(j=i+1;j<=(*ST).length;j++)
       if LT((*ST).elem[j].key,(*ST).elem[0].key)
       {
         k=j;
         (*ST).elem[0]=(*ST).elem[j];
       }
     if(k!=i) /* 有更小的值則交換 */
     {
       (*ST).elem[k]=(*ST).elem[i];
       (*ST).elem[i]=(*ST).elem[0];
     }
   }
 }

 Status Creat_Ord(SSTable *ST,int n)
 { /* 操作結果: 構造一個含n個數據元素的靜態按關鍵字非降序查找表ST */
   /* 數據來自全局數組r */
   Status f;
   f=Creat_Seq(ST,n);
   if(f)
     Ascend(ST);
   return f;
 }

 Status Destroy(SSTable *ST)
 { /* 初始條件: 靜態查找表ST存在。操作結果: 銷毀表ST */
   free((*ST).elem);
   (*ST).elem=NULL;
   (*ST).length=0;
   return OK;
 }

 int Search_Seq(SSTable ST,KeyType key)
 { /* 在順序表ST中順序查找其關鍵字等于key的數據元素。若找到，則函數值為 */
   /* 該元素在表中的位置，否則為0。算法9.1 */
   int i;
   ST.elem[0].key=key; /* 哨兵 */
   for(i=ST.length;!EQ(ST.elem[i].key,key);--i); /* 從后往前找 */
   return i; /* 找不到時，i為0 */
 }

 int Search_Bin(SSTable ST,KeyType key)
 { /* 在有序表ST中折半查找其關鍵字等于key的數據元素。若找到，則函數值為 */
   /* 該元素在表中的位置，否則為0。算法9.2 */
   int low,high,mid;
   low=1; /* 置區間初值 */
   high=ST.length;
   while(low<=high)
   {
     mid=(low+high)/2;
     if EQ(key,ST.elem[mid].key)  /* 找到待查元素 */
       return mid;
     else if LT(key,ST.elem[mid].key)
       high=mid-1; /* 繼續在前半區間進行查找 */
     else
       low=mid+1; /* 繼續在后半區間進行查找 */
   }
   return 0; /* 順序表中不存在待查元素 */
 }

 Status Traverse(SSTable ST,void(*Visit)(ElemType))
 { /* 初始條件: 靜態查找表ST存在，Visit()是對元素操作的應用函數 */
   /* 操作結果: 按順序對ST的每個元素調用函數Visit()一次且僅一次。 */
   /* 一旦Visit()失敗，則操作失敗 */
   ElemType *p;
   int i;
   p=++ST.elem; /* p指向第一個元素 */
   for(i=1;i<=ST.length;i++)
     Visit(*p++);
   return OK;
 }