რა არის აბსტრაქტული მონაცემთა ტიპი? აბსტრაქტული კლასები და კლასის წევრები. სპეციალური ტიპის ნაკრები

29.03.2019

მონაცემთა აბსტრაქტული მოდელების შემუშავება და მათი დამუშავების გზები არის კომპიუტერული პრობლემების გადაჭრის კრიტიკული კომპონენტი. ამის მაგალითებს ვხედავთ როგორც დაბალ დონეზე ყოველდღიურ პროგრამირებაში (მაგალითად, მასივების და დაკავშირებული სიების გამოყენებისას, განხილული), ასევე მაღალ დონეზე, როდესაც გამოიყენება პრობლემების გადაჭრა (როგორც დაკავშირების პრობლემის გადაჭრისას შეერთების საძიებო ტყის გამოყენებით. "შესავალში"). ეს ლექცია განიხილავს მონაცემთა აბსტრაქტულ ტიპებს (შემდგომში ADT), რომლებიც საშუალებას გაძლევთ შექმნათ პროგრამები მაღალი დონის აბსტრაქციების გამოყენებით. აბსტრაქტული მონაცემთა ტიპები საშუალებას იძლევა აბსტრაქტული (კონცეპტუალური) ტრანსფორმაციები, რომლებსაც პროგრამები ახორციელებენ მონაცემებზე, გამოყოფილი იყოს მონაცემთა სტრუქტურის ნებისმიერი კონკრეტული წარმოდგენისგან და ალგორითმის ნებისმიერი კონკრეტული განხორციელებისგან.

ყველა გამოთვლითი სისტემა დაფუძნებულია აბსტრაქციის დონეებზე: სილიციუმის და სხვა მასალების გარკვეული ფიზიკური თვისებები იძლევა ბიტის აბსტრაქტული მოდელის მიღების საშუალებას, რომელსაც შეუძლია მიიღოს ბინარული მნიშვნელობები 0-1; შემდეგ აპარატის აბსტრაქტული მოდელი აგებულია ბიტების გარკვეული ნაკრების მნიშვნელობების დინამიურ თვისებებზე; შემდგომში, მანქანურ ენაზე პროგრამის კონტროლის ქვეშ მყოფი მანქანის მუშაობის პრინციპიდან გამომდინარე, აგებულია პროგრამირების ენის აბსტრაქტული მოდელი; და ბოლოს, აგებულია ალგორითმის აბსტრაქტული კონცეფცია, რომელიც დანერგილია პროგრამის სახით C++-ში. აბსტრაქტული მონაცემთა ტიპები შესაძლებელს ხდის ამ პროცესის შემდგომ გაგრძელებას და აბსტრაქტული მექანიზმების შემუშავებას კონკრეტული გამოთვლითი პრობლემებისთვის უფრო მაღალ დონეზე, ვიდრე ეს არის C++ სისტემის მიერ მოწოდებული, აბსტრაქტული მექანიზმების შემუშავება, რომლებიც ორიენტირებულია კონკრეტულ აპლიკაციებზე და შესაფერისია პრობლემების გადასაჭრელად აპლიკაციების მრავალ დომენში. და ასევე შექმენით აბსტრაქტული უმაღლესი დონის მექანიზმები, რომლებიც იყენებენ ამ ძირითად დიზაინებს. მონაცემთა აბსტრაქტული ტიპები გვაწვდიან ინსტრუმენტების უსასრულოდ გაფართოებულ კომპლექტს უფრო და უფრო ახალი პრობლემების გადასაჭრელად.

ერთის მხრივ, აბსტრაქტული კონსტრუქციების გამოყენება ათავისუფლებს საზრუნავს მათ დეტალურ განხორციელებასთან დაკავშირებით; მეორეს მხრივ, როცა შესრულებაპროგრამა მნიშვნელოვანია, თქვენ უნდა იცოდეთ ძირითადი ოპერაციების შესრულების ხარჯები. ჩვენ ვიყენებთ უამრავ ძირითად აბსტრაქციას, რომელიც ჩაშენებულია აპარატურაკომპიუტერი და ემსახურება მანქანის ინსტრუქციების საფუძველს; სხვა აბსტრაქციების დანერგვა პროგრამულ უზრუნველყოფაში; და გამოიყენეთ დამატებითი აბსტრაქციები, რომლებიც მოწოდებულია ადრე დაწერილი სისტემის პროგრამული უზრუნველყოფით. მაღალი დონის აბსტრაქტული კონსტრუქტები ხშირად მომდინარეობს უფრო მარტივი კონსტრუქციებიდან. იგივე ძირითადი პრინციპი მოქმედებს ყველა დონეზე: იპოვნეთ პროგრამებში ყველაზე მნიშვნელოვანი ოპერაციები და მონაცემთა ყველაზე მნიშვნელოვანი მახასიათებლები და შემდეგ ზუსტად განსაზღვრეთ ორივე აბსტრაქტულ დონეზე და შეიმუშავეთ ეფექტური კონკრეტული მექანიზმები მათი განხორციელებისთვის. ამ ლექციაში განვიხილავთ ამ პრინციპის გამოყენების მრავალ მაგალითს.

აბსტრაქციის ახალი დონის შემუშავება მოითხოვს (1) აბსტრაქტული ობიექტების განსაზღვრას, რომლებზეც მანიპულირებაა საჭირო და ოპერაციები, რომლებიც უნდა შესრულდეს მათზე; (2) წარმოადგენს მონაცემებს მონაცემთა ზოგიერთ სტრუქტურაში და განახორციელებს ოპერაციებს; (3) და (რაც მთავარია) უზრუნველყოს, რომ ეს ობიექტები მოსახერხებელია გამოყენებული პრობლემების გადასაჭრელად. ეს პუნქტები ასევე ეხება მონაცემთა მარტივ ტიპებს, ამიტომ მონაცემთა ტიპების მხარდაჭერის ძირითადი მექანიზმები, რომლებიც განხილული იყო „მონაცემთა ელემენტარულ სტრუქტურებში“ შეიძლება ადაპტირებული იყოს ჩვენი მიზნებისთვის. თუმცა, C++ გვთავაზობს მნიშვნელოვან გაფართოებას სტრუქტურის მექანიზმისთვის, რომელსაც ეწოდება კლასი. კლასები ძალზე სასარგებლოა აბსტრაქციის ფენების შესაქმნელად და, შესაბამისად, განიხილება წიგნის დანარჩენ ნაწილში ამ მიზნისთვის გამოყენებული პირველადი ინსტრუმენტი.

განმარტება 4.1.აბსტრაქტული მონაცემთა ტიპი (ADT) არის მონაცემთა ტიპი (მნიშვნელობების ნაკრები და ოპერაციების ნაკრები ამ მნიშვნელობებზე), რომლის წვდომა შესაძლებელია მხოლოდ ინტერფეისის საშუალებით. პროგრამას, რომელიც იყენებს ADT-ს, დაერქმევა კლიენტს, ხოლო პროგრამას, რომელიც შეიცავს ამ ტიპის მონაცემების სპეციფიკაციას, დაერქმევა განხორციელება.

ეს არის სიტყვა, რომელიც მხოლოდ მონაცემთა ტიპს აბსტრაქტულ ხდის: ADT-ის შემთხვევაში, კლიენტის პროგრამებს არ აქვთ წვდომა მონაცემთა მნიშვნელობებზე არანაირად, გარდა ინტერფეისში აღწერილი ოპერაციებისა. ამ მონაცემების წარმოდგენა და ფუნქციები, რომლებიც ახორციელებენ ამ ოპერაციებს, განხორციელების პროცესშია და მთლიანად გამოყოფილია ინტერფეისით კლიენტისგან. ჩვენ ვამბობთ, რომ ინტერფეისი გაუმჭვირვალეა: კლიენტი ვერ ხედავს განხორციელებას ინტერფეისის საშუალებით.

C++ პროგრამებში ეს განსხვავება, როგორც წესი, ცოტა უფრო მკაფიოდ კეთდება, რადგან ინტერფეისის შექმნა ყველაზე მარტივია. მონაცემთა პრეზენტაცია, მაგრამ მიუთითებს, რომ კლიენტის პროგრამებს არ აქვთ პირდაპირ წვდომა მონაცემებზე. სხვა სიტყვებით რომ ვთქვათ, კლიენტის პროგრამის შემქმნელებს შეუძლიათ იცოდნენ მონაცემთა პრეზენტაცია, მაგრამ მისი გამოყენება არანაირად არ შეიძლება.

