Struktur & Algoritma Data Teratas di Java yang Perlu Anda Ketahui



Blog ini mengenai Struktur Data dan Algoritma di Java akan membantu anda memahami semua struktur & algoritma data utama di Java.

Sekiranya saya harus memilih satu topik yang paling penting dalam pembangunan perisian, itu adalah struktur data dan algoritma. Anda boleh menganggapnya sebagai alat asas yang tersedia untuk setiap pengaturcara komputer. Semasa pengaturcaraan, kami menggunakan struktur data untuk menyimpan dan menyusun data, dan algoritma untuk memanipulasi data dalam struktur tersebut. Artikel ini mengandungi tinjauan terperinci mengenai semua struktur dan algoritma data umum di untuk membolehkan pembaca menjadi lengkap.

Berikut adalah topik yang dibincangkan dalam artikel ini:





Struktur Data di Jawa

Struktur data adalah cara menyimpan dan menyusun data dalam komputer sehingga dapat digunakan dengan cekap. Ini menyediakan kaedah untuk menguruskan sejumlah besar data dengan cekap. Dan struktur data yang cekap adalah kunci untuk merancang algoritma yang cekap.

Dalamartikel 'Struktur Data dan Algoritma di Java' ini, kami akan merangkumi struktur data asas seperti:



Mari lihat masing-masing.

Struktur Data Linear di Jawa

Struktur data linear di adalah mereka yang unsurnya berurutan dan disusun sedemikian rupa sehingga: hanya ada satu elemen pertama dan hanya mempunyai satu elemen seterusnya , hanya ada satu elemen terakhir dan hanya mempunyai satu elemen sebelumnya , sementara semua elemen lain mempunyai seterusnya dan a sebelumnya unsur.

Susunan

Seorang susunan adalah struktur data linearmewakili sekumpulan elemen serupa, diakses oleh indeks. Saiz array mesti disediakan sebelum menyimpan data. Di bawah adalah sifat array:



  • Setiap elemen dalam array mempunyai jenis data yang sama dan mempunyai ukuran yang sama
  • Elemen array disimpan di lokasi memori bersebelahan dengan elemen pertama bermula di lokasi memori terkecil
  • Unsur-unsur larik dapat diakses secara rawak
  • Struktur data array tidak sepenuhnya dinamik

Susunan - Edureka

Sebagai contoh , kami mungkin mahu permainan video mengikuti skor sepuluh teratas untuk permainan itu. Daripada menggunakan sepuluh yang berbeza pemboleh ubah untuk tugas ini, kita boleh menggunakan satu nama untuk keseluruhan kumpulan dan menggunakan nombor indeks untuk merujuk kepada skor tinggi dalam kumpulan itu.

Senarai Terpaut

KE adalah struktur data linear dengan pengumpulan pelbagai nod, di mana eelemen ach menyimpan datanya sendiri dan penunjuk ke lokasi elemen seterusnya. Pautan terakhir dalam senarai yang dipautkan menunjuk ke nol, yang menunjukkan akhir rantaian. Elemen dalam senarai terpaut disebut a simpul . Node pertama dipanggil kepala .Node terakhir dipanggilyang ekor .

Jenis Senarai Terpaut

Senarai Terhubung Sendiri (Uni-Directional)

atur cara penggabungan sederhana di c ++

Senarai Berganda Berganda (Dua Hala)

Senarai Berkaitan Pekeliling

Berikut adalah contoh mudah: Bayangkan senarai terpaut seperti rantai klip kertas yang dihubungkan bersama. Anda boleh menambahkan klip kertas lain ke bahagian atas atau bawah dengan mudah. Lebih pantas memasukkannya di bahagian tengah. Yang harus anda lakukan hanyalah memutuskan sambungan rantai di tengahnya, menambah klip kertas baru, kemudian sambungkan semula separuh yang lain. Senarai terpaut serupa.

Tumpukan

