VB2008从入门到精通(PDF格式英文版)-第32部分
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
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 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 ind
