描述3.txt

9、优先级队列 QueueNode.h Compare.h PriorityQueue.h Test.cpp 10、串 88 MyString.h MyString.cpp

9、优先级队列	
QueueNode.h	
Compare.h	
PriorityQueue.h	
Test.cpp	
10、串	88
MyString.h	
MyString.cpp	
test.cpp	
11、二叉树	
BinTreeNode.h	
BinaryTree.h	
Test.cpp	
12、线索二叉树	
ThreadNode.h	
ThreadTree.h	
ThreadInorderIterator.h	
test.cpp	



9、优先级队列

QueueNode.h

template<typename Type,typename Cmp> class PriorityQueue;

template<typename Type,typename Cmp> class QueueNode{
private:
	friend class PriorityQueue<Type,Cmp>;
	QueueNode(const Type item,QueueNode<Type,Cmp> *next=NULL)
		:m_data(item),m_pnext(next){}
private:
	Type m_data;
	QueueNode<Type,Cmp> *m_pnext;
};

Compare.h

template<typename Type> class Compare{	//处理一般比较大小
public:
	static bool lt(Type item1,Type item2);
};

template<typename Type> bool Compare<Type>::lt(Type item1, Type item2){
	return item1<item2;
}

struct SpecialData{
	friend ostream& operator<<(ostream& ,SpecialData &);
	int m_ntenor;
	int m_npir;
};

ostream& operator<<(ostream& os,SpecialData &out){
	os<<out.m_ntenor<<"   "<<out.m_npir;
	return os;
}

class SpecialCmp{		//处理特殊比较大小,用户可添加适当的类
public:
	static bool lt(SpecialData item1,SpecialData item2);
};

bool SpecialCmp::lt(SpecialData item1, SpecialData item2){
	return item1.m_npir<item2.m_npir;
}

PriorityQueue.h

#include "QueueNode.h"
#include "Compare.h"

template<typename Type,typename Cmp> class PriorityQueue{	//Cmp is Designed for compare
public:
	PriorityQueue():m_prear(NULL),m_pfront(NULL){}
	~PriorityQueue(){
		MakeEmpty();
	}

	void MakeEmpty();               //make the queue empty
	void Append(const Type item);   //insert data
	Type Delete();                  //delete data
	Type GetFront();                //get data
    void Print();                   //print the queue
        
	bool IsEmpty() const{           
		return m_pfront==NULL;
	}
	

private:
	QueueNode<Type,Cmp> *m_prear,*m_pfront;
};

template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::MakeEmpty(){
	QueueNode<Type,Cmp> *pdel;
	while(m_pfront){
		pdel=m_pfront;
		m_pfront=m_pfront->m_pnext;
		delete pdel;
	}
}

template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::Append(const Type item){
	if(m_pfront==NULL){
		m_pfront=m_prear=new QueueNode<Type,Cmp>(item);
	}
	else{
		m_prear=m_prear->m_pnext=new QueueNode<Type,Cmp>(item);
	}
}

template<typename Type,typename Cmp> Type PriorityQueue<Type,Cmp>::Delete(){
	if(IsEmpty()){
		cout<<"There is no elements!"<<endl;
		exit(1);
	}
	QueueNode<Type,Cmp> *pdel=m_pfront,*pmove=m_pfront;
	while(pmove->m_pnext){  //get the minimize priority's data

        //cmp:: lt is used for compare the two data, if the front one 
        //      is less than the back, then return 1
		if(Cmp::lt(pmove->m_pnext->m_data,pdel->m_pnext->m_data)){
			pdel=pmove;
		}
		pmove=pmove->m_pnext;
	}

	pmove=pdel;
	pdel=pdel->m_pnext;
	pmove->m_pnext=pdel->m_pnext;
	Type temp=pdel->m_data;
	delete pdel;
	return temp;
}

template<typename Type,typename Cmp> Type PriorityQueue<Type,Cmp>::GetFront(){
	if(IsEmpty()){
		cout<<"There is no elements!"<<endl;
		exit(1);
	}
	QueueNode<Type,Cmp> *pdel=m_pfront,*pmove=m_pfront->m_pnext;
	while(pmove){   //get the minimize priority's data
		if(Cmp::lt(pmove->m_data,pdel->m_data)){
			pdel=pmove;
		}
		pmove=pmove->m_pnext;
	}
	return pdel->m_data;
}

template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::Print(){
	QueueNode<Type,Cmp> *pmove=m_pfront;
	cout<<"front";

	while(pmove){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}

	cout<<"--->rear"<<endl<<endl<<endl;
}

Test.cpp

#include <iostream>
#include <cstdlib>
using namespace std;

#include "PriorityQueue.h"

