以“路口漫游”为例探讨数据结构在数据库编程教学中的应用

李征宇　韩子扬　孙平

摘要：鉴于教学课时的限制以及教学手段的局限，数据库编程成为了数据库教学中的难点，特别是深入的编程教学受到了更大的考验。数据结构一般作为数据库的先导，是算法设计的基石，具有内容丰富、结构多变的特点，如若选作数据库编程的事例，不仅可以全面锻炼数据库编程经验技巧，也可加深对数据结构的理解。本文以数据结构中的“路口漫游”模型为例，借助SQLServer，阐述其数据库编程的实现过程。

关键字：数据库编程，数据结构，路口漫游

【中图分类号】S432.1

1.实例场景

在数据库编程教学中，为了更好的说明为何以及如何实现递归编程，我们引入了数据结构众多算法模型之一的路口漫游模型。同时，出于方便学生回忆和理解路口漫游模型的目的，引入模型应用的实际场景。例如，某市为了更好的发挥交巡警职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台，但由于警务资源有限，需要根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围以及调度警务资源。具体需要解决的问题可能很多，下面暂列几个：

（1）根据市区交通网络和现有交巡警平台设置情况，为各交巡警服务平台分配辖区范围，保证辖区内若有突发事件时能在规定时间内到达事发地点。

（2）在最短时间内封锁全市出口的调配方案。

（3）分析全市交巡警平台的工作量和出警时长，拟合增加若干平台，以减轻部分平台的工作量，提高整体效率。

通过对上述问题的分析，我们可以看出存在一个基础的问题就是如何求出从一个或者一批路口出发，寻找在指定距离范围内的所有可达路口，同时保留其所经路径。此需求和数据結构中所提的路口漫游模型非常贴切，下面我们详细说明此模型以及如何通过数据库编程实现。

2.路口漫游模型

路口漫游是数据结构中常用的模型之一，在搜索优化类算法中应用广泛。模型以图论为基础，假设端点存在可进行自由漫游的人，以不重复、非环路为条件向外漫游指定的距离，搜索所有可能到达的路径。在具体的应用中，可以根据需求保留或者舍弃末段不完整路径。在下面的讨论中，由于未到达的路口不在辖区或者封锁范围内，我们舍弃了末端路径。对于路口漫游的算法步骤简述如下：

步骤1 以指定的路口集C为中心，以特定的距离L为阈值。对路口集C中的任一路口ci，在关联ci的所有道路中任选一条加入漫游路径中，记录为；

步骤2 如若ci的漫游路径总长大于指定的阈值L，则从ci出发的向此方向的漫游结束；否则以rj的另一段，即非ci端继续向外漫游；

步骤3 重复步骤2直至漫游路径长大于阈值L，并且保证漫游路径为简单路径，即无环不回溯，也就是新加入的路径及端点均不在已游历的路径中。依据实例的需要我们将舍弃不完整的末端路径。

3.数据库解决方案

3.1公用表达式（CTE）

通过上述的分析，自然的考虑运用递归的思路来解决此问题。在实际的数据库编程的教学中，以SQLServer为工具，有关递归编程应用较多的是公用表达式（CTE）。定义递归CTE的要点在于，依次定义定位点成员和递归成员，并以UNIONALL链接，通过递归成员的FROM子句中引用CTE本身来实现递归。一个简单的递归CTE可以形式化定义为，

WITH公共表达名（列名）AS{

定位点成员定义

UNIONALL

递归成员定义，其FROM子句将应用自身的公共表达式名}

递归CTE的执行简单说来是这样的，

（1）执行定位点成员生成第一个调用的基准结果集{T0}；

（2）运行递归成员，以Ti作为输入，以Ti+1作为输出；

（3）重复（2）直至返回空集；

（4）最终结果为从T0一直UNIONALL到Tn的结果。

3.2路口漫游的实现

为了简化递归形式，交通路线相关信息汇总成中间表crossandroad_info中，包括路口[roadcross]，与路口关联的所有道路[roadlist]，关联道路号[road_num]，道路长[correct_road_lenth]，哪端[whichpoint]，另一端路口号[theOtherpoint]等。依据路口漫游模型，SQLServer形式的递归代码部分如下：

withpossiblepathas（

selectroadcross，

cast（current_pathinfoasvarchar（max））ascurrent_pathinfo，

cast（current_corsslistasvarchar（max））ascurrent_corsslist，

current_end，correct_road_lenth，remain_lenthfrompossiblepath_basewhereremain_lenth>0

--以距离中心点阈值L为条件过滤漫游路径，以此作为递归调用基准集；

unionall

selecta.roadcross，

（a.current_pathinfo+'Cross'+cast（b.current_endasvarchar（10））+'～'）ascurrent_pathinfo，

a.current_corsslist+cast（b.current_endasvarchar（10））+'，'ascurrent_corsslist，

b.current_endascurrent_end，b.correct_road_lenth，

a.remain_lenth-b.correct_road_lenthasremain_lenth

frompossiblepathasainnerjoinpossiblepath_baseasbona.current_end=b.roadcross

andcharindex（'，'+cast（b.current_endasvarchar（10））+'，'，a.current_corsslist）=0

wherea.remain_lenth-b.correct_road_lenth>0

--以上步探测的终点作为下步的起点，在确保简单路径（不重复非环）且不大于距离阈值L的条件下，逐步向外漫游，直至没有新的可选路口，即返回空集。

4.扩展

通过上述的分析与实践，我们成功的运用了数据库编程的核心思想“集合”的概念完成了数据结构中路口漫游的模型实现。由此，从一个新的角度实现算法的同时，锻炼了数据库的编程能力。实际上，基于集合的递归实现在数据结构中的应用不止于路口漫游，还有不少其他的算法也可通过上述方法加以实现，特别是以层次结构，树形结构为基础的算法中，具体地如生成表示嵌套集合关系的二进制排序路径，拓扑排序等。

当然，在数据结构的算法当中，某些算法并不合适使用那个数据库的语言来实现，例如需要逐条处理记录的情形。倘若硬性用标准的SQL语言来实现，不但代码冗长不易理解，效率也一般。

参考文献

[1]ItzikBen-Gan等著MicrosoftSQLServer2005技术内幕：T-SQL查询.电子工业出版社，2008.

[2]严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社，2007.

[3]ms-help：//MS.SQLCC.v10/MS.SQLSVR.v10.zh-CHS/s10de_1devconc/html/4acf8a3e-6dcc-420c-9088-9c57b976113e.htm