Data Structures and Algorithms Explained with Examples
Define Data Structures
With a neat diagram, explain the classification II Data Structure: It can be defined as a method of storing and organizing the data items in the computer’s memory. Mainly deal with:
- Storing data in memory
- Organizing data in memory
- Fetching and processing data
Write a Program in C for Stacks
Implement push, pop, and display operations for stacks using arrays. #include <stdio.h> int stk[10], ch, n, top=-1, item, i; void push() { if(top>=n-1) { printf(‘STACK is over flow’); } else { printf(‘Enter a value to be pushed:’); scanf(‘%d’, &item); top++; stk[top]=item; printf(‘Pushed successfully:’); } } void pop() { if(top == -1) { printf(‘Stack is under flow’); } else { printf(‘The popped elements is %d’, stk[top]); top–; } } void display() { if(top == -1) { printf(‘STACK is empty’); } else { printf(‘The elements in STACK’); for(i=top; i>=0; i–) printf(‘%d’, stk[i]); } } void main() { printf(‘Enter the size of STACK’); scanf(‘%d’, &n); for(;;) { printf(‘1.PUSH 2.POP 3.DISPLAY’); printf(‘Enter the Choice:’); scanf(‘%d’,&ch); switch(ch) { case 1: push(); break; case 2: pop(); break; case 3: display(); break; }…
Add Two Polynomials in C
Write the C function to add two polynomials. ANS :- 
Recursive C Functions for Binary Tree Traversals
Write recursive C functions for inorder, preorder, and postorder traversals of a binary tree. ANS :- void inorder(struct node *root) { if(root != NULL) { inorder(root->left); printf(‘%d’, root->data); inorder(root->right); } } Preorder: A B H E I C F G Postorder: D H I E B F G C A void preorder(struct node *root) { if(root != NULL) { printf(‘%d’, root->data); preorder(root->left); preorder(root->right); } } void postorder(struct node *root) { if(root != NULL) { postorder(root->left); postorder(root->right); printf(‘%d’, root->data); } }
C Functions for Doubly Linked List
i) Inserting a node at the beginning of a Doubly linked list ii) Deleting a node at the end of the Doubly linked list INSERT :- void insertfront() { ptr=createnode(); if(start==NULL) { ptr->left=ptr->right=NULL; start=last=ptr; } else { ptr->left=NULL; ptr->right=start; start->left=ptr; start=ptr; } } DELETION :- void deleteend() { temp=start; while(temp->right!=NULL) { temp=temp->right; } last=temp->left; last->right=NULL; temp->left=NULL; printf(‘element is deleted’); free(ptr); }
Chained Hashing Explained
Chained hashing, also known as separate chaining, is a technique used to resolve collisions in hash tables. Pros of Chained Hashing: 1. Simple Implementation 2. Efficient Insertion and Deletion 3. Dynamic Data Sets 4. Adaptability Cons of Chained Hashing: 1. Memory Overhead 2. Cache Inefficiency 3. Performance Degradation 4. Poor Worst-Case Performance
Dynamic Hashing Techniques
i) Dynamic hashing using directories ii) Directory less dynamic hashing. Dynamic hashing is a mechanism for dynamically adding and removing data buckets on demand. Dynamic hashing using directories: – It is a method of hashing in which the data structure grows and shrinks dynamically as records are added or removed. – It is also known as extendible hashing. – This method makes hashing dynamic, i.e., it allows insertion or deletion without resulting in poor performance. Buckets: The buckets are used to hash the actual data. Directories: They are the holders of pointers pointing towards these buckets. Each directory has a unique ID. Global Depth: They denote the number of bits which are used by the hash function to categorize the keys. Local Depth: It is associated with the buckets. Working: – Initialize the bucket depths and the global depth of the directories. – Convert data into a binary representation. – Consider the ‘global depth’ number of the least significant bits (LSBs) of data. – Map the data according to the ID of a directory. – Check if a bucket overflows or not. Directory less dynamic hashing: Also known as linear dynamic hashing. Directory less hashing assumes a continuous address space in the memory to hold all the records. Therefore, the directory is not needed. Thus, the hash function must produce the actual address of the page containing the key.
Hashing Functions and Examples
Define hashing. Explain different hashing functions with examples. Discuss the properties of a good hash function. A function that converts a given big number to a small integer value. The mapped integer value is used as an index in the hash table. hash Location = KEY %SIZE Types of Hash Functions: – Mid Square Hash Function – Division Hash Function – Folding Hash Function – Digit analysis – Converting keys to integers Division Method: In this method, we use modular arithmetic system to divide the key value by some integer divisor m (table size). x = 23, m = 10 then H(x) = (23 % 10) = 3 The key whose value is 23 is placed in 3rd location Fold-shifting: Here actual values of each part of the key are added. Example: The key is : 12345678, and the required address is of two digits, Then break the key into: 12, 34, 56, 78. Add these, we get 12 + 34 + 56 + 78 = 180 Ignore the first 1 we get 80 as the location (because it’s two digits) Fold-boundary: Here the reversed values of outer parts of the key are added. Example: The key is : 12345678, and the required address is of two digits, Then break the key into: 12 34 56 78 Reverse the keys 21, 34, 56, 87. Add these, we get 21 + 34 + 56 + 87 : 198, ignore the first 1 we get 98 as the location (Because digits are two) Digit Analysis: Here we make a statistical analysis of digits of the key, and select those digits (of fixed position) which occur quite frequently. For example, if the key is : 9861234. Here the third and fifth position digits occur quite frequently, then we choose the digits in these positions from the key. So we get, 62. Reversing it we get 26 as the address…