array.h

这是清华大学出版社的《数据结构》的电子文档讲义

//含向量类
#include<iostream.h>
#include<assert.h>
#include<stdlib.h>
const unsigned DefaultSize=30;

template<class Type>class array{
    			//数组是数据类型相同的n (size)个元素的一个收集，下标范围从0到n-1。
    			//对数组中元素可按下标所指示位置直接访问。
	public:
		array (unsigned Size=DefaultSize);				//构造函数
		array (const array<Type>& x);						//复制构造函数
		~array() {delete [] elements; }						//析构函数
		array<Type>& operator=(const array<Type>& A);		//数组赋值复制
		Type & operator [] (unsigned i)const;				//下标
		Type * operator *() const {return elements;}		//指针转换，返回指向数组指针
		unsigned length() const{return arraySize;}			//取数组长度
		void reSize(unsigned sz);							//修改数组长度
	private:
		Type * elements;									//指向数组的指针
		unsigned arraySize;                                 //元素个数
		void getArray();									//动态分配数组存储空间
    };

template<class Type>void array<Type>::getArray(){	//动态分配一个数组的空间，私有函数
	elements=new Type[arraySize];                        				//创建数组
	if(elements==0) {cerr<<"Memory Allocation Error"<<endl; arraySize=0; return;}
	}

template<class Type>array<Type>::array(unsigned sz){		//构造函数，建立最大长度为sz的数组
	if (sz<=0){cerr<<"Ivalid array Size"<<endl; arraySize=0; return;}	//参数检查
	arraySize=sz;														//数组长度
	//elements=new Type[arraySize];                        				//创建数组
	getArray();														//创建数组
	}

template<class Type>array<Type>::array(const array<Type>&x){  		//从x复制构造当前数组
	unsigned n=x.arraySize; 
	unsigned arraySize=n;    											//目的数组的长度
	elements=new Type[n];											//为目的数组分配空间
	if(elements==0)												//长度为0，直接返回
	{ cerr<<"Memory Allocation Error"<<endl;  arraySize=0;  return; }
	Type * srcptr=x.elements;                           			//源数组首地址
	Type * destptr=elements;										//目的数组首地址
	while(n--) * destptr++=* srcptr++;							//传送
	}

template<class Type>Type& array<Type>::operator[] (unsigned i)const{	//下标访问
	if (i<0 || i>arraySize-1)										//检查下标的取值范围
		{ cerr<<"Index out of Range"<<endl; exit(1);}				//下标越界，直接返回
	return elements[i];                        						//返回下标为i的数组元素
	}

template<class Type>void array<Type>::reSize(unsigned sz){ 				//修改数组大小
	if (sz<=0)  cerr<<"Invalid array Size"<<endl;           		//检查参数的合理性
	if (sz !=arraySize){								
  		Type * newarray=new Type[ sz]; 							//建立新数组
		if(newarray==0)
			{cerr<<"Memory Allocation Error"<<endl; return; }
		unsigned n=(sz<=arraySize)?sz:arraySize;					//向新数组传送数据个数
		Type * srcptr=elements;									//源数组首地址
		Type * destptr=newarray;                    				//目的数组首地址
		while (n--) * destptr++=* srcptr ++;						//逐个复制数组元素
		delete[] elements;											//释放老数组空间
		elements=newarray;  arraySize=sz;						//elements指向新数组
		}
	}

template<class Type > class matrix {
	public:
		matrix(unsigned nRows,unsigned nCols);
		matrix(unsigned nRows,unsigned nCols, Type initV);
		// ~matrix();
		array<Type>& operator[](unsigned index)const;
		void operator=(const matrix<Type>&);
		unsigned numberOfRows()const;
		unsigned numberOfColums()const;
	protected:
		array<array<Type> *> rows;
	};

template<class Type>matrix<Type>::matrix(unsigned nRows,unsigned nCols)
        :rows(nRows){
	for (unsigned i=0;i<nRows;i++) {  
		rows[i]=new array<Type>(nCols);
		assert(rows[i]!=0);
		}
	}
template<class Type>matrix<Type>
	::matrix(unsigned nRows,unsigned nCols, Type initV):rows(nRows){
	for (unsigned i=0;i<nRows;i++){  
		rows[i]=new array<Type>(numOfcolums,initV);
		assert(rows[i]!=0);} 
	}
/*template<class Type>matrix<Type>::~matrix(){
	unsigned max=rows.length(),i;
	array<Type> *p;
	for(i=0;i<max;i++){
		p=rows[i]; 
		rows[i]=0; 
		delete []p;}
	}*/
template<class Type> unsigned matrix<Type>::numberOfRows()const{
	return rows.length();  }

template<class Type> unsigned matrix<Type>::numberOfColums()const{
	return rows[0]->length();  }

template<class Type> array<Type>& matrix<Type>::operator[](unsigned index)const{
	return *rows[index];  }

template<class Type> void matrix<Type>::operator=(const matrix<Type>& mr){
	unsigned i,j; 
	assert(rows.length()==mr.rows.length());
	assert(rows[0]->length()==(mr.rows)[0]->length());
	for (i=0;i<rows.length();i++)
		for (j=0;j<rows[0]->length();j++)
			(*rows[i])[j]=(*mr.rows[i])[j]; 
	}

#include<string.h>
const int maxLen=128;  									//字符串的最大长度

