DATA STRUCTURE
1.BINARY SEARCH
#include
#include
int main()
{
int bsearch(int [],int,int);
int ARR[]={9,12,23,39,47,69,75,82,98,105,111,129,134};
int ITEM,N,index;
N=13;
cout<<"\nENTER ELEMENTS TO BE SEARCHED FOR:";
cin>>ITEM;
index=bsearch(ARR,N,ITEM);
if(index==1)
{
cout<<"\nSORRY!!! GIVEN DATA IS NOT AVAILABLE IN ARRAY \n";
}
else
{
cout<<"\n ELEMENTS FOUND AT INDEX:"<
return 0;
}
int bsearch(int ARR[],int size ,int item)
{
int beg ,last,mid;
beg=0;
last=size-1;
while(beg<=last)
{
mid=(beg+last)/2;
if(item==ARR[mid])
return mid;
else if(item>ARR[mid])
beg=mid+1;
else
last=mid-1;
}
return 1;
}
2.BUBBLE SORT
#include
#include
#include
int main()
{
int i,temp;
int num[10];
char *inname = "test.txt";
ifstream infile("D:\\cpp\\fs9.txt");
//clrscr();
if (!infile)
{
cout << "There was a problem opening file "
<< inname
<< " for reading."
<< endl;
return 0;
}
//clrscr();
cout << "Opened " << inname << " for reading." << endl;
int n=0;
while (infile >> i)
{
num[n]=i;
n++;
//cout << "Value from file is " << i << endl;
//cout<<"Array num:"<
cout<
{
cout<<"The value of file:"<
cout<<"\n*******************";
for(int u=0;u<10;u++)
{
for(int v=0;v
if(num[u]
temp=num[u];
num[u]=num[v];
num[v]=temp;
}
}
//cout<
}
cout<<"\nAfter sorting";
cout<
{
cout<<"The value of sorted array:"<
return 0;
}
3.SELECTION SORT
#include
#include
#include
class selections
{
int num[10];
int min,temp;
ifstream ifs;
public:
void acc()
{
ifstream ifs("D:\\cpp\\u.txt");
if(!ifs)
{
cout<<"\nError in opening file";
}
int n=0;
while(ifs)
{
ifs>>num[n];
n++;
}
for(int i=0;i<10;i++)
{
min=i;
for(int j=i+1;j<10;j++)
{
if(num[j]
min=j;
}
temp=num[i];
num[i]=num[min];
num[min]=temp;
}
}
cout<<"Array in sorted order\n";
for(i=0;i<10;i++)
{
cout<
}
};
void main()
{
selections s;
s.acc();
//getch();
}
4.INSERTION SORT
#include
int main()
{
int i, key;
//create array and store numbers to sort
int num[5] = {15,65,23,76,4};
int l=5;
// Display unsorted array
cout<
cout<
// perform insertion sort
for(int j=1;j<5;j++)
{
i=j-1;
key=num[j];
while(i>=0 && num[i]>key)
{
num[i+1]=num[i];
i--;
}
num[i+1]=key;
}
//Display sorted array
cout<
cout<
}
5.MERGE SORT
#include
#include
//Function Declarations
void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);
int main()
{
int arrayOne[5] ;
// = {65, 72, 105, 55, 2};
int arrayTwo[5];
ifstream ifs("D:\\cpp\\merge.txt");
int n=0;
while(ifs)
{
ifs>>arrayOne[n];
n++;
}
mergeSort(arrayOne, arrayTwo, 5);
for (int i = 0; i < 5; i++)
{
cout << arrayOne[i] << " ";
}//end for
return 0;
}//end main
// "Main" function of the sequence
// From here on out everything is called recursively
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, (mid+1), right);
merge(numbers, temp, left, (mid+1), right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos += 1;
left += 1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos += 1;
mid += 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left += 1;
tmp_pos += 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid += 1;
tmp_pos += 1;
}
//modified
for (i=0; i < num_elements; i++)
{
numbers[right] = temp[right];
right -= 1;
}
}
6.QUICK SORT
#include
#include
#include
#include
void quickSort(int numbers[], int array_size);
void q_sort(int numbers[], int left, int right);
int numbers[10];
int main()
{
clrscr();
int i;
ifstream infile("D:\\cpp\\fs9.txt");
//clrscr();
if (!infile)
{
cout << "There was a problem opening file "
<< " for reading."
<< endl;
return 0;
}
//clrscr();
cout << "Opened for reading." << endl;
int n1=0;
while (infile >> i)
{
numbers[n1]=i;
n1++;
//cout << "Value from file is " << i << endl;
//cout<<"Array num:"<
cout<
{
cout<<"The value of file:"<
/*
int i,n;
cout<<"How many numbers you want to sort: ";
cin>>n;
cout<<"Enter "<
*/
//perform quick sort on array
int n=sizeof(numbers)/sizeof(int);
q_sort(numbers,0,n-1);
cout<<"Numbers are sorted\n";
for (i = 0; i
return(0);
}
// Function to sort
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
Data encapsulation: the wrapping up of data and functions that act upon that data in a single unit is termed as data encapsulation. It binds together both the data and code and thus keeps both safe from the outside world. The data and the code to manipulate the data are combined in such a way that a black box is created which is self contained and modular. This box is termed as a class in object oriented terminology. Within a class the code or the data can be private or public. If it is private then these cannot be accessed by the outside world whereas public means that the code and the data is accessible to everyone. Typically the data is private and the methods are an interface to the private elements of the object.
Data abstraction: The term data abstraction is similar to data encapsulation. All the data and the methods that make sense to the objects of a class that is been designed need to be a part of the class. All unnecessary details should be left behind. E.g. when designing a class to represent a student we need data elements such as student no, student name, marks, grade, etc. If we now design a class representing a cricket player we need details like no of centuries, striking rate, no of matches played, etc. It will not make sense to add the player’s marks, grades which are applicable to a student class to this player class. The classes designed in object oriented language are also termed as User defined data types (UDT).
C++ Abstraction
Abstraction is one of the most powerful and vital features provided by object-oriented C++ programming language. Modularity is very important in any programming language, it provides flexibility to users for using the programming language. This aspect is well achieved with high performance by the concept of abstraction in C++. In object-oriented programming language the programmer can abstract both data and code when needed.
1) Encapsulation: It is the mechanism that binds together
code and data in manipulates, and keeps both safe from
outside interference and misuse. In short it isolates a
particular code and data from all other codes and data. A
well-defined interface controls the access to that
particular code and data.
2) Inheritance: It is the process by which one object
acquires the properties of another object. This supports
the hierarchical classification. Without the use of
hierarchies, each object would need to define all its
characteristics explicitly. However, by use of inheritance,
an object need only define those qualities that make it
unique within its class. It can inherit its general
attributes from its parent. A new sub-class inherits all of
the attributes of all of its ancestors.
3) Polymorphism: It is a feature that allows one interface
to be used for general class of actions. The specific
action is determined by the exact nature of the situation.
In general polymorphism means "one interface, multiple
methods", This means that it is possible to design a
generic interface to a group of related activities. This
helps reduce complexity by allowing the same interface to
be used to specify a general class of action. It is the
compiler's job to select the specific action (that is,
method) as it applies to each situation
7.BINARY SEARCH TREE
#include
#include
#include
int max(int value1,int value2)
{
return ((value1>value2)?value1:value2);
}
struct bstnode
{
public:
int data;
bstnode *left,*right;
bstnode(int x)
{
data=x;
left=right=NULL;
}
};
class bst
{
bstnode *root;
void inorder1(bstnode *t);
void preorder1(bstnode *t);
void postorder1(bstnode *t);
bstnode *delete1(bstnode *t,int);
int height1(bstnode *t);
public:
bst()
{
root=NULL;
}
bstnode *find(int x);
void delet(int x)
{
root=delete1(root,x);
}
void insert(int x);
void create();
void inorder()
{
inorder1(root);
}
void preorder()
{
preorder1(root);
}
void postorder()
{
postorder1(root);
}
int height()
{
return(height1(root));
}
};
int bst::height1(bstnode *t)
{
if(t==NULL)
return 0;
if(t->left==NULL && t->right==NULL)
return (0);
return (max(height1(t->left),height1(t->right))+1);
}
void bst::inorder1(bstnode *t)
{
if(t!=NULL)
{
inorder1(t->left);
cout<<" "<data;
inorder1(t->right);
}
}
void bst::preorder1(bstnode *t)
{
if(t!=NULL)
{
cout<<" "<data;
preorder1(t->left);
preorder1(t->right);
}
}
void bst::postorder1(bstnode *t)
{
if(t!=NULL)
{
postorder1(t->left);
postorder1(t->right);
cout<<" "<data;
}
}
bstnode *bst::delete1(bstnode *t,int x)
{
bstnode *temp;
if(t==NULL)
{
cout<<"\nElement Not Found";
return t;
}
if(xdata)
{
t->left=delete1(t->left,x);
return t;
}
if(x>t->data)
{
t->right=delete1(t->right,x);
return t;
}
if(t->left==NULL && t->right==NULL)
{
temp=t;
delete temp;
return (NULL);
}
if(t->left==NULL)
{
temp=t;
t=t->right;
delete temp;
return (t);
}
if(t->right==NULL)
{
temp=t;
t=t->left;
delete temp;
return (t);
}
temp=t->right;
while(temp->left!=NULL)
temp=temp->left;
t->data=temp->data;
t->right=delete1(t->right,temp->data);
return (t);
}
void bst::insert(int x)
{
bstnode *p,*q,*r;
r=new bstnode(x);
if(root==NULL)
{
root=r;
return;
}
p=root;
while(p!=NULL)
{
q=p;
if(x>p->data)
p=p->right;
else
p=p->left;
}
if(x>q->data)
q->right=r;
else
q->left=r;
}
void bst::create()
{
int n,x,i;
root=NULL;
cout<<"\nEnter no. of nodes";
cin>>n;
cout<<"\nEnter tree values:";
for(i=0;i
cin>>x;
insert(x);
}
}
bstnode *bst::find(int x)
{
bstnode *t=root;
while(t!=NULL)
{
if(x==t->data)
return(t);
if(x>root->data)
t=t->right;
else
t=t->left;
}
}
void main()
{
bst bs;
bstnode *p;
int x,op;
clrscr();
do
{
cout<<"\n\n1)Create\n2)inorder\n3)preorder\n4)postorder\n5)Find\n6)Delete\n7)height";
cout<<"\nEnter your choice:";
cin>>op;
switch(op)
{
case 1:bs.create();break;
case 2:bs.inorder();break;
case 3:bs.preorder();break;
case 4:bs.postorder();break;
case 5: cout<<"\nEnter the key to be searched:";
cin>>x;
p=bs.find(x);
if(p==NULL)
cout<<"\n*******Not Found********";
else
cout<<"\n********Found***********";
break;
case 6: cout<<"\nEnter key to be deleted";
cin>>x;
bs.delet(x);
break;
case 7: cout<<"\nHeight:"<
}
}while(op!=5);
}
Reverse a string.
//#include
#include
#include
typedef struct stack
{
char b[100];
int top;
}stack;
void push(stack *s,char k)
{
if(s->top==99)
printf("\n Stack is full ");
else
s->b[++s->top]=k;
}
char pop(stack *s)
{
char c;
if(s->top==(-1))
printf("\n Stack is empty");
else
c=s->b[s->top--];
return c;
}
void main()
{
char name[100];
stack s;
clrscr();
s.top=-1;
printf("\nEnter name :");
gets(name);
int i=0;
while(name[i]!='\0')
{
push(&s,name[i]);
i++;
}
printf("\n Reverse string is :");
while(s.top!=-1)
{
printf("%c",pop(&s));
}
getch();
}
#include
#include
#include
#include
class stack
{
char stack[50];
int top;
public:
void in_to_post(char infix[]);
void push (char);
char pop();
stack()
{
top=-1;
}
};
void stack::push(char symb)
{
if (top>=49)
{
cout<<"stack overflow";
getch();
return;
}
else
{
top=top+1;
stack[top]=symb;
}
}
char stack::pop()
{
char item;
if(top==-1)
{
cout<<"stack empty";
getch();
return(0);
}
else
{
item=stack[top];
top--;
}
return(item);
}
int preced(char ch)
{
if(ch== '(')
{
return 0;
}
else
if(ch== ')')
{
return 0;
}
if(ch== '+' || ch=='-')
{
return 1;
}
if(ch== '*' || ch=='/')
{
return 2;
}
if(ch=='^')
{
return 3;
}
else
return 0;
}
void stack::in_to_post(char infix[])
{
int length;
static int index=0,pos=0;
char symbol,temp;
char postfix[40];
length=strlen(infix);
push('#');
while(index
symbol=infix[index];
switch(symbol)
{
case'(':push(symbol);
break;
case')' :temp=pop();
while(temp!='(')
{
postfix[pos]=temp;
pos++;
temp=pop();
}
break;
case '+' :
case '-' :
case '*' :
case '/' :
case '^' :
while (preced(stack[top])>=preced(symbol))
{
temp=pop();
postfix[pos]=temp;
pos++;
}
push(symbol);
break;
default : postfix[pos++]=symbol;
break;
}
index++;
}
while(top>0)
{
temp=pop();
postfix[pos++]=temp;
}
postfix[pos++]='\0';
puts(postfix);
return;
}
void main()
{
stack s;
char infx[25];
cout<<"Enter the infix expression";
gets(infx);
s.in_to_post(infx);
getch();
}
#include
#include
#include
#include
struct node
{
char *names1;
char *roll1;
char * city1;
node *next;
};
class myfile
{
node *temp;
node *start;
char names[1300];
char roll[100];
char city[403];
public:
void display()
{
temp=new node;
//cout<
temp->roll1=roll;
temp->city1=city;
if(start==NULL)
{
start=temp;
start->next=NULL;
}
else
{
temp->next=start;
start=temp;
start->next=NULL;
}
cout<names1;
}
};
int main()
{
clrscr();
myfile f;
fstream fs;
fs.open("d:\\cpp\\kablu1.txt",ios::in||ios::out);
fs.seekg(0,ios::beg);
cout<<"\ncontents of file"<<"\n";
while(fs.read((char *)&f,sizeof(f)));
{
f.display();
}
getch();
}
*queue
#include
#include
struct node
{
int data;
node *next;
node()
{
next=NULL;
}
node(int x)
{
data=x;
}
};
class queue
{
node *r,*f;
public:
queue()
{
r=f=NULL;
}
void create();
void print();
void enqueue(int x);
int dequeue();
};
void queue::create()
{
int x,n,i;
node *p;
cout<<"\nEnter no. of nodes:";
cin>>n;
for(i=0;i
cout<<"\nEnter Next Data:";
cin>>x;
if(f==NULL)
r=f=new node(x);
else
{
r->next=new node(x);
r=r->next;
}
}
}
void queue::print()
{
cout<<"\nData Stored in the linked list";
node *p;
if(f==NULL)
return;
for(p=f;p!=NULL;p=p->next)
cout<<" "<data;
}
void queue::enqueue(int x)
{
if(f==NULL)
{
r=f=new node(x);
}
else
{
r->next=new node(x);
r=r->next;
}
}
int queue::dequeue()
{
node *p;
if(f==NULL)
{
cout<<"\nQueue is empty.....underflow";
return -1;
}
int x=f->data;
p=f;
f=f->next;
if(f==NULL)
r=NULL;
delete p;
return (x);
}
void main()
{
int op,x;
queue q;
do
{
cout<<"\n\n1)Create\n2)Print\n3)Insert";
cout<<"\n4)Delete\n5)Quit";
cout<<"\nEnter Your choice:";
cin>>op;
switch(op)
{
case 1: q.create();break;
case 2:q.print();break;
case 3: cout<<"Enter the data:";
cin>>x;
q.enqueue(x);
break;
case 4: x=q.dequeue();
cout<<"\nDeleted Data="<
}
}while(op!=5);
}
Stacks
#include
#include
struct node
{
node *next;
int data;
};
class stacks
{
public:
node *top;
void push();
void pop();
void display();
int empty();
void options();
stacks()
{
//top=NULL;
}
};
void stacks::options()
{
int i;
stacks s;
cout<<"\nEnter your choice:";
cin>>i;
switch(i)
{
case 1:
s.push();
exit(0);
break;
case 2:
s.pop();
break;
}
}
int stacks::empty()
{
if(top==NULL)
return 1;
}
void stacks::push()
{
node *p;
int d;
p=new node;
cout<<"\nEnter data:";
cin>>d;
p->data=d;
if(top==NULL)
{
top=p;
top->next=NULL;
}
else
{
p->data=d;
p->next=top;
top=p;
}
}
void stacks::display()
{
while(top->next==NULL)
{
cout<<"\ndata:"<data;
}
}
void stacks::pop()
{
if(top==NULL)
{
cout<<"\nUnderFlow";
}
else
{
node * t;
t=top;
top=top->next;
int x=t->data;
delete t;
cout<<"\nPop="<
}
int main()
{
stacks s;
//s.options();
int i;
while(1)
{
cout<<"\nEnter your choice:";
cin>>i;
switch(i)
{
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
exit(0);
}
}
return 0;
/*
s.push();
s.display();
s.pop();
s.push();
s.display();
s.pop();
*/
}
Sll
#include
#include
#include
#include
struct node
{ char name[20]; // Name of up to 20 letters
int age; // D.O.B. would be better
float height; // In metres
node *nxt; // Pointer to next node
};
node *temp,*temp2;
node *start_ptr = NULL;
class linklist
{
public:
void options();
void add_node_at_end();
void display();
void delete_start_node();
void delete_end_node();
//void display();
};
void linklist::delete_end_node()
{
node *temp1,*temp2;
if(start_ptr==NULL)
cout<<"The list is empty!!!!!"<
else
{
temp1=start_ptr;
if(temp1->nxt==NULL)
{
delete temp1;
start_ptr=NULL;
}
else
{
while(temp1->nxt!=NULL)
{
temp2=temp1;
temp1=temp1->nxt;
}
delete temp1;
temp2->nxt=NULL;
}
}
}
void linklist::options()
{
int i;
char ch;
do
{
cout<<"********************************"<
cout<<"\n1.Insert node at the end";
cout<<"\n2.Display the list";
cout<<"\n3.Deleting record from start of the list";
cout<<"\n4.Exit";
cout<<"\nEnter the operation::";
cin>>i;
switch(i)
{
case 1:
add_node_at_end();
break;
case 2:
display();
break;
case 3:
delete_start_node();
case 4:
exit(0);
default:
cout<<"\nWrong choice";
}
//cout<<"Would u like to see operations->>>>\n";
//cin>>ch;
}while(1);
}
void linklist::delete_start_node()
{
if(start_ptr==NULL)
cout<<"List is empty";
node *temp;
temp=start_ptr;
start_ptr=start_ptr->nxt;
delete temp;
}
void linklist::add_node_at_end()
{
// node *temp, *temp2; // Temporary pointers
// Reserve space for new node and fill it with data
char ch;
do
{
temp = new node;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;
// Set up link to this node
if (start_ptr == NULL)
{
start_ptr = temp;
}
else
{
temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{
temp2 = temp2->nxt;
// Move to next link in chain
}
temp2->nxt = temp;
}
cout<<"Would you like to Enter Another Record(y/n):"<
}
while(ch=='y');
}
void linklist::display()
{
temp=start_ptr;
do
{
if(temp==NULL)
{
cout<<"End of List or List is Empty\n"<
else
{
cout<<"Name :"<name<age<height<
temp=temp->nxt;
}
}while(temp!=NULL);
}
int main()
{
linklist l;
l.options();
//cout<"Press any key to exit......................";
//getch();
/*
l.add_node_at_end();
l.display();
l.delete_start_node();
l.display();
l.delete_end_node();
l.display();
*/
//getch();
//l.display();
//getch();
return 0;
}
Caps
#include
#include
#include
#include
int main()
{
char str[200];
char str1[200];
ifstream ifs("d:\\cpp\\kablu1.txt");
if(!ifs)
{
cout<<"\nError in opening file:";
return 0;
}
int n=0;
while(ifs)
{
ifs>>str[n];
str1[n]=str[n];
n++;
// cout<<(str1);
}
int sizes;
ifs.seekg(0,ios::end);
sizes=ifs.tellg();
cout<<"Size:"<
{
str1[i]=toupper(str[i]);
cout<<(str1[i]);
//if(str1[i+1]='\n')
//cout<
}
#include
#include
int main()
{
int bsearch(int [],int,int);
int ARR[]={9,12,23,39,47,69,75,82,98,105,111,129,134};
int ITEM,N,index;
N=13;
cout<<"\nENTER ELEMENTS TO BE SEARCHED FOR:";
cin>>ITEM;
index=bsearch(ARR,N,ITEM);
if(index==1)
{
cout<<"\nSORRY!!! GIVEN DATA IS NOT AVAILABLE IN ARRAY \n";
}
else
{
cout<<"\n ELEMENTS FOUND AT INDEX:"<
return 0;
}
int bsearch(int ARR[],int size ,int item)
{
int beg ,last,mid;
beg=0;
last=size-1;
while(beg<=last)
{
mid=(beg+last)/2;
if(item==ARR[mid])
return mid;
else if(item>ARR[mid])
beg=mid+1;
else
last=mid-1;
}
return 1;
}
2.BUBBLE SORT
#include
#include
#include
int main()
{
int i,temp;
int num[10];
char *inname = "test.txt";
ifstream infile("D:\\cpp\\fs9.txt");
//clrscr();
if (!infile)
{
cout << "There was a problem opening file "
<< inname
<< " for reading."
<< endl;
return 0;
}
//clrscr();
cout << "Opened " << inname << " for reading." << endl;
int n=0;
while (infile >> i)
{
num[n]=i;
n++;
//cout << "Value from file is " << i << endl;
//cout<<"Array num:"<
cout<
{
cout<<"The value of file:"<
cout<<"\n*******************";
for(int u=0;u<10;u++)
{
for(int v=0;v
if(num[u]
temp=num[u];
num[u]=num[v];
num[v]=temp;
}
}
//cout<
}
cout<<"\nAfter sorting";
cout<
{
cout<<"The value of sorted array:"<
return 0;
}
3.SELECTION SORT
#include
#include
#include
class selections
{
int num[10];
int min,temp;
ifstream ifs;
public:
void acc()
{
ifstream ifs("D:\\cpp\\u.txt");
if(!ifs)
{
cout<<"\nError in opening file";
}
int n=0;
while(ifs)
{
ifs>>num[n];
n++;
}
for(int i=0;i<10;i++)
{
min=i;
for(int j=i+1;j<10;j++)
{
if(num[j]
min=j;
}
temp=num[i];
num[i]=num[min];
num[min]=temp;
}
}
cout<<"Array in sorted order\n";
for(i=0;i<10;i++)
{
cout<
}
};
void main()
{
selections s;
s.acc();
//getch();
}
4.INSERTION SORT
#include
int main()
{
int i, key;
//create array and store numbers to sort
int num[5] = {15,65,23,76,4};
int l=5;
// Display unsorted array
cout<
cout<
// perform insertion sort
for(int j=1;j<5;j++)
{
i=j-1;
key=num[j];
while(i>=0 && num[i]>key)
{
num[i+1]=num[i];
i--;
}
num[i+1]=key;
}
//Display sorted array
cout<
cout<
}
5.MERGE SORT
#include
#include
//Function Declarations
void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);
int main()
{
int arrayOne[5] ;
// = {65, 72, 105, 55, 2};
int arrayTwo[5];
ifstream ifs("D:\\cpp\\merge.txt");
int n=0;
while(ifs)
{
ifs>>arrayOne[n];
n++;
}
mergeSort(arrayOne, arrayTwo, 5);
for (int i = 0; i < 5; i++)
{
cout << arrayOne[i] << " ";
}//end for
return 0;
}//end main
// "Main" function of the sequence
// From here on out everything is called recursively
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, (mid+1), right);
merge(numbers, temp, left, (mid+1), right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos += 1;
left += 1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos += 1;
mid += 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left += 1;
tmp_pos += 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid += 1;
tmp_pos += 1;
}
//modified
for (i=0; i < num_elements; i++)
{
numbers[right] = temp[right];
right -= 1;
}
}
6.QUICK SORT
#include
#include
#include
#include
void quickSort(int numbers[], int array_size);
void q_sort(int numbers[], int left, int right);
int numbers[10];
int main()
{
clrscr();
int i;
ifstream infile("D:\\cpp\\fs9.txt");
//clrscr();
if (!infile)
{
cout << "There was a problem opening file "
<< " for reading."
<< endl;
return 0;
}
//clrscr();
cout << "Opened for reading." << endl;
int n1=0;
while (infile >> i)
{
numbers[n1]=i;
n1++;
//cout << "Value from file is " << i << endl;
//cout<<"Array num:"<
cout<
{
cout<<"The value of file:"<
/*
int i,n;
cout<<"How many numbers you want to sort: ";
cin>>n;
cout<<"Enter "<
*/
//perform quick sort on array
int n=sizeof(numbers)/sizeof(int);
q_sort(numbers,0,n-1);
cout<<"Numbers are sorted\n";
for (i = 0; i
return(0);
}
// Function to sort
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
Data encapsulation: the wrapping up of data and functions that act upon that data in a single unit is termed as data encapsulation. It binds together both the data and code and thus keeps both safe from the outside world. The data and the code to manipulate the data are combined in such a way that a black box is created which is self contained and modular. This box is termed as a class in object oriented terminology. Within a class the code or the data can be private or public. If it is private then these cannot be accessed by the outside world whereas public means that the code and the data is accessible to everyone. Typically the data is private and the methods are an interface to the private elements of the object.
Data abstraction: The term data abstraction is similar to data encapsulation. All the data and the methods that make sense to the objects of a class that is been designed need to be a part of the class. All unnecessary details should be left behind. E.g. when designing a class to represent a student we need data elements such as student no, student name, marks, grade, etc. If we now design a class representing a cricket player we need details like no of centuries, striking rate, no of matches played, etc. It will not make sense to add the player’s marks, grades which are applicable to a student class to this player class. The classes designed in object oriented language are also termed as User defined data types (UDT).
C++ Abstraction
Abstraction is one of the most powerful and vital features provided by object-oriented C++ programming language. Modularity is very important in any programming language, it provides flexibility to users for using the programming language. This aspect is well achieved with high performance by the concept of abstraction in C++. In object-oriented programming language the programmer can abstract both data and code when needed.
1) Encapsulation: It is the mechanism that binds together
code and data in manipulates, and keeps both safe from
outside interference and misuse. In short it isolates a
particular code and data from all other codes and data. A
well-defined interface controls the access to that
particular code and data.
2) Inheritance: It is the process by which one object
acquires the properties of another object. This supports
the hierarchical classification. Without the use of
hierarchies, each object would need to define all its
characteristics explicitly. However, by use of inheritance,
an object need only define those qualities that make it
unique within its class. It can inherit its general
attributes from its parent. A new sub-class inherits all of
the attributes of all of its ancestors.
3) Polymorphism: It is a feature that allows one interface
to be used for general class of actions. The specific
action is determined by the exact nature of the situation.
In general polymorphism means "one interface, multiple
methods", This means that it is possible to design a
generic interface to a group of related activities. This
helps reduce complexity by allowing the same interface to
be used to specify a general class of action. It is the
compiler's job to select the specific action (that is,
method) as it applies to each situation
7.BINARY SEARCH TREE
#include
#include
#include
int max(int value1,int value2)
{
return ((value1>value2)?value1:value2);
}
struct bstnode
{
public:
int data;
bstnode *left,*right;
bstnode(int x)
{
data=x;
left=right=NULL;
}
};
class bst
{
bstnode *root;
void inorder1(bstnode *t);
void preorder1(bstnode *t);
void postorder1(bstnode *t);
bstnode *delete1(bstnode *t,int);
int height1(bstnode *t);
public:
bst()
{
root=NULL;
}
bstnode *find(int x);
void delet(int x)
{
root=delete1(root,x);
}
void insert(int x);
void create();
void inorder()
{
inorder1(root);
}
void preorder()
{
preorder1(root);
}
void postorder()
{
postorder1(root);
}
int height()
{
return(height1(root));
}
};
int bst::height1(bstnode *t)
{
if(t==NULL)
return 0;
if(t->left==NULL && t->right==NULL)
return (0);
return (max(height1(t->left),height1(t->right))+1);
}
void bst::inorder1(bstnode *t)
{
if(t!=NULL)
{
inorder1(t->left);
cout<<" "<
inorder1(t->right);
}
}
void bst::preorder1(bstnode *t)
{
if(t!=NULL)
{
cout<<" "<
preorder1(t->left);
preorder1(t->right);
}
}
void bst::postorder1(bstnode *t)
{
if(t!=NULL)
{
postorder1(t->left);
postorder1(t->right);
cout<<" "<
}
}
bstnode *bst::delete1(bstnode *t,int x)
{
bstnode *temp;
if(t==NULL)
{
cout<<"\nElement Not Found";
return t;
}
if(x
{
t->left=delete1(t->left,x);
return t;
}
if(x>t->data)
{
t->right=delete1(t->right,x);
return t;
}
if(t->left==NULL && t->right==NULL)
{
temp=t;
delete temp;
return (NULL);
}
if(t->left==NULL)
{
temp=t;
t=t->right;
delete temp;
return (t);
}
if(t->right==NULL)
{
temp=t;
t=t->left;
delete temp;
return (t);
}
temp=t->right;
while(temp->left!=NULL)
temp=temp->left;
t->data=temp->data;
t->right=delete1(t->right,temp->data);
return (t);
}
void bst::insert(int x)
{
bstnode *p,*q,*r;
r=new bstnode(x);
if(root==NULL)
{
root=r;
return;
}
p=root;
while(p!=NULL)
{
q=p;
if(x>p->data)
p=p->right;
else
p=p->left;
}
if(x>q->data)
q->right=r;
else
q->left=r;
}
void bst::create()
{
int n,x,i;
root=NULL;
cout<<"\nEnter no. of nodes";
cin>>n;
cout<<"\nEnter tree values:";
for(i=0;i
cin>>x;
insert(x);
}
}
bstnode *bst::find(int x)
{
bstnode *t=root;
while(t!=NULL)
{
if(x==t->data)
return(t);
if(x>root->data)
t=t->right;
else
t=t->left;
}
}
void main()
{
bst bs;
bstnode *p;
int x,op;
clrscr();
do
{
cout<<"\n\n1)Create\n2)inorder\n3)preorder\n4)postorder\n5)Find\n6)Delete\n7)height";
cout<<"\nEnter your choice:";
cin>>op;
switch(op)
{
case 1:bs.create();break;
case 2:bs.inorder();break;
case 3:bs.preorder();break;
case 4:bs.postorder();break;
case 5: cout<<"\nEnter the key to be searched:";
cin>>x;
p=bs.find(x);
if(p==NULL)
cout<<"\n*******Not Found********";
else
cout<<"\n********Found***********";
break;
case 6: cout<<"\nEnter key to be deleted";
cin>>x;
bs.delet(x);
break;
case 7: cout<<"\nHeight:"<
}
}while(op!=5);
}
Reverse a string.
//#include
#include
#include
typedef struct stack
{
char b[100];
int top;
}stack;
void push(stack *s,char k)
{
if(s->top==99)
printf("\n Stack is full ");
else
s->b[++s->top]=k;
}
char pop(stack *s)
{
char c;
if(s->top==(-1))
printf("\n Stack is empty");
else
c=s->b[s->top--];
return c;
}
void main()
{
char name[100];
stack s;
clrscr();
s.top=-1;
printf("\nEnter name :");
gets(name);
int i=0;
while(name[i]!='\0')
{
push(&s,name[i]);
i++;
}
printf("\n Reverse string is :");
while(s.top!=-1)
{
printf("%c",pop(&s));
}
getch();
}
#include
#include
#include
#include
class stack
{
char stack[50];
int top;
public:
void in_to_post(char infix[]);
void push (char);
char pop();
stack()
{
top=-1;
}
};
void stack::push(char symb)
{
if (top>=49)
{
cout<<"stack overflow";
getch();
return;
}
else
{
top=top+1;
stack[top]=symb;
}
}
char stack::pop()
{
char item;
if(top==-1)
{
cout<<"stack empty";
getch();
return(0);
}
else
{
item=stack[top];
top--;
}
return(item);
}
int preced(char ch)
{
if(ch== '(')
{
return 0;
}
else
if(ch== ')')
{
return 0;
}
if(ch== '+' || ch=='-')
{
return 1;
}
if(ch== '*' || ch=='/')
{
return 2;
}
if(ch=='^')
{
return 3;
}
else
return 0;
}
void stack::in_to_post(char infix[])
{
int length;
static int index=0,pos=0;
char symbol,temp;
char postfix[40];
length=strlen(infix);
push('#');
while(index
symbol=infix[index];
switch(symbol)
{
case'(':push(symbol);
break;
case')' :temp=pop();
while(temp!='(')
{
postfix[pos]=temp;
pos++;
temp=pop();
}
break;
case '+' :
case '-' :
case '*' :
case '/' :
case '^' :
while (preced(stack[top])>=preced(symbol))
{
temp=pop();
postfix[pos]=temp;
pos++;
}
push(symbol);
break;
default : postfix[pos++]=symbol;
break;
}
index++;
}
while(top>0)
{
temp=pop();
postfix[pos++]=temp;
}
postfix[pos++]='\0';
puts(postfix);
return;
}
void main()
{
stack s;
char infx[25];
cout<<"Enter the infix expression";
gets(infx);
s.in_to_post(infx);
getch();
}
#include
#include
#include
#include
struct node
{
char *names1;
char *roll1;
char * city1;
node *next;
};
class myfile
{
node *temp;
node *start;
char names[1300];
char roll[100];
char city[403];
public:
void display()
{
temp=new node;
//cout<
temp->roll1=roll;
temp->city1=city;
if(start==NULL)
{
start=temp;
start->next=NULL;
}
else
{
temp->next=start;
start=temp;
start->next=NULL;
}
cout<
}
};
int main()
{
clrscr();
myfile f;
fstream fs;
fs.open("d:\\cpp\\kablu1.txt",ios::in||ios::out);
fs.seekg(0,ios::beg);
cout<<"\ncontents of file"<<"\n";
while(fs.read((char *)&f,sizeof(f)));
{
f.display();
}
getch();
}
*queue
#include
#include
struct node
{
int data;
node *next;
node()
{
next=NULL;
}
node(int x)
{
data=x;
}
};
class queue
{
node *r,*f;
public:
queue()
{
r=f=NULL;
}
void create();
void print();
void enqueue(int x);
int dequeue();
};
void queue::create()
{
int x,n,i;
node *p;
cout<<"\nEnter no. of nodes:";
cin>>n;
for(i=0;i
cout<<"\nEnter Next Data:";
cin>>x;
if(f==NULL)
r=f=new node(x);
else
{
r->next=new node(x);
r=r->next;
}
}
}
void queue::print()
{
cout<<"\nData Stored in the linked list";
node *p;
if(f==NULL)
return;
for(p=f;p!=NULL;p=p->next)
cout<<" "<
}
void queue::enqueue(int x)
{
if(f==NULL)
{
r=f=new node(x);
}
else
{
r->next=new node(x);
r=r->next;
}
}
int queue::dequeue()
{
node *p;
if(f==NULL)
{
cout<<"\nQueue is empty.....underflow";
return -1;
}
int x=f->data;
p=f;
f=f->next;
if(f==NULL)
r=NULL;
delete p;
return (x);
}
void main()
{
int op,x;
queue q;
do
{
cout<<"\n\n1)Create\n2)Print\n3)Insert";
cout<<"\n4)Delete\n5)Quit";
cout<<"\nEnter Your choice:";
cin>>op;
switch(op)
{
case 1: q.create();break;
case 2:q.print();break;
case 3: cout<<"Enter the data:";
cin>>x;
q.enqueue(x);
break;
case 4: x=q.dequeue();
cout<<"\nDeleted Data="<
}
}while(op!=5);
}
Stacks
#include
#include
struct node
{
node *next;
int data;
};
class stacks
{
public:
node *top;
void push();
void pop();
void display();
int empty();
void options();
stacks()
{
//top=NULL;
}
};
void stacks::options()
{
int i;
stacks s;
cout<<"\nEnter your choice:";
cin>>i;
switch(i)
{
case 1:
s.push();
exit(0);
break;
case 2:
s.pop();
break;
}
}
int stacks::empty()
{
if(top==NULL)
return 1;
}
void stacks::push()
{
node *p;
int d;
p=new node;
cout<<"\nEnter data:";
cin>>d;
p->data=d;
if(top==NULL)
{
top=p;
top->next=NULL;
}
else
{
p->data=d;
p->next=top;
top=p;
}
}
void stacks::display()
{
while(top->next==NULL)
{
cout<<"\ndata:"<
}
}
void stacks::pop()
{
if(top==NULL)
{
cout<<"\nUnderFlow";
}
else
{
node * t;
t=top;
top=top->next;
int x=t->data;
delete t;
cout<<"\nPop="<
}
int main()
{
stacks s;
//s.options();
int i;
while(1)
{
cout<<"\nEnter your choice:";
cin>>i;
switch(i)
{
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
exit(0);
}
}
return 0;
/*
s.push();
s.display();
s.pop();
s.push();
s.display();
s.pop();
*/
}
Sll
#include
#include
#include
#include
struct node
{ char name[20]; // Name of up to 20 letters
int age; // D.O.B. would be better
float height; // In metres
node *nxt; // Pointer to next node
};
node *temp,*temp2;
node *start_ptr = NULL;
class linklist
{
public:
void options();
void add_node_at_end();
void display();
void delete_start_node();
void delete_end_node();
//void display();
};
void linklist::delete_end_node()
{
node *temp1,*temp2;
if(start_ptr==NULL)
cout<<"The list is empty!!!!!"<
else
{
temp1=start_ptr;
if(temp1->nxt==NULL)
{
delete temp1;
start_ptr=NULL;
}
else
{
while(temp1->nxt!=NULL)
{
temp2=temp1;
temp1=temp1->nxt;
}
delete temp1;
temp2->nxt=NULL;
}
}
}
void linklist::options()
{
int i;
char ch;
do
{
cout<<"********************************"<
cout<<"\n1.Insert node at the end";
cout<<"\n2.Display the list";
cout<<"\n3.Deleting record from start of the list";
cout<<"\n4.Exit";
cout<<"\nEnter the operation::";
cin>>i;
switch(i)
{
case 1:
add_node_at_end();
break;
case 2:
display();
break;
case 3:
delete_start_node();
case 4:
exit(0);
default:
cout<<"\nWrong choice";
}
//cout<<"Would u like to see operations->>>>\n";
//cin>>ch;
}while(1);
}
void linklist::delete_start_node()
{
if(start_ptr==NULL)
cout<<"List is empty";
node *temp;
temp=start_ptr;
start_ptr=start_ptr->nxt;
delete temp;
}
void linklist::add_node_at_end()
{
// node *temp, *temp2; // Temporary pointers
// Reserve space for new node and fill it with data
char ch;
do
{
temp = new node;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;
// Set up link to this node
if (start_ptr == NULL)
{
start_ptr = temp;
}
else
{
temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{
temp2 = temp2->nxt;
// Move to next link in chain
}
temp2->nxt = temp;
}
cout<<"Would you like to Enter Another Record(y/n):"<
}
while(ch=='y');
}
void linklist::display()
{
temp=start_ptr;
do
{
if(temp==NULL)
{
cout<<"End of List or List is Empty\n"<
else
{
cout<<"Name :"<
temp=temp->nxt;
}
}while(temp!=NULL);
}
int main()
{
linklist l;
l.options();
//cout<"Press any key to exit......................";
//getch();
/*
l.add_node_at_end();
l.display();
l.delete_start_node();
l.display();
l.delete_end_node();
l.display();
*/
//getch();
//l.display();
//getch();
return 0;
}
Caps
#include
#include
#include
#include
int main()
{
char str[200];
char str1[200];
ifstream ifs("d:\\cpp\\kablu1.txt");
if(!ifs)
{
cout<<"\nError in opening file:";
return 0;
}
int n=0;
while(ifs)
{
ifs>>str[n];
str1[n]=str[n];
n++;
// cout<<(str1);
}
int sizes;
ifs.seekg(0,ios::end);
sizes=ifs.tellg();
cout<<"Size:"<
{
str1[i]=toupper(str[i]);
cout<<(str1[i]);
//if(str1[i+1]='\n')
//cout<
}
Comments
Post a Comment