یک نوع انتزاعی اعلام شده در یک ماژول تعریف. نوع داده انتزاعی "درخت"

همه انواع داده های داخلی انتزاعی هستند، اگرچه به ندرت به آن ها گفته می شود.

مفهوم انتزاع

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

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

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

دلیل ایجاد انتزاع نوع داده و انتزاع فرآیند به عنوان یک اقدام متقابل در برابر پیچیدگی، راهی برای بزرگ کردن و/یا برنامه های پیچیدهقابل مدیریت تر

کپسوله سازی

تقسیم یک برنامه به محفظه های نحوی که حاوی گروه هایی از روال ها و داده های منطقی مرتبط هستند. این ظروف نحوی ماژول نامیده می شوند و فرآیند توسعه آنها مدولارسازی نامیده می شود.

کامپایل یک برنامه از مجموعه ای از زیر روال ها و داده ها، که هر کدام را می توان به طور جداگانه بدون کامپایل مجدد بقیه برنامه کامپایل کرد. به این مجموعه واحد کامپایل می گویند.

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

چکیده انواع داده های تعریف شده توسط کاربر

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

1) یک تعریف نوع، که به ماژول های برنامه اجازه می دهد تا متغیرهایی از این نوع را اعلام کنند، در حالی که یک نمایش واقعی از این متغیرها در حافظه ایجاد می کنند.

2) مجموعه ای از عملیات برای دستکاری اشیا از این نوع.

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

نمایش (تعریف نوع) و عملیات روی اشیاء از یک نوع معین در یک واحد نحوی موجود است؛ متغیرهای یک نوع معین را می توان در ماژول های دیگر ایجاد کرد.

نمایش اشیاء از این نوع پنهان است ماژول های نرم افزاریبا استفاده از این نوع، می توانید عملیاتی را روی اشیایی انجام دهید که مستقیماً در تعریف نوع ارائه شده اند.

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

مسائل توسعه را تایپ کنید

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

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

Smalltalk، C++ و Java به طور مستقیم از انواع داده های انتزاعی پشتیبانی می کنند.

انواع داده های انتزاعی در C++

زبان‌های Ada و Modula-2 کپسوله‌سازی را ارائه می‌کنند که می‌تواند برای مدل‌سازی انواع داده‌های انتزاعی استفاده شود، و C++ مفهوم کلاسی را معرفی می‌کند که مستقیماً از انواع داده‌های انتزاعی پشتیبانی می‌کند. در C++، کلاس ها نوع هستند، اما بسته های Ada و ماژول های Modula-2 نوع نیستند. بسته‌ها و ماژول‌ها وارد می‌شوند و به واحد برنامه واردکننده این امکان را می‌دهد تا متغیرهای هر نوع تعریف شده در بسته یا ماژول را اعلام کند. در یک برنامه ++C، متغیرها به عنوان موجودیت هایی اعلان می شوند که دارای نوع یک کلاس هستند. به این ترتیب، کلاس ها بیشتر شبیه انواع داخلی هستند تا بسته ها یا ماژول ها. یک واحد نرم افزاری که یک بسته را در Ada یا یک ماژول در Modula-2 می بیند، به هر نهاد عمومی به سادگی با نام آنها دسترسی دارد. یک واحد برنامه C++ که نمونه ای از یک کلاس را اعلام می کند، به هر نهاد عمومی در آن کلاس نیز دسترسی دارد، اما فقط از طریق نمونه ای از آن کلاس.

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

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

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

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

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

برخی از سیستم های شی گرا (مانند Smalltalk) انواع داده های پایه را به صورت انتزاعی پیاده سازی می کنند.

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

· اسم را تایپ کن؛

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

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

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

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

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

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

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

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

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

بیایید به اجرای مفهوم date با استفاده از struct برای تعریف یک نمایش تاریخ و مجموعه ای از توابع برای کار با متغیرهایی از این نوع نگاه کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#عبارتند از
تاریخ ساخت
{
ماه بین المللی; // ماه
روز بین المللی; // روز
سال بین المللی؛ // سال
};
void set_date (تاریخ* f، int d، int m، int y)
{
f->day = d;
f->month = m;
f->سال = y;
}
تاریخ چاپ باطل (تاریخ* f)
{
printf("%d.%d.%d" , f->day, f->month, f->year);
}
int main()
{
تاریخ امروز؛
set_date(&today, 2, 4, 2014);
چاپ_تاریخ (&امروز);
getchar();
بازگشت 0;
}

