Ashutosh Prasad Yadav Btech (Cse) - 3 Sem Roll No.-191112015010 Date-13-01-2021 CS392 Data Structure Practical

Ashutosh Prasad Yadav
Btech (cse) – 3rd sem

Roll no.-191112015010
Date- 13-01-2021
CS392
Data Structure Practical
Q1>
#include <iostream>
using namespace std;
int stack[100], n=100, top=-1;
void pushtop(int val) {

if(top>=n-1)
cout<<"Stack Overflow"<<endl;
else {
top++;
stack[top]=val;
}
}
void poptop() {
if(top<=-1)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
}
void pushend(int val) {

if(top>=n-1)
cout<<"Stack Overflow"<<endl;
else {
for(int kl=top;kl>0;kl--)
stack[kl+1]=stack[kl];
top++;
stack[0]=val;
}
}
void popend()
{
for(int kl=0;kl<top;kl++)
stack[kl]=stack[kl+1];
top--;
}
void display() {
if(top>=0) {
cout<<"Stack elements are:";
for(int i=0; i<=top; i++)
cout<<stack[i]<<" ";
cout<<endl;
} else
cout<<"Stack is empty";
}
int main() {
int ch, val;
cout<<"1) Push in stack(top)"<<endl;
cout<<"2) Pop from stack(top)"<<endl;
cout<<"3) Push in stack(bottom)"<<endl;
cout<<"4) Pop from stack(bottom)"<<endl;
cout<<"5) Display stack"<<endl;
cout<<"6) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
case 1:
{
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
pushtop(val);
break;
}
case 2:
{
poptop();
break;
}
case 3:
{
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
pushend(val);
break;
}
case 4:
{
popend();
break;
}
case 5:
{
display();
break;
}
case 6:
{
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=6);
return 0;
}
Q2>
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* top = NULL;
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
}
void pop() {
if(top==NULL)
printf("Stack Underflow");
else {
printf("The popped element is %d\n",top->data);

top = top->next;
}
}
void display() {
struct Node* ptr;
if(top==NULL)
printf("stack is empty");
else {
ptr = top;
printf("Stack elements are: ");
while (ptr != NULL) {
printf("%d ",top->data);
ptr = ptr->next;
}
}
printf("\n");
}
int main() {
int ch, val;
printf("1) Push in stack\n");
printf("2) Pop from stack\n");
printf("3) Display stack\n");
printf("4) Exit\n");
do {
printf("Enter choice: ");
scanf("%d", &ch);
switch(ch) {
case 1: {
printf("Enter value to be pushed:\n");
scanf("%d", &val);
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
printf("Exit\n");
break;
}
default: {
printf("Invalid Choice\n");
}
}
}while(ch!=4);
return 0;
}
Q3>
#include<stdio.h>
#include <stdlib.h>
typedef struct node

{
int data;
struct node *left,*right;
int ht;
}
node;
node *insert(node *,int);

node *Delete(node *,int);
void preorder(node *);

void inorder(node *);
int height( node *);
node *rotateright(node *);

node *rotateleft(node *);
node *RR(node *);

node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);

node * insert(node *T,int x)
{
if(T==0)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
if(x > T->data)
{
T->right=insert(T->right,x);
if(BF(T)==-2)
{
if(x>T->right->data)
{
T=RR(T);
}
else
{
T=RL(T);
}
}
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
{
if(x < T->left->data)
{
T=LL(T);
}
else
{
T=LR(T);
}
}
}
T->ht=height(T);
return(T);
}
int height(node *T)

{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return(lh);
return(rh);
}
node * rotateright(node *x)
{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * RR(node *T)
{
T=rotateleft(T);
return(T);
}
node * LL(node *T)
{
T=rotateright(T);
return(T);
}
node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return(T);
}
node * RL(node *T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}
int BF(node *T)
{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
return(lh-rh);
}
void preorder(node *T)
{
if(T!=0)
{
printf("%d(Bf=%d)",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}}
int main()
{
node *root=NULL;
int x,n;
printf("\nEnter no. of elements:");
scanf("%d",&n);
printf("\nEnter tree data:");
root=NULL;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x); }
printf("\nPreorder sequence:\n");
preorder(root);
printf("\n");
return 0;}
Q4>
(i) Hashing is an important Data Structure which is designed to use a special function called
the Hash function which is used to map a given value with a particular key for faster access of
elements. The efficiency of mapping depends of the efficiency of the hash function used.
(ii) Minimum spanning tree - A minimum spanning tree (MST) or minimum weight spanning
tree is a subset of the edges of a connected, edge-weighted undirected graph that connects
all the vertices together, without any cycles and with the minimum possible total edge
weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More
generally, any edge-weighted undirected graph (not necessarily connected) has a minimum
spanning forest, which is a union of the minimum spanning trees for its connected
components.
(iii) Time Complexity of an algorithm is the representation of the amount of time required
by the algorithm to execute to completion. Time requirements can be denoted or defined as
a numerical function t(N), where t(N) can be measured as the number of steps, provided
each step takes constant time. The Big-O notation is a unit to express complexity in terms of
the size of the input that goes into an algorithm. Big – O notation is used to study the
performance / complexity of an algorithm in theoretical terms.

Ashutosh Prasad Yadav Btech (Cse) - 3 Sem Roll No.-191112015010 Date-13-01-2021 CS392 Data Structure Practical

Uploaded by

Copyright:

Available Formats

Ashutosh Prasad Yadav Btech (Cse) - 3 Sem Roll No.-191112015010 Date-13-01-2021 CS392 Data Structure Practical

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ashutosh Prasad Yadav Btech (Cse) - 3 Sem Roll No.-191112015010 Date-13-01-2021 CS392 Data Structure Practical

Uploaded by

Copyright:

Available Formats

Ashutosh Prasad Yadav

Btech (cse) – 3rd sem

void pushtop(int val) {

void pushend(int val) {

printf("The popped element is %d\n",top->data);

typedef struct node

node insert(node ,int);

void preorder(node *);

node rotateright(node );

node RR(node );

int BF(node *);

int height(node *T)

You might also like