int main(){
	PriorityQueue<int,Compare<int> > queue;
	int init[10]={1,9,3,5,0,8,2,4,6,7};
	for(int i=0;i<10;i++){
		queue.Append(init[i]);
	}
	queue.Print();

	queue.Delete();

	queue.Print();

	system("pause");
	system("cls");
	
	PriorityQueue<SpecialData,SpecialCmp> spe_queue;
	int init2[5][2]={{34,2},{64,1},{18,3},{24,2},{55,4}};
	SpecialData data[5];
	for(int i=0;i<5;i++){
		data[i].m_npir=init2[i][1];
		data[i].m_ntenor=init2[i][0];
	}
	for(int i=0;i<5;i++){
		spe_queue.Append(data[i]);
	}
	spe_queue.Print();

    cout<<spe_queue.GetFront()<<endl<<endl;
	spe_queue.Delete();
	spe_queue.Print();
	
	
	return 0;
}
10、串

MyString.h

const int MAXSIZE=100;

class CMyString
{
public:
	CMyString(const CMyString& copy);
	CMyString(const char *init);
	CMyString();
	~CMyString(){
		delete[] m_pstr;
	}
	int Length() const{
		return m_ncurlen;
	}
	int Find(CMyString part) const;
	char* GetBuffer() const;

public:
	CMyString& operator()(int pos,int len);
	bool operator==(const CMyString cmp_str) const;
	bool operator!=(const CMyString cmp_str) const;
	bool operator<(const CMyString cmp_str) const;
	bool operator>(const CMyString cmp_str) const;
	bool operator!() const{
		return m_ncurlen==0;
	}
	CMyString& operator=(const CMyString &copy);
	CMyString& operator+=(const CMyString &add);
	char& operator[](int i);
	friend ostream& operator<<(ostream& ,CMyString&);
	friend istream& operator>>(istream& ,CMyString&);
private:
	void Next();

private:
	int m_ncurlen;
	char *m_pstr;
	int *m_pnext;
};

MyString.cpp

#include <iostream>
#include <cstring>

using namespace std;

#include "MyString.h"



CMyString::CMyString(){			//create empty string
	m_pstr=new char[MAXSIZE+1];
	if(!m_pstr){
		cerr<<"Allocation Error"<<endl;
		exit(1);
	}
	this->m_ncurlen=0;
	m_pstr[0]='\0';
}

CMyString::CMyString(const char *init){		//initialize the string with char*
	m_pstr=new char[MAXSIZE+1];
	if(!m_pstr){
		cerr<<"Allocation Error"<<endl;
		exit(1);
	}
	this->m_ncurlen=strlen(init);
	strcpy(m_pstr,init);
}

CMyString::CMyString(const CMyString &copy){	//initialize the string with string
	m_pstr=new char[MAXSIZE+1];
	if(!m_pstr){
		cerr<<"Allocation Error"<<endl;
		exit(1);
	}
	this->m_ncurlen=copy.m_ncurlen;
	strcpy(m_pstr,copy.m_pstr);
}

int CMyString::Find(CMyString part) const{		//string match :KMP
	int posP=0,posT=0;
	int lengthP=part.m_ncurlen,lengthT=this->m_ncurlen;

	part.Next();
	while(posP<lengthP&&posT<lengthT){
		if(part.m_pstr[posP]==this->m_pstr[posT]){
			posP++;
			posT++;
		}
		else{
			if(posP==0){
				posT++;
			}
			else{
				posP=part.m_pnext[posP-1];
			}
		}
	}
	delete[] part.m_pnext;
	if(posP<lengthP){
		return 0;
	}
	else{
		return 1;
	}
}

void CMyString::Next(){			//get the next char for matching : KMP
	int length=this->m_ncurlen;
	this->m_pnext=new int[length];
	this->m_pnext[0]=0;
	for(int i=1;i<length;i++){
		int j=this->m_pnext[i-1];
		while(*(this->m_pstr+i)!=*(this->m_pstr+j)&&j>0){
			j=this->m_pnext[j-1];
		}
		if(*(this->m_pstr+i)==*(this->m_pstr+j)){
			this->m_pnext[i]=j+1;
		}
		else{
			this->m_pnext[i]=0;
		}
	}
//	for(int i=0;i<length;i++)
//		cout<<i<<":\t"<<m_pnext[i]<<endl;
}

char *CMyString::GetBuffer() const{		//get the char* from string
	return this->m_pstr;
}

CMyString& CMyString::operator()(int pos, int len){		//get len char with the begining of pos
	CMyString *temp=new CMyString;
	if(pos<0||pos+len-1>MAXSIZE||len<0){
		temp->m_ncurlen=0;
		temp->m_pstr[0]='\0';
	}
	else{
		if(pos+len-1>=m_ncurlen){
			len=m_ncurlen-pos;
		}
		temp->m_ncurlen=len;
		for(int i=0,j=pos;i<len;i++,j++){
			temp->m_pstr[i]=m_pstr[j];
		}
		temp->m_pstr[len]='\0';
	}
	return *temp;
}

