Skip to main content


Showing posts from June, 2007

Data Structures: Introduction to Stacks

In the previous article, we saw how data is inserted and deleted in an array. In that case we could insert data at any place throughout the array. However, there are situations when we only need to add and retrieve data form the ends of the array. Stacks are one of the examples of this. Stacks are data structures in which data could be added and retrieved only from one end (also known as the TOP of the stack). Suppose we insert 5, 6, 9 to the stack consecutively then while retrieving the first one to be retrieved will be 9 then 6 and then 5. That is why stacks are also known as Last-In-First-Out (or LIFO) structure. A few terms regarding stacks: Stack: Stack is a user-defined data structure. It is most commonly represented by linked-lists and arrays. In this article, we will be representing stacks with arrays. Push: Adding data to the stack is known as pushing. Pop: Retrieving data from the stack is known as popping. Let us have look at this process with the help of an

Insertion and Deletion of elements in an Array

Suppose you are storing temperature data for a few months and you forgot to store the temperature of a particular day (say 5th day) then you need to INSERT that temperature after the 4th element of the array and in the other case if you accidentally stored duplicate data then you need to DELETE the duplicate element. Apart from these simple examples, there are many other uses of insertion and deletion The array to which the element is to be inserted or deleted can be of two types unordered (unsorted) and ordered (sorted). Here we will be discussing about the insertion and deletion of element in an unordered or unsorted array. For insertion in these types of arrays, we need to have two information, the element to be inserted and the position to which it will be inserted. For deletion, we only need the position. Suppose we have the following array: arr[5]={5,7,2,1,3} And we need to insert the element 6 at the 2nd position, after insertion: arr[5]={5,6,7,2,1} Notice how the last e

Algebra of Matrices (2D Arrays) Part II

As you know from the previous article, matrices are 2D arrays. In the previous article, we saw how two matrices are added and subtracted. In this article, we will continue our discussion on algebra of two matrices by discussing how two matrices are multiplied. Multiplication of two Matrices Multiplication of two matrices mat1[a x b] and mat2[p x q] is only valid if b=p. While there are many algorithms by which two matrices can be multiplied, here I’ll give you the most simple algorithm. Others are used when efficiency matters. Algorithm for Multiplication of two Matrices Suppose, Two 2D arrays to be mat1 [p][p] and mat2 [p][p] having same number of rows and columns. A third 2D array, mul [p][p] to store the result. Here is the algorithm: FOR I = 0 TO (p-1) FOR J = 0 TO (p-1) mul [I][J] = 0 FOR K = 0 TO (p-1) mul [I][J] += (mat1 [I][K] * mat2 [K][J]) END OF INNER LOOP END OF OUTER LOOP Below is a example program which illustrates the multiplication

Algebra of Matrices (2D Arrays)

In the programming sense, Matrices are Two Dimensional or 2D arrays. Just as Matrices have rows and columns, similarly 2D arrays too have rows and columns. There are many mathematical operations like addition, subtraction, multiplication etc. which can be performed on matrices, and therefore to 2D arrays also. In this article, we will be discussing about the addition and subtraction of two 2D arrays (Matrices). Addition of two Matrices (2D arrays) For addition of two matrices both the matrices must have the same dimension. Ex. if matrice one has the dimension p x q then matrice two must have the dimension p x q. In the addition process, each of the element of the first matrice is added to the corresponding element of the second matrice and result is stored in the third matrice having the same dimension (i.e. p x q). Below is the algorithm for adding two matrices. Algorithm for adding two Matrices Suppose, Two 2D arrays to be mat1 [p][q] and mat2 [p][q] having p rows and q colu

Binary Search: A Method of Searching

