Classes and Object

The most important principle of object-oriented programming is Classes and Objects.

A Class is a group of things(objects) which have similar properties or behaviour. For example - "Fruit" is a class. Why? because the word "Fruit" does not specify a particular fruit but all the types of fruits. In real life there is nothing called a "fruit", which means that if you go to a fruit seller and tell him that - I want to buy a fruit - he will ask you to specify which fruit exactly do you want to buy. All the examples of a "fruit" like Orange, Banana, Apple or any other are instances of simply examples of "fruit", that's why they are called "Objects". Objects are found in real world not the class. Classes are simply created to refer to all the similar objects easily.

The method invoked by an object in response to a message is determined by the class of the receiver. All objects of a given class use the same method in response to similar messages. Apple is an instance of a category or class of Fruit i.e. Apple is an instance of a class of fruits. The term fruit represents a class or category of all fruits. We interact with instances of a class but the class determines the behaviour of instances.

We can tell a lot about how Apple will taste by understanding how fruits taste. We know, for example, that Apple, like most fruits will have juice and will taste sweet.

In the real world there is this distinction between classes and objects. Real-world objects share two characteristics: They all have state and behavior. For example, dogs have state (name, color, breed, hungry) and behavior (barking, fetching, wagging tail). Students have state (name, student number, courses they are registered for, gender) and behavior (take tests, attend courses, write tests, party).

Basics of Objects and Classes

We move now from the conceptual picture of objects and classes to a discussion of software classes and objects. Objects are closely related to classes. A class can contain variables and methods. If an object is also a collection of variables and methods, how do they differ from classes?

Objects and Classes

Objects

In object-oriented programming we create software objects that model real world objects.Software objects are modeled after real-world objects in that they too have state and behavior. A software object maintains its state in one or more variables. A variable is an item of data named by an identifier. A software object implements its behavior with methods. A method is a function associated with an object.

Definition: An object is a collection of variables and related methods. An object is also known as an instance. An instance refers to a particular object. For e.g. My car is an instance of a car—It refers to a particular car. Allen is an instance of a Student. The variables of an object are formally known as instance variables because they contain the state for a particular object or instance. In a running program, there may be many instances of an object. For e.g. there may be many Student objects. Each of these objects will have their own instance variables and each object may have different values stored in their instance variables. For e.g. each Student object will have a different number stored in its StudentNumber variable.

Object Orientation As a Paradigm

It is claimed that the problem-solving techniques used in object-oriented programming is very close to the way we day-to-day problems. This is why the use of Object Oriented techniques has become very useful and popular in modern day programming languages like Java, VC#.Net etc. Let's try to understand how Object Oriented programming is close to our daily life with the help of an example.

Suppose you wanted to send a gift to a friend named James who lives in another city.To solve this problem you simply walk to your nearest gift shop run by, lets say, Scott. You tell Scott the kind of gift you want to send to James, your budget, along with the address of James. Once you are done with these things, you can be sure that the gift will be delivered.

Now, lets examine the steps used to solve your problem.

• You first found an appropriate agent (Scott, in this example) and you passed to this agent a message containing a request.

• It is the responsibility of Scott to satisfy the request.

• There is some method (an algorithm or set of operations) used by Scott to do this.

• You do not need to know the particular methods used to satisfy the request—such information is hidden from view. Ofcourse, you do not want to know the details, but on investigation you may find that Scott delivered a slightly different message to another gift shop in the city where your friend James lives. That person then passes another message to a subordinate who makes the final arrangement.The gift, along with yet another message, is passed onto a delivery person and so on.

This leads to our first conceptual picture of object-oriented programming: An object-oriented program is structured as community of interacting agents called objects. Each object has a role to play. Each object provides a service or performs an action that is used by other members of the community.  Messages and Responsibilities Members of an object-oriented community make requests of each other.
The next important principle explains the use of messages to initiate action:

Action is initiated in object-oriented programming by the transmission of a message to an agent (an object) responsible for the actions. The message encodes the request for an action and is accompanied by any additional information (arguments/parameters) needed to carry out the request. The receiver is the object to whom the message is sent. If the receiver accepts the message, it accepts responsibility to carry out the indicated action. In response to a message, the receiver will perform some method to satisfy the request.

There are some important issues to point out here:

• The client sending the request need not know the means by which the request is carried out. In this we see the principle of information hiding.

