李征宇　韓子揚　孫平

摘要：鑒于教學課時的限制以及教學手段的局限，數(shù)據(jù)庫編程成為了數(shù)據(jù)庫教學中的難點，特別是深入的編程教學受到了更大的考驗。數(shù)據(jù)結(jié)構(gòu)一般作為數(shù)據(jù)庫的先導，是算法設計的基石，具有內(nèi)容豐富、結(jié)構(gòu)多變的特點，如若選作數(shù)據(jù)庫編程的事例，不僅可以全面鍛煉數(shù)據(jù)庫編程經(jīng)驗技巧，也可加深對數(shù)據(jù)結(jié)構(gòu)的理解。本文以數(shù)據(jù)結(jié)構(gòu)中的“路口漫游”模型為例，借助SQLServer，闡述其數(shù)據(jù)庫編程的實現(xiàn)過程。

關(guān)鍵字：數(shù)據(jù)庫編程，數(shù)據(jù)結(jié)構(gòu)，路口漫游

【中圖分類號】S432.1

1.實例場景

在數(shù)據(jù)庫編程教學中，為了更好的說明為何以及如何實現(xiàn)遞歸編程，我們引入了數(shù)據(jù)結(jié)構(gòu)眾多算法模型之一的路口漫游模型。同時，出于方便學生回憶和理解路口漫游模型的目的，引入模型應用的實際場景。例如，某市為了更好的發(fā)揮交巡警職能，需要在市區(qū)的一些交通要道和重要部位設置交巡警服務平臺，但由于警務資源有限，需要根據(jù)城市的實際情況與需求合理地設置交巡警服務平臺、分配各平臺的管轄范圍以及調(diào)度警務資源。具體需要解決的問題可能很多，下面暫列幾個：

（1）根據(jù)市區(qū)交通網(wǎng)絡和現(xiàn)有交巡警平臺設置情況，為各交巡警服務平臺分配轄區(qū)范圍，保證轄區(qū)內(nèi)若有突發(fā)事件時能在規(guī)定時間內(nèi)到達事發(fā)地點。

（2）在最短時間內(nèi)封鎖全市出口的調(diào)配方案。

（3）分析全市交巡警平臺的工作量和出警時長，擬合增加若干平臺，以減輕部分平臺的工作量，提高整體效率。

通過對上述問題的分析，我們可以看出存在一個基礎的問題就是如何求出從一個或者一批路口出發(fā)，尋找在指定距離范圍內(nèi)的所有可達路口，同時保留其所經(jīng)路徑。此需求和數(shù)據(jù)結(jié)構(gòu)中所提的路口漫游模型非常貼切，下面我們詳細說明此模型以及如何通過數(shù)據(jù)庫編程實現(xiàn)。

2.路口漫游模型

路口漫游是數(shù)據(jù)結(jié)構(gòu)中常用的模型之一，在搜索優(yōu)化類算法中應用廣泛。模型以圖論為基礎，假設端點存在可進行自由漫游的人，以不重復、非環(huán)路為條件向外漫游指定的距離，搜索所有可能到達的路徑。在具體的應用中，可以根據(jù)需求保留或者舍棄末段不完整路徑。在下面的討論中，由于未到達的路口不在轄區(qū)或者封鎖范圍內(nèi)，我們舍棄了末端路徑。對于路口漫游的算法步驟簡述如下：

步驟1 以指定的路口集C為中心，以特定的距離L為閾值。對路口集C中的任一路口ci，在關(guān)聯(lián)ci的所有道路中任選一條加入漫游路徑中，記錄為；

步驟2 如若ci的漫游路徑總長大于指定的閾值L，則從ci出發(fā)的向此方向的漫游結(jié)束；否則以rj的另一段，即非ci端繼續(xù)向外漫游；

步驟3 重復步驟2直至漫游路徑長大于閾值L，并且保證漫游路徑為簡單路徑，即無環(huán)不回溯，也就是新加入的路徑及端點均不在已游歷的路徑中。依據(jù)實例的需要我們將舍棄不完整的末端路徑。

3.數(shù)據(jù)庫解決方案

3.1公用表達式（CTE）

通過上述的分析，自然的考慮運用遞歸的思路來解決此問題。在實際的數(shù)據(jù)庫編程的教學中，以SQLServer為工具，有關(guān)遞歸編程應用較多的是公用表達式（CTE）。定義遞歸CTE的要點在于，依次定義定位點成員和遞歸成員，并以UNIONALL鏈接，通過遞歸成員的FROM子句中引用CTE本身來實現(xiàn)遞歸。一個簡單的遞歸CTE可以形式化定義為，

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

定位點成員定義

UNIONALL

遞歸成員定義，其FROM子句將應用自身的公共表達式名}

遞歸CTE的執(zhí)行簡單說來是這樣的，

（1）執(zhí)行定位點成員生成第一個調(diào)用的基準結(jié)果集{T0}；

（2）運行遞歸成員，以Ti作為輸入，以Ti+1作為輸出；

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

（4）最終結(jié)果為從T0一直UNIONALL到Tn的結(jié)果。

3.2路口漫游的實現(xiàn)

為了簡化遞歸形式，交通路線相關(guān)信息匯總成中間表crossandroad_info中，包括路口[roadcross]，與路口關(guān)聯(lián)的所有道路[roadlist]，關(guān)聯(lián)道路號[road_num]，道路長[correct_road_lenth]，哪端[whichpoint]，另一端路口號[theOtherpoint]等。依據(jù)路口漫游模型，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為條件過濾漫游路徑，以此作為遞歸調(diào)用基準集；

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

--以上步探測的終點作為下步的起點，在確保簡單路徑（不重復非環(huán)）且不大于距離閾值L的條件下，逐步向外漫游，直至沒有新的可選路口，即返回空集。

4.擴展

通過上述的分析與實踐，我們成功的運用了數(shù)據(jù)庫編程的核心思想“集合”的概念完成了數(shù)據(jù)結(jié)構(gòu)中路口漫游的模型實現(xiàn)。由此，從一個新的角度實現(xiàn)算法的同時，鍛煉了數(shù)據(jù)庫的編程能力。實際上，基于集合的遞歸實現(xiàn)在數(shù)據(jù)結(jié)構(gòu)中的應用不止于路口漫游，還有不少其他的算法也可通過上述方法加以實現(xiàn)，特別是以層次結(jié)構(gòu)，樹形結(jié)構(gòu)為基礎的算法中，具體地如生成表示嵌套集合關(guān)系的二進制排序路徑，拓撲排序等。

當然，在數(shù)據(jù)結(jié)構(gòu)的算法當中，某些算法并不合適使用那個數(shù)據(jù)庫的語言來實現(xiàn)，例如需要逐條處理記錄的情形。倘若硬性用標準的SQL語言來實現(xiàn)，不但代碼冗長不易理解，效率也一般。

參考文獻

[1]ItzikBen-Gan等著MicrosoftSQLServer2005技術(shù)內(nèi)幕：T-SQL查詢.電子工業(yè)出版社，2008.

[2]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學出版社，2007.

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