51y0qrur.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[i].data;
 table[i].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[i].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[i]=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[i]=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[i];
}


template<class Type>
void Compositor<Type>::Insert()
{
Creat();
Type temp;
   for(int i=1;i<leng;i++)
 {
  if(sort[i]<sort[i-1])
  {
  temp=sort[i];
  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();
}


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[i]<=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[i];
  sort[i]=temp;
 }
}
Print();
}

template<class Type>
void Compositor<Type>::Print()
{
cout<<"排序结果为: ";
for(int i=0;i<leng;i++)
 cout<<sort[i]<<" ";
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')