# Presentation: 531189

## C++ Plus Data Structures

**Nell Dale**
**Chapter 2**
**Data Design and Implementation**
***Modified from the Slides by Sylvia Sorkin, Community College of Baltimore County - Essex Campus***

## 1. What do we mean by data?

2. Data abstraction and encapsulation

3. Data structure

4. Abstract data type operator categories

**2. Data abstraction and encapsulation**
**3. Data structure**
**4. Abstract data type operator categories**

**Different Views of Data       **

## 2. Data Abstraction       

**Separation of a data type’s logical properties from its implementation.**

**LOGICAL PROPERTIES****	****IMPLEMENTATION**

**What are the possible values?****	****            How can this be done in C++?**
**What operations will be needed?****	****            How can data types be used?**

## Data Encapsulation       

**Data Encapsulation       **

**is the separation of the representation of data from the applications that use the data at a logical level;  a programming language feature that enforces information hiding.**** **** **

**int  y;**
**y = 25;**

## Encapsulated C++ Data Type int

**Encapsulated C++ Data Type int**

**     ****Value range:  **
**INT_MIN . . INT_MAX**
**     ****Operations:**
**     ****+  prefix**
**     ****-  prefix**
**     ****+  infix**
**     ****-  infix**
**     *********  infix**
**     ****/  infix**
**     ****%****  ****infix**
**Relational Operators **
**        ****infix **

***TYPE***
** ****int**** **

**(inside)**

**Representation of**
**	****int**
**   ****as 16 bits two’s **
**    ****complement**
**	****+**
**Implementation of **
**      ****Operations**

## Abstract Data Type (ADT)       

**A data type whose properties (domain and operations) are specified independently of any particular implementation. **

## 3. Data Structures       

**Defined by**
**the logical arrangement of data elements**
**the set of operations we need to access the elements**

## Application (or user) level: modeling real-life data in a specific context.

Logical (or ADT) level: abstract view of the domain and operations.       WHAT

Implementation level: specific representation of the structure to hold the data items, and the coding for operations.      HOW

***Application (or user) level:***** modeling real-life data in a specific context.**
***Logical (or ADT) level:***** abstract view of the domain and operations.       ****WHAT**
***Implementation level:***** specific representation of the structure to hold the data items, and the coding for operations.      ****HOW**

**Data from 3 different levels       **

## Viewing a library from 3 different levels       

***Application (or user) level:***** Library of Congress, or Baltimore County Public Library.**
***Logical (or ADT) level:***** domain is a collection of books; operations include: check book out, check book in, pay fine, reserve a book.**
***Implementation level:***** representation of the structure to hold the “books”, and the coding for operations.**

## 4. ADT Operator Categories

**Constructor**** -- creates a new instance (object) of an ADT. **
**Transformer**** -- changes the state of one or more of the data values of an instance.**
**Observer**** -- allows us to observe the state of one or more of the data values without changing them.**
**Iterator**** -- allows us to process all the components in a data structure sequentially.**

## Abstraction and Built-in Types       

## C++  Built-In Data Types

**Composite**

**array   struct   union   class**

**Simple**

** ****Integral**

**Floating**

**char  short   int  long  enum**

**float  double   long double**

## Composite Data Type       

**A composite data type is a type which **
**stores a collection of individual data components under one variable name,**
**and allows the individual data components to be accessed.**

## Two Forms of Composite Data Types

**Components are not **
**organized with respect to **
**one another.**

**The organization **
**determines method used **
**to access individual **
**data components. **

**UNSTRUCTURED**

**STRUCTURED**

**EXAMPLES:**** ****	****	****	****EXAMPLES:****  arrays**
**classes and structs**

## Records       

**A record is a composite data type made up of a finite collection of not necessarily homogeneous elements called *****members *****or *****fields*****.  ****For example . . .**

## struct  CarType

**struct  CarType**

