[Powered by Google Translate] [კვირა 6] [დევიდ ჯ Malan] [ჰარვარდის უნივერსიტეტის] [ეს არის CS50.] [CS50.TV] 

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

მაგრამ ახლა, თუ ჩვენ წასვლას ამ დირექტორიაში აქ- და შენიშნავს, რომ მაქვს conditions2.c- მე და აწარმოებს ამ ახალი ბრძანება, style50, ამ ფაილის conditions2.c, მიუთითოთ, შეამჩნია, რომ ის მაცნობა, რომ უკვე სტილიზებული. Gedit შეამჩნია, რომ ფაილი შეიცვალა დისკზე, და თუ მე დააჭირეთ განაახლეთ, ყველა თქვენი პრობლემები ავტომატიზირებულია. [ტაში] სწორედ ერთი რამ გავაკეთეთ ამ კვირას. გააცნობიეროს, რომ ეს არის არასრულყოფილი, რადგან არსებობს კოდი რომ ეს უბრალოდ ვერ შეძლებს, რათა stylize კარგად, მაგრამ გააცნობიეროს ეს არის ინსტრუმენტი შეგიძლიათ ისარგებლოს თუ მხოლოდ Tidy up ზოგიერთი უფრო errantly განთავსებული Curly braces და ასე შემდეგ. 

მაგრამ უფრო მყარი ახლა არის CS50 ქვითარი. With CS50 შემოწმება, შეგიძლიათ რეალურად შეასრულოს იგივე სისწორის ტესტები საკუთარ კოდი, რომელიც სწავლების პრაქტიკის შეუძლიათ. ეს არის command line პროგრამა, რომელიც მოდის ახლა ელექტრო მოწყობილობების როგორც კი თქვენ ამის გაკეთება update50 როგორც პოსტი pset 4 სპეციფიკაციები და გამოიყენოს იგი არსებითად მოსწონს ეს. თქვენ აწარმოებს ბრძანება check50. მაშინ კორიდორი ბრძანების არგუმენტი, ან მეტი საყოველთაოდ ცნობილია, როგორც შეცვლა ან დროშას. საერთოდ, რამ აქვს დეფისის უწოდებენ შეცვლა to command line პროგრამა, ე.წ. გ განსაზღვრავს ამოწმებს, რომ გსურთ აწარმოებს. 

ტესტები რომ გსურთ აწარმოებს იდენტიფიცირებულია ცალსახად ამ სტრიქონს, 2012/pset4/resize. სხვა სიტყვებით, ეს მხოლოდ თვითნებური მაგრამ უნიკალური სიმებიანი ჩვენ ვიყენებთ, რათა ცალსახად იდენტიფიცირება pset 4 ს სისწორის ტესტები. და მაშინ დააკონკრეტა ჰარით გამოყოფილი ჩამონათვალი ფაილი, რომელიც ასატვირთად to CS50 შემოწმება ანალიზი. მაგალითად, თუ მე წასვლას ჩემი გამოსავალი აქ resize.c- ნება მომეცით ქმნის უფრო დიდი ტერმინალი ფანჯარა- მე და წავიდეთ წინ და აწარმოებს ვთქვათ check50-C 2012/pset4/resize, და მერე წავიდეთ წინ და მიუთითეთ სახელები ფაილი resize.c და შემდეგ დააჭიროთ, ეს კომპრესები, ეს ატვირთვები, ის ამოწმებს, და მე უბრალოდ ვერ მოხერხდა მთელი bunch of ტესტები. ერთი წითელი ზედა მარცხენა ნათქვამია, რომ resize.c და BMP არსებობს. ეს იყო ტესტი. ეს იყო კითხვა ვთხოვეთ. და ეს უბედური, რადგან პასუხი იყო ყალბი. თეთრი ქვემოთ ტექსტი ნათქვამია მოსალოდნელია bmp.h არსებობს, და ეს უბრალოდ ჩემი ბრალია. დამავიწყდა ატვირთვა, ასე რომ მე უნდა ატვირთოთ ორივე ფაილი resize.c და bmp.h. მაგრამ ახლა შეამჩნია ყველა სხვა ტესტები არიან ყვითელი რადგან მათ არ აწარმოებს, და ასე smiley face არის ვერტიკალური, რადგან ის არც ბედნიერი და არც სამწუხარო, მაგრამ უნდა შეცვალოს სიტუაცია, რომ საკითხი წითელი ადრე იმ სხვა ამოწმებს მიიღებს. 

ნება მომეცით დაფიქსირება ამ. ნება მომეცით დააშორებს და გამეორება ამ, ამ დროის bmp.h ასევე ბრძანების სტრიქონში, შეიყვანეთ და ახლა თუ ყველა კარგად იქნება, ეს ხდება შემოწმება და მერე დაბრუნების შედეგად-გამართავს თქვენი სუნთქვა- ყველა მწვანე, რაც იმას ნიშნავს, მე ვაკეთებ ნამდვილად კარგად pset 4 ჯერჯერობით. თქვენ შეგიძლიათ ნახოთ და infer საწყისი აღწერითი ტექსტი აქ ზუსტად რა არის ჩვენ ტესტირება. ჩვენ გამოცდილი პირველი არ არსებობს ფაილი? ჩვენ მაშინ ტესტირება არ resize.c კომპილირების? მაშინ ჩვენ ტესტირება იგი არ შეცვლის 1x1-pixel BMP, როდესაც N, Resize ფაქტორი, არის 1. ახლა კი, თუ არ ვიცი, რა N არის, თქვენ კიდევ თქვენ ჩაყვინთვის შევიდა pset 4, მაგრამ, რომ უბრალოდ არის საღი აზრის შეამოწმეთ დარწმუნდით, რომ თქვენ არ resizing გამოსახულება ყველა თუ Resize ფაქტორი 1. თუ, პირიქით, ეს უცვლის ზომას 1x1 pixel to 1x1 pixel BMP to 2x2 სწორად როდესაც N არის 2, მაშინ ანალოგიურად, მაღაროს აყალიბებს შესაბამისად. 

მოკლედ, ეს იმას ნიშნავდა, რომ, ერთი, მიიღოს გადაკვეთის თითების გარეთ განტოლება უფლება სანამ თქვენი pset. თქვენ იცით ზუსტად რა თქვენი TF მალე ვიცი როდესაც მიდიხარ შესახებ წარდგენის ზოგიერთი ამ პრობლემის კომპლექტი, და ასევე პედაგოგიური მოტივაცია მართლაც დააყენოს შესაძლებლობა თქვენს წინაშე, ისე რომ, როდესაც თქვენ იცით აპრიორი რომ არსებობს შეცდომები თქვენს კოდი და ტესტები რომ მის მიმართ არ ხორციელდება გავიდა, თქვენ შეგიძლიათ განათავსოთ უფრო ეფექტური დრო up წინა ხალხს პრობლემების ოპერატიულ მოგვარებას ვიდრე დაკარგავს ქულა, მიიღოთ კავშირი თქვენი TF, და მერე, "Ahh," როგორც მე უნდა figured რომ. ეხლა მაინც არსებობს ინსტრუმენტი, რათა დაგეხმაროთ თქვენ მოვძებნოთ რომ. ეს არ აღვნიშნო, სადაც შეცდომა, მაგრამ ეს გითხრათ რა არის სიმპტომატური იგი. 

ახლა აცნობიერებენ ტესტები არ არის აუცილებლად ამომწურავი. მხოლოდ იმიტომ, რომ თქვენ გაქვთ ეკრანზე სავსე მწვანე smiley სახეები არ ნიშნავს თქვენი კოდი არის სრულყოფილი, მაგრამ ეს იმას ნიშნავს, რომ მან გაიარა გარკვეული ტესტების დადგენილი სპეც. ზოგჯერ ჩვენ არ გაათავისუფლებს ამოწმებს. მაგალითად, whodunit, ერთ ასპექტს pset 4, არის სახის გულდასაწყვეტია თუ ჩვენ მოგაწვდით პასუხი, თუ რა არის ეს, და იქ ხმების გზები გამოსავლენად ვინც პირის არის, რომ წითელი ხმაური. სპეც ყოველთვის დააზუსტეთ მომავალი pset 5 Onward რა ამოწმებს არსებობს თქვენთვის. თქვენ შეამჩნევთ არსებობს ამ თეთრი URL ბოლოში. ახლა, ეს მხოლოდ დიაგნოსტიკური გამომუშავება. თუ თქვენ ესტუმრებით, რომ URL, თქვენ შეძლებთ მთელი bunch of გიჟები, cryptic შეტყობინებები რომ მობრძანდით, გაეცნონ, მაგრამ ძირითადად თანამშრომლებისათვის ასე, რომ ჩვენ შეგვიძლია დიაგნოსტიკა და გამართვის შეცდომებს check50 თავად. 

გარეშე ado, მოდით გადაადგილება სად ვიქნებით შეჩერდით. CS50 ბიბლიოთეკა ავიღეთ თავისთავად რამოდენიმე კვირაა, მაგრამ შემდეგ, გასულ კვირას დავიწყეთ peeling უკან ერთი ფენების იგი. ჩვენ დავიწყეთ აყენებს განზე სიმებიანი სასარგებლოდ რა ნაცვლად? [სტუდენტთა] ჩარ. ჩარ *, რომელსაც უკვე char * ყველა ამ დროს, მაგრამ ახლა ჩვენ არ ვიტყვი, რომ ეს ფაქტობრივი მონაცემების ტიპის სიმებიანი. უფრო მეტიც, უკვე სინონიმი ჯიშები ამისთვის char *, და სიმებიანი არის თანმიმდევრობა გმირები, ასე რატომ ხდება აზრი წარმოადგენენ სიმები როგორც char * s? რას char * წარმოადგენენ კონტექსტი კონცეფცია სიმებიანი? Yeah. >> [სტუდენტური] პირველ სიმბოლოს. კარგი, პირველ სიმბოლოს, მაგრამ არა საკმაოდ პირველი ხასიათი. ეს-[სტუდენტთა] მისამართი. კარგი, მისამართი პირველი ხასიათი. ყველა რომ აუცილებელია წარმოადგენენ string in კომპიუტერის მეხსიერების მხოლოდ უნიკალური მისამართი მისი პირველივე byte. თქვენ კი არ უნდა ვიცოდეთ რამდენი ხანი არის რადგან როგორ შეიძლება გაერკვნენ, რომ დინამიურად? [სტუდენტური] სიმებიანი სიგრძე. შეგიძლიათ დარეკოთ სიმებიანი სიგრძე, კარგი, მაგრამ რამდენად შეესაბამება სიმებიანი სიგრძე მუშაობს? რას აკეთებთ? Yeah. [სტუდენტური] Keep აპირებს სანამ არ მიიღებთ null ხასიათი. ჰო, ზუსტად, უბრალოდ iterates ერთად ამისთვის მარყუჟის, ხოლო მარყუჟის, რასაც საწყისი * ბოლომდე, და ბოლოს არის წარმოდგენილი მიერ \ 0, ე.წ. nul ხასიათი, nul, არ იყოს დაბნეული და null, რომელიც მაჩვენებელი, რაც ამუშავება საუბარში კიდევ ერთხელ დღეს. 

