按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 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