[Powered by Google Translate] [კვირა 6 გაგრძელდა] [დევიდ ჯ Malan] [ჰარვარდის უნივერსიტეტის] [ეს არის CS50.] [CS50.TV] ეს არის CS50 და ეს ბოლომდე კვირაში 6. ამიტომ CS50x, ერთი ჰარვარდის პირველი კურსები ჩართული EDX ინიციატივა მართლაც დებიუტი გასულ ორშაბათს. თუ გსურთ მიიღოთ glimpse თუ რა სხვები ინტერნეტში ახლა შემდეგ ერთად, შეგიძლიათ ხელმძღვანელს x.cs50.net. ეს ხელს გადამისამართება თქვენ შესაბამისი ადგილი edx.org, რაც იყო, სადაც ეს და სხვა საგნები MIT და Berkeley ცხოვრობს. თქვენ უნდა მოაწეროს up for ანგარიშის, თქვენ იპოვით რომ მასალა არის დიდწილად იმავე როგორც თქვენ მქონდა ამ სემესტრში, თუმცა რამდენიმე კვირის დაგვიანებულია, რადგან ჩვენ ყველაფერი მზად არის. მაგრამ რა სტუდენტების CS50x ახლა ვხედავთ არის ინტერფეისი საკმაოდ მოსწონს ეს. ეს, მაგალითად, არის Zamyla წამყვანი walkthrough პრობლემის კომპლექტი 0. Upon შესასვლელად, რათა edx.org, CS50x სტუდენტი ხედავს სახის ნივთები თქვენ მოელოდა დაათვალიერონ კურსი: ლექცია ორშაბათს, ლექცია ოთხშაბათი, სხვადასხვა შორტები, პრობლემა კომპლექტი, walkthroughs, PDFs. გარდა ამისა, როგორც ხედავთ აქ, მანქანა თარგმანი ინგლისური ტრანსკრიპცია შევიდა ჩინური, იაპონური, ესპანური, იტალიური, და მთელი bunch სხვა ენებზე რომ აუცილებლად არასრულყოფილი როგორც ჩვენ გააფართოვოს მათ პროგრამულად გამოყენებით რაღაც მოუწოდა API, ან განაცხადის პროგრამირების ინტერფეისი, საწყისი Google რომ საშუალებას გვაძლევს კონვერტირება ინგლისური ეს სხვა ენებზე. მაგრამ წყალობით საოცარი სულისკვეთებით რამდენიმე ასეული-plus მოხალისეები, შემთხვევითი ადამიანი ინტერნეტში, რომლებმაც kindly შესთავაზა ჩაერთოს ამ პროექტში, ჩვენ თანდათანობით ხარისხის გაუმჯობესება იმ თარგმანი by მქონე ადამიანები შეასწოროს შეცდომები, ჩვენი კომპიუტერები გააკეთეს. 

გამოდის, ჩვენ კიდევ რამდენიმე სტუდენტი გამოჩნდება ორშაბათს, ვიდრე ჩვენ თავდაპირველად მოსალოდნელია. ფაქტობრივად, ახლა CS50x აქვს 100,000 ადამიანი შემდეგ გასწვრივ სახლში. ასე რომ მიხვდებიან, თქვენ ყველა ნაწილი პირველი კლასის მიღების ამ კურსს კომპიუტერულ მეცნიერებათა განათლების უფრო ზოგადად, უფრო ფართოდ, ხელმისაწვდომი. და რეალობა არის, ზოგიერთ ამ მასიური ონლაინ კურსებს, ისინი ყველა იწყება ამ ძალიან მაღალი ციფრები, როგორც ჩვენ, როგორც ჩანს, არ გაკეთებულა აქ. მაგრამ მიზანი, საბოლოო ჯამში, ამისთვის CS50x მართლაც მიიღოს როგორც ბევრი ადამიანი, რათა finish line რაც შეიძლება. By დიზაინი, CS50x აპირებს შესთავაზებენ ამ წარსულის ორშაბათი ყველა გზა მეშვეობით 15 აპრილი, 2013, ისე, რომ დაკარგულია აქვს სკოლა ვალდებულებების სხვაგან, სამუშაო, ოჯახი, სხვა კონფლიქტების და მოსწონს, აქვს უფრო მეტი მოქნილობა , რომლითაც ჩაყვინთვის შევიდა ამ კურსს, რომლის, საკმარისია იმის თქმა, საკმაოდ ambitiously გაკეთდეს თუ მხოლოდ მეტი კურსი მხოლოდ სამი თვის განმავლობაში ჩვეულებრივი სემესტრში. მაგრამ ამ სტუდენტებს იქნება ბრძოლა იგივე პრობლემა კომპლექტი, ათვალიერებენ იგივე შინაარსი, დაშვების მქონე იგივე შორტები და მოსწონს. ასე რომ მიხვდებიან, რომ ჩვენ ყველანი ნამდვილად ამ ერთად. და ერთი ბოლომდე მიზნების CS50x არ არის მხოლოდ მიიღოს როგორც ბევრი FOLKS to finish line და მივცეთ ამ newfound გაგება კომპიუტერულ მეცნიერებათა და პროგრამირების არამედ იმისათვის, რომ მათ აქვთ ეს გაუზიარეს გამოცდილება. ერთი განმსაზღვრელი მახასიათებლების 50 წლის კამპუსში, იმედი გვაქვს, უკვე ამ სახის კომუნალური გამოცდილება, უკეთესი ან უარესი, ზოგჯერ, მაგრამ აქვთ ამ ხალხს მივმართოთ მარცხნივ და მარჯვნივ, და საოფისე საათი და hackathon და სამართლიანი. ეს პატარა რთული გავაკეთოთ, რომ პირი, FOLKS შემოსული, მაგრამ CS50x დაასრულებს აპრილში პირველი ოდესმე CS50 ექსპო, რაც იქნება ონლაინ ადაპტაციის ჩვენი იდეა სამართლიანი სადაც ეს ათასობით სტუდენტი მიიღებს ყველა მოიწვევენ წარმოადგინოს 1 - დან 2 წუთიანი ვიდეო, ან screencast მათი საბოლოო პროექტის ან ვიდეო მათგანი ფრიალი მიესალმები და ვსაუბრობთ მათი პროექტი და demoing ის, ჰგავს თქვენი წინამორბედები გავაკეთეთ აქ კამპუსში სამართლიანი, ასე, რომ სემესტრის ბოლოს, იმედი ჰქონდეს გლობალური გამოფენა საქართველოს CS50x სტუდენტთა საბოლოო პროექტები, ჰგავს, რომელიც გელოდებათ ამ დეკემბერს აქ კამპუსში. ასე უფრო, რომ თვით მოვა. 

100,000 სტუდენტები, თუმცა, მოდის საჭიროება კიდევ რამდენიმე CAS. იმის გათვალისწინებით, რომ თქვენ ბიჭები არიან Blazing ბილიკი აქ და აღების CS50 რამდენიმე კვირით ადრე ეს მასალა გათავისუფლების to FOLKS on EDX, გააცნობიეროს ჩვენ გვიყვარს ჩართვა, როგორც ბევრი ჩვენი სტუდენტები შეძლებისდაგვარად ამ ინიციატივას, ორივე დროს სემესტრის ასევე ზამთარში და ამ მოდის გაზაფხულზე. ასე რომ, თუ გსურთ ჩაერთოს CS50x, განსაკუთრებით გაწევრიანების წელს CS50x საუბარი, EDX ვერსია CS50 საუბარი, რაც ბევრ თქვენგანს არ იყენებს შესახებ კამპუსზე, ონლაინ ფორუმი, გთხოვთ ხელმძღვანელს, რომ URL, მოდით იცის ვინ ხარ შენ, იმიტომ, რომ ჩვენ გვიყვარს მინდა შექმნას გუნდი სტუდენტები და პერსონალი და ფაკულტეტის alike on კამპუსში რომლებიც უბრალოდ თამაშობენ ერთად და ეხმარება გარეთ. და როცა ხედავენ კითხვას რომ ნაცნობი მათ გესმით სტუდენტი ანგარიშგების ზოგიერთი ხარვეზის სადღაც არსებობს ზოგიერთ ქვეყანაში ინტერნეტი, და რომ ბეჭდები ზარი რადგან თქვენც ჰქონდა, რომ იგივე საკითხის თქვენს D-დარბაზში ცოტა ხნის წინ, იმედია მაშინ chime და გაუზიაროთ თქვენი საკუთარი გამოცდილება. ამიტომ გთხოვთ, ნუ მიიღოს თუ გსურთ. 

კომპიუტერულ მეცნიერებათა კურსები ჰარვარდის აქვს ცოტა ტრადიცია, CS50 მათ შორის, საქართველოს გარკვეული ტანსაცმელი, ზოგიერთი ტანსაცმელი, რომ თქვენ შეგიძლიათ აცვიათ ამაყად ზე სემესტრის ბოლოს და განაცხადა, რომ საკმაოდ ამაყად რომ თქვენ დასრულდა CS50 და აიღო CS50 და მოსწონს, და ჩვენ ყოველთვის ვცდილობთ ჩართვას სტუდენტები ამ პროცესში რაც შეიძლება მეტი, სადაც ვიწვევთ, გარშემო ამ დროს სემესტრის სტუდენტებს წარუდგენს დიზაინით გამოყენებით Photoshop, ან რასაც ინსტრუმენტი არჩევანის გსურთ გამოიყენოთ თუ თქვენ დიზაინერი, წარუდგინოს პროექტებში მაისურები და sweatshirts და ქოლგები და პატარა bandanas ამისთვის ძაღლები ჩვენ ახლა აქვს და ასე შემდეგ. და ყველაფერი ამის შემდეგ - გამარჯვებული ყოველი წლის შემდეგ ხდება გამოფენილი on რა თქმა ნახვა საათზე store.cs50.net. ყველაფერი გაიყიდა ღირებულება არსებობს, მაგრამ ნახვა მხოლოდ ეშვება თავისთავად და საშუალებას აძლევს ხალხს აირჩიოს ფერის და დიზაინის, რომ მათ ამის სურვილი აქვთ. ასე მეგონა ჩვენ უბრალოდ იზიარებს ზოგიერთი გასული წლის დიზაინის რომ იყვნენ ნახვა გარდა ამისა ერთი აქ, რაც წლიური ტრადიცია. "ყოველ დღე მე seg Faultn" იყო წარმოდგენილი გასული წლის რომელიც ჯერ კიდევ არ არის შესაძლებელი იქ კურსდამთავრებულები. ჩვენ გვქონდა ამ ერთი, "CS50 შექმნილი 1989 წელს." ერთი ჩვენი Bowdens, რობ, იყო ძალიან პოპულარული შარშან. "გუნდი Bowden" დაიბადა, ამ დიზაინით იყო წარმოდგენილი, მათ შორის ყველაზე გამყიდველები. როგორც იყო ამ ერთი აქ. ბევრი ადამიანი ჰქონდა "Bowden ცხელება" მიხედვით გაყიდვების ჟურნალი. გააცნობიეროს, რომ შეიძლება ახლა იყოს თქვენი დიზაინი, up ინტერნეტში. სხვა დეტალები ამ მომდევნო პრობლემა ადგენს მოვა. 

კიდევ ერთი ინსტრუმენტი: თქვენ გარკვეული ექსპოზიციის და იმედია ახლა ზოგიერთი პრაქტიკული გამოცდილება GDB, რაც, რა თქმა უნდა, debugger და გაძლევთ საშუალებას მანიპულირება თქვენი პროგრამის საკმაოდ დაბალი დონე, რასაც სახის რამ? რას GDB მოგცემთ გავაკეთოთ? ჰო? მომეცი რამე. [სტუდენტური პასუხი, გაუგებარია] კარგი. ნაბიჯი შევიდა ფუნქცია, ასე რომ თქვენ არ უბრალოდ უნდა აკრიფოთ აწარმოებს და აქვს პროგრამა დარტყმა მეშვეობით მთლიანობაში, დაბეჭდვისას რამ სტანდარტულ გამოსავალზე. უფრო მეტიც, თქვენ შეგიძლიათ დაიხევს მეშვეობით იგი ხაზს, ან აკრეფით შემდეგი წასვლა ხაზის მიერ ხაზს ან ნაბიჯი ჩაყვინთვის შევიდა ფუნქცია, როგორც წესი, ერთი, რომ თქვენ წერდა. რა ამჯამად GDB მოგცემთ გავაკეთოთ? ჰო? [სტუდენტური პასუხი, გაუგებარია] ამობეჭდვა ცვლადები. ასე რომ, თუ გსურთ პატარა introspection შიგნით თქვენი პროგრამა გარეშე მიმართო წერილობით printf განცხადებები მთელი ადგილი, შეგიძლიათ უბრალოდ ამობეჭდოთ ცვალებად და ცარიელია ცვლადი. რა შეგიძლიათ ერთად debugger მოსწონს GDB? [სტუდენტური პასუხი, გაუგებარია] სწორედ. შეგიძლიათ დააყენოთ breakpoints, თქვენ შეიძლება ითქვას, შესვენების აღსრულება მთავარ ფუნქციას ან foo ფუნქცია. შეიძლება ითქვას შესვენების შესრულების დროს ხაზი 123. და breakpoints არიან მართლაც ძლიერი ტექნიკა რადგან თუ თქვენ გაქვთ ზოგადად გრძნობა, სადაც თქვენი პრობლემა ალბათ, თქვენ არ დახარჯონ დრო სტეპინგზე მეშვეობით პროგრამის მთლიანად. შეგიძლიათ არსებითად ხტომა უფლება არსებობს და შემდეგ დაიწყება ფერთა - სტეპინგზე მეშვეობით იგი ნაბიჯი ან მომდევნო ან მოსწონს. მაგრამ დაჭერა რაღაც მოსწონს GDB არის ის, რომ გეხმარებათ, ადამიანური, იპოვოთ თქვენი პრობლემების და გაეცნონ თქვენს ბაგები. ეს სულაც არ იპოვის მათ იმდენად თქვენთვის. 