Binary Search method is popular for searching a specific item in an ordered array (sorted). It can perform the search in minimum possible comparisons, but it needs the array to be sorted in any order. Practically, it is used when the data is itself sorted initially or needs to be sorted for other activities also. This is because you don’t want to first sort the data and then use binary search, in that case use of linear search would be practical. Binary Search Algorithm Suppose, The array to be AR[SIZE] having SIZE number of elements. L is the index number of the lower element. We take it to be 0. U is the index number of the upper (last) element. It will be (SIZE-1). ITEM is the data that needs to be searched. beg, last and mid are variables of type int(eger). Here is the algorithm: LET beg = L AND last = U REPEAT STEPS 3 THROUGH 6 TILL beg<=last mid = ( (beg+last)/2) IF AR[mid] = ITEM THEN ITEM IS AT POSITION mid BREAK THE LOOP IF

Sorting an Array using Bubble Sort

In this article we will see how an array can be sorted using Bubble Sort Technique. Sorting, as you know, is the method of arranging the elements of an array in an order (ascending or descending). The basic idea behind bubble sort method of sorting is to keep on comparing adjoining elements of the array from the first until the last and interchanging them if they are not in proper order. The whole sequence is repeated several times when the array becomes sorted. Bubble Sort Algorithm Suppose, The array (to be sorted) to be AR[SIZE] having SIZE number of elements. L is the index number of the lower element. We take it to be 0, since the whole array has to be sorted. U is the index number of the upper (last) element. It will be (SIZE-1). Here is the algorithm of sorting the array using bubble sort FOR I = L TO U FOR J = L TO (U-1) IF AR[J] > AR[JA1] THEN temp = AR[J] AR[J] = AR[J+1] END OF INNER LOOP END OF OUTER LOOP Now that you know th

Classes & Objects: Dynamic Memory Allocation

Just as variables of pre-def data type are dynamically allocated, same way objects of class can also be dynamically allocated. While the method of doing this is no different but the way members of such objects are accessed is a bit different. This is why I thought of writing a separate article on it. Before discussing any further, look at the program below: // Example Program in C++ #include<iostream.h> // class class myclass { // by default everything is // private to the class int var1, var2; void add(); public: int sum; void input(int,int); }; // function definitions void myclass::input(int a, int b) { var1=a; var2=b; add(); } void myclass::add() { sum=var1+var2; } // main function starts void main(void) { myclass obj; // simple object myclass *pobj; // pointer // of type 'myclass' pobj=&obj; // now 'pobj' pointer // points to the object 'obj' of /

Features of C++, we haven't discussed...

In this article, we will discuss about certain features of C++ Programming Language, which we haven’t discussed so far. All the features are discussed with the help of example programs so that you could straightaway learn to use them. Let us have a look at them one-by-one: (Things are discussed in the comments wherever necessary) EXAMPLE 1 : Variation of for-loop // Example Program in C++ #include<stdio.h> #include<conio.h> void main(void) { char ch; for(;;) { // this loop will run // infinitely till // 'q' is pressed ch=getch(); if (ch=='q' ch=='Q') break; } printf("out of loop\n"); } EXAMPLE 2: Variation of for-loop // Example Program in C++ #include<iostream.h> void main(void) { char str[20]="learn C++"; for(int i=0;str[i];i++) ;// notice that there // is nothing in the // body of the loop cout<<"length

Reference Variables in Detail

A reference is an alias or alternate name for an object. It is just like having two variables having the same memory address, if one of them changes the other will also change. Actually, a reference is an implicit pointer. Suppose, we have an int(eger) variable num and its reference refnum , then both will always have the same value no matter which one gets alerted. We can have independent references, reference parameters in functions, functions returning references etc. that are illustrated below with the help of example programs:- EXAMPLE 1: Independent Reference to a variable // Example Program in C++ #include<iostream.h> void main(void) { int num; // notice the declaration of a reference // & has nothing to do with the 'address // of' operator (&amp;) int &refnum=num; cout<<"enter value for num: "; cin>>num; cout<<"now refnum="<<refnum; cout<<"\nenter value f

A Multi-Purpose String Class in C++

