?? 描述3.txt
字號:
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 ©);
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 ©){ //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 ©){ //賦值操作
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;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -