Jenis-jenis Struktur Data dalam Algoritma C++

July 20, 2022

Assalamu‘alaikum wr. wb.

Hello gais, Kembali lagi bersama Inzaghi's Blog! Dalam Algoritma, tentunya kita mengenal yang namanya Struktur Data. Jika untuk Pemula hanya mengenal Array dan Vector saja, ternyata yang lebih Algoritmik adalah seperti Linked List, Stack, Queue, dll. Kali ini kita akan membahas tentang Jenis-jenis Struktur Data dalam Algoritma C++.

Sumber Artikel : Medium.com (Towardsdatascience.com), Educative.io, dan Techvidvan.com

C++ adalah perpanjangan dari Bahasa Pemrograman C yang mendukung pembuatan kelas, maka dikenal sebagai "C dengan Class". Ini digunakan untuk membuat aplikasi berkinerja tinggi dan memberi kami kontrol tingkat tinggi atas sumber daya komputasi.

1. Array

Array adalah struktur dengan ukuran tetap, yang dapat menampung item dengan tipe data yang sama. Array diindeks, artinya akses acak dimungkinkan. Array biasanya disajikan sebagai struktur data asli dalam banyak bahasa pemrograman. Namun, orang tidak boleh mengacaukan array dengan list seperti struktur data dalam bahasa seperti Python. Mari kita lihat array disajikan dalam C++;

// deklarasi sederhana
int array[] = {1, 2, 3, 4, 5 };
// dalam bentuk pointer (mengacu pada objek yang disimpan di heap)
int * array = new int[5];

Ada array satu dimensi dan array multi dimensi. Nilai yang disimpan dalam array disebut elemen. Elemen disimpan dalam blok memori berurutan yang disebut indeks. Ukuran array ditentukan oleh jumlah elemen yang dikandungnya. Digambarkan adalah Array Satu dimensi dengan ukuran Enam.

Dalam kode ini, kami menginisialisasi sebuah array bernama Contoh yang menyimpan 200 pada indeks 0 dan 201 pada indeks 1.

#include <iostream>
using namespace std;

int main() {
    int Contoh[2];

    Contoh[0] = 200;
    Contoh[1] = 201;
}

Contoh lainnya untuk menginput Array :

#include <iostream>
using namespace std;

int main(){
    string arr[] = {"C1", "C2", "C3", "C4", "C5", "C6"};
    short ch;
    cout<<"Coose : ";
    cin>>ch;

    if (ch <= 6){
        cout<<arr[ch-1]<<endl;
    }
    else {
        cout<<"Invalid"<<endl;
    }

    return 0;
}

2. Vector

Sumber lainnya : Geeksforgeeks.org

Namun, kami terbiasa dengan struktur data vector<T> yang lebih ramah yang dapat kami dorong tanpa mengkhawatirkan ukurannya. Mari kita lihat bagaimana kita dapat mengimplementasikan salah satu dari list kita sendiri seperti struktur data yang akan mengubah ukurannya sendiri.

using namespace std;

class DynamicArray
{
private:
    int size_;
    int max_;
    int *arrayholder_;

public:
    DynamicArray()
    {
        this->size_ = 0;
        this->max_ = 5;
        this->arrayholder_ = new int[5];
    }

    ~DynamicArray()
    {
        delete[] this->arrayholder_;
    }

    int size()
    {
        return this->size_;
    }

    int& operator[](int i) 
    {
        assert(i < this->size_);
        return this->arrayholder_[i];
    }

    void add(int n)
    {
        if (this->max_ < this->size_ + 1)
        {
            this->max_ *= 2;
            int *tmp_ = new int[this->max_];

            for (size_t i = 0; i < this->size_; i++)
            {
                tmp_[i] = this->arrayholder_[i];
                
            }
            delete[] this->arrayholder_;
            this->arrayholder_ = tmp_;
            this->arrayholder_[this->size_] = n;
            this->size_ += 1;
        }
        else 
        {
            this->arrayholder_[this->size_] = n;
            this->size_ += 1;
        }
    }
};

int main(int argc, char **argv)
{
    DynamicArray darray;
      vector<int> varray;

    for (size_t i = 0; i <= 15; i++)
    {
        darray.add(i);
    }
    return 0;
}

Satu hal lagi yang perlu diperhatikan adalah bahwa kita menggunakan konstruktor dan destruktor. Ini karena kita memiliki pointer ke memori yang kita alokasikan saat array berkembang. Memori yang dialokasikan ini harus dilepaskan untuk menghindari overflow. Keindahan dari implementasi ini adalah bahwa pengguna tidak perlu tahu apa-apa tentang pointer jelek. Overloading operator[] memungkinkan akses yang diindeks seperti array asli. Memiliki pengetahuan ini, mari kita beralih ke struktur data berikutnya, daftar tertaut.

