Prog-12

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#include<iostream.h>

#include<fstream.h>

#include<new.h>

class node

{

 public:char name[20];

        char usn[20];

        node *link;

};

node *first=NULL;

void writeFile()

{

  node *p;

  char buffer[100];

  fstream out;

  out.open("student.txt",ios::out);

  if(!out)

  {

   cout<<"\nUnable to open the file student.txt in out mode";

   getch();

   exit(0);

  }

  p=first;

  while(p!=NULL)

  {

    strcpy(buffer,p->name);

    strcat(buffer,"|");

    strcat(buffer,p->usn);

    strcat(buffer,"\n");

    out<<buffer;

    p=p->link;

  }

}

void display()

{

 node *p;

 if(first==NULL)

 {

  cout<<"\nList is empty";

  return;

 }

  p=first;

 while(p!=NULL)

 {

  cout<<"|"<<p->name<<" "<<p->usn<<"|"<<"->";

  p=p->link;

 }

}

void Insert() //Insert the record at the rear end

{

 char name[20],usn[15];

 node *p,*q;

 cout<<"\nEnter name  = ";

 cin>>name;

 cout<<"\nEnter usn   = ";

 cin>>usn;

  p=new node;

 strcpy(p->name,name);

 strcpy(p->usn,usn);

 p->link=NULL;

 if(first==NULL)

 {

   first=p;

   writeFile();

   display();    //display the record on the screen

   return;

 }

 for(q=first;q->link!=NULL;q=q->link)

 {

  ;

 }

 q->link=p;

 writeFile(); //writing the record to the file

 display();   //display the records to the screen.

}

void Delete()

{

  char usn[15];

  node *curr,*prev,*del;

 if(first==NULL)

 {

  printf("\nThe list is empty. Deletion is not possible");

  return;

 }

 cout<<"\nEnter the usn to be deleted = ";

 cin>>usn;

 if(strcmp(first->usn,usn)==0)

 {

  cout<<"\nRecord deleted";

  del=first;

  delete del;

  first=first->link;

  writeFile();

  return;

 }

 prev=NULL;

 curr=first;

 while( ( strcmp(curr->usn,usn) != 0 ) && curr!=NULL)

 {

   prev=curr;

   curr=curr->link;

 }

 if(curr==NULL)

 {

    cout<<"\nThe student with usn "<<usn<<" is not present";

    return;

 }

 prev->link=curr->link;

 writeFile();

 display();

}

void main()

{

 int choice;

 clrscr();

 for(;;)

 {

  printf("\n1:Insert_rear");

  printf("\n2:Delete_id");

  printf("\n3:exit");

  printf("\nEnter the choice=");

  scanf("%d",&choice);

  switch(choice)

  {

   case 1:Insert();

          break;

   case 2:Delete();

          break;

   case 3:exit(0);

  default:cout<<"\nInvalid option";break;

  }

 }

}

Prog-11

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<conio.h>

#include<fstream.h>

#include<iostream.h>

//Record specification

class node

{

 public:char name[15],usn[15];

 node *link;

};

node *h[29];//Array of record pointers

//equal to size of hash keys--29

void insert()

{

 char name[15],usn[15],buffer[50];

 fstream out;

 out.open("student.txt",ios::app);//opening student.txt in append mode

 if(!out)

 {

  cout<<"\nUnable to open the file in append mode";

  getch();

  return;

 }

 cout<<"\nEnter the name = ";

 cin>>name;

 cout<<"\nEnter the usn = ";

 cin>>usn;

 strcpy(buffer,name); //Packing the record onto the file using '|' as

 strcat(buffer,"|");  //a delimiter

 strcat(buffer,usn);

 strcat(buffer,"\n");//'\n' delimiter for the record

 out<<buffer;        // appending the packed record onto the file

 out.close();

}

//Insert record into the hash table

void hash_insert(char name1[],char usn1[],int hash_key)

{

 node *p,*prev,*curr;

 p=new node;           //dynamically allocate space using 'new'

 strcpy(p->name,name1);

 strcpy(p->usn,usn1);

 p->link=NULL;

 prev=NULL;

 curr=h[hash_key];       //getting the hash pointer location

 if(curr==NULL)          // Case: No collision

 {

  h[hash_key]=p;

  return;

 }

 while(curr!=NULL)       // Case : On collision -- Insert at rear end

 {

  prev=curr;

  curr=curr->link;

 }

 prev->link=p;

}

void retrive()

