เจสัน 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 ส่วน เรื่องที่ว่าทำไมฉัน สวมใส่เครื่องแต่งกายฟักทอง และมันเป็นเรื่องที่น่าเศร้า เพื่อให้แน่ใจว่าคุณมี เนื้อเยื่อบางอย่างที่ใกล้เคียง แต่ในที่นี้ถ้าคุณมีใด ๆ คำถามที่ฉันจะติดรอบ หลังจากส่วนนอก ขอให้โชคดีในการแก้ปัญหาการตั้งหก และเช่นเคยถ้าคุณมีใด ๆ คำถามที่แจ้งให้เราทราบ