მაგალითად, განიხილეთ მონაცემთა ტიპის ინტერფეისი წერტილებისთვის (პროგრამა 3.3) 3.1 განყოფილებიდან „მონაცემთა ელემენტარული სტრუქტურები“. ეს ინტერფეისი ცალსახად აცხადებს, რომ წერტილები წარმოდგენილია როგორც სტრუქტურები, რომლებიც შედგება წყვილი მცურავი პუნქტიანი რიცხვებისგან, აღინიშნება x და y. მონაცემთა ტიპების ეს გამოყენება გავრცელებულია დიდ პროგრამულ სისტემებში: ჩვენ ვავითარებთ კონვენციების ერთობლიობას მონაცემთა წარმოდგენისთვის (და ასევე განვსაზღვრავთ მათთან დაკავშირებულ ოპერაციების ერთობლიობას) და ვაძლევთ ამ წესებს ხელმისაწვდომს ინტერფეისის საშუალებით, რათა მათი გამოყენება შესაძლებელი იყოს კლიენტის პროგრამებში. რომლებიც დიდი სისტემის ნაწილია. მონაცემთა ტიპი უზრუნველყოფს სისტემის ყველა ნაწილის თანმიმდევრულობას სისტემის მასშტაბით მონაცემთა სტრუქტურების წარმოდგენისას. რაც არ უნდა კარგი იყოს ეს სტრატეგია, მას აქვს ერთი ნაკლი: თუ შეცვლა გჭირდებათ მონაცემთა პრეზენტაცია, მაშინ მოგიწევთ ყველა კლიენტის პროგრამის შეცვლა. პროგრამა 3.3 კვლავ გვაძლევს მარტივ მაგალითს: მონაცემთა ამ ტიპის შექმნის ერთ-ერთი მიზეზი არის კლიენტის პროგრამების გაადვილება წერტილებთან მუშაობა და ჩვენ ველით, რომ კლიენტებს ექნებათ წვდომა ცალკეულ წერტილების კოორდინატებზე საჭიროების შემთხვევაში. მაგრამ ჩვენ არ შეგვიძლია გადავიდეთ მონაცემთა განსხვავებულ წარმოდგენაზე (ვთქვათ, პოლარული კოორდინატები, ან 3D კოორდინატები, ან თუნდაც მონაცემთა სხვადასხვა ტიპები ინდივიდუალური კოორდინატებისთვის) ყველა კლიენტის პროგრამის შეცვლის გარეშე.

