10.1 Data Types and Records

伪代码在线编程网站：[https://pseudocode.pro/](https://pseudocode.pro/)
# Data Types and Structures

# Data Type

A data type in programming defines the type or nature of data that can be stored, manipulated, or processed within a programming language, specifying the kind of values a variable can hold.

## Primitive data types

A primitive data type is a basic data type provided by a programming language that is directly supported by the underlying hardware, such as:

| Data Types | What it represents                       |
| ---------- | ---------------------------------------- |
| INTEGER    | Whole Number                             |
| REAL       | Number with a decimal point              |
| BOOLEAN    | Conditions that are either TRUE or FALSE |
| CHAR       | Single Character                         |

## Further data types

Further data types, often called composite or derived data types, are built upon primitive types or are custom-defined to create complex structures or collections of data, including:

| Data Types | What it represents                                           |
| ---------- | ------------------------------------------------------------ |
| STRING     | A sequence of characters                                     |
| DATE       | A date consisting of day, month and year, sometimes including a time in hours, minutes and seconds |

## Record Types

A record type in programming is a data structure that allows the storage of **multiple fields or pieces of information** under a single name or identifier. For example: data about a product could contain the following fields:

- Product Name: STRING
- Product Price: REAL
- Expiration Date: DATE
- A Dairy Product: BOOLEAN

The record type is known as a user-defined type, because the programmer can decide which variables to include as a record.

### Pseudocode

In pseudocode a record type is declared as:

```pseudocode
TYPE <TypeIdentifier>
	DECLARE <field identifier>: <data type>
	...
ENDTYPE
```

A record type for PRODUCT could look like this:

```pseudocode
TYPE Product
	DECLARE ProductName: STRING
	DECLARE ProductPrice: REAL
	DECLARE ExpirationDate: DATE
	DECLARE IsDairy: BOOLEAN
ENDTYPE
```

How to declare a variable of this record type:

```pseudocode
DECLARE <variable identifier>: <record type>
```

Declaring a new product - Milk

```pseudocode
DECLARE Milk: Product
```

We can assign value to a field of this Product record:

```pseudocode
Milk.ProductName <- "Dutch Lady"
Milk.ProductPrice <- 15.99
Milk.ExpirationDate <- 5/12/2024
Milk.isDairy <- TRUE
```

## Arrays

### 1-Dimensional (1D) Array

declared using a single index, can be represented as a list

![](/uploads/Theo/image033.png)

#### Declaring a 1D array:

```pseudocode
DECLARE <arrayidentifier>: ARRAY[<lowerBound>:<upperBound>] OF <dataType>
```

Eg:

```pseudocode
DECLARE StudentList: ARRAY[0:4] OF STRING
```

#### Accessing an element in the array using an index value:

```pseudocode
OUTPUT StudentList[1]
```

Will output:

```pseudocode
ERICSON
```

#### Assign a value to an element in the array:

```pseudocode
StudentList[1] <- "Ali"
```

The element with an index value of 1 becomes Ali.

![](/uploads/Theo/image_1712642178.png)

Example:

Declare an array called MultiplesOfTens that has 10 values. Then, populate the array with the first 10 multiples of 10.

```pseudocode
DECLARE MultiplesOfTens: ARRAY[0:9] OF INTEGER CurrentMultiple <- 10

FOR Index <- 0 TO 9
	MultiplesOfTens [Index] <- CurrentMultiple
	CurrentMultiple <- CurrentMultiple + 10
NEXT Index
```

![](/uploads/Theo/image-20240409105621307.png)

### 2-Dimensional (2D) Array

declared using two indices, can be represented as a table

![](/uploads/Theo/image_1712642240.png)

#### Declaring a 2D array

```pseudocode
DECLARE Board : ARRAY[1:6,1:7] OF CHAR
```

![](/uploads/Theo/image-20240409110830974.png)

#### Accessing an element in the 2D array using two index values:

```pseudocode
<arrayIdentifier>[x,y]
x is Row Number; y is Column number
```

#### Populating a 2D array with 0

```pseudocode
FOR Row <- 1 TO 6
	FOR Column <- 1 TO 7
			Board[Row, Column] <- 0
	NEXT Column
NEXT Row
```

![](/uploads/Theo/image_1712642388.png)

#### Outputting the values of a 2D array

```pseudocode
FOR Row <- 1 TO 6
	FOR Column <- 1 TO 7
			OUTPUT Board[Row, Column]
	NEXT Column
NEXT Row
```

## File

#### Why is text file needed?

Text files are employed in software development to store variables by writing their values into the file, enabling the program to access, modify, or retrieve these values during execution, allowing for persistent data storage across multiple runs of the software.

### Writing to a text file

```pseudocode
OPENFILE <filename> FOR WRITE
WRITEFILE <filename>, <stringValue>
CLOSEFILE <filename>
```

### Reading from a text file

```pseudocode
OPENFILE <filename> FOR READ
READFILE <filename>, <stringValue>
CLOSEFILE <filename>
```

### Appending to a text file

```pseudocode
OPENFILE <filename> FOR APPEND
WRITEFILE < filename>, <stringValue>
CLOSEFILE <filename>
```

### The end-of-file (EOF) marker

EOF (End-of-File) is a condition or marker used in programming to indicate the end of data in a file, helping programs identify when there is no more content to read from the file.

```pseudocode
OPENFILE "Test.txt" FOR READ
WHILE NOT EOF("Test.txt")
	READFILE "Test.txt", TextString
	OUTPUT TextString
ENDWHILE
CLOSEFILE "Test.txt"
```

## Bubble Sort

Bubble sort is a basic sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order, continuing until the entire list is sorted.

![](/uploads/Theo/image-20240409140046511.png)

Test if current element is greater than next element, if so then swap elements, eg:

![](/uploads/Theo/image_1712726687.png)

After one iteration, the biggest value is in the correct position at the end of the array.

![](/uploads/Theo/image_1712726701.png)

```pseudocode
FOR j<- 0 TO n
	IF NumberList[j] > NumberList[j+1] THEN
		Temp <- MyList[j]
		MyList[j] <- MyList[j+!]
		MyList[j+1] <- Temp
	ENDIF
NEXT j
```

Put an outer for Loop and to ensure that this operation is run many different times until the list is being sorted.

![](/uploads/Theo/image_1712726717.png)

```pseudocode
n <- MaxIndex - 1
FOR i <- 0 TO MaxIndex - 1
	FOR j<- 0 TO n
	IF NumberList[j] > NumberList[j+1] THEN
		Temp <- MyList[j]
		MyList[j] <- MyList[j+!]
		MyList[j+1] <- Temp
	ENDIF
	NEXT j
	n <- n - 1
NEXT i
```

the issue here is that there's a way that the algorithm could do an unnecessary operation. for example after third iteration, you can see that the list has already been sorted but then because of the way we write our code here, it's a for Loop meaning it runs for fixed number of time, it will still run even after the list has been sorted. so we can make the algorithm Faster by putting some condition in. so to tell our algorithm that hey if this condition is met, you can stop sorting it.

![](/uploads/Theo/image_1712726733.png)

Making it more efficient

```pseudocode
n <- MaxIndex - 1
REPEAT
	Swapped <- FALSE
	FOR j<- 0 TO n
		IF MyList[j] > MyList[j+1] THEN
			Temp <- MyList[j]
			MyList[j] <- Temp
			MyList[j+1] <- Temp
			Swapped <- TRUE
		ENDIF
	NEXT j
	n <- n - 1
UNTIL Swapped = FALSE
```

## Linear Search

Find whether a given value is stored in the array.

### How

- A FOR loop goes through the array
- It compares item in question to those in list using an IF:
  - If item matches with another then search is stopped
  - Also the location where it was found is returned
  - If not found it exits the FOR loop
- Then returns fact that item in question is not in the list

### Example

Finding a student in the **StudentList** array.

![](/uploads/Theo/image_1712726748.png)

```pseudocode
DECLARE NameGiven : STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
INPUT NameGiven
Found <- FALSE
Index <- 0
WHILE Found = FALSE AND Index <= 4
	IF StudentList[Index] =  NameGiven THEN
		Found <- TRUE
	ENDIF
	Index <- Index + 1
	
IF Found = TRUE THEN
	OUTPUT "Value found at location:", Index
ELSE
	OUTPUT "Value not found"
ENDIF
```

# Abstract Data Type

An abstract data type (ADT) is a theoretical model defining a data structure's behavior and operations independently of its implementation details.

## Stacks

A stack in programming is a data structure that operates on a **last-in, first-out (LIFO)** basis, allowing data to be added (pushed) and removed (popped) from the top of the stack.

### Initializes an empty stack

![](/uploads/Theo/image-20240417143411379.png)

- The TopOfStack pointer points to the last item added to the stack.
- The BottomOfStack pointer points to the first item on the stack.
- The stack grows upwards when items are added.
- Top pointer will be incremented by 1 whenever a new item is added.

### How the stack can be implemented using an array

1. Declare a (1D) array of data type STRING
2. The number of elements in that array corresponds to the size of the required stack
3. Declare an integer / variable for StackPointer
4. Declare an integer / variable for the size of the stack // for the max value of StackPointer
5. Use the StackPointer as an index to the array
6. Pointers and variables initialised to indicate empty stack
7. Store each item on the stack as one array element / Each stack item maps to one array element
8. Attempt to describe Push **and** Pop operations
9. Push **and** Pop routines need to check for full or empty conditions

## Queues

A queue in programming is a data structure that follows the **first-in, first-out (FIFO)** principle, allowing elements to be added at the rear (enqueue) and removed from the front (dequeue) of the queue.
### Initializes an empty queue
![](/uploads/Theo/image-20240417143800742.png)
- The Front of Queue Pointer points to the next data item to be removed.
- The End of Queue Pointer points to the last data item added.
- The queue is circular so that locations can be reused.
- When one value joins the queue, the EndOfQueuePointer will be incremented before adding the value to the array element where the pointer is pointing to.
- When the foremost item in the queue is removed, deleting the value to the array element where the FrontOfPointer is pointing to,  then the FrontOfPointer will be incremented.

### Features:

1. Each queue element contains one data item
2. A Pointer to the front / start of the queue
3. A Pointer to the back / end of the queue
4. Data is added at back / end and removed from front / start // works on a FIFO basis
5. May be circular

### Example: 
![](/uploads/Theo/image-20240416125949794.png)
##### Describe how the data items Orange and Yellow are added to the queue shown in the diagram.

1. Check that the queue is not full
2. EoQ pointer will move to point to location 9
3. Data item Orange will be stored in location referenced by EoQ pointer
4. EoQ pointer will move to point to location 0
5. Data item Yellow will be stored in location referenced by EoQ pointer

##### A programmer decides to implement a queue Abstract Data Type (ADT) in order to store characters received from the keyboard. The queue will need to store at least 10 characters and will be implemented using an array.

##### Describe the declaration and initialisation of the variables and data structures used to implement the queue.

1. Declare a (1D) array of size >= 10 
2.  …of data type CHAR
3. Declare integer variable for FrontOfQueuePointer 
4. Declare integer variable for EndOfQueuePointer
5. Initialise FrontOfQueuePointer and EndOfQueuePointer to represent an empty queue
6. Declare integer variable or NumberInQueue
7. Declare integer variable for SizeOfQueue to count / limit the max number of items allowed // Reference to mechanism for defining 'wrap' of circular queue
8. Initialise SizeOfQueue // Initialise NumberInQueue

## Linked List

A linked list is a linear data structure where elements, known as nodes, are connected via pointers, each node containing data and a reference to the next node in the sequence.

![](/uploads/Theo/image-20240416132611605.png)

![](/uploads/Theo/image_1713246315.png)

The symbol Ø represents a null pointer.

### Features:

1. Each node contains data and a pointer to the next node
2. A Pointer to the start of the list
3. Last node in the list has a null pointer
4. Data may be added / removed by manipulating pointers (not moving data)
5. Nodes are traversed in a specific sequence
6. Unused nodes are stored on a free list // a free-list pointer to the Free List

### Explain how the linked list showed above can be implemented.

1. Declare **two** (1D) arrays
2. One for data, one for pointers
3. Elements from same index represent one node
4. Declare an integer / variable for StartPointer 
5. Define appropriate value for null pointer
6. Declare an integer / variable for FreeList pointer 
7. Routines are needed to add / delete / search

### Advantages

- Pointers determine the ordering of data // only the pointers need to be changed when data changed
- Easier to add / delete data (to maintain correct sequence) in a linked list // description of moving data to maintain correct sequence when array used

### Disadvantages

- Need to store pointers as well as data
- More complex (to setup / implement)