Transcript Chapter 1

COP 3540 Data Structures with OOP
Overview: Chapter 1
1
21
Why Data Structures and Algorithms?
 Data Structures are merely different
arrangements of data in primary memory or
on disk, and
 Algorithms are sequences of instructions
that manipulate the data in these data
structures in a variety of ways.
2
21
Examples of Some Data Structures
 Many data structures:








Arrays
Linked lists
Stacks
Binary Trees
Red Black Trees
2-3-4 Trees
Hash Tables
Heaps, etc.
 Different algorithms are needed to build, search,
and manipulate data stored in these various
structures
3
21
Plain Facts:
 The plain fact is that many items in nature have an
‘natural arrangement’ with their predecessor or
successor element.
 Think: records in a sequential file
 Think: a family ‘tree’
 If we model this natural occurring arrangement
in the computer using some kind of data
structure that reflects the real world realities of the
data and their implicit relationships, then we need
specialized algorithms for building, retrieving,
and otherwise accessing the data itself.
4
21
Examples of ‘Plain Facts’
 Consider a sequence of numbers – may be best
represented in an array. (a physical data structure)
 Assume we need to ‘search’ this sequence for a
number…
 An Algorithm processes this arrangement of data.
 If ordered and sufficiently large: binary search
 If unordered: sequential search
 Performance issues can be huge: either way.
 We may best ‘represent’ (model) a family and
children by a tree structure. (a logical data structure)
 But how might we best add members to the tree?
Search for members? Delete
members? What are
5
the Algorithms to process the Structure?
21
Data Structures are NOT Created Equal
 All have advantages and disadvantages.
 Worst ‘algorithm’ that processes data in one
data structure may be the best in other
case.
 Never poo-poo a data structure or a
seemingly inefficient algorithm.
6
21
Know: Definitions of terms below and have an example…
 Database
 Record
 Field
 If I should ask for a definition, please
recognize that an ‘example’ is NOT a
definition.
7
21
Object Oriented Programming
 Addressed two problems of procedural
languages:
 Lack of correspondence between the program
and the real world, (physical description vs
program realization) and
 The internal organization of the program.
 Most real world objects have properties.
 They provide certain actions or services on
data.
 They can carry out a task; they provide
“services” for clients.
8
21
Examples:
 Programs were (largely) ‘procedural.’
 Divided into functions, sections, paragraphs, ‘routines.’
 Data:
 either ‘local’ to one construct or
 ‘global’ to many.
 Global Data, No practical way to specify what
methods could access a variable and others
couldn’t.
 Result: for global data, all data – even data not needed
by particular procedures – was available to all (or most)
procedures.
 Recall: Call by Reference; Call by Value??
9
 Frequently a source of inadvertent
errors!!!
21
Objects:
 Encapsulate data (attributes, fields, properties)
with the operations (methods, member functions)
that operate on them.
 Objects have some very nice properties (to be
discussed throughout this course).
 Only methods within an object are allowed
access to data in the object. (in Java).

 An object is a real world representation of a
real ‘thing.’
 An object is an instantiation of a class.
10
21
Classes




A class is a generalization of many objects;
A class is a template; an abstraction.
Objects are merely ‘instances’ of classes.
Access these objects by referencing them.
(References are ‘addresses’ of the objects)
  We often create references to objects first
and then create the objects themselves.
 e.g.
 thermostat therm1, therm2; // references
 therm1 = new thermostat(); // creates the object
 therm2 = new thermostat(); // w therm1 and 2 pointing
// to their respective objects.
 Consider Listing 1.1 in your book as a Review:
11
21

































// bank.java // // demonstrates basic OOP syntax
class BankAccount
{
private double balance;
// account balance
public BankAccount(double openingBalance) // constructor
{
balance = openingBalance;
}
public void deposit(double amount)
// makes deposit
{
balance = balance + amount;
}
public void withdraw(double amount)
// makes withdrawal
{
balance = balance - amount;
}
public void display()
// displays balance
{
System.out.println ("balance=" + balance);
}
} // end class BankAccount
KNOW:
Instance variables; local variables; static (class) variables)
class BankApp
{
public static void main(String[] args)
{
BankAccount ba1 = new BankAccount(100.00);
// reference and acct object
System.out.print ("Before transactions, ");
ba1.display();
// display balance
ba1.deposit(74.35);
// make deposit
ba1.withdraw(20.00);
// make withdrawal
System.out.print ("After transactions, ");
ba1.display();
// display 12
balance
} // end main()
21
Let’s look at the two Classes:
// bank.java // // demonstrates basic OOP syntax
file name or application name or package
//
name…(more ahead)
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class BankAccount
{
private double balance;
// account balance
most object data is private
public BankAccount(double openingBalance) // constructor Constructor never has a ‘return type’
{
balance = openingBalance;
}
public void deposit(double amount)
// makes deposit: four methods (“services” provided
// to clients of this object.
{
balance = balance + amount;
}
public void withdraw(double amount)
// makes withdrawal // most methods (services) are
{
// public. When might they be private?
balance = balance - amount;
// What is the signature of an object?
}
public void display()
// displays balance
{
System.out.println("balance=" + balance);
}
13 scope terminators on
21 methods and classes.
} // end class BankAccount
// I require
Note: object ‘encapsulates’ everything about bank account objects; ‘ information hiding’ too.
…and the second class
class BankApp
{
public static void main(String[] args)
{
BankAccount ba1 = new BankAccount(100.00);
// create acct
// what does this statement do?
System.out.print("Before transactions, ");
// Explain what this REALLY is!
ba1.display();
ba1.deposit(74.35);
// display balance // Explain generically what this really is!
// make deposit // Explain generically what this really is!
ba1.withdraw(20.00);
// make withdrawal
System.out.print("After transactions, ");
ba1.display();
} // end main()
} // end class BankApp
// What is this statement? What does it do?
// display balance

 Note the scope terminators
Outputs:
Before transactions, balance=100
After transactions, balance=154.35
14
21
Inheritance and Polymorphism
 Had
 1. encapsulation
 2. information hiding
 What is encapsulation? Examples?
 What is information hiding? Examples?
 Who cares??
15
21
Inheritance and Polymorphism
 Inheritance
 Creation of a class (subclass, derived class, child class…) from a base
class (super class, parent, …)
 Add features in subclasses (derived classes); override features in
base class, etc.
  Inheritance is all about reuse!!
 Polymorphism
 Are different derived classes from a base class.
 Methods are said to be ‘polymorphic.’
 In practice, polymorphism usually refers to referencing a method (a
‘polymorphic’ method) that will execute a different method for different
objects of different derived classes all of which come from the base
class.
• Method name is same;
• Pointer to object is different.
 Significant facility to support extension, maintainability, and a number
of other design features.
  Polymorphism is all about design, extension, and reuse.
16
21
 You don’t need to worry about the
Java – C++ similarities and features.
17
21
Java Library Data Structures
 Super data structures, etc. in the Java API in
general.
 Data Structures found in java.util.* package.
 We will NOT use these.
 Do NOT use these for this course.
 Take a look at: Java2 Platform, Standard Edition,
version 1.6.2 Specification, at
http://java.sun.com/j2se/1.6.2/docs/api (the third
link on my web page under Course Syllabus and
Very Helpful Links.)
Do look this over and try some links, in case you
have never done so… 18
21
Study:
 Summary
 Go through this and study Questions too.
 Make sure you understand these. You will
see these again shortly. 
19
21
Questions?
20
21