[เล่นเพลง] ลำโพง 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? ตกลงเสียงดี มีวันที่ดีพวก