**struct  CarType*****	***
**{**
**	****	****int     year ;     **
**     ****char    maker[10];      **
**	****	****float   price ;****          **
**	**
**} ;**
**CarType  thisCar;****	**** *****//CarType variables***
**CarType  myCar;*****     ***

## Accessing struct members 

**The ****member selection operator**** (period . ) is used between the variable name and the member identifier to access individual members of a record (struct or class) type variable.**
**EXAMPLES**
**	****	****	****myCar.year**
**	****	****	****thisCar.maker[4]**

## Valid struct operations 

- Operations valid on an entire struct type variable:
- 	    **assignment to another struct variable of same type,**
** **
**        ****pass as a parameter to a function**
**	****	****	****	****(either by value or by reference),**
**        ****return as the value of a function**.

## Pass-by-value

- sends a *copy** *
- of the contents of
- the actual  parameter

**SO, **
**the actual parameter cannot be changed by the function.**

## Pass-by-reference

- can change  value  of
- actual  parameter

## Using struct type Reference Parameter to change a member

**Using struct type ****Reference**** Parameter to ****change**** a member**

**void  AdjustForInflation(CarType&  car,  float  perCent)**
**// Increases price by the amount specified in perCent****	**
**{**
**	****	****car.price = car.price * perCent + car.price;     **
**} ;**
**SAMPLE CALL**
**AdjustForInflation(myCar, 0.03);**

## Using struct type Value Parameter to examine a member

**Using struct type ****Value**** Parameter to ****examine**** a member**

**bool  LateModel(CarType  car,  int date)**
**//  Returns true if the car’s model year is later than or**
**//  equal to date;  returns false otherwise.****	**
**{**
**	****	****return  ( car.year  >=  date ) ;**
**} ;**
**SAMPLE CALL**
**if ( LateModel(myCar, 1995) )**
**	****cout << myCar.price << endl ;**

## One-Dimensional Array at the Logical Level

**A one-dimensional array is a structured composite data type made up of a finite, fixed size (*****known at compile time*****) collection of homogeneous (*****all of the same data type*****) elements having relative positions and to which there is direct access (*****any element can be accessed immediately*****).**
**Array operations (*****creation, storing a value, retrieving a value*****) are performed using a declaration and indexes.**

## Implementation Example

- float  values[5];       ***// assume element size is 4 bytes***

**This ACCESSING FUNCTION gives position of values[Index]**
**Address(Index) = BaseAddress + Index * SizeOfElement**

**Base Address**

**values[0]   values[1]   values[2]   values[3]    values[4]**

** ****7000          7004          7008           7012           7016        **

**                   ****Indexes **

## One-Dimensional Arrays in C++ 

- The index must be of an integral type (char, short, int, long, or enum).
- The index range is always 0 through the array size minus 1.
- Arrays cannot be the return type of a function.

## Another Example

- char  name[10];	    ***// assume element size is 1 byte***

**name[0]  name[1]  name[2]  name[3]  name[4]                     .   .   .   .   .                       name[9]**

** ****6000    6001    6002    6003    6004    6005    6006    6007    6008    6009**

**Base Address**

**This ACCESSING FUNCTION gives position of name[Index]**
**Address(Index) = BaseAddress + Index * SizeOfElement**

## Passing Arrays as Parameters

- In C++, arrays are *always* passed by reference, and & is not used with the formal parameter type.
- Whenever an array is passed as a parameter, its base address is sent to the called function.

## const array parameter 

**const ****array parameter **

**Because arrays are always passed as reference parameters, you can protect the actual parameter from unintentional changes by using ****const**** in formal parameter list and function prototype.**
**FOR EXAMPLE . . .**
**	****	****	****	****	****	****	****  *****// prototype***
**  ****float  SumValues(****	****const****  float  values[ ], **
**	****	****	****	****            ****int  numOfValues );**

## float  SumValues (const  float  values[ ],                                            int   numOfValues )

