findfunc.cpp

数据结构中有关查找的所有算法

/******************************************************************************
    以下这些函数完成表的顺序查找，折半查找、静态树表的次优查找，二叉排序树的构
	造，结点插入及删除等操作       
	相关的存储结构定义在WORK19.H中

                                                            编写者：黄海于
										                    2002、12、6
******************************************************************************/
#include "work19.h"

/******************************************************************************
    函数：SSTable *CreateSTable(int Choice);

    功能：建立顺序查找表，根据choice的不同，可设定或不设定权值,0号存储单元没有
	      放具体的元素，表中的元素从1号存储单元开始。

    形式参数：
	      Choice:  确定权值是否相同。如果为1，则为静态树表的查找，权值不同。其它
		           则为1，如果为折半查找，则要求按从小到达的顺序建立该表。

    函数输出：
	      无
******************************************************************************/
SSTable *CreateSTable(int Choice)
{
     SSTable *st;
     int i;
     //建立顺序查找表，分配内存
     st=(SSTable*)malloc(sizeof(SSTable));
     
	 //输入表长
     printf("Please input length of Table:");
     scanf("%d",&st->length);
	 //给每个元素分配存储单元
     st->elem=(ElemType *)malloc(sizeof(ElemType)*(st->length+1));
   
	 //输入每个元素，如果权值不相同，则输入权值，由Choice确定
     for(i=1;i<=st->length;i++){
         printf("Please input element %d==>data",i);
	     if(Choice==1)
			 printf(" weight");
		 printf(":");
		 scanf("%f",&(st->elem[i].key));
		 if(Choice==1)
			 scanf("%f",&(st->elem[i].weight));		
	 }

   return st;
}

/******************************************************************************
    函数： int SeqSearch(SSTable *ST, float key)；

    功能： 采用顺序查找方法查找表中的元素

    形式参数：
	      ST：  顺序查找表
          key： 查找关键字
    函数输出：
	      关键字在查找表中的位置，为0表示没有找到，非0，则为实际位置
******************************************************************************/
int SeqSearch(SSTable *ST, float key)
{
     int i;
    
	 //设立监视哨
	 ST->elem[0].key=key;
	 //查找关键字
	 for(i=ST->length;ST->elem[i].key!=key;--i)
		 ;

   return i;
}   

/******************************************************************************
    函数： int SeqSearch(SSTable *ST, float key)；

    功能： 采用顺序查找方法查找表中的元素

    形式参数：
	      ST：  顺序查找表
          key： 查找关键字
    函数输出：
	      关键字在查找表中的位置，为0表示没有找到，非0，则为实际位置
******************************************************************************/
int BinarySearch(SSTable *st, float key)
{

	 int low,high,mid;

	 //设立起始位置
     low=1;
	 high=st->length;
	 //但low小于high时，继续查找
	 while(low<=high){
		 //计算mid的值
		 mid=(low+high)/2;
		 //如果关键字等于中间元素，则返回
		 if(key==st->elem[mid].key)
			 return mid;
		 //如果小于，则往前查找
		 else if(key<st->elem[mid].key)
			 high=mid-1;
		 //如果大于，则往后查找
		 else
			 low=mid+1;
	 }

  return 0;
}

/******************************************************************************
    函数： BiTree CreateSTree(SSTable  *st);

    功能： 建立次优查找树

    形式参数：
	      st：  顺序查找表
    函数输出：
	      指向次优查找树的指针
******************************************************************************/
BiTree CreateSTree(SSTable  *st)
{

	float *sw;
	int   i;
	BiTree T;

	//如果查找表的长度为0，则查找树为NULL
	if(st->length==0)
		T=NULL;
	//反之，求每个元素对应的权值之和，然后根据次优查找算法求次优查找树
	else{
		sw=(float *)malloc(sizeof(float)*(st->length+1));
	    sw[0]=0;
		for(i=1;i<=st->length;i++)
			sw[i]=sw[i-1]+st->elem[i].weight;
        //建立次优查找树
        OptimalSearch(T,st->elem,sw,1,st->length);	
	}
  return T;
}

