Re: [Tutor] When am I ever going to use this?
> 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. To be honest, with the possible exception of trees, not very often! Most of these data types are taught for historic reasons. Older programminng languages like assembler, C, BASIC, Fortran, Pascal typically only had arrays(and often only single dimensioned arrays) for collecting data, and arrays were either fixed size or had to be explicitly resized in blocks of storage. Thus a whole science grew up in Computing about how to represent data more abstractly using arrays as the underpinnings. For example a linked list could be built using 2 identical arrays. One held the data and the other held the index of the next item, like this: indexintListnext 0421 1272 266-1<-- where -1 indicates end of list... which was equivalent to a list: 42,27,66 Now we can insert a member between 42 and 27 by adding an item at index 3 then modifying the next value for 42 to be 3 and setting the next value at 3 to be 1 - like this: indexintListnext 0423 1272 266-1<-- where -1 indicates end of list... 3991 All very convoluted but produced the illusion of a python like list in a language without lists. But if the language has lists built in, which almost all modern languages do, there is no real need for most of this. You can add features like priorities and auto sorting etc etc, but this is almost trivial in modern languages whereas in old languages it was a lot of work. And if the language suuppors a dictionary type ijn addition to lists, and if it can store data of moxed types, then you can implement almost any abstract data collection easily. But the concepts of abstract data types are still taught to an increasingly bewildered audience... In practice, the average Python programmer can easily simulate or replace all of the classic data structures with built in types (with the possible exception of trees) or by using a relational database - the use of which wasn't possible in the 60's, 70's and early 80's because they hadn't been invented yet! Now implementing an RDBMS as part of a solution is so trivial that there's rarely need to worry about bulding trees etc for fast searches. That may be a slightly controversial view but it reflects my personal experience of programming with Python (and Ruby, Tcl, Smalltalk etc)! Of course if you ever have to use one of the older languages then the data structure stuff instantly applies again. HTH, Alan Gauld Author of the Learn to Program web site http://www.freenetpages.co.uk/hp/alan.gauld ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] When am I ever going to use this?
On 8/1/06, Christopher Spears <[EMAIL PROTECTED]> 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 amnot sure what they are used for.Queues and linked lists are also used extensively inside operating systems. Process lists are a large collections of queues organized in multiple queues implemented as linked lists and stored in one array. File systems store files by accessing data blocks through linked "blocks" (not quite the same as your linked node structure) and access to the disks and the network are through queues. Trees are used less often, but still very useful. The directory structure (folders and files) on your disk are trees, the program to search your email may use a tree. Stacks are often used for network protocols and program execution (every time you call a function, you are pushing something onto a stack). How about real life uses for these structures. Queues are one of the most natural structures from social life brought into computer science. Insects, banks, highways, birds, even the lunch line in grade school used queues. Stacks are the next, with stacks of books, papers, etc. Trees are used for people's genealogies. And you might used a linked list in a treasure hunt or for footnotes and bibliographies. Even post-it notes are a form of mental linked list. I hope this helps your understanding. -Arcege-- There's so many different worlds,So many different suns.And we have just one world,But we live in different ones. ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] When am I ever going to use this?
--- Christopher Spears <[EMAIL PROTECTED]> 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. > You probably use a linked list every day and don't even know it. Do you ever hit the "Back" button on your web browser to return to previous pages? The browser keeps a list of the pages you've visited, all linked together, so you can move backwards and forwards through the list. Here is a great resource for learning about different kinds of data structures: http://www.nist.gov/dads Regards, Marc __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] When am I ever going to use this?
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
||
||
cd -- 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!
___
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] When am I ever going to use this?
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. > > ___ > Tutor maillist - Tutor@python.org > http://mail.python.org/mailman/listinfo/tutor > They all have many uses. Priority Queues are used frequently in operating systems for process scheduling, etc. Trees are fantastic for most any searching application. Linked lists can be used for general purpose storage (since unlike arrays, their size is not fixed.) Learning data structures is really the one thing i wouldn't recommend python for, just because the job is usually done for you. Why implement a linked list, when we already have lists? Then Queues and Stacks are trivial to implement once you've got lists. If you're interested in learning more about data structures and their uses, this looks like a good reference: http://www.brpreiss.com/books/opus7/ -Jordan Greenberg ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
[Tutor] When am I ever going to use this?
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. ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
