[მუსიკალური სათამაშო] დინამიკები 1: ყველა უფლება. ყველას მივესალმებით თავში მონაკვეთზე. ვიმედოვნებ, რომ ყველა წარმატებით ამოღებული თქვენს ვიქტორინა გასულ კვირას. მე ვიცი, რომ ცოტა გიჟები დროს. როგორც მე ამბობდა ადრე, თუ თქვენ ფარგლებში სტანდარტული გადახრა, ნამდვილად არ აღელვებს, განსაკუთრებით ნაკლებად კომფორტული მონაკვეთზე. ეს არის ის, სადაც თქვენ უნდა იყოს. თუ თქვენ არ დიდი, მაშინ გასაოცარია. Kudos თქვენ. და თუ თქვენ თავს თქვენ უნდა ცოტა მეტი დახმარება, გთხოვთ შეგიძლიათ მიღწევა out ნებისმიერ TFs. ჩვენ ყველანი აქ, რათა დაეხმაროს. 

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

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

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

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

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

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

ასე რატომ ვირჩევთ უკავშირდება სიაში მეტი მასივი? რა განასხვავებს მათ? დიახ? 

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

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

დინამიკები 1: Right. ასე მასივების 

აუდიტორია: [INAUDIBLE]. 

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

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

და ამ შემთხვევაში, ეს არის ზოგიერთი კვანძის რომ გამართავს რამდენიმე რიცხვი. და მერე რა არის მეორე ნაწილი აქ? ვინმე? 

აუდიტორია: [INAUDIBLE]. 

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

ყველა უფლება, ასე ძიება, რადგან ჩვენ ვიყავით უბრალოდ ვამბობ, რომ ადრე მხრივ, თუ თქვენ მიმდინარეობს ძებნის მეშვეობით, თქვენ უნდა რეალურად iterate საშუალებით თქვენი უკავშირდება სიაში. ასე რომ, თუ ჩვენ ვეძებთ ნომერი 9, გვინდა იწყება ჩვენი უფროსი და რომ მიგვითითებს დასაწყისში ჩვენი დაკავშირებული სიაში, უფლება? და ვამბობთ, OK, ჯერ ეს node შეიცავს 9 ნომერი? არა? 

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

ასე რომ, ჩვენ უნდა რეალურად iterate ჩვენი უკავშირდება სიაში. ჩვენ არ შეგვიძლია მხოლოდ წასვლა პირდაპირ, სადაც 9. და თუ ბიჭები რეალურად გვინდა ვხედავ ზოგიერთი ფსევდო კოდი აქ. ჩვენ გვაქვს გარკვეული ძებნის ფუნქცია აქ რომელიც იღებს in-- რა სჭირდება ყველაზე მეტად? თქვენ რას ფიქრობთ? ასე ადვილი. რა არის ეს? აუდიტორია: [INAUDIBLE]. დინამიკები 1: ნომერი ჩვენ ვეძებთ. არა? და რა ეს შეესაბამება? ეს მაჩვენებელი? 

აუდიტორია: კვანძში. 

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

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

თუ ეს არ არის NULL, ჩვენ გასასვლელად ჩვენი ხოლო მარყუჟის და დაბრუნების ცრუ რადგან ეს იმას ნიშნავს, რომ ჩვენ არ აღმოაჩინა იგი. ამჯამად ყველას, როგორ მუშაობს? OK. 

ასე ჩანართი, თქვენ აქვს სამი სხვადასხვა გზა. თქვენ შეგიძლიათ prepend, შეგიძლიათ დამატება და შეგიძლიათ ჩადეთ ასორტი. ამ შემთხვევაში, ჩვენ აპირებს prepend. ვინმეს ვიცი, როგორ იმ სამი შემთხვევა შეიძლება განსხვავდება? 

ასე prepend ნიშნავს, რომ თქვენ დააყენა მას წინ თქვენი სია. ასე რომ, იმას ნიშნავს, რომ არ აქვს მნიშვნელობა, რა თქვენი კვანძის არის, არ აქვს მნიშვნელობა, რა ღირებულება, თქვენ აპირებს იმისათვის, რომ ეს უფლება აქ ჩვენს თვალწინ, OK? ეს იქნება პირველი ელემენტს სიაში. 

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

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

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

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

