هياكل البيانات الأساسية في C

طريقان إلى نفس الفكرة

قبل أن تبدأ

الفكرة الجوهرية: argc/argv كأول "هيكل بيانات" تستقبله

قبل بناء هياكلك الخاصة، مشروع argc/argv يعلّمك كيف يستقبل برنامجك بياناته من خارجه أصلًا:

int main(int argc, char *argv[])
{
    int i;

    /* argc: عدد الوسائط بما فيها اسم البرنامج نفسه */
    /* argv: مصفوفة من السلاسل النصية، argv[0] هو اسم البرنامج */
    for (i = 0; i < argc; i++)
        printf("argv[%d] = %s\n", i, argv[i]);
    return (0);
}
/* تشغيل: ./program hello world
   argv[0] = ./program
   argv[1] = hello
   argv[2] = world
   argc = 3 */

القوائم المرتبطة: أحادية ومزدوجة الاتجاه

شكل 1، كل عقدة (Node) تحتوي قيمة ومؤشرًا واحدًا للعقدة التالية فقط؛ للتنقل للخلف يجب المرور بالقائمة كاملة من البداية.

شكل 2، كل عقدة تحتوي مؤشرين: للعقدة التالية وللعقدة السابقة معًا، فتسمح بالتنقل في الاتجاهين بتكلفة ذاكرة إضافية بسيطة.

مثال محلول: بناء عقدة وإضافتها في بداية قائمة أحادية

typedef struct node_s
{
    int data;
    struct node_s *next;
} node_t;

node_t *push_front(node_t *head, int value)
{
    node_t *new_node = malloc(sizeof(node_t));

    if (new_node == NULL)
        return (head);          /* فشل الحجز: أعد القائمة كما هي */
    new_node->data = value;
    new_node->next = head;       /* العقدة الجديدة تشير لما كان أول القائمة */
    return (new_node);           /* هي الآن رأس القائمة الجديد */
}

شكل 3، لاحظ أن هذا بالضبط نفس منطق "المؤشر كعنوان" من الجزء السادس: كل ما تفعله هو ربط عناوين ببعضها بدل نسخ بيانات كاملة.

جداول التجزئة والأشجار الثنائية

شكل 4، شجرة بحث ثنائية: للوصول لأي قيمة، قارن مع الجذر واتجه يسارًا إن كانت أصغر أو يمينًا إن كانت أكبر، وكرر: بدون الحاجة لفحص كل عقدة.

الإدراج في BST يتبع نفس منطق البحث بالضبط: تبدأ من الجذر وتقارن، تتجه يسارًا أو يمينًا حسب نتيجة المقارنة، وتكرر ذلك حتى تصل لمكان فاضٍ (NULL) فتضع العقدة الجديدة هناك، لا حاجة لإعادة ترتيب الشجرة كاملة. الحذف أعقد قليلًا: حذف عقدة ورقة (بلا أطفال) بسيط، وحذف عقدة بطفل واحد يعني "تخطّيها" وربط أبيها بطفلها مباشرة، لكن حذف عقدة بطفلين يتطلب إيجاد "الخليفة" (Successor)، أصغر قيمة في الفرع الأيمن، ووضعها مكان العقدة المحذوفة حتى يبقى ترتيب الشجرة صحيحًا.

تعمّق: القوائم المرتبطة: عقد ومؤشرات وإعادة توصيل

القوائم المرتبطة أول مرة تبني فيها هيكلًا من قطع مبعثرة تربطها المؤشرات. الفكرة هنا أهم من الشيفرة: أين تقع العقد، وكيف تُعاد توصيل المؤشرات عند الإدراج والحذف، ومتى تتفوق القائمة على المصفوفة ومتى تخسر.

أولًا: العقدة والرأس

العقدة (Node) بنية تحمل قيمة ومؤشرًا إلى العقدة التالية (struct تحوي مؤشرًا إلى نفس نوعها). لا يوجد في القائمة شيء اسمه فهرس؛ كل ما تملكه مؤشر إلى أول عقدة يسمى الرأس (Head)، وتنتهي القائمة بعقدة يكون مؤشرها التالي NULL‏. أما القائمة الفارغة فرأسها NULL نفسه. وكل عقدة تُحجز عادة بـmalloc منفصلة، ولذلك تتناثر في الكومة بلا ترتيب، وما يربطها هو المؤشرات فقط.

شكل 5، قائمة أحادية الاتجاه من ثلاث عقد: كل عقدة تعرف التالية فقط.

ثانيًا: الإدراج والحذف إعادة توصيل لا نقل

ميزة القائمة أنك لا تنقل أي بيانات عند الإدراج: تحجز عقدة جديدة ثم تعدّل مؤشرين. والترتيب مهم جدًا: اجعل مؤشر العقدة الجديدة يشير إلى ما بعدها أولًا، ثم اجعل العقدة السابقة تشير إلى الجديدة. لو عكست الترتيب فقدت بقية القائمة لأن المؤشر الوحيد إليها ضاع. وعند الحذف تعيد توصيل السابقة بما بعد المحذوفة ثم تحرر المحذوفة، وإلا تسربت الذاكرة أو استعملت عقدة محررة. والحالات الحدّية التي ينهار عندها الكثيرون: الإدراج عند الرأس (يتغير الرأس نفسه فتحتاج مؤشرًا إلى مؤشر أو إعادة الرأس الجديد)، وحذف الرأس، والقائمة الفارغة، والموضع الذي يتجاوز الطول.

شكل 6، إدراج عقدة بين A و B: وصّل الجديدة بما بعدها قبل أن تغيّر مؤشر A.

ثالثًا: القائمة المزدوجة

