【C++板块提升计划】动态数组――Vector的详细用法【原创】

zhangjinxuan

求支持@tommyyu @柿子饼同学 @高山 @不二如是

zhangjinxuan

本来想设置回帖奖励的，但是又怕被审核

zhangjinxuan

果不其然，加一个回帖奖励，又被审核了

zhangjinxuan

顶一顶，有人吗？

zhangjinxuan

这计划不靠谱啊，还是没人我就删专辑不更新了哦

dolly_yos2

看到 vector 突然想起来一件事情，在这里放一个之前感觉很有趣的程序大家来看看（ debug ）。这不是一个求助！
代码和原始的已经完全不同了，这里是基于复现问题重新编造了一个背景并且把代码写的更简短和清晰得到的，应该可以排除一些不必要的干扰。当然，代码里不一定只有我想要分享的问题，毕竟水平有限，发现了什么问题都可以提

背景很简单，有向图的拓扑排序，但要同时给出节点的“层次”，节点 A 的“层次”定义为至少需要先删除几个节点和与被删除节点相连的边才能使 A 成为自由的，即没有入度的节点。代码如下

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. struct node{
   
5.     int id;     // 节点的编号
   
6.     int level;  // 节点的层次
   
7. 
   
8.     node(int id_, int level_): id(id_), level(level_){}
   
9. };
   
10. vector<node> arrange(const size_t n, const bool* const map, size_t* const in){
    
11.     vector<node> result; // 保存结果
    
12. 
    
13.     // 初始化：找到所有无入度的节点，保存进结果。它们具有层次0
    
14.     for(size_t i = 0; i < n; i++) if(in[i] == 0) result.emplace_back(i, 0);
    
15. 
    
16.     // 开始实际排序循环，对于已经记录的每一个节点
    
17.     for(size_t i = 0; i < result.size(); i++){
    
18.         // 获取当前找到的节点，使用引用避免复制
    
19.         node& current = result.at(i);
    
20.         // 对于每一条出边
    
21.         for(size_t j = 0; j < n; j++) if(map[current.id * n + j] == true){
    
22.             // 减少终点的入度
    
23.             in[j]--;
    
24.             // 如果终点已无入度，将其加入结果，记录其层次
    
25.             if(in[j] == 0){
    
26.                 result.emplace_back(j, current.level + 1);
    
27.             }
    
28.         }
    
29.     }
    
30. 
    
31.     // 查找结束，返回结果
    
32.     return result;
    
33. }
    
34. int main(){
    
35.     // 首先输入节点个数
    
36.     size_t n;
    
37.     cin >> n;
    
38.     // 申请空间存储邻接矩阵和入度表并初始化
    
39.     bool *map = new bool[n * n];
    
40.     size_t *in = new size_t[n];
    
41.     for(size_t i = 0; i < n; i++){
    
42.         for(size_t j = 0; j < n; j++) map[i * n + j] = false;
    
43.         in[i] = 0;
    
44.     }
    
45.     // 接下来输入边数
    
46.     size_t m;
    
47.     cin >> m;
    
48.     int from, to;
    
49.     for(size_t i = 0; i < m; i++){
    
50.         // 输入每一条边，格式是从先给出开始节点再给出结束节点
    
51.         cin >> from >> to;
    
52.         // 在矩阵中记录并更新入度
    
53.         map[from * n + to] = true;
    
54.         in[to]++;
    
55.     }
    
56.     // 进行拓扑排序
    
57.     auto result = arrange(n, map, in);
    
58.     // 输出结果
    
59.     for(const auto i: result) cout << '{' << i.id << ", " << i.level << "} ";
    
60.     // 释放申请的空间
    
61.     delete[] map;
    
62.     delete[] in;
    
63.     return 0;
    
64. }

复制代码

如果需要的话，可以使用下面的测试数据，尽管保证代码存在问题但不保证下方的数据能让问题被观测到

1. 20
   
2. 25
   
3. 0 1
   
4. 0 2
   
5. 0 3
   
6. 0 4
   
7. 0 5
   
8. 0 6
   
9. 0 7
   
10. 0 8
    
11. 0 9
    
12. 0 10
    
13. 0 11
    
14. 0 12
    
15. 0 13
    
16. 0 14
    
17. 0 15
    
18. 0 16
    
19. 0 17
    
20. 0 18
    
21. 0 19
    
22. 1 2
    
23. 1 4
    
24. 2 6
    
25. 3 8
    
26. 4 9
    
27. 5 10

复制代码

其实有点无聊，还是希望有兴趣的朋友能玩的愉快

zhangjinxuan

dolly_yos2 发表于 2022-11-22 13:57
看到 vector 突然想起来一件事情，在这里放一个之前感觉很有趣的程序大家来看看（ debug ）。这不是一个求 ...

感谢分享~

zhangjinxuan

@wangyanren 来吧，只想领个币的鱼油

dingyiwen

1

wangyanren

来了来了  多给点啊   帮我弄成最佳   加个技术值也好

zhangjinxuan

wangyanren 发表于 2022-11-22 17:18
来了来了  多给点啊   帮我弄成最佳   加个技术值也好

技术值需要自己的努力~

zhangjinxuan

dingyiwen 发表于 2022-11-22 16:38
1

希望下一次不会再有这样灌水的行为了

说了 N 遍了，不要回复 1！容易会判灌水的啊！

howzyao

讲的太好啦。赞

高山

顶