Общие операции с различными структурами данных

Опубликовано: 8 Января, 2022

Структура данных - это способ хранения данных в памяти компьютера, позволяющий легко и эффективно использовать их. Для хранения данных используются разные структуры данных. Его также можно определить как математическую или логическую модель конкретной организации элементов данных. Представление определенной структуры данных в основной памяти компьютера называется структурой хранения. Например: массив, стек, очередь, дерево, график и т. Д.

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