[მუსიკალური სათამაშო] DAVID Malan: ეს არის CS50. და ეს ორივე დაწყების და end-- როგორიცაა ფაქტიურად თითქმის ბოლომდე კვირაში ექვსი. 

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

აუდიტორია: [INAUDIBLE] დავით Malan: მართლაც. და უფრო amusingly, ღმერთმა ნუ ქნას, ჩვენ გამართავს ერთი ლექცია პარასკევი დასაწყისში სემესტრის ეს არის ის, რასაც ჩვენ ვხედავთ მოხდეს. ამიტომ დღეს, ჩვენ მიიღოს ცოტა უფრო მეტი მონაცემების სტრუქტურებში. და მოგცემთ უფრო მყარი გონებრივი მოდელი პრობლემები ხუთ საათზე რომელიც ახლა out. Misspellings, სადაც, ჩვენ გადმოგცეთ ტექსტური ფაილი რამდენიმე 100,000 პლუს ინგლისური სიტყვა და თქვენ აპირებს აქვს გაერკვნენ, თუ როგორ ჭკვიანურად მათ ჩატვირთვაზე მეხსიერება, შევიდა RAM გამოყენებით ზოგიერთი მონაცემები სტრუქტურა თქვენი არჩევანი. 

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

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

დავით Malan: Insertion. რას ნიშნავს ეს? 

აუდიტორია: Anywhere ერთად სია [INAUDIBLE]. 

დავით Malan: კარგი. ასე რომ თქვენ შეგიძლიათ ჩადეთ ელემენტს სადაც გსურთ შუა სიაში გარეშე shuffle არაფერი, რომელიც დავასკვენით, რომ ჩვენი დახარისხება დისკუსიები არ არის, აუცილებლად კარგია, იმიტომ, რომ ეს დრო სჭირდება რეალურად გადავიდეს ყველა იმ ადამიანებს, მარცხნივ ან მარჯვნივ. და ასე უკავშირდება სია, თქვენ შეგიძლიათ უბრალოდ გამოყოფს ერთად malloc, ახალი კვანძის, და შემდეგ განახლება რამდენიმე პოინტერები ორი, სამი ოპერაციების max-- და ჩვენ შეუძლია სლოტი ვინმე ყველგან შევიდა სიაში. 

სხვა რა უნდა იყო მომგებიანი შესახებ უკავშირდება სიაში? ჰო? 

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

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

აუდიტორია: არა წვდომის. 

DAVID Malan: არა წვდომის. მაგრამ ვინ ზრუნავს? წვდომის არ ჟღერს მყარი. 

აუდიტორია: [INAUDIBLE] DAVID Malan: ზუსტად. თუ გსურთ აქვს გარკვეული ალგორითმი და ნება მომეცით რეალურად შესთავაზოს ორობითი ძებნა, კერძოდ, რომელიც ერთ-ერთი, რომ ჩვენ გამოყენებული საკმაოდ bit-- თუ თქვენ არ გაქვთ წვდომის, თქვენ არ შეუძლია, რომ მარტივი არითმეტიკა მოძიებაში, როგორიცაა შუა ელემენტს და jumping უფლება მას. ნაცვლად უნდა დაიწყოს პირველი ელემენტს და ხაზოვანი მოძებნოთ მარცხენა მარჯვნივ თუ თქვენ გსურთ იპოვოთ შუა ან ნებისმიერ სხვა ელემენტს. 

აუდიტორია: ეს, ალბათ, სჭირდება მეტი მეხსიერება. 

დავით Malan: იღებს მეტი მეხსიერება. სად არის, რომ დამატებითი ღირს მოდის მეხსიერებაში? 

აუდიტორია: [INAUDIBLE] DAVID Malan: ზუსტად. ამ შემთხვევაში აქ, ჩვენ გვქონდა უკავშირდება სიაში რიცხვებით, და კიდევ ჩვენ გააორმაგოს ოდენობით მეხსიერება ჩვენ გვჭირდება, არამედ შენახვა ამ მითითებას. ახლა ნაკლებად დიდი გარიგება, როგორც თქვენი structs კიდევ უფრო დიდი და თქვენ შენახვა არ არის ნომერი, მაგრამ იქნებ სტუდენტი ან სხვა ობიექტი. მაგრამ საქმე რა თქმა უნდა რჩება. და ასე მთელი რიგი ოპერაციების on უკავშირდება სიები დაიბარეს იყო დიდი O N-- წრფივი. რამ, როგორიცაა ჩასაგდები ან ძიების ან წაშლა იმ შემთხვევაში, თუ ის ელემენტი მოხდა იყოს ბოლომდე სია იქნება ეს დალაგებულია თუ არა. 

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