ჩვენ peeled უკან ფენით GetInt და შემდეგ მივიღეთ შევხედოთ GetString, და გავიხსენოთ, რომ ორივე ამ ფუნქციების, ან მართლაც, GetString, იყო გამოყენებით გარკვეული ფუნქცია რეალურად გარჩევის, რომ წაიკითხა ან ანალიზი, მომხმარებლის შეყვანის. და რა იყო, რომ ახალი ფუნქცია? Scanf ან sscanf. ეს ფაქტიურად მოდის რამდენიმე სხვადასხვა არომატის. არსებობს scanf, არსებობს sscanf, არსებობს fscanf. ახლა, თუმცა, მოდით ფოკუსირება ერთი ყველაზე ადვილად ილუსტრირებული, და ნება მომეცით წავიდეთ წინ და ქმნის in ელექტრო მოწყობილობების შემდეგის მსგავსად, scanf1.c. ეს არის სუპერ მარტივი პროგრამა, მაგრამ, რომ არ ის, რაც ჩვენ არასოდეს კეთდება დახმარების გარეშე CS50 ბიბლიოთეკაში. ეს იღებს int საწყისი მომხმარებელს. როგორ მუშაობს იგი? კარგად, შეესაბამება 16 იქ, შეამჩნევთ, რომ ვაცხადებთ int მოუწოდა x, და ამ დროისთვის ამბავი, რა არის ღირებულება x? [Inaudible სტუდენტი საპასუხოდ] [დავით მ] მარჯვენა, ვინ იცის, ზოგიერთი ნაგვის ღირებულება პოტენციურად, ასევე 17, ჩვენ უბრალოდ ვუთხრა მომხმარებლის მომეცი ნომერი, გთხოვთ, და ნაბიჯი 18 არის სადაც იგი იღებს საინტერესო. Scanf ჩანს სესხება იდეა საწყისი printf, რომ ის იყენებს ამ ფორმატის კოდების შეთავაზებები. % D არ არის, რა თქმა უნდა ათობითი რიცხვი. მაგრამ რატომ ვარ მე გადადის & x ნაცვლად მხოლოდ x? ყოფილი სწორია. Yeah. [Inaudible სტუდენტი საპასუხოდ] სწორედ, თუ მიზანი ამ პროგრამის, როგორიცაა ფუნქციის GetInt თავად, მისაღებად int საწყისი მომხმარებლის შემიძლია გაივლის ფუნქციები ყველა ცვლადები მინდა, მაგრამ თუ არ გაივლის მათ მიერ მინიშნება ან მისამართი ან კურსორი, ყველა სინონიმი დღევანდელი მიზნებისათვის, მაშინ ეს ფუნქცია არ აქვს უნარი შეცვალოს შინაარსი რომ ცვლადი. ეს კორიდორი ასლი ისევე buggy ვერსია swap რომ ჩვენ ვისაუბრეთ რამდენიმეჯერ არის. 

მაგრამ ამის ნაცვლად, ამით და x, მე სიტყვასიტყვით ავლით რა? [სტუდენტური] მისამართზე. >> მისამართი x. ეს მოსწონს ხატვის რუკა ფუნქცია მოუწოდა scanf და ამბობდა აქ, ეს მითითებებს ბლოკი მეხსიერება კომპიუტერის რომ შეგიძლიათ შეინახოთ რამდენიმე რიცხვი სისტემაში იმისათვის sscanf აქამდე ასე რა ოპერატორი, რა ნაჭერი სინტაქსისიც იგი აპირებს უნდა გამოვიყენოთ მიუხედავად იმისა, რომ ჩვენ ვერ ვხედავ, რადგან სხვისი დაწერა ეს ფუნქცია? სხვა სიტყვებით - რა რომ? [სტუდენტური] X წაიკითხა. არსებობს იქნება ზოგიერთი მოსმენით, მაგრამ მხოლოდ დაკავშირებით x აქ. თუ scanf მიმდინარეობს გავიდა მისამართი X, syntactically, რა ოპერატორი ვალდებულია არსებობს სადმე შიგნით scanf განხორციელების ისე, რომ scanf შეიძლება რეალურად დაწეროს რიცხვი 2 რომ მისამართი? ჰო, ასე *. შეგახსენებთ, რომ * ჩვენი dereference ოპერატორი, რომელიც არსებითად ნიშნავს იქ. 

ერთხელ თქვენ გადაეცა მისამართი, როგორც ეს აქ, scanf ალბათ თუ ჩვენ რეალურად დაათვალიერეს მისი კოდის- აკეთებს * x ან ექვივალენტი ფაქტიურად წასვლა რომ მისამართი და დააყენა გარკვეული მნიშვნელობა არსებობს. ახლა, რაც შეეხება როგორ scanf იღებს შეიტანენ კლავიატურა, ჩვენ ტალღა ჩვენს ხელში გარეთ დღეს. უბრალოდ ვივარაუდოთ, რომ ოპერაციული სისტემა საშუალებას sscanf გაიგო to მომხმარებლის კლავიატურის, მაგრამ ამ ეტაპზე ახლა ხაზი 19, როცა ჩვენ უბრალოდ ამობეჭდოთ x, აშკარად ჩანს, რომ საქმე რომ scanf დააყენა int in x. სწორედ როგორ scanf მუშაობს, და გავიხსენოთ გასულ კვირას სწორედ როგორ GetString და GetInt და მისი ოჯახის სხვა ფუნქციების საბოლოოდ მუშაობს, თუმცა უმნიშვნელო ეწინააღმდეგება მოსწონს sscanf, რაც იმას ნიშნავს, სკანირების სიმებიანი ნაცვლად კლავიატურაზე. მაგრამ მოდით შევხედოთ პატარა ეწინააღმდეგება ამ. In scanf2, მე რეალურად ბრალია. რა არის არასწორი და მე დასამალი კომენტარი რომ განმარტავს, იმდენი- რა არის არასწორი ამ პროგრამით, ვერსია 2? იყოს, როგორც ტექნიკური, რაც შეიძლება ამ დროს. იგი გამოიყურება საკმაოდ კარგი. ეს ლამაზად indented, მაგრამ- Okay, რა მოდით prune იგი ქვემოთ მოკლე კითხვები? ხაზი 16. რა არის ხაზზე 16 აკეთებდა ზუსტი მაგრამ ტექნიკური ინგლისურ? შესმენილ პატარა უხერხულ. დიახ, მაიკლ. [სტუდენტური] ეს მიუთითებს პირველი წერილი სიმებიანი. 

Okay, ახლოს. ნება მომეცით tweak, რომ ცოტა. მიმანიშნებელი პირველი წერილი სიმებიანი, თქვენ ვაცხადებთ ცვლადში ბუფერული რომელიც აღვნიშნო, რომ პირველი მისამართი სიმებიანი, უფრო სწორად, რომელიც აღვნიშნო უფრო კონკრეტულად, რათა char. გაითვალისწინეთ ის რეალურად არ მიუთითებს სადმე რადგან იქ არ არის დავალება ოპერატორი. იქ არ არის თანაბარი ნიშანი, ასე რომ ყველა ვაკეთებთ არის გამოყოფის ცვლადში ბუფერული. ეს ხდება, რომ იყოს 32 ბიტი იმიტომ რომ მომცეთ, და შინაარსი ბუფერული სავარაუდოდ საბოლოოდ შეიცავს მისამართი char, მაგრამ ახლა, რა ბუფერული შეიცავდეს? რამოდენიმე გაყალბებულად, ვინ იცის, ზოგიერთი ნაგვის ღირებულება, იმიტომ, რომ ჩვენ არ არის მკაფიოდ ინიციალიზაცია, ასე რომ ჩვენ არ უნდა ვივარაუდოთ, არაფერი. Okay, ასე არის ხაზზე 17 IS-რას ხაზი 17 გავაკეთო? იქნებ, რომელიც თბილი ამ მდე. იგი ბეჭდავს სტრინგს, არა? იგი ბეჭდავს სიმებიანი გთხოვთ. 

Line 18 არის სახის ნაცნობი ახლა, რომ ჩვენ უბრალოდ დაინახა ეწინააღმდეგება ამ მაგრამ სხვადასხვა ფორმატში კოდი, ასევე ხაზი 18, ჩვენ ვეუბნებით scanf აქ მისამართი ბლოკი მეხსიერება. მინდა ბეჭედი წელს სიმებიანი, როგორც ითვალისწინებს% s, მაგრამ პრობლემა ის არის, რომ ჩვენ არ კეთდება რამდენიმე რამ აქ. რა არის ერთი პრობლემა? [სტუდენტური] ეს ცდილობს dereference null მაჩვენებელი. კარგი, null ან უბრალოდ სხვაგვარად უცნობია პოინტერები. თქვენ გადაცემის scanf მისამართი, მაგრამ თქვენ მხოლოდ განაცხადა მომენტში წინ რომ მისამართია ზოგიერთი ნაგვის ღირებულების რადგან ჩვენ ვერ რეალურად მივანიჭოთ მას არაფერი, და ა.შ. თქვენ ვეუბნებოდი scanf ეფექტურად წასვლა დააყენა სიმებიანი აქ, მაგრამ ჩვენ არ ვიცით, სად აქ ჯერ კიდევ არის, ამიტომ ჩვენ არ რეალურად გამოყოფილი მეხსიერების ბუფერი. უფრო მეტიც, რას ასევე კი არ ვეუბნებოდი scanf? დავუშვათ, რომ ეს იყო ბლოკი მეხსიერება, და ეს არ იყო ნაგვის ღირებულება, მაგრამ თქვენ მაინც არ ვეუბნებოდი scanf რაღაც მნიშვნელოვანია. [სტუდენტური] სად ის რეალურად არის, ampersand. Ampersand, ამიტომ ამ შემთხვევაში, ეს okay. იმის გამო, რომ ბუფერული უკვე გამოცხადდა მაჩვენებელი ერთად * ნაჭერი სინტაქსი, ჩვენ არ უნდა გამოვიყენოთ ampersand იმიტომ რომ უკვე მისამართი, მაგრამ ვფიქრობ, გავიგე აქ. [სტუდენტური] როგორ დიდი არის ეს? კარგი, ჩვენ არა ვართ ვეუბნებოდი scanf რამდენად დიდი ეს ბუფერული არის, რაც იმას ნიშნავს, მაშინაც კი, თუ ბუფერული იყო მაჩვენებელი, ჩვენ ვამბობთ, scanf, დაუსვან სიმებიანი აქ, მაგრამ აქ შეიძლება იყოს 2 ბაიტი, შეიძლება იყოს 10 ბაიტი, შეიძლება იყოს megabyte. Scanf ვიზიტორების იდეა, და რადგან ეს ბლოკი მეხსიერება სავარაუდოდ, ეს არ სიმებიანი ამჟამად. ეს მხოლოდ სიმებიანი ერთხელ წერთ გმირები და \ 0 რომ ბლოკი მეხსიერება. ახლა კი რამოდენიმე ბლოკი მეხსიერება. Scanf არ ვიცი, როდის უნდა შეწყვიტოს წერილობით, რომ მისამართზე. 

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

აქ, მე ვამბობ scanf აქ ბლოკი მეხსიერება. ამჯერად, ეს რეალურად ბლოკი მეხსიერება, მაგრამ რატომ არის ეს პროგრამა ჯერ კიდევ exploitable? რა არის არასწორი კვლავ? მე განაცხადა მომეცი 16 ბაიტი, მაგრამ- [სტუდენტური] რა თუ ისინი აკრიფოთ ზე მეტ 16? სწორედ, რა, თუ მომხმარებლის ტიპები 17 ასო, ან 1700 გმირები? ფაქტობრივად, ვნახოთ, შევძლებთ თუ არა მოგზაურობა ამ შეცდომას ახლა. სჯობს, მაგრამ არ არის სრულყოფილი. ნება მომეცით წავიდეთ წინ და აწარმოებს მიიღოს scanf3 შედგენა ამ პროგრამის. ნება მომეცით აწარმოებს scanf3, სიმებიანი გთხოვთ: Hello, და ჩვენ, როგორც ჩანს, იქნება. ნება მომეცით ვცდილობთ ოდნავ აღარ ერთი, გამარჯობა. Okay, მოდით გამარჯობა როგორ ხარ დღეს, შეიყვანეთ. შესმენილ სახის გაუმართლა აქ, ვთქვათ გამარჯობა, როგორ ხარ. Damn it. Okay, ასე მივიღეთ გაუმართლა. ვნახოთ, შევძლებთ თუ არა დაფიქსირება ამ. არა, ეს არ აპირებს ნება მომეცით ასლი. მოდით ვეცადოთ ეს კიდევ ერთხელ. ყველა უფლება დგას. ჩვენ დავინახავთ, თუ ხანგრძლივი შემიძლია პრეტენზია ფოკუსირება მიუხედავად აკეთებენ. Damn it. სწორედ საკმაოდ შესაბამისი, რეალურად. იქ ჩვენ წავიდეთ. ქულა გააკეთა. 

