Chapter1

EE441 Data Structures(Fall 2007): 

EE441 Data Structures (Fall 2007) Özgür B. Akan Department of Electrical & Electronics Engineering Middle East Technical University akan@eee.metu.edu.tr www.eee.metu.edu.tr/~akan

Administrative Details: 

Administrative Details Instructor (Section I): Özgür B. Akan Office: EC-102 Email: akan@eee.metu.edu.tr Course Web: Follow http://www.eee.metu.edu.tr/~akan/ Office Hours: Anytime!

Course Outline (Tentative): 

Course Outline (Tentative) Introduction to OOP Abstract Data Types, Classes & Objects Arrays, Pointers Complexity of algorithms Stacks Queues Dynamic memory management Linked Lists Trees, B-Trees Sorting and Hashing Algorithms

Chapter IIntroduction to OOP: 

Chapter I Introduction to OOP

Object-Orientation: 

Object-Orientation We perceive the world as a world of objects You look around and see a chair, a table, a person, and the objects are related in one way or another. The object-oriented technique tries to imitate the way we think A system developed by using the object-oriented technique can be seen as a system consisting of a number of objects which cooperate to solve a task.

A Shift in Thinking … ?: 

A Shift in Thinking … ? A fundamental change in approach: Structured programming reflects the way that computers process information (e.g. sequential execution, conditional branching and repetition). Hence, a problem is tackled by decomposing it into a flow of operations, data is of secondary importance. we do not naturally think this way  dealing with complex problems is difficult and bugs may not be obvious OO approach attempts to find a methodology and language that reflect the way that people think about problems. In fact, it appears that people tend to think in terms of things not operations. In OO development we refer to these "things" as objects

Structured vs. OO Programming: 

Structured vs. OO Programming STRUCTURED PROGRAMMING:

Structured Programming: 

Structured Programming Using function Function & program is divided into modules Every module has its own data and function which can be called by other modules.

A New Approach: 

A New Approach Software developers sought a new approach for developing software. One that would . . . Produce highly maintainable software, where changing one part of a program would not break the rest Produce reusable software, where similar programming tasks could share common elements, without having to reinvent the wheel Make it easier to tackle complex programming problems and reduce the chances of introducing bugs into programs. These ideas led to the development of object-oriented (OO) software development.

OO Approach: 

OO Approach OO development starts by thinking about the problem, and not about the program that will implement the solution In the real world, "things" have characteristics and behavior. e.g. a car is a "thing" that has a make, model, registration number and can accelerate, steer, brake, change gear etc. We think about the objects involved in the problem, their characteristics (attributes) and behaviors An OO language allows us to model these attributes and behaviors, and construct a solution to the problem from these objects

OO Programming: 

OO Programming A design and programming technique Objects have both data and methods Objects of the same class have the same data elements and methods Objects send and receive messages to invoke actions Key idea in object-oriented: The real world can be accurately described as a collection of objects that interact with each other Pure OO Languages: Smalltalk, Eiffel, Actor, Java Hybrid OO Languages: C++, Object-Pascal

Structured vs. OO Programming (Recap.): 

Structured vs. OO Programming (Recap.) STRUCTURED PROGRAMMING:

OO Programming: 

OO Programming

Some OOP Terminology: 

Some OOP Terminology object - usually a person, place or thing (a noun) method - an action performed by an object (a verb) class - a category of similar objects (such as automobiles) Class does not hold any values of the object’s attributes

Example of an Object Class: 

Example of an Object Class Attributes: manufacturer’s name model name year made color number of doors size of engine etc. Methods: Define data items (specify manufacturer’s name, model, year, etc.) Change a data item (color, engine, etc.) Display data items Calculate cost etc. Example (Automobile):

Examples of Objects: 

Examples of Objects What the objects are, will be determined by the problem domain: In a banking application: customers, accounts, sums of money etc. In a library application: books, journals, CD-Roms, members, etc. In a communication network simulator: network nodes, queues, channels, links, packets etc. (e.g., check http://www.isi.edu/nsnam/ns )

Why OOP?: 

Why OOP? Save development time (and cost) by reusing code once an object class is created it can be used in other applications Easier debugging classes can be tested independently reused objects have already been tested

Design Principles of OOP: 

Design Principles of OOP Three main design principles of Object-Oriented Programming(OOP): Encapsulation Polymorphism Inheritance

Encapsulation: 

Encapsulation Encapsulation: to design, produce, and describe software so that it can be easily used without knowing the details of how it works. Also known as data hiding Only object’s function which perform parts of the objects behavior can modify information in the object. An analogy: When you drive a car, you don’t have to know the details of how many cylinders the engine has or how the gasoline and air are mixed and ignited. Instead you only have to know how to use the controls.

Polymorphism: 

Polymorphism Polymorphism: the same word or phrase can mean different things in different contexts Analogy: in English, bank can mean side of a river or a place to put money Function Overloading: The operation of one function depends on the argument passed to it. Example: Fly(), Fly(low), Fly(150)

Inheritance: 

Inheritance Inheritance: a way of organizing classes Term comes from inheritance of traits like eye color, hair color, and so on. Classes with properties in common can be grouped so that their common properties are only defined once. Superclass: inherit its attributes & methods to the subclass(es). Subclass: inherit all its superclass attributes & methods besides having its own unique attributes & methods.

An Inheritance Hierarchy: 

An Inheritance Hierarchy Vehicle Automobile Motorcycle Bus Sedan Sports Car School Bus Luxury Bus Superclass Subclasses