Clist.rar_visual c

#ifndef __ADJ_LIST_GRAPH_H__ #define __ADJ_LIST_GRAPH_H__ #include "lk_list.h" // 线性链表类 #include "adj_list_network_edge.h" // 邻接表无向网边数据类 #include "adj_list_network_vex_node.h" // 邻接表无向网顶点结点类 // 无向网的邻接表类 template <class ElemType, class WeightType> class AdjListUndirNetwork { protected: // 邻接表的数据成员: int vexNum, edgeNum; // 顶点个数和边数 AdjListNetWorkVexNode<ElemType, WeightType> *adjList; // 由顶点数组组成的邻接表 mutable StatusCode *tag; // 指向标志数组的指针 WeightType infinity; // 无穷大 // 辅助函数 void DestroyHelp(); // 销毁无向网,释放无向网点用的空间 int IndexHelp(const LinkList<AdjListNetworkEdge<WeightType> > *la, int v) const; //定位顶点v在邻接链表中的位置 public: // 抽象数据类型方法声明及重载编译系统默认方法声明: AdjListUndirNetwork(ElemType es[], int vertexNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY); // 构造顶点数据为es[],顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网 AdjListUndirNetwork(int vertexNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY); // 构造顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网 ~AdjListUndirNetwork(); // 析构函数 StatusCode GetElem(int v, ElemType &e) const;// 求顶点的元素 StatusCode SetElem(int v, const ElemType &e);// 设置顶点的元素值 WeightType GetInfinity() const; // 返回无穷大 int GetVexNum() const; // 返回顶点个数 int GetEdgeNum() const; // 返回边数个数 int FirstAdjVex(int v) const; // 返回顶点v的第一个邻接点 int NextAdjVex(int v1, int v2) const; // 返回顶点v1的相对于v2的下一个邻接点 void InsertEdge(int v1, int v2, WeightType w); // 插入顶点为v1和v2,权为w的边 void DeleteEdge(int v1, int v2); // 删除顶点为v1和v2的边 WeightType GetWeight(int v1, int v2) const; // 返回顶点为v1和v2的边的权值 void SetWeight(int v1, int v2, WeightType w);// 设置顶点为v1和v2的边的权值 StatusCode GetTag(int v) const; // 返回顶点v的标志 void SetTag(int v, StatusCode val) const; // 设置顶点v的标志为val AdjListUndirNetwork(const AdjListUndirNetwork<ElemType, WeightType> &copy); // 复制构造函数 AdjListUndirNetwork<ElemType, WeightType> &operator =(const AdjListUndirNetwork<ElemType, WeightType> &copy); // 赋值语句重载 }; #ifndef _MSC_VER // 表示非VC // 非VC需要在函数声明时写上参数缺省值 template <class ElemType, class WeightType> void Display(const AdjListUndirNetwork<ElemType, WeightType> &net, bool showVexElem = true); // 显示邻接矩阵无向网 #else // 表示VC // VC不必在函数声明时写上参数缺省值 template <class ElemType, class WeightType> void Display(const AdjListUndirNetwork<ElemType, WeightType> &net, bool showVexElem); // 显示邻接矩阵无向网 #endif // 无向网的邻接表类的实现部分 template <class ElemType, class WeightType> AdjListUndirNetwork<ElemType, WeightType>::AdjListUndirNetwork(ElemType es[], int vertexNum, WeightType infinit) // 操作结果：构造顶点数据为es[],顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网 { if (vertexNum < 0) throw Error("顶点个数不能为负!");// 抛出异常 infinity = infinit; // 无穷大 vexNum = vertexNum; // 顶点数为vertexNum edgeNum = 0; // 边数为0 tag = new StatusCode[vexNum]; // 生成标志数组 int curPos; // 临时变量 for (curPos = 0; curPos < vexNum; curPos++) { // 初始化标志数组 tag[curPos] = UNVISITED; } adjList = new AdjListNetWorkVexNode<ElemType, WeightType>[vexNum];// 生成邻接表 for (curPos = 0; curPos < vexNum; curPos++) { // 初始化顶点数据 adjList[curPos].data = es[curPos]; } } template <class ElemType, class WeightType> AdjListUndirNetwork<ElemType, WeightType>::AdjListUndirNetwork(int vertexNum, WeightType infinit) // 操作结果：构造顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网 { if (vertexNum < 0) throw Error("顶点个数不能为负!");// 抛出异常 infinity = infinit; // 无穷大 vexNum = vertexNum; // 顶点数为vertexNum edgeNum = 0; // 边数为0 tag = new StatusCode[vexNum]; // 生成标志数组 int curPos; // 临时变量 for (curPos = 0; curPos < vexNum; curPos++) { // 初始化标志数组 tag[curPos] = UNVISITED; } adjList = new AdjListNetWorkVexNode<ElemType, WeightType>[vexNum];// 生成邻接表 } template <class ElemType, class WeightType> void AdjListUndirNetwork<ElemType, WeightType>::DestroyHelp() // 操作结果：销毁无向网,释放无向网点用的空间 { delete []tag; // 释放标志 for (int iPos = 0; iPos < vexNum; iPos++) { // 释放链表 if (adjList[iPos].adjLink != NULL) delete adjList[iPos].adjLink; } delete []adjList; // 释放邻接表 } template <class ElemType, class WeightType> AdjListUndirNetwork<ElemType, WeightType>::~AdjListUndirNetwork() // 操作结果：释放邻接表无向网所占用空间 { DestroyHelp(); } template <class ElemType, class WeightType> StatusCode AdjListUndirNetwork<ElemType, WeightType>::GetElem(int v, ElemType &e) const // 操作结果：求顶点v的元素, v的取值范围为0 ≤ v ＜ vexNum, v合法时函数返回 // SUCCESS, 否则函数返回RANGE_ERROR { if (v < 0 || v >= vexNum) { // v范围错 return NOT_PRESENT; // 元素不存在 } else { // v合法 e = adjList[v].data; // 将顶点v的元素值赋给e return ENTRY_FOUND; // 元素存在 } } template <class ElemType, class WeightType> StatusCode AdjListUndirNetwork<ElemType, WeightType>::SetElem(int v, const ElemType &e) // 操作结果：设置顶点的元素值v的取值范围为0 ≤ v ＜ vexNum, v合法时函数返回 // SUCCESS, 否则函数返回RANGE_ERROR { if (v < 0 || v >= vexNum) { // v范围错 return RANGE_ERROR; // 位置错 } else { // v合法 adjList[v].data = e; // 顶点元素 return SUCCESS; // 成功 } } template <class ElemType, class WeightType> WeightType AdjListUndirNetwork<ElemType, WeightType>::GetInfinity() const // 操作结果：返回无穷大 { return infinity; } template <class ElemType, class WeightType> int AdjListUndirNetwork<ElemType, WeightType>::GetVexNum() const // 操作结果：返回顶点个数 { return vexNum; } template <class ElemType, class WeightType> int AdjListUndirNetwork<ElemType, WeightType>::GetEdgeNum() const // 操作结果：返回边数个数 { return edgeNum; } template <class ElemType, class WeightType> int AdjListUndirNetwork<ElemType, WeightType>::FirstAdjVex(int v) const // 操作结果：返回顶点v的第一个邻接点 { if (v < 0 || v >= vexNum) throw Error("v不合法!");// 抛出异常 if (adjList[v].adjLink == NULL) { // 空邻接链表，无邻接点 return -1; } else { // 空邻接链表，存在邻接点 AdjListNetworkEdge<WeightType> tmpEdgeNode; adjList[v].adjLink->GetElem(1, tmpEdgeNode); return tmpEdgeNode.adjVex; } } template <class ElemType, class WeightType> int AdjListUndirNetwork<ElemType, WeightType>::IndexHelp(const LinkList<AdjListNetworkEdge<WeightType> > *la, int v) const // 操作结果：定位顶点v在邻接链表中的位置 { AdjListNetworkEdge<WeightType> tmpEdgeNode; int curPos; curPos = la->GetCurPosition(); la->GetElem(curPos, tmpEdgeNode); // 取得邻接点信息 if (tmpEdgeNode.adjVex == v) return curPos; // v为线性链表的当前位置处 curPos = 1; for (curPos = 1; curPos <= la->Length(); curPos++) { // 循环定定 la->GetElem(curPos, tmpEdgeNode); // 取得边信息 if (tmpEdgeNode.adjVex == v) break; // 定位成功 } return curPos; // curPos = la.Length() + 1 表定失败 } template <class ElemType, class WeightType> int AdjListUndirNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2) const // 操作结果：返回顶点v1的相对于v2的下一个邻接点 { if (v1 < 0 || v1 >= vexNum) throw Error("v1不合法!"); // 抛出异常 if (v2 < 0 || v2 >= vexNum) throw Error("v2不合法!"); // 抛出异常 if (v1 == v2) throw Error("v1不能等于v2!"); // 抛出异常 if (adjList[v1].adjLink == NULL) return -1; // 邻接链表adjList[v1].adjLink,不存在,返回-1 AdjListNetworkEdg