Struktur dan algoritma data
Data Struktur dan Algoritma (DSA) adalah salah satu topik terpenting dalam ilmu komputer bahwa setiap siswa CS harus mahir dan bahkan siswa non-CS harus memiliki pemahaman dasar tentang hal itu. Dikatakan bahwa DSA seperti roti dan mentega, kebutuhan CS. Repositori ini dibuat untuk para siswa (seperti saya?) Siapa yang ingin belajar dan ingin menerapkan struktur dan algoritma data.
Mengapa pergi/golang dan bukan C, C ++ atau Java?
Saya tidak akan tidak setuju bahwa C, C ++ atau Java tidak akan menjadi bahasa yang hebat untuk mengimplementasikan DSA karena seseorang harus mengurus banyak hal saat menulis kode seperti alokasi memori dan kesepakatan yang tepat dan dengan melakukannya, seseorang belajar banyak.
Namun alasan mengapa Go juga menjadi bahasa yang baik untuk mengimplementasikan DSA adalah karena tidak memiliki banyak sihir. Tidak ada operator yang berlebihan, jadi tidak ada cara untuk menyembunyikan kompleksitas ekstra. Operasi indeks adalah O (1), loop adalah O (n) - selalu. Tidak ada obat generik, jadi banyak abstraksi tambahan dan pembantu tidak ada, yang sebenarnya cukup bagus. Tidak ada kemalasan atau sihir yang digerakkan oleh kompiler lainnya yang dapat mengubah runtime algoritma Anda secara signifikan. Dan GO memiliki pointer dan primitif tingkat rendah untuk irisan, artinya jelas ketika data dikemas atau ketika data memiliki tipuan tambahan. Singkatnya : Pergi membuat eksekusi algoritmik yang sebenarnya jelas dari kode, yang merupakan hal yang baik untuk mempelajari algoritma.
Kesimpulan : GO juga akan menjadi bahasa yang baik untuk memulai dengan menerapkan struktur data dan algoritma.
Instruksi
- Untuk memulai, pastikan Anda memiliki bahasa pemrograman yang diinstal di komputer Anda. Ikuti cara menginstal instruksi dari instruksi unduhan Golang.
- Setelah Go diinstal pada mesin Anda, cukup klon atau unduh repositori ini.
- Sekarang
cd <folder-name> ke folder tempat file yang ingin Anda jalankan berada. - Sekarang jalankan
go run . .
Contoh
Mari kita asumsikan bahwa Anda ingin menjalankan file yang terletak di Direktori graphs/directed_unweighted kemudian sintaks untuk menjalankannya adalah:
cd graphs/directed_unweighted/
go run .
Nama folder
- Algoritma -
- 01knapsack_dp - 0-1 Masalah Knapsack Menggunakan Pemrograman Dinamis
- A_Star -
- 8_puzzle - 8 masalah puzzle menggunakan * algoritma
- Directed_graph - algoritma * untuk grafik terarah
- tidak diarahkan_graph - algoritma * untuk grafik yang tidak diarahkan
- Activity_selection_gp - Pemilihan aktivitas menggunakan pemrograman serakah
- Assembly_line_scheduling - Algoritma Penjadwalan Jalur Perakitan Menggunakan Pemrograman Dinamis
- Binary_reflected_gray_codes - Kode abu -abu yang dipantulkan biner
- Closest_pair_problem -
- CPP_BRUTE_FORCE - Masalah pasangan terdekat menggunakan teknik brute force
- CPP_DIVIDE_CONQUER - Masalah pasangan terdekat menggunakan Techinque Divide and Conquer
- Kombinasi -
- dengan_r - dengan pengulangan elemen
- tanpa_r - tanpa pengulangan elemen
- convex_hull -
- CH_BRUTE_FORCE - Algoritma Cembung Hull Menggunakan Teknik Brute Force
- CH_DIVIDE_CONQUER - Algoritma Cembung Hull Menggunakan Teknik Divide and Conquer
- Expression_conversions -
- infix_postfix - konversi infix ke postfix
- infix_prefix - konversi infix ke awalan
- Postfix_infix - Postfix ke Infix Conversion
- Postfix_prefix - Postfix ke Konversi Prefix
- prefix_infix - awalan ke konversi infix
- prefix_postfix - awalan ke konversi postfix
- GCD - Pembagi Umum Terbesar (Algoritma Euclid)
- Grafik -
- Articulation_Point_Detection - Mendeteksi titik artikulasi dalam grafik yang tidak diarahkan
- Bellman_ford - Algoritma Bellman Ford
- Bridge_Detection - Deteksi Deteksi/Potong Jembatan Deteksi dalam grafik yang tidak diarahkan
- Dijkstra - Algoritma Dijkstra
- Floyd_warshall - Algoritma Floyd Warshall (semua poin terpendek)
- Kruskals - Algoritma Kruskal (menemukan minimum spanning tree MST menggunakan pendekatan serakah)
- Prims - Algoritma Prim (Menemukan Minimum Spanning Tree MST Menggunakan Pendekatan Serakah)
- Topologi_sort - Topologi
- Traversals -
- cd_directed_graph_traversals - Deteksi siklus dalam grafik terarah menggunakan teknik traversals
- CD_UNDIRECTED_GRAPH_TRAVERSALS - Deteksi siklus dalam grafik yang tidak diarahkan menggunakan teknik traversals
- TSP -
- TSP_DYNAMIC -
- Directed_graph - TSP (Masalah Salesman Perjalanan) Menggunakan Pendekatan Dinamis untuk Grafik Diarahkan
- tidak terarah_graph - TSP (masalah wisatawan bepergian) Menggunakan pendekatan dinamis untuk grafik yang tidak diarahkan
- TSP_NAIVE -
- Directed_graph - TSP (Masalah Salesman Perjalanan) Menggunakan pendekatan naif untuk grafik terarah
- tidak terarah_graph - TSP (masalah wisatawan bepergian) menggunakan pendekatan naif untuk grafik yang tidak diarahkan
- Union_find - Set Union Find / Disjoint (mendeteksi siklus dalam grafik yang tidak diarahkan)
- Huffman_Codes - Kode Huffman (menghasilkan kode Huffman)
- job_scheduling_gp - algoritma penjadwalan pekerjaan menggunakan pemrograman serakah
- LCM - Paling tidak umum (menggunakan algoritma Euclid GCD)
- LCS - Umum terpanjang setelahnya
- Iterative_dp - Umum terpanjang setelah menggunakan pemrograman dinamis (versi iteratif)
- LO_PERMUTATION - Permutasi pemesanan leksikografi
- longest_palindrome_substring -
- Brute_force - Substring palindrome terpanjang menggunakan teknik brute force
- Manchers - Substring palindrome terpanjang menggunakan algoritma Mancher
- Making_change_dp - Membuat masalah perubahan menggunakan pemrograman dinamis
- order_statistics - Menemukan elemen terkecil/terbesar (statistik pesanan)
- Naive_approach - pendekatan naif menggunakan max heap - o (k + (nk)*log (k))
- Quick_Select - Pilih Cepat (Sortir Cepat) - O (n^2), θ (nlogn)
- world_case_linear_time - statistik pesanan waktu linier kasus terburuk - o (n)
- power_set - set power (set himpunan bagian)
- Pencarian -
- Binary_search - pencarian biner - o (log n)
- Interpolation_search - Pencarian Interpolasi - O (n)
- linear_search - pencarian linier - o (n)
- ternary_search - pencarian ternary - o (log 3 n)
- SEIVE_OF_ERATOSTHENES - Saringan Eratosthenes (bilangan prima berturut -turut tidak melebihi n)
- penyortiran -
- Binary_insertion_sort - Urutan Penyisipan Biner - O (n 2 )
- Bubble_sort - Sort Bubble - O (n 2 )
- Bucket_sort - Sortir Bucket - O (n 2 )
- Counting_sort - Penghitungan Sort - O (n + K)
- heap_sort - heap sort - o (nlog (n)
- Inserton_sort - Sort Penyisipan - O (n 2 )
- merge_sort - gabungan sort - o (nlog (n))
- Quick_sort - Sortir Cepat - θ (nlog (n))
- Radix_sort - Radix Sort - O (n+K)
- Selection_sort - Sortir Seleksi - (o (n 2 ))
- shell_sort - sortir shell - о (n)
- String_matching -
- Boyer_moore - algoritma Boyer Moore
- Horspool - Algoritma Horspool Boyer Moore
- Knuth_morris_pratt - Knuth Morris Pratt
- naive_pattern_matching - pencocokan pola naif
- Rabin_karp - Rabin Karp
- Toh - Tower of Hanoi
- Grafik -
- Directed_unweighted - grafik tanpa bobot terarah
- Directed_weighted - grafik tertimbang terarah
- tidak terarah_unweighted - grafik tanpa bobot yang tidak diarahkan
- tidak terarah_ boboted - grafik tertimbang tidak diarahkan
- Tumpukan -
- Max_Binary_Heap - Max Binary Heap
- Min_Binary_Heap - Min Binary Heap
- Linked_lists -
- Circular_doubly_ll - Daftar Tertaut Ganda Lingkar
- Circular_ll - Daftar Tertaut Circular
- Doubly_ll - Daftar Tertaut Ganda
- Pres_rev_single_ll - Celeserve Order Selama Insertion pada Daftar Tertaut Tunggal dan Membalikkan Daftar Tertaut Tunggal
- Single_ll - Daftar Tertaut Tunggal
- Antrian -
- CDQUEUE - Antrian Akhir Double Circular
- CQueue - Antrian melingkar
- DQUEUE - Antrian Berakhir Ganda
- Prioritas_Queue - Antrian prioritas dengan penggunaan heap min
- Simple_queue - antrian sederhana
- Tumpukan - Tumpukan
- Pohon -
- AVL_TREE_USING_LL - AVL Tree menggunakan daftar tertaut dengan BFS dan DFS (pre, in, post) pesanan traversals.
- BST_USING_ARR - Pohon pencarian biner menggunakan array dengan BFS dan DFS (pre, in, post) pesanan traversal.
- BST_USING_LL - Pohon pencarian biner menggunakan daftar tertaut dengan BFS dan DFS (pre, in, post) pesanan traversal.
- Simple_BT_USING_ARR - Pohon biner sederhana menggunakan array dengan BFS dan DFS (pra, in, post) pesanan traversal.
- Simple_BT_USING_LL - Pohon biner sederhana menggunakan daftar tertaut dengan BFS dan DFS (pre, in, post) pesanan traversal.
Catatan : Pointer ": point_left:" menunjukkan implementasi yang tidak lengkap dan ada dalam daftar TODO.
Kontribusi
Repositori ini adalah untuk mempelajari cara mengimplementasikan struktur dan algoritma data, dan karena kontribusi orang lain tidak akan benar -benar mengajari saya cara mengimplementasikannya sendiri, saya tidak akan menerima permintaan tarik apa pun. Namun, jangan ragu untuk membayar repo ini dan memodifikasi kode untuk bermain di sekitar berbagai struktur dan algoritma data. Selain itu, saat bermain di sekitar kode, jika Anda menemukan sesuatu yang tidak biasa atau salah dalam implemetasi, saya akan sangat menghargai jika Anda membuat masalah pada hal yang sama.
Lisensi
Repositori ini dirilis di bawah lisensi MIT. Singkatnya, ini berarti Anda bebas menggunakan perangkat lunak ini dalam proyek pribadi, open-source atau komersial. Atribusi adalah opsional tetapi dihargai.
HAPPY CODING
HAPPY LEARNING
