Binary Search Tree

I am indeed returning to this blog after almost 3 years.

As I have got more involved with Oracle ( love that product ) I was just checking how good my C, C++ coding skill is.

So first I took up a doubly linked list in C, coding came natural and easy and everything worked perfect.A menu driven interface to add, traverse, delete the list.

Next I took up a data base code in c++. Again menu driven program - Add, print, search, modify, delete a data structure with name, age as its components. Tough but could succeed. I had already done this code , so looked into it. Happy that I could code/debug with ease. Any one who has coded for file management knows the kind of issues one runs into - when one deletes/modifies record, the file is filled with infinite garbage data !! And this is C+, no FILE * concept - everything is class based , the ios class hierarchy is complex.

Having succeeded with that, I took up a Binary Search Tree program - Add, traverse inorder and print sorted data, remove an element. Add, traverse were not difficult to code, but removing a node from the binary search tree - Oh that was tough and kept me working at least 4 to 5 days . I looked up all the code lying around on the internet - but I want to master the ability to write the code myself with perfect understanding.

Recursive functions are tough to analyse, so I tried writing simple functions. One function required I write another, so I kept coding more and more functions. The beauty was now pointer manipulation came so easy. It was not tough to write p -> parent -> left -> right -> data.

I wrote a menu driven program in C++ for randomly inserting, printing sorted data and removing data .