class string{   										//对象：零个或有限多个字符的向量。
	friend	void replace(string& s,string& p,string& r);
	public: 
		string ();										//无参构造函数，构造最大长度maxLen，现长0的空串
		string (const char* init);						//有参构造函数，按init指向的字面串构造对象串
		string (const string & ob); 					//复制构造函数，按已有字符串对象ob构造一个新字符串
		~string (){delete[] ch;}						//析构函数，释放动态分配的串空间 
		int length() const { return curLen;}			//函数返回串* this的长度 
		string& operator() (int pos, int len);			//当0<=pos<=maxLen且0<=len且pos+len< maxLen
														//从pos所指位置开始连续取len个字符组成子串返回。
		int operator==(const string & ob)const {
			return strcmp(ch, ob.ch)==0;}				//判是否串相等。
		int operator !=(const string & ob)const {
			return strcmp(ch, ob.ch) !=0;}				//判是否串不等。
		int operator !() const {
			return curLen==0;} 							//判是否串空。
		string & operator=(const string& ob);  			//串ob赋值给当前串*this 
		string & operator+=(const string& ob);  
				//若length (* this)+ length (ob)<=maxLen，则把串ob接在串*this后面。
		char& operator[](int i);  						//下标运算，取* this的第i个字符。
		int kmpFind(string& pat, int[])const;			//KMP匹配算法
		void calcf1(int[]);						//求前缀(失效)数组
	private: 
		int curLen;  									//串的现有长度
		char* ch;										//存放串的字符数组
	};

string::string() {										//串无参构造函数 
	ch=new char[maxLen+1];   							//建数组，+1放结束标记'\0' 
	if(! ch){cerr<<"Allocation Error\n";  exit(1);} 	//分配空间失败，退出。
	curLen=0;											//初始串长度为0
	ch[0]='\0';											//加串尾标志    
	}    

string::string (const char * init) {					//串有参构造函数 
	ch=new char[maxLen+1];								//创建字符数组 
	if(! ch){cerr<<"Allocation Error\n";  exit(1);} 
	curLen=strlen (init);								//串长度为字面串的长度 
	strcpy(ch, init);									//调用系统串复制函数复制
	}   

string::string (const string &ob){						//串复制构造函数
	ch=new char[maxLen+1];								//创建对象字符数组 
	if(! ch){cerr<<"Allocation Error\n";  exit(1);} 
	curLen=ob.curLen ;									//串长度取源字符串长度
	strcpy (ch,ob.ch);									//调用系统串复制函数复制
	}

string& string::operator() (int pos,int len){			//求子串 
	string * temp=new string ;							//temp指向无名临时串对象 
	if (pos<0 || pos+len-1>=maxLen || len<0){			//参数不合理，不取子串
		//temp->curLen=0;   temp->ch[0]='\0'; 			//临时串对象本来就是空串
		}
	else {
		if (pos+len-1 >= curLen) len=curLen-pos ;  		//源串字符数不够，只取一部分 
		temp->curLen=len; 											//子串长
		for (int i=0,j=pos; i<len; i++,j++) temp->ch[i]=ch[j];		//子串字符拷贝
		temp->ch[len]='\0'; 										//子串结束标志
		}
	return * temp;										//返回temp指向的临时串作为子串
	}

string& string::operator=(const string &ob){				//重载，参数串向对像串赋值
	if (&ob !=this){										//若两串地址不同，才赋值
		//delete []ch ;										//删去释放当前串原有空间
		//ch=new char [maxLen+1];  							//重新分配，加一个字符放'\ 0'
		//if (! ch){cerr<<"Out Of Memory!\n";  exit(l);}	// ch为空，分配失败  
		curLen=ob.curLen;          
		strcpy (ch, ob.ch);									//复制
		}
	else cout<<"Attempted assignment of a string to itself!\n"; 	//若两串地址相同，为自我赋值
	return * this;
	}

string&  string::operator +=(const string &ob){				//串重载操作：串连接 
	//char * temp=ch ;										//保存将要覆盖字符串的地址
	int newLen=curLen+ob.curLen ;
	if(newLen<=maxLen) {									//若总长度不超过最大长度
		curLen=newLen;										//结果串长度
		//curLen+=ob.curlen ;								//结果串的长度
		//ch=new char [maxLen+1];								//为结果串分配存储
		//if(! ch){cerr<<"Out Of Memory!\n";exit(1);}
	//strcpy (ch,temp);										//结果串的前一部分
	strcat (ch,ob.ch);}						//调用系统串函数连接结果串的后一部分
	//delete []temp;											//释放旧存储
	return *this;											//返回结果串
	}

char& string::operator[] (int i){							//取*this的第i个字符
	if(i<0 /*&&*/ || i>=curLen) {cout<<"Out Of Boundary!\n";exit(1);}
	return ch[i];
	}

int string::kmpFind(string& pat, int f1[]) const{
	int posP=0,  posT=0;								//两个串的扫描指针
	int lengthP=pat.curLen, lengthT=curLen; 			//模式与目标串的长度
	while (posP<lengthP && posT<lengthT){	 			//对两串扫描
		if (pat.ch[posP]==ch[posT]){					//对应字符匹配
			posP++; posT++; }
		else if(posP==0) posT++;
			 else posP=f1[posP-1];						//pat.f1[posP-1];
	}
	if (posP<lengthP) return -1;							//匹配失败
	else return posT-lengthP;							//匹配成功
	}

void string::calcf1(int f1[]){								//对模式p(*this)，计算失效函数
	int lengthP=curLen; 
	f1[0]=-1; 
	for (int j=1; j<lengthP; j++){						//计算f[j] 
		int i=f1[j-1];    
		while(*(ch+j) != *(ch+i+1) && i>=0) i=f1[i];	//递推计算f[j]
		if(*(ch+j)== *(ch+i+1))f1[j]=i+1; 
		else f1[j]=-1; 
		}
	for (j=0; j<lengthP; j++){							//计算f1[j] 
		f1[j]++;
		}
	}

ostream& operator<<(ostream& out, string s){
	for(int i=0; i<s.length(); i++)	cout<<s[i];
	cout<<endl;
	return out;
	}