以“路口漫游”為例探討數(shù)據(jù)結(jié)構(gòu)在數(shù)據(jù)庫(kù)編程教學(xué)中的應(yīng)用

李征宇　韓子揚(yáng)　孫平

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

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

【中圖分類號(hào)】S432.1

1.實(shí)例場(chǎng)景

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

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

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

（3）分析全市交巡警平臺(tái)的工作量和出警時(shí)長(zhǎng)，擬合增加若干平臺(tái)，以減輕部分平臺(tái)的工作量，提高整體效率。

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

2.路口漫游模型

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

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

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

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

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

3.1公用表達(dá)式（CTE）

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

WITH公共表達(dá)名（列名）AS{

定位點(diǎn)成員定義

UNIONALL

遞歸成員定義，其FROM子句將應(yīng)用自身的公共表達(dá)式名}

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

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

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

（3）重復(fù)（2）直至返回空集；

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

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

為了簡(jiǎn)化遞歸形式，交通路線相關(guān)信息匯總成中間表crossandroad_info中，包括路口[roadcross]，與路口關(guān)聯(lián)的所有道路[roadlist]，關(guān)聯(lián)道路號(hào)[road_num]，道路長(zhǎng)[correct_road_lenth]，哪端[whichpoint]，另一端路口號(hào)[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

--以距離中心點(diǎn)閾值L為條件過濾漫游路徑，以此作為遞歸調(diào)用基準(zhǔn)集；

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

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

4.擴(kuò)展

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

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

參考文獻(xiàn)

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

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

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