დინამიკები 1: ყველა უფლება, ასე რომ, ჩვენ უკან. კეთილი CS50. ეს არის ბოლომდე კვირაში შვიდი. ასე რომ გავიხსენოთ, რომ ბოლო დროს, ჩვენ დავიწყეთ ეძებს ოდნავ უფრო დახვეწილი მონაცემთა სტრუქტურები. მას შემდეგ, რაც დღემდე, ყველა გვქონდა ნამდვილად ჩვენს ხელთ არსებული იყო ეს მასივი. მაგრამ სანამ ჩვენ გაუქმება მასივს როგორც არ ყველა რომ საინტერესო, რომელიც მართლაც ფაქტობრივად, რა pluses ამ მარტივი მონაცემები სტრუქტურა დღემდე? რა არის ეს კარგად? იმდენად, რამდენადაც ჩვენ ვნახეთ? რას მივიღე? არაფერი. სტუდენტი: [inaudible]. დინამიკები 1: რა არის ეს? სტუდენტი: [inaudible]. დინამიკები 1: ფიქსირებული ზომა. OK, რატომ არის ფიქსირებული ზომის კარგ თუმცა? სტუდენტი: [inaudible]. დინამიკები 1: OK, ამიტომ ეფექტური გრძნობა, რომ შეგიძლიათ გამოყოფს ფიქსირებული თანხის სივრცეში, რომელიც იმედია სწორედ იმდენი სივრცეში, როგორც თქვენ გსურთ. ასე რომ, შესაძლოა, სრულიად პლუს. რა არის კიდევ ერთი up მხარეს მასივი? ჰო? სტუდენტი: [inaudible]. დინამიკები 1: All - ბოდიში? სტუდენტი: [inaudible]. დინამიკები 1: All ყუთები ხსოვნას ან შემდეგ ერთმანეთს. და ეს სასარგებლოა - რატომ? ეს საკმაოდ ასეა. მაგრამ როგორ შეიძლება ჩვენ გამოეყენებინათ, რომ ჭეშმარიტება? სტუდენტი: [inaudible]. დინამიკები 1: კერძოდ, ჩვენ შეგვიძლია შენარჩუნება სიმღერა სადაც ყველაფერი მხოლოდ იცის, ერთ მისამართზე, კერძოდ მისამართი პირველი byte, რომ ბლოკი მეხსიერება. ან იმ შემთხვევაში, ტექსტი, მისამართი პირველი char, რომ მხოლოდ. და იქიდან, ჩვენ შეგვიძლია მოვძებნოთ ბოლოს სიმებიანი. ჩვენ შეგვიძლია მოვძებნოთ მეორე ელემენტის, მესამე ელემენტს და სხვ. ასე რომ, მიეცით გზა, სადაც აღწერილია, რომ ფუნქცია არის ის, რომ მასივების მოგვცეს წვდომის. უბრალოდ გამოყენებით კვადრატული ფრჩხილი notation და ნომერი, შეგიძლიათ გადასვლა კონკრეტული ელემენტის მასივი მუდმივ დროს, დიდი O ერთი, ასე ვთქვათ. მაგრამ არსებობს გარკვეული downsides. რა მასივი გაკეთება არ ძალიან ადვილად? რა არის ეს არ არის კარგი? სტუდენტი: [inaudible]. დინამიკები 1: რა არის ეს? სტუდენტი: [inaudible]. დინამიკები 1: გაშლილი ზომის. ასე რომ downsides of მასივი არიან ზუსტად საპირისპირო რა upsides არიან. ასე რომ, ერთი downsides არის რომ ეს ფიქსირებული ზომის. ასე რომ თქვენ არ ნამდვილად ზრდა იგი. შეგიძლიათ გადაანაწილოს უფრო დიდი ბლოკი მეხსიერება და შემდეგ გადავა ძველი ელემენტები ახალ მასივი. და მაშინ თავისუფალ წლის მასივი, for მაგალითად, გამოყენებით malloc ან ანალოგიური ფუნქცია მოუწოდა realloc, რომელიც reallocates მეხსიერება. Realloc, რადგან გარდა, ცდილობს გაძლევთ მეხსიერება, რაც იქნება შემდეგ მასივს რომ თქვენ უკვე გაქვთ. მაგრამ ეს შეიძლება გადავიდეს რამ გარშემო საერთოდ. მაგრამ მოკლედ, ეს არის ის, ძვირადღირებული, არა? იმიტომ, რომ თუ თქვენ გაქვთ ბლოკი ხსოვნას ამ ზომის, მაგრამ ნამდვილად მინდა ერთი ამ ზომის, და გსურთ, რომ შევინარჩუნოთ ორიგინალური ელემენტები, თქვენ გაქვთ დაახლოებით წრფივი დრო გადაწერა პროცესი რომ უნდა მოხდეს ეხლა ძველი მასივი ახალი. რეალობა ითხოვს ოპერაციული სისტემა ისევ და ისევ და კიდევ ერთხელ დიდი მოცულობით მეხსიერება შეგიძლიათ ეღირება თქვენ გარკვეული დროის ასევე. ასე რომ, ეს ორივე კურთხევით და წყევლა in შენიღბვას, იმისა, რომ ეს მასივების არის ფიქსირებული ზომა. მაგრამ თუ ჩვენ დანერგვა ნაცვლად რაღაც ასე, რომელიც ჩვენ მოუწოდა დაკავშირებული სია, მივიღებთ რამდენიმე upsides და რამდენიმე downsides აქაც. ასე უკავშირდება სია უბრალოდ მონაცემები სტრუქტურა შედგება C structs ამ შემთხვევაში, თუ struct, გაწვევას, მხოლოდ კონტეინერი ერთი ან მეტი სპეციფიკური სახის ცვლადები. ამ შემთხვევაში, რა მონაცემთა ტიპები როგორც ჩანს, შიგნით struct რომ ბოლო დროს ჩვენ მოუწოდა კვანძის? თითოეული ეს rectangles არის კვანძის. და თითოეული პატარა ოთხკუთხედს შიგნით ეს მონაცემები ტიპის. რა სახის საერთოდ ვამბობთ ისინი ორშაბათს? ჰო? სტუდენტი: [inaudible]. დინამიკები 1: ცვლადი და მაჩვენებელი, ან უფრო კონკრეტულად, int, for N, და მაჩვენებელი ბოლოში. ორივე არ უნდა იყოს 32 bits, ზე მაინც კომპიუტერული მსგავსი CS50 ელექტრო და ა.შ. ისინი შედგენილი თანაბრად ზომის. ასე რომ, რას გამოყენებით მაჩვენებელი თუმცა, როგორც ჩანს? რატომ დაამატოთ ეს arrow ახლა, როცა მასივების იყო ასე ლამაზი და სუფთა და მარტივი? რა არის მაჩვენებელი აკეთებს ჩვენს თითოეულ ამ კვანძების? სტუდენტი: [inaudible]. დინამიკები 1: ზუსტად. ეს ეუბნება, სად მომდევნო ერთი. ასე რომ, ერთგვარი გამოყენება ანალოგია გამოყენებით თემა დასალაგებლად of თემა ამ კვანძების ერთად. და ეს ზუსტად იმას თუ რას ვაკეთებთ ერთად მითითებები, რადგან თითოეული ამ მოცულობით მეხსიერება შეიძლება იყოს ან არ იყოს მომიჯნავე, უკან უკან დაბრუნება შიგნით ოპერატიული, რადგან ყოველი მოვუწოდებთ malloc ამბობდა, მომეცი საკმარისი bytes ახალი კვანძის, შესაძლოა, აქ ან შეიძლება იყოს აქ. ეს შეიძლება იყოს აქ. ეს შეიძლება იყოს აქ. თქვენ უბრალოდ არ ვიცი. მაგრამ მისი გამოყენება მითითებას in მისამართები იმ კვანძების, შეგიძლიათ სტიჩი მათ ერთად ისე, რომ გამოიყურება ვიზუალურად მოსწონს სია იმ შემთხვევაშიც კი თუ ეს ყველაფერი ყველა გავრცელდა მთელს თქვენს ერთი ან თქვენი ორი ან თქვენი ოთხი გიგაბაიტი ოპერატიული შიგნით საკუთარი კომპიუტერი. ასე რომ, downside, მაშინ, უკავშირდება სია რა? რა ფასად ჩვენ როგორც ჩანს გადამხდელი? სტუდენტი: [inaudible]. დინამიკები 1: მეტი სივრცე, არა? ჩვენ, ამ შემთხვევაში, გაორმაგდა ოდენობით სივრცე, რადგან ჩვენ წავიდნენ 32 bits თითოეული კვანძის, თითოეული int, ასე რომ, ახლა 64 ბიტი იმიტომ მივდივართ, შენარჩუნება გარშემო მაჩვენებელი ასევე. თქვენ უფრო მეტი ეფექტურობა, თუ თქვენი struct მეტია, ვიდრე ეს მარტივი რამ. თუ თქვენ რეალურად სტუდენტი შიგნით რომლის რამდენიმე strings for სახელი და სახლში, შესაძლოა, პირადობის მოწმობის ნომერი, შესაძლოა, რამდენიმე სხვა სფეროებში საერთოდ. ასე რომ, თუ თქვენ გაქვთ დიდი საკმარისი struct, მაშინ იქნებ ღირებულება მაჩვენებელი არის არა ასეთი დიდი გარიგება. ეს არის ცოტა კუთხეში შემთხვევაა, რომ ჩვენ შენახვის ასეთი მარტივი პრიმიტიული შიგნით უკავშირდება სიაში. მაგრამ საქმე ის არის იგივე. თქვენ ნამდვილად მეტის დახარჯვას მეხსიერება, მაგრამ თქვენ მისაღებად მოქნილობა. იმის გამო, რომ ახლა თუ მინდა დაამატოთ ელემენტს დასაწყისში ამ სიაში, მე უნდა გამოყოს ახალი კვანძის. და მე უბრალოდ განახლება იმ ისრის რატომღაც მხოლოდ მოძრავი რამდენიმე მითითებას გარშემო. თუკი მინდა ჩადეთ რამე შევიდა შუა სია, მე არ უნდა დააყენებს ყველას განზე ისე, როგორც ამ კვირა წარსულში ჩვენი მოხალისეები, რომლებიც წარმოდგენილია მასივი. მე შემიძლია მხოლოდ გამოყოს ახალი კვანძის და მაშინ უბრალოდ აღვნიშნო ისრები in სხვადასხვა მიმართულებით, რადგან არ უნდა დარჩეს ფაქტობრივი მეხსიერების ჭეშმარიტი ხაზი, როგორიც მე შედგენილი აქ ეკრანზე. და მაშინ ბოლოს, თუ გვინდა, რომ ჩადეთ რაღაც სიის ბოლოში, ეს კი ადვილია. ეს არის ერთგვარი თვითნებური notation, მაგრამ 34 ნახვა მაჩვენებელი, მიიღოს ვხვდები. რა არის ღირებულება, მისი მაჩვენებელი ყველაზე სავარაუდოდ შედგენილი სახის მსგავსად წლის სკოლა ანტენის იქ? სტუდენტი: [inaudible]. დინამიკები 1: ალბათ null. მართლაც, რომელიც ერთ ავტორის წარმომადგენლობა null. და ეს null იმიტომ, რომ თქვენ აბსოლუტურად უნდა ვიცოდეთ, სადაც ბოლოს დაკავშირებული სია, მცირეოდენ თქვენ გაქვთ შემდეგ და შემდეგ და შემდეგ ეს ისარი ზოგიერთი ნაგვის მნიშვნელობა. ასე რომ null იქნება ნიშნავდეს, რომ არ არსებობს მეტი კვანძების მარჯვნივ ნომერი 34, ამ შემთხვევაში. ამიტომ გთავაზობთ, რომ ჩვენ შეგვიძლია განვახორციელოთ ამ კვანძის კოდის. და ჩვენ ვხედავთ ამ სახის საქართველოს syntax ადრე. Typedef მხოლოდ განსაზღვრავს ახალი ტიპის ჩვენთვის, გვაძლევს სინონიმი მოსწონს სიმებიანი იყო char *. ამ შემთხვევაში, იგი აპირებს, რომ მოგვცეს სტენოგრამის notation ისე, რომ struct კვანძის შეიძლება ნაცვლად უბრალოდ უნდა ჩაიწეროს, როგორც კვანძის, რომელიც ბევრი სუფთა. ეს ბევრი ნაკლებად verbose. შიგნით კვანძის აშკარად int მოუწოდა ო, შემდეგ კი struct კვანძის * რაც იმას ნიშნავს, ზუსტად რა გვინდოდა ისრების ნიშნავს, მაჩვენებელი მეორეში კვანძის of ზუსტად იგივე მონაცემების ტიპის. და მე ვთავაზობ, რომ ჩვენ შეგვიძლია განვახორციელოთ ძებნის ფუნქცია ასე, რომელიც ერთი შეხედვით შესაძლოა, როგორც ჩანს ცოტა რთული. მაგრამ ვნახოთ, ეს კონტექსტში. ნება მომეცით წავიდეთ მეტი მოწყობილობის აქ. ნება მომეცით გახსნას ფაილი სახელად სიაში ნულოვანი dot თ. და ეს მხოლოდ შეიცავს განმარტება ჩვენ უბრალოდ დაინახა მომენტში წინ მონაცემთა ამ ტიპის მოუწოდა კვანძის. ასე რომ, ჩვენ დააყენა, რომ შევიდა dot თ ფაილი. და როგორც გარდა, მიუხედავად იმისა, რომ ამ პროგრამა, რომელიც თქვენ შესახებ სანახავად არის არ არის, რომ კომპლექსი, ეს მართლაც კონვენცია, როდესაც წერილობით პროგრამა დააყენა რამ, როგორიცაა მონაცემთა ტიპები, უნდა გაიყვანოს მუდმივები ზოგჯერ, შიგნით თქვენი header ფაილი და არა აუცილებლად თქვენი C ფაილი, რა თქმა უნდა, როდესაც თქვენი პროგრამების მისაღებად ზრდას, ისე, რომ თქვენ იცით, სად უნდა გამოიყურებოდეს როგორც დოკუმენტაცია გარკვეულ შემთხვევებში, ან ამისთვის საფუძვლებს ასე, განმარტება ზოგიერთი ტიპის. თუ მე ახლა ქმნის სიაში ნულოვანი dot გ, შეამჩნია რამდენიმე რამ. იგი მოიცავს რამდენიმე თავით ფაილი საუკეთესო რაც ჩვენ ვნახეთ ადრე. იგი მოიცავს საკუთარი თავით ფაილი. და როგორც გარდა, თუ რატომ არის ორმაგი შესრულების შეთავაზება აქ, განსხვავებით კუთხე ფრჩხილებში ხაზი, რომ მე ხაზი გაუსვა იქ? სტუდენტი: [inaudible]. დინამიკები 1: ჰო ამიტომ ადგილობრივი ფაილი. ასე რომ, თუ ის ადგილობრივი ფაილი საკუთარი აქ ხაზი 15, მაგალითად, თქვენ იყენებთ ორმაგი შეთავაზებებს ნაცვლად საქართველოს დახრილი ფრჩხილებში. ახლა ეს არის ერთგვარი საინტერესო. გავითვალისწინოთ, რომ მე გამოცხადდა გლობალური ცვლადი ამ პროგრამაში ხაზი 18 მოუწოდა პირველი იდეა, როგორც ეს იქნება მაჩვენებელი პირველი კვანძის ჩემს დაკავშირებული სიაში, და მე ინიციალიზაცია მას null, რადგან მე არ გამოყო ნებისმიერი ფაქტობრივი კვანძების მხოლოდ ამჟამად. ასე რომ, ეს წარმოადგენს, pictorially, რასაც ჩვენ დაინახა მომენტში წინ ამ სურათზე როგორც რომ მაჩვენებელი on შორს მარცხენა მხარეს. ასე რომ, ახლა, რომ მაჩვენებელი ჯერ არ ისარი. ის ნაცვლად მხოლოდ null. მაგრამ იგი წარმოადგენს რა იქნება მისამართი პირველი რეალური კვანძის ამ სიაში. ასე რომ, მე განახორციელეს არის გლობალური რადგან, როგორც ნახავთ, ეს ყველაფერი პროგრამა არ ცხოვრების განხორციელება უკავშირდება სია ჩემთვის. ახლა მაქვს რამდენიმე პროტოტიპები აქ. გადავწყვიტე განახორციელოს ფუნქციები, როგორიცაა წაშლა, ჩასმა, ჩხრეკის, და traversal - ბოლო მხოლოდ კონკრეტდება ფეხით გასწვრივ სია, დაბეჭდვისას მისი ელემენტების. ახლა კი აქ არის ჩემი მთავარი სიტუაციიდან. და ჩვენ არ ატარებენ ძალიან ბევრი დრო ეს იმიტომ რომ ეს არის ერთგვარი, იმედია ძველი ქუდი უკვე. მე ვაპირებ გაკეთებას შემდეგ, ხოლო შესახებ თანამშრომლობს. ასე რომ, ერთი, მე ვაპირებ ბეჭდვა ეს მენიუ. და მე ფორმატის იქნება, როგორც cleanly როგორც მე იქნებოდა. თუ მომხმარებლის ტიპის ერთ, რაც იმას ნიშნავს, მათ სურთ წაშლა რაღაც. თუ მომხმარებლის ტიპის ორ, რაც იმას ნიშნავს, მათ სურთ ჩადეთ რამე. და სხვ. მე ვაპირებ შემდეგ გამოიწვიოს მაშინ ბრძანება. და მაშინ მე ვაპირებ გამოყენება GetInt. ასე რომ, ეს მართლაც მარტივი menuing ინტერფეისი, სადაც თქვენ უბრალოდ უნდა შეიტანოთ ნომერი რუკების ერთ იმ ბრძანებებს. ახლა კი აქვს ლამაზი სუფთა გადართვის განცხადება, რომ აპირებს ჩართვის მიუხედავად შესახებ აკრეფილი შემოსული და თუ მათ აკრეფილი ერთი, მე მოვუწოდებთ წაშლა და შესვენება. თუ ისინი აკრეფილი ორი, მე მოვუწოდებთ ჩადეთ და შესვენება. ახლა კი შეამჩნია მე დააყენა ყოველ ამ იმავე ხაზი. ეს არის მხოლოდ სტილისტური გადაწყვეტილება. როგორც წესი ჩვენ ვნახეთ რაღაც მოსწონს ეს. მაგრამ მე მხოლოდ მიიღო გადაწყვეტილება, გულწრფელად ვამბობ, ჩემი პროგრამა ჩანდა უფრო იკითხება, რადგან ეს იყო მხოლოდ ოთხი საქმეების უბრალოდ სიაში მოსწონს ეს. სრულიად ლეგიტიმური გამოყენების სტილი. და მე ვაპირებ ამის გაკეთება ისე, სანამ მომხმარებელს ჯერ არ აკრეფილი ნულოვანი, რომელიც მე გადაწყდა, ნიშნავს, რომ მათ სურთ დატოვა. ასე რომ, ახლა შეამჩნია, რაც მე აპირებს აქ. მე ვაპირებ გასათავისუფლებლად ლენტა როგორც ჩანს. მაგრამ უფრო, რომ სულ რაღაც მომენტში. მოდით პირველ აწარმოებს ამ პროგრამაში. ნება მომეცით, უფრო დიდი ტერმინალში ფანჯრის dot ხაზი სიაში 0. მე ვაპირებ წავიდეთ წინ და ჩადეთ მიერ აკრეფა ორი, რაოდენობის, როგორიცაა 50, და ახლა დაინახავთ სიაში არის 50. და ჩემი ტექსტი მხოლოდ scrolled up bit. ასე რომ, ახლა შეამჩნია სია შეიცავს ნომერი 50. მოდით კიდევ ჩანართით მიღებით ორი. მოდით აკრიფოთ ნომერი, როგორც ერთი. სია არის ერთი, რასაც მოჰყვა 50. ასე რომ, ეს მხოლოდ ტექსტური წარმომადგენლობა უკავია. და მოდით ჩადეთ კიდევ ერთი ნომერი, როგორიცაა ნომერი 42, რომელიც იმედია აპირებს დასრულდება ცენტრიდან, რადგან ამ პროგრამის განსაკუთრებული სახის მას ელემენტები, როგორც ეს ჩანართები მათ. ასე რომ, ჩვენ გვაქვს იგი. სუპერ მარტივი პროგრამა, რომელიც შეიძლება აბსოლუტურად არ გამოიყენება მასივი, მაგრამ მე არ უნდა იყოს გამოყენებით დაკავშირებული სია მხოლოდ ასე შემიძლია დინამიურად იზრდება და მცირდება იგი. მოდით შევხედოთ ძებნის, თუ აწარმოებს ბრძანება სამი, მინდა ძებნის ამისთვის, ვთქვათ, ნომერი 43. და არაფერი აშკარად ი, იმიტომ, რომ მე დაუბრუნდა პასუხი არ. მოდით ეს კიდევ ერთხელ გავაკეთოთ. ძიება. მოვძებნოთ 50, უფრო სწორად ძებნის 42, რომელსაც აქვს ლამაზი ცოტა დახვეწილი მნიშვნელობა აქვს. და მივხვდი, მნიშვნელობა ცხოვრებაში არსებობს. ხმების 42, თუ არ ვიცი მითითება, Google იგი. ყველა უფლება. ასე რომ, თუ რა ამ პროგრამის გაკეთდეს ჩემთვის? უბრალოდ საშუალება მომცა ჩადეთ ამით შორს და ძიება ელემენტებს. მოდით სწრაფი წინ, მაშინ, რომ ფუნქცია ჩვენ მოხვდა ზე ორშაბათს, როგორც teaser. ასე რომ, ეს ფუნქცია, I აცხადებენ, ეძებს ელემენტის სიაში პირველი ერთი, რითაც შესახებ და შემდეგ მოუწოდებენ GetInt მიიღოს ფაქტობრივი int რომ გსურთ მოძებნოთ. მაშინ შეამჩნია ეს. მე ვაპირებ, რომ შეიქმნას დროებითი ცვლადი შეესაბამება 188 მოუწოდა მაჩვენებელი - Ptr - შეეძლო მას არაფერი. და ეს მაჩვენებელი, რომ კვანძის იმიტომ, რომ მე განაცხადა კვანძის * არსებობს. და მე ინიციალიზაციისას იგი უტოლდება პირველი ისე, რომ ეფექტურად მაქვს თითი, ასე ვთქვათ, მე ძალიან პირველი ელემენტის სიაში. ასე რომ, თუ ჩემი მარჯვენა ხელი აქ Ptr ვარ მიუთითებს, რომ იგივე, რომ პირველი არის მიუთითებს. ასე რომ, ახლა კოდი, რა მოხდება შემდეგ - ეს არის საერთო პარადიგმის როდესაც iterating მეტი სტრუქტურის მსგავსად უკავშირდება სიაში. მე ვაპირებ გაკეთებას შემდეგ, ხოლო მაჩვენებელი არ არის ტოლი null ასე რომ, ხოლო ჩემი თითი არ მიუთითებს ზოგიერთი null ღირებულება, თუ მაჩვენებელი ისარი ო შეადგენს ო. ჩვენ შეამჩნევთ პირველი რომ n რა მომხმარებლის აკრეფილი პოსტი GetInts მოვუწოდებთ აქ. და კურსორის arrow n ნიშნავს რა? თუ ჩვენ დაბრუნდეს სურათზე აქ, თუ მაქვს თითი მიუთითებს რომ პირველი კვანძის შემცველი ცხრა, arrow არსებითად ნიშნავს წასვლა, რომ კვანძის და დაიბრუნოს ღირებულება ადგილმდებარეობა n, ამ შემთხვევაში, მონაცემთა სფეროში მოუწოდა ო. როგორც განზე - და ჩვენ ვნახეთ ამ წყვილის კვირის წინ, როცა ვინმე მეუბნება - ამ სინტაქსისიც ახალი, მაგრამ ეს არ მოგვცეს უფლებამოსილება, რომ ჩვენ არ უკვე აქვს. რა იყო ეს ფრაზა ექვივალენტურია გამოყენებით dot notation და ვარსკვლავი წყვილი კვირის წინ, როდესაც ჩვენ peeled უკან ამ ფენას ცოტა ნაადრევად? სტუდენტი: [inaudible]. დინამიკები 1: სწორედ ეს იყო ვარსკვლავი, და მაშინ საუბარი იყო ვარსკვლავი dot ო, ერთად ფრჩხილებში, რაც გამოიყურება, გულწრფელად ვამბობ, მე ვფიქრობ, რომ ბევრი მეტი cryptic წაკითხვა. მაგრამ ვარსკვლავი მაჩვენებელი, როგორც ყოველთვის, საშუალება გვაქვს. და კიდევ თქვენ იქ, რა მონაცემების სფეროში გინდათ წვდომის? ისე თქვენ იყენებთ dot notation წვდომის structs მონაცემთა მოედანზე და მე კონკრეტულად მინდა ო. გულწრფელად ვამბობ, იტყოდა, რომ ამ მხოლოდ რთული წაიკითხა. ეს უფრო რთული უნდა გვახსოვდეს, სადაც ნუ ფრჩხილებში წავიდეს, ვარსკვლავი და ყველა რომ. ასე, რომ მსოფლიო მიღებული ზოგიერთი სინტაქსური შაქარი, ასე ვთქვათ. უბრალოდ სექსუალური გზით და განაცხადა, ამ ტოლფასია და ალბათ უფრო ინტუიტიური. თუ მაჩვენებელი მართლაც მაჩვენებელი, arrow notation საშუალებით წავალთ და იპოვოს სფეროში ამ შემთხვევაში მოუწოდა ო. ასე რომ, თუ მე ეს, შეამჩნია რა გავაკეთო. უბრალოდ ამობეჭდოთ, აღმოვაჩინე პროცენტს i, ჩართვის მნიშვნელობა, რომ int. მოვუწოდებ ძილის ერთი მეორე უბრალოდ სახის პაუზის რამ ეკრანზე მისცეს შესახებ მეორე აღიქვას რა უბრალოდ მოხდა. და მერე შესვენება. წინააღმდეგ შემთხვევაში, რა გავაკეთო? მე განახლება მაჩვენებელი ერთნაირი მაჩვენებელი ისარი მომავალი. ასე რომ, მხოლოდ იმისათვის, რომ იყოს ნათელი, ეს იმას ნიშნავს წასვლა იქ, გამოყენებით ჩემი ძველი სკოლა notation. ასე რომ, ეს მხოლოდ იმას ნიშნავს, წასვლა, რაც არ უნდა თქვენ მიუთითებს, რაც, ძალიან პირველ შემთხვევაში არის მე მიუთითებს struct ცხრა მას. ასე, რომ წავიდნენ იქ. და მაშინ dot notation ნიშნავს, მიიღონ ღირებულება მომავალი. მაგრამ ღირებულება, მიუხედავად იმისა, რომ ეს შედგენილი როგორც ვიწრო, მხოლოდ ნომერი. ეს რიცხვი მისამართი. ასე რომ, ეს ერთი ხაზი კოდი, თუ არა წერილობითი ასე, უფრო cryptic სხვათა შორის, თუ ასე, ოდნავ მეტი ინტუიციური გზა, მხოლოდ იმას ნიშნავს, გადაადგილება ჩემი მხრივ პირველი კვანძის მომდევნო ერთი, ხოლო შემდეგ მომდევნო ერთი, შემდეგ კი მომდევნო ერთი და სხვ. ასე რომ, ჩვენ არ შევჩერდებით სხვა განსახორციელებლად ჩადეთ და წაშლა და traversal, პირველ ორ რაც საკმაოდ ჩართული. და ვფიქრობ, ეს საკმაოდ მარტივია მისაღებად დაკარგული, როცა ამის გაკეთება სიტყვიერი შეურაცხყოფა. მაგრამ რა შეგვიძლია გავაკეთოთ აქ ცდილობენ განსაზღვრონ, როგორ იმისათვის, რომ ამის გაკეთება ვიზუალურად. იმის გამო, რომ მინდა შესთავაზოს, რომ თუ ჩვენ მინდა ჩასასმელად ელემენტები შეიტანა ამ არსებული სია, რომელიც ხუთ ელემენტები - 9, 17, 22, 26 და 33 - მე რომ განახორციელებს ეს კოდი, მე უნდა განიხილოს, თუ როგორ უნდა წავიდეს შესახებ აკეთებენ. და მე შესთავაზოს აღების ბავშვი ნაბიჯები რომლის დროსაც, ამ შემთხვევაში ვგულისხმობ, რა არის შესაძლო სცენარი, რომ ჩვენ შეიძლება ექმნებათ ზოგადად? განხორციელებისას ჩანართით for დაკავშირებული სია, ამ რაღაც უნდა იყოს კონკრეტული მაგალითი ზომა ხუთ. თუ გსურთ ჩადეთ ნომერი, მინდა ვთქვა, ნომერ და შენარჩუნების გადანაწილებული მიზნით, სადაც აშკარად არ ნომერ უნდა წავიდეთ ამ კონკრეტული მაგალითი? ისევე დასაწყისში. მაგრამ რა საინტერესოა არსებობს, რომ თუ გსურთ ჩადეთ ერთი მოხდეს ამ სიაში, რა განსაკუთრებული მაჩვენებელი სჭირდება დაზუსტებას როგორც ჩანს? პირველი. ასე რომ, იტყოდა, რომ ეს არის პირველი შემთხვევა, რომ ჩვენ დაგვჭირდება განიხილოს, სცენარი ჩართვის ჩასმის დროს დასაწყისში სიაში. მოდით pluck off შესაძლოა მარტივი ან თუნდაც ადვილი საქმე, შედარებით საუბარი. დავუშვათ, მინდა შეიყვანა ნომერი 35 გადანაწილებული მიზნით. ეს აშკარად ეკუთვნის იქ. ასე რომ, რა მაჩვენებელი აშკარად აპირებს უნდა იყოს, რომ ამ სცენარით? 34 ნახვა მაჩვენებელი ხდება არ null მაგრამ მისამართი struct შემცველი ნომერი 35. ასე რომ, საქმე ორი. ასე რომ, უკვე, მე ერთგვარი quantizing რამდენად იმუშავებს მე უნდა გავაკეთოთ აქ. და ბოლოს, აშკარა შუა საქმე მართლაც, შუა, თუ მინდა ჩადეთ რაღაც say 23, რომელიც მიდის შორის 23 და 26, მაგრამ ახლა რამ ცოტა მეტი ჩართული, რადგან რა მითითებები უნდა შეიცვალოს? ასე რომ, 22 აშკარად შესაცვლელია იმიტომ, რომ მას არ შეუძლია აღვნიშნო, რომ 26 აღარაა. მან უნდა აღვნიშნო, რომ ახალი კვანძის, რომ მე უნდა გამოყოს დარეკვით malloc ან რომელიმე ექვივალენტს. მაგრამ შემდეგ ასევე უნდა, რომ ახალი კვანძის, 23 ამ შემთხვევაში, უნდა ჰქონდეს თავისი მაჩვენებელი მიუთითებს, ვის? 26. და იქ იქნება იმისათვის ოპერაციების აქ. იმიტომ, რომ თუ ამის გაკეთება foolishly, და მე მაგალითად დაწყების დასაწყისში სია, და ჩემი მიზანია ჩადეთ 23. და მე ჩეკი, ჯერ ეს ეკუთვნის აქ, ახლოს ცხრა? პოსტები ს ეკუთვნის, აქ, შემდეგ 17? პოსტები აქვს თუ არა მას ეკუთვნის აქ მომდევნო 22? დიახ. ახლა თუ მე ვარ უგუნური აქ, და არ ფიქრი ამ გზით, შეიძლება გამოყოფს ჩემი ახალი კვანძის 23. მე შეიძლება განახლდეს მაჩვენებელი დან კვანძის მოუწოდა 22, მიუთითებს იგი ახალი კვანძის. და მაშინ რა უნდა განაახლოს ახალი კვანძის-ის მაჩვენებელი, რომ იყოს? სტუდენტი: [inaudible]. დინამიკები 1: ზუსტად. მიუთითებს 26. მაგრამ dammit თუ არ უკვე განახლება 22 ნახვა მაჩვენებელი აღვნიშნო, რომ ამ ბიჭს, და ახლა მე ობოლი, დანარჩენი სიის, ასე ვთქვათ. ასე რომ, ბრძანებით აქ ოპერაციები იქნება მნიშვნელოვანი. ამისათვის შეიძლება მე მოიპაროს, ამბობენ, ექვსი მოხალისეები. და ვნახოთ, შევძლებთ თუ არა ამის გაკეთება ვიზუალურად ნაცვლად კოდური ბრძენი. და ჩვენ გვაქვს მშვენიერი სტრესი ბურთები თქვენ დღეს. კარგი, რა ერთი, ორი, ამ უკან - წლის ბოლომდე იქ. სამი, ოთხი, როგორც თქვენ ბიჭები წლის ბოლომდე. ხოლო ხუთი, ექვსი. რა თქმა უნდა. ხუთი და ექვსი. ყველა უფლება და ჩვენ მოდის თქვენ, ბიჭები მომავალი დრო. ყველა უფლება, მოდის up. ყველა უფლება, რადგან თქვენ აქ პირველ რიგში, გსურთ იყოს ერთ უხერხულად in Google შუშა აქ? ყველა უფლება, ისე, ბატონო, შუშა, ჩაიწეროს ვიდეო. OK, თქვენ კარგი წასვლა. ყველა უფლება ასე რომ, თუ თქვენ ბიჭები შეუძლია მოვიდეს მეტი აქ, მე არ მომზადებული წინასწარ ზოგიერთი ნომრები. ყველა უფლება, მოდის შესახებ მეტი აქ. და რატომ არ წავიდეთ ცოტა შემდგომ, რომ გზა. და ვნახოთ, რა არის თქვენი სახელი და გვარი, ერთად Google შუშა? სტუდენტი: ბენ. დინამიკები 1: ბენ? OK, ბენ, თქვენ იქნება პირველი, ფაქტიურად. ასე რომ, ჩვენ ვაპირებთ გამოგიგზავნით ბოლომდე ეტაპზე. ყველა უფლება, და შენი სახელი? სტუდენტი: ჯეისონ. დინამიკები 1: ჯეისონ, OK თქვენ იყოს ნომერი ცხრა. ასე რომ, თუ გვინდა, რომ დაიცვას ბენ, რომ გზა. სტუდენტი: Jill. დინამიკები 1: Jill, თქვენ იქნება 17, რომელიც, თუ მინდა გაკეთდეს ეს უფრო ჭკვიანურად, მე არ დაიწყო ჩაეგდო. თქვენ წავიდეთ რომ გზა. 22. თქვენ? სტუდენტი: მარიამ. დინამიკები 1: მერი, თქვენ უნდა იყოს 22. და თქვენი სახელია? სტუდენტი: კრის. დინამიკები 1: კრის, თქვენ 26. და მაშინ ბოლოს. სტუდენტი: დიანა. დინამიკები 1: Diana, თქვენ უნდა იყოს 34. ასე რომ მოვა აქ. ყველა უფლება, იმდენად სრულყოფილი გადანაწილებული შეკვეთა უკვე. და მოდით წავიდეთ წინ და გაკეთება ასე რომ ჩვენ შეგვიძლია ნამდვილად - ბენ, თქვენ მხოლოდ ამ სახის ეძებს შევიდა არსად არსებობს. კარგი, მოდით წავიდეთ წინ და ასახავს ამ გამოყენებით იარაღი, ჰგავს ვიყავი, ზუსტად, რა ხდება. ასე რომ წავიდეთ წინ და მისცეს საკუთარი თავი ფეხით ან ორი შორის საკუთარი თავი. და წავიდეთ წინ და აღვნიშნო, ერთი მხრივ, რათა ვინც თქვენ უნდა მიუთითებს ამ საფუძველზე. და თუ თქვენ null მხოლოდ წერტილი სწორი ქვემოთ სართული. კარგი, იმდენად კარგი. ასე რომ, ახლა ჩვენ გვაქვს უკავშირდება სია, და ნება მომეცით ინიციატივით კი, მე როლი Ptr, ამიტომ მე არ გადაიტვირთოთ ტარების ამ გარშემო. ხოლო შემდეგ - ვინმე სულელური კონვენცია - შეგიძლიათ დარეკოთ ამ არაფერი გსურთ - წინამორბედის მაჩვენებელი, pred მაჩვენებელი - უბრალოდ მეტსახელად მივეცით in ჩვენი ნიმუში კოდი, ჩემი მარცხენა ხელი. მეორეს მხრივ, რომ უნდა შენახვა სიმღერა ვინ ვინ არის ამ შემდეგ სცენარებს. ამიტომ ვარაუდობენ, პირველ რიგში, მინდა pluck off რომ პირველი მაგალითი ჩასმის, ამბობენ 20, შევიდა სიაში. ამიტომ, მე ვაპირებ გვჭირდება ვინმე embody ნომერი 20 ჩვენთვის. ასე რომ, მე უნდა malloc ვინმე ეხლა დამსწრე საზოგადოებას. კარგით up. რა არის შენი სახელი? სტუდენტი: ბრაიან. დინამიკები 1: ბრაიან, ყველა უფლება, ასე რომ თქვენ უნდა იყოს კვანძის შეიცავს 20. ყველა უფლება, მოდის შესახებ მეტი აქ. და ცხადია, რომ, სადაც ამჯამად ბრაიან ეკუთვნის? ასე რომ, შუა - ფაქტობრივად, დაველოდოთ წუთში. ჩვენ ამით მწყობრიდან. ჩვენ ვდებთ ამ ბევრი უფრო რთული ვიდრე ეს უნდა იყოს პირველ რიგში. კარგი, ჩვენ ვაპირებთ, უფასო ბრაიან და realloc ბრაიან როგორც ხუთი. OK, ასე რომ, ახლა ჩვენ გვინდა ჩასასმელად ბრაიან როგორც ხუთი. ასე მოდის შესახებ მეტი აქ შემდეგი ბენ მხოლოდ ერთი წუთით. და შეგიძლიათ სავარაუდოდ გითხრათ სადაც ეს ამბავი ხდება. მაგრამ მოდით ვფიქრობ, ყურადღებით ამის შესახებ იმისათვის ოპერაციებში. და ეს ზუსტად ამ ვიზუალური რომ აპირებს გამოდიან რომ ნიმუში კოდი. ასე რომ, აქ მე Ptr მიუთითებს თავდაპირველად არა ბენ, თავისთავად, მაგრამ რაც არ უნდა ვაფასებთ მას შეიცავს, რაც ამ შემთხვევაში არის - რა არის შენი სახელი ისევ? სტუდენტი: ჯეისონ. დინამიკები 1: ჯეისონ, ასე რომ ორივე ბენ და მე ვართ მიუთითებს ჯეისონ ამ ეტაპზე. ასე რომ, ახლა მე უნდა განსაზღვროს, სად ბრაიან ეკუთვნის? ასე რომ, ერთადერთი, რაც აქვთ ისარგებლონ ახლა არის მისი ო მონაცემთა ერთეულზე. ამიტომ, მე ვაპირებ, რათა შეამოწმოს, არის ბრაიან ნაკლები ჯეისონ? პასუხი მართალია. ასე რომ, ის, რაც ახლა უნდა მოხდეს, სწორი მიზნით? მე უნდა განახლდეს, თუ რამდენი მითითებას საერთო ჯამში ამ ისტორიაში? სად ჩემი მხრივ კვლავ მიუთითებს ჯეისონ და თქვენი მხრივ - თუ გსურთ თქვენს მხრივ, როგორიცაა, ერთგვარი, I არ ვიცი, კითხვის ნიშნის. კარგი, კარგი. ყველა უფლება, ასე რომ თქვენ არ რამდენიმე კანდიდატს. ან ბენ ან მე ან ბრაიან ან ჯეისონ ან ყველას, რომელიც მითითებები უნდა შეცვალოს? რამდენი საერთო ჯამში? OK, ასე რომ ორი. ჩემი მაჩვენებელი ნამდვილად არ აქვს მნიშვნელობა აღარ იმიტომ, რომ მე მხოლოდ დროებითია. ასე რომ, ამ ორი ბიჭები, სავარაუდოდ, როგორც ბენ და ბრაიან. ნება მომეცით, შესთავაზოს, რომ ჩვენ განახლება ბენ, რადგან იგი პირველი. პირველი ელემენტი ამ სიის არის იქნება Brian. ასე რომ, ბენ პუნქტი, ბრაიან. კარგი, ახლა რა? ვინ იღებს მიუთითა ვისთან? სტუდენტი: [inaudible]. დინამიკები 1: OK ისე ბრაიან აქვს აღვნიშნო ერთი ჯეისონ. მაგრამ არ დაკარგა სიმღერა რომ მაჩვენებელი? ნუ მე ვიცი, სად ჯეისონ არის? სტუდენტი: [inaudible]. დინამიკები 1: მე, რადგან მე ვარ დროებითი მაჩვენებელი. და სავარაუდოდ, მე არ შეცვლილა აღვნიშნო ახალ კვანძის. ასე რომ, ჩვენ შეიძლება უბრალოდ ბრაიან წერტილი ერთი ვინც მე მიუთითებს. და ჩვენ გავაკეთეთ. ასე რომ, საქმე ერთი ჩანართი დროს დასაწყისში სიაში. ორი გასაღები ნაბიჯები. ერთი, ჩვენ უნდა განახლდეს ბენ, შემდეგ კი ჩვენ ასევე უნდა განახლდეს ბრაიან. და მე არ უნდა გადაიტვირთოთ traipsing მეშვეობით დანარჩენი სია, იმიტომ, რომ ჩვენ უკვე იპოვა თავისი მდებარეობა, იმიტომ, რომ მას ეკუთვნოდა მარცხენა პირველი ელემენტი. ყველა უფლება, საკმაოდ მარტივია. ფაქტობრივად, იგრძნობა ჩვენ თითქმის მიღების ეს ძალიან რთული. მოდით ახლა pluck off ბოლომდე სიის და ვხედავ, სადაც სირთულის იწყება. ასე რომ, თუ ახლა, მე alloc ეხლა დამსწრე საზოგადოებას. ნებისმიერ მსურველს სურს ითამაშოს 55? ყველა უფლება, ვნახე შენი ხელი პირველი. კარგით up. ჰო. რა არის შენი სახელი? სტუდენტი: [inaudible]. დინამიკები 1: Habata. კარგი, მოდის up. თქვენ უნდა იყოს რიცხვი 55. ასე რომ, რა თქმა უნდა, ეკუთვნის დასასრულს სიაში. მოდით მოთხრობა სიმულაციური ჩემთან ერთად როგორც Ptr მხოლოდ ერთი წუთით. ასე რომ მე პირველი ვაპირებ ზე რაც არ უნდა ბენ ის მიუთითებს. ჩვენ ორივე მიუთითებს ახლა ბრაიან. ასე რომ, 55 არანაკლებ ხუთი. ამიტომ, მე ვაპირებ განახლება თავს მიერ მიუთითებს ბრაიან მომდევნო მაჩვენებელი, რომელიც ახლა, რა თქმა უნდა ჯეისონ. 55 არანაკლებ ცხრა, ისე მე ვაპირებ განახლება Ptr. მე ვაპირებ განახლება Ptr. მე ვაპირებ განახლება Ptr მე აპირებს განაახლოს Ptr. და მე ვაპირებ - hmm, რა თქვენი სახელი ერთხელ? სტუდენტი: დიანა. დინამიკები 1: დიანა არის მიუთითებს, რა თქმა უნდა, ერთი null მისი მარცხენა ხელი. ასე რომ, სად Habata რეალურად ეკუთვნის ნათლად? მარცხნივ, აქ. ასე რომ, როგორ ვიცი დააყენოს მისი აქ ვფიქრობ, მე ბრალია. იმის გამო, რომ ის, რაც Ptr ხელოვნების ამ მომენტში დროს? Null. ასე რომ, მიუხედავად იმისა, რომ, ვიზუალურად, ჩვენ შეგვიძლია ცხადია, რომ ყველა ამ ბიჭები აქ სცენაზე. მე არ ინახება სიმღერა წინა პირი სიაში. მე არ მაქვს თითი მიუთითებს, ამ შემთხვევაში, კვანძის ნომერი 34. მოდით რეალურად დაიწყოს ამ დასრულდა. ასე რომ, ახლა მე რეალურად ესაჭიროებათ მეორე ადგილობრივი განსხვავებულია. და ეს არის ის, რაც თქვენ ხედავთ ფაქტობრივი ნიმუში C კოდი, სადაც მე მივალ, როდესაც მე: ჩემი მარჯვენა აღვნიშნო ჯეისონ, რითაც წასვლის ბრაიან უკან, I უკეთესი დაიწყება გამოყენებით ჩემი მარცხენა ხელი განახლება სადაც ვიყავი, ასე რომ, როგორც მე სწორედ ამ სიაში - უფრო უხერხულად, ვიდრე მე აპირებდა აქ ვიზუალურად - მე ვაპირებ მისაღებად სიის ბოლოში. ეს ხელი ჯერ კიდევ null, რომელიც საკმაოდ აზრი არ აქვს, გარდა მიუთითოს მე ნათლად დასასრულს სია, ეხლა მაინც მაქვს წინამორბედის მაჩვენებელი მიუთითებს აქ, ასე ახლა რა ხელში და რა მითითებას სჭირდება დაზუსტებას? ვისი ხელით გინდათ to reconfigure პირველი? სტუდენტი: [inaudible]. დინამიკები 1: OK, ასე რომ დიანას. სად გსურთ აღვნიშნო დიანა მარცხენა მაჩვენებელი ზე? 55, სავარაუდოდ, ისე, რომ ჩვენ შეიყვანეს იქ. სად უნდა 55 მაჩვენებელმა წავიდეთ? ქვემოთ წარმოდგენილ null. და ხელები, ამ ეტაპზე, არ სულ ერთია, იმიტომ, რომ ისინი მხოლოდ დროებითი ცვლადი. ასე რომ, ახლა ჩვენ გავაკეთეთ. ასე რომ, დამატებითი სირთულის იქ - და ეს არ არის, რომ მძიმე განხორციელება, მაგრამ ჩვენ გვჭირდება მეორად ცვლადი რათა დარწმუნებული ვარ, რომ ადრე მე გადაადგილება ჩემი უფლებაა მხრივ, მე განაახლებს ღირებულება ჩემი მარცხენა მხრივ, pred მაჩვენებელი ამ შემთხვევაში, ასე რომ მე ბოლოში მაჩვენებელი შენარჩუნება კვალს სადაც ვიყავი. ახლა, როგორც განზე, თუ თქვენ ფიქრი ამ მეშვეობით, ეს იგრძნობა ეს ცოტა შემაშფოთებელი უნდა შევინარჩუნოთ სიმღერა ამ მარცხენა ხელში. თუ რა სხვა გამოსავალი ამ პრობლემის ყოფილიყო? თუ თქვენ მივიღე რედიზაინი მონაცემები სტრუქტურა ჩვენ ვსაუბრობთ მეშვეობით წუთას? თუ ეს უბრალოდ სახის გრძნობს პატარა შემაშფოთებელი აქვს, მინდა, ორი მითითებას გადის სია, ვინ შეიძლება არ, იდეალური მსოფლიოში, შენარჩუნდება ინფორმაცია, რომ ჩვენ გვჭირდება? ჰო? სტუდენტი: [inaudible]. დინამიკები 1: ზუსტად. Right ასე რომ რეალურად საინტერესო ჩანასახი იდეა. ეს იდეა წინა მაჩვენებელი, მიუთითებს წინა ელემენტს. რა მოხდება, თუ მხოლოდ მასში, რომ შიგნით სია თავად? და ეს რთული იქნება ვიზუალურად ამ გარეშე ყველა ქაღალდი დაცემა სართული. თუმცა ვარაუდობენ, რომ ეს ბიჭები გამოიყენება, როგორც მათი ხელში აქვს წინა მაჩვენებელი და მომავალი მაჩვენებელი, რითაც ახორციელებს რა ჩვენ მოვუწოდებთ ორმაგად უკავშირდება სიაში. ეს საშუალებას მისცემს ჩემთვის ერთგვარი გადახვევა, ბევრად უფრო ადვილად გარეშე მე, პროგრამისტი, რომელსაც შენარჩუნება თვალყური ხელით - ნამდვილად ხელით - სად ვიყავი აქამდე ამ სიაში. ასე რომ, ჩვენ არ გაგვაჩნია. ჩვენ გავაგრძელებთ მარტივი რადგან ისინი აპირებთ მოდის, ფასი, ორჯერ ბევრი ფართი მითითებას, თუ გსურთ, მეორე. მაგრამ ეს მართლაც საერთო მონაცემთა სტრუქტურის ცნობილია, როგორც ორმაგად უკავშირდება სიაში. მოდით საბოლოო მაგალითად აქ და დააყენა ეს ბიჭები თავიანთი Misery. ასე რომ malloc 20. კარგით მდე aisle არსებობს. ყველა უფლება, რა გქვია? სტუდენტი: [inaudible]. დინამიკები 1: ბოდიში? სტუდენტი: [inaudible]. დინამიკები 1: Demeron? OK მოდის up. თქვენ უნდა იყოს 20. თქვენ აშკარად ვაპირებთ ეკუთვნის შორის 17 და 22. ნება მომეცით, სწავლობენ ჩემს გაკვეთილი. მე ვაპირებ, რომ დაიწყოს მაჩვენებელი მიუთითებს ბრაიან. და მე ვაპირებ მაქვს მარცხენა მხოლოდ განახლებული ბრაიან როგორც მე გადავა ჯეისონ, შემოწმების აკეთებს 20 ზე ნაკლები ცხრა? პოსტები 20 ზე ნაკლები 17? პოსტები 20 არანაკლებ 22? დიახ. ასე რომ, რა მითითებას ან ხელში უნდა შეიცვალოს სადაც ისინი მიუთითებს ახლა? ასე რომ ჩვენ შეგვიძლია გავაკეთოთ 17 მიუთითებს 20. ასე რომ, ჯარიმა. სად მინდა თქვენი მაჩვენებელი არის? 22. და ჩვენ ვიცით, სადაც 22 არის, კიდევ ერთხელ მადლობა ჩემი დროებითი მაჩვენებელი. ასე რომ, ჩვენ OK არსებობს. ასე რომ, ამის გამო დროებითი შენახვის მე ინახება სიმღერა სადაც ყველა. ახლა კი შეგიძლიათ ვიზუალურად წასვლას, სადაც თქვენ ეკუთვნის, და ახლა ჩვენ გვჭირდება 1, 2, 3, 4, 5, 6, 7, 8, 9 სტრესი ბურთები, და რაუნდი ტაში for ამ ბიჭებს, თუ შესაძლებელი იქნებოდა. ლამაზად კეთდება. [ტაში] დინამიკები 1: All უფლება. თქვენ შეიძლება შენარჩუნება ცალი ქაღალდის როგორც mementos. ყველა უფლება, ასე, მერწმუნეთ ეს არის ბევრი ადვილი გავლა, რომ ადამიანები, ვიდრე ფაქტობრივი კოდი. მაგრამ რა თქვენ მოვძებნოთ რაღაც მომენტში ახლა ის არის, რომ იგივე - oh, მადლობა. დიდი მადლობა - არის, რომ თქვენ იპოვით რომ იგივე მონაცემები სტრუქტურა, უკავშირდება სია, სინამდვილეში გამოყენებულ იქნას როგორც შენობის ბლოკის კიდევ უფრო დახვეწილი მონაცემების სტრუქტურებში. და გააცნობიეროს, ძალიან თემა ისაა, რომ ჩვენ აბსოლუტურად გააცნო მეტი სირთულის შევიდა განხორციელების ამ ალგორითმი. Insertion, და თუ წავედით მეშვეობით, წაშლა და ძებნა არის პატარა უფრო რთული, ვიდრე ეს იყო მასივი. მაგრამ ჩვენ გარკვეული დინამიკას. მივიღებთ ადაპტაციური მონაცემების სტრუქტურას. თუმცა ისევ და ისევ, ვიხდით ფასი გარკვეული დამატებითი სირთულის, როგორც ახორციელებს მას. და ჩვენ უარი წვდომის. და იყოს პატიოსანი, იქ არ კარგი გაწმენდა slide მე მოგცემთ, რომ ამბობს აქ ამიტომ უკავშირდება სია უკეთესია მასივი. და დატოვონ ეს იმ. იმის გამო, რომ თემა reoccurring ახლა კი, მით უმეტეს, უახლოეს მომავალში, არის რომ არსებობს არ არის აუცილებელი სწორი პასუხი. სწორედ ამიტომ ჩვენ გვაქვს ცალკე ღერძი დიზაინის პრობლემის კომპლექტი. ეს იქნება ძალიან კონტექსტში მგრძნობიარე თუ გსურთ გამოიყენოთ ამ მონაცემთა სტრუქტურის ან რომ ერთი იქნება, და ეს დამოკიდებული, თუ რა მნიშვნელობა აქვს თქვენ თვალსაზრისით რესურსებისა და სირთულის. მაგრამ ნება მიბოძეთ ინიციატივით კი, იდეალური მონაცემები სტრუქტურა, წმინდა გრაალი, იქნებოდა ის, რასაც ის მუდმივად დროს, მიუხედავად იმისა, თუ რამდენად პერსონალის არის მის შიგნით, რომ არ იქნება საოცარი თუ მონაცემთა სტრუქტურის დაბრუნდა პასუხები მუდმივი დროს. დიახ. ეს სიტყვა არის თქვენი დიდი ლექსიკონი. ან არა, ეს სიტყვა არ არის. ან რაიმე მსგავსი პრობლემა არსებობს. ისე ვნახოთ, შევძლებთ თუ არა, სულ მცირე, მიიღოს ნაბიჯი, რომელიც. ნება მომეცით შემოგთავაზოთ ახალი მონაცემები სტრუქტურა, რომელიც შეიძლება გამოყენებულ იქნას სხვადასხვა ნივთები, ამ შემთხვევაში მოუწოდა hash მაგიდასთან. ასე რომ, ჩვენ, ფაქტობრივად, უკან glancing ზე მასივი, ამ შემთხვევაში, და გარკვეულწილად თვითნებურად, მე შედგენილი ამ hash მაგიდაზე მასივში სახის ორგანზომილებიანი მასივი - უფრო სწორად ის გამოსახული აქ ორი განზომილებიანი მასივი - მაგრამ ეს მხოლოდ მასივი ზომა 26, როგორიცაა, რომ თუ ჩვენ მოვუწოდებთ მასივი მაგიდა, მაგიდა bracket ნულოვანი არის ოთხკუთხედის ზედა. მაგიდის bracket 25 მართკუთხედი ბოლოში. სწორედ ასე შეიძლება შევაჩერო მონაცემები სტრუქტურა, რომელიც მე მინდა შესანახად ხალხის სახელები. ასე მაგალითად, მე და არ დაიხევს მთელი რამ აქ მიწისზედა, თუ ჰქონდა ამ მასივი, რომელიც მე ახლა აპირებს მოვუწოდებთ hash მაგიდა, და ეს კიდევ ერთხელ საიდან ნულოვანი. ეს აქ საიდან ერთი, და სხვ. I აცხადებენ, რომ მინდა ამ მონაცემთა სტრუქტურა, გულისთვის დისკუსია, შესანახად ხალხის სახელები, ელის და ბობ ჩარლი და სხვა მსგავსი სახელები. ასე რომ, ვფიქრობ, ეს ახლა, როგორც წამოწყება საქართველოს, ვთქვათ, ლექსიკონი უამრავი სიტყვა. ისინი არ უნდა იყოს სახელები ჩვენს მაგალითად აქ. და ეს არის ძალიან გერმანე, ალბათ, რომ ახორციელებს მართლწერის შემოწმება, როგორც ჩვენ შეიძლება პრობლემის მითითებული ექვსი. ასე რომ, თუ ჩვენ გვაქვს მასივი საერთო ზომა 26 ასე, რომ ეს არის 25 ადგილმდებარეობა ბოლოში, და მე კი აცხადებენ, რომ Alice არის პირველი სიტყვა ლექსიკონი სახელები მინდა ჩადეთ შევიდა RAM, შევიდა ამ მონაცემთა სტრუქტურა, სადაც ინსტინქტები გეუბნებით, რომ Alice-ს სახელი უნდა წავიდეს ამ მასივი? ჩვენ გვყავს 26 პარამეტრები. სად გვინდა დააყენა მისი? ჩვენ გვინდა, რომ მისი bracket ნულოვანი, არა? ამისთვის ელის, მოდით მოვუწოდებთ, რომ ნულოვანი. და B იქნება ერთი, და C იქნება ორი. ასე რომ, ჩვენ ვაპირებთ დაწერა Alice-ის სახელს აქ. თუ ჩვენ შემდეგ ჩადეთ ბობ, მისი სახელი წავა აქ. ჩარლი წავა აქ. და ა.შ. ქვემოთ მეშვეობით ამ მონაცემთა სტრუქტურას. ეს არის შესანიშნავი მონაცემების სტრუქტურას. რატომ? ისე, რა არის გაშვებული დრო ჩასმის ადამიანის სახელწოდება და ამ მონაცემთა სტრუქტურის ახლა? იმის გათვალისწინებით, რომ ამ მაგიდასთან ხორციელდება, მართლაც, როგორც მასივი. ისე ეს მუდმივი დროს. ეს ბრძანებით ერთი. რატომ? ისე როგორ განსაზღვრავენ სადაც Alice ეკუთვნის? გადავხედავთ, რომელიც წერილში მისი სახელი? პირველი. და შეგიძლიათ იქ, თუ ეს ტექსტი, მხოლოდ ეძებს სიმებიანი bracket ნულოვანი. ასე რომ zeroth ხასიათის სიმებიანი. ეს არის ის, მარტივია. ჩვენ რომ შიფრის დავალება კვირის წინ. და მაშინ ერთხელ თქვენ იცით, რომ Alice-ს წერილს ხელს დედაქალაქში, ჩვენ შეგვიძლია სხვაობა off 65 ან კაპიტალი თავად, რომ გვაძლევს ნულოვანი. ასე რომ, ჩვენ ვიცით, რომ Alice ეკუთვნის ზე ადგილმდებარეობა ნულოვანი. და მოცემული მაჩვენებელი ამ მონაცემების სტრუქტურა, რაიმე სახის, რამდენი ხანი დასჭირდა ჩემთვის მოძიების მდებარეობა ნულოვანი in მასივი? მხოლოდ ერთი ნაბიჯია, მარჯვენა ის მუდმივ დრო გამო წვდომის ჩვენ შემოთავაზებული იყო თვისება მასივი. ასე რომ, მოკლედ, მჭიდროდაა რა ინდექსი საქართველოს Alice სახელთან, რომელიც, თავის ამ შემთხვევაში, არის, ან მოდით უბრალოდ მოსაგვარებლად რომ ნულის, სადაც B ერთია და C არის ორი, მჭიდროდაა რომ არის მუდმივი დროს. უბრალოდ უნდა შევხედოთ მისი პირველი წერილი, მჭიდროდაა თუ სად ნულოვანი არის მასივი ასევე მუდმივ დრო. ასე რომ ტექნიკურად, რომ ისევე, როგორც ორი ნაბიჯი არის. მაგრამ ეს ჯერ კიდევ მუდმივი. აქედან გამომდინარე, მოვუწოდებ, რომ დიდი O ერთი, ასე რომ ჩვენ შეიყვანეს Alice შევიდა ამ მაგიდაზე მუდმივი დროს. მაგრამ, რა თქმა უნდა, მე როგორც გულუბრყვილო აქ, არა? რა მოხდება, თუ არ არსებობს აარონის ამ კლასში? ან Alicia? ან ნებისმიერ სხვა სახელები დაწყებული ა სად მივდივართ დააყენოს რომ ადამიანი, არა? ვგულისხმობ, ახლა იქ მხოლოდ სამი ხალხს მაგიდაზე, იქნებ ჩვენ უნდა დააყენოს Aaron at მდებარეობა ნულოვანი ერთი ორი სამი. მარჯვენა, მე ვერ დააყენა აქ. მაგრამ შემდეგ, თუ ჩვენ ვცდილობთ ჩასასმელი დავით შევიდა ამ სიაში, სადაც ამჯამად დავით წავიდეთ? ახლა ჩვენი სისტემა იწყებს არღვევს ქვემოთ, არა? იმის გამო, რომ ახლა დავით მთავრდება აქ თუ აარონის ფაქტიურად აქ. ასე რომ, ახლა ეს მთელი იდეა, რომელსაც სუფთა მონაცემთა სტრუქტურა, რომელიც გვაძლევს მუდმივი დროის insertions აღარ არის მუდმივი დროს, იმიტომ, რომ მე უნდა შეამოწმოს, oh, damnit, ვიღაცამ უკვე ზე Alice ადგილსამყოფელი. ნება მომეცით გამოძიების დანარჩენი ამ მონაცემთა სტრუქტურა, ეძებს ადგილზე დააყენოს ვინმეს მოსწონს აარონის სახელი. ასე რომ, რომ ძალიან იწყებს მიიღოს წრფივი დროს. უფრო მეტიც, თუ თქვენ ახლა სურს იპოვოს აარონის ამ მონაცემთა სტრუქტურის და შეამოწმოს და აარონის სახელი არაა აქ. სასურველია, თქვენ უბრალოდ ამბობენ აარონის არ მონაცემების სტრუქტურას. მაგრამ თუ დაიწყოთ ოთახი აარონის, სადაც არ უნდა ყოფილიყო D ან E, თქვენ, უარეს შემთხვევაში, უნდა შეამოწმოს მთელი მონაცემთა სტრუქტურის, ამ რა შემთხვევაში ეს devolves შევიდა რაღაც წრფივი in ზომის მაგიდასთან. ასე რომ, ყველა უფლება, მე დაფიქსირება ამ. პრობლემა ისაა, რომ მე მქონდა 26 ელემენტები ამ მასივი. ნება მომეცით შეცვლის. Whoops. ნება მომეცით შეიცვალოს ისე, რომ საკმაოდ დავანებოთ ზომა 26 საერთო ჯამში, შეამჩნია ბოლოში ინდექსი აპირებს შეცვალოს to ო მინუს 1. თუ 26 აშკარად ძალიან მცირე ადამიანის გვარი, სახელი, რადგან არსებობს ათას სახელების მსოფლიოში, მოდით მხოლოდ 100 ან 1000 ან 10,000. მოდით, უბრალოდ გამოყოფს გაცილებით მეტი სივრცე. ისე, რომ სულაც არ შემცირდება ალბათობა იმისა, რომ ჩვენ არ გვაქვს ორი ადამიანებს სახელები დაწყებული და ისე, თქვენ მიდიოდნენ ცდილობენ სახელები ზე ადგილმდებარეობა ნულოვანი მაინც. ისინი მაინც გეგმავს დაეჯახება, რომელიც ნიშნავს, რომ ჩვენ ჯერ კიდევ გამოსავალი დააყენოს Alice და აარონი და Alicia და სხვა სახელები დაწყებული მის ფარგლებს გარეთ. მაგრამ რამდენად პრობლემაა ეს? რა არის ალბათობა, რომ თქვენ აქვს შეჯახება in მონაცემები სტრუქტურა ასე? ისე, მინდა გითხრათ, - ჩვენ დავბრუნდებით ამ კითხვაზე აქ. და შეხედეთ, როგორ შეიძლება გადაწყვიტოს იგი. ნება მომეცით გაიყვანოს ეს წინადადება აქ. რასაც ჩვენ მხოლოდ აღწერილი არის ალგორითმი, heuristic მოუწოდა წრფივი საცდელი რომლის, თუ ცდილობდა ჩადეთ რამე ამ მონაცემების სტრუქტურა, რომელსაც hash მაგიდა, და არ არსებობს ოთახი არსებობს, თქვენ ნამდვილად გამოძიების მონაცემთა სტრუქტურის შემოწმების, ეს შესაძლებელი? არის ეს ხელმისაწვდომია არის ეს შესაძლებელი? არის თუ არა ეს შესაძლებელი? და როდესაც საბოლოოდ არის, თქვენ ჩადეთ ასახელებს, რომ თქვენ თავდაპირველად გამიზნული სხვაგან იყო. მაგრამ უარეს შემთხვევაში, მხოლოდ ადგილზე შეიძლება იყოს ძალიან ბოლოში მონაცემები სტრუქტურა, ძალიან ბოლოს მასივი. ასე რომ წრფივი საცდელი, უარეს შემთხვევაში, devolves შევიდა წრფივი ალგორითმი, სადაც აარონის, თუ მოხდება უნდა დაემატოს ბოლო ამ მონაცემების სტრუქტურას, მან შეიძლება დაეჯახება ამ პირველი მდებარეობა, მაგრამ შემდეგ დასრულდება ცუდი წარმატებას at ბოლომდე. ასე რომ, ეს არ არის მუდმივი დრო წმინდა გრაალი ჩვენთვის. ეს მიდგომა ჩასმის ელემენტები შეიტანა მონაცემთა სტრუქტურის მოუწოდა hash მაგიდასთან არ ჩანს, იყოს მუდმივი დრო მაინც არ ზოგად შემთხვევაში. მას შეუძლია გადაეცემა შევიდა რაღაც სწორხაზოვან. მერე რა რომ ჩვენ გადავწყვიტოთ შეჯახება გარკვეულწილად განსხვავებულად? ასე რომ, აქ არის უფრო დახვეწილი მივუდგეთ რა მაინც მოუწოდა hash მაგიდასთან. და hash, როგორც განზე, რა ვგულისხმობ არის მაჩვენებელი, რომ მე მოხსენიებული ადრე. დან hash რაღაც შეიძლება იყოს ფიქრობდა, როგორც ზმნა. ასე რომ, თუ hash Alice ის სახელი, hash ფუნქცია, ასე ვთქვათ, უნდა დაუბრუნდეს ნომერი. ამ შემთხვევაში ნულის ტოლია, თუ ის მიეკუთვნება ზე საიდან ნულოვანი, ერთი თუ ის ეკუთვნის ზე ადგილმდებარეობა ერთი, და სხვ. ასე რომ, ჩემი hash ფუნქცია დღემდე უკვე სუპერ მარტივი, მხოლოდ შევხედავთ პირველი წერილი სხვის სახელი. მაგრამ hash ფუნქცია იღებს როგორც შეყვანის გარკვეული ნაწილი მონაცემებით, სიმებიანი, int, რასაც. და ეს spits out როგორც წესი ნომერი. და ეს რიცხვი, სადაც, რომ მონაცემები ელემენტს ეკუთვნის ამ მონაცემთა სტრუქტურის ცნობილია, აქ, hash მაგიდასთან. ასე რომ მხოლოდ ინტუიციურად, ეს ოდნავ სხვა კონტექსტში. ეს რეალურად გულისხმობდა მაგალითად ჩართვის დაბადების, სადაც შეიძლება იყოს, რაც უფრო მეტი 31 დღის განმავლობაში თვეში. მაგრამ რა ამ ადამიანს გადაწყვეტენ ამის გაკეთება იმ შემთხვევაში შეჯახება? კონტექსტი ახლა კი, არ შეჯახების სახელები, მაგრამ შეჯახების დაბადების დღეები, თუ ორ ადამიანს აქვს იგივე დაბადების დღე on 2 ოქტომბერი, მაგალითად. სტუდენტი: [inaudible]. დინამიკები 1: ჰო, ასე რომ აქ გვაქვს ოპერაციული დაკავშირებული სიები. ასე გამოიყურება ცოტა განსხვავებულად ვიდრე ჩვენ მიიპყრო მას ადრე. მაგრამ ჩვენ, როგორც ჩანს, უნდა მასივი მარცხენა მხარეს. ეს ერთი მაჩვენებელი, არა კონკრეტული მიზეზი. მაგრამ მაინც მასივი. ეს მასივი მითითებას. და თითოეული იმ ელემენტებს, თითოეული ამ წრეებში ან დახრილ ხაზებს - ხაზი წარმოადგენს null - თითოეული ამ მითითებები აშკარად მიუთითებს რა მონაცემების სტრუქტურას? უკავშირდება სიაში. ასე რომ, ახლა ჩვენ გვაქვს შესაძლებლობა მძიმე კოდი შევიდა ჩვენი პროგრამა ზომის მაგიდასთან. ამ შემთხვევაში, ჩვენ ვიცით, რომ არსებობს არასდროს ზე მეტი 31 დღის განმავლობაში თვეში. ასე კოდირების ღირებულება, როგორიცაა 31 არის გონივრული ამ კონტექსტში. კონტექსტში სახელები, მძიმე კოდირების 26 არ არის დაუსაბუთებელი ეს ხალხის სახელები მხოლოდ იწყება, მაგალითად, დამწერლობა ჩართვის გზით ზ ჩვენ შეგვიძლია cram მათ ყველა შევიდა, რომ მონაცემები სტრუქტურა ისე, სანამ, როდესაც მივიღებთ შეჯახება, ჩვენ არ დააყენა სახელები აქ, ჩვენ ნაცვლად ვფიქრობ ეს საკნები არა როგორც strings თავს, მაგრამ, როგორც მითითებას, მაგალითად, ელის. და მაშინ Alice შეიძლება კიდევ ერთი მაჩვენებელი მეორეში სახელი დაწყებული ა და ბობ რეალურად მიდის აქ. და თუ არსებობს სხვა სახელი იწყება ერთად B, იგი მთავრდება მეტი აქ. ასე რომ, თითოეული ელემენტები ამ მაგიდაზე ორი, თუ ჩვენ შემუშავებული ამ უფრო ჭკვიანურად - მოვა - თუ ჩვენ შემუშავებული ამ ცოტა მეტი ჭკვიანურად, ახლა ხდება ადაპტური მონაცემები სტრუქტურა, სადაც არ არსებობს მყარი ზღვარი რამდენი ელემენტები ჩადეთ შევიდა, რადგან, თუ აქვს შეჯახება, რომ ეს ჯარიმა. უბრალოდ წავიდეთ წინ და დამატება მას ის, რაც ჩვენ ვნახეთ, ცოტა წინ იყო ცნობილი უკავშირდება სიაში. ისე მოდით პაუზის მხოლოდ ერთი წუთით. რა არის ალბათობა შეჯახება პირველ რიგში? მარჯვენა, იქნებ მე მეტი ფიქრი, შესაძლოა, მე მეტი საინჟინრო ეს პრობლემა, იმიტომ, რომ თქვენ იცით რა? დიახ, მე ვერ ამუშავება თვითნებური მაგალითები off დაბრუნება ჩემი უფროსი მოსწონს ელისონ და აარონ, მაგრამ სინამდვილეში, მოცემული თანაბარი განაწილება საშუალებებით, რომ არის გარკვეული შემთხვევითი insertions შევიდა მონაცემთა სტრუქტურა, რა არის ალბათობა შეჯახება? ისე გამოდის, სინამდვილეში სუპერ მაღალი. ნება მომეცით განზოგადება ამ პრობლემა ის არის, როგორც ეს. ასე რომ, ოთახში n CS50 სტუდენტები, რა ალბათობა იმისა, რომ სულ მცირე ორი სტუდენტი ოთახში აქვს იგივე დაბადების დღე? ასე რომ, ის, რაც. რამდენიმე Hund - 200, 300 ხალხი აქ და რამდენიმე ასეული ადამიანი სახლში იმყოფება. ასე რომ, თუ უნდოდათ, საკუთარ თავს ვკითხოთ რა ალბათობა ორი ადამიანი ამ ოთახში, რომელსაც იგივე დაბადების დღე, ჩვენ შეგვიძლია ახერხებს ამ out. და მე პრეტენზია რეალურად არსებობს ორი ადამიანებს იგივე დაბადების დღე. მაგალითად, ვის აქვს აქვს დაბადების დღეს? გუშინ? ხვალ? ყველა უფლება, ასე რომ იგრძნობა მე ვაპირებ უნდა გავაკეთოთ ეს 363 ან ასე უფრო ჯერ რეალურად გაერკვნენ თუ ჩვენ გვაქვს შეჯახება. ან ჩვენ შეიძლება მხოლოდ ამის გაკეთება მათემატიკურად ვიდრე tediously აკეთებენ. და შესთავაზოს შემდეგ. ამიტომ მე ვთავაზობ, რომ ჩვენ შეგვიძლია მოდელირებისთვის ალბათობა ორი ადამიანი, რომელსაც იგივე დაბადების დღე როგორც ალბათობა 1 მინუსი ალბათობა არავინ მქონე იგივე დაბადების დღე. ასე რომ მიიღოს ეს, და ეს მხოლოდ მიეცით გზა წერა ამ, for პირველი პირი ოთახი, მას შეიძლება ჰქონდეს ნებისმიერი შესაძლო დაბადების ვთქვათ, 365 დღე წელიწადში, ერთად ბოდიშს to მქონე პირთა 29 თებერვალი დაბადების დღე. ასე რომ, პირველი პირი ამ ოთახში არის თავისუფალი რაიმე რაოდენობის დაბადების აქედან 365 შესაძლებლობები ისე, რომ ჩვენ ყველაფერს გავაკეთებთ, რომ 365 იყოფა 365, რომელიც ერთი. მომდევნო ოთახში, თუ გოლი თავიდან შეჯახება, მხოლოდ აქვს თავისი დაბადების დღე, თუ როგორ სხვადასხვა შესაძლო დღეებში? 364. ასე რომ, მეორე ვადით ამ გამოხატვის არსებითად აკეთებს, რომ მათემატიკის ჩვენთვის by subtracting off ერთ შესაძლო დღეში. შემდეგ კი მეორე დღეს, მეორე დღეს, მეორე დღეს ქვემოთ საერთო რაოდენობა ადამიანი ოთახში. და თუ ჩვენ შემდეგ განიხილავს, რაც მაშინ არის ალბათობა არა ყველას მქონე უნიკალური დაბადების დღეები, თუმცა ისევ და ისევ 1 მინუსი რომ, რასაც ჩვენ მივიღებთ არის გამოხატულება რომელიც შეიძლება ძალიან fancifully გამოიყურება ასე. მაგრამ ეს უფრო საინტერესო შევხედოთ ვიზუალურად. ეს არის სქემა სადაც x-ღერძი არის ადამიანთა რიცხვი, ოთახში, რიგი დაბადების. On Y-ღერძი არის ალბათობა საქართველოს შეჯახება, ორი ადამიანი მქონე იგივე დაბადების დღე. და takeaway ამ მრუდის რომ როგორც კი თქვენ მინდა 40 სტუდენტები, თქვენ up at 90% ალბათობა combinatorically ორი ადამიანი ან მეტი მქონე იგივე დაბადების დღე. და კიდევ თქვენ მინდა 58 ადამიანი ეს თითქმის 100% შანსი ორ ადამიანი ოთახში გვექნება იგივე დაბადების დღე, მიუხედავად იმისა, რომ არსებობს 365 ან 366 შესაძლო თაიგულების და მხოლოდ 58 ადამიანი ოთახში. უბრალოდ სტატისტიკურად თქვენ სავარაუდოდ მიიღეთ შეჯახება, რომელიც მოკლე ხელს ამ დისკუსიის შესახებ. რომ თუნდაც მივიღებთ ლამაზი აქ, და დაიწყება, რომელსაც ეს ჯაჭვების, ჩვენ ჯერ კიდევ გვექნება შეჯახება. ასე რომ, სთხოვს კითხვაზე, თუ რა არის ღირებულება აკეთებს insertions და წაშლებს შევიდა მონაცემთა სტრუქტურის ასე? ისე ნება მომეცით შესთავაზოს - და ნება მომეცით დაბრუნდეს ეკრანზე მეტი აქ - თუ ჩვენ n ელემენტების სია, ასე რომ, თუ ჩვენ ვცდილობთ ჩასასმელად ნ ელემენტები, და ჩვენ რამდენი საერთო თაიგულების? ვთქვათ 31 სულ თაიგულების იმ შემთხვევაში, თუ დაბადების. რა არის მაქსიმალური სიგრძე ერთი ამ ჯაჭვების პოტენციურად? თუ ისევ არსებობს 31 შესაძლო დაბადების მოცემულ თვეში. და ჩვენ უბრალოდ clumping ყველას - რეალურად, რომ სულელური მაგალითი. მოდით 26 ნაცვლად. ასე რომ, თუ რეალურად ადამიანები, რომელთა სახელები იწყება მეშვეობით Z, რითაც us 26 შესაძლებლობები. და ვიყენებთ მონაცემთა სტრუქტურის მოსწონს ერთი ჩვენ უბრალოდ დაინახა, სადაც ჩვენ გვაქვს მასივი მითითებას, რომელთაგან თითოეული ქულები დაკავშირებული სიაში, სადაც პირველი სია ყველას იმ სახელით Alice. მეორე სიაში არის ყველა ერთად ასახელებს დაწყებული, დაწყებული ერთად B, და ა.შ.. რა არის სავარაუდოდ ხანგრძლივობა თითოეულ იმ სიებს, თუ დავუშვებთ, ლამაზი სუფთა განაწილების სახელები მეშვეობით Z მთელ მონაცემთა სტრუქტურის? აქ არის ო ადამიანი მონაცემთა სტრუქტურის იყოფა 26, თუ ისინი ლამაზად გავრცელდა მთელ მონაცემთა სტრუქტურას. ასე ხანგრძლივობა თითოეულ ამ ჯაჭვების არის n იყოფა 26. მაგრამ დიდი O notation, რა არის ეს? რა არის ეს ნამდვილად? ასე რომ, ეს უბრალოდ ო, არა? იმიტომ, რომ ჩვენ უკვე აღვნიშნე, რომ წარსულში, რომ ugh თქვენ დაყოფის 26. დიახ, სინამდვილეში ეს არის სწრაფად. თუმცა თეორიულად, ეს არ არის პრინციპულად ყველა რომ სწრაფად. ასე რომ, ჩვენ არ ჩანს ყველა, რომ ბევრად დაახლოება ამ წმინდა გრაალი. ფაქტობრივად, ეს მხოლოდ წრფივი დროს. Heck, ამ ეტაპზე, რატომ არ გვაქვს უბრალოდ გამოიყენოთ ერთი დიდი უკავშირდება სიაში? რატომ არ ჩვენ უბრალოდ გამოიყენოთ ერთი დიდი მასივი შესანახად სახელწოდებას ყველას ოთახში? ასევე, არის კიდევ რაღაც მყარი შესახებ hash მაგიდაზე? არსებობს ჯერ კიდევ რაღაც მყარი შესახებ მონაცემთა სტრუქტურის რომ ჰგავს ეს? ეს. სტუდენტი: [inaudible]. დინამიკები 1: Right, და ისევ, თუ უბრალოდ წრფივი დრო ალგორითმი და წრფივი დროში მონაცემთა სტრუქტურა, რატომ არ უბრალოდ შეინახოს ყველას სახელს დიდი მასივი, ან დიდი უკავშირდება სიაში? და შეწყვიტოს მიღების CS ასე ბევრად უფრო რთული ვიდრე ეს უნდა იყოს? რა არის მყარი შესახებ, მაშინაც კი, თუმცა მე scratched ის? სტუდენტი: [inaudible]. დინამიკები 1: Insertions არ არიან? ძვირადღირებული აღარაა. ასე რომ insertions პოტენციურად შესაძლოა ჯერ კიდევ იყოს მუდმივი დროს, მაშინაც კი, თუ თქვენი მონაცემები სტრუქტურა ასე გამოიყურება, მასივი მითითებები, რომელთაგან თითოეული მიუთითებს პოტენციურად დაკავშირებული სიაში. როგორ შეიძლება თქვენ მისაღწევად მუდმივი დრო ჩასმა სახელები? გამყარებაში მას წინ, არა? თუ ჩვენ შესწირონ დიზაინი მიზანი დან ადრე, სადაც გვინდოდა, რომ შევინარჩუნოთ ყველას სახელით, მაგალითად, დალაგებულია, ან ყველა ციფრები სცენაზე დალაგებულია, ვარაუდობენ, რომ ჩვენ გვაქვს დაუხარისხებელი უკავშირდება სიაში. ეს მხოლოდ ღირს us ერთი ან ორი ნაბიჯი, მინდა იმ შემთხვევაში, ბენ და ბრაიან ადრე, ჩასასმელი ელემენტს ზე დასაწყისში სიაში. ასე რომ, თუ ჩვენ არ აინტერესებს დახარისხება ყველა საქართველოს სახელები დაწყებული ან ყველა სახელები დაწყებული B, ჩვენ მაინც მისაღწევად მუდმივად დრო ჩასაგდები. ახლა ეძებს Alice ან ბობ ან ნებისმიერი სახელი ზოგადად ჯერ კიდევ რა? ეს დიდი ო ო იყოფა 26 წლის იდეალური შემთხვევაა, როდესაც ყველას ერთნაირად გავრცელება, სადაც არ არის, როგორც ბევრი ნახვა რადგან Z-ის, რაც ალბათ არარეალურია. მაგრამ ეს ჯერ კიდევ წრფივი. მაგრამ აქ ჩვენ დავბრუნდებით წერტილი საქართველოს asymptotic notation მყოფი თეორიულად ასეა. მაგრამ რეალურ ცხოვრებაში, თუ აცხადებენ, რომ ჩემი პროგრამას შეუძლია გააკეთოს რაღაც 26 times სწრაფად, ვიდრე თქვენი, რომლის პროგრამა აპირებთ თუ ურჩევნია გამოყენებით? Yours ან აფეთქდა, რომელიც არის 26 ჯერ უფრო სწრაფად? რეალურად, პირი, რომლის არის 26 ჯერ უფრო სწრაფად, თუნდაც თეორიულად ჩვენი ალგორითმები აწარმოებს იგივე asymptotic ქრონომეტრაჟი. ნება მომეცით შემოგთავაზოთ სხვადასხვა გადაწყვეტა საერთოდ. და თუ ეს არ აფეთქება თქვენი გონება, ჩვენ გარეთ მონაცემთა სტრუქტურები. ასე რომ, ეს არის ის trie - სახის სულელური სახელი. მოდის retrievals და სიტყვა არის ჩაწერეთ trie, t-r-i-e, რადგან რა თქმა უნდა, კითხვის ჟღერს trie. მაგრამ ეს ისტორიაში სიტყვის trie. ასე რომ trie მართლაც ერთგვარი ხე, და ეს ასევე თამაში, რომ სიტყვა. და მიუხედავად იმისა, ვერ საკმაოდ დანახვა ამ ვიზუალიზაცია, trie არის ხე სტრუქტურა, ისევე როგორც ოჯახის ხეს ერთი წინაპარი ზედა და უამრავი საქართველოს შვილიშვილი და დიდი შვილიშვილი როგორც ტოვებს ქვედა. მაგრამ ყოველ კვანძის in trie არის მასივი. და ეს მასივი - და მოდით oversimplify ერთი წუთით - ეს მასივი, ამ შემთხვევაში, რა ზომა 26, სადაც ყოველი კვანძის ერთხელ მასივი ზომა 26, სადაც zeroth ელემენტია, რომელიც მასივი წარმოადგენს, ხოლო ბოლო ელემენტის ყოველი ასეთი მასივი წარმოადგენს ზ ამიტომ მე ვთავაზობ, მაშინ, რომ ეს მონაცემები სტრუქტურა, რომელიც ცნობილია როგორც trie, შეიძლება იყოს გამოიყენება ასევე შესანახად სიტყვა. ჩვენ ვნახეთ მომენტში წინ, როგორ შეგვეძლო შესანახად სიტყვა, ან ამ შემთხვევაში სახელები და ჩვენ დაინახა ადრე როგორ შეგვიძლია შესანახად ნომრები, მაგრამ თუ ჩვენ ფოკუსირება სახელები ან strings აქ, შეამჩნია რა საინტერესოა. I აცხადებენ, რომ სახელი Maxwell არის შიგნით ამ მონაცემთა სტრუქტურას. მიგაჩნიათ სად Maxwell? სტუდენტი: [inaudible]. დინამიკები 1: მარცხენა. რა არის საინტერესო ამ მონაცემთა სტრუქტურა ვიდრე მაღაზიაში სიმებიანი M-A-X-W-E-L-L წარმატებული ნულოვანი, ყველა contiguously, რას ნაცვლად გააკეთებს ასეთია. თუ ეს trie მოსწონს მონაცემთა სტრუქტურის, თითოეული რომელთა კვანძების კვლავ მასივი, და გსურთ შესანახად Maxwell, პირველად ინდექსი და ასე ძირეული-ის კვანძის, ასე ვთქვათ, ზედოთ მდებარე კვანძის, ზე ადგილმდებარეობა M, უფლება, უხეშად შევიდა ცენტრიდან. და მაშინ იქიდან, დაიცვას მომცეთ ბავშვის კვანძების, ასე ვთქვათ. ასე რომ, ოჯახის ხე გრძნობა, თქვენ დაიცვას ის ქვევით. და რომ გამოიწვიოს თქვენ კიდევ ერთი კვანძის შედეგად მარცხენა არსებობს, რომელიც კიდევ ერთი მასივი. და მაშინ, თუ გნებავთ შესანახად Maxwell, თქვენთვის მაჩვენებელი, რომელიც წარმოადგენს , რომელიც ამ ერთი აქ. მაშინ მისვლა მომდევნო კვანძის. და შეამჩნია - ამიტომ სურათის ცოტა იტყუებენ - ამ კვანძის გამოიყურება სუპერ პატარა. მაგრამ მარჯვნივ ეს Y და ზ უბრალოდ ავტორს truncated სურათს ასე რომ თქვენ რეალურად ვხედავ რამ. წინააღმდეგ შემთხვევაში ამ სურათს იქნება უკიდურესად კარს. ასე რომ, ახლა თქვენ ინდექსი შევიდა ადგილმდებარეობა X, მაშინ W, მაშინ E, მაშინ L, მაშინ ლ მაშინ რა ამ ცნობისმოყვარეობა? ისე, თუ ვიყენებთ ამ სახის ახალი მიიღებს თუ როგორ შესანახად სიმებიანი in მონაცემთა სტრუქტურა, თქვენ კვლავ უნდა არსებითად შეამოწმოს ში მონაცემები სტრუქტურა, რომელიც სიტყვის დამთავრდა აქ. სხვა სიტყვებით, თითოეული ამ კვანძების როგორმე უნდა გვახსოვდეს, რომ ჩვენ რეალურად მოჰყვა ყველა ამ მითითებას და ტოვებს ცოტა პური crumb ბოლოში აქ ამ სტრუქტურა მიუთითოს M-A-X-W-E-L-L არის მართლაც ამ მონაცემთა სტრუქტურას. ასე რომ, ჩვენ შეიძლება გავაკეთოთ ამ ასეთია. თითოეული კვანძების სურათს ჩვენ უბრალოდ დაინახა ერთი, მასივი ზომა 27. და ეს ახლა 27, რადგან ჟ მითითებული ექვსი, ჩვენ, ფაქტობრივად, გადმოგცეთ აპოსტროფი, ასე, რომ შეგვიძლია სახელები, როგორიცაა O'Reilly და სხვ apostrophes. მაგრამ იგივე იდეა. თითოეული მათგანი ელემენტების მასივი ქულები struct კვანძის, ასე რომ მხოლოდ კვანძის. ასე რომ, ეს ძალიან თქვენში ჩვენი დაკავშირებული სიაში. და მაშინ მე მაქვს ლოგიკური, რომელიც მე მოვუწოდებთ სიტყვა, რომელიც მხოლოდ იქნება ჭეშმარიტი, თუ სიტყვა მთავრდება ამ კვანძის in ხე. იგი ეფექტურად წარმოადგენს პატარა სამკუთხედის დავინახეთ მომენტში წინ. ასე რომ, თუ სიტყვა მთავრდება, რომ კვანძის in ხე, რომ სიტყვა სფეროში იქნება ნამდვილი, რომელიც კონცეპტუალურად შემოწმების off, ან ჩვენ ხატვის ამ სამკუთხედის, დიახ არსებობს არის სიტყვა აქ. ასე რომ, ეს trie. ახლა კი კითხვა არის, რა მისი ქრონომეტრაჟი? არის თუ არა დიდი ო ო? არის თუ არა რაიმე სხვა? ისე, თუ თქვენ არ n სახელები ამ მონაცემების სტრუქტურა, მაქსველი, რომ მხოლოდ ერთი მათ, რა არის გაშვებული დრო ჩასმის ან მოძიებაში Maxwell? რა არის ქრონომეტრაჟი საქართველოს ჩასმის Maxwell? თუ არსებობს n სხვა სახელები უკვე მაგიდაზე? ჰო? სტუდენტი: [inaudible]. დინამიკები 1: ჰო, ის სიგრძის საქართველოს სახელით, არა? ასე რომ, M--x-w-e-l-l ასე რომ იგრძნობა ამ ალგორითმი დიდი O შვიდი. ახლა, რა თქმა უნდა, სახელი იცვლება სიგრძის. იქნებ ეს მოკლე სახელი. იქნებ ეს აღარ სახელი. მაგრამ რა არის აქ მთავარია არის ის, რომ ეს მუდმივი ნომერი. და, შესაძლოა, ეს არ არის ნამდვილად მუდმივი, მაგრამ ღმერთი, თუ რეალურად, ამ ლექსიკონი, იქ, ალბათ, რაღაც ზღვარი რაოდენობის შესახებ წერილები პირის სახელი კონკრეტულ ქვეყანაში. ასე რომ, ჩვენ შეიძლება ვივარაუდოთ, რომ ღირებულება არის მუდმივი. მე არ ვიცი რა არის. ალბათ აღემატება ჩვენ მიგვაჩნია, რომ ეს არის. იმის გამო, რომ იქ ყოველთვის რაღაც კუთხეში საქმე გიჟები ხანგრძლივი სახელი. მოდით დავარქვათ ლ, მაგრამ მაინც მუდმივი სავარაუდოდ, რადგან ყველა ასახელებს მსოფლიოში მაინც, კონკრეტული ქვეყნის, არის ის, რომ სიგრძის ან მოკლე, ამიტომ მუდმივი. მაგრამ როდესაც ჩვენ განაცხადა, რომ რაღაც დიდი O of მუდმივი ღირებულება, რა, რომ მართლაც ექვივალენტურია? ეს მართლაც იგივე დაყრდნობით მუდმივ დრო. ახლა ჩვენ ერთგვარი მოტყუების, არა? ჩვენ სახის ოპერაციული ზოგიერთი თეორია აქ ამბობენ, რომ კარგად, ბრძანებით ლ არის რეალურად მხოლოდ ბრძანებით ერთი, და ეს მუდმივი დროს. მაგრამ ეს ნამდვილად არის. იმის გამო, რომ გასაღები რისთვისაც აქ არის ის, რომ თუ ჩვენ n სახელები უკვე ამ მონაცემთა სტრუქტურის და ჩვენ ჩანართით Maxwell, არის დროის სჭირდება გვაძლევს ჩადეთ Maxwell ყველა ზემოქმედების ქვეშ მყოფი რამდენად ბევრი სხვა ხალხი არიან მონაცემთა სტრუქტურის? არ ჩანს. მე რომ მილიარდი მეტი ელემენტები ამ trie, შემდეგ ჩადეთ Maxwell არის მან ყველა დაზარალებული? პოსტები სწორედ განსხვავებით, დღის მონაცემები სტრუქტურები ჩვენ ვნახეთ დღემდე, სადაც გაშვებული დრო თქვენი ალგორითმი სრულიად დამოუკიდებელი, რამდენად პერსონალის არის ან არ არის უკვე ამ მონაცემების სტრუქტურას. ასე რომ, ეს affords თქვენ ახლა არის შესაძლებლობა ჟ ნაკრები ექვსი, რომელიც ერთხელ ჩართვას ახორციელებს საკუთარი მართლწერის შემოწმება, კითხულობს 150,000 სიტყვები, თუ როგორ შესანახად, რომ არ არის აუცილებელი აშკარაა. და თუმცა მე ესწრაფოდნენ, რათა იპოვოს წმინდა გრაალი, მე არ აცხადებენ, რომ trie არის. ფაქტობრივად, hash მაგიდა შეიძლება ძალიან კარგად აღმოჩნდა ბევრად უფრო ეფექტური. მაგრამ ეს მხოლოდ - ეს მხოლოდ ერთი დიზაინი გადაწყვეტილებები თქვენ უნდა მიიღოს. მაგრამ დახურვის ავიღოთ 50 ან ასე წამში მიიღოს peek რა დევს წინ ანგარიშით მომავალ კვირას და მის ფარგლებს გარეთ ჩვენ გარდამავალ ამ ბრძანების ხაზი მსოფლიოში თუ C პროგრამების რამ ვებგვერდი საფუძველზე და ენებს, როგორიცაა PHP და JavaScript და ინტერნეტის თავად, ოქმები, როგორიცაა HTTP, რომელიც თქვენ მიღებული გაცემული წლის ახლა, და ნაბეჭდ საუკეთესო ყველა დღეს, ალბათ, ან უნახავს. და ჩვენ დავიწყებთ კანი უკან ფენების, რა არის ინტერნეტი. და რა არის კოდი, რომელიც უდევს დღევანდელ ინსტრუმენტები. ასე რომ, 50 წამი ამ teaser აქ. მე გაძლევთ Warriors of ტელევიზია. [ვიდეო აღწარმოების] -ის მოყვა გაგზავნა. მატჩის ოქმი ყველა საკუთარი. იგი მოვიდა სამყაროს სასტიკი ეკრანები, uncaring მარშრუტიზატორები, და საფრთხეების შორს უარესი სიკვდილი. ის სწრაფად. ის ძლიერი. ის TCPIP. ხოლო მან მიიღო თქვენს მისამართზე. Warriors of ტელევიზია. [END ვიდეო აღწარმოების] დინამიკები 1: ასე ინტერნეტით ვიმუშავებთ, როგორც მომავალ კვირას.