bool CMyString::operator==(const CMyString cmp_str) const{
	if(this->m_ncurlen!=cmp_str.m_ncurlen){
		return 0;
	}
	for(int i=0;i<this->m_ncurlen;i++){
		if(this->m_pstr[i]!=cmp_str.m_pstr[i])
			return 0;
	}
	return 1;
}
bool CMyString::operator!=(const CMyString cmp_str) const{
	if(*this==cmp_str)
		return 0;
	return 1;
}
bool CMyString::operator<(const CMyString cmp_str) const{
	if(this->m_ncurlen!=cmp_str.m_ncurlen){
		return this->m_ncurlen<cmp_str.m_ncurlen;
	}
	for(int i=0;i<this->m_ncurlen;i++){
		if(this->m_pstr[i]!=cmp_str.m_pstr[i]){
			return this->m_pnext[i]<cmp_str.m_pnext[i];
		}
	}
	return 0;
}
bool CMyString::operator>(const CMyString cmp_str) const{
	if(*this<cmp_str||*this==cmp_str){
		return 0;
	}
	return 1;
}
CMyString& CMyString::operator=(const CMyString &copy){		//赋值操作
	delete[] this->m_pstr;
	this->m_pstr=new char[copy.m_ncurlen+1];
	strcpy
		(this->m_pstr,copy.m_pstr);
	return *this;
}
CMyString& CMyString::operator+=(const CMyString &add){		//字符串追加
	int length=this->m_ncurlen+add.m_ncurlen;
	int n=this->m_ncurlen;
	CMyString temp(*this);
	delete[] this->m_pstr;
	this->m_pstr=new char[length+1];
	for(int i=0;i<n;i++){
		this->m_pstr[i]=temp[i];
	}
	for(int i=n;i<length;i++){
		this->m_pstr[i]=add.m_pstr[i-n];
	}
	this->m_pstr[length]='\0';
	return *this;
}
char& CMyString::operator[](int i){		//取元素
	if(i<0||i>=this->m_ncurlen){
		cout<<"out of boundary!"<<endl;
		exit(1);
	}
	return this->m_pstr[i];
}

ostream& operator<<(ostream& os,CMyString& str){
	os<<str.m_pstr;
	return os;
}

istream& operator>>(istream& is,CMyString& str){
	is>>str.m_pstr;
	return is;
}

test.cpp

#include <iostream>

using namespace std;

#include "MyString.h"

int main(){
	CMyString test1("babc");
	CMyString test2("abababcdefb");
	cout<<test2.Find(test1)<<endl;
	cout<<test2(2,3)<<endl;

	if(test1<test2){
		cout<<test1<<"<"<<test2<<endl;
	}
	else{
		if(test1==test2){
			cout<<test1<<"=="<<test2<<endl;
		}
		else{
			if(test1>test2){
				cout<<test1<<">"<<test2<<endl;
			}
		}
	}

	int length=test2.Length();
	for(int i=0;i<length;i++){
		cout<<test2[i];
	}
	cout<<endl;

	test1+=test2;
	cout<<test1<<endl;

	test1=test2;
	cout<<test1<<endl;

	return 0;
}
11、二叉树

BinTreeNode.h

template<typename Type> class BinaryTree;

template<typename Type> class BinTreeNode{
public:
	friend class BinaryTree<Type>;
	BinTreeNode():m_pleft(NULL),m_pright(NULL){}
	BinTreeNode(Type item,BinTreeNode<Type> *left=NULL,BinTreeNode<Type> *right=NULL)
		:m_data(item),m_pleft(left),m_pright(right){}

	Type GetData() const;		//get thd data
	BinTreeNode<Type> *GetLeft() const;		//get the left node
	BinTreeNode<Type> *GetRight() const;	//get the right node

	void SetData(const Type data);			//change the data
	void SetLeft(const BinTreeNode<Type> *left);	//change thd left node
	void SetRight(const BinTreeNode<Type> *right);	//change the right node

	void InOrder();		//inorder the tree with the root of the node
	void PreOrder();	//perorder the tree with the root of the node
	void PostOrder();	//postoder the tree with the root of the node
	
	int Size();			//get size
	int Height();		//get height
	BinTreeNode<Type> *Copy(const BinTreeNode<Type> *copy);	//copy the node
	void Destroy(){		//destroy the tree with the root of the node
		if(this!=NULL){
			this->m_pleft->Destroy();
			this->m_pright->Destroy();
			delete this;
		}
	}

	friend bool equal<Type>(const BinTreeNode<Type> *s,const BinTreeNode<Type> *t);	//is equal?

private:
	BinTreeNode<Type> *m_pleft,*m_pright;
	Type m_data;
};

template<typename Type> Type BinTreeNode<Type>::GetData() const{
	return this!=NULL?m_data:-1;
}

template<typename Type> BinTreeNode<Type>* BinTreeNode<Type>::GetLeft() const{
	return this!=NULL?m_pleft:NULL;
}

template<typename Type> BinTreeNode<Type>* BinTreeNode<Type>::GetRight() const{
	return this!=NULL?m_pright:NULL;
}

template<typename Type> void BinTreeNode<Type>::SetData(const Type data){
	if(this!=NULL){
		m_data=data;
	}
}

template<typename Type> void BinTreeNode<Type>::SetLeft(const BinTreeNode<Type> *left){
	if(this!=NULL){
		m_pleft=left;
	}
}