[เล่นเพลง]
>> DAVID ลัน: นี่คือ CS50
และนี่คือทั้งสองเริ่มต้นและ end-- เช่น literally-- เกือบสิ้นสุด
หกสัปดาห์
>> ฉันคิดว่าฉันต้องการแบ่งปัน นิด ๆ หน่อย ๆ ของความเป็นจริงที่สนุก
ผมเคยดึงนี้เพิ่มขึ้นจาก ข้อมูลภาคการศึกษาที่ผ่านมาของการตั้งค่า
คุณอาจจะจำได้ว่าเราขอให้คุณในทุก รูปแบบการตั้งค่า P ​​ถ้าคุณได้ดูออนไลน์
หรือถ้าคุณได้เข้าร่วมในคน
และนี่คือข้อมูล
ดังนั้นวันนี้เป็นอย่างมากคาดเดาได้
แต่เราอยากจะใช้บิต เวลาอยู่กับคุณอย่างไรก็ตาม
ทุกคนต้องการที่จะคาดเดาว่าทำไมนี้ กราฟเป็นหยักให้ขึ้นลงขึ้นลง
เพื่อให้อย่างต่อเนื่อง?
สิ่งที่ทำในแต่ละของยอดเขา และต่ำสุดเป็นตัวแทน?
>> ผู้ชม: [ไม่ได้ยิน]
DAVID ลัน: แท้จริง
และอื่น ๆ ขันพระเจ้าห้าม เราถือเป็นหนึ่งบรรยายในวันศุกร์ที่
ที่จุดเริ่มต้นของภาคการศึกษาที่ นั่นคือสิ่งที่เราเห็นเกิดขึ้น
ดังนั้นวันนี้เรามีส่วนร่วมในบิต เพิ่มเติมเกี่ยวกับโครงสร้างข้อมูล
และให้คุณมากกว่าของแข็ง รูปแบบจิตสำหรับปัญหาที่ห้า
ซึ่งเป็นตอนนี้ออก
สะกดผิดนั้นเราจะ มือคุณแฟ้มข้อความบาง 100,000
บวกคำในภาษาอังกฤษและ คุณกำลังจะมี
ที่จะคิดออกว่าจะโหลดได้อย่างชาญฉลาด ในหน่วยความจำลงใน RAM โดยใช้ข้อมูลบางส่วน
โครงสร้างของตัวเลือกของคุณ
>> ตอนนี้หนึ่งในโครงสร้างของข้อมูลดังกล่าวได้ เป็น แต่อาจจะไม่ควรจะเป็น
รายการที่เชื่อมโยงง่ายอย่างเป็นธรรม ที่เรานำมาใช้เป็นครั้งสุดท้าย
และรายการที่เชื่อมโยงได้อย่างน้อย หนึ่งในข้อได้เปรียบกว่าอาร์เรย์
เป็นสิ่งหนึ่งประโยชน์จาก รายการที่เชื่อมโยงเนื้อหา?
>> ผู้ชม: แทรก
>> DAVID ลัน: แทรก
คุณหมายถึงอะไรโดยที่?
>> ผู้ชม: ทุกที่พร้อม รายการ [ไม่ได้ยิน]
>> DAVID ลัน: ดี
เพื่อให้คุณสามารถแทรกองค์ประกอบใดก็ตาม คุณต้องการอยู่ตรงกลางของรายการ
โดยไม่ต้องสับอะไร ซึ่งเราได้ข้อสรุปในการเรียงลำดับของเรา
การอภิปรายไม่ได้ จำเป็นต้องเป็นสิ่งที่ดี
เพราะมันต้องใช้เวลาที่จะย้ายจริง ทั้งหมดของมนุษย์ที่ทางซ้ายหรือขวา
และอื่น ๆ ที่มีรายชื่อที่เชื่อมโยงคุณสามารถ เพียงจัดสรรด้วย malloc, โหนดใหม่
แล้ว update คู่ของ pointers-- สองสามการดำเนินงาน max--
และเราสามารถที่จะเสียบใครบางคน ในที่ใดก็ได้ในรายการ
>> อะไรที่เป็นประโยชน์ เกี่ยวกับรายการที่เชื่อมโยงหรือไม่?
ใช่?
>> ผู้ชม: [ไม่ได้ยิน]
DAVID ลันเพอร์เฟ
สมบูรณ์
มันเป็นแบบไดนามิกจริงๆ
และการที่คุณไม่ได้กระทำ, ล่วงหน้าให้มีขนาดคงที่บางส่วน
ก้อนของหน่วยความจำเช่นเดียวกับที่คุณจะต้อง ที่จะมีอาร์เรย์คว่ำที่
คือการที่คุณสามารถจัดสรรโหนดเฉพาะ จึงมีความต้องการใช้เฉพาะพื้นที่มากที่สุดเท่าที่
ตามที่คุณต้องการจริง
ตรงกันข้ามกับอาร์เรย์คุณอาจ ตั้งใจจัดสรรน้อยเกินไป
และแล้วก็แค่ไป จะมีอาการปวดคอ
จัดสรรอาร์เรย์ใหญ่ใหม่คัดลอก ทุกอย่างผ่านไปฟรีอาร์เรย์เก่า
และจากนั้นย้ายเกี่ยวกับธุรกิจของคุณ
หรือแย่ลงคุณอาจจัดสรรวิธี หน่วยความจำมากกว่าที่คุณต้องการจริง
และเพื่อให้คุณกำลังจะมีมาก อาร์เรย์เบาบางประชากรจึงจะพูด
>> ดังนั้นรายการที่เชื่อมโยงเหล่านี้จะช่วยให้คุณ ข้อดีของพลวัตและความยืดหยุ่น
ด้วยการแทรกและการลบ
แต่แน่นอนจะต้องมีราคาที่จ่าย
ในความเป็นจริงหนึ่งในรูปแบบ สำรวจแบบทดสอบศูนย์
เป็นคู่ค้าไม่ชอบ เราได้เห็นป่านนี้
ดังนั้นสิ่งที่เป็นราคาที่จ่ายหรือ ข้อเสียของการเชื่อมโยงรายชื่อ?
ใช่
>> ผู้ชม: ไม่มีการเข้าถึงแบบสุ่ม
>> DAVID ลัน: ไม่เข้าถึงโดยสุ่ม
แต่ผู้ที่ใส่ใจ?
เข้าถึงโดยสุ่มไม่ได้เสียงที่น่าสนใจ
>> ผู้ชม: [ไม่ได้ยิน]
DAVID ลัน: แน่นอน
ถ้าคุณต้องการที่จะมี algorithm-- บางอย่าง
และแจ้งให้เราจริงเสนอ ค้นหาแบบไบนารีโดยเฉพาะอย่างยิ่งที่
เป็นหนึ่งที่เราได้ใช้ค่อนข้าง bit-- ถ้าคุณไม่ได้มีการเข้าถึงแบบสุ่ม
คุณไม่สามารถทำอย่างนั้นคณิตศาสตร์ที่เรียบง่าย ในการค้นหาเช่นองค์ประกอบกลาง
และกระโดดขวาไป
คุณแทนจะต้องเริ่มต้นในตอนแรก องค์ประกอบและเป็นเส้นตรงค้นหาจากซ้าย
ไปทางขวาถ้าคุณต้องการที่จะหา กลางหรือองค์ประกอบอื่น ๆ
>> ผู้ชม: มันอาจใช้เวลาหน่วยความจำเพิ่มเติม
>> DAVID ลัน: ใช้หน่วยความจำมากขึ้น
อยู่ที่ไหนที่เพิ่มเติม ค่าใช้จ่ายที่มาจากในหน่วยความจำ?
>> ผู้ชม: [ไม่ได้ยิน]
DAVID ลัน: แน่นอน
ในกรณีนี้ที่นี่เรามี รายการที่เชื่อมโยงสำหรับจำนวนเต็ม
และยังเรากำลังเสแสร้ง จำนวนหน่วยความจำ
ที่เราต้องการโดยยังเก็บคำแนะนำเหล่านี้
ตอนนี้น้อยกว่าการจัดการที่ใหญ่เป็น structs ของคุณได้รับขนาดใหญ่
และคุณไม่ได้จัดเก็บตัวเลข แต่ บางทีนักเรียนหรือวัตถุอื่น ๆ
แต่จุดแน่นอนยังคงอยู่
และดังนั้นจำนวนของการดำเนินงาน อยู่ในรายชื่อที่เชื่อมโยงถูกเรียกว่า
มี O ใหญ่ของ n-- เชิงเส้น
สิ่งที่ต้องการแทรกหรือการค้นหา หรือลบในกรณีองค์ประกอบ
จะเกิดขึ้นที่ปลายสุดของ รายการไม่ว่าจะเป็นการจัดเรียงหรือไม่
>> บางครั้งคุณอาจได้รับโชคดีและใน ขอบเขตเพื่อให้ลดลงในการดำเนินงานเหล่านี้
นอกจากนี้ยังอาจจะมีเวลาคงที่ถ้าคุณอยู่ มักจะมองที่องค์ประกอบแรก
เช่น
แต่ในท้ายที่สุดเราสัญญาว่า เพื่อให้บรรลุจอกศักดิ์สิทธิ์
โครงสร้างข้อมูลหรือ บางส่วนดังกล่าวประมาณ
โดยวิธีการของเวลาอย่างต่อเนื่อง
เราสามารถหาองค์ประกอบหรือเพิ่มองค์ประกอบ หรือเอาองค์ประกอบจากรายการ?
เราจะได้เห็นค่อนข้างเร็ว ๆ นี้
และปรากฎว่า กลไกที่เรากำลัง
จะเริ่มต้นที่จะใช้ในวันนี้ การใช้งานประจำปีใน P ตั้งห้า
เป็นจริงที่คุ้นเคยสวย
ยกตัวอย่างเช่นถ้าเป็นพวง หนังสือสอบแต่ละที่
มีนักเรียนเป็นครั้งแรก ชื่อและนามสกุลที่มัน
และผมเลือกพวกเขาขึ้นมาจาก ในตอนท้ายของการสอบ,
และพวกเขากำลังทั้งหมดสวย มากในลำดับแบบสุ่ม
และเราต้องการที่จะไปเกี่ยวกับการเรียงลำดับ การสอบเหล่านี้เพื่อให้คะแนนอีกครั้ง
มันเป็นเพียงมากขึ้นและ ได้เร็วขึ้นจะส่งพวกเขากลับออกมา
ให้กับนักเรียนตามลำดับตัวอักษร
สิ่งที่สัญชาตญาณของคุณจะ สำหรับกองการสอบเช่นนี้?
>> ดีถ้าคุณต้องการฉันคุณ อาจจะเห็นว่านี่เป็นเมตร
ดังนั้นฉันจะเรียงลำดับของการวางนี้ใน, ถ้าเป็นโต๊ะหรือพื้นของฉันที่ฉัน
ฉันแพร่กระจายสิ่งที่ แทนดูหรืออาเรย์ของฉันนะ
ฉันอาจจะใส่ทั้งหมดของ Ms ในนั้น
โอ้
นี่ A. ดังนั้นฉันอาจ ใส่เป็นมากกว่าที่นี่
โอ้
A. ที่นี่ฉันจะอื่น ที่จะนำว่ากว่าที่นี่
นี่ Z. เป็นนี่คือเอ็มอีกและดังนั้น ฉันอาจจะเริ่มต้นสร้างกองเช่นนี้
แล้วบางทีผมอาจจะไปในภายหลัง และการเรียงลำดับของ nitpicky-Ly มากการจัดเรียง
แต่ละกอง
แต่ประเด็นก็คือผมจะดู ที่ใส่ว่าฉันมือ
และฉันจะทำให้บางคำนวณ การตัดสินใจบนพื้นฐานของข้อมูลที่
ถ้ามันเริ่มต้นด้วยใส่ไว้ที่นั่น
ถ้ามันเริ่มต้นด้วย Z ใส่มันไป มีและทุกสิ่งในระหว่าง
>> ดังนั้นนี่คือเทคนิคที่เป็น ที่รู้จักกันทั่วไป hashing-- H-A-S-H--
ซึ่งโดยทั่วไปหมายถึงการเป็น การป้อนข้อมูลและการใช้ข้อมูลที่จะคำนวณ
ค่าทั่วไปจำนวนและที่ ตัวเลขดัชนีลงในการจัดเก็บข้อมูล
ภาชนะเช่นอาร์เรย์
ดังนั้นในคำอื่น ๆ ที่ผมอาจจะมี ฟังก์ชันแฮชที่ผมทำในหัวของฉัน
ว่าถ้าผมเห็นใครบางคนเป็น ชื่อที่เริ่มต้นด้วย,
ฉันกำลังจะไปที่แผนที่ ให้เป็นศูนย์ในหัวของฉัน
และถ้าฉันเห็นคนที่มี Z ฉัน จะ map ที่ 25 ในหัวของฉัน
แล้วใส่ลงใน กองส่วนใหญ่ที่ผ่านมา
>> ตอนนี้ถ้าคุณคิดเกี่ยวกับการไม่สมองของฉัน แต่โปรแกรม C หมายเลขสิ่งที่สามารถทำได้
คุณพึ่งพาเพื่อให้บรรลุผลที่เหมือนกันหรือไม่
ในคำอื่น ๆ ถ้าคุณ มีตัวอักษร ASCII,
วิธีการทำคุณกำหนด สิ่งที่ถังที่จะนำมันมีอะไรบ้าง?
คุณอาจไม่ต้องการที่จะ ใส่มันลงไปในถัง 65 ซึ่ง
จะเป็นเช่นนั่น ไม่มีเหตุผลที่ดี
ที่คุณต้องการที่จะนำ ในแง่ของค่า ASCII หรือไม่?
ที่คุณต้องการที่จะทำเพื่อ ASCII ของ มูลค่าให้เกิดขึ้นกับถังอย่างชาญฉลาด
ที่จะนำมันมีอะไรบ้าง?
>> ผู้ชม: ลบ A.
>> DAVID ลัน: ใช่
เพื่อลบหรือลบ เฉพาะ 65 ถ้ามัน
A. ทุนหรือ 98 ถ้า มันเป็นตัวพิมพ์เล็ก
และเพื่อที่จะช่วยให้เราสามารถมาก เพียงและมาก arithmetically,
ใส่อะไรลงไปในถังเช่นนั้น
ดังนั้นมันจะเปิดออกที่เราทำจริง นี้ได้ดีกับแบบทดสอบ
>> ดังนั้นคุณอาจจำคุณวงกลมของคุณ ชื่อการเรียนการสอนของเพื่อนบนหน้าปก
และชื่อของ TF ถูกจัด ลงในคอลัมน์เหล่านี้ตามลำดับตัวอักษร
ดีเชื่อหรือไม่ว่า เมื่อทั้งหมด 80 บวกของเรา
ได้ร่วมกันคืนอื่น ๆ ที่จะเกรด ขั้นตอนสุดท้ายในกระบวนการการจัดลำดับของเรา
คือการสับแบบทดสอบเป็นใหญ่ พื้นที่ของชั้นที่ [ไม่ได้ยิน]
และการวางแบบทดสอบของทุกคนออกมา ในตรงคำสั่งของ TF ของพวกเขา
ชื่อบนหน้าปกเพราะ แล้วมันง่ายมากสำหรับเรา
การค้นหาผ่านว่าการใช้เส้นตรง ค้นหาหรือชนิดของความฉลาดบาง
สำหรับ TF ไปหาเขาหรือ นักเรียนของเธอ 'แบบทดสอบ
>> ดังนั้นความคิดของ hashing นี้ ที่คุณจะเห็นคือ
มีประสิทธิภาพมากสวยจริง เป็นเรื่องธรรมดาและใช้งานง่ายมาก
เหมือนบางทีอาจจะแบ่งและ ชนะในสัปดาห์ที่ศูนย์
ฉันอย่างรวดเร็วไปข้างหน้าเพื่อ Hackathon สองสามปีที่ผ่านมา
นี่คือ Zamyla และคู่ของ นักเรียนอวยพรเจ้าหน้าที่อื่น ๆ
ขณะที่พวกเขาเดินเข้ามาใน
และเรามีทั้งกลุ่มของการพับ มีตารางที่มีแท็กชื่อ
และเรามีแท็กชื่อที่จัด ด้วยเช่นเป็นที่นั่น
และ Zs ที่นั่น
และเพื่อให้เป็นหนึ่งใน TFS อย่างชาญฉลาด เขียนนี้เป็นคำแนะนำ
สำหรับวันที่
และในสัปดาห์ที่ 12 ของภาคการศึกษานี้ ทั้งหมดทำให้ความรู้สึกที่สมบูรณ์แบบและทุกคน
รู้ว่าจะทำอย่างไร
แต่เมื่อใดที่คุณได้ เข้าคิวในทางเดียวกัน
คุณกำลังดำเนินการ ความคิดเดียวกับกัญชา
ดังนั้นขอให้เป็นระเบียบแบบแผนมันนิด ๆ หน่อย ๆ
นี่คืออาร์เรย์
มันดึงไปเป็นเพียงเล็กน้อย กว้างเพียงเพื่อให้เห็นภาพ, สายตา
ที่เราอาจจะวางสาย ในบางสิ่งบางอย่างเช่นนี้
และอาเรย์นี้ อย่างเห็นได้ชัดขนาดทั้งหมด 26
และสิ่งที่เรียกว่า ตารางพล
แต่นี่เป็นเพียงการกระทำของศิลปิน ของสิ่งที่ตารางแฮชอาจจะ
>> ดังนั้นตารางแฮชตอนนี้เป็นไปได้ เป็นระดับโครงสร้างข้อมูลที่สูงขึ้น
ในตอนท้ายของวัน เรากำลังจะเห็นว่าคุณ
สามารถใช้ตารางแฮชซึ่ง เป็นเหมือนเส้นเช็คอิน
ที่ Hackathon มากเช่นนี้ ตารางที่ใช้สำหรับการจัดเรียงหนังสือสอบ
แต่ตารางแฮชเป็น การเรียงลำดับของระดับสูงนี้
แนวความคิดที่จะใช้อาร์เรย์ ใต้ฝากระโปรงจะใช้มัน
หรืออาจใช้รายการความยาวหรือแม้กระทั่ง บางทีบางโครงสร้างข้อมูลอื่น ๆ
และตอนนี้ที่การ theme-- บางส่วนของส่วนผสมพื้นฐานเหล่านี้
เช่นอาร์เรย์และอาคารหลังนี้ ปิดกั้นตอนนี้ของรายการความยาว
และเห็นว่าอะไรที่เราสามารถสร้าง ด้านบนของคนเช่นส่วนผสม
เป็นสูตรที่ทำให้มากขึ้นและมากขึ้น ผลสุดท้ายที่น่าสนใจและมีประโยชน์
>> ดังนั้นด้วยตารางแฮช เราอาจจะใช้มัน
ในหน่วยความจำ pictorially เช่นนี้ แต่ ว่าอาจเป็นจริงจะเขียนขึ้นมา?
ดีอาจจะเป็นเพียงนี้
ถ้าความจุในตัวพิมพ์ใหญ่ทั้งหมดเป็นเพียง constant-- บางอย่างเช่น 26,
สำหรับ 26 ตัวอักษรของ alphabet-- ผมอาจจะเรียกตารางตัวแปรของฉัน
และฉันอาจจะอ้างว่าฉันจะ ใส่ดาวถ่านในนั้นหรือสตริง
ดังนั้นจึงเป็นเรื่องง่ายอย่างที่นี้ถ้าคุณ ต้องการที่จะใช้ตารางแฮช
และยังนี้เป็นจริงเพียงอาร์เรย์
แต่อีกครั้งกัญชา ตารางอยู่ในขณะนี้สิ่งที่เราจะ
เรียกชนิดข้อมูลนามธรรมที่เป็นเพียง การเรียงลำดับของความคิดฝังรากลึกอยู่ด้านบน
บางสิ่งบางอย่างทางโลกมากขึ้น ตอนนี้ชอบอาร์เรย์
>> ตอนนี้วิธีที่เราทำไป เกี่ยวกับการแก้ปัญหา?
ดีก่อนหน้านี้ผมก็มีความหรูหรา ของการมีพื้นที่ตารางพอที่นี่
เพื่อที่ฉันจะใส่ จิปาถะที่ใดก็ได้ที่ฉันต้องการ
ดังนั้นในฐานะที่จะไปที่นี่
Zs อาจจะไปที่นี่
นางสาวอาจจะไปที่นี่
แล้วผมก็มีบางพื้นที่พิเศษ
แต่นี้เป็นบิตของโกงขวา ในขณะนี้เพราะตารางนี้ถ้าผมจริงๆ
คิดว่ามันเป็นอาเรย์เป็นเพียง จะมีขนาดคงที่บางส่วน
>> ดังนั้นในทางเทคนิคถ้าผมดึง ขึ้นแบบทดสอบของนักเรียนอีก
และดูโอ้คนนี้ ชื่อเริ่มต้นด้วยเกินไป
ชนิดของฉันต้องการที่จะนำมันมี
แต่ทันทีที่ฉันวางมันมีถ้า ตารางนี้แน่นอนเป็นอาร์เรย์
ฉันจะได้รับการเอาชนะหรือ clobbering ใครก็ตามที่ทำแบบทดสอบของนักเรียนนี้
ใช่มั้ย?
หากเป็นอาร์เรย์เพียงสิ่งเดียวสามารถ ไปในแต่ละเซลล์เหล่านี้หรือองค์ประกอบ
และดังนั้นผมชนิดของมี ที่จะเลือกและเลือก
>> ก่อนหน้านี้ตอนนี้ผมชนิด โกงและทำอย่างนี้หรือฉัน
เพียงแค่ซ้อนชนิดของ พวกเขาให้เหนือคนอื่น ๆ
แต่ที่ไม่ได้ไปบินในรหัส
เพื่อที่ฉันจะใส่ นักเรียนที่สองที่มีชื่อ
คือถ้าสิ่งที่ผมต้องเป็นแบบนี้ พื้นที่ตารางใช้ได้?
และฉันได้ใช้สามช่องและมัน มีลักษณะอื่น ๆ เช่นมีเพียงไม่กี่
สิ่งที่คุณสามารถทำอะไรได้บ้าง
ผู้ชม: [ไม่ได้ยิน]
DAVID ลัน: ใช่
บางทีขอเพียงแค่ให้มันง่าย
ใช่มั้ย?
มันไม่พอดีที่ฉันต้องการที่จะนำมัน
ดังนั้นฉันจะใส่มัน ในทางเทคนิคที่ B จะไป
ตอนนี้แน่นอนผมเริ่มต้น การวาดตัวเองในมุม
ถ้าฉันได้รับนักเรียน ที่มีชื่อเป็นจริง B,
ตอนนี้ B จะถูกย้ายไปเล็ก ๆ น้อย ๆ ไปข้างหน้าในขณะที่อาจจะเกิดขึ้นครับ
ถ้าเป็น B ตอนนี้มันได้ไปที่นี่
>> และเพื่อให้ได้อย่างรวดเร็ว อาจจะกลายเป็นปัญหา
แต่มันก็เป็นเทคนิคที่จริง จะเรียกว่าเป็นเส้นละเอียด,
โดยคุณเพียงแค่พิจารณาของคุณ อาเรย์ที่จะเป็นไปตามเส้น
และคุณเพียงแค่ชนิดของการสอบสวนหรือ ตรวจสอบในแต่ละองค์ประกอบ
มองหาจุดที่สามารถใช้ได้
และทันทีที่คุณพบว่า หนึ่งที่คุณวางไว้ในที่นั่น
>> ตอนนี้ราคาการจ่ายเงินตอนนี้ สำหรับการแก้ปัญหานี้คืออะไร?
เรามีอาร์เรย์ขนาดคงที่ และเมื่อฉันใส่ชื่อ
ลงไปอย่างน้อยในขั้นต้นว่ามีอะไร เวลาทำงานของการแทรก
สำหรับการวางของนักเรียน แบบทดสอบในถังที่เหมาะสมหรือไม่
Big O ของสิ่งที่?
>> ผู้ชม: n
DAVID ลัน: ฉันได้ยิน O ใหญ่ของ n
ไม่เป็นความจริง
แต่เราจะหยอกล้อกัน ทำไมในเวลาเพียงสักครู่
อะไรมันอาจจะมี?
>> ผู้ชม: [ไม่ได้ยิน]
DAVID ลัน: และให้ฉันทำมันสายตา
ดังนั้นคิดว่านี้เป็นตัวอักษรเอส
>> ผู้ชม: มันเป็นหนึ่งใน
DAVID ลัน: มันเป็นหนึ่งใน
ใช่มั้ย?
นี้เป็นอาเรย์ซึ่ง หมายความว่าเรามีการเข้าถึงแบบสุ่ม
และถ้าเราคิดว่าเรื่องนี้ เป็นศูนย์และนี่เป็น 25
และเราตระหนักว่า โอ้นี่เป็นสัญญาณ S ของฉัน
แน่นอนฉันจะแปลง S, อักขระ ASCII,
ให้เป็นตัวเลขที่สอดคล้อง ระหว่างศูนย์และ 25
และแล้วทันที วางไว้ที่มันอยู่
>> แต่แน่นอนเร็วที่สุดเท่าที่ฉันได้รับการ คนที่สองที่ชื่อเป็น A หรือ B หรือ C
ในที่สุดถ้าผมเคยใช้ เส้นละเอียดเป็นวิธีแก้ปัญหาของฉัน
เวลาทำงานของ แทรกในกรณีที่เลวร้ายที่สุด
เป็นจริงจะตกมาอยู่ในสิ่งที่?
และฉันไม่ได้ยินมันนี่ ได้อย่างถูกต้องในช่วงต้น
ผู้ชม: [ไม่ได้ยิน]
DAVID ลัน: ดังนั้นจึงเป็น n แน่นอนอีกครั้ง คุณมีชุดข้อมูลที่มีขนาดใหญ่พอสมควร
ดังนั้นในแง่หนึ่งหาก อาเรย์ของคุณมีขนาดใหญ่พอ
และข้อมูลของคุณจะเบาบางพอคุณ ได้รับเวลานี้คงสวยงาม
แต่ทันทีที่คุณเริ่มต้น รับองค์ประกอบมากขึ้นและมากขึ้น
และเพียงแค่สถิติที่คุณจะได้รับ ผู้คนมากขึ้นด้วยตัวอักษร
เป็นชื่อหรือหนังสือของพวกเขา B, มันอาจ
ตกมาเป็นสิ่งที่มากขึ้นเชิงเส้น
จึงไม่สมบูรณ์แบบเลยทีเดียว
เพื่อให้เราสามารถทำดีกว่า
>> ดีสิ่งที่เป็นของเรา การแก้ปัญหาก่อนที่เมื่อเรา
ต้องการที่จะมีชีวิตชีวามากกว่า บางอย่างเช่นอาเรย์ได้รับอนุญาต?
ผู้ชม: [ไม่ได้ยิน]
DAVID ลัน: เราไม่แนะนำอะไร?
ใช่
ดังนั้นรายการที่เชื่อมโยง
ดีขอดูสิ่งที่เชื่อมโยง รายการอาจจะทำเพื่อเราแทน
ดีให้ฉันเสนอเราว่า วาดภาพดังต่อไปนี้
ขณะนี้เป็นที่แตกต่างกัน ภาพจากตัวอย่าง
จากข้อความที่แตกต่างกันในความเป็นจริงว่า เป็นจริงโดยใช้อาร์เรย์ขนาด 31
และผู้เขียนคนนี้เพียงแค่ ตัดสินใจที่จะสับสตริง
ไม่ได้ขึ้นอยู่กับชื่อของบุคคล แต่ขึ้นอยู่กับวันเกิดของพวกเขา
โดยไม่คำนึงถึงของเดือนที่พวกเขาคิด ถ้าคุณเกิดในวันแรกของเดือน
หรือวันที่ 31 ของเดือนที่ผู้เขียน จะสับขึ้นอยู่กับค่าที่
เพื่อกระจายชื่อออกเล็กน้อย มากกว่าเพียงแค่ 26 จุดที่อาจจะช่วยให้
และบางทีมันอาจจะเป็นชุดที่น้อยมาก กว่าจะมีตัวอักษรตัวอักษร
เพราะแน่นอนอาจมี ผู้คนจำนวนมากในโลกที่มีชื่อ
เริ่มต้นด้วยกว่าแน่นอนว่า บางตัวอักษรอื่น ๆ ของตัวอักษร
ดังนั้นอาจจะเป็นเพียงเล็กน้อย เครื่องแบบสมมติ
กระจายสม่ำเสมอ ของทารกในเดือน
>> แต่แน่นอนนี้ยังคงไม่สมบูรณ์
ใช่มั้ย?
เรากำลังมีการชนกัน
หลายคนในนี้ โครงสร้างข้อมูลยังคงอยู่
มีวันเกิดเดียวกันอย่างน้อย คุณโดยไม่คำนึงถึงเดือน
แต่สิ่งที่ผู้เขียนได้ทำ?
ดีก็ดูเหมือนว่าเรามีอาร์เรย์ อยู่ทางด้านซ้ายมือวาดในแนวตั้ง
แต่นั่นเป็นเพียงการกระทำของศิลปิน
มันไม่สำคัญว่าสิ่งที่ทิศทางที่คุณ วาดอาร์เรย์ก็ยังคงอาร์เรย์
สิ่งนี้เป็นอาร์เรย์ของเห็นได้ชัด?
>> ผู้ชม: รายการที่เชื่อมโยง
>> DAVID ลัน: ใช่
ดูเหมือนว่าจะเป็น อาร์เรย์ของรายการที่เชื่อมโยง
ดังนั้นอีกครั้งไปยังจุดของการจัดเรียงนี้ ของการใช้โครงสร้างข้อมูลเหล่านี้
เป็นส่วนประกอบให้มากขึ้น การแก้ปัญหาที่น่าสนใจ
คุณอย่างสามารถใช้ พื้นฐานเช่นอาร์เรย์
แล้วนำสิ่งที่มากขึ้น ที่น่าสนใจเช่นรายการที่เชื่อมโยง
และแม้กระทั่งการรวมพวกเขาเป็นได้ โครงสร้างข้อมูลที่น่าสนใจอื่น ๆ อีกมากมาย
และแน่นอนนี้จะเกินไป จะเรียกว่าตารางแฮช,
โดยอาร์เรย์เป็น จริงๆตารางแฮช,
แต่ตารางแฮชที่มี เครือข่ายเพื่อที่จะพูด
ที่สามารถเติบโตหรือหดตาม จำนวนขององค์ประกอบที่คุณต้องการแทรก
>> ตอนนี้ดังนั้นสิ่งที่ เวลาที่ใช้ตอนนี้หรือไม่
ถ้าผมต้องการที่จะใส่คน ที่มีวันเกิดเป็นวันที่ 31 ตุลาคม
ที่เขาหรือเธอไป?
สิทธิ์ทั้งหมด
ที่ด้านล่างสุดที่จะกล่าวว่าวันที่ 31
และนั่นคือสิ่งที่สมบูรณ์แบบ
นั่นเป็นครั้งอย่างต่อเนื่อง
แต่ถ้าเราหาคนอื่น ที่มีวันเกิดที่ให้มาดู
เดือนตุลาคมพฤศจิกายน 31 ธันวาคม?
อยู่ที่ไหนเขาหรือเธอจะไป?
สิ่งเดียวกัน
ขั้นตอนที่สองว่า
ที่คงที่แม้ว่าไม่ได้หรือไม่
สิทธิ์ทั้งหมด
ในขณะที่มันเป็น
แต่ในกรณีทั่วไป ผู้คนจำนวนมากที่เราเพิ่ม
ความน่าจะเป็นเราจะ ที่จะได้รับการชนกันมากขึ้น
>> ขณะนี้เป็นเพียงเล็กน้อย ดีกว่าเพราะในทางเทคนิค
ตอนนี้กลุ่มของฉันอาจจะอยู่ใน กรณีที่เลวร้ายนานแค่ไหน?
ถ้าฉันใส่ n คนเข้ามามากขึ้น โครงสร้างข้อมูลที่ซับซ้อน n คน
ในกรณีที่เลวร้ายที่สุดมันจะเป็น n
ทำไม?
>> ผู้ชม: เพ​​ราะถ้าทุกคน มีวันเกิดเดียวกัน
พวกเขากำลังจะเป็นหนึ่งในสาย
DAVID ลันเพอร์เฟ
มันอาจจะประดิษฐ์เล็ก ๆ น้อย ๆ แต่อย่างแท้จริงในกรณีที่เลวร้ายที่สุด
ถ้าทุกคนมีวันเกิดเดียวกัน ที่ได้รับปัจจัยการผลิตที่คุณมี
คุณกำลังจะมี ห่วงโซ่ยาวอย่างหนาแน่น
และเพื่อให้คุณสามารถเรียกมันว่า สับตาราง แต่จริงๆมัน
เพียงแค่รายการที่เชื่อมโยงขนาดใหญ่ที่มี เป็นจำนวนมากทั้งของพื้นที่ที่สูญเสียไป
แต่โดยทั่วไปถ้าเราคิดว่า อย่างน้อยวันเกิดเป็น uniform--
และมันอาจจะไม่
ฉันทำขึ้น
แต่ถ้าเราคิดว่าสำหรับ ประโยชน์ของการสนทนา
ว่าพวกเขามีแล้วในทางทฤษฎีถ้า นี้คือการแสดงในแนวตั้ง
ของอาร์เรย์ที่ดีแล้วหวังว่าคุณ จะได้รับกลุ่มที่มีคุณรู้ว่า
ประมาณระยะเวลาเดียวกับที่แต่ละ เหล่านี้แสดงให้เห็นถึงวันของเดือน
>> ตอนนี้ถ้ามี 31 วันในเดือน, นั่นหมายความว่าเวลาทำงานของฉันจริงๆ
เป็น O ใหญ่ของ n กว่า 31 ซึ่ง รู้สึกดีขึ้นกว่าที่เป็นเส้นตรง
แต่สิ่งที่เป็นหนึ่งในของเรา ภาระผูกพันสองสามสัปดาห์
ที่ผ่านมาเมื่อใดก็ตามที่มันมาถึงการแสดง เวลาทำงานของอัลกอริทึม?
เพียงมองไปที่คำสั่งซื้อสูง
ใช่มั้ย?
31 แน่นอนเป็นประโยชน์
แต่นี้ยังคง O ใหญ่ของ n
แต่หนึ่งในรูปแบบ ของปัญหาการตั้งห้า
เป็นไปได้ที่จะ ยอมรับว่าอย่างแน่นอน
asymptotically เหตุผล โครงสร้างข้อมูลนี้
ไม่ดีกว่าเพียงแค่ หนึ่งรายการที่เชื่อมโยงขนาดใหญ่
และแน่นอนในกรณีที่เลวร้ายที่สุดนี้ ตารางแฮชอาจจะตกมาอยู่ในที่
>> แต่ในโลกแห่งความจริงกับมนุษย์เรา ที่แม็คเองหรือเครื่องคอมพิวเตอร์หรืออะไรก็ตาม
และกำลังทำงานอยู่โลกแห่งความจริง ซอฟแวร์กับข้อมูลจริง
ซึ่งขั้นตอนวิธีที่คุณจะชอบ?
หนึ่งที่ใช้ขั้นตอนปลายหรือ หนึ่งที่จะใช้เวลา n หารด้วย 31 ขั้นตอน
ที่จะหาชิ้นส่วนของข้อมูลบางส่วนหรือ เพื่อค้นหาข้อมูลบางอย่าง?
ผมหมายความว่าอย่าง 31 ทำให้ ความแตกต่างในโลกแห่งความจริง
มันเป็น 31 ครั้งได้เร็วขึ้น
และมนุษย์เราอย่างแน่นอน จะขอบคุณที่
>> เพื่อตระหนักถึงขั้ว ระหว่างมีจริง
พูดคุยเกี่ยวกับสิ่งที่ในทางทฤษฎี และในเชิงเส้นที่แน่นอน
มีค่าที่เราได้เห็น แต่ในโลกแห่งความเป็นจริง
ถ้าคุณดูแลเกี่ยวกับการเพียงแค่การทำ ความสุขของมนุษย์สำหรับปัจจัยการผลิตทั่วไป
คุณเป็นอย่างดีอาจต้องการที่จะยอมรับ ความจริงที่ว่าใช่นี้เป็นเชิงเส้น
แต่มันก็เป็น 31 ครั้งได้เร็วขึ้น กว่าเส้นอาจจะมี
และยังดีกว่าเราไม่เพียงแค่ต้อง ทำอะไรโดยพลการเช่นวันเกิด,
เราสามารถใช้จ่ายเล็ก ๆ น้อย ๆ เวลาและความฉลาด
และคิดเกี่ยวกับสิ่งที่เราอาจจะทำ ชื่อของบุคคลและอาจจะ
วันเกิดของพวกเขาที่จะรวมเหล่านั้น ส่วนผสมที่จะคิดออกบางสิ่งบางอย่าง
ที่เป็นจริงมากขึ้น สม่ำเสมอและหยักน้อย
จึงจะพูดกว่าภาพนี้ นี้แสดงให้เห็นว่ามันอาจจะ
วิธีการที่เราสามารถดำเนินการนี​​้ในรหัส?
ดีให้ฉันเสนอเราว่า เพียงแค่ขอยืมไวยากรณ์บางอย่างที่เราได้
ใช้กี่ครั้งป่านนี้
และฉันจะต้องกำหนด โหนดที่อีกครั้ง
เป็นคำทั่วไปสำหรับเพียงบางส่วน ภาชนะสำหรับโครงสร้างข้อมูลบางส่วน
ฉันจะเสนอว่า สตริงเป็นไปในที่นั่น
แต่เรากำลังจะเริ่มต้นการ ผู้ที่ล้อการฝึกอบรมออกตอนนี้
>> ไม่มีห้องสมุด CS50 เพิ่มเติม จริงๆถ้าคุณต้องการ
ที่จะใช้สำหรับขั้นสุดท้ายของคุณ โครงการซึ่งเป็นเรื่องปกติ
แต่ตอนนี้เรากำลังจะดึงกลับมา ผ้าม่านและบอกว่ามันเป็นเพียงแค่ดาวถ่าน
ดังนั้นคำว่ามีเป็นไปได้ ชื่อของบุคคลในคำถาม
และตอนนี้ฉันมีการเชื่อมโยง ที่นี่ไปยังโหนดถั​​ดไป
เพื่อที่ว่าเหล่านี้เป็นตัวแทน แต่ละโหนด
ในห่วงโซ่ที่อาจ ของรายการที่เชื่อมโยง
>> และตอนนี้ฉันจะประกาศ ตารางแฮชของตัวเอง?
ผมไม่ประกาศโครงสร้างทั้งหมดนี้ได้อย่างไร
ดีจริงๆเหมือนผมใช้ตัวชี้ เพียงแค่องค์ประกอบแรกของรายการ
ก่อนที่จะคล้าย ๆ ฉันสามารถเพียงกล่าวว่า ผมเพียงแค่ต้องพวงของตัวชี้
ที่จะใช้ตารางแฮชทั้งหมดนี้
ฉันจะมีอาร์เรย์ เรียกว่าตารางสำหรับตารางแฮช
มันเป็นไปได้ของความจุขนาด
นั่นเป็นวิธีที่หลายองค์ประกอบสามารถใส่ในนั้น
และแต่ละองค์ประกอบเหล่านั้นในเรื่องนี้ อาร์เรย์เป็นไปได้ที่ดาวโหนด
ทำไม?
ดีต่อภาพนี้สิ่งที่ฉัน การดำเนินการตารางแฮชเป็น
ได้อย่างมีประสิทธิภาพในการเริ่มต้นเป็นเพียง แถวนี้ที่เราได้วาดในแนวตั้ง
แต่ละสี่เหลี่ยมที่มี แสดงให้เห็นถึงตัวชี้
ว่าคนที่มีความทับ ผ่านพวกเขาเป็นเพียง null
และคนที่มี ลูกศรไปทางขวา
เป็นตัวชี้ไปยังโหนดที่เกิดขึ้นจริงที่เกิดขึ้นจริง เพราะฉะนั้นจุดเริ่มต้นของรายการที่เชื่อมโยง
>> ดังนั้นที่นี่ก็คือวิธีการที่เราอาจจะ ใช้ตารางแฮชที่
ดำเนินการผูกมัดแยกต่างหาก
ตอนนี้เราสามารถทำดีกว่า
สิทธิทั้งหมดที่ฉันสัญญาว่าครั้งสุดท้ายที่ เราสามารถประสบความสำเร็จอย่างต่อเนื่องตลอดเวลา
และชนิดของฉันให้คุณ เวลาคงที่นี่
แต่แล้วก็กล่าวว่าไม่ได้จริงๆ เวลาคงเพราะมันยังคง
ขึ้นอยู่กับทั้งหมด จำนวนขององค์ประกอบ
คุณกำลังป้อนเข้าไปใน โครงสร้างข้อมูล
แต่สมมติว่าเราทำอย่างนี้
ผมขอกลับไปที่หน้าจอมากกว่าที่นี่
ให้ฉันยังโครงการนี​​้ขึ้นที่นี่ชัดเจน หน้าจอและคิดว่าฉันทำอย่างนี้
สมมติว่าผมต้องการที่จะใส่ชื่อ Daven ในในโครงสร้างข้อมูลของฉัน
>> ดังนั้นผมจึงต้องการแทรกสตริง Daven เป็นโครงสร้างข้อมูล
จะทำอย่างไรถ้าฉันไม่ได้ใช้ สับตาราง แต่ฉันจะใช้
สิ่งที่มากขึ้นต้นไม้ เหมือนต้นไม้ครอบครัวที่
คุณมีรากบางส่วนที่ โหนดด้านบนแล้วและใบ
ที่ไปลงและขาออก
สมมติว่าแล้วผมว่า ต้องการแทรก Daven ของ
เป็นสิ่งที่เป็นอยู่ในปัจจุบันรายการที่ว่างเปล่า
ฉันจะทำต่อไปนี้: ฉัน จะสร้างโหนดในครอบครัวนี้
ต้นไม้โครงสร้างข้อมูลที่มีลักษณะ เล็ก ๆ น้อย ๆ เช่นนี้ซึ่งแต่ละ
รูปสี่เหลี่ยมได้สมมุติว่า สำหรับตอนนี้ 26 องค์ประกอบในนั้น
และแต่ละเซลล์ ในอาร์เรย์นี้จะ
เพื่อเป็นตัวแทนของตัวอักษร
>> โดยเฉพาะผมจะรักษา นี้แล้ว B แล้ว C, D แล้ว,
หนึ่งที่นี่
ดังนั้นนี้เป็นไปอย่างมีประสิทธิภาพ เป็นตัวแทนของตัวอักษรที่ดี
แต่การที่จะใส่ทั้งหมดของ Daven ของ ชื่อที่ฉันต้องทำมากขึ้นอีกนิด
ดังนั้นฉันแรกจะสับจึงจะพูด
ฉันจะไปดูที่ตัวอักษรตัวแรก ใน Daven ซึ่งจะเห็นได้ชัด D,
และฉันจะจัดสรร โหนดที่มีลักษณะ
เหมือนเจ้านี่สี่เหลี่ยมผืนผ้าขนาดใหญ่ขนาดใหญ่ พอที่จะพอดีกับตัวอักษรทั้ง
>> ตอนนี้ D จะทำ
ตอนนี้ A. D-A-V-E-N เป​​็นเป้าหมาย
ดังนั้นตอนนี้สิ่งที่ผมจะทำคือ
ทันทีที่ผมเริ่ม D แจ้งให้ทราบล่วงหน้า มีตัวชี้ไม่มี
มันเป็นค่าขยะในขณะนี้ หรือฉันอาจจะเริ่มต้นมันเป็นโมฆะ
แต่ให้ฉันเก็บไปด้วย ความคิดของการสร้างต้นไม้นี้
ผมขอจัดสรรอีกหนึ่งของเหล่านี้ โหนดที่มี 26 องค์ประกอบในนั้น
>> และคุณรู้อะไรไหม?
ถ้านี้เป็นเพียงโหนดในหน่วยความจำที่ ฉันสร้างขึ้นด้วย malloc ใช้ struct
ในขณะที่เราจะเห็นทันทีที่ ฉันจะทำเจ้านี่
ฉันจะวาดล​​ูกศรจาก สิ่งที่เป็นตัวแทน D ลง
ไปยังโหนดใหม่นี้
และตอนนี้เป็นครั้งแรกต่อไป ตัวอักษรที่อยู่ในชื่อ Daven ของ
V-- D-A-V-- ฉันจะไปข้างหน้า และวาดโหนดอื่นเช่นนี้
โดยองค์ประกอบ V ที่นี่ซึ่ง เราจะวาด instance-- ขออภัย
เราจะไม่วาดมี
มันจะไปที่นี่
>> จากนั้นเรากำลังจะไป พิจารณานี้จะ V.
แล้วลงที่นี่เรากำลังจะดัชนี ลดลงจาก V เป็นสิ่งที่เราจะพิจารณาอี
และจากที่นี่เรากำลังจะไป ไปมีหนึ่งโหนดเหล่านี้ที่นี่
และตอนนี้เรามีคำถามที่จะตอบ
ฉันต้องการที่จะแสดงให้เห็นว่าอย่างใด เราอยู่ที่ปลายสาย Daven
ดังนั้นผมก็สามารถปล่อยให้มันเป็นโมฆะ
>> แต่สิ่งที่ถ้าเรามี Daven ของ ชื่อเต็มด้วยซึ่ง
คือในขณะที่เราได้กล่าวว่าดาเวนพอร์ต?
ดังนั้นสิ่งที่ถ้าเป็น Daven จริงย่อย,
คำนำหน้าของสตริงนานมาก?
เราก็ไม่สามารถไปอย่างถาวร พูดอะไรที่เป็นไป
ไปที่นั่นเพราะเราสามารถทำได้ ไม่เคยใส่คำเหมือนดาเวนพอร์ต
เป็นโครงสร้างข้อมูล
>> ดังนั้นสิ่งที่เราสามารถทำแทนเป็น ปฏิบัติต่อกันขององค์ประกอบเหล่านี้
ขณะที่อาจจะมีสอง องค์ประกอบภายในของพวกเขา
หนึ่งคือตัวชี้จริง ขณะที่ฉันได้ทำ
ดังนั้นแต่ละกล่องเหล่านี้ ไม่ได้เป็นเพียงหนึ่งเซลล์
แต่ถ้าด้านบน one-- หนึ่งด้านล่างของ
จะเป็นโมฆะเพราะ ไม่มีหนังสือเพียง แต่
ถ้าหนึ่งด้านบน บางค่าพิเศษ?
และมันจะเป็นเพียงเล็กน้อย ยากที่จะวาดมันขนาดนี้
แต่คิดว่ามันเป็นเพียงเครื่องหมาย
ตรวจสอบ
D-A-V-E-N เป​​็นสตริง ในโครงสร้างของข้อมูลนี้
>> ในขณะเดียวกันถ้าผมมีพื้นที่มากขึ้น ที่นี่ฉันจะทำ P-O-R-T,
และฉันจะทำให้การตรวจสอบในโหนด ที่มีตัวอักษร T ที่ท้ายสุด
ดังนั้นนี่คืออย่างหนาแน่น ซับซ้อนมองโครงสร้างข้อมูล
และเขียนด้วยลายมือของฉัน แน่นอนไม่ได้ช่วย
แต่ถ้าผมอยากจะใส่อะไรบางอย่าง อื่นพิจารณาสิ่งที่เราจะทำ
ถ้าเราต้องการที่จะนำดาวิด เราจะทำตามตรรกะเดียวกัน D-A-V,
แต่ตอนนี้ผมจะชี้ให้ในครั้งต่อไป องค์ประกอบไม่ได้มาจาก E แต่จากที่ฉันจะดี
ดังนั้นจึงมีความเป็นไปได้ โหนดในต้นไม้ต้นนี้
เรากำลังจะมีการเรียก malloc เพิ่มเติม
แต่ฉันไม่ต้องการที่จะให้ รับประทานอาหารที่สมบูรณ์ของภาพนี้
จึงขอแทนที่จะมองไปที่หนึ่ง ที่ถูกก่อนกำหนด
เช่นนี้ไม่ได้มีจุด, จุด, จุด แต่อาร์เรย์ยากเพียงแค่
แต่แต่ละโหนด ในต้นไม้ขึ้นที่นี่
แสดงให้เห็นถึง thing-- เดียวกัน อาเรย์เรย์ขนาด 26
>> หรือถ้าเราต้องการที่จะ ที่เหมาะสมจริงๆตอนนี้สิ่งที่
ถ้าชื่อของใครบางคนเป็น เครื่องหมายวรรคตอนให้
สมมติว่าแต่ละโหนดจริงมี เช่น 27 ดัชนีในมันไม่ใช่แค่ 26
ดังนั้นในตอนนี้จะเป็นข้อมูลที่ โครงสร้างที่เรียกว่า trie-- T-R-I-E
Trie ซึ่งเป็นที่คาดคะเน ในอดีตชื่อฉลาดสำหรับต้นไม้
ที่เหมาะสำหรับ การเรียกที่แน่นอน
ถูกสะกดด้วย I-E จึง Trie
แต่ที่เป็นประวัติศาสตร์ของ Trie
>> ดังนั้น Trie ข้อมูลต้นไม้เช่นนี้ โครงสร้างเช่นต้นไม้ครอบครัว
ในท้ายที่สุดว่ามีพฤติกรรมเช่นนั้น
และนี่เป็นเพียงตัวอย่างของอีก ทั้งกลุ่มของชื่อของคนอื่น
แต่คำถามนี้ ที่อยู่ในมือคือสิ่งที่มี
เราได้รับโดยการแนะนำเนื้อหาที่มากขึ้น โครงสร้างข้อมูลที่ซับซ้อนและหนึ่ง
ตรงไปตรงมาที่ใช้หน่วยความจำมาก
>> เพราะถึงแม้, ในขณะที่ฉันเท่านั้น
ใช้ตัวชี้ D'และ และ V แ​​ละ Es และ NS,
ฉันเสีย heck ของมากของหน่วยความจำ
แต่ที่ผมใช้ทรัพยากรหนึ่ง ฉันมักจะได้รับกลับทำอีก
ดังนั้นถ้าผมใช้พื้นที่มากขึ้น สิ่งที่อาจจะเป็นความหวังหรือไม่
ที่ฉันใช้จ่ายน้อยอะไร?
ผู้ชม: ใช้เวลาน้อยลง
DAVID ลัน: เวลา
ตอนนี้ทำไมที่อาจจะมี?
ดีสิ่งที่เป็นแทรก เวลาในแง่ของ O ขนาดใหญ่ในขณะนี้
ชื่อเหมือน Daven หรือหนังสือหรือดาวิด
ดี Daven เป็นห้าขั้นตอน
ดาเวนพอร์ตจะเป็นเก้าขั้นตอน ดังนั้นมันจะเป็นไม่กี่ขั้นตอนมากขึ้น
เดวิดจะเป็นห้าขั้นตอนเป็นอย่างดี
ดังนั้นผู้ที่เป็นรูปธรรม ตัวเลข แต่ก็มี
ขอบเขตบน ความยาวของชื่อของใครบางคน
และแน่นอนในปัญหา ชุดห้าสเปค
เรากำลังจะนำเสนอ ว่ามันเป็นบางสิ่งบางอย่าง
ที่ 40 บางแปลกตัวอักษร
>> แนบเนียนไม่มีใครมี ชื่อยาวเพียบ
ซึ่งเป็นที่จะบอกว่าความยาวของ ชื่อหรือความยาวของสตริงที่เราอาจจะ
มีบางรัฐ โครงสร้างเป็น arguably อะไร?
มันเป็นค่าคงที่
ใช่มั้ย?
มันอาจจะเป็นค่าคงที่ขนาดใหญ่เช่น 40 บางสิ่งบางอย่าง แต่มันเป็นค่าคงที่
และมีการพึ่งพาไม่กี่ ชื่ออื่น ๆ ที่มีอยู่ในโครงสร้างของข้อมูลนี้
ในคำอื่น ๆ ถ้าฉัน ตอนนี้อยากจะใส่
โคลทันหรือกาเบรียลหรือร็อบหรือ Zamyla หรือ อลิสันหรือเบลินดาหรือชื่ออื่น ๆ
จากพนักงานที่เป็นข้อมูลนี้ โครงสร้างเป็นเวลาการทำงาน
ใส่ชื่ออื่น ๆ จะเป็นที่รับผลกระทบ
โดยองค์ประกอบอื่น ๆ จำนวนที่จะ ในโครงสร้างข้อมูลอยู่แล้ว?
มันไม่ใช่
ใช่มั้ย?
เพราะเราได้อย่างมีประสิทธิภาพโดยใช้ ตารางแฮชนี้หลายชั้น
และเวลาในการทำงานของ ใด ๆ ของการดำเนินงานเหล่านี้
ไม่ได้ขึ้นอยู่กับจำนวนของ องค์ประกอบที่มีอยู่ในโครงสร้างข้อมูล
หรือที่ในที่สุดก็จะ ที่จะอยู่ในโครงสร้างข้อมูล
แต่อยู่กับความยาวของสิ่งเฉพาะ?
>> สตริงเป็น แทรกซึ่งจะทำให้
นี้คง asymptotically O ใหญ่ time-- หนึ่ง
และตรงไปตรงมาเพียงใน โลกแห่งความจริงนี้
หมายถึงการใส่ชื่อ Daven ใช้เวลา เช่นห้าขั้นตอนหรือหนังสือเก้า
ขั้นตอนหรือเดวิดห้าขั้นตอน
นั่นคือสาปสวยครั้งที่ทำงานขนาดเล็ก
และแน่นอนว่าเป็นมาก สิ่งที่ดีโดยเฉพาะอย่างยิ่งเมื่อ
มันไม่ได้ขึ้นอยู่กับทั้งหมด จำนวนขององค์ประกอบในการมี
ดังนั้นวิธีที่เราอาจดำเนินการนี​​้ ชนิดของโครงสร้างในรหัส?
มันเป็นเรื่องเล็ก ๆ น้อย ๆ มากขึ้น ที่ซับซ้อน แต่ยังคงเป็น
เพียงแค่การประยุกต์ใช้ หน่วยการสร้างพื้นฐาน
ฉันจะกำหนด เราโหนดดังต่อไปนี้:
บูลเรียกว่า word-- นี้ อาจจะเรียกว่าอะไร
แต่บูลหมายถึง สิ่งที่ฉันเข้ามาเป็นเครื่องหมาย
ใช่
นี่คือจุดสิ้นสุดของสตริง ในโครงสร้างของข้อมูลนี้
>> และแน่นอนดาวโหนด มีจะหมายถึงเด็ก
และแน่นอนเช่นเดียวกับ ต้นไม้ครอบครัวของคุณ
จะพิจารณาโหนด ที่แขวนออก
ของด้านล่างของผู้ปกครองบางส่วน องค์ประกอบที่จะเป็นเด็ก
และเพื่อให้เด็กเป็นไปได้ เป็นอาร์เรย์ของ 27 คนที่ 27
เป็นเพียงสำหรับ apostrophe
เรากำลังจะไปค้นหาที่พัก กรณีพิเศษที่
เพื่อให้คุณสามารถมีบางอย่าง ชื่อที่มีเครื่องหมาย
แม้อาจจะยัติภังค์ควร ไปในนั้น แต่คุณจะ
เห็นใน P ชุด 5 เราดูแลเท่านั้น เกี่ยวกับตัวอักษรและเครื่องหมาย
>> แล้วอย่างไรคุณเป็นตัวแทนของ โครงสร้างข้อมูลของตัวเอง?
คุณจะเป็นตัวแทนของราก ของ Trie นี้เพื่อที่จะพูด?
ดีเช่นเดียวกับรายการที่เชื่อมโยงคุณ ต้องชี้ไปยังองค์ประกอบแรก
ด้วย Trie คุณก็จำเป็นต้องใช้ ตัวชี้ไปยังรากของ Trie นี้
และจากนั้นคุณสามารถสับ วิธีการของคุณลงลึกและลึก
ทุกโหนดอื่น ๆ ในโครงสร้าง
ดังนั้นเพียงแค่มีความสามารถนี้ เราเป็นตัวแทน struct ที่
>> ตอนนี้ Meanwhile-- โอ้คำถาม
>> ผู้ชม: อะไรคือคำว่าบูล?
>> DAVID ลัน: คำ Bool เป็น เพียงแค่นี้ชาติ C
สิ่งที่ผมอธิบาย ในกล่องที่นี่เมื่อนี้
ผมเริ่มแยกแต่ละ องค์ประกอบของอาเรย์เป็นสองชิ้น
หนึ่งคือตัวชี้ไปยังโหนดถั​​ดไป
อื่น ๆ ที่จะต้องมี สิ่งที่ต้องการกล่องกาเครื่องหมาย
จะบอกว่าใช่มี คำที่ลงท้าย Daven ที่นี่
เพราะเราไม่ต้องการ ในขณะที่เดฟ
>> แม้ว่าเดฟเป็นไปได้ คำที่ถูกต้องเขาก็ไม่ได้อยู่ใน Trie
ยัง
และ D ไม่ใช่คำ
และ D-ไม่ใช่คำหรือชื่อ
ดังนั้นเครื่องหมาย แสดงให้เห็นเพียงครั้งเดียวที่คุณ
ตีโหนดนี้เป็น เส้นทางก่อนหน้านี้ของตัวละคร
จริงสตริงที่คุณใส่
ดังนั้นนั่นคือทั้งหมดที่บูล มีการทำสำหรับเรา
>> ใด ๆ คำถามอื่น ๆ ที่พยายาม?
ใช่
>> ผู้ชม: การทับซ้อนคืออะไร?
สิ่งที่ถ้าคุณมีเดฟและ Daven?
DAVID ลันเพอร์เฟ
สิ่งที่ถ้าคุณมีเดฟและ Daven?
ดังนั้นหากเราแทรกบอกชื่อเล่น สำหรับ David-- Dave-- D-A-V-E?
นี้เป็นจริงง่ายสุด
ดังนั้นเราเพียง แต่จะใช้ขั้นตอนที่สี่
D-A-V-E และฉันทำในสิ่งที่ต้อง ทำเมื่อผมกดที่โหนดที่สี่?
เพียงแค่จะไปตรวจสอบ
เราอยู่แล้วดีที่จะไป
เสร็จแล้ว
ขั้นตอนที่สี่
เวลาคงที่ในเชิงเส้น
และตอนนี้เราได้แสดงให้เห็นว่าทั้งเดฟ และ Daven นี้จะมีอยู่ในโครงสร้าง
ดังนั้นไม่ได้เป็นปัญหา
และแจ้งให้ทราบว่าการปรากฏตัว ของ Daven ไม่ได้ทำให้มัน
ใช้เวลามากขึ้นหรือน้อยลง เวลาสำหรับเดฟและในทางกลับกัน
>> ดังนั้นอะไรที่สามารถตอนนี้เราจะทำอย่างไร
เราได้ใช้คำอุปมานี้มาก่อน ถาดที่เป็นตัวแทนของบางสิ่งบางอย่าง
แต่มันกลับกลายเป็นว่า สแต็คของถาดเป็นจริง
ชี้ของข้อมูลนามธรรมอื่น type-- ระดับโครงสร้างข้อมูลที่สูงขึ้น
ว่าในท้ายที่สุดในวันนี้คือเพียงแค่ เช่นอาร์เรย์หรือรายการที่เชื่อมโยง
หรือสิ่งที่โลกมากขึ้น
แต่มันน่าสนใจมากขึ้น แนวคิดแนวความคิด
สแต็ค, เช่นนี้ ถาดที่นี่ในท้อง
โดยทั่วไปจะเรียกว่า เพียง that-- สแต็ค
>> และในรูปแบบของโครงสร้างข้อมูลนี้ คุณมีสอง operations--
คุณมีหนึ่งผลักดันเรียกร้องให้ เพิ่มสิ่งที่จะแตก
เหมือนกับการใส่ถาดอื่น กลับไปที่ด้านบนของสแต็ค
และแล้ว pop ซึ่งหมายความว่าคุณ ใช้ถาดบนสุดออก
แต่สิ่งที่สำคัญเกี่ยวกับสแต็คที่ มันมีลักษณะที่อยากรู้อยากเห็นนี้
ในฐานะที่เป็นพนักงานโรงอาหารเป็น จัดเรียงถาดสำหรับอาหารต่อไป
สิ่งที่เป็นไปได้ ความจริงเกี่ยวกับวิธีนักเรียน
มีปฏิสัมพันธ์กับโครงสร้างข้อมูลนี้หรือไม่?
ผู้ชม: พวกเขากำลังจะปรากฏหนึ่งออก
DAVID ลัน: พวกเขากำลังจะไป ปรากฏหนึ่งออกหวังว่าด้านบน
มิฉะนั้นมันเป็นเพียงชนิดของโง่ ที่จะไปทุกทางไปด้านล่าง
ใช่มั้ย?
โครงสร้างข้อมูลไม่อนุญาตให้จริงๆ คุณสามารถคว้าถาดด้านล่างอย่างน้อย
อย่างง่ายดาย
เพื่อให้มีความอยากรู้อยากเห็นนี้ สถานที่ให้บริการไปยังกอง
ที่รายการสุดท้ายคือ จะเป็นครั้งแรกที่ออกมาอย่างใดอย่างหนึ่ง
และนักวิทยาศาสตร์คอมพิวเตอร์เรียก นี้ LIFO-- สุดท้ายในครั้งแรกออกมา
และเป็นจริงไม่ได้ โปรแกรมที่น่าสนใจ
ก็ไม่จำเป็นต้องเป็นที่เห็นได้ชัดขณะที่บางคน คนอื่น ๆ แต่ก็สามารถจริงจะเป็นประโยชน์
และสามารถจริงจะดำเนินการ ในสองวิธีที่แตกต่างกัน
>> ดังนั้นหนึ่งและจริงให้ ไม่ให้ผมดำน้ำในที่
ลองทำเช่นนี้แทน
ลองดูที่หนึ่งที่เกือบจะ ความคิดเดียวกัน แต่มันเป็นเรื่องเล็ก ๆ น้อย ๆ ที่เป็นธรรม
ใช่มั้ย?
หากคุณเป็นหนึ่งของเด็กผู้ชายที่แฟนเหล่านี้หรือ สาว ๆ ที่ชอบผลิตภัณฑ์แอปเปิ้ล
และคุณตื่นขึ้นมาที่ 03:00 เข้าแถวที่ร้านบางส่วน
ที่จะได้รับ iPhone รุ่นใหม่ล่าสุดที่คุณ อาจจะมีคิวขึ้นเช่นนี้
>> ตอนนี้คิวเป็นชื่ออย่างจงใจ
มันเป็นเส้นเพราะมี เป็นธรรมบางส่วนไป
ใช่มั้ย?
มันจะดูดชนิดของถ้าคุณได้ ไปถึงที่นั่นเป็นครั้งแรกที่ Apple Store
แต่คุณจะได้อย่างมีประสิทธิภาพล่างสุด ถาดเพราะพนักงานแอปเปิ้ลแล้ว
ป๊อปเป็นคนสุดท้ายที่ จริงมีอยู่ในแนวเดียวกัน
ดังนั้นกองและคิวแม้ว่า หน้าที่ที่พวกเขากำลังชนิดของมันเหมือนกับ
มันเป็นเพียงแค่การเก็บสะสมนี้ ของทรัพยากรที่
มีกำลังที่จะเติบโตและ shrink-- ที่ ด้านความเป็นธรรมนี้เพื่อมัน
อย่างน้อยในโลกจริง ซึ่งการดำเนินการที่คุณออกกำลังกาย
มีความแตกต่างกันลึกซึ้ง
stack-- คิว rather-- กล่าวกันว่ามี
สองการดำเนินงาน: คิว n และงคิว
หรือคุณสามารถเรียกพวกเขา จำนวนของสิ่งใด ๆ
แต่คุณก็ต้องการจับภาพ ความคิดที่ว่าหนึ่งคือการเพิ่ม
และหนึ่งในที่สุดการลบ
>> ตอนนี้อยู่ใต้กระโปรงหน้ารถทั้งสองกอง และคิวที่จะต้องดำเนินการอย่างไร
เราจะไม่ไปลงรหัสของ เพราะระดับที่สูงขึ้น
ความคิดคือการจัดเรียงของที่เห็นได้ชัดมากขึ้น
ผมหมายถึงสิ่งที่มนุษย์ทำอย่างไร
ถ้าผมเป็นคนแรกที่แอปเปิ้ล การจัดเก็บและนี่คือประตูหน้า
คุณรู้ว่าฉันจะไปยืนอยู่ที่นี่
และคนถัดไป จะไปยืนอยู่ที่นี่
ดังนั้นสิ่งที่โครงสร้างข้อมูล ยืมตัวเองไปยังคิว?
>> ผู้ชม: คิว
DAVID ลัน: ดีคิว
แน่ใจ
อะไร?
>> ผู้ชม: รายการที่เชื่อมโยง
>> DAVID ลัน: การเชื่อมโยง รายการที่คุณสามารถใช้
และรายการที่เชื่อมโยงเป็นสิ่งที่ดีเพราะแล้ว มันสามารถเติบโตได้โดยพลตราบใดที่ไม่เห็นด้วย
จะมีบางจำนวนคงที่ ของคนที่อยู่ในร้าน
แต่บางทีจำนวนคงที่ ในสถานที่ที่ถูกต้องตามกฎหมาย
เพราะถ้าพวกเขาเพียง แต่มีเช่น 20 iPhones ในวันแรกอาจจะ
พวกเขาจะต้องอาร์เรย์ของขนาด 20 เพื่อเป็นตัวแทนของคิวที่ซึ่ง
เป็นเพียงการที่จะบอกว่าตอนนี้เมื่อเราเริ่มพูดคุย เกี่ยวกับปัญหาเหล​​่านี้ในระดับที่สูงขึ้น
คุณสามารถใช้มัน ในหลายวิธีใด ๆ
และอาจมีแค่ไป ซื้อขายออกไปในพื้นที่และเวลา
หรือเพียงแค่ในความซับซ้อนรหัสของคุณเอง
>> สิ่งที่เกี่ยวกับสแต็ค?
ดีสแต็คที่เราได้เห็นอีกด้วย ก็อาจจะถาดเหล่านี้
และคุณสามารถดำเนินการนี​​้อาเรย์
แต่ในบางจุดหากคุณใช้อาร์เรย์ สิ่งที่จะเกิดขึ้นกับถาด
คุณกำลังพยายามที่จะนำลง?
สิทธิ์ทั้งหมด
คุณเท่านั้นที่จะไป จะสามารถไปสูงมาก
และผมคิดว่าในท้องพวกเขากำลัง ปิดภาคเรียนจริงในการเปิดที่
ดังนั้นแน่นอนก็เกือบ เหมือนท้องจะใช้
อาร์เรย์ที่มีขนาดคงที่ เพราะคุณสามารถเท่านั้น
พอดีถาดจำนวนมากดังนั้นในการเปิดในที่ ผนังลงมาด้านล่างหัวเข่าของผู้คน
และอื่น ๆ ที่อาจจะมี กล่าวกันว่าเป็นอาร์เรย์
แต่แน่นอนเราสามารถใช้ว่า มากขึ้นโดยทั่วไปกับรายการที่เชื่อมโยง
>> ดีสิ่งที่เกี่ยวกับการควบคุมโครงสร้างข้อมูล?
ผมขอดึงขึ้นอีกหนึ่งภาพที่นี่
สิ่งที่ต้องการวิธีการเกี่ยวกับที่นี่นี้หรือไม่?
ทำไมมันอาจเป็นประโยชน์ที่จะมีไม่ได้ สิ่งที่เป็นแฟนซีเป็น Trie, ซึ่ง
เราเห็นมีโหนดกว้างมากเหล่านี้ แต่ละที่อยู่ในอาเรย์?
แต่ถ้าเราทำอะไรบางอย่างมากขึ้น ก็เหมือนต้นไม้ครอบครัวโรงเรียนเก่า
แต่ละโหนดมีที่นี่ เป็นเพียงการจัดเก็บจำนวนมาก
แทนชื่อหรือลูกหลาน เป็นเพียงการจัดเก็บตัวเลขเช่นนี้
>> ดีศัพท์แสงที่เราใช้ใน โครงสร้างข้อมูลที่ถูกพยายามทั้งสอง
และต้นไม้ที่ Trie อีกครั้งเป็น เพียงหนึ่งที่มีโหนดมีอาร์เรย์
ก็ยังคงเป็นสิ่งที่คุณอาจจะ ใช้จากโรงเรียนชั้นประถมศึกษาปี
เมื่อคุณทำในครอบครัว ใบและราก tree--
ของต้นไม้และเด็กของ พ่อแม่และพี่น้องของมัน
และเราอาจจะใช้ต้นไม้ เช่นเป็นเพียงเช่นนี้
ต้นไม้ถ้ามันเป็นโหนดหนึ่ง วงการเหล่านี้ที่มีตัวเลข
ก็จะไม่ให้มีการ หนึ่งในตัวชี้ แต่ทั้งสอง
และทันทีที่คุณเพิ่ม ตัวชี้ที่สองคุณ
จริงสามารถทำให้การจัดเรียง ของข้อมูลสองมิติ
โครงสร้างในหน่วยความจำ
เหมือนสองมิติ อาร์เรย์ที่คุณสามารถ
มีชนิดของสองมิติ รายการเชื่อมโยง แต่คน
ที่เป็นไปตามรูปแบบ ที่ไม่มีรอบ
มันอย่างแท้จริงต้นไม้ที่มีอย่างใดอย่างหนึ่ง วิธีที่ปู่ย่าตายายที่นี่แล้ว
ผู้ปกครองบางคนและเด็กและ หลานและเหลน
เป็นต้น
>> แต่สิ่งที่เป็นจริงเกี่ยวกับเรื่องนี้เรียบร้อยเกินไป เพียงเพื่อหยอกล้อคุณมีบิตของรหัส
การเรียกคืนจากการเรียกซ้ำ เดี๋ยวกลับโดย
คุณเขียนฟังก์ชันที่เรียกตัวเองว่า
นี่เป็นโอกาสที่สวยงาม ในการดำเนินการบางสิ่งบางอย่าง
เช่นการเรียกซ้ำเพราะพิจารณานี้
>> นี้เป็นต้นไม้
และฉันได้รับทางทวารหนั​​กเล็ก ๆ น้อย ๆ กับวิธีการ ฉันใส่จำนวนเต็มไปที่ถนน
มากเสียจนมันมีพิเศษ name-- ค้นหาต้นไม้ไบนารี
ตอนนี้เราเคยได้ยินไบนารี ค้นหา แต่คุณสามารถ
ทำงานหลังจากชื่อสิ่งนี้?
เป็นรูปแบบของวิธีการที่ฉันคืออะไร แทรกจำนวนเต็มเป็นต้นไม้นี้หรือไม่?
มันไม่โดยพลการ
มีรูปแบบบางส่วนเป็น
ใช่
>> ผู้ชม: คนเล็กทางด้านซ้าย
>> DAVID ลัน: ใช่
คนเล็กจะอยู่ทางซ้ายมือ
คนที่ใหญ่กว่าอยู่ทางขวา
ดังกล่าวว่าเป็นคำสั่งที่แท้จริงคือ พ่อแม่มากกว่าเด็กทางด้านซ้ายของ
แต่น้อยกว่าเด็กขวา
และที่อยู่คนเดียวคือแม้ ความหมายของคำพูดซ้ำ
เพราะคุณสามารถนำมาใช้ว่า ตรรกะเดียวกันทุกโหนด
และมันก้น จากกรณีฐานถ้าคุณ
จะเมื่อคุณตีหนึ่งของ ใบเพื่อที่จะพูด
ที่ปล่อยให้มีเด็กต่อไป
>> ตอนนี้วิธีที่คุณอาจพบว่าจำนวน 44?
คุณจะเริ่มต้นที่รากและพูดว่า HM
55 ไม่ได้ 44 ดังนั้นฉันต้องการที่จะไป ขวาหรือฉันต้องการที่จะไปทางซ้าย?
ดีอย่างเห็นได้ชัดคุณต้องการไปทางด้านซ้าย
และก็เช่นเดียวกับโทรศัพท์มือถือ ตัวอย่างเช่นในการค้นหาหนังสือไบนารี
มากขึ้นโดยทั่วไป
แต่เรากำลังดำเนินการนั้น ตอนนี้เล็ก ๆ น้อย ๆ แบบไดนามิก
กว่าอาร์เรย์อาจอนุญาตให้
และในความเป็นจริงถ้าคุณต้องการดู รหัสที่ได้อย่างรวดเร็วก่อนว่า
ดูเหมือนว่าทั้งกลุ่มของเส้น
แต่มันง่ายอย่างสวยงาม
ถ้าคุณต้องการที่จะใช้ฟังก์ชั่น ที่เรียกว่าการค้นหาที่มีจุดมุ่งหมายในชีวิต
คือการค้นหาค่า เช่น n, จำนวนเต็ม
และคุณผ่านในหนึ่ง pointer-- ตัวชี้ไปยังโหนดราก,
ค่อนข้างของต้นไม้ที่จากการที่ คุณสามารถเข้าถึงได้ทุกอย่างอื่น
แจ้งให้ทราบว่าตรงไปตรงมา คุณสามารถใช้ตรรกะ
ถ้าต้นไม้เป็น null เห็นได้ชัดว่ายังไม่ได้มี
ขอเพียงกลับเท็จ
ใช่มั้ย?
ถ้าคุณส่งมันไม่มีอะไร ไม่มีอะไรที่นั่น
>> มิฉะนั้นถ้า n มีค่าน้อยกว่า ลูกศรต้นไม้ n-- ตอน arrow n,
จำเราได้นำเสนอซุปเปอร์ ในเวลาสั้น ๆ ในวันอื่น ๆ
และนั่นก็หมายความว่าเดอ้างอิง ตัวชี้และดูที่เขตข้อมูลที่เรียกว่า n
ดังนั้นจึงหมายความว่าไปที่นั่นและ ดูข้อมูลที่เรียกว่า n
ดังนั้นถ้า n ค่าคุณได้รับจะน้อย กว่ามูลค่าในจำนวนเต็มต้นไม้
ที่คุณต้องการที่จะไป?
ไปทางซ้าย
>> เพื่อแจ้งให้ทราบล่วงหน้าเรียกซ้ำ
ฉัน returning-- ไม่เป็นความจริง
ไม่เท็จ
ฉันกลับมาสิ่งที่คำตอบ เป็นจากการเรียกตัวเองผ่าน
n อีกครั้งซึ่งเป็นซ้ำซ้อน แต่เป็นสิ่งที่แตกต่างกันเล็กน้อยในตอนนี้?
ฉันทำให้ปัญหาวิธีเล็ก?
ฉันผ่านในขณะที่สอง อาร์กิวเมนต์ไม่ใช่รากของต้นไม้
แต่เด็กซ้ายในกรณีนี้
ดังนั้นฉันผ่านในเด็กซ้าย
>> ในขณะเดียวกันถ้า n มีขนาดใหญ่กว่า โหนดฉันกำลังมองหาที่
ฉันค้นหาด้านขวามือ
มิฉะนั้นถ้าต้นไม้ไม่เป็นโมฆะและ ถ้าองค์ประกอบไม่ไปทางซ้าย
และก็ไม่ไปทางขวา สิ่งที่น่าพิศวงกรณี?
เราได้พบจริงโหนดใน คำถามและเพื่อให้เรากลับจริง
>> ดังนั้นเราจึงได้เพียงแค่รอยขีดข่วนบนพื้นผิว ตอนนี้บางส่วนของโครงสร้างข้อมูลเหล่านี้
ในปัญหาการตั้งห้าคุณจะ สำรวจเหล่านี้ยังเพิ่มเติม
และคุณจะได้รับการออกแบบของคุณ ทางเลือกของวิธีการไปเกี่ยวกับเรื่องนี้
สิ่งที่ผมอยากจะสรุปได้ใน เป็นเพียง 30 ทีเซอร์ที่สอง
ของสิ่งที่รอคอยในสัปดาห์หน้าและอื่น ๆ
>> ในขณะที่เรา begin-- ขอบคุณคุณอาจ think-- การเปลี่ยนแปลงของเราอย่างช้าๆ
จากโลกของ C และล่าง รายละเอียดการปฏิบัติระดับ
กับโลกที่เราสามารถใช้สำหรับ รับว่าคนอื่นมีในที่สุด
ใช้ข้อมูลเหล่านี้ โครงสร้างสำหรับเรา
และเราจะเริ่มต้นที่จะเข้าใจ โลกแห่งความจริงหมายความว่าในการดำเนินการ
โปรแกรมบนเว็บและ เว็บไซต์มากขึ้นโดยทั่วไป
และนอกจากนี้ยังมีการรักษาความปลอดภัยมาก ผลกระทบที่เราได้เท่านั้น
เริ่มที่จะมีรอยขีดข่วนพื้นผิวของ
นี่คือสิ่งที่รอเรา ต่อนี้ไป
>> [การเล่นวิดีโอ]
>> พระองค์จึงมาพร้อมกับข้อความ กับโปรโตคอลทั้งหมดของเขาเอง
เขามาถึงโลกของโหดร้าย ไฟร์วอลล์เราเตอร์ไม่สนใจ,
และอันตรายที่ไกลยิ่งกว่าความตาย
เขาเป็นอย่างรวดเร็ว
เขาเป็นคนที่แข็งแกร่ง
เขาเป็น TCP / IP และเขาก็มีที่อยู่ของคุณ
"นักรบแห่งสุทธิ."
[จบการเล่นวิดีโอ]
DAVID ลัน: มาในสัปดาห์หน้า
เราจะเห็นคุณแล้ว
[การเล่นวิดีโอ]
ในอนาคตและตอนนี้ "คิดลึก" โดย Daven อัม
เดวิดเสมอเริ่มต้น บรรยายกับ "สิทธิทั้งหมด."
ทำไมไม่ "นี่คือการแก้ปัญหา เพื่อแก้ไขปัญหาในสัปดาห์นี้ชุด "
หรือ "เรากำลังให้ทุกท่าน"
[หัวเราะ]
[จบการเล่นวิดีโอ]