ساختارهای پیشرفته

دستکاری آرایه

یافتن slot خالی به درستی

این مثال نشان می‌دهد چگونه با استفاده از شیوه‌های استاندارد برنامه‌نویسی slot خالی را در آرایه پیدا کنید.

new
    gMyArray[10];

stock FindEmptySlot()
{
    new
        i = 0;
    while (i < sizeof (gMyArray) && gMyArray[i])
    {
        i++;
    }
    if (i == sizeof (gMyArray)) return -1;
    return i;
}

این مثال ساده فرض می‌کند slot آرایه اگر مقدارش 0 باشد خالی است. حلقه تا زمانی که مقادیر صفر نباشند، تمام مقادیر آرایه را حلقه می‌زند (می‌تواند با ثابت هم انجام شود). وقتی به یکی که 0 است برسد شرط while شکست می‌خورد و حلقه بدون استفاده از break که شیوه معمول است اما در موقعیت‌هایی مثل این ممنوع است، تمام می‌شود. این تابع همچنین -1 برمی‌گرداند اگر slot آزاد پیدا نشود، که باید در انتهای دیگر بررسی شود. بیشتر معمولاً id پیدا شده را مستقیماً استفاده می‌کنید:

MyFunction()
{
    new
        i = 0;
    while (i < sizeof (gMyArray) && gMyArray[i])
    {
        i++;
    }
    if (i == sizeof (gMyArray))
    {
        printf("No free slot found");
        return 0;
    }
    printf("Slot %d is empty", i);
    // از slot پیدا شده در کد خود برای هر چیزی استفاده کنید
    return 1;
}

بدیهی است که عبارت "gMyArray[i]" را با نشانگر خود از slot در استفاده جایگزین کنید.

لیست

مقدمه

لیست‌ها نوع بسیار مفیدی از ساختار هستند، آنها اساساً آرایه‌ای هستند که قسمت بعدی یا داده مربوطه توسط قسمت آخر اشاره می‌شود.

مثال:

فرض کنید آرایه زیر را دارید:

3, 1, 64, 2, 4, 786, 2, 9

اگر می‌خواستید آرایه را مرتب کنید در نهایت خواهید داشت:

1, 2, 2, 3, 4, 9, 64, 786

اگر اما می‌خواستید داده‌ها را در ترتیب اصلی بگذارید اما همچنان اعداد را به ترتیب برای دلیلی بدانید (فقط یک مثال است)، مشکلی دارید، چگونه قرار است اعداد را همزمان در دو ترتیب داشته باشید؟ این استفاده خوبی از لیست‌ها خواهد بود. برای ساختن لیست از این داده‌ها نیاز دارید آرایه را به آرایه دوبعدی تبدیل کنید، جایی که بعد دوم 2 سلول بزرگ باشد، بعد اول شامل عدد اصلی، دیگری شامل index بزرگترین عدد بعدی. همچنین نیاز به متغیر جداگانه برای نگهداری index کوچکترین عدد دارید، پس آرایه جدیدتان چنین خواهد بود:

start = 1
3, 1, 64, 2, 4, 786, 2, 9
4, 3, 5,  6, 7, -1,  0, 2

index بعدی مرتبط با 786 برابر -1 است، این یک index نامعتبر آرایه است و انتهای لیست را نشان می‌دهد، یعنی اعداد بیشتری نیست. دو تای 2 واضحاً می‌توانند در هر طرفی باشند، اولی در آرایه اولی در لیست هم هست زیرا محتمل‌تر است اول با آن برخورد شود.

مزیت دیگر این روش مرتب کردن اعداد این است که اضافه کردن اعداد بیشتر بسیار سریع‌تر است. اگر می‌خواستید عدد 3 دیگری را به آرایه مرتب شده اضافه کنید ابتدا نیاز دارید حداقل 4 عدد را یک slot به راست منتقل کنید تا فضا درست کنید، اینجا وحشتناک نیست اما در آرایه‌های بزرگتر بسیار کند است. با نسخه لیست فقط می‌توانید 3 را به انتهای آرایه اضافه کنید و یک مقدار واحد در لیست تغییر دهید:

start = 1
3, 1, 64, 2, 4, 786, 2, 9, 3
8, 3, 5,  6, 7, -1,  0, 2, 4
^ این مقدار را تغییر بده        ^ بالاترین slot بعدی

