یک نوع انتزاعی اعلام شده در یک ماژول تعاریف. اپراتورهای ADT "Set Union"

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

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

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

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

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

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

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

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

1. لیست را خالی کنید.

2. اولین عنصر لیست را انتخاب کنید و در صورت خالی بودن لیست، مقدار را برگردانید خالی.

3. عنصر بعدی لیست را انتخاب کنید و مقدار را برگردانید خالی،اگر عنصر بعدینه

4. یک عدد صحیح را در لیست قرار دهید.

این امکان وجود دارد که از ساختارهای داده مختلفی استفاده کنید که با آنها بتوانید اقدامات توصیف شده را به طور موثر انجام دهید. (ما در مبحث 2 به طور مفصل درباره ساختارهای داده بحث خواهیم کرد.) اگر در لیست 1.3 عملگرهای مربوطه را با عبارات جایگزین کنیم.

MAKENULL(newcJr)؛

w:= FIRST(newcJr);

w:= NEXT(newcfr);

INSERT(v, newclr);

سپس یکی از جنبه های اصلی (و مزایای) انواع داده های انتزاعی روشن خواهد شد. شما می توانید یک نوع داده را به هر طریقی پیاده سازی کنید و برنامه هایی که از اشیایی از این نوع استفاده می کنند به نحوه پیاده سازی نوع بستگی ندارند - رویه هایی که عملگرهای این نوع داده را پیاده سازی می کنند مسئول این هستند.

بازگشت به نوع انتزاعی داده های GRAPH(گراف). اشیاء از این نوع به عملگرهایی نیاز دارند که اقدامات زیر را انجام دهند.

1. اولین راس بدون رنگ را انتخاب کنید.

2. بررسی کنید که آیا یک لبه بین دو راس وجود دارد یا خیر.

3. قسمت بالایی را با یک رنگ مشخص کنید.

4. راس پر نشده بعدی را انتخاب کنید.

بدیهی است که عملگرهای دیگر، مانند درج رئوس و یال ها در یک نمودار یا علامت گذاری تمام رئوس یک گراف به عنوان پر نشده، خارج از محدوده رویه حریصانه باقی می مانند. ساختارهای داده مختلفی که از این نوع داده پشتیبانی می کنند در مبحث 6 و 7 پوشش داده خواهند شد.

لازم به ذکر است که تعداد عملگرهای اعمال شده برای اشیاء این مدل ریاضی محدود نیست. هر مجموعه ای از عبارات یک ADT جداگانه تعریف می کند. در اینجا نمونه هایی از عملگرهایی هستند که می توان برای نوع داده انتزاعی SET (Set) تعریف کرد.

1. MAKENULL(A)، این رویه مجموعه A را یک مجموعه خالی می کند.

2. اتحاد (A، B، C). این رویه دو آرگومان «ورودی» را می گیرد، مجموعه های A و B، و اتحاد این مجموعه ها را به آرگومان «خروجی» خود، مجموعه C اختصاص می دهد.

3. SIZE (A). این تابع دارای یک آرگومان مجموعه ای A است و یک شی از نوع عدد صحیح برابر با تعداد عناصر مجموعه A برمی گرداند. اصطلاح اجرای ADT به موارد زیر دلالت دارد: ترجمه به زبان برنامه نویسی عبارات اعلان هایی که متغیرهای این نوع داده انتزاعی را تعریف می کنند، به اضافه رویه ها. برای هر دستوری که روی اشیاء ADT انجام می شود. اجرا بستگی دارد ساختارهای داده،نماینده ATD هر ساختار داده بر اساس انواع داده های اصلی زبان برنامه نویسی مورد استفاده، با استفاده از ابزارهای ساختار داده موجود در این زبان ساخته شده است. ساختارهای آرایه و رکورد دو ابزار مهم برای ساختاردهی داده ها هستند که در پاسکال امکان پذیر است. به عنوان مثال، یکی از پیاده سازی های ممکنمتغیر S از نوع SET می تواند یک آرایه حاوی عناصر مجموعه باشد اس.

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

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

