موضوع مقاله: نوع داده انتزاعی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نوع داده انتزاعی | مقدمه: نوع داده مجرد امکانی را فراهم می‌آورد که باعث شناسایی (معرفی) اشیا از طریق بیان ساختار و رفتار آن‌ها بدون نیاز به اطلاع از نحوه پیاده‌سازی آن ساختار یا رفتار باشد مثال‌ها چند مثال از نوع داده انتزاعی را مطرح می‌کنیم : به عنوان مثال اعداد صحیح (Integers) یک داده‌گونه انتزاعی محسوب می‌شود. | ## بخش 1: نوع داده انتزاعی | این در حالی است که این اعداد می‌توانند به شکل‌های مختلفی همچون اعداد دودویی ، مکمل دو و یا مکمل یک پیاده‌سازی شوند و ولی این جزئیات می‌تواند از نگاه کاربر مخفی باشد و صرفاً از ویژگی‌های اعداد صحیح بهره ببرد. یک عملیات pop که داده را از پشته حذف می‌کند و یک عملیات top که بالاترین داده پشته را خروجی می‌دهد. که این رفتارها شامل تمام عملیات‌های ممکن برای کاربر ، و ویژگی‌هایی است که برای او قابل مشاهده می‌باشد. نوع داده انتزاعی ، یک موجود تماماً تئوری می‌باشد که برای موارد زیر به کار می‌آید : تسهیل توصیف الگوریتم‌هایی که به صورت انتزاعی هستند دسته‌بندی و ارزیابی ساختمان داده‌ها تعریف دقیق سیستم انواع در زبان‌های برنامه‌نویسی باید توجه داشت که نوع داده‌های انتزاعی ، با یک نوع داده و یا یک داده ساختار پیاده‌ساری می‌شوند. که این پیاده‌سازی می‌تواند با روش‌های متعدد و یا زبان‌های برنامه‌نویسی گوناگون انجام پذیرد. همچنین یک نوع داده انتزاعی تحت عنوان نوع داده گرافیکی انتزاعی در سال ۱۹۷۹ مطرح شد. تعریف کردن یک نوع داده انتزاعی یک نوع داده انتزاعی ، به صورت یک مدل ریاضیاتی شامل یک نوع داده تعریف می‌شود. برای تعریف کردن یک نوع داده انتزاعی ، ۲ رویکرد کلی متفاوت شامل رویکرد دستوری (Imperative) و رویکرد تابعی (Functional) وجود دارد رویکرد دستوری: در این رویکرد ، نوع داده انتزاعی به صورت یک ساختار انتزاعی توصیف می‌شود که امکان تغییر حالت در آن وجود دارد. عملیات‌‌هایی که در این مدل تعریف می‌شوند ، می‌توانند حالت آن را تغییر دهند.ترتیب اعمال این عملیات‌ها مهم هستند. به عبارتی عملیات‌های یکسان می‌توانند تأثیرهای متفاوتی در زمان‌های مختلف داشته باشند.‌ رویکرد تابعی: در این رویکرد برخلاف حالت دستوری ، هر حالت یک موجود جدا در نظر گرفته می‌شود. هر عملیاتی که وضعیت ساختار را تغییر می‌دهد ، به صورت یک تابع ریاضی مدل می‌شود که حالت قبلی را به عنوان ورودی دریافت می‌کند و حالت جدید را به عنوان بخشی از خروجی ، تولید می‌کند. | ## بخش 2: نوع داده انتزاعی | این توابع تأثیرات جانبی ندارند و همچنین ترتیب ارزیابی در آن‌ها اهمیتی ندارد و یک عملیات ثابت بر روی یک ورودی ثابت ، همواره خروجی ثابتی تولید خواهد کرد. پیچیدگی زمانی: نوع داده انتزاعی ، این امکان را به ما می‌دهد تا در تعریف آن پیچیدگی زمانی را بگنجانیم. زیرا ما نوع داده‌های انتزاعی را تعریف می‌کنیم تا به ما اجازه دهد که ماژول‌های نرم‌افزاری قابل مبادله‌ای داشته باشیم. این ماژول‌ها باید به نحوی باشند تا ما بتوانیم مستقل از نوع پیاده‌سازی ، عملکرد ثابتی را از نوع داده انتزاعی انتظار داشته باشیم. در صورتی که ما نوع داده انتزاعی را به شکل‌های مختلف پیاده‌سازی کنیم ، یک پیچیدگی زمانی برای عملیات‌های مختلف آن مورد انتظار خواهد بود. بنابراین پیچیدگی زمانی ، جزء غیرقابل حذف واسط‌ها می‌باشد و تمام عملیات‌ها باید همراه با یک پیچیدگی زمانی مشخص تعریف گردند. مزیت‌های نوع داده انتزاعی کپسوله‌سازی: انتزاعی کردن این اطمینان را به ما می‌دهد که هر پیاده‌سازی دلخواهی از این نوع داده انتزاعی ، چه ویژگی‌ها و عملکردهایی دارد. بنابراین ممکن است پیاده‌سازی آن پیچیده باشد ولی هنگامی که از این نوع داده استفاده می‌کنیم ، این پیچیدگی در یک واسط ساده ، کپسوله می‌شود. محلی‌سازی تغییرات: ویژگی‌ها و عملکردهای یک نوع داده انتزاعی ، مستقل از پیاده‌سازی آن ، ثابت است. بنابراین در صورتی که پیاده‌سازی آن دچار تغییراتی شود ، لازم نیست در جاهایی که از این نوع داده استفاده شده است ، هیچ‌گونه تغییری اعمال شود. انعطاف‌پذیری تمام پیاده‌سازی‌های یک نوع داده انتزاعی ، ویژگی‌ها و عملکردهای یکسانی دارند. | ## بخش 3: نوع داده انتزاعی | چرا که ممکن است پیاده‌سازی‌های مختلف یک نوع داده ، در شرایط مختلف عملکرد و سرعت مختلفی داشته باشند. این خاصیت این انعطاف‌پذیری را ایجاد می‌کند که در هر موقعیت ، آن پیاده‌سازی که بهینه‌تر است را به کار ببریم. پیاده‌سازی منظور از پیاده‌سازی یک نوع داده انتزاعی ، ایجاد یک روند یا تابعی است که تمام رفتارهای انتزاعی آن نوع داده را انجام دهد. که این داده ساختار ، متناسب با ویژگی‌های نوع داده ، عمکلرد‌های مشخص‌شده در نوع داده انتزاعی را اجرا می‌کند. عملگرهای معمول در نوع داده‌ی انتزاعی در نوع داده‌های انتزاعی تعدادی عملیات تعریف می‌شود. پرتکرار ترین این عملیات‌ها ، عملیات‌های زیر هستند: مقایسه: یکی از پرتکرارترین عملیات‌ها در نوع داده‌های انتزاعی است که دو حالت مختلف را با هم مقایسه می‌کند. درهم‌سازی: معمولاً ما نیاز پیدا می‌کنیم که حالت خاصی را جست‌وجو کنیم و در صورت وجود به آن دسترسی داشته باشیم. نمایش: ما در نوع داده‌های انتزاعی نیاز داریم تا درصورت لزوم ، یک حالت خاص را نمایش دهیم و برای این منظور باید تابعی در نوع داده انتزاعی در نظر گرفته شود. در رویکرد دستوری نوع داده انتزاعی ، معمولاً عملکردهای زیر گنجانده شده است: ساختن: این تابع یک نمونه جدید از این نوع داده انتزاعی را تولید می‌کند. در این صورت هنگامی که یک نمونه جدید از این نوع داده ساخته شود ،این حالت اولیه ، به آن داده می‌شود. کپی: این تابع یک نمونه را به همان شکل و بدون تغییر در یک نمونه دیگر قرار می‌دهد. | ## جمع‌بندی | آزادکردن: این تابع ، یک حالت قبلی موجود را نابود می‌کند و حافظه اختصاص داده‌شده به آن را آزاد می‌کند.