ამიტომ, ჩვენ გააცნო მეორე დღეს style50, რომელიც მოკლე ბრძანება ხაზი ინსტრუმენტი რომ ცდილობს stylize თქვენი კოდი ცოტა მეტი cleanly ვიდრე თქვენ, ადამიანური, შეიძლება გაკეთდეს. მაგრამ ეს, ძალიან, მართლაც მხოლოდ ესთეტიკური რამ. მაგრამ თურმე არსებობს ამ სხვა ინსტრუმენტი მოუწოდა Valgrind რომ არის ცოტა უფრო arcane გამოიყენოს. მისი გამომუშავება atrociously cryptic ერთი შეხედვით. მაგრამ შესანიშნავად სასარგებლო, განსაკუთრებით ახლა, რომ ჩვენ დროს ნაწილი ვადა აქ თქვენ დაწყებული გამოიყენოს malloc და დინამიური მეხსიერების გამოყოფის. რამ შეიძლება წასვლა ნამდვილად, ნამდვილად არასწორი სწრაფად. რადგან თუ თქვენ დაგავიწყდებათ გასათავისუფლებლად თქვენი მეხსიერება, ან თქვენ dereference ზოგიერთი NULL მაჩვენებელი, ან თქვენ dereference ზოგიერთი ნაგვის მაჩვენებელი, რა არის ტიპიურად სიმპტომია, რომ შედეგი? Seg ბრალია. და თქვენ მიიღებთ ამ ძირითადი ფაილის ზოგიერთი ხმების kilobytes ან მეგაბაიტები რომელიც წარმოადგენს სახელმწიფო თქვენი პროგრამის მეხსიერებაში, როდესაც ის შეეჯახა, მაგრამ თქვენი პროგრამის საბოლოოდ seg ხარვეზებით, სეგმენტაცია ბრალია, რაც იმას ნიშნავს, რაღაც ცუდი მოხდა თითქმის ყოველთვის დაკავშირებულია to მეხსიერების დაკავშირებული შეცდომა, რომ თქვენ გააკეთა სადღაც. ამიტომ Valgrind გეხმარებათ მოვძებნოთ რამ მოსწონს ეს. ეს ინსტრუმენტი, რომ თქვენ აწარმოებს, როგორიცაა GDB, შემდეგ თქვენ შედგენილი თქვენი პროგრამა, მაგრამ ვიდრე აწარმოებს თქვენი პროგრამის პირდაპირ, თქვენ აწარმოებს Valgrind და თქვენ გაივლის მას თქვენი პროგრამა, ისევე, როგორც თქვენ არ უკავშირდება GDB. ახლა გამოყენება, რომ მიიღოს საუკეთესო სახის გამომუშავება, ცოტა ხანგრძლივი, ამიტომ უფლება არსებობს atop of ეკრანზე დაინახავთ Valgrind-V. "V" თითქმის საყოველთაოდ ნიშნავს verbose როდესაც თქვენ იყენებთ პროგრამების Linux კომპიუტერზე. ეს იმას ნიშნავს Spit მეტი მონაცემები, ვიდრე თქვენ შეიძლება იყოს. "- გაჟონვის-შეამოწმოთ = სრული." ეს მხოლოდ ამბობდა გამშვები ყველა შესაძლო მეხსიერების ტბები, შეცდომები, მე შეიძლება გააკეთა. ეს, ძალიან, არის საერთო პარადიგმა ერთად Linux პროგრამები. საერთოდ, თუ გაქვთ ბრძანების არგუმენტი რომ "შეცვლა", რომ უნდა შეიცვალოს პროგრამის ქცევას და ეს ერთი წერილი, ეს-V, მაგრამ თუ ეს გადაერთო, მხოლოდ დიზაინი პროგრამისტი, არის სრული სიტყვა ან სერია სიტყვა, ბრძანება ხაზი არგუმენტი იწყება -. ეს არის უბრალოდ ადამიანის კონვენციების, მაგრამ თქვენ ნახავთ მათ სულ უფრო და უფრო. და მაშინ, საბოლოოდ, "a.out" არის თვითნებური სახელი პროგრამა ამ კონკრეტულ მაგალითს. და აქ ზოგიერთი წარმომადგენელი გამომუშავება. 

სანამ ჩვენ შევხედოთ რა, რომ შესაძლოა ნიშნავს, ნება მომეცით წასვლა მეტი Snippet კოდის მეტი აქ. და ნება მომეცით გადავიდეს ამ გარეთ გზა, მალე, და მოდით შევხედოთ memory.c, რომელიც ამ მოკლე მაგალითად აქ. ასე რომ ამ პროგრამის ნება მიბოძეთ, მიუახლოვდით ფუნქციები და კითხვები. ჩვენ გვყავს ფუნქცია ძირითად რომ უწოდებს ფუნქცია, ვ, და მერე რას ვ გაგრძელება გასაკეთებელი, ოდნავ ტექნიკური ინგლისურ? რას ვ გაგრძელება გავაკეთო? როგორ შესახებ დავიწყებ ხაზის 20 და ვარსკვლავი ადგილმდებარეობის მნიშვნელობა არ აქვს, მაგრამ მე უბრალოდ იყოს თანმიმდევრული აქ ბოლო ლექცია. რა არის ხაზზე 20 ნუ ჩვენთვის? წლის მარცხენა მხარეს. ჩვენ შესვენება მისი დანგრევა შემდგომი. Int * x: რას აკეთებთ? Okay. ეს გამოცხადების მაჩვენებელი და ახლა მოდით კიდევ უფრო ტექნიკური. რას ნიშნავს ეს, ძალიან კონკრეტულად, განაცხადოს მაჩვენებელი? ვინმე? ჰო? [სტუდენტური პასუხი, გაუგებარია] ძალიან შორს. ასე, რომ თქვენ კითხულობთ რომ მარჯვენა მხარეს თანაბარი ნიშანი. მოდით ფოკუსირება მხოლოდ მარცხენა, მხოლოდ int * x. ეს ნიშნავს "განაცხადოს" კურსორი, მაგრამ ახლა მოდით ჩაყვინთვის უფრო ღრმა წელს რომ განსაზღვრება. რას კონკრეტულად, ტექნიკურად ნიშნავს? ჰო? [სტუდენტური პასუხი, გაუგებარია] Okay. ის ემზადებოდა გადარჩენა მისამართი მეხსიერებაში. კარგი. და მოდით ეს ერთი ნაბიჯი შემდგომი; ის გამოცხადების ცვლადი, x, რომ 32 ბიტი. და ვიცი, ეს 32 ბიტი, რადგან -? ეს არა იმიტომ, რომ ეს int, რადგან ეს მაჩვენებელი ამ შემთხვევაში. შემთხვევითი, რომ ეს არის ერთ ერთი და იგივე int, მაგრამ ფაქტია, რომ არსებობს ვარსკვლავი იქ ნიშნავს ეს მაჩვენებელი და ელექტრო მოწყობილობების, როგორც მრავალი კომპიუტერები, მაგრამ არა ყველა, მითითებები 32 ბიტი. უფრო თანამედროვე ტექნიკითა მოსწონს უკანასკნელი Macs, უახლესი კომპიუტერით, თქვენ ალბათ 64-bit პოინტერები, მაგრამ ელექტრო მოწყობილობების, ეს ყველაფერი 32 ბიტი. ამიტომ ჩვენ standardize რომ. კერძოდ, სიუჟეტი მიდის შემდეგნაირად: ჩვენ "განაცხადოს" კურსორის; რას ნიშნავს ეს? ვამზადებთ შესანახად მეხსიერებაში მისამართზე. რას ნიშნავს ეს? ჩვენ ვქმნით ცვლადში x რომ იკავებს 32 ბიტს რომ მალე შესანახად მისამართი რიცხვი. და ეს ალბათ დაახლოებით როგორც ზუსტი, როგორც ჩვენ შეიძლება მიიღოს. ეს ჯარიმა წინსვლის გამარტივება მსოფლიოში და უბრალოდ, ვამბობთ განაცხადოს მაჩვენებელი მოუწოდა x. განაცხადოს მაჩვენებელი, მაგრამ რეალიზება და ესმით, რა რეალურად მიმდინარეობს თუნდაც მხოლოდ იმ რამდენიმე სიმბოლოს. 

ახლა, ამ ერთი თითქმის პატარა ადვილია, მიუხედავად იმისა, რომ ეს აღარ გამოხატვის. ასე რომ რა არის ეს აკეთებს, რომ ხაზგასმით არის: "malloc (10 * sizeof (int));" ჰო? [სტუდენტური პასუხი, გაუგებარია] კარგი. მე კი მას იქ. ეს განაწილების ბლოკი მეხსიერება ათი რიცხვებით. და ახლა მოდით ჩაყვინთვის წელს ოდნავ უფრო ღრმა, ვიდრე გამოყოფის ბლოკი მეხსიერება ათი რიცხვებით. რა არის malloc შემდეგ ბრუნდებიან? მისამართი, რომ ბლოკი, ან, უფრო კონკრეტულად, მისამართი პირველი byte რომ ბლოკი. როგორ მაშინ ვარ, პროგრამისტი, რომ ვიცი, სად, რომ ბლოკი მეხსიერება შაბათ? მე ვიცი, რომ ეს მომიჯნავე. Malloc, ზოგადად, მოგცემთ მომიჯნავე ბლოკი მეხსიერება. არარის ხარვეზები იყო. თქვენ გაქვთ ყველა byte რომ ბლოკი, თავში დაბრუნება უკან, მაგრამ როგორ ვიცი, სადაც ბოლომდე ბლოკი მეხსიერება? როდესაც თქვენ იყენებთ malloc? [სტუდენტური პასუხი, გაუგებარია] კარგი. თქვენ არ. თქვენ უნდა გვახსოვდეს. უნდა გვახსოვდეს, რომ მე გამოიყენება ღირებულების 10, და არც კი, როგორც ჩანს, არ გაკეთებულა, რომ აქ. მაგრამ onus მთლიანად ჩემზე. Strlen, რომელიც ჩვენ გავხდეთ ოდნავ დამოკიდებული სიმებისათვის, მუშაობს მხოლოდ ამ კონვენციას მქონე \ 0 ან ამ სპეციალური nul ხასიათი, NUL, დასასრულს სიმებიანი. რომ არ ფლობს მხოლოდ თვითნებური მოცულობით მეხსიერება. ეს თქვენი გადასაწყვეტია. ამიტომ ხაზი 20, მაშინ, გამოყოფს ბლოკი მეხსიერება რომ შენახვა შეუძლია ათი რიცხვებით და მას ინახავს მისამართი პირველი byte ამ ბლოკი მეხსიერება ცვლადში x. Ergo, რომელიც მაჩვენებელმა. ამიტომ ხაზი 21, სამწუხაროდ, შეცდომა იყო. მაგრამ პირველი, რა არის ეს აკეთებს? ის ამბობდა შენახვის დროს საიდან 10, 0 ინდექსირებული, საქართველოს ბლოკი მეხსიერება მოუწოდა x ღირებულების 0. 

ასე რომ შეამჩნია რამდენიმე რამ მიმდინარეობს. მიუხედავად იმისა, რომ X-ის მაჩვენებელი, გავიხსენოთ საწყისი რამდენიმე კვირის წინ რომ თქვენ შეგიძლიათ კვლავ გამოიყენოთ მასივი სტილის კვადრატული ფრჩხილი ნოტაცია. რადგან ისინი სინამდვილეში მოკლე მხრივ ნოტაცია ამისთვის მეტი cryptic ორიენტირებული მაჩვენებელი არითმეტიკული. სადაც ჩვენ ყველაფერს გააკეთებს მსგავსი რამ: ეს მიმართვა x გადატანა 10 წერტილში, შემდეგ იქ რასაც მისამართი ინახება იმ ადგილას. მაგრამ გულწრფელად ვამბობ, ეს მხოლოდ ბარბაროსულ წასაკითხად და კიდევ კომფორტულად. ასე, რომ მსოფლიო ჩვეულებრივ იყენებს კვადრატულ ფრჩხილებში მხოლოდ იმიტომ, რომ ეს ასე უფრო მეტი ადამიანის მეგობრული წაიკითხოს. მაგრამ ეს არის ის, რაც ნამდვილად მიმდინარეობს ქვეშ hood; x არის მისამართი, არ მასივი, თავისთავად. ასე რომ, ეს შენახვის 0 საიდან 10 in x. რატომ არის ეს ცუდი? ჰო? [სტუდენტური პასუხი, გაუგებარია] ზუსტად. ჩვენ მხოლოდ გამოყოფილი ათი ints, მაგრამ ჩვენ ითვლიან საწყისი 0 როდესაც პროგრამების C, ამიტომ თქვენ გაქვთ 0 1 2 3 4 5 6 7 8 9, მაგრამ არა 10. ასე რომ არც პროგრამა აპირებს seg ბრალია ან ეს არ. მაგრამ ჩვენ ნამდვილად არ ვიცით, ეს არის ერთგვარი nondeterministic ქცევა. ეს მართლაც დამოკიდებულია თუ არა მივიღებთ გაუმართლა. თუ აღმოჩნდება, რომ ოპერაციული სისტემა არ იბადება, თუ გამოვიყენო, რომ ზედმეტი byte, მიუხედავად იმისა, რომ არ მიეცა ის მე, ჩემი პროგრამა შეიძლება არ მისაწოდებლად. ეს ნედლეული, ეს buggy, მაგრამ თქვენ შეიძლება არ დაინახოს, რომ სიმპტომია, ან თქვენ შეიძლება ნახოთ ეს მხოლოდ ერთხელ, ხოლო. მაგრამ რეალობა ის არის, რომ შეცდომა, ფაქტობრივად, არ არსებობს. და ეს მართლაც პრობლემატურია, თუ თქვენ წერილობითი პროგრამა, რომელიც გსურთ ზუსტი, რომ თქვენ გაიყიდა პროგრამა, რომელიც ხალხს იყენებს, რომ ყველა ერთხელ ხოლო Crashes რადგან, რა თქმა უნდა, ეს არ არის კარგი. რეალურად, თუ თქვენ გაქვთ Android ტელეფონის ან iPhone და თქვენ ჩამოტვირთოთ apps ამ დღეებში, თუ თქვენ ოდესმე ჰქონდა app ახლახან შევწყვიტე, უეცრად იგი ქრება, რომ თითქმის ყოველთვის შედეგია ზოგიერთი მეხსიერების დაკავშირებული საკითხი, რის პროგრამისტი ბრალია და dereferenced მაჩვენებელი რომ მას არ უნდა ჰქონდეს, და შედეგად iOS ან Android არის უბრალოდ მოკვლა პროგრამის საერთოდ ვიდრე რისკის გაურკვეველი ქცევის ან რაიმე სახის უსაფრთხოების კომპრომისი. 

