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

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




…………………………………………………………Page　100……………………………………………………………

78　　　　　　　　　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　



　　　　　　　　　　　■Note　　An　algorithm　is　a　logical　set　of　finite；　repeatable　steps　for　pleting　a　task。　The　term　is　usually　　

　　　　　　　　　　　applied　in　relation　to　formal　problems　such　as　searching；　but　most；　if　not　all　puter　programs；　use　algo

　　　　　　　　　　　rithms　of　one　sort　or　another。　



　　　　　　　　　　　　　　　　　Before　we　write　any　code；　you　need　to　understand　what　the　depth…first　search　algorithm　　

　　　　　　　　　　　does　and　why　you　would　use　it。　The　problem　to　solve　is　how　to　get　from　point　A　to　point　B　in　　

　　　　　　　　　　　the　most　efficient　manner。　This　problem　can　be　stated　generally　as；　“how　to　solve　task　A　when　　

　　　　　　　　　　　you　have　X　options。”　

　　　　　　　　　　　　　　　　　Imagine　you　are　about　to　drive　to　work　and　you　are　at　the　front　door　of　your　house。　You　　

　　　　　　　　　　　don’t　know　where　your　keys　are；　and　thus　you　begin　a　search　for　the　keys　in　the　house。　Of　　

　　　　　　　　　　　course；　you　try　to　remember；　but　your　memory　is　not　working　that　early　in　the　morning。　You　　

　　　　　　　　　　　try　to　retrace　your　steps；　and　think　of　logical　places　where　you　could　have　placed　your　keys。　　

　　　　　　　　　　　When　you　retrace　your　steps；　you　follow　your　memory’s　logic。　Simply　put；　your　search　algo

　　　　　　　　　　　rithm　is　based　on　your　memory’s　suggestion　of　where　the　keys　might　be。　The　data　structure　　

　　　　　　　　　　　that　you　are　navigating　is　the　rooms　of　your　house。　Your　brain…based　search　algorithm　could　　

　　　　　　　　　　　create　a　search　pattern　like　that　shown　in　Figure　4…1。　



　　　　　　　　　　　Figure　4…1。　A　possible　search　order　for　your　keys　



　　　　　　　　　　　　　　　　　In　Figure　4…1；　you　found　the　keys　in　the　hall；　but　yet　your　search　algorithm　led　you　astray　　

　　　　　　　　　　　for　a　while；　since　you　searched　the　hall　last。　The　cynic　could　say　that　you　kept　walking　around　　

　　　　　　　　　　　the　keys　without　realizing　that　they　were　so　close　to　you。　But　this　is　the　crux　of　the　problem；　　

　　　　　　　　　　　because　you　didn’t　know　you　developed　a　search　algorithm　that　would　lead　you　astray　this　　

　　　　　　　　　　　time。　And　the　same　algorithm　might　not　lead　you　astray　next　time。　　


…………………………………………………………Page　101……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　　　　　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　79　



■Note　　Searching　using　different　strategies　is　very　similar　to　how　you　will　write　puter　algorithms。　There　　

is　no　single　best　algorithm；　there　are　only　good　algorithms　that　have　certain　promises。　When　you　imple

ment　an　algorithm；　you　need　to　consider　the　one　that　best　suits　your　needs　with　the　least　number　of　　

promises　that　could　cause　problems。　



　　　　　　As　Figure　4…1　illustrates；　you　searched　in　a　counterclockwise　manner。　Another　strategy　　

would　have　been　to　go　clockwise　or　even　in　a　zigzag；　or　you　could　have　searched　some　rooms　　

multiple　times。　　

　　　　　　Let’s　convert　Figure　4…1　into　a　program　that　has　a　search　algorithm　and　a　data　structure。　　

The　search　algorithm　will　be　depth…first；　and　the　data　structure　will　be　based　on　a　path　between　　

the　respective　rooms。　The　data　structure　representing　the　house　in　Figure　4…1　is　illustrated　in　　

Figure　4…2。　



Figure　4…2。　A　tree　structure　illustrates　each　possible　action。　Highlighted　lines　represent　a　depth

first　search；　and　each　circle　represents　a　destination。　


…………………………………………………………Page　102……………………………………………………………

80　　　　　　　　　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　



　　　　　　　　　　　　　　　　　In　the　tree　structure　shown　in　Figure　4…2；　each　node　represents　a　destination　that　can　be　　

　　　　　　　　　　　reached　from　a　particular　place　in　the　house。　From　each　room；　you　can　reach　the　other　room。　　

