نوع داده انتزاعی

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

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

به طور رسمی، ADT ممکن است به عنوان "کلاسی از اشیاء که رفتار منطقی آنها توسط مجموعه ای از مقادیر و مجموعه ای از عملیات تعریف می شود" تعریف شود. [1] این مشابه ساختار جبری در ریاضیات است. منظور از "رفتار" در نویسنده متفاوت است، با دو نوع اصلی از مشخصات رسمی برای رفتار، مشخصات بدیهی (جبری) و یک مدل انتزاعی. [2] اینها به ترتیب با معناشناسی بدیهی و معناشناسی عملیاتی یک ماشین انتزاعی مطابقت دارند. برخی از نویسندگان پیچیدگی محاسباتی را نیز شامل می شوند("هزینه")، هم از نظر زمان (برای عملیات محاسباتی) و هم از نظر مکان (برای نمایش مقادیر). در عمل، بسیاری از انواع داده های رایج ADT نیستند، زیرا انتزاع کامل نیست، و کاربران باید از مسائلی مانند سرریز حسابی که به دلیل نمایش است آگاه باشند. به عنوان مثال، اعداد صحیح اغلب به عنوان مقادیر با عرض ثابت (اعداد باینری 32 بیتی یا 64 بیتی) ذخیره می شوند و بنابراین در صورت تجاوز از حداکثر مقدار، سرریز اعداد صحیح را تجربه می کنند.

ADTها یک مفهوم نظری در علوم کامپیوتر هستند که در طراحی و تجزیه و تحلیل الگوریتم‌ها ، ساختار داده‌ها و سیستم‌های نرم‌افزاری استفاده می‌شوند و با ویژگی‌های خاص زبان‌های رایانه مطابقت ندارند - زبان‌های اصلی رایانه مستقیماً از ADT‌های مشخص شده رسمی پشتیبانی نمی‌کنند. با این حال، ویژگی های مختلف زبان با جنبه های خاصی از ADT ها مطابقت دارد و به راحتی با ADT های مناسب اشتباه گرفته می شود. اینها شامل انواع انتزاعی ، انواع داده های غیر شفاف ، پروتکل ها و طراحی بر اساس قرارداد می باشد. ADT ها برای اولین بار توسط باربارا لیسکوف و استفان ان. زیلس در سال 1974 به عنوان بخشی از توسعه زبان CLU پیشنهاد شدند. [3]

انواع داده های انتزاعی

به عنوان مثال، اعداد صحیح یک ADT هستند که به عنوان مقادیر ...، -2، -1، 0، 1، 2، ... و با عملیات جمع، تفریق، ضرب و تقسیم به همراه مقادیر بیشتر از ، کمتر از و غیره، که مستقل از نحوه نمایش اعداد صحیح توسط رایانه ، مطابق با ریاضیات آشنا (با مراقبت از تقسیم اعداد صحیح ) رفتار می کنند. [a] به صراحت، «رفتار» شامل اطاعت از بدیهیات مختلف (تداعی و جابه‌جایی جمع و غیره) و پیش‌شرط‌های عملیات (نمی‌توان بر صفر تقسیم کرد) است. معمولاً اعداد صحیح در یک ساختار داده به صورت اعداد باینری ، اغلب به صورت مکمل دو نشان داده می شوند ، اما ممکن است اعشاری با کد باینری یا به صورت اعشاری باشند.مکمل یکی است ، اما برای بیشتر اهداف کاربر می‌تواند با انتزاع کار کند تا انتخاب عینی نمایش، و به سادگی می‌تواند از داده‌ها استفاده کند که گویی نوع واقعاً انتزاعی است.

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

