You cannot copy content of this page.

Monthly Archive December 2012

Virtual Base class


Virtual Base Class:

A virtual base class is one that is specified as virtual when it is inherited.  If the base class definition precedes the keyword virtual, then it is referred to as virtual base class.  If a situation arises, where the data members of a base class are inherited more than once to a derived class through different inheritance paths, as in the case of hybrid inheritance, the duplication is avoided by defining the base class as virtual.  When a base class is defined as virtual, then only one copy of the members of the base class is inherited, irrespective of the existence of different inheritance paths.

An example demonstrating the use of virtual base class is given below:

Example:

#include <iostream.h>
#include <conio.h>

class teacher
{
protected:
int s_id;
public:
void get_v()
{
cout<<“\nEnter school id>”;
cin>>s_id;
}
void put_v()
{
cout<<“\nSchool id=”<<s_id;
}
};

class science : virtual public teacher
{
protected:
int science_code;
float science_marks;
public:
void get_sc()
{
cout<<“\nEnter science code?”;
cin>>science_code;
cout<<“\nEnter marks in science?”;
cin>>science_marks;
}
void put_sc()
{
cout<<“\nScience code =”<<science_code;
cout<<“\nMarks in Science =”<< science_marks;
}
};

class maths : virtual public teacher
{
protected:
int maths_code;
float maths_marks;
public:
void get_mc()
{
cout<<“\nEnter code for mathematics?”;
cin>>maths_code;
cout<<“\nEnter marks in Maths?”;
cin>>maths_marks;
}
void put_mc()
{
cout<<“\nMaths code =”<<maths_code;
cout<<“\nMarks in Maths =”<<maths_marks;
}
};

class tests_conducted : public science, public maths
{
protected:
float total_marks;
public:
void compute()
{
total_marks = science_marks + maths_marks;
}
void put_info()
{
put_v();
put_sc();
put_mc();
cout<<“\nTotal Marks =”<<total_marks;
}
};

void main()
{
clrscr();
tests_conducted test;
test.get_v();
test.get_sc();
test.get_mc();
test.compute();
test.put_info();
getch();
}

 

Tags,

'inline' keyword

Advantage of using the keyword ‘inline’ before a function:

The member functions of a class may be defined inside the class definition or outside the class using scope resolution operator. The functions defined inside a class are inline by default. Generally, the functions, which are small, are defined inside a class definition.

If a function defined outside the class intends to be inline, then inline keyword is used before the function, as shown below:

class A
{       int x;
public:
void getx();
int square(int);
};

inline int A :: square(int a)
{
return(a*a);
}

With inline keyword the function call will be replaced by the function code by the compiler. But it is upon the wish of compiler to make any function inline or not even after inline keyword is used. Only small functions should be made inline. If the functions are bigger in size, then they should be declarations normal functions. Before calling an inline function, it is required that the function is defined elsewhere.

Tags,

Scope resolution operator in C++

Function of scope resolution operator:

In C++ the scope of a variable is from the point of its declaration till the end of the block in which it is defined. A variable defined outside a block is global whereas the variable defined inside a block is local to the block. If the two variables defined in different scope bear similar name, then the global variable (variable in the outer block) is not accessible from the inner block. To access the global version of the variable, scope resolution operator is used, preceding the variable name.

Consider the following example:-

//some code segment
—————————
—————————
{             float ans=5;
{
float ans = 10;
cont << “ans=”<<ans;
cont <<”ans=”<<::ans;
————————–
}
—————-
—————-
}

The first output statement results in a value 10, which overrides the global value of a variable, whereas the second output statement fetches the global value of the variable, i.e. 5, as scope resolution operator is used.

Tags,

Function Prototype & Function Overloading

Function Prototype:

Function prototype also referred to as function signature specifies the number of arguments and return type of the function to the compiler. Function prototype is required when a function is invoked/called before it is defined. The following statement defines function prototype.

            <Return type> function_name(arguments);

where return type is any valid C++ data type. The arguments are the parameters or values passed to the function when it is invoked. The argument variable names in prototype are optional.

Function Overloading:

Function overloading refers to defining different functions with the same name but with different arguments and return types. This is also referred to as functional polymorphism, as overloading is a form of polymorphism. This function to be invoked is determined by the type and number of arguments passed to that function.

For example: if we have to find the sum of two numbers of type int as well as float type we need not define two different functions with different names.  Now we can define both the functions bearing same name but different argument type.

int add (int a, int b);

float add(float a, float b);

Now the same function ‘add’ sums up two integer values and returns an integer as well as float values, thereby returning float value.

Tags,

Object Oriented Programming


Object Oriented Programming:

Object-Oriented Programming is a program design approach. It is incorporated with several features and new concepts, which are quite different from other programming techniques such as Modular programming, Structural programming or Procedural programming. It supports objects that are data abstraction with an interface of named operations and a hidden local state. It ties data along with their methods that operate on data. It supports data encapsulation feature by encapsulating the data, which cannot be accessed by external functions. Object orientation demands the concept of data encapsulation so that an object does not permit other objects to access its data and operates directly. The services of an object can be called upon through messages, classes are defined that contains the data members along with methods or functions that operate on data. Data Abstraction, which represents only essential features to the outside world, again is a striking feature of OOPs, besides this inheritance supports reusability and extensibility of code segments, polymorphism implemented through function overloading and operation overloading, compile time polymorphism or dynamic binding are some of the other features of OOPs.

It is different from conventional programming approaches, such as Modular programming, Procedural programming, Top-down & Bottom-up programming, Structural programming, as it incorporates powerful features as mentioned to provide extra power to the programming approach. OOPs model the real world objects with great ease, which was quite difficult with conventional programming languages. There was no data security feature and it moved freely around the system. Overloading, Inheritance, Dynamic binding of modules etc. empowered it further and thus proved to be a good programming approach over other programming approaches.

Tags

Search – Indexed Sequential Search


Indexed Sequential Search:

In this searching technique, first of all an index file is created that contains references to a group of records, once an index is obtained, the partial searching takes less time since it is to be located in the group/bucket specified by the index.  The program given below creates an index file for the employee records by grouping the records and then locates the required key by searching the index first and then returns the required record.  The program to implement indexed sequential search is given below:

/*Indexed Sequential Search*/

#include <stdio.h>
#include <conio.h>

#define MAX 10

struct mainfile
{int empid;
char name[25];
float basic;
};

struct indexfile
{int index_id;
int kindex;
};

void main()
{
struct mainfile fobj[MAX];
struct indexfile index[MAX];
int i,num,low,high,ct=4;
float basicsal;
clrscr();
for(i=0;i<MAX;i++)
{
printf(“\nEnter employee id?”);
scanf(“%d”,&fobj[i].empid);
printf(“\nEnter name?”);
scanf(“%s”,fobj[i].name);
printf(“\nEnter basic?”);
scanf(“%f”,&basicsal);
fobj[i].basic=basicsal;
}
printf(“\nNow creating index file…!”);
for(i=0;i<(MAX/5);i++)
{index[i].index_id=fobj[ct].empid;
index[i].kindex = ct;
ct=ct+5;
}

printf(“\n\nEnter the empid to search?”);
scanf(“%d”,&num);
for(i=0;(i<MAX/5) && (index[i].index_id<=num);i++);
low=index[i-1].kindex;
high=index[i].kindex;
for(i=low;i<=high;i++)
{if(num==fobj[i].empid)
{
printf(“\nThe record is: \n\t”);
printf(“\nEmpid: %d”,fobj[i].empid);
printf(“\nName: %s”,fobj[i].name);
printf(“\nBasic: %f”,fobj[i].basic);
getch();
return;
}
}
printf(“\nNumber not found…!”);
return;
}

 

Tags,

Sorting on multiple keys

Sorting on multiple keys

The sorting algorithm may be applied on multiple keys such that if first field contains duplicate values, then sorting is done on a secondary field and so on. However, if the first field contains unique values, then sorting is not applied on secondary field.  Say for example:

The input for the combination {studentname, feeamt}

{ (xyz,3000), (abc,1000), (xyz, 1000), (abc,3000)}; will result in the following output:

{ (abc,1000), (abc,3000), (xyz,1000), (xyz,3000) }.

Program to implement sorting on student names entered by the user followed by feeamt, such that wherever name is same, sorting is applicable on feeamt field is given below:

/*Sorting on multiple keys*/

#include <stdio.h>
#include <conio.h>
#include <string.h>

#define MAX 5

struct student
{char name[25];
int feeamt;
};

void sort_multiplekeys(struct student[]);

void main()
{
struct student s[MAX];
int i;
clrscr();
for(i=0;i<MAX;i++)
{printf(“\nEnter name?”);
scanf(“%s”,s[i].name);
printf(“Enter fee amount?”);
scanf(“%d”,&s[i].feeamt);
}
sort_multiplekeys(s);
printf(“\nOutput sorted on name followed by feeamt:\n\n”);
for(i=0;i<MAX;i++)
{printf(“\nName = %s”,s[i].name);
printf(“\nFeeamt = %d”,s[i].feeamt);
}
}
void sort_multiplekeys(struct student s[])
{
int i,j;
char temp[25];
float x;
clrscr();
/*loop to arrange names in ascending order*/
for(i=0;i<MAX-1;i++)
for(j=i+1;j<MAX;j++)
{if(strcmp(s[i].name,s[j].name)>0)
{
/*swapping names*/
strcpy(temp,s[i].name);
strcpy(s[i].name,s[j].name);
strcpy(s[j].name,temp);

/*swapping feeamt*/
x=s[i].feeamt;
s[i].feeamt = s[j].feeamt;
s[j].feeamt = x;
}
}
/*loop to arrange second field-feeamt in ascending order*/
for(i=0;i<MAX-1;i++)
for(j=i+1;j<MAX;j++)
{if(strcmp(s[i].name,s[j].name)==0)
{if(s[i].feeamt>s[j].feeamt)
{
/*swapping feeamt*/
x=s[i].feeamt;
s[i].feeamt=s[j].feeamt;
s[j].feeamt=x;
}
}
}
}

 

Tags,

Sorting – Address Calculation Sort (Hashing)

Sorting – Address Calculation Sort (Hashing)

  • In this method a function f is applied to each key.
  • The result of this function determines into which of the several subfiles the record is to be placed.
  • The function should have the property that: if x <= y ,  f (x) <= f (y), Such a function is called order preserving.
  • An item is placed into a subfile in correct sequence by placing sorting method – simple insertion is often used.

Example:

25         57         48         37         12         92         86         33

Let us create 10 subfiles.  Initially each of these subfiles is empty.  An array of pointer f(10) is declared, where f(i) refers to the first element in the file, whose first digit is i.  The number is passed to hash function, which returns its last digit (ten’s place digit), which is placed at that position only, in the array of pointers.

num=    25         –           f(25) gives 2
57         –           f(57) gives 5
48         –           f(48) gives 4
37         –           f(37) gives 3
12         –           f(12) gives 1
92         –           f(92) gives 9
86         –           f(86) gives 8
33         –           f(33) gives 3 which is repeated.

Thus it is inserted in 3rd subfile (4th)  only, but must be checked with the existing elements for its proper position in this subfile.

Address Calculation Sort

Arrangement of nodes in subfiles

Efficiency:  If all the elements (n) are uniformly distributed over m subfiles then n/m is approximately 1, time of the sort is near O(n).

On the other hand if maximum elements accommodate in one or two subfiles, then n/m is much larger significant work is required to insert its proper subfile at its proper position and efficiency is O(n2).

Program to implement Address Calculation Sort:

/*Address Calculation Sort*/
/*It uses a hash function that can sort only 2 digit nos.*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 5

struct list
{int info;
struct list *next;
}*node[10]={NULL};

struct list *create()
{
struct list *temp=(struct list *)malloc(sizeof(struct list));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}

struct list *makenode(int num)
{
struct list *temp;
temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}

struct list *insert(struct list *s,int num)
{
struct list *ptr,*temp;
ptr=s;
temp=makenode(num);
if(s==NULL)
s=temp;
else
{
/*code for placing new node at appropriate
position in the subfile*/
while((ptr->next->info<=num) && (ptr->next!=NULL))
{ptr=ptr->next;
}
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}

