در این سوال شما بایستی کاری شبیه به C++ در تخصیص حافظه و آزاد کردن حافظه از Heap انجام دهید. فرض کنید آرایهی a از
نوع int
که بسیار بزرگ است وجود دارد.
در این سوال شما بایستی
توابع زیر را پیاده سازی کنید: دقت کنید همهی توابع باید از 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 استفاده کرده باشید.