მაგრამ reassigning თქვენი პოინტერები სწორი მიზნით იქნება ძალიან, ძალიან მნიშვნელოვანია ამ pset. წინააღმდეგ შემთხვევაში, თქვენ აპირებს აქვს hash მაგიდასთან ან ცდილობენ, რომ უბრალოდ იქნება მხოლოდ ნაწილი სიტყვა, რომ თქვენ გსურთ და შემდეგ you're-- mmhmm? აუდიტორია: რა იყო დროებითი შენახვის, რაც თქვენ ვსაუბრობთ? დინამიკები 1: დროებითი შენახვის. ასე რომ, ძირითადად, სხვა გზა თქვენ შეიძლება ამის გაკეთება არის შესანახად ხელმძღვანელი რაღაც, როგორიცაა ჩაწეროთ იგი დროებითი ცვლადი. მივანიჭოთ მას 1 და მაშინ განაახლებს 1 აღვნიშნო რაც არ უნდა უფროსის გამოიყენება წერტილი. ამ გზით, ცხადია, უფრო დახვეწილი იმიტომ, რომ თქვენ არ უნდა დროებითი ღირებულება, მაგრამ მხოლოდ სთავაზობს კიდევ ერთი გზა ამის გაკეთება. და ჩვენ მართლაც არ ზოგიერთი კოდი ამ. ასე უკავშირდება სია, ჩვენ რეალურად გვაქვს კოდი. ასე ჩასასმელი აქ, ამ prepending. ასე რომ, ეს შემოდის იგი სათავეში. 

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

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

აუდიტორია: გვაქვს ვრთავ new შემდეგი null პირველი, თუ შეგვიძლია მხოლოდ ინიციალიზაცია იგი უხელმძღვანელებს? 

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

OK, ასე რომ ორმაგად უკავშირდება სიები ახლა. რას ფიქრობენ? რა არის განსხვავებული ორმაგად უკავშირდება სიები? 

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

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

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

ასე რომ, თუ ჩვენ უნდა prepend ან append-- ჩვენ არ აქვს რაიმე კოდი ამ up აქ მაგრამ თუ თქვენ ცდილობენ და ჩადეთ იგი, მთავარია არის, რომ თქვენ უნდა მიიღოს დარწმუნებული ვარ, თქვენ მინიჭების ორივე წინა და თქვენი შემდეგი მაჩვენებელი სწორად. ასე რომ, ამ შემთხვევაში, თქვენ არა მხოლოდ ინიციალიზაცია შემდეგ, ინიციალიზაცია წინა. თუ ჩვენ იმ სიის სათავეში, ჩვენ რომ არა მხოლოდ უფროსი თანაბარი ახალი, მაგრამ ჩვენი ახალი წინა უნდა აღვნიშნო, რომ ხელმძღვანელი, არა? 

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

OK, ასე რომ hash მაგიდები. ეს არის ერთ ერთი ყველაზე სასარგებლო bit თქვენი pset აქ იმიტომ, რომ თქვენ იქნება განხორციელების ერთ-ერთი, ან ცდილობენ. მე ნამდვილად მინდა hash მაგიდები. ისინი საკმაოდ გრილი. 

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

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

ასე რომ, თუ მე რომ ჯგუფი ბიჭები ჯგუფები ვინც სახელი იწყება ერთად აქ, ან ვინც ის დაბადების დღე არის იანვარი, თებერვალი, მარტი, რასაც, რომელიც ეფექტურად შექმნის hash მაგიდასთან. უბრალოდ შექმნაში თაიგულების, თქვენ დასალაგებლად ელემენტები ასე რომ თქვენ შეგიძლიათ მათ ადვილია. ასე რომ, ეს გზა, როცა საჭიროა იპოვონ თქვენ, მე არ უნდა ვეძებოთ მეშვეობით თითოეული თქვენი სახელები. მე შეიძლება იყოს, როგორიცაა, oh, მე ვიცი, რომ Danielle დაბადების დღე არის in-- აუდიტორია: --April. დინამიკები 1: აპრილი. ასე რომ შევხედოთ ჩემი აპრილი bucket, და ნებისმიერ წარმატებას, ის იქნება მხოლოდ ერთი არსებობს და დრო იყო მუდმივი, ამ თვალსაზრისით, ხოლო თუ მე უნდა გამოიყურებოდეს მეშვეობით მთელი bunch ადამიანი, ის აპირებს ბევრად უფრო. ასე hash მაგიდები მართლაც მხოლოდ თაიგულების. მარტივი გზა ვფიქრობ ისინი. 

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

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

