seqlist.h

B-树实现索引和快速查找

#include<stdlib.h>
#include<iostream.h>
const int defaultSize=30;
template <class Type> class SeqList {
       Type *data;          //顺序表存储数组
	   int MaxSize;	         //最大允许长度	
	   int last; 	         //当前最后元素下标
public:
	   SeqList ( int MaxSize = defaultSize );
	   ~SeqList ( ) { delete [ ] data; }		
	   int Length ( ) const { return last+1; }
	   int Find (const Type & x ) const;
        int IsIn ( Type & x );				
        int Insert ( Type & x);		
        int Remove (const Type & x );			
        int Next ( Type & x ) ;				
	    int Prior ( Type & x ) ;
        int IsEmpty ( ) { return last ==-1; }	
        int IsFull ( ) { return last == MaxSize -1; }	
		Type& operator [] ( int i ) {
			if (i < 0 || i > last)
			{cerr<<"Index out of Range.\n";exit(1);}
			else return data[i];
        }
 };	   				
//构造函数
template <class Type>	
 SeqList<Type>::SeqList ( int sz ) {
      if ( sz > 0 ) {
	      MaxSize = sz;  last = -1;			
	      data = new Type[MaxSize];		
	  }
	}

template <class Type>	
int SeqList<Type>::Find (const Type & x ) const
{
     int  i = 0;
     while ( i <= last && data[i] != x )
          i++;		
     if ( i > last ) return -1;				
     else return i;					
}

//在表中第 i 个位置插入新元素 x
template <class Type>
int SeqList<Type>::Insert ( Type & x){
     if (  last == MaxSize-1 )
  	  return 0;                //插入不成功	
     else {
		  data[++last]=x;
          return 1;               //插入成功       
     }
}

template <class Type>
 int SeqList<Type>::Remove (const Type & x ) {
      int i = Find (x);	       //在表中搜索 x
     if ( i >= 0 ) {				
         data[i]=data[last];
		 last--;
         return 1;            //成功删除	
     }	
     return 0;                 //表中没有 x
 }