ეს, მუცელზე თუმცა ეს ასევე არის, ეს არის ერთერთი წყაროების დიდი დაბნეულობა როდესაც წერა პროგრამებს, აქვს შეცდომები, რადგან ისინი მანიფესტი თავად მხოლოდ ერთხელ, ხოლო ზოგჯერ. რეალობაა ის, რომ მაშინაც კი, თუ თქვენი კოდი მთლიანად გატეხილი, ეს შესაძლოა მხოლოდ მთლიანად გატეხილი ერთხელ ხოლო რადგან ზოგჯერ, არსებითად რა ხდება არის ოპერაციული სისტემა გამოყოფს ცოტა მეტი მეხსიერების ვიდრე რეალურად სჭირდება სხვადსხვა მიზეზის გამო, და ასე არავინ იყენებს მეხსიერების შემდეგ თქვენი ბლოკი 16 გმირები, ასე რომ, თუ მიდიხარ 17, 18, 19, რასაც, ეს არ ასეთი დიდი გარიგება. ახლა, კომპიუტერი, მაშინაც კი, თუ ის არ ავარიული იმ ეტაპზე, შესაძლოა საბოლოოდ გამოიყენოთ byte ხმების 17 ან 18 ან 19 რაღაც სხვას, სადაც აღვნიშნო თქვენი მონაცემები, რომ თქვენ დააყენა იქ, თუმცა ზედმეტად ხანგრძლივი, აპირებს მიიღოს ინსტალერის პოტენციურად ზოგიერთი სხვა ფუნქცია. ეს აუცილებლად არ აპირებს დარჩეს უცვლელი, მაგრამ ეს აუცილებლად არ იწვევს seg ბრალია. მაგრამ ამ შემთხვევაში, მე საბოლოოდ გათვალისწინებული საკმარისი გმირები რომ მე არსებითად გადააჭარბა ჩემი სეგმენტი მეხსიერება, და bam, ოპერაციული სისტემა განაცხადა, "ბოდიში, რომ არ არის კარგი, სეგმენტაცია ბრალია." 

და ვნახოთ ახლა თუ რა რჩება აქ ჩემი დირექტორია- შეამჩნია, რომ მე ამ ფაილის აქ, ძირითადი. გაითვალისწინეთ, რომ ეს კიდევ ერთხელ მოუწოდა ძირითადი ნაგავსაყრელი. ეს არსებითად ფაილი, რომელიც შეიცავს შინაარსი თქვენი პროგრამის მეხსიერებაში მომენტი, რომლის დროსაც იგი შეეჯახა, და უბრალოდ ცდილობენ პატარა მაგალითი აქ ნება მომეცით წავიდეს აქ და აწარმოებს GDB on scanf3 და შემდეგ მიუთითე მესამე არგუმენტი ეწოდება core, და შენიშნავს, აქ რომ თუ სიაში კოდი, ჩვენ შევძლებთ, როგორც ყოველთვის ერთად GDB დაიწყოს გავლით ამ პროგრამის და შემიძლია გაუშვით და როგორც კი მოხვდა, როგორც ერთად ნაბიჯი სარდლობის GDB- როგორც კი მოხვდა პოტენციურად buggy ხაზის შემდეგ აკრეფით უზარმაზარი ტექსტი, მე შევძლებთ რეალურად იდენტიფიცირება აქ. გაძლიერებული ამ, თუმცა, ნაწილში თვალსაზრისით ძირითადი dumps და მინდა ასე რომ თქვენ შეგიძლიათ რეალურად poke გარშემო შიგნით ძირითადი ნაგავსაყრელი და ნახე რა ხაზის პროგრამის ჩაიშალა თქვენ. ნებისმიერი კითხვები შემდეგ პოინტერები და მისამართები? იმის გამო, რომ დღეს, ჩვენ ვაპირებთ დავიწყოთ აღების თავისთავად, რომ ეს ყველაფერი არსებობს და ჩვენ ვიცით, ზუსტად რა ისინი. დიახ. 

[სტუდენტური] როგორ, შენ არ უნდა დააყენოს ampersand შემდეგი ნაწილს- კარგი კითხვაა. როგორ მოვიდა მე არ უნდა დააყენოს ampersand შემდეგ ხასიათი მასივს როგორც მე ადრე უმეტესობა ჩვენი მაგალითები? მოკლე პასუხი არის კოლექტორები ხართ პატარა სპეციალური. თქვენ შეგიძლიათ თითქმის ვფიქრობ ბუფერული როგორც მართლაც მისამართი, და ეს ასე მოხდება, რომ იყოს საქმე, რომ კვადრატული ფრჩხილი ნოტაცია არის კომფორტული ასე, რომ ჩვენ შეგვიძლია წასვლას bracket 0, bracket 1, bracket 2, გარეშე გამოყენება * ნოტაცია. სწორედ ცოტა თეთრი ტყუილი, რადგან მასივები და პოინტერები არიან, ფაქტობრივად, ცოტა განსხვავებული, მაგრამ ხშირად, მაგრამ არა ყოველთვის იქნება გამოყენებული interchangeably. მოკლედ, როდესაც ფუნქციის ელოდება მომცეთ ბლოკი მეხსიერება, თქვენ შეგიძლიათ ან გაიაროს ეს მისამართი, რომელიც დაბრუნდა მიერ malloc, და ვნახავთ malloc კიდევ ხანგრძლივი, ან შეგიძლიათ გაიაროს ეს სახელწოდება მასივი. თქვენ არ უნდა გავაკეთოთ ampersand ერთად კოლექტორები რადგან ისინი უკვე არსებითად like მისამართები. სწორედ ერთი გამონაკლისი. კვადრატულ ფრჩხილებში მათი სპეციალური. 

იქნებ დააყენა ampersand შემდეგ ბუფერული? არ ამ შემთხვევაში. რომ არ იმუშავებს, ვინაიდან, კიდევ ერთხელ, ამ კუთხეში შემთხვევაში სად კოლექტორები არ არიან საკმაოდ რეალურად მისამართები. მაგრამ ჩვენ ალბათ დაბრუნდება, რომ ხანგრძლივი სხვა მაგალითები. მოდით ცდილობენ გადაჭრის პრობლემა აქ. ჩვენ გვყავს მონაცემები სტრუქტურა, რომელიც ჩვენ გამოყენებით, გარკვეული დროის ცნობილი როგორც მასივი. მაგალითია ის, რაც ჩვენ უბრალოდ ჰქონდა. მაგრამ კოლექტორები აქვს გარკვეული upsides და downsides. კოლექტორები კი კარგია, თუ რატომ? რა არის ერთი რამ, რომ გსურთ-იმდენად, რამდენადაც ეს მოგწონთ კოლექტორები-ს შესახებ კოლექტორები? რა არის მოსახერხებელი მათ შესახებ? რა არის მყარი? რატომ გააცნოს მათ პირველ რიგში? Yeah. [სტუდენტური] მათ შეუძლიათ შესანახად ბევრი მონაცემები, და თქვენ არ უნდა გამოვიყენოთ მთელი რამ. თქვენ შეგიძლიათ გამოიყენოთ მონაკვეთზე. კარგი, ერთად მასივების შენახვა შეუძლია მრავალი მონაცემები, და თქვენ არ აუცილებლად უნდა გამოვიყენოთ ყველა ის, ასე რომ თქვენ შეგიძლიათ overallocate, რაც შესაძლოა მოსახერხებელი თუ თქვენ არ იცით, წინასწარ რამდენი რამე უნდა ველოდოთ. 

GetString არის მაგალითი. GetString, წერილობითი ჩვენს მიერ ვიზიტორების იდეა რამდენი სიმბოლო უნდა ველოდოთ, ასე რომ ჩვენ შეგვიძლია გამოყოფს მოცულობით მიმდებარე მეხსიერების არის კარგი. კოლექტორები ასევე გადაწყვიტოს პრობლემა დავინახეთ რამდენიმე კვირის წინ არის სადაც თქვენი კოდი იწყებს გადაეცემა შევიდა რაღაც ძალიან ცუდად დაპროექტებული. შეგახსენებთ, რომ მე შექმნილი სტუდენტი სტრუქტურა მოუწოდა დავით, და მაშინ ეს იყო რეალურად ალტერნატიული, თუმცა, to მქონე ცვლადში სახელი და სხვა ცვლადში, ვფიქრობ, კერძო სახლი, და სხვა ცვლადში ID რადგან ამბავი მე მაშინ სურდა შემოიღონ რაღაც მინდა რობ იქნება პროგრამაში, ასე შემდეგ გადავწყვიტე დაველოდოთ წუთში, მე უნდა გადაარქვათ ამ ცვლადებს. მოდით მოვუწოდებთ მაღაროს name1, ID1, house1. მოდით მოვუწოდებთ რობ ს name2, house2, ID2. მაგრამ შემდეგ დაველოდოთ წუთში, რაც შეეხება Tommy? მაშინ ჩვენ გვქონდა სამი ცვლადი. ჩვენ გააცნო ვინმე, ოთხი კომპლექტი ცვლადები. მსოფლიოში დაიწყო მისაღებად ბინძურ ძალიან სწრაფად, ამიტომ ჩვენ გააცნო structs, და რაც მყარი შესახებ struct? რას C struct მოგცემთ გავაკეთოთ? მართლაც უხერხულია დღეს. რა? >> [Inaudible სტუდენტი საპასუხოდ] ჰო, კონკრეტულად, typedef გაძლევთ საშუალებას შექმნათ ახალი მონაცემები ტიპის, და struct, struct სიტყვით, გაძლევთ საშუალებას encapsulate კონცეპტუალურად დაკავშირებული დარტყმები მონაცემთა ერთად და ამის შემდგომ მოვუწოდებთ მათ რაღაც სტუდენტი. 

