[მუსიკის დაკვრა] 

Andi Peng: კეთილი კვირაში 6 განყოფილებაში. ჩვენ გადაუხვია ჩვენი სტანდარტული განყოფილებაში დროს სამშაბათი დღის მეორე ნახევარში, ამ ლამაზი დილით. მადლობა ყველას, რომ შემომიერთდა დღეს, მაგრამ სერიოზულად, რაუნდი ტაში. 

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

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

ასე სწრაფად, სანამ ჩვენ იწყება, დღის წესრიგი დღეს ასეთია. როგორც ხედავთ, ჩვენ ძირითადად სწრაფი სროლის მთელი bunch მონაცემთა სტრუქტურები ნამდვილად, ნამდვილად, მართლაც სწრაფად. ასე რომ, როგორც ასეთი, ეს არ იქნება სუპერ ინტერაქტიული დღეს. ეს კიდე უბრალოდ ჩემთვის ერთგვარი ყვირილი რამ, რომ თქვენ, და თუ მე აღრეული, თუ მე ვაპირებ ძალიან სწრაფად, ნება მომეცით ვიცი. ისინი უბრალოდ სხვადასხვა მონაცემები სტრუქტურები და, როგორც ნაწილი თქვენი pset ამ მომავალ კვირას, თქვენ მოგეთხოვებათ განახორციელოს ერთ-ერთი მათგანი, ალბათ ორი them-- ორი მათგანი თქვენი pset. OK, ასე რომ მე უბრალოდ აპირებს დავიწყებ განცხადებები. ჩვენ წავიდეთ მეტი stacks და რიგები მეტი სიღრმე, ვიდრე ის, რაც ჩვენ გავაკეთეთ ადრე ვიქტორინა. ჩვენ წავიდეთ მეტი უკავშირდება მიუთითეთ ერთხელ, კიდევ ერთხელ, უფრო სიღრმისეული, ვიდრე ის, ჩვენ გვქონდა ადრე ვიქტორინა. და მაშინ ჩვენ ვსაუბრობთ hash მაგიდები, ხეები და ლელო, რომელიც ყველა საკმაოდ აუცილებელია თქვენი pset. და მაშინ ჩვენ წავიდეთ მეტი რამდენიმე სასარგებლო რჩევები pset5. 

OK, ასე რომ ინტელექტუალური 0. საშუალო იყო 58%. ეს იყო ძალიან დაბალი, და ასე რომ თქვენ ბიჭები ყველა გავაკეთეთ ძალიან, ძალიან კარგად შესაბამისად რომ. 

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

მე ვიცი, რომ საშინელი, რომ ვფიქრობ, რომ მე მივიღე, როგორც 40% ამ ვიქტორინაში. მე ვაპირებ, რომ ვერ ამ კლასში. მე გპირდებით, რომ თქვენ არ აპირებს ვერ კლასში. თქვენ სრულიად ჯარიმა. 

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

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

აუდიტორია: სად საათებში? 

Andi Peng: საათები tonight-- oh, კარგი კითხვა. მე ვფიქრობ, რომ სამუშაო საათებში დღეს არის თეთრი ან Commons. თუ თქვენ შეამოწმოთ ონლაინ CS50 და თქვენ გადასვლა საათებში, არ უნდა იყოს გრაფიკი, ეუბნება, სადაც ყველა მათგანი. 

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

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

OK, ასე რომ stacks. ვინ უყვარდა კითხვა ჯეკ და სამოსელი მისი ვიქტორინა? არავინ? OK, რომ ჯარიმა. 

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

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

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

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

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

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

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

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

