Chapter 10 | Data Types & Structures

10.1 Data Types and Records

Data Types →

Integer: A whole number without a decimal point.

Examples: 3, 20, -100, etc.
In pseudocode: INTEGER or INT

Real: A whole number with a decimal point.

Examples: 3.14, -2.5, 0.1, etc.
In pseudocode: REAL

Char:A single letter, digit, or symbol.

Examples: 'a', '5', '$', etc.
In pseudocode: CHAR

String: A sequence of characters that represents text or any other data.

Example: ‘Hello’
In pseudocde: STRING or STR

Boolean: A data type that represents true or false values.

Example: True/False
In pseudocode: BOOLEAN or BOOL

Date: A data type that is used to represent dates in a computer system

Example: 23/04/2003
In pseudocode: DATE

Records →

A record is a data structure that contains multiple fields, each of which can hold
different data types, that are all stored under one identifier.
For example, a record in a database might represent a customer and contain fields
for the customer's name, address, phone number, and email address.
Records can be used to store and retrieve data efficiently, and they are an important part of many computer systems.

10.2 Arrays

Technical terms associated with arrays →

Index: Refers to the position of a particular element within the array.
Upper Bound: Refers to the highest index or the maximum number of elements that
an array can hold. It represents the limit beyond which no more elements can be
added to the array.
Lower Bound:

Declaring an array in pseudocode→

DECLARE <identifier> : ARRAY[<lowerbound>:<upperbound>] OF <datatype>

Bubble Sort →


swapflag = true
WHILE swapflag == true
    swapflag = false
    position = 0
    FOR position = 0 to length_of_list
        compare(current_item , next_item)
        IF (current_item > next_item)
            swap(current_item, next_item)
            swapflag = true
        ENDIF
        position = position + 1
    ENDFOR
ENDWHILE

Linear Search →

position = 0
INPUT SearchValue
Length = array.length - 1
WHILE position < length AND array[position] != SearchValue
    position = position + 1
ENDWHILE
IF position > length
    OUTPUT “Value not found”
ELSE 
    OUTPUT “Item found at position” + position 
ENDIF

10.3 Files

Why are files needed →

Files are necessary because they allow for the storage and organisation of information in a computer system.
Files are typically composed of data that can be manipulated by software applications, and they can be stored in various formats, such as text.
Files are essential for efficient computer operations as they provide a means for storing and retrieving data in a structured and organised manner.
Moreover, files enable sharing and exchanging data between different users and computer systems. They provide a standard way of representing information that can be recognized and processed by various software applications.

Pseudocode to Open a Text File →

WRITEFILE <file identifier>, <string></string>

A new file is created and any existing data in the file will be lost.

Pseudocode to Read From a Text File →

READFILE <file identifier>, <variable>

The variable should be of data type STRING. When the command is executed, the next line of text in the file is read and assigned to the variable.

Pseudocode to Append a Text File →

WRITEFILE <file identifier>, <string>

Allows data to be added to an already created file.

Pseudocode to Close File →

CLOSEFILE <file identifier>

Files MUST be closed when they are no longer needed.

Pseudocode to Test Whether the File Pointer is at the End of The File:

EOF (<file identifier>)

This function returns a Boolean value: TRUE if the file pointer is at the end of the file and FALSE otherwise.

10.4 Introduction to Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a collection of data and a set of associated operations:

Create a new instance of the data structure
Find an element in the data structure
Insert a new element into the data structure
Delete an element from the data structure
Access all elements stored in the data structure in a systematic manner

Stacks →

Key Features of a Stack →

Entries are inserted and removed only at the head
A stack has a stack pointer that always points to the node at the top.
First-In-Last-Out (FILO) structure - the last item to be pushed onto the stack must also be the first item to be popped off.
Push and pop operations: Push adds an element to the top of the stack. The pop operation removes the top element from the stack.
Top element: A stack allows access to the top element
Size limit: A stack has a size limit, which determines the maximum number of elements that can be stored in the stack.
Overflow and underflow: Overflow is any attempt to push an item onto a full stack. Underflow is any attempt to pop an item off of an empty stack

