adj_list_network_edge.h
1 // 邻接表网边数据类模板 2 template <class WeightType> 3 class AdjListNetworkEdge 4 { 5 public: 6 // 数据成员: 7 int adjVex; // 邻接点 8 WeightType weight; // 权值 9 10 // 构造函数模板: 11 AdjListNetworkEdge(); // 无参数的构造函数模板 12 AdjListNetworkEdge(int v, WeightType w); // 构造邻接点为v，权为w的邻接边 13 }; 14 15 // 邻接表网边数据类模板的实现部分 16 template <class WeightType> 17 AdjListNetworkEdge<WeightType>::AdjListNetworkEdge() 18 // 操作结果：构造一个空邻接表边结点边——无参构造函数模板 19 { 20 adjVex = -1; 21 } 22 23 template <class WeightType> 24 AdjListNetworkEdge<WeightType>::AdjListNetworkEdge(int v, WeightType w) 25 // 操作结果：构造邻接点为v，权为w的邻接边 26 { 27 adjVex = v; // 邻接点 28 weight = w; // 权 29 }
adj_list_graph_vex_node
1 // 邻接表网顶点结点类模板 2 template <class ElemType, class WeightType> 3 class AdjListNetWorkVexNode 4 { 5 public: 6 // 数据成员: 7 ElemType data; // 数据元素值 8 LinkList<AdjListNetworkEdge<WeightType> > *adjLink; 9 // 指向邻接链表的指针 10 11 // 构造函数模板: 12 AdjListNetWorkVexNode(); // 无参数的构造函数模板 13 AdjListNetWorkVexNode(ElemType item, 14 LinkList<AdjListNetworkEdge<WeightType> > *adj = NULL); 15 // 构造顶点数据为item,指向邻接链表的指针为adj的结构 16 }; 17 18 // 邻接表网顶点结点类模板的实现部分 19 template <class ElemType, class WeightType> 20 AdjListNetWorkVexNode<ElemType, WeightType>::AdjListNetWorkVexNode() 21 // 操作结果：构造一个空顶点结点——无参构造函数模板 22 { 23 adjLink = NULL; // 指向邻接链表的指针为空 24 } 25 26 template <class ElemType, class WeightType> 27 AdjListNetWorkVexNode<ElemType, WeightType>::AdjListNetWorkVexNode(ElemType item, 28 LinkList<AdjListNetworkEdge<WeightType> > *adj) 29 // 操作结果：构造数据为item,边为eg的顶点 30 { 31 data = item; // 顶点数据 32 adjLink = adj; // 指向邻接链表的指针 33 }
adj_list_undir_graph.h
1 #include "adj_list_graph_vex_node.h" // 邻接表无向图顶点结点类模板 2 3 // 无向图的邻接表类模板 4 template <class ElemType> 5 class AdjListUndirGraph 6 { 7 protected: 8 // 邻接表的数据成员: 9 int vexNum, edgeNum; // 顶点个数和边数 10 AdjListGraphVexNode<ElemType> *vexTable; // 顶点表 11 mutable StatusCode *tag; // 指向标志数组的指针 12 13 // 辅助函数模板: 14 void DestroyHelp(); // 销毁无向图,释放无向图点用的空间 15 int IndexHelp(const LinkList<int> *la, int v) const; 16 //定位顶点v在邻接链表中的位置 17 18 public: 19 // 抽象数据类型方法声明及重载编译系统默认方法声明: 20 AdjListUndirGraph(ElemType es[], int vertexNum = DEFAULT_SIZE); 21 // 构造顶点数据为es[],顶点个数为vertexNum,infinit表示无穷大,边数为0的无向图 22 AdjListUndirGraph(int vertexNum = DEFAULT_SIZE); 23 // 构造顶点个数为vertexNum,infinit表示无穷大,边数为0的无向图 24 ~AdjListUndirGraph(); // 析构函数模板 25 StatusCode GetElem(int v, ElemType &e) const;// 求顶点的元素 26 StatusCode SetElem(int v, const ElemType &e);// 设置顶点的元素值 27 ElemType GetInfility() const; // 返回无穷大 28 int GetVexNum() const; // 返回顶点个数 29 int GetEdgeNum() const; // 返回边数个数 30 int FirstAdjVex(int v) const; // 返回顶点v的第一个邻接点 31 int NextAdjVex(int v1, int v2) const; // 返回顶点v1的相对于v2的下一个邻接点 32 void InsertEdge(int v1, int v2); // 插入顶点为v1和v2的边 33 void DeleteEdge(int v1, int v2); // 删除顶点为v1和v2的边 34 StatusCode GetTag(int v) const; // 返回顶点v的标志 35 void SetTag(int v, StatusCode val) const; // 设置顶点v的标志为val 36 AdjListUndirGraph(const AdjListUndirGraph<ElemType> ©); // 复制构造函数模板 37 AdjListUndirGraph<ElemType> &operator =(const AdjListUndirGraph<ElemType> ©); // 重载赋值运算符 38 }; 39 40 template <class ElemType> 41 void Display(const AdjListUndirGraph<ElemType> &g, bool showVexElem); // 显示邻接矩阵无向图 42 43 // 无向图的邻接表类模板的实现部分 44 template <class ElemType> 45 AdjListUndirGraph<ElemType>::AdjListUndirGraph(ElemType es[], int vertexNum) 46 // 操作结果：构造顶点数为numVex,顶点数据为es[],顶点个数为vertexNum,边数为0的无向图 47 { 48 if (vertexNum < 0) throw Error("顶点个数不能为负!");// 抛出异常 49 50 vexNum = vertexNum; // 顶点数为vertexNum 51 edgeNum = 0; // 边数为0 52 53 tag = new StatusCode[vexNum]; // 生成标志数组 54 int curPos; // 临时变量 55 for (curPos = 0; curPos < vexNum; curPos++) 56 { // 初始化标志数组 57 tag[curPos] = UNVISITED; 58 } 59 60 vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表 61 for (curPos = 0; curPos < vexNum; curPos++) 62 { // 初始化顶点数据 63 vexTable[curPos].data = es[curPos]; 64 } 65 } 66 67 template <class ElemType> 68 AdjListUndirGraph<ElemType>::AdjListUndirGraph(int vertexNum) 69 // 操作结果：构造顶点数为numVex,顶点个数为vertexNum,边数为0的无向图 70 { 71 if (vertexNum < 0) throw Error("顶点个数不能为负!");// 抛出异常 72 73 vexNum = vertexNum; // 顶点数为vertexNum 74 edgeNum = 0; // 边数为0 75 76 tag = new StatusCode[vexNum]; // 生成标志数组 77 int curPos; // 临时变量 78 for (curPos = 0; curPos < vexNum; curPos++) 79 { // 初始化标志数组 80 tag[curPos] = UNVISITED; 81 } 82 83 vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表 84 } 85 86 template <class ElemType> 87 void AdjListUndirGraph<ElemType>::DestroyHelp() 88 // 操作结果：销毁无向图,释放无向图点用的空间 89 { 90 delete []tag; // 释放标志 91 for (int iPos = 0; iPos < vexNum; iPos++) 92 { // 释放链表 93 if (vexTable[iPos].adjLink != NULL) 94 delete vexTable[iPos].adjLink; 95 } 96 delete []vexTable; // 释放邻接表 97 } 98 99 template <class ElemType> 100 AdjListUndirGraph<ElemType>::~AdjListUndirGraph() 101 // 操作结果：释放邻接表无向图所占用空间 102 { 103 DestroyHelp(); 104 } 105 106 template <class ElemType> 107 StatusCode AdjListUndirGraph<ElemType>::GetElem(int v, ElemType &e) const 108 // 操作结果：求顶点v的元素, v的取值范围为0 ≤ v ＜ vexNum, v合法时返回 109 // SUCCESS, 否则返回RANGE_ERROR 110 { 111 if (v < 0 || v >= vexNum) 112 { // v范围错 113 return NOT_PRESENT; // 元素不存在 114 } 115 else 116 { // v合法 117 e = vexTable[v].data; // 将顶点v的元素值赋给e 118 return ENTRY_FOUND; // 元素存在 119 } 120 } 121 122 template <class ElemType> 123 StatusCode AdjListUndirGraph<ElemType>::SetElem(int v, const ElemType &e) 124 // 操作结果：设置顶点的元素值v的取值范围为0 ≤ v ＜ vexNum, v合法时返回 125 // SUCCESS, 否则返回RANGE_ERROR 126 { 127 if (v < 0 || v >= vexNum) 128 { // v范围错 129 return RANGE_ERROR; // 位置错 130 } 131 else 132 { // v合法 133 vexTable[v].data = e; // 顶点元素 134 return SUCCESS; // 成功 135 } 136 } 137 138 template <class ElemType> 139 int AdjListUndirGraph<ElemType>::GetVexNum() const 140 // 操作结果：返回顶点个数 141 { 142 return vexNum; 143 } 144 145 template <class ElemType> 146 int AdjListUndirGraph<ElemType>::GetEdgeNum() const 147 // 操作结果：返回边数个数 148 { 149 return edgeNum; 150 } 151 152 template <class ElemType> 153 int AdjListUndirGraph<ElemType>::FirstAdjVex(int v) const 154 // 操作结果：返回顶点v的第一个邻接点 155 { 156 if (v < 0 || v >= vexNum) throw Error("v不合法!");// 抛出异常 157 158 if (vexTable[v].adjLink == NULL) 159 { // 空邻接链表，无邻接点 160 return -1; 161 } 162 else 163 { // 非空邻接链表，存在邻接点 164 int adjVex; 165 vexTable[v].adjLink->GetElem(1, adjVex); 166 return adjVex; 167 } 168 } 169 170 template <class ElemType> 171 int AdjListUndirGraph<ElemType>::IndexHelp(const LinkList<int> *la, int v) const 172 // 操作结果：定位顶点v在邻接链表中的位置 173 { 174 int curPos, adjVex; 175 curPos = la->GetCurPosition(); 176 177 la->GetElem(curPos, adjVex); // 取得邻接点信息 178 if (adjVex == v) return curPos; // v为线性链表的当前位置处 179 180 curPos = 1; 181 for (curPos = 1; curPos <= la->Length(); curPos++) 182 { // 循环定定 183 la->GetElem(curPos, adjVex); // 取得边信息 184 if (adjVex == v) break; // 定位成功 185 } 186 187 return curPos; // curPos = la.Length() + 1 表定失败 188 } 189 190 template <class ElemType> 191 int AdjListUndirGraph<ElemType>::NextAdjVex(int v1, int v2) const 192 // 操作结果：返回顶点v1的相对于v2的下一个邻接点 193 { 194 if (v1 < 0 || v1 >= vexNum) throw Error("v1不合法!"); // 抛出异常 195 if (v2 < 0 || v2 >= vexNum) throw Error("v2不合法!"); // 抛出异常 196 if (v1 == v2) throw Error("v1不能等于v2!"); // 抛出异常 197 198 if (vexTable[v1].adjLink == NULL) return -1; // 邻接链表vexTable[v1].adjList为空,返回-1 199 200 int curPos = IndexHelp(vexTable[v1].adjLink, v2); // 取出v2在邻接链表中的位置 201 if (curPos < vexTable[v1].adjLink->Length()) 202 { // 存在下1个邻接点 203 int adjVex; 204 vexTable[v1].adjLink->GetElem(curPos + 1, adjVex); // 取出后继 205 return adjVex; 206 } 207 else 208 { // 不存在下一个邻接点 209 return -1; 210 } 211 } 212 213 template <class ElemType> 214 void AdjListUndirGraph<ElemType>::InsertEdge(int v1, int v2) 215 // 操作结果：插入顶点为v1和v2的边 216 { 217 if (v1 < 0 || v1 >= vexNum) throw Error("v1不合法!"); // 抛出异常 218 if (v2 < 0 || v2 >= vexNum) throw Error("v2不合法!"); // 抛出异常 219 if (v1 == v2) throw Error("v1不能等于v2!"); // 抛出异常 220 221 // 插入<v1, v2> 222 if (vexTable[v1].adjLink == NULL) 223 { // 空链表 224 vexTable[v1].adjLink = new LinkList<int>; 225 } 226 227 int curPos = IndexHelp(vexTable[v1].adjLink, v2); // 取出v2在邻接链表中的位置 228 if (curPos > vexTable[v1].adjLink->Length()) 229 { // 不存在边<v1, v2> 230 vexTable[v1].adjLink->Insert(curPos, v2); // 插入边 231 edgeNum++; // 边数自增1 232 } 233 234 // 插入<v2, v1> 235 if (vexTable[v2].adjLink == NULL) 236 { // 空链表 237 vexTable[v2].adjLink = new LinkList<int>; 238 } 239 240 curPos = IndexHelp(vexTable[v2].adjLink, v1); // 取出v1在邻接链表中的位置 241 if (curPos > vexTable[v2].adjLink->Length()) 242 { // 不存在边<v1, v2> 243 vexTable[v2].adjLink->Insert(curPos, v1); // 插入边 244 } 245 } 246 247 template <class ElemType> 248 void AdjListUndirGraph<ElemType>::DeleteEdge(int v1, int v2) 249 // 操作结果：删除顶点为v1和v2的边 250 { 251 if (v1 < 0 || v1 >= vexNum) throw Error("v1不合法!"); // 抛出异常 252 if (v2 < 0 || v2 >= vexNum) throw Error("v2不合法!"); // 抛出异常 253 if (v1 == v2) throw Error("v1不能等于v2!"); // 抛出异常 254 255 int curPos = IndexHelp(vexTable[v1].adjLink, v2); // 取出v2在邻接链表中的位置 256 if (curPos <= vexTable[v1].adjLink->Length()) 257 { // 存在边<v1, v2> 258 vexTable[v1].adjLink->Delete(curPos, v2); // 删除<v1, v2> 259 edgeNum--; // 边数自减1 260 } 261 262 curPos = IndexHelp(vexTable[v2].adjLink, v1); // 取出v1在邻接链表中的位置 263 if (curPos <= vexTable[v2].adjLink->Length()) 264 { // 存在边<v2, v1> 265 vexTable[v2].adjLink->Delete(curPos, v1); // 删除<v2, v1> 266 } 267 } 268 269 template <class ElemType> 270 StatusCode AdjListUndirGraph<ElemType>::GetTag(int v) const 271 // 操作结果：返回顶点v的标志 272 { 273 if (v < 0 || v >= vexNum) throw Error("v不合法!"); // 抛出异常 274 275 return tag[v]; 276 } 277 278 template <class ElemType> 279 void AdjListUndirGraph<ElemType>::SetTag(int v, StatusCode val) const 280 // 操作结果：设置顶点v的标志为val 281 { 282 if (v < 0 || v >= vexNum) throw Error("v不合法!"); // 抛出异常 283 284 tag[v] = val; 285 } 286 287 template <class ElemType> 288 AdjListUndirGraph<ElemType>::AdjListUndirGraph(const AdjListUndirGraph<ElemType> ©) 289 // 操作结果：由无向图的邻接矩阵copy构造新无向图的邻接矩阵copy——复制构造函数模板 290 { 291 int curPos; // 临时变量 292 vexNum = copy.vexNum; // 复制顶点数 293 edgeNum = copy.edgeNum; // 复制边数 294 295 tag = new StatusCode[vexNum]; // 生成标志数组 296 for (curPos = 0; curPos < vexNum; curPos++) 297 { // 复制标志数组 298 tag[curPos] = copy.tag[curPos]; 299 } 300 301 vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表 302 for (curPos = 0; curPos < vexNum; curPos++) 303 { // 复制邻接链表 304 vexTable[curPos].data = copy.vexTable[curPos].data; // 复制顶点数据 305 vexTable[curPos].adjLink = new LinkList<int>(*copy.vexTable[curPos].adjLink); 306 } 307 } 308 309 template <class ElemType> 310 AdjListUndirGraph<ElemType> &AdjListUndirGraph<ElemType>::operator =(const AdjListUndirGraph<ElemType> ©) 311 // 操作结果：将无向图的邻接矩阵copy赋值给当前无向图的邻接矩阵——重载赋值运算符 312 { 313 if (© != this) 314 { 315 DestroyHelp(); // 释放当前无向图占用空间 316 317 int curPos; // 临时变量 318 vexNum = copy.vexNum; // 复制顶点数 319 edgeNum = copy.edgeNum; // 复制边数 320 321 tag = new StatusCode[vexNum]; // 生成标志数组 322 for (curPos = 0; curPos < vexNum; curPos++) 323 { // 复制标志数组 324 tag[curPos] = copy.tag[curPos]; 325 } 326 327 vexTable = new AdjListGraphVexNode<ElemType>[vexNum];// 生成邻接表 328 for (curPos = 0; curPos < vexNum; curPos++) 329 { // 复制邻接链表 330 vexTable[curPos].data = copy.vexTable[curPos].data; // 复制顶点数据 331 vexTable[curPos].adjLink = new LinkList<int>(*copy.vexTable[curPos].adjLink); 332 } 333 } 334 return *this; 335 } 336 337 template <class ElemType> 338 void Display(const AdjListUndirGraph<ElemType> &g, bool showVexElem = true) 339 // 操作结果: 显示邻接矩阵无向图 340 { 341 for (int v = 0; v < g.GetVexNum(); v++) 342 { // 显示第v个邻接链表 343 cout << endl << v << " "; // 显示顶点号 344 if (showVexElem) 345 { // 显示顶点元素 346 ElemType e; // 数据元素 347 g.GetElem(v, e); // 取出元素值 348 cout << e << " "; // 显示顶点元素 349 } 350 351 for (int u = g.FirstAdjVex(v); u != -1; u = g.NextAdjVex(v, u)) 352 { // 显示第v个邻接链表的一个结点（表示一个邻接点） 353 cout << "-->" << u; 354 } 355 cout << endl; 356 } 357 }