یک نوع داده مجموعه ای از اشیاء با ویژگی های مشابه را توصیف می کند. همه زبان های برنامه نویسی سنتی از مجموعه ای از انواع داده های اصلی (واقعی، عدد صحیح، رشته ای، کاراکتر) استفاده می کنند. انواع داده های پایه تابع مجموعه ای از عملیات از پیش تعریف شده هستند. به عنوان مثال، عدد صحیح نوع داده پایه به شما امکان می دهد عملیات هایی مانند جمع، تفریق، ضرب و تقسیم را انجام دهید.

زبان های برنامه نویسی سنتی شامل سازنده های نوع هستند که رایج ترین آنها سازنده رکورد است. به عنوان مثال، برای رکوردی از نوع CUSTOMER، می توانید فیلدهای داده را تعریف کنید. ورودی CUSTOMER خواهد بود نوع جدیدساختار داده که اطلاعات مربوط به مشتری را ذخیره می کند، می توانید با مراجعه به نام فیلدها به طور مستقیم به این ساختار داده دسترسی داشته باشید. می توانید عملیاتی مانند WRITE، READ، DELETE، UPDATE را روی یک رکورد انجام دهید. شما نمی توانید عملیات جدیدی را برای انواع داده های پایه تعریف کنید.

مانند انواع داده های پایه، انواع داده های انتزاعی (ATD) بسیاری از اشیاء مشابه را توصیف می کنند. تفاوت هایی بین ATD و نوع سنتیداده ها:

· عملیات تحت ATD توسط کاربر تعریف می شود.

· ATD ها اجازه دسترسی مستقیم به نمایش داده های داخلی و پیاده سازی روش را نمی دهند.

در برخی از سیستم‌های OO (به عنوان مثال، اسمال‌تاک)، انواع داده‌های پایه به صورت انتزاعی پیاده‌سازی می‌شوند.

برای ایجاد یک نوع داده انتزاعی، باید ارائه دهید:

نام نوع؛

نمایش داده ها یا متغیرهای نمونه یک شی متعلق به ATD. هر متغیر نمونه دارای یک نوع داده است که می تواند یکی باشد نوع پایه، یا ATD دیگر؛

· عملیات و محدودیت های ATD با استفاده از روش ها اجرا می شوند.

تعریف ATD تعریف کلاس را بازسازی می کند. در برخی از سیستم‌های OO، از کلمه کلیدی type برای تمایز بین کلاس‌ها و انواع هنگام ارجاع به ساختارهای داده و متدهای یک کلاس و هنگام ارجاع به مجموعه‌ای از نمونه‌های شی استفاده می‌شود. کلمه کلیدیکلاس نوع (نوع) یک مفهوم ثابت تر است و کلاس عمدتاً به زمان اجرا مربوط می شود. تفاوت بین کلاس OO و نوع OO را می توان با یک مثال نشان داد. فرض کنید یک قالب برای یک سازنده وجود دارد. این الگو با توضیحاتی در مورد ساختار آن و همچنین دستورالعمل استفاده از آن همراه است. این الگو تعریف نوع است. مجموعه ای از محصولات واقعی ساخته شده با استفاده از یک الگو، که هر کدام دارای یک شماره (یا OID) منحصر به فرد هستند، یک کلاس (کلاس) را تشکیل می دهند.

ATD، همراه با وراثت، به شما امکان ایجاد اشیاء پیچیده را می دهد. یک شی پیچیده از ترکیب اشیاء دیگر که در روابط پیچیده با یکدیگر هستند تشکیل می شود. مثال شی پیچیدهرا می توان در سیستم های امنیتی که استفاده می کنند پیدا کرد انواع متفاوتداده ها:

1. داده های استاندارد (جدولی) در مورد کارمند (نام کامل، شماره برگه و غیره)؛

2. بیت مپ برای ذخیره عکس کارمندان.

توانایی کار با چنین محیط داده پیچیده ای با سهولت نسبی، ارزش سیستم های OO را افزایش می دهد بازار مدرنپایگاه های داده

یک نوع داده انتزاعی معمولاً به نوع داده ای گفته می شود که به صراحت در یک زبان برنامه نویسی در دسترس نیست؛ از این نظر، این مفهوم نسبی است - نوع داده ای که در یک زبان برنامه نویسی وجود ندارد ممکن است در زبان برنامه نویسی دیگر وجود داشته باشد.

