مفهوم نوع داده انتزاعی کلاس های چکیده و اعضای کلاس

زبان 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;
}
void print_date (تاریخ*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();
};

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

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

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

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

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

نمونه های ADT

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

پیوندها

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1. توالی.

دنباله نامتناهی (متناهی) به طور رسمی به عنوان تابعی تعریف می شود که دامنه آن مجموعه اعداد صحیح مثبت است: f(i)= , . در بسیاری از موارد ایندکس کردن یک دنباله از ابتدا راحت تر است. سپس دامنه / مجموعه ای از اعداد صحیح غیر منفی خواهد بود. به طور مشابه، یک دنباله یا لیست محدود را به عنوان تابعی تعریف می کنیم که دامنه آن مجموعه (1، 2، ...، ) است.

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

¨ مجموعه مقادیر ممکن یک دنباله محدود از عناصر از همان نوع است.

¨ مجموعه عملیات:

§ درج کنیدعنصر به ترتیب

§ حذفعنصر از دنباله

§ نگاه کنتابعی است که مقدار یک عنصر از یک دنباله را برمی گرداند.

انواع این نوع ADT در نحوه دسترسی به عناصر یک دنباله و محدودیت در محل درج و حذف عناصر متفاوت است.

برای این نوع ATD پشته , صف و دسامبر (deque از صف دوبل پایان ) مشخصه خواندن مخرب، زیرا دسترسی به عناصر (برای هر سه عملیات) به یکی از انتهای دنباله محدود می شود و عملیات "نگاه به عنصر دیگر" را می توان تنها با حذف عناصری که با این کار تداخل دارند انجام داد. برای ATD وکتور (آرایه، وکتور)، فایل (فایل) و لیست خطی محدودیت های دسترسی فراهم می کند خواندن غیر مخرببنابراین از اهمیت ویژه ای برخوردار است ( مشتق) عملیات جستجوی توالی.

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

مفاهیم "تعداد" و "موقعیت" یک عنصر به هم نزدیک هستند، اما ممکن است مطابقت نداشته باشند:

§ عددعدد ترتیبی واقعی عنصر در دنباله است. اما تعداد ترتیبی عنصر در نتیجه درج و حذف عناصر قبلی تغییر می کند، این امر باعث ایجاد مشکلاتی در شناسایی عناصر دنباله می شود.

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

برای Sequence ADT، عملیات اضافی فرم مورد توجه است: دو دنباله را به هم متصل کنید، به دو دنباله جدا کنید. به عنوان مثال، در ATD رشته این نوع عملیات در واقع اصلی ترین است.

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

2.2. تنظیم.

¨ مجموعه مقادیر ممکن مجموعه محدودی از عناصر از همان نوع است.

¨ مجموعه عملیات:

§ درج کنیدعنصر به مجموعه

§ حذفعنصر از مجموعه

§ تعلق داشتنتابعی است که اگر عنصر متعلق به مجموعه باشد مقدار true را برمی گرداند.

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

پسوندهای تخصصی ATD "Set" در جهات مختلف در نظر گرفته می شوند:

§ نزدیک به مفهوم «مجموعه» مفهوم «مجموعه» است. ست (کیف، مولتی ست) - درست مانند یک مجموعه، خانواده ای از عناصر، صرف نظر از اینکه رابطه ترتیب روی عناصر مشخص شده باشد، اما عناصر موجود در مجموعه می توانند در مقدار تکرار شوند. به طور کلی، یک مجموعه را می توان با یک مجموعه نشان داد، برای مثال، که عناصر آن جفت [مقدار عنصر، تعداد رخدادها در مجموعه] هستند.

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

§ اختصاص یک رابطه سفارش، جزئی یا خطی، در مجموعه، طبیعی به نظر می رسد، «صف اولویت» ADT نمونه ای از چنین توسعه تخصصی ADT «مجموعه» است. به طور مشابه، در حوزه موضوعی مسئله در حال حل، روابط دیگری در مجموعه ممکن است مورد توجه باشد.

§ یک موقعیت اساسی در ریاضیات توسط مفهوم رابطه هم ارزی و بر این اساس، مفهوم تقسیم یک مجموعه به کلاس های هم ارزی اشغال شده است. به طور طبیعی، این مفهوم به طور گسترده ای در تحولات عملیمدل های حل مسئله حوزه های موضوعی. ADT "خانواده مجموعه های جدا" (Disjoint Sets, Partitions, Partitions) نمونه ای از توسعه تخصصی مربوطه ATD "Set" است.

برای توسعه های تخصصی ATD "Set"، عملیات فوق به طور طبیعی به روش مناسب مشخص شده و عملیات جدید مورد علاقه ظاهر می شود.

