------------------------------------------------
Program 1:
------------------------------------------------
#include<iostream.h>#include<string.h>
#include<conio.h>
class Item
{
public:
char item_name[20];
int item_cat,quantity;
float price;
void getdata(char *,int,int,float);
// void display();
};
void Item::getdata(char *s,int c,int q,float p)
{
strcpy(item_name,s);
item_cat = c;
quantity = q;
price = p;
}
void Display(Item Veg[],Item Fruit[],int count1,int count2)
{
if(count1!=0)
{
for(int i=0;i<count1;i++)
{
cout<<"\nItem Name:"<<Veg[i].item_name;
cout<<"\nItem Cat:"<<Veg[i].item_cat;
cout<<"\nItem Quantity:"<<Veg[i].quantity;
cout<<"\nItem Cost:"<<Veg[i].price;
}
}
if(count2!=0)
{
for(int i=0;i<count2;i++)
{
cout<<"\nItem Name:"<<Fruit[i].item_name;
cout<<"\nItem Cat:"<<Fruit[i].item_cat;
cout<<"\nItem Quantity:"<<Fruit[i].quantity;
cout<<"\nItem Cost:"<<Fruit[i].price;
}
}
}
void main()
{
Item Veg[50];
Item Fruit[50];
char Iname[20];
int cat, amt,no,count1=0,count2=0;
float cost;
void Display(Item V[],Item F[],int,int);
clrscr();
cout<<"\nEnter the number of vegetables:";
cin>>no;
for(int i=0;i<no;i++)
{
cout<<"\nEnter item name:";
cin>>Iname;
cout<<"\nEnter item cat:";
cin>>cat;
cout<<"\nEnter item amt:";
cin>>amt;
cout<<"\nEnter item cost:";
cin>>cost;
if(cat==0)
{
//Veg[count1] = new Item;
Veg[count1].getdata(Iname,cat,amt,cost);
count1++;
// k++;
}
}
cout<<"\nEnter the number of fruits:";
cin>>no;
for(i=0;i<no;i++)
{
cout<<"\nEnter item name:";
cin>>Iname;
cout<<"\nEnter item cat:";
cin>>cat;
cout<<"\nEnter item amt:";
cin>>amt;
cout<<"\nEnter item cost:";
cin>>cost;
// Fruit[count2] = new Item;
Fruit[count2].getdata(Iname,cat,amt,cost);
count2++;
}
cout<<"\nItems purchased are:-";
Display(Veg,Fruit,count1,count2);
getch();
}
------------------------------------------------
Program 2:
------------------------------------------------
#include<iostream.h>#include<conio.h>
#include<string.h>
//using namespace std;
struct node
{
char word[20];
char meaning[100];
node *next;
node *prev;
};
void addnode();
void delnode();
void display();
void update();
void sort();
void search();
node *start=NULL, *temp1, *temp2, *temp3;
int main()
{
char ch;
clrscr();
do
{
char i;
cout<<"Press 'a' to add node \n 'd' to delete"<<endl;
cout<<"'v' for display \n'u' for update"<<endl;
cout<<" 'r' to sort nodes\n 's' for search"<<endl;
cin>>i;
switch (i)
{
case'a':
addnode();
break;
case'd':
delnode();
break;
case'v' :
display();
break;
case 'r':
sort();
break;
case 'u':
update();
break;
case 's':
search();
break;
default:
cout<<"Bad input"<<endl;
break;
}
cout<<"want to process more y/n"<<endl;
cin>>ch;
}
while(ch!='n');
getch();
return 0;
}
void sort()
{
node *i,*j;
char tmp[20],tmp1[100];
for(i=start;i!=NULL;i=i->next)
{
for(j=i;j!=NULL;j=j->next)
{
if(strcmp(i->word,j->word)>0)
{
strcpy(tmp,i->word);
strcpy(tmp1,i->meaning);
strcpy(i->word,j->word);
strcpy(i->meaning,j->meaning);
strcpy(j->word,tmp);
strcpy(j->meaning,tmp1);
}
}
}
cout<<"\n\tSorted list in ascending order is:";
display();
}
void addnode() //adding node
{
char r;
temp1=new node;
cout<<"enter word to be stored"<<endl;
cin>>temp1->word;
cout<<"enter meaning to be stored"<<endl;
cin>>temp1->meaning;
if(start!=NULL)
{
cout<<"press 's' to add in start,'m' for midd , 'e' for end"<<endl;
cin>>r;
}
else r='s';
switch (r)
{
case's': //add start
if(start==NULL)
{
start=temp1;
temp1->next=NULL;
temp1->prev=NULL;
}
else
{
temp2=start;
temp1->next=temp2;
temp1->prev=NULL;
start=temp1;
temp2->prev=temp1;
}
break;
case'e': //add end
if(start==NULL)
{
start=temp1;
temp1->next=NULL;
temp1->prev=NULL;
}
else
{
temp2=start;
while(temp2->next!=NULL)
temp2=temp2->next;
temp2->next=temp1;
temp1->prev=temp2;
temp1->next=NULL;
}
break;
case'm': //add mid
int num;
cout<<"enter node after which you want to enter"<<endl;
cin>>num;
temp2=start;
for(int i=0;i<num;i++)
{
if(start==NULL)
cout<<"given node not found"<<endl;
else
{
temp3=temp2;
temp2=temp2->next;
}
}
temp1->next=temp2;
temp3->next=temp1;
temp1->prev=temp3;
temp2->prev=temp1;
break;
}
}
void display() //displaying
{
temp3=start;
if(start==NULL)
cout<<"no node to display"<<endl;
else
{
while(temp3->next!=NULL)
{
cout<<"\nWord: "<<temp3->word<<"\t Meaning:"<<temp3->meaning<<endl;
temp3=temp3->next;
}
cout<<"\nWord: "<<temp3->word<<"\t Meaning:"<<temp3->meaning<<endl;
}
}
void update() //update
{
char p[20];
char str[50];
int flag=0;
cout<<"enter word whose meaning is to be updated:"<<endl;
cin>>p;
temp1=start;
while(temp1->next!=NULL)
{
if(strcmp(temp1->word,p)==0)
{
cout<<"Enter new meaning";
cin>>str;
strcpy(temp1->meaning,str);
cout<<"Meaning updated successfully!!!";
flag=1;
}
temp1=temp1->next;
}
if(flag==0)
{
cout<<"Word not found in dictionary";
}
}
void search() //search
{
char p[20];
char str[50];
int flag=0;
int count=0;
cout<<"enter word to be searched:"<<endl;
cin>>p;
temp1=start;
while(temp1->next!=NULL)
{ count++;
if(strcmp(temp1->word,p)==0)
{
flag=1;
cout<<"Word found and its meaning is: "<<temp1->meaning<<endl;
cout<<"Total comparisions made are:"<<count<<endl;
}
temp1=temp1->next;
}
if(flag==0) //last node comparision
{ count++;
if(strcmp(temp1->word,p)==0)
{
flag=1;
cout<<"Word found and its meaning is: "<<temp1->meaning<<endl;
cout<<"Total comparisions made are:"<<count<<endl;
}
}
if(flag==0)
{
cout<<"Word not found in dictionary"<<endl;
}
}
void delnode() //deleting
{
char p[20];
int flag=0;
cout<<"enter word to be deleted:"<<endl;
cin>>p;
temp1=start;
while(temp1->next!=NULL)
{
if(strcmp(temp1->word,p)==0)
{
if(temp1==start) // first node
{
start=start->next;
start->prev=NULL;
delete temp1;
}
else if(temp1->next==NULL) //last node
{
temp1->prev->next=NULL;
delete temp1;
}
else //mid node
{
temp1->prev->next=temp1->next;
temp1->next->prev=temp1->prev;
delete temp1;
}
flag=1;
}
temp1=temp1->next;
}
if(flag==0)
{
cout<<"Word not found in dictionary";
}
}
------------------------------------------------
Program 3:
------------------------------------------------
#include <iostream>
using namespace std;
int g[20][20];
int cost[20][20];
int visit[20];
int TotalCost=0;
int source=0,no;
int route[30], minRoute[30],index=0;
int main()
{
int v1,k,i,j,minCost=9999,t,connected=0;
int TotalCost=0;
void create();
void dfs(int);
create();
for(v1=0;v1<20;v1++) //Initialize all vertex as unvisited
{
visit[v1] = 0;
}
for(k=0;k<no+1;k++) // run loop for all vertices
{
for(t=0;t<20;t++) // for each vertex check whether it is connected to any other vertex
{
if(g[k][t]==1)
{
connected=1; // mark its connected flag as 1 if it is connected to atleast 1 vertex
}
}
if(connected==1) //if atleast 1 edge is entered for the vertex
{
index=0;
cout<<"Depth first search route from house (vertex) "<<k<<" is:-\n";
dfs(k);
for(i=0;i<index-1;i++)//run loop for all vertices stored in route array
{
if(g[route[i]][route[i+1]]==1) // find if both are directly connected
{
TotalCost = TotalCost+cost[route[i]][route[i+1]]; // add their cost if yes
}
else
{
if(visit[route[i]]==1&&visit[route[i+1]]==1) // if not directly connected add 1000 to total cost
TotalCost = TotalCost+1000;
}
}
if(TotalCost<minCost)//check if this route's cost is minimum
{
minCost = TotalCost;
for(j=0;j<index;j++) // if yes copy the current route as minimum route
{
minRoute[j]=route[j];
}
}
cout<<"Total Cost for this route is:"<<TotalCost<<endl;
for(v1=0;v1<20;v1++)
{
visit[v1] = 0; //mark all vertices as unvisited
}
for(v1=0;v1<30;v1++)
{
route[v1] = 0; //reinitialize the route array
}
TotalCost=0;
connected=0;
} //if
}//for k
cout<<"Route with less effort (minimum cost) is:- ";
for(j=0;j<index;j++)
{
cout<<minRoute[j]<<"\t";
}
cout<<" and its length (cost) is "<<minCost;
return 0;
}
void create()
{
int v1,v2;
int weight=0;
cout<<"Enter the no of houses (vertices in graph):";
cin>>no;
do
{
cout<<"Enter the path between 2 houses (edge of a graph by two vertices):- ( Press -1 to exit) \n";
cin>>v1;
if(v1==-1)
break;
cin>>v2;
cout<<"Enter cost:\n";
cin>>weight;
g[v1][v2]=1;
g[v2][v1]=1;
cost[v1][v2]= weight;
cost[v2][v1]= weight;
}while(v1!=-1||v2!=-1); //accept edges until -1 is hit
}
void dfs(int v1)
{
int v2;
cout<<"\t"<<v1<<"\n";
visit[v1]=1; // mark this vertex as visited
route[index]=v1; // insert this vertex in route array
index++;
for(v2=0;v2<20;v2++) // check the neighbors of this vertex
{
if(g[v1][v2]==1&&visit[v2]==0) //check whether an edge exists between v1 & v2; also check whether v2 vertex is unvisited
{
dfs(v2);
}
}
}
/*******************************************************************************************
OUTPUT:
Enter the no of houses (vertices in graph):6
Enter the path between 2 houses (edge of a graph by two vertices):- ( Press -1 to exit)
1 2
Enter cost:
2
Enter the path between 2 houses (edge of a graph by two vertices):- ( Press -1 to exit)
1 3
Enter cost:
9
Enter the path between 2 houses (edge of a graph by two vertices):- ( Press -1 to exit)
2 4
Enter cost:
6
Enter the path between 2 houses (edge of a graph by two vertices):- ( Press -1 to exit)
3 5
Enter cost:
1
Enter the path between 2 houses (edge of a graph by two vertices):- ( Press -1 to exit)
5 6
Enter cost:
4
Enter the path between 2 houses (edge of a graph by two vertices):- ( Press -1 to exit)
-1
Depth first search route from house (vertex) 1 is:-
1
2
4
3
5
6
Total Cost for this route is:1013
Depth first search route from house (vertex) 2 is:-
2
1
3
5
6
4
Total Cost for this route is:1016
Depth first search route from house (vertex) 3 is:-
3
1
2
4
5
6
Total Cost for this route is:1021
Depth first search route from house (vertex) 4 is:-
4
2
1
3
5
6
Total Cost for this route is:22
Depth first search route from house (vertex) 5 is:-
5
3
1
2
4
6
Total Cost for this route is:1018
Depth first search route from house (vertex) 6 is:-
6
5
3
1
2
4
Total Cost for this route is:22
Route with less effort (minimum cost) is:- 4 2 1 3 5 6 and its length (cost) is 22
------------------------------------------------
Program 4:
------------------------------------------------
//============================================================================
// Name : avl.cpp
// Author : ssk
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include<fstream>
#include<string.h>
using namespace std;
// An AVL tree node
struct node
{
char word[20],meaning[30];
struct node *left;
struct node *right;
int height;
};
node *tnode;
// A utility function to get maximum of two integers
int max(int a, int b);
// A utility function to get height of the tree
int height(struct node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct node* newNode(char w[],char m[])
{
//node * tnode;
tnode = new node;
strcpy(tnode->word,w);
strcpy(tnode->meaning,m);
tnode->left = NULL;
tnode->right = NULL;
tnode->height = 1; // new node is initially added at leaf
return(tnode);
}
// A utility function to right rotate subtree rooted with y
struct node *rightRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
struct node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(struct node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, char w[],char m[])
{
/* 1. Perform the normal BST rotation */
if (node == NULL)
return(newNode(w,m));
if (strcmp(w,node->word)<0)
node->left = insert(node->left, w,m);
else
node->right = insert(node->right, w,m);
/* 2. Update height of this ancestor node */
node->height = max(height(node->left), height(node->right)) + 1;
/* 3. Get the balance factor of this ancestor node to check whether
this node became unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && (strcmp(w,node->left->word)<0))// word < node->left->word)
return rightRotate(node);
// Right Right Case
if (balance < -1 && (strcmp(w,node->right->word)>0)) //word > node->right->word)
return leftRotate(node);
// Left Right Case
if (balance > 1 && (strcmp(w,node->left->word)>0)) //word > node->left->word)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && (strcmp(w,node->right->word)<0)) // word < node->right->word)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// A utility function to print preorder traversal of the tree.
// The function also prints height of every node
void preOrder(struct node *root)
{
if(root != NULL)
{
cout<< root->word << "--"<<root->meaning<<endl;
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(struct node *root)
{
if(root != NULL)
{
inOrder(root->left);
cout<< root->word << "--"<<root->meaning<<endl;
inOrder(root->right);
}
}
void search(struct node *root,char k[])
{
node *temp;
temp=root;
int flag=0;
while(temp!=NULL)
{
if(strcmp(temp->word,k)==0)
{
flag=1;
cout<<"Word is found and its meaning is "<<temp->word<<"--"<<temp->meaning;
break;
}
if(strcmp(temp->word,k)>0)
{
temp=temp->left;
}
else
{
temp=temp->right;
}
}
if(flag==0)
{
cout<<"Word is not found in dictionary\n";
}
}
/* Drier program to test above function*/
int main()
{
struct node *root = NULL;
int choice;
char searchword[20];
fstream fp;
fp.open("dict.txt", ios::in );
char data[30],data1[30],data2[30] ;
if(fp==NULL)
{
cout<<"Error in opening file !!";
}
else
{
cout<<"Words from dictionary are:- "<<endl;
while(fp >> data)
{
//fp>>data;
// cout<<data<<endl;
strcpy(data1,data);
fp>>data2;
cout<<data1<<"--"<<data2<<endl;
if(strcmp(data,"")!=0)
{
root = insert(root, data1,data2);
}
//cout << word << endl;
}
}
do
{
cout<<"\n\n MENU: ";
cout<<"\n\n\t1.Display words in preorder\n\n\t2.Display words in inorder\n\n\t3.Search a word\n\n\t4.Exit\n\n\t";
cout<<"\n\nEnter the choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Preorder traversal of the constructed AVL tree is \n";
preOrder(root);
break;
case 2:
cout<<"Inorder traversal of the constructed AVL tree is \n";
inOrder(root);
break;
case 3:
cout<<"Enter the word to be searched";
cin>>searchword;
search(root,searchword);
break;
}
}while(choice!=4);
return 0;
}
**********************************************************************************************
OUTPUT:
Words from dictionary are:-
hello--greet
persuade--convince
aid--help
mend--repair
fortunate--lucky
deny--refuse
MENU:
1.Display words in preorder
2.Display words in inorder
3.Search a word
4.Exit
Enter the choice: 1
Preorder traversal of the constructed AVL tree is
hello--greet
deny--refuse
aid--help
fortunate--lucky
persuade--convince
mend--repair
MENU:
1.Display words in preorder
2.Display words in inorder
3.Search a word
4.Exit
Enter the choice: 2
Inorder traversal of the constructed AVL tree is
aid--help
deny--refuse
fortunate--lucky
hello--greet
mend--repair
persuade--convince
MENU:
1.Display words in preorder
2.Display words in inorder
3.Search a word
4.Exit
Enter the choice: 3
Enter the word to be searchedhello
Word is found and its meaning is hello--greet
MENU:
1.Display words in preorder
2.Display words in inorder
3.Search a word
4.Exit
Enter the choice: 4
------------------------------------------------
Program 5:
------------------------------------------------
//Cosider only undirected graph
#include<iostream>
using namespace std;
struct edge
{
int wt;
};
int n;
edge g[10][10];
int main()
{
int src,dest;
void get();
int shrt(int,int);
cout<<"Enter no of vertices:";
cin>>n;
get();
cout<<"Enter the source";
cin>>src;
cout<<"Enter destination:";
cin>>dest;
cout<<"shortest path is:"<<shrt(src,dest);
return 0;
}
void get()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"Enter edge of V"<<i<<"to"<<"& V"<<j;
cin>>g[i][j].wt;
}
}
}
int shrt(int src,int dest)
{
int small,perm[10],dist[10],current,start,new1;
int k=1,temp,i;
for(i=0;i<=n;i++)
{
perm[i]=0;
dist[i]=999;
}
perm[src]=1;
dist[src]=0;
current=src;
cout<<"path is:"<<src;
while(current!=dest)
{
small=999;
start=dist[current];
for(i=1;i<=n;i++)
{
if(perm[i]==0)
{
new1=start+g[current][i].wt;
if(new1<dist[i])
dist[i]=new1;
if(dist[i]<small)
{
small=dist[i];
temp=i;
}
}
}
current=temp;
perm[current]=1;
k++;
cout<<current;
}Enter no of vertices:4
Enter edge of V1to& V1999
Enter edge of V1to& V21
Enter edge of V1to& V32
Enter edge of V1to& V48
Enter edge of V2to& V11
Enter edge of V2to& V2999
Enter edge of V2to& V33
Enter edge of V2to& V4999
Enter edge of V3to& V12
Enter edge of V3to& V23
Enter edge of V3to& V3999
Enter edge of V3to& V45
Enter edge of V4to& V18
Enter edge of V4to& V2999
Enter edge of V4to& V35
Enter edge of V4to& V4999
Enter the source2
Enter destination:4
path is:2134shortest path is:8
return(small);
}
**********************************************************************
OUTPUT:
Enter no of vertices:4
Enter edge of V1to& V1999
Enter edge of V1to& V21
Enter edge of V1to& V32
Enter edge of V1to& V48
Enter edge of V2to& V11
Enter edge of V2to& V2999
Enter edge of V2to& V33
Enter edge of V2to& V4999
Enter edge of V3to& V12
Enter edge of V3to& V23
Enter edge of V3to& V3999
Enter edge of V3to& V45
Enter edge of V4to& V18
Enter edge of V4to& V2999
Enter edge of V4to& V35
Enter edge of V4to& V4999
Enter the source2
Enter destination:4
path is:2134shortest path is:8
------------------------------------------------
Program 6:
------------------------------------------------
f=open("//home//student//sam.txt",'r') #file read modea,e,i,o,u=0,0,0,0,0
for x in f.read(): #read vowels from file
if x=='a':
a+=1
if x=='e':
e+=1
if x=='i':
i+=1
if x=='o':
o+=1
if x=='u':
u+=1
f.seek(0)
s=f.readlines()
words=[]
at=0
white=0
dollar=0
hash1=0
excl=0
for v in s:
white+=str(v).count(' ') #count number of white space
for j in v.split(): #for finding words it splits the line
words.append(j)
at+=str(j).count('@')
dollar+=str(j).count('$')
hash1+=str(j).count('#')
excl+=str(j).count('@')
print words,'\n',len(words),'\n',len(s),'\n',at,'\n',dollar,'\n',hash1,'\n',excl,'\n',white
resultFile=open('//home//student//result.txt','w')
resultFile.write("words are "+str((words)))
resultFile.write("number of words are "+str(len(words)))
resultFile.write("\nnumber of lines are "+str(len(s)))
resultFile.write("\ncount of vowel a "+str(a))
resultFile.write("\ncount of vowel e "+str(e))
resultFile.write("\ncount of vowel i "+str(i))
resultFile.write("\ncount of vowel o "+str(o))
resultFile.write("\ncount of vowel u "+str(u))
resultFile.write("\n$ count "+str(dollar))
resultFile.write("\n# count "+str(hash1))
resultFile.write("\n! count "+str(excl))
resultFile.write("\n@ count "+str(at))
resultFile.write("\n White Space "+str(white))
resultFile.close()
------------------------------------------------
Program 7:
------------------------------------------------
#include <iostream>
using namespace std;
struct node
{
int data,lth,rth;
node *left,*right;
};
node *New,*dummy,*root,*temp,*parent;
void create()
{
void insert(node *,node*);
New = new node;
New->left=NULL;
New->right=NULL;
New->lth=0;
New->rth=0;
cout<<"Enter elements:"<<endl;
cin>>New->data;
if(root==NULL)
{
root = New;
dummy = new node;
dummy->data=-999;
dummy->left=root;
root->left=dummy;
root->right=dummy;
}
else
{
insert(root,New);
}
}
void insert(node *root,node *New)
{
if(New->data<root->data)
{
if(root->lth==0)
{
New->left=root->left;
New->right=root;
root->left=New;
root->lth=1;
}
else
insert(root->left,New);
}
if(New->data>root->data)
{
if(root->rth==0)
{
New->right=root->right;
New->left=root;
root->right=New;
root->rth=1;
}
else
insert(root->right,New);
}
}
void inorder()
{
if(root==NULL)
cout<<"Tree is not created.."<<endl;
else
{
temp=root;
cout<<"Tree is:-"<<endl;
while(temp!=dummy)
{
while(temp->lth==1)
{
temp=temp->left;
}
cout<<""<<temp->data;
while(temp->rth==0)
{
temp=temp->right;
if(temp==dummy)
return;
cout<<""<<temp->data;
}
temp=temp->right;
}
}
}
void find()
{
node *search(node *,node *,int,node *);
int key;
cout<<"Enter the element to be searched";
cin>>key;
temp=search(root,dummy,key,parent);
if(temp==NULL)
cout<<"Element not present";
}
node *search(node *root,node *dummy,int key,node *parent)
{
node *temp;
int flag=0;
temp=root;
while((temp!=dummy))
{
if(temp->data==key)
{
cout<<"The element "<<temp->data<<" is present";
flag=1;
return temp;
}
parent=temp;
if(temp->data>key)
temp=temp->left;
else
temp=temp->right;
}
return NULL;
}
int main()
{
int ch;
char ans='n';
do
{
cout << "\n1.Create Threaded Binary Tree" ;
cout << "\n2.Display Inorder Threaded Binary Tree" << endl;
cout << "\n3.Search node in Threaded Binary Tree" << endl;
cin>>ch;
switch(ch)
{
case 1:
do
{
create();
cout<<"Do u want to add more elements? "<<endl;
cin>>ans;
}while(ans=='y');
break;
case 2:
inorder();
break;
case 3:
find();
break;
}
}
while(ch<4);
return 0;
}
/*********************************************************
*
1.Create Threaded Binary Tree
2.Display Inorder Threaded Binary Tree
3.Search node in Threaded Binary Tree
1
Enter elements:
4
Do u want to add more elements?
y
Enter elements:
7
Do u want to add more elements?
y
Enter elements:
1
Do u want to add more elements?
y
Enter elements:
3
Do u want to add more elements?
n
1.Create Threaded Binary Tree
2.Display Inorder Threaded Binary Tree
3.Search node in Threaded Binary Tree
2
Tree is:-
1347
1.Create Threaded Binary Tree
2.Display Inorder Threaded Binary Tree
3.Search node in Threaded Binary Tree
3
Enter the element to be searched3
The element 3 is present
1.Create Threaded Binary Tree
2.Display Inorder Threaded Binary Tree
3.Search node in Threaded Binary Tree
3
Enter the element to be searched10
Element not present
1.Create Threaded Binary Tree
2.Display Inorder Threaded Binary Tree
3.Search node in Threaded Binary Tree
* ******************************************/
*/
------------------------------------------------
Program 8:
------------------------------------------------
#include <iostream>
using namespace std;
char square[10] = {'o','1','2','3','4','5','6','7','8','9'};
int checkwin();
void board();
int main()
{
int player = 1,i,choice;
char mark;
do
{
board();
player=(player%2)?1:2;
cout << "Player " << player << ", enter a number: ";
cin >> choice;
mark=(player == 1) ? 'X' : 'O';
if (choice == 1 && square[1] == '1')
square[1] = mark;
else if (choice == 2 && square[2] == '2')
square[2] = mark;
else if (choice == 3 && square[3] == '3')
square[3] = mark;
else if (choice == 4 && square[4] == '4')
square[4] = mark;
else if (choice == 5 && square[5] == '5')
square[5] = mark;
else if (choice == 6 && square[6] == '6')
square[6] = mark;
else if (choice == 7 && square[7] == '7')
square[7] = mark;
else if (choice == 8 && square[8] == '8')
square[8] = mark;
else if (choice == 9 && square[9] == '9')
square[9] = mark;
else
{
cout<<"Invalid move ";
player--;
}
i=checkwin();
player++;
}while(i==-1);
board();
if(i==1)
cout<<"==>\tPlayer "<<--player<<" wins ";
else
cout<<"==>\tGame draw";
return 0;
}
/*********************************************
FUNCTION TO RETURN GAME STATUS
1 FOR GAME IS OVER WITH RESULT
-1 FOR GAME IS IN PROGRESS
O GAME IS OVER AND NO RESULT
**********************************************/
int checkwin()
{
if (square[1] == square[2] && square[2] == square[3])
return 1;
else if (square[4] == square[5] && square[5] == square[6])
return 1;
else if (square[7] == square[8] && square[8] == square[9])
return 1;
else if (square[1] == square[4] && square[4] == square[7])
return 1;
else if (square[2] == square[5] && square[5] == square[8])
return 1;
else if (square[3] == square[6] && square[6] == square[9])
return 1;
else if (square[1] == square[5] && square[5] == square[9])
return 1;
else if (square[3] == square[5] && square[5] == square[7])
return 1;
else if (square[1] != '1' && square[2] != '2' && square[3] != '3' &&
square[4] != '4' && square[5] != '5' && square[6] != '6' &&
square[7] != '7' && square[8] != '8' && square[9] != '9')
return 0;
else
return -1;
}
/*******************************************************************
FUNCTION TO DRAW BOARD OF TIC TAC TOE WITH PLAYERS MARK
********************************************************************/
void board()
{
cout << "\n\n\tTic Tac Toe\n\n";
cout << "Player 1 (X) - Player 2 (O)" << endl << endl;
cout << endl;
cout << " | | " << endl;
cout << " " << square[1] << " | " << square[2] << " | " << square[3] << endl;
cout << "_____|_____|_____" << endl;
cout << " | | " << endl;
cout << " " << square[4] << " | " << square[5] << " | " << square[6] << endl;
cout << "_____|_____|_____" << endl;
cout << " | | " << endl;
cout << " " << square[7] << " | " << square[8] << " | " << square[9] << endl;
cout << " | | " << endl << endl;
}
************************************************************************
OUTPUT:
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
1 | 2 | 3
_____|_____|_____
| |
4 | 5 | 6
_____|_____|_____
| |
7 | 8 | 9
| |
Player 1, enter a number: 1
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
X | 2 | 3
_____|_____|_____
| |
4 | 5 | 6
_____|_____|_____
| |
7 | 8 | 9
| |
Player 2, enter a number: 2
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
X | O | 3
_____|_____|_____
| |
4 | 5 | 6
_____|_____|_____
| |
7 | 8 | 9
| |
Player 1, enter a number: 4
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
X | O | 3
_____|_____|_____
| |
X | 5 | 6
_____|_____|_____
| |
7 | 8 | 9
| |
Player 2, enter a number: 7
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
X | O | 3
_____|_____|_____
| |
X | 5 | 6
_____|_____|_____
| |
O | 8 | 9
| |
Player 1, enter a number: 5
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
X | O | 3
_____|_____|_____
| |
X | X | 6
_____|_____|_____
| |
O | 8 | 9
| |
Player 2, enter a number: 6
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
X | O | 3
_____|_____|_____
| |
X | X | O
_____|_____|_____
| |
O | 8 | 9
| |
Player 1, enter a number: 9
Tic Tac Toe
Player 1 (X) - Player 2 (O)
| |
X | O | 3
_____|_____|_____
| |
X | X | O
_____|_____|_____
| |
O | 8 | X
| |
==> Player 1 wins
------------------------------------------------
Program 9:
------------------------------------------------
#Depth First Search & Breadth First Search Traversal of Graph
class GraphTraversals():
def __init__(self):
self.vertices=[]
self.adjacencyList=[]
#function to vertices
def getVertices(self):
try:
nVertices=int(raw_input('Enter number of vertices-->'))
for i in range(nVertices):
self.vertices.append(raw_input('Enter Node-->'))
except:
print 'enter integer value'
#function to enter adjacency list
def getAdjacentNodes(self):
if len(self.vertices)>1:
for node in self.vertices:
adjNodes=[]
try:
print 'Enter number of adjacent nodes of -->',node
nAdj=int(raw_input())
for i in range(nAdj):
print 'Enter adjacent node of-->',node
adjNodes.append(raw_input())
self.adjacencyList.append(adjNodes)
except:
print 'Enter proper value'
else:
print 'No vertex found!'
#Function to calculate dfs path of graph
def dfs(self,start ,path=[]):
path=path+[start]
for vertex in self.adjacencyList[self.vertices.index(start)]:
if not vertex in path:
path=self.dfs(vertex, path)
return path
#Function to calculate bfs path of graph
def bfs(self, start, path=[]):
q=[start]
while q:
v=q.pop(0)
if not v in path:
path=path+[v]
for i in self.adjacencyList[self.vertices.index(v)]:
q.append(i)
return path
def dfsTraversal(self):
startVertex=raw_input('Enter Start Vertex-->')
return self.dfs(startVertex)
def bfsTraversal(self):
startVertex=raw_input('Enter Start Vertex-->')
return self.bfs(startVertex)
#Syntax to mention program execution starts from below
if __name__ == '__main__':
graph=GraphTraversals()
graph.getVertices()
graph.getAdjacentNodes()
print 'Vertices are',graph.vertices
print 'Adjacency List is-->',graph.adjacencyList
print 'DFS Traversal Path-->',graph.dfsTraversal()
print 'BFS Traversal Path-->',graph.bfsTraversal()
'''
##s##v##g##
OUTPUT
##s##v##g##
Enter number of vertices-->7
Enter Node-->a
Enter Node-->b
Enter Node-->c
Enter Node-->d
Enter Node-->e
Enter Node-->f
Enter Node-->g
Enter number of adjacent nodes of --> a-->2
Enter adjacent node of--> a-->b
Enter adjacent node of--> a-->c
Enter number of adjacent nodes of --> b-->4
Enter adjacent node of--> b-->a
Enter adjacent node of--> b-->c
Enter adjacent node of--> b-->d
Enter adjacent node of--> b-->e
Enter number of adjacent nodes of --> c-->4
Enter adjacent node of--> c-->a
Enter adjacent node of--> c-->b
Enter adjacent node of--> c-->f
Enter adjacent node of--> c-->g
Enter number of adjacent nodes of --> d-->2
Enter adjacent node of--> d-->b
Enter adjacent node of--> d-->e
Enter number of adjacent nodes of --> e-->3
Enter adjacent node of--> e-->d
Enter adjacent node of--> e-->b
Enter adjacent node of--> e-->f
Enter number of adjacent nodes of --> f-->3
Enter adjacent node of--> f-->e
Enter adjacent node of--> f-->c
Enter adjacent node of--> f-->g
Enter number of adjacent nodes of --> g-->2
Enter adjacent node of--> g-->c
Enter adjacent node of--> g-->f
Vertices are--> ['a', 'b', 'c', 'd', 'e', 'f', 'g']
Adjacency List is-->[['b', 'c'], ['a', 'c', 'd', 'e'], ['a', 'b', 'f', 'g'], ['b', 'e'], ['d', 'b', 'f'], ['e', 'c', 'g'], ['c', 'f']]
Enter Start Vertex-->a
DFS Traversal Path--> ['a', 'b', 'c', 'f', 'e', 'd', 'g']
Enter Start Vertex-->a
BFS Traversal Path--> ['a', 'b', 'c', 'd', 'e', 'f', 'g']
'''
------------------------------------------------
Program 10:
------------------------------------------------
#include <iostream>using namespace std;
int n;
int p[10],q[10],w[10][10],c[10][10],r[10][10];
char a[10][10];
void getdata()
{
int i;
cout<<"\n Optimal Binary Search Tree"<<endl;
cout<<"\n Number of nodes:-"<<endl;
cin>>n;
cout<<"\n p is the probablility of success & q is probability that the element is not found";
cout<<"\n Enter the data:-" ;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]:- ";
cin>>a[i];
}
for(i=1;i<=n;i++)
{
cout<<"p["<<i<<"]:- ";
cin>>p[i];
}
for(i=0;i<=n;i++)
{
cout<<"q["<<i<<"]:- ";
cin>>q[i];
}
}
int min_value(int i,int j)
{
int m,k;
int minimum = 32000;
for(m=r[i][j-1];m<=r[i+1][j];m++)
{
if((c[i][m-1]+c[m][j])<minimum)
{
minimum = c[i][m-1]+c[m][j];
k=m;
}
}
return k;
}
void OBST()
{
int i,j,k,l,m;
for(i=0;i<n;i++)
{
w[i][i]=q[i];
r[i][i]=c[i][i]=0;
w[i][i+1] = q[i]+q[i+1]+p[i+1];
r[i][i+1]=i+1;
c[i][i+1]=q[i]+q[i+1]+p[i+1];
}
w[n][n]=q[n];
r[n][n]=c[n][n] = 0;
for(m=2;m<=n;m++)
{
for(i=0;i<n-m+1;i++)
{
j=i+m;
w[i][j]=w[i][j-1]+p[j]+q[j];
k=min_value(i,j);
c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
r[i][j]=k;
}
}
}
void build_tree()
{
int i,j,k;
int queue[20],front = -1,rear=-1;
cout<<"\n Optimal Binary Search Tree for given nodes is :- "<<endl;
cout<<"\n Root of this Optimal Binary Search Tree is:-"<<r[0][n]<<endl;
cout<<"\n Cost of this Optimal Binary Search Tree is:-"<<c[0][n]<<endl;
cout<<"\n\n\tNODE\tLEFT CHILD\tRIGHT CHILD"<<endl;
cout<<"\n -------------------------------------------"<<endl;
queue[++rear]=0;
queue[++rear]=n;
while(front!=rear)
{
i=queue[++front];
j=queue[++front];
k=r[i][j];
cout<<"\n\t"<<a[k]<<"\t";
if(r[i][k-1]!=0)
{
cout<<a[r[i][k-1]]<<"\t\t";
queue[++rear]=i;
queue[++rear]=k-1;
}
else
{
cout<<"-\t\t";
}
if(r[k][j]!=0)
{
cout<<a[r[k][j]]<<"\t\t";
queue[++rear]=k;
queue[++rear]=j;
}
else
{
cout<<"-\t";
}
}//while
cout<<"\n";
}
int main()
{
getdata();
OBST();
build_tree();
return 0;
}
/********************************************************************
*OUTPUT
*Optimal Binary Search Tree
Number of nodes:-
4
p is the probablility of success & q is probability that the element is not found
Enter the data:-a[1]:- do
a[2]:- if
a[3]:- int
a[4]:- while
p[1]:- 3
p[2]:- 3
p[3]:- 1
p[4]:- 1
q[0]:- 2
q[1]:- 3
q[2]:- 1
q[3]:- 1
q[4]:- 1
Optimal Binary Search Tree for given nodes is :-
Root of this Optimal Binary Search Tree is:-2
Cost of this Optimal Binary Search Tree is:-32
NODE LEFT CHILD RIGHT CHILD
-------------------------------------------
if do int
do - -
int - while
while - -
*
* ******************************************************************/
------------------------------------------------
Program 11:
------------------------------------------------
#Heap Sortclass HeapSort():
#constructor function
def __init__(self):
#initialized empty list
self.lst=[]
#function to get elements from user
def getElementsFromUser(self):
try:
noElements=int(raw_input('Enter Number of Elements To Sort-->'))
for i in range(noElements):
self.lst.append(int(raw_input('Enter Number-->')))
except:
print 'Enter Integer Value'
#This function maintain heap property
#order=1 (Min Heap)
#order=2 (Max Heap)
def heapify(self,heap,end,order):
if end/2 >0:
if order==1:
while heap[end/2]>heap[end] and end/2 >0:
heap[end],heap[end/2]=heap[end/2],heap[end]
end/=2
if order==2:
while heap[end/2]<heap[end] and end/2 >0:
heap[end],heap[end/2]=heap[end/2],heap[end]
end/=2
#function to sort number as per order (1-Ascending 2-Descending)
#This Function is not directly called by user
def heapSort(self,s,order):
heap=[]
heap.append(0)
for i in s:
heap.append(i)
self.heapify(heap,len(heap)-1,order)
sortList=[]
for i in xrange(1,len(heap)):
sortList.append(heap[1])
heap.pop(1)
for j in xrange(1,len(heap)):
self.heapify(heap,j,order)
return sortList
#function to sort in ascending Order
def sortAscending(self):
self.lst=self.heapSort(self.lst,1)
return self.lst
#function to sort in descending Order
def sortDescending(self):
self.lst=self.heapSort(self.lst,2)
return self.lst
#Syntax to mention program execution starts from below
if __name__ == '__main__':
#created object of Class QuickSort
ms=HeapSort()
#called function to get data from user
ms.getElementsFromUser()
#called function sort in ascending order
print 'Ascending Order Sorted List-->',ms.sortAscending()
#called function sort in descending order
print 'Descending Order Sorted List-->',ms.sortDescending()
'''
##s##v##g##
OUTPUT
##s##v##g##
Enter Number of Elements To Sort-->10
Enter Number-->10
Enter Number-->59
Enter Number-->58
Enter Number-->-99
Enter Number-->-4
Enter Number-->88
Enter Number-->55
Enter Number-->93
Enter Number-->37
Enter Number-->86
Ascending Order Sorted List--> [-99, -4, 10, 37, 55, 58, 59, 86, 88, 93]
Descending Order Sorted List--> [93, 88, 86, 59, 58, 55, 37, 10, -4, -99]
'''
------------------------------------------------
Program 12:
------------------------------------------------
//===============================================================================
//Assingment title: Write a program in C++ to implement hash table and handle the collision using linear probing
and chaining. (with or without replacement) for employee information.Using the above implement direct access file mechanism.
//Assingment Number:01
//Roll no:
//Batch:
//=================================================================================
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<string.h>
using namespace std;
class emp
{
typedef struct EMPLOYEE
{
char name[10];
int empno;
int salary;
int chain;
int loc;
}rec;
rec records;
public:
int size; // hash table size
int chain_table[30][30]; // hash table data structure
emp();
void init();
void insert();
void display();
void search();
void chain_wo_repl();
int hash(int);
};
emp::emp()
{
strcpy(records.name,"");
records.empno=-1;
records.salary=-1;
records.chain=-1;
}
void emp::init()
{
int i,j;
fstream file; //object of fstream
file.open("emp.txt",ios::out); //open the file for writing
cout<<endl<<"Enter the hash table size : ";
cin>>size; //hash table size
for(i=0;i<size;i++)
{
strcpy(records.name,"");
records.empno=-1;
records.salary=-1;
records.chain=-1;
records.loc=i;
file.write((char *)&records,sizeof(records)); //write the initial values
}
for(i=0;i<size;i++) //initialize the hash table
for(j=0;j<size;j++) //entries to null value -1
chain_table[i][j]=-1;
file.close();
}
/*************hashing function**********/
int emp::hash(int num)
{
int key;
key=num%10;
return key;
}
/*************insert function**********/
void emp::insert()
{
int h;
char ans='y';
char new_name[10];
int new_empno,new_salary;
fstream file;
file.open("emp.txt",ios::in|ios::out); //open the file for writing
do
{
cout<<endl<<"enter name of employee :"; // ask for details odf student
cin>>new_name;
cout<<endl<<"enter his/her employee number :";
cin>>new_empno;
cout<<endl<<"enter his/her salary amount :";
cin>>new_salary;
h=hash(new_empno); // obtain hash key by providing empno to hash function
int offset; // use h for getting actual postion in file
offset=h*sizeof(records); // for writing the record at offset
file.seekg(offset); // seeking offset to read
file.read((char *)&records,sizeof(records)); // that position
file.seekp(offset);
if(records.empno==-1)
{
strcpy(records.name,new_name);
records.empno=new_empno;
records.salary=new_salary;
records.chain=-1;
records.loc=h;
file.write((char *)&records,sizeof(records)); //write the new values
//Thus new record has been
//placed at the hashed position.
}
else // Collision has occured
{
int flag=0; // mark collision occured
int prev_chain=records.loc;
do
{
h++; // searching for next empty location
if(h>size+1)
{
cout<<endl<<"Hash table full, can't insert more records";
return;
}
offset=h*sizeof(records);
file.seekg(offset); // seeking offset to read
file.read((char *)&records,sizeof(records)); // that position
file.seekp(offset);
if(records.empno==-1)
{
strcpy(records.name,new_name);
records.empno=new_empno;
records.salary=new_salary;
records.chain=-1;
records.loc=h;
file.write((char *)&records,sizeof(records));
//write the colliding record at a new position for which a
//chain table is maintained to keep track of the colliding records
chain_table[prev_chain][h]=1; // set among when the collision occurs
flag=1; // set flag when collision handled
}
}while(flag==0); // until collision handled
chain_wo_repl();
}
cout<<"Do you want to add more records (y/n) : ";
cin>>ans;
}while(ans=='y');
file.close();
}
/****Chaining without replacement function******/
void emp::chain_wo_repl()
{
int i,j,h,offset;
fstream file;
file.open("emp.txt",ios::in|ios::out); //open the file for reading
for(i=0;i<size;i++)
{
h=i;
for(j=0;j<size;j++)
{
if(chain_table[i][j]==1)
{
offset=h*sizeof(records);
file.seekg(offset); // seeking offset to read
file.read((char *)&records,sizeof(records)); // that position
file.seekp(offset);
records.chain=j; // set the link to
// search for colliding data
file.write((char *)&records,sizeof(records));
h=j; // for double collision
}
}
}
file.close();
}
/*************display function**********/
void emp::display()
{
fstream file;
file.open("emp.txt",ios::in); //open the file for reading
file.seekg(0,ios::beg);
cout<<"The contents of file are"<<endl;
cout<<"Loc. Name. EmpNo. Salary. Chain "<<endl;
cout<<"----------------------------------"<<endl;
while(file.read((char *)&records,sizeof(records)))
{
if(strcmp(records.name,"")!=0)
{
cout<<records.loc<<" "<<records.name<<" "<<records.empno<<" ";
cout<<records.salary<<" "<<records.chain<<endl;
}
}
file.close();
}
/*************search function**********/
void emp::search()
{
int key,offset,h;
int flag=0;
fstream file;
cout<<endl<<"Enter the employee number to be searched : ";
cin>>key;
file.open("emp.txt",ios::in); //open the file for reading
h=hash(key); //to get the position of key
while(file.eof()==0 && h!=-1)
{
offset=h*sizeof(records);
file.seekg(offset,ios::beg);
file.read((char *)&records,sizeof(records));
if(records.empno==key)
{
cout<<endl<<"The record is present in file";
cout<<endl<<"Name : "<<records.name;
cout<<endl<<"Employee No. : "<<records.empno;
cout<<endl<<"Salary : "<<records.salary;
cout<<endl;
flag=1;
return;
}
else
{ // move along the chain
h=records.chain; // for the colliding record
}
}
if(flag==0)
cout<<endl<<"Record not present in file";
file.close();
}
/*************Main function**********/
int main()
{
emp s; // object of class
int choice;
cout<<endl<<"--------------------------------------------------------------";
cout<<endl<<"File operation using hashing and collision handling technique";
cout<<endl<<"Linear Probing and Chaining without Replacement.";
cout<<endl<<"--------------------------------------------------------------";
s.init(); //initialization call only once
do
{
cout<<endl<<"Employee Records";
cout<<endl<<"----------------";
cout<<endl<<" Menu ";
cout<<endl<<"----------------";
cout<<endl<<"1.Insert";
cout<<endl<<"2.Display";
cout<<endl<<"3.Search";
cout<<endl<<"4.Exit";
cout<<endl<<"-----------";
cout<<endl<<"Enter you choice : ";
cin>>choice;
switch(choice)
{
case 1: s.insert();
break;
case 2: s.display();
break;
case 3: s.search();
break;
}
}while(choice<4);
return 0;
}
/********************************************************************
* Output
* -------------------------------------------------------------
File operation using hashing and collision handling technique
Linear Probing and Chaining without Replacement.
--------------------------------------------------------------
Enter the hash table size : 10
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 1
enter name of employee :Mr.Joshi
enter his/her employee number :11
enter his/her salary amount :34000
Do you want to add more records (y/n) : y
enter name of employee :Ms.Patil
enter his/her employee number :34
enter his/her salary amount :45890
Do you want to add more records (y/n) : y
enter name of employee :Mr.Pawar
enter his/her employee number :22
enter his/her salary amount :23006
Do you want to add more records (y/n) : y
enter name of employee :Mr.Dsouza
enter his/her employee number :45
enter his/her salary amount :26799
Do you want to add more records (y/n) : y
enter name of employee :Mrs.Iyer
enter his/her employee number :16
enter his/her salary amount :56000
Do you want to add more records (y/n) : n
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 2
The contents of file are
Loc. Name. EmpNo. Salary. Chain
----------------------------------
1 Mr.Joshi 11 34000 -1
2 Mr.Pawar 22 23006 -1
4 Ms.Patil 34 45890 -1
5 Mr.Dsouza 45 26799 -1
6 Mrs.Iyer 16 56000 -1
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 1
enter name of employee :Mr.Ghosh
enter his/her employee number :32
enter his/her salary amount :36777
Do you want to add more records (y/n) : n
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 2
The contents of file are
Loc. Name. EmpNo. Salary. Chain
----------------------------------
1 Mr.Joshi 11 34000 -1
2 Mr.Pawar 22 23006 3
3 Mr.Ghosh 32 36777 -1
4 Ms.Patil 34 45890 -1
5 Mr.Dsouza 45 26799 -1
6 Mrs.Iyer 16 56000 -1
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 1
enter name of employee :Mr.Deshpande
enter his/her employee number :43
enter his/her salary amount :56432
Do you want to add more records (y/n) : n
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 2
The contents of file are
Loc. Name. EmpNo. Salary. Chain
----------------------------------
1 Mr.Joshi 11 34000 -1
2 Mr.Pawar 22 23006 3
3 Mr.Ghosh 32 36777 7
4 Ms.Patil 34 45890 -1
5 Mr.Dsouza 45 26799 -1
6 Mrs.Iyer 16 56000 -1
7 Mr.Deshpande 43 56432 -1
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 3
Enter the employee number to be searched : 45
The record is present in file
Name : Mr.Dsouza
Employee No. : 45
Salary : 26799
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 3
Enter the employee number to be searched : 98
Record not present in file
Employee Records
----------------
Menu
----------------
1.Insert
2.Display
3.Search
4.Exit
-----------
Enter you choice : 4
*
* ********************************************************************/
------------------------------------------------
Program 13:
------------------------------------------------
#include<iostream>#include<string.h>
using namespace std;
struct node
{
int data;
node *next;
node *prev;
};
void addnode();
void delnode();
void display();
void search();
node *end=NULL,*start=NULL, *temp1, *temp2, *temp3;
int main()
{
char ch;
do
{
char i;
cout<<"Press 'a' to add node \n 'd' to delete"<<endl;
cout<<"'v' for display "<<endl;
cout<<"'s' for search"<<endl;
cin>>i;
switch (i)
{
case'a':
addnode();
break;
case'd':
delnode();
break;
case'v' :
display();
break;
case 's':
search();
break;
default:
cout<<"Bad input"<<endl;
break;
}
cout<<"want to process more y/n"<<endl;
cin>>ch;
}
while(ch!='n');
return 0;
}
void addnode() //adding node
{
char r;
temp1=new node;
cout<<"enter number to be stored"<<endl;
cin>>temp1->data;
if(start!=NULL)
{
cout<<"press 's' to add in start,'m' for midd , 'e' for end"<<endl;
cin>>r;
}
else r='s';
switch (r)
{
case's': //add start
if(start==NULL)
{
start=temp1;
temp1->next=NULL;
temp1->prev=NULL;
end=start;
}
else
{
temp2=start;
temp1->next=temp2;
temp2->prev=temp1;
temp1->prev=end;
end->next=temp1;
start=temp1;
}
break;
case'e': //add end
if(start==NULL)
{
start=temp1;
temp1->next=NULL;
temp1->prev=NULL;
end=start;
}
else
{
temp2=end;
temp2->next=temp1;
temp1->prev=temp2;
temp1->next=start;
start->prev=temp1;
end=temp1;
}
break;
case'm': //add mid
int num;
cout<<"enter node after which you want to enter"<<endl;
cin>>num;
temp2=start;
for(int i=0;i<num;i++)
{
if(start==NULL)
cout<<"given node not found"<<endl;
else
{
temp3=temp2;
temp2=temp2->next;
}
}
temp1->next=temp2;
temp3->next=temp1;
temp1->prev=temp3;
temp2->prev=temp1;
break;
}
}
void display() //displaying
{
temp3=start;
if(start==NULL)
cout<<"no node to display"<<endl;
else
{
while(temp3!=end)
{
cout<<"\nData is: "<<temp3->data<<endl;
temp3=temp3->next;
}
cout<<"\nData is: "<<temp3->data<<endl;
}
}
void search() //search
{
int p;
int flag=0;
int count=0;
cout<<"enter number to be searched:"<<endl;
cin>>p;
temp1=start;
while(temp1!=end)
{ count++;
if(temp1->data==p)
{
flag=1;
cout<<"Number found & its position is: "<<count<<endl;
}
temp1=temp1->next;
}
if(flag==0) //last node comparision
{ count++;
if(temp1->data==p)
{
flag=1;
cout<<"Number found & its position is: "<<count<<endl;
}
}
if(flag==0)
{
cout<<"Number not found "<<endl;
}
}
void delnode() //deleting
{
int p;
int flag=0;
cout<<"enter Number to be deleted:"<<endl;
cin>>p;
temp1=start;
if(start!=NULL)
{
if(temp1==end && temp1->data==p)
{
delete temp1; // only one node exists
flag=1;
start=NULL;
cout<<"Node deleted";
}
else
{
while(temp1!=end)
{
if(temp1->data==p)
{
if(temp1==start) // first node
{
start=start->next;
start->prev=end;
end->next=start;
delete temp1;
}
else //mid node
{
temp1->prev->next=temp1->next;
temp1->next->prev=temp1->prev;
delete temp1;
}
flag=1;
cout<<"Node deleted";
break;
}
temp1=temp1->next;
}//while
if(temp1==end && end->data==p) //last node
{
end = temp1->prev;
end->next = start;
start->prev = end;
delete temp1;
flag=1;
cout<<"Node deleted";
}
}//end else
}
if(flag==0)
{
cout<<"Number not found";
}
}
------------------------------------------------
Program 14:
------------------------------------------------
#Merge Sort
class MergeSort():
#constructor function
def __init__(self):
#initialized empty list
self.lst=[]
#function to get elements from user
def getElementsFromUser(self):
try:
noElements=int(raw_input('Enter Number of Elements To Sort-->'))
for i in range(noElements):
self.lst.append(int(raw_input('Enter Number-->')))
except:
print 'Enter Integer Value'
#function to sort number as per order (1-Ascending 2-Descending)
#This Function is not directly called by user
def mergeSort(self,s,order):
if s:
mid=int(len(s)/2)
left,right=s[:mid],s[mid:]
if len(left)>1:
left=self.mergeSort(left,order)
if len(right)>1:
right=self.mergeSort(right,order)
emptyList=[]
if left and right:
while left and right:
if order==1:
if left[0]<right[0]:
emptyList.append(left.pop(0))
else:
emptyList.append(right.pop(0))
if order==2:
if left[0]>right[0]:
emptyList.append(left.pop(0))
else:
emptyList.append(right.pop(0))
emptyList=emptyList+left
emptyList=emptyList+right
return emptyList
return None
#function to sort in ascending Order
def sortAscending(self):
self.lst=self.mergeSort(self.lst,1)
return self.lst
#function to sort in descending Order
def sortDescending(self):
self.lst=self.mergeSort(self.lst,2)
return self.lst
#Syntax to mention program execution starts from below
if __name__ == '__main__':
#created object of Class QuickSort
ms=MergeSort()
#called function to get data from user
ms.getElementsFromUser()
#called function sort in ascending order
print 'Ascending Order Sorted List-->',ms.sortAscending()
#called function sort in descending order
print 'Descending Order Sorted List-->',ms.sortDescending()
'''
##s##v##g##
OUTPUT
##s##v##g##
Enter Number of Elements To Sort-->10
Enter Number-->10
Enter Number-->59
Enter Number-->58
Enter Number-->-99
Enter Number-->-4
Enter Number-->88
Enter Number-->55
Enter Number-->93
Enter Number-->37
Enter Number-->86
Ascending Order Sorted List--> [-99, -4, 10, 37, 55, 58, 59, 86, 88, 93]
Descending Order Sorted List--> [93, 88, 86, 59, 58, 55, 37, 10, -4, -99]
'''
------------------------------------------------
Program 15:
------------------------------------------------
class QuickSort():
#constructor function
def __init__(self):
#initialized empty list
self.lst=[]
#function to get elements from user
def getElementsFromUser(self):
try:
noElements=int(raw_input('Enter Number of Elements To Sort-->'))
for i in range(noElements):
self.lst.append(int(raw_input('Enter Number-->')))
except:
print 'Enter Integer Value'
#function to sort number as per order (1-Ascending 2-Descending)
#This Function is not directly called by user
def quickSort(self,s,order):
if len(s)>1:
lessThanPivotElems,greaterThanPivotElems=[],[]
pivot=s[0]
for i in s:
if i<pivot:
lessThanPivotElems.append(i)
if i>pivot:
greaterThanPivotElems.append(i)
if len(lessThanPivotElems)>1:
lessThanPivotElems=self.quickSort(lessThanPivotElems,order)
if len(greaterThanPivotElems)>1:
greaterThanPivotElems=self.quickSort(greaterThanPivotElems,order)
if order==1:
return lessThanPivotElems+[pivot]+greaterThanPivotElems
elif order==2:
return greaterThanPivotElems+[pivot]+lessThanPivotElems
return None
#function to sort in ascending Order
def sortAscending(self):
self.lst=self.quickSort(self.lst,1)
return self.lst
#function to sort in descending Order
def sortDescending(self):
self.lst=self.quickSort(self.lst,2)
return self.lst
#Syntax to mention program execution starts from below
if __name__ == '__main__':
#created object of Class QuickSort
qs=QuickSort()
#called function to get data from user
qs.getElementsFromUser()
#called function sort in ascending order
print 'Ascending Order Sorted List-->',qs.sortAscending()
#called function sort in descending order
print 'Descending Order Sorted List-->',qs.sortDescending()
'''
##s##v##g##
OUTPUT
##s##v##g##
Enter Number of Elements To Sort-->8
Enter Number-->5
Enter Number-->89
Enter Number-->55
Enter Number-->-66
Enter Number-->57
Enter Number-->-558
Enter Number-->54
Enter Number-->998
Ascending Order Sorted List--> [-558, -66, 5, 54, 55, 57, 89, 998]
Descending Order Sorted List--> [998, 89, 57, 55, 54, 5, -66, -558]
'''
------------------------------------------------
Program 16:
------------------------------------------------
#include<stdlib.h>
#include<iostream>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
char data;
struct node* left;
struct node* right;
};
/* Prototypes for utility functions */
int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);
/* Recursive function to construct binary of size len from
Inorder traversal in[] and Preorder traversal pre[]. Initial values
of inStrt and inEnd should be 0 and len -1. The function doesn't
do any error checking for cases where inorder and preorder
do not form a tree */
struct node* buildTreeFromInPre(char in[], char pre[], int inStrt, int inEnd)
{
static int preIndex = 0;
if(inStrt > inEnd)
return NULL;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
struct node *tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if(inStrt == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode->data);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode->left = buildTreeFromInPre(in, pre, inStrt, inIndex-1);
tNode->right = buildTreeFromInPre(in, pre, inIndex+1, inEnd);
return tNode;
}
struct node* buildTreeFromInPost(char in[], char post[], int inStrt, int inEnd,int len1)
{
static int postIndex = len1-1;
if(inStrt > inEnd)
return NULL;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
struct node *tNode = newNode(post[postIndex--]);
/* If this node has no children then return */
if(inStrt == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode->data);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode->right = buildTreeFromInPost(in, post, inIndex+1, inEnd,len1-1);
tNode->left = buildTreeFromInPost(in, post, inStrt, inIndex-1,len1-1);
return tNode;
}
1. Create Binary Tree from Inorder and PreOrder traversals
2. Create Binary Tree from Inorder and PostOrder traversals
Enter your choice:-1
Postorder traversal of the constructed tree is
83176825
1. Create Binary Tree from Inorder and PreOrder traversals
2. Create Binary Tree from Inorder and PostOrder traversals
Enter your choice:-2
Preorder traversal of the constructed tree is
57183268
1. Create Binary Tree from Inorder and PreOrder traversals
2. Create Binary Tree from Inorder and PostOrder traversals
Enter your choice:-
/* UTILITY FUNCTIONS */
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
int search(char arr[], int strt, int end, char value)
{
int i;
for(i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(char data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* This funtcion is here just to test buildTree() */
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout<< node->data;
/* now recur on right child */
printInorder(node->right);
}
/* This funtcion is here just to test buildTree() */
void printPreorder(struct node* node)
{
if (node == NULL)
return;
/* then print the data of node */
cout<< node->data;
/* first recur on left child */
printPreorder(node->left);
/* now recur on right child */
printPreorder(node->right);
}
/* This funtcion is here just to test buildTree() */
void printPostorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printPostorder(node->left);
/* now recur on right child */
printPostorder(node->right);
/* then print the data of node */
cout<< node->data;
}
/* Driver program to test above functions */
int main()
{
int ch;
struct node *root;
/*char in[] = {'D', 'B', 'E', 'A', 'F', 'C'};
char post[]={'D','E','B','F','C','A'};
char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'};*/
char pre[]={'5','7','1','8','3','2','6','8'};
char in[]={ '7','8','1','3','5','6','2','8'};
char post[]={'8','3','1','7','6','8','2','5'};
int len = sizeof(in)/sizeof(in[0]);
int len1 = sizeof(post);
do
{
cout<<"\n1. Create Binary Tree from Inorder and PreOrder traversals";
cout<<"\n2. Create Binary Tree from Inorder and PostOrder traversals";
cout<<"\nEnter your choice:-";
cin>>ch;
switch(ch)
{
case 1:
root = buildTreeFromInPre(in, pre, 0, len - 1);
/* Let us test the built tree by printing Inorder traversal */
cout<<"\n Postorder traversal of the constructed tree is \n";
printPostorder(root);
break;
case 2:
root = buildTreeFromInPost(in, post, 0, len - 1,len1);
/* Let us test the built tree by printing Preorder traversal */
cout<<"\n Preorder traversal of the constructed tree is \n";
printPreorder(root);
break;
}
}while(ch<3);
}
**********************************************************************
OUTPUT:
1. Create Binary Tree from Inorder and PreOrder traversals
2. Create Binary Tree from Inorder and PostOrder traversals
Enter your choice:-1
Postorder traversal of the constructed tree is
83176825
1. Create Binary Tree from Inorder and PreOrder traversals
2. Create Binary Tree from Inorder and PostOrder traversals
Enter your choice:-2
Preorder traversal of the constructed tree is
57183268
1. Create Binary Tree from Inorder and PreOrder traversals
2. Create Binary Tree from Inorder and PostOrder traversals
Enter your choice:-
------------------------------------------------
Program 17:
------------------------------------------------
print "Python Program to sort the numbers using Bubble Sort"
arrNumbers = []
i = 0
j = 0
n = 0
a = 0
sum = 0
temp = 0
print "Total Numbers:",
n = input()
for i in range (0, n):
print "Enter", i + 1, "Number: ",
a = input()
arrNumbers.append(a)
for i in range (1, n):
for j in range (0, n - i):
if( arrNumbers[j] > arrNumbers[j + 1]):
temp = arrNumbers[j]
arrNumbers[j] = arrNumbers[j + 1]
arrNumbers[j + 1] = temp
print "After iteration: ", iPython Program to sort the numbers using Bubble Sort
Total Numbers: 7
Enter 1 Number: 23
Enter 2 Number: 1
Enter 3 Number: 8
Enter 4 Number: 44
Enter 5 Number: 19
Enter 6 Number: 54
Enter 7 Number: 4
After iteration: 1
1 8 23 19 44 4 54 /*** 2 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 2
1 8 19 23 4 44 54 /*** 3 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 3
1 8 19 4 23 44 54 /*** 4 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 4
1 8 4 19 23 44 54 /*** 5 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 5
1 4 8 19 23 44 54 /*** 6 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 6
1 4 8 19 23 44 54 /*** 7 biggest number(s) is(are) pushed to the end of the array***/
The sorted array is: 1 4 8 19 23 44 54
for k in range (0, n):
print arrNumbers[k],
print "/*** ", i + 1, "biggest number(s) is(are) pushed to the end of the array***/"
print "The sorted array is: ",
for i in range (0, n):
print arrNumbers[i],
**********************************************************************
OUTPUT:
Python Program to sort the numbers using Bubble Sort
Total Numbers: 7
Enter 1 Number: 23
Enter 2 Number: 1
Enter 3 Number: 8
Enter 4 Number: 44
Enter 5 Number: 19
Enter 6 Number: 54
Enter 7 Number: 4
After iteration: 1
1 8 23 19 44 4 54 /*** 2 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 2
1 8 19 23 4 44 54 /*** 3 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 3
1 8 19 4 23 44 54 /*** 4 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 4
1 8 4 19 23 44 54 /*** 5 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 5
1 4 8 19 23 44 54 /*** 6 biggest number(s) is(are) pushed to the end of the array***/
After iteration: 6
1 4 8 19 23 44 54 /*** 7 biggest number(s) is(are) pushed to the end of the array***/
The sorted array is: 1 4 8 19 23 44 54
No comments:
Post a Comment