鱼C论坛

 找回密码
 立即注册
查看: 2125|回复: 14

[技术交流] 【C++板块提升计划】动态数组――Vector的详细用法【原创】

[复制链接]
 楼主| 发表于 2022-11-21 21:58:49 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-21 21:59:28 | 显示全部楼层
本来想设置回帖奖励的,但是又怕被审核
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-21 22:01:31 | 显示全部楼层
果不其然,加一个回帖奖励,又被审核了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-22 08:47:48 | 显示全部楼层
顶一顶,有人吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-22 12:02:20 | 显示全部楼层
这计划不靠谱啊,还是没人我就删专辑不更新了哦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-22 13:57:06 | 显示全部楼层

回帖奖励 +2 鱼币

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

背景很简单,有向图的拓扑排序,但要同时给出节点的“层次”,节点 A 的“层次”定义为至少需要先删除几个节点和与被删除节点相连的边才能使 A 成为自由的,即没有入度的节点。代码如下
#include <iostream>
#include <vector>
using namespace std;
struct node{
    int id;     // 节点的编号
    int level;  // 节点的层次

    node(int id_, int level_): id(id_), level(level_){}
};
vector<node> arrange(const size_t n, const bool* const map, size_t* const in){
    vector<node> result; // 保存结果

    // 初始化:找到所有无入度的节点,保存进结果。它们具有层次0
    for(size_t i = 0; i < n; i++) if(in[i] == 0) result.emplace_back(i, 0);

    // 开始实际排序循环,对于已经记录的每一个节点
    for(size_t i = 0; i < result.size(); i++){
        // 获取当前找到的节点,使用引用避免复制
        node& current = result.at(i);
        // 对于每一条出边
        for(size_t j = 0; j < n; j++) if(map[current.id * n + j] == true){
            // 减少终点的入度
            in[j]--;
            // 如果终点已无入度,将其加入结果,记录其层次
            if(in[j] == 0){
                result.emplace_back(j, current.level + 1);
            }
        }
    }

    // 查找结束,返回结果
    return result;
}
int main(){
    // 首先输入节点个数
    size_t n;
    cin >> n;
    // 申请空间存储邻接矩阵和入度表并初始化
    bool *map = new bool[n * n];
    size_t *in = new size_t[n];
    for(size_t i = 0; i < n; i++){
        for(size_t j = 0; j < n; j++) map[i * n + j] = false;
        in[i] = 0;
    }
    // 接下来输入边数
    size_t m;
    cin >> m;
    int from, to;
    for(size_t i = 0; i < m; i++){
        // 输入每一条边,格式是从先给出开始节点再给出结束节点
        cin >> from >> to;
        // 在矩阵中记录并更新入度
        map[from * n + to] = true;
        in[to]++;
    }
    // 进行拓扑排序
    auto result = arrange(n, map, in);
    // 输出结果
    for(const auto i: result) cout << '{' << i.id << ", " << i.level << "} ";
    // 释放申请的空间
    delete[] map;
    delete[] in;
    return 0;
}
如果需要的话,可以使用下面的测试数据,尽管保证代码存在问题但不保证下方的数据能让问题被观测到
20
25
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
1 2
1 4
2 6
3 8
4 9
5 10

其实有点无聊,还是希望有兴趣的朋友能玩的愉快
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2022-11-22 14:14:44 | 显示全部楼层
dolly_yos2 发表于 2022-11-22 13:57
看到 vector 突然想起来一件事情,在这里放一个之前感觉很有趣的程序大家来看看( debug )。这不是一个求 ...

感谢分享~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-22 15:15:42 | 显示全部楼层
@wangyanren 来吧,只想领个币的鱼油
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-22 16:38:45 | 显示全部楼层

回帖奖励 +2 鱼币

1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-11-22 17:18:53 | 显示全部楼层

回帖奖励 +2 鱼币

来了来了  多给点啊   帮我弄成最佳   加个技术值也好
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-22 17:32:25 | 显示全部楼层
wangyanren 发表于 2022-11-22 17:18
来了来了  多给点啊   帮我弄成最佳   加个技术值也好

技术值需要自己的努力~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-11-22 18:10:01 | 显示全部楼层

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

说了 N 遍了,不要回复 1!容易会判灌水的啊!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-23 00:57:21 From FishC Mobile | 显示全部楼层
讲的太好啦。赞
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-23 16:56:13 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-10 18:50

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表