سوال ۸

در این سوال شما بایستی کاری شبیه به ‎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$‎ استفاده کرده باشید.

• سوال بعد
• سوال قبل