{

 fstream in;

 char name[15],usn[15];

 int j,count;

 node *curr;

 in.open("student.txt",ios::in);     // open the record file in input mode

 if(!in)

 {

  cout<<"\nUnable to open the file in input mode";

  getch();

  exit(0);

 }

 while(!in.eof())

 {

   in.getline(name,15,'|');          //unpacking the record

   in.getline(usn,15,'\n');

   count=0;

   for(j=0;j<strlen(usn);j++)        //Calculate sum of ascii values

   {                                 //of USN

    count=count+usn[j];

   }

   count=count%29;                   // Hash Key = ASCII count% 29

   hash_insert(name,usn,count);

 }

 cout<<"\nEnter the usn = ";

 cin>>usn;

 count=0;

 for(j=0;j<strlen(usn);j++)           // Calculating Hash Key

 count=count+usn[j];

 count=count%29;

 curr=h[count];

 if(curr==NULL)

 {

  cout<<"\nRecord not found";

  getch();

  return;

 }

 do

 {

  if(strcmp(curr->usn,usn)==0)                            //When the record is

  {                                                       //found, retrieve

   cout<<"\nRecord found : "<<curr->usn<<" "<<curr->name; //USN and name

   getch();

   return;

  }

  else

  {

   curr=curr->link;

  }

 }while(curr!=NULL);                 //Search till end of list

 if(curr==NULL)                      //End of list reached with no record found

 {

  cout<<"\nRecord not found";

  getch();

  return;

 }

}

void main()

{

 int choice;

 clrscr();

 fstream out;

 out.open("student.txt",ios::out);

 if(!out)

 {

  cout<<"\nUnable to open the file in out mode";

  getch();

  exit(0);

 }

 for(;;)

 {

  cout<<"\n1:insert";

  cout<<"\n2:retrive";

  cout<<"\n3:exit";

  cout<<"\nEnter the choice = ";

  cin>>choice;

  switch(choice)

  {

   case 1:insert();break;

   case 2:retrive();break;

   case 3:exit(0);

   default:cout<<"\nInvalid option";

  }

 }

}

Prog-9

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

const int MAX = 4 ;

const int MIN = 2 ;

struct btnode

{

int count ;

int value[MAX + 1] ;

btnode *child[MAX + 1] ;

} ;

class btree

{

private :

btnode *root ;

public :

btree( ) ;

void insert ( int val ) ;

int setval ( int val, btnode *n, int *p, btnode **c ) ;

static btnode * search ( int val, btnode *root, int *pos ) ;

static int searchnode ( int val, btnode *n, int *pos ) ;

void iskeypresent ( int val ) ;

void fillnode ( int val, btnode *c, btnode *n, int k ) ;

void split ( int val, btnode *c, btnode *n,

int k, int *y, btnode **newnode ) ;

void clear ( btnode *root, int k ) ;

void copysucc ( btnode *root, int i ) ;

void merge ( int k ) ;

void show( ) ;

static void display ( btnode *root ) ;

static void deltree ( btnode *root ) ;

~btree( ) ;

} ;

// initialises data member

btree :: btree( )

{

root = NULL ;

}

// searches a key and checks whether it is present or not

void btree :: iskeypresent ( int val )

{

int i ;

if ( searchnode ( val, root, &i ) )

cout<< "Key found "<<endl;

else

cout<< "Key Not found "<<endl;

}

// inserts a value in the B-tree

void btree :: insert ( int val )

{

int i ;

btnode *c, *n ;

int flag ;

flag = setval ( val, root, &i, &c ) ;

if ( flag )

{

n = new btnode ;

n -> count = 1 ;

n -> value[1] = i ;

n -> child[0] = root ;

n -> child[1] = c ;

root = n ;

}

}

// sets the value in the node

int btree :: setval ( int val, btnode *n, int *p, btnode **c )

{

int k ;

if ( n == NULL )

{

*p = val ;

*c = NULL ;

return 1 ;

}

else

{

if ( searchnode ( val, n, &k ) )

{

cout << endl << "Key value already exists." << endl ;

return 0 ;

}

if ( setval ( val, n -> child[k], p, c ) )

{

if ( n -> count < MAX )

{

fillnode ( *p, *c, n, k ) ;

return 0 ;

}

else

{

split ( *p, *c, n, k, p, c ) ;

return 1 ;

}

}

return 0 ;

}

}

// searches value in the node

btnode * btree :: search ( int val, btnode *root, int *pos )

{

if ( root == NULL )

return NULL ;

else

{

if ( searchnode ( val, root, pos ) )

return root ;

else

return search ( val, root -> child[*pos], pos ) ;

}

}

// searches for the node

int btree :: searchnode ( int val, btnode *n, int *pos )