نوع داده انتزاعی (ATD) بدون توجه به نحوه پیاده سازی آن تعریف می شود:

زیاد مقادیر ممکناز این نوع

و مجموعه ای از عملیات بر روی مقادیر از این نوع.

استفاده از ADT ممکن است به مرحله توسعه محدود شود نرم افزار، اما برای استفاده صریح از آن در برنامه، پیاده سازی آن بر اساس انواع داده های موجود (و قبلاً اجرا شده) در زبان برنامه نویسی ضروری است:

راهی برای نمایش مقادیر از آن نوع،

و اجرای عملیات بر روی مقادیری از آن نوع.

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

در مفهوم ATD، مفاهیم رابط ، در معرض کاربر و پیاده سازی از او پنهان شده است. نقش ویژه این مفاهیم در مفهوم ADT به این گزاره اساسی مربوط می شود که مفهوم ADT مستقل از روش اجرای آن است.

"زبان های برنامه نویسی کاربردی" مدرن معمولاً از عملیات ساخت و ساز از پیش تعریف شده برای ساختن یک ADT استفاده می کنند. کلاس ، که به توسعه دهنده-برنامه نویس نه تنها ابزار گروه بندی داده ها و عملیات (با این داده ها) را در یک کل واحد، بلکه ابزارهای کپسوله سازی، وراثت و چندشکلی را برای کنترل نحوه ساخت و دسترسی به چنین داده هایی می دهد. توجه داشته باشید که کلاس یک پیاده سازی ممکن از ADT را توصیف می کند، نگاشت کلاس به ADT با تابع انتزاعی بیان می شود، اما رابطه معکوس معمولاً کاربردی نیست، ممکن است چندین پیاده سازی از یک ADT وجود داشته باشد.

در تحقیق بر روی انواع داده های انتزاعی، نقش مهم مفهوم " پارامترسازی نوع ". در واقع، برای مثال، ADT "Stack" به نوع عناصر پشته بستگی ندارد، اما اجرای این ADT با اشاره به "عناصر از نوع مشابه" غیرممکن است. ابزارهای مربوطه برای ساخت انواع داده های پارامتری شده از همان ابتدا در زبان برنامه نویسی Ada گنجانده شد و در "زبان های برنامه نویسی عملی" مدرن چه ابزارهایی فقط از زمان توسعه کتابخانه STL ظاهر شده اند. امروزه مفهوم "برنامه نویسی عمومی" به دلیل گنجاندن آن در "زبان های برنامه نویسی عملی" جایگاه قابل توجهی را در برنامه نویسی عملی به خود اختصاص داده است. ابزارهای ساخت و ساز برای انواع داده های پارامتری شده (الگوها، قالب , عمومی) .

همه موارد فوق به این معنی است که از منظر روش شناختی و نظری، تعریف دقیق تری از مفهوم «نوع داده انتزاعی» مورد نیاز است. در تئوری، مفهوم "نوع داده انتزاعی" معمولاً به این صورت تعریف می شود سیستم جبری چند مرتبه ای (چند پایه). ، که در آن علاوه بر مجموعه مقادیر ممکن (حامل) و مجموعه عملیات روی چنین مقادیری، مفاهیم زیر برجسته شده است:

مرتب سازی و امضا - این مفاهیم امکان طبقه بندی عناصر حامل و عملیات با آنها را بر اساس انواع آنها (برای عملیات - بر اساس انواع آرگومان ها و مقدار بازگشتی آنها) ممکن می کند.

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

بر این اساس، می توان انواع داده های انتزاعی را از یک نقطه نظر منطقی- جبری کل نگر در نظر گرفت، از جمله سؤالاتی در مورد سازنده ها (نوع ها و مقادیر)، انتخابگرها و اصلاح کننده های ویژگی برای اشیاء از این نوع.

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

اما با این حال، ما بین این دو مفهوم تمایز قائل خواهیم شد، با توجه به:

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

