Please enable JavaScript.
Coggle requires JavaScript to display documents.
Alevel Unit 2. Data Structures - Coggle Diagram
Alevel Unit 2. Data Structures
Queues
Priority Queues
Add an item (enqueue)
Item will be added depending on priority
Equal priority items will be stored according to when they were enqueued
Can join ahead if priority greater
[
e.g. Highest Priority = Red. Med = Yellow. Lowest = Green
]
array data type
linked list might be more efficent
Remove an item (dequeue)
examples
printing documents with different priorities
def = a variation of the FIFO structure where some data may leave out of sequence where it has higher priority then other data items
Implementation
method 1 = standard queue
Items added usual way at the end of the queue
To remove, it requires a priority check to work out what goes next.
Circular Queues
Join at front
continuous adding on. Doesn't finish
enqueue
Modular athematic
then points back around to the front of the queue
dequeue
Test for full queue
when full, just continue around
test for empty queue
fixed size ring
ferris wheel
Pointers move. Not the data
FIFO
Uses
Buffering
Front and rear diagram
Linear Queues
Example Queue
First in, first out
Data removed from the front.
Data added to the rear
Code Example
Add an item (enqueue)
Rear point moves
FIFO
Front and rear diagram
Implementation
when implemented we need to know
name of the array
max size of the queue
whether the queue is full or empty
where the front of the queue is
where the rear of the queue is
typically 1D array
element 0 = front of queue
written left to right
Queue Abstract Data Type
Test for a full queue
Remove an item (dequeue)
Front Pointer moves up
Doesn't delete data. Just moves pointer
Test for an empty queue
Point front and rear pointer pointing at the same place
Add an item (enqueue)
Item will be added depending on priority
Equal priority items will be stored according to when they were enqueued
Underlying data structure is a cycle
Rear point moves
Uses pointers
Abstract data type
Can be implemented as static or dynamic.
Need to be created by the programmer using existing data types.
e.g. stack might be built from an array
Def = A data structure where the first item added is the first item removed.
FIFO
First in, first out
where data leaves in the order it arrives
first item of the data entered is the first item to leave
uses as a buffer
Where a keyboard is sending data to the CPU. Might need to store before it can be implemented
Sending a document to a printer.
stored in stack until printer can deal with it.
Typically made up of multiple items of the same type
Stacks
Stack Abstract Data Type
Add an element (push)
Remove an element (pop)
Take a look at the top (peek)
Test for an empty stack
How stacks work
LIFO structure
Last in, First Out
exits from the bottom
Data not actually removed. But a pointer is used to keep track of the top of the stack
Popping
Pointer moved down
If you attempt a 'pop' on an empty stack = stack underflow error
enters from the top
Pushing
Pointer pushed up
If you try to add more items than spaces = stack overflow error
Worked example
e.g. pile of dishes to wash up. You start washing from the top
Pointer: a data item that identifies a particular element in a data structure - normally the front or the read
Implementing a stack
Standard stack
Needs to check is the stack is full to prevent overflow errors
Needs to check if stack is empty to prevent underflow errors
Code Stack Example
Stack Frame
used to store information about running a program
"call stack"
def = a special type of stack used to store information about active subroutines and functions within a program
Also used to handle Interrupts and exceptions programs
Interrupts def = a signal sent by a device or program to the processor requesting attention
e.g. printer out of paper
e.g. power failure
def = a collection of data about a subroutine call
Diagram
Uses in nesting and recursion
Nesting def: the process of putting one statement inside another statement
recursion
the process of a subroutine calling itself
a data structre where the last item added is the first item removed
Abstract data type
Can be implemented as static or dynamic.
Need to be created by the programmer using existing data types.
e.g. stack might be built from an array
Uses
Reverse contents of the list
Graphs
Graph
Example
undirected example.
Data can go both ways
example of a cycle
Can start and finish at same node
All nodes directly or indirectly connected
Uses
Map out
network
Map out character relationships in a
book
Work out out the fastest way to destination
Directed Graph Example
Formal Definition
A set of vertices, V (Or Nodes)
an object in a graph - also known as a node (vertices is the plural)
A set of edges, E, where E is a…
(arcs)
subset of all the pairs (u, v) for u and v in V (undirected, unweighted)
subset of all the pairs [u, v] for u and v in V where the order of u and v is important (directed)
triple (u, v, w) where u and v are vertices in V and w is their associated weight (weighted)
Can be weighted
value
Weighted graph = a graph that has a data value labelled on the edge,
Directed
Arrow
Set
Allows not duplicates
Tree
Is a connected graph
Examples
Has no cycles
Uses
Exploring a graph
Spanning
Tree
Rooted Trees
General Features
Usually Top Down
Multiple rooted Trees = a forest
Terminology
(hence must be an acyclic, connected graph with one node designated as the root node)
Types of Rooted trees
Binary Tree
Each parent node has at most two child nodes
Worked in levels
Each level = double the amount of elements that can be stored
Balanced = every level is full
Unbalanced
levels have spaces left
Example
Could be used in search algorithm
Recursively asks "Is this greater or less than?"
increased time effeiceny
calculated on worst case scenario number of statements
Coding
Not in specification But handy to know
Create Class
Recursive function
Origins of graph theory
Figuring out how to get across bridges and now go across them once
Used abstraction
proved that you couldn't do each bridge eaxctly once
Arity = Amount of edges
Diagram
Matrix
Adjacency Matrix implementation
2D Array used to represent
Direct access to edges (using node values as indexes to a two-dimensional array)
Easy to implement weighted and directed graphs
Easy to implement weighted and directed graphs
1 = connection
0 = no connection
Example. Top = Undirectied. Bottom = diirection
Example Directed and weighted
Graph
infinity = no edge connecting them
No labels as using integer values in order.
Adjacency List Implementation
Natural implementation of directed graph
Use
if nodes connect in a line wouldn't use much space
Example
Linked list with pointers to next part of the list.
^ end of the list
An array of arrays
Benefits
Space efficient (uses only space necessary)
Indirect access to edges if more than one edge from that node
To use to show a weighted. Each list would need to be a tuple containing the link and the weight value
Connected and disconnected graphs
Example
Cycle Graph
exampls
def = a math structure that models the relationship between pairs of objects.
Graph theory = the underlying math principles behind the use of graphs
arc = a join or relationship between 2 nodes. (edge)
Hash Table
associate keys with values
multiple keys can map to the same value
unlike a dictionary, more than one key can have the same value
Naive Hashing Function
1)Add up the Unicode values of all the characters in the title
2) Modulo the number of shelves in the library
Code example
diagram example
Uses
Large data sets
Buckets
Data
If multiple entries
Linked lists
Reduces down the amount of entries to search
e.g. library search - pointing to a shelf. Saves searching the whole library
increases efficency
Dictionary
Examples
Example of mapping
Another Example
Example using a line of tezt. Absolute frequency of words
Could be linked with huffman coding
Markov Chain
Build a chain based on probability of the word appearing
Can build text that makes the language logic
Markov string chain by prob
peter -> piper -> picked -> a -> peck -> of ->pickled -> peppers -> how -> many -> pickled -> peppers -> a -> peck -> of -> pickled -> peppers
uses
plagerism
working out who an unknown author might be
Keys
keys usually mapped to something more complex
keys have to be unique
keys only matched to 1 value
Definition
A data structure consisting of key-value pairs
Every key is unique
Every key maps to a value
Key-value pairs can be inserted, updated and deleted
Also called associative arrays and maps
Normally implemented as hash tables or binary trees
Vector
Free Vecotors
Example
Diagram
Example Arrows
Quantities
Direction
Size/magnitude
Uses
Games programming
flight sim
Spatial programming
Used when need movement and motion
Can describe position, movement, acceleration, forces and so on
Representing Vectors
A list of numbers, e.g. [4.3, 1.21, 2.0]
Every number here is a real number, hence this is a 3-vector over ℝ^3
A dictionary mapping integers to values, e.g. {0: 4.3, 1: 1.21, 2: 2.0}
A function where, for example, f(0) = 4.3, f(1) = 1.21 and f(2) = 2.0
Dictionary/Function Representation
for a function
The domain is the set of keys
The co-domain is the set of values mapped to from the keys
The co-domain could be the set of reals, ℝ
The function maps S to ℝ, or 𝑓:𝑆⟼ℝ
The domain, S, could be {0, 1, 2} i.e. as many integer values as the vector requires
List Representation
The placement of the value in the list is indicative of its ‘dimension’,
e.g.
[4.3, 1.21, 2.0] could represent the x, y and z axes
Vector Addition
Add the x and y coordinates pairwise
e.g. graph
A = [4, 3]
B = [-2, 3]
C = [(4-2), (3+3)] = [2, 6]
e.g. No Graph
A = [4, 1, 6, 5]
B = [5, 1, -2, 4]
A + B = [(4+5), (1+1), (6-2), (5,4)] = [9, 2, 4, 9]
Assumes both vectors have the same dimensionality
assumes same number of dimensions
e.g. 2 D adds to 2D etc
Scalar Vector Multiplication
Multiplying a vector by a scalar achieves ‘scaling’, seen on a 2-d vector as reducing or increasing the length of the arrow or the magnitude
Diagram
Multiply every value in the vector by the multiplicand
e.g.
A = [4, 6, 2]
B = 2
A = [2
4, 2
6, 2
2] = [8, 12, 4]
Localised Vectors
Example
Convex Combination
Example with
Diagram
u = [5, 3]
v = [2, 6]
w = 0.2[5, 3] + 0.8[2, 6] = [1, 0.6] + [1.6, 4.8] = [2.6, 5.4] is convex
x = 0.4[5, 3] + 0.8[2, 6] = [2, 1.2] + [1.6, 4.8] = [3.6, 6.0] is not convex
Dot Product
Gives a single number by summing the pairwise products, e.g.
𝑢 = [4, 2, 6]
𝑣 = [1, 7, 2]
𝑢∙𝑣=4×1+2×7+6×2=30
Can be used to find the angle between two vectors
Data Structures intro
What is a Data Structure?
A collection of data
An implementation of one or more abstract data types
A way of organising data
"Any method used to store data in an organised an accessible format.
Different data structure = Different applications
text file = database
Stack = exceptions
Why use data structures
More expressive power to the programmer (assembly languages generally do not support data structures explicitly)
E.g some data makes more sense in an array instead of Sep variable
Different data structures can be used in different situations to handle data appropriately
Data structures (or pointers to them) can be passed as arguments to functions
E.g sort
Name\structure\pointer passed
Types of Data Structures
Basic
Record
Example of record
Bespoke data structure
Contains fields
File
Binary file
Examples of files
All executables are binary files
PNG
Binary Basics
All data is stored in binary and is machine-readable but not human readable
File stored as ones and zeros
8 bits = 1 byte
Covered in more detail in later unit
Possible Actions
Write data to text File from a program
Read data into program from a text file
Students need to be able to read and write to files in all specifications
Non-binary file
/Text
Human readable
Common text files
Use = Data transfer
CSV
Comma separated variables
1 more item...
Plain Text
May use other delimitators
2 more items...
Structure
Header
explains content and structure
End of File marker
each line = record
Data (normally) stored as text
Line endings often delimited by special characters
Possible Actions
Write data to text File from a program
Read data into program from a text file
Students need to be able to read and write to files in all specifications
IO
Most programming languages allow you to open a stream to an external file
These streams are wrapped in objects to enable reading and writing
Highly language-specific
buffering
flushing
some need closing files to prevent unrequired streaming
Look at the specific language that you're teaching
Python
file = collection of related data
Array
1D array
Each value indexed
Usually I in most modern languages
Sequence of values :
Linear data
Homogeneous data (type)
Java has to be homogeneous
Contiguous memory.
Physically next to each other
Diagram example
common for int to be 32 bits
(Base address+offset)* width
Need to know how to figure out address of memory
Can iterate using a for loop
Length array -1
For Loop Example
Work like a list
Static array
Multi Dimensional array
Grid for game
How the Grid references work
3D Cube array
How to read a 3D grid ref
Data structures 4D+
Difficult to build a mental model of
Difficult to work with
Best avoided for "day to day" programming
Essential for some forms of modelling
e.g.
storing mock exam results of students
Array = a set of related data items stored under a single identifier. Can work on one or more dimensions
Each item on in the table = element
Abstract data types
Non-programming language specific
The data model: the operations and methods of data storage and retrieval (i.e. the semantics)
Data structures are implementations of ADTs
in a particular Programming Language
Data combined together
Def = conceptual model of how data is stored and the operations that can be performed upon them.
Static V Dynamic
Static:
Examples
Arrays often considered static
Records
Advantages of static:
Space efficient if size is known prior to execution
Implementation easier than dynamic structures
Faster access to the data
Fixed memory location
Contiguous memory addresses.
Fixed structure size. More predictable to work with
Relationship between different elements of data does not change
Disadvantages of static:
Possibly space inefficient
If you declare way more memory than you end up using
Number of elements is fixed
What is a static data structure?
number of elements fixed and defined at compile time
Set amount of memory allocated to the data structure
Memory location is fixed for each element
a method of storing data where the amount of data store (and memory used to store it) is fixed.
Dynamic:
Examples
lists often considered dynamic.
Stacks
Queues
Binary Trees
What is a Dynamic Data structure?
number of elements can vary during execution
Changeable
Can use more or less memory that needed through the use of a heap.
Can take off and add on to the unused data for the program
Heap = a pool of unused memory that can be allocated to a dynamic data structure
Advantages
Memory efficient
amount varies as needed
More flexible use of resources
Easier to add and remove
Disadvanages
slower access to elements
location allocated at run time
fragmented memory addresses
Needs to be a mechanism for knowing the size of current structure.
relationship between different elements of data will change as program is run.
a method of storing data where the amount of data stored (and memory used to store it) will vary as the program is being run.
Whether a structure is dynamic or static depends on the programming language being used
Queues and stacks can be either