数据结构算法集 c++语言实现(上).txt

数据结构常用算法

template<class Type> 
void Compositor<Type>::Msort(Type SR[],Type TR1[],int s,int t) 
{ 
int m; 
Type *TR2=new Type[t-s]; 
if(s==t) TR1[s]=SR[s]; 
else 
{ 
m=(t+s)/2; 
Msort(SR,TR2,s,m); 
Msort(SR,TR2,m+1,t); 
Merge(TR2,TR1,s,m,t); 
} 
} 

template<class Type> 
void Compositor<Type>::Merge(Type SR[],Type TR[],int i,int m,int n) 
{ 
for(int j=m+1,k=i;i<=m&&j<=n;k++) 
{ 
if(SR<=SR[j]) 
TR[k]=SR[i++]; 
else 
TR[k]=SR[j++]; 
} 
while(i<=m) 
TR[k++]=SR[i++]; 
while(j<=n) 
TR[k++]=SR[j++]; 
} 


template<class Type> 
void Compositor<Type>::Select() 
{ 
Creat(); 
Type temp; 
int t; 
for(int i=0;i<leng;i++) 
{ 
t=i; 
for(int j=i+1;j<leng;j++) 
{ 
if(sort[t]>sort[j]) 
t=j; 
} 
if(t!=i) 
{ 
temp=sort[t]; 
sort[t]=sort; 
sort=temp; 
} 
} 
Print(); 
} 

template<class Type> 
void Compositor<Type>::Print() 
{ 
cout<<"排序结果为: "; 
for(int i=0;i<leng;i++) 
cout<<sort<<" "; 
cout<<endl; 
}
/////////////////////////// 
//   // 
//   二叉树数据结构 BinTree.h     // 
//   // 
////////////////////////// 


#include<iostream.h> 

template<class Type>class BinTree; 

template<class Type> 
class TreeNode 
{ 
protected: 
  friend class BinTree<Type>; 
TreeNode():lchild(NULL),rchild(NULL){} 
  Type data; 
  TreeNode *lchild; //左，右子树 
  TreeNode *rchild; 
}; 

template<class Type> 
class BinTree 
{ 
friend void BinTree_PRE(BinTree<Type>& BinTreeOPP); //友元函数 
friend void BinTree_INO(BinTree<Type>& BinTreeOPP); 
friend void BinTree_POS(BinTree<Type>& BinTreeOPP); 
friend void BinTree_Destroy(BinTree<Type>& BinTreeOPP); 
public: 
BinTree():root(NULL){} 
void CreatTree();           //创建二叉树,主过程 
void CreatTree(TreeNode<Type>* child,int k); //子过程 
void PreTree(TreeNode<Type> *point);   //先序遍历二叉树 
void InoTree(TreeNode<Type> *point); //中序遍历二叉树 
void PosTree(TreeNode<Type> *point); //后序遍历二叉树 
void Destroy(TreeNode<Type> *point);   //销毁二叉树 
bool ISEmpty(); 
protected: 
TreeNode<Type>* root; 
}; 


template<class Type> 
void BinTree<Type>::CreatTree() 
{ 
CreatTree(root,1); 
} 

template<class Type> 
void BinTree<Type>::CreatTree(TreeNode<Type>* child,int k) 
{ 
TreeNode<Type>* point; 
point=new TreeNode<Type>; 
cout<<"输入节点数据项 :"; 
cin>>point->data; 
switch(k) 
{ 
case 1: root=point; break; 
case 2: child->lchild=point;break; 
case 3: child->rchild=point;break; 
} 

char temp; 
cout<<"该"<<point->data<<"节点是否有左子树 Y / 任意键 :"; 
cin>>temp; 
if(temp=='y'||temp=='Y') 
{ 
  CreatTree(point,2); 
} 

cout<<"该"<<point->data<<"节点是否有右子树 Y / 任意键 :"; 
cin>>temp; 
if(temp=='y'||temp=='Y') 
{ 
CreatTree(point,3); 
} 
} 

