الأسبوع 5: هياكل البيانات

ترجمة آلية تحت المراجعة

المصدر الأصلي على CS50

المحاضرة الخامسة (Lecture 5)

مرحبًا!
جاك يتعلم الحقائق
هياكل البيانات
قوائم الانتظار
الأكوام
المصفوفات
القوائم المرتبطة
الأشجار
جداول التجزئة والتجزئة
يحاول
التلخيص

مرحبًا! (Welcome!)

قدمت لك الأسابيع السابقة من الدورة التدريبية العناصر الأساسية للبرمجة.
كل ما تعلمته في لغة C سيمكنك من تنفيذ هذه العناصر الأساسية في لغات البرمجة ذات المستوى الأعلى مثل Python.
في كل أسبوع، أصبحت المفاهيم أكثر تحديًا، مثل التل الذي يصبح أكثر انحدارًا وأكثر انحدارًا. وفي هذا الأسبوع، يتصاعد التحدي بينما نستكشف هياكل البيانات.
لقد تعلمت حتى الآن كيف يمكن للمصفوفة تنظيم البيانات في الذاكرة.
سنتحدث اليوم عن تنظيم البيانات في الذاكرة وإمكانيات التصميم التي تنشأ من معرفتك المتزايدة.

جاك يتعلم الحقائق (Jack Learns the Facts)

شاهدنا مقطع فيديو يسمى جاك يعرف الحقائق للبروفيسور شانون دوفال من جامعة إيلون.

هياكل البيانات (Data Structures)

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

قوائم الانتظار (Queues)

قوائم الانتظار هي أحد أشكال بنية البيانات المجردة.
قوائم الانتظار لها خصائص محددة. وهي كذلك ما يصرف أولاً أو "ما يدخل أولاً يخرج أولاً." يمكنك أن تتخيل نفسك في طابور لركوب في متنزه. يجب على أول شخص في الصف أن يركب الركوب أولاً. آخر شخص هو الذي سيذهب في الرحلة أخيرًا.
تحتوي قوائم الانتظار على إجراءات محددة مرتبطة بها. على سبيل المثال، يمكن أن يكون العنصر في قائمة الانتظار; أي أنه يمكن للعنصر الانضمام إلى السطر أو قائمة الانتظار. وعلاوة على ذلك، يمكن أن يكون هذا البند تم وضعه في قائمة الانتظار أو اترك قائمة الانتظار بمجرد وصولها إلى مقدمة السطر.
في الشيفرة، يمكنك تخيل قائمة الانتظار كما يلي:
```
const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
queue;
```
لاحظ أنه تم استدعاء مصفوفة people من النوع person. ال يُستخدم الرمز CAPACITY هو مدى ارتفاع قائمة الانتظار. العدد الصحيح size هو مدى امتلاء قائمة الانتظار فعليًا، بغض النظر عن حجمها يمكن مع الاستمرار.

الأكوام (Stacks)

تتناقض قوائم الانتظار مع أ مكدس. بشكل أساسي، تختلف خصائص المكدس عن خصائص قائمة الانتظار. على وجه التحديد، هو عليه ليفو أو "آخر من يدخل أولاً يخرج أولاً." تمامًا مثل تكديس الصواني في قاعة الطعام، فإن الصينية التي يتم وضعها في الكومة الأخيرة هي أول صينية يمكن التقاطها.
تحتوي الأكوام على إجراءات محددة مرتبطة بها. على سبيل المثال، ادفع يضع شيئًا ما أعلى المكدس. بوب يقوم بإزالة شيء ما من أعلى المكدس.
في الشيفرة، قد تتخيل المكدس كما يلي:
```
const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
stack;
```
لاحظ أنه تم استدعاء مصفوفة people من النوع person. ال يُستخدم الرمز CAPACITY هو مدى ارتفاع المكدس. العدد الصحيح size هو مدى امتلاء المكدس فعليًا، بغض النظر عن حجمه يمكن مع الاستمرار. لاحظ أن هذا الرمز هو نفس الرمز من قائمة الانتظار.
قد تتخيل أن الشيفرة أعلاه به قيود نظرًا لأن سعة المصفوفة محددة مسبقًا دائمًا في هذا الشيفرة. ولذلك، قد تكون المكدس دائمًا كبيرة الحجم. قد تتخيل استخدام مكان واحد فقط في المكدس من أصل 5000.
سيكون من الجيد أن تكون مجموعتنا ديناميكية - قادرة على النمو مع إضافة العناصر إليها.