/******************************************************************************
    函数：int OptimalSearch(BiTree &T, ElemType *R, float *sw,int low,int high);

    功能：按照次优查找方法，建立次优查找树

    形式参数：
	      T：   次优查找树首址
          R：   查找表中的元素首址
		  sw:   每个元素对应的权值之和
		  low:  查找表的低地址
		  high: 查找表高地址
    函数输出：
	      0:    内存分配失败
		  1:    成功建立次优查找树
******************************************************************************/
int OptimalSearch(BiTree &T, ElemType *R, float *sw,int low,int high)
{
     int i,j;
     float min,dw;
	 	 
	 //起始地址
	 i=low;
	 //计算起始差值delta P
	 min=(float)fabs(sw[high]-sw[low]);
	 //计算h和l-1权值之和
	 dw=sw[high]+sw[low-1];
	 //计算每一个元素对应的delta P,并与前一个比较，如果小于前一个，则记录其
	 //对应的的位置，保存在i中
     for(j=low+1;j<=high;++j){
		 if(fabs(dw-sw[j]-sw[j-1])<min){
			 i=j;
			 min=(float)fabs(dw-sw[j]-sw[j-1]);
		 }
	 }

	 //这样第i个元素为所要求的结点
	 if(!(T=(BiTree )malloc(sizeof(BiTNode))))
		 return 0;
     T->e=R[i];
	 //如果该元素在low的位置，显然该次优查找树没有左子树
	 if(i==low)
		 T->lchild=NULL;
	 //反之，则对其左边的元素采用相同的方法建立次优查找树
	 else
		 OptimalSearch(T->lchild,R,sw,low,i-1);

	 //如果该元素在high的位置，显然该次优查找树没有右子树
	 if(i==high)
		 T->rchild=NULL;
	 //反之，则对其右边的元素采用相同的方法建立次优查找树
     else
		 OptimalSearch(T->rchild,R,sw,i+1,high);

  return 1;
}

/******************************************************************************
    函数：IndexTable *CreateIndexTable(void);

    功能：建立索引表，根据查找表中元素及其相对位置建立索引表

    形式参数：
	      无
    函数输出：
	      索引表起始地址
******************************************************************************/
IndexTable *CreateIndexTable(void)
{
     IndexTable *It;
     int i;

	 //给索引表分配存储单元
	 It=(IndexTable*)malloc(sizeof(IndexTable));
	 //输入索引表中关键字的数目
     printf("Please input Length of MaxKey:");
	 scanf("%d",&It->length);

	 //分配空间，并输入关键字的值
     It->kt=(KeyTable*)malloc(sizeof(KeyTable)*(It->length+1));
	 for(i=1;i<=It->length;i++){
		 printf("Please input No.%d MaxKey and StartPos:",i);
		 scanf("%f%d",&(It->kt[i].MaxKey.key),&(It->kt[i].pos));		 
	 }

   return It;
}

/******************************************************************************
    函数：int TableSearch(IndexTable *index,SSTable *st,float key)；

    功能：根据索引表确定元素的分块，然后再在分块中查找相应的关键字。分块查找采
	      用折半查找方法，块内查找采用顺序查找

    形式参数：
	      IndexTable:  索引表起始地址
		  st:          查找表起始地址
		  key:         待查找的关键字
    函数输出：
	      0:       无法找到关键字key
		  非0：    关键字所在的位置
******************************************************************************/
int TableSearch(IndexTable *index,SSTable *st,float key)
{
       
     int i;
     int low,high,mid;

	 //设立起始位置
     low=1;
	 high=index->length;
	 //但low小于high时，继续查找
	 while(low<=high){
		 //计算mid的值
		 mid=(low+high)/2;
		 //如果关键字等于中间元素，则返回
		 if(key==index->kt[mid].MaxKey.key){
			 high=mid-1;
			 break;
		 }
		 //如果小于，则往前查找
		 else if(key<index->kt[mid].MaxKey.key)
			 high=mid-1;
		 //如果大于，则往后查找
		 else
			 low=mid+1;
	 }
    
	 //获取起始位置
	 low=index->kt[high+1].pos;
	 if(high+2>=index->length)
		 high=st->length;
	 else
	     high=index->kt[high+2].pos;
     
	 //查找关键字
	 for(i=low;i<high;++i){
		 if(st->elem[i].key==key)
			 return i;
	 }

  return 0;

}

/******************************************************************************
    函数：BiTree CreateBSTree(void)；

    功能：建立二叉排序树

    形式参数：
	      无

    函数输出：
	      建立后的二叉排序树的头指针
******************************************************************************/
BiTree CreateBSTree(void)
{
     BiTree    bt;
	 int       i,length;
	 ElemType  e;
	 
	 //给根结点分配存储空间
	 bt=(BiTree)malloc(sizeof(BiTNode));
	 //输入序列长度
     printf("Please input length of Table:");
	 scanf("%d",&length);
     bt->lchild=NULL;
	 bt->rchild=NULL;

	 //建立每个结点
	 for(i=1;i<=length;i++){
		 printf("Please input Node %d:",i);
		 scanf("%f",&(e.key));
		 if(i==1){
			 bt->e.key=e.key;
			 continue;
		 }
		 InsertNode(bt,&e);		
	 }
  
  return bt;

}