template<class Type> 
void BinTree<Type>::PreTree(TreeNode<Type> *point) 
{ 
if(point!=NULL) 
{ 
cout<<" "<<point->data; 
PreTree(point->lchild); 
PreTree(point->rchild); 
} 
} 


template<class Type> 
void BinTree<Type>::InoTree(TreeNode<Type> *point) 
{ 
if(point!=NULL) 
{ 
  
  InoTree(point->lchild); 
cout<<" "<<point->data; 
InoTree(point->rchild); 
} 
} 

template<class Type> 
void BinTree<Type>::PosTree(TreeNode<Type> *point) 
{ 
if(point!=NULL) 
{ 
  
PosTree(point->lchild); 
PosTree(point->rchild); 
cout<<" "<<point->data; 
} 
} 


template<class Type> 
bool BinTree<Type>::ISEmpty() 
{ 
return root==NULL; 
} 

template<class Type> 
void BinTree<Type>::Destroy(TreeNode<Type> *point) 
{ 
if(point!=NULL) 
{ 
Destroy(point->lchild); 
Destroy(point->rchild); 
delete point; 
} 
}
/////////////////////////// 
//   // 
// 基本功能函数 BaseFun.h   // 
//   // 
////////////////////////// 

void GRAPH(); 
void LIST(); 
void STACK(); 
void QUEUE(); 
void COMPOSITOR(); 
void BINTREE(); 

/////////////////////////// 
//   // 
//   堆栈功能函数   Stack.cpp/ / 
//   // 
////////////////////////// 



#include"Stack.h" 
#include"iostream.h" 


const int INT =13; 
const double FLOAT= 13.33; 
const char CHAR ='a'; 




template<class Type> 
void Stack_Push(Stack<Type> &StackOPP) 
{ 
cout<<"请输入要插入的数据项: "; 
Type item; 
cin>>item; 
StackOPP.Push(item); 
} 

template<class Type> 
void Stack_Pop(Stack<Type> &StackOPP) 
{ 
if(!StackOPP.ISEmpty()) 
{ 
  cout<<"出栈数据项: "; 
  cout<<StackOPP.Pop()<<endl; 
} 
else 
{ 
cout<<"堆栈已经为空!"<<endl; 
} 
} 

template<class Type> 
void Stack_ISEmpty(Stack<Type> &StackOPP) 
{ 
if(!StackOPP.ISEmpty()) 
  cout<<"堆栈不空,还有"<<StackOPP.GetNum()<<"数据项!"<<endl; 
else 
cout<<"堆栈为空!"<<endl; 
  
} 

template<class Type> 
void Stack_GetTop(Stack<Type> &StackOPP) 
{ 
if(!StackOPP.ISEmpty()) 
cout<<"栈顶元素为："<<StackOPP.GetTop()<<endl; 
else 
cout<<"堆栈为空!"<<endl; 
} 

template<class Type> 
void Stack_MakeEmpty(Stack<Type> &StackOPP) 
{ 
if(!StackOPP.ISEmpty()) 
{ 
StackOPP.MakeEmpty(); 
cout<<"堆栈已经销毁!"<<endl; 
} 
else 
{ 
cout<<"销毁失败!"<<endl; 
} 
} 


template<class Type> 
void StackINI(Type temp) 
{ 
Stack<Type> StackOPP; 

do 
{ 
cout<<"堆栈的操作: "<<endl 
<<" 1) 插入堆栈"<<endl 
<<" 2) 出栈"<<endl 
<<" 3) 堆栈是否为空"<<endl 
<<" 4) 得栈顶数据项"<<endl 
<<" 5) 销毁堆栈"<<endl 
<<" X) 退出堆栈操作"<<endl; 
int item; 
cin>>item; 
switch(item) 
{ 
case 1: Stack_Push(StackOPP); break; 
case 2: Stack_Pop(StackOPP); break; 
case 3: Stack_ISEmpty(StackOPP); break; 
case 4: Stack_GetTop(StackOPP); break; 
case 5: Stack_MakeEmpty(StackOPP); break; 

default: return ; 
} 

}while(true); 


} 


