დავით Malan ყველა უფლება. სტუმარს უკან CS50. ეს არის დაწყების კვირაში 8. და გავიხსენოთ, რომ პრობლემა ნაკრები 5 დასრულდა ერთად ცოტა გამო. ასე რომ, თუ ვთქვათ თქვენ ამოღებული ყველა თქვენი სწავლების პრაქტიკის და CA-ის ფოტოებზე ამ card.raw ფაილი, თქვენ უფლება ახლა ყველა იმ ხალხს და ერთი იღბლიანი გამარჯვებული ფეხით სახლში ერთი ეს ყველაფერი, ნახტომი მოძრაობის მოწყობილობა, რომელიც შეგიძლიათ გამოიყენოთ საბოლოო პროექტები, მაგალითად. ეს კი, ყოველ წელს, იწვევს ცოტა creepiness. ასე რომ, ის, რაც მეგონა, მე მინდა გაკეთება არის წილი თქვენთან ერთად ზოგიერთი აღნიშნავს, რომ აქვს წავიდა უკან და მეოთხე ზე საშტატო ხვდება. მაგალითად, გასულ ღამეს, გაცემა unquote, ერთი პერსონალის წევრი, "მე მქონდა სტუდენტი დარტყმა ჩემი კარი მიიღოს ფოტო ჩემთან ერთად. Stalkers, მე გეტყვით. "მოედანზე საკმაოდ აღწერითი და შემდეგ გადავედით შესახებ, საათში ან ასე შემდეგ, "მე მქონდა სტუდენტი მელოდება შემდეგ სექციაში მას ჰქონდა ყველა ჩვენი სახელები და ფოტოები ზოგიერთ ფურცლებზე. "ყველა უფლება. ასე რომ, ორგანიზებული, მაგრამ არა ყველა რომ creepy ამჟამად. ამის შემდეგ, "მე ვიყავი ქალაქგარეთ ამ კვირის ბოლოს, და როცა დაბრუნდა, იყო ერთი ჩემი საძინებელი. "[სიცილი] დავით Malan: შემდეგი ციტატა პერსონალი წევრი, "სტუდენტი მოვიდა სახლი SOMERVILLE ღამის 4 საათზე დილით. "შემდეგი თანამშრომლები, "მე მივიღე ჩემი სასტუმროს სან ფრანცისკოსა და სტუდენტი ელოდა მე ფოიეში სამი DSLRs ". გაცნობის კამერა. "მე არ ვარ კი თანამშრომლები ამ სემესტრის მაგრამ სტუდენტი შეიჭრნენ ჩემს სახლში ამ დილით და ჩაწერა მთელი რამ Google-შუშა. "და მაშინ ბოლოს, "სულ მცირე 12 ადამიანი იმყოფებოდა ცალსახად ელოდება ჩემთვის, როდესაც მე მივიღე და ჩემი limo, და მერე გაიღვიძა. "ყველა უფლება. ასე რომ, მათ შორის ფოტოების, როგორც შეგიძლიათ გავიხსენოთ, რომლებიც ამ თანამემამულე აქ, ვინ ხარ ალბათ იცით, როგორც მილო ბანანის, რომელიც ცხოვრობს ერთად ლორენ Carvalho, ჩვენი უფროსი სწავლების თანამშრომელი. Milo, Milo, აქ მოვიდა ბიჭი. Milo. Milo. ნუ თქვენ, ის ეცვა Google შუშა, ისე ჩვენ გავხდით თქვენ ეს ყველაფერი შემდეგ. ასე რომ, ეს Milo თუ გსურთ მიიღოს ფოტოს მასთან შემდეგ. თუ გსურთ გამოიყურებოდეს out ზე აუდიტორიის არსებობს. OK. სწორედ კარგი კადრები. ისე, Milo Banana. ოჰ, არ გაგვაჩნია. [სიცილი] OK. ასე რომ, სიტყვა მერე რა დევს წინ, რადგან ჩვენ ვიწყებთ გარდამავალი ამ კვირაში კონკრეტულად, საწყისი C- ბრძანების ხაზი გარემოს PHP და JavaScript და SQL და HTML და CSS ში ინტერნეტის მეშვეობით გარემო, ვიქნებით აღჭურვას გაძლევთ ყველა მეტი ცოდნის პოტენციური საბოლოო პროექტები. მიმართ, რომ ბოლოს და ბოლოს, რა თქმა უნდა აქვს ჩატარების ტრადიციის დამკვიდრება სემინარები რომელიც არიან tangential თემა to რა თქმა უნდა. ძალიან დაკავშირებული პროგრამირების და ოთახი განვითარებისა და ა.შ., მაგრამ არ არის აუცილებელი შესწავლილი მიერ რა თქმა უნდა, საკუთარი სილაბუსში. ასე რომ, თუ თქვენ შეიძლება იყოს დაინტერესებული ერთი ან მეტი წლევანდელი სემინარები, დარეგისტრირდეთ cs50.net/seminar. არსებობს ძველი სემინარები ზე cs50.net/seminars. ხოლო სტუმარს დღემდე ამ წელს საოცარი ვებ პროგრამები ერთად Ruby on რელსები, რომელიც ალტერნატიული ენა PHP. კომპიუტერული ლინგვისტიკა. შესავალი iOS, რომელიც პლატფორმა, რომელიც გამოიყენება iPhone და iPad განვითარებას. JavaScript ვებ პროგრამები, ჩვენ დაფარავს , მაგრამ ამ სემინარის, თქვენ წავიდეთ უფრო დეტალურად. ნახტომი Motion, ასე რომ ჩვენ რეალურად გვაქვს ჩვენი მეგობრების მხრიდან ნახტომის Motion, კომპანია თავად, შემოგვიერთდნენ. ხვალ, ფაქტობრივად, უზრუნველყოს პრაქტიკული სემინარი, თუ საინტერესო იყოს თქვენთვის. Meteor.js, ალტერნატიული ტექნიკა გამოყენებით JavaScript არა ბრაუზერის, მაგრამ სერვერზე. Node.js, რაც ძალიან ამ ვენის ასევე. Sleek Android დიზაინი. Android მყოფი ძალიან პოპულარულია ალტერნატიული to iOS და Windows ტელეფონი და სხვა მობილური პლატფორმების. და ვებ უშიშროების შემოვიდა თავდაცვის. ასე რომ, რეალურად, თუ გსურთ ჩაერთონ ამ ნება მიბოძეთ, მიიღოს ნოტა ამ. ჩვენ ძალიან მოხარულები ვართ, რომ ვთქვათ, რომ ჩვენს მეგობრებს ნახტომის Motion, რომელიც გაშვების - ამ მოწყობილობის რეალურად მხოლოდ მოვიდა რამდენიმე თვის წინ - აქვს graciously საჩუქრად 30 ასეთი მოწყობილობები კლასს, რადგან ბევრი სტუდენტი, თუ გსურთ სესხის ტექნიკის მიმართ სემესტრის ბოლოს და გამოყენება ფაქტობრივი საბოლოო პროექტს. ისინი მხარს უჭერენ რიგი ენებზე. არც ერთ მათგანს C, არც ერთი მათგანი PHP, ისე გააცნობიეროს, ერთი ან მეტი ასეთი სემინარები შეიძლება დაამტკიცოს ინტერესი. და ყველა მათგანი იქნება გადაღებული შემთხვევაში, თუ თქვენ ვერ ახერხებენ დასწრების პირადად. გრაფიკის გამოცხადდება მეშვეობით ელ, როგორც ჩვენ გაამყარებს ოთახები. და ბოლოს, თუ თქვენ გადასვლა projects.cs.50.net, ეს ნახვა შევინარჩუნებთ ყოველწლიურად, რომ ჩვენ ვიწვევთ ეგ ეხლა თანამეგობრობას, ფაკულტეტი, დეპარტამენტები, პერსონალი, და ორივე in გარეთ CS50 to შესთავაზოს პროექტის იდეები. სიტუაცია საინტერესო სტუდენტური ჯგუფების. სიტუაცია საინტერესო განყოფილებებს. ასე რომ აქციოს არსებობს თუ თქვენ იბრძვიან ერთად გაურკვევლობა, თუ რა თქვენ თავს მინდა დაძლევის. ასე რომ, ბოლო დროს ჩვენ გააცნო სავარაუდოდ უფრო რთული მონაცემთა სტრუქტურის, ვიდრე ჩვენ მინდა ჩანს კვირის წარსულში. გვსურს იყენებს მასივების საკმაოდ სიხარულით როგორც სასარგებლო, თუ მარტივი მონაცემთა სტრუქტურა. ამის შემდეგ ჩვენ გააცნო ამ, რომელიც რა თქმა უნდა, დაკავშირებულია სიები. და რა იყო ერთი მოტივაცია for დანერგვის ამ მონაცემთა სტრუქტურაში? ჰო? რა არის ეს? აუდიტორია: დინამიური ზომა. დავით Malan: დინამიური ზომა. ასე რომ, ხოლო მასივი, თქვენ უნდა ვიცი მისი ზომა წინასწარ, როდესაც თქვენ გამოყოს იგი. In უკავშირდება სია, თქვენ არ უნდა ვიცოდეთ, რომ. თქვენ შეგიძლიათ malloc, ან უფრო ზოგადად, გამოყოფს დამატებით კვანძის, ასე ვთქვათ, ნებისმიერ დროს გვინდა ჩადეთ უფრო მონაცემები. და კვანძის არ აქვს წინასწარ განსაზღვრული მნიშვნელობა. უბრალოდ გვარეობითი ცნება, სადაც აღწერილია ერთგვარი კონტეინერი, რომ ჩვენ გამოყენებით ჩვენს მონაცემთა სტრუქტურის შესანახად ზოგიერთ პუნქტში ინტერესი, რომელიც ამ შემთხვევაში არ უნდა იყოს რიცხვებით. მაგრამ ყოველთვის tradeoff. ასე რომ, ჩვენ ვიღებთ დინამიური ზომის მონაცემები სტრუქტურა, მაგრამ რა ფასად არ ვიხდით? რა არის downside დაკავშირებული სიები? ჰო? აუდიტორია: მეტი მეხსიერება. დავით Malan: ეს მოითხოვს უფრო მეხსიერება, რამდენად ზუსტად? აუდიტორია: [inaudible]. დავით Malan: ზუსტად. ასე რომ, ახლა ჩვენ მითითებას დაკავების დამატებითი მეხსიერების, რომ ჩვენ ადრე არ სჭირდება, რადგან უპირატესობა საქართველოს მასივი, რა თქმა უნდა, არის ის, რომ ყველაფერი მომიჯნავე, უკან უკან რომ დაბრუნდა, რომელიც გაძლევთ წვდომის. იმის გამო, რომ უბრალოდ გამოყენებით კვადრატული ფრჩხილი notation ან უფრო ტექნიკურად მაჩვენებელი არითმეტიკული, ძალიან მარტივია გარდა ამისა, შეგიძლიათ წვდომის ნებისმიერი ელემენტები მუდმივ დრო. და სინამდვილეში, ეს ერთგვარი მან მიანიშნა ზე სხვა ფასი, რომ ჩვენ გადახდის უკავშირდება სიაში. რა მოხდება, გაშვებული დრო რაღაც ძებნა, თუ მინდა რაღაც ღირებულება და შიგნით საქართველოს უკავშირდება სიაში? რას ჩემი ქრონომეტრაჟი გახდეს? დიდი ო ო. თუ ეს გადანაწილებული უნდა? რა მოხდება, თუ მონაცემთა სტრუქტურის გადანაწილებული? გავაკეთო უკეთესია, ვიდრე დიდი O of ო ძებნას? არა, იმიტომ, რომ უარეს შემთხვევაში ეს შესაძლოა ძალიან კარგად იყოს დახარისხებული, მაგრამ ნომერი ვეძებთ შეიძლება იყოს დიდი. ეს შეიძლება იყოს რიცხვი 100, რომელიც შეიძლება მოხდეს, რომ იყოს ყველა გზა ბოლოს. და რადგან თქვენ მხოლოდ წვდომის დაკავშირებული სიაში ამ შესრულების გზა მისი პირველი კვანძის, თქვენ ჯერ კიდევ სახის out of luck. თქვენ უნდა traverse მთელი რამ პირველი გაგრძელდება, რათა რომ დიდი მნიშვნელობა, როგორიცაა 100. ან, რათა დადგინდეს, თუ ეს არც კი არსებობს. ასე რომ, ჩვენ არ შეგვიძლია გავაკეთოთ ალგორითმი მონაცემები სტრუქტურა, რომელიც ასე გამოიყურება? ჩვენ არ შეგვიძლია გავაკეთოთ ორობითი ძებნა, რადგან ორობითი ძებნა საჭირო, რომ ჩვენ გვქონდა წვდომის. ჩვენ შეიძლება მხოლოდ ნახტომი from ადგილმდებარეობა საიდან გარეშე დაიცვას ეს პური crumbs სახით ყველა ამ მითითებას. ახლა, რა ჩვენ შევასრულებთ? ისე, თუ ჩვენ წასვლა ეკრანზე აქ, თუ ჩვენ შეგვიძლია სწრაფად reimplement ამ მონაცემთა სტრუქტურა - ჩემი ხელწერა არ არის ყველა, რომ დიდი, მაგრამ ჩვენ შევეცდებით. ასე რომ typedef struct, რა უნდოდა I მინდა მოვუწოდო ამ რამ აქ? Node. ასე რომ, შეძლებთ us დაიწყო. ახლა კი, თუ რა უნდა იყოს შიგნით მონაცემთა სტრუქტურა, რომელიც ცალკე უკავშირდება სიაში? რამდენი სფეროებში? ასე რომ, ორი. ერთი საკმაოდ მარტივია. ასე int n. და ჩვენ შეიძლება მოუწოდოს ო არაფერი ჩვენ გვინდა, მაგრამ ეს უნდა იყოს int, თუ ჩვენ ახორციელებს უკავშირდება სიაში ints. ახლა კი რა მეორე სფეროში უნდა იყოს? Struct კვანძის *. ასე რომ, თუ struct კვანძის *, და მერე შეუძლიათ ეს ასევე რაც არ მინდა, მაგრამ უნდა იყოს ნათელი მე მოვუწოდებ მას შემდეგ, როგორც ჩვენ აკეთებდა. და მაშინ მე ახლოს ჩემს curly აფრთხილებს. ახლა კი, როგორც ბოლო დროს, მე კვანძის ქვემოთ აქ. მაგრამ თუ მე გამოცხადების ეს ყველაფერი კვანძის, რატომ მე გადაიტვირთოთ ასეთი verbose აქ გამოცხადების struct კვანძის * მომდევნო, როგორც ეწინააღმდეგებოდა უბრალოდ კვანძის * შემდეგი? ჰო? აუდიტორია: [inaudible]. დავით Malan: ზუსტად. ზუსტად. იმის გამო, რომ C მართლაც მოგაწვდით ფაქტიურად და მხოლოდ ხედავს განსაზღვრება კვანძის გზა ქვემოთ აქ, თქვენ ვერ უწოდებს აქ. ამიტომ ამ სახის უპირატესი გამოსყიდვის დეკლარაციის აქ, რომელიც admittedly მეტი verbose. Struct კვანძის, რაც იმას ნიშნავს, ჩვენ ახლა ვებგვერდზე შიგნით მონაცემთა სტრუქტურას. და როგორც განზე, რადგან ეს გახდეს უფრო სუბიექტური ახლა, ვარსკვლავი შეიძლება ტექნიკურად აქ, მას შეუძლია წავიდეს აქ, მას შეუძლია კიდევ წავიდეთ ცენტრიდან. ჩვენ მიღებული, ამ სტილის სახელმძღვანელო რა თქმა უნდა, კონვენციის აყენებს ვარსკვლავი უფლება შემდეგ მონაცემები ტიპის, რაც ამ შემთხვევაში, იქნება struct კვანძის. მაგრამ განხორციელებისას ბევრი სახელმძღვანელოების და ონლაინ ცნობას, შეიძლება მართლაც მისი დანახვა მეორე მხარეს. მაგრამ მიხვდებიან, რომ ორივე რეალურად მუშაობა და თქვენ უნდა უბრალოდ იყოს თანმიმდევრული. ყველა უფლება. ასე რომ, იყო ჩვენი დეკლარაცია საქართველოს struct კვანძის. მაგრამ შემდეგ ჩვენ დავიწყეთ აკეთებს უფრო დახვეწილი რამ. მაგალითად, ჩვენ გადავწყვიტეთ, რომ გააცნობს რაღაც hash მაგიდასთან. ასე რომ, აქ არის hash მაგიდასთან ზომა n, ინდექსირებული 0 ზედა დარჩა ო მინუს 1 წლის ბოლოში დარჩა. ეს შეიძლება იყოს hash მაგიდა არაფერი. მაგრამ რა სახის რამ საერთოდ ვსაუბრობთ გამოყენების შესახებ hash მაგიდა? შენახვა რა? სახელები. ჩვენ შეიძლება არ სახელები, როგორიცაა ჩვენ გავაკეთეთ ბოლო დროს. მართლაც, შეგიძლიათ შესანახად არაფერი. და ჩვენ დავინახავთ, ეს კიდევ ერთხელ in PHP და JavaScript. Hash მაგიდა ლამაზი სახის შვეიცარიის არმიის დანა, რომელიც საშუალებას გაძლევთ შენახვა საკმაოდ ბევრი რაც გაგიხარდებათ შიგნით მას ასოცირების გასაღებები ფასეულობებით. Keys ფასეულობებით. ახლა ამ მარტივი შემთხვევაში, ჩვენი გასაღებები მხოლოდ ციფრები. ჩვენ ახორციელებს hash მაგიდა როგორც მასივი. ასე რომ გასაღებები 0, 1, 2, და ა.შ.. ასე რომ, ჩვენ, როგორც ადამიანი, გადაწყვიტა ბოლო კვირას, რომ იცით, რა, თუ ჩვენ აპირებს მაღაზიის სახელები, მოდით მხოლოდ თვითნებურად, მაგრამ საკმაოდ გონივრულად, ვარაუდობენ, რომ ელის, სახელი და გვარი, უბრალოდ იყოს ინდექსირებული შევიდა 0. და ბობ, B სახელწოდება იქნება ინდექსირებული შევიდა 1, და ა.შ.. ასე რომ, ჩვენ გვქონდა რუკების შორის საშუალებებით, რომლებიც strings და hash ადგილებში, რომლებიც ნომრები. ასე რომ, პროცესი საყოველთაოდ ცნობილია, როგორც hash ფუნქცია, შეგიძლიათ ნამდვილად განახორციელოს ეს კოდი. თუ მინდოდა განხორციელება hash ფუნქცია რომ არ ზუსტად ის, რაც ჩვენ უბრალოდ აღწერილი ბოლო დროს, ალბათ ვაცხადებ ფუნქცია, რომელიც გადადის, როგორც შეყვანის მაგალითად - და მოდით ეს ამ ეკრანზე მეტი აქ. თუ მინდოდა განხორციელება hash ფუნქცია, შეიძლება ითქვას, მსგავსი რამ. ეს დაბრუნებას აპირებს int. ეს იქნება მოუწოდა hash და ეს აპირებს მიიღოს როგორც არგუმენტი ტექსტი, ან ჩვენ შეიძლება იყოს უფრო სწორად, ახლა, და აცხადებენ, char *, ჩვენ მოვუწოდებთ მას s. და მაშინ ყველაფერი ეს ფუნქცია უნდა გააკეთოს, საბოლოო ჯამში, არის დაბრუნდეს int. ახლა, როგორ აკეთებს, რომ შეიძლება არ უნდა იყოს ისე ნათელი. მე ვაპირებ განხორციელების გარეშე ფორმა შეცდომა შემოწმების უფლება. მე მხოლოდ აპირებს ბრმად ამბობენ, დაბრუნება რაც at s bracket 0, მინუსი, ვთქვათ, კაპიტალი მძიმით. სრულიად გატეხილი. ეს არ არის სრულყოფილი, რადგან ერთი, რა, თუ არის null? ცუდი რამ მოხდება. ორი, რა, თუ პირველი წერილი ამ სახელი არა დედაქალაქის წერილი? ამით არ აპირებს გახდეს გარეთ კარგად ან. ეს შეიძლება ამას წერილი თუ არა წერილი ყველა. ასე რომ, მთლიანად საჭიროებს გაუმჯობესებას აქ, მაგრამ ეს არის ძირითადი იდეა. რაც ჩვენ აღწერილი გასულ კვირას სიტყვიერი როგორც უბრალოდ პროცესი რუკების Alice to 0 და ბობ 1 შეიძლება გამოიხატოს რა თქმა უნდა, უფრო formulaically როგორც C ფუნქციონირებას აქ. მოუწოდა კვლავ hash, იღებს სიმებიანი როგორც შეყვანა, შემდეგ კი რატომღაც არ რაღაც რომ შეტანის წარმოების გამომავალი. არ არის განსხვავებით ჩვენი შავი ყუთი აღწერა რომ ჩვენ ხანგრძლივი გაკეთდეს. არ ვიცი, როგორ შეიძლება იყოს სამუშაო ქვეშ hood. პრობლემის კომპლექტი 6, ერთ გამოწვევები თქვენთვის უნდა გადაწყვიტოს რა თქვენი hash ფუნქცია იქნება? რა იქნება შიგნით, რომ შავი ყუთი, და სავარაუდოდ, ეს იქნება უფრო საინტერესოა, ვიდრე ეს, და ნამდვილად უფრო მგრძნობიარეა, რომ შეცდომა შემოწმების, ვიდრე ამ კონკრეტული განხორციელებას. მაგრამ პრობლემა წარმოიქმნება, არა? თუ ჩვენ გვაქვს მონაცემთა სტრუქტურის მსგავსი ერთი, რა არის ერთ ერთი პრობლემები შეგიძლიათ აწარმოებს შევიდა დროთა განმავლობაში, როგორც თქვენ ჩადეთ უფრო და უფრო სახელები შევიდა hash მაგიდაზე? თქვენ შეჯახება, არა? რა მოხდება, თუ თქვენ გაქვთ Alice და აარონი, ორი ადამიანი, რომელთა სახელები მოხდა უნდა დაიწყოს? ეს სთხოვს კითხვა, თუ სად დააყენა მეორე ასეთი სახელი? ისე, თქვენ შეიძლება გულუბრყვილოდ მხოლოდ დააყენა ეს სადაც ბობ ეკუთვნის, მაგრამ შემდეგ ბობ არის სახის ბრალია თუ ცდილობენ ჩადეთ მისი სახელი მომავალი და არ არსებობს ოთახი მისთვის. ასე რომ, შესაძლოა, დააყენა ბობ, სადაც ჩარლი არის, და თქვენ წარმოიდგინეთ ეს ძალიან სწრაფად devolving შევიდა ცოტა სასადილო. რაღაც სწორხაზოვან, საბოლოოდ, სადაც თქვენ უბრალოდ უნდა ვეძებოთ მთელი რამ ეძებს Alice ან ბობ ან აარონის ან ჩარლი. ასე რომ, ნაცვლად შევთავაზეთ, ნაცვლად მხოლოდ ხაზოვანი საცდელი ღია ფართები და plopping სახელები არსებობს, ჩვენ შემოთავაზებული fancier მიდგომა. Hash მაგიდა განხორციელდა ჯერ კიდევ რიგი მაჩვენებლების, მაგრამ მონაცემთა ტიპის იმ მაჩვენებლების ახლა იყო მითითებას. მითითებას, თუ რა? მითითებას უკავშირდება სიები. იმის გამო, რომ შეგახსენებთ, რომ უკავშირდება სია რეალურად მხოლოდ კურსორის კვანძის და კვანძის აქვს მომავალი სფეროში, და რომ კვანძის აქვს შემდეგი მოედანზე და სხვ. ასე რომ, შეგიძლიათ ვფიქრობ, ამ მასივი წლის მარცხენა მხარეს hash მაგიდაზე რასაც უკავშირდება სიაში. უპირატესობა, რომელიც თუ თქვენ გაქვთ შეჯახების შორის Alice და აარონი, რას არ უკავშირდება მეორე ასეთი ადამიანი? თქვენ უბრალოდ ვანიჭებთ მას, რათა ბოლოს და ბოლოს, ან თუნდაც დასაწყისში იმ კავშირშია სიაში. და ფაქტობრივად, მოდით უბრალოდ noodle მეშვეობით რომ მხოლოდ მეორე. სად გახდის საუკეთესო გაგებით? თუ მე ჩადეთ Alice და იგი მთავრდება ზე პირველი მდებარეობა, შემდეგ ვცდილობ ჩადეთ აარონის სახელი და იქ ცხადია, შეჯახება, უნდა დააყენოს მას დასაწყისში საქართველოს უკავშირდება სიაში? სწორედ ამ დროს, პირველი მდებარეობა, ან ბოლოს? აუდიტორია: [inaudible]. დავით Malan: OK. გავიგე დასაწყისია. რატომ დასაწყისში? აუდიტორია: [inaudible]. დავით Malan: OK. ეს ანბანურ, ისე, რომ ლამაზი. ეს არის ის, კარგი ქონება. ეს გადაარჩენს მე გარკვეული დრო პოტენციურად. ეს არ მინდა ამის გაკეთება ბინარული ძებნის, მაგრამ მე შესაძლოა, სულ ცოტა შეძლებს დაარღვიოს საქართველოს მარყუჟის თუ ვხვდები, ისე, მე გზა წარსულში იყო აარონის იქნება ამ დახარისხება დაკავშირებული სიაში. მე არ დაგვრჩა დროს ეძებს ყველა გზა ბოლომდე. ასე რომ, გონივრული. რატომ სხვაგან შესაძლოა გსურთ ჩადეთ colliding სახელი ზე დასაწყისში სიაში? რა არის ეს? აუდიტორია: [inaudible]. დავით Malan: ეს შეიძლება გაგრძელდეს დიდი ხანი მისაღებად სიის ბოლოში. და სინამდვილეში, აღარ და აღარ. მეტ დასახელებას ჩადეთ, რომ იწყება, აღარ, რომ ჯაჭვის აპირებს მიიღოს. აღარ, რომ უკავშირდება სიაში აპირებდა. ასე რომ თქვენ რეალურად მხოლოდ გაყვანაა თქვენი დრო. იქნებ თქვენ უკეთესად შენარჩუნების მუდმივი ჩასმის დროს, დიდი O 1, by ყოველთვის აყენებს colliding სახელი ზე დასაწყისში უკავშირდება სია, და არა შემაშფოთებელია, ისევე შესახებ დახარისხება. რა არის საუკეთესო პასუხი? ეს გაურკვეველია. ეს ერთგვარი დამოკიდებული, თუ რა განაწილების, რა ნიმუში საქართველოს გვარები თქვენ ჩასმის. ეს არ არის აუცილებელი, ცხადია პასუხი. მაგრამ აქ, კიდევ ერთხელ, არის დიზაინი შესაძლებლობა. ასე რომ, ჩვენ მაშინ უყურებდნენ ამ რამ, რაც მართლაც დიდი შანსი ამისთვის P-ნაკრები 6. და გააცნობიეროს, თუ არ უკვე, Zamyla dives შევიდა ორივე, hash მაგიდები და ცდილობს, უფრო დეტალურად. და ვიდეო Walkthrough არის ჩართული P-ნაკრები სპეც. ეს იყო trie - T-R-I-E. და რა იყო საინტერესო შესახებ ეს იყო, რომ ქრონომეტრაჟი ეძებს სახელწოდება, ისევე როგორც Maxwell ბოლო დროს, იყო დიდი O თუ რა? რა არის ეს? აუდიტორია: რაოდენობამ წერილები. დავით Malan: პუნქტების წერილები. გავიგე ორი რამ. ხმების წერილები და მუდმივი დროში. მოდით წავიდეთ ერთად, რომ პირველი. რიგი წერილები. ასევე, ამ მონაცემების სტრუქტურას, გაწვევას, არის მიყვარს ხე, ოჯახის ხე, თითოეული რომელთა კვანძების შედგება მასივები. და იმ მასივების არიან მითითებას სხვა ასეთი კვანძების, ან სხვა ამგვარი მასივების in ხე. ასე რომ, თუ გვინდოდა შემდგომში გადაწყვეტს თუ არა Maxwell არის აქ, მე რომ ვთქვათ პირველი მასივი, ზუსტად იმ დასაწყისში ხე, ე.წ. root, თავზე trie და შემდეგ მ მაჩვენებელი, მაშინ მაჩვენებელი, მაშინ x, w, e, l, ლ. და მაშინ, როდესაც მე ვხედავ რაღაც განსაკუთრებული სიმბოლო, აღნიშნა, აქ, სამკუთხედის. კოდის დაინახავთ, გთავაზობთ, ხორციელდება bool, უბრალოდ ამბობდა დიახ ან არა, სიტყვა აჩერებს აქ. ისე, ერთხელ ჩვენ წავიდა M-A-X-W-E-L-L, იგრძნობა შვიდი, შესაძლოა, რვა თუ ჩვენ ერთი წარსულში, რვა ნაბიჯები, რათა იპოვოს Maxwell. ან მოდით ეძახით კ მაგრამ გავიხსენოთ ბოლო დროს, მე ამტკიცებდა, რომ თუ იქ რეალურად მაქსიმალური სიგრძე on სიტყვა, ისევე როგორც 40-რაღაც-უცნაური პერსონაჟი, მაქსიმალური სიგრძე გულისხმობს მუდმივი მნიშვნელობა. ასე რომ, რეალურად, დიახ, ეს ტექნიკურად დიდი O 8 ან 7, ან მართლაც დიდი O კ მაგრამ თუ არსებობს სასრული ქუდი, თუ რა K შეიძლება იყოს, ეს მუდმივი. ასე რომ, ეს არის ის, დიდი O of 1 დღის ბოლოს. არ რეალურ სამყაროში. არა, როდესაც თქვენ რეალურად დაიწყოს თვალს თქვენი საათი როგორც თქვენი პროგრამის გაშვებული. ეს აბსოლუტურად იქნება ცოტა ნელი, ვიდრე ნამდვილად მუდმივი დროს ერთი ნაბიჯია. ეს იქნება შვიდი ან რვა ნაბიჯი, მაგრამ მაინც, რომ ბევრად, ბევრად უკეთესი ვიდრე ალგორითმი, როგორიცაა დიდი ო ო, რომ დამოკიდებულია ზომის რა მონაცემთა სტრუქტურას. გავითვალისწინოთ upside აქ ჩვენ ჩადეთ მილიონი სახელები შევიდა ამ მონაცემთა სტრუქტურის, მაგრამ კიდევ რამდენი ნაბიჯები იგი აპირებს us იპოვონ Maxwell ამ შემთხვევაში? არა. ის unaffected. და დღემდე, არა მგონია, ჩვენ ვნახეთ მაგალითია მონაცემთა სტრუქტურის ან ალგორითმი, რომელიც იყო სრულიად unaffected გარე ქცევაში, რომ. მაგრამ ეს არ უნდა იყოს გასაოცარი. ეს არ შეიძლება ერთადერთი გამოსავალი ამისთვის P-ნაკრები და ეს არ არის. ეს არ არის აუცილებელი მონაცემები სტრუქტურა უნდა gravitate to, იმიტომ, რომ მოსწონს hash მაგიდები, tradeoff. რა ფასი თქვენ გადაიხადოს აქ? მეხსიერება. ვგულისხმობ, ეს ბარბაროსულ თანხის მეხსიერება. და ვერ საკმაოდ დანახვა, რადგან ავტორი ამ სურათში აშკარად truncated ყველა მასივები, და ჩვენ არ ხედავს ბევრი და B და C-ს და Q-ს და Y-ს და Z-ის ამ მასივები. მაგრამ ისინი იქ. თითოეული ეს კვანძების არის მთელი რიგი ზოგიერთი 26 ან მეტი ბაიტი, თითოეული რაც წარმოადგენს წერილში. 27 ჩვენს შემთხვევაში, ასე, რომ ჩვენ შეგვიძლია მხარი დაუჭიროს apostrophes პრობლემის ნაკრები. ასე რომ, ამ მონაცემების სტრუქტურას მართლაც, მართლაც ხშირი და კარს. და ეს მარტო შეიძლება დასრულდეს up slowing რამ ქვემოთ, ან თუნდაც რაზეც თქვენ გაცილებით მეტი სივრცე. თუმცა ისევ და ისევ, ჩვენ შეგვიძლია დავხატოთ შედარება აქ. შეგახსენებთ, ხოლო უკან, მივაღწიეთ ბევრად უფრო საინტერესო გაშვებული დროს დახარისხება როდესაც ვიყენებთ შერწყმა დალაგების, მაგრამ ფასი ვიხდიდით, რათა მივაღწიოთ ო სისტემიდან ო for შერწყმა დალაგების საჭირო, რომ ვხარჯავთ მეტი რა რესურსი? მეტი სივრცე. ჩვენ გვჭირდებოდა მეორად მასივი კოპირება ადამიანები, ისევე, როგორც ჩვენ გავაკეთეთ აქ სცენაზე. ასე რომ, კიდევ ერთხელ, ცხადად არ გამარჯვებული, მაგრამ სუბიექტური დიზაინი გადაწყვეტილება იქნეს მიღებული. ყველა უფლება. ასე რომ, როგორ ამის შესახებ? ნებისმიერ მსურველს აღიარებს, რომელიც D-Hall? OK. ასე რომ, სამი ჩვენგანი. Mather სახლი. ასე რომ, ეს არის Mather-ის სასადილო. მე დადებს ყველა სასადილო დარბაზები stacks საქართველოს ქაღალდის მოსწონს ეს. და ეს არის რეალურად წარმომადგენელი რაღაც ჩვენ აშკარად ჩანს უკვე. ჩვენ მას ფაქტიურად დასტის. და სტეკი, იმ თვალსაზრისით, თქვენი კომპიუტერის მეხსიერებაში, თუ სად მონაცემთა მიდის ხოლო ფუნქციები მიმდინარეობს მოუწოდა. მაგალითად, თუ რა სახის რამ წავიდეთ on დასტის მიმართებაში მეხსიერება ჩვენ განიხილეს ამ კვირის განმავლობაში წარსულში? რა არის ეს? აუდიტორია: კავშირი ფუნქციები. დავით Malan: მე ბოდიში. აუდიტორია: კავშირი ფუნქციები. დავით Malan: კავშირი ფუნქციები, მაგრამ კონკრეტულად, რა შიგნით თითოეული იმ ფარგლებში? რა სახის რამ? ჰო. ასე რომ, ადგილობრივი ცვლადი. ნებისმიერი გვჭირდებოდა ზოგიერთი ადგილობრივი შენახვა, ისევე როგორც არგუმენტი, ან int მე, ან int temp, ან რაც ადგილობრივი ცვლადი, ჩვენ აყენებს, რომ დასტის. და ჩვენ მას დასტის რადგან იმ layering იდეა. უბრალოდ ასეთი მატჩები ერთად რეალობას, კონცეფციის შესახებ. მაგრამ აღმოჩნდება, რომ დასტის ასევე შეგიძლიათ იქნას, როგორც მონაცემთა სტრუქტურა, ალტერნატივა მასივი, ალტერნატიული to უკავშირდება სიაში. რაღაც კონცეპტუალურად უფრო საინტერესო რომ ჯერ კიდევ შესაძლებელია განხორციელებული გამოყენებით ან იმ რამ, მაგრამ ეს სხვა ტიპის მონაცემთა სტრუქტურის მხარდამჭერი, ნამდვილად, მხოლოდ ორი ოპერაციებში. მაგრამ შეგიძლიათ დამატების შესახებ fancier თვისებები, ვიდრე ეს. მაგრამ ეს მხოლოდ საფუძვლებს - დააყენებს და საესტრადო. და იდეა ერთად სტეკი არის, რომ თუ აქ, ან მის გარეშე Annenberg იცის, tray from მეზობლად ნომრით 9 იგი. ასე რომ მხოლოდ int. მინდა დააყენებს ამ გადატანა მონაცემები სტრუქტურა, რომელიც ამჟამად თავისუფალია. მიგვაჩნია, რომ ეს ბოლოში დასტის. მე დააყენებს ეს რიცხვი 9 გადატანა დასტის, და ახლა უფლება არსებობს. მაგრამ საინტერესო ის სტეკი ის არის, რომ თუ მე ახლა მინდა დააყენებს ზოგიერთი სხვა ღირებულების, ისევე როგორც მე -17 და მე დააყენებს ამ გადატანა დასტის, მე ვაპირებ გაკეთებას მხოლოდ ინტუიციური რამ, მე მხოლოდ აპირებს იმისათვის, რომ ეს უფლება, სადაც ჩვენ ადამიანები იქნება მიდრეკილია თქმით, წლის დასაწყისში. მაგრამ რა საინტერესოა ახლა არის, როგორ მივიღებ 9 საათზე? თქვენ იცით, მე არ გარეშე გარკვეული ძალისხმევა. რა არის საინტერესო სტეკი არის, რომ დიზაინი, ეს lifo მონაცემთა სტრუქტურას. სულელური გზა, სადაც აღწერილია უკანასკნელი, პირველ გარეთ. ასე რომ, ბოლო ნომერი ამ დროს 17 წლის იყო. ასე რომ, თუ მინდა პოპ რაღაც შუქი საქართველოს დასტის, ეს შეიძლება იყოს მხოლოდ 17. ასე რომ სავალდებულო ბრძანებით ოპერაციების აქ, სადაც ბოლო პუნქტის ამ უნდა იყოს პირველი out. აქედან გამომდინარე აკრონიმი, lifo. რატომ შეიძლება ეს იყოს სასარგებლო? მათი კონტექსტში, რომელშიც ნეტავ მინდა მონაცემთა სტრუქტურის ასე? ასევე, ეს, რა თქმა უნდა სასარგებლო შიგნით კომპიუტერი. ასე რომ, ოპერაციული სისტემა აშკარად გამოიყენოს ეს მონაცემთა ამგვარი სტრუქტურა stacks. ჩვენ მოვისმენთ ასევე ვხედავთ იგივე იდეა როდესაც საქმე ვებ გვერდები. ასე რომ, ამ კვირაში და მომავალ კვირას და მის ფარგლებს გარეთ, და როგორც თქვენ დაიწყოს ახორციელებს ვებგვერდი გვერდების ენის მოუწოდა HTML, შეგიძლიათ რეალურად გამოვიყენოთ მონაცემთა სტრუქტურის მოსწონს ამ დასადგენად გვერდი არის სწორად ფორმატის. იმის გამო, რომ ჩვენ დავინახავთ ყველა ვებ გვერდების დაიცვას სახის იერარქიაში, indentation რომელიც, იმ დღის ბოლოს, იქნება ხის სტრუქტურაში ქვეშ hood. ასე რომ, უფრო, რომ სულ რაღაც ცოტა. მაგრამ ახლა, მოდით შესთავაზოს for მომენტი, თუ როგორ უნდა წავსულიყავით შესახებ წარმოადგენს რა სტეკი არის? ნება მომეცით შესთავაზოს, რომ ჩვენ განახორციელოს დასტის კოდით მოსწონს ეს. ასე რომ დასტის აპირებს აქვს შიგნით ეს ორი რამ, მასივი, სახელწოდებით ქაღალდის, უბრალოდ უნდა შეესაბამებოდეს დემო. და თითოეული ელემენტი, რომ მასივი იქნება ტიპის int. და შესაძლებლობები, სავარაუდოდ, რა? იმის გამო, რომ მე არ წერია სრული განმარტება აქ. ალბათ მაქსიმუმ ზომის მასივი. და ეს, ალბათ გამოცხადდა მკვეთრი განისაზღვროს ზედა ფაილი, ზოგიერთი სახის მუდმივ როგორც ითვალისწინებს უბრალო კაპიტალიზაცია. ასე რომ სადღაც მოცულობა განისაზღვრება როგორც მაქსიმალური ზომა. იმავდროულად, შიგნით მონაცემთა სტრუქტურის ცნობილია როგორც დასტის იქ იყოს მთელი რიცხვი მხოლოდ ცნობილია უბრალოდ ზომა. ასე რომ, თუ მე წარმოადგინოს ეს ახლა pictorially, მოდით ვივარაუდოთ, რომ ამ მთელი შავი ყუთი წარმოადგენს ჩემს დასტის. შიგნით ეს ორი ცვლადი. ამიტომ, მე ვაპირებ შევაჩერო პირველი, როგორც ზომა. ხოლო მეორე მე ვაპირებ მიაპყროს როგორც მასივი. მაგრამ შენარჩუნება რამ თანმიმდევრული, ჩვეულებრივ მე მიაპყროს მასივი მოსწონს ეს, მაგრამ ეს სახის ლამაზი თუ ჩვენ ემთხვევა რეალობას, ან ემთხვევა ფსიქიკური მოდელი. ნება მომეცით, ნაცვლად მიაპყროს მასივი ვერტიკალურად, რაც არის, კიდევ ერთხელ, მხატვრის rendition. აბსოლიტურად სულ ერთია, თუ რას არის ქვეშ hood. და ჩვენ ვთქვათ, რომ, ჩვეულებრივ, სიმძლავრის იქნება სამი. ასე რომ, ეს იქნება ადგილმდებარეობა 0, ამ იქნება ადგილმდებარეობა 1, ამ იქნება მდებარეობა 2. თუ მე მოსყიდვა ერთად სტრესი ეკუთვნოდა, რომ ვინმე მინდა ამუშავება და აწარმოებს ფორუმში აქ მხოლოდ ერთი წუთით? კარგი, ვნახე მხრივ პირველი. კარგით up. ყველა უფლება. ასე რომ, ვფიქრობ, სტივენ. კარგით up. ყველა უფლება. მაგრამ დავუშვათ ახლა ჩვენ გადახვევა პირველადი სახელმწიფო, სადაც მე ახლახან განაცხადა, დასტის, და ეს იქნება სიმძლავრის სამი. მაგრამ ზომა ჯერჯერობით არ განისაზღვრება. ქაღალდის ჯერ კიდევ არ არის დადგენილი. ასე რომ რამდენიმე კითხვებს პირველი. და ნება მომეცით, გადმოგცეთ mic ასე რომ თქვენ მიიღოს უფრო აქტიურად ამ. რა არის შიგნით ზომა ამ დროს ამ დროს, თუ ყველა მე არ კეთდება არის გამოცხადებული დასტის ერთად ერთი ხაზი კოდი? STEVEN: არ ღირს. დავით Malan: კარგი, არ არის ბევრი. ვიცით, რა არის შიგნით ზომა, ვიცით, რა არის შიგნით ამ მასივი აქ? STEVEN: უბრალოდ შემთხვევით კოდი, არა? უბრალოდ - დავით Malan: ჰო, მე ვაპირებ მას კოდექსი, მაგრამ შემთხვევით - STEVEN: სიტუაცია. დავით Malan: რამ, როგორიცაა შემთხვევით STEVEN: Bits. დავით Malan: Bits, არა? ასე რომ, ნაგვის ღირებულებები, არა? ასე რომ permutations of 0 და 1 ს. ნარჩენების წინა ჩვეულებების ამ მეხსიერებაში. და ჩვენ ნამდვილად არ ვიცით, რა ღირებულებები მათ, ასე რომ, როგორც წესი, მიაპყროს მათ კითხვის ნიშნები. ასე რომ, პირველი, რაც ჩვენ, სავარაუდოდ აპირებს გსურთ აქ - და ნება მიბოძეთ ამ სფეროში შიგნით არსებობს სახელი - ქაღალდის. რა უნდა სავარაუდოდ ინიციალიზაცია ზომა, რათა, თუ გვინდა დაიწყოს გამოყენებით ამ დასტის? STEVEN: უჯრა არის ქვე 3. დავით Malan: ასე რომ, OK. იმისათვის რომ ნათელი, მოცულობა ცხადდება სხვაგან, როგორც სამი. და ეს არის ის, რაც მე გამოყენებული გამოყოფას მასივი. ზომა აპირებს მიმართოს, თუ რამდენი ქაღალდის ამჟამად on დასტის. STEVEN: ნულოვანი. დავით Malan: ასე რომ ეს უნდა იყოს ნულოვანი. ასე რომ წავიდეთ წინ, და ნებისმიერი თითი მიაპყროს ნულოვანი ზომის. ყველა უფლება. ასე რომ, ახლა, რა შიგნით ამ აქ, ჩვენ არ ვიცით. ეს არის რეალურად მხოლოდ ნაგვის ღირებულებებს. ასე რომ, ჩვენ შეიძლება შევაჩერო კითხვის ნიშნები, მაგრამ მოდით შენარჩუნება ფორუმში სუფთა ახლა იმიტომ, რომ არა აქვს მნიშვნელობა რა არის იქ. ჩვენ არ გვჭირდება ინიციალიზაცია მასივი არაფერი, რადგან თუ ჩვენ ვიცით, რომ ზომის სტეკი შეადგენს ნულს, ასევე, ჩვენ არ უნდა ეძებს არაფერი ამ მასივი მაინც ზე ამ მომენტში. ასე რომ, ახლა ვარაუდობენ, რომ მე დააყენებს ნომერი 9 გადატანა დასტის. როგორ უნდა განახლდეს მონაცემთა სტრუქტურის შიგნით ამ შავი ყუთი? რა ღირებულებები უნდა შეცვალოს? STEVEN: ვადაში - ზომა? დავით Malan: OK. ზომა უნდა გახდეს, თუ რა? STEVEN: ზომა იქნება. დავით Malan: OK. ასე რომ, ზომა უნდა გახდეს ერთი. ასე რომ თქვენ ამის გაკეთება რამდენიმე გზა არსებობს. ნება მომეცით, გადმოგცეთ, ახლა თქვენი თითის არის საშლელი. ყველა უფლება. მაშინ ახლა თითის არის brush. ყველა უფლება. ახლა კი რა უნდა შეცვალოს, ცხადია, ამ მონაცემების სტრუქტურას? STEVEN: ჩვენ ვაპირებთ ეხლა ქვედა მდე 9. დავით Malan: 9. კარგი, კარგი. ასე რომ ჯერ კიდევ არ აქვს მნიშვნელობა, რა დროს ადგილმდებარეობა ერთი ან ორი, რადგან ისინი ნაგვის ღირებულებები, მაგრამ ჩვენ არ უნდა გადაიტვირთოთ ეძებს არსებობს, რადგან ზომა არის გვეუბნება, რომ მხოლოდ პირველი ელემენტი ფაქტიურად ლეგიტიმური. ასე რომ, ახლა მე დააყენებს 17 გადატანა სიაში. რა ხდება ამ სურათზე? STEVEN: So ზომა აპირებს მისვლას ორი. დავით Malan: OK. თქვენ eraser - oops. თქვენ eraser. STEVEN: Eraser. დავით Malan: შენ brush. STEVEN: Brush. დავით Malan: OK. და რა? STEVEN: და მერე - დავით Malan: ჩვენ მივიღებთ 17. STEVEN: ჩვენ გამყარებაში 17 თავზე, ასე - დავით Malan: კარგი, კარგი. STEVEN: - ვარდნა მას. დავით Malan ყველა უფლება. ის მიღების ადვილი. მე არ ვაპირებ, რომ დაგეხმაროთ ამ დროს. Push 22. STEVEN: შესრულებულია. ხდება eraser. მე ხდება brush. და მაშინ მე აყენებს 22. დავით Malan: 22. შესანიშნავი. ასე რომ, კიდევ ერთხელ. მე ახლა მიმდინარეობს დააყენებს გადატანა სტეკი 26. STEVEN: Ooh. Oh Gosh. თქვენ ნამდვილად დაიჭირეს me off დაცვის. დავით Malan: თქვენ არ რომ ეს მოდის? STEVEN: მე არ მინახავს ამ მოდის. შეგვეძლო თავიდან საწყის მოცულობა? დავით Malan: ეს კარგი კითხვაა. ასე რომ, ჩვენ ასეთი მოხატული საკუთარ თავს კუთხეში აქ. მართლაც არ არის კარგი გარეთ სტივენ იმიტომ, რომ ჩვენ გამოყოფილი ამ მასივი statically, ასე ვთქვათ, შიგნით მონაცემთა სტრუქტურას. და ჩვენ არსებითად მყარი კოდირებული ეს უნდა იყოს, ზომით სამი. ასე რომ, ჩვენ ვერ გადაანაწილოს იგი. ჩვენ შეგვეძლო თუ წავედით უკან, ჩვენ redefined ქაღალდის უნდა იყოს მაჩვენებელი, ჩვენ შემდეგ გამოიყენოთ malloc ხელით მეხსიერების. იმიტომ, რომ თუ ჩვენ მივიღეთ მეხსიერება დან ბევრი მეშვეობით malloc ჩვენ შეიძლება შემდეგ გასათავისუფლებლად იგი. მაგრამ სანამ ათავისუფლებს მას, შეგვეძლო გადაანაწილოს უფრო დიდი ბლოკი მეხსიერება, განაახლოს მაჩვენებელი და სხვ. მაგრამ ახლა, ეს ნამდვილად საუკეთესო შეგვიძლია. დააყენებს და საესტრადო რომლებიც სავარაუდოდ აპირებს უნდა სიგნალი რაიმე შეცდომა. ასე მაგალითად, ჩვენი განხორციელება საქართველოს ბიძგი შეიძლება დაბრუნდეს bool რომელიც ადრე დაბრუნდა ნამდვილი, ჭეშმარიტი, ნამდვილი. მაგრამ მეოთხედ, ის აპირებს დაბრუნების ცრუ, მაგალითად. ყველა უფლება. ძალიან კარგად გაკეთდეს. გილოცავთ. თქვენ მიღებული სტრესის ბურთი დღეს. [ტაში] STEVEN: დიდი მადლობა. დავით Malan: დიდი მადლობა. OK, ასე რომ ეს, როგორც ჩანს, არ არის ბევრი საქართველოს წინგადადგმული ნაბიჯი, არა? ჩვენ აღწერილი ამ მონაცემთა სტრუქტურას. ეს იყო დამაჯერებელი, არა? ოპერაციული სისტემები მომწონს. როგორც ჩანს შეიძლება მოცემული გამოუყენებია, და სხვა პროგრამებს მაინც. მაგრამ რა სულელური შეზღუდვა, რომ ჩვენ თავში ერთგვარი კვირაში ორი ლიმიტები სადაც ჩვენ არ დაფიქსირდა ზომის მასივების. ასე რომ მართლაც რამდენიმე გზა ჩვენ შეგვიძლია მოსაგვარებლად. ჩვენ შეგვეძლო დინამიურად გამოყოფს მასივი, არა მძიმე კოდირების მას, როგორც მე კეთდება აქ, არამედ ხელახლა გამოცხადების ეს, უბრალოდ უნდა იყოს მკაფიო, როგორც მსგავსი რამ. Int * ქაღალდის, არ წყვეტენ on მოცულობა ამჟამად. მაგრამ როდესაც ვაცხადებ დასტის სხვაგან ჩემს კოდი, მე მაშინ მოვუწოდებთ malloc, მიიღეთ მისამართი ბლოკი მეხსიერება, და მე ვერ დაავალოს რომ მიმართვაში ქაღალდის. შემდეგ კი, იმიტომ, რომ ეს უბრალოდ ბლოკი მეხსიერება, მე ვერ გაგრძელდება გამოყენება კვადრატულ bracket notation ჩვეულ რეჟიმში. იმის გამო, რომ მიუხედავად ერთგვარი ამ ფუნქციური ეკვივალენტს მასივების და მოცულობით მეხსიერება რომ მოვიდა უკან malloc. ჩვენ შეგვიძლია მკურნალობა ერთი, როგორც სხვა გამოყენების მაჩვენებელი არითმეტიკული ან კვადრატული ფრჩხილი notation. ასე რომ, ერთი მიდგომა. მაგრამ სხვაგვარად, როგორ შეიძლება ჩვენ შევასრულებთ იგივე მონაცემების სტრუქტურას, პოტენციურად? არა? ვგრძნობ, ჩვენ უბრალოდ მოგვარდება ამ პრობლემა, როგორიც ერთი კვირის წინ. რა იყო ამ პრობლემის მოგვარების რომ სტივენ შეუვარდნენ? ასე უკავშირდება სიები, მარჯვენა. თუ პრობლემა არის ის, რომ ჩვენ ხატვის საკუთარ თავს კუთხეში გამოიყოფა წინასწარ ძალიან პატარა მეხსიერება, რაც ჩვენ მაშინ უნდა როგორმე გაუმკლავდეს, ასევე, რატომ არა მხოლოდ თავიდან ავიცილოთ, რომ გასცეს საერთოდ? რატომ არ არის მხოლოდ გამოაცხადოს ქაღალდის უნდა იყოს მომცეთ კვანძის, Ergo უკავშირდება სია, შემდეგ კი უბრალოდ გამოყოფს ახალი კვანძების ყოველ ჯერზე სტივენ საჭირო ჯდება ნომერი შევიდა მონაცემთა სტრუქტურას. ასე რომ სურათს უნდა შეიცვალოს. ეს არ უნდა იყოს, როგორც სუფთა და როგორც მარტივია, უბრალოდ მასივი სამი ints. ახლა ეს იქნება მომცეთ struct, და რომ struct აპირებს აქვს int და მომავალი მაჩვენებელი. იგი აპირებს გამოიწვიოს მეშვეობით, რომ მაჩვენებელი კიდევ ერთი ასეთი struct to სხვა ასეთი struct. ასე რომ სურათს რომ რეალურად მიიღეთ ცოტა მესიეს. და ჩვენ მინდა არ ისრები ჩვევების ყველაფერი ერთად. მაგრამ ეს ჯარიმა, მარჯვენა, რადგან ჩვენ ვნახეთ, თუ როგორ უნდა გავაკეთოთ ეს. და კიდევ თქვენ გაქვთ კომფორტული ახორციელებს რაღაც დაკავშირებული სია, რომელიც თქვენ უნდა, თუ აირჩიოს განახორციელოს hash მაგიდა ცალკე chaining for P-ნაკრები 6, შეგიძლიათ გამოიყენოს იგი როგორც შენობა ბლოკი, ან ნივთიერება, ან Scratch საუბარი, პროცედურა, რაღაც, რომ თქვენ, თქვენ შექმნა თქვენი საკუთარი თავსატეხი ცალი რომ ამის შემდეგ შეგიძლიათ reuse. ასე რომ tradeoffs, მაგრამ პოტენციურ გზებზე რომ ჩვენ რეალურად მინახავს ადრე. ასე რომ, ხშირად, ხედავთ ამ ყველა ერთი ან ორი წელი, როდესაც Apple ავრცელებს რაღაც ახალი და ყველა გიჟები ადამიანები გამოდიან გარეთ Apple შესანახად შეძენა მათი მარგინალური განაახლოს on აპარატურა. ამას, ეს კარგია, რადგან მე ვარ ერთ იმ ხალხს. ასე რომ, თუ რა სახის მონაცემების სტრუქტურა შეიძლება წარმოადგენს ეს რეალობა? ისე, მოდით დავარქვათ მდგომ, ხაზი. ასე რომ, დიდი ბრიტანეთის რომ მას, როგორც წესი, მდგომ მაინც, ამიტომ ლამაზი სახელი. ხოლო ორი ოპერაცია, მდგომ ხელს უწყობს ჩვენ ამას დავარქმევთ enqueue ოპერაცია და dequeue ოპერაცია, რაც მსგავსი სულის დააყენებს და საესტრადო. უბრალოდ ერთგვარი განსხვავებული კონვენცია, რასაც ჩვენ მოუწოდებდა ამ. მაგრამ enqueue რაღაც იმას ნიშნავს, რომ დაამატოთ ან ჩადეთ დისკი მონაცემებით სტრუქტურა. დან dequeue ნიშნავს ამოიღონ იგი. მაგრამ იმის გამო, რომ სტეკი იყო lifo მონაცემები სტრუქტურა, მდგომ არის პირველი, პირველი out მონაცემთა სტრუქტურას. თუ თქვენ ხართ პირველი პირი ხაზი, თქვენ იქნება პირველი პირი მისაღებად გარეთ ხაზი და ყიდვა თქვენი მოწყობილობა. წარმოიდგინეთ, რამდენად დაარღვიოს ეს ხალხი იქნება თუ ვაშლის ნაცვლად გამოიყენება დასტის, ამისთვის მაგალითად, განახორციელოს კრეფა up თქვენი ახალი სათამაშო. ასე რომ რიგები აზრი, რა თქმა უნდა, და ჩვენ შეიძლება ვიფიქროთ, ყველა სახის განცხადებები, სავარაუდოდ, for რიგები, განსაკუთრებით მაშინ, როდესაც გსურთ სამართლიანობა. ასე რომ, როგორ შეიძლება ჩვენ განახორციელოს ეს როგორც მონაცემთა სტრუქტურა? ისე, მე ვთავაზობ, რომ ჩვენ შეიძლება უნდა გავაკეთოთ, რომ ამ გზით. ამიტომ, მე ვაპირებ ახლა უკვე ნომრები. ასე რომ, ჩვენ გავაგრძელებთ მარტივი და არა აუცილებლად გაიგო თვალსაზრისით ქაღალდის. უბრალოდ ნომრები, რომ ხალხს მიღებული. სიმძლავრე აპირებს, კიდევ ერთხელ, დაფიქსირება საერთო რაოდენობის ხალხი, რომ შეიძლება იყოს ამ ხაზის, როგორც სამი ან რაც არ უნდა სხვა ღირებულების. მაგრამ მე ვთავაზობ, რომ მე უნდა შეასრულოს სიმღერა არა მარტო ზომის მდგომ, რამდენი რამ არის მასში. ასე რომ, ზომა არის მიმდინარე ზომა, მოცულობა მაქსიმალური ზომის. უბრალოდ, კიდევ ერთხელ, ნომენკლატურა by კონვენციას. რატომაა დამატებითი int შიგნით საქართველოს მდგომ შენარჩუნება სიმღერა, თუ ვინ არის ამ წინ ხაზი? რატომ უნდა გავაკეთოთ, რომ ამ შემთხვევაში? ისე, როგორ არის ამ სურათში შეიცვლება? მე ალბათ reuse საუკეთესო ამ სურათს. ნება მომეცით წავიდეთ წინ და წაშლას რა აქ. ჩვენ მოგაწვდით ამ ოდნავ სხვა სახელი აქ. მოდით, თავი დაეღწია 17, მოდით, თავი დაეღწია საქართველოს 9, მოდით თავი დაეღწია 3. და მოდით დაამატოთ კიდევ ერთი რამ. მე ვთავაზობ, რომ მე უნდა შევინარჩუნოთ სიმღერა წინ სია, რომელიც მხოლოდ იქნება int ასევე. და ჩვენ ვაპირებთ, რომ შევინარჩუნოთ ის მარტივი. არ უკავშირდება სიაში ახლა. ჩვენ ამას ვაღიარებთ, რომ ჩვენ ვაპირებთ bump წინააღმდეგ ზომას. მაგრამ რას მსურს, რომ მოხდება ამ დროს? ამიტომ ვარაუდობენ, I წავიდეთ წინ და პირველი პირი მოდის ხაზი, და ეს რიცხვი 9. ჩვენ გვყავს სტრესი ბურთები. შემიძლია მოიპაროს, ვთქვათ, ორი ან სამი ადამიანი? ერთი, ორი, სამი? კარგით up. მარჯვნივ წინ, რადგან ჩვენ ეს ერთი სწრაფად. თითოეული თქვენგანი არის იქნება გულშემატკივართა ბიჭი ხაზის Apple. თქვენ არ იქნება მიღების Apple ტექნიკის დასასრულს ამ თუმცა. ყველა უფლება. ასე რომ თქვენ ნომერი 9, თქვენ ნომერი 17, ნომერი 22. ეს არის უკანონო ციფრები, ისევე როგორც სტუდენტი პირადობის მოწმობა ან whatnot. ხოლო სულ ერთი წუთით, დავიწყოთ უნდა დაიწყოს დასძინა რამ. და მე აწარმოებს საბჭოს აქ ამ დროს. ასე რომ, ამ შემთხვევაში, მე ინიციალიზაცია წინ რომ იყოს - მე რეალურად ნამდვილად არ აღელვებს, თუ რა წინ არის, იმიტომ, რომ ზომა არის ნულოვანი. ასე რომ, ეს შესაძლოა, ასევე უბრალოდ იყოს კითხვის ნიშნის. ეს არის ყველა კითხვის ნიშნები. ასე რომ, ახლა ჩვენ დავიწყოთ რეალურად ვხედავ რაღაც ხალხის უგულებელყოფა up at მაღაზია. ასე რომ, თუ ნომერი 9, თქვენ პირველი იქ დილის 5 საათზე, წავიდეთ წინ და გამოდიან, ან ღამეს. OK. ასე რომ, ახლა 9 აქ არის. ასე რომ 9 არის წინ სიაში. ამიტომ, მე ვაპირებ წავიდეთ წინ და განახლება ზომა არსებული მონაცემების სტრუქტურა არ უნდა იყოს 0 აღარ, მაგრამ უნდა იყოს 1. მე ვაპირებ დააყენოს 9 საათზე წინ სიაში. ნება მომეცით წავიდეთ წინ და გადართვის ეკრანზე ასე რომ, ჩვენ ვხედავთ, წარსული გვაქვს. ახლა კი რა მინდა დააყენოს at წინ? მე ვაპირებ შენარჩუნება სიმღერა რომ წინ მდგომ ახლავე არის ადგილმდებარეობა 0. იმის გამო, რომ ის, რაც მომავალ მოხდება? ასევე, ვარაუდობენ, ახლა მე enqueue 17 ასევე. ასე რომ hop შეესაბამება არსებობს. ისევ და ისევ, ერთგვარი კარი მაღაზია იქნება აქ. ასე რომ, ახლა მე დასძინა 17. და მიუხედავად იმისა, ამ ბიჭებს ბლოკავს ეკრანზე, რომ კარგადაა, იმიტომ, რომ ჩვენ ვხედავთ მას აქ. ბოდიში. აუდიტორია: ჩვენ შეგვიძლია გადაადგილება - დავით Malan: არა, რომ კარგადაა. ძალიან დიდ აქ. ასე რომ 17 არის შიგნით მდგომ. მე უნდა განახლდეს, რაც სფეროებში არის, თუმცა? კარგი, აუცილებლად ზომა. და რა ჩაყენება? OK, არ. ფრონტის არ უნდა შეცვალოს, რადგან განსხვავებით დასტის, ჩვენ მინდა, რომ შევინარჩუნოთ სამართლიანობა. ასე რომ, თუ 9 წავიდა პირველი, ჩვენ გვინდა 9 როგორც პირველი გარეთ ხაზი და შევიდა მაღაზიაში. ფაქტობრივად, ვნახოთ, რომ. სანამ ჩვენ ჩადეთ 22, მოდით წავიდეთ წინ და dequeue 9. რა არის შენი სახელი ისევ? აუდიტორია: Jake. დავით Malan: Jake აპირებს უნდა dequeued არის. ასე რომ, თქვენ ფეხით შევიდა მაღაზიაში. და ვიტყვი, რომ მაღაზია არის იქ. ასე რომ, ახლა, რა სჭირდება - dit-dit-dit, რა უნდა მოხდეს ახლა? დიზაინი გადაწყვეტილება. ასე რომ, არა ცუდი ინსტიქტი, მაგრამ - რა არის შენი სახელი ისევ? აუდიტორია: დავით. დავით Malan: დავით. ასე რომ, რა დავით გაკეთება? იგი ცდილობდა სახის დაფიქსირება მონაცემები სტრუქტურა და გადაადგილება მისი ადგილსამყოფელი შევიდა Jake ყოფილი ადგილას. და ეს ჯარიმა, თუ ჩვენ სურვილი მიიღოს, რომ როგორც შესრულების დეტალურად. მაგრამ პირველი, მოდით განაახლოს მონაცემები სტრუქტურა სანამ ჩვენ გაგვაჩნია. იმის გამო, რომ მე არ liking იდეა ყველა ადამიანი გადავიდა ამ მხრივაც. ეს არ არის დიდი გარიგება თუ დავით აკეთებს იგი ერთი ნაბიჯია, მაგრამ კვლავ, ვფიქრობ, უკან როდესაც ჩვენ გვქონდა რვა მოხალისეები ეტაპზე და ჩვენ გავაკეთეთ, როგორიც ჩასაგდები დალაგების, სადაც ჩვენ მოუწია დაწყება მოძრავი ყველას გარშემო. ეს მივიღე ძვირი, არა? ეს მაიძულებს cringe შესახებ დიდი O საქართველოს N, დიდი ო ო Squared ერთხელ. ეს არ გრძნობს თავს, როგორიც არის იდეალური შედეგს. მოდით უბრალოდ განაახლოს ეს. ასე ზომის მდგომ აღარ არის 2. ეს ახლა უბრალოდ 1. მაგრამ მე ახლა განაახლებს რაღაც მე არ განაახლებს ადრე, წინ სიაში. მე ვერ, უბრალოდ ამბობენ, რომ ადგილმდებარეობის 1? ასე რომ, ახლა ჩვენ გვაქვს ნაგვის მნიშვნელობა, ნაგვის მნიშვნელობა, და დავითს შუა ამ ნაგავი. მაგრამ მონაცემთა სტრუქტურის ჯერ კიდევ უცვლელი. და სინამდვილეში, არც კი უნდა შეცვლის Jake ყოფილი ნომერი 9, რადგან ახსოვს. მე მაქვს საკმარისი ინფორმაცია ახლა ზომა, რომელიც მე ვიცი თუმცა ერთი პირი ამ მდგომ. და ვიცი, რომ ეს პირი არის ადგილმდებარეობა 1, არ 0. არ ვგულისხმობ. ამგვარად 1 ასევე. ასე რომ, მონაცემთა სტრუქტურის მაინც OK. ისე, რა მოხდება შემდეგ? მოდით enqueue - რა არის შენი სახელი? აუდიტორია: Callen. დავით Malan: Callen. მოდით enqueue Callen და 22 ახლა მდგომ. ასე რომ, ახლა რა უნდა შეცვალოს აქ? ფრონტის არ აპირებს იცვლება, რა თქმა უნდა. ზომა აპირებს შეცვალოს იყოს 2 ერთხელ. ხოლო 22 მთავრდება აქ, 9 არის რჩება, მაგრამ ეფექტურად ნაგვის ღირებულება არის. უბრალოდ remnant of Jake წარსულში. ასე რომ, ახლა რა მოხდება თუ მე dequeue დავით? ერთი ბოლო ოპერაცია, dequeue დავით. ჩვენ ვერ გადაიტანოს, მაგრამ მე ვთავაზობ მოდით ამის გაკეთება, როგორც პატარა, როგორც ეს შესაძლებელია. ახლა ჩემი მონაცემთა სტრუქტურის მიდის უკან ზომა 2 დან 1. მაგრამ წინ მდგომ ახლა ხდება 2. მე არ უნდა შეცვალოს ამ ნომრებზე მხოლოდ ამჟამად, რადგან ისინი მხოლოდ ნაგვის ღირებულებებს. მაგრამ ახლა რა ხდება? დავუშვათ, მე enqueue თავს, 26? ვგრძნობ, როგორიც მე ეკუთვნის მეტი აქ. ასე რომ, მე მიმდინარეობს enqueued. ასე, რომ სახის ეკუთვნის აქ. და მიუხედავად იმისა, არა საკმაოდ ვაფასებთ ამ ვიზუალურად სცენაზე, იმიტომ რომ ჩვენ გვაქვს უამრავი ოთახი, მინდა არ შეიძლება ვდგავართ აქ, რატომ? აუდიტორია: თქვენ ფარგლებს გარეთ. დავით Malan: Right. მე ფარგლებს გარეთ. მე ინდექსირებული მიღმა ფარგლებში ამ მასივი. მე ნამდვილად უნდა იყოს ერთი სამი შესაძლო ადგილებში. ახლა, სად არის ყველაზე ბუნებრივი წასვლა? მე ვთავაზობ, ჩვენ leveraged კვირაში ერთი შეასრულა. თავდაცვის სამინისტროს ოპერატორი, პროცენტი. იმის გამო, რომ მე ტექნიკურად იდგა ადგილმდებარეობა 3, მაგრამ მე ნამდვილად 3 mod მოცულობა, ასე 3, პროცენტი ნიშანი, 3 - მოცულობა არის 3. რა არის ეს? რა არის დარჩენილი, როდესაც თქვენ დაყოფის 3 3? 0. ასე რომ აყენებს მე იყო Jake იყო, რომელიც რეალურად კარგი. ასე რომ, ახლა განხორციელება ამ რამ აპირებს იყოს ცოტა თავის ტკივილი. ეს მართლაც მხოლოდ ერთი ხაზი საქართველოს თავის ტკივილი, საქართველოს კოდი. მაგრამ მაინც ახლა არის ნაგავი მნიშვნელობა, მაგრამ არსებობს ორი ლეგიტიმური ints აქ. და მე აცხადებენ, რომ ახლა ჩვენ გავაკეთეთ ზუსტად ის, რაც ჩვენ უნდა გავაკეთოთ ისე, სანამ შევცვლით იმას, რაც Jake-ს ღირებულება იყო, რომ 26. ახლა ჩვენ გვაქვს საკმარისი ინფორმაცია ჯერ კიდევ ერთიანობის შენარჩუნებას ამ მონაცემების სტრუქტურას. ჩვენ ჯერ კიდევ სახის out of luck როდესაც ჩვენ გვინდა ჩადეთ ოთხი და მეტი საერთო ელემენტები, მაგრამ შემიძლია, სულ მცირე, მიიღოს საკმაოდ ეფექტიანი გამოყენების კონსტანტის დრო, ფაქტობრივად. მე არ მაქვს ფიქრი გადავიდა ყველას, როგორც დავითის მიდრეკილება იყო. ნებისმიერი შეკითხვა stacks, ან ამ მდგომ? აუდიტორია: არის მიზეზი იმისა, გჭირდებათ ზომა ასე რომ თქვენ იცით სად უნდა ჰქონდეს პირი? დავით Malan: ზუსტად. მე უნდა იცოდეს ზომის მასივი იმიტომ, რომ მე უნდა იცოდეს, თუ რამდენად ბევრი ეს ფასეულობები ლეგიტიმური, და რომ ვიპოვი, სად უნდა დააყენოს მომდევნო. ზუსტად. ზომა არის - რეალურად, ჩვენ არ განაახლოს ეს არის. მე დასძინა თავს ზე 26. ზომა არის, არა 1, არამედ 2. ასე რომ, ახლა ამ მართლაც მეხმარება იპოვოს ხელმძღვანელი სია, რომელიც არ არის 0, არ 1, მაგრამ 2. წინ სია მართლაც ნომერი 22. იმის გამო, რომ იგი პირველი, ამიტომ იგი უნდა უნდა უშვებდნენ მაღაზია ჩემს წინაშე, მიუხედავად იმისა, რომ ვიზუალურად მე დგანან უფრო ახლოს მაღაზია. ყველა უფლება? რაუნდი ტაში ამ ბიჭებს და ჩვენ მისცეს მათ გარეთ არსებობს. [ტაში] დავით Malan: მე ვერ დავუშვებთ თქვენ გაქვთ პანელში. ჩვენ ვერ ვხედავთ, თუ რა მოხდება, თუ გსურთ, მაგრამ იქნებ არა. ყველა უფლება. ასე რომ, ის, რაც ახლა აკეთებს, რომ დაგვტოვებთ? ისე, მინდა შესთავაზოს, რომ არსებობს რამდენიმე სხვა მონაცემები სტრუქტურების შეგვეძლო დაიწყება და დასძინა, რომ ჩვენი ინსტრუმენტი ნაკრები, რომლებიც რეალურად, საკმაოდ, საკმაოდ აქტუალურია, როგორც ჩვენ dive შევიდა ვებგვერდი პერსონალი. რაც კიდევ ერთხელ, რაღაც სახის კავშირი ხეები სახით რაღაც მოუწოდა DOM, დოკუმენტი ობიექტის მოდელი. მაგრამ ჩვენ დავინახავთ მეტი ისიც აღნიშნა, რომ ხანგრძლივი. ნება მომეცით შესთავაზოს definitionally, რომ ჩვენ მოვუწოდებთ ხე ეხლა მოგეხსენებათ, როგორც მეტი ოჯახის ხე, სადაც თქვენ გარკვეული წინაპრების ზე ფესვები ხე. პატრიარქალურ ან matriarch ზე ძალიან თავზე ხე. მათ გარეშე მეუღლე, ამ შემთხვევაში. მაგრამ ჩვენ ახლა აქვს, რაც ჩვენ ამას დავარქმევთ ბავშვები, რომლებიც კვანძების, რომ დაკიდება off მარცხენა ბავშვის ან უფლება ბავშვი, ისარი როგორც გამოსახული აქ. სხვა სიტყვებით,, ხის მონაცემთა სტრუქტურის კომპიუტერული, ხე ნულოვანი ან მეტი კვანძების. თუ მას აქვს მინიმუმ ერთი კვანძის, რომ ე.წ. root. ეს რამ ვიზუალურად, რომ ჩვენ მიაპყროს ზედა. და ეს კვანძი, ისევე როგორც სხვა ნებისმიერი კვანძის, შეიძლება ნულოვანი, ერთი, ან ორი, ან სამი, ან თუმცა ბევრი ბავშვი მონაცემთა სტრუქტურის უჭერს მხარს. ამ შემთხვევაში, ძირი, შენახვისა ღირებულება ერთ და ორი შვილი, 2 და 3, ასე რომ, ჩვენ ზოგადად მოვუწოდებთ 2 მარცხენა ბავშვი და 3 უფლება შვილი. და მაშინ, როდესაც მივიღებთ ქვემოთ 5, 6, და 7, 6, შესაძლოა ეწოდოს შუა შვილი. თუ თქვენ გაქვთ ოთხი შვილი, იგი იღებს გაუგებარია. ასე რომ, ჩვენ შეწყვიტოს გამოყენებით, ასეთი საქართველოს მალსახმობი სიტყვიერი შეურაცხყოფა. მაგრამ ეს მართლაც მხოლოდ ოჯახის ხე. და ფოთლები აქ კვანძების, რომ თავად არ მყავს ბავშვები. მათ დაკიდება off ბოლოში ხე. ასე რომ, როგორ შეიძლება ჩვენ განახორციელოს ხე, ახლახანს ორი შვილი მაქსიმალურად? ჩვენ ამას ეძახით ორობითი ხე. ბი ერთხელ რაც იმას ნიშნავს, ორი, ამ შემთხვევაში, ისევე, როგორც ორობითი. ასე რომ მას შეუძლია ნულოვანი, ერთი, ან ორი შვილი მაქსიმალურად. მე შესთავაზოს, რომ ჩვენ განახორციელოს კვანძის რომ სტრუქტურის int n, და შემდეგ ორი მითითებას, ერთი მოუწოდა დატოვა, ერთი მოუწოდა უფლება. მაგრამ ეს მხოლოდ ლამაზი თვითნებური კონვენციები. და რა ლამაზი არის, განსაკუთრებით თუ სახის იბრძოდა კონცეპტუალურად ერთად უკან, ან ეგონა, რომ ეს არ იყო ნამდვილად გამოსავალი არაფერი, მით უმეტეს, თუ შეიძლება ამოიწურა მეხსიერება. ახლა, როდესაც ჩვენ ვსაუბრობთ მონაცემები სტრუქტურები და ალგორითმები, რომელიც საშუალებას us to traverse და მანიპულირება მათ, გამოდის, რომ უკან ბრუნდება წელს ბევრად უფრო მყარი თუ არ ლამაზი გზა. ასე რომ, ეს მე ვთავაზობ არის განხორციელება საქართველოს ძებნის ფუნქცია. იმის გათვალისწინებით, ორ საშუალებებით - ასე ვფიქრობ, როგორც შავი ყუთი. იმის გათვალისწინებით, ორ საშუალებებით, n, int, და მომცეთ ხე, მომცეთ კვანძის, ან მართლაც ძირი ხე, I აცხადებენ, რომ ამ ფუნქციას შეუძლია დაბრუნდეს ჭეშმარიტი ან ცრუ, რომ ღირებულება ო არის შიგნით ამ ხე. რა არის შიგნით ამ შავი ყუთი? ასევე, ოთხ ფილიალს. პირველი უბრალოდ ამოწმებს. თუ ხე null, დააბრუნებს false. თუ არ არსებობს კვანძის, არ არსებობს n, არ არსებობს ნომერი, დააბრუნებს false. თუ იმისა, N, ღირებულება ვეძებთ ამისთვის, ნაკლებია, ვიდრე ხე arrow n, და უბრალოდ უნდა იყოს მკაფიო, რას ნიშნავს, როდესაც ვწერ ხე და შემდეგ arrow notation, ო? ზუსტად. ეს იმას ნიშნავს, რომ dereference მაჩვენებელი მოუწოდა ხე. წავალთ, და შემდეგ მიიღოს შიგნით რომ კვანძის და მიიღეთ თავისი სფეროს მოუწოდა ო. და მაშინ შედარების ფაქტობრივი ო რომ იყო გადავიდა ძებნა წინააღმდეგ. ასე რომ, თუ n ნაკლებია, ვიდრე, ო ღირებულება in tree კვანძის თავად, ასევე, რას ნიშნავს ეს? ეს იმას ნიშნავს, არაფერი ერთი შეხედვით. არა? ისევე, როდესაც თქვენ მასივი ღირებულებები, თქვენ ალბათ მინდა ვრცელდება ორობითი ძებნის სახით გათიშე და დაპყრობას. მაგრამ რა ვარაუდი, არც ჩვენ უნდა გააკეთოს ბინარული ძებნის მუშაობს ამ სატელეფონო წიგნი და ადრე მაგალითები? როგორ იყოს დახარისხებული. მოდით დახვეწა განსაზღვრება ხე აქ არ უნდა იყოს მხოლოდ ხე, რომელიც შეიძლება აქვს ნებისმიერი რაოდენობის შვილი. არა მხოლოდ ორობითი ხე, რომელიც შეიძლება აქვს 0, 1, ან 2 მაქსიმალურად. მაგრამ, როგორც ბინარული ძებნის ხე, ან BST, რაც არის ლამაზი გზა ამბობდა binary tree ისეთი, რომ ყველა კვანძის ნახვა მარცხენა ბავშვის ამჟამად, არის ნაკლებია, ვიდრე კვანძის. და ყველა კვანძის უფლება ბავშვი, თუ დღემდე, უფრო ვიდრე კვანძის თავად. ასე რომ, სხვა სიტყვებით, თუ იყო მიაპყროს ხე out, ყველა ნომრები ყურადღებით დაბალანსებული მოსწონს ეს ასე, რომ თუ თქვენ გაქვთ 55 როგორც root, 33 შეიძლება მისი მარცხენა იმიტომ, რომ ნაკლები 55. 77, მივიდეს მისი უფლება, რადგან ეს უფრო მეტია, ვიდრე 55. მაგრამ ახლა შეამჩნია, იგივე განმარტება, ეს რეკურსიული განმარტება სიტყვიერი, უნდა მიმართონ 33. 33 მარცხენა ბავშვის ნაკლები უნდა იყოს იგი, და 33 მარჯვენა შვილი, 44 წლის, უნდა იყოს აღემატება მას. ასე რომ, ეს ორობითი ძებნის ხე, მე ვთავაზობ, გამოყენებით ცოტა უკან, ჩვენ შეგვიძლია ახლა მოვძებნოთ ო. ასე რომ, თუ n ნაკლებია, ვიდრე ღირებულება ო, რომ მიმდინარე კვანძის, მე ვაპირებ წასვლა წინ და punt, ასე ვთქვათ, და მხოლოდ დაბრუნების მიუხედავად პასუხი of ეძებს ო on ხე მარცხენა შვილი. გავითვალისწინოთ, კიდევ ერთხელ, ამ ფუნქციის მხოლოდ ელოდება კვანძის ვარსკვლავი, მომცეთ კვანძის. ასე რომ აუცილებლად შემიძლია მხოლოდ ამის გაკეთება ხე arrow მარცხენა, რაც გამოიწვევს ჩემთვის კიდევ ერთი კვანძის. მაგრამ რა არის ის, რომ კვანძის? ასევე, აღნიშნული დეკლარაცია, მარცხენა არის მხოლოდ მაჩვენებელი, ისე, რომ მხოლოდ ნიშნავს მე გავლით რომ ძებნის ფუნქცია სხვადასხვა მაჩვენებელი, კერძოდ ერთი, რომელიც წარმოადგენს ჩემი მარცხენა ბავშვის ხე. ასე რომ, ამ შემთხვევაში, მომცეთ 33, თუ ეს არის ჩვენი ნიმუში შეტანის იმავდროულად, თუ ო მეტია ღირებულება n ზე მიმდინარე კვანძის in ხე, მაშინ მე აპირებთ წავიდეთ წინ და punt სხვა მიმართულებით და უბრალოდ ამბობენ, მე არ ვიცი, თუ ამ მნიშვნელობის N არის ხე, მაგრამ მე ვიცი, თუ ეს არის, ეს არის ქვემოთ ჩემს მარჯვენა ფილიალი, ასე ვთქვათ. ასე რომ, მინდა გითხრათ, რეკურსიული მოძებნოს, გავლის ო ერთხელ, მაგრამ გადადის მომცეთ ჩემი უფლება შვილი. სხვა სიტყვებით, თუ ვარ ამჟამად 55 და მე ვეძებ 99, მე ვიცი, რომ 99 მეტია 55, ასე რომ, ისევე, როგორც მე დახიეს სატელეფონო წიგნი კვირის წინ და ჩვენ წავიდა, ისევე ვართ ჩვენ აპირებს წავიდეს უფლება აქ. და მე არ ვიცი, თუ ეს ჩემს უფლება ბავშვი, და ეს არ არის, 77 არის, მაგრამ მე ვიცი, რომ ამ მიმართულებით. ამიტომ, მე მოვუწოდებ ძებნა ჩემი უფლება ბავშვი, 77, და ნება ძებნის ფიგურა out from არსებობს თუ 99 ამ თვითნებური მაგალითად, ფაქტობრივად, არ არსებობს. სხვაგან, რა საბოლოო შემთხვევაში? თუ ხე null არის ერთ შემთხვევაში. თუ n ნაკლებია, ვიდრე მიმდინარე კვანძის ნახვა ღირებულება არის კიდევ ერთი შემთხვევა. თუ n მეტია მიმდინარე კვანძის ღირებულების არის მესამე შემთხვევაში. რა არის მეოთხე და საბოლოო შემთხვევაში? მე ვფიქრობ, ჩვენ გარეთ შემთხვევებში, არა? ეს უნდა იყოს რომ n in მიმდინარე კვანძის, რომ მე სხვა. ასე რომ, თუ მე ეძებს 55 ამ ეტაპზე ამბავი, რომ ფილიალი ხე დაბრუნდნენ მართალია. რა არის საინტერესო ისაა, რომ ჩვენ რეალურად, განსხვავებით კვირის წარსულში, ჩვენ ტიპის საქართველოს აქვს ორი ბაზა შემთხვევაში. და ისინი არ უნდა იყოს ყველა ზედა. რა არის ბაზა შემთხვევაში, რადგან თუ ხე null, იქ არაფერი უნდა გააკეთოს. უბრალოდ დაბრუნების მყარი კოდირებული ღირებულება ყალბი. ქვედა ფილიალი სახის ჩვეულებრივ, რომლის მიხედვითაც, თუ ჩვენ შემოწმდება null ჩვენ შეამოწმა, თუ ეს უნდა იყოს წავიდა, მაგრამ ეს არ უნდა იყოს, ჩვენ შემოწმდება თუ ის უნდა იყო მართალი, მაგრამ ეს არ უნდა იყოს, ნათლად უნდა იყოს უფლება, სადაც ჩვენ ვართ. სწორედ ბაზის შემთხვევაში. ასე რომ ორი რეკურსიული შემთხვევებში sandwiched იქ ცენტრიდან. მაგრამ მე ვერ დავწერე ამ გარეშე. უბრალოდ ეგონა, რომ ეს ერთგვარი იგრძნო ბუნებრივი პირველ შემოწმება შესაძლებელია შეცდომა, მონიშნეთ დატოვა, მონიშნეთ უფლება, მაშინ ვარაუდობენ, რომ თქვენ იმ კვანძის თქვენ რეალურად ეძებენ. რატომ შეიძლება ეს იყოს სასარგებლო? გამოდის, - და ნება მომეცით გადასვლა teaser აქ არის ამ ინტერნეტში. ჩვენ ვაპირებთ დაიწყება გამოყენებით არ პროგრამირების ენა, პირველ რიგში, მაგრამ markup ენაზე. Markup ენის ერთ, რომ მსგავსი სულითა პროგრამირების ენა, მაგრამ ეს არ გაძლევთ უნარი გამოხატონ საკუთარი თავის ლოგიკურად. ეს მხოლოდ გაძლევთ უნარი გამოხატონ საკუთარი თავის სტრუქტურულად. სად გსურთ დააყენა რაღაც გვერდზე, ვებ გვერდზე? რა ფერის გინდათ, რათა ის? რა შრიფტი გნებავთ, რათა ის? რა სიტყვა გააკეთებს რეალურად მინდა ვებ გვერდზე? ასე რომ, markup ენაზე. მაგრამ ჩვენ ძალიან სწრაფად დანერგვა JavaScript, რომელიც სრულფასოვანი პროგრამირების ენაზე. მსგავსი syntactically გამოჩენა to C, მაგრამ ეს თქვენ გარკვეული ლამაზი, უფრო ძლიერი, უფრო მომხმარებლის მეგობრული ფუნქციები. ხოლო ერთი იმედგაცრუებები, ამ წერტილი სემესტრის რომ ჩვენ მალე განახორციელოს speller გაცილებით ნაკლები ხაზი კოდი გამოყენებით სხვა ენებზე ვიდრე C თავად საშუალებას, არამედ მიზეზი ნახვა ჩვენ მალე მესმის. ეს იქნება პირველი ასეთი ვებ გვერდზე. ეს იქნება სრულიად underwhelming, პირველი მოგვცემს. ეს იქნება უბრალოდ, Hello World. მაგრამ თუ მინახავს იგი ადრე, ეს არის HTML, ჰიპერტექსტის მარკირებას ენა. თუ გარკვეული მენიუს ვარიანტი ყველაზე ნებისმიერი ბრაუზერი, ნებისმიერ ვებ გვერდზე on ინტერნეტით, ხედავთ HTML რომ ზოგიერთი ადამიანი მისწერა შექმნა, რომ ვებ გვერდზე. და ეს, ალბათ, არ გამოიყურება, როგორც მოკლე ან როგორც გარღვევა, როგორც ეს. მაგრამ ეს მოჰყვება ნიმუში ამ ღია კრონშტეინები და დახრილ ხაზებს და წერილები და პოტენციურად ნომრები. მეგონა, მე მინდა გადმოგცეთ teaser თუ რა თქვენ ვერ გააკეთებს მიღების შემდეგ CS50. ნება მომეცით წასვლა cs.harvard.edu / ძარცვა, ჩვენი საკუთარი Rob Bowden-ს მთავარ გვერდზე. ამის შესახებ მან ჩვენთვის. ასე რომ მალე შეძლებს გაგვაჩნია. ასევე, რა მოისმინა დღეს დილით - რა გსმენიათ ამ დილით - [Hamster საცეკვაო მუსიკა] - You'll შეძლებს, რათა ეს. ეს გველოდება ოთხშაბათს. ჩვენ ვნახავთ მაშინ. [Hamster საცეკვაო მუსიკა] დავით Malan: მომდევნო CS50 -