الاسم¶

tsearch, tfind, tdelete, twalk, twalk_r, tdestroy - إدارة شجرة بحث ثنائية

المكتبة¶

مكتبة سي المعيارية (libc، -lc)

موجز¶

#include <search.h>

typedef enum { preorder, postorder, endorder, leaf } VISIT;

void *tfind(const void *key, void *const *rootp,
            typeof(int (const void *, const void *)) *compar);
void *tsearch(const void *key, void **rootp,
            typeof(int (const void *, const void *)) *compar);
void *tdelete(const void *restrict key, void **restrict rootp,
            typeof(int (const void *, const void *)) *compar);
void twalk(const void *root,
            typeof(void (const void *nodep, VISIT which, int depth))
                *action);

#define _GNU_SOURCE         /* انظر feature_test_macros(7) */
#include <search.h>

void twalk_r(const void *root,
            typeof(void (const void *nodep, VISIT which, void *closure))
                *action,
            void *closure);
void tdestroy(void *root,
            typeof(void (void *nodep)) *free_node);

الوصف¶

تدير الدوال tsearch() و tfind() و twalk() و tdelete() شجرة بحث ثنائية. عُمِّمت هذه الدوال من خوارزمية T لـ Knuth (6.2.2). الحقل الأول في كل عقدة من الشجرة هو مؤشر لعنصر البيانات المقابل. (يجب على البرنامج المستدعي تخزين البيانات الفعلية.) يشير compar إلى روتين مقارنة، يأخذ مؤشرين لعنصرين. يجب أن يُرجع عددًا صحيحًا سالبًا أو صفرًا أو موجبًا، اعتمادًا على ما إذا كان العنصر الأول أقل من الثاني أو مساويًا له أو أكبر منه.

تبحث tsearch() في الشجرة عن عنصر. يشير key إلى العنصر المطلوب البحث عنه. يشير rootp إلى متغير يشير إلى جذر الشجرة. إذا كانت الشجرة فارغة، فيجب ضبط المتغير الذي يشير إليه rootp على NULL. إذا وُجد العنصر في الشجرة، فتُرجع tsearch() مؤشرًا إلى عقدة الشجرة المقابلة. (بمعنى آخر، تُرجع tsearch() مؤشرًا إلى مؤشر لعنصر البيانات.) إذا لم يُعثر على العنصر، فتضيفه tsearch() وتُعيد مؤشرًا إلى عقدة الشجرة المقابلة.

tfind() تشبه tsearch()، باستثناء أنه إذا لم يُعثر على العنصر، فتُرجع tfind() NULL.

تحذف tdelete() عنصرًا من الشجرة. وسيطاتها هي نفس وسيطات tsearch().

تنفذ twalk() اجتيازًا أوليًا بالعمق من اليسار إلى اليمين لشجرة ثنائية. يشير root إلى عقدة البداية للاجتياز. إذا لم تكن تلك العقدة هي الجذر، فستتم زيارة جزء فقط من الشجرة. تستدعي twalk() دالة المستخدم action في كل مرة تُزار فيها عقدة (أي ثلاث مرات للعقدة الداخلية، ومرة واحدة للورقة). تأخذ action بدورها ثلاث وسيطات. الوسيطة الأولى هي مؤشر للعقدة التي تُزار. بنية العقدة غير محددة، لكن من الممكن تحويل المؤشر إلى مؤشر لمؤشر للعنصر للوصول إلى العنصر المخزن داخل العقدة. يجب ألا يُعدِّل التطبيق البنية المشار إليها بهذه الوسيطة. الوسيطة الثانية هي عدد صحيح يأخذ إحدى القيم preorder أو postorder أو endorder اعتمادًا على ما إذا كانت هذه هي الزيارة الأولى أو الثانية أو الثالثة للعقدة الداخلية، أو القيمة leaf إذا كانت هذه هي الزيارة الوحيدة لعقدة ورقية. (هذه الرموز مُعرَّفة في <search.h>.) الوسيطة الثالثة هي عمق العقدة؛ عمق عقدة الجذر هو صفر.

(بشكل أكثر شيوعًا، تُعرف preorder و postorder و endorder باسم preorder و inorder و postorder: قبل زيارة الأطفال، بعد الأول وقبل الثاني، وبعد زيارة الأطفال. وبالتالي، فإن اختيار الاسم postorder مربك إلى حد ما.)

twalk_r() مشابهة لـ twalk()، ولكن بدلاً من وسيطة depth، يُمرَّر مؤشر وسيطة closure إلى كل استدعاء لاستدعاء الإجراء، دون تغيير. يمكن استخدام هذا المؤشر لتمرير المعلومات من وإلى دالة الاستدعاء بطريقة آمنة للخيوط، دون اللجوء إلى متغيرات عامة.

