نوع داده انتزاعی "فهرست". نوع داده انتزاعی کلیات داده چکیده

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

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

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

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;);

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

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

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

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

حقوق دسترسی

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

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

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

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

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

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

1
2
3
4
5
6
7
8

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

توسعه مدل های انتزاعی برای داده ها و روش های پردازش این داده ها می باشد جزء ضروریدر فرآیند حل مشکلات با استفاده از کامپیوتر. نمونه هایی از این را هم در سطح پایین در برنامه نویسی روزمره می بینیم (مثلاً هنگام استفاده از آرایه ها و لیست های پیوندی که در آن بحث می شود) و هم در سطح بالا هنگام حل. وظایف کاربردی(مانند حل مشکل اتصال با استفاده از جنگل جستجوی پیوستن در «مقدمه»). این سخنرانی انواع داده های انتزاعی (نوع داده انتزاعی، از این پس 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 یک برنامه مشتری است که با این نوع داده کار می کند. این دو برنامه محاسباتی مشابه برنامه های 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 = 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)، ساختارها همچنین می توانند توابعی مرتبط با آنها داشته باشند. تفاوت اصلی بین کلاس ها و ساختارها مربوط به دسترسی به اطلاعات است که با کلمات کلیدی مشخص می شود.

روز بخیر، habravchane!

پست زیر خلاصه ای از افکار من در مورد ماهیت کلاس ها و 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 برای ارتقای کیفیت کار و توسعه نرم افزار نوشتم.

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

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

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

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

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

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

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

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

نمونه های ADT

همچنین ببینید

پیوندها

• Lapshin V. A. انواع داده های انتزاعی در برنامه نویسی

بنیاد ویکی مدیا 2010 .

ببینید «نوع داده انتزاعی» در فرهنگ‌های دیگر چیست:

نوع داده انتزاعی- یک نوع داده (کلاس انتزاعی) که با برشمردن روش ها و ویژگی های آن بدون ایجاد پیاده سازی مشخص از آنها تعریف می شود. موضوعات فناوری اطلاعات به طور کلی EN Abstract Data TypeADT ... کتابچه راهنمای مترجم فنی

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

عدد صحیح، نوع داده عدد صحیح (English Integer)، در علوم کامپیوتر، یکی از ساده ترین و رایج ترین انواع داده در زبان های برنامه نویسی است. برای نمایش اعداد صحیح استفاده می شود. مجموعه اعداد از این نوع ... ... ویکی پدیا است

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

برخی از زبان های برنامه نویسی یک نوع داده خاص برای اعداد مختلط ارائه می دهند. وجود یک نوع داخلی ذخیره مقادیر پیچیده و محاسبات روی آنها را ساده می کند. محتویات 1 حساب بیش از مختلط 2 پشتیبانی در زبان های ... ویکی پدیا

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

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

یک صفت یک نوع انتزاعی در علوم کامپیوتر است که به عنوان "یک مدل مفهومی ساده برای ساختار برنامه های شی گرا" استفاده می شود. صفات مانند میکسین هستند، اما می توانند شامل تعاریف متد کلاس باشند. ... ... ویکی پدیا

درخت دودویی یک مثال ساده از یک ساختار داده متصل منشعب است. ساختار داده (ساختار داده انگلیسی) یک واحد نرم افزاری است که امکان ذخیره سازی ... ویکی پدیا

- (نوع بالا) در تئوری نوع، اغلب به سادگی به عنوان یک نماد بالا یا "ثابت" (⊤) نشان داده می شود، یک نوع جهانی، یعنی نوعی که شامل هر شی ممکن در سیستم نوع مورد نظر است. از بالاترین نوع گاهی به عنوان ... ... ویکی پدیا یاد می شود