>> เจสัน Hirschhorn: ยินดีต้อนรับทุกท่าน มาตราเจ็ด
เราอยู่ในสัปดาห์ที่เจ็ดของหลักสูตร
และจะเกิดขึ้นนี้พฤหัสบดี เป็นวันฮาโลวีนดังนั้นฉัน
แต่งตัวเหมือนฟักทอง
ฉันไม่สามารถโค้งกว่าและวางอยู่บน รองเท้าของฉันเพื่อที่ว่าทำไมฉัน
เพียงแค่สวมใส่ถุงเท้า
ฉันยังไม่ได้สวมใส่อะไรภายใต้ นี้ดังนั้นฉันไม่สามารถเอามันออกถ้าหากมันเป็น
เบี่ยงเบนความสนใจให้กับคุณ
ผมต้องขออภัยล่วงหน้าสำหรับการที่
คุณไม่จำเป็นที่จะจินตนาการ สิ่งที่เกิดขึ้น
ฉันสวมใส่บ็อกเซอร์
ดังนั้นจึงเป็นสิ่งที่ดี
>> ผมมีเรื่องที่ไม่เกี่ยวกับเหตุผลที่ฉัน แต่งตัวเป็นฟักทอง แต่ฉันกำลังจะไป
บันทึกว่าต่อไปในส่วนนี้ เพราะผมไม่ต้องการที่จะเริ่มต้น
เรามีจำนวนมากของสิ่งที่น่าตื่นเต้น ที่จะไปในช่วงสัปดาห์นี้
ส่วนใหญ่ของพวกเขาเกี่ยวข้องโดยตรงกับเรื่องนี้ ปัญหาสัปดาห์ชุดสะกดผิด
เรากำลังจะไปกว่าการเชื่อมโยง รายการและตารางแฮช
สำหรับส่วนทั้งหมด
ฉันใส่รายการนี​​้ขึ้นทุกสัปดาห์ในรายการ ทรัพยากรสำหรับคุณที่จะช่วยให้คุณมี
เนื้อหาในหลักสูตรนี้
ถ้าที่สูญเสียหรือถ้ากำลังมองหาบาง ข้อมูลเพิ่มเติมตรวจสอบหนึ่งของ
ทรัพยากรเหล่านี้
>> อีกครั้ง pset6 เป็นสะกดผิด pset สัปดาห์นี้
และยังขอให้คุณและฉัน ขอแนะนำให้คุณใช้งานอื่น ๆ
ทรัพยากรเฉพาะสำหรับ pset นี้
โดยเฉพาะอย่างยิ่งสามฉันได้ ปรากฏขึ้นบนหน้าจอ -
gdb ซึ่งเราได้รับคุ้นเคยกับ และได้ใช้ในขณะที่ตอนนี้เป็น
จะเป็นประโยชน์มากในสัปดาห์นี้
ดังนั้นผมจึงใส่ที่นี่
แต่เมื่อใดก็ตามที่คุณกำลังทำงานกับซี คุณควรจะใช้ gdb เสมอ
แก้ปัญหาโปรแกรมของคุณ
สัปดาห์นี้ยัง valgrind
ไม่มีใครรู้ว่าสิ่งที่ valgrind อย่างไร
>> ผู้ชม: มันจะตรวจสอบการรั่วไหลของหน่วยความจำ
>> เจสัน Hirschhorn: Valgrind การตรวจสอบการรั่วไหลของหน่วยความจำ
ดังนั้นถ้าคุณมีอะไรบางอย่างใน malloc ของคุณ โปรแกรมที่คุณกำลังขอให้สำหรับหน่วยความจำ
ในตอนท้ายของโปรแกรมของคุณคุณมี การเขียนฟรีในทุกสิ่งที่คุณได้
malloced เพื่อให้หน่วยความจำกลับ
หากคุณไม่ได้เขียนฟรีที่สิ้นสุดและ โปรแกรมของคุณมาถึงข้อสรุป
ทุกอย่างจะทำงานโดยอัตโนมัติ เป็นอิสระ
และสำหรับโปรแกรมขนาดเล็กก็ ไม่ว่าใหญ่จัดการ
แต่ถ้าคุณกำลังเขียนทำงานอีกต่อไป โปรแกรมที่ไม่เลิก
จำเป็นต้องในไม่กี่นาทีหรือ สองสามวินาทีจากนั้นหน่วยความจำรั่วไหล
จะกลายเป็นข้อใหญ่
>> ดังนั้นสำหรับ pset6 ความคาดหวังก็คือว่า คุณจะมีศูนย์การรั่วไหลของหน่วยความจำด้วย
โปรแกรมของคุณ
เพื่อตรวจสอบการรั่วไหลของหน่วยความจำ valgrind ทำงาน และมันจะทำให้คุณมีบางอย่างที่ดี
เอาท์พุทให้คุณทราบว่า หรือทุกอย่างไม่ได้เป็นอิสระ
เราจะปฏิบัติกับมันในภายหลัง วันนี้หวังว่า
>> ในที่สุดคำสั่งต่าง
คุณใช้สิ่งที่คล้ายกับมัน ใน pset5 ด้วยเครื่องมือแอบมอง
อนุญาตให้คุณสามารถดูภายใน
นอกจากนี้คุณยังใช้ diff เกินไปต่อ ปัญหาที่กำหนดสเป็ค
แต่ในอนุญาตให้คุณสามารถ เปรียบเทียบสองไฟล์
คุณสามารถเปรียบเทียบไฟล์บิตแมปและ ข้อมูลส่วนหัวของการแก้ปัญหาพนักงานและ
การแก้ปัญหาของคุณใน pset5 ถ้า คุณเลือกที่จะใช้มัน
ความแตกต่างจะช่วยให้คุณ ทำอย่างนั้นได้เป็นอย่างดี
คุณสามารถเปรียบเทียบคำตอบที่ถูกต้องสำหรับ ปัญหาในสัปดาห์นี้กำหนดให้คำตอบของคุณ
และดูว่าเส้นขึ้นหรือเห็น ที่ผิดพลาดได้
>> ดังนั้นผู้ที่มีสามเครื่องมือที่ดีที่ คุณควรใช้สำหรับสัปดาห์นี้และ
แน่นอนตรวจสอบโปรแกรมของคุณ กับเหล่านี้สามเครื่องมือ
ก่อนที่จะเปิดเข้ามา
อีกครั้งที่ผมได้กล่าวถึงทุกสัปดาห์ ถ้าคุณมีความคิดเห็นใด ๆ สำหรับฉัน - ทั้งสอง
เชิงบวกและสร้างสรรค์ -
อย่าลังเลที่จะมุ่งหน้าไปยังเว็บไซต์ ที่ด้านล่างของสไลด์นี้
และใส่มันมี
ผมขอขอบคุณที่ใด ๆ และข้อเสนอแนะทั้งหมด
และถ้าคุณให้ฉันสิ่งที่เฉพาะเจาะจงที่ ที่ฉันสามารถทำได้ในการปรับปรุงหรือว่าฉัน
ทำดีที่คุณต้องการให้ฉัน ต่อมาผมใช้เวลาที่หัวใจและ
จริงๆพยายามอย่างหนักที่จะรับฟัง ความคิดเห็นของคุณ
ฉันไม่สามารถสัญญาฉันจะทำอย่างไร ทุกอย่าง แต่ชอบใส่
ฟักทองเครื่องแต่งกายทุกสัปดาห์
>> ดังนั้นเราจะใช้จ่ายจำนวนมากของ ส่วนที่ผมกล่าวถึงการพูดคุยเกี่ยวกับ
รายการที่เชื่อมโยงและตารางแฮชซึ่ง จะโดยตรงที่ใช้บังคับกับ
ปัญหาการตั้งค่าในสัปดาห์นี้
รายการที่เชื่อมโยงเราจะไปกว่าค่อนข้าง ได้อย่างรวดเร็วเพราะเราได้ใช้จ่ายยุติธรรมบิต
เวลาไปกว่านั้นในส่วน
และเพื่อให้เราจะได้รับตรงเข้า ปัญหาการเข้ารหัสสำหรับรายการที่เชื่อมโยง
และแล้วในที่สุดเราจะพูดคุยเกี่ยวกับ สับตารางและวิธีการที่พวกเขานำไปใช้กับนี้
ปัญหาสัปดาห์ชุด
>> คุณเคยเห็นรหัสนี้ก่อนที่จะ
นี้เป็น struct และเป็นที่กำหนด สิ่งใหม่ที่เรียกว่าโหนด
และภายในโหนดมีจำนวนเต็ม ที่นี่และมีตัวชี้ไปยัง
โหนดอื่น
เราได้เห็นนี้มาก่อน
นี้ได้รับการขึ้นมาสำหรับ สองสามสัปดาห์ในขณะนี้
มันรวมตัวชี้ซึ่งเราได้รับ การทำงานร่วมกับและ structs ซึ่งช่วยให้
ที่เราจะรวมทั้งสองที่แตกต่างกัน สิ่งที่เป็นชนิดข้อมูลหนึ่ง
>> มีจำนวนมากที่เกิดขึ้นบนหน้าจอ
แต่ทั้งหมดก็ควรจะค่อนข้าง ที่คุ้นเคยกับคุณ
ในบรรทัดแรกที่เรา ประกาศโหนดใหม่
แล้วภายในที่โหนดใหม่ผมตั้ง จำนวนเต็มในโหนดที่หนึ่ง
เราจะเห็นในบรรทัดถัดไปที่ฉันทำ คำสั่ง printf แต่ฉันเป็นสีเทา
คำสั่ง printf เพราะจริงๆ ส่วนหนึ่งที่สำคัญคือสายนี้ที่นี่ -
new_node.n
อะไรจุดหมายความว่าอย่างไร
>> ผู้ชม: ไปที่โหนดและ ประเมินมูลค่า n สำหรับมัน
>> เจสัน Hirschhorn: นั่น ตรงขวา
จุดหมายถึงการเข้าถึงส่วนที่ n ของโหนดใหม่นี้
บรรทัดถัดไปนี้จะเป็นอย่างไร
ไมเคิล
>> ผู้ชม: มันจะสร้างโหนดอื่น ที่จะชี้ไปที่โหนดใหม่
>> เจสัน Hirschhorn: ดังนั้นมันไม่ได้ สร้างโหนดใหม่
มันจะสร้างสิ่งที่?
>> ผู้ชม: ตัวชี้
>> เจสัน Hirschhorn: ตัวชี้ไปยังโหนด, ตามที่ระบุโดยโหนดนี้ * ที่นี่
ดังนั้นมันจะสร้างตัวชี้ไปยังโหนด
และที่โหนดมันชี้ กับไมเคิล?
>> ผู้ชม: โหนดใหม่
>> เจสัน Hirschhorn: โหนดใหม่
และก็ชี้ไปที่นั่นเพราะเราได้ ให้มันอยู่ของโหนดใหม่
และตอนนี้ในสายนี้ที่เราเห็น สองวิธีที่แตกต่างกันของ
แสดงในสิ่งเดียวกัน
และผมอยากจะชี้ให้เห็นวิธีการเหล่านี้ สองสิ่งที่เหมือนกัน
ในบรรทัดแรกที่เรา dereference ตัวชี้
ดังนั้นเราจึงไปที่โหนด
นั่นคือสิ่งที่นี้หมายถึงดาว
เราได้เห็นว่าก่อนที่จะมีการชี้
ไปที่โหนดที่
ที่อยู่ในวงเล็บ
แล้วเข้าถึงผ่านทางผู้ประกอบการจุด n องค์ประกอบของโหนดที่
>> เพื่อให้สละไวยากรณ์ เราเห็นที่นี่และตอนนี้
ใช้กับตัวชี้
แน่นอนว่าจะได้รับชนิดของว่างถ้า คุณกำลังเขียนวงเล็บที่ -
ดาวที่และจุดที่
จะได้รับไม่ว่างน้อย
ดังนั้นเราจึงมีน้ำตาลประโยคบาง
และบรรทัดนี้ที่นี่ -
ptr_node> n
นั่นจะเป็นสิ่งที่แน่นอนเดียวกัน
ดังนั้นทั้งสองบรรทัดของรหัสที่ เทียบเท่าและจะทำ
สิ่งเดียวที่แน่นอน
>> แต่ผมอยากจะชี้ให้ผู้ที่ออกมาก่อน เราจะไปเพิ่มเติมใด ๆ เพื่อให้คุณเข้าใจ
ที่จริงเรื่องนี้ที่นี่เป็น เพียงแค่น้ำตาลประโยคเพื่อ dereferencing
ตัวชี้และจากนั้นจะไป ส่วนที่ n ของ struct ที่
คำถามใด ๆ เกี่ยวกับสไลด์นี้
ตกลง
>> ดังนั้นเรากำลังจะผ่านไปสองสาม ของการดำเนินงานที่คุณสามารถทำได้ใน
รายการเชื่อมโยง
รายการที่เชื่อมโยงการเรียกคืนเป็นชุดของ โหนดที่ชี้ไปยังอีกคนหนึ่ง
และเรามักจะเริ่มต้นด้วยการชี้ เรียกว่าหัวทั่วไปที่ชี้ไปยัง
สิ่งแรกที่อยู่ในรายการ
ดังนั้นในบรรทัดแรกที่นี่เรา มี L เดิมของเราครั้งแรก
ดังนั้นสิ่งที่คุณสามารถคิด - นี้ ข้อความที่นี่คุณสามารถคิดเป็น
เพียงแค่ชี้ที่เราได้เก็บไว้ บางที่จุด
ไปยังองค์ประกอบแรก
และในรายการที่เชื่อมโยงนี้ เรามีสี่โหนด
แต่ละโหนดเป็นกล่องใหญ่
กล่องขนาดใหญ่ภายในใหญ่ กล่องเป็นส่วนหนึ่งจำนวนเต็ม
และแล้วเราก็มีส่วนหนึ่งของตัวชี้
>> กล่องเหล่านี้จะไม่ได้ดึง เพราะวิธีการขนาดใหญ่คือ
จำนวนเต็มไบต์?
วิธีการใหญ่อยู่ตอนนี้
สี่
และวิธีการที่มีขนาดใหญ่เป็นตัวชี้ได้หรือไม่
สี่
ดังนั้นจริงๆถ้าเราจะวาด นี้ในการวัดทั้งสองกล่อง
จะมีขนาดเดียวกัน
ในกรณีนี้เราต้องการที่จะแทรก บางสิ่งบางอย่างลงไปในรายการที่เชื่อมโยง
ดังนั้นคุณจะเห็นลงมาที่นี่เรากำลังใส่ ห้าเราสำรวจผ่าน
รายการที่เชื่อมโยงหาที่ห้า ไปแล้วใส่มัน
>> Let 's ทำลายลงและไปที่ นิด ๆ หน่อย ๆ ที่ช้ากว่า
ฉันจะชี้ไปที่คณะกรรมการ
ดังนั้นเราจึงมีโหนดที่ห้าของเรา ที่เราได้สร้างขึ้นใน mallocs
ทำไมทุกคนหัวเราะ
ล้อเล่น
ตกลง
ดังนั้นเราจึงได้ malloced ห้า
เราได้สร้างโหนดนี้ ที่อื่น
เรามีมันพร้อมที่จะไป
เราเริ่มต้นที่ด้านหน้าของ รายการของเรามีสอง
และเราต้องการที่จะแทรก ในแบบที่เรียงลำดับ
>> ดังนั้นหากเราเห็นสองและเราต้องการที่จะนำ ในห้าสิ่งที่เราทำเมื่อเราเห็น
สิ่งที่น้อยกว่าเรา
คืออะไร?
เราต้องการที่จะใส่ลงไปในห้านี้ รายการที่เชื่อมโยงทำให้มันเรียงลำดับ
เรามาดูกันจำนวนสอง
ดังนั้นเราจะทำอย่างไร
มาร์คัส?
>> AUDIENCE: Call ชี้ ไปยังโหนดถั​​ดไป
>> เจสัน Hirschhorn: และทำไม เราไปอย่างใดอย่างหนึ่งต่อไปหรือไม่
>> ผู้ชม: เพ​​ราะมันเป็น โหนดถั​​ดไปในรายการ
และเรารู้ว่าตำแหน่งอื่น
>> เจสัน Hirschhorn: และห้าเป็นมากขึ้น กว่าสองโดยเฉพาะอย่างยิ่ง
เพราะเราต้องการที่จะให้มันเรียงลำดับ
ดังนั้นห้ามากกว่าสอง
ดังนั้นเราจึงย้ายไปที่หน้าหนึ่ง
และตอนนี้เรามาถึงสี่
และสิ่งที่เกิดขึ้นเมื่อเราไปถึงสี่
>> ห้ามากกว่าสี่
ดังนั้นเราจึงให้ไป
และตอนนี้เราอยู่ที่หก
และเราทำในสิ่งที่เห็นที่หก?
มีคาร์ลอ?
>> ผู้ชม: หกมากกว่าห้า
>> เจสัน Hirschhorn: หกเป็น มากขึ้นกว่าห้า
ดังนั้นนั่นคือสิ่งที่เราต้องการ แทรกห้า
แต่เก็บไว้ในใจว่าถ้าเรา เพียง แต่มีตัวชี้หนึ่งที่นี่ -
นี้เป็นตัวชี้พิเศษของเราที่ traversing ผ่านรายการ
และเรากำลังชี้ไปที่หก
เราได้สูญเสียการติดตามของสิ่งที่ มาก่อนที่จะหก
ดังนั้นหากเราต้องการที่จะใส่ลงไปในสิ่งที่ รายการการรักษานี้แยกเรา
อาจจะต้องมีตัวชี้ว่ามีกี่?
>> ผู้ชม: สอง
>> เจสัน Hirschorn: สอง
หนึ่งในการติดตามปัจจุบัน และหนึ่งในการติดตาม
ก่อนหน้าหนึ่ง
นี้เป็นเพียงรายการที่เชื่อมโยงโดยลำพัง
มันจะไปทิศทางเดียว
ถ้าเรามีรายการที่เชื่อมโยงทวีคูณที่ ทุกอย่างชี้ไปที่สิ่งที่
หลังจากที่มันและสิ่งก่อนที่มันแล้ว เราจะไม่จำเป็นต้องทำอย่างนั้น
แต่ในกรณีนี้เราไม่ต้องการที่จะสูญเสีย ติดตามของสิ่งที่มาก่อนเราในกรณีที่
เราต้องใส่ห้าอยู่ที่ไหนสักแห่ง อยู่ตรงกลาง
บอกว่าเราถูกใส่เก้า
อะไรจะเกิดขึ้นเมื่อ เราได้แปด
>> ผู้ชม: คุณจะต้อง ได้รับจุดว่างว่า
แทนที่จะมีจุด null คุณต้องการมี เพื่อเพิ่มองค์ประกอบแล้วมี
มันชี้ไปที่เก้า
>> เจสัน Hirschorn: แน่นอน
ดังนั้นเราจึงได้รับแปด
เราไปถึงจุดสิ้นสุดของรายการเพราะ นี้จะชี้ไปที่เป็นโมฆะ
และตอนนี้แทนที่จะมีมันชี้ไปที่ null เรามีมันชี้ไปที่โหนดใหม่ของเรา
และเราจะกำหนดตัวชี้ใน โหนดใหม่ของเราให้เป็นโมฆะ
ไม่มีใครมีคำถามใด ๆ เกี่ยวกับการแทรก?
ถ้าฉันไม่สนใจเกี่ยวกับ เก็บรายชื่อเรียงลำดับ?
>> ผู้ชม: ติดได้ที่ จุดเริ่มต้นหรือจุดสิ้นสุด
>> เจสัน Hirschorn: ติดได้ที่ จุดเริ่มต้นหรือจุดสิ้นสุด
ที่หนึ่งที่เราควรทำอย่างไร
บ๊อบบี้?
ทำไมสิ้นสุดหรือไม่
>> ผู้ชม: เพ​​ราะจุดเริ่มต้น เต็มไปแล้ว
>> เจสัน Hirschorn: OK
จุดเริ่มต้นที่เต็มไปแล้ว
ที่อยากจะเถียงกับบ๊อบบี้
มาร์คัส
>> ผู้ชม: ดีที่คุณอาจต้องการ ติดที่จุดเริ่มต้นเพราะ
มิฉะนั้นถ้าคุณวางมันไว้ที่ ท้ายที่คุณจะต้อง
สำรวจรายชื่อทั้งหมด
>> เจสัน Hirschorn: แน่นอน
ดังนั้นหากเรากำลังคิดเกี่ยวกับรันไทม์ runtime ใส่ที่ปลาย
n จะเป็นขนาดนี้
อะไร O runtime ใหญ่ใส่ ที่จุดเริ่มต้นหรือไม่
เวลาคงที่
ดังนั้นหากคุณไม่ดูแลเกี่ยวกับการรักษา สิ่งที่เรียงลำดับมากดีกว่าที่จะเพียงแค่
แทรกที่จุดเริ่มต้นของรายการนี​​้
และที่สามารถทำได้ในเวลาคงที่
>> ตกลง
การดำเนินการต่อไปคือการหาที่อื่น ๆ - เราได้ phrased นี้การค้นหา
แต่เรากำลังจะมองผ่าน รายการที่เชื่อมโยงกับวัตถุบางอย่าง
พวกคุณได้เห็นสำหรับ ก่อนที่จะค้นหาในการบรรยาย
แต่เราเพียงแค่การจัดเรียงของมันด้วย แทรกหรืออย่างน้อยใส่
สิ่งที่เรียงลำดับ
คุณมองผ่านไปโดยโหนดโหนด จนกว่าคุณจะพบหมายเลขที่คุณ
ที่กำลังมองหา
เกิดอะไรขึ้นถ้าคุณมาถึง ในตอนท้ายของรายการหรือไม่
บอกว่าฉันกำลังมองหาเก้าและฉัน ถึงจุดสิ้นสุดของรายการ
สิ่งใดที่เราจะทำอย่างไร
>> ผู้ชม: กลับเท็จ
>> เจสัน Hirschorn: กลับเท็จ
เราไม่ได้พบว่ามัน
ถ้าคุณถึงจุดสิ้นสุดของรายการและ คุณไม่พบหมายเลขที่คุณกำลัง
มองหาก็ไม่ได้อยู่ที่นั่น
คำถามใด ๆ เกี่ยวกับการหา
หากนี่เป็นรายการที่เรียงลำดับสิ่งที่จะ แตกต่างกันสำหรับการค้นหาของเราหรือไม่
ใช่
>> ผู้ชม: มันจะหาค่าแรก ที่มากกว่าหนึ่ง
คุณกำลังมองหาและ แล้วกลับเท็จ
>> เจสัน Hirschorn: แน่นอน
ดังนั้นถ้ามันเป็นรายการที่เรียงลำดับถ้าเราได้รับการ สิ่งที่ยิ่งใหญ่กว่าสิ่งที่
เรากำลังมองหาเราไม่จำเป็นต้อง ให้ไปที่ส่วนท้ายของรายการ
เราสามารถที่จุดที่กลับเท็จ เพราะเราไม่ได้จะไปหามัน
คำถามคือตอนนี้เราได้พูดคุยเกี่ยวกับ ทำให้รายการเชื่อมโยงเรียงลำดับ
ทำให้พวกเขาไม่ได้คัดแยก
นั่นจะเป็นสิ่งที่คุณกำลัง อาจจะต้องคิดเกี่ยวกับ
เมื่อมีปัญหาการเข้ารหัสตั้งห้าถ้าคุณ เลือกตารางแฮชที่มีการแยก
วิธีการผูกมัดที่ เราจะพูดถึงในภายหลัง
>> แต่มันเป็นความคุ้มค่าที่จะเก็บรายชื่อ ที่เรียงลำดับแล้วจะสามารถที่จะอาจจะมี
การค้นหาเร็ว
หรือจะเป็นดีกว่าที่จะแทรก อะไรบางอย่างใน runtime คงที่ แต่แล้ว
มีอีกต่อไปการค้นหา
นั่นคือการถ่วงดุลอำนาจมีสิทธิที่คุณ ได้รับที่จะตัดสินใจเลือกสิ่งที่มีความเหมาะสมมากขึ้น
สำหรับปัญหาเฉพาะของคุณ
และมีไม่จำเป็นต้องเป็นอย่างใดอย่างหนึ่ง คำตอบที่เหมาะสมอย่างแน่นอน
แต่มันก็แน่นอนการตัดสินใจของคุณจะได้รับ ที่จะทำให้และอาจจะดีที่จะปกป้อง
ว่าในการพูดการแสดงความคิดเห็นหรือสองทำไม คุณเลือกหนึ่งในช่วงอื่น ๆ
>> ในที่สุดลบ
เราได้เห็นการลบ
มันคล้ายกับการค้นหา
เรามองหาองค์ประกอบ
บอกว่าเรากำลังพยายามที่จะลบหก
ดังนั้นเราจึงหาหกที่นี่
สิ่งที่เราจะต้องทำให้แน่ใจว่าเรา ทำคือว่าสิ่งที่จะชี้ไปที่
หก - ในขณะที่เราเห็นในขั้นตอนที่ สองลงที่นี่ -
สิ่งที่ชี้ถึงหกความต้องการที่จะ ข้ามหกตอนนี้และจะมีการเปลี่ยนแปลง
สิ่งที่หกจะชี้ไปที่
เราไม่ต้องการที่จะเคยนี้้ส่วนที่เหลือของ รายการของเราโดยลืมที่จะกำหนดว่า
ตัวชี้หน้าที่แล้ว
แล้วบางครั้งก็ขึ้นอยู่ กับโปรแกรมที่พวกเขาจะเพียงแค่
ลบโหนดนี้อย่างสิ้นเชิง
บางครั้งคุณจะต้องการที่จะกลับมา ค่าที่อยู่ในโหนดนี้
เพื่อให้เป็นวิธีการลบงาน
คำถามใด ๆ เกี่ยวกับการลบ
>> ผู้ชม: ดังนั้นถ้าคุณกำลังจะลบ มันจะให้คุณเพียงแค่ใช้ฟรีเพราะ
สันนิษฐานว่ามันถูก malloced?
>> เจสัน Hirschorn: ถ้าคุณต้องการที่จะเป็นอิสระ บางสิ่งบางอย่างที่ว่าถูกต้องและคุณ
malloced มัน
บอกว่าเราอยากจะกลับค่านี้
เราอาจจะกลับหกและฟรีแล้ว โหนดนี้และโทรฟรีในนั้น
หรือเราอาจต้องการโทรฟรีครั้งแรก แล้วกลับหก
>> ตกลง
จึงขอย้ายไปฝึกการเขียนโปรแกรม
เรากำลังจะไปรหัสสามฟังก์ชั่น
หนึ่งคือเรียกว่า insert_node
เพื่อให้คุณมีรหัสที่ฉันส่งอีเมลที่คุณและ ถ้าคุณกำลังดูนี้ในภายหลัง
คุณสามารถเข้าถึงรหัสใน linked.c บนเว็บไซต์ CS50
แต่ใน linked.c มีบาง รหัสโครงกระดูกที่มีอยู่แล้ว
ถูกเขียนขึ้นสำหรับคุณ
แล้วมีฟังก์ชั่นที่สอง คุณจะต้องเขียน
>> ครั้งแรกที่เรากำลังจะ เขียน insert_node
และสิ่งที่ไม่ insert_node แทรกเป็นจำนวนเต็ม
และคุณกำลังให้จำนวนเต็ม เป็นรายการที่เชื่อมโยง
และโดยเฉพาะอย่างยิ่งที่คุณต้องการ เพื่อให้รายการที่เรียงลำดับ
จากที่เล็กที่สุดไปหามากที่สุด
นอกจากนี้คุณไม่ต้องการที่จะ แทรกรายการที่ซ้ำกันใด ๆ
สุดท้ายที่คุณสามารถดู insert_node กลับบูล
ดังนั้นคุณควรจะให้ผู้ใช้ทราบ หรือไม่แทรกเป็น
ที่ประสบความสำเร็จโดยการกลับจริงหรือเท็จ
ในตอนท้ายของโปรแกรมนี้ -
และขั้นตอนนี้คุณไม่จำเป็นต้อง กังวลเกี่ยวกับการพ้นอะไร
ดังนั้นสิ่งที่คุณกำลังทำคือการใช้จำนวนเต็ม และใส่ลงในรายการ
>> นั่นคือสิ่งที่ฉันขอให้คุณทำตอนนี้
อีกครั้งใน linked.c ซึ่งคุณ ทุกคนมีความเป็นรหัสโครงกระดูก
และคุณจะเห็นทางด้านล่าง การประกาศฟังก์ชันตัวอย่าง
อย่างไรก็ตามก่อนที่จะเข้าสู่การเข้ารหัสมัน ใน C ผมขอแนะนำให้คุณไป
ผ่านขั้นตอนที่เราได้รับ การฝึกซ้อมในแต่ละสัปดาห์
เราได้ผ่านไปแล้ว ภาพนี้
ดังนั้นคุณควรมีความเข้าใจบางอย่าง ของวิธีการทำงานนี้
แต่ฉันจะขอแนะนำให้คุณเขียน pseudocode ก่อนดำน้ำค่ะบาง
และเรากำลังจะไปกว่า pseudocode เป็นกลุ่ม
และจากนั้นเมื่อคุณได้เขียนของคุณ pseudocode และเมื่อเราได้เขียนของเรา
pseudocode เป็นกลุ่มที่คุณสามารถ ไปในการเขียนโปรแกรมใน C.
>> ในฐานะที่เป็นหัวขึ้นฟังก์ชั่น insert_node น่าจะเป็นของยาก
สามที่เรากำลังจะเขียนเพราะผม เพิ่มข้อ จำกัด เพิ่มเติมบางอย่างไป
การเขียนโปรแกรมของคุณโดยเฉพาะอย่างยิ่งที่ คุณจะไม่สามารถแทรกใด ๆ
รายการที่ซ้ำกันและรายการที่ ควรจะเรียงลำดับ
ดังนั้นนี้เป็นโปรแกรมที่ไม่น่ารำคาญ ที่คุณต้องรหัส
และคุณไม่ 6:55 ทำไม นาทีเพียงเพื่อให้ได้ทำงานใน
pseudocode และรหัส
แล้วเราจะเริ่มต้น จะเป็นกลุ่ม
อีกครั้งถ้าคุณมีคำถามใด ๆ เพียงแค่ ยกมือของคุณและฉันจะมารอบ
.
>> นอกจากนี้เรายังทำโดยทั่วไปเหล่านี้ -
หรือฉันไม่ชัดเจนว่าคุณ สามารถทำงานร่วมกับคน
แต่เห็นได้ชัดว่าผมขอสนับสนุนให้คุณ ถ้าคุณมีคำถามที่จะถาม
เพื่อนบ้านนั่งถัดจากคุณ หรือแม้กระทั่งการทำงานร่วมกับใครบางคน
อื่นถ้าคุณต้องการ
นี้ไม่จำเป็นต้องเป็นบุคคล กิจกรรมเงียบ
>> ขอเริ่มต้นด้วยการเขียนบางอย่าง pseudocode บนกระดาน
ที่สามารถให้ฉันบรรทัดแรกของ pseudocode สำหรับโปรแกรมนี้
สำหรับฟังก์ชั่นนี้ค่อนข้าง - insert_node
Alden?
>> ผู้ชม: ดังนั้นสิ่งแรกที่ผมทำก็คือ สร้างตัวชี้ไปยังโหนดใหม่และฉัน
เริ่มต้นมันชี้ไปที่เดียวกัน สิ่งที่รายการจะชี้ไปที่
>> เจสัน Hirschorn: OK
ดังนั้นคุณกำลังสร้างตัวชี้ใหม่ ไปยังรายการที่ไม่โหนด
>> ผู้ชม: ขวา
ใช่
>> เจสัน Hirschorn: OK
และแล้วสิ่งที่เราต้องการจะทำอย่างไร
อะไรหลังจากที่
สิ่งที่เกี่ยวกับโหนดหรือไม่
เราไม่ได้มีโหนด
เราก็มีค่า
ถ้าเราต้องการที่จะแทรกโหนดเป็นสิ่งที่เราทำ ต้องทำครั้งแรกก่อนที่เราจะยังสามารถ
คิดเกี่ยวกับการใส่มันได้หรือไม่
>> ผู้ชม: โอ้ขอโทษ
เราต้องไปยังพื้นที่ malloc โหนด
>> เจสัน Hirschorn: ยอดเยี่ยม
ขอทำ -
ตกลง
ไม่สามารถเข้าถึงสูงที่
ตกลง
เรากำลังจะไปลงแล้ว เรากำลังใช้สองคอลัมน์
ฉันไม่สามารถไปที่ -
ตกลง
สร้างโหนดใหม่
คุณสามารถสร้างตัวชี้ไปยังรายการอื่น หรือคุณก็สามารถใช้รายการที่มีอยู่
คุณไม่ได้จริงๆต้องทำ
>> ดังนั้นเราจึงสร้างโหนดใหม่
ยิ่งใหญ่
นั่นคือสิ่งที่เราทำครั้งแรก
ถัดไปคืออะไร
>> ผู้ชม: รอ
เราควรจะสร้างโหนดใหม่ในขณะนี้หรือ เราควรที่จะรอเพื่อให้แน่ใจว่า
มีรายการที่ซ้ำกันของโหนดไม่มี ในรายการก่อนที่เราจะสร้างมันได้หรือไม่
>> เจสัน Hirschorn: เป็นคำถามที่ดี
ขอบอกว่าในภายหลังเพราะ ส่วนใหญ่เวลาที่เราจะสร้าง
โหนดใหม่
ดังนั้นเราจะให้ที่นี่
แต่นั่นเป็นคำถามที่ดี
ถ้าเราสร้างมันขึ้นมาและเราพบ ที่ซ้ำกันเป็นสิ่งที่ควรจะเป็น
ที่เราทำก่อนที่จะกลับ?
>> ผู้ชม: มันฟรี
>> เจสัน Hirschorn: ใช่
มันอาจจะฟรี
ตกลง
เราจะทำอะไรหลังจากที่เรา สร้างโหนดใหม่ได้หรือไม่
แอนนี่?
>> ผู้ชม: เราใส่ ตัวเลขที่อยู่ในโหนดหรือไม่
>> เจสัน Hirschorn: แน่นอน
เราใส่จำนวน - เรา malloc พื้นที่
ฉันจะออกจากที่ ทั้งหมดเป็นหนึ่งบรรทัด
แต่คุณขวา
เรา malloc พื้นที่แล้ว เราใส่หมายเลขระบบ
เรายังสามารถตั้งค่าตัวชี้ ส่วนหนึ่งของมันเป็นโมฆะ
นั่นคือสิ่งที่ถูกต้อง
และแล้วสิ่งที่เกี่ยวกับหลังจากที่
เราวาดภาพนี้ขึ้นมาบนเรือ
ดังนั้นเราจะทำอย่างไร
>> ผู้ชม: เราไปผ่านรายการ
>> เจสัน Hirschorn: ไปผ่านรายการ
ตกลง
และสิ่งที่เราจะตรวจสอบในแต่ละโหนด
เคิร์ตสิ่งที่เราตรวจสอบ เพื่อที่แต่ละโหนด?
>> ผู้ชม: ดูว่าค่า n ของ โหนดที่มากกว่าค่า n
ของโหนดของเรา
>> เจสัน Hirschorn: OK
ฉันจะทำ -
ใช่ตกลง
ดังนั้นจึงเป็น n -
ฉันจะบอกว่าถ้าค่ามากขึ้น กว่าโหนดนี้แล้วสิ่งที่เราจะทำอย่างไร
>> ผู้ชม: ดีแล้วที่เราใส่ สิ่งที่ถูกต้องก่อนที่จะว่า
>> เจสัน Hirschorn: OK
ดังนั้นถ้ามันมากขึ้นกว่านี้ แล้วเราต้องการแทรก
แต่เราต้องการที่จะใส่มันขวาก่อนที่ เพราะเรายังจะต้องมี
การติดตามแล้ว ของสิ่งที่มีมาก่อน
ดังนั้นก่อนที่จะแทรก
ดังนั้นเราอาจจะลืมอะไรบางอย่าง ก่อนหน้านี้เมื่อวันที่
เราอาจจำเป็นต้องได้รับการรักษา ติดตามสิ่งที่เกิดขึ้น
แต่เราจะได้รับกลับไปที่นั่น
ดังนั้นสิ่งที่มีค่าน้อยกว่า?
เคิร์ตสิ่งที่เราทำอย่างไรถ้า ค่าน้อยกว่า
>> ผู้ชม: แล้วคุณก็ให้ไป เว้นแต่จะเป็นคนสุดท้ายที่
>> เจสัน Hirschorn: ฉันชอบที่
เพื่อไปยังโหนดถั​​ดไป
เว้นแต่จะเป็นคนสุดท้ายที่ -
เราอาจจะตรวจสอบว่า ในแง่ของสภาพ
แต่ใช่โหนดถั​​ดไป
และที่ได้รับต่ำเกินไป ดังนั้นเราจะย้ายไปที่นี่
แต่ถ้า -
ทุกคนสามารถมองเห็นนี้
ถ้าเราเท่ากับที่เราจะทำอย่างไร
หากค่าที่เรากำลังพยายามที่จะแทรก จะมีค่าเท่ากับค่าของโหนดนี้
ใช่?
>> ผู้ชม: [ไม่ได้ยิน]
>> เจสัน Hirschorn: ใช่
ป.ร. ให้ไว้นี้ -
มาร์คัสที่ถูกต้อง
เราจะได้ทำอาจจะ บางสิ่งบางอย่างที่แตกต่างกัน
แต่รับว่าเราได้สร้างมันนี่ เราควรจะเป็นอิสระแล้วกลับ
Oh boy
ที่ดีขึ้นหรือไม่
วิธีการของที่?
ตกลง
ฟรีและแล้วสิ่งที่เราทำ กลับ [ไม่ได้ยิน]?
ตกลง
ที่เราขาดหายไปอะไร
ดังนั้นเราจึงมีการติดตามที่ ของโหนดก่อน?
>> ผู้ชม: ฉันคิดว่ามันจะไป หลังจากสร้างโหนดใหม่
>> เจสัน Hirschorn: OK
ดังนั้นจุดเริ่มต้นที่เราจะอาจ -
ใช่เราสามารถสร้างตัวชี้ไปยังใหม่ โหนดเช่นตัวชี้โหนดก่อนหน้านี้และ
ตัวชี้โหนดปัจจุบัน
จึงขอแทรกที่นี่
สร้างปัจจุบันและก่อนหน้า ตัวชี้ไปยังโหนด
แต่เมื่อเราปรับคำแนะนำเหล่านั้นหรือไม่
เราจะทำในกรณีที่ว่าในรหัส?
เจฟฟ์?
>> ผู้ชม: - เงื่อนไขค่า?
>> เจสัน Hirschorn: ไหน อย่างใดอย่างหนึ่งโดยเฉพาะอย่างยิ่ง?
>> ผู้ชม: ฉันสับสนเพียง
ถ้าค่ามากกว่าโหนดนี้ ไม่ได้หมายความว่าที่คุณต้องการไป
ไปยังโหนดต่อไปหรือไม่
>> เจสัน Hirschhorn: ดังนั้นถ้าค่าของเรา สูงกว่าค่าของโหนดนี้
>> ผู้ชม: ใช่แล้วคุณจะต้องการที่จะ ไปต่อสายลงใช่ไหม
>> เจสัน Hirschhorn ขวา
ดังนั้นเราจึงไม่ได้ใส่ที่นี่
ถ้าค่าน้อยกว่าโหนดนี้แล้ว เราไปโหนดถั​​ดไป - หรือแล้วเรา
ก่อนที่จะแทรก
>> ผู้ชม: รอที่เป็นแบบนี้ โหนดและซึ่งเป็นค่า?
>> เจสัน Hirschhorn: เป็นคำถามที่ดี
มูลค่าต่อความหมายของฟังก์ชั่นนี้ คือสิ่งที่เรากำลังได้รับ
ดังนั้นค่าคือจำนวนที่เราได้รับ
ดังนั้นถ้าค่าน้อยกว่านี้ โหนดที่เราต้องการเวลาในการใส่
ถ้าค่ามากกว่าโหนดนี้ เราไปโหนดถั​​ดไป
และกลับไปที่คำถามเดิม แม้ว่าที่ -
>> ผู้ชม: ถ้าค่าสูง กว่าโหนดนี้
>> เจสัน Hirschhorn: และดังนั้น สิ่งที่เราทำที่นี่?
หวาน
นั่นคือที่ถูกต้อง
ฉันแค่จะเขียน การปรับปรุงตัวชี้
แต่ใช่กับหนึ่งในปัจจุบัน คุณจะปรับปรุงให้
ชี้ไปที่หน้าหนึ่ง
สิ่งอื่นที่เรากำลังขาดหายไป
ดังนั้นฉันจะพิมพ์นี้ รหัสลง Gedit
และในขณะที่ผมทำเช่นนี้คุณสามารถมี นาทีที่สองมากขึ้นในการทำงานเกี่ยวกับการเขียนโปรแกรม
นี้ใน C.
>> ดังนั้นผมจึงมีการใส่ pseudocode
ทราบอย่างรวดเร็วก่อนที่เราจะเริ่มต้น
เราอาจจะไม่สามารถที่จะสมบูรณ์ เสร็จสิ้นในทุก
สามฟังก์ชั่นเหล่านี้
มีการแก้ปัญหาที่ถูกต้องให้แก่พวกเขาเป็น ที่ฉันจะส่งอีเมลออกไปพวกคุณ
หลังจากส่วนและมันจะ โพสต์ใน CS50.net
ดังนั้นผมจึงไม่ขอแนะนำให้คุณ ไปดูที่ส่วน
ผมขอแนะนำให้คุณลองเหล่านี้ด้วย เป็นเจ้าของและใช้การปฏิบัติ
ปัญหาในการตรวจสอบคำตอบของคุณ
เหล่านี้ได้รับการออกแบบมาอย่างใกล้ชิด และเกี่ยวข้องกับการยึดมั่นในสิ่งที่
ที่คุณต้องทำในการแก้ปัญหาที่กำหนด
ดังนั้นผมจึงขอแนะนำให้คุณปฏิบัตินี้ ด้วยตัวคุณเองแล้วใช้รหัสเพื่อ
ตรวจสอบคำตอบของคุณ
เพราะผมไม่ต้องการที่จะย้ายไปยังสับ ตารางในบางจุดในส่วน
ดังนั้นเราจึงอาจไม่ได้รับผ่านมันทั้งหมด
แต่เราจะทำมากที่สุดเท่าที่เราสามารถทำได้ในขณะนี้
>> ตกลง
ให้เราเริ่มต้น
Asam อย่างไรเราสร้างโหนดใหม่ได้หรือไม่
>> ผู้ชม: คุณ struct *
>> เจสัน Hirschhorn: ดังนั้นเราจึง มีที่มาที่นี่
โอ้ขอโทษ
คุณกำลังพูด struct *
>> ผู้ชม: แล้ว [? ชนิด?] โหนดหรือคโหนด
>> เจสัน Hirschhorn: OK
ฉันจะเรียกมันว่า new_node เพื่อให้เราสามารถอยู่สม่ำเสมอ
>> ผู้ชม: และคุณต้องการที่จะกำหนดว่า ที่จะมุ่งหน้าไปที่โหนดแรก
>> เจสัน Hirschhorn: OK
ดังนั้นตอนนี้ชี้นี้เพื่อ - เพื่อให้นี้ ยังไม่ได้สร้างโหนดใหม่ยัง
นี้เป็นเพียงการชี้ไปที่ โหนดแรกในรายการ
ฉันจะสร้างโหนดใหม่ได้อย่างไร
ถ้าผมต้องการพื้นที่ในการสร้างโหนดใหม่
malloc
และวิธีการใหญ่
>> ผู้ชม: ขนาดของ struct
>> เจสัน Hirschhorn: ขนาดของ struct
และสิ่งที่ struct เรียกว่า
>> ผู้ชม: โหนด?
>> เจสัน Hirschhorn: โหนด
ดังนั้น malloc (sizeof (โหนด)); ช่วยให้เรามีพื้นที่
และเป็นสายนี้ -
สิ่งหนึ่งที่ไม่ถูกต้องในสายนี้
เป็น new_node ตัวชี้ไปยัง struct?
นั่นเป็นชื่อสามัญ
มันคืออะไร -
โหนดว่า
มันเป็นโหนด *
และสิ่งที่เราจะทำทันทีหลังจากที่ เรา malloc สิ่ง Asan?
อะไรเป็นสิ่งแรกที่เราจะทำอย่างไร
ถ้ามันไม่ทำงาน
>> ผู้ชม: โอ้ตรวจสอบว่า ชี้ไปยังโหนด?
>> เจสัน Hirschhorn: แน่นอน
ดังนั้นหากคุณ new_node เท่ากับเท่ากับ null สิ่งที่เราจะทำอย่างไร
นี้จะคืนค่าบูลฟังก์ชั่นนี้
อย่างแน่นอน
ดูดี
อะไรเพิ่มมี
เราจะเพิ่มสิ่งที่สิ้นสุด
แต่จนถึงขณะนี้ดูดี
สร้างตัวชี้ปัจจุบันและก่อนหน้า
ไมเคิล, ฉันจะทำเช่นนี้?
>> ผู้ชม: คุณจะต้อง ที่จะทำโหนด *
คุณจะต้องทำอย่างใดอย่างหนึ่งไม่ได้ เพื่อ new_node แต่สำหรับ
โหนดเรามีอยู่แล้ว
>> เจสัน Hirschhorn: OK
ดังนั้นโหนดปัจจุบันเรากำลังอยู่ใน
ฉันจะเรียกว่า curr
ขวาทั้งหมด
เราได้ตัดสินใจที่เราต้องการที่จะเก็บ สองเพราะเราจำเป็นต้องรู้
สิ่งที่เป็นก่อนที่จะ
สิ่งที่พวกเขาได้รับการเริ่มต้นได้หรือไม่
>> ผู้ชม: ค่าของพวกเขาในรายการของเรา
>> เจสัน Hirschhorn: ดังนั้นสิ่งที่เป็น สิ่งแรกที่อยู่ในรายชื่อของเราหรือไม่
หรือวิธีที่เราจะทราบว่า จุดเริ่มต้นของรายการของเราคืออะไร
>> ผู้ชม: มันจะไม่ผ่าน ในการทำงานหรือไม่
>> เจสัน Hirschhorn ขวา
มันก็ผ่านไปในที่นี่
ดังนั้นถ้ามันผ่านเข้าไปในฟังก์ชั่น เริ่มต้นของรายการสิ่งที่เราควรทำ
การตั้งค่าปัจจุบันเท่ากับ?
>> ผู้ชม: รายชื่อ
>> เจสัน Hirschhorn: รายชื่อ
นั่นคือสิ่งที่ถูกต้อง
ตอนนี้มันมีที่อยู่ของ จุดเริ่มต้นของรายการของเรา
และสิ่งที่เกี่ยวกับก่อนหน้าหรือไม่
>> ผู้ชม: รายชื่อลบหรือไม่
>> เจสัน Hirschhorn: มี ก่อนที่จะไม่มีอะไร
ดังนั้นสิ่งที่เราสามารถทำได้เพื่อมีความหมายอะไร
>> ผู้ชม: Null
>> เจสัน Hirschhorn: ใช่
ที่เสียงเหมือนความคิดที่ดี
สมบูรณ์
ขอบคุณ
ผ่านรายการ
คอนสแตนติ, ระยะเวลาที่เราจะ ไปผ่านรายการหรือไม่
>> ผู้ชม: จนกว่าเราจะเข้าถึง null
>> เจสัน Hirschhorn: OK
ดังนั้นหากในขณะที่สำหรับวง
สิ่งที่เราจะทำอย่างไร
>> ผู้ชม: บางทีสำหรับวง?
>> เจสัน Hirschhorn: ขอทำสำหรับวง
ตกลง
>> ผู้ชม: และเราพูด -
จนกระทั่งตัวชี้ปัจจุบัน ไม่เท่ากับโมฆะ
>> เจสัน Hirschhorn: ดังนั้นถ้าเรารู้ เงื่อนไขวิธีการที่เราสามารถเขียนห่วง
ตามออกเงื่อนไขที่ว่า
ชนิดของวงที่เราควรจะใช้งานหรือไม่
>> ผู้ชม: ในขณะที่
>> เจสัน Hirschhorn: ใช่
ที่ทำให้ความรู้สึกมากขึ้น ออกจากสิ่งที่คุณกล่าวว่า
ถ้าเราเพียงแค่ต้องการที่จะไปลงเราก็จะ เพียงแค่รู้ว่าสิ่งที่มันจะทำให้
ความรู้สึกที่จะทำในขณะที่วง
ในขณะที่ปัจจุบันไม่ว่างไม่เท่ากัน ถ้าค่าน้อยกว่าโหนดนี้
Akshar ให้ฉันบรรทัดนี้
>> ผู้ชม: ถ้าปัจจุบัน> n n น้อยกว่าค่า
หรือย้อนกลับว่า
สลับวงเล็บว่า
>> เจสัน Hirschhorn: ขออภัย
>> ผู้ชม: เปลี่ยนวงเล็บ
>> เจสัน Hirschhorn: ดังนั้นถ้าหากมันเป็น มากกว่าค่า
เพราะที่ทำให้เกิดความสับสนกับ แสดงความคิดเห็นข้างต้นผมกำลังจะไปทำอย่างนั้น
แต่ใช่
ถ้าค่าของเราจะน้อยกว่านี้ โหนดสิ่งที่เราจะทำอย่างไร
โอ้
ฉันมีมันที่นี่
ก่อนที่จะใส่
ตกลง
เราจะทำอย่างไรที่
>> ผู้ชม: มันยังคงฉัน
>> เจสัน Hirschhorn: ใช่
>> ผู้ชม: คุณ -
new_node> ต่อไป
>> เจสัน Hirschhorn: ดังนั้นสิ่งที่ ที่จะเท่ากับ?
>> ผู้ชม: มันจะเท่ากับปัจจุบัน
>> เจสัน Hirschhorn: แน่นอน
และอื่น ๆ -
เราทำในสิ่งที่คนอื่นต้องการที่จะปรับปรุง?
>> ผู้ชม: ตรวจสอบว่าที่ผ่านมาเท่ากับโมฆะ
>> เจสัน Hirschhorn: ถ้าก่อนหน้า -
ดังนั้นถ้าก่อนหน้าเท่ากับโมฆะ
>> ผู้ชม: นั่นหมายความว่ามันจะ ที่จะเป็นหัวหน้า
>> เจสัน Hirschhorn: ซึ่งหมายความว่า มันกลายเป็นหัว
ดังนั้นแล้วสิ่งที่เราจะทำอย่างไร
>> ผู้ชม: เราทำหัวเท่ากับ new_node
>> เจสัน Hirschhorn หัวหน้า เท่ากับ new_node
และทำไมหัวนี่ไม่รายการ?
>> ผู้ชม: เพ​​ราะหัวเป็นทั่วโลก ตัวแปรซึ่งเป็นสถานที่เริ่มต้น
>> เจสัน Hirschhorn: หวาน
ตกลง
และ -
>> ผู้ชม: แล้วคุณอื่น prev> ต่อไปเท่ากับ new_node
แล้วคุณจะกลับจริง
>> เจสัน Hirschhorn: ที่ไหนทำ เราตั้งปลาย new_node?
>> ผู้ชม: ฉันจะ -
ฉันจะตั้งค่าว่าในช่วงเริ่มต้น
>> เจสัน Hirschhorn: ดังนั้นสิ่งที่บรรทัด
>> ผู้ชม: หลังจากที่ถ้ามีคำสั่ง การตรวจสอบว่าเป็นที่รู้จักกัน
>> เจสัน Hirschhorn: ที่นี่?
>> ผู้ชม: ฉันทำ new_node> n เท่ากับค่า
>> เจสัน Hirschhorn: เสียงดี
บางทีมันอาจจะทำให้รู้สึก - ที่เราทำไม่ได้ จำเป็นต้องรู้รายชื่อสิ่งที่เรากำลัง
เพราะเราเท่านั้นที่จัดการ กับรายการหนึ่ง
ดังนั้นการประกาศฟังก์ชันที่ดีกว่าสำหรับ นี้เป็นเพียงการกำจัดนี้
ทั้งหมดและใส่เพียง ค่าลงหัว
เราไม่จำเป็นต้องรู้ รายการสิ่งที่เรากำลังเข้า
แต่ผมจะให้มันตอนนี้และ แล้วเปลี่ยนกับการปรับปรุง
ภาพนิ่งและรหัส
เพื่อให้ดูดีสำหรับตอนนี้
ถ้าค่า - ที่สามารถทำสายนี้
ถ้า -
สิ่งที่เราทำที่นี่โนอาห์
>> ผู้ชม: ถ้าค่าสูง กว่า curr> n -
>> เจสัน Hirschhorn: วิธีทำ เราไปที่โหนดต่อไปหรือไม่
>> ผู้ชม: Curr> n คือ เท่ากับ new_node
>> เจสัน Hirschhorn: ดังนั้น n คือ สิ่งที่เป็นส่วนหนึ่งของโครงสร้างหรือไม่
จำนวนเต็ม
และ new_node เป็นตัวชี้ไปยังโหนด
ดังนั้นสิ่งที่เป็นส่วนหนึ่งของ curr เราควรปรับปรุง?
ถ้าไม่ได้ n แล้​​วสิ่งที่เป็นส่วนที่อื่น ๆ
โนอาห์เป็นสิ่งที่ส่วนอื่น ๆ
>> ผู้ชม: โอ้ต่อไป
>> เจสัน Hirschhorn: ต่อไปว่า
อย่างแน่นอน
ถัดไปเป็นหนึ่งที่เหมาะสม
และเราทำในสิ่งที่คนอื่นต้องการ เพื่ออัปเดตโนอาห์?
>> ผู้ชม: ตัวชี้
>> เจสัน Hirschhorn: ดังนั้น เราปรับปรุงในปัจจุบัน
>> ผู้ชม: ย้อนกลับ> ต่อไป
>> เจสัน Hirschhorn: ใช่
ตกลงเราจะหยุดการทำงานชั่วคราว
ที่สามารถช่วยให้เราออกจากที่นี่?
มนูสิ่งที่เราควรทำอย่างไร
>> ผู้ชม: คุณได้มีการตั้ง มันเท่ากับ curr> ต่อไป
แต่ก่อนที่จะทำเช่นนั้นบรรทัดก่อนหน้า
>> เจสัน Hirschhorn: OK
อะไรอีกหรือไม่
Akshar
>> ผู้ชม: ผมไม่คิดว่าคุณ หมายถึงการเปลี่ยน curr> ต่อไป
ฉันคิดว่าคุณหมายถึงการทำเท่ากับ curr curr> ถัดไปโหนดถั​​ดไป
>> เจสัน Hirschhorn: ขอโทษที่?
กับสิ่งที่บรรทัด
บรรทัดนี้?
>> ผู้ชม: ใช่
ทำให้ curr เท่ากับ curr> ต่อไป
>> เจสัน Hirschhorn: เพื่อให้เป็นที่ถูกต้อง เพราะปัจจุบัน
ตัวชี้ไปยังโหนด
และเราต้องการที่จะชี้ไปข้างหน้า โหนดของสิ่งที่ได้รับในปัจจุบัน
ชี้ไปที่
curr ตัวเองมีต่อไป
แต่ถ้าเรามีการปรับปรุง curr.next เรา จะได้รับการปรับปรุงการบันทึกที่เกิดขึ้นจริง
ตัวเองไม่ได้ที่นี้ ชี้ถูกชี้
สิ่งที่เกี่ยวกับสายนี้แม้ว่า
avi?
>> ผู้ชม: ย้อนกลับ> ต่อไปเท่ากับ curr
>> เจสัน Hirschhorn: ดังนั้นอีกครั้งถ้าก่อนหน้าเป็น ตัวชี้ไปยังโหนดก่อนหน้า> ต่อไปคือ
ตัวชี้ที่เกิดขึ้นจริงในโหนด
ดังนั้นนี้จะได้รับการปรับปรุง ตัวชี้ในโหนด curr
เราไม่ต้องการที่จะปรับปรุง ตัวชี้ในโหนด
เราต้องการที่จะปรับปรุงแล้ว
ดังนั้นทำอย่างไรเราทำอย่างนั้น
>> ผู้ชม: มันก็จะย้อนกลับ
>> เจสัน Hirschhorn ขวา
ย้อนกลับเป็นตัวชี้ไปยังโหนด
ตอนนี้เรากำลังเปลี่ยนไป ตัวชี้ไปยังโหนดใหม่
ตกลงขอให้เราย้ายลง
ในที่สุดสภาพที่ผ่านมานี้
เจฟฟ์สิ่งที่เราทำที่นี่?
>> ผู้ชม: ถ้าค่าเป็น เท่ากับ curr> n
>> เจสัน Hirschhorn: ขออภัย
โอ้ความดีของฉัน
คืออะไร?
ค่า curr ==> n
สิ่งใดที่เราจะทำอย่างไร
>> ผู้ชม: คุณจะเป็นอิสระ new_node ของเรา และแล้วคุณจะกลับเท็จ
>> เจสัน Hirschhorn: นี่คือสิ่งที่ เราได้เขียนเพื่อให้ห่างไกล
ไม่มีใครมีอะไร เพื่อเพิ่มก่อนที่เราจะทำ?
ตกลง
ลองมัน
การควบคุมอาจจะถึงจุดสิ้นสุด ของฟังก์ชั่นที่ไม่เป็นโมฆะ
avi, สิ่งที่เกิดขึ้น?
>> ผู้ชม: คุณควรที่จะนำกลับมา จริงนอกวงในขณะที่?
>> เจสัน Hirschhorn: ผมไม่ทราบว่า
คุณต้องการให้ฉันไป?
>> ผู้ชม: ไม่เป็นไร
เลขที่
>> เจสัน Hirschhorn: Akshar?
>> ผู้ชม: ฉันคิดว่าคุณหมายถึง ใส่กลับเท็จที่สิ้นสุด
ของวงในขณะที่
>> เจสัน Hirschhorn: ดังนั้นที่ ที่คุณต้องการจะไปที่ไหน
>> ผู้ชม: เช่นเดียวกับที่อยู่นอกวงในขณะที่
ดังนั้นหากคุณออกจากวงในขณะที่หมายถึง ที่คุณได้มาถึงที่สิ้นสุดและ
ไม่มีอะไรเกิดขึ้น
>> เจสัน Hirschhorn: OK
ดังนั้นสิ่งที่เราจะทำในที่นี่
>> ผู้ชม: คุณกลับเท็จ มีทั้ง
>> เจสัน Hirschhorn: โอ้เรา ทำในสถานที่ที่ทั้งสอง
>> ผู้ชม: ใช่
>> เจสัน Hirschhorn: OK
เราควรจะไป?
โอ้ความดีของฉัน
ฉันขอโทษ
ฉันขอโทษสำหรับหน้าจอ
มันเป็นชนิดของออกซเรา
เพื่อเลือกตัวเลือก
ศูนย์ต่อรหัสหยุดโปรแกรม
หนึ่งในสิ่งที่แทรก
ขอแทรกสาม
แทรกไม่ประสบความสำเร็จ
ฉันจะพิมพ์ออกมา
ผมไม่ได้มีอะไร
ตกลง
บางทีนี่อาจจะเป็นเพียงความบังเอิญ
ใส่อย่างใดอย่างหนึ่ง
ไม่ประสบความสำเร็จ
ตกลง
ขอทำงานผ่าน GDB อย่างรวดเร็วจริงๆ เพื่อตรวจสอบสิ่งที่เกิดขึ้น
>> จำ gdb. / ชื่อของคุณ โปรแกรมที่เราได้รับใน GDB
เป็นที่มากที่จะจัดการกับ?
กระพริบ
อาจ
ปิดตาของคุณและใช้เวลาบางลึก หายใจถ้าคุณได้รับเหนื่อย
การมองไปที่มัน
ฉันอยู่ใน GDB
อะไรเป็นสิ่งแรกที่ฉันทำใน GDB?
เรามีที่จะคิดออก สิ่งที่เกิดขึ้นที่นี่
ลองมาดูกัน
เรามีหกนาทีตัวเลข สิ่งที่เกิดขึ้น
ทำลายหลัก
และแล้วสิ่งที่ฉันจะทำอย่างไร
คาร์ลอ?
วิ่ง
ตกลง
ให้เลือกตัวเลือก
และสิ่งที่ไม่ยังไม่มีจะทำอย่างไร
ต่อไป
ใช่
>> ผู้ชม: คุณไม่พูดถึง -
ไม่ได้คุณบอกว่าหัวก็คือ เริ่มต้นให้เป็นโมฆะที่จุดเริ่มต้น
แต่ผมคิดว่าคุณบอกว่าตกลง
>> เจสัน Hirschhorn: ไป - ให้ดู ใน GDB แล้วเราจะกลับไป
แต่ดูเหมือนคุณมีอยู่แล้ว ความคิดบางอย่างเกี่ยวกับสิ่งที่เกิดขึ้น
ดังนั้นเราจึงต้องการที่จะใส่บางสิ่งบางอย่าง
ตกลง
เราได้ใส่
กรุณาใส่ int
เราจะใส่สาม
และแล้วผมในบรรทัดนี้
ฉันจะไปวิธีเริ่มแก้จุดบกพร่อง แทรกที่รู้จักกันฟังก์ชั่ทำไม
โอ้ความดีของฉัน
นั่นเป็นจำนวนมาก
เป็นที่ประหลาดออกมามากหรือไม่
>> ผู้ชม: โอ้มันตาย
>> เจสัน Hirschhorn: ฉันเพียงแค่ ดึงมันออก
ตกลง
>> ผู้ชม: อาจจะเป็น ปลายอีกด้านของสาย
>> เจสัน Hirschhorn: ว้าว
ดังนั้นบรรทัดด้านล่าง -
สิ่งที่คุณพูด
>> ผู้ชม: ผมพูดประชดของเทคนิค ความยากลำบากในชั้นนี้
>> เจสัน Hirschhorn: ฉันรู้ว่า
ถ้าเพียง แต่ฉันมีการควบคุมที่เป็นส่วนหนึ่ง
[ไม่ได้ยิน]
ที่เสียงดี
ทำไมพวกคุณไม่ได้เริ่มคิดเกี่ยวกับ สิ่งที่เราจะได้ทำผิด
และเราจะกลับมาอยู่ใน 90 วินาที
>> Avica, ฉันจะถามคุณว่าจะไป ภายใน insert_node จะแก้ปัญหาได้
ดังนั้นนี่คือที่ที่เราสุดท้ายที่เหลืออยู่ออก
ฉันจะไปภายใน insert_node วิธี Avica, เพื่อตรวจสอบสิ่งที่เกิดขึ้น?
สิ่งที่คำสั่ง GDB?
วันหยุดจะไม่พาฉันภายใน
ไม่ Marquise รู้
>> ผู้ชม: อะไร
>> เจสัน Hirschhorn: อะไร GDB คำสั่ง ผมใช้ไปภายในฟังก์ชั่นนี้
>> ผู้ชม: ขั้นตอน?
>> เจสัน Hirschhorn: ขั้นตอนที่ผ่าน เอสที่ใช้เวลาฉันภายใน
ตกลง
new_node mallocing พื้นที่บางส่วน
ลักษณะที่ทุกคนชอบไปของ
ขอตรวจสอบ new_node
มันมีอยู่หน่วยความจำบางส่วน
ขอตรวจสอบ -
ที่ถูกต้องทั้งหมด
ดังนั้นทุกอย่างที่นี่น่าจะ จะทำงานได้อย่างถูกต้อง
>> ผู้ชม: อะไรคือความแตกต่าง ระหว่าง P และแสดง?
>> เจสัน Hirschhorn: P ย่อมาจากการพิมพ์
และเพื่อให้คุณกำลังขอให้สิ่งที่เป็น ความแตกต่างระหว่างที่และนี้
ในกรณีนี้ไม่มีอะไร
แต่โดยทั่วไปมี ความแตกต่างบาง
และคุณควรจะดูในคู่มือการ GDB
แต่ในกรณีนี้ไม่มีอะไร
เรามักจะใช้ในการพิมพ์ แต่เนื่องจาก เราไม่ต้องทำอะไรมากไปกว่า
พิมพ์ค่าเดียว
>> ตกลง
ดังนั้นเราอยู่ในสาย 80 จากรหัสของเรา การตั้งค่าโหนด * curr เท่ากับรายการ
ให้เราพิมพ์ออกมา curr
มันเท่ากับรายการ
หวาน
รอ
มันเท่ากับสิ่งที่
ที่ดูเหมือนจะไม่เหมาะสม
มีเราไป
ก็เพราะใน GDB ขวาถ้า มันเส้นที่คุณกำลังจะ
ยังไม่ได้ดำเนินการยัง
ดังนั้นคุณจะต้องพิมพ์จริง ต่อไปที่จะดำเนินการสาย
ก่อนที่จะเห็นผลของมัน
ดังนั้นที่นี่เรามี
เราก็ดำเนินการบรรทัดนี้ หน้าที่เท่ากับโมฆะ
ดังนั้นอีกครั้งถ้าเราพิมพ์แล้ว เราจะไม่เห็นอะไรแปลก
แต่ถ้าเราจะดำเนินการที่ สายแล้วเราจะเห็น
ว่าสายที่ทำงาน
>> ดังนั้นเราจึงมี curr
ผู้ที่มีทั้งดี
ใช่มั้ย?
ตอนนี้เราอยู่ในสายนี้ที่นี่
ในขณะที่ curr ไม่โมฆะเท่ากับ
ดีสิ่งที่ไม่ curr เท่ากัน
เราก็เห็นว่ามันเท่ากับโมฆะ
เราพิมพ์มันออกมา
ฉันจะพิมพ์ออกมาอีกครั้ง
ดังนั้นคือในขณะที่วง จะรัน
>> ผู้ชม: เลขที่
>> เจสัน Hirschhorn: ดังนั้นเมื่อผมพิมพ์ว่า สายคุณจะเห็นเราเพิ่มขึ้นทุกทาง
ลงไปที่ด้านล่างกลับเท็จ
แล้วเรากำลังจะกลับเท็จ และกลับไปยังโปรแกรมของเราและ
ในที่สุดก็จะพิมพ์ออกมาเหมือนอย่างที่เราเห็น แทรกไม่ประสบความสำเร็จ
ดังนั้นใครมีความคิดใด ๆ กับสิ่งที่ เราต้องทำเพื่อแก้ไขปัญหานี้
ฉันจะรอจนกว่าฉันเห็น สองมือขึ้นไป
เราไม่ได้ดำเนินการนี​​้
เก็บไว้ในใจนี้เป็นครั้งแรกที่ สิ่งที่เรากำลังทำ
ฉันไม่ได้จะทำคู่
ฉันจะทำไม่กี่
เพราะคู่หมายถึงสอง
ฉันจะรอนานกว่าสอง
>> แทรกแรก curr, โดยค่าเริ่มต้นเท่ากับโมฆะ
และห่วงนี้จะดำเนินการ ถ้า curr ไม่โมฆะ
ดังนั้นวิธีการที่ฉันจะได้รับรอบนี้
ผมเห็นสามมือ
ฉันจะรอนานกว่าสาม
มาร์คัสสิ่งที่คุณคิดว่า
>> ผู้ชม: ดีถ้าคุณต้องการให้ ดำเนินการมากกว่าหนึ่งครั้งคุณก็
เปลี่ยนเป็นห่วงในขณะที่ทำ
>> เจสัน Hirschhorn: OK
ที่จะแก้ปัญหาของเรา แต่?
>> ผู้ชม: ในกรณีนี้ไม่มีเพราะ ความจริงที่ว่ารายการเป็นที่ว่างเปล่า
ดังนั้นแล้วคุณอาจจะเพียงแค่ต้องเพิ่ม คำสั่งว่าถ้าออกจากวง
แล้วคุณจะต้องเป็นที่สิ้นสุดของ รายการที่จุดที่คุณ
ก็สามารถใส่
>> เจสัน Hirschhorn: ฉันชอบที่
ที่ทำให้รู้สึก
ถ้าวงออก -
เพราะมันจะกลับเท็จที่นี่
ดังนั้นหากออกจากวงแล้วเราอยู่ที่ ในตอนท้ายของรายการหรืออาจจะ
เริ่มต้นของรายการถ้ามีอะไรใน มันซึ่งเป็นเช่นเดียวกับในตอนท้าย
ดังนั้นตอนนี้เราต้องการที่จะแทรก บางสิ่งบางอย่างที่นี่
ดังนั้นวิธีที่จะดูรหัสที่มาร์คัส?
>> ผู้ชม: หากคุณมีอยู่แล้วโหนด malloced คุณก็อาจจะบอกว่า
new_node> ต่อไปเท่ากับโมฆะเพราะ ว่ามันจะเป็นที่สิ้นสุดมี
หรือ new_node> ต่อไปเท่ากับโมฆะ
>> เจสัน Hirschhorn: OK
ขอโทษ
new_node> ต่อไปเท่ากับโมฆะ เพราะเราอยู่ที่ปลาย
ที่ไม่ได้วางระบบ
เราจะวางไว้ในรายการหรือไม่
ขวา
นั่นเป็นเพียงการตั้งค่าเท่ากับ
ไม่ว่าเราจะเป็นจริง ใส่ไว้ในรายการหรือไม่
สิ่งที่ชี้ไปที่ ในตอนท้ายของรายการหรือไม่
>> ผู้ชม: หัวหน้า
>> เจสัน Hirschhorn: ขอโทษ?
>> ผู้ชม: หัวหน้าชี้ ที่ส่วนท้ายของรายการ
>> เจสัน Hirschhorn: ถ้าไม่มีอะไรใน รายการหัวจะชี้ไปที่
ตอนท้ายของรายการ
เพื่อที่จะทำงานให้ แทรกแรก
สิ่งที่เกี่ยวกับถ้ามีคู่ สิ่งที่อยู่ในรายการหรือไม่
กว่าที่เราไม่ต้องการที่จะตั้ง หัวเท่ากับ new_node
สิ่งที่เราต้องการจะทำมี
ใช่?
แล้วน่าจะเป็น
ที่จะทำงานอย่างไร
จำได้ว่าก่อนหน้านี้เพียง ตัวชี้ไปยังโหนด
และก่อนหน้านี้เป็นตัวแปรท้องถิ่น
ดังนั้นสายนี้จะกำหนดตัวแปรท้องถิ่น ก่อนหน้านี้เท่ากับหรือ
ชี้ไปที่โหนดใหม่นี้
ที่จะไม่จริงใส่มัน ในรายการของเราว่า
เราจะวางไว้ในรายการของเราหรือไม่
Akchar?
>> ผู้ชม: ฉันคิดว่าคุณ ทำปัจจุบัน> ต่อไป
>> เจสัน Hirschhorn: OK
curr> ต่อไป
ดังนั้นอีกครั้งเหตุผลเดียวที่เรากำลังลง นี่คือสิ่งที่ไม่เท่ากันในปัจจุบัน?
>> ผู้ชม: null เท่ากับ
>> เจสัน Hirschhorn: และดังนั้นสิ่งที่ เกิดอะไรขึ้นถ้าเราทำโมฆะ> ต่อไปหรือไม่
สิ่งที่เราจะได้รับ
เราจะได้รับความผิดส่วน
>> ผู้ชม: ทำ curr เท่ากับโมฆะ
>> เจสัน Hirschhorn: นั่นเป็นสิ่งเดียวกัน เช่นก่อนหน้า แต่เนื่องจากมี
ตัวแปรท้องถิ่นที่เรากำลังตั้งค่า เท่ากับโหนดใหม่นี้
ให้กลับไปที่ภาพของเรา การแทรกบางสิ่งบางอย่าง
บอกว่าเรากำลังใส่ที่ปลาย ของรายชื่อเพื่อให้ที่นี่
เรามีตัวชี้ปัจจุบันที่ ชี้เป็นโมฆะและจุดก่อนหน้า
ที่ชี้ไปที่ 8
ดังนั้นเราจึงทำในสิ่งที่จำเป็นต้องปรับปรุง, Avi?
>> AUDIENCE: ก่อนหน้านี้> ต่อไปหรือไม่
>> เจสัน Hirschhorn: ก่อนหน้านี้> ต่อไปคือสิ่งที่ เราต้องการที่จะปรับปรุงเพราะที่
จริงจะใส่ที่ ตอนท้ายของรายการ
เรายังมีข้อผิดพลาดอย่างใดอย่างหนึ่ง แต่ ที่เรากำลังจะวิ่งเข้ามาใน
สิ่งที่ผิดพลาดที่
ใช่?
>> ผู้ชม: มันจะกลับมา เท็จในกรณีนี้
>> เจสัน Hirschhorn: โอ้เป็นถูก จะกลับเท็จ
แต่มีข้อผิดพลาดอีก
ดังนั้นเราจะต้องใส่ในการกลับมาเป็นความจริง
>> ผู้ชม: ไม่มีแล้วยังคงเท่ากับ null ที่ด้านบนของรายการหรือไม่
>> เจสัน Hirschhorn: ยังคงดังนั้นหน้าที่แล้ว เท่ากับ null ที่จุดเริ่มต้นมาก
ดังนั้นวิธีที่เราจะได้รับมากกว่านั้น
ใช่?
>> ผู้ชม: ฉันคิดว่าคุณสามารถจะตรวจสอบ ก่อนที่จะห่วงในขณะที่เพื่อดูว่ามันเป็น
รายการว่างเปล่า
>> เจสัน Hirschhorn: OK
จึงขอไปที่นี่
ดำเนินการตรวจสอบ
ถ้า -
>> ผู้ชม: ดังนั้นถ้าหัว เท่ากับเท่ากับโมฆะ
>> เจสัน Hirschhorn: ถ้าหัว เท่ากับเท่ากับ null -
ที่จะบอกเราว่ามันเป็นรายการที่ว่างเปล่า
>> ผู้ชม: แล้วคุณ ไม่เท่ากับหัวใหม่
>> เจสัน Hirschhorn หัวหน้า เท่ากับ new_node?
และเราทำในสิ่งที่คนอื่นต้องทำอย่างไร
>> ผู้ชม: แล้วคุณจะกลับจริง
>> เจสัน Hirschhorn: ไม่เชิง
เรากำลังขาดหายไปหนึ่งขั้นตอน
>> ผู้ชม: new_node ต่อไป มีการชี้ไปที่เป็นโมฆะ
>> เจสัน Hirschhorn: แน่นอน, Alden
และแล้วเราสามารถกลับจริง
ตกลง
แต่ก็ยังคงเป็นความคิดที่ดีที่จะทำสิ่ง ที่ส่วนท้ายของรายการใช่ไหม
ขวาทั้งหมด
เรายังอาจได้รับจริง ที่ส่วนท้ายของรายการ
ดังนั้นจะปรับรหัสนี้ถ้าเราอยู่ที่ ท้ายของรายการและมีบางส่วน
สิ่งที่อยู่ในรายการหรือไม่
ใช่มั้ย?
เพราะเรายังมีความคิดที่มาร์คัส
เราอาจจะออกจากวงนี้เพราะ เราอยู่ที่จุดสิ้นสุดของรายการ
ดังนั้นเรายังคงอยากให้เรื่องนี้ รหัสลงที่นี่?
>> ผู้ชม: ใช่
>> เจสัน Hirschhorn: ใช่
และเราทำในสิ่งที่จำเป็นต้องเปลี่ยนแปลงนี้หรือไม่
จริง
ไม่ว่าเสียงดี ทุกคนเพื่อให้ห่างไกล
ใครมีใด ๆ -
avi, คุณมีสิ่งที่จะเพิ่ม?
>> ผู้ชม: เลขที่
>> เจสัน Hirschhorn: OK
ดังนั้นเราจึงได้ทำคู่ของการเปลี่ยนแปลง
เราได้ทำให้การตรวจสอบนี้ก่อนที่เราจะ ไปในรายการว่างเปล่า
ดังนั้นเราจึงได้รับการดูแลรายการที่ว่างเปล่า
และที่นี่เราเอาดูแลของการใส่ บางสิ่งบางอย่างที่ส่วนท้ายของรายการ
ดังนั้นดูเหมือนว่าเช่นนี้การห่วงขณะ ดูแลสิ่งในระหว่าง
ที่ใดที่หนึ่งในรายการถ้ามี เป็นสิ่งที่อยู่ในรายการ
>> ตกลง
ให้เราเรียกใช้โปรแกรมนี้อีกครั้ง
ไม่ประสบความสำเร็จ
>> ผู้ชม: คุณไม่ได้ทำให้มัน
>> เจสัน Hirschhorn: โอ้ ผมไม่ได้ทำมัน
จุดดีของไมเคิล
ขอเพิ่มทำให้การเชื่อมโยง
สาย 87 มีข้อผิดพลาด
สาย 87
Alden นี้เป็นสายที่คุณให้ฉัน
เกิดอะไรขึ้น
>> ผู้ชม: มันจะต้องเป็นโมฆะได้
>> เจสัน Hirschhorn: ยอดเยี่ยม
ขวาตรง
มันควรจะเป็นโมฆะ
ขอให้อีกครั้ง
คอมไพล์
ตกลง
ขอแทรกสาม
แทรกก็ประสบความสำเร็จ
ลองพิมพ์ออกมา
โอ้ถ้าเพียง แต่เราสามารถตรวจสอบ
แต่เรายังไม่ได้ทำ ฟังก์ชั่นการพิมพ์ยัง
ลองป้อนอย่างอื่น
สิ่งที่เราควรจะใส่?
>> ผู้ชม: เซเว่น
>> เจสัน Hirschhorn: เซเว่น?
>> ผู้ชม: ใช่
>> เจสัน Hirschhorn: เรามีความผิด seg ของ
ดังนั้นเราจึงมีหนึ่ง แต่เราได้อย่างชัดเจน ไม่สามารถได้รับสอง
มันเป็น 05:07
เพื่อให้เราสามารถแก้ปัญหานี้ เป็นเวลาสามนาที
แต่ฉันจะปล่อยให้เราที่นี่ และไปยังสับตาราง
แต่อีกครั้งคำตอบสำหรับรหัสนี้ ฉันจะส่งอีเมลถึงคุณในบิต
เรามีความใกล้เคียงกับมัน
ผมขอแนะนำให้คุณที่จะคิดออก สิ่งที่เกิดขึ้นที่นี่และแก้ไขได้
ดังนั้นฉันจะส่งอีเมลถึงคุณรหัสนี้เป็น ดีบวกการแก้ปัญหา -
อาจจะแก้ปัญหาในภายหลัง
รหัสนี้เป็นครั้งแรก
>> สิ่งอื่น ๆ ที่ฉันต้องการจะทำก่อนที่เราจะ จบเราไม่ได้ปลดปล่อยอะไร
ดังนั้นผมจึงต้องการที่จะแสดงให้คุณเห็นสิ่งที่ valgrind ดูเหมือนว่า
ถ้าเราทำงานขอบเขต valgrind ในโปรแกรมของเรา. / เชื่อมโยง
อีกครั้งตามที่สไลด์นี้เรา ควรใช้ valgrind กับชนิดของบางอย่าง
ตัวเลือกในกรณีนี้ - ตรวจสอบการรั่วไหล = เต็ม
จึงขอเขียน valgrind - ตรวจสอบการรั่วไหล = เต็ม
ดังนั้นนี้จะทำงาน valgrind ในโปรแกรมของเรา
และตอนนี้โปรแกรมจริงทำงาน
ดังนั้นเราจะใช้มันเช่นเดียวกับ ก่อนที่จะใส่บางสิ่งบางอย่างค่ะ
ฉันจะใส่ในสาม
ที่ทำงาน
ฉันไม่ได้จะพยายามที่จะวางในบางสิ่งบางอย่าง อื่นเพราะเรากำลังจะ
ได้รับเท็จ จ. ในกรณีที่
ดังนั้นฉันแค่ไปที่จะออกจาก
>> และตอนนี้ที่คุณเห็นลงที่นี่ รั่วและกองสรุป
เหล่านี้เป็นสิ่งที่ดีที่ คุณต้องการที่จะตรวจสอบ
ดังนั้นสรุปกอง - มันกล่าวว่าในการใช้งาน ที่ทางออก - แปดไบต์ในหนึ่งบล็อก
นั่นเป็นหนึ่งบล็อก โหนดเรา malloced
ไมเคิล, คุณกล่าวว่าก่อนที่จะโหนดเป็นแปด กัดเพราะมีจำนวนเต็ม
และตัวชี้
เพื่อให้เป็นโหนดของเรา
แล้วก็บอกว่าเราใช้ malloc เจ็ดครั้งและเราปล่อยให้เป็นอิสระ
สิ่งที่หกครั้ง
แต่เราไม่เคยเรียกฟรีดังนั้นผมไม่มี ความคิดว่านี้คือการพูดคุยเกี่ยวกับ
>> แต่พอมันจะบอกว่าเมื่อคุณ โปรแกรมวิ่ง malloc จะถูกเรียกว่า
ในบางสถานที่อื่น ๆ ที่เรา ไม่จำเป็นต้องกังวลเกี่ยวกับ
ดังนั้น malloc อาจจะถูกเรียกว่า ในบางสถานที่
เราไม่จำเป็นต้องกังวลที่
แต่นี้เป็นจริงเรา
บรรทัดแรกนี้เป็นเรา
เราออกจากบล็อกที่
และคุณจะเห็นว่าที่นี่ ในการสรุปการรั่วไหล
ยังคงสามารถเข้าถึงได้ -
แปดไบต์ในหนึ่งบล็อก
นั่นหมายถึงหน่วยความจำที่ -
เราได้รั่วไหลออกมาว่าหน่วยความจำ
หายไปแน่นอน -
สิ่งที่หายไปให้ดี
โดยทั่วไปแล้วคุณจะไม่ เห็นอะไรที่มี
ยังคงสามารถเข้าถึงได้โดยทั่วไปที่ คุณจะเห็นสิ่งที่คุณจะต้องการ
มองไปเห็นสิ่งที่คุณควรจะรหัส มีอิสระ แต่คุณลืมที่จะฟรี
>> แล้วถ้าเรื่องนี้ไม่ได้เป็นกรณีที่ ถ้าเราทำทุกอย่างฟรี
เราสามารถตรวจสอบว่า
ขอเพียงรันโปรแกรม ไม่ได้ใส่อะไร
คุณจะเห็นลงมาที่นี่ในการใช้งานที่ออก -
ศูนย์ศูนย์ไบต์ในบล็อก
นั่นหมายความว่าเรามีอะไรเหลือ เมื่อโปรแกรมนี้ออก
ดังนั้นก่อนที่จะเปิดใน pset6 เรียกใช้ valgrind และให้แน่ใจว่าคุณไม่ได้มี
หน่วยความจำที่รั่วไหลในโปรแกรมของคุณ
หากคุณมีคำถามใด ๆ กับ valgrind, อย่าลังเลที่จะเอื้อมมือออก
แต่นี้เป็นวิธีการที่คุณใช้มัน
ง่ายมาก - ดูว่าคุณ มีในการใช้งานที่ออก -
ไบต์ในบล็อกใด ๆ
>> ดังนั้นเราจึงมีการทำงานเกี่ยวกับการแทรกโหนด
ฉันมีสองฟังก์ชั่นอื่น ๆ ที่นี่ - พิมพ์โหนดและโหนดฟรี
อีกครั้งเหล่านี้เป็นฟังก์ชั่นที่มี จะเป็นที่ดีสำหรับคุณที่จะปฏิบัติ
เพราะพวกเขาจะช่วยให้คุณไม่เพียง แต่มี การออกกำลังกายเหล่านี้ตัวอย่าง แต่ยัง
ในการแก้ปัญหาที่กำหนด
พวกเขาแผนที่สวยอย่างใกล้ชิดกับสิ่งที่ คุณจะต้องทำใน
ชุดปัญหา
แต่ฉันต้องการให้แน่ใจว่า เราสัมผัสในทุกสิ่ง
และตารางแฮชนอกจากนี้ยังมีความสำคัญต่อการ สิ่งที่เราทำในส่วนนี้
สัปดาห์ - หรือปัญหาในการตั้งค่า
>> ดังนั้นเรากำลังจะเสร็จสิ้นส่วน พูดคุยเกี่ยวกับตารางแฮช
ถ้าคุณสังเกตเห็นฉันทำ ตารางแฮชน้อย
นั่นไม่ใช่สิ่งที่เรากำลังพูดถึง เกี่ยวกับการ แต่
เรากำลังพูดถึงเกี่ยวกับการที่แตกต่างกัน ประเภทของตารางแฮช
และที่หลักของตารางแฮช คืออะไรมากกว่า
อาร์เรย์บวกฟังก์ชันแฮช
เรากำลังจะไปพูดคุยสำหรับบิตเพียงเพื่อ ให้แน่ใจว่าทุกคนเข้าใจสิ่งที่
ฟังก์ชันแฮชเป็น
และฉันบอกคุณตอนนี้ว่ามันเป็น ไม่มีอะไรมากไปกว่าสองสิ่ง -
อาร์เรย์และฟังก์ชันแฮช
และที่นี่เป็นขั้นตอนผ่าน ซึ่งนี้ทำงาน
>> มีอาเรย์ของเรา
มีฟังก์ชั่นของเรา
โดยเฉพาะอย่างยิ่งฟังก์ชันแฮชต้อง ทำสองสิ่งนี้
ฉันจะพูดคุยเฉพาะ เกี่ยวกับปัญหาการตั้งค่านี้
มันอาจจะ ใช้เวลาในสตริง
และสิ่งที่มันจะกลับมา?
ชนิดข้อมูล
Alden?
ฟังก์ชันแฮชของคุณกลับมา?
จำนวนเต็ม
ดังนั้นนี่คือสิ่งกัญชา ตารางประกอบด้วย -
ตารางในรูปแบบของอาร์เรย์ และฟังก์ชันแฮช
มันทำงานอย่างไร
มันทำงานในสามขั้นตอน
เราให้มันสำคัญ
ในกรณีนี้เราจะให้มันสตริง
เราเรียกฟังก์ชันแฮชต่อขั้นตอนเดียว ที่สำคัญและเราได้รับค่า
>> โดยเฉพาะเราจะบอกว่า เราได้รับจำนวนเต็ม
เลขที่มีที่เฉพาะเจาะจงมาก ข้อ จำกัด กับสิ่งจำนวนเต็มที่สามารถ
ในตัวอย่างนี้อาร์เรย์ของเรา มีขนาดสาม
ดังนั้นสิ่งที่ตัวเลขจำนวนเต็มที่สามารถ
คือช่วงของค่าที่ถูกต้องสำหรับสิ่งที่ เลขที่ประเภทนี้การกลับมาของ
สับฟังก์ชั่ทำไม
ศูนย์หนึ่งและสอง
จุดของฟังก์ชันแฮชคือการ คิดออกสถานที่ในอาร์เรย์
ที่สำคัญของเราเป็นไป
มีเพียงสามที่เป็นไปได้ สถานที่อยู่ที่นี่ -
ศูนย์หนึ่งหรือสอง
ดังนั้นฟังก์ชั่นที่ดีกว่านี้กลับ ศูนย์หนึ่งหรือสอง
บาง indice ถูกต้องในอาร์เรย์นี้
>> และจากนั้นก็ขึ้นอยู่กับที่มันกลับมา คุณสามารถดูมีอาร์เรย์เปิด
ยึดค่า
นั่นคือสิ่งที่เราใส่กุญแจ
ดังนั้นเราจึงโยนในฟักทอง เราได้รับการออกเป็นศูนย์
ที่อาร์เรย์วงเล็บ 0 เราใส่ฟักทอง
เราโยนในแมวที่เราได้รับอย่างใดอย่างหนึ่งออกมา
เราใส่แมวที่หนึ่ง
เราใส่ในเดอร์
เราได้รับการออกสอง
เราใส่แมงมุมที่อาร์เรย์วงเล็บสอง
มันจะดีดังนั้นหาก มันทำงานเหมือนที่
แต่น่าเสียดายที่ในขณะที่เราจะเห็น มันเป็นบิตที่ซับซ้อนมากขึ้น
>> ก่อนที่เราจะมีคำถามใด ๆ เกี่ยวกับขั้นพื้นฐานนี้
การตั้งค่าของตารางแฮช?
นี้เป็นภาพของว่า สิ่งที่เราเข้ามาอยู่ในคณะกรรมการ
แต่เนื่องจากเราดึงมันขึ้นมาบนเรือผม ฉันจะไม่ไปลงมันต่อไป
คีย์หลักกล่องดำมายากล - หรือในกรณีนี้กล่องนกเป็ดน้ำ - ของ
ฟังก์ชันแฮชทำให้พวกเขาในถัง
และในตัวอย่างนี้เรา ไม่ได้ใส่ชื่อ
เรากำลังวางโทรศัพท์ที่เกี่ยวข้อง จำนวนของชื่อในถัง
แต่คุณได้เป็นอย่างดีเพียงแค่ ใส่ชื่อในถัง
>> นี่เป็นเพียงภาพของสิ่งที่ เราเข้ามาอยู่ในคณะกรรมการ
เรามีข้อผิดพลาดที่อาจเกิดขึ้นแม้ว่า
และมีสองโดยเฉพาะอย่างยิ่ง สไลด์ที่ฉันต้องการจะไปกว่า
คนแรกคือเกี่ยวกับ ฟังก์ชันแฮช
ดังนั้นผมจึงถามคำถามที่ว่า ทำให้ฟังก์ชันแฮชที่ดี
ฉันให้สองคำตอบ
แรกคือว่ามันเป็นที่กำหนด
ในบริบทของฟังก์ชันแฮช, สิ่งนี้หมายความว่าอย่างไร
ใช่?
>> ผู้ชม: มันสามารถหา ดัชนีในเวลาคงที่?
>> เจสัน Hirschhorn: นั่น ไม่ได้เป็นสิ่งที่มันหมายถึง
แต่ที่คาดเดาที่ดี
คนอื่นมีการคาดเดา กับสิ่งที่นี้หมายถึง
ฟังก์ชันแฮชที่ดี คือกำหนด?
แอนนี่?
>> ผู้ชม: ที่สำคัญสามารถแมปเพียง ไปยังสถานที่หนึ่งในตารางแฮช
>> เจสัน Hirschhorn: นั่น ตรงขวา
ทุกครั้งที่คุณใส่ในฟักทอง มันจะได้ค่าเป็นศูนย์
หากคุณใส่ในฟักทองและกัญชาของคุณ ฟังก์ชันส่งกลับเป็นศูนย์ แต่มี
น่าจะเป็นของบางสิ่งบางอย่างกลับมา อื่นมากกว่าศูนย์ -
ดังนั้นอาจจะสามารถกลับมาเป็นหนึ่งในบางครั้ง หรือสองครั้งอื่น ๆ -
ที่ไม่ได้ฟังก์ชันแฮชที่ดี
คุณตรงขวา
ฟังก์ชันแฮชของคุณควรจะกลับ เลขที่แน่นอนเดียวกันในกรณีนี้
สายตรง
>> บางทีมันอาจจะส่งกลับจำนวนเต็มแน่นอนเดียวกัน สำหรับสายตรง
โดยไม่คำนึงถึงมูลค่า
แต่ในกรณีที่มันยังคงเป็น กำหนดเพราะสิ่งที่หลาย ๆ
จะถูกแมปไปยังค่าเดียวกัน
ที่ปรับได้
ตราบใดที่มีเพียงหนึ่ง เอาท์พุทสำหรับใส่ให้
>> ตกลง
สิ่งที่สองคือว่ามัน ผลตอบแทนดัชนีที่ถูกต้อง
เราเติบโตขึ้นมาว่าก่อนหน้านี้
ฟังก์ชันแฮชนี้ -
โอ้เด็ก -
ฟังก์ชันแฮชควร กลับดัชนีที่ถูกต้อง
ดังนั้นพูด -
ให้กลับไปที่ตัวอย่างนี้
ฟังก์ชันแฮชของฉันนับขึ้น ตัวอักษรในคำว่า
นั่นคือฟังก์ชันแฮช
และส่งกลับจำนวนเต็มที่
ดังนั้นถ้าผมมีคำที่เป็น จะกลับมาอย่างใดอย่างหนึ่ง
และก็จะใส่ที่นี่
ถ้าฉันใส่ในค้างคาวคำว่า
มันจะกลับมาสาม
ที่ไม่ค้างคาวไป
>> มันไม่พอดี
แต่จะต้องไปที่ไหนสักแห่ง
นี้เป็นตารางแฮชของฉันหลังจากทั้งหมดและ ทุกอย่างต้องไปที่ไหนสักแห่ง
เพื่อที่ค้างคาวควรจะไป?
คิดใด?
คาดเดา?
คาดเดาที่ดี
>> ผู้ชม: ศูนย์
>> เจสัน Hirschhorn: ทำไมศูนย์?
>> ผู้ชม: เพ​​ราะสาม โมดูโลสามเป็นศูนย์?
>> เจสัน Hirschhorn สาม โมดูโลสามเป็นศูนย์
นั่นคือการคาดเดาที่ดี และที่ถูกต้อง
ดังนั้นในกรณีนี้มันควรจะเป็น อาจจะไปที่ศูนย์
ดังนั้นวิธีที่ดีเพื่อให้แน่ใจว่ากัญชานี้ ฟังก์ชั่นส่งกลับเฉพาะดัชนีที่ถูกต้อง
การโมดูโลได้โดยขนาดของตาราง
หากคุณโมดูโลสิ่งที่ผลตอบแทนโดย สามคุณเสมอไปที่จะได้รับ
บางสิ่งบางอย่างระหว่างศูนย์หนึ่งและสอง
และถ้าเสมอกลับเจ็ดและ คุณโมดูโลเสมอโดยสามคุณ
เสมอไปที่จะได้รับในสิ่งเดียวกัน
>> ดังนั้นจึงยังคงกำหนด ถ้าคุณโมดูโล
แต่ที่จะให้แน่ใจว่าคุณ ไม่เคยได้รับสิ่งที่ -
อุตสาหกรรมที่ไม่ถูกต้อง
โดยทั่วไปโมดูโลที่ควรจะเกิดขึ้น ภายในฟังก์ชันแฮชของคุณ
ดังนั้นคุณจึงไม่จำเป็นต้องกังวลเกี่ยวกับเรื่องนี้
คุณก็สามารถมั่นใจได้ว่า นี้เป็น indice ถูกต้อง
คำถามใด ๆ เกี่ยวกับเรื่องนี้ ที่อาจเกิดอันตราย?
>> ตกลง
และมีเราไป
ถัดไปที่อาจเกิดอันตรายและ นี้เป็นหนึ่งใหญ่
ถ้าสองปุ่มแผนที่ ให้เป็นค่าเดียวกันได้หรือไม่
จึงมีสองวิธีที่จะจัดการกับนี้
หนึ่งคือเรียกว่าเป็นเส้นตรง ละเอียดซึ่​​งฉัน
จะไม่ไปกว่า
แต่คุณควรจะคุ้นเคยกับวิธีการ ที่ทำงานและสิ่งที่เป็น
>> คนที่สองฉันจะไปกว่า เพราะนั่นเป็นสิ่งหนึ่งที่หลาย
คนอาจจะจบลงด้วยการที่จะตัดสินใจ เพื่อใช้ในการกำหนดปัญหาของพวกเขา
แน่นอนคุณจะได้ไม่ต้อง
แต่สำหรับชุดปัญหาหลายคน มีแนวโน้มที่จะเลือกที่จะสร้างตารางแฮช
ด้วยการผูกมัดที่แยกต่างหากที่จะใช้ พจนานุกรมของพวกเขา
ดังนั้นเรากำลังจะไปกว่าสิ่งที่มันหมายถึง ในการสร้างตารางแฮชที่มี
ผูกมัดแยก
>> ดังนั้นฉันใส่ในฟักทอง
มันกลับเป็นศูนย์
และฉันใส่ฟักทองที่นี่
จากนั้นฉันใส่ใน -
สิ่งที่เป็นอีกหนึ่งสิ่งที่ฮัลโลวีแกน
>> ผู้ชม: Candy
>> เจสัน Hirschhorn: Candy!
นั่นเป็นหนึ่งที่ดี
ฉันใส่ในขนมและลูกอม ยังช่วยให้ฉันเป็นศูนย์
ฉันจะทำอะไร
ความคิดใด?
เพราะคุณทุกคนรู้ว่าการจัดเรียงของ สิ่งที่แยกจากกันเป็นผูกมัด
ดังนั้นความคิดใด ๆ ว่าจะทำอย่างไร
ใช่
>> ผู้ชม: ใส่สตริง จริงในตารางแฮช
>> เจสัน Hirschhorn: ดังนั้นเราจะ วาดความคิดที่ดีกว่าที่นี่
ตกลง
>> ผู้ชม: มี Hashtable [ไม่ได้ยิน]
ตัวชี้ที่ชี้ไปยัง จุดเริ่มต้นของรายการ
และจากนั้นได้ฟักทองเป็นค่าแรก ในรายการที่เชื่อมโยงและลูกอมเป็น
ค่าที่สองในรายการที่เชื่อมโยง
>> เจสัน Hirschhorn: OK
มาร์คัสที่โดดเด่น
ฉันจะทำลายลง
มาร์คัสจะพูดไม่ได้ เขียนทับฟักทอง
ว่าจะไม่ดี
อย่าใส่ขนมที่อื่น
เราจะทำให้พวกเขาทั้งที่ศูนย์
แต่เรากำลังจะจัดการกับ วางพวกเขาที่ศูนย์โดย
การสร้างรายการที่ศูนย์
และเรากำลังจะสร้างรายการของ ทุกอย่างที่แมปไปยังศูนย์
และวิธีที่ดีที่สุดที่เราเรียนรู้ที่จะสร้าง รายการที่สามารถเจริญเติบโตและหดตัว
แบบไดนามิกไม่ได้อยู่ใน อาร์เรย์อื่น
จึงไม่ array หลายมิติ
แต่การที่จะเพียงแค่สร้างรายการที่เชื่อมโยง
>> ดังนั้นสิ่งที่เขาเสนอ -
ฉันจะได้รับใหม่ -
คือการสร้างอาเรย์กับตัวชี้, อาร์เรย์ของตัวชี้
ตกลง
ความคิดใด ๆ หรือคำแนะนำในสิ่งที่ประเภท ของตัวชี้นี้ควรจะเป็นอย่างไร
มาร์คัส?
>> ผู้ชม: ชี้ไป -
>> เจสัน Hirschhorn: เพราะคุณ รายการที่เชื่อมโยงกล่าวว่าดังนั้น -
>> ผู้ชม: ตัวชี้โหนด?
>> เจสัน Hirschhorn: ตัวชี้โหนด
หากสิ่งที่เราในการเชื่อมโยง รายการเป็นโหนดแล้วพวกเขา
ควรจะเป็นตัวชี้โหนด
และสิ่งที่พวกเขาเริ่มต้นเท่ากับ?
>> ผู้ชม: Null
>> เจสัน Hirschhorn: Null
ดังนั้นจึงมีสิ่งที่ว่างเปล่าของเรา
ฟักทองผลตอบแทนที่เป็นศูนย์
สิ่งใดที่เราจะทำอย่างไร
เดินฉันผ่านมันได้หรือไม่
ที่จริงแล้วมาร์คัสให้ฉัน
คนอื่นเดินฉันผ่านมัน
สิ่งที่เราทำเมื่อเรา -
นี้ดูคล้ายกับ สิ่งที่เรากำลังทำเพียงแค่
avi
>> ผู้ชม: ฉันจะใช้เวลาเดา
ดังนั้นเมื่อคุณได้รับขนม
>> เจสัน Hirschhorn: ใช่
ดีที่เราได้ฟักทอง
ให้ของได้รับคนแรกของเรา
เรามีฟักทอง
>> ผู้ชม: ตกลง
ฟักทองผลตอบแทนที่เป็นศูนย์
เพื่อให้คุณวางไว้ในที่
จริงหรือที่คุณใส่มัน ในรายการที่เชื่อมโยง
>> เจสัน Hirschhorn: วิธีที่เราทำ ใส่ไว้ในรายการที่เชื่อมโยงหรือไม่
>> ผู้ชม: โอ้ไวยากรณ์จริง
>> เจสัน Hirschhorn: เพียงแค่เดิน -
กล่าวเพิ่มเติม
สิ่งใดที่เราจะทำอย่างไร
>> ผู้ชม: คุณเพียงแค่ใส่ มันเป็นโหนดแรก
>> เจสัน Hirschhorn: OK
ดังนั้นเราจึงมีโหนดเราฟักทอง
และตอนนี้ฉันจะใส่มันได้หรือไม่
>> ผู้ชม: คุณสามารถกำหนด ไปชี้
>> เจสัน Hirschhorn: ซึ่งตัวชี้?
>> ผู้ชม: ตัวชี้ที่ศูนย์
>> เจสัน Hirschhorn: ดังนั้นที่ ไม่จุดนี้
>> ผู้ชม: เพ​​ื่อให้เป็นโมฆะได้ในขณะนี้
>> เจสัน Hirschhorn: ดี มันชี้ไปที่เป็นโมฆะ
แต่ฉันใส่ลงในฟักทอง
เพื่อที่มันควรจะชี้?
>> ผู้ชม: เพ​​ื่อฟักทอง
>> เจสัน Hirschhorn: เพื่อฟักทอง
อย่างแน่นอน
ดังนั้นจุดนี้ฟักทอง
และสถานที่ที่จะชี้นี้ ในจุดฟักทอง
ไปยัง
>> ผู้ชม: Null
>> เจสัน Hirschhorn: เพื่อโมฆะ
อย่างแน่นอน
ดังนั้นเราเพียงแค่ใส่บางสิ่งบางอย่าง เป็นรายการที่เชื่อมโยง
เราก็เขียนรหัสนี้จะทำเช่นนี้
เกือบเราเกือบจะได้มัน แตกอย่างสมบูรณ์
ตอนนี้เราใส่ขนม
ขนมของเรายังไปที่ศูนย์
ดังนั้นสิ่งที่เราจะทำอย่างไรกับขนม
>> ผู้ชม: มันขึ้นอยู่กับว่า เราไม่ได้กำลังพยายามที่จะจัดเรียง
>> เจสัน Hirschhorn: นั่น ตรงขวา
มันขึ้นอยู่กับว่าหรือไม่ เรากำลังพยายามที่จะจัดเรียง
สมมติว่าเราไม่ได้ จะจัดเรียง
>> ผู้ชม: ดีแล้วที่เรากล่าวถึง ก่อนที่มันจะง่ายที่สุดเพียงที่จะนำมัน
ในขณะที่จุดเริ่มต้นเพื่อให้ตัวชี้ จากศูนย์ชี้ไปที่ขนม
>> เจสัน Hirschhorn: OK
ยึดมั่นใน
ผมขอสร้างขนมที่นี่
ดังนั้นตัวชี้นี้ -
>> ผู้ชม: ใช่ตอนนี้ควร จะชี้ไปที่ขนม
แล้วมีตัวชี้จาก จุดขนมฟักทอง
>> เจสัน Hirschhorn: เช่นเดียวกับที่
และบอกว่าเราได้อีก สิ่งที่จะต้องทำแผนที่ให้เป็นศูนย์?
>> ผู้ชม: ดีคุณเพียงแค่ ทำในสิ่งเดียวกันได้หรือไม่
>> เจสัน Hirschhorn: ทำในสิ่งเดียวกัน
ดังนั้นในกรณีนี้ถ้าเราทำไม่ได้ ต้องการที่จะให้มันเรียงลำดับมัน
เสียงค่อนข้างง่าย
เราจะใช้ตัวชี้ใน indice ที่ได้รับจากฟังก์ชันแฮชของเรา
เรามีจุดที่ไปยังโหนดใหม่ของเรา
และแล้วสิ่งที่มันชี้ ไปก่อนหน้านี้ -
ในกรณี null นี้ใน กรณีฟักทองสอง -
ว่าสิ่งที่จะชี้ไปที่ ก่อนหน้านี้เราเพิ่มเข้าไปในต่อไปของ
โหนดใหม่ของเรา
เรากำลังใส่บางสิ่งบางอย่าง ในการเริ่มต้น
ในความเป็นจริงนี้เป็นจำนวนมากง่ายกว่า พยายามที่จะให้รายการที่เรียงลำดับ
แต่อีกครั้งจะมีการค้นหา ที่ซับซ้อนมากขึ้นที่นี่
เรามักจะต้องไปที่จุดสิ้นสุด
>> ตกลง
คำถามใด ๆ เกี่ยวกับการผูกมัดแยก
วิธีการทำงานที่?
กรุณาขอให้พวกเขาในขณะนี้
ผมต้องการที่จะให้แน่ใจว่าคุณทั้งหมด เข้าใจในเรื่องนี้ก่อนที่เราจะมุ่งหน้าออก
>> ผู้ชม: คุณไม่ใส่ฟักทองทำไม และลูกอมเป็นเดียวกัน
เป็นส่วนหนึ่งของตารางแฮชหรือไม่
>> เจสัน Hirschhorn: เป็นคำถามที่ดี
เราจะใส่ทำไมพวกเขาอยู่ในที่เดียวกัน เป็นส่วนหนึ่งของตารางแฮชหรือไม่
ดีในกรณีนี้ฟังก์ชันแฮชของเรา ผลตอบแทนที่เป็นศูนย์สำหรับทั้งสองของพวกเขา
ดังนั้นพวกเขาจึงจำเป็นต้องไปที่ศูนย์ indice เพราะที่ที่เรากำลังจะ
มองหาพวกเขาว่าเราเคย ต้องการที่จะดูพวกเขาขึ้น
อีกครั้งด้วยวิธีการเชิงเส้นละเอียด เราจะไม่ทำให้พวกเขาทั้งที่ศูนย์
แต่ในวิธีการที่ห่วงโซ่ที่แยกจากกัน เราจะทำให้พวกเขาทั้งที่ศูนย์
แล้วสร้างรายชื่อออกจากศูนย์
>> และเราไม่ต้องการที่จะเขียนทับฟักทอง เพียงเพื่อที่แล้วเพราะเราจะ
สมมติว่าฟักทองเป็น ไม่เคยใส่
ถ้าเราเพียงแค่ให้สิ่งหนึ่งใน สถานที่จะไม่ดี
จากนั้นก็จะไม่มี โอกาสของเราที่เคย -
ถ้าเราเคยมีที่ซ้ำกันแล้วเรา ก็จะลบค่าเริ่มต้นของเรา
เพื่อที่ว่าทำไมเราทำวิธีนี้
หรือว่าเป็นเหตุผลที่เราเลือก - แต่อีกครั้งเรา เลือกวิธีการผูกมัดที่แยกจากกัน
ซึ่งมีวิธีการอื่น ๆ อีกมากมาย หนึ่งสามารถเลือก
ไม่ว่าจะตอบคำถามของคุณหรือไม่
>> ตกลง
คาร์ลอ
เชิงเส้นละเอียดจะเกี่ยวข้องกับการ -
ถ้าเราพบการปะทะกันที่ศูนย์เรา จะดูในจุดต่อไปที่จะดูว่า
มันก็เปิดและใส่มันมี
แล้วเราดูในการเล่นกีฬาต่อไปและ ดูว่าที่เป็นแบบเปิดและใส่มันมี
ดังนั้นเราจึงหาที่มีอยู่ต่อไป จุดที่เปิดและใส่มันมี
คำถามใด ๆ อื่น ๆ
ใช่ Avi
>> ผู้ชม: ในฐานะที่เป็นตามขึ้นไปที่ สิ่งที่คุณหมายถึงโดยจุดต่อไปหรือไม่
ในตารางแฮชหรือในรายการที่เชื่อมโยง
>> เจสัน Hirschhorn: สำหรับการเชิงเส้น การเขียนโปรแกรมรายการไม่มีการเชื่อมโยง
จุดต่อไปในตารางแฮช
>> ผู้ชม: ตกลง
ดังนั้นตารางแฮชจะเป็น เริ่มต้นขนาด -
เช่นจำนวนของสตริง ที่คุณใส่?
>> เจสัน Hirschhorn: คุณจะ ต้องการให้เป็นใหญ่จริงๆ
ใช่
นี่คือภาพของสิ่งที่เรา เพียงแค่เข้ามาในคณะกรรมการ
อีกครั้งที่เราได้มีการปะทะกันที่นี่
ที่ 152
และคุณจะเห็นเราได้สร้าง รายการที่เชื่อมโยงออกจากมัน
อีกครั้งตารางแฮชผูกมัดแยก ไม่ได้เป็นวิธีการหนึ่งที่คุณ
ต้องใช้เวลาสำหรับปัญหาการตั้งค่า หก แต่เป็นหนึ่งที่มากของ
นักเรียนมีแนวโน้มที่จะใช้เวลา
ดังนั้นเมื่อทราบว่าให้เราพูดคุยสั้น ๆ ก่อนที่เราจะมุ่งหน้าออกเกี่ยวกับปัญหาที่หก
แล้วฉันจะแบ่งปันเรื่องราวกับคุณ
เรามีสามนาที
>> ปัญหาชุดหก
คุณมีสี่ฟังก์ชั่น -
ภาระการตรวจสอบขนาดและขน
โหลด -
ดีที่เราได้รับไป กว่าภาระเพียงแค่ตอนนี้
เราเข้ามาโหลดบนกระดาน
และที่เราจะได้เริ่มต้นการเขียนโปรแกรมมาก ใส่ลงไปในรายการที่เชื่อมโยง
ดังนั้นภาระไม่ได้เป็นอะไรมากไปกว่า สิ่งที่เราได้รับเพียงแค่การทำ
>> ตรวจสอบคือเมื่อคุณมี สิ่งที่โหลด
มันเป็นกระบวนการเดียวกันเช่นนี้
เดียวกันสองส่วนแรกที่คุณโยน บางสิ่งบางอย่างในการทำงานกัญชา
และได้รับค่าของมัน
แต่ตอนนี้เราไม่ได้ใส่
ตอนนี้เรากำลังมองหามัน
ฉันได้เขียนโค้ดตัวอย่างสำหรับการค้นหา สิ่งที่อยู่ในรายการที่เชื่อมโยง
ผมขอแนะนำให้คุณในการปฏิบัติที่
แต่สังหรณ์ใจหาสิ่งที่ สวยคล้ายกับการใส่บางสิ่งบางอย่าง
อันที่จริงเราวาดภาพในการค้นหา สิ่งที่อยู่ในรายการที่เชื่อมโยงย้าย
ผ่านทางจนกว่าคุณจะได้ไปในตอนท้าย
และถ้าคุณได้ไปที่สิ้นสุดและไม่สามารถ หามันแล้วมันไม่ได้มี
เพื่อให้การตรวจสอบเป็นหลัก
>> ถัดไปคือขนาด
ขอข้ามขนาด
ในที่สุดคุณได้ปลดปล่อย
ยกเลิกการโหลดเป็นหนึ่งที่เราไม่ได้วาด บนกระดานหรือเขียนยัง
แต่ผมขอแนะนำให้คุณลองใช้การเข้ารหัสมัน ตัวอย่างเช่นในรายการของเราเชื่อมโยง
แต่ขนอย่างสังหรณ์ใจ มีลักษณะคล้ายกับฟรี -
หรือผมหมายถึงคือที่คล้ายกันในการตรวจสอบ
ยกเว้นตอนนี้ทุกครั้งที่คุณกำลังจะ ผ่านคุณไม่ได้เพียงแค่การตรวจสอบเพื่อ
ดูว่าคุณมีค่าของคุณมี
แต่คุณกำลังการโหนดที่และ พ้นเป็นหลัก
นั่นคือสิ่งที่ขนขอให้คุณทำ
ทุกอย่างฟรีคุณ malloced
ดังนั้นคุณกำลังจะผ่านรายการทั้งหมด อีกครั้งจะผ่านทั้งกัญชา
ตารางอีกครั้ง
คราวนี้ไม่ต้องตรวจสอบ เพื่อดูสิ่งที่มี
ฟรีเพียงแค่สิ่งที่มี
>> และขนาดในที่สุด
ขนาดควรจะดำเนินการ
หากคุณไม่ได้ใช้ขนาด -
ฉันจะบอกเช่นนี้
หากคุณไม่ได้ใช้ในตรงขนาด หนึ่งบรรทัดของรหัสรวมทั้ง
กลับคำสั่งของคุณ ทำขนาดไม่ถูกต้อง
เพื่อให้แน่ใจว่าขนาดสำหรับการออกแบบเต็มรูปแบบ จุดที่คุณกำลังทำมันในตรงหนึ่ง
บรรทัดของรหัสรวมทั้ง งบกลับ
>> และไม่ได้แพ็คขึ้นยัง Akchar
ช่องคลอดกระตือรือร้น
ผมอยากจะบอกว่าขอบคุณพวกคุณ ที่มาไปยังส่วน
มี Happy Halloween
นี้เป็นเครื่องแต่งกายของฉัน
ฉันจะสวมใส่ในวันพฤหัสบดีนี้ ถ้าฉันเห็นคุณในเวลาทำการ
และถ้าคุณอยากรู้เกี่ยวกับบางอย่างมากขึ้น พื้นหลังเป็นชุดนี้ให้ความรู้สึก
ฟรีเพื่อตรวจสอบ 2011 ส่วน เรื่องที่ว่าทำไมฉัน
สวมใส่เครื่องแต่งกายฟักทอง
และมันเป็นเรื่องที่น่าเศร้า
เพื่อให้แน่ใจว่าคุณมี เนื้อเยื่อบางอย่างที่ใกล้เคียง
แต่ในที่นี้ถ้าคุณมีใด ๆ คำถามที่ฉันจะติดรอบ
หลังจากส่วนนอก
ขอให้โชคดีในการแก้ปัญหาการตั้งหก
และเช่นเคยถ้าคุณมีใด ๆ คำถามที่แจ้งให้เราทราบ