ასევე, თუ თქვენ ჩემნაირი, თქვენ შეიძლება, რომ ეს მ, ამიტომ მე ვაპირებ სახის დააყენოს ამ შევიდა, თუ ეს ჩემი მაგიდა ან ჩემი სართულზე, მე გავრცელების რამ out-- ან ჩემი array ნამდვილად მე შეიძლება დააყენოს ყველა ქალბატონი იქ. Oh. აი ა ასე მე შეიძლება ამით, როგორც აქ. Oh. აქ არის კიდევ ერთი A. მე ვაპირებ იმისათვის, რომ მეტი აქ. აი ზ აქ არის კიდევ ერთი M. და ასე მე შეიძლება დაიწყოს მიღების piles მოსწონს ეს. და მაშინ იქნებ მე მინდა წასვლა მოგვიანებით და ასეთი ძალიან nitpicky-ly სახის ინდივიდუალური piles. მაგრამ საქმე ისაა, მინდა ვეძებოთ იმ შეყვანის, რომ მე ვარ გადასცა და მინდა, რომ ზოგიერთი გათვლილი გადაწყვეტილების საფუძველზე, რომ შეყვანის. თუ იგი იწყება, დაუსვან მას იქ. თუ იგი იწყება Z, ამას მეტი იქ, და ყველაფერი შორის. 

ასე რომ, ეს არის ტექნიკა, რომელიც არის საყოველთაოდ ცნობილია, როგორც hashing-- H-A-S-H-- რაც ზოგადად იმას ნიშნავს, რომ, როგორც შემავალი და გამოყენებით, რომ input გამოთვლაც მნიშვნელობა, ზოგადად ნომერი, და რომ ნომერი არის ინდექსი შენახვის კონტეინერი, მასივი. ასე რომ, სხვა სიტყვებით რომ ვთქვათ, მე შეიძლება ქეშირების ფუნქცია, როგორც მე ჩემი უფროსი, რომ თუ მე ვერ ვხედავ ვინმეს სახელი, რომელიც იწყება, მე ვაპირებ რუკაზე რომ ნულის ჩემი უფროსი. და თუ მე ვერ ვხედავ ვინმე Z, მე ვაპირებთ რუკაზე რომ 25 ჩემი უფროსი და შემდეგ დააყენა, რომ შევიდა ბოლო ყველაზე pile. 

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

აუდიტორია: მინუს ა 

DAVID Malan: ჰო. მინუს მინუს კონკრეტულად 65 თუ კაპიტალური ა ან 98 თუ ის ამას. და ისე, რომ საშუალებას გვაძლევს, ძალიან უბრალოდ და ძალიან arithmetically, რომ რაღაც შევიდა bucket, როგორიცაა, რომ. გამოდის, ჩვენ რეალურად ეს ასევე თუნდაც ტესტები. 

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

ასე რომ, ეს იდეა ჰეშირება რომ დაინახავთ არის საკმაოდ ძლიერი არის რეალურად საკმაოდ ცნობილი და ძალიან ინტუიტიური, ჰგავს, ალბათ, გაყოფა და დაპყრობა იყო კვირაში ნულოვანი. მე სწრაფად ველით hackathon რამდენიმე წლის წინ. ეს იყო Zamyla და რამდენიმე სხვა პერსონალი მისალოცი სტუდენტები როგორც მოვიდნენ. და ჩვენ გვქონდა მთელი bunch of დასაკეცი მაგიდები სახელი tags. და ჩვენ სახელი tags ორგანიზებული ერთად მოსწონს როგორც იქ და Zs იქ. და ასე ერთ TFs ძალიან ჭკვიანურად დაწერა ეს როგორც ინსტრუქციას იმ დღეს. და კვირას 12 სემესტრის ეს ყველა გააკეთა სრულყოფილი გრძნობა და ყველას იცოდა, რა უნდა გააკეთოს. მაგრამ ნებისმიერ დროს თქვენ რიგშია, ისევე, თქვენ განხორციელების იგივე ცნება hash. მოდით გააფორმონ ეს ცოტა. აქ არის მასივი. შედგენილი უნდა იყოს პატარა ფართო უბრალოდ ასახავს, ​​ვიზუალურად, რომ ჩვენ შეიძლება დააყენოს strings რაღაც ამ. და ამ მასივი ნათლად ზომა 26 სულ. და რამ მოუწოდა მაგიდა თვითნებურად. მაგრამ ეს მხოლოდ მხატვრის rendition რა hash მაგიდაზე შეიძლება იყოს. 

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

