描述4.txt

13、堆 MinHeap.h test.cpp 14、哈夫曼树 BinTreeNode.h BinaryTree.h MinHeap.h Huffman.h Test.

13、堆	
MinHeap.h	
test.cpp	
14、哈夫曼树	
BinTreeNode.h	
BinaryTree.h	
MinHeap.h	
Huffman.h	
Test.cpp	
15、树	164
QueueNode.h	
LinkQueue.h	
TreeNode.h	
Tree.h	170
test.cpp	
16、B+树	
BTreeNode.h	
BTree.h	192
test.cpp	
17、图	217
MinHeap.h	
Edge.h	222
Vertex.h	
Graph.h	224
test.cpp	
18、排序	
Data.h	249
QueueNode.h	
LinkQueue.h	
Sort.h	263
test.cpp




13、堆

MinHeap.h

template<typename Type> class MinHeap{
public:
	MinHeap(int size):m_nMaxSize(size > defaultsize ? size : defaultsize)
			,m_pheap(new Type[m_nMaxSize]),m_ncurrentsize(0){}
	MinHeap(Type heap[],int n);		//initialize heap by a array
	~MinHeap(){
		delete[] m_pheap;
	}

public:
	bool Insert(const Type item);	//insert element
	bool Delete(const Type item);	//delete element
	bool IsEmpty() const{			
		return m_ncurrentsize == 0;
	}
	bool IsFull() const{
		reutrn m_ncurrentsize == m_nMaxSize;
	}
	void Print(const int start=0, int n=0);			

private:
    //adjust the elements of the child tree with the root of start from top to bottom
	void Adjust(const int start, const int end);	

private:
	static const int defaultsize = 100;
	const int m_nMaxSize;	
	Type *m_pheap;
	int m_ncurrentsize;
};

template<typename Type> void MinHeap<Type>::Adjust(const int start, const int end){
	int i = start,j = i*2+1;    //get the position of the child of i
	Type temp=m_pheap[i];
	while(j <= end){    
		if(j<end && m_pheap[j]>m_pheap[j+1]){   //left>right
			j++;
		}
		if(temp <= m_pheap[j]){ //adjust over
			break;
		}
		else{   //change the parent and the child, then adjust the child
			m_pheap[i] = m_pheap[j];
			i = j;
			j = 2*i+1;
		}
	}
	m_pheap[i] = temp;
}

template<typename Type> MinHeap<Type>::MinHeap(Type heap[], int n):m_nMaxSize(
		n > defaultsize ? n : defaultsize){
	m_pheap = new Type[m_nMaxSize];
	for(int i=0; i<n; i++){
		m_pheap[i] = heap[i];
	}
	m_ncurrentsize = n;
	int pos=(n-2)/2;	//Find the last child tree which has more than one element;
	while(pos>=0){
		Adjust(pos, n-1);
		pos--;
	}
}

template<typename Type> bool MinHeap<Type>::Insert(const Type item){
	if(m_ncurrentsize == m_nMaxSize){
		cerr<<"Heap Full!"<<endl;
		return 0;
	}
	m_pheap[m_ncurrentsize] = item;
	int j = m_ncurrentsize, i = (j-1)/2;    //get the position of the parent of j
	Type temp = m_pheap[j];
	while(j > 0){   //adjust from bottom to top
		if(m_pheap[i] <= temp){
			break;
		}
		else{
			m_pheap[j] = m_pheap[i];
			j = i;
			i = (j-1)/2;
		}
	}
	m_pheap[j] = temp;
	m_ncurrentsize++;
	return 1;
}

template<typename Type> bool MinHeap<Type>::Delete(const Type item){
	if(0 == m_ncurrentsize){
		cerr<<"Heap Empty!"<<endl;
		return 0;
	}
	for(int i=0; i<m_ncurrentsize; i++){
		if(m_pheap[i] == item){
			m_pheap[i] = m_pheap[m_ncurrentsize-1]; //filled with the last element
			Adjust(i,m_ncurrentsize-2);     //adjust the tree with start of i
			m_ncurrentsize--;
			i=0;
		}
	}
	return 1;
}

template<typename Type> void MinHeap<Type>::Print(const int start, int n){
	if(start >= m_ncurrentsize){
		return;
	}
	Print(start*2+2, n+1);  //print the right child tree

	for(int i=0; i<n; i++){
		cout<<"    ";
	}
	cout<< m_pheap[start] << "--->" << endl;

	Print(start*2+1, n+1);  //print the left child tree
}

