数据结构各种算法实现(C++模板).doc

目 录
1、顺序表 1
Seqlist.h 1
Test.cpp 6
2、单链表 8
ListNode.h 8
SingleList.h 10
test.cpp 20
3、双向链表 22
NodeList.h 22
DoubleList.h 24
Test.cpp 34
4、循环链表 36
ListNode.h 36
CircularList.h 37
Test.cpp 47
5、顺序栈 49
SeqStack.h 49
Test.cpp 54
6、链式栈 55
StackNode.h 55
LinkStack.h 56
Test.cpp 60
7、顺序队列 62
SeqQueue.h 63
Test.cpp 68
8、链式队列 70
QueueNode.h 70
LinkQueue.h 71
Test.cpp 75
9、优先级队列 77
QueueNode.h 77
Compare.h 78
PriorityQueue.h 80
Test.cpp 85
10、串 88
MyString.h 88
MyString.cpp 90
test.cpp 101
11、二叉树 104
BinTreeNode.h 104
BinaryTree.h 112
Test.cpp 124
12、线索二叉树 126
ThreadNode.h 126
ThreadTree.h 128
ThreadInorderIterator.h 128
test.cpp 139
13、堆 140
MinHeap.h 140
test.cpp 147
14、哈夫曼树 149
BinTreeNode.h 149
BinaryTree.h 151
MinHeap.h 156
Huffman.h 161
Test.cpp 163
15、树 164
QueueNode.h 164
LinkQueue.h 165
TreeNode.h 169
Tree.h 170
test.cpp 187
16、B+树 189
BTreeNode.h 189
BTree.h 192
test.cpp 215
17、图 217
MinHeap.h 217
Edge.h 222
Vertex.h 223
Graph.h 224
test.cpp 246
18、排序 249
Data.h 249
QueueNode.h 255
LinkQueue.h 259
Sort.h 263
test.cpp 278

数据结构算法实现 2008-9-3
1、顺序表

Seqlist.h

const int DefaultSize=100;

template <typename Type> class SeqList{
public:
SeqList(int sz=DefaultSize)
:m_nmaxsize(sz),m_ncurrentsize(-1){
if(sz>0){
m_elements=new Type[m_nmaxsize];
}
}
~SeqList(){
delete[] m_elements;
}
int Length() const{ //get the length
return m_ncurrentsize+1;
}
int Find(Type x) const; //find the position of x
int IsElement(Type x) const; //is it in the list
int Insert(Type x,int i); //insert data
int Remove(Type x); //delete data
int IsEmpty(){
return m_ncurrentsize==-1;
}
int IsFull(){
return m_ncurrentsize==m_nmaxsize-1;
}
Type Get(int i){ //get the ith data
return i<0||i>m_ncurrentsize?(cout<<"can't find the element"<<endl,0):m_elements[i];
}
void Print();

private:
Type *m_elements;
const int m_nmaxsize;
int m_ncurrentsize;
};

template <typename Type> int SeqList<Type>::Find(Type x) const{
for(int i=0;i<m_ncurrentsize;i++)
if(m_elements[i]==x)
return i;
cout<<"can't find the element you want to find"<<endl;
return -1;
}

template <typename Type> int SeqList<Type>::IsElement(Type x) const{
if(Find(x)==-1)
return 0;
return 1;
}

template <typename Type> int SeqList<Type>::Insert(Type x, int i){
if(i<0||i>m_ncurrentsize+1||m_ncurrentsize==m_nmaxsize-1){
cout<<"the operate is illegal"<<endl;
return 0;
}
m_ncurrentsize++;
for(int j=m_ncurrentsize;j>i;j--){
m_elements[j]=m_elements[j-1];
}
m_elements[i]=x;
return 1;
}

template <typename Type> int SeqList<Type>::Remove(Type x){
int size=m_ncurrentsize;
for(int i=0;i<m_ncurrentsize;){
if(m_elements[i]==x){
for(int j=i;j<m_ncurrentsize;j++){
m_elements[j]=m_elements[j+1];
}
m_ncurrentsize--;
continue;
}
i++;
}
if(size==m_ncurrentsize){
cout<<"can't find the element you want to remove"<<endl;
return 0;
}
return 1;
}

