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

Data Structures and Algorithms in C

شفرة المصدر الأخرى

1.0.0

تنزيل

قواعد البيانات والخوارزميات المنفذة في ج

ستجد هنا بعض هياكل البيانات والخوارزميات التي تم تنفيذها في C. تعتمد هذه الخوارزميات في الغالب على كتاب مقدمة إلى الخوارزميات التي كتبها Thomas H. Cormen .

تعليمات

يتكون كل وحدة من ملف رأس واحد على الأقل (.H) وملف مصدر واحد يحتوي على كوري كوري (.C). من أجل استخدام إحدى هذه الوحدات ، أقترح عليك اتباع هذه الخطوات:

ابحث عن بنية البيانات أو الخوارزمية التي تحتاجها من /modules
قم بتنزيل دليل الوحدة النمطية (على سبيل المثال /modules/List ) التي تحتوي على ملف .C المصدر (على سبيل المثال List.c )
انتقل إلى /include/ مجلد ، ابحث عن ملف الرأس (.h) الذي تريده (على سبيل المثال List.h ) وتنزيله.
❕ لم ينته بعد ❕ ، الآن اذهب وتحقق من ملف الرأس (.h) وقم بتنزيل ما تم تضمينه (الأوامر #include "foo.h" ). تتضمن معظم الوحدات على سبيل المثال HashFunctions أو Comparators أو حتى هياكل البيانات الأخرى. بقعة ما هو مطلوب وتنزيل جميع الملفات.
إصلاح المسارات إلى #include "foo.h" إذا قمت بتغيير بنية المجلد الحالي.
كل شيء جاهز ، آمل أن يكون قد ساعدك!

ترجمة وتنفيذ

إذا قمت باستنساخ المجلد بأكمله يمكنك تشغيله:

make : هذا يلفت كل وحدة نمطية
make run-tests : التي تجمع كل وحدة وتنفذ جميع الاختبارات
make valgind-tests : التي تجمع كل وحدة وتنفذ جميع الاختبارات باستخدام Valgrind

زائدة

بنية البيانات	تعريف
مرشح بلوم	Floom Filter هو بنية بيانات احتمالية فعالة للفضاء ، تصورها بيرتون هوارد بلوم في عام 1970 ، والتي يتم استخدامها لاختبار ما إذا كان العنصر عضوًا في مجموعة. المباريات الإيجابية الخاطئة ممكنة ، لكن السلبيات الخاطئة ليست كذلك - بمعنى آخر ، يعود الاستعلام إما "ربما في المجموعة" أو "بالتأكيد ليس في المجموعة". يمكن إضافة العناصر إلى المجموعة ، ولكن لم تتم إزالتها (على الرغم من أنه يمكن معالجة هذا مع متغير مرشح بلوم العد) ؛ كلما تمت إضافة المزيد من العناصر ، زاد احتمال وجود إيجابيات كاذبة.
شجرة أسود أحمر	شجرة السود الحمراء هي نوع من شجرة البحث الثنائية التوازن الذاتي. تقوم كل عقدة بتخزين جزء إضافي يمثل "لون" ("أحمر" أو "أسود") ، يستخدم للتأكد من أن الشجرة تظل متوازنة أثناء الإدراج والحذف. عند تعديل الشجرة ، يتم إعادة ترتيب الشجرة الجديدة و "إعادة الطلاء" لاستعادة خصائص التلوين التي تقيد مدى عدم توازن الشجرة في أسوأ الحالات. تم تصميم الخصائص بحيث يمكن تنفيذ إعادة ترتيب وإعادة التداول بكفاءة. إعادة التوازن ليست مثالية ، ولكنها تضمن البحث في وقت O (logn) ، حيث N هو عدد العقد من الشجرة. كما يتم تنفيذ عمليات الإدراج والحذف ، إلى جانب إعادة ترتيب الأشجار وإعادة التداخل ، في وقت O (logn) .
قائمة مرتبطة	القائمة المرتبطة عبارة عن مجموعة خطية لعناصر البيانات التي لا يتم تقديم طلبها من خلال وضعها المادي في الذاكرة. بدلاً من ذلك ، يشير كل عنصر إلى التالي. إنه بنية بيانات تتكون من مجموعة من العقد التي تمثل معًا تسلسلًا.
طابور	قائمة الانتظار ذات الأولوية هي نوع بيانات مجردة مشابه لإنشاء قائمة انتظار أو بنية بيانات المكدس العادية التي يكون لكل عنصر بالإضافة إلى ذلك "أولوية" مرتبطة به. في قائمة انتظار الأولوية ، يتم تقديم عنصر ذي أولوية عالية قبل عنصر ذي أولوية منخفضة.
علامة التجزئة مع القائمة	التنفيذ العام لتصنيف بسيط للغاية مع المفاتيح والسلاسل. لم يتم إعادة بناء.
علامة التجزئة مع شجرة اللون الأسود الأحمر	يتكون من طاولة ، حيث يكون لكل صف مؤشر لشجرة سوداء حمراء بهذه الطريقة نحصل على أفضل التعقيدات المذكورة أعلاه وفي الوقت نفسه تجنب الكثير من التصادمات.
علامة التجزئة مع دلاء إلى شجرة أسود حمراء	يتألف علامة التجزئة من دلاء من المؤشرات للأشجار السوداء الحمراء
Maxheap	يعد Max-Heap شجرة ثنائية كاملة تكون فيها القيمة في كل عقدة داخلية أكبر من أو تساوي القيم في أطفال تلك العقدة. تعيين عناصر الكومة في صفيف تافهة: إذا تم تخزين عقدة فهرس k ، ثم يتم تخزين طفلها الأيسر في الفهرس 2K+1 وطفلها الأيمن في الفهرس 2K+2.
تفكيك	بنية البيانات غير المنفصلة ، والتي تسمى أيضًا بنية بيانات الاتحاد أو مجموعة الدمج ، هي بنية بيانات تخزن مجموعة من مجموعات المفككة (غير المتداخلة). بشكل ما يعادل ، يخزن قسم مجموعة في مجموعات فرعية مفككة. يوفر عمليات لإضافة مجموعات جديدة ، ودمج مجموعات (استبدالها بنقاباتهم) ، وإيجاد عضو تمثيلي في مجموعة. تتيح العملية الأخيرة أن تكتشف بكفاءة إذا كان هناك عنصرين في نفس المجموعات أو المجموعات المختلفة.
جدولة الوظائف مع المواضيع	جدولة الوظائف متعددة الخيوط باستخدام Unix Pthreads.

خوارزمية	تعريف
الكثافة	Heapsort هي خوارزمية الفرز القائمة على المقارنة. يمكن اعتبار Hepsort بمثابة نوع من التحديد المحسّن: مثل نوع الاختيار ، يقسم Heapsort مدخلاته إلى منطقة مصنفة وغير مصنفة ، وتقلل بشكل تكرار المنطقة غير المصنفة عن طريق استخراج أكبر عنصر منه وإدراجها في المنطقة المرتبة. على عكس فرز الاختيار ، لا يضيع Heapsort الوقت مع فحص خطي للمنطقة غير المصنفة ؛ بدلاً من ذلك ، يحتفظ Theap Sort بالمنطقة غير المصورة في بنية بيانات الكومة لإيجاد العنصر الأكبر في كل خطوة بسرعة أكبر.
Quicksort	Quicksort هي خوارزمية فرز فعالة. تم تطويره من قبل عالم الكمبيوتر البريطاني توني هوير في عام 1959 ونشره في عام 1961 ، ولا يزال خوارزمية شائعة الاستخدام للفرز. عند تنفيذها بشكل جيد ، يمكن أن يكون أسرع إلى حد ما من دمج الفرز وحوالي مرتين أو ثلاث مرات أسرع من Heapsort.

خوارزمية

تعريف

الكثافة

Heapsort هي خوارزمية الفرز القائمة على المقارنة. يمكن اعتبار Hepsort بمثابة نوع من التحديد المحسّن: مثل نوع الاختيار ، يقسم Heapsort مدخلاته إلى منطقة مصنفة وغير مصنفة ، وتقلل بشكل تكرار المنطقة غير المصنفة عن طريق استخراج أكبر عنصر منه وإدراجها في المنطقة المرتبة. على عكس فرز الاختيار ، لا يضيع Heapsort الوقت مع فحص خطي للمنطقة غير المصنفة ؛ بدلاً من ذلك ، يحتفظ Theap Sort بالمنطقة غير المصورة في بنية بيانات الكومة لإيجاد العنصر الأكبر في كل خطوة بسرعة أكبر.

Quicksort

Quicksort هي خوارزمية فرز فعالة. تم تطويره من قبل عالم الكمبيوتر البريطاني توني هوير في عام 1959 ونشره في عام 1961 ، ولا يزال خوارزمية شائعة الاستخدام للفرز. عند تنفيذها بشكل جيد ، يمكن أن يكون أسرع إلى حد ما من دمج الفرز وحوالي مرتين أو ثلاث مرات أسرع من Heapsort.

جدوى	تعريف
المقارنات	الوظائف التي تقارن قيمتين وإرجاع 0 ،> 0 ، <0
وظائف التجزئة	وظائف التجزئة سلسلة