المصفوفات (Arrays)

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

في جهازك الطرفي، اكتب code list.c واكتب الشيفرة كما يلي:

// Implements a list of numbers with an array of fixed size

#include <stdio.h>

int main(void)
{
    // List of size 3
    int list[3];

    // Initialize list with numbers
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // Print list
    for (int i = 0; i < 3; i++)
    {
        printf("%i\n", list[i]);
    }
}

لاحظ أن ما ورد أعلاه يشبه إلى حد كبير ما تعلمناه سابقًا في هذه الدورة. تم تخصيص الذاكرة مسبقًا لثلاثة عناصر. يمكنك تنزيل هذا الرمز هنا.

ألن يكون جميلًا لو تمكنا من وضع 4 في مكان آخر في الذاكرة؟ بحكم التعريف، لن يعد هذا مصفوفة لأن 4 لن يكون موجودًا في الذاكرة المتجاورة بعد الآن. كيف يمكننا ربط مواقع مختلفة في الذاكرة؟
في الذاكرة، هناك قيم أخرى يتم تخزينها بواسطة برامج ووظائف ومتغيرات أخرى. قد يكون العديد من هذه القيم غير مستخدمة وتم استخدامها في وقت ما ولكنها متاحة الآن للاستخدام.
تخيل أنك تريد تخزين قيمة رابعة 4 في مصفوفتنا. ما سيكون مطلوبًا هو تخصيص مساحة جديدة من الذاكرة ونقل المصفوفة القديمة إلى منطقة جديدة. في البداية، سيتم ملء هذه المنطقة الجديدة من الذاكرة بقيم البيانات المهملة.
عند إضافة القيم إلى هذه المنطقة الجديدة من الذاكرة، سيتم استبدال القيم القديمة المهملة.
في النهاية، سيتم استبدال جميع القيم القديمة غير المرغوب فيها ببياناتنا الجديدة.
أحد عيوب هذا الأسلوب هو أنه تصميم سيء: في كل مرة نضيف فيها رقمًا، يتعين علينا نسخ عنصر المصفوفة تلو الآخر.

بناءً على معرفتنا التي حصلنا عليها مؤخرًا، يمكننا الاستفادة من فهمنا للمؤشرات لإنشاء تصميم أفضل في هذا الشيفرة. قم بتعديل الشيفرة الخاص بك كما يلي:

// Implements a list of numbers with an array of dynamic size

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    // List of size 3
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    // Initialize list of size 3 with numbers
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // List of size 4
    int *tmp = malloc(4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list);
        return 1;
    }

    // Copy list of size 3 into list of size 4
    for (int i = 0; i < 3; i++)
    {
        tmp[i] = list[i];
    }

    // Add number to list of size 4
    tmp[3] = 4;

    // Free list of size 3
    free(list);

    // Remember list of size 4
    list = tmp;

    // Print list
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // Free list
    free(list);
    return 0;
}

لاحظ أنه تم إنشاء قائمة بحجم ثلاثة أعداد صحيحة. بعد ذلك، يمكن تعيين القيم لثلاثة عناوين ذاكرة 1, 2و 3. ثم يتم إنشاء قائمة بالحجم الرابع. بعد ذلك، يتم نسخ القائمة من الأول إلى الثاني. القيمة ل تمت إضافة 4 إلى قائمة tmp . منذ كتلة من الذاكرة ذلك لم تعد نقاط list مستخدمة، وتم تحريرها باستخدام الأمر free(list). وأخيرا، list يُطلب الآن من المؤشر أن يشير إلى كتلة الذاكرة التي tmp يشير إلى. محتويات تتم طباعة list ثم تحريرها. وعلاوة على ذلك، لاحظ إدراج stdlib.h. يمكنك تنزيل هذا الرمز هنا.

من المفيد التفكير فيه list و tmp كلتا العلامتين تشيران إلى جزء من الذاكرة. كما في المثال أعلاه، list عند نقطة واحدة أشار إلى مصفوفة بحجم 3. وفي النهاية، طُلب من list أن يشير إلى جزء من الذاكرة بحجم 4. ومن الناحية الفنية، بنهاية الشيفرة أعلاه، tmp و list كلاهما يشير إلى نفس كتلة الذاكرة.

