13.1 User-defined types

A user-defined data type is a feature in most high-level programming languages that allows a user (programmer) to define data type according to his/her requirements.
A data type constructed by a programmer
A data type that references at least one other data type, the data types can be primitive or user-defined. [MS]

Composite

[!Definition]

Can be user-defined or primitive

Refer to other datatypes containing more than one datatype

Composite datatype can be record/class/set

Record data type

TYPE <identifier1>
    DECLARE <identifier2> : <data type>
    DECLARE <identifier3> : <data type>
    ...
ENDTYPE

Set data type

TYPE <identifier1> = SET OF <data type>
DEFINE <identifier2> (value1, value2, value, … ) : <identifier1>
Example:
TYPE LetterSet = SET OF CHAR
DEFINE Vowels ('A','E','I','O','U'): LetterSet

Non-Composite

[!Definition]

Non-composite data types can both be user-defined or primitive

Non-composite data types do not refer to other data types in their definition

Non-composite data types can be primitive/enumerated/pointer(原始/枚举/指针)

Enumerated data type

[!Definition]
A user-defined non-composite datatype, with a list of all possible values that is ordered [3]

TYPE <identifier> = (value1, value2, value3, ... )
Example:
TYPE Season = (Spring, Summer, Autumn, Winter)

Pointer data type

[!Definition]
A user-defined non-composite datatype, stores memory location only and indicates the type of data stored in the memory location. [3]

TYPE <identifier> = ^<data type>

Declaration of pointer type
TYPE TIntPointer = ^INTEGER

Declaration of pointer variable
DECLARE MyPointer : TIntPointer

Dereference of pointer
TYPE Tmontin = ^STRING
DECLARE myMonth : Tmonth
myMonth ← monthPointer^ + 1

Dereferencing means accessing the contents of a memory location instead of its address.

Example

DECLARE Pupil1 : StudentRecord
DECLARE Pupil2 : StudentRecord
DECLARE Form : ARRAY[1:30] OF StudentRecord
DECLARE ThisSeason : Season
DECLARE NextSeason : Season
DECLARE MyPointer : TIntPointer
Pupil1.LastName ← "Johnson"
Pupil1.Firstname←"Leroy"
Pupil1.DateOfBirth ← 02/01/2005
Pupil1.YearGroup ← 6
Pupil1.FormGroup ← ꞌAꞌ
Pupil2 ← Pupil1
FOR Index ← 1 TO 30
    Form[Index].YearGroup ← Form[Index].YearGroup + 1
NEXT Index
ThisSeason ←Spring
MyPointer← ^ThisSeason
NextSeason← MyPointer^ + 1// access the value stored at the memory address

13.2 File Organization And Access

File Organization

Sequential

[!Definition]
A method of file organization in which data records are physically stored in a file, one after another, in a given order(Order based on key field, key usually be primary key). A new version (of the file) has to be created to update the file

Direct access to Sequential files

In sequential files, an index of all key fields is kept. The index is searched for the address of the file location where the target record is stored.

Serial

[!Definition]
a method of file organization in which data records are physically stored in a file, one after another, in the order they were added to the file.

Random

[!Definition]
a method of file organization in which data records are physically stored in a file in any available position; the location of any record in the file is found by using a hashing algorithm on the key field of a record. Updates to the file can be carried out directly

Direct access to Random files

A hashing algorithm is used on the record's key field to calculate the address of the memory location where the target record is expected to be stored. Method to find a record if it is not at the expected location, e.g., linear probing, search overflow area, etc.

File Access

Direct Access
[!Definition]
- The direct access method can physically find a record in a file without other records being physically read.
- Records are found by using the key field of the target record
  
  Sequential
  
  [!Definition]
  a method of file access in which records are searched one after another from the physical start of the file until the required record is found.
  
  Hash
  
  [!Definition]
  a mathematical formula used to perform a calculation on the key field
  
  Collision
  
  [!Definition]
  A collision is when the two values/data items in the key field for two records (pass through a hashing algorithm and) result in the same hash value, so the location identified (by the hashing algorithm) may already be in use.

Solution 1

Search the overflow area, go through the following spaces linearly, and store the data item in the first available slot.

Solution 2

Each storage space refers to a collection/chain of items that can be searched individually. The data item is stored in the first available space in this chain.