CSC-335 Data Structures and Algorithms (Chapter 2Introduction to Abstract Data Types)
Instructor: Ahmad Reza Hadaegh
The content of this power point lecture has been originally created by Christos Kolonis and modified by Dr. Ahmad R Hadaegh
Chapter Contents
2.1 A first look at ADTs and Implementations 2.2 C++'s Simple Data Types
2.3 Programmer-Defined Data Types
2.4 Pointers
Chapter Objectives
Distinguish between ADTs and implementations of ADTs Review C++'s simple data types & ADTs they model See examples of how implementations of ADTs are sometimes insufficient Look at simple mechanisms to define new data types Take a first look at pointers and pointer operations
2.1 First Look at ADTs & Implementations For a programming task we must identify
The collection of data items
Basic operations to be performed on them EX: the car example, its properties and its functions
Taken together (data items & operations)
are called an Abstract Data Type (ADT)
Implementation
Storage structures for the data items Algorithms for the operations (functions)
2.2 C++ Simple Data Types Integers Unsigned integers
unsigned short, unsigned, unsigned long
Sometimes called whole numbers Represented in 2, 4, or 8 bytes
Signed integers
short, int, long
represented in two's complemen 1010 00000000000000000000000000001010
5
Two's Complement Representation
For nonnegative n:
Use ordinary base-two representation with leading (sign) bit 0
For n < 0
1) Find w-bit base-2 representation of |n| 2) Complement each bit.
3) Add 1 ---------------------------------------------------------------------------Ex: 00001010 in 8-bits system is equal to 10 in decimal. Now to get -10, we flip every bit to get 11110101 and add 1 to get 11110110 which is -10 in binary
6
Two's Complement Representation Example: 88
1. 88 as a 16-bit base-two number
0000000001011000
2. Complement this bit string
1111111110100111
3. Add 1
1111111110101000
WHY?
Two's Complement Representation Works well for arithmetic computations
5 + 6:
0000000000000101 +1111111111111010 1111111111111111
What gets done to the bits to give this answer?
Problems with Integer Representation Limited Capacity a finite number of bits An operation can produce a value that requires more bits than maximum number allowed. This is called overflow .
None of these is a perfect representation of (mathematical) integers Can only store a finite (sub)range of them. See Demonstrations Figure 2.1 and Figure 2.2
2.2 C++ Simple Data Types Character Data 1 byte for ASCII, EBCDIC 2 bytes for Unicode (java) or C++ wide character type
Operations ==, <, >, etc. Using numeric code
10
2.2 C++ Simple Data Types Boolean Data Values {false, true } Could be stored in bits, usually use a byte
Operations &&, ||, !
In C++
bool type int (boolVal) evaluates to
0 if false 1 if true
11
2.3 Programmer-Defined Data Types Typedefs
Mechanism usable to create a new type
Give new name to existing type
Example: typedef double real; Now either double or real can be used.
12
2.3 Programmer-Defined Data Types Enumerations
Mechanism for creating types whose literals are identifiers Each identifier associated with unique integer
13
2.3 Programmer-Defined Data Types Also possible to specify explicit values to give the enumerators
enum NumberBase { BINARY = 2, OCTAL = 8, DECIMAL = 10, HEXADECIMAL = 16};
14
2.4 Pointers
When regular variables are declared
Memory allocated for value of specified type Variable name associated with that memory location Memory initialized with values provided (if any)
Fig. 2.3
27
15
2.4 Pointers
Pointer Variables
value stored is a memory address
Note sample program, Figure 2.4 Declares variables that can store int addresses and double variables
Displays the addresses
16
Basic Pointer Operations
Dereferencing and indirection
Pointer variable stores address of a location Accessing contents of that location requires dereferencing operator *
Note program example Figure 2.5
17
Basic Pointer Operations
Assignment
Pointer variables can be assigned the values of other pointer variables bound to same type
18
Basic Pointer Operations
Consider *jPtr = 44;
Changes value that both pointers reference
*iPtr
iPtr = &j
Not good programming practice, hard to debug Known as aliasing problem
19
Basic Pointer Operations
Comparison
Relational operators used to compare two pointers
Must be bound to same type
Most common
= = and !=
The null address may be compared with any pointer variable
20
Dynamic Memory Allocation
The new operation Example typede int* intPtr; intPtr p = new int; X X X
intPtr p = new int;
21
Pointer Arguments
Pointers can be passed as arguments to functions
This is logically equivalent to reference parameters In fact, this is how early C++ compilers accomplished reference parameters
22
Pointer Examples
int i1; int i2; int* iPtr1; Int* iPtr2; double d1; double d2; double* dPtr1; double* dPtr2; dPtr1 = &d1 dPtr1 = d1; iPtr1 = & d1; iPtr2 = &i2; iPtr1 = iPtr2; dPtr1 = iPtr1; *iPtr1 = 19 *dPtr1 = *iPtr1; *dPtr2 = 20.67; *iPtr2 = *dPtr2;
23