إحدى الطرق التي يمكننا من خلالها نسخ المصفوفة بدون حلقة for هي باستخدام realloc:

// Implements a list of numbers with an array of dynamic size using realloc

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    // List of size 3
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    // Initialize list of size 3 with numbers
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // Resize list to be of size 4
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list);
        return 1;
    }
    list = tmp;

    // Add number to list
    list[3] = 4;

    // Print list
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // Free list
    free(list);
    return 0;
}

لاحظ أنه تم إعادة تخصيص القائمة لمصفوفة جديدة عبر realloc. يمكنك تنزيل هذا الرمز هنا.

قد يميل المرء إلى تخصيص ذاكرة أكبر مما هو مطلوب للقائمة، مثل 30 عنصرًا بدلاً من 3 أو 4 المطلوبة. ومع ذلك، يعد هذا تصميمًا سيئًا لأنه يفرض ضرائب على موارد النظام عندما لا تكون هناك حاجة إليها. علاوة على ذلك، ليس هناك ما يضمن أن هناك حاجة إلى ذاكرة لأكثر من 30 عنصرًا في نهاية المطاف.

القوائم المرتبطة (Linked Lists)

في الأسابيع الأخيرة، تعرفت على ثلاثة أساسيات مفيدة. أ struct هو نوع بيانات يمكنك تعريفه بنفسك. أ . في تدوين نقطي يسمح لك بالوصول إلى المتغيرات داخل تلك البنية. ال يُستخدم عامل التشغيل * للإعلان عن مؤشر أو إلغاء الإشارة إلى متغير.
اليوم، تعرفت على عامل التشغيل -> . إنه سهم. يذهب هذا العامل إلى العنوان وينظر داخل الهيكل.
A القائمة المرتبطة هي واحدة من أقوى بنيات البيانات في لغة C. وتسمح لك القائمة المرتبطة بتضمين القيم الموجودة في مناطق مختلفة من الذاكرة. علاوة على ذلك، فهي تسمح لك بتنمية القائمة وتقليصها ديناميكيًا حسب رغبتك.
قد تتخيل ثلاث قيم مخزنة في ثلاث مناطق مختلفة من الذاكرة على النحو التالي:
كيف يمكن دمج هذه القيم معًا في القائمة؟
يمكننا أن نتخيل البيانات الموضحة أعلاه على النحو التالي:
يمكننا استخدام المزيد من الذاكرة لتتبع مكان العنصر التالي باستخدام المؤشر.

لاحظ أنه يتم استخدام NULL للإشارة إلى عدم وجود أي شيء آخر التالي في القائمة.
وفقًا للاتفاقية، سنحتفظ بعنصر آخر في الذاكرة، وهو المؤشر، الذي يتتبع العنصر الأول في القائمة، والذي يسمى الرأس من القائمة.
بتجريد عناوين الذاكرة، ستظهر القائمة كما يلي:
يتم استدعاء هذه الصناديق العقد. أ العقدة يحتوي على كلاً من عنصر ودعا المؤشر التالي. في الشيفرة، يمكنك تخيل عقدة على النحو التالي:
```
typedef struct node
{
    int number;
    struct node *next;
}
node;
```
لاحظ أن العنصر الموجود داخل هذه العقدة هو عدد صحيح يسمى number. ثانيا، يتم استدعاء مؤشر إلى عقدة تم تضمين next ، والذي سيشير إلى عقدة أخرى في مكان ما في الذاكرة.

يمكننا إعادة الإنشاء list.c لاستخدام القائمة المرتبطة:

// Start to build a linked list by prepending nodes

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Prepend node to list
        n->next = list;
        list = n;
    }
    return 0;
}

أولاً، أ node على أنه struct. لكل عنصر من عناصر القائمة، ذاكرة لـ a يتم تخصيص node عبر malloc إلى حجم العقدة. n->number (أو يتم تعيين عدد صحيح لحقل رقم n). n->next (أو تم تعيين الحقل التالي لـ n). NULL. ثم يتم وضع العقدة في بداية القائمة في موقع الذاكرة list. يمكنك تنزيل هذا الرمز هنا.