თუმცა ერთი სხვა bug ამ პროგრამის გარდა ამისა ერთი. რა არ მე ბრალია ამ პროგრამაში? მე არ გამოცდილები რასაც მე იქადაგა. ჰო? [სტუდენტური პასუხი, გაუგებარია] კარგი. მე არ გაათავისუფლა მეხსიერება. ამიტომ უზენაესობის ცერის არის უნდა იყოს ნებისმიერ დროს რეკავთ malloc, თქვენ უნდა დარეკოთ უფასო როდესაც თქვენ კეთდება გამოყენებით, რომ მეხსიერებაში. ახლა, როდესაც ამას მინდა გასათავისუფლებლად ამ მეხსიერების? ალბათ, თუ ვთქვათ ამ პირველი ხაზი იყო ზუსტი, მე მინდა ამის გაკეთება აქ. იმიტომ, რომ მე ვერ, მაგალითად, ამას ქვემოთ აქ. რატომ? უბრალოდ გარეთ ფარგლებს. ასე რომ მიუხედავად იმისა, რომ ჩვენ ვსაუბრობთ პოინტერები, ეს კვირაში 2 ან 3 საკითხი, სადაც x არის მხოლოდ ფარგლებს შიგნით Curly braces სადაც იგი გამოცხადდა. ასე, რომ თქვენ აუცილებლად ვერ გასათავისუფლებლად ეს იქ. ჩემი ერთადერთი შანსი გასათავისუფლებლად ეს უხეშად შემდეგ ხაზი 21. ეს არის საკმაოდ მარტივი პროგრამა, რომ ეს იყო საკმაოდ ადვილი ერთხელ თქვენ სახის გახვეული თქვენი გონება გარშემო რა პროგრამა აკეთებს, სადაც შეცდომები იქნა. და მაშინაც კი თუ თქვენ არ ჩანს, პირველ რიგში, იმედია ეს პატარა აშკარა არის რომ ამ შეცდომების საკმაოდ ადვილად მოგვარდება და მარტივად გააკეთა. მაგრამ როდესაც პროგრამა უმეტეს 12 ხაზების ხანგრძლივი, ეს 50 ხაზების ხანგრძლივი, 100 ხაზების ხანგრძლივი, გავლით თქვენი კოდი ხაზს, ფიქრი მეშვეობით იგი ლოგიკურად, შესაძლებელია, მაგრამ არა განსაკუთრებით გართობა გავაკეთოთ, მუდმივად ეძებს შეცდომებს, და ეს ასევე რთულია, და ამიტომ ინსტრუმენტი, როგორიცაა Valgrind არსებობს. ნება მომეცით წავიდეთ წინ და ამის გაკეთება: ნება მომეცით გახსნა ჩემი ტერმინალის ფანჯარა, და ნება მომეცით არა მხოლოდ აწარმოებს მეხსიერება, რადგან მეხსიერების ჩანს ჯარიმა. მე მიღების გაუმართლა. აპირებს, რომ დამატებითი byte დასასრულს მასივი არ ჩანს, ძალიან პრობლემატურია. მაგრამ ნება მიბოძეთ, მიუხედავად ამისა, არ საღი აზრის შემოწმება, რომელიც მხოლოდ იმას ნიშნავს, რომ შეამოწმოთ თუ არა ეს რეალურად სწორი. 

ასე რომ მოდით valgrind-V - გაჟონვის-შეამოწმოთ = სრული, და შემდეგ პროგრამის დასახელება ამ შემთხვევაში არის მეხსიერება, არ a.out. ნება მომეცით, წავიდეთ წინ და ამის გაკეთება. 'Enter. ძვირფასო ღმერთი. ეს არის მისი გამომუშავება, და ეს არის ის, რაც მე გააკეთა მინიშნება ადრე. მაგრამ, თუ თქვენ ვისწავლოთ წაკითხვის საშუალებით ყველა სისულელე აქ, ყველაზე მეტად ეს მხოლოდ დიაგნოსტიკური გამომავალი რომ არ არის, რომ საინტერესო. რა თქვენი თვალის ნამდვილად სურს ეძებს რაიმე ნახსენები შეცდომა ან არასწორი. სიტყვები, ვარაუდობენ პრობლემები. მართლაც, ვნახოთ რა ხდება არასწორი ქვემოთ აქ. მაქვს შემაჯამებელი რაიმე სახის ", გამოიყენება საათზე გასასვლელში: 40 bytes in 1 ბლოკები." მე არ ვარ ნამდვილად დარწმუნებული რა ბლოკი არ არის, მაგრამ 40 ბაიტი რეალურად იგრძნობა შემეძლო გაერკვნენ, სადაც რომ მოდის. 40 ბაიტი. რატომ 40 ბაიტი გამოიყენება საათზე გასასვლელში? და უფრო კონკრეტულად, თუ ჩვენ გადახვევა ქვემოთ აქ, რატომ არ ნამდვილად დაკარგული 40 ბაიტი? ჰო? [სტუდენტური პასუხი, გაუგებარია] Perfect. ჰო, ზუსტად. იყო ათი რიცხვებით, და თითოეული იმ არის ზომა 4, ან 32 ბიტი, მე დავკარგე ზუსტად 40 ბაიტი, რადგან, როგორც თქვენ შესთავაზა, მე არ მოუწოდა უფასო. სწორედ ერთი bug, და ახლა მოდით წავიკითხოთ ქვემოთ პატარა შემდგომი და ვნახოთ შემდეგი ამ, "არასწორი წერენ of ზომა 4." ახლა რა არის ეს? ეს მისამართი გამოთქვა რა ბაზის ნოტაცია, როგორც ჩანს? ეს არის თექვსმეტობითი და ნებისმიერ დროს ხედავთ ხმების დაწყებული 0x, ეს იმას ნიშნავს, თექვსმეტობითი, რომელიც ჩვენ გავაკეთეთ გზა უკან, ვფიქრობ, pset 0 ნახვა მონაკვეთზე კითხვები, რომელიც იყო უბრალოდ უნდა გავაკეთოთ warmup exercise, converting ათობითი to hex to ბინარული და სხვ. თექვსმეტობითი, მხოლოდ ადამიანის კონვენცია, ჩვეულებრივ გამოიყენება წარმოადგენენ პოინტერები ან, უფრო ზოგადად, მისამართები. უბრალოდ კონვენცია, იმიტომ რომ პატარა ადვილი წასაკითხი, ეს ცოტა უფრო კომპაქტური ვიდრე რაღაც ათობითი, და ბინარული აზრი არა უმეტესი ადამიანები გამოიყენოს. ახლა რას ნიშნავს ეს? ასევე, ის ჰგავს არსებობს არასწორი ჩაწერის საქართველოს ზომა 4 on line 21 memory.c. მოდით დავუბრუნდეთ ხაზი 21, და მართლაც, აქ არის ის, რომ არასწორი ჩაწერის. ამიტომ Valgrind არ აპირებს მთლიანად Hold My Hand და მეუბნებოდა, თუ რა სარემონტო არის, მაგრამ გამოვლენის, რომ მე ვაკეთებ არასწორი ჩაწერის. მე ეხება 4 ბაიტი, რომ მე არ უნდა იყოს, და როგორც ჩანს, ეს იმიტომ, რომ, როგორც თქვენ აღნიშნა, მე ვაკეთებ [10] ნაცვლად [9] მაქსიმალურად ან [0] ან რაღაც შორის. With Valgrind, გააცნობიეროს ნებისმიერ დროს თქვენ ახლა პროგრამის წერა რომელიც იყენებს მაჩვენებლებისა და იყენებს მეხსიერების და malloc უფრო კონკრეტულად, აუცილებლად მოხვდება ჩვევა გაშვებული ამ ხანგრძლივი მაგრამ ძალიან ადვილად გადაწერა და pasted ფლობს Valgrind თუ არსებობს რაღაც შეცდომები არსებობს. და ეს იქნება აბსოლუტური ყოველ ჯერზე ხედავთ გამომუშავება, მაგრამ გარჩევის გზით ვიზუალურად ყველა გამომავალი და ვხედავ თუ ხედავთ აღნიშნავს შეცდომები ან გაფრთხილებისა ან არასწორი ან დაკარგა. ნებისმიერი სიტყვა რომ ჟღერს როგორც თქვენ ბრალია სადღაც. ასე რომ მიხვდებიან, რომ ახალი ინსტრუმენტი თქვენს ინსტრუმენტარიუმის. 

ახლა ორშაბათს, ჩვენ გვქონდა მთელი bunch of FOLKS ამუშავება აქ და წარმოადგენენ ცნება დაკავშირებულია სიაში. ჩვენ გააცნო უკავშირდება სიაში როგორც გამოსავალი რა პრობლემა? ჰო? [სტუდენტური პასუხი, გაუგებარია] კარგი. კოლექტორები არ შეიძლება მეხსიერების ემატება მათ. თუ გამოყოფს მასივი ზომა 10, რომ ყველა თქვენ. შეგიძლიათ დარეკოთ ფუნქცია, როგორიცაა realloc თუ თავდაპირველად მოუწოდა malloc, და რომ შეიძლება ცდილობენ იზრდება array თუ სივრცის მიმართ ბოლომდე მას რომ არავინ იყენებს, და თუ არ, ამას მხოლოდ იპოვით თქვენთვის უფრო დიდი ბლოკი სხვაგან. მაგრამ მაშინ დააკოპირეთ ყველა იმ bytes შევიდა ახალი მასივი. ეს ჟღერს ძალიან სწორი გადაწყვეტა. რატომ არის ამ წარმოჩენა, მისთვის ნიშნეული? ვგულისხმობ მუშაობს, ადამიანები არ მოგვარდება ეს პრობლემა. რატომ უნდა მოგვარდეს ეს ორშაბათს ერთად უკავშირდება სიები? ჰო? [სტუდენტური პასუხი, გაუგებარია] ეს შეიძლება გაგრძელდეს დიდი ხანი. ფაქტობრივად, ნებისმიერ დროს თქვენ მოუწოდებდა malloc ან realloc ან calloc, რომელიც არის კიდევ ერთი ერთი, ნებისმიერ დროს, პროგრამა, ვსაუბრობთ რომ ოპერაციული სისტემა, თქვენ ტენდენცია ნელი პროგრამის ქვემოთ. და თუ თქვენ აკეთებთ ამ სახის რამ მარყუჟების, თქვენ ნამდვილად slowing რამ down. თქვენ არ აპირებს შეამჩნია ეს უმარტივესი of "Hello World" ტიპის პროგრამების, მაგრამ გაცილებით პროგრამების, გეკითხებით ოპერაციული სისტემა ისევ და ისევ მეხსიერების ან ვაძლევთ მას უკან ისევ და ისევ იჩენს, რომ არ იყოს კარგია. Plus, უბრალოდ სახის ინტელექტუალურად - ის სრული დროს გაფლანგვა. რატომ გამოყოფს უფრო და უფრო მეხსიერება, რისკის გადაწერა ყველაფერი ახალი მასივი, თუ თქვენ გაქვთ ალტერნატიული, რომელიც საშუალებას თქვენ გამოყოფს მხოლოდ იმდენი მეხსიერებაში, თქვენ ნამდვილად გჭირდებათ? ასე რომ არსებობს pluses და minuses აქ. ერთი pluses ახლა ის არის, რომ ჩვენ გვაქვს დინამიურობა. არ აქვს მნიშვნელობა, სადაც მოცულობით ხსოვნა, რომ თავისუფალი, მე შემიძლია მხოლოდ სახის შექმნა ამ პურის crumbs მეშვეობით პოინტერები to string მთელი ჩემი უკავშირდება სია ერთად. მაგრამ გადავიხადო მინიმუმ ერთი ფასი. 

რა უნდა დათმოს წელს იძენს უკავშირდება სიები? ჰო? [სტუდენტური პასუხი, გაუგებარია] კარგი. გჭირდებათ მეტი მეხსიერება. ახლა მჭირდება სივრცეში ამ მითითებას, და იმ შემთხვევაში, თუ ეს სუპერ მარტივი უკავშირდება სია რომ მხოლოდ ცდილობს შესანახად რიცხვებით, რომლებიც 4 ბაიტი, ჩვენ შევინარჩუნოთ ამბობდა ასევე, კურსორი არის 4 ბაიტი, ამიტომ ახლა მე სიტყვასიტყვით გაორმაგდა თანხის მეხსიერების მჭირდება მხოლოდ შესანახად ამ სიაში. თუმცა ისევ და ისევ, ეს არის მუდმივი tradeoff კომპიუტერულ მეცნიერებაში შორის დრო და სივრცე და განვითარება, ძალისხმევა და სხვა რესურსების. რა არის კიდევ ერთი downside გამოყენების უკავშირდება სიაში? ჰო? [სტუდენტური პასუხი, გაუგებარია] კარგი. არა როგორც მარტივი წვდომისათვის. ჩვენ ვეღარ ბერკეტები კვირაში 0 პრინციპებს, როგორიცაა გათიშე და დაიპყროთ. და უფრო კონკრეტულად, ორობითი ძებნა. იმის გამო, რომ მიუხედავად იმისა, რომ ჩვენ ადამიანები ვხედავთ უხეშად სადაც შუა ამ სიაში არის, კომპიუტერი მხოლოდ იცის, რომ ეს დაკავშირებულია სია იწყება მისამართი მოუწოდა პირველი. სწორედ 0x123 ან რამე მაგდაგვარს. და ერთადერთი გზა პროგრამას შეუძლია იპოვოს შუა ელემენტს არის რეალურად ძებნის მთელი სია. და მაშინაც, ეს სიტყვასიტყვით უნდა მოძებნოთ მთელი სია, რადგან კიდევ ერთხელ თქვენ მიაღწიოს შუა ელემენტს შემდეგი პოინტერები, თქვენ, პროგრამა, არ ვიცი რამდენ ხანს ამ სიაში არის, პოტენციურად, სანამ არ მოხვდა ბოლოს, და იცით პროგრამულად რომ თქვენ დასასრულს უკავშირდება სიაში? არსებობს სპეციალური NULL მაჩვენებელი, ამიტომ ერთხელ, კონვენცია. იმის ნაცვლად, რომ გამოიყენოს ეს მაჩვენებელი, ჩვენ ნამდვილად არ გვინდა, რომ იყოს ზოგიერთი ნაგვის ღირებულება მიუთითებს off ეტაპზე სადღაც, ჩვენ გვინდა, რომ იყოს ხელის ქვემოთ, NULL, ასე, რომ ჩვენ გვაქვს ეს Terminus ამ მონაცემების სტრუქტურას ასე ვიცით, სადაც ეს დამთავრდა. 

რა მოხდება, თუ ჩვენ გვინდა, რომ მანიპულირება ამ? ჩვენ ყველაზე მეტად ეს ვიზუალურად, და ადამიანები, მაგრამ რა, თუ ჩვენ გვსურს რომ Insertion? ასე რომ ორიგინალური სიაში იყო 9, 17, 20, 22, 29, 34. რა მოხდება, თუ ჩვენ მაშინ სურდა malloc ფართი ნომერი 55, node მას, და მაშინ ჩვენ გვინდა ჩადეთ 55 შევიდა სიაში, ისევე როგორც ჩვენ ორშაბათს? როგორ გავაკეთოთ ეს? ისე, ანიტა გამოვიდა და მან არსებითად დადიოდა სიაში. მან დაიწყო პირველი ელემენტს, მაშინ მომდევნო, შემდეგი, მომდევნო, შემდეგი, მომდევნო. საბოლოოდ მოხვდა მარცხენა ყველა გზა ქვემოთ და მივხვდი, ო, ეს არის NULL. მერე რა მაჩვენებელი მანიპულირება რამ არის გასაკეთებელი? პირი, რომელიც წლის ბოლომდე, ნომერი 34, საჭიროა მისი მარცხენა ხელის დააყენა აღვნიშნო ზე 55, 55 საჭიროა მათი მარცხენა მკლავი მიუთითებს ქვემოთ იყოს ახალი null terminator. შესრულებულია. Pretty მარტივი ჩადეთ 55 შევიდა დახარისხებული სია. და როგორ შეიძლება ამ გამოიყურებოდეს? 