　　　　　　　　　　　But　this　structure　is　recursive。　From　the　child　bedroom；　you　can　reach　the　living　room；　and　　

　　　　　　　　　　　then　you　can　reach　the　child　bedroom　again。　Even　though　you　navigated　down　the　tree；　you　　

　　　　　　　　　　　moved　from　one　room　to　another　and　back　to　the　original　room。　This　is　perfectly　acceptable　　

　　　　　　　　　　　from　a　data　structure　perspective；　even　though　you　are　probably　saying；　“But　that　is　wrong　　

　　　　　　　　　　　since　rooms　will　show　up　multiple　times。”　



　　　　　　　　　　　■Note　　The　tree　representation　in　Figure　4…2　is　by　no　means　plete；　because　from　each　room　you　can　　

　　　　　　　　　　　go　to　the　other　room。　A　full　tree　representation　would　be　a　binatorial　explosion。　



　　　　　　　　　　　　　　　　The　structure　is　the　way　it　is　because　the　data　structure　is　a　representation　of　the　house。　If　　

　　　　　　　　　　　you　were　searching　the　house；　would　you　be　able　to　move　from　one　room　to　another　and　back　　

　　　　　　　　　　　again？　Sure　you　would。　Would　you　do　it？　No；　because　your　search　algorithm　would　say；　“Hey　　

　　　　　　　　　　　dude；　you’re　repeating　yourself。”　And　therein　lies　the　trick　when　writing　applications。　You　have　　

　　　　　　　　　　　a　data　structure　and　an　algorithm　that　operates　on　the　data　structure。　I　call　this　building　an　　

　　　　　　　　　　　application　in　layers。　You　have　the　lowest　level；　which　is　an　intelligent　data　structure；　and　a　　

　　　　　　　　　　　higher　level　that　uses　the　functionality　of　the　intelligent　data　structure。　

　　　　　　　　　　　　　　　　　By　　intelligent　data　structure；　I　mean　that　the　structure　is　always　consistent　and　does　not　　

　　　　　　　　　　　corrupt　itself。　In　this　example；　a　room　will　not　point　to　itself；　a　room　will　be　present　in　the　struc

　　　　　　　　　　　ture　only　if　it　is　present　in　the　house；　and　so　on。　The　higher…level　algorithm　would　be　responsible　　

　　　　　　　　　　　for　figuring　out　how　to　find　information　in　the　tree。　It　should　be　smart　enough　to　realize　that　　

　　　　　　　　　　　constantly　traveling　between　two　rooms　is　not　going　to　achieve　anything　other　than　wasted　　

　　　　　　　　　　　time。　

　　　　　　　　　　　　　　　　The　search　logic　is　where　you　go　down　the　tree　traversing　one　room　after　another。　It　is　　

　　　　　　　　　　　called　a　depth…first　search　algorithm　because　you　iterate　the　tree　by　going　down　the　tree　one　　

　　　　　　　　　　　level　after　another。　You　stop　traversing　down　the　tree　once　you　reach　a　room　that　you　have　　

　　　　　　　　　　　already　traversed。　Then　you　go　back　one　level　and　traverse　the　room　beside　the　room　that　　

　　　　　　　　　　　you　have　already　traversed。　This　could　mean　the　search　path　found　by　the　puter　would　　

　　　　　　　　　　　be　similar　to　Figure　4…1。　That’s　because　the　puter　is　as　dumb　as　you　are；　albeit　the　puter　is　　

　　　　　　　　　　　not　saying　to　itself；　“If　only　I　had　started　in　the　hall。”　

　　　　　　　　　　　　　　　　　Realize　that　there　is　no　magic　wand　to　find　the　keys　for　you。　The　technique　that　you　and　　

　　　　　　　　　　　the　puter　used　is　called　brute　force；　and　it　is　putationally　expensive　and　typically　avoided。　　

　　　　　　　　　　　In　this　case　though；　brute　force　is　the　only　real　solution；　because　you　don’t　know　where　the　　

　　　　　　　　　　　keys　are—they　could　be　anywhere　in　the　house。　It　just　happened　to　be　your　bad　luck　that　the　　

　　　　　　　　　　　keys　were　found　in　the　last　place　you　looked。　　

　　　　　　　　　　　　　　　　　Let’s　try　to　improve　the　situation。　Imagine　for　a　moment　that　your　keys　are　tagged　with　a　　

　　　　　　　　　　　clapper。　The　idea　is　that　with　your　keys　going　“beep；　beep；　beep；”　you　will　be　able　to　instantly　　