მაგრამ არსებობს ასევე მარტივი პირობა, როგორიცაა compute თანხა სიტყვებით, როგორიცაა თითოეულ წერილს აქვს ნომერი. გამოთვლაც თანხა. რომელიც განსაზღვრავს bucket. მათ ასევე აქვს მარტივი პირობა, რომ , ისევე, როგორც ყველა აქ, ყველა B აქ. ერთ-ერთი მათგანია. 

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

ასე რომ თქვენ გაქვთ ზოგიერთი ქეშირების ეს მხოლოდ პირველი წერილი თქვენი string მინუს, რომელიც მოგცემთ ზოგიერთი რიცხვი 0 და 25. და რა გინდათ რომ გააკეთოთ, არის დარწმუნდით, რომ ეს ზომა თქვენი hash table-- რამდენი თაიგულების არსებობს. მრავალი ამ hash ფუნქციები, ისინი უნდა დაბრუნების ღირებულებები, რომლებიც შეიძლება იყოს ბევრად მაღლა რაოდენობის თაიგულების რომ თქვენ ნამდვილად აქვს თქვენი hash მაგიდასთან, ასე რომ თქვენ უნდა მიიღოს დარწმუნებული ვარ და თავდაცვის სამინისტროს მიერ იმ. წინააღმდეგ შემთხვევაში, ეს ხდება იმის თქმა, ოჰ, ეს უნდა იყოს bucket 5000 მაგრამ თქვენ გაქვთ 30 თაიგულების თქვენი hash მაგიდასთან. და რა თქმა უნდა, ჩვენ ყველამ ვიცით, რომ ის, ვაპირებთ გამოიწვიოს ზოგიერთი გიჟები შეცდომები. ამიტომ დარწმუნდით, რომ თავდაცვის სამინისტროს მიერ ზომა თქვენი hash მაგიდასთან. ზემოთ. ასე collisions. ყველას კარგი აქამდე? Mmhmm? 

აუდიტორია: რატომ დაბრუნდეს ასეთი მასიური მნიშვნელობა? 

დინამიკები 1: დამოკიდებულია ალგორითმი რომ თქვენი ქეშირების ფუნქცია იყენებს. ზოგიერთი მათგანი გააკეთებს გიჟები გამრავლება. და ეს ყველაფერი არის მიღების მაშინაც კი, განაწილების, ასე რომ მათ გარკვეული ნამდვილად გიჟები რამ ზოგჯერ. ეს ყველაფერი. არაფერი? OK. 

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

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

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

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

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

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

ასე რომ, ჩვენ ვისაუბრეთ ამ ადრე. მე მივიღე ცოტა ადრე თავს. მაგრამ chaining ძირითადად, რომ თითოეულ bucket თქვენი hash მაგიდასთან მხოლოდ უკავშირდება სიაში. 

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

აუდიტორია: ასე რომ hash მაგიდა გააჩნია წინასწარ ზომა, როგორც [INAUDIBLE] თაიგულების? 

დინამიკები 1: Right. ასე რომ მას აქვს მითითებული რაოდენობის თაიგულების, რომ თქვენ determine-- რომელიც თქვენ ბიჭები უნდა შეგიძლიათ ითამაშოთ ერთად. ეს შეიძლება იყოს საკმაოდ cool ვნახოთ, რა მოხდება როგორც თქვენ შეცვალოთ თქვენი რაოდენობის თაიგულების. მაგრამ ჰო, მას აქვს მითითებული რაოდენობის თაიგულების. რაც საშუალებას გაძლევთ ჯდება, ბევრი ელემენტები, როგორც თქვენ უნდა ეს ცალკე chaining, სადაც თქვენ არ უკავშირდება სიები თითოეულ bucket. ეს ნიშნავს, რომ თქვენი hash მაგიდა იქნება ზუსტად ზომა რომ თქვენ უნდა, რომ იყოს, არა? რომ მთელი წერტილი უკავშირდება სიები. ზემოთ. 

