ظرف (نوع داده انتزاعی)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه، ظرف (به انگلیسی: Container) یک کلاس، ساختار داده[۱][۲] یا یک نوع داده انتزاعی است که نمونه‌های آن دربرگیرنده اشیاء دیگر هستند. به عبارت دیگر، آنها برای ذخیره کردن اشیاء به روشی سازمان یافته استفاده می‌شوند و اشیاء موجو در آنها تحت یکسری قوانین مشخص قابل دسترسی هستند. اندازه یک ظرف بستگی به تعداد اشیائی (عناصری) که در آن قرار گرفته‌اند دارد. پیاده‌سازی گونه‌های مختلف ظرف‌ها در فضا و پیچیدگی زمانی با یکدیگر تفاوت دارند که باید برای هر سناریو از یک پیاده‌سازی مناسب استفاده کرد.

کلیات[ویرایش]

ظرف‌ها را می‌توان از سه منظر مورد مطالعه قرار داد:

  1. دسترسی: به معنی دسترسی داشتن به عناصر موجود در ظرف است. در مورد آرایه‌ها، دسترسی به عناصر با استفاده از اندیس آرایه صورت می‌گیرد. در مورد پشته‌ها، دسترسی به عناصر به روش آخرین ورودی، اولین خروجی[۳] و در مورد صف‌ها دسترسی به عناصر به شکل اولین ورودی، اولین خروجی صورت می‌گیرد.[۳][۴]
  2. ذخیره‌سازی: شامل ذخیره کردن عناصر در ظرف است. برخی از ظرف‌ها اندازه محدودی دارند و برخی دیگر به شکل نامحدود هستند.
  3. پیمایش: به این معنی که چگونه باید عناصر موجود در ظرف را پیمایش کرد، به طوری که بتوان به همه عناصر دسترسی داشت و هر عنصر فقط یک بار مورد دستیابی قرار گیرد.

کلاس‌های ظرف‌ها معمولاً متدهای زیر را پیاده‌سازی می‌کنند:

  • ساخت یک ظرف جدید (سازنده)
  • گزارش کردن تعداد عناصر موجود در ظرف (اندازه)
  • حذف کردن تمام عناصر موجود در ظرف (پاکسازی)
  • درج کردن عناصر جدید در ظرف
  • حذف کردن برخی از عناصر موجود در ظرف
  • ارائه کردن یک روش برای دسترسی به عناصر ظرف

انواع[ویرایش]

ظرف‌ها معمولاً به دو گروه تقسیم می‌شوند:

  1. ظرف‌های مبتنی بر مقدار
  2. ظرف‌های مبتنی بر ارجاع

ظرف‌های مبتنی بر مقدار[ویرایش]

این ظرف‌ها کپی‌هایی از اشیاء را ذخیره می‌کنند. در هنگام دسترسی به یک شی، کپی آن شی برمی‌گردد. اگر یک شی خارجی را پس از درج کردن آن در ظرف، تغییر دهیم، آن تغییر بر روی نمونه ذخیره شده در ظرف تاثیری نخواهد داشت و تنها نمونه خارجی آن شی تغییر می‌کند.

ظرف‌های مبتنی بر ارجاع[ویرایش]

در این گونه از ظرف‌ها، به جای کپی یک شی، اشاره‌گر یا مرجعی به آن شی در ظرف ذخیره می‌شود. اگر بخواهیم به یک شی ذخیره شده در ظرف دسترسی داشته باشیم، به جای کپی آن شی، اشاره‌گری به آن شی برمی‌گردد. اگر یک شی خارجی را پس از ذخیره کردن آن در ظرف، تغییر دهیم، بر روی محتوای ظرف هم اثر گذار خواهد بود.

منفرد یا انجمنی[ویرایش]

یک ظرف ممکن است:

  1. مفرد باشد
  2. انجمنی باشد.

ظرف‌های تک مقداری[ویرایش]

هر شی به شکل مستقل در ظرف ذخیره می‌شود و یا به صورت مستقیم و یا از طریق یک تکرارگر در دسترس قرار می‌گیرد.

ظروف انجمنی[ویرایش]

آرایه انجمنی، نگاشت، یا دیکشنری، ظرفی است که از جفت‌های (کلید، مقدار) تشکیل شده است. در این گونه ظروف، تنها یک نمونه از هر شی می‌تواند در ظرف قرار گیرد. از کلید برای پیدا کردن مقدار یا شیئی که در ظرف ذخیره شده استفاده می‌گردد.

منابع[ویرایش]

  1. Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. US مؤسسه ملی فناوری و استانداردها.15 December 2004. Accessed on Oct 04, 2011.
  2. Entry data structure in the Encyclopædia Britannica (2009) Online entry Accessed on Oct 04, 2011.
  3. ۳٫۰ ۳٫۱ LIFO(investopedia.com)
  4. FIFO(businessdictionary.com)