　　　　　　　　　　　find　them　and　avoid　the　brute…force　searching。　But　suppose　that　the　keys　are　in　the　upper…right　　

　　　　　　　　　　　corner　of　the　child　bedroom。　Listening　for　the　beeping；　you　think　that　you　hear　the　keys　either　　

　　　　　　　　　　　in　the　kitchen　or　the　child　bedroom。　So；　where　do　you　go　first？　　


…………………………………………………………Page　103……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　　　　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　81　



　　　　　　Which　path　es　first　or　is　the　most　efficient　is　a　mon　problem；　and　you　may　witness　　

it　every　day　if　you　have　a　global　positioning　system　（GPS）　for　you　car。　A　search　algorithm　is　　

monly　used　in　GPS　devices。　You　punch　in　a　set　of　coordinates；　and　the　GPS　device　will　　

attempt　to　find　the　quickest　or　shortest　way。　In　the　abstract　sense；　the　search　algorithm　the　GPS　　

makers　apply　is　identical　to　the　search　algorithm　that　we　are　going　to　develop　in　this　chapter。　



Implementing　User…Defined　Types　



The　data　structure　on　which　the　algorithm　will　operate　is　a　user…defined　type。　In　the　examples　　

up　to　this　point；　we　have　been　using　types　like　Double　and　String；　which　are　CLR…provided　　

types。　For　the　example　in　this　chapter；　we　will　define　our　own　type；　which　we　will　use　to　repre

sent　a　node　in　the　tree。　



Declaring　Structures　and　Classes　



A　user…defined　type　can　be　implemented　in　one　of　two　ways：　as　a　structure　or　as　a　class。　An　　

example　of　each　is　shown　in　Figure　4…3。　



　　　　　　　A　type　declaration　requireA　type　declaration　requiress　a　　a　CCLRLR　In　Visual　Basic；　an　appropriate　

　　　　conconsstruct　（e。g。；　truct　（e。g。　SStructure　or　tructure　or　CClalassss）　and）　and　keyword　（e。g。；　Class）　opens　a　block。　

　　　　　　　　　　　　an　identifier　（e。g。；　Node）an　identifier　（e。g。　Node）　To　close　the　block；　the　keyword　is　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　bined　with　the　End　identifier。　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Everything　in　between　belongs　to　

　Structure　Node　　　　　　　　　　　　　　　　　　　　　　Class　Node　　　　　　　　　　　　　　　　　the　keyword。　So；　if　the　keyword　is　

　End　Structure　　　　　　　　　　　　　　　　　　　　　　　End　Class　　　　　　　　　　　　　　　　　　　Class；　everything　within　the　block　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　belongs　to　the　creation　of　a　class　



　　　Structure　is　used　to　define　

　　　a　custom　value　type　（e。g。；　

　　　　Double）；　which　has　some　　　　　　　　　　　　　　　Class　is　used　to　define　a　custom　reference　type　

　　restrictions　and　is　used　only　　　　　　　　　　　　（e。g。；　String）；　which　is　the　most　mon　type　

　　　　　　　in　certain　situations　　　　　　　　　　　　　　　　　　　　　　　　　　　　used　for　development　



Figure　4…3。　Choices　for　implementing　the　Node　custom　type　



　　　　　　As　shown　in　Figure　4…3；　you　can　choose　to　create　a　user…defined　type　as　a　value　type　　

（Structure）　or　reference　type　（Class）　type。　For　the　most　part；　developers　use　a　reference　type；　　

because　it　has　fewer　constraints　and　is　easiest　to　use　in　a　general　context。　A　value　type　has　some　　

constraints　due　its　behavior　of　storing　everything　on　the　stack；　as　discussed　in　the　following　　

sections。　



Value　Type　Constraints　



The　constraints　of　using　a　value　type　relate　to　the　fact　that　data　is　copied。　This　has　an　impact　on　　

what　happens　when　you　embed　reference　types　in　value　types　and　use　value　types　as　parame

ters　to　methods。　


…………………………………………………………Page　104……………………………………………………………

82　　　　　　　　　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　Effects　of　Copying　Data　



　　　　　　　　　　　　When　one　　value　type　is　assigned　to　another　value　type；　the　contents　of　the　value　types　are　copied。　　

　　　　　　　　　　　　To　see　this　in　action；　consider　the　declarations　in　Figure　4…4。　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Declaration　of　the　identifier　

