VB2008从入门到精通(PDF格式英文版)-第21部分

快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！



method；　implying　that　DepthFirstSearch　must　be　instantiated　before　we　can　call　　FindRoute（）。　　

We　should　modify　the　test　again　as　follows：　



Public　Sub　TestSearch（）　　

　　Dim　cls　As　DepthFirstSearch　=　New　DepthFirstSearch（）　

　　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

End　Sub　



　　　　　To　execute　the　method　FindRoute（）；　we　need　to　create　a　DepthFirstSearch　object；　allowing　　

multiple　users　to　perform　searches　without　getting　state　mixed　up。　At　this　point；　we　could　pat　　

ourselves　on　the　back　and　think　that　we　have　written　a　good　test　that　requires　a　class　　

implementation。　



The　Problem　of　Magic　Data　



Our　test　is　not　yet　plete；　because　we　don’t　have　access　to　the　route　found　by　the　algorithm；　　

but　that　will　be　explained　in　a　moment。　　

　　　　　In　the　implementation　of　DepthFirstSearch；　a　reference　to　the　data　structure　is　necessary。　　

The　search　algorithm　needs　to　know　which　tree　to　navigate。　One　way　to　implement　a　reference　　

to　the　tree　is　to　directly　reference　the　shared　data　Node。RootNodes。　An　implementation　of　　

DepthFirstSearch　would　be　as　follows：　


…………………………………………………………Page　122……………………………………………………………

100　　　　　　　CH　AP　T　E　R　　　4　　　■　　　　L　E　A　R　N　IN　G　　　AB　OU　T　　　D　AT　A　　S　TR　U　CT　U　R　E　S；　　　DE　CI　SI　ON　S；　　　A　N　D　　　L　O　OP　S　



　　　　　　　　　　　Public　Class　DepthFirstSearch　　

　　　　　　　　　　　　　　Public　Sub　FindRoute（ByVal　start　As　String；　ByVal　finish　As　String）　　

　　　　　　　　　　　　　　　　　　Dim　startNodes　As　Node（）　=　Node。RootNodes　

　　　　　　　　　　　　　　End　Sub　

　　　　　　　　　　　End　Class　



　　　　　　　　　　　　　　　　This　example　declares　a　variable　called　startNodes；　which　represents　the　starting　point　　

　　　　　　　　　　and　root　of　the　tree　as　shown　in　Figure　4…2。　The　root　of　the　tree　is　based　on　the　data　member　　

　　　　　　　　　　　Node。RootNodes；　and　this　assignment　is　called　a　magic　type　assignment。　A　magic　type　is　formed　　

　　　　　　　　　　when　you　call　a　method；　and　magically；　it　happens　to　know　how　to　reference　data；　even　though　　

　　　　　　　　　　you　never　instructed　the　type。　In　the　case　of　DepthFirstSearch；　the　magic　is　the　ability　of　　

　　　　　　　　　　　FindRoute（）　to　know　to　reference　the　correct　data　member　RootNodes。　

　　　　　　　　　　　　　　　　The　assumption　is　bad　because　it　couples　the　data　member　　RootNodes　to　the　method　　

　　　　　　　　　　　FindRoute（）。　Imagine　if　the　developer　of　the　Node　class　later　decides　to　add　functionality　to　load　　

　　　　　　　　　　the　tree　from　a　file　on　the　hard　disk。　So　that　　FindRoute（）　is　not　broken；　the　developer　would　　

　　　　　　　　　　need　to　explicitly　copy　the　hard…disk…loaded　tree　to　the　data　member　RootNodes。　

　　　　　　　　　　　　　　　　Or　what　if　two　different　users　wanted　to　create　two　different　flight　trees？　Node。RootNodes　is　　

　　　　　　　　　　a　shared　resource；　and　thus　can　process　only　a　single　flight　tree。　The　developer　of　Node　might　　

　　　　　　　　　　alter　RootNodes；　and　thus　FindRoute（）　would　behave　erratically。　

