// algo9-3.cpp 靜態查找表(靜態樹表)的操作
 #include"c1.h"
 #define N 9 // 數據元素個數
 typedef char KeyType; // 設關鍵字域為字符型
 struct ElemType // 數據元素類型(以教科書例9-1為例)
 {
   KeyType key;
   int weight;
 }r[N]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3},
       {'F',4},{'G',4},{'H',3},{'I',5}}; // 全局變量
 int sw[N+1]; // 累計權值，全局變量
 #include"c9.h"
 #include"c9-1.h"
 #include"bo9-1.cpp"

 typedef ElemType TElemType;
 #include"c6-2.h"
 Status SecondOptimal(BiTree &T, ElemType R[],int sw[],int low,int high)
 { // 由有序表R[low..high]及其累計權值表sw(其中sw[0]==0)遞歸構造
   // 次優查找樹T。算法9.3
   int i,j;
   double min,dw;
   i=low;
   min=fabs(sw[high]-sw[low]);
   dw=sw[high]+sw[low-1];
   for(j=low+1;j<=high;++j) // 選擇最小的△Pi值
     if(fabs(dw-sw[j]-sw[j-1])<min)
     {
       i=j;
       min=fabs(dw-sw[j]-sw[j-1]);
     }
   if(!(T=(BiTree)malloc(sizeof(BiTNode))))
     return ERROR;
   T->data=R[i]; // 生成結點
   if(i==low)
     T->lchild=NULL; // 左子樹空
   else
     SecondOptimal(T->lchild,R,sw,low,i-1); // 構造左子樹
   if(i==high)
     T->rchild=NULL; // 右子樹空
   else
     SecondOptimal(T->rchild,R,sw,i+1,high); // 構造右子樹
   return OK;
 }

 void FindSW(int sw[],SSTable ST)
 { // 按照有序表ST中各數據元素的Weight域求累計權值表sw
   int i;
   sw[0]=0;
   for(i=1;i<=ST.length;i++)
     sw[i]=sw[i-1]+ST.elem[i].weight;
 }

 typedef BiTree SOSTree; // 次優查找樹采用二叉鏈表的存儲結構
 Status CreateSOSTree(SOSTree &T,SSTable ST)
 { // 由有序表ST構造一棵次優查找樹T。ST的數據元素含有權域weight。算法9.4
   if(ST.length==0)
     T=NULL;
   else
   {
     FindSW(sw,ST); // 按照有序表ST中各數據元素的Weight域求累計權值表sw
     SecondOptimal(T,ST.elem,sw,1,ST.length);
   }
   return OK;
 }

 Status Search_SOSTree(SOSTree &T,KeyType key)
 { // 在次優查找樹T中查找關鍵字等于key的元素。找到則返回OK，否則返回FALSE
   while(T) // T非空
     if(T->data.key==key)
       return OK;
     else if(T->data.key>key)
       T=T->lchild;
     else
       T=T->rchild;
   return FALSE; // 順序表中不存在待查元素
 }

 void print(ElemType c) // Traverse()調用的函數
 {
   printf("(%c %d) ",c.key,c.weight);
 }

 void main()
 {
   SSTable st;
   SOSTree t;
   Status i;
   KeyType s;
   Creat_Ord(st,N); // 由全局數組產生非降序靜態查找表st
   Traverse(st,print);
   CreateSOSTree(t,st); // 由有序表構造一棵次優查找樹
   printf("\n請輸入待查找的字符: ");
   scanf("%c",&s);
   i=Search_SOSTree(t,s);
   if(i)
     printf("%c的權值是%d\n",s,t->data.weight);
   else
     printf("表中不存在此字符\n");
 }