　　　　　　　　　　　　　Custom　value　type　declaration　　　　　　　　　　value　is　inside　the　block；　so　it　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　belongs　to　the　custom　type　



　　　　　　　　　　　　　　　　Structure　MyValueType　

　　　　　　　　　　　　　　　　　　　　Public　value　As　Integer　　　　　　　　　　　　　　Declaration　of　value　is　associated　

　　　　　　　　　　　　　　　　End　Structure　　　　　　　　　　　　　　　　　　　　　　　　　　with　a　type　identifier　（Integer）　and　a　

　　　　　　　　　　　　　　　　Class　MyReferenceType　　　　　　　　　　　　　　　　　　　　　　　　　scope　identifier　（Public）　



　　　　　　　　　　　　　　　　　　　　Public　value　As　Integer　

　　　　　　　　　　　　　　　　End　Class　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Custom　reference　type　declaration　



　　　　　　　　　　　　　　　　　　　　　　Both　custom　types　declare　a　variable　

　　　　　　　　　　　　　　　　　　　　　that　is　a　value　type；　which　is　called　a　

　　　　　　　　　　　　　　　　　　　　data　member　because　it　belongs　to　the　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　custom　type　declaration　



　　　　　　　　　　　　Figure　4…4。　Declaring　custom　types　



　　　　　　　　　　　　　　　　　When　declaring　user…defined　types；　the　data　members　and　methods　are　declared　inside　　

　　　　　　　　　　　　the　block　of　code。　You　can　think　of　the　declaration　as　the　writing　on　the　outside　of　the　box；　and　　

　　　　　　　　　　　　anything　in　the　block　of　code　as　the　contents　of　the　box。　The　custom　types　（MyValueType　and　　

　　　　　　　　　　　　MyReferenceType）　as　declared　in　Figure　4…4　do　not　have　a　scope　identifier。　Think　of　a　scope　identifier　　

　　　　　　　　　　　　as　defining　who　has　access　to　your　pockets　and　wallet。　In　the　case　of　the　types　in　the　example；　　

　　　　　　　　　　　　the　scope　is　like　saying　that　your　spouse　is　allowed　to　peek　into　your　wallet；　but　strangers　　

　　　　　　　　　　　　cannot。　In　other　words；　the　types　cannot　be　used　outside　their　own　namespace。　

　　　　　　　　　　　　　　　　　If　the　Public　keyword　had　been　in　front　of　the　type　identifier；　then　the　user…defined　type　　

　　　　　　　　　　　　would　be　exposed　like　a　wallet　that　is　allowed　to　be　peeked　into　by　the　general　public。　This　means　　

　　　　　　　　　　　　the　types　can　be　used　by　other　code。　In　the　case　of　the　wallet；　it’s　a　bad　idea　to　have　unfettered　　

　　　　　　　　　　　　public　scope；　but　sometimes　public　scope　is　desirable　when　you　are　able　to　control　its　access。　　

　　　　　　　　　　　And　you　do　this　every　time　you　pay　for　something　by　handing　a　credit　card　to　the　cashier。　In　　

　　　　　　　　　　　　that　case；　you　are　publicly　exposing　parts　of　your　wallet　under　your　supervision。　In　code　terms；　　

　　　　　　　　　　　　this　means　making　your　types　public；　but　not　necessarily　making　the　data　members　public。　

　　　　　　　　　　　　　　　　　Next；　consider　the　code　in　Figure　4…5。　It　instantiates　MyValueType　and　assigns　it　to　another　　

　　　　　　　　　　　　variable　of　the　same　type。　

　　　　　　　　　　　　　　　　　The　example　in　Figure　4…5　illustrates　what　happens　to　two　variables　when　one　is　instanti

　　　　　　　　　　　　ated　and　assigned　to　the　other；　and　then　the　other　is　modified。　You　want　to　understand　how　　

　　　　　　　　　　　　each　data　type　is　modified　when　an　interaction　with　another　type　occurs。　　


…………………………………………………………Page　105……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　　　　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　83　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　To　create　a　valid　instance　

　　　　Variable　var　is　declared；　　　　　　　　　　　associated　with　the　

　　　but　a　declaration　does　not　　　　　　　　　variable　var；　you　need　to　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Another　way　to　associate　a　

　　　　　　imply　a　valid　instance　　　　　　　　　　allocate　the　object　using　　　　　　　valid　instance　with　a　variable　is　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　the　New　keyword　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　to　assign　the　variable　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（e。g。；　copiedVar）　from　another　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　variable