ساختار داده ها نوعی طرح سازماندهی داده است و مدیریت آنها، که در صورت استفاده در موقعیت های خاص در حل مسائل خاص، مستلزم دقیق سازی مناسب است.

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

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

همه چيز سیستم های محاسباتیبر اساس سطوح انتزاع: خواص فیزیکی خاصی از سیلیکون و سایر مواد اجازه می دهد تا یک مدل انتزاعی از یک بیت را اتخاذ کنید که می تواند مقادیر باینری 0-1 را به خود بگیرد. سپس، یک مدل انتزاعی از ماشین بر روی ویژگی های دینامیکی مقادیر مجموعه خاصی از بیت ها ساخته می شود. علاوه بر این، بر اساس اصل عملکرد دستگاه تحت کنترل برنامه در زبان ماشینیک مدل انتزاعی از زبان برنامه نویسی ساخته شده است. و در نهایت یک مفهوم انتزاعی از یک الگوریتم ساخته می شود که به عنوان یک برنامه ++C پیاده سازی می شود. انواع داده‌های انتزاعی ادامه این فرآیند را امکان‌پذیر می‌سازد و مکانیسم‌های انتزاعی را برای وظایف محاسباتی خاص در سطحی بالاتر از آنچه توسط سیستم C ++ ارائه می‌شود، توسعه می‌دهد، مکانیسم‌های انتزاعی را توسعه می‌دهد برنامه های کاربردی خاصو مناسب برای حل مسائل در زمینه های کاربردی متعدد و همچنین برای ایجاد مکانیسم های انتزاعی برای بیشتر سطح بالاکه از این ساختارهای اساسی استفاده می کنند. انواع داده های انتزاعی مجموعه ای از بی نهایت قابل گسترش را در اختیار ما قرار می دهند ابزاربرای حل بیشتر و بیشتر مشکلات جدید.

از یک سو، استفاده از ساختارهای انتزاعی فرد را از نگرانی در مورد اجرای دقیق آنها رها می کند. از سوی دیگر، زمانی که کاراییبرنامه مهم است، شما باید هزینه های انجام عملیات اساسی را بدانید. ما از انتزاعات اساسی بسیاری استفاده می کنیم سخت افزارکامپیوتر و به عنوان مبنایی برای دستورالعمل های ماشین. پیاده سازی انتزاعات دیگر در نرم افزار؛ و از انتزاعات اضافی ارائه شده توسط نرم افزار سیستمی که قبلا نوشته شده است استفاده کنید. ساختارهای انتزاعی سطح بالا اغلب بر اساس موارد بیشتری هستند طرح های ساده. در همه سطوح، همان اصل اساسی اعمال می شود: شما باید بیشترین را پیدا کنید عملیات مهمدر برنامه ها و بیشتر ویژگی های مهمداده ها و سپس تعریف دقیق هر دو در سطح انتزاعی و توسعه مکانیسم های ملموس مؤثر برای اجرای آنها. در این سخنرانی به نمونه های زیادی از کاربرد این اصل خواهیم پرداخت.

توسعه سطح جدیدی از انتزاع مستلزم (1) تعریف اشیاء انتزاعی برای دستکاری و عملیاتی است که باید روی آنها انجام شود. (2) نشان دادن داده ها در برخی از ساختار داده و اجرای عملیات. (3) و (مهمتر از همه) برای اطمینان از اینکه این اشیا برای حل مسائل کاربردی مناسب هستند. این نکات برای انواع سادهداده ها، به طوری که مکانیسم های اساسی برای پشتیبانی از انواع داده ها، که در "ساختارهای داده اولیه" مورد بحث قرار گرفت، می تواند برای اهداف ما تطبیق داده شود. با این حال، زبان C++ ارائه می دهد گسترش مهممکانیسم سازه ها، کلاس (کلاس) نامیده می شود. کلاس ها در ایجاد سطوح انتزاع بسیار مفید هستند و بنابراین به عنوان ابزار اصلی مورد استفاده برای این منظور در ادامه کتاب تلقی می شوند.

