نوع داده انتزاعی
در علوم رایانه، یک نوع داده انتزاعی (به انگلیسی: Abstract Data Type، مخفف: ADT) یک مدل ریاضی برای رده خاصی از ساختارهای داده است که عملکرد مشابهی دارند؛ یا برای انواع داده یک یا چند زبان برنامه‌نویسی است که دارای معناشناسی یکسانی هستند، به کار می‌رود.
نوع داده مجرد امکانی را فراهم می‌آورد که باعث شناسایی (معرفی) اشیا از طریق بیان ساختار و رفتار آن‌ها بدون نیاز به اطلاع از نحوه پیاده‌سازی آن ساختار یا رفتار باشد
مثال‌ها[ویرایش]
چند مثال از نوع داده انتزاعی را مطرح می‌کنیم[۱] :
- به عنوان مثال اعداد صحیح (Integers) یک داده‌گونه انتزاعی محسوب می‌شود. که یک مجموعه با مقادیر ... -۱و 0 و ۱ و ... و همراه با عملیات‌های جمع ، تفریق ، ضرب و تقسیم توصیف می‌شود. این در حالی است که این اعداد می‌توانند به شکل‌های مختلفی همچون اعداد دودویی ، مکمل دو و یا مکمل یک پیاده‌سازی شوند و ولی این جزئیات می‌تواند از نگاه کاربر مخفی باشد و صرفاً از ویژگی‌های اعداد صحیح بهره ببرد.
- به عنوان مثالی دیگر می‌توان پشته (Stack) را نام برد. این یک ساختار انتزاعی دارای رفتار LIFO می‌باشد که ۳ عملیات اساسی دارد. یک عملیات push که داده را در پشته درج می‌کند. یک عملیات pop که داده را از پشته حذف می‌کند و یک عملیات top که بالاترین داده پشته را خروجی می‌دهد.
- صف (Queue) ، نیز یک نوع داده انتزاعی است. این ساختار دارای رفتار FIFO می‌باشد. صف یک عملیات enqueue برای اضافه کردن داده به یک طرف صف و یک عملیات dequeue برای خارج کردن داده از طرف دیگر صف دارد.
تعریف و کاربردها[ویرایش]
به طور دقیق ، یک نوع داده انتزاعی ، یک کلاس از اشیاء تعریف می‌شود که رفتار آن با مجموعه‌ای از مقادیر و عملیات‌ها مشخص می‌گردد.[۲]
این انواع داده انتزاعی ، مشابه با ساختارهای جبری در ریاضیات می‌باشند.
نوع داده انتزاعی ، آن رفتاری است که از جانب کاربر مشاهده می‌شود. که این رفتارها شامل تمام عملیات‌های ممکن برای کاربر ، و ویژگی‌هایی است که برای او قابل مشاهده می‌باشد.
نوع داده انتزاعی ، یک موجود تماماً تئوری می‌باشد که برای موارد زیر به کار می‌آید[۳] :
- تسهیل توصیف الگوریتم‌هایی که به صورت انتزاعی هستند
- دسته‌بندی و ارزیابی ساختمان داده‌ها
- تعریف دقیق سیستم انواع در زبان‌های برنامه‌نویسی
باید توجه داشت که نوع داده‌های انتزاعی ، با یک نوع داده و یا یک داده ساختار پیاده‌ساری می‌شوند. که این پیاده‌سازی می‌تواند با روش‌های متعدد و یا زبان‌های برنامه‌نویسی گوناگون انجام پذیرد.
نوع داده انتزاعی می‌تواند در جایگاه‌های دیگری نیز به کار برده شود. که از جمله‌ی آن‌ها می‌توان به ساختارهای جبری از جمله لتیس ، گروه یا حلقه را نام برد.[۴]
همچنین یک نوع داده انتزاعی تحت عنوان نوع داده گرافیکی انتزاعی در سال ۱۹۷۹ مطرح شد. [۵] در آن مزیت‌های نوع داده انتزاعی به کار گرفته می‌شود تا فرآیند ساختن اشیاء گرافیکی تسهیل شود و در یک روند ساختارمند انجام گیرد.
تعریف کردن یک نوع داده انتزاعی[ویرایش]
یک نوع داده انتزاعی ، به صورت یک مدل ریاضیاتی شامل یک نوع داده تعریف می‌شود. این مدل شامل توابعی نیز می‌باشد که عملیاتهایی روی این نوع داده انجام می‌دهند. برای تعریف کردن یک نوع داده انتزاعی ، ۲ رویکرد کلی متفاوت شامل رویکرد دستوری (Imperative) و رویکرد تابعی (Functional) وجود دارد[۶]:
- رویکرد دستوری:
- در این رویکرد ، نوع داده انتزاعی به صورت یک ساختار انتزاعی توصیف می‌شود که امکان تغییر حالت در آن وجود دارد. این به این معنی است که می‌تواند در زمان‌های گوناگون در حالت‌های متفاوتی باشد. عملیاتهایی که در این مدل تعریف می‌شوند ، می‌توانند حالت آن را تغییر دهند.ترتیب اعمال این عملیات‌ها مهم هستند. به عبارتی عملیات‌های یکسان می‌توانند تأثیرهای متفاوتی در زمان‌های مختلف داشته باشند.
- رویکرد تابعی:
- در این رویکرد برخلاف حالت دستوری ، هر حالت یک موجود جدا در نظر گرفته می‌شود. هر عملیاتی که وضعیت ساختار را تغییر می‌دهد ، به صورت یک تابع ریاضی مدل می‌شود که حالت قبلی را به عنوان ورودی دریافت می‌کند و حالت جدید را به عنوان بخشی از خروجی ، تولید می‌کند. این توابع تأثیرات جانبی ندارند و همچنین ترتیب ارزیابی در آن‌ها اهمیتی ندارد و یک عملیات ثابت بر روی یک ورودی ثابت ، همواره خروجی ثابتی تولید خواهد کرد.
پیچیدگی زمانی: نوع داده انتزاعی ، این امکان را به ما می‌دهد تا در تعریف آن پیچیدگی زمانی را بگنجانیم. این امر کاملاً ضروری است. زیرا ما نوع داده‌های انتزاعی را تعریف می‌کنیم تا به ما اجازه دهد که ماژول‌های نرم‌افزاری قابل مبادله‌ای داشته باشیم. این ماژول‌ها باید به نحوی باشند تا ما بتوانیم مستقل از نوع پیاده‌سازی ، عملکرد ثابتی را از نوع داده انتزاعی انتظار داشته باشیم. در صورتی که ما نوع داده انتزاعی را به شکل‌های مختلف پیاده‌سازی کنیم ، یک پیچیدگی زمانی برای عملیات‌های مختلف آن مورد انتظار خواهد بود. بنابراین پیچیدگی زمانی ، جزء غیرقابل حذف واسط‌ها می‌باشد و تمام عملیات‌ها باید همراه با یک پیچیدگی زمانی مشخص تعریف گردند.
مزیت‌های نوع داده انتزاعی[ویرایش]
- انتزاعی کردن این اطمینان را به ما می‌دهد که هر پیاده‌سازی دلخواهی از این نوع داده انتزاعی ، چه ویژگی‌ها و عملکردهایی دارد. تعریف کردن این دو خصوصیت ، برای ساختن یک نوع داده انتزاعی ، لازم و کافی است. بنابراین ممکن است پیاده‌سازی آن پیچیده باشد ولی هنگامی که از این نوع داده استفاده می‌کنیم ، این پیچیدگی در یک واسط ساده ، کپسوله می‌شود. [۷]
- محلی‌سازی تغییرات:
- ویژگی‌ها و عملکردهای یک نوع داده انتزاعی ، مستقل از پیاده‌سازی آن ، ثابت است. بنابراین در صورتی که پیاده‌سازی آن دچار تغییراتی شود ، لازم نیست در جاهایی که از این نوع داده استفاده شده است ، هیچ‌گونه تغییری اعمال شود.
- انعطاف‌پذیری
- تمام پیاده‌سازی‌های یک نوع داده انتزاعی ، ویژگی‌ها و عملکردهای یکسانی دارند. این خصوصیت ، موجب انعطاف‌پذیری می‌شود. چرا که ممکن است پیاده‌سازی‌های مختلف یک نوع داده ، در شرایط مختلف عملکرد و سرعت مختلفی داشته باشند. این خاصیت این انعطاف‌پذیری را ایجاد می‌کند که در هر موقعیت ، آن پیاده‌سازی که بهینه‌تر است را به کار ببریم.
پیاده‌سازی[ویرایش]
منظور از پیاده‌سازی یک نوع داده انتزاعی ، ایجاد یک روند یا تابعی است که تمام رفتارهای انتزاعی آن نوع داده را انجام دهد. پیاده‌سازی یک نوع داده انتزاعی با یک داده ساختار مشخص نمایش داده می‌شود. که این داده ساختار ، متناسب با ویژگی‌های نوع داده ، عمکلرد‌های مشخص‌شده در نوع داده انتزاعی را اجرا می‌کند.
عملگرهای معمول در نوع داده‌ی انتزاعی[ویرایش]
در نوع داده‌های انتزاعی تعدادی عملیات تعریف می‌شود. تعدادی از عملیات‌ها در بسیاری از این نوع داده‌ها تکرار می‌شوند. پرتکرار ترین این عملیات‌ها ، عملیات‌های زیر هستند:[۸]
- مقایسه: یکی از پرتکرارترین عملیات‌ها در نوع داده‌های انتزاعی است که دو حالت مختلف را با هم مقایسه می‌کند.
- درهم‌سازی: معمولاً ما نیاز پیدا می‌کنیم که حالت خاصی را جست‌وجو کنیم و در صورت وجود به آن دسترسی داشته باشیم. توابع درهم‌سازی در نوع داده‌های انتزاعی چنین وظیفه‌ای را دارند.
- نمایش: ما در نوع داده‌های انتزاعی نیاز داریم تا درصورت لزوم ، یک حالت خاص را نمایش دهیم و برای این منظور باید تابعی در نوع داده انتزاعی در نظر گرفته شود.
در رویکرد دستوری نوع داده انتزاعی ، معمولاً عملکردهای زیر گنجانده شده است:
- ساختن: این تابع یک نمونه جدید از این نوع داده انتزاعی را تولید می‌کند.
- مقداردهی اولیه: یک حالت جدید در ابتدا برای نوع داده انتزاعی ایجاد می‌کند. در این صورت هنگامی که یک نمونه جدید از این نوع داده ساخته شود ،این حالت اولیه ، به آن داده می‌شود.
- کپی: این تابع یک نمونه را به همان شکل و بدون تغییر در یک نمونه دیگر قرار می‌دهد.
- کلون: این تابع یک حالت را انتشار می‌دهد و چند نسخه از آن را تولید می‌کند.
- آزادکردن: این تابع ، یک حالت قبلی موجود را نابود می‌کند و حافظه اختصاص داده‌شده به آن را آزاد می‌کند.
منابع[ویرایش]
- ↑ https://en.wikipedia.org/wiki/Abstract_data_type#Examples
- ↑ Dale, Nell; Walker, Henry M. (1996). Abstract Data Types: Specifications, Implementations, and Applications. Jones & Bartlett Learning. ISBN 978-0-66940000-7.
- ↑ https://en.wikipedia.org/wiki/Abstract_data_type#Introduction
- ↑ Rudolf Lidl (2004). Abstract Algebra. Springer. ISBN 978-81-8128-149-4., Chapter 7, section 40.
- ↑ D. Thalmann, N. Magnenat Thalmann (1979). Design and Implementation of Abstract Graphical Data Types. IEEE. doi:10.1109/CMPSAC.1979.762551., Proc. 3rd International Computer Software and Applications Conference (COMPSAC'79), IEEE, Chicago, USA, pp.519-524
- ↑ https://en.wikipedia.org/wiki/Abstract_data_type#Defining_an_abstract_data_type
- ↑ "Encapsulation - an overview | ScienceDirect Topics". www.sciencedirect.com. Retrieved 2020-05-01.
- ↑ https://en.wikipedia.org/wiki/Abstract_data_type#Typical_operations
پانویس[ویرایش]
- Wikipedia contributors, "Abstract data type," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Abstract_data_type&oldid=518919191 (accessed October 21, 2012).