Anyway the purpose of writing this blog is that I ended up with a final code around 400 lines, with many functions - looked more complex than any of those codes I found complex - made me laugh at myself. Along the way, I created complex requirements like printing tree statistics ( depth, number of nodes, order of original data entry, current node address, parent node address, is it a left/right/root node etc.. and got struck in the logic .

It was fun and lot of skill sharpening. Any one who wants to master coding skill must take up data structures like lists and trees - endless challenges here. And when I am playing the Oh so very addictive - Angry Birds game , I am wondering at the logic of the code behind. It must have been maddening to develop such an application.



# include
# include
# include

typedef int bool;
enum { true = 1 , false = 0 };
enum { ROOT = 0 , LEAFNODE = 1, WITH_SINGLE_SUBTREE = 2 , WITH_BOTH_SUBTREES = 3};



class bSearchTree
{
protected:
struct treeNode
{
int data ;
treeNode *left;
treeNode *right;
treeNode *parent;
char nodeType ;
};
struct treeInfo
{
treeNode * address;
int data;
treeNode * parentAddress;
treeInfo *next;

char nodeType;
};

treeNode * root ;
treeInfo *info , *prevInfo, *startInfo;
int depth ;
int isEmpty () const { return root==NULL; }
void inorder(treeNode *p);

treeNode *getNode(int data, treeNode *p);

bool removeNode(treeNode *t, int data);

int getNodeType(treeNode *t);

void printNode(int data);
void printNodeType(int data);

treeNode* getLargestRight(treeNode * p, int & replaceData);
treeNode* getSmallestLeft(treeNode * p, int & replaceData);
void removeFromTreeInfo(treeNode *p);


public:

bSearchTree () { root = NULL; depth = 0 ; nodeCount = 0 ; }

void insert(int data);
void remove(int data);
void print(){inorder(root);}

int nodeCount ;

int count () { return nodeCount ; }
void printTreeInfo();
int getTreeDepth(treeNode *t);
};

int bSearchTree::getTreeDepth(treeNode *t)
{
if (t == NULL)
return 0 ;
else
{
int lDepth = getTreeDepth(t -> left);
int rDepth = getTreeDepth(t -> right);
if ( lDepth > rDepth)
return lDepth + 1 ;
else
return rDepth + 1 ;
}
}


void bSearchTree::printTreeInfo()

{
clrscr();

cout << "Tree Information \n\n Tree Type: Binary Search Tree ";

cout << "\n\n Number of nodes : " << nodeCount ; cout << "\n\nDepth : " << getTreeDepth(root);

cout << "\n\nNode Address\tData\tParent Address\tNode Type\n";

treeInfo *ptr = startInfo ;

while(ptr)
{
cout <<"\n\n"<< ptr->address<<"\t"< data << "\t" << ptr -> parentAddress<<"\t";

switch( ptr->nodeType)
{
case 'R' :
cout <<"Root" ;
break;
case 'l' :
cout <<"Left";
break;
case 'r' :
cout << "Right";
break;
}
ptr = ptr -> next;
}
}




int bSearchTree::getNodeType(treeNode *t)
{
int nodetype ;

if ( t == root) nodetype = ROOT ;
else
if ( t -> right == NULL && t -> left == NULL )
nodetype = LEAFNODE;
else
if( (t -> right == NULL && t-> left != NULL ) || ( t -> left == NULL && t -> right != NULL ))
nodetype = WITH_SINGLE_SUBTREE ;
else
if ( t -> right != NULL && t-> left != NULL)
nodetype = WITH_BOTH_SUBTREES ;

return nodetype;
}

void bSearchTree::printNodeType(int data)
{
switch ( getNodeType( getNode(data, root)))
{
case ROOT:
cout << "\nRoot" ; break ; case LEAFNODE: cout << "\nLeaf Node "; break; case WITH_SINGLE_SUBTREE : cout << "\nWith single subtree.. " ; break; case WITH_BOTH_SUBTREES : cout << "\nWith both subtrees" ; } } bSearchTree::treeNode *bSearchTree::getNode(int data, treeNode *p) { if (p == NULL ) return NULL; if (p -> data == data) return p ;
if ( p -> left) getNode(data, p -> left);
//cout << "\t" << p->data ;
if(p -> right) getNode(data, p -> right);
}

void bSearchTree::printNode(int data)
{
treeNode *t = getNode(data, root);
if (t)
cout << "\nData at node " << t << " Parent = " << t -> parent ;
else
cout << "\nData not found " ; } void bSearchTree::insert(int data) { treeNode *t = new treeNode(); t -> data = data;
t -> left = NULL;
t -> right = NULL ;
t -> parent = NULL ;


nodeCount++;

treeNode *curr , *parent;
curr = parent = NULL;
if (isEmpty() )
{ root = t ;
t -> nodeType = 'R' ;
t -> parent = NULL ;

/* update tree info */


info = new treeInfo();
info -> next = NULL ;
info -> address = root;
info -> parentAddress = NULL;
startInfo = info ;
info -> data = data ;
info->nodeType = root -> nodeType;
prevInfo = NULL ;
return ;
}


curr = root ;

while(curr)
{
parent = curr;
if( t -> data > curr -> data)
curr = curr -> right ;
else
curr = curr -> left ;
}

if ( t -> data <= parent -> data)
{parent -> left = t ;
t -> nodeType = 'l' ;
}

else
{ parent -> right = t ;
t -> nodeType = 'r' ;
}
t -> parent = parent ;
/* update tree info */
prevInfo = info ;

info = new treeInfo();

prevInfo -> next = info;

info -> address = t;
info -> parentAddress = t -> parent ;
info -> data = data ;
info -> next = NULL ;
info -> nodeType = t -> nodeType;
depth = getTreeDepth(root);

}

void bSearchTree::inorder(treeNode *p)
{
if (p == NULL ) return ;
if ( p -> left) inorder(p -> left);
cout << "\t" << p->data ;
if(p -> right) inorder(p -> right);
}

treeNode* bSearchTree::getLargestRight(treeNode * p, int & replaceData)
{
// traverse right till u have located the last in the line
treeNode *curr, *t ;
t = curr = p;
while(t )
{
curr = t ;
replaceData = t -> data ;
cout << "\nreplace data = " << replaceData << "\n" ; getch(); if ( t -> right )
t = t -> right;
else if( t -> left)
t = t -> left -> right ;
else break ;
}
cout << "\nout of glr ...."; return curr ; } treeNode* bSearchTree::getSmallestLeft(treeNode *p, int & d) { // traverse left till u have located the last in the line treeNode *curr, *t = p ; while(t ) { curr = t ; d = t -> data;
cout << "\nreplace data = " << d << "\n" ; getch(); if( t -> left )
t = t -> left ;
else if ( t -> right)
t = t -> right -> left ;
else
break ;
}
return curr;
}
void bSearchTree::removeFromTreeInfo(treeNode *p)
{
treeInfo *prev, *ptr= startInfo;

while(ptr)
{
prev= ptr ;
if (ptr -> address == p )
{
prev -> next = ptr -> next ;
delete ptr;
break;
}
else
ptr = ptr -> next;
}
}




