Data Structures and Algorithms in C Download - Data Structures and Algorithms in C

Data Structures and Algorithms in C

Kode sumber lainnya

1.0.0

Unduh

Penyimpangan dan algoritma data yang diimplementasikan dalam C

Di sini Anda akan menemukan beberapa struktur data dan algoritma yang diimplementasikan dalam C. Algoritma ini sebagian besar didasarkan pada buku pengantar algoritma oleh Thomas H. Cormen .

Instruksi

Setiap modul terdiri dari setidaknya satu file header (.h) dan satu file sumber yang berisi kode corpus (.c). Untuk menggunakan salah satu modul ini, saya sarankan Anda untuk mengikuti langkah -langkah ini:

Temukan struktur data atau algoritma yang Anda butuhkan dari /modules
Unduh Direktori Modul (EG /modules/List ) yang berisi kode sumber .c file (misalnya List.c )
Pergi ke /include/ folder, temukan file header (.h) yang Anda inginkan (misalnya List.h ) dan unduh.
❕ Belum selesai ❕, sekarang pergi dan periksa file header (.h) dan unduh apa yang disertakan (perintah #include "foo.h" ). Sebagian besar modul termasuk misalnya HashFunctions atau Comparators atau bahkan struktur data lainnya. Temukan apa yang dibutuhkan dan unduh semua file.
Perbaiki jalur ke #include "foo.h" jika Anda mengubah struktur folder saat ini.
Semuanya siap, semoga membantu Anda!

Kompilasi dan eksekusi

Jika Anda mengkloning seluruh folder yang dapat Anda jalankan:

make : itu melumatkan setiap modul
make run-tests : Yang mengkompilasi setiap modul dan menjalankan semua tes
make valgind-tests : yang mengkompilasi setiap modul dan menjalankan semua tes menggunakan valgrind

Lampiran

Struktur data	Definisi
Filter mekar	Bloom Filter adalah struktur data probabilistik yang efisien ruang, yang dipahami oleh Burton Howard Bloom pada tahun 1970, yang digunakan untuk menguji apakah elemen adalah anggota set. Pertandingan positif palsu dimungkinkan, tetapi negatif palsu tidak - dengan kata lain, kueri mengembalikan "mungkin dalam set" atau "pasti tidak dalam set". Elemen dapat ditambahkan ke set, tetapi tidak dihapus (meskipun ini dapat diatasi dengan varian filter penghitung bloom); Semakin banyak item yang ditambahkan, semakin besar probabilitas positif palsu.
Pohon merah-hitam	Pohon merah-hitam adalah semacam pohon pencarian biner yang menyeimbangkan diri. Setiap node menyimpan bit ekstra yang mewakili "warna" ("merah" atau "hitam"), yang digunakan untuk memastikan bahwa pohon tetap seimbang selama penyisipan dan penghapusan. Ketika pohon dimodifikasi, pohon baru disusun ulang dan "dicat ulang" untuk mengembalikan sifat pewarnaan yang membatasi seberapa tidak seimbang pohon itu dalam kasus terburuk. Properti ini dirancang sedemikian rupa sehingga penataan ulang dan rekoloring ini dapat dilakukan secara efisien. Keseimbangan ulang tidak sempurna, tetapi menjamin pencarian dalam waktu O (LOGN) , di mana N adalah jumlah node pohon. Operasi penyisipan dan penghapusan, bersama dengan penataan ulang pohon dan rekoloring, juga dilakukan dalam waktu O (LOGN) .
Daftar Tertaut	Daftar Tertaut adalah kumpulan linear elemen data yang pesanannya tidak diberikan oleh penempatan fisik mereka dalam memori. Sebaliknya, setiap elemen menunjuk ke yang berikutnya. Ini adalah struktur data yang terdiri dari kumpulan node yang bersama -sama mewakili urutan.
Antre	Antrian prioritas adalah tipe data abstrak yang mirip dengan antrian reguler atau struktur data tumpukan di mana setiap elemen juga memiliki "prioritas" yang terkait dengannya. Dalam antrian prioritas, elemen dengan prioritas tinggi dilayani sebelum elemen dengan prioritas rendah.
Hashtable dengan daftar	Implementasi generik dari hashtable yang sangat sederhana dengan kunci dan rantai. Tidak ada rekonstruksi yang disediakan.
Hashtable dengan pohon merah-hitam	Terdiri dari sebuah meja, di mana setiap baris memiliki pointer ke pohon merah-hitam dengan cara ini kita mendapatkan kompleksitas terbaik di atas dan pada saat yang sama menghindari terlalu banyak tabrakan.
Hashtable dengan ember ke pohon merah-hitam	Hashtable terdiri dari ember pointer untuk pohon hitam merah
Maxheap	Max-heap adalah pohon biner lengkap di mana nilai di setiap simpul internal lebih besar dari atau sama dengan nilai pada anak-anak dari simpul itu. Memetakan elemen -elemen tumpukan ke dalam array adalah sepele: jika sebuah simpul disimpan indeks k, maka anak kirinya disimpan pada indeks 2k+1 dan anak kanannya di indeks 2k+2.
Disjointset	Struktur data yang disjoint-set, juga disebut struktur data pentalan-temui atau set gabungan-temuk, adalah struktur data yang menyimpan kumpulan set Disjoint (non-overlapping). Secara setara, ia menyimpan partisi set ke subset terpisah. Ini menyediakan operasi untuk menambahkan set baru, menggabungkan set (menggantikannya dengan serikat mereka), dan menemukan anggota perwakilan dari suatu set. Operasi terakhir memungkinkan untuk mengetahui secara efisien jika ada dua elemen yang ada di set yang sama atau berbeda.
Penjadwal Pekerjaan dengan utas	Penjadwal Pekerjaan Multi-Thread Menggunakan UNIX PTHREADS.

Algoritma	Definisi
Heapsort	Heapsort adalah algoritma penyortiran berbasis perbandingan. Heapsort dapat dianggap sebagai jenis seleksi yang ditingkatkan: seperti jenis seleksi, Heapsort membagi inputnya menjadi wilayah yang disortir dan tidak disortir, dan secara iteratif menyusut wilayah yang tidak disortir dengan mengekstraksi elemen terbesar darinya dan memasukkannya ke wilayah yang diurutkan. Tidak seperti jenis seleksi, Heapsort tidak membuang waktu dengan pemindaian linear-waktu dari wilayah yang tidak disortir; Sebaliknya, Heap Sort mempertahankan wilayah yang tidak disortir dalam struktur data tumpukan untuk lebih cepat menemukan elemen terbesar di setiap langkah.
Quicksort	Quicksort adalah algoritma penyortiran yang efisien. Dikembangkan oleh ilmuwan komputer Inggris Tony Hoare pada tahun 1959 dan diterbitkan pada tahun 1961, itu masih merupakan algoritma yang umum digunakan untuk menyortir. Ketika diimplementasikan dengan baik, itu bisa agak lebih cepat daripada menggabungkan dan sekitar dua atau tiga kali lebih cepat dari heapsort.

Algoritma

Definisi

Heapsort

Heapsort adalah algoritma penyortiran berbasis perbandingan. Heapsort dapat dianggap sebagai jenis seleksi yang ditingkatkan: seperti jenis seleksi, Heapsort membagi inputnya menjadi wilayah yang disortir dan tidak disortir, dan secara iteratif menyusut wilayah yang tidak disortir dengan mengekstraksi elemen terbesar darinya dan memasukkannya ke wilayah yang diurutkan. Tidak seperti jenis seleksi, Heapsort tidak membuang waktu dengan pemindaian linear-waktu dari wilayah yang tidak disortir; Sebaliknya, Heap Sort mempertahankan wilayah yang tidak disortir dalam struktur data tumpukan untuk lebih cepat menemukan elemen terbesar di setiap langkah.

Quicksort

Quicksort adalah algoritma penyortiran yang efisien. Dikembangkan oleh ilmuwan komputer Inggris Tony Hoare pada tahun 1959 dan diterbitkan pada tahun 1961, itu masih merupakan algoritma yang umum digunakan untuk menyortir. Ketika diimplementasikan dengan baik, itu bisa agak lebih cepat daripada menggabungkan dan sekitar dua atau tiga kali lebih cepat dari heapsort.