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

 void Ascend(SSTable &ST)
 { // 重建靜態(tài)查找表為按關(guān)鍵字非降序排序
   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)
 { // 操作結(jié)果: 構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)按關(guān)鍵字非降序查找表ST
   // 數(shù)據(jù)來自全局?jǐn)?shù)組r
   Status f;
   f=Creat_Seq(ST,n);
   if(f)
     Ascend(ST);
   return f;
 }

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

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

 int Search_Bin(SSTable ST,KeyType key)
 { // 在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為
   // 該元素在表中的位置，否則為0。算法9.2
   int low,high,mid;
   low=1; // 置區(qū)間初值
   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; // 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找
     else
       low=mid+1; // 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找
   }
   return 0; // 順序表中不存在待查元素
 }

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