Programming using C

Session 1 & 2: Arrays: -------------- Q. Multiplication of matrics: #include #include int main() { int a[10][10],b[10][10],mul[10][10],r1,c1,r2,c2,i,j,k; printf("Enter matric size which fulfills the matric product condition:\n"); printf("*************************:\n"); printf("Enter First matric size : \n"); printf("No. of row="); scanf("%d",&r1); printf("No. of column="); scanf("%d",&c1); printf("Input first matrix elements, horizontally as 00, 01, 02 and so on:\n"); for(i=0;i #include main(){ int i,j,n; char str[100][100],s[100]; printf("Enter number of names : "); scanf("%d",&n); printf("Enter names in any order: "); for(i=0;i0){ strcpy(s,str[i]); strcpy(str[i],str[j]); strcpy(str[j],s); } } } printf(" The sorted order of names are: "); for(i=0;i int main() { char str[80], search[10]; int count1 = 0, count2 = 0, i, j, flag; printf("Enter a string:"); gets(str); printf("Enter search substring:"); gets(search); while (str[count1] != '\0') count1++; while (search[count2] != '\0') count2++; for (i = 0; i <= count1 - count2; i++) { for (j = i; j < i + count2; j++) { flag = 1; if (str[j] != search[j - i]) { flag = 0; break; } } if (flag == 1) break; } if (flag == 1) printf("SEARCH SUCCESSFUL!"); else printf("SEARCH UNSUCCESSFUL!"); return 0; } 4. // C Program to concatenate two // strings without using strcat #include int main() { // Get the two Strings to be concatenated char str1[100] = "Geeks", str2[100] = "World"; // Declare a new Strings // to store the concatenated String char str3[100]; int i = 0, j = 0; printf("\nFirst string: %s", str1); printf("\nSecond string: %s", str2); // Insert the first string // in the new string while (str1[i] != '\0') { str3[j] = str1[i]; i++; j++; } // Insert the second string // in the new string i = 0; while (str2[i] != '\0') { str3[j] = str2[i]; i++; j++; } str3[j] = '\0'; // Print the concatenated string printf("\nConcatenated string: %s", str3); return 0; } Session 3 & 4- Structures: ------------ Q. Read Records of n Students & Sort Marks in Ascending Order #include /* Declaration of structure */ struct student { char name[30]; int roll; float marks; }; int main() { /* Declaration of array of structure */ struct student s[20], temp; int i,j,n; printf("Enter n:\n"); scanf("%d",&n); for(i=0;i< n;i++) { printf("Enter name, roll and marks of student:\n"); scanf("%s%d%f",s[i].name, &s[i].roll, &s[i].marks); } for(i=0;i< n-1;i++) { for(j=i+1;j< n;j++) { if(s[i].marks>s[j].marks) { temp = s[i]; s[i] = s[j]; s[j] = temp; } } } printf("Sorted records are:\n"); for(i=0;i< n;i++) { printf("Name: %s\n", s[i].name); printf("Roll: %d\n", s[i].roll); printf("Marks: %0.2f\n\n", s[i].marks); } return 0; } Q. Multiplication of two sparse matrices: struct matrix { int row; //To store row no. int col; //To store col no int value; // element value }; // Print the sparse matrix void printMatrix(matrix a[100], int k) { for (int i=0; i b.row) { return false; } if (a.col < b.col) { return true; } return false; } // Transpose of a sparse Matrix void transpose(matrix a[100], matrix b[100], int row,int col, int n) { for (int i=0;i #include #include int main() { char str[100], word[20]; int i, j, ls, lw, temp, countW=0, chk; printf("Enter the String: "); gets(str); printf("Enter a Word: "); gets(word); ls = strlen(str); lw = strlen(word); for(i=0; i #include void main() { int count = 0, c = 0, i, j = 0, k, space = 0; char str[100], p[50][100], str1[20], ptr1[50][100]; char *ptr; printf("Enter the string\n"); scanf(" %[^\n]s", str); for (i = 0;i %d times\n", ptr1[i], c); c = 0; } } Session 5 & 6 : Linked List: --------------- Q. Code of deletion in a Singly linked list (For a Value) #include #include struct Node { int data; struct Node *next; }; void delete (struct Node **head, int delVal) { struct Node *temp = *head; struct Node *previous; //Case when there is only 1 node in the list if (temp->next == NULL) { *head = NULL; free (temp); printf ("Value %d, deleted \n", delVal); return; } //if the head node itself needs to be deleted if (temp != NULL && temp->data == delVal) { //Case 1 head becomes 30 *head = temp->next; //changing head to next in the list printf ("Value %d, deleted \n", delVal); //case 1: 22 deleted and freed free (temp); return; } //run until we find the value to be deleted in the list while (temp != NULL && temp->data != delVal) { //store previous link node as we need to change its next val previous = temp; temp = temp->next; } //if value is not present then //temp will have traversed to last node NULL if (temp == NULL) { printf ("Value not found\n"); return; } // Case 2: (24)->next = 16 (as 20->next = 16) // Case 3: (16)->next = NULL (as 12->next = NULL) previous->next = temp->next; free (temp); //case 2: 20 deleted and freed //case 3: 12 deleted and freed printf ("Value %d, deleted \n", delVal); } void display (struct Node *node) { //as linked list will end when Node is Null while (node != NULL) { printf ("%d ", node->data); node = node->next; } printf ("\n"); } int main () { //creating 4 pointers of type struct Node //So these can point to address of struct type variable struct Node *head = NULL; struct Node *node2 = NULL; struct Node *node3 = NULL; struct Node *node4 = NULL; struct Node *node5 = NULL; struct Node *node6 = NULL; // allocate 3 nodes in the heap head = (struct Node *) malloc (sizeof (struct Node)); node2 = (struct Node *) malloc (sizeof (struct Node)); node3 = (struct Node *) malloc (sizeof (struct Node)); node4 = (struct Node *) malloc (sizeof (struct Node)); node5 = (struct Node *) malloc (sizeof (struct Node)); node6 = (struct Node *) malloc (sizeof (struct Node)); head->data = 22; // data set for head node head->next = node2; // next pointer assigned to address of node2 node2->data = 30; node2->next = node3; node3->data = 24; node3->next = node4; node4->data = 20; node4->next = node5; node5->data = 16; node5->next = node6; node6->data = 12; node6->next = NULL; /*No need for & i.e. address as we do not need to change head address */ printf ("Linked List Before Operations : "); display (head); //deleting first occurance of a value in linked list delete (&head, 22); delete (&head, 20); delete (&head, 12); printf ("Linked List After Operations : "); display (head); return 0; } Q. Code for Deletion in a Doubly Linked List #include #include struct Node { int data; struct Node *next; struct Node *prev; }; int getLength (struct Node *node); void insert (struct Node **head, int data) { struct Node *freshNode = (struct Node *) malloc (sizeof (struct Node)); freshNode->data = data; freshNode->next = *head; freshNode->prev = NULL; // If the linked list already had atleast 1 node if (*head != NULL) (*head)->prev = freshNode; // freshNode will become head *head = freshNode; } void deleteFront (struct Node **head) { struct Node *tempNode = *head; // if DLL is empty if (*head == NULL) { printf ("Linked List Empty, nothing to delete\n"); return; } // if Linked List has only 1 node if (tempNode->next == NULL) { printf ("%d deleted\n", tempNode->data); *head = NULL; return; } // move head to next node *head = (*head)->next; // assign head node's previous to NULL (*head)->prev = NULL; printf ("%d deleted\n", tempNode->data); free (tempNode); } void deleteEnd (struct Node **head) { struct Node *tempNode = *head; // if DLL is empty if (*head == NULL) { printf ("Linked List Empty, nothing to delete\n"); return; } // if Linked List has only 1 node if (tempNode->next == NULL) { printf ("%d deleted\n", tempNode->data); *head = NULL; return; } // else traverse to the last node while (tempNode->next != NULL) tempNode = tempNode->next; struct Node *secondLast = tempNode->prev; // Curr assign 2nd last node's next to Null secondLast->next = NULL; printf ("%d deleted\n", tempNode->data); free (tempNode); } void deleteNthNode (struct Node **head, int n) { //if the head node itself needs to be deleted int len = getLength (*head); // not valid if (n < 1 || n > len) { printf ("Enter valid position\n"); return; } // delete the first node if (n == 1) { deleteFront (head); return; } if (n == len) { deleteEnd (head); return; } struct Node *tempNode = *head; // traverse to the nth node while (--n) { tempNode = tempNode->next; } struct Node *previousNode = tempNode->prev; // (n-1)th node struct Node *nextNode = tempNode->next; // (n+1)th node // assigning (n-1)th node's next pointer to (n+1)th node previousNode->next = tempNode->next; // assigning (n+1)th node's previous pointer to (n-1)th node nextNode->prev = tempNode->prev; // deleting nth node printf ("%d deleted \n", tempNode->data); free (tempNode); } // required for deleteNthNode int getLength (struct Node *node) { int len = 0; while (node != NULL) { node = node->next; len++; } return len; } //function to print the doubly linked list void display (struct Node *node) { struct Node *end = NULL; printf ("List in Forward direction: "); while (node != NULL) { printf (" %d ", node->data); end = node; node = node->next; } printf ("\nList in backward direction:"); while (end != NULL) { printf (" %d ", end->data); end = end->prev; } printf ("\n\n"); } int main () { struct Node *head = NULL; insert (&head, 7); insert (&head, 8); insert (&head, 9); insert (&head, 10); insert (&head, 11); insert (&head, 12); display (head); deleteFront (&head); display (head); deleteEnd (&head); display (head); // delete 3rd node deleteNthNode (&head, 3); display (head); // delete 1st node deleteNthNode (&head, 1); display (head); // delete 1st node deleteEnd (&head); display (head); return 0; } Q. C Program For Deletion in Circular Linked List #include #include // structure for Circular Linked List struct Node { int data; struct Node *next; }; void deleteBegin(struct Node **head) { struct Node *tempNode = *head; // if there are no nodes in Linked List can't delete if (*head == NULL) { printf ("Linked List Empty, nothing to delete"); return; } // if only 1 node in CLL if (tempNode->next == *head) { *head = NULL; return; } struct Node *curr = *head; // traverse till last node in CLL while (curr->next != *head) curr = curr->next; // assign last node's next to 2nd node in CLL curr->next = (*head)->next; // move head to next node *head = (*head)->next; free (tempNode); } void insert (struct Node **head, int data) { struct Node *newNode = (struct Node *) malloc (sizeof (struct Node)); newNode->data = data; if (*head == NULL) { *head = newNode; (*head)->next = *head; return; } struct Node *curr = *head; while (curr->next != *head) { curr = curr->next; } curr->next = newNode; newNode->next = *head; *head = newNode; } void display (struct Node *head) { // if there are no node in CLL if (head == NULL) return; struct Node *temp = head; //need to take care of circular structure of CLL do { printf ("%d ", temp->data); temp = temp->next; } while (temp != head); printf ("\n"); } int main () { // first node will be null at creation struct Node *head = NULL; insert (&head, 10); insert (&head, 11); insert (&head, 12); insert (&head, 13); insert (&head, 14); insert (&head, 15); insert (&head, 16); display (head); deleteBegin(&head); display (head); return 0; } Q. Intersection of two sorted linked lists #include #include /* Link list node */ struct Node { int data; struct Node* next; }; void push(struct Node** head_ref, int new_data); /*This solution uses the temporary dummy to build up the result list */ struct Node* sortedIntersect( struct Node* a, struct Node* b) { struct Node dummy; struct Node* tail = &dummy; dummy.next = NULL; /* Once one or the other list runs out -- we're done */ while (a != NULL && b != NULL) { if (a->data == b->data) { push((&tail->next), a->data); tail = tail->next; a = a->next; b = b->next; } /* advance the smaller list */ else if (a->data < b->data) a = a->next; else b = b->next; } return (dummy.next); } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the linked list */ void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = (struct Node*)malloc( sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(struct Node* node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty lists */ struct Node* a = NULL; struct Node* b = NULL; struct Node* intersect = NULL; /* Let us create the first sorted linked list to test the functions Created linked list will be 1->2->3->4->5->6 */ push(&a, 6); push(&a, 5); push(&a, 4); push(&a, 3); push(&a, 2); push(&a, 1); /* Let us create the second sorted linked list Created linked list will be 2->4->6->8 */ push(&b, 8); push(&b, 6); push(&b, 4); push(&b, 2); /* Find the intersection two linked lists */ intersect = sortedIntersect(a, b); printf("\n Linked list containing common items of a & b \n "); printList(intersect); getchar(); } Q. Sorting a list: #include #include struct node { int data; struct node* next; }; struct node* head = NULL; struct node* sorted = NULL; void push(int val) { /* allocate node */ struct node* newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = val; /* link the old list off the new node */ newnode->next = head; /* move the head to point to the new node */ head = newnode; } void sortedInsert(struct node* newnode) { /* Special case for the head end */ if (sorted == NULL || sorted->data >= newnode->data) { newnode->next = sorted; sorted = newnode; } else { struct node* current = sorted; /* Locate the node before the point of insertion */ while (current->next != NULL && current->next->data < newnode->data) { current = current->next; } newnode->next = current->next; current->next = newnode; } } // function to sort a singly linked list // using insertion sort void insertionsort() { struct node* current = head; // Traverse the given linked list and insert every // node to sorted while (current != NULL) { // Store next for next iteration struct node* next = current->next; // insert current in sorted linked list sortedInsert(current); // Update current current = next; } // Update head to point to sorted linked list head = sorted; } /* Function to print linked list */ void printlist(struct node* head) { while (head != NULL) { printf("%d->", head->data); head = head->next; } printf("NULL"); } // Driver program to test above functions int main() { push(5); push(20); push(4); push(3); push(30); printf("Linked List before sorting:\n"); printlist(head); printf("\n"); insertionsort(head); printf("Linked List after sorting:\n"); printlist(head); } Q. C Program to insert an element in a Sorted Linked List // Linked List in C Implementation code #include #include //stdlib is included because we will be using 'malloc' // creating a node in linked list struct Node { int data; struct Node *next; // Pointer pointing towards next node }; //function to print the linked list void display (struct Node *node) { while (node != NULL) { printf ("%d ", node->data); node = node->next; } } struct Node *newNode (int data) { struct Node *newNode = (struct Node *) malloc (sizeof (struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } //function to insert data in sorted position void insertion_sort (struct Node **head, struct Node *newNode) { //If linked list is empty if (*head == NULL || (*head)->data >= newNode->data) { newNode->next = *head; *head = newNode; return; } //Locate the node before insertion struct Node *current = *head; while (current->next != NULL && current->next->data < newNode->data) current = current->next; newNode->next = current->next; current->next = newNode; } // main function int main () { int k; //creating 4 pointers of type struct Node //So these can point to address of struct type variable struct Node *head = NULL; struct Node *node2 = NULL; struct Node *node3 = NULL; // allocate 3 nodes in the heap head = (struct Node *) malloc (sizeof (struct Node)); node2 = (struct Node *) malloc (sizeof (struct Node)); node3 = (struct Node *) malloc (sizeof (struct Node)); head->data = 10; // data set for head node head->next = node2; // next pointer assigned to address of node2 node2->data = 15; node2->next = node3; node3->data = 20; node3->next = NULL; printf ("Linked list before insertion : "); display (head); printf ("\nEnter data you want to insert: "); scanf ("%d", &k); insertion_sort (&head, newNode (k)); printf ("Linked list after insertion : "); display (head); return 0; } Q. Skiplist implemetation in C. /* Skip Lists: A Probabilistic Alternative to Balanced Trees */ #include #include #include #define SKIPLIST_MAX_LEVEL 6 typedef struct snode { int key; int value; struct snode **forward; } snode; typedef struct skiplist { int level; int size; struct snode *header; } skiplist; skiplist *skiplist_init(skiplist *list) { int i; snode *header = (snode *) malloc(sizeof(struct snode)); list->header = header; header->key = INT_MAX; header->forward = (snode **) malloc( sizeof(snode*) * (SKIPLIST_MAX_LEVEL + 1)); for (i = 0; i <= SKIPLIST_MAX_LEVEL; i++) { header->forward[i] = list->header; } list->level = 1; list->size = 0; return list; } static int rand_level() { int level = 1; while (rand() < RAND_MAX / 2 && level < SKIPLIST_MAX_LEVEL) level++; return level; } int skiplist_insert(skiplist *list, int key, int value) { snode *update[SKIPLIST_MAX_LEVEL + 1]; snode *x = list->header; int i, level; for (i = list->level; i >= 1; i--) { while (x->forward[i]->key < key) x = x->forward[i]; update[i] = x; } x = x->forward[1]; if (key == x->key) { x->value = value; return 0; } else { level = rand_level(); if (level > list->level) { for (i = list->level + 1; i <= level; i++) { update[i] = list->header; } list->level = level; } x = (snode *) malloc(sizeof(snode)); x->key = key; x->value = value; x->forward = (snode **) malloc(sizeof(snode*) * (level + 1)); for (i = 1; i <= level; i++) { x->forward[i] = update[i]->forward[i]; update[i]->forward[i] = x; } } return 0; } snode *skiplist_search(skiplist *list, int key) { snode *x = list->header; int i; for (i = list->level; i >= 1; i--) { while (x->forward[i]->key < key) x = x->forward[i]; } if (x->forward[1]->key == key) { return x->forward[1]; } else { return NULL; } return NULL; } static void skiplist_node_free(snode *x) { if (x) { free(x->forward); free(x); } } int skiplist_delete(skiplist *list, int key) { int i; snode *update[SKIPLIST_MAX_LEVEL + 1]; snode *x = list->header; for (i = list->level; i >= 1; i--) { while (x->forward[i]->key < key) x = x->forward[i]; update[i] = x; } x = x->forward[1]; if (x->key == key) { for (i = 1; i <= list->level; i++) { if (update[i]->forward[i] != x) break; update[i]->forward[1] = x->forward[i]; } skiplist_node_free(x); while (list->level > 1 && list->header->forward[list->level] == list->header) list->level--; return 0; } return 1; } static void skiplist_dump(skiplist *list) { snode *x = list->header; while (x && x->forward[1] != list->header) { printf("%d[%d]->", x->forward[1]->key, x->forward[1]->value); x = x->forward[1]; } printf("NIL\n"); } int main() { int arr[] = { 3, 6, 9, 2, 11, 1, 4 }, i; skiplist list; skiplist_init(&list); printf("Insert:--------------------\n"); for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { skiplist_insert(&list, arr[i], arr[i]); } skiplist_dump(&list); printf("Search:--------------------\n"); int keys[] = { 3, 4, 7, 10, 111 }; for (i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) { snode *x = skiplist_search(&list, keys[i]); if (x) { printf("key = %d, value = %d\n", keys[i], x->value); } else { printf("key = %d, not fuound\n", keys[i]); } } printf("Search:--------------------\n"); skiplist_delete(&list, 3); skiplist_delete(&list, 9); skiplist_dump(&list); return 0; } Session 7 & 8 - Stacks: ------------------ Q. Prefix to postfix expression using pointers: #include #include char stack[50][50]; int top = -1; void clear_stack() { top = -1 ; } void push(char *s) { strcpy(stack[++top], s) ; } char* pop() { return stack[top--]; } int is_operator(char x) { if(x == '+' ||x == '-'||x == '*'||x == '/'){ return 1; } else{ return 0; } } //function to Convert prefix to Postfix void convert(char *exp) { clear_stack() ; int i,l; char op1[50],op2[50]; l = strlen(exp); //scanning from right to left for(i = l - 1; i >= 0; i--) { //checking if the symbol is an operator if (is_operator(exp[i])) { //popping two operands from stack strcpy(op1, pop()) ; strcpy(op2, pop()) ;; //concating the operands and operator strcat(op1 , strcat(op2 , (char[2]) {(char)exp[i], '\0'})) ; //Pushing the temporary string to stack push(op1); } //if it is an operand else { //push the operand to the stack push((char[2]){(char)exp[i], '\0'}); } } //printf("The postfix expression is: %s",stack[top].c_str()); printf("%s\n",stack[top]); } //main function int main() { convert("*-A/BC-/AKL"); convert("+ab"); convert("*+abc"); convert("*a+bc"); convert("+/ab/cd"); convert("*+ab+cd"); convert("-*+abcd"); return 0; } Output : Prefix expression : *-a/bc-/ade Postfix expression : abc/-ad/e-* Q. Reverse an input string using stack. #include #include #define max 100 int top,stack[max]; void push(char x){ // Push(Inserting Element in stack) operation if(top == max-1){ printf("stack overflow"); } else { stack[++top]=x; } } void pop(){ // Pop (Removing element from stack) printf("%c",stack[top--]); } main() { char str[]="sri lanka"; int len = strlen(str); int i; for(i=0;i int stack[100],choice,n,top,x,i; void push(void); void pop(void); void display(void); int main() { top=-1; printf("\n Enter the size of STACK[MAX=100]:"); scanf("%d",&n); printf("\n\t STACK OPERATIONS USING ARRAY"); printf("\n\t--------------------------------"); printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT"); do { printf("\n Enter the Choice:"); scanf("%d",&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf("\n\t EXIT POINT "); break; } default: { printf ("\n\t Please Enter a Valid Choice(1/2/3/4)"); } } } while(choice!=4); return 0; } void push() { if(top>=n-1) { printf("\n\tSTACK is over flow"); } else { printf(" Enter a value to be pushed:"); scanf("%d",&x); top++; stack[top]=x; } } void pop() { if(top<=-1) { printf("\n\t Stack is under flow"); } else { printf("\n\t The popped elements is %d",stack[top]); top--; } } void display() { if(top>=0) { printf("\n The elements in STACK \n"); for(i=top; i>=0; i--) printf("\n%d",stack[i]); printf("\n Press Next Choice"); } else { printf("\n The STACK is empty"); } } Output: Enter the size of STACK[MAX=100]:10 STACK OPERATIONS USING ARRAY -------------------------------- 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter the Choice:1 Enter a value to be pushed:12 Enter the Choice:1 Enter a value to be pushed:24 Enter the Choice:1 Enter a value to be pushed:98 Enter the Choice:3 The elements in STACK 98 24 12 Press Next Choice Enter the Choice:2 The popped elements is 98 Enter the Choice:3 The elements in STACK 24 12 Press Next Choice Enter the Choice:4 EXIT POINT Q. Implementation of a Stack using a Linked List #include #include struct Node { int data; struct Node *next; }; struct Node *head = NULL; void push(int val) { //create new node struct Node *newNode = malloc(sizeof(struct Node)); newNode->data = val; //make the new node points to the head node newNode->next = head; //make the new node as head node //so that head will always point the last inserted data head = newNode; } void pop() { //temp is used to free the head node struct Node *temp; if(head == NULL) printf("Stack is Empty\n"); else { printf("Poped element = %d\n", head->data); //backup the head node temp = head; //make the head node points to the next node. //logically removing the node head = head->next; //free the poped element's memory free(temp); } } //print the linked list void display() { struct Node *temp = head; //iterate the entire linked list and print the data while(temp != NULL) { printf("%d->", temp->data); temp = temp->next; } printf("NULL\n"); } int main() { push(10); push(20); push(30); printf("Linked List\n"); display(); pop(); printf("After the pop, the new linked list\n"); display(); pop(); printf("After the pop, the new linked list\n"); display(); return 0; } Output: Linked List 30->20->10->NULL Poped element = 30 After the pop, the new linked list 20->10->NULL Poped element = 20 After the pop, the new linked list 10->NULL Q. Implement multiple stack in a single array: //This is a C Program to Implement two Stacks using a Single Array & Check for Overflow & Underflow #include #define SIZE 10 int ar[SIZE]; int top1 = -1; int top2 = SIZE; //Functions to push data void push_stack1 (int data) { if (top1 < top2 - 1) { ar[++top1] = data; } else { printf ("Stack Full! Cannot Push\n"); } } void push_stack2 (int data) { if (top1 < top2 - 1) { ar[--top2] = data; } else { printf ("Stack Full! Cannot Push\n"); } } //Functions to pop data void pop_stack1 () { if (top1 >= 0) { int popped_value = ar[top1--]; printf ("%d is being popped from Stack 1\n", popped_value); } else { printf ("Stack Empty! Cannot Pop\n"); } } void pop_stack2 () { if (top2 < SIZE) { int popped_value = ar[top2++]; printf ("%d is being popped from Stack 2\n", popped_value); } else { printf ("Stack Empty! Cannot Pop\n"); } } //Functions to Print Stack 1 and Stack 2 void print_stack1 () { int i; for (i = top1; i >= 0; --i) { printf ("%d ", ar[i]); } printf ("\n"); } void print_stack2 () { int i; for (i = top2; i < SIZE; ++i) { printf ("%d ", ar[i]); } printf ("\n"); } int main() { int ar[SIZE]; int i; int num_of_ele; printf ("We can push a total of 10 values\n"); //Number of elements pushed in stack 1 is 6 //Number of elements pushed in stack 2 is 4 for (i = 1; i <= 6; ++i) { push_stack1 (i); printf ("Value Pushed in Stack 1 is %d\n", i); } for (i = 1; i <= 4; ++i) { push_stack2 (i); printf ("Value Pushed in Stack 2 is %d\n", i); } //Print Both Stacks print_stack1 (); print_stack2 (); //Pushing on Stack Full printf ("Pushing Value in Stack 1 is %d\n", 11); push_stack1 (11); //Popping All Elements From Stack 1 num_of_ele = top1 + 1; while (num_of_ele) { pop_stack1 (); --num_of_ele; } //Trying to Pop From Empty Stack pop_stack1 (); return 0; } Output: gcc TwoStacksSingleArray.c ./a.out We can push a total of 10 values Value Pushed in Stack 1 is 1 Value Pushed in Stack 1 is 2 Value Pushed in Stack 1 is 3 Value Pushed in Stack 1 is 4 Value Pushed in Stack 1 is 5 Value Pushed in Stack 1 is 6 Value Pushed in Stack 2 is 1 Value Pushed in Stack 2 is 2 Value Pushed in Stack 2 is 3 Value Pushed in Stack 2 is 4 6 5 4 3 2 1 4 3 2 1 Pushing Value in Stack 1 is 11 Stack Full! Cannot Push 6 is being popped from Stack 1 5 is being popped from Stack 1 4 is being popped from Stack 1 3 is being popped from Stack 1 2 is being popped from Stack 1 1 is being popped from Stack 1 Stack Empty! Cannot Pop Session 9 & 10 - Queues: ------------ Q. Implement dequeue using Array: #include #define SIZE 1> #include void ip_res() ;//Input Restricted void op_res(); //Output Restricted void insert_front(int queue[], int n) ; void insert_rear(int queue[], int n) ; void delete_front(int queue[]) ; //Error was accepting int n void delete_rear(int queue[]) ; void display(int queue[]) ; int front = -1; int rear = -1 ; int queue[SIZE], n ; void main() { int ch; while(1) { system("CLS") ; printf("\n***MENU***\n") ; printf("\n1. INPUT RESTRICTED DEQUEUE") ; printf("\n2. OUTPUT RESTRICTED DEQUEUE") ; printf("\n3. DISPLAY"); printf("\n4. EXIT") ; printf("\n\nEnter your choice: ") ; scanf("%d", &ch) ; switch(ch) { case 1 : ip_res(queue,n); //Input-Restricted Dequeue break ; case 2 : op_res(queue,n); //Input-Restricted Dequeue break ; case 3 : display(queue) ; break ; default : printf("INVALID INPUT!!!") ; system("pause") ; } } } void ip_res() { int ch; while(1) { system("CLS") ; printf("\n***Menu***") ; printf("\n 1. Insert from Rear") ; printf("\n 2. Delete from Front") ; printf("\n 3. Delete from Rear") ; printf("\n 4. Display") ; printf("\n 5. Exit") ; printf("\nEnter your choice: ") ; scanf("%d", &ch) ; switch(ch) { case 1: insert_rear(queue,n) ; printf("\n"); system("pause"); break ; case 2: delete_front(queue) ; system("pause") ; break ; /* case 3: delete_rear(queue) ; system("pause") ; break ; */ case 4: display(queue) ; system("pause") ; break ; case 5: exit(0) ; default: printf("\n Invalid ch") ; system("pause") ; break ; } } } void op_res() { int ch; while(1) { system("CLS") ; printf("\n***Menu***") ; printf("\n 1. Insert from Front") ; printf("\n 2. Insert from Rear") ; printf("\n 3. Delete from Front") ; printf("\n 4. Display") ; printf("\n 5. Exit\n") ; printf("\nEnter your choice: ") ; scanf("%d", &ch) ; switch(ch) { /* case 1: insert_front(queue,n) ; printf("\n"); system("pause"); break ; */ case 2: insert_rear(queue,n); system("pause") ; break ; case 3: delete_front(queue); system("pause") ; break ; case 4: display(queue) ; system("pause") ; break ; case 5: exit(0) ; default: printf("\nINVALID CHOICE!!!\n") ; system("pause") ; break ; } } } void insert_rear(int queue[], int n) { //Case for inserting an element at Rear End of the queue. if(front == 0 && rear == SIZE-1) { printf("\nOVERFLOW ERROR!!!\nQUEUE IS FULL! \n\n") ; } else { if (front==-1) front=0; rear = rear + 1 ; queue[rear] = n ; printf("Insertion Successful!! \n\n") ; } system("pause") ; } //Case 2 is for deleting an element from front of the queue. void delete_front(int queue[]) { int i ; if(front == -1 && rear == -1) { printf("\nUNDERFLOW ERROR!!! \nQUEUE IS EMPTY \n\n") ; } else if (front==0 && rear==-1) { front=-1; printf("\nUNDERFLOW ERROR!!! \nQUEUE IS EMPTY \n\n") ; } else { printf("Deleted element is:%d\n\n", queue[front]) ; for(i = front ; iR? { printf("\nUNDERFLOW ERROR!!! \nQUEUE IS EMPTY \n\n") ; } else if (front==0 && rear==-1) { front=-1; printf("\nUNDERFLOW ERROR!!! \nQUEUE IS EMPTY \n\n") ; } else { printf("Deleted element is:%d\n\n", queue[rear]) ; for(i = front ; i #include struct node { int data; struct node * next; }; struct node * front; struct node * rear; void insert(struct node * ptr, int item) { ptr = (struct node * ) malloc(sizeof(struct node)); if (ptr == NULL) { printf("\nOVERFLOW\n"); return; } else { ptr -> data = item; if (front == NULL) { front = ptr; rear = ptr; front -> next = NULL; rear -> next = NULL; } else { rear -> next = ptr; rear = ptr; rear -> next = NULL; } } } int main() { struct node * head = NULL; insert(head, 10); insert(head, 20); printf("front element: %d", front -> data); return 0; } Q. Reverse the element of a queue: #include #include #define MAX_SIZE 100 struct Queue { int items[MAX_SIZE]; int front; int rear; }; struct Stack { int items[MAX_SIZE]; int top; }; void enqueue (struct Queue *q, int item) { if (q->rear == MAX_SIZE - 1) { printf ("Queue overflow\n"); return; } if (q->front == -1) { q->front = 0; } q->rear++; q->items[q->rear] = item; } int dequeue (struct Queue *q) { if (q->front == -1) { printf ("Queue underflow\n"); return -1; } int item = q->items[q->front]; q->front++; if (q->front > q->rear) { q->front = q->rear = -1; } return item; } void display (struct Queue *q) { if (q->rear == -1) { printf ("Queue is empty\n"); return; } for (int i = q->front; i <= q->rear; i++) { printf ("%d ", q->items[i]); } printf ("\n"); } void push (struct Stack *s, int item) { if (s->top == MAX_SIZE - 1) { printf ("Stack overflow\n"); return; } s->top++; s->items[s->top] = item; } int pop (struct Stack *s) { if (s->top == -1) { printf ("Stack underflow\n"); return -1; } int item = s->items[s->top]; s->top--; return item; } int main () { struct Queue q; q.front = -1; q.rear = -1; struct Stack s; s.top = -1; enqueue (&q, 1); enqueue (&q, 2); enqueue (&q, 3); enqueue (&q, 4); printf ("Queue before reversing:\n"); display (&q); while (q.front != -1) { push (&s, dequeue (&q)); } while (s.top != -1) { enqueue (&q, pop (&s)); } printf ("Queue after reversing:\n"); display (&q); return 0; } Output: Queue before reversing: 1 2 3 4 Queue after reversing: 4 3 2 1 Q. Implement queue using two stacks: /* C program to implement queues using two stacks */ #include #include struct node { int data; struct node *next; }; void push(struct node** top, int data); int pop(struct node** top); struct queue { struct node *stack1; struct node *stack2; }; void enqueue(struct queue *q, int x) { push(&q->stack1, x); } void dequeue(struct queue *q) { int x; if (q->stack1 == NULL && q->stack2 == NULL) { printf("queue is empty"); return; } if (q->stack2 == NULL) { while (q->stack1 != NULL) { x = pop(&q->stack1); push(&q->stack2, x); } } x = pop(&q->stack2); printf("%d\n", x); } void push(struct node** top, int data) { struct node* newnode = (struct node*) malloc(sizeof(struct node)); if (newnode == NULL) { printf("Stack overflow \n"); return; } newnode->data = data; newnode->next = (*top); (*top) = newnode; } int pop(struct node** top) { int buff; struct node *t; if (*top == NULL) { printf("Stack underflow \n"); return; } else { t = *top; buff = t->data; *top = t->next; free(t); return buff; } } void display(struct node *top1,struct node *top2) { while (top1 != NULL) { printf("%d\n", top1->data); top1 = top1->next; } while (top2 != NULL) { printf("%d\n", top2->data); top2 = top2->next; } } int main() { struct queue *q = (struct queue*)malloc(sizeof(struct queue)); int f = 0, a; char ch = 'y'; q->stack1 = NULL; q->stack2 = NULL; while (ch == 'y'||ch == 'Y') { printf("enter ur choice\n1.add to queue\n2.remove from queue\n3.display\n4.exit\n"); scanf("%d", &f); switch(f) { case 1 : printf("enter the element to be added to queue\n"); scanf("%d", &a); enqueue(q, a); break; case 2 : dequeue(q); break; case 3 : display(q->stack1, q->stack2); break; case 4 : exit(1); break; default : printf("invalid\n"); break; } } } Output: Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 1 Enter the element to be added to queue 34 Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 1 Enter the element to be added to queue 55 Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 1 Enter the element to be added to queue 99 Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 1 Enter the element to be added to queue 77 Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 3 34 55 99 77 Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 2 Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 3 55 99 77 Enter your choice 1. Add an element to the queue 2. Remove an element from queue 3. Display the elements in queue 4. Exit 4 Q. Implementation of a stack using two queue: #include #include /* Queue structure */ #define QUEUE_EMPTY_MAGIC 0xdeadbeef typedef struct _queue_t { int *arr; int rear, front, count, max; } queue_t; /* Queue operation function prototypes */ queue_t *queue_allocate(int n); void queue_insert(queue_t * q, int v); int queue_remove(queue_t * q); int queue_count(queue_t * q); int queue_is_empty(queue_t * q); /* NOTE: Here is the stuff we are interested in */ /* Simulated stack operations START */ /* NOTE: passing the queue object, on which we will only operate the * queue operations. */ void stack_push(queue_t * q, int v) { queue_insert(q, v); } int stack_pop(queue_t * q) { int i, n = queue_count(q); int removed_element; for (i = 0; i < (n - 1); i++) { removed_element = queue_remove(q); queue_insert(q, removed_element); /* same as below */ //queue_insert (q, queue_remove (q)) } removed_element = queue_remove(q); return removed_element; } int stack_is_empty(queue_t * q) { return queue_is_empty(q); } int stack_count(queue_t * q) { return queue_count(q); } /* Simulated stack operations END */ /* Queue operations START */ int queue_count(queue_t * q) { return q->count; } queue_t * queue_allocate(int n) { queue_t *queue; queue = malloc(sizeof(queue_t)); if (queue == NULL) return NULL; queue->max = n; queue->arr = malloc(sizeof(int) * n); queue->rear = n - 1; queue->front = n - 1; return queue; } void queue_insert(queue_t * q, int v) { if (q->count == q->max) return; q->rear = (q->rear + 1) % q->max; q->arr[q->rear] = v; q->count++; } int queue_remove(queue_t * q) { int retval; /* magic number if queue is empty */ if (q->count == 0) return QUEUE_EMPTY_MAGIC; q->front = (q->front + 1) % q->max; retval = q->arr[q->front]; q->count--; return retval; } int queue_is_empty(queue_t * q) { return (q->count == 0); } /* Queue operations END */ /* For demo */ void queue_display(queue_t * q) { int i = (q->front + 1) % q->max, elements = queue_count(q); while (elements--) { printf("[%d], ", q->arr[i]); i = (i >= q->max) ? 0 : (i + 1); } } #define MAX 128 int main(void) { queue_t *q; int x, select; /* Static allocation */ q = queue_allocate(MAX); do { printf("\n[1] Push\n[2] Pop\n[0] Exit"); printf("\nChoice: "); scanf(" %d", &select); switch (select) { case 1: printf("\nEnter value to Push:"); scanf(" %d", &x); /* Pushing */ stack_push(q, x); printf("\n\n__________________________\nCurrent Queue:\n"); queue_display(q); printf("\n\nPushed Value: %d", x); printf("\n__________________________\n"); break; case 2: /* Popping */ x = stack_pop(q); printf("\n\n\n\n__________________________\nCurrent Queue:\n"); queue_display(q); if (x == QUEUE_EMPTY_MAGIC) printf("\n\nNo values removed"); else printf("\n\nPopped Value: %d", x); printf("\n__________________________\n"); break; case 0: printf("\nQutting.\n"); return 0; default: printf("\nQutting.\n"); return 0; } } while (1); return 0; } Output: [1] Push [2] Pop [0] Exit Choice: 1 Enter value to Push: 12 __________________________ Current Queue: [12], Pushed Value: 12 __________________________ [1] Push [2] Pop [0] Exit Choice: 1 Enter value to Push: 53 __________________________ Current Queue: [12], [53], Pushed Value: 53 __________________________ [1] Push [2] Pop [0] Exit Choice: 1 Enter value to Push: 75 __________________________ Current Queue: [12], [53], [75], Pushed Value: 75 __________________________ [1] Push [2] Pop [0] Exit Choice: 2 __________________________ Current Queue: [12], [53], Popped Value: 75 __________________________ [1] Push [2] Pop [0] Exit Choice: 0 Qutting. Session 11 & Session 12 : Trees and Binary Trees: ------------ Q. Insertion in binary tree: #include #include struct BTnode { int keyVal; struct BTnode *leftNode; struct BTnode *rightNode; }; struct BTnode *getNode(int value) { struct BTnode *newNode = malloc(sizeof(struct BTnode)); newNode->keyVal = value; newNode->leftNode = NULL; newNode->rightNode = NULL; return newNode; } struct BTnode *insert(struct BTnode *rootNode, int value) { if(rootNode == NULL) return getNode(value); if(rootNode->keyVal < value) rootNode->rightNode = insert(rootNode->rightNode,value); else if(rootNode->keyVal > value) rootNode->leftNode = insert(rootNode->leftNode,value); return rootNode; } void insertorder(struct BTnode *rootNode) { if(rootNode == NULL) return; insertorder(rootNode->leftNode); printf("%d ",rootNode->keyVal); insertorder(rootNode->rightNode); } int main() { struct BTnode *rootNode = NULL; rootNode = insert(rootNode,7); rootNode = insert(rootNode,4); rootNode = insert(rootNode,8); rootNode = insert(rootNode,1); rootNode = insert(rootNode,5); rootNode = insert(rootNode,2); rootNode = insert(rootNode,9); rootNode = insert(rootNode,3); insertorder(rootNode); return 0; } Q. Deletion operation in binary tree: // C++ program to delete element in binary tree #include using namespace std; /* A binary tree node has key, pointer to left child and a pointer to right child */ struct Node { int key; struct Node *left, *right; }; /* function to create a new node of tree and return pointer */ struct Node* newNode(int key) { struct Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; }; /* Inorder traversal of a binary tree*/ void inorder(struct Node* temp) { if (!temp) return; inorder(temp->left); cout << temp->key << " "; inorder(temp->right); } /* function to delete the given deepest node (d_node) in binary tree */ void deletDeepest(struct Node* root, struct Node* d_node) { queue q; q.push(root); // Do level order traversal until last node struct Node* temp; while (!q.empty()) { temp = q.front(); q.pop(); if (temp == d_node) { temp = NULL; delete (d_node); return; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; delete (d_node); return; } else q.push(temp->right); } if (temp->left) { if (temp->left == d_node) { temp->left = NULL; delete (d_node); return; } else q.push(temp->left); } } } /* function to delete element in binary tree */ Node* deletion(struct Node* root, int key) { if (root == NULL) return NULL; if (root->left == NULL && root->right == NULL) { if (root->key == key) return NULL; else return root; } queue q; q.push(root); struct Node* temp; struct Node* key_node = NULL; // Do level order traversal to find deepest // node(temp) and node to be deleted (key_node) while (!q.empty()) { temp = q.front(); q.pop(); if (temp->key == key) key_node = temp; if (temp->left) q.push(temp->left); if (temp->right) q.push(temp->right); } if (key_node != NULL) { int x = temp->key; deletDeepest(root, temp); key_node->key = x; } return root; } // Driver code int main() { struct Node* root = newNode(10); root->left = newNode(11); root->left->left = newNode(7); root->left->right = newNode(12); root->right = newNode(9); root->right->left = newNode(15); root->right->right = newNode(8); cout << "Inorder traversal before deletion: "; inorder(root); int key = 11; root = deletion(root, key); cout << endl; cout << "Inorder traversal after deletion: "; inorder(root); return 0; } Output: Inorder traversal before deletion : 7 11 12 10 15 9 8 Inorder traversal after deletion : 7 8 12 10 15 9 Q. Binary tree, inorder, preorder, and postorder traversal #include #include struct BTnode { int data; struct BTnode* leftNode; struct BTnode* rightNode; }; void inorder(struct BTnode* rootNode) { if (rootNode == NULL) return; inorder(rootNode->leftNode); printf("%d ->", rootNode->data); inorder(rootNode->rightNode); } void preorder(struct BTnode* rootNode) { if (rootNode == NULL) return; printf("%d ->", rootNode->data); preorder(rootNode->leftNode); preorder(rootNode->rightNode); } void postorder(struct BTnode* rootNode) { if (rootNode == NULL) return; postorder(rootNode->leftNode); postorder(rootNode->rightNode); printf("%d ->", rootNode->data); } struct BTnode* createNode(value) { struct BTnode* newNode = malloc(sizeof(struct BTnode)); newNode->data = value; newNode->leftNode = NULL; newNode->rightNode = NULL; return newNode; } struct BTnode* insertLeftNode(struct BTnode* rootNode, int value) { rootNode->leftNode = createNode(value); return rootNode->leftNode; } struct BTnode* insertRightNode(struct BTnode* rootNode, int value) { rootNode->rightNode = createNode(value); return rootNode->rightNode; } int main() { struct BTnode* rootNode = createNode(7); insertLeftNode(rootNode, 4); insertRightNode(rootNode, 8); insertLeftNode(rootNode->leftNode, 1); insertRightNode(rootNode->rightNode, 5); insertLeftNode(rootNode->leftNode, 6); insertRightNode(rootNode->rightNode, 3); printf("Inorder \n"); inorder(rootNode); printf("\nPreorder \n"); preorder(rootNode); printf("\nPostorder \n"); postorder(rootNode); } Output: Inorder: 6 -> 4 -> 7 -> 8 -> 3 Preorder: 7 -> 4 -> 6 -> 8 -> 3 Postorder: 6 -> 4 -> 3 -> 8 ->7 Q. Convert tree into binary tree. #include #include using namespace std; class TreeNode { public: int data; TreeNode* left; TreeNode* right; vector child; TreeNode(int data) { this->data = data; this->left = this->right = NULL; } }; TreeNode* genericToBinary(TreeNode* root) { if (!root || root->child.size()==0) { return root; } root->left = genericToBinary(root->child[0]); if (root->child.size() == 1) { return root; } root->right = genericToBinary(root->child[1]); for (int i = 2; i < root->child.size(); i++) { TreeNode* rightNode = root->right; while (rightNode->left != NULL) { rightNode = rightNode->left; } rightNode->left = genericToBinary(root->child[i]); } return root; } void printTree(TreeNode* root) { if (root == NULL) { return; } cout << root->data << " "; printTree(root->left); printTree(root->right); } int main() { TreeNode* root = new TreeNode(5); root->child.push_back(new TreeNode(8)); root->child.push_back(new TreeNode(2)); root->child.push_back(new TreeNode(1)); root->child[0]->child.push_back(new TreeNode(3)); root->child[0]->child.push_back(new TreeNode(4)); TreeNode* binaryTree = genericToBinary(root); printTree(binaryTree); } Q. Check if a binary tree is full binary tree: // C++ program to check whether a given Binary Tree is full or not #include using namespace std; /* Tree node structure */ struct Node { int key; struct Node *left, *right; }; /* Helper function that allocates a new node with the given key and NULL left and right pointer. */ struct Node *newNode(char k) { struct Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } /* This function tests if a binary tree is a full binary tree. */ bool isFullTree (struct Node* root) { // If empty tree if (root == NULL) return true; // If leaf node if (root->left == NULL && root->right == NULL) return true; // If both left and right are not NULL, and left & right subtrees // are full if ((root->left) && (root->right)) return (isFullTree(root->left) && isFullTree(root->right)); // We reach here when none of the above if conditions work return false; } // Driver Program int main() { struct Node* root = NULL; root = newNode(10); root->left = newNode(20); root->right = newNode(30); root->left->right = newNode(40); root->left->left = newNode(50); root->right->left = newNode(60); root->right->right = newNode(70); root->left->left->left = newNode(80); root->left->left->right = newNode(90); root->left->right->left = newNode(80); root->left->right->right = newNode(90); root->right->left->left = newNode(80); root->right->left->right = newNode(90); root->right->right->left = newNode(80); root->right->right->right = newNode(90); if (isFullTree(root)) cout << "The Binary Tree is full\n"; else cout << "The Binary Tree is not full\n"; return(0); } Q. Check if two trees are identical/same. // C++ program to see if two trees are identical #include using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class node { public: int data; node* left; node* right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode(int data) { node* Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL; return (Node); } /* Given two trees, return true if they are structurally identical */ int identicalTrees(node* a, node* b) { /*1. both empty */ if (a == NULL && b == NULL) return 1; /* 2. both non-empty -> compare them */ if (a != NULL && b != NULL) { return (a->data == b->data && identicalTrees(a->left, b->left) && identicalTrees(a->right, b->right)); } /* 3. one empty, one not -> false */ return 0; } /* Driver code*/ int main() { node* root1 = newNode(1); node* root2 = newNode(1); root1->left = newNode(2); root1->right = newNode(3); root1->left->left = newNode(4); root1->left->right = newNode(5); root2->left = newNode(2); root2->right = newNode(3); root2->left->left = newNode(4); root2->left->right = newNode(5); // Function call if (identicalTrees(root1, root2)) cout << "Both trees are identical."; else cout << "Trees are not identical."; return 0; } Q. Count the number of leaves of a binary tree: // C++ implementation to find leaf // count of a given Binary tree #include using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Function to get the count of leaf nodes in a binary tree*/ unsigned int getLeafCount(struct node* node) { if(node == NULL) return 0; if(node->left == NULL && node->right == NULL) return 1; else return getLeafCount(node->left)+ getLeafCount(node->right); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /*Driver code*/ int main() { /*create a tree*/ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); /*get leaf count of the above created tree*/ cout << "Leaf count of the tree is : "<< getLeafCount(root) << endl; return 0; } Session 13 & 14 - Advanced trees: ----------------- Q. Create a binary search tree, accept key value and search. #include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; } else if(a[mid] < val) { return binarySearch(a, mid+1, end, val); } else { return binarySearch(a, beg, mid-1, val); } } return -1; } int main() { int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; int val = 40; int n = sizeof(a) / sizeof(a[0]); int res = binarySearch(a, 0, n-1, val); printf("The elements of the array are - "); for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\nElement to be searched is - %d", val); if (res == -1) printf("\nElement is not present in the array"); else printf("\nElement is present at %d position of array", res); return 0; } Output: The elements of the array are – 11 14 25 30 40 41 52 57 70 Element to be searched is – 40 Element is present at 5 position of array Q. Insertion into AVL tree: // C program to insert a node in AVL tree #include #include // An AVL tree node struct Node { int key; struct Node *left; struct Node *right; int height; }; // A utility function to get the height of the tree int height(struct Node *N) { if (N == NULL) return 0; return N->height; } // A utility function to get maximum of two integers int max(int a, int b) { return (a > b)? a : b; } /* Helper function that allocates a new node with the given key and NULL left and right pointers. */ struct Node* newNode(int key) { struct Node* node = (struct Node*) malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; // new node is initially added at leaf return(node); } // A utility function to right rotate subtree rooted with y // See the diagram given above. struct Node *rightRotate(struct Node *y) { struct Node *x = y->left; struct Node *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; // Return new root return x; } // A utility function to left rotate subtree rooted with x // See the diagram given above. struct Node *leftRotate(struct Node *x) { struct Node *y = x->right; struct Node *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; // Return new root return y; } // Get Balance factor of node N int getBalance(struct Node *N) { if (N == NULL) return 0; return height(N->left) - height(N->right); } // Recursive function to insert a key in the subtree rooted // with node and returns the new root of the subtree. struct Node* insert(struct Node* node, int key) { /* 1. Perform the normal BST insertion */ if (node == NULL) return(newNode(key)); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys are not allowed in BST return node; /* 2. Update height of this ancestor node */ node->height = 1 + max(height(node->left), height(node->right)); /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int balance = getBalance(node); // If this node becomes unbalanced, then // there are 4 cases // Left Left Case if (balance > 1 && key < node->left->key) return rightRotate(node); // Right Right Case if (balance < -1 && key > node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } // A utility function to print preorder traversal // of the tree. // The function also prints height of every node void preOrder(struct Node *root) { if(root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } /* Driver program to test above function*/ int main() { struct Node *root = NULL; /* Constructing tree given in the above figure */ root = insert(root, 5); root = insert(root, 8); root = insert(root, 11); root = insert(root, 12); root = insert(root, 18); root = insert(root, 17); /* The constructed AVL Tree would be 12 / \ 8 18 / \ / 5 11 17 */ printf("Preorder traversal of the constructed AVL" " tree is \n"); preOrder(root); return 0; } Output: Preorder traversal of the constructed AVL tree is 30 20 10 25 40 50 Q. Implementation of B-Tree // Searching a key on a B-tree in C #include #include #define MAX 3 #define MIN 2 struct BTreeNode { int val[MAX + 1], count; struct BTreeNode *link[MAX + 1]; }; struct BTreeNode *root; // Create a node struct BTreeNode *createNode(int val, struct BTreeNode *child) { struct BTreeNode *newNode; newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); newNode->val[1] = val; newNode->count = 1; newNode->link[0] = root; newNode->link[1] = child; return newNode; } // Insert node void insertNode(int val, int pos, struct BTreeNode *node, struct BTreeNode *child) { int j = node->count; while (j > pos) { node->val[j + 1] = node->val[j]; node->link[j + 1] = node->link[j]; j--; } node->val[j + 1] = val; node->link[j + 1] = child; node->count++; } // Split node void splitNode(int val, int *pval, int pos, struct BTreeNode *node, struct BTreeNode *child, struct BTreeNode **newNode) { int median, j; if (pos > MIN) median = MIN + 1; else median = MIN; *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); j = median + 1; while (j <= MAX) { (*newNode)->val[j - median] = node->val[j]; (*newNode)->link[j - median] = node->link[j]; j++; } node->count = median; (*newNode)->count = MAX - median; if (pos <= MIN) { insertNode(val, pos, node, child); } else { insertNode(val, pos - median, *newNode, child); } *pval = node->val[node->count]; (*newNode)->link[0] = node->link[node->count]; node->count--; } // Set the value int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child) { int pos; if (!node) { *pval = val; *child = NULL; return 1; } if (val < node->val[1]) { pos = 0; } else { for (pos = node->count; (val < node->val[pos] && pos > 1); pos--) ; if (val == node->val[pos]) { printf("Duplicates are not permitted\n"); return 0; } } if (setValue(val, pval, node->link[pos], child)) { if (node->count < MAX) { insertNode(*pval, pos, node, *child); } else { splitNode(*pval, pval, pos, node, *child, child); return 1; } } return 0; } // Insert the value void insert(int val) { int flag, i; struct BTreeNode *child; flag = setValue(val, &i, root, &child); if (flag) root = createNode(i, child); } // Search node void search(int val, int *pos, struct BTreeNode *myNode) { if (!myNode) { return; } if (val < myNode->val[1]) { *pos = 0; } else { for (*pos = myNode->count; (val < myNode->val[*pos] && *pos > 1); (*pos)--) ; if (val == myNode->val[*pos]) { printf("%d is found", val); return; } } search(val, pos, myNode->link[*pos]); return; } // Traverse then nodes void traversal(struct BTreeNode *myNode) { int i; if (myNode) { for (i = 0; i < myNode->count; i++) { traversal(myNode->link[i]); printf("%d ", myNode->val[i + 1]); } traversal(myNode->link[i]); } } int main() { int val, ch; insert(8); insert(9); insert(10); insert(11); insert(15); insert(16); insert(17); insert(18); insert(20); insert(23); traversal(root); printf("\n"); search(11, &ch, root); } Q. Implementation of Splay Tree: #include #include // An AVL tree node struct node { int key; struct node *left, *right; }; /* Helper function that allocates a new node with the given key and NULL left and right pointers. */ struct node* newNode(int key) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->key = key; node->left = node->right = NULL; return (node); } // A utility function to right rotate subtree rooted with y // See the diagram given above. struct node *rightRotate(struct node *x) { struct node *y = x->left; x->left = y->right; y->right = x; return y; } // A utility function to left rotate subtree rooted with x // See the diagram given above. struct node *leftRotate(struct node *x) { struct node *y = x->right; x->right = y->left; y->left = x; return y; } // This function brings the key at root if key is present in tree. // If key is not present, then it brings the last accessed item at // root. This function modifies the tree and returns the new root struct node *splay(struct node *root, int key) { // Base cases: root is NULL or key is present at root if (root == NULL || root->key == key) return root; // Key lies in left subtree if (root->key > key) { // Key is not in tree, we are done if (root->left == NULL) return root; // Zig-Zig (Left Left) if (root->left->key > key) { // First recursively bring the key as root of left-left root->left->left = splay(root->left->left, key); // Do first rotation for root, second rotation is done after else root = rightRotate(root); } else if (root->left->key < key) // Zig-Zag (Left Right) { // First recursively bring the key as root of left-right root->left->right = splay(root->left->right, key); // Do first rotation for root->left if (root->left->right != NULL) root->left = leftRotate(root->left); } // Do second rotation for root return (root->left == NULL) ? root : rightRotate(root); } else // Key lies in right subtree { // Key is not in tree, we are done if (root->right == NULL) return root; // Zag-Zig (Right Left) if (root->right->key > key) { // Bring the key as root of right-left root->right->left = splay(root->right->left, key); // Do first rotation for root->right if (root->right->left != NULL) root->right = rightRotate(root->right); } else if (root->right->key < key)// Zag-Zag (Right Right) { // Bring the key as root of right-right and do first rotation root->right->right = splay(root->right->right, key); root = leftRotate(root); } // Do second rotation for root return (root->right == NULL) ? root : leftRotate(root); } } // The search function for Splay tree. Note that this function // returns the new root of Splay Tree. If key is present in tree // then, it is moved to root. struct node *search(struct node *root, int key) { return splay(root, key); } // A utility function to print preorder traversal of the tree. // The function also prints height of every node void preOrder(struct node *root) { if (root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } int main() { struct node *root = newNode(100); root->left = newNode(50); root->right = newNode(200); root->left->left = newNode(40); root->left->left->left = newNode(30); root->left->left->left->left = newNode(20); printf("Preorder traversal of the Splay tree is \n"); preOrder(root); root = search(root, 20); printf("\nPreorder traversal of after search Splay tree is \n"); preOrder(root); return 0; } Output: Preorder traversal of the Splay tree is 100 50 40 30 20 200 Preorder traversal of after search Splay tree is 20 50 30 40 100 200 Q. Implementation of Red-Black tree: // Implementing Red-Black Tree in C #include #include enum nodeColor { RED, BLACK }; struct rbNode { int data, color; struct rbNode *link[2]; }; struct rbNode *root = NULL; // Create a red-black tree struct rbNode *createNode(int data) { struct rbNode *newnode; newnode = (struct rbNode *)malloc(sizeof(struct rbNode)); newnode->data = data; newnode->color = RED; newnode->link[0] = newnode->link[1] = NULL; return newnode; } // Insert an node void insertion(int data) { struct rbNode *stack[98], *ptr, *newnode, *xPtr, *yPtr; int dir[98], ht = 0, index; ptr = root; if (!root) { root = createNode(data); return; } stack[ht] = root; dir[ht++] = 0; while (ptr != NULL) { if (ptr->data == data) { printf("Duplicates Not Allowed!!\n"); return; } index = (data - ptr->data) > 0 ? 1 : 0; stack[ht] = ptr; ptr = ptr->link[index]; dir[ht++] = index; } stack[ht - 1]->link[index] = newnode = createNode(data); while ((ht >= 3) && (stack[ht - 1]->color == RED)) { if (dir[ht - 2] == 0) { yPtr = stack[ht - 2]->link[1]; if (yPtr != NULL && yPtr->color == RED) { stack[ht - 2]->color = RED; stack[ht - 1]->color = yPtr->color = BLACK; ht = ht - 2; } else { if (dir[ht - 1] == 0) { yPtr = stack[ht - 1]; } else { xPtr = stack[ht - 1]; yPtr = xPtr->link[1]; xPtr->link[1] = yPtr->link[0]; yPtr->link[0] = xPtr; stack[ht - 2]->link[0] = yPtr; } xPtr = stack[ht - 2]; xPtr->color = RED; yPtr->color = BLACK; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = xPtr; if (xPtr == root) { root = yPtr; } else { stack[ht - 3]->link[dir[ht - 3]] = yPtr; } break; } } else { yPtr = stack[ht - 2]->link[0]; if ((yPtr != NULL) && (yPtr->color == RED)) { stack[ht - 2]->color = RED; stack[ht - 1]->color = yPtr->color = BLACK; ht = ht - 2; } else { if (dir[ht - 1] == 1) { yPtr = stack[ht - 1]; } else { xPtr = stack[ht - 1]; yPtr = xPtr->link[0]; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = xPtr; stack[ht - 2]->link[1] = yPtr; } xPtr = stack[ht - 2]; yPtr->color = BLACK; xPtr->color = RED; xPtr->link[1] = yPtr->link[0]; yPtr->link[0] = xPtr; if (xPtr == root) { root = yPtr; } else { stack[ht - 3]->link[dir[ht - 3]] = yPtr; } break; } } } root->color = BLACK; } // Delete a node void deletion(int data) { struct rbNode *stack[98], *ptr, *xPtr, *yPtr; struct rbNode *pPtr, *qPtr, *rPtr; int dir[98], ht = 0, diff, i; enum nodeColor color; if (!root) { printf("Tree not available\n"); return; } ptr = root; while (ptr != NULL) { if ((data - ptr->data) == 0) break; diff = (data - ptr->data) > 0 ? 1 : 0; stack[ht] = ptr; dir[ht++] = diff; ptr = ptr->link[diff]; } if (ptr->link[1] == NULL) { if ((ptr == root) && (ptr->link[0] == NULL)) { free(ptr); root = NULL; } else if (ptr == root) { root = ptr->link[0]; free(ptr); } else { stack[ht - 1]->link[dir[ht - 1]] = ptr->link[0]; } } else { xPtr = ptr->link[1]; if (xPtr->link[0] == NULL) { xPtr->link[0] = ptr->link[0]; color = xPtr->color; xPtr->color = ptr->color; ptr->color = color; if (ptr == root) { root = xPtr; } else { stack[ht - 1]->link[dir[ht - 1]] = xPtr; } dir[ht] = 1; stack[ht++] = xPtr; } else { i = ht++; while (1) { dir[ht] = 0; stack[ht++] = xPtr; yPtr = xPtr->link[0]; if (!yPtr->link[0]) break; xPtr = yPtr; } dir[i] = 1; stack[i] = yPtr; if (i > 0) stack[i - 1]->link[dir[i - 1]] = yPtr; yPtr->link[0] = ptr->link[0]; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = ptr->link[1]; if (ptr == root) { root = yPtr; } color = yPtr->color; yPtr->color = ptr->color; ptr->color = color; } } if (ht < 1) return; if (ptr->color == BLACK) { while (1) { pPtr = stack[ht - 1]->link[dir[ht - 1]]; if (pPtr && pPtr->color == RED) { pPtr->color = BLACK; break; } if (ht < 2) break; if (dir[ht - 2] == 0) { rPtr = stack[ht - 1]->link[1]; if (!rPtr) break; if (rPtr->color == RED) { stack[ht - 1]->color = RED; rPtr->color = BLACK; stack[ht - 1]->link[1] = rPtr->link[0]; rPtr->link[0] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } dir[ht] = 0; stack[ht] = stack[ht - 1]; stack[ht - 1] = rPtr; ht++; rPtr = stack[ht - 1]->link[1]; } if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) { rPtr->color = RED; } else { if (!rPtr->link[1] || rPtr->link[1]->color == BLACK) { qPtr = rPtr->link[0]; rPtr->color = RED; qPtr->color = BLACK; rPtr->link[0] = qPtr->link[1]; qPtr->link[1] = rPtr; rPtr = stack[ht - 1]->link[1] = qPtr; } rPtr->color = stack[ht - 1]->color; stack[ht - 1]->color = BLACK; rPtr->link[1]->color = BLACK; stack[ht - 1]->link[1] = rPtr->link[0]; rPtr->link[0] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } break; } } else { rPtr = stack[ht - 1]->link[0]; if (!rPtr) break; if (rPtr->color == RED) { stack[ht - 1]->color = RED; rPtr->color = BLACK; stack[ht - 1]->link[0] = rPtr->link[1]; rPtr->link[1] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } dir[ht] = 1; stack[ht] = stack[ht - 1]; stack[ht - 1] = rPtr; ht++; rPtr = stack[ht - 1]->link[0]; } if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) { rPtr->color = RED; } else { if (!rPtr->link[0] || rPtr->link[0]->color == BLACK) { qPtr = rPtr->link[1]; rPtr->color = RED; qPtr->color = BLACK; rPtr->link[1] = qPtr->link[0]; qPtr->link[0] = rPtr; rPtr = stack[ht - 1]->link[0] = qPtr; } rPtr->color = stack[ht - 1]->color; stack[ht - 1]->color = BLACK; rPtr->link[0]->color = BLACK; stack[ht - 1]->link[0] = rPtr->link[1]; rPtr->link[1] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } break; } } ht--; } } } // Print the inorder traversal of the tree void inorderTraversal(struct rbNode *node) { if (node) { inorderTraversal(node->link[0]); printf("%d ", node->data); inorderTraversal(node->link[1]); } return; } // Driver code int main() { int ch, data; while (1) { printf("1. Insertion\t2. Deletion\n"); printf("3. Traverse\t4. Exit"); printf("\nEnter your choice:"); scanf("%d", &ch); switch (ch) { case 1: printf("Enter the element to insert:"); scanf("%d", &data); insertion(data); break; case 2: printf("Enter the element to delete:"); scanf("%d", &data); deletion(data); break; case 3: inorderTraversal(root); printf("\n"); break; case 4: exit(0); default: printf("Not available\n"); break; } printf("\n"); } return 0; } Session 15 & 16 : Graphs: ------------------- Q. Implement Dijkstra's algorithm: // Dijkstra's Algorithm in C #include #define INFINITY 9999 #define MAX 10 void Dijkstra(int Graph[MAX][MAX], int n, int start); void Dijkstra(int Graph[MAX][MAX], int n, int start) { int cost[MAX][MAX], distance[MAX], pred[MAX]; int visited[MAX], count, mindistance, nextnode, i, j; // Creating cost matrix for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (Graph[i][j] == 0) cost[i][j] = INFINITY; else cost[i][j] = Graph[i][j]; for (i = 0; i < n; i++) { distance[i] = cost[start][i]; pred[i] = start; visited[i] = 0; } distance[start] = 0; visited[start] = 1; count = 1; while (count < n - 1) { mindistance = INFINITY; for (i = 0; i < n; i++) if (distance[i] < mindistance && !visited[i]) { mindistance = distance[i]; nextnode = i; } visited[nextnode] = 1; for (i = 0; i < n; i++) if (!visited[i]) if (mindistance + cost[nextnode][i] < distance[i]) { distance[i] = mindistance + cost[nextnode][i]; pred[i] = nextnode; } count++; } // Printing the distance for (i = 0; i < n; i++) if (i != start) { printf("\nDistance from source to %d: %d", i, distance[i]); } } int main() { int Graph[MAX][MAX], i, j, n, u; n = 7; Graph[0][0] = 0; Graph[0][1] = 0; Graph[0][2] = 1; Graph[0][3] = 2; Graph[0][4] = 0; Graph[0][5] = 0; Graph[0][6] = 0; Graph[1][0] = 0; Graph[1][1] = 0; Graph[1][2] = 2; Graph[1][3] = 0; Graph[1][4] = 0; Graph[1][5] = 3; Graph[1][6] = 0; Graph[2][0] = 1; Graph[2][1] = 2; Graph[2][2] = 0; Graph[2][3] = 1; Graph[2][4] = 3; Graph[2][5] = 0; Graph[2][6] = 0; Graph[3][0] = 2; Graph[3][1] = 0; Graph[3][2] = 1; Graph[3][3] = 0; Graph[3][4] = 0; Graph[3][5] = 0; Graph[3][6] = 1; Graph[4][0] = 0; Graph[4][1] = 0; Graph[4][2] = 3; Graph[4][3] = 0; Graph[4][4] = 0; Graph[4][5] = 2; Graph[4][6] = 0; Graph[5][0] = 0; Graph[5][1] = 3; Graph[5][2] = 0; Graph[5][3] = 0; Graph[5][4] = 2; Graph[5][5] = 0; Graph[5][6] = 1; Graph[6][0] = 0; Graph[6][1] = 0; Graph[6][2] = 0; Graph[6][3] = 1; Graph[6][4] = 0; Graph[6][5] = 1; Graph[6][6] = 0; u = 0; Dijkstra(Graph, n, u); return 0; } Q. Implement Kruskal's algorithm: // Kruskal's algorithm in C #include #define MAX 30 typedef struct edge { int u, v, w; } edge; typedef struct edge_list { edge data[MAX]; int n; } edge_list; edge_list elist; int Graph[MAX][MAX], n; edge_list spanlist; void kruskalAlgo(); int find(int belongs[], int vertexno); void applyUnion(int belongs[], int c1, int c2); void sort(); void print(); // Applying Krushkal Algo void kruskalAlgo() { int belongs[MAX], i, j, cno1, cno2; elist.n = 0; for (i = 1; i < n; i++) for (j = 0; j < i; j++) { if (Graph[i][j] != 0) { elist.data[elist.n].u = i; elist.data[elist.n].v = j; elist.data[elist.n].w = Graph[i][j]; elist.n++; } } sort(); for (i = 0; i < n; i++) belongs[i] = i; spanlist.n = 0; for (i = 0; i < elist.n; i++) { cno1 = find(belongs, elist.data[i].u); cno2 = find(belongs, elist.data[i].v); if (cno1 != cno2) { spanlist.data[spanlist.n] = elist.data[i]; spanlist.n = spanlist.n + 1; applyUnion(belongs, cno1, cno2); } } } int find(int belongs[], int vertexno) { return (belongs[vertexno]); } void applyUnion(int belongs[], int c1, int c2) { int i; for (i = 0; i < n; i++) if (belongs[i] == c2) belongs[i] = c1; } // Sorting algo void sort() { int i, j; edge temp; for (i = 1; i < elist.n; i++) for (j = 0; j < elist.n - 1; j++) if (elist.data[j].w > elist.data[j + 1].w) { temp = elist.data[j]; elist.data[j] = elist.data[j + 1]; elist.data[j + 1] = temp; } } // Printing the result void print() { int i, cost = 0; for (i = 0; i < spanlist.n; i++) { printf("\n%d - %d : %d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w); cost = cost + spanlist.data[i].w; } printf("\nSpanning tree cost: %d", cost); } int main() { int i, j, total_cost; n = 6; Graph[0][0] = 0; Graph[0][1] = 4; Graph[0][2] = 4; Graph[0][3] = 0; Graph[0][4] = 0; Graph[0][5] = 0; Graph[0][6] = 0; Graph[1][0] = 4; Graph[1][1] = 0; Graph[1][2] = 2; Graph[1][3] = 0; Graph[1][4] = 0; Graph[1][5] = 0; Graph[1][6] = 0; Graph[2][0] = 4; Graph[2][1] = 2; Graph[2][2] = 0; Graph[2][3] = 3; Graph[2][4] = 4; Graph[2][5] = 0; Graph[2][6] = 0; Graph[3][0] = 0; Graph[3][1] = 0; Graph[3][2] = 3; Graph[3][3] = 0; Graph[3][4] = 3; Graph[3][5] = 0; Graph[3][6] = 0; Graph[4][0] = 0; Graph[4][1] = 0; Graph[4][2] = 4; Graph[4][3] = 3; Graph[4][4] = 0; Graph[4][5] = 0; Graph[4][6] = 0; Graph[5][0] = 0; Graph[5][1] = 0; Graph[5][2] = 2; Graph[5][3] = 0; Graph[5][4] = 3; Graph[5][5] = 0; Graph[5][6] = 0; kruskalAlgo(); print(); } Q. Implement Prim's algorithm: // Prim's Algorithm in C #include #include #define INF 9999999 // number of vertices in graph #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G[V][V] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0}}; int main() { int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected[V]; // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected[0] = true; int x; // row number int y; // col number // print for edge and weight printf("Edge : Weight\n"); while (no_edge < V - 1) { //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) { if (selected[i]) { for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } printf("%d - %d : %d\n", x, y, G[x][y]); selected[y] = true; no_edge++; } return 0; } Session 17 & 18 : Searching and Sorting: -------- Q. Implement linear search using pointer: #include int LINEAR_SEARCH(int inp_arr[], int size, int val) { for (int i = 0; i < size; i++) if (inp_arr[i] == val) return i; return -1; } int main(void) { int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; int key = 100; int size = 10; int res = LINEAR_SEARCH(arr, size, key); if (res == -1) printf("ELEMENT NOT FOUND!!"); else printf("Item is present at index %d", res); return 0; } Output: Item is present at index 5 Q. Binary search using pointer: // Binary Search in C #include int binarySearch(int array[], int x, int low, int high) { // Repeat until the pointers low and high meet each other while (low <= high) { int mid = low + (high - low) / 2; if (array[mid] == x) return mid; if (array[mid] < x) low = mid + 1; else high = mid - 1; } return -1; } int main(void) { int array[] = {3, 4, 5, 6, 7, 8, 9}; int n = sizeof(array) / sizeof(array[0]); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; } Q. Quick sort using pointer: #include // Function to swap two elements void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Function to print the array void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = { 12, 17, 6, 25, 1, 5 }; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printf("Sorted array: \n"); printArray(arr, n); return 0; } Q. Heap sort using pointer: #include // Function to swap two elements void swap(int* x, int* y) { int temp = *x; *x = *y; *y = temp; } // Heapify function to maintain the max-heap property void heapify(int array[], int size, int index) { int largest = index; // Initialize the largest element as the root int left = 2 * index + 1; // Left child index int right = 2 * index + 2; // Right child index // If left child is larger than root if (left < size && array[left] > array[largest]) { largest = left; } // If right child is larger than largest so far if (right < size && array[right] > array[largest]) { largest = right; } // If largest is not the root, swap the root with the largest element if (largest != index) { swap(&array[index], &array[largest]); // Recursively heapify the affected sub-tree heapify(array, size, largest); } } // Heap Sort function void heapSort(int array[], int size) { // Build the max-heap from the array for (int i = size / 2 - 1; i >= 0; i--) { heapify(array, size, i); } // Extract elements from the heap one by one for (int i = size - 1; i > 0; i--) { // Move the current root (maximum element) to the end swap(&array[0], &array[i]); // Heapify the reduced heap heapify(array, i, 0); } } // Function to print an array void printArray(int array[], int size) { for (int i = 0; i < size; i++) { printf("%d ", array[i]); } printf("\n"); } // Driver code int main() { int arr[] = {54, 32, 67, 12, 90, 5}; int size = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, size); heapSort(arr, size); printf("Sorted array: "); printArray(arr, size); return 0; } Q. 2-way merge sort using pointer: #include #define MAX 50 void mergeSort(int arr[],int low,int mid,int high); void partition(int arr[],int low,int high); int main(){ int merge[MAX],i,n; printf("Enter the total number of elements: "); scanf("%d",&n); printf("Enter the elements which to be sort: "); for(i=0;imid){ for(k=m;k<=high;k++){ temp[i]=arr[k]; i++; } } else{ for(k=l;k<=mid;k++){ temp[i]=arr[k]; i++; } } for(k=low;k<=high;k++){ arr[k]=temp[k]; } } Q. Implement Bubble sort using pointer: #include #include void swap(int *ip, int *jp) { int temp = *ip; *ip = *jp; *jp = temp; } void bubbleSort(int array[], int n) { int l, m; bool swapped; for(l = 0; l < n-1; l++) { swapped = false; for(m = 0; m < n-l-1; m++) { if(array[m] > array[m+1]) { swap(&array[m], &array[m+1]); swapped = true; } } // If no two elements were swapped by inner loop, then break if(swapped == false) { break; } } } void printArray(int array[], int size) { int l; for(l = 0; l < size; l++) printf("%d ", array[l]); printf("\n"); } int main() { int array[] = {48, 34, 57, 28, 21, 31, 90}; int n = sizeof(array) / sizeof(array[0]); bubbleSort(array, n); printf("Sorted array: \n"); printArray(array, n); return 0; } Session 19 & 20: Advance Data Structures: ---------- Q. Implementation of Trie Data structure: #include #include #include // The number of children for each node // We will construct a N-ary tree and make it // a Trie // Since we have 26 english letters, we need // 26 children per node #define N 26 typedef struct TrieNode TrieNode; struct TrieNode { // The Trie Node Structure // Each node has N children, starting from the root // and a flag to check if it's a leaf node char data; // Storing for printing purposes only TrieNode* children[N]; int is_leaf; }; TrieNode* make_trienode(char data) { // Allocate memory for a TrieNode TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode)); for (int i=0; ichildren[i] = NULL; node->is_leaf = 0; node->data = data; return node; } void free_trienode(TrieNode* node) { // Free the trienode sequence for(int i=0; ichildren[i] != NULL) { free_trienode(node->children[i]); } else { continue; } } free(node); } TrieNode* insert_trie(TrieNode* root, char* word) { // Inserts the word onto the Trie // ASSUMPTION: The word only has lower case characters TrieNode* temp = root; for (int i=0; word[i] != '\0'; i++) { // Get the relative position in the alphabet list int idx = (int) word[i] - 'a'; if (temp->children[idx] == NULL) { // If the corresponding child doesn't exist, // simply create that child! temp->children[idx] = make_trienode(word[i]); } else { // Do nothing. The node already exists } // Go down a level, to the child referenced by idx // since we have a prefix match temp = temp->children[idx]; } // At the end of the word, mark this node as the leaf node temp->is_leaf = 1; return root; } int search_trie(TrieNode* root, char* word) { // Searches for word in the Trie TrieNode* temp = root; for(int i=0; word[i]!='\0'; i++) { int position = word[i] - 'a'; if (temp->children[position] == NULL) return 0; temp = temp->children[position]; } if (temp != NULL && temp->is_leaf == 1) return 1; return 0; } int check_divergence(TrieNode* root, char* word) { // Checks if there is branching at the last character of word // and returns the largest position in the word where branching occurs TrieNode* temp = root; int len = strlen(word); if (len == 0) return 0; // We will return the largest index where branching occurs int last_index = 0; for (int i=0; i < len; i++) { int position = word[i] - 'a'; if (temp->children[position]) { // If a child exists at that position // we will check if there exists any other child // so that branching occurs for (int j=0; jchildren[j]) { // We've found another child! This is a branch. // Update the branch position last_index = i + 1; break; } } // Go to the next child in the sequence temp = temp->children[position]; } } return last_index; } char* find_longest_prefix(TrieNode* root, char* word) { // Finds the longest common prefix substring of word // in the Trie if (!word || word[0] == '\0') return NULL; // Length of the longest prefix int len = strlen(word); // We initially set the longest prefix as the word itself, // and try to back-tracking from the deepst position to // a point of divergence, if it exists char* longest_prefix = (char*) calloc (len + 1, sizeof(char)); for (int i=0; word[i] != '\0'; i++) longest_prefix[i] = word[i]; longest_prefix[len] = '\0'; // If there is no branching from the root, this // means that we're matching the original string! // This is not what we want! int branch_idx = check_divergence(root, longest_prefix) - 1; if (branch_idx >= 0) { // There is branching, We must update the position // to the longest match and update the longest prefix // by the branch index length longest_prefix[branch_idx] = '\0'; longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char)); } return longest_prefix; } int is_leaf_node(TrieNode* root, char* word) { // Checks if the prefix match of word and root // is a leaf node TrieNode* temp = root; for (int i=0; word[i]; i++) { int position = (int) word[i] - 'a'; if (temp->children[position]) { temp = temp->children[position]; } } return temp->is_leaf; } TrieNode* delete_trie(TrieNode* root, char* word) { // Will try to delete the word sequence from the Trie only it // ends up in a leaf node if (!root) return NULL; if (!word || word[0] == '\0') return root; // If the node corresponding to the match is not a leaf node, // we stop if (!is_leaf_node(root, word)) { return root; } TrieNode* temp = root; // Find the longest prefix string that is not the current word char* longest_prefix = find_longest_prefix(root, word); //printf("Longest Prefix = %s\n", longest_prefix); if (longest_prefix[0] == '\0') { free(longest_prefix); return root; } // Keep track of position in the Trie int i; for (i=0; longest_prefix[i] != '\0'; i++) { int position = (int) longest_prefix[i] - 'a'; if (temp->children[position] != NULL) { // Keep moving to the deepest node in the common prefix temp = temp->children[position]; } else { // There is no such node. Simply return. free(longest_prefix); return root; } } // Now, we have reached the deepest common node between // the two strings. We need to delete the sequence // corresponding to word int len = strlen(word); for (; i < len; i++) { int position = (int) word[i] - 'a'; if (temp->children[position]) { // Delete the remaining sequence TrieNode* rm_node = temp->children[position]; temp->children[position] = NULL; free_trienode(rm_node); } } free(longest_prefix); return root; } void print_trie(TrieNode* root) { // Prints the nodes of the trie if (!root) return; TrieNode* temp = root; printf("%c -> ", temp->data); for (int i=0; ichildren[i]); } } void print_search(TrieNode* root, char* word) { printf("Searching for %s: ", word); if (search_trie(root, word) == 0) printf("Not Found\n"); else printf("Found!\n"); } int main() { // Driver program for the Trie Data Structure Operations TrieNode* root = make_trienode('\0'); root = insert_trie(root, "hello"); root = insert_trie(root, "hi"); root = insert_trie(root, "teabag"); root = insert_trie(root, "teacan"); print_search(root, "tea"); print_search(root, "teabag"); print_search(root, "teacan"); print_search(root, "hi"); print_search(root, "hey"); print_search(root, "hello"); print_trie(root); printf("\n"); root = delete_trie(root, "hello"); printf("After deleting 'hello'...\n"); print_trie(root); printf("\n"); root = delete_trie(root, "teacan"); printf("After deleting 'teacan'...\n"); print_trie(root); printf("\n"); free_trienode(root); return 0; } Output: Searching for tea: Not Found Searching for teabag: Found! Searching for teacan: Found! Searching for hi: Found! Searching for hey: Not Found Searching for hello: Found! -> h -> e -> l -> l -> o -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n -> After deleting 'hello'... -> h -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n -> After deleting 'teacan'... -> h -> i -> t -> e -> a -> b -> a -> g -> Q. Implement Binary Trie: #include #include #include #define ALPHABET_SIZE 26 struct node { int data; struct node* link[ALPHABET_SIZE]; }; struct node* root = NULL; struct node* create_node() { struct node *q = (struct node*) malloc(sizeof(struct node)); int x; for (x = 0; x < ALPHABET_SIZE; x++) q->link[x] = NULL; q->data = -1; return q; } void insert_node(char key[]) { int length = strlen(key); int index; int level = 0; if (root == NULL) root = create_node(); struct node *q = root; // For insertion of each String key, we will start from the root for (; level < length; level++) { index = key[level] - 'a'; if (q->link[index] == NULL) { q->link[index] = create_node(); // which is : struct node *p = create_node(); q->link[index] = p; } q = q->link[index]; } q->data = level; // Assuming the value of this particular String key is 11 } int search(char key[]) { struct node *q = root; int length = strlen(key); int level = 0; for (; level < length; level++) { int index = key[level] - 'a'; if (q->link[index] != NULL) q = q->link[index]; else break; } if (key[level] == '\0' && q->data != -1) return q->data; return -1; } int main(int argc, char **argv) { insert_node("by"); insert_node("program"); insert_node("programming"); insert_node("data structure"); insert_node("coding"); insert_node("code"); printf("Searched value: %d\n", search("code")); printf("Searched value: %d\n", search("geeks")); printf("Searched value: %d\n", search("coding")); printf("Searched value: %d\n", search("programming")); return 0; } Output: Searched value: 4 Searched value: -1 Searched value: 6 Searched value: 11