به عنوان مثال، یک پشته انتزاعی ، که یک ساختار آخرین در اول است، می تواند با سه عملیات تعریف شود: pushکه یک آیتم داده را در پشته قرار می دهد. pop، که یک آیتم داده را از آن حذف می کند. و peekیا top، که بدون حذف به یک آیتم داده در بالای پشته دسترسی دارد. یک صف انتزاعی ، که یک ساختار first-in-first-out است، همچنین دارای سه عملیات است: enqueueکه یک آیتم داده را در صف قرار می دهد. dequeue، که اولین مورد داده را از آن حذف می کند. وfront، که به اولین مورد داده در صف دسترسی پیدا می کند و سرویس می دهد. اگر اینها کل تعاریف بودند، هیچ راهی برای تمایز این دو نوع داده و رفتار سفارشی مورد انتظار بسیار متفاوت آنها وجود نداشت. بنابراین، محدودیتی معرفی می‌شود که برای یک پشته مشخص می‌کند که هر پاپ همیشه آخرین مورد فشار داده شده را که هنوز پاپ نشده است را برمی‌گرداند (و حذف می‌کند) و برای یک صف (در مقابل) مشخص می‌کند که pop روی آیتم کم‌تر فشار داده شده عمل می‌کند. .

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

مقدمه

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

اصطلاح نوع داده انتزاعی را می توان به عنوان رویکرد تعمیم یافته تعدادی از ساختارهای جبری مانند شبکه ها، گروه ها و حلقه ها در نظر گرفت. [4] مفهوم انواع داده های انتزاعی مربوط به مفهوم انتزاع داده است که در برنامه نویسی شی گرا و طراحی با روش های قراردادی برای توسعه نرم افزار مهم است . [5]

تعریف یک نوع داده انتزاعی

یک نوع داده انتزاعی به عنوان یک مدل ریاضی از اشیاء داده ای که یک نوع داده را تشکیل می دهند و همچنین توابعی که روی این اشیاء عمل می کنند، تعریف می شود. هیچ قرارداد استانداردی برای تعریف آنها وجود ندارد. ممکن است یک تقسیم بندی گسترده بین سبک های تعریف «واجبی» (یا «عملیاتی») و «کارکردی» (یا «بدیهی») صورت گیرد.

تعریف سبک امری

در تئوری زبان های برنامه نویسی امری ، ساختار داده انتزاعی به عنوان موجودی قابل تغییر در نظر گرفته می شود - به این معنی که ممکن است در حالت های مختلف در زمان های مختلف باشد. برخی از عملیات ممکن است وضعیت ADT را تغییر دهد. بنابراین، ترتیب ارزیابی عملیات مهم است و همان عملیات روی یک موجودیت ممکن است اثرات متفاوتی داشته باشد، اگر در زمان‌های مختلف اجرا شود. این مشابه دستورالعمل های یک کامپیوتر، یا دستورات و رویه های یک زبان امری است. برای تأکید بر این دیدگاه، مرسوم است که بگوییم عملیات به جای ارزیابی ، اجرا یا اعمال می شود .، شبیه به سبک امری است که اغلب هنگام توصیف الگوریتم های انتزاعی استفاده می شود. ( برای جزئیات بیشتر به هنر برنامه نویسی کامپیوتری توسط دونالد کنات مراجعه کنید).

متغیر چکیده

تعاریف سبک امری ADT اغلب به مفهوم یک متغیر انتزاعی بستگی دارد که ممکن است به عنوان ساده ترین ADT غیر پیش پا افتاده در نظر گرفته شود. یک متغیر انتزاعی V یک موجودیت قابل تغییر است که دو عملیات را می پذیرد:

  • store( V , x ) که در آن x مقداری با ماهیت نامشخص است.
  • fetch( V )، که یک مقدار را به دست می دهد،

با این محدودیت که

  • fetch( V ) همیشه مقدار x مورد استفاده در آخرین عملیات store( V , x ) روی همان متغیر V را برمی‌گرداند .

واکشی قبل از ذخیره‌سازی را می‌توان غیرمجاز، تعریف کرد که نتیجه خاصی داشته باشد، یا (به‌طور کمتر مطلوب)، رفتار را نامشخص بگذارد.