تعریف 4.1.نوع داده انتزاعی (ATD) یک نوع داده (مجموعه ای از مقادیر و مجموعه ای از عملیات روی آن مقادیر) است که فقط از طریق یک رابط قابل دسترسی است. برنامه ای که از ADT استفاده می کند مشتری نامیده می شود و برنامه حاوی مشخصات این نوع داده پیاده سازی نامیده می شود.

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

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

به عنوان مثال، رابط نوع داده را برای نقاط (برنامه 3.3) از بخش 3.1 "ساختارهای داده اولیه" در نظر بگیرید. این واسط به صراحت اعلام می کند که نقاط به صورت ساختارهایی متشکل از یک جفت اعداد ممیز شناور نشان داده می شوند که با x و y نشان داده می شوند. این استفاده از انواع داده رایج است سیستم های بزرگنرم افزار: ما مجموعه ای از قراردادهای نمایش داده را توسعه می دهیم (و همچنین مجموعه ای از عملیات مرتبط را تعریف می کنیم) و این قوانین را از طریق یک رابط در دسترس قرار می دهیم تا بتوانند توسط برنامه های مشتری موجود در سیستم بزرگ. نوع داده تضمین می کند که تمام بخش های سیستم با نمایش ساختارهای داده زیربنایی در سراسر سیستم سازگار است. هر چقدر هم که این استراتژی خوب باشد، یک ایراد دارد: اگر نیاز به تغییر باشد ارائه داده ها، باید همه برنامه های کلاینت را تغییر دهید. برنامه 3.3 دوباره یک مثال ساده به ما می دهد: یکی از دلایل توسعه این نوع داده، راحتی برنامه های کلاینت است که با نقاط کار می کنند، و ما انتظار داریم که کلاینت ها در صورت لزوم به مختصات فردی یک نقطه دسترسی داشته باشند. اما ما نمی‌توانیم به یک نمایش داده متفاوت (مثلاً مختصات قطبی، یا مختصات سه بعدی، یا حتی انواع دیگر داده‌ها برای مختصات فردی) بدون تغییر همه برنامه‌های مشتری تغییر دهیم.

در مقابل، برنامه 4.1 شامل اجرای یک نوع داده انتزاعی است که با نوع داده در برنامه 3.3 مطابقت دارد، اما از کلاس زبان C++ استفاده می کند که هم داده ها و هم عملیات مرتبط با آن را به طور همزمان تعریف می کند. برنامه 4.2 است برنامه مشتری A که با این نوع داده کار می کند. این دو برنامه همانند برنامه های 3.3 و 3.8 محاسبات را انجام می دهند. آنها تعدادی از ویژگی های اصلی کلاس ها را نشان می دهند که اکنون در نظر خواهیم گرفت.

وقتی تعریفی مانند int i در یک برنامه می نویسیم، به سیستم می گوییم که یک منطقه حافظه برای داده ها (آنبرد) رزرو کند. int را تایپ کنید، که با نام i قابل دسترسی است. زبان C++ عبارت شیء را برای چنین موجوداتی دارد. وقتی تعریفی مانند POINT p در برنامه ای نوشته می شود، می گویند که یک شی از کلاس POINT ایجاد می شود که می توان با نام p به آن اشاره کرد. در مثال ما، هر شی شامل دو عنصر داده به نام‌های x و y است. همانطور که در مورد ساختارها، آنها را می توان با نام هایی مانند p.y نام برد.

اعضای داده x و y اعضای داده کلاس نامیده می شوند. کلاس همچنین می تواند توابع عضوی را تعریف کند که عملیات مرتبط با این نوع داده را اجرا می کند. به عنوان مثال، کلاس تعریف شده در برنامه 4.1 دارای دو تابع عضو به نام های POINT و فاصله است.

برنامه های سرویس گیرنده، مانند برنامه 4.2، می توانند توابع عضو مرتبط با یک شی را با تعیین نام آنها به همان روشی که نام داده های موجود در ساختار ساختاری دارند، فراخوانی کنند. به عنوان مثال، عبارت p.distance(q) فاصله بین نقاط p و q را محاسبه می کند (همان فاصله باید با فراخوانی q.distance(p) برگردانده شود). تابع ()POINT، اولین تابع در برنامه 4.1، یک تابع عضو ویژه به نام سازنده است: این تابع همنام کلاس است و زمانی فراخوانی می شود که یک شی از آن کلاس باید ایجاد شود.