ასე hash მაგიდა შეიძლება განახორციელოს ეს მეხსიერების ხატოვნად, მაგრამ, როგორ შეიძლება, რომ რეალურად მიეცეს up? ასევე, შესაძლოა, უბრალოდ ეს. თუ მოცულობით ყველა caps, მხოლოდ ზოგიერთი constant-- მაგალითად 26 26 ასო alphabet-- მე შეიძლება მოვუწოდებთ ჩემი ცვლადი მაგიდა, და მე შეიძლება ითქვას, რომ მე ვაპირებ ბოლო char ვარსკვლავი არსებობს, ან string. ასე რომ, ეს მარტივია, როგორც ეს თუ განახორციელოს hash მაგიდასთან. და კიდევ, ეს მართლაც მხოლოდ მასივი. მაგრამ კიდევ ერთხელ, hash მაგიდა არის ის, რაც ჩვენ დარეკეთ აბსტრაქტული მონაცემები ტიპის, რომ მხოლოდ ერთგვარი კონცეპტუალური layering თავზე რაღაც უფრო mundane ახლა მინდა მასივი. 

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

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

ახლა ადრე მე სახის მოტყუებული და ეს გავაკეთეთ და მე უბრალოდ სახის stacked მათ ზემოთ ერთმანეთს. მაგრამ ეს არ აპირებს დაფრინავენ კოდი. ასე რომ, სად შეიძლება მე დააყენა მეორე სტუდენტი, რომლის სახელიც არის თუ ყველა მე ეს ხელმისაწვდომია მაგიდა სივრცეში? და მე გამოიყენება სამი სლოტი და ჩანს, იქ მხოლოდ რამდენიმე სხვები. რა შეიძლება გავაკეთოთ? აუდიტორია: [INAUDIBLE] DAVID Malan: ჰო. იქნებ მოდით უბრალოდ შეინახოს იგი მარტივი. არა? ეს არ ჯდება, სადაც მე მინდა, რომ ეს. ამიტომ, მე ვაპირებ, რომ დააყენოს ის ტექნიკურად, სადაც B წავიდოდა. ახლა, რა თქმა უნდა, მე დაწყებული ხატავს თავს კუთხეში. თუ მე სტუდენტი რომლის სახელიც არის რეალურად B, ახლა B იქნება გადავიდა პატარა წინ, როგორც შეიძლება მოხდეს, yep, თუ ეს არის B, ახლა იგი უნდა წავიდეს აქ. 

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

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

აუდიტორია: n. დავით Malan: მე მოვისმინე დიდი O of n. სიმართლეს არ შეესაბამება. მაგრამ ჩვენ აჯავრებენ გარდა რატომ მხოლოდ მომენტში. რა შეიძლება იყოს ეს? 

აუდიტორია: [INAUDIBLE] დავით Malan: ნება მომეცით ამის გაკეთება ვიზუალურად. ამიტომ ვარაუდობენ, რომ ეს არის წერილი S. 

აუდიტორია: ეს ერთი. დავით Malan: ეს არის ერთ ერთი. არა? ეს არის მასივი, რომელიც ნიშნავს, რომ ჩვენ წვდომის. და თუ ჩვენ ვფიქრობთ, რომ ეს ნულოვანი და ეს, როგორც 25, და გვესმის, რომ, რა, აქ ჩემი შეყვანის S, მე რა თქმა უნდა გარდაქმნას S, ASCII ხასიათი, შესაბამის ნომერი შორის ნულოვანი და 25 და შემდეგ დაუყოვნებლივ დააყენა, სადაც მას ეკუთვნის. 

მაგრამ რა თქმა უნდა, როგორც კი მივიღებ მეორე პირი, რომელიც არის სახელი ან B ან C საბოლოოდ, თუ მე გამოიყენება ხაზოვანი probing როგორც ჩემი გადაწყვეტა, ქრონომეტრაჟი ჩასმა უარეს შემთხვევაში რეალურად აპირებს გადაზრდას რა? და მე მესმის, რომ ეს აქ სწორად დასაწყისში. აუდიტორია: [INAUDIBLE] დავით Malan: ასე რომ, n მართლაც ერთხელ თქვენ გაქვთ საკმაოდ დიდი მონაცემები კომპლექტი. ასე რომ, ერთის მხრივ, თუ თქვენი მასივი დიდი საკმარისი და თქვენი მონაცემები იშვიათი საკმარისი, ეს ლამაზი მუდმივი დრო. მაგრამ, როგორც კი თქვენ დაიწყოს უფრო და უფრო მეტი ელემენტები, და მხოლოდ სტატისტიკურად თქვენ მიიღებთ მეტი ადამიანი წერილი როგორც მათი სახელი და წერილი B, შეიძლება პოტენციურად გადაეცემა შევიდა რაღაც უფრო მარტივია. ასე რომ არ საკმაოდ სრულყოფილი. აქედან გამომდინარე, შეიძლება გავაკეთოთ უკეთესი? 

