CS UNIT 13 medium

• A user-defined data type is a data type based on either an existing data type or other data types that a programmer has defined.
• User-defined data types can be divided into non-composite and composite data types.

Non-Composite Data Types

• A non-composite data type can be defined without referencing another data type.
• It can be a primitive type or a user-defined data type.
• They are usually used for a special purpose.
• Enumerated data types for lists of items and pointers to data in memory are non-composite data types.

Enumerated Data Types

• An enumerated data type contains no references to other data types when it is defined.
• In pseudocode, the type definition for an enumerated data type has this structure: TYPE <identifier> = (value1, value2, value3, ...)
• Example for months of the year: TYPE Tmonth = (January, February, March, April, May, June, July, August, September, October, November, December)
• The values are not strings, so they are not enclosed in quotation marks.

Pointer Data Types

• A pointer data type is used to reference a memory location.
• Needs to have information about the type of data that will be stored in the memory location.
• In pseudocode the type definition has the following structure: TYPE <pointer> = *<Typename>
• <Typename> is the type of data to be found in the memory location e.g. INTEGER, REAL.
• Example: TYPE TmonthPointer = *Tmonth, DECLARE monthPointer : TmonthPointer
• If the contents of the memory location are required rather than the address of the memory location, the pointer can be dereferenced by adding a ^ e.g., myMonth = monthPointer^.

Composite Data Types

• A data type that refers to any other data type in its type definition is a composite data type.
• Examples include records, sets and classes.

Sets

• A set is a given list of unordered elements that can use set theory operations such as intersection and union.
• A set data type includes the type of data in the set.
• In pseudocode, the type definition has this structure: TYPE <set-identifier> = SET OF <Basetype>
• Example: TYPE Sletter = SET OF CHAR, DEFINE vowel = ('a', 'e', 'i', 'o', 'u') : letters

Classes

• A class is a composite data type that includes variables of given data types and methods (code routines that can be run by an object in that class).
• An object is defined from a given class; several objects can be defined from the same class.

File Organization

• Data of all types is stored as records in files, which can be organized using different methods.

Serial File Organization

• The serial file organization method physically stores records of data in a file, one after another, in the order they were added to the file.
• New records are appended to the end of the file.
• Used for temporary files storing transactions to be made to more permanent files.
• Records will be in a chronological order.

Sequential File Organization

• Physically stores records of data in a file, one after another, in a given order.
• The order is usually based on the key field of the records as this is a unique identifier.
• New records must be added to the file in the correct place.

Random File Organization

• Physically stores records of data in a file in any available position.
• The location of any record in the file can be found by using a hashing algorithm on the key field of a record.
• Records can be added at any empty position.

File Access Methods

• There are different methods of file access (the method used to physically find a record in the file): sequential access and direct access.

Sequential Access

• Searches for records one after another from the physical start of the file.
• This method is used for serial and sequential files.
• When searching, every record needs to be checked until that record is found.
• Any new records are appended to the end of the file.
• In sequential files, the rest of the file does not need to be searched as the records are sorted on ascending key field values.

Direct Access

• Can physically find a record in a file without other records being physically read.
• Both sequential and random files can use direct access.
• For a sequential file, an index of all the key fields is kept and used to look up the address of the file location where a given record is stored.
• For a random access file, a hashing algorithm is used on the key field to calculate the address of the file location where a given record is stored.

Hashing Algorithms

• In the context of storing and accessing data in a file, a hashing algorithm is a mathematical formula used to perform a calculation on the key field of the record.
• The result of the calculation gives the address where the record should be found.
• Formula example: if a file has space for 2000 records and the key field can take any values between 1 and 9999, then the hashing algorithm could use the remainder when the value of key field is divided by 2000, together with the start address of the file and the size of the space allocated to each record.

Collisions

• Collisions can occur if more than one record lands on the same position.
• Dealing with collisions: open hash, where the record is stored in the next free space and closed hash, where an overflow area is set up.

Binary Floating-Point Representation

• Magnitude of the numbers depends on the number of bits used; however, using solely this type limits the range of numbers and does not allow for fractional values.
• Formula: M x 2^E
• M is the mantissa and E is the exponent.

Converting Binary Floating-Point Numbers into Decimal

• Method 1 is adding up the mantissa values where a bit appears, calculating the exponent value, and employing M x 2^E.
• In Method 2, one writes the mantissa down and moves the point relative to exponent value.

Normalization

• Used in order to address overflow and underflow errors.
• With this method, for a positive number, the mantissa must start with 0.1.
• The bits in the mantissa are shifted to the left until that condition is satisfied, and the exponent altered accordingly.
• For a negative number the mantissa must start with 1.0.

Precision versus Range

• Accuracy of a number can be increased by increasing the number of bits used in the mantissa.
• The range of numbers can be increased by increasing the number of bits used in the exponent.
• Accuracy and range will always be a trade-off between mantissa and exponent size.

Floating-Point Problems

• The storage of certain numbers is an approximation, due to limitations in the size of the mantissa.
• This problem can be minimized when using programming languages that allow for double precision and quadruple precision.
• Issues: overflow, underflow, the inability to store zero.