第 5 章　数据结构——真正的指针的使用方法 - 5.2　案例学习 2：绘图工具的数据结构 - 《征服C指针》

5.2　案例学习 2：绘图工具的数据结构

5.2　案例学习 2：绘图工具的数据结构

5.2.1　案例的需求

这次让我们考虑开发一个绘图工具，来进一步实践。假定程序的名称为“X-Draw”。

5.2　案例学习 2：绘图工具的数据结构 - 图1

图 5-12　绘图工具“X-Draw”的界面

在 X-Draw 中，可以绘制下面的图形^*，

^{* 也许让大家失望了，这只是个很简陋的绘图工具。}

折线（有任意个顶点的折线）
长方形（不考虑相对坐标轴倾斜的长方形）
圆形（不考虑弧形和椭圆形）

考虑到篇幅，我没有在书中提供所有的程序代码。不管怎么说，窗体程序还是非常依赖运行环境的。

这里只会跟大家说明实现 X-Draw“数据结构”的“头文件”部分。

5.2.2　实现各种图形的数据模型

首先让我们考虑一下怎么表示折线、长方形、圆形等图形。

在第 4 章已经跟大家讨论过折线的表示方式，在这里我们依然采用这种方式。

typedef struct {
    double      x;
    double      y;
} Point;
typedef struct {
    int         npoints;
    Point       *point;
} Polyline;

对于长方形，可以使用处于对角线上的两个点来表示：

typedef struct {
    Point       minPoint; /* 左下的坐标 */
    Point       maxPoint; /* 右上的坐标 */
} Rectangle;

对于圆形，可以用圆心和半径来表示：

typedef struct {
    Point       center; /* 圆心 */
    double      radius; /* 半径 */
} Circle;

补充　坐标系的话题

读到这里，可能有很多人有下面的疑问，

咦？坐标值怎么都搞成了 double？绘制图形的画布不是用像素来表示的吗？我记得坐标值应该是 int 啊？

确实，无论是 X Window System 的图形库 Xlib，还是 Windows 的 API，还是 Java 的 AWT，坐标值都是以像素为单位的整数。

Windows 的情况稍微有点复杂，关于这一点，后面会有说明。

尽管如此，程序内部还是不应该使用以像素为单位的整数值来表示坐标。如果使用以像素为单位的整数值，首先需要解决的问题就是如何实现图像的放大表示。很多工具软件只能做到 200%、400%这样的整倍地放大，使用起来似乎不是很方便。此外，对于稍稍复杂的图形，将它们组合，然后通过操作顶点再将其一会儿放大，一会儿缩小，图形就变得粗糙不堪了吧。

计算机上的图形大多都是用像素（这种方式并不是很细腻）来表示的，这是由显示设备自身的条件造成的，并不是用户一开始就想使用像素来绘制和表示图形。

在画笔工具的情况下，也可能不是这样。

因此，正确的解决方案应该是，首先定义逻辑上假定的用户坐标系，在图形显示的时机再转换成设备坐标系（参照图 5-13）。

有时也称为世界坐标系或者逻辑坐标系。

图 5-13　坐标系变换

因为有“像素”这样的源于设备条件的限制，用户坐标系的坐标值使用 double。另外，设备坐标系的原点大多在左上，而用户坐标系是遵循数学坐标将原点设置在左下，我认为这种做法比较通俗易懂。

^{也可以使用 float。在 C 中，浮点数类型大多都会变成 double，在内存充裕的情况下，最好还是使用 double。}

这还是要根据用途来决定，在文字处理软件中绘图的时候，因为文字是横着从左上写到右下的，如果考虑到这一点，将原点设定在左上也许更方便。

做一些乘法运算和减法运算，可以简单地将用户坐标和设备坐标进行转换。

最一般的做法，可以采用矩阵。

此外，Windows 从设备坐标系独立出来一种自定义的逻辑坐标系，它可以以毫米为单位进行图形绘制。但……此时坐标值的类型却为 short int，这样的设计思路，好像完全超出了我的理解能力……

5.2.3　Shape型

5.2.2 节中讨论了各图形的表示方法。对于绘图工具，还需要管理大量各种各样的图形进行管理。

在这里，我们使用 Shape 这样一个结构体来表示一个“图形”。

对于“图形”来说，它应该有颜色这样的属性。如果内部被涂满，那就还有填充方式这样的属性。下面使用枚举的方式来表示这些属性。