ისე, რა იყო ჩვენი გამოსავალი ადრე, როდესაც ჩვენ გვინდა უფრო მეტი დინამიურობა მეტი რაღაც მასივი უფლება? აუდიტორია: [INAUDIBLE] DAVID Malan: რა მივიღეთ გააცნოს? ჰო. ასე უკავშირდება სიაში. ისე, ვნახოთ, რა უკავშირდება სია შეიძლება გავაკეთოთ ჩვენთვის ნაცვლად. ასევე, ნება მომეცით შესთავაზოს, რომ ჩვენ მიაპყროს სურათს შემდეგნაირად. ახლა ეს არის სხვადასხვა სურათი მაგალითი განსხვავებული ტექსტი, ფაქტობრივად, რეალურად გამოყენებით მასივი ზომა 31. და ამ ავტორის უბრალოდ გადაწყვიტა hash strings არ ეფუძნება ადამიანის სახელები, მაგრამ საფუძველზე მათი birthdates. მიუხედავად იმისა, თვის, მათ figured თუ თქვენ დაიბადა პირველ თვეში ან 31 თვეში, ავტორი იქნება hash საფუძველზე, რომ ღირებულება, ისე, რომ გავრცელებული სახელები ცოტა მეტი, ვიდრე უბრალოდ 26 წერტილებით შეიძლება დაუშვას. და ალბათ ეს არის უფრო ერთიანი ვიდრე მიმდინარეობს ანბანური წერილებს, იმიტომ, რომ, რა თქმა უნდა, ალბათ, უფრო მეტი ადამიანი მსოფლიოში სახელები რომ დაიწყოს, ვიდრე თქმა ზოგიერთი სხვა ასო ანბანი. იქნებ ეს არის პატარა უფრო ერთიანი, ვთქვათ, თანაბარი განაწილება ჩვილი მთელი თვის განმავლობაში. 

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

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

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

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

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

აუდიტორია: იმიტომ, რომ თუ ყველას აქვს იგივე დღე, ისინი აპირებენ იყოს ერთ ხაზზე. დავით Malan: Perfect. ეს შეიძლება იყოს პატარა contrived, მაგრამ ნამდვილად, უარეს შემთხვევაში, თუ ყველას აქვს იგივე დღე, მოცემული საშუალებებით გაქვთ, თქვენ აპირებს აქვს მასიურად ხანგრძლივი ჯაჭვი. ასე რომ, თქვენ შეიძლება ეძახით hash მაგიდასთან, მაგრამ რეალურად ეს მასიური უკავშირდება სიაში მთელი ბევრი შეეწირა სივრცეში. მაგრამ ზოგადად, თუ დავუშვებთ, რომ მინიმუმ დაბადების დღე არის uniform-- და ეს, ალბათ, არ არის. მე მიღების, რომ. მაგრამ თუ ჩვენ ვივარაუდოთ, რომ გულისთვის დისკუსია რომ ისინი, მაშინ თეორიულად თუ ეს არის ვერტიკალური წარმომადგენლობა მასივი, ასევე მაშინ, იმედია, თქვენ აპირებს მიიღოს ჯაჭვები, რომლებიც, თქვენ იცით, დაახლოებით იგივე სიგრძე, სადაც თითოეული ეს წარმოადგენს თვის. 

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

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

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

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

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

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

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

კერძოდ, მე ვაპირებ მკურნალობა ეს არის A, მაშინ B, მაშინ C, მაშინ D, ეს ერთი აქ. ასე რომ, ეს აპირებს ეფექტურად წარმოადგენს წერილში დ მაგრამ ჩადეთ ყველა Daven მიერ ასახელებს, მე უნდა გავაკეთოთ ცოტა მეტი. ასე რომ, მე პირველი აპირებს hash, ასე ვთქვათ. მე ვაპირებ შევხედოთ პირველი წერილი in Daven ის რაც აშკარად D, და მე ვაპირებ გამოუყოფს კვანძში, რომელიც გამოიყურება მსგავსი რამ დიდი მართკუთხედი დიდი საკმარისი, რათა შეწყობოდა მთელი ანბანი. 