　　　　　　　　　　　　　　　　When　you　have　a　case　of　magic　data；　whatever　data　is　magic　needs　to　be　passed　to　the　type　　

　　　　　　　　　　via　a　constructor　or　other　method。　So　the　test　for　the　flight　route　would　change　to　the　following：　



　　　　　　　　　　　Public　Sub　TestSearch（）　　

　　　　　　　　　　　　Dim　cls　As　DepthFirstSearch=　_　

　　　　　　　　　　　　　　New　DepthFirstSearch（Node。RootNodes）　

　　　　　　　　　　　　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

　　　　　　　　　　　End　Sub　



　　　　　　　　　　　　　　　　As　the　root　tree　node　is　required；　we　change　the　constructor　to　require　that　a　caller　pass　in　the　　

　　　　　　　　　　root　tree　node。　The　test　code　still　uses　the　shared　data　member　RootNodes；　but　DepthFirstSearch　　

　　　　　　　　　　does　not　need　to　know　where　to　find　the　tree。　If　the　Node　developer　were　to　alter　the　behavior　of　　

　　　　　　　　　　the　data　member　RootNodes；　then　only　the　constructor　code　to　DepthFirstSearch　would　need　　

　　　　　　　　　　altering；　not　the　FindRoute（）　method。　Thus；　Node　and　DepthFirstSearch　are　properly　decoupled　　

　　　　　　　　　　from　each　other。　



　　　　　　　　　　　Getting　the　Found　Route　



　　　　　　　　　　Once　you　have　called　the　FindRoute（）　method；　you　expect　an　answer。　Because　the　route　could　　

　　　　　　　　　　involve　multiple　cities；　the　found　route　is　stored　in　an　array　of　Node　elements。　In　programmatic　　

　　　　　　　　　　terms；　there　are　two　ways　of　retrieving　the　array　of　Nodes。　The　first　is　a　return　value；　like　this：　



　　　　　　　　　　　Public　Sub　TestSearch（）　　

　　　　　　　　　　　　Dim　cls　As　DepthFirstSearch　=　New　DepthFirstSearch（Node。RootNodes）　

　　　　　　　　　　　　Dim　foundRoute　As　Node（）　=　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

　　　　　　　　　　　End　Sub　



　　　　　　　　　　　　　　　　The　bold　code　shows　the　assignment　of　the　return　value　to　the　variable　foundRoute。　　


…………………………………………………………Page　123……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　CH　AP　T　E　R　　　4　　　■　　　　L　E　A　R　N　I　N　G　　　A　B　OU　T　　　D　AT　A　　S　TR　U　CT　U　R　E　S；　　　DE　CI　SI　ON　S；　　　A　N　D　　　L　O　OP　S　101　



　　　　　The　second　approach　is　for　the　FindRoute（）　method　to　store　the　result　in　an　internal　data　　

member。　The　following　example　assumes　that　the　FindRoute（）　method　stores　the　result　in　a　　

data　member　named　FoundRoute：　



Public　Sub　TestSearch（）　　

　　Dim　cls　As　DepthfirstSearch　=　New　DepthFirstSearch（Node。RootNodes）　

　　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

　　Dim　foundRoute　As　Node（）　=　cls。FoundRoute　

End　Sub　



　　　　　Each　approach　seems　acceptable；　and　you　are　not　sure　which　to　use。　When　you　have　a　　

choice　like　this；　you　need　to　make　a　decision。　The　safest　way　to　make　a　decision　is　to　write　tests　　

and　see　if　there　are　any　problems　with　either　approach。　

　　　　　In　the　example　of　calculating　a　single　route；　either　approach　is　fine。　But　let’s　look　at　the　　

code　when　multiple　routes　are　being　searched。　First；　consider　the　code　where　the　found　path　　

is　a　return　parameter　value：　



Public　Sub　TestSearch（）　　

　　Dim　cls　As　DepthFirstSearch　=　New　DepthFirstSearch（Node。RootNodes）　

　　Dim　foundRoute1　As　Node（）　=　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

　　Dim　foundRoute2　As　Node（）　=　cls。FindRoute（〃New　York〃；　〃Seattle〃）　

