[เล่นเพลง]
ลำโพง 1: สิทธิทั้งหมด
ทุกคนยินดีต้อนรับกลับไปยังส่วน
ฉันหวังว่าคุณทุกคนจะประสบความสำเร็จ หายจากการทดสอบของคุณ
จากสัปดาห์ก่อน
ฉันรู้ว่ามันนิด ๆ หน่อย ๆ บ้าในบางครั้ง
ขณะที่ผมกำลังบอกก่อนถ้าคุณอยู่ ภายในส่วนเบี่ยงเบนมาตรฐาน
ไม่ต้องกังวลเกี่ยวกับเรื่องนี้โดยเฉพาะอย่างยิ่ง สำหรับส่วนที่สะดวกสบายน้อยกว่า
ที่เกี่ยวกับการที่คุณควรจะ
>> ถ้าคุณไม่ดี, น่ากลัวแล้ว
รุ่งโรจน์เพื่อคุณ
และถ้าคุณรู้สึกว่าคุณต้อง นิด ๆ หน่อย ๆ ความช่วยเหลือเพิ่มเติมกรุณา
อย่าลังเลที่จะไปให้ถึง ออกไปใด ๆ ของ TFS
เราทุกคนที่นี่เพื่อช่วย
>> นั่นเป็นเหตุผลที่เราสอน
นั่นเป็นเหตุผลที่ผมมาที่นี่ทุกวันจันทร์สำหรับคุณ คนและในเวลาทำการในวันพฤหัสบดี
ดังนั้นโปรดอย่าลังเลที่จะแจ้งให้เราทราบ ถ้าคุณกังวลเกี่ยวกับอะไร
หรือถ้ามีอะไรที่เกี่ยวกับการทดสอบ ที่คุณต้องการจริงๆชอบที่จะอยู่
>> ดังนั้นวาระการประชุมสำหรับวันนี้เป็น ทั้งหมดเกี่ยวกับโครงสร้างข้อมูล
บางส่วนของเหล่านี้เป็นเพียงการไปได้เพียงแค่ เพื่อให้ได้คุ้นเคยกับสิ่งเหล่านี้
ที่คุณอาจไม่เคยใช้ พวกเขาในชั้นนี้
บางส่วนของพวกเขาที่คุณจะ เหมือน pset สะกดของคุณ
>> คุณจะมีตัวเลือกของคุณ ระหว่างตารางแฮชและพยายาม
ดังนั้นเราจะมั่นเหมาะจะไปกว่านั้น
มันเป็นไปได้แน่นอนมากขึ้นของชนิด ส่วนในระดับที่สูงในวันนี้แม้ว่า
เพราะมีจำนวนมากของพวกเขาและถ้า เราเดินเข้าไปในรายละเอียดการดำเนินการ
ในทุกเหล่านี้เราจะไม่ แม้จะได้รับผ่านรายการเชื่อมโยง
และอาจจะนิด ๆ หน่อย ๆ ของตารางแฮช
>> ดังนั้นอดทนกับฉัน
เราไม่ได้จะต้องทำ เท่าเข้ารหัสเวลานี้
หากคุณมีคำถามใด ๆ เกี่ยวกับเรื่องนี้ หรือคุณต้องการที่จะเห็นมันดำเนินการ
หรือลองด้วยตัวคุณเอง แน่นอนผมขอแนะนำให้
จะ study.cs50.net ซึ่ง มีตัวอย่างของสิ่งเหล่านี้
มันจะมี PowerPoints ของฉัน กับบันทึกที่เรา
มีแนวโน้มที่จะใช้เช่นเดียวกับการเขียนโปรแกรมบางอย่าง การออกกำลังกายโดยเฉพาะอย่างยิ่งสำหรับสิ่งที่
เช่นรายการเชื่อมโยงและไบนารี กองต้นไม้และความหมาย
เล็ก ๆ น้อย ๆ ดังนั้นในระดับสูงมากขึ้นซึ่ง อาจจะดีสำหรับพวกคุณ
>> ดังนั้นด้วยความที่เราจะเริ่มต้น
และยัง yes-- แบบทดสอบ
ผมคิดว่าส่วนใหญ่ของคุณที่อยู่ใน ส่วนของผมมีแบบทดสอบของคุณ
แต่ทุกคนมาในหรือเหตุผลบางอย่างที่คุณ ไม่ได้พวกเขาที่นี่ในด้านหน้า
>> รายการเชื่อมโยงดังนั้น
ฉันรู้ว่าแบบนี้ไป การสำรองข้อมูลก่อนที่จะตอบคำถามของคุณ
นั่นคือเมื่อสัปดาห์ก่อน ที่เราได้เรียนรู้เกี่ยวกับเรื่องนี้
แต่ในกรณีนี้เราจะเพียงแค่ ไปนิด ๆ หน่อย ๆ เพิ่มเติมในเชิงลึก
>> ดังนั้นทำไมเราจะเลือก รายการที่เชื่อมโยงมากกว่าอาร์เรย์?
แตกต่างพวกเขาคืออะไร?
ใช่?
>> ผู้ชม: คุณสามารถขยายการเชื่อมโยง รายการเมื่อเทียบกับขนาดคงอาร์เรย์
ลำโพง 1: ขวา
อาเรย์ได้กำหนดขนาดในขณะที่ รายการที่เชื่อมโยงมีขนาดตัวแปร
ดังนั้นหากเราไม่ทราบว่า มากที่เราต้องการในการจัดเก็บ
รายการที่เชื่อมโยงจะช่วยให้เราดี วิธีการที่จะทำอย่างนั้นเพราะเราสามารถทำได้เพียงแค่
เพิ่มในโหนดอื่นและเพิ่ม โหนดอื่นและเพิ่มในโหนดอื่น
แต่สิ่งที่อาจจะมีการออก?
ไม่มีใครจำได้ว่าการออก ระหว่างอาร์เรย์และรายการเชื่อมโยง?
mmhmm?
>> ผู้ชม: คุณต้อง ผ่านไปตลอดทาง
ผ่านรายการที่เชื่อมโยง หาองค์ประกอบในรายการ
ในอาร์เรย์คุณสามารถ เพียงแค่หาองค์ประกอบ
>> ลำโพง 1: ขวา
ดังนั้นด้วย arrays--
>> ผู้ชม: [ไม่ได้ยิน]
>> ลำโพง 1: ด้วยอาร์เรย์เรามี สิ่งที่เรียกว่าการเข้าถึงแบบสุ่ม
หมายความว่าถ้าเราต้องการสิ่งที่เป็น ที่เคยเป็นจุดที่ห้าของรายการ
หรือจุดที่ห้าของเรา อาเรย์เราก็สามารถคว้ามัน
หากเป็นรายการที่เชื่อมโยงเรามี เพื่อย้ำผ่านใช่มั้ย?
ดังนั้นการเข้าถึงองค์ประกอบใน อาร์เรย์เป็นเวลาที่คงที่
ในขณะที่มีการเชื่อมโยงรายการมันจะ ส่วนใหญ่จะเป็นเส้นเวลาเพราะอาจจะ
องค์ประกอบของเรามีทุกอย่างในตอนท้าย
เรามีการค้นหาผ่านทุกอย่าง
ดังนั้นด้วยข้อมูลทั้งหมดเหล่านี้ โครงสร้างที่เรากำลังจะ
ที่จะใช้เวลามากขึ้นเล็ก ๆ น้อย ๆ , สิ่งที่เป็นบวกและเชิงลบ
เมื่อเราอาจต้องการที่จะ ใช้หนึ่งในช่วงอื่น ๆ ?
และนั่นคือชนิดของ สิ่งที่ใหญ่กว่าที่จะไป
>> เพื่อให้เรามีที่นี่ ความหมายของโหนด
มันก็เหมือนกับองค์ประกอบหนึ่งใน รายการที่เชื่อมโยงของเราใช่มั้ย?
ดังนั้นเราทุกคนคุ้นเคย กับ structs typedef ของเรา
ที่เราเดินไปในการตรวจสอบครั้งสุดท้าย
มันเป็นเพียงแค่การสร้างพื้น ชนิดข้อมูลอื่นที่เราสามารถใช้
>> และในกรณีนี้มันเป็นบางโหนด ที่จะถือจำนวนเต็มบางอย่างใน
และแล้วสิ่งที่เป็นส่วนที่สองที่นี่?
ใคร?
>> ผู้ชม: [ไม่ได้ยิน]
>> ลำโพง 1: ใช่
มันเป็นตัวชี้ไปยังโหนดถั​​ดไป
ดังนั้นนี้จริงควรจะขึ้นที่นี่
นี้เป็นตัวชี้ประเภท โหนดสิ่งต่อไปที่
และนั่นคือสิ่งที่พวกเขา ครอบคลุมโหนดของเรา
เย็น
>> สิทธิทั้งหมดเพื่อให้มีการค้นหาในขณะที่เรามี เพียงแค่บอกว่าก่อนที่มือถ้าคุณ
จะค้นหาผ่าน, คุณต้องย้ำจริง
ผ่านรายการที่เชื่อมโยงของคุณ
ดังนั้นหากเรากำลังมองหาตัวเลข 9 เราจะเริ่มต้นที่หัวของเรา
และที่ชี้ให้เราที่จุดเริ่มต้น ของรายการที่เชื่อมโยงของเราใช่มั้ย?
และเราบอกว่าโอเคไม่นี้ โหนดมีจำนวน 9?
ไม่มี?
>> สิทธิทั้งหมดไปที่หนึ่งต่อไป
ทำตามมัน
มันมีจำนวน 9?
เลขที่
ทำตามอย่างใดอย่างหนึ่งต่อไป
>> ดังนั้นเราต้องย้ำจริง ผ่านรายการที่เชื่อมโยงของเรา
เราก็ไม่สามารถไปที่ 9 เป็น
และถ้าพวกคุณจริงต้องการ เห็นบางนามแฝงรหัสขึ้นมี
เรามีฟังก์ชันการค้นหาบางส่วนที่นี่ ที่ใช้เวลา in-- สิ่งที่ไม่ได้ใช้มีอะไรบ้าง?
คุณคิดอย่างไร?
เพื่อให้ง่ายต่อหนึ่ง
นี่คืออะไร?
ผู้ชม: [ไม่ได้ยิน]
ลำโพง 1: จำนวนที่เรากำลังมองหา
ใช่มั้ย?
และสิ่งนี้จะสอดคล้องกับ?
มันเป็นตัวชี้ไปยัง?
>> ผู้ชม: โหนด
>> ลำโพง 1: โหนดในรายการ ที่เรากำลังมองหาที่ใช่มั้ย?
ดังนั้นเราจึงมีบางโหนดเป็นตัวชี้ที่นี่
ตรงนี้คือจุดที่จะ จริงย้ำผ่านรายการของเรา
เราตั้งค่ามันเท่ากันในรายการ เนื่องจากว่าเป็นเพียง
การตั้งค่าเท่ากับ จุดเริ่มต้นของรายการที่เชื่อมโยงของเรา
>> และในขณะที่มันไม่ได้เป็นโมฆะขณะที่ เรายังคงมีสิ่งที่อยู่ในรายชื่อของเรา
ตรวจสอบเพื่อดูว่าโหนดที่มี จำนวนที่เรากำลังมองหา
กลับจริง
มิฉะนั้น update มันใช่มั้ย?
>> ถ้ามันเป็นโมฆะเราออกจากเรา ในขณะที่วงและกลับเท็จ
เพราะนั่นหมายความว่าเราไม่ได้พบว่ามัน
ทุกคนได้รับว่าทำงานอย่างไร
ตกลง
>> ดังนั้นด้วยการแทรกคุณ มีสามวิธีที่แตกต่างกัน
คุณสามารถ prepend คุณสามารถผนวก และคุณสามารถใส่ลงในสารพัน
ในกรณีนี้เราไม่ จะทำย่อหน้า
ไม่มีใครรู้ว่าผู้ที่ สามกรณีอาจแตกต่างกัน?
>> ดังนั้นย่อหน้าหมายความว่าคุณใส่ มันที่ด้านหน้าของรายการของคุณ
เพื่อที่จะหมายถึงว่าไม่ว่า สิ่งที่โหนดของคุณไม่ว่า
สิ่งที่มีค่าเป็นคุณจะ ที่จะนำมันที่นี่ในหน้า, OK?
มันจะเป็นครั้งแรก องค์ประกอบในรายการของคุณ
>> ถ้าคุณผนวกก็จะ เพื่อไปยังด้านหลังของรายการของคุณ
และใส่ลงในสารพันหมายความว่าคุณ จะใส่เข้าไปในสถานที่จริง
ที่จะช่วยให้รายการที่เชื่อมโยงที่เรียงลำดับ
อีกวิธีที่คุณใช้ เหล่านั้นและเมื่อคุณใช้
พวกเขาจะแตกต่างกันขึ้นอยู่กับกรณีของคุณ
ถ้ามันไม่จำเป็นต้อง ถูกจัดเรียงย่อหน้ามีแนวโน้มที่
จะเป็นสิ่งที่คนส่วนใหญ่ ใช้เพราะคุณทำไม่ได้
ต้องผ่านรายการทั้งหมด ที่จะหาจุดสิ้นสุดที่จะเพิ่มในใช่มั้ย?
คุณก็สามารถติดอยู่ใน
>> ดังนั้นเราจะไปถึง แทรก 1 ได้ในขณะนี้
ดังนั้นสิ่งหนึ่งที่ฉันจะ ขอแนะนำให้ใน pset นี้
คือการวาดสิ่งที่ออกเช่นเคย
มันเป็นสิ่งสำคัญมากที่คุณอัปเดต ตัวชี้ของคุณในลำดับที่ถูกต้อง
เพราะถ้าคุณปรับปรุงพวกเขา เล็กน้อยออกคำสั่ง
คุณกำลังจะจบลง ส่วนการสูญเสียของรายการของคุณ
>> ดังนั้นสำหรับตัวอย่างเช่นในกรณีนี้เราไม่ บอกหัวเพียงแค่จุดที่ 1
ถ้าเราเพียงแค่ทำอย่างนั้น โดยไม่บันทึก 1 นี้
เรามีความคิดว่า 1 ควรชี้ไปตอนนี้
เพราะเราได้สูญเสียสิ่งที่ หัวชี้ไปที่
ดังนั้นสิ่งหนึ่งที่ต้องจำไว้ เมื่อคุณกำลังทำย่อหน้า
คือการบันทึกสิ่งที่ มุ่งหน้าไปยังจุดแรก
แล้วกำหนดมันแล้วปรับปรุง สิ่งที่โหนดใหม่ของคุณควรชี้ไป
ในกรณีนี้เป็นวิธีหนึ่งที่จะทำมัน
>> ดังนั้นหากเราได้ทำมันด้วยวิธีนี้ ซึ่งเราก็มีพระราชเสาวนีย์หัว
เราสูญเสียโดยทั่วไปของเรา รายการทั้งหมดใช่มั้ย?
วิธีหนึ่งที่จะทำก็คือการมี 1 ชี้ไปที่ ถัดไปและจากนั้นมีจุดหัว 1
หรือคุณสามารถทำชนิดเช่น จัดเก็บชั่วคราวที่ฉันพูดคุยเกี่ยวกับ
>> แต่มอบหมายงานใหม่ของคุณ ตัวชี้ในลำดับที่ถูกต้อง
เป็นไปได้มาก สิ่งสำคัญสำหรับ pset นี้
มิฉะนั้นคุณจะต้องกัญชา ตารางหรือพยายามที่เพียงแค่จะเป็น
เพียงส่วนหนึ่งของคำที่คุณ ต้องการแล้ว mmhmm you're--?
ผู้ชม: อะไรคือสิ่งที่ชั่วคราว สิ่งที่จัดเก็บข้อมูลที่คุณกำลังพูดถึง?
ลำโพงที่ 1: การจัดเก็บชั่วคราว
ดังนั้นโดยทั่วไปอีก วิธีการที่คุณสามารถทำเช่นนี้
มีการเก็บหัวของบางอย่างเช่น เก็บไว้ตัวแปรชั่วคราว
กำหนดให้ 1 และ แล้ว update 1 ที่จะชี้
สิ่งที่หัวที่ใช้ในการชี้ไปที่
วิธีนี้จะเห็นได้ชัด สง่างามมากขึ้นเพราะคุณ
ไม่จำเป็นต้องมีค่าชั่วคราว แต่ เพียงแค่นำเสนอวิธีที่จะทำมันอีก
และเราทำจริงได้ รหัสบางอย่างสำหรับการนี​​้
ดังนั้นสำหรับรายการที่เชื่อมโยงเรา จริงมีโค้ดบางส่วน
ดังนั้นที่นี่ใส่นี้ prepending
ดังนั้นนี่มันเข้าที่หัว
>> ดังนั้นสิ่งแรกที่คุณจะต้อง สร้างโหนดใหม่ของคุณแน่นอน
และตรวจสอบเป็นโมฆะ
ดีอยู่เสมอ
และจากนั้นคุณต้องกำหนดค่า
เมื่อใดก็ตามที่คุณสร้างโหนดใหม่คุณ ไม่ทราบว่าสิ่งที่มันชี้ไปข้างหน้า
ดังนั้นคุณจึงต้องการที่จะเริ่มต้นให้ NULL
ถ้ามันไม่จบลงด้วยการชี้ไปที่บางสิ่งบางอย่าง อื่น ๆ จะได้รับพระราชเสาวนีย์และก็ปรับ
ถ้ามันเป็นสิ่งแรก ในรายการก็ต้อง
ให้ชี้ไปที่ NULL เพราะ ที่ตอนท้ายของรายการ
>> ดังนั้นแล้วการใส่เราเห็นที่นี่เรา มีการกำหนดค่าถัดไปของโหนดของเรา
จะเป็นสิ่งที่หัวคือ ซึ่งเป็นสิ่งที่เรามีที่นี่
นั่นคือสิ่งที่เราได้ทำ
และจากนั้นเราจะกำหนดหัวไปยังจุด ไปยังโหนดใหม่ของเราเพราะจำ
ใหม่เป็นตัวชี้บางโหนด และนั่นคือสิ่งที่เป็นหัว
ที่ว่าทำไมเรา มีผู้เข้าใช้ลูกศรนี้
เย็น?
mmhmm?
>> ผู้ชม: เราต้อง เริ่มต้นต่อใหม่เพื่อ NULL แรก
หรือเราสามารถเพียงแค่เริ่มต้นมันที่หัว?
>> ลำโพง 1: ใหม่ต่อไป ความต้องการที่จะเป็นโมฆะในการเริ่มต้น
เพราะคุณไม่ทราบ ที่มันจะเป็น
นอกจากนี้เป็นชนิดของ เช่นเดียวกระบวนทัศน์
คุณตั้งค่าเท่ากับเป็นโมฆะเพียงเพื่อให้ แน่ใจหรือว่าฐานของคุณทั้งหมดจะถูกปกคลุม
ก่อนที่จะทำการโอนใด ๆ เพื่อให้ คุณกำลังรับประกันเสมอว่ามันจะ
จะชี้ไปยังค่าที่ระบุ เมื่อเทียบกับค่าเช่นขยะ
เพราะใช่เรากำหนด ใหม่ต่อไปโดยอัตโนมัติ
แต่มันก็มากขึ้นเช่นเดียวกับ การปฏิบัติที่ดีในการเริ่มต้นมัน
ในทางที่กำหนดแล้ว
>> ตกลงเชื่อมโยงอย่างทวีคูณรายการตอนนี้
เราคิดอย่างไร?
สิ่งที่แตกต่างกันด้วย รายการที่เชื่อมโยงทวีคูณ?
>> ดังนั้นในรายการเชื่อมโยงของเราเราสามารถ เพียงย้ายในทิศทางเดียวใช่มั้ย?
เรามีเพียงต่อไป
เราสามารถก้าวไปข้างหน้า
>> กับรายการที่เชื่อมโยงทวีคูณ เรายังสามารถย้ายไปข้างหลัง
ดังนั้นเราจึงมีไม่เพียง ตัวเลขที่เราต้องการในการจัดเก็บ
เรามีที่ชี้ไปยัง และที่เราเพิ่งมาจาก
ดังนั้นนี้ช่วยให้การ บางสำรวจเส้นทางที่ดีกว่า
>> ดังนั้นการเชื่อมโยงโหนดทวีคูณ คล้ายกันมากใช่มั้ย?
เพียง แต่ความแตกต่างก็คือตอนนี้เรา มีต่อไปและก่อนหน้านี้
มันเป็นเรื่องที่แตกต่าง
>> ดังนั้นถ้าเราจะ prepend หรือเรา append-- ไม่มีรหัสใด ๆ สำหรับการนี​​้ขึ้นตรงนี้
แต่ถ้าคุณได้ลอง ใส่สิ่งที่สำคัญ
เป็นที่คุณต้องทำ แน่ใจว่าคุณกำลังกำหนด
ทั้งของคุณก่อนหน้านี้และของคุณ ตัวชี้ต่อไปได้อย่างถูกต้อง
ดังนั้นในกรณีนี้คุณจะ ไม่เพียง แต่การเริ่มต้นต่อไป
คุณเริ่มต้นที่ก่อนหน้านี้
ถ้าเราอยู่ที่หัวของรายการเรา จะไม่เพียง แต่ทำให้หัวเท่ากับใหม่
แต่ควรที่ก่อนหน้าใหม่ของเรา ชี้ไปที่หัวใช่มั้ย?
>> นั่นคือความแตกต่างเท่านั้น
และถ้าคุณต้องการการปฏิบัติมากยิ่งขึ้นด้วย เหล่านี้ด้วยรายการที่เชื่อมโยงกับการแทรก
ด้วยการลบด้วยการแทรก เป็นรายการสารพัน
โปรดตรวจสอบ study.cs50.net
มีพวงของการออกกำลังกายที่ดีคือ
ผมขอแนะนำให้พวกเขา
ฉันหวังว่าเรามีเวลาที่จะไปถึงพวกเขา แต่มีจำนวนมากของโครงสร้างข้อมูลเป็น
จะได้รับผ่าน
>> ตกลงดังนั้นตารางแฮช
นี่อาจจะเป็นส่วนใหญ่ บิตมีประโยชน์สำหรับ pset ของคุณ
นี่เพราะคุณกำลังจะเป็น การดำเนินการอย่างใดอย่างหนึ่งเหล่านี้หรือลอง
ฉันชอบตารางแฮช
พวกเขากำลังเย็นสวย
>> ดังนั้นโดยทั่วไปสิ่งที่ ที่เกิดขึ้นคือตารางแฮช
คือเมื่อเราต้องการจริงๆได้อย่างรวดเร็ว แทรกการลบและการค้นหา
เหล่านี้คือสิ่งที่เรากำลัง จัดลำดับความสำคัญในตารางแฮช
พวกเขาจะได้รับใหญ่สวย แต่ที่เราจะเห็นด้วยพยายาม
มีสิ่งที่มีขนาดใหญ่มาก
>> แต่โดยทั่วไปทั้งหมดกัญชา ตารางฟังก์ชันแฮช
ที่จะบอกคุณซึ่งถังที่จะใส่ในแต่ละ ข้อมูลของคุณแต่ละองค์ประกอบของคุณใน
วิธีง่ายๆในการคิดของตารางแฮช ก็คือว่ามันเป็นเพียงถังของสิ่ง
ใช่มั้ย?
ดังนั้นเมื่อคุณมีการเรียงลำดับสิ่งที่โดย เช่นอักษรตัวแรกของชื่อของพวกเขา
นั่นคือชนิดเช่นตารางแฮช
>> ดังนั้นถ้าผมให้กับกลุ่มพวกคุณเป็น เป็นกลุ่มของใครก็ตามที่ชื่อเริ่ม
กับที่นี่หรือใครก็ตามที่เป็นวันเกิด ในเดือนมกราคม, กุมภาพันธ์, มีนาคม
อะไรก็ตามที่เป็นได้อย่างมีประสิทธิภาพ การสร้างตารางแฮช
มันเป็นเพียงแค่การสร้างถังที่ คุณเรียงลำดับองค์ประกอบของคุณให้เป็น
เพื่อให้คุณสามารถค้นหาได้ง่ายขึ้น
ดังนั้นวิธีที่ฉันต้องการ ที่จะหาหนึ่งของคุณ,
ฉันไม่ได้มีการค้นหา ผ่านแต่ละชื่อของคุณ
ฉันจะเป็นเหมือนโอ้ฉันรู้ว่า วันเกิดของแดเนียลเป็น in--
ผู้ชม: --April
ลำโพง 1: เมษายน
ดังนั้นผมจึงมองในของฉันเมษายน ถังและมีโชคใด ๆ
เธอจะเป็นเพียงหนึ่งในการมีและ เวลาของฉันเป็นอย่างต่อเนื่องในความรู้สึกที่
ในขณะที่ถ้าผมต้องมอง ผ่านทั้งกลุ่มของผู้คน
มันจะใช้เวลานานมาก
ดังนั้นตารางแฮชมีจริงๆเพียงแค่ถัง
วิธีง่ายๆในการคิดว่าพวกเขา
>> ดังนั้นสิ่งที่สำคัญมากเกี่ยวกับ ตารางแฮชเป็นฟังก์ชันแฮช
ดังนั้นสิ่งที่ฉันเพียงแค่พูดคุยเกี่ยวกับเช่น ตัวอักษรตัวแรกของชื่อของคุณ
หรือเดือนวันเกิดของคุณ เหล่านี้เป็นความคิดที่ว่า
จริงๆมีความสัมพันธ์กับฟังก์ชันแฮช
มันเป็นเพียงวิธีการที่จะตัดสินใจซึ่ง ถังองค์ประกอบคุณกำลังจะเข้าสู่, OK?
ดังนั้นสำหรับ pset นี้คุณสามารถดู สวยมากฟังก์ชันแฮชที่คุณต้องการ
>> ไม่จำเป็นต้องเป็นของคุณเอง
มีบางคนที่เจ๋งจริงๆจะออก มีที่ทำทุกประเภทของคณิตศาสตร์บ้า
และถ้าคุณต้องการที่จะทำให้คุณ เช็คคำสะกดเร็วสุด
ฉันจะแน่นอน มองเข้าไปในหนึ่งในบรรดา
>> แต่ยังมี คนที่เรียบง่ายเช่นเดียวกับการคำนวณ
ผลรวมของคำเช่น ตัวอักษรแต่ละตัวมีจำนวน
คำนวณผลบวก
ที่กำหนดถั​​ง
พวกเขายังมีคนง่ายว่า ก็เป็นเหมือนทุกคนของที่นี่
ทั้งหมดของ B ที่นี่
หนึ่งในบรรดาการใด ๆ
>> โดยทั่วไปก็แค่จะบอกคุณที่ ดัชนีอาร์เรย์องค์ประกอบของคุณควรจะไปเป็น
เพียงแค่การตัดสินใจ bucket-- มันคือทั้งหมดที่ฟังก์ชันแฮชเป็น
ดังนั้นที่นี่เรามีตัวอย่างซึ่งเป็น เพียงแค่ตัวอักษรตัวแรกของสตริง
ว่าฉันเป็นเพียงการพูดคุยเกี่ยวกับ
>> เพื่อให้คุณมีกัญชานั่นเป็นเพียงบางส่วน ตัวอักษรตัวแรกของสตริงลบของคุณ
ซึ่งจะให้คุณบาง ตัวเลขระหว่าง 0 และ 25
และสิ่งที่คุณต้องการจะทำคือ ตรวจสอบให้แน่ใจว่าเรื่องนี้แสดงให้เห็นถึง
ขนาดของกัญชาของคุณ table-- กี่ถังมี
มีหลายเหล่านี้ ฟังก์ชันแฮชพวกเขากำลัง
จะได้รับการกลับค่าที่อาจจะ จะสูงกว่าจำนวนที่เก็บข้อมูล
จริงที่คุณมี ในตารางแฮชของคุณ
ดังนั้นคุณต้องทำให้ ตรวจสอบและสมัยโดยผู้
มิฉะนั้นก็จะพูดว่า โอ้มันควรจะเป็นในถัง 5,000
แต่คุณมีเวลา 30 เท่านั้น ถังในตารางแฮชของคุณ
และแน่นอนเราทุกคนรู้ว่า จะส่งผลให้เกิดข้อผิดพลาดบางบ้า
เพื่อให้แน่ใจว่าการพอควรโดย ขนาดของตารางแฮชของคุณ
เย็น
ดังนั้นการชน
ทุกคนที่ดีเพื่อให้ห่างไกล?
mmhmm?
>> ผู้ชม: ทำไมมัน กลับดังกล่าวมีมูลค่าขนาดใหญ่?
>> ลำโพง 1: ขึ้นอยู่กับขั้นตอนวิธี ว่าฟังก์ชันแฮชของคุณใช้
บางส่วนของพวกเขาจะทำ คูณบ้า
และมันคือทั้งหมดที่เกี่ยวกับการ กระจาย,
เพื่อให้พวกเขาทำบางอย่างจริงๆ สิ่งที่บ้าบางครั้ง
นั่นคือทั้งหมดที่
อะไรอีกหรือไม่
ตกลง
>> ดังนั้นการชน
โดยทั่วไปที่ผมกล่าวว่าก่อนหน้านี้ ในสถานการณ์กรณีที่ดีที่สุด
ถังใด ๆ ที่ฉันมองเข้าไปในเป็น จะมีสิ่งหนึ่งที่
ดังนั้นผมจึงไม่ต้องมองเลยใช่มั้ย?
ฉันอาจรู้ว่ามันมีหรือเป็น ไม่ได้และนั่นคือสิ่งที่เราต้องการจริงๆ
แต่ถ้าเรามีนับหมื่นของ จุดข้อมูลและน้อยกว่าตัวเลขที่
ของถังที่เรากำลังจะมี ชนที่ท้ายที่สุดสิ่งที่
เป็นไปได้ที่จะจบลงใน ถังที่มีอยู่แล้วองค์ประกอบ
>> ดังนั้นคำถามคือสิ่งที่ เราจะทำในกรณีที่?
ทำในสิ่งที่เราจะทำอย่างไร
เรามีบางสิ่งบางอย่างที่นั่น?
เราเพียงแค่โยนมันออกมา?
>> เลขที่
เราต้องให้ทั้งสองของพวกเขา
ดังนั้นวิธีการที่เรา ที่มักจะทำคืออะไร?
เป็นโครงสร้างข้อมูลอะไร เราก็พูดคุยกันเกี่ยวกับ?
ผู้ชม: รายการที่เชื่อมโยง
ลำโพง 1: รายการที่เชื่อมโยง
ดังนั้นตอนนี้แทนแต่ละเหล่านี้ ถังเพียงแค่มีองค์ประกอบหนึ่ง,
มันจะมีรายการที่เชื่อมโยงของ องค์ประกอบที่ถูกถกลงไป
ตกลงทุกคนไม่ได้รับชนิดของความคิดที่ว่า?
เพราะเราไม่สามารถมีอาร์เรย์ เพราะเราไม่ทราบว่าหลายสิ่งหลายอย่าง
เป็นไปได้ในการมี
รายการที่เชื่อมโยงช่วยให้เราสามารถ มีเพียงจำนวนที่แน่นอนว่า
มี hashed ลงในถังที่ใช่มั้ย?
>> ดังนั้นเส้นละเอียดเป็น พื้น idea-- นี้
มันเป็นวิธีหนึ่งที่จะจัดการกับการปะทะกัน
สิ่งที่คุณสามารถทำได้คือถ้าในเรื่องนี้ กรณีที่ถูกแบล็กเบอร์ hashed เป็น 1
และเรามีอยู่แล้ว สิ่งที่มีคุณเพียงแค่
ให้ไปลงจน คุณจะพบช่องว่าง
นั่นเป็นวิธีหนึ่งที่จะจัดการกับมัน
วิธีอื่น ๆ ในการจัดการ มันขึ้นอยู่กับสิ่งที่เราเพียง
called-- ที่เชื่อมโยง รายการที่เรียกว่าการผูกมัด
>> ดังนั้นความคิดนี้ทำงานถ้า ตารางแฮชของคุณที่คุณคิดว่า
มีขนาดใหญ่กว่า ข้อมูลของคุณตั้งค่าหรือถ้าคุณ
ต้องการที่จะลองและลดการผูกมัด จนกว่าจะมีความจำเป็นอย่างยิ่ง
ดังนั้นสิ่งหนึ่งที่เป็นเส้นตรง เห็นได้ชัดว่าหมายถึงละเอียด
ว่าฟังก์ชันแฮชของคุณ ไม่มากที่เป็นประโยชน์
เพราะคุณกำลังจะสิ้นสุดการใช้ ฟังก์ชันแฮชของคุณได้รับไปยังจุดที่
คุณ Linear สอบสวนลงไป สถานที่ที่มีอยู่บางส่วน
แต่ตอนนี้แน่นอนอะไร อื่น ๆ ที่จบลงที่นั่น
คุณจะต้อง ค้นหายิ่งขึ้นลง
>> และมีมากขึ้น ค่าใช้จ่ายในการค้นหาที่
จะเข้าสู่ป้อนองค์ประกอบ ในตารางแฮชของคุณตอนนี้ใช่มั้ย?
และตอนนี้เมื่อคุณไปและพยายามหา เบอร์รี่อีกครั้งคุณกำลังจะสับมัน
และมันจะพูดว่า โอ้ดูในถังที่ 1
และก็จะไม่ได้ ในถังที่ 1 เพื่อให้คุณ
จะมีการสำรวจ ส่วนที่เหลือของเหล่านี้
ดังนั้นจึงเป็นเรื่องที่มีประโยชน์บางครั้ง แต่ในกรณีส่วนใหญ่
เรากำลังจะบอกว่า ผูกมัดคือสิ่งที่คุณต้องการจะทำ
>> ดังนั้นเราได้พูดคุยเกี่ยวกับเรื่องนี้ก่อนหน้านี้
ผมได้น้อยหน้าของตัวเอง
แต่การผูกมัดเป็นพื้นว่า ถังในตารางแฮชของคุณในแต่ละ
เป็นเพียงรายการที่เชื่อมโยง
>> ดังนั้นวิธีอื่นหรือทางเทคนิคเพิ่มเติม วิธีการคิดของตารางแฮช
คือว่ามันเป็นเพียงแค่อาร์เรย์ ของรายการที่เชื่อมโยงซึ่ง
เมื่อคุณกำลังเขียนพจนานุกรมของคุณ และคุณกำลังพยายามที่จะโหลดมัน
คิดว่ามันเป็น อาร์เรย์ของรายการเชื่อมโยง
จะทำให้มันง่ายมาก สำหรับคุณที่จะเริ่มต้น
>> ผู้ชม: ดังนั้นตารางแฮช มีขนาดที่กำหนดไว้
เช่น [ไม่ได้ยิน] ของถัง?
>> ลำโพง 1: ขวา
ดังนั้นจึงมีจำนวนชุดของ ถังที่คุณ determine--
ซึ่งพวกคุณควร อย่าลังเลที่จะเล่นกับ
มันอาจจะเป็นเย็นสวย เพื่อดูสิ่งที่เกิดขึ้น
ในขณะที่คุณเปลี่ยนจำนวนของถัง
แต่ใช่มันมี กำหนดจำนวนของถัง
สิ่งที่ช่วยให้คุณเพื่อให้พอดีกับเป็น หลายองค์ประกอบตามที่คุณต้องการ
คือที่กำลังแยกนี้ที่คุณ มีการเชื่อมโยงรายชื่อในแต่ละถัง
นั่นหมายความว่าตารางแฮชของคุณ จะตรงขนาด
ที่คุณต้องการให้เป็นใช่มั้ย?
นั่นเป็นจุดรวมของรายการที่เชื่อมโยง
เย็น
>> เพื่อให้ทุกคนตกลงที่นั่น?
สิทธิ์ทั้งหมด
อา
สิ่งที่เพิ่งเกิดขึ้น?
จริงๆตอนนี้
คิดว่าคนที่ฆ่าฉัน
>> ตกลงเราจะไปสู่ พยายามที่จะบ้าเล็กน้อย
ฉันชอบตารางแฮช
ผมคิดว่าพวกเขากำลังเย็นจริงๆ
พยายามที่จะเย็นเกินไป
>> เพื่อให้ทุกคนไม่จำสิ่งที่พยายามคืออะไร?
คุณควรจะได้หายไปกว่า มันสั้นในการบรรยาย?
คุณจำชนิดของมันทำงานอย่างไร
ผู้ชม: ฉันแค่พยักหน้า ว่าเราไม่ไปกว่านั้น
ลำโพง 1: เราไม่ไปกว่านั้น
ตกลงเราจริงๆจะไป กว่าตอนนี้มันคือสิ่งที่เรากำลังจะบอกว่า
>> ผู้ชม: นั่นคือสำหรับการดึงต้นไม้
>> ลำโพง 1: ใช่
มันเป็นต้นไม้ดึง
น่ากลัว
ดังนั้นสิ่งหนึ่งที่จะสังเกตเห็นที่นี่คือเรา กำลังมองหาที่ตัวละครแต่ละคน
ที่นี่ใช่มั้ย?
>> ดังนั้นก่อนที่จะมีฟังก์ชันแฮชของเราเรา กำลังหาที่คำพูดโดยรวม
และตอนนี้เรากำลังมองหามากขึ้น ที่ตัวละครใช่มั้ย?
ดังนั้นเราจึงมีแมกซ์เวลที่นี่และเมนเดล
ดังนั้นโดยทั่วไป try-- วิธีที่จะคิดว่า เกี่ยวกับเรื่องนี้คือการที่ทุกระดับที่นี่
เป็นอาร์เรย์ของตัวอักษร
ดังนั้นนี่คือโหนดรากของคุณที่นี่ใช่มั้ย?
นี้มีตัวอักษรทั้งหมดของ ตัวอักษรสำหรับการเริ่มต้นของทุกคำ
>> และสิ่งที่คุณต้องการจะทำคือ กล่าวว่าตกลงเรามีบางคำ M
เรากำลังจะไปมองหาแมกซ์เวลดังนั้น เราไปที่เอ็มและเอ็มชี้ไปที่ทั้ง
อาร์เรย์อื่น ๆ ที่ทุก คำตราบใดที่มี
เป็นคำที่มี เป็นจดหมายฉบับที่สอง,
ตราบใดที่มีคำว่า มี B เป็นจดหมายฉบับที่สอง,
มันจะมีตัวชี้ จะบางอาร์เรย์ต่อไป
>> มีไม่น่าจะเป็น คำว่าสิ่งที่ส
ดังนั้นที่ตำแหน่ง P ในครั้งนี้ อาเรย์มันก็จะเป็นโมฆะ
มันจะบอกว่าตกลงมีคำว่าไม่มี ที่มี M ตามด้วย P, OK?
ดังนั้นหากเราคิดเกี่ยวกับมันแต่ละ หนึ่งในสิ่งที่มีขนาดเล็กเหล่านี้
เป็นจริงหนึ่งในจำนวนนี้ อาร์เรย์ขนาดใหญ่จากถึง Z
ดังนั้นสิ่งที่อาจจะเป็นหนึ่งในสิ่งที่ ว่าเป็นชนิดของข้อบกพร่องของลอง?
>> ผู้ชม: จำนวนมากของหน่วยความจำ
>> ลำโพง 1: มันเป็นตันของหน่วยความจำใช่มั้ย?
หนึ่งแต่ละบล็อกเหล่านี้ที่นี่ แสดงให้เห็นถึงช่องว่างที่ 26, 26 องค์ประกอบอาร์เรย์
ดังนั้นพยายามที่ได้รับอย่างไม่น่าเชื่อพื้นที่หนัก
>> แต่พวกเขามีความรวดเร็วมาก
อย่างรวดเร็วอย่างไม่น่าเชื่อ แต่ จริงๆพื้นที่ไม่มีประสิทธิภาพ
ชนิดของต้องคิด ที่หนึ่งที่คุณต้องการ
เหล่านี้จริงๆเย็นสำหรับ pset ของคุณ แต่พวกเขาจะใช้เวลามากของหน่วยความจำ,
เพื่อให้คุณค้าปิด
ใช่?
>> ผู้ชม: มันจะเป็นไปได้ การตั้งค่าลองแล้ว
เมื่อคุณมีทั้งหมด ข้อมูลในนั้นที่คุณ need--
ผมไม่ทราบว่าจะทำให้ความรู้สึก
ผมได้รับการกำจัดของทุกคน ตัวอักษรเป็นโมฆะ แต่แล้ว
คุณจะไม่สามารถที่จะดัชนี them--
>> ลำโพงที่ 1: คุณยังคงต้องให้พวกเขา
>> ผู้ชม: - วิธีการเดียวกันในแต่ละครั้ง
ลำโพง 1: ใช่
คุณจำเป็นต้องมีตัวละครที่เป็นโมฆะที่จะปล่อยให้ คุณทราบว่ามีไม่คำมี
เบนไม่คุณมีสิ่งที่คุณต้องการ?
ตกลง
สิทธิทั้งหมดดังนั้นเราจะ ที่จะไปนิด ๆ หน่อย ๆ
เป็นรายละเอียดทางเทคนิคที่อยู่เบื้องหลัง และพยายามทำงานผ่านตัวอย่างเช่น
>> ตกลงดังนั้นนี่คือสิ่งเดียวกัน
ขณะที่ในรายชื่อที่เชื่อมโยงหลักของเรา ชนิดเเล้สิ่งที่คำที่ฉันต้องการ? -
เช่นการสร้างบล็อกเป็นโหนด
ในลองเรายังมีโหนด แต่จะกำหนดไว้แตกต่างกัน
>> ดังนั้นเราจึงมีบางอย่างที่บูล แสดงให้เห็นถึงว่าคำจริง
ที่มีอยู่ในสถานที่นี้แล้ว เรามีอาร์เรย์บางตรงนี้หรือเปล่า
นี้เป็นตัวชี้ไป อาร์เรย์ของ 27 ตัวอักษร
และนี่คือสำหรับในกรณีนี้นี้ 27-- ผมมั่นใจว่าทุกท่านจะชอบรอ
มี 2​​6 ตัวอักษรในตัวอักษร
เรามี 27 ทำไม?
>> ดังนั้นขึ้นอยู่กับ วิธีการที่คุณใช้นี้
นี้มาจาก pset ว่า ได้รับอนุญาตให้เครื่องหมาย
เพื่อที่ว่าทำไมคนพิเศษ
นอกจากนี้คุณยังจะมีในบางส่วน กรณีที่เทอร์มิ null
จะรวมเป็นหนึ่ง อักขระที่จะได้รับอนุญาตให้เป็น
และนั่นคือวิธีที่พวกเขาตรวจสอบ ดูว่าเป็นจุดสิ้นสุดของคำว่า
หากคุณสนใจตรวจสอบ วิดีโอของเควินใน study.cs50,
เช่นเดียวกับวิกิพีเดียมี บางแหล่งข้อมูลที่ดีมี
>> แต่เรากำลังจะผ่านไปเพียงชนิด ว่าคุณสามารถทำงานผ่านลอง
ถ้าคุณได้รับหนึ่ง
ดังนั้นเราจึงมีอย่างใดอย่างหนึ่งที่ง่ายสุดที่นี่ มีคำว่า "ค้างคาว" และ "ซูม" ในพวกเขา
และที่เราเห็นขึ้นที่นี่ พื้นที่เล็ก ๆ นี้ที่นี่
แสดงให้เห็นถึงบูลของเราที่ กล่าวว่าใช่นี้เป็นคำ
และจากนั้นก็มีของเรา อาร์เรย์ของตัวละครใช่มั้ย?
>> ดังนั้นเรากำลังจะผ่านไป การหา "ค้างคาว" ในความพยายามนี้
ดังนั้นจะเริ่มต้นที่ด้านบนขวา?
และเรารู้ว่าขสอดคล้องกับ ดัชนีสององค์ประกอบที่สอง
ในอาร์เรย์นี้เพราะ A และ B
ดังนั้นประมาณหนึ่งวินาที
>> และกล่าวว่า, OK เย็นตามที่เป็น อาเรย์ต่อไปเพราะถ้าเราจำ
มันไม่ใช่ว่าแต่ละเหล่านี้ จริงมีองค์ประกอบ
หนึ่งในอาร์เรย์แต่ละเหล่านี้ ประกอบด้วยตัวชี้ใช่มั้ย?
มันเป็นความแตกต่างที่สำคัญที่จะทำให้
>> ฉันรู้ว่านี้เป็นไป be-- พยายามที่จะ ยากมากที่จะได้รับในครั้งแรก
ดังนั้นแม้ว่านี้ ครั้งที่สองหรือสาม
และจะยังคงชนิด ของที่ดูเหมือนยาก
ฉันสัญญาว่าถ้าคุณไปดู ในวันพรุ่งนี้สั้นอีกครั้ง
มันอาจจะทำให้รู้สึกมากขึ้น
มันใช้เวลามากในการย่อย
บางครั้งฉันยังคงรู้สึก เหมือนรออะไรคือลอง?
ฉันจะใช้นี้ได้อย่างไร
>> ดังนั้นเราจึงได้ b ในกรณีนี้ ซึ่งเป็นดัชนีที่สองของเรา
ถ้าเรามีการพูด, C หรือ งหรือหนังสืออื่น ๆ
เราต้องกลับไปที่แผนที่ดัชนีที่ ของอาร์เรย์ของเราที่ที่สอดคล้องกับ
ดังนั้นเราจะใช้เวลาเช่น rchar และเราก็ ลบออกจากแผนที่ลงใน 0-25
ทุกคนที่ดีวิธีการที่เรา แผนที่ตัวละครของเรา?
ตกลง
>> ดังนั้นเราจึงไปที่สองและเรา เห็นว่าใช่มันจะไม่เป็นโมฆะ
เราสามารถย้ายไปยังอาเรย์ต่อไปนี้
ดังนั้นเราจึงไปแถวต่อไปที่นี่
>> และเราบอกว่าโอเคตอนนี้เรา ต้องดูว่าอยู่ที่นี่
เป็นโมฆะหรือไม่ได้ จริงก้าวไปข้างหน้า?
ดังนั้นย้ายจริง ส่งต่อในอาร์เรย์นี้
และเราบอกว่าโอเคทีเป็นตัวอักษรสุดท้ายของเรา
ดังนั้นเราจึงไปที่เสื้อที่ดัชนี
แล้วเราก้าวไปข้างหน้า เพราะมีอีกคนหนึ่ง
และหนึ่งนี้กล่าวว่าโดยทั่วไปว่าใช่ มันบอกว่ามีคำที่ตรงนี้
ว่าถ้าคุณทำตามนี้ เส้นทางที่คุณได้มาถึง
คำพูดที่เราทราบว่าเป็น "ค้างคาว".
ใช่?
>> ผู้ชม: มันเป็นมาตรฐานที่จะมีที่ เป็นดัชนี 0 แล้วมีการเรียงลำดับที่ 1
หรือมีที่สิ้นสุดหรือไม่
>> ลำโพง 1: ฉบับที่
ดังนั้นหากเรามองกลับไปที่ของเรา ประกาศที่นี่ก็บูล,
ดังนั้นจึงเป็นองค์ประกอบของตัวเองในโหนดของคุณ
ดังนั้นจึงไม่เป็นส่วนหนึ่งของอาร์เรย์
เย็น
ดังนั้นเมื่อเราเสร็จสิ้นคำพูดของเราและเรา ที่แถวนี้สิ่งที่เราต้องการจะทำ
คือจะตรวจสอบคือคำนี้
และในกรณีนี้ก็จะกลับมาใช่
>> ดังนั้นเมื่อทราบว่าเรารู้ว่า "สวนสัตว์" - เรารู้ว่าเป็นมนุษย์ที่ "สวนสัตว์" เป็นคำที่
ใช่มั้ย?
แต่จะลองที่นี่ บอกว่าไม่มีก็ไม่ได้
และมันก็จะบอกว่าเพราะเรา ยังไม่ได้กำหนดว่ามันเป็นคำที่นี่
แม้ว่าเราจะสามารถสำรวจ ผ่านไปแถวนี้
ลองนี้จะบอกว่าไม่มี สวนสัตว์ไม่ได้อยู่ในพจนานุกรมของคุณ
เพราะเรายังไม่ได้ กำหนดให้มันเป็นเช่นนั้น
>> ดังนั้นวิธีหนึ่งที่จะทำ that-- โอ้ขอโทษหนึ่งนี้
ดังนั้นในกรณีนี้ "สวนสัตว์" ไม่ คำ แต่มันอยู่ในลองของเรา
แต่ในคนนี้บอกว่าเราอยากให้มันเป็น แนะนำคำว่า "อาบน้ำ" สิ่งที่เกิดขึ้น
คือเราทำตาม through-- B, A, T
เราอยู่ในแถวนี้และ เราไปค้นหาชั่วโมง
>> ในกรณีนี้เมื่อเรา มองไปที่ตัวชี้ไปที่ H,
มันชี้ไปที่ NULL, OK?
ดังนั้นถ้ามันอย่างชัดเจน ชี้ไปยังอาร์เรย์อื่น
คุณคิดว่าตัวชี้ทั้งหมด ในอาร์เรย์นี้จะชี้ให้เป็นโมฆะ
ดังนั้นในกรณีนี้, H ชี้ ให้เป็นโมฆะดังนั้นเราจึงไม่สามารถทำอะไร
ดังนั้นมันก็จะกลับมา เท็จ "อาบน้ำ" ไม่ได้อยู่ในที่นี่
ดังนั้นตอนนี้เรากำลังจริง จะไปผ่าน
วิธีการที่เราจะพูดจริง ที่ "สวนสัตว์" ที่อยู่ในความพยายามของเรา
เราไม่ใส่ "สวนสัตว์" วิธีในลองของเราหรือไม่
ดังนั้นในทางเดียวกันกับที่เราเริ่มต้นด้วย รายการที่เชื่อมโยงของเราเราเริ่มต้นที่ราก
เมื่อสงสัยเริ่มต้นที่ รากของสิ่งเหล่านี้
>> และเราจะพูดว่าตกลง Z
Z ที่มีอยู่ในนี้และจะไม่
ดังนั้นคุณจะย้ายไป อาเรย์ต่อไปของคุณ OK?
และจากนั้นในหน้าหนึ่ง เราพูดว่าตกลงไม่ o อยู่?
มันไม่
นี้อีกครั้ง
>> และอื่น ๆ หนึ่งต่อไปของเราที่เราได้กล่าวว่า ตกลง "สวนสัตว์" ที่มีอยู่แล้วที่นี่
ทั้งหมดที่เราต้องทำคือการตั้งเท่านี้ เป็นจริงว่ามีคำมี
ถ้าคุณได้ทำตามทุกอย่าง ก่อนที่จะถึงจุดนั้น
มันเป็นคำพูดดังนั้นเพียง ตั้งค่าเท่ากับดังกล่าว
ใช่?
>> ผู้ชม: ดังนั้นแล้วไม่ว่า หมายความว่า "บริติชแอร์เวย์" เป็นคำที่ยัง?
>> ลำโพง 1: ฉบับที่
ดังนั้นในกรณีนี้ "Ba" เราจะได้รับ ที่นี่เราจะบอกว่ามันเป็นคำที่
และก็ยังจะไม่มี
OK?
mmhmm?
>> ผู้ชม: ดังนั้นเมื่อคุณเป็นมัน คำพูดและการที่คุณบอกว่าใช่แล้วมัน
จะมีไป M?
>> ลำโพง 1: ดังนั้นนี้จะทำอย่างไร with-- คุณโหลดนี้
คุณจะพูดว่า "สวนสัตว์" เป็นคำ
เมื่อคุณไปที่ check-- เช่นสมมติว่าคุณต้องการที่จะพูดว่า
ไม่ "สวนสัตว์" ที่มีอยู่ในพจนานุกรมนี้?
คุณเท่านั้นที่จะไปค้นหา "สวนสัตว์" แล้วตรวจสอบเพื่อดูว่ามันเป็นคำ
คุณไม่เคยไปที่จะย้าย ผ่านไปยังม. เพราะไม่ว่า
สิ่งที่คุณกำลังมองหา
>> ดังนั้นหากเราต้องการที่จะเป็นจริง เพิ่ม "อาบน้ำ" ในความพยายามนี้
เราจะทำในสิ่งเดียวกัน ในขณะที่เราทำกับ "สวนสัตว์"
ยกเว้นเราจะเห็นว่าเมื่อเรา ลองและได้รับการชั่วโมงก็ไม่ได้มีอยู่
เพื่อให้คุณสามารถคิดนี้เป็นความพยายามที่ การเพิ่มโหนดใหม่ลงในรายการที่เชื่อมโยง
ดังนั้นเราจะต้องเพิ่มอีก หนึ่งในอาร์เรย์เหล่านี้เช่นดังนั้น
และแล้วสิ่งที่เราทำคือเราก็ตั้งชั่วโมง องค์ประกอบของอาร์เรย์นี้ชี้ไปที่นี้
>> และแล้วสิ่งที่เราต้องการจะทำที่นี่?
เพิ่มเท่ากับที่แท้จริง เพราะมันเป็นคำพูด
เย็น
ฉันรู้ว่า
พยายามที่จะไม่เป็นที่น่าตื่นเต้นที่สุด
ความน่าเชื่อถือฉันฉันรู้ว่า
>> ดังนั้นสิ่งหนึ่งที่จะตระหนักถึงกับพยายาม ผมบอกว่าพวกเขากำลังที่มีประสิทธิภาพมาก
ดังนั้นเราจึงได้เห็นพวกเขา ใช้เวลาถึงตันของพื้นที่
พวกเขากำลังชนิดของความสับสน
ดังนั้นทำไมเราจะเคยใช้เหล่านี้หรือไม่
เราใช้เหล่านี้เพราะพวกเขากำลัง ที่มีประสิทธิภาพอย่างไม่น่าเชื่อ
>> ดังนั้นถ้าคุณเคยมอง คำที่คุณเป็นเพียง
กระโดดจากความยาวของคำ
ดังนั้นหากคุณกำลังมองหา คำที่มีความยาวห้า
คุณเท่านั้นที่เคยจะต้อง ทำให้ที่มากที่สุดห้าเปรียบเทียบ OK?
จึงทำให้มันเป็นพื้นอย่างต่อเนื่อง
เช่นเดียวกับการแทรกและการค้นหา จะใช้เวลาอย่างต่อเนื่องโดยทั่วไป
>> ดังนั้นถ้าคุณเคยได้รับ บางสิ่งบางอย่างในเวลาที่คงที่
ที่ดีที่สุดเท่าที่จะได้รับ
คุณไม่สามารถรับได้ดีกว่า เวลาคงที่สำหรับสิ่งเหล่านี้
เพื่อให้เป็นหนึ่งใน pluses ใหญ่ของการพยายาม
>> แต่มันเป็นพื้นที่จำนวนมาก
เพื่อให้คุณชนิดของต้องตัดสินใจ สิ่งที่สำคัญมากขึ้นเพื่อคุณ
และบนเครื่องคอมพิวเตอร์ของว​​ันนี้ พื้นที่ที่ลองอาจใช้เวลานาน
อาจจะไม่ได้ส่งผลกระทบต่อ คุณที่มาก แต่อาจจะ
คุณจัดการกับบางสิ่งบางอย่าง ที่มีสิ่งที่ไกลมากขึ้น
และพยายามที่เพียงไม่เหมาะสม
ใช่?
>> ผู้ชม: รอเพื่อให้คุณมี 26 ตัวอักษรในทุกหนึ่งเดียว?
>> ลำโพง 1: Mmhmm
ใช่คุณมี 26
คุณมีบางเป็นเครื่องหมายคำพูดแล้ว คุณมี 26 ตัวชี้ในทุกคน
และพวกเขากำลังจุดลิ
>> ผู้ชม: และทุก 26 พวกเขาแต่ละคนมี 26?
>> ลำโพง 1: ใช่
และนั่นเป็นเหตุผลที่คุณสามารถ เห็นจะขยายอย่างรวดเร็ว
สิทธิ์ทั้งหมด
ดังนั้นเรากำลังจะได้รับเป็นต้นไม้ซึ่ง ฉันรู้สึกเหมือนจะง่ายขึ้นและอาจจะ
จะเป็นโทษน้อยดี จากการพยายามมี
เพื่อหวังว่าส่วนใหญ่ของคุณ ได้เห็นต้นไม้ก่อน
ไม่ชอบสวย คนที่อยู่ข้างนอกซึ่งผม
ไม่ทราบว่าใคร ไปนอกบ้านเมื่อเร็ว ๆ นี้
ผมไปเก็บแอปเปิ้ลวันหยุดสุดสัปดาห์นี้ และโอ้ฉันเอ้ยมันก็สวยงาม
ฉันไม่ทราบว่าใบ สามารถมองที่สวย
>> ดังนั้นนี้เป็นเพียงต้นไม้ใช่มั้ย?
มันเป็นเพียงโหนดบางและมัน ชี้ไปที่พวงของโหนดอื่น ๆ
ในขณะที่คุณดูที่นี่นี้เป็น ชนิดของรูปแบบที่เกิดขึ้นเป็นประจำ
โหนดชี้ไปยังโหนดเป็นชนิดของ สาระสำคัญของโครงสร้างข้อมูลจำนวนมาก
มันก็ขึ้นอยู่กับวิธีการที่เรา มีพวกเขาชี้ไปที่คนอื่น ๆ
และวิธีที่เราสำรวจ ผ่านพวกเขาและวิธีที่เรา
แทรกสิ่งที่เป็นตัวกำหนด ลักษณะที่แตกต่างกันของพวกเขา
>> ดังนั้นเพียงแค่คำศัพท์บางอย่าง ซึ่งผมเคยใช้มาก่อน
ดังนั้นรากเป็นสิ่งที่อยู่ที่ส่วนบนสุด
มันเป็นเรื่องที่เรามักจะเริ่มต้น
คุณสามารถคิดว่ามันเป็นหัวยัง
แต่สำหรับต้นไม้ที่เรามักจะ ดูเป็นราก
>> อะไรที่ตรงนี้ด้านล่าง ที่มาก bottom-- มาก
ใบพิจารณา
ดังนั้นมันจะไปพร้อมกับ สิ่งที่ต้นไม้ทั้งใช่มั้ย?
ใบที่ขอบของต้นไม้ของคุณ
>> แล้วเรายังมีคู่ของ คำที่จะพูดคุยเกี่ยวกับโหนดที่เกี่ยวข้อง
ซึ่งกันและกัน
ดังนั้นเราจึงมีผู้ปกครอง เด็กและพี่น้อง
ดังนั้นในกรณีนี้, 3 แม่ของ 5, 6, และ 7
ดังนั้นผู้ปกครองเป็นสิ่งที่ หนึ่งในขั้นตอนข้างต้นสิ่งที่คุณกำลัง
หมายถึงดังนั้นเพียง เหมือนต้นไม้ครอบครัว
หวังว่านี้เป็นสิ่งที่เล็ก ๆ น้อย ๆ บิตใช้งานง่ายกว่าพยายาม
>> พี่น้องที่ใด ๆ ที่มี พ่อแม่เหมือนกันใช่มั้ย?
พวกเขาอยู่ในระดับเดียวกับที่นี่
แล้วขณะที่ผมกำลัง บอกว่าเด็กเป็นเพียง
สิ่งที่เป็นขั้นตอนหนึ่งด้านล่าง โหนดในคำถาม OK?
เย็น
ดังนั้นต้นไม้ไบนารี
ทุกคนสามารถอันตรายเดาที่หนึ่งใน ลักษณะของต้นไม้ไบนารี?
>> ผู้ชม: แม็กซ์สองใบ
>> ลำโพง 1: ขวา
ดังนั้นสูงสุดของทั้งสองใบ
ดังนั้นในหนึ่งก่อนหน้านี้เรามีหนึ่งในนี้ ที่มีสาม แต่ในต้นไม้ไบนารี
คุณมีสูงสุดของทั้งสอง เด็กต่อพ่อแม่ใช่มั้ย?
มีอีก ลักษณะที่น่าสนใจ
ไม่มีใครรู้ว่า?
ต้นไม้ไบนารี
>> ดังนั้นต้นไม้ไบนารีจะมีทุกอย่าง ที่ยกกำลังหนึ่งนี้ไม่ได้ sorted--
แต่ในต้นไม้ไบนารีเรียงลำดับ ทุกอย่างที่อยู่ด้านขวา
มากกว่าแม่ และทุกอย่างที่อยู่ทางซ้าย
น้อยกว่าผู้ปกครอง
และที่ได้รับการทดสอบ คำถามก่อนที่จะดีเพื่อที่จะรู้ว่า
ดังนั้นวิธีที่เรากำหนดนี้, อีกครั้งเรามีโหนดอื่น
นี้มีลักษณะคล้ายกับสิ่งที่?
เป็นทวีคูณ
>> แสดงการเชื่อมโยง: ผู้ชม
>> ลำโพง 1: รายการที่เชื่อมโยงคู่ใช่มั้ย?
ดังนั้นหากเราแทนที่นี้ ที่มีก่อนหน้านี้และต่อไป
นี้จะเป็นรายการที่เชื่อมโยงทวีคูณ
แต่ในกรณีนี้เราจริง ได้ทางซ้ายและขวาและที่มัน
มิฉะนั้นจะตรงเดียวกัน
เรายังคงมีองค์ประกอบ คุณกำลังมองหา
และคุณก็มีสองตัวชี้ สิ่งที่จะเป็นต่อไป
ใช่ต้นไม้ค้นหาแบบไบนารีเพื่อ
ถ้าเราสังเกตเห็นทุกอย่างบน ที่นี่เป็น than-- มากขึ้น
หรือทุกอย่างทันที ไปทางขวาที่นี่
มากกว่าทุกอย่าง ที่นี่มีค่าน้อยกว่า
>> ดังนั้นถ้าเราจะค้นหาผ่านมัน ควรมีลักษณะที่ใกล้เคียงกับค้นหาแบบไบนารี
ที่นี่ใช่มั้ย?
ยกเว้นแทนที่จะมอง ที่ครึ่งอาร์เรย์
เราเพียงแค่มองที่ทั้งซ้าย ด้านข้างหรือด้านขวาของต้นไม้
ดังนั้นจึงได้รับเพียงเล็กน้อยง่ายผมคิดว่า
>> ดังนั้นถ้ารากของคุณเป็นโมฆะ เห็นได้ชัดว่ามันเป็นเท็จเพียง
และถ้ามันมีเห็นได้ชัดว่ามันเป็นความจริง
ถ้ามันน้อยกว่าเราค้นหาทางด้านซ้าย
ถ้ามันมากขึ้นกว่า เราค้นหาทางด้านขวา
มันเหมือนกับการค้นหาแบบไบนารี เพียงแค่โครงสร้างข้อมูลที่แตกต่างกัน
ที่เรากำลังใช้
แทนที่จะอาร์เรย์ มันเป็นเพียงแค่ต้นไม้ไบนารี
>> ตกลงกอง
และยังดูเหมือนว่าเรา อาจจะมีนิด ๆ หน่อย ๆ ของเวลา
ถ้าเราทำฉันมีความสุขที่จะไป กว่าใด ๆ นี้อีกครั้ง
ตกลงดังนั้นกอง
ไม่มีใครจำสิ่งที่ stacks-- ลักษณะของสแต็คที่ใด?
>> ตกลงดังนั้นส่วนใหญ่ของเราผมคิดว่า กินในอาหาร halls--
มากที่สุดเท่าที่เราอาจจะไม่ชอบที่จะ
แต่เห็นได้ชัดว่าคุณสามารถคิดของสแต็ค ตัวอักษรเช่นเดียวกับสแต็คของถาด
หรือสแต็คในสิ่งที่
และสิ่งที่สำคัญ ตระหนักคือว่ามันเป็น
บางสิ่งบางอย่างลักษณะ ที่เราเรียกว่าคูณเป็น LIFO
ไม่มีใครรู้ว่าสิ่งที่ยืนอยู่หรือ?
mmhmm?
>> ผู้ชม: สุดท้ายในครั้งแรกออกมา
>> ลำโพง 1: ขวาสุดท้ายในครั้งแรกออกมา
ดังนั้นหากเรารู้ว่าถ้าเรากำลังซ้อนสิ่งที่ ขึ้นสิ่งที่ง่ายที่สุดที่จะคว้า off--
และอาจจะเป็นสิ่งเดียวที่เราสามารถคว้า ออกหากสแต็คของเราคือการ enough-- ใหญ่
คือการที่องค์ประกอบด้านบน
ดังนั้นสิ่งที่วางอยู่บน last-- ที่เราเห็นที่นี่
สิ่งที่ได้รับการผลักดัน ส่วนใหญ่เป็น recently--
จะเป็นครั้งแรก สิ่งที่เรา pop ปิด, OK?
>> ดังนั้นสิ่งที่เรามีที่นี่ struct typedef อื่น
นี้เป็นจริงเช่นเดียวกับ ผิดพลาดแน่นอนในโครงสร้างข้อมูล
เพื่อให้มีจำนวนมากโยนที่พวกคุณเป็น
ฉันรู้ว่า
ดังนั้นยัง struct อื่น
ยายสำหรับโครงสร้าง
>> และในกรณีนี้มันเป็นตัวชี้บางอย่าง ไปยังอาร์เรย์ที่มีความจุบางส่วน
ดังนั้นนี้เป็นสแต็คของเรา ที่นี่เช่นเดียวกับอาเรย์ที่แท้จริงของเรา
ที่ถือองค์ประกอบของเรา
แล้วที่นี่เรามีขนาดบาง
>> และโดยทั่วไปแล้วคุณต้องการให้ ติดตามวิธีการใหญ่สแต็คของคุณ
เพราะสิ่งที่มันจะช่วยให้ คุณจะทำคือถ้าคุณทราบขนาด
จะช่วยให้คุณที่จะบอกว่า ตกลงฉันที่ความจุ?
ฉันสามารถเพิ่มอะไรอีกหรือไม่
และก็ยังจะบอกคุณ ที่ด้านบนสุดของสแต็คของคุณ
เพื่อให้คุณรู้ว่าสิ่งที่คุณ จริงสามารถนำออกไป
และที่จริงจะ มีความชัดเจนน้อยมากที่นี่
>> ดังนั้นสำหรับการผลักดันสิ่งหนึ่งถ้าคุณ เคยที่จะดำเนินการผลักดัน
ขณะที่ผมก็แค่พูดของคุณ สแต็คที่มีขนาด จำกัด ใช่มั้ย?
อาเรย์ของเรามีความสามารถบางอย่าง
มันเป็นอาเรย์
มันเป็นขนาดคงที่ดังนั้นเราจึงจำเป็นที่จะต้อง ให้แน่ใจว่าเราไม่ได้วางมากขึ้น
เป็น array ของเรามากกว่าที่เรา จริงมีที่ว่างสำหรับ
>> ดังนั้นเมื่อคุณกำลังสร้างการผลักดัน ฟังก์ชั่น, สิ่งแรกที่คุณทำคือการพูดการตกลง
ฉันจะมีพื้นที่ว่างในกองของฉันได้อย่างไร
เพราะถ้าผมไม่ขอโทษ ฉันไม่สามารถจัดเก็บองค์ประกอบของคุณ
ถ้าผมทำแล้วคุณต้องการเก็บ ไว้ที่ด้านบนของสแต็คใช่มั้ย?
>> และนี่คือเหตุผลที่เรามี เพื่อติดตามขนาดของเรา
ถ้าเราไม่ได้ติดตามขนาดของเรา เราไม่ทราบว่าจะนำมัน
เราไม่ทราบว่าหลายสิ่งหลายอย่าง อยู่ในอาเรย์ของเราอยู่แล้ว
เช่นเดียวกับที่เห็นได้ชัดมีวิธีการ ที่บางทีคุณอาจจะทำมัน
คุณสามารถเริ่มต้นทุกอย่างเพื่อ NULL แล้วตรวจสอบเป็นโมฆะล่าสุด
แต่เป็นสิ่งที่ง่ายมากที่เป็นเพียง ที่จะบอกว่าตกลงติดตามขนาด
เหมือนฉันรู้ว่าฉันมีธาตุทั้งสี่ ในอาเรย์ของฉันดังนั้นสิ่งต่อไปที่
ที่เราใส่ในเราไม่ ไปเก็บที่ดัชนี 4
แล้วของหลักสูตรนี้หมายความว่า คุณได้ผลักดันให้ประสบความสำเร็จในบางสิ่งบางอย่าง
บนสแต็คของคุณคุณ ต้องการเพิ่มขนาด
เพื่อให้คุณรู้ว่าคุณอยู่ที่ไหนดังนั้น ที่คุณสามารถผลักดันสิ่งที่เพิ่มเติมเกี่ยวกับ
>> ดังนั้นหากเรากำลังพยายามที่จะป๊อปอัพ บางสิ่งบางอย่างออกจากสแต็
สิ่งที่อาจจะเป็นสิ่งแรก ที่เราต้องการตรวจสอบ?
คุณกำลังพยายามที่จะใช้ บางสิ่งบางอย่างออกจากสแต็คของคุณ
คุณแน่ใจว่ามี บางสิ่งบางอย่างในกองของคุณ?
เลขที่
ดังนั้นสิ่งที่เราอาจต้องการตรวจสอบ?
>> ผู้ชม: [ไม่ได้ยิน]
ลำโพง 1: ตรวจสอบขนาด?
ขนาด
ดังนั้นเราจึงต้องการที่จะตรวจสอบเพื่อดูว่า ขนาดของเรามากกว่า 0, OK?
และถ้าเป็นแล้วเราต้องการที่จะลดลง ขนาดของเราโดยที่ 0 และผลตอบแทนที่
ทำไม?
>> ในครั้งแรกที่พวกเราอยู่ ผลักดันให้เราผลักดันมัน
บนขนาดและขนาดของการอัปเดตแล้ว
ในกรณีนี้เรากำลัง decrementing ขนาด แล้วพามันออกไปดึงมัน
จากอาร์เรย์ของเรา
ทำไมเราจะทำเช่นนั้น?
ดังนั้นถ้าฉันมีสิ่งหนึ่งในกองของฉัน สิ่งที่จะเป็นขนาดของฉันที่จุดนั้น?
1
>> และสถานที่ที่องค์ประกอบที่ 1 จะถูกเก็บไว้?
สิ่งที่ดัชนี?
ผู้ชม: 0
ลำโพง 1: 0
ดังนั้นในกรณีนี้เรา มักจะต้องทำให้ sure--
แทนที่จะกลับ ขนาดลบ 1 เพราะเรา
รู้ว่าองค์ประกอบของเราคือการ จะถูกเก็บไว้ที่ 1 น้อย
สิ่งที่ขนาดของเรานี้ ใช้เวลาเพียงดูแลมัน
มันเป็นวิธีที่สง่างามมากขึ้นเล็กน้อย
และเราก็พร่องของเรา ขนาดและขนาดจากนั้นกลับมา
mmhmm?
>> ผู้ชม: ผมคิดว่าเพียงแค่ในทั่วไป ทำไมจะโครงสร้างข้อมูลนี้
เป็นประโยชน์?
>> ลำโพง 1: มันขึ้นอยู่กับบริบทของคุณ
ดังนั้นสำหรับบางส่วนของทฤษฎี ถ้าคุณกำลังทำงาน with-- ตกลง
ให้ฉันดูว่ามีประโยชน์อย่างใดอย่างหนึ่ง ที่เป็นประโยชน์ต่อมากกว่าภายนอก
ของลูกค้า
กับกองเวลาใด ๆ ที่คุณต้องการ เพื่อติดตามสิ่งที่
มีการเพิ่มมากที่สุดเมื่อเร็ว ๆ นี้คือเมื่อ คุณจะต้องการที่จะใช้สแต็ค
>> และผมก็ไม่สามารถคิดที่ดี ตัวอย่างเช่นสิทธิที่ตอนนี้
แต่เมื่อใดก็ตามที่ผ่านมามากที่สุด สิ่งที่สำคัญที่สุดให้กับคุณ
ที่เมื่อสแต็ค เป็นไปได้ที่มีประโยชน์
ฉันพยายามที่จะคิดว่าถ้า มีหนึ่งที่ดีสำหรับการนี​​้
ถ้าผมคิดว่าเป็นตัวอย่างที่ดีในครั้งต่อไป 20 นาทีแน่นอนผมจะบอกคุณ
>> แต่โดยรวมแล้วถ้ามีอะไร เหมือนที่ผมกล่าวว่าส่วนใหญ่เมื่อเร็ว ๆ นี้ที่มากที่สุด
เป็นสิ่งที่สำคัญที่สุดที่ ที่กองเข้ามาในเล่น
ในขณะที่รอคิวเป็นชนิดของตรงข้าม
และสุนัขเล็ก ๆ น้อย ๆ
ไม่ดีนี้ใช่มั้ย?
ฉันรู้สึกเหมือนฉันควร เพียงแค่มีวิดีโอกระต่าย
ขวาตรงกลางของ ส่วนสำหรับพวกคุณ
เพราะเป็นส่วนที่รุนแรง
>> ดังนั้นคิว
โดยทั่วไปคิวเป็นเหมือนเส้น
พวกคุณฉันแน่ใจว่าใช้ชีวิตประจำวันนี้ เช่นเดียวกับในห้องอาหารของเรา
ดังนั้นเราจึงต้องไปใน และได้รับถาดของฉัน
แน่ใจว่าคุณต้องรอในบรรทัด ที่จะรูดหรือได้รับอาหารของคุณ
>> ดังนั้นความแตกต่างที่นี่ ว่าขณะนี้เป็น FIFO
ดังนั้นหาก LIFO เป็นครั้งสุดท้ายในครั้งแรก ออก FIFO เป็นครั้งแรกในครั้งแรกออกมา
ดังนั้นนี่คือที่สิ่งที่คุณใส่ ในครั้งแรกเป็นสิ่งที่สำคัญที่สุดของคุณ
ดังนั้นถ้าคุณกำลังรอ ใน line-- คุณสามารถ
คิดว่าคุณไป ไปรับ iPhone ใหม่
และมันก็เป็นกองที่ คนสุดท้ายในสายได้มันครั้งแรก
คนจะฆ่ากัน
>> ดังนั้น FIFO เราไม่คุ้นเคยมาก ที่มีอยู่ในโลกแห่งความจริงที่นี่
และมีทุกอย่างจะทำอย่างไรกับความจริง ชนิดของสูตรทั้งบรรทัดนี้
และโครงสร้างเข้าคิว
ดังนั้นในขณะที่มีกอง เรามีการผลักดันและป๊อป
กับคิวที่เรามี และ enqueue dequeue
ดังนั้น enqueue โดยทั่วไปหมายถึง วางลงบนด้านหลัง
และวิธีการใช้ dequeue ออกจากด้านหน้า
ดังนั้นโครงสร้างข้อมูลของเรา นิด ๆ หน่อย ๆ ที่ซับซ้อนมากขึ้น
เรามีสิ่งที่สองที่จะติดตาม
>> ดังนั้นไม่มีหัวนี้ เป็นสิ่งกองใช่มั้ย?
นี้เป็นโครงสร้างเดียวกันเป็นกอง
สิ่งเดียวที่แตกต่างกันขณะนี้คือเรา มีหัวนี้ซึ่งสิ่งที่คุณคิด
จะไปติดตาม?
>> ผู้ชม: คนแรก
>> ลำโพง 1: ขวา สิ่งแรกที่เราใส่ใน
หัวของคิวของเรา
ใครก็ตามที่เป็นครั้งแรกในสาย
สิทธิทั้งหมดดังนั้นหากเราทำ enqueue
อีกครั้งกับใด ๆ ของ เหล่านี้โครงสร้างข้อมูล
เนื่องจากเรากำลังติดต่อกับอาร์เรย์ เราจำเป็นต้องตรวจสอบว่าเรามีพื้นที่ว่าง
>> นี้เป็นชนิดของเช่นฉันบอก พวกคุณถ้าคุณเปิดแฟ้ม
คุณจำเป็นต้องตรวจสอบเป็นโมฆะ
กับใด ๆ ของกองเหล่านี้ และคิวที่คุณต้องการ
เพื่อดูว่ามีพื้นที่เพราะเรา จัดการกับอาร์เรย์ขนาดคงที่
เหมือนที่เราเห็นตรงนี้ 0, 1 ทั้งหมดถึง 5
ดังนั้นสิ่งที่เราทำในกรณีที่มีการตรวจสอบ เพื่อดูว่าเรายังคงมีพื้นที่ว่าง
คือขนาดของเราน้อยกว่าความจุ?
>> ถ้าเป็นเช่นนั้นเราจำเป็นต้องเก็บไว้ที่ หางและเราปรับปรุงขนาดของเรา
ดังนั้นสิ่งที่หางอาจจะมีในกรณีนี้หรือไม่?
มันไม่ได้เป็นลายลักษณ์อักษรอย่างชัดเจนออกมา
วิธีการที่เราจะเก็บมันได้หรือไม่
สิ่งที่หางจะเป็นอย่างไร
>> จึงขอเดินผ่านตัวอย่างนี้
ดังนั้นนี่คืออาร์เรย์ของขนาด 6 ใช่มั้ย?
และเรามีตอนนี้ขนาดของเราคือ 5
และเมื่อเราใส่ไว้ในก็จะ ที่จะเข้าไปในดัชนีที่ห้าใช่มั้ย?
ดังนั้นการจัดเก็บที่หาง
>> อีกวิธีหนึ่งที่จะเขียนหางจะเพียง เป็นอาร์เรย์ของเราได้ที่ดัชนีของขนาดใช่ไหม?
นี้คือขนาด 5
สิ่งต่อไปที่จะไปเป็น 5
เย็น?
ตกลง
จะได้รับเพียงเล็กน้อยที่ซับซ้อนมากขึ้น เมื่อเราเริ่มล้อเล่นกับหัว
ใช่?
>> ผู้ชม: ไม่ว่าหมายถึงว่าเรา จะมีการประกาศอาร์เรย์ที่
เป็นห้าองค์ประกอบยาวและ แล้วเรากำลังเพิ่มไปยังมันได้หรือไม่
>> ลำโพง 1: ฉบับที่
ดังนั้นในกรณีนี้เป็นกอง
นี้จะมีการประกาศ เป็นอาร์เรย์ที่มีขนาด 6
และในกรณีนี้เรา เพียงแค่มีพื้นที่หนึ่งที่เหลือ
>> ตกลงดังนั้นสิ่งหนึ่งที่อยู่ในนี้ กรณีถ้าศีรษะของเราอยู่ที่ 0,
จากนั้นเราก็สามารถเพิ่มขนาด
แต่ได้รับเล็กน้อย trickier เพราะในความเป็นจริงพวกเขา
จะได้ไม่ต้องเลื่อน สำหรับเรื่องนี้ดังนั้นฉันจะ
การวาดหนึ่งเพราะมันเป็นไม่ได้ ไม่ง่ายอย่างนั้นเมื่อคุณ
เริ่มต้นการกำจัดสิ่ง
ดังนั้นในขณะที่มีกอง คุณเคยมี
ที่จะต้องกังวลเกี่ยวกับสิ่งที่มีขนาด เมื่อคุณกำลังเพิ่มบางสิ่งบางอย่างเกี่ยวกับ
กับคิวที่คุณยังต้องทำให้ แน่ใจว่าหัวของคุณจะคิดเป็น
เพราะสิ่งดีๆเกี่ยวกับการรอคิว คือว่าถ้าคุณไม่ได้อยู่ที่ความจุ
จริงคุณสามารถทำให้มันห่อรอบ
>> ตกลงดังนั้นหนึ่ง thing-- โอ้ นี่คือชอล์กที่น่ากลัว
สิ่งหนึ่งที่จะต้องพิจารณาเป็นกรณี
เราเพียงแค่จะทำห้า
ตกลงดังนั้นเรากำลังจะไป บอกว่าหัวอยู่ที่นี่
นี้เป็น 0, 1, 2, 3, 4
>> หัวที่นั่นและ กรุณามีสิ่งที่อยู่ในนั้น
และเราต้องการที่จะเพิ่มบางอย่างใช่มั้ย?
ดังนั้นสิ่งที่เราจำเป็นต้อง ทราบว่าเป็นที่หัวอยู่เสมอ
จะย้ายด้วยวิธีนี้และ แล้ววนกลับไปรอบ ๆ OK?
>> ดังนั้นคิวนี้มีพื้นที่ใช่มั้ย?
มันมีช่องว่างในจุดเริ่มต้นมาก ชนิดของตรงข้ามของนี้
ดังนั้นสิ่งที่เราต้องทำคือเรา ต้องคำนวณหาง
ถ้าคุณรู้ว่าคุณ หัวยังไม่ได้ย้ายไปหาง
เป็นเพียงอาร์เรย์ที่ ดัชนีของขนาด
>> แต่ในความเป็นจริงถ้าคุณใช้คิว หัวของคุณอาจจะถูกปรับปรุง
ดังนั้นสิ่งที่คุณต้องทำคือ จริงคำนวณหาง
ดังนั้นสิ่งที่เราทำคือสูตรนี้ ที่นี่ซึ่งผมจะให้คุณ
คนคิดเกี่ยวกับและ แล้วเราจะพูดคุยเกี่ยวกับเรื่องนี้
ดังนั้นนี่คือความจุ
>> ดังนั้นนี่จะจริง ให้คุณวิธีที่จะทำ
เพราะในกรณีนี้สิ่งที่?
หัวของเราคือวันที่ 1, ขนาดของเราคือ 4
ถ้าเรา mod ที่ 5 เราจะได้ 0, ซึ่งเป็นที่ที่เราควรใส่มัน
>> ดังนั้นแล้วในกรณีต่อไป ถ้าเราจะทำเช่นนี้
เราพูดว่าตกลงขอ dequeue บางสิ่งบางอย่าง
เรา dequeue นี้
เราจะออกจากองค์ประกอบนี้ใช่มั้ย?
>> และตอนนี้หัวของเราจะชี้ที่นี่ และเราต้องการที่จะเพิ่มในสิ่งอื่น
นี้เป็นพื้น ด้านหลังของสายของเราใช่มั้ย?
คิวสามารถห่อรอบอาร์เรย์
นั่นคือหนึ่งในความแตกต่างหลัก
กองคุณไม่สามารถทำเช่นนี้
>> กับคิวที่คุณสามารถ เพราะเรื่องทั้งหมดที่
คือการที่คุณรู้ว่าสิ่งที่ ถูกเพิ่มเข้ามามากที่สุดเมื่อเร็ว ๆ นี้
เนื่องจากทุกอย่างเป็นไปได้ที่จะเพิ่มขึ้นใน ทิศทางไปทางซ้ายนี้ในกรณีนี้
แล้วห่อรอบคุณสามารถ ยังคงวางในองค์ประกอบใหม่
ที่ด้านหน้าของอาร์เรย์ เพราะมันไม่ได้จริงๆ
ด้านหน้าของอาเรย์อีกต่อไป
คุณสามารถคิดว่าจุดเริ่มต้นของ อาร์เรย์เป็นที่หัวของคุณเป็นจริง
>> ดังนั้นสูตรนี้เป็นวิธีการที่ คุณคำนวณหางของคุณ
ไม่ว่าจะทำให้ความรู้สึก?
ตกลง
ตกลง dequeue แล้ว พวกคุณมีเวลา 10 นาที
ที่จะถามฉันคำถาม Clarifying ใด ๆ คุณต้องการเพราะฉันรู้ว่ามันบ้า
>> สิทธิทั้งหมดดังนั้นใน way-- เดียวกัน ผมไม่ทราบว่าพวกคุณสังเกตเห็น
แต่ลูกค้าเป็นข้อมูลเกี่ยวกับรูปแบบ
สิ่งที่จะสวยมาก เดียวกันเพียงกับปรับแต่งเล็ก ๆ
สิ่งเดียวกันดังนั้นที่นี่
เราจำเป็นต้องตรวจสอบเพื่อดูว่าเราจริง มีบางสิ่งที่อยู่ในคิวของเราใช่มั้ย?
บอกว่าโอเคคือขนาดของเรามากกว่า 0?
เย็น
>> ถ้าเราทำแล้วเราย้ายหัวของเราซึ่ง คือสิ่งที่ฉันเพียงแค่แสดงให้เห็นที่นี่
เราอัปเดตใหญ่ของเราที่จะเป็นอีกหนึ่ง
แล้วเราพร่องของเรา ขนาดและองค์ประกอบกลับ
>> นอกจากนี้ที่เป็นรูปธรรมมากขึ้น โค้ดบน study.cs50.net,
และผมขอแนะนำให้ไป ผ่านมันถ้าคุณมีเวลา
ถึงแม้ว่ามันจะเป็นเพียงนามแฝงรหัส
และถ้าพวกคุณต้องการที่จะพูดคุยผ่านทาง ที่อยู่กับฉันแบบหนึ่งต่อหนึ่งโปรดแจ้งให้เรา
รู้
ผมยินดีที่จะ
โครงสร้างข้อมูลถ้า คุณใช้ CS 124, คุณจะ
รู้ว่าโครงสร้างข้อมูลที่ได้รับมาก สนุกและเป็นเพียงการเริ่มต้น
>> ดังนั้นผมรู้ว่ามันยาก
ก็ OK
เราต่อสู้
ฉันยังคงทำ
จึงไม่ต้องกังวลมากเกินไปเกี่ยวกับเรื่องนี้
>> แต่ที่เป็นพื้นของคุณ หลักสูตรความผิดพลาดในโครงสร้างข้อมูล
ฉันรู้ว่ามันเป็นจำนวนมาก
มีอะไรที่เรา อยากจะไปซ้ำอีก?
สิ่งที่เราต้องการที่จะพูดคุยผ่าน?
ใช่?
>> ผู้ชม: ตัวอย่างเช่นนั้นดังนั้น หางใหม่อยู่ที่ 0 ในช่วงที่?
ลำโพง 1: ใช่
ผู้ชม: ตกลง
ดังนั้นแล้วจะผ่าน คุณต้องการมี 1 บวก 4 or--
>> ลำโพง 1: เพื่อให้คุณได้รับการบอกว่า เมื่อเราต้องการที่จะไปทำเช่นนี้อีกครั้งหรือไม่
ผู้ชม: ใช่
ดังนั้นถ้าคุณกำลังคิดแทนดูอยู่ที่ไหน คุณคำนวณหางจากในที่?
>> ลำโพง 1: ดังนั้นหาง เป็น in-- ผมเปลี่ยนนี้
ดังนั้นในตัวอย่างนี้ที่นี่นี้คือ อาร์เรย์ที่เรากำลังมองหาที่ OK?
ดังนั้นเราจึงมีสิ่งที่ 1, 2, 3 และ 4
ดังนั้นเราจึงมีหัวของเราเท่ากับ 1 ที่ จุดนี้และขนาดของเรามีค่าเท่ากับ 4
ที่จุดนี้ใช่มั้ย?
>> พวกคุณทุกคนยอมรับว่าเป็นกรณี?
ดังนั้นเราจึงทำหัวขนาดบวกซึ่ง จะช่วยให้เรา 5 แล้วเรา mod 5
เราได้รับ 0 ซึ่งบอกเราว่าเป็น 0 ที่เป็นหางที่เรามีพื้นที่ของเรา
>> ผู้ชม: หมวกอะไร?
>> ลำโพง 1: ความจุ
ขอโทษ
เพื่อให้เป็นขนาดของอาร์เรย์ของคุณ
ใช่?
>> ผู้ชม: [ไม่ได้ยิน] ก่อน เรากลับองค์ประกอบ?
>> ลำโพง 1: ดังนั้นเราจึงย้าย มุ่งหน้าหรือกลับขณะนี้?
ดังนั้นหากเราย้ายหนึ่งพร่องขนาด?
ยึดมั่นใน
แน่นอนผมลืมอีก
ใจไม่เคย
ไม่มีสูตรอื่น
ใช่คุณต้องการที่จะกลับมา ศีรษะและจากนั้นย้ายกลับ
>> ผู้ชม: ตกลงเพราะในตอนนี้ จุดหัวอยู่ที่ 0,
แล้วคุณต้องการที่จะกลับมา ดัชนี 0 แล้วทำให้หัว 1?
>> ลำโพง 1: ขวา
ผมคิดว่ามีอีก สูตรชนิดเช่นนี้
ฉันไม่ได้มีไว้ที่ด้านบนหัวของฉันเป็น ผมไม่ต้องการให้คุณผิดหนึ่ง
แต่ผมคิดว่ามันเป็นอย่างสมบูรณ์แบบที่ถูกต้อง พูดตกลงเก็บ element-- นี้สิ่งที่
องค์ประกอบของหัวเท่าไหร่พร่องของคุณ ขนาดย้ายหัวของคุณไปและกลับ
สิ่งที่เป็นองค์ประกอบ
ที่ถูกต้องสมบูรณ์
ตกลง
ฉันรู้สึกเช่นนี้ไม่ได้ เช่น most-- คุณไม่ได้
จะเดินออกจากที่นี่ เหมือนใช่ฉันรู้พยายาม
ผมได้รับมันทั้งหมด
ไม่เป็นไร
ฉันสัญญาว่า
แต่โครงสร้างข้อมูลเป็นสิ่งที่ มันต้องใช้เวลามากในการรับใช้
อาจเป็นหนึ่งในที่ยากที่สุด สิ่งที่ผมคิดว่าในหลักสูตร
>> จึงแน่นอนใช้เวลา ซ้ำและมอง at-- ฉัน
ไม่ทราบจริงๆรายการที่เชื่อมโยง จนกว่าฉันจะไม่มากเกินไปกับพวกเขา
ในแบบเดียวกับที่ผมทำไม่ได้ เข้าใจจริงๆตัวชี้
จนกว่าฉันจะได้มีการสอนสอง ปีและทำ psets ของตัวเองกับมัน
มันใช้เวลามากในการย้ำและเวลา
และในที่สุดก็จะชนิดของคลิก
>> แต่ในขณะเดียวกันถ้าคุณมีชนิด ของความเข้าใจในระดับสูงของสิ่งที่
เหล่านี้ข้อดีของพวกเขา และ cons-- ซึ่งเป็นสิ่งที่
เราจริงๆมีแนวโน้มที่จะเน้น โดยเฉพาะอย่างยิ่งในหลักสูตรบทนำ
เช่นเดียวกับเหตุผลที่เราจะใช้ พยายามกว่าอาร์เรย์?
เช่นเดียวกับสิ่งที่เป็นบวก และเชิงลบของแต่ละเหล่านั้นหรือไม่
>> และทำความเข้าใจเกี่ยวกับการแลกเปลี่ยน ระหว่างกันของโครงสร้างเหล่านี้
เป็นสิ่งที่สำคัญมากขึ้นในขณะนี้
อาจจะมีคนบ้า คำถามหรือสองที่
จะขอให้คุณที่จะดำเนินการผลักดันหรือ ใช้ POP หรือ enqueue และ dequeue
แต่ส่วนใหญ่ที่มีที่ ความเข้าใจระดับที่สูงขึ้นและอื่น ๆ
ของเข้าใจง่ายคือ สำคัญกว่าความจริง
ความสามารถในการใช้มัน
>> มันจะน่ากลัวจริงๆถ้าทุกท่าน สามารถออกไปและไปใช้ลอง
แต่เราเข้าใจว่ามันไม่จำเป็นต้องเป็น สิ่งที่เหมาะสมที่สุดในตอนนี้
แต่คุณสามารถใน pset ของคุณถ้าคุณต้องการ เพื่อและจากนั้นคุณจะได้รับการปฏิบัติ
แล้วบางทีคุณอาจจะ จริงๆเข้าใจมัน
ใช่?
>> ผู้ชม: OK เพื่อให้คนที่มี เราหมายถึงการใช้ใน pset?
ฉันจะต้องใช้หนึ่งของพวกเขา?
ลำโพง 1: ใช่
เพื่อให้คุณมีทางเลือกของคุณ
ผมคิดว่าในกรณีนี้เราสามารถทำได้ พูดคุยเกี่ยวกับ pset นิด ๆ หน่อย ๆ
เพราะผมวิ่งผ่านเหล่านี้
ดังนั้นใน pset ของคุณคุณมีของคุณ ทางเลือกของการพยายามหรือตารางแฮช
บางคนจะพยายาม และใช้ตัวกรองบาน
แต่ผู้ที่ไม่ได้ในทางเทคนิคที่ถูกต้อง
เพราะธรรมชาติของความน่าจะเป็นของพวกเขา พวกเขาให้ผลบวกปลอมบางครั้ง
พวกเขากำลังดูเย็นลง แต่
ขอแนะนำให้มอง ที่พวกเขาอย่างน้อย
แต่คุณมีทางเลือกของคุณ ระหว่างตารางแฮชและลอง
และบอกว่าเป็นไปได้ที่ คุณโหลดในพจนานุกรมของคุณ
>> และคุณจะต้องเลือก ฟังก์ชันแฮชของคุณ
คุณจะต้องเลือกวิธีที่หลาย ๆ บุ้งกี๋ที่คุณมีและมันจะแตกต่างกันไป
เช่นถ้าคุณมีถังมากขึ้น บางทีมันอาจจะจะทำงานได้เร็วขึ้น
แต่บางทีคุณอาจจะสูญเสีย พื้นที่จำนวนมากวิธีการที่ว่า
คุณมีที่จะคิดออก
mmhmm?
>> ผู้ชม: คุณบอกว่าก่อนหน้านั้น เราสามารถใช้ฟังก์ชั่นแฮชอื่น ๆ
ที่เราจะได้ไม่ต้อง สร้างฟังก์ชันแฮช?
>> ลำโพง 1: ใช่ขวา
ดังนั้นตัวอักษรสำหรับฟังก์ชันแฮชของคุณ เช่น google "ฟังก์ชันแฮช"
และมองหาบางคนที่เย็น
คุณยังไม่ได้คาดหวังว่าจะสร้าง ฟังก์ชั่นแฮชของคุณเอง
คนใช้จ่ายของพวกเขา วิทยานิพนธ์ในสิ่งเหล่านี้
>> จึงไม่ต้องกังวลเกี่ยวกับการสร้างของคุณเอง
หาหนึ่งออนไลน์จะเริ่มต้นด้วย
บางส่วนของพวกเขาที่คุณจะต้อง จัดการนิด ๆ หน่อย ๆ
เพื่อให้แน่ใจว่าผลตอบแทนประเภทตรง และ whatnot ดังนั้นในการเริ่มต้น
ผมจะแนะนำให้ใช้สิ่งที่ ง่ายจริงๆที่อาจจะแค่
hashes กับตัวอักษรตัวแรก
และจากนั้นเมื่อคุณมีการทำงานที่ ผสมผสานฟังก์ชันแฮชเย็น
mmhmm?
>> ผู้ชม: จะพยายามเป็นหรือ ที่มีประสิทธิภาพ แต่เพียงยาก, like--
>> ลำโพง 1: จึงพยายามที่ผมคิดว่า สังหรณ์ใจเป็นเรื่องยากที่จะดำเนินการ
แต่เป็นไปอย่างรวดเร็วมาก
แต่ต้องใช้พื้นที่มากขึ้น
อีกครั้งคุณสามารถเพิ่มประสิทธิภาพของทั้งสองของผู้ที่อยู่ใน วิธีที่แตกต่างกันและมีวิธี to--
ผู้ชม: วิธีการที่เราจัดลำดับเกี่ยวกับเรื่องนี้?
มัน matter--
>> ลำโพง 1: วิธีปกติดังนั้นคุณอย่างช้า ๆ
คุณกำลังจะได้รับการจัดลำดับในการออกแบบ
วิธีใดก็ตามที่คุณทำคุณต้องการ ให้แน่ใจว่าเป็นที่สง่างามที่สุดเท่าที่จะสามารถ
และมีประสิทธิภาพที่สุดเท่าที่จะสามารถ
แต่ถ้าคุณเลือกลองหรือกัญชา ตารางตราบใดที่การทำงาน
เรากำลังมีความสุขกับที่
และถ้าคุณใช้สิ่งที่ hashes กับตัวอักษรตัวแรกที่ปรับได้
เช่นอาจจะเหมือนการออกแบบที่ชาญฉลาด
เรายังถึง จุดใน semester-- นี้
ผมไม่ทราบว่าคุณ พวก noticed-- ถ้าคุณ
เกรด pset ลดลงเล็กน้อย เพราะการออกแบบและ whatnot,
ที่ดีอย่างสมบูรณ์แบบ
มันได้รับไปยังจุดที่คุณ โปรแกรมที่ได้รับความซับซ้อนมากขึ้น
มีสถานที่มากขึ้น คุณสามารถปรับปรุง
>> ดังนั้นจึงเป็นเรื่องปกติอย่างสมบูรณ์
มันไม่ใช่ว่าคุณ ทำเลวใน pset ของคุณ
มันเป็นเพียงแค่เราเป็นหนักขึ้นในขณะนี้คุณ
เพื่อให้ทุกคนรู้สึกว่า
ฉันเพียงแค่คะแนน psets ทั้งหมดของคุณ
ฉันรู้ว่าทุกคนจะรู้สึกว่ามัน
>> ดังนั้นไม่ต้องกังวลเกี่ยวกับการที่
และถ้าคุณมีคำถามใด ๆ เกี่ยวกับ psets ก่อนหรือวิธีที่คุณสามารถปรับปรุง
ฉันพยายามและแสดงความคิดเห็นที่เฉพาะเจาะจง สถานที่ แต่บางครั้งมันจะสาย
และฉันได้รับเบื่อ
มีสิ่งอื่น ๆ เกี่ยวกับโครงสร้างข้อมูล?
ผมมั่นใจว่าพวกคุณไม่ได้จริงๆ ต้องการพูดคุยเกี่ยวกับพวกเขาอีกต่อไป
แต่ถ้ามีผมมีความสุขที่จะ ไปกว่าพวกเขาเช่นเดียวเป็นอะไร
จากการบรรยายที่ผ่านมานี้ สัปดาห์หรือสัปดาห์ที่ผ่านมา
>> ฉันรู้ว่าเมื่อสัปดาห์ที่แล้วคือการตรวจสอบทั้งหมดเพื่อ เราอาจจะข้ามการตรวจสอบบางอย่าง
จากการบรรยาย
คำถามอื่น ๆ ใด ๆ ที่ฉันสามารถตอบ?
ตกลงขวาทั้งหมด
ดีที่พวกคุณได้รับการออก 15 นาทีก่อน
>> ฉันหวังว่านี้เป็นกึ่งประโยชน์อย่างน้อย และผมจะเห็นพวกคุณในสัปดาห์หน้า
หรือพฤหัสบดีเวลาทำการ
มีขอขนม สำหรับสัปดาห์ถัดไปก็คือสิ่งที่?
เพราะฉันลืมขนมวันนี้
แล้วเราก็นำขนมที่ผ่านมา สัปดาห์ แต่มันก็เป็นวันโคลัมบัส,
จึงมีเป็นเหมือนคนที่หก มีสี่ถุงขนมกับตัวเอง
ฉันสามารถนำ starbursts อีกครั้งถ้าคุณชอบ
starbursts?
ตกลงเสียงดี
มีวันที่ดีพวก