Data Structures – Basic Concepts
Overview
• Programming Paradigms
• Values, Sets, and Arrays
• Indexer, Iterators, and Pattern Structures
References
• Bruno R. Preiss: Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons, Inc. (1999)
• Richard F. Gilberg and Behrouz A. Forouzan: Data Structures – A Pseudocode Approach with C. 2nd Edition. Thomson (2005)
• Russ Miller and Laurence Boxer: Algorithms Sequential & Parallel. 2nd Edition. Charles River Media Inc. (2005)
• Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo: C++ Primer. 4th Edition. Addison-Wesley (2006)
115
© Dr Markus Lumpe, 2021
Programming Paradigms
• Imperative style:
program = algorithms + data • Functional style:
program = function ⦁ function • Logic programming style:
program = facts + rules • Object-oriented style:
program = objects + messages • Other styles and paradigms:
blackboard, events, pipes and filters, constraints, lists, …
116
© Dr Markus Lumpe, 2021
Object-Oriented Software Development
• Object-oriented programming is about
Object-oriented software development
Using an object-oriented programming language
• Object-oriented software development is
An evolutionary step refining earlier techniques A revolutionary idea perfecting earlier methods
• •
• •
117
© Dr Markus Lumpe, 2021
Object-Oriented Design
Concrete Entities
Abstract Types
Classes 118
APPLICATION DOMAIN
Domain Analysis
Objects
SOLUTION DOMAIN
© Dr Markus Lumpe, 2021
Prototypes
Concrete vs. Abstract
Universe of Shapes
Rectangle
draw()
Triangle
draw()
Shape
draw()
Circle
draw()
Polygon
draw()
119
© Dr Markus Lumpe, 2021
Why is object-oriented software development popular?
• The object-oriented development approach
Naturally captures real life
Scales well from trivial to complex tasks
Focuses on responsibilities, reuse, and composition
• • •
120
© Dr Markus Lumpe, 2021
Values
• In computer science we classify as a value everything that may be evaluated, stored, incorporated in a data structure, passed as an argument to a procedure or function, returned as a function result, and so on.
• In computer science, as in mathematics, an “expression” is used (solely) to denote a value.
• Which kinds of values are supported by a specific programming environment depends heavily on the underlying paradigm and its application domain.
• Most programming environments provide support for some basic sets of values like truth values, integers, real number, records, lists, etc.
121
© Dr Markus Lumpe, 2021
Constants
• Constants are named abstractions of values.
• Constants are used to assign an user-defined meaning to a value.
• Examples:
• EOF = -1
• TRUE = 1
• FALSE = 0
• PI = 3.1415927
• MESSAGE = ”Welcome to DSP”
• Constants do not have an address, that is, they do not have a location.
• At compile time, applications of constants are substituted by their corresponding definition.
122
© Dr Markus Lumpe, 2021
Primitive Values
• Primitive values are values whose representation cannot be further decomposed. We find that some of these values are implementation and platform dependent.
• Examples:
• Truth values,
• Integers,
• Characters,
• Strings,
• Enumerands,
• Real numbers.
-1
123
© Dr Markus Lumpe, 2021
“Hello World!”
3.14159
Red
false
Composite Values
• Composite values are built up using primitive values and composite values. The layout of composite values is in general implementation dependent.
• Examples: • Records
• Arrays
• Enumerations • Sets
• Lists
• Tuples
• Files
124
© Dr Markus Lumpe, 2021
Pointers
• Pointers are references to values, i.e., they denote locations of a values.
• Pointers are used to store the address of a value (variable or function) – pointer to a value, and pointers are also used to store the address of another pointer – pointer to pointer.
• In general, it not necessary to define pointers with a greater reference level than pointer to pointer.
• In modern programming environments, we find pointers to variables, pointers to pointer, function pointers, and object pointers, but not all programming languages provide means to use pointers directly (e.g., Java).
125
© Dr Markus Lumpe, 2021
Memory, Values, and Pointers
Memory:
+1 +2 +3
+4 +5 +6
+7 +8 +9
int* pivar = &ivar;
int ivar = 3;
float* pfvar = &fvar float fvar = 3.14;
Values:
pivar == +3 pivar == 3
pfvar == +8 fvar == 3.14
Deference/Address :
*pivar == 3 &pivar == +3
*pfvar == 3.14 &fvar == +8
126
© Dr Markus Lumpe, 2021
Sets
• A set is a collection of elements (or values), possibly empty.
• All elements satisfy a possibly complex characterizing property. Formally, we write:
{ x | P(x) = True }
to define a set, where all elements satisfy the property P.
• The basic axiom of set theory is that there exists an empty set, ∅, with no elements. Formally,
∀x, x ∉ ∅
In words, “for every x, x is not an element of ∅.”
127
© Dr Markus Lumpe, 2021
Sets are collections of values.
128
© Dr Markus Lumpe, 2021
Inductive Reasoning
• To define a set and to capture what qualifies values to be members of the set, we can use inductive reasoning and formally verify properties about members of the set.
• Algebraically, we can define a set using induction on the structure of expressions and induction on the length or structure of expressions as a means to verify (prove) properties of the set and the elements thereof.
• Note: We can construct infinitely many values from a given finite recipe – inductive specification.
129
© Dr Markus Lumpe, 2021
Inductive Specification
• Sometimes it is difficult to define a set explicitly, in particular if the elements of the set have a complex structure.
• However, it may be easy to define the set in terms of itself. This process is called inductive specification or recursion.
• Example:
Let the set S be the smallest set of natural numbers satisfying the following two properties:
• 0 ∈ S, and
• Whenever x ∈ S, then x + 3 ∈ S.
The first property is called base clause and the second property is called inductive/recursive clause. An inductive specification may have multiple base and inductive clauses.
130
© Dr Markus Lumpe, 2021
The “Smallest Set”
• If we use inductive specification, we always define the smallest set that satisfies all given properties. That is, inductive specification is free of redundancy.
• It is easy to see that there can be only one such set:
If S1 and S2 both satisfy all given properties, and both are the smallest, then we have S1 ⊆ S2 (since S1 is the smallest), and S2 ⊆ S1 (since S2 is the smallest), hence S1 = S2.
131
© Dr Markus Lumpe, 2021
The Set of Strings
S = ∊ | aS, where
∊ is the empty string and
a ∈ Σ, with Σ being the alphabet over S.
• •
Examples:
∊, ∊a, ∊aaaaaaaaa where a is some character
•
•
in the alphabet Σ (a ∈ Σ) 132
© Dr Markus Lumpe, 2021
Regular Sets of Strings
• Operations for building sets of strings: • Alternation
S1 | S2 = { s | s ∈ S1 ∨ s ∈ S2 } • Concatenation
S1 · S2 = { s1s2 | s1 ∈ S1, s2 ∈ S2 } • Iteration
S* = {∊} | S | S · S | S · S · S | … = S0 | S1 | S3 | S3 | …
• A set of strings over Σ is said to be regular if it can be built from the empty set ∅ and the singleton set {a} (for each a ∈ Σ), using just the operations of alternation, concatenation, and iteration.
133
© Dr Markus Lumpe, 2021
Indexed Sets
• Sets are unordered collections of data elements.
• In order to obtain an ordering relation over the elements of a given set, we can assign each element in that set a unique element of another ordered set I:
SI = { ai | a ∈ S, i ∈ I } SI is called the “indexed set” of S.
134
© Dr Markus Lumpe, 2021
Some Indexed Sets
• Let A = { a, b, c, d } and I = N, then AI = { a1, b2, c3, d4 }
• Let A = { a, b, c, d } and I = (S×S, < ), then AI = { a“1”, b“2”, c“3”, d“4” }
135
© Dr Markus Lumpe, 2021
Arrays are indexed sets.
136
© Dr Markus Lumpe, 2021
Pairs and Maps
• Let A and B be sets. The Cartesian product of A and B, denoted by A×B, is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B:
A × B = { (a,b) | a ∈ A and b ∈ B }
• A map is an associative container, whose elements are key-value pairs. The key serves as an index into the map, and the value represents the data being stored and retrieved.
137
© Dr Markus Lumpe, 2021
Associative Array (Dictionaries)
• An associate array is a map in which elements are indexed by a key ra{ther than by their position.
v, if i ↦ v in a ⊥, otherwise
a = { (“u” ↦ 345), (“v” ↦ 2), (“w” ↦ 39), (“x” ↦ 5) } a[“w”] = 39
a[“z”] = ⊥
a[i] =
• Example:
138
© Dr Markus Lumpe, 2021