ลำโพงที่ 1: สิทธิทั้งหมดดังนั้นนี่คือ CS50 นี่คือจุดสิ้นสุดของสัปดาห์ห้า และจำได้ว่าครั้งสุดท้ายที่เรา เริ่มมองหาข้อมูลนักเล่น โครงสร้างที่เริ่มต้นที่จะแก้ปัญหา ปัญหาที่เริ่มต้นที่จะแนะนำ ปัญหาใหม่ แต่ที่สำคัญไปนี้ คือการจัดเรียงของเกลียวที่เรา เริ่มต้นที่จะทำจากโหนดไปยังโหนด ดังนั้นนี่แน่นอน รายการที่เชื่อมโยงโดยลำพัง และโดยการเชื่อมโยงโดยลำพัง ฉันหมายความว่ามีเพียงหนึ่ง ด้ายระหว่างแต่ละโหนดเหล่านั้น เปิดออกคุณสามารถทำนักเล่น สิ่งที่ชอบรายการที่เชื่อมโยงเป็นทวีคูณ โดยคุณมีลูกศร ไปในทั้งสองทิศทางซึ่ง สามารถช่วยให้มีประสิทธิภาพบางอย่าง แต่ตอนนี้แก้ปัญหาได้หรือไม่ สิ่งที่เป็นปัญหานี้ไม่แก้ปัญหา? ทำไมเราดูแลในวันจันทร์? ทำไมในทางทฤษฎีเราไม่ดูแลในวันจันทร์? มันทำอะไร? 

ผู้ชม: เราแบบไดนามิกสามารถปรับขนาด 

ลำโพง 1: ตกลงดังนั้นเราสามารถทำได้ ปรับขนาดแบบไดนามิก ทำได้ดีทั้งสองท่าน ดังนั้นคุณจึงสามารถปรับขนาดแบบไดนามิกนี้ โครงสร้างข้อมูลในขณะที่อาร์เรย์ จำที่คุณต้องรู้ เบื้องต้นช่องว่างที่คุณต้องการ และหากคุณต้องการน้อยมาก พื้นที่ที่คุณกำลังชนิดของออกจากโชค คุณต้องสร้างอาร์เรย์ใหม่ทั้งหมด คุณจะต้องย้ายทั้งหมดของคุณ ข้อมูลจากที่หนึ่งไปยังที่อื่น ๆ ในที่สุดก็เป็นอิสระอาร์เรย์เก่า ถ้าคุณสามารถแล้วดำเนินการต่อ ซึ่งเพียงแค่รู้สึกมีราคาแพงมากและมาก ที่ไม่มีประสิทธิภาพและแน่นอนที่จะสามารถ แต่ตอนนี้ไม่ดี เราจ่ายราคาเป็นสิ่งที่เป็นหนึ่ง ของราคาที่เห็นได้ชัดมากขึ้นเรา โดยการใช้จ่ายรายการที่เชื่อมโยงหรือไม่? 

ผู้ชม: เราต้องใช้ พื้นที่สองสำหรับแต่ละคน ลำโพง 1: ใช่เราจึงจำเป็นต้อง อย่างน้อยสองเท่าของพื้นที่มาก ในความเป็นจริงผมก็นึกภาพนี้ แม้เพียงเล็กน้อยทำให้เข้าใจผิด เพราะ IDE CS50 ในจำนวนมากของที่ทันสมัย คอมพิวเตอร์ตัวชี้หรือที่อยู่ ไม่ได้อยู่ในความเป็นจริงสี่ไบต์ มันมากเหล่านี้มักจะ วันที่แปดไบต์ซึ่ง ด้านล่างหมายถึงมากที่สุด รูปสี่เหลี่ยมมีในความเป็นจริง เป็นชนิดของสองเท่า ใหญ่เป็นสิ่งที่ผมเคยวาด ซึ่งหมายความว่าคุณกำลังใช้สามเท่า พื้นที่มากที่สุดเท่าที่เราอาจจะมีอย่างอื่น ตอนนี้ในเวลาเดียวกันเรา ยังคงพูดคุยไบต์ใช่มั้ย? เราไม่จำเป็นต้องพูด เมกะไบต์หรือกิกะไบต์ เว้นแต่โครงสร้างข้อมูลเหล่านี้จะได้รับใหญ่ 

และในวันนี้เราจะเริ่มต้นที่จะต้องพิจารณา วิธีการที่เราจะสำรวจข้อมูล มีประสิทธิภาพมากขึ้นถ้าใน ความเป็นจริงข้อมูลที่ได้รับใหญ่ แต่ลอง canonicalize การดำเนินงานครั้งแรก ที่คุณสามารถทำในสิ่งเหล่านี้ ชนิดของโครงสร้างข้อมูล ดังนั้นสิ่งที่ต้องการเชื่อมโยง รายการสนับสนุนทั่วไป การดำเนินงานที่ต้องการลบ แทรกและค้นหา และสิ่งที่ผมหมายถึงโดยที่? นั่นก็หมายความว่าปกติ ถ้าคนจะใช้รายการที่เชื่อมโยง พวกเขาหรือคนอื่นได้ดำเนินการ ฟังก์ชั่นเช่นการลบแทรก และการค้นหาเพื่อให้คุณสามารถ จริงทำอะไรบางอย่าง ที่เป็นประโยชน์กับโครงสร้างข้อมูล ดังนั้นลองมาดูอย่างรวดเร็ว วิธีการที่เราจะใช้ รหัสบางอย่างสำหรับรายการที่เชื่อมโยงดังต่อไปนี้ 

ดังนั้นนี้เป็นเพียงบางส่วนรหัสซี ไม่ได้โปรแกรมที่สมบูรณ์ ที่ผมวิปปิ้งได้อย่างรวดเร็วขึ้น มันไม่ได้ออนไลน์ในการจัดจำหน่าย รหัสเพราะมันจะไม่ได้ทำงานจริง แต่สังเกตเห็นฉันได้เพียงแค่ ที่มีความคิดเห็นกล่าวว่า dot dot dot มีบางสิ่งบางอย่าง มีจุดจุดจุดมีบางสิ่งบางอย่าง และขอเพียงแค่มอง ส่วนสิ่งที่มีความฉ่ำ ดังนั้นในบรรทัดที่สาม จำได้ว่าตอนนี้ เราเสนอประกาศโหนดที่ผ่านมา เวลาหนึ่งในบรรดาวัตถุทรงสี่เหลี่ยม มันมี int ว่าเราจะเรียกยังไม่มีข้อความที่ แต่เราจะเรียกมันว่าอะไร แล้วดาวโหนดโครงสร้างที่เรียกว่าต่อไป และเพียงเพื่อจะชัดเจนที่สองที่ บรรทัดในบรรทัดหกสิ่งที่เป็นที่? มันจะทำอะไรสำหรับเรา? เพราะมันแน่นอนดูเพิ่มเติม ความลับกว่าตัวแปรตามปกติของเรา 

ผู้ชม: มันทำให้ย้ายไปหนึ่ง 

ลำโพงที่ 1: มันทำให้ย้ายไปหนึ่ง และจะแม่นยำมากขึ้น มันจะเก็บที่อยู่ ของโหนดที่หมายถึงการเป็น ความหมายถัดไปใช่มั้ย? ดังนั้นจึงไม่ได้ไป จำเป็นต้องย้ายอะไร มันเป็นเพียงแค่ไป เก็บค่าซึ่งเป็น จะเป็นที่อยู่ บางโหนดอื่น ๆ และนั่นคือเหตุผลที่เราได้กล่าวว่า struct ดาวโหนดดาวแสดงถึง ตัวชี้หรือที่อยู่ ตกลงดังนั้นตอนนี้ถ้าคุณคิดว่าเรามี นี้ยังไม่มีข้อความที่มีให้เราและให้ คิดว่าคนอื่นมี ใส่ทั้งกลุ่มของจำนวนเต็ม เป็นรายการที่เชื่อมโยง และที่เป็นรายการที่เชื่อมโยง ชี้ไปในบางจุด รายการที่เรียกว่าตัวแปรที่ ผ่านในที่นี่เป็นพารามิเตอร์ ฉันจะไปเกี่ยวกับสาย 14 การดำเนินการค้นหา? ในคำอื่น ๆ ถ้าผมกำลังดำเนินการ ฟังก์ชั่นที่มีจุดมุ่งหมายในชีวิต คือการใช้ int แล้ว จุดเริ่มต้นของรายการที่เชื่อมโยง ที่เป็นตัวชี้ไปยังรายการที่เชื่อมโยง เช่นเดียวกับครั้งแรกที่ผมคิดว่าเดวิด เป็นอาสาสมัครของเราในวันจันทร์ที่ เขาได้รับการชี้ไปที่ ทั้งรายการที่เชื่อมโยง มันเหมือนกับว่าเรากำลังผ่าน ดาวิดเป็นอาร์กิวเมนต์ของเราที่นี่ เราไม่ไปวิธีการเกี่ยวกับภายในรายการนี​​้ ดีก็ปรากฎว่าแม้ว่า ตัวชี้ค่อนข้างใหม่ในขณะนี้กับเรา เราสามารถทำเช่นนี้ค่อนข้าง ตามตรง 

ฉันจะไปข้างหน้าและ ประกาศตัวแปรชั่วคราวที่ โดยการประชุมเป็นเพียงการไป จะเรียกว่าตัวชี้หรือ PTR, แต่คุณสามารถเรียกมันว่าสิ่งที่คุณต้องการ และฉันจะเริ่มต้น ไปยังจุดเริ่มต้นของรายการ เพื่อให้คุณสามารถชนิดของการคิดว่านี้ ฉันเป็นครูในวันอื่น ๆ ชนิดของการชี้ไปที่ใครบางคน ในหมู่มนุษย์ของเราเป็นอาสาสมัคร ดังนั้นฉันตัวแปรชั่วคราวที่ เพียงแค่ชี้ไปที่สิ่งเดียวกัน ที่บังเอิญชื่อของเรา อาสาสมัครเดวิดก็ยังชี้ให้เห็น ตอนนี้ในขณะที่ตัวชี้เป็น ไม่เป็นโมฆะเพราะการเรียกคืน null ที่บางค่าแมวมองพิเศษ demarcates ท้ายของรายการ ดังนั้นในขณะที่ฉันไม่ได้ชี้ไปที่ พื้นดินเช่นอาสาสมัครครั้งสุดท้ายของเรา ก็ให้เป็นไปข้างหน้า และทำต่อไปนี้ หาก pointer-- และตอนนี้ฉันต้องการชนิดของ จะทำในสิ่งที่เราทำกับนักเรียน structure-- ถ้าตัวชี้จุดต่อไป equals-- แต่ถ้ายังไม่มีตัวชี้จุดเท่ากับ เท่ากับตัวแปรยังไม่มีข้อความที่ อาร์กิวเมนต์ที่ถูกส่งผ่านไปใน แล้วฉันต้องการที่จะไปข้างหน้า และพูดกลับจริง ฉันได้พบจำนวนไม่มีข้อความภายในของ หนึ่งของโหนดของรายการที่เชื่อมโยงของฉัน แต่จุดไม่ ทำงานในบริบทนี้ เพราะตัวชี้ PTR เป็น แน่นอนตัวชี้ที่อยู่ เราจริงสามารถที่เยี่ยมยอด ในที่สุดก็ใช้ชิ้นส่วนของไวยากรณ์ ว่าจะทำให้ ความรู้สึกที่ใช้งานง่ายและจริง ใช้ลูกศรที่นี่ซึ่งหมายความว่าจะไปจาก ว่าที่อยู่ที่จะมีจำนวนเต็มใน ดังนั้นจึงเป็นที่คล้ายกันมากใน จิตวิญญาณของผู้ประกอบการที่จะจุด, แต่เป็นเพราะไม่ได้เป็นตัวชี้ตัวชี้ และไม่ได้เป็นโครงสร้างที่เกิดขึ้นจริงของตัวเอง เราก็ใช้ลูกศร 

ดังนั้นถ้าโหนดปัจจุบันที่ฉันที่ ตัวแปรชั่วคราวกำลังชี้ไปที่ ไม่มีไม่ได้ทำในสิ่งที่ฉันต้องการจะทำอย่างไร? ดีกับอาสาสมัครของฉัน ที่เรามีที่นี่ในวันอื่น ๆ ถ้ามนุษย์คนแรกของฉันไม่ได้เป็นคนเดียวที่ฉัน ต้องการและบางทีมนุษย์ที่สองไม่ได้ หนึ่งที่ฉันต้องการและคนที่สามผม จำเป็นที่จะต้องให้ย้ายร่างกาย เช่นเดียวกับฉันจะก้าวผ่านรายการ? เมื่อเรามีอาร์เรย์คุณ ก็ไม่ได้เหมือนที่ผมบวกบวก แต่ในกรณีนี้ก็พอเพียงที่จะ ทำชี้ได้รับตัวชี้ต่อไป ในคำอื่น ๆ ฟิลด์ต่อไป เป็นเหมือนทั้งหมดของมือซ้าย ที่อาสาสมัครของเราในวันจันทร์ ได้ใช้ไปยังจุดที่บางโหนดอื่น ๆ สิ่งเหล่านี้เป็นเพื่อนบ้านของพวกเขาต่อไป 

ดังนั้นถ้าผมต้องการที่จะก้าวผ่านรายการนี​​้ ฉันไม่สามารถเพียงแค่ทำผมบวกบวกอีกต่อไป ฉันแทนที่จะต้องบอกว่า ผมชี้เป็นไป เท่ากับสิ่งที่ฟิลด์ถัดไปคือ สนามต่อไปคือข้อมูลต่อไปคือ ต่อไปนี้ทุกมือทิ้ง ที่เรามีอยู่บนเวทีชี้ บางส่วนค่าที่ตามมา และถ้าฉันได้รับผ่าน ย้ำว่าทั้ง และในที่สุดผมตี null ไม่ได้มี พบว่ายังไม่มี แต่ผมก็กลับเท็จ ดังนั้นอีกครั้งสิ่งที่เรากำลังทำอะไรที่นี่ ตามภาพช่วงเวลาที่ผ่านมา จะเริ่มต้นด้วยการชี้ที่ จุดเริ่มต้นของรายการสันนิษฐานว่า และจากนั้นผมตรวจสอบเป็นค่า ฉันกำลังมองหาเท่ากับเก้า? ถ้าฉันกลับจริงและฉันทำ ถ้าไม่ได้ผมปรับปรุงมือของฉัน ตัวชี้ AKA เพื่อชี้ ที่ตำแหน่งลูกศรถัดไปและ แล้วสถานที่ลูกศรถัดไป และต่อไป ฉันเพียงแค่เดินผ่านแถวนี้ 

ดังนั้นอีกครั้งที่ใส่ใจ? ชอบสิ่งนี้เป็นส่วนผสมสำหรับ? ดีจำได้ว่าเราได้แนะนำ ความคิดของกองซึ่ง เป็นข้อมูลนามธรรมพิมพ์ตราบเท่าที่มันเป็น ไม่ได้เป็นสิ่งซีก็ไม่ได้เป็นสิ่ง CS50, เป็นความคิดที่เป็นนามธรรมความคิดนี้ สิ่งที่ซ้อนอยู่ด้านบนของอีกคนหนึ่ง ที่สามารถนำมาใช้ใน ที่อัดแน่นของวิธีที่แตกต่าง และเป็นหนึ่งในวิธีที่เรานำเสนอกับ อาร์เรย์หรือรายการที่เชื่อมโยง และปรากฎว่า canonically เป็น สแต็คสนับสนุนอย่างน้อยสองการดำเนินงาน และคำฉวัดเฉวียนที่มีการผลักดันเพื่อ ผลักดันบางสิ่งบางอย่างลงบนกอง เช่นถาดใหม่ใน ห้องรับประทานอาหารหรือป๊อป ซึ่งหมายความว่าจะเอาสูงสุด ถาดจากสแต็คในการรับประทานอาหารที่ ฮอลล์แล้วบางทีบาง การดำเนินงานอื่น ๆ เช่นกัน ดังนั้นวิธีที่เราอาจกำหนดโครงสร้าง ว่าตอนนี้เรากำลังเรียกร้องให้กอง? 

ดีที่เรามีทั้งหมดของที่จำเป็น ไวยากรณ์ที่จำหน่ายของเราใน C. ฉันพูดว่า ให้ฉันกำหนดประเภทของ โครงสร้างภายในของสแต็คที่ ฉันจะบอกก็คืออาร์เรย์ของ ทั้งกลุ่มของตัวเลขและขนาดแล้ว ดังนั้นในคำอื่น ๆ ถ้าฉันต้องการ ที่จะใช้ในรหัส ให้ฉันไปและเพียงแค่ชนิดของ วาดสิ่งที่นี้ไม่ว่าจะเป็น ดังนั้นไม่ว่าจะเป็นให้ฉัน โครงสร้างที่มีอาร์เรย์ และผมไม่ทราบว่าสิ่งที่เป็นความจุ มันเห็นได้ชัดว่าบางส่วนคงที่ที่ฉันได้ ที่กำหนดไว้ที่อื่นและที่ดี แต่คิดว่ามันเป็นเพียงหนึ่ง สองสามสี่ห้า กำลังการผลิตเพื่อให้เป็น 5 องค์ประกอบภายในของฉัน โครงสร้างจะถูกเรียกว่าตัวเลข แล้วฉันจำเป็นต้องใช้ ตัวแปรอื่น ๆ ที่เห็นได้ชัด เรียกว่าขนาดที่เริ่มฉันจะ เพื่อกำหนดจะเริ่มต้นให้เป็นศูนย์ หากมีอะไรใน สแต็คขนาดเป็นศูนย์ และเป็นค่าขยะในตัวเลข ฉันมีความคิดว่ามีอะไรอยู่ในนั้นไม่เพียง แต่ 

ดังนั้นถ้าผมต้องการที่จะผลักดัน บางสิ่งบางอย่างลงบนกอง สมมติว่าผมเรียกฟังก์ชั่นการผลักดันและ ผมบอกว่าจะผลักดัน 50, เช่นหมายเลข 50 ที่คุณจะนำเสนอ ผมวาดไว้ในอาร์เรย์นี้หรือไม่? มีคำตอบได้ห้าที่แตกต่างกันคือ คุณต้องการที่จะผลักดันจำนวน 50 ที่ไหน? ถ้าเป้าหมายของที่นี่อีกครั้งเรียกว่า การผลักดันการทำงานผ่านในการโต้แย้ง 50 ที่ฉันจะใส่มันได้หรือไม่ ห้าหากเป็นไปได้มีโอกาส 20% การคาดเดาได้อย่างถูกต้อง ใช่? 

ผู้ชม: ขวาสุด 

ลำโพง 1: ขวาสุด ขณะนี้มีโอกาส 25% การคาดเดาได้อย่างถูกต้อง ดังนั้นที่จริงน่าจะดี โดยการประชุมผมจะพูดด้วยอาร์เรย์ เรามักจะเริ่มต้นที่ด้านซ้าย แต่เราจะทำได้อย่างแน่นอน เริ่มต้นที่เหมาะสม สปอยเลอร์ดังนั้นนี่จะเป็นฉัน อาจจะวาดมันด้านซ้าย เช่นเดียวกับในอาร์เรย์ปกติท​​ี่ ฉันเริ่มจะซ้ายไปขวา แต่ถ้าคุณสามารถพลิก เลขคณิตปรับ มันก็ไม่ธรรมดา ตกลงฉันจำเป็นต้องทำอย่างใดอย่างหนึ่ง แม้ว่าการเปลี่ยนแปลงมากขึ้น ตอนนี้ที่ผมได้ผลักดันบางสิ่งบางอย่าง ลงบนกองสิ่งต่อไปหรือไม่ 

สิทธิทั้งหมดที่ฉันต้องเพิ่มขนาด เพื่อให้ฉันไปข้างหน้าและเพียง อัปเดตนี้ซึ่งเป็นศูนย์ และแทนที่จะตอนนี้ฉันจะ ที่จะใส่ในค่าหนึ่ง และตอนนี้คิดว่าฉันจะผลักดันอีก จำนวนลงบนกองเช่น 51 ดีฉันจะต้องทำอีกหนึ่ง การเปลี่ยนแปลงซึ่งจะขึ้นอยู่กับขนาดของทั้งสอง และจากนั้นก็คิดว่าฉันจะผลักดันอีกหนึ่ง จำนวนลงบนสแต็คเช่น 61, ตอนนี้ผมจำเป็นต้องปรับปรุงขนาดหนึ่งที่มากขึ้น เวลาและได้รับ 3 คุ้มค่าในขณะที่ขนาด และตอนนี้คิดว่าที่ผมเรียกว่าป๊อป ตอนนี้ปรากฏโดยการประชุม ไม่ได้ใช้อาร์กิวเมนต์ กับกองทั้ง จุดของคำอุปมาถาด คือการที่คุณไม่ได้มีการพิจารณา จะไปรับถาดว่าสิ่งที่คุณสามารถทำได้ จะปรากฏหนึ่งสูงสุดจาก สแต็คเพียงเพราะ นั่นคือสิ่งที่โครงสร้างข้อมูลนี้จะ 

ดังนั้นโดยตรรกะว่าถ้าผม ป๊อปบอกว่าสิ่งที่ออกมา? ดังนั้น 61 ดังนั้นสิ่งที่จริงๆเป็นคอมพิวเตอร์ จะทำในหน่วยความจำ? รหัสของฉันไม่ต้องทำอะไร สิ่งที่คุณจะนำเสนอ เราเปลี่ยนบนหน้าจอ? สิ่งที่ควรเปลี่ยน? ขออภัย? ดังนั้นเราจึงได้รับการกำจัดของ 61 ดังนั้นแน่นอนผมสามารถทำเช่นนั้น และผมสามารถกำจัด 61 และแล้วสิ่งอื่น ๆ การเปลี่ยนแปลงความต้องการที่จะเกิดขึ้น? ขนาดอาจมีการกลับไปที่สอง และอื่น ๆ ที่ดี แต่รอสักครู่ขนาด ช่วงเวลาที่ผ่านมาได้สาม ขอเพียงทำตรวจสอบอย่างรวดเร็วมีสุขภาพจิตดี วิธีการที่เรารู้ว่าเรา ต้องการที่จะกำจัดของ 61? เพราะเรากำลัง popping และดังนั้นผมจึงมีขนาดของสถ​​านที่ที่สองนี้ 

รอสักครู่ผม คิดกลับไปสองสัปดาห์ เมื่อเราเริ่มพูดคุยเกี่ยวกับ อาร์เรย์ที่นี้เป็นที่ตั้งศูนย์ นี้เป็นที่ตั้งหนึ่งนี้เป็นที่ตั้ง ทั้งสองนี้เป็นที่ตั้งสามสี่ ดูเหมือนว่า ความสัมพันธ์ระหว่างขนาด และองค์ประกอบที่ฉันต้องการที่จะลบ จากอาร์เรย์ที่ดูเหมือนจะเป็นสิ่งที่เพียง? ขนาดลบหนึ่ง และเพื่อให้เป็นวิธีการที่เป็นมนุษย์ เรารู้มาก่อน 61 วิธีที่คอมพิวเตอร์จะรู้หรือไม่? เมื่อรหัสของคุณที่คุณอาจจะ ต้องการที่จะทำขนาดลบหนึ่ง เพื่อให้สามลบหนึ่งสองและที่ หมายความว่าเราต้องการที่จะกำจัดของ 61 และจากนั้นเราแน่นอนสามารถปรับปรุง ขนาดเพื่อขนาดที่ตอนนี้ ไปจากสามถึงเพียงสอง และเพียงเพื่อจะอวดความรู้ฉันจะ ที่จะเสนอว่าฉันทำใช่มั้ย? คุณเสนอสังหรณ์ใจ ได้อย่างถูกต้องที่ฉันควรจะได้รับการกำจัดของ 61 แต่ยังไม่ได้ชนิดของฉัน อากาศการเรียงลำดับของการกำจัดของ 61? ฉันลืมได้อย่างมีประสิทธิภาพ ว่ามันเป็นจริงมี และคิดว่ากลับไป PSET4 ถ้าคุณได้อ่าน บทความเกี่ยวกับนิติไฟล์ PDF ที่เรามีพวกคุณอ่านหรือคุณ จะอ่านในสัปดาห์นี้สำหรับ PSET4 จำได้ว่านี้เป็นจริงที่จะใกล้ชิด ความคิดทั้งหมดของนิติคอมพิวเตอร์ คอมพิวเตอร์คืออะไรโดยทั่วไปจะเป็น มันก็ลืมบางสิ่งบางอย่างที่เป็น แต่ก็ไม่ได้ไปและไม่ชอบ พยายามที่จะเกามันออกมาหรือแทนที่ บิตผู้ที่มีศูนย์และคน หรือรูปแบบอื่น ๆ สุ่ม จนกว่าคุณจะทำเช่นนั้นได้ด้วยตัวคุณเองโดยเจตนา ดังนั้นสัญชาตญาณของคุณเป็น สิทธิขอกำจัด 61 แต่ในความเป็นจริงเราไม่ต้องกังวล เราก็ต้องลืมว่า มันมีโดยการเปลี่ยนขนาดของเรา 

ตอนนี้มีปัญหากับสแต็คนี้ ถ้าผมผลักดันให้สิ่งที่ ลงบนกองสิ่งที่ เห็นได้ชัดว่าจะเกิดขึ้น ในเวลาเพียงไม่กี่ช่วงเวลา? เรากำลังจะไปทำงานออกจากพื้นที่ และสิ่งที่เราจะทำอย่างไร เรากำลังเมาชนิดของ การดำเนินการนี​​้ไม่ได้ให้ เราปรับขนาดอาร์เรย์เพราะใช้ รูปแบบนี้ถ้าคุณ คิดว่ากลับไปสองสัปดาห์ เมื่อคุณได้ประกาศ ขนาดของอาร์เรย์ เราไม่ได้เห็นกลไกที่ยัง คุณสามารถเปลี่ยนขนาดของอาร์เรย์ และแน่นอน C ไม่ได้มีคุณลักษณะที่ ถ้าคุณบอกว่าให้ฉันห้า NTHS เรียกพวกเขาตัวเลข นั่นคือทั้งหมดที่คุณกำลังจะได้รับมัน ดังนั้นเราจึงทำตอนนี้ในวันจันทร์ได้ ความสามารถในการแสดงวิธีการแก้ปัญหา แต่เราก็ต้องปรับแต่ง คำนิยามของสแต็คของเรา เพื่อไม่ให้มีบางอาร์เรย์ตายตัว, แต่เพียงในการจัดเก็บที่อยู่ 

ตอนนี้ทำไมนี้คืออะไร? ตอนนี้เราก็จะต้องมีความสะดวกสบายด้วย ความจริงที่ว่าเมื่อโปรแกรมของฉันทำงาน ฉันน่าจะไป ต้องถามมนุษย์ จำนวนตัวเลขที่คุณต้องการในการจัดเก็บ? ดังนั้นการป้อนข้อมูลได้ที่จะมาจากที่ไหนสักแห่ง แต่เมื่อฉันรู้ว่า จำนวนแล้วฉันก็สามารถ ใช้สิ่งที่ทำงานที่จะให้ ฉันรู้ของหน่วยความจำหรือไม่? ฉันสามารถใช้ malloc และผมสามารถพูดได้หมายเลขใด ๆ ไบต์ฉันต้องการกลับ NTHS เหล่านี้ และทั้งหมดที่ฉันต้องเก็บในตัวเลข ตัวแปรที่นี่ภายในของโครงสร้างนี้ ควรจะเป็นสิ่งที่? สิ่งที่จริงจะเข้าสู่ ตัวเลขในสถานการณ์นี้ ใช่ตัวชี้ไปแรก ไบต์ของก้อนของหน่วยความจำที่ หรือมากขึ้นโดยเฉพาะที่อยู่ ในครั้งแรกของผู้ไบต์ ไม่สำคัญว่าถ้ามันเป็นหนึ่งใน ไบต์หรือพันล้านไบต์ ฉันต้องดูแลเกี่ยวกับครั้งแรก เพราะสิ่งที่ค้ำประกัน malloc และ การค้ำประกันระบบปฏิบัติการของฉัน คือก้อนของหน่วยความจำฉัน ได้รับก็เป็นไปได้ที่ต่อเนื่องกัน มีไม่ได้จะเป็นช่องว่าง ดังนั้นถ้าฉันถาม 50 ไบต์หรือ 1,000 ไบต์ พวกเขากำลังทั้งหมดไปได้ กลับไปกลับไปกลับ และตราบใดที่ผมจำได้ว่าใหญ่แค่ไหน ฉันถามสิ่งที่ผมจำเป็นต้องรู้ คือที่อยู่ดังกล่าวครั้งแรก 

ดังนั้นตอนนี้เรามีความสามารถในรหัส แม้ว่ามันจะพาเรา มีเวลามากขึ้นที่จะเขียนนี้ขึ้น ตอนนี้เราสามารถจัดสรรหน่วยความจำที่โดย เพียงแค่การจัดเก็บที่อยู่ที่แตกต่างกันมี ถ้าเราต้องการที่ใหญ่กว่าหรือแม้กระทั่ง เป็นก้อนขนาดเล็กของหน่วยความจำ ดังนั้นที่นี่เพื่อการค้าปิด ตอนนี้เราได้รับอย่างแคล่วคล่อง เรายังคงมี contiguousness ฉันอ้าง เพราะ malloc จะให้เรา ก้อนที่ต่อเนื่องกันของหน่วยความจำ แต่นี้เป็นไปได้ในความเจ็บปวด คอสำหรับเราโปรแกรมเมอร์ รหัสขึ้นจริง มันเป็นเพียงแค่การทำงานมากขึ้น เราจำเป็นต้องมีรหัสคล้ายกับสิ่งที่ฉันเป็น ตีตัวออกสักครู่ที่ผ่านมา doable มาก แต่ก็เพิ่มความซับซ้อน และเพื่อให้เวลานักพัฒนาโปรแกรมเมอร์ เวลายังเป็นทรัพยากรที่อื่น ที่เราอาจจำเป็นต้องใช้จ่าย เวลาที่จะได้รับคุณสมบัติใหม่ และแล้วแน่นอนมีคิว เราจะไม่เข้าไปนี้ หนึ่งในรายละเอียดมาก แต่มันก็คล้ายกันมากในจิตวิญญาณ ฉันสามารถใช้คิวและ การดำเนินงานที่สอดคล้องกันของ Enqueue หรือ dequeue เช่นเพิ่มหรือลบ มันเป็นเพียงวิธีที่นักเล่นบอกว่ามัน enqueue หรือ dequeue ดังต่อไปนี้ ฉันสามารถให้ตัวเอง struct อีกครั้งมีอาร์เรย์ของจำนวนที่ อีกครั้งที่มีขนาด แต่ทำไมตอนนี้ผมต้องการ เพื่อติดตามด้านหน้าของคิวหรือไม่ ผมไม่จำเป็นต้องรู้ ด้านหน้าของสแต็คของฉัน ดีถ้าฉันอีกครั้งสำหรับ queue-- ให้เพียงอย่างหนัก รหัสมันมีเหมือนห้า เลขที่อาจเกิดขึ้นที่นี่ ดังนั้นนี่คือศูนย์หนึ่งสองสามสี่ นี้เป็นไปได้ เรียกว่าตัวเลขอีกครั้ง และสิ่งนี้จะถูกเรียกว่าขนาด 

ทำไมมันจึงไม่เพียงพอ จะมีขนาดเพียง? ดีขอผลักดันตัวเลขเดียวกันผู้ที่อยู่ใน ดังนั้นผมจึง pushed-- ฉัน enqueued หรือผลักดัน ตอนนี้ผมจะ enqueue 50 แล้ว 51, 61 แล้วและจุดจุดจุด ดังนั้นที่กำหนดไว้เป็นลำดับ ฉัน enqueued 50 แล้ว 51 แล้ว 61 และมีลักษณะที่เหมือนกันว่า ไปกองป่านนี้ ยกเว้นผมไม่ต้องการที่จะทำให้การเปลี่ยนแปลงอย่างใดอย่างหนึ่ง ผมจำเป็นต้องปรับปรุงขนาดนี้ดังนั้นฉันไป จากศูนย์ถึงหนึ่งไป 2-3 ในขณะนี้ ฉันจะ dequeue อย่างไร ที่เกิดขึ้นกับ dequeue อะไร? ใครควรจะมาออกรายการนี​​้เป็นครั้งแรก ถ้าเป็นเส้นที่ร้านแอปเปิ้ล? ดังนั้น 50 ดังนั้นจึงเป็นชนิดของ trickier เวลานี้ ขณะที่ครั้งที่แล้วมันเป็นซุปเปอร์ เรื่องง่ายที่จะทำขนาดลบหนึ่ง ฉันได้รับการสิ้นสุดของอาเรย์ของฉันได้อย่างมีประสิทธิภาพ ที่ตัวเลขที่มีก็เอา 61 แต่ฉันไม่ต้องการที่จะลบ 61 ฉันต้องการที่จะใช้เวลา 50 ที่ มีที่ 05:00 เข้าแถวสำหรับ iPhone ใหม่หรือ whatnot และเพื่อที่จะได้รับการกำจัดของ 50 ผม ก็ไม่สามารถทำเช่นนี้ใช่มั้ย? ฉันสามารถข้ามออก 50 แต่เราก็บอกว่าเรา ไม่จำเป็นต้องเป็นทางทวารหนั​​กเพื่อ เป็นรอยขีดข่วนหรือซ่อนข้อมูล เราก็สามารถลืมมันอยู่ที่ไหน 

แต่ถ้าผมเปลี่ยนขนาดของฉันตอนนี้ ทั้งสองนี้เป็นข้อมูลที่เพียงพอ ที่จะรู้ว่าสิ่งที่เกิดขึ้นในคิวของฉันได้อย่างไร ไม่ได้จริงๆ เช่นขนาดของฉันคือสอง แต่ ที่ไม่คิวเริ่มต้น โดยเฉพาะอย่างยิ่งถ้าฉันยังคงมี ผู้ที่ตัวเลขเดียวกันในหน่วยความจำ 50, 51, 61 ดังนั้นผมจึงต้องจำไว้ ตอนนี้ที่ด้านหน้าเป็น และอื่น ๆ ตามที่ผมเสนอขึ้น ที่นั่นเราจะได้เรียกว่าเพียงแค่ ชับหน้าซึ่งเริ่มต้น ค่าควรจะได้รับสิ่งที่? ศูนย์เพียงจุดเริ่มต้นของรายการ แต่ตอนนี้นอกเหนือไปจาก decrementing ขนาดเราก็เพิ่มขึ้นด้านหน้า ตอนนี้ที่นี่เป็นอีกปัญหาหนึ่ง ดังนั้นเมื่อผมให้ไป คิดว่านี้คือจำนวนของ เช่น 121, 124, และจากนั้นซ, ฉันออกจากพื้นที่ แต่รอสักครู่ฉันไม่ ดังนั้นที่จุดในเรื่องนี้ สมมติว่าขนาดเป็นหนึ่งในสอง สามสี่จึงคิดว่า ขนาดสี่ด้านหน้าเป็นหนึ่ง ดังนั้น 51 ที่ด้านหน้า ฉันต้องการที่จะนำหมายเลขอื่นที่นี่ แต่บ้าผมออกจากพื้นที่ แต่ฉันไม่ได้จริงๆใช่มั้ย? ที่ฉันสามารถนำบางส่วน มูลค่าเพิ่มเช่น 171? ใช่ฉันทำได้เพียงแค่ชนิดของ กลับไปที่นั่นใช่มั้ย? และจากนั้นก็ข้ามออก 50 หรือ เพียงเขียนทับด้วย 171 และถ้าคุณกำลังสงสัยว่าทำไม ตัวเลขที่เราได้สุ่มเช่นนั้น เหล่านี้จะถูกนำทั่วไปคอมพิวเตอร์ หลักสูตรวิทยาศาสตร์ที่ Harvard หลังจาก CS50 แต่นั่นก็เป็นการเพิ่มประสิทธิภาพที่ดี เพราะตอนนี้ผมไม่ได้สูญเสียพื้นที่ ฉันยังคงต้องจำไว้ วิธีการใหญ่สิ่งนี้รวม มันเป็นห้ารวม เพราะผมไม่ต้องการที่จะ เริ่มต้นการเขียนทับ 51 ดังนั้นตอนนี้ผมยังคงออกจากพื้นที่ เพื่อให้ปัญหาที่เกิดขึ้นเช่นเดียวกับก่อน แต่คุณสามารถดูวิธีการในขณะนี้ ในรหัสของคุณคุณอาจ ต้องเขียนเล็ก ๆ น้อย ๆ ความซับซ้อนที่จะทำให้มันเกิดขึ้น และในความเป็นจริงสิ่งที่ผู้ประกอบการ ใน C อาจจะช่วยให้ คุณทำเช่นนี้ได้อย่างน่าอัศจรรย์วัฏจักรหรือไม่ ใช่ผู้ประกอบการโมดูโล, สัญญาณที่ร้อยละ ดังนั้นสิ่งที่เป็นชนิดของดีๆเกี่ยวกับคิว แม้ว่าเราจะเก็บอาร์เรย์การวาดภาพ เหล่านี้เป็นเส้นตรงเช่นถ้าคุณ ชนิดของการคิดเกี่ยวกับเรื่องนี้เป็นโค้ง รอบเป็นวงกลมแล้วก็ สังหรณ์ใจชนิดของมันทำงานจิตใจ ผมคิดว่าเล็ก ๆ น้อย ๆ อย่างหมดจด คุณยังจะต้องดำเนินการ ว่ารูปแบบทางจิตในรหัส ดังนั้นไม่ยาก ท้ายที่สุดที่จะใช้ แต่เรายังคงสูญเสีย size-- ค่อนข้างที่ ความสามารถในการปรับขนาด, หากเราทำเช่นนี้ 

เราจะต้องได้รับการกำจัดของอาร์เรย์เรา แทนที่ด้วยตัวชี้เดียว แล้วที่ไ​​หนสักแห่งในรหัสของฉันฉันมี โทรสิ่งที่ทำงานจริงสร้าง อาร์เรย์ที่เรียกว่าตัวเลข? malloc หรือบางที่คล้ายกัน ฟังก์ชั่นว่า คำถามใด ๆ เกี่ยวกับกองหรือคิว ใช่? คำถามที่ดี. สิ่งที่โมดูโลที่คุณจะใช้ที่นี่ ดังนั้นโดยทั่วไปเมื่อมีการใช้ สมัยคุณจะทำมัน ที่มีขนาดของ โครงสร้างข้อมูลทั้งหมด ดังนั้นสิ่งที่ต้องการความจุห้าหรือถ้า ก็คงอาจจะมีส่วนเกี่ยวข้อง แต่เพียงแค่การทำแบบโมดูโลห้า อาจจะไม่เพียงพอ เพราะเราจำเป็นต้องรู้ว่าเราทำ ห่อรอบที่นี่หรือที่นี่หรือที่นี่ ดังนั้นคุณอาจจะยัง จะต้องการที่จะมีส่วนร่วม ขนาดของสิ่งหรือ ตัวแปรหน้าได้เป็นอย่างดี ดังนั้นจึงเป็นเพียงแค่นี้ค่อนข้าง การแสดงออกทางคณิตศาสตร์ที่เรียบง่าย แต่โมดูโลจะเป็นองค์ประกอบที่สำคัญ 

หนังสั้นดังนั้นถ้าคุณจะ ภาพเคลื่อนไหวที่บาง folks ที่มหาวิทยาลัยอื่น ใส่กันที่เราได้ เหมาะสำหรับการสนทนานี้ มันเกี่ยวข้องกับแจ็คการเรียนรู้ ข้อเท็จจริงเกี่ยวกับการรอคิวและสถิติ 

ฟิล์ม: กาลครั้งหนึ่ง, มีผู้ชายที่ชื่อแจ็ค เมื่อมันมาถึงการทำเพื่อน แจ็คไม่ได้มีความสามารถพิเศษ ดังนั้นแจ็คก็ไปพูดคุยกับ คนที่นิยมมากที่สุดที่เขารู้ เขาเดินไปที่ลูและถามว่าฉันจะทำอย่างไร? ลูเห็นว่าเพื่อนของเขา เป็นทุกข์จริงๆ ดีเขาเริ่มเพียง ดูวิธีการที่คุณสวมใส่ คุณไม่มีเสื้อผ้าใด ๆ ด้วยรูปลักษณ์ที่แตกต่างกันอย่างไร ใช่แจ็คกล่าวว่า ผมแน่ใจว่าจะทำอย่างไร มาที่บ้านของฉันและ ฉันจะแสดงให้คุณเห็น ดังนั้นพวกเขาจึงออกไปของแจ็ค และแสดงให้เห็นว่าแจ็คลูกล่อง ที่เขาเก็บเสื้อของเขาทั้งหมด และกางเกงขายาวของเขาและถุงเท้าของเขา ลูกล่าวว่าผมเห็นคุณมี เสื้อผ้าของคุณทั้งหมดในกอง ทำไมคุณไม่สวมใส่บาง คนอื่น ๆ ครั้งในชั่วขณะ? 

แจ็คกล่าวว่าดีเมื่อฉัน เอาเสื้อผ้าและถุงเท้า ผมล้างพวกเขาและใส่ พวกเขาออกไปในกล่อง แล้วมาต่อไป เช้าและฉันกระโดดขึ้น ฉันไปที่กล่องและได้รับ เสื้อผ้าของฉันออกด้านบน ลูตระหนักได้อย่างรวดเร็ว ปัญหาที่เกิดขึ้นกับแจ็ค เขาเก็บเสื้อผ้าของซีดี และหนังสือในกอง เมื่อเขาไปถึงสำหรับ บางสิ่งบางอย่างที่จะอ่านหรือการสวมใส่ เขาจะเลือกหนังสือด้านบนหรือชุดชั้นใน จากนั้นเมื่อเขาทำเขา จะวางไว้ด้านหลังขวา กลับมันจะไปที่ด้านบนของสแต็ค ฉันรู้ว่าการแก้ปัญหา กล่าวว่าชัยชนะดัง คุณต้องเรียนรู้ที่จะ เริ่มใช้คิว ลูเอาเสื้อผ้าของแจ็คและ แขวนไว้ในตู้เสื้อผ้า และเมื่อเขาได้หมด กล่องเขาก็โยนมัน 

จากนั้นเขาก็กล่าวว่าตอนนี้แจ็คในตอนท้ายของ วันที่ใส่เสื้อผ้าของคุณด้านซ้าย เมื่อคุณใส่พวกเขาออกไป แล้วพรุ่งนี้เช้าเมื่อคุณ เห็นแสงแดดที่ได้รับเสื้อผ้าของคุณ ด้านขวาจากจุดสิ้นสุดของเส้น คุณไม่เห็น? ลูกล่าวว่า มันจะดีมาก คุณจะได้สวมใส่ทุกอย่างในครั้งเดียว ก่อนที่คุณจะสวมใส่สิ่งที่เป็นครั้งที่สอง และมีทุกอย่างที่อยู่ในคิว ในตู้เสื้อผ้าและชั้นวางของเขา แจ็คเริ่มรู้สึก ค่อนข้างแน่ใจว่าตัวเอง ขอบคุณทุกลูและ คิวยอดเยี่ยมของเขา ลำโพงที่ 1: สิทธิทั้งหมดมันเป็นเรื่องที่น่ารัก ดังนั้นสิ่งที่ได้รับจริงที่เกิดขึ้น ในใต้ฝากระโปรงตอนนี้? ว่าเรามีตัวชี้ ที่เรามี malloc, ว่าเรามีความสามารถในการสร้าง ชิ้นของหน่วยความจำสำหรับตัวเอง แบบไดนามิก ดังนั้นนี่คือภาพที่เรา เห็นเพียงวันอื่น ๆ เราไม่ได้จริงๆอาศัยอยู่ ใน แต่ภาพนี้ มีเกิดขึ้นอยู่ภายใต้ เครื่องดูดควันสำหรับสัปดาห์นี้ ดังนั้นนี้เป็นเพียง สี่เหลี่ยมผืนผ้าที่เราได้วาด, หน่วยความจำของคอมพิวเตอร์ของคุณ และบางทีคอมพิวเตอร์ของคุณหรือ CS50 ID มีกิกะไบต์หน่วยความจำหรือแรม หรือสองหรือสี่กิกะไบต์ มันไม่สำคัญว่าจริงๆ ระบบปฏิบัติการของคุณ Windows หรือ Mac OS หรือ Linux หลักช่วยให้โปรแกรมของคุณ ที่จะคิดว่ามันมีการเข้าถึง เพื่อความสมบูรณ์ของ หน่วยความจำของคอมพิวเตอร์ของคุณ แม้ว่าคุณอาจจะทำงาน โปรแกรมหลายครั้ง ดังนั้นในความเป็นจริงที่ไม่ได้ทำงานจริงๆ แต่มันเป็นชนิดของภาพลวงตา มอบให้กับทุกโปรแกรมของคุณ ดังนั้นถ้าคุณมีสองกิ๊กของแรมนี้ เป็นวิธีการที่เครื่องคอมพิวเตอร์อาจจะคิดว่ามัน 

ตอนนี้บังเอิญหนึ่งในจำนวนนี้ สิ่งหนึ่งในกลุ่มเหล่านี้ของหน่วยความจำ เรียกว่ากอง และแน่นอนทุกเวลา ป่านนี้ในการเขียนรหัส ที่คุณได้เรียกว่า ฟังก์ชั่นเช่นหลัก จำได้ว่าเวลาใดที่ฉันได้ หน่วยความจำคอมพิวเตอร์วาดของ ฉันมักจะวาดการเรียงลำดับของ ครึ่งหนึ่งของรูปสี่เหลี่ยมผืนผ้าที่นี่ และไม่รบกวนการพูดคุย เกี่ยวกับสิ่งที่กล่าวข้างต้น เพราะเมื่อหลักที่เรียกว่าผมเรียกร้อง ที่คุณได้รับเศษไม้จากหน่วยความจำนี้ ที่จะไปลงที่นี่ และถ้าหลักที่เรียกว่าฟังก์ชั่น เช่นการแลกเปลี่ยนดีแลกเปลี่ยนที่นี่ และปรากฎว่า ที่มันสิ้นสุด ในสิ่งที่เรียกว่ากอง ภายในของหน่วยความจำของคอมพิวเตอร์ของคุณ ตอนนี้ในตอนท้ายของวัน นี้เป็นเพียงที่อยู่ มันเหมือนไบต์ศูนย์ ไบต์หนึ่งไบต์ 2 พันล้าน แต่ถ้าคุณคิดเกี่ยวกับมัน เป็นวัตถุรูปสี่เหลี่ยมนี้ ทุกสิ่งที่เรากำลังทำทุก เวลาที่เราเรียกฟังก์ชั่นเป็น layering ชิ้นใหม่ของหน่วยความจำ เรากำลังให้ฟังก์ชั่นที่ชิ้น ของหน่วยความจำของตัวเองในการทำงานกับ 

และจำได้ว่าตอนนี้นี้เป็นสิ่งสำคัญ เพราะถ้าหากเราจะมี สิ่งที่ต้องการแลกเปลี่ยน และสองตัวแปรท้องถิ่นเช่น A และ B และ เราเปลี่ยนค่าเหล่านั้นจากที่หนึ่งและสอง สองและเป็นหนึ่งในการเรียกคืน ว่าเมื่อผลตอบแทนแลกเปลี่ยน มันราวกับว่าชิ้นนี้ ของหน่วยความจำจะหายไปเพียง ในความเป็นจริงก็ยังคง มี forensically และสิ่งที่ยังคงเป็นจริงมี แต่แนวคิดก็เป็น แม้ว่ามันจะหายไปอย่างสมบูรณ์ และที่สำคัญเพื่อไม่ทราบใด ๆ ของการทำงาน ที่ได้ทำในฟังก์ชั่นการแลกเปลี่ยนนั้น เว้นแต่จะผ่านจริงเหล่านั้น โดยตัวชี้ข้อโต้แย้งหรือการอ้างอิง ตอนนี้การแก้ปัญหาพื้นฐาน ในการแก้ไขปัญหาที่มีการแลกเปลี่ยน จะผ่านสิ่งที่อยู่ในที่อยู่ แต่มันกลับกลายเป็นเหมือนกันว่ามีอะไร รับไปในข้างต้นเป็นส่วนหนึ่ง ของสี่เหลี่ยมตลอดเวลานี้ ยังมีหน่วยความจำมากขึ้นมี และเมื่อคุณแบบไดนามิก จัดสรรหน่วยความจำ ไม่ว่าจะเป็นด้านในของ GetString ซึ่ง เราได้รับการทำสำหรับคุณใน CS50 ห้องสมุดหรือถ้าพวกคุณ เรียก malloc และขอให้ ระบบปฏิบัติการสำหรับก้อนของ หน่วยความจำมันไม่ได้มาจากกอง มันมาจากที่อื่น ในหน่วยความจำของคอมพิวเตอร์ของคุณ ที่เรียกว่ากอง และที่ไม่แตกต่างกัน มันเป็นแรมเดียวกัน มันเป็นหน่วยความจำเดียวกัน มันเป็นเพียงแค่แรมที่ขึ้น มีแทนที่จะลงที่นี่ 

ดังนั้นสิ่งที่หมายความว่า? ดีถ้าคอมพิวเตอร์ของคุณมี จำนวน จำกัด ของหน่วยความจำ และสแต็คที่มีการเติบโตขึ้นดังนั้น ที่จะพูดและกองตาม ไปที่ลูกศรนี้มีการเติบโตลดลง ในคำอื่น ๆ ทุกคน ครั้งที่คุณโทร malloc, คุณกำลังจะได้รับชิ้น ของหน่วยความจำมาจากเบื้องบน แล้วอาจจะต่ำกว่าเล็กน้อยแล้วเล็กน้อย ต่ำกว่าครั้งที่คุณโทร malloc ทุก กองก็ใช้งาน เป็นชนิดของการเจริญเติบโต การเจริญเติบโตใกล้ชิดและใกล้ชิดกับสิ่งที่? สแต็ค ดังนั้นนี้ไม่ได้ดูเหมือนเป็นความคิดที่ดี? ผมหมายถึงที่มันไม่ชัดเจนจริงๆ อะไรที่คุณสามารถทำได้ถ้าคุณเพียง มีจำนวน จำกัด ของหน่วยความจำ แต่นี้ไม่ดีแน่ ทั้งสองลูกศรที่อยู่บน ความผิดพลาดแน่นอนสำหรับอีกคนหนึ่ง 

และปรากฎว่าคนเลว, คนที่ โดยเฉพาะอย่างยิ่งที่ดีกับการเขียนโปรแกรม และพยายามที่จะตัดเข้าสู่คอมพิวเตอร์ สามารถใช้ประโยชน์ความเป็นจริงนี้ ในความเป็นจริงให้พิจารณา ตัวอย่างเล็ก ๆ น้อย ๆ ดังนั้นนี่คือตัวอย่างเช่นคุณสามารถอ่าน เกี่ยวกับรายละเอียดเพิ่มเติมเกี่ยวกับวิกิพีเดีย เราจะชี้ให้คุณที่ ถ้าอยากรู้บทความ แต่มีการโจมตีโดยทั่วไป ที่รู้จักกันเป็นหน่วยความจำล้นที่ มีชีวิตอยู่ให้นานที่สุดเท่าที่มนุษย์ มีความสามารถในการจัดการ หน่วยความจำของคอมพิวเตอร์โดยเฉพาะอย่างยิ่งใน C. ดังนั้นนี้เป็นโปรแกรมใดมาก แต่ให้อ่านได้จากด้านล่างขึ้น หลักลงในถ่านดาว argc argv ดังนั้นจึงเป็นโปรแกรมที่ใช้ อาร์กิวเมนต์บรรทัดคำสั่ง และที่สำคัญทุกคนไม่เห็นได้ชัดคือการเรียกร้อง ฟังก์ชั่นที่เรียกว่า F สำหรับความเรียบง่าย และมันก็ผ่านไปในสิ่งที่? argv หนึ่ง ดังนั้นจึงผ่านเข้าไปในสิ่งที่ F เป็นคำที่ว่าผู้ใช้พิมพ์ ที่พรอมต์หลังจากที่ ชื่อโปรแกรมที่ทุก มากเช่นซีซาร์หรือ Vigenere ซึ่ง คุณอาจจำทำกับ argv 

ดังนั้นสิ่งที่เป็น F? F ใช้เวลาในสตริง เป็นอาร์กิวเมนต์ แต่เพียงผู้เดียว AKA ดาวถ่านเดียวกัน สิ่งที่เป็นสตริง และก็เรียกว่าโดยพลการ บาร์ในตัวอย่างนี้ และแล้วถ่านค 12 เพียง แต่ในแง่ของคนธรรมดา สิ่งที่เป็นถ่านวงเล็บค 12 ทำสำหรับเรา? มันเป็นสิ่งที่ทำอย่างไร จัดสรรหน่วยความจำโดยเฉพาะ 12 ไบต์ 12 ตัวอักษร ที่แน่นอน และแล้วบรรทัดสุดท้าย, ผัดและ คัดลอกคุณอาจไม่เคยเห็น นี่เป็นสำเนาสตริง ฟังก์ชั่นที่มีจุดมุ่งหมายในชีวิต คือการคัดลอกอาร์กิวเมนต์ที่สองของ โต้เถียงแรก แต่ขึ้นไป จำนวนหนึ่งไบต์ ดังนั้นอาร์กิวเมนต์ที่สามกล่าวว่า จำนวนไบต์คุณควรคัดลอก? ความยาวของบาร์ สิ่งที่ผู้ใช้พิมพ์ลงใน และเนื้อหาของ บาร์, สตริงที่มี คัดลอกลงในหน่วยความจำที่ชี้ไปที่ซี 

ดังนั้นนี้ดูเหมือนว่าชนิดของโง่และมันก็เป็น มันเป็นตัวอย่างที่ประดิษฐ์, แต่มันก็เป็นตัวแทน ของชั้นเรียนของเวกเตอร์โจมตี, วิธีการโจมตีโปรแกรมได้ ทั้งหมดเป็นสิ่งที่ดีและสิ่งที่ดีถ้าผู้ใช้ ชนิดในคำว่า 11 ตัวอักษร หรือน้อยกว่ารวมทั้งศูนย์ทับขวา เกิดอะไรขึ้นถ้าผู้ใช้ชนิดในกว่า 11 หรือ 12 หรือ 20 หรือ 50 ตัวอักษร? โปรแกรมนี้จะทำคืออะไร? ความผิดพลาดที่อาจเกิด seg มันจะ สุ่มสี่สุ่มห้าคัดลอกทุกอย่างในแถบขึ้น ความยาวของซึ่งเป็น แท้จริงทุกอย่างในบาร์ เข้าไปในที่อยู่ชี้ไปที่ซี แต่ C มีเพียงได้รับ preemptively 12 ไบต์ แต่ไม่มีการตรวจสอบเพิ่มเติม ไม่มีถ้าเงื่อนไข มีข้อผิดพลาดไม่ได้ตรวจสอบที่นี่ 

และเพื่อให้สิ่งที่โปรแกรมนี้คือ จะทำคือเพียงสุ่มสี่สุ่มห้า คัดลอกสิ่งที่หนึ่งไปยังอีก ดังนั้นถ้าเราวาดนี้ เป็นรูปภาพที่นี่ เพียงเศษไม้ของพื้นที่หน่วยความจำ ดังนั้นสังเกตที่ด้านล่างเรา มีบาร์ตัวแปรท้องถิ่น ดังนั้นตัวชี้ว่าจะ store-- ว่า ค่อนข้างที่โต้แย้งในท้องถิ่นที่ จะเก็บบาร์สตริง และจากนั้นก็สังเกตเห็นเพียง ดังกล่าวข้างต้นในกอง เพราะเวลาที่คุณถามทุก สำหรับหน่วยความจำบนกอง มันจะไปนิด ๆ หน่อย ๆ เหนือ pictorially, แจ้งให้ทราบว่าเรามี 12 ไบต์มี หนึ่งบนซ้ายเป็นวงเล็บ C ศูนย์และ หนึ่งที่เหมาะสมล่างคือยึด C 11 นั่นเป็นเพียงวิธีการที่คอมพิวเตอร์ ไปวางมันออกมา ดังนั้นเพียงแค่สังหรณ์ใจถ้าแถบมี กว่า 12 ตัวอักษรในทั้งหมดรวมถึง เครื่องหมายศูนย์ซึ่งเป็น 12 หรือวงเล็บ C 12 จะไป? หรือมากกว่าที่เป็นที่ 12 ตัวอักษรหรือตัวอักษรที่ 13 ตัวอักษรที่ร้อยไป ที่จะจบลงในภาพหรือไม่ สูงหรือต่ำกว่า? 

ขวาเพราะแม้ว่า สแต็คของตัวเองเติบโตขึ้น เมื่อคุณได้นำสิ่งที่อยู่ใน มันด้วยเหตุผลที่การออกแบบ ทำให้หน่วยความจำจากบนลงล่าง ดังนั้นถ้าคุณได้มีมากกว่า 12 ไบต์ คุณกำลังจะเริ่มต้นในการเขียนทับบาร์ ตอนนี้ที่ข้อผิดพลาด แต่มัน ไม่ได้จริงๆเป็นเรื่องใหญ่ แต่มันเป็นเรื่องใหญ่เพราะมี สิ่งอื่น ๆ อีกที่เกิดขึ้นในหน่วยความจำ ดังนั้นนี่คือวิธีการที่เราอาจจะ ใส่สวัสดีต้องมีความชัดเจน ถ้าผมพิมพ์ลงในสวัสดีที่พรอมต์ H-E-L-L-O เครื่องหมายศูนย์จบลงภายใน ผู้ที่ 12 ไบต์และเราจะปลอดภัยสุด ทั้งหมดเป็นอย่างดี. แต่ถ้าผมพิมพ์บางสิ่งบางอย่าง อีกต่อไปที่อาจเกิดขึ้นมันเป็น จะคืบคลานเข้ามาในพื้นที่แถบ แต่แย่ลงยังก็จะเปิด ออกทั้งหมดเวลานี้ แม้ว่าเราจะไม่เคยพูดคุยเกี่ยวกับ มันสแต็คที่ใช้สำหรับสิ่งอื่น ๆ มันไม่ใช่แค่ตัวแปรท้องถิ่น 

ซีเป็นภาษาระดับต่ำมาก และการจัดเรียงของแอบ ใช้สแต็คยัง ที่ต้องจำไว้เมื่อ ฟังก์ชั่นที่เรียกว่าสิ่งที่ ที่อยู่ของการทำงานก่อนหน้านี้ เพื่อที่จะสามารถกระโดดกลับไปที่ฟังก์ชั่นที่ ดังนั้นเมื่อสลับสายหลักหมู่ สิ่งที่ผลักลงบนกอง ไม่เพียง แต่แลกเปลี่ยนตัวแปรท้องถิ่น หรือข้อโต้แย้งที่ยังผลักดันแอบ บนสแต็คเป็นตัวแทน โดยชิ้นสีแดงที่นี่ เป็นที่อยู่ของหลักทางร่างกาย ในหน่วยความจำของคอมพิวเตอร์ของคุณ เพื่อที่ว่าเมื่อแลกเปลี่ยนจะทำคอมพิวเตอร์ รู้ดีว่าฉันต้องการที่จะกลับไปเป็นหลัก และเสร็จสิ้นการดำเนินการฟังก์ชั่นหลัก ดังนั้นนี่คืออันตรายในขณะนี้เพราะถ้า ประเภทของผู้ใช้ในดีกว่าสวัสดี ดังกล่าวว่าการป้อนข้อมูลของผู้ใช้ clobbers หรือเขียนทับส่วนที่เป็นสีแดง ถ้ามีเหตุผลของคอมพิวเตอร์ เพียงแค่จะสุ่มสี่สุ่มห้าถือว่า ว่าไบต์ในชิ้นที่มีสีแดง ที่อยู่ที่มันควรจะกลับมา สิ่งที่ถ้าฝ่ายตรงข้ามจะฉลาดพอหรือ โชคดีพอที่จะทำให้ลำดับของไบต์ มีที่มีลักษณะเช่นที่อยู่, แต่มันเป็นเรื่องที่อยู่ของรหัส ที่เขาหรือเธอต้องการคอมพิวเตอร์ ในการดำเนินการแทนการหลัก? 

ในคำอื่น ๆ ถ้าสิ่งที่เป็น ผู้ใช้จะพิมพ์ที่พรอมต์, ไม่ได้เป็นเพียงแค่สิ่งที่ ไม่มีอันตรายเช่นสวัสดี แต่มันเป็นเรื่องจริงรหัสที่เทียบเท่า จะลบไฟล์ทั้งหมดของผู้ใช้นี้หรือไม่? หรือส่งอีเมลรหัสผ่านของพวกเขากับผมหรือเปล่า หรือเริ่มต้นการเข้าสู่ระบบของพวกเขา การกดแป้นพิมพ์ใช่มั้ย? มีวิธีขอกำหนดวันนี้ ว่าพวกเขาสามารถพิมพ์ไม่ได้เป็นเพียงทักทาย โลกหรือชื่อของพวกเขา พวกเขาสามารถเป็นหลัก รหัสผ่านในศูนย์และ คนที่ใช้คอมพิวเตอร์ ความผิดพลาดทั้งรหัสและที่อยู่ ดังนั้นแม้จะค่อนข้างเป็นนามธรรมถ้า ผู้ใช้พิมพ์ในรหัสขัดแย้งพอ ว่าเราจะคุยที่นี่ A. คือการโจมตีฝ่ายตรงข้ามหรือ สิ่งที่ไม่ดีดังนั้นเพียงแค่ เราไม่ได้ดูแลเกี่ยวกับ ตัวเลขหรือค่าศูนย์หรือคน วันนี้เช่นที่คุณจบลง เขียนทับส่วนที่เป็นสีแดง แจ้งให้ทราบลำดับของไบต์ที่ O 835 C ศูนย์แปดศูนย์ และในขณะนี้เป็นบทความวิกิพีเดียที่นี่ ได้เสนอถ้าคุณตอนนี้จะเริ่มต้น การติดฉลากไบต์ในของเครื่องคอมพิวเตอร์ของคุณ หน่วยความจำสิ่งที่บทความวิกิพีเดีย เสนอคือสิ่งที่ถ้าที่อยู่ ที่ด้านบนซ้ายไบต์ 80 C 0 3508 

ในคำอื่น ๆ ถ้าเป็นคนเลว ฉลาดพอที่มีรหัสของเขาหรือเธอ ที่จริงการใส่หมายเลขที่นี่ว่า ตรงไปยังที่อยู่ของรหัส เขาหรือเธอฉีด ลงในคอมพิวเตอร์ของคุณ สามารถหลอกลวงคอมพิวเตอร์ ในการทำอะไร การลบไฟล์ที่ส่งอีเมล สิ่งที่การดมกลิ่นการจราจรของคุณ สิ่งที่อาจจะเป็นตัวอักษร ฉีดเข้าไปในคอมพิวเตอร์ และเพื่อให้หน่วยความจำล้น การโจมตีที่หลักของ เป็นเพียงโง่โง่ ที่สำคัญของอาร์เรย์ที่ ไม่ได้มีการตรวจสอบขอบเขตของมัน และนี่คือสิ่งที่เป็นอันตรายสุด และพร้อมที่มีประสิทธิภาพสุด ใน C คือการที่เราไม่แน่นอนมี การเข้าถึงไปยังที่ใดในหน่วยความจำ มันขึ้นอยู่กับเราโปรแกรมเมอร์, ที่เขียนรหัสเดิม เพื่อตรวจสอบความยาวของสาปใด ๆ อาร์เรย์ที่เรากำลังจัดการกับ ดังนั้นเพื่อให้มีความชัดเจนสิ่งที่แก้ไขได้หรือไม่? ถ้าเราย้อนกลับไปนี้ รหัสผมไม่ควรเพียง เปลี่ยนความยาวของแถบสิ่งที่ อื่นที่ฉันควรจะได้รับการตรวจสอบ? อะไรที่ฉันควรจะทำเพื่อ ป้องกันการโจมตีครั้งนี้อย่างสิ้นเชิง? ฉันไม่ต้องการที่จะเพียงแค่พูดสุ่มสี่สุ่มห้า ที่คุณควรคัดลอกไบต์เป็นจำนวนมาก เช่นเดียวกับความยาวของบาร์ ผมอยากจะบอกให้คัดลอกเป็น จำนวนไบต์เป็นอยู่ในบาร์ ขึ้นไปที่ได้รับการจัดสรร หน่วยความจำหรือ 12 ที่สุด ดังนั้นผมจึงต้องชนิดของถ้าเงื่อนไขบางอย่าง ที่ไม่ตรวจสอบความยาวของบาร์ แต่ถ้ามันเกินกว่า 12 เรารหัสยากเพียง 12 เป็นระยะทางเป็นไปได้สูงสุด มิฉะนั้นบัฟเฟอร์ที่เรียกว่า โจมตีล้นสามารถเกิดขึ้นได้ ที่ด้านล่างของภาพนิ่งเหล่านั้น ถ้าคุณอยากรู้อยากเห็นในการอ่านมากขึ้น เป็นบทความเดิมที่เกิดขึ้นจริง ถ้าคุณต้องการที่จะดู 

แต่ตอนนี้ในหมู่ราคา การชำระเงินที่นี่เป็นความไร้ประสิทธิภาพ เพื่อให้เป็นที่รวดเร็ว ดูในระดับต่ำในสิ่งที่ ปัญหาจะเกิดขึ้นตอนนี้ที่เรา มีการเข้าถึงหน่วยความจำของคอมพิวเตอร์ แต่ปัญหาที่เราอีก แล้วสะดุดในวันจันทร์ เป็นเพียงขาดประสิทธิภาพ ของรายการที่เชื่อมโยง เราจะกลับไปที่เส้นเวลา เราไม่ได้มีอาร์เรย์ที่ต่อเนื่องกัน เราไม่ได้มีการเข้าถึงแบบสุ่ม เราไม่สามารถใช้เครื่องหมายวงเล็บเหลี่ยม แท้จริงเราต้องใช้ห่วงในขณะที่ เช่นเดียวกับที่ผมเขียนช่วงเวลาที่ผ่านมา แต่ในวันจันทร์ที่เราอ้างว่าเราสามารถทำได้ คืบคลานกลับเข้ามาในดินแดนของประสิทธิภาพ ประสบความสำเร็จในสิ่งที่ ลอการิทึมอาจจะดีที่สุดหรือยัง แม้กระทั่งสิ่งที่ ที่เรียกว่าเวลาคง ดังนั้นวิธีที่เราสามารถทำเช่นนั้นโดยใช้ใหม่ ๆ เหล่านี้ เครื่องมือที่อยู่เหล่านี้ตัวชี้เหล่านี้ และเกลียวสิ่งที่เราเอง? ดีคิดว่า ที่นี่เหล่านี้เป็นพวง ของตัวเลขที่เราต้องการที่จะเก็บใน โครงสร้างข้อมูลและการค้นหาได้อย่างมีประสิทธิภาพ เราอย่างสามารถย้อนกลับไปในสัปดาห์ สองโยนเหล่านี้ลงในอาร์เรย์ และการค้นหาโดยใช้การค้นหาแบบไบนารี แบ่งและพิชิต และในความเป็นจริงที่คุณเขียน การค้นหาแบบไบนารีใน PSET3, ที่คุณนำมาใช้โปรแกรมค้นหา แต่คุณรู้ว่าสิ่งที่ มีชนิดของมากขึ้น วิธีที่ฉลาดในการดำเนินการนี​​้ มันเป็นเรื่องเล็ก ๆ น้อย ๆ ที่มีความซับซ้อนและมันอาจจะ ช่วยให้เราสามารถดูว่าทำไมไบนารี การค้นหาเป็นไปอย่างรวดเร็วยิ่งขึ้น ก่อนขอแนะนำ ความคิดของต้นไม้ ซึ่งแม้ว่าใน ความเป็นจริงชนิดของต้นไม้ เติบโตเช่นนี้ในโลกของคอมพิวเตอร์ วิทยาศาสตร์พวกเขาชนิดของการเติบโตที่ลดลง เหมือนต้นไม้ครอบครัวที่คุณมี ปู่ย่าตายายของคุณหรือปู่ย่าตายายที่ดี หรือ whatnot ที่ด้านบนและพระสังฆราช ปูชนียบุคคลของครอบครัวเพียงหนึ่ง รากที่เรียกว่าโหนดด้านล่าง ที่เป็นบุตรของตน ด้านล่างซึ่งเป็นลูกของตนหรือ ลูกหลานมากขึ้นโดยทั่วไป และทุกคนที่แขวนปิด ด้านล่างของครอบครัว ต้นไม้นอกจากเป็น ที่อายุน้อยที่สุดในครอบครัว ยังสามารถเป็นทั่วไป ที่เรียกว่าใบของต้นไม้ 

ดังนั้นนี้เป็นเพียงพวง คำพูดและคำจำกัดความ สำหรับสิ่งที่เรียกว่าต้นไม้ในคอมพิวเตอร์ วิทยาศาสตร์เหมือนต้นไม้ครอบครัว แต่มีสาขานักเล่น ของต้นไม้ซึ่งหนึ่งในนั้น จะเรียกว่าเป็นต้นไม้ค้นหาแบบทวิภาค และคุณสามารถชนิดของการหยอกล้อ นอกเหนือสิ่งสิ่งนี้ไม่ ดีก็ไบนารีในสิ่งที่เหมาะสมหรือไม่ ไบนารีมาจากไหนนี่? ขออภัย? มันไม่มากหรือ มันขึ้นว่าแต่ละโหนดมีใคร มากกว่าเด็กสองคนที่เราเห็นที่นี่ โดยทั่วไป tree-- และ พ่อแม่และปู่ย่าตายายของคุณ จะมีเด็ก ๆ จำนวนมากหรือ หลานที่พวกเขาต้องการจริง และอื่น ๆ เช่นมีเรามีสาม เด็กออกโหนดมือที่ถูกต้อง แต่ในต้นไม้ไบนารีโหนดมี ศูนย์หนึ่งหรือสองเด็กที่สุด และที่เป็นสถานที่ให้บริการที่ดี เพราะถ้ามันปกคลุมด้วยสอง เราจะสามารถที่จะ ได้รับการเข้าสู่ระบบฐานเล็ก ๆ น้อย ๆ สอง การกระทำที่เกิดขึ้นที่นี่ในที่สุด ดังนั้นเราจึงมีบางสิ่งบางอย่างเกี่ยวกับลอการิทึม แต่เพิ่มเติมว่าในช่วงเวลาที่ ค้นหาต้นไม้หมายความว่าตัวเลข จัดเช่นว่าเด็กซ้าย ค่ามากกว่าราก และสิทธิของเด็กคือ มีขนาดใหญ่กว่าราก ในคำอื่น ๆ ถ้าคุณใช้ใด ๆ ของ โหนดวงกลมในภาพนี้ และมองไปที่ด้านซ้ายของ เด็กและเด็กที่เหมาะสมของตน ครั้งแรกที่ควรจะน้อยกว่า ที่สองควรมากกว่า ดังนั้นสติกา 55 มันเป็นเด็กซ้าย 33 มันน้อยกว่า 55 เด็กที่เหมาะสมคือ 77 มันเป็นเรื่องที่ยิ่งใหญ่กว่า และนั่นคือคำนิยาม recursive เราสามารถตรวจสอบทุกหนึ่งในบรรดา โหนดและรูปแบบเดียวกันจะถือ 

ดังนั้นสิ่งที่ดีใน ต้นไม้ค้นหาแบบทวิภาคเป็น ว่าเราสามารถใช้มัน กับ struct เพียงเช่นนี้ และแม้ว่าเรากำลังขว้างปา จำนวนมากของโครงสร้างที่ของคุณ พวกเขากำลังค่อนข้าง ที่ใช้งานง่ายในขณะนี้หวังว่า ไวยากรณ์ยังคงเป็นความลับเพื่อตรวจสอบว่า แต่เนื้อหาของโหนดในนี้ context-- และเราให้ โดยใช้โหนดคำ ไม่ว่าจะเป็นรูปสี่เหลี่ยมผืนผ้า บนหน้าจอหรือวงกลม มันเป็นเพียงบางส่วนภาชนะทั่วไป ในกรณีนี้ของต้นไม้เช่นหนึ่ง เราเห็นเราต้องเป็นจำนวนเต็ม ในแต่ละโหนด แล้วฉันต้องสองตัวชี้ชี้ เพื่อให้เด็กซ้ายและเด็กที่ถูกต้อง ตามลำดับ นั่นคือวิธีการที่เราอาจจะ การดำเนินการว่าใน struct และวิธีการที่ผมอาจจะใช้มันในรหัส? ดีขอใช้เวลาที่รวดเร็ว ดูตัวอย่างเล็ก ๆ นี้ มันไม่ได้ทำงาน แต่ฉันได้ คัดลอกและวางโครงสร้างที่ และถ้าฟังก์ชั่นของฉันสำหรับไบนารี ค้นหาต้นไม้ที่เรียกว่าการค้นหา และนี่จะใช้เวลาสองข้อโต้แย้ง จำนวนเต็ม n และตัวชี้ ไปยังโหนดเพื่อชี้ไปยังต้นไม้ หรือชี้ไปยังรากของต้นไม้ที่ ฉันจะไปเกี่ยวกับการค้นหาไม่มี? ดีแรกเพราะฉัน การจัดการกับตัวชี้ ฉันจะทำกาสติ ถ้าเท่ากับต้นไม้เท่ากับโมฆะคือไม่มี ในต้นไม้ต้นนี้หรือไม่ในต้นไม้นี้หรือไม่? เป็นไปไม่ได้ใช่มั้ย? ถ้าฉันที่ผ่านมาเป็นโมฆะ ไม่มีอะไรที่มี ฉันอาจจะดีแค่ สุ่มสี่สุ่มห้าพูดกลับเท็จ ถ้าคุณให้ฉันไม่มีอะไรผมก็ไม่สามารถ ค้นหาหมายเลขเอ็นใด ๆ ดังนั้นสิ่งที่คนอื่นอาจจะฉัน การตรวจสอบตอนนี้หรือไม่ ฉันจะบอกว่าดีอื่นถ้า N คือ น้อยกว่าสิ่งที่อยู่ในโหนดต้นไม้ ที่ฉันได้รับการส่งมอบมูลค่าที่ยังไม่มี ในคำอื่น ๆ ถ้าจำนวนฉัน มองหา N, น้อยกว่าโหนด ที่ผมกำลังมองหาที่ และโหนดฉันกำลังมองหา ที่เรียกว่าต้นไม้ และจำได้จากตัวอย่างก่อนหน้านี้ ที่จะได้รับค่าในตัวชี้ ผมใช้สัญกรณ์ลูกศร ดังนั้นหากยังไม่มีน้อยกว่าลูกศรต้นไม้ N, ฉันต้องการที่จะไปแนวคิดซ้าย ฉันจะเหลือการค้นหาด่วนอย่างไร ต้องมีความชัดเจนว่านี่คือ ภาพในคำถาม และฉันได้รับการส่งผ่านที่สูงสุด ลูกศรที่ชี้ลง นั่นเป็นตัวชี้ต้นไม้ของฉัน ผมชี้ไปที่รากของต้นไม้ และฉันกำลังมองพูดสำหรับ หมายเลข 44, พล 44 น้อยกว่าหรือ มากกว่า 55 เห็นได้ชัด? ดังนั้นจึงเป็นที่น้อยกว่า และเพื่อให้สภาพนี้ถ้านำไปใช้ ดังนั้นแนวคิดสิ่งที่ฉันต้องการ ค้นหาต่อไปถ้าฉันกำลังมองหา 44? ใช่? 

ว่าผมต้องการที่จะ ค้นหาเด็กด้านซ้าย หรือซ้ายย่อยต้นไม้ของภาพนี้ และในความเป็นจริงให้ฉันผ่าน ภาพที่ลงที่นี่ เพียงช่วงเวลาตั้งแต่ ฉันไม่สามารถเกานี้ออก ถ้าฉันเริ่มต้นที่นี่ที่ 55 และ ฉันรู้ว่าค่า 44 ฉันกำลังมองหาคือการ ด้านซ้ายเป็นชนิด เช่นฉีกสมุดโทรศัพท์ใน ครึ่งหนึ่งหรือฉีกขาดต้นไม้ในช่วงครึ่งปี ฉันไม่ต้องดูแลเกี่ยวกับ ทั้งหมดนี้ครึ่งหนึ่งของต้นไม้ และยังอยากรู้อยากเห็นในแง่ของ โครงสร้างสิ่งนี้มากกว่าที่นี่ที่ เริ่มต้นด้วย 33 นั้นเอง เป็นต้นไม้ค้นหาแบบทวิภาค ผมบอกว่าคำว่า recursive ก่อนเพราะ แท้จริงนี้คือโครงสร้างข้อมูลที่ โดยความหมายคือ recursive คุณอาจมีต้นไม้ที่นี้ ใหญ่ แต่ทุกคนของเด็ก แสดงให้เห็นถึงต้นไม้ที่มีขนาดเล็กเพียงเล็ก ๆ น้อย ๆ แทนของมันถูกคุณปู่ หรือยายตอนนี้ก็เพียงแค่แม่ or-- ฉันไม่สามารถ say-- แม่ไม่ได้ หรือพ่อที่จะแปลก แต่เด็กทั้งสองมี จะเป็นเหมือนพี่ชายและน้อง รุ่นใหม่ของต้นไม้ครอบครัว แต่การก่อสร้างก็เป็นความคิดเดียวกัน และปรากฎฉันมีฟังก์ชั่น ที่ฉันสามารถค้นหาการค้นหาแบบไบนารี ต้นไม้ มันถูกเรียกว่าการค้นหา ฉันจะค้นหาไม่มีลูกศรซ้ายต้นไม้ อื่นถ้ายังไม่มีข้อความที่มีค่ามากกว่าค่า ว่าฉันในขณะนี้ที่ 55 ในเรื่องช่วงเวลาที่ผ่านมา ฉันมีฟังก์ชั่นที่เรียกว่า ค้นหาที่ฉันสามารถทำได้เพียงแค่ ไม่มีข้อความผ่านนี้และค้นหาซ้ำ ย่อยต้นไม้และการกลับมาเพียง สิ่งที่ว่าคำตอบ อื่น ๆ ที่ฉันได้มีกรณีฐานบางส่วนสุดท้ายที่นี่ 

กรณีสุดท้ายคืออะไร? ต้นไม้เป็นทั้ง null ค่าฉันทั้งมองหาคือ น้อยกว่าหรือมากกว่า หรือเท่ากับมัน และผมสามารถพูดได้เท่ากัน เท่ากัน แต่ก็มีเหตุผล เทียบเท่ากับคำพูดว่าคนอื่นที่นี่ ดังนั้นความจริงเป็นวิธีที่ผมพบสิ่งที่ เพื่อหวังว่านี่คือ ตัวอย่างเช่นแม้จะน่าสนใจมากขึ้น มากกว่าฟังก์ชั่นซิกโง่ เราได้บรรยายไม่กี่หลัง ที่มันเป็นเพียงเป็นเรื่องง่ายที่จะใช้ห่วง การนับตัวเลขทั้งหมดจากหนึ่ง เอ็นที่นี่มีโครงสร้างข้อมูล ที่ตัวเองเป็นซ้ำ กำหนดและวาดซ้ำตอนนี้เรา มีความสามารถในการแสดงตัวเอง ในรหัสที่ตัวเองเป็น recursive ดังนั้นนี่เป็นรหัสเดียวกันแน่นอนที่นี่ 

ดังนั้นสิ่งที่เป็นปัญหาอื่น ๆ ที่เราสามารถแก้ปัญหา? ดังนั้นขั้นตอนที่รวดเร็วอยู่ห่างจาก ต้นไม้เพื่อรอสักครู่ นี่คือการพูด, ธงเยอรมัน และมีอย่างชัดเจน รูปแบบการตั้งค่าสถานะนี้ และมีจำนวนมาก ธงในโลกที่ เป็นที่เรียบง่ายเช่นนี้ในแง่ สีและรูปแบบของพวกเขา แต่สมมติว่านี้จะถูกเก็บไว้เป็น .GIF หรือ JPEG หรือบิตแมปหรือปิงที่ รูปแบบไฟล์กราฟิกใด ๆ ที่คุณคุ้นเคย บางอย่างที่เรา เล่นกับใน PSET4 นี้ดูเหมือนจะไม่คุ้มค่าที่จะเก็บ พิกเซลสีดำพิกเซลสีดำพิกเซลสีดำ จุดจุดจุดทั้งกลุ่ม พิกเซลสีดำสำหรับ scanline แรก หรือแถวแล้วทั้งกลุ่ม เดียวกันแล้วทั้งกลุ่ม ของเดียวกันแล้ว ทั้งกลุ่มของพิกเซลสีแดง พิกเซลสีแดง, สีพิกเซลสีแดงแล้วทั้งหมด พวงของพิกเซลสีเหลือง, สีเหลือง, ใช่มั้ย? 

มีการขาดประสิทธิภาพเช่นที่นี่ คุณจะทำอย่างไรสังหรณ์ใจ บีบอัดธงเยอรมัน ถ้าการดำเนินการนั้นเป็นไฟล์? เช่นเดียวกับข้อมูลที่เราไม่สามารถ รำคาญการจัดเก็บบนดิสก์ในการสั่งซื้อ เพื่อลดขนาดไฟล์ของเราจากที่ชอบ เมกะไบต์เพื่อกิโลไบต์ซึ่งเป็นสิ่งที่ เล็ก? ประเด็นอยู่ซ้ำซ้อน ที่นี่จะเป็นที่ชัดเจน? สิ่งที่คุณจะทำอย่างไร ใช่? ที่แน่นอน ทำไมไม่จำมากกว่า สีของทุกพิกเซลยี้ เช่นเดียวกับที่คุณทำใน PSET4 กับรูปแบบไฟล์บิตแมป ทำไมคุณไม่เพียงแค่เป็นตัวแทนของ คอลัมน์ซ้ายสุดพิกเซลเช่น พวงของพิกเซลสีดำพวง ของสีแดง, และพวงของสีเหลือง แล้วก็อย่างใดเข้ารหัส ความคิดของการทำซ้ำนี้ 100 ครั้ง หรือทำซ้ำนี้ 1,000 ครั้ง? ที่ไหน 100 หรือ 1,000 เป็น เพียงจำนวนเต็มเพื่อให้คุณ จะได้รับไปมีเพียงหมายเลขเดียว แทนการร้อยหรือหลายพัน พิกเซลที่เพิ่มขึ้นของ และแน่นอนที่ว่าเรา สามารถบีบอัดธงเยอรมัน และ ตอนนี้สิ่งที่เกี่ยวกับธงฝรั่งเศส? และน้อยจัดเรียงของบางอย่าง ออกกำลังกายทางจิตซึ่งธง สามารถบีบอัดมากขึ้นบนดิสก์? ธงเยอรมันหรือฝรั่งเศส ธงถ้าเราใช้วิธีการที่? ธงเยอรมันเพราะมี ความผิดพลาดในแนวนอนมากขึ้น และโดยการออกแบบกราฟิกหลายไฟล์ รูปแบบที่ไม่แน่นอนทำงานเป็นเส้นสแกน แนวนอน พวกเขาสามารถทำงานได้ แนวตั้งเป็นมนุษย์เพียง ตัดสินใจปีมาแล้วที่เราจะ มักคิดว่าของแถวสิ่ง โดยแถวแทนคอลัมน์คอลัมน์ ดังนั้นแน่นอนถ้าคุณมี ไปดูที่ไฟล์ ขนาดของธงเยอรมันและฝรั่งเศส ธงตราบใดที่ความละเอียด เดียวกันความกว้างเท่ากัน และความสูงหนึ่งนี้ ที่นี่เป็นไปได้ที่ใหญ่กว่าเพราะคุณ ต้องทำซ้ำตัวเองสามครั้ง คุณจะต้องระบุสีฟ้าซ้ำ ด้วยตัวคุณเอง, สีขาว, ซ้ำตัวเอง, สีแดง, ซ้ำตัวเอง คุณก็ไม่สามารถไปทั้งหมด วิธีการที่เหมาะสม และเป็นกันที่จะทำให้ ล้างอัด เป็นทุกที่ถ้าเหล่านี้เป็น เฟรมที่สี่จาก video-- คุณ อาจจะจำได้ว่าภาพยนตร์ หรือวิดีโอโดยทั่วไป เช่น 29 หรือ 30 เฟรมต่อวินาที มันเหมือนพลิกหนังสือเล็ก ๆ น้อย ๆ ที่คุณ เพียงแค่เห็นภาพภาพภาพภาพ ภาพเร็วสุดเพียงเพื่อให้ดูเหมือนว่า นักแสดงบนหน้าจอจะย้าย นี่เป็นแมลงภู่ในเป็น ด้านบนของช่อดอกไม้ และแม้ว่ามันอาจจะเป็นชนิดของ ยากที่จะเห็นได้อย่างรวดเร็วก่อน สิ่งเดียวที่จะย้ายไปอยู่ หนังเรื่องนี้เป็นผึ้ง 

อะไรคือสิ่งที่เกี่ยวกับการเก็บใบ้ บีบอัดวิดีโอ? เป็นชนิดของขยะในการจัดเก็บวิดีโอ เป็นสี่ภาพที่เหมือนกันเกือบ แตกต่างกันเฉพาะเท่าที่ผึ​​้งเป็น คุณสามารถโยนไปมากที่สุด ของข้อมูลที่ และจำไว้เท่านั้นเช่น เฟรมแรกและกรอบที่ผ่านมา เฟรมที่สำคัญถ้าคุณได้ เคยได้ยินคำว่า และเพียงแค่เก็บใน กลางที่ผึ​​้งเป็น และคุณจะได้ไม่ต้อง เก็บทุกสีชมพู และสีฟ้าและ ค่าสีเขียวเช่นกัน ดังนั้นนี้เป็นเพียงบอกว่า การบีบอัดมีอยู่ทั่วไป มันเป็นเทคนิคที่เรามักจะใช้ หรือใช้สำหรับการรับวันนี้ 

แต่คุณจะบีบอัดข้อความ? คุณไปเกี่ยวกับการบีบอัดข้อความได้อย่างไร ดีของแต่ละตัวละครใน ascii เป็นหนึ่งไบต์หรือแปดบิต และนั่นคือชนิดของใบ้ใช่มั้ย? เพราะคุณอาจจะเป็นชนิด A และ E และ I และ O และ U มาก บ่อยกว่าเช่น W หรือ Q หรือซี ขึ้นอยู่กับภาษาที่ คุณกำลังเขียนอย่างแน่นอน ดังนั้นทำไมเราใช้ แปดบิตสำหรับจดหมายทุก รวมทั้งน้อย ตัวอักษรที่นิยมใช่มั้ย? ทำไมไม่ใช้บิตน้อยลงสำหรับ ตัวอักษรที่นิยมสุด เช่น E, สิ่งที่คุณคิดว่า ครั้งแรกในวงล้อแห่งโชคลาภ และใช้บิตม​​ากขึ้นสำหรับ ตัวอักษรที่ได้รับความนิยมน้อยลงหรือไม่ ทำไม? เพราะเรากำลังจะ ใช้พวกเขาไม่บ่อย 

ดีก็ปรากฎว่ามีมี ความพยายามที่รับทำจะทำเช่นนี้ และถ้าคุณจำได้จากเกรด โรงเรียนหรือโรงเรียนมัธยมรหัสมอร์ส รหัสมอร์สมีจุด และรอยขีดข่วนที่สามารถ ส่งผ่านไปตามสายเป็น เสียงหรือสัญญาณของการจัดเรียงบาง แต่รหัสมอร์สเป็นที่สะอาดสุด เป็นชนิดของระบบดาวคู่ใน ว่าคุณมีจุดหรือรอยขีดข่วน แต่ถ้าคุณเห็นเช่นจุดสองจุด หรือถ้าคุณคิดว่ากลับไปดำเนินการ ที่ไปเช่นเสียงเตือนเสียงเตือนเสียงเตือน เสียงเตือนกดปุ่มทริกเกอร์เล็ก ๆ น้อย ๆ ที่ส่งสัญญาณ ถ้าคุณผู้รับได้รับสอง จุดสิ่งที่คุณได้รับข้อความได้? สมบูรณ์โดยพลการ 

ผม? ผม? หรือสิ่งที่ about-- หรือ I? บางทีมันอาจจะเป็นเพียงแค่สองขวาอี จึงมีปัญหานี้ ของ decodability กับมอร์ส รหัสโดยเว้นแต่ คนที่ส่งข้อความ จริงหยุดเพื่อให้คุณสามารถเรียงลำดับของ เห็นหรือได้ยินช่องว่างระหว่างตัวอักษร มันไม่เพียงพอเพียงเพื่อ ส่งกระแสของศูนย์และคน, หรือจุดและขีดกลาง เพราะมีความคลุมเครือ E เป็นจุดเดียวดังนั้นหากคุณ เห็นสองจุดหรือได้ยินสองจุด บางทีมันอาจจะสอง E หรือบางทีมันอาจจะเป็นหนึ่งในครั้งที่หนึ่ง ดังนั้นเราจึงจำเป็นต้องมีระบบที่เป็น เล็ก ๆ น้อย ๆ ที่ฉลาดมากขึ้นกว่าที่ ดังนั้นผู้ชายที่ชื่อปี Huffman ที่ผ่านมาขึ้นมาตรงนี้ ดังนั้นเราจึงกำลังจะ ที่จะใช้อย่างรวดเร็ว ที่วิธีการที่ต้นไม้ใกล้ชิดกับเรื่องนี้ สมมติว่านี่คือบางส่วน ข้อความโง่คุณต้องการที่จะส่ง ประกอบด้วยเพียง A, B, C ของ D'และ E ของ แต่มีจำนวนมากที่มีความซ้ำซ้อนที่นี่ มันไม่ได้หมายความว่าจะเป็นภาษาอังกฤษ มันไม่ได้เข้ารหัส มันเป็นเพียงข้อความโง่ มีจำนวนมากของการทำซ้ำ ดังนั้นถ้าคุณจริงนับออกทั้งหมด เอบีซีของ D's และ E ของที่นี่ ความถี่ 20% ของตัวอักษรที่ เอเอส 45% ของตัวอักษร เป็น E และสามความถี่อื่น ๆ เรานับไปอยู่ที่นั่นด้วยตนเอง และเพียงแค่ไม่คณิตศาสตร์ 

ดังนั้นมันกลับกลายเป็นว่า Huffman, เวลาที่ผ่านมาบางส่วน ตระหนักว่าคุณรู้ว่า สิ่งที่ถ้าผมเริ่มต้นสร้าง ต้นไม้หรือป่าไม้ของต้นไม้ถ้าคุณจะ ดังต่อไปนี้ฉันจะทำต่อไปนี้ ฉันจะให้โหนดแต่ละ ของตัวอักษรที่ฉันดูแลเกี่ยวกับ และฉันจะเก็บ ภายในของโหนดที่ ความถี่เป็นจุดลอย ค่าหรือคุณอาจจะใช้มันยังไม่มีมากเกินไป แต่เราก็จะใช้ลอยที่นี่ และอัลกอริทึมที่ เขาเสนอคือการที่คุณ ใช้ป่าโหนดเดียวนี้ ต้นไม้เพื่อต้นไม้สั้นสุด และคุณจะเริ่มต้นการเชื่อมต่อพวกเขาด้วย กลุ่มใหม่ผู้ปกครองใหม่ถ้าคุณจะ และคุณทำเช่นนี้โดยการเลือก สองความถี่ที่เล็กที่สุดในช่วงเวลาที่ ดังนั้นผมจึงเอา 10% และ 10% ฉันจะสร้างโหนดใหม่ และที่ผมเรียกว่าโหนดใหม่ 20% 

ซึ่งสองโหนด I รวมต่อไปหรือไม่ มันเป็นเรื่องเล็ก ๆ น้อย ๆ ที่ไม่ชัดเจน จึงมีบางกรณีมุม พิจารณา แต่เพื่อให้สิ่งที่สวย ฉันจะเลือก 20% - ตอนนี้ผมไม่สนใจเด็ก ฉันจะเลือก 20% และ 15% และวาดสองขอบใหม่ และตอนที่สองโหนด ฉันมีเหตุผลรวม? ไม่สนใจเด็กทุกคนทุก หลานเพียงแค่มองไปที่ราก ตอนนี้ ซึ่งสองโหนดฉันจะผูกกัน? จุดที่สองและ 0.35 เพื่อให้ฉันวาดสองขอบใหม่ และจากนั้นผมได้มีเพียงคนเดียวที่เหลือ ดังนั้นนี่คือต้นไม้ และจะได้รับการวาดจงใจ ที่จะดูชนิดของสวย แต่สังเกตเห็นว่ามีขอบ ยังได้รับการติดป้ายชื่อศูนย์และหนึ่ง ดังนั้นสิ่งที่ขอบด้านซ้ายเป็นศูนย์ โดยพลการ แต่อย่างต่อเนื่อง ทั้งหมดขอบด้านขวาจะเป็นคน 

และเพื่อให้สิ่งที่ฮอฟแมนที่นำเสนอมี ถ้าคุณต้องการที่จะเป็นตัวแทนของ B, มากกว่าแทนจำนวน 66 เป็น Ascii ซึ่งเป็นแปดบิตทั้งหมด คุณรู้ว่าสิ่งที่จัดเก็บเพียง รูปแบบศูนย์ศูนย์ศูนย์ ศูนย์เนื่องจากว่าเป็นเส้นทาง จากต้นไม้ของฉันนายต้นไม้ Huffman ของ ใบจากราก ถ้าคุณต้องการในการจัดเก็บ E โดยคมชัดไม่ ส่งแปดบิตที่เป็นตัวแทนของอี แต่สิ่งที่ส่งรูปแบบของบิต? หนึ่ง และสิ่งที่ดีเกี่ยวกับเรื่องนี้คือ ที่ E เป็นตัวอักษรที่นิยมมากที่สุด และคุณกำลังใช้ รหัสที่สั้นที่สุดสำหรับมัน ถัดไปที่นิยมมากที่สุด ตัวอักษรที่ดูเหมือนว่ามัน เป็นเอและเพื่อให้วิธีการหลายบิต เขาเสนอใช้สำหรับที่? ศูนย์หนึ่ง 

และเพราะการดำเนินการ เป็นต้นไม้ต้นนี้สำหรับตอนนี้ กำหนดให้ฉันมี ความคลุมเครือในขณะที่มอร์สไม่มี รหัสเพราะทั้งหมดของ ตัวอักษรที่คุณดูแลเกี่ยวกับ อยู่ที่ปลายขอบเหล่านี้ เพื่อให้เป็นเพียงหนึ่ง แอพลิเคชันของต้นไม้ is-- นี้และฉันจะโบก มือของฉันที่นี้วิธีการที่คุณ อาจดำเนินการนี​​้เป็นโครงสร้าง C เราก็ต้องรวม สัญลักษณ์เช่นถ่าน, และความถี่ในด้านซ้ายและขวา แต่ให้ดูที่สอง ตัวอย่างสุดท้ายที่คุณจะ ได้รับค่อนข้างคุ้นเคยกับหลัง ศูนย์ในการตอบคำถามปัญหาตั้งห้า 

จึงมีโครงสร้างข้อมูล ที่รู้จักกันเป็นตารางแฮช และตารางแฮชเป็นชนิดของ เย็นในการที่จะมีถัง และสมมติว่ามีสี่ถัง นี่แค่สี่ช่องว่าง นี่คือของการ์ด, และนี่คือ สโมสร, จอบ, สโมสร, เพชร, สโมสร เพชรสโมสร, เพชร, clubs-- ดังนั้นนี้เป็นแบบสุ่ม หัวใจ hearts-- ดังนั้นฉัน bucketizing ทั้งหมดของปัจจัยการผลิตที่นี่ และตารางแฮชความต้องการ จะมองไปที่การป้อนข้อมูลของคุณ แล้ววางไว้ในบางอย่าง วางอยู่บนพื้นฐานของสิ่งที่คุณเห็น มันเป็นขั้นตอนวิธี และผมใช้ซุปเปอร์ อัลกอริทึมภาพอย่างง่าย ส่วนที่ยากที่สุดซึ่งเป็น จดจำสิ่งที่เป็นภาพ แล้วมีสี่สิ่งที่รวม 

ตอนนี้กองกำลังที่เพิ่มขึ้นซึ่ง เป็นสิ่งที่ออกแบบโดยเจตนาที่นี่ แต่อะไรที่ฉันจะทำอย่างไร ดังนั้นจริง ๆ แล้วนี่เรามี พวงของหนังสือสอบโรงเรียนเก่า สมมติว่าพวงของ ชื่อนักเรียนที่นี่ นี่เป็นตารางแฮชที่ใหญ่กว่าคือ แทนที่จะเป็นสี่ถัง ฉันได้สมมติว่า 26 และเราไม่ได้ต้องการที่จะไปยืม 26 สิ่งที่มาจากข้างนอก [? Annenberg?] ดังนั้น นี่คือห้าที่เป็นตัวแทนของ ผ่านซีและถ้าฉัน เห็นนักเรียนที่มีชื่อขึ้นต้นด้วย A, ฉันจะใส่การตอบคำถามของเขาหรือเธอมี ถ้ามีคนเริ่มต้นด้วยซีที่นั่น A-- จริงไม่ต้องการที่จะทำเช่นนั้น B ไปกว่าที่นี่ ดังนั้นผมจึงได้มี A และ B และ C และ ตอนนี้ที่นี่เป็นนักเรียนอีก แต่ถ้าตารางแฮชนี้ ดำเนินการกับอาร์เรย์ ฉันชนิดของเมา ที่จุดนี้ใช่มั้ย? ชนิดของฉันต้องการที่จะนำเรื่องนี้อยู่ที่ไหนสักแห่ง 

ดังนั้นหนึ่งวิธีที่ฉันสามารถแก้ปัญหานี้คือทั้งหมด ที่ถูกต้องคือไม่ว่างไม่ว่าง B, C ไม่ว่าง ฉันจะทำให้เขาอยู่ในที่ดีดังนั้น ครั้งแรกที่ผมสามารถเข้าถึงได้ทันทีแบบสุ่ม แต่ละถังสำหรับนักเรียน แต่ตอนนี้มันเป็นชนิดของเงินทอง ลงไปในเชิงเส้นบางสิ่งบางอย่าง เพราะถ้าผมต้องการที่จะค้นหาคน มีชื่อขึ้นต้นด้วยผมตรวจสอบที่นี่ แต่ถ้านี้ไม่ได้เป็น นักศึกษาที่ฉันกำลังมองหา ชนิดของฉันจะต้องเริ่มต้นการตรวจสอบ ถังเพราะสิ่งที่ผมทำ คือการจัดเรียงของเส้นตรง ตรวจสอบโครงสร้างข้อมูล วิธีที่โง่บอกว่าเพียงแค่มอง สำหรับการเปิดใช้ได้แรก และใส่เป็นแผน B, เพื่อที่จะพูด หรือวางแผนที่ดีในกรณีนี้ค่า ในสถานที่ที่แทน นี่เป็นเพียงเพื่อที่ว่าถ้าคุณได้ มี 2​​6 สถานที่และนักเรียนไม่มี Q กับชื่อหรือ Z หรือสิ่งที่ต้องการ ว่าอย่างน้อยคุณใช้พื้นที่ 

แต่เราได้เห็นแล้ว โซลูชั่นที่ชาญฉลาดที่นี่ใช่มั้ย? คุณจะทำอะไรแทน ถ้าคุณมีการปะทะกันหรือไม่? ถ้าคนสองคนที่มี ชื่อที่สิ่งที่จะ ได้รับอย่างชาญฉลาดหรือมากกว่า วิธีการแก้ปัญหาที่ใช้งานง่ายกว่าเพียงแค่ วางที่ดีควรจะเป็น? ทำไมฉันจึงไม่เพียงแค่ไป นอก [? Annenberg?] เช่น malloc โหนดอื่นวางไว้ ที่นี่แล้วใส่ว่านักเรียนที่นี่ เพื่อที่ฉันเป็นหลักมี ชนิดของอาร์เรย์ หรืออาจจะหรูหรามากขึ้นตามที่เรา เริ่มที่จะเห็นรายการที่เชื่อมโยง 

และเพื่อให้ตารางแฮชเป็นโครงสร้าง ที่จะมีลักษณะเหมือนเพียงแค่นี้ แต่ชาญฉลาดคุณสิ่งที่เรียกว่า ผูกมัดที่แยกจากกันโดยตารางแฮช ค่อนข้างง่ายเป็นอาร์เรย์แต่ละ มีองค์ประกอบไม่ได้เป็นตัวเลข ตัวเองเป็นรายการที่เชื่อมโยง เพื่อที่คุณจะได้รับการเข้าถึงเร็วสุด การตัดสินใจที่จะสับค่าของคุณไป เหมือนตัวอย่างบัตร ฉันทำตัดสินใจที่รวดเร็วสุด หัวใจที่นี่เพชรที่นี่ เดียวกันที่นี่, A ไปที่นี่ D ที่นี่, B ที่นี่ ดังนั้นเร็วสุดดูอัพและถ้า คุณเกิดขึ้นที่จะทำงานเป็นกรณี ที่คุณได้มีการชนกันของทั้งสอง คนที่มีชื่อเดียวกันดีแล้ว คุณเพียงแค่เริ่มต้นการเชื่อมโยงเข้าด้วยกัน และบางทีคุณอาจให้พวกเขาเรียง ตัวอักษรอาจจะคุณทำไม่ได้ แต่อย่างน้อยตอนนี้เรามีชีวิตชีวา ดังนั้นในแง่หนึ่งเรามีเร็วสุด เวลาคงที่และชนิดของเส้นเวลา ที่เกี่ยวข้องกับการเชื่อมโยงถ้ารายการเหล่านี้ เริ่มต้นที่จะได้รับเป็นเวลานาน ๆ หน่อย ๆ 

ดังนั้นชนิดของโง่นี้ ปีที่ผ่านมาเป็นเรื่องตลก geeky ที่ CS50 สับธนบุรี, เมื่อนักเรียนเช็คอิน บาง TF หรือ CA ทุกปี คิดว่ามันเป็นเรื่องตลกที่จะนำขึ้น เข้าสู่ระบบเช่นนี้ซึ่งก็แค่ หมายความว่าชื่อของคุณเริ่มต้นด้วย A, ไปทางนี้ หากชื่อของคุณเริ่มต้น กับ B ไป this-- ตกลง มันตลกหลังจากนั้นอาจอยู่ในภาคการศึกษา แต่มีผู้อื่น วิธีการทำเช่นนี้มากเกินไป กลับมาที่ 

เพื่อให้มีโครงสร้างนี้ และนี่คือครั้งสุดท้ายของเรา โครงสร้างสำหรับวันนี้ ซึ่งเป็นสิ่งที่เรียกว่า Trie T-R-I-E ซึ่งด้วยเหตุผลบางอย่างที่เป็นระยะสั้น สำหรับการเรียก แต่ก็เรียกว่า Trie ดังนั้น Trie เป็นที่น่าสนใจอีก รวมกันของจำนวนมากของความคิดเหล่านี้ มันเป็นต้นไม้ที่เราเคยเห็นมาก่อน มันไม่ได้เป็นต้นไม้ค้นหาแบบทวิภาค มันเป็นต้นไม้ที่มีจำนวนของเด็กที่ใด ๆ แต่แต่ละของเด็กใน Trie ที่ เป็นอาร์เรย์ อาร์เรย์ของขนาดบอกว่าอาจจะ 26 หรือ 27 ถ้าคุณต้องการที่จะสนับสนุนชื่อยัติภังค์ หรือ apostrophes ในชื่อของผู้คน 

และเพื่อให้เป็นโครงสร้างข้อมูล และถ้าคุณมองจากด้านบน ไปที่ด้านล่างเช่นถ้าคุณ มองไปที่ด้านบนมีโหนด, M, คือ ชี้ไปที่สิ่งที่ซ้ายสุดมี ซึ่งจะแล้ว A, X, W, E, L, แอลนี่คือ เพียงแค่โครงสร้างข้อมูลที่พล มีการจัดเก็บชื่อของผู้คน และแมกซ์เวลจะถูกเก็บไว้โดยเพียงแค่ต่อไปนี้ เส้นทางของอาร์เรย์อาร์เรย์อาร์เรย์ แต่สิ่งที่น่าทึ่งเกี่ยวกับ Trie เป็น ว่าในขณะที่รายการที่เชื่อมโยงและแม้กระทั่ง อาร์เรย์ดีที่สุดที่เราเคยเคยเป็น เส้นเวลาหรือเวลาลอการิทึมมอง คนที่ขึ้น ในโครงสร้างข้อมูลของ Trie ถ้า โครงสร้างข้อมูลของฉันมีชื่ออยู่ในนั้น และฉันกำลังมองหาแมกซ์เวลผม จะไปหาเขาสวยได้อย่างรวดเร็ว ฉันเพียงแค่มองหา M-A-X-W-E-L-L หาก โครงสร้างข้อมูลนี้ตรงกันข้าม ถ้า N เป็นล้านถ้ามี ล้านชื่อในโครงสร้างข้อมูลนี้ แมกซ์เวลยังคงไปได้ ค้นพบหลังจากนั้นเพียง M-A-X-W-E-L-L ขั้นตอน และ David-- D-A-V-I-D ขั้นตอน ในคำอื่น ๆ โดยการสร้าง โครงสร้างข้อมูลที่ มีทั้งหมดของอาร์เรย์เหล่านี้ทั้งหมดที่ ตัวเองสนับสนุนการเข้าถึงแบบสุ่ม ฉันจะเริ่มมองขึ้นของผู้คน ชื่อที่ใช้ระยะเวลาที่เป็น ไม่ได้สัดส่วนกับจำนวน ของสิ่งที่อยู่ในโครงสร้างข้อมูล เหมือนล้านชื่อที่มีอยู่ ปริมาณของเวลาที่ใช้ผมที่จะหา M-A-X-W-E-L-L ในโครงสร้างข้อมูลนี้ สัดส่วนไม่ให้ ขนาดของโครงสร้างข้อมูล แต่ความยาวของชื่อ และแนบเนียน ชื่อที่เรากำลังมองหา ไม่เคยไปจะบ้านาน อาจจะมีคนมี 10 ตัวอักษร ชื่อ 20 ชื่อตัวละคร ก็แน่นอนแน่นอนใช่มั้ย? มีมนุษย์บนโลกเป็นใคร มีชื่อที่เป็นไปได้ที่ยาวที่สุด แต่ชื่อที่เป็นค่าคงที่ ระยะเวลาค่าใช่มั้ย? มันไม่ได้แตกต่างกันในความรู้สึกใด ๆ ดังนั้นในวิธีนี้เราได้ ประสบความสำเร็จในโครงสร้างข้อมูล ที่มีเวลาคงมองขึ้น แต่จะใช้จำนวนของขั้นตอน ขึ้นอยู่กับระยะเวลาของการป้อนข้อมูล แต่ไม่จำนวนของชื่อ ในโครงสร้างข้อมูล ดังนั้นหากเราเพิ่มจำนวนของชื่อ ปีถัดไปจากพันล้านถึงสองพันล้าน การค้นพบแมกซ์เวลจะใช้เวลา หมายเลขเดียวกันแน่นอนของเจ็ดขั้นตอน ไปหาเขา และเพื่อให้เราดูเหมือนจะได้ประสบความสำเร็จ จอกศักดิ์สิทธิ์ของเราในเวลาทำงาน 

ดังนั้นคู่ของประกาศอย่างรวดเร็ว ศูนย์ทดสอบกำลังจะมาถึง เพิ่มเติมเกี่ยวกับที่อยู่บนเว็บไซต์ของหลักสูตร ในช่วงสองสามวันถัดไป วันจันทร์ lecture-- มันเป็นวันหยุด ที่นี่ที่ฮาร์วาร์เมื่อวันจันทร์ที่ มันไม่ได้ใน New Haven, ดังนั้นเราจึงกำลังการเรียน การท่าเรือใหม่สำหรับการบรรยายในวันจันทร์ ทุกอย่างจะได้รับการถ่ายทำ และมีการถ่ายทอดสดตามปกติ แต่ขอให้จบในวันนี้ มี 30 คลิปที่สอง ที่เรียกว่า "คิดลึก" โดย Daven Farnham ซึ่ง เป็นแรงบันดาลใจปีที่ผ่านมาวันเสาร์ Night Live ของ "ความคิดลึก" โดยแจ็คที่มีประโยชน์ซึ่ง ขณะนี้ควรให้ความรู้สึก 

ฟิล์ม: และตอนนี้ "ลึก ความคิด "โดย Daven Farnham ตารางแฮช 

ลำโพงที่ 1: สิทธิทั้งหมดที่มันสำหรับตอนนี้ เราจะเห็นคุณในสัปดาห์ถัดไป 

DOUG: หากต้องการดูในการกระทำ ดังนั้นลองมาดูที่ว่าตอนนี้ ดังนั้นที่นี่เรามีอาร์เรย์ที่ไม่ได้เรียงลำดับ 

เอียน: ดั๊กคุณสามารถไปข้างหน้าและเริ่มต้นใหม่ นี้เพียงหนึ่งวินาทีโปรด สิทธิทั้งหมดกล้องจะกลิ้งดังนั้น การดำเนินการเมื่อใดก็ตามที่คุณพร้อมที่ดั๊ก, OK? DOUG สิทธิทั้งหมดดังนั้นสิ่งที่เรา มีที่นี่เป็นอาเรย์ไม่ได้เรียงลำดับ และฉันได้สีทุกองค์ประกอบ สีแดงเพื่อแสดงให้เห็นว่ามันเป็นในความเป็นจริง ไม่ได้เรียงลำดับ ดังนั้นจำได้ว่าสิ่งแรกที่เราทำ คือเราจัดเรียงครึ่งซ้ายของอาร์เรย์ จากนั้นเราก็เรียงลำดับที่ถูกต้อง ครึ่งหนึ่งของอาร์เรย์ และยาดา, ya-da, ya-ดา เราผสานเข้าด้วยกัน และเรามีอาร์เรย์ที่จัดเรียงอย่างสมบูรณ์ เพื่อให้เป็นวิธีการผสานการทำงานการจัดเรียง 

เอียน: โอ้โฮโอ้โฮโอ้โฮ ตัดตัดตัดตัด ดั๊กคุณไม่สามารถเพียงแค่ยาดา, ya-ดา ยาดาที่ทางของคุณผ่านการผสานการเรียงลำดับ 

ดั๊ก: ผมก็ไม่ได้ ทุกอย่างปกติดี. เราจะดีไป ขอเพียงให้กลิ้ง ยังไงก็ตาม, 

เอียน: คุณต้องอธิบาย มันมากขึ้นอย่างเต็มที่กว่า นั่นเป็นเพียงไม่เพียงพอ DOUG: เอียนเราทำไม่ได้ ต้องการที่จะกลับไปอย่างใดอย่างหนึ่ง ทุกอย่างปกติดี. ดังนั้นต่อไปถ้าเราดำเนินการกับ merge-- เอียนเรากำลังอยู่ในช่วงกลางของการถ่ายทำ 

เอียน: ฉันรู้ว่า และเราไม่สามารถเพียงแค่ยาดา, ya-ดา ยาดาผ่านกระบวนการทั้งหมด คุณจะต้องอธิบายว่า ทั้งสองฝ่ายได้รับรวมกัน 

ดั๊ก: แต่เราได้แล้ว อธิบายวิธีการทั้งสอง sides-- 

เอียน: คุณได้แสดงให้เห็นเพียงแค่ พวกเขาอาร์เรย์ผสาน ดั๊ก: พวกเขารู้ว่ากระบวนการ พวกเขากำลังดี เราได้ไปกว่านั้นสิบครั้ง 

เอียน: คุณเพียงแค่ข้ามที่ถูกต้องมากกว่านั้น เรากำลังจะกลับไปที่หนึ่งคุณ คุณไม่สามารถยาดา, ya-da มากกว่านั้น สิทธิทั้งหมดกลับไปที่หนึ่ง 

ดั๊ก: ผมต้องกลับไป ผ่านทุกภาพนิ่ง? พระเจ้าของฉัน. มันเหมือนเป็นครั้งที่หกเอียน ทุกอย่างปกติดี. 

เอียนสิทธิทั้งหมด คุณพร้อม? ที่ดี การดำเนินการ