مانند بسیاری از زبان های برنامه نویسی، عملیات store( V ، x ) اغلب با Vx (یا نمادهای مشابه) نوشته می شود، و fetch( V ) هر زمان که یک متغیر V در زمینه ای که یک مقدار مورد نیاز است استفاده می شود، ضمنی است. بنابراین، به عنوان مثال، VV + 1 معمولاً به عنوان storeمخفف ( V ، fetch( V ) + 1 شناخته می شود.

در این تعریف، به طور ضمنی فرض می‌شود که نام‌ها همیشه متمایز هستند: ذخیره یک مقدار در یک متغیر U تأثیری بر وضعیت متغیر متمایز V ندارد. برای صریح کردن این فرض، می توان محدودیتی را اضافه کرد که

  • اگر U و V متغیرهای متمایز هستند، دنباله { store( U , x ); store( V , y ) } معادل { store( V , y ) است. store( U ، x )}.

به طور کلی تر، تعاریف ADT اغلب فرض می کنند که هر عملیاتی که وضعیت یک نمونه ADT را تغییر می دهد تأثیری بر وضعیت هر نمونه دیگری از همان ADT ندارد، مگر اینکه بدیهیات ADT نمونه های خاصی را به صورت متصل تعریف کنند (به نام مستعار مراجعه کنید ) . رایج ترین این اتصالات عبارتند از:

  • نام مستعار، که در آن دو یا چند نام دقیقاً به یک شی داده اشاره دارد.
  • ترکیبی که در آن یک ADT حاوی نمونه هایی از (همان یا دیگر) ADT ها تعریف می شود.
  • مرجع، که در آن یک ADT برای اشاره به نمونه ای از (همان یا دیگر) ADT ها تعریف می شود.

برای مثال، وقتی تعریف یک متغیر انتزاعی را برای گنجاندن رکوردهای انتزاعی بسط می‌دهیم ، عملیات روی یک فیلد F از متغیر رکورد R ، به وضوح F را در بر می‌گیرد ، که متمایز از R ، اما همچنین بخشی از آن است .

تعریف یک ADT ممکن است مقدار(های) ذخیره شده را برای نمونه های آن محدود به اعضای یک مجموعه خاص X به نام محدوده آن متغیرها کند. به عنوان مثال، یک ADT برای یک مجموعه مانند یک پشته یا صف، ممکن است همه موارد موجود در صف را محدود کند که اعداد صحیح باشند یا حداقل همه از یک نوع باشند (به همگنی مراجعه کنید ). مانند زبان های برنامه نویسی، چنین محدودیت هایی ممکن است توصیف و تحلیل الگوریتم ها را ساده کرده و خوانایی آن را بهبود بخشد.

توجه داشته باشید که این تعریف چیزی در مورد نتیجه ارزیابی fetch( V ) در زمانی که V اولیه نشده است ، یعنی قبل از انجام هر storeعملیاتی بر روی V ، دلالت نمی کند . الگوریتمی که این کار را انجام می دهد ممکن است نامعتبر در نظر گرفته شود، یا (الف) زیرا ADT چنین عملیاتی را ممنوع می کند، یا (ب) صرفاً به این دلیل که اثر آن توسط ADT تعریف نشده است. با این حال، برخی از الگوریتم‌های مهم وجود دارند که کارایی آنها به شدت به این فرض بستگی دارد که چنین fetchچیزی قانونی است و مقداری دلخواه را در محدوده متغیر برمی‌گرداند. [ نیازمند منبع ] )

ایجاد نمونه

برخی از الگوریتم ها نیاز به ایجاد نمونه های جدیدی از برخی ADT دارند (مانند متغیرهای جدید یا پشته های جدید). برای توصیف چنین الگوریتم‌هایی، معمولاً در تعریف ADT یک createعملیات () گنجانده می‌شود که نمونه‌ای از ADT را به دست می‌دهد، معمولاً با بدیهیات معادل

  • نتیجه create() از هر نمونه ای که قبلاً توسط الگوریتم استفاده شده است متمایز است.

این بدیهیات را می توان تقویت کرد تا همخوانی جزئی با نمونه های دیگر را حذف کند [ توضیحات لازم است ] . برای استفاده عملی، مانند بدیهیات ممکن است همچنان به پیاده سازی های create() اجازه دهد تا نمونه ای از قبل ایجاد شده را که برای برنامه غیرقابل دسترس شده است، ایجاد کند. با این حال، تعریف این که چنین مثالی حتی "همان" است، به ویژه در انتزاع دشوار است (اگرچه حتی یک بلوک حافظه که دوباره استفاده می شود فقط "همان شی" در معانی خاصی است).