نتیجه اجرا

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#عبارتند از
تاریخ ساخت
{
ماه بین المللی; // ماه
روز بین المللی; // روز
سال بین المللی؛ // سال
تنظیم_تاریخ باطل (int d، int m، int y)
{
روز = d; ماه = m; سال = y;
}
void print_date(void);
};
void date::print_date(void)
{
printf("%d.%d.%d"، روز، ماه، سال);
}
int main()
{
تاریخ امروز؛
Today.set_date(2, 4, 2014);
Today.print_date();
getchar();
بازگشت 0;
}

توابع اعضا و اعضای داده

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

توابع عضو را می توان به دو صورت تعریف کرد:

• توصیف تابع به طور مستقیم هنگام توصیف ساختار؛
• توصیف یک تابع خارج از ساختار

توابع عضوی که در داخل یک ساختار تعریف شده اند به طور ضمنی خطی شده اند ( ). به عنوان یک قاعده، فقط توابع عضو کوتاه و پرکاربرد باید در داخل ساختار تعریف شوند:

مجموعه خالی (int m, int d, int y) (ماه = m؛ روز = d؛ سال = y;);

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

• نوع- نوع بازگشت تابع عضو
• ATD- نام یک نوع داده انتزاعی (نام یک ساختار یا کلاس)
• نام- نام تابع عضو

void date::print_date(void)
( printf("%d.%d.%d"، روز، ماه، سال)؛)

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

توابع اعضای یک ساختار می توانند چند شکلی باشند، یعنی بارگذاری بیش از حد.

حقوق دسترسی

مفهوم ساختار در C++ (در مقابل C) به اعضای یک ساختار اجازه می دهد تا عمومی، خصوصی یا محافظت شده باشند:

• عمومی - عمومی;
• خصوصی - خصوصی
• محافظت شده - محافظت شده.

استفاده کلمه کلیدیمحافظت شده با مفهوم ارث مرتبط است.

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

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

بیایید ساختار تاریخ را تغییر دهیم تا نمایش داده ها پنهان شود (انکپسولاسیون داده):

1
2
3
4
5
6
7
8

تاریخ ساخت
{
خصوصی :
بین ماه، روز، سال؛
عمومی:
مجموعه خالی (int، int، int);
void print();
};

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

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

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

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

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

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

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

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

در مقابل، برنامه 4.1 شامل اجرای یک نوع داده انتزاعی مربوط به نوع داده در برنامه 3.3 است، اما با استفاده از یک کلاس زبان C++ که بلافاصله هم داده ها و هم عملیات مرتبط با آن را تعریف می کند. برنامه 4.2 است برنامه مشتری، کار با این نوع داده. این دو برنامه محاسباتی مشابه برنامه های 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: تابع POINT() که سازنده ای است که مختصات را با مقادیر تصادفی بین 0 و 1 مقداردهی اولیه می کند و فاصله تابع (POINT) که فاصله تا نقطه دیگر را محاسبه می کند. ارائه داده هاخصوصی است و فقط توسط توابع عضو قابل دسترسی یا تغییر است. توابع عضو خود عمومی هستند و برای هر مشتری قابل دسترسی هستند. کد را می توان به عنوان مثال در فایلی به نام POINT.cxx ذخیره کرد.

#عبارتند از کلاس POINT ( خصوصی: float x, y؛ عمومی: POINT() (x = 1.0*rand()/RAND_MAX؛ y = 1.0*rand()/RAND_MAX؛ ) فاصله شناور (POINT a) (شناور dx = x-a.x , dy = y-a.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)، ساختارها همچنین می توانند توابعی مرتبط با آنها داشته باشند. تفاوت اصلی بین کلاس ها و ساختارها مربوط به دسترسی به اطلاعات است که با کلمات کلیدی مشخص می شود

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‌ها را اعلام کرد، دشوار است. برای اطلاعات بیشتر در مورد این گونه زبان های برنامه نویسی، به یادداشت های کتابشناختی در انتهای مبحث مراجعه کنید.