设为首页 加入收藏

TOP

数据结构与算法 - 图的邻接表表示法类的C++实现(二)
2016-04-28 13:25:50 来源: 作者: 【 】 浏览:599
Tags:数据结构 算法 邻接 表示 实现

***************** 函数名称:print 功能描述:将图的信息以邻接表的形式输出到标准输出 参数列表:无 返回结果:无 *************************************************/ void Graph::print() { cout << "******************************************************************" << endl; //for(int i = 0 ; i < MAX_VERTEX_NUM; ++i){ for(int i = 0 ; i < vertex_num; ++i){ if(graph_list[i].begin() != graph_list[i].end()){ cout << i << "-->"; for(list ::iterator it = graph_list[i].begin(); it != graph_list[i].end(); ++it){ cout << (*it).vertex << "(边号:" << (*it).edge_num << ",权重:" << (*it).weight << ")-->"; } cout << "NULL" << endl; } } cout << "******************************************************************" << endl; } /************************************************* 函数名称:get_graph_value 功能描述:将图的每一条边的信息保存到一个数组中 参数列表: graph:指向图信息的二维数组 columns:图的第几条边 返回结果:无 *************************************************/ vector Graph::get_graph_value(char* graph[], int columns) { vector v; char buff[20]; int i = 0, j = 0, val; memset(buff, 0, 20); while((graph[columns][i] != '\n') && (graph[columns][i] != '\0')){ if(graph[columns][i] != ','){ buff[j] = graph[columns][i]; j++; } else{ j = 0; val = atoi(buff); v.push_back(val); memset(buff, 0, 20); } i++; } val = atoi(buff); v.push_back(val); return v; } /************************************************* 函数名称:addEdge 功能描述:将图的每一条边的信息加入图的邻接表中 参数列表:graph:指向图信息的二维数组 columns:图的第几条边 返回结果:无 *************************************************/ void Graph::addEdge(char* graph[], int columns) { Node node; vector v = get_graph_value(graph, columns); node.edge_num = v[0]; node.src = v[1]; node.vertex = v[2]; node.weight = v[3]; if(node.vertex > vertex_num) vertex_num = node.vertex; //要考虑重复的边,但是边的权重不一样 for(list ::iterator it = graph_list[node.src].begin(); it != graph_list[node.src].end(); ++it){ if((*it).vertex == node.vertex){ if((*it).weight > node.weight){ (*it).weight = node.weight; } return; } } graph_list[node.src].push_back(node); } /************************************************* 函数名称:构造函数 功能描述:以邻接表的形式保存图的信息,并保存必须经过的顶点 参数列表:graph:指向图信息的二维数组 edgenum:图的边的个数 返回结果:无 *************************************************/ Graph::Graph(char* graph[], int edgenum) { edge_num = edgenum; vertex_num = 0; graph_list = new list [MAX_VERTEX_NUM+1]; for(int i = 0; i < edgenum; ++i){ addEdge(graph, i); } vertex_num++; } /************************************************* 函数名称:析构函数 功能描述:释放动态分配的内存 参数列表:无 返回结果:无 *************************************************/ Graph::~Graph() { delete[] graph_list; } #endif

测试函数的源代码:

#include 
                        
                         
#include 
                         
                           #include 
                          
                            #include 
                           
                             #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #include 
                                 
                                   #include "graph.h" #define MAX_LINE_LEN 4000 int read_file(char ** const buff, const unsigned int spec, const char * const filename); void release_buff(char ** const buff, const int valid_item_num); int main(int argc, char *argv[]) { char *topo[5000]; int edge_num; char *demand; int demand_num; char *topo_file = argv[1]; edge_num = read_file(topo, 5000, topo_file); if (edge_num == 0) { printf("Please input valid topo file.\n"); return -1; } Graph G(topo, edge_num);//创建一个图对象G G.print();//以邻接表的形式打印图信息 release_buff(topo, edge_num); return 0; } /**************************************************************** * 函数名称:read_file * 功能描述: 读取文件中的图的数据信息 * 参数列表: buff是将文件读取的图信息保存到buff指向的二维数组中 * spec是文件中图最大允许的边的个数 * filename是要打开的图文件 * 返回结果:无 *****************************************************************/ int read_file(char ** const buff, const unsigned int spec, const char * const filename) { FILE *fp = fopen(filename, "r"); if (fp == NULL) { printf("Fail to open file %s, %s.\n", filename, strerror(errno)); return 0; } printf("Open file %s OK.\n", filename); char line[MAX_LINE_LEN + 2]; unsigned int cnt = 0; while ((cnt < spec) && !feof(fp)) { line[0] = 0; fgets(line, MAX_LINE_LEN + 2, fp); if (line[0] == 0) continue; buff[cnt] = (char *)malloc(MAX_LINE_LEN + 2); strncpy(buff[cnt], line, MAX_LINE_LEN + 2 - 1); buff[cnt][4001] = 0; cnt++; } fclose(fp); printf("There are %d lines in file %s.\n", cnt, filename); return cnt; } /**************************************************************** * 函数名称:release_buff * 功能描述: 释放刚才读取的文件中的图的数据信息 * 参数列表: buff是指向文件读取的图信息 * valid_item_num是指图中边的个数 * 返回结果:void *****************************************************************/ void release_buff(char ** const buff, const int valid_item_num) { for (int i = 0; i < valid_item_num; i++) free(buff[i]); } 
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        

测试用例0:

0,0,1,1
1,0,2,2
2,0,3,1
3,2,1,3
4,3,1,1
5,2,3,1
6,3,2,1
7,3,0,1

测试用例1:

0,0,13,15
1,0,8,17
2,0,19,1
3,0,4,8
4,1,0,4
5,2,9,19
6,2,15,8
7,3,0,14
8,3,11,12
9,4,1,15
10,4,5,17
11,5,8,18
12,5,9,14
13,5,6,2
14,6,17,4
15,7,13,1
16,7,16,19
17,8,6,1
18,8,12,17
19,9,14,11
20,10,12,1
21,11,7,12
22,11,4,7
23,12,14,5
24,13,17,12
25,13,4,2
26,14,19,9
27,15,10,14
28,15,18,
首页 上一页 1 2 3 下一页 尾页 2/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇浅谈c++资源管理以及对[STL]智能.. 下一篇OpenCV实践之路――行人检测

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目