თქვენ გინდათ შიგნით თქვენი დასტის, ასე s.strings, და თქვენ აპირებს იმისათვის, რომ ახალი ნომერი რომ გსურთ ჩადეთ არსებობს. მოდით უბრალოდ, ვამბობთ ჩვენ გვინდა, რომ ჩადეთ int n გადატანა დასტის, ჩვენ შეგვიძლია ამის გაკეთება s.strings, ფრჩხილებში, s.size შეადგენს ო. იმის გამო, რომ ზომა არის, სადაც ჩვენ ამჟამად არიან დასტის თუ ჩვენ ვაპირებთ დააყენებს ის, რომ ჩვენ უბრალოდ შედიხართ სადაც ზომა არის, მიმდინარე სისრულეს დასტის, და ჩვენ დააყენებს int n გადატანა მას. და შემდეგ ჩვენ გვინდა დავრწმუნდეთ, რომ ჩვენ ასევე ზრდა ზომა n, ასე რომ ჩვენ შეგვიძლია შენარჩუნება სიმღერა ჩვენ დასძინა ზედმეტი რამ Stack. ახლა ჩვენ გვაქვს დიდი ზომა. ნიშნავს თუ არა ეს აქ აზრი, რომ ყველას, რამდენად ლოგიკურია ეს? ეს იყო ერთგვარი სწრაფად. აუდიტორია: შეგიძლიათ წასვლა მეტი s.stringss.strings [s.size] ერთხელ? Andi Peng: რა თქმა უნდა, რას s.size გაკეთებული მოგვცეს? აუდიტორია: ეს არის მიმდინარე ზომა. Andi Peng: სწორედ, ამიტომ მიმდინარე ინდექსი, რომ ჩვენი ზომა არის, და ასე ჩვენ გვინდა, რომ ახალი რიცხვი ჩვენ გვინდა, რომ ჩადეთ s.size. ამას რამე აზრი აქვს? იმის გამო, რომ s.strings, რომ ყველა არის არის სახელი მასივი. ყველა ის არის წვდომის მასივი ჩვენს struct, და ასე რომ, თუ ჩვენ გვინდა, რომ განათავსეთ n შევიდა, რომ ინდექსი, ჩვენ შეგვიძლია მხოლოდ ის ხელმისაწვდომი გამოყენებით ფრჩხილებში s.size. ზემოთ. 

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

ასე რომ თქვენ მხოლოდ მინდა შეასრულოს ეს კოდი, ეს მხოლოდ პოპ, თუ არსებობს რაღაც პოპ. ასე რომ, თუ ზომა მეტია ვიდრე 0, ჩვენ მინუსი ზომა. ჩვენ decrement ზომა და შემდეგ დაბრუნდნენ რაც შიგნით, რადგან მიერ popping, ჩვენ გვინდა ხელმისაწვდომობა რასაც ინახება ინდექსის ზევით Stack. ყველაფერი აზრი? თუ მე თქვენ ბიჭები დაწერა ეს, იქნებოდა თუ არა ბიჭები შეძლებთ დაწეროთ ის? OK, შენ შეიძლება ითამაშოს გარშემო. არ აწუხებს, თუ არ მიიღოს იგი. ჩვენ არ გვაქვს დრო, რომ კოდი იგი დღეს იმიტომ, რომ ჩვენ ბევრი ამ სტრუქტურებში გავლა, მაგრამ არსებითად pseudocode, ძალიან, ძალიან ჰგავს დააყენებს. უბრალოდ მიყევით ერთად ლოგიკა. დარწმუნდით, რომ თქვენ წვდომის ყველა თვისებები თქვენი struct სწორად. ჰო? 

აუდიტორია: უილ ეს სლაიდები და ეს მთელი რამ იყოს დღეს-ish? Andi Peng: ყოველთვის, yep. მე ვაპირებ, რომ ცდილობენ, ეს ყველაფერი, როგორც საათის შემდეგ. მე მქონ დავით, შევეცდებით ამას, როგორც საათის შემდეგ ეს. 

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

ასე რომ, ჩვენ მინდა მოვუწოდო ამ არის dequeueing და enqueueing. თუ გვინდა, რომ დაამატოთ რამე ჩვენი რიგში, ჩვენ enqueue. თუ ჩვენ გვინდა dequeue, ან რაღაც დაშორებით, ჩვენ dequeue. 

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

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

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

აუდიტორია: [INAUDIBLE] Andi Peng: კერძოდ, გსურთ დაამატოთ ეს დამოკიდებულია იქნებ არ წერია ეს. არც ეს არის ცარიელი, ან ცარიელი. ასე რომ, თუ გსურთ რომ დაამატოთ ეს, ალბათ, აქ იმიტომ, რომ იმ შემთხვევაში, თუ ზომა არის თუ ეს არის სავსე, გსურთ რომ დაამატოთ ეს უფლება აქ, არა? 

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

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

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