void STACK() 
{ 
int item; 
cout<<"清选择数据类型: 1) 整型 2) 浮点型 3) 字符型 X) 退出: "; 

cin>>item; 
switch(item) 
{ 
case 1: StackINI(INT); break; //根据不同的用户需要选择数据类型 
case 2: StackINI(FLOAT); break; 
case 3: StackINI(CHAR); break; 
default: return ; break; 
} 
} 



/////////////////////////// 
//   // 
//   队列功能函数 Queue.h // 
//   // 
////////////////////////// 



#include"Queue.h" 

const int INT =13; 
const double FLOAT= 13.33; 
const char CHAR ='a'; 



template<class Type> 
void Queue_Enter(Queue<Type> &QueueOPP) 
{ 
cout<<"请输入要插入队列的数据: "; 
Type item; 
cin>>item; 
QueueOPP.EnQueue(item); 
} 

template<class Type> 
void Queue_Del(Queue<Type> &QueueOPP) 
{ 
if(!QueueOPP.ISEmpty()) 
{ 
cout<<"出队数据:"<<QueueOPP.DelQueue()<<endl; 
} 
else 
{ 
cout<<"队列已为空!"<<endl; 
} 
} 

template<class Type> 
void Queue_ISEmpty(Queue<Type> &QueueOPP) 
{ 
if(QueueOPP.ISEmpty()) 
{ 
cout<<"队列已空!"<<endl; 
} 
else 
{ 
cout<<"队列不空!"<<endl; 
} 
} 


template<class Type> 
void Queue_GetFront(Queue<Type> &QueueOPP) 
{ 
if(!QueueOPP.ISEmpty()) 
{ 
cout<<"队头元素为: "<<QueueOPP.GetFront()<<endl; 
} 
else 
{ 
cout<<"队列已空!"<<endl; 
} 
} 

template<class Type> 
void Queue_MakeEmpty(Queue<Type> &QueueOPP) 
{ 
QueueOPP.MakeEmpty(); 
cout<<"队列清空!"<<endl; 
} 

template<class Type> 
void QueueINI(Type temp) 
{ 
Queue<Type> QueueOPP; 

do 
{ 
cout<<"队列的操作: "<<endl 
<<" 1) 插入队列"<<endl 
<<" 2) 出队"<<endl 
<<" 3) 队列是否为空"<<endl 
<<" 4) 得队头数据项"<<endl 
<<" 5) 销毁队列"<<endl 
<<" X) 退出队列操作"<<endl; 
int item; 
cin>>item; 
switch(item) 
{ 
case 1: Queue_Enter(QueueOPP); break; 
case 2: Queue_Del(QueueOPP); break; 
case 3: Queue_ISEmpty(QueueOPP); break; 
case 4: Queue_GetFront(QueueOPP); break; 
case 5: Queue_MakeEmpty(QueueOPP); break; 

default: return ; 
} 

}while(true); 


} 


void QUEUE() //根据不同的用户需要选择数据类型 
{ 
int item; 
cout<<"清选择数据类型: 1) 整型 2) 浮点型 3) 字符型 X) 退出: "; 


cin>>item; 
switch(item) 
{ 
case 1: QueueINI(INT); break;   
case 2: QueueINI(FLOAT); break; 
case 3: QueueINI(CHAR); break; 
default: return ; break; 
} 
}


/////////////////////////// 
//   // 
//   链表   List.h       // 
//   // 
////////////////////////// 


#include"list.h" 
#include<iostream.h> 
#include<stdlib.h> 


template<class type> 
void initlist(type &tmp) 
{ 
list<type> List; 
int n; 

while(true) 
{ 

cout<<"请选择你要对链表进行的操作 "<<endl 
<<"1) 在末尾插入数据"<<endl 
  <<"2) 在任意处插入数据"<<endl 
<<"3) 删除数据项"<<endl 
<<"4) 删除整个链表"<<endl 
<<"5) 打印链表"<<endl 
<<"6) 查找数据项"<<endl 
<<"7) 退出"<<endl; 

cout<<">\ "; 
cin>>n; 

while(n<1||n>7) 
{ 
cout<<"输入有误，请从新输入!"<<endl; 
  cout<<">\ "; 
  cin>>n; 
} 

switch(n) 
{ 
case 1: list_insertend(List);break; 
case 2: list_insert(List);break; 
case 3: list_delnode(List);break; 
case 4: list_makeempty(List);break; 
case 5: list_print(List);break; 
case 6: list_find(List);break; 
case 7: return ;break; 
} 

} 

} 