• Another principle implicit in message passing is the idea of finding someone else to do the work i.e. reusing components that may have been written by someone else.

• The interpretation of the message is determined by the receiver and can vary with different receivers. For example, if you sent the message “deliver gift” to a friend, he will probably have understood what was required and gift would still have been delivered but the method he used would have been very different from that used by the person in the example.

• In object-oriented programming, behaviour is described in terms of responsibilities.

• Client’s requests for actions only indicates the desired outcome. The receivers are free to pursue any technique that achieves the desired outcomes.

• Thinking in this way allows greater independence between objects.

• Thus, objects have responsibilities that they are willing to fulfill on request. The collection of reponsibilities associated with an object is often called a protocol.

Programming Paradigms

Programming Paradigms

Object-oriented programming is one of several programming paradigms. Other programming paradigms include the imperative programming paradigm (as exemplified by languages such as Pascal or C), the logic programming paradigm (Prolog), and the functional programming paradigm (exemplified by languages such as ML, Haskell or Lisp). Logic and functional languages are said to be declarative languages. We use the word paradigm to mean “any example or model”. This usage of the word was popularized by the science historian Thomas Kuhn.He used the term to describe a set of theories, standards and methods that together represent a way of organising knowledge—a way of viewing the world. Thus a programming paradigm is a "way of conceptualizing what it means to perform computation and how tasks to be carried out on a computer should be structured and organized".
We can distinguish between two types of programming languages: Imperative languages and declarative languages. Imperative knowledge describes how-to knowledge while declarative knowledge is what-is knowledge. A program is ”declarative” if it describes what something is like, rather than how to create it. This is a different approach from traditional imperative programming languages such as Fortran, and C, which require the programmer to specify an algorithm to be run. In short, imperative programs make the algorithm explicit and leave the goal implicit, while declarative programs make the goal explicit and leave the algorithm implicit.
Imperative languages require you to write down a step-by-step recipe specifing how something is to be done. For example to calculate the factorial function in an imperative language we would write something like:
public int factorial(int n) {
int ans=1;
for (int i = 2; i <= n; i++){
ans = ans i;
}
return ans;
}
Here, we give a procedure (a set of steps) that when followed will produce the answer.
12

Functional programming
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. Functional programming emphasizes the definition of functions, in contrast to procedural programming, which emphasizes the execution of sequential commands. The following is the factorial function written in a functional language called Lisp:
(defun factorial (n)
(if (<= n 1) 1 ( n (factorial (− n 1))))
)
Notice that it defines the factorial function rather than give the steps to calculate it.
The factorial of n is defined as 1 if n <= 1 else it is n factorial(n − 1)

Logic Programming
Prolog (PROgramming in LOGic) 2 is the most widely available language in the logic programming paradigm. It is based on the mathematical ideas of relations and logical inference. Prolog is a declarative language meaning that rather than describing how to compute a solution, a program consists of a data base of facts and logical relationships (rules) which describe the relationships which hold for the given application.
Rather then running a program to obtain a solution, the user asks a question. When asked a question, the run time system searches through the data base of facts and rules to determine (by logical deduction) the answer.
Logic programming was an attempt to make a programming language that enabled the expression of logic instead of carefully specified instructions on the computer. In the logic programming language Prolog you supply a database of facts and rules; you can then perform queries on the database.
The factorial function is written in prolog as two rules. Again, notice the declarative nature of the program.
fac(0,1).
fac(N,F) :− N > 0,
M is N − 1,
fac(M,Fm),
F is N * Fm.
To summarize:
• In procedural languages, everything is a procedure.
• In functional languages, everything is a function.
• In logic programming languages, everything is a logical expression (predicate).
• In object-oriented languages, everything is an object.

Object Oriented Programming

Oriented Programming
Introduction

Object Oriented Programming, also known as OOP, is a programming methodology in which a computer application is designed as things are in the real world. Object Oriented Programming (OOP) represents an attempt to make programs more closely model the way people think about and deal with the world. In the older styles of programming, a programmer who is faced with some problem must identify a computing task that needs to be performed in order to solve the problem. Programming then consists of finding a sequence of instructions that will accomplish that task. But at the heart of object-oriented programming, instead of tasks we find objects – entities that have behaviors, that hold information, and that can interact with one another. Programming consists of designing a set of objects that model the problem at hand.
With OOP, every object can handle data, get messages, and transfer messages to other objects. The objects will all act as independent units in their own right, and they will be responsible for carrying out a certain process. Software objects in the program can represent real or abstract entities in the problem domain. This is supposed to make the design of the program more natural and hence easier to get right and easier to understand.

