Abstract Data Types

Data Structures

Data ≡Abstraction of reality

Personnel File

Choice of representation and Level of Detail

Arithmetic?

Precise?

Counting?

Comparison? Logic?

Report Composition?

Desired Internal Representation?

Goals for Studying Data Structures

· Identify useful objects/entities, operations, and classes of problems that can be solved using them.

· Determine representations for the abstract entities and implementations for abstract operations.

· Space (Memory), Executing Time, Programming Time

Built-in Data Types

Boolean - (Logical Type)

*Integer

*Float

*Char

[*Elementary Types (Atomic)]

Structured Type

Array

Records (or structs)

Set

Strings

Files

Dynamic (Structured) Types

Stacks

Queues

Linked Lists

Graphs

Trees

Hash Tables

3 Key Ideas for each Data Type

1. What are the attributes of the type?

2. What operations are allowed on instances of type?

3. What compromises must be made when a specific means of implementation is Chosen for the type?

Variable-Storage Location

-Representation

(Bits String)ßData Type

C++ Enumerations

Enum Color [Red, Orange, Yellow, Green, Blue, Indigo, Violet]

0 1 2 3 4 5 6

Enum Base [Binary=2, Octal=8, Decimal=10, Hex=10]

Enum Day [Day Under Flow=1, Sun, Mon, Tue, Wed, Thurs, Fri, Sat, Number Days, Overflow=7]

Day Next (Day DayVal)

{

Switch (DayVal)

{

Case Sun: Return Mon;

Case Mon: Return Tue;

}

Case Sat: Return Sun;

Default: cerr<<”Bad Day”;

Return Day Flow;

}

à Overloaded Operators

#include <ostream.h>

ostream& operator << (ostream& Out, Day DayVal) ß (return type)

}

switch (DayVal)

}

case sun; out<<”Sunday”

break;

}

case sat: out<<”Saturday”

break;

default: cerr<<”Bad Day Value!”;

return out;

}

Finishing up from last times lecture:

Template < class T, int size > class vector

{

struct

{

T data;

Int defined;

} Elements [size];

public;

}

typedef Vector<int, 100> BigInt;

BigInt X;

Type Vector<char, 26> Alfa;

Alfa Z;

Int I=3;

float x;

x=(float)I;

C style typecast

x=float (I);

(C++) functional notation for type cast

Int Array X;

X [0]=1;

X [1]=2;

OneClass I= OneClass(X); //Constructor

OneClass J= OneClass(X);//Typecast

OneClass K=X; //Conversion

IntStruct Y;

Y,A=3

Y,B=4

OneClass L=OneClass(Y);

OneClass M=(OneClass)Y;

OneClass N=Y;

Two Class Z=(OneClass N);