[მუსიკის დაკვრა] დევიდ ჯ Malan: ყველა უფლება. ეს არის CS50. ეს არის კვირაში ხუთი გაგრძელდება და ჩვენ რამდენიმე კარგი ამბავი და ზოგიერთი ცუდი ამბავი. ასე რომ, კარგი ისაა, რომ CS50 იწყებს ამ პარასკევს. თუ გსურთ, რომ შემოგვიერთდნენ, უხელმძღვანელებს ჩვეულებრივი URL აქ. კარგი ამბავია, არ ლექცია ამ მომავალ ორშაბათს, 13. ოდნავ ნაკლებად კარგი ამბავია, ვიქტორინა ნულოვანი შემდეგი კვირა. უფრო დეტალურად შეიძლება იყოს ი ამ URL აქ. და მომდევნო რამდენიმე დღის განმავლობაში ჩვენ უნდა შევსების ბლანკები რაც შეეხება ოთახი , რომ ჩვენ ყველაფერს დაცულია. უკეთესი ისაა, რომ იქ შეიძლება რა თქმა უნდა, ფართო განხილვის სხდომაზე მომავალი ორშაბათს საღამოს. ადევნეთ თვალყური, რა თქმა უნდა ვებ ადგილმდებარეობა და დეტალები. სექციები, მიუხედავად იმისა, რომ ეს არის დღესასწაული, ასევე შეხვდება ასევე. ახალი ამბები, ლექცია შემდეგი პარასკევი. ასე რომ, ეს ტრადიცია ჩვენ აქვს, როგორც პოსტი სილაბუსი. Just-- ეს იქნება საოცარი. თქვენ ნახავთ, რამ, როგორიცაა მუდმივი დროს მონაცემთა სტრუქტურები და hash მაგიდები და ხეები ლელო. და ჩვენ ვსაუბრობთ დაბადების პრობლემები. მთელი bunch პერსონალის ელის მომდევნო პარასკევს. OK. ყოველ შემთხვევაში. ასე რომ გავიხსენოთ, ჩვენ აქცენტი ამ სურათს რა არის შიგნით ჩვენი კომპიუტერის მეხსიერებაში. ასე მეხსიერების ან RAM სადაც პროგრამების არსებობს ხოლო თქვენ გაშვებული მათ. თუ ორჯერ დააწკაპუნეთ icon აწარმოებს ზოგიერთი პროგრამა ან ორჯერ დააწკაპუნეთ Icon გახსნა რამოდენიმე ფაილი, ის დატვირთული თქვენს ხისტ დისკზე ან მყარი დისკის შევიდა RAM, ოპერატიული მეხსიერება, სადაც ის ცხოვრობს, სანამ ძალა მიდის off, ლეპტოპი სახურავი ხურავს, ან დატოვა პროგრამა. ახლა, მეხსიერება, საქართველოს რომელიც თქვენ ალბათ 1 გბ ამ დღეებში, 2 გიგაბაიტი, ან კიდევ უფრო, ზოგადად ასახული მოცემული პროგრამა ამ სახის მართკუთხა კონცეპტუალური მოდელი რომლითაც ჩვენ დასტის ბოლოში და bunch სხვა პერსონალი ზედა. რამ ძალიან ზევით ჩვენ ვნახეთ ამ სურათს ადრე, მაგრამ არასოდეს მითქვამს არის ე.წ. ტექსტი სეგმენტი. ტექსტი სეგმენტი არის მხოლოდ ლამაზი გზა ვამბობ zeros და პირობა, რომ შესაქმნელად თქვენი ფაქტობრივი შედგენილი პროგრამა. ასე რომ, როდესაც თქვენ ორმაგი დაწკაპუნება Microsoft Word თქვენს Mac ან PC, ან როდესაც თქვენ აწარმოებს dot slash Mario on Linux კომპიუტერზე თქვენი ტერმინალის ფანჯარა, zeros და პირობა, რომ დაკომპლექტებას სიტყვა ან Mario ინახება დროებით თქვენი კომპიუტერის RAM, რომ ე.წ. ტექსტის სეგმენტის კონკრეტული პროგრამა. ქვემოთ რომ მიდის ინიციალიზაცია და uninitialized მონაცემები. ეს არის პერსონალის როგორიცაა გლობალური ცვლადები, რომ ჩვენ არ გამოიყენება მრავალი, მაგრამ ხანდახან ჩვენ ჰქონდა გლობალური ცვლადები ან statically განსაზღვრული strings რომ არის მყარი კოდირებული სიტყვები, როგორიცაა "გამარჯობა" რომ არ გაითვალისწინებს ეხლა შესახებ რომ მყარი კოდირებული თქვენი პროგრამა. ახლა ქვევით ბოლოში ჩვენ აქვს ე.წ. დასტის. და დასტის, ჯერჯერობით, ჩვენ გამოყენებით, თუ რა სახის მიზნებისათვის? რა დასტის გამოიყენება? ჰო? აუდიტორია: ფუნქციები. დევიდ ჯ Malan: ფუნქციები? რა გაგებით ფუნქციები? აუდიტორია: როცა რეკავთ ფუნქცია, არგუმენტები გადაწერილი გადატანა დასტის. დევიდ ჯ Malan: ზუსტად. როცა რეკავთ ფუნქცია, მისი არგუმენტები გადაწერილი გადატანა დასტის. ასე რომ, ნებისმიერ X ან Y ან ან B-ს რომ თქვენ გადადის შევიდა ფუნქცია დროებით დააყენა ე.წ. დასტის, ისევე, როგორც ერთი Annenberg სასადილოს ქაღალდის, და ასევე რამ როგორიცაა ადგილობრივი ცვლადები. თუ თქვენი foo ფუნქცია ან თქვენი swap ფუნქცია აქვს ადგილობრივი ცვლადები, როგორიცაა temp, ამ ორი დასრულდება up on Stack. ახლა, ჩვენ არ გაიგო ძალიან ბევრი შესახებ მათ, მაგრამ ამ გარემოს ცვლადები ბოლოში ჩვენ ვნახეთ ცოტა ხნის წინ, როდესაც მე futzing კლავიატურის ერთ დღეს და დავიწყე წვდომის რამ როგორიცაა argv 100 ან argv 1000, უბრალოდ ელემენტები მე დაგვავიწყდეს ნომრები, მაგრამ ეს არ უნდა იქნეს ჩემთვის. ჩვენ დაიწყო ხედავს ზოგიერთი ხმაურიანი სიმბოლოები ეკრანზე. ისინი იყვნენ ე.წ. გარემოს ცვლადები ისევე გლობალური პარამეტრების ჩემი პროგრამა ან ჩემი კომპიუტერი, არ უკავშირდება ბოლო შეცდომა, რომელიც ჩვენ განვიხილეთ, Shellshock, რომ უკვე დიდად აწუხებს საკმაოდ კომპიუტერი. ახლა ბოლოს, დღევანდელ აქცენტი ჩვენ, საბოლოო ჯამში, იქნება ბევრი. ეს არის კიდევ ერთი ბლოკი მეხსიერება. და ფუნდამენტურად ეს ყველაფერი მეხსიერება არის იგივე პერსონალი. ეს იგივეა, ტექნიკა. ჩვენ უბრალოდ სახის მკურნალობის სხვადასხვა მტევანი ბაიტი სხვადასხვა მიზნით. ბევრი ასევე იქნება, სადაც ცვლადები და მეხსიერება, რომ თქვენ მოითხოვოს ოპერაციული სისტემა დროებით შენახული. მაგრამ არსებობს ასეთი პრობლემა აქ, როგორც სურათზე გულისხმობს. ჩვენ ერთგვარი აქვს ორი გემების შესახებ დაეჯახება. იმის გამო, რომ, როგორც თქვენ იყენებთ უფრო და უფრო დასტის, და როგორც დღეს ვხედავთ მოყოლებული, როგორც თქვენ გამოიყენოთ უფრო და უფრო ბევრი, აუცილებლად ცუდი რამ შეიძლება მოხდეს. და მართლაც, ჩვენ შეიძლება გამოიწვიოს, რომ ნებსით თუ უნებლიეთ. ასე რომ, cliffhanger ბოლო დრო იყო ამ პროგრამაში, რომელიც არ ემსახურება რაიმე ფუნქციური სხვა მიზნით, ვიდრე იმის დემონსტრირება, თუ როგორ, როგორც ცუდი ბიჭი შეგიძლიათ რეალურად მიიღოს უპირატესობა შეცდომებს სხვისი პროგრამა და მიიღოს პროგრამა ან თუნდაც მთელი კომპიუტერული სისტემა ან სერვერზე. ასე რომ მხოლოდ ერთი შეხედვით მოკლედ, თქვენ შეამჩნევთ, რომ ძირითად ბოლოში იღებს ბრძანების არგუმენტები, როგორც ერთ argv. და მას აქვს ზარი ფუნქცია f, არსებითად უსახელო ფუნქცია მოუწოდა f, და ის გადადის argv [1]. ასე რომ, რასაც სიტყვა მომხმარებლის ტიპების ზე სწრაფი შემდეგ ამ პროგრამის სახელი, და შემდეგ ამ თვითნებური ფუნქცია up ზედა, f, იღებს ტექსტი, AKA char *, როგორც ჩვენ დავიწყეთ, რათა განიხილონ, და ეს მხოლოდ მას უწოდებს "ბარი". მაგრამ ჩვენ შეგვიძლია ეძახით არაფერი. და შემდეგ იგი აცხადებს, შიგნით F, მასივი სიმბოლო მოუწოდა, C 12 ასეთი გმირები. ახლა, ამბავი ვეუბნებოდი მომენტში წინ, სადაც მეხსიერება გ, ან იმ 12 ჩარები აპირებს დასრულდება up? უბრალოდ უნდა იყოს წმინდა. ჰო? აუდიტორია: On Stack. დევიდ ჯ Malan: On Stack. ასე რომ გ ადგილობრივი ცვლადი. ჩვენ ითხოვს 12 chars და 12 ბაიტი. იმ ვაპირებთ დასრულდება მდე on ე.წ. დასტის. ახლა საბოლოოდ ამ სხვა ფუნქცია ეს რეალურად საკმაოდ სასარგებლო, მაგრამ ჩვენ ნამდვილად არ გამოიყენება ის საკუთარ თავს, strncopy. ეს იმას ნიშნავს, string ასლი, მაგრამ მხოლოდ ო წერილები, n სიმბოლო. ასე რომ, ო გმირები იქნება გადაწერა ბარი შევიდა გ. და რამდენი? სიგრძეზე ბარი. ასე რომ, სხვა სიტყვებით, რომ ერთი ხაზი, strncopy, აპირებს კოპირება ეფექტურად ბარი გ. ახლა, მხოლოდ სახის მოსალოდნელია მორალური ამ ამბავი, რა არის პოტენციურად პრობლემური აქ? მიუხედავად იმისა, რომ ჩვენ შემოწმების ხანგრძლივობა ბარი და ჩაბარების ის strncopy, რა არის თქვენი gut გეუბნებოდით არის კვლავ დაარღვიეს ამ პროგრამის შესახებ? ჰო? აუდიტორია: არ მოიცავს ოთახი null ხასიათი. დევიდ ჯ Malan: არ მოიცავს ოთახი null ხასიათი. პოტენციურად, განსხვავებით წარსული პრაქტიკა ჩვენ კი არა, აქვს იმდენად, როგორც პლუს 1 გადაიდგა, რომ null ხასიათი. მაგრამ კიდევ უარესი რომ. რა ჩვენ ვერ გააკეთებს? ჰო? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: Perfect. ჩვენ რთული კოდირებული 12 საკმაოდ თვითნებურად. რომ არ არის იმდენად პრობლემა, მაგრამ ის ფაქტი, რომ ჩვენ კი არ შემოწმების სიგრძეზე ბარი ნაკლებია, ვიდრე 12, ამ შემთხვევაში ეს იქნება უსაფრთხო რომ იგი ხსოვნას ე.წ. c რომ ჩვენ გამოყოფილი. მართლაც, თუ ბარი, როგორიცაა 20 სიმბოლომდე ეს ფუნქცია, როგორც ჩანს, გადაწერა 20 სიმბოლოებს ბარი შევიდა გ, რითაც აღების მინიმუმ 8 bytes რომ ეს არ უნდა იყოს. რომ გავლენა აქ. ასე მოკლედ, გატეხილი პროგრამა. არ არის ისეთი დიდი გარიგება. იქნებ თქვენ გაქვთ სეგმენტაცია ბრალია. ჩვენ გვქონდა შეცდომები პროგრამები. ალბათ ყველა აქვს შეცდომები პროგრამების ახლა. მაგრამ რა გავლენა? ისე, აქ zoomed-in მობილური ეს სურათი ჩემი კომპიუტერის მეხსიერებაში. ეს არის ბოლოში ჩემი Stack. და მართლაც, ძალიან ბოლოში არის ის, რაც მოუწოდა მშობელი რუტინული დასტის, ლამაზი გზა განაცხადა, რომ მთავარ. ასე რომ, ვინც მოუწოდა ფუნქცია f, რომ ჩვენ ვსაუბრობთ. ასე რომ, ეს ბოლოში დასტის. დაბრუნების მისამართი არის რაღაც ახალი. ის ყოველთვის არსებობს, ყოველთვის, რომ სურათი. ჩვენ უბრალოდ არ ჰქვია ამას ყურადღებას. იმიტომ, რომ ეს თურმე გზა C მუშაობს არის რომ როდესაც ერთი ფუნქცია მოუწოდებს სხვა, არა მარტო არგუმენტები, რომ ფუნქცია მივიღებთ გადატანა დასტის, არა მარტო ფუნქციის ადგილობრივი ცვლადები მივიღებთ გადატანა დასტის, რაღაც მოუწოდა დაბრუნების მისამართი ასევე იღებს გადატანა დასტის. კერძოდ, თუ მთავარ მოუწოდებს foo, ძირითად საკუთარ მეხსიერებაში, ox რაღაც, ეფექტურად იღებს დააყენა გადატანა დასტის ასე რომ, როცა f კეთდება შესრულებაში მას იცის, სად უნდა ხტომა უკან ტექსტში სეგმენტი, რათა გაგრძელდება შესრულებაში. ასე რომ, თუ ჩვენ აქ, კონცეპტუალურად, მთავარი, მაშინ f იღებს მოუწოდა. როგორ ამჯამად f იცის, ვინ მხრივ კონტროლის უკან? ისე, ეს პატარა breadcrumb წითელი აქ, მოუწოდა დაბრუნების მისამართი, ეს მხოლოდ ამოწმებს, რა არის, რომ დაბრუნების მისამართი? ოჰ, ნება მომეცით გადასვლა უკან to main აქ. და რომ ცოტა oversimplification, რადგან zeros და პირობა ძირითადი ტექნიკურად აქ ტექნიკური სეგმენტი. მაგრამ ეს იდეა. ვ უბრალოდ უნდა იცოდეს, რას სადაც კონტროლი საბოლოოდ ბრუნდება. მაგრამ გზა კომპიუტერები დიდი ხანია ასახული რამ როგორიცაა ადგილობრივი ცვლადები და არგუმენტები მოსწონს ეს. ასე რომ ზედა ამ სურათს ლურჯი არის დასტის ჩარჩო f, ასე რომ ყველა მეხსიერების რომ f კონკრეტულად გამოყენებით. ასე რომ, შესაბამისად, შეამჩნევთ, რომ ბარი ამ სურათს. ბარი იყო მისი არგუმენტი. და ჩვენ აცხადებდა, რომ არგუმენტები ფუნქციები მივიღებთ გადატანა Stack. და c, რა თქმა უნდა, ასევე ამ სურათს. და მხოლოდ notational მიზნით, შეამჩნია ზედა მარცხენა კუთხეში არის რა იქნება c bracket 0 და შემდეგ ოდნავ ქვემოთ მარჯვენა გ bracket 11. სხვა სიტყვებით, თქვენ წარმოიდგინეთ, რომ არსებობს ქსელის bytes არსებობს, პირველი არის ზედა მარცხენა, ბოლოში, რომელიც უკანასკნელი იმ 12 ბაიტი. მაგრამ ახლა ცდილობენ სწრაფად გადასახვევად. ის, რაც უნდა მოხდეს, თუ ჩვენ გაიაროს სიმებიანი ბარი, რომ უფრო მეტია, ვიდრე გ? და ჩვენ არ შესამოწმებლად, თუ ეს მართლაც უმეტეს 12. რომელი ნაწილი ამ სურათს აპირებს მიიღოს ინსტალერის ბაიტი 0, 1, 2, 3, dot dot dot, 11, და შემდეგ ცუდი, 12, 13 გზით 19? რა მოხდება აქ, თუ ითქვას, შეკვეთით რომ გ bracket 0 არის ზედა და c bracket 11 არის ერთგვარი down მარჯვნივ? ჰო? აუდიტორია: Well, ის აპირებს გადავაწერო char * ბარი. დევიდ ჯ Malan: ჰო, როგორც ჩანს, თქვენ აპირებს გადავაწერო char * ბარი. და უარესი, თუ თქვენ მართლაც ხანგრძლივი სიმებიანი, თქვენ შეიძლება გადაწერა რა? დაბრუნების მისამართზე. რაც კიდევ ერთხელ, ისევე, როგორც breadcrumb გითხრათ პროგრამა, რომელშიც დაბრუნდეს, როცა f კეთდება მიმდინარეობს მოუწოდა. ასე რომ, რა ცუდები, როგორც წესი, იმ შემთხვევაში, თუ ისინი გვხვდება პროგრამა რომ ისინი აინტერესებდა არის exploitable, buggy ისე, რომ მას შეუძლია უპირატესობა რომ bug, ზოგადად, ისინი არ ეს უფლება პირველად. ისინი უბრალოდ დაიწყოს გაგზავნის, მაგალითად, შემთხვევითი strings თქვენი პროგრამა, არა კლავიატურის, ან გულახდილად ისინი, ალბათ, წერენ პატარა პროგრამა მხოლოდ ავტომატურად წარმოქმნის strings, და დაიწყოს ბრახუნი თქვენი პროგრამის მიერ გაგზავნის უამრავი სხვადასხვა საშუალებებით სხვადასხვა lengths. როგორც კი თქვენი პროგრამის დამსხვრევაზე, რომ საოცარი რამ. რადგან ეს იმას ნიშნავს, ან მან აღმოაჩინა რა არის, ალბათ მართლაც bug. და მაშინ მათ შეუძლიათ მიიღონ უფრო ჭკვიანი და დაიწყოს ფოკუსირება უფრო ვიწროდ როგორ უნდა გამოეყენებინათ, რომ შეცდომა. კერძოდ, ის, რაც მას შეიძლება გავაკეთოთ არის გაგზავნას, საუკეთესო შემთხვევაში, hello. არ არის დიდი გარიგება. ის ტექსტი, რომელიც არის საკმაოდ მოკლე. მაგრამ რა, თუ იგი აგზავნის, და ჩვენ განზოგადება, როგორც, თავდასხმა კოდი ისე zeros და პირობა, რომ გავაკეთოთ რამ, როგორიცაა rm-rf, რომ ამოიღონ ყველაფერი დისკის და სპამის ან რაიმე შეტევა მანქანა? ასე რომ, თუ თითოეული ამ წერილები უბრალოდ წარმოადგენს, კონცეპტუალურად, თავდასხმა, თავდასხმა, ზოგიერთი ცუდი კოდი რომელიც სხვისი დაწერა, მაგრამ თუ ეს პირი არის ჭკვიანი საკმარისი არა მხოლოდ მოიცავს ყველა იმ rm-გადატანაში, არამედ აქვს მისი ბოლო რამდენიმე bytes იქნება მთელი რიგი, რომელიც შეესაბამება მისამართს მისი ან საკუთარი შეტევის კოდი რომ მას გადაეცემა მხოლოდ უზრუნველყოფს, რომ ეს ყველაზე სწრაფი, შეგიძლიათ ეფექტურად შეასრულა კომპიუტერული შევიდა დაენახა, როდესაც f კეთდება შესრულებაში, oh, დროა ჩემთვის ხტომა თავში წითელი დაბრუნების მისამართზე. არამედ იმიტომ, რომ მას არ აქვს რატომღაც გადაფარა, რომ დაბრუნების მისამართი საკუთარი ნომერი, და ისინი არიან ძალიან გონიერები არ კონფიგურაცია, რომ ნომერი ეხება, როგორც თქვენ იხილეთ სუპერ დაბრუნება მარცხენა კუთხეში არსებობს, ფაქტობრივი მისამართი კომპიუტერის მეხსიერების ზოგიერთი მათი თავდასხმა კოდი ცუდი ბიჭი შეასრულა კომპიუტერული სიკვდილით დაესაჯა თავისი კოდი. და რომ კოდი, კიდევ ერთხელ, შეიძლება ასეც იყოს. ეს ზოგადად მოუწოდა shell კოდი, რაც არის გზას ვამბობ, რომ ეს არ არის ზოგადად რაღაც იმდენად მარტივია, rm-rf. ეს რეალურად რაღაც Bash, ან ფაქტობრივი პროგრამა, რომელიც აძლევს მას ან მისი პროგრამული კონტროლის შეასრულოს არაფერი, რომ მათ სურთ. ასე მოკლედ, ეს ყველაფერი გამომდინარეობს მარტივი ფაქტი რომ ეს შეცდომა იყო არა შემოწმების საზღვრების თქვენი მასივი. და რადგან გზა კომპიუტერები მუშაობენ არის, რომ ისინი გამოყენება დასტის საწყისი ეფექტურად, კონცეპტუალურად, ბოლოში, მაგრამ შემდეგ ელემენტებს თქვენ დააყენებს გადატანა დასტის იზრდება ზემოდან ქვემოთ, ეს არის ძალიან პრობლემატურია. ახლა, არსებობს გზები, რათა მუშაობა გარშემო. და გულწრფელად ვამბობ, არსებობს ენები რომლის მუშაობა გარშემო. Java იმუნური, მაგალითად, ამ კონკრეტულ საკითხთან დაკავშირებით. იმიტომ, რომ ისინი არ მოგცემთ მითითებას. ისინი არ მოგცემთ პირდაპირი მეხსიერების მისამართები. ასე რომ, ეს ძალა, რომელიც ჩვენ გვაქვს შეეხოთ არაფერი მეხსიერება გვინდა საქმე, მართლაც, დიდი რისკი. ასე რომ, ადევნეთ თვალი გარეთ. თუ გულწრფელად რომ ვთქვათ, რამდენიმე თვის განმავლობაში, ან წლის განმავლობაში, ნებისმიერ დროს თქვენ წაიკითხოთ ზოგიერთი ექსპლუატაციის პროგრამა ან სერვერზე, თუ თქვენ ოდესმე ვხედავ მინიშნება რაღაც ისევე როგორც ბუფერული overflow თავდასხმა, ან დასტის overflow არის სხვა ტიპის თავდასხმა, მსგავსი სულისკვეთებით, ისევე როგორც შთააგონებს საიტის ასახელებს, თუ იცით, ეს ყველაფერი ლაპარაკი მხოლოდ ადიდებულმა ზომა ზოგიერთი ხასიათი მასივში ან გარკვეული მასივი ზოგადად. ნებისმიერი კითხვები, მაშინ, ამ? ნუ ეცდებით ამ სახლში. ყველა უფლება. ასე malloc დღემდე ჩვენი ახალი მეგობარს, რომ ჩვენ შეგვიძლია გამოყოს მეხსიერება რომ ჩვენ არ ვიცით, აუცილებლად in წინასწარ, რომ ჩვენ გვინდა, ამიტომ ჩვენ არ გვაქვს მძიმე კოდი ჩვენი პროგრამა ნომრები, როგორიცაა 12. მას შემდეგ, შესახებ გვეუბნება, თუ რამდენად მონაცემები მას სურს შეყვანა, ჩვენ შეგვიძლია malloc რომ ბევრი რამ მეხსიერებაში. ასე malloc ირკვევა, რომ რამდენად ჩვენ უკვე იყენებს, პირდაპირ ბოლო დროს და შემდეგ თქვენ ბიჭები არ იყენებს განთავსების GetString unknowingly for რამდენიმე კვირის განმავლობაში, ყველა malloc ხსოვნას მოდის ე.წ. ბევრი. და ამიტომ GetString, მაგალითად, შეიძლება გამოყოს მეხსიერება დინამიურად გარეშე იცის, თუ რა თქვენ ვაპირებ აკრიფოთ წინასწარ, გადმოგცეთ უკან მომცეთ, რომ მეხსიერება, და რომ მეხსიერების კვლავ თქვენი შეინახოს, მას შემდეგ, რაც GetString დააბრუნებს. იმიტომ, რომ გავიხსენოთ ამ ყველაფრის შემდეგ დასტის მუდმივად მიდის და ქვემოთ, up და down. და როგორც კი იგი მიდის down, ეს ნიშნავს, რომ ნებისმიერი მეხსიერების ეს ფუნქცია გამოიყენება, უნდა არ უნდა იქნას გამოყენებული ვინმეს. ეს ნაგვის ღირებულებებს. მაგრამ ბევრი არის აქ. და რა არის ლამაზი შესახებ malloc არის, როდესაც malloc გამოყოფს მეხსიერება აქ, ის არ იმოქმედა, რომ ყველაზე ნაწილი, Stack. და ნებისმიერი ფუნქცია შეუძლიათ მეხსიერება, რომელიც უკვე malloc'd, თუნდაც ფუნქცია, როგორიცაა GetString, მას შემდეგ, რაც იგი დაბრუნდა. ახლა, პირიქით malloc არის უფასო. და მართლაც, წესით უნდა დავიწყოთ მიღებით ნებისმიერი, ნებისმიერი, ნებისმიერ დროს თქვენ იყენებთ malloc თქვენ უნდა თავს გამოიყენოს თავისუფალი, საბოლოოდ, იმავე მაჩვენებელი. ყველა ამ დროს ჩვენ არ წერდა buggy, buggy კოდი, მრავალი მიზეზის გამო. მაგრამ ერთი, რომელიც უკვე გამოყენებით CS50 ბიბლიოთეკა, რომელიც თავად შეგნებულად buggy, იგი გაჟონვის მეხსიერება. ნებისმიერ დროს თქვენ მოუწოდა GetString უკანასკნელი რამდენიმე კვირის განმავლობაში ჩვენ გეკითხებით ოპერაციული სისტემა, Linux, მეხსიერება. და თქვენ არასდროს ერთხელ ეძლევა უკან. და ეს არ არის, პრაქტიკაში, კარგია. და Valgrind, ერთი ინსტრუმენტები გააცნო pset 4, ყველაფერი ეხმარება თქვენ ახლა შეცდომები, როგორიცაა, რომ. მაგრამ საბედნიეროდ, ამისთვის pset 4 თქვენ არ გჭირდებათ გამოიყენოს CS50 ბიბლიოთეკაში ან GetString. ასე რომ, ნებისმიერი შეცდომები დაკავშირებული მეხსიერების საბოლოოდ იქნება თქვენი საკუთარი. ასე malloc უფრო მეტია ვიდრე მოსახერხებელი ამ მიზნით. ჩვენ შეგვიძლია რეალურად ახლა გადაწყვიტოს ფუნდამენტურად განსხვავებული პრობლემები, და ფუნდამენტურად პრობლემების უფრო ეფექტურად კვირაში ნულოვანი დაპირება. ჯერჯერობით ეს არის ყველაზე სექსუალური მონაცემები სტრუქტურა ჩვენ გვქონდა. და მონაცემთა სტრუქტურის უბრალოდ ნიშნავს, გზა conceptualizing მეხსიერება ისე, რომ სცილდება უბრალოდ ამბობდა, ეს არის int, ეს არის char. ჩვენ შეგვიძლია დავიწყოთ კასეტური რამ ერთად. ამიტომ მასივი ჩანდა მოსწონს ეს. და რა იყო გასაღები შესახებ array არის ის, რომ გაძლევთ back-to-back მოცულობით მეხსიერება, რომელთაგან თითოეული იქნება იგივე ტიპის, int, int, int, int, ან char, char, char, char. მაგრამ არსებობს რამდენიმე downsides. ამ მაგალითად, მასივი ზომა ექვსი. დავუშვათ, რომ თქვენ შეავსოთ ამ მასივი ექვსი ნომრები და შემდეგ, გარკვეული მიზეზების გამო, თქვენი მომხმარებლის სურს თქვენ მეშვიდე ნომერი. სად დააყენა ეს? რა არის გამოსავალი, თუ თქვენ გაქვთ განთავსებულია მასივი დასტის, მაგალითად, მხოლოდ კვირაში ორი notation, რომ ჩვენ გააცნო, კვადრატულ ფრჩხილებში რიგ შიგნით? კარგად, თქვენ მოხვდით ექვსი ნომრები ამ ყუთები. რა თქვენი ინსტინქტები იყოს? სადაც გინდათ ამას? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: უკაცრავად? აუდიტორია: ამას ბოლომდე. დევიდ ჯ Malan: ამას ბოლომდე. ასე რომ, მხოლოდ მეტი უფლება, გარეთ ამ ყუთში. რომელიც იქნებოდა, მაგრამ ეს გამოდის, რომ თქვენ ამის გაკეთება არ შეუძლიათ, რომ. იმიტომ, რომ თუ თქვენ არ სთხოვა ამ ბლოკი მეხსიერება, ეს შეიძლება იყოს შემთხვევითი, რომ ამ რომელიც გამოიყენება რაიმე სხვა ცვლადი საერთოდ. ვფიქრობ, უკან ერთი კვირის ან ასე რომ, როდესაც ჩვენ ჩაუყარა out Zamyla და Davin და Gabe სახელები მეხსიერებაში. მათ პირდაპირი გაგებით უკან დაბრუნება თავში დაბრუნება. ასე რომ ჩვენ შეგვიძლია არ არის აუცილებელი ენდობა, რომ ყველაფერს, რაც აქ არის შესაძლებელი ჩემთვის გამოყენება. ასე რომ, რა შეიძლება გავაკეთოთ? ისე, ერთხელ ხვდებიან უნდა მასივი ზომა შვიდი, შეიძლება მხოლოდ შექმნა მასივი ზომა შვიდი შემდეგ გამოიყენოთ ამისთვის მარყუჟი ან ხოლო მარყუჟის, კოპირება ახალი მასივი, და მერე რაღაცნაირად უბრალოდ, თავი დაეღწია ამ მასივი ან უბრალოდ შეწყვიტოს გამოყენება. მაგრამ ეს არ არის განსაკუთრებით ეფექტური. მოკლედ, კოლექტორები არ მისცეს თქვენ დინამიურად პასუხის. ასე რომ, ერთი მხრივ, თქვენ მიიღებთ წვდომის, რომელიც არის საოცარი. იმიტომ, რომ ეს საშუალებას გვაძლევს გავაკეთოთ რამ, როგორიცაა გათიშე და იბატონე, ორობითი ძებნა, რაც ჩვენ ისაუბრა ეკრანზე აქ. მაგრამ თქვენ ხატავს თავის კუთხეში. როგორც კი მოხვდა ბოლოს თქვენი მასივი, თქვენ უნდა გავაკეთოთ ძალიან ძვირადღირებული ოპერაცია ან ჩაწერის მთელი bunch of კოდი ახლა საქმე, რომ პრობლემა. მერე რა, რომ ნაცვლად გვქონდა რაღაც მოუწოდა სიაში, ან დაკავშირებული სიაში, კერძოდ? რა მოხდება, თუ ნაცვლად, რომელმაც მართკუთხედების დაბრუნება უკან, ჩვენ მართკუთხედების რომ დატოვოთ პატარა ცოტა wiggle ოთახი მათ შორის? და მიუხედავად იმისა, რომ მე შედგენილი ამ სურათი ან ადაპტირებული ამ სურათს ერთი ტექსტები აქ იქნება უკან უკან დაბრუნება ძალიან მოწესრიგებული, რეალურად, ერთ იმ მართკუთხედების შეიძლება აქ მეხსიერებაში. ერთი მათგანი შეიძლება იყოს აქ. ერთი მათგანი შეიძლება იყოს აქ, აქ და სხვ. მაგრამ რა, თუ ჩვენ მიიპყრო, ამ შემთხვევაში, ისრები რომ როგორმე დაუკავშირონ ეს მართკუთხედების ერთად? მართლაც, ჩვენ ვხედავთ, ტექნიკური განსახიერება ისარი. რა გვაქვს გამოიყენება უკანასკნელ დღის განმავლობაში, რომ, ქვევმოთ hood, წარმომადგენელი arrow? მაჩვენებელი, არა? მერე რა, რომ ნაცვლად მხოლოდ შენახვის ნომრები, როგორიცაა 9, 17, 22, 26, 34, თუ ჩვენ ინახება არა მხოლოდ რამდენიმე, მაგრამ მაჩვენებელი შემდეგი თითოეული ასეთი ნომერი? ასე, რომ ბევრი რამ, როგორც თქვენ თემა ნემსის მეშვეობით მთელი bunch of ქსოვილზე, რატომღაც გამათანაბრებელი რამ ერთად, ასევე შეგიძლიათ ჩვენ ერთად პოინტერები, როგორც incarnated მიერ ისრებით აქ, სახის ერთმანეთთან აკავშირებს, ეს ინდივიდუალური მართკუთხედების მიერ ეფექტურად გამოყენების მაჩვენებელი შემდეგი თითოეული ნომერი, რომელიც , გარკვეული შემდეგი ნომერი, რომელიც მიუთითებს, თავის მხრივ, გარკვეული შემდეგი ნომერი? ასე რომ, სხვა სიტყვებით რომ ვთქვათ, თუ ჩვენ რეალურად სურდა განახორციელოს მსგავსი რამ? ასევე, სამწუხაროდ, ამ მართკუთხედების, მინიმუმ ერთი 9, 17, 22, და ა.შ., ეს აღარ არის ლამაზი სკვერების ერთი ნომრები. ბოლოში, მართკუთხედი ქვემოთ 9, მაგალითად, წარმოადგენს რა უნდა კურსორი, 32 ბიტი. ახლა, მე ჯერ კიდევ არ იცის ნებისმიერი ტიპის მონაცემის C რომ გაძლევთ არა მხოლოდ int მაგრამ მაჩვენებელი საერთოდ. ასე რომ, რა არის გამოსავალი, თუ გვინდა, გამოგონება ჩვენი საკუთარი პასუხი ამ? ჰო? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: რა არის ეს? აუდიტორია: New სტრუქტურა. დევიდ ჯ Malan: ჰო, რატომ არ უნდა შეიქმნას ახალი სტრუქტურა, ან C, struct? ჩვენ ვნახეთ structs ადრე, თუ მოკლედ, სადაც ჩვენ გვქონდა სტუდენტი სტრუქტურა მოსწონს ეს, რომელმაც სახელი და სახლი. In pset 3 ბრეაკოუტ გამოყენებულია მთელი bunch of structs-- GRect და GOvals რომ სტენფორდის შექმნა, რათა კასეტური ერთად. მერე რა, რომ ჩვენ ეს იგივე იდეა საკვანძო სიტყვები "typedef" და "struct," და შემდეგ რამდენიმე სტუდენტმა კონკრეტული პერსონალის, და განვითარება ამ შევიდა შემდეგი: typedef struct კვანძის და კვანძის უბრალოდ ძალიან generic კომპიუტერულ მეცნიერებათა ტერმინი რაღაც მონაცემები სტრუქტურა, კონტეინერის მონაცემები სტრუქტურა. კვანძი მე პრეტენზია ექნება int n, სრულიად მარტივია, და შემდეგ ცოტა მეტი cryptically, ეს მეორე ხაზი, struct კვანძის * შემდეგი. მაგრამ ნაკლებად ტექნიკურ ტერმინებში, რა არის, რომ მეორე ხაზი კოდი შიგნით Curly braces? ჰო? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: მაჩვენებელი სხვა კვანძის. ასე რომ, მართლაც, სინტაქსი ცოტა cryptic. მაგრამ თუ თქვენ ეს ფაქტიურად, შემდეგი არის სახელი ცვლადი. რა არის მისი მონაცემები ტიპის? ეს პატარა verbose ამ დროს, მაგრამ ეს ტიპის struct კვანძის *. ნებისმიერ დროს, ჩვენ ვხედავთ, რომ რაღაც ვარსკვლავი, რომ ეს იმას ნიშნავს რომ მომცეთ, რომ მონაცემები ტიპის. ასე რომ, მომავალი, როგორც ჩანს, მომცეთ struct კვანძში. ახლა, რა არის struct კვანძის? ყურადღება მიაქციეთ, ხედავთ იმ იგივე სიტყვები, ზედა მარჯვენა. და მართლაც, თქვენ აგრეთვე სიტყვა "კვანძის" ქვემოთ აქ ბოლოში მარცხენა. და ეს არის რეალურად მხოლოდ მოხერხებულობისთვის. გაითვალისწინეთ, რომ ჩვენი სტუდენტური განმარტება არსებობს სიტყვა "სტუდენტი" მხოლოდ ერთხელ. და ეს იმიტომ, სტუდენტი ობიექტი არ იყო თვითმმართველობის რეფერენტული. არაფერია შიგნით სტუდენტი რომ სჭირდება აღვნიშნო, რომ ერთი სტუდენტი, persay. რომ იქნება ერთგვარი უცნაური რეალურ სამყაროში. მაგრამ კვანძი უკავშირდება სია, ჩვენ გვინდა კვანძის უნდა იყოს რეფერენტული მსგავსი ობიექტი. და ასე შეამჩნია ცვლილება აქ არ არის უბრალოდ, რა არის შიგნით Curly braces. მაგრამ ჩვენ სიტყვა "კვანძის" ზედა ასევე და დასძინა, რომ ბოლოში ნაცვლად "სტუდენტი". და ეს არის მხოლოდ ტექნიკური დეტალია ასე რომ, კიდევ ერთხელ, თქვენი მონაცემები სტრუქტურა შეიძლება თვითმმართველობის რეფერენტული, ისე, რომ კვანძის შეიძლება აღვნიშნო, რომ ერთი ასეთი კვანძის. რა არის ეს, საბოლოო ჯამში, აპირებს ნიშნავს ეს ჩვენთვის? ასევე, ერთი, ეს პერსონალის შიგნით არის შინაარსი ჩვენი კვანძში. ეს რამ აქ, მარჯვენა ზედა, მხოლოდ ისე, , კიდევ ერთხელ, ჩვენ შეგვიძლია ეხება საკუთარ თავს. და შემდეგ outermost პერსონალი, მიუხედავად იმისა, რომ კვანძის არის ახალი ტერმინი, ალბათ, მაინც იგივე როგორც სტუდენტი და რა იყო ქვევმოთ hood in SPL. ასე რომ, თუ ჩვენ ახლა უნდოდა ახორციელებს ამ დაკავშირებული სიაში, როგორ შეიძლება ჩვენ ვთარგმნით მსგავსი რამ კოდექსში? კარგად, მოდით უბრალოდ ვხედავ მაგალითად პროგრამა, რომელიც რეალურად იყენებს უკავშირდება სიაში. შორის დღევანდელი განაწილების კოდი არის პროგრამის მოუწოდა სია Zero. და თუ მე აწარმოებს ამ იქმნება super მარტივი GUI, გრაფიკული ინტერფეისი, მაგრამ ეს მართლაც მხოლოდ printf. და ახლა მე, თავს რამდენიმე მენიუ options-- წაშლა, ჩასმა, ძიება, და Traverse. და დატოვეს. ეს არის მხოლოდ საერთო ოპერაციების მონაცემები სტრუქტურა ცნობილია, როგორც ლინკი სიაში. ახლა, წაშლა აპირებს წაშალოთ ნომერი სიიდან. Insert აპირებს დაამატოთ რიგი სიაში. ძებნა აპირებს გამოიყურებოდეს რიგი სიაში. და გვერდის ავლით არის მხოლოდ ლამაზი გზა ამბობდა, გავლა სია, ბეჭდვა ეს, მაგრამ ეს არის ის. არ შეცვლის არანაირად. მოდით ცდილობენ ამ. მოდით წავიდეთ წინ და ტიპის 2. და შემდეგ მე ვაპირებ ჩადეთ ნომერი, ვთქვათ, 9. შევა. და ახლა ჩემი პროგრამა უბრალოდ დაპროგრამებული თქმა უნდა, სიაში არის 9. ახლა, თუ წავიდეთ წინ და არ ჩადეთ კიდევ ერთხელ, მოდით მომეცით წავიდეთ წინ და დააშორებს და ჩაწერეთ 17. ახლა ჩემს სიაში არის 9, მაშინ 17. თუ ამის გაკეთება ჩასმა ერთხელ, მოდით გამოტოვოთ ერთი. იმის ნაცვლად, რომ 22, თითო სურათს ჩვენ უკვე ეძებს აქ, ნება მომეცით გადასვლა წინ და ჩადეთ 26 შემდეგი. ამიტომ, მე ვაპირებ აკრიფოთ 26. სიაში არის როგორც ველოდები. მაგრამ ახლა, უბრალოდ, თუ ამ კოდექსით იქნება მოქნილი, ნება მომეცით, ახლა ტიპი 22, რომელიც, სულ მცირე, კონცეპტუალურად, თუ ჩვენ შენახვა ეს დახარისხებული, რაც მართლაც იქნება კიდევ ერთი მიზანი სწორედ ახლა, უნდა წავიდეს შორის 17 და 26. ასე რომ, მე დააჭიროთ. მართლაც, რომ მუშაობს. და ახლა ნება მომეცით ჩადეთ და ბოლოს, ერთ სურათზე, 34. ყველა უფლება. ასე რომ, ახლა ნება მომეცით ითვალისწინებს, რომ წაშლა და Traverse და ძიება ამის გაკეთება, ფაქტობრივად, მუშაობა. ფაქტობრივად, თუ მე აწარმოებს ძებნა, მოდით მოძებნოთ ნომერი 22, შეიყვანეთ. გაირკვა, 22. ასე რომ, სწორედ ამ პროგრამის მიხედვით Zero აკეთებს. მაგრამ რა არის რეალურად აპირებს on, რომელიც ახორციელებს ამ? პირველ რიგში, მე შეიძლება, და მართლაც მე არ, ფაილი სახელად list0.h. და სადღაც არსებობს ამ ხაზი, typedef, struct კვანძის, მაშინ მე მაქვს ჩემი Curly braces, int n, და მაშინ struct-- რა განმარტება იყო? Struct კვანძის შემდეგი. ასე რომ, ჩვენ უნდა ვარსკვლავი. ახლა ტექნიკურად ჩვენ შეღწევას ჩვევა გრაფიკა აქ. თქვენ შეიძლება ნახოთ სახელმძღვანელოები და ონლაინ ცნობას ამის გაკეთება არის. ეს ფუნქციურად ექვივალენტური. ფაქტობრივად, ეს არის უფრო დამახასიათებელი. მაგრამ მე ვიქნები შეესაბამება იმას, რასაც ჩვენ ბოლო დროს, და ამის გაკეთება. და მერე ბოლოს, მე ვაპირებ ამის გაკეთება. ასე რომ header ფაილი სადღაც, list0.h დღეს არის ამ struct განმარტება, და იქნებ რაიმე სხვა პერსონალი. ამასობაში list0c არსებობს იქნება რამდენიმე რამ. მაგრამ ჩვენ ვაპირებთ დაიწყოს და არ დასრულდება ეს. List0.h ფაილი მინდა მოიცავს ჩემს C ფაილი. და მერე რაღაც მომენტში მე ვაპირებთ აქვს int, მთავარი, ბათილად. და შემდეგ მე ვაპირებ აქვს გარკვეული დავალებების აქ. მე ასევე აპირებს პროტოტიპი, როგორც ბათილად, ძიების, int, n, რომლის მიზანი ცხოვრებაში არის მოძიება ელემენტს. და შემდეგ ქვევით აქ I აცხადებენ, დღევანდელ კოდი, ბათილად, ძიების, int, N, არ მძიმით, მაგრამ ღია Curly braces. და ახლა მინდა, რომ როგორმე ძიება ელემენტის ამ სიაში. მაგრამ ჩვენ არ გვაქვს საკმარისი ინფორმაცია ეკრანზე ამჟამად. მე არ რეალურად წარმოდგენილია სიაში თავად. ასე რომ ერთი გზა ჩვენ შეგვიძლია განვახორციელოთ უკავშირდება სიაში პროგრამა არის მე ასეთი მინდა, რომ რამე ისევე როგორც აცხადებენ უკავშირდება სია აქ. სიმარტივის, მე ვაპირებ, რათა ამ გლობალურ, მიუხედავად იმისა, რომ ზოგადად, ჩვენ არ უნდა გავაკეთოთ ეს ძალიან ბევრი. მაგრამ ეს გაამარტივებს ამ მაგალითს. ასე რომ, მინდა განვაცხადო, უკავშირდება სიაში აქ. ახლა, როგორ შეიძლება ამის გაკეთება? აი სურათს უკავშირდება სიაში. და მე ნამდვილად არ ვიცი იმ მომენტში როგორ მე ვაპირებ წასვლა შესახებ წარმოადგენს ამდენი რამ მხოლოდ ერთი ცვლადი მეხსიერებაში. მაგრამ ვფიქრობ, უკან ერთი წუთით. მთელი ამ ხნის განმავლობაში ჩვენ გვქონდა სტრიქონები, რომელიც ჩვენ მაშინ გამოვლენილი იქნება კოლექტორები პერსონაჟი, რომელიც ჩვენ მაშინ გამოვლინდა, რომ მხოლოდ კურსორი პირველი ხასიათი მასივი გმირები რომ null წყდება. ასე რომ, ლოგიკა, და ამ სურათი სახის სათესლე თქვენი აზრები, რა საჭიროა ჩვენ რეალურად წერენ ჩვენს კოდი წარმოადგენს უკავშირდება სიაში? რამდენად ეს ინფორმაცია გვჭირდება ხელში C კოდი, იტყვით? ჰო? აუდიტორია: ჩვენ უნდა მომცეთ კვანძში. დევიდ ჯ Malan: A მომცეთ კვანძის. კერძოდ, რომელიც კვანძის რომ თქვენი ინსტინქტები იყოს შენარჩუნება მომცეთ? აუდიტორია: პირველი კვანძი. დევიდ ჯ Malan: ჰო, ალბათ მხოლოდ პირველი. და შენიშნავს, პირველი კვანძი სხვადასხვა ფორმის. ეს მხოლოდ ნახევარი ზომა struct, იმიტომ, რომ ეს მართლაც მხოლოდ კურსორი. რა შეგიძლიათ მართლაც არ არის განაცხადოს, უკავშირდება სიაში იყოს ტიპის კვანძის *. და მოდით ეძახით პირველი და ინიციალიზაცია იგი null. ასე რომ, null, კიდევ ერთხელ მოდის იმ სურათს აქ. არა მხოლოდ null გამოიყენება, როგორც, როგორც სპეციალური დაბრუნების ღირებულება რამ, როგორიცაა GetString და malloc, null, ასევე ნულოვანი მაჩვენებელი, ნაკლებობა მაჩვენებელი, თუ გნებავთ. ეს უბრალოდ ნიშნავს, არაფერი არ აქ. ახლა პირველად, მე ვერ მოვისმინეთ უწოდა არაფერი. მე შეეძლო მას "სია" ან ნებისმიერი რაოდენობის სხვა რამ. მაგრამ მე ამას "პირველი", ისე, რომ ეს ხაზები ამ სურათს. ასე რომ, როგორც სიმებიანი გამოისახება მისამართს პირველი byte, ასე რომ შეგიძლიათ უკავშირდება სიაში. და ჩვენ ვხედავთ, სხვა მონაცემები სტრუქტურები, წარმოდგენილი იყოს მხოლოდ ერთი მაჩვენებელი, 32-bit arrow, მიუთითებს პირველივე კვანძის სტრუქტურა. მაგრამ ახლა მოდით მოსალოდნელია პრობლემა. თუ მე მხოლოდ დამახსოვრების ჩემი პროგრამა მისამართი პირველი კვანძი, პირველი ოთხკუთხედი ამ მონაცემების სტრუქტურას, რა ჰქონდა უკეთესი იქნება საქმე, განხორციელების დანარჩენი ჩემს სიაში? რა არის მთავარი დეტალი, რომელიც აპირებს იმისათვის, რათა ეს რეალურად მუშაობს? და "რეალურად მუშაობს" მე ნიშნავს, ისევე როგორც სიმებიანი, მოდით წავიდეთ პირველი ხასიათი in Davin სახელზე მეორე, მესამე, იმ მეოთხე, ბოლომდე, ვიცით, როდესაც ჩვენ ბოლოს უკავშირდება სია, რომელიც ასე გამოიყურება? მაშინ, როდესაც ეს null. და მე სწორედ ამ სახის როგორც როგორიცაა ელექტრო ინჟინერი ძალა, პატარა დამიწების სიმბოლო, სახის. მაგრამ ეს მხოლოდ იმას ნიშნავს, null ამ შემთხვევაში. თქვენ შეგიძლიათ დახაზოთ იგი ნებისმიერი რაოდენობის გზები, მაგრამ ამ ავტორის მოხდა გამოიყენოს ეს სიმბოლო აქ. ასე რომ, სანამ ჩვენ კაბელის ყველა ამ კვანძების ერთად, მხოლოდ დამახსოვრების, სადაც პირველი არის ის, ცოტა ხნის როგორც ჩვენ დააყენა სპეციალური სიმბოლო ძალიან ბოლო კვანძის სიაში, და ჩვენ ვიყენებთ null, იმიტომ, რომ ის, რაც ჩვენ გვაქვს ჩვენს ხელთ არსებული, ამ სიაში არის სრული. და მაშინაც კი, თუ მე მხოლოდ მოგცემთ მომცეთ პირველ ელემენტს, თქვენ, პროგრამისტი, რა თქმა უნდა, შეამოწმონ დანარჩენი მას. მაგრამ მოდით მოდით, რომ თქვენი გონება wander ცოტა, თუ ისინი არ უკვე საკმაოდ wandered-- რა არის იქნება გაშვებული დრო მოძიებაში არაფერი ამ სიაში? Damn it, ეს დიდი O of n, რაც ცუდი არ არის, რომ სამართლიანობა. მაგრამ ეს არის სწორხაზოვანი. ჩვენ უარი რა ფუნქცია მასივები მოძრავი მეტი მიმართ ამ სურათს დინამიურად ნაქსოვი ერთად ან დაკავშირებულია კვანძების? ჩვენ მოცემული შემთხვევითი წვდომის. მასივი არის ლამაზი, რადგან მათემატიკურად ყველაფერი უკან დაბრუნება თავში დაბრუნება. მიუხედავად იმისა, რომ ამ სურათს გამოიყურება საკმაოდ, და კიდევ იმისა, რომ ჰგავს ეს კვანძების ლამაზად Spaced გარდა, რეალურად ისინი შეიძლება იყოს სადმე. OX1, Ox50, Ox123, Ox99, ამ კვანძების შეიძლება იყოს სადმე. იმის გამო, რომ malloc არ გამოყოს მეხსიერება საწყისი ბევრი, მაგრამ სადმე ბევრი. აუცილებელი არ არის, ვიცით, რომ ეს იქნება თავში დაბრუნება თავში დაბრუნება. და ასე ამ სურათის რეალობაში არ იქნება საკმაოდ საკმაოდ. ასე რომ, ის აპირებს ცოტა მუშაობა განახორციელოს ამ ფუნქციას. მოდით განახორციელოს ძიების არის. და ვნახავთ, როგორი ჭკვიანი გზა ამით. ასე რომ, თუ მე ვარ ძებნის ფუნქცია და მე მოცემული ცვლადი, რიცხვი n უნდა ვეძებოთ, მე უნდა იცოდეს ახალი სინტაქსი ეძებს შიგნით სტრუქტურა, რომელიც არის მიუთითა, რათა იპოვოს n. ასე რომ, მოდით ეს. ასე რომ, პირველ რიგში, მე ვაპირებ წავიდეთ წინ და აცხადებენ კვანძის *. და მე ვაპირებ მოვუწოდო მას მაჩვენებელი, მხოლოდ კონვენციას. და მე ვაპირებ ინიციალიზაცია მას პირველი. და ახლა მე შემიძლია ამის გაკეთება რიგ გზები. მაგრამ მე ვაპირებ მიიღოს საერთო მიდგომა. მიუხედავად იმისა, რომ მაჩვენებელი არ არის ტოლი, null, და ეს მოქმედებს სინტაქსი. და ეს მხოლოდ იმას ნიშნავს, ამის შემდეგ, ასე რომ სანამ თქვენ არ მიუთითებს არაფერი. რა მინდა ამის გაკეთება? თუ მაჩვენებელი dot n, ნება მომეცით მოდის უკან რომ, შეადგენს შეადგენს რა? რა ღირებულება მე ეძებს? ფაქტობრივი n მიღებულ იქნა. ასე რომ, აქ არის კიდევ ერთი ფუნქცია C და მრავალ ენაზე. მიუხედავად იმისა, რომ სტრუქტურა მოუწოდა კვანძის აქვს მნიშვნელობა n, სრულიად ლეგიტიმური ასევე აქვს ადგილობრივი არგუმენტი ან ცვლადში n. იმიტომ, რომ თუნდაც ჩვენ კი, ადამიანის თვალში, შეიძლება გამოიყოს რომ ეს n სავარაუდოდ განსხვავდება ამ n. იმის გამო, რომ სინტაქსი არის სხვადასხვა. თქვენ მოხვდით dot და მაჩვენებელი, იმის გამო, რომ ამ ერთი არსებობს ასეთი რამ. ასე რომ, ეს არის OK. რომ კარგადაა მოვუწოდებთ მათ, რომ იგივე რამ. თუ მე ეს არ ვარ, აპირებს მინდა, რომ რამე როგორიცაა განვაცხადო, რომ ჩვენ ი n. და ჩვენ დავტოვებთ, როგორც კომენტარის ან pseudocode კოდი. სხვაგან, და აქ არის საინტერესო ნაწილი, რა არ მინდა ამის გაკეთება, თუ მიმდინარე კვანძის არ შეიცავს ო, რომ აღელვებს? როგორ შემიძლია მიღწევის შემდეგ? თუ ჩემი თითი მომენტი, არის PTR, და ეს მიუთითებს, რასაც პირველი მიუთითებს, როგორ გადავინაცვლოთ my finger შემდეგი კვანძის კოდი? ისე, რა breadcrumb ჩვენ აპირებს დაიცვას ამ შემთხვევაში? აუდიტორია: [INAUDIBLE]. დევიდ ჯ Malan: ჰო, ასე შემდეგ. ასე რომ, თუ მე დაბრუნდეს ჩემი კოდი აქ, მართლაც, მე ვაპირებ წავიდეთ წინ და აცხადებენ, მაჩვენებელი, რომელიც არის მხოლოდ დროებითი ცვლადი ეს უცნაური სახელი, ptr, მაგრამ ის ისევე temp-- მე ვაპირებ მითითებული მაჩვენებელი უდრის რასაც მაჩვენებელი is-- და ისევ, ეს იქნება ცოტა buggy for მომენტში dot შემდეგ. სხვა სიტყვებით, მე ვაპირებ, რომ ჩემი finger რომ მიუთითებს ამ კვანძში და მე ვაპირებ ვთქვა, თქვენ იცით, რა, შევხედოთ მომდევნო სფეროში და გადაადგილება თითის რასაც ის მიუთითებს. და ამ აპირებს ვიმეორებ, ვიმეორებ, ვიმეორებ. მაგრამ როდის my finger შეწყვიტოს აკეთებს არაფერს? როგორც კი რა ხაზი კოდი ჩათვლით წელს? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: თუ წერტილი, ხოლო მაჩვენებელი არ არის ტოლი null. რაღაც მომენტში ჩემი თითი იქნება მიუთითებს null და მე ვაპირებ უნდა გააცნობიეროს ეს ბოლომდე ამ სიაში. ახლა, ეს არის პატარა თეთრი ტყუილი სიმარტივის. გამოდის, რომ მიუხედავად იმისა, რომ გავიგე, ამ dot ნოტაცია სტრუქტურები, მაჩვენებელი არ არის struct. ptr რა? უბრალოდ უნდა იყოს უფრო nitpicky. ეს მაჩვენებელი კვანძის. ეს არ არის კვანძის თავად. თუ არ მქონდა ვარსკვლავი აქ, მაჩვენებელი absolutely-- ეს კვანძი. ეს არის, როგორც კვირას დეკლარაცია ცვლადი, მიუხედავად იმისა, რომ სიტყვა "კვანძის" არის ახალი. მაგრამ როგორც კი ჩვენ გააცნობს ვარსკვლავი, ეს არის მომცეთ კვანძში. და სამწუხაროდ, თქვენ არ შეგიძლიათ გამოიყენოთ dot ნოტაცია მაჩვენებელი. თქვენ უნდა გამოვიყენოთ arrow ნოტაცია, რომელიც, საოცრად, არის პირველი შემთხვევა, ნებისმიერი ნაჭერი სინტაქსი გამოიყურება ინტუიციური. ეს სიტყვა ჰგავს arrow. და ისე, რომ კარგია. და ქვემოთ აქ ფაქტიურად ჰგავს arrow. ასე რომ, მე ვფიქრობ, რომ ის la-- მე არ ვფიქრობ მე ზედმეტად ჩადენილი აქ მე ვფიქრობ, რომ ბოლო ახალი ნაჭერი სინტაქსი ჩვენ ვაპირებთ ვხედავ. და საბედნიეროდ, ეს მართლაც უფრო ინტუიტიური. ახლა, იმ თქვენ, რომლებიც ალბათ ურჩევნია ძველი გზა, თქვენ შეგიძლიათ კვლავ გამოიყენოთ dot ნოტაცია. მაგრამ როგორც პოსტი ორშაბათს საუბრის პირველი უნდა წავიდეთ იქ, წასვლა, რომ მიმართოს და შემდეგ მიმართონ სფეროში. ასე რომ, ეს სწორია. და გულწრფელად ვამბობ, რომ ეს არის ცოტა მეტი pedantic. თქვენ ფაქტიურად განაცხადა, რომ dereference მაჩვენებელი და იქ. შემდეგ აითვისებდა .n, სფეროში მოუწოდა n. მაგრამ გულწრფელად ვამბობ, არავის არ სურს აკრიფოთ ან წაიკითხა ეს. და ასე, რომ მსოფლიო გამოგონილი arrow ნოტაცია, რომელიც უდრის, იდენტური, ეს მხოლოდ სინტაქსური შაქარი. ასე ლამაზი გზა ამბობდა ამ უკეთესია, ან გამოიყურება მარტივი. ასე რომ, ახლა მე ვაპირებ, რომ ერთი რამ. მე ვაპირებ ვთქვა, "შესვენების" ერთხელ მე აღმოჩნდა, რომ ეს ასე რომ არ შეინახოს ეძებს მას. მაგრამ ეს არის არსი საძიებო ფუნქცია. მაგრამ ეს არის ბევრი ადვილია, და ბოლოს, არ გავლა კოდი. ეს მართლაც ფორმალური განხორციელება ძებნა დღევანდელ განაწილების კოდი. მე ვერ გაბედავს ამბობენ, რომ ჩანართით არ არის განსაკუთრებით fun ფეხით გაიარა ვიზუალურად, არც წაშლა, მაშინაც კი, თუმცა იმ დღის ბოლოს, ისინი მოვხარშოთ ქვემოთ საკმაოდ მარტივი heuristics. ასე რომ, მოდით ეს. თუ თქვენ იუმორი ჩემთვის აქ, მე რათა bunch of სტრესი ბურთები. მოუტანა bunch of ნომრები. და შესაძლოა მივიღებთ რამდენიმე მოხალისეები წარმოადგენს 9, 17, 20, 22, 29, 34? ასე რომ, არსებითად, ყველას ვინ არის დღეს აქ. რომ იყო ერთი, ორი, სამი, ოთხი, ხუთი, ექვსი ადამიანი. და მე უკვე ვთხოვე წასვლა ვხედავთ, ერთი უკან ბადებს ხელში. OK, ერთი, ორი, სამი, ოთხი, ხუთ მიადევნე თვალი ჩატვირთვა balance-- ექვსი. OK, თქვენ ექვსი მოდის up. ჩვენ გვჭირდება სხვა ადამიანები. ჩვენ მოუტანა დამატებითი სტრესი ბურთები. და თუ შეიძლება, რაღაც მომენტში, ხაზი საკუთარი თავი, ისევე, როგორიცაა ამ სურათს აქ. ყველა უფლება. ვნახოთ, რა გქვია? აუდიტორია: Andrew. დევიდ ჯ Malan: Andrew, თქვენ ხართ ნომერი 9. კარგია თქვენთან შეხვედრა. აქ თქვენ. აუდიტორია: Jen. დევიდ ჯ Malan: Jen. დავით. ნომერი 17. დიახ? აუდიტორია: მე Julia. დევიდ ჯ Malan: Julia, დავით. ნომერი 20. აუდიტორია: ქრისტიანი. დევიდ ჯ Malan: Christian, დავით. ნომერი 22. და? აუდიტორია: JP. დევიდ ჯ Malan: JP. 29. ასე რომ, წავიდეთ წინ და მიიღოს in-- Uh oh. Uh oh. ლოდინის. 20. ვინმეს აქვს მარკერი? აუდიტორია: მე მაქვს Sharpie. დევიდ ჯ Malan: შენ Sharpie? OK. და ვინმეს აქვს ნაჭერი ქაღალდი? გადარჩენა ლექცია. მოდის. აუდიტორია: ჩვენ მივიღეთ ეს. დევიდ ჯ Malan: ჩვენ მივიღეთ ის? ყველა უფლება, მადლობა. აქ ჩვენ მივდივართ. იყო ეს თქვენ? თქვენ უბრალოდ გადაარჩინა დღეში. ასე რომ, 29. ყველა უფლება. მე misspelled 29, მაგრამ OK. წავიდეთ წინ. ყველა უფლება, მე გაძლევთ თქვენი კალამი უკან მომენტალურად. ამიტომ, ჩვენ უნდა ეგ აქ. მოდით ერთი სხვა. Gabe, არ გსურთ, რომ ითამაშოს პირველ ელემენტს აქ? ჩვენ გვჭირდება თქვენ აღვნიშნო ამ შესანიშნავი ადამიანი. ასე რომ, 9, 17, 20, 22, ერთგვარი 29 და შემდეგ 34. ჩვენ არ დაკარგავს ვინმე? მე მაქვს 34. სადაც did-- OK, რომელსაც სურს იყოს 34? OK, მოდის up, 34. ყველა უფლება, ეს იქნება კარგად ღირს მეტისმეტი იყო. რა გქვია? აუდიტორია: პეტრე. დევიდ ჯ Malan: პეტრე, მოდის up. ყველა უფლება, ასე რომ, აქ არის მთელი bunch of კვანძების. თითოეული თქვენგანი წარმოადგენს ერთი ამ ოთხკუთხედს. და Gabe, ოდნავ უცნაური კაცი, წარმოადგენს პირველი. ასე რომ, მისი მაჩვენებელი არის პატარა ეკრანზე, ვიდრე ყველას. და ამ შემთხვევაში, თითოეული თქვენი მარცხენა ხელში აპირებს ან აღვნიშნო ქვემოთ, ამით წარმოადგენს null, ამიტომ მხოლოდ არარსებობის მაჩვენებელი, ან ეს იქნება მიუთითებს კვანძში შემდეგი თქვენ. ასე რომ, ახლა თუ adorn საკუთარი თავი, როგორც სურათზეა აქ, წავიდეთ წინ და წერტილი ერთმანეთს, ერთად Gabe კერძოდ მიუთითებს ნომერი 9 წარმოადგენს სიაში. OK და ნომერი 34, თქვენი მარცხენა ხელის უბრალოდ უნდა მიუთითებს სართული. OK, ასე რომ, ეს უკავშირდება სიაში. ასე რომ, ეს არის სცენარი კითხვა. და მართლაც, ეს არის წარმომადგენლობითი კლასი პრობლემები რომ თქვენ შეიძლება ცდილობენ მოგვარებას კოდი. გსურთ საბოლოოდ ჩადეთ ახალ ელემენტს სიაში. ამ შემთხვევაში, ჩვენ ვაპირებთ ცდილობენ ჩასმა ნომერი 55. მაგრამ იქ უნდა იყოს სხვადასხვა შემთხვევებში განიხილავს. და მართლაც, ეს იქნება ერთი საქართველოს დიდი სურათი takeaways აქ, არის, რა არის სხვადასხვა შემთხვევებში. რა არის სხვადასხვა პირობები და ფილიალები, რომ თქვენი პროგრამა შეიძლება ჰქონდეს? კარგად, თქვენ ცდილობთ კულტურა, რომელიც ჩვენ ვიცით, ახლა 55, მაგრამ თუ თქვენ არ იცით, წინასწარ კი, ვფიქრობ იყოფა მინიმუმ სამი შესაძლო სიტუაციაში. სად შეიძლება ახალი ელემენტი უნდა იყოს? აუდიტორია: და ბოლოს ან შუა. დევიდ ჯ Malan: ბოლოს კი, შუა, ან დასაწყისში. ასე, რომ აცხადებენ, არსებობს მინიმუმ სამი პრობლემა უნდა მოგვარდეს. მოდით აირჩიოს, რა, ალბათ, ალბათ უმარტივესი ერთი, სადაც ახალი ელემენტი ეკუთვნის დასაწყისში. ამიტომ, მე ვაპირებ, რომ აქვს კოდი, საკმაოდ როგორიცაა ძებნა, რომელიც მე დავწერე. და მე ვაპირებ აქვს ptr, რომელიც მე წარმოვადგენ ჩემი თითი, როგორც ყოველთვის. და მახსოვს, რა ღირებულება ჩვენ არ ვრთავ ptr to? ასე რომ, ჩვენ ინიციალიზაცია null თავდაპირველად. მაგრამ მაშინ რა ვქნათ, როდესაც ჩვენ შიგნით ჩვენი ძებნის ფუნქცია? ჩვენ ვაყენებთ მას ტოლი პირველი, რაც არ ნიშნავს, ამით. თუ მე მითითებული ptr ტოლია პირველი, რასაც უნდა ჩემი მხრივ ნამდვილად იქნება მიუთითებს? უფლება. ასე რომ, თუ Gabe და მე ვაპირებთ თანაბარი უნდა იყოს ღირებულებების აქ, ჩვენ უნდა ორივე პუნქტი, ნომერი 9. ასე რომ, ეს იყო დასაწყისში ჩვენი ამბავი. და ახლა ეს მხოლოდ პირდაპირი, მიუხედავად იმისა, რომ სინტაქსი არის ახალი. კონცეპტუალურად, ეს უბრალოდ, ხაზოვანი ძებნა. 55 უდრის 9? უფრო სწორად, ასე ვთქვათ, ნაკლები 9. იმიტომ, რომ მე ვცდილობ გაერკვნენ, სადაც დააყენოს 55. ნაკლებია, ვიდრე 9, არანაკლებ 17, ნაკლები მეტი 20, ნაკლები 22, ნაკლები 29, ნაკლებია, ვიდრე 34, არ. ასე რომ, ახლა ჩვენ საქმე ერთი მინიმუმ სამი. თუ მინდა ჩადეთ 55 ზე მეტი აქ, რა ხაზი კოდი უნდა მიიღონ შესრულებული? როგორ ამჯამად ამ სურათს ადამიანები უნდა შეიცვალოს? რა გავაკეთო ჩემი მარცხენა ხელი? ეს უნდა იყოს null, თავდაპირველად, იმიტომ, რომ მე ბოლოს სიაში. და რა უნდა მოხდეს აქ პეტრე, იყო ის? ის აშკარად აპირებს აღვნიშნო, რომ ჩემთვის. ასე, რომ აცხადებენ, არსებობს მინიმუმ ორი ხაზი კოდის ნიმუში კოდი, დღეს რომ აპირებს განახორციელოს ამ სცენარი დასძინა 55 კუდი. და შეიძლება მე ვინმე hop და მხოლოდ წარმოადგენს 55? ყველა უფლება, თქვენ ახალი 55. ასე რომ, ახლა რა, თუ მომავალ სცენარი მოდის, და ჩვენ გვინდა ჩადეთ ზე დასაწყისში ან ხელმძღვანელი ამ სიაში? და რა არის თქვენი სახელი, ნომერი 55? აუდიტორია: Jack. დევიდ ჯ Malan: Jack? OK, კარგია თქვენთან შეხვედრა. სტუმარს ბორტზე. ასე რომ, ახლა ჩვენ ვაპირებთ ჩადეთ, ვთქვათ, ნომერი 5. აი მეორე შემთხვევაში სამი მოვედით აქამდე. ასე რომ, თუ 5 ეკუთვნის დასაწყისში, ვნახოთ, თუ როგორ ჩვენ ვხედავთ, რომ გარეთ. მე ინიციალიზაცია ჩემი ptr მომცეთ ნომერი 9 ერთხელ. და მივხვდი, რა, 5 ნაკლებია 9. ასე დაფიქსირება ამ სურათს გვაძლევს. ვის ხელშია, Gabe ან დავითის or-- რა არის 9 ნომერი სახელი? აუდიტორია: Jen. დევიდ ჯ Malan: Jen-ს hands-- რომელიც ჩვენს ხელში უნდა შეიცვალოს? OK, ასე რომ Gabe მიუთითებს თუ რა არის? ჩემთვის. მე ვარ ახალი კვანძში. ამიტომ მე მხოლოდ სახის ნაბიჯი აქ, ვიზუალურად. და ამავე დროს რა აღვნიშნო, რომ? ჯერ კიდევ, სადაც მე მიუთითებს. ასე რომ, ეს არის ის. ასე რომ, ნამდვილად ერთი ხაზი კოდი აფიქსირებს ამ კონკრეტულ საკითხთან დაკავშირებით, როგორც ჩანს. ყველა უფლება, ასე რომ კარგია. და შეიძლება ვინმეს შეიძლება placeholder 5? მოდის up. ჩვენ კიდევ თქვენ მომავალი დრო. ყველა უფლება, ასე ახლა და როგორც განზე, სახელები მე არ მიღების გამოკვეთილ ნახსენები უფლება ახლა, Pred მაჩვენებელი, წინამორბედის მაჩვენებელი და ახალი მაჩვენებელი, რომ უბრალოდ სახელები მოცემულია ნიმუში კოდი მითითებას ან ჩემი ხელები, რომ სახის მიუთითებს გარშემო. რა გქვია? აუდიტორია: Christine. დევიდ ჯ Malan: Christine. სტუმარს ბორტზე. ყველა უფლება, მოდით ახლა განვიხილოთ ოდნავ უფრო შემაშფოთებელი სიტუაცია, რომლის დროსაც მინდა ჩადეთ რაღაც 26 ამ. 20? რა? ამ are-- კარგია გვაქვს ამ კალამი. ყველა უფლება, 20. თუ ვინმე ვერ ერთი ნაჭერი ქაღალდის მზად, უბრალოდ case-- ყველა უფლება. ოჰ, საინტერესოა. კარგად, ეს არის მაგალითი ლექცია შეცდომა. OK, ასე რომ, რა არის თქვენი სახელი კვლავ? აუდიტორია: Julia. დევიდ ჯ Malan: Julia, შეგიძლიათ პოპ out და ვითომ თქვენ არასოდეს არსებობდა? OK, ეს არ მოხდა. დიდი მადლობა. ამიტომ ვარაუდობენ, რომ ჩვენ გვინდა ჩადეთ Julia ამ ბმის სიაში. იგი არის ნომერი 20. და რა თქმა უნდა, ის აპირებს მიეკუთვნება begin-- არ აღვნიშნო, არაფერი გაუკეთებია. ასე რომ, თქვენი მხრივ სახის იყოს ქვემოთ null ან რაღაც ნაგავი ღირებულება. მოდით გეტყვით სწრაფი ამბავი. მე მიუთითებს ნომერი 5 ამ დროს. მერე შეამოწმეთ 9. მერე შეამოწმეთ 17. მერე შეამოწმეთ 22. და ვხვდები, Ooh, Julia უნდა წავიდეს, სანამ 22. ასე რომ, რა უნდა მოხდეს? რომლის ხელში უნდა შეიცვალოს? იულია, ჩემია, or-- რა არის თქვენი სახელი კვლავ? აუდიტორია: ქრისტიანი. დევიდ ჯ Malan: Christian ან? აუდიტორია: Andy. დევიდ ჯ Malan: Andy. ქრისტიანული და ენდი? Andy საჭიროებს აღვნიშნო? Julia. ყველა უფლება. ასე რომ, ენდი, გსურთ აღვნიშნო Julia? მაგრამ დაველოდოთ წუთში. ამბავი ჯერჯერობით, მე სახის ერთი პასუხისმგებელი, იმ გაგებით, რომ მაჩვენებელი არის ის, რომ ის, მოძრავი მეშვეობით სიაში. ჩვენ შეიძლება გვქონდეს სახელი ენდი, მაგრამ არ არსებობს ცვლადში Andy. მხოლოდ სხვა ცვლადი, ჩვენ გვაქვს არის პირველი, ვინც წარმოდგენილია Gabe. ასე რომ, ეს არის რეალურად რატომ ამით შორს ჩვენ არ სჭირდებოდა ეს. მაგრამ ახლა ეკრანზე არსებობს ვთქვათ ისევ Pred მაჩვენებელი. ნება მომეცით, უფრო ზუსტად. არის თუ არა ეს მაჩვენებელი, მე უკეთესი ცოტა უფრო ჭკვიანი , ჩემი iteration. თუ არ იბადება ჩემი გადის აქ ერთხელ, მიუთითებს აქ, მიუთითებს აქ. მაგრამ ნება მომეცით აქვს Pred მაჩვენებელი, წინამორბედის მაჩვენებელი, რომ სახის მიუთითებს ელემენტის I იყო მხოლოდ. ასე რომ, როდესაც მე აქ, ახლა ჩემი მარცხენა ხელის განახლება. როდესაც მე აქ ჩემი მარცხენა ხელის განახლება. და ახლა არა მხოლოდ მომცეთ ელემენტი, რომელიც მიდის შემდეგ Julia, მე მაინც უნდა მომცეთ Andy ელემენტს ადრე. ასე რომ თქვენ გაქვთ, არსებითად, breadcrumbs, თუ გნებავთ, ყველა საჭირო მითითებები. ასე რომ, თუ მე მიუთითებს ენდი და მე ასევე მიუთითებს ქრისტიანულ, რომლის ხელში უნდა აღინიშნოს სხვაგან? ასე რომ, ენდი შეგიძლიათ აღვნიშნო Julia. Julia შეგიძლიათ აღვნიშნო ქრისტიანი. იმის გამო, რომ მას შეუძლია კოპირება ჩემი მარჯვენა ხელის მაჩვენებელი. და რომ ეფექტურად აყენებს თქვენ ისევ ამ ადგილას აქ. ასე მოკლედ, მიუხედავად იმისა, რომ ამ გვაძლევს სახის forever რეალურად განახლება დაკავშირებული სიაში, გააცნობიეროს რომ ოპერაციების შედარებით მარტივია. ეს ერთი, ორი, სამი ხაზების კოდი საბოლოოდ. მაგრამ გახვეული გარშემო იმ ხაზების კოდი, სავარაუდოდ, ცოტა ლოგიკა, რომელიც ეფექტურად სვამს კითხვას, სად ვართ ჩვენ? ვართ ჩვენ დასაწყისში, შუა, ან ბოლომდე? ახლა, რა თქმა უნდა, ზოგიერთი სხვა ოპერაციები შეიძლება განახორციელოს. და ეს სურათები აქ მხოლოდ ასახავს რაც ჩვენ გავაკეთეთ ადამიანები. რაც შეეხება მოხსნა? თუ მინდა, რომ, მაგალითად, ამოიღონ ნომერი 34 ან 55, მე ალბათ იგივე სახის კოდი, მაგრამ მე ვაპირებ ერთი ან ორი ნაბიჯი. იმიტომ, რომ რა არის ახალი? თუ წაშლა ვიღაცას დასასრულს, ისევე როგორც ნომერი 55 და შემდეგ 34, რაც ასევე უნდა შეიცვალოს როგორც მე, რომ? მე უნდა არ evict-- რა არის თქვენი სახელი კვლავ? აუდიტორია: Jack. დევიდ ჯ Malan: Jack. მე უნდა არა მხოლოდ evict-- უფასო Jack, ასე სიტყვასიტყვით მოვუწოდებთ თავისუფალი Jack, ან თუნდაც მაჩვენებელი არსებობს, მაგრამ ახლა რა უნდა შეიცვალოს, პიტერ? თავის მხრივ უკეთესი დაიწყება მიუთითებს ქვემოთ. რადგან, როგორც კი მოვუწოდებ უფასოდ ჯეკ, თუ პეტრეს კვლავ მიუთითებს ჯეკ და მე ამიტომ შენარჩუნება გადიოდა სია და ხელმისაწვდომობის ეს მაჩვენებელი, ეს მაშინ, როცა ჩვენი ძველი მეგობარი სეგმენტაცია ბრალია, შესაძლოა, რეალურად დარტყმა. იმიტომ, რომ ჩვენ, მეხსიერების თავში Jack. შეგიძლიათ იქ უხერხულად მხოლოდ ერთი წუთით. იმიტომ, რომ ჩვენ მხოლოდ რამდენიმე საბოლოო ოპერაცია განიხილოს. მოხსნის ხელმძღვანელი სია, ან beginning-- და ამ ერთი ცოტა შემაშფოთებელი. იმიტომ, რომ ჩვენ უნდა ვიცოდეთ, რომ Gabe სახის განსაკუთრებული ამ პროგრამაში. რადგან მართლაც, მას აქვს თავისი მაჩვენებელი. ის არ არის მხოლოდ მიმდინარეობს მიუთითა, როგორც თითქმის ყველას აქ. ასე რომ, როდესაც სიის სათავეში არის ამოღებულია, რომლის ხელში უნდა შეცვალოს? რა არის თქვენი სახელი კვლავ? აუდიტორია: Christine. დევიდ ჯ Malan: მე ვარ საშინელი at სახელები, როგორც ჩანს. ასე რომ, ქრისტინე და Gabe, რომლის ხელში უნდა შეიცვალოს როდესაც ჩვენ ამოიღონ Christine, ნომერი 5, სურათზე? OK, ასე რომ მოდით Gabe. Gabe აპირებს აღვნიშნო, სავარაუდოდ, ერთი ნომერი 9. მაგრამ შემდეგ რა უნდა მოხდეს? აუდიტორია: Christine უნდა იყოს null [INAUDIBLE]. დევიდ ჯ Malan: OK, ჩვენ, ალბათ make-- გავიგე "null" სადღაც. აუდიტორია: Null და თავისუფალი მისი. დევიდ ჯ Malan: null რა? აუდიტორია: Null და თავისუფალი მისი. დევიდ ჯ Malan: Null და თავისუფალი მისი. ასე რომ, ეს ძალიან მარტივია. და ეს შესანიშნავია, რომ თქვენ ახლა დალაგების იდგა იქ, არ, რომლებიც. იმიტომ, რომ თქვენ უკვე decoupled სიიდან. თქვენ ეფექტურად იქნა ობოლი სიიდან. ასე რომ, ჩვენ უკეთესი მოვუწოდებთ თავისუფალი ამიერიდან Christine მისცეს, რომ მეხსიერების უკან. წინააღმდეგ შემთხვევაში, ყოველ ჯერზე ჩვენ წაშლა კვანძის სიაში ჩვენ შეიძლება მიღების სიაში მოკლე, მაგრამ არა რეალურად მცირდება ზომა მეხსიერებაში. ასე რომ, თუ ჩვენ შევინარჩუნოთ და დასძინა დასძინა, დასძინა რამ სიაში, ჩემი კომპიუტერი შეიძლება ნელა და ნელა და ნელა, რადგან მე გაშვებული out of მეხსიერება, მაშინაც კი, თუ მე არ ვარ რეალურად გამოყენებით ქრისტინე bytes მეხსიერების უქმნით. ამიტომ, საბოლოოდ, არსებობს სხვა სცენარი, რა თქმა უნდა მოხსნა შუა, მოხსნის ბოლოს, როგორც დავინახეთ. მაგრამ უფრო საინტერესო ახლა მთავარია, იქნება განიხილოს ზუსტად რა ქრონომეტრაჟი არის. ასე რომ, არა მარტო შეგიძლიათ შეინახოთ თქვენი ცალი ქაღალდის, თუ, Gabe, თქვენ არ იბადება მიცემა ყველას სტრესი დაადასტურა. დიდი მადლობა, რომ ჩვენი დაკავშირებული სიაში მოხალისეები აქ, თუ ეს შესაძლებელი იქნებოდა. [ტაში] დევიდ ჯ Malan: ყველა უფლება. ასე რომ, რამდენიმე ანალიტიკური კითხვები მაშინ, თუ შეიძლება. ჩვენ ვნახეთ ამ notation ადრე, დიდი O და ომეგა, ზედა საზღვრები და ქვედა საზღვრები შესახებ ქრონომეტრაჟი ზოგიერთი ალგორითმი. ასე რომ, მოდით მიაჩნიათ რამოდენიმე კითხვას. ერთი, და ვუთხარით, ადრე, რა არის გაშვებული დრო ძიება სიაში თვალსაზრისით დიდი O? რა არის ზედა ზღვარი, რომელიც გაშვებული დრო ძებნას უკავშირდება სიაში მიერ განხორციელებულ ჩვენი მოხალისეები აქ? ეს დიდი O of n, წრფივი. რადგან უარეს შემთხვევაში, ელემენტს, როგორიცაა 55, ჩვენ შეიძლება ეძებს შეიძლება იყოს, სადაც ჯეკ იყო, ყველა გზა ბოლომდე. და სამწუხაროდ, განსხვავებით მასივი ჩვენ ვერ მიეცით ამ დროს. მიუხედავად იმისა, რომ ყველა ჩვენი ადამიანებს დალაგებულია მცირე ელემენტები, 5, ყველა გზა მდე უფრო დიდი ელემენტი, 55, რომელიც, როგორც წესი, კარგია. მაგრამ რა ვარაუდს აღარ მოგვცემს გავაკეთოთ? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: ასე უთხარი ერთხელ? აუდიტორია: შემთხვევითი წვდომის. დევიდ ჯ Malan: შემთხვევითი წვდომის. და, თავის მხრივ, ეს ნიშნავს, რომ არ შეუძლია აღარ გამოიყენოს სუსტი zeros, ინტუიცია, და obviousness გამოყენებით ორობითი ძიება და გათიშე და დაიპყროთ. იმის გამო, რომ მიუხედავად იმისა, რომ ადამიანები შეიძლება აშკარად , რომ ენდი და ქრისტიანი უხეშად შუა სიაში, ჩვენ მხოლოდ ვიცით, რომ, როგორც კომპიუტერი skimming სია თავიდანვე. ასე რომ, ჩვენ,, რომ წვდომის. ასე რომ, დიდი O of n ახლა არის ზედა შეკრული ჩვენი ძებნის დროს. რაც შეეხება omega ჩვენი ძებნის? რა არის ქვედა შეკრული მოძიება გარკვეული რაოდენობის ამ სიაში? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: ასე უთხარი ერთხელ? აუდიტორია: One. დევიდ ჯ Malan: One. ასე რომ, მუდმივი დრო. საუკეთესო შემთხვევაში, ქრისტინე არის მართლაც დასაწყისში სიაში. და ჩვენ ვეძებთ ნომერი 5, ამიტომ ჩვენ აღმოვაჩინეთ მისი. ასე რომ, არ არის დიდი გარიგება. მაგრამ ის რაღაც უნდა იყოს დასაწყისში სიაში ამ შემთხვევაში. რაც შეეხება რაღაც წაშლა? რა მოხდება, თუ გსურთ წაშალოთ ელემენტს? რა არის ზედა ზღვარი და ქვედა შეკრული წაშლისას რაღაც უკავშირდება სიაში? აუდიტორია: [INAUDIBLE] დევიდ ჯ Malan: ასე უთხარი ერთხელ? აუდიტორია: n. დევიდ ჯ Malan: n არის მართლაც ზედა შეკრული. იმიტომ, რომ ყველაზე ცუდ შემთხვევაში, ჩვენ ვცდილობთ წაშლა Jack, როგორც ჩვენ გავაკეთეთ. ის ყველა გზა ბოლომდე. იღებს us სამუდამოდ, ან N ნაბიჯები, რათა იპოვოს იგი. ისე, რომ ზედა ზღვარი. რომ არის წრფივი, დარწმუნებული ვარ. და საუკეთესო შემთხვევაში ქრონომეტრაჟი, ან ქვედა საზღვრები, საუკეთესო შემთხვევაში, იქნება მუდმივი დრო. რადგან შესაძლოა, ჩვენ ვცდილობთ წაშლა ქრისტინე, და ჩვენ უბრალოდ გაუმართლა ის დასაწყისში. ახლა დაველოდოთ წუთში. Gabe იყო დასაწყისში, და ჩვენ ასევე განაახლოთ Gabe. ასე რომ, ეს არ იყო მხოლოდ ერთი ნაბიჯია. ასე რომ მართლაც მუდმივი დროს, საუკეთესო შემთხვევაში, უნდა ამოიღონ პატარა ელემენტს? ეს არის, მიუხედავად იმისა, რომ ეს შეიძლება იყოს ორი, სამი, ან თუნდაც 100 ხაზების კოდი, თუ ეს ერთი და იგივე ნომერი ხაზები, არ მარყუჟის, და დამოუკიდებელი ზომა სია, აბსოლუტურად. წაშლის ელემენტს დასაწყისში სიაში, მაშინაც კი, თუ ჩვენ უნდა გაუმკლავდეთ Gabe, ჯერ კიდევ მუდმივი დროს. ასე რომ, ეს, როგორც ჩანს, მასიური ნაბიჯი უკან. და რა ნარჩენები დრო თუ, კვირაში ერთი და კვირას ნულოვანი ჩვენ გვქონდა არა მხოლოდ pseudocode კოდი, მაგრამ ფაქტობრივი კოდი განახორციელოს ის, რასაც ჟურნალი ბაზის n, ან შეხვიდეთ, უფრო სწორად, N, ბაზა 2, თვალსაზრისით მისი ქრონომეტრაჟი. რატომ heck გვინდა, რომ დაიწყოს გამოყენებით რაღაც უკავშირდება სიაში? Yeah. აუდიტორია: ასე რომ თქვენ შეგიძლიათ დაამატოთ ელემენტების მასივი. დევიდ ჯ Malan: ასე რომ თქვენ შეგიძლიათ რჩეულებში ელემენტების მასივი. და ესეც თემატური. და ჩვენ კვლავაც ვხედავთ ეს არის, ეს ვაჭრობის, ბევრი ისევე, როგორც ჩვენ ვნახეთ ვაჭრობის შერწყმა დალაგების. ჩვენ შეიძლება მართლაც დააჩქაროს მოძიება ან დახარისხება, უფრო სწორად, თუ ჩვენ დახარჯოს ცოტა მეტი სივრცე და დამატებითი ბლოკი მეხსიერება ან მასივი შერწყმა დალაგების. მაგრამ ჩვენ უფრო მეტი სივრცეში, მაგრამ ჩვენ დროის. ამ შემთხვევაში, ჩვენ უარს დრო, მაგრამ ჩვენ იძენს მოქნილობა, დინამიკას თუ გნებავთ, რომელიც სავარაუდოდ დადებითი თვისება. ჩვენ ასევე ხარჯავს სივრცეში. რა გაგებით არის დაკავშირებული სიაში უფრო ძვირი თვალსაზრისით სივრცეში, ვიდრე მასივი? სად არის დამატებითი ფართი მოდის? ჰო? აუდიტორია: [INAUDIBLE] მაჩვენებელი. დევიდ ჯ Malan: ჰო, ჩვენ ასევე აქვს მაჩვენებელი. ასე რომ, ეს minorly შემაშფოთებელი რომ აღარ ვარ მე შენახვა მხოლოდ int წარმოადგენენ int. მე შენახვის int და მაჩვენებელი, რომელიც ასევე 32 ბიტი. ასე რომ, მე სიტყვასიტყვით გაორმაგდა თანხის სივრცეში ჩართული. ასე რომ, ვაჭრობის, მაგრამ რომელიც არის ამ შემთხვევაში int. დავუშვათ, რომ თქვენ არ შენახვა int, მაგრამ ვარაუდობენ, თითოეულ ამ მართკუთხედების ან თითოეული ეს ადამიანები არ წარმოადგენს ერთი სიტყვით, ინგლისური სიტყვა, რომელიც შეიძლება იყოს ხუთი პერსონაჟი, 10 პერსონაჟები, იქნებ კიდევ უფრო. შემდეგ დასძინა მხოლოდ 32 მეტი ბიტი შესაძლოა ნაკლები იყოს დიდი გარიგება. რა მოხდება, თუ თითოეული სტუდენტები მიტინგზე პირდაპირი გაგებით სტუდენტი structs რომ აქვს სახელები და სახლები და შესაძლოა ტელეფონის ნომრები და Twitter ამუშავებს და ასე შემდეგ. ასე რომ, ყველა სფეროებში დავიწყეთ ვსაუბრობთ მეორე დღეს, ნაკლებად დიდი გარიგება, როგორც ჩვენი კვანძების უფრო საინტერესო და დიდი გასატარებლად, eh, დამატებითი მხოლოდ კურსორი, რათა მათ ერთად. მაგრამ ის ფაქტი, რომ ვაჭრობის. და მართლაც, კოდი არის უფრო რთული, როგორც თქვენ ვხედავ skimming მეშვეობით რომ კონკრეტულ მაგალითს. მაგრამ რა, თუ იყო ზოგიერთი წმინდა გრაალი აქ. რა მოხდება, თუ ჩვენ არ მიიღოს ნაბიჯი უკან მაგრამ მასიური წინ გადადგმული ნაბიჯია და განახორციელოს მონაცემები სტრუქტურა მეშვეობით, რომელიც ჩვენ შეგიძლიათ ელემენტებს, როგორიცაა ჯეკ ან ქრისტინე და სხვა ელემენტების ამ მასივი ჭეშმარიტი მუდმივი დროს? ძებნა მუდმივი. წაშალე არის მუდმივი. კულტურა არის მუდმივი. ყველა ეს ოპერაცია მუდმივი. რომ იქნება ჩვენი წმინდა გრაალი. და ეს არის, სადაც ჩვენ გააშუქა მომავალი დრო. აგრეთვე შეგიძლიათ შემდეგ.