End　Sub　



　　　　　Now　take　a　look　at　the　code　that　uses　the　data　member：　



Public　Sub　TestSearch（）　　

　　Dim　cls　As　DepthFirstSearch　=　New　DepthFirstSearch（Node。RootNodes）　

　　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

　　Dim　foundRoute1　As　Node（）　=　cls。FoundRoute　

　　cls。FindRoute（〃New　York〃；　〃Seattle〃）　

　　Dim　foundRoute2　As　Node（）　=　cls。FoundRoute　

End　Sub　



　　　　　Again；　it　would　seem　that　both　choices　are　adequate。　However；　there　is　a　difference；　the　　

difference　is　subtle；　but　distinct　enough　to　matter。　In　the　test　implementation　where　the　found　　

route　is　a　return　value；　the　variables　foundRoute1　and　foundRoute2　represent　routes　that　relate　　

directly　to　the　route　being　searched。　There　is　no　chance　that　the　variables　foundRoute1　can　　

represent　the　route　New　York–Seattle。　With　the　data　member　code；　it　could　happen　that　　

foundRoute1　points　to　the　route　New　York–Seattle；　as　shown　in　the　following　code。　



Public　Sub　TestSearch（）　　

　　Dim　cls　As　DepthFirstSearch　=　New　DepthFirstSearch（Node。RootNodes）　

　　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

　　cls。FindRoute（〃New　York〃；　〃Seattle〃）　

　　Dim　foundRoute1　As　Node（）　=　cls。FoundRoute　

　　Dim　foundRoute2　As　Node（）　=　cls。FoundRoute　

End　Sub　


…………………………………………………………Page　124……………………………………………………………

102　　　　　　　CH　AP　T　E　R　　　4　　　■　　　　L　E　A　R　N　IN　G　　　AB　OU　T　　　D　AT　A　　S　TR　U　CT　U　R　E　S；　　　DE　CI　SI　ON　S；　　　A　N　D　　　L　O　OP　S　



　　　　　　　　　　　　　　　　By　switching　the　order　of　the　FindRoute（）　method　calls　and　references　to　the　data　member　　

　　　　　　　　　　　FoundRoute；　the　variables　foundRoute1　and　foundRoute2　will　reference　the　same　found　route；　　

　　　　　　　　　　　specifically　the　route　New　York–Seattle。　This　is　not　a　good　idea。　The　example　shows　how　data　　

　　　　　　　　　　　members　have　no　direct　relation　to　methods　and　can　vary　independently。　

　　　　　　　　　　　　　　　　So　the　choice　of　returning　the　found　route　from　a　method　is　the　better　and　more　robust　　

　　　　　　　　　　　approach。　



　　　　　　　　　　　■Note　　Data　members　are　useful　when　you　want　to　store　or　retrieve　data　that　spans　multiple　method　calls　　

　　　　　　　　　　　or　is　not　dependent　on　the　order　of　how　methods　are　called。　When　you　have　data　that　is　dependent　on　the　　

　　　　　　　　　　　order　of　called　methods；　you　should　use　the　Return　keyword　or　ByRef　parameters。　



　　　　　　　　　　　　　　　　The　following　is　the　plete　test　case　that　includes　the　verification　code　that　searches　for　　

　　　　　　　　　　　a　flight　from　Montreal　to　Seattle。　



　　　　　　　　　　　Public　Sub　TestSearch（）　　

　　　　　　　　　　　　　Dim　cls　As　DepthFirstSearch　=　New　DepthFirstSearch（Node。RootNodes）　

　　　　　　　　　　　　　Dim　foundRoute　As　Node（）　=　cls。FindRoute（〃Montreal〃；　〃Seattle〃）　

　　　　　　　　　　　　　If　foundRoute。Length　　2　Then　

　　　　　　　　　　　　　　　Console。WriteLine（〃Incorrect　route　as　route　has　two　legs〃）　

　　　　　　　　　　　　　End　If　

