ＩＳＳＮ １００９－３０４４ Ｅ—ｍａｉｌ：ｘｓｊｌ＠ｄｎｚｓ．ｎｅｔ．ｃｒｌ ｈｔｔｐ：／／ｗｗｗ．ｄｎｚｓ．ｎｅｔ．ｃｎ Ｔｅｌ：＋８６—５５ １—６５６９０９６３ ６５６９０９６４ Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技术 Ｖｏ１．９，Ｎｏ．７，Ｍａｒｃｈ ２０１３． ＡＶＬ树研究与实现 解晨 （中山大学，广东广州５１０２７５） 摘要：计算机最广为人知的优点之一是其能储存大量的数据，如今随着时代的发展，储存容量更是犹如日进千里一般极速 扩展，大容量的硬盘、ｕ盘早已随处可见。然而，要在巨大的数据中搜索出需要的内容却不是一件容易的事，由此，为了能 减少在搜索储存数据上的开销，各种适应于不同访问搜索背景的数据结构应运而生。树，便是计算机学科中最基本的数 据结构之一，提供了快速的储存和访问性能。该文探究了带有平衡条件的二又查找树——ＡｖＬ树的原理，并对其使用Ｃ 语言进行了实现。 关键词：数据结构；平衡二叉查找树；ＡｖＬ树 中图分类号：ＴＰ３ｌｌ 文献标识码：Ａ 文章编号：１００９—３Ｏ４４（２Ｏ１３）０７—１５３２—０４ Ｒｅｓｅａｒｃｈ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＡＶＬ Ｔｒｅｅ ＸＩＥＣｈｅｎ （Ｚｈｏｎｇｓｈａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ ５１０２７５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｏｎｅ ｏｆｔｈｅ ｍｏｓｔ ｗｅｌｌ ｋｎｏｗｎ ｉｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆｃｏｍｐｕｔｅｒ ｃａｎ ｓｔｏｒｅ ｌａｒｇｅ ａｍｏｕｎｔｓ ｏｆｄａｔａ，ａｎｄ ｎｏｗ ｗｉｔｈ ｔｈｅ ｄｅｖｅｌｏｐ— ｍｅｎｔ ｏｆ ｔｈｅ ｔｉｍｅｓ，ｔｈｅ ｓｔｏｒａｇｅ ｃａｐａｃｉｙｔ ｉｓ ｍｏｒｅ ｌｉｋｅ Ｊａｐａｎ ｉｎｔｏ ｔｈｏｕｓａｎｄｓ ｏｆ ｇｅｎｅｒａｌ ｅｘｔｅｎｄｅｄ，ｈａｒｄ ｄｉｓｋ，Ｕ ｄｉｓｋ ｈａｓ ｌａｒｇｅ ｃａｐａｃｉｔｙ ｃａｎ ｂｅ ｓｅｅｎ ｅｖｅｒｙｗｈｅｒｅ．Ｈｏｗｅｖｅｒ，ｔＯ ｓｅａｒｃｈ ｆｏｒ ｉｎ ｔｈｅ ｈｕｇｅ ｄａｔａ ｉｎ ｔｈｅ ｎｅｅｄｓ ｏｆ ｔｈｅ ｃｏｎｔｅｎｔ ｉｓ ｎｏｔ ａ ｅａｓｙ ｔｈｉｎｇ，ｔｈｅｒｅｆｏｒｅ，ｉｎ ｏｒ— ｄｅｒ ｔＯ ｒｅｄｕｃｅ ｔｈｅ ｄａｔａ ｓｔｏｒａｇｅ ｏｖｅｒｈｅａｄ ｉｎ ｔｈｅ ｓｅａｒｃｈ，ａｌｌ ｋｉｎｄｓ ｏｆ ａｄａｐｔａｔｉｏｎ ｔＯ ｄｉｆｆｅｒｅｎｔ ａｃｃｅｓｓ ｓｅａｒｃｈ ｅｍｅｒｇｅ ａｓ ｔｈｅ ｔｉｍｅｓ ｒｅｑｕｉｒｅ ａｔａ ｓｔｒｄｕｃｔｕｒｅ ｂａｃｋｇｒｏｕｎｄ．Ｔｒｅｅ，ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｂａｓｉｃ ｄａｔａ ｓｔｒｕｃｔｕｒｅ ｉｎ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ，ｐｒｏｖｉｄｅｓ ｆａｓｔ ｓｔｏｒａｇｅ ａｎｄ ａｃｃｅｓｓ ｐｅｒ— ｆｏｒｍａｎｃｅ．Ｔｈｉｓ ｐａｐｅｒ ｅｘｐｌｏｒｅｓ ｔｈｅ ｔｗｏ ｂｉｎａｒｙ ｓｅａｒｃｈ ｔｒｅｅ ｗｉｔｈ ｅｑｕｉｌｉｂｒｉｕｍ ｃｏｎｄｉｔｉｏｎｓ一一ｐｒｉｎｃｉｐｌｅ ｏｆＡＶＬ ｔｒｅｅ，ａｎｄ ｔｈｅ ｕｓｅ ｏｆＣ ｌａｎｇｕａｇｅ ｔＯ ｒｅａｌｉｚｅ． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｓｔｕｃｔｒｕｒｅ；ｂａｌａｎｃｅｄ ｂｉｎａｒｙ ｓｅａｒｃｈ ｔｒｅｅ；ＡＶＬ ｔｒｅｅ 对于大量的输入数据，普通的线性数据结构访问时间太慢，例如，对于一个有Ｎ个数据的线性数据结构，假设对每个数据的访 问几率大致相同，每个数据每次访问有Ｉ／Ｎ的机会被访问，由于是线性数据，因此每个数据的访问花销可以经过一定的排列，最通常 的是访问第一个数据花销１个单位时间，第二个２个单位时间，第三个３各单位时间……第Ｎ个Ｎ各单位时间，于是访问一次的平均 花销为（Ⅳ＋Ｎ ）／２Ｎ＝（Ｉ＋Ｎ）／２，用计算机专业的符号来说，其访问运行时间可以用０（Ｎ）来表示，即访问一次线性数据结构的花销 在Ｎ这个数量级上。使用树这一数据结构可将访问花销将至ｌｏｇＮ这个数量级上，也即Ｏ（１ｏｇＮ），这里ｌｏｇＮ是以二为底的Ｎ的对数。 可以对比一下，若Ｎ＝１２６７６５０６００２２８２２９４０１４９６７０３２０５３７６，则ｌｏｇＮ＝１００。数字越大，则Ｏ（Ｎ）与Ｏ（１ｏｇＮ）相差越大。 一般来说，计算机学科中使用的最基本的树为二叉查找树，下图是一颗二叉树的简单示意图： 图１二叉树示意图 二叉查找树则是在二叉树的基础上得来。假设在一颗二叉树中，每个节点都有一个关键词值，并且关键词值都是互异且可以 比较，若对于此二又树中的每个节点，其左子树中所有节点的关键词值小于其本身关键词值，其右子树中所有关键词值大于其本身 关键词值，则此二叉树为二叉查找树。 收稿日期：２０１３一叭一１０ 作者简介：解晨（１９９２一），男，安徽合肥人，中山大学信息安全专业，研究方向为人工智能、算法设计。 １５３２㈣软件设计开发 本栏目责任编辑：谢媛媛 第９卷第Ｏ７期（２０１３年０３月） Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技术 ＡＶＬ树，则是最先发明的带有平衡条件的二叉查找树。 下面，就让我们来分析一下ＡＶＬ树的思想和原理。 １ ＡＶＬ树思想和原理 正如上所述，ＡＶＬ树是一种带有平衡条件的二叉查找树。那么，这个平衡条件是什么呢？ 对于二叉查找树这样的数据结构来说，由于其节点有着按顺序排列的性质，若有数据往此数据结构中插入，则可能会引起树的 高度过高，使得访问数据的花销可能会比应有的要多。 例如，对于只有一个节点ｘ的二叉查找树，若此后往树中插人的元素其关键词值皆小于ｘ的关键词值，那么这棵树的左子树就 会越来越庞大，最终访问一个比ｘ小得多的数据可能会花费相当多的开销，而如果在插入数据到一定程度时选择Ｘ的左子树中适当 的节点作为根节点，则情况会好得多。 如上所述的即是平衡条件，即使得树的深度不致过于深，让左子树和右子树的高度相差不宜过大。同时，从应用的角度来说， 这个平衡条件必须容易实现，并且应该允许能够易如反掌地对数据结构进行如插入数据、删除数据这样的常见操作。 １．１ ＡＶＬ树的思想与原理 对于一颗ＡＶＬ树来说，其平衡条件是要求其每个节点的左子树和右子树的高度最多差一。例如，在图２中，左边的树为ＡＶＬ 树，右边的则不是： 图２二叉树 据资料显示，一个ＡＶＬ树的高度平均来说只有１．４４ｌｏｇ（Ｎ＋２）一１．３２８，并且其实际上的高度只比ｌｏｇＮ多一点，这样的访问花销 是比较高效的。 那么，ＡＶＬ树是如何实现这个平衡条件的呢？很幸运，这个解决方法并不难。事实上，我们是可以通过足够简单的对树的修改 来做到。 １．２ ＡＶＬ树的旋转操作 在对一颗ＡＶＬ树进行插入数据或者删除数据的操作时，我们通过一种称之为“旋转”的操作来保持树的左右子树之差。由于对 像二叉查找树这样本身已经包含排列性质的数据结构的修改，一般来说只有插入数据和删除数据是常用的，所以在这作者只使用 插入数据来分析ＡＶＬ树的旋转操作，删除数据可以依理推知。 同时，由于插入节点后，只有那些从插人点到根节点路径上的节点的平衡性会改变，所以在对树进行操作以更新平衡时，能找 到这样一个节点，它破坏了平衡性，但是可以对它进行操作使得树重新变得平衡。 现在假设这个破换平衡的节点为Ｗ。可知，根据ＡＶＬ树的定义可知，此时ｗ的左子树和右子树的高度差为二，并且这种造成不 平衡的插人操作会有如下四种情况： １）对Ｗ的左儿子的左子树进行一次插入； ２）对Ｗ的右儿子的右子树进行一次插入； ３）对ｗ的左儿子的右子树进行一次插入； ４）对ｗ的右儿子的左子树进行一次插入。 可以看出，１）和２）是一个镜像关系，３）和４）也是一个镜像关系，因此，从理论的角度来说实际上只有两种情况。 对于１）和２）的情形，可以使用“单旋转”来恢复平衡。 单旋转的操作示意图如下： 图３单旋转操作示意图 本栏目责任编辑：谢媛媛 ｗ 软件设计开发 １５３３ Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技＿术 第９卷第０７期（２０１３年０３月） 可以看到，在这个示意图中，节点ｋ２扮演着ｗ的角色，其左子树与右子树的高度差为２，并且再插入包含新数据的新节点之前， ｋ２满足ＡｖＬ树的平衡条件。于是为了恢复平衡，对ｋｌ和ｋ２及其左右子树进行操作。在示意图中，是以ｋ１取代ｋ２作为根节点，将Ｙ 变成了ｋ２的左子树，并将此时的ｋ２作为ｋ１的右儿子。 对于其镜像情形的操作也是一样，在此就不赘述。 而对于３）和４）的情形，则必须使用双旋转操作来保持树的平衡。例如，可以根据如下示意图来说明： 图４双旋转操作示意图 在这个情形中，对于以ｋ１为根节点的树来说，其高度比树Ｄ多二，问题发生在ｋ１的右子树，更准确的说，是发生在Ｂ或Ｃ，具体 哪个不要紧，【大１为都有可能，所以此处将Ｂ和Ｃ画得一样高。 对于这种情形，可以像示意图那样改变根节点，并且将ｋ ｌ、ｋ２、ｋ３的左右子树进行交换而使树重新得到平衡。 对于其镜像情况也可以使用相同的技巧使树的平衡得到保持，在此就不赘述。 可以看出，对于这两种情况，一次旋转足以解决问题，因此，其效率能够在接受的范围之内，并且易于实现。 下面，作者使用Ｃ语言对ＡＶ１树这一数据结构进行了实现。 ２ ＡＶＬ树的Ｃ语言实现 作者使用Ｃ语言对ＡＶＬ树的节点、获取节点所在高度函数、数据节点的插入函数、左右单旋转函数、左右双旋转函数以及以中 序遍历在屏幕上显示节点信息函数等进行了实现。 ２．１ ＡＶＬ树节点实现 由前文分析可知，要实现的ＡＶＬ树节点包含四个元素，即节点的关键词值，指向左儿子的指针以及指向右儿子的指针，此外，还 需有一个记录节点高度的元素用以判断平衡状态。可以使用一个结构来表示节点，其源代码如下： ｔｒｕｅｒ Ａｖｌｔｒｅｅ ｛ ｉｎｔ ｅｌｅｍｅｎｔ； Ａｖｌｔｒｅｅ ｌｅｆｔ； Ａｖｌｔｒｅｅ ｒｉｇｈｔ； ｉｎｔ ｈｉｇｈ； ｝； ２．２ ＡＶＩ．树获取节点高度函数实现 获取节点的高度比较容易，只需返回节点中保存的高度信息即可，唯一要注意的是若是一颗空树，则返回一１这个高度。源代码 如下： ｉｎｔ ＨｌＧＨ（Ａｖｈｒｅｅ ｔ）ｆ ｉｆ（ｔ＝：ＮＵＬＬ）ｆ ｒｅｔｕｒｎ－ｉ； ｝ ｅｌｓｅ ｒｅｔｕｒｎ ｔ—＋ｈｉｇｈ； ｌ ２．３ ＡＶＬ树插入元素函数实现 向ＡＶＬ树中插入元素即使用一般的向二叉查找树中插入元素的操作即可，唯一要注意的是需修改节点高度信息，若平衡被破 坏则使用两种旋转对树进行修改。其源代码如下： ｒａｔｉｏ Ａｖｌｔｒｅｅ ｉｎｓｅｒｔ（ｉｎｔ Ａｖｌｔｒｅｅ ｔ）｛ ｉｆ（ｔ＝＝ＮＵＬＬ）Ｉ ｔ＝（Ａｖｌｔｒｅｅ ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｓｔｒｕｃｔ Ａｖｌｔｒｅｅ））； ｔ－＊ｅｌｅｍｅｎｔ ｘ： ｔ—ｈｉｇｈ＝０； ｔ—ｌｅｆｔ＝ｔ＿÷ｒｉｇｈｔ＝ＮＵＩ—Ｌ； １５３４ 软件设计开发 ＊ 本栏目责任编辑：谢媛媛 Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ『ｅｃｎｎ０Ｊｐ 电脑知识与技术 第９卷第０７期（２０１３年Ｏ３月） ｝ ｅｌｓｅ｛ ｉｆ（ｘ＞ｔ－－￣ｅｌｅｍｅｎｔ）Ｉ ｔ—＋ｒｉｇｈｔ：ｉｎｓｅｒｔ（ｘ，ｔ— ｒｉｇｈｔ）； ｉｆ（Ｈ１ＧＨ（ｔ一￣ｒｉｇｈｔ）一ＨＩＧＨ（ｔ－￣Ｉｅ０） ２）ｆ ｉｆ（ｘ＞ｔ＿＿＋ｒｉｇｈｒ ｅ１ｅｍｅｎｔ） ｔ＝ｓｉｎｇａｌｒｏｔａｔｅｗｉｔｈｒｉｇｈｔ（ｔ）； ｅｌｓｅ ｔ＝ｄｏｕｂｌｅｒｏｔａｔｅｗｉｔｈｒｉｇｈｔ（ｔ）； ｝Ｊ ｅｌｓｅ ｉｆ（ｘ＜ｔ－－－￣ｅｌｅｍｅｎｔ）｛ ｔ—ｌｅｆ【＝ｉｎｓｅｒｔ（ｘ，ｔ ｌｅｆｌ１； ｉｆ（ＨＩＧＨ（ｔ－－￣ｌｅｆ１）一ＨＩＧＨ（ｔ—ｒ ｈｔ）＝＝２）｛ ｉｆ（ｘ＜ｔ—｝ｌｅｆｌ—｝ｅ１ｅｍｅｎｔ）ｆ ｔ＝ｓｉｎｇａｌｒｏｔａｔｅｗｉｔｈｌｅｆｔ（ｔ）； ｝ ｅｌｓｅ ｔ＝ｄｏｕｂｌｅｒ０ｔａｔｅｗｉｔｈ１ｅｆｔｍ； ｝｝１ ｉｆＨＩＧＨ（ｔ－－－＋ｌｅｆ１）＞＝ＨＩＧＨ（ｔ－￣ｒｉｇｈｔ））｛ ｔ— ｇｈ＝ＨＩＧＨ（ｔ－－ｑｅｆｔ）＋ｌ； ｝ ｅｌｓｅ｛ ｔ— ｉｇｈ＝ＨＩＧＨ（ｔ－－￣ｒｉｇｈｔ）＋１： ｝ｒｅｔｕｒｎ ｔ； ｝ ２．４左右单旋转函数实现 左右单旋转函数的过程可以按上文所分析的来实现，左右单旋转只是互为镜像。 右单旋转的源代码如下： Ａｖｌｔｒｅｅ水ｓｉｎｇａｌｒ０ｔａｔｅｗｉｉｈｒｉｇｈｔ（ＡＶ１ｔｒｅｅ水ｔ） ｛ Ａｖｌｔｒｅｅ ｄ＝ｔ— ｒｉｇｈｔ； ｔ．－＋ｒｉ曲ｔ＝ｄ一１ｅｆｆ； ｄ－－￣ｌｅｆｔ＝ｔ： ｉｆ（ＨＩＧＨ（ｔ－＋ｌｅｔｆ）＞：ＨＩＧＨ（ｔ－－－￣ｒｉｇｈｔ））｛ 卜＋ｈ ｈ＝ＨＩＧＨ（ｔ－＋ｌｅｆｔ）＋１； １ ｅｌｓｅ（ ｔ—ｈｉｇｈ＝ＨＩＧｉ｛（ｔ－－－￣ｒｉｇｈｔ）＋１； １ｉｆ（ＨｉＧＨ（ｄ－＋ｌｅｆｔ）＞＝Ｈｌ（瑚（ｄ—ｒｉ ｇｌ１１））｛ ｄ—＿’ｈｉｇｈ＝ＨＩＧＨ（ｄ－－－￣ｌｅｆ１）＋ｌ； ｝ｅｌｓｅ（ ｄ—＋ｈ唔ｈ＝ＨＩＧＨ（ｄ－－－￣ｒｉｇｈｔ）＋１； １ｒｅｔｕｒｎ ｄ； ｌ 左单旋转的源代码如下： Ａｖｌｔｒｅｅ＊ｓｉｎｇａｌｒｏｔａｔｅｗｉｔｈｌｅｆｌ ｖｈｒｅｅ ｔ１ ｆＡｖｈｒｅｅ ｄ＝ｔ＿＋ｌｅｆｔ； ｔ— ｌｅｆＩ＝ｄ—｝ｒｊｇｈｔ； ｄ＿＋ｒ ｈｔ＝ｔ； ｉ（ｆＨＩＧＨ（ｔ－－ｑｅｆ１）＞＝ＨＩＧＨ（ｔ－－－￣ｒｉｇｈｔ））｛ ｔ—ｈｉｇｈ＝ＨＩＧＨ（ｔ－－￣ｌｅ１ｆ）＋ｌ； 本栏目责任编辑：谢媛媛 ＃ ∞ 软件设计开发…１５３５ Ｃｏｍｐｕ￣ｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技术 ｝ｅｌｓｅ｛ ｔ—，ｈｉｇｈ＝ＨＩＧＨｆｆ—＋ｒｊｇｈｔ）＋１； 第９卷第Ｏ７期（２０１３年０３，ＥＪ） ｝ｉｆ（ＨＩＧＨ（ｄ－－＇ｌｅｆｔ）＞＝Ｈ１ＧＨ（ｄ—ｒｉ ｔ））｛ ｄ— ｈｉｇｈ＝ＨＩＧＨ（ｄ－－Ｊｅｆｆ１＋１： ｝ｅｌｓｅ｛ ｄ—— ｈｉｇｈ＝ＨｌＧＨ（ｄ－－￣ｒｉｇｈｔ）＋１； ｝ｒｅｔｕｒｎ ｄ； Ｊ ２．５左右双旋转函数实现。 从上文中的分析可知，双旋转可以看成两次使用单旋转，因此，双旋转函数可以调用两次相对应的单旋转函数来实现。 右双旋转函数源代码如下： Ａｖｌｔｒｅｅ ｄｏｕｂｌｅｒｏｔａｔｅｗｉｔｈｒｉｇｈｔ（Ａｖｈｒｅｅ ｔ１ ｛ ｔ— ｒｉｇｈｔ＝ｓｉｎｇａｌｒｏｔａｔｅｗｉｔｈｌｅｆｔ（ｔ－－＊ｒｉｇｈｔ）； ｒｅｔｕｒｎ ｓｉｎｇａｌｒｏｔａｔｅｗｉｔｈｒｉｇｈｔ（ｔ）； ｝ 左双旋转函数源代码如下： Ａｖｈｒｅｅ ｄｏｕｂｌｅｒｏｔａｔｅｗｉｔｈｌｅｆｔ（Ａｖｌｔｒｅｅ ｔ１ ｆ卜÷ｌｅｆｔ＝ｓｉｎｇａｌｒｏｔａｔｅｗｉｔｈｒｉｇｈｔ（ｔ－￣ｌｅｆｔ）； ｒｅｔｕｍ ｓｉｎｇａｌｒｏｔａｔｅｗｉｔｈｌｅｆｔ（ｔ）； ｌ ２．６中序遍历函数实现 中序遍历是一种常用的遍历树这一数据结构的方法。此顺序先访问节点中的信息，再递归访问节点左子树中节点的信息，最 后递归访问右子树节点中的信息。 其源代码如下： ｖｏｉｄ ｐｒｉｎｔｔｒｅｅ（Ａｖｈｒｅｅ ｔ１ ｛ｉｆ（ｔ！＝ＮＵＬＬ）｛ ｃｏｕｔ＜＜ｔ－－－￣ｅｌｅｍｅｎｔ＜＜””： ｝ｉ ｔ—ｌｅｆｔ『－ＮＵＬＬ）｛ ｐｒｉｎｔｔｒｅｅ（ｔ－＊ｌｅｆｔ）； ｝ｉｆ（ｔ—ｒｉｇｈｔ！＝ＮＵＬＬ）｛ ｐｒｉｎｔｔｒｅｅ（ｔ－￣ｒｉｇｈｔ）； ｝Ｊ 以上，便是作者使用ｃ语言实现的有关ＡＶＬ树的所有源代码，其他操作如删除元素等可以依原理推知。 ３总结 本文分析了ＡＶＬ树的思想与原理，并根据其特点，结合Ｃ语言的特性，对ＡＶＬ树和一系列的操作进行了实现。 ＡＶＬ树是最早出现的数据结构之一，大大提高了访问数据的效率，也为以后数据结构的发展起着开拓性的作用。虽然如今计 算机的性能越来越匪夷所思，计算速度简直无法想象，访问速度早已大有提升，但毫无疑问，使用良好的数据结构依然对提高访问 速度有着举足轻重的作用。 参考文献： ［１］Ｒｏｂｅｒｔ Ｓｅｄｇｅｗｉｃｋ．算法：ｃ语言实现【Ｍ】．北京：机械工业出版，２００９． ［２］Ｅｌｌｉｓ Ｈｏｒｏｗｉｔｚ，Ｓａｒｔａｊ Ｓａｈｎｉ，Ｓｕｓａｎ Ａｎｄｅｒｓｏｎ—Ｆｒｅｅｄ．数据结构（ｃ语言版）【Ｍ】．北京：机械工业出版社，２００６ ［３３］ Ｍａｒｋ Ａｌｌｅｎ Ｗｅｉｓｓ．数据结构与算法分析【Ｍ】．北京：人民邮电出版社，２００５． ［４］Ｓｅｓｈ Ｖｅｎｕｇｏｐａ１．数据结构：从应用到实￣（Ｊａｖａ版）［Ｍ］．北京：机械工业出版社，２００８． 【５】Ａｄａｍ Ｄｒｏｚｄｅｋ．数据结构与算法：Ｊａｖａ语言版［Ｍ］．２版．北京：机械工业出版社，２００６． １５３６…软件设计开发 ％ 本栏目责任编辑：谢媛媛