Timbunan, struktur data abstrak, adalah koleksi benda yang dimasukkan dan dikeluarkan mengikut terakhir-dalam-pertama-keluar (LIFO) prinsip. Objek dapat dimasukkan ke dalam tumpukan kapan saja, tetapi hanya objek yang terakhir dimasukkan (yaitu, 'terakhir') yang dapat dikeluarkan setiap saat.Di bawah adalah sifat timbunan:

  • Ini adalah senarai pesanan di manapenyisipan dan penghapusan boleh dilakukan hanya pada satu hujung yang disebut bahagian atas
  • Struktur data rekursif dengan penunjuk ke elemen teratasnya
  • Mengikuti terakhir-dalam-pertama-keluar (LIFO) prinsip
  • Menyokong dua kaedah paling asas
    • tolak (e): Masukkan elemen e, ke bahagian atas timbunan
    • pop (): Keluarkan dan kembalikan elemen teratas pada timbunan

Contoh praktik timbunan termasuk ketika membalikkan perkataan,untuk memeriksa kebenaran kurunganurutan,melaksanakan fungsi kembali dalam penyemak imbas dan banyak lagi.

Beratur

juga jenis struktur data abstrak yang lain. Tidak seperti tumpukan, barisan adalah kumpulan objek yang dimasukkan dan dikeluarkan mengikut first-in-first-out (FIFO) prinsip. Artinya, elemen dapat disisipkan kapan saja, tetapi hanya elemen yang paling lama berada dalam barisan yang dapat dihapus kapan saja.Di bawah adalah sifat-sifat giliran:

  • Selalunya disebut sebagai pertama masuk, pertama keluar senarai
  • Menyokong dua kaedah paling asas
    • enqueue (e): Masukkan elemen e, di belakang dari barisan
    • dequeue (): Keluarkan dan kembalikan elemen dari depan dari barisan

Antrian digunakan dipemindahan data tidak segerak antara dua proses, penjadwalan CPU, Penjadualan Disk dan situasi lain di mana sumber dikongsi di antara beberapa pengguna dan dilayan berdasarkan pelayan pertama. Selanjutnya dalam artikel ‘Struktur Data dan Algoritma di Jawa’ ini, kami mempunyai struktur data hierarki.

Struktur Data Hierarki di Jawa

Pokok Perduaan

Pokok Binari adalahstruktur data pokok hierarki di mana setiap nod mempunyai maksimum dua orang anak , yang disebut sebagai anak kiri dan juga anak yang betul . Setiap pokok binari mempunyai kumpulan nod berikut:

  • Node Akar: Ia adalah simpul paling atas dan sering disebut sebagai simpul utamakerana semua nod lain dapat dicapai dari akar
  • Sub-Tree Kiri, yang juga merupakan pokok binari
  • Sub-Pokok Kanan, yang juga merupakan pokok binari

Disenaraikan di bawah adalah sifat pokok binari:

  • Pokok binari boleh dilalui dengan dua cara:
    • Pelayaran Pertama Kedalaman : Dalam urutan (Kiri-Root-Kanan), Praorder (Root-Kiri-Kanan) dan Postorder (Kiri-Kanan-Akar)
    • Melintang Pertama : Melintang Perintah Tahap
  • Kerumitan Masa Melintasi Pokok: O (n)
  • Bilangan nod maksimum pada tahap ‘l’ = 2l-1.

Aplikasi pokok binari merangkumi:

  • Digunakan dalam banyak aplikasi carian di mana data sentiasa masuk / keluar
  • Sebagai aliran kerja untuk menyusun gambar digital untuk kesan visual
  • Digunakan di hampir setiap penghala lebar jalur tinggi untuk menyimpan jadual penghala
  • Juga digunakan dalam rangkaian tanpa wayar dan peruntukan memori
  • Digunakan dalam algoritma pemampatan dan banyak lagi

Timbunan binari

Binary Heap adalah lengkappokok binari, yang menjawab harta timbunan. Secara ringkasnyaadalah variasi pokok binari dengan sifat berikut:

  • Tumpukan adalah pokok binari lengkap: Pokok dikatakan lengkap jika semua peringkatnya, kecuali mungkin yang paling dalam, lengkap. Tharta miliknya Binary Heap menjadikannya sesuai untuk disimpan di sebuah .
  • Mengikuti harta timbunan: Binary Heap adalah sama ada a Tumpukan Min atau a Tumpukan Maksimum .
    • Tumpukan Perduaan Min: Fatau setiap nod dalam timbunan, nilai nod adalah kurang daripada atau sama dengan nilai-nilai anak-anak
    • Tumpukan Perduaan Maksimum: Fatau setiap nod dalam timbunan, nilai simpulnya adalah lebih besar daripada atau sama dengan nilai-nilai anak-anak

