seqlist.h

来自「基于c++的数据结构源代码。是学习数据结构的很好的demo」· C头文件 代码 · 共 106 行

#include <stdio.h>
#include <assert.h>
#include<iostream.h>
#define DefaultSize 100

template <class Type> class SeqList {

public:
    SeqList ( const int size = DefaultSize );//构造数组
    ~SeqList() { delete[] data; }
    int Length() const { return last + 1; }
    int Find( const Type & x ) const;//查找数组中的元素的位置
    int IsIn ( Type & x);//判断x是否在数组中
    int Insert ( Type & x, int i );//在i位置插入指定元素x
    int Remove ( Type & x);//从x开始,往后的元素前移,数组长减1.
    int Next ( Type & x );//返回x的下一个元素的位置.
    int Prior ( Type & x );//返回x的上一个元素的位置
    int IsEmpty()const { return last == -1; }
    int IsFull() const { return last == MaxSize - 1; }
    Type Get( int i ) { return i < 0 || i > last ? NULL:data[i]; }//获取i位置的元素值
    void Print();
private:
    Type *data;
    int MaxSize;
    int last;
};

template < class Type > SeqList <Type>::SeqList( const int size  ) {
    assert ( size >= 0 );
    if ( size > 0 ) {
       MaxSize = size;  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;//查找数组中的元素的位置
}

template < class Type > int SeqList <Type>::IsIn( Type & x ) {
    int i = 0, found = 0;
    while ( i <= last && !found)
	if ( data[i] != x ) i++;
	else found = 1;
    return found;
}//判断x是否在数组中

template < class Type > int SeqList <Type>::Insert(  Type & x, int i ) {
    if ( i < 0 || i > last+1 || last == MaxSize - 1 ) return 0;
    else {
	last++;
	for ( int j = last; j > i; j-- ) data[j] = data[j-1];
	data[i] = x;
	return 1;
    }
}//在i位置插入指定元素x

template < class Type > int SeqList <Type>::Remove( Type & x ) {
    int i = Find(x);
    if ( i >= 0 ) {
	last--;
	for ( int j = i; j <= last; j++ ) data[j] = data[j+1];
	return 1;
    }
    return 0;//从x开始,往后的元素前移,数组长减1.
}

template < class Type > int SeqList <Type>::Next( Type & x ) {
    int i = Find(x);
    if ( i >= 0 && i < last ) return i+1;
    else return -1;//返回x的下一个元素的位置.
}

template < class Type > int SeqList <Type>::Prior( Type & x ) {
    int i = Find(x);
    if ( i > 0 && i <= last ) return i-1;
    else return -1;//返回x的上一个元素的位置
}

template < class Type > void Union( SeqList <Type> & LA, SeqList <Type> & LB ) {
    int n = LA.Length(); int m = LB.Length();
    for ( int i=0; i <= m; i++ ) {
	Type x = LB.Get(i);
	int k = LA.Find(x);
	if ( k == -1 ) { LA.Insert( x, n );  n++;}
    }
}//以LA返回LA与LB的并集

template < class Type > void Intersection ( SeqList <Type> & LA, SeqList <Type> & LB ) {
    int n = LA.Length();  int m = LB.Length();  int i = 0;
    while ( i < n ) {
	Type x = LA.Get(i);
	int k = LB.Find(x);
	if ( k == -1 ) { LA.Remove(x); n--; }
	else i++;
    }
}//删除LA中在LB中未出现的元素,即以LA返回LA与LB的交集

template < class Type > void SeqList <Type>::Print() {
    if ( last == -1 ) cout << "It is empty" ;
    else for ( int i=0; i<=last; cout << "  data[" << i++ << "] = " << data[i] );
    cout << endl;//打印数组元素
}