搜索

题目：堆栈搜索

存储结构：

物理存储结构：要查询的数据存放静态数组中。在查找时把对应元素的指针入栈出栈。

逻辑存储结构：采用静态数组的方法存储，在静态数组中的数据符合最大堆或最小堆的原则。

思想的形成：

在顺序搜索中需要逐次比较，其平均速度较慢；在折半搜索中虽速度较快，但要求数据按一定的顺序存放，对于无序的数据进行排序需要花费较多的时间。所以提出另外一种搜索方法：堆栈搜索（堆和栈配合使用）。因为对于无序的数据进行调整堆所花的时间相对较少。

在最小堆中任意一个子完全二叉树的跟元素为这子二叉树中最小的元素，所以我们可以根据查找元素与子二叉树的比较来判断是否要与这树中的其他元素继续比较。而且在建立最小堆所花费的时间不是很多（相对于把数组元素排序而言）。因为有可能与左孩子与右孩子相比较，所以我们要用栈来记录还需比较的元素。

算法思想：

堆栈搜索

定义一个堆的类和一个栈的类用来存放数组元素与元素的指针（下标）。

读入元素并建立最小堆。（如果要增加元素也要增加的时候同时建立最小堆）

进行搜索操作：数组为arr[],搜索元素为a；

Int i=0；进入循环（把最后一个元素设置为监视哨，用于判断循环结束）

A与arr[i]相比较；

相等 a小于arr[i] a大于arr[i]

如果i不等于当前元 出栈一元素继续比较。 先把其右孩子下标进栈

素加一返回找到元素 如果栈空，则返回 i=2i+1；继续比较

的下标否则返回-1； -1；

查看搜索函数返回的值：

返回值为-1， 返回值为一其他整数

说明没有找到要找到的元素 输出找到元素的相应信息

搜索结束，把栈置空返回。

程序代码为：

#include<iostream.h>

#include<fstream.h>

#include<stdlib.h>

#include<conio.h>

struct field {

char stu_num[6]; //比实际长度多1位

char name[7]; //比实际长度多1位

char sex[3]; //比实际长度多1位

intage;

//以考试成绩为排序关键码

};

template <class Type> class MinHeap;

//定义排序数据记录（一行数据的各列）

template <class Type> class Record {

friend class MinHeap<Type>;

private:

Type key; //排序关键码

field other; //其它数据列

public:

//提取排序关键码

Type getKey ( ) { return key; }

//修改排序关键码

void setKey ( const Type x ) { key = x; }

//重载判断运算符判this == x

bool operator == (Record<Type> x )

{ return key == x.key; }

//重载判断运算符 判this <= x

bool operator <= (Record<Type> x )

{ return key <= x.key; }

//重载判断运算符 判this < x

bool operator < (Record<Type> x )

{ return key < x.key; }

//重载判断运算符 判this > x

bool operator > (Record<Type> x )

{ return key > x.key; }

friend ifstream & operator >> ( ifstream & fin ,Record<Type>& x );

friend ostream & operator << ( ostream & fout ,Record<Type>& x );

};

//H0001潘刀郎 男 49 56.8

template <class Type>

ifstream & operator >> ( ifstream & fin ,Record<Type>& x )

{ fin>>x.other.stu_num;fin>>x.other.name;fin>>x.other.sex;

fin>>x.other.age;fin>>x.key;

return fin;

}

template <class Type>

ostream & operator << ( ostream & out ,Record<Type>& x ){

out<<x.other.stu_num<<"";out<<x.other.name<<"";out<<x.other.sex<<"";

out<<x.other.age<<"";out<<x.key<<"";

return out;

}

template <class Type> class headstracksearch;

//定义“最小堆”

