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

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


　　　　　　　　　　　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　returnArray（Node。GetMaxPossibleDestinationsArraySize（））　As　Node　

　　　　　　　　　　　　Return　returnArray　

　　　　　　　　　　　End　Function　



　　　　　　　　　　　　　　　　Now　the　code　doesn’t　have　a　keyhole　problem　from　the　perspective　of　DepthFirstSearch；　　

　　　　　　　　　　because　Node　will　always　indicate　the　appropriate　size　for　the　array。　If　there　is　still　not　enough　　

　　　　　　　　　　room；　the　problem　will　lie　with　Node。　This　is　not　an　ideal　solution；　but　sometimes　it’s　the　only　　

　　　　　　　　　　　option。　



　　　　　　　　　　　Using　the　For　Loop　



　　　　　　　　　　The　root　node　（root）　references　a　list　of　cities　that　are　available　as　a　starting　point。　To　start　off　　

　　　　　　　　　　the　search；　the　first　step　is　to　match　the　starting　city　with　the　start　parameter　by　iterating　over　　

　　　　　　　　　　the　list　of　cities。　For　that；　we　need　the　　For　loop。　Here　is　the　modified　source　code　of　　

　　　　　　　　　　　FindRoute（）：　



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

　　　　　　　　　　　　　　Dim　returnArray（Node。GetMaxPossibleDestinationsArraySize（））　As　Node　

　　　　　　　　　　　　　　For　c1　As　Integer　=　0　To　root。Length　1　　

　　　　　　　　　　　　　　　　　　If　Me。root（c1）。CityName。pareTo（start）　=　0　Then　

　　　　　　　　　　　　　　　　　　　　　　returnArray（0）　=　Me。root（c1）　

　　　　　　　　　　　　　　　　　　　　　　FindNextLeg（returnArray；　1；　finish；　root（c1））　

　　　　　　　　　　　　　　　　　　End　If　

　　　　　　　　　　　　　　Next　

　　　　　　　　　　　　　　Return　returnArray　

　　　　　　　　　　　End　Function　



　　　　　　　　　　　　　　　　The　For　loop　starts　counting　at　0　and　goes　to　the　end　of　the　　root　array　using　the　Me。root。　

　　　　　　　　　　　Length　property。　For　each　loop　iteration；　the　　root（c1）。CityName　is　tested　to　see　if　it　is　the　　

　　　　　　　　　　starting　city。　Then　the　starting　city　is　assigned　as　the　first　city　in　the　array　that　represents　the　　

　　　　　　　　　　found　travel　route　（returnArray（0）　=　Me。root（c1））。　Finally；　the　method　FindNextLeg（）　is　used　　

　　　　　　　　　　to　find　a　possible　route　to　the　destination。　


…………………………………………………………Page　127……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　　　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　105　



　　　　　A　　For　loop　is　used　to　go　through　a　series　based　on　some　logic。　For　the　most　part；　that　series　　

involves　incrementing　or　decrementing　numbers；　but　it　can　use　other　kinds　of　logic。　

　　　　　　The　　For　loop　has　the　following　form：　



For　＇variable＇　＇As　type＇　=　＇starting　condition＇　To　＇ending　condition＇　＇step　size＇　

　　　　　　　　＇Operations　of　doing　something＇　

Next　



where：　



　　　　　　＇variable＇：　Defines　the　variable　that　will　serve　as　the　counter　in　the　loop。　



　　　　　　＇As　type＇：　An　optional　definition　used　to　define　the　type　of　the　counter　in　the　loop。　For　the　　

　　　　　　most　part；　the　counter　will　be　a　numeric　value。　However；　you　can　have　other　types　as　long　　

　　　　　　as　the　increment　operators　are　supported。　　



　　　　　　＇starting　condition＇：　Defines　the　initial　state　of　the　counter　when　the　loop　is　started。　　



　　　　　　＇ending　condition＇：　Defines　the　ending　state　that　will　terminate　the　looping。　An　example　　

　　　　　　loop　termination　is　when　a　counter　reaches　the　maximum　length　of　an　array；　and　thus　no　　

　　　　　　more　elements　can　be　referenced。　



　　　　　　＇step　size＇：　　The　size　of　the　step　that　the　counter　should　take。　By　default；　the　size　of　a　step　　

　　　　　　is　1；　indicating　an　incrementing　counter　value。　If　the　step　size　were　　…1；　the　counter　would　　

　　　　　　decrement。　A　decrementing　counter　is　OK；　but　you　must　remember　to　assign　appropriate　　

　　　　　　starting　and　ending　conditions；　where　the　ending　condition　has　a　lesser　value　than　the　　

　　　　　　starting　condition。　



　　　　　　The　main　purpose　of　the　　For　loop　is　to　generate　a　series　of　numbers　that　could　be　used　as　　

indexes　to　an　array。　In　the　case　of　iterating　over　the　array；　it　generated　a　series　of　numbers　（0；　1；　　

2；　3；　and　so　on）；　and　each　number　was　then　used　to　reference　an　array　element　in　Me。root。　



■Note　　The　rule　of　thumb　for　a　　For　loop　is　that　it　is　employed　to