typedef enum {
    COLOR_BLACK,   /* 黑 */
    COLOR_BLUE,    /* 蓝 */
    COLOR_RED,     /* 红 */
    COLOR_MAGENTA, /* 品红 */
    COLOR_GREEN,   /* 绿 */
    COLOR_CYAN,    /* 青*/
    COLOR_YELLOW,  /* 黄*/
    COLOR_WHITE    /* 白 */
} Color;
typedef enum {
    FILL_NONE,      /* 不填充 */
    FILL_SOLID,     /* 实心填充 */
    FILL_HATCH,     /* 斜线图案填充 */
    FILL_CROSSHATCH /* 交叉图案填充 */
} FillPattern;

在一开始我们是无法预测图形的数量的，所以考虑使用 malloc()为 Shape 动态地分配内存区域，然后通过链表对它们进行管理。

考虑到以下原因，我们选择双向链表，

对所有的图形进行重绘的时候，“从后面的图形开始顺序地”绘制，能够以正确的顺序表示各图形。
使用按下鼠标的方式选择图形的时候，需要从“前面的图形开始顺序地”检查哪个图形才是选择对象*。

^{* 在绘图工具中，基于通过鼠标来选择图形（pick），经常需要运用几何方法来计算距离。}

对于 Shape，它可能代表折线，可能代表长方形，也可能代表圆，使用 C 的结构体和共用体来表示 Shape 是惯用的手法（下面就是实际的例子）。

根据上面的分析，可以用下面的方式来表示 Shape 类型：

typedef enum {
    POLYLINE_SHAPE,
    RECTANGLE_SHAPE,
    CIRCLE_SHAPE
} ShapeType;
typedef struct Shape_tag {
    /* 画笔（轮廓）的颜色 */
    Color       pen_color;
    /* 填充样式，FILL_NONE 的时候不填充 */
    FillPattern fill_pattern;
    /* 填充颜色 */
    Color       fill_color;
    /* 图形的种类 */
    ShapeType   type;
    union {
        Polyline        polyline;
        Rectangle       rectangle;
        Circle          circle;
    } u;
    struct Shape_tag *prev;
    struct Shape_tag *next;
} Shape;

ShapeType 是一个用于区别 Shape 种类的枚举类型，根据 Shape 的成员 type，可以判定 Shape 的种类。

假设，将指向 Shape 的链表的头指针放到 head 这样一个变量中，“绘制所有图形的程序”大致可以写成下面这样：

Shape *pos;
for (pos = head; pos != NULL; pos = pos->next) {
    switch (pos->type) {
      case POLYLINE_SHAPE:
        /* 调用绘制折线的函数 */
        draw_polyline(pos);
        break;
      case RECTANGLE_SHAPE:
        /* 调用绘制长方形的函数 */
        draw_rectangle(pos);
        break;
      case CIRCLE_SHAPE:
        /* 调用绘制圆形的函数 */
        draw_circle(pos);
        break;
      default:
        assert(0);
    }
}

因为是从链表的第一个元素开始绘制图形，所以链表后面的元素会被表示在前面。

在大多的绘图工具中，通过点击鼠标选择一个图形，然后可以将它移动到最前面或最后面。此时，需要将图形对应的元素在链表中进行移动，图形要移动到最前面，元素就要移动到链表的末尾；图形要移动到最后面，元素就要移动到链表的最前面。

做这样的元素移动，那是链表的强项。

5.2.4　讨论——还有别的方法吗

到这里为止我们讨论过的方法好像都还不错，但还是让我们再想想有没有更好的解决方案。

可能有人会有下面的想法，

俺所知道的绘图工具中，经常需要的功能倒不是什么绘制折线，绘制“线段”倒挺常见的。虽然菜单中也有折线，但是经常使用的是“线段”。因此，是不是应该也有一个 Line 这样的类型呢？

我平时使用 UNIX 的 tgif 这个工具比较多一些，在这个工具的菜单中前面出现的就不是“线段”，而是“折线”。确实，在 Windows 和 Macintosh 中的绘图工具的菜单中出现的大多还是“线段”。

“线段”经常出现在菜单的最前面，证明对于用户来说，相比“折线”，绘制“线段”功能的使用会更加频繁^*。但即使是这样，如果用户选择了位于菜单最前面的“线段”选项，程序能够很简单地绘制出“顶点数目为 2 的折线”，那么就不需要特地再搞出一个什么 Line 类型了吧。

^{* 到底是不是这样，我还真说不好。但至少作为软件设计者，肯定应该这样去考虑。}

即使 Windows 中的绘图工具总是将折线功能藏在菜单层次结构的里面，但这种功能毕竟是存在的，并且，作为折线的修正功能，肯定也会有“增减折线顶点的功能”吧。此外，恐怕也会有增加线段的顶点的功能吧。因此，线段的内部使用折线来实现，应该是一个不错的方案。如果定义了新的 Line 类型，就又需要开发一个“一旦在 Line 上添加了顶点，就要将它转换成 Polyline 类型”这样的功能了。