2.3. فرهنگ لغت، نقشه، نام دیگر - آرایه انجمنی.

¨ مجموعه مقادیر ممکن مجموعه محدودی از عناصر از همان نوع است، به شکلی که Key کلید منحصر به فرد عنصر است، Value مقدار واقعی است.

¨ مجموعه عملیات:

§ درج کنیدیک عنصر (با یک کلید) در یک مجموعه.

§ حذفیک عنصر (داده شده توسط یک کلید) از یک مجموعه.

§ عنصر را پیدا کنید- تابعی که مقدار یک عنصر را با کلید یا مقدار خالی را برمی‌گرداند اگر عنصری با چنین کلیدی در مجموعه نباشد.

ADT "Dictionary" نسخه تخصصی مفهوم نقشه برداری (ذخیره شده) (کلیدهای مقادیر) است که به طور گسترده در برنامه نویسی عملی استفاده می شود. اما برای برخی از حوزه های موضوعی، ممکن است طراحی ATD راحت تر باشد نقشه برداری که به تعریف ریاضی کلاسیک نزدیکتر است.

2.4. صف اولویت.

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

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

¨ مجموعه عملیات:

§ درج کنیدعنصر در یک مجموعه (به صورت خطی)

§ حذف حداقلعنصر از مجموعه

§ حداقل را پیدا کنیدتابعی است که مقدار حداقل عنصر در مجموعه را برمی گرداند.

ما همچنین تغییرات (ضروری) این ADT را با عملیات اضافی در نظر می گیریم:

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

§ دو صف را که در یکی از آنها همه عناصر دارای اولویت بالاتری نسبت به تمام عناصر صف دیگر هستند به یک صف اولویت بدون حفظ صف های الحاقی اصلی زنجیره بزنید.

§ ادغام دو مجموعه مرتب شده ناهمگون (ادغام دو صف از این قبیل) در یک مجموعه مرتب شده (یک صف اولویت)، همچنین بدون حفظ مجموعه های ادغام شده اصلی.

§ مقدار (اولویت) عنصر مشخص شده را کاهش دهید.

§ حذف (خودسرانه) یک عنصر داده شده از یک مجموعه.

2.5. مجموعه های جدا، پارتیشن ها، پارتیشن ها.

¨ مجموعه مقادیر ممکن مجموعه های محدود (خانواده ها) از مجموعه های محدود غیر همپوشانی هستند. عناصر خانواده مشخص می شوند، یعنی. هر مجموعه در خانواده یک نام (بی نظیر) دارد.

¨ مجموعه عملیات:

§ ادغام (A,B)– عملیاتی به شکل A:= A È B بدون حفظ مجموعه های ادغام شده اصلی (به این معنی که مقدار جدید خانواده به عنوان یک خانواده از مجموعه های جدا باقی می ماند و تعداد آنها کاهش می یابد).

§ مجموعه را پیدا کنیدتابعی است که برای یک x معین، نام چنین مجموعه ای X را در خانواده ای که x Î X برمی گرداند، برمی گرداند.

2.6. درختان، نمودارها و روابط عمومی.

در ریاضیات گسسته، توجه ویژه ای به روابط (متناهی) شکل - درخت، نمودار و شبکه (مولتی گراف، هایپرگراف) می شود که تفسیر هندسی مشخصی دارند:

¨ نمودار یک رابطه دودویی (متناهی) (متقارن در مورد گراف های غیر جهت دار)، E Í V 2، که در آن V مجموعه رئوس و E مجموعه یال های گراف است.

در ریاضیات گسسته، E معمولاً نه به عنوان یک مجموعه، بلکه به عنوان مجموعه ای از یال های نمودار تعریف می شود، این به ما امکان می دهد نمودارهایی را در نظر بگیریم که در آنها یک جفت رئوس می توانند توسط چندین یال به هم متصل شوند (مثلاً با برچسب های متفاوت).

¨ درخت یک رابطه دودویی از نظم جزئی (سخت) است که علاوه بر این الزامات (سلسله مراتب، ساختار درختی) را برآورده می کند:

§ از این واقعیت که x<у,z следует, что у и z сравнимы, т.е. либо у£z либо z£у (х<у трактуется как: х встречается раньше у в пути к корню дерева, х – потомок, у - предок);

§ در مجموعه V (راس درخت) بزرگترین عنصر (ریشه درخت) وجود دارد.

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

¨ خالص یک رابطه شکل کلی است که می تواند به عنوان یک تعمیم تعبیر شود - E Í VÈV 2 È...V k یا به عنوان یک رابطه (E Í V k) با مجموعه ای از عناصر V که دارای "تهی" (ساختگی) هستند. عنصر

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

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