What is Object Oriented Programming?
Object-Orientation is a set of tools and methods that enable software engineers to build reliable, user friendly, maintainable, well documented, reusable software systems that fulfills the requirements of its users. It is claimed that object-orientation provides software developers with new mind tools to use in solving a wide variety of problems. Object-orientation provides a new view of computation. A software system is seen as a community of objects that cooperate with with each other by passing messages in solving a problem.  An object-oriented programming language provides support for the following object oriented concepts:

1. Abstraction
2. Encapsulation
3. Inheritance
4. Polymophism
5.  Dynamic binding

Binary Sorted Tree : Source Code

1. #include
2. #include
3. #include
4. struct tree
5. {
6. int data;
7. tree *left;
8. tree *right;
9. }*root;
10.  
12. void main()
13. {
14. root=NULL;
15. int d;
16. void add();
17. void traverse(tree *);
18. tree* del(tree *,int);
19. int c;
20. do
21. {
22. printf("\nM A I N M E N U ");
23. printf("\n=====================");
24. printf("\n1. Add a node ");
25. printf("\n2. Display tree");
26. printf("\n3. Delete a node");
27. printf("\n4. Quit");
28. printf("\nSelect your choice ");
29. scanf("%d",&c);
30. if(c==1)
31. add();
32. else if(c==2)
33. traverse(root);
34. else if(c==3)
35. {
36. printf("\nEnter data to delete ");
37. scanf("%d",&d);
38. root=del(root,d);
39. }
40. }while(c!=4);
41. }
42.  
43. void add()
44. {
45. printf("\nAdd a node ");
46. tree *t,*prev;
47. tree *search(tree *,int);
48. t=(tree *)malloc(sizeof(tree));
49. printf("\nEnter data ");
50. scanf("%d",&t->data);
51. if(root==NULL)
52. {
53. root=t;
54. t->left=NULL;
55. t->right=NULL;
56. }
57. else
58. {
59. prev=search(root,t->data);
60. if(prev==NULL)
61. {
62. printf("\nNode already exists");
63. return;
64. }
65. else if(prev->data>t->data)
66. {
67. prev->left=t;
68. }
69. else
70. prev->right=t;
71. t->left=NULL;
72. t->right=NULL;
73. }
74. printf("\nNode Added ");
75. }
76.  
77. tree *search(tree *r,int d)
78. {
79. tree *prev;
80. while(r!=NULL)
81. {
82. if(r->data==d)
83. return NULL;
84. else if(r->data>d)
85. {
86. prev=r;
87. r=r->left;
88. }
89. else
90. {
91. prev=r;
92. r=r->right;
93. }
94. }
95. return prev;
96. }
97. void traverse(tree *r)
98. {
99. if(r==NULL)
100. return;
101. traverse(r->left);
102. printf("\n%d",r->data);
103. traverse(r->right);
104. }
105. tree *del(struct tree *root, int key)
106. {
107. tree *p,*p2;
108. if(!root)
109. return root;
110. if(root->data == key)
111. {
112. if(root->left == root->right){
113. free(root);
114. return NULL;
115. }
116. else if (root->left == NULL)
117. {
118. p = root->right;
119. free(root);
120. return p;
121. }
122. else if(root->right == NULL)
123. {
124. p = root->left;
125. free(root);
126. return p;
127. }
128. else
129. {
130. p2 = root->right;
131. p = root->right;
132. while(p->left)
133. p = p->left;
134. p->left = root->left;
135. free(root);
136. return p2;
137. }
138. }
139. if(root->data < key)
140. root->right = del(root->right, key);
141. else
142. root->left = del(root->left, key);
143. return root;
144. }

Binary Sorted Trees

A linked list,stack or a queue work fine for a small number of items, but when it comes to search for an item all the three data structures require a lot of time. Searching for an item's position requires comparing the value to be searched with each item in the list. Suppose there are 100 values in a linked list and the value that we want to find is stored in the last node, then it will take 100 comparisons to find the desired value.

Binary Sorted Tree