Atau Contoh lain dari Vector adalah :

#include <iostream>
#include <vector> 
using namespace std;
  
int main() {
    vector<int> g1;

    for (int i = 1; i <= 5; i++)
        g1.push_back(i);

    cout << "Output of begin and end : ";
    for (auto i = g1.begin(); i != g1.end(); ++i) {
        cout << *i << " ";
    }

    cout << "\nOutput of cbegin and cend : ";
    for (auto i = g1.cbegin(); i != g1.cend(); ++i) {
        cout << *i << " ";
    }
  
    cout << "\nOutput of rbegin and rend : ";
      for (auto ir = g1.rbegin(); ir != g1.rend(); ++ir) {
        cout << *ir << " ";
    }
  
    cout << "\nOutput of crbegin and crend : ";
    for (auto ir = g1.crbegin(); ir != g1.crend(); ++ir) {
        cout << *ir << " ";
    }
  
    return 0;
}

Output :

Output of begin and end : 1 2 3 4 5 
Output of cbegin and cend : 1 2 3 4 5 
Output of rbegin and rend : 5 4 3 2 1 
Output of crbegin and crend : 5 4 3 2 1

Contoh lainnya untuk menginput Array :

#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<string> v;
    v.push_back("C1");
    v.push_back("C2");
    v.push_back("C3");
    v.push_back("C4");
    v.push_back("C5");
    v.push_back("C6");

    short ch;
    cout<<"Coose : ";
    cin>>ch;
    
    if (ch <= 6){
        cout<<v[ch-1]<<endl;
    }
    else {
        cout<<"Invalid"<<endl;
    }

    return 0;
}

3. Linked List

Daftar Tertaut (Linked List) adalah struktur sekuensial yang terdiri dari urutan item dalam urutan linier yang dihubungkan satu sama lain. Anda hanya perlu mengetahui salah satu ujung rantai untuk melintasi struktur data ini. Dalam skenario di mana ukuran mengubah frekuensi, menggunakan array mungkin tidak menguntungkan kecuali data diakses secara acak (ekspansi dapat menyebabkan waktu penyalinan yang lebih tinggi dan menggunakan lebih banyak memori kecuali jika Anda menerapkan operasi penyusutan). Jadi Linked List dapat dianggap sebagai struktur data yang mendukung variasi ukuran yang sering dan akses berurutan.

Mari kita lihat implementasinya.

#include <iostream>
#include <vector> 
using namespace std;

template <typename T>
class Node {
    public:
    T value;
    Node *next;
    Node *previous;

    Node(T value) {
        this->value = value;
    }
};

template <typename T>
class LinkedList {
    private:
    int size_;
    Node<T> *head_ = NULL;
    Node<T> *tail_ = NULL;
    Node<T> *itr_ = NULL;

    public:
    LinkedList() {
        this->size_ = 0;
    }

    void append(T value) {
        if (this->head_ == NULL) {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        }
        else {
            this->tail_->next = new Node<T>(value);
            this->tail_->next->previous = this->tail_;
            this->tail_ = this->tail_->next;
        }
        this->size_ += 1;
    }

    void prepend(T value) {
        if (this->head_ == NULL) {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        }
        else {
            this->head_->previous = new Node<T>(value);
            this->head_->previous->next = this->head_;
            this->head_ = this->head_->previous;
        }
        this->size_ += 1;
    }

    Node<T> * iterate() {
        if (this->itr_ == NULL)  {
            this->itr_ = this->head_;
        } 
        else  {
            this->itr_ = this->itr_->next;
        }
        return this->itr_;
    }

    T ptr() {
        return this->itr_->value;
    }

    void resetIterator() {
        this->tail_ = NULL;
    }
};


int main(int argc, char **argv) {
    LinkedList<int> llist;
    llist.append(10);
    llist.append(12);
    llist.append(14);
    llist.append(16);
    llist.prepend(5);
    llist.prepend(4);
    llist.prepend(3);
    llist.prepend(2);
    llist.prepend(1);

    cout << "Printing Linked List" << endl;

    while(llist.iterate() != NULL) {
        cout << llist.ptr() << "\t";
    }
    cout << endl;

    return 0;
}

Di sini kita menggunakan struktur pendukung yang disebut Node/Simpul. Node ini akan membawa pointer ke item berikutnya dan item sebelumnya. Biasanya memiliki item berikutnya sudah cukup. Tetapi memiliki next dan before dapat meningkatkan kinerja append dan prepend karena kita memiliki akses O(1) ke kedua ujungnya. Menambahkan berarti kita akan memperbarui elemen penunjuk ekor berikutnya diikuti dengan memperbarui ekor menjadi item yang ditambahkan. Sebaliknya, prepending akan membuat elemen baru dan mengatur item berikutnya menjadi kepala saat ini. Perhatikan bahwa saya tidak menyertakan operasi pembersihan memori karena kita tidak berurusan dengan penghapusan eksplisit dan untuk membuat kode lebih sederhana. Namun, seseorang harus memilikinya di destruktor terpisah untuk menghindari kebocoran memori. Juga, kami menggunakan iterator sederhana hanya untuk mencetak item.