برنامه 4.1. اجرای کلاس POINT (نقطه)

این کلاس یک نوع داده را تعریف می کند که شامل مجموعه ای از مقادیر است که "جفت اعداد ممیز شناور" هستند (با فرض اینکه آنها به عنوان نقاط در صفحه دکارتی تفسیر شوند)، و همچنین دو تابع عضو تعریف شده برای همه نمونه های POINT. class: تابع POINT() که سازنده ای است که مختصات را با مقادیر تصادفی از 0 تا 1 مقداردهی اولیه می کند و یک تابع distance(POINT) که فاصله تا نقطه دیگر را محاسبه می کند. بازنمایی داده هاخصوصی است و فقط توابع اعضا می توانند به آن دسترسی داشته باشند یا آن را تغییر دهند. توابع عضو خود عمومی (عمومی) و در دسترس هر مشتری هستند. کد را می توان به عنوان مثال در فایلی به نام POINT .cxx ذخیره کرد.

#عبارتند از کلاس POINT ( خصوصی: float x, y؛ عمومی: POINT() (x = 1.0*rand()/RAND_MAX؛ y = 1.0*rand()/RAND_MAX؛ ) فاصله شناور (POINT a) (شناور dx = xa.x , dy = ya.y؛ بازگشت sqrt(dx*dx + dy*dy); ) );

برنامه 4.2. برنامه مشتری برای کلاس POINT (پیدا کردن نزدیکترین نقطه)

این نسخه از برنامه 3.8 یک کلاینت است که از POINT ADT تعریف شده در برنامه 4.3 استفاده می کند. عملیات جدیدآرایه ای از اشیاء POINT ایجاد می کند (با فراخوانی سازنده POINT() برای مقداردهی اولیه هر شی با مقادیر مختصات تصادفی). عبارت a[i].distance(a[j]) تابع عضو را روی شیء a[i] با آرگومان a[j] فراخوانی می‌کند.

#عبارتند از #عبارتند از #include "POINT.cxx" int main(int argc, char *argv) ( float d = atof(argv)؛ int i, cnt = 0, N = atoi(argv)؛ POINT *a = new POINT[N]; برای (i = 0; i< N; i++) for (int j = i+1; j < N; j++) if (a[i].distance(a[j]) < d) cnt+ + ; cout << cnt << " пар в радиусе " << d << endl; }

تعریف POINT p در برنامه مشتری منجر به تخصیص یک منطقه حافظه برای یک شی جدید و سپس (با استفاده از تابع POINT()) می شود که به هر یک از دو عنصر داده آن یک مقدار تصادفی در محدوده 0 تا 1 اختصاص می دهد.

این سبک از برنامه نویسی که گاهی برنامه نویسی شی گرا نامیده می شود، به طور کامل توسط ساختار کلاس C++ پشتیبانی می شود. یک کلاس را می توان به عنوان بسط مفهوم ساختار در نظر گرفت، که در آن نه تنها داده ها ترکیب می شوند، بلکه عملیات روی آن داده ها نیز تعریف می شوند. ممکن است اشیاء مختلف زیادی متعلق به یک کلاس وجود داشته باشد، اما همه آنها از این نظر شبیه هستند که اعضای داده آنها می توانند مجموعه ای از مقادیر یکسانی داشته باشند، و مجموعه عملیات یکسانی را می توان روی آن اعضای داده انجام داد - به طور کلی، آنها نمونه هایی از همان نوع داده در برنامه نویسی شی گرا، اشیا برای پردازش اعضای داده خود طراحی می شوند (در مقابل استفاده از توابع مستقل برای پردازش داده های ذخیره شده در اشیاء).

ما به مثال یک کلاس کوچک که در بالا توضیح داده شد نگاه می کنیم تا با ویژگی های اصلی کلاس ها آشنا شویم. بنابراین تا کامل شدن فاصله زیادی دارد. در کد واقعی برای کلاس نقطه، عملیات های بسیار بیشتری خواهیم داشت. به عنوان مثال، در برنامه 4.1، حتی عملیاتی وجود ندارد که به شما امکان می دهد مقادیر مختصات x و y را پیدا کنید. همانطور که خواهیم دید، افزودن این و سایر عملیات ها کار نسبتاً ساده ای است. در قسمت 5، نگاه دقیق تری به کلاس های نقاط و سایر انتزاعات هندسی مانند خطوط و چندضلعی ها خواهیم داشت.

