[Powered by Google Translate] პროგრამირებაში, ჩვენ ხშირად უნდა წარმოადგინოს სიები ღირებულებების, როგორიცაა სახელები სტუდენტების სექციაში ან მათი ბალით უკანასკნელი ვიქტორინა. 

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

როდესაც ვაცხადებთ, მათ, ჩვენ საჭირო ვთქვა მდე წინა რამდენად დიდი ისინი, რომ არის, რამდენი ელემენტები ისინი შენახვა შეუძლია და რამდენად დიდი ეს ელემენტები არიან, რაც განპირობებულია მათი ტიპის. მაგალითად, int arr (10) შენახვა შეუძლია 10 ელემენტი რომლებიც ზომა int. 

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

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

აქ ზოგიერთი C კოდი ძალიან მარტივია უკავშირდება სიაში რიცხვებით. თქვენ ხედავთ, რომ ჩვენ წარმოდგენილია თითოეული კვანძის სიაში როგორც struct რომელიც შეიცავს 2 რამ, მთელი რიცხვი შესანახად მოუწოდა 'Val' და ლინკი შემდეგი კვანძის სიაში რომელსაც ჩვენ წარმოვადგენთ როგორც კურსორი სახელწოდებით "შემდეგი". ამ გზით, ჩვენ შეგიძლიათ აკონტროლოთ მთელი სია მხოლოდ ერთი მომცეთ 1st კვანძში, და მაშინ ჩვენ შეგვიძლია დაიცვას შემდეგი პოინტერები to 2nd კვანძში, მე -3 კვანძში, მე -4 კვანძში, და ასე შემდეგ, სანამ არ მივიღებთ, რათა სიის ბოლოში. 

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

გარდა ამისა, ჩვენ არ გვაქვს იმის თქმა up წინა რამდენად დიდი უკავშირდება სიაში იქნება გზა ჩვენ არ უკავშირდება სტატიკური მასივები, მას შემდეგ, რაც ჩვენ შეგვიძლია შევინარჩუნოთ დასძინა კვანძების to სია რადგან არსებობს სივრცე სადღაც მეხსიერების ახალი კვანძების. ამიტომ, დაკავშირებული სიები ადვილად ზომის შეცვლა დინამიურად ვითარდება. ამბობენ, მოგვიანებით პროგრამა გვჭირდება დაამატოთ კვანძების ჩვენს სიაში. ჩასასმელად ახალი კვანძის ჩვენს სიაში on the fly, ყველა ჩვენ უნდა გავაკეთოთ არის გამოყოფს მეხსიერებას, რომ კვანძის, plop მონაცემთა ღირებულება, და შემდეგ განათავსონ, სადაც ჩვენ გვინდა მიერ მორგება შესაბამისი მითითებები. 

მაგალითად, თუ გვინდოდა განათავსებს კვანძის შორის მე -2 და მე -3 კვანძების სიის,  ჩვენ არ უნდა გადავიდეთ მე -2 ან მე -3 კვანძების ყველა. Say ჩვენ ჩასმა ამ წითელი კვანძში. ყველა ჩვენ გვინდა უნდა გავაკეთოთ არის ახალი კვანძის მომდევნო მაჩვენებელი უნდა აღვნიშნო, რომ მე -3 კვანძში და შემდეგ rewire -2 კვანძის მომდევნო მაჩვენებელი უნდა აღვნიშნო, რომ ჩვენს ახალ კვანძში. ასე რომ, ჩვენ შეიძლება შემცირება ჩვენი სიები on the fly რადგან ჩვენი კომპიუტერის მონაცემები არ დაეყრდნონ ინდექსირებას, არამედ on აკავშირებს გამოყენებით პოინტერები შესანახად მათ. 

თუმცა, მინუსი of უკავშირდება სიები არის ის, რომ განსხვავებით სტატიკური მასივი, კომპიუტერი არ შეუძლიათ უბრალოდ გადადით შუა სიაში. მას შემდეგ, რაც კომპიუტერი ეწვევა თითოეული კვანძის წელს უკავშირდება სია მისაღებად შემდეგი ერთი, ის აპირებს დასჭირდეს, რათა იპოვოს კონკრეტული კვანძში ვიდრე ეს იქნებოდა მასივი. To traverse მთელი სია დრო სჭირდება პროპორციული to სიგრძეზე სია, ან O (N) in asymptotic ნოტაცია. საშუალოდ, მიაღწია ნებისმიერი კვანძის ასევე დრო სჭირდება პროპორციული n. 

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

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

