[Tutor] When am I ever going to use this?
Danny Yoo
dyoo at hkn.eecs.berkeley.edu
Wed Aug 2 05:19:37 CEST 2006
On Tue, 1 Aug 2006, Christopher Spears wrote:
> I've been working through a tutorial:
> http://www.ibiblio.org/obp/thinkCSpy/index.htm. Lately, I have been
> learning about abstract data types (linked lists, stacks, queues, trees,
> etc.). While I do enjoy the challenge of creating these objects, I am
> not sure what they are used for.
Hi Chris,
Let say that we are trying to write a navigator program, one that helps
plan road trips. One portion of the input to this program would be a map
of the roads.
For example:
map = [('a', 'b'),
('a', 'c'),
('c', 'f'),
('b', 'd'),
('d', 'e'),
('d', 'f')]
might represent the following street map:
a ------ b
| |
| |
c d ------ e
\ |
\ |
----- f
where 'a', 'b', 'c', 'd', 'e', and 'f' are points of interest. (I'm
oversimplifying, but I hope you don't mind!)
A simple question we might ask this system is: how far is it from point
'a' to point 'f'? We'd like to ask the system:
distance('a', 'f', map)
and be able to get 2, since there's a hop from 'a' to 'c', and from 'c' to
'f'.
This problem is ripe to be attacked with an algorithm called
"breadth-first search", and breadth-first search typically is implemented
by keeping a queue of places. We can talk about this in more detail if
you'd like.
http://en.wikipedia.org/wiki/Breadth-first_search
This is a long hand-wavy example for a short explanation: queues and and
other data structures are "background" support tools: they themselves
aren't so interesting, but they're the tools that a programmer often will
reach for when working on non-string related problems.
If you remember Starcraft: there was a four-level queue of movement
commands that you could set up by holding "shift" while navigating your
forces. You could also "queue" up production orders in factories.
Same data structure. *grin*
Best of wishes!
More information about the Tutor
mailing list