Struktur data paling populer

Apa itu struktur data?
Sederhananya, struktur data adalah wadah di mana data disimpan dalam tata letak tertentu (format, atau cara itu diatur dalam memori). "Layout" ini memungkinkan struktur data menjadi efektif dalam beberapa operasi dan tidak efektif pada yang lain. Tujuan Anda adalah untuk memahami struktur data sehingga Anda dapat memilih struktur data yang paling optimal untuk masalah yang dimaksud.

Mengapa kita membutuhkan struktur data?
Karena struktur data digunakan untuk menyimpan data secara terorganisir, dan karena data merupakan elemen paling penting dalam ilmu komputer, nilai sebenarnya dari struktur data jelas.
Apa pun masalah yang Anda pecahkan, Anda harus berurusan dengan data dengan satu atau lain cara - apakah itu gaji karyawan, harga saham, daftar belanja, atau bahkan direktori telepon sederhana.
Berdasarkan skenario yang berbeda, data harus disimpan dalam format tertentu. Kami memiliki beberapa struktur data yang mencakup kebutuhan untuk menyimpan data dalam format yang berbeda.


Struktur Data yang Umum Digunakan
Pertama-tama mari kita buat daftar struktur data yang paling umum digunakan, dan kemudian melihatnya satu per satu:
  • Array - Array
  • Tumpukan - Tumpukan
  • Antrian - Antrian
  • Linked Linked - Daftar Terkait
  • Pohon - Pohon
  • Grafik - grafik
  • Mencoba (mereka pada dasarnya adalah pohon, tetapi masih bagus untuk menamainya secara terpisah). - prioritas
  • Hash Tables - tabel hash


Array - Array
Array adalah struktur data yang paling sederhana dan paling banyak digunakan. Struktur data lainnya, seperti tumpukan dan antrian, berasal dari array.
Berikut adalah gambar array sederhana ukuran 4 yang mengandung elemen (1, 2, 3, dan 4).

gambar

Setiap item data diberi nilai numerik positif yang disebut indeks, yang sesuai dengan posisi item ini dalam array. Sebagian besar bahasa mendefinisikan indeks awal array sebagai 0.

Berikut ini adalah dua jenis array:
  • Array satu dimensi (seperti yang ditunjukkan di atas)
  • Array multidimensi (array dalam array) Array multi dimensi


Operasi dasar pada array.
Sisipkan - menyisipkan
elemen pada indeks yang ditentukan.
Hapus (Hapus) - menghapus elemen pada indeks yang ditentukan.
Ukuran - dapatkan jumlah total elemen dalam array.

Untuk belajar sendiri:
1 Temukan elemen minimum kedua array.
2. Bilangan bulat non-berulang dalam array.
3. Gabungkan dua array yang diurutkan.
4. Urutkan ulang nilai positif dan negatif dalam array.

Tumpukan
Kita semua akrab dengan opsi Undo (Cancel) yang terkenal, yang hadir di hampir setiap aplikasi. Pernah bertanya-tanya bagaimana cara kerjanya? Inti dari mekanisme ini adalah Anda menyimpan status sebelumnya dari pekerjaan Anda (yang dibatasi oleh jumlah tertentu) dalam memori sedemikian rupa sehingga tindakan terakhir muncul terlebih dahulu. Ini tidak dapat dilakukan dengan hanya array. Di situlah tumpukan berguna!

Contoh nyata tumpukan adalah tumpukan buku yang disusun secara vertikal. Untuk mendapatkan buku di tengah, Anda perlu menghapus semua buku yang diletakkan di atasnya. Inilah cara kerja metode LIFO (Last In First Out) .
Berikut adalah gambar tumpukan yang mengandung tiga elemen data (1, 2, dan 3), di mana 3 berada di atas dan akan dihapus terlebih dahulu:



Operasi dasar dengan tumpukan:
Push - menyisipkan elemen di atas yang lain.
Tarik (Pop) - mengembalikan elemen atas setelah penghapusan dari tumpukan.
Kosong? (IsEmpty) - mengembalikan true (true) jika tumpukan kosong.
Atas (Atas) - mengembalikan elemen atas tanpa menghapus dari tumpukan.

Untuk studi independen:
1. Evaluasi ekspresi postfix menggunakan stack.
2. Urutkan nilai pada tumpukan.
3. Periksa tanda kurung seimbang dalam ekspresi.

