从C++中的文件输入输入

Question

我试图实现Prim的算法。我正在接受来自文件的输入，如下所示。

3 3 // Number of vertices and edges 
1 2 3 // edge 1 edge 2 cost 
2 3 4 // edge 2 edge 3 cost 
1 3 4 // edge 1 edge 3 cost 

我创建一个成本矩阵如下。最初，成本矩阵中的每个权重都是无穷大（本例中为9999）。

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     cost[i][j] = 9999; 
    } 
} 

现在，我需要通过读取文件中的权重来更新成本矩阵的权重。 所以，我正在阅读文件如下。

ifstream fin; 
fin.open("input.txt",ios::in); 
fin >> n; //nodes 
fin >> e; //edges 
while(fin) 
{ 
    fin>>a>>b>>w; 
    cost[a-1][b-1] =cost[b-1][a-1]= w; 
} 
fin.close(); 

所以，a和b是边缘，w是边缘的权重。所以，假设我有边缘（1,2），其权重为3.所以，我的成本矩阵cost[1][2]和cost[2][1]应该更新为3.我无法弄清楚如何使用文件操作更新成本矩阵。

再次说明，我有一个文本文件，就像上面提到的文件一样。文件的第一行包含边的顶点数。我想读取变量v中的顶点和变量e中的边。然后，我有一个初始成本矩阵cost[i][i]其中所有值都是无穷大。我想从文件更新此成本矩阵中的边。所以，我会从文件中读取第二行并更新cost[1][2] = 3.我不知道如何执行此操作。

下面是完整的程序我现在有：

#include<iostream> 
#include<fstream> 
using namespace std; 

int n,e,a,b,w; 
int **cost = new int*[n]; 

void prim() 
{ 
int i,j,k,l,x,nr[10],temp,min_cost=0; 
int **tree = new int*[n]; 

for(i = 0; i < n; i++) 
tree[i]=new int[n]; 

/* For first smallest edge */ 
temp=cost[0][0]; 
for(i=0;i< n;i++) 
{ 
for(j=0;j< n;j++) 
{ 
    if(temp>cost[i][j]) 
    { 
    temp=cost[i][j]; 
    k=i; 
    l=j; 
    } 
} 
} 
/* Now we have fist smallest edge in graph */ 
tree[0][0]=k; 
tree[0][1]=l; 
tree[0][2]=temp; 
min_cost=temp; 

/* Now we have to find min dis of each 
vertex from either k or l 
by initialising nr[] array 
*/ 

for(i=0;i< n;i++) 
    { 
    if(cost[i][k]< cost[i][l]) 
    nr[i]=k; 
    else 
    nr[i]=l; 
    } 
    /* To indicate visited vertex initialise nr[] for them to 100 */ 
    nr[k]=100; 
    nr[l]=100; 
    /* Now find out remaining n-2 edges */ 
    temp=99; 
    for(i=1;i< n-1;i++) 
    { 
    for(j=0;j< n;j++) 
    { 
     if(nr[j]!=100 && cost[j][nr[j]] < temp) 
     { 
     temp=cost[j][nr[j]]; 
     x=j; 
     } 
    } 
    /* Now i have got next vertex */ 
    tree[i][0]=x; 
    tree[i][1]=nr[x]; 
    tree[i][2]=cost[x][nr[x]]; 
    min_cost=min_cost+cost[x][nr[x]]; 
    nr[x]=100; 

    /* Now find if x is nearest to any vertex 
    than its previous near value */ 

for(j=0;j< n;j++) 
{ 
if(nr[j]!=100 && cost[j][nr[j]] > cost[j][x]) 
    nr[j]=x; 
} 
temp=9999; 
} 
/* Now i have the answer, just going to print it */ 
cout<<"\n The minimum spanning tree is:"<<endl; 
for(i=0;i< n-1;i++) 
{ 
for(j=0;j< 3;j++) 
     cout<<tree[i][j]; 
cout<<endl; 
} 

cout<<"\nMinimum cost:"; 
cout<<min_cost; 
} 


int main() 
{ 
    int i,j; 

    for(i = 0; i < n; i++) 
    cost[i]=new int[n]; 


for(i = 0; i < n; i++) 
    { 
    for(j = 0; j < n; j++) 
     { 
     cost[i][j] = 9999; 
     } 
    } 

    ifstream fin; 
    fin.open("input.txt",ios::in); 

//cout<<n<<e; 
    fin>>n>>e; 

    while(fin>>a>>b>>w) 
    { 

    cost[a-1][b-1] = w; 


     } 
fin.close(); 
    prim(); 
    system("pause"); 
    } 

Answer 1

更新

读码的改编加入到OP后：

#include<vector> 

typedef int Cost; 
typedef std::vector<std::vector<Cost> > Matrix; 
typedef Matrix::value_type Row; 

不改变prim采取cost matrix by ref：

void prim(Matrix const& cost) 

和阅读变为：