test.cpp

#include <iostream>

using namespace std;

#include "MinHeap.h"

int main(){
	int init[30]={17,6,22,29,14,0,21,13,27,18,2,28,8
			,26,3,12,20,4,9,23,15,1,11,5,19,24,16,7,10,25};
	MinHeap<int> heap(init,30);
	heap.Print();
	cout<<endl<<endl<<endl;

	heap.Insert(20);
	heap.Print();
	cout<<endl<<endl<<endl;
	
	heap.Delete(20);
	heap.Print();
	cout<<endl<<endl<<endl;
	return 0;
}
14、哈夫曼树

BinTreeNode.h

template<typename Type> class BinaryTree;

template<typename Type> void Huffman(Type *, int, BinaryTree<Type> &);

template<typename Type> class BinTreeNode{
public:
	friend class BinaryTree<Type>;
    friend void Huffman<Type>(Type *, int, 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){}
	void Destroy(){		//destroy the tree with the root of the node
		if(this!=NULL){
			this->m_pleft->Destroy();
			this->m_pright->Destroy();
			delete this;
		}
	}
    Type GetData(){
        return m_data;
    }
    BinTreeNode<Type> *Copy(const BinTreeNode<Type> *copy);	//copy the node

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

template<typename Type> BinTreeNode<Type>* BinTreeNode<Type>::Copy(const BinTreeNode<Type> *copy){
	if(copy==NULL){
		return NULL;
	}

	BinTreeNode<Type> *temp=new BinTreeNode<Type>(copy->m_data);
	temp->m_pleft=Copy(copy->m_pleft);
	temp->m_pright=Copy(copy->m_pright);
	return temp;
}

BinaryTree.h

#include "BinTreeNode.h"

template<typename Type> void Huffman(Type *, int, BinaryTree<Type> &);

template<typename Type> class BinaryTree{
public:
    
    BinaryTree(BinaryTree<Type> &bt1, BinaryTree<Type> &bt2){
        m_proot = new BinTreeNode<Type>(bt1.m_proot->m_data 
            + bt2.m_proot->m_data, bt1.m_proot, bt2.m_proot);
    }
    BinaryTree(Type item){
        m_proot = new BinTreeNode<Type>(item);
    }
    BinaryTree(const BinaryTree<Type> &copy){
        this->m_proot = copy.m_proot;
    }
    BinaryTree(){
        m_proot = NULL;
    }
    void Destroy(){
        m_proot->Destroy();
    }
    ~BinaryTree(){
//        m_proot->Destroy();
    }
    
    BinaryTree<Type>& operator=(BinaryTree<Type> copy);	//evaluate node
    friend void Huffman<Type>(Type *, int, BinaryTree<Type> &);
    friend bool operator < <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
    friend bool operator > <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
    friend bool operator <= <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
    friend ostream& operator<< <Type>(ostream& ,BinaryTree<Type>&);	//output the data
private:
	BinTreeNode<Type> *m_proot;
    void Print(BinTreeNode<Type> *start,int n=0);	//print the tree with the root of start
};

template<typename Type> bool operator <(BinaryTree<Type> &l, BinaryTree<Type> &r){
    return l.m_proot->GetData() < r.m_proot->GetData();
}

template<typename Type> bool operator >(BinaryTree<Type> &l, BinaryTree<Type> &r){
    return l.m_proot->GetData() > r.m_proot->GetData();
}

template<typename Type> bool operator <=(BinaryTree<Type> &l, BinaryTree<Type> &r){
    return l.m_proot->GetData() <= r.m_proot->GetData();
}


template<typename Type> void BinaryTree<Type>::Print(BinTreeNode<Type> *start, int n){
	if(start==NULL){
		for(int i=0;i<n;i++){
			cout<<"     ";
		}
		cout<<"NULL"<<endl;
		return;
	}
	Print(start->m_pright,n+1);	//print the right subtree
	for(int i=0;i<n;i++){	//print blanks with the height of the node
		cout<<"     ";
	}
	if(n>=0){
		cout<<start->m_data<<"--->"<<endl;//print the node
	}
	Print(start->m_pleft,n+1);	//print the left subtree
}

template<typename Type> ostream& operator<<(ostream& os,BinaryTree<Type>& out){
	out.Print(out.m_proot);
	return os;
}

template<typename Type> BinaryTree<Type>& BinaryTree<Type>::operator=(BinaryTree<Type> copy){
	m_proot=m_proot->Copy(copy.m_proot);
    return *this;
}

MinHeap.h

template<typename Type> class MinHeap{
public:
	MinHeap(Type heap[],int n);		//initialize heap by a array
	~MinHeap(){
		delete[] m_pheap;
	}

public:
    bool Insert(const Type item);
    bool DeleteMin(Type &first);

private:
	void Adjust(const int start, const int end);	//adjust the elements from start to end


private:
	const int m_nMaxSize;	
	Type *m_pheap;
	int m_ncurrentsize;
};

template<typename Type> void MinHeap<Type>::Adjust(const int start, const int end){
	int i = start,j = i*2+1;
	Type temp=m_pheap[i];
	while(j <= end){
		if(j<end && m_pheap[j]>m_pheap[j+1]){
			j++;
		}
		if(temp <= m_pheap[j]){
			break;
		}
		else{
			m_pheap[i] = m_pheap[j];
			i = j;
			j = 2*i+1;
		}
	}
	m_pheap[i] = temp;
}

template<typename Type> MinHeap<Type>::MinHeap(Type heap[], int n):m_nMaxSize(n){
	m_pheap = new Type[m_nMaxSize];
	for(int i=0; i<n; i++){
		m_pheap[i] = heap[i];
	}
	m_ncurrentsize = n;
	int pos=(n-2)/2;	//Find the last tree which has more than one element;
	while(pos>=0){
		Adjust(pos, n-1);
		pos--;
	}
}

template<typename Type> bool MinHeap<Type>::DeleteMin(Type &first){
    first = m_pheap[0];
    m_pheap[0] = m_pheap[m_ncurrentsize-1];
    m_ncurrentsize--;
    Adjust(0, m_ncurrentsize-1);
    return 1;
}

template<typename Type> bool MinHeap<Type>::Insert(const Type item){
	if(m_ncurrentsize == m_nMaxSize){
		cerr<<"Heap Full!"<<endl;
		return 0;
	}
	m_pheap[m_ncurrentsize] = item;
	int j = m_ncurrentsize, i = (j-1)/2;
	Type temp = m_pheap[j];
	while(j > 0){
		if(m_pheap[i] <= temp){
			break;
		}
		else{
			m_pheap[j] = m_pheap[i];
			j = i;
			i = (j-1)/2;
		}
	}
	m_pheap[j] = temp;
	m_ncurrentsize++;
	return 1;
}

Huffman.h

#include "BinaryTree.h"
#include "MinHeap.h"

template<typename Type> void Huffman(Type *elements, int n, BinaryTree<Type> &tree){
    BinaryTree<Type> first, second;
    BinaryTree<Type> node[20];
    for (int i=0; i<n; i++){
        node[i].m_proot = new BinTreeNode<Type>(elements[i]);
    }
    MinHeap<BinaryTree<Type> > heap(node, n);

    for (int i=0; i<n-1; i++){
        heap.DeleteMin(first);
        heap.DeleteMin(second);
        
        //using the first and the second minimize element create new tree
        if (first.m_proot->GetData() == second.m_proot->GetData()){
            tree = *(new BinaryTree<Type>(second, first));
        }
        else {
            tree = *(new BinaryTree<Type>(first, second));
        }

        heap.Insert(tree);
    }
}

Test.cpp

#include <iostream>

using namespace std;

#include "Huffman.h"

int main(){
    BinaryTree<int> tree;
    int init[10]={3,6,0,2,8,4,9,1,5,7};
    Huffman(init,10,tree);
    cout << tree;
    tree.Destroy();
    return 0;
}
15、树

QueueNode.h

template<typename Type> class LinkQueue;

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

LinkQueue.h

#include "QueueNode.h"

template<typename Type> class LinkQueue{
public:
	LinkQueue():m_prear(NULL),m_pfront(NULL){}
	~LinkQueue(){
		MakeEmpty();
	}
	void Append(const Type item);
	Type Delete();
	Type GetFront();
	void MakeEmpty();
	bool IsEmpty() const{
		return m_pfront==NULL;
	}
	void Print();

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