ویرگول
ورودثبت نام
سهراب خان‌بدر | Sohrab Khanbadr
سهراب خان‌بدر | Sohrab Khanbadrچیزی مثبت بگو، و چیز مثبت خواهی دید." — جیم تامپسون من کیستم ؟ من کجا هستم ؟ من چه میخواهم ؟
سهراب خان‌بدر | Sohrab Khanbadr
سهراب خان‌بدر | Sohrab Khanbadr
خواندن ۷ دقیقه·۳ سال پیش

انواع مجرد داده (ADT) در دنیای برنامه‌نویسی


انواع مجرد داده (ADT) در دنیای برنامه‌نویسی

در این مقاله با مفهوم «انواع مجرد داده» (ADT) آشنا می‌شویم. اما قبل از درک مفهوم ADT، بیایید به انواع داده‌ی از پیش تعریف‌شده‌ای که در اختیار ما قرار داده می‌شوند نگاهی بیندازیم. انواع داده‌ای مانند int، float، double، long و غیره، انواع داده‌ی از پیش تعریف‌شده در نظر گرفته می‌شوند و ما می‌توانیم عملیات اولیه‌ای مانند جمع، تفریق، تقسیم، ضرب و غیره را با آن‌ها انجام دهیم. حال ممکن است وضعیتی پیش بیاید که به عملیات خاصی برای نوع داده‌ی تعریف‌شده توسط کاربر نیاز داشته باشیم که باید تعریف شوند. این عملیات تنها در صورت نیاز قابل تعریف هستند. بنابراین، برای ساده‌سازی فرآیند حل مسائل، می‌توانیم ساختارهای داده را به همراه عملیات آن‌ها ایجاد کنیم. چنین ساختارهای داده‌ای که از پیش تعریف نشده‌اند، به عنوان «انواع مجرد داده» (ADT) شناخته می‌شوند.

تعریف انواع مجرد داده (ADT):

یک نوع مجرد داده (ADT) نوعی (یا کلاسی) برای اشیاء است که رفتار آن‌ها توسط مجموعه‌ای از مقادیر و مجموعه‌ای از عملیات تعریف می‌شود. تعریف ADT تنها به این موضوع اشاره می‌کند که چه عملیاتی باید انجام شود، اما نه اینکه چگونه این عملیات اجرا خواهند شد. این تعریف مشخص نمی‌کند که داده‌ها چگونه در حافظه سازماندهی می‌شوند و از چه الگوریتم‌هایی برای اجرای عملیات استفاده خواهد شد. به دلیل اینکه نمایشی مستقل از پیاده‌سازی ارائه می‌دهد، «مجرد» نامیده می‌شود.

فرایند ارائه‌ی تنها موارد ضروری و پنهان کردن جزئیات به عنوان «انتزاع» شناخته می‌شود.

کاربر نوع داده نیازی ندارد بداند که آن نوع داده چگونه پیاده‌سازی می‌شود. برای مثال، ما از مقادیر اولیه مانند int، float و char استفاده کرده‌ایم، تنها با این دانش که می‌توان روی این انواع داده عملیات انجام داد، بدون اینکه ایده‌ای از نحوه‌ی پیاده‌سازی آن‌ها داشته باشیم.

بنابراین کاربر فقط باید بداند که یک نوع داده چه کاری می‌تواند انجام دهد، اما نه اینکه چگونه اجرا می‌شود. ADT را به عنوان یک جعبه سیاه در نظر بگیرید که ساختار داخلی و طراحی نوع داده را پنهان می‌کند. اکنون سه نوع مجرد داده (ADT) به نام‌های لیست، پشته و صف را تعریف می‌کنیم.

1. لیست (List):

داده‌ها به طور کلی در یک توالی کلیدی در لیستی ذخیره می‌شوند که دارای یک ساختار سرپوش (head) است که از شمارنده، اشارهگرها و آدرس تابع مقایسه برای مقایسه‌ی داده‌ها در لیست تشکیل شده است.