template <typename Type> void SeqList<Type>::Print(){
for(int i=0;i<=m_ncurrentsize;i++)
cout<<i+1<<":\t"<<m_elements[i]<<endl;
cout<<endl<<endl;
}

Test.cpp

#include <iostream>
#include "SeqList.h"

using namespace std;

int main()
{
SeqList<int> test(15);
int array[15]={2,5,8,1,9,9,7,6,4,3,2,9,7,7,9};
for(int i=0;i<15;i++){
test.Insert(array[i],0);
}
test.Insert(1,0);
cout<<(test.Find(0)?"can't be found ":"Be found ")<< 0 << endl<<endl;
test.Remove(7);
test.Print();
test.Remove(9);
test.Print();
test.Remove(0);
test.Print();
return 0;
}
2、 单链表

ListNode.h

template<typename Type> class SingleList;

template<typename Type> class ListNode{
private:
friend typename SingleList<Type>;

ListNode():m_pnext(NULL){}
ListNode(const Type item,ListNode<Type> *next=NULL):m_data(item),m_pnext(next){}
~ListNode(){
m_pnext=NULL;
}

public:
Type GetData();
friend ostream& operator<< <Type>(ostream& ,ListNode<Type>&);

private:
Type m_data;
ListNode *m_pnext;
};

template<typename Type> Type ListNode<Type>::GetData(){
return this->m_data;
}

template<typename Type> ostream& operator<<(ostream& os,ListNode<Type>& out){
os<<out.m_data;
return os;
}

SingleList.h

#include "ListNode.h"

template<typename Type> class SingleList{
public:
SingleList():head(new ListNode<Type>()){}
~SingleList(){
MakeEmpty();
delete head;
}

public:
void MakeEmpty(); //make the list empty
int Length(); //get the length
ListNode<Type> *Find(Type value,int n); //find thd nth data which is equal to value
ListNode<Type> *Find(int n); //find the nth data
bool Insert(Type item,int n=0); //insert the data in the nth position
Type Remove(int n=0); //remove the nth data
bool RemoveAll(Type item); //remove all the data which is equal to item
Type Get(int n); //get the nth data
void Print(); //print the list

private:
ListNode<Type> *head;
};

template<typename Type> void SingleList<Type>::MakeEmpty(){
ListNode<Type> *pdel;
while(head->m_pnext!=NULL){
pdel=head->m_pnext;
head->m_pnext=pdel->m_pnext;
delete pdel;
}
}

template<typename Type> int SingleList<Type>::Length(){
ListNode<Type> *pmove=head->m_pnext;
int count=0;
while(pmove!=NULL){
pmove=pmove->m_pnext;
count++;
}
return count;
}

template<typename Type> ListNode<Type>* SingleList<Type>::Find(int n){
if(n<0){
cout<<"The n is out of boundary"<<endl;
return NULL;
}
ListNode<Type> *pmove=head->m_pnext;
for(int i=0;i<n&&pmove;i++){
pmove=pmove->m_pnext;
}
if(pmove==NULL){
cout<<"The n is out of boundary"<<endl;
return NULL;
}
return pmove;
}

template<typename Type> ListNode<Type>* SingleList<Type>::Find(Type value,int n){
if(n<1){
cout<<"The n is illegal"<<endl;
return NULL;
}
ListNode<Type> *pmove=head;
int count=0;
while(count!=n&&pmove){
pmove=pmove->m_pnext;
if(pmove->m_data==value){
count++;
}

}
if(pmove==NULL){
cout<<"can't find the element"<<endl;
return NULL;
}
return pmove;
}

template<typename Type> bool SingleList<Type>::Insert(Type item, int n){
if(n<0){
cout<<"The n is illegal"<<endl;
return 0;
}
ListNode<Type> *pmove=head;
ListNode<Type> *pnode=new ListNode<Type>(item);
if(pnode==NULL){
cout<<"Application error!"<<endl;
return 0;
}
for(int i=0;i<n&&pmove;i++){
pmove=pmove->m_pnext;
}
if(pmove==NULL){
cout<<"the n is illegal"<<endl;
return 0;
}
pnode->m_pnext=pmove->m_pnext;
pmove->m_pnext=pnode;
return 1;
}

