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

数据结构常用算法

数据结构算法集 C++语言实现(上)

/////////////////////////// 
//   // 
//   堆栈数据结构   stack.h       // 
//   // 
////////////////////////// 


#include<iostream.h> 

template<class Type>class Stack; 

template<class Type> 
class StackNode 
{ 
friend class Stack<Type>; 
private: 
Type data; 
StackNode<Type> *link; 
  StackNode(Type D=0,StackNode<Type> *L=NULL):link(L),data(D){} 
}; 

template<class Type> 
class Stack 
{ 
public: 
Stack():top(NULL),NumItem(0){} 
void Push(Type item); 
Type Pop(); 
Type GetTop(); 
void MakeEmpty(); 
bool ISEmpty(); 
int GetNum(); 
private: 
int NumItem; 
StackNode<Type> *top; 
}; 

template<class Type> 
void Stack<Type>::Push(Type item) 
{ 
top=new StackNode<Type>(item,top); 
NumItem++; 
} 

template<class Type> 
Type Stack<Type>::Pop() 
{ 
StackNode<Type> *p; 
Type temp; 
temp=top->data; 
p=top; 
top=top->link; 
delete p; 
NumItem--; 
return temp; 

} 

template<class Type> 
Type Stack<Type>::GetTop() 
{ 
return top->data; 
} 

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

template<class Type> 
void Stack<Type>::MakeEmpty() 
{ 
delete top; 
} 

template<class Type> 
int Stack<Type>::GetNum() 
{ 
return NumItem; 
}
/////////////////////////// 
//   // 
//   队列数据结构     Queue.h // 
//   // 
////////////////////////// 
#include<iostream.h> 

template<class Type> class Queue; 

template<class Type> class QueueNode 
{ 
friend class Queue<Type>; 
private: 
Type data; 
QueueNode<Type> *link; 
QueueNode(Type d=0,QueueNode *l=NULL):data(d),link(l){} 
}; 

template <class Type> class Queue 
{ 
public: 
Queue():rear(NULL),front(NULL){} 
~Queue(); 
void EnQueue(Type item); 
Type DelQueue(); 
Type GetFront(); 
void MakeEmpty(); 
bool ISEmpty() { return front==NULL; } 
private: 
QueueNode<Type> *front,*rear; 
}; 


template<class Type> 
Queue<Type>::~Queue() 
{ 
QueueNode<Type> *p; 
while(front!=NULL) 
{ 
p=front; 
front=front->link; 
delete p; 
} 
} 

template<class Type> 
void Queue<Type>::EnQueue(Type item) 
{ 
if(front==NULL) 
front=rear=new QueueNode<Type> (item,NULL); 
else 
rear=rear->link=new QueueNode<Type> (item,NULL); 
} 


template<class Type> 
Type Queue<Type>::DelQueue() 
{ 
QueueNode<Type> *p=front; 
Type temp=p->data;; 
front=front->link; 
delete p; 
return temp; 
} 


template<class Type> 
Type Queue<Type>::GetFront() 
{ 
return front->data; 
} 


template<class Type> 
void Queue<Type>::MakeEmpty() 
{ 
QueueNode<Type> *p; 
while(front!=NULL) 
{ 
p=front; 
front=front->link; 
delete p; 
} 
}
/////////////////////////// 
//   // 
//   链表数据结构 list.h // 
//   // 
////////////////////////// 


#include<iostream.h> 

template<class type> 
class list; 

template<class type> 
class listnode 
{ 
public: 
friend class list<type>; 
private: 
type data; 
listnode<type> * next; 
}; 


template<class type> 
class list 
{ 
public: 
list(); 
~list(); 
void insertend(type); //向链表尾部插入元素 
bool insert(type,int); //向链表任意位置插入元素 
void delnode(int i); //删除元素 
int find(type T);   //查找元素 
void makeempty();   //销毁链表 
bool print(); //打印链表 
int getlen(); //得到链表长度 
private: 
listnode<type> *first,*last; 
int length; 
}; 

template<class type> 
void initlist(type &tmp); 

template<class type> 
void list_exit(list<type> &L,type tmp); 

void initation(); 

template<class type> 
void list_insertend(list<type> &L,type tmp); 


template<class type> int list<type>::getlen() 
{ 
return length; 
} 

template<class type> void list<type>::makeempty() 
{ 
listnode<type> *p1,*p2; 

p1=first->next; 
first->next=NULL; 
while(p1!=NULL) 
{ 
p2=p1; 
p1=p1->next; 
delete p2; 
} 
length=0;   
} 

