DSL notes

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<stdio.h> #include<conio.h>  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;i<n;i++)
    printf("\n%d",a[i]);&nbsp;
for(i=0;i<n;i++)
{
    for(j=i+1;j<n;j++)
    {
        if(a[i]>a[j])
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
}&nbsp;
printf("\nSorted Array elements are");
for(i=0;i<n;i++)
    printf("\n %d",a[i]);&nbsp;
printf("\n enter the element to be searched");
scanf("%d",&key);&nbsp;
low=0;
high=n-1;
while(low<=high)
{
    mid=(low+high)/2;
    if(key==a[mid])
    {
        printf("\n key %d found succesfully at position %d",key,mid + 1);
        break;
    }
    else if(key<a[mid])
        high=mid-1;
    else
        low=mid+1;
}&nbsp;
if(low>high)
    printf("\n key %d not found",key);&nbsp;
getch();

} 2.Given (5,3,1,6,0,2,4} order the numbers in ascending order using Quick Sort. #include <stdio.h> 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<stdio.h> #include<conio.h> #include<stdlib.h> #include<alloc.h> 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 <stdio.h> #include <stdlib.h> 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<stdio.h>#include<conio.h>#include<alloc.h> 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<stdio.h> #include<conio.h> 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<conio.h> #include<stdlib.h> 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<stdio.h> #include<string.h> #include<conio.h> 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/(5z)+2 to its postfix expression. #include<stdio.h> #include<conio.h> #include<ctype.h> #include<string.h> #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<stdio.h> #include<conio.h> #include<math.h> #include<ctype.h> #include<string.h> #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<stdio.h> #include<conio.h> #include<alloc.h> 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<stdio.h> #include<conio.h> #include<alloc.h> 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<stdio.h> #include<conio.h> 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();}