ასე რომ, ყველას OK არსებობს? ყველა უფლება. Ah. რა მოხდა? ნამდვილად არის. ვფიქრობ, ვიღაცამ მკვლელობის ჩემთვის. 

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

ასე რომ ვინმეს გახსოვთ რა ლელო? თქვენ უნდა დაასრულოთ მოკლედ ლექცია? გახსოვთ, როგორი როგორ მუშაობს? აუდიტორია: მე უბრალოდ nodding რომ ჩვენ არ წასვლა მას. დინამიკები 1: ჩვენ არ წასვლა მას. OK, ჩვენ ნამდვილად აპირებს მისვლას მეტი ახლა არის ის, რაც ჩვენ დაყრდნობით. 

აუდიტორია: ეს დიდი კითხვის ხე. 

დინამიკები 1: ჰო. ეს კითხვის ხე. გასაოცარია. ასე რომ ერთი რამ შეამჩნია აქ არის ის, რომ ჩვენ ეძებს ინდივიდუალური გმირები აქ, არა? 

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

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

იქ, ალბათ, არ არის სიტყვა, რომელიც MP რაღაც, ისე P პოზიცია მასივი, რომ ის უბრალოდ იყოს NULL. რომ ვთქვა, OK, არ არსებობს სიტყვა რომ M მოჰყვა P, OK? ასე რომ, თუ ჩვენ ამაზე ვფიქრობთ, თითოეული ერთ-ერთი ასეთი მცირე რამ ფაქტიურად ერთი ასეთი დიდი მასივების ეხლა მეშვეობით ზ ასე რომ, რა შეიძლება იყოს, ერთი რამ ეს არის ერთგვარი ხარვეზად ლელო? 

აუდიტორია: მეხსიერების დიდ ნაწილს. 

დინამიკები 1: ეს ტონა მეხსიერება, არა? თითოეული ეს ბლოკები აქ წარმოადგენს 26 ფართები, 26 ელემენტს მასივი. ასე ცდილობს მიიღოს წარმოუდგენლად ფართი მძიმე. 

მაგრამ ისინი ძალიან სწრაფად. ასე ძალიან სწრაფი, მაგრამ ნამდვილად ფართი არაეფექტური. სახის უნდა გაერკვნენ რომელი ერთი გსურთ. ეს არის მართლაც cool თქვენი pset, მაგრამ ისინი დასჭირდეს ბევრი მეხსიერება, ასე რომ თქვენ ვაჭრობის off. ჰო? 

აუდიტორია: თუ ეს შესაძლებელია შეიქმნა ცდილობენ და მაშინ ერთხელ თქვენ ყველა მონაცემები, რომ თქვენ need-- მე არ ვიცი, თუ ეს აზრი. მე მოშორების ყველა NULL პერსონაჟი, მაგრამ შემდეგ თქვენ ვერ შეძლებს ინდექსი them-- 

დინამიკები 1: თქვენ ჯერ კიდევ გვჭირდება. 

აუდიტორია: - იგივე გზა ყოველ ჯერზე. დინამიკები 1: ჰო. თქვენ უნდა NULL გმირები მისცეს თქვენ იცით, თუ იქ არ არის სიტყვა არსებობს. Ben გქონდათ რაიმე გინდათ? OK. ყველა უფლება, ამიტომ ჩვენ ვაპირებთ წასვლა ცოტა მეტი ტექნიკურ დეტალურად უკან ცდილობენ და მუშაობა მეშვეობით მაგალითი. 

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

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