**float  SumValues (****const****  float  values[ ], ****                                           int   numOfValues )**

***//  Pre:   values[ 0] through values[numOfValues-1] ***
***//           have been assigned***
***//  Returns the sum of values[0] through***
***//  values[numOfValues-1]***
**{**
**    ****float  sum  = 0;**
** ****  ****   ****for ( int  index = 0;  index < numOfValues; index++ )**
**    ****{**
**	****	****sum += values [ index ] ;**
**    ****}**
**     ****return  sum;**
**}**

## Two-Dimensional Array at the Logical Level

**A two-dimensional array is a structured composite data type made up of a finite, fixed size collection of homogeneous elements having relative positions and to which there is direct access.**
**Array operations (*****creation, storing a value, retrieving a value*****) are performed using a declaration and a ****pair of indexes**** ****(*****called row and column*****) representing the component’s position in each dimension.**

## EXAMPLE -- To keep monthly high temperatures for            		50 states in a two-dimensional array. 

const  int  NUM_STATES    =  50 ;
const  int  NUM_MONTHS  =  12 ;
int  stateHighs [ NUM_STATES ] [ NUM_MONTHS ] ;

               [ 0 ]
               [ 1 ]
               [ 2 ]
                 .
                 .					  stateHighs [2] [7]
                 .
              [ 48 ]
              [ 49 ]

**EXAMPLE -- To keep monthly high temperatures for            ****	****	****50 states in a two-dimensional array. **
** **
**const  int  NUM_STATES    =  50 ;**
**const  int  NUM_MONTHS  =  12 ;**
**int  stateHighs [ NUM_STATES ] [ NUM_MONTHS ] ;**
**               ****[ 0 ]**
**               ****[ 1 ]**
**               ****[ 2 ]**
**                 ****.**
**                 ****.****	****	****	****	****	****  ****stateHighs [2] [7]**
**                 ****.**
**              ****[ 48 ]**
**              ****[ 49 ]**

**[0]  [1]  [2]  [3]  [4]   [5]  [6]  [7]  [8]  [9] [10] [11]**

**66 64 72 78 85 90 99 115 98 90 88 80**

**row 2,**
**col 7**
**might be**
**Arizona’s**
**high for**
**August**

## Finding the average high temperature for Arizona

**int  total  = 0 ;**
**int  month ;****	****	****	**
**int  average ;**
**for ( month = 0 ; month < NUM_MONTHS ; month ++ )**
**      ****total = total + stateHighs [ 2 ] [ month ] ;       **
**                     **
**average  = int ( total / 12.0  + 0.5 ) ;****	****	****	****        **

## const  int  NUM_STATES    =  50 ;const  int  NUM_MONTHS  =  12 ;int  stateHighs [ NUM_STATES ] [ NUM_MONTHS ] ;

- In memory, C++ stores arrays in row order.  The first row is followed by the second row, etc.

**12 highs for state 0         12 highs for state 1              etc.**** **
**Alabama                           Alaska****                       **
**first row                            second row            **

**8000**

**8024**

**8048**

**Base Address**

**STORAGE**

**  ****. . .**

**rows                          columns**

## Implementation Level View

**stateHighs[ 0 ] [ 0 ]**
**stateHighs[ 0 ] [ 1 ]**
**stateHighs[ 0 ] [ 2 ]**
**stateHighs[ 0 ] [ 3 ]**
**stateHighs[ 0 ] [ 4 ]**
**stateHighs[ 0 ] [ 5 ]**
**stateHighs[ 0 ] [ 6 ]**
**stateHighs[ 0 ] [ 7 ]**
**stateHighs[ 0 ] [ 8 ]**
**stateHighs[ 0 ] [ 9 ]**
**stateHighs[ 0 ] [10 ]**
**stateHighs[ 0 ] [11 ]**
**stateHighs[ 1 ] [ 0 ]**
**stateHighs[ 1 ] [ 1 ]**
**stateHighs[ 1 ] [ 2 ]**
**stateHighs[ 1 ] [ 3 ]**
**           ****.**
**           ****.**
**           ****.**