void bSearchTree::remove(int data)
{
if (removeNode(root, data))
{
cout <<"\n\nSuccessful deletion of " << data << "\n\n" ; nodeCount--; depth = getTreeDepth(root); } else cout <<"\n\nDeletion of " << data << " Failed \n\n" ; getch(); } bool bSearchTree::removeNode(treeNode *t, int data) { bool removed = false; if (isEmpty() ) { cout << "\n\nEmpty Tree\n\n"; return false;} treeNode *p = getNode(data, t); int x = 0; int &replaceData = x ; treeNode *toDelete ; if ( !p ) { cout << "\nData does not exist. \n" ; return false; } // data does not exists int nodetype ; nodetype = getNodeType(p) ; //printNodeType(data); //getch(); treeInfo *deletedInfo , *infoPtr ; switch ( nodetype) { case LEAFNODE : (p -> parent) -> left = (p -> parent ) -> right = NULL;
cout << "\nDeleted a leaf node with "<< data << "\n "; removeFromTreeInfo(p); delete p ; removed =true; break ; case WITH_SINGLE_SUBTREE : // 4 possibilities if ( (p -> parent) -> left -> data == data) //delete left node
{ cout << "\nDeleting a left node \n" ; if (p -> left != NULL )
p-> parent -> left = p -> left ;
else if(p -> right != NULL)
p -> parent -> left = p -> right;
}
else if ( p -> parent -> right -> data == data ) // delete right node
{
cout << "\nDeleting a right node\n"; if (p -> left != NULL )
p -> parent -> right = p -> left ;
else if(p -> right != NULL)
p -> parent -> right = p -> right;
}
removed = true;
removeFromTreeInfo(p);
delete p ;

break ;

case WITH_BOTH_SUBTREES :
if ( data <= root -> data ) // left node
{
toDelete = getLargestRight(p->left, replaceData);
cout << "\nReplacing " << data << " with " << replaceData ; cout << " and deleting node at " << toDelete ; getch(); p -> data = replaceData ;
toDelete -> parent -> right = NULL ;
if ( toDelete -> left != NULL)
toDelete -> parent -> right = toDelete -> left ;
removeFromTreeInfo(toDelete);
delete toDelete;

}
else
if ( data > root -> data ) // right node
{
toDelete = getSmallestLeft(p, replaceData);
cout << "\nReplacing " << data << " with " << replaceData ; cout << " and deleting node at " << toDelete ; getch(); p -> data = replaceData ;
toDelete -> parent -> left = NULL ;
removeFromTreeInfo(toDelete);
delete toDelete;
}
removed = true;
break;

case ROOT:

if( p -> left) // left subtree exists
{
p -> data = p -> left -> data ;
cout << "\nLeft. Root replaced with " << p -> data << "\n" ; getch(); toDelete = getLargestRight(p -> left, replaceData) ;
cout << "\nfn returned Deleting node " << toDelete << " with data " << toDelete -> data << "\n"; getch(); toDelete -> parent -> right = NULL ;
if ( toDelete -> left != NULL)
toDelete -> parent -> right = toDelete -> left ;

p -> left -> data = replaceData ;
cout << "\ndeleting " << toDelete<< "\n" ; getch(); removeFromTreeInfo(toDelete); delete(toDelete); } else if ( p -> right) // suppose the root does not have a left node ??
{
p -> data = p -> right -> data ;
cout << "\nRight Root replaced with " << p -> data << "\n" ; getch(); toDelete = getSmallestLeft(p -> right, replaceData) ;
p -> right -> data = toDelete -> data ;
if ( toDelete -> right)
toDelete -> parent -> left = toDelete -> right;
removeFromTreeInfo(toDelete);
delete(toDelete);

}
else // the root is a single node
{
cout << "The root is a leaf root!! \n\nDeleting root will remove the tree itself\n" ; getch(); toDelete = root ; removeFromTreeInfo(toDelete); delete toDelete ; } getch(); removed = true ; break ; default: removed = false; } return removed; } int displayMenu() { int option ; clrscr(); int y = 3 ; int x = 30 ; gotoxy(x, y); cout << "Binary Search Tree"; y = 10; x = 20; gotoxy(x, y); cout << "1. Insert Data"; y = y + 5; gotoxy(x, y); cout << "2. Print Sorted Data "; y = y + 5; gotoxy(x, y); cout << "3. Print Tree Information"; y = y + 5; gotoxy(x, y); cout << "4. Delete Data"; y = y + 5; gotoxy(x, y); cout << "5. Close Application"; y = y + 10; gotoxy(x, y); cout << "Enter Menu option : "; cin.clear(); cin >> option ;

return option ;
}









main()
{
clrscr();
bSearchTree tree;
int data , option = 1;
while (option != 5)
{
clrscr();
option = displayMenu();
char ans = 'y' ;

switch (option)
{

case 1 :
clrscr();

while(ans == 'y' || ans =='Y')
{
cout << "\nEnter data to insert "; cin >> data;
tree.insert(data);
cout <<"1 node inserted\n\n"; cout<<"One more insert?? "; cin >> ans;
}
break;
case 2 :
clrscr();
cout << "Inserted Data in sorted order as follows:-\n\n" ; tree.print(); getch(); break; case 3 : tree.printTreeInfo(); getch(); break; case 4 : int data ; clrscr(); tree.print(); cout << "Enter data to delete " ; cin >> data ;
tree.remove(data);
getch();
break;
case 5:
default : break;
}
}
getch();
return 0 ;
}