这样说来，是不是有人又会有下面的想法：

嗯，长方形可以用顶点数为 5 的折线来表示，那 Rectangle 类型是不是也可以不要了？

这可不行！假设我们选中一个顶点进行拖拽，对于长方形和折线图形如何变化，我们的期待肯定是不一样的吧？

让我们再把目光投向内部实现，此时也许又会出现下面的观点：

折线必须要实现“增减顶点”的功能，所以对于折线的 Point，不应该用可变长数组，而应该使用链表来表示。

追加顶点的时候，往往是在顶点和顶点之间插入新顶点，因此，相比使用数组，链表的插入操作更简单。

这倒是一个比较麻烦的问题，不能断然说哪个观点就是正确的。

但是，Point 类型只包含两个 double 元素，相对来说比较小。对于绘图工具，折线顶点的数量也是可以预期的。因此，Point 的数组也不会变得很大，可以说不会发生导致执行效率低下的现象（追加顶点时，使用 realloc() 不断地分配内存区域，或者在插入顶点时，整体移动后方的元素）。倒是为了使用链表，在成员中追加指针，或者为每一个 Point 使用 malloc()分配管理空间这样的行为反而会引起严重的问题。

如果对 malloc()的管理区域比较在意的话，可以使用可变长结构体来构造 Polyline 类型呀！

对啊，如果使用 4.3.1 节中介绍的技巧，就可以不用调用 malloc()为 Point 数组来分配新的内存区域了！……但是，由于 Polyline 不是 Shape 结构体的最后成员，一旦使用这个技巧，就会破坏掉 prev 和 next 的数据。

调整一下 Shape 结构体成员的顺序看上去好像可行，但折线的顶点个数一旦发生变化，就必须为每一个 Shape 调用 realloc()，当前的 Shape 的地址也会随之发生变化（有可能）。由于 Shape 在双向链表中，它被前后两个 Shape 所指向，一旦移动了地址，自然麻烦也随之而来。因此，这个方法也不靠谱。

前面我们使用了共用体。共用体会根据其最大的一个成员来分配内存空间，这是不是有点浪费内存？

倒是有点道理。但是这次的 Polyline、Rectangle 和 Circle 的大小，在大多数处理环境中都是差不多的。

如果这些类型的大小完全不同，当然也不能无视内存的浪费。此时，也可以考虑使用“指针共用体”^*，然后通过 malloc()给 Polyline、Rectangle 和 Circle 分配内存区域。

^{* 当然也可以使用 void，但此时完全不知道指针指向什么类型，所以从代码的可读性上考虑，还是应该使用指针的共用体。}

typedef struct Shape_tag {
        ┊
    union {
        Polyline        *polyline;     /*（以下3行）指针的共用体*/
        Rectangle       *rectangle;
        Circle          *circle;
    } u;
    struct Shape_tag *prev;
    struct Shape_tag *next;
} Shape;

此时，刚才的“应该把 Polyline 构造成可变长结构体”这种方案也就具备了现实的意义。

但是，正如刚才描述的那样，因为 Polyline、Rectangle、Circle 的大小并没有很大差异，考虑到使用 malloc()需要额外的管理内存，或者消耗在调用 free()上的精力，所以我不会考虑通过别的方式分配内存。

在 Shape 中放进 prev 和 next 的做法也让人觉得不太自然。Shape 只是一个“图形”，使用链表来管理还是使用数组来管理，这是使用者的自由，为什么我们一开始就先入为主地认为 Shape 天生就应该通过双向链表来管理呢？这一点本身就很奇怪。

这个批评不无道理。我们经常将链表和本来无关的 Shape 放在一起使用，此时有人会想：那就将 prev 和 next 设定为 NULL 好了。但将原本就不需要的对象作为成员，你不觉得奇怪吗？

因此，让我们来看看下面这个方案。这个方案不需要在 Shape 中放入 prev 和 next，而是像下面这样定义一个 LinkableShape 类型，Shape 作为这个类型的一个成员（参照图 5-14）。

5.2　案例学习 2：绘图工具的数据结构 - 图3

图 5-14　Shape 的持有方式（其 2）

typedef struct LinkableShape_tag {
      Shape shape;
      struct LinkableShape_tag *prev;
      struct LinkableShape_tag *next;
  } LinkableShape;

或者写成这样，

typedef struct LinkableShape_tag {
      Shape *shape;
      struct LinkableShape_tag *prev;
      struct LinkableShape_tag *next;
  } LinkableShape;

在图 5-14 的实现中，保存 Shape 到链表的时候，需要将 Shape 整个复制到链表中。复制这样的操作肯定会改变 Shape 的地址，后果就是丢失了指向 Shape 的指针。