არავის სურს მიიღოს stab აეხსნა, თუ რატომ თქვენ მივიღე ეს რთული რამ აქ? ჩვენ ვხედავთ, რომ დაბრუნების ჩვენი შესანიშნავი მეგობარი modulus. როგორც თქვენ ბიჭები მალე მოვა აღიაროს პროგრამირებაში, თითქმის ნებისმიერ დროს გჭირდებათ რაიმე გადაიტანოთ გარშემო არაფერი, modulus იქნება გზა ამის გაკეთება. ასე იცის, რომ, ჯერ არავის მინდა ცდილობენ აეხსნა, რომ ხაზი კოდი? ჰო, ყველა პასუხი მისაღები და მისასალმებელია. აუდიტორია: თქვენ საუბარი ჩემთვის? Andi Peng: ჰო. აუდიტორია: Oh, არ ვწუხვარ. Andi Peng: OK, მოდით გავლა ეს კოდი. ასე რომ, როდესაც თქვენ ცდილობთ რჩეულებში რაღაც გადატანა მდგომ, იმ საყვარელი საქმე, რომ ხელმძღვანელი ხდება იყოს უფლება აქ, ეს ძალიან ადვილია ჩვენთვის უბრალოდ წასვლა ბოლოს ჩადეთ რამე, არა? მაგრამ საქმე იმაშია, რიგიდან არის რომ უფროსი შეგიძლიათ რეალურად დინამიურად შეიცვალოს, სადაც ჩვენ მინდა დაწყება ჩვენი q უნდა იყოს, და როგორც ასეთი, კუდი ასევე შეიცვლება. 

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

ახლა ჩვენ გვინდა დაამატოთ რამე ამ მდგომ, მაგრამ როგორც თქვენ ბიჭები ვხედავთ, ეს არ არის იმდენად მარტივია, რომ მხოლოდ რჩეულებში რასაც მას შემდეგ, რაც ზომა იმიტომ, რომ მაშინ ჩვენ ამოიწურა ფარგლებში ჩვენი ფაქტობრივი მასივი. სად გვინდა ნამდვილად დაამატოთ აქ. სწორედ სილამაზის მდგომ ის არის, რომ ჩვენთვის, ვიზუალურად ეს ჰგავს ხაზი გადის, როგორც ეს, მაგრამ, როდესაც ინახება მონაცემთა სტრუქტურა, მათ მისცეს, როგორც მოსწონს ციკლი. ეს ერთგვარი დასრულდება გარშემო რომ წინა ანალოგიურად რომ ხაზი ასევე შეგიძლიათ გადაიტანოთ გარშემო დამოკიდებულია სადაც თქვენ გვინდა ხაზის დასაწყისში უნდა იყოს. ასე რომ, თუ ავიღებთ შეხედეთ ქვემოთ აქ, მოდით ამბობენ, რომ ჩვენ გვინდოდა, რომ შევქმნათ ფუნქცია მოუწოდა enqueue. ჩვენ გვინდოდა, რომ დაამატოთ int n შევიდა, რომ ქ. თუ q.size q-- ჩვენ მოვუწოდებთ, რომ ჩვენი მონაცემებით სტრუქტურა თუ ჩვენი queue.size არ თანაბარი შესაძლებლობების, ან თუ ეს ნაკლები მოცულობა, q.strings არის მასივი ჩვენს ქ. ჩვენ ვაპირებთ, რომ მითითებული რომ თანაბარი q.heads, რომელიც სწორედ აქ, პლუს q.size modulus მიერ მოცულობა, რომელიც გადაიტანოთ ჩვენს უკან გარშემო აქ. 

ასე რომ, ამ მაგალითად, ინდექსი of უფროსი არის 1, უფლება? ინდექსი ზომა არის 0, 1, 2, 3, 4. ასე რომ, ჩვენ შეგვიძლია გავაკეთოთ 1 + 4 modulus ჩვენი მოცულობა, რომელიც არის 5. რას გვაძლევს ეს? რა არის მაჩვენებელი, რომელიც გამოდის ეს? 

