1.Given {4,7,3,2,1,7,9,0}, find the location of 7 using Binary search and also display its first occurrence.
#include
#include
void main()
{
int a[10]={4,7,3,2,1,7,9,0};
int i, j, n, low, high, mid, temp, key;
n=8;
printf("\n Given Array elements are:\n");
for(i=0;ia[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("\nSorted Array elements are");
for(i=0;ihigh)
printf("\n key %d not found",key);
getch();
}
2.Given (5,3,1,6,0,2,4} order the numbers in ascending order using Quick Sort.
#include
void quick_sort(int a[], int lb, int ub) {
if (lb < ub) {
int key = a[lb], i = lb + 1, j = ub, temp;
while (i <= j) {
while (i <= ub && a[i] < key) i++;
while (j >= lb && a[j] > key) j--;
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
} else { break; } }
temp = a[lb];
a[lb] = a[j];
a[j] = temp;
quick_sort(a, lb, j - 1);
quick_sort(a, j + 1, ub);} }
int main() {
int i, n, a[20];
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements: ");
for (i = 0; i < n; i++) scanf("%d", &a[i]);
quick_sort(a, 0, n - 1);
printf("The sorted elements are: ");
for (i = 0; i < n; i++) printf("%4d", a[i]);
return 0;}
3.Perform the Merge Sort on the input {75,8,1,16,48,3,7,0} and display the output in descending order.
#include
#include
#include
#include void mergesort(int a[], int i, int j);
void merge(int a[], int i1, int j1, int i2, int j2);
int main()
{ int a[8]={75,8,1,16,48,3,7,0}, i; printf("Array elements are:");
for(i=0; i<8; i++)
printf("%d\t",a[i]);
mergesort(a, 0, 7);
printf("\nSorted array is :");
for(i=0; i<8; i++)
printf("%d\t",a[i]);
getch(); return 0; }
void mergesort(int a[], int i, int j)
{ int mid;
if(i < j)
{ mid = (i+j) / 2;
mergesort(a, i, mid);
mergesort(a, mid+1, j);
merge(a, i, mid, mid+1, j); } }
void merge(int a[], int i1, int j1, int i2, int j2)
{ int temp[50];
int i, j, k;
i = i1;
j = i2;
k = 0;
while(i <= j1 && j <= j2)
{ if(a[i] > a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++]; }
while(i <= j1)
temp[k++] = a[i++];
while(j <= j2)
temp[k++] = a[j++];
for(i = i1, j = 0; i <= j2; i++, j++)
a[i] = temp[j]; }
4. Write a program to insert the elements 61,16,8,27 into singly linked list and delete 8,61,27 from the list. Display your list after each insertion and deletion.
#include #include
typedef struct node {
int value;
struct node *next;
} DATA_NODE;
DATA_NODE *first_node = NULL;
void insert(int data) {
DATA_NODE *temp_node = (DATA_NODE *) malloc(sizeof (DATA_NODE));
temp_node->value = data;
temp_node->next = NULL;
if (first_node == NULL) {
first_node = temp_node;
} else {
DATA_NODE *head_node = first_node;
while (head_node->next != NULL) {
head_node = head_node->next; }
head_node->next = temp_node; } }
void delete(int pos) {
int countvalue = 0;
DATA_NODE *temp_node = first_node;
DATA_NODE *next_node;
while (temp_node != NULL) {
countvalue++;
temp_node = temp_node->next; }
if (pos > 0 && pos <= countvalue) {
temp_node = first_node;
if (pos == 1) {
first_node = temp_node->next;
free(temp_node);
} else { int i;
for (i = 1; i < pos - 1; i++) {
temp_node = temp_node->next; }
next_node = temp_node->next; temp_node->next = next_node->next;
free(next_node); }
} else {
printf("\nInvalid Position \n\n"); } }
void display() {
int count = 0;
DATA_NODE *temp_node = first_node;
printf("\nDisplay Linked List : \n");
while (temp_node != NULL) {
printf("# %d # ", temp_node->value);
count++;
temp_node = temp_node->next; }
printf("\nNo Of Items In Linked List : %d\n", count); } int main() {
int option = 0;
printf("Singly Linked List Example - All Operations\n");
while (option < 4) {
printf("\nOptions\n");
printf("1 : Insert into Linked List \n");
printf("2 : Delete from Linked List \n");
printf("3 : Display Linked List\n");
printf("Others : Exit()\n");
printf("Enter your option:");
scanf("%d", &option);
switch (option) {
case 1: {
int data;
printf("\nEnter Element for Insert Linked List : \n");
scanf("%d", &data);
insert(data);
display();
break; }
case 2: {
int pos;
printf("\nEnter Position for Delete Element : \n");
scanf("%d", &pos);
delete(pos);
display();
break; }
case 3:
display();
break;
default:
break; } }
return 0; }
6. Write a program to push 5,9,34,17,32 into stack and pop 3 times from the stack, also display the popped numbers.
#include#include#include
typedef struct stack {
int data;
struct stack *next; } S;
S *top = NULL;
void push() {
S temp = (S) malloc(sizeof(S));
printf("Enter the element: ");
scanf("%d", &temp->data);
temp->next = top;
top = temp;
printf("The %d element PUSHED successfully into the Stack\n", temp->data); }
void pop() {
S *temp = top;
if (top == NULL)
printf("Stack Underflow\n");
else {
top = top->next;
printf("Element deleted Is %d\n", temp->data);
free(temp);} }
void display() {
S *temp = top;
if (top == NULL)
printf("Stack is empty\n");
else {
printf("Elements in Stack are: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next; }
printf("\n"); } }
void main() {
int ch;
while (1) {
clrscr();
printf("1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\n");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch (ch) {
case 1: push(); break;
case 2: pop(); break;
case 3: display(); break;
case 4: exit(0); break;
default: printf("Invalid Choice\n"); }
getch(); } }
7. Write a recursive program to find GCD of 4,6,8.
#include
#include
int gcd(int x, int y) {
return (x == 0) ? y : gcd(y % x, x); }
void main() {
int a, b, c;
clrscr();
printf("Enter three numbers to find GCD of: ");
scanf("%d%d%d", &a, &b, &c);
if (a == 0 && b == 0 && c == 0) {
printf("Invalid number");
exit(0); }
printf("GCD of %d, %d and %d is: %d\n", a, b, c, gcd(c, gcd(a, b)));
getch(); }
8. Write a program to insert the elements (5,7,0,6,3,9} into circular queue and delete 6,9 & 5 from it(using linked list implementation).
#include
#include
struct node {
int data;
struct node* next;};
struct node *f = NULL;
struct node *r = NULL;
void enqueue(int d) {
struct node* n = (struct node*)malloc(sizeof(struct node));
n->data = d;
n->next = NULL;
if(f == NULL && r == NULL) {
f = r = n;
r->next = f;
} else {
r->next = n;
r = n;
n->next = f;} }
void dequeue() {
struct node* t = f;
if(f == NULL && r == NULL)
printf("\nQueue is Empty");
else if(f == r) {
f = r = NULL;
free(t);
} else {
f = f->next;
r->next = f;
free(t); } }
void print() {
struct node* t = f;
if(f == NULL && r == NULL)
printf("\nQueue is Empty");
else {
do {
printf("\n%d", t->data);
t = t->next;
} while(t!= f);} }
void main() {
int opt, n, i, data;
clrscr();
do {
printf("\n\n1 for Insert the Data in Queue\n2 for show the Data in Queue \n3 for Delete the data from the Queue\n0 for Exit");
scanf("%d", &opt);
switch(opt) {
case 1:
printf("\nEnter the number of data");
scanf("%d", &n);
printf("\nEnter your data");
for(i = 0; i < n; i++) {
scanf("%d", &data);
enqueue(data); }
break;
case 2:
print();
break;
case 3:
dequeue();
break;
case 0:
break;
default:
printf("\nIncorrect Choice"); }
} while(opt!= 0);
getch(); }
9. Given S1="Flowers", S2="are beautiful"
a. Find the length of S1.
b. Concatenate S1 and S2.
c. Extract the substring "low" from S1.
d. Find "are" in S2 and replace it with "is".
#include
#include
#include
void replaceSubstring(char [], char [], char []);
void main() {
char string1[50] = "flowers", string2[50] = "are beautiful", sub[30] = "low", replace_str[30] = "are", new_str[50] = "is";
clrscr();
printf("\nLength of string 1 is :%d", strlen(string1));
printf("\nConcatenation of two strings : %s", strcat(string1, string2));
printf("\nSubstring %s found at loc %d", sub, strstr(string1, sub) - string1);
replaceSubstring(string2, replace_str, new_str);
printf("\nThe string after replacing : %s\n", string2);
getch(); }
void replaceSubstring(char string[], char sub[], char new_str[]) {
int stringLen, subLen, newLen, i, j, k, flag, start, end;
stringLen = strlen(string);
subLen = strlen(sub);
newLen = strlen(new_str);
for(i = 0; i < stringLen; i++) {
flag = 0;
start = i;
for(j = 0; string[i] == sub[j]; j++, i++)
if(j == subLen - 1)
flag = 1;
end = i;
if(flag == 0)
i -= j;
else {
for(j = start; j < end; j++) {
for(k = start; k < stringLen; k++)
string[k] = string[k + 1];
stringLen--;
i--; }
for(j = start; j < start + newLen; j++) {
for(k = stringLen; k >= j; k--)
string[k + 1] = string[k];
string[j] = new_str[j - start];
stringLen++;
i++;}}}}
10. Write a program to convert an infix expression X^y/(5*z)+2 to its postfix expression.
#include
#include
#include
#include
#define max 20
char s[max];
int top = 0;
void push(char element);
int pop();
int preced(char element);
void main() {
int i, j = 0;
char ch, infix[max], post[max];
clrscr();
printf("\nEnter a valid infix Expression: ");
scanf("%s", infix);
push('#');
for(i = 0; i < strlen(infix); i++) {
ch = infix[i];
if(isalnum(ch))
post[j++] = ch;
else {
if(ch == '(')
push(ch);
else if(ch == ')') {
while(s[top] != '(')
post[j++] = pop();
pop();
} else {
while(preced(s[top]) >= preced(ch))
post[j++] = pop();
push(ch); } } }
while(s[top] != '#')
post[j++] = pop();
post[j] = '\0';
printf("\n\tResultant postfix Expression is: %s\n", post);
getch(); }
int preced(char element) {
switch(element) {
case '+':
case '-': return 1;
case '*':
case '/': return 2;
case '^': return 3;
case '(':
case '#': return 0; }
return 0; }
void push(char element) {
s[++top] = element; }
int pop() {
return s[top--]; }
11.Write a program to evaluate a postfix expression 53+2-.
#include
#include
#include
#include
#include
#define max 20
int a[max], top = 0;
void push(int element);
int pop();
void main() {
char posfix[max], ch;
int i, op1, op2, res;
clrscr();
printf("\n\t\tProgram to Evaluate postfix Expression.");
printf("\n\t\t~~~~~~~~~~~~~~");
printf("\nEnter the postfix expression: ");
scanf("%s", posfix);
for(i = 0; i < strlen(posfix); i++) {
ch = posfix[i];
if(isdigit(ch))
push(ch - '0');
else {
op2 = pop();
op1 = pop();
switch(ch) {
case '+': res = op1 + op2; break;
case '-': res = op1 - op2; break;
case '*': res = op1 * op2; break;
case '/': res = op1 / op2; break;
case '^': res = (int)pow(op1, op2); break;
default: printf("\nEnter the valid option: "); }
push(res); } }
printf("Result of above expression is: %d\n", pop());
getch(); }
void push(int element) {
a[++top] = element;}
int pop() {
return a[top--]; }
12. Write a program to create a binary tree with the elements 18,15,40,50,30,17,41 after creation insert 45 and 19 into tree and delete 15,17 and 41 from tree. Display the tree on each insertion and deletion operation.
#include
#include
#include
struct node {
int data;
struct node *left, *right; };
struct node *root = NULL;
void insert(int x) {
struct node *p, *previous, *current;
p = (struct node *)malloc(sizeof(struct node));
if(p == NULL) {
printf("\n Out of memory");
return; }
p->data = x;
p->left = NULL;
p->right = NULL;
if(root == NULL) {
root = p;
return; }
previous = NULL;
current = root;
while(current != NULL) {
previous = current;
if(p->data < current->data)
current = current->left;
else
current = current->right; }
if(p->data < previous->data)
previous->left = p;
else
previous->right = p; }
void inorder(struct node *t) {
if(t != NULL) {
inorder(t->left);
printf("\n %5d", t->data);
inorder(t->right);} }
void del(int x) {
struct node *ptr = root, *parent = NULL;
while(ptr != NULL && ptr->data != x) {
parent = ptr;
if(x < ptr->data)
ptr = ptr->left;
else
ptr = ptr->right; }
if(ptr == NULL) {
printf("\n Delete element not found");
return; }
if(ptr->left == NULL && ptr->right == NULL) {
if(parent == NULL)
root = NULL;
else if(parent->left == ptr)
parent->left = NULL;
else
parent->right = NULL;
} else if(ptr->left == NULL) {
if(parent == NULL)
root = ptr->right;
else if(parent->left == ptr)
parent->left = ptr->right;
else
parent->right = ptr->right;
} else if(ptr->right == NULL) {
if(parent == NULL)
root = ptr->left;
else if(parent->left == ptr)
parent->left = ptr->left;
else
parent->right = ptr->left;
} else {
struct node *temp = ptr, *t = ptr->right;
while(t->left != NULL)
t = t->left;
ptr->data = t->data;
if(t->right != NULL)
temp->right = t->right;
else
temp->right = NULL;}
free(ptr);}
void main() {
int op, n, srchno;
clrscr();
do {
printf("\n 1.Insertion");
printf("\n 2.Deletion");
printf("\n 3.Inorder");
printf("\n 4.Quit");
printf("\n Enter your choice\n");
scanf("%d", &op);
switch(op) {
case 1: printf("\n Enter the element to insert\n");
scanf("%d", &n);
insert(n);
break;
case 2: printf("\n Enter the element to be deleted\n");
scanf("%d", &srchno);
del(srchno);
break;
case 3: printf("\n The inorder elements are\n");
inorder(root);
getch();
break;
default: exit(0);}
} while(op < 4);
getch();}
13.Write a program to create binary search tree with the elements {2,5,1,3,9,0,6) and perform inorder, preorder and post order traversal.
#include
#include
#include
struct bst {
int info;
struct bst *right, *left; };
typedef struct bst *NODEPTR;
NODEPTR create(NODEPTR, int);
void preorder(NODEPTR);
void postorder(NODEPTR);
void inorder(NODEPTR);
void main() {
int ch, item;
NODEPTR root = NULL;
for(;;) {
clrscr();
printf("\nOperations on Binary Search Tree\n");
printf("----------------------------------\n");
printf("1. Create Binary Search Tree\n");
printf("2. Preorder Traversal\n");
printf("3. Postorder Traversal\n");
printf("4. Inorder Traversal\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch(ch) {
case 1: printf("Enter item to be inserted: ");
scanf("%d", &item);
root = create(root, item);
break;
case 2: printf("\nPreorder Traversal: ");
preorder(root);
break;
case 3: printf("\nPostorder Traversal: ");
postorder(root);
break;
case 4: printf("\nInorder Traversal: ");
inorder(root);
break;
case 5: exit(1);
default: printf("\nInvalid choice"); }
printf("\n\nPress any key to continue....");
getch(); } }
NODEPTR create(NODEPTR root, int item) {
NODEPTR p;
if(root != NULL) {
if(item < root->info)
root->left = create(root->left, item);
else
root->right = create(root->right, item);
return root;
} else {
p = (NODEPTR)malloc(sizeof(struct bst));
p->info = item;
p->left = p->right = NULL;
return p;}}
void preorder(NODEPTR root) {
if(root != NULL) {
printf("%d ", root->info);
preorder(root->left);
preorder(root->right);}}
void postorder(NODEPTR root) {
if(root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->info);}}
void inorder(NODEPTR root) {
if(root != NULL) {
inorder(root->left);
printf("%d ", root->info);
inorder(root->right);}}
14. Write a program to sort the following elements using heap sort (9,16,32,8,4,1,5,8,0}.
#include
#include
void heap(int a[], int n) {
int i, k, item;
for(k = 1; k < n; k++) {
item = a[k];
i = k;
while(i > 0 && item > a[(i - 1) / 2]) {
a[i] = a[(i - 1) / 2];
i = (i - 1) / 2; }
a[i] = item;}}
void adjust(int a[], int n) {
int i, j, item;
j = 0;
item = a[j];
i = 2 * j + 1;
while(i <= n - 1) {
if(i + 1 <= n - 1 && a[i] < a[i + 1]) i++;
if(item < a[i]) {
a[j] = a[i];
j = i;
i = 2 * j + 1;
} else break;}
a[j] = item;}
void heapsort(int a[], int n) {
int i, temp;
heap(a, n);
for(i = n - 1; i > 0; i--) {
temp = a[0];
a[0] = a[i];
a[i] = temp;
adjust(a, i);} }
void main() {
int a[20], i, n;
clrscr();
printf("\nEnter number of elements to sort: ");
scanf("%d", &n);
printf("\nEnter the elements: ");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
heapsort(a, n);
printf("\nThe sorted List: ");
for(i = 0; i < n; i++)
printf("%d ", a[i]);
getch();}