ამის საპირისპიროდ, პროგრამა 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; ) float მანძილი(POINT a) (float dx = x-a.x , dy = y-a.y დაბრუნების sqrt(dx*dx + dy*dy);

პროგრამა 4.2. კლიენტის პროგრამა POINT კლასისთვის (უახლოესი წერტილის პოვნა)

3.8 პროგრამის ეს ვერსია არის კლიენტი, რომელიც იყენებს 4.3 პროგრამაში განსაზღვრულ POINT ADT-ს. ახალი ოპერაცია ქმნის 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 = ახალი 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

ამ მრავალფეროვნების მონაცემთა უნივერსალური წარმოდგენა რთული და არაპრაქტიკულია. მიზანშეწონილია მათი დაყოფა 3 ტიპად

რა არის მონაცემთა ტიპი? მონაცემთა ტიპი განისაზღვრება: – კომპიუტერის მეხსიერებაში წარმოდგენის ფორმატით ალგორითმული ენის გარკვეული კონვენციების მიხედვით, მაგრამ გამოთვლების საჭიროების გარეშე; - მოქმედი მნიშვნელობების ნაკრები, რომელსაც შეუძლია მიიღოს არჩეული ტიპის ცვლადი ან მუდმივი; – ამ ტიპის მოქმედი ოპერაციების ნაკრები. 4

მონაცემთა ტიპების მაგალითები მთელი რიცხვის ტიპები რეალური ტიპი ლოგიკური ტიპი სიმბოლოს ტიპი ჩამოთვლილი ტიპი ინტერვალის ტიპი მაჩვენებლები 5

მთელი რიცხვის ტიპები არსებობს ხუთი წინასწარ განსაზღვრული მთელი ტიპი: Shortint, Integer, Longint, Byte და Word. თითოეული ტიპი აღნიშნავს მთელი რიცხვების კონკრეტულ ქვეჯგუფს. ერთი ინტეგრალური ტიპის მნიშვნელობა შეიძლება ცალსახად გარდაიქმნას სხვა ინტეგრალურ ტიპად კასტის ტიპის გამოყენებით. 6

რეალური ტიპი რეალური ტიპი არის რიცხვების ქვეჯგუფი, რომელიც წარმოდგენილია მცურავი წერტილის ფორმატით და ციფრების ფიქსირებული რაოდენობით. მცურავი წერტილის ფორმატში მნიშვნელობის ჩაწერა ჩვეულებრივ მოიცავს სამ მნიშვნელობას - m, b და e - ისეთს, რომ m * b ^ e = n, სადაც b ყოველთვის არის 2 და m და e არის მთელი რიცხვები რეალურ დიაპაზონში. m და e-ის ეს მნიშვნელობები კიდევ უფრო განსაზღვრავს რეალური ტიპის წარმოდგენის დიაპაზონს და სიზუსტეს. მაგალითი: 0.143 E+22, სადაც m - 0.143; b=2 (იგულისხმება), e=22. არსებობს ხუთი სახის რეალური ტიპი: რეალური, ერთჯერადი, ორმაგი, გაფართოებული და კომპ. 7

ლოგიკური ტიპი არსებობს 4 წინასწარ განსაზღვრული ლოგიკური (Boolean) ტიპი: Boolean, Byte. Bool, Word. ბული და ლონგი. ბული. ლოგიკური მნიშვნელობები აღინიშნება ჩაშენებული მუდმივი იდენტიფიკატორებით False და True. ლოგიკური ცვლადები შეიძლება გამოყენებულ იქნას ნებისმიერი ლოგიკური გამოთვლების შედეგების შესანახად. ლოგიკური ცვლადებისთვის დაშვებულია მხოლოდ 2 შედარების ოპერაცია: "=" (ტოლი) და "" (არათანაბარი). 8

სიმბოლოების ტიპი ამ ტიპის მნიშვნელობების ნაკრები არის სიმბოლოები, რომლებიც დალაგებულია ASCII სიმბოლოების გაფართოებული ნაკრების მიხედვით. ეს არის ასოები ["A". . . "Z", "a". . . "z"], ნომრები ["0". . . "9"], სასვენი ნიშნები და სპეციალური სიმბოლოები. ამ ტიპის ცვლადი მეხსიერებაში ერთ ბაიტს იკავებს. 9

აღრიცხვის ტიპი აღრიცხვის ტიპები განსაზღვრავენ მნიშვნელობების მოწესრიგებულ კომპლექტს იდენტიფიკატორების ჩამოთვლით, რომლებიც წარმოადგენენ ამ მნიშვნელობებს. კომპლექტები დალაგებულია თანმიმდევრობის მიხედვით, რომელშიც მითითებულია იდენტიფიკატორები. ტიპი Week = (ორშაბათი, სამშაბათი, ოთხშაბათი, ხუთშაბათი, პარასკევი, შაბათი, კვირა); 10

ინტერვალის ტიპი ინტერვალის ტიპი წარმოადგენს მნიშვნელობების დიაპაზონს რიგითი ტიპისგან. ინტერვალის ტიპის განმარტება მოიცავს ყველაზე მცირე და უდიდეს მნიშვნელობას ქვედიაპაზონში. ტიპი ინტერვალი = 0. . . 1000; ამ ტიპის დეკლარაცია ეუბნება შემდგენელს, რომ მხოლოდ მითითებულ დიაპაზონში მყოფი რიცხვები მოქმედებს ამ ტიპის ცვლადებისთვის. ამრიგად, პროგრამას შეუძლია ავტომატურად შეამოწმოს ამ ცვლადების მინიჭების ოპერაციების სისწორე. თერთმეტი

საერთო მონაცემთა ტიპებისთვის მონაცემთა თითოეულ ტიპს აქვს მასთან დაკავშირებული რამდენიმე მარტივი ოპერაცია. მთელი ოპერაციები +, -, *, div, mod REAL - ოპერაციები + , -, *, / BOOLEAN - ოპერაციები - კავშირი (და), დისიუნქცია V (ან), უარყოფა (არა) CHAR ოპერაციები ORD (c) -N : ( C ASCII-ში), CHR (I) I-th სიმბოლო ASCII-ში ინფორმაციის წარმოდგენის მოცულობისა და სირთულის მატებასთან ერთად, ჩნდება მისი წარმოდგენის, შენახვისა და დამუშავების მოსახერხებელი ფორმების საჭიროება. 12

განმარტება: აბსტრაქტული მონაცემთა ტიპი (ATD ან აბსტრაქტული მონაცემთა ტიპი, ან ADT) არის აბსტრაქტული ობიექტების ნაკრები, რომელიც წარმოადგენს მონაცემთა ელემენტებს და მასზე განსაზღვრულ ოპერაციების კომპლექტს, რომელიც შეიძლება შესრულდეს ამ ნაკრების ელემენტებზე. 13

ADT - მონაცემთა ტიპების განზოგადება აბსტრაქტული მონაცემთა ტიპები (ADT) შეიძლება ჩაითვალოს პროგრამირების ენების გაფართოების საშუალებად. მოდით შევადაროთ აბსტრაქტული მონაცემთა ტიპი ისეთ ნაცნობ კონცეფციას, როგორიცაა პროცედურა. პროცედურა შეიძლება ჩაითვალოს ოპერატორის განზოგადებულ კონცეფციად. პროცედურების ორი დამახასიათებელი თვისება, განზოგადება და ინკაფსულაცია, შესანიშნავად ახასიათებს მონაცემთა აბსტრაქტულ ტიპებს. ADT შეიძლება მივიჩნიოთ, როგორც მონაცემთა მარტივი ტიპების განზოგადება (მთლიანი, რეალური და ა.შ.), ისევე როგორც პროცედურა არის მარტივი ოპერატორების განზოგადება (+, - და ა.შ.) 14.

ADT Abstract მონაცემთა სტრუქტურების უპირატესობები შექმნილია მოსახერხებელი შენახვისა და ინფორმაციის ხელმისაწვდომობისთვის. ისინი უზრუნველყოფენ მოსახერხებელ ინტერფეისს შენახულ ობიექტებთან საერთო ოპერაციებისთვის, ხოლო მომხმარებლისგან მალავენ განხორციელების დეტალებს. რა თქმა უნდა, ეს ძალიან მოსახერხებელია და საშუალებას გაძლევთ მიაღწიოთ პროგრამის უფრო მეტ მოდულარობას. 15

მაგალითი დიდი შენობის სხვადასხვა ოთახებში ტემპერატურის ავტომატური კონტროლისთვის სასარგებლო ADT იქნება თერმოსტატი. პროგრამას შეიძლება ჰქონდეს მრავალი თერმოსტატის ტიპის ცვლადი, რომელიც შეესაბამება რეალურ თერმოსტატებს შენობის სხვადასხვა ზონაში. ADT შეიძლება აღწერილი იყოს მისი სახელით, მნიშვნელობების ნაკრებით და მოქმედი ოპერაციებით, ისევე როგორც ნებისმიერი სხვა მონაცემთა ტიპი. აღწერა თერმოსტატის ტიპისთვის: – მონაცემთა ტიპი: თერმოსტატი – მნიშვნელობების დიაპაზონი: ტემპერატურა შეიძლება განსხვავდებოდეს 0-დან 50 გრადუსამდე (ცელსიუსამდე). - ოპერაციები: მაღალი, დაბალი, დაყენება, შემოწმება, სიგნალიზაცია. (შეგიძლიათ მოიფიქროთ ბევრი სასარგებლო ოპერაცია, მაგრამ ძალიან ბევრი მათგანი ამცირებს აბსტრაქციას) 16

აბსტრაქციის დონეები აბსტრაქციის დონეები პროგრამული უზრუნველყოფის ფენებს ჰგავს. აბსტრაქციის უმაღლესი დონე ასახავს მომხმარებლის გაგებას პრობლემის გადაწყვეტის შესახებ. აბსტრაქციის ქვედა დონე არის პროგრამირების ენის შესაძლებლობები. 17

მომხმარებლის დონის აბსტრაქციის მაგალითი არქიტექტორი წარმოადგენს სახლს, როგორც კედლებს, იატაკებს, ფანჯრებს, კარებს და ა.შ. ამ შემთხვევაში, მონაცემთა ტიპია Drawing. კარები იქნება კარგი აბსტრაქტული ტიპი. მონაცემთა ტიპი: ნახაზი. კარის ოპერაციები: დახაზვა. კარის წაშლა. კარის დახატვა. Ორმაგი. კარი……. ნახატი. კარები არის მაღალი დონის აბსტრაქცია, რომელიც ასახავს მომხმარებლის შეხედულებას პრობლემის შესახებ 18

პროგრამისტის დონის აბსტრაქციის მაგალითი პროგრამისტს შეუძლია შესთავაზოს აბსტრაქციის სხვა დონე ამ ობიექტებისთვის, როგორიცაა მართკუთხედი. მონაცემთა ტიპი: მართკუთხედი ოპერაციები: დახაზვა. მართკუთხედის წაშლა. მართკუთხედის გაყოფა. მართკუთხედი. Ზე. ნაწილები……. მართკუთხედი უფრო დაბალი დონის აბსტრაქციაა, რადგან ის უფრო ახლოსაა განხორციელებასთან. 19

ADT კონსტრუქტორები თითოეული ADT უნდა შეიცავდეს ოპერაციებს მისი ტიპის მნიშვნელობების ასაგებად. ასეთ ოპერაციებს კონსტრუქტორებს უწოდებენ. უნდა იყოს საკმარისი კონსტრუქტორი მოცემული ტიპის მნიშვნელობების მთელი ნაკრების შესაქმნელად. ADT, რომელიც აკმაყოფილებს ამ თვისებას, ეწოდება სრული. არასრული ADT არის დიზაინის შეცდომა. 20

რეკომენდაციები მონაცემთა აბსტრაქტული ტიპის ოპერაციების არჩევისთვის მიზანშეწონილია შემდეგი ოპერაციების ჩართვა: – კონსტრუქტორის ოპერაციები, – გადამოწმების ოპერაციები, – ტიპის კონვერტაციის ოპერაციები, – შეყვანა-გამომავალი ოპერაციები, – კოპირების ოპერაციები, – ამორჩევის ოპერაციები. შეეცადეთ მინიმუმამდე დაიყვანოთ ოპერაციების რაოდენობა. მარტივი ADT უფრო ადვილი გასაგებია. არჩეული ტიპის აბსტრაქციასთან დაკავშირებული ოპერაციების შენარჩუნება. 21

პირველადი კონსტრუქტორი ოპერაციებს, რომლებიც ქმნიან ADT-ის ახალ მნიშვნელობებს მისი წინა მნიშვნელობის მიუხედავად, პირველადი კონსტრუქტორები ეწოდება. თითოეული ADT მოიცავს მინიმუმ ერთ ძირითად კონსტრუქტორს: მის გარეშე შეუძლებელია საწყისი მნიშვნელობის გენერირება. 22

დამალული ტიპების გამოყენება აბსტრაქტული მონაცემთა ტიპები საუკეთესოდ არის გამოცხადებული, როგორც ფარული. ეს საშუალებას იძლევა მონაცემთა სტრუქტურის აღწერილობა გადავიდეს განხორციელების მოდულში, სადაც ის ძირითადად გამოიყენება. ისინი ასევე უზრუნველყოფენ იმპორტიორის მიერ ტიპის კომპონენტებზე პირდაპირი წვდომის თავიდან აცილების შესაძლებლობას. ვინაიდან დამალული ტიპი ყოველთვის ხორციელდება მაჩვენებლის გამოყენებით, ADT-ში უნდა იყოს ჩართული სამი ოპერაცია. – შექმნა - ოპერაცია, რომელიც ქმნის შესაბამისი სტრუქტურის კვანძს. – Destroy არის ოპერაცია ფარული ტიპის კვანძის მეხსიერების გასათავისუფლებლად. – მინიჭება - ფარული ტიპის კვანძის დინამიური სტრუქტურის ველების კოპირების ოპერაცია. 23

რა არის აბსტრაქტული მონაცემთა ტიპის სპეციფიკაცია და განხორციელება. პროგრამირების ენაში ასეთი განმარტება ფორმალიზებულია, როგორც სპეციალური სინტაქსური კონსტრუქცია, რომელსაც სხვადასხვა ენაზე ეწოდება კაფსულა, მოდული, კლასტერი, კლასი, პაკეტი, ფორმა და ა.შ. ეს კონსტრუქცია თავისი ყველაზე განვითარებული ფორმით შეიცავს: მონაცემთა ტიპის სპეციფიკაციას. ინტერფეისის აღწერილობის ჩათვლით (განსაზღვრული ტიპის დასახელება, ოპერაციების სახელები მათი პროფილების მითითებით) და ოპერაციების და ობიექტების აბსტრაქტული აღწერილობა, რომლებთანაც ისინი მუშაობენ, გარკვეული სპეციფიკაციის საშუალებების გამოყენებით; მონაცემთა ტიპის განხორციელება, იგივე ოპერაციების და ობიექტების სპეციფიკური აღწერილობის ჩათვლით. 24

მონაცემთა ტიპების კლასიფიკაცია აღწერისა და დაცვის მეთოდის მიხედვით, თუ მონაცემთა ტიპის აღწერა გროვდება ერთ ადგილას (ერთ პაკეტში), ანუ მისი ობიექტები და ოპერაციები გაერთიანებულია ერთ კონცეფციაში; მას აქვს განმარტება, რომელიც შეიძლება შეიცავდეს მხოლოდ მის განხორციელებას; ენკაფსულირებული, თუ მონაცემთა ტიპი შეფუთულია, მისი განმარტება შეიცავს ინტერფეისის აღწერას და განხორციელებას, ასევე მოცემულია განხორციელების ინკაფსულაცია; აბსტრაქტი, თუ მონაცემთა ტიპი არის კაფსულირებული და მისი სპეციფიკაცია მოიცავს აბსტრაქტულ აღწერას. 25

სპეციფიკაციის კომპონენტები პროგრამირება, როგორც პროცესი, იწყება პრობლემის განცხადებით (მისი განმარტებით) ან პრობლემის დაზუსტებით. შემდგომ ტექსტში გამოყენებულია ექვსი კომპონენტისგან შემდგარი სპეციფიკაციები: – სათაური – გადასაჭრელი პრობლემის დასახელება; – აღწერა – რამდენიმე წინადადება, რომელიც აღწერს ამოცანის არსს; – შეყვანა – შეყვანის მონაცემების მოსალოდნელი ფორმის დეტალური აღწერა; – გამომავალი – გამომავალი მონაცემების მოსალოდნელი ფორმის დეტალური აღწერა; – შეცდომები - სიტუაციების დეტალური ჩამონათვალი, რომლებიც წარმოიქმნება, როდესაც შეყვანის მონაცემები არასწორია; – მაგალითი - შესრულების მაგალითი შეყვანა-გამომავალი თვალსაზრისით. 26

სპეციფიკაციის მაგალითი აბსტრაქტული მონაცემთა ტიპი STACK, რომელიც ახორციელებს მონაცემთა კარგად ცნობილ სტრუქტურას, რომელიც ხასიათდება იმით, რომ თქვენ შეგიძლიათ მასში „ჩადოთ“ რაიმე ელემენტი და „აირჩიოთ“ ის ელემენტი, რომელიც ახლახან იყო განთავსებული. STACK მონაცემთა ტიპის სპეციფიკაციის სინტაქსური ნაწილი ჰგავს ტიპის STACK სპეციფიკაციას CREATE: ფუნქცია () return (@); INSERT: ფუნქცია (მთლიანი; @) return (@); DELETE: ფუნქცია (@) დაბრუნება (@); TOP: ფუნქცია (@) დაბრუნება (მთლიანი); EMPTY: ფუნქცია (@) დაბრუნება (ლოგიკური); ბოლო სპეციფიკაცია; აქ, CREATE ოპერაცია აწარმოებს ცარიელ დასტას, INSERT - დასტას, რომლის ელემენტი დამატებულია "ზევით", DELETE - დასტა, რომელზეც ამოღებულია "ზედა" ელემენტი, TOP - "ზედა" ელემენტის მნიშვნელობა. სტეკი, EMPT - ნიშანი იმისა, რომ დასტა ცარიელია. სტეკის ელემენტები აქ შეიძლება იყოს მხოლოდ მთელი რიცხვები. 27

მონაცემთა აბსტრაქტული ტიპის იმპლემენტაცია დანერგვა უფრო მოსახერხებელია ობიექტზე ორიენტირებული პროგრამირების ენების გამოყენებით, როგორიცაა C++ ან Java, სადაც მონაცემთა აბსტრაქტული ტიპები მხარდაჭერილია კლასების გამოყენებით ამ ტიპის ოპერაციებიდან. ეს ნიშნავს, რომ ობიექტები აღწერილია როგორც მარტივი ტიპის მონაცემები, ან როგორც მასივები, ჩანაწერები ან გაერთიანებები. უფრო მეტიც, გამოიყენება წინასწარ განსაზღვრული მონაცემთა ტიპები ან ადრე განსაზღვრული ADT-ები. ოპერაციების განხორციელება შედგება ქვეპროგრამების აღწერისგან, რომლებიც ასრულებენ აუცილებელ მოქმედებებს მითითებულ ობიექტებთან. მაგალითად, ოპერაციები +, *, =. . და ა.შ., მაგრამ ამავე დროს ამ ოპერაციების განხორციელება იმალება. 28

რეზიუმეს ჩვეულებრივ უწოდებენ მონაცემთა ტიპს, რომელიც აშკარად არ არის წარმოდგენილი პროგრამირების ენაში, ეს არის შედარებითი ცნება - მონაცემთა ტიპი, რომელიც არ არის ერთ პროგრამირების ენაში, შეიძლება იყოს სხვაში.

აბსტრაქტული მონაცემთა ტიპი (ATD) განისაზღვრება მისი განხორციელების მეთოდის მიუხედავად:

ამ ტიპის შესაძლო მნიშვნელობების ნაკრები,

და ოპერაციების ნაკრები ამ ტიპის მნიშვნელობებით.

ADT-ის გამოყენება შეიძლება შემოიფარგლოს პროგრამული უზრუნველყოფის შემუშავების ეტაპით, მაგრამ პროგრამაში მისი აშკარა გამოყენებისთვის აუცილებელია მისი დანერგვა პროგრამირების ენაში არსებული (და ადრე დანერგილი) მონაცემთა ტიპების საფუძველზე:

ამ ტიპის მნიშვნელობების წარმოდგენის გზა,

და ოპერაციების განხორციელება ამ ტიპის მნიშვნელობებით.

ADT არ არის წინასწარ განსაზღვრული პროგრამირების ენაზე და უფრო მეტიც, ამ ტიპის კონსტრუქციული ოპერაციები, წინასწარ განსაზღვრული ენაში, გადადის დეველოპერ-პროგრამისტზე კითხვაზე, თუ როგორ უნდა წარმოადგინოს ამ ტიპის მნიშვნელობები და განახორციელოს ოპერაციები მნიშვნელობებით. ამ ტიპის. მაშასადამე, ასეთი ტიპის მონაცემებისთვის საკითხი ეხება ფორმის ოპერაციების განხორციელების განმარტებებსა და მეთოდებს კონსტრუქტორი (მნიშვნელობები და მონაცემთა მაღაზიები) ამ ტიპის, სელექტორი და მოდიფიკატორი ამ ტიპის კომპონენტები (მნიშვნელობები და მონაცემთა მაღაზიები) ეკისრება პროგრამისტის დეველოპერს.

ADT კონცეფციაში ცნებებს განსაკუთრებული სტატუსი აქვთ ინტერფეისი , გახსნილია მომხმარებლისთვის და განხორციელება , მისგან დამალული. ამ ცნებების განსაკუთრებული როლი ADT-ის კონცეფციაში დაკავშირებულია ფუნდამენტურ პოზიციასთან ADT კონცეფციის დამოუკიდებლობის შესახებ მისი განხორციელების მეთოდისგან.

თანამედროვე "პროგრამირების პრაქტიკულ ენებში", წინასწარ განსაზღვრული ტიპის სამშენებლო ოპერაცია ჩვეულებრივ გამოიყენება ADT-ის ასაგებად. კლასი , რომელიც აძლევს დეველოპერ-პროგრამისტს არა მხოლოდ მონაცემთა და ოპერაციების (ამ მონაცემებით) ერთ მთლიანობად დაჯგუფების საშუალებებს, არამედ ენკაფსულაციის, მემკვიდრეობის და პოლიმორფიზმის საშუალებებს, რათა გააკონტროლონ თუ როგორ ხდება ასეთი მონაცემების აგება და წვდომა. გაითვალისწინეთ, რომ კლასი აღწერს ADT-ის ერთ-ერთ შესაძლო განხორციელებას, კლასის დახატვა ADT-ზე გამოიხატება აბსტრაქციის ფუნქციით, მაგრამ შებრუნებული მიმართება ჩვეულებრივ არ არის ფუნქციონალური, შეიძლება არსებობდეს ერთი და იგივე ADT-ის რამდენიმე განხორციელება.

აბსტრაქტული მონაცემთა ტიპების კვლევაში, კონცეფციის მნიშვნელოვანი როლი " ტიპის პარამეტრიზაცია " მართლაც, მაგალითად, ADT "Stack" არ არის დამოკიდებული სტეკის ელემენტების ტიპზე, მაგრამ შეუძლებელია ამ ADT-ის განხორციელება "ზოგიერთი იდენტური ტიპის ელემენტებზე" მითითებით. Ada-ს პროგრამირების ენაში თავდაპირველად შედიოდა შესაბამისი ინსტრუმენტები პარამეტრიზებული მონაცემთა ტიპების ასაგებად, ხოლო თანამედროვე "პროგრამირების პრაქტიკულ ენებში", რომლებიც მხოლოდ STL ბიბლიოთეკის გამოყენებით განვითარების დღიდან გამოჩნდა. დღესდღეობით „განზოგადებული პროგრამირების“ კონცეფცია მნიშვნელოვან ადგილს იკავებს პრაქტიკულ პროგრამირებაში „პროგრამირების პრაქტიკულ ენებში“ ჩართვის გამო. ინსტრუმენტები პარამეტრიზებული მონაცემთა ტიპების შესაქმნელად (თარგები, შაბლონი , ზოგადი) .

ყოველივე ზემოთქმული ნიშნავს, რომ მეთოდოლოგიური და თეორიული თვალსაზრისით აუცილებელია „აბსტრაქტული მონაცემთა ტიპის“ ცნების უფრო დეტალური ზუსტი განმარტება. თეორიულად, "აბსტრაქტული მონაცემთა ტიპის" კონცეფცია ჩვეულებრივ განისაზღვრება როგორც მრავალდახარისხებული (მრავალძირიანი) ალგებრული სისტემა , რომელშიც, გარდა შესაძლო მნიშვნელობების სიმრავლისა (გადამზიდავი) და ასეთ მნიშვნელობებზე ოპერაციების სიმრავლისა, ხაზგასმულია შემდეგი ცნებები:

დალაგება და ხელმოწერა - ეს ცნებები საშუალებას გაძლევთ კლასიფიციროთ როგორც მედია ელემენტები, ასევე მათთან ოპერაციები მათი ტიპების მიხედვით (ოპერაციებისთვის - მათი არგუმენტების ტიპებისა და დაბრუნების მნიშვნელობის მიხედვით).

პრედიკატები არის ურთიერთობები მატარებლის ელემენტებზე. ეს საშუალებას გაძლევთ განსაზღვროთ შესაძლო მნიშვნელობების დიაპაზონი დასაშვებ მნიშვნელობებზე შეზღუდვების (მოთხოვნების) დაწესებით, ისევე როგორც თვითნებური ლოგიკური გამონათქვამებით მუშაობა ბუნებრივი ინტერპრეტაციით, იძულების გარეშე მათი ინტერპრეტაცია, როგორც წევრობის ფუნქციები კომპლექტებისთვის ან როგორც მრავალმხრივი. ღირებული ოპერაციები.

ამის საფუძველზე შესაძლებელია მონაცემთა აბსტრაქტული ტიპების განხილვა ერთი ჰოლისტიკური ლოგიკურ-ალგებრული თვალსაზრისით, მათ შორის კითხვები კონსტრუქტორების (ტიპები და მნიშვნელობები), სელექტორები და თვისებების მოდიფიკატორები ამ ტიპის ობიექტებისთვის.

"მონაცემთა სტრუქტურის" და "აბსტრაქტული მონაცემთა ტიპის" ცნებები გარკვეულწილად ძალიან ახლოს არის. შეიძლება, რა თქმა უნდა, ვივარაუდოთ, რომ ეს ცნებები უბრალოდ ორი შეხედულებაა ერთი და იგივეს შესახებ. ADT-ის წარმოდგენის მნიშვნელობები ყოველთვის ეფუძნება მონაცემთა გარკვეულ სტრუქტურას, ნაკლებად ან უფრო რთულს და ასეთ მნიშვნელობებზე ოპერაციების განხორციელება ბუნებრივად დამოკიდებულია ამ არჩეულ მონაცემთა სტრუქტურაზე. მეორეს მხრივ, თუ ჩვენ ნამდვილად გვინდა, ჩვენ ყოველთვის შეგვიძლია შევქმნათ მონაცემთა სტრუქტურა, რომელიც გვაინტერესებს, როგორც ADT.

მაგრამ მაინც განვასხვავებთ ამ ორ ცნებას, იმის გათვალისწინებით:

აბსტრაქტული მონაცემთა ტიპი - გულისხმობს აბსტრაქციის გარკვეულ დონეს, რათა დაფიქსირდეს გამოყენებული (დომენზე ორიენტირებული) მონაცემთა ტიპი, განურჩევლად მისი განხორციელების მეთოდებისა და შესაძლებელია ამ ტიპის მონაცემთა ჩართვა აპლიკაციის ბიბლიოთეკაში, ყოველ შემთხვევაში, კონკრეტული პროგრამული სისტემის სპეციფიკური განვითარება. ADT-ს შეიძლება ჰქონდეს რამდენიმე ალტერნატიული განხორციელება, რომელიც დაფუძნებულია მონაცემთა სხვადასხვა სტრუქტურებზე.

მონაცემთა სტრუქტურა უფრო მეტად არის მონაცემთა ორგანიზებისა და მართვის სქემა, რომელიც მოითხოვს შესაბამის სპეციფიკაციებს, როდესაც გამოიყენება კონკრეტულ სიტუაციებში კონკრეტული პრობლემების გადასაჭრელად.

აბსტრაქტული მონაცემთა ტიპები, პირველ რიგში, ბუნებრივად მოიცავს მათემატიკურ საბაზისო ალგებრულ სისტემებს - თანმიმდევრობებს, სიმრავლეებს, მიმართებებს და რუკებს (ფუნქციური ურთიერთობები, ფუნქციები). მაგრამ პროგრამირებაში წინა პლანზე არ არის ამ მათემატიკური ცნებების ზოგადი თვისებების შესწავლა, არამედ მათი გამოყენების შესაძლებლობა საგნობრივ სფეროში პრობლემების გადაჭრის მოდელების შემუშავებაში, ამ ამოცანების გადაჭრის ალგორითმების და ეფექტური განხორციელებისთვის. შემუშავებული ალგორითმები. ამიტომ, ADT-ის სახით პროგრამირებისას, ერთი მხრივ, ამ ძირითადი ალგებრული სისტემების შეზღუდული ვერსიები ჩვეულებრივ ფორმალიზებულია და, მეორე მხრივ, გაფართოებულია სპეციალიზებული ოპერაციების კომპლექტებით, რომლებიც პრაგმატულ ინტერესს წარმოადგენს. გამოყენების სფერო.

1.2. აბსტრაქტული მონაცემთა ტიპები

წინა ნაწილში წარმოდგენილი ცნებების უმეტესობა, როგორც წესი, ისწავლება პროგრამირების საწყის კურსზე და თქვენთვის ნაცნობი უნდა იყოს. მხოლოდ აბსტრაქტული მონაცემების ტიპები შეიძლება იყოს ახალი, ასე რომ, ჯერ განვიხილოთ მათი როლი პროგრამის შემუშავების პროცესში. უპირველეს ყოვლისა, მოდით შევადაროთ აბსტრაქტული მონაცემთა ტიპი ისეთ ნაცნობ კონცეფციას, როგორიცაა პროცედურა.

პროცედურა, ინტეგრალური პროგრამირების ინსტრუმენტი, შეიძლება ჩაითვალოს ოპერატორის განზოგადებულ კონცეფციად. პროგრამირების ენის ჩაშენებული ოპერატორებისგან განსხვავებით (მიმატება, გამრავლება და ა.შ.), რომლებიც შეზღუდულია მათი შესაძლებლობებით, პროცედურების დახმარებით პროგრამისტს შეუძლია შექმნას საკუთარი ოპერატორები და გამოიყენოს ისინი სხვადასხვა ტიპის ოპერანდებზე, არა მხოლოდ ძირითადი. პირობა. ასეთი ოპერატორის პროცედურის მაგალითია სტანდარტული მატრიცის გამრავლების ქვეპროგრამა.

პროცედურების კიდევ ერთი უპირატესობა (გარდა ახალი განცხადებების შექმნის შესაძლებლობისა) არის მათი გამოყენება კაფსულაციაალგორითმის ნაწილები პროგრამის ცალკეულ განყოფილებაში განთავსებით ყველა ოპერატორი, რომელიც პასუხისმგებელია პროგრამის ფუნქციონირების გარკვეულ ასპექტზე. ინკაფსულაციის მაგალითი: ერთი პროცედურის გამოყენება ნებისმიერი ტიპის შეყვანის წასაკითხად და მისი მოქმედების შესამოწმებლად. ინკაფსულაციის უპირატესობა ის არის, რომ ჩვენ ვიცით, რომელი ენკაფსულირებული განცხადებები უნდა შეიცვალოს, თუ პროგრამის ფუნქციონირებაში პრობლემები წარმოიქმნება. მაგალითად, თუ ჩვენ უნდა შევამოწმოთ შეყვანის მონაცემები დადებითი მნიშვნელობებისთვის, ჩვენ მხოლოდ უნდა შევცვალოთ კოდის რამდენიმე ხაზი და ზუსტად ვიცით სად არის ეს ხაზები.

აბსტრაქტული მონაცემთა ტიპის განსაზღვრა

ჩვენ განვსაზღვრავთ აბსტრაქტული მონაცემთა ტიპი(ATD) როგორც მათემატიკური მოდელი ამ მოდელის ფარგლებში განსაზღვრული ოპერატორების სიმრავლით. ADT-ის მარტივი მაგალითია მთელი რიცხვების სიმრავლე გაერთიანების, კვეთის და სიმრავლის სხვაობის ოპერატორებით. ADT მოდელში ოპერატორებს შეუძლიათ ჰქონდეთ არა მხოლოდ ADT-ით განსაზღვრული მონაცემების, არამედ სხვა ტიპის მონაცემების ოპერანდები: პროგრამირების ენის სტანდარტული ტიპები ან განსაზღვრული სხვა ADT-ებში. ოპერატორის მოქმედების შედეგი ასევე შეიძლება იყოს განსხვავებული ტიპის ADT მოდელისგან განსაზღვრული. მაგრამ ჩვენ ვვარაუდობთ, რომ რომელიმე ოპერატორის მინიმუმ ერთ ოპერანდს ან შედეგს აქვს მოცემული ADT მოდელში განსაზღვრული მონაცემთა ტიპი.

ზემოთ განხილული პროცედურების ორი დამახასიათებელი თვისება, განზოგადება და ინკაფსულაცია, შესანიშნავად ახასიათებს მონაცემთა აბსტრაქტულ ტიპებს. ADT შეიძლება მივიჩნიოთ, როგორც მონაცემთა მარტივი ტიპების განზოგადება (მთლიანი რიცხვები, რეალური რიცხვები და ა.შ.), ისევე როგორც პროცედურა არის მარტივი ოპერატორების განზოგადება (+, - და ა.შ.). ADT აერთიანებს მონაცემთა ტიპებს იმ გაგებით, რომ ტიპის განსაზღვრება და ამ ტიპის მონაცემებზე შესრულებული ყველა განცხადება შეიცავს პროგრამის ერთ განყოფილებას. თუ ჩვენ გვჭირდება ADT-ის იმპლემენტაციის შეცვლა, ჩვენ ვიცით სად ვიპოვოთ და რა შევცვალოთ პროგრამის ერთ პატარა მონაკვეთში და შეგვიძლია დარწმუნებული ვიყოთ, რომ ეს არ გამოიწვევს შეცდომებს პროგრამაში არსად ამ მონაცემთა ტიპთან მუშაობისას. . უფრო მეტიც, ADT ოპერატორების განსაზღვრის განყოფილების გარეთ, ჩვენ შეგვიძლია განვიხილოთ ADT ტიპები, როგორც პირველადი ტიპები, რადგან ტიპების დეკლარაცია ფორმალურად არ არის დაკავშირებული მათ განხორციელებასთან. მაგრამ ამ შემთხვევაში შეიძლება წარმოიშვას სირთულეები, რადგან ზოგიერთი განცხადების ინიცირება შესაძლებელია ერთზე მეტი ADT-ისთვის და ამ განცხადებებზე მითითებები უნდა იყოს რამდენიმე ADT-ის განყოფილებაში.

ძირითადი იდეების საილუსტრაციოდ, რომლებიც მიგვიყვანს ADT-ის შექმნამდე, განიხილეთ წინა განყოფილების ხარბ პროცედურა (ჩამონათვალი 1.3), რომელიც იყენებს მარტივ ოპერატორებს აბსტრაქტული მონაცემთა ტიპის LIST (მთლიანი რიცხვების სია) მონაცემებზე. ამ ოპერატორებმა უნდა შეასრულონ შემდეგი მოქმედებები LIST ტიპის newclr ცვლადზე.

1. სია ცარიელია.

2. აირჩიეთ სიის პირველი ელემენტი და თუ სია ცარიელია, დააბრუნეთ მნიშვნელობა null.

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. ზომა (A). ეს ფუნქცია იღებს კომპლექტის არგუმენტს A და აბრუნებს მთელი რიცხვის ტიპის ობიექტს, რომელიც ტოლია A სიმრავლის ელემენტების რაოდენობას. ტერმინი ADT იმპლემენტაცია გულისხმობს შემდეგს: პროგრამირების ენაზე თარგმნა ამ აბსტრაქტული მონაცემთა ტიპის ცვლადების განმსაზღვრელი დეკლარაციების განცხადებები, პლუს პროცედურები. ADT ობიექტებზე შესრულებული თითოეული განცხადება. განხორციელება დამოკიდებულია მონაცემთა სტრუქტურები,წარმოადგენს ATD. მონაცემთა თითოეული სტრუქტურა აგებულია გამოყენებული პროგრამირების ენის ძირითადი მონაცემთა ტიპების საფუძველზე, ამ ენაში არსებული მონაცემთა სტრუქტურირების ხელსაწყოების გამოყენებით. მასივი და ჩანაწერის სტრუქტურები მონაცემთა სტრუქტურირების ორი მნიშვნელოვანი ინსტრუმენტია, რომელიც ხელმისაწვდომია პასკალში. მაგალითად, SET ტიპის S ცვლადის ერთ-ერთი შესაძლო განხორციელება შეიძლება იყოს მასივი, რომელიც შეიცავს კომპლექტის ელემენტებს. ს.

ერთი და იგივე მოდელის ფარგლებში ორი განსხვავებული ADT-ის განსაზღვრის ერთ-ერთი მთავარი მიზეზი არის ის, რომ ამ ADT-ების ობიექტებზე უნდა განხორციელდეს განსხვავებული მოქმედებები, ე.ი. განსაზღვრეთ სხვადასხვა ტიპის ოპერატორები. ეს ჩანაწერი მოიცავს მხოლოდ რამდენიმე ძირითად მათემატიკურ მოდელს, როგორიცაა სიმრავლეების თეორია და გრაფიკის თეორია, მაგრამ სხვადასხვა იმპლემენტაცია შექმნის ოპერატორების სხვადასხვა კომპლექტს გარკვეული ADT-ების ამ მოდელებზე დაყრდნობით.

იდეალურ შემთხვევაში, სასურველია პროგრამების დაწერა ენაზე, რომლის ძირითადი მონაცემთა ტიპები და ოპერატორები საკმარისია ADT-ის განსახორციელებლად. ამ თვალსაზრისით, პასკალი არ არის ძალიან შესაფერისი ენა სხვადასხვა ADT-ების განსახორციელებლად, მაგრამ, მეორე მხრივ, ძნელია იპოვოთ სხვა პროგრამირების ენა, რომელშიც შესაძლებელი იქნებოდა ADT-ების ასე პირდაპირ გამოცხადება. ამ პროგრამირების ენების შესახებ დამატებითი ინფორმაციისთვის იხილეთ თემის ბოლოს ბიბლიოგრაფიული შენიშვნები.

აბსტრაქტული მონაცემთა ტიპი(ATD) განისაზღვრება მისი განხორციელების მეთოდის მიუხედავად:

§ ამ ტიპის შესაძლო მნიშვნელობების ნაკრები,

§ და ოპერაციების ნაკრები ამ ტიპის მნიშვნელობებით.

§ ამ ტიპის მნიშვნელობების წარმოდგენის გზა,

§ და ოპერაციების განხორციელება ამ ტიპის მნიშვნელობებით.

ADT არ არის წინასწარ განსაზღვრული პროგრამირების ენაზე და უფრო მეტიც, ამ ტიპის კონსტრუქციული ოპერაციები, წინასწარ განსაზღვრული ენაში, გადადის დეველოპერ-პროგრამისტზე კითხვაზე, თუ როგორ უნდა წარმოადგინოს ამ ტიპის მნიშვნელობები და განახორციელოს ოპერაციები მნიშვნელობებით. ამ ტიპის. მაშასადამე, ასეთი ტიპის მონაცემებისთვის საკითხი ეხება ფორმის ოპერაციების განხორციელების განმარტებებსა და მეთოდებს კონსტრუქტორი (მნიშვნელობები და მონაცემთა მაღაზიები) ამ ტიპის, სელექტორი და მოდიფიკატორი ამ ტიპის კომპონენტები (მნიშვნელობები და მონაცემთა მაღაზიები) ეკისრება პროგრამისტის დეველოპერს.

ADT კონცეფციაში ცნებებს განსაკუთრებული სტატუსი აქვთ ინტერფეისი , გახსნილია მომხმარებლისთვის და განხორციელება , მისგან დამალული. ამ ცნებების განსაკუთრებული როლი ADT-ის კონცეფციაში დაკავშირებულია ფუნდამენტურ პოზიციასთან ADT კონცეფციის დამოუკიდებლობის შესახებ მისი განხორციელების მეთოდისგან.

თანამედროვე "პროგრამირების პრაქტიკულ ენებში", წინასწარ განსაზღვრული ტიპის სამშენებლო ოპერაცია ჩვეულებრივ გამოიყენება ADT-ის ასაგებად. კლასი , რომელიც აძლევს დეველოპერ-პროგრამისტს არა მხოლოდ მონაცემთა და ოპერაციების (ამ მონაცემებით) ერთ მთლიანობად დაჯგუფების საშუალებებს, არამედ ენკაფსულაციის, მემკვიდრეობის და პოლიმორფიზმის საშუალებებს, რათა გააკონტროლონ თუ როგორ ხდება ასეთი მონაცემების აგება და წვდომა. გაითვალისწინეთ, რომ კლასი აღწერს ADT-ის ერთ-ერთ შესაძლო განხორციელებას, კლასის დახატვა ADT-ზე გამოიხატება აბსტრაქციის ფუნქციით, მაგრამ შებრუნებული მიმართება ჩვეულებრივ არ არის ფუნქციონალური, შეიძლება არსებობდეს ერთი და იგივე ADT-ის რამდენიმე განხორციელება.

აბსტრაქტული მონაცემთა ტიპების კვლევაში, კონცეფციის მნიშვნელოვანი როლი " ტიპის პარამეტრიზაცია " მართლაც, მაგალითად, ADT "Stack" არ არის დამოკიდებული სტეკის ელემენტების ტიპზე, მაგრამ შეუძლებელია ამ ADT-ის განხორციელება "ზოგიერთი იდენტური ტიპის ელემენტებზე" მითითებით. Ada-ს პროგრამირების ენაში თავდაპირველად შედიოდა შესაბამისი ინსტრუმენტები პარამეტრიზებული მონაცემთა ტიპების ასაგებად, ხოლო თანამედროვე "პროგრამირების პრაქტიკულ ენებში", რომლებიც მხოლოდ STL ბიბლიოთეკის გამოყენებით განვითარების დღიდან გამოჩნდა. დღესდღეობით „განზოგადებული პროგრამირების“ კონცეფცია მნიშვნელოვან ადგილს იკავებს პრაქტიკულ პროგრამირებაში „პროგრამირების პრაქტიკულ ენებში“ ჩართვის გამო. ინსტრუმენტები პარამეტრიზებული მონაცემთა ტიპების შესაქმნელად (თარგები, შაბლონი , ზოგადი) .

ყოველივე ზემოთქმული ნიშნავს, რომ მეთოდოლოგიური და თეორიული თვალსაზრისით აუცილებელია „აბსტრაქტული მონაცემთა ტიპის“ ცნების უფრო დეტალური ზუსტი განმარტება. თეორიულად, "აბსტრაქტული მონაცემთა ტიპის" კონცეფცია ჩვეულებრივ განისაზღვრება როგორც მრავალდახარისხებული (მრავალძირიანი) ალგებრული სისტემა , რომელშიც, გარდა შესაძლო მნიშვნელობების სიმრავლისა (გადამზიდავი) და ასეთ მნიშვნელობებზე ოპერაციების სიმრავლისა, ხაზგასმულია შემდეგი ცნებები:

§ დახარისხება და ხელმოწერა - ეს ცნებები საშუალებას გაძლევთ კლასიფიციროთ როგორც მედია ელემენტები, ასევე მათთან ოპერაციები მათი ტიპების მიხედვით (ოპერაციებისთვის - მათი არგუმენტების ტიპებისა და დაბრუნების მნიშვნელობის მიხედვით).

§ პრედიკატები არის მიმართებები მატარებლის ელემენტებზე. ეს საშუალებას გაძლევთ განსაზღვროთ შესაძლო მნიშვნელობების დიაპაზონი დასაშვებ მნიშვნელობებზე შეზღუდვების (მოთხოვნების) დაწესებით, ისევე როგორც თვითნებური ლოგიკური გამონათქვამებით მუშაობა ბუნებრივი ინტერპრეტაციით, იძულების გარეშე მათი ინტერპრეტაცია, როგორც წევრობის ფუნქციები კომპლექტებისთვის ან როგორც მრავალმხრივი. ღირებული ოპერაციები.

მაგრამ მაინც განვასხვავებთ ამ ორ ცნებას, იმის გათვალისწინებით:

§ აბსტრაქტული მონაცემთა ტიპი - გულისხმობს აბსტრაქციის გარკვეულ დონეს, რათა დაფიქსირდეს გამოყენებული (დომენზე ორიენტირებული) მონაცემთა ტიპი, განურჩევლად მისი განხორციელების მეთოდებისა და შესაძლებელია ამ ტიპის მონაცემთა ჩართვა აპლიკაციის ბიბლიოთეკაში, სულ მცირე, კონკრეტული პროგრამული სისტემის სპეციფიკური განვითარება. ADT-ს შეიძლება ჰქონდეს რამდენიმე ალტერნატიული განხორციელება, რომელიც დაფუძნებულია მონაცემთა სხვადასხვა სტრუქტურებზე.

§ მონაცემთა სტრუქტურა უფრო მეტად არის მონაცემთა ორგანიზებისა და მართვის გარკვეული სქემა, რომელიც მოითხოვს შესაბამის სპეციფიკაციებს, როდესაც გამოიყენება კონკრეტულ სიტუაციებში, კონკრეტული პრობლემების გადაჭრისას.

2.1. თანმიმდევრობა.

უსასრულო (სასრული) მიმდევრობა ფორმალურად განისაზღვრება, როგორც ფუნქცია, რომლის დომენი არის დადებითი მთელი რიცხვების სიმრავლე: f(i)= , . ხშირ შემთხვევაში, უფრო მოსახერხებელია მიმდევრობის ნულიდან ინდექსირება; მაშინ დომენი / იქნება არაუარყოფითი მთელი რიცხვების სიმრავლე. ანალოგიურად, ჩვენ განვსაზღვრავთ სასრულ მიმდევრობას ან სიას, როგორც ფუნქციას, რომლის დომენი არის სიმრავლე (1, 2, ..., ).

თანმიმდევრობის კონცეფცია, რომელშიც ელემენტები ერთმანეთს მიჰყვება, ფუნდამენტურია პროგრამირებაში. თანმიმდევრობა ჩნდება კომპიუტერული პროგრამის კოდის სტრიქონ-სტრიქონში, სადაც ბრძანებების თანმიმდევრობა განსაზღვრავს პროგრამის მიერ შესრულებულ მოქმედებებს. ქსელის პაკეტების თანმიმდევრობა წარმოადგენს ელფოსტის შეტყობინებას, რადგან შეტყობინება მხოლოდ მაშინ იქნება მნიშვნელოვანი, თუ პაკეტები მიიღება იმავე თანმიმდევრობით, რომლითაც ისინი იგზავნება. მიმდევრობები წარმოადგენს მნიშვნელოვან ურთიერთობებს ობიექტებს შორის, როგორიცაა "შემდეგი" და "წინა". გარდა ამისა, მიმდევრობები ხშირად გამოიყენება სხვა მონაცემთა სტრუქტურების განსახორციელებლად, ანუ ისინი წარმოადგენენ ბლოკებს, რომლებზეც დაფუძნებულია ასეთი სტრუქტურების დიზაინი.

¨ შესაძლო მნიშვნელობების ნაკრები არის იმავე ტიპის ელემენტების სასრული თანმიმდევრობა.

¨ ოპერაციების ნაკრები:

§ ჩასმაელემენტი თანმიმდევრობით.

§ წაშლაელემენტი თანმიმდევრობიდან.

§ შეხედე- ფუნქცია, რომელიც აბრუნებს მიმდევრობის ელემენტის მნიშვნელობას.

ამ ტიპის ADT-ის ჯიშები განსხვავდება თანმიმდევრობის ელემენტებზე წვდომით და ელემენტების ჩასმა და წაშლის შეზღუდვებით.

ამ ტიპის ADT-სთვის დასტის , რიგში და დეკე Double Ended Queue-დან - ორმხრივი რიგი ) ტიპიური დესტრუქციული კითხვა, იმიტომ ელემენტებზე წვდომა (სამივე ოპერაციისთვის) შემოიფარგლება მიმდევრობის ერთი ბოლოთი და ოპერაცია „სხვა ელემენტზე შეხედვა“ შეიძლება შესრულდეს მხოლოდ ჩარევის ელემენტების მოხსნით. ATD-სთვის ვექტორი (მასივი, ვექტორი), ფაილი (ფაილი) და ხაზოვანი სია წვდომის შეზღუდვა უზრუნველყოფს არა დესტრუქციული კითხვაამიტომ მას განსაკუთრებული მნიშვნელობა აქვს ( წარმოებული) თანმიმდევრობის ძიება ოპერაცია.