ნება მომეცით წავიდეთ წინ და ქმნის ზოგიერთი კოდი მაგალითად აქ. მე გახსენით gedit და ნება მომეცით გახსენით ორი ფაილი პირველი. ერთი არის list1.h, და ნება მომეცით მხოლოდ შევახსენო, რომ ეს იყო ბლოკი კოდი რომ ჩვენ გამოიყენება წარმოადგენენ კვანძში. კვანძის გააჩნია როგორც int მოუწოდა N და კურსორი მოუწოდა შემდეგი, რომ მხოლოდ მიუთითებს შემდეგი რამ სიაში. სწორედ ახლა. თ ფაილი. რატომ? არსებობს ამ კონვენციით, და ჩვენ არ მიუღიათ უპირატესობა ამ უზარმაზარი თანხა თავს, მაგრამ ადამიანი, რომელიც წერდა printf და სხვა ფუნქციების მისცა, როგორც საჩუქარი მსოფლიოს ყველა იმ ფუნქციების წერა ფაილი სახელად stdio.h. და შემდეგ იქ string.h და შემდეგ იქ map.h, და იქ ყველა ამ თ ფაილები რომ თქვენ შეიძლება არ მინახავს ან დროს გამოყენებული ტერმინი წერილობითი სხვების მიერ. როგორც წესი იმ. თ ფაილები მხოლოდ რამ, როგორიცაა typedefs ან დეკლარაციები საბაჟო ტიპის ან დეკლარაციები მუდმივები. თქვენ არ დააყენოს ფუნქციები 'შესრულება in header ფაილი. თქვენ დააყენა, ნაცვლად, მხოლოდ მათი პროტოტიპები. თქვენ დააყენა რამ გსურთ გაუზიაროს მსოფლიოს, რაც მათ სჭირდებათ რათა შეადგინონ მათი კოდი. ასე რომ მხოლოდ შეღწევას ამ ჩვევა, გადავწყვიტეთ გავაკეთოთ იგივე. აქ არ ბევრი list1.h, მაგრამ ჩვენ დააყენა რაღაც რომ შეიძლება საინტერესო იყოს ხალხი მსოფლიოში ვისაც სურს გამოიყენონ ჩვენი დაკავშირებული სიაში განხორციელება. ახლა კი, list1.c, მე არ გადავიტან მთელი რამ იმიტომ რომ ცოტა გრძელია, ამ პროგრამით, მაგრამ მოდით გაუშვით უძრავი სწრაფად ბრძანებათა ზოლზე. ნება მომეცით კომპილაციის list1, ნება მომეცით მაშინ აწარმოებს list1, და რა თქვენ ნახავთ არის ჩვენ იმიტირებული მარტივი პატარა პროგრამა აქ რომ აპირებს, ნება მიბოძეთ დაამატოთ და ამოიღოთ ნომრის სიაში. ნება მომეცით, წავიდეთ წინ და ტიპის 3 მენიუ ვარიანტი 3. მინდა ჩადეთ ნომერი - მოდით პირველი ნომერი, რომელიც იყო 9, და ახლა მე განუცხადა სიაში არის 9. ნება მომეცით წავიდეთ წინ და ნუ სხვა Insertion, ამიტომ მოხვდა მენიუ ვარიანტი 3. რა რაოდენობის არ მინდა ჩადეთ? 17. შეიყვანეთ. და მე გავაკეთებ კიდევ ერთი. ნება მომეცით ჩადეთ ნომერი 22. ამიტომ დასაწყისი უკავშირდება სია რომ გვქონდა in slide ფორმა მომენტში წინ. როგორ ხდება ამ Insertion რეალურად ხდება? მართლაც, 22 არის დასასრულს სიაში. ასე ამბავი ვუთხარით სცენაზე ორშაბათს და recapped ახლა უნდა იყოს რეალურად ხდება კოდი. ავიღოთ სახეს. ნება მომეცით გადახვევა ქვემოთ ამ ფაილის. ჩვენ სიპრიალის მეტი ზოგიერთი ფუნქციების მაგრამ ჩვენ ქვევით რომ, ვთქვათ, ჩანართით ფუნქცია. 

ვნახოთ თუ როგორ წავიდეთ შესახებ ჩასმა new node ამ ბმის სიაში. სად არის სია გამოაცხადა? კარგად, მოდით გადახვევა ყველა გზა მდე ზედა, და შენიშნავს, რომ ჩემი უკავშირდება სია არსებითად განაცხადა, როგორც ერთი მაჩვენებელი, რომ თავდაპირველად null. ამიტომ მე გამოყენებით გლობალური ცვლადი აქ, რომელიც ზოგადად ჩვენ იქადაგა წინააღმდეგ რადგან ეს ქმნის თქვენს კოდი პატარა ბინძურ შენარჩუნება, ეს ერთგვარი ზარმაცი, როგორც წესი, მაგრამ ეს არ ეზარება და ეს არ არასწორი და ეს ცუდი არ თუ თქვენი პროგრამის ერთადერთი მიზანი ცხოვრებაში არის სიმულაცია ერთ დაკავშირებული სიაში. სწორედ იმას, რასაც ვაკეთებთ. ასე რომ, ვიდრე განაცხადოს ამ მთავარ და შემდეგ უნდა გაიაროს ეს ყველა ფუნქცია ჩვენ წერილობით ამ პროგრამაში, ჩვენ ნაცვლად გააცნობიეროს OH, მოდით უბრალოდ რათა ის გლობალური რადგან მთელი მიზნით ამ პროგრამის დემონსტრირება ერთი და მხოლოდ ერთი უკავშირდება სიაში. ასე რომ გრძნობს okay. აქ არის ჩემი პროტოტიპები, და ჩვენ არ გავლა ყველა ჩამოთვლილს, მაგრამ მე დავწერე წაშლა ფუნქცია, იპოვოს ფუნქციის ჩასმა ფუნქცია და ტრავერსზე ფუნქცია. მაგრამ მოდით ახლა დავუბრუნდეთ ქვემოთ ჩანართით ფუნქცია და ვნახავთ, როგორ ეს ერთი მუშაობს აქ. Insert არის ხაზზე - Here We Go. ჩანართით. ასე რომ, ეს არ მიიღოს ნებისმიერი არგუმენტაცია, რადგან ჩვენ ვაპირებთ ვთხოვოთ მომხმარებლის შიგნით ამ ფუნქციას ხმების სურთ ჩადეთ. მაგრამ პირველ რიგში, ჩვენ მოამზადოს რათა მათ გარკვეული ფართი. ეს არის ერთგვარი ასლი და პასტა მეორე მაგალითი. ამ შემთხვევაში, ჩვენ გამოყოფის int; ამჯერად ჩვენ გამოყოფის კვანძში. მე ნამდვილად არ გვახსოვს, რამდენი ბაიტი კვანძში არის, მაგრამ ეს ჯარიმა. Sizeof შეგიძლიათ გაერკვნენ, რომ ჩემთვის. და რატომ ვარ მე შემოწმების for null შეესაბამება 120? რა შეიძლება გადასვლა არასწორი შეესაბამება 119? ჰო? [სტუდენტური პასუხი, გაუგებარია] კარგი. უბრალოდ შეიძლება იყოს საქმე, რომ მე სთხოვა ძალიან ბევრი მეხსიერება ან რაღაც არასწორი და ოპერაციული სისტემა არ გააჩნია საკმარისი bytes რომ მომეცი, ასე რომ გვიჩვენებს იმდენი მიერ დაბრუნების NULL, და თუ მე არ ვამოწმებ, რომ და მე უბრალოდ ბრმად გაგრძელება გამოიყენოს მისამართი დაბრუნდა, შეიძლება იყოს null. ეს შეიძლება იყოს რაღაც უცნობი ღირებულება; არ კარგია, თუ არ მე - რეალურად არ იქნება უცნობი ღირებულება. ეს შეიძლება იყოს NULL, ამიტომ მე არ მინდა ბოროტად და რისკების dereferencing იგი. თუ ეს მოხდება, მე უბრალოდ დააბრუნოს და ჩვენ პრეტენზია მოსწონს მე არ დაუბრუნდება ნებისმიერი მეხსიერების ყველა. 

წინააღმდეგ შემთხვევაში, მე გეტყვით მომხმარებლის მომეცი ნომერი ჩასასმელად, მოვუწოდებ ჩვენი ძველი მეგობარი GetInt, და მაშინ ეს იყო ახალი სინტაქსის ჩვენ გააცნო ორშაბათს. 'Newptr-> n' ნიშნავს ეს მიმართვა, რომ თქვენ მიერ malloc რომელიც წარმოადგენს პირველ byte ახალი კვანძის ობიექტი, შემდეგ კი საველე მოუწოდა n. პატარა trivia კითხვა: ეს არის ეკვივალენტი რა უფრო cryptic ხაზი კოდი? როგორ შეიძლება სხვას მე არ წერია ეს? სურს stab? [სტუდენტური პასუხი, გაუგებარია] კარგი. გამოყენება. N, მაგრამ ეს არ საკმაოდ მარტივია, როგორც ეს. რა უნდა გავაკეთო? [სტუდენტური პასუხი, გაუგებარია] კარგი. მე უნდა გავაკეთოთ * newptr.n. ასე რომ, ეს ამბობს ახალი კურსორი არის აშკარად მისამართზე. რატომ? რადგან ეს იყო დაბრუნდა მიერ malloc. * Newptr რომ "იქ," და მაშინ ერთხელ თქვენ იქ, მაშინ შეგიძლიათ გამოიყენოთ მეტი ნაცნობი. N, მაგრამ ეს მხოლოდ გამოიყურება პატარა მახინჯი, განსაკუთრებით თუ ჩვენ ადამიანები აპირებენ მიაპყროს პოინტერები ისრებით ყველა დრო; მსოფლიოს სტანდარტიზებული ამ arrow ნოტაცია, რომელიც ზუსტად იმავეს. ასე, რომ თქვენ მხოლოდ -> ნოტაცია, როდესაც რამ მარცხენა არის კურსორი. წინააღმდეგ შემთხვევაში, თუ ის ფაქტობრივი struct, გამოიყენოს. N. და მაშინ ეს: რატომაა ინიციალიზაცია newptr-> შემდეგი null? ჩვენ არ გვინდა dangling მარცხენა გამორთვა ბოლომდე ეტაპზე. ჩვენ გვინდა ეს მიუთითებს სწორი down, რაც იმას ნიშნავს, ბოლომდე ამ ჩამონათვალს შესაძლოა იყოს ამ კვანძში, ამიტომ ჩვენ უკეთესი დარწმუნდით, რომ იგი null. და, ზოგადად, ინიციალიზაციისას თქვენი ცვლადები ან თქვენი მონაცემები წევრები და structs რაიმე არის მხოლოდ კარგი პრაქტიკის. Just გაქირავების ნაგვის არსებობს და კვლავაც იარსებებს ზოგადად იღებს თქვენ პრობლემები თუ თქვენ დაგავიწყდებათ, რომ რამე შემდგომში. 

აი რამდენიმე შემთხვევა. ეს, კიდევ ერთხელ, არის ჩანართით ფუნქცია, და პირველი, რასაც მე შევამოწმოთ არის თუ ცვლადში პირველი, რომ გლობალური ცვლადი არის NULL, რაც იმას ნიშნავს, რომ არ არსებობს უკავშირდება სიაში. ჩვენ არ შეიყვანეს ნებისმიერი ციფრები, ამიტომ ტრივიალური ჩასასმელად ამ მიმდინარე ნომერი შევიდა სიაში, რადგან ეს უბრალოდ ეკუთვნის დაწყების სიაში. ასე რომ, ეს იყო, როდესაც ანიტა უბრალოდ იდგა up აქ მარტო, pretending არავინ იყო აქ სცენაზე სანამ ჩვენ გამოყოფილი კვანძში, მაშინ მას შეეძლო დააყენებს თავის მხრივ პირველად, თუ ყველას ჰქონდა ამუშავება სცენაზე შემდეგ მისი ორშაბათს. ახლა აქ, ეს არის პატარა გამშვები სად უნდა ვთქვა, თუ ახალი კვანძის მისი ღირებულება N არის <ღირებულება N მიმდინარე პირველი კვანძი, ეს ნიშნავს, რომ არსებობს დაკავშირებული სიაში რომ დაწყებულია. არსებობს მინიმუმ ერთი კვანძის სიაში, მაგრამ ეს ახალი გაი ეკუთვნის სანამ, ამიტომ ჩვენ უნდა გადავიდეს რამ გარშემო. სხვა სიტყვებით, თუ სიაში დაიწყო უბრალოდ, ასე ვთქვათ, მხოლოდ ხმების 17, რომ - ფაქტობრივად, ჩვენ შეგვიძლია გავაკეთოთ ეს უფრო ნათლად. თუ ჩვენ დავიწყებთ ჩვენი ამბავი ერთად კურსორი აქ მოუწოდა პირველი, და თავდაპირველად ის NULL, და ჩვენ ჩადეთ ნომერი 9, ნომერი 9 ნათლად ეკუთვნის დაწყების სიაში. მოდით ვითომ ჩვენ უბრალოდ malloced მისამართი ან ნომერი 9 და განათავსოთ აქ. თუ პირველი არის 9 ჩვეულებრივ, პირველი სცენარი ჩვენ განვიხილეთ მხოლოდ იმას ნიშნავს, მოდით წერტილი ამ ბიჭს აქ, დატოვეთ როგორც NULL, ახლა ჩვენ გვაქვს ნომერი 9. შემდეგი ნომერი გვინდა ჩადეთ არის 17. 17 ეკუთვნის მეტი აქ, ამიტომ ჩვენ ვაპირებთ უნდა გავაკეთოთ გარკვეული ლოგიკური Stepping მეშვეობით. მოდით ნაცვლად, სანამ ჩვენ გავაკეთებთ, რომ, მოდით, ვიტყვი, რომ გვინდოდა ჩადეთ ნომერი 8. 