如果采用图 5-15 的方法，就没有这样的担心了。但会出现另外一个问题：随着 malloc()调用次数的增加，会浪费一些管理区域的内存，而且也要在 free()调用上花费相当的精力。

5.2　案例学习 2：绘图工具的数据结构 - 图4

图 5-15　Shape 的持有方式（其 3）

但是，对于本例这样的结构体，考虑到实现简单，在 Shape 中放入 prev 和 next 其实也没有什么问题。

通过上面种种分析，我们应该能体会到，对于数据结构的设计，其实说到底就是权衡利弊的过程，根本就不存在所谓的“银弹”¹。对于数据的特征以及使用方式进行细致的分析，并且选择最合适的手法，这是程序设计者的责任。同时，设计者还要熟知 malloc()、realloc()的内部实现机制。

^{1 银弹：出自《人月神话》，指那些可以解决所有问题的方法论，可以理解成“一招鲜”。——译者注}

另外，设计者不但需要根据现状决定使用方法，还要考虑到将来的扩展性，以及执行速度、内存使用这两个方面的最优化设计。最后，还要考虑到编程的可行性。在设计数据结构这一点上，最能体现设计者的水平。

补充　什么都放的链表

进一步考虑图 5-15 的方案，应该还有以下的方法：
typedef struct Linkable_tag {
   void object;
   struct Linkable_tag prev;
   struct Linkable_tag next;
} Linkable;
Linkable 的成员变量 object 的类型是 void\，所以它可以指向任意类型。也就是说，在 Linkable 类型不依赖于 Shape 类型，它可以存储任意类型。

大部分情况下，双向链表都会拥有指向初始元素和末尾元素的指针，为了能够持有整个双向链表，有必要定义下面这样的类型：
/ 持有全体双向链表的类型 /
typedef struct {
   Linkable head;  / 初始的元素 /
   Linkable tail;  / 末尾的元素 /
} LinkedList;
双向链表是使用很频繁的一种数据结构，但使用双向链表进行开发的时候，每次都重复做“在某元素前面插入一个元素”这样无聊的编程，既浪费时间又容易引起 bug。

此时，可以使用 LinkedList 或者 Linkable 这样的类型，如果将双向链表的常用操作整理成函数库来加以利用，就可以省去那些无聊的重复编程。

可是，在大型项目中，这个方法也有致命的弱点。造成这个弱点的起因就是“什么都可以扔进去”。向保存 Shape 的链表中无限制地放入“白萝卜”还是“胡萝卜”总是会出问题的（编译时不会出错）。

此外，也完全不知道 LinkedList 中究竟保存了什么。假设，使用 Point 的链表来表示 Polyline：
typedef struct Point_tag {
   double x;
   double y;
   struct Point_tag prev;
   struct Point_tag next;
} Point;
　
typedef struct {
   Point head;
   Point tail;
} Polyline;
看一眼上面的代码，基本可以知道数据结构中的内容。
typedef struct {
   LinkedList list;
} Polyline;
如果这样，那就真不知道 list 是什么东东了。就算好不容易搞明白它是个链表，你也无法知道它其实是个“Point 类型的链表”（除非你加上注释）。这对程序的可读性和可维护性产生了恶劣的影响。

顺便介绍一下，Java 的集合类库中也有和此处介绍的 void*方式类似的实现。

java.lang.Object 相当于 C 的 void*，它们都是最邪恶的指针。

对于 C 这样的骨灰级语言，已经没有必要解决这样的问题了。在一些最新的语言中，为了持续维持 LinkedList 的通用性和杜绝 void*的危险性，实现了叫做“泛型（genericity）”和“模板（template）”的功能。

Java 中缺少这么一个重要的功能，真是让人不解。

C#里也似没有²……