მიმდევრობის ელემენტებზე წვდომის შეზღუდვები ბუნებრივად მოქმედებს ძირითადი ოპერაციების სემანტიკაზე. სერიული წვდომაკონცეფციაზე დაყრდნობით მიმდინარე პოზიციადა საშუალებას აძლევს წვდომას (მოძრაობა, ნავიგაცია) მიმდევრობის ერთ (ან ორივე) ბოლოში და მიმდებარე პოზიციაზე (მარცხნივ, მარჯვნივ ან ორივე) მიმდინარეთან შედარებით. ადგილი, სადაც ძირითადი ოპერაციები გამოიყენება ამ შემთხვევაში, ჩვეულებრივ მიბმულია მიმდინარე პოზიციაზე. პირდაპირი (პოზიციური, შემთხვევითი) წვდომაგლობალურ კონცეფციაზე დაყრდნობით პოზიციაელემენტი თანმიმდევრობით და უზრუნველყოფს ელემენტზე პირდაპირ წვდომას, თუ მისი პოზიცია ცნობილია. მაგალითად, ATD-ში დინამიური ვექტორი (დინამიური მასივი, ვექტორი) , პოზიცია არის ელემენტის ინდექსი. მაგრამ სხვა სახის მიმდევრობების სხვა განხორციელებაში, პოზიციის იდენტიფიკატორი შეიძლება განსხვავებულად განხორციელდეს.