ასე რომ მხოლოდ მოხერხებულობის ის გულისთვის, მე ვაპირებ გავამახვილო აქ. მაგრამ გახსოვდეთ, malloc შეგიძლიათ განათავსოთ ეს ყველაზე მეტად არსად. მაგრამ ნახატის გულისთვის, მე ამას აქ. ასე ვიტყვი მე უბრალოდ გამოყოფილი კვანძის ამისთვის ნომერი 8; ეს NULL იყოს. რა არის უნდა მოხდეს? რამდენიმე რამ. ჩვენ მივიღეთ ეს შეცდომა სცენაზე ორშაბათს, სადაც ჩვენ ახლდება მაჩვენებელი მოსწონს, მაშინ ამ, და შემდეგ ჩვენ აცხადებდა - ჩვენ ობოლი ყველას სცენაზე. იმიტომ, რომ თქვენ can't - ბრძანებით ოპერაციების აქ მნიშვნელოვანია, რადგან ახლა ჩვენ დავკარგეთ ამ კვანძის 9 რომ მხოლოდ სახის მცურავი სივრცეში. ასე რომ, ეს არ იყო სწორი მიდგომა ორშაბათს. ჩვენ პირველი უნდა გავაკეთოთ რაღაც. სახელმწიფო მსოფლიოს ასე გამოიყურება. თავდაპირველად, 8 გამოყოფილი. რა იქნებოდა უკეთესი გზა ჩასმა 8? იმის ნაცვლად, რომ განახლებას ამ მაჩვენებელმა პირველი, უბრალოდ განაახლოთ ეს ერთი აქ ნაცვლად. ამიტომ ჩვენ გვჭირდება ხაზი კოდი, რომ აპირებს გახდეს ამ NULL ხასიათი შევიდა ფაქტობრივი მაჩვენებელი, ის მიუთითებს კვანძის 9, და მაშინ ჩვენ შეგვიძლია უსაფრთხოდ შეცვლის პირველი აღვნიშნო ამ ბიჭს აქ. ახლა ჩვენ გვაქვს სია, ბმის სია, ორი ელემენტები. და რას რეალურად გამოიყურებოდეს აქ? თუ დავაკვირდებით კოდი შეამჩნევთ, რომ მე ვაკეთებ ზუსტად რომ. მე განაცხადა newptr, და ამ ამბის, newptr იყო მიუთითებს ამ ბიჭს. 

ნება მომეცით, შევაჩერო კიდევ ერთი რამ, და მე უნდა წასულიყო ცოტა მეტი ოთახი ამისათვის. ასე რომ ვაპატიოთ პატარა პატარა ნახაზი. ამ ბიჭს ჰქვია newptr. სწორედ ცვლადი განვუცხადეთ რამოდენიმე ხაზს ადრე, ხაზი - მაღლა 25. და ეს მიუთითებს 8. ამიტომ როდესაც ვამბობ, რომ newptr-> შემდეგი, ეს ნიშნავს, რომ წასვლა struct რომ მიმდინარეობს მიუთითა მიერ newptr, ამიტომ აქ ვართ, იქ. მაშინ arrow ამბობს მიიღოს შემდეგი სფეროში და შემდეგ = ამბობს დააყენა რა ღირებულება არსებობს? ღირებულება, რომელიც იყო პირველი, რა ღირებულების იყო პირველი? პირველი იყო მიუთითებს ამ კვანძში, ისე, რომ ნიშნავს ეს უნდა აღვნიშნო ამ კვანძში. სხვა სიტყვებით, თუ რა გამოიყურება თუმცა სასაცილოა mess with ჩემი ხელწერა, რა მარტივი იდეა მხოლოდ მოძრავი ამ ისრებით გარშემო ითარგმნება როგორც კოდი და მხოლოდ ამ ერთი ლაინერი. მაღაზიის რა არის პირველი შემდეგი სფეროში და შემდეგ განაახლოს რა პირველი რეალურად არის. მოდით წავიდეთ წინ და სწრაფად წინსვლის გზით გარკვეული ამ, და მოუთმენლად მხოლოდ ამ კუდი Insertion ახლა. დავუშვათ, რომ მივიღო, რათა წერტილში, სადაც მე რომ შემდეგი სფეროში ზოგიერთი კვანძის არის NULL. და ამ დროისთვის ამბავი, დეტალურად რომ მე glossing მეტი ის არის, რომ მე გააცნო კიდევ ერთი მაჩვენებელი აქ შეესაბამება 142, წინამორბედის მაჩვენებელი. არსებითად, ამ დროისთვის ამბავი, ერთხელ სია იღებს ხანგრძლივი, I ტიპის უნდა სიარული ეს ორი თითი, რადგან თუ ასე შორს, მახსოვს ერთ სიგრძე სია, თქვენ ვერ მიდის უკან. ასე რომ, ეს იდეა predptr არის ჩემი მარცხენა თითი და newptr - არ newptr. კიდევ ერთი მაჩვენებელი, რომ აქ არის ჩემი სხვა თითი და მე უბრალოდ სახის ფეხით სია. ამიტომ, რომ არსებობს. მაგრამ მოდით მხოლოდ განიხილოს ერთი მარტივი შემთხვევებში აქ. თუ ეს მაჩვენებელი მომდევნო ველი NULL, რა ლოგიკური მნიშვნელობა? თუ თქვენ traversing ამ სიაში და თქვენ მოხვდა NULL მაჩვენებელი? თქვენ დასასრულს სია და ასე კოდი შემდეგ დამატება ამ ერთ დამატებით ელემენტს არის ერთგვარი ინტუიციური მიიღებს, რომ კვანძის რომლის შემდეგი კურსორი არის NULL, ასე რომ, ეს არის გაკეთებული NULL, და შეცვლის, თუმცა, უნდა იყოს მისამართი ახალი კვანძში. ასე რომ ჩვენ უბრალოდ ნახატის კოდი arrow რომ ჩვენ გაამახვილა სცენაზე მიერ ამაღლების ვინმეს მარცხენა ხელში. 

და საქმე რომ მე ტალღის ხელები დროს ახლა, მხოლოდ იმიტომ, რომ ვფიქრობ, ეს არის მარტივი დაკარგვა, როდესაც ჩვენ გავაკეთებთ ამ სახის გარემო, ამოწმებს ამისთვის Insertion საათზე სია ახლო. მაგრამ უბრალოდ ინტუიციურად, თუ რა სჭირდება რომ მოხდეს, თუ გსურთ გაერკვნენ სადაც ნომერი ეკუთვნის შუა არის თუ თქვენ ჩვენგან აქვს ფეხით იგი ერთზე მეტი თითი, ერთზე მეტი მაჩვენებელი, გაერკვნენ, სადაც მას ეკუთვნის მიერ შემოწმების არის ელემენტს <მიმდინარე ერთი, > მიმდინარე ერთი, და კიდევ თქვენთვის, რომ ადგილი, მაშინ თქვენ უნდა გავაკეთოთ ამ სახის ჭურვი თამაში, სადაც თქვენ გადატანა პოინტერები გარშემო ძალიან ფრთხილად. და რომ პასუხი, თუ გსურთ მიზეზი ამ სახლში საკუთარ, boils ქვემოთ მხოლოდ ამ ორი ხაზი კოდი, მაგრამ იმისათვის იმ ხაზები არის სუპერ მნიშვნელოვანია. რადგან თუ თქვენ დააგდოთ ვიღაცის ხელი და დასვას სხვისი არასწორი მიზნით, ერთხელ, თქვენ შეიძლება დასრულდეს up orphaning სიაში. შეჯამება უფრო კონცეპტუალურად, Insertion საათზე კუდი შედარებით მარტივია. Insertion სათავეში ასევე შედარებით მარტივია, მაგრამ თქვენ უნდა განაახლოთ დამატებითი მაჩვენებელი ამ დროს to squeeze ნომერი 5 შევიდა სიაში აქ, და შემდეგ Insertion შუა მოიცავს კიდევ უფრო მეტი ძალისხმევა, ძალიან ფრთხილად ჩადეთ ხმების 20 თავის სწორი მდებარეობის, რაც შორის 17 და 22. ასე, რომ თქვენ უნდა გავაკეთოთ მსგავსი რამ აქვს ახალი კვანძის 20 წერტილი 22, და შემდეგ, რაც node-ს მაჩვენებელი საჭიროებს ახლდება ბოლო? ეს 17, რეალურად ჩადეთ იგი. ასე რომ კიდევ ერთხელ, მე defer ფაქტობრივი კოდი კონკრეტულ განხორციელებაში. 

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

ფაქტობრივად, ვივარაუდოთ, რომ ჩვენ გადადონ უკავშირდება სიაში მომენტში და ჩვენ ნაცვლად გააცნო ცნება მაგიდასთან. და მოდით უბრალოდ ვფიქრობ მაგიდა მომენტში, როგორც მასივი. ეს მასივი და ამ შემთხვევაში აქ რაღაც 26 ელემენტებს, 0 მეშვეობით 25, და ვარაუდობენ, რომ თქვენ საჭირო ზოგიერთი ბლოკი შენახვისა და სახელები: Alice და ბობ და ჩარლი და მოსწონს. და თქვენ უნდა გარკვეული მონაცემები სტრუქტურის შესანახად იმ სახელები. ისე, თქვენ შეიძლება გამოიყენოთ რაღაც კავშირშია სია და თქვენ შეიძლება ფეხით სია ჩასმა Alice ადრე ბობ და ჩარლი შემდეგ ბობ და სხვ. და, ფაქტობრივად, თუ გვინდა, რომ კოდი მოსწონს, რომ როგორც განზე, ვიცი, რომ list2.h, ჩვენ ზუსტად რომ. ჩვენ არ გავლა ამ კოდექსით, მაგრამ ეს ვარიანტი პირველი მაგალითი რომ წარმოგიდგენთ ერთ სხვა struct ჩვენ ვნახეთ ადრე წოდებული სტუდენტი, და მერე რა ეს ფაქტიურად მაღაზიების დაკავშირებული სია მომცეთ სტუდენტი სტრუქტურა ვიდრე უბრალო პატარა რიცხვი, N. ასე რომ მიხვდებიან, იქ კოდი იქ რომ მოიცავს ფაქტობრივი სიმები, მაგრამ თუ მიზანი მხრივ ნამდვილად არის არის მივმართო ეფექტურობის პრობლემა, არ იქნება ლამაზი, თუ ჩვენ მოცემული ობიექტი მოუწოდა Alice, ჩვენ გვინდა დააყენა მისი სწორი მდებარეობის მონაცემები სტრუქტურის, იგი გრძნობს, როგორც ეს მინდა იყოს მართლაც ლამაზი უბრალოდ დააყენა Alice, რომლის სახელი იწყება, პირველ ადგილას. და ბობ, რომლის სახელი იწყება B, მეორე ადგილას. With მასივი, ან დავიწყოთ უწოდა მაგიდა, hash მაგიდაზე რომ, ჩვენ შეგვიძლია გავაკეთოთ ზუსტად რომ. თუ ჩვენ მოცემულია სახელი როგორიცაა Alice, სიმებიანი მოსწონს Alice, სად დააყენა-L-I-C-E? ჩვენ გვჭირდება hueristic. ჩვენ გვჭირდება ფუნქცია მიიღოს გარკვეული შეყვანის მოსწონს Alice და დაბრუნების პასუხი, "Put Alice ამ ადგილას." და ამ ფუნქციას, ამ შავი ყუთი, აპირებს ეწოდოს ქეშირების ფუნქცია. 

ქეშირების ფუნქცია არის ის, რასაც იღებს შეყვანის, როგორიცაა "Alice", და დაბრუნდა თქვენ, როგორც წესი, რიცხვითი საიდან ზოგიერთ მონაცემები სტრუქტურა, სადაც Alice ეკუთვნის. ამ შემთხვევაში, ჩვენი ქეშირების ფუნქცია უნდა იყოს შედარებით მარტივი. ჩვენი ქეშირების ფუნქცია უნდა ვთქვათ, თუ მოცემულია "Alice", რომელიც ხასიათი უნდა აღელვებს? პირველი. ასე რომ შევხედოთ [0], და მერე ამბობენ, თუ [0] ხასიათი არის, დაუბრუნოს ნომერი 0. თუ ეს B, დაბრუნდნენ 1. თუ C, დაბრუნდნენ 2 და სხვ. ყველა 0 ინდექსი, და რომ ნება მიბოძეთ ჩადეთ Alice და შემდეგ ბობ და შემდეგ ჩარლი და ა.შ. ამ მონაცემების სტრუქტურას. მაგრამ პრობლემა. რა მოხდება თუ ანიტა მოდის გასწვრივ კვლავ? სად ჩვენ ანიტა? მისი სახელი, ძალიან, იწყება წერილი, და ეს იგრძნობა ჩვენ გააკეთა უფრო დიდი ხმაური ამ პრობლემის. ჩვენ ახლა აქვს დაუყოვნებლივ Insertion, მუდმივი დროის Insertion, შევიდა მონაცემები სტრუქტურა ვიდრე უარესი-საქმის ხაზოვანი, მაგრამ რა გავაკეთოთ ანიტა ამ შემთხვევაში? რა არის ორი ვარიანტი, ნამდვილად? ჰო? [სტუდენტური პასუხი, გაუგებარია] Okay, ამიტომ ვერ აქვს კიდევ ერთი განზომილება. ეგ კარგია. ასე რომ ჩვენ შეგვიძლია ავაშენოთ რამ გარეთ 3D როგორც ჩვენ ვისაუბრეთ სიტყვიერი ორშაბათს. ჩვენ შეგვეძლო დაამატოთ კიდევ ერთი ხელმისაწვდომობის აქ, მაგრამ ვარაუდობენ, რომ არა, ვცდილობ, რომ ეს მარტივია. მთელი მიზანი აქ არის ჰქონდეს დაუყოვნებლივი მუდმივ დროში ხელმისაწვდომობა, ასე რომ დასძინა ძალიან ბევრი სირთულის. რა არის სხვა ვარიანტი, როცა ცდილობს ჩადეთ ანიტა შევიდა ამ მონაცემთა სტრუქტურას? ჰო? [სტუდენტური პასუხი, გაუგებარია] კარგი. ამიტომ ვერ გადავა ყველას down, მოსწონს ჩარლი nudges ქვემოთ ბობ და Alice, და შემდეგ ჩვენ დააყენა ანიტა სადაც იგი ნამდვილად სურს იყოს. 

რა თქმა უნდა, არის, აქ არის გვერდითი ეფექტი ამ. ეს მონაცემები სტრუქტურა ალბათ სასარგებლო არა იმიტომ, რომ სურთ ჩადეთ ხალხი ერთხელ არამედ იმიტომ, რომ ჩვენ გვინდა შევამოწმოთ, თუ ისინი იქ მოგვიანებით თუ ჩვენ გვინდა, რომ ამობეჭდოთ ყველა სახელების მონაცემები სტრუქტურა. ჩვენ ვაპირებთ, რომ რამე ამ მონაცემების საბოლოოდ. ახლა ჩვენ სახის ბრალია მეტი Alice, რომელიც აღარ სადაც მან უნდა იყოს. არც არის ბობ, არც არის ჩარლი. იქნებ ეს არ არის ისეთი კარგი იდეა. მაგრამ მართლაც, ეს არის ერთი ვარიანტი. ჩვენ შეგვეძლო გადაეტანა ყველას down, ან heck, ანიტა მოვიდა გვიან თამაში, რატომ არ ვართ, უბრალოდ დააყენა ანიტა არ აქ, არ აქ, არ აქ, მოდით უბრალოდ დააყენა მისი პატარა ქვედა სიაში. მაგრამ შემდეგ ეს პრობლემა იწყებს გადაეცემა ერთხელ. თქვენ შეიძლება იპოვოთ Alice მყისიერად, დაფუძნებული მისი სახელი. და ბობ მყისიერად, და ჩარლი. მაგრამ მაშინ თქვენ მოძებნით ანიტა, და ხედავთ, hmm, Alice არის გზა. ისე, ნება მომეცით შეამოწმოთ ქვემოთ Alice. Bob არ არის Anita. ჩარლი არ არის Anita. ოჰ, არსებობს Anita. და თუ გააგრძელებთ, რომ მატარებელი ლოგიკით ყველა გზა, რა უარესი გაშვებული დრო მოძიების ან ჩასმა ანიტა ამ ახალი სტრუქტურის მონაცემები? ეს O (N), არა? რადგან უარეს შემთხვევაში, არსებობს Alice, ბობ, ჩარლი. . . ყველა გზა ქვემოთ ვინმე "Y", ასე რომ, მხოლოდ ერთი ლაქა დატოვა. საბედნიეროდ, ჩვენ არ გვაქვს ერთი სახელწოდებით "Z", ამიტომ ჩვენ დააყენა ანიტა დროს ძალიან ბოლოში. 