ახლა D კეთდება. ახლა A. D-A-V-E-N არის მიზანი. ასე რომ, ახლა, რაც მე ვაპირებ, რომ ეს. როგორც კი დავიწყე D ცნობა არ არსებობს კურსორი იქ. ეს ნაგვის ღირებულებების მომენტში, ან მე შეიძლება ინიციალიზაცია მას null. მაგრამ ნება მომეცით შენარჩუნება აპირებს ეს იდეა ხე. მიადევნე თვალი გამოყოს ერთი ამ კვანძების, რომელსაც აქვს 26 ელემენტები მასში. 

და იცით რა? თუ ეს არ არის მხოლოდ კვანძის მეხსიერებაში, რომ მე შეიქმნა malloc გამოყენებით struct როგორც ჩვენ მალე ვნახავთ, მე ვაპირებ ამის გაკეთება მე ვაპირებ მიაპყროს arrow საწყისი ის, რომ წარმოდგენილი D ქვემოთ ამ ახალი კვანძში. და ახლა, პირველი შემდეგი წერილი Daven სახელი, V-- D-A-V-- მე ვაპირებ წავიდეთ წინ და გავამახვილო კიდევ ერთი კვანძის, როგორც ეს, რომლის დროსაც, V ელემენტები აქ, ჩვენ მიაპყროს instance-- whoops. ჩვენ არ დაიხევს არსებობს. ის აპირებს წავიდეს აქ. 

მაშინ ჩვენ ვაპირებთ მიგვაჩნია, რომ ეს V. და შემდეგ ქვევით აქ ჩვენ ვაპირებთ ინდექსი ქვემოთ V შევიდა, რაც ჩვენ განვიხილავთ E. და მერე აქ ჩვენ ვაპირებთ წავიდეთ ერთი ასეთი კვანძების აქ. და ახლა ჩვენ გვაქვს კითხვა პასუხი. მე უნდა როგორმე მიუთითებს, რომ ჩვენ ბოლოს სიმებიანი Daven. ასე რომ მე ვერ დატოვოს null. 

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

ამიტომ, რაც ჩვენ შეგვიძლია გავაკეთოთ, ნაცვლად მკურნალობა თითოეული ეს ელემენტები როგორც ალბათ, რომელსაც ორი ელემენტების შიგნით მათ. ერთ-ერთი მაჩვენებელი, რა თქმა უნდა, როგორც მე უკვე აკეთებს. ასე რომ თითოეული ეს ყუთები ეს არ არის მხოლოდ ერთ საკანში. მაგრამ რა, თუ ზედა one-- ბოლოში ერთი იქნება null, რადგან არ არსებობს Davenport უბრალოდ არ არის. რა მოხდება, თუ ზედა ერთი არის რაღაც განსაკუთრებული მნიშვნელობა? და ის აპირებს, რომ იყოს პატარა იმისთვის, რომ შევაჩერო ეს ამ ზომის. მაგრამ ვარაუდობენ, რომ ეს მხოლოდ გამშვები ნიშნის. შემოწმება. D-A-V-E-N ტექსტი ამ მონაცემების სტრუქტურას. 

იმავდროულად, თუ მქონდა მეტი სივრცე აქ, მე ვერ გავაკეთებ P-O-R-T, და მე ვერ დააყენა გამშვები კვანძის რომ აქვს წერილი T at ბოლომდე. ასე რომ, ეს არის მასიურად კომპლექსი ეძებს მონაცემები სტრუქტურა. და ჩემი ხელწერა რა თქმა უნდა, ხელს არ უწყობს. მაგრამ თუ მინდოდა ჩადეთ რამე სხვაგან, რა ჩვენ ყველაფერს გააკეთებს. თუ გვინდოდა დავით, ჩვენ გვინდა დაიცვას იგივე ლოგიკით, D-A-V, მაგრამ ახლა მინდა აღვნიშნო შემდეგი ელემენტი არ E, მაგრამ მე დ ასე არ იქნება კვანძების ამ ხეს. ჩვენ ვაპირებთ, რომ ზარი malloc მეტი. მაგრამ მე არ მინდა, რომ სრული არეულობა ამ სურათს. მოდით ნაცვლად შევხედოთ ერთი რომ უკვე წინასწარ ჩამოყალიბებული ისევე როგორც ეს არ dot, dot, წერტილი, მაგრამ მხოლოდ შემოკლებით მასივები. მაგრამ თითოეული კვანძების ამ ხეს აქ წარმოადგენს იგივე რამ მასივი Ray ზომა 26. 

