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

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



least　let’s　try　it　and　see　what　happens。　

　　　　　As　per　the　attributes　illustrated　in　Figure　4…7；　the　data　structure　that　is　added　to　the　　

SearchSolution　project　is　implemented　as　shown　in　Figure　4…9。　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Name　of　the　city　



　Public　Structure　Node　

　　　　　Public　CityName　As　String　

　　　　　Public　X　As　Double　　　　　　　　　　　　　　　　　　　　　　　X　and　Y　coordinates　

　　　　　Public　Y　As　Double　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　of　the　city　

　　　　　Public　Connections　As　Node（）　

　End　Structure　



　　　　　　　　　　　　　　　　　　Array　of　cities　that　are　

　　　　　　　　　　　　　　　　　　　　reachable　from　the　

　　　　　　　　　　　　　　　　　　　　　　　　current　city　



Figure　4…9。　　The　data　structure　for　the　depth…first　search　



　　　　　The　data　structure　is　declared　as　a　Structure；　with　the　connections　represented　as　an　array　　

of　Node　elements。　An　array　of　　Node　elements　is　formed　when　one　　Node　contains　a　list　of　refer

ences　to　other　Node　elements。　Think　of　an　array　as　a　collection　of　sticky　notes　that　say；　“Here　is　　

a　reference　to　A；　B；　C；　and　so　on。”　By　having　one　node　reference　another　node；　a　sort　of　never

ending　tree　is　created；　because　it　is　possible　to　travel　back　and　forth　between　two　cities。　Thus；　　

the　depth…first　search　algorithm　will　need　to　avoid　repeating　itself。　

　　　　　The　Connections　data　member　is　an　array　used　to　define　cities　that　are　the　next　connection。　　

To　reference　another　city；　you　can　create　the　reference　as　an　array　of　Node　elements；　as　in　the　　

declaration　shown　in　Figure　4…9。　An　alternative　is　to　use　an　array　of　strings　that　contain　the　　

name　of　the　next　city；　like　this：　　


…………………………………………………………Page　112……………………………………………………………

90　　　　　　　　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　Structure　Node　　

　　　　　　　　　　　　　Public　CityName　As　String　

　　　　　　　　　　　　　Public　X　As　Double　

　　　　　　　　　　　　　Public　Y　As　Double　

　　　　　　　　　　　　　Public　Connections　As　String（）　

　　　　　　　　　　　End　Structure　



　　　　　　　　　　　　　　　　In　this　declaration；　Connections　is　an　array　of　strings　that　references　other　city　names　and　　

　　　　　　　　　　　is　what　humans　would　see　when　they　look　at　a　table　showing　all　of　the　connections　for　a　partic

　　　　　　　　　　　ular　city。　The　problem　with　using　strings　is　that　it　is　inefficient　from　a　puting　perspective。　　

　　　　　　　　　　　To　traverse　a　tree　of　cities；　you　would　first　traverse　the　city　names；　resolve　the　city　name　to　a　　

　　　　　　　　　　　Node　object；　and　then　traverse　the　node。　The　string　array　approach　requires　an　extra；　unneces

　　　　　　　　　　　sary　step。　So　the　more　efficient　and　programmatic　approach　is　to　have　an　array　of　Node　instances。　

　　　　　　　　　　　　　　　　By　using　the　declaration　where　Connections　is　an　array　of　Node　instances；　you　have　both　　

　　　　　　　　　　　the　city　name　and　available　connections　in　one　cohesive　object。　　



　　　　　　　　　　　Instantiating　and　Initializing　a　Node　



　　　　　　　　　　　In　previous　code；　you　have　seen　how　objects　can　be　instantiated　using　the　New　keyword。　To　　

　　　　　　　　　　　instantiate　a　type；　you　always　use　the　New　keyword。　After　the　New　keyword　is　the　type　that　you　　

　　　　　　　　　　　want　to　instantiate；　followed　by　a　set　of　parentheses。　A　node　is　instantiated　using　the　following　　

　　　　　　　　　　　code：　



　　　　　　　　　　　Dim　city　As　Node　=　New　Node（）　



　　　　　　　　　　　　　　　　If　you　look　only　at　the　identifier　Node　with　parentheses；　you　would　get　the　impression　that　　

　　　　　　　　　　　you　are　calling　a　method　that　has　no　parameters。　The　impression　is　correct；　but　it　is　a　special　　

　　　　　　　　　　　type　of　method　call；　and　that　is　made　apparent　by　the　use　of　the　New　keyword。　The　method　that　　

　　　　　　　　　　　is　being　called　is　known　as　a　constructor。　Every　type　has　a　constructor；　and　it　can　be　used　to　　