NOTE: Here I present you with a String Class in C++. We have pre-defined string class (CString in Microsoft Visual C++) which has similar but more powerful to the one presented here but using something is one thing and learning how it works is another. Here I show you how string functions actually work. All the functions are programmed from the scratch without using any other standard library function. Look at the program (Class) carefully and try to understand how each of the function is working. //----------------------------- //-----------myClass----------- //----A String Class in C++---- #include<iostream.h> #include<stdlib.h> class myString { private: // these functions are not // needed outside the class void allocate(int); void copy(char *, char *); public: char *string; // member functions myString(); myString(char *); int getLength(); int getLength(char *); void empty(); bool isEmpty(); void putStri

Destructor Functions in Detail

If you don’t know what destructor functions are, read Introduction to Constructor and Destructor functions of a Class . As the example programs in this article makes use of the dynamic memory allocation of C++, so please read Introduction to Dynamic Memory Allocation in C++ , in case you missed it. When does the destructor function gets invoked The examples below illustrates when the destructor function gets invoked: Example 1: //Example Program in C++ #include<iostream.h> class myclass { public: ~myclass() { cout<<"destructed\n"; } }; void main(void) { myclass obj; cout<<"inside main\n"; } OUTPUT: inside main destructed Press any key to continue As I said in the other article, destructors get invoked when the object of a class goes out of scope. In this case, the object goes out of scope as the program terminates. So the destructor gets invoked just before the program’s termination.

Introduction to Dynamic Memory Allocation in C++

Suppose you are making a C++ program to store a particular number (specified by the user at runtime) of phone numbers. What will you do? You cannot declare array of 10 or 20 elements because you don’t know how many numbers the user will enter. He may want to enter 1, 10 or even 100 phone numbers. So what will you do? Actually, you can do two things to achieve this, that are listed below: You can create a very large int(eger) array (say, of 500 elements) , in this case whether the user wants to store 1 or 500 phone numbers, the memory used will always be the same (large!). You can make use of C++’s dynamic memory allocation to allocate only the needed amount of memory. The first choice is a very bad way of programming, nevertheless it works fine, you should never employ such an inefficient method of programming. So, you are left with only one choice to use the Dynamic Memory Allocation of C++ programming language, that I w

Introduction to Constructor and Destructor functions of a Class