تضيف القائمة مزدوجة الاتجاه إلى كل عقدة مؤشرًا إلى السابقة أيضًا. فائدتها أن تسير في الاتجاهين وأن تحذف عقدة وأنت تملك مؤشرًا إليها فقط دون أن تبحث عن سابقتها من الرأس. ثمنها مؤشر إضافي في كل عقدة (ذاكرة أكبر) وعملان إضافيان في كل إدراج وحذف، وخطأ في أحد الاتجاهين يُفسد القائمة بصمت. ولذا تحافظ على قاعدة ثابتة: لو كانت a تشير إلى b بـnext فإن b تشير إلى a بـprev‏.

شكل 7، قائمة مزدوجة: كل رابط له وجهان يجب أن يبقيا متسقين.

رابعًا: قائمة أم مصفوفة؟

وخلاصة المقارنة: اختر القائمة حين يكثر الإدراج والحذف وقلّ الوصول العشوائي. لكن في كثير من الحالات الواقعية تتفوق المصفوفة رغم نظرية Big O لأن تجاور الذاكرة يفيد ذاكرة التخبئة للمعالج، ولهذا لا تحكم بالنظرية وحدها بل قِس.

تعمّق: جداول التجزئة والتصادمات وعامل الحمل

جدول التجزئة يعد بشيء يبدو مستحيلًا: الوصول إلى أي عنصر بأي مفتاح في زمن شبه ثابت. نفصّل كيف يفعل ذلك ومتى ينهار الوعد.

أولًا: الفكرة: حوّل المفتاح إلى فهرس

المصفوفة تعطيك وصولًا فوريًا لكن بفهرس رقمي. دالة التجزئة (Hash Function) تحوّل أي مفتاح، حتى لو نصًا، إلى عدد ثم تأخذ باقي قسمته على حجم المصفوفة لتحصل على فهرس. فتصبح سلة (Bucket) معروفة لكل مفتاح، وتبحث فيها مباشرة بدل أن تمر على كل العناصر.

ثانيًا: ما الذي يصنع دالة تجزئة جيدة؟

ثالثًا: التصادم أمر حتمي

عدد المفاتيح الممكنة أكبر بكثير من عدد السلال، فبالضرورة سيُنتج مفتاحان مختلفان الفهرس نفسه، وهذا هو التصادم (Collision). وتفسّره مفارقة عيد الميلاد: في غرفة فيها 23 شخصًا فقط يتجاوز احتمال اشتراك اثنين في يوم الميلاد نفسه النصف، فالتصادمات تحدث مبكرًا جدًا قبل أن تمتلئ السلال. لذلك المهم ليس منع التصادم بل التعامل معه. وللمعالجة أسلوبان رئيسيان:

شكل 8، التسلسل: apple و grape وصلا إلى السلة 2 فاصطفّا في قائمة واحدة.

رابعًا: عامل الحمل ولماذا يهم

عامل الحمل (Load Factor) هو عدد العناصر مقسومًا على عدد السلال. كلما ارتفع زاد طول السلاسل وتدهور زمن البحث من قريب من الثابت إلى قريب من الخطي. ولذلك تعيد الجداول الجدية بناء نفسها بمصفوفة أكبر (Rehashing) عند تجاوز عامل معين. وفي أسوأ حالة، إذا وقعت كل المفاتيح في سلة واحدة، يصير الجدول قائمة مرتبطة واحدة وزمن البحث O(n).

وتستعملها أنظمة كثيرة: القواميس (Dictionary) في اللغات، وذاكرات التخبئة، وجداول الرموز في المترجمات، وفهرسة قواعد البيانات، وعدّ تكرار الكلمات.

تعمّق: الأشجار الثنائية: مصطلحات ومرور واتزان

الشجرة الثنائية هرمية كما أن القائمة خطية. نتعلم هنا لغة وصف الأشجار، ثم طرق المرور عليها، ثم لماذا يُحدث الاتزان فرقًا كبيرًا في الأداء.

أولًا: مصطلحات لا بد منها

شكل 9، شجرة بحجم 8 وارتفاع 3: أبعد الأوراق عن الجذر هي 10 على عمق 3.

ثانيًا: ثنائية عادية أم شجرة بحث ثنائية؟

الشجرة الثنائية العادية كل عقدة فيها لها ابنان على الأكثر، بلا شرط على القيم. أما شجرة البحث الثنائية (BST) فتفرض ترتيبًا: كل ما في الفرع الأيسر لعقدة أصغر منها، وكل ما في الأيمن أكبر. بهذا الشرط يصبح البحث كالبحث الثنائي: عند كل عقدة تقارن فتتخلص من نصف الاحتمالات، فتبلغ هدفك في زمن يتناسب مع الارتفاع لا مع الحجم.

ثالثًا: طرق المرور

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

رابعًا: أنواع الأشجار الثنائية

وفي الشجرة التامة بارتفاع h يكون عدد العقد 2^(h+1) − 1‏، أي أن الشجرة بمليون عقدة تقريبًا ارتفاعها نحو 20 فقط. وهذا سر قوتها: الارتفاع لوغاريتمي في الحجم. لكن إن أدرجت قيمًا مرتبة في BST عادية صارت كل عقدة بابن واحد، وتحولت الشجرة إلى قائمة مرتبطة ارتفاعها n، وتنهار الفائدة. فالاتزان هو ما يضمن الأداء، وهو سبب وجود الأشجار ذاتية الاتزان (AVL، الأحمر والأسود).

شكل 10، الشكل يحكم الأداء: العقد نفسها، وزمن البحث يختلف.

جرّب بنفسك

بطاقات مراجعة سريعة

تحقق من فهمك