ელემენტის "რიცხვის" და "პოზიციის" ცნებები ახლოსაა, მაგრამ შეიძლება არ ემთხვეოდეს:

§ ნომერი- ეს არის ელემენტის რეალური სერიული ნომერი თანმიმდევრობით. მაგრამ ელემენტის სერიული ნომერი იცვლება წინა ელემენტების ჩასმის და წაშლის ოპერაციების შედეგად, ეს ქმნის უამრავ უხერხულობას მიმდევრობის ელემენტების იდენტიფიცირებაში.

§ თანამდებობა- რიგის მსგავსია იმ გაგებით, რომ მოცემული პოზიციის ელემენტისთვის ის საშუალებას გვაძლევს ვისაუბროთ მიმდევრობის წინა და მომდევნო ელემენტებზე (და მათ პოზიციაზე). მაგრამ ელემენტის პოზიციის მნიშვნელობა არ იცვლება წინა ელემენტის ჩასმისა და წაშლის შედეგად, ამიტომ ელემენტის პოზიციის მნიშვნელობა შეიძლება შეინახოს და გამოიყენოს ამ ელემენტზე წვდომისათვის მომავალში. მაგალითად, მიმდევრობის მიბმული სიის განხორციელებაში, ცნება „პოზიცია“ შეიძლება იყოს წარმოდგენილი ელემენტის ინდიკატორით, ხოლო სხვა განხორციელებებში შეიძლება წარმოდგენილი იყოს სხვა სახის იდენტიფიკატორით, რომელიც სპეციალურად მხარდაჭერილია იმპლემენტაციის მიერ.