Constructor and Destructor functions are Member Functions of a class having some special property. Constructor function gets invoked when an object of a class is constructed (declared) and destructor function gets invoked when the object is destructed (goes out of scope). Use of Constructor and Destructor function of a class Constructor function is used to initialize member variables to pre-defined values as soon as an object of a class is declared. Constructor function having parameters is used to initialize the data members to the values passed values, upon declaration. Generally, the destructor function is needed only when constructor has allocated dynamic memory. Defining Constructor and Destructor functions The example below illustrates how constructor and destructor functions are defined: class myclass { private: int number; public: myclass()//constructor { number=10; } ~myclass()//destructor { //nothing needed } }; A few

Introduction to Function Overloading in C++

Let us start this with a question! All of you know that we cannot have two variables of the same name, but can we have two Functions having the same name. The answer is YES, we can have two functions of the same name by a method known as function overloading and the functions having the same name are known as overloaded functions. So, what’s the use of Function Overloading Function overloading is one of the most powerful features of C++ programming language. It forms the basis of polymorphism (compile-time polymorphism). Most of the time you’ll be overloading the constructor function of a class. How function overloading is achieved One thing that might be coming to your mind is, how will the compiler know when to call which function, if there are more than one function of the same name. The answer is, you have to declare functions in such a way that they differ either in terms of the number of parameters or in terms of the type of parameters they take. What that means is, noth

Unit Conversion Program using Classes

Welcome back guys, I hope you like my previous article, Introduction to Classes in C++ , in this article we will be further continuing our discussion on classes in C++. We will not be discussing anything new on the topic though, just a simple example program to elaborate more on Classes in C++. In this article, I will show you a program based on classes, which converts units of length from one to another. The program is simple and I do not think there is any need for discussing it in detail. The example program is given below: //C++ Program #include<iostream.h> class length { private: float in_meter, in_cm, in_inch; public: void input(float len,int ch); float output(int ch); }; //---function definition starts--- void length::input(float len,int ch) { switch(ch) { case 1://for meter in_meter=len; in_cm=in_meter*100; in_inch=in_cm*2.54; break; case 2://for cm in_cm=len; in_meter=in_cm/100; in_inch=in_cm

Introduction to Classes in C++

Classes are the building blocks of Object Oriented Programming in C++ language. Class gives us the ability to simplify certain types of programs by creating objects that forms the basis of Object Oriented programming. Just like identifiers of built-in data types (ex. int, char etc.) are known as variables similarly identifiers (instances) of class are known as Objects. Classes in C++ have two parts, data and functions; these are known as data members and member function respectively. Member functions are usually the means of accessing and modifying data members. Anything inside the class can be either private to the class or public to the program. Classes may have both type of members (private and public) at the same time. General form of Class: class class_name { access-specifier: member… member… member… access-specifier: member… member… member… }object-list; Few points to remember: Access-specifier can be anyone of the three private, public and

Method of Adding Individual Digits of a Number

NOTE: The program discussed in this article has no use in practice but it would definitely help you understand a few things, so please read on… What this program does is that it takes a number as input (such as 12345) and outputs the sum of the individual digits, which in this case is 15 (1+2+3+4+5). For achieving the required result, we need to do two things, first we should store each of the individual digits in the number and second, we need to add those numbers, which will give us the required result. Let us move on to the first stage where we need to separate the digits. Here are the steps:- STEP 1: We declare a variable num as integer type and an array sep[] again as integer type. Suppose num=12345 STEP 2: We will be fetching digits from the right (5) to left (1). For this, we use the modulus (%) operator which divides two numbers, giving us the remainder. sep[0]=12345 % 10 Now, num=12345 sep[0]=5 (last digit has been fe

Simulating the throw of dice in C++

What makes the throw of dice special is the fact that you can’t always guess which number will come up. This property is known as randomness, which is needed in certain types of programs (ex. Games). In this article, we are going to discuss how random numbers are generated and used in C++ with the help of a simple example. The program illustrates generation and use of random numbers in C++: //C++ Program to generate RANDOM NUMBERS //function is isolated so it may be easily //incorporated in other programs //NOTE:stdlib.h header file is required //for using this funtion elsewhere #include<stdio.h> #include<stdlib.h> #include<conio.h> //FUNCTION PROTOTYPE int random(int HighestNumber,int LowestNumber); void main(void) { char ch = ''; puts("Random Number Generator: "); while(ch!='q' && ch!='Q') //loop until q or Q is pressed { puts("Press any key to throw dice...");

String Searching Function in C++

Nothing much to say, here I present you with a searching function. It takes two-character string (array) as the argument and finds the position of the second string in the first. For example, if the two arrays passed to the function have the following values: String 1: ”I like C++” String 2: “C++” then the function will return 7, because as an array, string 1 has the word C++ starting from the index number 7. If the function cannot find the second string inside first then it will return the value -1, indicating that the search was unsuccessful. The program below is easy to understand; therefore, I have left it up to you to understand how it is working. //C++ program which searches for a substring //in the main string #include<stdio.h> int search(char *string, char *substring); void main(void) { char s1[50], s2[30]; int n; puts("Enter main string: "); gets(s1); puts("Enter substring: "); gets(s2); n=search(s1,s2);

Sorting an array using Selection Sort

Sorting is the process by which the elements of a group (ex. Arrays) are arranged in a specific order (ascending or descending). The process of sorting is very important, since it is needed in many types of programs. Ex. If you need to arrange the heights of various students in a class, you need to sort their heights. While there are quite a few methods employed for sorting, we will be discussing about Selection Sort method in this article. In selection sort, all the elements of an array are compared with the other elements following it and interchanged so that smaller elements come at the top. So, what that means is that the first element is compared with the second, third … elements then the next is selected (second element of the array) and it is compared with the third, fourth … elements and in this way different elements are selected serially and compared with elements following it. Interchange is done so that smaller elements come high up in the array. (for ascending order) To m

Simple Problems in C++ Part III

Yesterday I was having a look at my traffic statistics when I came to know about one thing. I saw that most of the visitors to this blog paying attention to the two of my recent articles Simple Problems in C++ Part I and Simple Problems in C++ part II. Seeing that, I made up my mind to write the third part of the Problems in C++ series with some more interesting problems. Now, without wasting your time anymore, I present you with some more Simple problems in C++. Here they are :- Problem No. 1: #include<iostream.h> void main(void) { int i=1; for(;;) { cout<<i++; if (i>10) break; } } QUESTION: Is there any error in the program? Problem No. 2: #include<iostream.h> void main(void) { int i=1; while() { cout<<i++; if (i>10) break; } } QUESTION: Is there any error in the program? Problem No. 3: #include<iostream.h> void main(void) { int a=10,b=20; if(!(

Name Abbreviation Program in C++

In this article, we are going to design a program that abbreviates the first and middle name leaving the last name as it is. Suppose if the user inputs the following name: William Henry Gates Then the output of the program would be: W. H. Gates Without further a due I present you with the Steps:- We have declared two character arrays (strings), name[4] and abname[30], which stores the name input by the user and abbreviated name respectively. Suppose if the user inputs the following name: William Henry Gates Then the two arrays would have the following values: Name[40]="William Henry Gates" (unchanged) Abname[30]=EMPTY The next step is to store the first character of the array name[40] to the abname[30] array and put a dot (.) and a space( ) after it. Next, we set-up a loop which finds space in the array name[40] (space separates first, middle and last names). As soon as a space is detected the character immediately after the space is stored to the abname[30] array, f

Learn to Define and Use Functions in C++

Functions can be thought of as separate programs that are designed to perform specific tasks. For example, in a program, separate functions can be so designed to perform specific tasks such as taking input, doing calculation, giving output etc. In this article we will be discussing about what functions are and how they are designed in C++. Generally, programs have many logically different parts (input, output etc.) which can be coded separately as function. This makes programs easily manageable and understandable. Suppose we have to design an invoice program that takes input, calculates and at last displays the output. We have two options to do so, we can either program the whole thing linearly or we can make separate functions for each of the tasks (input, output etc.), this would make the program far more manageable and upgradeable. (In the future, if you need to change certain things, you only need to alter the functions) In this way if you divide various activities of the program i

Learn to use Loops in C++

While every programming language has its own version of loops (iteration statements), the loop statements of C++ are way much more powerful than those of other languages. It is because of the variations that loops can have in C++. This article would give just an introduction to the loop structures in C++, leaving complex variation of loops for the coming articles. A Loop (iteration) statement repeatedly executes a set of statements until a particular condition is reached. Have a look at this program: //C++ program #include<iostream.h> void main(void) { int arr[3]; cout<<"enter three numbers:"<<endl; cin>>arr[0]>>arr[1]>>arr[2]; cout<<"number 1: "<<arr[0]<<endl; cout<<"number 2: "<<arr[1]<<endl; cout<<"number 3: "<<arr[2]<<endl; } Now look at this program: //C++ program #include<iostream.h> void main(void

Learn to use Pointers in C++

For those of you who do not know what pointers are, I give you a short definition. Pointer is a type of variable that stores memory addresses rather than simple data. Pointers also have Data Types associated with it, Ex. int pointers can only store memory address of int variables and similarly float pointers can only store memory address of float variables. Pointers are one of the most important distinct features of C++. It gives the programmers power and control over several things. Pointers have many uses; sometimes it is used as the faster means of accessing arrays while sometimes it is implemented so that the function in C++ can modify the parameters passed to it. Pointers are extensively used in C++, this might not be obvious to you right now but as you start programming some complex program, you will notice how important pointers are. This article would serve as a little introduction to pointers in C++, it would help you understand what pointers are and how it is used in C++. De