求助：coursera斯坦福的那个算法课week3的作业

用c++实现文件操作，读取文件并且制作邻接表

1 2 3
2 4 1
3 1
4 2

文件形式如上所示。最左边的一列代表顶点（datatype为int），右边的几列都是相邻的顶点。现在想把这个东西用c++读进来并且创建一个邻接表，请问应该怎么操作？？谢谢！

http://www.cplusplus.com/reference/fstream/ifstream/

freopen("in.txt", "r", stdin);
getline字符串后用sstream处理

AdjList.h

1. #ifndef _ADJLIST_H_
   
2. #define _ADJLIST_H_
   
3. #include <vector>
   
4. 
   
5. class AdjList {
   
6. private:
   
7.   std::vector<int>* myAdj;
   
8.   int myVertexNum;
   
9.   void destory();
   
10.   void copyAll(const AdjList &that);
    
11. 
    
12. public:
    
13.   AdjList(const int vertexNum);
    
14.   AdjList(const AdjList &that);
    
15.   const AdjList & operator=(const AdjList &that);
    
16.   ~AdjList();
    
17.   void addEdge(const int v, const int w);
    
18.   void getAdj(const int v, std::vector<int> &adj) const;
    
19.   void print() const;
    
20. };
    
21. 
    
22. #endif
    

复制代码

AdjList.cpp

1. #include <iostream>
   
2. #include <cassert>
   
3. #include <vector>
   
4. #include "AdjList.h"
   
5. 
   
6. void AdjList::destory() {
   
7.     delete [] myAdj;
   
8.     myAdj = 0;
   
9.     myVertexNum = 0;
   
10. }
    
11. 
    
12. void AdjList::copyAll(const AdjList &that) {
    
13.     myVertexNum = that.myVertexNum;
    
14.     myAdj = new std::vector<int> [myVertexNum];
    
15.     for (int i = 0; i < myVertexNum; ++i) {
    
16.         myAdj[i] = that.myAdj[i];
    
17.     }
    
18. }
    
19. 
    
20. AdjList::AdjList(const int vertexNum) : myAdj(0), myVertexNum(vertexNum) {
    
21.     myAdj = new std::vector<int> [myVertexNum];
    
22. }
    
23. 
    
24. AdjList::AdjList(const AdjList &that) : myAdj(0), myVertexNum(0) {
    
25.     copyAll(that);
    
26. }
    
27. 
    
28. const AdjList & AdjList::operator=(const AdjList &that) {
    
29.     if (this != &that) {
    
30.         destory();
    
31.         copyAll(that);
    
32.     }
    
33.     return *this;
    
34. }
    
35. 
    
36. AdjList::~AdjList() {
    
37.     destory();
    
38. }
    
39. 
    
40. void AdjList::addEdge(const int v, const int w) {
    
41.     assert(v >= 0 && v < myVertexNum && w >= 0 && w < myVertexNum);
    
42.     for (unsigned i = 0; i < myAdj[v].size(); ++i) {
    
43.         if (myAdj[v][i] == w) {
    
44.             return;
    
45.         }
    
46.     }
    
47.     myAdj[v].push_back(w);
    
48.     myAdj[w].push_back(v);
    
49. }
    
50. 
    
51. void AdjList::getAdj(const int v, std::vector<int> &adj) const {
    
52.     assert(v >= 0 && v < myVertexNum);
    
53.     adj = myAdj[v];
    
54. }
    
55. 
    
56. void AdjList::print() const {
    
57.     for (int i = 0; i < myVertexNum; ++i) {
    
58.         std::cout << "No." << i << ": ";
    
59.         for (unsigned j = 0; j < myAdj[i].size(); ++j) {
    
60.             std::cout << myAdj[i][j] << " ";
    
61.         }
    
62.         std::cout << std::endl;
    
63.     }
    
64. }
    

复制代码

helperFunction.h

1. #ifndef _FUN_H_
   
2. #define _FUN_H_
   
3. #include <string>
   
4. 
   
5. int power(const int base, const int exp);
   
6. 
   
7. int str2int(const std::string &str);
   
8. 
   
9. #endif

复制代码

helperFunction.cpp

1. #include <string>
   
2. #include "fun.h"
   
3. 
   
4. int power(const int base, const int exp) {
   
5.     int result = 1;
   
6.     for (int i = 0; i < exp; ++i) {
   
7.         result *= base;
   
8.     }
   
9.     return result;
   
10. }
    
11. 
    
12. int str2int(const std::string &str) {
    
13.     int size = str.size();
    
14.     int result = 0;
    
15.     for (int i = size - 1; i >= 0; --i) {
    
16.         result += (str[i] - '0') * power(10, size - 1 - i);
    
17.     }
    
18.     return result;
    
19. }

复制代码

main.cpp

1. #include <iostream>
   
2. #include <stdio.h>
   
3. #include <fstream>
   
4. #include <vector>
   
5. #include "AdjList.h"
   
6. #include "fun.h"
   
7. 
   
8. using namespace std;
   
9. 
   
10. int main()
    
11. {
    
12.     ifstream infile("input.txt");
    
13.     int vertexNum = 0;
    
14.     string line;
    
15.     while (getline(infile, line)) {
    
16.         ++vertexNum;
    
17.         line.clear();
    
18.     }
    
19.     infile.close();
    
20.     AdjList adjList(vertexNum);
    
21.     infile.open("input.txt");
    
22.     while (getline(infile, line)) {
    
23.         unsigned pos1 = -1, pos2 = -1;
    
24.         pos1 = line.find_first_of(' ');
    
25.         if (pos1 == string::npos) {
    
26.             line.clear();
    
27.             continue;
    
28.         }
    
29.         string vName(line, 0, pos1);
    
30.         int v = str2int(vName) - 1;
    
31.         while (pos1 != string::npos) {
    
32.             pos2 = line.find_first_of(' ', pos1 + 1);
    
33.             if (pos2 == string::npos) {
    
34.                 break;
    
35.             }
    
36.             string wName(line, pos1 + 1, pos2 - pos1 - 1);
    
37.             int w = str2int(wName) - 1;
    
38.             adjList.addEdge(v, w);
    
39.             pos1 = line.find_first_of(' ', pos2 + 1);
    
40.         }
    
41.         pos1 = line.find_last_of(' ');
    
42.         string wName(line, pos1 + 1, line.size() - 1 - pos1);
    
43.         int w = str2int(wName) - 1;
    
44.         adjList.addEdge(v, w);
    
45.         line.clear();
    
46.     }
    
47.     infile.close();
    
48.     adjList.print();
    
49.     return 0;
    
50. }
    

复制代码

lvchaoshuai 发表于 2013-7-26 03:24
freopen("in.txt", "r", stdin);
getline字符串后用sstream处理

嗯。谢谢~我之后就是这么干的~

浅浅 发表于 2013-7-29 00:12
AdjList.hAdjList.cpphelperFunction.hhelperFunction.cppmain.cpp

谢谢~我还没有啥把程序分成头文件的意识~看你写的程序真规整。向你学习！

我用的是python。。。感觉python写起来很方便。

gnijuohz 发表于 2013-7-29 20:22
我用的是python。。。感觉python写起来很方便。

我也用习惯python..但是感觉用惯了python..对底层算法的理解并不有利

zhujl1991 发表于 2013-7-29 18:28
谢谢~我还没有啥把程序分成头文件的意识~看你写的程序真规整。向你学习！

哈哈不必客气，互相学习吧；能否帮我加点分，分太低看不了别人帖子

楼上厉害，写的真规整