ეს იყო კარგი, რადგან ახლა ჩვენ შეგვიძლია მოდელირებისა ბევრად უფრო სახის კონცეპტუალურად თანმიმდევრული ცნება სტუდენტი ცვლადი ვიდრე თვითნებურად მქონე ერთი ტექსტი, ერთი ID, და სხვ. კოლექტორები კი კარგია, რადგან ისინი საშუალებას მოგვცემს დავიწყოთ გაწმენდის ჩვენი კოდი. მაგრამ რა არის downside ახლა მასივი? რა შეგიძლიათ არ გააკეთებს? Yeah. [სტუდენტური] თქვენ უნდა იცოდეს, რამდენად დიდი ეს არის. თქვენ უნდა იცოდეს, რამდენად დიდი ეს არის, ამიტომ სახის ტკივილი. იმ თქვენ წინასწარი პროგრამირების გამოცდილება ვიცი, რომ ბევრი ენების, მოსწონს ჯავის, შეგიძლიათ ბლოკი მეხსიერება, კონკრეტულად მასივი, რამდენად დიდი ხარ, ერთად სიგრძე, ქონება, ასე ვთქვათ, და ეს მართლაც მოსახერხებელია. In C, თქვენ კი ვერ ვუწოდებთ strlen on generic მასივი რადგან strlen, როგორც სიტყვა გულისხმობს, არის მხოლოდ სიმები, და შეგიძლიათ გაერკვნენ სიგრძეზე string რადგან ამ ადამიანის კონვენცია მქონე \ 0, მაგრამ მასივი, უფრო generically, მხოლოდ ბლოკი მეხსიერება. თუ ეს მასივი ints, იქ არ იქნება ზოგიერთი სპეციალური ხასიათის დასასრულს გელოდებათ. თქვენ უნდა გვახსოვდეს, სიგრძით მასივი. კიდევ ერთი downside of მასივი reared მისი მეთაურის GetString თავად. რა არის კიდევ ერთი downside of მასივი? სერ, უბრალოდ მე და შენ დღეს. [Inaudible სტუდენტი საპასუხოდ] >> ეს რა? ეს განაცხადა Stack. Okay, განაცხადა Stack. რატომ არ მოგწონთ, რომ? [სტუდენტური] გამო იგი იღებს reused. იგი იღებს reused. Okay, თუ თქვენ იყენებთ მასივი გამოყოს მეხსიერება, თქვენ არ შეგიძლიათ, მაგალითად, მისი დაბრუნება, რადგან ეს on Stack. Okay, რომ მინუსი. და როგორ დაახლოებით ერთი მეორე მასივი? ერთხელ თქვენ გამოყოფს იგი, თქვენ სახის ბრალია თუ გჭირდებათ მეტი სივრცე ვიდრე, რომ მასივი აქვს. 

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

ახლა, მხოლოდ დაჭერა აქ არის ის, რომ ამ თითქმის იგრძნობა მაქვს მთელი bunch სხვადასხვა ცვლადები. ეს იგრძნობა ხუთი ცვლადის სხვადასხვა პოტენციურად. მაგრამ რა, თუ ჩვენ მოიპაროს იდეა საწყისი სტრიქონები რომლითაც ჩვენ როგორღაც დაუკავშირონ ეს ყველაფერი ერთად კონცეპტუალურად, და რა მე რომ ამ? ეს არის ჩემი ძალიან ცუდად შედგენილი arrow. მაგრამ ვარაუდობენ, რომ თითოეულ ამ მოცულობით მეხსიერება აღნიშნა, რომ სხვა, და ამ ბიჭს, რომელმაც არ აქვს ძმა მისი უფლება, ვიზიტორების ასეთი arrow. ეს არის, ფაქტობრივად, რასაც დაკავშირებული სიაში. ეს არის ახალი მონაცემები სტრუქტურა, რომელიც საშუალებას გვაძლევს გამოყოფს ბლოკი მეხსიერება, მაშინ კიდევ, მაშინ მეორე, მაშინ კიდევ, ნებისმიერ დროს ჩვენ გვინდა დროს პროგრამა, და ჩვენ გვახსოვს, რომ ისინი ყველა როგორღაც დაკავშირებული მიერ სიტყვასიტყვით chaining მათი ერთად, და გავაკეთეთ, რომ pictorially აქ arrow. მაგრამ კოდი, რა იქნება მექანიზმი მეშვეობით რომელიც თქვენ შეიძლება რაღაცნაირად დააკავშირებს, თითქმის მოსწონს Scratch, ერთი ბლოკი მეორეში ბლოკი? ჩვენ შეგვეძლო გამოიყენოთ მომცეთ, არა? რადგან მართლაც arrow რომ ხდება საწყისი ზედა მარცხენა მოედანზე, ამ ბიჭს აქ ამ ერთი, შეიძლება შეიცავდეს შიგნით ამ მოედანზე არა მხოლოდ რამდენიმე ints, არა მხოლოდ ზოგიერთი char, მაგრამ მე ვფიქრობ რეალურად გამოყოფილი ცოტა ზედმეტი სივრცე ისე, რომ ახლა, თითოეული ჩემი მოცულობით მეხსიერება, მიუხედავად იმისა, რომ ამ აპირებს ეღირება ჩემთვის, ახლა გამოიყურება უფრო მართკუთხა სადაც ერთ მოცულობით მეხსიერება გამოიყენება ნომერი, როგორიც ნომერი 1, და თუ ამ ბიჭს ინახავს რიცხვი 2, ამ სხვა ბლოკი მეხსიერება გამოიყენება arrow, ან უფრო კონკრეტულად, მაჩვენებელი. და ვარაუდობენ მე შესანახად ნომერი 3 ზე აქ მე გამოიყენოს ეს აღვნიშნო, რომ ბიჭს, და ახლა ამ ბიჭს, დავუშვათ მე მხოლოდ მინდა სამი ასეთი მოცულობით მეხსიერება. მე დახაზოთ ხაზი მეშვეობით რომ მითითებით null. არ არსებობს დამატებითი ხასიათი. 

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

ისევე ერთად სიმებიანი, თქვენ უნდა იცოდეს, მისამართი პირველი ჩარ. იგივე გარიგება ამისთვის დაკავშირებული სიები. თქვენ უნდა იცოდეს, მისამართი პირველი ბლოკი მეხსიერება რადგან იქ, შეგიძლიათ მიღწევა ყოველ მეორე. Downside. რა ფასი ჩვენ გადამხდელი ამ versatility მქონე დინამიურად მნიშვნელოვანი მონაცემები სტრუქტურის, რომ თუ ჩვენ ოდესმე გვჭირდება მეტი მეხსიერების, ჯარიმა, უბრალოდ გამოყოფს კიდევ ერთი ბლოკი და დავხატოთ კურსორი საწყისი ძველიდან ახალ კუდი სიის? Yeah. [სტუდენტური] ეს დაახლოებით ორჯერ იმდენი ფართი. იგი იღებს ორჯერ იმდენი სივრცეში, ასე რომ აუცილებლად downside, და ჩვენ ვნახეთ ამ tradeoff ადრე შორის დრო და სივრცე და მოქნილობა იმ შემთხვევაში, როდესაც ახლა, ჩვენ გვჭირდება არა 32 ბიტი თითოეული ამ ნომრებზე. ჩვენ ნამდვილად გვჭირდება 64, 32 ნომერი და 32 კურსორი. მაგრამ hey, მაქვს 2 გბ ოპერატიული მეხსიერება. დამატება სხვა 32 ბიტი აქ და აქ არ ჩანს, რომ დიდი გარიგება. მაგრამ დიდი მონაცემები კომპლექტი, იგი აუცილებლად დასძენს მდე სიტყვასიტყვით ორჯერ იმდენი. რა არის კიდევ ერთი downside არის, ან რა ფუნქცია ჩვენ დავთმობთ, თუ ჩვენ წარმოვადგენთ სიები რამ ერთად უკავშირდება სიაში და არ მასივი? [სტუდენტური] თქვენ არ შეგიძლიათ traverse მას უკან. თქვენ არ შეგიძლიათ traverse მას უკან, ასე რომ თქვენ ტიპის ბრალია თუ თქვენ ფეხით მარცხნიდან მარჯვნივ გამოყენებით ამისთვის მარყუჟი ან ხოლო loop და მაშინ ხვდები, "ოჰ, მე მინდა დავუბრუნდეთ დასაწყისში სიაში." თქვენ არ შეგიძლიათ, რადგან ამ მითითებას მხოლოდ იქ მარცხნიდან მარჯვნივ, როგორც ისრებით მიუთითოს. 

ახლა, თქვენ შეიძლება გახსოვთ დაწყების სიაში სხვა ცვლადი, მაგრამ ეს სირთულის გვახსოვდეს. Array, არ აქვს მნიშვნელობა, თუ რამდენად შორს წახვალ, შეგიძლიათ ყოველთვის მინუსია, მინუს, მინუს, მინუს და წავიდეთ უკან საიდანაც თქვენ მოვიდა. რა არის კიდევ ერთი downside აქ? Yeah. [Inaudible სტუდენტი კითხვა] თქვენ შეიძლება, ასე რომ თქვენ რეალურად მხოლოდ შემოთავაზებული მონაცემები სტრუქტურა მოუწოდა ორმაგად უკავშირდება სია, და მართლაც, თქვენ რომ დაამატოთ კიდევ ერთი მაჩვენებელი თითოეულ ამ მართკუთხედების რომ მიდის სხვა მიმართულებით, Upside, რომლის არის შეგიძლიათ traverse უკან და მეოთხე, downside რომლის არის თქვენ იყენებთ სამჯერ იმდენი მეხსიერება როგორც ჩვენ გამოიყენება და ასევე დასძინა, სირთულის თვალსაზრისით კოდი თქვენ უნდა დაწეროს მიიღოს ეს უფლება. მაგრამ ეს მხოლოდ ყველა ალბათ ძალიან გონივრული tradeoffs, თუ შეცვლის უფრო მნიშვნელოვანია. Yeah. [სტუდენტური] თქვენ ასევე შეგიძლიათ არ აქვს 2D დაკავშირებული სიაში. კარგი, შეგიძლიათ ნამდვილად არ აქვს 2D უკავშირდება სიაში. თქვენ შეიძლება. ეს არ არის თითქმის მარტივი როგორც მასივი. Like მასივი, თქვენ ღია bracket, დახურული ფრჩხილი, ღია bracket, დახურული ფრჩხილი, და თქვენ მიიღეთ რაიმე 2 განზომილებიანი სტრუქტურა. თქვენ შეიძლება განახორციელოს 2 განზომილებიანი უკავშირდება სია თუ add-როგორც თქვენ შემოთავაზებული-მესამე მომცეთ თითოეული ეს ყველაფერი, და თუ ფიქრობთ ამის შესახებ კიდევ ერთი სია მოდის at თქვენ 3D სტილი საწყისი ეკრანის ყველა ჩვენგანისთვის, რომელიც არის კიდევ ერთი ჯაჭვის გარკვეული. ჩვენ შეგვეძლო ამის გაკეთება, მაგრამ არ იმდენად მარტივია, აკრეფით ღია bracket, სკვერი bracket. Yeah. [Inaudible სტუდენტი კითხვა] კარგი, ასე რომ ეს არის რეალური kicker. 

ეს ალგორითმები, რომ ჩვენ pined მეტი, როგორიცაა OH, ორობითი ძებნა, თქვენ შეგიძლიათ მოძებნოთ მასივი ნომრები ფორუმში ან სატელეფონო წიგნი იმდენად უფრო სწრაფად, თუ თქვენ იყენებთ გათიშე და დაიპყროთ და ბინარული ძებნის ალგორითმი, მაგრამ ბინარული ძებნა საჭირო ორი ვარაუდები. ერთი, რომ მონაცემები იყო დახარისხებული. ახლა შეგვიძლია, სავარაუდოდ რომ ეს დახარისხებული, იქნებ ეს არ არის შეშფოთება, მაგრამ ბინარული ძებნის ასევე აიღო რომ თქვენ გქონდათ შემთხვევითი ხელმისაწვდომობის სიაში ნომრები, და array საშუალებას გაძლევთ შემთხვევითი წვდომის და შემთხვევითი წვდომის, ვგულისხმობ თუ თქვენ მოცემული მასივი, რამდენი დრო სჭირდება თქვენ მისაღებად bracket 0? ერთი ოპერაცია, უბრალოდ გამოიყენოთ [0] და თქვენ უფლება არსებობს. რამდენი ნაბიჯები სჭირდება მოხვედრა საიდან 10? ერთი ნაბიჯი, თქვენ უბრალოდ წასვლა [10] და თქვენ იქ. ამის საპირისპიროდ, თუ როგორ იღებთ მე -10 რიცხვი წელს უკავშირდება სიაში? თქვენ უნდა დაიწყოს დასაწყისში რადგან თქვენ მხოლოდ დამახსოვრების დასაწყისში უკავშირდება სია, ისევე, როგორც სიმებიანი ხდება გაიხსენა მისი მისამართია მისი პირველი char, და იპოვოს, რომ მე -10 int ან რომ მე -10 პერსონაჟი სიმებიანი, თქვენ უნდა მოძებნოთ მთელი Damn რამ. 

