Wednesday, 23 January 2013
latest news
hey guys will be uploading 6th sem lab programs soon in the same blog . Thanking you in advance
Saturday, 15 December 2012
OS LRU PROGRAM
#include<stdio.h>
main()
{
int
q[20],p[50],c=0,c1,d,f,i,j,k=0,n,r,t,b[20],c2[20];
printf("Enter
no of pages:");
scanf("%d",&n);
printf("Enter
the reference string:");
for(i=0;i<n;i++)
scanf("%d",&p[i]);
printf("Enter
no of frames:");
scanf("%d",&f);
q[k]=p[k];
printf("\n\t%d\n",q[k]);
c++;
k++;
for(i=1;i<n;i++)
{
c1=0;
for(j=0;j<f;j++)
{
if(p[i]!=q[j])
c1++;
}
if(c1==f)
{
c++;
if(k<f)
{
q[k]=p[i];
k++;
for(j=0;j<k;j++)
printf("\t%d",q[j]);
printf("\n");
}
else
{
for(r=0;r<f;r++)
{
c2[r]=0
for(j=i-1;j<n;j--)
{
if(q[r]!=p[j])
c2[r]++;
else
break;
}
}
for(r=0;r<f;r++)
b[r]=c2[r];
for(r=0;r<f;r++)
{
for(j=r;j<f;j++)
{
if(b[r]<b[j])
{
t=b[r];
b[r]=b[j];
b[j]=t;
}
}
}
for(r=0;r<f;r++)
{
if(c2[r]==b[0])
q[r]=p[i];
printf("\t%d",q[r]);
}
printf("\n");
}
}
}
printf("\nThe
no of page faults is %d",c);
}
Tuesday, 4 December 2012
Fs Kway merge
#include
<iostream>
#include <fstream>
#include <string>
using namespace std;
class coseq
{
public:
string list[8][100];
string outlist[100];
int count[8];
int current[8];
void load_list();
void read_file(int);
void sort_list(int);
void merge();
};
void coseq::read_file(int i)
{
fstream file;
string name;
switch(i){
case 1: file.open("name1.txt");break;
case 2: file.open("name2.txt");break;
case 3: file.open("name3.txt");break;
case 4: file.open("name4.txt");break;
case 5: file.open("name5.txt");break;
case 6: file.open("name6.txt");break;
case 7: file.open("name7.txt");break;
case 8: file.open("name8.txt");break;
}
while (!file.eof()){
name.erase();
getline(file,name);
list[i][++count[i]]=name;
}
file.close();
}
void coseq::load_list()
{
for (int i=1;i<=8;i++)
{
count[i]=-1;
read_file(i);
sort_list(i);
}
}
void coseq::sort_list(int k)
{
int i,j;
string temp;
for (i=0;i<=count[k];i++)
{
for (j=i+1;j<=count[k];j++)
{
if (list[k][i]>list[k][j])
{
temp=list[k][i];
list[k][i]=list[k][j];
list[k][j]=temp;
}}}
}
void coseq::merge()
{
string smallest;
int small_list, t=-1,start=1,avail[8],avail_lists=8;
for (int i=1;i<=8;i++) {avail[i]=1;current[i]=1;}
while (avail_lists>1)
{
if (!avail[start]) {start++; continue;}
small_list=start;
smallest=list[start][current[start]];
for (int i=start+1;i<=7;i++)
{
if (!avail[i]) continue;
if (list[i][current[i]]<smallest)
{
smallest=list[i][current[i]];
small_list=i;
}
}
current[small_list]++;
if (current[small_list]>count[small_list]) {avail[small_list]=0;avail_lists--;}
outlist[++t]=smallest;
for (int j=1;j<=8;j++)
if (j!=small_list) {if (list[j][current[j]]==smallest){current[j]++;}}
}
for (int i=1;i<=8;i++) if (avail[i]) { for (int j=current[i];j<=count[i];j++) outlist[++t]=list[i][j];}
cout<<"\nThe Merged List:";
for (int i=0;i<=t+1;i++) cout<<"\n"<<outlist[i];
}
int main()
{
coseq c1;
c1.load_list();
c1.merge();
return 0;
}
#include <fstream>
#include <string>
using namespace std;
class coseq
{
public:
string list[8][100];
string outlist[100];
int count[8];
int current[8];
void load_list();
void read_file(int);
void sort_list(int);
void merge();
};
void coseq::read_file(int i)
{
fstream file;
string name;
switch(i){
case 1: file.open("name1.txt");break;
case 2: file.open("name2.txt");break;
case 3: file.open("name3.txt");break;
case 4: file.open("name4.txt");break;
case 5: file.open("name5.txt");break;
case 6: file.open("name6.txt");break;
case 7: file.open("name7.txt");break;
case 8: file.open("name8.txt");break;
}
while (!file.eof()){
name.erase();
getline(file,name);
list[i][++count[i]]=name;
}
file.close();
}
void coseq::load_list()
{
for (int i=1;i<=8;i++)
{
count[i]=-1;
read_file(i);
sort_list(i);
}
}
void coseq::sort_list(int k)
{
int i,j;
string temp;
for (i=0;i<=count[k];i++)
{
for (j=i+1;j<=count[k];j++)
{
if (list[k][i]>list[k][j])
{
temp=list[k][i];
list[k][i]=list[k][j];
list[k][j]=temp;
}}}
}
void coseq::merge()
{
string smallest;
int small_list, t=-1,start=1,avail[8],avail_lists=8;
for (int i=1;i<=8;i++) {avail[i]=1;current[i]=1;}
while (avail_lists>1)
{
if (!avail[start]) {start++; continue;}
small_list=start;
smallest=list[start][current[start]];
for (int i=start+1;i<=7;i++)
{
if (!avail[i]) continue;
if (list[i][current[i]]<smallest)
{
smallest=list[i][current[i]];
small_list=i;
}
}
current[small_list]++;
if (current[small_list]>count[small_list]) {avail[small_list]=0;avail_lists--;}
outlist[++t]=smallest;
for (int j=1;j<=8;j++)
if (j!=small_list) {if (list[j][current[j]]==smallest){current[j]++;}}
}
for (int i=1;i<=8;i++) if (avail[i]) { for (int j=current[i];j<=count[i];j++) outlist[++t]=list[i][j];}
cout<<"\nThe Merged List:";
for (int i=0;i<=t+1;i++) cout<<"\n"<<outlist[i];
}
int main()
{
coseq c1;
c1.load_list();
c1.merge();
return 0;
}
Sunday, 25 November 2012
FS PROGRAM HASHING
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class student
{
public:
string USN;
string Name;
string Branch;
int Semester;
string buffer;
void read_data();
void pack();
void write_to_file();
void unpack(int);
void search(string);
int hash(string);
};
int student::hash(string key)
{
int t;
t = (((key[7]-48) *100) + ((key[8]-48)*10) + (key[9]-48)) % 9;
if (t==0) return 9;
else return t;
}
void student::read_data()
{
cout<<"\nUsn:";
cin>>USN;
cout<<"\nName:";
cin>>Name;
cout<<"\nBranch:";
cin>>Branch;
cout<<"\nSemster:";
cin>>Semester;
}
void student::pack()
{
string sem,temp;
stringstream out;
out << Semester;
sem = out.str();
buffer.erase();
temp.erase();
temp+=USN+'|'+Name+'|'+Branch+'|'+sem;
for(;temp.size()<100;) temp+='$';
buffer=temp+'\n';
}
void student::write_to_file()
{
fstream file;
string temp;
int count, pos;
pos=hash(USN);
pos--;
pos=pos*304;
file.open("1.txt");
file.seekp(pos,ios::beg);
getline(file,temp);
file.close();
count=temp[0]-48;
file.open("1.txt");
if (count<0)
{
file.seekp(pos,ios::beg);
file.put('1');
pos=pos+1;
}
else if (count==1)
{
file.seekp(pos,ios::beg);
file.put('2');
pos=pos+102;
}
else if (count==2)
{
file.seekp(pos,ios::beg);
file.put('3');
pos=pos+203;
}
cout<<"\nInserting at:"<<pos;
file.seekp(pos,ios::beg);
file<<buffer;
file.close();
if (count==3) cout<<"\n\nCannot Insert....Overflow";
}
void student::unpack(int flag)
{
string sem;
int ch=1,i=0;
USN.erase();
if (flag==1) i++; //skip the count value
while (buffer[i]!='|')
USN+=buffer[i++];
Name.erase();
i++;
while (buffer[i]!='|')
Name+=buffer[i++];
Branch.erase();
i++;
while (buffer[i]!='|')
Branch+=buffer[i++];
sem.erase();
i++;
while (buffer[i]!='$')
sem+=buffer[i++];
istringstream out(sem);
out>>Semester;
}
void student::search(string key)
{
fstream file;
int flag=0, pos=0, count,i=1;
string temp;
pos=hash(key);
pos--;
pos=pos*304;
file.open("1.txt");
file.seekp(pos,ios::beg);
getline(file,temp);
count=temp[0]-48;
file.seekp(pos,ios::beg);
while (i<=count)
{
buffer.erase();
getline(file,buffer);
unpack(i++);
if (key==USN) flag=1;
}
if (!flag) cout<<"\n\nKey not found:";
else {
cout<<"\nThe Record details are-\n";
cout<<"\nUSN:"<<USN<<"\nName:"<<Name<<"\nBranch:"<<Branch<<"\nSemester:"<<Semester;
}
file.close();
}
int main()
{
int choice;
student s1;
string key;
while (1){
cout <<"\n\nMain Menu\n 1.Add \n\n 2.Search \n\n 3.Exit\n\nEnter the choice:";
cin>>choice;
switch (choice)
{
case 1: cout<<"Data\n";
s1.read_data();
s1.pack();
s1.write_to_file();
break;
case 2: cout <<"\n\nEnter the key";
cin>>key;
s1.search(key);
break;
case 3: return 0;
default: cout<<"\n\nWrong Choice";
}}
}
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class student
{
public:
string USN;
string Name;
string Branch;
int Semester;
string buffer;
void read_data();
void pack();
void write_to_file();
void unpack(int);
void search(string);
int hash(string);
};
int student::hash(string key)
{
int t;
t = (((key[7]-48) *100) + ((key[8]-48)*10) + (key[9]-48)) % 9;
if (t==0) return 9;
else return t;
}
void student::read_data()
{
cout<<"\nUsn:";
cin>>USN;
cout<<"\nName:";
cin>>Name;
cout<<"\nBranch:";
cin>>Branch;
cout<<"\nSemster:";
cin>>Semester;
}
void student::pack()
{
string sem,temp;
stringstream out;
out << Semester;
sem = out.str();
buffer.erase();
temp.erase();
temp+=USN+'|'+Name+'|'+Branch+'|'+sem;
for(;temp.size()<100;) temp+='$';
buffer=temp+'\n';
}
void student::write_to_file()
{
fstream file;
string temp;
int count, pos;
pos=hash(USN);
pos--;
pos=pos*304;
file.open("1.txt");
file.seekp(pos,ios::beg);
getline(file,temp);
file.close();
count=temp[0]-48;
file.open("1.txt");
if (count<0)
{
file.seekp(pos,ios::beg);
file.put('1');
pos=pos+1;
}
else if (count==1)
{
file.seekp(pos,ios::beg);
file.put('2');
pos=pos+102;
}
else if (count==2)
{
file.seekp(pos,ios::beg);
file.put('3');
pos=pos+203;
}
cout<<"\nInserting at:"<<pos;
file.seekp(pos,ios::beg);
file<<buffer;
file.close();
if (count==3) cout<<"\n\nCannot Insert....Overflow";
}
void student::unpack(int flag)
{
string sem;
int ch=1,i=0;
USN.erase();
if (flag==1) i++; //skip the count value
while (buffer[i]!='|')
USN+=buffer[i++];
Name.erase();
i++;
while (buffer[i]!='|')
Name+=buffer[i++];
Branch.erase();
i++;
while (buffer[i]!='|')
Branch+=buffer[i++];
sem.erase();
i++;
while (buffer[i]!='$')
sem+=buffer[i++];
istringstream out(sem);
out>>Semester;
}
void student::search(string key)
{
fstream file;
int flag=0, pos=0, count,i=1;
string temp;
pos=hash(key);
pos--;
pos=pos*304;
file.open("1.txt");
file.seekp(pos,ios::beg);
getline(file,temp);
count=temp[0]-48;
file.seekp(pos,ios::beg);
while (i<=count)
{
buffer.erase();
getline(file,buffer);
unpack(i++);
if (key==USN) flag=1;
}
if (!flag) cout<<"\n\nKey not found:";
else {
cout<<"\nThe Record details are-\n";
cout<<"\nUSN:"<<USN<<"\nName:"<<Name<<"\nBranch:"<<Branch<<"\nSemester:"<<Semester;
}
file.close();
}
int main()
{
int choice;
student s1;
string key;
while (1){
cout <<"\n\nMain Menu\n 1.Add \n\n 2.Search \n\n 3.Exit\n\nEnter the choice:";
cin>>choice;
switch (choice)
{
case 1: cout<<"Data\n";
s1.read_data();
s1.pack();
s1.write_to_file();
break;
case 2: cout <<"\n\nEnter the key";
cin>>key;
s1.search(key);
break;
case 3: return 0;
default: cout<<"\n\nWrong Choice";
}}
}
B+ trees FS
#include <iostream>
#include <cmath>
using namespace std;
struct node
{
int ele[4];
int child[4];
node *next;
};
class bptree
{
public:
node *tree[10][10];
int count[10];
int leaf;
int path[10];
node *head;
bptree();
node* create_node();
void insert(int);
void main_search(int);
void display_tree();
void insert_node(node*,int);
void search(int);
int search_node (node*,int);
int nodefull(node*);
void split(node*);
void display_seqset();
};
bptree::bptree()
{
leaf=-1;
for (int i=0;i<10;i++)
{count[i]=-1;path[i]=-1;}
}
node* bptree::create_node()
{
node *n;
n = new node;
for (int i=0;i<4;i++) {n->ele[i]=-1;n->child[i]=-1;}
n->next=NULL;
return n;
}
void bptree::insert(int key)
{
int n, parent;
node *first_node;
if (leaf==-1)
{
first_node=create_node();
tree[0][0]=first_node;
leaf++;count[0]++;
first_node->ele[0]=key;
head=first_node; //header node of seq set
}
else if (leaf==0)
{
if (nodefull(tree[0][0])) {path[leaf]=0;split(tree[0][0]);insert(key);}
else insert_node(tree[0][0],key);
}
else{
search(key);
n=path[leaf];
parent=path[leaf-1];
if ( (nodefull(tree[leaf][n])) )
{
split(tree[leaf][n]);
insert(key);
}
else
insert_node(tree[leaf][n],key);
}
}
void bptree::main_search(int key)
{
int flag=0, i;
node *node1;
search(key);
node1=tree[leaf][path[leaf]];
for (i=0;node1->ele[i]!=-1;i++)
if (node1->ele[i]==key) {flag=1; break;}
cout<<"\nThe path traversed is: ";
for (i=0;path[i]!=-1;i++)
cout<<path[i]<<" -> ";
if (flag) cout <<"\nElement Found";
else cout<<"\nNot Found";
}
void bptree::display_tree()
{
int i,j,k;
for (i=0;i<=leaf;i++)
{
cout<<"\n\nLevel------ " <<i<<"\n";
for (j=0;j<=count[i];j++)
{
if (i!=leaf) k=1; else k=0; //print first element only at leaf level
for (;tree[i][j]->ele[k]!=-1;k++)
cout<<" "<<tree[i][j]->ele[k];
cout<<"\t";
}
}
}
void bptree::search(int key)
{
int i,j,temp;
path[0]=0; //always start the path from root
if (leaf){ // search only if there are more than 1 level
j=0;
for (i=0;i<leaf;i++)
{
temp=search_node(tree[i][j],key);
path[i+1]=temp;
j=temp;
}}
}
int bptree::search_node(node *node1, int key)
{
if (key<=node1->ele[0]) return node1->child[0];
for (int i=1;i<4;i++)
{
if ((key >= node1->ele[i]) && (key < node1->ele[i+1])) return node1->child[i];
else if (node1->ele[i+1]==-1) return node1->child[i];
}
}
int bptree::nodefull(node *node1)
{
if (node1->ele[3]!=-1) return 1;
else return 0;
}
void bptree::insert_node(node *node1, int key)
{
int flag=0, count=-1,i,j, x, y, l;
node *newnode, *parent;
for (i=0;i<4;i++) if (node1->ele[i]!=-1) ++count;
i=0;
while (!flag && node1->ele[i]!=-1)
{
if (node1->ele[i] > key) //not considering duplicate entries
{
flag=1;
for (int j=count;j>=i;j--)
node1->ele[j+1]=node1->ele[j];
node1->ele[i]=key;
}
i++;
}
if (!flag) node1->ele[count+1]=key; //highest element added at end
if (node1->ele[0]==key) //new element is the lowest, hence propogate this till root
{
for (i=leaf-1;i>=0;i--)
{
x=path[i+1];
if (tree[i][path[i]]->ele[x] > key) tree[i][path[i]]->ele[x]=key;
else insert_node(tree[i][x],key);
} }
for (i=0;i<=count+1;i++)
cout<<"\t\t"<<node1->ele[i];
}
void bptree::split(node *oldnode)
{
node *newnode, *parent, *n1, *n2;
int i,j,k,n,t,x,y,pos;
newnode = create_node();
newnode->ele[0]=oldnode->ele[2]; //copy elements to new node
newnode->ele[1]=oldnode->ele[3];
oldnode->ele[2]=-1; //delete entries in old node
oldnode->ele[3]=-1;
t=count[leaf];
n=path[leaf];
for (i=t,j=t+1;i>n;i--,j--) //move the elements in leaf level one place right
tree[leaf][j]=tree[leaf][i];
newnode->next=tree[leaf][n]->next; //updating the next pointers
tree[leaf][n]->next=newnode;
tree[leaf][n+1] = newnode; //insert new node to the tree
count[leaf]++;
x=leaf;
if (count[leaf]+1==1) t=1; else t=log(count[leaf]+1)/log(2); //how many levels does the tree need?
if (t!=leaf) //increase the level of the tree
{
++leaf;
count[leaf]=count[x];
for (i=0;i<=count[leaf];i++) //copy the leaf nodes to the new level
std::swap(tree[leaf][i],tree[x][i]);
}
for (i=leaf-1;i>=0;i--) count[i]=-1; //make the tree empty
for (i=t,j=i-1;i>0;i--,j--)
{
for (k=0;k<=count[i]/3;k++)
{
n1=tree[i][2*k];
n2=tree[i][(2*k)+1];
//for (x=0;n1->ele[x]!=-1;x++); //find last element in the nodes
//for (y=0;n2->ele[y]!=-1;y++);
newnode=create_node();
count[j]++;
tree[j][count[j]]=newnode;
newnode->ele[0]=n1->ele[0];
newnode->child[0]=2*k;
newnode->ele[1]=n2->ele[0];
newnode->child[1]=(2*k)+1;
}
if (count[i]!=1 && count[i]%2==0) //one node is remaining
{
n2=tree[i][count[i]];
//for (y=0;n2->ele[y]!=-1;y++);
newnode->ele[2]=n2->ele[0];
newnode->child[2]=count[i];
}
}
}
void bptree::display_seqset()
{
node *t;
int k;
t=head;
cout<<"\n\nThe sequence set is:";
while (t)
{
for (k=0;t->ele[k]!=-1;k++)
cout<<" "<<t->ele[k];
cout<<"\t";
t=t->next;
}
}
int main()
{
bptree bt;
int choice, key;
while(1)
{
cout<<"\n\n\nMain Menu\n-------------------\n1.Insert\n2.Search\n3.Display Tree\n4.Display Sequence Set\n5.Exit\n\nEnter your choice:";
cin>>choice;
switch(choice)
{
case 1: cout<<"\nEnter the element:";
cin>>key;
bt.insert(key);
break;
case 2:cout<<"Enter the key:";
cin>>key;
bt.main_search(key);
break;
case 3: bt.display_tree();
break;
case 4: bt.display_seqset();
break;
case 5: return 0;
default: cout<<"\nEnter valid choice";
}
}
}
#include <cmath>
using namespace std;
struct node
{
int ele[4];
int child[4];
node *next;
};
class bptree
{
public:
node *tree[10][10];
int count[10];
int leaf;
int path[10];
node *head;
bptree();
node* create_node();
void insert(int);
void main_search(int);
void display_tree();
void insert_node(node*,int);
void search(int);
int search_node (node*,int);
int nodefull(node*);
void split(node*);
void display_seqset();
};
bptree::bptree()
{
leaf=-1;
for (int i=0;i<10;i++)
{count[i]=-1;path[i]=-1;}
}
node* bptree::create_node()
{
node *n;
n = new node;
for (int i=0;i<4;i++) {n->ele[i]=-1;n->child[i]=-1;}
n->next=NULL;
return n;
}
void bptree::insert(int key)
{
int n, parent;
node *first_node;
if (leaf==-1)
{
first_node=create_node();
tree[0][0]=first_node;
leaf++;count[0]++;
first_node->ele[0]=key;
head=first_node; //header node of seq set
}
else if (leaf==0)
{
if (nodefull(tree[0][0])) {path[leaf]=0;split(tree[0][0]);insert(key);}
else insert_node(tree[0][0],key);
}
else{
search(key);
n=path[leaf];
parent=path[leaf-1];
if ( (nodefull(tree[leaf][n])) )
{
split(tree[leaf][n]);
insert(key);
}
else
insert_node(tree[leaf][n],key);
}
}
void bptree::main_search(int key)
{
int flag=0, i;
node *node1;
search(key);
node1=tree[leaf][path[leaf]];
for (i=0;node1->ele[i]!=-1;i++)
if (node1->ele[i]==key) {flag=1; break;}
cout<<"\nThe path traversed is: ";
for (i=0;path[i]!=-1;i++)
cout<<path[i]<<" -> ";
if (flag) cout <<"\nElement Found";
else cout<<"\nNot Found";
}
void bptree::display_tree()
{
int i,j,k;
for (i=0;i<=leaf;i++)
{
cout<<"\n\nLevel------ " <<i<<"\n";
for (j=0;j<=count[i];j++)
{
if (i!=leaf) k=1; else k=0; //print first element only at leaf level
for (;tree[i][j]->ele[k]!=-1;k++)
cout<<" "<<tree[i][j]->ele[k];
cout<<"\t";
}
}
}
void bptree::search(int key)
{
int i,j,temp;
path[0]=0; //always start the path from root
if (leaf){ // search only if there are more than 1 level
j=0;
for (i=0;i<leaf;i++)
{
temp=search_node(tree[i][j],key);
path[i+1]=temp;
j=temp;
}}
}
int bptree::search_node(node *node1, int key)
{
if (key<=node1->ele[0]) return node1->child[0];
for (int i=1;i<4;i++)
{
if ((key >= node1->ele[i]) && (key < node1->ele[i+1])) return node1->child[i];
else if (node1->ele[i+1]==-1) return node1->child[i];
}
}
int bptree::nodefull(node *node1)
{
if (node1->ele[3]!=-1) return 1;
else return 0;
}
void bptree::insert_node(node *node1, int key)
{
int flag=0, count=-1,i,j, x, y, l;
node *newnode, *parent;
for (i=0;i<4;i++) if (node1->ele[i]!=-1) ++count;
i=0;
while (!flag && node1->ele[i]!=-1)
{
if (node1->ele[i] > key) //not considering duplicate entries
{
flag=1;
for (int j=count;j>=i;j--)
node1->ele[j+1]=node1->ele[j];
node1->ele[i]=key;
}
i++;
}
if (!flag) node1->ele[count+1]=key; //highest element added at end
if (node1->ele[0]==key) //new element is the lowest, hence propogate this till root
{
for (i=leaf-1;i>=0;i--)
{
x=path[i+1];
if (tree[i][path[i]]->ele[x] > key) tree[i][path[i]]->ele[x]=key;
else insert_node(tree[i][x],key);
} }
for (i=0;i<=count+1;i++)
cout<<"\t\t"<<node1->ele[i];
}
void bptree::split(node *oldnode)
{
node *newnode, *parent, *n1, *n2;
int i,j,k,n,t,x,y,pos;
newnode = create_node();
newnode->ele[0]=oldnode->ele[2]; //copy elements to new node
newnode->ele[1]=oldnode->ele[3];
oldnode->ele[2]=-1; //delete entries in old node
oldnode->ele[3]=-1;
t=count[leaf];
n=path[leaf];
for (i=t,j=t+1;i>n;i--,j--) //move the elements in leaf level one place right
tree[leaf][j]=tree[leaf][i];
newnode->next=tree[leaf][n]->next; //updating the next pointers
tree[leaf][n]->next=newnode;
tree[leaf][n+1] = newnode; //insert new node to the tree
count[leaf]++;
x=leaf;
if (count[leaf]+1==1) t=1; else t=log(count[leaf]+1)/log(2); //how many levels does the tree need?
if (t!=leaf) //increase the level of the tree
{
++leaf;
count[leaf]=count[x];
for (i=0;i<=count[leaf];i++) //copy the leaf nodes to the new level
std::swap(tree[leaf][i],tree[x][i]);
}
for (i=leaf-1;i>=0;i--) count[i]=-1; //make the tree empty
for (i=t,j=i-1;i>0;i--,j--)
{
for (k=0;k<=count[i]/3;k++)
{
n1=tree[i][2*k];
n2=tree[i][(2*k)+1];
//for (x=0;n1->ele[x]!=-1;x++); //find last element in the nodes
//for (y=0;n2->ele[y]!=-1;y++);
newnode=create_node();
count[j]++;
tree[j][count[j]]=newnode;
newnode->ele[0]=n1->ele[0];
newnode->child[0]=2*k;
newnode->ele[1]=n2->ele[0];
newnode->child[1]=(2*k)+1;
}
if (count[i]!=1 && count[i]%2==0) //one node is remaining
{
n2=tree[i][count[i]];
//for (y=0;n2->ele[y]!=-1;y++);
newnode->ele[2]=n2->ele[0];
newnode->child[2]=count[i];
}
}
}
void bptree::display_seqset()
{
node *t;
int k;
t=head;
cout<<"\n\nThe sequence set is:";
while (t)
{
for (k=0;t->ele[k]!=-1;k++)
cout<<" "<<t->ele[k];
cout<<"\t";
t=t->next;
}
}
int main()
{
bptree bt;
int choice, key;
while(1)
{
cout<<"\n\n\nMain Menu\n-------------------\n1.Insert\n2.Search\n3.Display Tree\n4.Display Sequence Set\n5.Exit\n\nEnter your choice:";
cin>>choice;
switch(choice)
{
case 1: cout<<"\nEnter the element:";
cin>>key;
bt.insert(key);
break;
case 2:cout<<"Enter the key:";
cin>>key;
bt.main_search(key);
break;
case 3: bt.display_tree();
break;
case 4: bt.display_seqset();
break;
case 5: return 0;
default: cout<<"\nEnter valid choice";
}
}
}
Saturday, 24 November 2012
FS PROGRAM FOR RE USE DELETED SPACE IN INDEXING
#include
<iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class student
{
public:
string USN;
string Name;
string Branch;
int Semester;
string buffer;
int avail[10];
int top;
void initialize();
void read_data();
void pack();
void write_to_file();
void unpack();
int search(string);
int delete_from_file(string);
void modify(string);
};
void student::initialize()
{
top=0;
for (int i=0;i<10;i++)
avail[i]=0;
}
void student::read_data()
{
cout<<"\nUsn:";
cin>>USN;
cout<<"\nName:";
cin>>Name;
cout<<"\nBranch:";
cin>>Branch;
cout<<"\nSemster:";
cin>>Semester;
}
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class student
{
public:
string USN;
string Name;
string Branch;
int Semester;
string buffer;
int avail[10];
int top;
void initialize();
void read_data();
void pack();
void write_to_file();
void unpack();
int search(string);
int delete_from_file(string);
void modify(string);
};
void student::initialize()
{
top=0;
for (int i=0;i<10;i++)
avail[i]=0;
}
void student::read_data()
{
cout<<"\nUsn:";
cin>>USN;
cout<<"\nName:";
cin>>Name;
cout<<"\nBranch:";
cin>>Branch;
cout<<"\nSemster:";
cin>>Semester;
}
void
student::pack()
{
string sem;
stringstream out;
out << Semester;
sem = out.str();
buffer.erase();
buffer+=USN+'|'+Name+'|'+Branch+'|'+sem;
for(;buffer.size()<100;) buffer+='$';
buffer+='\n';
}
void student::write_to_file()
{
fstream file;
int pos;
file.open("1.txt");
pos = avail[top];
if (pos){
file.seekp(pos,ios::beg);
file<<buffer;
top--;
cout<<"\n\nReusing Deleted Space at position:"<<pos;
}
else file<<buffer;
file.close();
}
void student::unpack()
{
string sem;
int ch=1,i=0;
USN.erase();
while (buffer[i]!='|')
USN+=buffer[i++];
Name.erase();
i++;
while (buffer[i]!='|')
Name+=buffer[i++];
Branch.erase();
i++;
while (buffer[i]!='|')
Branch+=buffer[i++];
sem.erase();
i++;
while (buffer[i]!='$')
sem+=buffer[i++];
istringstream out(sem);
out>>Semester;
}
int student::search(string key)
{
ifstream file;
int flag=0, pos=0;
file.open("1.txt",ios::in);
while (!file.eof())
{
buffer.erase();
getline(file,buffer);
unpack();
if (key==USN) {
{
string sem;
stringstream out;
out << Semester;
sem = out.str();
buffer.erase();
buffer+=USN+'|'+Name+'|'+Branch+'|'+sem;
for(;buffer.size()<100;) buffer+='$';
buffer+='\n';
}
void student::write_to_file()
{
fstream file;
int pos;
file.open("1.txt");
pos = avail[top];
if (pos){
file.seekp(pos,ios::beg);
file<<buffer;
top--;
cout<<"\n\nReusing Deleted Space at position:"<<pos;
}
else file<<buffer;
file.close();
}
void student::unpack()
{
string sem;
int ch=1,i=0;
USN.erase();
while (buffer[i]!='|')
USN+=buffer[i++];
Name.erase();
i++;
while (buffer[i]!='|')
Name+=buffer[i++];
Branch.erase();
i++;
while (buffer[i]!='|')
Branch+=buffer[i++];
sem.erase();
i++;
while (buffer[i]!='$')
sem+=buffer[i++];
istringstream out(sem);
out>>Semester;
}
int student::search(string key)
{
ifstream file;
int flag=0, pos=0;
file.open("1.txt",ios::in);
while (!file.eof())
{
buffer.erase();
getline(file,buffer);
unpack();
if (key==USN) {
cout<<"\nFound
the key. The record is
"<<buffer;pos=file.tellg(); flag=1;return pos;}
}
file.close();
if (!flag) {cout<<"\n Not Found \n\n"; return pos;}
}
int student::delete_from_file(string key)
{
fstream file;
char del_mark='*',t;
int pos,flag=0;
pos=search(key);
if (pos){
file.open("1.txt");
pos-=101; //skip the $$$$$$ and \n characters
file.seekp(pos,ios::beg);
file.put(del_mark);
flag=1;
avail[++top]=pos;
cout<<"\n\nThe position of deleted record is:"<<pos;
}
file.close();
if (!flag) {cout<<"\n Not Found \n\n"; return pos;}
}
int student::delete_from_file(string key)
{
fstream file;
char del_mark='*',t;
int pos,flag=0;
pos=search(key);
if (pos){
file.open("1.txt");
pos-=101; //skip the $$$$$$ and \n characters
file.seekp(pos,ios::beg);
file.put(del_mark);
flag=1;
avail[++top]=pos;
cout<<"\n\nThe position of deleted record is:"<<pos;
}
file.close();
buffer.empty();
if (!flag) return 0;
else return 1;
}
void student::modify(string key)
{
int choice;
if (delete_from_file(key)){
cout<<"\n What to modify?";
cin>>choice;
switch(choice)
{
case 1: cout<<"\nUSN:"; cin>>USN; break;
case 2: cout<<"\nName:";cin>>Name;break;
case 3: cout<<"\nBranch:";cin>>Branch;break;
case 4: cout<<"\nSemster:";cin>>Semester;break;
default: cout <<"Wrong Choice";
}
buffer.erase();
pack();
write_to_file();
}
}
int main()
{
int count,choice,len,i;
student s1;
s1.initialize();
string key;
while(1){
cout <<"\nMain Menu\n 1.Add \n\n 2.Delete \n\n 3.Modify \n\n 4.Search \n\n 5.Exit\n\nEnter the choice:";
cin>>choice;
switch (choice)
{
case 1: cout<<"Data\n";
s1.read_data();
s1.pack();
s1.write_to_file();
break;
case 2: cout <<"\n\nEnter the key";
cin>>key;
i=s1.delete_from_file(key);
break;
case 3: cout <<"\n\nEnter the key";
cin>>key;
s1.modify(key);
break;
case 4: cout <<"\n\nEnter the key";
cin>>key;
i=s1.search(key);
break;
case 5: return 0;
default: cout<<"\n\nWrong Choice";
}
file.close();
buffer.empty();
if (!flag) return 0;
else return 1;
}
void student::modify(string key)
{
int choice;
if (delete_from_file(key)){
cout<<"\n What to modify?";
cin>>choice;
switch(choice)
{
case 1: cout<<"\nUSN:"; cin>>USN; break;
case 2: cout<<"\nName:";cin>>Name;break;
case 3: cout<<"\nBranch:";cin>>Branch;break;
case 4: cout<<"\nSemster:";cin>>Semester;break;
default: cout <<"Wrong Choice";
}
buffer.erase();
pack();
write_to_file();
}
}
int main()
{
int count,choice,len,i;
student s1;
s1.initialize();
string key;
while(1){
cout <<"\nMain Menu\n 1.Add \n\n 2.Delete \n\n 3.Modify \n\n 4.Search \n\n 5.Exit\n\nEnter the choice:";
cin>>choice;
switch (choice)
{
case 1: cout<<"Data\n";
s1.read_data();
s1.pack();
s1.write_to_file();
break;
case 2: cout <<"\n\nEnter the key";
cin>>key;
i=s1.delete_from_file(key);
break;
case 3: cout <<"\n\nEnter the key";
cin>>key;
s1.modify(key);
break;
case 4: cout <<"\n\nEnter the key";
cin>>key;
i=s1.search(key);
break;
case 5: return 0;
default: cout<<"\n\nWrong Choice";
}
}
}
}
Wednesday, 21 November 2012
OS MVT PROGRAM
#include<stdio.h>
#include<stdlib.h>
void main()
{
int m=0,m1=0,m2=0,p,count=0,i;
printf("\n enter the memory capacity:");
scanf("%d",&m);
printf("\n enter the no of processes:");
scanf("%d",&p);
for(i=0;i<p;i++)
{
printf("\n Enter memory required for process%d: ",i+1);
scanf("%d",&m1);
count=count+m1;
if(m1<=m)
{
if(count==m)
printf("\n there is no further memory remaining:");
printf(" \n the memory allocated for process%d is: %d \n ",i+1,m);
m2=m-m1;
printf("\n remaining memory is: %d",m2);
m=m2;
}
else
{
printf("\n memory is not allocated for process%d",i+1);
}
printf("\n external fragmentation for this process is:%d \n",m2);
}
}
Subscribe to:
Posts (Atom)