ასე რომ დამოკიდებულია ისე თქვენ განხორციელების, ეს არის საწყისი pset, რომ დაშვებულია apostrophes. ამიტომაც დამატებით ერთი. თქვენ ასევე უნდა ზოგიერთი შემთხვევაში null terminator შედის როგორც ერთ-ერთი სიმბოლო, რომ ეს დასაშვებია, და ეს, როგორ შეამოწმეთ თუ ეს ბოლოს სიტყვა. თუ თქვენ დაინტერესებული, შეამოწმეთ Kevin ს ვიდეო study.cs50, ისევე როგორც ვიკიპედია კარგი რესურსები არსებობს. 

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

ამიტომ, ჩვენ ვაპირებთ გავლა გამოვლენა "წინ" ამ ცდილობენ. ასე იწყება ზედა, არა? და ვიცით, რომ ბ შეესაბამება მეორე ინდექსი, მეორე ელემენტი ამ მასივი, რადგან a და b. ასე რომ დაახლოებით მეორე. 

ის ამბობს, OK, cool, დაიცვას, რომ შევიდა შემდეგი მასივი, რადგან, თუ ჩვენ გვახსოვს, ეს არ არის, რომ თითოეული ეს რეალურად შეიცავს ელემენტს. თითოეული ეს კოლექტორები შეიცავს მაჩვენებელი, არა? ეს არის მნიშვნელოვანი განსხვავება, რათა. 

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

ასე რომ, ჩვენ ბ ამ შემთხვევაში, რომელიც არის ჩვენი მეორე ინდექსი. თუ ჩვენ გვექნება, ვთქვათ, გ ან d ან რაიმე სხვა წერილი, ჩვენ უნდა განვსაზღვრავთ, რომ თავში ინდექსი ჩვენი მასივი, რომ შეესაბამება. ასე რომ, ჩვენ უნდა მიიღოს, როგორიცაა rchar და ჩვენ უბრალოდ სხვაობა off რუკაზე იგი 0-დან 25. ყველას კარგი თუ როგორ ჩვენ რუკა ჩვენი გმირები? OK. 

ამიტომ, ჩვენ წასვლა მეორე და ჩვენ , რომ, დიახ, ეს არ არის NULL. ჩვენ შეგვიძლია გადაადგილება ამ შემდეგი მასივი. ასე რომ, ჩვენ წასვლა ამ შემდეგი მასივი აქ. 

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

აუდიტორია: ეს სტანდარტი აქვს, რომ ინდექსი 0 და შემდეგ აქვს სახის ანგარიშით 1 ან აქვს ბოლოს? 

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

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

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

ამ შემთხვევაში, როცა ჩვენ შევხედოთ მაჩვენებელი h, ეს მიუთითებს NULL, OK? ასე რომ, თუ ეს პირდაპირ მიუთითებს სხვა მასივი, თქვენ ვივარაუდოთ, რომ ყველა მითითებას ამ მასივი მიუთითებს null. ასე რომ, ამ შემთხვევაში, h მიუთითებს to null ასე რომ, ჩვენ არაფრის გაკეთება არ შეგვიძლია, ასე რომ, ეს დაბრუნდება ყალბი, "აბანო" არ არის აქ. ასე რომ, ახლა ჩვენ, ფაქტობრივად, შევჩერდები როგორ იქნებოდა რეალურად ამბობენ რომ "ზოოპარკი" არის ჩვენი შანსი. როგორ უნდა ჩადოთ "ზოოპარკი" ჩვენი შანსი? ასე რომ, იმ გზით, რომ ჩვენ დავიწყეთ ჩვენი უკავშირდება სია, ჩვენ იწყება root. როდესაც ეჭვი, იწყება ფესვი ეს ყველაფერი. 

და ჩვენ ვიტყვით, OK, z. z არსებობს, და ეს ასეა. ასე რომ, თქვენ მოძრავი თქვენი შემდეგი მასივი, OK? და შემდეგ მომდევნო ერთი, ჩვენ ვამბობთ, OK, არ o არსებობს? ეს ასეა. ეს კიდევ ერთხელ. 

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

აუდიტორია: ასე შემდეგ აკეთებს, რომ ნიშნავს, რომ "ba" არის სიტყვა, ასევე? 

