```COP 3540 Data Structures with OOP
Overview: Chapter 1
1
21
Important Notice
 I will cover several slides (but not all) in these sets
of slides. I will outline those that need
elaboration.
 You are responsible for studying and knowing all
the slide materials and the text materials.
 Exams and short quizzes will be taken largely
from these slides and topics brought up in class.
2
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.
3
21
Examples of Some Data Structures
 Many data structures:








Arrays
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
4
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.
5
21
Examples of ‘Plain Facts’ Example 1
 Consider a sequence of numbers
 may be best represented in an array.
 We need to ‘search’ the array for a number.
 An Algorithm processes this arrangement of data.
 If ordered and sufficiently large: binary search
 If unordered: sequential search is our only option.
• (Performance issues can be huge: either way.)
6
21
Examples of ‘Plain Facts’ Example 2
 We may best ‘represent’ (model) a family and children by a
tree structure. (a logical data structure)




How do we add members to such a tree?
How do we Search?
How to delete when there are ‘descendents’
How do we best Add to a large tree?
 We need very specific Algorithms to process this structure.
7
21
Data Structures are NOT Created Equal
 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!
8
21
Know: Definitions of terms below and have an example…
 Database
 Record
 Field (attribute)
that an ‘example’ (drawing or text) is NOT a
definition.
 A definition must be very unambiguous.
9
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)
 The internal organization of the program.
 Most real world objects have properties (attributes).
 Objects provide certain actions or services on data
for clients.
 They can carry out a task 10if sent a ‘message.’
21
Examples:
 Programs were (largely) ‘procedural.’
 Divided into functions, sections, paragraphs, ‘routines.’
 Data:
 either ‘local’ to one construct (function or procedure) or
 ‘global’ to many.
 Global Data, No practical way to specify methods that can
access a variable and those that cannot.
 Result: for global data, all data – even data not needed by particular
procedures – was available to all (or most) procedures.
 COBOL; Can do in C and others too, if not careful
  Recall: Call by Reference; Call by Value??
 Frequently a source of inadvertent errors!!!
 Know these!!!

11
21
Objects:
 Encapsulate data (attributes, fields, properties)
 and
 Encapsulate operations (methods, member functions)
that operate on the data.
data in that object. (in Java)
 (if attributes are given visibility ‘private.’)

 An object may be viewed as a real world
representation of a real ‘thing’ or ‘noun.’
 An object is an instantiation of a class.
12
21
Classes
 A class is a generalization of many objects;
 A class is a template; an abstraction.
 Objects are merely ‘instances’ of classes, but these are
real and these are what we process!
 We 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 your13book as a Review:
21
 A good ‘review’ is undertaken in the following
code… 
14
21




// bank.java
// demonstrates basic OOP syntax
class BankAccount
{


















// account balance why private? What kind of variable is this? Why?
// Who has ‘access’ to balance?
public BankAccount ( double openingBalance) // constructor
{
balance = openingBalance;
// What is a Constructor?
}
public void deposit ( double amount)
// makes deposit
{
balance = balance + amount;
// What is amount called? (formally)
// Is this Call by Reference or Call by Value?
} // end deposit
// Note ‘scope terminator’
public void withdraw(double amount)
// makes withdrawal
{
balance = balance - amount;
}
public void display()
// displays balance
{
System.out.println ("balance=" + balance);
KNOW:
}
Instance variables; local variables; static (class) variables)
} // end class BankAccount

class BankApp












private double balance;
{
// Note: this class is still in the same file….
// Where does execution start?
public static void main(String[] args)
{
BankAccount ba1 = new BankAccount(100.00); // reference and acct object; Other ways to do this?
System.out.print ("Before transactions, ");
ba1.display();
// display balance
What is going on here? What do you call this?
ba1.deposit(74.35);
// make deposit
What is the 74.35 called?
ba1.withdraw(20.00);
// make withdrawal
System.out.print ("After transactions, ");
15
ba1.display();
// display balance
} // end main()
} // end class BankApp
21
Let’s look at the two Classes:
// bank.java // // demonstrates basic OOP syntax
file name or application name or package
//
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class BankAccount
{
private double balance;
// account balance
most object data is private
public BankAccount(double openingBalance) // constructor Constructor never has a ‘return type’
{
// in Javadoc for @params put None.
balance = openingBalance;
}// end constructor
public void deposit(double amount)
// makes deposit: four methods (“services” provided
// to clients of this object.
{
balance = balance + amount;
}// end deposit
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?
}// end withdraw
public void display()
// displays balance
{
System.out.println("balance=" + balance);
}//end display()
16 scope terminators on methods and classes. 21
} // 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
17
21
Inheritance and Polymorphism
 1. encapsulation
 2. information hiding
 What is encapsulation? Examples?
 What is information hiding? Examples?
 Who cares??
18
21
Inheritance and Polymorphism
 Inheritance involves
 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 (and thus method body) is different.
 Significant facility to support extension, maintainability, and a number
of other design features.
  Polymorphism is all about design, extension, and reuse.
19
21
Study:
 Summary
 Go through these materials and the study
questions too.
 Make sure you understand these. You will see
these again shortly. 
20
21
Questions?
21
21
```