　　　　　　　　　　　initialize　the　state　of　the　object　before　being　returned　to　the　caller。　

　　　　　　　　　　　　　　　　In　the　declaration　of　Node；　there　is　no　defined　constructor；　and　thus　a　default　constructor　　

　　　　　　　　　　　is　provided　by　the　CLR。　The　default　constructor　does　nothing　and　has　no　parameters。　　

　　　　　　　　　　　　　　　　After　having　instantiated　a　node；　we　can　assign　the　data　members；　as　in　the　following　　

　　　　　　　　　　　code。　



　　　　　　　　　　　city。CityName　=　〃Montreal〃　

　　　　　　　　　　　city。X　=　0。0　

　　　　　　　　　　　city。Y　=　0。0　



　　　　　　　　　　　　　　　　Assigning　the　data　members　results　in　setting　the　city　name　to　Montreal　and　the　coordi

　　　　　　　　　　　nates　to　（0；0）。　

　　　　　　　　　　　　　　　　This　is　all　fine；　but　shouldn’t　we　need　to　provide　some　data　members　when　creating　a　city　　

　　　　　　　　　　　node？　Does　it　make　sense　to　instantiate　a　node　without　defining　the　name　and　coordinates　of　　

　　　　　　　　　　　the　city？　Technically；　a　node　does　not　need　to　be　assigned；　but　logically　speaking；　an　unassigned　　

　　　　　　　　　　　node　is　quite　useless。　And　remember　that　we　are　working　on　defining　an　intelligent　data　struc

　　　　　　　　　　　ture；　thus　a　Node　instance　without　city　name　and　coordinates　is　logically　not　a　valid　　Node。　We　　

　　　　　　　　　　　also　need　to　have　a　root　for　the　Node　structure；　which　we　will　set　up　as　an　array。　

　　　　　　　　　　　　　　　　You　can　enforce　a　verifiable　correct　initial　state　by　defining　a　constructor　with　parameters；　　

　　　　　　　　　　　rather　than　using　the　default　constructor；　as　in　the　following　example。　When　your　code　provides　　


…………………………………………………………Page　113……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　　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　91　



a　constructor；　regardless　of　the　declaration；　the　default　constructor　is　not　generated　and　is　not　　

accessible。　



Public　Structure　Node　　

　　　　Public　Shared　RootNodes　As　Node（）　

　　　　Public　CityName　As　String　

　　　　Public　X　As　Double　

　　　　Public　Y　As　Double　

　　　　Public　Connections　As　Node（）　



　　　　Public　Sub　New（ByVal　city　As　String；　ByVal　X　As　Double；　ByVal　Y　As　Double）　

　　　　　　　　Me。CityName　=　city　

　　　　　　　　Me。X　=　x　

　　　　　　　　Me。Y　=　y　

　　　　　　　　Me。Connections　=　Nothing　

　　　　End　Sub　

End　Structure　



■Note　　Nothing　is　a　special　value　that　you　can　assign　to　reference　variables。　It　means　that　the　reference　　

variable　does　not　point　to　a　real　object。　Nothing　is　a　useful　value　to　assign　to　reference　variables　in　a　constructor；　　

if　you　don’t　have　a　meaningful　object　that　they　can　point　to　at　the　outset。　



　　　　　To　define　a　constructor；　you　define　a　method　of　type　Sub　called　New（）。　And；　in　most　cases；　　

you　will　use　public　scope。　The　parameters　of　the　constructor　represent　the　three　pieces　of　　

information　that　are　required　to　instantiate　a　valid　state。　Within　the　constructor；　the　data　　

members　are　assigned　the　values　of　the　parameters。　

　　　　　The　defined　constructor　has　parameters；　which　means　that　to　instantiate　Node；　you　need　　

to　provide　the　three　pieces　of　data。　Thus；　to　instantiate　Node；　you　need　to　provide　enough　data　　

to　make　the　node　logical。　The　original　instantiation　code　would　not　pile；　so　to　pile　the　　

code；　you　need　to　modify　the　instantiation　to　the　following：　



Dim　city　as　Node　=　New　Node（〃Montreal〃；　0。0；　0。0）　



　　　　　The　declaration　of　the　node　might　reference　incorrect　data；　but　that　is　not　the　responsibility　　

of　the　intelligent　data　structure。　An　analogy　is　that　a　word　processor　by　itself　is　not　responsible　for　　

making　sure　that　the　text　you　write　makes　sense。　The　role　of　the　word　processor　is　to　give　you　　

the　ability　to　construct　intelligent　text。　



Examining　the　Problem　of　Referencing　Using　Value　Types　



As　you’ve　learned；　a　value　type　is　stored　on　the　stack；　and　its　contents　are　copied；　not　refer

