بنى المعطيات
بنى المعطيات Data Structures هي الطريقة المتبعة في ترتيب البيانات في الحاسوب بحيث يمكن استخدامها بفعالية، والهدف من بنى المعطيات هو اختزال المساحة والتعقيد الزمني المطلوب للمهام المختلفة.
تقسم بنى المعطيات إلى نوعين:
- بنى المعطيات الخطية.
- بنى المعطيات الهرمية.
بنى المعطيات الخطية
المصفوفات
تستخدم المصفوفات في تخزين العناصر المتجانسة في مواقع متجاورة، ويجب تحديد حجم المصفوفة قبل تخزين البيانات فيها.
القوائم المترابطة
يكون كل عنصر في القائمة المترابطة كائنًا بحد ذاته، ويتكون كل عنصر (أو ما يعرف كذلك بالعقدة) من جزئين: البيانات وإشارة إلى العقدة اللاحقة.
هناك عدة أنواع للقوائم المترابطة منها:
القوائم المترابطة المفردة
في هذا النوع من القوائم المترابطة تخزّن كل عقدة موقع العقدة اللاحقة أو تشير إليه، وتشير العقدة الأخيرة في القائمة المترابطة إلى القيمة NULL.
القوائم المترابطة المزدوجة
تمتلك كل عقدة في هذا النوع من القوائم إشارتين، تشير واحدة منهما إلى العقدة التالية والأخرى إلى العقدة السابقة.
القوائم المترابطة الدائرية
ترتبط جميع العقد في هذا النوع من القوائم بعضها ببعض لتشكّل دائرة، ولا وجود لقيمة NULL في نهاية القائمة.
المكادس
الكدس Stack أو LIFO(يدخل أخيرًا، يخرج أوّلًا اختصار last in, first out) هو من بنى المعطيات المجردة والتي تكون على هيئة مجموعة من العناصر التي يمكن أن نؤدي عمليتين أساسيتين عليها وهما عملية إضافة العنصر push وحذف العنصر pop. تجري هاتان العمليتان في المكادس من جهة واحدة وهي قمّة المكدس.
الأرتال
الرتل Queue أو FIFO (يدخل أولًا، يخرج أولًا اختصار first in, first out) هو من بنى المعطيات المجردة والتي تكون على هيئة مجموعة من العناصر التي يمكن أن نؤدي عليها عمليتين أساسيتين هما: إضافة العنصر enqueue وإزالة العنصر dequeue.
الأشجار الثنائية
الأشجار الثنائية هي من بنى المعطيات الهرمية، والشجرة الثنائية هي شجرة بيانات تمتلك كل عقدة فيها على عقدتي أبناء كحدّ أقصى، وتسمّيان بالابن الأيمن والابن الأيسر.
أشجار البحث الثنائية
شجرة البحث الثنائية Binary Search Tree هي شجرة ثنائية تمتلك الخصائص الإضافية التالية:
- الشجرة الفرعية اليسرى تتضمن عقدًا تكون مفاتيحها أقل من مفاتيح العقدة التي تتفرع منها.
- الشجرة الفرعية اليمنى تتضمن عقدًا تكون مفاتيحها أكبر من مفاتيح العقدة التي تتفرع منها.
- يجب أن تكون الأشجار الفرعية جميعها أشجار بحث ثنائية.
دالة التقطيع
دالة التقطيع Hashing Function هي دالة تحول مفتاحًا كبيرًا إلى عدد صحيح ذي قيمة أصغر ويستخدم كموقع index في جدول التقطيع.
الرسم البياني
يضمّ الرسم البياني Graph المكونات التالية:
- مجموعة محددة من الرؤوس vertices والتي تسمى كذلك بالعقد nodes.
- مجموعة محددة من أزواج مرتّبة وتكون بالهيئة (u,v) وتسمى بالأضلاع edges.