დინამიკები 1: No. ასე რომ, ამ შემთხვევაში, "ba" ჩვენ მივიღებთ აქ, ჩვენ ვთქვათ, არის ის სიტყვა, და ეს მაინც არ იქნება. OK? Mmhmm? 

აუდიტორია: ასე რომ, კიდევ არის ის სიტყვა და ამბობენ დიახ, მაშინ ეს შეიცავს წასვლა მ? 

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

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

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

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

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

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

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

აუდიტორია: დაველოდოთ, ასე რომ თქვენ უნდა 26 წერილები ყველა ერთი? 

დინამიკები 1: Mmhmm. ჰო, თქვენ გაქვთ 26. თქვენ გაქვთ გარკვეული არის სიტყვა marker და შემდეგ თქვენ გაქვთ 26 მითითებას ყველა ერთი. და ისინი point-- 

აუდიტორია: და ყოველ 26 ისინი ყოველ 26? 

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

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

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

არაფერი ბოლოში აქ ძალიან, ძალიან ქვედა განხილულია ფოთლები. ასე რომ მიდის ერთად მთელი ხე რამ, არა? ფოთლები კიდეებს თქვენი ხე. 

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

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

აუდიტორია: Max ორი ფოთლები. 

დინამიკები 1: Right. ასე max ორი ფოთლები. ასე რომ ამ ერთი ადრე გვქონდა ამ ერთი რომ სამი, არამედ ორობითი ხე, თქვენ გაქვთ max ორი ბავშვის მშობელი, არა? არსებობს კიდევ ერთი საინტერესო დეტალს. ვინმეს ვიცი, რომ? ორობითი ხე. 

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

აუდიტორია: უკავშირებს სიები 

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

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

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

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

OK, ასე რომ ყველაზე მეტად, მე ვფიქრობ, ჭამა სასადილო halls-- ისევე, როგორც ჩვენ შეიძლება არ მოგწონდეს. მაგრამ ცხადია, რომ შეგიძლიათ წარმოიდგინოთ, რომ დასტის ფაქტიურად, ისევე როგორც Stack of ქაღალდის ან დასტის რამ. და, რაც მთავარია გააცნობიეროს, ის არის, რომ რაღაც დამახასიათებელი რომ ჩვენ მას by-- არის LIFO. ვინმემ იცის რა, რომ დგას? Mmhmm? 

აუდიტორია: ბოლო წელს, პირველი out. 

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

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

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

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

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

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

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

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

აუდიტორია: [INAUDIBLE]. დინამიკები 1: შეამოწმეთ ზომა? ზომა. ამიტომ, ჩვენ გვინდა შეამოწმეთ თუ ჩვენი ზომა მეტია 0, OK? და თუ არის, მაშინ ჩვენ გვინდა შემცირება ჩვენი ზომა 0 და დააბრუნა. რატომ? 

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

და სად არის ელემენტს 1 შენახული? რა ინდექსი? აუდიტორია: 0. დინამიკები 1: 0. ასე რომ, ამ შემთხვევაში, ჩვენ ყოველთვის უნდა მიიღოს sure-- დაბრუნების ნაცვლად ზომა მინუს 1, იმიტომ, რომ ჩვენ ვიცი, რომ ჩვენი ელემენტს იქნება ინახება 1 ნაკლები მიუხედავად ჩვენი ზომა, ამ უბრალოდ ზრუნავს მასზე. ეს ოდნავ უფრო დახვეწილი გზა. და ჩვენ უბრალოდ decrement ჩვენი ზომა და შემდეგ დაბრუნდნენ ზომა. Mmhmm? 

აუდიტორია: ვფიქრობ, უბრალოდ, ზოგადად, რატომ ამ მონაცემების სტრუქტურას იყოს მომგებიანი? 

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

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

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

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

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

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

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

აუდიტორია: პირველი. 

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

ეს არის სახის მოსწონს მითხრა, შენ, თუ გახსნა ფაილი, თქვენ უნდა შევამოწმოთ null. ნებისმიერი ამ stacks და რიგები, თქვენ უნდა თუ არსებობს სივრცე, რადგან ჩვენ საქმე ფიქსირებული ზომის მასივი, როგორც ვხედავთ, აქ 0, 1 ყველა 5. რასაც ჩვენ ვაკეთებთ ამ შემთხვევაში შემოწმება თუ ჩვენ ჯერ კიდევ აქვს სივრცეში. ჩვენი ზომა ნაკლები მოცულობა? 

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

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

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