აუდიტორია: 0. 

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

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

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

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

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

OK, ასე რომ, ჩვენ ვაპირებთ, რომ გაიგო ცოტა უფრო სიღრმისეული დაკავშირებული სიები იმიტომ, რომ ისინი ძალიან, ძალიან ძვირფასი თქვენ, რა თქმა უნდა ამ კვირაში psets. დაკავშირებული სიები, როგორც თქვენ ბიჭები მახსოვს, ყველა ისინი კვანძების, რომ კვანძების გარკვეული ღირებულებები ორივე მნიშვნელობა და მომცეთ რომლებიც დაკავშირებულია ერთად იმ მითითებას. ასე რომ, struct, თუ როგორ ჩვენ ვქმნით კვანძის აქ ჩვენ აქვს int n, რომელიც რაც არ უნდა ღირებულება მაღაზიაში ან სიმებიანი n ან რასაც თქვენ გსურთ ეძახით, char ვარსკვლავი n. Struct კვანძის ვარსკვლავი, რომელიც არის მაჩვენებელი, რომ გსურთ აქვს თითოეულ კვანძის, თქვენ აპირებს აქვს, რომ მაჩვენებელი წერტილი მიმართ მომავალი. თქვენ არ გაქვთ უფროსი უკავშირდება სიაში, რომ აპირებს აღვნიშნო, რომ დანარჩენი ღირებულებების ასე შემდეგ და ასე შემდეგ სანამ თქვენ საბოლოოდ მიაღწიონ ბოლომდე. და ეს ბოლო კვანძის მხოლოდ აპირებს არ აქვს მაჩვენებელი. ის აპირებს აღვნიშნო, რომ null, და ეს მაშინ, როდესაც თქვენ იცით, თქვენ მოხვდა ბოლოს თქვენი უკავშირდება სიაში როდესაც თქვენი ბოლო მაჩვენებელი არ აღვნიშნო, რომ არაფერი. 

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

აუდიტორია: იმიტომ, რომ ისინი ყველა დაკავშირებული, მაგრამ თქვენ არ საკმაოდ ვიცი სად [INAUDIBLE]. 

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

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

ასე რომ, კოდი, რომელიც ჩვენ შევასრულებთ, და ეს ცოტა new თქვენ ბიჭები მას შემდეგ, რაც თქვენ ბიჭები არ ნამდვილად ისაუბრა და ოდესმე ჩანს მითითებას, თუ როგორ უნდა ძებნის მეშვეობით პოინტერები, ასე რომ, ჩვენ გავლა ეს ძალიან, ძალიან ნელა. ასე რომ, bool ძიება, უფლება, წარმოვიდგინოთ, ჩვენ გვინდა შევქმნათ ფუნქცია მოუწოდა ძებნა, რომელიც ბრუნდება ნამდვილი თუ თქვენ ი მნიშვნელობა შიგნით დაკავშირებული სიაში, და ის დააბრუნებს ცრუ სხვაგვარად. კვანძის ვარსკვლავი სიაში ამჟამად მხოლოდ მაჩვენებელი პირველი პუნქტის თქვენი უკავშირდება სიაში. int n არის ღირებულება, რომ თქვენ ეძებს ამ სიაში. 

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

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

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

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

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

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

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

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

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

აუდიტორია: ეს არის დინამიური, ასე უფრო ადვილია, რომელთა მიზანია: 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

OK, ასე რომ კოდი იქნება აქ. თქვენ ბიჭები შევხედოთ შემდეგ სექციაში. ეს იქნება. 

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

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

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

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

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

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

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

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

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

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

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

ყველა უფლება, ასე რომ, ახლა მე ვარ რეალურად გაატარონ ალბათ მოსწონს 15-დან 20-ე წუთზე და ნაყარი დანარჩენი დროის მონაკვეთი ვსაუბრობთ hash მაგიდები. რამდენი თქვენგანი წავიკითხე pset5 სპეც? ყველა უფლება, კარგი. ეს არის ის, უფრო მეტია, ვიდრე 50% ნორმალურად. ეს OK. 

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

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

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

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

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

