Общие операции с различными структурами данных
Структура данных - это способ хранения данных в памяти компьютера, позволяющий легко и эффективно использовать их. Для хранения данных используются разные структуры данных. Его также можно определить как математическую или логическую модель конкретной организации элементов данных. Представление определенной структуры данных в основной памяти компьютера называется структурой хранения. Например: массив, стек, очередь, дерево, график и т. Д.
Operations on different Data Structure:
There are different types of operations that can be performed for the manipulation of data in every data structure. Some operations
are explained and illustrated below:
- Traversing: Traversing a Data Structure means to visit the element stored in it. This can be done with any type of DS.
Below is the program to illustrate traversal in an array:Array
// C++ program to traversal in an array
#include <iostream>
using
namespace
std;
// Driver Code
int
main()
{
// Initialise array
int
arr[] = { 1, 2, 3, 4 };
// size of array
int
N =
sizeof
(arr) /
sizeof
(arr[0]);
// Traverse the element of arr[]
for
(
int
i = 0; i < N; i++) {
// Print the element
cout << arr[i] <<
" "
;
}
return
0;
}
Stack
// C++ program to traversal in an stack
#include <bits/stdc++.h>
using
namespace
std;
// Function to print the elemen in stack
void
printStack(stack<
int
>& St)
{
// Traverse the stack
while
(!St.empty()) {
// Print top element
cout << St.top() <<
" "
;
// Pop top element
St.pop();
}
}
// Driver Code
int
main()
{
// Initialise stack
stack<
int
> St;
// Insert Element in stack
St.push(4);
St.push(3);
St.push(2);
St.push(1);
// Print elements in stack
printStack(St);
return
0;
}
Queue
// C++ program to traversal
// in an queue
#include <bits/stdc++.h>
using
namespace
std;
// Function to print the
// element in queue
void
printQueue(queue<
int
>& Q)
{
// Traverse the stack
while
(!Q.empty()) {
// Print top element
cout << Q.front() <<
" "
;
// Pop top element
Q.pop();
}
}
// Driver Code
int
main()
{
// Initialise queue
queue<
int
> Q;
// Insert element
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
// Print elements
printQueue(Q);
return
0;
}
LinkedList
// C++ program to traverse the
// given linked list
#include <bits/stdc++.h>
using
namespace
std;
struct
Node {
int
data;
Node* next;
};
// Function that allocates a new
// node with given data
Node* newNode(
int
data)
{
Node* new_node =
new
Node;
new_node->data = data;
new_node->next = NULL;
return
new_node;
}
// Function to insert a new node
// at the end of linked list
Node* insertEnd(Node* head,
int
data)
{
// If linked list is empty,
// Create a new node
if
(head == NULL)
return
newNode(data);
// If we have not reached the end
// Keep traversing recursively
else
head->next = insertEnd(head->next, data);
return
head;
}
/// Function to traverse given LL
void
traverse(Node* head)
{
if
(head == NULL)
return
;
// If head is not NULL,
// print current node and
// recur for remaining list
cout << head->data <<
" "
;
traverse(head->next);
}
// Driver Code
int
main()
{
// Given Linked List
Node* head = NULL;
head = insertEnd(head, 1);
head = insertEnd(head, 2);
head = insertEnd(head, 3);
head = insertEnd(head, 4);
// Function Call to traverse LL
traverse(head);
}
Output:1 2 3 4
- Searching: Searching means to find a particular element in the given data-structure. It is considered as successful when the required element is found. Searching is the operation which we can performed on data-structures like array, linked-list, tree, graph, etc.
Below is the program to illustrate searching an element in an array:
Array
// C++ program to searching in an array
#include <iostream>
using
namespace
std;
// Function that finds element K in the
// array
void
findElement(
int
arr[],
int
N,
int
K)
{
// Traverse the element of arr[]
// to find element K
for
(
int
i = 0; i < N; i++) {
// If Element is present then
// print the index and return
if
(arr[i] == K) {
cout <<
"Element found!"
;
return
;
}
}
cout <<
"Element Not found!"
;
}
// Driver Code
int
main()
{
// Initialise array
int
arr[] = { 1, 2, 3, 4 };
// Element to be found
int
K = 3;
// size of array
int
N =
sizeof
(arr) /
sizeof
(arr[0]);
// Function Call
findElement(arr, N, K);
return
0;
}
Stack
// C++ program to find element in stack
#include <bits/stdc++.h>
using
namespace
std;
// Function to find element in stack
void
findElement(stack<
int
>& St,
int
K)
{
// Traverse the stack
while
(!St.empty()) {
// Check if top is K
if
(St.top() == K) {
cout <<
"Element found!"
;
return
;
}
// Pop top element
St.pop();
}
cout <<
"Element Not found!"
;
}
// Driver Code
int
main()
{
// Initialise stack
stack<
int
> St;
// Insert Element in stack
St.push(4);
St.push(3);
St.push(2);
St.push(1);
// Element to be found
int
K = 3;
// Function Call
findElement(St, K);
return
0;
}
Queue
// C++ program to find given element
// in an queue
#include <bits/stdc++.h>
using
namespace
std;
// Function to find element in queue
void
findElement(queue<
int
>& Q,
int
K)
{
// Traverse the stack
while
(!Q.empty()) {
// Check if top is K
if
(Q.front() == K) {
cout <<
"Element found!"
;
return
;
}
// Pop top element
Q.pop();
}
cout <<
"Element Not found!"
;
}
// Driver Code
int
main()
{
// Initialise queue
queue<
int
> Q;
// Insert element
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
// Element to be found
int
K = 3;
// Print elements
findElement(Q, K);
return
0;
}
LinkedList
// C++ program to traverse the
// given linked list
#include <bits/stdc++.h>
using
namespace
std;
struct
Node {
int
data;
Node* next;
};
// Function that allocates a new
// node with given data
Node* newNode(
int
data)
{
Node* new_node =
new
Node;
new_node->data = data;
new_node->next = NULL;
return
new_node;
}
// Function to insert a new node
// at the end of linked list
Node* insertEnd(Node* head,
int
data)
{
// If linked list is empty,
// Create a new node
if
(head == NULL)
return
newNode(data);
// If we have not reached the end
// Keep traversing recursively
else
head->next = insertEnd(head->next, data);
return
head;
}
/// Function to traverse given LL
bool
traverse(Node* head,
int
K)
{
if
(head == NULL)
return
false
;
// If node with value K is found
// return true
if
(head->data == K)
return
true
;
return
traverse(head->next, K);
}
// Driver Code
int
main()
{
// Given Linked List
Node* head = NULL;
head = insertEnd(head, 1);
head = insertEnd(head, 2);
head = insertEnd(head, 3);
head = insertEnd(head, 4);
// Element to be found
int
K = 3;
// Function Call to traverse LL
if
(traverse(head, K)) {
cout <<
"Element found!"
;
}
else
{
cout <<
"Element Not found!"
;
}
}
Output:Element found!
- Insertion: It is the operation which we apply on all the data-structures. Insertion means to add an element in the given data structure. The operation of insertion is successful when the required element is added to the required data-structure. It is unsuccessful in some cases when the size of the data structure is full and when there is no space in the data-structure to add any additional element. The insertion has the same name as an insertion in the data-structure as an array, linked-list, graph, tree. In stack, this operation is called Push. In the queue, this operation is called Enqueue.
Below is the program to illustrate insertion in stack:
Array
// C++ program for insertion in array
#include <iostream>
using
namespace
std;
// Function to print the array element
void
printArray(
int
arr[],
int
N)
{
// Traverse the element of arr[]
for
(
int
i = 0; i < N; i++) {
// Print the element
cout << arr[i] <<
" "
;
}
}
// Driver Code
int
main()
{
// Initialise array
int
arr[4];
// size of array
int
N = 4;
// Insert elements in array
for
(
int
i = 1; i < 5; i++) {
arr[i - 1] = i;
}
// Print array element
printArray(arr, N);
return
0;
}
Stack
// C++ program for insertion in array
#include <bits/stdc++.h>
using
namespace
std;
// Function to print the element in stack
void
printStack(stack<
int
>& St)
{
// Traverse the stack
while
(!St.empty()) {
// Print top element
cout << St.top() <<
" "
;
// Pop top element
St.pop();
}
}
// Driver Code
int
main()
{
// Initialise stack
stack<
int
> St;
// Insert Element in stack
St.push(4);
St.push(3);
St.push(2);
St.push(1);
// Print elements in stack
printStack(St);
return
0;
}
Queue
// C++ program for insertion in queue
#include <bits/stdc++.h>
using
namespace
std;
// Function to print the
// element in queue
void
printQueue(queue<
int
>& Q)
{
// Traverse the stack
while
(!Q.empty()) {
// Print top element
cout << Q.front() << <
РЕКОМЕНДУЕМЫЕ СТАТЬИ