按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
involve multiple cities； the found route is stored in an array of Node elements。 In programmatic
terms； there are two ways of retrieving the array of Nodes。 The first is a return value； like this：
Public Sub TestSearch（）
Dim cls As DepthFirstSearch = New DepthFirstSearch（Node。RootNodes）
Dim foundRoute As Node（） = cls。FindRoute（〃Montreal〃； 〃Seattle〃）
End Sub
The bold code shows the assignment of the return value to the variable foundRoute。
…………………………………………………………Page 123……………………………………………………………
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 101
The second approach is for the FindRoute（） method to store the result in an internal data
member。 The following example assumes that the FindRoute（） method stores the result in a
data member named FoundRoute：
Public Sub TestSearch（）
Dim cls As DepthfirstSearch = New DepthFirstSearch（Node。RootNodes）
cls。FindRoute（〃Montreal〃； 〃Seattle〃）
Dim foundRoute As Node（） = cls。FoundRoute
End Sub
Each approach seems acceptable； and you are not sure which to use。 When you have a
choice like this； you need to make a decision。 The safest way to make a decision is to write tests
and see if there are any problems with either approach。
In the example of calculating a single route； either approach is fine。 But let’s look at the
code when multiple routes are being searched。 First； consider the code where the found path
is a return parameter value：
Public Sub TestSearch（）
Dim cls As DepthFirstSearch = New DepthFirstSearch（Node。RootNodes）
Dim foundRoute1 As Node（） = cls。FindRoute（〃Montreal〃； 〃Seattle〃）
Dim foundRoute2 As Node（） = cls。FindRoute（〃New York〃； 〃Seattle〃）
End Sub
Now take a look at the code that uses the data member：
Public Sub TestSearch（）
Dim cls As DepthFirstSearch = New DepthFirstSearch（Node。RootNodes）
cls。FindRoute（〃Montreal〃； 〃Seattle〃）
Dim foundRoute1 As Node（） = cls。FoundRoute
cls。FindRoute（〃New York〃； 〃Seattle〃）
Dim foundRoute2 As Node（） = cls。FoundRoute
End Sub
Again； it would seem that both choices are adequate。 However； there is a difference； the
difference is subtle； but distinct enough to matter。 In the test implementation where the found
route is a return value； the variables foundRoute1 and foundRoute2 represent routes that relate
directly to the route being searched。 There is no chance that the variables foundRoute1 can
represent the route New York–Seattle。 With the data member code； it could happen that
foundRoute1 points to the route New York–Seattle； as shown in the following code。
Public Sub TestSearch（）
Dim cls As DepthFirstSearch = New DepthFirstSearch（Node。RootNodes）
cls。FindRoute（〃Montreal〃； 〃Seattle〃）
cls。FindRoute（〃New York〃； 〃Seattle〃）
Dim foundRoute1 As Node（） = cls。FoundRoute
Dim foundRoute2 As Node（） = cls。FoundRoute
End Sub
…………………………………………………………Page 124……………………………………………………………
102 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
By switching the order of the FindRoute（） method calls and references to the data member
FoundRoute； the variables foundRoute1 and foundRoute2 will reference the same found route；
specifically the route New York–Seattle。 This is not a good idea。 The example shows how data
members have no direct relation to methods and can vary independently。
So the choice of returning the found route from a method is the better and more robust
approach。
■Note Data members are useful when you want to store or retrieve data that spans multiple method calls
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