ADT თანმიმდევრობისთვის ფორმის დამატებითი ოპერაციები საინტერესოა: ორი მიმდევრობის შეერთება, ორ თანმიმდევრობად გაყოფა. მაგალითად, ATD-ში სიმებიანი ამ ტიპის ოპერაცია რეალურად ძირითადია.

სხვადასხვა ტიპის ADT "Sequence"-სთვის მიიღწევა სხვადასხვა ოპერაციების განხორციელების განსხვავებული ეფექტურობა. მაგალითად, თუ დანერგვა გვთავაზობს ეფექტურ პირდაპირ წვდომას მიმდევრობის ელემენტებზე, მაშინ დიდი ალბათობით, მიმდევრობის შუაში ჩასმის ოპერაციის შესრულების დრო სასურველს ტოვებს. ADT მიმდევრობის სხვადასხვა ტიპები (და განხორციელებები) პროგრამისტს წარუდგენენ სხვადასხვა წინადადებებს ოპერაციების შემადგენლობისა და მათი განხორციელების ეფექტურობის შესახებ. ამიტომ, პროგრამირების პრაქტიკაში, როგორც წესი, უფრო საინტერესოა არა იმდენად ამ (ისევე როგორც სხვა) ADT-ების უნივერსალური ვერსიები, არამედ სპეციალიზებული და პროგრამისტმა უნდა გააკეთოს შესაბამისი არჩევანი მათი გამოყენების გათვალისწინებით. საგნობრივ სფეროში პრობლემების გადაჭრაში.

2.2. კომპლექტი.

¨ შესაძლო მნიშვნელობების სიმრავლე არის იმავე ტიპის ელემენტების სასრული ნაკრები.

¨ ოპერაციების ნაკრები:

§ ჩასმაელემენტი ნაკრებში.

§ წაშლაელემენტი ნაკრებიდან.

§ ეკუთვნის– ფუნქცია, რომელიც აბრუნებს true-ს, თუ ელემენტი ეკუთვნის სიმრავლეს.

კლასიკური მათემატიკის ასეთი ფუნდამენტური კონცეფციისთვის ბუნებრივია ოპერაციების ნაკრების გაფართოება სტანდარტულ კლასიკურზე. მაგრამ პროგრამირების მრავალი პრაგმატული მიზეზის გამო, ზოგადი (უნივერსალური) ტიპის ასეთი ADT შეზღუდული ინტერესია. მაგალითად, გადაკვეთის კომპლექტების გაერთიანების ოპერაციის ჩართვა მოითხოვს განხორციელების დროს გადაკვეთის ელემენტების ამოღებას. ამან შეიძლება მნიშვნელოვნად გაართულოს ამ ოპერაციის განხორციელება. მეორეს მხრივ, დუბლიკატების არსებობა შეიძლება არ იყოს კრიტიკული ამ შემთხვევაში პრობლემის გადასაჭრელად, ADT-ები მრავალსახეობაა. კომპლექტის კონცეფციის ფუნდამენტური მნიშვნელობა, რა თქმა უნდა, გამოიხატება ამ ძირითადი ADT "Set"-ის სპეციალიზებული გაფართოებების მდიდარი ნაკრების არსებობით, რომლებიც ფართოდ გამოიყენება პროგრამირების პრაქტიკაში, როგორც ამ ხელსაწყოების ძლიერი ექსპრესიული ძალის გამო. პრობლემის მოდელებისა და მათი გადაჭრის ალგორითმების შემუშავებაში და ამ ATD ეფექტური განხორციელების მეთოდების არსებობის გამო.