თუ ჩვენ გვინდა, რომ იყოს ნამდვილად სწორი ახლა, რა თუ ვინმეს სახელი აპოსტროფი, მოდით ვივარაუდოთ, რომ თითოეული კვანძის რეალურად აქვს როგორც 27 ინდექსები, არა მხოლოდ 26. ასე რომ, ეს ახლა იქნება მონაცემები სტრუქტურა მოუწოდა trie-- T-R-I-E. Trie, რომელიც, სავარაუდოდ, ისტორიულად ჭკვიანი სახელი ხე რომ ოპტიმიზირებულია მოძიება, რომელიც რა თქმა უნდა, ჩაწერეთ რომელზეც I-E, ასე რომ trie. მაგრამ ეს არის ისტორია trie. 

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

იმის გამო, რომ მიუხედავად იმისა, ამ ეტაპზე, მე მხოლოდ გამოყენებით D's მაჩვენებელი და და V და Es და Ns, მე გაყვანაა heck of მეხსიერების დიდ ნაწილს. მაგრამ სად ვატარებ კიდევ ერთი რესურსი, მე, როგორც წესი, არ დაიბრუნებს სხვა. ასე რომ, თუ მე ხარჯვის მეტი სივრცე, რა ალბათ იმედი? რომ მე ხარჯავს ნაკლებ რა? აუდიტორია: ნაკლები დრო. დავით Malan: Time. რატომ შეიძლება რომ იყოს? ისე, რა არის ჩასმა დრო, თვალსაზრისით დიდი O ახლა, სახელის როგორიცაა Daven ან Davenport ან დავითი? ასევე, Daven იყო ხუთი საფეხურით. Davenport იქნება ცხრა ნაბიჯები, ასე რომ, ეს იქნება კიდევ რამდენიმე ნაბიჯი. დავით იქნებოდა ხუთ ნაბიჯები, ისევე. ასე რომ, ეს არის კონკრეტული ნომრები, მაგრამ ნამდვილად არსებობს ზედა ზღვარი შესახებ ხანგრძლივობა ვინმეს სახელი. და მართლაც, პრობლემა კომპლექტი ხუთი სპეციფიკაცია, ჩვენ წარვადგენთ რომ ეს რაღაც რომ 40-რაღაც უცნაური სიმბოლო. 

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

სიმებიანი მიმდინარეობს ჩასმული, რომელშიც არ მიიღოს ამ asymptotically მუდმივი time-- დიდი O ერთი. და გულწრფელად, უბრალოდ რეალურ ცხოვრებაში, ეს ნიშნავს ჩასმა Daven სახელი იღებს ისევე როგორც ხუთი ნაბიჯები, ან Davenport ცხრა ნაბიჯები, ან დავით ხუთი საფეხურით. ეს არის საკმაოდ darn პატარა გაშვებული ჯერ. და, მართლაც, რომ ძალიან კარგია, განსაკუთრებით მაშინ, როდესაც ეს არ არის დამოკიდებული საერთო რაოდენობის ელემენტები არსებობს. ასე როგორ შეიძლება ჩვენ შევასრულებთ სახის სტრუქტურის კოდი? ეს ცოტა მეტი რთული, მაგრამ მაინც უბრალოდ განაცხადი ძირითადი შენობა ბლოკად. მე ვაპირებ, ხელახლა ჩვენს კვანძის შემდეგი რედაქციით: bool მოუწოდა word-- და ეს შეიძლება მოუწოდა არაფერი. მაგრამ bool წარმოადგენს რა მიიპყრო, როგორც გამშვები ნიშნის. დიახ. ეს არის ბოლოს სიმებიანი ამ მონაცემების სტრუქტურას. 

და, რა თქმა უნდა, კვანძის ვარსკვლავი არ გულისხმობდა ბავშვებს. და, რა თქმა უნდა, ისევე, როგორც ოჯახის ხე, თქვენ მივიჩნევთ, რომ კვანძების რომ ჰკიდია off ბოლოში ზოგიერთი მშობელი ელემენტს უნდა იყოს შვილი. და ა.შ. ბავშვები აპირებს იყოს მასივი 27, 27 ერთი მხოლოდ იმიტომ, რომ ამისთვის აპოსტროფი. ჩვენ ვაპირებთ, რომ დასალაგებლად გამონაკლის შემთხვევაში, რომ. ასე რომ თქვენ გაქვთ გარკვეული სახელები apostrophes. შესაძლოა, დეფისი უნდა წავიდეს, მაგრამ თქვენ ხედავთ p კომპლექტი 5 ჩვენ მხოლოდ აინტერესებს შესახებ წერილები და ხაზს. 

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

ახლა Meanwhile-- Oh, კითხვა. 

აუდიტორია: რა არის bool სიტყვა? 

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

