CHAPTER 1: INTRODUCTION 1
Main contents
• Data and Information
• Representation of Data
• Data Type
• Data Structure
• Object-Oriented Programming
2
11
Data and Information
• Data is the basic entity or fact that is used in a calculation or
manipulation process.
• Data is commonly processed by some stages.
• Unprocessed data or raw data is a collection of numbers, characters.
• Raw data may be considered as an input of a stage and processed
data is the output of the stage.
3
11
Data and Information
4
11
Data and Information
• Data are raw facts without context, whereas Information is
data with context.
• Data are an abstraction of Information
in a problem-solving system.
• Data require interpretation to become an Information.
5
11
How does a program work?
Algorithms
Data
6
11
Representation of Data
• Almost all the high-level languages allow data to
be represented in computer memory of mainly two types:
✓ Numerical data
✓ Alphanumerical data
7
11
Representation of Data
• Numerical data are classified into two types:
✓ Integer
✓ Floating-point
8
11
Representation of Data
Alphanumerical data are classified into two types:
- Character: alphabets, digits, special characters and white spaces
- String: a sequence of characters may consist of any number and any
combination of characters. The characters may be alphabets, digits, special
characters and white spaces.
9
11
Data types
▪ A data type refers to the type of data that variables hold.
▪ The C language supports three classes of data types:
- Primary or Basic data types
- Derived data types
- User-defined data types
10
11
Data types
11
11
Data types - Example
• Example of Integer:
4, 6, -12, …
• Example of Array:
A list of values of interest in each month of this year.
• Example of Struct:
Information of a student (name, age, class, program, GPA)
12
11
About data structures and algorithms
13
11
About data structures and algorithms
• Data structures and algorithms are two essential concepts in computer science.
• Data structures are the objects generated to organize, store and retrieve data.
• Algorithms are a set of instructions to perform specific task by using the data
structures
14
11
About data structures and algorithms
15
11
Data Structure
• Data Structure is the representation of the logical relationship
between individual elements of data.
• Data Structure is defined as a mathematical or logical model of
organizing the data items into computer memory to use efficiently.
• Data Structure refers to the study of data and representation of data
objects within the program.
16
11
Data Structure - Purposes
• Organizing the data: How data items are organized in the main memory.
• Accessing methods: How data items can be accessed.
• Specifying the degree of associativity: How data items are interrelated.
• Processing alternatives for data: How many different ways are there in which these data
items can be processed.
17
11
Classifications of Data Structure
18
11
Primitive data structure
• Primitive data structure is a fundamental type of data structure.
• Primitive data structure allows you to store only single data type values.
• Primitive data structure can be manipulated or operated by the machine instructions.
19
11
Non-primitive data structure
• A type of data structure stores the data of different types in a single entity.
• Cannot be manipulated or operated by the machine instructions.
• A group of homogeneous or heterogeneous data items.
• Non-primitive data structures are derived from the primitive data structure.
20
11
Non-primitive data structure Every data item
attaches to many
other data items in
specific ways to
reflect relationships
Every data item
is related to its
previous and
next data items
21
11
Static and Dynamic data structure
• Static data structure: once memory space
is allocated it cannot be extended.
• Dynamic Data Structure is another kind of
data structure, which can be extended or
shrink during the execution.
22
11
Operations can be performed on data structure
23
11
Applications of Data Structure
Note: Different kinds of data structures are suitable for different kinds of application
24
11
Example of Data Structure and algorithm
Data structure: Select a data structure to store the amount of money that you
spent each month last year.
Algorithm: Find the max amount and the average amount that you’ve spent.
25
Object-oriented programming (OOP)
• Object-oriented programming (OOP) is a computer programming model that organizes
software design around data, or objects, rather than functions and logic.
• An object is a data structure, combined with the operations pertinent to that structure.
• Most object-oriented languages (OOLs) define objects through the use of a class.
26
Object-oriented programming (OOP)
• Object-oriented programming (OOP) is a computer programming model that organizes
software design around data, or objects, rather than functions and logic.
• An object is a data structure, combined with the operations pertinent to that structure.
• Most object-oriented languages (OOLs) define objects through the use of a class.
27
Object-oriented programming (OOP)
Class
Objects
28
Abstract Data Types
• Proper planning is essential to successful implementation of programs
• Typical design methodologies focus on developing models of solutions
before implementing them
• These models emphasize structure and function of the algorithms
used
• Initially our attention is on what needs to be done, not how it is done
29
Abstract Data Types (cont.)
• Define program behavior in terms of operations to be performed on data
• The details will emerge as we refine the definitions of the operations
• Only then will implementation of those operations be carried out
• As part of this implementation, we must choose appropriate data structures
• A data structure is a technique of storing and organizing data so it can be used efficiently
30
Abstract Data Types (continued)
• In our program models, data structures are described by abstract data types (ADTs)
• An Abstract Data Type (ADT) describes the data objects, which constitute the data
structure and the fundamental operations supported on them.
• ADTs are defined indirectly, in terms of operations to be performed rather than in terms
of its inner structure
• ADTs can then be implemented through class definitions in an object-oriented language.
31
Abstract Data Types: Examples
• A stack is a last-in first-out (LIFO) linear structure where items can only
be added and removed from one end
• Operations on this stack ADT might include:
➢PUSH – add an item to the stack
➢POP – remove the item at the top of the stack
➢TOP – return the value of the item at the top of the stack
➢EMPTY – determine if the stack is empty
➢CREATE – create a new empty stack PUSH POP
A Simple Stack Representation
32
Abstract Data Types: stacks
33
Main principles in OOP
Data
encapsulation
Inheritance
OOP
Polymorphism
Fiend
relationship
34
Data encapsulation
• A class is a template which implements the ADT defining the objects that the class creates.
• Within a class, the data elements are called data members, and member functions.
• The combination of data members and methods in a class is referred to as data
encapsulation
35
Data encapsulation
• This approach has several advantages:
✓The strong link between data and operations better mimics real-world behavior, on which program
models are based
✓Errors in implementation are confined to the methods of a particular class in which they occur,
making them easier to detect and correct
✓Details of the implementation of the object can be hidden from other objects to prevent side effects
from occurring.
• This last point illustrates the principle of information-hiding.
• Our use of an object is based on what it does for us, not how it goes about doing it.
• So, an object can be looked at as a black box, with specific user-available methods and a
well-defined behavior.
36
Inheritance
• Inheritance is a technique of reusing existing class definitions to derive new classes
• These new classes (called derived classes or subclasses or child classes) can inherit the
attributes and behavior of the pre-existing classes (called base classes or super classes or
parent classes)
• This relationship of classes through inheritance forms a hierarchy, which can be
diagrammed
37
Inheritance
• Information hiding can be extended through this hierarchy by the access the base
class allows the derived class(es)
• Derived classes can then add, delete, & modify methods and data members in their
own definitions (known as overriding).
• The amount of access, and level of modifications, are controlled by specifying public,
protected, or private in the derived class header
38
Inheritance
The amount of access, and level of modifications, are controlled by
specifying public, protected, or private in the derived class header.
derived class
(public inheritance)
Base
class
derived class
(protected inheritance)
derived class
(private inheritance)
39
Polymorphism
Polymorphism is the ability, in many OOLs, to create objects of different types that
respond to method calls having the same name
They differ in that they respond according to type-specific behavior
Which method is called depends on the time at which the decision is made about the call
This decision is referred to as binding, and can occur in different ways
◦ Static binding determines the function call at compile time
◦ Dynamic binding delays the decision until run time
40
Polymorphism
41
The Standard Template Library (STL)
▪ While C++ is a powerful language in its own right, recent additions have added even more
capabilities
▪ Of these, perhaps the most influential is the Standard Template Library (STL)
▪ It provides three generic entities: containers, iterators, and algorithms, and a set of classes that
overload the function operator called function objects
▪ It also has a ready-made set of common classes for C++, such as containers and associative arrays
▪ These can be used with any built-in type and with any user-defined type that supports some
elementary operations
42
The Standard Template Library (cont.)
Containers
◦ Designed to hold objects of the same type
◦ Containers are implemented as template classes whose methods specify operations on the
data in the structures as well as the structures themselves
◦ A number of these methods are common to all containers, while some are more specific to
the container they are defined in
◦ The data stored in containers can be of any type and must supply some basic methods and
operations
◦ This is especially necessary if pointers are involved
43
Containers in C++
➢ Vector
➢ List
➢ Queue (Priority Queue)
➢ Deque
➢ Stack
➢ Map/Multimap
➢ Set/MultiSet
►
The Standard Template Library (cont.)
Iterators
◦ An iterator is an object that accesses the elements of a container
◦ The STL implements five types of iterators
◦ Input iterators, which can read a sequence of values
◦ Output iterators, which can write a sequence of values
◦ Forward iterators, which can be read, written to, or moved forward
◦ Bidirectional iterators, which behave like forward iterators but can also move backwards
◦ Random iterators that can move freely in any direction at one time
◦ Essentially, an iterator is a generalized pointer, and can be dereferenced and
manipulated like a pointer
◦ These capabilities make iterators a major feature that allows the generality of
the STL
45
The Standard Template Library (cont.)
Algorithms
◦ About 70 generic functions, known as algorithms, are provided in the STL
◦ These perform operations such as searching and sorting
◦ Each is implemented to require a certain level of iterator (and therefore will
work on any container that provides an interface by iterators)
◦ Algorithms are in addition to the methods provided by containers, but some
algorithms are implemented as member functions for efficiency
46
Algorithms in C++
➢ max_element(), max_element(iterl, iter2)
➢ min_element(), min_element(iterl, iter2)
➢ sort(), sort(iterl, iter2)
➢ random_shuffle() random_shuffle(iterl, iter2)
➢ binary_search()
➢ for_each()
➢ find()
►
Example
Design an algorithm to enter the coordinates of three vertices in a
triangle and calculate the perimeter and the area of that triangle.
►
Summary
• Data is the basic entity or fact that is used in the calculation or manipulation process.
• Data are raw facts without context, whereas information is data with context.
• Data Structure is defined as a mathematical or logical model of the particular
organization of data items in computer memory so that it can be used efficiently.
• An Abstract Data Type (ADT) describes the data objects, which constitute the data
structure, and the fundamental operations supported on them.
• The main principles in OOP include Abstraction, encapsulation, inheritance, and
polymorphism
52
Exercises
53
Exercises
On Page 1.5
See Table 1.2 on Page 1.7
On Page 1.6
54
55