=================================================================================

It was fun and lot of skill sharpening. Any one who wants to master coding skill must take up data structures like lists and trees - endless challenges here. And when I am playing the Oh so very addictive - Angry Birds game , I am wondering at the logic of the code behind. It must have been maddening to develop such an application.

One important learning was how to give a very simple public interface to a class and make the public functions call complex private functions, passing parameters which may be private variables. I liked that. Like tree.print() calls another function which requires the tree root to be passed to it as a parameter. On a public interface tree.print() is simpler than tree.print(tree.root) !!


When I copy/pasted a perfectly indented code into the blog editor, the final look of the code is a bit messed up in places and I am trying to figure out why it is so.

Dynamic Memory Allocation

DMA - Dynamic memory allocation

This means memory is allocated for a variable at runtime as and when a request is made .When we use char pointers to store data , we usually have just declared a pointer like char *ptr . Here ptr is allocated a memory of 2 bytes only.If we now want to store data we first have to allocate enough memory for that data . We have to call malloc( ) . In that call we have to specify how many bytes of space we need . malloc() returns a pointer to such a location

malloc( ) : The function malloc( ) Allocates memory

Declaration : void *malloc(size_t size);

malloc( ) allocates a block of size bytes from the memory heap. It allows a program to allocate memory explicitly as it's needed, and in the exact amounts needed. On success, malloc returns a pointer to the newly allocated block of memory. On error (if not enough space exists for the new block), malloc returns null. contents of the block are left unchanged.If the argument size == 0, malloc returns null.We have to explicitly typecast the kind of pointer we want as malloc() returns a void * by default . A void pointer is called as a generic pointer. It can be typecast into different types of pointers

free( ) : The function free( ) is called with pointers to free the memory allocated with malloc( ) e.g free(ptr);

Strings in C

Strings

What is a string ?

Any data enclosed in double quotes like “ Welcome” is termed as a string in C . The data structure used to represent a string could be an array or a pointer

E.g char name[20] = “Focus Systems”;
Here name is an array holding the string “Focus Systems”
char *str = “Team work”
Here str is a pointer . It is the starting address of the string str . It holds
the address of the first letter ‘T’

End of string marker : ‘\0’
Every string is characterized by an end of string marker ‘\0’ (backslash zero or null character or ascii 0 ). This indicates that the string fininshes here . Thus memory allocation for a string is 1 more than the number of characters in it.

String length :
The length of a string is the number of characters in a string including space , tabs , new lines . It does not include ‘\0’

String.h :
The header file string.h contains several useful functions for string manipulations like strlen() , strcpy() , strcmp(), strcat() etc
Some Commonly used string functions are :
strcpy( ) :Copies one string into another
Prototype : char *stpcpy(char *dest , const char *src);
strcpy( ) function copies the string src to dest, stopping after the terminating null character of src has been reached.

strlen( ) : Calculates length of a string
Declaration: size_t strlen(const char *s);
strlen( ) calculates the length of s. Returns the number of characters in s, not counting the terminating null character.

strcmp( ) compare two strings
stricmp( ) , strcmpi( ) compares two strings without case sensitivity
Declaration :
int strcmp(const char *s1, const char*s2);
int strcmpi(const char *s1, const char *s2)
int stricmp(const char *s1, const char *s2);
strcmp() performs an unsigned comparison of s1 to s2.
strcmpi() or stricmp() performs an unsigned comparison of s1to s2, without case sensitivity. The string comparison starts with the first character in each string and continues with subsequent characters until the corresponding characters differ or until the end of the strings is reached.

strcat( ) Appends one string to another
Declaration: char *strcat(char *dest, const char *src);
Strcat( ) appends a copy of src to the end of dest. The length of the resulting string is strlen(dest) + strlen(src). strcat returns a pointer to the concatenated
strings.

strchr( ) Scans a string for the first occurence of a given character
Declaration: char *strchr(const char *s, int c);
strchr scans a string in the forward direction, looking for a specific character.
It finds the first occurrence of the character c in the string s.The null-terminator of the string; for Program strchr(strs, 0) returns a pointer to the terminating character of the string str.


Strings and Dynamic memory allocation :-
As strings are often represented as pointer we may often require to allocates some memory and then read a string into that pointer variable.

For e.g
void main( )
{
char *p ;
p = (char *) malloc (80 * sizeof(char) ) ;
if ( p == NULL )
{
printf(“Allocation failure”);
return 1 ;
}
printf(“Enter a line of text :- “);
gets(p);
printf(“\nYou entered %s” , p );

}