template<class type> void list<type>::insertend(type t) 
{ 

listnode<type> *p; 
p=new listnode<type>; 
p->data=t; 
p->next=NULL; 
last->next=p; 
last=p; 

length++; 
} 

template<class type> bool list<type>::insert(type t,int i) 
{ 
listnode<type> *p; 
p=first; 

int k=1; 
while(p!=NULL&&k<i) 
{ 
p=p->next; 
k++; 
} 
if(p==NULL&&k!=i) 
return false; 
else 
{ 
  listnode<type> *tp; 
tp=new listnode<type>; 
tp->data=t; 
tp->next=p->next; 
p->next=tp; 
length++; 
  
return true; 
} 
} 

template<class type> void list<type>::delnode(int i) 
{ 
int k=1; 
listnode<type> *p,*t; 
p=first; 

while(p->next!=NULL&&k!=i) 
{ 
p=p->next; 
  k++; 
} 
t=p->next; 
cout<<"你已经将数据项 "<<t->data<<"删除"<<endl; 

p->next=p->next->next; 
length--; 
delete t; 
} 

template<class type> bool list<type>::print() 
{ 
listnode<type> *p=first->next; 
if(length==0) 
return false; 
else 
{ 
cout<<"链表中有"<<length<<"项数据: "<<endl; 
while(p) 
{ 
cout<<p->data<<" "; 
p=p->next; 
} 
} 
cout<<endl; 


return true; 
} 

template<class type> int list<type>::find(type T) 
{ 
listnode<type> *p=first->next; 
int i=1; 
while(p&&p->data!=T) 
{ 
p=p->next; 
i++; 
} 
if(p) 
return i; 
else 
  return 0; 
} 


template<class type> list<type>::~list() 
{ 
delete first; 
cout<<"欢迎再次使用 (!^!) "<<endl; 
} 

template<class type> list<type>::list() 
{ 
  listnode<type> *node=new listnode<type>; 
node->next=NULL; 
first=last=node; 
length=0; 
}
/////////////////////////// 
//   // 
//   图数据结构 graph.h // 
//   // 
////////////////////////// 


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

template<class NameType,class DisType>class Graph; 

template<class NameType,class DisType> struct Node   
{ 
friend class Graph<NameType,DisType>; 
int num; 
DisType val; 
Node<NameType,DisType> *next; 
}; 

template<class NameType,class DisType> struct GpNode 
{ 
friend class Graph<NameType,DisType>; 
NameType data; 
Node<NameType,DisType> *link; 
}; 

template<class NameType,class DisType> 
class Graph 
{ 
public: 
void Creat(); //创建图 
void PrintNode();   //打印图中的各个数据项 
void DFS();   //图的深度优先搜索,主过程 
void DFS(int v,int visited[]); // 子过程 
void BFS(); //图的广度优先搜索，主过程 
void BFS(int v,int visited[]); //子过程 
void ShortPath();   //求最短路径 
private: 
GpNode<NameType,DisType> *table; 
Node<NameType,DisType> *p; 
int NumNode;     //节点个数 
}; 


template<class NameType,class DisType> 
void Graph<NameType,DisType>::Creat() 
{ 
do 
{ 
cout<<"请输入节点个数: "; 
cin >> NumNode; 
}while(NumNode<=0); 

table=new GpNode<NameType,DisType>[NumNode]; 
cout<<"请输入各节点数据项"<<endl; 
for(int i=0;i<NumNode;i++) 
{ 
cin>>table.data; 
table.link=NULL; 
} 

cout<<"请输入各边的关系 (如: A B)"<<endl; 
i=1; 
NameType nodeA,nodeB; 
bool findA,findB; 
char ISExit; 
int m,n; 
do 
{ 
findA=findB=false; 
cout<<"请输入第"<<i<<"对边的关系"<<endl; 
cin>>nodeA>>nodeB; 
for(m=0,n=0;m<NumNode&&n<NumNode&&!(findA & findB);) //查找边的节点 
{ 
if(nodeA!=table[m].data) 
m++; 
else 
findA=true; 
if(nodeB!=table[n].data) 
n++; 
else 
findB=true; 

} 
if(!(findA & findB)) 
cout<<"输入的节点数据项有错误"<<endl; 
else 
{ 
p=new Node<NameType,DisType>; 
p->next=table[m].link; 
p->num=n; 
table[m].link=p; 
cout<<"请输入该对边的权值: "; 
cin>>p->val; 
i++; 
} 
cout<<"是否继续输入: y)继续,X)任意键退出 "; 
cin>>ISExit; 
if(ISExit!='y'&&ISExit!='Y') 
break; 

}while(true); 
  
} 

