Data Structures and Algorithm
About
Data structures are fundamental components of computer science that allow for the organization and storage of data in a way that facilitates efficient access and modification. They are essential for designing and implementing algorithms and play a crucial role in the efficiency of software.
Here are some common data structures:
1. Arrays: A collection of elements stored in contiguous memory locations, with each element accessible by its index.
2. Linked Lists: A linear collection of elements, where each element points to the next one in the sequence.
3. Stacks: A Last In, First Out (LIFO) data structure, where elements are added and removed from the same end, known as the "top."
4. Queues: A First In, First Out (FIFO) data structure, where elements are added at the rear and removed from the front.
5. Trees: Hierarchical data structures with a root element and branches, where each node has a parent and zero or more children.
6. Graphs: A collection of nodes connected by edges, allowing for more complex relationships between elements.
7. Hash Tables: A data structure that maps keys to values, providing efficient data retrieval based on the key.
8. Heaps: A specialized tree-based data structure that satisfies the heap property, often used for priority queues.
9. Trie: A tree-like data structure used to store a dynamic set or associative array where the keys are usually strings.
10. Sets and Maps: Collections that store unique elements, where a set only contains elements, and a map associates keys with values.
Array:
Definition: An array is a collection of elements, each identified by an index or a key.
Structure: Elements are stored in contiguous memory locations.
Indexing: Elements are accessed using their index (starting from 0 in many programming languages).
Size: Fixed size in most languages (static arrays), or dynamic size (dynamic arrays).
Advantages:
Random Access: Constant time access to any element using its index.
Memory Efficiency: Contiguous memory allocation allows for efficient use of cache.
Disadvantages:
Fixed Size: Static arrays have a fixed size, making it challenging to change the size dynamically.
Insertion/Deletion: Can be inefficient since elements may need to be shifted when inserting or deleting elements.
Use Cases:
Storing and accessing a collection of elements with constant-time random access requirements.
Implementing mathematical matrices, vectors, etc.
Efficient storage of elements when the size is known and doesn't change frequently.
Arrays are a fundamental and versatile data structure used in various algorithms and applications. While they offer constant-time access to elements, their fixed size can be limiting in some scenarios, leading to the use of dynamic arrays or other data structures like linked lists when flexibility in size is required.
Basic operations in the Arrays
Insertion
Deletion
Searching
Display
Traverse and
Update.
Insertion
To insert an element at a specific position in an array, you can use the following general approach:
1. Create a new array with a size one greater than the original array.
2. Copy the elements from the original array to the new array up to the desired position.
3. Insert the new element at the desired position in the new array.
4. Copy the remaining elements from the original array to the new array.
Here's an example in cpp (C++): Code (Click on Code and Display the program)
Sample input and Output
Enter the size of an array: 5
Enter array elements:1 2 3 4 5
Enter the insertion index position of an array: 3
Enter element to be inserted: 30
New Array after Insertion:1 2 3 30 4 5
Algorithm
Input the size of the array (n) and the array elements.
Input the element to be deleted (num).
Search for the element in the array and delete it.
Searches for the element (num) in the array. If found, it shifts the elements to the left to overwrite the position of the element to be deleted.
Display the new array after deletion.
Prints the elements of the modified array after the deletion operation.
Delation
To Delate an element in an array, you can use the following general approach:
1. Deletion is nothing but process of remove an element from the array.
2. Here we have shifted the numbers of placed after the position from where the number is to be deleted, one place to the left of their existing positions.
Here's an example in cpp (C++): Code (Click on Code and Display the program)
Sample input and Output
Enter the size of an array: 5
Enter array elements:1 2 3 4 5
Enter the Delating element of an array: 3
New Array after Delation:1 2 4 5
Algorithm
1. Input the size of the array (n):
Prompt the user to enter the size of the array.
2. Input array elements:
Use a loop to input the elements of the array.
3. Input the element to be deleted (num):
Prompt the user to enter the element they want to delete.
4. Find the index of the element to be deleted:
Iterate through the array to find the index (i) where the element matches the user input (num).
5. Shift elements to the left to delete the element:
Use a loop to shift all elements from the index (i) to the end of the array one position to the left
6. Display the new array:
Use a loop to print the elements of the array after deletion.
Searching
Searching is an operation or a technique that helps finds the place of a given element or value in the list.
Any search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not.
Searching techniques
There are three types of searching in data structure and analysis
Linear Search
Binary Search
Interpolation Search
Linear Search
Linear search is a very simple search algorithm.
In this type of search, a sequential search is made over all items one by one.
Every item is checked and if a match is found then that particular item is returned.
Otherwise the search continues till the end of the data collection.
Here's an example in cpp (C++): Code (Click on Code and Display the program)
Sample input and Output
Enter the size of an array: 5
Enter array elements:1 2 3 4 5
Enter your searching value: 4
4 Found the location a[3]
Algorithm
1. Input the size of the array (n):
Prompt the user to enter the size of the array.
2. Input array elements:
Use a loop to input the elements of the array.
3. Input the value to be searched (num):
Prompt the user to enter the value they want to search for.
4. Search for the value in the array:
Use a loop to iterate through the array.
If the current element (a[i]) matches the search value (num), print the index and break out of the loop.
5. Display the result:
If the loop completes without finding the value (i == n), print a message indicating that the value was not found.
Binary Search
Binary search is a fast search algorithm with run-time complexity of O(log n).
This search algorithm works on the principle of divide and conquer. For this algorithm to work properly.
The data collection should be in the sorted form.
Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned.
If the middle item is greater than the item, then the item is searched in the sub-array to the right of the middle item.
Otherwise, the item is searched for in the sub-array to the left of the middle item.
The process continues on till the subarray reduces to zero.
Compare x with the middle element. If x matches with middle element, we return the mid index.
Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
Else (x is smaller) recur for the left half.
Here's an example in cpp (C++): Code (Click on Code and Display the program)
Sample input and Output
Enter the size of an array: 5
Enter array elements:1 2 3 4 5
Enter your searching value: 3
3 Found the location a[2]
Algorithm
1. Input:
The user is prompted to enter the size of the array (n).
The user is then asked to input the elements of the array (a).
2. Binary Search Algorithm:
The program initializes low to 0 and high to n-1, representing the search interval.
It calculates the initial value of mid as the average of low and high.
It enters a while loop as long as low is less than or equal to high.
3. Inside the loop:
If the element at the middle (a[mid]) is less than the target num, it means the target must be in the right half of the array. So, low is updated to mid + 1.
If a[mid] is equal to num, the target is found, and the program prints the index and exits the loop.
If a[mid] is greater than num, the target must be in the left half of the array. So, high is updated to mid - 1.
The value of mid is recalculated based on the new values of low and high.
4. Output:
If the while loop exits without finding the target (when low is greater than high), the program prints "Element not found."
Interpolation Search
Interpolation search is an improved variant of binary search.
This search algorithm works on the probing position of the required value.
For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.
Interpolation search usage
There are cases where the location of target data may be known in advance.
For example, in case of a telephone directory, if we want to search the telephone number of Morphius Here, linear search and even binary search will seem slow as we can directly jump to memory space where the names start from 'M' are stored
Here's an example in cpp (C++): Code (Click on Code and Display the program)
Sample input and Output
Enter the size of an array: 5
Enter array elements:1 2 3 4 5
Enter your searching value: 3
3 Found the location a[2]
Algorithm
1. Input:
The user is prompted to enter the size of the array (n).
The user then inputs the array elements.
The user is prompted to enter the element to be searched (e).
2. Array Initialization:
An array a of size n is declared and initialized with user-input elements.
3.Interpolation Search Initialization:
Variables start, end, and pos are initialized.
start represents the starting index of the search range.
end represents the ending index of the search range.
pos is calculated using the interpolation formula to estimate the probable position of the target element within the array.
4.Search Loop:
A while loop is used to iteratively search for the element e in the array.
Inside the loop, it checks if the current position pos is less than, equal to, or greater than the target element e.
If a[pos]< e it updates start and recalculates pos.
If a[pos] == e, it prints the index where the element is found and breaks out of the loop.
If a[pos] > e, it updates end and recalculates pos..
The loop continues until start becomes greater than end or the element is found.
5. Output:
If the element is found, it prints the index where the element is located.
If the element is not found, it prints a message indicating that the element is not in the array.