Strings and 2d arrays :-
A data structure like char str[10][80] can be used to store a maximum of 10 strings each with a maximum size of (80 – 1 ) characters whether we use or not a space of 10 X 80 X sizeof(char) is allocated here .

Strings and Array of Pointers :-
A data structure like char *ptr[10] can be used to store 10 strings of varying lengths. Here you allocate memory as and when needed using malloc( ) function . ptr[0] , ptr[1] , ptr[2] … each point to a different location holding a different (length) string . The advantage here is that memory is not blocked unutilized.

E.g:- Program accepts lines of text from the user and outputs in alphabetically sorted order. The program swaps pointers to read data in a sorted order rather than rearranging data to

# define MAXSIZE 10

main( )
{
char *ptr[MAXSIZE] , str[80] ;
char ans = ‘y’ ;
int j , k , len , count ;

clrscr( ) ;

j = 0 ;

while( (ans == ‘y’ || ans == ‘y’ ) && j < len =" strlen(str);"> 0 )
break ; /* At least one string was input so proceed further */
else
return 1 ; /* no strings were input */
}

j++;
printf(“\nOne more line to input ? [y/n] :- “);
fflush(stdin);
ans = getchar( ) ;
}

count = j ; /* count holds number of lines entered */

printf(“\n\nYou entered %d lines of text in this order :\n\n” , count);

