About utils data_structures module

关于util/data_structures模块

内容简介

这个模块被命名为数据结构，里面存放的是各种数据结构的实现。基本的如链表、队列、栈等，分别对应一组*.{c,h}。有的高级数据结构也放在这里，比如鼠标指针。在编写客户端控件的时候，见得最多的应该还是“对象”这种结构，它实现在object.{c,h}里。这个结构使用了多叉树的二叉树表示法，只是跟传统的多叉转二叉有微妙的区别。从名字来看，设计者的目标大概是用object这个结构去模拟面向对象语言里的对象，但是结果并没有实现继承，而是实现了一个完全不相关的多叉树。总的来说，这个结构对控件的组织还是确实有利的。

跟其他模块一样，这个数据结构模块也有一个external.h一次性包装所有的头文件，再在include/目录里建立一个data_structures.h指向这个external.h，让外面的模块去使用。这一点的损益很值得讨论，之后会再详细说。

疑问

有的算法是不涉及复杂数据结构的，经典的比如快速排序。这些算法放到utils/data_structures模块里就很容易让人产生怀疑，到底是否合适，毕竟这个模块的名字是“数据结构”，而不是“算法”。一种考虑是新建一个utils/algorithms模块，专门用来放算法。但是这也有问题，人家都说算法和数据结构是不可分割的，这倒确实没错，毕竟链表和遍历链表的算法怎么想都应该放在一个模块里。

其实上面的说法也有问题，原因只要参考C++里的STL即可。STL里有一个与数据结构分开的algorithm头文件，这里面的函数模板都是使用各种Iterator作为参数的，而Iterator可以用在几乎任意的STL数据结构上，所以这个算法头文件里的函数也能用于STL自己实现的复杂数据结构，可以理解为是确实把某些算法和数据结构分开了。

结论

EGUI目前的数据结构并没有抽象出Iterator，而是每个结构只能用它自己的方法操作。就目前的这个状况，只保留data_structures是最好的。至于怎么把类似快速排序这样的算法放进去，我的解决方案是新建一个专门用来做这个的数据结构。就好像在Java或Python里，很多时候都会把一个算法封装在特制的类里，这个类只用来完成这个算法，类的数据成员就存放这个算法的各种中间结果。这样的一个好处是算法的执行周期可以不连续，新建一个对象之后，由于对象的数据成员保存了算法的执行状态，我们可以在适当的时候允许代码临时退出算法执行，在需要的时候再回来继续。

当然快速排序这样的简单算法，并不值得单独新建一个这样的类。实际上这个例子不是很好，我暂时也想不出应该怎么设计出融入到EGUI风格的解决方法。目前的解决方案其实比上面说的还要差，比如之前我添加的一个“遍历两点之间直线上的像素”的算法，就由于它跟几何方面的贴近性，就简单把它放到了utils/geometry模块里。根据上面说的方法，应该要考虑把整个geometry模块都融合到数据结构模块里去，因为前者包含了point、line这样的数据结构。