/*A hash function that operates upon two digit
numbers only*/

int hashfun(int n)
{return (n/10);
}

void addr_calc(int arr[],int size)
{
int i,j=0,pos;
for(i=0;i<size;i++)
{pos=hashfun(arr[i]);
node[pos]=insert(node[pos],arr[i]);
}
for(i=0;i<10;i++)
{while(node[i]!=NULL)
{arr[j++]=node[i]->info;
node[i]=node[i]->next;
}
}
printf(“\nSorted output is: “);
for(i=0;i<size;i++)
printf(“%d\t”,arr[i]);
getch();
}

void main()
{
int arr[MAX],i,n;
clrscr();
printf(“Enter total numbers to sort?”);
scanf(“%d”,&n);
printf(“Enter numbers?”);
for(i=0;i<n;i++)
scanf(“%d”,&arr[i]);
addr_calc(arr,n);
}

 

Tags,

Sorting – Quick Sort (Partition Exchange Sort)

Sorting – Quick Sort (Partition Exchange Sort)

Suppose x be an array, n is the number of elements.  Choose an element from a specific position within the array.  Array x is partitioned so that y is placed into position j, and the following conditions hold:

1)      Each of the elements in position 0 through (j-1) is less than or equal to y.
2)      Each of the elements in position (j+1) through (n-1) is greater than or equal to y.

Example:

Let key element = lb = arr[0] = 14

Now i will move forward until arr[i] becomes greater than key value.  Finally i is positioned at 15.

Similarly j shifts backward until arr[j] becomes lower than key value.  Finally j is positioned at 11.

Now, swap(arr[i],arr[j]);

Now the same set of routines are again called with new values of i and j i.e. lb and ub.

Now i is positioned at 15, since 8 is less than 14.  Similarly j is positioned at 8.

Now i<=j condition is false i.e. upper bound is lower than lower bound which must be higher.

Now swap(arr[j],key);

Then all smaller values (for  key) are aligned to left and greater values to right.  Now partition it in two parts (8,7,3,11) and (15,16,25).  Repeat the same process again.  Finally combine all segments – (left, key, right) to obtain sorted array.

Program to implement Quicksort:

#include <stdio.h>
#include <conio.h>

#define MAX 10

void quicksort(int arr[],int lb,int ub);
int partition(int arr[],int lb,int ub);

void main()
{
int arr[MAX],i,n,keyelement,lb,ub;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
printf(“\nEnter elements?”);
for(i=0;i<n;i++)
{scanf(“%d”,&arr[i]);
}
keyelement = arr[0];
lb=0;
ub=(n-1);
quicksort(arr,lb,ub);
printf(“\nSorted Array is: “);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}

void quicksort(int arr[],int lb,int ub)
{
int j;
if(lb>=ub)
return;
j=partition(arr,lb,ub);
quicksort(arr,lb,j-1);
quicksort(arr,j+1,ub);
return;
}

int partition(int arr[],int lb,int ub)
{
int a,down,temp;
a=arr[lb];
down=lb;
while(lb<ub)
{while((arr[lb]<=a) && (lb<ub))
lb++;
while(arr[ub]>a)
ub–;
if(lb<ub)
{temp=arr[lb];
arr[lb]=arr[ub];
arr[ub]=temp;
}
}
temp=arr[ub];
arr[ub]=a;
arr[down]=temp;
return ub;
}

 

Tags,

Sorting – Merge Sort

Sorting – Merge Sort

Merging:-  Merging is the process of combining two or more sorted files into a third sorted file.  An example of a routine that accepts two sorted arrays a and b of n1 and n2 elements  respectively and merges them into a third array c containing n3 (n1+n2) elements.