　　　　　　　　　　　　　If　foundRoute（0）。CityName。pareTo（〃Los　Angeles〃）　　0　Then　

　　　　　　　　　　　　　　　Console。WriteLine（〃Incorrect　as　first　leg　is　Los　Angeles〃）　

　　　　　　　　　　　　　End　If　

　　　　　　　　　　　End　Sub　



　　　　　　　　　　　■Note　　We’ve　already　used　the　If　construct　in　earlier　chapters。　It　tests　a　condition　and　executes　its　contained　　

　　　　　　　　　　　code　if　that　condition　is　true。　The　　means　does　not　equal。　We’ll　examine　If　in　more　detail　later　in　this　　

　　　　　　　　　　　chapter；　in　the　“Using　the　If　Statement”　section。　



　　　　　　　　　　　Implementing　the　Depth…First　Search　Algorithm　



　　　　　　　　　　　The　implementation　of　the　depth…first　search　algorithm　involves　creating　an　algorithm　that　　

　　　　　　　　　　　iterates　the　tree。　Here；　we’ll　implement　the　algorithm　in　Visual　Basic。　In　so　doing；　we’ll　use　　

　　　　　　　　　　　decision　statements　and　For　loops　to　iterate　the　array　data。　These　are　incredibly　mon　in　　

　　　　　　　　　　Visual　Basic　programs；　and　life　would　be　very　difficult　without　them。　

　　　　　　　　　　　　　　　　We　implemented　the　test　code　in　the　previous　section；　so　the　next　step　is　to　implement　a　　

　　　　　　　　　　　version　of　DepthFirstSearch　that　represents　a　shell；　so　that　all　of　the　code　piles　and　runs。　　

　　　　　　　　　　　The　shell　is　structural　and　is　used　to　hold　up　the　entire　application。　It　is　defined　as　shown　in　　

　　　　　　　　　　　Figure　4…15。　


…………………………………………………………Page　125……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　　　　CH　AP　T　E　R　　　4　　　■　　　　L　E　A　R　N　I　N　G　　　A　B　OU　T　　　D　AT　A　　S　TR　U　CT　U　R　E　S；　　　DE　CI　SI　ON　S；　　　A　N　D　　　L　O　OP　S　103　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Tree　to　be　searched　is　passed　as　a　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　parameter　to　the　constructor　

　Public　Class　DepthFirstSearch　

　　　　　Private　root　As　Node（）　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Constructor　parameter　is　assigned　to　a　private　data　

　　　　　Public　Sub　New（ByVal　root　As　Node（））　

　　　　　　　　　Me。root　=　root　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　member。　Making　a　data　member　private　means　only　those　

　　　　　End　Sub　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　methods　declared　in　DepthFirstSearch　can　reference　it。　



　　　　　Public　Function　FindRoute（ByVal　start　As　String；　ByVal　finish　As　String）　_　

　As　Node（）　

　　　　　　　　　Throw　New　Exception（〃Not　implemented〃）　

　　　　　End　Function　

　End　Class　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Empty　implementation　throws　an　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　exception　（an　error）　indicating　that　the　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　code　is　not　implemented　



Figure　4…15。　　The　initial　shell　of　the　depth…first　algorithm　



　　　　　　With　a　shell　implemented；　you　could　run　the　application　and　see　if　everything　works。　If　　

you　do　run　the　test　code；　you　will　get　an　error；　because　calling　　FindRoute（）　generates　an　excep

tion　that　indicates　　FindRoute（）　has　not　been　fully　implemented。　（Exceptions　are　discussed　in　　

detail　in　the　next　chapter。）　However；　the　shell　is　plete；　and　we　are　ready　to　implement　the　　

guts　of　the　algorithm。　

　　　　　　Implementing　the　guts　of　an　algorithm　is　arguably　one　of　the　most　difficult　steps；　as　you　　

must　go　through　the　logic　of　what　you　want　to　do。　Whenever　I　am　confronted　with　an　algorithm　　

that　needs　implementation　and　I　am　not　quite　sure　how　to　proceed；　I　just　write　code；　based　on　　