ისევ და ისევ, ჩვენ არ გადაჭრის ყველა ჩვენი პრობლემები. ჩვენ ახალი პირობა, მაგრამ ეს ნამდვილად არის დამოკიდებული, თუ რა თქვენ ცდილობთ დიზაინი. განხორციელების თვალსაზრისით, ჩვენ შეგვიძლია სესხება იდეა, რომ სტუდენტი სტრუქტურა. სინტაქსი ძალიან ჰგავს, გარდა ახლა, იდეა არის ცოტა უფრო აბსტრაქტული ვიდრე სახლში და სახელი და ID. მაგრამ მე ვთავაზობ, რომ ჩვენ შეგვეძლო მონაცემები სტრუქტურა C რომ ჰქვია კვანძში, როგორც ბოლო სიტყვა on the slide ვარაუდობს, შიგნით კვანძი, და კვანძის მხოლოდ generic კონტეინერის კომპიუტერულ მეცნიერებათა. ეს, როგორც წესი, შედგენილია, როგორც წრის ან კვადრატული ან მართკუთხედი, როგორც ჩვენ გავაკეთეთ. და ამ მონაცემების სტრუქტურას, ჩვენ გვაქვს int, N, ასე რომ ნომერი მინდა შესანახად. მაგრამ რა არის ეს მეორე ხაზი, struct კვანძის * შემდეგი? რატომ არის ეს სწორი, ან რა როლი აქვს ამ რამ პიესა, მიუხედავად იმისა, რომ ეს პატარა cryptic ერთი შეხედვით? Yeah. [Inaudible სტუდენტი საპასუხოდ] სწორედ, ამიტომ * სახის გაფუჭდა, რომ მომცეთ რაიმე სახის. სახელი ამ მაჩვენებელმა არის თვითნებურად შემდეგი, მაგრამ ჩვენ შეეძლო მას არაფერი გვინდა, მაგრამ რას უნდა მომცეთ წერტილი? [სტუდენტური] კიდევ ერთი კვანძის. >> სწორედ ეს მიუთითებს სხვა ასეთი კვანძის. 

ახლა, ეს არის ერთგვარი ცნობისმოყვარეობა C. შეგახსენებთ, რომ C წაკითხვის მიერ შემდგენელი ყველაზე ქვედა, მარცხნიდან მარჯვნივ, რაც იმას ნიშნავს, თუ-ეს არის პატარა განსხვავდება, რაც ჩვენ გავაკეთეთ ერთად სტუდენტი. როდესაც ჩვენ განსაზღვრული სტუდენტი, ჩვენ რეალურად არ დააყენა სიტყვა არსებობს. ეს უბრალოდ განაცხადა typedef. მაშინ ჩვენ გვქონდა int id, string სახელი, string სახლი, და მაშინ სტუდენტი ბოლოში struct. ეს დეკლარაცია ცოტა განსხვავებული იმიტომ, ერთხელ, C კომპილატორი არის პატარა მუნჯი. ეს მხოლოდ აპირებს წაიკითხა ზედა ქვედა, ასე რომ, თუ იგი აღწევს მე -2 ხაზი აქ აქ შემდეგი ცხადდება და მას ხედავს, OH, აქ ცვლადში შემდეგი. ეს მომცეთ struct კვანძში. შემდგენელი აპირებს გააცნობიეროს, რა არის struct კვანძის? მე არასდროს მსმენია ამ რამ ადრე, რადგან სიტყვა კვანძის შეიძლება არ სხვაგვარად გამოჩნდება სანამ ბოლოში, ასე რომ, ამ redundancy. თქვენ უნდა ვთქვა struct კვანძის აქ, რომელიც შეგიძლიათ შემდეგ shorten მოგვიანებით წყალობით typedef ქვემოთ აქ, მაგრამ ეს იმიტომ ჩვენ referencing სტრუქტურა თავად შიგნით სტრუქტურა. სწორედ ერთ GOTCHA არსებობს. 

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

C არის ბევრად უფრო გართობა როცა ეს მოქმედებდა გარეთ. ვის სიტყვასიტყვით მინდა იყოს პირველი? Okay, მოდის up. თქვენ ხართ პირველი. ვინ მინდა იყოს 9? Okay, 9. როგორ დაახლოებით 9? 17? პატარა clique აქ. 22 და 26 წლის, რომ წინა რიგის. და მაშინ როგორ შესახებ ვინმე იქ მიმდინარეობს მიუთითა. თქვენ ხართ 34. Okay, 34, მოდის up. პირველი არის იქ. Okay, ოთხივე თქვენგანს ბიჭები. არიან და არ ვამბობთ, 9? ვინ არის ჩვენი 9? ვინ ნამდვილად სურს იყოს 9? ყველა უფლება ერთი, იყოს 9. Here We Go. 34, ჩვენ შეგხვდებით იქ. პირველი ნაწილი არის მიიღოს თქუენგან ჰგავს, რომ. 26, 22, 17, კარგი. თუ თქვენ დავდგეთ off იმ მხარეს, რადგან ჩვენ ვაპირებთ malloc თქვენ მომენტში. 

კარგი, კარგი. Okay, კარგი, მოდით ვკითხოთ რამდენიმე კითხვები აქ. და ფაქტობრივად, რა გქვია? >> Anita. ანიტა, okay, მოდის, მეტი აქ. Anita აპირებს დაგვეხმარება სახის გადაჭრას ერთი საკმაოდ მარტივი კითხვა პირველი, რომელიც როგორ მოვძებნოთ თუ არა მნიშვნელობა არის სიაში? ახლა, რომ პირველი, წარმოდგენილია აქ ლუკასი არის ცოტა განსხვავებული და ამიტომ მისი ნაჭერი ქაღალდი განზრახ sideways რადგან ეს არ საკმაოდ როგორც მაღალი და არ იღებს, როგორც ბევრი ბიტი, მიუხედავად იმისა, რომ ტექნიკურად მას იგივე ზომის ქაღალდი მხოლოდ გარდამავალია. მაგრამ ის ცოტა განსხვავებული, რომ ის მხოლოდ 32 ბიტი ამისთვის მაჩვენებელი, და ყველა ეს ბიჭები არიან 64 ბიტი, ნახევარი, რომელიც ნომერი, ნახევარი, რომელიც მაჩვენებელმა. მაგრამ მაჩვენებელი არ არის გამოსახული, ასე რომ, თუ თქვენ ბიჭები შეეძლო გარკვეულწილად უხერხულად გამოიყენოთ თქვენი მარცხენა ხელის აღვნიშნო დროს პირი შემდეგი თქვენ. და თქვენ ნომერი 34. რა არის შენი სახელი? Ari. Ari, ისე რეალურად, გამართავს ქაღალდის თქვენს მარჯვენა ხელი, და მარცხენა ხელის მიდის სწორი ქვემოთ. თქვენ წარმოადგენთ null მარცხენა. 

ახლა ჩვენი ადამიანის სურათს ძალიან თანმიმდევრული. ეს არის რეალურად როგორ პოინტერები მუშაობა. და თუ შეგიძლიათ scrunch ცოტა ამ გზით, ასე რომ მე არ ვარ თქვენი გზა. Anita აქ, იპოვეთ ჩემთვის ნომერი 22, მაგრამ ვივარაუდოთ შეზღუდვა არა ადამიანები ჩატარების up ცალი ქაღალდის, მაგრამ ეს სია, და თქვენ მხოლოდ ლუკას დავიწყოთ იმიტომ, რომ ის არის სიტყვასიტყვით პირველი მაჩვენებელი. დავუშვათ, რომ თავად არიან მაჩვენებელი, და ასე რომ თქვენ ძალიან აქვს უნარი ადგილამდე რაღაც. რატომ არ იწყება მიუთითებს ზუსტად რა Lucas არის მიუთითებს? კარგი, და ნება მომეცით მიიღოს ამ გარეთ მეტი აქ. მხოლოდ გულისთვის დისკუსია, ნება მომეცით დახევის up ცარიელი გვერდი აქ. როგორ მართლწერის თქვენი სახელი? >> Anita. Okay, ანიტა. ვთქვათ კვანძის * anita = ლუკასი. ასევე, ჩვენ არ უნდა მოვუწოდებთ თქვენ ლუკასი. ჩვენ უნდა მოვუწოდებთ თქვენ პირველი. რატომ არის ეს რეალურად შეესაბამება რეალობას? ერთი, პირველი უკვე არსებობს. პირველი გამოყოფილი სავარაუდოდ სადღაც აქ. Node * პირველი და ეს გამოყოფილი სიაში რატომღაც. არ ვიცი როგორ მოხდა, რომ. რაც მოხდა ადრე კლასის დაიწყო. ეს დაკავშირებულია სია ადამიანისა შეიქმნა. და ახლა ამ დროისთვის ამბავი ეს ყველაფერი ხდება Facebook სავარაუდოდ მოგვიანებით- ამ დროისთვის ამბავი, ანიტა უკვე ინიციალიზაცია იყოს თანაბარი პირველ, რაც არ ნიშნავს, რომ ანიტა ქულა Lucas. უფრო მეტიც, მან ქულა, თუ რას ქულა რადგან იგივე მისამართზე რომ შიგნით Lucas-ს 32 ბიტი - 1, 2, 3 - არის ასევე შიგნით ანიტა ს 32 ბიტი - 1, 2, 3. 

ახლა იპოვოს 22. როგორ წავიდეთ შესახებ ამით? რა არის ეს? >> წერტილი რასაც. წერტილი რასაც, ასე წავიდეთ წინ და იმოქმედოს ის, როგორც საუკეთესო შეგიძლიათ აქ. კარგი, კარგი, და ახლა თქვენ მიუთითებს რა არის თქვენი სახელი 22? რამონ. >> Ramon, ასე რამონ მართავს up 22. თქვენ ახლა კეთდება ქვითარი. ამჯამად რამონ == 22, და თუ ასეა, მაგალითად, ჩვენ შეგვიძლია იქნება TRUE. ნება მომეცით-ხოლო ეს ბიჭები დგანან აქ გარკვეულწილად უხერხულად- ნება მომეცით რაღაც სწრაფად მოსწონს bool იპოვოს. მე ვაპირებ წავიდეთ წინ და ვთქვათ (კვანძის * სიაში, int N). მე უფლებას უკან თქვენ ბიჭები. მე უბრალოდ უნდა დაეწერა რაღაც კოდი. და ახლა მე ვაპირებ წავიდეთ წინ და ამის გაკეთება, node * anita = სიაში. და მე ვაპირებ წავიდეთ წინ და აცხადებენ, ხოლო (anita = NULL). 

