>> DAVID ลัน: ทั้งหมดขวา
ยินดีต้อนรับกลับไป CS50
นี่คือจุดเริ่มต้นของสัปดาห์ที่ 8
และจำชุดปัญหาที่สิ้นสุดวันที่ 5 กับเล็กน้อยของความท้าทาย
ดังนั้นสมมติว่าคุณกู้คืนทั้งหมดของคุณ Fellows การเรียนการสอนและรูปถ่ายของ CA
ในแฟ้ม card.raw, คุณมีสิทธิ์ ถึงตอนนี้ค้นหาทั้งหมดของคนเหล่านั้นและ
หนึ่งในผู้โชคดีจะเดินกลับบ้านด้วย สิ่งเหล่านี้เคลื่อนไหวก้าวกระโดด
อุปกรณ์ที่คุณสามารถใช้สำหรับสุดท้าย โครงการตัวอย่างเช่น
>> นี้ทุกปีจะนำไปสู่ บิตของความน่าขยะแขยง
และดังนั้นสิ่งที่ฉันคิดว่าฉันควรจะทำร่วมกันคือ กับคุณบางส่วนของบันทึกที่มี
ไปและกลับออกไป รายการพนักงานของสาย
ตัวอย่างเช่นเพียงแค่คืนที่ผ่านมาอ้าง ไม่ได้นำมาอ้างจากหนึ่งของพนักงาน
สมาชิก, "ฉันเพิ่งมีการเคาะนักเรียน ประตูของฉันไปถ่ายรูปกับผม
Stalkers ผมบอกคุณ. "เริ่มออก ธรรมบรรยายและจากนั้นเราก็ย้าย
เมื่อถึงชั่วโมงหรือดังนั้นต่อมา "ผมมี นักเรียนรอฉันหลังจากที่ส่วน
และเขาก็มีทั้งหมดของชื่อและภาพถ่ายของเรา เมื่อแผ่นบางของกระดาษ. "ทุกขวา
ดังนั้นการจัดระเบียบ แต่ไม่ ทั้งหมดที่ยังน่าขนลุก
>> จากนั้น "ฉันออกไปจากเมืองวันหยุดสุดสัปดาห์นี้ และเมื่อฉันได้กลับมามีเป็นหนึ่งใน
ของฉัน
ห้องนอน. "[เสียงหัวเราะ]
DAVID ลัน: อ้างถัดไปจากเจ้าหน้าที่ ของสมาชิก "นักเรียนมาที่บ้านของฉันที่
ซอเมอร์ที่ 04:00 เช้านี้. เลือก "Next พนักงาน "ผมได้ไปที่โรงแรมของฉันในซาน
ฟรานซิสและนักเรียนกำลังรอ เราได้ที่ล็อบบี้กับสาม DSLRs. "
ประเภทของกล้อง
"ผมไม่ได้อยู่ในทีมงานภาคการศึกษานี้ แต่นักเรียนบุกเข้าไปในบ้านของฉัน
ตอนเช้าและบันทึกสิ่งที่ทั้ง กับแก้ว Google. "และแล้วในที่สุด
"อย่างน้อย 12 คนกระหาย รอสำหรับฉันเมื่อฉันได้ออกจากฉัน
รถลีมูซีนและแล้วฉัน
ตื่นขึ้นมา. "ทุกขวา
ดังนั้นระหว่างการถ่ายภาพตามที่คุณอาจ จำคนนี้อยู่ที่นี่ที่คุณ
อาจจะรู้ว่าเป็นไมโลกล้วยที่มีชีวิตอยู่ กับลอเรนวัลโญ่หัวของเรา
เพื่อนการเรียนการสอน
ไมโลไมโลมาที่นี่เด็ก
ไมโล
ใจคุณเขาสวมใส่ Google แก้วดังนั้น เราจะแสดงให้คุณทั้งหมดนี้หลังจาก
ดังนั้นนี่คือไมโลถ้าคุณต้องการที่จะ ถ่ายรูปกับเขาหลังจากนั้น
หากคุณต้องการที่จะดูออก ที่ผู้ชมมี
ตกลง
นั่นเป็นภาพที่ดี
ดีกล้วยไมโล
โอ้ไม่ทำอย่างนั้น
>> [เสียงหัวเราะ]
>> ตกลง
ดังนั้นคำแล้วกับสิ่งที่อยู่ข้างหน้า เพราะในขณะที่เราเริ่มต้นที่จะเปลี่ยนแปลง
สัปดาห์โดยเฉพาะจาก C ในนี้ สภาพแวดล้อมที่บรรทัดคำสั่งเพื่อ PHP และ
JavaScript และ SQL และ HTML และ CSS ใน สภาพแวดล้อมบนเว็บเราจะ
เตรียมให้คุณกับ ความรู้ที่มากขึ้นสำหรับ
โครงการสุดท้ายที่มีศักยภาพ
ไปยังจุดสิ้นสุดที่แน่นอนมี ประเพณีของผู้ถือหุ้นซึ่งการสัมมนา
เป็นหัวข้อที่วง เพื่อการเรียนการสอน
ที่เกี่ยวข้องเป็นอย่างมากในการเขียนโปรแกรมและการ การพัฒนา App และอื่น ๆ แต่
ไม่จำเป็นต้องสำรวจโดย หลักสูตรของตัวเองของหลักสูตร
>> ดังนั้นหากคุณอาจจะสนใจในการอย่างใดอย่างหนึ่ง หรือมากกว่าของการสัมมนาในปีนี้
ลงทะเบียนที่ cs50.net/seminar
มีการจัดสัมมนาเก่า ที่ cs50.net/seminars
และบัญชีรายชื่อป่านนี้ปีนี้ ซอฟแวร์เว็บที่น่าตื่นตาตื่นใจกับทับทิมอยู่บน
ทางรถไฟซึ่งเป็นทางเลือก ภาษา PHP
ภาษาศาสตร์
รู้เบื้องต้นเกี่ยวกับ iOS ซึ่งเป็น แพลตฟอร์มที่ใช้สำหรับ iPhone และ
การพัฒนา iPad
JavaScript สำหรับ Web Apps ของเราจะครอบคลุม แต่ในการสัมมนาครั้งนี้คุณจะไป
มีรายละเอียดเพิ่มเติม
>> Leap เคลื่อนไหวดังนั้นเราจริงจะมีบางส่วน เพื่อนของเราจากภาพยนตร์ Leap,
บริษัท ของตัวเองเข้าร่วมกับเรา
พรุ่งนี้ในความเป็นจริงเพื่อให้ มือบนสัมมนาถ้า
ที่สนใจของคุณ
Meteor.js, เทคนิคทางเลือกสำหรับ ใช้ JavaScript ไม่ได้อยู่ในเบราว์เซอร์,
แต่บนเซิร์ฟเวอร์
Node.js ซึ่งเป็นอย่างมาก ในหลอดเลือดดำด้วยเช่นกันว่า
การออกแบบหุ่นยนต์รูปแบบเพรียวบาง
Android เป็นทางเลือกที่นิยมมาก ไปยังโทรศัพท์มือ iOS และ Windows
และแพลตฟอร์มมือถืออื่น ๆ
และ Web งานรักษาความปลอดภัยกลาโหม
>> ดังนั้นในความเป็นจริงถ้าคุณต้องการ จะมีส่วนร่วมในเรื่องนี้ให้ฉัน
ให้จดบันทึกนี้
เรามีความสุขมากที่จะบอกว่า เพื่อนของเราที่ก้าวกระโดด
การเคลื่อนไหวซึ่งเป็นการเริ่มต้น -
อุปกรณ์นี้จริงๆเพียงแค่เข้ามา ออกไม่กี่เดือนที่ผ่านมา -
ได้บริจาคพระกรุณ​​าโปรดเกล้าฯ 30 อุปกรณ์ดังกล่าว ในชั้นเรียนเพื่อเป็นนักเรียนหลายคนถ้า
คุณต้องการยืมฮาร์ดแวร์ ไปยังจุดสิ้นสุดภาคการศึกษาและใช้งานได้
โครงการสุดท้ายที่เกิดขึ้นจริง
พวกเขาสนับสนุนหลายภาษา
ไม่มีพวกเขา C ไม่มีของพวกเขา PHP ดังนั้น ตระหนักถึงหนึ่งหรือมากกว่าหนึ่งของการสัมมนาเหล่านี้
อาจพิสูจน์ที่น่าสนใจ
และทั้งหมดของพวกเขาจะได้รับการถ่ายทำใน กรณีที่คุณไม่สามารถ
ที่จะเข้าร่วมในบุคคล
ตารางเวลาการประกาศผ่านทาง อีเมล์ที่เราแข็งห้องพัก
>> และสุดท้ายถ้าคุณไปที่ projects.cs.50.net นี้เป็นเว็บไซต์
เรารักษาในแต่ละปีที่เราเชิญ folks จากชุมชนของอาจารย์
แผนกพนักงานและทั้งสอง ในด้านนอกของ CS50 ไป
เสนอความคิดโครงการ
กิจกรรมที่น่าสนใจให้กับกลุ่มนักเรียน
สถานที่น่าสนใจให้กับหน่วยงาน
ดังนั้นจะเปิดมีถ้าคุณกำลังดิ้นรน ที่มีความไม่แน่นอนเป็นสิ่งที่คุณ
ตัวเองต้องการที่จะแก้ไขปัญหา
>> ดังนั้นครั้งสุดท้ายที่เรานำเนื้อหา โครงสร้างข้อมูลที่ซับซ้อนมากขึ้นกว่าที่เราต้องการ
มองเห็นได้ในสัปดาห์ที่ผ่านมา
เราต้องการได้รับการใช้อาร์เรย์สวย อย่างมีความสุขเป็นประโยชน์ในกรณีที่
โครงสร้างข้อมูลแบบง่ายๆ
จากนั้นเราก็นำเหล่านี้ซึ่ง แน่นอนมีการเชื่อมโยงรายการ
และสิ่งที่เป็นหนึ่งในแรงจูงใจสำหรับ การแนะนำนี้โครงสร้างข้อมูล?
อ้าง?
ว่าคืออะไร?
>> ผู้ชม: Dynamic ขนาด
>> DAVID ลัน: Dynamic ขนาด
ดังนั้นในขณะที่อยู่ในอาร์เรย์คุณต้อง ทราบขนาดล่วงหน้าเมื่อมัน
คุณจัดสรรมัน
ในรายการการเชื่อมโยงที่คุณทำไม่ได้ ต้องรู้ว่า
คุณสามารถ malloc เพียงหรือมากกว่าปกติ จัดสรรเพิ่มเติม
โหนดเพื่อที่จะพูดทุกครั้งที่คุณใด ๆ ต้องการแทรกข้อมูลได้มากขึ้น
และโหนดได้กำหนดไว้ไม่มีความหมาย
มันก็แค่เป็นคำทั่วไปที่อธิบาย บางชนิดของภาชนะว่าเรา
ใช้ในโครงสร้างข้อมูลของเราในการจัดเก็บ รายการที่น่าสนใจบางอย่างซึ่งในเรื่องนี้
กรณีที่เกิดขึ้นจะเป็นจำนวนเต็ม
>> แต่มีเสมอ tradeoff
ดังนั้นเราจึงได้รับขนาดของข้อมูลแบบไดนามิก โครงสร้าง แต่สิ่งที่ราคาที่เราจ่ายเงิน
ข้อเสียของรายการที่เชื่อมโยงคืออะไร?
อ้าง?
>> ผู้ชม: ต้องหน่วยความจำเพิ่มเติม
>> DAVID ลัน: มันต้องมีมากขึ้น หน่วยความจำวิธีการว่า?
>> ผู้ชม: [ได้ยิน]
>> DAVID ลัน: ว่า
ดังนั้นตอนนี้เรามีตัวชี้การขึ้น หน่วยความจำเพิ่มเติมที่เราก่อนหน้านี้
ไม่จำเป็นเพราะความได้เปรียบ ของอาร์เรย์ของหลักสูตรคือ
ทุกอย่างที่ต่อเนื่องกันกลับ ที่จะกลับไปทางด้านหลังซึ่ง
จะช่วยให้คุณเข้าถึงโดยสุ่ม
เพราะเพียงโดยใช้วงเล็บเหลี่ยม ตัวชี้สัญกรณ์หรือมากกว่าในทางเทคนิค
คณิตศาสตร์นอกจากนี้ง่ายมาก คุณสามารถเข้าถึงใด ๆ
องค์ประกอบในเวลาคง
และในความเป็นจริงที่ว่าชนิดของเค้า ราคาที่เราจ่ายเงินให้กับคนอื่น
รายการที่เชื่อมโยง
>> ที่เกิดขึ้นกับเวลาทำงานของอะไร สิ่งที่ต้องการค้นหาถ้าฉันต้องการ
หาค่าบางและภายใน ของรายการที่เชื่อมโยง?
เวลาการทำงานของฉันจะกลายเป็นอะไร?
O ใหญ่ของ n
ถ้ามันจัดเรียง?
เกิดอะไรขึ้นถ้าโครงสร้างข้อมูลที่เรียง?
ผมสามารถทำได้ดีกว่าขนาดใหญ่ ของ O n สำหรับการค้นหา
ไม่มีเพราะในกรณีที่เลวร้ายที่สุดก็อาจ เป็นอย่างดีและสามารถจัดเรียง แต่จำนวน
คุณกำลังมองหาอาจจะมีขนาดใหญ่
มันอาจจะมีจำนวน 100 ซึ่ง อาจจะเกิดขึ้นทั้งหมด
วิธีที่สิ้นสุด
และเนื่องจากคุณจะสามารถเข้าถึงการเชื่อมโยง รายการในการดำเนินการนี​​้โดย
วิธีการของโหนดแรกของคุณ ชนิดยังคงออกจากโชค
คุณจะต้องเข้าไปในสิ่งที่ทั้ง ตั้งแต่แรกที่จะผ่านมาเพื่อหาสิ่งที่
ว่าค่าขนาดใหญ่เช่น 100
หรือตรวจสอบว่าเป็น ไม่ได้มี
>> ดังนั้นเราจึงไม่สามารถทำในสิ่งที่อัลกอริทึมในข้อมูล โครงสร้างที่มีลักษณะเช่นนี้หรือไม่
เราไม่สามารถทำการค้นหาแบบไบนารีเพราะ การค้นหาแบบไบนารีจำเป็นที่เรามี
เข้าถึงโดยสุ่ม
เราก็สามารถกระโดดจากที่ตั้งไป สถานที่โดยไม่ต้องปฏิบัติตาม
เหล่านี้ขนมปังในรูปแบบ ของตัวชี้เหล่านี้ทั้งหมด
>> ตอนนี้เราไม่ใช้วิธีนี้
ดีถ้าเราไปที่หน้าจอนี่ถ้า เราได้อย่างรวดเร็วสามารถ reimplement ข้อมูลนี้
โครงสร้าง -
เขียนด้วยลายมือของฉันไม่ทั้งหมดที่ ดีที่นี่ แต่เราจะพยายาม
typedef struct ดังนั้นและสิ่งที่ไม่ฉัน ต้องการที่จะเรียกสิ่งนี้ขึ้นที่นี่?
ตุ่ม
ดังนั้นผมจึงจะได้รับเราเริ่ม
และตอนนี้จำเป็นต้องอยู่ภายในของสิ่งที่ โครงสร้างข้อมูลสำหรับลำพังว่า
เชื่อมโยงรายการ?
วิธีการหลายสาขา?
>> ดังนั้นสอง
หนึ่งเป็นเรื่องง่ายสวย
int ดังนั้น n
และเราสามารถเรียกสิ่งที่ n ที่เราต้องการ แต่ควรจะ int ถ้าเรา
การดำเนินการรายการที่เชื่อมโยงสำหรับ ints
และตอนนี้ไม่สองสิ่ง สนามจะต้องมี?
struct โหนด *
ดังนั้นถ้าฉันทำโหนด struct * และแล้วฉัน สามารถโทรนี้สิ่งที่ฉันต้องการ,
แต่เพียงเพื่อให้มีความชัดเจนฉันจะเรียก มันต่อไปในขณะที่เราได้รับการทำ
และแล้วฉันจะปิดวงเล็บปีกกาของฉัน
>> และตอนนี้เป็นเวลาที่ผ่านมา ฉันใส่โหนดลงที่นี่
แต่ถ้าฉันประกาศนี้เป็น โหนดผมไม่รำคาญเป็นดังนั้นทำไม
verbose ที่นี่ในประกาศ struct โหนดต่อไปเมื่อเทียบกับ
เพียง * โหนดต่อไปหรือไม่
อ้าง?
>> ผู้ชม: [ได้ยิน]
>> DAVID ลัน: ว่า
อย่างแน่นอน
C เพราะจริงๆจะคุณอย่างแท้จริงและ เพียง แต่เห็นความหมายของโหนด
ทางลงที่นี่คุณจะไม่สามารถ หมายถึงมันขึ้นมาที่นี่
ดังนั้นเราจึงมีการจัดเรียงของมาตรการนี​​้ ประกาศที่นี่ซึ่งเป็นที่ยอมรับ
verbose เพิ่มเติม
struct โหนดนั่นหมายความว่า ตอนนี้เราสามารถเข้าถึงได้
ภายในของโครงสร้างข้อมูล
>> และเป็นกันเพราะนี้เป็น กลายเป็นเล็ก ๆ น้อย ๆ ส่วนตัวมากกว่าตอนนี้
ดาวในทางเทคนิคสามารถไปที่นี่ ที่จะสามารถไปที่นี่ก็สามารถ
ได้ไปอยู่ตรงกลาง
เราได้นำมาใช้ในรูปแบบคู่มือสำหรับ การเรียนการสอนการประชุมของการวาง
ดาวทางขวาถัดจากข้อมูล ประเภทซึ่งในกรณีนี้
จะเป็นโหนด struct
แต่ตระหนักในหลายตำราและ อ้างอิงออนไลน์คุณอาจแน่นอน
เห็นมันในด้านอื่น ๆ
แต่ก็ตระหนักดีว่าทั้งสองจะจริง การทำงานและคุณก็ควรจะเป็น
คงเส้นคงวา
>> ทั้งหมดขวา
เพื่อให้การประกาศของเรา ของโหนด struct
แต่แล้วเราเริ่มต้นการทำมากขึ้น สิ่งที่มีความซับซ้อน
ตัวอย่างเช่นเราตัดสินใจที่จะนำ สิ่งที่ต้องการตารางแฮช
ดังนั้นที่นี่ของตารางแฮชขนาด n คือ การจัดทำดัชนีจาก 0 ด้านบนซ้ายถึง n
ลบ 1 ที่ด้านล่างซ้าย
ซึ่งอาจเป็นกัญชา ตารางอะไร
แต่สิ่งที่เราไม่ชนิดของสิ่งที่พูดคุย เกี่ยวกับการใช้ตารางแฮชหรือไม่?
การจัดเก็บอะไร
>> ชื่อ
เราสามารถทำอะไรได้ชื่อเช่น ที่เราทำครั้งสุดท้าย
และจริงๆคุณสามารถเก็บสิ่งใด
และเราจะเห็นสิ่งนี้อีกครั้งใน PHP และใน JavaScript
ตารางแฮชเป็นประเภทที่ดีของสวิส มีดทหารที่ช่วยให้คุณในการจัดเก็บ
สวยมากสิ่งที่คุณต้องการภายในของ มันโดยการเชื่อมโยงคีย์ที่มีค่า
คีย์ที่มีค่า
>> ขณะนี้ในกรณีแบบนี้ของเรา คีย์เป็นเพียงตัวเลข
เรากำลังดำเนินการกัญชา ตารางเป็นแถว
และเพื่อให้คีย์เป็น 0, 1, 2, และอื่น ๆ
และเพื่อให้เราเป็นมนุษย์ตัดสินใจล่าสุด สัปดาห์นี้คุณรู้ว่าถ้าเราไม่
ไปชื่อร้านให้เพียง โดยพลการ แต่สวยพอสมควร
สมมติว่าอลิซ, ชื่อ, จะเพิ่งจะจัดทำดัชนีเป็น 0
และ Bob ชื่อ B, จะได้รับการจัดทำดัชนี เป็น 1 และอื่น ๆ
ดังนั้นเราจึงมีการทำแผนที่ระหว่างปัจจัยการผลิต, ซึ่งเป็นสตริงและกัญชา
สถานที่ที่เป็นตัวเลข
>> ดังนั้นกระบวนการที่เป็นที่รู้จักกันโดยทั่วไปว่า ฟังก์ชันแฮชและคุณสามารถอย่างแท้จริง
ใช้มันในรหัส
ถ้าผมต้องการที่จะใช้ฟังก์ชันแฮช ที่ไม่ตรงกับสิ่งที่เรา
เพียงแค่อธิบายจากครั้งสุดท้ายที่ฉันอาจ ประกาศฟังก์ชันที่ใช้เป็น
อินพุทเช่น -
และขอทำเช่นนี้เกี่ยวกับเรื่องนี้ หน้าจอกว่าที่นี่
ถ้าผมต้องการที่จะใช้กัญชา ฟังก์ชั่นผมอาจจะบอกว่า
บางอย่างเช่นนี้
>> มันจะกลับ int
มันจะถูกเรียกว่ากัญชาและก็ จะไปรับเป็นอาร์กิวเมนต์
สตริงหรือเราสามารถที่เหมาะสมขึ้นในขณะนี้, และพูดว่า char * เราจะเรียกมัน
และแล้วสิ่งที่ฟังก์ชั่นนี้จะทำอย่างไร, ในท้ายที่สุดก็จะกลับ int
ตอนนี้มันไม่ที่อาจ ไม่ได้มีความชัดเจนดังนั้น
ฉันจะดำเนินการนี​​้โดยไม่ต้องมี รูปแบบของการตรวจสอบข้อผิดพลาดได้ในขณะนี้
ฉันแค่จะไปสุ่มสี่สุ่มห้าพูดกลับ สิ่งที่อยู่ในวงเล็บ s 0, ลบ,
สมมติว่าเป็นเมืองหลวงอัฒภาค
>> เสียโดยสิ้นเชิง
มันไม่สมบูรณ์เพราะ หนึ่งถ้าสิ่งที่เป็นโมฆะ?
สิ่งเลวร้ายที่กำลังจะเกิดขึ้น
สองสิ่งที่ถ้าตัวอักษรตัวแรกในเรื่องนี้ ชื่อไม่ได้เป็นตัวอักษร?
ที่ไม่ได้ไปเปิด ออกมาได้ดีอย่างใดอย่างหนึ่ง
มันอาจจะเป็นอักษรตัวพิมพ์เล็ก หรือไม่ตัวอักษรที่
ห้องพักทั้งหมดดังนั้นสำหรับการปรับปรุงที่นี่ แต่นี้เป็นแนวคิดพื้นฐาน
>> สิ่งที่เราอธิบายสัปดาห์สุดท้ายด้วยวาจาเป็น เพียงกระบวนการของการทำแผนที่อลิซ
และบ๊อบ 0 ถึง 1 สามารถแสดง แน่นอนมาก formulaically เป็น C
ทำงานที่นี่
ที่เรียกว่ากัญชาอีกครั้งใช้เวลาเป็นสตริง การป้อนข้อมูลและจากนั้นก็ไม่มีอะไร
กับข้อมูลการผลิตการส่งออกที่
ไม่แตกต่างจากคำอธิบายของเรากล่องสีดำ ที่เราได้ทำมานาน
ผมไม่ทราบว่าวิธีการนี​​้อาจจะมี ทำงานภายใต้ประทุน
>> สำหรับปัญหาชุดที่ 6 หนึ่งในความท้าทาย สำหรับคุณที่จะตัดสินใจว่า
ฟังก์ชันแฮชของคุณจะเป็นอย่างไร
สิ่งที่จะเป็นด้านในของสีดำที่ กล่องและสันนิษฐานว่ามันจะ
เล็ก ๆ น้อย ๆ ที่น่าสนใจกว่านี้และ แน่นอนมากขึ้นมีแนวโน้มที่จะเกิดข้อผิดพลาด
การตรวจสอบกว่านี้โดยเฉพาะ การดำเนินงาน
>> แต่ปัญหาจะเกิดขึ้นใช่มั้ย?
ถ้าเรามีโครงสร้างข้อมูลเช่นนี้ หนึ่งสิ่งที่หนึ่งของปัญหา
คุณสามารถเรียกใช้ในช่วงเวลาที่คุณใส่ ชื่อมากขึ้นใน
ตารางแฮช?
คุณจะได้รับการชนกันใช่มั้ย?
เกิดอะไรขึ้นถ้าคุณมีอลิซและแอรอน คนสองคนที่มีรายชื่อที่เกิดขึ้น
จะเริ่มต้นด้วย?
ที่ begs คำถามที่คุณ ใส่ชื่อที่สองเช่น?
>> ดีคุณอาจจะไร้เดียงสาเพียงแค่ใส่มัน ที่บ๊อบเป็น แต่แล้วบ๊อบคือ
เมาชนิดของถ้าคุณพยายามที่จะ ใส่ชื่อของเขาต่อไปและ
มีห้องพักสำหรับเขาไม่ได้
ดังนั้นคุณอาจใส่บ๊อบที่ชาร์ลี, และคุณสามารถจินตนาการนี​​้ได้อย่างรวดเร็ว
จุติเป็นบิตของระเบียบ
บางสิ่งบางอย่างเชิงเส้นในท้ายที่สุดที่คุณ เพียงแค่ต้องค้นหาสิ่งที่ทั้ง
กำลังมองหาอลิซหรือบ๊อบ หรือแอรอนหรือชาร์ลี
>> ดังนั้นแทนที่จะเราเสนอแทนเพียง เป็นเส้นตรงละเอียดสำหรับการเปิดช่องว่าง
และ plopping ชื่อนั่นเรา เสนอวิธีการที่นักเล่น
ตารางแฮชยังคงดำเนินการด้วย อาร์เรย์ของดัชนี แต่ชนิดข้อมูลของ
ดัชนีเหล่านี้เป็นตัวชี้
ตัวชี้กับสิ่งที่?
ตัวชี้ไปยังการเชื่อมโยงรายการ
>> เพราะจำได้ว่าเป็นรายการที่เชื่อมโยง จริงๆเพียงแค่ชี้ไปยังโหนดและ
โหนดที่มีเขตข้อมูลถัดไปและโหนดที่ มีเขตข้อมูลถัดไปและอื่น ๆ
ดังนั้นตอนนี้คุณสามารถคิดของอาร์เรย์นี้ ด้านซ้ายมือของตารางแฮชเป็น
นำไปสู่​​การเชื่อมโยงรายชื่อ
ข้อได้เปรียบที่เป็นถ้าคุณได้รับ การปะทะกันระหว่างอลิซและแอรอน
สิ่งที่คุณทำกับ บุคคลดังกล่าวที่สอง?
คุณเพียงแค่แนบให้เขาหรือเธอ ปลายหรือแม้กระทั่งการเริ่มต้น
ของรายการที่เชื่อมโยงว่า
>> และที่จริงให้เพียงบะหมี่กึ่งผ่าน ที่เพียงสอง
ที่จะทำให้ความรู้สึกมากที่สุด
ถ้าผมใส่อลิซและเธอจบลงด้วยการที่ สถานที่แรกแล้วฉันพยายามที่จะ
ใส่ชื่อของแอรอนและมี เห็นได้ชัดว่าการปะทะกัน, ฉันควรวาง
เขาที่จุดเริ่มต้น ของรายการที่เชื่อมโยง?
นั่นเป็นสถานที่แรกที่ หรือที่ส่วนท้าย?
>> ผู้ชม: [ได้ยิน]
>> DAVID ลัน: ตกลง
ผมได้ยินมาว่าการเริ่มต้น
ที่จุดเริ่มต้นทำไม?
>> ผู้ชม: [ได้ยิน]
>> DAVID ลัน: ตกลง
มันเรียงตามตัวอักษรเพื่อที่ว่าดี
นั่นเป็นสถานที่ให้บริการที่ดี
มันจะช่วยฉันเวลาที่อาจเกิดขึ้นบางส่วน
มันจะไม่ยอมให้ฉันทำค้นหา binary แต่ฉัน อย่างน้อยอาจจะไม่สามารถที่จะแยกออก
ของวงถ้าฉันรู้ดีว่าฉันวิธี อดีตที่ผ่านมามีแอรอนจะอยู่ในนี้
รายการที่เชื่อมโยงเรียง
ผมจะได้ไม่ต้องเสียเวลาของฉันกำลังมองหา ไปตลอดทางจนถึงปลาย
ดังนั้นที่ที่เหมาะสม
ทำไมอื่นคุณอาจต้องการที่จะแทรก ชื่อชนกันที่
จุดเริ่มต้นของรายการ?
ว่าคืออะไร?
>> ผู้ชม: [ได้ยิน]
>> DAVID ลัน: มันอาจจะใช้เวลานาน เพื่อไปยังจุดสิ้นสุดของรายการ
และในความเป็นจริงอีกต่อไปและอีกต่อไป
ชื่ออื่น ๆ ที่คุณใส่ว่า เริ่มต้นด้วยอีกต่อไปว่า
ห่วงโซ่เป็นไปได้
อีกต่อไปแล้วว่าการเชื่อมโยง รายการเป็นไปได้
ดังนั้นคุณจริงๆเพียงแค่ เสียเวลาของคุณ
บางทีคุณอาจจะดีกว่าการรักษา เวลาแทรกคง O ใหญ่ 1,
เสมอโดยการใส่ชื่อที่ชน จุดเริ่มต้นของรายการที่เชื่อมโยง,
และไม่ต้องกังวลมาก เกี่ยวกับการเรียงลำดับ
>> คำตอบที่ดีที่สุดคืออะไร?
มันไม่ชัดเจน
ชนิดของมันขึ้นอยู่กับสิ่ง การกระจายคือสิ่งที่รูปแบบคือ
ชื่อที่คุณใส่
มันไม่จำเป็นต้อง คำตอบที่ชัดเจน
แต่ที่นี่ไปอีกครั้งคือ โอกาสที่การออกแบบ
>> ดังนั้นเราจึงมองไปที่สิ่งนี้ซึ่ง เป็นจริงโอกาสที่ขนาดใหญ่อื่น ๆ
สำหรับ p-6 ชุด
และตระหนักถึงถ้าคุณยังไม่ได้ ดำผุดดำว่า Zamyla ลงทั้งสองคนนี้, กัญชา
ตารางและพยายามในรายละเอียดมากขึ้น
และคำแนะนำแบบวิดีโอเป็น ที่ฝังอยู่ใน p-ชุด spec
นี่เป็นคู่ชีวิต -
T-R-I-E และสิ่งที่เป็นที่น่าสนใจเกี่ยวกับ นี้คือการที่เวลาทำงาน
ของการค้นหาสำหรับชื่อเช่นแมกซ์เวล ครั้งสุดท้ายที่เป็น O ใหญ่ของอะไร
ว่าคืออะไร?
>> ผู้ชม: จำนวนตัวอักษร
>> DAVID ลัน: หมายเลขของตัวอักษร
ผมได้ยินมาว่าสองสิ่ง
จำนวนของตัวอักษรและเวลาคง
ดังนั้นขอไปก่อนว่า
จำนวนตัวอักษร
ดีนี้โครงสร้างข้อมูลการเรียกคืนคือ ชอบต้นไม้ต้นไม้ครอบครัวแต่ละ
โหนดที่มีการสร้างขึ้นจากอาร์เรย์
และอาร์เรย์ที่เป็นตัวชี้ไปยัง โหนดดังกล่าวอื่น ๆ หรืออื่น ๆ เช่น
อาร์เรย์ในต้นไม้
>> ดังนั้นหากเราต้องการที่จะตรวจสอบแล้ว ไม่ว่าจะเป็นแม็กซ์อยู่ในที่นี่ผมอาจจะไป
ไปยังแถวแรกที่ส่วนบนสุดของ ต้นไม้, รากที่เรียกว่าด้านบนของ
Trie แล้วทำตามตัวชี้เมตร แล้วตัวชี้แล้ว x,
W, E, l, l
และจากนั้นเมื่อฉันเห็นบางสัญลักษณ์พิเศษ แสดงที่นี่เป็นรูปสามเหลี่ยม
ในรหัสของคุณจะเห็นเรานำเสนอให้คุณ นำมาใช้เป็น bool เพียงแค่บอกว่าใช่
หรือไม่มีคำว่าหยุดที่นี่
>> ดีเมื่อเราไป M--X-W-E-L-L, รู้สึกเหมือนเจ็ด, บางที
แปดถ้าเราไปหนึ่งอดีตที่ผ่านมามันแปด ขั้นตอนในการหาแมกซ์เวล
หรือขอเรียกว่าเค แต่จำล่าสุด เวลาที่ฉันถกเถียงกันอยู่ว่าถ้ามี
แนบเนียนยาวสูงสุดเมื่อ คำเช่นตัวอักษร 40 บางแปลก,
ความยาวสูงสุดถึง ค่าคงที่
ดังนั้นจริงๆใช่มันใหญ่เทคนิค O จาก 8 หรือ 7 หรือใหญ่จริงๆโอเค แต่
ถ้ามีฝา จำกัด ในสิ่งที่ K อาจจะเป็นค่าคงที่
และดังนั้นจึง O ใหญ่ของ 1 อยู่ที่ ตอนท้ายของวัน
>> ไม่ได้อยู่ในโลกแห่งความจริง
ไม่ได้เมื่อคุณจริงเริ่มต้นดู นาฬิกาของคุณในขณะที่การทำงานของโปรแกรม
มันแน่นอนจะเป็นบิต ช้ากว่าค่าคงที่อย่างแท้จริง
เวลาอยู่กับขั้นตอนที่หนึ่ง
มันเป็นไปได้เจ็ดหรือแปดขั้นตอน แต่ยังคงที่มากดีกว่ามาก
กว่าขั้นตอนวิธีเช่น O ใหญ่ของ n ที่ ขึ้นอยู่กับขนาดของสิ่งที่อยู่ใน
โครงสร้างข้อมูล
>> สังเกตคว่ำนี่คือเราสามารถแทรก ล้านชื่อขึ้นในการนี​​้
โครงสร้างข้อมูล แต่วิธีการขั้นตอนอื่น ๆ อีกมากมาย มันจะพาเราไปหา
แมกซ์เวลในกรณีที่?
ไม่
เขาเป็นคนที่ได้รับผลกระทบ
และถึงวันที่ฉันไม่คิดว่าเราได้เห็น ตัวอย่างของโครงสร้างข้อมูลหรือ
อัลกอริทึมที่ได้อย่างสมบูรณ์ รับผลกระทบจากภายนอก
พฤติกรรมเช่นเดียวกับที่
แต่เรื่องนี้ไม่สามารถเป็นที่น่าตื่นตาตื่นใจ
นี้ไม่สามารถแก้ปัญหาเฉพาะ สำหรับ p-set
>> และยังไม่ได้
นี้ไม่จำเป็นต้องข้อมูล โครงสร้างที่คุณควรจะไหลไป
เพราะเช่นตารางกัญชาแลกเปลี่ยน,
ราคาที่คุณจ่ายที่นี่คืออะไร?
หน่วยความจำ
ผมหมายถึงนี้เป็นที่เลวร้าย จำนวนหน่วยความจำ
และคุณไม่สามารถค่อนข้างเห็นได้ที่นี่เพราะ ผู้เขียนของภาพนี้
ถูกตัดทอนอย่างเห็นได้ชัดทั้งหมดของอาร์เรย์, และเราไม่เห็นจำนวนมากและ
B และ C และ Q และของ Y และ Z ในอาร์เรย์เหล่านี้
แต่พวกเขากำลังมี
>> แต่ละโหนดเหล่านี้เป็นอาร์เรย์ทั้งหมด ของบางส่วนหรือมากกว่า 26 ไบต์แต่ละ
ซึ่งหมายถึงตัวอักษร
27 ในกรณีของเราเพื่อให้เราสามารถรองรับ apostrophes ในชุดปัญหา
ดังนั้นนี่คือโครงสร้างข้อมูลที่เป็นจริง, จริงๆหนาแน่นและกว้าง
และที่อยู่คนเดียวอาจท้ายชะลอตัว สิ่งที่ลงหรืออย่างน้อยต้นทุนคุณ
พื้นที่มากขึ้น
แต่อีกครั้งที่เราสามารถวาด การเปรียบเทียบที่นี่
>> ในขณะที่การเรียกคืนกลับมาที่เราประสบความสำเร็จมาก เวลาการทำงานที่น่าตื่นเต้นมากในการเรียงลำดับ
เมื่อเราใช้ตัดจัดเรียง แต่ราคา เราจ่ายเพื่อให้บรรลุ n log n สำหรับการผสาน
จัดเรียงจำเป็นที่เราใช้จ่าย มากขึ้นทรัพยากรสิ่ง?
พื้นที่มากขึ้น
เราต้องการอาร์เรย์รอง คัดลอกคนเข้าเช่นเดียวกับ
เราได้ที่นี่บนเวที
ดังนั้นอีกครั้งไม่มีผู้ชนะที่ชัดเจน, แต่เพียงแค่การออกแบบอัตนัย
การตัดสินใจที่จะทำ
>> ทั้งหมดขวา
ดังนั้นวิธีการเกี่ยวกับเรื่องนี้?
ทุกคนรับรู้ซึ่ง D-Hall แล้วหรือยัง
ตกลง
ดังนั้นเราสามคนทำ
บ้านท้อง
ดังนั้นนี่คือสำหรับการรับประทานอาหารท้อง
ฉันจะเดิมพันทั้งหมดมีห้องอาหาร กองถาดเช่นนี้
และนี้เป็นจริงตัวแทน จากสิ่งที่เราได้
เห็นได้ชัดอยู่แล้ว
เราเรียกว่าอักษรสแต็ค
และสแต็คในแง่ของของคุณ หน่วยความจำของคอมพิวเตอร์เป็นที่ข้อมูลไป
ในขณะที่ฟังก์ชั่นที่ถูกเรียกว่า
>> ตัวอย่างเช่นสิ่งที่ชนิดของสิ่งที่ไป ในกองด้วยความเคารพ
หน่วยความจำแบบเราได้กล่าว ในสัปดาห์ที่ผ่านมา?
ว่าคืออะไร?
>> ผู้ชม: โทรไปยังฟังก์ชั่น
>> DAVID ลัน: ฉันขอโทษ
>> ผู้ชม: โทรไปยังฟังก์ชั่น
>> DAVID ลัน: โทรไปยังฟังก์ชั่น แต่ โดยเฉพาะภายในของแต่ละสิ่ง
เฟรมเหล่านั้นหรือไม่
สิ่งที่ชนิดของสิ่ง?
ใช่
ตัวแปรท้องถิ่นดังนั้น
เมื่อใดก็ตามที่เราต้องการบางจัดเก็บในท้องถิ่น, เช่นเดียวกับการโต้แย้งหรือ int i หรือ int
อุณหภูมิหรืออะไรก็ตามในประเทศ ตัวแปรคือเราได้รับ
ที่วางบน stack
และเราเรียกมันว่าสแต็คเพราะ ของความคิดที่ฝังรากลึก
เพียงแค่ชนิดของการแข่งขันขึ้นกับความเป็นจริง, แนวคิดดังกล่าว
>> แต่มันกลับกลายเป็นว่าสแต็คยังสามารถ ถูกมองว่าเป็นโครงสร้างข้อมูล,
ทางเลือกให้กับอาร์เรย์ทางเลือก ไปยังรายการที่เชื่อมโยง
สิ่งที่แนวคิดที่น่าสนใจมาก ที่ยังคงสามารถ
ดำเนินการโดยใช้อย่างใดอย่างหนึ่งของคนเหล่านั้น สิ่ง แต่มันเป็นประเภทที่แตกต่างกันของ
โครงสร้างข้อมูลสนับสนุนจริงๆ เพียงสองการดำเนินงาน
แต่คุณสามารถเพิ่มเมื่อนักเล่น คุณสมบัติเหล่านี้กว่า
แต่เหล่านี้เป็นพื้นฐาน -
ผลักดันและ pop
>> และความคิดที่มีสแต็คเป็นว่าถ้าผม มีที่นี่มีหรือไม่มี Annenberg
รู้ถาดจากประตูถัดไป ที่มีจำนวน 9 กับมัน
ดังนั้นเพียงแค่ int
และฉันต้องการที่จะผลักดันนี้ลงบนข้อมูล โครงสร้างซึ่งปัจจุบันเป็นที่ว่างเปล่า
พิจารณานี้ด้านล่างของสแต็ค
ผมจะผลักดันจำนวน 9 ชุดนี้ลง สแต็ค, และตอนนี้ก็มีสิทธิ์
>> แต่สิ่งที่น่าสนใจเกี่ยวกับสแต็ค หมายถึงว่าถ้าผมต้องการที่จะผลักดัน
บางค่าอื่น ๆ เช่น 17 และฉันผลักดัน นี้บนสแต็คที่ฉันจะทำ
สิ่งเดียวที่ใช้งานง่าย, ฉันแค่ไป ที่จะนำมันขวาที่มนุษย์เรา
จะกินที่จะนำมันบน
แต่สิ่งที่น่าสนใจในขณะนี้ คือฉันจะได้รับที่ 9 อย่างไร
คุณจะรู้ว่าที่ฉันทำไม่ได้โดยไม่มีความพยายามบาง
>> ดังนั้นที่น่าสนใจเกี่ยวกับสิ่งที่ สแต็คคือโดยการออกแบบ
มันเป็นโครงสร้างข้อมูล LIFO
วิธีการโง่ในการอธิบาย สุดท้ายในออกก่อน
ดังนั้นตัวเลขสุดท้ายใน ในเวลานี้ก็คือ 17
ดังนั้นถ้าฉันต้องการที่จะปรากฏบางสิ่งบางอย่างออกไป ของสแต็คก็จะไม่สามารถอยู่ 17
จึงมีคำสั่งบังคับของคน การดำเนินงานที่นี่ที่รายการสุดท้าย
ในจะต้องมีครั้งแรกหนึ่งออก
ดังนั้นตัวย่อ, LIFO
>> ดังนั้นทำไมนี้อาจจะมีประโยชน์?
เป็นบริบทของพวกเขาในที่ที่คุณต้องการ ต้องการโครงสร้างข้อมูลเช่นนี้หรือไม่
ดีจะได้รับประโยชน์อย่างแน่นอน ภายในเครื่องคอมพิวเตอร์
เพื่อให้ระบบการดำเนินงานอย่างชัดเจนใช้นี้ ชนิดของโครงสร้างข้อมูลสำหรับกอง
นอกจากนี้เรายังจะได้เห็นความคิดเดียวกัน เมื่อมันมาถึงหน้าเว็บ
ดังนั้นสัปดาห์นี้และสัปดาห์ถัดไปและไกลออกไป และในขณะที่คุณเริ่มต้นการดำเนินการเว็บ
หน้าเว็บในภาษาที่เรียกว่า HTML คุณสามารถ จริงใช้โครงสร้างข้อมูลเช่น
นี้เพื่อตรวจสอบว่าหน้า จัดรูปแบบได้อย่างถูกต้อง
เพราะเราจะเห็นหน้าเว็บทั้งหมดตาม เรียงลำดับจากลำดับชั้นเยื้อง
ที่จะตอนท้ายของวันที่จะต้อง โครงสร้างต้นไม้ที่อยู่ภายใต้ฝากระโปรง
ดังนั้นเพิ่มเติมว่าในเวลาเพียงเล็กน้อย
>> แต่ตอนนี้ขอเสนอให้ ขณะที่วิธีการที่เราจะไปเกี่ยวกับการ
ที่เป็นตัวแทนของสแตกอะไรคืออะไร
ผมขอเสนอว่าเราดำเนินการ สแต็คที่มีรหัสเช่นนี้
ดังนั้นสแต็คเป็นไปได้ภายในของมัน สองสิ่งอาร์เรย์, ถาดที่เรียกว่า
เพียงเพื่อให้สอดคล้องกับการสาธิต
และแต่ละรายการในอาร์เรย์ที่ เป็นไปได้ชนิด int
และความสามารถสันนิษฐานว่าเป็นอะไร
เพราะผมไม่ได้เขียน ความละเอียดที่นี่
>> มันอาจจะสูงสุด ขนาดของอาร์เรย์
และจะประกาศอาจจะเป็นคม กำหนดที่ด้านบนของไฟล์บาง
ชนิดของค่าคงที่ส่อให้เห็นว่าเป็นไปตามที่ มูลค่าเพียง
ดังนั้นกำลังการผลิตบางแห่งถูกกำหนด เป็นขนาดที่เป็นไปได้สูงสุด
ในขณะที่ภายในของโครงสร้างข้อมูล หรือที่เรียกว่าสแต็คจะมี
เป็นจำนวนเต็มรู้จักกันในชื่อ เป็นเพียงขนาด
>> ดังนั้นถ้ามีการแสดงในตอนนี้ pictorially, ขอสมมติว่านี้
กล่องดำทั้งเป็นตัวแทนของสแต็คของฉัน
ภายในของมันสองตัวแปรคือ
ดังนั้นฉันจะวาด คนแรกเป็นขนาด
และคนที่สองฉันจะ การวาดเป็นอาร์เรย์
>> แต่เพียงเพื่อให้สิ่งที่เป็นระเบียบ ปกติผมจะวาดอาร์เรย์เช่น
นี้ แต่มันชนิดของดี ถ้าเราให้ตรงกับความเป็นจริงหรือ
ตรงกับรูปแบบจิต
เพื่อให้ฉันวาดแทนอาร์เรย์ ในแนวตั้งซึ่งเป็นเพียงอีกครั้ง
การกระทำของศิลปิน
ไม่ได้เรื่องจริงๆสิ่งที่มัน คืออยู่ภายใต้ฝากระโปรง
และเราจะบอกให้ว่าตามค่าเริ่มต้น กำลังการผลิตเป็นไปได้สาม
ดังนั้นนี้จะเป็นสถานที่ 0 นี้ จะเป็นสถานที่ 1 นี้
จะเป็น 2 สถานที่
>> ถ้าฉันให้สินบนกับลูกบอลความเครียดก็จะ ใครบางคนชอบที่จะเกิดขึ้นและเรียกใช้
คณะกรรมการที่นี่รอสักครู่?
ตกลงเห็นมือของคุณเป็นครั้งแรก
มาขึ้น
ทั้งหมดขวา
ดังนั้นผมจึงเชื่อว่ามันเป็นสตีเว่น
มาขึ้น
ทั้งหมดขวา
>> แต่สมมติว่าตอนนี้เราย้อนกลับไปเริ่มต้น รัฐของโลกที่ฉัน
มีเพียงการประกาศสแต็คและก็ จะเป็นในสามของความจุ
แต่ขนาดยังไม่ได้กำหนด
ถาดยังไม่ได้กำหนด
ดังนั้นคู่ในคำถามแรก
และให้ฉันให้คุณไมค์เพื่อให้คุณสามารถ มีส่วนร่วมอย่างแข็งขันมากขึ้นในเรื่องนี้
>> ดังนั้นภายในของขนาดเป็นสิ่งที่ในขณะนี้ ในเวลาถ้าทุกอย่างที่ฉันได้ทำคือ
ประกาศกองด้วย หนึ่งบรรทัดของรหัส?
>> STEVEN: ไม่มาก
>> DAVID ลัน: ตกลงไม่มาก
เรารู้ว่ามีอะไรอยู่ภายในขนาด เรารู้ว่ามีอะไรอยู่ภายใน
ของอาร์เรย์ที่นี่?
>> STEVEN: เพียงรหัสสุ่มขวา?
เพียง -
>> DAVID ลัน: ใช่ฉันจะไป เรียกมันว่ารหัส แต่สุ่ม -
>> STEVEN: กิจกรรม
>> DAVID ลัน: สิ่งที่ต้องการสุ่ม
>> STEVEN: Bits
>> DAVID ลัน: Bits ขวา?
ดังนั้นค่าขยะใช่มั้ย?
พีชคณิตดังนั้นจาก 0 และ 1
เศษของประเพณีหน้าที่แล้ว ของหน่วยความจำนี้
และเราไม่ทราบจริงๆสิ่งที่ค่า จะดังนั้นเราจึงมักจะวาดพวกเขา
เป็นเครื่องหมายคำถาม
>> ดังนั้นสิ่งแรกที่เราสันนิษฐานว่า ไปที่ต้องการทำที่นี่ -
และให้ฉันให้ฟิลด์นี้ภายใน ของมีชื่อ - ถาด
เราควรจะเริ่มต้นสิ่งที่สันนิษฐานว่า ขนาดถ้าเราต้องการ
เริ่มใช้สแต็คนี้
>> STEVEN: Tray ย่อย 3
>> DAVID ลัน: ดังนั้นตกลง
ต้องมีความชัดเจนความจุมีการประกาศ ที่อื่นที่สาม
และนั่นคือสิ่งที่ผมเคยใช้ ในการจัดสรรอาร์เรย์
ขนาดจะไปดูวิธีการหลาย ถาดมีอยู่ในปัจจุบันในกอง
>> STEVEN: ศูนย์
>> DAVID ลัน: ดังนั้นจึงควรจะเป็นศูนย์
เพื่อไปข้างหน้าและมีนิ้วมือใด ๆ วาดเป็นศูนย์ในขนาดที่
ทั้งหมดขวา
ดังนั้นตอนนี้ข้างในของสิ่งนี้ ที่นี่เราไม่ทราบ
เหล่านี้จริงๆเพียงแค่ค่าขยะ
ดังนั้นเราจึงสามารถวาดเครื่องหมายคำถาม แต่ ขอให้คณะกรรมการที่สะอาดสำหรับตอนนี้
เพราะมันไม่ได้เรื่อง ของสิ่งที่มี
เราไม่จำเป็นต้องเริ่มต้นอาร์เรย์ เพื่ออะไรเพราะถ้าเรารู้ว่า
ขนาดของสแต็คเป็นศูนย์ดีเรา ไม่ควรที่จะมองหาที่ใดใน
แถวต่อไปนี้ จุดนี้ในเวลา
>> ดังนั้นตอนนี้ผมคิดว่าจะผลักดัน หมายเลข 9 ลง stack
วิธีการที่เราควรปรับปรุงโครงสร้างข้อมูล ภายในกล่องดำนี้
ค่าอะไรบ้างที่ต้องเปลี่ยน?
>> STEVEN: ภายใน -
ขนาด?
>> DAVID ลัน: ตกลง
ขนาดควรจะเป็นอะไร
>> STEVEN: ขนาดจะเป็นหนึ่ง
>> DAVID ลัน: ตกลง
ดังนั้นขนาดควรจะเป็นอย่างใดอย่างหนึ่ง
เพื่อให้คุณสามารถทำเช่นนี้ในสองวิธี
ผมขอให้คุณตอนนี้ของคุณ นิ้วเป็นยางลบ
ทั้งหมดขวา
แล้วตอนนี้นิ้วของคุณแปรงคือ
ทั้งหมดขวา
และตอนนี้อะไรที่มีการเปลี่ยนแปลง เห็นได้ชัดว่าในโครงสร้างข้อมูล?
>> STEVEN: เรากำลังจะจาก ด้านล่างขึ้นถึง 9
>> DAVID ลัน: 9
ตกลงดี
ดังนั้นยังคงไม่สำคัญอะไรที่ สถานที่หนึ่งหรือสองเพราะพวกเขากำลัง
ค่าขยะ แต่เราไม่ควรกังวล กำลังมองหาเพราะมีขนาดเป็น
บอกเราว่ามีเพียงองค์ประกอบแรก เป็นจริงถูกต้องตามกฎหมาย
ดังนั้นตอนนี้ฉันจะผลักดันลงบน 17 รายการ
ที่เกิดขึ้นกับภาพยนตร์เรื่องนี้คืออะไร?
>> STEVEN: ขนาดดังนั้นจะไปที่สอง
>> DAVID ลัน: ตกลง
คุณยางลบ -
อุ่ย
คุณยางลบ
>> STEVEN: ยางลบ
>> DAVID ลัน: คุณแปรง
>> STEVEN: แปรง
>> DAVID ลัน: ตกลง
และสิ่งอื่นใช่หรือไม่
>> STEVEN: และแล้วเรา -
>> DAVID ลัน: เราผลักดัน 17
>> STEVEN: เราติด 17 ด้านบนดังนั้น -
>> DAVID ลัน: ตกลงที่ดี
>> STEVEN: - วางมันลง
>> DAVID ลัน: ทั้งหมดขวา
ก็เริ่มง่าย
ผมไม่ได้ไปช่วยคุณในเวลานี้
กด 22
>> STEVEN: Done
กลายเป็นยางลบ
ผมกลายเป็นแปรง
แล้วฉันวาง 22
>> DAVID ลัน: 22
ยอดเยี่ยม
ดังนั้นอีกครั้งหนึ่ง
ฉันตอนนี้ที่จะผลักดัน ลงบนสแต็ค 26
>> STEVEN: Ooh
โอ้พุทโธ่
จริงๆคุณจับฉัน off guard
>> DAVID ลัน: คุณไม่ได้ ดูจะมาถึงนี้?
>> STEVEN: ฉันไม่เห็นจะมาถึงนี้
เราจะได้ความจุเริ่มต้นใหม่?
>> DAVID ลัน: นั่นเป็นคำถามที่ดี
ดังนั้นเราจึงทาสีชนิดของตัวเอง ในมุมที่นี่
มีจริงๆไม่มีออกที่ดีสำหรับสตีเว่น เพราะเราได้รับการจัดสรรแถวนี้
แบบคงที่เพื่อที่จะพูด, ภายใน ของโครงสร้างข้อมูล
และเราได้เป็นหลักรหัสยาก มันจะมีสามขนาด
ดังนั้นเราจึงไม่สามารถจริงๆจัดสรรมัน
>> เราสามารถถ้าเราเดินกลับไปในเรา นิยามใหม่ถาดเป็นตัวชี้ว่า
จากนั้นเราจะใช้หน่วยความจำ malloc มือเพื่อ
เพราะถ้าเราได้หน่วยความจำจาก กองผ่าน malloc เรา
ก็จะเป็นอิสระมัน
แต่ก่อนที่จะพ้นที่เราจะได้ จัดสรรเป็นก้อนขนาดใหญ่ของหน่วยความจำ
ปรับปรุงตัวชี้และอื่น ๆ
แต่ตอนนี้เป็นจริง ที่ดีที่สุดที่เราสามารถทำได้
ผลักดันและ pop จะสันนิษฐานไป ที่จะมีการส่งสัญญาณข้อผิดพลาดบาง
>> ดังนั้นสำหรับตัวอย่างเช่นการดำเนินงานของเรา ของการผลักดันจะกลับมาบูลซึ่ง
กลับไปก่อนหน้านี้จริงจริงจริง
แต่ครั้งที่สี่ก็จะมี เพื่อกลับเท็จเช่น
ทั้งหมดขวา
ทำได้ดีมาก
ขอแสดงความยินดี
คุณได้รับลูกบอลความเครียดของคุณในวันนี้
>> [APPLAUSE]
>> STEVEN: ขอบคุณ
>> DAVID ลัน: ขอบคุณ
ตกลงดังนั้นนี้ดูเหมือนว่าจะมีไม่มาก ของขั้นตอนไปข้างหน้าใช่มั้ย?
เราอธิบายโครงสร้างข้อมูลนี้
มันเป็นเรื่องที่น่าสนใจใช่มั้ย?
ระบบปฏิบัติการเช่นนั้น
เห็นได้ชัดว่าเว็บสามารถใช้ประโยชน์จากนี้ และโปรแกรมอื่น ๆ ยังคง
แต่สิ่งที่เป็นข้อ จำกัด โง่ว่าเรา กลับไปยังสัปดาห์การจัดเรียงของสอง จำกัด
ที่เรามีการแก้ไขอาร์เรย์ขนาด
>> จึงมีจริงคู่ของ วิธีที่เราสามารถแก้ปัญหานี้
เราสามารถจัดสรรแบบไดนามิกอาร์เรย์ ไม่ยากโดยการเข้ารหัสมันเป็นฉันได้
ทำที่นี่ แต่แทนที่จะ re-ประกาศ นี้เพียงเพื่อให้มีความชัดเจนเช่น
บางอย่างเช่นนี้
Int ถาด * ไม่ตัดสินใจ กับความจุยัง
แต่เมื่อผมประกาศสแต็คที่อื่น ๆ ในรหัสของฉันฉันแล้วสามารถโทร malloc,
ได้รับที่อยู่ของก้อน หน่วยความจำและฉันสามารถกำหนด
ที่อยู่ไปที่ถาด
>> แล้วเพราะมันเป็นเพียงก้อน หน่วยความจำที่ฉันจะยังคงใช้ตาราง
วงเล็บในทางปกติ
เพราะอีกครั้งจะมีการจัดเรียงของนี้ เทียบเท่าการทำงานของอาร์เรย์และ
ชิ้นของหน่วยความจำที่มา กลับมาจาก malloc
เราสามารถปฏิบัติต่อคนอื่น โดยใช้การคำนวณตัวชี้หรือ
สัญกรณ์วงเล็บเหลี่ยม
ดังนั้นวิธีการหนึ่งของ
>> แต่วิธีการอื่นที่เราอาจจะดำเนินการนี​​้ โครงสร้างข้อมูลเดียวกันที่อาจเกิดขึ้น?
ใช่ไหม?
ฉันรู้สึกเหมือนเราเพิ่งแก้ไขนี้ ปัญหาเช่นสัปดาห์ที่ผ่านมา
สิ่งที่วิธีการแก้ปัญหานี้คือ ที่สตีเว่นวิ่งเข้าไปใน?
การเชื่อมโยงรายการดังนั้นขวา
>> หากปัญหาก็คือว่าเรากำลังวาดภาพ ตัวเองในมุมโดยการจัดสรร
ในหน่วยความจำน้อยเกินไปล่วงหน้าว่าเรา แล้วมีอย่างใดจัดการกับดี
ทำไมไม่เพียง แต่หลีกเลี่ยงที่ ออกไปโดยสิ้นเชิง?
ทำไมไม่เพียง แต่ประกาศถาดจะเป็น ตัวชี้ไปยังโหนด Ergo, รายการที่เชื่อมโยง,
แล้วก็จัดสรรโหนดใหม่ สตีเว่นเวลาที่จำเป็นเพื่อให้พอดีกับทุก
จำนวนเป็นโครงสร้างข้อมูล
>> ดังนั้นภาพที่จะต้องเปลี่ยน
มันจะไม่ได้เป็นที่สะอาดและเป็น ง่ายๆเป็นเพียงอาร์เรย์ของสาม ints
ตอนนี้มันจะเป็นตัวชี้ไปยัง โครงสร้างและโครงสร้างที่เป็นไป
มี int และตัวชี้ต่อไป
มันจะนำไปสู่​​การผ่านตัวชี้ว่า ไปยังอีก struct ดังกล่าวไปยัง
อีก struct เช่น
ดังนั้นภาพที่จะเป็นจริง รับบิต Messier
และเรามีลูกศรต้องการผูก ทุกอย่างร่วมกัน
>> แต่ที่ดีที่ถูกต้องเพราะ เราได้เห็นวิธีการทำเช่นนี้
และเมื่อคุณได้รับความสะดวกสบาย บางสิ่งบางอย่างที่เชื่อมโยงการดำเนินการเช่น
รายการที่คุณจะต้องทำอย่างไรถ้าคุณ เลือกที่จะใช้ตารางแฮชด้​​วย
ผูกมัดแยกต่างหากสำหรับ p-6 ชุดคุณสามารถ ใช้เป็นอาคารตึกหรือ
ส่วนผสมหรือใน Scratch พูด ขั้นตอนบางอย่างที่คุณใส่คุณ
สร้างชิ้นส่วนจิ๊กซอว์ของคุณเอง ที่คุณสามารถนำมาใช้ใหม่
tradeoffs ดังนั้นการแก้ปัญหาที่อาจเกิดขึ้น แต่ ที่เราได้เห็นจริงก่อน
>> ค่อนข้างบ่อยดังนั้นคุณจะเห็นนี้ทุกคน ปีหรือสองปีเมื่อแอปเปิ้ลออก
สิ่งใหม่ ๆ และทุกคนบ้า เส้นขึ้นที่ด้านนอกของแอปเปิ้ล
เก็บที่จะซื้อของพวกเขาเล็กน้อย อัพเกรดฮาร์ดแวร์
ผมพูดนี้ก็ตกลงเพราะ ผมเป็นหนึ่งในคนเหล่านั้น
ดังนั้นสิ่งที่ชนิดของโครงสร้างข้อมูล อาจเป็นตัวแทนของความเป็นจริงนี้
>> ดีขอเรียกว่าคิวสาย
ดังนั้นอังกฤษจะเรียกว่าโดยปกติจะเป็น คิวต่อไปเพื่อให้มันเป็นชื่อดี
และทั้งสองการดำเนินงานที่คิว จะสนับสนุนเราจะเรียก enqueue
การดำเนินงานและการดำเนินการ dequeue, ซึ่งเป็นสิ่งที่คล้ายกันใน
จิตวิญญาณที่จะผลักดันและ pop
มันเรียงลำดับที่แตกต่างกันเพียงแค่ใน การประชุมสิ่งที่เรากำลังเรียกร้องเหล่านี้
แต่การที่จะ enqueue สิ่งที่หมายถึงการเพิ่ม หรือใส่ไปให้โครงสร้างข้อมูล
เพื่อ dequeue วิธีที่จะเอามันออกไป
แต่ในขณะที่สแต็คเป็นข้อมูล LIFO โครงสร้างคิวเป็นครั้งแรกแล้ว
ครั้งแรกที่ออกโครงสร้างข้อมูล
>> หากคุณเป็นคนแรกในสาย คุณจะเป็นคนแรกที่ได้รับ
ออกมาจากแถวและซื้ออุปกรณ์ใหม่ของคุณ
คิดว่าไม่พอใจที่คนเหล่านี้จะเป็น ถ้าแอปเปิ้ลแทนสแต็คที่ใช้สำหรับ
ตัวอย่างเช่นในการดำเนินการเลือก ขึ้นจากของเล่นใหม่ของคุณ
ดังนั้นการรอคิวให้ความรู้สึกอย่างแน่นอนและ เราสามารถคิดของทุกประเภทของ
โปรแกรมสมมุติสำหรับคิว โดยเฉพาะอย่างยิ่งเมื่อคุณต้องการความเป็นธรรม
ดังนั้นวิธีที่เราอาจจะใช้เหล่านี้ เป็นโครงสร้างข้อมูล?
>> ผมเสนอว่าเราอาจจะ ต้องทำมันด้วยวิธีนี้
ดังนั้นฉันจะไปตอนนี้มีตัวเลข
ดังนั้นเราจะให้มันง่ายและไม่ จำเป็นต้องพูดคุยในแง่ของถาด
เพียงตัวเลขที่ผู้คนจากอากาศ
ความจุเป็นไปได้อีกครั้งแก้ไข จำนวนของคนที่สามารถอยู่ใน
บรรทัดนี้เป็นสามหรือ สิ่งอื่น ๆ มูลค่า
>> แต่ผมเสนอว่าผมต้องติดตาม ไม่เพียง แต่ขนาดของ
คิววิธีการหลายสิ่งที่อยู่ในนั้น
ดังนั้นขนาดขนาดกำลังการผลิตในปัจจุบันคือ เป็นขนาดสูงสุด
เพียงแค่อีกครั้งศัพท์ โดยการประชุม
ฉันไม่จำเป็นต้อง int เพิ่มเติมภายในทำไม ของคิวที่จะติดตามคนที่อยู่ใน
ด้านหน้าของสาย?
ฉันต้องทำในกรณีนี้ทำไม?
>> ด้วยวิธีการนี​​้เป็นภาพ จะเปลี่ยน?
ผมอาจจะสามารถนำมาใช้มากที่สุด ของภาพนี้
ให้ฉันไปข้างหน้าและลบอะไรที่นี่
เราจะให้นี้เล็กน้อย ชื่อที่แตกต่างกันที่นี่
Let 's กำจัด 17 ให้ได้รับการกำจัด จาก 9 ให้ของได้รับกำจัดของ 3
และขอเพิ่มอีกหนึ่งสิ่งอื่น ๆ
ผมเสนอว่าผมจำเป็นที่จะต้องติดตาม ด้านหน้าของรายการซึ่งเป็นเพียง
จะเป็น int เช่นกัน
และเราจะให้มันง่าย
ไม่มีรายการที่เชื่อมโยงสำหรับตอนนี้
>> เราจะยอมรับว่าเรากำลังจะ ชนขึ้นกับขีด จำกัด นี้
แต่สิ่งที่ฉันต้องการที่จะเห็น เกิดขึ้นในเวลานี้?
ดังนั้นคิดว่าฉันไปข้างหน้าและเป็นคนแรก คนที่ขึ้นมาอยู่ในแถวและ
มันเป็นหมายเลข 9
เราจะมีลูกความเครียด
ฉันสามารถขโมยพูดสองหรือสามคน?
หนึ่งสองสาม?
มาขึ้น
ขวาจากด้านหน้าเพราะ เราจะทำให้เรื่องนี้อย่างใดอย่างหนึ่งอย่างรวดเร็ว
>> แต่ละคุณคือตอนนี้ไปได้ เด็กชายแฟนในสายที่แอปเปิ้ล
คุณจะไม่ได้รับฮาร์ดแวร์แอปเปิ้ล ในตอนท้ายของเรื่องนี้แม้ว่า
ทั้งหมดขวา
ดังนั้นคุณหมายเลข 9 คุณ หมายเลข 17, หมายเลข 22
เหล่านี้เป็นตัวเลขโดยพลการเช่น นักศึกษารหัสหรือ whatnot
และในเพียงสักครู่ขอเริ่มต้น เพื่อเริ่มต้นการเพิ่มสิ่ง
และฉันจะใช้คณะกรรมการที่นี่เวลานี้
>> ดังนั้นในกรณีนี้ผมได้เริ่มต้น ด้านหน้าที่จะเป็น -
ที่จริงผมไม่ได้จริงๆดูแลสิ่งที่ ด้านหน้าเป็นเพราะขนาดเป็นศูนย์
ดังนั้นนี้อาจจะดีแค่ เป็นเครื่องหมายคำถาม
เหล่านี้ทั้งหมดเครื่องหมายคำถาม
ดังนั้นตอนนี้เราจะเริ่มต้นที่จะเห็นบางส่วนจริง คนแถวที่ร้านค้า
>> ดังนั้นหากหมายเลข 9 คุณหนึ่งครั้งแรก มีที่ 5:00 ไปข้างหน้าและแถว,
หรือคืนก่อ​​น
ตกลง
ดังนั้นตอนนี้อยู่ที่นี่ 9
ดังนั้น 9 ในด้านหน้าของรายการ
ดังนั้นฉันจะไปข้างหน้าและปรับปรุง ขนาดของข้อมูลในปัจจุบันนี้
โครงสร้างที่จะไม่เป็น 0 อีกต่อไป แต่เป็น 1
ฉันจะใส่ที่ 9 ด้านหน้าของรายการ
ให้ฉันไปข้างหน้าและสลับหน้าจอ เพื่อให้เราสามารถมองเห็นอดีตที่ผ่านมาเราได้ที่นี่
>> และตอนนี้ฉันทำในสิ่งที่ต้องการ ใส่ที่ด้านหน้า?
ฉันจะติดตามว่า ด้านหน้าของคิวในขณะนี้
อยู่ที่ 0 สถานที่
เพราะสิ่งที่เป็นไปที่จะเกิดขึ้น?
ดีสมมติว่าตอนนี้ฉัน enqueue 17 เช่นกัน
การฟ้อนรำดังนั้นในบรรทัดที่มี
และอีกครั้งที่จัดเรียงของประตูไป เก็บเป็นไปได้ที่นี่
ดังนั้นตอนนี้ฉันได้เพิ่ม 17
และถึงแม้คนเหล่านี้มีการปิดกั้น หน้าจอที่ตกลง
เพราะเราสามารถดูได้ที่นี่
ขอโทษ
>> ผู้ชม: เราสามารถเคลื่อนย้าย -
>> DAVID ลัน: ไม่มีที่ตกลง
มันใหญ่ขึ้น
ดังนั้น 17 คือตอนนี้ภายในของคิว
ผมจำเป็นต้องปรับปรุงซึ่ง ฟิลด์ในขณะนี้แม้ว่า?
ตกลงขนาดแน่นอน
และวิธีการเกี่ยวกับด้านหน้า
ตกลงไม่มี
ด้านหน้าไม่ควรเปลี่ยนเพราะ ซึ่งแตกต่างจากสแต็คเรา
ต้องการที่จะรักษาความเป็นธรรม
ดังนั้นถ้า 9 มาในครั้งแรกที่เราต้องการ 9 จะออกเป็นครั้งแรกของสาย
และเข้าไปในร้าน
>> ในความเป็นจริงเราจะเห็นว่า
ก่อนที่เราจะใส่ 22 ให้ ไปข้างหน้าและ dequeue 9
ชื่ออะไรของคุณอีกครั้ง?
>> ผู้ชม: เจค
>> DAVID ลัน: เจคที่เกิดขึ้น จะ dequeued ขณะนี้
เพื่อให้คุณได้รับที่จะเดินเข้าไปในร้าน
และแกล้งทำเป็นว่าเก็บ คือที่นั่น
ดังนั้นตอนนี้สิ่งที่จำเป็น - dit-dit-dit!
ความต้องการที่จะเกิดขึ้นอะไรอยู่ตอนนี้
การตัดสินใจการออกแบบ
ดังนั้นไม่สัญชาตญาณที่ไม่ดี แต่ - ชื่ออะไรของคุณอีกครั้ง?
>> ผู้ชม: เดวิด
>> DAVID ลัน: เดวิด
ดังนั้นสิ่งที่ไม่เดวิดทำอะไร?
เขากำลังพยายามที่จะเรียงลำดับของการแก้ไขข้อมูล โครงสร้างและย้ายจากที่ตั้งของเขา
ในสถานที่ที่อดีตของเจค
และที่ว่าดีถ้าเราเต็มใจ ที่จะยอมรับว่าเป็น
รายละเอียดการปฏิบัติ
แต่ก่อนอื่นขอปรับปรุงข้อมูล โครงสร้างก่อนที่เราจะทำอย่างนั้น
เพราะฉันไม่ชอบความคิดของทุกคน คนขยับในสายนี้
>> มันไม่ใช่เรื่องใหญ่ถ้าดาวิดด้วย ขั้นตอนที่หนึ่ง แต่อีกครั้งคิดว่ากลับไป
เมื่อเราได้มีแปดอาสาสมัคร เวทีและที่เราเคยทำเช่นการแทรก
การจัดเรียงที่เราต้องเริ่มต้น ย้ายทุกคนรอบตัว
ที่ได้มีราคาแพงใช่มั้ย?
ที่ทำให้ฉันประจบประแจงเกี่ยวกับ O ใหญ่ ของ n O ใหญ่ของ n ยืดอีกครั้ง
มันไม่ได้เป็นความรู้สึกเหมือน ผลในอุดมคติ
>> ดังนั้นขอเพียงแค่การปรับปรุงนี้
ดังนั้นขนาดของคิว จะไม่มีอีกต่อ 2
ก็ตอนนี้เพียงแค่ 1
แต่ตอนนี้ผมสามารถปรับปรุงบางสิ่งบางอย่าง ฉันไม่ได้ปรับปรุงมาก่อน
ด้านหน้าของรายการ
ฉันสามารถบอกตำแหน่งที่ 1?
ดังนั้นตอนนี้เรามีค่าขยะที่นี่ มูลค่าขยะที่นี่และเดวิดใน
ตรงกลางของขยะนี้
แต่โครงสร้างข้อมูล ยังคงเป็นเหมือนเดิม
>> และในความเป็นจริงผมไม่จำเป็นที่จะต้อง เปลี่ยนหมายเลขอดีตของเจค
9 เพราะใครจะสน
ผมมีข้อมูลที่เพียงพอในขณะนี้ ขนาดที่ฉันรู้ว่ามีหนึ่งคน
คิวนี้
และฉันรู้ว่าคนคนนั้น อยู่ที่สถานที่ 1 ไม่ได้ 0
ฉันไม่ได้นับ
So 1 เช่นกัน
ดังนั้นโครงสร้างข้อมูลที่ยังคงตกลง
>> ดีสิ่งที่เกิดขึ้นต่อไปหรือไม่
enqueue Let 's -
คุณชื่ออะไร?
>> ผู้ชม: Callen
>> DAVID ลัน: Callen
Let 's enqueue Callen และ 22 ขณะนี้อยู่ในคิว
ดังนั้นตอนนี้สิ่งที่เปลี่ยนที่นี่?
ด้านหน้าจะไม่ไป เปลี่ยนแปลงอย่างเห็นได้ชัด
ขนาดจะเปลี่ยนเป็น 2 อีกครั้ง
22 และจบลงที่นี่ 9 ยังคงเป็นปัจจุบัน แต่มันได้อย่างมีประสิทธิภาพ
ค่าขยะในขณะนี้
มันเป็นเพียงเศษเล็กเศษน้อยของอดีตเจค
>> ดังนั้นตอนนี้สิ่งที่เกิดขึ้นถ้า ผม dequeue ดาวิด
การดำเนินการที่ผ่านมา dequeue เดวิด
เราสามารถเปลี่ยน แต่ผมเสนอขอ ทำตามที่ทำงานน้อยที่สุดเท่าที่ทำได้
ตอนนี้โครงสร้างข้อมูลของฉันไป กลับมาอยู่ในขนาด 2-1
แต่ด้านหน้าของคิว ตอนนี้กลายเป็น 2
ฉันไม่จำเป็นต้องเปลี่ยนตัวเลขเหล่านี้ เพียง แต่เพราะพวกเขากำลัง
เพียงแค่ค่าขยะ
>> แต่ตอนนี้สิ่งที่เกิดขึ้น?
สมมติว่าฉัน enqueue ตัวเอง, 26?
ฉันรู้สึกเหมือนฉันเป็นส่วนหนึ่งของที่นี่
ดังนั้นฉันถูก enqueued
ดังนั้นผมชนิดเป็นของที่นี่
และถึงแม้คุณไม่ได้ค่อนข้าง ขอขอบคุณที่นี้สายตาบนเวที
เพราะเรามีมากมายห้องพักผมควร ไม่สามารถยืนอยู่ที่นี่ทำไม?
>> ผู้ชม: คุณกำลังออกไปจากตัว
>> DAVID ลันขวา:
ฉันออกไปจากตัว
ผมเคยจัดทำดัชนีเกิน ขอบเขตของอาร์เรย์นี้
ผมควรจะอยู่ในหนึ่งใน สามสถานที่ที่เป็นไปได้
ตอนนี้เป็นธรรมชาติมากที่สุดจะไปที่ไหน
ผมเสนอเรา leveraged หนึ่งสัปดาห์เคล็ดลับ
ประกอบ Mod ร้อยละ
เพราะฉันยืนอยู่ที่ทางเทคนิค สถานที่ตั้ง 3 แต่ฉันกำลังเล่น 3
ดังนั้น 3, เครื่องหมายเปอร์เซ็นต์, 3 -
กำลังการผลิต 3
ว่าคืออะไร?
ส่วนที่เหลือคืออะไรเมื่อ คุณแบ่ง 3 โดย 3
0
>> ดังนั้นที่ทำให้ฉันถูกเจคคือ ซึ่งเป็นจริงดี
ดังนั้นตอนนี้การดำเนินการ ของสิ่งนี้ไป
เป็นบิตของปวดหัว
มันจริงๆเพียงหนึ่งบรรทัด อาการปวดหัวของรหัส
แต่อย่างน้อยตอนนี้มีขยะของ ค่าที่นี่ แต่มีสองคน
ints ถูกต้องตามกฎหมายที่นี่
และผมก็อ้างว่าตอนนี้เราได้ทำ สิ่งที่เราต้องทำตราบใดที่
เราเปลี่ยนสิ่งที่เจค ค่าจะเป็น 26
>> ขณะนี้เรามีข้อมูลที่เพียงพอยังคง เพื่อรักษาความสมบูรณ์
ของโครงสร้างข้อมูลนี้
เรายังคงชนิดของออกจากโชคเมื่อเรา ต้องการแทรกสี่หรือมากกว่าทั้งหมด
องค์ประกอบ แต่ฉันสามารถอย่างน้อยทำให้สวย ประสิทธิภาพในการใช้อย่างต่อเนื่องนี้
เวลาในความเป็นจริง
ฉันไม่ต้องกังวลเกี่ยวกับการขยับ ทุกคนเป็นความชอบเดวิด
>> คำถามใด ๆ เกี่ยวกับสแต็ค, หรือคิวนี้?
>> ผู้ชม: คือเหตุผลว่าทำไม ขนาดที่คุณต้องการเพื่อให้คุณทราบ
ที่จะมีคนคนหนึ่ง?
>> DAVID ลัน: ว่า
ฉันจำเป็นต้องทราบขนาดของอาร์เรย์ เพราะผมจำเป็นต้องรู้ว่าวิธีการ
หลายค่าเหล่านี้ถูกต้องตามกฎหมาย และเพื่อที่ฉันสามารถหาที่ที่จะใส่
คนถัดไป
อย่างแน่นอน
ขนาดคือ -
ที่จริงเราไม่ได้ปรับปรุงนี้ยัง
ฉันจะเพิ่มตัวเองที่ 26
ขนาดตอนนี้ไม่ได้ 1 แต่ 2
ดังนั้นตอนนี้แน่นอนช่วยให้ผมหา หัวของรายการซึ่งไม่ได้เป็น 0 ไม่
1 แต่คือ 2
ด้านหน้าของรายการ เป็นที่แน่นอนจำนวน 22
เพราะเขาเดินเข้ามาในครั้งแรกดังนั้นเขาจึงควร ได้รับอนุญาตให้เข้าไปในร้านก่อนที่ฉัน
แม้ว่าสายตาผมยืนอยู่ ใกล้ชิดในการจัดเก็บ
>> ขวาทั้งหมด?
รอบปรบมือสำหรับคนเหล่านี้ และเราจะให้พวกเขาออกจากที่นั่น
>> [APPLAUSE]
>> DAVID ลัน: ฉันจะให้ คุณเก็บถาด
เราจะได้เห็นว่าเกิดอะไรขึ้นถ้า ที่คุณต้องการ แต่อาจจะไม่
ทั้งหมดขวา
ดังนั้นสิ่งที่ตอนนี้ไม่ปล่อยให้เรา?
ดีให้ฉันเสนอว่ามี ไม่กี่โครงสร้างข้อมูลอื่น ๆ ที่เราจะทำได้
เริ่มต้นการเพิ่มชุดเครื่องมือของเราที่จะ จริงจะค่อนข้างค่อนข้างที่เกี่ยวข้องเช่น
เราดำน้ำในสิ่งที่เว็บ
อีกครั้งซึ่งมีชนิดของการเชื่อมต่อบางอย่าง กับต้นไม้ในรูปแบบของ
สิ่งที่เรียกว่า DOM เอกสาร, รูปแบบวัตถุ
แต่เราจะดูรายละเอียดของ ก่อนที่จะยาว
>> ผมขอเสนอว่าเรา definitionally เรียกต้นไม้ในขณะนี้สิ่งที่คุณอาจรู้ว่าเป็น
มากขึ้นของต้นไม้ครอบครัวที่คุณ มีบรรพบุรุษที่บาง
รากของต้นไม้
ปูชนียบุคคลโบราณหรือที่ ส่วนบนสุดของต้นไม้
โดยไม่มีคู่สมรสในกรณีนี้ของพวกเขา
แต่ตอนนี้เรามีสิ่งที่เราจะเรียก เด็กซึ่งเป็นโหนดที่แขวน
เด็กออกทางซ้ายหรือทางขวาเด็ก, ลูกศรเป็นภาพที่นี่
>> ในคำอื่น ๆ ในโครงสร้างข้อมูลต้นไม้ ในคอมพิวเตอร์, ต้นไม้มีศูนย์
โหนดหรือมากกว่า
ถ้ามันมีอย่างน้อยหนึ่งโหนด ที่เรียกว่าราก
มันเป็นสิ่งที่มองเห็นว่า เราวาดที่ด้านบน
และโหนดที่เช่นโหนดอื่น ๆ สามารถ มีศูนย์หนึ่งหรือสองหรือสาม
หรือ แต่เด็กหลายคน โครงสร้างข้อมูลสนับสนุน
ในกรณีนี้รากของการจัดเก็บ หนึ่งค่ามีลูกสองคน, 2 และ 3,
ดังนั้นเราจึงมักเรียก 2 ด้านซ้าย ของเด็กและ 3 เด็กขวา
>> และจากนั้นเมื่อเราได้รับลงไปที่ 5, 6, และ 7, 6 อาจเรียกได้ว่าเด็กกลาง
ถ้าคุณมีลูกสี่คน, ที่จะได้รับสับสน
ดังนั้นเราจึงหยุดการใช้ชนิดที่ ทางลัดด้วยวาจา
แต่มันจริงๆเพียงต้นไม้ครอบครัว
และใบที่นี่มีโหนที่ ตัวเองไม่มีลูก
พวกเขาแขวนออกด้านล่างของต้นไม้
>> ดังนั้นวิธีที่เราอาจจะใช้ต้นไม้ที่ มีเพียงเด็กสองคนสุด?
เราจะเรียกว่าต้นไม้ไบนารี
Bi อีกความหมายสองในการนี​​้ กรณีเช่นกับไบนารี
และดังนั้นจึงสามารถมีศูนย์หนึ่ง หรือเด็กสองคนสูงสุด
>> ผมเสนอว่าเราใช้โหนด สำหรับงานโครงสร้างที่มี int n ที่
แล้วสองตัวชี้หนึ่งที่เรียกว่า ซ้ายขวาหนึ่งที่เรียกว่า
แต่ผู้ที่มีดีเพียงแค่ การประชุมโดยพลการ
และเป็นเรื่องดีที่ในขณะนี้โดยเฉพาะอย่างยิ่งถ้าคุณ ชนิดของการต่อสู้กับแนวคิด
เรียกซ้ำตัวเองหรือคิดว่ามันไม่ได้ จริงๆวิธีการแก้อะไรเลย,
โดยเฉพาะอย่างยิ่งถ้าคุณสามารถ วิ่งออกจากหน่วยความจำ
ตอนนี้เรากำลังพูดถึงเกี่ยวกับข้อมูล โครงสร้างและขั้นตอนวิธีที่ช่วยให้
เราสามารถสำรวจและจัดการกับพวกเขา ปรากฎว่าเรียกซ้ำตัวเองกลับมาใน
อื่น ๆ อีกมากมายที่น่าสนใจ ถ้าไม่ได้เป็นวิธีที่สวยงาม
>> ดังนั้นผมเสนอนี้คือการดำเนินการ ของฟังก์ชั่นค้นหา
ให้สองปัจจัยการผลิต -
ดังนั้นคิดว่านี้เป็นกล่องสีดำ
ให้สองปัจจัยการผลิต, n, int และ ตัวชี้ไปยังต้นไม้ตัวชี้ไปยัง
โหนดหรือจริงๆรากของต้นไม้ที่ผม อ้างว่าฟังก์ชั่นนี้สามารถกลับ
จริงหรือเท็จที่ n ค่า ภายในของต้นไม้ต้นนี้คือ
>> อยู่ภายในของกล่องดำนี้คืออะไร?
ดีสี่สาขา
ครั้งแรกที่ตรวจสอบเพียง
ถ้าต้นไม้เป็นโมฆะเพียงกลับเท็จ
หากมีโหนดไม่มี n ไม่ได้, มีจำนวนไม่เพียงกลับเท็จ
ถ้าแม้ว่า, n, ค่าที่คุณกำลังมองหา สำหรับน้อยกว่าต้นไม้ศร n และ
เพียงเพื่อให้ชัดเจนสิ่งที่ไม่ได้หมายถึงเมื่อ ผมเขียนต้นไม้แล้วลูกศร
สัญกรณ์, n?
อย่างแน่นอน
ก็หมายความว่า dereference ตัวชี้ที่เรียกว่าต้นไม้
ไปที่นั่นและจากนั้นได้รับภายในที่ โหนดและสาขาของตนที่เรียกว่า n
แล้วเปรียบเทียบ n จริงที่เป็น ผ่านเข้าไปค้นหากับมัน
>> ดังนั้นถ้า n มีค่าน้อยกว่าค่า n ในโหนดตัวเองดี
ว่าหมายความว่าอย่างไร
ซึ่งหมายความว่าไม่มีอะไรได้อย่างรวดเร็วก่อน
ใช่ไหม?
เช่นเดียวกับเมื่อคุณมี array ของ ค่าคุณอาจชอบที่จะใช้เลขฐานสอง
ค้นหาเป็นรูปแบบของการหาร และพิชิต
แต่เราทำในสิ่งที่สมมติฐานที่จำเป็นต้องทำ สำหรับการค้นหาแบบไบนารีไปทำงานที่ทั้งหมด
ในสมุดโทรศัพท์และ ตัวอย่างก่อนหน้านี้?
>> วิธีการที่จะแยก
เพื่อขอปรับแต่งความหมายของต้นไม้ ที่นี่จะไม่เป็นเพียงแค่ต้นไม้ซึ่งสามารถ
มีจำนวนของเด็ก ๆ
ไม่ได้เป็นเพียงต้นไม้ไบนารีซึ่งสามารถ มี 0, 1, 2 หรือสูงสุด
แต่ในขณะที่ต้นไม้ค้นหาไบนารีหรือ BST, ซึ่งเป็นเพียงวิธีแฟนซีของบอกว่า
ต้นไม้ไบนารีดังกล่าวว่าโหนดทุกคน เด็กซ้ายถ้าปัจจุบันคือ
น้อยกว่าโหนด
และเด็กขวาของโหนดทุก ถ้าปัจจุบันเป็นใหญ่
กว่าโหนดตัวเอง
>> ดังนั้นในคำอื่น ๆ ถ้าคุณมีการวาด ออกต้นไม้ทั้งหมดของจำนวนที่มีค่า
มีความสมดุลอย่างรอบคอบเช่นนี้เพื่อที่ว่าถ้า คุณมี 55 เป็นราก, 33 สามารถไป
ไปทางซ้ายเพราะมันน้อยกว่า 55
77 สามารถไปทางขวาเพราะ มันยิ่งใหญ่กว่า 55
แต่ตอนนี้สังเกตเห็นความหมายเดียวกัน มันเป็น recursive นิยามวาจา
มีที่จะใช้สำหรับ 33
เด็กซ้าย 33 ของต้องน้อยกว่ามัน และเด็กขวาของ 33, 44, ต้อง
มีขนาดใหญ่กว่ามัน
>> ดังนั้นนี่คือต้นไม้ค้นหาแบบไบนารีและ ผมเสนอใช้นิด ๆ หน่อย ๆ
เรียกซ้ำตัวเองตอนนี้เราสามารถหา n
ดังนั้นถ้า n คือ n น้อยกว่าค่าที่ โหนดปัจจุบันผมจะไป
ข้างหน้าและเรือท้องแบนเพื่อที่จะพูดและเพียง กลับสิ่งที่เป็นคำตอบของ
ค้นหา n เมื่อ เด็กซ้ายของต้นไม้
แจ้งให้ทราบอีกครั้งงานนี้จะเป็นเพียงแค่ คาดว่าจะเป็นดาวโหนด
ตัวชี้ไปยังโหนด
ดังนั้นแน่นอนผมก็สามารถทำต้นไม้ ลูกศรซ้ายซึ่งจะนำไปสู่
ฉันไปยังโหนดอื่น
แต่โหนดที่คืออะไร?
>> ดีตามประกาศนี้ ด้านซ้ายเป็นเพียงตัวชี้เพื่อที่ว่าเพียงแค่
หมายความว่าผมผ่านไปฟังก์ชันการค้นหา ตัวชี้ที่แตกต่างกันคือ
หนึ่งที่แสดงถึง ต้นไม้เด็กซ้ายของฉัน
ดังนั้นในกรณีนี้ชี้ถึง 33 ถ้า นี้คือตัวอย่างใส่ของเราในขณะเดียวกันถ้า
n มากกว่า n มูลค่าที่ โหนดปัจจุบันในต้นไม้แล้วผม
จะไปข้างหน้าและเรือท้องแบนในอื่น ๆ ทิศทางและเพียงแค่พูดว่าผมทำไม่ได้
ทราบว่า n ค่านี้ในต้นไม้, แต่ฉันรู้ว่ามันคือมันลงของฉัน
สาขาขวาเพื่อที่จะพูด
เพื่อให้ฉันโทร recursively ค้นหา n ผ่านอีกครั้ง แต่ผ่านใน
ตัวชี้ไปที่เด็กขวาของฉัน
>> ในคำอื่น ๆ ถ้าฉันปัจจุบันอยู่ที่ 55 และฉันกำลังมองหา 99, ฉันรู้ว่า 99
มีค่ามากกว่า 55 ดังนั้นเช่นเดียวกับผมฉีก สัปดาห์ที่สมุดโทรศัพท์ที่ผ่านมาและเรา
ไปขวาในทำนองเดียวกันเราเป็น จะไปที่นี่
และฉันไม่ทราบว่าเป็นที่ด้านขวาของฉัน เด็กและยังไม่ได้ 77 จะมี แต่
ฉันรู้ว่ามันไปในทิศทางนั้น
ดังนั้นผมจึงเรียกค้นหาเด็กขวาของฉัน, 77, และปล่อยให้ร่างการค้นหาออกมาจาก
มีถ้า 99 ในกฎเกณฑ์นี้ ตัวอย่างที่เป็นจริงมี
>> อื่นกรณีสุดท้ายคืออะไร
ถ้าต้นไม้เป็นโมฆะกรณีหนึ่งคือ
ถ้า n มีค่าน้อยกว่าในปัจจุบันของโหนด มูลค่าเป็นอีกกรณีหนึ่ง
ถ้า n มีค่ามากกว่าปัจจุบัน ค่าของโหนดเป็นกรณีที่สาม
กรณีที่สี่และสุดท้ายคืออะไร?
ผมคิดว่าเรากำลังออกจากกรณีขวา?
มันต้องเป็นที่ n คือใน โหนดปัจจุบันว่าฉันเมื่อ
>> ดังนั้นถ้าฉันกำลังค้นหา 55 ที่จุดนี้ ในเรื่องสาขาที่
ต้นไม้จะกลับมาจริง
ดังนั้นสิ่งที่น่าสนใจที่นี่เป็นที่ที่เรา จริงซึ่งแตกต่างจากสัปดาห์ที่ผ่านมาชนิดที่เรา
ของมีสองกรณีฐาน
และพวกเขาจะได้ไม่ต้อง เป็นสิ่งที่ด้านบน
ด้านบนเป็นกรณีฐานเพราะถ้า ต้นไม้เป็นโมฆะมีอะไรจะทำอะไร
เพียงแค่กลับยากรหัส ค่าของเท็จ
>> สาขาล่างคือการจัดเรียงของ เริ่มต้นด้วยเหตุนี้ถ้าเราได้รับการตรวจสอบ
โมฆะเราได้ตรวจสอบถ้ามันควรจะเป็น ทิ้งไว้ แต่มันไม่ควรจะเป็นเราได้
การตรวจสอบถ้ามันควรจะเป็นที่ถูกต้อง แต่มัน ไม่ควรจะเป็นอย่างเห็นได้ชัดก็จะต้องมี
ขวาว่าเราอยู่ที่ไหน
กรณีที่ฐานของ
ดังนั้นจึงมีสองกรณี recursive ของ แซนวิชที่นั่นในกลาง
แต่ฉันจะได้เขียน นี้ในลำดับใด ๆ
ผมแค่คิดว่ามันชนิดของความรู้สึกที่เป็นธรรมชาติ ตรวจสอบก่อนสำหรับข้อผิดพลาดที่เป็นไปได้
จากนั้นตรวจสอบที่เหลือจากนั้นตรวจสอบที่ถูกต้องแล้ว สมมติว่าคุณกำลังที่โหนด
คุณจริงกำลังมองหา
>> ดังนั้นทำไมนี้อาจจะมีประโยชน์?
ดังนั้นมันจะเปิดออก -
และแจ้งให้เราข้ามไปยังทีเซอร์ ที่นี่ที่อยู่ในเว็บ
เรากำลังจะเริ่มต้นใช้ไม่ได้ ภาษาการเขียนโปรแกรมในตอนแรก แต่
ภาษามาร์กอัป
ภาษามาร์กอัปเป็นหนึ่งที่ ในทำนองเดียวกันการเขียนโปรแกรม
ภาษา แต่มันก็ไม่ได้ให้คุณ ความสามารถในการแสดงตัวเองมีเหตุผล
มันจะช่วยให้คุณมีความสามารถในการ แสดงตัวเองโครงสร้าง
>> คุณไม่ต้องการที่จะนำบางสิ่งบางอย่างที่ บนหน้าเว็บเพจ?
อะไรที่คุณต้องการสีที่จะทำให้มัน?
คุณทำอะไรขนาดตัวอักษรต้องการให้มัน?
คำอะไรที่คุณจริง ต้องการบนหน้าเว็บ?
เพื่อให้ภาษามาร์กอัป
แต่แล้วเราได้อย่างรวดเร็วจะแนะนำ จาวาสคริปต์ซึ่งเป็นที่เต็มเปี่ยม
การเขียนโปรแกรมภาษา
มากที่คล้ายคลึงกันในลักษณะที่ปรากฏ ไปที่ C แต่จะมีบางส่วน
ดีที่มีประสิทธิภาพมากขึ้น คุณสมบัติเป็นมิตรกับผู้ใช้
>> และเป็นหนึ่งในความผิดหวังที่นี้ จุดในภาคการศึกษาคือการที่เราจะ
ในเร็ว ๆ นี้ดำเนินการสะกดในไกลน้อย บรรทัดของรหัสที่ใช้ภาษาอื่น ๆ
กว่า C ตัวเองช่วยให้ แต่ด้วยเหตุผลของ ไม่ช้าเราก็จะเข้าใจว่า
นี้จะเป็นหน้าเว็บดังกล่าวเป็นครั้งแรก
มันจะเป็น underwhelming สมบูรณ์ คนแรกที่เราทำ
มันก็จะพูดว่า Hello World
แต่ถ้าคุณไม่เคยเห็นมัน ก่อนนี้เป็น HTML,
ภาษา Hypertext Markup
>> ถ้าคุณไปที่ตัวเลือกเมนูบางอย่างใน มากที่สุดเบราว์เซอร์ใด ๆ บนหน้าเว็บใด ๆ
อินเทอร์เน็ตคุณสามารถดู HTML ที่บางคนเขียนจดหมายไปถึง
สร้างหน้าเว็บที่
และมันอาจจะดูไม่เป็น สั้นหรือเป็นที่เรียบร้อยเช่นนี้
แต่มันจะเป็นไปตามรูปแบบของเหล่านี้ วงเล็บเปิดและ slashes และ
ตัวอักษรและตัวเลขที่อาจเกิดขึ้น
>> ฉันคิดว่าฉันต้องการให้คุณทีเซอร์ ของสิ่งที่คุณจะสามารถที่จะทำ
หลังจากการ CS50
ให้ฉันไป cs.harvard.edu / ปล้น, หน้าแรกของตัวเองของเราร็อบโบว์
เขาทำนี้สำหรับเรา
ดังนั้นคุณจะเร็วจะสามารถที่จะทำอย่างนั้น
และยังเป็นสิ่งที่คุณได้ยิน เช้านี้ -
สิ่งที่คุณได้ยินเมื่อเช้านี้ -
>> [MUSIC หนูแฮมสเตอร์ DANCE]
>> - You'Ll จะสามารถที่จะทำเรื่องนี้ให้
ที่รอเราเมื่อวันพุธที่
เราจะเห็นคุณแล้ว
>> [MUSIC หนูแฮมสเตอร์ DANCE]
DAVID ลัน: ตอนต่อไป CS50 -