/******************************************************************************
    函数：BiTree SearchBSTree(BiTree bt, ElemType *e, int *Notfind);

    功能：在二叉排序树中查找规定的关键字，如果关键字相同，则查找成功，并返回与
	      关键字相同结点的指针；如果查找不成功，则返回其双亲结点的指针

    形式参数：
	      bt:       二叉排序树的头指针
		  e:        待查找的关键字
		  Notfind:  返回的查找成功与否以及该结点是其双亲结点的左孩子还是右孩子
		            的标志。如果为0，表明查找成功，函数返回的是查找到的结点指
					针；如果为1和2，则查找不成功，为1表明待插入结点为其
    函数输出：
	      0:       无法找到关键字key
		  非0：    关键字所在的位置
******************************************************************************/
BiTree SearchBSTree(BiTree bt, ElemType *e, int *Notfind)
{
     BiTree p,q;
     
	 //从根结点开始进行查找
	 p=q=bt;
	 //如果不为空，则继续查找
     while(p!=NULL){
		 //保存当前结点的指针
		 q=p; 
		 //如果关键字相同，则返回查找到的信息
		 if(p->e.key==e->key){
			 *Notfind=0;
			 break;
		 }

		 //如果插入结点的关键字小于原二叉排序树中的结点的关键字，则从左找
		 if(p->e.key>e->key){
			 p=p->lchild;	
			 *Notfind=1;
		 }
		 //反之，则从右找
		 else{
			 p=p->rchild;
			 *Notfind=2;
		 }
	 }

	 //返回找到的结点的位置，或者待连接的结点的位置
  return q;
}

/******************************************************************************
    函数：void InsertNode(BiTree bt, ElemType *e)

    功能：在二叉排序树中插入关键字e

    形式参数：
	      bt:       二叉排序树的头指针
		  e:        待插入的关键字
	
    函数输出：
	      无
******************************************************************************/
void InsertNode(BiTree bt, ElemType *e)
{
     BiTree q,p;
	 int Notfind;
	 //查找原来的二叉排序数中是否有关键字为e.key的结点，如果有，则Notfind=0
	 //如果没有，则插入到该二叉排序树中。如果Notfind=1，则插入在q的左孩子,
	 //如果为2，则插入在其右孩子
	 q=SearchBSTree(bt,e,&Notfind);

     //根据上述原则插入结点
	 if(Notfind){
         p=(BiTree)malloc(sizeof(BiTNode));
	     p->e.key=e->key;
	  	 p->lchild=p->rchild=NULL;
		 p->parent=q;
		 if(Notfind==1)
			 q->lchild=p;
		 else
			 q->rchild=p;
	 }
	 
   return;
}

/******************************************************************************
    函数：int DeleteNode(BiTree bt, ElemType *e)

    功能：删除二叉排序树中值为e的结点

    形式参数：
	      bt:       二叉排序树的头指针
		  e:        待删除的关键字
	
    函数输出：
	      0:   没有找到该结点
		  1：  删除成功
******************************************************************************/
int DeleteNode(BiTree bt, ElemType *e)
{
     int   Notfind;
     BiTree  q,p,s;

	 //查找该结点的位置
     q=SearchBSTree(bt,e,&Notfind);
   
	 //如果没有找到该结点，则返回
     if(Notfind)
	     return 0;
	 //如果该结点的右孩子为空，则将其右孩子作为其双亲结点的右孩子，然后
	 //删除该结点，是左孩子时，也采用相同的处理方法
     if(q->rchild==NULL){
        q->parent->lchild=q->lchild;
        free(q);
	    return 1;
	 }	 
	 if(q->lchild==NULL){
		 q->parent->rchild=q->rchild;
		 free(q);
		 return 1;
	 }
     //如果左右孩子都不空，则将该结点的右孩子作为其左孩子的最右边的一个结点的
	 //右孩子，将其左孩子作为其双亲结点的左孩子，然后删除该结点
	 p=q->lchild;
	 while(q!=NULL){
		 s=p;
		 p=p->rchild;
	 }
	 s->rchild=q->rchild;
	 q->parent->lchild=q->lchild;
	 free(q);

  return 1;
}