Aplikasi timbunan binari yang popular termasukmelaksanakan barisan keutamaan yang cekap, mencari elemen k terkecil (atau terbesar) dalam array dan banyak lagi.

Jadual Hash

Bayangkan bahawa anda mempunyai objek dan anda mahu memberikan kunci untuk menjadikan carian sangat mudah. Untuk menyimpan pasangan kunci / nilai itu, anda boleh menggunakan susunan sederhana seperti struktur data di mana kunci (bilangan bulat) dapat digunakan secara langsung sebagai indeks untuk menyimpan nilai data. Namun, dalam kasus di mana kunci terlalu besar dan tidak dapat digunakan secara langsung sebagai indeks, teknik yang disebut hashing digunakan.

Dalam hashing, kunci besar diubah menjadi kunci kecil dengan menggunakan fungsi hash . Nilai kemudian disimpan dalam struktur data yang dipanggilke jadual hash. Jadual hash adalah struktur data yang menerapkan kamus ADT, struktur yang dapat memetakan kunci unik ke nilai.

Secara umum, jadual hash mempunyai dua komponen utama:

  1. Susunan Baldi: Susunan baldi untuk tabel hash adalah susunan A berukuran N, di mana setiap sel A dianggap sebagai 'baldi', iaitu kumpulan pasangan nilai-kunci. Nombor bulat N menentukan kapasiti larik.
  2. Fungsi Hash: Fungsi apa pun yang memetakan setiap kunci k dalam peta kita menjadi bilangan bulat dalam julat [0, N & minus 1], di mana N adalah kapasiti array baldi untuk jadual ini.

Ketika kita memasukkan objek ke hashtable, ada kemungkinan objek yang berlainan mungkin mempunyai kod hash yang sama. Ini dipanggil a perlanggaran . Untuk menangani perlanggaran, ada teknik seperti merantai dan menangani terbuka.

Jadi, ini adalah beberapa struktur data asas dan paling kerap digunakan di Java. Sekarang setelah anda mengetahui setiap perkara ini, anda boleh mula melaksanakannya di dalam . Dengan ini, kami telah menyelesaikan bahagian pertama artikel 'ini' Struktur Data dan Algoritma di Java '. Pada bahagian seterusnya, kita akan belajaralgoritma asas dan cara menggunakannya dalam aplikasi praktikal seperti menyusun dan mencari, membahagi dan menakluk, algoritma tamak, pengaturcaraan dinamik.

Algoritma di Jawa

Secara historis digunakan sebagai alat untuk menyelesaikan pengiraan matematik yang kompleks, algoritma sangat berkaitan dengan sains komputer, dan struktur data khususnya. Algoritma ialah urutan arahan yang menerangkan cara menyelesaikan masalah tertentu dalam jangka masa yang terhad. Mereka dilambangkan dengan dua cara:

  • Carta alir - Ia adalahperwakilan visual aliran kawalan algoritma
  • Pseudokod - Iniadalah representasi teks algoritma yang menghampiri kod sumber akhir

Catatan: Prestasi algoritma diukur berdasarkan kerumitan masa dan kerumitan ruang. Sebilangan besarnya, kerumitan algoritma bergantung kepada masalah dan algoritma itu sendiri.

Mari kita teliti dua kategori algoritma utama di Java, iaitu:

Menyusun Algoritma di Jawa

Algoritma penyortiran adalah algoritma yang meletakkan unsur-unsur senarai dalam urutan tertentu. Pesanan yang paling biasa digunakan ialah urutan berangka dan urutan leksikografi. Dalam artikel ‘Struktur Data dan Algoritma’ ini, mari meneroka beberapa algoritma penyusun.

Bubble Sort di Jawa

Bubble Sort, yang sering disebut sebagai sinking sort, adalah algoritma penyusun paling mudah. Ia berulang kali melalui senarai yang akan disusun, membandingkan setiap pasangan elemen bersebelahan dan menukarnya jika berada dalam urutan yang salah.Jenis gelembung mendapat namanya kerana ia menyaring elemen ke bahagian atas larik, seperti gelembung yang terapung di atas air.

