按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
losangeles； seattle｝
End Sub
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
Public CityName As String
Public Connections As Node（）
Public Shared RootNodes As Node（）
Public X As Double
Public Y As Double
End Class
Defining the Algorithm Test
The Node type is a self…contained type； meaning that the algorithm does not need to instantiate
the tree structure （the Node constructor does it for you）。 This is an example of good design；
because if you had to add more cities； the only changes required would be to Node itself。 Any
search algorithm that uses the Node type does not need to be changed。
■Note When you have the ability to create code that localizes changes without affecting other pieces of
code； it is called decoupling code。 You want to write code that is decoupled from other code； so that when
changes are made in one piece of code； other pieces of code continue functioning。 As you will experience
when developing code； decoupling of code is a daily struggle。
For illustrative purposes； let’s try a first stab at the search algorithm and see where things
take us。 We could start by defining the search class or start by defining the test that will test the
search class。 Let’s define the test first； because it allows us to figure out what shape the search
class should take：
…………………………………………………………Page 121……………………………………………………………
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 99
Public Sub TestSearch（）
SearchAlgorithm。DepthFirstFindRoute（〃Montreal〃； 〃Seattle〃）
End Sub
In the test； the search algorithm is called directly using
SearchAlgorithm。DepthFirstFindRoute（）。 Here； SearchAlgorithm is the name of the class；
and DepthFirstFindRoute（） is the name of the method。 The class name implies that this class
will contain all search algorithm implementations。 This is wrong； because most likely； each
search algorithm will require multiple methods； leading to a very large and plicated
SearchAlgorithm class。 If this is the case； then maintaining the SearchAlgorithm class will
bee a nightmare。
A better solution would be to identify a single class as being a single implementation of a
search algorithm。 Then for each class； we can define a mon method identifier that is used
to find the route between two points。 Doing this results in the following modified test：
Public Sub TestSearch（）
DepthFirstSearch。FindRoute（〃Montreal〃； 〃Seattle〃）
End Sub
Now the test implies that the class DepthFirstSearch has a shared method FindRoute（）。
This is acceptable； and if you were to implement BreadthFirstSearch； the naming would be
BreadthFirstSearch。FindRoute（）。 However； there is another problem； which relates to multiple
users being able to use the algorithm during the execution of a program。 Going back to the
push…to…talk feature of a cell phone； the method FindRoute（） is shared and thus a shared
resource。 If multiple users do use this algorithm； they will share the resource。 This could be
problematic if you are storing temporary data in the data members of the DepthFirstSearch
class。 Using a shared method could corrupt your found search path。
The more appropriate solution is to define the method FindRoute（） as a non…shared
method； implying that DepthFirstSearch must be instantiated before we can call FindRoute（）。
We should modify the test again as follows：
Public Sub TestSearch（）
Dim cls As DepthFirstSearch = New DepthFirstSearch（）
cls。FindRoute（〃Montreal〃； 〃Seattle〃）
End Sub
To execute the method FindRoute（）； we need to create a DepthFirstSearch object； allowing
multiple users to perform searches without getting state mixed up。 At this point； we could pat
ourselves on the back and think that we have written a good test that requires a class
implementation。
The Problem of Magic Data
Our test is not yet plete； because we don’t have access to the route found by the algorithm；
but that will be explained in a moment。
In the implementation of DepthFirstSearch； a reference to the data structure is necessary。
The search algorithm needs to know which tree to navigate。 One way to implement a reference
to the tree is to directly reference the shared data Node。RootNodes。 An implementation of
DepthFirstSearch would be as follows：
…………………………………………………………Page 122……………………………………………………………
100 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 Class DepthFirstSearch
Public Sub FindRoute（ByVal start As String； ByVal finish As String）
Dim startNodes As Node（） = Node。RootNodes
End Sub
End Class
This example declares a variable called startNodes； which represents the starting point
and root of the tree as shown in Figure 4…2。 The root of the tree is based on the data member
Node。RootNodes； and this assignment is called a magic type assignment。 A magic type is formed
when you call a method； and magically； it happens to know how to reference data； even though
you never instructed the type。 In the case of DepthFirstSearch； the magic is the ability of
FindRoute（） to know to reference the correct data member RootNodes。
The assumption is bad because it couples the data member RootNodes to the method
FindRoute（）。 Imagine if the developer of the Node class later decides to add functionality to load
the tree from a file on the hard disk。 So that FindRoute（） is not broken； the developer would
need to explicitly copy the hard…disk…loaded tree to the data member RootNodes。
Or what if two different users wanted to create two different flight trees？ Node。RootNodes is
a shared resource； and thus can process only a single flight tree。 The developer of Node might
alter RootNodes； and thus FindRoute（） would behave erratically。
When you have a case of magic data； whatever data is magic needs to be passed to the type
via a constructor or other method。 So the test for the flight route would change to the following：
Public Sub TestSearch（）
Dim cls As DepthFirstSearch= _
New DepthFirstSearch（Node。RootNodes）
cls。FindRoute（〃Montreal〃； 〃Seattle〃）
End Sub
As the root tree node is required； we change the constructor to require that a caller pass in the
root tree node。 The test code still uses the shared data member RootNodes； but DepthFirstSearch
does not need to know where to find the tree。 If the Node developer were to alter the behavior of
the data member RootNodes； then only the constructor code to DepthFirstSearch would need
altering； not the FindRoute（） method。 Thus； Node and DepthFirstSearch are properly decoupled
from each other。
Getting the Found Route
Once you have called the FindRoute（） method； you expect an answer。 Because the route could
involve multiple cities； the found route is stored in an array of Node elements。 In programmatic
terms； there are two ways of