**To locate an element such as**
**stateHighs [ 2 ] [ 7] **
**the compiler needs to know **
**that there are 12 columns**
**in this two-dimensional array.**
**At what address will **
**stateHighs [ 2 ] [ 7 ] be found?**
**Assume 2 bytes for type int.**

**Base Address 8000**

## Two-Dimensional Array Parameters

**Just as with a one-dimensional array, when a two- (or higher) dimensional array is passed as a parameter, the base address of the actual array is sent to the function.**
**The size of all dimensions except the first must be included in the function heading and prototype.**
**The sizes of those dimensions for the formal parameter must be exactly the same as in the actual array.**

##  Using typedef with arrays

** ****Using**** typedef ****with arrays**

**helps eliminate the chances of size mismatches between **
**formal and actual parameters.            FOR  EXAMPLE,**
**typedef  int   StateHighsType [ NUM_STATES ] [ NUM_MONTHS ] ;**
**typedef  int   StateAveragesType [ NUM_STATES ] ;**
**void  findAverages(****  const  ****StateHighsType         stateHighs , ****	****	****      ****	****        ****  ****           StateAveragesType  stateAverages  )**
**{**
-            .
-            .
-            .
**}**

## Declaring Multidimensional Arrays

**EXAMPLE USING TYPEDEF**
**const  int NUM_DEPTS      =   5 ;    *****// mens, womens, childrens, electronics, linens***
**const  int NUM_MONTHS  =  12 ;     **
**const  int NUM_STORES   =    3 ;   *****// White Marsh,  Owings Mills, Towson***
**typedef  long MonthlySalesType***** *****[NUM_DEPTS] [NUM_MONTHS] [NUM_STORES];**
**MonthlySalesType   monthlySales;**

## const  int NUM_DEPTS      =   5 ;    // mens, womens, childrens, electronics, linens
const  int NUM_MONTHS  =  12 ;     
const  int NUM_STORES   =   3 ;    // White Marsh,  Owings Mills, Towson

typedef long MonthlySalesType [NUM_DEPTS] [NUM_MONTHS] [NUM_STORES] ;
MonthlySalesType   monthlySales;

**const  int NUM_MONTHS  =  12 ;     **
**const  int NUM_STORES   =   3 ;    *****// White Marsh,  Owings Mills, Towson***
**typedef long MonthlySalesType***** *****[NUM_DEPTS] [NUM_MONTHS] [NUM_STORES] ;**
**MonthlySalesType   monthlySales;**

**                  ****monthlySales****[****3****][****7****][****0****]**
**sales for electronics in August at  White Marsh**

**12  MONTHS columns**

**5 DEPTS**
**   ****rows**

**3  STORES**
**   ****sheets**

## Higher Level Abstraction and C++ Class Type

## C++ class data type

**A class is an unstructured type that encapsulates a fixed number of data components (****data members****) with the functions (called ****member functions****) that manipulate them.**
**The predefined operations on an instance of a class are whole assignment and component access.**

## class Logbook Specification

**class**** ****Logbook**** Specification**

**//  SPECIFICATION FILE****	****	****( Logbook.h )**
**class  Logbook*****	******	******	******// declares a  class data type***
**{****	****	****	****	****	****	**
**public : ****	****	****	****	*****// public member functions***
***	******Logbook ( int month, int year);******	******// constructor***
**	****void          putEntry (**** ****int  day,**** ****int  value) ; ****// store entry for day**
**	****int****	****         getEntry ( int day)  ****const ****;         *****// return entry for day***
**	****...**
**private :****	****	****	****	*****//  private data members***
**	****...         **
**	****int             logMonth, logYear, entry[31];          **
**} ;*****	***

