CMPT 115
Abstract Data Types

1 / 21

Part I Data Types

2 / 21

Outline

1

Levels of Data Abstraction Atomic Data Composite Data Data Types Data Structures Abstract Data Types Implementing ADTs

3 / 21

Levels of Data Abstraction

Atomic Data Composite Data Data Types Data Structures Abstract Data Structures

4 / 21

Atomic data

We will start out at a “low-level” and build up. Atomic data are data which consists of a single piece of information. Examples: numbers, characters, references

5 / 21

Composite data

Composite data represents data which can be broken down into various smaller parts or subfields. Multiple properties are required to capture its relevant data.

6 / 21

Composite data

Example: a point on a graph is represented by two real numbers, an x coordinate and a y coordinate. These two numbers are associated with each other. Example: a phone number is represented by area code, exchange and the number within the exchange. Example: a geometric shape such as a circle is represented by it’s center point, and it’s radius (observe nesting of composite data!).

C++
In C++, composite data are usually represented by a struct. This term is ambiguous! Sometimes it refers to a type; sometimes it refers to data.

7 / 21

Data Types

A data type packages together data and ways of manipulating the data together.

Data Type
A data type consists of two parts:
1 2

a set of values operations that can be performed on the data.

8 / 21

Example Data Types
Example (Integer Data Type)
The integer data type can consist of: data values: −∞, . . . , −2, −1, 0, 1, 2, . . . , ∞ operations: +, −, ∗, %, /, . . .

Example (Character Data Type)
The character data type can consist of: data values: \0, . . ., ’A’,’B’,. . .,’a’,’b’,. . ., ’1’, ’2’, . . . operations: , ≤, ≥, ==, . . .

Example (Person Data Type)
The Person data type can consist of: data values: { 15, "Bob", "Buckwheat"}, { 50, "Jack", "Bauer" }, . . . operations: set/get firstname, set/get lastname, set/get age, ==, . . .
9 / 21

Data Structures

A data structure is an aggregation of data elements into a set with defined relationships.

Data Structure
A combination of elements in which each element is either a data type or another data structure. A set of associations or relationships (structure) between elements.

10 / 21

Data Structures

Example (Data Structure: Array)
Elements: All the same data type (integer, float, Person, etc,.). Structure: Elements form a contiguous sequence in which each element is numbered with an index.

Example (Data Structure: Matrix (2D array))
Elements: All the same data type (integer, float, Person, etc,.). Structure: Elements form a grid in which each element has a row and column position. We will see additional examples of data structures in this course, such as lists, and trees.

11 / 21

Abstract Data Types

An abstract data type (ADT) is an abstraction that permits programmers to make use of the data structure without knowing its internal implementation. We know what an ADT can do, but how it is done is hidden.

Abstract Data Type
An abstract data type consists of: One or more data structures (declaration of data). Declaration of operations on the data (the interface). Encapsulation (hiding) of data and the implementation of the operations.

12 / 21

ADTs

Example (String ADT)
A string consists of: the data structure: a sequence of characters the operations (interface): create, compare, concatenate, etc. (in C++, interface specified in cstring) the encapsulation: Implementation of operations and data structure are hidden in the string library (data structure might be character array like in C++, might be something else...)

13 / 21

ADTs

Example (Matrix ADT)
A matrix consists of: the data structure: a 2D array of numbers the operations (interface): create, edit element, +, −, /, ×, . . . the encapsulation: details of operations