1-95.c

1.6.1 顺序表的查找 273 范例1-94 顺序表的查找 273 ∷相关函数：Search_Seq函数 1.6.2 静态树表的查找 276 范例1-95 静态树表的查找 276 ∷相关函

#include<stdio.h> /* EOF(=^Z或F6),NULL */
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
#define N 9 /* 数据元素个数 */
typedef char KeyType; /* 设关键字域为字符型 */
typedef struct /* 数据元素类型 */
{
  KeyType key;
  int weight;
}ElemType;
ElemType r[N]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3},
               {'F',4},{'G',4},{'H',3},{'I',5}}; /* 数据元素(以教科书例9-1为例),全局变量 */
int sw[N+1]; /* 累计权值，全局变量 */
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef struct
{
  ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */
  int length; /* 表长度 */
}SSTable;
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 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;
}
typedef ElemType TElemType;
typedef struct BiTNode
{
  TElemType data;
  struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
Status SecondOptimal(BiTree *T, ElemType R[],int sw[],int low,int high)
{ /* 由有序表R[low..high]及其累计权值表sw(其中sw[0]==0)递归构造 */
  /* 次优查找树T。*/
  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]);
    }
  *T=(BiTree)malloc(sizeof(BiTNode));
  if(!*T)
    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。*/
  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");
}