template<typename Type> bool SingleList<Type>::RemoveAll(Type item){
ListNode<Type> *pmove=head;
ListNode<Type> *pdel=head->m_pnext;
while(pdel!=NULL){
if(pdel->m_data==item){
pmove->m_pnext=pdel->m_pnext;
delete pdel;
pdel=pmove->m_pnext;
continue;
}
pmove=pmove->m_pnext;
pdel=pdel->m_pnext;
}
return 1;
}

template<typename Type> Type SingleList<Type>::Remove(int n){
if(n<0){
cout<<"can't find the element"<<endl;
exit(1);
}
ListNode<Type> *pmove=head,*pdel;
for(int i=0;i<n&&pmove->m_pnext;i++){
pmove=pmove->m_pnext;
}
if(pmove->m_pnext==NULL){
cout<<"can't find the element"<<endl;
exit(1);
}
pdel=pmove->m_pnext;
pmove->m_pnext=pdel->m_pnext;
Type temp=pdel->m_data;
delete pdel;
return temp;
}

template<typename Type> Type SingleList<Type>::Get(int n){
if(n<0){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
ListNode<Type> *pmove=head->m_pnext;
for(int i=0;i<n;i++){
pmove=pmove->m_pnext;
if(NULL==pmove){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
}
return pmove->m_data;
}

template<typename Type> void SingleList<Type>::Print(){
ListNode<Type> *pmove=head->m_pnext;
cout<<"head";
while(pmove){
cout<<"--->"<<pmove->m_data;
pmove=pmove->m_pnext;
}
cout<<"--->over"<<endl<<endl<<endl;
}

test.cpp

#include <iostream>
using namespace std;

#include "SingleList.h"

int main()
{
SingleList<int> list;
for(int i=0;i<20;i++){
list.Insert(i*3,i);
}
for(int i=0;i<5;i++){
list.Insert(3,i*3);
}
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();

list.Remove(5);
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();

list.RemoveAll(3);
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();

cout<<"The third element is "<<list.Get(3)<<endl;

cout<<*list.Find(18,1)<<endl;

list.Find(100);

list.MakeEmpty();
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();

return 0;
}

3、 双向链表

NodeList.h

template<typename Type> class DoublyList;

template<typename Type> class ListNode{
private:
friend class DoublyList<Type>;
ListNode():m_pprior(NULL),m_pnext(NULL){}
ListNode(const Type item,ListNode<Type> *prior=NULL,ListNode<Type> *next=NULL)
:m_data(item),m_pprior(prior),m_pnext(next){}
~ListNode(){
m_pprior=NULL;
m_pnext=NULL;
}
public:
Type GetData();
private:
Type m_data;
ListNode *m_pprior;
ListNode *m_pnext;
};

template<typename Type> Type ListNode<Type>::GetData(){
return this->m_data;
}

DoubleList.h

#include "ListNode.h"

template<typename Type> class DoublyList{
public:
DoublyList():head(new ListNode<Type>()){ //the head node point to itself
head->m_pprior=head;
head->m_pnext=head;
}
~DoublyList(){
MakeEmpty();
delete head;
}

public:
void MakeEmpty(); //make the list empty
int Length(); //get the length of the list
ListNode<Type> *Find(int n=0); //find the nth data
ListNode<Type> * FindData(Type item); //find the data which is equal to item
bool Insert(Type item,int n=0); //insert item in the nth data
Type Remove(int n=0); //delete the nth data
Type Get(int n=0); //get the nth data
void Print(); //print the list

private:
ListNode<Type> *head;
};

template<typename Type> void DoublyList<Type>::MakeEmpty(){
ListNode<Type> *pmove=head->m_pnext,*pdel;
while(pmove!=head){
pdel=pmove;
pmove=pdel->m_pnext;
delete pdel;
}
head->m_pnext=head;
head->m_pprior=head;
}

template<typename Type> int DoublyList<Type>::Length(){
ListNode<Type> *pprior=head->m_pprior,*pnext=head->m_pnext;
int count=0;
while(1){
if(pprior->m_pnext==pnext){
break;
}
if(pprior==pnext&&pprior!=head){
count++;
break;
}
count+=2;
pprior=pprior->m_pprior;
pnext=pnext->m_pnext;
}
return count;
}

template<typename Type> ListNode<Type>* DoublyList<Type>::Find(int n = 0){
if(n<0){
cout<<"The n is out of boundary"<<endl;
return NULL;
}
ListNode<Type> *pmove=head->m_pnext;
for(int i=0;i<n;i++){
pmove=pmove->m_pnext;
if(pmove==head){
cout<<"The n is out of boundary"<<endl;
return NULL;
}
}
return pmove;
}

template<typename Type> bool DoublyList<Type>::Insert(Type item,int n){
if(n<0){
cout<<"The n is out of boundary"<<endl;
return 0;
}
ListNode<Type> *newnode=new ListNode<Type>(item),*pmove=head;
if(newnode==NULL){
cout<<"Application Erorr!"<<endl;
exit(1);
}
for(int i=0;i<n;i++){ //find the position for insert
pmove=pmove->m_pnext;
if(pmove==head){
cout<<"The n is out of boundary"<<endl;
return 0;
}
}

//insert the data
newnode->m_pnext=pmove->m_pnext;
newnode->m_pprior=pmove;
pmove->m_pnext=newnode;
newnode->m_pnext->m_pprior=newnode;
return 1;
}

template<typename Type> Type DoublyList<Type>::Remove(int n = 0){
if(n<0){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
ListNode<Type> *pmove=head,*pdel;
for(int i=0;i<n;i++){ //find the position for delete
pmove=pmove->m_pnext;
if(pmove==head){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
}

//delete the data
pdel=pmove;
pmove->m_pprior->m_pnext=pdel->m_pnext;
pmove->m_pnext->m_pprior=pdel->m_pprior;
Type temp=pdel->m_data;
delete pdel;
return temp;
}

template<typename Type> Type DoublyList<Type>::Get(int n = 0){
if(n<0){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
ListNode<Type> *pmove=head;
for(int i=0;i<n;i++){
pmove=pmove->m_pnext;
if(pmove==head){
cout<<"The n is out of boundary"<<endl;
exit(1);
}
}
return pmove->m_data;
}

template<typename Type> void DoublyList<Type>::Print(){
ListNode<Type> *pmove=head->m_pnext;
cout<<"head";
while(pmove!=head){
cout<<"--->"<<pmove->m_data;
pmove=pmove->m_pnext;
}
cout<<"--->over"<<endl<<endl<<endl;

}

template<typename Type> ListNode<Type>* DoublyList<Type>::FindData(Type item){
ListNode<Type> *pprior=head->m_pprior,*pnext=head->m_pnext;
while(pprior->m_pnext!=pnext && pprior!=pnext){ //find the data in the two direction
if(pprior->m_data==item){
return pprior;
}
if(pnext->m_data==item){
return pnext;
}
pprior=pprior->m_pprior;
pnext=pnext->m_pnext;
}
cout<<"can't find the element"<<endl;
return NULL;
}

Test.cpp

#include <iostream>
#include "DoublyList.h"

using namespace std;

int main()
{
DoublyList<int> list;
for(int i=0;i<20;i++){
list.Insert(i*3,i);
}
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();
for(int i=0;i<5;i++){
list.Insert(3,i*3);
}
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();

list.Remove(5);
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();

cout<<list.FindData(54)->GetData()<<endl;

cout<<"The third element is "<<list.Get(3)<<endl;

list.MakeEmpty();
cout<<"the Length of the list is "<<list.Length()<<endl;
list.Print();

return 0;
}

4、 循环链表

ListNode.h

template<typename Type> class CircularList;

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

private:
Type m_data;
ListNode *m_pnext;
};

CircularList.h

#include "ListNode.h"

template<typename Type> class CircularList{
public:
CircularList():head(new ListNode<Type>()){
head->m_pnext=head;
}
~CircularList(){
MakeEmpty();
delete head;
}
public:
void MakeEmpty(); //clear the list
int Length(); //get the length
ListNode<Type> *Find(Type value,int n); //find the nth data which is equal to value
ListNode<Type> *Find(int n); //find the nth data
bool Insert(Type item,int n=0); //