მეტაფორა აქ დღითიდღე პატარა გადაჭიმული, მაგრამ (anita = NULL), რა გსურთ? მჭირდება რამდენიმე გზა referencing მთელი რიცხვი, რომ ანიტა არის მიუთითებს. წარსულში, როდესაც ჩვენ გვქონდა სტრუქტურებში, რომლებიც კვანძში არის, ჩვენ გამოიყენება dot ნოტაცია და ჩვენ ვიტყოდი რაღაც anita.n, მაგრამ პრობლემა აქ ის არის, რომ ანიტა არ არის struct თავისთავად. რა არის იგი? შიზი მაჩვენებელი, ასე ნამდვილად, თუ ჩვენ გვინდა გამოვიყენოთ ეს dot ნოტაცია- და ამ აპირებს გამოიყურებოდეს განზრახ პატარა cryptic- ჩვენ უნდა გავაკეთოთ მსგავსი რამ წასვლა რასაც ანიტა მარცხენა ხელის მიუთითებს და შემდეგ კიდევ სფეროში მოუწოდა n. ანიტა არის კურსორი, მაგრამ რა არის * anita? რას პოულობენ, როდესაც მიდიხარ რა ანიტა არის მიუთითებს? Struct, კვანძში, და კვანძის, გაწვევას, აქვს სფეროში მოუწოდა N იმიტომ, რომ მან, გავიხსენოთ, ამ 2 სფეროებში, შემდეგი და n, რომ დავინახეთ მომენტში წინ სწორედ აქ. 

რეალურად იმიტაცია ამ კოდის, ჩვენ შეგვიძლია ამის გაკეთება და ვთქვათ თუ ((* anita). N == N), n, რომ ვეძებ. გაითვალისწინეთ, რომ ფუნქცია იყო მიღებული ხმების მე აღელვებთ. მაშინ შემიძლია წავიდეთ წინ და რაღაც მოსწონს დაბრუნების ჭეშმარიტი. სხვაგან, თუ ეს ასე არ არის საქმე, რა გსურთ? როგორ შემიძლია თარგმნა ენაზე კოდი რა ანიტა გააკეთა ინტუიციურად გავლით სიაში? რა უნდა გავაკეთოთ, აქ სიმულაცია ანიტა აღების, რომ ნაბიჯი მარცხნივ, რომ ნაბიჯი მარცხნივ? [Inaudible სტუდენტი საპასუხოდ] >> რა არის რომ? [Inaudible სტუდენტი საპასუხოდ] კარგი, არ არის ცუდი იდეა, მაგრამ წარსულში, როდესაც ჩვენ გავაკეთეთ, ჩვენ გავაკეთეთ anita + + იმიტომ, რომ დაამატოთ ნომერი 1 დან ანიტა, რომელმაც შესაძლოა ტიპიურად აღვნიშნო მომდევნო პირი, ისევე როგორც Ramon, ან პირის შემდეგი თქმით, თუ მომდევნო მას პირი ქვემოთ ხაზი. მაგრამ ეს არ არის საკმაოდ კარგი აქ იმიტომ რას რამ ჰგავს მეხსიერებაში? არა. ჩვენ უნდა გამორთოთ, რომ. როგორც ჩანს ეს მეხსიერებაში და მიუხედავად იმისა, რომ მე შედგენილი 1 და 2 და 3 ახლოს ერთმანეთთან, თუ ჩვენ ნამდვილად სიმულაცია ამ-შეგიძლიათ ბიჭები, მიუხედავად მიუთითებს იგივე ადამიანები, შეიძლება ზოგიერთ თქვენგანს მიიღოს შემთხვევითი ნაბიჯი უკან, ზოგიერთი თქვენგანი შემთხვევითი წინგადადგმული ნაბიჯი? 

ეს სასადილო ჯერ კიდევ დაკავშირებული სიაში, მაგრამ ეს ბიჭები შეიძლება სადმე მეხსიერება, ასე anita + + არ იმუშავებს, თუ რატომ? რა დროს საიდან anita + +? ვინ იცის. ეს რაღაც სხვა მნიშვნელობა, რომელიც მხოლოდ ასე ხდება უნდა interposed შორის ყველა ამ კვანძების მიერ შანსი, რადგან ჩვენ არ იყენებს მასივი. ჩვენ გამოყოფილი თითოეული ამ კვანძების ინდივიდუალურად. Okay, თუ ბიჭები შეიძლება გაწმენდა თქუენგან უკან მდე. ნება მომეცით ინიციატივით კი, ნაცვლად anita + +, ჩვენ ნაცვლად გააკეთოს anita იღებს- ასევე, რატომ არ გვაქვს წასვლა რასაც ანიტა არის მიუთითებს და მერე გავაკეთოთ. შემდეგი? სხვა სიტყვებით, ჩვენ წასვლა Ramon, რომელიც ჩატარების ნომერი 22, და შემდეგ. შემდეგი არის თითქოს ანიტა იქნება კოპირება მისი მარცხენა ხელის მაჩვენებელი. მაგრამ მან წასვლა არ შემდგომი ვიდრე რამონ რადგან აღმოვაჩინეთ 22. მაგრამ ეს იქნება იდეა. ახლა, ეს არის ღვთის საშინელი ხმაური. პატიოსნად, ვერავინ გახსოვთ ეს სინტაქსი და ა.შ. საბედნიეროდ, სინამდვილეში პატარა მიზანმიმართული-oh, თქვენ არ რეალურად ვხედავ რა დავწერე. ეს იქნება უფრო მყარი, თუ თქვენ შეიძლება. Voila! 

კულისებში, მე პრობლემის გადაჭრის ამ გზით. ანიტა, მიიღოს ეს ნაბიჯი მარცხნივ, პირველი, ჩვენ გადადით მისამართზე, რომელიც ანიტა არის მიუთითებს და სადაც იგი იპოვის არა მხოლოდ N, რომელიც ჩვენ მხოლოდ შემოწმდება შედარებით ის გულისთვის, მაგრამ თქვენ ასევე მოვძებნოთ შემდეგი - ამ შემთხვევაში, რამონ მარცხენა მხრივ მიუთითებს შემდეგი კვანძის სიაში. მაგრამ ეს ღვთის საშინელი ხმაური, რომლის მე მოხსენიებული ადრე, მაგრამ აღმოჩნდება, C საშუალებას გვაძლევს გავამარტივოთ ამ. ნაცვლად წერა (* anita), ჩვენ შეგვიძლია ნაცვლად მხოლოდ წერენ anita-> n, და ეს ზუსტად იმავეს ფუნქციურად, მაგრამ ბევრად უფრო ინტუიტიური, და ეს ბევრად უფრო შეესაბამება სურათზე რომ ჩვენ ხატვის მთელი ამ ხნის გამოყენებით ისრებით. 

და ბოლოს, რას უნდა გავაკეთოთ დასასრულს ამ პროგრამის? თუმცა ერთი ხაზი კოდი დარჩენილი. დაბრუნება რა? ყალბი, რადგან თუ არ მივიღებთ მთელ ხოლო loop და ანიტა არის, ფაქტობრივად, null, რაც იმას ნიშნავს, მან ყველა გზა ბოლომდე სია სადაც ის მიუთითებს რა არის თქვენი სახელი კვლავ? Ari. >> Ari მარცხენა მხრივ, რომელიც null. ანიტა არის null, და ვხვდები, თქვენ მხოლოდ ვდგავართ აქ უხერხულად წელს ჰაერშია გამოკიდებული რადგან მე ვაპირებ off on მონოლოგი აქ, მაგრამ ჩვენ ჩართვას კიდევ ერთხელ რაღაც მომენტში. ანიტა არის null იმ მომენტში ამბავი, ასე ხოლო loop წყვეტს, და ჩვენ გვაქვს დასაბრუნებელი ცრუ, რადგან თუ მან შეიძინა ყველა გზა Ari ს null მაჩვენებელი მაშინ არ იყო ნომერი, რომელიც მან ვეძებოთ სიაში. ჩვენ შეგვიძლია გაწმენდა ამ up ძალიან, მაგრამ ეს არის საკმაოდ კარგი განხორციელების შემდეგ საქართველოს გასვლის ფუნქცია, იპოვოს ფუნქცია უკავშირდება სიაში. ეს ჯერ კიდევ ხაზოვანი ძებნა, მაგრამ არ იმდენად მარტივია, + + კურსორი ან + + მე ცვლადი რადგან ახლა ჩვენ ვერ ვხვდები, სადაც თითოეულ ამ კვანძების არიან მეხსიერებაში. ჩვენ უნდა დაიცვას სიტყვასიტყვით ბილიკი breadcrumbs ან, უფრო კონკრეტულად, პოინტერები, მიიღოს ერთი კვანძის სხვა. 

ახლა მოდით შევეცადოთ კიდევ ერთი. ანიტა, გსურთ დავბრუნდებით აქ? რატომ არ ვართ წავიდეთ წინ და გამოყოფს ერთ სხვა პირს აუდიტორიის? Malloc-რა გქვია? >> რებეკა. რებეკა. რებეკა უკვე malloced საწყისი აუდიტორიას, და ქალი არის შენახვის ნომერი 55. და მიზანი ხელთ არის არის ანიტა ჩასასმელად რებეკა შევიდა უკავშირდება სია აქ თავის შესაბამის ადგილზე. Come on მეტი აქ ერთი მომენტი. მე არ კეთდება მსგავსი რამ. მე არ კეთდება კვანძის *. და რაც თქვენი სახელი კვლავ? რებეკა. >> რებეკა, okay. რებეკა იღებს malloc (sizeof (კვანძის)). ისევე, როგორც ჩვენ გამოყოფილი რამ, როგორიცაა სტუდენტებისა და whatnot წარსულში, ჩვენ გვჭირდება ზომის კვანძი, ამიტომ ახლა რებეკა არის მიუთითებს რა? რებეკა აქვს ორი სფეროებში შიგნით მისი, რომელთაგან ერთი 55. მოდით რა, რებეკა-> = 55. მაგრამ შემდეგ რებეკა-> მომავალი უნდა მსგავსი ახლავე, თავის მხრივ არის ერთგვარი ვინ იცის? ეს მიუთითებს ზოგიერთი ნაგვის ღირებულება, ასე რომ რატომ არ კარგი ღონისძიება ჩვენ მინიმუმ ამის გაკეთება ისე, რომ მარცხენა ხელის არის მის მხარეს. ახლა ანიტა, მას აქედან. თქვენ გაქვთ რებეკა რომელმაც გამოიყო. წავიდეთ წინ და იპოვოს, სადაც ჩვენ უნდა დააყენოს რებეკა. კარგი, ძალიან კარგი. Okay, კარგი, და ახლა ჩვენ თქვენ გვჭირდებით, რომ უზრუნველყოს ცოტა მიმართულებით, ასე თქვენ მიაღწია Ari. მისი მარცხენა ხელი null, მაგრამ რებეკა ნათლად ეკუთვნის უფლება, ასე როგორ უნდა უნდა შეცვალოს ამ ბმის სია რათა ჩადეთ რებეკა შევიდა შესაბამის ადგილზე? თუ შეიძლება სიტყვასიტყვით გადავა ხალხის ხელში მარცხენა გარშემო როგორც საჭიროა, ჩვენ დაფიქსირება პრობლემა რომ გზა. Okay, კარგი, და იმავდროულად, რებეკა მარცხენა ხელით არის მისი მხრიდან. 