enced。　When　you　are　trying　to　build　a　tree　structure　with　a　value　type；　references　that　were　　

assigned　are　not　updated　with　the　correct　information　because　values　are　copied。　This　effect　　

can　be　demonstrated　by　going　through　a　longer　example　of　building　a　data　structure　of　cities　　

that　can　be　reached　from　another　city。　To　start　off；　consider　the　following　declaration　of　all　the　　

cities　and　their　coordinates。　


…………………………………………………………Page　114……………………………………………………………

92　　　　　　　　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　



　　　　　　　　　　　Dim　montreal　As　Node　=　New　Node（〃Montreal〃；　0；　0）　

　　　　　　　　　　　Dim　newyork　As　Node　=　New　Node（〃New　York〃；　0；　…3）　

　　　　　　　　　　　Dim　miami　As　Node　=　New　Node（〃Miami〃；　…1；　…11）　

　　　　　　　　　　　Dim　toronto　As　Node　=　New　Node（〃Toronto〃；　…4；　…1）　

　　　　　　　　　　　Dim　houston　As　Node　=　New　Node（〃Houston〃；　…10；　…9）　

　　　　　　　　　　　Dim　losangeles　As　Node　=　New　Node（〃Los　Angeles〃；　…17；　…6）　

　　　　　　　　　　　Dim　seattle　As　Node　=　New　Node（〃Seattle〃；　…16；　…1）　



　　　　　　　　　　　　　　　　This　code　creates　several　Node　objects　that　represent　all　of　the　cities　from　Figure　4…7。　The　　

　　　　　　　　　　　individual　objects　are　cities　without　connections；　and　the　next　step　is　to　connect　one　city　to　　

　　　　　　　　　　　another。　We　need　to　allocate　and　assign　the　Connections　data　member。　　

　　　　　　　　　　　　　　　　Having　initialized　all　of　the　individual　cities；　the　next　step　is　to　cross…reference　the　destina

　　　　　　　　　　　tions　of　each　city。　In　Visual　Basic；　the　array　requires　some　special　understanding。　The　Connections　　

　　　　　　　　　　　data　member　is　an　empty　array　without　any　elements。　This　is　not　a　problem；　as　long　as　you　　

　　　　　　　　　　　don’t　attempt　to　reference　or　assign　any　of　the　elements。　　

　　　　　　　　　　　　　　　　You　need　to　allocate　space　for　the　array　so　that　you　can　store　the　individual　cities。　One　　

　　　　　　　　　　　solution　is　to　reassign　the　array　to　another　array　that　contains　elements；　as　follows：　



　　　　　　　　　　　montreal。Connections　=　New　Node（）　｛newyork；　toronto；　losangeles｝　



　　　　　　　　　　　　　　　　In　this　example；　the　Connections　data　member　is　reassigned　with　the　contents　of　another　　

　　　　　　　　　　　array　that　has　been　allocated　to　contain　the　three　cities；　newyork；　toronto；　and　losangeles。　　

　　　　　　　　　　　Think　of　the　array　as　a　basket。　Using　this　approach；　the　original　empty　basket　has　been　replaced　　

　　　　　　　　　　　with　a　basket　of　three　items。　These　three　items　can　be　referenced　using　three　indices　（0　=　newyork；　　

　　　　　　　　　　　1　=　toronto；　2　=　losangeles）。　This　solution　creates　a　fixed…content　basket。　

　　　　　　　　　　　　　　　　Alternatively；　you　could　create　space　in　the　basket　and　then　manually　fill　the　basket；　as　follows：　



　　　　　　　　　　　ReDim　montreal。Connections（2）　　

　　　　　　　　　　　montreal。Connections（0）　=　newyork　

　　　　　　　　　　　montreal。Connections（1）　=　toronto　

　　　　　　　　　　　montreal。Connections（2）　=　losangeles　



　　　　　　　　　　　　　　　　The　ReDim　statement　takes　the　array　referenced　by　the　data　member　Connections　and　real

　　　　　　　　　　　locates　it　to　a　new　size。　That　size　could　be　larger　or　smaller　than　the　current　size。　In　the　example；　　

　　　　　　　　　　　the　size　of　the　array　is　2；　which　does　not　mean　two　elements；　but　rather　that　it　is　an　array　sized　　

　　　　　　　　　　　from　the　index　0　to　2。　　

　　　　　　　　　　　　　　　　The　ReDim　statement　actually　performs　a　redimension　of　an　array。　The　example　demon

　　　　　　　　　　　strates　using　it　on　an　empty　array；　but　you　can　also　use　it　with　an　array　that　contains　data；　such　　

