>> [เล่นเพลง]
>> ANDI PENG: ยินดีต้อนรับสู่สัปดาห์ที่ 6 ของส่วน
เราผิดไปจากมาตรฐานของเรา เวลาส่วนวันอังคาร
ช่วงบ่ายไปเช้าวันอาทิตย์นี้น่ารัก
ขอบคุณสำหรับทุกคนที่ เข้าร่วมฉันในวันนี้ แต่อย่างจริงจัง
รอบของการปรบมือ
>> นั่นเป็นความพยายามที่ใหญ่สวย
ฉันเกือบจะไม่ได้ทำให้มัน ขึ้นมาในเวลา แต่มันก็ตกลง
ดังนั้นผมจึงรู้ว่าทุกท่าน ได้ทำเพียงแค่ไปที่การตอบคำถาม
ครั้งแรกของทั้งหมดยินดี พลิกด้านที่
>> ประการที่สองเราจะพูดคุยเกี่ยวกับเรื่องนี้
เราจะพูดคุยเกี่ยวกับการตอบคำถาม
เราจะพูดคุยเกี่ยวกับวิธีการ คุณกำลังทำในชั้นเรียน
คุณจะได้รับการปรับ
ฉันมีแบบทดสอบของคุณ คุณในตอนท้ายของที่นี่
ดังนั้นถ้าพวกคุณต้องการที่จะใช้ ดูที่มันทั้งหมดที่ดี
>> ดังนั้นอย่างรวดเร็วก่อนที่เราจะเริ่มต้นที่ วาระการประชุมในวันนี้มีดังนี้
ที่คุณสามารถดูเรา ยิงอย่างรวดเร็วโดยทั่วไป
ผ่านทั้งกลุ่มของโครงสร้างข้อมูล จริงๆจริงๆได้อย่างรวดเร็ว
ดังนั้นเป็นเช่นนี้มันจะไม่เป็น โต้ตอบสุดในวันนี้
มันก็จะเป็นชนิดของฉันตะโกน สิ่งที่คุณและถ้าผมสับสนคุณ
ถ้าฉันจะเร็วเกินไปแจ้งให้เราทราบ
พวกเขากำลังเพียงข้อมูลต่างๆ โครงสร้างและเป็นส่วนหนึ่ง
ของ pset ของคุณสำหรับ ที่จะเกิดขึ้นในสัปดาห์ที่คุณจะ
ถูกขอให้ดำเนินการอย่างใดอย่างหนึ่งของพวกเขา บางทีอาจจะเป็นสอง them-- สองของพวกเขา
ใน pset ของคุณ
ตกลงดังนั้นฉันแค่จะไป เริ่มต้นด้วยการประกาศบางส่วน
เราจะไปกว่ากองและการรอคิวใน ความลึกกว่าสิ่งที่เราทำก่อนที่จะตอบคำถาม
เราจะไปกว่าการเชื่อมโยง รายการอีกครั้งอีกครั้งหนึ่ง
เพิ่มเติมในเชิงลึกกว่าสิ่งที่ เรามีก่อนที่จะตอบคำถาม
และจากนั้นเราจะพูดคุยเกี่ยวกับกัญชา ตารางต้นไม้และพยายามที่
ทั้งหมดที่จำเป็นสำหรับ pset สวยของคุณ
และจากนั้นเราจะไปกว่าบาง เคล็ดลับที่เป็นประโยชน์สำหรับ pset5
>> ตกลงดังนั้นตอบคำถาม 0
เฉลี่ยเป็น 58%
มันเป็นที่ต่ำมากและเพื่อให้คุณผู้ชายทั้งหมด ไม่ได้เป็นอย่างดีมากตาม
กับที่
>> สวยมากกฎของหัวแม่มือคือถ้าคุณ ภายในเบี่ยงเบนมาตรฐานของค่าเฉลี่ย
โดยเฉพาะอย่างยิ่งนับตั้งแต่ที่เราอยู่ในน้อย ส่วนอุ่นหนาฝาคั่งคุณดีทั้งหมด
คุณกำลังติดตาม
ชีวิตเป็นสิ่งที่ดี.
>> ฉันรู้ว่ามันน่ากลัวที่จะคิดว่า ฉันได้เหมือน 40% ในการตอบคำถามนี้
ฉันจะล้มเหลวในชั้นนี้
ผมสัญญาว่าคุณคุณไม่ได้ จะล้มเหลวในชั้นเรียน
คุณกำลังดีทั้งหมด
>> สำหรับบรรดาผู้ที่ได้มากกว่า ค่าเฉลี่ยที่น่าประทับใจที่น่าประทับใจ
เหมือนอย่างจริงจังทำได้ดี
ฉันมีพวกเขากับฉัน
รู้สึกอิสระที่จะมารับพวกเขา ในตอนท้ายของส่วน
แจ้งให้เราทราบหากคุณมี ประเด็นคำถามกับพวกเขา
ถ้าเราเพิ่มขึ้นคะแนนของคุณ ที่ไม่ถูกต้องแจ้งให้เราทราบ
>> ตกลงดังนั้น pset5 นี้เป็นจริง สัปดาห์ที่แปลกสำหรับเยลในความรู้สึก
ที่ pset ของเราเป็นเพราะ วันพุธตอนเที่ยงรวมทั้ง
วันปลายดังนั้นจึงเป็นเรื่องจริง เนื่องจากในทางทฤษฎีวันอังคารเวลาเที่ยง
อาจเป็นหนึ่งในไม่เสร็จ ในวันอังคารเวลาเที่ยง
ที่ดีทั้งหมด
เรากำลังจะมีเวลาทำงาน คืนนี้เช่นเดียวกับคืนวันจันทร์
และทุกส่วนในสัปดาห์นี้จะ จริงจะกลายเป็นการประชุมเชิงปฏิบัติการ
ดังนั้นรู้สึกฟรีที่จะปรากฏใน ส่วนที่คุณต้องการใด ๆ
และพวกเขาจะเป็นชนิดของมินิ pset การประชุมเชิงปฏิบัติการเพื่อขอความช่วยเหลือเกี่ยวกับการที่
ดังนั้นเป็นเช่นนี้เป็นเพียงบางส่วน ที่เรากำลังเรียนการสอนวัสดุ
ทุกส่วนอื่น ๆ จะเน้น เฉพาะในการช่วยเหลือสำหรับ pset
ใช่?
>> ผู้ชม: อยู่ที่ไหนเวลาทำงาน?
>> ANDI PENG: เวลาทำการ tonight-- โอ้คำถามที่ดี
ผมคิดว่าคืนนี้เวลาราชการ อยู่ในน้านหรือคอมมอนส์
หากคุณตรวจสอบออนไลน์ CS50 และคุณจะไปเวลาทำการ
ควรจะมีการกำหนดเวลาที่ จะบอกคุณที่ทั้งหมดของพวกเขา
>> ฉันรู้ว่าทั้งคืน หรือวันพรุ่งนี้เป็นนกเป็ดน้ำ
และฉันคิดว่าเราอาจจะมี คอมมอนส์สำหรับคืนอื่น ๆ
ฉันไม่แน่ใจ.
คำถามที่ดี.
ตรวจสอบ CS50
>> เย็นคำถามใด ๆ เกี่ยวกับการ ระยะเวลาในการต่อไปเช่นวันที่สาม?
ผมสัญญาว่าคุณคนชอบเดวิด กล่าวมานี้เป็นด้านบนของเนินเขา
พวกคุณเกือบจะมี
เพียงสามวัน
รับมีและจากนั้นเราทุกคนจะลงมา
เราจะมีดีแบ่ง CS-ฟรี
เราจะกลับมา
เราจะดำน้ำในเว็บ การเขียนโปรแกรมและพัฒนา
สิ่งที่มีความสนุกสนานมากเมื่อเทียบ บางส่วนของ psets อื่น ๆ
และมันจะเย็นและ เราจะมีความสนุกสนานมากมาย
เราจะมีขนมอื่น ๆ อีกมากมาย
ขออภัยสำหรับลูกอม
ฉันลืมลูกอม
มันเป็นตอนเช้าที่หยาบกร้าน
ดังนั้นพวกคุณเกือบจะมี และผมภูมิใจของพวกคุณ
>> ตกลงดังนั้นกอง
ที่รักคำถามเกี่ยวกับแจ็ค และเสื้อผ้าของเขาในการตอบคำถามหรือไม่
ไม่มีใคร?
โอเคไม่เป็นไร.
>> เพื่อเป็นหลักในขณะที่คุณสามารถ ภาพแจ็ค, ผู้ชายคนนี้ที่นี่
รักที่จะใช้เสื้อผ้า ออกจากด้านบนของสแต็ค,
และเขาทำให้มันกลับไปยัง กองหลังจากที่เขาทำ
ดังนั้นในทางนี้เขาไม่เคย ดูเหมือนว่าจะได้รับ
ไปที่ด้านล่างของ สแต็คในเสื้อผ้าของเขา
ดังนั้นนี้ชนิดของการอธิบาย โครงสร้างข้อมูลพื้นฐาน
ของวิธีการที่สแต็คจะดำเนินการ
>> เป็นหลักคิด สแต็คเป็นกองของวัตถุใด ๆ
ที่คุณใส่ลงในสิ่งที่ด้านบนและ แล้วคุณป๊อปพวกเขาออกมาจากด้านบน
ดังนั้น LIFO เป็นตัวย่อที่เราชอบ เพื่อ use-- ในล่าสุด, First Out
และเพื่อให้มีอายุการใช้งานในด้านบนของ สแต็คเป็นคนแรกที่ออกมา
และเพื่อให้คำสองคำ เราชอบที่จะเชื่อมโยง
กับการที่จะเรียกว่าการผลักดันและป๊อป
เมื่อคุณผลักดันบางสิ่งบางอย่างบน สแต็คและคุณป๊อปมันกลับขึ้น
>> และเพื่อให้ฉันเดานี้เป็นชนิดของ แนวคิดที่เป็นนามธรรมสำหรับบรรดาของคุณ
ที่ต้องการเห็นเช่น การปฏิบัติจริงของเรื่องนี้
ในโลกแห่งความจริง
วิธีการหลายท่านได้เขียนเรียงความ อาจจะเหมือนชั่วโมงก่อนที่จะถูกกำหนด
และคุณตั้งใจลบขนาดใหญ่ ก้อนของมันเหมือนตั้งใจ?
และแล้วสิ่งที่ควบคุมทำ เราใช้ที่จะนำมันกลับมา?
ควบคุม-Z ใช่?
ควบคุม-Z ดังนั้นจำนวนครั้ง ที่ควบคุม-Z ได้บันทึกชีวิตของฉัน
มีการบันทึกไว้ตูดของฉันทุกครั้ง ที่ดำเนินการผ่านกอง
>> เป็นหลักข้อมูลทั้งหมด ที่อยู่ในเอกสาร Word ของคุณ
จะได้รับการผลักดันและโผล่ที่จะ
และเพื่อให้เป็นหลักเมื่อใดก็ตามที่คุณ ลบสิ่งที่คุณป๊อปมันสำรอง
และแล้วถ้าคุณต้องการมันกลับมาที่คุณ ผลักดันมันซึ่งเป็นสิ่งที่ควบคุมไม่-C
และฟังก์ชั่นโลกแห่งความจริงดังนั้น ของวิธีการที่โครงสร้างข้อมูลง่าย
สามารถช่วยให้มีชีวิตประจำวันของคุณ
>> ดังนั้น struct เป็นวิธีการที่ เราจริงสร้างกอง
เราพิมพ์กำหนด struct แล้ว เราเรียกว่าสแต็คที่ด้านล่าง
และภายในกอง เรามีสองพารามิเตอร์
ว่าเราเป็นหลักสามารถจัดการ เพื่อให้เรามีสายดาวถ่านความจุ
>> สิ่งที่จะทำ คือการสร้างอาร์เรย์
ที่เราสามารถจัดเก็บสิ่งที่คุณต้องการ ซึ่งเราสามารถตรวจสอบความสามารถของตน
ความจุเป็นเพียงจำนวนเงินสูงสุด รายการที่เราสามารถใส่ลงในอาร์เรย์นี้
ขนาด int เป็นเคาน์เตอร์ที่ช่วยให้ การติดตามของจำนวนรายการที่มีอยู่ในปัจจุบัน
ในกอง
ดังนั้นแล้วเราสามารถติดตาม, A, ทั้งสองวิธีใหญ่สแต็คที่เกิดขึ้นจริงคือ
และ B, วิธีการมากของสแต็คที่ เราเต็มไปเพราะเราไม่ต้องการ
ล้นมากกว่าสิ่งที่เป็นความสามารถของเรา
>> ดังนั้นสำหรับตัวอย่างเช่นนี้น่ารัก คำถามที่อยู่ในการตอบคำถามของคุณ
เป็นหลักทำอย่างไรเราจะผลักดัน ไปยังด้านบนของสแต็คที่
สวยเรียบง่าย
ถ้าคุณมองไปที่มัน เราจะเดินผ่านทางนี้
หาก [ไม่ได้ยิน] size-- จำได้ว่าเมื่อใดก็ตามที่คุณ
ต้องการเข้าถึงใด ๆ พารามิเตอร์ภายใน struct ที่
คุณทำชื่อของ struct.parameter ที่
>> ในกรณีนี้คือ ชื่อของสแต็คของเรา
เราต้องการที่จะเข้าถึงขนาด ของมันดังนั้นเราจึง s.size
ดังนั้นตราบใดที่ขนาดไม่ได้ เท่ากับกำลังการผลิตหรือเป็นเวลานาน
เป็นมันน้อยกว่ากำลังการผลิต อาจจะทำงานที่นี่
>> คุณต้องการที่จะเข้าถึงภายใน ของสแต็คของคุณเพื่อให้ s.strings,
และคุณกำลังจะไปใส่ที่หมายเลขใหม่ ที่คุณต้องการแทรกลงในมี
ขอเพียงบอกว่าเราจะต้องการ ใส่ int n ลงบนกอง
เราสามารถทำ s.strings, วงเล็บ s.size เท่ากับ n
เพราะขนาดเป็นที่ที่เรา ขณะนี้อยู่ในกอง
ถ้าเรากำลังจะผลักดัน มันเกี่ยวกับเราเข้าถึงเพียง
ทุกที่ขนาดคือ อิ่มปัจจุบันของกอง
และเราจะผลักดัน int n ลงบนมัน
แล้วเราต้องการที่จะให้แน่ใจว่า เรายังมีการเพิ่มขนาดของ n,
เพื่อให้เราสามารถติดตามเราได้ เพิ่มสิ่งที่พิเศษที่จะสแต็ค
ตอนนี้เรามีขนาดมากขึ้น
ที่นี่ไม่ทำให้รู้สึกถึง ทุกคนมีเหตุผลว่ามันทำงานอย่างไร
มันเป็นชนิดของอย่างรวดเร็ว
ผู้ชม: คุณสามารถไปมากกว่า s.stringss.strings [การ s.size] อีกครั้งหรือไม่
ANDI PENG: แน่นอนดังนั้นสิ่งที่ไม่ ขณะ s.size ให้เรา?
ผู้ชม: มันเป็นขนาดปัจจุบัน
ANDI PENG: แน่นอนดังนั้น ดัชนีปัจจุบันว่าขนาดของเราอยู่ที่
และเพื่อให้เราต้องการที่จะนำเลขที่ใหม่ ที่เราต้องการแทรกลงใน s.size
ที่ทำให้รู้สึก?
เพราะ s.strings ทั้งหมดที่ คือเป็นชื่อของอาร์เรย์
ทั้งหมดก็คือค​​ือการเข้าถึง อาร์เรย์ภายในโครงสร้างของเรา
และดังนั้นหากเราต้องการที่จะ n วางลงในดัชนีที่
เราก็สามารถเข้าถึงได้ โดยใช้วงเล็บ s.size
เย็น.
>> สิ่งที่ถูกต้อง, ป๊อป, ฉัน pseudocode มันออกมา สำหรับคุณผู้ชาย แต่แนวคิดที่คล้ายกัน
ที่ทำให้รู้สึก?
ถ้ามีขนาดที่ใหญ่กว่า กว่าศูนย์แล้วคุณ
รู้ว่าคุณต้องการที่จะใช้บางสิ่งบางอย่าง ออกมาเพราะถ้าขนาดไม่ได้
มากกว่าศูนย์แล้วคุณ มีอะไรในกอง
>> ดังนั้นคุณเพียงต้องการที่จะดำเนินการ รหัสนี้ก็สามารถ
ปรากฏว่ามีบางสิ่งบางอย่างที่จะปรากฏ
ดังนั้นถ้ามีขนาดที่ใหญ่กว่า มากกว่า 0 เราลบขนาด
เราพร่องขนาดแล้วกลับ สิ่งที่อยู่ภายในของมันเพราะ
โดย popping เราต้องการที่จะ การเข้าถึงสิ่งที่ถูกเก็บไว้
ในดัชนีของด้านบนของสแต็คที่
ทุกสิ่งที่ทำให้รู้สึก?
ถ้าผมทำพวกคุณเขียนออกนี้ คนที่คุณจะสามารถที่จะเขียนมันออกมา?
ตกลงพวกคุณสามารถเล่นรอบกับมัน
ไม่ต้องกังวลถ้าคุณไม่ได้รับมัน
เราไม่ได้มีเวลาที่จะรหัส มันออกมาในวันนี้เพราะเราได้
มีจำนวนมากของโครงสร้างเหล่านี้ ที่จะผ่านไป แต่เป็นหลัก
pseudocode มากคล้ายกันมากที่จะผลักดัน
เพียงแค่ทำตามตรรกะ
ให้แน่ใจว่าคุณกำลังเข้าถึงทั้งหมด คุณสมบัติของ struct คุณอย่างถูกต้อง
ใช่?
>> ผู้ชม: Will ภาพนิ่งเหล่านี้และ เรื่องทั้งหมดนี้จะมีขึ้นในวันนี้-ish?
ANDI PENG: เสมอครับ
ฉันจะพยายามที่จะนำ ขึ้นเช่นนี้หนึ่งชั่วโมงหลังจากที่
ฉันจะส่งอีเมลเดวิดเดวิดจะพยายามที่จะ ใส่มันขึ้นเหมือนชั่วโมงหลังจากนี้
>> ตกลงดังนั้นแล้วเราย้ายเข้าอื่น ๆ โครงสร้างข้อมูลที่น่ารักที่เรียกว่าคิว
ในฐานะที่พวกคุณสามารถดูที่นี่เป็น คิวอังกฤษในหมู่พวกเรา
ทั้งหมดมันเป็นเป็นเส้น
ตรงกันข้ามกับดังนั้นสิ่งที่ คุณคิดว่ากองคือ
คิวเป็นสิ่งที่ เหตุผลที่คุณคิดว่ามันเป็น
มันจัดขึ้นตามกฎของ FIFO ที่ ซึ่งเป็นครั้งแรกในครั้งแรกออก
หากคุณเป็นคนแรก หนึ่งในสายคุณ
คนแรกที่ ออกมาจากเส้น
>> ดังนั้นสิ่งที่เราชอบที่จะเรียกสิ่งนี้ เป็น dequeueing และ enqueueing
ถ้าเราต้องการที่จะเพิ่มบางสิ่งบางอย่าง คิวของเราเรา enqueue
ถ้าเราต้องการที่จะ dequeue หรือใช้ บางสิ่งบางอย่างออกไปเรา dequeue
>> รู้สึกเดียวกันเพื่อให้เราชนิดของ การสร้างองค์ประกอบขนาดคงที่เรา
สามารถจัดเก็บบางอย่าง สิ่ง แต่เรายังสามารถ
เปลี่ยนที่เรากำลังวาง พารามิเตอร์ภายในของพวกเขา
ขึ้นอยู่กับชนิดของ ฟังก์ชั่นที่เราต้องการ
ดังนั้นกองเราต้องการที่ผ่านมา อย่างใดอย่างหนึ่ง, N จะเป็นครั้งแรกหนึ่ง
เป็นคิวที่เราต้องการสิ่งแรก ในการที่จะเป็นสิ่งแรกที่ออกมา
>> ดังนั้น struct ประเภท กำหนดในขณะที่คุณสามารถดู
มันเป็นความแตกต่างกันเล็กน้อย จากสิ่งที่เป็นกอง
เพราะไม่เพียง แต่เราจะต้องเก็บ ติดตามในขณะนี้ขนาดที่เป็น
เรายังต้องการที่จะติดตามของศีรษะ เช่นเดียวกับที่เรามีอยู่ในปัจจุบัน
ดังนั้นผมจึงคิดว่ามันง่ายขึ้น ถ้าผมวาดขึ้นนี้
ดังนั้นลองจินตนาการว่าเรามีคิว จึงขอบอกว่าหัวเป็นขวาที่นี่
หัวของเส้นสมมติ เพียงแค่บอกว่าขณะนี้มี
และเราต้องการที่จะแทรก บางสิ่งบางอย่างเข้าไปในคิว
ฉันจะเรียกขนาดเป็นหลัก เป็นสิ่งเดียวกับหาง
ในตอนท้ายของทุกคิวของคุณคือ
ขอเพียงบอกว่าขนาดถูกต้องที่นี่
>> ดังนั้นวิธีที่จะหนึ่ง feasibly บางสิ่งบางอย่างใส่ลงในคิวหรือไม่?
เราทำอะไรดัชนีต้องการวาง ที่เราต้องการแทรกลงใน
ถ้านี่คือจุดเริ่มต้นของคุณ คิวและนี่คือจุดสิ้นสุดของมัน
หรือขนาดของมันที่เราทำ ต้องการที่จะเพิ่มวัตถุต่อไปหรือไม่
>> ผู้ชม: [ไม่ได้ยิน]
ANDI PENG: แน่นอนคุณต้องการเพิ่ม มันขึ้นอยู่กับที่คุณเขียน
ทั้งสองนี้จะว่างเปล่าหรือว่าจะว่างเปล่า
ดังนั้นคุณจึงต้องการที่จะเพิ่มก็อาจ ที่นี่เพราะถ้าขนาด is--
ถ้าเหล่านี้ทั้งหมดเต็มรูปแบบที่คุณต้องการ เพื่อเพิ่มที่นี่ใช่มั้ย?
>> และเพื่อให้เป็นในขณะที่มาก ที่เรียบง่ายไม่มากถูกต้องเสมอ
เพราะความแตกต่างหลัก ระหว่างคิวและกอง
คือคิวสามารถ จริงจัดการ
เพื่อให้การเปลี่ยนแปลงหัว ขึ้นอยู่กับที่คุณต้องการ
จุดเริ่มต้นของคิวของคุณที่จะเริ่มต้น
และเป็นผลให้หางของคุณ ยังจะมีการเปลี่ยนแปลง
และเพื่อให้ดูที่ รหัสนี้ได้ในขณะนี้
ในฐานะที่พวกคุณยังได้ขอให้ เขียนออกมาในการตอบคำถามที่กำหนดไว้เป็นลำดับ
บางทีเราจะพูดคุยผ่านทำไม คำตอบก็คือสิ่งที่มันเป็น
>> ฉันไม่สามารถค่อนข้างพอดีกับสายนี้ในหนึ่ง แต่เป็นหลักชิ้นส่วนของรหัสนี้
ควรจะอยู่ในหนึ่งบรรทัด
การใช้จ่ายเช่น 30 วินาที
ลองดูและดูว่าทำไม นี้เป็นวิธีที่ว่ามันเป็น
>> มาก struct คล้ายกันมากมาก โครงสร้างเช่นเดียวกับก่อนหน้านี้
สแต็คยกเว้นบางที หนึ่งบรรทัดของรหัส
และที่หนึ่งบรรทัดของรหัส กำหนดฟังก์ชันการทำงาน
และเป็นเรื่องที่แตกต่าง คิวจากกอง
>> ทุกคนต้องการที่จะใช้แทง ที่อธิบายว่าทำไมคุณได้
ได้รับนี้สิ่งที่ซับซ้อนในที่นี่?
เราจะเห็นการกลับมาของเรา โมดูลัสเพื่อนที่ยอดเยี่ยม
ในฐานะที่พวกคุณเร็ว ๆ นี้จะมา ที่จะรับรู้ในการเขียนโปรแกรม
เกือบตลอดเวลาที่คุณต้องการอะไร การห่อรอบอะไร
โมดูลัสที่เกิดขึ้นจะเป็นวิธีการที่จะทำมัน
ดังนั้นการรู้ว่าไม่มีใครต้องการ ที่จะพยายามอธิบายบรรทัดของรหัสที่?
ใช่คำตอบทั้งหมดที่มี ได้รับการยอมรับและยินดีต้อนรับ
ผู้ชม: คุณพูดกับผมหรือเปล่า
ANDI เป็ง: ใช่
ผู้ชม: โอ้ไม่เสียใจ
ANDI PENG: OK จึงขอ เดินผ่านรห​​ัสนี้
ดังนั้นเมื่อคุณกำลังพยายามที่จะ เพิ่มสิ่งบนคิว
ในกรณีที่น่ารักที่หัวเกิดขึ้น จะอยู่ตรงนี้มันเป็นเรื่องง่ายมากสำหรับเรา
เพียงแค่ไปที่สิ้นสุด ใส่บางสิ่งบางอย่างใช่มั้ย?
แต่จุดรวมของคิวเป็น ที่หัวสามารถจริงแบบไดนามิก
เปลี่ยนแปลงขึ้นอยู่กับที่เรา ต้องการเริ่มต้นของคิวของเราที่จะเป็น
และเป็นเช่นหาง ยังจะมีการเปลี่ยนแปลง
>> ดังนั้นคิดว่านี้ไม่ได้ คิว แต่นี้เป็นคิว
สมมติว่าหัวเป็นขวาที่นี่
สมมติว่าคิวเรามองเช่นนี้
ถ้าเราต้องการที่จะเปลี่ยนที่ จุดเริ่มต้นของบรรทัดคือ
สมมติว่าเราขยับหัว ด้วยวิธีนี้และขนาดที่นี่
>> ตอนนี้เราต้องการที่จะเพิ่มสิ่งที่ คิวนี้ แต่เป็นพวกคุณสามารถดู
มันไม่ง่ายที่จะเพียงแค่ เพิ่มสิ่งที่อยู่หลังขนาด
แล้วเพราะเราทำงานออกจาก ขอบเขตของอาร์เรย์ที่แท้จริงของเรา
ที่เราต้องการจริงๆเพิ่มอยู่ที่นี่
ที่ความงามของคิว คือว่าให้เรามองเห็นมัน
ดูเหมือนว่าสายไปเช่นนี้ แต่เมื่อเก็บไว้ในโครงสร้างข้อมูล
พวกเขาให้เป็นเหมือนวงจร
ชนิดของมันล้อมรอบ ไปข้างหน้าด้วยวิธีเดียวกัน
ว่าสายยังสามารถตัด รอบขึ้นอยู่กับทุกท่าน
ต้องการที่จะเริ่มต้นของบรรทัดที่จะเป็น
ดังนั้นถ้าเราใช้เวลา มองลงมาที่นี่ขอ
บอกว่าเราต้องการที่จะสร้าง ฟังก์ชั่นที่เรียกว่า Enqueue
เราต้องการที่จะเพิ่ม int n ลงในคิว
ถ้าเรา q.size q-- จะเรียกได้ว่าข้อมูลของเรา structure-- ถ้า queue.size ของเราไม่ได้
เท่ากับความจุหรือถ้า มันน้อยกว่ากำลังการผลิต
q.strings เป็นอาร์เรย์ที่อยู่ในคิวของเรา
เรากำลังจะไปตั้ง ที่เท่ากับ q.heads,
ซึ่งเป็นสิทธิที่นี่บวก q.size โมดูลัสโดยกำลังการผลิตที่
ห่อเรากลับมาที่นี่
>> ดังนั้นในตัวอย่างนี้ดัชนี ของหัว 1 ใช่มั้ย?
ดัชนีของขนาดเป็น 0, 1, 2, 3, 4
ดังนั้นเราจึงสามารถทำ 1 บวก 4 โมดูลัส โดยความสามารถของเราซึ่งเป็น 5
อะไรที่ทำให้เรา?
ดัชนีคืออะไรที่ ออกมาจากนี้หรือไม่?
>> ผู้ชม: 0
>> ANDI PENG: 0 ซึ่ง ที่จะเกิดขึ้นที่นี่
และเพื่อให้เราต้องการที่จะสามารถ เพื่อแทรกลงในที่นี่
และเพื่อให้สมการนี​​้ชนิดที่นี่ เพียงทำงานร่วมกับตัวเลขใด ๆ
ขึ้นอยู่กับที่ของคุณ หัวและขนาดของคุณ
ถ้าคุณรู้ว่าสิ่งเหล่านั้น สิ่งที่คุณรู้
ตรงที่คุณต้องการแทรก สิ่งที่อยู่หลังคิวของคุณ
ไม่ว่าทำให้ความรู้สึกที่ทุกคน?
>> ฉันรู้ว่าชนิดของสมอง ทีเซอร์โดยเฉพาะอย่างยิ่งตั้งแต่นี้
เดินเข้ามาในผลพวงของการตอบคำถามของคุณ
หวังว่าทุกคน แต่ สามารถเข้าใจ
ทำไมการแก้ปัญหานี้หรือนี้ ฟังก์ชั่นเป็นวิธีที่ว่ามันเป็น
ทุกคนบิตไม่มีความชัดเจนในที่?
ตกลง.
>> ดังนั้นตอนนี้ถ้าคุณ อยากจะ dequeue นี้
คือที่หัวของเราจะขยับ เพราะถ้าเราจะ dequeue,
เราไม่ได้จะปิดท้ายของคิว
เราต้องการที่จะออกหัวใช่มั้ย?
ดังนั้นเป็นผลให้หัวที่เกิดการเปลี่ยนแปลง และนั่นคือเหตุผลที่เมื่อคุณ enqueue,
คุณได้มีการติดตาม ที่หัวของคุณและขนาดของคุณ
จะต้องสามารถที่จะใส่ เข้าไปในตำแหน่งที่ถูกต้อง
>> ดังนั้นเมื่อคุณ dequeue, ฉันยัง pseudocode มันออกมา
รู้สึกอิสระที่จะถ้าคุณต้องการ พยายามที่การเข้ารหัสนี้ออก
คุณต้องการที่จะย้ายหัวใช่มั้ย?
ถ้าผมอยากจะ dequeue ผม จะย้ายหัวมากกว่า
นี้จะเป็นหัว
>> และขนาดของเราในปัจจุบันจะ ลบเพราะเราไม่ได้
มีสี่องค์ประกอบในอาร์เรย์
เรามีเพียงสามแล้วที่เราต้องการ ที่จะกลับมาอะไรก็ตามที่เก็บไว้ภายใน
ของหัวเพราะเราต้องการที่จะใช้เวลานี้ ค่าออกเพื่อให้คล้ายกับสแต็ค
เพียงแค่คุณถ่าย จากสถานที่ที่แตกต่างกัน
และคุณจะต้องกำหนดตัวชี้ของคุณ ไปยังสถานที่ที่แตกต่างกันเป็นผล
เหตุผลที่ทุกคนทำตาม?
ที่ดี
>> ตกลงดังนั้นเรากำลังจะพูดคุยเล็กน้อย เพิ่มเติมในเชิงลึกเกี่ยวกับรายการที่เชื่อมโยง
เพราะพวกเขาจะมากที่มีคุณค่ามาก สำหรับคุณในหลักสูตรของสัปดาห์นี้
psets
รายการที่เชื่อมโยงเป็นพวกคุณ สามารถจำสิ่งที่พวกเขามี
เป็นโหนดที่มีโหนดของบางอย่าง ค่านิยมของทั้งมูลค่าและตัวชี้
ที่มีการเชื่อมโยงกัน โดยคำแนะนำเหล่านั้น
และเพื่อให้โครงสร้างเกี่ยวกับวิธีการ เราสร้างโหนดที่นี่เป็นที่ที่เรา
มี n int ซึ่งเป็นสิ่งที่ มูลค่าในร้านค้าหรือสตริง n
หรือสิ่งที่คุณต้องการ เรียกว่าที่ n ดาวถ่าน
ดาวโหนดโครงสร้างซึ่งเป็นตัวชี้ ที่คุณต้องการที่จะมีในแต่ละโหนด
คุณกำลังจะมีที่ จุดที่ชี้ไปทางต่อไป
คุณจะมีหัว ของรายการที่เชื่อมโยงว่า
จะชี้ไปที่ส่วนที่เหลือของ ค่าอื่น ๆ และอื่น ๆ
จนในที่สุดคุณถึงจุดสิ้นสุด
และโหนดสุดท้ายนี้เป็นเพียง จะได้มีตัวชี้
มันจะชี้ไปที่ โมฆะและที่ว่าเมื่อ
คุณรู้ว่าคุณเคยตี ในตอนท้ายของรายการที่เชื่อมโยงของคุณ
คือเมื่อตัวชี้สุดท้ายของคุณ ไม่ได้ชี้ไปที่ใด
>> ดังนั้นเรากำลังจะไปอีกเล็กน้อยใน เชิงลึกเกี่ยวกับวิธีการหนึ่งที่จะเป็นไปได้
ค้นหารายการที่เชื่อมโยง
โปรดจำไว้ว่าสิ่งที่เป็นบางส่วนของ ข้อเสียของรายการที่เชื่อมโยง
โองการอาร์เรย์เกี่ยวกับการค้นหา
อาร์เรย์ที่คุณสามารถค้นหา binary แต่ ทำไมคุณไม่สามารถทำในรายการที่เชื่อมโยงหรือไม่?
>> ผู้ชม: เพ​​ราะพวกเขากำลังทั้งหมดที่เชื่อมต่อ แต่คุณไม่ทราบว่าค่อนข้าง
[ไม่ได้ยิน]
>> ANDI เป็ง: ใช่ว่าเพื่อให้จำ ที่ความฉลาดของอาร์เรย์
เป็นความจริงที่ว่าเรามี หน่วยความจำเข้าถึงโดยสุ่มที่
ถ้าผมต้องการค่าจากดัชนี หกผมก็อาจจะบอกว่าดัชนีหก
ให้ฉันค่าที่
และนั่นเป็นเพราะอาร์เรย์จะถูกจัดเรียง ในพื้นที่ที่อยู่ติดกันของหน่วยความจำ
ในสถานที่แห่งหนึ่งในขณะที่ ชนิดของรายการที่เชื่อมโยง
มีการสุ่มสลับรอบ ๆ และวิธีเดียวที่คุณสามารถหาหนึ่ง
ผ่านตัวชี้ที่จะบอกคุณ ที่อยู่ของโหนดที่ต่อไปคือ
>> และเพื่อให้เป็นผลให้วิธีเดียวที่ การค้นหาผ่านรายการที่เชื่อมโยง
คือการค้นหาเชิงเส้น
เพราะผมไม่ทราบว่าที่ ค่าที่ 12 ในรายการที่เชื่อมโยงเป็น
ฉันมีการสำรวจครบถ้วน ของรายการที่เชื่อมโยงอย่างใดอย่างหนึ่ง
โดยหนึ่งตั้งแต่หัวโหนดแรก ไปยังโหนดที่สองไปยังโหนดที่สาม
ตลอดทางลงไปจนในที่สุดผมก็จะได้รับ ไปยังที่ที่โหนดฉันกำลังมองหาที่
ดังนั้นในแง่นี้การค้นหา ในรายการที่เชื่อมโยงอยู่เสมอ n
มันเสมอ n
มันมักจะอยู่ในเส้นเวลา
>> และเพื่อให้รหัสที่ เราดำเนินการนี​​้และนี้
เป็นบิตใหม่สำหรับคุณผู้ชายตั้งแต่คุณ คนไม่ได้พูดคุยมากเกี่ยวกับหรือเคย
เห็นคำแนะนำในวิธีการ ค้นหาผ่านตัวชี้
ดังนั้นเราจะเดินผ่าน นี้มากช้ามาก
ดังนั้นการค้นหาบูลขวา ลองจินตนาการที่เราต้องการ
ในการสร้างฟังก์ชั่นที่เรียกว่า ค้นหาที่ผลตอบแทนจริง
ถ้าคุณพบว่าค่าภายในที่เชื่อมโยง รายการและจะกลับเท็จอย่างอื่น
รายการโหนดดาว ขณะนี้เพียงตัวชี้
ไปที่รายการแรกในรายการที่เชื่อมโยง
n int คือค่าที่คุณเป็น ค้นหาในรายการว่า
>> ดังนั้นตัวชี้ดาวโหนดเท่ากับรายการ
นั่นหมายความว่าเรากำลังตั้ง และการสร้างตัวชี้
ที่โหนดแรกภายในของรายการ
ทุกคนกับผมได้ไหม
ดังนั้นถ้าเราจะไป กลับมาที่นี่ผมจะต้อง
เริ่มต้นที่ตัวชี้ชี้ไปที่ หัวของรายการสิ่งที่เป็น
>> และจากนั้นเมื่อคุณได้รับลงที่นี่ ในขณะที่ตัวชี้ null ไม่เท่ากัน
เพื่อให้เป็นห่วงในการที่เราเป็น ไปได้ต่อมาภายใน
ส่วนที่เหลือของรายการของเราเพราะสิ่งที่ ที่เกิดขึ้นเมื่อตัวชี้เท่ากับ null?
เรารู้ว่าเรา have--
>> ผู้ชม: [ไม่ได้ยิน]
>> ANDI PENG: แน่นอนดังนั้นเราจึงรู้ว่า เราได้มาถึงจุดสิ้นสุดของรายการใช่มั้ย?
ถ้าคุณกลับไปที่นี่แต่ละโหนด ควรจะชี้ไปยังโหนดอื่น
และอื่น ๆ และอื่น ๆ จนกว่าคุณจะตีในที่สุด
หางของรายการที่เชื่อมโยงของคุณ ซึ่งมีตัวชี้ว่าเพียงแค่
ไม่ได้ชี้ทุกที่อื่นที่ไม่ใช่ไม่มี
และเพื่อให้คุณรู้ว่าโดยทั่วไป รายการของคุณยังคงมีขึ้น
จนกว่าตัวชี้ไม่เท่ากับ null เพราะเมื่อมันเท่ากับโมฆะ
คุณรู้ไหมว่าไม่มีสิ่งอื่น ๆ อีก
>> เพื่อให้เป็นวงที่เรากำลัง จะมีการค้นหาที่เกิดขึ้นจริง
และถ้า pointer-- คุณเห็น ชนิดของฟังก์ชั่นที่มีลูกศร?
ดังนั้นถ้าจุดที่ชี้ไปยัง n ถ้า ชี้ที่ n เท่ากับเท่ากับ n,
เพื่อให้หมายความว่าหาก ตัวชี้ว่าคุณ
หาที่สิ้นสุดของแต่ละคน โหนดเป็นจริงเท่ากับค่า
คุณกำลังมองหาแล้ว คุณต้องการที่จะกลับจริง
ดังนั้นโดยทั่วไปถ้าคุณที่โหนดว่า มีค่าที่คุณกำลังมองหา
คุณรู้ว่าคุณได้รับ สามารถที่จะประสบความสำเร็จในการค้นหา
>> มิฉะนั้นคุณต้องการตั้งค่า ตัวชี้ของคุณไปยังโหนดถั​​ดไป
นั่นคือสิ่งที่สายที่นี่ที่ทำ
ชี้เท่ากับตัวชี้ต่อไป
ทุกคนดูว่าที่ทำงาน?
>> และเป็นหลักที่คุณกำลังจะเพียง สำรวจความสมบูรณ์ของรายการ
รีเซ็ตตัวชี้ของคุณเวลาจนกว่าแต่ละ ในที่สุดคุณตีท้ายของรายการ
และคุณรู้ว่าไม่มี โหนดมากขึ้นในการค้นหาผ่าน
และจากนั้นคุณสามารถกลับเท็จ เพราะคุณรู้ว่าโอ้ดี
ถ้าฉันได้รับสามารถที่จะค้นหา ผ่านครบถ้วนของรายการ
ถ้าในตัวอย่างนี้ถ้าผมต้องการ ที่จะมองหาค่าของ 10
และฉันเริ่มต้นที่หัวและ ฉันค้นหาทั้งหมดทางลง
และในที่สุดผมก็มาถึงนี้ซึ่ง ชี้ที่ชี้ให้เป็นโมฆะที่
ฉันรู้ว่าอึผมคิดว่า 10 ไม่ได้อยู่ใน รายการนี​​้เพราะผมไม่สามารถหาได้
และฉันในตอนท้ายของรายการ
และในกรณีที่คุณรู้ ฉันจะกลับเท็จ
>> ปล่อยให้แช่ในนิด ๆ หน่อย ๆ
นี้จะสวย สิ่งสำคัญสำหรับ pset ของคุณ
ตรรกะของมันเป็นเรื่องง่ายมากอาจ syntactically เพียงการดำเนินการนั้น
พวกคุณต้องการที่จะทำให้ แน่ใจว่าคุณเข้าใจ
เย็น.
>> ตกลงดังนั้นวิธีการที่เราจะเป็น แทรกโหนดขวา
ลงในรายการเพราะจำได้ว่า สิ่งที่เป็นสิ่งที่ของผลประโยชน์
ของการมีรายการที่เชื่อมโยงกับ อาร์เรย์ในแง่ของการจัดเก็บอยู่แล้ว?
>> ผู้ชม: มันเป็นแบบไดนามิก ดังนั้นจึงเป็นเรื่องง่ายขึ้น to--
>> ANDI PENG: แน่นอน, ดังนั้นจึงเป็นแบบไดนามิกซึ่ง
หมายความว่ามันสามารถขยายและหดตัว ขึ้นอยู่กับความต้องการของผู้ใช้
ดังนั้นในแง่นี้เราไม่จำเป็นต้อง เสียหน่วยความจำที่ไม่จำเป็นเพราะผม
ถ้าฉันไม่ทราบว่าหลายค่าที่ฉันต้องการ ในการจัดเก็บก็ไม่ได้ทำให้ความรู้สึกของฉัน
เพื่อสร้างอาร์เรย์เพราะ ถ้าผมต้องการที่จะเก็บค่า 10
และฉันสร้างอาร์เรย์ 1,000 ที่ จำนวนมากของหน่วยความจำที่สูญเสียได้รับการจัดสรร
นั่นเป็นเหตุผลที่เราต้องการที่จะใช้เชื่อมโยง รายการที่จะสามารถแบบไดนามิก
เปลี่ยนหรือหดขนาดของเรา
>> และเพื่อที่จะทำให้การแทรก บิตซับซ้อนมากขึ้น
เนื่องจากเราไม่สามารถเข้าถึงองค์ประกอบแบบสุ่ม วิธีการที่เราจะของอาร์เรย์
ถ้าผมต้องการแทรกองค์ประกอบ เข้าสู่ดัชนีที่เจ็ด
ฉันสามารถใส่ เข้าสู่ดัชนีที่เจ็ด
ในรายการที่เชื่อมโยงก็ไม่ได้ ค่อนข้างทำงานได้อย่างง่ายดาย
และดังนั้นหากเราต้องการที่จะใส่ ที่นี่หนึ่งในรายการที่เชื่อมโยง
สายตามันเป็นเรื่องง่ายมากที่จะเห็น
เราเพียงแค่ต้องการที่จะใส่ที่นั่น ที่เหมาะสมในการเริ่มต้นของรายการ
หลังจากที่หัว
>> แต่วิธีการที่เรามีการกำหนด ชี้เป็นบิตซับซ้อน
หรือเหตุผลที่มันทำให้รู้สึก แต่ คุณต้องการที่จะให้แน่ใจว่าคุณมีมัน
เพราะลงอย่างสมบูรณ์ สิ่งสุดท้ายที่คุณต้องการ
คือการกำหนดตัวชี้ที่ วิธีการที่เรากำลังทำอะไรที่นี่
หากคุณ dereference ตัวชี้จากหัวถึง 1,
แล้วทั้งหมดในทันที ส่วนที่เหลือของรายการที่เชื่อมโยงของคุณ
จะหายไปเพราะคุณมีไม่จริง สร้างอะไรชั่วคราว
ที่ชี้ไปที่ 2
ถ้าคุณกำหนดตัวชี้แล้ว ส่วนที่เหลือของรายการของคุณจะหายไปโดยสิ้นเชิง
ดังนั้นคุณจึงต้องการที่จะเป็น มากระวังให้มากที่นี่
ก่อนกำหนด ตัวชี้จากสิ่งที่คุณ
ต้องการแทรกลงในที่ใดก็ตาม คุณต้องการและจากนั้นคุณ
สามารถ dereference ส่วนที่เหลือของรายการของคุณ
>> ดังนั้นนี้สำหรับทุกที่ คุณกำลังพยายามที่จะใส่ลงใน
ถ้าคุณต้องการที่จะแทรกที่ หัวถ้าคุณต้องการที่จะตอบที่นี่
ถ้าคุณต้องการที่จะแทรก ท้ายที่สุดดี, เอ็นฉัน
คิดว่าคุณจะเพียงแค่ มีตัวชี้ไม่มี แต่คุณ
ต้องการที่จะให้แน่ใจว่าคุณทำไม่ได้ สูญเสียส่วนที่เหลือของรายการของคุณ
คุณต้องการให้แน่ใจว่า โหนดใหม่ของคุณจะชี้
ที่มีต่อสิ่งที่คุณ ต้องการแทรกลง
และจากนั้นคุณสามารถเพิ่มผูกมัดบน
ทุกคนชัดเจน?
>> นี้เป็นไปได้ หนึ่งในปัญหาที่แท้จริง
หนึ่งในประเด็นที่สำคัญมากที่สุด คุณกำลังจะมีใน pset ของคุณ
คือการที่คุณกำลังจะพยายามที่จะสร้าง รายการที่เชื่อมโยงและสิ่งที่แทรก
แต่แล้วก็สูญเสีย ส่วนที่เหลือของรายการที่เชื่อมโยงของคุณ
และคุณกำลังจะเป็นเหมือนผม ไม่ทราบว่าทำไมนี้เกิดขึ้น?
และมันก็เป็นความเจ็บปวดที่จะไปผ่าน และค้นหาทั้งหมดของตัวชี้ของคุณ
>> และฉันก็รับประกันคุณ pset นี้ การเขียนและการวาดภาพโหนดเหล่านี้ออก
จะมีมากที่เป็นประโยชน์มาก
ดังนั้นคุณสมบูรณ์สามารถติดตาม ของที่ชี้ทั้งหมดของคุณมี
สิ่งที่เกิดขึ้นที่ไม่ถูกต้อง โหนดทั้งหมดที่คุณมี
สิ่งที่คุณต้องทำเพื่อให้เข้าถึงหรือ แทรกหรือลบหรือใด ๆ ของพวกเขา
ทุกคนที่ดีกับที่?
เย็น.
>> ดังนั้นถ้าเราต้องการที่จะดูรหัส?
โอ้ผมไม่ทราบว่าถ้าเรา สามารถดูตกลง the-- ดังนั้น
ที่ด้านบนทั้งหมดเป็นเป็นฟังก์ชั่น แทรกชื่อที่เราต้องการ
แทรก n int ลงในรายการที่เชื่อมโยง
เรากำลังจะเดินผ่านทางนี้
มันมากรหัสจำนวนมากไวยากรณ์ใหม่
เราจะตกลง
>> ดังนั้นขึ้นที่ด้านบนเมื่อใดก็ตามที่ เราต้องการที่จะสร้างอะไร
ทำในสิ่งที่เราต้องทำโดยเฉพาะอย่างยิ่งถ้าคุณ อยากให้มันไม่ถูกเก็บไว้ในกอง
แต่ในกองหรือไม่
เราไป malloc ใช่มั้ย?
ดังนั้นเรากำลังจะสร้างตัวชี้
โหนดชี้เท่ากับใหม่ malloc ขนาดของโหนด
เพราะเราต้องการโหนดที่ถูกสร้างขึ้น
เราต้องการปริมาณของ หน่วยความจำที่โหนดจะขึ้น
ที่จะได้รับการจัดสรรสำหรับ การสร้างโหนดใหม่
>> และจากนั้นเราจะตรวจสอบเพื่อ ดูว่าเท่ากับใหม่เท่ากับ null
โปรดจำไว้ว่าสิ่งที่เรากล่าวว่า?
สิ่งที่คุณ malloc, สิ่งที่คุณมักจะต้องทำอย่างไร
คุณต้องตรวจสอบเพื่อดู หรือไม่ว่าเป็นโมฆะ
>> ตัวอย่างเช่นถ้าปฏิบัติการของคุณ ระบบเต็มสมบูรณ์
ถ้าคุณมีหน่วยความจำเพิ่มเติมได้ที่ และคุณพยายามที่จะ malloc,
มันจะกลับมา null สำหรับคุณ
ดังนั้นถ้าคุณพยายามที่จะใช้ เมื่อได้มีการชี้ให้เป็นโมฆะ,
คุณจะไม่สามารถ ในการเข้าถึงข้อมูลที่
และเพื่อให้เป็นเช่นนี้เราต้องการที่จะทำให้ แน่ใจว่าเมื่อใดก็ตามที่คุณกำลัง mallocing,
คุณมักจะตรวจสอบเพื่อดูว่า หน่วยความจำที่ให้กับคุณเป็นโมฆะ
และถ้ามันไม่ได้แล้วเราสามารถย้าย กับส่วนที่เหลือของรหัสของเรา
>> ดังนั้นเรากำลังจะไป เริ่มต้นโหนดใหม่
เรากำลังจะทำใหม่เท่ากับ n n
แล้วเรากำลังจะทำ กำหนดตัวชี้ใหม่ใหม่
เพื่อ null เพราะตอนนี้เราทำไม่ได้ ต้องการอะไรมันจะชี้ไปที่
เรามีความคิดที่ไม่มี มันจะทำให้คุณ,
แล้วถ้าเราต้องการ ใส่ที่ศีรษะ
แล้วเราสามารถกำหนด ตัวชี้ไปที่หัว
ทุกคนไม่ทำตามตรรกะ ของการที่ที่เกิดขึ้น?
>> ทั้งหมดที่เรากำลังทำคือการสร้างใหม่ โหนด, การตั้งค่าตัวชี้ให้เป็นโมฆะ,
แล้วกำหนดใหม่ มันไปที่หัวถ้าเรา
รู้ว่าเราต้องการที่จะใส่ที่หัว
และแล้วหัวจะไป ชี้ไปโหนดใหม่ที่
ทุกคนตกลงกับที่?
>> ดังนั้นจึงเป็นกระบวนการสองขั้นตอน
คุณได้มีการกำหนดเป็นครั้งแรก สิ่งที่คุณกำลังสร้าง
ตั้งชี้ไปที่ อ้างอิงและจากนั้นคุณ
สามารถชนิดของ dereference ตัวชี้เป็นครั้งแรก
และชี้ไปที่โหนดใหม่
เมื่อใดก็ตามที่คุณต้องการแทรกมัน ตรรกะที่จะไปถือเป็นจริง
>> มันเป็นชนิดเช่นการกำหนด ตัวแปรชั่วคราว
โปรดจำไว้ว่าคุณได้มี เพื่อให้แน่ใจว่าคุณ
จะไม่สูญเสียการติดตามของถ้าคุณกำลังแลกเปลี่ยน
คุณต้องการที่จะตรวจสอบให้แน่ใจว่าคุณมี ตัวแปรชั่วคราวที่ชนิดของการเก็บ
ติดตามการที่สิ่งหนึ่งที่ จะถูกเก็บไว้เพื่อให้คุณ
ไม่เสียค่าใด ๆ ในการเรียนการสอน เช่น messing รอบกับมัน
>> ตกลงดังนั้นรหัสจะอยู่ที่นี่
พวกคุณจะดูหลังจากที่ส่วน
มันจะมี
>> ดังนั้นผมคิดว่าวิธีการที่ไม่ นี้แตกต่างกันถ้าเราต้องการ
เพื่อแทรกลงในกลางหรือปลายหรือไม่
ทุกคนมีความคิดของสิ่งที่ pseudocode เป็นอ้างอิงตรรกะ
ที่เราจะต้องใช้เวลาถ้าเราต้องการ ที่จะแทรกอยู่ตรงกลาง?
ดังนั้นถ้าเราต้องการที่จะใส่ไว้ที่ หัวทุกสิ่งที่เราทำคือการสร้างโหนดใหม่
เราตั้งตัวชี้ของที่ โหนดใหม่เพื่อสิ่งที่หัว
และจากนั้นเราตั้งหัว ไปยังโหนดใหม่ใช่มั้ย?
ถ้าเราต้องการที่จะแทรกอยู่ตรงกลาง ของรายการสิ่งที่เราจะต้องทำอย่างไร
>> ผู้ชม: มันจะยังคง จะเป็นกระบวนการที่คล้ายกัน
เช่นการกำหนดตัวชี้และ แล้วการกำหนดตัวชี้ว่า
แต่เราจะต้องมีการค้นหา
>> ANDI PENG: แน่นอนดังนั้นว่า กระบวนการเดียวกันยกเว้นคุณ
ต้องค้นหาที่ว่าคุณ ต้องการที่ชี้ใหม่ที่จะไปลง
ดังนั้นถ้าผมต้องการที่จะใส่ลงใน ช่วงกลางของการเชื่อมโยง list-- ตกลง
ขอบอกว่าเป็นรายการที่เชื่อมโยงของเรา
ถ้าเราต้องการที่จะใส่ที่นี่ เรากำลังจะสร้างโหนดใหม่
เรากำลังจะไป malloc
เรากำลังจะสร้างโหนดใหม่
เรากำลังจะไปกำหนด ตัวชี้ของโหนดที่นี่
>> แต่ปัญหาที่แตกต่าง จากการที่หัวเป็น
คือการที่เรารู้ว่า ที่หัวเป็น
มันเป็นที่ที่เหมาะสมในครั้งแรกใช่ไหม?
แต่ที่นี่เราได้มีการติดตาม ของที่เรากำลังใส่ลงใน
ถ้าเราใส่ของเรา โหนดที่นี่เรามี
เพื่อให้แน่ใจว่า ก่อนหน้านี้หนึ่งไปยังโหนดนี้
เป็นสิ่งหนึ่งที่ reassigns ตัวชี้
ดังนั้นแล้วคุณจะต้องชนิดของ ติดตามในสองสิ่ง
ถ้าคุณสามารถติดตามของที่นี้ โหนดปัจจุบันคือการใส่ลงใน
นอกจากนี้คุณยังต้องติดตามการที่ โหนดก่อนหน้านี้ที่คุณกำลังมองหา
ยังอยู่ที่นั่น
ทุกคนที่ดีกับที่?
ตกลง.
>> วิธีการเกี่ยวกับการใส่ลงไปในที่สุด?
ถ้าผมต้องการที่จะเพิ่ม here-- ถ้าผมต้องการ การเพิ่มโหนดใหม่ที่ส่วนท้ายของรายการที่
วิธีการที่ฉันอาจจะไปเกี่ยวกับการทำเช่นนั้น?
ผู้ชม: ดังนั้นในปัจจุบัน หนึ่งที่ผ่านมาชี้ให้เป็นโมฆะ
ANDI เป็ง: ใช่
ตรงนี้จึงเป็นหนึ่ง ในปัจจุบันคือการชี้ให้เห็นที่จะรู้ว่า
และผมคิดว่าในความรู้สึกนี้ก็ ง่ายมากที่จะเพิ่มถึงจุดสิ้นสุดของรายการ
สิ่งที่คุณต้องทำคือการตั้งค่า เท่ากับเป็นโมฆะแล้วบูม
มีสิทธิที่ง่ายมาก
ง่ายมาก.
>> คล้ายกับ มุ่ง แต่เหตุผลที่คุณ
ต้องการที่จะให้แน่ใจว่าขั้นตอน คุณจะใช้เวลาที่มีต่อการดำเนินการใด ๆ ในเรื่องนี้
คุณไปพร้อม
มันง่ายมากที่จะอยู่ตรงกลาง ของรหัสของคุณได้รับการติดขึ้นบน
โอ้ฉันมีตัวชี้จำนวนมาก
ผมไม่ทราบว่า สิ่งที่จะชี้ไปที่
ฉันไม่ได้รู้ว่าโหนดซึ่งฉัน
เกิดอะไรขึ้น?
>> ผ่อนคลายสงบลงหายใจลึก
วาดออกรายการที่เชื่อมโยงของคุณ
ถ้าคุณบอกว่าฉันรู้ว่าที่ว่า ฉันต้องการที่จะแทรกเข้ามาในนี้
และฉันรู้ว่าวิธีการที่กำหนดของฉัน ตัวชี้มากง่ายมากที่จะถ่ายภาพ
out-- มากง่ายมากที่จะไม่ได้ ได้หายไปในข้อบกพร่องของรหัสของคุณ
ทุกคนตกลงกับที่?
ตกลง.
>> ดังนั้นผมคิดว่าแนวคิดที่เรายังไม่ได้ จริงๆก่อนที่จะพูดคุยเกี่ยวกับตอนนี้
และผมคิดว่าคุณอาจจะ จะไม่พบ yet-- มาก
มันเป็นชนิดของ concept-- ขั้นสูง คือการที่เราจะมีข้อมูลที่
โครงสร้างที่เรียกว่ารายการที่เชื่อมโยงเป็นทวีคูณ
ดังนั้นในขณะที่พวกคุณสามารถดู ทุกสิ่งที่เรากำลังทำคือการสร้าง
ค่าที่เกิดขึ้นจริงเป็นพิเศษ ตัวชี้ในแต่ละโหนดของเรา
ที่ยังชี้ไปยังโหนดก่อนหน้านี้
ดังนั้นไม่เพียง แต่เรามีของเรา โหนดชี้ไปที่หน้าหนึ่ง
พวกเขายังชี้ไปที่หนึ่งก่อนหน้านี้
ฉันจะที่จะไม่สนใจทั้งสองได้ในขณะนี้
>> ดังนั้นแล้วคุณมีโซ่ ที่สามารถเคลื่อนที่ได้ทั้งสองวิธี
และจากนั้นก็เป็นบิตง่ายขึ้น เหตุผลที่จะทำตาม
เช่นเดียวกับที่นี่แทน ติดตามความเคลื่อนไหวของโอ้ฉัน
ต้องรู้ว่าโหนดนี้คือ คนที่ฉันต้องกำหนด,
ฉันสามารถไปที่นี่และ เพียงดึงก่อนหน้านี้
จากนั้นฉันก็รู้ว่าที่ ที่อยู่และจากนั้นคุณ
ไม่ได้มีการสำรวจ สมบูรณ์ของรายการที่เชื่อมโยง
เป็นบิตง่ายขึ้น
>> แต่เป็นเช่นนี้คุณต้องเป็นทวีคูณ จำนวนของตัวชี้ที่
ที่สองจำนวนของหน่วยความจำ
มันมากของตัวชี้ที่จะติดตาม
เป็นบิตที่ซับซ้อนมากขึ้น แต่ก็ ผู้ใช้ที่เป็นมิตรอีกเล็กน้อยขึ้นอยู่กับ
กับสิ่งที่คุณกำลังพยายามที่จะประสบความสำเร็จ
>> ดังนั้นชนิดของข้อมูลนี้ โครงสร้างทั้งหมดที่มีอยู่
และโครงสร้างเป็นอย่างมาก ง่ายยกเว้นสิ่งที่คุณกำลังมีอยู่
แทนเพียงตัวชี้ไปข้างหน้า คุณยังมีตัวชี้ไปก่อนหน้านี้
นั่นคือทั้งหมดที่แตกต่างกันคือ
ทุกคนที่ดีกับที่?
เย็น.
>> สิทธิทั้งหมดดังนั้นตอนนี้ฉัน จริงๆอาจจะใช้จ่าย
เช่น 15-20 นาทีหรือเป็นกลุ่ม ส่วนที่เหลือของเวลาในส่วน
พูดคุยเกี่ยวกับตารางแฮช
จำนวนของพวกคุณ ได้อ่านข้อมูลจำเพาะ pset5?
สิทธิทั้งหมดที่ดี
นั่นคือสูงกว่า 50% ของตามปกติ
ไม่เป็นไร.
>> ดังนั้นในขณะที่พวกคุณจะได้เห็น คุณความท้าทายในการ pset5
จะได้รับการดำเนินการตามพจนานุกรม ที่คุณโหลดกว่า 140,000 คำ
ที่เราให้คุณและตรวจสอบการสะกด มันกับข้อความทั้งหมด
เราจะให้คุณแบบสุ่ม ชิ้นส่วนของวรรณกรรม
เราจะให้คุณโอเดสซี
เราจะให้คุณอีเลียด
เราจะให้คุณออสติน
>> และความท้าทายของคุณ จะได้รับการตรวจสอบการสะกด
ทุกคำเดียวในทุก พจนานุกรมเหล่านั้น
เป็นหลักที่มีตรวจสอบการสะกดของเรา
และเพื่อให้มีชิ้นส่วนเพียงไม่กี่ ของการสร้าง pset นี้
แรกที่คุณต้องการที่จะเป็น สามารถโหลดจริง
ทุกคำของคุณลงใน พจนานุกรมและจากนั้นคุณ
ต้องการที่จะสามารถที่จะ ตรวจสอบการสะกดทั้งหมดของพวกเขา
และเพื่อให้เป็นเช่นนี้คุณจะต้อง โครงสร้างข้อมูลที่สามารถทำอย่างรวดเร็วนี้
และมีประสิทธิภาพและแบบไดนามิก
>> ดังนั้นผมจึงคิดว่าง่ายที่สุด วิธีการที่จะทำเช่นนี้คุณ
อาจจะสร้างอาร์เรย์ใช่มั้ย?
วิธีที่ง่ายที่สุดในการจัดเก็บที่เป็นคุณ สามารถสร้างอาร์เรย์ของ 140,000 คำ
และเพียงแค่วางพวกเขาทั้งหมดที่มีและ จากนั้นพวกเขาโดยการสำรวจค้นหาแบบทวิภาค
หรือโดยการเลือกหรือ not-- ขอโทษที่การเรียงลำดับ
คุณสามารถจัดเรียงพวกเขาแล้วพวกเขาสำรวจ โดยการค้นหาแบบไบนารีหรือเพียงแค่การค้นหาเชิงเส้น
และเพียงแค่คำพูดสุดท้าย แต่ที่ จะใช้เวลาเป็นจำนวนมากของหน่วยความจำ
และก็ไม่ได้มีประสิทธิภาพมาก
>> และเพื่อที่เรากำลังจะเริ่มต้น พูดคุยเกี่ยวกับวิธีการทำ
เวลาทำงานของเรามีประสิทธิภาพมากขึ้น
และเป้าหมายของเราคือการได้รับ เวลาคงที่
มันเกือบจะเหมือนอาร์เรย์ที่ คุณมีการเข้าถึงทันที
ถ้าผมต้องการที่จะค้นหาอะไร ฉันต้องการที่จะสามารถที่จะเพียงแค่
บูมพบว่ามันตรงและดึงออก
และเพื่อให้โครงสร้างที่ เราจะกลายเป็นความใกล้ชิด
เพื่อให้สามารถเข้าถึงอย่างต่อเนื่อง เวลานี้ศักดิ์สิทธิ์
ในการเขียนโปรแกรมของอย่างต่อเนื่อง เวลาที่เรียกว่าตารางแฮช
และเพื่อให้เดวิดกล่าวถึงก่อนหน้านี้ [ไม่ได้ยิน] นิด ๆ หน่อย ๆ ในการบรรยาย
แต่เรากำลังจะไปจริงๆ ดำน้ำลึกในสัปดาห์นี้
ในส่วนที่เกี่ยวกับการ วิธีตารางแฮชผลงาน
>> ดังนั้นวิธีการที่แฮช ตารางงานยกตัวอย่างเช่น
ถ้าผมต้องการที่จะเก็บพวงของคำเป็น พวงของคำในภาษาอังกฤษ
ผมในทางทฤษฎีสามารถใส่ กล้วยแอปเปิ้ลกีวีมะม่วงคู่
และแคนตาลูปทั้งหมดเพียงอาร์เรย์
พวกเขาอาจจะทั้งหมดพอดีและพบว่า
มันต้องการจะเป็นชนิดของความเจ็บปวดไปยัง ค้นหาผ่านเข้าถึงและ
แต่วิธีที่ง่ายของการทำเช่นนี้คือ ที่เราสามารถสร้างโครงสร้างจริง
เรียกว่าตารางแฮชที่เราสับ
เราทำงานทั้งหมดของคีย์ของเราผ่าน ฟังก์ชั่นแฮช, สมการ,
ที่จะเปลี่ยนพวกเขาทั้งหมดลง การเรียงลำดับของค่าบางอย่าง
ว่าแล้วเราสามารถจัดเก็บลงบน หลักอาร์เรย์ของรายการที่เชื่อมโยง
>> และอื่น ๆ ที่นี่ถ้าเราต้องการ ในการจัดเก็บคำในภาษาอังกฤษ,
ที่อาจเกิดขึ้นเราสามารถทำได้เพียงแค่ฉันทำไม่ได้ รู้ว่าเปิดทุกตัวอักษรตัวแรก
เป็นประเภทของตัวเลขบางอย่าง
และอื่น ๆ ยกตัวอย่างเช่นถ้าผมต้องการ ที่จะตรงกันกับ apple--
หรือมีค่าดัชนีของ 0 และ B จะตรงกันกับ 1,
เราสามารถมี 26 รายการ ที่เพียงแค่สามารถจัดเก็บ
ทุกตัวอักษรของ ตัวอักษรที่เราจะเริ่มต้นด้วย
และจากนั้นเราจะได้มี แอปเปิ้ลที่ดัชนีของ 0
เราสามารถมีกล้วยที่ดัชนีของ 1, แคนตาลูปที่ดัชนีของ 2,
และอื่น ๆ และอื่น ๆ.
และทำให้ถ้าผมต้องการที่จะค้นหา ตารางแฮชของฉันและแอปเปิ้ลการเข้าถึง
ฉันรู้ว่าแอปเปิ้ลจะเริ่มต้นด้วย ต่อ A และฉันรู้ว่า
ว่ามันจะต้องเป็นและกัญชา ตารางที่ดัชนี 0 เพราะ
ของการทำงานที่ได้รับมอบหมายก่อนหน้านี้
>> ดังนั้นผมจึงไม่ทราบว่าเรามี โปรแกรมที่ใช้
คุณจะได้รับค่าใช้จ่ายด้วย arbitrarily-- ไม่พล
กับความพยายามที่จะคิด คิดว่าสมการที่ดี
เพื่อให้สามารถที่จะแพร่กระจาย ออกทั้งหมดของค่าของคุณ
ในทางที่พวกเขาสามารถเข้าถึงได้อย่างง่ายดาย ได้ในภายหลังด้วยเช่นสมการ
ที่คุณเองรู้
ดังนั้นในแง่ที่ว่าถ้าผมอยากจะไป มะม่วงฉันรู้ว่าโอ้จะเริ่มต้นด้วยม.
มันจะต้องเป็นที่ดัชนี 12
ฉันไม่ได้มีการค้นหาผ่านอะไร
ฉันรู้ว่า exactly-- ฉันสามารถไปที่ ดัชนี 12 และดึงออก
>> ทุกคนที่ชัดเจนเกี่ยวกับวิธีการที่ ฟังก์ชั่นของตารางแฮชทำงานอย่างไร
เป็นชนิดของเพียงอาร์เรย์ที่ซับซ้อนมากขึ้น
นั่นคือทั้งหมดที่มันเป็น
ตกลง.
>> ดังนั้นผมจึงคิดว่าเราทำงานเป็น ปัญหาของสิ่งนี้
เกิดขึ้นถ้าคุณมีสิ่งที่หลาย ๆ ที่ให้คุณดัชนีเดียวกันได้หรือไม่
เพื่อบอกว่าฟังก์ชั่นของเราทั้งหมดก็ ไม่ได้ใช้เวลาที่ตัวอักษรตัวแรก
และเปิดที่เป็น ที่เกี่ยวข้อง 0 ถึง 25 ดัชนี
นั่นคือทั้งหมดที่ดีถ้า คุณมีเพียงหนึ่งของแต่ละ
แต่ที่สองคุณเริ่มต้น มีมากขึ้นคุณ
จะมีสิ่งที่เรียกว่าการปะทะกัน
>> ดังนั้นถ้าผมพยายามที่จะแทรกเข้าไปฝังกัญชา ตารางที่มีอยู่แล้วกล้วยกับมัน
สิ่งที่จะเกิดขึ้นเมื่อ คุณพยายามที่จะแทรกที่?
สิ่งที่ไม่ดีเพราะกล้วย ที่มีอยู่แล้วภายในดัชนี
ที่คุณต้องการเก็บไว้ใน
ชนิดของแบล็กเบอร์เป็นเหมือน ah, สิ่งที่ฉันจะทำอย่างไร
ผมไม่ทราบว่าจะไปที่ไหน
ฉันจะแก้ปัญหานี้ได้อย่างไร?
>> และเพื่อให้พวกคุณจะชนิดของ เห็นว่าเราทำเช่นนี้สิ่งที่ยุ่งยาก
ที่เราสามารถชนิดของจริง สร้างรายการเชื่อมโยงในอาร์เรย์ของเรา
ดังนั้นวิธีที่ง่ายที่สุด ที่จะคิดเกี่ยวกับเรื่องนี้
ตารางแฮชทั้งหมดเป็น อาร์เรย์ของรายการที่เชื่อมโยง
และอื่น ๆ ในความรู้สึกที่คุณมี นี้อาร์เรย์ที่สวยงามของตัวชี้
และจากนั้นในแต่ละตัวชี้ ค่าที่อยู่ในดัชนีที่
จริงสามารถชี้ไปที่สิ่งอื่น ๆ
และเพื่อให้คุณมีทั้งหมดเหล่านี้แยกต่างหาก โซ่ออกมาจากอาเรย์ขนาดใหญ่
>> และอื่น ๆ ที่นี่ถ้าฉัน อยากจะใส่เบอร์รี่,
ฉันรู้ว่าตกลงฉันจะป้อนข้อมูล มันผ่านฟังก์ชันแฮชของฉัน
ฉันจะจบลงด้วยดัชนีของ 1 แล้วฉันจะสามารถที่จะมี
เพียงส่วนย่อยที่มีขนาดเล็กนี้ ยักษ์ 140,000 คำพจนานุกรม
แล้วฉันก็สามารถมอง ผ่าน 1/26 ที่
>> และอื่น ๆ แล้วฉันก็สามารถแทรก แบล็กเบอร์ก่อนหรือหลังกล้วย
ในกรณีนี้?
หลังจากใช่มั้ย?
และเพื่อให้คุณจะต้องการที่จะ แทรกโหนดนี้หลังจากที่กล้วย
และเพื่อให้คุณกำลังจะแทรก ที่หางของรายการที่เชื่อมโยงว่า
ฉันจะกลับไป ไปยังภาพนิ่งก่อนหน้านี้
เพื่อที่พวกคุณจะได้เห็นว่า งานฟังก์ชันแฮช
>> ดังนั้นฟังก์ชันแฮชเป็นสมการนี​​้ ว่าคุณกำลังใช้ชนิดของการป้อนข้อมูลของคุณ
ผ่านทางที่จะได้รับสิ่งที่ดัชนี คุณต้องการที่จะกำหนดต่อ
ดังนั้นในตัวอย่างนี้ทั้งหมดที่เราต้องการ จะทำคือใช้ตัวอักษรตัวแรก,
เปิดที่เป็นดัชนีแล้วเรา สามารถจัดเก็บว่าในฟังก์ชันแฮชของเรา
ทั้งหมดที่เรากำลังทำอะไรที่นี่คือเรา แปลงตัวอักษรตัวแรก
KeyKey ดังนั้น [0] เป็นเพียงตัวอักษรตัวแรก ของสตริงสิ่งที่เรากำลังมี,
เรากำลังผ่านใน
เรากำลังแปลงที่บนและ เรากำลังลบโดยพิมพ์ใหญ่ A,
ดังนั้นสิ่งที่จะทำ จะให้เราเป็นจำนวนมาก
ที่เราสามารถสับลงบนค่านิยมของเรา
>> และจากนั้นเรากำลังจะไป โมดูลัสกลับขนาดกัญชา
จะมากระวังให้มาก เพราะเหตุผลที่นี่
ค่าแฮชของคุณอาจจะไม่มีที่สิ้นสุด
มันก็สามารถไปบนและบนและบน
มันอาจจะมีบางจริงๆ ค่าขนาดใหญ่จริงๆ
แต่เป็นเพราะตารางแฮชคุณที่ คุณได้สร้างมีเพียง 26 ดัชนี
คุณต้องการที่จะให้แน่ใจว่าคุณ modulusing เพื่อให้คุณ
ไม่ run-- ก็เหมือนกัน สิ่งที่เป็นของคุณ queue--
เพื่อที่คุณจะไม่ทำงานออก ด้านล่างของฟังก์ชันแฮชของคุณ
>> คุณต้องการที่จะตัดกลับไปรอบ ๆ วิธีเดียวกันใน [ไม่ได้ยิน] เมื่อ
คุณมีเหมือนมาก ตัวอักษรที่มีขนาดใหญ่มากคุณ
ไม่ได้ต้องการที่ เพียงแค่เรียกใช้ปิดท้าย
สิ่งเดียวกันที่นี่คุณต้องการให้แน่ใจว่า จะไม่ทำงานออกจากปลายโดยตัด
รอบด้านบนของตาราง
ดังนั้นนี่เป็นเพียงมาก ฟังก์ชันแฮชที่เรียบง่าย
สิ่งที่ไม่ได้ใช้เป็นครั้งแรก สิ่งที่ตัวอักษรของการป้อนข้อมูลของเราคือ
และเปิดที่เป็นดัชนีที่ เราสามารถใส่ลงไปในตารางแฮชของเรา
>> ใช่และอื่น ๆ ที่ผมกล่าวมาก่อน วิธีการที่เราแก้ปัญหาการชนกัน
ในตารางแฮชของเรามี, สิ่งที่เราเรียกผูกมัด
ดังนั้นถ้าคุณพยายามที่จะแทรกหลาย คำที่ขึ้นต้นด้วยสิ่งเดียวกัน
คุณกำลังจะมีค่าแฮหนึ่ง
อะโวคาโดและแอปเปิ้ลถ้าคุณได้ เรียกใช้ผ่านฟังก์ชันแฮชของเรา
จะไปให้คุณ หมายเลขเดียวกันจำนวน 0
ดังนั้นวิธีการที่เราแก้ปัญหาที่เป็น ที่เราสามารถจริงชนิดของการเชื่อมโยงพวกเขา
ร่วมกันผ่านทางรายการที่เชื่อมโยง
>> และในแง่นี้ พวกคุณสามารถดูชนิด
ของวิธีการที่โครงสร้างข้อมูล เราได้รับการตั้งค่าก่อนหน้านี้
เช่นเดียวกับชนิดรายการลูกเกดเชื่อมโยง ของสามารถมาร่วมกันเป็นหนึ่ง
และจากนั้นคุณสามารถสร้างให้ห่างไกล โครงสร้างข้อมูลที่มีประสิทธิภาพมากขึ้น
ที่สามารถจัดการกับจำนวนเงินขนาดใหญ่ของ ข้อมูลแบบไดนามิกที่ปรับขนาดขึ้นอยู่กับ
ความต้องการของคุณ
ทุกคนชัดเจน?
ชนิดของทุกคนที่ชัดเจน กับสิ่งที่เกิดขึ้นที่นี่?
>> ถ้าผมอยากจะ insert-- สิ่งที่เป็น ผลไม้ที่เริ่มต้นด้วยผมไม่ทราบว่า
B, อื่น ๆ นอกเหนือจากเบอร์รี่กล้วย
>> ผู้ชม: Blackberry
>> ANDI PENG: BlackBerry, ผลไม้ชนิดหนึ่ง
ผลไม้ชนิดไหนไปที่นี่?
ดีเราจริงไม่ได้เรียง นี้ แต่ในทางทฤษฎี
ถ้าเราต้องการที่จะมีนี้ ตามลำดับตัวอักษร
ผลไม้ชนิดหนึ่งที่ควรจะไป?
>> ผู้ชม: [ไม่ได้ยิน]
>> ANDI PENG: ว่าหลังจากที่นี่ใช่มั้ย?
แต่เนื่องจากมันเป็นเรื่องยากมากที่จะ reorder-- ผมคิดว่ามันขึ้นอยู่กับพวกคุณ
พวกคุณทั้งหมดสามารถ ใช้สิ่งที่คุณต้องการ
วิธีที่มีประสิทธิภาพมากขึ้น การทำเช่นนี้อาจจะเป็น
จะมีการจัดเรียงที่เชื่อมโยง รายการลงในลำดับตัวอักษร
และอื่น ๆ เมื่อคุณอยู่ ใส่สิ่งที่คุณต้องการ
เพื่อให้แน่ใจว่าพวกเขาจะแทรก เข้ามาตามลำดับตัวอักษร
เพื่อที่ว่าเมื่อคุณ พยายามที่จะค้นหาพวกเขา
คุณไม่ได้มีการสำรวจทุกอย่าง
คุณจะรู้ว่าที่ มันเป็นและมันง่าย
>> แต่ถ้าคุณมีชนิดของ สิ่งที่สลับแบบสุ่ม
คุณยังจะมี เพื่อสำรวจมันนะ
ดังนั้นถ้าผมต้องการที่จะเพียงแค่ ใส่ผลไม้ชนิดหนึ่งที่นี่
และฉันต้องการที่จะค้นหา มันฉันรู้ว่าโอ้, BlackBerry
ต้องเริ่มต้นด้วยดัชนีของ 1 ดังนั้นฉัน รู้ทันทีเพียงค้นหาวันที่ 1
แล้วฉันสามารถชนิดของ สำรวจรายการที่เชื่อมโยง
จนได้รับการ Blackberry, และ then-- ใช่?
>> ผู้ชม: ถ้าคุณกำลังพยายามที่จะ create-- ผมคิดเช่นนี้เป็นกัญชาที่ง่ายมาก
ฟังก์ชัน
และถ้าเราอยากจะทำ หลายชั้นเช่นนั้น
ตกลงเราต้องการที่จะแยกออกเป็น เช่นเดียวกับตัวอักษรที่เรียงตามตัวอักษร
และหลังจากนั้นอีกจะชอบอีกชุดหนึ่ง เรียงตามตัวอักษรของตัวอักษรที่อยู่ในนั้น
เราจะวางเช่นกัญชา ตารางในตารางแฮช
หรือชอบฟังก์ชั่นภายในฟังก์ชั่นหรือไม่?
หรือ that--
>> ANDI PENG: ดังนั้นกัญชาของคุณ function-- ตารางแฮชของคุณ
อาจมีขนาดใหญ่ที่สุดเท่าที่คุณต้องการให้
ดังนั้นในแง่นี้ผมคิดว่า มันเป็นเรื่องง่ายมาก
ง่ายสำหรับผมที่จะเพียงแค่การจัดเรียงตาม เกี่ยวกับตัวอักษรของคำแรก
และเพื่อให้มีเพียง 26 ตัวเลือก
ฉันเท่านั้นที่จะได้รับเลือกจาก 26 0-25 เพราะพวกเขาสามารถ
เริ่มต้นจาก A ถึง Z แต่ถ้าคุณต้องการ เพื่อเพิ่มอาจจะซับซ้อนมากขึ้น
หรือทำงานได้เร็วขึ้นเวลาที่จะของคุณ ตารางแฮชคุณอย่าง
สามารถทำทุกประเภทของสิ่ง
คุณสามารถทำด้วยตัวเอง สมการที่ช่วยให้คุณ
มากขึ้นในการจัดจำหน่ายของคุณ คำแล้วเมื่อคุณค้นหา
มันเป็นไปได้เร็วขึ้น
>> มันทั้งหมดขึ้นอยู่กับพวกคุณ วิธีที่คุณต้องการที่จะดำเนินการที่
คิดว่ามันเป็นเพียงแค่ถัง
ถ้าผมต้องการที่จะมี 26 ถัง, ฉันจะ
การเรียงลำดับสิ่งที่เป็นถังเหล่านั้น
แต่ฉันจะมีพวง ของสิ่งที่อยู่ในแต่ละถัง
ดังนั้นหากคุณต้องการที่จะให้มัน ได้เร็วขึ้นและมีประสิทธิภาพมากขึ้น
ให้ฉันมีร้อยถัง
>> แต่แล้วคุณจะต้องคิดออก วิธีการเรียงลำดับสิ่งที่เพื่อให้พวกเขา
ในถังที่เหมาะสมที่พวกเขาควรจะอยู่ใน
แต่แล้วเมื่อคุณจริง ต้องการดูที่ถังนั้น
มันเร็วมากเพราะมี สิ่งที่น้อยกว่าในถังแต่ละ
ดังนั้นใช่ว่าเป็นจริง เคล็ดลับสำหรับคุณผู้ชายใน pset5
คือการที่คุณจะ ความท้าทายที่จะเพียงแค่สร้าง
สิ่งที่มีประสิทธิภาพมากที่สุด ฟังก์ชั่นที่คุณสามารถคิดที่จะเป็น
สามารถจัดเก็บและตรวจสอบค่าเหล่านี้
>> ทั้งหมดขึ้นอยู่กับพวกคุณ แต่คุณต้องการที่จะทำมัน
แต่ที่เป็นจุดที่ดีจริงๆ
ชนิดของตรรกะที่คุณ ต้องการที่จะเริ่มคิดเกี่ยวกับ
คือดีว่าทำไมฉันจึงไม่ทำให้ถังมากขึ้น
แล้วฉันต้องค้นหา สิ่งที่น้อยแล้วบางทีฉัน
มีฟังก์ชั่นที่แตกต่างกันกัญชา
>> ใช่มีหลายวิธีที่จะทำเช่นนี้ pset บางเร็วกว่าคนอื่น
ฉันจะไปทั้งหมดเพียงแค่ดูว่า ได้อย่างรวดเร็วเป็นที่เร็วที่สุดที่พวกคุณจะ
จะสามารถที่จะได้รับฟังก์ชั่นการทำงานของคุณ
ตกลงทุกคนที่ดีใน ผูกมัดและตารางแฮช?
เป็นจริงเหมือนที่ง่ายมาก แนวคิดถ้าคุณคิดเกี่ยวกับมัน
ทั้งหมดก็คือเป็นสิ่งที่แยก ปัจจัยการผลิตของคุณลงในถัง
การเรียงลำดับพวกเขาแล้วการค้นหา แสดงว่ามีการเชื่อมโยงกับ
>> เย็น.
สิทธิทั้งหมดตอนนี้เรามีการจัดเรียงที่แตกต่างกัน ของโครงสร้างข้อมูลที่เรียกว่าต้นไม้
ลองไปและพยายามพูดคุยเกี่ยวกับ ซึ่งจะแตกต่างกันอย่างเห็นได้ชัด
แต่ในประเภทเดียวกัน
โดยพื้นฐานแล้วทุกต้นไม้แทน ในการจัดระเบียบข้อมูลในวิธีการเชิงเส้น
ว่าตารางแฮช does-- คุณ รู้ว่ามันมีด้านบนและด้านล่าง
และจากนั้นคุณชนิดของการเชื่อมโยงออกจาก it-- ต้นไม้ที่มีด้านบนที่คุณเรียกราก
และจากนั้นก็มีการออกรอบ ๆ ตัวมัน
>> และดังนั้นสิ่งที่คุณได้ที่นี่ เป็นเพียงโหนดบน
ที่ชี้ไปยังโหนดอื่น ๆ ที่จุด ไปยังต่อมน้ำมากขึ้นและอื่น ๆ และอื่น ๆ
และเพื่อให้คุณเพียงแค่มีสาขาแยก
มันเป็นเพียงวิธีที่แตกต่างในการจัดระเบียบ ข้อมูลและเพราะเราเรียกมันว่าต้นไม้
พวกคุณ just-- มันเป็นเพียงแค่ รูปแบบออกมาให้มีลักษณะเหมือนต้นไม้
นั่นเป็นเหตุผลที่เราเรียกมันว่าต้นไม้
>> ตารางแฮชดูเหมือนตาราง
ต้นไม้ก็ดูเหมือนต้นไม้
ทั้งหมดก็คือเป็นที่แยกต่างหาก วิธีการจัดระเบียบของโหนด
ขึ้นอยู่กับความต้องการของคุณ
>> เพื่อให้คุณมีรากและ แล้วคุณมีใบ
วิธีการที่เราสามารถทำได้โดยเฉพาะอย่างยิ่ง คิดเกี่ยวกับมันเป็นต้นไม้ไบนารี
ต้นไม้ไบนารีเป็นเพียง ประเภทที่เฉพาะเจาะจงของต้นไม้
ซึ่งแต่ละโหนดจุดเท่านั้น ไปที่สูงสุดสองโหนดอื่น ๆ
และเพื่อให้ที่นี่คุณมีที่แตกต่างกัน สมมาตรในต้นไม้ของคุณ
ที่ทำให้ง่ายต่อการดูชนิดของ สิ่งที่มีค่าที่คุณอยู่แล้วเพราะคุณ
มีเสมอทางซ้ายหรือขวา
มีไม่เหมือนคนที่สามจากซ้าย ซ้ายหรือสี่จากซ้าย
มันเป็นเพียงแค่คุณมีด้านซ้ายและขวา และคุณสามารถค้นหาได้ทั้งของทั้งสอง
และเพื่อเหตุผลนี้เป็นประโยชน์หรือไม่
วิธีที่ว่านี้คือ ประโยชน์คือถ้าคุณกำลังมองหา
การค้นหาผ่านค่าใช่มั้ย?
แทนที่จะดำเนินการไบนารี ค้นหาในอาร์เรย์ข้อผิดพลาด
ถ้าคุณต้องการที่จะสามารถที่จะแทรกโหนด และนำไปโหนดที่จะและยัง
รักษาค้นหา ขีดความสามารถของการค้นหาแบบไบนารี
ดังนั้นในทางนี้เรากำลังชนิดของ tricking-- จำได้ว่าเมื่อเรา
กล่าวว่ารายการที่เชื่อมโยงไม่สามารถค้นหา binary?
เรากำลังชนิดของการสร้างโครงสร้างข้อมูล ว่าเทคนิคที่เข้าทำงาน
>> และอื่น ๆ เพราะรายการที่เชื่อมโยงเป็นเชิงเส้น พวกเขาเชื่อมโยงเพียงหนึ่งหลังจากที่อื่น ๆ
เราสามารถมีชนิดของ การจัดเรียงที่แตกต่างกันของตัวชี้
ชี้ไปที่โหนดที่แตกต่างกัน ที่สามารถช่วยให้เรามีการค้นหา
และอื่น ๆ ที่นี่ถ้าผมต้องการที่จะ มีต้นไม้ค้นหาไบนารี
ฉันรู้ว่าฉันถ้ากลาง 55
ฉันแค่จะสร้างที่ เป็นกลางของฉันเป็นรากของฉัน
แล้วฉันจะมี ค่าสปินออกจากมัน
>> ดังนั้นที่นี่ถ้าฉันจะค้นหา ค่าของ 66 ผมสามารถเริ่มต้นที่ 55
มันเป็น 66 มากกว่า 55?
ใช่มันเป็นดังนั้นฉันรู้ว่าฉัน mus ค้นหา ฉัน n ตัวชี้ขวาของต้นไม้ต้นนี้
ฉันไปที่ 77
ตกลง 66 น้อยกว่าหรือมากกว่า 77?
มันน้อยกว่าเพื่อให้คุณรู้ว่าโอ้ ที่จะต้องมีโหนดซ้าย
>> และอื่น ๆ ที่นี่เรากำลังชนิดของการรักษา ทุกสิ่งที่ดีเกี่ยวกับอาร์เรย์
เพื่อต้องการปรับขนาดแบบไดนามิก ของวัตถุที่เป็น
สามารถแทรกและลบที่จะ, โดยไม่ต้องกังวลเกี่ยวกับการคงที่
จำนวนของพื้นที่
เรายังคงรักษาทั้งหมดของ บรรดาสิ่งที่ยอดเยี่ยม
ในขณะที่ยังมีความสามารถในการรักษา เข้าสู่ระบบและค้นหาเวลาของการค้นหาแบบทวิภาค
ว่าเราเป็นเพียงก่อนหน้านี้ สามารถที่จะได้รับวลี
>> โครงสร้างข้อมูลเย็นชนิดของ ที่ซับซ้อนในการใช้โหนด
ที่คุณสามารถดูทั้งหมดก็ เป็นโครงสร้างของโหนด
คือการที่คุณมีซ้าย และตัวชี้ด้านขวา
นั่นคือทั้งหมดที่มันเป็น
ดังนั้นแทนที่จะเป็นเพียง มี x หรือก่อนหน้า
คุณมีทางซ้ายหรือขวาแล้ว ชนิดที่คุณสามารถเชื่อมโยงเข้าด้วยกัน
แต่คุณจึงเลือก
>> ตกลงเรากำลังจะเป็นจริง เพียงแค่ใช้เวลาไม่กี่นาที
ดังนั้นเรากำลังจะไปกลับมาที่นี่
ที่ผมกล่าวว่าก่อนหน้านี้ ชนิดของฉันอธิบาย
ตรรกะที่อยู่เบื้องหลังวิธีการที่เรา จะค้นหาผ่านทางนี้
เรากำลังจะไปลอง pseudocoding นี้ออกเพื่อดู
ถ้าเราชนิดสามารถใช้ ตรรกะเดียวกันของการค้นหาแบบไบนารี
จะเป็นชนิดที่แตกต่างกันของโครงสร้างข้อมูล
ถ้าพวกคุณต้องการที่จะใช้เช่นคู่ นาทีที่จะเพียงแค่คิดเกี่ยวกับเรื่องนี้
ตกลง.
สิทธิทั้งหมดที่ฉันจะ จริงเพียงแค่ให้คุณ the-- ไม่มี
เราจะพูดคุยเกี่ยวกับ pseudocode แรก
ดังนั้นไม่มีใครต้องการ เพื่อให้แทงที่สิ่งที่
สิ่งแรกที่คุณต้องการจะทำอย่างไรเมื่อ คุณกำลังเริ่มออกค้นหาคืออะไร?
หากเรากำลังมองหา ค่าของ 66 สิ่งที่
สิ่งแรกที่เราต้องการจะทำอย่างไรถ้า เราต้องการที่จะค้นหาต้นไม้ไบนารีนี้หรือไม่?
>> ผู้ชม: คุณต้องการที่จะมองขวา และมองซ้ายและดู [ไม่ได้ยิน]
จำนวนมาก
>> ANDI เป็ง: ใช่ว่า
ดังนั้นคุณจะไปดูที่รากของคุณ
มีหลายวิธีที่คุณสามารถเรียกเป็น มันผู้ปกครองคนโหนดของคุณบอกว่า
ผมชอบที่จะพูดเพราะราก ที่เหมือนรากของต้นไม้
คุณกำลังจะไปดูที่ โหนดรากของคุณและคุณ
จะไปดู 66 มากขึ้น มากกว่าหรือน้อยกว่า 55
และถ้ามันมากกว่าดีก็คือ มากกว่าที่เราจะต้องการที่จะมอง?
ในกรณีที่เราต้องการค้นหาตอนนี้ใช่มั้ย?
เราต้องการที่จะค้นหา ครึ่งขวาของต้นไม้ต้นนี้
>> ดังนั้นเราจึงมีสิ่งอำนวยความสะดวกที่ ชี้ที่ชี้ไปทางขวา
และอื่น ๆ แล้วเราสามารถตั้งค่า รากใหม่ของเราจะเป็น 77
เราก็สามารถไปได้ทุกที่ ตัวชี้ชี้
ดีโอ้นี่เรากำลังเริ่มต้น ที่ 77 และเราก็สามารถ
ทำเช่นนี้ซ้ำอีกครั้งและอีกครั้ง
ด้วยวิธีนี้คุณชนิด ของมีฟังก์ชั่น
คุณมีวิธีการค้นหาที่คุณ ก็สามารถทำซ้ำมากกว่าและเหนือและมากกว่า
ขึ้นอยู่กับที่คุณต้องการดู จนกว่าคุณจะได้รับในที่สุดค่า
ที่คุณกำลังค้นหา
ความรู้สึกให้?
>> ฉันจะแสดงให้คุณเห็นที่เกิดขึ้นจริง รหัสและก็มากรหัส
ไม่จำเป็นต้องออกนอกลู่นอกทาง
เราจะพูดคุยผ่านมัน
>> อันที่จริงไม่มี
ที่เป็นเพียง pseudocode
ตกลงที่เป็นเพียง pseudocode ที่ ซึ่งมีความซับซ้อนเล็กน้อย
แต่มันเป็นเรื่องที่ดีโดยสิ้นเชิง
ทุกคนไปพร้อมที่นี่?
หากรากเป็นโมฆะกลับ เท็จเพราะหมายความว่า
คุณไม่ได้มีอะไรที่มี
>> ถ้า n รากเป็นค่าดังนั้นถ้ามัน เกิดขึ้นเป็นหนึ่งที่คุณกำลังมองหาที่
แล้วคุณจะกลับจริง เพราะคุณรู้ว่าคุณจะพบว่า
แต่ถ้าค่าน้อย กว่ารากของ n คุณ
จะค้นหาทางด้านซ้าย เด็กหรือใบซ้าย
สิ่งที่คุณต้องการที่จะเรียกว่า
และถ้ามีค่าเป็นมากกว่าราก คุณกำลังจะไปค้นหาต้นไม้ที่ถูกต้อง
จากนั้นเพียงแค่ใช้ฟังก์ชั่น ผ่านการค้นหาอีกครั้ง
>> และถ้ารากเป็นโมฆะว่า หมายความว่าคุณได้มาถึงจุดสิ้นสุดหรือไม่
ซึ่งหมายความว่าคุณไม่มี ใบมากขึ้นมากขึ้นในการค้นหา
แล้วคุณจะรู้ว่าโอ้ฉัน คิดว่ามันไม่ได้อยู่ในที่นี่
เพราะหลังจากที่ฉันมองผ่าน สิ่งที่ทั้งและก็ไม่อยู่ที่นี่
มันก็อาจจะไม่ได้ที่นี่
>> ไม่ว่าทำให้ความรู้สึกที่ทุกคน?
ดังนั้นมันก็เหมือนการค้นหาแบบไบนารีรักษา ความสามารถของรายการที่เชื่อมโยง
เย็นและอื่น ๆ ประเภทที่สอง โครงสร้างข้อมูลของพวกคุณ
สามารถลองการดำเนินการใน pset ของคุณ คุณจะต้องเลือกวิธีการอย่างใดอย่างหนึ่ง
แต่บางทีอาจจะเป็นวิธีทางเลือกที่จะ ตารางแฮชคือสิ่งที่เราเรียก Trie
>> ทั้งหมดเป็น Trie เป็น ประเภทเฉพาะของต้นไม้ที่
มีค่าที่ไปค่าอื่น ๆ
ดังนั้นแทนที่จะมีไบนารี ต้นไม้ในแง่ที่ว่ามีเพียงหนึ่ง
สิ่งที่สามารถชี้ไปที่สองคุณสามารถมี จุดสิ่งหนึ่งที่หลายหลายสิ่งหลายอย่าง
คุณเป็นหลักมีอาร์เรย์ ด้านในของที่คุณเก็บ
ชี้ที่ชี้ไปยังอาร์เรย์อื่น ๆ
>> ดังนั้นโหนดของวิธีการที่พวกเราทุกคน จะกำหนด Trie
คือเราต้องการที่จะมี บูลีนคำคใช่มั้ย?
ดังนั้นโหนดเป็นแบบบูล เหมือนจริงหรือเท็จ
ครั้งแรกของทั้งหมดที่หัวของ อาร์เรย์ที่นี้เป็นคำ?
ประการที่สองคุณต้องการที่จะมีคำแนะนำ สิ่งที่เหลือของพวกเขา
ซับซ้อนบิตนามธรรมเล็กน้อย แต่ ผมจะอธิบายสิ่งที่หมายถึงทั้งหมด
>> ดังนั้นที่นี่ที่ด้านบนถ้าคุณ มีอาร์เรย์ประกาศแล้ว
โหนดที่คุณต้องบูล ค่าที่เก็บไว้ที่ด้านหน้า
ที่จะบอกคุณคือคำ?
นี้ไม่ได้เป็นคำ?
แล้วคุณมี ส่วนที่เหลือของอาเรย์ที่
เก็บจริงทั้งหมด ความเป็นไปได้ของสิ่งที่มันอาจจะเป็น
ดังนั้นสำหรับตัวอย่างเช่น ที่ด้านบนที่คุณมี
สิ่งแรกที่บอกว่าจริงหรือ เท็จใช่หรือไม่นี่คือคำ
>> แล้วคุณมี 0 ถึง 26 ตัวอักษรที่คุณสามารถจัดเก็บ
ถ้าผมต้องการที่จะค้นหาที่นี่ สำหรับค้างคาวผมไปด้านบน
และฉันมองหาฉันพบบีบีของฉัน อาร์เรย์และเพื่อให้ฉันรู้ว่าตกลงเป็น B คำ?
B เป็นคำไม่ได้ดังนั้นจึง ฉันต้องเก็บการค้นหา
ฉันไปจาก B และผมมองไปที่ ชี้ที่ชี้ไปทาง B
และฉันเห็นอาร์เรย์ของข้อมูลอื่น โครงสร้างเดียวกับที่เราเคยมีมาก่อน
>> และ here-- โอ้ต่อไป จดหมาย [ไม่ได้ยิน] เป็นเอ
ดังนั้นเรามองว่าในอาร์เรย์
เราหาค่าที่แปด และจากนั้นเราดูเพื่อดูโอ้
เดี๋ยวก่อนคือคำที่เป็น B-A คำ?
มันไม่ได้เป็นคำ
เราได้มีการให้มอง
>> และอื่น ๆ แล้วเรามองไปที่ ตัวชี้ของจุดที่
และชี้ไปทางอื่น ที่เราได้มูลค่ามากขึ้นเก็บไว้
และในที่สุดเราได้รับ B-A-T ซึ่งเป็นคำ
ดังนั้นในครั้งต่อไป คุณมองไปที่คุณกำลังจะ
ที่จะมีการตรวจสอบของใช่ที่ ฟังก์ชั่นบูลีนนี้เป็นความจริง
และอื่น ๆ ในความรู้สึกเราชนิด ของการมีต้นไม้ที่มีอาร์เรย์
>> ดังนั้นแล้วคุณสามารถค้นหาชนิดของลง
แทนที่จะ hashing ฟังก์ชั่นและ การกำหนดค่าตามรายการที่เชื่อมโยง
คุณก็สามารถใช้ Trie ที่ค้นหา downwords
จริงๆสิ่งที่ซับซ้อนมาก
ไม่ง่ายที่จะคิดเกี่ยวกับเพราะฉันชอบ คายโครงสร้างข้อมูลจำนวนมากออก
ที่คุณ แต่ไม่ทุกคนชนิดของ เข้าใจว่าตรรกะนี้ทำงานอย่างไร
>> ตกลงเย็น
ดังนั้น B-A-T แล้ว คุณกำลังจะค้นหา
ครั้งต่อไปที่คุณจะ เพื่อดูโอ้เดี๋ยวก่อนมันเป็นความจริง
ทำให้ฉันรู้ว่านี้จะต้องเป็นคำ
>> สิ่งที่เหมือนกันสำหรับสวนสัตว์
ดังนั้นนี่คือสิ่งที่ตอนนี้ถ้าเรา ต้องการที่จะค้นหาสวนสัตว์ตอนนี้
สวนสัตว์ในปัจจุบันไม่ได้เป็น คำในพจนานุกรมของเรา
เพราะในขณะที่พวกคุณสามารถดูที่ สถานที่แรกที่เรามีแบบบูล
กลับจริงคือในตอนท้ายของการซูม
เรามี Z-O-O-M
>> และอื่น ๆ ที่นี่เราไม่จริงมี คำว่าสวนสัตว์ในพจนานุกรมของเรา
เพราะช่องนี้ไม่ได้ตรวจสอบ
เพื่อให้คอมพิวเตอร์ไม่ได้ รู้ว่าสวนสัตว์เป็นคำ
เพราะวิธีการที่เราได้ เก็บไว้เพียงซูมที่นี่
จริงมีค่าบูลีน ที่ได้รับการเปิดจริง
ดังนั้นถ้าเราต้องการที่จะใส่ คำว่าสวนสัตว์ลงไปในพจนานุกรมของเรา
วิธีการที่เราจะไปเกี่ยวกับการทำเช่นนั้น?
เราจะต้องทำอะไรเพื่อให้แน่ใจว่าเรา คอมพิวเตอร์รู้ว่า Z-O-O เป็นคำ
และไม่ได้เป็นคำแรกคือ Z-O-O-M?
>> ผู้ชม: [ไม่ได้ยิน]
>> ANDI PENG: แน่นอนเรา ต้องการให้แน่ใจว่านี้
ที่นี่ที่ค่าบูลีนเป็น การตรวจสอบออกว่ามันเป็นความจริง
Z-O-O แล้วเรากำลังจะไปตรวจสอบว่า เพื่อให้เรารู้ว่าเดี๋ยวก่อนสวนสัตว์เป็นคำ
ฉันจะบอก คอมพิวเตอร์ว่ามันเป็นคำพูดเพื่อให้
ว่าเมื่อตรวจสอบคอมพิวเตอร์ มันรู้ว่าสวนสัตว์เป็นคำ
>> เพราะจำได้ว่าข้อมูลทั้งหมดเหล่านี้ โครงสร้างมันเป็นเรื่องง่ายมากสำหรับเรา
ที่จะบอกว่าโอ้ค้างคาวเป็นคำ
สวนสัตว์เป็นคำ
ซูมเป็นคำ
แต่เมื่อคุณกำลังสร้างมัน คอมพิวเตอร์มีความคิด
>> ดังนั้นคุณต้องบอกว่า สิ่งที่จุดนี้คือคำ?
สิ่งที่จุดที่มันไม่ได้คำ?
และสิ่งที่จุดที่ฉัน ต้องค้นหาสิ่งที่
และสิ่งที่จุดที่ฉันจะต้องไปต่อไปหรือไม่
ทุกคนที่ชัดเจนว่า?
เย็น.
>> และเป็นอย่างนั้นมา ปัญหาของการที่เราจะ
ไปเกี่ยวกับการใส่บางสิ่งบางอย่าง ที่จริงไม่ได้มี?
ถ้าอย่างนั้นเราก็บอกว่าเราต้องการที่จะใส่ คำอาบน้ำลงไปใน Trie ของเรา
ในฐานะที่เป็นคนที่คุณสามารถเห็นเหมือนในปัจจุบัน ทั้งหมดที่เรามีตอนนี้คือ B-A-T,
และโครงสร้างข้อมูลใหม่นี้ ได้มีไพน์ว่า
ชี้ไป null เพราะเราถือว่า ว่าโอ้มีคำหลังจาก B-A-T,
ทำไมเราต้องให้ มีสิ่งทีหลังจากที่
>> แต่ปัญหาที่เกิดขึ้นถ้าเราทำคุณ ต้องการที่จะมีคำที่มาหลังจากที่
เสื้อของ
หากคุณมีห้องอาบน้ำที่คุณ จะต้องการสิทธิ H
ดังนั้นวิธีที่เรากำลังจะทำว่าเป็น เรากำลังจะสร้างโหนดแยกต่างหาก
เราไม่ได้จัดสรรจำนวนเงินใด ๆ ก็ตาม ของหน่วยความจำสำหรับอาร์เรย์ใหม่นี้
และเรากำลังจะกำหนดตัวชี้
>> เรากำลังจะไปกำหนด H, แรกของทั้งหมด null นี้
เรากำลังจะได้รับการกำจัด
เรากำลังจะมี จุด H ลง
ถ้าเราเห็น H, เราต้องการ ที่จะไปที่อื่น
>> ในที่นี่เราก็จะสามารถตรวจสอบการปิดใช่
ถ้าเราตีหลังจากที่เอชทีโอ้ แล้วเรารู้ว่านี่คือคำ
บูลีนเป็นไปเพื่อกลับจริง
ทุกคนที่ชัดเจนเกี่ยวกับวิธีการที่เกิดขึ้น?
ตกลง.
>> เพื่อเป็นหลักทั้งหมด เหล่านี้โครงสร้างข้อมูล
ที่เราได้ไปกว่าวันนี้ผมได้ ไปเหนือพวกเขาจริงๆได้อย่างรวดเร็ว
และไม่อยู่ในมาก รายละเอียดและที่ตกลง
เมื่อคุณเริ่ม messing กับมันคุณจะ
การติดตามที่ ชี้ทั้งหมดที่มี
สิ่งที่เกิดขึ้นในของคุณ โครงสร้างข้อมูลและอื่น ๆ
พวกเขาจะมีประโยชน์มาก และมันก็ขึ้นอยู่กับคุณ
คนที่จะคิดออกว่าทั้งหมด คุณต้องการที่จะใช้สิ่งที่
>> และเพื่อให้ pset4 ของ 5-- โอ้ว่าเป็นสิ่งที่ผิด
Pset5 เป็นคำที่สะกดผิด
ที่ผมกล่าวว่าก่อนที่คุณจะไปครั้งเดียว อีกครั้งดาวน์โหลดซอร์สโค้ดจากเรา
มีจะมีสามหลัก สิ่งที่คุณจะได้รับการดาวน์โหลด
คุณจะดาวน์โหลดพจนานุกรม KERS และตำรา
>> ทุกสิ่งเหล่านี้จะเป็น ทั้งพจนานุกรมของคำ
ที่เราต้องการให้คุณตรวจสอบ หรือการทดสอบของข้อมูล
ที่เราต้องการให้คุณตรวจสอบการสะกด
และเพื่อพจนานุกรม เราให้คุณจะ
เพื่อให้คุณมีคำพูดที่เกิดขึ้นจริงที่เราต้องการ คุณสามารถจัดเก็บอย่างใดในทางที่เป็น
มีประสิทธิภาพมากขึ้นกว่าอาร์เรย์
และจากนั้นจะมีข้อความ จะเป็นสิ่งที่เรากำลัง
ขอให้คุณตรวจสอบการสะกดเพื่อให้แน่ใจว่า ทุกคำที่มีคำพูดจริง
>> และเพื่อให้สามช่วงตึกของ โปรแกรมที่เราจะให้คุณ
จะเรียกว่า dictionary.c, dictionary.h และ speller.c
และเพื่อ dictionary.c ทั้งหมดไม่เป็น สิ่งที่คุณกำลังขอให้ดำเนินการ
โหลดคำ
มันสะกดตรวจสอบพวกเขาและมันจะทำให้แน่ใจว่า ทุกอย่างที่ใส่อย่างถูกต้อง
>> diction.h เป็นเพียงไฟล์ไลบรารี ฟังก์ชั่นที่บอกทุกคน
และ speller.c เรากำลังจะให้คุณ
คุณไม่จำเป็นต้องปรับเปลี่ยนใด ๆ ของมัน
speller.c ทั้งหมดไม่สามารถใช้เวลาที่ โหลดมันจะตรวจสอบความเร็วของมัน
การทดสอบมาตรฐานเช่นวิธีการที่ ได้อย่างรวดเร็วคุณสามารถที่จะทำในสิ่งที่
>> มันสะกด
เพียงแค่จะไม่ยุ่งกับมัน แต่ให้ แน่ใจว่าคุณเข้าใจสิ่งที่มันทำ
เราใช้ฟังก์ชั่นที่เรียกว่า getrusage ว่า การทดสอบประสิทธิภาพของการสะกดคำของคุณ
ตรวจสอบ
ทั้งหมดก็จะเป็นพื้นทดสอบ ช่วงเวลาของทุกอย่างในพจนานุกรมของคุณ
เพื่อให้แน่ใจว่าคุณเข้าใจมัน
โปรดใช้ความระมัดระวังที่จะไม่ยุ่งกับมันหรือ สิ่งอื่นที่จะไม่ทำงานอย่างถูกต้อง
>> และเป็นกลุ่มของความท้าทายนี้เป็น พวกคุณที่จะปรับเปลี่ยนจริงๆ dictionary.c
เราจะให้คุณ 140,000 คำในพจนานุกรม
เราจะให้คุณข้อความ แฟ้มที่มีคำพูดเหล่านั้น
และเราต้องการให้คุณสามารถจัดระเบียบ พวกเขาเข้าไปในตารางแฮชหรือ Trie
เพราะเมื่อเราขอให้คุณสะกด check-- คิดว่าคุณกำลังสะกด
การตรวจสอบเช่นเดียวกับโอดิสซีของโฮเมอร์
มันเป็นเช่นนี้มากการทดสอบขนาดใหญ่
>> ลองคิดดูหากทุกเดียว คำที่คุณต้องมอง
ผ่านแถว 140,000 ค่านิยม
ที่จะใช้ตลอดไป สำหรับเครื่องของคุณทำงาน
นั่นคือเหตุผลที่เราต้องการที่จะจัดระเบียบของเรา ข้อมูลลงในโครงสร้างข้อมูลที่มีประสิทธิภาพมากขึ้น
เช่นตารางแฮชหรือ Trie
และแล้วพวกคุณชนิดสามารถ เมื่อคุณเข้าถึงค้นหา
สิ่งที่มากขึ้นได้อย่างง่ายดายและรวดเร็วยิ่งขึ้น
>> และเพื่อให้ระมัดระวังในการแก้ปัญหาการชนกัน
คุณกำลังจะได้รับพวง คำพูดของการเริ่มต้นกับเอว่า
คุณจะได้รับพวงคำ ที่เริ่มต้นด้วยบีขึ้นอยู่กับคุณ
คนวิธีที่คุณต้องการที่จะแก้ปัญหาได้
บางทีอาจจะมีมากขึ้น ฟังก์ชันแฮชที่มีประสิทธิภาพ
มากกว่าเพียงแค่ตัวอักษรตัวแรกของ บางสิ่งบางอย่างและอื่น ๆ ที่ขึ้นอยู่กับคุณ
ผู้ชายกับชนิดของการทำสิ่งที่คุณต้องการ
>> บางทีคุณอาจต้องการที่จะเพิ่ม ตัวอักษรทั้งหมดเข้าด้วยกัน
บางทีคุณอาจต้องการที่จะชอบทำสิ่งที่แปลก บัญชีจำนวนตัวอักษรที่
อะไรก็ตาม
ขึ้นอยู่กับพวกคุณว่าคุณต้องการที่จะทำ
หากคุณต้องการที่จะทำตารางแฮชถ้าคุณ ต้องการที่จะลอง Trie ที่ทั้งหมดขึ้นอยู่กับคุณ
ฉันจะเตือนคุณก่อนเวลาว่า Trie ปกติจะเป็นบิตยากขึ้น
เพียงเพราะมีจำนวนมาก คำแนะนำเพิ่มเติมในการติดตาม
แต่ทั้งหมดขึ้นอยู่กับพวกคุณ
มันไกลมีประสิทธิภาพมากขึ้น ในกรณีส่วนใหญ่
คุณต้องการที่จะจริงๆจะสามารถที่จะให้ ติดตามทั้งหมดของตัวชี้ของคุณ
ชอบทำสิ่งเดียวกัน ว่าฉันกำลังทำอะไรที่นี่
เมื่อคุณกำลังพยายามที่จะแทรก ค่าลงในตารางแฮชหรือลบ
ตรวจสอบให้แน่ใจว่าคุณ จริงๆการติดตาม
ของที่ทุกอย่างเป็นเพราะ มันเป็นเรื่องง่ายถ้าฉัน
พยายามที่จะแทรกเช่นคำว่าแอนดี้
ขอเพียงบอกว่าเป็น คำจริงคำว่าแอนดี้,
เป็นรายการยักษ์ของคำ
>> ถ้าฉันเพิ่งเกิดขึ้นกำหนด ผิดตัวชี้โอ๊ะ
ไปมีความสมบูรณ์ของ ส่วนที่เหลือของรายการที่เชื่อมโยงของฉัน
ตอนนี้คำเดียวที่ฉัน มีคือแอนดี้และตอนนี้
ทั้งหมดของคำอื่น ๆ ใน พจนานุกรมที่ได้รับการสูญเสีย
และเพื่อให้คุณต้องการที่จะให้แน่ใจว่าคุณ ติดตามทั้งหมดของตัวชี้ของคุณ
หรืออื่น ๆ ที่คุณกำลังจะได้รับ ปัญหาใหญ่ในรหัสของคุณ
วาดสิ่งที่ออกอย่างระมัดระวังทีละขั้นตอน
มันทำให้มันง่ายมากที่จะคิดว่า
>> และสุดท้ายคุณต้องการที่จะสามารถที่จะ ทดสอบประสิทธิภาพของคุณโปรแกรมของคุณ
บนกระดานใหญ่
ถ้าพวกคุณใช้ ดู CS50 ในขณะนี้
เรามีสิ่งที่เรียกว่าคณะกรรมการใหญ่
มันเป็นแผ่นคะแนนได้เร็วที่สุด ตรวจสอบการสะกดครั้งในทุก CS50
ตอนนี้ผมคิดว่าด้านบนเช่น 10 ครั้งผมคิดว่าแปดของพวกเขาเป็นพนักงาน
จริงๆเราต้องการพวกคุณที่จะชนะเรา
>> ทั้งหมดของเรากำลังพยายามที่จะดำเนินการ รหัสที่เร็วที่สุดเท่าที่จะทำได้
เราต้องการให้พวกคุณจะพยายามที่จะท้าทาย เราและดำเนินการได้เร็วกว่าที่เราทุกคน
สามารถ.
ดังนั้นนี้เป็นจริง ครั้งแรกที่เรา
ขอให้พวกคุณจะทำ pset ที่ จริงๆคุณสามารถทำในสิ่งที่วิธีการ
คุณต้องการ.
>> ฉันมักจะบอกนี้เป็นมากขึ้นคล้าย เพื่อการแก้ปัญหาในชีวิตจริงใช่มั้ย?
ผมบอกว่าเดี๋ยวก่อนฉันต้องการให้คุณทำเช่นนี้
สร้างโปรแกรมที่ไม่นี้สำหรับฉัน
มันทำ แต่คุณต้องการ
ผมเพิ่งรู้ว่าที่ฉันต้องการได้อย่างรวดเร็ว
นั่นคือความท้าทายของคุณในสัปดาห์นี้
พวกคุณที่เรากำลังจะ เพื่อให้คุณได้งาน
เราจะให้คุณท้าทาย
และจากนั้นก็ขึ้นอยู่กับพวกคุณ ที่จะสมบูรณ์คิดเพียงแค่ออก
สิ่งที่เร็วที่สุดและมากที่สุด วิธีที่มีประสิทธิภาพในการดำเนินการนี​​้
ใช่?
>> ผู้ชม: พวกเราจะได้รับอนุญาตให้ถ้า ต้องการเพื่อการวิจัยวิธีการได้เร็วขึ้น
ที่จะทำตารางแฮชออนไลน์ที่เราสามารถทำได้ และกล่าวถึงรหัสของคนอื่น?
ANDI เป็ง: ใช่ดีทั้งหมด
ดังนั้นถ้าพวกคุณอ่าน ข้อมูลจำเพาะมีเส้น
ในสเปคที่ระบุว่าพวกคุณ เป็นบริการฟรีเพื่อการวิจัยกัญชา
ฟังก์ชั่นในสิ่งที่บางส่วน ของฟังก์ชันแฮชได้เร็วขึ้น
เพื่อให้ทำงานได้เป็นสิ่งที่ผ่าน ตราบใดที่คุณอ้างว่ารหัส
ดังนั้นบางคนมีอยู่แล้ว คิดออกวิธีการได้อย่างรวดเร็ว
ในการดำเนินการตรวจสอบการสะกดคำของอย่างรวดเร็ว วิธีการในการเก็บข้อมูล
ทั้งหมดขึ้นอยู่กับพวกคุณถ้าคุณ ต้องการเพียงแค่ใช้เวลาที่ใช่มั้ย?
ให้แน่ใจว่าคุณกำลังอ้างถึง
ความท้าทายที่นี่จริงๆ ที่เรากำลังพยายามที่จะทดสอบ
คือการทำให้แน่ใจว่าคุณรู้ว่า ทางของรอบตัวชี้
เท่าที่คุณดำเนินการ ฟังก์ชั่นแฮชที่เกิดขึ้นจริง
และขึ้นมาพร้อมกับเช่น ทางคณิตศาสตร์ที่จะทำอย่างนั้น
พวกคุณสามารถวิจัยสิ่งที่ วิธีการออนไลน์ที่พวกคุณต้องการ
ใช่?
>> ผู้ชม: เราสามารถกล่าวถึงเพียง โดยใช้ [ไม่ได้ยิน]
>> ANDI เป็ง: ใช่
คุณสามารถเพียงแค่ในความคิดเห็นของคุณ คุณสามารถอ้างเช่นโอ้
ที่นำมาจากญาดา, ญาดา, ญาดา, ฟังก์ชันแฮช
ใครมีคำถามหรือข้อสงสัย
เราแวะจริง ผ่านส่วนในวันนี้
ผมจะขึ้นที่นี่เพื่อ ตอบคำถามได้เป็นอย่างดี
>> นอกจากนี้ที่ผมกล่าวว่าสำนักงาน ชั่วโมงในคืนนี้และวันพรุ่งนี้
ข้อมูลจำเพาะในสัปดาห์นี้เป็นจริง ซุปเปอร์ที่ง่ายและสั้นสุดที่จะอ่าน
ผมจะแนะนำการดูเพียง อ่านทั้งหมดของมัน
>> และ Zamyla จริงคุณเดิน ผ่านแต่ละฟังก์ชั่น
คุณจำเป็นต้องใช้และเพื่อให้มันเป็น มากชัดเจนว่าจะทำทุกอย่าง
เพียงเพื่อให้แน่ใจว่าคุณ ติดตามความเคลื่อนไหวของตัวชี้
นี้เป็น pset ที่ท้าทายมาก
>> มันไม่ได้เป็นสิ่งที่ท้าทายเพราะชอบ โอ้แนวคิดที่มีมากขึ้น
ยากหรือคุณต้องเรียนรู้ ไวยากรณ์ใหม่มากทาง
ที่คุณไม่สำหรับ pset ที่ผ่านมา
pset นี้เป็นเรื่องยากเพราะ มีคำแนะนำมากมาย
และแล้วก็มากง่ายมากที่จะครั้งเดียว คุณมีข้อผิดพลาดในรหัสของคุณจะไม่สามารถ
ที่จะหาข้อผิดพลาดที่เป็น
>> และมีความสมบูรณ์มากและความเชื่อมั่นในตัวคุณที่สุด คนที่จะสามารถที่จะชนะเรา [ไม่ได้ยิน]
การสะกดคำ
ที่จริงผมไม่ได้เขียนใด ๆ เหมือง แต่ฉันจะเขียนเหมือง
ดังนั้นในขณะที่คุณกำลังเขียน คุณผมจะเขียนเหมือง
ฉันจะพยายามที่จะทำให้ เหมืองเร็วกว่าคุณ
เราจะดูว่าใครมีหนึ่งที่เร็วที่สุด
>> และใช่ฉันจะดูทั้งหมดของ พวกคุณที่นี่ในวันอังคาร
ฉันจะทำงานชนิดเช่นการประชุมเชิงปฏิบัติการ pset ได้
ทั้งหมดในส่วนนี้ สัปดาห์การประชุมเชิงปฏิบัติการ pset,
เพื่อให้คุณผู้ชายที่มีจำนวนมากของโอกาส เพื่อขอความช่วยเหลือเวลาทำงานเช่นเคย
และผมหวังว่าจะได้ อ่านทั้งหมดของรหัสพวกคุณ
ฉันมีแบบทดสอบได้ที่นี่ถ้าคุณ คนต้องการที่จะมารับเหล่านั้น
นั่นคือทั้งหมดที่