heapsearch.cpp

用VC。NET2005实现优秀的最近邻搜索算法LB-TREE的模拟和图形显示。具有建立优良数据结构和搜索功能

#include "StdAfx.h"
#include "HeapSearch.h"

HeapSearch::HeapSearch(void)
{
	LB_TreeRoot=NULL;
    QueryPoint=NULL;
	NodePtr=NULL;
	ElemNum=0;
}
HeapSearch::HeapSearch(Cluster* Root,NPoint* Query)
{
	LB_TreeRoot=Root;
	QueryPoint=Query;
	NodePtr=NULL;
	ElemNum=0;
}
HeapSearch::~HeapSearch(void)
{
}

// 初始化堆的数据集合
void HeapSearch::InitialNode(void)
{
	ElemNum=(int)LB_TreeRoot->GetSubCluster()->GetSize();
	NodePtr=new Elem[ElemNum+1];
	for(int i=1;i<=ElemNum;i++)
	{
		(NodePtr+i)->ClusterPtr=(Cluster*)LB_TreeRoot->GetSubCluster()->GetAt(i-1);
		(NodePtr+i)->DisLB=(NodePtr+i)->ClusterPtr->DisLB(QueryPoint);
	}
}

// 对ＬＢ－ＴＲＥＥ进行堆排序，返回最近邻
Cluster* HeapSearch::NearestNeighbor(void)
{
	InitialNode();
	HeapSort();
	while(LB_TreeRoot->GetSubCluster()->GetSize()>0)
	{
		InsertSub();
		HeapSort();
	}
	return LB_TreeRoot;
}


// 堆排序
void HeapSearch::HeapSort(void)
{
	Elem Temp;
	for(int i=ElemNum/2;i>0;--i)
		HeapAdjust(i,ElemNum);
	for(int i=ElemNum;i>1;--i)
	{
		Temp=*(NodePtr+1);
		*(NodePtr+1)=*(NodePtr+i);
		*(NodePtr+i)=Temp;
		HeapAdjust(1,i-1);
	}
    LB_TreeRoot=(NodePtr+1)->ClusterPtr;
}

// 调整堆
void HeapSearch::HeapAdjust(int s, int m)
{
    Elem rc;
	rc=*(NodePtr+s);
	for(int j=2*s;j<=m;j*=2)
	{
		if((j<m)&&((NodePtr+j)->DisLB<(NodePtr+j+1)->DisLB)) ++j;
		if(rc.DisLB>=(NodePtr+j)->DisLB) break;
			*(NodePtr+s)=*(NodePtr+j);
		s=j;
	}
	*(NodePtr+s)=rc; //插入
}

// 将节点的后代节点插入堆排序
void HeapSearch::InsertSub(void)
{
	int SubNum=(int)LB_TreeRoot->GetSubCluster()->GetSize();
    int OldNum=ElemNum;
	ElemNum+=SubNum-1;
    Elem* Ptr=new Elem[ElemNum+1];
    for(int i=1;i<=ElemNum;i++)
	{
		if(i<OldNum)
			*(Ptr+i)=*(NodePtr+i+1);
		else
		{
			(Ptr+i)->ClusterPtr=(Cluster*)(LB_TreeRoot->GetSubCluster()->GetAt(i-OldNum));
			(Ptr+i)->DisLB=(Ptr+i)->ClusterPtr->DisLB(QueryPoint);
		}
	}
    NodePtr=Ptr;
}