^{2 C#从.NET2.0 开始也具备了泛型和模板的功能。——译者注}

对于 C++、Ada 这样可以操作对象实体的语言，泛型伴随着复制执行代码的问题。但是，对 Java 这样只能使用指针的语言来说，只要在编译时加入一些检查就可以简单地实现这个功能。

现在，也出现嵌入泛型功能的 Java 编译器。（参照 http://www.cs.bell-labs.com/who/wadler/gj）。（第 8 印注：在 JDK1.5 中被正式采用。）

5.2.5　图形的组合

几乎在所有的绘图工具中，都可以将几个图形进行组合，然后当作一个图形去操作。本节中也考虑将这个功能在 X-Draw 中实现。

首先定义一个 Group 类型。虽然 Group 类型需要包含很多 Shape，但是 Shape 自身可以实现双向链表，所以只要在 Group 中定义指向初始元素和最后元素的指针就可以了。

typedef struct {
    Shape   *head;
    Shape   *tail;
} Group;

所谓图形组合就是“将几个图形组合成一个图形”的功能。被组合到一起的图形组，其自身也可以说是一种“图形”。因此，可以考虑将“Group”加入到枚举类型 ShapeType 中。

typedef enum {
    POLYLINE_SHAPE,
    RECTANGLE_SHAPE,
    CIRCLE_SHAPE,
    GROUP_SHAPE
} ShapeType;

但是，可能有人觉得这么做有些不和谐，让 Group 和 Polyline、Rectangle 相提并论真的有些奇怪。

因为 Group 也是一个 Shape，所以我倒认为这么做未尝不可。只是对于 Shape 来说，它虽然有自己的颜色或者填充图案，但“组合后的图形”的颜色就不是固定的。将图形进行组合，然后去变更其颜色，整组的图形颜色都会发生变化。但之后如果解除了图形的组合，其每一个图形都不会变回原来的颜色，因此你不能说这是一个“变更组合图形的颜色”的功能，准确地应该说这是一个“变更组内所有图形的颜色”的功能。

在这里，让我们首先把 Shape 分类成折线、长方形这样的“基本图形”和“组”。

typedef enum {
    PRIMITIVE_SHAPE,
    GROUP_SHAPE
} ShapeType;
typedef struct Shape_tag {
    ShapeType           type;
    union {
        Primitive       primitive;
        Group           group;
    } u;
    struct Shape_tag *prev;
    struct Shape_tag *next;
} Shape;

然后，将到现在为止 Shape 中持有的数据放到 Primitive 类型中。

typedef enum {
    POLYLINE_PRIMITIVE,
    RECTANGLE_PRIMITIVE,
    CIRCLE_PRIMITIVE
} PrimitiveType;
typedef struct {
    /* 画笔（轮廓）的颜色 */
    Color       pen_color;
    /* 填充样式，FILL_NONE 的时候不填充 */
    FillPattern fill_pattern;
    /* 填充颜色 */
    Color       fill_color;
    /* 图形的种类 */
    PrimitiveType   type;
    union {
        Polyline        polyline;
        Rectangle       rectangle;
        Circle          circle;
    } u;
} Primitive;

此时，包含“组”的 Shape 数据结构，就变成图 5-16 的形式。看上去好像和 5.1.6 节中列举的例子有些不同，其实它也是一种树结构。

5.2　案例学习 2：绘图工具的数据结构 - 图5

图 5-16　包含“组”的 Shape 数据结构

包含到此为止涉及的所有类型的头文件，如代码清单 5-15 所示，

代码清单 5-15　Shape.h

 1:  #ifndef SHAPE_H_INCLUDED
 2:  #define SHAPE_H_INCLUDED
 3:   
 4:  typedef enum {
 5:      COLOR_BLACK,                /* 黑 */
 6:      COLOR_BLUE,                 /* 蓝 */
 7:      COLOR_RED,                  /* 红 */
 8:      COLOR_MAGENTA,              /* 品红 */
 9:      COLOR_GREEN,                /* 绿 */
10:      COLOR_CYAN,                 /* 青 */
11:      COLOR_YELLOW,               /* 黄 */
12:      COLOR_WHITE                 /* 白 */
13:  } Color;
14:   
15:  typedef enum {
16:      FILL_NONE,                  /* 不填充 */
17:      FILL_SOLID,                 /* 实心填充 */
18:      FILL_HATCH,                 /* 填充斜线图案 */
19:      FILL_CROSSHATCH             /* 填充交叉阴影线 */
20:  } FillPattern;
21:   
22:  typedef enum {
23:      POLYLINE_PRIMITIVE,
24:      RECTANGLE_PRIMITIVE,
25:      CIRCLE_PRIMITIVE
26:  } PrimitiveType;
27:   
28:  typedef struct {
29:      double      x;
30:      double      y;
31:  } Point;
32:   
33:  typedef struct {
34:      int         npoints;
35:      Point       *point;
36:  } Polyline;
37:   
38:  typedef struct {
39:      Point       minPoint;       /* 左下的坐标 */
40:      Point       maxPoint;       /* 右上的坐标 */
41:  } Rectangle;
42:   
43:  typedef struct {
44:      Point       center;         /* 圆心 */
45:      double      radius;         /* 半径 */
46:  } Circle;
47:   
48:  typedef struct {
49:      /* 画笔（轮廓）的颜色 */
50:      Color       pen_color;
51:      /* 填充样式，FILL_NONE 的时候不填充 */
52:      FillPattern fill_pattern;
53:      /* 填充的颜色 */
54:      Color       fill_color;
55:      /* 图形的种类 */
56:      PrimitiveType   type;
57:      union {
58:          Polyline        polyline;
59:          Rectangle       rectangle;
60:          Circle          circle;
61:      } u;
62:  } Primitive;
63:   
64:  typedef struct Shape_tag Shape;
65:   
66:  typedef struct {
67:      Shape   *head;
68:      Shape   *tail;
69:  } Group;
70:   
71:  typedef enum {
72:      PRIMITIVE_SHAPE,
73:      GROUP_SHAPE
74:  } ShapeType;
75:   
76:  struct Shape_tag {
77:      ShapeType           type;
78:      union {
79:          Primitive       primitive;
80:          Group           group;
81:      } u;
82:      struct Shape_tag *prev;
83:      struct Shape_tag *next;
84:  };
85:   
86:  #endif /* SHAPE_H_INCLUDED */

Shape 类型的定义依赖于 Group 类型，Group 类型的定义又依赖于指向 Shape 类型的指针，因此它们之间形成了相互依赖的关系。第 64 行利用不完全类型声明了 Shape 类型。76 行以后给 struct Shape_tag 定义了实际的内容。

至于使用此数据结构的程序，比如“绘制所有图形”的程序，如代码清单 5-16 所示。

代码清单 5-16　draw_shape.c

 1:  #include <stdio.h>
 2:  #include <assert.h>
 3:  #include "shape.h"
 4:   
 5:  void draw_polyline(Shape *shape);
 6:  void draw_rectangle(Shape *shape);
 7:  void draw_circle(Shape *shape);
 8:   
 9:  void draw_primitive(Shape *shape)
10:  {
11:      switch (shape->u.primitive.type) {
12:        case POLYLINE_PRIMITIVE:
13:          /* 调用绘制折线的函数 */
14:          draw_polyline(shape);
15:          break;
16:        case RECTANGLE_PRIMITIVE:
17:          /* 调用绘制长方形的函数 */
18:          draw_rectangle(shape);
19:          break;
20:        case CIRCLE_PRIMITIVE:
21:          /* 调用绘制圆的函数 */
22:          draw_polyline(shape);
23:          break;
24:        default:
25:          assert(0);
26:      }
27:  }
28:   
29:  void draw_all_shapes(Shape *head)
30:  {
31:      Shape       *pos;
32:   
33:      for (pos = head; pos != NULL; pos = pos->next) {
34:          switch (pos->type) {
35:            case PRIMITIVE_SHAPE:
36:              draw_primitive(pos);
37:              break;
38:            case GROUP_SHAPE:
39:              draw_all_shapes(pos->u.group.head);
40:              break;
41:            default:
42:              assert(0);
43:          }
44:      }
45:  }

图形的具体绘制方式依赖于各窗口图形系统，在代码清单 5-16 的第 5～7 行，假定了传入指向 Shape 类型的指针就可以绘制对应图形的几个函数^*。

^{* 从常识来说，非 static 函数的原型声明不应该写在.c 文件中。外部函数的原型声明必定写在头文件中，被多个头文件共用。此处的例程，只是为了通过编译（不出警告），暂时做了这样的原型声明。}

第 39 行通过对 draw_all_shapes()递归调用来实现图形组合的绘制。在这种需要遍历树结构的情况下，使用递归调用是常用的手法。

5.2.6　继承和多态之道

本书是一本关于 C 语言的书籍，所以到现在为止，只是在 C 语言的功能范围内讨论了绘图工具的数据结构。

其实，前面介绍的方法中存在比较严重的问题，它就是：

为了区别处理各种图形，switch case 这样的语句散落在程序的各个角落。

代码清单 5-16 的第 11 行开始出现的 switch case，不只是出现在图形绘制的时候，在使用鼠标选择图形而进行距离计算的时候，以及将整体图形保存在文件中，或者从文件中加载图形的时候，都会出现 switch case 的身影。

像这样在程序中到处写 switch case 的编程风格，一旦增加了一种图形，就必须在分散在各处的 switch case 中挨个追加 case。不但麻烦，还很容易疏漏^*。

^{* 在代码清单 5-16 中的 default 中的 assert()，可以在早期就发现这种疏漏。}

在 C++或者 Java 等面向对象的语言中，通过使用继承和多态，可以在很多实现中回避 switch case。

简单地说，面向对象的语言有以下这些功能：

在面向对象的类（粗暴地说，它类似于结构体）中，不但可以有变量，还可以放入函数，这些函数我们称为“方法”。
在面向对象的语言中，可以对现有的类进行扩展，做出一个新的类，这种行为被称为继承（inheritance）。比如，Polyline 继承了 Shape。
继承类的方法可以覆盖（override）被继承类的方法。

使用这个功能，可以将 draw() 这个方法放到 Shape 中，然后针对 Polyline 或者 Rectangle 做 draw()的具体实现，“绘制所有图形的程序”就可以大致写成下面这样（C++风格）：

for (pos = head; pos != NULL; pos = pos->next) {
    pos->draw();   ←调用pos 指向的Shape 的draw()方法
}

这么写的话，如果 pos 是 Polyline 就自动调用 Polyline 的 draw()方法，如果 pos 是 Rectangle 就自动调用 Rectangle 的 draw()方法。就没有必要再使用 switch case 来区分处理了。这样的特征我们称为多态（polymorphism）。

如果想要用 C 来实现多态，可以考虑让每一个 Shape 持有一个指向结构体的指针，而在结构体中包含函数指针。这样的做法很流氓。其实，在 X Window System 的 GUI 工具包 Xt Intrinsics 和 GTK+中，就是通过这样的方法勉强地实现了多态。但这种方式毕竟还是太暴力了，在一般开发中还是建议大家老老实实地使用 switch case。

编程语言是在不断发展的，每一种新的语言都会推出一些有用的新功能。

补充　真的可以将 draw()放到 Shape 中吗？

将 draw()方法定义到 Shape 中，然后利用多态的特征将处理分开，很多面向对象的入门书都将这个案例作为例题来讲解。比如，在《编程语言 C++ 第 3 版^[9]》中，就利用 Shape 的例子来说明多态。

在我看来，对于最多几万行代码的小规模程序，“在 Shape 中定义 draw()”这种手法还是很有效的。可是，如果是像 CAD 这样庞大的系统，有时就需要尽量回避这种手法。

定义了 Shape 等类型的 shape.h，是全体程序中最主要的头文件，其中的大量内容被所有的程序引用。因此，必须非常谨慎地定义 shape.h 的内容，因为一旦内容确定了，以后再修改就不是那么简单的了。

因为 draw()方法的实现特别依赖于窗口的图形系统，如果将 draw() 方法放到 shape.h 中，就会发生严重的可移植性的问题。像 C++那样将方法的声明和实现分开还好，如果是 Java 那就比较麻烦了³。

^{3 Java 中根本没有头文件，在这里，原著作者先把话题指向头文件，然后拿 C++和 Java 进行对比，这是不公平的。况且 Java 中也可以通过 interface 将声明和实现分开。在此书翻译过程中，译者认为原著作者对 Java 有着很深的偏见和误解。——译者注}

正是这种情况下我们才要考虑设计模式^[10]呀！如果想要不依存窗口图形系统，为什么不考虑使用 Bridge 模式呢？

可能有人会有上面的想法。可是，抽象出可以对应现实中所有窗口图形系统的绘图接口，是非常困难的。比如在如今的图形系统（X Window、 Windows、Java AWT）中，“将线从这里画到那里”这样的即时绘图，和很久以前作为标准的 GKS就有概念上的差异。

Graphical Kernel System，它是 ISO 制定的二维图形库的国际标准。GKS 通过“segment”采用了显示列表模型。

因此，在根本概念发生变化的时候，对于程序这方面，废弃掉原来的程序，重新开发也许就能解决问题。但是，相比程序，系统数据的生命周期要长很多，所以需要尽可能不改变原来的数据结构（这里就是指 shape.h）。

另外，在 CAD 等系统使用的数据中，图形（形状）数据不只是被 draw() 所用。比如，利用 CAD 设计出的图形会被保存在文件中，其他的应用程序也可以读取这些文件中的数据，并且可以对它们进行解析。对于解析的处理来说，shape.h 也许是不可缺少的，但是其中的 draw()其实是完全用不上的。“数据”往往会超越原本设计其“数据结构”的人的意志，被很多其他的应用程序使用。

那么，对于 C 语言，最终的方案是什么？将数据和处理过程分开是一个好的解决方案。问题是，为了区分图形种类而产生的 switch case。比起数据的生命周期，试图废弃一部分程序逻辑时，也不是只能使用 switch case。除此之外，还可以考虑使用 Vistor 模式。在 Vistor 模式中，Polyline 和 Rectangle 并存于 Vistor 一侧，所以这种手法和 switch case 相比好像换汤不换药。或者在所有的 Shape 中，只定义将“形状”变换成折线的方法，而将 draw()方法放到类的外面；抑或，在 Shape 中只保留一个指向“定义了运行时执行逻辑的对象”的指针，然后在从文件中加载 Shape 实例时，通过 Abstract Factory 模式实例化出特定的运行时对象……

这也是一种设计模式。

唉，总是有无尽的烦恼纠缠在程序设计者周围。

5.2.7　对指针的恐惧

大多的绘图工具，都有图形“复制”功能。比如，如果是 Windows 上的工具，通过选择图形→复制→粘贴，就可以完成图形的复制。

/* 将指向被复制图形的指针放在new_shape 中 */
Shape *new_shape;
new_shape = malloc(sizeof(Shape));
*new_shape = *shape;   ←通过结构体赋值将Shape 结构体赋予new_shape
/* 将new_shape 连接到链表的末尾 */

同学，你知道上面的代码中，哪里有问题吗？

如果被复制的图形是长方形或者圆，上面的方法是没有缺陷的。可是，一旦使用上面的方法对折线进行复制，会怎样呢？

Polyline 中只是持有指向它的坐标群（Point 的可变长数组）的指针，坐标群自身其实是保存在其他的内存区域中的。因此，即使通过结构体一次赋值的方式对 Shape 进行复制，坐标群自身却并没有被复制。结果就是，多个 Shape 共享了同一个坐标群。

这种状态显然不是我们原本期待的结果。只要变化了一个折线的坐标，其他折线的坐标也会跟着一起变化。还有，在删除某折线时使用了 free()释放坐标群的内存区域，就会发生重大的问题。其中的缘由已经在 2.6.4 节中向大家说明过了。

就像这样，如果指针指向了一个偏离程序员意图的对象，调试是异常困难的。上面的折线的例子还算比较简单，一旦图形中更加复杂的数据结构的指针纠结到一起，结局往往惨不忍睹。

5.2　案例学习 2：绘图工具的数据结构 - 图6

图 5-17　多个 Shape 共享一个坐标群

人们有时说：“指针很可怕。”他们大多是想表达下面的意思吧，

C 语言的指针一旦指向一个奇怪的地址，程序往往会在一个不起眼的地方崩溃。

其实，我认为真正的可怕之处在于：

因为引用关系的相互纠葛而导致程序调试非常困难。

前者的恐惧是 C 语言的特性带来的，而后者的恐惧，伴随着所有的持有指针的语言^*。

^{* 有 GC（Garbage Collection）功能的语言，也只能回避 free()的相关问题。}

随便提一下，Pascal 的作者 Niklaus Wirth 认为，数据结构中的指针对应于用于逻辑跳转的 goto（《算法+数据结构=程序》^[11] p.192）⁴。确实，对此我也深有同感，但至少在目前，不使用指针，还是无法构造出复杂的数据结构^*。

^{4 goto 是目前很多编程规范中提倡尽量避免使用的逻辑跳转方式。在此，Niklaus Wirth 的意思是指针和 goto 一样，应该尽量避免使用。——译者注}

^{* 正如一度提倡使用 if、for、while 这样的控制结构来取缔 goto 一样，如果普及使用集合类库，程序员不用顾及指针，也可以轻松操作像链表这样频繁使用的数据结构。尽管如此，我并不认为完全不使用指针的情况下，能解决所有的问题。}

5.2.8　说到底，指针究竟是什么

本章从“数据结构”这个侧面，对指针进行了说明。

在单向链表、双向链表、树、哈希（链式）的图解中，“箭头”必然会登场。这个“箭头”，就是指针。

在设计数据结构的时候，如果不使用“箭头”，就很难设计出“像样的”数据结构。因此，“指针”是构造“像样的”数据结构时必需的概念，如今“像样的”程序都会使用指针。

如果要说起 C 语言指针特有的功能，那就不得不提到它和数组之间微妙的可交换性。关于这一点，在第 4 章进行了完整的说明。

对于 C 语言，我们经常听到下面的观点：

C 语言和硬件关系密切，为什么这么说，因为 C 语言中有指针。

对于早期的编程，或者现在有时也能见到的操作系统内核编程，也许可以认为指针和硬件关系密切。

但只要你能很好地理解第 4 章的那些常用用法，还有第 5 章中介绍的将指针作为箭头来使用的方法，仅仅是使用 C 语言来开发应用程序应该是游刃有余了。

我想，“将指针作为箭头来使用”这个“真正的指针的使用方法”，对于其他语言也同样适用。

5.2 案例学习 2：绘图工具的数据结构

5.2 案例学习 2：绘图工具的数据结构

5.2.1 案例的需求

5.2.2 实现各种图形的数据模型

5.2.3 Shape型

5.2.4 讨论——还有别的方法吗

5.2.5 图形的组合

5.2.6 继承和多态之道

5.2.7 对指针的恐惧

5.2.8 说到底，指针究竟是什么

5.2　案例学习 2：绘图工具的数据结构

5.2　案例学习 2：绘图工具的数据结构

5.2.1　案例的需求

5.2.2　实现各种图形的数据模型

5.2.3　Shape型

5.2.4　讨论——还有别的方法吗

5.2.5　图形的组合

5.2.6　继承和多态之道

5.2.7　对指针的恐惧

5.2.8　说到底，指针究竟是什么