هیچ‌یک از اعداد دیگر حرکت نکرده‌اند پس هیچ‌یک از indexهای دیگر نیاز به به‌روزرسانی ندارند، فقط کمترین عدد بعدی را بگذارید به عدد جدید اشاره کند و عدد جدید را بگذارید به عددی که کمترین بعدی قبلاً اشاره می‌کرد اشاره کند. حذف مقدار حتی آسان‌تر است:

start = 1
3, 1, 64, X, 4, 786, 2, 9, 3
8, 6, 5,  6, 7, -1,  0, 2, 4
   ^ تغییر یافته تا از مقدار حذف شده بپرد

اینجا اولین 2 حذف شده و عددی که به آن عدد اشاره می‌کرد (1) به‌روزرسانی شده تا به عددی که عدد حذف شده اشاره می‌کرد اشاره کند. در این مثال نه pointer عدد حذف شده و نه خود عدد حذف نشده‌اند، اما غیرممکن است دنبال کردن لیست به آن slot برسید پس مهم نیست، عملاً حذف شده است.

انواع

لیست‌ها در مثال‌های بالا فقط لیست‌های تکی ساده بودند، همچنین می‌توانید لیست‌های دوتایی داشته باشید جایی که هر مقدار به مقدار بعدی و مقدار آخر اشاره می‌کند، اینها معمولاً pointer به انتهای لیست هم دارند تا به عقب بروند (مثلاً برای گرفتن اعداد به ترتیب نزولی):

start = 1
end = 5
value: 3, 1,  64, 2, 4, 786, 2, 9, 3
next:  8, 3,  5,  6, 7, -1,  0, 2, 4
last:  6, -1, 7,  1, 8, 2,   3, 4, 0

باید با اینها مراقب باشید، خصوصاً وقتی بیش از یک مقدار از هر مقدار دارید، که last pointer به عددی اشاره کند که next pointer آن مستقیماً دوباره برمی‌گردد، مثلاً این اشتباه است:

2,  3, 3
1,  2, -1
-1, 2, 0

next pointer دوم به 3 در slot یک اشاره می‌کند، اما last pointer آن 3 برنمی‌گردد به دو، هر دو لیست روی خودشان به ترتیب هستند (زیرا دو سه می‌تواند هر طرفی باشد) اما با هم اشتباه هستند، نسخه صحیح خواهد بود:

2,  3, 3
1,  2, -1
-1, 0, 2

هر دوی آن لیست‌ها روی دو عدد انتهایی شروع و پایان می‌یابند، لیست پشت در مثال اشتباه روی عدد وسطی شروع شده بود.

نوع دیگر لیست، لیست حلقه‌ای است جایی که مقدار آخر به اولی برمی‌گردد. مزیت واضح این است که می‌توانید از هر مقداری به هر مقدار دیگری بدون دانستن از قبل اینکه هدف قبل یا بعد از نقطه شروع است برسید، فقط نیاز دارید مراقب باشید وارد حلقه بی‌نهایت نشوید زیرا نقطه پایان صریح -1 وجود ندارد. این لیست‌ها همچنان نقاط شروع دارند. همچنین می‌توانید لیست‌های حلقه‌ای دوتایی داشته باشید جایی که لیست next و last دارید، هر دوی آنها حلقه می‌زنند:

start = 1
end = 5
3, 1,  64, 2, 4, 786, 2, 9, 3
8, 3,  5,  6, 7, 1,   0, 2, 4
6, 5,  7,  1, 8, 2,   3, 4, 0

لیست‌های مختلط

لیست‌های مختلط آرایه‌هایی هستند که شامل چندین لیست همزمان هستند. مثال می‌تواند آرایه‌ای از مقادیر باشد، مرتب شده توسط لیست، با لیست دیگری که تمام slot‌های استفاده نشده را پیوند می‌دهد تا بدانید کجا می‌توانید مقدار جدید اضافه کنید. مثال (X یعنی slot استفاده نشده (آزاد)):

sortedStart = 3
unusedStart = 1
value: 34, X, X, 6, 34, 46, X,  54, 23, 25, X,  75, X, 45
sort:  4,        8, 13, 7,      11, 9,  0,      -1,    5
free:      2, 6,            10,             12,     -1

بدیهی است دو لیست هرگز تعامل نمی‌کنند پس هر دو می‌توانند از همان slot برای مقدار بعدی‌شان استفاده کنند:

sortedStart = 3
unusedStart = 1
value: 34, X, X, 6, 34, 46, X,  54, 23, 25, X,  75, X,  45
next:  4,  2, 6, 8, 13, 7,  10, 11, 9,  0,  12, -1, -1, 5

کد

قبل از شروع کد باید تصمیم بگیرید کدام نوع لیست برای برنامه شما مناسب‌تر است، این کاملاً بر اساس برنامه است و نمی‌تواند به راحتی اینجا پوشش داده شود. تمام این مثال‌ها لیست‌های مختلط هستند، یک لیست برای مقادیر مورد نیاز، یکی برای slot‌های استفاده نشده.

این مثال نشان می‌دهد چگونه کد برای لیست مرتب شده عددی صعودی بنویسید.

#define NUMBER_OF_VALUES (10)

enum E_DATA_LIST
{
    E_DATA_LIST_VALUE,
    E_DATA_LIST_NEXT
}

new
    gListData[NUMBER_OF_VALUES][E_DATA_LIST],
    gUnusedStart = 0,
    gListStart = -1; // بدون لیست شروع می‌شود

// این تابع لیست را مقداردهی اولیه می‌کند
List_Setup()
{
    new
        i,
        size = NUMBER_OF_VALUES;
    size--;
    for (i = 0; i < size; i++)
    {
        // برای شروع همه slotها استفاده نشده‌اند
        gListData[i][E_DATA_LIST_NEXT] = i + 1;
    }
    // لیست را پایان بده
    gListData[size][E_DATA_LIST_NEXT] = -1;
}

// این تابع مقدار را به لیست اضافه می‌کند (با استفاده از مرتب‌سازی ساده)
List_Add(value)
{
    // بررسی کن اگر slotهای آزاد در آرایه وجود دارد
    if (gUnusedStart == -1) return -1;
    new
        pointer = gListStart,
        last = -1,
        slot = gUnusedStart;
    // مقدار را به آرایه اضافه کن
    gListData[slot][E_DATA_LIST_VALUE] = value;
    // لیست خالی را به‌روزرسانی کن
    gUnusedStart = gListData[slot][E_DATA_LIST_NEXT];
    // تا رسیدن به عدد بزرگتر/مساوی در لیست حلقه بزن
    while (pointer != -1 && gListData[pointer][E_DATA_LIST_VALUE] < value)
    {
        // موقعیت مقدار آخر را ذخیره کن
        last = pointer;
        // به slot بعدی حرکت کن
        pointer = gListData[pointer][E_DATA_LIST_NEXT];
    }
    // اگر به اینجا رسیدیم از مقادیر تمام شدیم یا به یکی بزرگتر رسیدیم
    // بررسی کن اگر هیچ عددی بررسی کردیم
    if (last == -1)
    {
        // اولین عدد بزرگتر بود یا لیستی وجود ندارد
        // در هر حال مقدار جدید را به شروع لیست اضافه کن
        gListData[slot][E_DATA_LIST_NEXT] = gListStart;
        gListStart = slot;
    }
    else
    {
        // مقدار جدید را در لیست قرار بده
        gListData[slot][E_DATA_LIST_NEXT] = pointer;
        gListData[last][E_DATA_LIST_NEXT] = slot;
    }
    return slot;
}

// این تابع مقدار را از slot داده شده در آرایه حذف می‌کند (برگشت داده شده توسط List_Add)
List_Remove(slot)
{
    // این slot معتبر است؟
    if (slot < 0 || slot >= NUMBER_OF_VALUES) return 0;
    // ابتدا slot قبل را پیدا کن
    new
        pointer = gListStart,
        last = -1;
    while (pointer != -1 && pointer != slot)
    {
        last = pointer;
        pointer = gListData[pointer][E_DATA_LIST_NEXT];
    }
    // slot را در لیست پیدا کردیم؟
    if (pointer == -1) return 0;
    if (last == -1)
    {
        // مقدار اولی در لیست است
        // این slot را در لیست رد کن
        gListStart = gListData[slot][E_DATA_LIST_NEXT];
    }
    else
    {
        // مقدار در لیست است
        // این slot را در لیست رد کن
        gListData[last][E_DATA_LIST_NEXT] = gListData[slot][E_DATA_LIST_NEXT];
    }
    // این slot را به لیست استفاده نشده اضافه کن
    // لیست استفاده نشده در هیچ ترتیبی نیست پس مهم نیست
    gListData[slot][E_DATA_LIST_NEXT] = gUnusedStart;
    gUnusedStart = slot;
    return 1;
}

