سوال ۸

در این سوال شما بایستی کاری شبیه به C++ در تخصیص حافظه و آزاد کردن حافظه از Heap انجام دهید. فرض کنید آرایه‌ی $a$ از نوع int که بسیار بزرگ است وجود دارد. در این سوال شما بایستی توابع زیر را پیاده سازی کنید: دقت کنید همه‌ی توابع باید از ${\cal O}(1)$ باشند.

• تابع :void initialize() در این تابع شما می‌توانید متغیّرهایتان را برای مراحل بعدی مقدار دهی اوّلیّه بکنید. این تابع فقط یک‌بار قبل از استفاده از توابع بعدی اجرا خواهد شد.
• تابع int *allocateMemory(int min, int max): این تابع یک آرایه که عناصرش در بازه‌ی $[min, max)$ قرار دارد را در نظر می‌گیرد و اشاره‌گر به آن را بر می‌گرداند. دقّت کنید min$$ یا $$max می‌توانند منفی هم باشند ولی می‌دانیم همیشه $min\leq max$ است. دقّت کنید عنصر $max$ جز آن نیست. یعنی اگر $min=max$ باشد آرایه هیچ خانه‌ای ندارد.
• تابع void freeMemory(int *b): این تابع آرایه‌ای که قبلاً اختصاص داده شده بود و اشاره‌گر $b$ به آن برگردانده شده بود را خالی می‌کند.

بعنوان یک مثال از نحوه‌ی استفاده از این توابع می‌توان نوشت:

intialize();
int *c=allocateMemory(-3, -2);
int *b=allocateMemory(0, n);
c[-3]=5;
for (int i=0; i<n; i++)
     b[i]=i;
freeMemory(b);
int *d=allocateMemory(-3, -3);
freeMemory(d);
freeMemory(c);

فرض کنید که آرایه‌ها به عکس ترتیبی که ساخته می‌شوند خالی می‌شوند یعنی اگر آرایه‌ی $c$ زودتر از $b$ ساخته شده باشد، $b$ زودتر از $c$ از بین می‌رود. شما برای پیاده‌سازی توابع فوق به غیر از آرایه‌ی $a$ تنها می‌توانید از ${\cal O}(1)$ حافظه‌ی اضافی استفاده کنید. در ضمن در هر لحظه اگر جمعاً $m$ تا آرایه allocate شده وجود داشته باشد که این آرایه‌ها جمعاً $n$ خانه‌ی allocate شده دارند شما می‌توانید از ${\cal O}(m+n)$ تا از خانه‌های آرایه‌ی $a$ استفاده کرده باشید.