مثال: پشته انتزاعی (ضروری)

به عنوان مثالی دیگر، یک تعریف به سبک دستوری از یک پشته انتزاعی می تواند مشخص کند که وضعیت پشته S را فقط می توان با عملیات تغییر داد.

  • push( S ، x )، که در آن x مقداری از طبیعت نامشخص است.
  • pop( S )، که در نتیجه یک مقدار به دست می دهد،

با این محدودیت که

  • برای هر مقدار x و هر متغیر انتزاعی V ، دنباله عملیات { push( S , x ); Vpop( S ) } معادل Vx است.

از آنجایی که انتساب Vx ، بنا به تعریف، نمی تواند وضعیت S را تغییر دهد ، این شرط نشان می دهد که Vpop( S ) S را به حالت قبل از push( S ، x ) باز می گرداند . از این شرط و از ویژگی های متغیرهای انتزاعی، به عنوان مثال، نتیجه می شود که دنباله

{ push( S , x ); push( S , yUpop( S ); push( S ، zVpop( S ); Wpop( S ) }

که در آن x , y , و z هر مقدار هستند و U , V , W متغیرهای متمایز جفتی هستند که معادل

{ Uy ; Vz ; Wx }

در اینجا به طور ضمنی فرض می شود که عملیات روی یک نمونه پشته، وضعیت هیچ نمونه ADT دیگر، از جمله پشته های دیگر را تغییر نمی دهد. به این معنا که،

  • برای هر مقدار x , y , و هر پشته متمایز S و T , دنباله { push( S , x ); push( T , y ) } معادل { push( T , y ) است. push( S , x )}.

یک تعریف پشته انتزاعی معمولاً شامل یک تابع با ارزش بولیempty ( S ) و یک createعملیات () است که یک نمونه پشته را با بدیهیات معادل برمی گرداند.

  • create() ≠ S برای هر پشته قبلی S (یک پشته جدید ایجاد شده از همه پشته های قبلی متمایز است).
  • empty( create()) (پشته ای که به تازگی ایجاد شده خالی است).
  • not empty( push( S , x )) (فشار دادن چیزی به پشته باعث می شود خالی نباشد).

سبک تک نمونه ای

گاهی اوقات یک ADT به گونه‌ای تعریف می‌شود که گویی تنها یک نمونه از آن در طول اجرای الگوریتم وجود داشته است و همه عملیات‌ها بر روی آن نمونه اعمال شده‌اند که به صراحت ذکر نشده است. برای مثال، پشته انتزاعی بالا را می‌توان با عملیات push( x ) و pop() که روی تنها پشته موجود عمل می‌کنند، تعریف کرد . تعاریف ADT در این سبک را می توان به راحتی بازنویسی کرد تا چندین نمونه از ADT را با هم وجود داشته باشد، با افزودن یک پارامتر نمونه صریح (مانند S در مثال قبلی) به هر عملیاتی که از نمونه ضمنی استفاده یا اصلاح می کند.

از سوی دیگر، برخی از ADT ها را نمی توان بدون فرض چند نمونه به طور معناداری تعریف کرد. این مورد زمانی است که یک عملیات واحد دو نمونه مجزا از ADT را به عنوان پارامتر در نظر می گیرد. برای مثال، تعریف پشته انتزاعی را با یک عملیات compare( S ، T ) در نظر بگیرید که بررسی می‌کند آیا پشته‌های S و T حاوی موارد مشابهی هستند یا خیر.

تعریف سبک عملکردی

راه دیگر برای تعریف یک ADT، نزدیکتر به روح برنامه نویسی تابعی ، در نظر گرفتن هر حالت از ساختار به عنوان یک موجودیت جداگانه است. در این دیدگاه، هر عملیاتی که ADT را تغییر دهد به عنوان یک تابع ریاضی مدل‌سازی می‌شود که حالت قدیمی را به عنوان آرگومان می‌گیرد و حالت جدید را به عنوان بخشی از نتیجه برمی‌گرداند. بر خلاف عملیات ضروری، این توابع عوارض جانبی ندارند . بنابراین، ترتیب ارزیابی آنها بی اهمیت است و همان عملیات اعمال شده بر روی آرگومان های یکسان (شامل همان حالت های ورودی) همیشه همان نتایج (و حالت های خروجی) را برمی گرداند.

به طور خاص، در دیدگاه عملکردی، هیچ راهی (یا نیازی) برای تعریف «متغیر انتزاعی» با معنایی متغیرهای امری (یعنی با fetchو storeعملیات) وجود ندارد. به جای ذخیره مقادیر در متغیرها، فرد آنها را به عنوان آرگومان به توابع ارسال می کند.

مثال: پشته انتزاعی (عملکردی)

به عنوان مثال، یک تعریف کامل به سبک عملکردی از یک پشته انتزاعی می تواند از سه عملیات استفاده کند:

  • push: حالت پشته و مقدار دلخواه را می گیرد، وضعیت پشته را برمی گرداند.
  • top: یک حالت پشته می گیرد، یک مقدار برمی گرداند.
  • pop: حالت پشته را می گیرد، حالت پشته را برمی گرداند.

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

به جای create()، یک تعریف به سبک عملکردی از یک پشته انتزاعی ممکن است وجود یک حالت پشته خاص را فرض کند، پشته خالی ، که با نماد خاصی مانند Λ یا "()" مشخص شده است. یا یک bottomعملیات () تعریف کنید که هیچ آرگومان نمی گیرد و این حالت پشته خاص را برمی گرداند. توجه داشته باشید که بدیهیات دلالت بر آن دارند

  • push(Λ, x ) ≠ Λ.

در تعریفی به سبک عملکردی از پشته، نیازی به emptyگزاره نیست: در عوض، می‌توان خالی بودن پشته را با آزمایش اینکه آیا برابر Λ است یا خیر، آزمایش کرد.

توجه داشته باشید که این بدیهیات اثر top( s ) یا pop( s ) را تعریف نمی کنند، مگر اینکه s یک حالت پشته ای باشد که توسط a برگردانده شده pushاست. از آنجایی pushکه پشته را خالی می‌گذارد، این دو عملیات زمانی که s = Λ تعریف نشده‌اند (از این رو نامعتبر هستند). از سوی دیگر، بدیهیات (و فقدان عوارض جانبی) دلالت دارند که push( s ، x ) = push( t ، y ) اگر و فقط اگر x = y و s = t باشد.

مانند برخی دیگر از شاخه‌های ریاضیات، معمولاً فرض می‌شود که حالت‌های پشته فقط آنهایی هستند که وجود آنها از بدیهیات در تعداد محدودی از مراحل اثبات می‌شود. در مثال پشته انتزاعی بالا، این قانون به این معنی است که هر پشته یک دنباله محدود از مقادیر است که پس از تعداد محدودی از pops تبدیل به پشته خالی (Λ) می شود. بدیهیات بالا به خودی خود وجود پشته های نامتناهی (که می توانند popبرای همیشه ویرایش شوند و هر بار حالت متفاوتی را ایجاد می کنند) یا پشته های دایره ای (که پس از تعداد pops محدود به همان حالت باز می گردند) را رد نمی کند. به طور خاص، آنها حالت هایی را استثنا نمی کنند که ( s ) = s یا ( s ،poppushx ) = s برای برخی از x . با این حال، از آنجایی که نمی توان چنین حالت های پشته ای را با عملیات داده شده بدست آورد، فرض می شود که "وجود ندارند".

آیا شامل پیچیدگی

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

دلیل معرفی مفهوم انواع داده های انتزاعی اجازه دادن به ماژول های نرم افزاری قابل تعویض بود. شما نمی توانید ماژول های قابل تعویض داشته باشید مگر اینکه این ماژول ها رفتار پیچیدگی مشابهی داشته باشند. اگر من یک ماژول را با ماژول دیگری با همان رفتار عملکردی اما با پیچیدگی های متفاوت جایگزین کنم، کاربر این کد به طرز ناخوشایندی شگفت زده می شود. من می‌توانم هر چیزی را که در مورد انتزاع داده‌ها دوست دارم به او بگویم، و او هنوز نمی‌خواهد از کد استفاده کند. اظهارات پیچیدگی باید بخشی از رابط باشد.

-  الکساندر استپانوف [6]

مزایای تایپ داده های انتزاعی

کپسولاسیون

Abstraction این نوید را می دهد که هر پیاده سازی ADT دارای ویژگی ها و توانایی های خاصی است. دانستن اینها تنها چیزی است که برای استفاده از یک شی ADT لازم است.

بومی سازی تغییرات

اگر اجرای ADT تغییر کند، کدی که از یک شی ADT استفاده می کند، نیازی به ویرایش نخواهد داشت. از آنجایی که هرگونه تغییر در پیاده‌سازی باید همچنان با اینترفیس مطابقت داشته باشد، و از آنجایی که کد با استفاده از یک شی ADT ممکن است فقط به ویژگی‌ها و توانایی‌های مشخص‌شده در اینترفیس اشاره داشته باشد، ممکن است تغییراتی در پیاده‌سازی بدون نیاز به تغییر در کد در جایی که ADT استفاده می‌شود، ایجاد شود. .

انعطاف پذیری

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

عملیات معمولی

برخی از عملیات که اغلب برای ADT ها (احتمالاً تحت نام های دیگر) مشخص می شوند، هستند

  • compare( s , t )، که آزمایش می کند که آیا حالت های دو نمونه به نوعی معادل هستند یا خیر.
  • hash( s )، که برخی از تابع هش استاندارد را از حالت نمونه محاسبه می کند.
  • print( s ) یا show( s )، که نمایشی قابل خواندن برای انسان از حالت نمونه ایجاد می کند.

در تعاریف ADT به سبک امری، غالباً نیز می‌توان یافت

  • create()، که نمونه جدیدی از ADT را به دست می دهد.
  • initialize( s )، که یک نمونه جدید ایجاد شده را برای عملیات بیشتر آماده می کند ، یا آن را به حالت اولیه بازنشانی می کند.
  • copy( s , t )، که نمونه s را در حالتی معادل t قرار می دهد .
  • clone( t )، که screate()، copy( s ، t )، را انجام می دهد و s را برمی گرداند .
  • free( s ) یا destroy( s )، که حافظه و سایر منابع استفاده شده توسط s را بازیابی می کند.

این freeعملیات معمولاً مرتبط یا معنی دار نیست، زیرا ADT ها موجودیت های نظری هستند که از "حافظه" استفاده نمی کنند. با این حال، زمانی که نیاز به تجزیه و تحلیل ذخیره سازی مورد استفاده توسط الگوریتمی که از ADT استفاده می کند، ممکن است ضروری باشد. در آن صورت، نیاز به بدیهیات اضافی است که مشخص کند هر نمونه ADT چه مقدار حافظه استفاده می کند، به عنوان تابعی از حالت خود، و چه مقدار از آن توسط free.

مثالها

برخی از ADT های متداول که در کاربردهای مختلف مفید بوده اند، هستند

هر یک از این ADT ها ممکن است به روش ها و انواع مختلفی تعریف شوند، نه لزوما معادل. به عنوان مثال، یک پشته انتزاعی ممکن است countعملیاتی داشته باشد یا نداشته باشد که نشان می دهد چند آیتم فشار داده شده اند و هنوز ظاهر نشده اند. این انتخاب نه تنها برای مشتریان خود بلکه برای اجرا نیز تفاوت ایجاد می کند.

نوع داده های گرافیکی انتزاعی

توسعه ADT برای گرافیک کامپیوتری در سال 1979 پیشنهاد شد: [7] یک نوع داده گرافیکی انتزاعی (AGDT). توسط Nadia Magnenat Thalmann و Daniel Thalmann معرفی شد. AGDT ها مزایای ADT ها را با امکاناتی برای ساخت اشیاء گرافیکی به روشی ساختاریافته فراهم می کنند.

پیاده سازی

پیاده سازی ADT به معنای ارائه یک رویه یا تابع برای هر عملیات انتزاعی است. نمونه های ADT توسط برخی از ساختار داده های انضمامی نشان داده می شوند که طبق مشخصات ADT توسط آن رویه ها دستکاری می شوند.

معمولاً راه های زیادی برای پیاده سازی ADT یکسان با استفاده از چندین ساختار داده بتنی مختلف وجود دارد. بنابراین، برای مثال، یک پشته انتزاعی را می توان توسط یک لیست پیوندی یا توسط یک آرایه پیاده سازی کرد .

به منظور جلوگیری از وابستگی کلاینت‌ها به پیاده‌سازی، یک ADT اغلب به‌عنوان یک نوع داده غیرشفاف در یک یا چند ماژول بسته‌بندی می‌شود که رابط آن فقط شامل امضا (تعداد و انواع پارامترها و نتایج) عملیات است. سپس اجرای ماژول - یعنی بدنه رویه ها و ساختار داده بتن مورد استفاده - می تواند از اکثر مشتریان ماژول پنهان شود. این امکان تغییر پیاده سازی را بدون تأثیرگذاری بر مشتریان فراهم می کند. اگر پیاده سازی در معرض دید قرار گیرد، در عوض به عنوان یک نوع داده شفاف شناخته می شود.

هنگام پیاده‌سازی یک ADT، هر نمونه (در تعاریف سبک امری) یا هر حالت (در تعاریف سبک عملکردی) معمولاً توسط دسته‌ای نشان داده می‌شود . [8]

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

مثال: اجرای پشته انتزاعی

به عنوان مثال، در اینجا پیاده سازی پشته انتزاعی بالا در زبان برنامه نویسی C است .

رابط به سبک امری

یک رابط به سبک امری ممکن است:

typedef struct stack_Rep stack_Rep ; // type: نمایش نمونه پشته (رکورد مات) typedef stack_Rep * stack_T ; // type: handle به یک نمونه پشته (اشاره گر مات) typedef void * stack_Item ; // نوع: مقدار ذخیره شده در نمونه پشته (آدرس دلخواه)          
                 
                   

stack_T stack_create ( void ); // یک نمونه پشته خالی جدید void stack_push ایجاد می کند ( stack_T s , stack_Item x ); // یک آیتم را در بالای پشته اضافه می کند stack_Item stack_pop ( stack_T s ); // آیتم بالایی را از پشته حذف می کند و آن را برمی گرداند bool stack_empty ( stack_T s ); // خالی بودن پشته را بررسی می کند                
     
            
                

این رابط را می توان به روش زیر استفاده کرد:

#include <stack.h>           // شامل رابط پشته است 

stack_T s = stack_create (); // یک نمونه پشته خالی جدید ایجاد می کند int x = 17 ;    
   
stack_push ( s , & x ); // آدرس x را در بالای پشته void اضافه می کند * y = stack_pop ( s ); // آدرس x را از پشته حذف می کند و اگر ( stack_empty ( s )) { } // اگر پشته خالی باشد کاری انجام دهد آن را برمی گرداند           
        
        

این رابط را می توان به روش های مختلفی پیاده سازی کرد. پیاده سازی ممکن است به طور دلخواه ناکارآمد باشد، زیرا تعریف رسمی ADT، در بالا، مشخص نمی کند که پشته چقدر فضای ممکن است استفاده کند، و همچنین مدت زمان هر عملیات را مشخص نمی کند. همچنین مشخص نمی کند که آیا وضعیت پشته s پس از فراخوانی xpop( s ) همچنان وجود دارد یا خیر .

در عمل، تعریف رسمی باید مشخص کند که فضا متناسب با تعداد مواردی است که فشار داده شده و هنوز باز نشده است. و اینکه هر یک از عملیات فوق باید مستقل از آن تعداد در مدت زمان ثابتی به پایان برسد. برای مطابقت با این مشخصات اضافی، پیاده سازی می تواند از یک لیست پیوندی، یا یک آرایه (با تغییر اندازه پویا) همراه با دو عدد صحیح (تعداد آیتم و اندازه آرایه) استفاده کند.

رابط کاربری به سبک

تعاریف ADT به سبک عملکردی برای زبان های برنامه نویسی تابعی مناسب تر است و بالعکس. با این حال، می توان یک رابط کاربری به سبک عملکردی را حتی در یک زبان امری مانند C ارائه کرد. به عنوان مثال:

typedef struct stack_Rep stack_Rep ; // نوع: نمایش وضعیت پشته (رکورد مات) typedef stack_Rep * stack_T ; // type: دسته به حالت پشته (اشاره گر مات) typedef void * stack_Item ; // نوع: مقدار یک حالت پشته (آدرس دلخواه)             
                    
                      

stack_T stack_empty ( void ); // وضعیت پشته خالی را برمی گرداند stack_T stack_push ( stack_T s , stack_Item x ); // یک آیتم را در بالای حالت پشته اضافه می کند و وضعیت پشته حاصل را برمی گرداند stack_T stack_pop ( stack_T s ); // آیتم بالایی را از حالت پشته حذف می کند و وضعیت پشته حاصل را برمی گرداند stack_Item stack_top ( stack_T s ); // آیتم بالای حالت پشته را برمی گرداند                    
     
                  
               

کتابخانه های ADT

بسیاری از زبان‌های برنامه‌نویسی مدرن، مانند C++ و جاوا، دارای کتابخانه‌های استانداردی هستند که چندین ADT رایج مانند موارد ذکر شده در بالا را پیاده‌سازی می‌کنند.

انواع داده های انتزاعی داخلی

مشخصات برخی از زبان‌های برنامه‌نویسی عمداً در مورد نمایش برخی از انواع داده‌های داخلی مبهم است و تنها عملیاتی را که می‌توان روی آنها انجام داد، تعریف می‌کند. بنابراین، آن انواع را می توان به عنوان "ADT های داخلی" مشاهده کرد. به عنوان مثال، آرایه‌ها در بسیاری از زبان‌های اسکریپت‌نویسی، مانند Awk ، Lua ، و Perl هستند که می‌توانند به عنوان پیاده‌سازی فهرست انتزاعی در نظر گرفته شوند.

همچنین مشاهده کنید

یادداشت ها

  1. ^ با توصیف اعداد صحیح در جبر انتزاعی مقایسه کنید.

نقل قول ها

  1. ^ دیل و واکر 1996 ، ص. 3.
  2. ^ دیل و واکر 1996 ، ص. 4.
  3. Liskov & Zilles 1974 .
  4. رودولف لیدل (2004). جبر انتزاعی . اسپرینگر. شابک 978-81-8128-149-4.، فصل 7، بخش 40.
  5. "برنامه نویسی شی گرا چیست؟" . استخدام | Upwork . 05/05/2015 . بازیابی شده در 2016-10-28 .
  6. استیونز، آل (مارس 1995). "مصاحبه های آل استیونز با الکس استپانوف" . مجله دکتر داب . بازبینی شده در 31 ژانویه 2015 .
  7. D. Thalmann، N. Magnenat Thalmann (1979). طراحی و پیاده سازی انواع داده های گرافیکی انتزاعی . IEEE. doi : 10.1109/CMPSAC.1979.762551 .، Proc. سومین کنفرانس بین المللی نرم افزار و برنامه های کاربردی کامپیوتر (COMPSAC'79), IEEE, Chicago, USA, pp.519-524
  8. رابرت سجویک (1998). الگوریتم ها در C ادیسون/وسلی. شابک 978-0-201-31452-6.، تعریف 4.4.

منابع

  • لیسکوف، باربارا ؛ زیلس، استفان (1974). "برنامه نویسی با انواع داده های انتزاعی". مجموعه مقالات سمپوزیوم ACM SIGPLAN در مورد زبان های سطح بسیار بالا . اطلاعیه های SIGPLAN. جلد 9. صص 50-59. CiteSeerX  10.1.1.136.3043 . doi : 10.1145/800233.807045 .
  • دیل، نل؛ واکر، هنری ام (1996). انواع داده های چکیده: مشخصات، پیاده سازی ها و کاربردها . یادگیری جونز و بارتلت شابک 978-0-66940000-7.

ادامه مطلب

پیوندهای خارجی