Deleted.
SEARCHING & SORTING
Searching and sorting are fundamental operations, which are frequently used in many applications. Identifying a particular item or a record among a set of elements or records is called as searching. If the item or record is found then search is said to be successful; otherwise unsuccessful. Sorting is a process of arranging a set of elements or records in a specific way. In sorting the elements are arranged in increasing or decreasing order of their key values. In this article you can read about various searching and sorting techniques. Searching Notations Before the main article starts, you should read some terms, which are frequently used in searching process. A table or a file is a group of records, each record having one or more fields, known as keys. These keys are used to differentiate among different records. For instance we may regard a telephone directory as a file of records, each record having three fields : name, address and phone number. The key may be either the person name or the phone number. In some other applications one may desire the phone number at a particular address, so this field too could be the key. We can say that there is a strong relationship between the key and the record. The association between the key and the record may be simple or complex. In the simplest form, a key may be contained within the record at a specific offset from the start of the record. Such a key is called an internal key or an embedded key as shown in figure-1(a). On the other hand, in the complex form, there may be separate table of keys that include pointers to the records. Such keys are called external keys as shown in figure-1(b). For the sake of simplicity we will adopt the rule throughout this article, which is given a key there should be at most one record have the same key value. Such a key is called a primary key. For example, the telephone number is a primary key because there can not be two records with the same telephone number. However since any field of a record can serve as the key in a particular applications, keys need not be unique. For example, if we are using name as a key in a telephone directory, there may be more than one person with the same name in the directory, such a key is called a secondary key. Figure 1 When we search a table or a file for a specific record, it will be a time-consuming action in a program and when we write searching techniques we must consider this point. Before writing any searching techniques we must see how the records are arranged. A table or file may be organized as an array of records, a linked list, a tree or even a graph. If there are large number of records then it will be necessary to store the records in the file on some secondary media, which are external to the computer memory, such as tape or disk. This case is called external searching. On the other hand if the records to be searched are stored entirely within the computer memory, it is called internal searching. In this article we will study internal searching in detail. Three are three basic searching techniques – sequential, binary and hash searching. Let us study these searching techniques in details. Sequential (Linear) Searching
Introduction
A general searching algorithm accepts two arguments – the target ‘item’ and the list to be searched. A list may contain ‘n’ number of records. For the sake of simplicity each record is assumed to consist of a key field only. Our goal is to find an item in the list whose key is equal to the ‘item’. The searching algorithm will indicate whether it has found ‘item’ or not. If the ‘item’ is found in a contiguous list then it returns the index of the list where the ‘item’ is found or in case of a linked list it returns any positive value, say 1. Unfortunately if the ‘item’ was not found, it returns a value –1.
Basic Searching Techniques
The simplest form of a search is the sequential searching or linear searching. In sequential searching we search for a target ‘item’ in the list by examining the records in the list one by one. Initially the process starts with the first record. If this first comparison results in false then the algorithm proceeds to the next record. This process continues until either the desired record is found or the list is exhausted. Thus we can say that in sequential search we start at one end of the list and scan down it until the desired item is found or the other end is reached. This technique is suitable for a table or a linked list.
Let us assume that ‘A’ is an array of 10 keys; A[0], A[1], through A[9] and we have following list of numbers:
A[0] |
A[1] |
A[2] |
A[3] |
A[4] |
A[5] |
A[6] |
A[7] |
A[8] |
A[9] |
28 |
24 |
36 |
29 |
14 |
75 |
80 |
31 |
60 |
49 |
And let we want to find the item ‘75’. Initially we will start searching with the very first element of the list, that is A[0]. If item ‘75’ is not found at A[0] then we will take next element, that is A[1], as shown in figure-2(a) and compare it with the item ‘75’. If item ‘75’ is not found at A[0] then we will take next element as shown in figure-2(b). And this process goes on until the item is found or the list gets exhausted. Figure-2 shows that the item is found at 6th location.
Here is the sequential search algorithm.
Algorithm : SequentialSearch
SequentialSearch(a, n, item)
Here ‘a’ is an array of ‘n’ number of elements and ‘item’ represents the item to be searched in array ‘a’
- Step-1 : Initialize i = 0
- Step-2 : Repeat through step-4 while (i < n)
- Step-3 : Compare a[i] and item
- If (a[i] == item) then return (i) and go to step-6
- Step-4 : Increment the value of ‘i’ as: i = i+1
- Step-5 : If item not found then just print a message – “Item not found” and return (-1)
- Step-6 : Exit
The C implementation of this sequential search algorithm is as:
Implementation : SequentialSearch
SequentialSearch(int a[], int n, int item)
{
int i;
for (i = 0; i < n; i++)
{
if (a[i] == item)
return (i);
}
return (-1);
}
This function examines each element in turn, using the for loop; upon finding one that matches the search argument, its index is returned. Unfortunately if there is no such element, it returns –1. Thus this algorithm checks each entry in turn. When the values in the array ‘a’ are not distinct then this function will return the first index ‘i’ of the array ‘a’ which is equal to the ‘item’.
Figure 2
Sequential Search in Linked List
We can also store a table as a linked list. Let us assume that the table is organized as a linear linked list point to by an external pointer variable ‘first’ and linked by a pointer field ‘link’. For this we will assume the type declaration of the node of the linked list is as:
struct Node
{
int data;
struct Node *link;
};
typedef struct Node Node;
Node *first;
A version of sequential search for linked list is equally easy , as follows:
SequentialSearch(Node *first, int item)
{
while (first != NULL)
{
if (first->data == item)
return (1);
first = first->link;
}
return (-1);
}
As far as the comparisons of keys is concerned, both versions are same, but the running time of the two versions may be different due to their implementation. So whenever we will compare this searching technique with another method we will consider the concept of number of keys of comparisons.
Analysis of Sequential Search
Initially when we start searching we really do not know how many times the loop will be iterated because the number of comparisons required for a successful search is not fixed. It all depends upon the position of item within the array. And we have no way to know in advance whether or not the search will be successful. The target ‘item’ will be the first element in the array, the last or some where between. If it is the first element then only one comparison is sufficient and if it is the last element then ‘n’ comparison are required, where ‘n’ is the length of the list. If the search is unsuccessful then ‘n’ comparisons are required. Then we can say that the best time for successful search is ‘1’ and the worst case is ‘n’ comparison.
And in general if it is assumed that if the search is successful, the average behavior of the algorithm is calculated by adding the number of comparisons needed for all successful search and divide it by ‘n’ as follows:
(1+2+3+….+n)
n
n*(n+1)*1
2 n
(n+1)
2
Hence the average number of key comparisons done by sequential search in the successful case is (n+1)/2. However in any case the number of comparison is O(n).
- Sequential Searching on an Ordered list
The efficiency of sequential searching can be greatly improved if the list is stored in ascending or descending order. In such case the expected number of comparisons required for an unsuccessful search can be reduced. Assuming that the elements appear in the ascending order, the search can be terminated as soon as we encounter an element that is greater than or equal to ‘item’ is found. When the element is equal to ‘item’ then the search is successful. When the element is greater than ‘item’ it can be concluded that ‘item’ is not present in the array and the search ends unsuccessfully.
Here is the algorithm of sequential search on an ordered list.
Algorithm : SequentialSearchOrder
SequentialSearchOrder(a, n, item)
Here ‘a’ is an array of ‘n’ number of elements and ‘item’ represents the item to be searched in array ‘a’
- Step-1 : Initialize i = 0
- Step-2 : Repeat through step-4 while (i < n)
- Step-3 : Compare a[i] and item
- If (a[i] == item) then return (i) and go to step-6
- Else if (item < a[i]) go to step-5
- Step-4 : Increment the value of ‘i’ as: i = i+1
- Step-5 : return (-1) as item was not found in the list
- Step-6 : Exit
The C implementation of this sequential search algorithm is as:
Implementation : SequentialSearchOrder
SequentialSearchOrder(int a[], int n, int item)
{
int i;
for (i = 0; i < n; i++)
{
if (a[i] == item)
return (i);
else if (a[i] > item)
break;
}
return (-1);
}
In this case there is no change in the expected number of comparisons for a successful search. The average number of comparisons for a successful search is still O(n). But there is definitely a reduction of the expected number of comparison required for an unsuccessful search. In fact this value may be ‘1’ in the best case and ‘n+1’ in the worst case.
- Indexed Sequential Searching
Indexed sequential searching is another improved searching technique for a sorted list. In this we maintained an auxiliary array ‘aux’ in addition to the sorted list itself. Each element in the array aux consists of a value (key) and a link to the record in the list that corresponds to the key. The elements in the array ‘aux’ as well as the elements in the original list must be sorted on the key. If the index is one fifth the size of the original list, every tenth record of the list is represented in the array ‘aux’. Figure-3 illustrates this.
Figure 3
Here is the indexed sequential search algorithm.
Algorithm : IndexSequentialSearch
IndexSequentialSearch(a, n, item)
Here ‘a’ is an array of ‘n’ number of elements and ‘item’ represents the item to be searched in array ‘a’
- Step-1 : Initialize an auxiliary array ‘aux’ of size n/5 such that every fifth element of the array ‘a’ is represented in ‘aux’.
- Step-2 : Find the appropriate index using an auxiliary array ‘aux’. Let ‘start’ and ‘end’ be the starting and ending index of the reduced list.
- Step-3 : Initialize i = start
- Step-4 : Repeat through step-6 while (i <= end)
- Step-5 : Compare a[i] and item
- If (a[i] == item) then return (i) and go to step-8
- Step-6 : Increment the value of ‘i’ as: i = i+1
- Step-7 : If item not found then return (-1)
- Step-8 : Exit
The C implementation of this indexed sequential search algorithm is as:
Implementation : IndexedSequentialSearch
IndexSequentialSearch(int a[], int n, int item)
{
int aux[10];
int i, value, start, end;
for(i=0; i
aux[i] = i*5;
for(i=0; i
{
value = aux[i];
if (a[value] > item)
break;
}
start = aux[i-1];
if (i==n/5)
end = n-1;
else
end = aux[i]-1;
for(i=start; i<=end; i++)
{
if (a[i] == item)
return (i);
}
return(-1);
}
The major advantage of this indexed sequential searching technique is that the elements in the list are examined sequentially even if all the elements in the list are accessed, yet the search time for a particular item is sharply reduced. In this case the sequential search is performed on the smaller index rather than on the lager one. Once the correct index position has been found in the original list, a second sequential search is performed on a smaller portion of the original list itself.
One main point to note here is that if the original list is so large that even the use of an index does not achieve the sufficient efficiency we will use another secondary index which will act as an index to the primary index, which points to the entries in the sequential table.
Binary Searching
No doubt the sequential search is easy and simple to write. It is efficient for the short lists but highly inefficient for long lists. Imaging try to find the name “Suman” in a large telephone directory by reading one name at a time starting at the front of the directory. We can improve this search time if the elements in the list are sorted in some order. One of the better known techniques for searching an ordered list is called binary searching.
In binary searching we compare the item with the element in the center of the list and then restrict our attention to only the first or second half of the list, depending on whether the ‘item’ comes before or after the central one. If the ‘item’ is in the first half of the list, the procedure is repeated on the first half of the list. In this way at each step we reduce the length of the list to be searched by half. And this process continues until either the required ‘item’ is found or the search intervals become empty.
Binary search is not good for linked list since it requires jumping back and forth from one end of the list to middle. That’s why we will discuss only contiguous lists.
Let us assume that the array being searched is sorted. Initially we will make a comparison between the ‘item’ and the middle element of the array, then based on the result of the comparison with the middle element one can draw one of the following conclusion:
- if (item == a[mid] then the middle element is the one being searched for
- if (item < a[mid] then the ‘item’ being searched for may be in the first half of the array
- if (item > a[mid] then the ‘item’ being searched for may be in the second half of the array
In the case when the ‘item’ is not found the process is repeated on the half in which the desired ‘item’ is likely to be present. This process goes on until either the search terminates successfully or the final division leads to a half consisting of ‘1’ number of elements. Let we have following list of numbers:
A[0] |
A[1] |
A[2] |
A[3] |
A[4] |
A[5] |
A[6] |
A[7] |
A[8] |
A[9] |
28 |
33 |
36 |
49 |
64 |
75 |
80 |
91 |
95 |
98 |
And let we want to find the item ‘49’. Initially we will start searching with the middle element of the list, that is A[5]. If item ‘49’ is not found at A[5] then we will search the first half of the list as shown in figure-4(a) and compare it with the item ‘49’. If item ‘49’ is not found at A[5] then we will take the middle element of the first half of the list as shown in figure-4(b). And this process goes on. Figure-4 shows that the item is found at 4th location.
Figure 4
Here is the binary search algorithm.
Algorithm : BinarySearch
BinarySearch(a, n, item)
Here ‘a’ is an array of ‘n’ number of elements and ‘item’ represents the item to be searched in array ‘a’
- Step-1 : Set lower = 0
- Step-2 : Set upper = n-1
- Step-3 : Repeat through step-5 while (lower <= upper)
- Step-4 : mid = (lower+upper)/2
- Step-5 : Compare a[mid] and item
- If (a[mid] == item) then return (mid) and go to step-7
- Else if (a[mid] > item ) then upper = mid-1
- Else lower = mid+1
- Step-6 : If item not found then return (-1)
- Step-7 : Exit
The C implementation of this Binary search algorithm is as:
Implementation : BinarySearch
BinarySearch(int a[], int n, int item)
{
int mid, lower, upper;
lower = 0;
upper = n-1;
while (lower <= upper)
{
mid = (lower+upper)/2;
if (a[mid] == item)
return (mid);
else if (a[mid] > item)
upper = mid-1;
else
lower = mid+1;
}
return (-1);
}
Analysis of Binary Search
Each comparison in the binary searching reduces the number of possible candidates by a factor of 2. In other words we can say that after each comparison either the search terminates successfully or the size of the array remaining to be searched is about one half of the original size.
And in worst case, the expected number of comparison require O(log2n) to search the target ‘item’, even if the search is unsuccessful.
Comparison Trees : How fast is it possible to Search
Till now we have studied sequential searching and binary searching. However the process of searching for ‘item’ in an array ‘a’ by means of comparing ‘item’ with the elements of ‘a’ can be conveniently expressed in terms of a binary tree. We trace the algorithm by representing each comparison of keys by a node (vertex) of the tree. Inside the circle we put the index of the key against which we are comparing the ‘item’. Two edges emanating out of a node represents the result of the comparison and are labeled accordingly. When the search is successful, we put the location where the ‘item’ is found at the end of the appropriate branch which we call a leaf and draw as a square as shown in figure-5.
Note that the search starts by the comparison at the root node of the tree. When we search for an ‘item’ into a tree then there are two possibilities – either the item is found or not found. When the search algorithm terminates we put either ‘F’ (for failure) or the location where the ‘item’ is found at the end of the appropriate branch. A successful search terminates in some internal nodes while an unsuccessful search terminate in an external node. We often call such trees as comparison trees.
The comparison tree for a sequential search is especially simple as shown in figure-5.
Figure 5
Figure-6 shows the sequence of comparisons required when binary search is applied to an array of 10 elements.
The number of comparison done in the comparison tree is the number of internal nodes traversed in going from the top of the tree (which is called its root) down the appropriate path to a leaf. The root itself has level 0, the nodes immediately below it has level 1, and so on. The largest level that occurs in a tree is called the height of the tree. The minimum height of a tree having ‘n’ nodes is log2n. So if we search for an ‘item’ in an array of ‘n’ elements then there are at least ‘n’ internal nodes.
Now we can say that the minimum worst case complexity of search algorithm must be equal to minimum height of a comparison tree having ‘n’ internal nodes, which is of course log2n. Thus there can not be comparison based searching technique where worst case complexity is less than O(log2n). On the same track we find that the average number of comparison based searching technique can not be less than O(log2n).
Figure 6 Comparison Of Binary Search For n=10
Inheritance
It’s a common saying. It suggests that we carry over some of the traits of our parents. Not only that we carry over their traits, but also, their belongings. They give us whatever they have except for a few things, which they treat as personnel or private to them. Except for these few, everything else, by default, falls in our lap. They serve us as a ‘base’ for our growth. Apart from what we get from our parents in legacy, we also have some personnel traits and acquire our own belongings, which prove to be an extension to the subtle base our parents provide. This is the phenomenon of INHERITANCE. In this whole process one unique feature that comes out is that we as inheritors are not required to work for what our parents have acquired - we simply ‘extend’ it. However at the application point the effect is of our possessing both - into our account - what our parents had and what we have. In OOPS this concept is followed, as it is, by extending classes. Inheritance is a real-life concept of deriving something more specific from a generalised existing thing, children have their own mental, physical and spiritual traits but they also inherit the features of their parents. Inheritance, as a mechanism of extending classes, involves deriving a new class from an old one. (existing one). The existing/old class is referred to as base class and the new one is known as the derived class. An example of inheritance is shown in fig lh1.
Introduction“Father or Mother is reflected in a child……”
The direction of arrow in figure lh1 should not be a source of confusion for the reader. Some texts show the arrow pointing from base class to derived class, while other texts show it in reverse order (representing “inherited from “relationship). The derived class inherits some or all of the traits from the base class.
Why Inheritance?
Inheritance truly supports REUSABILITY feature of Object Oriented Programming (OOP). If a class has been tested, debugged and used many times, then the effort of developing and testing the class again can be saved by making use of same class. If changes are required, programmers can derive another class from already existing one and make necessary changes in the derived of class. A class “fun” developed by Tom can be used by his friends X, Y, Z, A, B and so on (of course! only as long as Tom is willing to do share).
Different Types of Inheritance
Single Inheritance
A derived class has only one base class. (see figure lh2).
A class with several base classes is known as multiple inheritance (see figure lh33)
Class C inherits from both A and B
Hierarchical Inheritance
The mechanism of deriving a class from another ‘derived’ class is known as ‘multilevel’ inheritance (see figure lh5).
Hybrid Inheritance
This form of inheritance combines two or more forms of inheritance (see figure lh6)
Defining Derived Classes; Visibility Modes
In order to define a class having name derived-class-name from a class having name base-class-name, the following syntax is used
class derived-class-name : visibility-mode base-class-name
{
// members of derived class
};
The colon indicates that the derived-class-name has been derived from base-class-name.
It is important to learn about visibility modes while inheriting from a class. REMEMBER THAT PRIVATE DATA MEMBERS OF BASE CLASS WILL NOT BE INHERITED IN ANY CASE. When a class is ‘privately inherited’, its effect is that all public members of base class become private in the derived class, such that they are inaccessible to the objects of the derived class. On the other hand, when a class is publicly inherited into another class, the public members of base class remain public in the derived class, such that they are accessible to the objects of derived class. The syntax illustration is given below: -
class ABC: private XYZ /*private derivation */
{
members of ABC
};
Class ABC : public XYZ /* public derivation */
{
members of ABC
};
Consider the example of public inheritance given below:
class base
{
int a;
public :
int b;
void get_ab();
int return_a();
void show_a();
};
void base : : get_ab()
{
cin >>a >>b;
}
int base :: return_a()
{
return a;
}
void base :: show_a ()
{ cout << “\n a = “<< a; }
class derived : public base
{ int c;
public :
void add ();
void display ();
};
void derived :: add()
{
c= return_a() +b;
}
void derived :: display()
{
cout << “\n a = “<
cout << “\n b = “<
cout << “\n c = “<
}
void main ()
{
derived D;
D.get_ab(); /*public members of base class are */
D.add(); /* public members of derived class now */
D.show_a();
D.display ();
D.b= 35; /* b is also available as public member in derived*/
D.add();
D.display ();
}
The memory map of class derived is as shown in figure lh7
Let us now modify the earlier example a bit (though it will make a big change!) by inheriting the derived class privately. Notice the consequent changes design carefully
class base
{
int a;
public;
int b;
void get_ab( );
int return_a( );
void show_a( );
};
void base :: get_ab( )
{
cin >> a>>b;
}
void base :: return_a( )
{
return a;
}
void base :: show_a()
{
cout << “\n a =” <
}
};
class derived : private base
{
int c;
public;
void add ( );
void display ( );
};
void derived :: add ( )
{
get_ab ( );
c = return_a( ) + b;
}
void derived :: display ( )
{
cout << “\n a = “<
cout << “\n b = “<
cout << “\n c = “<
}
void main ( )
{
derived D;
D.add( ); /* D.get_ab ( ) is not allowed as get_ab( ) is a
private data member of derived class */
D.display ( );
}
Observe the effect of changing visibility mode to private. The main function cannot have the following statements: -
D.show_a( ); /*not allowed */
D.b = 35;
This is simply because show_a( ) and b are also private members of derived as is et_ab( ). The memory map of derived class is shown in fig.
The memory map of class derived is as shown in figure lh8
A major problem that remains unsolved is how to inherit a private data member, if it is needed in derived class. The ‘private’ label does not allow to break the walls of encapsulation whereas making such a data member ‘public’ would make it accessible to outside world besides imparting it inheritance capability.
The answer is ‘protected’ data member. The visibility label ‘protected’ ensures that the members declared under it are accessible to the derived class through inheritance. Further, protected members cannot be accessed by the functions outside the class. In a way, they combine the functionality of private and public members into one label. It is important to learn that behavior of protected data members in derived class depends upon visibility mode of inheritance.
The following example shows the use of protected visibility label:
# include
class base
{
protected ;
int a;
public;
int b;
void get_ab ( )
{
cin >> a>>b; }
}
class derived : private base
{
int c;
public:
void add ( )
{
get_ab( ) /* get_ab( ) is now private member of derived class */
c = a + b;
}
void display ( )
{
cout << “\n a = ” <
cout << “\n b = ” <
cout << “\n c = ” <, c;
}
};
void main ( )
{ derived D;
D.add ( );
D.display ( );
}
In the given example, the protected member ‘a’ became private in derived class. But it cannot be referred directly in main. Further, the function get_ab( ) can be completely removed by accepting the input for a and b in the add ( ) function itself. When using ‘protected’ visibility label, inheritance should be public if we expect more classes to be derived from the ‘derived’ class. (so that the protected member lands as protected in the derived class). In case the inheritance is not needed further after derived class, it is advisable to inherit privately. That is why, the last example uses private inheritance.
The table given in figure lh9 summarizes the inheritance rules: -
A Little Intro :
So far, each of the programs in this article has been a series of instructions executed in its physical order. First the statement at the top of the program is executed, then the second statement, then third statement and so on, until the last statement is executed. When working, there are several instances when we have had to make decisions. In other words, the order of execution of statements of a program may change depending upon the specified conditions. You can say that the statements may execute in logical order rather than physical order (the order in which the statements are written in the program). For instance, you need to use a simple condition like:
“If I buy more than 2 shirts then discount will be 20% on each shirt.”
In this case, the result action, that is discount will be 20%, is taken only when the condition, that is number of shirts is more than 2, is evaluated TRUE. Here we have only one condition. However, the conditions could be multiple.
Let we have a program of five statement as
main ()
{
statement-1;
statement-2;
statement-3;
….
Statement-n;
}
Then firstly the statement1 is executed, then the next statement2, statement3, statement4 and in last statement5 would be executed. But what would happen if we want to execute either statement3 or statement4, depending upon certain condition.
The C language provides many control structures to handle conditions and the resultant decisions. In this chapter we will study: the if-else and switch-case constructs. In C, we have relational operators to compare the value of two operands.
Relational Operators
Relational operators are used to compare two operands to test the validity of their relationship. The result of the relational expression is either TRUE or FALSE. However the relational expressions produce the value “1” for TRUE and the value “0” for FALSE. In other words we can say that the type of result is always an int value.
Table-1 shows a list of relational operators.
Precedence of Relational Operators
The relational operators are lower in precedence than arithmetic operators. It means that the expression:
x > y + z
is equivalent to the expression:
x > (y + z)
Parentheses can always be used to override the order of evaluation in an expression. Thus in the following expression
(x > y) + z
the comparison is made first and then the result of the comparison is added to the value of z. The best rule to follow for deciding when to use parentheses is to use them when in doubt. If they make it easier for human to understand the expression, they should be used.
Operator |
Meaning |
< |
Less than |
> |
Greater than |
<= |
Less than or equal to |
>= |
Greater than or equal to |
== |
Equal to |
! = |
Not equal to |
Table 1
Every relational operator is a binary operator. The left-hand side operand of the relational operator is treated as first operand and right side operand as second operand. The operands can have integrals, floating or pointer type.
For example
int x , y ;
x = 5;
y = 7;
x > y results in 0
x < y results in 1
x <= y results in 1
x >= y results in 0
x == y results in 0
x ! = y results in 1
The relational operators are not bound to just comparing variables or constants; we can also compare directly the results of arithmetic expressions. Watch the result of the following expressions:
int x, y ;
x = 10;
y = 15;
Expressions Result
(x+3) < (y-4) 0 (false)
(x+6) > (y+2) 0 (false)
(x+9) <= (y+4) 1 (true)
(x-3) >= (y-10) 1 (true)
(x+6) == (y+6) 0 (false)
(x+5) != (y-1) 1 (true)
As stated earlier, C allows decisions to be made by evaluating a given expression as true or false. The computer’s ability to make decision and execute different sequence of statements is a key factor in its usefulness for solving practical problems. In C, we have decision control structures that are used when a program requires that the computer must choose between two or more actions.
C provides three decision control structures:
- the simple if statement
- the if-else statement
- the switch statement
The Simple if Statement
The syntax of a simple if statement is as:
if (test-condition)
Statement;
Here if is a keyword which is followed by a test-condition. The test-condition consists of relational operators. If the test-condition is TRUE then the Statement is executed; otherwise the statement that follows the if–statement is executed.
The pictorial representation of if-statement is as shown in figure-1
Figure 1
Now let us write the if-statement of the earlier said example, say if I buy more than 2 shirts then discount will be 20% on each shirt. The above example is thus written as:
if (shirts > 2 )
discount = 0.20;
Here the number of shirt is received from the keyboard, then tested using the if-statement.
Following program illustrates the use of simple if statement.
/* Program-cs1.c */
#include
main ()
{
int shirts;
float rate, discount, total_price;
rate = 150.00;
printf("\nEnter the number of shirts = ");
scanf("%d",&shirts);
discount = 0.0;
if (shirts > 2 )
discount = 0.2;
total_price = shirts * rate * (1 - discount) ;
printf("Total price of %d shirts = %f", shirts, total_price) ;
}
Here are sample outputs of this program….
First Run:
Enter the number of shirts = 10
Total price of 10 shirts = 1200.000000
Second Run:
Enter the number of shirts = 2
Total price of 2 shirts = 300.000000
In this we have just one statement, discount = 0.2, as a result of test condition inside the if statement. But sometimes there may be more than one statement inside the if statement and then such set of statement must be enclosed within braces ({ }) as:
if (test-condition)
{
Statement-1;
Statement-2;
Statement-3;
----
----
Statement-n;
}
Here if you do not use the braces then the compiler will execute only Statement-1 if the test-condition results in true and other statements will always execute irrespective of the result of test-condition. The program given below illustrates the execution of multiple statements upon the fulfillment of a test condition.
/* Program-cs2.c */
#include
main ()
{
int number;
scanf("%d", &number);
if (number < 0)
{
printf("\nYou have entered negative number.");
printf("\nPlease enter any positive number.");
}
printf("\nThank you.");
}
In this example, if you enter any negative number during then the following statements are executed first:
You have entered negative number.
Please enter any positive number.
and then
Thank you.
However, if you do not enter a negative number then it will only display the following statement:
Thank you.
Another main point to note here is that there are no restrictions on the positions of braces. You can put them anywhere around this block and this block is indented to the right. It is used just for the convenience of the reader. It will help you read your programs, especially when they get larger and contain many nested blocks.
Here one should remember that the right parentheses of a test condition should not be followed by a semicolon; as the semicolon will itself be conditionally executed. The following statement
if (test-condition) ;
Statement;
is interpreted as:
if (test-condition) ;
Statement;
Thus if you write an if-statement, by mistake, as:
if (shirts > 2 );
discount = 0.2;
The extra semicolon after the condition will end the statement at this point, and the next statement will be always executed. Therefore watch your semicolons more carefully while using if statement.
The if-else Statement
In certain programming environment we come across in such a situation where we want to execute a statement Statement1 if our condition is TRUE and execute a statement Statement2 if our condition is FALSE. In other words, you can say that when taking a decision, there are always two faces to it, that is to do or not to do. This can be achieved by using the complete if-else structure. The syntax of the if-else statement is as:
if (test-condition)
Statement-1;
else
Statement-2;
Here if the test-condition results in TRUE then the Statement1 is executed; otherwise Statement1 is skipped and Statement2 is executed. The pictorial representation of if-else statement is as shown in figure-2
Figure 2
However you can also have a set of statements as results for either the TRUE or FALSE conditions. Like simple if statement, if you have multiple statements in if body and as well as in else body then it is necessary to enclose them within a pair of braces as:
if (test-condition) {
Statement-1;
Statement-2;
Statement-3;
Statement-4;
}
else
{
Statement-5;
Statement-6;
Statement-7;
Statement-8;
}
Like simple if statement, the statements in the else block have been indented to the right just to improve the readability of the code. Following example illustrates the use of the if-else statement.
/* Program-cs3.c */
#include
main ()
{
int number;
scanf("%d", &number);
if (number < 0)
{
printf("\nYou have entered a negative number.");
printf("\nYou should enter a positive number.");
}
else
{
printf("\nYou have entered a positive number.");
printf("\nYou should enter a negative number.");
}
printf("\nThank you.");
}
Now if you enter a number, say –10, the output will be:
You have entered a negative number.
You should enter a positive number.
Thank you.
However, if you enter a number, say 35, the output will be:
You have entered a positive number.
You should enter a negative number.
Thank you.
Nested if-else Structure
There are no restrictions on what the statement in an if-else statement can be. Therefore C provides the facility of using an entire if–else statement within either the body of the if statement or the body of an else statement. This is called as nested if–else statement. The term nesting comes from an analogy to a set of mixing bowls that nest together with smaller ones inside of larger ones. The most general form of two layer-nesting is:
if (test-condition-1)
{
if (test-condition-2)
{
Statement(s);
}
else
{
Statement(s);
}
}
else
{
if (test-condition-3)
{
Statement(s);
}
else
{
Statement(s);
}
}
In this if the test-condition-1 results in true then the if-else statement, which is embedded in if block, is executed and the other if-else statement, which is embedded in else block, is skipped. On the other hand if the test-condition-1 results in false then the if-else statement, which is embedded in if block, is skipped and the other if-else statement, which is embedded in else block, is executed.
The following program puts this logic into action:
/* Program cs4.c */
#include
main()
{
int a,b;
printf("\nEnter first number : ");
scanf("%d", &a);
printf("Enter second number : ");
scanf("%d", &b);
if (a>b)
printf("First number is greater than second number.");
else
{
if (a printf("Second number is greater than first number.");
else
printf( "Both numbers are equal.");
}
}
The following are sample runs for this program:
First Run
Enter first number : 10
Enter second number : 12
Second number is greater than first number.
Second Run
Enter first number : 12
Enter second number : 2
First number is greater than second number.
In this program, the second if–else statement is nested in the first else statement. If the first test-condition, that is a>b, is true then it displays the message
- First number is greater than second number.
If the first test-condition is false, then the second test-condition, that is a
Otherwise it displays the message
Both numbers are equal.
Here an if–statement is placed within the else body of the if–else statement. You can also place an if–else in the if block as well. Note that there is no limit on how deeply the ifs and the elses can be nested. If you are nested more deeply then you should make proper indentation; otherwise it may misguide you and others. In such case you may inadvertently match the wrong if.
Actually the rule is that every else belongs to the last if in the same block. Following program shows this.
/* Program cs5.c */
#include
main()
{
int age;
printf("\n Enter your age : ");
scanf("%d", &age);
if (age <=18) /* first if-statement */
printf("\n You have not yet grown up.");
else /* first else-statement */
if (age <= 35) /* second if-statement */
printf("\n You are a good looking young person.");
else /* second else-statement */
printf("\n You are a nice gentleman");
}
In this program, the second else statement does not belong to first if-statement. Rather than the second else belongs to second if-statement. No doubt, this program would work. But when you will look at this program after some time, you may get confused because the else is matched with the wrong if. Here is the proper indentation of this program.
/* Program cs66.c */
#include
main()
{
int age;
printf("\nEnter your age : ");
scanf("%d", &age);
if (age <=18) /* first if-statement */
printf("\nYou have not yet grown up.");
else /* first else-statement */
if (age <= 35) /* second if-statement */
printf("\nYou are a good looking young person.");
else /* second else-statement */
printf("\nYou are a nice gentleman");
}
Here are some sample outputs of this program….
First Run
Enter your age : 15
You have not yet grown up.
Second Run
Enter your age : 30
You are a good looking young person.
Third Run
Enter your age : 50
You are a nice gentleman
The if-else-if Ladder
When there are several different conditions are evaluated from the top down, and whenever a condition is evaluated TRUE, the corresponding statement (or set of statements) is (or are) executed and the rest of the construct is skipped. This construct is referred to as the if-else-if ladder. The general syntax of if-else-if ladder is as:
if (test-condition-1)
Statement-1;
else if (test-condition-2)
Statement-2;
else if (test-condition-3)
Statement-3;
else if (test-condition-4)
Statement-4;
….
else if (test-condition-n)
Statement-n;
Since C does not offer an else-if statement, therefore one should not confuse that the else-if is another reserved, rather than it is just another refined form of nested if-else statement. We know that C is a free-form language, therefore their conditions and their associated statements are just shown in a well-organized way in order to make a program into an easy–to–read format.
Now look at the following program. It is just another way of writing program-cs6.c
/* Program cs7.c */
#include
main()
{
int age;
printf("\nEnter your age : ");
scanf("%d", &age);
if (age <=18)
printf("\nYou have not yet grown up.");
else if (age <= 35)
printf("\nYou are a good looking young person.");
else
printf("\nYou are a nice gentleman");
}
This revised format is much clearer than earlier one. Here this entire structure still counts as one statement and lets you choose one among several alternatives.
Combining Several Relational Expressions
The logical operators are used to combine relational expressions together using the rules of formal logic. Table-2 lists three logical operators:
Operator |
Meaning |
&& |
AND |
|| |
OR |
! |
NOT |
The first two operators, && and ||, allow two or more relational expressions to be combined in an if statement. Let us see a simple program that illustrates the use of the logical operators.
The following program displays whether a given year is a leap year or not.
/* Program - cs8.c */
#include
main()
{
int year;
printf("\nEnter a year : ");
scanf("%d", &year);
if ((year%4==0) && (year%100 != 0) || (year % 400 == 0))
printf("%d is a leap year.\n", year);
else
printf("%d is not a leap year.\n", year);
}
Here are some sample outputs of this program….
First Run:
Enter a year : 1600
1600 is a leap year.
Second Run:
Enter a year : 1900
1900 is not a leap year.
The switch Statement
We know that the nested if–elses provides the facility of making a choice among several alternatives. The limitation of using nested if–elses is that you have to carefully match the corresponding ifs and elses and also the corresponding pair of braces. However C provides another decision control statement, a switch statement, that allows you to handle multiple choices, such as menu options. The decision is based upon the current value of the expression which is specified with the switch statement.
The syntax of the switch statement is as:
switch (integer-expression)
{
case label1 :
statement(s);
case label2 :
statement(s);
case label3 :
statement(s);
….
case labeln :
statement(s);
default :
statement(s);
}
The switch structure starts with the switch keyword followed by one block, which contains different cases. The keyword switch is followed by an integer expression. The integer-expression must be any expression that yields an integer value. It could be any integer constant or an expression that reduces to an integer value. The values followed by the keyword case are labels. Each label must be an integer or a character constant. Also each label must be different from all the others.
When a program encounters a switch statement, the integer-expression is evaluated first. If it is evaluated as “label1”, the “case label1 :” is executed. If it is evaluated as “label2”, the “case label1 :” is skipped and “case label2 :” is executed and so forth. Whenever it finds the suitable match, the statements following that case labels gets executed and all subsequent cases and default statements as well unless you explicitly direct it otherwise. However, if the value of the integer expression does not correspond to any case, the default case is executed. If the default case is omitted, and no case match is found, none of the statements in the switch body is executed.
The pictorial representation of the switch statement is as shown in figure-3
Figure 3
Here is a simple program of a switch statement.
/* Program cs9.c */
#include
main()
{
int n;
printf("\nEnter a number : ");
scanf("%d", &n);
switch (n)
{
case 1:
printf("\nYou entered 1.");
case 2:
printf("\nYou entered 2.");
case 3:
printf("\nYou entered 3.");
case 4:
printf("\nYou entered 4.");
default :
printf("\nYou have not entered 1, 2, 3 or 4.");
}
}
The output of this program is
Enter a number : 3
You entered 3.
You entered 4.
You have not entered 1, 2, 3 or 4.
From this output it is clear that whenever it finds a match, it then sequentially executes all the statements following that line, including the default as well, even though a match has already taken place. The default case may or may not be included, depending on the program’s needs. However, the default case can appear anywhere within the switch statement. If you do not want to execute all the subsequent cases and the default then use a break statement. The break statement skips the remaining statements of the switch statement and transfers the control to the statement following the switch statement.
C provides the facility of making decisions by using three selection control statements: the simple if statement, the if-else statement and the switch statement. The if-statement allows you to take different paths through a program based on the test condition. The test condition contains relational and logical operators. A test condition is evaluated and is assigned the value 1 if the condition is true or 0 if the condition is false.
The if-else allows you to choose between two courses of action. There can be simple or compound statement with if and else clause. There can be an if-else statement within another if statement, that nested if statement.
The switch statement is a multi-way selection statement. It allows the program to choose among a set of alternatives. The selection is based upon the current value of the expression, which is specified within the switch statement. This expression should yield an integer value because it can not be used with real values. The break statement terminates the switch statement and transfers the control outside the switch statement. If the break is omitted then the statements for subsequent cases will also be executed, even though a match has already taken place.