گره‌ی داده حاوی اشاره‌گر به یک ساختار داده و یک اشاره‌گر خودارجاعی است که به گره‌ی بعدی در لیست اشاره می‌کند.

توابع لیست به شرح زیر است:

  • get() - عنصری را از لیست در هر موقعیت دلخواه برگرداند.
  • insert() - درج یک عنصر در هر موقعیت دلخواه از لیست.
  • remove() - اولین رخداد هر عنصری را از لیستی غیرتهی حذف کند.
  • removeAt() - حذف عنصر در موقعیت مشخص‌شده از لیستی غیرتهی.
  • replace() - جایگزینی یک عنصر در هر موقعیتی با عنصر دیگر.
  • size() - تعداد عناصر موجود در لیست را برگرداند.
  • isEmpty() - اگر لیست خالی باشد True برگرداند، در غیر این صورت False برگرداند.
  • isFull() - اگر لیست پر باشد True برگرداند، در غیر این صورت False برگرداند.

2. پشته (Stack):

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

گره سر و گره‌های داده در ADT کپسوله‌سازی شده‌اند. تابع فراخوان فقط می‌تواند اشاره‌گر به پشته را ببیند.

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

  • push() - درج یک عنصر در یک انتهای پشته به نام بالا (top).
  • pop() - عنصر بالایی پشته را حذف و برگرداند (در صورتی که خالی نباشد).
  • peek() - عنصر بالایی پشته را بدون حذف برگرداند (در صورتی که پشته خالی نباشد).
  • size() - تعداد عناصر موجود در پشته را برگرداند.
  • isEmpty() - اگر پشته خالی باشد True برگرداند، در غیر این صورت False برگرداند.
  • isFull() - اگر پشته پر باشد True برگرداند، در غیر این صورت False برگرداند.

3. صف (Queue):

نوع مجرد داده صف (Queue) از طراحی پایه‌ای نوع مجرد داده پشته (Stack) پیروی می‌کند.

هر گره شامل یک اشاره‌گر تهی به داده و یک اشاره‌گر پیوندی به عنصر بعدی در صف است. وظیفه‌ی برنامه تخصیص حافظه برای ذخیره‌ی داده است.

  • enqueue() - درج یک عنصر در انتهای صف.
  • dequeue() - اولین عنصر صف را حذف و برگرداند (در صورتی که صف خالی نباشد).
  • peek() - عنصر اول صف را بدون حذف برگرداند (در صورتی که صف خالی نباشد).
  • size() - تعداد عناصر موجود در صف را برگرداند.
  • isEmpty() - اگر صف خالی باشد True برگرداند، در غیر این صورت False برگرداند.
  • isFull() - اگر صف پر باشد True برگرداند، در غیر این صورت False برگرداند.

ویژگی‌های انواع مجرد داده (ADT):

  • انتزاع: کاربر نیازی به دانستن جزئیات پیاده‌سازی ساختار داده ندارد، فقط اطلاعات ضروری ارائه می‌شود.
  • مفاهیم‌سازی بهتر: ADT به ما درک بهتری از دنیای واقعی می‌دهد.
  • قوی: برنامه قوی است و توانایی شناسایی خطاها را دارد.
  • کپسوله‌سازی: ADT جزئیات داخلی داده را پنهان می‌کند و رابط عمومی برای تعامل کاربران با داده ارائه می‌دهد. این امر نگهداری و اصلاح ساختار داده را آسان‌تر می‌کند.
  • انتزاع داده: ADT سطحی از انتزاع را از جزئیات پیاده‌سازی داده ارائه می‌دهد. کاربران فقط باید عملیات قابل انجام روی داده را بدانند، نه اینکه چگونه آن عملیات اجرا می‌شوند.
  • استقلال ساختار داده: ADT را می‌توان با استفاده از ساختارهای داده مختلف مانند آرایه‌ها یا لیست‌های پیوندی بدون تحت تاثیر قرار دادن عملکرد ADT پیاده‌سازی کرد.
  • پنهان کردن اطلاعات: ADT می‌تواند با کنترل دسترسی و جلوگیری از تغییرات غیرمجاز، از یکپارچگی داده‌ها محافظت کند. این امر به جلوگیری از خطاها و سوء استفاده از داده‌ها کمک می‌کند.
  • مدولاریتی: ADT را می‌توان با ADTهای دیگر ترکیب کرد تا ساختارهای داده بزرگ‌تر و پیچیده‌تر را تشکیل داد. این امر انعطاف‌پذیری و مدولاریتی بیشتر در برنامه‌نویسی را فراهم می‌کند.