მიუხედავად იმისა, რომ Dave იქნება ლეგიტიმური სიტყვა, ის არ trie ამჟამად. და D არ არის სიტყვა. და D-არ არის, სიტყვა ან სახელი. ასე რომ, გამშვები ნიშნის მიუთითებს, რომ ერთხელ თქვენ მოხვდა ამ კვანძის არის გეზზე გმირები ფაქტიურად სიმებიანი რომ თქვენ ჩასმული. ასე რომ, ყველა bool იქ აკეთებს. 

ნებისმიერი სხვა კითხვები ლელო? ჰო. 

აუდიტორია: რა არის გადახურვა? რა მოხდება, თუ თქვენ გაქვთ Dave და Daven? დავით Malan: Perfect. რა მოხდება, თუ თქვენ გაქვთ Dave და Daven? ასე რომ, თუ ჩვენ ჩადეთ, ამბობენ, მეტსახელად for David-- Dave-- D-A-V-E? ეს არის რეალურად სუპერ მარტივი. ასე რომ, ჩვენ მხოლოდ აპირებს ოთხი ნაბიჯები. D-A-V-E. და რა მაქვს გავაკეთოთ ერთხელ მოხვდა, რომ მეოთხე კვანძის? უბრალოდ აპირებს შეამოწმოს. ჩვენ უკვე კარგად წასვლა. გაკეთდეს. ოთხი ნაბიჯი. მუდმივი asymptotically. და ახლა ჩვენ მითითებულია, რომ ორივე Dave და Daven სიმები სტრუქტურა. ასე არ არის პრობლემა. და შეამჩნია, როგორ თანდასწრებით საქართველოს Daven არ ხდის მიიღოს ნებისმიერი მეტი დრო და ნაკლები დრო Dave და პირიქით. 

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

და ამ ტიპის მონაცემები სტრუქტურა თქვენ გაქვთ ორი ოპერაციები თქვენ გაქვთ ერთი მოუწოდა დააყენებს და დასძინა, რაღაც დასტის, აყენებს სხვა tray უკან ზევით Stack. და მაშინ პოპ, რაც იმას ნიშნავს, მიიღოს უმაღლეს tray off. მაგრამ რა არის დასტის არის, რომ ის მივიღე ეს საინტერესო დამახასიათებელი. როგორც სასადილოს თანამშრომლები არიან გაგაგებინოთ ქაღალდის მომდევნო კვება, რა იქნება მართალია, როგორ სტუდენტები ურთიერთქმედება ამ მონაცემების სტრუქტურას? აუდიტორია: ისინი აპირებენ პოპ ერთი off. დავით Malan: ისინი აპირებენ პოპ ერთჯერადი, იმედია ზედა. წინააღმდეგ შემთხვევაში, ეს უბრალოდ სახის სულელური წავიდეთ ყველა გზა ბოლოში. არა? მონაცემები სტრუქტურა ნამდვილად არ დაუშვებს თქვენ უნდა დაიბრუნოს ქვედა უჯრა მინიმუმ მარტივად. ასე რომ არსებობს ამ ცნობისმოყვარე ქონების დასტის რომ ბოლო პუნქტის არის იქნება პირველი out. და კომპიუტერული მეცნიერები უწოდებენ ამ LIFO-- გაგრძელდება, პირველი გარეთ. ეს, ფაქტობრივად, არ აქვს საინტერესო პროგრამა. ეს არ არის აუცილებელი, როგორც აშკარა, როგორც ზოგიერთი სხვა, მაგრამ ეს შეიძლება, მართლაც, იყოს სასარგებლო, და მას შეუძლია, რა თქმა უნდა, რაც უნდა განხორციელდეს რამდენიმე განსხვავებული გზები. 

ასე რომ, ერთი და ფაქტობრივად, ნება მე არ ჩაყვინთვის შევიდა, რომ. მოდით ნაცვლად. მოდით შევხედოთ ერთი, რომ თითქმის იგივე იდეა, მაგრამ ეს ცოტა უფრო სამართლიანი. არა? თუ თქვენ ერთი ამ გულშემატკივართა ბიჭები ან გოგონებს, რომ ნამდვილად უყვარს Apple პროდუქცია და თქვენ გამოიღვიძა up at 3:00 AM გამოდიან რაღაც მაღაზიაში მიიღოს უახლესი iPhone, თქვენ შესაძლოა, რიგშია მდე მოსწონს ეს. 