Antrian
Seperti tumpukan, antrian adalah struktur data linier lain di mana item disimpan secara berurutan. Satu-satunya perbedaan signifikan antara tumpukan dan antrian adalah bahwa alih-alih menggunakan metode LIFO, Antrian mengimplementasikan metodeFIFO, yang merupakan kependekan dari First in First Out .
Contoh kehidupan nyata yang sangat bagus: sejumlah orang menunggu di kantor tiket. Jika seseorang baru tiba, ia bergabung dengan garis dari akhir, dan bukan dari awal - dan orang yang berdiri di depan akan menjadi yang pertama menerima tiket dan, oleh karena itu, akan meninggalkan garis.
Berikut adalah gambar antrian yang berisi empat elemen data (1, 2, 3, dan 4), di mana 1 berada di atas dan akan dihapus terlebih dahulu:



Operasi dasar dengan antrian:
Enqueue - menyisipkan elemen di akhir antrian.
Dequeue - Menghapus item dari awal antrian.
Kosong? (IsEmpty) - mengembalikan true (true) jika antrian kosong.
Atas (Atas) - mengembalikan elemen pertama dari antrian.

Untuk studi independen:
1. Implementasi tumpukan menggunakan antrian.
2. Unsur k terbalik pertama dari antrian.
3. Pembuatan angka biner dari 1 hingga n menggunakan antrian.

Linked List Daftar
tertaut adalah struktur data linier penting lainnya yang sekilas mungkin terlihat mirip dengan array, tetapi berbeda dalam alokasi memori, struktur internal, dan bagaimana operasi penyisipan dan penghapusan dasar dilakukan.

Daftar tertaut seperti rantai simpul, di mana setiap simpul berisi informasi seperti data, dan penunjuk ke simpul berikutnya dalam rantai. Ada pointer header yang menunjuk ke elemen pertama dari daftar yang ditautkan, dan jika daftar itu kosong, maka itu hanya menunjuk ke nol atau tidak sama sekali.

Daftar tertaut digunakan untuk mengimplementasikan sistem file, tabel hash, dan daftar adjacency.

Berikut ini adalah representasi visual dari struktur internal daftar tertaut:



Berikut ini adalah jenis daftar tertaut:
  • Daftar Tautan Tunggal (Searah)
  • Daftar tertaut ganda (dua arah)


Operasi Dasar pada Daftar Tertaut
InsertAtEnd - Menyisipkan item di akhir daftar tertaut.
InsertB Start (InsertAtHead) - Menyisipkan item di awal daftar yang ditautkan.
Hapus - menghapus item ini dari daftar yang ditautkan.
DeleteBeginning (DeleteAtHead) - menghapus elemen pertama dari daftar yang ditautkan.
Cari - mengembalikan item yang ditemukan dari daftar tertaut.
Kosong? (IsEmpty) - mengembalikan true (true) jika daftar yang ditautkan kosong.

Untuk studi independen:
1. Balikkan daftar yang ditautkan (Balikkan, balikkan, tampilkan mundur).
2. Tentukan lingkaran dalam daftar yang ditautkan.
3. Kembalikan simpul N dari ujung dalam daftar tertaut.
4. Hapus duplikat dari daftar tertaut.

Grafik
Grafik adalah kumpulan node yang terhubung satu sama lain dalam bentuk jaringan. Node juga disebut simpul. Pasangan (x, y) disebut tepi, yang menunjukkan bahwa simpul x terhubung dengan simpul y. Tepi dapat berisi berat / biaya, menunjukkan berapa banyak biaya yang diperlukan untuk berpindah dari atas x ke y.



Jenis grafik:
  • Grafik tidak terarah
  • Grafik yang diarahkan


Dalam bahasa pemrograman, grafik direpresentasikan dalam dua bentuk:


Berikut ini adalah contoh dari Adjacency List yang bersebelahan (grafik tidak terarah).



Contoh algoritma bergerak yang diketahui di sepanjang grafik:


Untuk studi independen:
1. Implementasi Luas dan Kedalaman Pencarian pertama
2. Periksa apakah grafik tersebut pohon atau tidak.
3. Menghitung jumlah tepi dalam grafik.
4. Temukan jalur terpendek di antara puncak.

