Data types and structures
Data types:
Primitive data types – These data types are variables that can be defined by commands
build into the programming language.
Further data types – This is a data type that is created by the programmer
The record type:
Sometimes variables of different data types are a logical group, such as data about a person:
name, date of birth, height, number of siblings. Each of these have their own data type.
We can declare a record type to suit our purpose. The record type is known as a user-
defined type, because the programmer can decide which variables (fields) to include as a
record.
A record types is declared as:
Arrays:
An array is an ordered set of data items, usually of the same type, grouped together using a
single identifier.
Array index – Row or columns number of an individual array element
Upper bound – The highest number index of an array dimension
Lower bound – The smallest number index of an array dimension
One-dimensional array:
A 1D array is like a numbered list of items.
In pseudocode, a 1D array is written as:
DECLARE <arrayIdentifiers>: ARRAY [<lowerBound> : < upperBound>] OF <datatype>
Here is a pseudocode example:
DECLARE List1: ARRAY [0:5] OF STRING There are 6 elements in this list
Accessing 1D arrays – A specific element in an array is accessed using an index value. In
pseudocode this is written as:
<ArrayIdentifier>[x]
Linear search – Checking each element of an array in turn for a required value
Bubble sort – A sort method where adjacent pairs are compared and swapped
Two dimensional arrays:
A 2D array is like a table and you want to refer to an individual element of the table.
In pseudocode, a 2D array is written as:
DECLARE <arrayIdentifiers>: ARRAY [<LBound1> : < UBound1>, <LBound2> : < UBound2>]
OF <datatype>
Here is a pseudocode example:
DECLARE List1: ARRAY [0:5, 0:7] OF INTEGER
Accessing 2D arrays – A specific element in a table is accessed using an index pair. In
pseudocode this is written as:
<ArrayIdentifier>[x, y]
Text files:
To store data permanently files can be used. Data held in an array will be lost when the
program is stopped. You can save the data to a file and read it back in when your program
requires it.
A text file consists of a sequence of characters formatted into lines. Each line is terminated
by an end-of-line marker. The text file is terminated by an end-of-file marker.
Writing to a text file – Writing to a text file usually means creating a text file
Reading from a text file – An existing file can be read by a program
Appending to a text file – Sometimes we may wish to add data to an existing file rather than
create a new file. This can be done in Append mode it adds new data to the end of an
existing file
The end of file (EOF) marker – If we want to read a file from beginning to end, we can use a
conditional loop. Text files contain a special marker at the end of the file that we can test
for. Testing for this special end-of-file marker is a standard function in many programming
languages. Every time this function is called it will test for this marker. The function will
return TRUE if the end-of-file marker has been reached.
In pseudocode we call this function EOF(). We can use the construct REPEAT…UNTIL EOF().
If it possible that the file contains no data, it is better to use the construct WHILE NOT EOF().
Abstract Data Type (ADTs):
Abstract data type – A collection of data with 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:
Top of stack pointer – Always points to the top item in the stack
Base of attack pointer – Always points to the first slot in the stack
When an item is placed into the stack it goes to the first available slot. Any items bellow that
item cannot be accessed unit it is removed. When there are no items in the stack the Top of
stack pointer will have the value of -1.
To implement a stack using a 1D array, we write:
DECLARE Stack: ARRAY[0:7] OF CHAR
Queues:
Front of queue pointer – This will hold the spot where the items will leave the queue
End of queue pointer – This will point to the end of the queue
When an item joins the queue it must enter from behind the end of queue pointer and the
end of queue pointer will move to the new item at the end. When an item leaves the queue
all the items move one forward. When there are no items in the queue both pointers will
have the value of -1.
The last method have a lot of moving of data. A more efficient way to make use of the slots
is the concept of a ‘circular’ queue. When the front item leaves the queue instead of
everything we can just move the Front pointer one back and when an item joins the queue
we can move the end pointer one back.
Linked list:
Node – An element of a list
Pointer – A variable that stores the address of the node it points to
Null pointer – A pointer that does not point at anything
Start pointer – A variable that stores the address of the first element of a linked list
This is how you could use this in a 2D array:
