[เล่นเพลง]
เดวิดเจลัน: ทั้งหมดขวา
นี้เป็น CS50
นี่เป็นสัปดาห์ที่ห้าอย่างต่อเนื่องและเรา มีบางข่าวที่ดีและบางข่าวที่ไ​​ม่ดี
ดังนั้นข่าวดีก็คือว่า CS50 เปิดตัววันศุกร์นี้
ถ้าคุณต้องการที่จะเข้าร่วมกับเรา หัวไปยัง URL ปกติท​​ี่นี่
ข่าวที่ดียิ่งขึ้นบรรยายไม่มี มาจันทร์ที่ 13
น้อยข่าวที่ดีขึ้น แบบทดสอบศูนย์เป็นวันพุธหน้า
รายละเอียดเพิ่มเติมสามารถ พบที่ URL ที่นี่
และในอีกสองสามวัน เราจะเติมในช่องว่าง
ที่มีไปถึงห้องพัก ว่าเราจะได้ลิขสิทธิ์
ข่าวที่ดีคือว่ามีจะ จะทบทวนหลักสูตรกว้าง
เซสชั่นนี้มา วันจันทร์ในช่วงเย็น
ติดตามความคืบหน้าในการเรียนการสอนของ เว็บไซต์สำหรับสถานที่ตั้งและรายละเอียด
ส่วนถึงแม้ว่ามันจะ วันหยุดยังจะได้พบเช่นกัน
ข่าวที่ดีที่สุด, บรรยายวันศุกร์ถัดไป
ดังนั้นนี่คือเราประเพณี มีตามหลักสูตร
Just-- มันจะเป็นที่น่าตื่นตาตื่นใจ
คุณจะเห็นสิ่งที่ต้องการ โครงสร้างข้อมูลเวลาคงที่
และตารางแฮชและต้นไม้และพยายาม
และเราจะพูดคุยเกี่ยวกับปัญหาวันเกิด
ทั้งกลุ่มของสิ่งที่ รอวันศุกร์ถัดไป
ตกลง
แต่อย่างใด
>> ดังนั้นจำได้ว่าเราได้รับ มุ่งเน้นไปที่ภาพของสิ่งนี้
ภายในของหน่วยความจำคอมพิวเตอร์ของเรา
ดังนั้นหน่วยความจำหรือแรมที่โปรแกรม ที่มีอยู่ในขณะที่คุณกำลังใช้งานพวกเขา
ถ้าคุณคลิกสองครั้ง ไอคอนเพื่อรันโปรแกรมบางอย่าง
หรือดับเบิลคลิกที่ icon เพื่อเปิดไฟล์บาง
ก็โหลดจากฮาร์ดดิสก์ของคุณ ไดรฟ์หรือไดรฟ์ของรัฐที่มั่นคง
เป็น RAM, Random Access Memory ที่ มันอาศัยอยู่จนไฟดับลง
แล็ปท็อปฝาปิด หรือคุณออกจากโปรแกรม
>> ขณะนี้หน่วยความจำที่ของ ซึ่งคุณอาจจะมี
1 กิกะไบต์วันนี้ 2 กิกะไบต์, หรือแม้กระทั่งมากขึ้น
โดยทั่วไปจะวางออก สำหรับโปรแกรมที่กำหนด
ในการเรียงลำดับของรูปสี่เหลี่ยมผืนผ้านี้ รูปแบบความคิด
โดยเรามีสแต็คที่ด้านล่าง และพวงของสิ่งอื่น ๆ ที่ด้านบน
สิ่งที่ส่วนบนสุด ที่เราได้เห็นในภาพนี้
ก่อน แต่ไม่เคยพูดคุยเกี่ยวกับ เป็นส่วนข้อความที่เรียกว่า
ส่วนข้อความนี้เป็นเพียงวิธีแฟนซี พูดว่าศูนย์และคนที่
เขียนโปรแกรมคอมไพล์ที่แท้จริงของคุณ
>> ดังนั้นเมื่อคุณคลิกสองครั้งที่ Microsoft Word บน Mac หรือ PC ของคุณ
หรือเมื่อคุณเรียกจุดเฉือนมาริโอบน คอมพิวเตอร์ลินุกซ์ที่หน้าต่าง terminal ของคุณ
ศูนย์และคนที่แต่ง Word หรือมาริโอจะถูกเก็บไว้ชั่วคราว
ในแรมของคอมพิวเตอร์ของคุณในที่เรียกว่า ส่วนข้อความสำหรับโปรแกรมเฉพาะ
ด้านล่างที่จะไปเริ่มต้น และเตรียมข้อมูล
นี่คือสิ่งที่ต้องการตัวแปรทั่วโลก ที่เราได้ไม่ได้ใช้จำนวนมากของ
แต่ในโอกาสที่เราได้ มีตัวแปรทั่วโลก
หรือกำหนดสตริงแบบคงที่ เป็นรหัสที่ยากคำว่า "สวัสดี"
ที่ไม่ได้นำมาจากผู้ใช้ ที่ได้รับการกำหนดค่าตายตัวลงในโปรแกรมของคุณ
>> ตอนนี้ลงที่ด้านล่างเรา มีที่เรียกว่าสแต็ค
และกองป่านนี้เราได้รับ ใช้สำหรับสิ่งที่ชนิดของวัตถุประสงค์?
สิ่งที่สแต็คที่ถูกนำมาใช้ใช่หรือไม่
ใช่?
>> ผู้ชม: ฟังก์ชั่น
>> เดวิดเจลัน: สำหรับฟังก์ชั่น?
ในสิ่งที่เหมาะสมสำหรับฟังก์ชั่น?
>> ผู้ชม: เมื่อคุณเรียกฟังก์ชัน ข้อโต้แย้งที่จะถูกคัดลอกลงบนสแต็ค
>> เดวิดเจลัน: แน่นอน
เมื่อคุณเรียกฟังก์ชั่นของมัน ข้อโต้แย้งที่จะถูกคัดลอกลงบนสแต็ค
ดังนั้น X ใด ๆ หรือ Y หรือหรือข ที่คุณผ่านเข้ามาในฟังก์ชั่น
จะใส่ชั่วคราว ที่เรียกว่ากอง
เช่นเพียงหนึ่งใน Annenberg รับประทานอาหารถาดฮอลล์และยังมีสิ่ง
เช่นตัวแปรท้องถิ่น
ถ้าฟังก์ชัน foo หรือแลกเปลี่ยนของคุณ ฟังก์ชั่นมีตัวแปรท้องถิ่น
เช่นอุณหภูมิ, ทั้งสอง จบลงในกอง
ตอนนี้เราจะไม่พูดมากเกินไปเกี่ยวกับ พวกเขา แต่ตัวแปรสภาพแวดล้อมเหล่านี้
ที่ด้านล่างที่เราเห็นในขณะที่ที่ผ่านมาเมื่อ ผม futzing ที่แป้นพิมพ์หนึ่งวัน
และผมก็เริ่มเข้าถึงสิ่งที่ เช่น argv 100 หรือ argv 1,000
เพียง elements-- ลืม numbers-- แต่ที่
ไม่ควรที่จะเข้าถึงได้โดยฉัน
เราเริ่มเห็นบาง ขี้ขลาดสัญลักษณ์บนหน้าจอ
สิ่งเหล่านี้เป็นที่เรียกว่า ตัวแปรสภาพแวดล้อม
เช่นการตั้งค่าสำหรับโลกของฉัน หรือโปรแกรมสำหรับเครื่องคอมพิวเตอร์ของฉันไม่
ไม่เกี่ยวข้องกับที่ผ่านมา ข้อผิดพลาดที่เรากล่าวถึง
ทำพิษ, ที่ได้รับ รบกวนคอมพิวเตอร์ค่อนข้างน้อย
>> ตอนสุดท้ายในการมุ่งเน้นในวันนี้ เราในท้ายที่สุดจะได้ในกอง
นี้เป็นก้อนของหน่วยความจำอื่น
และพื้นฐานทั้งหมดนี้ หน่วยความจำเป็นสิ่งเดียวกัน
มันเป็นฮาร์ดแวร์เดียวกัน
เราเป็นแค่การจัดเรียงของ การรักษากลุ่มที่แตกต่างกัน
ของไบต์เพื่อวัตถุประสงค์ที่แตกต่างกัน
กองยังเป็นไปได้ที่ ตัวแปรและหน่วยความจำที่คุณร้องขอ
จากระบบปฏิบัติการ จะถูกเก็บไว้ชั่วคราว
>> แต่มีชนิดของปัญหา นี่เป็นภาพที่มีความหมาย
เราเรียงลำดับของการมีสอง เรือจะชนกัน
เพราะในขณะที่คุณใช้มากขึ้นและมากขึ้น ของสแต็คและในขณะที่เราเห็นในวันนี้
เป็นต้นในขณะที่คุณใช้มากขึ้นของ กองแน่นอนสิ่งเลวร้ายที่อาจเกิดขึ้น
และแน่นอนเราสามารถทำให้เกิดการที่ ตั้งใจหรือไม่ตั้งใจ
ดังนั้นที่น่าตื่นเต้นที่ผ่านมา เวลาเป็นโปรแกรมนี้
ซึ่งไม่ได้ให้บริการการทำงานใด ๆ นอกเหนือจากวัตถ​​ุประสงค์เพื่อแสดงให้เห็น
วิธีการที่คุณเป็นคนเลวจริงสามารถใช้ ประโยชน์จากข้อบกพร่องในโปรแกรมของใครบางคน
และใช้เวลามากกว่าโปรแกรมหรือแม้แต่ ระบบคอมพิวเตอร์ทั้งหมดหรือเซิร์ฟเวอร์
ดังนั้นเพียงแค่การได้อย่างรวดเร็วในเวลาสั้น ๆ คุณ สังเกตหลักที่ด้านล่างว่า
จะใช้เวลาในบรรทัดคำสั่ง ข้อโต้แย้งตาม argv
และมีการเรียกฟังก์ชัน f, เป็นหลักฟังก์ชันนิรนามที่เรียกว่า
ฉและมันก็ผ่านใน argv [1]
>> ดังนั้นไม่ว่าคำประเภทผู้ใช้ในที่ ให้หลังชื่อของโปรแกรมนี้
แล้วฟังก์ชั่นนี้ขึ้นโดยพลการ ด้านบน, F, ใช้เวลาในสตริงอาคาถ่าน *
ในขณะที่เราได้เริ่มต้นเพื่อหารือเกี่ยวกับ และมันก็เรียกมันว่า "บาร์".
แต่เราสามารถเรียกมันว่าอะไร
และจากนั้นจะประกาศภายใน ของ F, อาร์เรย์ของตัวอักษร
เรียกว่า c-- 12 ตัวอักษรดังกล่าว
>> ตอนนี้จากเรื่องราวที่ผมบอก ช่วงเวลาที่ผ่านมาที่ในหน่วยความจำ
คือ c หรือเป็นผู้ที่ 12 ตัวอักษรจะจบได้อย่างไร
เพียงเพื่อให้มีความชัดเจน
ใช่?
>> ผู้ชม: บนสแต็ค
>> เดวิดเจลัน: บนสแต็ค
ดังนั้น c คือตัวแปรท้องถิ่น
เราขอ 12 ตัวอักษรหรือ 12 ไบต์
ผู้ที่กำลังจะจบลง ที่เรียกว่าสแต็ค
ตอนนี้จนเป็นฟังก์ชั่นอื่น ๆ ที่จริงที่มีประโยชน์สวย
แต่เราไม่ได้ใช้จริงๆ มันเอง strncopy
มันหมายถึงการคัดลอกสตริง แต่ n ตัวอักษร n ตัวอักษรเท่านั้น
ดังนั้นตัวอักษรที่ n จะเป็น คัดลอกมาจากบาร์ในค
และวิธีการที่หลายคน?
ความยาวของบาร์
ดังนั้นในคำอื่น ๆ ที่ หนึ่งบรรทัด strncopy,
จะคัดลอก ได้อย่างมีประสิทธิภาพในบาร์ค
>> ตอนนี้เพียงชนิดของการคาดการณ์ คุณธรรมของเรื่องนี้
สิ่งที่เป็นปัญหาที่อาจเกิดขึ้นที่นี่?
แม้ว่าเรากำลังตรวจสอบความยาว บาร์และผ่านมันลงไปใน strncopy,
สิ่งที่ลำไส้ของคุณบอกคุณเป็น หักยังคงเกี่ยวกับโปรแกรมนี้?
ใช่?
>> ผู้ชม: ไม่รวม ห้องพักสำหรับอักขระ null
เดวิดเจลัน: ไม่รวม ห้องพักสำหรับอักขระ null
อาจแตกต่างจากใน การปฏิบัติที่ผ่านมาที่เราทำไม่ได้
มีให้มากที่สุดเท่าบวก 1 ถึง รองรับว่าอักขระ null
แต่ก็จะยิ่งแย่ไปกว่านั้น
อะไรที่เราไม่สามารถที่จะทำอย่างไร
ใช่?
>> ผู้ชม: [ไม่ได้ยิน]
เดวิดเจลัน: ที่สมบูรณ์แบบ
เราได้เขียนยาก 12 สวยพล
ที่เป็นไม่มาก ปัญหา แต่ความจริง
ที่เราไม่ได้ตรวจสอบว่า ความยาวของบาร์จะน​​้อยกว่า 12
ในกรณีที่มันเป็นไปได้ ปลอดภัยที่จะใส่ลงในหน่วยความจำ
เรียกว่าคที่เราได้รับการจัดสรร
แน่นอนถ้าบาร์ก็เหมือน 20 ตัวอักษรยาว
ฟังก์ชั่นนี้จะปรากฏขึ้นที่จะคัดลอก 20 ตัวอักษรจากแถบเป็นคจึง
การไม่น้อยกว่า 8 ไบต​​์ ว่ามันไม่ควรจะเป็น
นั่นคือความหมายที่นี่
>> ดังนั้นในระยะสั้นโปรแกรมหัก
ไม่ได้เป็นเรื่องใหญ่
บางทีคุณอาจจะได้รับความผิดส่วน
เรามีทุกข้อบกพร่องในโปรแกรม
เราทุกคนอาจจะมีข้อบกพร่อง ในโปรแกรมได้ในขณะนี้
แต่สิ่งที่เป็นความหมายหรือไม่
ดีที่นี่เป็นรุ่นที่ซูมในของ ภาพของหน่วยความจำของคอมพิวเตอร์ของฉันที่
นี่คือด้านล่างของสแต็คของฉัน
และแน่นอนที่ด้านล่างสุดเป็นสิ่งที่ เรียกว่ากองประจำแม่วิธีแฟนซี
ที่บอกว่าเป็นหลัก
เพื่อให้ใครก็ตามที่เรียกว่าฟังก์ชั่น ฉนั้นเรากำลังพูดถึง
ดังนั้นนี่คือด้านล่างของสแต็ค
ที่อยู่ผู้ส่งเป็นสิ่งที่ใหม่
มันเป็นเสมอ ได้เสมอในภาพที่
เราก็ไม่เคยเรียกความสนใจไปที่
เพราะมันจะเปิดออกทางคทำงานเป็น ว่าเมื่อฟังก์ชั่นหนึ่งเรียกร้องอื่น
ไม่เพียง แต่ทำข้อโต้แย้งที่ว่า ฟังก์ชั่นได้รับการผลักดันเข้าสู่กอง
ไม่เพียง แต่ทำหน้าที่ของท้องถิ่น ตัวแปรที่ได้รับการผลักดันเข้าสู่กอง
สิ่งที่เรียกว่าที่อยู่ผู้ส่ง นอกจากนี้ยังได้รับการวางลงบนสแต็ค
โดยเฉพาะถ้าสายหลักฟูหลักของ ที่อยู่ในความทรงจำของตัวเองบางสิ่งบางอย่างวัว
ได้อย่างมีประสิทธิภาพได้รับการวางลงบนสแต็ค เพื่อที่ว่าเมื่อเอฟจะทำรันมัน
รู้ที่จะกระโดดกลับไปในข้อความ ส่วนในการที่จะดำเนินการต่อการดำเนินงาน
>> ดังนั้นถ้าเราอยู่ที่นี่แนวคิด ในหลักแล้วฉได้รับเรียกว่า
วิธีการที่ไม่ฉรู้ว่าใคร กับการควบคุมมือกลับ?
ดีเล็ก ๆ น้อย ๆ นี้ เกล็ดขนมปังสีแดงที่นี่
เรียกว่าที่อยู่ผู้ส่งก็แค่ ตรวจสอบสิ่งที่เป็นที่อยู่ผู้ส่งที่?
โอ้ให้ฉันกระโดดกลับไปที่หลักที่นี่
และที่นิด ๆ หน่อย ๆ ของเปลือก,
เพราะศูนย์และคนที่ สำหรับหลักในทางเทคนิค
ขึ้นที่นี่ในส่วนของเทคโนโลยี
แต่นั่นเป็นความคิดที่ ฉ ก็มีที่จะรู้ว่า
ไปยังที่ที่การควบคุมในท้ายที่สุดกลับไป
>> แต่ทางคอมพิวเตอร์ ได้วางยาวออกสิ่ง
เช่นตัวแปรท้องถิ่นและ ข้อโต้แย้งที่เป็นเช่นนี้
ดังนั้นในด้านบนของภาพนี้ สีฟ้าเป็นกองกรอบสำหรับฉดังนั้นสิ่งที่
ของหน่วยความจำที่ฉ โดยเฉพาะคือการใช้
ดังนั้นจึงสังเกตเห็นว่า บาร์ที่อยู่ในภาพนี้
บาร์เป็นอาร์กิวเมนต์
และเราอ้างว่ามีปากเสียงกับ ฟังก์ชั่นได้รับการผลักดันเข้าสู่สแตก
และ C แน่นอนคือ ยังอยู่ในภาพนี้
>> และเพียงเพื่อวัตถุประสงค์สัญลักษณ์, สังเกตเห็นที่มุมซ้ายมือด้านบน
เป็นสิ่งที่จะเป็นควงเล็บ 0 และ แล้วลดลงเล็กน้อยไปทางขวา
คือ c วงเล็บ 11
ดังนั้นในคำอื่น ๆ ที่คุณสามารถจินตนาการ ว่ามีตารางของไบต์
นั่นเป็นครั้งแรกที่เป็น ด้านซ้ายด้านบนด้านล่างซึ่ง
เป็นวันสุดท้ายของผู้ที่ 12 ไบต์
>> แต่ตอนนี้พยายามที่จะไปข้างหน้าอย่างรวดเร็ว
เป็นเรื่องเกี่ยวกับสิ่งที่จะเกิดขึ้นถ้าเราผ่าน ในแถบสตริงที่ยาวกว่าค?
และเราไม่ได้ตรวจสอบว่า มันแน่นอนมากกว่า 12
ซึ่งเป็นส่วนหนึ่งของภาพนี้จะ ได้รับการเขียนทับโดยไบต์ 0, 1, 2, 3,
dot dot dot, 11, และจากนั้น ไม่ดี, 12, 13 ผ่าน 19?
สิ่งที่จะเกิดขึ้นที่นี่ ถ้าคุณสรุปจากการสั่งซื้อ
ที่ควงเล็บ 0 อยู่ด้านบน c และ 11 วงเล็บคือการจัดเรียงของลง
ไปทางขวาหรือไม่
ใช่?
>> ผู้ชม: ดีก็จะ ที่จะเขียนทับแถบ char *
>> เดวิดเจลัน: ใช่มันดูเหมือนว่า คุณกำลังจะเขียนทับบาร์ char *
และแย่กว่านั้นถ้าคุณส่งในระยะยาวจริงๆ สตริงคุณยังอาจเขียนทับอะไร
ที่อยู่ผู้ส่ง
ซึ่งอีกครั้งเช่นเดียวกับ เกล็ดขนมปังที่จะบอกโปรแกรมที่
จะกลับไปเมื่อฉ จะทำถูกเรียกว่า
>> ดังนั้นสิ่งที่คนเลวมักจะทำ คือถ้าพวกเขาเจอโปรแกรม
ว่าพวกเขากำลังอยากรู้อยากเห็นไม่ว่าจะเป็น ใช้ประโยชน์รถในลักษณะดังกล่าว
ที่เขาหรือเธอสามารถใช้ ประโยชน์จากข้อผิดพลาดที่
โดยทั่วไปพวกเขาไม่ได้รับ เหมาะสมในครั้งแรกนี้
พวกเขาก็เริ่มส่งตัวอย่างเช่น สตริงสุ่มเข้าไปในโปรแกรมของคุณ
ไม่ว่าจะที่แป้นพิมพ์ หรือตรงไปตรงมาพวกเขาอาจ
เขียนโปรแกรมเล็ก ๆ เพียง โดยอัตโนมัติสร้างสตริง
และเริ่มต้นการต่อสู้ในโปรแกรมของคุณโดย ส่งในจำนวนมากของปัจจัยการผลิตที่แตกต่างกัน
ที่มีความยาวที่แตกต่างกัน
>> ทันทีที่เกิดปัญหาโปรแกรมของคุณ นั่นคือสิ่งที่น่าทึ่ง
เพราะมันหมายความว่าเขา หรือเธอได้ค้นพบ
สิ่งที่น่าจะเป็นจริงข้อผิดพลาด
และแล้วพวกเขาจะได้รับความคิดสร้างสรรค์มากขึ้น และเริ่มต้นมุ่งเน้นมากขึ้นอย่างหวุดหวิด
เกี่ยวกับวิธีการใช้ประโยชน์จากข้อผิดพลาดที่
โดยเฉพาะอย่างยิ่งสิ่งที่เขาหรือเธออาจจะ ทำคือการส่งในกรณีที่ดีที่สุดครับ
ไม่มีเรื่องใหญ่
มันเป็นสตริงที่สั้นพอ
แต่สิ่งที่ถ้าเขาหรือเธอส่ง, และเราจะพูดคุยมันเป็น
โจมตี code-- ดังนั้นศูนย์ และคนที่ทำสิ่งที่
เช่น RM-RF ที่เอาทุกอย่าง จากฮาร์ดไดรฟ์หรือส่งสแปม
หรืออย่างใดโจมตีเครื่องหรือไม่
>> ดังนั้นหากแต่ละเหล่านี้ ตัวอักษรเพียงหมายถึง
แนวคิดการโจมตีการโจมตี การโจมตีการโจมตีบางรหัสที่ไม่ดี
ว่าคนอื่นเขียน แต่ ถ้าเป็นคนที่มีความฉลาดพอที่
ที่ไม่เพียง แต่รวมทั้งหมด ของผู้ RM RFS แต่ยัง
มีเพียงไม่กี่ไบต์สุดท้ายของเขาหรือเธอ เป็นตัวเลขที่สอดคล้อง
ไปยังที่อยู่ของเขา หรือรหัสการโจมตีของเธอเอง
ที่เขาหรือเธอผ่านไปในเวลาเพียง โดยการให้ที่พรอมต์ที่
คุณมีประสิทธิภาพสามารถหลอกคอมพิวเตอร์ เป็นสังเกตเห็นเมื่อเอฟจะทำรัน
โอ้ก็ถึงเวลาสำหรับผมที่จะกระโดด กลับไปอยู่กลับสีแดง
แต่เป็นเพราะเขาหรือเธอมีอย่างใด ซ้อนทับที่อยู่ผู้ส่งว่า
กับจำนวนของตัวเอง และพวกเขากำลังฉลาดพอ
จะมีการกำหนดค่าที่ จำนวนการอ้างอิงที่คุณ
เห็นในด้านบนสุด มุมซ้ายมือมี
ที่เกิดขึ้นจริงที่อยู่ในคอมพิวเตอร์ของ ความทรงจำของบางส่วนของรหัสการโจมตีของพวกเขา
คนเลวสามารถหลอกคอมพิวเตอร์ ในการดำเนินงานของเขาหรือรหัสของตัวเองของเธอ
>> และรหัสที่อีกครั้งสามารถเป็นอะไรก็ได้
มันเรียกว่าโดยทั่วไป รหัสเปลือกซึ่งเป็นเพียง
วิธีที่บอกว่ามันเป็นไม่ได้ โดยทั่วไปสิ่งที่ง่ายเป็น RM-RF
เป็นจริงอย่างที่ชอบทุบตี หรือโปรแกรมที่แท้จริงที่ทำให้เขา
หรือการควบคุมการเขียนโปรแกรมของเธอที่จะดำเนินการ สิ่งอื่นที่พวกเขาต้องการ
ดังนั้นในระยะสั้นนี้ทั้งหมด เกิดขึ้นจากความเป็นจริงง่ายๆ
ว่าปัญหานี้ไม่ได้เกี่ยวข้องกับการตรวจสอบ ขอบเขตของอาเรย์ของคุณ
และเนื่องจากทาง การทำงานของเครื่องคอมพิวเตอร์ก็คือพวกเขา
ใช้สแต็คจาก ได้อย่างมีประสิทธิภาพแนวคิด
ด้านล่างขึ้น แต่แล้วองค์ประกอบ คุณผลักดันลง stack เติบโตด้านบนลง
นี้เป็นปัญหาอย่างไม่น่าเชื่อ
ตอนนี้มีวิธีการทำงานรอบนี้
และตรงไปตรงมามีภาษาที่ ด้วยซึ่งในการทำงานรอบนี้
Java เป็นภูมิคุ้มกันเช่น กับปัญหานี้โดยเฉพาะอย่างยิ่ง
เพราะพวกเขาไม่ให้คำแนะนำ
พวกเขาไม่ให้คุณ ที่อยู่หน่วยความจำโดยตรง
ดังนั้นด้วยอำนาจที่เรามีนี้ ไปสัมผัสอะไรในหน่วยความจำ
ที่เราต้องการมาเป็นที่ยอมรับความเสี่ยงที่ดี
>> เพื่อให้ตาออก
ถ้าตรงไปตรงมาในเดือน หรือปีที่ผ่านมาที่ทุกเวลา
คุณอ่านเกี่ยวกับการแสวงหาผลประโยชน์บางอย่าง ของโปรแกรมหรือเซิร์ฟเวอร์
ถ้าคุณเคยเห็นคำใบ้ของสิ่งที่ เช่นการโจมตีหน่วยความจำล้น
หรือกองล้นเป็นประเภทอื่น ของการโจมตีที่คล้ายกันในจิตวิญญาณ
มากที่สุดเท่าที่เป็นแรงบันดาลใจที่เว็บไซต์ของ ชื่อถ้าคุณจะรู้ว่า
มันคือทั้งหมดที่พูดถึงเพียงแค่ ล้นขนาดของตัวอักษรบาง
อาร์เรย์หรือแถวบางมากกว่าปกติ
คำถามใด ๆ แล้วเกี่ยวกับเรื่องนี้?
ไม่ลองนี้ที่บ้าน
>> ขวาทั้งหมด
ดังนั้น malloc จึงห่างไกลได้รับใหม่ของเรา เพื่อนในการที่เราสามารถจัดสรรหน่วยความจำ
ที่เราไม่จำเป็นต้องรู้ ความก้าวหน้าที่เราต้องการเพื่อให้เราไม่ได้มี
รหัสยากที่เป็นของเรา หมายเลขโปรแกรมเช่น 12
เมื่อผู้ใช้บอกเราว่า ข้อมูลที่เขาหรือเธอต้องการที่จะป้อนข้อมูล
เราสามารถ malloc หน่วยความจำมากว่า
>> ดังนั้น malloc มันจะเปิดออกไป เท่าที่เราได้รับใช้มัน
อย่างชัดเจนเป็นครั้งสุดท้ายแล้ว พวกคุณได้ใช้มัน
สำหรับ GetString ไม่รู้สำหรับ หลายสัปดาห์ที่ผ่านมาทั้งหมดของหน่วยความจำ malloc ของ
มาจากการที่เรียกว่ากอง
และนี่คือเหตุผล GetString ตัวอย่างเช่น สามารถจัดสรรหน่วยความจำแบบไดนามิก
โดยไม่ทราบว่าสิ่งที่คุณกำลัง จะพิมพ์ล่วงหน้า
มือคุณกลับชี้ไปยังหน่วยความจำที่ และหน่วยความจำที่ยังคงของคุณเพื่อให้,
แม้หลังจาก GetString ผลตอบแทน
เพราะการเรียกคืนหลังจากที่ กองอยู่ตลอดเวลาจะขึ้นและลง
ขึ้นและลง
และเร็วที่สุดเท่าที่มันจะไป ลงนั่นหมายความว่าหน่วยความจำใด
ฟังก์ชันนี้ใช้ควร ไม่ได้นำมาใช้โดยคนอื่น
มันเป็นค่าขยะตอนนี้
>> แต่กองขึ้นที่นี่
และสิ่งที่ดีเกี่ยวกับ malloc คือ เมื่อ malloc จัดสรรหน่วยความจำขึ้นที่นี่
มันไม่ได้ส่งผลกระทบต่อการ ส่วนใหญ่โดยกอง
และเพื่อให้การทำงานใด ๆ ที่สามารถเข้าถึง หน่วยความจำที่ได้รับการ malloc'd,
แม้โดยฟังก์ชันเช่น GetString, แม้กระทั่งหลังจากที่มันจะถูกส่งกลับ
>> ตอนนี้การสนทนาของ malloc ฟรี
และแน่นอนคุณกฎ จะต้องเริ่มต้นการใช้
เป็นใด ๆ ทุกครั้งที่คุณใช้ malloc ใด ๆ คุณเองต้องใช้ฟรีในที่สุด
ในตัวชี้เดียวกันกับที่
ทุกครั้งที่เราได้รับการเขียนนี้ รถ, รหัสรถ, ด้วยเหตุผลหลายประการ
แต่คนที่ได้รับ โดยใช้ห้องสมุด CS50 ซึ่ง
ตัวเองเป็นอย่างจงใจ รถก็รั่วไหลของหน่วยความจำ
เวลาที่คุณเรียกว่า GetString ใด ๆ ในช่วงไม่กี่สัปดาห์ที่ผ่านมา
เรากำลังขอให้การดำเนินงานของ ระบบลินุกซ์สำหรับหน่วยความจำ
และคุณยังไม่เคยได้รับเมื่อมันกลับมา
และนี่คือไม่ได้ใน การปฏิบัติเป็นสิ่งที่ดี
>> และ Valgrind ซึ่งเป็นหนึ่งใน เครื่องมือที่นำมาใช้ใน Pset 4
เป็นข้อมูลเกี่ยวกับการช่วยให้คุณ ขณะนี้พบข้อบกพร่องเช่นนั้น
แต่โชคดีสำหรับ Pset 4 คุณไม่จำเป็นต้อง การใช้ห้องสมุด CS50 หรือ GetString
ดังนั้นข้อบกพร่องใด ๆ ที่เกี่ยวข้องกับหน่วยความจำ ในท้ายที่สุดจะเป็นของคุณเอง
>> ดังนั้น malloc เป็นมากกว่าเพียงแค่ สิ่งอำนวยความสะดวกเพื่อการนี​​้
เราสามารถจริงตอนนี้แก้ ปัญหาที่แตกต่างกันโดยพื้นฐาน
และพื้นฐานการแก้ปัญหามากขึ้น ได้อย่างมีประสิทธิภาพตามสัญญาสัปดาห์ที่ศูนย์ของ
ป่านนี้นี้เป็นที่เซ็กซี่ที่สุด โครงสร้างข้อมูลที่เราเคยมี
และโครงสร้างข้อมูลฉันหมายถึง วิธีการของหน่วยความจำ conceptualizing
ในทางที่ไปกว่าเพียงแค่การพูด, นี้เป็น int นี้เป็นถ่าน
เราสามารถเริ่มต้นที่จะจัดกลุ่มสิ่งต่างๆร่วมกัน
>> ดังนั้นอาร์เรย์มองเช่นนี้
และสิ่งที่เป็นกุญแจสำคัญในการเกี่ยวกับ อาเรย์ก็คือว่ามันจะช่วยให้คุณ
กลับไปกลับ chunks ของ หน่วยความจำซึ่งแต่ละ
เป็นไปได้ของประเภทเดียวกัน int, int, int, int หรือถ่าน, ถ่าน, ถ่าน,
ถ่าน
แต่มีข้อเสียไม่กี่
นี้ตัวอย่างเช่นเป็น อาร์เรย์ของหกขนาด
สมมติว่าคุณกรอกอาร์เรย์นี้กับหก หมายเลขแล้วด้วยเหตุผลอะไรก็ตาม
ผู้ใช้ของคุณต้องการที่จะให้ คุณเป็นจำนวนเจ็ด
คุณจะใส่มันได้หรือไม่
>> อะไรคือการแก้ปัญหาหากคุณมี สร้างอาร์เรย์ในกอง
เช่นเดียวกับสัปดาห์ สองสัญกรณ์ที่เราแนะนำ
ของวงเล็บที่มีจำนวนที่อยู่ภายในหรือไม่
ดีที่คุณได้มีหก ตัวเลขในกล่องเหล่านี้
สิ่งที่สัญชาตญาณของคุณจะเป็นอย่างไร
ที่คุณจะต้องการที่จะนำมันได้หรือไม่
>> ผู้ชม: [ไม่ได้ยิน]
>> เดวิดเจลัน: ขออภัย?
>> ผู้ชม: วางไว้ที่ปลาย
>> เดวิดเจลัน: วางไว้ที่ปลาย
ดังนั้นเพียงแค่ผ่านไปทางขวา ด้านนอกของกล่องนี้
ซึ่งจะดี แต่ก็ จะเปิดออกคุณไม่สามารถทำเช่นนั้นได้
เพราะถ้าคุณไม่ได้ถาม สำหรับก้อนของหน่วยความจำนี้
มันอาจจะโดยบังเอิญที่นี้ จะถูกใช้โดยบางตัวแปรอื่น ๆ
โดยสิ้นเชิง
คิดย้อนกลับไปหนึ่งสัปดาห์หรือดังนั้นเมื่อเราวาง ออก Zamyla และดาวินและเกบชื่อ
ในความทรงจำ
พวกเขาอย่างแท้จริง หลังการสำรองข้อมูล
ดังนั้นเราจึงไม่สามารถหลีกเลี่ยง เชื่อว่าของอะไรก็ตาม
ที่นี่สามารถใช้ได้สำหรับผมที่จะใช้
>> ดังนั้นอะไรที่คุณอาจทำอย่างไร
ดีเมื่อคุณตระหนักถึง ต้องอาร์เรย์ของขนาดเจ็ด,
คุณก็สามารถสร้าง อาร์เรย์ของขนาดเจ็ดแล้วใช้
สำหรับวงหรือวงในขณะที่ คัดลอกลงในอาร์เรย์ใหม่
แล้วอย่างใดเพียงกำจัด แถวนี้หรือเพียงแค่หยุดใช้มัน
แต่ที่ไม่ได้มีประสิทธิภาพโดยเฉพาะอย่างยิ่ง
ในระยะสั้นอาร์เรย์จะไม่ปล่อยให้ คุณแบบไดนามิกปรับขนาด
>> ดังนั้นบนมือข้างหนึ่งคุณจะได้รับ เข้าถึงโดยสุ่มซึ่งเป็นที่น่าตื่นตาตื่นใจ
เพราะมันช่วยให้เราทำในสิ่งที่ เช่นการแบ่งและพิชิต,
ค้นหา binary ทั้งหมดที่เราได้ พูดคุยเกี่ยวกับบนหน้าจอที่นี่
แต่คุณวาดตัวเองเข้าไปในมุม
เร็วที่สุดเท่าที่คุณจะตี ปลายแถวของคุณ
ที่คุณต้องทำมาก การดำเนินงานที่มีราคาแพง
หรือเขียนทั้งกลุ่มของรหัส ถึงตอนนี้จัดการกับปัญหาที่
>> ดังนั้นสิ่งที่ถ้าเรามีแทน สิ่งที่เรียกว่ารายการ
หรือรายการที่เชื่อมโยงโดยเฉพาะอย่างยิ่ง?
สิ่งที่ถ้าแทนที่จะต้อง สี่เหลี่ยมกลับไปกลับไปกลับ
เรามีรูปสี่เหลี่ยมที่ออกจากเล็ก ๆ น้อย ๆ บิตของห้องเลื้อยในระหว่างพวกเขา?
และแม้ว่าฉันได้วาดนี้ รูปภาพหรือดัดแปลงภาพนี้
จากหนึ่งในตำราที่นี่เพื่อจะกลับไป หลังเป็นระเบียบเรียบร้อยมากในความเป็นจริง
หนึ่งในสี่เหลี่ยมที่ อาจจะขึ้นที่นี่ในความทรงจำ
หนึ่งของพวกเขาอาจจะมีขึ้นที่นี่
กว่าที่นี่และอื่น ๆ
>> แต่ถ้าเราดึง ในกรณีนี้ลูกศร
ที่ใดเชื่อมโยงเหล่านี้ รูปสี่เหลี่ยมพร้อมกันไหม
อันที่จริงเราได้เห็นเทคนิค ชาติของลูกศร
สิ่งที่เรานำมาใช้ในเร็ว ๆ นี้ วันที่ใต้กระโปรงหน้ารถ
เป็นตัวแทนของลูกศร?
ตัวชี้ขวา?
>> ดังนั้นสิ่งที่ถ้าแทน เพียงแค่การจัดเก็บตัวเลข
เช่น 9, 17, 22, 26, 34, สิ่งที่ถ้าเราเก็บไว้ไม่ได้
เพียง แต่จำนวน แต่ตัวชี้ ติดกันจำนวนดังกล่าวหรือไม่
เพื่อให้เหมือนที่คุณจะด้าย เข็มผ่านทั้งกลุ่มของผ้า
สิ่งที่ผูกอย่างใด เข้าด้วยกันในทำนองเดียวกันสามารถ
เรามีคำแนะนำเป็น เกิดมาโดยลูกศรที่นี่
ชนิดของสานเข้าด้วยกัน สี่เหลี่ยมแต่ละบุคคลเหล่านี้
โดยมีประสิทธิภาพการใช้ตัวชี้ ถัดจากแต่ละหมายเลขที่
ชี้ไปที่บางหมายเลขถัดไปที่ ชี้ไปในทางกลับกันบางจำนวนต่อไปหรือไม่
ดังนั้นในคำอื่น ๆ สิ่ง ถ้าเราต้องการจริง
ในการดำเนินการบางอย่างเช่นนี้ได้อย่างไร
ดี แต่น่าเสียดายที่รูปสี่เหลี่ยมเหล่านี้ ที่หนึ่งอย่างน้อยกับ 9, 17, 22,
และอื่น ๆ เหล่านี้จะไม่มีอีกต่อไป สแควร์มีความสุขกับตัวเลขเดียว
ด้านล่างรูปสี่เหลี่ยมผืนผ้า ด้านล่าง 9 ตัวอย่างเช่น
แสดงให้เห็นถึงสิ่งที่ควร เป็นตัวชี้ 32 บิต
ตอนนี้ฉันยังไม่ทราบชนิดของข้อมูลใด ๆ ใน C ที่ช่วยให้คุณไม่เพียง แต่ int
แต่ชี้ไปโดยสิ้นเชิง
>> ดังนั้นสิ่งที่เป็นวิธีแก้ปัญหาถ้าเราต้องการ คิดค้นคำตอบของเราเองในการนี​​้หรือไม่?
ใช่?
>> ผู้ชม: [ไม่ได้ยิน]
>> เดวิดเจลัน: มีอะไรที่?
>> ผู้ชม: โครงสร้างใหม่
>> เดวิดเจลัน: ใช่ดังนั้นทำไม เราไม่สร้างโครงสร้างใหม่
หรือใน C struct?
เราได้เห็น structs ก่อนถ้าสั้น ๆ ที่เราจัดการกับโครงสร้างของนักเรียน
เช่นนี้ที่มีชื่อและที่บ้าน
ใน Pset 3 แหกคุกที่คุณใช้ทั้ง พวงของ GRect structs-- และ Govals
Stanford ที่สร้างขึ้นเพื่อ ข้อมูลกลุ่มเข้าด้วยกัน
ดังนั้นสิ่งที่ถ้าเราใช้เวลานี้ความคิดเดียวกันของ คำหลัก "typedef" และ "struct"
และแล้วสิ่งที่นักศึกษาที่เฉพาะเจาะจงบางอย่าง และพัฒนาให้เป็นดังต่อไปนี้
typedef struct node-- และโหนดเป็น เพียงวิทยาการคอมพิวเตอร์ทั่วไปมาก
คำบางสิ่งบางอย่างในโครงสร้างข้อมูล ภาชนะในโครงสร้างข้อมูล
โหนดฉันเรียกร้องเป็นไปได้ n int ตรงไปตรงมาโดยสิ้นเชิง
และแล้วความลับเล็ก ๆ น้อย ๆ , บรรทัดที่สองนี้ struct โหนด * ต่อไป
แต่ในแง่ทางเทคนิคน้อยกว่า สิ่งที่เป็นบรรทัดที่สองว่า
ของรหัสภายในวงเล็บปีกกา?
ใช่?
>> ผู้ชม: [ไม่ได้ยิน]
เดวิดเจลัน: ตัวชี้ไปยังโหนดอื่น
เพื่อให้เป็นที่ยอมรับไวยากรณ์ลับเล็ก ๆ น้อย ๆ
แต่ถ้าคุณอ่านมันอย่างแท้จริง ต่อไปคือชื่อของตัวแปร
เป็นประเภทของข้อมูลอะไร
มันเป็น verbose น้อยเวลานี้ แต่มันก็เป็นประเภทโหนด struct *
ทุกครั้งที่เราได้เห็นสิ่งที่ดาวที่ หมายความว่ามันเป็นตัวชี้ไปยังชนิดข้อมูลที่
ดังนั้นต่อไปคือเห็นได้ชัด ตัวชี้ไปยังโหนด struct
>> ตอนนี้สิ่งที่เป็นโหนด struct?
ดีสังเกตเห็นคุณเห็นเหล่านั้น คำเดียวกันที่ด้านบนขวา
และแน่นอนคุณยังเห็นคำว่า "โหนด" ลงที่นี่ที่ด้านล่างซ้าย
และนี้เป็นจริงเพียงแค่ความสะดวกสบาย
ขอให้สังเกตว่าในความหมายของเรานักเรียน มีคำว่า "นักเรียน" เพียงครั้งเดียว
และนั่นเป็นเพราะนักเรียน วัตถุที่เป็นตัวเองไม่ได้อ้างอิง
ไม่มีอะไรภายในของนักเรียนเป็น ที่ต้องการให้ชี้ไปที่นักเรียนคนอื่น
persay
ที่จะมีการจัดเรียงของ แปลกในโลกจริง
>> แต่ด้วยโหนดในการเชื่อมโยง รายการที่เราทำต้องการโหนด
จะอ้างอิงกับวัตถุที่คล้ายกัน
และเพื่อให้สังเกตเห็นความเปลี่ยนแปลงที่นี่ไม่ได้ เพียงแค่สิ่งที่อยู่ภายในวงเล็บปีกกา
แต่เราจะเพิ่มคำว่า "โหนด" ที่ด้านบนเช่นเดียวกับที่
เพิ่มที่ด้านล่าง แทน "นักเรียน".
และนี่เป็นเพียงรายละเอียดทางเทคนิค เพื่อให้อีกครั้งโครงสร้างข้อมูลของคุณ
สามารถเป็นตัวอ้างอิงเพื่อให้ โหนดสามารถชี้ไปยังอีกโหนดดังกล่าว
>> ดังนั้นสิ่งนี้เป็นที่สุด จะหมายถึงสำหรับเรา
ดีหนึ่งสิ่งนี้ภายใน เป็นเนื้อหาของโหนดของเรา
สิ่งนี้ขึ้นที่นี่ ขวาบนเป็นเพียงเพื่อให้
นั้นอีกครั้งเราสามารถอ้างกับตัวเอง
และแล้วสิ่งที่นอกสุด, แม้ว่าโหนดเป็นคำใหม่
บางทีก็ยังคง เช่นเดียวกับนักเรียนและสิ่งที่
เป็นใต้เครื่องดูดควันใน SPL
>> ดังนั้นถ้าตอนนี้เราอยากจะเริ่มต้น การดำเนินรายการที่เชื่อมโยงนี้
วิธีการที่เราอาจจะแปล บางสิ่งบางอย่างเช่นนี้จะรหัส?
ดีขอเพียงแค่เห็น ตัวอย่างของโปรแกรมที่
จริงใช้รายการที่เชื่อมโยง
ในรหัสการกระจายของวันนี้ เป็นโปรแกรมที่เรียกว่ารายชื่อศูนย์
และถ้าฉันทำงานนี้ฉันสร้างซุปเปอร์ GUI ง่ายอินเตอร์เฟซผู้ใช้แบบกราฟิก,
แต่มันเป็นความจริงเพียง printf
และตอนนี้ฉันได้รับตัวเองไม่กี่เมนู options-- ลบแทรกค้นหา
และการสำรวจ
และออกจาก
เหล่านี้เป็นเพียงการดำเนินงานร่วมกันใน โครงสร้างข้อมูลที่เรียกว่ารายการการเชื่อมโยง
>> ตอนนี้ลบเป็นไปได้ ลบหมายเลขจากรายการ
แทรกที่จะเพิ่ม จำนวนในรายการ
การค้นหาจะไปดู สำหรับจำนวนในรายการ
และการสำรวจเป็นเพียงวิธีแฟนซี พูดว่าเดินผ่านรายการ
พิมพ์ออกมา แต่ที่มัน
อย่าเปลี่ยนในทางใดทางหนึ่ง
>> ดังนั้นเรามาลองนี้
ให้เป็นไปข้างหน้าและพิมพ์ 2
แล้วฉันจะไป ใส่หมายเลขที่บอกว่า 9
ใส่
และตอนนี้โปรแกรมของฉันเป็นเพียง โปรแกรมที่จะบอกว่ารายการนี​​้ 9
ตอนนี้ถ้าผมไปข้างหน้าและ ไม่ใส่อีกครั้งให้
ฉันไปข้างหน้าและซูมออกและพิมพ์ 17
ตอนนี้รายชื่อของฉันคือ 9 แล้ว 17
ถ้าฉันจะใส่อีกครั้งให้ข้ามอย่างใดอย่างหนึ่ง
แทน 22, เป็นต่อรูปเราได้ รับการมองหาที่นี่ให้ฉันกระโดดไปข้างหน้า
และใส่ 26 ต่อไป
ดังนั้นฉันจะต้องพิมพ์ 26
รายการเป็นตามที่ผมคาดหวัง
แต่ตอนนี้เพียงเพื่อดูว่ารหัสนี้ เป็นไปได้ที่มีความยืดหยุ่นให้ฉันตอนนี้
22 ชนิดซึ่งอย่างน้อย แนวคิดถ้าเรา
รักษานี้แยกซึ่งเป็นที่แน่นอน จะเป็นเป้าหมายอื่นในขณะนี้
ควรจะไปในระหว่างวันที่ 17 และ 26
ดังนั้นผมจึงกด Enter
อันที่จริงที่ทำงาน
และดังนั้นตอนนี้ให้ฉันใส่ ที่ผ่านมาต่อภาพที่ 34
>> ขวาทั้งหมด
ดังนั้นสำหรับตอนนี้ให้ฉันระบุว่า ลบและการสำรวจและค้นหาทำ
ในความเป็นจริงการทำงาน
ในความเป็นจริงถ้าฉันจะเรียกใช้การค้นหาให้ ค้นหาหมายเลข 22, ใส่
พบ 22
เพื่อให้เป็นสิ่งนี้ โปรแกรมรายชื่อศูนย์ไม่
>> แต่สิ่งที่เป็นจริงที่เกิด ว่าการดำเนินการนี​​้
ดีแรกที่ผมอาจจะมีและแน่นอน ผมมีไฟล์ที่เรียกว่า list0.h
และที่ใดที่หนึ่งในนั้นคือ บรรทัด typedef โหนด struct,
แล้วฉันมีวงเล็บปีกกาของฉัน int n และ แล้ว struct-- สิ่งที่เป็นความหมายหรือไม่
โหนดโครงสร้างต่อไป
ดังนั้นเราจึงจำเป็นดาว
ตอนนี้ในทางเทคนิคเราจะได้เป็น นิสัยของการวาดภาพได้ที่นี่
คุณอาจเห็นตำราและ อ้างอิงออนไลน์ทำมันมี
มันเป็นหน้าที่เทียบเท่า
ในความเป็นจริงนี้เป็นเรื่องปกติน้อยมาก
แต่ฉันจะมีความสอดคล้องกับสิ่งที่ เราทำครั้งสุดท้ายและจะทำเช่นนี้
แล้วสุดท้ายที่ฉันจะทำเช่นนี้
>> ดังนั้นในไฟล์ส่วนหัว ที่ไหนสักแห่งใน list0.h
ในวันนี้คือความหมาย struct นี้ และบางทีบางสิ่งอื่น ๆ
ในขณะเดียวกันใน list0c มี จะเป็นสิ่งที่ไม่กี่
แต่เรากำลังจะไปเพียงแค่ เริ่มต้นและไม่จบนี้
List0.h เป็นไฟล์ที่ฉันต้องการ จะรวมอยู่ในแฟ้มของฉัน C
แล้วในบางจุดฉัน จะมี int, หลักเป็นโมฆะ
แล้วฉันจะไป มีบางสิ่งที่ต้องทำที่นี่
ฉันยังจะมี ต้นแบบเช่นโมฆะ, ค้นหา, int,
n วัตถุประสงค์ที่มีในชีวิตก็คือ เพื่อค้นหาองค์ประกอบ
แล้วลงมาที่นี่ฉันเรียกร้องใน รหัสของวันนี้เป็นโมฆะ, ค้นหา, int, n,
ไม่มีอัฒภาค แต่เปิดวงเล็บปีกกา
และตอนนี้ฉันต้องการที่จะค้นหาอย่างใด สำหรับองค์ประกอบในรายการนี​​้
แต่เราไม่ได้มีมากพอ ข้อมูลบนหน้าจอยัง
ฉันไม่ได้จริง แสดงรายชื่อของตัวเอง
ดังนั้นวิธีหนึ่งที่เราสามารถใช้ รายการที่เชื่อมโยงในโปรแกรม
เป็นชนิดของฉันต้องการที่จะทำอะไรบางอย่าง เช่นประกาศรายการที่เชื่อมโยงที่นี่
สำหรับความเรียบง่ายผมจะทำให้ นี้ทั่วโลกแม้ว่าในเราทั่วไป
ไม่ควรทำเช่นนี้มากเกินไป
แต่มันจะง่ายตัวอย่างนี้
ดังนั้นผมจึงต้องการที่จะประกาศ รายการขึ้นเชื่อมโยงที่นี่
ตอนนี้ฉันอาจจะทำเช่นนั้น?
>> นี่คือภาพของรายการที่เชื่อมโยง
และฉันไม่ได้จริงๆ ทราบว่าในขณะนี้ว่า
ฉันจะไปเกี่ยวกับการเป็นตัวแทนของ หลายสิ่งหลายอย่างที่มีเพียงหนึ่ง
ตัวแปรในหน่วยความจำ
แต่คิดว่ากลับไปสักครู่
ตลอดเวลาที่เราเคยมีนี้ สตริงซึ่งเราแล้ว
เห็นจะเป็นอาร์เรย์ของ ตัวละครซึ่งเราแล้ว
เผยให้เห็นถึงเพียงแค่เป็นตัวชี้ กับตัวอักษรตัวแรก
ในอาร์เรย์ของตัวอักษร ที่สิ้นสุด null
ดังนั้นโดยตรรกะที่และกับเรื่องนี้ ชนิดภาพของการเพาะความคิดของคุณ
เราจำเป็นต้องเขียนสิ่งที่จริงในบ้านเรา รหัสที่จะเป็นตัวแทนของรายการที่เชื่อมโยงหรือไม่
เท่าไหร่ของข้อมูลนี้เราต้อง ในการจับภาพในรหัส C คุณจะว่าอย่างไร
ใช่?
>> ผู้ชม: เราต้องชี้ไปยังโหนด
เดวิดเจลัน: ตัวชี้ไปยังโหนด
โดยเฉพาะอย่างยิ่งที่โหนดจะของคุณ สัญชาตญาณที่จะให้ตัวชี้ไปยัง?
>> ผู้ชม: โหนดแรก
>> เดวิดเจลัน: ใช่ อาจเป็นเพียงแค่ครั้งแรก
และสังเกตเห็นครั้งแรก โหนดเป็นรูปร่างที่แตกต่าง
มันเป็นเพียงครึ่งหนึ่งของขนาดของ struct, เพราะมันเป็นเรื่องจริงเพียงตัวชี้
ดังนั้นสิ่งที่คุณจริงสามารถทำได้คือการประกาศ รายการที่เชื่อมโยงไปเป็นชนิดโหนด *
และขอเรียกมันเป็นครั้งแรก และเริ่มต้นมันให้เป็นโมฆะ
ดังนั้น null อีกครั้งเป็นมา ในภาพที่นี่
ไม่เพียง แต่จะใช้เป็นโมฆะเช่นพิเศษ ค่าตอบแทนสำหรับสิ่งที่ต้องการ GetString
และ malloc, null ยังเป็นศูนย์ ตัวชี้ขาดของตัวชี้ที่
ถ้าคุณจะ
มันก็ไม่มีความหมายอะไรเป็นอีกที่นี่
ตอนแรกที่ผมจะได้ เรียกว่าอะไรที่นี้
ฉันจะได้เรียกมันว่า "รายการ" หรือจำนวนของสิ่งอื่นใด
แต่ฉันเรียกมันว่า "ครั้งแรก" เพื่อให้ เส้นมันขึ้นกับภาพนี้
ดังนั้นเช่นเดียวสตริงสามารถแสดง กับที่อยู่ของไบต์แรกของมัน
เพื่อให้สามารถเชื่อมโยงรายชื่อ
และเราจะเห็นข้อมูลอื่น ๆ โครงสร้างจะเป็นตัวแทน
ที่มีเพียงหนึ่งตัวชี้ ลูกศร 32 บิตชี้
ที่โหนดแรกมากในโครงสร้าง
>> แต่ตอนนี้เรามาคาดว่าจะมีปัญหา
ถ้าฉันเพียงความทรงจำ ในโปรแกรมของฉันอยู่
ของโหนดแรกแรก สี่เหลี่ยมผืนผ้าในโครงสร้างข้อมูลนี้
สิ่งที่ได้ดีกว่าเป็นกรณีที่เกี่ยวกับ การดำเนินการของส่วนที่เหลือของรายการของฉันได้อย่างไร
สิ่งที่เป็นรายละเอียดสำคัญที่จะ เพื่อให้แน่ใจว่านี้ใช้งานได้จริง?
และ "ใช้งานได้จริง" ผม หมายถึงมากเช่นสตริง
ช่วยให้เราไปจากตัวอักษรตัวแรก ในชื่อ Davin เพื่อที่สอง
สามเพื่อ ที่สี่จะสิ้นสุดมาก
ทำอย่างไรเราจะรู้ว่าเมื่อเราอยู่ในตอนท้าย ของรายการที่เชื่อมโยงที่มีลักษณะเช่นนี้หรือไม่?
เมื่อมันเป็นโมฆะ
และฉันได้เป็นตัวแทนของการจัดเรียงของเช่นนี้ เช่นวิศวกรอาจไฟฟ้า
กับดินเล็ก ๆ น้อย ๆ สัญลักษณ์แปลก ๆ
แต่นั่นก็หมายความว่าโมฆะในกรณีนี้
คุณสามารถวาดมันหมายเลขใด ๆ วิธี แต่ผู้เขียนคนนี้
ที่เกิดขึ้นในการใช้สัญลักษณ์นี้ที่นี่
>> ดังนั้นตราบใดที่เรากำลังคบ ทั้งหมดของโหนดเหล่านี้ร่วมกัน
เพียงความทรงจำที่ คนแรกเป็นเวลานาน
ในขณะที่เราใส่สัญลักษณ์พิเศษที่ โหนดสุดท้ายในรายการ
และเราจะใช้โมฆะเพราะนั่นคือ สิ่งที่เรามีให้กับเรา
รายการนี​​้เสร็จสมบูรณ์
และแม้ว่าฉันเท่านั้นที่ให้คุณได้ชี้ไปยัง องค์ประกอบแรกคุณ, โปรแกรมเมอร์
แน่นอนสามารถเข้าถึงส่วนที่เหลือของมัน
แต่ขอให้จิตใจของคุณ เดินนิด ๆ หน่อย ๆ
ถ้าพวกเขาไม่ได้อยู่แล้ว ค่อนข้าง wandered-- สิ่งที่
จะเป็นเวลาทำงานของ หาอะไรในรายการนี​​้หรือไม่?
ประณามมันก็โอใหญ่ของ n, ซึ่งไม่เลวในความเป็นธรรม
แต่มันเป็นเส้นตรง
เราได้รับค่าคุณลักษณะสิ่งที่ ของอาร์เรย์โดยการเคลื่อนย้ายมากขึ้น
ต่อภาพของแบบไดนามิกนี้ ทอด้วยกันหรือโหนดที่เชื่อมโยง?
เราได้รับการเข้าถึงแบบสุ่ม
อาเรย์เป็นสิ่งที่ดีเพราะ ทุกอย่างทางคณิตศาสตร์
กลับไปกลับไปกลับไปกลับ
แม้ว่าภาพนี้ ดูสวยและแม้แต่
แม้ว่ามันจะดูเหมือนว่าโหนดเหล่านี้ มีระยะห่างออกจากกันเป็นอย่างดีในความเป็นจริง
พวกเขาอาจจะที่ใดก็ได้
OX1, Ox50, Ox123, Ox99 เหล่านี้ โหนดอาจจะเป็นที่ใดก็ได้
เพราะ malloc ไม่จัดสรรหน่วยความจำ จากกอง แต่ที่ใดก็ได้ในกอง
คุณไม่จำเป็นต้องรู้ว่ามันเป็น จะเป็นหลังการสำรองข้อมูล
และเพื่อให้ภาพในความเป็นจริงนี้ จะไม่ได้ค่อนข้างสวยนี้
>> ดังนั้นมันจะใช้เวลาบิตของ ทำงานที่จะใช้ฟังก์ชั่นนี้
จึงขอใช้ค้นหาขณะนี้
และเราจะเห็นชนิดของ วิธีที่ฉลาดของการทำเช่นนี้
ดังนั้นหากผมมีฟังก์ชันการค้นหาและ ฉันได้รับตัวแปรจำนวนเต็ม n
ที่จะมองหาฉันจำเป็นต้องทราบ ไวยากรณ์ใหม่สำหรับการมองภายใน
ของโครงสร้างที่ ชี้ไปที่การหา n
ดังนั้นขอให้ทำเช่นนี้
>> ดังนั้นก่อนที่ฉันจะไป ข้างหน้าและประกาศโหนด *
และฉันจะเรียกมันว่า ตัวชี้เพียงโดยการประชุม
และฉันจะเริ่มต้นมันไปก่อน
และตอนนี้ฉันสามารถทำเช่นนี้ ในหลายวิธี
แต่ผมจะใช้วิธีการที่พบบ่อย
ในขณะที่ตัวชี้ไม่เท่ากับ null และที่ไวยากรณ์ที่ถูกต้อง
และมันก็หมายความว่าทำต่อไปเพื่อให้ ตราบใดที่คุณไม่ได้ชี้ไปที่อะไร
สิ่งที่ฉันต้องการจะทำอย่างไร
>> หากตัวชี้จุด n ให้ฉันกลับมา นั้น equals-- เท่ากับอะไร
สิ่งที่มีค่าที่ฉันกำลังมองหาอยู่
n จริงที่ถูกส่งผ่านไปใน
ดังนั้นนี่คือคุณสมบัติอื่น ของซีและหลายภาษา
แม้ว่าโหนดโครงสร้างที่เรียกว่า n มีค่าถูกต้องตามกฎหมายทั้งหมด
นอกจากนี้ยังมีการโต้แย้งในท้องถิ่น หรือที่เรียกว่าตัวแปร n
เพราะแม้เราด้วย ดวงตาของมนุษย์สามารถแยกแยะความแตกต่าง
ที่ n นี้สันนิษฐานว่า แตกต่างจาก n นี้
เพราะไวยากรณ์ที่แตกต่างกัน
คุณมีจุดและตัวชี้ ในขณะที่หนึ่งนี้มีไม่มีสิ่งนั้น
ดังนั้นนี่คือตกลง
ที่ตกลงจะเรียกพวกเขาในสิ่งเดียวกัน
>> ถ้าผมคุณจะพบนี้ฉัน จะต้องการที่จะทำบางสิ่งบางอย่าง
เช่นประกาศว่าเราพบ n
และเราจะออกจากที่เป็น แสดงความคิดเห็นหรือ pseudocode รหัส
อื่น ๆ และนี่คือ ส่วนที่น่าสนใจสิ่งที่
ฉันต้องการจะทำอย่างไรถ้าโหนดปัจจุบัน ไม่ได้มี n ที่ฉันดูแลเกี่ยวกับ?
ผมไม่ประสบความสำเร็จต่อไปได้อย่างไร
ถ้านิ้วของฉันที่ ขณะที่ PTR และก็
ชี้ไปที่สิ่งที่ ก่อนจะชี้ไปที่
ฉันจะย้ายนิ้วของฉัน ไปยังโหนดถั​​ดไปในรหัส?
ดีสิ่งที่เป็นเกล็ดขนมปังที่เรากำลัง จะทำตามในกรณีนี้หรือไม่?
ผู้ชม: [ไม่ได้ยิน]
เดวิดเจลัน: ใช่ดังนั้นต่อไป
ดังนั้นถ้าฉันกลับไปของฉัน รหัสที่นี่จริงฉัน
จะไปข้างหน้าและบอกว่าตัวชี้ที่ เป็นเพียงชั่วคราว variable-- มัน
ชื่อแปลก PTR แต่ ก็เช่นเดียวกับ temp--
ฉันจะตั้งตัวชี้ เท่ากับสิ่งที่ชี้ค่าเท่าใด
และครั้งนี้เป็นไปได้ รถเล็ก ๆ น้อย ๆ สำหรับจุด moment-- ต่อไป
ในคำอื่น ๆ ฉันจะใช้เวลาของฉัน นิ้วที่ชี้ไปที่โหนดนี้
ที่นี่และฉันจะบอกว่าคุณรู้ว่า สิ่งที่จะดูที่เขตข้อมูลถัดไป
และเลื่อนนิ้วของคุณไปยัง สิ่งที่มันชี้ไปที่
และสิ่งนี้เป็นไปได้ ซ้ำซ้ำซ้ำ
แต่เมื่อไม่นิ้วของฉัน หยุดการทำอะไรที่ทั้งหมดหรือไม่
เร็วที่สุดเท่าที่สิ่งที่บรรทัดของรหัสลูกมีอะไรบ้าง?
ผู้ชม: [ไม่ได้ยิน]
เดวิดเจลัน: ถ้าจุดในขณะที่ ชี้ไม่เท่ากับโมฆะ
ในบางจุดที่นิ้วของฉัน จะชี้ไปที่ null
และฉันจะตระหนักถึง นั่นคือจุดสิ้นสุดของรายการนี​​้
ตอนนี้เป็นเพียงเล็กน้อย โกหกสีขาวสำหรับความเรียบง่าย
แต่กลับกลายเป็นว่าแม้ว่าเรา เพียงแค่เรียนรู้สัญกรณ์จุดนี้
สำหรับโครงสร้างตัวชี้ไม่ struct
PTR คืออะไร?
เพียงเพื่อให้ nitpicky มากขึ้น
มันเป็นตัวชี้ไปยังโหนด
มันไม่ได้เป็นโหนดตัวเอง
ถ้าผมมีดาวที่นี่ชี้ absolutely-- ก็โหนด
นี้เป็นเหมือนหนึ่งสัปดาห์ การประกาศตัวแปร
แม้คำว่า "โหนด" เป็นของใหม่
>> แต่ทันทีที่เราแนะนำ ดาวก็ตอนนี้ตัวชี้ไปยังโหนด
และโชคร้ายที่คุณไม่สามารถใช้ สัญกรณ์จุดสำหรับตัวชี้
คุณต้องใช้ลูกศร สัญกรณ์ที่ยอดเยี่ยม
เป็นครั้งแรกที่ชิ้นส่วนใด ๆ ของไวยากรณ์มีลักษณะใช้งานง่าย
นี้อย่างแท้จริงมีลักษณะเหมือนลูกศร
และเพื่อให้เป็นสิ่งที่ดี
และลงมาที่นี่อย่างแท้จริง มีลักษณะเหมือนลูกศร
ดังนั้นผมคิดว่าเป็น la-- ที่ฉันทำไม่ได้ คิดว่าฉันเกินกระทำตรงนี้ฉัน
คิดว่าเป็นชิ้นใหม่ล่าสุด ของไวยากรณ์ที่เรากำลังจะไปดู
และโชคดีที่มันเป็นจริง เล็ก ๆ น้อย ๆ ได้ง่ายขึ้น
>> ตอนนี้สำหรับบรรดาของคุณที่ อาจจะชอบวิธีการแบบเก่าที่
คุณยังสามารถใช้สัญกรณ์จุด
แต่เป็นต่อวันจันทร์ การสนทนาครั้งแรกที่เรา
จำเป็นต้องไปที่นั่นไปที่ อยู่แล้วเข้าถึงข้อมูล
ดังนั้นนี้ยังเป็นที่ถูกต้อง
และตรงไปตรงนี้เป็น เล็ก ๆ น้อย ๆ อวดความรู้มากขึ้น
คุณอย่างแท้จริงกล่าวว่า dereference ตัวชี้และไปที่นั่น
แล้วคว้า .n ฟิลด์ที่เรียกว่า n
แต่ตรงไปตรงมาไม่มีใครต้องการ ที่จะพิมพ์หรืออ่านข้อความนี้
และเพื่อโลกที่คิดค้น สัญกรณ์ลูกศรที่
เป็นเทียบเท่าเหมือนกัน มันเป็นเพียงน้ำตาล syntactic
ดังนั้นวิธีที่จินตนาการของคำพูดนี้ ดูดีหรือมีลักษณะที่เรียบง่าย
>> ดังนั้นตอนนี้ฉันกำลังจะไปทำสิ่งอื่น ๆ ที่หนึ่ง
ฉันจะบอกว่า "หยุด" เมื่อฉันได้ พบว่ามันดังนั้นผมจึงไม่ให้มองหามัน
แต่นี้เป็นส่วนสำคัญ ฟังก์ชั่นการค้นหา
แต่มันง่ายมากที่ใน ท้ายที่สุดไม่ได้ที่จะเดินผ่านรห​​ัส
นี้คือการดำเนินการอย่างเป็นทางการแน่นอน ของการค้นหาในรหัสการกระจายของวันนี้
ผมกล้าพูดแทรกที่ไม่ได้ สนุกสนานโดยเฉพาะอย่างยิ่งที่จะเดินผ่าน
สายตาไม่เป็นลบได้ แม้ว่าในตอนท้ายของวันที่
พวกเขาต้มลงไปอย่างเป็นธรรม วิเคราะห์พฤติกรรมง่าย
>> ดังนั้นขอให้ทำเช่นนี้
ถ้าคุณจะขบขันผมมาที่นี่ผมได้ นำพวงของลูกความเครียด
ฉันนำพวงของตัวเลข
และสามารถที่เราได้รับอาสาสมัครเพียงไม่กี่ เพื่อเป็นตัวแทนของ 9, 17, 20, 22, 29, และ 34?
ทุกคนเพื่อเป็นหลัก คนที่นี่ในวันนี้
นั่นคือหนึ่งสองสาม สี่ห้าหกคน
และฉันได้รับการร้องขอให้ go-- เห็นไม่มี หนึ่งในด้านหลังยกมือของพวกเขา
ตกลงหนึ่งสองสามสี่ five-- ให้ฉันโหลด balance-- หก
ตกลงคุณหกมาขึ้น
เราจะต้องให้คนอื่น ๆ
เราได้นำลูกความเครียดเพิ่ม
และถ้าคุณสามารถทำได้สำหรับ เพียงแค่ช่วงเวลาที่สาย
ตัวเองขึ้นเพียง เช่นภาพนี้ที่นี่
>> ขวาทั้งหมด
ลองมาดูสิ่งที่เป็นชื่อของคุณ?
>> ผู้ชม: แอนดรู
>> เดวิดเจลัน: แอนดรู คุณมีจำนวน 9
มีความสุขที่ได้พบคุณ
ที่นี่คุณไป
ผู้ชม: เจน
เดวิดเจลัน: เจน
เดวิด
เลขที่ 17
ใช่?
>> ผู้ชม: ฉันจูเลีย
>> เดวิดเจลัน: จูเลียเดวิด
จำนวน 20
ผู้ชม: คริสเตียน
เดวิดเจลัน: คริสเตียนเดวิด
22
และ?
>> ผู้ชม: JP
เดวิดเจลัน: JP
29
เพื่อไปข้างหน้าและได้รับ in-- เอ่อโอ้
เอ่อโอ้
สแตนด์บาย
20
ไม่มีใครมีเครื่องหมาย?
ผู้ชม: ฉันมี Sharpie
เดวิดเจลัน: คุณมี Sharpie?
ตกลง
และทุกคนจะมีชิ้นส่วนของกระดาษหรือไม่
บันทึกการบรรยาย
มาใน
ผู้ชม: เราได้รับมัน
เดวิดเจลัน: เรามีมันได้หรือไม่
ขวาทั้งหมดขอขอบคุณ
ที่นี่เราไป
เป็นแบบนี้จากคุณ?
คุณเพียงแค่บันทึกวัน
ดังนั้น 29
ขวาทั้งหมด
ผมสะกดผิด 29 แต่ตกลง
ไปข้างหน้า
สิทธิทั้งหมดที่ฉันจะให้คุณ ปากกาของคุณกลับมาชั่วขณะ
ดังนั้นเราจึงมีคนเหล่านี้ที่นี่
Let 's มีคนอื่น ๆ
เกบ, คุณไม่ต้องการที่จะเล่น องค์ประกอบแรกที่นี่?
เราจะต้องการให้คุณชี้ ที่คนเหล่านี้ได้ดี
ดังนั้น 9, 17, 20, 22, การจัดเรียง วันที่ 29 และ 34 จากนั้น
เราได้สูญเสียใครบางคน?
ฉันจะมี 34
ที่ตกลง did-- ที่อยากจะเป็น 34?
ตกลงมาขึ้น 34
สิทธิทั้งหมดนี้จะเป็น อย่างคุ้มค่าที่สุด
คุณชื่ออะไร?
>> ผู้ชม: ปีเตอร์
>> เดวิดเจลัน: ปีเตอร์มาขึ้น
สิทธิทั้งหมดเพื่อให้ที่นี่เป็น ทั้งกลุ่มของโหนด
แต่ละพวกคุณแสดงให้เห็นถึง หนึ่งในสี่เหลี่ยมเหล่านี้
และเกบ, แปลกเล็กน้อย คนที่ออกมาแสดงเป็นครั้งแรก
ดังนั้นตัวชี้ของเขาเป็นเพียงเล็กน้อยที่มีขนาดเล็ก บนหน้าจอกว่าคนอื่น
และในกรณีนี้แต่ละด้านซ้ายของคุณ มือเป็นไปอย่างใดอย่างหนึ่งชี้ลง
จึงเป็นโมฆะดังนั้น เพียงแค่ขาดของตัวชี้ที่
หรือมันจะได้รับการชี้ ที่โหนดถั​​ดจากคุณ
>> ดังนั้นตอนนี้ถ้าคุณประดับ ตัวเองเหมือนภาพ
ที่นี่ไปข้างหน้าและจุดที่ ในแต่ละอื่น ๆ ที่มีเกบ
โดยเฉพาะอย่างยิ่งในการชี้ที่ หมายเลข 9 เพื่อเป็นตัวแทนของรายการ
ตกลงและหมายเลข 34, มือซ้ายของคุณ ควรจะเป็นเพียงการชี้ไปที่พื้น
>> ตกลงดังนั้นนี่คือรายการที่เชื่อมโยง
ดังนั้นนี่คือสถานการณ์ในคำถาม
และแน่นอนนี้เป็นตัวแทน ของชั้นของปัญหา
ที่คุณอาจพยายามที่จะแก้ปัญหาที่มีรหัส
คุณต้องการที่จะใส่ในท้ายที่สุด องค์ประกอบใหม่ในรายการ
ในกรณีนี้เรากำลังจะไป พยายามใส่หมายเลข 55
แต่มีจะเป็น กรณีที่แตกต่างกันที่จะต้องพิจารณา
และแน่นอนนี้จะเป็นหนึ่งใน ของภาพใหญ่ประเด็นที่นี่คือ
สิ่งที่เป็นกรณีที่แตกต่างกัน
สิ่งที่แตกต่างกันถ้าเงื่อนไขหรือ สาขาที่โปรแกรมของคุณอาจจะมี?
>> ดีหมายเลขที่คุณกำลังพยายามที่จะ แทรกซึ่งเรารู้ว่าตอนนี้จะเป็น 55,
แต่ถ้าคุณไม่ทราบ ล่วงหน้าผม daresay
ตกอยู่ในอย่างน้อยสาม สถานการณ์ที่เป็นไป
ที่อาจจะเป็นองค์ประกอบใหม่เป็นอย่างไร
ผู้ชม: และสิ้นสุดหรือตรงกลาง
เดวิดเจลัน: ในตอนท้ายใน กลางหรือที่จุดเริ่มต้น
ดังนั้นผมจึงเรียกร้องว่ามีอย่างน้อย สามปัญหาที่เราต้องแก้
ลองเลือกสิ่งที่อาจจะ เนื้อหาที่ง่ายที่สุด
หนึ่งที่องค์ประกอบใหม่ เป็นที่จุดเริ่มต้น
ดังนั้นฉันจะมีรหัสที่ค่อนข้าง เช่นการค้นหาที่ฉันเพิ่งเขียน
และฉันจะมี PTR ซึ่ง ผมจะเป็นตัวแทนของที่นี่ด้วยนิ้วของฉัน
ตามปกติ
>> และจำไว้ว่าค่าสิ่งที่ พวกเราเริ่มต้น PTR ไป?
ดังนั้นเราจึงเริ่มต้นมันเป็นโมฆะแรก
แต่แล้วสิ่งที่เราทำเมื่อเรา อยู่ภายในฟังก์ชันการค้นหาของเราหรือไม่
เราตั้งค่าเท่ากับครั้งแรก ซึ่งไม่ได้หมายความว่าการทำเช่นนี้
หากฉันตั้ง PTR เท่ากับครั้งแรกสิ่งที่ ควรมือของฉันจริงๆจะชี้ไปที่?
ขวา
ดังนั้นถ้าเกบและฉันจะไป จะต้องมีค่าเท่ากันที่นี่
เราต้องไปที่จุดทั้งที่บ้านเลขที่ 9
>> ดังนั้นนี่คือจุดเริ่มต้นของเรื่องราวของเรา
และตอนนี้เป็นที่ตรงไปตรงมาเพียง แม้ว่าไวยากรณ์เป็นของใหม่
แนวคิดนี้เป็นเพียงการค้นหาเชิงเส้น
55 เท่ากับ 9?
หรือมากกว่าสมมุติว่าน้อยกว่า 9
เพราะผมกำลังพยายามที่จะ คิดออกว่าจะใส่ 55
น้อยกว่า 9, น้อยกว่า 17 น้อย กว่า 20 น้อยกว่า 22 น้อยกว่า 29
น้อยกว่า 34 ไม่
ดังนั้นตอนนี้เราอยู่ในกรณีที่ หนึ่งในอย่างน้อยสาม
>> ถ้าฉันต้องการแทรก 55 กว่าที่นี่สิ่งที่ บรรทัดของรหัสที่จำเป็นต้องได้รับการดำเนินการ?
อย่างไรภาพนี้ มนุษย์จำเป็นต้องเปลี่ยน?
ฉันจะทำอะไรกับมือซ้ายของฉันได้อย่างไร
นี้ควรจะเป็นโมฆะในขั้นต้น เพราะผมตอนท้ายของรายการ
และสิ่งที่ควรจะเกิดขึ้น ที่นี่กับปีเตอร์เป็นมันได้หรือไม่
เขาก็เห็นได้ชัดว่าจะชี้ให้ฉัน
ดังนั้นผมจึงเรียกร้องว่ามีอย่างน้อยสองบรรทัด ของรหัสในโค้ดตัวอย่างตั้งแต่วันนี้
ที่จะดำเนินการนี​​้ สถานการณ์ของการเพิ่ม 55 ที่หาง
และอาจจะมีใครบางคนกระโดด และเพียงแค่แสดง 55?
สิทธิทั้งหมดคุณใหม่ 55
>> ดังนั้นตอนนี้สิ่งที่ถ้าต่อไป สถานการณ์มาพร้อม
และเราต้องการที่จะแทรกที่ จุดเริ่มต้นหรือหัวของรายการนี​​้หรือไม่
และสิ่งที่ชื่อหมายเลข 55 ของคุณ?
>> ผู้ชม: แจ็ค
>> เดวิดเจลัน: แจ็ค?
ตกลงที่ดีที่จะได้พบคุณ
ยินดีต้อนรับบนเรือ
ดังนั้นตอนนี้เรากำลังจะไป แทรกพูดหมายเลข 5
นี่คือกรณีที่สองของการเป็น สามเรามาด้วยก่อนที่จะ
ดังนั้นถ้า 5 เป็นที่จุดเริ่มต้น เรามาดูวิธีการที่เราพบว่า
ฉันเริ่มต้น PTR ของฉัน ตัวชี้ไปยังหมายเลข 9 อีกครั้ง
และฉันรู้ว่าโอ้, 5 เป็นน้อยกว่า 9
ดังนั้นการแก้ไขปัญหาภาพนี้สำหรับเรา
มีมือเกบหรือเดวิด or-- ชื่ออะไรหมายเลข 9 หรือไม่
>> ผู้ชม: เจน
>> เดวิดเจลัน: hands-- เจน ซึ่งจากมือของเราจำเป็นที่จะต้องเปลี่ยน?
OK เพื่อให้เกบชี้ในสิ่งที่ตอนนี้หรือไม่
มาที่ฉัน
ผมโหนดใหม่
ดังนั้นฉันจะเพียงชนิดของการย้าย ที่นี่จะเห็นมันสายตา
และในขณะเดียวกันสิ่งที่ฉันชี้ที่?
ยังคงที่ฉันชี้
ดังนั้นที่มัน
ดังนั้นเพียงแค่จริงๆหนึ่งบรรทัดของการแก้ไขรหัส ปัญหานี้โดยเฉพาะอย่างยิ่งก็จะดูเหมือน
สิทธิทั้งหมดเพื่อให้เป็นสิ่งที่ดี
และคนที่สามารถเป็นตัวยึดสำหรับ 5?
มาขึ้น
เราจะให้คุณได้รับในครั้งต่อไป
>> ทั้งหมดขวาดังนั้น now-- และ เช่นกันชื่อ
ผมไม่ได้กล่าวถึงอย่างชัดเจนสิทธิ ตอนนี้ตัวชี้ pred ตัวชี้บรรพบุรุษ
และตัวชี้ใหม่ที่ เพียงแค่ชื่อที่กำหนด
ในโค้ดตัวอย่างที่จะชี้หรือ มือของฉันที่ชนิดของการชี้รอบ
คุณชื่ออะไร?
>> ผู้ชม: คริสติน
>> เดวิดเจลัน: คริสติน
ยินดีต้อนรับบนเรือ
สิทธิทั้งหมดเพื่อให้พิจารณาขณะนี้ สถานการณ์ที่น่ารำคาญมากขึ้นเล็กน้อย
โดยผมต้องการที่จะใส่ 26 สิ่งที่ต้องการลงในนี้
20?
คืออะไร?
เหล่านี้ are-- สิ่งที่ดีเรามีปากกานี้
สิทธิทั้งหมด 20
ถ้ามีคนจะได้รับชิ้นส่วนของอื่น กระดาษพร้อมเพียงใน case-- ขวาทั้งหมด
โอ้ที่น่าสนใจ
อย่างนี้เป็นตัวอย่าง ข้อผิดพลาดของการบรรยาย
ตกลงดังนั้นสิ่งที่เป็นชื่อของคุณอีกครั้งหรือไม่
ผู้ชม: จูเลีย
เดวิดเจลัน: จูเลียคุณสามารถป๊อปอัพ ออกมาและหลอกคุณไม่เคยมี?
ตกลงนี้ไม่เคยเกิดขึ้น
ขอบคุณ
ดังนั้นสมมติว่าเราต้องการแทรก จูเลียเป็นรายการที่เชื่อมโยงนี้
เธอคือหมายเลข 20
และแน่นอนเธอ จะอยู่ที่
begin-- ไม่ได้ชี้ไปที่อะไรยัง
เพื่อให้มือของคุณชนิดของสามารถ ลงโมฆะหรือค่าขยะบาง
ขอบอกเล่าเรื่องราวได้อย่างรวดเร็ว
ผมชี้ไปที่หมายเลข 5 ในครั้งนี้
แล้วฉันจะตรวจสอบ 9
แล้วฉันจะตรวจสอบ 17
แล้วฉันจะตรวจสอบ 22
และฉันตระหนักโอจูเลีย ต้องไปก่อนวันที่ 22
ดังนั้นสิ่งที่ต้องเกิดขึ้น?
ที่มีอยู่ในมือจะต้องเปลี่ยน?
จูเลียเหมือง or-- สิ่งที่ชื่อของคุณอีกครั้งหรือไม่
>> ผู้ชม: คริสเตียน
>> เดวิดเจลัน: คริสเตียนหรือ?
>> ผู้ชม: แอนดี้
>> เดวิดเจลัน: แอนดี้
คริสเตียนหรือแอนดี้?
แอนดี้จะต้องชี้ไปที่?
จูเลีย
ขวาทั้งหมด
ดังนั้นแอนดี้, คุณต้องการที่จะชี้ไปที่จูเลีย?
แต่รอสักครู่
ในเรื่องป่านนี้ ฉันจัดเรียงของหนึ่ง
ในค่าใช้จ่ายในแง่ที่ว่า ชี้เป็นสิ่งที่เป็น
เคลื่อนที่ผ่านรายการ
เราอาจจะมีชื่อของแอนดี้ แต่ มีตัวแปรที่เรียกว่าแอนดี้ไม่
เพียงตัวแปรอื่น ๆ ที่เรามีคือ ครั้งแรกที่ได้แสดงโดยเกบ
>> ดังนั้นนี้เป็นจริงทำไมจึง จนถึงขณะนี้เราได้ไม่จำเป็นต้องนี้
แต่ตอนนี้บนหน้าจอมี พูดถึงอีกครั้งของตัวชี้ผู้ชนะ
ดังนั้นขอให้ฉันเป็นที่ชัดเจนมากขึ้น
ถ้านี่เป็นตัวชี้ผมได้ดีกว่า ได้รับน้อยฉลาดมากขึ้น
เกี่ยวกับการย้ำของฉัน
ถ้าคุณไม่คิดจะของฉันผ่านที่นี่ อีกครั้งชี้นี่ชี้ที่นี่
แต่ให้ฉันมีตัวชี้ชนะ, ตัวชี้บรรพบุรุษที่
ชนิดของชี้ไปที่ องค์ประกอบฉันเป็นเพียงที่
ดังนั้นเมื่อผมไปที่นี่ตอนนี้ การปรับปรุงของฉันมือซ้าย
เมื่อผมไปที่นี่การปรับปรุงทางด้านซ้ายมือของฉัน
และตอนนี้ฉันไม่เพียง แต่มีตัวชี้ไปยัง องค์ประกอบที่จะไปหลังจากที่จูเลีย
ผมยังมีตัวชี้ไปยัง แอนดี้องค์ประกอบก่อน
เพื่อให้คุณมีการเข้าถึงเป็นหลัก สวดมนต์, ถ้าคุณจะ
ทั้งหมดของตัวชี้จำเป็น
>> ดังนั้นหากผมชี้ไปที่ แอนดี้และฉันยังชี้
ที่นับถือศาสนาคริสต์ที่มีอยู่ในมือ ตอนนี้ควรจะชี้อื่น?
แอนดี้ดังนั้นตอนนี้สามารถชี้ไปที่จูเลีย
จูเลียขณะนี้สามารถชี้ไปที่นับถือศาสนาคริสต์
เพราะเธอสามารถคัดลอกของฉัน ชี้มือข้างขวาของ
และที่มีประสิทธิภาพทำให้คุณ กลับเข้าที่นี่
ดังนั้นในระยะสั้นแม้นี้ คือการให้เราชนิดของตลอดไป
การปรับปรุงจริง รายการที่เชื่อมโยงตระหนัก
ว่าการดำเนินงาน มีความง่าย
มันเป็นหนึ่งสองสาม บรรทัดของรหัสในท้ายที่สุด
แต่พันรอบที่ บรรทัดของรหัสสันนิษฐาน
เป็นบิตของตรรกะที่มีประสิทธิภาพ ถามคำถามที่เรา?
เราอยู่ที่จุดเริ่มต้นที่ กลางหรือสิ้นสุดหรือไม่
>> ตอนนี้มีแน่นอนอื่น ๆ การดำเนินงานของเราอาจจะใช้
และภาพเหล่านี้ที่นี่ก็แสดงให้เห็นถึง สิ่งที่เราได้ทำกับมนุษย์
สิ่งที่เกี่ยวกับการกำจัด?
ถ้าผมอยากจะยกตัวอย่างเช่น ลบหมายเลข 34 หรือ 55,
ฉันอาจจะมีชนิดเดียวกันของรหัส แต่ฉันจะต้องหนึ่งหรือสองขั้นตอน
เพราะมีอะไรใหม่?
ถ้าผมเอาคนที่ท้ายที่สุด เช่นหมายเลข 55 และแล้ว 34,
สิ่งที่ยังมีการเปลี่ยนแปลงที่ผมทำนั้น
ฉันต้องไม่ evict-- สิ่งที่ชื่อของคุณอีกครั้งหรือไม่
>> ผู้ชม: แจ็ค
>> เดวิดเจลัน: แจ็ค
ฉันต้องไม่เพียง แต่ evict-- ฟรีแจ็ค เพื่อเรียกตัวอักษรฟรีแจ็คหรืออย่างน้อย
ชี้มีเกินไป แต่ตอนนี้ สิ่งที่ต้องเปลี่ยนกับปีเตอร์?
มือของเขาเริ่มดีขึ้นชี้ลง
เพราะทันทีที่ผมเรียกฟรีใน แจ็คถ้าปีเตอร์ยังคงชี้ไปที่แจ็ค
และฉันจึงเก็บไว้ภายใน รายการและการเข้าถึงตัวชี้นี้
ที่เมื่อแบ่งส่วนเพื่อนเก่าของเรา ความผิดจริงอาจเตะใน
เพราะเราได้รับ กลับหน่วยความจำเพื่อแจ็ค
>> คุณสามารถอยู่ที่นั่น อย่างเชื่องช้าเพียงสักครู่
เพราะเรามีเพียงไม่กี่ การดำเนินงานขั้นสุดท้ายที่จะต้องพิจารณา
ถอดหัวของรายการที่ หรือ beginning-- และเป็นหนึ่งในนี้
ที่น่ารำคาญเล็ก ๆ น้อย ๆ
เพราะเราต้องรู้ว่าเกบ เป็นชนิดพิเศษในโปรแกรมนี้
เพราะอันที่จริงเขามีตัวชี้ของตัวเอง
เขาไม่ได้เพียงแค่ถูกชี้ไปที่ เป็นเกือบทุกคนอื่นที่นี่
>> ดังนั้นเมื่อหัวของรายการเป็น ออกซึ่งมือต้องเปลี่ยนตอนนี้หรือไม่
คุณชื่ออะไรอีกครั้งหรือไม่
>> ผู้ชม: คริสติน
>> เดวิดเจลัน: ฉันกลัว ชื่อที่เห็นได้ชัด
ดังนั้นคริสตินและเกบ ที่มีอยู่ในมือจะต้องเปลี่ยน
เมื่อเราพยายามที่จะเอาคริสติน จำนวน 5 จากภาพหรือไม่
ตกลงจึงขอทำเกบ
เกบจะชี้ สันนิษฐานว่าที่บ้านเลขที่ 9
แต่สิ่งที่ควรจะเกิดขึ้นต่อไป?
ผู้ชม: คริสตินควร เป็นโมฆะ [ไม่ได้ยิน]
เดวิดเจลัน: ตกลงเราควรอาจ make-- ฉันได้ยิน "โมฆะ" อยู่ที่ไหนสักแห่ง
ผู้ชม: Null และฟรีของเธอ
เดวิดเจลัน: Null อะไร
ผู้ชม: Null และฟรีของเธอ
เดวิดเจลัน: Null และฟรีของเธอ
ดังนั้นนี้เป็นเรื่องง่ายมาก
และมันเป็นเรื่องที่สมบูรณ์แบบที่คุณตอนนี้การจัดเรียง ยืนอยู่ที่นั่นไม่ได้เป็น
เพราะคุณได้รับ หลุดพ้นจากรายการ
คุณได้รับได้อย่างมีประสิทธิภาพ กำพร้าจากรายการ
และเพื่อให้เราได้ดีกว่าการโทรฟรีในขณะนี้ คริสตินที่จะให้หน่วยความจำที่กลับมา
มิฉะนั้นทุกครั้งที่เรา ลบโหนดจากรายการ
เราอาจจะมีการทำรายการ สั้นลง แต่ไม่ได้ลดลง
ขนาดในหน่วยความจำ
และอื่น ๆ ถ้าเราเก็บเพิ่มและ เพิ่มเพิ่มสิ่งที่รายการ
คอมพิวเตอร์ของฉันอาจได้รับช้า และช้าลงและช้าลง
เพราะฉันวิ่งออกมาจาก หน่วยความจำแม้ว่าฉันไม่ได้จริง
โดยใช้ไบต์คริสติน ของหน่วยความจำอีกต่อไป
>> ดังนั้นในที่สุดมีอื่น ๆ สถานการณ์การกำจัด course--
ในกลางกำจัด ในตอนท้ายที่เราเห็น
แต่ที่น่าสนใจมากขึ้น ความท้าทายขณะนี้คือ
จะเป็นที่จะต้องพิจารณาว่า สิ่งที่เวลาการทำงานเป็น
ดังนั้นไม่เพียง แต่คุณสามารถเก็บของคุณ ชิ้นส่วนของกระดาษถ้าเกบ
คุณจะไม่คิดให้ ทุกคนลูกความเครียด
ขอบคุณมากที่จะเชื่อมโยงรายการของเรา ของอาสาสมัครที่นี่ถ้าคุณสามารถทำได้
>> [APPLAUSE]
>> เดวิดเจลัน: ทั้งหมดขวา
ดังนั้นคู่ของการวิเคราะห์ คำถามแล้วถ้าฉันสามารถ
เราได้เห็นสัญกรณ์เช่นนี้มาก่อน O ขนาดใหญ่และโอเมก้า, ขอบเขตบน
และขอบเขตที่ลดลง ใช้เวลาบางส่วนของขั้นตอนวิธี
ดังนั้นขอให้พิจารณาเพียงแค่ สองสามคำถาม
>> หนึ่งและเราบอกว่ามัน ก่อนที่สิ่งที่ทำงาน
ช่วงเวลาของการค้นหา รายการในแง่ของ O ใหญ่?
อะไรคือขอบเขตบนทำงาน เวลาของการค้นหารายการที่เชื่อมโยง
ที่ดำเนินการโดยอาสาสมัครของเราที่นี่?
มันเป็นเรื่องใหญ่ของ O n เชิงเส้น
เพราะในกรณีที่เลวร้ายที่สุด องค์ประกอบเช่น 55,
เราอาจจะมองหาอาจจะเป็นที่ แจ็คเป็นทุกทางในตอนท้าย
และโชคไม่ดีที่แตกต่างจากอาร์เรย์ เราไม่สามารถรับแฟนซีเวลานี้
แม้ว่าทั้งหมดของมนุษย์ของเราได้ เรียงลำดับจากองค์ประกอบขนาดเล็ก, 5,
ทุกอย่างขึ้นอยู่กับองค์ประกอบที่ใหญ่กว่าที่ 55, ที่มักจะเป็นสิ่งที่ดี
แต่สิ่งที่จะสันนิษฐานว่า ไม่ได้ช่วยให้เราสามารถทำอย่างไร
ผู้ชม: [ไม่ได้ยิน]
เดวิดเจลัน: พูดอีกครั้งหรือไม่
ผู้ชม: การเข้าถึงแบบสุ่ม
เดวิดเจลัน: การเข้าถึงแบบสุ่ม
และในทางกลับนั่นหมายความว่าเราสามารถไม่มี ได้ใช้ศูนย์อ่อนแอปรีชา
และความชัดเจนของการใช้ไบนารี การค้นหาและการแบ่งและพิชิต
เพราะถึงแม้เรา มนุษย์สามารถที่จะเห็นได้ชัด
เห็นว่าแอนดี้หรือคริสเตียน ๆ ที่อยู่ตรงกลางของรายการที่
เราเท่านั้นที่รู้ว่าเป็น คอมพิวเตอร์โดย skimming รายการ
จากจุดเริ่มต้นมาก
ดังนั้นเราจึงได้รับการเข้าถึงแบบสุ่มที่
>> O ดังนั้นใหญ่ของ n ขณะนี้คือด้านบน ผูกพันกับเวลาค้นหาของเรา
สิ่งที่เกี่ยวกับโอเมก้าของการค้นหาของเราหรือไม่
สิ่งที่ขอบเขตที่ต่ำในการค้นหา สำหรับจำนวนในรายการนี​​้บาง
ผู้ชม: [ไม่ได้ยิน]
เดวิดเจลัน: พูดอีกครั้งหรือไม่
ผู้ชม: หนึ่ง
เดวิดเจลัน: หนึ่ง
เวลาเพื่อให้คงที่
ในกรณีที่ดีที่สุดคริสตินเป็น แน่นอนที่จุดเริ่มต้นของรายการ
และเรากำลังมองหา จำนวน 5 ดังนั้นเราจึงพบว่าเธอ
ดังนั้นไม่มีเรื่องใหญ่
แต่เธอก็เป็นที่ จุดเริ่มต้นของรายการในกรณีนี้
สิ่งที่เกี่ยวกับสิ่งที่ต้องการลบ?
ถ้าคุณต้องการที่จะลบองค์ประกอบ?
อะไรคือขีด จำกัด บนและขีด จำกัด ล่าง ในการลบอะไรบางอย่างจากการเชื่อมโยง
รายการ?
ผู้ชม: [ไม่ได้ยิน]
เดวิดเจลัน: พูดอีกครั้งหรือไม่
ผู้ชม: n
เดวิดเจลัน: n คือ แน่นอนบนปก
เพราะในกรณีที่เลวร้ายที่สุดที่เราพยายาม ลบแจ็คเหมือนเราเพิ่งได้
เขาเป็นทุกอย่างในตอนท้าย
จะพาเราตลอดไปหรือ n ขั้นตอนไปหาเขา
เพื่อให้บนปก
นั่นเป็นเชิงเส้นนั่นเอง
และกรณีที่ดีที่สุดใช้เวลาหรือ ขอบเขตที่ต่ำกว่าในกรณีที่ดีที่สุด
จะเป็นเวลาคงที่
เพราะบางทีเราพยายามที่จะลบ คริสตินและเราก็โชคดีที่ได้รับ
เธอเป็นที่จุดเริ่มต้น
ตอนนี้รอสักครู่
เกบยังเป็นที่จุดเริ่มต้น และเรายังมีการอัปเดตเกบ
เพื่อให้เป็นไม่ได้เป็นเพียงขั้นตอนเดียว
ดังนั้นจึงเป็นที่แน่นอนคงที่ เวลาในกรณีที่ดีที่สุด
ในการลบองค์ประกอบที่เล็กที่สุดหรือไม่
มันคือแม้ว่ามันอาจจะสอง สามหรือ 100 สายรหัส
ถ้าหากมันเป็นหมายเลขเดียวกันของ เส้นไม่ได้อยู่ในวงบาง
และเป็นอิสระจากขนาด ของรายการอย่าง
การลบองค์ประกอบที่ จุดเริ่มต้นของรายการที่
แม้ว่าเราจะมีการจัดการกับ เกบยังคงเป็นเวลาอย่างต่อเนื่อง
>> ดังนั้นนี้ดูเหมือนว่า ขั้นตอนใหญ่ไปข้างหลัง
และสิ่งที่เสียเวลา ถ้าในหนึ่งสัปดาห์และสัปดาห์
เป็นศูนย์ที่เรามีไม่เพียง รหัส pseudocode แต่รหัสที่เกิดขึ้นจริง
ที่จะใช้สิ่งที่บันทึก ฐาน n, หรือเข้าสู่ระบบค่อนข้างของ n, ฐานที่ 2
ในแง่ของเวลาการทำงานของตน
ดังนั้นทำไม heck เราต้องการที่จะเริ่มต้น ใช้สิ่งที่ต้องการรายการที่เชื่อมโยงหรือไม่
ใช่
>> ผู้ชม: เพ​​ื่อให้คุณสามารถเพิ่ม องค์ประกอบไปยังอาร์เรย์
เดวิดเจลัน: คุณสามารถ เพิ่มองค์ประกอบไปยังอาร์เรย์
และนี่ก็เป็นใจ
และเราจะยังคงเห็น นี้นี้ค้าออกมาก
เหมือนที่เราเคยเห็น การปิดด้วยการจัดเรียงเวียน
จริงๆเราสามารถเพิ่มความเร็ว ค้นหาหรือเรียงลำดับค่อนข้าง
ถ้าเราใช้พื้นที่น้อยมากและ มีก้อนที่เพิ่มขึ้นของหน่วยความจำ
หรืออาเรย์สำหรับการจัดเรียงเวียน
แต่เราใช้จ่ายมากขึ้น พื้นที่ แต่เราประหยัดเวลา
ในกรณีนี้เราไม่ ให้ขึ้นเวลา แต่เรา
ดึงดูดความยืดหยุ่น พลวัตถ้าคุณจะ
ซึ่งเป็นเนื้อหาที่มีลักษณะเชิงบวก
>> เรายังใช้พื้นที่
ในสิ่งที่ความรู้สึกที่เชื่อมโยง รายการมีราคาแพงกว่า
ในแง่ของพื้นที่กว่าอาร์เรย์?
ที่มีการพื้นที่พิเศษมาจากไหน?
ใช่?
>> ผู้ชม: ตัวชี้ [ไม่ได้ยิน]
>> เดวิดเจลัน: ใช่เรา ยังมีตัวชี้
ดังนั้นนี้เป็นที่น่ารำคาญ minorly ในที่ไม่มีฉัน
ฉันเพียงแค่การจัดเก็บ int ที่จะเป็นตัวแทน int
ฉันเก็บ int และ ตัวชี้ซึ่งเป็น 32 บิต
ดังนั้นฉันอย่างแท้จริงเสแสร้ง จำนวนของพื้นที่ที่เกี่ยวข้อง
นั่นคือการปิด แต่ นั่นคือในกรณีที่ int
สมมติว่าคุณไม่ได้จัดเก็บ int, แต่คิดว่าแต่ละสี่เหลี่ยมเหล่านี้
หรือแต่ละคนเหล่านี้เป็นตัวแทนของ คำภาษาอังกฤษคำว่า
อาจจะมีห้าตัวอักษร, 10 ตัวละครอาจจะมากยิ่งขึ้น
แล้วเพิ่มเพียง 32 บิตมากขึ้น อาจจะน้อยกว่าเป็นเรื่องใหญ่
>> สิ่งที่ถ้าแต่ละของนักเรียน ในการสาธิต
เป็นตัวอักษร structs นักเรียนที่ มีชื่อและบ้านและอาจจะ
หมายเลขโทรศัพท์และทวิตเตอร์ จัดการและชอบ
เพื่อให้ทุกสาขาที่เราเริ่มต้น พูดคุยเกี่ยวกับวันอื่น ๆ
มากน้อยของการจัดการที่ใหญ่เป็น โหนดของเราได้รับน่าสนใจมากขึ้น
และขนาดใหญ่ที่จะใช้จ่ายใช่มั้ยเพิ่มเติม ตัวชี้เพียงเพื่อเชื่อมโยงพวกเขาเข้าด้วยกัน
แต่จริง ๆ แล้วมันเป็นค้าออก
และแน่นอนรหัสเป็น ที่ซับซ้อนมากขึ้นในขณะที่คุณจะ
ดูได้จากการ skimming ผ่าน ตัวอย่างเช่นโดยเฉพาะอย่างยิ่งที่
แต่สิ่งที่ถ้ามี จอกศักดิ์สิทธิ์ที่นี่
สิ่งที่ถ้าเราไม่ได้ใช้ขั้นตอนที่ หลัง แต่เป็นขั้นตอนใหญ่ไปข้างหน้า
และใช้ข้อมูลที่ โครงสร้างที่เราผ่านทาง
สามารถหาองค์ประกอบเช่นแจ็คหรือ คริสตินหรือองค์ประกอบอื่น ๆ
ในอาร์เรย์ในเวลาที่คงที่จริงนี้
ค้นหาเป็นอย่างต่อเนื่อง
ลบเป็นค่าคงที่
ใส่เป็นค่าคงที่
ทั้งหมดของการดำเนินงานเหล่านี้อย่างต่อเนื่อง
ที่จะเป็นจอกศักดิ์สิทธิ์ของเรา
และนั่นคือที่ที่เรา จะรับครั้งต่อไป
ดูแล้วคุณ