ეს იყო ძალიან ადვილი. მოდით ვეცადოთ გამოყოფის-we're თითქმის გაკეთდეს, 20. Okay, მოდის up. 20 გამოეყო, ნება მომეცით, წავიდეთ წინ და ვთქვათ ერთხელ აქ ჩვენ უბრალოდ გაკეთდეს კვანძის * saad. ჩვენ გვყავს malloc (sizeof (კვანძის)). ჩვენ მაშინ იგივე ზუსტი სინტაქსი როგორც გავაკეთეთ ადრე, 20, და მე გავაკეთებ შემდეგი = NULL, და ახლა ეს მდე ანიტა ჩასასმელად თქვენ შევიდა უკავშირდება სია, თუ შეუძლიათ, რომ ზუსტად იგივე როლი. შეასრულოს. Okay, კარგი. ახლა ყურადღებით იფიქრეთ თქვენს წინაშე დაიწყება მოძრავი მარცხენა ხელში გარშემო. თქვენ ბევრად მიიღო საუკეთესო უხერხულ როლი დღეს. ვისი ხელით უნდა გადავიდნენ პირველი? Okay, დაველოდოთ, მე მოსმენის გარკვეული არ იყო. თუ FOLKS რომ თავაზიანად მინდა დაეხმარება გადაჭრას უხერხულ მდგომარეობაში აქ. ვისი მარცხენა ხელის უნდა განახლდეს პირველი ალბათ? Yeah. [სტუდენტური] Saad-ს. Okay, Saad-ს, თუ რატომ, თუმცა? [Inaudible სტუდენტი საპასუხოდ] კარგი, რადგან თუ ჩვენ გადაადგილება-რა გქვია? >> მარშალის. მარშალის, თუ ჩვენ გადაადგილება თავისი ხელით პირველ ქვემოთ null, ახლა ჩვენ სიტყვასიტყვით ობოლი ოთხი ადამიანი ამ სიაში რადგან იგი ერთადერთი მიუთითებს რამონ და ყველას მარცხენა ასე განახლებას რომ კურსორი პირველი იყო ცუდი. მოდით გაუქმება, რომ. კარგი, ახლა წავიდეთ წინ და გადატანა შესაბამისი მარცხენა მიუთითებს რამონ. ეს გრძნობს პატარა გადაჭარბებული. ახლა ორი ადამიანი მიუთითებს Ramon, მაგრამ ეს ჯარიმა რადგან ახლა როგორ სხვაგან უნდა განახლდეს სიაში? რა მხრივ უნდა გადავიდეს? შესანიშნავი, ახლა ჩვენ დავკარგეთ ნებისმიერი მეხსიერების? არა, იმდენად კარგი, ვნახოთ, შევძლებთ თუ არა დაარღვიოს ამ კიდევ ერთხელ. 

Mallocing ერთი ბოლო დროს, ნომერი 5. ყველა გზა უკან, მოდის ქვემოთ. ძალიან საინტერესო. [ტაში] რა არის შენი სახელი? >> რონ. რონ, okay, თქვენ malloced როგორც ნომერი 5. ჩვენ უბრალოდ დახვრიტეს კოდი, რომელიც თითქმის იდენტურია ამ მხოლოდ სხვა სახელი. შესანიშნავი. ახლა, ანიტა, წარმატებას გისურვებთ ჩასმა ხმების 5 შევიდა სიაში ახლა. კარგი, და? შესანიშნავი, ასე რომ, ეს ნამდვილად მესამე სამი სულ შემთხვევებში. ჩვენ პირველი ჰქონდა ვიღაცას დასასრულს, რებეკა. ჩვენ მაშინ ჰქონდა ვიღაცას შუა. ახლა ჩვენ გვაქვს ვინმე დასაწყისში, და ამ მაგალითად, ჩვენ ახლა განაახლოთ Lucas პირველად რადგან პირველ ელემენტს სიაში ახლა აღვნიშნო ახალ კვანძში, ვინც, თავის მხრივ, არის მიუთითებს კვანძის ნომერი 9. 

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

ავიღოთ რამ უფრო დახვეწილი მიმართულება მაინც. ჩვენ ახლა აქვს ცნება დაკავშირებულია სიაში. ჩვენ ასევე გვაქვს-წყალობით წინადადება თავში იქ-ორმაგად უკავშირდება სია, რომელიც გამოიყურება თითქმის იგივე, მაგრამ ახლა ჩვენ ორი პოინტერები შიგნით struct ერთის ნაცვლად, და ჩვენ შეგვიძლია ალბათ მოვუწოდებთ მათ მითითებას წინა და შემდეგი ან მარცხნივ ან მარჯვნივ, მაგრამ ჩვენ, ფაქტობრივად, გვჭირდება ორი მათგანი. კოდი იქნებოდა ცოტა მეტი ჩართული. Anita ექნებოდა უფრო მეტი მუშაობა აქ სცენაზე. მაგრამ ჩვენ ნამდვილად განახორციელოს ისეთი სტრუქტურა. თვალსაზრისით გაშვებული დრო, თუმცა, რა იქნება გაშვებული დრო ამისთვის ანიტა მოძიების ნომერი N ში დაუკავშირა სია არის? ჯერ კიდევ დიდი O of n, ამიტომ არ უკეთესად ხაზოვანი ძებნა. ჩვენ არ შეგვიძლია გავაკეთოთ ორობითი ძებნა, თუმცა, კიდევ ერთხელ. რატომ იყო, რომ საქმე? თქვენ არ შეგიძლიათ ხტომა გარშემო. მიუხედავად იმისა, რომ ჩვენ აშკარად ყველა ადამიანისა სცენაზე, და ანიტა შეეძლო eyeballed იგი და თქვა: "აქ არის შუა სია" იგი აღარ იციან, რომ თუ ის იყო კომპიუტერული პროგრამა რადგან ერთადერთი, რაც მას უნდა latch შესახებ, რომ დაწყების სცენარი იყო ლუკას, რომელიც იყო პირველი მაჩვენებელი. მან აუცილებლად უნდა დაიცვას ეს კავშირები, დათვლის მიმავალი სანამ ნაპოვნია უხეშად შუა, და მაშინაც, იგი არ აპირებს იცით, როდესაც მან მიაღწია შუა მოხდება მისი მიდის ყველა გზა ბოლომდე უნდა გაერკვნენ, თუ რამდენი არსებობს, მაშინ backtracks, და რომ ძალიან იქნება რთული, თუ არ გქონდათ ორმაგად უკავშირდება სიაში გარკვეული. 

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

ახლა რაიმე სცენარი მოვიდა იბადება სადაც მქონე დასტის მონაცემები სტრუქტურა, სადაც თქვენ, რომ საკუთრების უკანასკნელი წელს, პირველი გარეთ, ფაქტობრივად აიძულებს? ის არის, რომ კარგია? ის არის, რომ ცუდი რამ? ეს ნამდვილად ცუდი რამ თუ უჯრები არ იყო ყველა იდენტური და ისინი ყველა სპეციალური სხვადასხვა ფერის ან whatnot, და ფერი გნებავთ არის ყველა გზა ბოლოში. რა თქმა უნდა, თქვენ ვერ იღებს გარეშე დიდი ძალისხმევა. თქვენ უნდა დაიწყოს ზემოდან და მუშაობა თქვენი გზა down. ანალოგიურად, რა თუ იყო ერთი ამ გულშემატკივართა ბიჭები ვინც ელოდება Up All Night ცდილობს iPhone და ხაზების up ადგილზე ასე? არ იქნება ლამაზი თუ Apple მაღაზია იყო დასტის მონაცემები სტრუქტურა? YAY? Nay? ეს მხოლოდ კარგი ადამიანები, რომლებიც გამოჩნდება უკანასკნელ შესაძლო წუთი და შემდეგ მიიღოს plucked off რიგიდან. და რეალურად, ის ფაქტი, რომ მე ასე ვაპირებთ ამბობენ მდგომ ფაქტიურად შეესაბამება რასაც ჩვენ მოვუწოდებთ ამ სახის მონაცემები სტრუქტურის, ერთი რეალურად სადაც წესრიგი არ აქვს მნიშვნელობა, და გსურთ პირველი ერთი იქნება პირველი გარეთ თუ მხოლოდ გულისთვის ადამიანის სამართლიანობისა. ჩვენ ზოგადად მოვუწოდებთ, რომ რიგი მონაცემები სტრუქტურა. 

თურმე გარდა უკავშირდება სიები, ჩვენ შეგვიძლია დავიწყოთ გამოყენებით ამ საერთო ძირითადი იდეები და დაიწყოს შეიქმნას ახალი და სხვადასხვა სახის იმ პრობლემების გადასაჭრელად. მაგალითად, იმ შემთხვევაში, დასტის, შეიძლება წარმოადგენდეს დასტის გამოყენებით მონაცემების სტრუქტურას ასე, მინდა შესთავაზოს. ამ შემთხვევაში, მე განაცხადა struct, და მე განაცხადა შიგნით ამ სტრუქტურის არის მასივი ნომრები და შემდეგ ცვლადში ზომა, და ვაპირებ მოვუწოდო ამ რამ Stack. ახლა, რატომ ამ რეალურად მუშაობს? იმ შემთხვევაში, დასტის, მე ვერ მიაპყროს ამ ეფექტურად ეკრანზე როგორც მასივი. აქ არის ჩემი Stack. ეს ის ჩემი ნომრები. და ჩვენ დავხატოთ მათ ამ, ამ, ამ, ამ, ამ. და მერე გარკვეული სხვა მონაცემები წევრი აქ, რომელსაც ზომა, ასე რომ, ეს ზომა, და ეს ნომრები, და ერთობლივად, მთელი iPad აქ წარმოადგენს ერთ დასტის სტრუქტურა. ახლა, ცხადია, ზომა სავარაუდოდ რაღაც უნდა იყოს ინიციალიზაცია 0, და რაც შიგნით მასივი ნომრები თავდაპირველად როდესაც მე პირველად გამოყოფს მასივი? Garbage. ვინ იცის? და ეს ფაქტობრივად არ აქვს. არ აქვს მნიშვნელობა, თუ ეს 1, 2, 3, 4, 5, სრულიად შემთხვევით ცუდი იღბალი შენახული ჩემი სტრუქტურა, რადგან, თუ ვიცი, რომ ზომის დასტის არის 0, მაშინ მე ვიცი, პროგრამულად, არ შევხედოთ ნებისმიერი ელემენტების მასივი. არ აქვს მნიშვნელობა, რა იქ. ნუ შეხედავს მათ, როგორც იქნებოდა გავლენა საქართველოს ზომის 0. 

მაგრამ ვარაუდობენ, ახლა წავიდეთ წინ და ჩადეთ რამე შევიდა Stack. მინდა ჩადეთ ნომერი 5, ამიტომ დააყენა ნომერი 5 აქ, და მერე რა ჩასახშობად აქ? ახლა მინდა რეალურად ჩასახშობად 1 ამისთვის ზომა, და ახლა დასტის არის ზომა 1. რა მოხდება, თუ წავიდეთ წინ და ჩადეთ ნომერი, ვთქვათ, 7 შემდეგი? ეს მაშინ იღებს განახლებული 2, და შემდეგ ჩვენ გავაკეთებთ 9, და მაშინ ეს იღებს განახლებული 3. მაგრამ საინტერესო ფუნქცია, ახლა ამ დასტის არის, რომ მე უნდა ამოიღონ, რომელიც ელემენტს თუ მინდა პოპ რაღაც გამორთვა დასტის, ასე ვთქვათ? 9 იქნება პირველი, რაც წასვლა. როგორ უნდა სურათზე შეიცვალოს თუ მინდა პოპ ელემენტს off დასტის, ჰგავს უჯრა წელს Mather? Yeah. >> [სტუდენტური] Set ზომა, რათა 2. სწორედ ყველა გავაკეთო არის მითითებული ზომა: 2, და რა ვუყოთ მასივი? მე არ მაქვს არაფრის. შემეძლო, უბრალოდ უნდა იყოს anal, დაუსვან 0 იქ ან -1 ან რაიმე ნიშნავდეს რომ ეს არ არის legit ღირებულება, მაგრამ ეს არაფერს ნიშნავს, რადგან შემიძლია ჩაწერას გარეთ მასივი თავად რამდენი ხანი არის ასე რომ ვიცი, მხოლოდ შევხედოთ პირველი ორი ელემენტები ამ მასივი. ახლა, თუ წავიდე და დაამატოთ ხმების 8 ამ მასივი, როგორ სურათზე შეცვლის შემდეგ? ეს ხდება 8, და ეს ხდება 3. მე ჭრის რამდენიმე კუთხეების აქ. ახლა ჩვენ გვაქვს 5, 7, 8, და ჩვენ თავში ზომა 3. ეს არის საკმაოდ მარტივი განხორციელება, მაგრამ როდესაც ჩვენ ვაპირებთ ვნანობ ამ დიზაინის გადაწყვეტილება? როდის რამ დაიწყება წასვლა ძალიან, ძალიან არასწორი? Yeah. [Inaudible სტუდენტი საპასუხოდ] როდესაც გსურთ უკან და კიდევ პირველი ელემენტს თქვენ დააყენა სისტემაში 