აუდიტორია: არა ეს იმას, რომ ჩვენ არ გამოცხადდა მასივი, იყო ხუთ ელემენტები ხანგრძლივი და მაშინ ჩვენ დასძინა გადატანა? 

დინამიკები 1: No. ასე რომ, ამ შემთხვევაში, ეს არის დასტის. ეს არ ჩაითვლება მასივი ზომა 6. და ამ შემთხვევაში, ჩვენ მხოლოდ ერთი სივრცე მარცხენა. 

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

OK, ასე რომ ერთი რამ oh, ამ საშინელი ცარცი. ერთი რამ განიხილოს საქმე. ჩვენ უბრალოდ ხუთ. OK, ასე რომ, ჩვენ ვაპირებთ ამბობენ, არის აქ. ეს არის 0, 1, 2, 3, 4. 

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

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

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

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

ასე რომ, მაშინ მომდევნო შემთხვევაში, თუ ჩვენ ამის გაკეთება, ჩვენ ვამბობთ, კარგი, მოდით dequeue რაღაც. ჩვენ dequeue ეს. ჩვენ ვიღებთ ამ ელემენტს, არა? 

და ახლა ჩვენი თავი მიუთითებს აქ, და ჩვენ გვინდა, რომ დაამატოთ კიდევ ერთი რამ. ეს არის ძირითადად უკან ჩვენი ხაზი, არა? რიგები შეგიძლიათ გადაიტანოთ გარშემო მასივი. ეს არის ერთ ერთი ძირითადი განსხვავებები. Stacks, თქვენ ამის გაკეთება არ შეუძლიათ. 

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

ასე რომ, ეს ფორმულა როგორ თქვენ გამოთვალოთ თქვენი კუდი. ამჯამად რომ აზრი? OK. OK, dequeue, და შემდეგ თქვენ ბიჭები 10 წუთი მკითხავთ, ნებისმიერი გასარკვევად კითხვები გსურთ, რადგან ვიცი, რომ ეს გიჟები. 

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

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

არსებობს ბევრად უფრო კონკრეტული კოდი on study.cs50.net, და მე მაღალ რეკომენდაციას აპირებს მეშვეობით, თუ თქვენ გაქვთ დრო, მაშინაც კი, თუ ეს მხოლოდ ფსევდო კოდი. და თუ ბიჭები მინდა გაიგო მეშვეობით რომ ჩემთან ერთად ერთ ერთი, გთხოვთ, ნება მომეცით ვიცი. მე მინდა იყოს ბედნიერი. მონაცემთა სტრუქტურები, თუ თქვენ მიიღოს CS 124, თქვენ ვიცი, რომ მონაცემები სტრუქტურების კიდევ ძალიან გართობა და ეს მხოლოდ დასაწყისია. 

მე ვიცი, ძნელია. ეს OK. ჩვენ ბრძოლას. მე მაინც გავაკეთებ. ასე რომ არ ინერვიულოთ ძალიან ბევრი ამის შესახებ. 

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

აუდიტორია: იმისათვის, რომ მაგალითად, ასე ახალი კუდი 0 დასრულდა, რომ? დინამიკები 1: დიახ. აუდიტორია: OK. ასე რომ, მაშინ გადის, ნეტავ 1 + 4 or-- 

დინამიკები 1: ასე ამბობდნენ, როდესაც ჩვენ გვინდა ეს კიდევ ერთხელ გავაკეთოთ? აუდიტორია: Yeah. ასე რომ, თუ თქვენ მჭიდროდაა out-- სად არის თქვენ გაანგარიშების კუდი ეხლა რომ? 

დინამიკები 1: ასე კუდი იყო in-- მე შევცვალე ეს. ასე რომ, ამ მაგალითში, ეს იყო მასივი ჩვენ შევხედავთ, OK? ამიტომ რამ, 1, 2, 3, 4. ასე რომ, ჩვენ გვაქვს ჩვენი უფროსი უდრის 1-ში ამ ეტაპზე, და ჩვენი ზომა უდრის 4 ამ ეტაპზე, არა? 

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