## Use of C++ data type class

**Variables of a class type are called ****objects**** (or instances) of that particular class.**
**Software that declares and uses objects of the class is called a ****client****.**
**Client code uses public member functions (called methods in OOP) to handle its class objects.**
**Sending a message**** means calling a public member function.**

## Client Code Using Logbook

**Client Code Using**** Logbook**

**// Test1.cpp**
**#include   “Logbook.h”    ****	****    *****// includes specification of the class***
**#include   <iostream.h>**
**void  main ( )**
**{**
**	**** ...**
**	**** ****Logbook  testLog(month,year); *****// declares an object of  Logbook***
***	****** ******...***
***	****** ******testLog.putEntry(day, entry);***
***	****** ...***
***	****** ******cout << ... << testLog.getEntry(day) << ... ;***
**	**** ...**
**	**** ****Logbook logDay100(month, year), **
**	****                 ****logDay200(month, year); ****// declares new obj. of Logbook**
**	**** ****...**
**}*****	***

## Two separate files generally used for class type

**  ****//   SPECIFICATION FILE                  ****( Logbook .h )**
**  ****//   Specifies the data and function members.**
**  ****class Logbook****	**
**    ****{**** **
**      ****public:**
-               .  .  .
**      ****private:**
**            ****.  .  .**
**     ****} ;**
**  ****//   IMPLEMENTATION FILE ****	****          ****( Logbook.cpp )**
**  ****//   Implements the Logbook member functions**.
-           .  .  .

** **

** ****Logbook ****Class Instance Diagrams**

**logDay100         ****	****          logDay200**

**1**
** **
**2001**
**100*day**

**Private data:**
**logMonth**
**logYear**
**Entry[]**

**Logbook()**

## Implementation of Logbook member functions 

**Implementation of ****Logbook**** member functions **

**// IMPLEMENTATION FILE                    (Logbook.cpp)**
**#include “Logbook.h”*****// also must appear in client code***** **
**Logbook :: Logbook ( int month, int year) **
** ****	****            ****// constructor: initialize data members of class**
**{**
**	****int j;   ****// loop counter**
**	****logMonth = month;**
**	****logYear    = year;**
**	****for (j=0; j<31; j++)**
**	****	****entry[j] = 0;**
**}**
**void Logbook :: putEntry ( int day, int  value) *****//  store entry for the specified day.***
**{**
**	****   ****entry[day-1] = value;**
**}**
**...**

## Class Instances and Member Functions 

**The member selection operator ( . ) selects either data members or member functions.**
**	****	****	****	****testLog.putEntry**** ****( )**** ;**
**	****	****	****	****testLog.getEntry**** ****( )**** ;**
**Header file ****Logbook****.h**** declares the ****Logbook**** class.**
**testLog****, ****logDay100**** and ****logDay200**** are class objects and ****put****Entry**** and ****getEntry**** ****are member functions.**
**	****	****	****	**
**	****	****	****	**

## Scope Resolution Operator ( :: ) 

**C++ programs typically use several class types.**
**Different classes can have member functions with the same identifer, like Write( ).**
**Member selection operator is used to determine the class whose member function Write( ) is invoked. **
**	****	****currentDate .Write( ) ;*****	******	******// class DateType***
**	****	****numberZ .Write( ) ;*****	******	******// class ComplexNumberType***
**In the implementation file, the scope resolution operator is used in the heading before the member function’s name to specify its class. **
**	****	****void  DateType :: Write ( )   const**
**	****	****{           .  .  .**
**	****	****}**

## Information Hiding

**Class implementation details are hidden from the client’s view.  This is called information hiding.**
**Public functions of a class provide the**** interface**** between the client code and the class objects.**

**client**
**code**

**specification**

**implementation**

**abstraction**
**    ****barrier**

## Object-Oriented Programming 

**Three essential ingredients:**
**encapsulation**
**Inheritance**
**polymorphism**