თურმე აქ მიუხედავად იმისა დასტის არის მასივი ქვეშ hood, ამ მონაცემების სტრუქტურები დავიწყეთ ლაპარაკი ასევე საყოველთაოდ ცნობილია, როგორც აბსტრაქტული მონაცემები სტრუქტურების რომლითაც როგორ ისინი განხორციელდა სრულიად გარდა წერტილი. მონაცემები სტრუქტურის მსგავსად დასტის უნდა დაამატოთ მხარდაჭერა ოპერაციების მოსწონს ბიძგი, რომელიც უბიძგებს უჯრა გადატანა დასტის, და საესტრადო, რომელიც შლის ელემენტს საწყისი დასტის, და ამით ყველაფერი მთავრდება. თუ იყო ჩამოტვირთოთ სხვისი კოდი რომელმაც უკვე განახორციელა ამ რამ მოუწოდა დასტის, რომ პირი იქნებოდა დაწერილი მხოლოდ ორი ფუნქცია თქვენთვის, დააყენებს და საესტრადო, რომლის ერთადერთი მიზანი ცხოვრებაში იქნებოდა გავაკეთოთ ზუსტად რომ. თქვენ ან მას ვინც განახორციელა, რომ პროგრამა იქნებოდა მთლიანად ერთი გადასაწყვეტია როგორ განახორციელებენ სემანტიკა უბიძგებს და popping ქვეშ hood ან ფუნქციონალური ზრდის და popping. და მე მივიღე გარკვეულწილად shortsighted გადაწყვეტილება აქ განხორციელებით ჩემი დასტის ამ მარტივი მონაცემთა სტრუქტურა რატომ? როდის ამ მონაცემთა სტრუქტურა შესვენების? რა წერტილი უნდა დაბრუნდეს შეცდომა, როდესაც მომხმარებლის მოუწოდებს ბიძგი, მაგალითად? [სტუდენტური] თუ არ მეტი სივრცე. სწორედ, თუ არ მეტი სივრცე, თუ მე გადააჭარბა მოცულობა, რაც ყველა caps რადგან იგი ვარაუდობს, რომ ეს რაღაც გლობალური მუდმივი. კარგად, მაშინ მე უბრალოდ აპირებს უნდა ვთქვა, "ბოდიში, მე ვერ დააყენებს სხვა ღირებულება გადატანა დასტის, "ჰგავს, რომელიც Mather. 

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

მაგრამ რა გვაქვს მოვიდა ვაფასებთ როდესაც საქმე კოლექტორები და მოძრავი რამ გარშემო? სწორედ სახის ნარჩენები თქვენი დრო, არა? რატომ უნდა იყოს ასე anal როგორც აქვს პირველი პირი დაწყების ხაზს ფიზიკურად დაწყების ბლოკი მეხსიერება? სწორედ სრულიად არასაჭირო. რატომ? რა შეიძლება მე უბრალოდ გვახსოვდეს ნაცვლად? >> [Inaudible სტუდენტი საპასუხოდ] სწორედ, მე ვერ უბრალოდ გვახსოვდეს, ამ დამატებითი მონაცემები წევრი ხელმძღვანელი რომ ახლა ხელმძღვანელი სიაში აღარ არის 0, რომელიც იყო მომენტი წინ. ახლა კი რეალურად ხმების 1. ამ გზით, მივიღებ უმნიშვნელო ოპტიმიზაცია. მხოლოდ იმიტომ, რომ მე დე რიგშია ვინმე ხაზს დაწყების ხაზს Apple მაღაზია არ ნიშნავს, ყველას აქვს გადაეტანა, რომელიც გაწვევას არის წრფივი ოპერაცია. შემიძლია ნაცვლად დახარჯოს მუდმივი ახლა მხოლოდ და მივაღწიოთ მაშინ ბევრად უფრო სწრაფად საპასუხოდ. მაგრამ ფასი მე გადამხდელი არის რა მოსაპოვებლად, რომ დამატებით შესრულება და არ მქონე გადაეტანა ყველას? Yeah. >> [Inaudible სტუდენტი საპასუხოდ] შეგიძლიათ დაამატოთ მეტი ადამიანი, ისევე, რომ პრობლემა არის orthogonal ის ფაქტი, რომ ჩვენ არ გადავიდა გარშემო. ეს ჯერ კიდევ მასივი, ასე თუ არა ჩვენ გადაეტანა ყველას თუ არა- OH, ვხედავ, რაც თქვენ ნიშნავს, okay. სინამდვილეში, მე ვეთანხმები თუ რას ამბობდა, რომ ის თითქმის თითქოს ჩვენ ახლა არასდროს გამოიყენოთ დაწყება ამ მასივი უქმნით რადგან თუ მოვხსნა 5, მერე ამოიღონ 7. მაგრამ მე მხოლოდ დააყენა ხალხის უფლება. 

ეს იგრძნობა მე გაყვანაა სივრცეში, და საბოლოოდ ჩემი მდგომ disintegrates შევიდა არაფერი ყველა, ამიტომ ვერ უბრალოდ ადამიანი wraparound, და ჩვენ შეგვიძლია ვიფიქროთ, ეს მასივი მართლაც როგორც გარკვეული სახის ცირკულარული სტრუქტურა, მაგრამ ჩვენ ვიყენებთ რა ოპერატორს C გავაკეთოთ, რომ სახის wraparound? [Inaudible სტუდენტი საპასუხოდ] >> modulo ოპერატორს. კარგი იქნებოდა, ცოტა შემაშფოთებელი ვიფიქროთ მეშვეობით როგორ გავაკეთოთ wraparound, მაგრამ ჩვენ შეგვიძლია ამის გაკეთება, და ჩვენ შეგვიძლია დავიწყოთ ხალხის რა გამოყენებული იქნება წინა ხაზის, მაგრამ ჩვენ უბრალოდ გვახსოვდეს ამ ხელმძღვანელი ცვლადი ვინც ფაქტობრივი ხელმძღვანელი ხაზის ფაქტობრივად. რა მოხდება, თუ, ნაცვლად, ჩვენი მიზანი საბოლოოდ, თუმცა, იყო ეძებოთ ნომრები, როგორც გავაკეთეთ აქ სცენაზე ერთად ანიტა, მაგრამ ჩვენ ნამდვილად გვინდა საუკეთესო ყველა ამ სამყაროებს? ჩვენ გვინდა უფრო დახვეწილობის, ვიდრე მასივი საშუალებას იმიტომ, რომ ჩვენ გვინდა უნარი დინამიურად იზრდება მონაცემები სტრუქტურა. მაგრამ ჩვენ არ გვინდა, რომ გვქონდეს მიმართო ის, რასაც ჩვენ აღნიშნა პირველ ლექციას არ იყო ოპტიმალური ალგორითმის, რომ წრფივი ძებნა. თურმე შეგიძლიათ, ფაქტობრივად, მივაღწიოთ ან თუნდაც ახლოს მუდმივი დროს, რომლის დროსაც ვიღაცას მოსწონს ანიტა, თუ ის configures მისი მონაცემები სტრუქტურა არ უნდა იყოს დაკავშირებული სიაში, არ უნდა დასტის, არ იყოს რიგში, შეიძლება, ფაქტობრივად, ამუშავება მონაცემები სტრუქტურა, რომელიც საშუალებას აძლევს მას ეძებოთ ნივთები, თუნდაც სიტყვა, არა მხოლოდ ციფრები, რა ჩვენ მოვუწოდებთ მუდმივი დრო. 

ფაქტია, ვეძებ წინ, ერთ psets ამ კლასში თითქმის ყოველთვის განხორციელების ეცნობით, რომლის დროსაც ჩვენ გაძლევთ კვლავ ზოგიერთ 150,000 ინგლისური სიტყვა და მიზანია ჩატვირთვა იმ მეხსიერებაში და სწრაფად შეძლებს უპასუხოს კითხვებს ფორმა არის ამ სიტყვის მართლწერაში? და ეს მართლაც suck თუ მოუხდა iterate მთელი 150,000 სიტყვა უპასუხოს, რომ. მაგრამ, სინამდვილეში, ჩვენ დავინახავთ, რომ ჩვენ შეგვიძლია გავაკეთოთ ეს ძალიან, ძალიან სწრაფი დრო. და ეს აპირებს ჩართვას ახორციელებს რაღაც მოუწოდა hash მაგიდა, და მიუხედავად იმისა, რომ ერთი შეხედვით ეს რამ მოუწოდა hash table აპირებს მოდით მივაღწიოთ ამ სუპერ სწრაფი რეაგირების ჯერ, აღმოჩნდება, რომ არსებობს რეალურად პრობლემა. როდესაც საქმე დროის განხორციელების რამ მოუწოდა-ისევ, მე ამის გაკეთება კიდევ ერთხელ. მე მხოლოდ ერთი აქ. როდესაც საქმე დროის შეასრულოს ამ რამ მოუწოდა hash მაგიდა, ჩვენ ვაპირებთ აქვს მიიღოს გადაწყვეტილება. რამდენად დიდი უნდა ამ რამ რეალურად იყოს? და როდესაც ჩვენ დავიწყებთ ჩასმა ციფრები ამ hash მაგიდა, როგორ მივდივართ შესანახად მათ ასეთი გზა რომ ჩვენ შეგვიძლია მიიღონ მათ უკან, როგორც სწრაფად, როგორც მივიღეთ მათ? მაგრამ ჩვენ დავინახავთ ადრე ხანგრძლივი, რომ ეს საკითხი როდესაც ყველას დაბადების დღე არის კლასის იქნება საკმაოდ გერმანე. თურმე ამ ოთახში, გვაქვს რამდენიმე ასეული ადამიანი, ასე რომ შანსები ორი უნდა გვქონდეს იგივე დღე ალბათ საკმაოდ მაღალია. რა მოხდება, თუ იქ მხოლოდ 40 ჩვენგანს ამ ოთახში? რა შანსები ორი მქონე ადამიანები იგივე დაბადების დღე? [სტუდენტთა] 50%. ჰო, მეტი 50%. რეალურად, მე კი მოუტანა ჩარტში. თურმე, და ამ მართლაც მხოლოდ Sneak გადახედვისას- თუ მხოლოდ 58 ჩვენგანს ამ ოთახში, ალბათობა 2 ჩვენგანი იგივე დღე არის უკიდურესად მაღალია, თითქმის 100%, და რომ აპირებს გამოიწვევს მთელი bunch of ავნებს ჩვენთვის ოთხშაბათს. 

აღნიშნულის გათვალისწინებით, მოდით adjourn აქ. ჩვენ დავინახავთ, თქვენ ოთხშაბათს. [ტაში] [CS50.TV]