در C++ (اما نه در C)، ساختارها همچنین می توانند توابعی مرتبط با آنها داشته باشند. تفاوت اصلی بین کلاس ها و ساختارها مربوط به دسترسی به اطلاعات است که با کلمات کلیدی مشخص می شود.

روز بخیر، habravchane!

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

معرفی

بیایید با این واقعیت شروع کنیم که به راحتی به تعریف ATD نزدیک می شویم. یک ADT در درجه اول یک نوع داده است که به این معنی است:
در دسترس بودن برخی عملیات های موجود بر روی عناصری از این نوع؛
و همچنین داده هایی که این عملیات بر روی آنها انجام می شود (محدوده مقادیر).

کلمه "انتزاعی" به چه معناست؟ اول از همه، مفهوم "انتزاعی" به معنای تمرکز بر یک چیز مهم است و در عین حال باید از جزئیات بی اهمیت، در حال حاضر، منحرف شویم. تعریف انتزاعی به خوبی در کتاب گریدی بوچ آمده است. این تعریف به نظر می رسد:

انتزاع عبارت است از انتخاب و دادن مجموعه ای از اشیاء با ویژگی های مشترک که مرزهای مفهومی آنها را مشخص می کند و آنها را از سایر انواع اشیاء متمایز می کند.
به عبارت دیگر، انتزاع به ما این امکان را می‌دهد که به داده‌های شی مورد نیاز خود «نور بتابانیم» و در عین حال داده‌هایی را که برای ما مهم نیستند، «مبهم» کنیم.

بنابراین، اگر مفاهیم «نوع داده» و «انتزاع» را با هم ادغام کنیم، چه اتفاقی خواهد افتاد؟ ما یک نوع داده دریافت خواهیم کرد که مجموعه ای از عملیات را به ما ارائه می دهد که رفتار اشیاء این نوع داده را ارائه می دهد، و این نوع داده نیز داده هایی را که این رفتار با آنها پیاده سازی شده است پنهان می کند. از اینجا به مفهوم ATD می رسیم:

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

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

مزایای ATD

استفاده از ADT مزایای زیادی دارد (همه مزایای توصیف شده را می توان در Code Perfect استیو مک کانل یافت):

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

• کاهش پیچیدگی
  با انتزاع از جزئیات پیاده سازی، به جای اینکه چگونه انجام می شود، روی رابط تمرکز می کنیم، یعنی آنچه که یک ADT می تواند انجام دهد. علاوه بر این، ADT به ما اجازه می دهد تا با ماهیت دنیای واقعی کار کنیم.

• محدودیت دامنه استفاده از داده ها.
  با استفاده از یک ADT، می‌توانیم مطمئن باشیم که داده‌هایی که ساختار داخلی یک ADT را نشان می‌دهند به بخش‌های دیگر کد بستگی ندارند. در این صورت، "استقلال" ADT محقق می شود.

• محتوای اطلاعاتی بالای رابط.
  ADT به شما امکان می دهد کل رابط را از نظر موجودیت های حوزه موضوعی نشان دهید، که، می بینید، خوانایی و آموزنده بودن رابط را افزایش می دهد.

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

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

شایان ذکر است که مفهوم ADT کاربرد گسترده ای در OOP پیدا کرده است، زیرا این مفهوم است که OOP را تکمیل می کند و به شما امکان می دهد پیچیدگی برنامه ها را در دنیای به سرعت در حال تغییر نیازمندی های نرم افزار کاهش دهید.

این مقاله را به منظور جلب توجه توسعه دهندگان به ATD برای ارتقای کیفیت کار و توسعه نرم افزار نوشتم.

منابع مورد استفاده:

استیو مک کانل - "کد کامل"؛
رابرت سدویک - الگوریتم‌ها در جاوا.