ასე რომ, ჩვენ გვჭირდება მაჩვენებელი სპეციალურად გასვლის რაც ჩვენ მოვუწოდებთ "crawler. ' ეს იქნება სეირნობისას მეშვეობით ყველა ელემენტების სია შემდეგი ჯაჭვის შემდეგი პოინტერები. ყველა ჩვენ ინახება არის მომცეთ 1st კვანძში, ან "ხელმძღვანელი" უკავია. უფროსი მიუთითებს 1st კვანძში. ეს ტიპის კურსორი-to-node. 

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

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

ასე რომ, თუ crawler → მომდევნო არის null, გვახსოვდეს, რომ arrow სინტაქსი არის მალსახმობი ამისთვის dereferencing მომცეთ struct, მაშინ წვდომის მისი შემდეგი სფეროში ექვივალენტი უხერხულ: (* Crawler). შემდეგი. ერთხელ ჩვენ ნაპოვნი ბოლო კვანძის, ჩვენ გვინდა ბეჭდვა crawler → Val, ღირებულების მიმდინარე კვანძის რაც ჩვენ ვიცით არის ბოლო. წინააღმდეგ შემთხვევაში, თუ ჩვენ არა ვართ ჯერ კიდევ გასული კვანძის სიაში, ჩვენ უნდა გადავიდეთ შემდეგ კვანძის სიაში და შემოწმება თუ ეს ბოლო ერთი. ამისათვის ჩვენ უბრალოდ მითითებული ჩვენი crawler მაჩვენებელი უნდა აღვნიშნო, რომ მიმდინარე კვანძის მომდევნო ღირებულება, რომ არის, მომდევნო კვანძის სიაში. ეს კეთდება მიიღწევა crawler = crawler → მომდევნო. მაშინ ჩვენ ვიმეორებ ეს პროცესი, რომელზეც მარყუჟი მაგალითად, სანამ ჩვენ ბოლო კვანძში. ასე მაგალითად, თუ crawler იყო მიუთითებს ხელმძღვანელი, ჩვენ დავსახეთ crawler აღვნიშნო, რომ crawler → მომდევნო, რაც არის იგივე, რაც შემდეგი სფეროში 1st კვანძში. ასე რომ, ახლა ჩვენი crawler არის მიუთითებს -2 კვანძში, და, კიდევ ერთხელ, ჩვენ ვიმეორებთ ამ მარყუჟის, სანამ ჩვენ ნაპოვნი ბოლო კვანძში, რომელიც, სადაც კვანძის მომდევნო მაჩვენებელი არის მიუთითებს null. და იქ არის ის, ჩვენ ნაპოვნი ბოლო კვანძის სიაში და ბეჭდვა მისი ღირებულება, ჩვენ უბრალოდ გამოიყენოთ crawler → Val. 

Traversing ასე არ არის ცუდი, მაგრამ რაც შეეხება ჩასმა? Lets ამბობენ გვინდა ჩადეთ მთელი შევიდა მე -4 პოზიცია წელს მთელი სია. სწორედ შორის მიმდინარე მე -3 და მე -4 კვანძების. ერთხელ, ჩვენ უნდა traverse სიაში მხოლოდ კიდევ მე -3 ელემენტს, ერთი ჩვენ ჩასმა შემდეგ. ასე რომ, ჩვენ შევქმნით crawler მაჩვენებელი კვლავ traverse სია, შეამოწმეთ თუ ჩვენი უფროსი მაჩვენებელი არის null, და თუ ეს ასე არ არის, აღვნიშნო ჩვენი crawler მაჩვენებელი სათავეში კვანძში. ასე რომ, ჩვენ დროს 1 ელემენტს. ჩვენ უნდა წავიდეთ წინ კიდევ 2 ელემენტები სანამ ჩვენ ჩადეთ, ამიტომ ჩვენ შეგვიძლია გამოვიყენოთ ამისთვის loop int i = 1; I <3 მე + + და თითოეულ iteration of მარყუჟის, წინასწარ ჩვენი crawler მაჩვენებელი ნაბიჯია მიერ 1 კვანძში მიერ შემოწმების თუ მიმდინარე კვანძის მომდევნო ველი null, და თუ ეს ასე არ არის, გადავიდეს ჩვენი crawler მომცეთ შემდეგი კვანძში მიიღწევა ის ტოლია მიმდინარე კვანძის მომდევნო მაჩვენებელი. ასე რომ, რადგან ჩვენი ამისთვის loop ამბობს გავაკეთოთ, რომ ორჯერ, ჩვენ მიაღწია მე -3 კვანძში, და კიდევ ჩვენი crawler მაჩვენებელმა მიაღწია კვანძის შემდეგ რაც გვინდა, რომ ჩადეთ ჩვენი ახალი რიცხვი, როგორ უნდა მართლაც ჩასმა? 