ჩვენ ნამდვილად არ მოგვარდება, რომ პრობლემა. იქნებ ჩვენ უნდა გააცნოს ამ მესამე განზომილება. და თურმე, თუ ჩვენ ამ თანამედროვე მესამე განზომილება, ჩვენ არ შეგვიძლია ამის გაკეთება კარგად, მაგრამ წმიდა გრაალი იქნება მიღების მუდმივი დროში Insertion და დინამიური insertions ისე, რომ ჩვენ არ უნდა მყარი კოდი მასივი ზომა 26. ჩვენ ჩადეთ როგორც ბევრი სახელები, როგორც ჩვენ გვინდა, მაგრამ ავიღოთ ჩვენი 5 წუთიანი შესვენება აქ და მერე რომ სათანადოდ. ყველა უფლება. მე მითითებული ამბავი up საკმაოდ ხელოვნურად არსებობს არჩევით Alice და შემდეგ ბობ და შემდეგ ჩარლი და შემდეგ ანიტა, რომლის სახელი იყო აშკარად აპირებს collide ერთად Alice. მაგრამ კითხვაზე ჩვენ დასრულდა ორშაბათს ერთად არის, თუ რამდენად სავარაუდოა არის ეს რომ თქვენ მიიღოთ ამ სახის collisions? სხვა სიტყვებით, თუ ჩვენ დავიწყებთ გამოიყენოს ეს tabular სტრუქტურა, რომელიც რეალურად მხოლოდ მასივი, ამ შემთხვევაში 26 ადგილებში, ჩვენი საშუალებებით მათ ნაცვლად ერთნაირად ნაწილდება? ეს არ არის ხელოვნურად Alice და ბობ და ჩარლი და დავით და სხვ ალფავიტის, ის ერთნაირად გავრცელებული მეშვეობით ზ 

იქნებ ჩვენ უბრალოდ გაუმართლა და ჩვენ არ ვაპირებთ, რომ გვქონდეს ორი ან ორი B-ს ძალიან მაღალი ალბათობით, მაგრამ როგორც ვიღაცამ აღნიშნა, თუ ჩვენ განზოგადებული ეს პრობლემა და არ გააკეთებს 0 დან 25 მაგრამ, ვთქვათ, 0 მეშვეობით 364 ან 65, ხშირად ხმების დღე ტიპიური წელი, და კითხვას, "რა არის ალბათობა, რომ ორი ჩვენგანი ამ ოთახში აქვს იგივე დღე?" ამას სხვა გზა, რა ალბათობა, რომ ორი უნდა გვქონდეს სახელი იწყება? სახის შეკითხვა იგივეა, მაგრამ ამ მისამართზე სივრცეში, ამ ძებნის სივრცეში, მეტია იმ შემთხვევაში, დაბადების, იმიტომ, რომ ჩვენ ამდენი მეტი დღით წელიწადში ვიდრე შრიფტით ანბანი. რა არის ალბათობა შეჯახება? ასევე, ჩვენ შეიძლება ვიფიქროთ ამ მიერ მჭიდროდაა გარეთ მათემატიკის საპირისპირო გზა. რა არის ალბათობა არ collisions? ისე, ეს გამოთქმა აქ ნათქვამია, რომ რა ალბათობა თუ არსებობს მხოლოდ ერთი პირი ამ ოთახში, რომ მათ აქვთ უნიკალური დაბადების დღე? ეს 100%. რადგან თუ მხოლოდ ერთი პირი ოთახი, მისი დაბადების დღე შეიძლება იყოს ნებისმიერი 365 დღე გარეთ წელიწადში. ასე რომ 365/365 პარამეტრები მაძლევს ღირებულება 1. ამიტომ ალბათობა კითხვა მომენტში არის მხოლოდ 1. მაგრამ თუ არსებობს მეორე პირი ოთახი, რა ალბათობა, რომ მათი დაბადების დღე განსხვავებულია? არსებობს მხოლოდ 364 შესაძლო დღით, იგნორირება ნახტომი წლის, მათი დაბადების დღე არ collide ერთად სხვა პირები. ასე რომ 364/365. თუ მესამე პირი მოდის, ის 363/365 და ა.შ.. ამიტომ, ჩვენ შევინარჩუნოთ გამრავლებით ერთად ამ ფრაქციები, რომლებიც მიღების პატარა და პატარა, გაერკვნენ, რა არის ალბათობა, რომ ყველას უნდა გვქონდეს უნიკალური დაბადების? მაგრამ შემდეგ ჩვენ შეგვიძლია, რა თქმა უნდა, მხოლოდ მიიღოს, რომ პასუხი და Flip ირგვლივ და ნუ 1 მინუს ყველაფრისა, გამოხატვის ჩვენ საბოლოოდ მისაღებად თუ გახსოვთ უკან თქვენი მათემატიკის წიგნი, ეს გამოიყურება პატარა რაღაც მსგავსი, რომელიც ბევრად უფრო ადვილად ინტერპრეტირებული გრაფიკულად. და ამ გრაფიკული აქ უკვე შესახებ x ღერძი ხმების დაბადების, ან რაოდენობის მქონე ადამიანების დაბადების, და Y ღერძი არის ალბათობა მატჩი. და რა ამ ამბობს, რომ თუ თქვენ გაქვთ, ასე ვთქვათ, თუნდაც, მოდით ავირჩიოთ რაღაც 22, 23. თუ ის 22 ან 23 ადამიანი ოთახი, ალბათობა, რომ ორი იმ ძალიან ცოტა ხალხი აპირებს იგივე დაბადების დღე ფაქტიურად სუპერ მაღალი, combinatorially. 50% შანსები რომ კლასი მხოლოდ 22 ადამიანი, სემინარი, პრაქტიკულად, 2 იმ ადამიანების ვაპირებთ აქვს იგივე დღე. იმის გამო, რომ იქ ამდენი გზა, რომელიც შეგიძლიათ აქვს იგივე დღე. კიდევ უფრო უარესი, თუ გადავხედავთ მარჯვენა მხარეს გრაფიკი, იმ დროისთვის თქვენ გაქვთ კლასი 58 სტუდენტი მასში, ალბათობა 2 მქონე ადამიანები დაბადების დღე არის სუპერ, სუპერ მაღალი, თითქმის 100%. ახლა, რომ სახის გართობა ფაქტი ნამდვილ ცხოვრებაში. 

მაგრამ შედეგებზე, ახლა, მონაცემთა სტრუქტურები და შენახვის იმას ნიშნავს, რომ მხოლოდ ვთქვათ თქვენ გაქვთ ლამაზი, სუფთა, თანაბარი განაწილება მონაცემები და თქვენ დიდი საკმარისი მასივი, რათა შეწყობოდა bunch რამ არ ნიშნავს, თქვენ აპირებს მიიღოს ადამიანი უნიკალური ადგილებში. თქვენ აპირებს collisions. ასე რომ, ეს ცნება hashing, როგორც მას უწოდებენ, აღების შეყვანის როგორიცაა "Alice" და massaging მას რამდენიმე გზა და შემდეგ დავუბრუნდეთ პასუხი მოსწონს 0 ან 1 ან 2. დავუბრუნდეთ ზოგიერთ გამომავალი რომ ფუნქცია ხშირია ამ ალბათობა შეჯახება. ასე რომ როგორ შეგვიძლია გაუმკლავდეს იმ შეჯახებების? ისე, ერთის შემთხვევაში, შეგვიძლია იდეა, რომელიც შესთავაზა. ჩვენ შეგვიძლია მხოლოდ გადაეტანა ყველას ქვემოთ, ან იქნებ, ცოტა უფრო უბრალოდ, ვიდრე ნაბიჯი ყველას, მოდით უბრალოდ გადაადგილება ანიტა ბოლოში შესაძლებელი ადგილზე. ასე რომ, თუ Alice არის 0, ბობ არის 1, ჩარლი არის 2, ჩვენ უბრალოდ დააყენა ანიტა ზე საიდან 3. და ეს არის ტექნიკის მონაცემთა სტრუქტურების მოუწოდა ხაზოვანი probing. ხაზოვანი რადგან თქვენ მხოლოდ ფეხით ამ ხაზი, და თქვენ ერთგვარი საცდელი ამისთვის ხელმისაწვდომი ლაქების მონაცემთა სტრუქტურას. რა თქმა უნდა, ამ devolves შევიდა O (N). თუ მონაცემები სტრუქტურა მართლაც სრული, იქ 25 ადამიანი უკვე, და შემდეგ ანიტა მოდის გასწვრივ, მან მთავრდება რა იქნებოდა საიდან Z, და ეს ჯარიმა. იგი დღესაც ჯდება, და ჩვენ შეგვიძლია მოვძებნოთ მისი მოგვიანებით. 

მაგრამ ეს იყო ეწინააღმდეგება მიზანი სისწრაფეს რამ up. მერე რა რომ ჩვენ ნაცვლად გააცნო ამ მესამე განზომილების? რომ ტექნიკა ზოგადად მოუწოდა ცალკე chaining, ან მქონე ჯაჭვების. და რა hash მაგიდაზე ახლა არის, ამ tabular სტრუქტურა, თქვენი მაგიდა მხოლოდ მასივი პოინტერები. მაგრამ რა იმ პოინტერები აღვნიშნო, რომ არის გამოიცანით რა? უკავშირდება სიაში. მერე რა რომ ჩვენ საუკეთესო ორივე სამყაროს? ჩვენ ვიყენებთ კოლექტორები ამისთვის საწყის ინდექსები შევიდა მონაცემები სტრუქტურა ასე შეგვიძლია მომენტალურად წასვლა [0] [1], [30] ან სხვ, მაგრამ ისე, რომ ჩვენ გვაქვს გარკვეული მოქნილობა და ჩვენ შეგვიძლია ჯდება ანიტა და Alice და ადამ და ნებისმიერი სხვა სახელი, ჩვენ ნაცვლად ნება სხვა ღერძი იზრდება თვითნებურად. ჩვენ საბოლოოდ, როგორც ორშაბათს, აქვს, რომ ექსპრესიული შესაძლებლობების დაკავშირებული სიაში. ჩვენ შეგვიძლია იზრდება მონაცემები სტრუქტურა თვითნებურად. გარდა ამისა, ჩვენ შეგვიძლია მხოლოდ იმის უზარმაზარი 2 განზომილებიანი მასივი, მაგრამ ეს იქნება საშინელი სიტუაცია, თუ ერთი მწკრივების 2 განზომილებიანი მასივი არ არის დიდი საკმარისი დამატებითი პირი, რომლის სახელი ხდება იწყება ა ღმერთმა ნუ ქნას, რომ ჩვენ უნდა reallocate უზარმაზარი 2 განზომილებიანი სტრუქტურა მხოლოდ იმიტომ, რომ იქ ამდენი ადამიანი დაასახელა, განსაკუთრებით მაშინ, როდესაც იქ ასე ცოტა ადამიანი დაასახელა Z რაღაც. უბრალოდ იქნება ძალიან sparse მონაცემები სტრუქტურა. ასე რომ არ არის სრულყოფილი ნებისმიერი საშუალებით, მაგრამ ახლა ჩვენ სულ ცოტა აქვს უნარი დან მყისიერად მოვძებნოთ სადაც Alice ან ანიტა ეკუთვნის, მინიმუმ თვალსაზრისით ვერტიკალური ღერძი, და მაშინ ჩვენ უბრალოდ უნდა გადაწყვიტოს სად უნდა დააყენოს ანიტა ან Alice ამ ბმის სიაში. თუ ჩვენ არ აინტერესებს დახარისხება რამ, რამდენად სწრაფად შეგვეძლო ჩადეთ Alice შევიდა სტრუქტურა ასე? ეს მუდმივი დრო. ჩვენ ინდექსი შევიდა [0], და თუ არავის იქ, Alice მიდის დაწყების რომ უკავშირდება სიაში. მაგრამ ეს არ არის დიდი გარიგება. რადგან თუ ანიტა შემდეგ მოდის გასწვრივ ზოგიერთი მთელი რიგი ზომების მოგვიანებით, სადაც ამჯამად ანიტა ეკუთვნის? ისე, [0]. OOP. Alice უკვე რომ უკავშირდება სიაში. 

მაგრამ თუ ჩვენ არ აინტერესებს დახარისხება ეს სახელები, ჩვენ შეგვიძლია მხოლოდ გადაადგილება Alice მეტი, ჩადეთ ანიტა, მაგრამ რომ არის მუდმივი დრო. მაშინაც კი, თუ არსებობს Alice და ადამ და ყველა ეს სხვა სახელები, ეს ნამდვილად არ გადავიდა მათ ფიზიკურად. რატომ? იმიტომ, რომ ჩვენ უბრალოდ გააკეთეს აქ უკავშირდება სია, ვინც იცის იყო ეს კვანძების არიან მაინც? ყველა თქვენ უნდა გააკეთოთ გადაადგილება პური crumbs. ამოძრავეთ ისრები ირგვლივ, თქვენ არ უნდა ფიზიკურად გადაადგილება ნებისმიერი მონაცემების ირგვლივ. ასე რომ ჩვენ შეგვიძლია ჩადეთ ანიტა, იმ შემთხვევაში, მყისიერად. მუდმივი დრო. ასე რომ, ჩვენ გვაქვს მუდმივი დროში lookup და მუდმივი დროში ჩასმა ვინმეს მოსწონს Anita. მაგრამ სახის oversimplifying მსოფლიოში. რა მოხდება, თუ ჩვენ მოგვიანებით გვსურს მოვძებნოთ Alice? რა მოხდება, თუ ჩვენ მოგვიანებით გვსურს მოვძებნოთ Alice? რამდენი ნაბიჯების რომ აპირებს? [სტუდენტური პასუხი, გაუგებარია] სწორედ. რაოდენობის ხალხი წინაშე ალისა უკავშირდება სიაში. ასე რომ არ საკმაოდ სრულყოფილი, რადგან ჩვენი მონაცემები სტრუქტურას, კვლავ აქვს ამ ვერტიკალური ხელმისაწვდომობის და შემდეგ მას ეს დაკავშირებული სიები ჩამოკიდებული - ფაქტობრივად, მოდით არ დაიხევს ეს მასივი. იგი ამ ბმის სიები ჩამოკიდებული off ის რომ გამოიყურება პატარა რაღაც მსგავსი. მაგრამ პრობლემა ის არის, თუ Alice და ადამ და ყველა ეს სხვა სახელები დასრულდება მდე სულ უფრო და უფრო მეტი არსებობს, მოძიებაში ვინმეს შეიძლება დასრულდეს up აღების bunch of ნაბიჯები, bcause თქვენ უნდა traverse დაკავშირებული სიაში, რაც ხაზოვანი ოპერაცია. ასე ნამდვილად, მაშინ, Insertion დრო საბოლოოდ არის O (N), სადაც n რაოდენობის ელემენტების სიაში. გაყოფილი, მოდით თვითნებურად ეძახით m, სადაც m არის ხმების დაკავშირებული სიები რომ ჩვენ გვაქვს ამ ვერტიკალური ღერძი. სხვა სიტყვებით, თუ ჩვენ ნამდვილად ვივარაუდოთ, თანაბარი განაწილება სახელები, სრულიად არარეალურია. იქ აშკარად უფრო ზოგიერთი წერილებს, ვიდრე სხვები. 