Pohon
Pohon adalah struktur data hierarkis yang terdiri dari simpul (simpul) dan tepi yang menghubungkannya. Pohon terlihat seperti grafik, tetapi titik kunci yang membedakan pohon dari grafik adalah bahwa loop tidak dapat eksis di pohon. Pohon adalah grafik yang sobek.

Pohon banyak digunakan dalam kecerdasan buatan dan algoritma kompleks untuk menyediakan mekanisme penyimpanan yang efisien untuk algoritma pemecahan masalah.

Berikut adalah gambar pohon sederhana dan istilah dasar yang digunakan dalam struktur data pohon:



Ada beberapa jenis pohon:

  • N-
  • (Balanced Tree)
  • (Binary Tree)
  • (Binary Search Tree)
  • AVL
  • - (Red Black Tree)
  • 2–3


Dari atas, Pohon Biner dan Pohon Pencarian Biner adalah pohon yang paling umum digunakan.

Untuk studi independen:
1. Temukan ketinggian pohon biner.
2. Temukan nilai maksimum kth di pohon pencarian biner.
3. Temukan node pada jarak "k" dari root.
4. Temukan leluhur dari simpul yang diberikan di pohon biner.

Contoh-contoh praktis:

1. Facebook: Setiap pengguna adalah simpul, dan dua orang berteman ketika ada keunggulan antara dua simpul. Juga rekomendasi kepada teman dihitung berdasarkan teori grafik.

2. Google Maps: Lokasi yang berbeda diwakili oleh puncak dan jalan diwakili oleh tepi, teori grafik digunakan untuk menemukan jalur terpendek antara dua puncak.

3. Jaringan transportasi: di dalamnya puncak adalah persimpangan jalan dan tulang rusuk - ini adalah segmen jalan di antara persimpangan mereka.

4. Representasi struktur molekul di mana simpul adalah molekul dan ujung-ujungnya adalah ikatan antara molekul.

5. Proses pensinyalan diskrit dalam grafik. ( dan ada artikel bagus di sini juga, dan ini sekaligus )

6. Pengamatan empiris menunjukkan bahwa sebagian besar gen diatur oleh sejumlah kecil gen lain, biasanya kurang dari sepuluh. Oleh karena itu, jaringan genetik dapat dianggap sebagai grafik jarang, yaitu grafik di mana sebuah node terhubung ke beberapa node lainnya. Jika grafik berorientasi (asiklik) atau grafik tidak terarah jenuh dengan probabilitas, hasilnya masing-masing adalah model grafis berorientasi probabilistik dan model grafis tidak diarahkan probabilistik.

7. Teori Mayer cluster memperluas fungsi volatilitasgas (Z) dalam termodinamika membutuhkan perhitungan dua, tiga, empat kondisi dan seterusnya. Ada cara sistematis untuk melakukan ini secara kombinatorial dengan grafik, dan ini membantu untuk mengetahui seberapa terhubung grafik tersebut. Mengetahui teori grafik dapat berguna ketika Anda ingin meringkas bagian dari diagram ini.

8. Pewarnaan peta: teorema empat warna yang terkenal menyatakan bahwa Anda selalu dapat mewarnai wilayah peta dengan benar sehingga tidak ada dua wilayah yang berdekatan diberi warna yang sama menggunakan tidak lebih dari empat warna berbeda. Dalam model ini, daerah dengan warna adalah simpul, dan kedekatan adalah tepi grafik.

9. Tugas dengan tiga pondok adalah teka-teki matematika yang terkenal. Dapat dirumuskan sebagai berikut: Tiga pondok di pesawat (atau bola), yang masing-masing harus terhubung ke perusahaan gas, air dan listrik. Masalahnya dipecahkan dengan menggunakan grafik di pesawat .

10. Cari pusat grafik: Untuk setiap titik, cari panjang jalur terpendek ke titik terjauh. Pusat grafik adalah titik yang nilainya minimal. Ini penting untuk perencanaan arsitektur pemukiman di mana rumah sakit, pemadam kebakaran atau kantor polisi harus ditempatkan sehingga titik terjauh sedekat mungkin.

Untuk pecinta C #, seperti saya, tautan dengan contoh kode grafik C # ada di sini. Untuk pustaka tercanggih dengan implementasi grafik di C ++ di sini . Untuk penggemar AI dan Skynet, injak-injak di sini .

