VB2008从入门到精通(PDF格式英文版)-第40章

按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！



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　generate　an　index　series　that　is　used　to　　

reference　another　piece　of　information。　The　index　series　could　be　a　direct　array　element　reference；　or　it　could　　

be　used　to　perform　a　calculation；　which　is　then　used　to　generate　a　reference　to　a　piece　of　data。　The　index　　

series　does　not　need　to　generate　incremental　or　decremental　values。　The　index　series　does　need　to　generate　　

a　logical　index　series。　



Using　the　If　Statement　



When　the　starting　point　city　has　been　found；　the　tree　will　begin　to　search　down　the　tree。　A　　

depth…first　search　means　that　the　search　will　travel　down　the　tree　as　far　as　it　can　before　back

tracking　and　trying　other　routes。　The　recursion　of　traveling　down　the　tree　is　managed　by　the　　

FindNextLeg（）　method；　which　is　defined　as　shown　in　Figure　4…16。　


…………………………………………………………Page　128……………………………………………………………

106　　　　　　　　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　



　　　　　　　　　　　　　　　　　　Loop　used　to　generate　the　index