Untuk membaca Artikel lebih lanjut tentang Linked List, silakan lihat di sini.

4. Stack

Tumpukan adalah struktur LIFO (Last In First Out — elemen yang ditempatkan pada akhirnya dapat diakses terlebih dahulu). Meskipun struktur data ini memiliki perilaku yang berbeda, ini dapat dianggap sebagai turunan dari daftar tertaut dengan hanya kepala atau akses ke elemen teratas.

#include <iostream>
using namespace std;

template <typename T>
class Node {
public:
    T value;
    Node *next;

    Node(T value) {
        this->value = value;
    }
};

template <typename T>
class Stack {
private:
    int size_;
    Node<T> *top_ = NULL;
    Node<T> *itr_ = NULL;

public:
    Stack() {
        this->size_ = 0;
    }

    void push(T value) {
        if (this->top_ == NULL) {
            this->top_ = new Node<T>(value);
        }
        else {
            Node<T> *tmp = new Node<T>(value);
            tmp->next = this->top_;
            this->top_ = tmp;
        }
        this->size_ += 1;
    }

    Node<T> *pop() {
        Node<T> *tmp = this->top_;

        this->top_ = this->top_->next;
        this->size_ -= 1;
        return tmp;
    }

    Node<T> *peek() {
        return this->top_;
    }

    int size() {
        return this->size_;
    }

    Node<T> *iterate() {
        if (this->itr_ == NULL) {
            this->itr_ = this->top_;
        }
        else {
            this->itr_ = this->itr_->next;
        }
        return this->itr_;
    }


      T ptr() {
        return this->itr_->value;
    }

    void resetIterator() {
        this->itr_ = NULL;
    }
};

int main(int argc, char **argv) {
    Stack<int> stk1;
    stk1.push(10);
    stk1.push(12);
    stk1.push(14);
    stk1.push(16);
    stk1.push(5);
    stk1.push(4);
    stk1.push(3);
    stk1.push(2);
    stk1.push(1);

    cout << "Printing Stack" << endl;

    while (stk1.iterate() != NULL) {
        cout << stk1.ptr() << "\t";
    }
    
    cout << endl;
    return 0;
}

Perhatikan bahwa Node hanya memiliki referensi ke item berikutnya. Menambahkan item akan memperbarui bagian atas struktur data. Selanjutnya, penghapusan dan pengambilan dilakukan dari atas juga. Untuk ini, kami menggunakan metode pop() dan top() masing-masing.

4. Queue

Antrian adalah struktur FIFO (First In First Out — elemen yang ditempatkan pertama dapat diakses terlebih dahulu). Ini dapat dianggap sebagai skenario kebalikan dari stack. Dalam istilah yang lebih sederhana, ini adalah daftar tertaut tempat kami menambahkan dari satu ujung membaca dari ujung lainnya. Ini meniru line-up dunia nyata di jalan masuk. Di sini kita dapat memikirkan struktur Node sebagai berikut.

template <typename T>
class Node
{
    public:
    T value;
    Node *next;
    Node *previous;

    Node(T value)
    {
        this->value = value;
    }
};

Struktur data utama akan menjadi :

#include <iostream>
using namespace std;

template <typename T>
class Queue {
    private:
    int size_;
    Node<T> *head_ = NULL;
    Node<T> *tail_ = NULL;

    public:
    Queue() {
        this->size_ = 0;
    }

    void enqueue(T value) {
        if (this->head_ == NULL) {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        }
        else {
            this->tail_->next = new Node<T>(value);
            this->tail_->next->previous = this->tail_;
            this->tail_ = this->tail_->next;
        }
        this->size_ += 1;
    }

    Node<T> dequeue() {
        Node<T> *tmp = this->tail_;

        this->tail_ = this->tail->previous;
        this->tail_->next = NULL;
        this->size_ -= 1;
        return tmp;
    }
};

5. Tree

Ini adalah sedikit dari struktur data yang kompleks dan rumit. Pohon (Tree) dikenal sebagai himpunan elemen yang terbatas dan tidak kosong dalam istilah matematika. Pohon adalah struktur data hierarkis. Sebuah pohon mencakup banyak node. Struktur data ini mengikuti hubungan induk-anak. Ini bukan Struktur Data Linier seperti Array, Struktur, Daftar Tertaut (Linked List), dll. Ini adalah struktur data non-linear.

Untuk membaca Artikel lebih lanjut tentang Teori Tree, silakan lihat di sini.

6. Hash Table

Sumber lainnya : Geeksforgeeks.org