template <class Type> class MinHeap{

friend class headstracksearch<Type>;

private:

Type * heap; //存放最小堆元素的数组

int CurrentSize;//堆当前元素个数

int HeapMaxSize; //堆元素个数上限

//私有成员函数：只能由公有成员函数调用

void FilterDown ( int i, int m );

//从 i 到m自顶向下进行调整成为最小堆

void FilterUp ( int i );

//从 i 到0自底向上进行调整成为最小堆

public:

MinHeap ();//无参构造函数

//构造函数：建立最小堆

MinHeap ( Type *, int , int );

~MinHeap ( ) ;

//删除堆顶元素

bool RemoveMin ( Type& x );

//向最小堆插入一个元素

bool Insert ( const Type x );

bool IsEmpty ( ) const;//判堆空否

bool display();

};

//构造函数：建立最小堆

template <class Type>

MinHeap <Type> ::MinHeap ( ):heap(NULL),CurrentSize(0),HeapMaxSize(0){

}

template <class Type>

MinHeap <Type> ::

MinHeap ( Type * p, int cur,int max )

{

HeapMaxSize = max;//

heap = p;

CurrentSize = cur;//当前堆大小

int currentPos = CurrentSize/2-1;

//找最初调整位置:最后的非叶子结点号

//从下到上逐步扩大,最后形成完整的堆

while ( currentPos >= 0 ) {

//对子树进行自顶向下调整，形成子堆。

FilterDown ( currentPos, CurrentSize-1 );

//从currentPos开始,到数组末尾止,调整

currentPos--;

}

}

//析构函数

template <class Type>

MinHeap <Type> ::~MinHeap ( ){

delete [] heap;

}

//对以序号start为根结点的子树进行

//自顶向下的调整，使其成为最小堆。

//参数EndOfHeap是子树里最后一个结点序号

template <class Type>

void MinHeap<Type> ::

FilterDown ( int start, int EndOfHeap )

{

int i = start;

int j = 2*i+1; // j 是 i 的左孩子

Type temp = heap[i]; //暂存子树的根

while ( j <= EndOfHeap ) { //调整完？

if ( j < EndOfHeap &&

heap[j] > heap[j+1] )j++;

//让j指向左右孩子中最小者

if ( temp <= heap[j] ) break;

//根结点不大于最小者，不调整

else { heap[i] = heap[j];//上浮调整

i = j; //向下滑动一层

j = 2*i+1; //j是i的左孩子

}

}

heap[i] = temp; //根结点归位

}

//判堆空否

template <class Type>

bool MinHeap <Type> :: IsEmpty ( ) const{

return CurrentSize==0;

}

//在堆中插入新元素 x

template <class Type>

bool MinHeap<Type> :: Insert ( const Type x )

{

if ( CurrentSize == HeapMaxSize ) { //堆满

cerr << "堆已满" << endl;

return false;

}

heap[CurrentSize] = x;//插在表尾

FilterUp (CurrentSize);//向上调整为堆

CurrentSize++; //堆元素增一

return true;

}

//从 start 开始,向上直到0,调整堆

template <class Type>

void MinHeap<Type> :: FilterUp ( int start )

{

int j = start,i = (j-1)/2;

// i 是 j 的双亲

Type temp = heap[j];//暂存起点元素

while ( j > 0 ) {//调整到栈顶

if ( heap[i] <= temp ) break;

//不用调了

else {//向上调整

heap[j] = heap[i];

j = i;i = (i -1)/2;

}

}

heap[j] = temp; //起点元素归位

}

template <class Type>

bool MinHeap <Type> :: display(){

for( int i=0; i<CurrentSize;i++)

cout<<heap[i]<<endl;

cout<<endl;

return true;

}

//栈

#define MAXSIZE 20

template<class Type>

class stack{//定义一个栈

protected:

int * p;//用数组的形式存放栈的元素

int imaxsize;//栈所能存放的最大元素个数

int itop;//栈中当前所存放的元素个数

public:

stack(int a=MAXSIZE);//缺省状况下的最大值为MAXSIZE

~stack();

bool push(Type &);//进栈

bool pop(Type &);//出栈

bool checkele(int a,Type & ele);//查看栈中与栈顶元素相距为a个的元素.元素返回在ele中

bool MakeEmpty();//置空栈

int IsEmpty();//判断是否为空

int IsFull();//判断是否为满

};