Sequences (Trie)
Sequences, juga dikenal sebagai pohon dengan awalan (Prefix Trees), adalah struktur data seperti pohon yang cukup efektif untuk menyelesaikan masalah yang terkait dengan string. Mereka menyediakan pencarian cepat dan terutama digunakan untuk mencari kata-kata dalam kamus, kalimat otomatis di mesin pencari, dan bahkan untuk IP routing.

Berikut adalah ilustrasi tentang bagaimana tiga kata "atas", "dengan demikian", dan "mereka" disimpan dalam Prioritas:



Kata-kata disimpan dari atas ke bawah, di mana simpul hijau "p", "s" dan "r" menunjuk ke ujung "atas", " dengan demikian ", dan" mereka ", masing-masing.

Untuk studi independen:
1. Hitung jumlah total kata dalam Prioritas.
2. Cetak semua kata yang disimpan dalam Prioritas.
3. Mengurutkan elemen array menggunakan Prioritas.
4. Hasilkan kata-kata dari kamus menggunakan Antrian.
5. Buat kamus T9.

Contoh penggunaan praktis:
1. Pilihan dari kamus atau selesai saat mengetik kata.
2. Cari kontak di telepon atau kamus telepon.

Meja Hash
Hashing adalah proses yang digunakan untuk mengidentifikasi objek secara unik dan menyimpan setiap objek dengan beberapa indeks unik yang dihitung sebelumnya yang disebut "kunci" -nya. Dengan demikian, objek disimpan dalam bentuk pasangan kunci-nilai, dan kumpulan elemen-elemen tersebut disebut kamus. Setiap objek dapat ditemukan menggunakan kunci ini.

Ada berbagai struktur data berbasis hash, tetapi tabel hash adalah struktur data yang paling umum digunakan. Tabel hash digunakan ketika Anda perlu mengakses elemen dengan kunci, dan Anda bisa menentukan nilai kunci yang berguna.

Tabel hash biasanya diimplementasikan menggunakan array.

Kinerja hashing struktur data tergantung pada tiga faktor berikut:
  • Fungsi hash
  • Ukuran Meja Hash
  • Metode Pengolahan Tabrakan


Berikut ini adalah ilustrasi tentang bagaimana hash ditampilkan dalam array. Indeks array ini dihitung menggunakan fungsi hash.



Untuk studi independen:
1. Temukan pasangan simetris dalam array.
2. Ikuti jalur perjalanan lengkap.
3. Temukan apakah array adalah himpunan bagian dari array lain.
4. Periksa apakah array yang diberikan terpisah.

Di bawah ini adalah contoh kode penggunaan tabel hash di .Net

static void Main(string[] args)
        {
            Hashtable ht = new Hashtable
            {
                { "001", "Zara Ali" },
                { "002", "Abida Rehman" },
                { "003", "Joe Holzner" },
                { "004", "Mausam Benazir Nur" },
                { "005", "M. Amlan" },
                { "006", "M. Arif" },
                { "007", "Ritesh Saikia" }
            };

            if (ht.ContainsValue("Nuha Ali"))
            {
                Console.WriteLine("    !");
            }
            else
            {
                ht.Add("008", "Nuha Ali");
            }

            //   .
            ICollection key = ht.Keys;

            foreach (string k in key)
            {
                Console.WriteLine(k + ": " + ht[k]);
            }
            Console.ReadKey();
        }


Contoh-contoh praktis:

1. Game "Life". Di dalamnya, hash adalah seperangkat koordinat dari setiap sel hidup.

2. Versi primitif dari mesin pencari Google dapat memetakan semua kata yang ada menjadi satu set URL di mana mereka muncul. Dalam hal ini, tabel hash digunakan dua kali: pertama kali untuk memetakan kata-kata untuk set URL, dan, kedua kalinya, untuk menyimpan setiap set URL.

3. Ketika menerapkan struktur / algoritma multi jalur pohon, tabel hash dapat digunakan untuk akses cepat ke elemen turunan dari simpul internal.

4. Saat menulis program untuk bermain catur, sangat penting untuk melacak posisi yang telah dievaluasi sebelumnya, sehingga Anda dapat kembali ketika Anda membutuhkannya lagi jika perlu.

5. Bahasa pemrograman apa pun perlu memetakan nama variabel ke alamatnya dalam memori. Bahkan, dalam bahasa scripting seperti Javascript dan Perl, bidang dapat ditambahkan ke objek secara dinamis, yang berarti bahwa objek itu sendiri seperti peta hash.

All Articles