for(j = 0 ; j < j =" 0" k =" j+1"> 0 ) /* Compare lines */
{
/* Now swap pointers
char *t ;
t = ptr[ j ] ;
ptr[ j ] = ptr [ k ] ;
ptr [ k ] = t ;
}

printf(“\n\n The lines are sorted as follows :- \n\n”);

for(j = 0 ; j < count ; j++ )
puts ( ptr [ j ] );

getch( );
return 0 ;

}

Why do we call fflush(stdin) in the above program ?

stdin is a pointer to the input ( keyboard buffer) stream . When ever we input data we press the enter key as an indication that the input is over. Next time we attempt to read a character as an input this enter key gets read as an input. This prevents us from reading any further input.A call to the function fflush( stdin ) clears the input buffer of any key that might be lingering .

union , enum , typedef :

union

The keyword union is useful in defining a new data type like a structure. Its usage is also similar in syntax to a structure. But conceptually union and structures differ in the way they manage memory.In a structure memory is allocated for each member . In Union same memory is shared by all data members

Thus a structure variable requires memory = sum of the memory requirements of all its members

A union variable requires memory = maximum memory requirement of one member

Thus union allows us to interpret the same memory location

in different ways .

union sample

{

int x ;

float y ;

char ch ;

} p ;

Thus here p occupies 4 bytes. Byte 0 is interpreted as char ch . Byte 0 , byte1 together as int x , .All the four bytes together are read as float y . Changing the value of one data member may affect value of all other members.

Program:

union A

{

int x ;

char ch[2] ;

};

void main( )

{

union A var ;

var.x = 260 ;

printf(“%d %d” , var.ch[0] , var.ch[1] );

var.ch[0] += 10 ;

printf(“\nx = 5d” , var.x );

var.ch[1] += 2 ;

printf(“\nx = %d” , var.x);

}

Memory allocated for var => 2 Bytes or 16 bits

var.x = 260 -> 0000 0001 0000 0100

var.ch[0] - > 0000 0100 /* prints 4 */

var.ch[1] - > 0000 0001 /* prints 1 */

var.ch[0] += 10

var.ch[0] - > 0000 1110 /* now 14 */

var.x -> 0000 0001 0000 1110 /* now 270 */

var.ch[1] += 2 ;

var.ch[1] - > 0000 0011 /* 3 */

var.x - > 0000 0011 0000 1110

/* 512 + 256 + 14 = 782 */

Application of unions :-

There is a frequent requirement while interacting with hardware that the same data be interpreted differently

For e.g : Unions are useful in reading and manipulating CPU registers and availing various BIOS services (calling int86( ) function)

CPU registers are 2 bytes in size .We may access the information they store as 2 bytes entirely or as two information of one byte each.

What is an interrupt ?

An interrupt means to stop doing something and instead do something else. Keyboard interrupts are generated by pressing control key , (and or) alt keys , shift key along with some other key. An operating system has a table of interrupt numbers (Interrupt Vector Table IVT) and actions to be taken when the interrupt is encountered.

For e.g

ctrl + C : by pressing ctrl + C (^C) you might stop some

process

PrintScreen : By pressing the PrintScreen key you are generating an interrupt

An interrupt is serviced by the Operating system

You can call various dos interrupt services using int86( ) function (include

Declaration:

int int86(int intno, union REGS *inregs, union REGS *outregs);

inregs holds the values of A , B , C, D registers that are set before the function call

outregs holds the values of A , B , C , D registers after the call

Return Value:

The functions returns the value of AX register after completion of the software interrupt.

Programs: int86( ) function

#include

#include

#include

#define VIDEO 0x10

void movetoxy(int x, int y)

{

union REGS regs;

regs.h.ah = 2; /* set cursor position */

regs.h.dh = y;

regs.h.dl = x;

regs.h.bh = 0; /* video page 0 */

int86(VIDEO, &regs, &regs);

}

­

REGS

REGS (union)

The union REGS is used to pass information to and from these functions . It is defined as follows :-

union REGS {

struct WORDREGS x;

struct BYTEREGS h;

};

BYTEREGS and WORDREGS

Structures for storing byte and word registers

struct BYTEREGS {

unsigned char al, ah, bl, bh;

unsigned char cl, ch, dl, dh;

};

struct WORDREGS {

unsigned int ax, bx, cx, dx;

unsigned int si, di, cflag, flags;

};

Enumerated Data Types :-

The keyword enum helps us to define named integral constants .The advantage :

Improved readability and program documentation.

We use #defines to define constants. Here the datatype is not specific .But with enums the constants are of type int .

Program:

enum status { false , true };

here the constant false is assigned a value 0 and the constant true is assigned a value 1

We may have a code line such as

return true ;

or found = false ;

Program:

enum colors { red , green , blue } ;

Here the constant red has a value 0 , green 1 , blue 2

You might write code like

COLOR background, foreground;
background = blue ;
foreground = red;

Values may be redefined as

enum E1 { c1 = 100 , c2 , c3 };

In this case c1 is assigned a value 100 , c2 = 101 , c3 = 102 and so on .

By default the named constants take incremental values starting with 0 ( 0 , 1 , 2 , 3 .... )
One is free to change these values while defining such as

enum sample { x = 1 , y = 10 , z = 20 } ;
or
enum sample { a , b , c = 10 , d , e , f = 100 , g , h };
here values of a to h are a = 0 , b = 1 , c = 10 , d = 11 , e = 12 , f = 100 , g = 101 , h = 102

The C std library includes lot of enums and one can freely use them in code. IF given a choice between #define and enum in code, one is adviced to use enums liberally instead of #defines as the latter do not pin down the data type while enums are always considered integral constants.

typedef :

The keyword typedef helps to rename datatypes or create datatypes to suit our needs . We can create user defined datatypes based on basic types like int, char, float, double or derived types like struct, union etc. Advantage is ability to call data type by a name that better defines its values and the code is better documented.

For e.g
typedef unsigned int number ;

/* program calls int by another name number */

number age ;
number quantity ;

The advantage is improved readability and program documentation .

typedef int boolean ;

typedef unsigned int WORD ;

You might now declare a variable as

Boolean status ;

WORD x ;

typedef are useful in structures

typedef struct

{

char *title ;

char *author ;

float cost ;

}Book ;

Book is a datatype we have defined .We might declare a variable

Book b1 , b2 ;

Note :

The keyword struct is not used while using data type Book to declare a variable.

Graphics in C

Basic concepts for computer generated Graphics:

A computer draws a picture (graphics) as a combination of dots(pixels) in different colors in different positions . This graphics is displayed on a monitor or sent to a printer .

Concept 1 : Monitor resolution

The monitor may display the output in text mode or graphics mode.

Text Mode :

In text mode (DOS) the monitor displays 80 characters in 25 lines [ 80 X 25 ] .

Graphics Mode :

In graphics mode the monitor resolution is measured in terms of pixels number of dots that can be displayed in each row and column.This resolution is determined by :-

• The type of display adapter card we are using
• The Operating System’s monitor display specification that we have set
• Greater the resolution finer the picture .

Concept 2 :Graphics are mathematical in origin

Graphics are based on some mathematical algorithms (formula or equations or principles). For e.g a circle has an equation and to draw a circle you generate a set of points of points(x , y ) satisfying that equation.

Concept 3 :Graphical Functions in C

C has a number of library functions for managing simple graphical programs . Include header file

You may also write your own functions to create specific graphical objects .The graphics.h header file also includes several constants (enums) that we can use in our programs

Concept 4 : Graphics files like .jpg , .bmp , .gif

When we draw graphics using graphical packages like paintbrush the files get saves in a specific file format like with extensions like .bmp , .jif , .gpg etc. These files store data about the various graphical functions and data structures , data etc into a persistent storage device(hard disk) that helps us to retrieve the picture as and when we want.

Concept 5 : initgraph( ) function in C

A graphics program in C requires to call the initgraph() function that initializes the graphical system by loading a graphics driver from the system .initgraph() also resets all the graphical settings like color , palette , current position … to their defaults . It then resets graphresult to 0.

Declaration:

void far initgraph(int far *graphdriver, int far *graphmode,

char far *pathtodriver);

*graphdriver :- Integer that specifies the graphics driver to

be used.

*graphmode :- Integer that specifies the initial graphics

mode (unless *graphdriver = DETECT).

If *graphdriver = DETECT, initgraph sets *graphmode to the highest resolution available for the detected driver. You can give graphmode a value using a constant of the graphics_modes enumeration type.

pathtodriver : Specifies the directory path where initgraph

looks for graphics drivers (*.BGI) first.

If they're not there, initgraph looks in the current directory. If pathtodriver is null, the driver files must be in the current directory.

This is also the path settextstyle searches for the stroked character font files (*.CHR).

Return Value of initgraph( ) function:

initgraph sets the internal error code On success code is set to to 0 and On error, initgraph sets *graphdriver to -2, -3, -4, or -5, and graphresult returns the same value.

Note :

*graphdriver and *graphmode must be set to valid graphics drivers and graphics mode values or you'll get unpredictable results.

(The exception is graphdriver = DETECT for auto detection.)

After a call to initgraph, *graphdriver is set to the current graphics driver, and *graphmode is set to the current graphics mode.

Program:

#include

#include

#include

#include

int main(void)

{

int gdriver = DETECT, gmode, errorcode;

initgraph(&gdriver, &gmode, "c:\\tc\\bgi");

errorcode = graphresult();

if (errorcode != grOk)

{ _

printf("Graphics error: %s\n", grapherrormsg(errorcode));

printf("Press any key to halt:");

getch();

exit(1);

}

line(0, 0, getmaxx(), getmaxy());

getch();

closegraph();

return 0;

}

Concept 6 : Graphical library functions are available. One can use them to create graphical images.

Some Common functions are:

arc( ) ,bar( ) ,bar3d( ), circle( ) , closegraph ( ) , drawpoly( ) , ellipse ( ) , fillellipse( ), fillpoly ( ), floodfill( ), getbkcolor( ) getcolor( ) , getimage( ) , getmaxx ( ) , getmaxy( ), getpixel , getx( ) , gety ( ) , line( ), lineto ( ) , moveto ( ) , outtext( ) ,

outtextxy( ), pieslice ( ) , putimage( ) , putpixel( ), rectangle( ) , setbkcolor ( ) , setcolor( ) , setfillpattern ( ) , setfillstyle( ) , setlinestyle ( ) , settextjustify( ) , settextstyle( ) , textheight( ) , textwidth( )

bgi.exe is a graphics demo file bundled with Borlands Turboc and one can learn a lot by going through the source code bgi.c

Bitwise Operators

A bit is 0 or 1 . All data in the computer is stored in the binary format as streams of 0 , 1.

Bitwise operators act on each bit of data of the operands. Thus associativity is immaterial in case of bitwise & , | , ^ , ` operators.

Bitwise operators are applicable to only integral operands

Following are bitwise operators:

& Bitwise and

| Bitwise or

~ Bitwise Not or Complment

^ Bitwise XOR (Exclusive or)

>> Right Shift

<< Left Shift

Assignment operators combined with bitwise operators :-

&=

|=

^=

>>=

<<=

Bitwise ‘and’ & Operator : (called anding) is a binary operator that returns 1 if both operands are 1 else returns 0 . Acts on each bit of data .

Program 1 :- Bitwise & operator

void main( )

{

char x = 100 , y = 53 , z ;

clrscr( );

z = x & y ;

printf(“z = %d” , z ); /* prints z = 36 */

}

x è 0110 0100 /* 100 */

y è 0011 0101 /* 53 */

z = x & y è 0010 0100 /* 36 */

Bitwise ‘or’ | Operator : is a binary operator that returns 1 if any one operand is 1 else returns 0 . Acts on each bit of data .

Program 2 :- Bitwise | operator

void main( )

{

char x = 100 , y = 53 , z ;

clrscr( );

z = x | y ;

printf(“z = %d” , z ); /* prints z = 117 */

}

x è 0110 0100 /* 100 */

y è 0011 0101 /* 53 */

z = x | y è 0111 0101 /* 117 */

Bitwise XOR ^ Operator : (mutually excusive or) is a binary operator that returns 1 if any one operand is 1 and one operand is 0 .If both are 1 or both are zero , ^ operator returns 0 . Acts on each bit of data .

Program 3:-

void main()

{

char x = 100 , y = 53 , z ;

clrscr( );

z = x ^ y ;

printf(“z = %d” , z ); /* prints z = 81 */

}

x è 0110 0100 /* 100 */

y è 0011 0101 /* 53 */

z = x ^ y è 0101 0001 /* 81 */

Bitwise Complement or not ~ Operator : is a unary operator that toggles bits if 1 then it becomes 0 and vice versa. Acts on each bit of data .

Program 3:-

void main()

{

char x = 100 , z ;

clrscr( );

z = ~y ;

printf(“z = %d” , z ); /* prints z = */

}

x è 0110 0100 /* 100 */

z = ~x è 1001 1011 /* - 101 */

How is 1001 1011 interpreted ?

Since the left most bit or the most significant bit (msb) is on , the data is negative. We must take a 2’s complement to find the numerical value

Z è 1001 1011

1’s complement è 0110 0100

Add 1 1

2’s Complement è 0110 0101 /* -101 */

Shift Operators :- >> , <<

The bits get shifted to left or right positions

A shift is not a rotation .This means the bits shifted out on the right side will not come and fill up from the left side.

Bit representation of x :

x >> 2

For e.g

If x = 0110 0110 then x << style=""> 1001 1000

If x = 0110 0110 then x << style=""> 0011 0000

If x = 0110 0110 then x >> 2 will give 0010 0110

If x = 0110 0110 then x >> 3 will give 0010 0110

Right Shift of a negative number :-

In case of a negative number , the left most bit is set to 1 . A right shift results in 1’s fill in from the left side to fill up instead of 0’s

If x = 1110 0110 then x >> 2 will give 1111 1001

If x = 1110 0110 then x >> 3 will give 1111 1100

Assignment operators with Bitwise operators :-

&= An expression like x &= y is equivalent to x = x & y

|= An expression like x |= y is equivalent to x = x | y

^= An expression like x ^= y is equivalent to x = x ^ y

>>= An expression like x >>= y is equivalent to x = x >> y

<<= An expression like x <<= y is equivalent to x = x <<>

Application of bitwise operators :-

While software programs are byte oriented, hardwares are bit oriented.As bitwise operators act on each bit of data , One byte of information can be treated as 8 pieces of informations .Each information can be checked and manipulated.

For e.g video memory stores 1 byte for each character attributes .This 1 byte represents 8 bits of information of screen attributes of fore color, back color as shown above.

File Encryption program using bitwise complement ~ operator:

Encryption means changing the contents of a file into an illegible format for protection .Pass the file name to a command called encrypt as a command parameter

For e.g:

C:> encrypt file1

This call changes the contents of file1 into an illegible format.

/*

File encryption

command line encryption

Bitwise complement used for encryption

*/

# include

# include

main(int argc , char *argv[])

{

char ch ;FILE *fp , *ft ;

if(argc != 2)

{

printf("Error in no. of arguments");

printf("\nEncryption Failue");

exit(1);

}

if(!(fp = fopen(argv[1] , "r")) )

{

printf("Error opening file to be encrypted");

printf("\nEncryption Failue");

exit(1);

}

if(!(ft = fopen("temp" , "w")) )

{

printf("Error creating encryption file ");

printf("\nEncryption Failue");

exit(1);

}

while(!feof(fp) )

{

ch = fgetc(fp);

fputc(~ch , ft);

}

remove(argv[1]);

rename("temp" , argv[1]);

printf("\nFile Successfully encrypted");

return 0 ;

}

File Decryption program :

Decryption means restoring the contents of an encrypted file Pass the file name to a command called decrypt as a command parameter

For e.g:

C:> decrypt file1

This call recovers the file encrypted by the above encryption call

/*

File decryption

File name passed as a command line argument

Bitwise complement used for decryption

*/

# include

# include

main(int argc , char *argv[])

{

char ch ;FILE *fp , *ft ;

if(argc != 2)

{

printf("Error in no. of arguments");

printf("\nDecryption Failue");

exit(1);

}

if(!(fp = fopen(argv[1] , "r")) )

{

printf("Error in file Decryption Recovery”);

printf("\nDecryption Failue");

exit(1);

}

if(!(ft = fopen("temp" , "w")) )

{

printf("Error while decrypting ");

printf("\nDecryption Failure");

exit(1);

}

while(!feof(fp) )

{

ch = fgetc(fp);

fputc(~ch , ft);

}

remove(argv[1]);

rename("temp" , argv[1]);

printf("\nFile Successfully decrypted");

return 0 ;

}