Gibt es eine zuverlässige und einfache Prioritäts-Warteschlange (verknüpfte Liste bevorzugt, nicht notwendig) Implementierung für C?
Allgemeiner ausgedrückt: Welche C-Standardbibliotheken verwenden Sie?
Antworten
Zu viele Anzeigen?
dsh
Punkte
71
PQLib (die derzeit akzeptierte Antwort) ist unvollständig und die Funktionalität stimmt zum Zeitpunkt dieses Beitrags nicht mit der Dokumentation überein. Die Dokumentation von pq_dequeue sagt z.B., dass ein Eintrag zurückgegeben wird. Die Implementierung gibt NULL zurück. Es gibt viele "TO DO"-Kommentare im Code, wie z.B. "remove node containing highest priority entry from its heap". Es fehlt die wesentliche Logik.
An alle, die eine Prioritäts-Warteschlange suchen: Ich empfehle, einen Code zu finden, der gute, erfolgreiche Unit-Tests hat. Ich empfehle PQLib nicht, es sei denn, es ist aktualisiert und enthält Tests.
An den Besitzer von PQLib oder jeden, der es empfiehlt: Ich bin davon ausgegangen, dass dieser Code vollständig ist und habe viel Zeit mit der Fehlersuche verbracht, bis ich gemerkt habe, dass er es nicht ist, was frustrierend war. Bitte empfehlen Sie keinen Code, den Sie nicht ausprobiert haben oder von dem Sie wissen, dass er noch in Arbeit ist.
AShelly
Punkte
33678
El Quellcode begleitend Robert Sedgewick 's Algorithmen in C, Teile 1-4 (Grundlegende Algorithmen, Datenstrukturen, Sortieren, Suchen) enthält sowohl eine heap-basierte als auch eine listenbasierte Implementierung. Siehe Kapitel 9 - Prioritätswarteschlangen und Heapsort.
justinhj
Punkte
10753
Ich habe eine Prioritäts-Warteschlange in C geschrieben, die auf Google Code gehostet wird. MIT-Lizenz
https://code.google.com/p/pqueue-heap-c/source/browse/trunk/pqueue.cpp
Der Code wurde in einigen Projekten verwendet, ist also solide, aber ich habe ihn '98 geschrieben und weiß nicht mehr, wie man ihn benutzt. Lassen Sie sich nicht von der cpp-Erweiterung in die Irre führen. Es ist reines C.