ისე, ჩვენი ახალი რიცხვი უნდა იყოს ჩასმული შევიდა სიაში როგორც ნაწილი საკუთარი კვანძის struct, რადგან ეს მართლაც თანმიმდევრობა კვანძების. ასე რომ, მოდით ახალი მომცეთ კვანძში ე.წ. "new_node, ' და ვაყენებთ მას აღვნიშნო ხსოვნას, რომ ჩვენ ახლა გამოყოფს on ბევრი ამისთვის კვანძის თავად, და რამდენი მეხსიერება გვჭირდება გამოყოფას? ისე, ზომა კვანძში, და ჩვენ გვინდა მითითებული მისი Val ველის მთელი რიცხვი, რომ ჩვენ გვინდა ჩადეთ. ვთქვათ, 6. ახლა, node შეიცავს ჩვენი მთელი მნიშვნელობა. ეს ასევე კარგი პრაქტიკის ინიციალიზაცია ახალი კვანძის მომდევნო სფეროში უნდა აღვნიშნო, რომ null, მაგრამ ახლა რა ხდება? 

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

ასე რომ, გამარტივება ამ, ვთქვათ, რომ ჩვენი პირველი 4 კვანძების ეწოდება, B, C, და D, ერთად ისრებით წარმოადგენს ჯაჭვის პოინტერები რომ დააკავშირებს კვანძების. ამიტომ, ჩვენ უნდა ჩადეთ ჩვენი ახალი კვანძში შორის კვანძების C და დ ეს კრიტიკული ამას უფლება, და მე შენ გაჩვენებ, რატომ. 

მოდით შევხედოთ არასწორი გზა ამის პირველი. Hey, ჩვენ ვიცით, ახალი კვანძში უნდა მოვიდეს შემდეგ C, მოდით მითითებული C მომდევნო მაჩვენებელი უნდა აღვნიშნო, რომ new_node. ყველა უფლება, როგორც ჩანს okay, ჩვენ უბრალოდ უნდა დაასრულოს დღემდე მიერ მიღების ახალი კვანძის მომდევნო მაჩვენებელი წერტილი D, მაგრამ დაველოდოთ, როგორ შეგვიძლია გავაკეთოთ, რომ? ერთადერთი, რაც შეიძლება გვითხრათ, სადაც D იყო, იყო შემდეგი მაჩვენებელი ადრე შენახული C, მაგრამ ჩვენ უბრალოდ rewrote რომ მომცეთ უნდა აღვნიშნო, რომ ახალი კვანძის, ამიტომ ჩვენ აღარ აქვს რაიმე ნახავ სადაც D არის მეხსიერება, და ჩვენ დავკარგეთ დანარჩენი სიაში. არ არის კარგი ყველა. 

ასე რომ, როგორ უნდა გავაკეთოთ ეს უფლება? პირველი, აღვნიშნო ახალი კვანძის მომდევნო კურსორი at დ ახლა, როგორც ახალი კვანძის და C-ს შემდეგი პოინტერები მათ მიუთითებს იმავე კვანძში, D, მაგრამ ეს ჯარიმა. ახლა ჩვენ შეგვიძლია აღვნიშნოთ C მომდევნო კურსორი ახალ კვანძში. ასე რომ, ჩვენ გავაკეთეთ ეს დაკარგვის გარეშე ნებისმიერი მონაცემები. კოდის, C არის მიმდინარე კვანძის რომ გასვლის მაჩვენებელი crawler არის მიუთითებს, და D წარმოდგენილია კვანძის მიუთითა მიერ მიმდინარე კვანძის მომდევნო სფეროში, ან crawler → მომდევნო. ასე რომ, ჩვენ პირველად მითითებული ახალი კვანძის მომდევნო მაჩვენებელი უნდა აღვნიშნო, რომ crawler → მომდევნო, ანალოგიურად ჩვენ განაცხადა new_node მომდევნო მაჩვენებელი უნდა აღვნიშნავთ, რომ D ში ილუსტრაცია. მაშინ ჩვენ შეგვიძლია მითითებული მიმდინარე კვანძის მომდევნო მაჩვენებელი ახალ კვანძში, ისევე როგორც ჩვენ გვქონდა ლოდინი აღვნიშნო C-დან new_node წელს ნახაზი. ახლა ყველაფერი იმისათვის, და ჩვენ არ დაუკარგავს აკონტროლოთ ნებისმიერი მონაცემების, და ჩვენ შეგვეძლო მხოლოდ გამყარებაში ჩვენი ახალი კვანძის შუა სია გარეშე აღდგენის მთელი რამ ან თუნდაც გადავიდა ნებისმიერი ელემენტები გზა ჩვენ არ მოუხდა ერთად ფიქსირებული სიგრძე მასივი. 

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

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

ჩემი სახელი არის ჯექსონის Steinkamp, ​​ეს CS50.