如何让数据结构可视化？

超、凢脫俗 2022-10-17 01:36 144阅读 0赞

当我们实现一个比较复杂的数据结构，比如二叉树、图、跳表，Debug的时候怎么验证自己写的函数对不对呢？

一个方法是将数据结构可视化，与理论上的结果比较即可。

请出主角：**Graphviz**，带一种解释语言`dot`，可以用简明的代码作图。  
之所以推荐这个是因为它可以**自动排版**

## 1. 安装 ##

官网下载链接\[1\]：http://www.graphviz.org/download/

作者系统为win10，其他操作系统应该大同小异。  
安装时需要勾选**添加环境变量**：

![89635b8bce81c9dfd60a0c00acda57d5.png][] 添加环境变量

## 2. 渲染 ##

有vscode的读者可以安装一个vscode插件：

![4ab2a757b69a09e9f45af9af5367a898.png][] 安装vscode插件

安装完成后，新建一个`.dot`文件，右上角会出现一个渲染按钮：

![9e5f4799a0dbd20964475172f5201340.png][] 渲染按钮  
没有vscode的读者可以使用命令手动渲染：

dot -Tpng 你的代码文件名 -o 输出图片文件名

## 3. 编写代码 ##

一个空的dot代码（什么都不渲染）：

digraph {
    }

![4ee2b688a7a9b530af8d29c4681755c1.png][] 四个样例渲染效果

如图左上，可以使用下面代码，来创建一个名字为a的结点

digraph {
      a
    }

如图左下，通过`label`的修改可以改动结点显示的文字。  
如图右上，通过`style = "dotted"`可以让其外侧圈边成虚线（可以用来显示NULL结点）  
代码中的引号疑似不是必须的，建议保留。

digraph {
        a[label = "文字", style = "dotted"]
    }

通过`结点名称 -> 结点名称`来创建一条线。  
同理也可以使用`dotted`，（虚线用于连接NULL结点）。  
这个`taillabel`可以在靠近第一个结点处显示一个数值（可用于显示结点中的一个数值）

digraph {
        node1[label = "A"]
        node2[label = "B"]
        node1 -> node2[style = dotted, taillabel = "0"]
    }

tips:建议将结点的数据，也就是`value`，拿到`node[label = ]`中显示，最突出、显眼。

## 4. 坑 ##

### 3.4.1 NULL补位 ###

> NULL，空指针，在C++中被定义为`0`  
> 一个正常结点缺失左或右子结点时，会使用NULL指针来填补空缺。

正是因为其自动排版的功能，会导致一些坑。  
举个例子，我们要画一个这样的二叉树：

1
        |
     -------
    |       |
    0    没有右孩子（NULL结点）

因为我们不能使用开头为数字作为变量名，所以我们的命名规则为：`n + 数字`。

绘画效果：

![ebc8249ec65fb66519f7ddf77478559d.png][] NULL结点补位

我们发现，如果不使用一个结点NULL来补位，树被拉成了一个链。  
我们只需要使用**一层NULL结点**来补位，这样结构就渲染正常了。

### 3.4.2 命名 ###

两个结点名字相同，会被判定为一个结点：

![827b2a7179a7d1316cadc0debd85e3cc.png][] 结点名称相同

虽然这种情况在二叉搜索树中不存在，但是这里还是提一下。

怎么区分不同的结点呢？我们可以通过C++程序中结点的指针来命名。  
结点名称：`n + 指针`  
**即使两个结点存储内容相同，但是在电脑中的内存地址一定不同。**

但是NULL结点都会被命名为`n0`，无法区分，怎么办呢？  
我这里使用的解决方法：NULL结点命名规则为`n + 叶子结点指针 + 是左子结点还是右子结点`

![d73aa89a90ffc9fa05465f1fde4dc358.png][] AVL样例

## 3.5 代码 ##

这个代码是基于Part 1中结点的定义来实现的。

void DEBUG() { // 使用了part 2中的软件来绘图，调试神器
        FILE *fp = NULL;
        fp = fopen("./output.dot", "w"); // ./output.dot 为输出的文件名
        fprintf(fp, "digraph {\n");
    
        deque<node*> q; // 前序遍历，使用队列实现
        node *current;
        q.push_back(root);
        while (!q.empty()) {
            current = q.front();
            q.pop_front();
            if (current == NULL) {
                continue;
            }
            fprintf(fp, "\tn%d[label = \"%d\"]\n", current, current->value);
            for (int i = 0; i < 2; ++i) {
                if (current->child[i]) {
                    fprintf(fp, "\tn%d -> n%d[style = blod]\n", current, current->child[i]);
                    q.push_back(current->child[i]);
                } else {
                    fprintf(fp, "\tnull%d%d[label = \"NULL\", style = dotted]\n", current, i);
                    fprintf(fp, "\tn%d -> null%d%d[style = dotted]\n", current, current, i);
                }
            }
        }
        fprintf(fp, "}");
        fclose(fp);
    }

### 参考资料 ###

\[1\]

官网下载链接: http://www.graphviz.org/download/

[89635b8bce81c9dfd60a0c00acda57d5.png]: /images/20221014/efe2eef3bb5b4045b2c3f257fd3d1074.png
[4ab2a757b69a09e9f45af9af5367a898.png]: /images/20221014/c4a0846b81b5486588c73433feee3c40.png
[9e5f4799a0dbd20964475172f5201340.png]: /images/20221014/826075c8f71741249e30448d65d51fdc.png
[4ee2b688a7a9b530af8d29c4681755c1.png]: /images/20221014/4353d69e505f4a05a06331de1811c755.png
[ebc8249ec65fb66519f7ddf77478559d.png]: /images/20221014/7fa02e63c08d4c09b9d14d8dbe9a4053.png
[827b2a7179a7d1316cadc0debd85e3cc.png]: /images/20221014/1a75911adf4f4407a52d02913ba2508d.png
[d73aa89a90ffc9fa05465f1fde4dc358.png]: /images/20221014/33bc8680dfd049cbb0e4730576175541.png