ADT "Multiple"-ს სპეციალიზებული გაფართოებები განიხილება სხვადასხვა მიმართულებით:

§ „კომპლექტის“ ცნებასთან ახლოს არის ცნება „კომპლექტი“. კომპლექტი (ჩანთა, MultiSet) – ისევე როგორც ნაკრები არის ელემენტების ოჯახი, მიუხედავად იმისა, მითითებულია თუ არა ელემენტებზე თანმიმდევრობის მიმართება, მაგრამ სიმრავლის ელემენტები შეიძლება განმეორდეს მნიშვნელობით. ზოგადად რომ ვთქვათ, ნაკრები შეიძლება წარმოდგენილი იყოს როგორც კომპლექტი, მაგალითად, რომლის ელემენტებია [ელემენტის მნიშვნელობა, სიმრავლეში გამოვლინებების რაოდენობა] წყვილი.

§ პრაქტიკულ გამოყენებაში ხშირად იდენტიფიცირებულია კომპლექტების ელემენტები, ე.ი. ელემენტი არის წყვილი [ელემენტის გასაღები, ელემენტის რეალური მნიშვნელობა], ლექსიკონი ADT არის ADT ნაკრების ასეთი სპეციალიზებული გაფართოების მაგალითი. სასურველი შემთხვევაა როცა ელემენტის გასაღები უნიკალურია, ე.ი. ნაკრები არ შეიძლება შეიცავდეს ორ ელემენტს ერთი და იგივე გასაღებით. მაგრამ შესაძლებელია გამოყენებული გასაღები არა უნიკალური იყოს, ე.ი. ელემენტის რეალური მნიშვნელობის ორაზროვნად იდენტიფიცირება. ზოგადად რომ ვთქვათ, კომპლექტი (და კოლექცია) არაუნიკალური გასაღებით შეიძლება წარმოდგენილი იყოს როგორც ნაკრები უნიკალური გასაღებით ელემენტის მნიშვნელობის ტიპის გართულებით, მაგალითად, წინა ტიპის მნიშვნელობების სიმრავლის გათვალისწინებით ( იგივე გასაღები), როგორც ელემენტის მნიშვნელობა.

§ ბუნებრივია, რომ დააკონკრეტოთ შეკვეთის მიმართება, ნაწილობრივი ან წრფივი, კომპლექტზე, ADT "რიგი პრიორიტეტით" არის "Set" ADT-ის ასეთი სპეციალიზებული გაფართოების მაგალითი. ანალოგიურად, პრობლემის გადაჭრის საგნობრივ არეალში, სხვა ურთიერთობები შეიძლება იყოს საინტერესო.

§ მათემატიკაში ფუნდამენტური პოზიცია უკავია ეკვივალენტურობის მიმართების ცნებას და, შესაბამისად, სიმრავლის ეკვივალენტურ კლასებად დაყოფის კონცეფციას. ბუნებრივია, ეს კონცეფცია ფართოდ გამოიყენება საგნობრივ სფეროებში პრობლემების გადაჭრის მოდელების პრაქტიკულ შემუშავებაში. ADT „განაწილებული კომპლექტების ოჯახი“ (Disjoint Sets, Partitions, Partitions) არის ADT „Set“-ის შესაბამისი სპეციალიზებული გაფართოების მაგალითი.

"Set" ADT-ის სპეციალიზებული გაფართოებისთვის, ზემოაღნიშნული ოპერაციები ბუნებრივად დახვეწილია და ჩნდება ახალი საინტერესო ოპერაციები.

2.3. ლექსიკონი (რუკა), სხვა სახელია ასოციაციური მასივი.

¨ შესაძლო მნიშვნელობების სიმრავლე არის იგივე ტიპის, ტიპის ელემენტების სასრული ნაკრები, სადაც Key არის ელემენტის უნიკალური გასაღები, მნიშვნელობა არის თავად მნიშვნელობა.

¨ ოპერაციების ნაკრები:

§ ჩასმაელემენტი (გასაღებით) ნაკრებში.

§ წაშლაელემენტი (გასაღებით მითითებული) ნაკრებიდან.

§ ელემენტის მოძებნა– ფუნქცია, რომელიც აბრუნებს ელემენტის მნიშვნელობას გასაღების მიხედვით ან „ცარიელ“ მნიშვნელობას, თუ ასეთი გასაღების მქონე ელემენტი არ არის ნაკრებში.

ADT "ლექსიკონი" არის (შენახული) რუკების (მნიშვნელობების გასაღებები) კონცეფციის სპეციალიზებული ვერსია, რომელიც ფართოდ გამოიყენება პრაქტიკულ პროგრამირებაში. მაგრამ ზოგიერთი საგნისთვის, შეიძლება უფრო მოსახერხებელი იყოს ADT-ის დიზაინი "რუქირება" , უფრო ახლოს კლასიკურ მათემატიკურ განმარტებასთან.

2.4. პრიორიტეტული რიგი.

¨ შესაძლო მნიშვნელობების ნაკრები არის იგივე ტიპის ელემენტების სასრული ნაკრები. სიმრავლეებზე (შესაძლებელ მნიშვნელობებზე) მითითებულია წრფივი რიგის მიმართება, რომელიც ინტერპრეტირებულია, როგორც ელემენტების შედარება პრიორიტეტის მიხედვით. პრიორიტეტის დონე შეიძლება განისაზღვროს, როგორც ელემენტის მნიშვნელობის კომპონენტი ან გამოითვალოს ელემენტის მნიშვნელობის მოცემული ფუნქციით.

გაითვალისწინეთ, რომ შესაძლო მნიშვნელობების ასეთი ნაკრები ასევე შეიძლება განიმარტოს, როგორც მიმდევრობების ნაკრები (მისი ელემენტების ჩამონათვალი მოცემული ხაზოვანი თანმიმდევრობით).

¨ ოპერაციების ნაკრები:

§ ჩასმაელემენტი (წრფივად დალაგებული) კომპლექტში.

§ ამოიღეთ მინიმალურიელემენტი ნაკრებიდან.

§ იპოვეთ მინიმალური– ფუნქცია, რომელიც აბრუნებს ნაკრების მინიმალური ელემენტის მნიშვნელობას.

ასევე განიხილება ამ ADT-ის (მნიშვნელოვანი) ვარიაციები დამატებითი ოპერაციებით:

§ ელემენტის მოცემული მნიშვნელობის (პრიორიტეტის) მიხედვით რიგის ორად გაყოფა - ქვედა პრიორიტეტის მქონე ელემენტების რიგში და დანარჩენის რიგში.

§ შეაერთეთ ორი რიგი, რომელთაგან ერთს აქვს ყველა ელემენტი, რომელსაც აქვს უფრო მაღალი პრიორიტეტი, ვიდრე მეორე რიგის ყველა ელემენტი, ერთ პრიორიტეტულ რიგში, თავდაპირველი თანმიმდევრული რიგების შენარჩუნების გარეშე.

§ გააერთიანეთ ორი არაერთგვაროვანი მოწესრიგებული ნაკრები (ორი ასეთი რიგის შერწყმა) ერთ მოწესრიგებულ ნაკრებში (ერთი რიგი პრიორიტეტით), ასევე ორიგინალური შერწყმის გარეშე.

§ მოცემული ელემენტის მნიშვნელობის (პრიორიტეტის) შემცირება.

§ ამოიღეთ (შემთხვევით) მითითებული ელემენტი ნაკრებიდან.

2.5. Disjoint კომპლექტები, ტიხრები, ტიხრები.

¨ შესაძლო მნიშვნელობების სიმრავლე არის სასრული სიმრავლეები (ოჯახები) დაშლილი სასრული სიმრავლეების. გამოვლენილია ოჯახის ელემენტები, ე.ი. ოჯახში თითოეულ კომპლექტს აქვს (უნიკალური) სახელი.

¨ ოპერაციების ნაკრები:

§ შერწყმა (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-ის ეფექტური განხორციელებისთვის და მთლიანად პრობლემის გადაჭრის ალგორითმისთვის. მაგრამ ასეთ კონტექსტში, მათი წარმოდგენის ხერხიც და ოპერაციების ნაკრები ამ ხეებთან, გრაფიკებთან და ქსელებთან, ბუნებრივად სპეციალიზირებულია კონკრეტული კონტექსტის შესაბამისად.

რა არის აბსტრაქტული მონაცემთა ტიპი? აბსტრაქტული კლასები და კლასის წევრები. სპეციალური ტიპის ნაკრები

შეატყობინეთ შეცდომას

ტექსტი, რომელიც გაეგზავნება ჩვენს რედაქტორებს:

თქვენი კომენტარი (სურვილისამებრ):