ასე რომ, აქ, თუ გვინდოდა შესანახად ინგლისური სიტყვა, ჩვენ შესაძლოა, უბრალოდ, მე არ ვიცი, რომ ყველა პირველი ასო შევიდა გარკვეული რაოდენობის. ასე რომ, მაგალითად, თუ მინდოდა ა სინონიმი apple-- ან ინდექსი 0, და B სინონიმი 1, ჩვენ შეგვიძლია 26 მასალა რომელიც შეიძლება უბრალოდ შეინახოს ყველა ასო ანბანი, რომ ჩვენ დავიწყებთ. და მაშინ ჩვენ შეიძლება ჰქონდეს ვაშლს ინდექსი 0. ჩვენ შეგვიძლია ბანანის at ინდექსი 1, cantaloupe ზე ინდექსი 2, და ასე შემდეგ და ასე შემდეგ. და ამგვარად, თუ მინდოდა ძიება ჩემი hash მაგიდა და ხელმისაწვდომობის ვაშლის, მე ვიცი, ვაშლის იწყება A, და ვიცი ზუსტად რომ ეს უნდა იყოს და hash მაგიდაზე ინდექსი 0 იმიტომ ფუნქცია ადრე დანიშნული. 

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

ყველას ნათელი, თუ როგორ hash მაგიდა ფუნქცია მუშაობს? ეს არის ერთგვარი უბრალოდ უფრო რთული მასივი. ეს არის ის, რაც არის. OK. 

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

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

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

ასე რომ, აქ, თუ მე სურდა ჩადეთ ბერი, მე ვიცი, OK, მე ვაპირებ შეყვანის ის მეშვეობით ჩემი ქეშირების ფუნქცია. მე ვაპირებ დასრულდება up ერთად ინდექსი 1, და შემდეგ მე ვაპირებ შეძლებს აქვს უბრალოდ პატარა subset ეს გიგანტური 140,000 სიტყვა ლექსიკონი. და მერე შეიძლება შევჩერდეთ მეშვეობით 1/26, რომ. 

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

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

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

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

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

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

თუ მინდოდა insert-- რა არის ხილი, რომელიც იწყება, მე არ ვიცი, B, გარდა ბერი, ბანანის. 

აუდიტორია: Blackberry. 

Andi Peng: Blackberry, მაყვალი. სად blackberry აქ? ასევე, ჩვენ რეალურად არ დახარისხებული ეს არ არის, მაგრამ თეორიულად თუ ჩვენ გვინდოდა, რომ ანბანის მიხედვით, სად უნდა BlackBerry წავიდეთ? 

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

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

მაგრამ თუ შენ გაქვს რამ interspersed შემთხვევით, თქვენ კვლავ აპირებს კვეთენ მას მაინც. ასე რომ, თუ მინდოდა უბრალოდ ჩადეთ blackberry აქ და მინდოდა ძიება ის, მე ვიცი, oh, blackberry უნდა დაიწყოს ინდექსი 1, ასე რომ მე ვიცი, მომენტალურად უბრალოდ ძებნის 1. და მაშინ მე შემიძლია სახის traverse დაკავშირებული სიაში სანამ მივიღებ BlackBerry, და მერე ჰო? 

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

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

ეს სრულიად თქვენ ბიჭები როგორ გსურთ განახორციელოს. ვფიქრობ, რომ ეს მხოლოდ თაიგულების. თუ მინდოდა 26 თაიგულების, მე ვაპირებ დასალაგებლად რამ იმ თაიგულების. მაგრამ მე ვაპირებ აქვს bunch პერსონალის თითოეული bucket, ასე რომ, თუ გსურთ, რომ მას უფრო სწრაფი და ეფექტური, მიადევნე თვალი ასი თაიგულების. 

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

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

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

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

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

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

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

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

ასე რომ, თუ მე ვაპირებ ძიება ღირებულება 66, მე შეიძლება დაიწყოს 55. ეს არის 66 მეტია 55? დიახ, მე ვიცი, მე Mus ძიება i n უფლება მომცეთ ამ ხე. მე წასვლა 77. OK, არის 66-ზე ნაკლები ან მეტი 77? იგი ნაკლებია, ასე რომ თქვენ იცით, რა, რომ უნდა იყოს მარცხენა კვანძის. 

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

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