Inilahpseudocode mewakili Algoritma Bubble Sort (konteks jenis menaik).

a [] ialah susunan ukuran N mula BubbleSort (a []) menyatakan bilangan bulat i, j untuk i = 0 hingga N - 1 untuk j = 0 hingga N - i - 1 jika [j]> a [j + 1 ] kemudian tukar [j], akhir [j + 1] jika akhir untuk mengembalikan BubbleSort akhir

Kod ini memerintahkan susunan satu dimensi item data N ke urutan menaik. Gelung luar menjadikan N-1 melepasi array. Setiap lulus menggunakan gelung dalam untuk menukar item data sehingga item data terkecil berikutnya 'gelembung' menjelang permulaan array. Tetapi masalahnya ialah algoritma memerlukan satu keseluruhan lulus tanpa pertukaran untuk mengetahui bahawa senarai disusun.

Kerumitan Masa Kes Terburuk dan Purata: O (n * n). Perkara terburuk berlaku apabila larik disusun terbalik.

Kerumitan Masa Kes Terbaik: O (n). Kes terbaik berlaku apabila array sudah disusun.

Pilihan Susun di Jawa

Pemilihan pemilihan adalah gabungan antara pencarian dan penyortiran. Algoritma menyusun array dengan berulang kali mencari elemen minimum (mempertimbangkan urutan menaik) dari bahagian yang tidak disusun dan meletakkannya pada kedudukan yang tepat dalam array.

Berikut adalah pseudocode yang mewakili Selection Sort Algorithm (konteks jenis menaik).

a [] ialah susunan ukuran N mulakan SelectionSort (a []) untuk i = 0 hingga n - 1 / * tetapkan elemen semasa minimum * / min = i / * cari elemen minimum * / untuk j = i + 1 ke n jika senarai [j]

Seperti yang anda fahami dari kodnya, berapa kali urutan melewati array adalah lebih kecil daripada jumlah item dalam array. Gelung dalam mencari nilai terkecil seterusnya dan gelung luar meletakkan nilai ke lokasi yang sepatutnya. Pemilihan pilihan tidak akan membuat lebih banyak daripada pertukaran O (n) dan boleh berguna ketika memori menulis adalah operasi yang mahal.

Kerumitan Masa: O (n2) kerana terdapat dua gelung bersarang.

Ruang Bantu: Atau (1).

Penyisipan Penyisipan di Java

Penyisipan Penyisipan adalah algoritma penyortiran sederhana yang berulang melalui senarai dengan menggunakan satu elemen input pada satu masa dan membina susunan disusun akhir. Ia sangat mudah dan lebih berkesan pada set data yang lebih kecil. Ia adalah teknik penyisihan yang stabil dan di tempat.

Berikut pseudokod yang mewakili Algoritma Penyisipan Penyisipan (konteks jenis menaik).