من الناحية النظرية، يمكننا أن نتخيل عملية إنشاء قائمة مرتبطة. أولا، تم الإعلان عن node *list ، ولكن له قيمة غير صحيحة.
بعد ذلك، تم استدعاء العقدة تم تخصيص n في الذاكرة.
التالي، number يتم تعيين القيمة للعقدة 1.
بعد ذلك، العقدة تم تعيين حقل next NULL.
التالي، list يشير إلى موقع الذاكرة حيث n نقطة. n و list يشير الآن إلى نفس المكان.
يتم بعد ذلك إنشاء عقدة جديدة. كلا تمتلئ حقول number و next بالقيم المهملة.
ال يتم استخدام الدالة number قيمة تم تحديث عقدة n(العقدة الجديدة) إلى 2.
أيضًا تم تحديث حقل next أيضًا.
والأهم من ذلك، أننا لا نريد أن نفقد اتصالنا بأي من هذه العقد خشية أن تُفقد إلى الأبد. وبناء على ذلك، nق يشير الحقل next إلى نفس موقع الذاكرة تم تحديث list.
أخيرًا، list للإشارة إلى n. لدينا الآن قائمة مرتبطة من عنصرين.
بالنظر إلى الرسم البياني للقائمة، يمكننا أن نرى أن آخر رقم تمت إضافته هو الرقم الأول الذي يظهر في القائمة. وعليه، إذا قمنا بطباعة القائمة بالترتيب، بدءاً من العقدة الأولى، فستظهر القائمة غير مرتبة.

يمكننا طباعة القائمة بالترتيب الصحيح كما يلي:

// Print nodes in a linked list with a while loop

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Prepend node to list
        n->next = list;
        list = n;
    }

    // Print numbers
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }
    return 0;
}

لاحظ ذلك تم الآن إنشاء node *ptr = list يقوم بإنشاء متغير مؤقت يشير إلى نفس المكان list يشير إلى. ال تطبع حلقة while ما هي العقدة ptr إلى، ثم يقوم بالتحديث ptr للإشارة إلى عقدة next في القائمة. يمكنك تنزيل هذا الرمز هنا.

في هذا المثال، يكون الإدراج في القائمة دائمًا بالترتيب \(O(1)\)، حيث لا يستغرق الأمر سوى عدد قليل جدًا من الخطوات للإدراج في مقدمة القائمة.
بالنظر إلى مقدار الوقت المطلوب للبحث في هذه القائمة، فهو بالترتيب \(O(n)\)، لأنه في أسوأ الحالات يجب دائمًا البحث في القائمة بأكملها للعثور على عنصر. يعتمد التعقيد الزمني لإضافة عنصر جديد إلى القائمة على مكان إضافة هذا العنصر. وهذا موضح في الأمثلة أدناه.
لا يتم تخزين القوائم المرتبطة في كتلة متجاورة من الذاكرة. ويمكن أن تنمو بالحجم الذي تريده، بشرط وجود موارد كافية للنظام. ومع ذلك، فإن الجانب السلبي هو أن هناك حاجة إلى المزيد من الذاكرة لتتبع القائمة بدلاً من المصفوفة. بالنسبة لكل عنصر، يجب عليك تخزين ليس فقط قيمة العنصر، ولكن أيضًا مؤشر إلى العقدة التالية. علاوة على ذلك، لا يمكن فهرسة القوائم المرتبطة كما هو ممكن في المصفوفة لأننا بحاجة إلى المرور عبر العناصر \(n - 1\) الأولى للعثور على موقع العنصر \(n\)th. ولهذا السبب، يجب البحث في القائمة الموضحة في الصورة أعلاه خطيًا. ولذلك، فإن البحث الثنائي غير ممكن في القائمة التي تم إنشاؤها على النحو الوارد أعلاه.

علاوة على ذلك، يمكنك وضع الأرقام في نهاية القائمة كما هو موضح في هذا الشيفرة:

// Appends numbers to a link list

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // If list is empty
        if (list == NULL)
        {
            // This node is the whole list
            list = n;
        }

        // If list has numbers already
        else
        {
            // Iterate over nodes in list
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // If at end of list
                if (ptr->next == NULL)
                {
                    // Append node
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // Print numbers
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Free memory
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
    return 0;
}

لاحظ كيف هذا الشيفرة يمشي للأسفل هذه القائمة للعثور على النهاية. عند إلحاق عنصر (الإضافة إلى نهاية القائمة) سيتم تشغيل الشيفرة الخاص بنا في \(O(n)\)، حيث يتعين علينا مراجعة القائمة بأكملها قبل أن نتمكن من إضافة العنصر النهائي. علاوة على ذلك، لاحظ أن المتغير المؤقت يسمى next يستخدم للتتبع ptr->next. يمكنك تنزيل هذا الرمز هنا.

علاوة على ذلك، يمكنك فرز قائمتك عند إضافة العناصر:

// Implements a sorted linked list of numbers

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // If list is empty
        if (list == NULL)
        {
            list = n;
        }

        // If number belongs at beginning of list
        else if (n->number < list->number)
        {
            n->next = list;
            list = n; 
        }

        // If number belongs later in list
        else
        {
            // Iterate over nodes in list
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // If at end of list
                if (ptr->next == NULL)
                {
                    // Append node
                    ptr->next = n;
                    break;
                }

                // If in middle of list
                if (n->number < ptr->next->number)
                {
                    n->next = ptr->next;
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // Print numbers
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Free memory
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
    return 0;
}

لاحظ كيف تم فرز هذه القائمة عند إنشائها. لإدراج عنصر بهذا الترتيب المحدد، سيظل الشيفرة الخاص بنا يعمل في \(O(n)\) لكل عملية إدراج، لأنه في أسوأ الحالات سيتعين علينا البحث في جميع العناصر الحالية. يمكنك تنزيل هذا الرمز هنا.

كإضافة نهائية، يمكن للمرء إنشاء وظيفة يمكن من خلالها تفريغ القائمة المرتبطة: تعمل وظيفة

// Frees memory in cases of error too

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

void unload(node *list);

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            unload(list);
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // If list is empty
        if (list == NULL)
        {
            list = n;
        }

        // If number belongs at beginning of list
        else if (n->number < list->number)
        {
            n->next = list;
            list = n; 
        }

        // If number belongs later in list
        else
        {
            // Iterate over nodes in list
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // If at end of list
                if (ptr->next == NULL)
                {
                    // Append node
                    ptr->next = n;
                    break;
                }

                // If in middle of list
                if (n->number < ptr->next->number)
                {
                    n->next = ptr->next;
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // Print numbers
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Free memory
    unload(list);
    return 0;
}

void unload(node *list)
{
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

لاحظ أن يتم استخدام كتلة unload على تحرير القائمة بأكملها. يمكنك تنزيل هذا الرمز هنا.

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

الأشجار (Trees)

توفر المصفوفات ذاكرة متجاورة يمكن البحث فيها بسرعة. توفر المصفوفات أيضًا الفرصة للمشاركة في البحث الثنائي.
هل يمكننا الجمع بين أفضل المصفوفات والقوائم المرتبطة؟
أشجار البحث الثنائية هي بنية بيانات أخرى يمكن استخدامها لتخزين البيانات بشكل أكثر كفاءة بحيث يمكن البحث عنها واسترجاعها.
يمكنك تخيل تسلسل مرتب من الأرقام.
تخيل إذن أن القيمة المركزية تصبح أعلى الشجرة. يتم وضع تلك التي هي أقل من هذه القيمة على اليسار. يتم وضع القيم الأكبر من هذا على اليمين.
يمكن بعد ذلك استخدام المؤشرات للإشارة إلى الموقع الصحيح لكل منطقة من الذاكرة بحيث يمكن توصيل كل من هذه العقد.
في الشيفرة، يمكن تنفيذ البحث عن مثل هذه الشجرة على النحو التالي:
```
bool search(node *tree, int number)
{
    if (tree == NULL)
    {
        return false;
    }
    else if (number < tree->number)
    {
        return search(tree->left, number);
    }
    else if (number > tree->number)
    {
        return search(tree->right, number);
    }
    else if (number == tree->number)
    {
        return true;
    }
}
```
لاحظ كيف تقوم وظيفة البحث هذه بالبحث بشكل متكرر في الشجرة. إذا كان الرقم الذي تم البحث عنه أقل من رقم العقدة الحالية، فإنه يبحث في الشجرة الفرعية اليسرى. إذا كان أكبر، فإنه يبحث في الشجرة الفرعية الصحيحة. يسمح هذا النهج العودي بالبحث الفعال مع التعقيد الزمني لـ O(log n) عندما تكون الشجرة متوازنة.
توفر الشجرة ديناميكية لا توفرها المصفوفة. يمكنها أن تنمو وتتقلص كما نشاء.
علاوة على ذلك، توفر هذه البنية وقت بحث قدره \(O(log n)\) عندما تكون الشجرة متوازنة.

جداول التجزئة والتجزئة (Hashing and Hash Tables)

ال يتم استخدام الدالة الكأس المقدسة من التعقيد الزمني الخوارزمي هو \(O(1)\) أو وقت ثابت. وهذا يعني أن الهدف النهائي هو أن يكون الوصول فوريًا.
التجزئة هي فكرة أخذ قيمة والقدرة على إخراج قيمة تصبح اختصارًا لها لاحقًا.
على سبيل المثال، التجزئة تفاحة قد يتم تجزئة كقيمة 1و التوت قد يتم تجزئة كـ 2. لذلك، العثور على تفاحة أمر سهل مثل سؤال تجزئة خوارزمية حيث تفاحة تم تخزين . على الرغم من أنها ليست مثالية من حيث التصميم، إلا أنها في النهاية تضع كل شيء aفي مجموعة واحدة و bموجود في مفهوم آخر التجميع توضح القيم المجزأة كيف يمكنك استخدام هذا المفهوم: يمكن استخدام القيمة المجزأة لاختصار العثور على مثل هذه القيمة.
A وظيفة التجزئة هي خوارزمية تقلل القيمة الأكبر إلى شيء صغير ويمكن التنبؤ به. بشكل عام، تأخذ هذه الوظيفة العنصر الذي ترغب في إضافته إلى جدول التجزئة الخاص بك، وتقوم بإرجاع عدد صحيح يمثل فهرس المصفوفة الذي يجب وضع العنصر فيه.
A جدول التجزئة عبارة عن مزيج رائع من المصفوفات والقوائم المرتبطة. عند تنفيذه في الشيفرة، يكون جدول التجزئة بمثابة مصفوفة من مؤشرات إلى العقدةق.
يمكن تصور جدول التجزئة على النحو التالي:

لاحظ أن هذه مصفوفة يتم تعيينها لكل قيمة من الحروف الأبجدية.
بعد ذلك، في كل موقع من المصفوفة، يتم استخدام قائمة مرتبطة لتتبع كل قيمة يتم تخزينها هناك:
الاصطدامات تحدث عندما تقوم بإضافة قيم إلى جدول التجزئة، ويكون هناك شيء موجود بالفعل في الموقع المجزأ. في ما سبق، يتم ببساطة إلحاق التصادمات بنهاية القائمة.
يمكن تقليل التصادمات من خلال برمجة جدول التجزئة وخوارزمية التجزئة بشكل أفضل. يمكنك أن تتخيل تحسنا على ما ورد أعلاه على النحو التالي:
فكر في المثال التالي لخوارزمية التجزئة:
يمكن تنفيذ ذلك في الشيفرة كما يلي:
```
#include <ctype.h>

unsigned int hash(const char *word)
{
    return toupper(word[0]) - 'A';
}
```
لاحظ كيف تقوم دالة التجزئة بإرجاع قيمة toupper(word[0]) - 'A'.
يتعين عليك، كمبرمج، اتخاذ قرار بشأن مزايا استخدام المزيد من الذاكرة للحصول على جدول تجزئة كبير وربما تقليل وقت البحث أو استخدام ذاكرة أقل وربما زيادة وقت البحث.
توفر هذه البنية وقت بحث قدره \(O(n)\).

يحاول (Tries)

يحاول هي شكل آخر من أشكال بنية البيانات. المحاولات عبارة عن أشجار من المصفوفات.
يحاول قابلة للبحث دائمًا في وقت ثابت.
جانب سلبي واحد ل يحاول هو أنها تميل إلى استهلاك قدر كبير من الذاكرة. لاحظ أننا نحتاج إلى عقد \(26 \times 4 = 104\) فقط للتخزين الضفدع!
الضفدع سيتم تخزين على النحو التالي:
توم سيتم بعد ذلك تخزين على النحو التالي:
توفر هذه البنية وقت بحث قدره \(O(1)\).
الجانب السلبي لهذه البنية هو عدد الموارد المطلوبة لاستخدامها.

التلخيص (Summing Up)

في هذا الدرس، تعلمت كيفية استخدام المؤشرات لإنشاء هياكل بيانات جديدة. وعلى وجه التحديد، تعمقنا في…

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

نراكم في المرة القادمة!