ახლა მდგომ სრულიად შეგნებულად დაასახელა. ეს ხაზი იმიტომ, რომ იქ ზოგიერთი სამართლიანობის მას. არა? ეს იქნებოდა ერთგვარი sucked, თუ თქვენ იქ პირველად Apple Store მაგრამ თქვენ ეფექტურად bottommost უჯრა, რადგან Apple თანამშრომლები შემდეგ პოპ უკანასკნელი ადამიანი, რომელიც რეალურად მივიღე ხაზი. ასე stacks და რიგები, მიუხედავად იმისა, ფუნქციურად ისინი სახის იგივე ეს მხოლოდ ამ კოლექცია რესურსი, რომელიც არის გაიზრდება და shrink-- იქ ეს სამართლიანობის ასპექტი კი, მინიმუმ, რეალურ ცხოვრებაში, სადაც ფუნქციონირებს განახორციელოს ფუნდამენტურად განსხვავებული. Stack-- მდგომ rather-- განაცხადა, რომ ორი ოპერაცია: n მდგომ და დ მდგომ. ან შეგიძლიათ დაუკავშირდეთ მათ ნებისმიერი რაოდენობის რამ. მაგრამ უბრალოდ მინდა ხელში მოსაზრება, რომ ერთი და დასძინა, და ერთი, საბოლოო ჯამში, გამოკლებით. 

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

აუდიტორია: მდგომ. დავით Malan: ისე, რიგიდან. რა თქმა უნდა. რა? 

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

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

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

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

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

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

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

აუდიტორია: პატარა მარცხენა. 

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

ახლა როგორ შეიძლება თქვენთვის ნომერი 44? თქვენ, რომ იწყება root და აცხადებენ, რომ hm. 55 არ არის 44 ასე რომ, მინდა წასვლა უფლება ან არ მინდა წასვლა მარცხენა? ისე, ცხადია გსურთ წასვლა მარცხენა. ასე რომ, ეს, ისევე, როგორც სატელეფონო წიგნი მაგალითად ორობითი ძებნა უფრო ზოგადად. მაგრამ ჩვენ ახორციელებს ახლა ცოტა უფრო დინამიურად ვიდრე მასივი შეიძლება დაუშვას. და რეალურად, თუ გსურთ გამოიყურება კოდს, ერთი შეხედვით, დარწმუნებული ვარ. როგორც ჩანს, მთელი bunch of ხაზები. მაგრამ ეს ლამაზად მარტივი. თუ გსურთ განახორციელოს ფუნქცია მოუწოდა ძიების რომლის მიზანი ცხოვრებაში მოძიება მნიშვნელობა მოსწონს N, რიცხვი, და თქვენ გავიდა ერთი მაჩვენებელი მომცეთ კვანძის ფესვები, უფრო სწორად, რომ ხე, საიდანაც თქვენ შეგიძლიათ თქვათ ყველაფერი, შეამჩნევთ, თუ როგორ პირდაპირ შეგიძლიათ განახორციელოს ლოგიკა. თუ ხე null, ცხადია, რომ ეს არ არსებობს. მოდით უბრალოდ დაბრუნების ცრუ. არა? თუ თქვენ გადასცეს იგი სხვა არაფერია, იქ არაფერია. 

სხვაგან, თუ n ნაკლებია, ვიდრე ხე arrow N-- ახლა arrow n, გავიხსენოთ, რომ ჩვენ გააცნო super მოკლედ მეორე დღეს, და ეს მხოლოდ იმას ნიშნავს de-მინიშნება მაჩვენებელი და შევხედოთ საველე მოუწოდა n. ეს იმას ნიშნავს, იქ და შევხედოთ საველე მოუწოდა n. ასე რომ, თუ n ღირებულება თქვენ მოცემული, ნაკლებად მეტი ღირებულების ხეები რიცხვი, სად გინდათ წასვლა? მარცხენა. 

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

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

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

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

[ვიდეო აღწარმოების] 

-ის მოყვა გაგზავნა, ერთად ოქმი ყველა საკუთარი. ის მოვიდა სამყაროში სასტიკი ეკრანები, uncaring მარშრუტიზატორები, და საფრთხეები გაცილებით უარესი, ვიდრე სიკვდილი. ის სწრაფად. ის ძლიერი. ის TCP / IP, და ის მიიღო თქვენს მისამართზე. "Warriors წმინდა." [END ვიდეო აღწარმოების] დავით Malan: მოდის მომავალ კვირას. ჩვენ ვნახავთ შემდეგ. [ვიდეო აღწარმოების] და ახლა, "Deep Thoughts" მიერ Daven Farnham. დავით ყოველთვის იწყება ლექციები, "ყველა უფლება". რატომ არ "აქ არის გამოსავალი ამ კვირის პრობლემა კომპლექტი " ან "ჩვენ ვაძლევთ ყველა თქვენ?" [LAUGHING] [END ვიდეო აღწარმოების]