void LIST() 
{ 
int n; 
cout<<"请选择你要构造的链表的数据类型 1)整型，2)字符型,3)浮点型"<<endl;   
cout<<">\ "; 
cin>>n; 

while(n<1||n>3) 
{ 
cout<<"输入有误，请从新输入!"<<endl; 
  cout<<">\ "; 
  cin>>n; 
} 

char t_c='c'; 
int t_i=12; 
double t_f=23.3; 

switch(n) 
{ 
case 1:initlist(t_i);break; 
case 2:initlist(t_c);break; 
case 3:initlist(t_f);break; 
} 
} 

template<class type> 
void list_insertend(list<type> &L) 
{ 
type t; 
cout<<"请输入插入数据: >\"; 
cin>>t; 
L.insertend(t); 
} 

template<class type> 
void list_find(list<type> &L) 
{ 
type T; 
cout<<"请输入你要查找的数据项：>\ "; 
cin>>T; 

int i; 
if(!(i=L.find(T))) 
cout<<"你要查找的数据项不存在!"<<endl; 
else 
cout<<"你要查找的数据项在第"<<i<<"个位置"<<endl; 
} 

template<class type> 
void list_insert(list<type> &L) 
{ 

type t; 
cout<<"请输入插入数据: >\"; 
cin>>t; 

int n; 
cout<<"请输入插入位置: >\"; 
cin>>n; 
if(L.insert(t,n)) 
cout<<"插入成功! 在"<<n<<"位置 插入"<<t<<endl; 
else 
cout<<"插入失败! 插入位置不正确!"<<endl; 

} 

template<class type> 
void list_delnode(list<type>& L) 
{ 
int i; 
cout<<"请输入要删除数据项的位置: >\"; 
cin>>i; 


while(i<1||i>L.getlen()) 
{ 
  cout<<"输入有误，可能大与链表长度,请从新输入!"<<endl; 
  cout<<">\ "; 
cin>>i; 
} 

L.delnode(i); 
} 
template<class type> 
void list_makeempty(list<type> &L) 
{ 
L.makeempty(); 
} 

template<class type> 
void list_print(list<type> &L) 
{ 
if(!L.print()) 
cout<<"链表为空!"<<endl; 
}
/////////////////////////// 
//   // 
//   图功能函数 Graph.h   // 
//   // 
////////////////////////// 


#include"Graph.h" 

template<class NameType,class DisType> 
void Graph_Creat(Graph<NameType,DisType> &GraphOPP) 
{ 
GraphOPP.Creat(); 
} 

template<class NameType,class DisType> 
void Graph_DFS(Graph<NameType,DisType> &GraphOPP) 
{ 
GraphOPP.DFS(); 
} 

template<class NameType,class DisType> 
void Graph_BFS(Graph<NameType,DisType> &GraphOPP) 
{ 
GraphOPP.BFS(); 
} 

template<class NameType,class DisType> 
void Graph_PRINT(Graph<NameType,DisType> &GraphOPP) 
{ 
GraphOPP.PrintNode(); 
} 


void GRAPH() 
{ 
Graph<char,int> GraphOPP; 
do 
{ 
cout<<"图的操作: "<<endl 
<<" 1) 建立图"<<endl 
<<" 2) 图的深度优先搜索"<<endl 
<<" 3) 图的广度优先搜索"<<endl 
<<" 4) 打印图中各结点"<<endl 
<<" X) 退出排序操作"<<endl; 
int item; 
cin>>item; 
switch(item) 
{ 
case 1: Graph_Creat(GraphOPP); break; 
case 2: Graph_DFS(GraphOPP); break; 
case 3: Graph_BFS(GraphOPP); break; 
case 4: Graph_PRINT(GraphOPP); break; 
default: return ; 
} 

}while(true); 


}