　　　　　　　　　　　as　to　enlarge　an　array　without　losing　the　old　data。　To　keep　the　old　data　in　a　new　array；　you　use　　

　　　　　　　　　　　the　Preserve　keyword；　as　follows：　



　　　　　　　　　　　ReDim　Preserve　montreal。Connections（2）　　

　　　　　　　　　　　montreal。Connections（0）　=　newyork　

　　　　　　　　　　　montreal。Connections（1）　=　toronto　

　　　　　　　　　　　montreal。Connections（2）　=　losangeles　



　　　　　　　　　　　　　　　　However；　be　aware　that　if　the　ReDim　statement　causes　an　array　to　shrink；　you　can　still　lose　　

　　　　　　　　　　　data—whatever　elements　are　located　above　the　array　size　are　discarded。　To　be　safe；　before　　

　　　　　　　　　　　using　ReDim；　you　might　want　to　reference　the　array’s　　Length　property　to　verify　that　you　are　not　　

　　　　　　　　　　　shrinking　the　array　and　losing　data。　


…………………………………………………………Page　115……………………………………………………………

　　　　　　　　　　　　　　　　　　　　　　　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　93　



　　　　　Using　either　the　fixed…content　or　ReDim　approach；　you　allocate　space　for　the　array　and　assign　　

the　variables　representing　the　cities　to　the　individual　elements　of　the　array。　Since　Connections　　

is　an　array　of　value　types；　the　connections　within　the　connections　are　not　set；　as　shown　in　　

Figure　4…10。　



Figure　4…10。　　The　problem　of　the　missing　connections　for　New　York　



　　　　　The　problem　is　that　the　Connections　array　for　New　York　is　missing。　Of　course；　you　could　be　　

logical　and　say　it　is　missing　because　the　Connections　data　member　for　New　York　has　not　yet　　

been　defined。　But；　and　it　is　a　big　but；　think　about　how　data　is　referenced　and　think　about　the　　

behavior　summarized　in　Table　4…1。　

　　　　　　Node　is　a　value　type；　and　when　a　value　type　is　assigned；　the　values　within　the　type　are　copied。　　

Because　the　connections　for　New　York　have　not　been　assigned；　the　Montreal　Connections　array　　

will　not　contain　any　connections　from　New　York。　And　if　you　modify　the　original　variable　for　　

New　York　and　its　connections；　those　changes　will　not　be　reflected　in　the　array　of　connections　　

that　Montreal　has。　

　　　　　At　this　point；　you　might　think　this　is　not　a　problem；　but　consider　the　following　New　York　code：　



ReDim　newyork。Connections（2）　　

newyork。Connections（0）　=　montreal　

newyork。Connections（1）　=　houston　

newyork。Connections（2）　=　miami　



　　　　　In　this　example；　New　York　has　a　connection　to　Montreal；　and　Montreal　has　a　connection　　

to　New　York；　pleting　a　full　circle。　muters　would　want　this　ability　to　fly　back　and　forth　　

between　cities。　But　because　we　are　using　value　types；　it　is　not　possible　to　fly　back　and　forth；　as　　

illustrated　by　Figure　4…11。　

　　　　　Figure　4…11　illustrates　that　recursion　with　value　types　does　not　work。　It　shows　that　there　　

are　connections　from　New　York　to　Montreal。　But　following　the　connection　to　Montreal；　it　would　　

appear　that　New　York　has　no　connections；　which　is　blatantly　false；　because　we　can　see　the　　

connection　from　New　York　to　Montreal。　


…………………………………………………………Page　116……………………………………………………………

94　　　　　　　　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　



　　　　　　　　　　　Figure　4…11。　Missing　connections　for　New　York　



　　　　　　　　　　　　　　　　When　value　types　are　assigned；　you　are　copying　contents　of　the　value　type　and　thus　getting　　

　　　　　　　　　　　a　snapshot　of　the　state　of　an　object　at　some　period　in　time。　In　essence；　the　code　illustrates　the　　

　　　　　　　　　　　chicken…and…egg　problem　of　defining　the　connections　for　a　particular　city　and　then　assigning　　

　　　　　　　　　　　them。　For　value　types；　how　can　you　assign　the　connection　of　one　city　to　another　when　the　to

　　　　　　　　　　　be…assigned　connection　does　not　exist？　The　short　answer　is　you　can’t。　The　long　answer　is　you　　

　　　　　　　　　　　can；　but　it　would　mean　executing　an　infinite　loop；　which　is　of　no　use　to　us；　because　we　want　to　　

　　　　　　　　　　　do　something　with　the　data　once　it　has　been　assigned。　



　　　　　　　　　　　Switching　to　a　Class　to　Defi