მაგრამ თუ ჩვენ დავუშვათ მომენტში თანაბარი განაწილება, და ჩვენ n სულ ხალხს და მ სულ ჯაჭვების ჩვენს ხელთ არსებული, მაშინ სიგრძე თითოეული ამ ჯაჭვების სამართლიანად უბრალოდ იქნება სულ, N დაყოფილი ხმების ჯაჭვები. ამიტომ N / მ. მაგრამ აქ, სადაც ჩვენ შეიძლება ყველა მათემატიკურად ჭკვიანი. მ არის მუდმივი, რადგან არსებობს ფიქსირებული რიგი ამ. თქვენ აპირებს გამოაცხადოს თქვენი მასივი დასაწყისში, და ჩვენ არა ვართ resizing ვერტიკალური ღერძი. ზოგადად, რომ რჩება დაფიქსირდა. ეს მხოლოდ ჰორიზონტალური ღერძი, ასე ვთქვათ, რომ იცვლება. ასე რომ ტექნიკურად, ეს არის მუდმივი. ახლა, Insertion დრო არის საკმაოდ ბევრი O (N). ასე რომ ვერ გრძნობს ყველა, რომ ბევრად უკეთესი. მაგრამ რა არის ჭეშმარიტება აქ? ისე, მთელი ამ ხნის, კვირების განმავლობაში, ჩვენ ვამბობდით O (N ²). O (N), 2 x n ², - N, გაყოფილი 2. . . ech. უბრალოდ n ². მაგრამ ახლა, ამ ნაწილში სემესტრის ჩვენ შეგვიძლია დავიწყოთ ლაპარაკი რეალური მსოფლიოს კიდევ ერთხელ. და N / მ სრულიად სწრაფად, ვიდრე უბრალოდ n მარტო. თუ თქვენ გაქვთ ათასი სახელები და დაარღვიოს ისინი შევიდა მრავალი თაიგულების ასე, რომ თქვენ გაქვთ მხოლოდ ათი სახელები თითოეულ ამ ჯაჭვები, აბსოლუტურად ძებნას ათი რამ იქნება უფრო სწრაფად, ვიდრე ათასი რამ. და ა.შ. ერთი მომავალი პრობლემა კომპლექტი აპირებს დაუპირისპირდეს თქვენ ფიქრი ზუსტად, რომ მიუხედავად იმისა, yeah, asymptotically და მათემატიკურად, ეს მაინც მხოლოდ წრფივი, რომელიც sucks ზოგადად, როდესაც ცდილობს იპოვოს რამ. სინამდვილეში, ეს იქნება უფრო სწრაფად, ვიდრე, რომ რადგან ამ divisor. და ასე რომ ის კვლავ იქნება ამ ვაჭრობის საგანი და ამ კონფლიქტის შორის თეორია და რეალობა, და ერთი knobs დაიწყება გარდამტეხ ამ დროისთვის სემესტრის უფრო რეალობის ერთი, როგორც ჩვენ სახის მომზადება semster ბოლოს, როგორც ჩვენ წარმოგიდგინოთ სამყაროში ვებ პროგრამირება, აქ ნამდვილად, შესრულების აპირებს ითვლიან რადგან თქვენს მომხმარებლებს აპირებენ დაიწყოს გრძნობს და ვაფასებთ ცუდი დიზაინის გადაწყვეტილებები. 

მაშ როგორ დადიხართ შესახებ ახორციელებს დაკავშირებული - hash მაგიდასთან 31 ელემენტებს? და წინა მაგალითი იყო თვითნებურად შესახებ დაბადების. თუ ვინმეს დაბადების დღე 1 იანვრიდან ან 1 თებერვალს, ჩვენ დააყენა მათ ამ bucket. თუ ეს 2 იანვარი, 2 თებერვალს, 2 მარტს, ჩვენ დააყენა მათ ამ bucket. ამიტომ იყო 31. როგორ განაცხადოს hash მაგიდასთან? ეს შეიძლება იყოს საკმაოდ მარტივია, node * მაგიდასთან არის ჩემი თვითნებური სახელი მას, [31]. ეს მაძლევს 31 მითითებას კვანძების, და რომელიც საშუალებას აძლევს ჩემთვის აქვს 31 მითითებას უკავშირდება სიები მაშინაც კი, თუ იმ ჯაჭვების თავდაპირველად null. რა მინდა დააყენა თუ მინდა შესანახად "Alice", "ბობ", "ჩარლი"? ასევე, ჩვენ უნდა გადაიტანოთ იმ რამ სტრუქტურა რადგან ჩვენ გვჭირდება Alice აღვნიშნო, რომ ბობ, აღვნიშნო, რომ ჩარლი და სხვ. ჩვენ არ შეგვიძლია უბრალოდ სახელები მარტო ვარ, ამიტომ შეიძლება შეიქმნას ახალი სტრუქტურა მოუწოდა კვანძის აქ. 

რა არის ფაქტობრივი კვანძის? რა არის კვანძში ამ ახალ უკავშირდება სიაში? პირველი, რაც უწოდა სიტყვა, არის პირის სახელი. სიგრძე, სავარაუდოდ, უკავშირდება მაქსიმალური ადამიანის სახელი, რასაც არ უნდა არის, 20, 30, 40 სიმბოლო Crazy კუთხეში შემთხვევაში, და +1 არის რა? უბრალოდ ზედმეტი NULL ხასიათი, \ 0. ასე რომ, ეს არის კვანძის შესაფუთი "რაღაც" შიგნით თავისთავად მაგრამ ეს ასევე აცხადებს მაჩვენებელი მოუწოდა შემდეგი რათა შევძლოთ ჯაჭვის Alice to ბობ to ჩარლი და სხვ. შეიძლება იყოს NULL მაგრამ სულაც არ უნდა იყოს. ნებისმიერი კითხვები ამ hash მაგიდები? ჰო? [სტუდენტური სვამს კითხვას, გაუგებარია] მასივი - კარგი კითხვაა. რატომ არის ეს char სიტყვა მასივი, ვიდრე უბრალოდ char *? ამ გარკვეულწილად თვითნებური მაგალითად, მე არ მინდა მიმართო to malloc თითოეული ორიგინალური სახელები. მინდოდა განაცხადოს მაქსიმალური მეხსიერების სიმებიანი ასე რომ მე ვერ კოპირება შევიდა სტრუქტურა Alice \ 0 და არ უნდა გაუმკლავდეთ malloc და თავისუფალი და მოსწონს. მაგრამ მე ვერ გავაკეთებ, რომ თუ მინდოდა უფრო შეგნებული სივრცის გამოყენებაზე. კარგი კითხვაა. მოდით ცდილობენ განზოგადება მოშორებით ამ და ფოკუსირება დარჩენილ დღეს მონაცემები სტრუქტურების უფრო ზოგადად და სხვა პრობლემები, რომელიც ჩვენ შეგვიძლია გადავჭრათ გამოყენებით იგივე საფუძვლები მიუხედავად იმისა, რომ მონაცემები სტრუქტურების თავად შესაძლოა განსხვავდებოდეს მისი ცალკეული. 

გამოდის, კომპიუტერულ მეცნიერებაში, ხეები ძალზე გავრცელებულია. და შეგიძლიათ წარმოიდგინოთ, რომ ხე სახის მოსწონს ოჯახის ხე, სადაც რამდენიმე ფესვები, ზოგიერთი matriarch ან პატრიარქის, ბებიას ან ბაბუის ან ადრე თავში, ქვეშ, რომლებიც დედა და მამა ან ძმა სხვადასხვა ან ანალოგიური. ასე რომ ხე სტრუქტურა კვანძების და მას ბავშვები, ჩვეულებრივ 0 ან მეტი ბავშვი თითოეული კვანძის. და ზოგიერთი jargon რომ ხედავთ ამ სურათში აქ არის რომელიმე პატარა ბავშვები ან grandkids on კიდეები რომელთაც არ ისრებით გამომდინარე მათ, ეს ის ე.წ. ფოთლები, და ვინმეს შიგნით არის შიდა კვანძის; შეგიძლიათ ეძახით არაფერი გასწვრივ იმ ხაზები. მაგრამ ეს სტრუქტურა საკმაოდ საერთო. ეს ერთი პატარა თვითნებური. ჩვენ გვყავს ერთი შვილი მარცხენა, ჩვენ გვაქვს სამი შვილი მარჯვენა, ორი შვილი მარცხენა ქვედა. ასე რომ, ჩვენ შეიძლება ჰქონდეთ განსხვავებული ზომის ხეები, მაგრამ თუ ჩვენ დავიწყებთ standardize რამ, და თქვენ ალბათ გავიხსენოთ ამ საწყისი პატრიკ ს ვიდეო ორობითი ძებნა საწყისი წინა მოკლე შემოსული, ორობითი ძებნა არ უნდა განხორციელდეს მასივი ან ცალი მოხსენება დაფაზე. დავუშვათ, რომ თქვენ სურდა ჩაწეროთ თქვენი ნომრები უფრო დახვეწილი მონაცემები სტრუქტურა. თქვენ შეუქმნიდა ხე მოსწონს ეს. თქვენ შეიძლება კვანძის გამოცხადებული C, და რომ კვანძის შეიძლება ჰქონდეს არანაკლებ ორი ელემენტების შიგნით მას. ერთი ნომრის გსურთ შესანახად, და სხვა არის - კარგად, ჩვენ გვჭირდება კიდევ ერთი. სხვა არის მისი შვილი. ასე რომ აქ კიდევ ერთი მონაცემები სტრუქტურა. ამჯერად, node განისაზღვრება, როგორც შენახვის ნომერი N და შემდეგ ორი მაჩვენებლებს; მარცხენა ბავშვი და მარჯვენა შვილი. და ისინი არ თვითნებური. რა არის საინტერესო ამ ხეს? 

რა არის ნიმუში, როგორ ჩვენ ჩაუყარა ამ გამოსვლა ან როგორ პატრიკ ჩაუყარა მას თავის ვიდეო? ეს სახის აშკარაა, რომ არსებობს გარკვეული დახარისხება მიმდინარეობს აქ, მაგრამ რა მარტივი წესი? ჰო? [სტუდენტური პასუხი, გაუგებარია] Perfect. თუ ერთი შეხედვით ეს, ხედავთ პატარა ნომრები მარცხენა დიდი ციფრები, მარცხენა, მაგრამ ეს ეხება ყველა კვანძში. თითოეული კვანძის, მისი მარცხენა ბავშვის ნაკლები, და მისი უფლება ბავშვს აღემატება მას. რას ნიშნავს ახლა არის თუ მინდა მოვძებნო მონაცემები სტრუქტურა, ვთქვათ, ნომერი 44, მე უნდა იწყება root, რადგან როგორც ყველა ამ უფრო რთული მონაცემები სტრუქტურები არის, ჩვენ მხოლოდ მომცეთ ერთი რამ, დასაწყისია. და ამ შემთხვევაში, დასაწყისში არის root. ეს არ არის ბოლომდე მარცხენა, ეს root ამ სტრუქტურის. ასე რომ მე ვერ ვხედავ აქ 55 და მე ეძებს 44. რა მიმართულებით არ მინდა წასვლა? ისე, მე მინდა მარცხენა, რადგან ცხადია, რომ უფლება იქნება ძალიან დიდი. ასე რომ შეამჩნია აქ, თქვენ ერთგვარი კონცეპტუალურად chopping ხე ნახევარ რადგან თქვენ არასდროს ქვემოთ მარჯვენა მხარეს. ახლა მე აქედან 55 დან 33. ეს ძალიან მცირე რიგი. ვეძებ 44, მაგრამ ახლა ვიცი, თუ 44 არის ამ ხე, შემიძლია წასვლა აშკარად მარჯვნივ. ასე რომ ისევ, მე pruning ხე ნახევარ. ეს საკმაოდ ბევრი იდენტური კონცეპტუალურად to სატელეფონო წიგნი. ეს იდენტური რა გავაკეთეთ ერთად ნაშრომების დაფაზე, მაგრამ უფრო დახვეწილი სტრუქტურა, რომელიც საშუალებას გვაძლევს რეალურად გააკეთებს ამ გათიშე და დაიპყროთ მიერ დიზაინი ალგორითმი, და ფაქტობრივად, traversing სტრუქტურა მოსწონს - whoops. Traversing სტრუქტურის მსგავსი, სადაც ეს მხოლოდ "ამ გზით ან რომ გზა," ნიშნავს, რომ ყველა კოდი, რომელიც მოხრილი თქვენი აზრით, პირველ რიგში, როცა განმახორციელებელი ის ნაწილში ან გავლით იგი სახლში, ბინარული ძებნის გამოყენებით უკან დაბრუნების ან iteration, ეს ტკივილი კისრის. მოძებნა შუა ელემენტს, მაშინ ნუ თქვენი დამრგვალება ან ქვემოთ. 

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

