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

按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 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………………………………………