Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data types, data structures and algorithms - Coggle Diagram
Data types, data structures and algorithms
Data types
Data types
Integer:
- A whole number
- Zero is an integer
- Negative numbers are integers
- Can't have a fractional part
- Useful for counting things
Real:
- Positive or negative numbers
- Can, but do not necessarily, have a fractional part
- Useful for measuring things
- All integers are real numbers
Character:
- A single symbol used by a computer
- The letters A to Z
- The numbers 0 to 9
- Symbols like %, £, and ¬
String:
- A collection of characters
- Can be used to store a single character
- Can also be used to store many characters in succession
- Useful for storing text
- Don't cut off leading 0s like numeric types
Boolean:
- Restricted to True or False
- Useful for recording data that can only take two values
-
Binary addition
When adding binary, there are four simple rules to remember:
- 0+0=0
- 0+1=1
- 1+1=10
- 1+1+1=11
-
-
Hexadecimal
- Hexadecimal is base 16
- The characters are 0-9 as usual
- The characters A-F represent 10-15
- Place values start with 1 (16^0) and go up in powers of 16
- 0=0
- 1=1
- 2=2
- 3=3
- 4=4
- 5=5
- 6=6
- 7=7
- 8=8
- 9=9
- 10=A
- 11=B
- 12=C
- 13=D
- 14=E
- 15=F
Converting from hexadecimal to binary:
- First convert each hexadecimal digit to a decimal number
- Convert these to as binary nibble
- Combine the nibbles to form a single binary number
Converting from hexadecimal to decimal:
- First convert to binary and then convert from binary to decimal
- Alternatively, use the place values of hexadecimal to convert directly to decimal
-
Normalisation
- Maximises precision in a given number of bits
- To normalise a binary number:
- Adjust the mantissa so that it starts 01 for a positive number of 10 for a negative number
-
-
-
Data structures
Arrays, records, lists and tuples
Arrays:
- An array is an ordered, finite set of elements of a single type
- A 1D (one-dimensional) array is a linear array
- A 2D (two-dimensional) array can be visualised as a table/spreadsheet
- When searching an array, first go down the rows and then across the columns
- A 3D (three-dimensional) array can be visualised as a multi-page spreadsheet
- An element in a 3DS array using: threeDimensionalArray[z, y, x]
z = array number, y = row number, x = column number
Records:
- More commonly referred to as a row in a file
- A record is made up of fields and is widely used in databases
Lists:
- Consists of a number of items, where items can occur more than once
- Data can be stored in non-contiguous locations and be of more than one data type
Tuples:
- An ordered set of values of any data type
- Cannot be changed: elements cannot be added, edited or removed once initialised
- Initialised with regular brackets rather than square brackets
Linked lists, graphs, stacks, queues and trees
Linked lists:
- Dynamic data structure used to hold an ordered sequence
- Items do not have to be in contiguous data locations
- Each item is called a node, and contains a data field and a link or pointer field
- Data field: contains the actual data associated with the list
- Pointer: contains the address of the next item in the list
Graphs:
- Set of vertices/nodes connected by edges/arcs
- Directed graph: edges can only be traversed in one direction
- Undirected graph: edges can be traversed in both directions
- Weighted graph: each arc has a cost attached to it
- Implemented using an adjacency matrix or an adjacency ist
Advantages of using adjacency matrix:
- Convenient to work with
- Easy to add nodes
Advantages of using adjacency list:
- Space efficient for large sparse networks
Stacks:
- Last in first out (LIFO) data structure:
- Items can only be added to/removed from the top of the stack
- Used to reverse actions, e.g. back buttons and undo buttons use stacks
- Can be implemented as a static or dynamic structure
Queues:
- First in first out (FIFO) data structure:
- Items are added to the end and are removed from the front of the queue
- Used in printers, keyboards and simulators
- Linear queue: items are added into the next available space, starting at the front
- Items are removed from the front of the queue
- Uses two pointers: pointing to the front and back of the queue
- Use space inefficiently, as positions from which data has been removed cannot be reused
- Circular queues have a rear pointer that can look back to the front of the queue and utilise empty space at the front
Trees:
- A connected graph, with a root and child nodes
- Node: item in a tree
- Edge: connects two nodes together and is also called a branch/arc
- Root: node with no incoming nodes
- Child: node with incoming edges
- Parent: node with outgoing edges
- Subtree: section of a tree consisting of a parent and its children
- Leaf: node with no children
- A binary tree is a type of tree where each node has a maximum of two children
- Store information in a way that is easy to search through
- Commonly represented by storing each node with a left pointer and a right pointer
Hash tables:
- An array coupled with a hash function
- Hash function takes in data (a key) to produce a unique output (the hash)
- Typically used to map the key to a unique index in a hash table
- Two keys producing the same hashed value is called a collision
- If this occurs, the item is typically placed in the next available location
- A good hashing algorithm should have a low rate of collisions
-
Boolean algebra
-
-
-
-
Logic circuits
D-type flip flops:
- Logic circuit which can store the value of one bit
- Two inputs, a control signal and a clock
- A clock is a regular pulse generated by the CPU which is used to coordinate the computers' components
- A clock pulse rises and falls as shown in the diagram
- Edges can be classified rising or falling
- The output of a D-type flip flop can only change at the rising edge, the start of a clock tick
- Logic circuit uses four NAND gates
- Updates the value of Q to the value of D whenever the clock (CLK) rises
- The value of Q is the stored value
Adders:
- A logic circuit which adds together the number of inputs which are True
- Outputs this number in binary
Half adder:
- Two inputs, A and B
- Two outputs, Sum and Carry
- Formed from two logic gates: AND and XOR
- When both A and B are False, both outputs are False
- When one of A or B is True, Sum (S) is True
- When both inputs are True, Carry (C) is True
Full adder:
- Similar to a half adder, but has an additional input
- Allows carry in to be represented
- Formed from two XOR gates, two AND gates and an OR gate
- Can be chained together to form a ripple adder with many inputs