下面讲一下C++代码实现
图类，基于邻接矩阵，不详细的写了 ==
class Graph
{
private:
CArray<DataType,DataType> Vertices;
int Edge[MaxVertices][MaxVertices];
int numOfEdges;
public:
Graph();
~Graph();
void InsertVertex(DataType Vertex);
void InsertEdge(int v1,int v2,int weight);
int GetWeight(int i,int j);
int GetVertices();
DataType GetValue(int i);
};
首先自己写一个简单的“栈类”，由于新增了些方法所以不完全叫栈
template<class T>
class Stack
{
private:
int m_size;
int m_maxsize;
T* data;
public:
Stack();
~Stack();
void push(T data); //压栈
T pop(); //出栈，并返回弹出的元素
T peek(); //查看栈顶元素
bool isEmpty(); //判断是否空
int getSize(); //得到栈的中元素个数
T* getPath(); //返回栈中所有元素
};
template<class T>
Stack<T>::Stack()
{
m_size=0;
m_maxsize=100;
data=new T[m_maxsize];
}
template<class T>
Stack<T>::~Stack()
{
delete []data;
}
template<class T>
T Stack<T>::pop()
{
m_size--;
return data[m_size];
}
template<class T>
void Stack<T>::push(T d)
{
if (m_size==m_maxsize)
{
m_maxsize=2*m_maxsize;
T* new_data=new T[m_maxsize];
for (int i=0;i<m_size;i++)
{
new_data[i]=data[i];
}
delete []data;
data=new_data;
}
data[m_size]=d;
m_size++;
}
template<class T>
T Stack<T>::peek()
{
return data[m_size-1];
}
template<class T>
bool Stack<T>::isEmpty()
{
if (m_size==0)
{
return TRUE;
}
else
{
return FALSE;
}
}
template<class T>
T* Stack<T>::getPath()
{
T* path=new T[m_size];
for (int i=0;i<m_size;i++)
{
path[i]=data[i];
}
return path;
}
template<class T>
int Stack<T>::getSize()
{
return m_size;
}
Vertex类，便于遍历全部的结点
class CVertex
{
private:
int m_num;//保存与该顶点相邻的顶点个数
int *m_nei; //与该顶点相邻的顶点序号
int *m_flag; //与该顶点相邻的顶点是否访问过
bool isin; //该顶点是否入栈
public:
CVertex();
void Initialize(int num,int a[]);
int getOne(); //得到一个与该顶点相邻的顶点
void resetFlag(); //与该顶点相邻的顶点全被标记为未访问
void setIsin(bool);//标记该顶点是否入栈
bool isIn(); //判断该顶点是否入栈
void Reset();//将isin和所有flag置0
~CVertex();
};
CVertex::CVertex()
{
m_num=SIZE;
m_nei=new int[m_num];
m_flag=new int[m_num];
isin=false;
for (int i=0;i<m_num;i++)
{
m_flag[i]=0;
}
}
void CVertex::Initialize(int num,int a[])
{
m_num=num;
for (int i=0;i<m_num;i++)
{
m_nei[i]=a[i];
}
}
CVertex::~CVertex()
{
delete []m_nei;
delete []m_flag;
}
int CVertex::getOne()
{
int i=0;
for (i=0;i<m_num;i++)
{
if (m_flag[i]==0) //判断是否访问过
{
m_flag[i]=1; //表示这个顶点已经被访问，并将其返回
return m_nei[i];
}
}
return -1; //所有顶点都已访问过则返回-1
}
void CVertex::resetFlag()
{
for (int i=0;i<m_num;i++)
{
m_flag[i]=0;
}
}
void CVertex::setIsin(bool a)
{
isin=a;
}
bool CVertex::isIn()
{
return isin;
}
void CVertex::Reset()
{
for (int i=0;i<m_num;i++)
{
m_flag[i]=0;
}
isin=false;
}
