LU 2.txt

Abstract Data Types (ADTs) Solving a problem involves: Processing data Careful organization of the data To identify: The collection of data items Basic operations that must be performed on them ADT Definition A collection of data items together with the operations on the data The word "abstract" ref...

Abstract Data Types (ADTs) Solving a problem involves: Processing data Careful organization of the data To identify: The collection of data items Basic operations that must be performed on them ADT Definition A collection of data items together with the operations on the data The word "abstract" refers to studying data and basic operations independently of their implementation Focus on what can be done with the data, not how it is done ADT Example Implementation of ADT consists of: Storage structures to store the data items Algorithms for basic operations Data Structures, Abstract Data Types, and Implementations Example: Airplane flight with 10 seats to be assigned Tasks: List available seats Reserve a seat How to store & access the data? 10 individual variables An array of variables Using 10 Individual Variables Algorithm to List Available Seats: If seat1 == ' ': display 1 If seat2 == ' ': display 2... If seat10 == ' ': display 10 Algorithm to Reserve a Seat: Set DONE to false If seat1 == ' ': Print "do you want seat \#1?" Get answer If answer == 'Y': Set seat1 to 'X' Set DONE to true If seat2 == ' ': Print "do you want seat \#2?" Get answer If answer == 'Y': Set seat2 to 'X' Set DONE to true... Using an Array Algorithm to List Available Seats: For number ranging from 0 to max\_seats -1, do: If seat\[number\] == ' ': Display number Algorithm to Reserve a Seat: Get the number of the seat to be reserved If seat\[number\] is equal to ' ': Set seat\[number\] to 'X' Else: Display a message that the seat having this number is occupied Data Structure and Abstract Data Type Terms: Data Structures and Abstract Data Type are often used interchangeably ADT is used when data is studied at a logical level Data structure refers to a construct in programming language used to store data Array ADT Collection of data elements: A fixed-size sequence of elements, all of the same type Basic Operations: Direct access to each element in the array by specifying its position so that values can be retrieved from or stored in that position Different Types of Array One-dimensional array: Only one index is used Multi-dimensional array: Array involving more than one index Static array: The compiler determines how memory will be allocated for the array Dynamic array: Memory allocation takes place during execution One-Dimensional Static Array Syntax: CopyElementType arrayName\[CAPACITY\]; ElementType arrayName\[CAPACITY\] = {initializer\_list}; Example: Copyint b\[10\]; int b\[10\] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Array and ADT Array as an ADT: Fixed size: Specify the capacity of the array Ordered: Indices are numbered 0, 1, 2,..., capacity -1 Same type of elements: Specify the element type Direct access: Subscript operator \[\] Example of array: Copyint const size = 10; int a\[size\]; int b\[size\] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int c\[size\] = {1, 2, 3}; int d\[size\] = {0}; char name\[size\] = "John Doe"; Array Output Function Function: Copyvoid display(int array\[\], int num\_values) { for (int i = 0; i \< num\_values; i++) cout \