adj_list_network_edge.h

 // 邻接表网边数据类模板

 template <class WeightType>

 class AdjListNetworkEdge

 {

 public:

 // 数据成员:

     int adjVex;                                // 邻接点

     WeightType weight;                        // 权值

 // 构造函数模板:

     AdjListNetworkEdge();                        // 无参数的构造函数模板

     AdjListNetworkEdge(int v, WeightType w);    // 构造邻接点为v，权为w的邻接边

 };

 // 邻接表网边数据类模板的实现部分

 template <class WeightType>

 AdjListNetworkEdge<WeightType>::AdjListNetworkEdge()

 // 操作结果：构造一个空邻接表边结点边——无参构造函数模板

 {

     adjVex = -;

 }

 template <class WeightType>

 AdjListNetworkEdge<WeightType>::AdjListNetworkEdge(int v, WeightType w)

 // 操作结果：构造邻接点为v，权为w的邻接边

 {

     adjVex = v;                                // 邻接点

     weight = w;                                // 权

 }

adj_list_graph_vex_node

 // 邻接表网顶点结点类模板

 template <class ElemType, class WeightType>

 class AdjListNetWorkVexNode

 {

 public:

 // 数据成员:

     ElemType data;                            // 数据元素值

     LinkList<AdjListNetworkEdge<WeightType> > *adjLink;

         // 指向邻接链表的指针

 // 构造函数模板:

     AdjListNetWorkVexNode();                // 无参数的构造函数模板

     AdjListNetWorkVexNode(ElemType item,

         LinkList<AdjListNetworkEdge<WeightType> > *adj = NULL);

         // 构造顶点数据为item,指向邻接链表的指针为adj的结构

 };

 // 邻接表网顶点结点类模板的实现部分

 template <class ElemType, class WeightType>

 AdjListNetWorkVexNode<ElemType, WeightType>::AdjListNetWorkVexNode()

 // 操作结果：构造一个空顶点结点——无参构造函数模板

 {

     adjLink = NULL;                            // 指向邻接链表的指针为空

 }

 template <class ElemType, class WeightType>

 AdjListNetWorkVexNode<ElemType, WeightType>::AdjListNetWorkVexNode(ElemType item,

     LinkList<AdjListNetworkEdge<WeightType> > *adj)

 // 操作结果：构造数据为item,边为eg的顶点

 {

     data = item;                            // 顶点数据

     adjLink = adj;                            // 指向邻接链表的指针

 }

