FDF*_*ock 7 c language-agnostic binary-tree pretty-print
(第一次发布海报,而不是新编程,请耐心等待!)
我对打印格式化二叉树(在CLI环境中)和C实现的高效通用算法感兴趣.这是我为了好玩而编写的一些代码(这是原始版本的简化版本,是支持许多BST操作的大型程序的一部分,但它应该编译得很好):
#include <stdbool.h> // C99, boolean type support
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define DATATYPE_IS_DOUBLE
#define NDEBUG // disable assertions
#include <assert.h>
#define WCHARBUF_LINES 20 // def: 20
#define WCHARBUF_COLMS 800 // def: 80 (using a huge number, like 500, is a good idea,
// in order to prevent a buffer overflow :)
#define RECOMMENDED_CONS_WIDTH 150
#define RECOMMENDED_CONS_WIDTHQ "150" // use the same value, quoted
/* Preprocessor directives depending on DATATYPE_IS_* : */
#if defined DATATYPE_IS_INT || defined DATATYPE_IS_LONG
#define DTYPE long int
#define DTYPE_STRING "INTEGER"
#define DTYPE_PRINTF "%*.*ld"
#undef DATATYPE_IS_CHAR
#elif defined DATATYPE_IS_FLOAT
#define DTYPE float
#define DTYPE_STRING "FLOAT"
#define DTYPE_PRINTF "%*.*f"
#undef DATATYPE_IS_CHAR
#elif defined DATATYPE_IS_DOUBLE
#define DTYPE double
#define DTYPE_STRING "DOUBLE"
#define DTYPE_PRINTF "%*.*lf"
#undef DATATYPE_IS_CHAR
#elif defined DATATYPE_IS_CHAR
#define DTYPE char
#define DTYPE_STRING "CHARACTER"
#define DTYPE_PRINTF "%*.*c" /* using the "precision" sub-specifier ( .* ) with a */
/* character will produce a harmless compiler warning */
#else
#error "DATATYPE_IS_* preprocessor directive undefined!"
#endif
typedef struct node_struct {
DTYPE data;
struct node_struct *left;
struct node_struct *right;
/* int height; // useful for AVL trees */
} node;
typedef struct {
node *root;
bool IsAVL; // useful for AVL trees
long size;
} tree;
static inline
DTYPE get_largest(node *n){
if (n == NULL)
return (DTYPE)0;
for(; n->right != NULL; n=n->right);
return n->data;
}
static
int subtreeheight(node *ST){
if (ST == NULL)
return -1;
int height_left = subtreeheight(ST->left);
int height_right = subtreeheight(ST->right);
return (height_left > height_right) ? (height_left + 1) : (height_right + 1);
}
void prettyprint_tree(tree *T){
if (T == NULL) // if T empty, abort
return;
#ifndef DATATYPE_IS_CHAR /* then DTYPE is a numeric type */
/* compute spaces, find width: */
int width, i, j;
DTYPE max = get_largest(T->root);
width = (max < 10) ? 1 :
(max < 100) ? 2 :
(max < 1000) ? 3 :
(max < 10000) ? 4 :
(max < 100000) ? 5 :
(max < 1000000) ? 6 :
(max < 10000000) ? 7 :
(max < 100000000) ? 8 :
(max < 1000000000) ? 9 : 10;
assert (max < 10000000000);
width += 2; // needed for prettier results
#if defined DATATYPE_IS_FLOAT || defined DATATYPE_IS_DOUBLE
width += 2; // because of the decimals! (1 decimal is printed by default...)
#endif // float or double
int spacesafter = width / 2;
int spacesbefore = spacesafter + 1;
//int spacesbefore = ceil(width / 2.0);
#else /* character input */
int i, j, width = 3, spacesbefore = 2, spacesafter = 1;
#endif // #ifndef DATATYPE_IS_CHAR
/* start wchar_t printing, using a 2D character array with swprintf() : */
struct columninfo{ // auxiliary structure
bool visited;
int col;
};
wchar_t wcharbuf[WCHARBUF_LINES][WCHARBUF_COLMS];
int line=0;
struct columninfo eachline[WCHARBUF_LINES];
for (i=0; i<WCHARBUF_LINES; ++i){ // initialization
for (j=0; j<WCHARBUF_COLMS; ++j)
wcharbuf[i][j] = (wchar_t)' ';
eachline[i].visited = false;
eachline[i].col = 0;
}
int height = subtreeheight(T->root);
void recur_swprintf(node *ST, int cur_line, const wchar_t *nullstr){ // nested function,
// GCC extension!
float offset = width * pow(2, height - cur_line);
++cur_line;
if (eachline[cur_line].visited == false) {
eachline[cur_line].col = (int) (offset / 2);
eachline[cur_line].visited = true;
}
else{
eachline[cur_line].col += (int) offset;
if (eachline[cur_line].col + width > WCHARBUF_COLMS)
swprintf(wcharbuf[cur_line], L" BUFFER OVERFLOW DETECTED! ");
}
if (ST == NULL){
swprintf(wcharbuf[cur_line] + eachline[cur_line].col, L"%*.*s", 0, width, nullstr);
if (cur_line <= height){
/* use spaces instead of the nullstr for all the "children" of a NULL node */
recur_swprintf(NULL, cur_line, L" ");
recur_swprintf(NULL, cur_line, L" ");
}
else
return;
}
else{
recur_swprintf(ST->left, cur_line, nullstr);
recur_swprintf(ST->right, cur_line, nullstr);
swprintf(wcharbuf[cur_line] + eachline[cur_line].col - 1, L"("DTYPE_PRINTF"",
spacesbefore, 1, ST->data);
//swprintf(wcharbuf[cur_line] + eachline[cur_line].col + spacesafter + 1, L")");
swprintf(wcharbuf[cur_line] + eachline[cur_line].col + spacesafter + 2, L")");
}
}
void call_recur(tree *tr){ // nested function, GCC extension! (wraps recur_swprintf())
recur_swprintf(tr->root, -1, L"NULL");
}
call_recur(T);
/* Omit empty columns: */
int omit_cols(void){ // nested function, GCC extension!
int col;
for (col=0; col<RECOMMENDED_CONS_WIDTH; ++col)
for (line=0; line <= height+1; ++line)
if (wcharbuf[line][col] != ' ' && wcharbuf[line][col] != '\0')
return col;
return 0;
}
/* Use fputwc to transfer the character array to the screen: */
j = omit_cols() - 2;
j = (j < 0) ? 0 : j;
for (line=0; line <= height+1; ++line){ // assumes RECOMMENDED_CONS_WIDTH console window!
fputwc('\n', stdout); // optional blanc line
for (i=j; i<j+RECOMMENDED_CONS_WIDTH && i<WCHARBUF_COLMS; ++i)
fputwc(wcharbuf[line][i], stdout);
fputwc('\n', stdout);
}
}
(也上传到pastebin服务,以保留语法高亮)
虽然自动宽度设置可能更好,但效果很好.预处理器魔术有点愚蠢(甚至丑陋)并且与算法没有实际关系,但它允许在树节点中使用各种数据类型(我认为这是一个机会对预处理器进行一些实验 - 请记住,我是一个新手!).
主程序应该调用
system("mode con:cols="RECOMMENDED_CONS_WIDTHQ" lines=2000");
在调用prettyprint_tree()之前,在cmd.exe中运行时.
样本输出:
(106.0)
(102.0) (109.0)
(101.5) NULL (107.0) (115.0)
NULL NULL (106.1) NULL (113.0) NULL
NULL NULL NULL NULL
理想情况下,输出将是这样的(我使用wprintf()系列函数的原因是无论如何都能够打印Unicode字符):
(107.0)
?????????????
(106.1) NULL
?????????
NULL NULL
所以,我的问题:
提前感谢您的回复!
PS.现在的问题是没有一个重复的这一个.
编辑: 乔纳森莱弗勒写了一个很好的答案,很可能在几天后成为"接受的答案"(除非有人发布同样令人敬畏的东西!).由于空间限制,我决定在这里回答而不是评论.
bool IsAVL结构成员是任何但未使用的; 只是没有用在这个特定的功能.我不得不从各种文件中复制/粘贴代码并进行大量更改以呈现上面引用的代码.这是一个我不知道如何解决的问题.我很乐意发布整个节目,但它太大了,用我的母语评论(不是英文!).-Wall和-Wextra启用.根据构建目标自动启用/禁用断言和调试消息.另外我认为嵌套函数不需要函数原型,所有嵌套函数都没有按照定义实现任何外部接口- GCC当然没有抱怨.我不知道为什么在OSX上有这么多警告:(vim,我使用nano(在GNU屏幕内)或者gedit代替(射击我)!无论如何,我更喜欢K&R支撑式:)L' '建议!这是我的第一个"大型"(并且非平凡)计划,我真的很感谢你的建议.
编辑#2:
这是这里提到的"快速和脏"方法的实现.
(编辑#3:我决定把它拆分成一个单独的答案,因为它是OP的有效答案.)
很多回复都提到了Graphviz.我已经知道了(许多Linux应用程序与它相关联)但我认为对于10KB的CLI可执行文件来说会有点过分.但是,我将在未来牢记这一点.看起来很棒.
您需要决定您的代码是否需要可移植。如果您可能需要使用 GCC 以外的编译器，那么嵌套函数对于您的可移植性目标来说是致命的。我不会使用它们 - 但我的可移植性目标可能与您的不同。
\n\n您的代码丢失<wchar.h>；如果没有它，它的编译相当干净 - GCC 抱怨您的非静态函数和 forswprintf()和fputwc()) 缺少原型，但添加<wchar.h>会生成许多与swprintf();相关的严重警告。他们实际上是在诊断错误。
gcc -O -I/Users/jleffler/inc -std=c99 -Wall -Wextra -Wmissing-prototypes \\\n -Wstrict-prototypes -Wold-style-definition -c tree.c\ntree.c:88:6: warning: no previous prototype for \xe2\x80\x98prettyprint_tree\xe2\x80\x99\ntree.c: In function \xe2\x80\x98prettyprint_tree\xe2\x80\x99:\ntree.c:143:10: warning: no previous prototype for \xe2\x80\x98recur_swprintf\xe2\x80\x99\ntree.c: In function \xe2\x80\x98recur_swprintf\xe2\x80\x99:\ntree.c:156:17: warning: passing argument 2 of \xe2\x80\x98swprintf\xe2\x80\x99 makes integer from pointer without a cast\n/usr/include/wchar.h:135:5: note: expected \xe2\x80\x98size_t\xe2\x80\x99 but argument is of type \xe2\x80\x98int *\xe2\x80\x99\ntree.c:156:17: error: too few arguments to function \xe2\x80\x98swprintf\xe2\x80\x99\n/usr/include/wchar.h:135:5: note: declared here\ntree.c:160:13: warning: passing argument 2 of \xe2\x80\x98swprintf\xe2\x80\x99 makes integer from pointer without a cast\n/usr/include/wchar.h:135:5: note: expected \xe2\x80\x98size_t\xe2\x80\x99 but argument is of type \xe2\x80\x98int *\xe2\x80\x99\ntree.c:174:22: warning: passing argument 2 of \xe2\x80\x98swprintf\xe2\x80\x99 makes integer from pointer without a cast\n/usr/include/wchar.h:135:5: note: expected \xe2\x80\x98size_t\xe2\x80\x99 but argument is of type \xe2\x80\x98int *\xe2\x80\x99\ntree.c:174:22: warning: passing argument 3 of \xe2\x80\x98swprintf\xe2\x80\x99 makes pointer from integer without a cast\n/usr/include/wchar.h:135:5: note: expected \xe2\x80\x98const wchar_t * restrict\xe2\x80\x99 but argument is of type \xe2\x80\x98int\xe2\x80\x99\ntree.c:177:13: warning: passing argument 2 of \xe2\x80\x98swprintf\xe2\x80\x99 makes integer from pointer without a cast\n/usr/include/wchar.h:135:5: note: expected \xe2\x80\x98size_t\xe2\x80\x99 but argument is of type \xe2\x80\x98int *\xe2\x80\x99\ntree.c:177:13: error: too few arguments to function \xe2\x80\x98swprintf\xe2\x80\x99\n/usr/include/wchar.h:135:5: note: declared here\ntree.c: In function \xe2\x80\x98prettyprint_tree\xe2\x80\x99:\ntree.c:181:10: warning: no previous prototype for \xe2\x80\x98call_recur\xe2\x80\x99\ntree.c:188:9: warning: no previous prototype for \xe2\x80\x98omit_cols\xe2\x80\x99\n（这是 MacOS X 10.6.5 上的 GCC 4.5.2。）
\n\nswprintf()；它更像是snprintf()（sprintf()这是一件好事\xe2\x84\xa2！）。整体想法很有趣。我建议在提交代码进行分析时选择一种表示形式，并清理与代码分析无关的任何内容。例如，arraystr类型已定义但未使用 - 您不想让像我这样的人对您的代码进行廉价攻击。与未使用的结构成员类似；甚至不要将它们保留为注释，即使您可能希望将它们保留在 VCS 的代码中（为什么？）。您正在使用版本控制系统（VCS），不是吗？这是一个反问句 - 如果您没有使用 VCS，请立即开始使用，以免失去您所珍视的东西。
在设计方面，您希望避免做诸如要求主程序运行晦涩system()命令之类的事情 - 您的代码应该处理此类问题（可能使用初始化函数，也可能使用终结函数来撤消对终端设置所做的更改）。
不喜欢嵌套函数的另一个原因是：我不知道如何获得函数的声明。看似合理的替代方案并没有起作用——但我没有去阅读有关它们的 GCC 手册。
\n\n小问题：您可以告诉那些不使用“vi”或“vim”进行编辑的人 - 他们不会将函数的左大括号放在第 1 列中。在“vi”中，第 1 列中的左大括号为您提供了从函数内部的任何位置开始函数的简单方法（“[[”向后跳转；“]]”跳转到下一个函数的开头）。
\n\n不要禁用断言。
\n\n一定要包含主程序和相关的测试数据 - 这意味着人们可以测试您的代码，而不仅仅是编译它。
\n\n使用宽字符常量而不是强制转换：
\n\nwcharbuf[i][j] = (wchar_t)' ';\nwcharbuf[i][j] = L' ';\n您的代码创建一个大屏幕图像（代码中为 20 行 x 800 列）并填充要打印的数据。这是一个合理的方法。小心地，你可以安排处理画线字符。但是，我认为您需要重新考虑核心绘图算法。您可能希望封装整个绘图代码，以便屏幕图像和相关信息位于单个结构中，该结构可以通过引用（指针）传递给函数。您将拥有一组函数来在树搜索代码指定的位置绘制各种位。您将有一个函数可以在适当的位置绘制数据值；您将有一个在适当位置画线的功能。您可能不会有嵌套函数 - 在我看来，当一个函数嵌套在另一个函数中时，阅读代码要困难得多。使函数静态是好的；使嵌套函数成为静态（非嵌套）函数。为他们提供所需的上下文 - 从而封装屏幕图像。
\n\n请求有关封装的信息...
\n\n您可以使用如下结构：
\n\ntypedef struct columninfo Colinfo;\n\ntypedef struct Image\n{\n wchar_t image[WCHARBUF_LINES][WCHARBUF_COLUMNS];\n Colinfo eachline[WCHARBUF_LINES];\n} Image;\n\nImage image;\n您可能会发现添加一些额外成员很方便和/或明智；这将在实施过程中显现出来。然后您可以创建一个函数：
\n\nvoid format_node(Image *image, int line, int column, DTYPE value)\n{\n ...\n}\n您还可以将一些常量（例如 spaceafter）设置为枚举值：
\n\nenum { spacesafter = 2 };\n然后这些可以被任何函数使用。
\n