Steps for Merge Sort:

  • Divide the file n subfiles of size 1 and merge adjacent pair of files.
  • We then have approximately n/2 files of size 2.
  • Repeat this process until there is only file of size n.
  • An auxillary array aux, of size n is required to hold the results of merging two subarrays of x.  The variable size contains the size of the subarrays being merged.  Since at any time the two files being merged are both subarrays of x, lower and upper bounds are required to indicate the subfiles of x being merged.  l1 and u1 represents the lower and upper bounds of the first file and l2 and u2 represents the lower and upper bounds of the second file respectively.  i and j are used to reference elements of the source files being merged and k indexes the destination file aux.

Program to merge two sorted arrays to result in another sorted array:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

int checksort(int arr[],int n)
{
int i,j,temp,flag=1;
for(i=0;i<n-1;i++)
{for(j=i+1;j<n;j++)
{if(arr[i]>arr[j])
{flag=0;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return flag;
}

void mergearr(int a[], int b[], int c[], int n1,int n2,int n3)
{
int al,bl,cl,ah,bh,ch,i;/*l for low, h for high*/
ah=n1-1;
bh=n2-1;
ch=n3-1;
if(n1+n2!=n3)
{printf(“\nArray bounds not proper!”);
exit(1);
}
al=0;
bl=0;
for(i=0;al<=ah && bl<=bh;i++)
{if(a[al]<b[bl])
c[i]=a[al++];
else
c[i]=b[bl++];
}
while(al<=ah)
c[i++]=a[al++];
while(bl<=bh)
c[i++]=b[bl++];
}

void main()
{
int a1[MAX],a2[MAX],a3[MAX],n1,n2,n3,i;
clrscr();
printf(“\nEnter the size of first array?”);
scanf(“%d”,&n1);
printf(“\nEnter the size of second array?”);
scanf(“%d”,&n2);
printf(“\nEnter elements of first array?”);
for(i=0;i<n1;i++)
{scanf(“%d”,&a1[i]);
}
printf(“\nEnter elements of second array?”);
for(i=0;i<n2;i++)
{scanf(“%d”,&a2[i]);
}
n3=n1+n2;
if(!checksort(a1,n1))
{printf(“\nMerging operates on sorted array.”);
printf(“\nFirst Array you entered is not sorted.”);
printf(“\nSorting array 1….”);
printf(“\nPress any key to continue!”);
getch();
}

if(!checksort(a2,n2))
{printf(“\n\nMerging operates on sorted array.”);
printf(“\nSecond Array you entered is not sorted.”);
printf(“\nSorting array 2….”);
printf(“\nPress any key to continue!”);
getch();
}

printf(“\n\nNow Merging both the sorted arrays…\n”);
mergearr(a1,a2,a3,n1,n2,n3);

printf(“\nMerged sorted array is:”);
for(i=0;i<n3;i++)
printf(“%d\t”,a3[i]);
getch();
}

Program to implement Merge sort:

#include <stdio.h>
#include <conio.h>

#define MAX 10

void mergesort(int x[], int n)
{
int aux[MAX],i,j,k,l1,l2,u1,u2,size;
size=1;/*initially size is 1.*/
while(size<n)
{
l1=0;
k=0;/*k is the index of auxillary array.*/
while((l1+size)<n)
{l2=l1+size;
u1=l2-1;
u2=((l2+size-1)<n)?(l2+size-1):n-1;
for(i=l1,j=l2;i<=u1 && j<=u2;k++)
{if(x[i]<=x[j])
aux[k]=x[i++];
else
aux[k]=x[j++];
}
/*Remaining elements of first array*/
for(;i<=u1;k++)
aux[k]=x[i++];
/*Remaining elements of second array*/
for(;j<=u2;k++)
aux[k]=x[j++];
/*Advance l1 to the start of the next pair of files.*/
l1=u2+1;
}
for(i=l1;k<n;i++)
aux[k++]=x[i];
for(i=0;i<n;i++)
x[i]=aux[i];
size *= 2;
}
}

void main()
{
int array[MAX],i;
clrscr();
printf(“Enter array elements?”);
for(i=0;i<MAX;i++)
scanf(“%d”,&array[i]);
mergesort(array,MAX);
printf(“Sorted elements are: “);
for(i=0;i<MAX;i++)
printf(“%d\t”,array[i]);
getch();
}

 

Tags,

x Close

Like Us On Facebook