Experiments Of Data Structure.docx

1. /* 2. * C Program Count the Number of Occurrences of an Element in the Linked List 3. * without using Recursion 4. */ 5. #include <stdio.h> 6. 7. int occur(int [], int, int); 8. 9. int main() 10. { 11.

int size, key, count;

12.

int list[20];

13.

int i;

14. 15.

printf("Enter the size of the list: ");

16.

scanf("%d", &size);

17.

printf("Printing the list:\n");

18.

for (i = 0; i < size; i++)

19.

{

20.

list[i] = rand() % size;

21.

printf("%d

", list[i]);

22.

}

23.

printf("\nEnter the key to find it's occurence: ");

24.

scanf("%d", &key);

25.

count = occur(list, size, key);

26.

printf("%d occurs for %d times.\n", key, count);

27.

return 0;

28. } 29. 30. int occur(int list[], int size, int key) 31. { 32.

int i, count = 0;

33. 34.

for (i = 0; i < size; i++)

35.

{

36.

if (list[i] == key)

37.

{

38.

count += 1;

39.

}

40.

}

41.

return count;

42. }

$ gcc occurnumber.c -o occurnumber $ a.out Enter the size of the list: 10 Printing the list: 3 6 7 5 3 5 6 2 9 Enter the key to find it's occurence: 3

1

3 occurs for 2 times.

// C++ program to detect loop in a linked list #include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = new 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; } // Returns true if there is a loop in linked list // else returns false. bool detectLoop(struct Node *h) { unordered_set s; while (h != NULL) { // If this node is already present // in hashmap it means there is a cycle // (Because you we encountering the // node for the second time). if (s.find(h) != s.end()) return true; // If we are seeing the node for // the first time, insert it in hash

s.insert(h); h = h->next; } return false; } /* Drier program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, push(&head, push(&head, push(&head,

20); 4); 15); 10);

/* Create a loop for testing */ head->next->next->next->next = head; if (detectLoop(head)) cout << "Loop found"; else cout << "No Loop"; return 0; } // This code is contributed by Geetanjali Copy CodeRun on IDE Output : Loop Found

* C Program to remove duplicates from a sorted linked list */ #include<stdio.h> #include<stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* The function removes duplicates from a sorted list */ void removeDuplicates(struct Node* head) { /* Pointer to traverse the linked list */