درخت‌های باینری

مقدمه

درخت‌های باینری روش بسیار سریعی برای جستجوی داده در آرایه با استفاده از سیستم لیست بسیار خاص هستند. شناخته شده‌ترین درخت باینری احتمالاً بازی 20 سؤال است، با فقط 20 سؤال بله/خیر می‌توانید بیش از 1048576 آیتم داشته باشید. درخت باینری، همان طور که نامش نشان می‌دهد، نوعی درخت است، شبیه درخت خانوادگی، جایی که هر آیتم 0، 1 یا 2 فرزند دارد. آنها برای ترتیب دادن داده مثل لیست استفاده نمی‌شوند بلکه برای مرتب کردن داده برای جستجوی بسیار کارآمد استفاده می‌شوند. اساساً با آیتمی جایی نزدیک وسط لیست مرتب شده اشیا شروع می‌کنید (مثلاً عدد وسط در آرایه مرتب شده) و آن را با مقداری که می‌خواهید پیدا کنید مقایسه می‌کنید. اگر همان باشد آیتم خود را پیدا کرده‌اید، اگر بزرگتر باشد به آیتم سمت راست حرکت می‌کنید (نه بلافاصله سمت راست، آیتم سمت راست آیتم وسطی آیتمی در نشان سه چهارم خواهد بود)، اگر کمتر باشد به چپ حرکت می‌کنید، سپس فرآیند را تکرار می‌کنید.

مثال

1 2 5 6 7 9 12 14 17 19 23 25 28 33 38

آرایه مرتب شده قبلی را دارید و می‌خواهید بفهمید slot شماره 7 در کدام slot است (اگر اصلاً باشد)، در این مثال احتمالاً کارآمدتر است مستقیماً در آرایه حلقه بزنید تا پیدا کنید اما هدف این نیست، آن روش زمان به طور خطی با اندازه آرایه افزایش می‌یابد، زمان جستجوی باینری به طور خطی افزایش می‌یابد همان طور که آرایه به طور نمایی در اندازه افزایش می‌یابد. یعنی آرایه 128 بزرگ دو برابر زمان بیشتر برای جستجوی مستقیم نسبت به آرایه 64 بزرگ طول می‌کشد، اما جستجوی باینری 128 بزرگ فقط یک بررسی بیشتر از جستجوی باینری 64 بزرگ طول می‌کشد، اصلاً زیاد نیست.

اگر درخت باینری از داده بالا بسازیم خواهیم داشت:

اگر از چپ به راست بخوانید، جنبه عمودی را نادیده بگیرید می‌توانید ببینید که اعداد به ترتیب هستند. حالا می‌توانیم سعی کنیم 7 را پیدا کنیم.

عدد شروع 14 است، 7 کمتر از 14 است پس به slot اشاره شده توسط شاخه چپ 14 می‌رویم. این ما را به 6 می‌رساند، 7 از 6 بزرگتر است پس راست به 9 می‌رویم، سپس دوباره چپ به 7. این روش 4 مقایسه برای پیدا کردن عدد طول کشید (شامل بررسی نهایی برای تأیید اینکه روی 7 هستیم)، استفاده از جستجوی مستقیم 5 طول می‌کشید.

بیایید بگوییم 7 وجود ندارد، با این درخت باینری خواهیم داشت:

این، بر خلاف مثال بالا، یک عدد فرزند واحد (9) همراه با اعداد 2 و 0 فرزند دارد. فقط درخت کامل داشته باشید وقتی (2^n)-1 عدد داشته باشید (0, 1, 3, 7, 15, 31 ...)، هر عدد دیگری درخت کاملاً پر نخواهد بود. در این حالت وقتی به 9، جایی که 7 خواهد بود، می‌رسیم شاخه چپی پیدا نخواهیم کرد، یعنی 7 وجود ندارد (ممکن نیست در جای دیگری در درخت باشد، فکرش را بکنید)، پس -1 برای slot نامعتبر برمی‌گردانیم.

متعادل و نامتعادل

