DSPS MANUAL & PRACTICALS
SEM-1
------------------------------------------------------------------------------------------
DSPS(Data Structure And Problem Solving) Program's :
-------------------------------------------------------------------------------------------
GroupA
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 01
/* TITLE :A Vegetable and Fruit Mall wants to organize its vegetables and fruit products in a combination of purchase
pattern of customers. Solve the problem by suggesting appropriate data structures. Design necessary class.
//============================================================================*/
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
class fruit
{
public:
int i,n,m[10],temp;
char s[20][20],temp1[20][20];
int getdata();
int putdata();
};
class veg
{
public:
int i,n1,m1[10],temp;
char s1[20][20],temp1[20][20];
int getdata1();
int putdata1();
};
int fruit::getdata()
{
cout<<"\nEnter the number of fruits: ";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"\nEnter the name: ";
cin>>s[i];
cout<<"Enter the quantity: ";
cin>>m[i];
}
return 0;
}
int fruit::putdata()
{
cout<<"\nFruits Amount";
cout<<"\n....................";
for(i=0;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(m[i]<m[i+1])
{
temp=m[i];
strcpy(temp1[i],s[i]);
m[i]=m[i+1];
strcpy(s[i],s[i+1]);
m[i+1]=temp;
strcpy(s[i+1],temp1[i]);
}
}
}
for(i=0;i<n;i++)
{
cout<<endl;
cout<<s[i];
cout<<" "<<m[i];
}
return 0;
}
int veg::getdata1()
{
cout<<"\nEnter the number of vegetables: ";
cin>>n1;
for(i=0;i<n1;i++)
{
cout<<"\nEnter the name:";
cin>>s1[i];
cout<<"Enter the quantity: ";
cin>>m1[i];
}
return 0;
}
int veg::putdata1()
{
cout<<"\nVegetable Amount";
cout<<"\n....................";
for(i=0;i<n1;i++)
{
for(int j=1;j<n1;j++)
{
if(m1[i]<m1[i+1])
{
int temp;
temp=m1[i];
strcpy(temp1[i],s1[i]);
m1[i]=m1[i+1];
strcpy(s1[i],s1[i+1]);
m1[i+1]=temp;
strcpy(s1[i+1],temp1[i]);
}
}
}
for(i=0;i<n1;i++)
{
cout<<endl;
cout<<s1[i];
cout<<" "<<m1[i];
}
cout<<endl;
return 0;
}
int main()
{
veg v;
fruit f;
f.getdata();
v.getdata1();
f.putdata();
v.putdata1();
return 0;
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 02
/* TITLE :A Dictionary stores keywords & its meanings. Provide facility for adding new keywords, deleting keywords,
& updating values of any entry. Also provide facility to display whole data sorted in ascending/ Descending
order, Also find how many maximum comparisons may require for finding any keyword. Make use of
appropriate data structures
//============================================================================*/
//Assignment No. 2 - Dictionary
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define size 50
int creat();
int insert(int n);
int delet(int n);
int display(int n);
int modify(int n);
int sort(int n);
int search(int n);
struct dictionary
{
char word[20];
char meaning[30];
char key[20];
}d[size];
int main()
{
int ch,n=0;
do
{
printf("\n 1.Insert \n 2.Delete \n 3.Update \n 4.Sort \n 5.Search \n 6.Display \n 7. Exit");
printf("\n Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
n=insert(n);
display(n);
break;
case 2: delet(n);
display(n);
break;
case 3:
modify(n);
display(n);
break;
case 4:
sort(n);
display(n);
break;
case 5:
search(n);
break;
case 6:
display(n);
break;
case 7:
exit(0);
break;
default: printf("\nWrong choice...!!!");
}
printf("\n\nDo You want to Continue(1.Yes/2.No): ");
scanf("%d",&ch);
}while(ch==1);
}
int creat()
{
int i,n;
for(i=0;i<n;i++)
{
strcpy(d[i].word,"");
strcpy(d[i].meaning,"");
}
}
int insert (int i)
{
int n,j;
printf("\n\n How many Words you want to insert: ");
scanf("%d",&j);
for(i=0;i<j;i++)
{
printf("\nEnter the no. %d word: ",i+1);
scanf("%s",d[i].word);
printf(" Enter its Meaning: ");
scanf("%s",d[i].meaning);
}
printf("\n\n %d words are inserted successfully.\n\n",j);
}
int delet(int n)
{
int i, flag=0;
printf("\n\n Enter the Word to be Deleted: ");
scanf("%s",d[0].key);
for( i=0;i<n;i++)
{
if((strcmp(d[i].word,d[0].key)==0))
{
strcpy(d[i].word,"");
strcpy(d[i].meaning,"");
flag=1;
}
}
printf("\n\n Specified word is deleted successfully.\n\n");
if(flag==0)
printf("\n\n Specified word not found !!!\n\n");
}
int modify(int n)
{
int i;
int nr,nm;
char *key;
char nword[20];
char nmeaning[20];
printf("\n Enter the word to Update:");
scanf("%s",key);
for( i=0;i<n;i++)
{
if((strcmp(d[i].word,key)==0))
{
printf("\n Enter the New Word: ");
scanf("%s",nword);
printf("Enter the New meaning: ");
scanf("%s",nmeaning);
strcpy(d[i].word,nword);
strcpy(d[i].meaning,nmeaning);
}
}
printf("\n\n Specified word is updated successfully.\n\n");
}
int display(int n)
{
int i;
printf("\n\n**** DICTIONARY ***\n");
printf("\nSr.No. WORD MEANING \n");
printf(".......................................\n");
for(i=0;i<n;i++)
{
if((strcmp(d[i].word,"")!=0))
printf("\n %d\t %s\t %s",i+1,d[i].word,d[i].meaning);
}
printf("\n.......................................\n");
}
int search(int n)
{
int i,flag=0;
printf("\n Enter the Word to be searched: ");
scanf("%s",d[1].key);
for(i=0;i<n;i++)
{
if((strcmp(d[i].word,d[1].key)==0))
{
flag=1;
break;
}
}
if(flag==1)
{
printf("\nThe word with its meaning is Displayed below:\n");
printf("\n %s : %s \n\n",d[1].key,d[i].meaning);
}
else
printf("\n The Word Is Not Present");
}
int sort(int n)
{
int i,j,ch;
char temp_word[20];
char temp_meaning[30];
printf("\n1.Ascending\n2.Descending");
printf("\nSelect Choice: ");
scanf("%d",&ch);
if(ch==1)
{
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if((strcmp(d[i].word,d[j].word)<0))
{
strcpy(temp_word,d[i].word);
strcpy(temp_meaning,d[i].meaning);
strcpy(d[i].word,d[j].word);
strcpy(d[i].meaning,d[j].meaning);
strcpy(d[j].word,temp_word);
strcpy(d[j].meaning,temp_meaning);
}
}
}
printf("\nDictionary Sorted In Ascending Order.\n\n");
}
else
{
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if((strcmp(d[i].word,d[j].word)>0))
{
strcpy(temp_word,d[i].word);
strcpy(temp_meaning,d[i].meaning);
strcpy(d[i].word,d[j].word);
strcpy(d[i].meaning,d[j].meaning);
strcpy(d[j].word,temp_word);
strcpy(d[j].meaning,temp_meaning);
}
}
}
printf("\nDictionary Sorted In Descending Order.\n\n");
}
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 03
/* TITLE :A news paper delivery boy every day drops news paper in a society having many lanes & each lane have
many houses. Design a program to provide different paths that he could follow & also suggest the path which
will make him to finish his task with less effort. Solve the problem by suggesting appropriate data structures.
Design necessary class.
//============================================================================*/
//Assignment No. : 3 - Newspaper Delivery Boy
#include<stdio.h>
#include<stdlib.h>
#define size 20
#define TRUE 1
#define FALSE 0
int v[size];
int st[10];
int Paths[10][10];
int top,row;
int n=4;
int main()
{
int v1,i,j,sum[10];
int PathCompute(int v1, int g[size][size]);
int g[size][size] = {{0,5,9999,2},
{5,0,7,1},
{9999,7,0,4},
{2,1,4,0},
};
printf("\nProgram for finding various paths for a Newspaper Boy-\n");
row=-1;
for(i=0;i<size;i++)
sum[i]=9999;
for(v1=0;v1<n;v1++)
{
for(i=0;i<n;i++)
{
st[i]=0;
}
top=-1;
printf("\n Path");
if(v1>=n)
printf("Invalid Lane.\n");
else
{
PathCompute(v1,g);
printf("\n");
sum[v1]=0;
for(i=0,j=1;i<n-1;i++,j++)
sum[v1]=sum[v1]+g[Paths[v1][i]][Paths[v1][j]];
printf("\t Total Distance Travelled : %d\n", sum[v1]);
printf("\n-----------------------------");
}
}
int mindist=sum[0];
int mark=0;
for(i=0;i<n;i++)
{
if(sum[i]<mindist)
{
mindist=sum[i];
mark=i;
}
}
printf("\n\n The Minimum Effort Path :");
for(j=0;j<n;j++)
{
printf("\t%d",Paths[mark][j]);
}
printf("\n\n");
return 0;
}
int PathCompute(int v1,int g[size][size])
{
int i,v2,col=0;
row++;
int push(int item);
int efforts(int v,int row,int col);
int pop();
for(i=0;i<n;i++)
v[i]=FALSE;
push(v1);
while(top!=-1)
{
v1=pop();
if(v[v1]==FALSE)
{
printf("- Lane %d ",v1);
v[v1]=TRUE;
efforts(v1,row,col++);
}
for(v2=0;v2<n;v2++)
if(g[v1][v2]!=0 && v[v2]==FALSE)
push(v2);
}
}
int push(int item)
{
st[++top]=item;
}
int pop()
{
int item;
item=st[top];
top--;
return item;
}
int efforts(int v, int r, int c)
{
Paths[r][c]=v;
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 04
/* TITLE :Extending to problem 2. Consider dictionary data is stored in a file in random order. Thus, to search any
the word & its meanings from given data, program should create reasonably balanced tree.
//============================================================================*/
// Assignment No.- A4 - Dictionary using Tree (on window platform)
#include <stdio.h>
#include<iostream.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include<dos.h>
#define LEFT 1
#define RIGHT 2
struct node
{
char word[20],meaning[100];
node *left,*right;
};
node *maketree(char[],char[]);
node* treefromfile();
void filefromtree(node*);
void addword(node*,char[],char[]);
void seperateword(char[],char[],char[]);
void displayall(node*);
node* bsearch(node*,char[]);
void showmenu();
FILE *file_ptr;
void prog()
{
clrscr();
char word[20],meaning[100];
int menuchoice;
node *temp;
temp=treefromfile();
if(temp==NULL)
{
printf("
File does not exist or dictionary is empty...");
getch();
}
while(1)
{
clrscr();
showmenu();
scanf("
%d",&menuchoice);
switch(menuchoice)
{
case 1:printf("
Enter word : ");
scanf("%s",word);
printf("
Enter meaning : " );
flushall();
gets(meaning);
if(temp==NULL)
temp=maketree(word,meaning);
else
addword(temp,word,meaning);
break;
case 2:if(temp==NULL)
printf("
The dictionary is empty...");
else
{
printf("
Find meaning of : ");
flushall();
gets(word);
node *t;
t=bsearch(temp,word);
if(t==NULL)
printf("
Word not found...");
else
{
printf("
%s : ",t->word);
puts(t->meaning);
}
}
getch();
break;
case 3:if(temp==NULL)
printf("
Dictionary is empty...");
else
displayall(temp);
getch();
break;
case 4:filefromtree(temp);
exit(1);
break;
default:cout<<"
Enter Again";
delay(1000);
prog();
break;
}
}
}
void showmenu()
{
printf("
COMPUTER DICTIONARY");
printf("
[1]. Add a word.");
printf("
[2]. Find meaning.");
printf("
[3]. Display all.");
printf("
[4]. Save and Close.
Enter Choice");
}
node* treefromfile()
{
node *ptree=NULL;
char word[20],meaning[100],str[120],*i;
int flags=0;
file_ptr=fopen("C:\dict.anu","r");
if(file_ptr==NULL)
ptree=NULL;
else
{
while(!feof(file_ptr))
{
i=fgets(str,120,file_ptr);
if(i==NULL)
break;
seperateword(str,word,meaning);
if(flags==0)
{
ptree=maketree(word,meaning);
flags=1;
}
else
addword(ptree,word,meaning);
}
fclose(file_ptr);
}
return ptree;
}
node* maketree(char w[],char m[])
{
node *p;
p=new node;
strcpy(p->word,w);
strcpy(p->meaning,m);
p->left=NULL;
p->right=NULL;
return p;
}
void seperateword(char str[],char w[],char m[])
{
int i,j;
for(i=0;str[i]!=' ';i++)
w[i]=str[i];
w[i++]=NULL; //Append the null and skip the space.
for(j=0;str[i]!='
';i++,j++)
{
m[j]=str[i];
}
m[j]=NULL;
}
void addword(node *tree,char word[],char meaning[])
{
node *p,*q;
p=q=tree;
while(strcmp(word,p->word)!=0 && p!=NULL)
{
q=p;
if(strcmp(word,p->word)<0)
p=p->left;
else
p=p->right;
}
if(strcmp(word,q->word)==0)
{
printf("
This word already exists...");
delay(1000);
}
else if(strcmp(word,q->word)<0)
q->left=maketree(word,meaning);
else
q->right=maketree(word,meaning);
}
node* bsearch(node *tree,char word[])
{
node *q;
q=tree;
while(q!=NULL)
{
//p=q;
if(strcmp(word,q->word)<0)
q=q->left;
else if(strcmp(word,q->word)>0)
q=q->right;
if(strcmp(word,q->word)==0)
break;
}
return q;
}
void filefromtree(node *tree)
{
void travandwrite(node*);
file_ptr=fopen("C:\dict.anu","w");
if(file_ptr==NULL)
{
printf("
Cannot open file for writing data...");
}
else //if(tree==NULL)
{
if(tree!=NULL)
{
travandwrite(tree);
}
fclose(file_ptr); //Close the file anyway.
}
}
void travandwrite(node *tree)
{
if(tree!=NULL)
{
fprintf(file_ptr,"%s %s
",tree->word,tree->meaning);
travandwrite(tree->left);
travandwrite(tree->right);
}
}
void displayall(node *tree)
{
if(tree!=NULL)
{
displayall(tree->left);
printf("%s : %s
",tree->word,tree->meaning);
displayall(tree->right);
}
}
void intro()
{
int i;
clrscr();
gotoxy(20,20);
cout<<"DICTIONARY LOADING";
for(i=0;i<50;i++)
{
gotoxy(15+i,21);
cout<<"þþþ";
gotoxy(20,22);
cout<<2*i<<"% completed";
delay(150);
}
gotoxy(20,20);
cout<<"DICTIONARY LOADING COMPLETED";
clrscr();
}
void main()
{
clrscr();
intro();
prog();
}
Group-B
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 1
/* TITLE :Write a program using object oriented programming features to implement Doubly circular linked list with
different manipulation facilities in C++
//============================================================================*/
/*Assignment No:=B1*
* C++ Program to Implement Circular Doubly Linked List*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int info;
struct node *next;
struct node *prev;
}*start, *last;
int counter = 0;
class double_clist
{ public:
node *create_node(int);
void insert_begin();
void insert_last();
void insert_pos();
void delete_pos();
void search();
void update();
void display();
void reverse();
void sort();
double_clist()
{
start = NULL;
last = NULL;
} };
int main()
{
int choice;
double_clist cdl;
while (1)
{
cout<<"\n-------------------------------"<<endl;
cout<<"Operations on Doubly Circular linked list"<<endl;
cout<<"\n-------------------------------"<<endl;
cout<<"1.Insert at Beginning"<<endl;
cout<<"2.Insert at Last"<<endl;
cout<<"3.Insert at Position"<<endl;
cout<<"4.Delete at Position"<<endl;
cout<<"5.Update Node"<<endl;
cout<<"6.Search Element"<<endl;
cout<<"7.Sort"<<endl;
cout<<"8.Display List"<<endl;
cout<<"9.Reverse List"<<endl;
cout<<"10.Exit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cdl.insert_begin();
break;
case 2:
cdl.insert_last();
break;
case 3:
cdl.insert_pos();
break;
case 4:
cdl.delete_pos();
break;
case 5:
cdl.update();
break;
case 6:
cdl.search();
break;
case 7:
cdl.sort();
break;
case 8:
cdl.display();
break;
case 9:
cdl.reverse();
break;
case 10:
exit(1);
default:
cout<<"Wrong choice"<<endl;
} }
return 0;
}
node* double_clist::create_node(int value)
{
counter++;
struct node *temp;
temp = new(struct node);
temp->info = value;
temp->next = NULL;
temp->prev = NULL;
return temp;
}
void double_clist::insert_begin()
{
int value;
cout<<endl<<"Enter the element to be inserted: ";
cin>>value;
struct node *temp;
temp = create_node(value);
if (start == last && start == NULL)
{ cout<<"Element inserted in empty list"<<endl;
start = last = temp;
start->next = last->next = NULL;
start->prev = last->prev = NULL;
}
else
{
temp->next = start;
start->prev = temp;
start = temp;
start->prev = last;
last->next = start;
cout<<"Element inserted"<<endl;
} }
void double_clist::insert_last()
{
int value;
cout<<endl<<"Enter the element to be inserted: ";
cin>>value;
struct node *temp;
temp = create_node(value);
if (start == last && start == NULL)
{
cout<<"Element inserted in empty list"<<endl;
start = last = temp;
start->next = last->next = NULL;
start->prev = last->prev = NULL;
}
else
{
last->next = temp;
temp->prev = last;
last = temp;
start->prev = last;
last->next = start;
}
}
void double_clist::insert_pos()
{
int value, pos, i;
cout<<endl<<"Enter the element to be inserted: ";
cin>>value;
cout<<endl<<"Enter the postion of element inserted: ";
cin>>pos;
struct node *temp, *s, *ptr;
temp = create_node(value);
if (start == last && start == NULL)
{
if (pos == 1)
{
start = last = temp;
start->next = last->next = NULL;
start->prev = last->prev = NULL;
}
else
{
cout<<"Position out of range"<<endl;
counter--;
return;
}
}
else
{
if (counter < pos)
{
cout<<"Position out of range"<<endl;
counter--;
return;
}
s = start;
for (i = 1;i <= counter;i++)
{
ptr = s;
s = s->next;
if (i == pos - 1)
{
ptr->next = temp;
temp->prev = ptr;
temp->next = s;
s->prev = temp;
cout<<"Element inserted"<<endl;
} } } }
void double_clist::delete_pos()
{
int pos, i;
node *ptr, *s;
if (start == last && start == NULL)
{
cout<<"List is empty, nothing to delete"<<endl;
return;
}
cout<<endl<<"Enter the postion of element to be deleted: ";
cin>>pos;
if (counter < pos)
{
cout<<"Position out of range"<<endl;
return;
}
s = start;
if(pos == 1)
{
counter--;
last->next = s->next;
s->next->prev = last;
start = s->next;
free(s);
cout<<"Element Deleted"<<endl;
return;
}
for (i = 0;i < pos - 1;i++ )
{
s = s->next;
ptr = s->prev;
}
ptr->next = s->next;
s->next->prev = ptr;
if (pos == counter)
{
last = ptr;
}
counter--;
free(s);
cout<<"Element Deleted"<<endl;
}
void double_clist::update()
{
int value, i, pos;
if (start == last && start == NULL)
{
cout<<"The List is empty, nothing to update"<<endl;
return;
}
cout<<endl<<"Enter the postion of node to be updated: ";
cin>>pos;
cout<<"Enter the new value: ";
cin>>value;
struct node *s;
if (counter < pos)
{
cout<<"Position out of range"<<endl;
return;
}
s = start;
if (pos == 1)
{
s->info = value;
cout<<"Node Updated"<<endl;
return;
}
for (i=0;i < pos - 1;i++)
{
s = s->next;
}
s->info = value;
cout<<"Node Updated"<<endl;
}
void double_clist::search()
{
int pos = 0, value, i;
bool flag = false;
struct node *s;
if (start == last && start == NULL)
{
cout<<"The List is empty, nothing to search"<<endl;
return;
}
cout<<endl<<"Enter the value to be searched: ";
cin>>value;
s = start;
for (i = 0;i < counter;i++)
{
pos++;
if (s->info == value)
{
cout<<"Element "<<value<<" found at position: "<<pos<<endl;
flag = true;
}
s = s->next;
}
if (!flag)
cout<<"Element not found in the list"<<endl;
}
void double_clist::sort()
{
struct node *temp, *s;
int value, i;
if (start == last && start == NULL)
{
cout<<"The List is empty, nothing to sort"<<endl;
return;
}
s = start;
for (i = 0;i < counter;i++)
{
temp = s->next;
while (temp != start)
{
if (s->info > temp->info)
{
value = s->info;
s->info = temp->info;
temp->info = value;
}
temp = temp->next;
}
s = s->next;
} }
void double_clist::display()
{
int i;
struct node *s;
if (start == last && start == NULL)
{
cout<<"The List is empty, nothing to display"<<endl;
return;
}
s = start;
for (i = 0;i < counter-1;i++)
{
cout<<s->info<<"<->";
s = s->next;
}
cout<<s->info<<endl;
}
void double_clist::reverse()
{
if (start == last && start == NULL)
{
cout<<"The List is empty, nothing to reverse"<<endl;
return;
}
struct node *p1, *p2;
p1 = start;
p2 = p1->next;
p1->next = NULL;
p1->prev = p2;
while (p2 != start)
{
p2->prev = p2->next;
p2->next = p1;
p1 = p2;
p2 = p2->prev; }
last = start;
start = p1;
cout<<"List Reversed"<<endl;
}
/* OUTPUT
$ g++ doublycircular_llist.cpp
$ a.out
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 4
List is empty, nothing to delete
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 5
The List is empty, nothing to update
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 6
The List is empty, nothing to search
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 7
The List is empty, nothing to sort
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
The List is empty, nothing to display
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 9
The List is empty, nothing to reverse
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 1
Enter the element to be inserted: 100
Element inserted in empty list
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 2
Enter the element to be inserted: 200
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->200
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 3
Enter the element to be inserted: 150
Enter the postion of element inserted: 2
Element inserted
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->150<->200
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 3
Enter the element to be inserted: 1010
Enter the postion of element inserted: 3
Element inserted
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->150<->1010<->200
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 3
Enter the element to be inserted: 1111
Enter the postion of element inserted: 50
Position out of range
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 4
Enter the postion of element to be deleted: 3
Element Deleted
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->150<->200
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 5
Enter the postion of node to be updated: 2
Enter the new value: 1111
Node Updated
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->1111<->200
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 6
Enter the value to be searched: 200
Element 200 found at position: 3
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 5
Enter the postion of node to be updated: 14
Enter the new value: 45
Position out of range
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->1111<->200
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 7
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
100<->200<->1111
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 9
List Reversed
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 8
1111<->200<->100
---------------------------------
Operations on Doubly Circular linked list
---------------------------------
1.Insert at Beginning
2.Insert at Last
3.Insert at Position
4.Delete at Position
5.Update Node
6.Search Element
7.Sort
8.Display List
9.Reverse List
10.Exit
Enter your choice : 10
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 2
/* TITLE :Write a modular program using object oriented programming features to implement different sorting
methods(quick, merge, radix, shell, heap sort) using Python
//============================================================================*/
//All Python Program
*Assignment NO:=B2 heap*
def heapsort( aList ):
# convert aList to heap
length = len( aList ) - 1
leastParent = length / 2
for i in range ( leastParent, -1, -1 ):
moveDown( aList, i, length )
# flatten heap into sorted array
for i in range ( length, 0, -1 ):
if aList[0] > aList[i]:
swap( aList, 0, i )
moveDown( aList, 0, i - 1 )
def moveDown( aList, first, last ):
largest = 2 * first + 1
while largest <= last:
# right child exists and is larger than left child
if ( largest < last ) and ( aList[largest] < aList[largest + 1] ):
largest += 1
# right child is larger than parent
if aList[largest] > aList[first]:
swap( aList, largest, first )
# move down to largest child
first = largest;
largest = 2 * first + 1
else:
return # force exit
def swap( A, x, y ):
tmp = A[x]
A[x] = A[y]
A[y] = tmp
*Assignment No:=B2 merge*
list=[]
list1=[]
list2=[]
def merge(list,list1,list2):
for k in range(1,len(list1)+len(list2)):
i=1
j=1
if list1[i]>list2[j]:
list[k]=list2[j]
j=+1
k=+1
else:
list[k]=list2[i]
i=+1
k=+1
def split(list,list1,list2):
if len(list)<>1:
list1=list[:len(list)/2]
list2=list[len(list)/2:]
return
def sort(list):
split(list,list1,list2)
sort(list1)
sort(list2)
merge(list,list1,list2)
list = [15,8,59,69,45,23]
sort(list)
*Assignment No:=B2 Quick*
def sort(array=[12,4,5,6,7,3,1,15]):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
sort(less)
sort(pivot)
sort(greater)
*Assignment No:=B2 Radix*
def radixsort( aList ):
RADIX = 10
maxLength = False
tmp , placement = -1, 1
while not maxLength:
maxLength = True
# declare and initialize buckets
buckets = [list() for _ in range( RADIX )]
# split aList between lists
for i in aList:
tmp = i / placement
buckets[tmp % RADIX].append( i )
if maxLength and tmp > 0:
maxLength = False
# empty lists into aList array
a = 0
for b in range( RADIX ):
buck = buckets[b]
for i in buck:
aList[a] = i
a += 1
# move to next digit
placement *= RADIX
*Assignment NO:=B2 shell*
def shellSort(items):
inc = len(items) / 2
while inc:
for i in xrange(len(items)):
j = i
temp = items[i]
while j >= inc and items[j-inc] > temp:
items[j] = items[j - inc]
j -= inc
items[j] = temp
inc = inc/2 if inc/2 else (0 if inc==1 else 1)
a = [35, -8, 11, 1, 68, 0, 3];
shellSort(a)
print a
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 4
/* TITLE :Write a program using object oriented programming using C++ to create a binary tree if inorder& preorder or
inorder & postorder any two traversals are given.
//============================================================================*/
// Assignment No. B4 : Binary Tree Traversals
#include<iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
}node;
class BIN_TREE
{
public:
node *root,*New;
BIN_TREE();
void create();
void insert(node*,node*);
void inorder(node*);
void preorder(node*);
void postorder(node*);
};
class Stack
{
public:
node *data[20];
int Top;
int isempty();
void push(node *);
node *pop();
Stack()
{
Top=-1;
}
};
int Stack::isempty()
{
if(Top==-1)
return 1;
else
return(0);
}
void Stack::push(node *p)
{
Top++;
data[Top]=p;
}
node *Stack::pop()
{
return(data[Top--]);
}
BIN_TREE::BIN_TREE()
{
root=NULL;
}
void BIN_TREE::create()
{
char ch,ans;
do
{
New=new node;
cout<<" \n Enter the Value for the Node (Should be Numeric only):";
cin>>New->data;
New->left=New->right=NULL;
if(root==NULL)
root=New;
else
insert(root,New);
cout<<"\n Do you want to more nodes (y/n)?";
cin>>ch;
ans=ch;
}while(ans=='y'||ans=='Y');
}
void BIN_TREE::insert(node* root,node* New)
{
char ch;
cout<<"\n Where you want to attach this node ?";
cout<<"\n Insert to left or right of "<<root->data<<" (l/r)?";
cin>>ch;
{
if(ch=='l'||ch=='L')
{
if(root->left==NULL)
root->left=New;
else
insert(root->left,New);
}
else
{
if(root->right==NULL)
root->right=New;
else
insert(root->right,New);
}
}
}
void BIN_TREE::preorder(node *R)
{
if(R!=NULL)
{
cout<<R->data<<"\t";
preorder(R->left);
preorder(R->right);
}
}
void BIN_TREE::inorder(node *R)
{
if(R!=NULL)
{
inorder(R->left);
cout<<R->data<<"\t";
inorder(R->right);
}
}
void BIN_TREE::postorder(node *R)
{
if(R!=NULL)
{
inorder(R->left);
inorder(R->right);
cout<<R->data<<"\t";
}
}
int main()
{
int choice;
BIN_TREE obj;
do
{
cout<<"\n\n\n You have following Choices:";
cout<<"\n 1:Create a Tree \n 2:Find Preorder \n 3:Find Inorder";
cout<<"\n 4:Find Postorder \n 5:Exit";
cout<<"\n\n Enter your Choice:";
cin>>choice;
switch(choice)
{
case 1:
obj.create();
break;
case 2:
if(obj.root==NULL)
cout<<"\n There is no tree \n";
else
cout<<"\n\nThe Preorder for the given Tree is : ";
obj.preorder(obj.root);
break;
case 3:
if(obj.root==NULL)
cout<<"\n There is no tree \n";
else
cout<<"\nThe Inorder for the given Tree is : ";
obj.inorder(obj.root);
break;
case 4:
if(obj.root==NULL)
cout<<"\n There is no tree \n";
else
cout<<"\nThe Postorder for the given Tree is : ";
obj.postorder(obj.root);
break;
case 5:
//exit(0);
break;
}
}while(choice!=5);
return (0);
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 5
/* TITLE :Write a C++ program to implement traversals on Threaded Binary Tree using object oriented programming
features. Design necessary class.
//============================================================================*/
// Assignment No.: B5 - Threaded Binary Tree
#include<iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
int lbit,rbit;//0 thread 1 normal pointer
int isleft;//1 leftchild 0 rt child
}node;
class Thread_BIN_TREE
{
public:
node *root,*New;
Thread_BIN_TREE();
void create();
void insert(node*,node*);
node * inorder_succ(node*);
node * preorder_succ(node*);
node * postorder_succ(node*);
node * father(node*);
void nonrec_inorder();
void nonrec_preorder();
void nonrec_postorder();
};
Thread_BIN_TREE::Thread_BIN_TREE()
{
root=new Node;
root->lbit=0;
root->rbit=1;
root->left=root->right=root;
}
void Thread_BIN_TREE::create()
{
char ch,ans;
do
{
New=new node;
cout<<" \n Enter node data:";
cin>>New->data;
New->left=New->right=NULL;
if(root->lbit==0)
{
New->isleft=1;
New->left=root->left;
New->lbit=root->lbit;
New->right=root;
New->rbit=0;
root->left=New;
root->lbit=1;
}
else
{
insert(root->left,New);
}
cout<<"\n Do you want to more nodes(y/n)?";
cin>>ch;
ans=ch;
}while(ans=='y'||ans=='Y');
}
void Thread_BIN_TREE::insert(node* root,node* New)
{
char ch;
cout<<"\n Insert to left or right"<<root->data<<"(l/r)?";
cin>>ch;
{
if(ch=='l'||ch=='L')
{
New->isleft=1;
if(root->lbit==0)
{
New->left=root->left;
New->lbit=root->lbit;
New->right=root;
New->rbit=0;
root->left=New;
root->lbit=1;
}
else
{
insert(root->left,New);
}
}
else
{
New->isleft=0;
if(root->rbit==0)
{
New->left=root;
New->lbit=0;
New->right=root->right;
New->rbit=0;
root->right=New;
root->rbit=1;
}
else
insert(root->right,New);
}
}
}
void Thread_BIN_TREE::nonrec_preorder()
{
node *T;
T=root->left;
while(T!=root)
{
cout<<"\t"<<T->data;
T=preorder_succ(T);
}
}
node * Thread_BIN_TREE::preorder_succ(node* T)
{
if(T->lbit==1)
return(T->left);
if(T->rbit==1)
return(T->right);
while(T->rbit==0)
T=T->right;
return(T->right);
}
void Thread_BIN_TREE::nonrec_postorder()
{
node *T;
T=root->left;
while(T->lbit==1 || T->rbit==1)
{
if(T->lbit==1)
T=T->left;
else
T=T->right;
}
while(T!=root)
{
cout<<"\t"<<T->data;
T=postorder_succ(T);
}
}
node * Thread_BIN_TREE::father(node* T)
{
if(T->isleft==1)//isleft 1 for leftchild
{
while(T->rbit==1)
T=T->right;
return(T->right);
}
else
{
while(T->lbit==1)
T=T->left;
return(T->left);
}
}
node * Thread_BIN_TREE::postorder_succ(node* T)
{
if(T->isleft==1)
{
T=father(T);
if(T->rbit==0)//fathers right is thread
{
return(T);
}
else
{
if(T=T->right)//if father is root
return(T);
T=T->right;
while(T->lbit==1 || T->rbit==1)
{
if(T->lbit==1)
T=T->left;
else
T=T->right;
return(T);
}
}
}
else
{
return(father(T));
}
}
void Thread_BIN_TREE::nonrec_inorder()
{
node *T;
T=root->left;
while(T->lbit==1)
{
T=T->left;
}
while(T!=root)
{
cout<<"\t"<<T->data;
T=inorder_succ(T);
}
}
node * Thread_BIN_TREE::inorder_succ(node* T)
{
if(T->rbit==1)
{
T=T->right;
while(T->lbit==1)
{
T=T->left;
}
return(T);
}
if(T->rbit==0)
{
return(T->right);
}
}
int main()
{
int choice;
Thread_BIN_TREE obj;
do
{
cout<<"\n You have following choices:";
cout<<"\n 1:Create tree \n 2:Preorder Tree\n 3:Inorder Tree";
cout<<"\n 4:Postorder Tree\n5:Exit";
cout<<"\n Enter your choice:";
cin>>choice;
switch(choice)
{
case 1:
obj.create();
break;
case 2:
if(obj.root==NULL)
cout<<"\n There is no tree";
else
obj.nonrec_preorder();
break;
case 3:
if(obj.root==NULL)
cout<<"\n There is no tree";
else
obj.nonrec_inorder();
break;
case 4:
if(obj.root==NULL)
cout<<"\n There is no tree";
else
obj.nonrec_postorder();
break;
case 5:
//exit(0);
break;
}
}while(choice!=5);
return (0);
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 7
/* TITLE :Write a program to find shortest path for given source & destination of a given graph using C.
//============================================================================*/
// Assignment No.: B7 - Dijkstra's Shortest Path Algorithm.
#include<iostream>
#define INFINITY 999
using namespace std;
class Dijkstra{
private:
int adjMatrix[15][15];
int predecessor[15],distance[15];
int mark[15]; //keep track of visited node
int source;
int numOfVertices;
public:
/*
Function read() reads No of vertices, Adjacency Matrix and source
Matrix from the user. The number of vertices must be greather than
zero, all members of Adjacency Matrix must be postive as distances
are always positive. The source vertex must also be positive from 0
to noOfVertices - 1
*/
void read();
/*
Function initialize initializes all the data members at the begining of
the execution. The distance between source to source is zero and all other
distances between source and vertices are infinity. The mark is initialized
to false and predecessor is initialized to -1
*/
void initialize();
/*
Function getClosestUnmarkedNode returns the node which is nearest from the
Predecessor marked node. If the node is already marked as visited, then it search
for another node.
*/
int getClosestUnmarkedNode();
/*
Function calculateDistance calculates the minimum distances from the source node to
Other node.
*/
void calculateDistance();
/*
Function output prints the results
*/
void output();
void printPath(int);
};
void Dijkstra::read(){
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>numOfVertices;
while(numOfVertices <= 0) {
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>numOfVertices;
}
cout<<"Enter the adjacency matrix for the graph\n";
cout<<"To enter infinity enter "<<INFINITY<<endl;
for(int i=0;i<numOfVertices;i++)
{
cout<<"Enter the (+ve)weights for the row "<<i<<endl;
for(int j=0;j<numOfVertices;j++)
{
cin>>adjMatrix[i][j];
while(adjMatrix[i][j]<0)
{
cout<<"Weights should be +ve. Enter the weight again\n";
cin>>adjMatrix[i][j];
}
}
}
cout<<"Enter the source vertex\n";
cin>>source;
while((source<0) && (source>numOfVertices-1))
{
cout<<"Source vertex should be between 0 and"<<numOfVertices-1<<endl;
cout<<"Enter the source vertex again\n";
cin>>source;
}
}
void Dijkstra::initialize(){
for(int i=0;i<numOfVertices;i++) {
mark[i] = 0;
predecessor[i] = -1;
distance[i] = INFINITY;
}
distance[source]= 0;
}
int Dijkstra::getClosestUnmarkedNode(){
int minDistance = INFINITY;
int closestUnmarkedNode;
for(int i=0;i<numOfVertices;i++) {
if((!mark[i]) && ( minDistance >= distance[i])) {
minDistance = distance[i];
closestUnmarkedNode = i;
}
}
return closestUnmarkedNode;
}
void Dijkstra::calculateDistance(){
initialize();
int minDistance = INFINITY;
int closestUnmarkedNode;
int count = 0;
while(count < numOfVertices) {
closestUnmarkedNode = getClosestUnmarkedNode();
mark[closestUnmarkedNode] = 1;
for(int i=0;i<numOfVertices;i++) {
if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) ) {
if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {
distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];
predecessor[i] = closestUnmarkedNode;
}
}
}
count++;
}
}
void Dijkstra::printPath(int node){
if(node == source)
cout<<(char)(node + 97)<<"..";
else if(predecessor[node] == -1)
cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl;
else {
printPath(predecessor[node]);
cout<<(char) (node + 97)<<"..";
}
}
void Dijkstra::output(){
for(int i=0;i<numOfVertices;i++) {
if(i == source)
cout<<(char)(source + 97)<<".."<<source;
else
printPath(i);
cout<<"->"<<distance[i]<<endl;
}
}
int main(){
Dijkstra G;
G.read();
G.calculateDistance();
G.output();
return 0;
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 8
/* TITLE :Write a C program to generate optimal Binary Search Tree for given data
//============================================================================*/
//Assignment No.: B8 - Optimal binary search tree
#include <stdio.h>
#define MAXKEYS (30)
#define INFINITY 30000
int n; // number of keys
int key[MAXKEYS+1];
float p[MAXKEYS+1]; // probability of hitting key i
float e[MAXKEYS+1][MAXKEYS+1]; // cost of subtree
int r[MAXKEYS+1][MAXKEYS+1]; // root of subtree
float w[MAXKEYS+1][MAXKEYS+1]; // weight
void opttree()
{
int i,j,l,r1;
float t;
for (i=1;i<=n+1;i++)
{
e[i][i-1]=0; // initialize cost and weight matrix to zero
w[i][i-1]=0;
}
for (l=1;l<=n;l++) // width of tree h=1
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1;
e[i][j]=INFINITY;
w[i][j]=w[i][j-1]+p[j];
for(r1=i;r1<=j;r1++)
{
t=e[i][r1-1]+e[r1+1][j]+w[i][j];
if(t<e[i][j])
{
e[i][j]=t;
r[i][j]=r1;
}
}
}
}
}
//this function prints subtree
void construct_optimal_subtree(int i,int j, int r1, char *dir)
{
int t;
if(i<=j)
{
t=r[i][j];
printf("\n %d is the %s Child of %d ",key[t],dir,key[r1]);
construct_optimal_subtree(i,t-1,t,"Left");
construct_optimal_subtree(t+1,j,t,"Right");
}
}
// this function contructs binary tree. prints root
void construct_BST()
{
int r1;
r1=r[1][n];
printf("\n %d is the Root",key[r1]);
construct_optimal_subtree(1,r1-1,r1,"Left") ;
construct_optimal_subtree(r1+1,n,r1,"Right");
}
int main()
{
int i,j;
float prob=1.1;
printf("Enter the Total Number of Nodes");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\nEnter the Value of a Key: ");
scanf("%d",&key[i]);
printf("\n Enter its Probability of Success: ");
scanf("%f",&p[i]);
prob=prob-p[i];
if(prob<0)
{
printf("\nTotal Probability increased by 1, Enter again:");
prob=prob+p[i];
i--;
}
}
opttree();
printf("\nAverage Probe Length is %f\n",e[1][n]/w[1][n]);
printf("\nCost (e) Matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %.3f ",e[i][j]);
}
printf("\n");
}
printf("\n Weight Matrix is: \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %.3f ",w[i][j]);
}
printf("\n");
}
printf("\n Root Matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d ",r[i][j]);
}
printf("\n");
}
construct_BST();
printf("\n");
return 0;
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 10
/* TITLE :Write a C program to perform insert node, delete node and display operations on B tree.(on window platform)
//============================================================================*/
/* Binary tree implementation in CPP */
/* --------------------------------- */
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
struct node
{
node *left;
int value;
node *right;
};
node *curr=NULL;
int addnode(node *, node *);
int inorder(node *);
int preorder(node *);
int postorder(node *);
void main()
{
char c;
int v;
clrscr();
do
{
cout<<"
Select any one
";
cout<<"
0 ->Exit
";
cout<<"1 ->Add node
";
cout<<"2 ->Inorder traversal
";
cout<<"3 ->Preorder traversal
";
cout<<"4 ->Postorder trversal : ";
cin>>c;
switch(c)
{
case '0':
exit(1);
case '1':
node *temp;
temp = new node;
cout<<" Enter the value of the node : ";
cin>>temp->value;
if(curr==NULL)
{
curr=new node;
curr->value=temp->value;
curr->left=NULL;
curr->right=NULL;
cout<<" The root node is added";
}
else
v=addnode(curr,temp);
if(v==1)
cout<<" The node is added to the left";
else if(v==2)
cout<<" The node is added to the right";
else if(v==3)
cout<<" The same value exists";
break;
case '2':
v=inorder(curr);
if(v==0)
cout<<"The tree is empty";
break;
case '3':
v=preorder(curr);
if(v==0)
cout<<" The tree is empty";
break;
case '4':
v=postorder(curr);
if(v==0)
cout<<" The tree is empty";
break;
default:
cout<<" Invalid entry";
break;
}
}while(c!='0');
getch();
}
int addnode(node *fcurr, node *fnew )
{
if(fcurr->value==fnew->value)
{
return 3;
}
else
{
if(fcurr->value > fnew->value)
{
if(fcurr->left != NULL)
addnode(fcurr->left, fnew);
else
{
fcurr->left = fnew;
(fcurr->left)->left=NULL;
(fcurr->left)->right=NULL;
return 1;
}
}
else
{
if(fcurr->right != NULL)
addnode(fcurr->right, fnew);
else
{
fcurr->right = fnew;
(fcurr->right)->left=NULL;
(fcurr->right)->right=NULL;
return 2;
}
}
}
}
int inorder(node *fincurr)
{
if(fincurr == NULL)
return 0;
else
{
if(fincurr->left != NULL)
inorder(fincurr->left);
cout<<fincurr->value<<" ";
if(fincurr->right != NULL)
inorder(fincurr->right);
}
}
int preorder(node *fprcurr)
{
if(fprcurr == NULL)
return 0;
else
{
cout<<fprcurr->value<<" ";
if(fprcurr->left != NULL)
preorder(fprcurr->left);
if(fprcurr->right != NULL)
preorder(fprcurr->right);
}
}
int postorder(node *fpocurr)
{
if(fpocurr == NULL)
return 0;
else
{
if(fpocurr->left != NULL)
postorder(fpocurr->left);
if(fpocurr->right != NULL)
postorder(fpocurr->right);
cout<<fpocurr->value<<" ";
}
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 11
/* TITLE :Tic-Tac- Toe gaming application using C++ Programming
//============================================================================*/
//Assignment No.: B11 - Tic Tac Toe Game
#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 \n";
player--;
}
i=checkwin();
player++;
}while(i==-1);
board();
if(i==1)
cout<<"==>\aPlayer "<<--player<<" win \n\n";
else
cout<<"==>\aGame draw\n\n";
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;
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 12
/* TITLE :Binary tree traversals BFS & DFS using Python classes
//============================================================================*/
//BFS.py
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def traverse(rootnode):
thislevel = [rootnode]
while thislevel:
nextlevel = list()
for n in thislevel:
print n.value,
if n.left: nextlevel.append(n.left)
if n.right: nextlevel.append(n.right)
print
thislevel = nextlevel
//DFS.py
void printLevel(BinaryTree *p, int level) {
if (!p) return;
if (level == 1) {
cout << p->data << " ";
} else {
printLevel(p->left, level-1);
printLevel(p->right, level-1);
}
}
void printLevelOrder(BinaryTree *root) {
int height = maxHeight(root);
for (int level = 1; level <= height; level++) {
printLevel(root, level);
cout << endl;
}
}
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 14
/* TITLE :Write a program in Python – to implement following operations on text file :- create , Read,
calculate the frequency of each vowel, Count the words, characters, lines, white space & special
characters, Write all the results into another text file
//============================================================================*/
*Assignment No:=B14*
def count_vowels():
fin = open ('words.txt')
count = 0
vowels = ['aeiou']
for line in fin:
word = line.strip()
if uses(word, vowels):
count = count + 1
print "There are", count ," words with a vowel."
def uses(word, vowels):
for vowels in word:
if vowels in vowels:
return True
return False
def count_words():
fin = open ('words.txt')
vowels = ['aeiou']
for line in fin:
word = line.strip()
if uses(word, vowels):
print word
count_vowels()
count_words()
#This is what returns in the shell when I run my code:
>>>There are 1 words with a vowel.
There are 2 words with a vowel.
There are 3 words with a vowel.
There are 4 words with a vowel.
There are 5 words with a vowel.
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: 15
/* 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.
//============================================================================*/
/*
* C++ Program to Implement Hash Tables with Linear Probing
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;
/*
* HashNode Class Declaration
*/
class HashNode
{
public:
int key;
int value;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
}
};
/*
* DeletedNode Class Declaration
*/
class DeletedNode:public HashNode
{
private:
static DeletedNode *entry;
DeletedNode():HashNode(-1, -1)
{}
public:
static DeletedNode *getNode()
{
if (entry == NULL)
entry = new DeletedNode();
return entry;
}
};
DeletedNode *DeletedNode::entry = NULL;
/*
* HashMap Class Declaration
*/
class HashMap
{
private:
HashNode **htable;
public:
HashMap()
{
htable = new HashNode* [TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
{
htable[i] = NULL;
}
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; i++)
{
if (htable[i] != NULL && htable[i] != DeletedNode::getNode())
delete htable[i];
}
delete[] htable;
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
/*
* Insert Element at a key
*/
void Insert(int key, int value)
{
int hash_val = HashFunc(key);
int init = -1;
int deletedindex = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
if (htable[hash_val] == DeletedNode::getNode())
deletedindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
{
if(deletedindex != -1)
htable[deletedindex] = new HashNode(key, value);
else
htable[hash_val] = new HashNode(key, value);
}
if(init != hash_val)
{
if (htable[hash_val] != DeletedNode::getNode())
{
if (htable[hash_val] != NULL)
{
if (htable[hash_val]->key == key)
htable[hash_val]->value = value;
}
}
else
htable[hash_val] = new HashNode(key, value);
}
}
/*
* Search Element at a key
*/
int Search(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
return -1;
else
return htable[hash_val]->value;
}
/*
* Remove Element at a key
*/
void Remove(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && htable[hash_val] != NULL)
{
delete htable[hash_val];
htable[hash_val] = DeletedNode::getNode();
}
}
};
/*
* Main Contains Menu
*/
int main()
{
HashMap hash;
int key, value;
int choice;
while(1)
{
cout<<"\n----------------------"<<endl;
cout<<"Operations on Hash Table"<<endl;
cout<<"\n----------------------"<<endl;
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if(hash.Search(key) == -1)
{
cout<<"No element found at key "<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<hash.Search(key)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.Remove(key);
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}
/*
OUTPUT
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 100
Enter key at which element to be inserted: 1
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 300
Enter key at which element to be inserted: 3
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 500
Enter key at which element to be inserted: 5
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 600
Enter key at which element to be inserted: 6
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 800
Enter key at which element to be inserted: 8
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 1000
Enter key at which element to be inserted: 10
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 3
Element at key 3 : 300
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
No element found at key 7
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 10
Element at key 10 : 1000
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 5
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 6
Element at key 6 : 600
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 5
No element found at key 5
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 700
Enter key at which element to be inserted: 7
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
Element at key 7 : 700
----------------------
Operations on Hash Table
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4
*/
Group-C
//============================================================================
// Author: Aman Bohra
// ( bohraaman.blogspot.in)
// ROLL NO : 007
// CLASS : SE(COMPUTER)
// BATCH : S1
// ASSIGNMENT NO.: C1
/* TITLE :Write bubble Sort program using Python programming
//============================================================================*/
class Bubble:
#constructor defined
def __init__(self,myarr):
self.myarr=myarr
def bubbleSort(self):
swaps=True
while swaps:
swaps=False
for i in range(len(self.myarr)-1):
if self.myarr[i]>self.myarr[i+1]:
swaps=True
temp=self.myarr[i]
self.myarr[i]=self.myarr[i+1]
self.myarr[i+1]=temp
print(self.myarr)
def display(self):
print(self.myarr)
myarr=[70,20,10,40,30,60,50]
print("\n\t Program for Bubble Sort")
obj=Bubble(myarr)
obj.bubbleSort()
obj.display()
-------------------------------------------------------------------------
//output
//#Python Program to sort the numbers using Bubble Sort
#Total Numbers: 5
#Enter 1 Number: 5
#Enter 2 Number: 4
#Enter 3 Number: 3
#Enter 4 Number: 2
#Enter 5 Number: 1
#After iteration: 1
#4 3 2 1 5 /*** 2 biggest number(s) is(are) pushed to the end of the array***/
#After iteration: 2
#3 2 1 4 5 /*** 3 biggest number(s) is(are) pushed to the end of the array***/
#After iteration: 3
#2 1 3 4 5 /*** 4 biggest number(s) is(are) pushed to the end of the array***/
#After iteration: 4
#1 2 3 4 5 /*** 5 biggest number(s) is(are) pushed to the end of the array***/
#The sorted array is: 1 2 3 4 5
No comments:
Post a Comment