ასე რომ კიდევ ერთი მონაცემები სტრუქტურის, რომ ჩვენ შეგვიძლია წარმოგიდგინოთ. ეს ერთი განკუთვნილია ერთი შეხედვით, თვალი cryptic, მაგრამ ეს ერთი საოცარი. ასე რომ, ეს მონაცემები სტრუქტურა მოუწოდა trie, trie, რომელიც მემკვიდრეობით სიტყვის მოძიება, რომელიც არ წარმოითქმის ხელახალი მცდელობა-Val, მაგრამ ეს რა მსოფლიოს მოუწოდებს ეს ყველაფერი. ცდილობს. T-r-i-e. ეს ხე სტრუქტურის გარკვეული, მაგრამ თითოეული კვანძების trie როგორც ჩანს, თუ რა? და ეს არის ცოტა დამაბნეველი რადგან სახის შემოკლებით. მაგრამ ეს ჰგავს ყოველ კვანძში ამ trie ფაქტიურად მასივი. და მიუხედავად იმისა, ავტორი ამ დიაგრამაზე არ უჩვენებია ის, ამ შემთხვევაში, ეს არის trie მონაცემები სტრუქტურა რომლის მიზანია ცხოვრების შესანახად სიტყვა მოსწონს-L-I-C-e ან B-o-B. და ამ გზით ამ მონაცემთა მაღაზიებში Alice და ბობ და ჩარლი და ანიტა და ა.შ. იგი იყენებს მასივი რომლის შესანახად ალისა trie, ჩვენ იწყება root node რომელიც ჰგავს მასივი, და მისთვის დაწერილი სტენოგრამის ნოტაცია. ავტორი გამოტოვებული abcdefg რადგან არ იყო სახელები, რომ. ისინი მხოლოდ აჩვენა M და P და T, მაგრამ ამ შემთხვევაში, მოდით გადავიდეს დაშორებით Alice და ბობ და ჩარლი ზოგიერთი სახელები, რომ აქ ხართ. Maxwell ფაქტიურად ამ დიაგრამაზე. ასე როგორ მოხდა ავტორი მაღაზიის M--x-W-e-L-მ? მან დაიწყო ძირეული კვანძის და წავიდა [M], ასე უხეშად 13, 13 ადგილმდებარეობა მასივი. შემდეგ იქიდან, არსებობს მაჩვენებელი. კურსორის წამყვან სხვა მასივი. იქიდან ავტორი ინდექსირებული შევიდა, რომ მასივი ზე საიდან, როგორც გამოსახული იქ ზედა მარცხენა, და შემდეგ მას მოჰყვა, რომ მომცეთ კიდევ ერთი მასივი, და წავიდა კურსორი at საიდან X. შემდეგ კი შემდეგი მასივი საიდან W, E, L, L, და ა.შ., და ბოლოს, მოდით რეალურად ვცდილობ მას გამოსახულება ამ. რას კვანძის ჰგავს კოდის? კვანძის წელს trie შეიცავს მასივი მითითებას მეტი კვანძების. მაგრამ ასევე რაღაც უნდა იყოს გარკვეული სახის ლოგიკური ღირებულების, მინიმუმ ამ განხორციელება. მე მოხდეს ეძახით is_word. რატომ? რადგან, როდესაც თქვენ ჩასმა მაქსველი, თქვენ არ ჩასმა არაფერი შევიდა ამ მონაცემთა სტრუქტურას. თქვენ არ წერილობით მ თქვენ არ წერა X. ყველა თქვენ აკეთებთ არის შემდეგ მითითებას. მაჩვენებელი, რომელიც წარმოადგენს M, მაშინ მაჩვენებელი, რომელიც წარმოადგენს, მაშინ მაჩვენებელი, რომელიც წარმოადგენს X, მაშინ W, E, L, L, მაგრამ, რაც თქვენ გჭირდებათ რომ გააკეთოთ დასასრულს არის ერთგვარი წასვლა, ჩეკი, მე მიაღწია ამ ადგილას. იყო სიტყვა, რომელიც დამთავრდა აქ მონაცემები სტრუქტურა. 

მერე რა trie მართლაც ივსება და ავტორმა წარმოადგინოს ამ terminuses პატარა სამკუთხედები. ეს მხოლოდ იმას ნიშნავს, რომ ის ფაქტი, ამ სამკუთხედის არის აქ, ამ ლოგიკური ღირებულება ჭეშმარიტი ნიშნავს თუ უკან in ხე, რაც იმას ნიშნავს სიტყვა სახელად მაქსველი არის ამ. მაგრამ სიტყვა foo, მაგალითად, არ არის ხე, რადგან თუ მე იწყება root node აქ ზედა, იქ არ არის ვ მაჩვენებელი, არ o მაჩვენებელი, არ o მაჩვენებელი. Foo არ არის სახელი ამ ლექსიკონი. მაგრამ ამის საპირისპიროდ, turing, t-U-r-i-n-გ. ისევ და ისევ, მე არ შესანახად t ან U ან R ან მე ან N ან გ. მაგრამ მე მაღაზიაში ამ მონაცემების სტრუქტურას ღირებულება ჭეშმარიტი გზა ქვევით აქ ამ კვანძში - ში ხე მიიღწევა ამ ლოგიკური ღირებულება is_word ჭეშმარიტი. ამიტომ trie არის სახის ამ ძალიან საინტერესო მეტა სტრუქტურა, აქ თქვენ ნამდვილად არ შენახვის სიტყვა თავად ამ სახის ლექსიკონის. იყოს ნათელი, თქვენ მხოლოდ ამ შენახვის დიახ ან არა, არ არსებობს სიტყვა, რომელიც დამთავრდა აქ. 

ახლა რა გავლენა? თუ თქვენ გაქვთ 150,000 სიტყვების ლექსიკონი, რომ თქვენ ცდილობთ მაღაზიის მეხსიერება გამოყენებით რაღაც კავშირშია სია, თქვენ აპირებთ აქვს 150,000 კვანძების თქვენი უკავშირდება სიაში. და მოძიებაში ერთი იმ სიტყვა ალფავიტის შეეძლო O (N) დროს. ხაზოვანი დრო. ეს იმ შემთხვევაში აქ trie, რა გაშვებული დრო მოძიებაში სიტყვა? თურმე სილამაზის აქ არის ის, რომ მაშინაც კი, თუ თქვენ გაქვთ 149.999 სიტყვა უკვე ამ ლექსიკონში, როგორც განხორციელდა ამ მონაცემთა სტრუქტურას, რამდენი დრო სჭირდება მოძებნის ან ჩადეთ კიდევ ერთი პირი, რომ, როგორც Alice, Alice? ისე, ეს მხოლოდ 5, შესაძლოა 6 ნაბიჯები გადმოკიდული ხასიათი. რადგან presense სხვა სახელების სტრუქტურის არ მიიღონ გზა ჩასმა Alice. უფრო მეტიც, მოძიებაში Alice ერთხელ არსებობს 150,000 სიტყვა ამ ლექსიკონი არ მიიღოთ თქვენს გზას მოძიებაში Alice ყველა, რადგან Alice არის. . . . . აქ, იმიტომ, რომ მე ი ლოგიკური მნიშვნელობა. და თუ არ არსებობს ლოგიკური მართალია, მაშინ Alice არ არის ამ მონაცემების სტრუქტურას სიტყვა. სხვა სიტყვებით, გაშვებული დრო მოძიებაში ნივთები და ჩასმა რამ ამ ახალ მონაცემები სტრუქტურა trie არის O of - ეს არ ნ. რადგან presense of 150,000 ადამიანი ვიზიტორების გავლენას Alice, როგორც ჩანს. მოდით ეძახით K, სადაც K არის მაქსიმალური სიგრძე სიტყვა ინგლისურ რაც, როგორც წესი, არა უმეტეს 20-რაღაც სიმბოლოებს. ასე რომ K არის მუდმივი. ამიტომ წმიდა გრაალი ჩვენ, როგორც ჩანს, არ არის ნაპოვნი ის არის, რომ საქართველოს trie, მუდმივი დრო ჩანართები, ამისთვის lookups, ამისთვის წაშლებს. რაოდენობის გამო, რამ უკვე სტრუქტურა, რომელიც კი არ არის ფიზიკურად არსებობს. ისევ და ისევ, ისინი მხოლოდ დასალაგებლად გადამოწმებული off, დიახ ან არა, ვიზიტორების ზეგავლენა მისი მომავალი ქრონომეტრაჟი. 

მაგრამ რაღაც უნდა იყოს დაჭერა, თორემ არ შეეწირა ამდენი დრო ყველა ამ სხვა მონაცემები სტრუქტურების უბრალოდ საბოლოოდ მისაღებად საიდუმლო ერთი რომ საოცარი. მერე რა ფასი ჩვენ გადამხდელი, რათა მივაღწიოთ ამ სიდიადე აქ? ფართი. ეს ის არის, მასიური. და მიზეზით, რომ ავტორი არ დაუსახელებია აქ შეამჩნევთ, რომ ყველა ამ საკითხზე, რომ გამოიყურებოდეს მასივები, იგი არ შეუდგენიათ დანარჩენი ხე, დანარჩენი trie, რადგან ისინი უბრალოდ არ შეესაბამება ამბავი. მაგრამ ყველა ამ კვანძების არიან სუპერ ფართო, და ყველა კვანძის in ხე იკავებს 26 ან რეალურად, შეიძლება 27 გმირები, რადგან ამ შემთხვევაში მე მათ შორის სივრცე აპოსტროფი ასე რომ ჩვენ შეგვეძლო apostrophized სიტყვა. ამ შემთხვევაში, ეს არის ფართო მასივები. ასე რომ მიუხედავად იმისა, რომ ისინი არ picutured, ამ იკავებს მასიური რაოდენობით RAM. რაც შესაძლოა ჯარიმა, especilly თანამედროვე ტექნიკა, მაგრამ ეს tradeoff. ჩვენ კიდევ უფრო ნაკლები დრო მიერ ხარჯვის მეტი სივრცე. ისე სად არის ამ ყველა აპირებს? ისე, მოდით - ვნახოთ აქ. მოდით აირჩიე ამ ბიჭს აქ. 

მჯერა, რომ ეს თუ არა, იმდენი fun როგორც C უკვე გარკვეული დრო არის, ჩვენ მიღწევის წერტილი სემესტრის სადაც დროა გადასვლას რამ უფრო თანამედროვე. Things შესახებ მაღალ დონეზე. და მიუხედავად იმისა, რომ მომავალ რამდენიმე კვირის ჩვენ კვლავ immerse საკუთარ თავს სამყაროში მაჩვენებლებისა და მეხსიერების მართვა მისაღებად, რომ კომფორტს რომელთანაც შეგვიძლია მაშინ დაეყრდნონ, ბოლოს თამაში არის საბოლოოდ გააცნოს, ირონიულად, არ ამ ენაზე. ჩვენ დახარჯოს, ისევე როგორც 10 წუთის ვსაუბრობთ HTML. ყველა HTML არის არის markup ენაზე და რა მარკირებას ენა არის ამ სერიის ღია ფრჩხილებში და დახურული ფრჩხილებში რომ ამბობენ "ეს თამამი" "ეს კურსივით '' ამ ორიენტირებული." ეს არ არის ყველა, რომ ინტელექტუალურად საინტერესო, მაგრამ სუპერ სასარგებლო. და ეს, რა თქმა უნდა omnipresent ამ დღეებში. მაგრამ რა ძლევამოსილი შესახებ სამყაროში HTML და ვებ პროგრამირების უფრო ზოგადად, აშენებს დინამიური რამ; წერა კოდი ენებს, როგორიცაა PHP ან Python ან Ruby ან Java ან C #. მართლაც, მიუხედავად თქვენი ენა არჩევანი, და გამოიმუშავებს HTML დინამიურად ვითარდება. გენერაცია რაღაც მოუწოდა CSS დინამიურად ვითარდება. კასკადური სტილების, რომელიც არის ასევე შესახებ ესთეტიკას. და ა.შ. მიუხედავად იმისა, დღეს, თუ მივდივარ გარკვეული ვებ როგორიცაა ნაცნობი Google.com, და მივდივარ სანახავად, დეველოპერი, იხილე წყარო, რომელიც იქნებ გავაკეთეთ ადრე, მაგრამ აპირებს იხილე წყარო, ამ პერსონალის ალბათ გამოიყურება საკმაოდ cryptic. მაგრამ ეს ფუძემდებლური კოდი, რომელიც ახორციელებს Google.com. ფრონტის ბოლომდე. და პრაქტიკულად ყველა ეს ფუმფულა ფისუნიაა ესთეტიკის პერსონალი. ეს არის CSS აქ. თუ მე შენარჩუნება სენსორული ქვემოთ ჩვენ კიდევ რამდენიმე ფერი კოდირებული პერსონალი. ეს არის HTML. Google-ის კოდი ჰგავს სასადილო, მაგრამ თუ რეალურად ქმნის სხვადასხვა ფანჯარაში, ვხედავთ ზოგიერთი სტრუქტურის ამ. თუ გავხსნა ეს ყველაფერი, შეამჩნევთ აქ, ეს უფრო იკითხება. ჩვენ ვაპირებთ ვხედავ სანამ ამ ხანგრძლივი tag, [სიტყვა] არის tag, HTML, თავი, სხეული, div, სკრიპტი, ტექსტის არე, span, ორიენტირებული, DIV. და ეს არის ასევე სახის cryptic ორიენტირებული ერთი შეხედვით, მაგრამ ყველა ამ mess შემდეგნაირად გარკვეული ნიმუშების, და განმეორებადი თარგების, ისე, რომ ერთხელ მივიღებთ საფუძვლებს ქვემოთ, თქვენ გექნებათ დაწერა კოდი მოსწონს და შემდეგ მანიპულირება კოდი მოსწონს გამოყენებით კიდევ ერთი ენა, მოუწოდა JavaScript. და JavaScript არის ენა, რომელიც ეშვება შიგნით ბრაუზერის დღეს ჩვენ ვიყენებთ on ჰარვარდის კურსები, ამისთვის რა თქმა სავაჭრო ინსტრუმენტი, რომელიც Google Maps იყენებს გადმოგცეთ მთელი bunch of დინამიურობა, Facebook გაძლევთ აჩვენოს მყისიერი სტატუსის განახლება, Twitter იყენებს გაჩვენოთ tweets მყისიერად. ყველა ამ ჩვენ დაიწყებს immerse ვდებთ სისტემაში მაგრამ იქ, ჩვენ უნდა გვესმოდეს, ცოტა რაღაც შესახებ ინტერნეტში. ეს კლიპი აქ არის მხოლოდ წუთიანი, და მოდით დავუშვათ ახლა ეს არის, ფაქტობრივად, როგორ ინტერნეტში მუშაობს teaser ამისთვის რა უნდა მოვიდეს. მე გაძლევთ "Warriors წმინდა." 

[♫ Slow გუნდისათვის მუსიკა ♫] [კაცი მთხრობელი] მან მოყვა გაგზავნა. With ოქმი ყველა საკუთარი. [♫ Faster ელექტრონული მუსიკა ♫] იგი მოვიდა სამყაროში cool ეკრანები, uncaring მარშრუტიზატორები, და საფრთხეები გაცილებით უარესი, ვიდრე სიკვდილი. ის სწრაფად. ის ძლიერი. ის TCP / IP, და ის მიიღო თქვენს მისამართზე. Warriors of Net. [Malan] მომავალ კვირას, შემდეგ. ინტერნეტი. ვებ პროგრამირებას. ეს არის CS50. [CS50.TV]