مزایا و معایب انواع مجرد داده (ADT):


مزایا:

  • کپسوله‌سازی: ADT روشی برای کپسوله‌سازی داده و عملیات در یک واحد واحد ارائه می‌دهد و مدیریت و اصلاح ساختار داده را آسان‌تر می‌کند.
  • انتزاع: ADT به کاربران اجازه می‌دهد تا با ساختارهای داده بدون نیاز به دانستن جزئیات پیاده‌سازی کار کنند، که می‌تواند برنامه‌نویسی را ساده‌تر کند و خطاها را کاهش دهد.
  • استقلال ساختار داده: ADT را می‌توان با استفاده از ساختارهای داده مختلف مانند آرایه‌ها یا لیست‌های پیوندی پیاده‌سازی کرد که می‌تواند انطباق با نیازها و الزامات در حال تغییر را آسان‌تر کند.
  • پنهان کردن اطلاعات: ADT می‌تواند با کنترل دسترسی و جلوگیری از تغییرات غیرمجاز، از یکپارچگی داده‌ها محافظت کند.
  • مدولاریتی: ADT را می‌توان با ADTهای دیگر ترکیب کرد تا ساختارهای داده بزرگ‌تر و پیچیده‌تر را تشکیل داد. این امر انعطاف‌پذیری و مدولاریتی بیشتر در برنامه‌نویسی را فراهم می‌کند.

معایب:

  • ** سربار:** پیاده‌سازی ADT می‌تواند سربار حافظه و پردازش را اضافه کند که می‌تواند بر عملکرد تأثیر بگذارد.
  • پیچیدگی: ADT می‌تواند پیچیده باشد، به خصوص برای ساختارهای داده بزرگ و پیچیده.
  • منحنی یادگیری: استفاده از ADT نیاز به دانش پیاده‌سازی و استفاده از آنها دارد که می‌تواند زمان و تلاش برای یادگیری را به خود اختصاص دهد.
  • انعطاف‌پذیری محدود: برخی از ADTها ممکن است در عملکرد خود محدود باشند یا برای همه انواع ساختارهای داده مناسب نباشند.
  • هزینه: پیاده‌سازی ADT ممکن است به منابع و سرمایه‌گذاری اضافی نیاز داشته باشد که می‌تواند هزینه توسعه را افزایش دهد.

نتیجه‌گیری:

به طور کلی، مزایای ADTها اغلب بیشتر از معایب آنها است و آنها به طور گسترده در توسعه نرم‌افزار برای مدیریت و دستکاری داده‌ها به روشی ساختاریافته و کارآمد استفاده می‌شوند. با این حال، مهم است که نیازها و الزامات خاص یک پروژه را هنگام تصمیم‌گیری برای استفاده از ADTها در نظر بگیرید.

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

این مقاله توسط Anuj Chauhan نوشته شده است.

اگر به GeeksforGeeks علاقه دارید و می‌خواهید به آن کمک کنید، می‌توانید با استفاده از write.geeksforgeeks.org مقاله‌ای بنویسید یا مقاله خود را به [email protected] ارسال کنید. مقاله خود را در صفحه اصلی GeeksforGeeks مشاهده کنید و به دیگر Geeks کمک کنید.

آخرین به‌روزرسانی: 23 سپتامبر 2023

۰
۰
سهراب خان‌بدر | Sohrab Khanbadr
سهراب خان‌بدر | Sohrab Khanbadr
چیزی مثبت بگو، و چیز مثبت خواهی دید." — جیم تامپسون من کیستم ؟ من کجا هستم ؟ من چه میخواهم ؟
شاید از این پست‌ها خوشتان بیاید