Difference between revisions of "DataStructures"
Jump to navigation
Jump to search
| (15 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[Category:Pragmatic Programming]] | [[Category:Pragmatic Programming]] | ||
| − | ''''Data Structures: | + | ''''Data Structures: starting to designing your program'''' |
=Introduction= | =Introduction= | ||
| + | |||
| + | '''''If your data structures effectively represent your area of modelling interest, the logic and control flow of your code will be naturally constrained and hence simpler and more robust to bugs.''''' | ||
<pre> | <pre> | ||
svn co http://soutce.ggy.bris.ac.uk/subversion-open/data-structures/trunk ./data-structures | svn co http://soutce.ggy.bris.ac.uk/subversion-open/data-structures/trunk ./data-structures | ||
</pre> | </pre> | ||
| + | |||
| + | [[Image:Rube-goldberg-toothpaste.jpg|365px|thumbnail|none|less like this...]] | ||
| + | [[Image:Lego.jpg|365px|thumbnail|none|..and more like this.]] | ||
=Stacks= | =Stacks= | ||
| Line 15: | Line 20: | ||
./simple-stack.exe | ./simple-stack.exe | ||
</pre> | </pre> | ||
| + | |||
| + | * The deliberately constrained nature of the stack gives elements a '''natural order'''. | ||
| + | * Elements added early remain in the stack the longest. | ||
| + | |||
| + | [[Image:stack-drawers.jpg|300px|thumbnail|none|A Stack.., in this case of boxes.]] | ||
=Linked Lists= | =Linked Lists= | ||
| + | |||
| + | <pre> | ||
| + | cd ../example2 | ||
| + | make | ||
| + | ./simple-LL.exe | ||
| + | </pre> | ||
| + | |||
| + | * Can grow with more data | ||
| + | * Can insert items in the middle of the list (e.g. can store items in order which arrive out of order) | ||
| + | |||
| + | [[Image:Toytrain.jpg|300px|thumbnail|none|A train--of knitted pigs--is much like a linked list.]] | ||
=Hash Tables= | =Hash Tables= | ||
| + | |||
| + | <pre> | ||
| + | cd examples/example1 | ||
| + | make | ||
| + | ./simple-hash.exe | ||
| + | </pre> | ||
| + | |||
| + | * Content addressable storage. | ||
| + | * Must manage potential collisions. | ||
| + | |||
| + | [[Image:450pxHashTable.png|300px|thumbnail|none|A hash table mapping names to phone numbers.]] | ||
=Trees= | =Trees= | ||
| + | |||
| + | ==Searchtrees== | ||
| + | |||
| + | ==Quadtrees== | ||
http://en.wikipedia.org/wiki/Quadtree | http://en.wikipedia.org/wiki/Quadtree | ||
| + | |||
| + | A quadtree could be used to store: | ||
| + | |||
| + | * A sparse matrix (Can think of an image this way) | ||
| + | * Variable resolution data (parent's value is the average of its children's values) | ||
=The C++ Standard Template Library= | =The C++ Standard Template Library= | ||
| + | |||
| + | Pretty much rocks. And saves you the hassle of writing all these data structures yourself. | ||
Latest revision as of 19:19, 13 April 2010
'Data Structures: starting to designing your program'
Introduction
If your data structures effectively represent your area of modelling interest, the logic and control flow of your code will be naturally constrained and hence simpler and more robust to bugs.
svn co http://soutce.ggy.bris.ac.uk/subversion-open/data-structures/trunk ./data-structures
Stacks
cd examples/example1 make ./simple-stack.exe
- The deliberately constrained nature of the stack gives elements a natural order.
- Elements added early remain in the stack the longest.
Linked Lists
cd ../example2 make ./simple-LL.exe
- Can grow with more data
- Can insert items in the middle of the list (e.g. can store items in order which arrive out of order)
Hash Tables
cd examples/example1 make ./simple-hash.exe
- Content addressable storage.
- Must manage potential collisions.
Trees
Searchtrees
Quadtrees
http://en.wikipedia.org/wiki/Quadtree
A quadtree could be used to store:
- A sparse matrix (Can think of an image this way)
- Variable resolution data (parent's value is the average of its children's values)
The C++ Standard Template Library
Pretty much rocks. And saves you the hassle of writing all these data structures yourself.