#ifndef LIST_HPP
#define LIST_HPP
#include <iostream>
#include <string>
using namespace std;
#define DefaultListSize 1000
template< typename Elem>
class List
{
public:
virtual void clear() = 0; // 清空表
virtual bool insert( const Elem& )= 0; // 从表中当前位置插入元素
virtual bool append( const Elem& )= 0; // 从表中后面插入元素
virtual bool remove( Elem& )= 0; // 移除该元素，并且用引用返回该元素
virtual void setStart() = 0; // 将表当前位置指向第一个
virtual void setEnd() = 0; // 将表当前位置指向最后元素
virtual void pre() = 0; // 将指针移向当前位置前一个
virtual void next() = 0; // 将指针移向当前位置的下一个
virtual int rightLength() const= 0; // 指针后面数据的大小
virtual int leftLength() const= 0; // 指针前面数据的大小
virtual bool setPos( int pos )= 0; // 设置当前指针
virtual bool getValue( Elem& ) const= 0; // 获得当前指针所指元素
virtual void print() const= 0; // 输出信息
virtual bool find( Elem const& data )= 0; // 能否在表中找到元素 data
virtual int length() const= 0; // 整个表的长度
virtual bool empty() const= 0; // 表是否为空
};
#endif
#ifndef ALIST_HPP
#define ALIST_HPP
#include "List.hpp"
template<typename Elem>
class AList: public List<Elem>
{
private:
int maxSize;
int listSize;
int fence;
Elem* listArray;
public:
AList( int size= DefaultListSize );
~AList();
void clear();
bool insert( const Elem& );
bool append( const Elem& );
bool remove( Elem& );
void setStart() ;
void setEnd() ;
void prev() ;
void next();
int rightLength() const;
int leftLength() const;
bool setPos( int pos );
bool getValue( Elem& ) const;
void print() const;
int length() const;
bool find( Elem const& data );
bool empty() const;
int getMaxSize() const;
int getListSize() const;
int getFence() const;
AList<Elem>& operator= ( AList<Elem>& t );
Elem& operator[]( int i );
};
template<typename Type>
AList<Type>::AList( int size )
{
maxSize= size;
listSize= fence= 0;
listArray= new Type[maxSize];
}
template<typename Type>
AList<Type>::~AList()
{
delete [] listArray;
}
template<typename Type>
void AList<Type>::clear()
{
listSize= fence= 0;
}
template<typename Type>
bool AList<Type>::insert( Type const& Item )
{
if( listSize== maxSize ) return false;
for( int i= listSize; i> fence; i-- )
listArray[i]= listArray[i-1];
listArray[fence]= Item;
listSize++;
return true;
}
template<typename Type>
bool AList<Type>::append( Type const& Item )
{
if( listSize== maxSize ) return false;
listArray[listSize++]= Item;
return true;
}
template<typename Type>
bool AList<Type>::remove( Type& Item )
{
if( rightLength()== 0 ) return false;
for( int i= fence; i< listSize- 1; ++i )
listArray[i]= listArray[i+1];
listSize--;
return true;
}
template<typename Type>
void AList<Type>::prev()
{
if( fence> 0 ) fence--;
}
template<typename Type>
void AList<Type>::next()
{
if( fence<= listSize ) fence++;
}
template<typename Type>
int AList<Type>::rightLength() const
{
return listSize- fence;
}
template<typename Type>
int AList<Type>::leftLength() const
{
return fence;
}
template<typename Type>
int AList<Type>::length() const
{
return listSize;
}
template<typename Type>
bool AList<Type>::setPos( int pos )
{
if( pos< 0 || pos> listSize ) return false;
fence= pos;
return true;
}
template<typename Type>
bool AList<Type>::getValue( Type& Item ) const
{
if( fence< 0 || fence>= listSize ) return false;
Item= listArray[fence];
return true;
}
template<typename Type>
void AList<Type>::setStart()
{
fence= 0;
}
template<typename Type>
void AList<Type>::setEnd()
{
fence= listSize;
}
template<typename Type>
bool AList<Type>::find( Type const& data )
{
for( int i= 0; i< listSize; ++i )
if( listArray[i]== data ) return true;
return false;
}
template<typename Type>
void AList<Type>::print() const
{
int t= 0;
for( t= 0; t< fence; ++t ) cout << listArray[t] << ' ';
cout << '|' << ' ';
for( t= fence; t< listSize; ++t ) cout << listArray[t] << ' ';
}
template<typename Type>
bool AList<Type>::empty() const
{
return listSize== 0;
}
template<typename Type>
AList<Type>& AList<Type>::operator= ( AList<Type>& t )
{
maxSize= t.getMaxSize();
listSize= t.getListSize();
fence= t.getFence();
listArray= new Type[maxSize];
for( int i= 0; i< listSize; ++i )
listArray[i]= t[i];
return *this;
}
template<typename Type>
Type& AList<Type>::operator[]( int i )
{
return listArray[i];
}
template<typename Type>
int AList<Type>::getMaxSize() const
{
return maxSize;
}
template<typename Type>
int AList<Type>::getListSize() const
{
return listSize;
}
template<typename Type>
int AList<Type>::getFence() const
{
return fence;
}
#endif
#ifndef LLIST_HPP
#define LLIST_HPP
#include "list.hpp"
#include <iostream>
using namespace std;
/////////////////////////////////////////////////////////
// 结点类， 使用可利用空间表实现
/////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
template<typename Type>
class CLink
{
private:
static CLink<Type>* freelist;
public:
Type element;
CLink* next;
public:
void* operator new ( size_t );
void operator delete( void* );
CLink();
CLink( Type, CLink<Type>* );
};
template<typename Type>
CLink<Type>* CLink<Type>::freelist= NULL;
template<typename Type>
CLink<Type>::CLink()
{}
template<typename Type>
CLink<Type>::CLink( Type a, CLink<Type>* b ):
element(a), next(b)
{}
template<typename Type>
void* CLink<Type>::operator new( size_t )
{
if( freelist== NULL ) return ::new CLink<Type>;
CLink<Type>* temp= freelist;
freelist= freelist->next;
return temp;
}
template<typename Type>
void CLink<Type>::operator delete( void* t )
{
((CLink<Type>*)t)->next= freelist;
freelist= ( CLink<Type>* )t;
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
/// 链表实现
/////////////////////////////////////////////////////////////////
template<typename Type>
class LList: public List<Type>
{
private:
CLink<Type>* head, *tail, *fence;
int leftcnt, rightcnt;
public:
LList( int size= DefaultListSize );
~LList();
void clear();
bool insert( const Type& );
bool append( const Type& );
bool remove( Type& );
void setStart() ;
void setEnd() ;
void pre() ;
void next();
int rightLength() const;
int leftLength() const;
bool setPos( int pos );
bool getValue( Type& ) const;
void print() const;
int length() const;
bool find( Type const& data );
bool empty() const;
void init();
void removeall();
bool setvalue( int pos, Type t );
bool setvalue( Type t );
};
template<typename Type>
LList<Type>::LList( int size )
{
init();
}
template<typename Type>
void LList<Type>::init()
{
fence= tail= head= new CLink<Type>;
leftcnt= rightcnt= 0;
}
template<typename Type>
void LList<Type>::removeall()
{
while( head!= NULL )
{
fence= head;
head= head->next;
delete fence;
}
}
template<typename Type>
LList<Type>::~LList()
{
removeall();
}
template<typename Type>
void LList<Type>::clear()
{
removeall();
init();
}
template<typename Type>
void LList<Type>::setStart()
{
fence= head;
rightcnt+= leftcnt;
leftcnt= 0;
}
template<typename Type>
void LList<Type>::setEnd()
{
fence= tail;
leftcnt+= rightcnt;
rightcnt= 0;
}
template<typename Type>
void LList<Type>::next()
{
if( fence!= tail ) fence= fence->next, rightcnt--, leftcnt++;
}
template<typename Type>
int LList<Type>::leftLength() const
{
return leftcnt;
}
template<typename Type>
int LList<Type>::rightLength() const
{
return rightcnt;
}
template<typename Type>
bool LList<Type>::getValue( Type& it ) const
{
if( rightcnt== 0 ) return false;
it= fence->next->element;
return true;
}
template<typename Type>
bool LList<Type>::insert( const Type& item )
{
fence->next= new CLink<Type>( item, fence->next );
if( tail== fence ) tail= fence->next;
rightcnt++;
return true;
}
template<typename Type>
bool LList<Type>::append( Type const& Item )
{
tail= tail->next= new CLink<Type>( Item, NULL );
rightcnt++;
return true;
}
template<typename Type>
bool LList<Type>::remove( Type& it )
{
if( fence->next== NULL ) return false;
it= fence->next->element;
CLink<Type>* ltemp= fence->next;
fence->next= ltemp->next;
if( tail== ltemp ) tail= fence;
delete ltemp;
rightcnt--;
return true;
}
template<typename Type>
void LList<Type>::pre()
{
CLink<Type>* temp= head;
if( fence== head ) return;
while( temp->next!= fence ) temp= temp->next;
fence= temp;
leftcnt--, rightcnt++;
}
template<typename Type>
bool LList<Type>::setPos( int pos )
{
if( pos< 0 || pos> rightcnt+ leftcnt ) return false;
fence= head;
for( int i= 0; i< pos; ++i ) fence= fence->next;
return true;
}
template<typename Type>
bool LList<Type>::setvalue( int pos, Type Item )
{
if( pos< 0 || pos> rightcnt+ leftcnt ) return false;
fence= head;
for( int i= 0; i< pos; ++i ) fence= fence->next;
fence->element= Item;
}
template<typename Type>
bool LList<Type>::setvalue( Type Item )
{
if( fence= head ) return false;
fence->element= Item;
return true;
}
template<typename Type>
int LList<Type>::length() const
{
return rightcnt+ leftcnt;
}
template<typename Type>
bool LList<Type>::empty() const
{
return rightcnt+ leftcnt== 0;
}
template<typename Type>
bool LList<Type>::find( Type const& Item )
{
CLink<Type>* temp;
for( temp= head; temp; temp= temp->next )
if( temp->element== Item ) return true;
return false;
}
template<typename Type>
void LList<Type>::print() const
{
CLink<Type>* temp= head;
cout << "< ";
while( temp!= fence )
{
cout << temp->next->element << " ";
temp= temp->next;
}
cout << "| ";
while( temp->next!= NULL )
{
cout << temp->next->element << ' ';
temp= temp->next;
}
cout << "> " << endl;
}
#endif
posted on 2009-03-15 10:47
Darren 阅读(891)
评论(2) 编辑 收藏 引用