adj_list_undir_graph.h

 #include "adj_list_graph_vex_node.h"            // 邻接表无向图顶点结点类模板

 // 无向图的邻接表类模板

 template <class ElemType>

 class AdjListUndirGraph

 {

 protected:

 // 邻接表的数据成员:

     int vexNum, edgeNum;                        // 顶点个数和边数

     AdjListGraphVexNode<ElemType> *vexTable;    // 顶点表

     mutable StatusCode *tag;                    // 指向标志数组的指针                

 // 辅助函数模板:

     void DestroyHelp();                            // 销毁无向图,释放无向图点用的空间

     int IndexHelp(const LinkList<int> *la, int v) const;

         //定位顶点v在邻接链表中的位置

 public:

 // 抽象数据类型方法声明及重载编译系统默认方法声明:

     AdjListUndirGraph(ElemType es[], int vertexNum = DEFAULT_SIZE);

         // 构造顶点数据为es[],顶点个数为vertexNum,infinit表示无穷大,边数为0的无向图

     AdjListUndirGraph(int vertexNum = DEFAULT_SIZE);

         // 构造顶点个数为vertexNum,infinit表示无穷大,边数为0的无向图

     ~AdjListUndirGraph();                        // 析构函数模板

     StatusCode GetElem(int v, ElemType &e) const;// 求顶点的元素

     StatusCode SetElem(int v, const ElemType &e);// 设置顶点的元素值

     ElemType GetInfility() 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);            // 插入顶点为v1和v2的边

     void DeleteEdge(int v1, int v2);            // 删除顶点为v1和v2的边

     StatusCode GetTag(int v) const;                // 返回顶点v的标志

     void SetTag(int v, StatusCode val) const;    // 设置顶点v的标志为val

     AdjListUndirGraph(const AdjListUndirGraph<ElemType> &copy);    // 复制构造函数模板

     AdjListUndirGraph<ElemType> &operator =(const AdjListUndirGraph<ElemType> &copy); // 重载赋值运算符

 };

 template <class ElemType>

 void Display(const AdjListUndirGraph<ElemType> &g, bool showVexElem);    // 显示邻接矩阵无向图

 // 无向图的邻接表类模板的实现部分

 template <class ElemType>

 AdjListUndirGraph<ElemType>::AdjListUndirGraph(ElemType es[], int vertexNum)

 // 操作结果：构造顶点数为numVex,顶点数据为es[],顶点个数为vertexNum,边数为0的无向图

 {

     if (vertexNum < )    throw Error("顶点个数不能为负!");// 抛出异常

     vexNum = vertexNum;                            // 顶点数为vertexNum

     edgeNum = ;                                // 边数为0

     tag = new StatusCode[vexNum];                // 生成标志数组

     int curPos;                                    // 临时变量

     for (curPos = ; curPos < vexNum; curPos++)

     {    // 初始化标志数组

         tag[curPos] = UNVISITED;

     }

     vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表

     for (curPos = ; curPos < vexNum; curPos++)

     {    // 初始化顶点数据

         vexTable[curPos].data = es[curPos];

     }

 }

 template <class ElemType>

 AdjListUndirGraph<ElemType>::AdjListUndirGraph(int vertexNum)

 // 操作结果：构造顶点数为numVex,顶点个数为vertexNum,边数为0的无向图

 {

     if (vertexNum < )    throw Error("顶点个数不能为负!");// 抛出异常

     vexNum = vertexNum;                            // 顶点数为vertexNum

     edgeNum = ;                                // 边数为0

     tag = new StatusCode[vexNum];                // 生成标志数组

     int curPos;                                    // 临时变量

     for (curPos = ; curPos < vexNum; curPos++)

     {    // 初始化标志数组

         tag[curPos] = UNVISITED;

     }

     vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表

 }

 template <class ElemType>

 void AdjListUndirGraph<ElemType>::DestroyHelp()

 // 操作结果：销毁无向图,释放无向图点用的空间

 {

     delete []tag;                                // 释放标志

     for (int iPos = ; iPos < vexNum; iPos++)

     {    // 释放链表

         if (vexTable[iPos].adjLink != NULL)

             delete vexTable[iPos].adjLink;

     }

     delete []vexTable;                            // 释放邻接表

 }

 template <class ElemType>

 AdjListUndirGraph<ElemType>::~AdjListUndirGraph()

 // 操作结果：释放邻接表无向图所占用空间

 {

     DestroyHelp();

 }

 template <class ElemType>

 StatusCode AdjListUndirGraph<ElemType>::GetElem(int v, ElemType &e) const

 // 操作结果：求顶点v的元素, v的取值范围为0 ≤ v ＜ vexNum, v合法时返回

 //    SUCCESS, 否则返回RANGE_ERROR

 {

     if (v <  || v >= vexNum)

     {    // v范围错

         return NOT_PRESENT;            // 元素不存在

     }

     else

     {    // v合法

         e = vexTable[v].data;        // 将顶点v的元素值赋给e

         return ENTRY_FOUND;            // 元素存在

     }

 }    

 template <class ElemType>

 StatusCode AdjListUndirGraph<ElemType>::SetElem(int v, const ElemType &e)

 // 操作结果：设置顶点的元素值v的取值范围为0 ≤ v ＜ vexNum, v合法时返回

 //    SUCCESS, 否则返回RANGE_ERROR

 {

     if (v <  || v >= vexNum)

     {    // v范围错

         return RANGE_ERROR;            // 位置错

     }

     else

     {    // v合法

         vexTable[v].data = e;        // 顶点元素

         return SUCCESS;                // 成功

     }

 }

 template <class ElemType>

 int AdjListUndirGraph<ElemType>::GetVexNum() const

 // 操作结果：返回顶点个数

 {

     return vexNum;

 }

 template <class ElemType>

 int AdjListUndirGraph<ElemType>::GetEdgeNum() const

 // 操作结果：返回边数个数

 {

     return edgeNum;

 }         

 template <class ElemType>

 int AdjListUndirGraph<ElemType>::FirstAdjVex(int v) const

 // 操作结果：返回顶点v的第一个邻接点

 {

     if (v <  || v >= vexNum) throw Error("v不合法!");// 抛出异常

     if (vexTable[v].adjLink == NULL)

     {    // 空邻接链表，无邻接点

         return -;

     }

     else

     {    // 非空邻接链表，存在邻接点

         int adjVex;

         vexTable[v].adjLink->GetElem(, adjVex);

         return adjVex;

     }

 }

 template <class ElemType>

 int AdjListUndirGraph<ElemType>::IndexHelp(const LinkList<int> *la, int v) const

 // 操作结果：定位顶点v在邻接链表中的位置

 {

     int curPos, adjVex;

     curPos = la->GetCurPosition();

     la->GetElem(curPos, adjVex);                    // 取得邻接点信息

     if (adjVex == v) return curPos;                    // v为线性链表的当前位置处 

     curPos = ;

     for (curPos = ; curPos <= la->Length(); curPos++)

     {    // 循环定定

         la->GetElem(curPos, adjVex);                // 取得边信息

         if (adjVex == v) break;                        // 定位成功

     }

     return curPos;                                    // curPos = la.Length() + 1 表定失败

 }

 template <class ElemType>

 int AdjListUndirGraph<ElemType>::NextAdjVex(int v1, int v2) const

 // 操作结果：返回顶点v1的相对于v2的下一个邻接点

 {

     if (v1 <  || v1 >= vexNum) throw Error("v1不合法!");    // 抛出异常

     if (v2 <  || v2 >= vexNum) throw Error("v2不合法!");    // 抛出异常

     if (v1 == v2) throw Error("v1不能等于v2!");                // 抛出异常

     if (vexTable[v1].adjLink == NULL) return -;            // 邻接链表vexTable[v1].adjList为空,返回-1

     int curPos = IndexHelp(vexTable[v1].adjLink, v2);        // 取出v2在邻接链表中的位置

     if (curPos < vexTable[v1].adjLink->Length())

     {    // 存在下1个邻接点

         int adjVex;

         vexTable[v1].adjLink->GetElem(curPos + , adjVex);    // 取出后继

         return adjVex;

     }

     else

     {    // 不存在下一个邻接点

         return -;

     }

 }

 template <class ElemType>

 void AdjListUndirGraph<ElemType>::InsertEdge(int v1, int v2)

 // 操作结果：插入顶点为v1和v2的边

 {

     if (v1 <  || v1 >= vexNum) throw Error("v1不合法!");    // 抛出异常

     if (v2 <  || v2 >= vexNum) throw Error("v2不合法!");    // 抛出异常

     if (v1 == v2) throw Error("v1不能等于v2!");                // 抛出异常

     // 插入<v1, v2>

     if (vexTable[v1].adjLink == NULL)

     {    // 空链表

         vexTable[v1].adjLink = new LinkList<int>;

     }

     int curPos = IndexHelp(vexTable[v1].adjLink, v2);            // 取出v2在邻接链表中的位置

     if (curPos > vexTable[v1].adjLink->Length())

     {    // 不存在边<v1, v2>

         vexTable[v1].adjLink->Insert(curPos, v2);                // 插入边

         edgeNum++;                                            // 边数自增1

     }

     // 插入<v2, v1>

     if (vexTable[v2].adjLink == NULL)

     {    // 空链表

         vexTable[v2].adjLink = new LinkList<int>;

     }

     curPos = IndexHelp(vexTable[v2].adjLink, v1);                // 取出v1在邻接链表中的位置

     if (curPos > vexTable[v2].adjLink->Length())

     {    // 不存在边<v1, v2>

         vexTable[v2].adjLink->Insert(curPos, v1);                // 插入边

     }

 }

 template <class ElemType>

 void AdjListUndirGraph<ElemType>::DeleteEdge(int v1, int v2)

 // 操作结果：删除顶点为v1和v2的边

 {

     if (v1 <  || v1 >= vexNum) throw Error("v1不合法!");    // 抛出异常

     if (v2 <  || v2 >= vexNum) throw Error("v2不合法!");    // 抛出异常

     if (v1 == v2) throw Error("v1不能等于v2!");                // 抛出异常

     int curPos = IndexHelp(vexTable[v1].adjLink, v2);    // 取出v2在邻接链表中的位置

     if (curPos <= vexTable[v1].adjLink->Length())

     {    // 存在边<v1, v2>

         vexTable[v1].adjLink->Delete(curPos, v2);        // 删除<v1, v2>

          edgeNum--;                                    // 边数自减1

     }

     curPos = IndexHelp(vexTable[v2].adjLink, v1);        // 取出v1在邻接链表中的位置

     if (curPos <= vexTable[v2].adjLink->Length())

     {    // 存在边<v2, v1>

         vexTable[v2].adjLink->Delete(curPos, v1);        // 删除<v2, v1>

     }

 }

 template <class ElemType>

 StatusCode AdjListUndirGraph<ElemType>::GetTag(int v) const

 // 操作结果：返回顶点v的标志

 {

     if (v <  || v >= vexNum) throw Error("v不合法!");        // 抛出异常

     return tag[v];

 }

 template <class ElemType>

 void AdjListUndirGraph<ElemType>::SetTag(int v, StatusCode val) const

 // 操作结果：设置顶点v的标志为val

 {

     if (v <  || v >= vexNum) throw Error("v不合法!");        // 抛出异常

     tag[v] = val;

 }

 template <class ElemType>

 AdjListUndirGraph<ElemType>::AdjListUndirGraph(const AdjListUndirGraph<ElemType> &copy)

 // 操作结果：由无向图的邻接矩阵copy构造新无向图的邻接矩阵copy——复制构造函数模板

 {

     int curPos;                                    // 临时变量

     vexNum = copy.vexNum;                        // 复制顶点数

     edgeNum = copy.edgeNum;                        // 复制边数

     tag = new StatusCode[vexNum];                // 生成标志数组

     for (curPos = ; curPos < vexNum; curPos++)

     {    // 复制标志数组

         tag[curPos] = copy.tag[curPos];

     }

     vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表

     for (curPos = ; curPos < vexNum; curPos++)

     {    // 复制邻接链表

         vexTable[curPos].data = copy.vexTable[curPos].data;    // 复制顶点数据

         vexTable[curPos].adjLink = new LinkList<int>(*copy.vexTable[curPos].adjLink);

     }

 }

 template <class ElemType>

 AdjListUndirGraph<ElemType> &AdjListUndirGraph<ElemType>::operator =(const AdjListUndirGraph<ElemType> &copy)

 // 操作结果：将无向图的邻接矩阵copy赋值给当前无向图的邻接矩阵——重载赋值运算符

 {

     if (&copy != this)

     {

         DestroyHelp();                                // 释放当前无向图占用空间

         int curPos;                                    // 临时变量

         vexNum = copy.vexNum;                        // 复制顶点数

         edgeNum = copy.edgeNum;                        // 复制边数

         tag = new StatusCode[vexNum];                // 生成标志数组

         for (curPos = ; curPos < vexNum; curPos++)

         {    // 复制标志数组

             tag[curPos] = copy.tag[curPos];

         }

         vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表

         for (curPos = ; curPos < vexNum; curPos++)

         {    // 复制邻接链表

             vexTable[curPos].data = copy.vexTable[curPos].data;    // 复制顶点数据

             vexTable[curPos].adjLink = new LinkList<int>(*copy.vexTable[curPos].adjLink);

         }

     }

     return *this;

 }

 template <class ElemType>

 void Display(const AdjListUndirGraph<ElemType> &g, bool showVexElem = true)

 // 操作结果: 显示邻接矩阵无向图

 {

     for (int v = ; v < g.GetVexNum(); v++)

     {    // 显示第v个邻接链表

         cout << endl << v << "  ";                            // 显示顶点号

         if (showVexElem)

         {    // 显示顶点元素

             ElemType e;                                        // 数据元素

             g.GetElem(v, e);                                // 取出元素值

             cout << e << "  ";                                // 显示顶点元素

         }

         for (int u = g.FirstAdjVex(v); u != -; u = g.NextAdjVex(v, u))

         {    // 显示第v个邻接链表的一个结点（表示一个邻接点）

             cout << "-->" << u;

         }

         cout << endl;

     }

 }