//构造函数

template<class Type>

stack<Type>::stack(int a)

{

imaxsize=a;itop=-1;

if(!(p=new Type[a]))

cerr<<"内存不足，不能运行此程序";

}

//析构函数

template<class Type>

stack<Type>::~stack(){

}

//进栈函数

template<class Type>

bool stack<Type>::push(Type &ele)

{

if(itop<imaxsize)

p[++itop]=ele;

else

return false;

return true;

}

//出栈函数

template<class Type>

bool stack<Type>::pop(Type &ele)

{

if(itop+1)//如果为空加一为零

ele=p[itop--];

else

return false ;

return true ;

}

//检查栈中数据的函数

template<class Type>

bool stack<Type>::checkele(int a,Type&ele)

{

if(itop-a>=0)

ele=p[itop-a];

else

return false ;

return true ;

}

//把栈置空函数

template<class Type>

bool stack<Type>::MakeEmpty()

{

if(itop+1)//已经为空

return false ;

itop=-1;

return true;

}

//判断栈是否为空函数

template<class Type>

int stack<Type>::IsEmpty()//判断是否为空

{

return itop+1;//如果为空则返回0

}

//判断栈是否为满函数

template<class Type>

int stack<Type>::IsFull()

{

return (itop+1)/imaxsize;

}

template<class Type>

class headstracksearch{

MinHeap<Type>*datalist; //最小堆的数组

stack <int>*Stack; //栈

bool isminheap;//是否为最小堆

public:

headstracksearch<Type>(Type * = NULL,int=10 , int=10);

~headstracksearch<Type>();

bool display();

int searchdata(Type & );

};

//构造函数

template<class Type>

headstracksearch<Type>::headstracksearch<Type>(Type * a,int b,int c)

:isminheap(true){

datalist = new MinHeap<Type>(a,b,c);

}

//析构函数

template<class Type>

headstracksearch<Type>::~headstracksearch<Type>(){

// deletedatalist;deleteStack;

}

template<class Type>

bool headstracksearch<Type>::display(){

datalist->display();

return true;

}

//查找函数

template<class Type>

int headstracksearch<Type>:: searchdata(Type & aa ){

if(!isminheap){

cout<<"数组中的数据不是按最小堆存放， 不能查找，按任意键退出"<<endl;

getch();

return -1;

}

Stack= new stack<int>(datalist->CurrentSize);

int i=0,a;

while(i<datalist->CurrentSize){

if(datalist->heap[i]==aa)

return i;

else if(datalist->heap[i]>aa){//出栈一元素继续比较,如果栈空，则返回-1

if(!Stack->pop(i))

return -1;

}

else{

a=2*i+2;

Stack->push(a);

i=2*i+1;

}

}

return -1;

}

//主函数

void main()

{

ifstream fin;

int a=15,i=0;

char filename[15]="wjh.txt";

Record<double> * p;

cout<<"请输入要建立最小堆数组的最大长度"<<endl;

// cin>>a;

p=new Record<double>[a+1];

// cout<<"请读入数据的文件"<<endl;

// cin>>filename;

fin.open(filename);

if( fin.fail() ){

cout<<"文件读取失败!!!"<<endl;

return ;

}

while(i<a&&!fin.eof() ){

fin>>p[i];

i++;

}

// datalist=new MinHeap<Type>;

headstracksearch< Record<double> >MINh(p,i,a+1);

MINh.display();

i=MINh.searchdata(p[2]);

if(i==-1){

while(a!=13){

cout<<"没有找到相应的数据,按回车键确定"<<endl;

a=getch();

}

return ;

}

cout<<"找到要找的数据: "<<p[i]<<endl;

}