int main() 
{ 
    ifstream fin; 
    fin.open("input.txt", ios::in); 
    unsigned n, e; 

    if (fin >> n >> e) 
    { 
     Matrix cost(n, Row(n, 9999)); 

     unsigned a, b; 
     Cost w; 
     while(fin >> a >> b >> w) 
     { 
      cost[a - 1][b - 1] = w; 
     } 
     prim(cost); 
    } 
    fin.close(); 
} 

你看，

• 避免手动内存管理
• 做错误检查

---

老回答：

假设的数据结构：

typedef unsigned Vertex; 
typedef std::pair<Vertex, Vertex> Edge; 
typedef double Cost; 

typedef std::map<Edge, Cost> Graph; 
typedef Graph::value_type Entry; 

这里使用的readGraph一个很干净的版本只是标准库设施：

Graph readGraph(std::istream& is) 
{ 
    size_t vertices, edges; 

    if (is >> vertices >> edges) 
    { 
     is.ignore(1024, '\n'); // assume not overly long lines 

     Graph graph; 
     while (edges--) 
     { 
      std::string line; 
      if (is && std::getline(is, line)) 
      { 
       Vertex from, to; 
       Cost cost; 

       std::istringstream line_stream(line); 

       if (line_stream >> from >> to >> cost) 
       { 
        if (!(graph.insert({ { from, to }, cost }).second)) 
         throw std::runtime_error("Duplicate edge"); 
       } else 
       { 
        is.setstate(is.rdstate() | std::ios::badbit); 
       } 
      } 
     } 

     if (!is.bad()) 
      return graph; 
    } 

    throw std::runtime_error("Invalid input"); 
} 

看到它Live On Coliru

Graph const graph = readGraph(std::cin); 

for (auto& entry: graph) 
{ 
    Edge const& edge = ::get_edge(entry); 
    Cost  cost = ::get_cost(entry); 

    std::cout << "Edge(" << get_source(edge) << ", " << get_destination(edge) << "): cost " << cost << "\n"; 
} 

输出：

Edge(1, 2): cost 3 
Edge(1, 3): cost 4 
Edge(2, 3): cost 4 

替代

使用升压精神做解析。这是一个简易替换和数据结构和main()已经完全未改变：

Graph readGraph(std::istream& is) 
{ 
    typedef boost::spirit::istream_iterator It; 
    is.unsetf(std::ios::skipws); 
    It f(is), l; 

    size_t vertices = 0, edges = 0; 
    Graph graph; 

    using namespace boost::spirit::qi; 
    static const rule<It, Edge(), blank_type> edge_rule = uint_ >> uint_; 

    bool ok = phrase_parse(f, l, 
      uint_ >> uint_ >> eol >> 
      (edge_rule >> double_) % eol >> (*eol > eoi), 
      blank, 
      vertices, edges, graph); 

    assert(ok && f==l && graph.size() == edges); 

    return graph; 
} 

看到它Live on Coliru了。

参考

完整代码

（万一Coliru不再存在）：

#include <iostream> 
#include <fstream> 
#include <iterator> 
#include <algorithm> 
#include <sstream> 
#include <map> 
#include <cassert> 
#include <stdexcept> 

typedef unsigned Vertex; 
typedef std::pair<Vertex, Vertex> Edge; 
typedef double Cost; 

typedef std::map<Edge, Cost> Graph; 
typedef Graph::value_type Entry; 

Graph readGraph(std::istream& is) 
{ 
    size_t vertices, edges; 

    if (is >> vertices >> edges) 
    { 
     is.ignore(1024, '\n'); // assume not overly long lines 

     Graph graph; 
     while (edges--) 
     { 
      std::string line; 
      if (is && std::getline(is, line)) 
      { 
       Vertex from, to; 
       Cost cost; 

       std::istringstream line_stream(line); 

       if (line_stream >> from >> to >> cost) 
       { 
        if (!(graph.insert({ { from, to }, cost }).second)) 
         throw std::runtime_error("Duplicate edge"); 
       } else 
       { 
        is.setstate(is.rdstate() | std::ios::badbit); 
       } 
      } 
     } 

     if (!is.bad()) 
      return graph; 
    } 

    throw std::runtime_error("Invalid input"); 
} 

static inline Vertex  get_source  (Edge const& e) { return e.first; } 
static inline Vertex  get_destination(Edge const& e) { return e.second; } 
static inline Edge const& get_edge  (Entry const& e) { return e.first; } 
static inline double  get_cost  (Entry const& e) { return e.second; } 

static inline Vertex&  get_source  (Edge  & e) { return e.first; } 
static inline Vertex&  get_destination(Edge  & e) { return e.second; } 
static inline double&  get_cost  (Entry  & e) { return e.second; } 

int main() 
{ 
    Graph const graph = readGraph(std::cin); 

    for (auto& entry: graph) 
    { 
     Edge const& edge = ::get_edge(entry); 
     Cost  cost = ::get_cost(entry); 

     std::cout << "Edge(" << get_source(edge) << ", " << get_destination(edge) << "): cost " << cost << "\n"; 
    } 
}