struct Node* current = head; /* Pointer to store the next pointer of a node to be deleted*/ struct Node* next_next; /* do nothing if the list is empty */ if (current == NULL) return; /* Traverse the list till last node */ while (current->next != NULL) { /* Compare current node with next node */ if (current->data == current->next->data) { /* The sequence of steps is important*/ next_next = current->next->next; free(current->next); current->next = next_next; } else /* This is tricky: only advance if no deletion */ { current = current->next; } } } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginging 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;

} } /* Drier program to test above functions*/ int main() { /* Start with the empty list */ struct Node* head = NULL; /* Let us create a sorted linked list to test the functions Created linked list will be 11->11->11->13->13->20 */ push(&head, 20); push(&head, 13); push(&head, 13); push(&head, 11); push(&head, 11); push(&head, 11); printf("\n Linked list before duplicate removal printList(head);

");

/* Remove duplicates from linked list */ removeDuplicates(head); printf("\n Linked list after duplicate removal "); printList(head); return 0; } Copy CodeRun on IDE Output: Linked list before duplicate removal 11 11 11 13 13 20 Linked list after duplicate removal 11 13 20

/* Program to split a circular linked list into two halves */ #include<stdio.h> #include<stdlib.h> /* structure for a node */ struct Node { int data; struct Node *next; }; /* Function to split a list (starting with head) into two lists. head1_ref and head2_ref are references to head nodes of the two resultant linked lists */

void splitList(struct Node *head, struct Node **head1_ref, struct Node **head2_ref) { struct Node *slow_ptr = head; struct Node *fast_ptr = head; if(head == NULL) return; /* If there are odd nodes in the circular list then fast_ptr->next becomes head and for even nodes fast_ptr->next->next becomes head */ while(fast_ptr->next != head && fast_ptr->next->next != head) { fast_ptr = fast_ptr->next->next; slow_ptr = slow_ptr->next; } /* If there are even elements in list then move fast_ptr */ if(fast_ptr->next->next == head) fast_ptr = fast_ptr->next; /* Set the head pointer of first half */ *head1_ref = head; /* Set the head pointer of second half */ if(head->next != head) *head2_ref = slow_ptr->next; /* Make second half circular */ fast_ptr->next = slow_ptr->next; /* Make first half circular */ slow_ptr->next = head; } /* UTILITY FUNCTIONS */ /* Function to insert a node at the begining of a Circular linked lsit */ void push(struct Node **head_ref, int data) { struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node)); struct Node *temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if(*head_ref != NULL) { while(temp->next != *head_ref)

temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given Circular linked list */ void printList(struct Node *head) { struct Node *temp = head; if(head != NULL) { printf("\n"); do { printf("%d ", temp->data); temp = temp->next; } while(temp != head); } } /* Driver program to test above functions */ int main() { int list_size, i; /* Initialize lists as empty */ struct Node *head = NULL; struct Node *head1 = NULL; struct Node *head2 = NULL; /* Created linked list will be 12->56->2->11 */ push(&head, 12); push(&head, 56); push(&head, 2); push(&head, 11); printf("Original Circular Linked List"); printList(head); /* Split the list */ splitList(head, &head1, &head2); printf("\nFirst Circular Linked List"); printList(head1); printf("\nSecond Circular Linked List"); printList(head2); getchar(); return 0; }

Copy CodeRun on IDE

Output: Original Circular Linked List 11 2 56 12 First Circular Linked List 11 2 Second Circular Linked List 56 12

/ A C++ program to demonstrate implementation of k stacks in a single // array in time and space efficient way #include #include using namespace std; // A C++ class class kStacks { int *arr; stacks int *top; stacks int *next;

to represent k stacks in a single array of size n // Array of size n to store actual content to be stored in // Array of size k to store indexes of top elements of // Array of size n to store next entry in all stacks // and free list

int n, k; int free; // To store beginning index of free list public: //constructor to create k stacks in an array of size n kStacks(int k, int n); // A utility function to check if there is space available bool isFull() { return (free == -1); } // To push an item in stack number 'sn' where sn is from 0 to k-1 void push(int item, int sn); // To pop an from stack number 'sn' where sn is from 0 to k-1 int pop(int sn); // To check whether stack number 'sn' is empty or not bool isEmpty(int sn) { return (top[sn] == -1); } }; //constructor to create k stacks in an array of size n kStacks::kStacks(int k1, int n1) { // Initialize n and k, and allocate memory for all arrays k = k1, n = n1;

arr = new int[n]; top = new int[k]; next = new int[n]; // Initialize all stacks as empty for (int i = 0; i < k; i++) top[i] = -1; // Initialize all spaces as free free = 0; for (int i=0; i
// Store index of first free slot

// Update index of free slot to index of next slot in free list free = next[i]; // Update next of top and then top for stack number 'sn' next[i] = top[sn]; top[sn] = i; // Put the item in array arr[i] = item; } // To pop an from stack number 'sn' where sn is from 0 to k-1 int kStacks::pop(int sn) { // Underflow check if (isEmpty(sn)) { cout << "\nStack Underflow\n"; return INT_MAX; }

// Find index of top item in stack number 'sn' int i = top[sn]; top[sn] = next[i];

// Change top to store next of previous top

// Attach the previous top to the beginning of free list next[i] = free; free = i; // Return the previous top item return arr[i]; } /* Driver program to test twStacks class */ int main() { // Let us create 3 stacks in an array of size 10 int k = 3, n = 10; kStacks ks(k, n); // Let us put some items in stack number 2 ks.push(15, 2); ks.push(45, 2); // Let us put some items in stack number 1 ks.push(17, 1); ks.push(49, 1); ks.push(39, 1); // Let us put some items in stack number 0 ks.push(11, 0); ks.push(9, 0); ks.push(7, 0); cout << "Popped element from stack 2 is " << ks.pop(2) << endl; cout << "Popped element from stack 1 is " << ks.pop(1) << endl; cout << "Popped element from stack 0 is " << ks.pop(0) << endl; return 0; } Copy CodeRun on IDE Output: Popped element from stack 2 is 45 Popped element from stack 1 is 39 Popped element from stack 0 is 7

Consider two stacks s1 & s2 ( we will be using STL stacks for implementation ). Enqueue Operation :: Simply push the element onto s1. Dequeue Operation :: Transfer all elements from s1 onto s2. Pop the top element from s2. Transfer remaining elements from s2 back to s1.

#include #include<stack> using namespace std;

// queue data structure using two stacks class queue { private : stack s1, s2; public

:

void enqueue(int element); int dequeue(); void displayQueue(); };

// enqueue an element to the queue void queue :: enqueue(int element) { s1.push(element); }

// dequeue the front element int queue :: dequeue() { // transfer all elements of s1 into s2 while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } // pop and store the top element from s2 int ret = s2.top(); s2.pop(); // transfer all elements of s2 back to s1 while (!s2.empty()) { s1.push(s2.top()); s2.pop();

} return ret; }

//display the elements of the queue void queue :: displayQueue() { cout<<"\nDisplaying the queue :-\n"; while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } while (!s2.empty()) { cout<<s2.top()<<" "; s1.push(s2.top()); s2.pop(); } }

// main int main() { queue q; q.enqueue(5); q.enqueue(11); q.enqueue(1); q.enqueue(7); q.enqueue(13); q.enqueue(11); q.displayQueue(); int dq_element = q.dequeue(); cout<<"\nAfter dequeing :-"; q.displayQueue(); cout<<endl; return 0;

} Displaying the queue :5 11 1 7 13 11 After dequeing :Displaying the queue :11 1 7 13 1

#include <stdio.h> #include <stdlib.h> /* A binary tree and a pointer struct node { int data; struct node* struct node* };

node has data, pointer to left child to right child */

left; 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); } /* Given two trees, return true if they are structurally identical */ int identicalTrees(struct node* a, struct 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 program to test identicalTrees function*/ int main() { struct node *root1 = newNode(1); struct 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); if(identicalTrees(root1, root2)) printf("Both tree are identical."); else printf("Trees are not identical."); getchar(); return 0; }

Both tree are identical.