Struktur Data
Perpustakaan ini menyediakan implementasi algoritma dan struktur data klasik.
Organisasi
Proyek ini dibagi menjadi dua paket, algoritma dan struktur. Paket algoritma berisi implementasi sebagian besar algoritma yang berdiri sendiri sementara paket struktur berisi struktur data dan algoritma yang secara eksklusif beroperasi pada mereka.
Algoritma
Berikut adalah daftar algoritma di bawah paket algoritma:
Di BinarySearch.py:
- Pencarian biner standar: Pencarian biner standar. https://en.wikipedia.org/wiki/binary_search_algorithm
- Pencarian Biner Accolence Pertama: Pencarian biner standar kecuali bahwa ia menemukan elemen pertama yang cocok dengan kunci pencarian.
Di Expression.py:
Algoritma Halaman Shunting: Algoritma Dijkstra untuk mengubah infiks ke notasi postfix. https://en.wikipedia.org/wiki/shunting-hard_algorithm
Dua Algoritma Tumpukan Dijkstra: Algoritma Dijkstra untuk menafsirkan ekspresi postfix.
Di masalah solver.py:
- A* Algoritma: Algoritma pencarian jalan. https://en.wikipedia.org/wiki/a*_search_algorithm
- A* algoritma yang disesuaikan dengan masalah 8-puzzle: https://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html
Di sort.py:
- Sortian Seleksi: https://en.wikipedia.org/wiki/selection_sort
- Sort Penyisipan: https://en.wikipedia.org/wiki/insertion_sort
- Sortir Shell: https://en.wikipedia.org/wiki/shellsort
- Variasi Gabungan Sort: https://en.wikipedia.org/wiki/merge_sort
- Hitungan inversi: Hitung jumlah inversi dengan jenis gabungan yang dimodifikasi
- Variasi dengan cepat: termasuk jenis cepat standar, jenis cepat 3 arah, dan pengambilan sampel. https://en.wikipedia.org/wiki/quicksort
- Heap Sort: https://en.wikipedia.org/wiki/heapsort
- Pilih KTH: Pilih elemen KTH secara berurutan. Berdasarkan partisi Sortir Cepat.
Struktur
Berikut adalah daftar struktur data dan algoritma yang diimplementasikan yang beroperasi pada mereka:
Di linkedlist.py:
- Daftar Tertaut: https://en.wikipedia.org/wiki/linked_list
- Stack Linked: Stack diimplementasikan dengan daftar tertaut.
- Antrian Tertaut: Antrian diimplementasikan dengan daftar tertaut.
Dalam unionfind.py: https://en.wikipedia.org/wiki/disjoint-set_data_struktur
- Temukan cepat: Set Disjoint diimplementasikan dengan array seperti struktur data. O (1) Temukan.
- Persatuan Cepat: Set Disjoint Diimplementasikan dengan Pohon Tautan Orangtua.
- Balanced Quick Union: Set Disjoint diterapkan dengan TREE TINGKAT ORANG TERKAIT DAN BAYANCING ON UNION. O (log (n)) efisiensi untuk menemukan dan persatuan.
- Path Compression Quick Union: Disjoint Set diimplementasikan dengan Tree Link Parent dan ditambah dengan kompresi jalur.
- Balanced Path Compression Quick Union: Disjoint Set diimplementasikan dengan Tree Link Parent dengan Balancing dan Path Compression. Efisiensi O (1) hampir diamortisasi pada penemuan dan persatuan.
Di Symboltable.py:
- Pohon pencarian biner: BST standar. https://en.wikipedia.org/wiki/binary_search_tree
- Pohon Merah & Hitam: BSTEAL BST menggunakan 2-3 representasi. https://en.wikipedia.org/wiki/red%e2%80%93black_tree
- Tabel hash rantai terpisah: tabel hash yang menyelesaikan tabrakan dengan merantai mereka dalam daftar. https://en.wikipedia.org/wiki/hash_table#separate_chaining
- Tabel Hash Alamat Terbuka: Tabel Hash yang menyelesaikan tabrakan dengan penyelidikan linier. https://en.wikipedia.org/wiki/hash_table#open_addressing
Di heap.py:
- Biner Heap: Implementasi antrian prioritas dengan tumpukan biner. https://en.wikipedia.org/wiki/binary_heap
Dalam graph.py:
- Grafik tidak terarah: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#undirected_graph
- Grafik terarah: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#directed_graph
- Grafik tertimbang tidak terarah: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)# weighted_graph
- Diarahkan grafik tertimbang: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weighted_graph
- Pencarian pertama kedalaman: https://en.wikipedia.org/wiki/depth-first_search
- Luas Pencarian Pertama: https://en.wikipedia.org/wiki/breadth-first_search
- Komponen terhubung yang tidak diarahkan: https://en.wikipedia.org/wiki/component_(graph_theory)
- Deteksi siklus tidak terarah: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Deteksi siklus terarah: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Deteksi Biparte: https://en.wikipedia.org/wiki/bipartite_graph
- Pemesanan Topologi: https://en.wikipedia.org/wiki/topological_sorting
- Komponen yang sangat terhubung (algoritma Kosaraju): https://en.wikipedia.org/wiki/kosaraju%27s_algorithm
- Algoritma Prim (malas): https://en.wikipedia.org/wiki/prim%27s_algorithm
- Algoritma Kruskal: https://en.wikipedia.org/wiki/kruskal%27s_algorithm
- Jalur terpendek Dijkstra: https://en.wikipedia.org/wiki/dijkstra%27s_algorithm
- Jalur terpendek Acyclic Topologis: https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
- Bellman Ford Path Terpendek: https://en.wikipedia.org/wiki/bellman%E2%80%93ford_algorithm
Penggunaan
Semua komponen diuji. Namun, mereka tidak diuji ke standar produksi yang ketat. Struktur data seperti daftar yang ditautkan dan simboltable memiliki antarmuka seperti daftar python standar dan kamus.
