Transcript pptx

CSCE 221-200, SPRING 2016
INSTRUCTOR: DR. NANCY M. AMATO
1
SYLLABUS , COURSE ORGANIZATION & ASSIGNMENTS
 Course Webpage: http://parasol.tamu.edu/~amato/Courses/221
 Syllabus: https://parasol.tamu.edu/~amato/Courses/221/Syllabus/syllabus.pdf
 Assignments and Activites: https//parasol.tamu.edu/~amato/assignments.php

Culture

Programming

Homework

In Class Activities (ICAs) and In Lab Activities (ILAs)
2
CH 1-4 : INTRODUCTION
ACKNOWLEDGEMENT: THESE SLIDES INCLUDE INPUT FROM SLIDES PROVIDED WITH ``DATA STRUCTURES AND
ALGORITHMS IN C++’’, GOODRICH, TAMASSIA AND MOUNT (WILEY 2004) AND SLIDES FROM JORY DENNY
3
OBJECT ORIENTED DESIGN (CH 2)
 Object Oriented Design and Principles
 Abstract Data Types
 Encapsulation
 Inheritance
 Polymorphism
 Exceptions
4
OBJECT ORIENTED DESIGN AND PRINCIPLES (CH 2.1)
 Design Principles:

Abstraction: Abstract the complicated details in form
of fundamental parts and operations
 Design Goals:

Robustness : Capability to handle any type of inputs

Encapsulation: Coupling data with methods.

Adaptability : Can be used in various environments with
minimal or no changes

Modularity: Component based design

Inheritance: Hierarchical and “is-a type-of” relationship

Polymorphism: Ability to take different form

Reusability : Same code can be used as a component in
various applications over time
5
ABSTRACT DATA TYPE (ADT)
 An abstract data type (ADT) is an abstraction of a
data structure
 An ADT specifies:
 Example: ADT modeling a simple stock trading
system

The data stored are buy/sell orders

The operations supported are

Data stored

Operations on the data

order buy(stock, shares, price)

Error conditions associated with operations

order sell(stock, shares, price)

void cancel(order)
 Mathematical model only with no details about the
implementation :

ADT specifies what each operation does not how it
does it.

Error conditions:

Buy/sell a nonexistent stock

Cancel a nonexistent order
6
ENCAPSULATION
 Bundling of data and associated methods as a type.
 Hiding the details and direct access to the underlying data.
 Class: Construct or the definition of encapsulated data and associated methods. User-defined types.

class Person {
private: string name;
public:
string GetName() { return name; }
void SetName( string _n) { name = _n; }
}
 Object: Instance of an object

Person A; // A is an object of class Person or in other words type of A is Person
7
INHERITANCE
 Hierarchical organization of classes.
Shape
 Base class: The class from which another class is inherited.
 Derived class: The class that inherits
 Abstract classes: Base class with one or more virtual
member functions

Circle
Triangle
Square
Virtual member functions are abstract functions with no
details.
8
POLYMORPHISM
 Different types of a variable
 Subtyping : Type of the variable is determined at runtime based on the instance.

Eg: Shape* newShape = new Circle();
newShape->draw(); //Will call draw() function of Circle class and not of the Shape class.
 Parametric: Generics (templates) where code is written without any specific type.

Eg: template <typename T>
T sum ( T a, T b) {} // Can be used as sum (3,4) and sum (4.5, 7.8)
9
EXCEPTIONS (CH 2.4)
 Attempting the execution of an operation of ADT may sometimes cause an error condition, called an exception
 Exceptions are said to be “thrown” by an operation that cannot be executed
 Example: removing an element from an empty container
10
ARRAYS AND LINKED LISTS (CH 3)
 Arrays (Ch 3.1)
 Singly Linked List (Ch 3.2)
 Doubly Linked (Ch 3.3)
11
ARRAYS
 Data structure containing a collection of same type
 Contiguous allocation in memory
 Limitation: The length or capacity of the array is fixed.
 Easy Random Access through index of the element (position of the element with respect to the first element
in the array. Eg. A[3] indicates fourth element if the first element is stored in index 0.
 Insertions and deletion at arbitrary location would include rearrangement of the elements following the
location. Eg. Removing an element at index 6 would involve moving elements at indices 7,8,9 to 6,7,8.
12
SINGLY LINKED LIST
 A singly linked list is a concrete data structure consisting of a sequence of nodes
 Each node stores
next
 element
 link to the next node
 No contiguous allocation of memory
node
elem
 Accessing an element at an arbitrary location includes traversing the list
from the first element.

13
A
B
C
D
DOUBLY LINKED LIST
 A doubly linked list provides a natural implementation
of the Node List ADT
prev
next
 Nodes implement Position and store:
 element
 link to the previous node
elem
node
 link to the next node
 Special trailer and header nodes
 No contiguous allocation of memory
header
nodes/positions trailer
 Access at arbitrary position requires traversal of the
list
 Easy insertion and deletion of element

If the pointer to the element is known
elements
14
EXERCISE: ARRAYS, SINGLY LINKED LIST, DOUBLY LINKED LIST
 Describe how you would reach/access the third element in a data structure if it were a

Array

Singly Linked List

Doubly Linked List
 Would your answer change if we wanted to reach/access the last element in the data structure? If so, how?
15
EXERCISE: COMPLETE THE TABLE WITH THE COMPLEXITY OF THESE
OPERATIONS
Array
Singly Linked List
Doubly Linked List
Access first element
Access last element
Access middle element
16
EXERCISE: COMPLETE THE TABLE WITH THE COMPLEXITY OF THESE
OPERATIONS
Array
Singly Linked List
Doubly Linked List
Access first element
𝑂(1)
𝑂(1)
𝑂(1)
Access last element
𝑂(1)
𝑂(𝑛)
𝑂(1)
Access middle element
𝑂(1)
𝑛
𝑂( )
2
𝑛
𝑂( )
2
17