Semakin saya perhatikan bahwa orang otodidak modern benar-benar kekurangan materi. Semua orang tahu bahasa, tetapi sedikit dasar seperti tipe data atau algoritma. Sedikit tentang tipe data.
Kembali pada tahun 1976, ilmuwan Swiss
Nicklaus Wirth menulis buku
Algoritma + struktur data = program.40+ tahun kemudian, persamaan ini masih benar. Dan jika Anda orang yang belajar sendiri dan mempelajari artikel dalam waktu yang lama dalam pemrograman, Anda bisa melakukannya secara diagonal. Anda bisa membuat kode kopi.
Artikel ini juga akan memiliki pertanyaan yang dapat Anda dengar dalam wawancara.
Apa itu struktur data?
Struktur data adalah wadah yang menyimpan data dalam tata letak tertentu. "Layout" ini memungkinkan struktur data menjadi efektif dalam beberapa operasi dan tidak efektif pada yang lain.
Yang mana disana?
Linear , elemen membentuk urutan atau daftar linier, melewati node adalah linier. Contoh: Array. Daftar tertaut, tumpukan, dan antrian.
Non-linear , jika bypass node adalah non-linear, dan data tidak berurutan. Contoh: grafik dan pohon.
Struktur data dasar.
- Array
- Tumpukan
- Antrian
- Daftar terkait
- Hitungan
- Pohon
- Awalan pohon
- Hash meja
Array
Array adalah struktur data yang paling sederhana dan paling banyak digunakan. Struktur data lainnya, seperti tumpukan dan antrian, berasal dari array.
Gambar array sederhana ukuran 4 yang mengandung elemen (1, 2, 3, dan 4).
Setiap item data diberi nilai numerik positif (indeks), yang sesuai dengan posisi item dalam array. Sebagian besar bahasa mendefinisikan indeks awal array sebagai 0.
Ada
Satu dimensi , seperti yang ditunjukkan di atas.
Multidimensi , array di dalam array.
Operasi dasar
- Sisipkan-sisipkan elemen pada indeks yang diberikan
- Dapatkan-mengembalikan elemen pada indeks yang diberikan
- Hapus-hapus item pada indeks yang diberikan
- Ukuran-dapatkan jumlah total elemen dalam array
Pertanyaan
- Temukan elemen array minimum kedua
- Bilangan bulat non-berulang dalam array
- Gabungkan dua array yang diurutkan
- Menyusun ulang nilai-nilai positif dan negatif dalam sebuah array
Tumpukan
Tumpukan adalah tipe data abstrak, yang merupakan daftar elemen yang disusun berdasarkan prinsip LIFO (last last - first out, last come - first go).
Ini bukan array. Inilah gilirannya.
Diciptakan oleh Alan Thuring.Contoh tumpukan adalah sekelompok buku yang disusun secara vertikal. Untuk mendapatkan buku, yang berada di suatu tempat di tengah, Anda harus menghapus semua buku yang ditempatkan di sana. Inilah cara kerja metode LIFO (Last In First Out). Fungsi "Batal" dalam aplikasi berfungsi pada LIFO.
Gambar tumpukan, dalam tiga elemen (1, 2 dan 3), di mana 3 berada di atas dan akan dihapus terlebih dahulu.
Operasi dasar
- Push memasukkan item di atas
- Pop-mengembalikan elemen atas setelah mengeluarkan dari tumpukan
- isEmpty-mengembalikan true jika stack kosong
- Top-mengembalikan elemen atas tanpa menghapus dari tumpukan
Pertanyaan
- Terapkan antrian menggunakan tumpukan
- Sortir Nilai di Stack
- Menerapkan dua tumpukan dalam sebuah array
- Membalikkan string menggunakan tumpukan
Antrian
Seperti tumpukan, antrian menyimpan elemen secara berurutan. Perbedaan signifikan dari stack adalah penggunaan FIFO (First in First Out) dan bukan LIFO.
Contoh garis adalah garis orang. Yang terakhir mengambil yang terakhir dan Anda akan, dan yang pertama akan meninggalkannya terlebih dahulu.
Gambar antrian, dalam empat elemen (1, 2, 3 dan 4), di mana 1 berada di atas dan akan dihapus terlebih dahulu
Operasi dasar
- Enqueue—) - menyisipkan elemen di akhir antrian
- Dequeue () - menghapus elemen dari awal antrian
- isEmpty () - mengembalikan true jika antrian kosong
- Top () - mengembalikan elemen pertama dari antrian
Pertanyaan
- Menerapkan tumpukan menggunakan antrian
- Membalikkan elemen N pertama dalam antrian
- Menghasilkan angka biner dari 1 hingga N menggunakan antrian
Daftar tertaut
Daftar tertaut adalah larik di mana setiap elemen adalah objek yang terpisah dan terdiri dari dua elemen - data dan tautan ke simpul berikutnya.
Keuntungan utama dari array adalah fleksibilitas struktural: urutan elemen daftar tertaut mungkin tidak sesuai dengan urutan lokasi elemen data dalam memori komputer, dan urutan traversal daftar selalu ditentukan secara eksplisit oleh hubungan internalnya.
Ada
Searah , setiap node menyimpan alamat atau tautan ke simpul berikutnya dalam daftar dan simpul terakhir memiliki alamat atau tautan berikutnya sebagai NULL.
1-> 2-> 3-> 4-> NULL
Dua arah , dua tautan yang terkait dengan masing-masing simpul, satu dari poin kuat ke simpul berikutnya dan satu ke simpul sebelumnya.
NULL <-1 <-> 2 <-> 3-> NULL
Circular , semua node terhubung untuk membentuk lingkaran. Pada akhirnya tidak ada NULL. Daftar tertaut siklik dapat berupa daftar tertaut siklik tunggal atau ganda.
1-> 2-> 3-> 1
Daftar searah linear paling umum. Contohnya adalah sistem file.
Operasi dasar
- InsertAtEnd - Masukkan item yang ditentukan di akhir daftar.
- SisipkanAtHead - Menyisipkan item ke bagian atas daftar
- Hapus - menghapus item yang ditentukan dari daftar.
- DeleteAtHead - menghapus elemen pertama dari daftar
- Cari - mengembalikan item yang ditentukan dari daftar
- isEmpty - mengembalikan True jika daftar tertaut kosong
Pertanyaan
- Reverse Linked List
- Menentukan lingkaran dalam daftar tertaut
- Kembalikan item N dari ujung dalam daftar tertaut
- Hapus duplikat dari daftar tertaut
Hitungan
Grafik adalah seperangkat simpul (simpul) yang terhubung satu sama lain dalam bentuk jaringan dengan tepi (busur).
Ada
Berorientasi , tulang rusuknya terarah, mis. hanya ada satu arah yang tersedia antara dua simpul yang terhubung.
Tidak berorientasi , untuk masing-masing tulang rusuk Anda dapat pergi ke dua arah.
Campur
Ditemukan dalam bentuk seperti
- Matriks adjacency
- Daftar Adjacency
Algoritma traversal grafik umum
- Pencarian lebar - penjelajahan tingkat
- Pencarian mendalam - melintasi puncak
Pertanyaan
- Terapkan pencarian dengan lebar dan dalam
- Periksa apakah grafik itu pohon atau tidak
- Hitung jumlah tepi dalam grafik
- Temukan jalur terpendek antara dua puncak
Pohon
Pohon adalah struktur data hierarkis yang terdiri dari node (simpul) dan tepi (busur). Pohon pada dasarnya terhubung grafik tanpa loop.
Struktur pohon di mana-mana. Semua orang tahu pohon keterampilan dalam game.
Pohon sederhana
Jenis pohon
Pohon biner adalah yang paling umum.
“Pohon biner adalah struktur data hierarkis di mana setiap node memiliki nilai (juga merupakan kunci dalam kasus ini) dan referensi ke keturunan kiri dan kanan. »- ProcsTiga cara untuk berkeliling pohon
- Dalam urutan langsung (dari atas ke bawah) - bentuk awalan.
- Dalam urutan simetris (dari kiri ke kanan) - bentuk infiks.
- Dalam urutan terbalik (dari bawah ke atas) - bentuk postfix.
Pertanyaan
- Temukan ketinggian pohon biner
- Temukan N item terkecil di pohon pencarian biner
- Temukan node pada jarak N dari root
- Temukan leluhur simpul N di pohon biner
Trie (pohon awalan)
Semacam pohon untuk string, pencarian cepat. Kamus T9
Ini adalah bagaimana pohon semacam itu menyimpan kata-kata "atas", "demikian" dan "mereka".
Kata-kata disimpan dari atas ke bawah, node berwarna hijau "p", "s" dan "r" menunjuk ke ujung "atas", "demikian" dan "mereka".
Pertanyaan
- Hitung total jumlah kata
- Cetak semua kata
- Urutkan elemen array dari pohon awalan
- Buat Kamus T9
Hash meja
Hashing adalah proses yang digunakan untuk mengidentifikasi objek secara unik dan menyimpan setiap objek dalam indeks unik yang sudah dihitung sebelumnya (kunci).
Objek disimpan sebagai pasangan nilai kunci, dan kumpulan elemen-elemen tersebut disebut kamus. Setiap objek dapat ditemukan menggunakan kunci ini.
Intinya, ini adalah array di mana kunci direpresentasikan sebagai fungsi hash.
Tergantung kinerja
- Fungsi hash
- Ukuran Meja Hash
- Metode Manajemen Tabrakan
Contoh pencocokan hash dalam array. Indeks array ini dihitung melalui fungsi hash.
Pertanyaan
- Temukan pasangan simetris dalam array
- Cari apakah array adalah himpunan bagian dari array lain
- Jelaskan hashing terbuka
Daftar sumber daya
Alih-alih sebuah kesimpulan
Materi itu sama menariknya dengan bahasa itu sendiri. Mungkin seseorang akan melihat struktur dasar yang akrab dengannya dan tertarik.
Terima kasih sudah membaca. Saya harap tidak membuang waktu =)
PS: Saya minta maaf, ternyata terjemahannya sudah ada di sini dan baru-baru ini saya abaikan.
Jika tertarik, ini
dia , terima kasih
Hokum , aku akan lebih berhati-hati.