Data Structures, C and C++
One especially important consideration is the choice of an algorithm description language. This choice actually depends on several factors, such as programmer background, programmer’s ability to express his views, language availability, etc. Pascal is still a very impressive language for an algorithm description language, but today the programming language ‘C’ and ‘C++’ has become pervasive as the most likely language in computer field.
A ‘C’ programmer knows that ‘C’ has its own capabilities, data types and operations. Additionally ‘C’ provides more useful programming constructs as tools to a ‘C’ programmer. ‘C’ has already two main data structures – array and structure. When we define structured data structures, such as stacks, queues, lists, etc., we will extensively make use of arrays and structures. In fact there are languages of significantly higher level than C that have many of these data types already built into them, but unfortunately many of them inefficient, and are therefore not in widespread use.
Once you know ‘C’, you can easily switch from ‘C’ to ‘C++’ without any tension because C++ is derived from C with new paradigm – Object-oriented programming, or OOP – well suited to modern programming needs.
Brief Discussion of C and C++
The programming language ‘C’ was designed and written by a system programmer Dennis Ritchie at AT&T Bell Labs of USA in 1972. Ritchie goal was to provide a language that would allow the programmer to access the hardware as is done with assembly language but with structured programming features similar to those found in high-level programming languages.
In fact the origin of ‘C’ language was just to make UNIX operating system potable in order to use it on a variety of computer types. At that time Ken Thompson, creator of UNIX operating system, and Dennis Ritchie needed a high-level language that combined low-level efficiency and hardware access with high-level generality and portability. So, building from older languages, he created ‘C’. After this UNIX operating system was rewritten in C language. More than 80% of UNIX is in C. UNIX became the first major operating system to be written in something other than assembly language. C rapidly became most programmer’s favorite language for writing program under MS-DOS. MS-DOS itself consists of C programs, as do most of its utility programs. You will be surprised to know that Windows 3.x graphical operating system was written in C. Even Windows 98 and Windows NT are written mostly in C.
C was originally defined in 1981 in the C Programming Language (Prentice Hall) by Brian Kernighan and Dennis Ritchie. This book described C the way Ritchie implemented it. This book became known simply as K&R C. Some programmers now refer to K&R C as “Classic C”. Over the years, compiler builders added features of C according to the requirements of their own users.
Many different organizations have their own C compilers which may differ from one another to a greater or lesser extent. In order to provide a standard for C, a technical committee on C language standardization, was formed by American National Standard Institute (ANSI) in 1983. ANSI was joined in their task by a committee of the International Standard Organization (ISO), which formed to define the language for the international programming community. And in 1990, the C language was finalized by the ANSI-committee and ISO. The language defined by them is known as Standard C.
‘C’ includes features to facilitate structured programming approach using a set of well-behaved constructs, such as the for-loop, while-loop, do-while loop, and the if-else statement. Additionally ‘C’ provides the facility of using top-down methodology (an idea of breaking a large program into smaller, more manageable tasks) by developing program units called functions to represent individual task modules.
No doubt the principles of structured programming improved the clarity, reliability and ease of maintenance of programs, but the major limitation of structured programming was that it gave first priority to algorithms, that is structured programming emphasize algorithms, rather than the data. Object-oriented programming was the next step. OOP gives the first priority to data, thus emphasizes data by using a class facility. OOP’s main features are – classes, inheritance and polymorphism. C++ is one the most frequently used OOPs language.
C++ programming language was designed and developed by Bjarne Stroustrup also at AT&T BELL laboratories in the early 1980’s. Bjarne Stroustrup based C++ on C language. Bjarne Stroustrup added some new features, such as objects, classes, polymorphism, inheritance, operator overloading, functions overloading etc, to the most popular language C without significantly changing its components. Bjarne Stroustrup called it “C with classes” originally. Later it was named as C++ (pronounced as C plus plus) where “++” is the C increment operator indicating an incremental development of C. C++ is a superset of C, meaning that any valid C programming is a C++ programming too.
Concept of a Data Type
Data items are the physical symbols that represent information in the computer system. A computer program operates on data and produces an output. In a computer programming language (high-level programming language) each data item must be of a specific type. The data type determines how the data items will be represented in the computer and what types of operations the computer will be able to perform on them. In other words a data type is a term which refers to the kinds of the data that variables may hold in a programming language. With every programming language there is a set of built-in data types. Some of the standard data types in ‘C’ are: integer, double, float and character.
When we say it is of type integer or real or character then it means that we are talking about the set of values and the set of operations applicable those values. In other words to define a type, the set of values and the set of operations are defined. Thus as far as the integer type is concerned, the operations such as addition, subtraction, multiplication etc. are defined. These operations are defined to be binary, that is we need two integer operands in order to perform addition or subtraction or multiplication and so on. But if we use character data type then two variables of character data type can not be added or subtracted because these operations are not defined on character data type.
Another main point to note here is that we have to define each type of data that we will use in our program. Of course almost every programming language support built-in data types, they are not enough for most of the practical applications, that’s why we need structured data types.
Structured Data Types
Programming languages, such as Pascal or C, however, provide tools such as arrays, structure, files, and pointers, with which new data types can be built. Such data types are called as structured data types. A structure data type is made up of several components each of which are either an atomic type (types such as integer, real and character are called atomic types because we think of their values as single entities only) or of another structure type. In C. this can be accomplished by defining a struct. However, just by defining a structured data type, the operations applicable to variables of that type can not be specified.
Abstract Data Types
We know that a basic data type is a collection of values and a set of operations on those values. In the same way the term abstract data type (ADT) refers to a programmer defined data type together with a set of operations that an be performed on that data. It is called abstract just to distinguish it from basic built-in data types such as int, char, and double. In other words the definition of an ADT consists of two main points – the internal representation of the ADT’s data and the functions to manipulate this data.
In C we can define an ADT by using the keywords – typedef and struct and defining the functions thus data abstraction. But in C++ we have much better facilities, using class, for defining and using ADTs. And it is totally the programmer’s duty to use the class mechanism in such a way that it does, in fact, represents an ADT. This process of defining an abstract data type together with the principles of data hiding is called data abstraction, one of the basic concepts underlying OOP (Object Oriented Programming). You will be surprised to even know that most experts agree that OOP involves defining ADT representing complex real-world.
For example, consider the list abstract data type. A list of element of type T is a finite sequence of elements of T together with the possible operations, such as:
1. initialize the list to be empty
2. adding new elements to the list, provided that list is not full
3. deleting elements from the list, provided that list is not empty
4. determine the length of the list
5. determine whether the list is empty or not
6. determine whether the list is full or not
7. replacing an element in the list, provided that list is not empty
Here the programmer is not concerned with how a list is represented and how the above mentioned operations are implemented. We only need to know that we have a list whose elements are of given type T, and what can we do with the list. Similarly we can consider the stack abstract data type. A stack of element of type T is a finite sequence of elements of T together with the possible operations, such as:
1. initialize the stack to be empty
2. adding new elements to the stack, provided that stack is not full
3. deleting elements from the stack, provided that stack is not empty
4. retrieving the topmost element from the stack, provided that stack is not empty
5. determine whether the stack is empty or not
6. determine whether the stack is full or not
Again the stack abstract data type make no mention of the way in which it is to be implemented. We only need to know that we have a stack whose elements are of given type T, and what can we do with the stack. It is to emphasize again that defining an ADT implies a description of the way in which the elements are related to each other and a set of operations that can be performed on elements of the abstract data type.
Structures
The secondary data type, which associates with a set of similar data types, is array data type. We have already discussed array of ints, array of floats or array of char’s etc. These set represent the characteristics of samedata type . But we are living in such an environment that in our daily life we need to associate a single variable to different data types. For example let an employee of an institution is referred as its:
First name
Second name
Age
Salary
Department etc.
C provides a data type structure to handle such type of environment. A structure is basically a collection of data fields in which the fields may or may not belong to same category. And the fields of the structure are called as members of the structure.Now we will see how to define structure data type. C provides a keyword ‘ struct ’ to declare a structure. The syntax of a structure declaration is as:
struct{
datatype_1 list of datatype_1 variables;
datatype_2 list of datatype_2 variables;
datatype_3 list of datatype_3 variables;
datatype_m-1 list of datatype_m-1 variables;
datatype_m list of datatype_m variables;
};
For example if we want collect the information of all the employees have as of an institution then let it has following information:
First name
Second name
Age
Salary
Department
City
Pincode
Then we will use the following structure declaration:
struct employee{
char f_name [20];
char s_name [20];
int age;
float salary;
char dept [25];
char city [15];
long int pincode; };
Here employee is not a variable, rather than it is a structure declaration, which is used to create structures, or you can say employee is new user structure defined data type. Since a structure declaration does not reserve any space in memory. Therefore employee is a structure declaration, so it will not reserve any space in memory.If we want to create one or two variables of data type employee then we will use the following statement:
struct employee emp1, emp2;
Here emp1 and emp2 are two structure variables of data type employee. And now the compiler reserves space in memory for each variable. The compiler reserves 80 bytes for each structure variables of type employee as:
20 bytes are reserved for f_name
20 bytes are reserved for l_name
02 bytes are reserved for age
04 bytes are reserved for salary
15 bytes are reserved for dept
15 bytes are reserved for city
04 bytes are reserved for pincode
And these bytes are reserved contiguously in memory as
Addresses |
Contents |
68201 68202 | 68220 |
f_name |
68221 68222 | 68240 |
l_name |
68241 68442 |
age |
68443 | 68446 |
salary |
68447 | 68461 |
dept |
68462 | 68476 |
city |
68477 | 68480 |
pincode |
In this figure (a), it is assumed that the starting address as 68201.
The complete structure declaration and structure variables are as:
struct employee{
char f_name [20];
char s_name [20];
int age;
float salary;
char dept [25];
char city [15];
long int pincode;
};
struct employee emp1, emp2;
The another way of writing this is:
struct employee{
char f_name [20] ;
char s_name [20];
int age;
float salary;
char dept [25];
char city [15];
long int pincode;
} emp1, emp2;
Till now we know how to define a structure declaration and how to create structure variables. Now we will see - how to access individual member of the structure variables. C provides a dot (.) Operator to access the individual member of the structure variables. The syntax of accessing the member of a structure variable is as:
For example, if we want to refer the first name of the structure variable emp1 then we will use:
emp1.f_name;
Similarly if we want to refer the department of the structure variable emp2 then we will use:
emp2.dept;
Now let us write a simple program in which we store the values into three structure variables and output these values:
/* Program – 1 : Simple structure */
#includemain ()
{
struct employee
{
char name [20];
int age;
float salary;*
long int pincode;
};
struct employee e1, e2, e3;
printf (“\n Enter the name, age, salary and pin code of first employee =”);
scanf (“%s %d %f %ld”, e1.name, &e1.age, &e1.salary, &e1.pincode) ;
printf (“\n Enter the name, age, salary and pin code of second employee =”);
scanf (“%s %d %f %ld”, e2.name, &e2.age, &e2.salary, &e2.pincode) ;
printf (“\n Enter the name, age, salary and pin code of third employee =”);
scanf (“%s %d %f %ld”, e3.name, &e3.age, &e3.salary, &e3.pincode);
printf (“\n You have entered following values = ”);
printf (“%s %d %f %ld”, e1.name, e1.age, e1.salary, e1.pincode);
printf (“%s %d %f %ld”, e2.name, e2.age, e2.salary, e2.pincode);
printf (“%s %d %f %ld”, e3.name, e3.age, e3.salary, e3.pincode);
}
The output of this program is
Enter the name, age, salary and pin code of first employee =
Ambit 28 12000.00 126001
Enter the name, age, salary and pin code of second employee =
Ramesh 32 10075.75 145600
Enter the name, age, salary and pin code of third employee =
Sumit 26 9000.50 127006
You have entered following values
Amit 28 12000.00 126001
Ramesh 32 10075.75 145600
Summit 26 9000.50 127006
Structure Variable Initialization
Like ints, floats, chars and arrays, we can also initialize structure variables as:
struct employee{
char name [20] ;
int age ;
float salary ;
long int pincode;
};
struct employee emp1 = {
“Amit” , 28 , 12000.00 , 126001
};
struct employee emp2 = { “Ramesh”, 32 10075.75, 145600 };
struct employee emp3 = { “Sumit”, 26 , 9000.50 , 127006 };
Array of Structures
Till now we have defined structure declaration and structure variables. But some we need to store a set of 100 employees records or a set of 50 student records, then we need to maintain a number of structure variables.
There are ways to handle this problem:
- Either uses 100 different structure variables such as emp1, emp2, and emp3.... emp100
- or use an array of structures that store all hundred structures into one umbrella
To declare an array of structure, we must define a struct data type and then declare as array of structure. Let us declare an array of 50 structure variables that holds the records of 50 students.
struct student_rec{
char name[20];
int age;
long int rollno;
char section;
};
struct student_rec student[50];
C compiler reserves memory space for 50 structures after the execution of this statement declaration and the same rule applies for array of structure as for array of primary data types such as ints, floats or chars i.e. the first student record is referred as:
student [0].namestudent [0].age
student [0].rollno
student [0].section
and the 50th record is referred as :
student [49].name
student [49].age
student [49].rollno
student [49].section
And in memory all the structure variables are stored in contiguous memory locations because array elements are stored continuously in memory and here array element is a structure and members of structure are always stored contiguously. It means that first one student [0]’s name, age, rollno and section would be stored, then student [1]’s name, age, rollno and section, student [2]’s name, age, rollno and so on.
Let us look at a complete program that uses array of structures:
/* Program – 2 : Array of structures */
#includemain ()
{
struct student_rec
{
char name[20];
int age;
long int rollno;
char section;
};
struct student_rec s[50] ;
int i ;
for (i=0; i<= 49 ; i++ )
{
printf (“\n Enter the name, age, roll number and section of %d student”, i+1);
scanf (“%s %d %ld %c”, s[i].name, &s[i].age, &s[i].rollno , &s[i].section ) ;
}
for (i=0; i<= 49 ; i++ )
{
printf (“\nThe name, age, roll number and section of %d student is \n”,i+1);
printf (“%s %d %ld %c”, s[i].name, s[i].age, s[i].rollno , s[i].section);
} }
Nested Structures
C also provides the facility of nested structure i.e. declaring one structure within another structure. Following program illustrates this concept of nested structure:
/* Program – 3 : Nested structures */
#includemain ()
{
struct address
{
char street[20] ;
char city[20] ;
char state[15] ;
long int pincode;
};
struct stud
{
char f_name[20];
char l_name;
int age;
struct address addr;
};
struct stud s1 = {“Amit”, “Kr.”, 32, “Raj Marg”, “Bomby”, “MH” , 400001 } ;
struct stud s2 ;
printf (“\nEnter the first name , last name , age , street , city , state and pincode”);
scanf (“%s %s %d”, s2.f_name, s2_lname, s2.age) ;
scanf (“%s %s %s %ld”, s2.addr.street, s2.addr.city, s2.state, s2.addr.pincode);
printf (“\nFirst student record = ”);
printf (“\nFirst name = %s”, s1.f_name);
printf (“\nLast name = %s”, s1.l_name);
printf (“\nAge = %d”, s1.age);
printf (“\nStreet = %s”, s1.addr.street);
printf (“\nCity = %s”, s1.addr.city);
printf (“\State = %s”, s1.addr.state);
printf (“\nPincode = %s”, s1.addr.pincode);
printf (“\nSecond student record = ”);
printf (“\nFirst name = %s”, s2.f_name);
printf (“\nLast name = %s”, s2.l_name);
printf (“\nAge = %d”, s2.age);
printf (“\nStreet = %s”, s2.addr.street);
printf (“\nCity = %s”, s2.addr.city);
printf (“\State = %s”, s2.addr.state);
printf (“\nPincode = %s”, s2.addr.pincode);
}
The output of this program is as:
Enter the first name, last name, age, street, city, state and pincode
First name = Maggy
Last name = Dsouza
Age = 45
Street = Mal Road
City = Salcette
State = Goa
Pincode = 444000
First student record =
First name = Amit
Last name = Kumar
Age = 32
Street = Raj Marg
City = Bombay
State = MH
Pincode = 400001
Second student record =
First name = Maggy
Last name = Dsouza
Age = 45
Street = Mal Road
City = Salcette
State = Goa
Pincode = 444000
The main thing in this program is to note – how do we access members of structure, which is a part of another structure. In this program
struct address is used in struct stud.
Thus when we access the members of structure address through structure variables of type student_rec, we will use dot (.) operator twice as:
s1.addr.streets1.addr.city
s1.addr.state
s1.addr.pincode
The following program to swap Two numbers without using temp variable
int main()
{
int a=10,b=20;
printf("before swapping a=%d...b=%d",a,b);
a=a+b;
b=a-b;
a=a-b;
printf("after swapping a=%d...b=%d",a,b);
return 0;
}
Interesting C++ Program With Explanation
Program No.1
Raising a number n to a power p is the same as multiplying n by itself p times.Write a function called power ( ) that takes a double value for n and an int value for p, and returns the result as double value. Use a default argument of 2 for p, so that if thisargument is omitted, the number will be squared. Write a main( ) function that gets values from the user to test this function.
//Raising a number n to a power p is the same as multiplying n by itself p times.
#include//including file iostream
double power(double,int=2); //prototype of power function
int main(){
double n;
int p ;
std::cout<<"enter the number and its power to be calculated"<<"\n";
std::cin>>n>>p;
std::cout<<"\n"<<"it's square is :"<<"\n";
std::cout<
std::cout<<"\n"<<"power as you required is :"<<"\n";
std::cout<<"\n"<<<'\n';
return 0;
}
//power function calculates power of number n
//and returns ,default power is 2.
double power(double n,int p){
double q=1;
for(int i=0;i
q=q*n;
return q;
}
Here Is the Output:
Program No. 2
A point on the two dimensional plane can be represented by two numbers: an X coordinate and a Y coordinate. The sum of two points can be defined as a new point whose X coordinate is the sum of the X coordinates of the points and whose coordinate is the sum of their Y coordinates. Write a program that uses a structure called point to model a point. Define three points, and have the user input values to two of them. Than set the third point equal to the sum of the other two, and display the value of the new point.
// adding two points using structure and display new point.
#includestruct point
//structure defination
{ int x,y;
};
//Add function adds two point and return new point
point add(point p1,point p2)
{
point p3;
p3.x=p1.x+p2.x;
p3.y=p1.y+p2.y;
return p3;
}
main()
{
int x,y;
point p1,p2,p3;
std::cout<<"enter the x-coordinate :";
std::cin>>p1.x;
std::cout<<"enter the y-coordinate :";
std::cin>>p1.y;
std::cout<<"enter the x-coordinate for second point :";
std::cin>>p2.x;
std::cout<<"enter the y-coordinate for second point :";
std::cin>>p2.y;
p3=add(p1,p2); //calling add functions
std::cout<<"co-ordinates of third point is:"<<"\t"<<<"\t"<
return 0;
}
Here Is Output:
Program No. 3
Create the equivalent of a four function calculator. The program should request the user to enter a number, an operator, and another number. It should then carry out the specified arithmetical operation: adding, subtracting, multiplying, or dividing the two numbers. (It should use a switch statement to select the operation). Finally it should display the result. When it finishes the calculation, the program should ask if the user wants to do another calculation.
// Creating the equivalent of a four function calculator //using switch statement.
# includeint add(int a,int b) //adds two numbers and return new number
{
int c=a+b;
return c;
}
int sub(int a,int b) //subtracts two numbers and return new number
{
int c=a-b;
return c;
}
int multi(int a,int b) // multiplies two numbers and return new number
{
int c=a*b;
return c;
}
int divide(int a,int b) //it divides two numbers and return new number
{
int c=a/b;
return c;
}
int main()
{
int a,i,j;
char o;
char t='y’;
do {
std::cout<<"enter the first number ,operator & second number"<<"\n";
std::cin>>i>>o>>j;
switch (o)
{
case '+':
{
a=add(i,j);
std::cout<<"addition of two numbers is:\t"<
break; }
case '-':
{
a=sub(i,j);
std::cout<<"subtraction of two numbers is:\t"<
break; }
case '*':
{
a=multi(i,j);
std::cout<<"multiply of two numbers is:\t"<
break;
}
case '/':
{
a=divide(i,j);
std::cout<<"division result is:\t"<
break; }
defualt:{
std::cout<<"use (+,-,*,/) operators only";
break; }
}
std::cout<<"\n"<<"wanna try again press y/n"<<"\n";
std::cin>>t;
}while(t=='y');
}
Here Is Output:
Program No. 4
A phone number, such as (212) 767-8900, can be thought of as having three parts: the area code (212), the exchange (767) and the number (8900). Write a program that uses a structure to store these three parts of a phone number separately. Call the structure phone. Create two structure variables of type phone. Initialize one, and have the use number for the other one. Then display both numbers.
// create a phone number containing three parts area code, //exchange and number
//using structure variables.
#includeusing std::cout;
using std::cin;
using std::endl;
//creating structure phone having area code , exchange and //number
struct phone
{
int areacode;
int exchange;
int number;
};
//creating setnumber function having return type phone
//ignore is a member function of istream.
phone setnumber(phone &p3)
{
cin.ignore(); //ignore function ignores first brace ’(’
cin>>p3.areacode; //input area code
cin.ignore(1); //ignores ‘)’
cin>>p3.exchange; //input exchange part of phone number
cin.ignore(); //ignores ‘-’
cin>>p3.number; //input number
}
//creating a display function which display phone number
//in given pattern.
void display(phone &p3)
{
cout<<"("<<<")"<<<"-"<<
}
int main()
{
phone p2,p1;
cout<<"enter phone number in the form (212)767-8900:"<<"\t";
setnumber(p2); //sets phone number from user to p2
//initializing phone number to p1
p1.areacode=212;
p1.exchange=767;
p1.number=8900;
cout<<"my number is:";
display(p1); //display p1
cout<<"your number is:";
display(p2); //display p2
return 0;
}
Here Is Output:
Program No. 5
Create two classes DM and DB which store the value of distances. DM stores distances in meters and centimeters and DB in feet and inches. Write a program that can read values for the class objects and add one object of DM with another object of DB. Use a friend function to carry out the addition operation. The object that stores the results maybe a DM or DB objects, depending on the units in which the results are required. The display should be in the format feet in inches meters and centimeters depending on the object on display.
// create two classes dm & db stores distance in different scales carry out addition
//operation with objects of two classes using friend function
#includeusing std::cout;
using std::cin;
using std::endl;
class db; //forward declaration of class db
class dm
{
int meter,centi;
friend dm operator +(dm &,db &);
public:
dm();
dm(int m);
void insert();
void display();
};
dm::dm() //constructor
{
meter=0;
centi=0;
}
dm::dm(int m) //parameterised constructor
{
meter=m;
centi=100*m;
}
void dm::insert()
{
int m;
cout<<"enter value in meter:";
cin>>m;
meter=m;
centi=100*m;
}
void dm::display()
{
cout<<"result in meter is:";
cout<<<"m"<
cout<<"result in centimeter is:";
cout<<<"cm"<
}
class db
{
int feet,inch;
friend dm operator +(dm &,db &);
public:
db();
db(int f);
void insert();
};
db::db()
{
feet=0;
inch=0;
}
db::db(int f)
{
feet=f;
inch=12*f;
}
void db::insert()
{
int f;
cout<<"enter value in feet:";
cin>>f;
feet=f;
inch=12*f;
}
dm operator +(dm &d1,db &d2)
{
dm d3;
d3.meter=d1.meter+(d2.feet/3.28);
d3.centi=100*(d3.meter);
return d3;
}
int main()
{
dm d5,d6;
db d4;
d5.insert();
d4.insert();
d6=d5+d4;
d6.display();
return 0;
}
Here Is Output: