Transcript CS2006Ch01B

CS2006 - Data Structures I
Chapter 2
Principles of Programming
&
Software Engineering
Topics

Modular Design Concepts


Abstraction
OO Design
Encapsulation
 Inheritance
 Polymorphism


Top Down Design

2
Structure Chart
Abstraction & Information Hiding

Example: Cars brakes
My interior design is
using
Cylinder brakes
or
Drum brakes
Push
the brakes
Brake pedal pushed
Client
box
3
Car stop
Car
Black box
Abstraction


Abstraction separates the purpose of a
module from its implementation.
Example: Sorting
Sort this data
please,
I don’t care
how you do it
I can sort data into
ascending order without
you knowing how
Unsorted data
4
Client
box
Sorted data
Sort
Black box
Procedural Abstraction
Procedural Abstraction is the process of
separating the purpose of a method from
its implementation.



5
Once written the method can be used without
any knowledge of how it is implemented - only
need to know the parameters.
Example: nearly all methods in the entire Java
API.
Abstract Data Types
ADT - a collection of data along with a set of
operations that can be performed on that
data.



6
No details about how the data is stored or how
the operations on the data are implemented.
An ADT is a general description of the design of
a module with no details.
Abstract Data Types
Data Structure - the implementation of an
ADT in a programming language.


7
The details of data storage and how
operations are performed are crucial parts of a
data structure.
ADT List
Any List in general will allow the following
operations:







8
Create an empty list
Destroy a list
Determine whether a list is empty
Determine the number of items in a list
Insert an item at a given position in the list
What else?
Object-Oriented Design
Three elements to OOD:

Encapsulation - combining data and
operations within one object.
Inheritance - objects can inherit data and/or
methods from other objects.
Polymorphism - objects can determine
operations at execution time.




9
Every object knows its "true" type regardless of type
casting
Inheritance

A class can inherit the variables and methods of another
class.



It can keep those it wants and replace those it doesn’t.
Example: our Person class.
 we want a class of students.
 we can’t change our Person class because
 many people are using it as it stands
 perhaps we don’t have access to the source
code
Create a new class called Student that extends the
current class Person by the addition of a new variables
parent class
and methods
Person
super class
Student
10
child class
subclass
Class design

extend the definition of Person

build a subclass for each specific type of
person
Person
Student
11
Faculty
Class hierarchy
int getAge()
Person
Student
12
String getName()
Faculty
void setId(String new_id)
void setSalary(float newSalary)
float getGPA()
float getHoursWorked()
Object-Oriented Design
Produce a collection of objects that have
behaviours
How to do





13
Identifying the objects in the problem
UML
Contents of Software Engineering (cosc 4506)
Object-Oriented Design

14
Consider the nouns and verbs in the
problem domain
Create a ATM machine which allow user to retrieve,
deposit, transfer and check balance of their accounts
Account
ATM
Account: account
Type: String
Amount: double
Open ()
transfer (int )
Close()
checkBalance()
retrieve
deposit ()
Top-Down Design
Is a structured programming methodology
Focused on algorithm design.



15
Goal is to break a large problem into a set of
smaller problems that are more easily solved.
Top-Down Design
An attempt is made to solve a problem in
terms of small subproblems



16
Divide and Conquer strategy
How?
Top-Down Design (TDD)

Structure chart:
Find Median
Read Scores
Read score
From user
17
Insert score
into array
Sort scores
Get middle score
Structure Charts

Can add some info into our structure chart


to show how we share the data
Two type of info that get passed between
our methods


Data
Control Information or flags
Thing like “perform such and such an operation”
 Or “ we have hit the end of file”

18
Structure Charts

19
Use named arrows to show the data flow

Data arrows

Flag arrows
Structure Charts

Structure chart:
Find Median
Read Scores
20
Sort scores
Get middle score
Structure Charts

Structure chart:
Find Median
Read Scores
Read score
21
Insert score
into array
Sort scores
Get middle score
MarkEnrty: contain score and ID
MarkArray: contain array of scores
Structure Charts

Structure chart:
Find Median
Read Scores
Sort scores
Get middle score
EOF
MarkEntry
MarkEntry
Insert score
Read score
into array
22
MarkEnrty: contain score and ID
MarkArray: contain array of scores
Structure Charts

Structure chart:
Find Median
MarkArray
Read Scores
Sort scores
Get middle score
EOF
MarkEntry
MarkEntry
Insert score
Read score
into array
23
MarkEnrty: contain score and ID
MarkArray: contain array of scores
Structure Charts

Structure chart:
Find Median
MarkArray
Read Scores
MarkArray
Sort scores
MarkArray
Get middle score
EOF
MarkEntry
MarkEntry
Insert score
Read score
into array
24
MarkEnrty: contain score and ID
MarkArray: contain array of scores
Structure Charts


The manner in which this structure
diagram would be implemented as a
program is obvious
It is now possible to create a skeletal
program with all the method headers

25
All you need is to fill in detail
Structure Charts
Public class FindMedian {
public static void main (..) {
}
public static void readScore (int []MarkArray) { }
public static void sortScore (int []MarkArray) {}
public static int getMedian (int []MarkArray) {}

26
}
Structure Charts
public class FindMedian {
public static void main (..) {
int MarkArray [];
}
public static void readScore (int []MarkArray) { }
public static void sortScore (int []MarkArray) {}
public static int getMedian (int []MarkArray) {}

27
}
Structure Charts
public class FindMedian {
public static void main (..) {
int MarkArray [];
readScore (MarkArray);
}
public static void readScore (int []MarkArray) { }
public static void sortScore (int []MarkArray) {}
public static int getMedian (int []MarkArray) {}
28
Structure Charts
public class FindMedian {
public static void main (..) {
int MarkArray [];
readScore (MarkArray);
sortScore (MarkArray);
}
public static void readScore (int []MarkArray) { }
public static void sortScore (int []MarkArray) {}
public static int getMedian (int []MarkArray) {}
 }
29
Structure Charts
public class FindMedian {
public static void main (..) {
int MarkArray [];
readScore (MarkArray);
sortScore (MarkArray);
getMedian (MarkArray);
}
public static void readScore (int []MarkArray) { }
public static void sortScore (int []MarkArray) {}
public static void getMedian (int []MarkArray) {}
 }
30