DOUG LLOYD: ასე CS50, ჩვენ დაფარული ბევრი სხვადასხვა მონაცემთა სტრუქტურები, არა? ჩვენ ვნახეთ კოლექტორები, და უკავშირდება სიები და hash მაგიდები, და ცდილობს, stacks და რიგები. ჩვენ ასევე ვისწავლოთ ცოტა ხეები და heaps, მაგრამ რეალურად ეს ყველაფერი უბრალოდ დასრულდება მიმდინარეობს ვარიაციები თემაზე. მართლაც ეს სახის ოთხი ძირითადი იდეები რომ ყველაფერი შეიძლება მოვხარშოთ ქვემოთ. მასივები, დაკავშირებული სიები, hash მაგიდები და ლელო. და როგორც მე ვთქვი, ვარიაციები, მათ შორის, მაგრამ ეს არის საკმაოდ ბევრი ვაპირებ ყველაფერი ჩვენ ვაპირებთ, რომ გაიგო შესახებ ამ კლასში თვალსაზრისით C. მაგრამ როგორ გავაკეთოთ ეს ყველა ღონისძიება, არა? ჩვენ ვისაუბრეთ დადებითი და უარყოფითი მხარეები თითოეული ცალკე videos მათ, მაგრამ არსებობს ბევრი ნომრები მიღების დააგდეს გარშემო. არსებობს ბევრი საერთო აზრები მიღების დააგდეს გარშემო. შევეცადოთ და კონსოლიდაცია იგი მხოლოდ ერთ ადგილას. მოდით მოხდეს დადებითი წინააღმდეგ უარყოფითი, და მიიჩნევს, რომელიც მონაცემები სტრუქტურა შეიძლება იყოს უფლება მონაცემები სტრუქტურა თქვენი კონკრეტული სიტუაცია, ნებისმიერი სახის მონაცემები, თქვენ შენახვას. თქვენ არ აუცილებლად ყოველთვის უნდა გამოიყენოთ სუპერ სწრაფი ჩასმა, წაშლა, და საძიებელი საქართველოს trie თუ თქვენ ნამდვილად არ აინტერესებს ჩასმა და წაშლა ძალიან ბევრი. თუ თქვენ უბრალოდ სწრაფად შემთხვევითი ხელმისაწვდომობა, იქნებ მასივი უკეთესია. მოდით გამოიხადოს რომ. მოდით ვისაუბროთ თითოეული ოთხი ძირითადი სახის მონაცემთა სტრუქტურები რომ ჩვენ ვისაუბრეთ და უბრალოდ, როდესაც ისინი შეიძლება იყოს კარგი, და როდესაც ისინი შეიძლება არ იყოს კარგი. მოდით დავიწყოთ მასივები. ასე რომ, ჩასმა, რომ სახის ცუდი. 

Insertion ბოლოს მასივი OK, თუ ჩვენ ვაშენებთ მასივი, როგორც ჩვენ მივდივართ. მაგრამ, თუ ჩვენ უნდა ჩაწეროთ ელემენტების შევიდა შუა, ვფიქრობ, უკან ჩასმა დალაგების, იქ არის ბევრი გადასვლის ჯდება ელემენტს არსებობს. ასე რომ, თუ ჩვენ ვაპირებთ ჩადეთ სადმე, მაგრამ ბოლოს მასივი, ეს, ალბათ, არც ისე დიდი. 

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

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

კოლექტორები ასევე შედარებით ადვილი დასალაგებლად. ყოველ დროს, ჩვენ ვისაუბრეთ დახარისხება ალგორითმი, როგორიცაა შერჩევის დალაგების, Insertion დალაგების, bubble sort, შერწყმა დალაგების, ჩვენ ყოველთვის გამოიყენება კოლექტორები უნდა გავაკეთოთ, რადგან მასივები საკმაოდ ადვილი სახის, შედარებით მონაცემთა სტრუქტურები ჩვენ ვნახეთ ჯერჯერობით. 

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

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

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

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

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

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

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

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

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

ახლა, ძიება, სადაც ყველაფერი კიდევ ცოტა უფრო რთული. ეს საშუალოდ უკეთესი ვიდრე დაკავშირებული სიები. თუ თქვენ იყენებთ chaining, თქვენ ჯერ კიდევ აქვს უკავშირდება სია, რაც იმას ნიშნავს, თქვენ გაქვთ ძიება აზიანებს უკავშირდება სიაში. იმის გამო, რომ თქვენ მიღების თქვენი უკავშირდება სიაში და გაყოფის იგი 100-ზე მეტი ან 1000 ან n ელემენტების თქვენი hash მაგიდა, თქვენ დაკავშირებული სიები ყველა ერთი nth ზომა. ისინი ყველა არსებითად პატარა. თქვენ არ n დაკავშირებული სიები ნაცვლად ერთი უკავშირდება სიაში ზომა n. 

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

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

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

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

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

მინუსი, რა თქმა უნდა, არის ის, რომ trie, სწრაფად ხდება დიდი. ყოველი გადაკვეთაზე წერტილი, თქვენ შეიძლება ჰქონდეს თუ თქვენი გასაღები შედგება ციფრები, თქვენ გაქვთ 10 სხვა ადგილებზე შეგიძლიათ გადასვლა, რომელიც იმას ნიშნავს, რომ ყველა კვანძის შეიცავს ინფორმაციას მონაცემები გსურთ შეინახოთ რომ კვანძის, პლიუს 10 მითითებას. რაც, CS50 IDE, არის 80 ბაიტი. ასე რომ, ეს მინიმუმ 80 ბაიტი ყველა კვანძის რომ თქვენ შექმნათ, და ეს არ არის კი დამთვლელი მონაცემები. და თუ თქვენი კვანძების წერილების ნაცვლად ციფრები, ახლა თქვენ გაქვთ 26 მითითებას ყველა ადგილმდებარეობა. და 26-ჯერ 8 არის ალბათ 200 ბაიტი, ან რაღაც მსგავსი. და თქვენ უნდა კაპიტალი და ამას თქვენ შეგიძლიათ ვხედავ, სადაც მე ვაპირებ ამ, არა? შენი კვანძების შეიძლება მიიღოს მართლაც დიდი, და ასე trie თავად, საერთო ჯამში, შეიძლება ნამდვილად დიდი, ძალიან. ასე რომ, თუ სივრცეში არის მაღალი პრემია თქვენი სისტემის, trie, არ შეიძლება იყოს სწორი გზა წასვლა, მიუხედავად იმისა, რომ მისი სხვა სარგებელი მოვიდეს პიესა. მე Doug Lloyd. ეს არის CS50.