تزيل tdestroy() الشجرة بأكملها المشار إليها بواسطة root، وتحرر جميع الموارد المخصصة بواسطة دالة tsearch(). بالنسبة للبيانات في كل عقدة شجرة، تُستدعى الدالة free_node. يُمرَّر مؤشر البيانات كوسيطة للدالة. إذا لم تكن هناك حاجة لمثل هذا العمل، فيجب أن يشير free_node إلى دالة لا تفعل شيئًا.

قيمة الإرجاع¶

تُرجع tsearch() مؤشرًا إلى عقدة مطابقة في الشجرة، أو إلى العقدة المضافة حديثًا، أو NULL إذا لم تكن هناك ذاكرة كافية لإضافة العنصر. تُرجع tfind() مؤشرًا إلى العقدة، أو NULL إذا لم يُعثر على تطابق. إذا كانت هناك عناصر متعددة تطابق المفتاح، فإن العنصر الذي تُعاد عقدته غير محدد.

تُرجع tdelete() مؤشرًا إلى أصل العقدة المحذوفة، أو NULL إذا لم يُعثر على العنصر. إذا كانت العقدة المحذوفة هي عقدة الجذر، فتُرجع tdelete() مؤشرًا معلقًا يجب عدم الوصول إليه.

تُرجع tsearch() و tfind() و tdelete() أيضًا NULL إذا كان rootp هو NULL عند الدخول.

السمات¶

للاطلاع على شرح للمصطلحات المستخدمة في هذا القسم، انظر attributes(7).

المعايير¶

tsearch()

tfind()

tdelete()

twalk()

POSIX.1-2008.

tdestroy()

twalk_r()

GNU.

التاريخ¶

tsearch()

tfind()

tdelete()

twalk()

POSIX.1-2001, POSIX.1-2008, SVr4.

twalk_r()

glibc 2.30.

ملاحظات¶

تأخذ twalk() مؤشرًا إلى الجذر، بينما تأخذ الدوال الأخرى مؤشرًا إلى متغير يشير إلى الجذر.

تحرر tdelete() الذاكرة المطلوبة للعقدة في الشجرة. المستخدم مسؤول عن تحرير الذاكرة للبيانات المقابلة.

يعتمد البرنامج المثال على حقيقة أن twalk() لا تشير إلى عقدة بعد استدعاء دالة المستخدم بالوسيطة "endorder" أو "leaf". يعمل هذا مع تنفيذ مكتبة GNU، لكنه ليس في توثيق System V.

أمثلة¶

يدرج البرنامج التالي اثني عشر رقمًا عشوائيًا في شجرة ثنائية، حيث تُدمج الأرقام المكررة، ثم يطبع الأرقام بالترتيب.

#define _GNU_SOURCE     /* Expose declaration of tdestroy() */
#include <search.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static void *root = NULL;
static void *
xmalloc(size_t n)
{


    void *p;


    p = malloc(n);


    if (p)


        return p;


    fprintf(stderr, "insufficient memory\n");


    exit(EXIT_FAILURE);
}
static int
compare(const void *pa, const void *pb)
{


    if (*(int *) pa < *(int *) pb)


        return -1;


    if (*(int *) pa > *(int *) pb)


        return 1;


    return 0;
}
static void
action(const void *nodep, VISIT which, int depth)
{


    int *datap;


    switch (which) {


    case preorder:


        break;


    case postorder:


        datap = *(int **) nodep;


        printf("%6d\n", *datap);


        break;


    case endorder:


        break;


    case leaf:


        datap = *(int **) nodep;


        printf("%6d\n", *datap);


        break;


    }
}
int
main(void)
{


    int  *ptr;


    int  **val;


    srand(time(NULL));


    for (unsigned int i = 0; i < 12; i++) {


        ptr = xmalloc(sizeof(*ptr));


        *ptr = rand() & 0xff;


        val = tsearch(ptr, &root, compare);


        if (val == NULL)


            exit(EXIT_FAILURE);


        if (*val != ptr)


            free(ptr);


    }


    twalk(root, action);


    tdestroy(root, free);


    exit(EXIT_SUCCESS);
}

انظر أيضًا¶

bsearch(3), hsearch(3), lsearch(3), qsort(3)

ترجمة¶

تُرجمت هذه الصفحة من الدليل بواسطة زايد السعيدي <zayed.alsaidi@gmail.com>

هذه الترجمة هي وثيقة مجانية؛ راجع رخصة جنو العامة الإصدار 3 أو ما بعده للاطلاع على شروط حقوق النشر. لا توجد أي ضمانات.

إذا وجدت أي أخطاء في ترجمة صفحة الدليل هذه، يرجى إرسال بريد إلكتروني إلى قائمة بريد المترجمين: kde-l10n-ar@kde.org.