05-06-2012, 03:26 PM
Introduction to data structures
03-DataStructures.ppt (Size: 72.5 KB / Downloads: 1)
What is a data structure?
A primitive data type holds a single piece of data
e.g. in Java: int, long, char, boolean etc.
Legal operations on integers: + - * / ...
A data structure structures data!
Usually more than one piece of data
Should provide legal operations on the data
The data might be joined together (e.g. in an array): a collection
An Abstract Data Type (ADT) is a data type together with the operations, whose properties are specified independently of any particular implementation.
ADTs use the following principles
Encapsulation: Providing data and operations on the data
Abstraction: hiding the details.
e.g. A class exhibits what it does through its methods; however, the details of how the methods work is hidden from the user
Modularity: Splitting a program into pieces.
An object-oriented program is a set of classes (data structures) which work together.
There is usually more than one way to split up a program
Principles of good design: High cohesion, low coupling
Modules (i.e. classes) should be as independent as possible
Cohesion: The extent to which methods in a class are related
Coupling: The extent to which a class uses other classes
Strive for high cohesion and low coupling
The ADTs we will examine have high cohesion and low coupling
Basic data structures: data collections
Linear structures
Array: Fixed-size
Linked-list: Variable-size
Stack: Add to top and remove from top
Queue: Add to back and remove from front
Priority queue: Add anywhere, remove the highest priority
Hash tables: Unordered lists which use a ‘hash function’ to insert and search
Tree: A branching structure with no loops
Graph: A more general branching structure, with less stringent connection conditions than for a tree
Kinds of operations
Builders
Change the contents of the data structure
Viewers
Retrieve the contents of the data structure
Queries
Return information about the data structure
Iterators
Return each element of the data structure, in some order