an　entry　point　（the　method　call）　and　an　exit　point　（the　end　of　a　method’s　execution）。　



The　Keyhole　Problem　



In　the　example；　the　entry　and　exit　point　into　the　algorithm　is　FindRoute（）。　In　turn；　the　entry　of　　

FindRoute（）　is　two　parameters：　start；　indicating　the　beginning　city；　and　finish；　indicating　the　　

destination　city。　The　exit　of　FindRoute（）　is　an　array　of　Node　objects。　

　　　　　　The　array　of　Node　objects　needs　to　be　preallocated　with　space　so　that　all　of　the　found　cities　　

can　be　added。　We　can　make　an　assumption　at　this　point　that　we　preallocate　the　number　of　　

nodes　to　the　length　of　the　data　member　DepthFirstSearch。root　plus　one。　The　assumption　is　　

that　the　longest　trip　cannot　exceed　the　number　of　cities　available。　We　know　that　the　root　node　　

is　an　array　of　all　starting　point　cities；　thus　the　allocation　can　never　be　exceeded。　

　　　　　　Focusing　on　the　FindRoute（）　method；　the　updated　code　looks　like　this：　



Public　Function　FindRoute（ByVal　start　As　String；　ByVal　finish　As　String）　As　Node（）　

　　Dim　returnArray（Me。root。Length　＋　1）　As　Node　

　　Return　returnArray　

End　Function　



　　　　　　The　code　with　the　array　allocation　is　a　classic　keyhole　problem　（an　idea　first　introduced　by　　

Scott　Meyers；　see　http：//aristeia。/TKP/）。　The　problem　of　a　keyhole　is　that　you　imple

ment　an　algorithm　based　on　assumptions　that　cause　you　to　write　code　that　works　for　that　specific　　

context；　but　would　fail　when　executed　in　another　context。　


…………………………………………………………Page　126……………………………………………………………

104　　　　　　　CH　AP　T　E　R　　　4　　　■　　　　L　E　A　R　N　IN　G　　　AB　OU　T　　　D　AT　A　　S　TR　U　CT　U　R　E　S；　　　DE　CI　SI　ON　S；　　　A　N　D　　　L　O　OP　S　



　　　　　　　　　　　　　　　　The　code　allocates　an　array　to　the　length　of　the　root　tree　structure；　and　that　is　making　a　　

　　　　　　　　　　grand　assumption。　Imagine　if　the　Node　developers　decided　to　introduce　connections　that　could　　

　　　　　　　　　　be　reached　only　via　another　city　that　is　not　included　in　the　root　nodes。　At　that　point；　you　could　　

　　　　　　　　　　potentially　exceed　the　available　space　in　the　array。　Another　solution　would　be　to　allocate　an　　

　　　　　　　　　　　array　of　arbitrary　length　X　。　But　then；　if　there　were　X＋1　unique　cities；　another　array　could　be　　

　　　　　　　　　　violated。　

　　　　　　　　　　　　　　　　The　simplest　solution　would　be　to　not　allocate　an　array；　but　instead　figure　out　how　many　　

　　　　　　　　　　　elements　you　needed　after　having　found　a　path。　However；　this　would　not　work；　because　then　　

　　　　　　　　　　you　would　have　no　idea　which　city　you　had　already　visited。　Another　solution　（which　will　be　　

　　　　　　　　　　　discussed　in　Chapter　9）　would　be　to　use　a　collection　class。　

　　　　　　　　　　　　　　　　In　this　case；　we　are　going　to　wash　our　hands　of　the　problem　and　force　the　Node　developers　　

　　　　　　　　　　to　modify　their　class。　The　Node　developers　are　going　to　add　a　shared　method　that　tells　the　search　　

　　　　　　　　　　　algorithm　how　big　the　array　needs　to　be。　The　following　is　the　modified　FindRoute（）　code。　



　　　　　　　　　　　Public　Function　FindRoute（ByVal　start　As　String；　ByVal　finish　As　String）　As　Node（）　

　　　　　　　　　　　　Dim　returnA