BYR Achieve · 镜像论坛

编程手册-----身边的数据结构

2007/10/30镜像同步7 回复

编程手册-----身边的数据结构身边的数据结构，谈起数据结构，很多同学都已经非常熟悉了(至少对名字)。很多时候，我们都会下意识地知道一个道理：数据结构，是编程领域的一门基础。似乎学习了数据结构，编程就多了一份把握，多了一些向别人证明自己编程能力的筹码。有些人甚至将数据结构学得很熟，在与别人谈起时总是头头是道。但我想，其中有很多同学会有这种感觉，在实际的编程中，没有感到数据结构被使用到。这是怎么回事呢？数据结构真的只是高层建筑吗？数据结构真的那么难以碰见吗？为什么我编程时就没有用到数据结构？难道数据结构只是理论范畴中神秘的文字符号？数据结构是一群理论家在无聊之余随手诞生的产物吗？要回答这个问题，答案有很多种。为了快些得到答案，我们打算一起来做个项目。请同学们跟我一起来，看看数据结构是怎样产生及为什么会被理论家们看中的？项目要求：做一个游戏2D界面，界面上有各种元素，响应消息。首先，我们想到很多元素，就是一个数组。只要将数组中的元素全部画到界面上即可。但需求并没有告诉我们元素的数目，创建数组却是固定大小的，我们不希望空间不够，也不想浪费空间。于是我们只好选择收到创建元素请求时才去创建元素。这样我们就做了一些不断new的工作。但这些元素是需要管理的，不然我们不知道哪个先画哪个后画，以及一共有多少个元素等相关信息。这使我们不得不把一个链将这些元素串起来。而最初，我们是根据先后画的顺序将它们串起来的。于是简单的链表产生了。然后，我们要作响应消息的处理，比如我们要做个元素被单击的处理。我们希望点击界面上的某一点时，查看这点正好在哪个元素内。于是我们按刚才的链表一个一个元素地判断。但这样的实验结果并不如我们预期，我们发现，当一个点击位置在两个元素的共有区域时，链表中的前一个元素一定是先被响应。而前个元素比它后面的元素先画。这就使得我们在界面上看，是画在后面被盖住的元素先于前面的元素响应消息，这与我们的习惯相违背。这样我们突然明白了一个简单的道理：最先响应消息的，往往是最后才画的。而我们刚才的链表显然不能满足这种需求。我们需要找一个方法来解决从后面往前遍历元素的问题。于是我们又做了个反向的链表。并简单地将这两个链表合二为一。于是双相链表产生了。但需求总是无穷的。我们又希望，某一元素C是属于元素A但不属于元素B的，简单地说，就是当C被点击时，A和C都能收到消息，而B是不可能收到的，即使A和B有重叠的情况。这种需求的典型就是子母控件。这使我们不得不考虑建立两条链表，一条是A-C，一条是B。但如果有A和B同属于元素R，那我们到底要建多少条链表？晕！我们不得不考虑新的方案。有人提出，用树吧。对，用树。很恰当地解决了这个问题。我们可以建一棵树。目前暂且树根为R，树技为A，B。而C亦为A的树技存在。于是有人欢呼：树是万能的，终于可以把链表换下了。但不一会，我们又遇上了问题，我们还要画这些元素并响应消息。树的遍历显然要比链表复杂且开销大。单从画来说，我们需要每次画时都进行树遍历。这种机制固然不会出错，但我们却皱起眉头，因为这看起来一点都不美。想来想去，还是把链表拿回来吧。我们只需在开始时遍历树，将结果依次加到链表中。以后就可以只遍历链表了，这样既快又无误。当树结点发生增删时，我们只需重建链表即可。这对于每次都遍历树所付出的牺牲是值得的。加上消息处理，我们刚才的双向链表又回来了。最简单的应用，使我们不得不借助树和链表。凭借这些知识，我们才能很好地解决项目开发中的问题。现实往往比理论都严酷。我们不但要知道树和链表的概念。我们可能还要在实践中去处理很多复杂的细节问题。如子树的增删，远比我们从书上学到的难掌握。以上只是简单的举例，一个成型的工程，使用到的往往要更多，如消息处理中的使用队列的消息泵，对于复杂查询元素集合使用的快照等。数据结构其实就在我们身边。 PS:可能会连载，不必每次都精华。

订阅后，新回复会通过你的通知中心匿名送达。