COMPUTER SCIENCE: YOU NEED TO KNOW DATA STRUCTURE...EXPLAINED
DATA STRUCTURES
Data Structure refers to data organization, management and storage format.
FIND OUT MORE ABOUT - WHAT IS AN ALGORITHM?
HOW CLASSES ARE IMPLEMENTED IN C++?
In OOD, the first step is to identify the components called objects; an object combines data and operation in a single unit, called encapsulation.
In C++, the mechanism that allows you to combine data and operations in a single unit is called a class. A class is a collection of a fixed number of components. The components of a class are called the members of the class.
syntax to define class:
class classIdentifier
{
class members list
};
* If a member of a class is a variable, you declare it. In the definition of a class, you cannot initialize a variable when you declare it.
In C++, class is a reserved word and it defines only a data type. No memory is allocated. It announces the declaration of a class.
**There is a semicolon(;) after the right brace. The semicolon is part of the syntax. A missing semicolon will result in a syntax error.
The members of a class are classified into 3 categories: private, public and protected, called member access specifiers.
FACTS on private & public members of a class:
By default, all members of a class is private
If a member of a class is private, you cannot access it outside the class
A public member is accessible outside the class
**In C++, private, protected and public are reserved words.
CONSTRUCTORS
C++ does not automatically initialize variables when they are declared. When an object is instantiated, there is no guarantee that the data members of the object will be initialized.
To guarantee that the instance variables of a class are initialized, use constructors.
There are 2 types of constructors: With Parameters & Without Parameters.
Constructor properties:
The name of the constructor is the same as the name of the class
Even though Constructor is a function, it has no type. It is neither a value returning function nor a void function.
A class can have more than one constructor. However, all constructors of a class have the same name.
If a class has more than one constructor, the constructor must have different formal parameter lists.
Constructors execute automatically when a class object enters its scope.
UML (Unified Modeling Language Diagrams)
A class and its members can be described graphically using a notation known as UML.
The top box contains the name of the class. The middle box contains data members and their data types. The last box contains the member function name, parameter list and the return type of the function. +(plus) sign in front of the member indicates that this member is a public member. -(minus) sign indicates that this is a private member. The symbol # before the member indicates that the member is a protected member.
VARIABLE (OBJECT) DECLARATION
Once a class is defines, you can declare variables of that type. A class variable is called a class instance or class object in C++.
A class can have both types of constructors: with or without parameters.
For example:
clockType myClock;
The statement above declares myClock to be an object of type clockType. In this, the default constructor executes and the instance variables of myClock are initialized to 0.
**If you declare an object and want the default constructor to be executed, the empty parentheses after the object name are not required in the object declaration statement.
If you accidentally include empty parentheses, the compiler generates syntax error messages.
clockType myClock(); //illegal object declaration
ACCESSING CLASS MEMBERS
Once an object of a class is declared, it can access the members of the class. The general syntax for an object to access a member of a class is:
classObjectName.memberName
In C++, the dot . (period) is an operator called the member access operator called the member access operator.
clockType myClock;
clockType yourClock;
myClock,setTime (5, 2, 30)
myClock.printTime (yourClock))
.
.
.
In the first statement, myClock.setTime(5, 2, 30); , the member function setTime is executed. The values 5, 2 and 30 are passed as parameters to the function setTime and the function uses these values to set the values of the 3 instance variables hr, min and sec of myClock to 5, 2, 30, respectively. Simlarly, the second statement executes the member function printTime and outputs the contents of the three instance variables of myClock.
In the third statement, the member function equalTime executes and compares the three instance variables of myClock to the corresponding instance variables of yourClock. Because in this statement equalTime is a member of the object myClock, it has direct access to the three instance variables of myClock. So it needs one more object, which in this case is yourClock, to compare. This explains why the function equalTime has only one parameter.
The object myClock and yourClock can access only public members of the class. Thus, the following statements are illegal because hr and min are declared as private members of the class clockType and cannot be accessed by the objects myClock and yourClock.
myClock.hr = 10; //illegal
myClock.min = yourClock.min; //illegal
IMPLEMENTATION OF MEMBER FUNCTIONS
When we define clockType, we include only function prototype for the member functions. For these functions to work properly, we must write the related algorithms. One way to implement these functions is to provide the function definition rather than the function prototype in the class itself.
Next, we will write the definitions of the functions for setTime, getTime, printTime, incrementSeconds, equalTime. Because the identifiers setTime, printTime and so on are local to the class, we cannot reference them directly outside the class.
To reference these identtifiers, we use the scope solution operator, :: (double colon). In the function definition's heading, the name of the function is the name of the class, followed by the scope resolution operator, followed by the function name.
Example of function setTime:
void clockType::setTime(int hours, int minutes, int seconds)
{
if (0 <= hours && hours <24)
hr = hours;
else
hr = 0;
if (0<= minutes && minutes < 60)
min = minutes;
else
min = 0;
if (0 <= seconds && seconds < 60)
sec = seconds;
else
sec = 0;
}
Based on the given program above, the definition of the function setTime checks for the valid value of hours, minutes and seconds. If these values are out of range, the instance variables hr, min and sec are initialized to 0.
Suppose myClock is an object of type clockType. The object myClock has 3 instance variables.
myClock.setTime (3, 48, 52);
In the code above, setTime is accessed by the object myClock.
** Therefore, the 3 variables - hr, min & sec - to which the body of the function setTime refers, are the 3 instance variables of myClock. Thus, the values of 3, 48 and 52 which are passed as parameters in the preceding statement are assigned to the 3 instance variables of myClock by the function setTime.
DATA ABSTRACTION, CLASSES & ABSTRACT DATA TYPES
For the car we drive, most of us want to know how to start the car and drive it. Most people are not concerned with the complexity of how an engine works.
By separating the design details of a car's engine from its use, the manufacturer helps the driver focus on how to drive the car.
*In norm, we are concerned only how to use certain items, rather than with how they work.
Separating the design details (that is, how a car engine works) from its use is called abstraction. In other words, abstraction focuses on what the engine does and not on how it works.
***Abstraction is the process of separating the logical properties from the implementation detail
Driving a car is a logical property; the construction of the engine constitutes the implementation details.
Abstraction can also be applied to data. Earlier we defined a data type clockType. The data type clockType has three instance variables and the following basic operations:
Set the time
Return the time
Print the Time
Increment the time by one second
Increment the time by one minute
Increment the time by one hour
Compare two times to see whether they are equal
The definition of clockType and its basic operations are the logical properties; storing clockType objects in the computer. The algorithm to perform these operations, are the implementation details of clockType.
Abstract Data Type (ADT): A data type that separates the logical properties from the implementation details.
Like any other data type, ADT has 3 things associated with it: The name of the ADT, called the type name; the set of values belonging to ADT, called the domain; & the set of operations on the data.
Below is the clockType ADT example:
dataTypeName
clockType
domain
Each clockType value is a time of day in the form of hours, minutes, and seconds.
operations
Set the time
Return the time
Print the Time
Increment the time by one second
Increment the time by one minute
Increment the time by one hour
Compare two times to see whether they are equal
*To implement ADT, you must represent the data and write algorithms to perform the operations.
***In C++, classes were specifically designed to handle ADTs.
You can define a list as an ADT as follows:
dTypeName
listType
domain
Each element of a listType is a set of, say at most 1000 numbers.
operations
Check to see if the list is empty
Check to see if the list is full
Search the list for a given item
Delete an item from the list
Insert an item from the list
Sort the list
Print the list
Comments
Post a Comment