a [] ialah susunan ukuran N mulai InsertionSort (a []) untuk i = 1 hingga N key = a [i] j = i - 1 sementara (j> = 0 dan a [j]> key0 a [j + 1] = x [j] j = j - 1 hujung sementara [j + 1] = hujung kekunci untuk akhir InsertionSort

Seperti yang anda fahami dari kodnya, algoritma penyisipanmengeluarkan satu elemen dari data input, mencari lokasi yang berada dalam senarai yang disusun dan memasukkannya ke sana. Ia berulang sehingga tidak ada unsur input yang tidak tersusun.

Kes Terbaik: Perkara terbaik adalah apabila input adalah array yang sudah disusun. Dalam kes ini, jenis penyisipan mempunyai masa berjalan linier (iaitu, & Theta (n)).

Kes terburuk: Input kes terburuk yang paling mudah adalah susunan yang disusun dalam urutan terbalik.

QuickSort di Java

Algoritma Quicksort adalah algoritma jenis cepat, rekursif, tidak stabil yang berfungsi berdasarkan prinsip divide and winer. Ia memilih elemen sebagai pivot dan membahagi susunan yang diberikan di sekitar pivot yang dipilih.

Langkah-langkah untuk melaksanakan Jenis cepat:

  1. Pilih 'titik pangsi' yang sesuai.
  2. Bahagikan senarai menjadi dua senaraiberdasarkan elemen pangsi ini. Setiap elemen yang lebih kecil daripada elemen pangsi diletakkan di senarai kiri dan setiap elemen yang lebih besar diletakkan di senarai kanan. Sekiranya elemen sama dengan elemen pangsi maka ia boleh masuk dalam senarai apa pun. Ini dipanggil operasi partition.
  3. Urutkan setiap senarai yang lebih kecil secara berulang.

Inilah pseudocode yang mewakili Algoritma Quicksort.

QuickSort (A sebagai array, rendah int, tinggi int) {jika (rendah

Dalam pseudokod di atas, partition () fungsi melakukan operasi partition dan Quicksort () fungsi berulang kali memanggil fungsi partisi untuk setiap senarai yang lebih kecil yang dihasilkan. Kerumitan pintasan dalam kes purata ialah & Theta (n log (n)) dan dalam kes terburuk adalah & Theta (n2).

Gabungkan Susun di Jawa

Mergesort adalah algoritma jenis cepat, rekursif, stabil yang juga berfungsi berdasarkan prinsip divide and winer. Sama seperti quicksort, penggabungan jenis membahagikan senarai elemen menjadi dua senarai. Senarai ini disusun secara bebas dan kemudian digabungkan. Semasa gabungan senarai, elemen dimasukkan (atau digabungkan) di tempat yang betul dalam senarai.

Inilah pseudokod yang mewakili Algoritma Gabungan.

prosedur MergeSort (a sebagai array) jika (n == 1) mengembalikan var l1 sebagai array = a [0] ... a [n / 2] var l2 sebagai array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) penggabungan kembali (l1, l2) prosedur prosedur akhir bergabung (a sebagai array, b sebagai array) var c sebagai array sementara (a dan b mempunyai unsur) jika (a dan b a [0]> b [0]) tambahkan b [0] ke hujung c keluarkan b [0] dari b lain tambahkan [0] ke hujung c keluarkan [0] dari hujung jika berakhir sementara (a mempunyai unsur) tambahkan [0] ke hujung c keluarkan a [0] dari hujung sementara sementara (b ada unsur) tambahkan b [0] ke hujung c keluarkan b [0] dari b akhir semasa kembali prosedur akhir c

mergesort () fungsi membahagikan senarai menjadi dua, panggilan mergesort () pada senarai ini secara berasingan dan kemudian menggabungkannya dengan menghantarnya sebagai parameter untuk menggabungkan fungsi ().Algoritma mempunyai kerumitan O (n log (n)) dan mempunyai pelbagai aplikasi.

Isi Tumpukan di Jawa

Heapsort adalah algoritma penyortiran berdasarkan perbandinganStruktur data timbunan binari. Anda boleh menganggapnya sebagai pilihan versi f yang lebih baik, di manaia membahagikan inputnya ke wilayah yang diurutkan dan tidak diurutkan, dan secara iteratif mengecilkan wilayah yang tidak diurutkan dengan mengekstrak elemen terbesar dan memindahkannya ke wilayah yang diurutkan.

Langkah-langkah untuk melaksanakan Quicksort (dalam urutan meningkat):

  1. Bina timbunan maksimum dengan susunan penyusun
  2. Pada titik init, barang terbesar disimpan di akar timbunan. Gantikannya dengan item timbunan terakhir dan kurangkan ukuran timbunan sebanyak 1. Akhirnya, timbulkan akar pokok
  3. Ulangi langkah di atas sehingga ukuran timbunan lebih besar daripada 1

Berikut adalah pseudocode yang mewakili Algoritma Heap Sort.

Heapsort (a sebagai array) untuk (i = n / 2 - 1) hingga i> = 0 heapify (a, n, i) untuk i = n-1 hingga 0 pertukaran (a [0], a [i]) heapify (a, i, 0) akhir untuk akhir untuk heapify (susunan sebagai, n sebagai int, i sebagai int) terbesar = i // Permulaan terbesar sebagai akar int l eft = 2 * i + 1 // kiri = 2 * i + 1 int kanan = 2 * i + 2 // kanan = 2 * i + 2 jika (kiri a [terbesar]) terbesar = kiri jika (kanan a [terbesar]) terbesar = kanan jika (terbesar! = I) tukar ( a [i], A [terbesar]) Heapify akhir (a, n, terbesar) heapify

Selain daripada ini, terdapat algoritma penyortiran lain yang tidak begitu terkenal seperti, Introsort, Counting Sort, dll. Beralih ke rangkaian algoritma seterusnya dalam artikel ‘Struktur Data dan Algoritma’ ini, mari kita meneroka algoritma carian.

Mencari Algoritma di Java

Mencari adalah salah satu tindakan yang paling biasa dan sering dilakukan dalam aplikasi perniagaan biasa. Algoritma carian adalah algoritma untuk mencari item dengan sifat yang ditentukan di antara koleksi item. Mari kita terokai dua algoritma carian yang paling biasa digunakan.

apa hashset di java

Algoritma Pencarian Linear di Jawa

Pencarian linear atau carian berurutan adalah algoritma carian termudah. Ia melibatkan pencarian berurutan untuk elemen dalam struktur data yang diberikan sehingga elemen itu dijumpai atau akhir struktur dicapai. Sekiranya elemen dijumpai, maka lokasi item dikembalikan sebaliknya algoritma mengembalikan NULL.

Berikut pseudocode yang mewakili Carian Linear di Java:

prosedur linear_search (a [], nilai) untuk i = 0 hingga n-1 jika nilai [i] = kemudian cetak 'Found' return i end if print 'Not found' end for end linear_search

Ia adalahalgoritma brute-force.Walaupun semestinya paling mudah, yang pasti bukan yang paling biasa, kerana ketidakcekapannya. Kerumitan Masa pencarian Linear adalah O (N) .

Algoritma Pencarian Binari di Jawa

Pencarian binari, juga dikenali sebagai carian logaritmik, adalah algoritma carian yang mencari kedudukan nilai sasaran dalam susunan yang sudah disusun. Ia membahagikan koleksi input menjadi dua bahagian yang sama dan item tersebut dibandingkan dengan elemen tengah senarai. Sekiranya unsur itu dijumpai, carian akan berakhir di sana. Jika tidak, kami terus mencari elemen dengan membahagikan dan memilih partisi array yang sesuai, berdasarkan pada apakah elemen sasaran lebih kecil atau lebih besar daripada elemen tengah.

Berikut pseudocode yang mewakili Carian Binari di Java:

Prosedur binary_search array diurutkan n ukuran array x nilai yang akan dicari lebih rendahBound = 1 atasBound = n sementara x tidak dijumpai jika atasBound

Pencarian akan berakhir apabila the άνωBound (penunjuk kami) melepasi lowerBound (elemen terakhir), yang menunjukkan bahawa kita telah mencari keseluruhan array dan elemen tersebut tidak ada.Ini adalah algoritma carian yang paling biasa digunakan terutamanya kerana masa cariannya yang cepat. Kerumitan masa carian binari adalah O (N) yang merupakan peningkatan ketara pada O (N) kerumitan masa Pencarian Linear.

Ini membawa kita ke akhir artikel ‘Struktur Data dan Algoritma di Jawa’ ini. Saya telah membahas salah satu topik Java yang paling asas dan penting.Semoga anda jelas dengan semua yang telah dikongsi dengan anda dalam artikel ini.

Pastikan anda berlatih sebanyak mungkin dan kembalikan pengalaman anda.

Lihat oleh Edureka, sebuah syarikat pembelajaran dalam talian yang dipercayai dengan rangkaian lebih daripada 250,000 pelajar berpuas hati yang tersebar di seluruh dunia. Kami di sini untuk membantu anda dalam setiap langkah dalam perjalanan anda, kerana selain daripada soalan wawancara java ini, kami menyediakan kurikulum yang dirancang untuk pelajar dan profesional yang ingin menjadi Pembangun Java.

Ada soalan untuk kami? Sila sebutkan di bahagian komen ‘Struktur Data dan Algoritma di Jawa’ ini artikel dan kami akan menghubungi anda secepat mungkin.