_1.1b07010424.txt

① 设计和实现基于哈夫曼算法的编码和译码功能

#include<iostream.h>
template<class T>
class LinearList
{
	public:
		virtual bool IsEmpty() const=0;
        virtual int Search(T x) const=0;
		virtual bool Delete(int i)=0;
		virtual void Output(ostream& out) const=0;
	protected:
		int n;
};
template<class T>
class SeqList:public LinearList<T>
{
	public:
		SeqList(int mSize);
		~SeqList(){delete[]elements;}
		bool IsEmpty() const;
		int Length() const;
		int Search(T x) const;
		bool Insert(int i,T x);
        void Reverse() const;
		bool Delete(int i);
        bool Delete2(const T&x);
		void Output(ostream& out) const;
	private:
		int maxLength;
		T *elements;
};
template<class T>
SeqList<T>::SeqList(int mSize)
{
	maxLength=mSize;
	elements=new T[maxLength];
	n=0;
}
template<class T>
bool SeqList<T>::IsEmpty() const
{
	return n==0;
}
template<class T>
int SeqList<T>::Length() const
{
	return n;
}
template<class T>
int SeqList<T>::Search(T x) const
{
	for(int j=0;j<n;j++)
		if(elements[j]==x) return j;
		return -1;
}
template<class T>
bool SeqList<T>::Insert(int i,T x)
{
	if(i<-1||i>n-1){
		cout<<"Out Of Bounds"<<endl;return false;
	}
	if(n==maxLength){
		cout<<"OverFlow"<<endl;return false;
	}
	for(int j=n-1;j>i;j--) elements[j+1]=elements[j];
	elements[i+1]=x;
	n++;return true;
}
	
template<class T>
void SeqList<T>::Reverse() const
{
	for(int i=0;i<=n/2-1;i++)
	{
		T t=elements[i];
		elements[i]=elements[maxLength-i-1];
		elements[maxLength-i-1]=t;
	}
}
template<class T>
bool SeqList<T>::Delete(int i)
{
	if(!n){
		cout<<"UnderFlow"<<endl;return false;
	}
	if(i<0||i>n-1){
		cout<<"Out Of Bounds"<<endl;return false;
	}
	for(int j=j+1;j<n;j++) elements[j-1]=elements[j];
	n--;return true;
}
template<class T>
bool SeqList<T>::Delete2(const T &x)
{
	int i=Search(x);
	Delete(i);
	return true;
}
template<class T>
void SeqList<T>::Output(ostream& out)const
{
	for(int i=0;i<n;i++) out<<elements[i]<<' ';
	out<<endl;
}
void main()
{
	SeqList<int> LA(10);
	for(int i=0;i<7;i++) LA.Insert(i-1,2*i);
	LA.Insert(5,9);
	LA.Insert(3,5);
	LA.Output(cout);
    LA.Reverse();
    cout<<"逆置输出：";
    LA.Output(cout);
    LA.Delete2(2);
    cout<<"删除输出：";
    LA.Output(cout);
}