· 7 years ago · Oct 27, 2018, 03:00 AM
1/*Batch:S4
2Problem Statement:
3 Begining with an empty binary search tree,construct binary search tree by inserting the values in the order given After constructing binary tree:
4 1)Insert new node.
5 2)Find no.of nodes in longest path.
6 3) Minimum data values found in tree.
7 4)Change a tree so the roles of the left and right pointer
8 5) Search a value
9
10*/
11#include <iostream>
12#include <stdlib.h>
13using namespace std;
14struct tree
15{
16 tree *left, *right;
17 int data;
18}*T=NULL;
19
20class bst
21{
22 tree *root;
23 public:
24 bst();
25 void create();
26 int height(tree *);
27 tree *swap(tree *);
28 void inorder(tree *);
29 void preorder(tree *);
30 void postorder(tree *);
31 tree *findmin(tree *);
32 void findmax(tree *);
33 void search(tree *,int);
34 tree *del(tree *,int);
35 tree *getroot()
36 {
37 return root;
38 }
39};
40
41bst::bst()
42{
43 root=NULL;
44}
45
46void bst::create()
47{
48 int num,n;
49 cout<<"Enter total no of elements:- ";
50 cin>>n;
51 for(int i=0;i<n;i++)
52 {
53 if (root == NULL)
54 {
55 root = new tree;
56 cout<<"enter value of root node\n";
57 cin>>root->data;
58 root->right=NULL;
59 root->left=NULL;
60 }
61 else
62 {
63 T = root;
64 cout<<"enter value of node\n";
65 cin>>num;
66 while(true)
67 {
68 if (num < T->data)
69 {
70 if (T->left == NULL)
71 {
72 T->left = new tree;
73 T = T->left;
74 T->data = num;
75 cout<<"node entered in left\n";
76 break;
77 }
78 else if (T->left != NULL)
79 {
80 T = T->left;
81 }
82 }
83 else if (num > T->data)
84 {
85 if (T->right == NULL)
86 {
87 T->right = new tree;
88 T = T->right;
89 T->data = num;
90 cout<<"node entered in right\n";
91 break;
92 }
93 else if (T->right != NULL)
94 {
95 T = T->right;
96 }
97 }
98 }
99 }
100 }
101}
102
103void bst::inorder(tree *T)
104{
105 if (T != NULL)
106 {
107 inorder(T->left);
108 cout<<T->data<<" ";
109 inorder(T->right);
110 }
111}
112
113void bst::preorder(tree *T)
114{
115 if (T != NULL)
116 {
117 cout<<T->data<<" ";
118 inorder(T->left);
119 inorder(T->right);
120 }
121}
122
123void bst::postorder(tree *T)
124{
125 if (T != NULL)
126 {
127 inorder(T->left);
128 inorder(T->right);
129 cout<<T->data<<" ";
130 }
131}
132
133tree *bst::findmin(tree *T)
134{
135 while(T->left!=NULL)
136 T=T->left;
137 cout<<"Smallest value in BST:- "<<T->data;
138}
139
140void bst::findmax(tree *T)
141{
142 while(T->right!=NULL)
143 T=T->right;
144 cout<<"Largest value in BST:- "<<T->data;
145}
146
147void bst::search(tree *T,int key)
148{
149 if(T->data==key)
150 cout<<"Key found and its root node";
151 else if(key>T->data)
152 {
153 T=T->right;
154 cout<<"Key found at right side of root node";
155 }
156 else
157 {
158 T=T->left;
159 cout<<"Key found at left side of root node";
160 }
161}
162
163int bst::height(tree *T)
164{
165 if(T==NULL)
166 return 0;
167 if(T->left==NULL && T->right==NULL)
168 return 0;
169 return(max(height(T->left),height(T->right))+1);
170}
171
172tree * bst::swap(tree *T)
173{
174 tree *temp;
175 if(T!=NULL)
176 {
177 temp=T->left;
178 T->left=swap(T->right);
179 T->right=swap(temp);
180 }
181 return(T);
182}
183
184
185tree * bst::del(tree *T,int key)
186{
187 tree *temp;
188 if(T==NULL)
189 {
190 cout<<"Element not found";
191 return T;
192 }
193 if(key<T->data) //delete in left subtree
194 {
195 T->left=del(T->left,key);
196 return T;
197 }
198 if(key>T->data) //delete in right subtree
199 {
200 T->right=del(T->right,key);
201 return T;
202 }
203 //element is found
204 if(T->left==NULL && T->right==NULL) //a leaf node
205 {
206 temp=T;
207 free(temp);
208 return(NULL);
209 }
210 if(T->left==NULL)
211 {
212 temp=T;
213 T=T->right;
214 delete temp;
215 return T;
216 }
217 if(T->right==NULL)
218 {
219 temp=T;
220 T=T->left;
221 delete temp;
222 return T;
223 }
224 //node with two children
225 temp=findmin(T->right);
226 T->data=temp->data;
227 T->right=del(T->right,temp->data);
228 return T;
229}
230
231
232int main()
233{
234 bst t;
235 int ch,n,k;
236 while(1)
237 {
238 cout << "\nOperations on Binary Tree\n";
239 cout << "1. Create Binary Tree\n";
240 cout << "2. Inorder\n";
241 cout << "3. Preorder\n";
242 cout << "4. Postorder\n";
243 cout << "5. Find Minimum Value\n";
244 cout << "6. Find Maximum Value\n";
245 cout << "7. Search a node\n";
246 cout << "8. Height\n";
247 cout << "9. Swap\n";
248 cout <<"10. Delete\n";
249 cout << "11. Exit\n";
250 cout << "Enter your choice :- ";
251 cin >> ch;
252 switch (ch)
253 {
254 case 1:
255 t.create();
256 break;
257 case 2:
258 t.inorder(t.getroot());
259 break;
260 case 3:
261 t.preorder(t.getroot());
262 break;
263 case 4:
264 t.postorder(t.getroot());
265 break;
266 case 5:
267 t.findmin(t.getroot());
268 break;
269 case 6:
270 t.findmax(t.getroot());
271 break;
272 case 7:
273 cout<<"Enter the key to search";
274 cin>>n;
275 t.search(t.getroot(),n);
276 break;
277 case 8:
278 cout<<"\nHeight:- "<<t.height(t.getroot());
279 break;
280 case 9:
281 t.swap(t.getroot());
282 break;
283 case 10:
284 cout<<"Enter key to delete";
285 cin>>k;
286 t.del(t.getroot(),k);
287 break;
288 case 11:
289 exit(0);
290
291 default:
292 cout << "Wrong choice,Try again.";
293 }
294 }
295 return 0;
296}
297
298
299
300/*Batch:S4
301
302Problem statement:
303 Construct the Threaded binary tree and perform Inorder Traversal on it.
304/*Program Name: Inorder and Preorder Traversal of Threaded Binary Tree*/
305/* 50
306 - -
307 - -
308 30 60
309 - - - -
310 - - - -
311 15 40 55 70
312
313 for above tree inorder traversal:- 15 30 35 50 60 70 80
314 for above tree pre order traversa:- 50 30 15 35 70 60 80
315 Note:- see the below implementation with comments consideing above example*/
316
317
318#include<iostream>
319//#include<process.h>
320using namespace std;
321class TBT
322{
323 private:
324 int data;
325 int lbit,rbit;
326 TBT*lchild,*rchild;
327 public:
328 TBT*create_TBT(TBT*,TBT*);
329 void inorder_TBT(TBT*,TBT*);
330 void preorder_TBT(TBT*,TBT*);
331};
332
333
334void TBT::preorder_TBT(TBT*root,TBT*header)
335{
336 TBT*trav;
337 int flag=0;
338 trav=root;
339 while(trav!=header)
340 {
341 while(trav->lbit==0&&flag==0) //step 1) if normal child
342 {
343 cout<<" "<<trav->data; // print 50 and then 30
344 trav=trav->lchild; // go to left child
345 }
346 if(flag==0) // step 2) if normal child but lbit=1 i.e last child
347 cout<<" "<<trav->data; // print 15 and then 40, 55 , 70
348
349 if(trav->rbit==0&&flag==0)
350 {
351 trav=trav->rchild;
352 }
353 else
354 {
355 if(trav->rbit==0&&flag==1)// step no 4 go to 40
356 {
357 trav=trav->rchild;
358 flag=0; // mark 40 as not visited
359 }
360 else
361 {
362 if(trav->rbit==1&&flag==0)//step 3) if rt child is thread climb up
363 {
364 trav=trav->rchild; //from 15 go to 30 again
365 flag=1; // make 30 as visited or printed
366 }
367 else
368 {
369 if(trav->rbit==1&&flag==1)
370 {
371 trav=trav->rchild;
372
373 }
374 }
375 }
376 }
377 }
378
379}
380void TBT::inorder_TBT(TBT*root,TBT*header)
381{
382 int flag=0;
383 TBT*trav;
384 trav=root;
385
386 while(trav!=header)
387 {
388 while(trav->lbit!=1&&flag==0)
389 {
390 trav=trav->lchild; // go to left
391 }
392
393 cout<<" "<<trav->data; // ptint leftmost data
394
395 if(trav->rbit==0)
396 {
397 trav=trav->rchild;
398 flag=0;
399 }
400 else
401 {
402 trav=trav->rchild;
403 flag=1;
404 }
405 }
406}
407
408TBT*TBT::create_TBT(TBT*root,TBT*header)
409{
410 TBT*trav,*temp,*p;
411 int attached_flag=0;
412 char ans;
413
414 while(1)
415 {
416 trav=root;
417
418 if(root==NULL)
419 {
420 temp=new TBT();
421 cout<<"\nEnter the data ";
422 cin>>temp->data;
423 temp->lbit=1;
424 temp->rbit=1;
425 temp->lchild=header;
426 temp->rchild=header;
427 root=temp;
428 }
429 else
430 {
431 temp=new TBT();
432 cout<<"\nEnter the data ";
433 cin>>temp->data;
434 temp->lbit=1;
435 temp->rbit=1;
436 attached_flag=0;
437
438 trav=root;
439 while(attached_flag==0)
440 {
441 if(trav->data<temp->data&&trav->rbit==0)
442 {
443 trav=trav->rchild;
444 }
445 else
446 if(trav->data<temp->data&&trav->rbit==1)
447 {
448 trav->rbit=0;
449 p=trav->rchild;
450 trav->rchild=temp;
451 temp->rchild=p;
452 temp->lchild=trav;
453 attached_flag=1;
454 }
455
456 if(trav->data>temp->data&&trav->lbit==0)
457 {
458 trav=trav->lchild;
459 }
460 else
461 if(trav->data>temp->data&&trav->lbit==1)
462 {
463 trav->lbit=0;
464 p=trav->lchild;
465 trav->lchild=temp;
466 temp->lchild=p;
467 temp->rchild=trav;
468 attached_flag=1;
469 }
470 }
471
472 attached_flag=0;
473 }
474 cout<<"\nDo you want to attach more nodes [y/n] ";
475 cin>>ans;
476 if(ans=='n'||ans=='N')
477 break;
478 }
479 return root;
480}
481int main()
482{
483 int choice;
484 TBT*root=NULL,obj,*header=NULL;
485
486
487 while(1)
488 {
489 cout<<"\n1.Create TBT";
490 cout<<"\n2.Inorder TBT";
491 cout<<"\n3.Preorder TBT";
492 cout<<"\n4.Exit";
493 cout<<"\nEnter your choice :";
494 cin>>choice;
495 switch(choice)
496 {
497 case 1: root=obj.create_TBT(root,header);
498 break;
499 case 2: obj.inorder_TBT(root,header);
500 break;
501 case 3: obj.preorder_TBT(root,header);
502 break;
503 //case 4:
504 // exit(0);
505 }
506 }
507 return 0;
508}
509
510/*
511
512 Batch:S4
513 Problem Statement::
514 Write a function to get the number of vertices in an undirected graph and
515 its edges. You may assume that no edge is input twice. i. Use adjacency
516 list representation of the graph and find runtime of the function ii. Use
517 adjacency matrix representation of the graph and find runtime of the
518 function
519*/
520
521#include<iostream>
522using namespace std;
523class graph
524{
525 int g[20][20],vertices,i,j;
526 char edge;
527 public:
528 void accept();
529 void Adj_matrix();
530 void Adj_list();
531};
532
533void graph::accept()
534{
535 cout<<"\nEnter number of vertices: ";
536 cin>>vertices;
537 for(i=0;i<vertices;i++)
538 {
539 for(j=0;j<vertices;j++)
540 {
541 g[i][j]=0;
542 }
543 }
544 for(i=0;i<vertices;i++)
545 {
546 for(j=0;j<vertices;j++)
547 {
548 if(g[i][j]==0 || g[j][i]==0)
549 {
550 cout<<"\nEnter y if edge exists between "<<i<<" & "<<j;
551 cin>>edge;
552 if(edge=='y')
553 {
554 g[i][j]=1;
555 g[j][i]=1;
556 }
557 else
558 {
559 g[i][j]=0;
560 g[j][i]=0;
561 }
562 }
563 }
564 }
565}
566void graph::Adj_matrix()
567{
568 cout<<"\nAdjacency Matrix:\n";
569 for(i=0;i<vertices;i++)
570 {
571 for(j=0;j<vertices;j++)
572 {
573 cout<<g[i][j]<<"\t";
574 }
575 cout<<endl;
576 }
577}
578
579void graph::Adj_list()
580{
581 cout<<"\nAdjacency list:\n";
582 for(i=0;i<vertices;i++)
583 {
584 cout<<i<<"->>";
585 for(j=0;j<vertices;j++)
586 {
587 if(g[i][j]==1)
588 {
589 cout<<j<<"->>";
590 }
591 }
592 cout<<"NULL"<<endl;
593 }
594
595}
596
597int main()
598{
599 graph g;
600 g.accept();
601 g.Adj_matrix();
602 g.Adj_list();
603 return 0;
604}
605/*
606
607/*
608 Batch:S4
609 Problem Statement::
610 There are flight paths between cities. If there is a flight between city
611 A and city B
612 then there is an edge between the cities. The cost of the edge can be the
613 time that
614 flight takes to reach city B from A, or the amount of fuel used for the
615 journey.
616 Represent this as a graph. The node can be represented by airport name or
617 name of the city.
618*/
619
620#include<iostream>
621using namespace std;
622class flight
623{
624 string citiname[50];
625 int cities,i,j,arr[20][20];
626 char path[20][20];
627 public:
628 void accept();
629 void Adj_matrix();
630 void Adj_list();
631};
632
633void flight::accept()
634{
635 cout<<"\nEnter number of cities: ";
636 cin>>cities;
637 for(i=0;i<cities;i++)
638 {
639 for(j=0;j<cities;j++)
640 {
641 arr[i][j]=0;
642 }
643 }
644
645 for(i=0;i<cities;i++)
646 {
647 cout<<"Enter the citiname:";
648 cin>>citiname[i];
649 }
650 for(i=0;i<cities;i++)
651 {
652 for(j=0;j<cities;j++)
653 {
654 if(i!=j)
655 {
656 cout<<"\nEnter y if edge exists between "<<citiname[i]<<" & "<<citiname[j]<<"\t";
657 cin>>path[i][j];
658 if(path[i][j]=='y')
659 {
660 cout<<"Enter amount of fuel:";
661 cin>>arr[i][j];
662 }
663 else
664 arr[i][j]=0;
665 }
666 }
667 }
668}
669void flight::Adj_matrix()
670{
671 cout<<"\nAdjacency Matrix:\n";
672 for(i=0;i<cities;i++)
673 {
674 for(j=0;j<cities;j++)
675 {
676 cout<<arr[i][j]<<"\t";
677 }
678 cout<<endl;
679 }
680}
681
682void flight::Adj_list()
683{
684 cout<<"\nAdjacency list:\n";
685 for(i=0;i<cities;i++)
686 {
687 cout<<citiname[i]<<"->>";
688 for(j=0;j<cities;j++)
689 {
690 if(path[i][j]=='y')
691 {
692 cout<<citiname[j]<<"->>";
693 }
694 }
695 cout<<"NULL"<<endl;
696 }
697}
698
699int main()
700{
701 flight g;
702 g.accept();
703 g.Adj_matrix();
704 g.Adj_list();
705 return 0;
706}
707/*
708/*
709 Batch::S4
710 Problem Statement:
711 Consider telephone book database of N clients. Make use of a hash table
712 implementation to quickly look up client‘s telephone number.
713
714*/
715#include<iostream>
716#include<stdlib.h>
717using namespace std;
718class Hashing
719{
720int size,i,total_ele,index,new_index;
721long tele,hashtable[50],search_key;
722public:
723void accept();
724int hash(long key)
725{
726return (key % size);
727}
728void display();
729int linear_prob(long,int);
730void search();
731void del();
732};
733void Hashing::accept()
734{
735cout<<"\nEnter size of Hash Table:";
736cin>>size;
737for(i=0;i<size;i++)
738{
739hashtable[i]=0;
740}
741cout<<"\nEnter the total number of elements:";
742cin>>total_ele;
743i=0;
744while(i!=total_ele)
745{
746cout<<"\nEnter the telephone number:";
747cin>>tele;
748index = hash(tele);
749if(hashtable[index]==0)
750{
751hashtable[index]=tele;
752}
753else
754{
755linear_prob(tele,index);
756}
757i++;
758}
759}int Hashing::linear_prob(long key,int pos){
760int j;
761for(j=0;j<size;j++){
762new_index= (pos + j)% size;
763if(hashtable[new_index]==0)
764{
765hashtable[new_index]=key;
766break;
767}
768}
769}
770void Hashing::display()
771{
772cout<<"\nTelephone numbers in hash table:\n";
773for(i=0;i<size;i++)
774{
775cout<<i<<"\t";
776cout<<hashtable[i]<<endl;
777}
778}
779void Hashing::search()
780{
781int flag=0;
782cout<<"\nEnter number to search:";
783cin>>search_key;
784for(i=0;i<size;i++)
785{
786if(hashtable[i]==search_key)
787{
788cout<<"\nTelephone number is found at position "<<i<<endl;
789flag=1;
790break;
791}
792else
793continue;
794}
795if(flag==0)
796cout<<"\n Search key not found"<<endl;
797}
798void Hashing::del()
799{
800int flag=0,key;
801cout<<"Enter the number to delete:- ";
802cin>>key;
803for(int i=0;i<size;i++)
804{
805if(hashtable[i]==key)
806{
807cout<<"The telephone no."<<hashtable[i]<<" is deleted";
808hashtable[i]=0;
809flag=1;}
810elsecontinue;
811}
812if(flag==0)
813cout<<"\nGiven key not found"<<endl;
814}
815int main(){
816int ch;
817Hashing h;
818while(1)
819{
820cout<<"\nHashing Operations"<<endl;
821cout<<"1.Insert Telephone Numbers"<<endl;
822cout<<"2.Display Telephone Numbers"<<endl;
823cout<<"3.Search Telephone Numbers"<<endl;
824cout<<"4.Delete Telephone Number"<<endl;
825cout<<"5.Exit"<<endl;
826cout<<"Enter your choice:- ";
827cin>>ch;
828switch(ch)
829{
830case 1:
831h.accept();
832break;
833case 2:
834h.display();
835break;
836case 3:
837h.search();
838break;
839case 4:
840h.del();
841break;
842case 5:
843exit(0);
844default:
845cout<<"Wrong Choice,Try Again";
846}
847}
848return 0;
849}
850 Batch: S4
851Problem Statement:Implementation all the function of a dictionary usinh hashing
852 Data set of(Keys,value)pairs,keys are mapped to values,keys must
853 be compatiable keys must be unique.
854 Standardoperations: 1)Insert(key,value)
855 2)Search(key)
856 3)Delete(key)
857*/
858
859
860
861#include<iostream>
862#include<string.h>
863#define size 10
864using namespace std;
865class Dict
866{
867 public:
868 int n,key;
869 string tempkey[20],tempmean[20],hashkey[20],hashmean[20];
870 Dict()
871 {
872 for(int i=0;i<20;i++)
873 {
874 hashkey[i]="NULL";
875 hashmean[i]="NULL";
876 }
877 }
878 void create();
879 void linear_prob();
880 void display();
881 void search();
882 void delete_mean();
883};
884
885
886void Dict::create()
887{
888 cout<<"Enter the no of entries in dictionary:";
889 cin>>n;
890 for(int i=0;i<n;i++)
891 {
892 cout<<"Enter the keyword:";
893 cin>>tempkey[i];
894 cout<<"\nEnter the meaning:";
895 cin>>tempmean[i];
896 key=int(tempkey[i][0])%size;
897 if(hashkey[key]=="NULL")
898 {
899 hashkey[key]=tempkey[i];
900 hashmean[key]=tempmean[i];
901 }
902 else
903 {
904 while(hashkey[key]!="NULL")
905 {
906 key=int(tempkey[i][0]+i)%size;
907 }
908 hashkey[key]=tempkey[i];
909 hashmean[key]=tempmean[i];
910 }
911 }
912}
913
914void Dict::display()
915{
916 for(int i=0;i<size;i++)
917 {
918 if(hashkey[i]!="NULL")
919 {
920 cout<<"Key is: "<<hashkey[i]<<" and its meaning is: "<<hashmean[i]<<"\n";
921 }
922 }
923}
924
925void Dict::search()
926{
927 string key;
928 cout<<"Enter the keyword you want to search:";
929 cin>>key;
930 for(int i=0;i<size;i++)
931 {
932 if(hashkey[i]==key)
933 {
934 cout<<"Its meaning is "<<hashmean[i]<<" at location "<<i<<"\n";
935 }
936 }
937}
938
939void Dict::delete_mean()
940{
941 string key;
942 cout<<"Enter the key to be deleted\n";
943 cin>>key;
944 for(int i=0;i<size;i++)
945 {
946 if(hashkey[i]==key)
947 {
948 cout<<"The keyword and its meaning has been deleted\n";
949 hashkey[i]="NULL";
950 hashmean[i]="NULL";
951 return;
952 }
953 }
954 cout<<"The keyword doesnt exist";
955}
956int main()
957{
958 Dict d1;
959 int ch;
960 char choice;
961 d1.create();
962 do
963 {
964 cout<<"Enter the choice:";
965 cin>>ch;
966 switch(ch)
967 {
968 case 1:
969 d1.display();
970 break;
971 case 2:
972 d1.search();
973 break;
974 case 3:
975 d1.delete_mean();
976 d1.display();
977 break;
978 }
979 cout<<"Do you want to continue:";
980 cin>>choice;
981 }
982 while(choice=='y');
983 return 0;
984}
985/*Batch:S4
986/*Problem Statement
987A Dictionary stores keywords & its meanings. Provide facility for adding new keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Binary Search Tree for implementation.
988Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Height balance tree and find the complexity for finding a keyword
989
990*/
991#include<iostream>
992#include<string.h>
993using namespace std;
994class node
995{public:
996 //int data;
997 char key[10],mean[10];
998 node *left,*right;
999 int ht;
1000};
1001
1002class AVL
1003{
1004 public:
1005 node *root;
1006 node *insert(node *,char[], char[]);//Recursive counterpart of insert
1007 node *Delete1(node *,char[]);//Recursive counterpart of delete
1008 void preorder1(node *); //Recursive counterpart of preorder
1009 void inorder1(node *); //Recursive counterpart of inorder
1010
1011 node *rotateright(node *);
1012 node *rotateleft(node *);
1013 node *RR(node *);
1014 node *LL(node *);
1015 node *LR(node *);
1016 node *RL(node *);
1017 int height(node *);
1018 int BF(node *);
1019 AVL()
1020 {
1021 root=NULL;
1022 }
1023 void create(char *x,char *y)
1024 {
1025 root=insert(root,x,y);
1026 }
1027 void Delete(char *x)
1028 {
1029 root=Delete1(root,x);
1030 }
1031
1032 void levelwise();
1033 void makenull()
1034 {
1035 root=NULL;
1036 }
1037};
1038int main()
1039{
1040 AVL A;
1041 char k[20],m[20];
1042 int n,i,op;
1043
1044 do
1045 {
1046 cout<<"\n1)Create : ";
1047 cout<<"\n2)Insert : ";
1048 cout<<"\n3)Delete : ";
1049 cout<<"\n4)Print : ";
1050 cout<<"\n5)Quit : ";
1051 cout<<"\nEnter Your Choice : ";
1052 cin >> op;
1053 switch(op)
1054 {
1055
1056 case 1:cout<<"\nEnter no.of elements :";
1057 cin>>n;
1058 cout<<"\n Enter key and its meaning:";
1059 A.makenull();
1060 for(i=0;i<n;i++)
1061 {
1062 cin>>k;
1063 cin>>m;
1064 A.create(k,m);
1065 }
1066 break;
1067 case 2:cout<<"\n Enter key and its meaning:";
1068 cin >>k;
1069 cin >>m;
1070 A.create(k,m);
1071 break;
1072 case 3:cout<<"\n Enter key to be deleted:";
1073 cin >>k;
1074 A.Delete(k);
1075 break;
1076 case 4: cout<<"\nPreorder sequence :\n";
1077 A.preorder1(A.root);
1078 cout<<"\nInorder sequence :\n";
1079 A.inorder1(A.root);
1080 //A.levelwise();
1081 break;
1082 }
1083
1084 }while(op!=5);
1085return 0;
1086
1087}
1088node * AVL::insert(node *T,char *k,char *m)
1089{
1090int i;
1091 if(T==NULL)
1092 {
1093 T=new node;
1094 strcpy(T->key,k);
1095 strcpy(T->mean,m);
1096 T->left=NULL;
1097 T->right=NULL;
1098 }
1099 else
1100 {
1101 for(int i=0;i<=strlen(k);i++)
1102 {
1103 if(k[i] > T->key[i]) // insert in right subtree
1104 {
1105 T->right=insert(T->right,k,m);
1106 if(BF(T)==-2)
1107 if(k [i] >T->right->key[i])
1108 T=RR(T);
1109 else
1110 T=RL(T);
1111 break;
1112 }
1113 else
1114 //if(x<T->key)
1115 {
1116 T->left=insert(T->left,k,m);
1117 if(BF(T)==2)
1118 if(k[i] < T->left->key[i])
1119 T=LL(T);
1120 else
1121 T=LR(T);
1122 break;
1123 }
1124 }
1125 }
1126 T->ht=height(T);
1127 return(T);
1128}
1129
1130int AVL::height(node *T)
1131{
1132 int lh,rh;
1133 if(T==NULL)
1134 return(0);
1135 if(T->left==NULL)
1136 lh=0;
1137 else
1138 lh=1+T->left->ht;
1139 if(T->right==NULL)
1140 rh=0;
1141 else
1142 rh=1+T->right->ht;
1143 if(lh>rh)
1144 return(lh);
1145 return(rh);
1146}
1147node * AVL::rotateright(node *x)
1148{
1149 node *y;
1150 y=x->left;
1151 x->left=y->right;
1152 y->right=x;
1153 x->ht=height(x);
1154 y->ht=height(y);
1155 return(y);
1156}
1157node * AVL::rotateleft(node *x)
1158{
1159 node *y;
1160 y=x->right;
1161 x->right=y->left;
1162 y->left=x;
1163 x->ht=height(x);
1164 y->ht=height(y);
1165 return(y);
1166}
1167node * AVL::RR(node *T)
1168{
1169 T=rotateleft(T);
1170 return(T);
1171}
1172node * AVL::LL(node *T)
1173{
1174 T=rotateright(T);
1175 return(T);
1176}
1177node * AVL::LR(node *T)
1178{
1179 T->left=rotateleft(T->left);
1180 T=rotateright(T);
1181 return(T);
1182}
1183node * AVL::RL(node *T)
1184{
1185 T->right=rotateright(T->right);
1186 T=rotateleft(T);
1187 return(T);
1188}
1189int AVL::BF(node *T)
1190{
1191 int lh,rh;
1192 if(T==NULL)
1193 return(0);
1194 if(T->left==NULL)
1195 lh=0;
1196 else
1197 lh=1+T->left->ht;
1198 if(T->right==NULL)
1199 rh=0;
1200 else
1201 rh=1+T->right->ht;
1202 return(lh-rh);
1203}
1204
1205void AVL::preorder1(node *T)
1206{
1207 if(T!=NULL)
1208 {
1209 cout<<" "<<T->key<<"(Bf="<<BF(T)<<")";
1210 preorder1(T->left);
1211 preorder1(T->right);
1212 }
1213}
1214
1215void AVL::inorder1(node *T)
1216{
1217 if(T!=NULL)
1218 {
1219 inorder1(T->left);
1220 cout<<" "<<T->key<<"(Bf="<<BF(T)<<")";
1221 inorder1(T->right);
1222 }
1223}
1224
1225node * AVL::Delete1(node *T,char *x)
1226{ node *p;
1227 if(T==NULL)
1228 {
1229 return NULL;
1230 }
1231 else
1232 {
1233 for(int i=0;i<strlen(x);i++)
1234 if(x[i] > T->key[i]) // insert in right subtree
1235 {
1236 T->right=Delete1(T->right,x);
1237 if(BF(T)==2)
1238 if(BF(T->left)>=0)
1239 T=LL(T);
1240 else
1241 T=LR(T);
1242 break;
1243 }
1244 else
1245 if(x[i]<T->key[i])
1246 {
1247 T->left=Delete1(T->left,x);
1248 if(BF(T)==-2)//Rebalance during windup
1249 if(BF(T->right)<=0)
1250 T=RR(T);
1251 else
1252 T=RL(T);
1253 break;
1254 }
1255
1256 else
1257 {
1258 //key to be deleted is found
1259 if(T->right !=NULL)
1260 { //delete its inorder succesor
1261 p=T->right;
1262 while(p->left != NULL)
1263 p=p->left;
1264
1265 strcpy(T->key,p->key);
1266 T->right=Delete1(T->right,p->key);
1267 if(BF(T)==2)//Rebalance during windup
1268 if(BF(T->left)>=0)
1269 T=LL(T);
1270 else
1271 T=LR(T);
1272 }
1273 else
1274 return(T->left);
1275 break;
1276
1277 }
1278 }
1279 T->ht=height(T);
1280 return(T);
1281}
1282/*Batch:S4
1283To create ADT that implements the SET concept. a. Add (new Element) -Place a value into the set b. Remove (element) Remove the value c. Contains (element) Return true if element is in collection d. Size () Return number of values in collection Iterator () Return an iterator used to loop over collection e. Intersection of two sets, f. Union of two sets, g. Difference between two sets, h. Subset set operations using STL
1284/*/
1285#include<iostream>
1286#include<set>
1287#include<algorithm>
1288#include<vector>
1289using namespace std;
1290int main()
1291{
1292 char y='y';
1293 int s1,s2;
1294 int a[20];
1295 int b[20];
1296
1297 cout<<"*** PROGRAM OF OPERATIONS ON SET ***";
1298 cout<<"\n Adding elements:";
1299 cout<<"\nEnter size of Set I and Set II :"<<endl;
1300 cin>>s1>>s2;
1301 cout<<"Enter elements of Set I :"<<endl;
1302 for(int i=0; i<s1; i++){
1303 cin>>a[i];
1304 }
1305 cout<<"\nEnter elements of Set II :"<<endl;
1306 for(int i=0; i<s2; i++){
1307 cin>>b[i];
1308 }
1309 set<int> I(a,a+s1);
1310 set<int> II(b,b+s2);
1311 vector<int> v(s1+s2);
1312 vector<int>::iterator i;
1313 set<int>::iterator it;
1314int ch;
1315int x=0;
1316int ch2;
1317int key;
1318do{
1319 cout<<"\n Menu:";
1320 cout<<"\n 1.Remove";
1321 cout<<"\n 2.Display";
1322 cout<<"\n 3.Union of sets";
1323 cout<<"\n 4.Intersection of sets";
1324 cout<<"\n 5.Difference of sets";
1325 cout<<"\n Enter your choice:";
1326 cin>>ch;
1327 switch(ch){
1328 case 1:
1329 cout<<"Remove from Set I or Set II?";
1330 cin>>ch2;
1331 cout<<"Enter the element to be deleted:";
1332 cin>>key;
1333 switch(ch2){
1334 case 1:
1335 for(it=I.begin();it!=I.end();it++){
1336 if(*it==key){
1337 break;
1338 }
1339 }
1340 I.erase(it);
1341 break;
1342 case 2:
1343 for(it=II.begin();it!=II.end();it++){
1344 if(*it==key){
1345 break;
1346 }
1347 }
1348 II.erase(it);
1349 break;
1350 }
1351 x++;
1352 v.resize(s1+s2-x);
1353 break;
1354 case 2:
1355 cout<<"\n Size of set I: "<<I.size();
1356 cout<<"\n Elements are:";
1357 for(it=I.begin();it!=I.end();it++)
1358 cout<<" "<<*it;
1359 cout<<"\n Size of set II: "<<II.size();
1360 cout<<"\n Elements are:";
1361 for(it=II.begin();it!=II.end();it++)
1362 cout<<" "<<*it;
1363 break;
1364 case 3:
1365 i=set_union(a,a+s1,b,b+s2,v.begin());
1366 v.resize(i-v.begin());
1367 cout<<"\nUNION: ";
1368 for(i=v.begin();i!=v.end();i++)
1369 cout<<" "<<*i;
1370 break;
1371 case 4:
1372 i=set_intersection(a,a+s1,b,b+s2,v.begin());
1373 v.resize(i-v.begin());
1374 cout<<"\n INTERSECTION: ";
1375 for(i=v.begin();i!=v.end();i++)
1376 cout<<" "<<*i;
1377 break;
1378 case 5:
1379 i=set_difference(a,a+s1,b,b+s2,v.begin());
1380 v.resize(i-v.begin());
1381 cout<<"\n SET DIFFERENCE: ";
1382 for(i=v.begin();i!=v.end();i++)
1383 cout<<" "<<*i;
1384 break;
1385
1386 }
1387 cout<<"\n Do you want to continue?(y,n) : ";
1388 cin>>y;
1389}while((y=='y')||(y=='Y'));
1390return 0;
1391}
1392
1393#include<iostream>
1394using namespace std;
1395class graph
1396{
1397int adjmat[10][10];
1398public:
1399 void initgraph();
1400 void displayg(int v,int e);
1401 void scangraph(int v,int e);
1402};
1403
1404void graph::initgraph() //constuctor to intialize Graph
1405 {
1406 int i,j;
1407 for(i=0;i<10;i++)
1408 {
1409 for(j=0;j<10;j++)
1410 adjmat[i][j]=0;
1411 }
1412 }
1413
1414void graph::displayg(int v,int e)
1415 {
1416 int i,j;
1417 for(i=0;i<v;i++)
1418 {
1419 cout<<endl;
1420 for(j=0;j<v;j++)
1421 cout<<adjmat[i][j]<<" ";
1422 }
1423 }
1424
1425void graph::scangraph(int v ,int e)
1426{
1427int i,s,d;
1428
1429cout<<"please enter source and destination of the edge(vertex no must be between 1 to"<<v<<")";
1430for(i=0;i<e;i++)
1431{
1432l1:
1433 cout<<endl<<"Edge no -> "<<i+1<<endl;
1434 cout<<"Source Vertex->";
1435 cin>>s;
1436 cout<<"Destination Vertex-> ";
1437 cin>>d;
1438 if((s>=1 && s<=v) && (d>=1 && d<=v))
1439{
1440 if((adjmat[s-1][d-1]==0) && (adjmat[d-1][s-1] == 0))
1441 {
1442 adjmat[s-1][d-1]=1;
1443 }
1444 else
1445 {
1446 cout<<"Edge already exist";
1447 goto l1;
1448 }
1449}
1450else
1451{
1452 cout<<"Please Enter correct vertex no's";
1453 goto l1;
1454}
1455}
1456}
1457int main()
1458{
1459int ch,cont,v,e;
1460graph g1;
1461do
1462{
1463cout<<endl<<"Menu";
1464cout<<endl<<"1.Create Graph using adjacency matrix";
1465cout<<endl<<"2.Display Graph";
1466cout<<endl<<"Enter Choice";
1467cin>>ch;
1468switch(ch)
1469{
1470case 1:
1471 g1.initgraph();
1472 cout<<"No of Vertices ?";
1473 cin>>v;
1474 cout<<"No of edges ?";
1475 cin>>e;
1476 g1.scangraph(v,e);
1477 break;
1478case 2:
1479 g1.displayg(v,e);
1480 break;
1481}
1482cout<<"do u want to continue?(1 for continue)";
1483cin>>cont;
1484}while(cont==1);
1485return 0;
1486}
1487//second part program
1488
1489
1490#include<iostream>
1491using namespace std;
1492struct edge
1493{
1494int dest;
1495struct edge *link;
1496};
1497
1498struct node
1499{
1500 struct node *next;
1501 int name;
1502 struct edge *adj;
1503};
1504
1505class graph
1506{
1507node *start;
1508
1509public:
1510 graph()
1511 {
1512 start=NULL;
1513 }
1514 void displayg(int v,int e);
1515 void scangraph(int v,int e);
1516};
1517
1518 void graph::displayg(int v,int e)
1519 {
1520 node *ptr;
1521 edge *p;
1522 ptr=start;
1523 while(ptr!=NULL)
1524 {
1525 cout<<endl;
1526 cout<<ptr->name;
1527 p=ptr->adj;
1528 while(p!=NULL)
1529 {
1530 cout<<"--> "<<p->dest;
1531 p=p->link;
1532 }
1533 ptr=ptr->next;
1534 if(ptr!=NULL)
1535 cout<<endl<<"|";
1536 }
1537 }
1538
1539void graph::scangraph(int v ,int e)
1540{
1541int i,s,d;
1542node *ptr,*bptr;
1543edge *p,*bp;
1544 for(i=0;i<v;i++) // for creating list of verices
1545 {
1546 ptr = new node;
1547 ptr->name=i+1;
1548 ptr->next=NULL;
1549 ptr->adj=NULL;
1550 if(start==NULL)
1551 {
1552 start =ptr;
1553 }
1554 else
1555 {
1556 bptr=start;
1557 while(bptr->next!=NULL)
1558 bptr=bptr->next;
1559 bptr->next=ptr;
1560 }
1561 }
1562 cout<<"please enter source and destination of the edge(vertex no must be between 1 to"<<v<<")";
1563 for(i=0;i<e;i++)
1564 {
1565 l1:
1566 cout<<endl<<"Edge no -> "<<i+1<<endl;
1567 cout<<"Source Vertex->";
1568 cin>>s;
1569 cout<<"Destination Vertex-> ";
1570 cin>>d;
1571 if((s>=1 && s<=v) && (d>=1 && d<=v))
1572 {
1573 bptr=start;
1574 while(bptr->name!=s)
1575 bptr=bptr->next;
1576 if(bptr!=NULL)
1577 {
1578 p =new edge;
1579 p->dest=d;
1580 p->link=NULL;
1581 bp=bptr->adj;
1582 if(bp==NULL)
1583 bptr->adj=p;
1584 else
1585 {
1586 while(bp->link!=NULL)
1587 bp=bp->link;
1588 bp->link=p;
1589 }
1590 }
1591 }
1592 else
1593 {
1594 cout<"Please Enter correct vertex no's";
1595 goto l1;
1596 }
1597 }
1598}
1599
1600int main()
1601{
1602int ch,cont,v,e;
1603graph g1;
1604do
1605{
1606cout<<endl<<"Menu";
1607cout<<endl<<"1.Create Graph using adjacency List";
1608cout<<endl<<"2.Display Graph";
1609cout<<endl<<"Enter Choice";
1610cin>>ch;
1611switch(ch)
1612{
1613case 1:
1614
1615 cout<<"No of Vertices ?";
1616 cin>>v;
1617 cout<<"No of edges ?";
1618 cin>>e;
1619 g1.scangraph(v,e);
1620 break;
1621case 2:
1622 g1.displayg(v,e);
1623 break;
1624}
1625cout<<endl<<"do u want to continue?(1 for continue)";
1626cin>>cont;
1627}while(cont==1);
1628return 0;
1629}
1630
1631#include<iostream>
1632using namespace std;
1633struct teldir
1634{
1635char name;
1636long number;
1637};
1638class dir
1639{
1640teldir book[25];
1641public:
1642 dir()
1643 {
1644 for(int i=0;i<25;i++)
1645 {
1646 book[i].name=' ';
1647 book[i].number=0;
1648 }
1649 }
1650 void createdir(int i,char p,long n);
1651 void display();
1652 void search(char p,int i);
1653};
1654
1655void dir::search(char p,int i)
1656{
1657int flag=0,count=1;
1658 if(book[i].name==p)
1659 {
1660 cout<<"found at "<<i;
1661 cout<<endl<<"no of comparision"<<count;
1662 }
1663 else
1664 {
1665 for(int j=i+1;j<25;j++)
1666 {
1667 count++;
1668 if(book[j].name==p)
1669 {
1670 cout<<"found at "<<j;
1671 cout<<endl<<"no of comparision"<<count;
1672 flag=1;
1673 break;
1674 }
1675 }
1676 if(flag==0)
1677 {
1678 for(int j=0;j<i;j++)
1679 {
1680 count++;
1681 if(book[j].name==p)
1682 {
1683 cout<<"found at "<<j;
1684 cout<<endl<<"no of comparision"<<count;
1685 flag=1;
1686 }
1687 }
1688 }
1689 if(flag==0)
1690 {
1691 cout<<"not found";
1692 }
1693 }
1694
1695}
1696void dir::display()
1697{
1698for(int i=0;i<25;i++)
1699 cout<<endl<<book[i].name<<" "<<book[i].number;
1700}
1701void dir::createdir(int i,char p, long n)
1702{
1703 int flag=0;
1704 if(book[i].name==' ')
1705 {
1706 book[i].name=p;
1707 book[i].number=n;
1708 }
1709 else
1710 {
1711 for(int j=i+1;j<25;j++)
1712 {
1713 if(book[j].name==' ')
1714 {
1715 book[j].name=p;
1716 book[j].number=n;
1717 flag=1;
1718 break;
1719 }
1720 }
1721 if(flag==0)
1722 {
1723 for(int j=0;j<i;j++)
1724 {
1725 if(book[j].name==' ')
1726 {
1727 book[j].name=p;
1728 book[j].number=n;
1729 flag=1;
1730 break;
1731 }
1732 }
1733 }
1734 if(flag==0)
1735 {
1736 cout<<"overflow";
1737 }
1738 }
1739
1740}
1741int main()
1742{
1743int ch,cont,total,tmp;
1744char p;
1745long n;
1746dir d1;
1747do
1748{
1749cout<<endl<<"Menu";
1750cout<<endl<<"1.Create Telephone book ";
1751cout<<endl<<"2.Display";
1752cout<<endl<<"3.Look up";
1753cout<<endl<<"Enter Choice";
1754cin>>ch;
1755switch(ch)
1756{
1757case 1:
1758 cout<<"how many entries";
1759 cin>>total;
1760 for(int i=0;i<total;i++)
1761 {
1762 cout<<"enter Name";
1763 cin>>p;
1764 cout<<"enter number";
1765 cin>>n;
1766 tmp=p;
1767 tmp=tmp%25;
1768 d1.createdir(tmp,p,n);
1769 }
1770 break;
1771case 2:
1772 d1.display();
1773 break;
1774case 3:
1775 cout<<"enter Name to search";
1776 cin>>p;
1777 tmp=p;
1778 tmp=tmp%25;
1779 d1.search(p,tmp);
1780 break;
1781
1782}
1783cout<<endl<<"do u want to continue?(1 for continue)";
1784cin>>cont;
1785}while(cont==1);
1786return 0;
1787}
1788#include<iostream>
1789#include<iomanip>
1790#include<fstream>
1791#include<string.h>
1792//#include<conio.h>
1793#include<stdlib.h>
1794using namespace std;
1795class STUD_CLASS
1796{
1797 typedef struct student
1798 {
1799 char name[10];
1800 int rollno;
1801 char div;
1802 char Address[20];
1803 }Rec;
1804 Rec Records;
1805 public:
1806 void Create(char f[]);
1807 void Display(char f[]);
1808 void Update(char f[]);
1809 void Delete(char f[]);
1810 void Append(char f[]);
1811 int Search(char f[]);
1812};
1813void STUD_CLASS::Create(char f[])
1814{
1815 char ch='y';
1816 fstream seqfile;
1817 seqfile.open(f,ios::in|ios::out|ios::binary);
1818 do
1819 {
1820 cout<<"\n Enter Name: ";
1821 cin>>Records.name;
1822 cout<<"\n Enter roll no: ";
1823 cin>>Records.rollno;
1824 cout<<"\n Enter div: ";
1825 cin>>Records.div;
1826 cout<<"\n Enter Address ";
1827 cin>>Records.Address;
1828
1829 //then write the record containing this data in the file
1830 seqfile.write((char*)&Records,sizeof(Records));
1831 cout<<"\nDo you want to add more records?";
1832 cin>>ch;
1833 }while(ch=='y');
1834 seqfile.close();
1835}
1836void STUD_CLASS::Display(char f[])
1837{
1838 fstream seqfile;
1839 int n,m,i;
1840 seqfile.open(f,ios::in|ios::out|ios::binary);
1841 //positioning the pointer in the file at the beginning
1842 seqfile.seekg(0,ios::beg);
1843 cout<<"\n The Contents of file are ..."<<endl;
1844 //read the records sequentially
1845 while(seqfile.read((char *)&Records,sizeof(Records)))
1846 {
1847 if(Records.rollno!=-1)
1848 {
1849 cout<<"\nName: "<<Records.name;
1850 cout<<"\nRollNO: "<<Records.rollno;
1851 cout<<"\nDivision: "<<Records.div;
1852 cout<<"\nAddress: "<<Records.Address;
1853 cout<<"\n";
1854 }
1855 }
1856 int last_rec=seqfile.tellg();//last record position
1857 //formula for computing total number of objects in the file
1858// n=last_rec/(sizeof(Rec));
1859// cout<<"\n\n Total number of objects are "<<n<<"(considering logical deletion)";
1860 seqfile.close();
1861}
1862void STUD_CLASS::Update(char f[])
1863{
1864 int pos;
1865 cout<<"\n For updation,";
1866 fstream seqfile;
1867 seqfile.open(f,ios::in|ios::out|ios::binary);
1868 seqfile.seekg(0,ios::beg);
1869 //obtaining the position of desired record in the file
1870 pos=Search(f);
1871 if(pos==-1)
1872 {
1873 cout<<"\n The record is not present in the file";
1874 return;
1875 }
1876 //calculate the actual offset of the desired record in the file
1877 int offset=pos*sizeof(Rec);
1878 seqfile.seekp(offset);//seeking the desired record for modification
1879 cout<<"\n Enter the values for updation...";
1880 cout<<"\n Name: ";cin>>Records.name;
1881 cout<<"\n Rollno: ";cin>>Records.rollno;
1882 cout<<"\n Div: ";cin>>Records.div;
1883 cout<<"\n Address: ";cin>>Records.Address;
1884 seqfile.write((char*)&Records,sizeof(Records))<<flush;
1885 seqfile.seekg(0);
1886 seqfile.close();
1887 cout<<"\n The record is updated!!!";
1888}
1889void STUD_CLASS::Delete(char f[])
1890{
1891 int id,pos;
1892 cout<<"\n For deletion,";
1893 fstream seqfile;
1894 seqfile.open(f,ios::in|ios::out|ios::binary);
1895 seqfile.seekg(0,ios::beg);//seeking for reading purpose
1896 pos=Search(f);//finding pos. for the record to be deleted
1897 if(pos==-1)
1898 {
1899 cout<<"\n The record is not present in the file";
1900 return;
1901 }
1902 //calculate offset to locate the desired record in the file
1903 int offset=pos*sizeof(Rec);
1904 seqfile.seekp(offset);//seeking the desired record for deletion
1905 strcpy(Records.name,"");
1906 Records.rollno=-1;
1907 Records.div=' ';
1908 strcpy(Records.Address,"");
1909 seqfile.write((char*)&Records,sizeof(Records))<<flush;
1910 seqfile.seekg(0);
1911 seqfile.close();
1912 cout<<"\n The record is Deleted!!!";
1913}
1914void STUD_CLASS::Append(char f[])
1915{
1916 fstream seqfile;
1917 seqfile.open(f,ios::ate|ios::in|ios::out|ios::binary);
1918 seqfile.seekg(0,ios::beg);
1919 int i=0;
1920 while(seqfile.read((char *)&Records,sizeof(Records)))
1921 {
1922 i++;//going through all the records
1923 // for reaching at the end of the file
1924 }
1925 //instead of above while loop
1926 //we can also use seqfile.seekg(0,ios::end)
1927 //for reaching at the end of the file
1928 seqfile.clear();//turning off EOF flag
1929 cout<<"\n Enter the record for appending";
1930 cout<<"\nName: ";cin>>Records.name;
1931 cout<<"\nRoll NO ";cin>>Records.rollno;
1932 cout<<"\nDiv: ";cin>>Records.div;
1933 cout<<"\nAddress: ";cin>>Records.Address;
1934 seqfile.write((char*)&Records,sizeof(Records));
1935 seqfile.seekg(0);//reposition to start(optional)
1936 seqfile.close();
1937 cout<<"\n The record is Appended!!!";
1938}
1939int STUD_CLASS::Search(char f[])
1940{
1941 fstream seqfile;
1942 int id,pos;
1943 cout<<"\n Enter the Roll no for searching the record ";
1944 cin>>id;
1945 seqfile.open(f,ios::ate|ios::in|ios::out|ios::binary);
1946 seqfile.seekg(0,ios::beg);
1947 pos=-1;
1948 int i=0;
1949 while(seqfile.read((char *)&Records,sizeof(Records)))
1950 {
1951 if(id==Records.rollno)
1952 {
1953 pos=i;
1954 break;
1955 }
1956 i++;
1957 }
1958 return pos;
1959}
1960int main()
1961{
1962 STUD_CLASS List;
1963 char ans='y';
1964 int choice,key;
1965 char filename[20];
1966 cout<<endl<<"please enter filename(make sure file is created in same folder)";
1967 cin>>filename;
1968 //clrscr();
1969 do
1970 {
1971 cout<<"\n Main Menu "<<endl;
1972 cout<<"\n 1.Create";
1973 cout<<"\n 2.Display";
1974 cout<<"\n 3.Update";
1975 cout<<"\n 4.Delete";
1976 cout<<"\n 5.Append";
1977 cout<<"\n 6.Search";
1978 cout<<"\n 7.Exit";
1979 cout<<"\n Enter your choice ";
1980 cin>>choice;
1981 switch(choice)
1982 {
1983 case 1:List.Create(filename);
1984 break;
1985 case 2:List.Display(filename);
1986 break;
1987 case 3:List.Update(filename);
1988 break;
1989 case 4:List.Delete(filename);
1990 break;
1991 case 5:List.Append(filename);
1992 break;
1993 case 6:key=List.Search(filename);
1994 if(key<0)
1995 cout<<"\n Record is not present in the file";
1996 else
1997 cout<<"\n Record is present in the file";
1998 break;
1999 case 7:exit(0);
2000 }
2001 cout<<"\n\t Do you want to go back to Main Menu?";
2002cin>>ans;
2003}while(ans=='y');
2004}
2005
2006/*
2007/*
2008 Batch::S4
2009 Problem Statement:
2010 Consider telephone book database of N clients. Make use of a hash table
2011 implementation to quickly look up client‘s telephone number.
2012
2013*/
2014#include<iostream>
2015#include<stdlib.h>
2016using namespace std;
2017class Hashing
2018{
2019int size,i,total_ele,index,new_index;
2020long tele,hashtable[50],search_key;
2021public:
2022void accept();
2023int hash(long key)
2024{
2025return (key % size);
2026}
2027void display();
2028int linear_prob(long,int);
2029void search();
2030void del();
2031};
2032void Hashing::accept()
2033{
2034cout<<"\nEnter size of Hash Table:";
2035cin>>size;
2036for(i=0;i<size;i++)
2037{
2038hashtable[i]=0;
2039}
2040cout<<"\nEnter the total number of elements:";
2041cin>>total_ele;
2042i=0;
2043while(i!=total_ele)
2044{
2045cout<<"\nEnter the telephone number:";
2046cin>>tele;
2047index = hash(tele);
2048if(hashtable[index]==0)
2049{
2050hashtable[index]=tele;
2051}
2052else
2053{
2054linear_prob(tele,index);
2055}
2056i++;
2057}
2058}int Hashing::linear_prob(long key,int pos){
2059int j;
2060for(j=0;j<size;j++){
2061new_index= (pos + j)% size;
2062if(hashtable[new_index]==0)
2063{
2064hashtable[new_index]=key;
2065break;
2066}
2067}
2068}
2069void Hashing::display()
2070{
2071cout<<"\nTelephone numbers in hash table:\n";
2072for(i=0;i<size;i++)
2073{
2074cout<<i<<"\t";
2075cout<<hashtable[i]<<endl;
2076}
2077}
2078void Hashing::search()
2079{
2080int flag=0;
2081cout<<"\nEnter number to search:";
2082cin>>search_key;
2083for(i=0;i<size;i++)
2084{
2085if(hashtable[i]==search_key)
2086{
2087cout<<"\nTelephone number is found at position "<<i<<endl;
2088flag=1;
2089break;
2090}
2091else
2092continue;
2093}
2094if(flag==0)
2095cout<<"\n Search key not found"<<endl;
2096}
2097void Hashing::del()
2098{
2099int flag=0,key;
2100cout<<"Enter the number to delete:- ";
2101cin>>key;
2102for(int i=0;i<size;i++)
2103{
2104if(hashtable[i]==key)
2105{
2106cout<<"The telephone no."<<hashtable[i]<<" is deleted";
2107hashtable[i]=0;
2108flag=1;}
2109elsecontinue;
2110}
2111if(flag==0)
2112cout<<"\nGiven key not found"<<endl;
2113}
2114int main(){
2115int ch;
2116Hashing h;
2117while(1)
2118{
2119cout<<"\nHashing Operations"<<endl;
2120cout<<"1.Insert Telephone Numbers"<<endl;
2121cout<<"2.Display Telephone Numbers"<<endl;
2122cout<<"3.Search Telephone Numbers"<<endl;
2123cout<<"4.Delete Telephone Number"<<endl;
2124cout<<"5.Exit"<<endl;
2125cout<<"Enter your choice:- ";
2126cin>>ch;
2127switch(ch)
2128{
2129case 1:
2130h.accept();
2131break;
2132case 2:
2133h.display();
2134break;
2135case 3:
2136h.search();
2137break;
2138case 4:
2139h.del();
2140break;
2141case 5:
2142exit(0);
2143default:
2144cout<<"Wrong Choice,Try Again";
2145}
2146}
2147return 0;
2148}
2149/*
2150Batch:s4
2151Problem Statement:
2152Any application defining scope of Formal parameter, Global parameter, Local parameter accessing mechanism and also relevance to private, public and protected access. Write a Java program which demonstrates the scope rules of the programming mechanism.
2153*/
2154
2155
2156class Teacher
2157 {
2158 private String designation = "Teacher";
2159 private String collegeName = "Beginnersbook";
2160 public String getDesignation()
2161 {
2162 return designation;
2163 }
2164 protected void setDesignation(String designation)
2165 {
2166 this.designation = designation;
2167 }
2168 protected String getCollegeName()
2169 {
2170 return collegeName;
2171 }
2172 protected void setCollegeName(String collegeName)
2173 {
2174 this.collegeName = collegeName;
2175 }
2176 void does(){
2177 System.out.println("Teaching");
2178 }
2179}
2180
2181public class JavaExample extends Teacher{
2182 String mainSubject = "Physics";
2183 public static void main(String args[])
2184 {
2185 JavaExample obj = new JavaExample();
2186 /* Note: we are not accessing the data members
2187 * directly we are using public getter method
2188 * to access the private members of parent class
2189 */
2190 System.out.println(obj.getCollegeName());
2191 System.out.println(obj.getDesignation());
2192 System.out.println(obj.mainSubject);
2193 obj.does();
2194 }
2195}
2196/*
2197 Batch:-S4
2198 Problem Statement:-
2199 Write a Java program which will demonstrate a concept of Interfaces and packages: In this assignment design and use of customized interfaces and packages for a specific application are expected.
2200*/
2201/*
2202package shapes;
2203
2204public interface Shape
2205{
2206
2207 public void getdata();
2208 public void calcarea();
2209 public void display();
2210}//create separate folder for package shape and create interface Shape
2211
2212*/
2213import shapes.*;
2214import java.util.*;
2215
2216class Circle implements Shape
2217{
2218 int radius;
2219 float area;
2220
2221 public void getdata()
2222 {
2223 Scanner scan = new Scanner(System.in);
2224 System.out.println("Enter the radius: ");
2225 radius=scan.nextInt();
2226 }
2227 public void calcarea()
2228 {
2229 area=(float)(3.14*radius*radius);
2230 }
2231 public void display()
2232 {
2233 System.out.println("Area of Circle is: "+area);
2234 }
2235}
2236
2237class Square implements Shape
2238{
2239 int side;
2240 float area;
2241
2242 public void getdata()
2243 {
2244 Scanner scan = new Scanner(System.in);
2245 System.out.println("Enter the side: ");
2246 side=scan.nextInt();
2247 }
2248 public void calcarea()
2249 {
2250 area=(float)(side*side);
2251 }
2252 public void display()
2253 {
2254 System.out.println("Area of Square is: "+area);
2255 }
2256}
2257
2258class Rectangle implements Shape
2259{
2260 int l,b;
2261 float area;
2262
2263 public void getdata()
2264 {
2265 Scanner scan = new Scanner(System.in);
2266 System.out.println("Enter the length: ");
2267 l=scan.nextInt();
2268 System.out.println("Enter the breadth: ");
2269 b=scan.nextInt();
2270 }
2271 public void calcarea()
2272 {
2273 area=(float)(l*b);
2274 }
2275 public void display()
2276 {
2277 System.out.println("Area of Square is: "+area);
2278 }
2279}
2280
2281class Display
2282{
2283 public static void main(String args[])
2284 {
2285 int ch;
2286 char choice;
2287 Circle c1 = new Circle();
2288 Square s1 = new Square();
2289 Rectangle r1 = new Rectangle();
2290 do
2291 {
2292 Scanner scan = new Scanner(System.in);
2293 System.out.println("Enter the choice 1.Circle \n 2.Square \n 3.Rectangle:");
2294 ch = scan.nextInt();
2295 switch(ch)
2296 {
2297 case 1:
2298 c1.getdata();
2299 c1.calcarea();
2300 c1.display();
2301 break;
2302
2303 case 2:
2304 s1.getdata();
2305 s1.calcarea();
2306 s1.display();
2307 break;
2308
2309
2310 case 3:
2311 r1.getdata();
2312 r1.calcarea();
2313 r1.display();
2314 break;
2315 }
2316
2317 System.out.println("Do you want to continue(y/n)");
2318 Scanner reader = new Scanner(System.in);
2319 choice = reader.next().charAt(0);
2320 }
2321 while(choice=='y');
2322 }
2323}
2324//============================================================================
2325// Name : Given binary tree with n nodes, assign this tree to another [operator=] and then erase all
2326// nodes in a binary tree.Assignment.cpp
2327// Author :
2328// Version :
2329// Copyright : Your copyright notice
2330// Description : C++,
2331//============================================================================
2332
2333#include<iostream>
2334using namespace std;
2335
2336// Node structure for BST
2337struct tnode
2338{
2339 int info; // node value
2340 struct tnode *left; //left child pointer
2341 struct tnode *right; //right child pointer
2342};
2343
2344
2345class bintree
2346{
2347 tnode *root; //private Memeber root of the tree
2348 public:
2349 bintree() //constructor to intialize root to NULL
2350 {
2351 root = NULL;
2352 }
2353 int isEmpty() //function to check if tree is empty
2354 {
2355 if(root==NULL)
2356 return 1;
2357 return 0;
2358 }
2359
2360 void insert(int val); //function for insertion of node in tree
2361 void inordertrav(); //wrapper function of inorder traveral
2362 void inorderbt(struct tnode *); //recursive function for inordere traversal
2363 void eraseall();//wrapper function to delete all nodes
2364 void displaytree();
2365 void display(struct tnode *);
2366};
2367
2368void bintree::display(struct tnode *p)
2369{
2370 if(p!=NULL)
2371 {
2372 cout<<endl<<p->info;
2373 display(p->left);
2374 display(p->right);
2375 }
2376
2377}
2378
2379void bintree::displaytree()
2380{
2381 display(root);
2382}
2383
2384void erase(struct tnode *p) //recursive function to delete nodes
2385{
2386 if(p!=NULL)
2387 {
2388 erase(p->left);
2389 erase(p->right);
2390 cout<<endl<<"deleting"<<p->info;
2391 delete p;
2392
2393 }
2394
2395}
2396void bintree::eraseall()
2397{
2398 erase(root);
2399 if(root==NULL)
2400 cout<<"deleted all";
2401
2402}
2403void bintree::inorderbt(struct tnode *p)
2404{
2405 if(p!=NULL)
2406 {
2407 inorderbt(p->left);
2408 cout<<" "<<p->info<<" ";
2409 inorderbt(p->right);
2410 }
2411}
2412void bintree::inordertrav()
2413{
2414
2415 inorderbt(root);
2416
2417}
2418void bintree::insert(int v)
2419{
2420 tnode *ctnode = new tnode;
2421 tnode *parent;
2422 ctnode->info =v;
2423 ctnode->left=NULL;
2424 ctnode->right=NULL;
2425 parent=NULL;
2426 if(isEmpty())
2427 {
2428 root=ctnode;
2429 }
2430 else
2431 {
2432 tnode *p=root;
2433 while(p!=NULL)
2434 {
2435 parent =p;
2436 if(v>p->info)
2437 p=p->right;
2438 else
2439 p=p->left;
2440
2441 }
2442 if(v<parent->info)
2443 parent->left=ctnode;
2444 else
2445 parent->right=ctnode;
2446 }
2447
2448}
2449
2450
2451int main()
2452{
2453bintree b;
2454bintree b1;
2455int ch,cont;
2456do
2457{
2458cout<<endl<<"Menu";
2459cout<<endl<<"1.Create Tree";
2460cout<<endl<<"2.Assign to other tree";
2461cout<<endl<<"3.Erase tree";
2462cout<<endl<<"Enter Choice";
2463cin>>ch;
2464switch(ch)
2465{
2466case 1:
2467 int n,val;
2468 cout<<"how many nodes" ;
2469 cin>>n;
2470 for(int i=0;i<n;i++)
2471 {
2472 cout<<"Enter Data for node";
2473 cin>>val;
2474 b.insert(val);
2475 }
2476 cout<<endl<<"Tree is-";
2477 b.inordertrav();
2478 break;
2479case 2:
2480 b1=b;
2481 b1.inordertrav();
2482 //b1.displaytree();
2483 break;
2484case 3:
2485 b.eraseall();
2486 break;
2487}
2488cout<<"do u want to continue?(1 for continue)";
2489cin>>cont;
2490}while(cont==1);
2491return 0;
2492}