OK, ჩვენ რეალურად აპირებს მხოლოდ რამდენიმე წუთი. ასე რომ, ჩვენ ვაპირებთ, რომ დაბრუნდეს აქ. როგორც ვთქვი ადრე, I ტიპის განმარტა ლოგიკა, თუ როგორ რომ მოძებნოთ მეშვეობით. ჩვენ ვაპირებთ, რომ ცდილობენ pseudocoding ამ გარეთ რომ ნახოთ იმ შემთხვევაში, თუ ჩვენ შეგვიძლია სახის ვრცელდება იგივე ლოგიკით ორობითი ძებნა სხვადასხვა ტიპის მონაცემების სტრუქტურას. თუ თქვენ ბიჭებს სურთ მიიღონ როგორც რამდენიმე წუთი უბრალოდ ვფიქრობ, რომ ამ. OK. ყველა უფლება, მე ვაპირებ რეალურად მხოლოდ გაძლევთ the-- არსებობს, ჩვენ ვსაუბრობთ pseudocode პირველი. ასე რომ, ჯერ არავის სურს რათა stab რა პირველი, რაც თქვენ გჭირდებათ რომ გააკეთოთ, როდესაც თქვენ დაწყებული out სამძებრო არის? თუ ჩვენ ვეძებთ ღირებულება 66, რა არის პირველი, რაც ჩვენ გვინდა, რომ იმ შემთხვევაში, თუ ჩვენ გვინდა, რომ ორობითი ძებნა ამ ხეს? 

აუდიტორია: გსურთ გამოიყურება უფლება და შევხედოთ მარცხენა და ვხედავ [INAUDIBLE] დიდი რაოდენობის. 

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

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

მე უნდა ავუხსნათ, თუ ფაქტობრივი კოდი, და ეს ბევრი კოდი. არ უნდა freak out. ჩვენ ვსაუბრობთ მეშვეობით. 

ფაქტობრივად, არ. ეს იყო მხოლოდ pseudocode. OK, ეს იყო მხოლოდ pseudocode, რომელიც ცოტა რთული, მაგრამ ეს სრულიად ჯარიმა. ყველას შემდეგ გასწვრივ აქ? თუ ფესვი null, დაბრუნების ცრუ იმიტომ, რომ საშუალება თქვენ კი არ აქვს არაფერი არსებობს. 

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

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

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

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

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

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

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

და აქ რა, შემდეგი წერილი [INAUDIBLE] არის ა ასე შევხედავთ, რომ მასივი. მიგვაჩნია, რომ მერვე ღირებულება, და მაშინ ჩვენ დაინახოს, რა, hey, ის არის, რომ სიტყვა, არის B-A სიტყვა? ეს არ არის სიტყვა. ჩვენ მივიღეთ შენარჩუნება ეძებს. 

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

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

OK, მაგარი. ასე რომ, B-A-T, და შემდეგ თქვენ აპირებთ უნდა ვეძებოთ. მომავალი დრო თქვენ აპირებს იმისათვის, რომ ნახოთ, oh, hey, ეს სიმართლეა, ამრიგად, მე ვიცი, რომ ეს უნდა იყოს სიტყვა. 

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

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

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

Andi Peng: კერძოდ, ჩვენ გვინდა დავრწმუნდეთ, რომ ეს აქ, ლოგიკური ღირებულება გადამოწმებული off, რომ ეს სიმართლეა. Z-O-O, მაშინ ჩვენ ვაპირებთ, რათა შეამოწმოს, რომ, ასე რომ, ჩვენ ზუსტად ვიცით, hey, ზოოპარკში არის სიტყვა. მე ვაპირებ ვუთხრა კომპიუტერული, რომ ეს სიტყვა ასე რომ როდესაც კომპიუტერი ამოწმებს, იგი დარწმუნებულია, რომ ზოოპარკში არის სიტყვა. 

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

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

