DSA Program in C
How is a Data Structure Implemented?
- The foundational terms of a data structure are the following terms. Data may be arranged using data structures to make it easier to use.
- Each data structure has an interface that represents the set of operations the data structure allows. An interface only gives a list of supported operations, the types of arguments that these operations can accept, and their return types.
- The definitions of the algorithms used in a data structure's operations are also supplied by the implementation, together with the internal representation of the data structure.
Characteristics of Data Structure
- Correctness of a Data Structure: The interface of a Data Structure should be implemented appropriately.
- Time Complexity: The operations on the data structure must be completed in the least amount of time.
- Space Complexity: A data structure action should need the least amount of memory.
Applications:
- Today experience three main problems due to growing complexity and data density.
- Consider a retail store's inventory of one million (106) goods. If an application is used to seek up a product each time it must search one of them 106 million items, and the search process takes longer. As data accumulates, this problem will only become worse.
- Processing speed: Although processor speed is quite fast, it hits a limit once there are one billion records of data.
- Multiple requests: Even the fastest server can't manage the number of numbers since hundreds of users can search a database on a web server at once.
- The solutions to the aforementioned problems come from data structures, which can arrange data such that not all things need to be searched for but just the relevant data can be found almost instantly.
Time Cases of Execution:
Examples for Execution Time to examine the relative execution speeds of different data structures, three basic cases are typically employed.
- Worst Situation: In this case, a certain data structure operation takes the largest amount of time possible to complete.
- Average Case: This case illustrates how long it typically takes to complete a data structure operation. If an operation takes (n) times to complete, then m operations will likewise take (n) times to complete. If an operation takes (n) times to complete, then (n) times represent the function of n.
- Best Case: If an operation on a data structure requires (n) time to complete, then the actual process may take up to (n) time, or the smallest possible amount of time for that operation to complete.
Algorithm
- An algorithm is a step-by-step process that describes a series of instructions that must be followed in a certain order in order to the intended result. In terms of data structures, algorithms fall into the following categories:
- Using search algorithms to look up a certain item in a database.
- Analysis of algorithms the execution time or running time of various operations on a data structure is the topic of analysis of algorithms. It adds an item to a data structure, modifies an item that already exists there, and removes an item that already exists from a data structure.
- An operation's running time may be defined as the number of computer commands that are executed for each operation.
- Since the precise running time varies from machine to computer, we normally examine every operation's running time as a function of n, where n is the number. Of items in a data structure processed by that operation.
Asymptotic Analysis:
- It is the process of calculating any operation's running time in mathematical computation units. For example, the running time of one operation can be calculated as f(n) and that of another as g(n2).
- As a result, the first operation's running time will increase linearly with n while the second operation's running time will increase exponentially with n. Similarly, if n is significantly small, the running times of both operations will be nearly same.
- The run the ing time complexity of an algorithm is typically expressed using the asymptotic notations shown below.
- Ο Notation
- Ω Notation
- θ Notation
- The core concepts of a data structure are those that are given below. Data may be structured using data structures in a way that makes. The Data Definition provides a list of certain data attributes.
- A data element should be able to be mapped to a traceable definition. Atomic Definition need to define by June the definition
- Accurate the definition must be unambiguous.
- The definition should be understandable and clear.
Data Type
- Internal Data Type Data types that have built-in support in a language are known as built-in data types. For instance, the majority of languages have the following built-in data types.
- Derived Data Types: Character, Strings, Floating (decimal numbers), Boolean (true, false), and Integers. Because they may be implemented in a variety of ways, derived data types are implementation independent.
- Implementation-independent produced by fusing basic or built-in data types with their corresponding operations. For instance, "Stack Queue," "List," and "Array."
Array Representation
- The index starts at zero.
- The array can accommodate eight elements because it is eight elements long.
- Each element can be retrieved using its index.
- For example, we may get the element at index 6 as 9.
- The following is a list of the basic operations an array is capable of.
- Insertion: Add a new element at a specific index.
- Erasing an element at a given index is deletion.
- Search: Use the provided index or the element's value to do a search.
- Update an element searching a specified index.
#include <stdio.h>
#include <string.h>
static void display(int intArray[], int length){
int i=0;
printf("Array : [");
for(i = 0; i < length; i++) {
/* display value of element at index i. */
printf(" %d ", intArray[i]); }
printf(" ]\n "); }
int main() {
int i = 0;
/* Declare an array */
int intArray[8];
// initialize elements of array n to 0
for ( i = 0; i < 8; i++ ) {
intArray[ i ] = 0; // set elements to default value of 0; }
printf("Array with default data.");
/* Display elements of an array.*/
display(intArray,8);
/* Operation : Insertion
Add elements in the array */
for(i = 0; i < 8; i++) {
/* place value of i at index i. */
printf("Adding %d at index %d\n",i,i);
intArray[i] = i; }
printf("\n");
printf("Array after adding data. ");
display(intArray,8);
/* Operation : Insertion
Element at any location can be updated directly */
int index = 5;
intArray[index] = 10;
printf("Array after updating element at index %d.\n",index);
display(intArray,8);
/* Operation : Search using index
Search an element using index.*/
printf("Data at index %d:%d\n" ,index,intArray[index]);
/* Operation : Search using value
Search an element using value.*/
int value = 4;
for(i = 0; i < 8; i++) {
if(intArray[i] == value ){
printf("value %d Found at index %d \n", intArray[i],i);
break;
}
}
return 0;
}
Linked List
- The LinkedList's link element comes first.
- Each link carries a data field and a next link field.
- Each link is connected to the one after it using the following link.
- The Last Link includes a null link to denote the conclusion of the list.
- The many kinds of linked lists are shown below.
- In a Simple Linked List, there is just forward-facing item navigation.
- You can access items in the double-linked list both forward and backward.
- In a circular linked list, the first element links to the last element as the previous item, and the first element links to the first element as the next item.
- The following is a list of the fundamental operations that a list can handle.
- Insertion: Add a new element to the list's first position.
- Deletion: the act of deleting the first item from the list.
- presenting a complete list
- Search: To find an element, use the provided key.
- Delete: To remove an element, press the designated key.
- There are two phases in Operation Deletion: 1. Obtain the URL that the First Connection has indicated is the temporary link.
- Direct the First Link to the Next Link of the Temporary Link.
- Navigation many operations, including delete and others like it, are built on operation navigation. It involves recursive steps. Obtain the initial links pointing link to the present link.
- If it is not null, show the current link.
- Pointing the Current Link to the Next Link of the Current Link will advance you to the following stage.
- Advanced Techniques the following is a list of list's advanced operations.
- Arranging a list in a certain manner recursively reverse a linked list.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
//is list empty
bool isEmpty(){
return head == NULL; }
int length(){
int length = 0;
struct node *current;
for(current = head; current!=NULL;
current = current->next){
length++;
}
return length; }
//find a link with given key
struct node* find(int key){
//start from the first link
struct node* current = head;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return NULL;
} else {
//go to next link
current = current->next; } }
//if data found, return the current Link
return current;
}
//delete a link with given key
struct node* delete(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next; } }
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
previous->next = current->next;
}
return current;
}
void sort(){
int i, j, k, tempKey, tempData ;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ;
next = head->next ;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data ;
current->data = next->data;
next->data = tempData ;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
current = current->next;
next = next->next;
}
}
}
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");
//print list
printList();
while(!isEmpty()){
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data); }
printf("\nList after deleting all items: ");
printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nRestored List: ");
printList();
printf("\n");
struct node *foundLink = find(4);
if(foundLink != NULL){
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}
delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);
if(foundLink != NULL){
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found."); }
printf("\n");
sort();
printf("List after sorting the data: ");
printList();
reverse(&head);
printf("\nList after reversing the data: ");
printList(); }
Output:
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[ ]
Restored List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1)
List after deleting an item:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data:
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Double Linked List:
- The link element, known as first and last, is present in the Double Linked List the next link field and data field are carried by each link.
- Using its next link will link each link to its next link each link is linked to its previous link using its previous link to mark the end of the list, the last reference contains a null reference.
- The main operations supported by the list are given below Insert: Inserting item at the beginning of the list.
- Delete: Removes an item from the top of the list. Insert Last: Inserts the item at the end of the list.
- Remove Last: Removes an item from the end of the list. Insert After: Inserts an item after the list item
- Delete: Use the button to remove an item from the list Show Forward: Shows the entire list forward.
- Show in reverse order: Shows the entire list in reverse order
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
int length(){
int length = 0;
struct node *current;
for(current = head; current!=NULL;
current = current->next){
length++;
}
return length;
}
//display the list in from first to last
void displayForward(){
//start from the beginning
struct node *ptr = head;
//navigate till the end of the list
printf("\n[ ");
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//display the list from last to first
void displayBackward(){
//start from the last
struct node *ptr = last;
//navigate till the start of the list
printf("\n[ ");
while(ptr != NULL){
//print data
printf("(%d,%d) ",ptr->key,ptr->data);
//move to next item
ptr = ptr ->prev;
printf(" ");
}
printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()){
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()){
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL){
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
//save reference to last link
struct node *tempLink = last;
//if only one link
if(head->next == NULL){
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
//return the deleted link
return tempLink;
}
//delete a link with given key
struct node* delete(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
current->prev->next = current->next;
}
if(current == last){
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int data){
//start from the first link
struct node *current = head;
//if list is empty
if(head == NULL){
return false;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return false;
} else {
//move to next link
current = current->next;
}
}
//create a link
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = key;
newLink->data = data;
if(current==last) {
newLink->next = NULL;
last = newLink;
} else {
newLink->next = current->next;
current->next->prev = newLink;
}
newLink->prev = current;
current->next = newLink;
return true; }
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nList (First to Last): ");
displayForward();
printf("\n");
printf("\nList (Last to first): ");
displayBackward();
printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();
printf("\nList , after deleting last record: ");
deleteLast();
displayForward();
printf("\nList , insert after key(4) : ");
insertAfter(4,7, 13);
displayForward();
printf("\nList , after delete key(4) : ");
delete(4);
displayForward();
}
Output:
List (First to Last):
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first):
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
List , after deleting first record:
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record:
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) :
[ (5,40) (4,1) (4,13) (3,30) (2,20) ]
List , after delete key(4) :
[ (5,40) (4,13) (3,30) (2,20) ]
Stack:
- A stack is a type of data structure that allows you to manipulate data at only one end. Only recently added data can be accessed.
- The push-stop operations are linked so that only the last element can be pushed (added to the stack) and popped (removed from the stack)
- A stack is also known as a LIFO (Last In First Out) data structure Basic Operations Two major stacking operations follow. Push the top stack element. Pop an item to pop an item off the top of the stack.
- Below are some of the other operations the stack supports. Peek to get the top item on the stack.
- isFull: Determines if the stack is full Empty: Determines if the stack is empty.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
// size of the stack
int size = 8;
// stack storage
int intArray[8];
// top of the stack
int top = -1;
// Operation : Pop
// pop item from the top of the stack
int pop() {
//retrieve data and decrement the top by 1
return intArray[top--];
}
// Operation : Peek
// view the data at top of the stack
int peek() {
//retrieve data from the top
return intArray[top];
}
//Operation : isFull
//return true if stack is full
bool isFull(){
return (top == size-1); }
// Operation : isEmpty
// return true if stack is empty
bool isEmpty(){
return (top == -1);
}
// Operation : Push
// push item on the top of the stack
void push(int data) {
if(!isFull()){
// increment top by 1 and insert data
intArray[++top] = data;
} else {
printf("Cannot add data. Stack is full.\n");
}
}
main() {
// push items on to the stack
push(3);
push(5);
push(9);
push(1);
push(12);
push(15);
printf("Element at top of the stack: %d\n" ,peek());
printf("Elements: \n");
// print stack data
while(!isEmpty()){
int data = pop();
printf("%d\n",data);
}
printf("Stack full: %s\n" , isFull()?"true":"false");
printf("Stack empty: %s\n" , isEmpty()?"true":"false");
}
Output
Element at top of the stack: 15
Elements:
15
12
1
9
5
3
Stack full: false
Stack empty: true
Queue:
- The main difference between Queue and Stack is that Queue is based on FIFO (First In First Out) principle whereas Stack is based on LIFO (Last In First Out) principle.
- Inserts and enqueues are basic operations that add elements to the end of a queue.
- Delete or Dequeue: First dequeue the item. This article uses arrays to implement queues.
- Below are some additional operations supported by queues? Peek to get the element at the beginning of the lineiis full Determines if the queueis fullisEmpty — make sure the queue is empty.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isEmpty(){
return itemCount == 0;
}
bool isFull(){
return itemCount == MAX;
}
int size(){
return itemCount;
}
void insert(int data){
if(!isFull()){
if(rear == MAX-1){
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX){
front = 0;
}
itemCount--;
return data; }
int main() {
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
// front : 0
// rear : 4
// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 3 5 9 1 12
insert(15);
// front : 0
// rear : 5
// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 3 5 9 1 12 15
int removeData(){
int data = intArray[front++];
if(front == MAX){
front = 0; }
itemCount--;
return data;
}
int main() {
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
if(isFull()){
printf("Queue is full!\n");
} int num = removeData();
printf("Element removed: %d\n",num);
insert(16);
insert(17);
insert(18);
printf("Element at front: %d\n",peek());
printf("----------------------\n");
printf("index : 5 4 3 2 1 0\n");
printf("----------------------\n");
printf("Queue: ");
while(!isEmpty()){
int n = removeData();
printf("%d ",n);
}
}
Output:
The queue is full!
Element removed: 3
Element at the front: 5
index : 5 4 3 2 1 0
Queue: 5 9 1 12 15 16
Tree:
- A tree represents nodes connected by edges. Binary search trees or binary trees are specifically mentioned.
- It stores data using a unique data structure called a binary tree. A unique feature of binary trees is that each node cannot have more than three children.
- moreDeletion is as fast on binary trees as on ordered arrays. The following are important terms related to trees.
- Path: A path is a series of nodes along an edge of a tree. Root: The root is the node at the top of the tree.
- Every tree has exactly one root and only one path from the root node to all other nodes.
- Parent node: A parent node can be accessed from any node except the root node a child node is a node below the specified node, connected by the bottom edge.
- Leaf node: A leaf node is a node that has no children Subtree: A subtree represents the descendants of a node. Visit: If the control is on a node, visiting means checking its value.
- Traverse: When traversing, nodes are traversed in the order specified. Level: A node's generations represented by its level. If the root node is level 0, its next child node level el 1.
- Key: The key is the value of the node used as the basis for searching for the node. Binary search trees have special behaviour
- A node's special behaviour has a lower value than its parent, and the node's right child must have a higher value than s parent The following basic major operations on the tree are called element operations
- Find: Find tree items. Embed - Embeds the component in the tree Preorder Traversal: Traverse the tree in the order specified.
- Traversing the tree in an irregular order is called inorder traversal Use postorder traversal to traverse the tree in a postorder fashion.
- Whenever a new component is to be added. First, locate where it belongs. If the data is less than the value, search for an empty location in the left subtree and insert the data
- .Otherwise, insert the data and search for an empty location.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL){
root = tempNode;
}else {
current = root;
parent = NULL;
while(1){
parent = current;
//go to left of the tree
if(data < parent->data){
current = current->leftChild;
if(current == NULL){
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else{
current = current->rightChild;
//insert to the right
if(current == NULL){
parent->rightChild = tempNode;
return;
} } } } }
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL)
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
}//else go to right tree
else{
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
return current;
}
void preOrder(struct node* root){
if(root!=NULL){
printf("%d ",root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
} }
void inOrder(struct node* root){
if(root!=NULL){
inOrder(root->leftChild);
printf("%d ",root->data);
inOrder(root->rightChild);
}
}
void postOrder(struct node* root){
if(root!=NULL){
postOrder(root->leftChild);
postOrder(root->rightChild);
printf("%d ",root->data); } }
void traverse(int traversalType){
switch(traversalType){
case 1:
printf("\nPreorder traversal: ");
preOrder(root);
break;
case 2:
printf("\nInorder traversal: ");
inOrder(root);
break; } }
int main()
{
insert(11);
insert(20);
insert(3);
insert(42);
insert(54);
insert(16);
insert(32);
insert(9);
insert(4);
insert(10);
struct node * temp = search(32);
if(temp!=NULL){
printf("Element found.\n");
printf("( %d )",temp->data);
printf("\n");
} else {
printf("Element not found.\n"); }
struct node *node1 = search(2);
if(node1!=NULL){
printf("Element found.\n");
printf("( %d )",node1->data);
printf("\n");
} else {
printf("Element not found.\n"); }
traverse(1);
traverse(2);
traverse(3);
}
Output:
Visiting elements: 11 20 42 Element found.(
32)
Visiting elements: 11 3 Element not found.
Preorder traversal: 11 3 9 4 10 20 16 42 32 54
Inorder traversal: 3 4 9 10 11 16 20 32 42 54
Postorder traversal: 4 10 9 3 16 32 54 42 20 11
Hash Table:
- Regardless of the size of the hash table, inserts and lookups are extremely quick with the Hash Table data structure. It uses an array as a storage medium and a hashing technique to create an index into which an element is to be inserted or from which it is to be found, making it nearly constant or O(1) Hash Table.
- Hashing is a technique for transforming a set of key values into a set of indexes for an array. To obtain a set of key values, we will make use of the modulo operator.
- Consider a 20-column hash table in which the following elements must be stored: The element has the format (key, value).fundamental operations A hash table's fundamental operations are listed below.
- Lookup: Search the hash table for an element.
- Insert is a function that adds a new element to the hash table. Delete is used to get rid of an item from the hash table.
- Data item define a data item with some data and a key that can be used to search the hash table. Process of searching whenever an element needs to be found. Find the element by using the passed key's hash code as an index in the array. If the element is missing, use linear probing to bring it forward.
- Whenever a new component is to be added. Find the index in the array by computing the hash code of the passed key and using that hash code as the index. If an element is found at the computed hash code, use linear probing to find an empty location.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 20
struct DataItem {
int data;
int key;
};
struct DataItem* hashArray[SIZE];
struct DataItem* dummyItem;
struct DataItem* item;
int hashCode(int key){
return key % SIZE;
}
struct DataItem *search(int key){
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=NULL){
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
void insert(int key,int data){
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] !=NULL &&
hashArray[hashIndex]->key != -1){
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
hashArray[hashIndex] = item; }
struct DataItem* delete(struct DataItem* item){
int key = item->key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=NULL){
if(hashArray[hashIndex]->key == key){
struct DataItem* temp = hashArray[hashIndex];
//assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp; }
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE; }
void display(){
int i=0;
for(i=0; i<SIZE; i++) {
if(hashArray[i] != NULL)
printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
else
printf(" ~~ ");
}
printf("\n");
}
int main(){
dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
dummyItem->data = -1;
dummyItem->key = -1;
insert(1, 20);
insert(2, 70);
insert(42, 80);
insert(4, 25);
insert(12, 44);
insert(14, 32);
insert(17, 11);
insert(13, 78);
insert(37, 97);
display();
item = search(37);
if(item != NULL){
printf("Element found: %d\n", item->data);
} else {
printf("Element not found\n");
}
delete(item);
item = search(37);
if(item != NULL){
printf("Element found: %d\n", item->data);
} else {
printf("Element not found\n");
}
}
Output:
An element found: 97
Element not found
Recursion:
- A programming language technique in which a function calls itself is called recursion. A recursive method is a function that calls itself In a recursive function, the following two characteristics must be present: base case(s) A set of rules that, after reducing the cases, result in a base case Recursive Factorial
- The factorial is one of the old-style illustrations of recursion. A factor is a non-negative number that satisfies the following conditions 0!=1
1!=1
n!= n * n-1!
- "!" stands for faculty. Rule 3 is the factorial rule, and rules 1 and 2 are the base cases The Fibonacci series is another famous example of recursion.
- The Fibonacci series is a set of integers that meet the following requirements Fibonacci is represented by the letter "F". F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 Rule 3 and Rule 1 are the Fibonacci rules and Rule 2 and Rule 1 are the base cases Example: F5 = 0 1, 1, 2, 3,