درخت‌ها در مثال‌های بالا درخت‌های باینری متعادل نامیده می‌شوند، این یعنی تا جایی که ممکن است همه شاخه‌ها طول یکسان دارند (بدیهی است در دومی اعداد کافی برای این حالت وجود ندارد اما تا جایی که ممکن است نزدیک است). ساختن درخت‌های متعادل آسان نیست، روش پذیرفته شده عمومی ساختن درخت‌های تقریباً متعادل قرار دادن اعداد به ترتیب تصادفی است، این ممکن است یعنی با چیزی مثل این خواهید داشت:

بدیهی است این درخت همچنان معتبر است اما سمت راست خیلی بزرگتر از چپ است، اما پیدا کردن 25 همچنان فقط 7 مقایسه در این نسبت به 12 در لیست مستقیم طول می‌کشد. همچنین، تا زمانی که با عدد نسبتاً وسطی شروع کنید روش درج تصادفی باید درخت نسبتاً متعادلی تولید کند. بدترین کار ممکن این است که اعداد را به ترتیب قرار دهید زیرا آنگاه هیچ شاخه چپی اصلاً نخواهد بود (یا شاخه‌های راست اگر برعکس انجام شود)، اما حتی در این بدترین حالت درخت باینری بیش از لیست مستقیم برای جستجو طول نخواهد کشید.

تغییر

اضافه کردن

اضافه کردن مقدار به درخت باینری نسبتاً آسان است، فقط درخت را دنبال می‌کنید، مقداری که می‌خواهید اضافه کنید را به عنوان مرجع استفاده می‌کنید تا به شاخه خالی برسید و عدد را آنجا اضافه کنید. مثلاً اگر می‌خواستید عدد 15 را به درخت متعادل اصلی ما اضافه کنید در شاخه چپ 17 خواهد بود. اگر می‌خواستیم عدد 8 را به درخت متعادل دوم اضافه کنیم (آنی بدون 7) در slot قدیمی 7 در چپ 9 خواهد بود.

حذف

حذف عدد از درخت باینری می‌تواند سخت یا آسان باشد. اگر عدد در انتهای شاخه باشد (مثلاً 1, 5, 7, 12 و غیره در درخت اصلی) فقط آنها را حذف می‌کنید. اگر عددی فقط یک فرزند داشته باشد (مثلاً 9 در مثال دوم) فقط آن فرزند را (مثلاً 12) به موقعیت آنها منتقل می‌کنید (پس فرزندان 6 در مثال دوم جدید 2 و 12 با حذف 9 خواهند بود). حذف فقط وقتی جالب می‌شود که node دو فرزند داشته باشد. حداقل چهار راه برای انجام این کار وجود دارد:

روش اول از نظر محاسباتی ساده‌ترین است. اساساً یکی از شاخه‌ها را انتخاب می‌کنید (چپ یا راست، برای این توضیح راست فرض کنید) و node حذف شده را با اولین node آن شاخه جایگزین می‌کنید (یعنی فرزند راست node حذف شده). سپس از طریق شاخه جدید چپ می‌روید تا به انتها برسید و شاخه چپ را آنجا قرار می‌دهید. مثلاً اگر 14 را از مثال اصلی حذف کنید 25 جای آن را در بالای درخت خواهد گرفت و 6 به شاخه چپ 17 متصل خواهد شد. این روش سریع است اما درخت‌های بسیار نامتعادل به سرعت ایجاد می‌کند.

روش دوم گرفتن تمام اعدادی که فرزند node که تازه حذف کردید هستند و بازسازی درخت باینری جدید از آنها، سپس قرار دادن بالای آن درخت در node که تازه حذف کردید است. این درخت را نسبتاً متعادل نگه می‌دارد اما بدیهی است کندتر است.

روش سوم ترکیب دو روش بالا و بازسازی درخت درجا است، پیچیده‌تر برای کد است اما درخت را متعادل نگه می‌دارد و سریع‌تر از روش دوم است (اگرچه هیچ جا نزدیک سریعی روش اول نیست).

روش نهایی فهرست شده اینجا فقط تنظیم پرچمی روی مقدار که می‌گوید دیگر استفاده نمی‌شود است، این حتی سریع‌تر از روش اول است و ساختار را حفظ می‌کند اما یعنی نمی‌توانید slotها را دوباره استفاده کنید مگر اینکه بتوانید مقداری برای جایگزینی با آن بعداً پیدا کنید.