აუდიტორია: რა არის cap? 

დინამიკები 1: მოცულობა. უკაცრავად. ასე რომ, არის ზომა თქვენი მასივი. დიახ? 

აუდიტორია: [INAUDIBLE] წინაშე ჩვენ დაბრუნდნენ ელემენტს? 

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

აუდიტორია: OK, რადგან ამ წერტილი, ხელმძღვანელი იყო 0, და მაშინ მინდა დაბრუნდეს ინდექსი 0 და შემდეგ, რათა უფროსმა 1? 

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

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

მაგრამ, მანამდე, თუ თქვენ გაქვთ სახის მაღალი დონის გაგება, თუ რა ეს გააკეთოს, მათი დადებითი და cons-- რაც ჩვენ ნამდვილად ტენდენცია აღვნიშნო, განსაკუთრებით intro რა თქმა უნდა. როგორიცაა, თუ რატომ ვიყენებთ ცდილობენ მეტი მასივი? როგორიცაა, რა არის დადებითი და ნეგატივები, თითოეულ? 

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

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

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

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

აუდიტორია: თქვენ დაწყებამდე განაცხადა, რომ ჩვენ შეგვიძლია გამოვიყენოთ სხვა hash ფუნქციები, რომ ჩვენ არ უნდა შექმნა ქეშირების ფუნქცია? 

დინამიკები 1: დიახ, მარჯვნივ. ასე სიტყვასიტყვით თქვენი ქეშირების ფუნქცია, როგორიცაა Google "ქეშირების ფუნქცია" და გადახედეთ cool პირობა. თქვენ არ მოსალოდნელია, რომ ავაშენოთ საკუთარი hash ფუნქციები. ადამიანები გაატარონ თეზისები ეს ყველაფერი. 

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

აუდიტორია: თუ ცდილობენ იყოს ან ეფექტური, მაგრამ მხოლოდ უფრო რთული, ისევე როგორც 

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

დინამიკები 1: ასე რომ თქვენ ფასდება ნორმალური გზა. თქვენ აპირებს ფასდება დიზაინი. რომელი გზა, თქვენ გინდათ, რომ დარწმუნდით, რომ იგი როგორც ელეგანტური, როგორც ეს შეიძლება იყოს და, როგორც ეფექტური როგორც ეს შეიძლება იყოს. მაგრამ თუ თქვენ ცდილობენ ან hash მაგიდა, რადგან იგი მუშაობს, ჩვენ კმაყოფილი, რომ. და თუ თქვენ იყენებთ რაღაც რომ ჰეშები პირველი წერილი, რომ ჯარიმა, როგორც ალბათ, ისევე როგორც დიზაინის ბრძენი. ჩვენ ასევე მიაღწია წერტილი ამ სემესტრის მე არ ვიცი, თუ ბიჭები noticed-- თუ თქვენ pset შეფასება უარი ცოტა იმის გამო, რომ დიზაინი და whatnot, ეს შესანიშნავად ჯარიმა. ის მიღების წერტილში, სადაც თქვენი პროგრამები უფრო რთული. არსებობს სხვა ადგილებში თქვენ შეგიძლიათ გაუმჯობესება. 

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

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

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

ვიმედოვნებ, რომ ეს ნახევრად სასარგებლო მინიმუმ, და მე ვხედავ, რომ თქვენ ბიჭები მომავალ კვირას, ან ხუთშაბათს საათებში. არსებობს მოთხოვნები, საჭმლის მომავალ კვირას, ეს რამ? იმიტომ დამავიწყდა candy დღეს. მე და მოიყვანა candy ბოლო კვირას, მაგრამ ეს იყო Columbus Day, ასე იყო, როგორც ექვსი ადამიანი, რომლებიც მას ოთხი ჩანთა Candy თავს. მე შეუძლია Starbursts ერთხელ თუ გნებავთ. Starbursts? OK, ჟღერს. აქვს დიდი დღე, ბიჭები.