Tabel hash menyimpan pasangan kunci dan data. Mereka biasanya diimplementasikan menggunakan array, di mana setiap elemen memiliki nilai indeks uniknya sendiri untuk memungkinkan akses cepat. Meskipun Anda dapat menetapkan kunci (nilai integer) sebagai indeks untuk data, ini menjadi rumit dalam kasus kunci besar. Sebaliknya, teknik hashing digunakan untuk menghasilkan indeks untuk elemen.

Angka ini mewakili pasangan kunci dan data yang disimpan dalam Tabel Hash.

Teknik hashing menggunakan fungsi hash untuk mengubah kunci besar menjadi kunci yang lebih kecil yang kemudian dapat disimpan dalam tabel hash. Fungsi hash yang baik harus memenuhi kondisi berikut :

Mudah dihitung
Mendistribusikan data secara seragam (tanpa pengelompokan)
Meminimalkan tabrakan

Kinerja tabel hash tergantung pada ukuran tabel hash, fungsi hash yang digunakan, dan metode penanganan tabrakan.

Tabrakan adalah sesuatu yang kami coba hindari saat melakukan hashing. Tabrakan mengacu pada contoh di mana dua kunci berbeda yang diteruskan ke fungsi hash mengembalikan indeks yang sama. Kemungkinan tabrakan meningkat ketika kita berurusan dengan kunci besar. Metode penanganan tabrakan membantu mengatasi tabrakan, dan mencakup strategi umum berikut : Penyelidikan Linier (Linear Probing), Rantai, dan Pengubahan Ukuran Array.

Contoh Program :

#include<bits/stdc++.h>
using namespace std;

class Hash {
    int BUCKET;    // No. of buckets
 
    // Pointer to an array containing buckets
    list<int> *table;
public:
    Hash(int V);  // Constructor
 
    // inserts a key into hash table
    void insertItem(int x);
 
    // deletes a key from hash table
    void deleteItem(int key);
 
    // hash function to map values to key
    int hashFunction(int x) {
        return (x % BUCKET);
    }
 
      void displayHash();
};
 
Hash::Hash(int b) {
    this->BUCKET = b;
    table = new list<int>[BUCKET];
}
 
void Hash::insertItem(int key) {
    int index = hashFunction(key);
    table[index].push_back(key);
}
 
void Hash::deleteItem(int key) {
  // get the hash index of key
  int index = hashFunction(key);
 
  // find the key in (index)th list
  list <int> :: iterator i;
  for (i = table[index].begin();
           i != table[index].end(); i++) {
    if (*i == key)
      break;
  }
 
  // if key is found in hash table, remove it
  if (i != table[index].end())
    table[index].erase(i);
}
 
// function to display hash table
void Hash::displayHash() {
  for (int i = 0; i < BUCKET; i++) {
    cout << i;
    for (auto x : table[i])
      cout << " --> " << x;
    cout << endl;
  }
}
 
// Driver program
int main() {
  // array that contains keys to be mapped
  int a[] = {15, 11, 27, 8, 12};
  int n = sizeof(a)/sizeof(a[0]);
 
  // insert the keys into the hash table
  Hash h(7);   // 7 is count of buckets in
               // hash table
  for (int i = 0; i < n; i++)
    h.insertItem(a[i]); 
 
  // delete 12 from hash table
  h.deleteItem(12);
 
  // display the Hash table
  h.displayHash();
 
  return 0;
}

Output :

0
1 --> 15 --> 8
2
3
4 --> 11
5
6 --> 27

7. Graf

Grafik adalah struktur data non-linier. Mereka terdiri dari satu set simpul yang terbatas (yaitu node) yang dihubungkan oleh satu set tepi. Orde suatu graf mengacu pada jumlah simpul dalam graf tersebut. Ukuran grafik sesuai dengan jumlah sisinya.

Ilustrasi ini mewakili simpul dan tepi. Grafik juga merupakan grafik siklik. Graf adalah siklik jika setidaknya satu simpul memiliki jalur yang mengarah kembali ke dirinya sendiri.

Grafik sering digunakan untuk memodelkan hubungan kehidupan nyata dalam berbagai konteks mulai dari jaringan sosial hingga jaringan saraf.

Ada 3 (Tiga) jenis Graf yang umum :

Graf tak berarah : Graf yang semua sisinya dua arah
Graf berarah : Graf yang semua sisinya satu arah
Graf berbobot : Graf yang semua sisinya diberi nilai, disebut bobot

[Untuk membaca Artikel tentang Teori Graf, silakan lihat di sini.]

Semoga saja Artikel ini sangat bermanfaat bagi para IT Pemula. Terima Kasih 😄😘👌👍 :)

Wassalamu‘alaikum wr. wb.

Inzaghi's Blog (Legacy)

Jenis-jenis Struktur Data dalam Algoritma C++

Ads