Key Features of a Stack →

Keeping track of user inputs for undo operations
Backtracking algorithms

Methods Used for Stacks →

push(item) – adds item to the top of the stack
pop() – removes and returns the item on the top of the stack
isFull() – checks if the stack is full
isEmpty() – checks if the stack is empty
peek() – return the top item without removing it
size() – return the number of items on the stack
append(item) – add item to the top of the stack
len(stack) – find the length (height) of the stack

Queues →

Key Features of a Queue →

A queue is a list where entries are removed only at the head and new entries are removed only at the tail.
Each queue element contains one data item
A pointer to the front of the queue
A pointer to the back of the queue
Data is added at the back and removed from the front, works on a First-In-First-Out basis
May be circular → the pointer can move to the top of the queue once the end of the queue is reached

Uses of Queues →

Web server requests
Buffering

Methods Used for Queues →

enQueue(item) – add an item to the rear of the queue
deQueue – remove and return an item from the front
isEmpty – indicates if the queue is empty
isFull – indicates if the queue is full

Implementing a Queue Using an Array →

Declare a (1D) array of size of the queue
…of relevant data type
Declare integer variable for FrontOfQueuePointe
Declare integer variable for EndOfQueuePointer
nitialise FrontOfQueuePointer and EndOfQueuePointer to represent an empty queue
Declare integer variable for NumberInQueue
Declare integer variable for SizeOfQueue to count / limit the max number of items allowed
Initialise SizeOfQueue // Initialise NumberInQueue

Linked Lists →

Key Features of a Linked List →

Each node contains data and a pointer to the next node
A pointer to the start of the list - the start pointer
Last node in the list has a null pointer
Data may be added or removed by manipulating pointers
Nodes are traversed in a specific sequence
Unused nodes are stored on a free list

Inserting to an Ordered List →

PROCEDURE InsertInOrder(MyList, data)
    DECLARE NewNode : Node
    NewNode.data = data
    CurrentNode = MyList.head

    IF CurrentNode == NULL THEN
        MyList.head = NewNode
    ELSE 
        IF NewNode.data  current.data THEN
            NewNode.pointer = MyList.head
            MyList.head = NewNode
        ELSE
            WHILE (current.pointer != NULL AND current.next.data < NewNode.data)
                Current = current.next
            ENDWHILE 
            NewNode.next = current.next
            Current.next = NewNode
        ENDIF
    ENDIF
ENDPROCEDURE

Traversing a Linked List→

PROCEDURE traverse (MyList)
    CurrentNode = MyList.head
    WHILE CurrentNode != NULL
        OUTPUT(CurrentNode.data)
        CurrentNode = CurrentNode.next
    ENDWHILE
ENDPROCEDURE

Deleteing From a Linked List→

PROCEDURE delete(MyList, data)
    current = MyList.head

    IF current.data == data THEN
        MyList.head = current.head
    ELSE
        WHILE current.next.data != data THEN
            Current = current.next
        ENDWHILE
        current.next = current.next.next
    ENDIF
ENDPROCEDURE

Implementing a Linked List using an array →

A linked list can be implemented using an array by using two arrays: one for the values of the nodes and one for the pointers to the next node in the list.
Each node in the list is represented by an index in the arrays, with the value array storing the value of the node and the pointer array storing the index of the next node in the list.
The first node in the list is represented by the index 0, and subsequent nodes are represented by consecutive indices.
This implementation has the advantage of being able to dynamically resize the list by allocating more space for the arrays when needed.
However, it can also be less memory-efficient than using a traditional linked list, since each node requires both a value and a pointer to the next node in the list, which can use up more memory than just a value and a single pointer as in a traditional linked list.