და ასე შემდეგ მოდის პრობლემა, თუ როგორ გვინდა ჩვენ წავიდეთ შესახებ ჩასმა რაღაც რომ არის, ფაქტობრივად, არ არსებობს? ასე რომ, მოდით უბრალოდ, ვამბობთ ჩვენ გვინდა ჩადეთ სიტყვა, აბაზანა, ჩვენს trie. როგორც ბიჭებს ვხედავ, როგორიცაა გაკეთებული ყველა გვაქვს ახლა არის B-A-T, და ამ ახალი სტრუქტურის მონაცემები არ ჰქონდა pint, რომ აღნიშნა, რომ null იმიტომ, რომ ჩვენ ვივარაუდოთ, რომ, რა, არ არსებობს სიტყვა შემდეგ B-A-T, რატომ ჩვენ უნდა შევინარჩუნოთ მქონე რამ მას შემდეგ, რაც T. 

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

ჩვენ ვაპირებთ, რომ დაავალოს H, პირველ რიგში, ეს null, ჩვენ ვაპირებთ, რომ თავი დაეღწია. ჩვენ ვაპირებთ, რომ სთ წერტილი ქვემოთ. თუ ჩვენ ვხედავთ H, ჩვენ გვინდა, რომ ეს წასვლა სხვაგან. 

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

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

ასე რომ, pset4, საქართველოს მე -5 ბლოკის oh, რომ არასწორია. Pset5 არის შეცდომები. როგორც ვთქვი, თქვენ აპირებს, კიდევ ერთხელ ერთხელ, ჩამოტვირთვა კოდის ჩვენგან. არ იქნება სამი მთავარი რამ თქვენ უნდა ჩამოტვირთვის. თქვენ ჩამოტვირთოთ ლექსიკონები, kers და ტექსტები. 

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

ასე რომ, სამ პროგრამა, რომელიც ჩვენ მოგცემთ უწოდებენ dictionary.c, dictionary.h და speller.c. ასე რომ, ყველა dictionary.c არ არის რაც თქვენ სთხოვა განახორციელოს. ეს ტვირთავს სიტყვა. ეს სიტყვიერად ამოწმებს მათ, და რაც დარწმუნებული ვარ, რომ ყველაფერი არის ჩასმული სწორად. 

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

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

და ნაყარი ამ გამოწვევას არის თქვენ ბიჭები ნამდვილად ცვლილებები dictionary.c. ჩვენ ვაპირებთ, რომ გადმოგცეთ 140,000 სიტყვების ლექსიკონი. ჩვენ ვაპირებთ, რომ გადმოგცეთ ტექსტი ფაილი, რომელიც ამ სიტყვებით, და ჩვენ გვინდა, რომ თქვენ შეძლებთ ორგანიზება მათ hash მაგიდასთან ან trie იმიტომ, რომ როცა ჩვენ ვთხოვთ თქვენ სიტყვიერად check-- წარმოიდგინეთ, თუ თქვენ მართლწერის შემოწმების, როგორიცაა ჰომეროსის ოდისეა. ეს იგივეა, რომ ეს ძალიან დიდი გამოცდა. 

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

და ამიტომ ფრთხილად უნდა გადავწყვიტოთ შეჯახება. თქვენ აპირებთ მისაღებად bunch სიტყვები, რომელიც იწყება ა თქვენ აპირებთ მისაღებად bunch სიტყვა რომ იწყება B. Up თქვენ ბიჭები, თუ როგორ გსურთ მოგვარებას. ალბათ იქ უფრო ეფექტური hash ფუნქცია მეტი, ვიდრე უბრალოდ პირველი წერილი რაღაც, და ისე, რომ თქვენზეა ბიჭები სახის რასაც თქვენ გსურთ. 

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

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

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

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

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

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

აუდიტორია: მოვიყვანთ მხოლოდ გამოყენებით [INAUDIBLE]? 

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

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

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

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

ასე რომ, სრული და არაადამიანური რწმენა, ბიჭები შეძლებთ სცემეს ჩვენი [INAUDIBLE] spellings. მე რეალურად არ რაიმე წერილობითი აფეთქდა არ არის, მაგრამ მე უნდა დაწეროს აფეთქდა. ასე რომ, როდესაც თქვენ წერა თქვენი, მე წერა აფეთქდა. მე ვაპირებ ცდილობენ, რათა ნაღმი უფრო სწრაფად, ვიდრე თქვენი. ჩვენ დავინახავთ, რომელსაც აქვს უსწრაფესი ერთი. 

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