template<class NameType,class DisType> 
void Graph<NameType,DisType>::PrintNode() 
{ 
cout<<"图中各节点数据项 : "; 
for(int i=0;i<NumNode;i++) 
  cout<<table.data<<" "; 
cout<<endl; 
} 


template<class NameType,class DisType> 
void Graph<NameType,DisType>::DFS() 
{ 
int *visited=new int[NumNode]; 
cout<<"图的深度优先搜索 : "; 
for(int i=0;i<NumNode;i++) 
visited=0; 
for(i=1;i<NumNode;i++) //遍厉孤立节点 
DFS(i,visited); 
delete []visited; 
cout<<endl; 
} 

template<class NameType,class DisType> 
void Graph<NameType,DisType>::DFS(int v,int visited[]) 
{ 
Node<NameType,DisType> *t; 
if(visited[v]==0) 
  cout<<table[v].data<<" "; 
visited[v]=1; 
t=table[v].link; 
while(t!=NULL) 
{ 
if(visited[t->num]==0) 
DFS(t->num,visited); 
t=t->next; 
} 
} 


template<class NameType,class DisType> 
void Graph<NameType,DisType>::BFS() 
{ 
int *visited=new int[NumNode]; 
cout<<"图的广度优先搜索 : "; 
for(int i=0;i<NumNode;i++) 
visited=0; 
for( i=0;i<NumNode;i++) 
  BFS(i,visited); 
} 


template<class NameType,class DisType> 
void Graph<NameType,DisType>::BFS(int v,int visited[]) 
{ 
Queue<int> q; 
int n; 
if(visited[v]==0) 
{ 
visited[v]=1; 
cout<<table[v].data<<" "; 
q.EnQueue(v); 
while(!q.ISEmpty()) 
{ 
n=q.DelQueue(); 
p=table[n].link; 
while(p!=NULL) 
{ 
n=p->num; 
if(visited[n]==0) 
{ 
  cout<<table[n].data<<" "; 
  visited[n]=1; 

} 
p=p->next; 
} 

} 
} 

}
/////////////////////////// 
//   // 
// 排序算法数据结构 Compositor.h   // 
//   // 
////////////////////////// 


#include<iostream.h> 


template<class Type> 
class Compositor 
{ 
public: 
Compositor():sort(NULL){} 
void Creat();   //创建排序数组 
void Bubble(); //冒泡排序   
void Insert(); //插入排序 
//快速排序 
void Quick();   
void QSort(int,int); 
int Partition(int low,int high); 
//归并排序 
void Merge(Type SR[],Type TR[],int i,int m,int n); 
void Msort(Type SR[],Type TR1[],int s,int t); 
  void MergeSort(); 
//选择排序 
void Select(); 
void Print();   //打印排序后的结果 
protected: 
Type *sort; 
int leng; 
}; 

template<class Type> 
void Compositor<Type>::Creat() 
{ 
cout<<"输入你需要排序的数据个数: "; 
cin>>leng; 
while(leng<=0) 
{ 
cout<<"输入数据有误"; 
cin>>leng; 
} 
sort=new Type[leng]; 
cout<<"请输入各数据项："; 
for(int i=0;i<leng;i++) 
cin>>sort; 
}   


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

} 

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

template<class Type> 
void Compositor<Type>::Quick() 
{ 
Creat(); 
QSort(0,leng-1); 
Print(); 
} 

template<class Type> 
void Compositor<Type>::QSort(int s,int t) 
{ 
if(s<t-1) 
{ 
int pivotloc=Partition(s,t); 
QSort(s,pivotloc-1); 
QSort(pivotloc+1,t); 
} 
} 

template<class Type> 
int Compositor<Type>::Partition(int low,int high) 
{ 
  Type pivotkey=sort[low]; 
while(low < high) 
{ 
while(low<high&&sort[high]>=pivotkey) 
--high; 
sort[low++]=sort[high]; 
while(low<high&&sort[low]<=pivotkey) 
++low; 
sort[high--]=sort[low]; 
}   
sort[low]=pivotkey; 
return low; 
} 

template<class Type> 
void Compositor<Type>::MergeSort() 
{ 
Creat(); 
Msort(sort,sort,0,leng-1); 
Print(); 
}