{

//this condition is used to decide the traversal

if ( val < n -> value[1] )

{

*pos = 0 ;

return 0 ;

}

else

{

*pos = n -> count ;

while ( ( val < n -> value[*pos] ) && *pos > 1 )

( *pos )-- ;

if ( val == n -> value[*pos] )

return 1 ;

else

return 0 ;

}

}

// adjusts the value of the node

void btree :: fillnode ( int val, btnode *c, btnode *n, int k )

{

int i ;

for ( i = n -> count ; i > k ; i-- )

{

n -> value[i + 1] = n -> value[i] ;

n -> child[i + 1] = n -> child[i] ;

}

n -> value[k + 1] = val ;

n -> child[k + 1] = c ;

n -> count++ ;

}

// splits the node

void btree :: split ( int val, btnode *c, btnode *n,

int k, int *y, btnode **newnode )

{

int i, mid ;

if ( k <= MIN )

mid = MIN ;

else

mid = MIN + 1 ;

*newnode = new btnode ;

for ( i = mid + 1 ; i <= MAX ; i++ )

{

( *newnode ) -> value[i - mid] = n -> value[i] ;

( *newnode ) -> child[i - mid] = n -> child[i] ;

}

( *newnode ) -> count = MAX - mid ;

n -> count = mid ;

if ( k <= MIN )

fillnode ( val, c, n, k ) ;

else

fillnode ( val, c, *newnode, k - mid ) ;

*y = n -> value[n -> count] ;

( *newnode ) -> child[0] = n -> child[n -> count] ;

n -> count-- ;

}

// removes the value from the node and adjusts the values

void btree :: clear ( btnode *root, int k )

{

int i ;

for ( i = k + 1 ; i <= root -> count ; i++ )

{

root -> value[i - 1] = root -> value[i] ;

root -> child[i - 1] = root -> child[i] ;

}

root -> count-- ;

}

// copies the successor of the value that is to be deleted

void btree :: copysucc ( btnode *root, int i )

{

btnode *temp = root -> child[i] ;

while ( temp -> child[0] )

temp = temp -> child[0] ;

root -> value[i] = temp -> value[1] ;

}

// merges two nodes

void btree :: merge ( int k )

{

btnode *temp1, *temp2 ;

temp1 = root -> child[k] ;

temp2 = root -> child[k - 1] ;

temp2 -> count++ ;

temp2 -> value[temp2 -> count] = root -> value[k] ;

temp2 -> child[temp2 -> count] = root -> child[0] ;

for ( int i = 1 ; i <= temp1 -> count ; i++ )

{

temp2 -> count++ ;

temp2 -> value[temp2 -> count] = temp1 -> value[i] ;

temp2 -> child[temp2 -> count] = temp1 -> child[i] ;

}

for ( i = k ; i < root -> count ; i++ )

{

root -> value[i] = root -> value[i + 1] ;

root -> child[i] = root -> child[i + 1] ;

}

root -> count-- ;

delete temp1 ;

}

// calls display( )

void btree :: show( )

{

display ( root ) ;

}

// displays the B-tree

void btree :: display ( btnode *root )

{

if ( root != NULL )

{

for ( int i = 0 ; i < root -> count ; i++ )

{

display ( root -> child[i] ) ;

cout << root -> value[i + 1] << "\t" ;

}

display ( root -> child[i] ) ;

}

}

// deallocates memory

void btree :: deltree ( btnode *root )

{

if ( root != NULL )

{

for ( int i = 0 ; i < root -> count ; i++ )

{

deltree ( root -> child[i] ) ;

delete ( root -> child[i] ) ;

}

deltree ( root -> child[i] ) ;

delete ( root -> child[i] ) ;

}

}

btree :: ~btree( )

{

deltree ( root ) ;

}

void main( )

{

btree b ;

clrscr();

int num;

int choice=0;

while (choice!=4)

{

cout<<endl<<"1 - Insert"<<endl;

cout<<"2 - Search"<<endl;

cout<<"3 - Display"<<endl;

cout<<"4 - Exit"<<endl;

cout<<"Enter your choice"<<endl;

cin>>choice;

switch(choice)

{

case 1:

cout<<"\nEnter the elements to be inseretd into b tree \n";

cin>>num;

b.insert ( num ) ;

break;

case 2:

cout<<"\nEnter the elements to be searched in b tree \n";

cin>>num;

b.iskeypresent ( num ) ;

break;

case 3:b.show( ) ;

              break;

case 4:exit(0);

default: cout<<"\nInvalid Option \n";

}

}

}