1.4 Data types, structures and algorithms

Importance of using the correct data type

Allows the right operations to be performed on it

Character

Single symbol

String

Collection of characters

Real/floating point

Number which can have a decimal part

Binary

2 digit number system

Fractions in binary

Represented by 1/2^x where x increases towards the right in the binary table

Most significant bit/leading bit

First binary digit

Sign magnitude

Uses an extra binary digit to add a +ve or -ve sign in front of the binary number

Sign magnitude - negative

1 as the leading bit (at the start)

Sign magnitude - positive

0 as the leading bit (at the start)

Two’s complement

Makes the most significant bit negative in the binary table

Hexadecimal

16 digit number system, base 16, uses 0-9 and A-F

Binary - hexadecimal

4 bits in binary is equivalent to one place of hex

Floating point binary- sections

Mantissa and exponent

Mantissa

Number

Exponent

Power, number of places the floating point is moved

To practise: subtraction, floating point arithmetic

Examples on physics and maths tutor

Floating point binary - accuracy

Larger values are less accurate

Floating point binary - normalisation

Starts 01 for a positive number or 10 for a negative number

Normalisation - advantage

Makes numbers as precise as possible in the given number of bits

Logical shift

Shift performed on binary numbers, moves all digits a set number of places to the right/left

Effect of logical shift

Division or multiplication by 2^shift number

Carry bit

Can hold 1 binary digit which is lost due to a shift

Mask

Applied to binary by combining with a logic gate

XOR

Exclusive OR, both on or both off=0

Bitewise manipulation

Logical shifts and mask

Character set

Collection of characters and corresponding codes which can be used by computers to represent text

ASCII

Uses 7/8 bits and can represent 128 characters

ASCII - advantage

Uses fewer bits so each character takes less memory to store

ASCII - disadvantage

Fewer characters can be represented

Unicode

Uses a varying number of bits so over a million characters can be represented

Unicode - advantage

Many more characters can be represented

Unicode - disadvantage

Uses more bits so each character requires more memory to be stored

Data structure

Specialised format for processing, storing and retrieving data, collection of different kinds of data

Static data structures

Fixed size during run-time

Dynamic data structures

Can change size during run-time

Array

Static, ordered, finite set of elements of a single type, 0-indexed, values stored contiguously

Data type

The form of a variable to which a value can be assigned

2D arrays

Like a table, use [y,x]

3D arrays

Like a spreadsheet with many sheets, use [z,y,x] with z as the array number

Record

Like a row in a file, made up of fields - each field can have a different data type

List

Dynamic data structure, values stored non-contiguously (do not have to be stored next to each other in memory)

List - data types

Can contain elements of more than one data type

Tuples

Static ordered set of values, immutable, initialised using normal brackets

Immutable definition

Elements cannot be added or removed once the structure has been created

Contiguous

Data stored consecutively together in memory

Linked-list

Dynamic data structure used to hold an ordered sequence of items (nodes)

Linked-list - advantage

Items do not have to be stored contiguously, dynamic so it can change size

Linked-list - disadvantage

No direct access to a single piece of data so slow to search, pointers must also be stored

Linked-list - items

Nodes, contains a data field and a link/pointer field

Linked-list - pointer

Holds the address of the next item

Linked-list - data stored

Index, data, pointer as well as start pointer and next available location for data

Linked-list - editing

Edit pointers to point to a new item or miss out an existing item

Linked-list - editing: advantage

Easy to edit

Linked-list - editing: disadvantage

Node is not removed but simply ignored, which wastes memory

Graph

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

Weight (numerical value) attached to each edge

Graph - representation

Computers use an adjacency matrix or an adjacency list

Adjacency matrix - advantage

Quicker access times than adjacency list

Adjacency list - advantage

More space efficient for large, sparse networks

Stack

LIFO (last in first out) data structure, either static or dynamic

Stack - LIFO

Items can only be added to/removed from the top of the stack

Stack - use

To reverse an action e.g. go back a page in web browsers, undo buttons

Stack - static

Preferred when maximum size of the stack is known in advance, easier to implement and make more efficient use of memory

Stack - implementation

Uses a pointer that points to the top of the stack, where the next piece of data will be inserted

Stack - function

stackName.function(parameters)

Stack - check if empty

.isEmpty() - must be done before peeking or popping, returns Boolean value and works by checking the value of the top pointer

Stack - add a new value

.push(value)

Stack - return top value of stack

.peek()

Stack - remove and return top value of stack

.pop()

Stack - return size

.size()

Stack - check if full

.isFull() - returns Boolean value, works by comparing stack size to top pointer

Queue

FIFO (first in first out) data structure

Queue - FIFO

Items are added to the end of the queue and removed from the front of the queue

Queue - uses

Printers, keyboards, simulators

Linear queue

Data structure consisting of an array

Linear queue - items

Items added into the next available space and removed from the front of the queue

Linear queue - pointers

Two pointers, one pointing to each end of the queue, where items can be added/removed

Linear queue - advantage

Easy to implement

Linear queue - disadvantage

As the queue removes items, there are addresses that cannot be used again, making it ineffective

Queue - functions

queueName.function(parameters)

Queue - add item

.enQueue(item) - increments back pointer

Queue - remove item

.deQueue() - increments front pointer

Queue - checks if empty

.isEmpty() - works by comparing front and back pointer

Queue - checks if full

.isFull() - works by comparing back pointer and queue size

Circular queue - description

FIFO, operates similarly to a linear queue

Circular queue - pointer usage

Once back pointer is equal to maximum size of queue, it can loop back to the front and store values there if the space is empty

Circular queue - advantage

More space efficient than linear

Circular queue - disadvantage

Harder to implement than linear

Tree

Connected form of graph

Tree - root node

Top node, has no incoming edges

Tree - node

Item in tree

Tree - edge/branch/arc

Connects two nodes

Tree - child

Node with incoming edges

Tree - parent

Node with outgoing edges

Tree - subtree

Subsection of tree consisting of a parent and all the children of that parent

Tree - leaf

Node with no children

Binary tree

Type of tree where each node has a maximum of two children