最新文章

  1. $_SERVER 的用法
  2. Chapter 1: Design the application architecture
  3. Genymotion关于【启动后player.exe已停止运行】解决方案总结
  4. NYOJ之喷水装置（一）
  5. Lucene.net 全文检索 盘古分词
  6. 第一个app.总结
  7. POJ 1185 炮兵阵地（状压DP）
  8. 移动设备3G网站制作的detail
  9. VMwareWorkstation10安装OS_X_Mavericks10.9.2图文详细教程
  10. OC加强-day06
  11. ViewPager中使用自定义的ListView实例
  12. Android学习笔记（三）Application类简介
  13. Android基本组件-Activity
  14. a标签伪类的顺序
  15. WinForm - 格式化DataGridView单元格数据
  16. Apriori算法-位运算-C语言
  17. iOS热更新技术被苹果官方警告？涉及到RN、Weex、JSPatch！！！
  18. NET中小型企业级项目开发架构系列（一）
  19. vue1.0与vue2.0对于v-for的使用的区别
  20. Java实现视频转码或压缩demo.

热门文章

  1. 矩阵的f范数及其求偏导法则
  2. 【LeetCode】152. Maximum Product Subarray
  3. JDBC数据库增、删、改、查方法实现类
  4. Octopus——excel导入导出工具
  5. Django学习（八）---修改文章和添加文章
  6. css 子div自适应父div高度
  7. docker~Dockerfile方式生成控制台和Api项目的镜像
  8. ES6中的箭头函数
  9. 学会用requirejs，5分钟足矣
  10. Golang 基于libpcap/winpcap的底层网络编程——gopacket安装