A binary sorted tree is a type of binary tree in which values are stored in respect to the root node. All the nodes having data less than the root's data are stored to the left of the root, while the nodes having a value more than the root's value are stored to the right of root. A binary tree can be used to store an ordered list of strings, or other items, in a way that makes both searching and insertion efficient. A binary tree used in this way is called a binary sort tree.

A binary sort tree has the following properties

For every node in the tree, the item in that node is greater than every item in the left subtree of that node, and it is less than or equal to all the items in the right subtree of that node. Take a look at the picture, you will see that all the nodes to the left of the root have smaller data while the right ones have larger data in comparison to the root.

The Advantage

Binary sorted trees offer a very useful advantage - When we traverse a binary sorted tree using the inorder method, all the values of the tree are accessed in ascending order. An inorder traversal of the tree will process the items in increasing order. For example, if an inorder traversal is used to print the items in the tree shown above, then the items will be in increasing order of their numerical value. The inorder traversal ensures that 1 will be printed before 2 and 2 will be printed before 3.Suppose that we want to search for a given item in a binary search tree. The item will be first compared with the root item of the tree. If they are equal,the search operation stops there. If the item we are searching for is less than the root item, then the value will be searched in the left subtree of the root ,the right subtree can be eliminated because it only contains items that are greater than or equal to the root. Similarly, if the item we are looking for is greater than the item in the root, then we only need to look in the right subtree. In either case, the same procedure can then be applied to search the subtree. Inserting a new item is similar: Start by searching the free for the position where the new item belongs. When that position is found, create a new node and attach it to the tree at that position.

Searching and inserting are efficient operations on a binary search tree, provided that the tree is close to being balanced.

A binary tree is balanced if for each node, the left subtree of that node contains approximately the same number of nodes as the right subtree. In a perfectly balanced tree, the two numbers differ by at most one. Not all binary trees are balanced, but if the tree is created randomly, there is a high probability that the tree is approximately balanced. During a search of any binary sort tree, every comparison eliminates one of two subtrees from further consideration. If the tree is balanced, that means cutting the number of items still under consideration in half.

Binary Tree

A Binary tree is a data structure that stores the data hierarchically in the form of a tree. Each node of a binary tree has 2 pointers usually called left and right. Additionally , the nodes can contain other types of data. For example, a binary tree of integers could be made up of objects of the following type:

struct tree {

int item; // The data in this node.

tree * left; // Pointer to the left subtree.

tree * right; // Pointer to the right subtree.

}



Binary Tree



The top most node of a tree is called the "root" node. A tree always starts from the root. The left and right pointers in a TreeNode can point to one,two or no nodes. A node that points to another node is said to be the parent of that node, and the node it points to is called a child. In the given picture , for example, node 7 is the parent of node 6, and nodes 5 and 11 are children of node 6. Not every linked structure made up of tree nodes is a binary tree.

A binary tree must have the following properties: There is exactly one node in the tree which has no parent. This node is called the root of the tree. Every other node in the tree has exactly one parent. Finally, there can be no loops in a binary tree. That is, it is not possible to follow a chain of pointers starting at some node and arriving back at the same node. A node that has no children is called a leaf or a terminal node. A leaf node has both the left and right pointers as null. In the standard picture of a binary tree, the root node is shown at the top and the leaf nodes at the bottom.

Consider any node in a binary tree. Look at that node together with all its descendents (that is, its children, the children of its children, and so on). This set of nodes forms a binary tree, which is called a subtree of the original tree. For example, in the picture, nodes 7, 2, and 6 form a subtree. This subtree is called the left subtree of the root. Similarly, nodes 5 and 9 make up the right subtree of the root. We can consider any non-empty binary tree to be made up of a root node, a left subtree, and a right subtree. Either or both of the subtrees can be empty. This is a recursive definition, matching the recursive definition of the TreeNode class.

Traversing a binary tree

There are three methods by which a binary tree can be traversed :

1. Preorder : In this type of traversal the root nodes is processed first following by left and right nodes. For example, in the above picture, between 2, 7 and 5, the preorder method will read 2 first, followed by 7 and 5.
2. Postorder : In a postorder traversal, the left subtree is traversed, then the right subtree, and then the root node is processed. In this method of reading 7,5 and 2 will be printed.
3. Inorder : In an inorder traversal, the left subtree is traversed first, then the root node is processed, then the right subtree is traversed. The output for the same set of nodes will be 7,2 and 5.