; პითონის ენის გამოყენებით სიის შექმნა - IT Academy STEP Tbilisi პითონის ენის გამოყენებით სიის შექმნა - IT Academy STEP Tbilisi

თბილისი, ჯანო ბაგრატიონის 6

პითონის ენის გამოყენებით სიის შექმნა

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

რას გულისხმობს მიბმული სიები?

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

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

ცალკე მიბმული სია და მისი განხორციელება პითონის ენის გამოყენებით

ცალკე მიბმული სია აგრეთვე არის კვანძების კომპლექტი და აქვს საწყისი წერტილი სახელწოდებით HEAD და საბოლოო წერტილი სახელწოდებით TAIL.

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

TAIL განსაზღვრავს ბოლო კვანძს ცალკე მიბმულ სიაში და ამ შემთხვევაში კვანძის მითითების ნაწილი მიუთითებს არაფერზე ან ნულზე.

ასე გამოიყურება ცალკე მიბმული სია დიაგრამაში. თითოეულ კვანძს აქვს გასაღები/მნიშვნელობა, რომლებიც არის სტრიქონები ზემოთ მოცემულ შემთხვევაში და მითითება ანუ მომდევნო პოინტერი, რომელიც მიუთითებს მომდევნო ელემენტზე. ძირითადად, პირველი კვანძი არის head-ი და ბოლო კვანძი არის tail-ი სიაში. ერთი კვანძიდან მეორეში გადასვლას სიაში traversal ჰქვია.

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

ძირითადი ოპერაციები ცალკე მიბმულ სიაში

ძირითადად არსებობს ორი ოპერაცია, რომლებსაც ჩვეულებრივ ვასრულებთ ცალკე მიბმულ სიასთან.

1 Push ანუ ახალი ელემენტის ჩასმა

2 Pop ანუ ელემენტის წაშლა/გაუქმება სიიდან.

ოპერაცია PUSH

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

1 ელემენტის ჩასმა დასაწყისში.

2 ელემენტის ჩასმა ბოლოში.

ელემენტის ჩასმა დასაწყისში

ალგორითმი

1 ვქმნით ახალ კვანძს

2 მას ამატებს ახალ ელემენტს

3 სიმრავლე არის მინიშნების ნაწილი მიმდინარე head-ზე

4 ვაწესებთ სიის head-ს, რომ მივუთითოთ ახალ კვანძზე

ელემენტის ჩასმა ბოლოში

ალგორითმი

1 ვქმნით ახალ კვანძს

2 ადგენს მის მინიშნების ნაწილს ნულზე ან არაფერზე

3 ადგენს tail კვანძის მინიშნების ნაწილს, რომ განსაზღვროს ახლად შექმნილი კვანძის მნიშვნელობა

4 განაახლებს tail მინიშნებას ამ ახალ კვანძზე

ოპერაცია POP

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

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

ცალკე მიბმული სიის დადებითი და უარყოფითი მხარეები

დადებითი მხარეები

მათ აქვთ მუდმივი დრო ჩასმისთვის და წაშლისთვის

მისი ზომა განსაზღვრული არ არის, ის მოქნილია

უარყოფითი მხარეები

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

კოდი

შეგიძლიათ გამოიყენოთ ნებისმიერი ტექსტის რედაქტორი და სცადოთ ეს კოდი.

მიიღეთ საჭირო ცოდნა

შემოგვიერთდით მსოფლიო ბრენდ  IT აკადემია STEP-ში!

თბილისი,
ჯანო ბაგრატიონი #6
+995 (32) 215-55-51
+995 (32) 215-50-05

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

რეგისტრაცია

სახელი, გვარი*
ტელეფონი*
E-mail*
სად გაეცანით ინფორმაციას ღია კარის დღის შესახებ?*


ახალი ამბები