>> ลำโพง 1: ทั้งหมดขวาดังนั้นเราจะกลับมา
ยินดีต้อนรับสู่ CS50
นี่คือจุดสิ้นสุดของสัปดาห์ที่เจ็ด
ดังนั้นจำได้ว่าครั้งสุดท้ายที่เราเริ่มต้น กำลังมองหาที่ซับซ้อนมากขึ้นเล็กน้อย
โครงสร้างข้อมูล
ตั้งแต่จนถึงขณะนี้เรามีทั้งหมดจริงๆ ในการกำจัดของเรานี้เป็นอาร์เรย์
>> แต่ก่อนที่เราทิ้งแถวที่จะไม่ ทั้งหมดที่น่าสนใจซึ่งแน่นอนมัน
จริงเป็นสิ่งที่บางส่วนของที่มี pluses ของข้อมูลที่เรียบง่ายนี้
โครงสร้างป่านนี้?
ดีที่มันคืออะไร?
เท่าที่เราเคยเห็น?
คุณทำอะไรได้?
ไม่มีอะไร
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: อะไรที่?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงขนาดคงที่
OK เพื่อให้ขนาดคงที่คือเหตุผลที่ดีแม้ว่า?
>> ลูกศิษย์: [ได้ยิน]
>> ลำโพง 1: ตกลงดังนั้นจึงมีประสิทธิภาพในการ ความรู้สึกที่ว่าคุณสามารถจัดสรร
จำนวนคงที่ของพื้นที่ซึ่งหวังว่า เป็นอย่างแม่นยำเท่า
พื้นที่เท่าที่คุณต้องการ
เพื่อที่ว่าอาจจะเป็นบวกอย่างแน่นอน
>> อีกด้านขึ้นของอาร์เรย์คืออะไร?
อ้าง?
>> ลูกศิษย์: [ได้ยิน]
>> ลำโพง 1: ทั้งหมด - เสียใจ?
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: ทั้งหมดในกล่องสี่เหลี่ยมในหน่วยความจำ หรือถัดจากแต่ละอื่น ๆ
และที่เป็นประโยชน์ - เพราะเหตุใด
ที่จริงค่อนข้าง
แต่วิธีการที่เราสามารถใช้ประโยชน์จากความจริงที่ว่า?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงว่าเราสามารถติดตาม ที่ทุกอย่างเป็นเพียงโดยรู้
หนึ่งที่อยู่คือที่อยู่ของ ไบต์แรกของหน่วยความจำอันว่า
หรือในกรณีของสตริง, ที่อยู่ของแรก
ถ่านในสตริงที่
และจากนั้นเราสามารถหา จุดสิ้นสุดของสตริง
เราสามารถหาองค์ประกอบที่สอง, องค์ประกอบที่สามและอื่น ๆ
>> และดังนั้นวิธีที่จินตนาการในการอธิบายว่า คุณลักษณะคืออาร์เรย์ให้เรา
เข้าถึงโดยสุ่ม
โดยใช้เพียงแค่วงเล็บเหลี่ยม สัญกรณ์และจำนวนคุณสามารถข้ามไปยัง
องค์ประกอบเฉพาะในอาร์เรย์ ในช่วงเวลาคงที่, O ใหญ่
หนึ่งเพื่อที่จะพูด
>> แต่มีข้อเสียบางอย่างที่รับ
อะไรอาร์เรย์ได้ทำมากได้อย่างง่ายดาย?
มันเป็นสิ่งที่ไม่ดีที่?
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: อะไรที่?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงขยายขนาด
ดังนั้นข้อเสียของอาร์เรย์เป็น ได้อย่างแม่นยำตรงข้ามของสิ่ง
upsides เป็น
ดังนั้นหนึ่งในข้อเสียคือ ว่ามันเป็นขนาดคงที่
ดังนั้นคุณไม่สามารถจริงๆมันเติบโต
คุณสามารถจัดสรรก้อนใหญ่ หน่วยความจำและจากนั้นย้ายองค์ประกอบเก่า
เข้าแถวใหม่
แล้วฟรีอาร์เรย์เก่าสำหรับ ตัวอย่างเช่นโดยการใช้ malloc หรือคล้ายกัน
ฟังก์ชันที่เรียกว่า realloc ซึ่ง หน่วยความจำ reallocates
>> realloc เช่นกันพยายามที่จะให้คุณ หน่วยความจำที่ต่อไปไปยังอาร์เรย์
ที่คุณมีอยู่แล้ว
แต่มันอาจจะย้ายสิ่ง รอบทั้งหมด
แต่ในระยะสั้นที่มีราคาแพงใช่มั้ย?
เพราะถ้าคุณมีหน่วยความจำอันของ ขนาดนี้ แต่คุณต้องการจริงๆหนึ่ง
ขนาดนี้และคุณต้องการที่จะรักษา องค์ประกอบเดิมที่คุณมี
ประมาณเวลากระบวนการเชิงเส้นการคัดลอก ที่ต้องการที่เกิดขึ้นจาก
อาร์เรย์เก่าไปใหม่
และความเป็นจริงจะขอปฏิบัติการ ระบบอีกครั้งและอีกครั้งและ
อีกครั้งสำหรับชิ้นใหญ่ของหน่วยความจำที่สามารถเริ่มต้น เพื่อใช้เวลาของคุณบางส่วนเช่นกัน
ดังนั้นจึงเป็นทั้งพรและสาปใน ปิดบังความจริงที่ว่าเหล่านี้อาร์เรย์
มีขนาดคงที่
แต่ถ้าเราแนะนำแทนบางสิ่งบางอย่าง เช่นนี้ซึ่งเราเรียกว่าการเชื่อมโยง
รายการที่เราได้รับไม่กี่ upsides และ ข้อเสียไม่กี่ที่นี่เช่นกัน
>> ดังนั้นรายการที่เชื่อมโยงเป็นเพียงข้อมูล โครงสร้างที่สร้างขึ้นจาก structs ใน C นี้
กรณีที่โครงสร้างการเรียกคืนเป็นเพียง ภาชนะสำหรับหนึ่งหรือเฉพาะเจาะจงมากขึ้น
ประเภทของตัวแปร
ในกรณีนี้สิ่งที่ทำชนิดข้อมูล ดูเหมือนจะเป็นด้านในของ struct ว่า
ครั้งสุดท้ายที่เราเรียกว่าโหนด?
แต่ละสี่เหลี่ยมเหล่านี้คือโหนด
และแต่ละรูปสี่เหลี่ยมที่มีขนาดเล็ก ภายในของมันชนิดข้อมูลคือ
เราไม่ประเภทใดบ้างที่บอกว่า พวกเขาเมื่อวันจันทร์ที่?
อ้าง?
>> ลูกศิษย์: [ได้ยิน]
>> ลำโพง 1: ตัวแปรและตัวชี้หรือ มากขึ้นโดยเฉพาะ int สำหรับ n,
และตัวชี้ที่ด้านล่าง
ทั้งของผู้ที่เกิดขึ้นจะเป็น 32 บิตที่ อย่างน้อยในคอมพิวเตอร์เช่นนี้ CS50
เครื่องใช้ไฟฟ้าและอื่น ๆ ที่พวกเขากำลัง วาดอย่างเท่าเทียมกันในขนาดที่
>> ดังนั้นสิ่งที่จะใช้ตัวชี้ แต่สำหรับที่เห็นได้ชัด?
เพิ่มลูกศรนี้ทำไมตอนนี้เมื่อมีอาร์เรย์ ดังนั้นที่ดีและสะอาดและเรียบง่าย?
ตัวชี้กำลังทำอะไรอยู่สำหรับ เราในแต่ละโหนดเหล่านี้ได้อย่างไร
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงว่า
มันบอกคุณที่ หนึ่งต่อไปคือ
ดังนั้นผมจึงเรียงลำดับของการใช้การเปรียบเทียบของ โดยใช้ด้ายจะเรียงลำดับจาก
ด้ายโหนดเหล่านี้ร่วมกัน
และนั่นคือสิ่งที่เรากำลังทำอยู่ด้วย ชี้เพราะแต่ละเหล่านี้
ชิ้นของหน่วยความจำอาจจะหรืออาจจะไม่ ที่อยู่ติดกันกลับไปกลับไปที่
ภายในของ RAM เพราะทุกครั้งที่คุณ เรียก malloc บอกให้ฉันพอ
ไบต์สำหรับโหนดใหม่ก็อาจจะ จะอยู่ที่นี่หรือมันอาจจะเป็นที่นี่
มันอาจจะเป็นที่นี่
คุณเพียงแค่ไม่ทราบ
>> แต่การใช้ตัวชี้ในที่อยู่ของ โหนดที่คุณสามารถปักครอสติพวกเขา
ร่วมกันในวิธีการที่มีลักษณะทางสายตา เช่นรายการแม้ว่าสิ่งเหล่านี้
ทั้งหมดกระจายออกไปทั่วหนึ่งของคุณหรือ สองหรือสี่กิกะไบต์ของ RAM ของคุณ
ภายในเครื่องคอมพิวเตอร์ของคุณเอง
>> ข้อเสียเช่นนั้นแล้วของ รายการที่เชื่อมโยงคืออะไร?
ราคาเท่ากันคืออะไร เห็นได้ชัดว่าการจ่ายเงิน?
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: พื้นที่มากขึ้นใช่มั้ย?
เราได้ในกรณีนี้จำนวนสองเท่า ของพื้นที่เพราะเราได้ไปแล้ว
จาก 32 บิตสำหรับแต่ละโหนดสำหรับแต่ละ int ดังนั้นตอนนี้ 64 บิตเพราะเราต้อง
ให้ทั่วตัวชี้เช่นกัน
คุณจะได้รับประสิทธิภาพมากขึ้นถ้า struct ของคุณ มีขนาดใหญ่กว่าสิ่งที่ง่ายนี้
ถ้าคุณจริงมีนักเรียนภายใน ซึ่งคู่ของสตริงคือ
ชื่อและที่บ้านอาจจะมีหมายเลขประจำตัว, บางทีบางสาขาอื่น ๆ โดยสิ้นเชิง
>> ดังนั้นถ้าคุณมีโครงสร้างขนาดใหญ่มากพอ, แล้วอาจจะเสียค่าใช้จ่ายของตัวชี้คือ
ไม่เช่นใหญ่จัดการ
นี้เป็นบิตของกรณีมุมในการที่ เรากำลังจัดเก็บดังกล่าวที่เรียบง่ายแบบดั้งเดิม
ภายในของรายการที่เชื่อมโยง
แต่ประเด็นก็คือเดียวกัน
คุณกำลังใช้จ่ายมากขึ้นแน่นอน หน่วยความจำ แต่คุณจะได้รับ
ความยืดหยุ่น
เพราะตอนนี้ถ้าผมต้องการที่จะเพิ่มองค์ประกอบ ที่จุดเริ่มต้นของรายการนี​​้
ฉันต้องจัดสรรโหนดใหม่
และฉันได้เพียงแค่การปรับปรุงเหล่านั้น ลูกศรอย่างใดโดยเพียงแค่ย้าย
ชี้บางรอบ
>> ถ้าฉันต้องการแทรกสิ่งที่เป็น กลางของรายการที่ผมจะได้ไม่ต้อง
ผลักดันให้ทุกคนเหมือนกันที่เราทำใน อดีตที่ผ่านมาสัปดาห์โดยได้รับอาสาสมัครของเราที่
เป็นตัวแทนของอาร์เรย์
ฉันสามารถจัดสรรโหนดใหม่และ แล้วก็ชี้ลูกศรใน
ทิศทางที่แตกต่างกันเพราะมันไม่ได้ ต้องยังคงอยู่ในที่เกิดขึ้นจริง
หน่วยความจำเส้นจริงเหมือนที่ผมเคยวาด ได้ที่นี่บนหน้าจอ
>> แล้วสุดท้ายหากคุณต้องการแทรก บางสิ่งบางอย่างในตอนท้ายของรายการก็
ง่ายยิ่งขึ้น
นี้จะเรียงลำดับของสัญกรณ์พล แต่ตัวชี้ 34 ของใช้เดา
ค่าของตัวชี้มากที่สุดคืออะไร จัดเรียงวาดน่าจะเหมือนเก่า
โรงเรียนมีเสาอากาศ?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงมันอาจโมฆะ
และแน่นอนว่าเป็นหนึ่งของผู้เขียน เป็นตัวแทนของโมฆะ
และมันก็เป็นโมฆะเพราะคุณอย่างแน่นอน จำเป็นต้องรู้ว่าจุดสิ้นสุดของการเชื่อมโยง
คือรายการที่เกรงว่าคุณเก็บต่อไปนี้และ ต่อไปและต่อไปนี้ลูกศรเหล่านี้
ค่าขยะบาง
ดังนั้นโมฆะจะมีความหมายว่าไม่มี โหนดขึ้นทางด้านขวาของหมายเลข 34,
ในกรณีนี้
>> ดังนั้นเราจึงเสนอว่าเราสามารถใช้ โหนดในรหัสนี้
และเราได้เห็นแบบนี้ ของไวยากรณ์ก่อน
typedef เพียงแค่กำหนดประเภทใหม่สำหรับ เราทำให้เรามีความหมายเหมือนกันเช่น
สตริงเป็น char *
ในกรณีนี้มันจะให้เรา สัญกรณ์ชวเลขเพื่อให้โหนด struct
สามารถแทนเพียงแค่จะเขียนเป็น โหนดซึ่งเป็นมากสะอาด
มันมากน้อย verbose
>> ภายในของโหนดเห็นได้ชัดคือ int ที่เรียกว่า n แล้​​วโหนด struct *
ซึ่งหมายความว่าสิ่งที่เราต้องการ ลูกศรจะหมายถึงตัวชี้ไปยังอีก
โหนดของชนิดข้อมูลที่แน่นอนเดียวกัน
และผมเสนอว่าเราสามารถใช้ ฟังก์ชั่นค้นหาเช่นนี้ซึ่งที่
แวบแรกอาจจะดูเหมือน ที่มีความซับซ้อนน้อย
แต่เรามาดูมันในบริบท
>> ผมขอข้ามไปเครื่องใช้ที่นี่
ผมขอเปิดไฟล์ที่เรียกว่า รายการชั่วโมงศูนย์จุด
และมีเพียงคำนิยามของเรา เพิ่งเห็นสักครู่ที่ผ่านมาสำหรับข้อมูลนี้
ประเภทที่เรียกว่าโหนด
ดังนั้นเราจึงได้วางว่าเป็นไฟล์ dot ชั่วโมง
>> และเป็นกันแม้นี้ โปรแกรมที่คุณกำลังจะได้เห็นคือ
ไม่ทั้งหมดที่ซับซ้อนที่มันแน่นอน การประชุมเมื่อเขียนโปรแกรมเพื่อ
ใส่สิ่งที่ต้องการชนิดข้อมูลที่จะดึง ค่าคงที่บางครั้งภายในของคุณ
ไฟล์ส่วนหัวและไม่จำเป็นต้องใน ไฟล์ของคุณ C แน่นอนเมื่อของคุณ
ที่โปรแกรมมีขนาดใหญ่และมีขนาดใหญ่เพื่อให้ คุณรู้จักที่จะมองทั้งสอง
เอกสารในบางกรณีหรือ สำหรับพื้นฐานเช่นนี้
ความหมายของบางประเภท
>> ถ้าตอนนี้ผมเปิดรายการเป็นศูนย์จุด คสังเกตเห็นบางสิ่ง
ซึ่งจะรวมถึงส่วนหัวของไฟล์ไม่กี่ส่วนใหญ่ จากที่เราเคยเห็นมาก่อน
ซึ่งจะรวมถึงไฟล์ส่วนหัวของตัวเอง
>> และเป็นกันทำไมที่สอง คำพูดที่นี่เมื่อเทียบกับมุม
วงเล็บในบรรทัดที่ ผมได้เน้นมี?
>> ลูกศิษย์: [ได้ยิน]
>> ลำโพง 1: Yeah จึงเป็นไฟล์ท้องถิ่น
ดังนั้นถ้ามันเป็นไฟล์ของคุณเองที่นี่ ในบรรทัดที่ 15 ตัวอย่างเช่นคุณใช้
คำพูดคู่แทน ของวงเล็บมุม
>> ตอนนี้เป็นชนิดของที่น่าสนใจ
ขอให้สังเกตว่าที่ผมเคยประกาศทั่วโลก ตัวแปรในโปรแกรมนี้อยู่บนเส้น 18
ครั้งแรกเรียกว่าความคิดเป็นนี้คือ จะเป็นตัวชี้ไปที่แรก
โหนดในรายการที่เชื่อมโยงของฉันและฉันได้ เริ่มต้นให้เป็นโมฆะเพราะฉัน
ไม่ได้รับการจัดสรรตามความเป็นจริงใด ๆ โหนดเพียง แต่
>> ดังนั้นนี่หมายถึง pictorially สิ่งที่เรา เห็นช่วงเวลาที่ผ่านมาในภาพ
ตัวชี้ไกลว่า ด้านซ้ายมือ
ดังนั้นในขณะนี้ชี้ว่า ไม่ได้มีลูกศร
มันแทนเป็นโมฆะเพียง
แต่มันหมายถึงสิ่งที่จะเป็น ที่อยู่ของคนแรกที่เกิดขึ้นจริง
โหนดในรายการนี​​้
ดังนั้นผมจึงได้ดำเนินการมันเป็นระดับโลก เพราะเป็นคุณจะเห็นทั้งหมดนี้
โปรแกรมไม่ในชีวิตคือการดำเนินการ รายการที่เชื่อมโยงสำหรับฉัน
>> ตอนนี้ฉันมีต้นแบบไม่กี่ที่นี่
ฉันตัดสินใจที่จะใช้คุณสมบัติเช่น การลบการแทรก, การค้นหาและ
traversal -
เดินเพียงการข้ามล่าสุด รายการพิมพ์ออกองค์ประกอบ
และตอนนี้ที่นี่เป็นประจำหลักของฉัน
และเราจะไม่ใช้เวลามากเกินไปใน เหล่านี้ตั้งแต่นี้เป็นจัดเรียงของหวังว่า
หมวกเก่าโดยขณะนี้
>> ฉันจะทำต่อไปนี้, ขณะที่ผู้ใช้ให้ความร่วมมือ
ดังนั้นหนึ่งผมจะพิมพ์ ออกเมนูนี้
และฉันได้จัดรูปแบบเป็น เรียบร้อยเท่าที่ฉันสามารถ
ถ้าผู้ใช้ในหนึ่งนั่นหมายความว่า พวกเขาต้องการที่จะลบบางสิ่งบางอย่าง
ถ้าผู้ใช้ในสองนั่นหมายความว่า พวกเขาต้องการที่จะแทรกบางสิ่งบางอย่าง
เป็นต้น
ฉันกำลังจะไปแล้วแจ้งให้ แล้วสำหรับคำสั่ง
แล้วฉันจะใช้ GetInt
>> ดังนั้นนี่คือ menuing ง่ายจริงๆ ติดต่อที่คุณเพียงแค่ต้องพิมพ์
การทำแผนที่จำนวนหนึ่ง ของคำสั่งเหล่านั้น
และตอนนี้ฉันมีสวิทช์สะอาดดี คำสั่งที่จะเปิด
สิ่งที่ผู้ใช้พิมพ์นิ้ว
และถ้าพวกเขาพิมพ์หนึ่งฉันจะ เรียกลบและทำลาย
ถ้าพวกเขาพิมพ์สองนี้ฉันจะ เรียกแทรกและทำลาย
>> และผมสังเกตเห็นในขณะนี้ได้วางแต่ละ ของเหล่านี้ในบรรทัดเดียวกัน
นี่เป็นเพียงการตัดสินใจโวหาร
โดยปกติท​​ี่เราเคยเห็นบางสิ่งบางอย่าง เช่นนี้
แต่ฉันก็ตัดสินใจที่ตรงไปตรงมาโปรแกรมของฉัน มองที่อ่านได้มากขึ้นเพราะ
มันก็เป็นเพียงสี่กรณีไป เพียงรายการเช่นนี้
ใช้ที่ถูกต้องทั้งหมดของสไตล์
และฉันจะทำเช่นนี้ตราบเท่าที่ ผู้ใช้ยังไม่ได้พิมพ์เป็นศูนย์ซึ่งผม
ตัดสินใจที่จะหมายถึงการที่พวกเขาต้องการที่จะเลิก
>> ดังนั้นตอนนี้สังเกตเห็นสิ่งที่ฉัน จะทำที่นี่
ฉันจะเป็นอิสระรายชื่อเห็นได้ชัดว่า
แต่เพิ่มเติมว่าในเวลาเพียงสักครู่
Let 's แรกรันโปรแกรมนี้
ดังนั้นให้ฉันทำขั้วใหญ่ หน้าต่างรายชื่อจุดเฉือน 0
ฉันจะไปข้างหน้าและใส่โดย การพิมพ์สองเป็นจำนวนมากเช่น 50 และตอนนี้
คุณจะเห็นรายการอยู่ในขณะนี้ 50
และข้อความของฉันเพียงแค่เลื่อนขึ้นเล็กน้อย
ดังนั้นตอนนี้สังเกตเห็นรายการมี จำนวน 50
>> ขอทำแทรกอื่นโดยการสอง
ประเภทให้อยู่ในจำนวนหนึ่งเช่น
รายชื่อเป็นหนึ่งตามด้วย 50
ดังนั้นนี้เป็นเพียงการแสดงต้นฉบับ ของรายการ
และให้ใส่หมายเลขหนึ่งมากขึ้นเช่น หมายเลข 42 ซึ่งเป็นความหวัง
จะจบลงในช่วงกลางเพราะ โปรแกรมนี้ในทุกประเภทโดยเฉพาะอย่างยิ่งมัน
องค์ประกอบแทรกพวกเขา
จึงมีเรามีมัน
โปรแกรมใช้งานง่ายสุดที่จะทำได้ อย่างที่มีการใช้อาร์เรย์ แต่ฉัน
เกิดขึ้นที่จะใช้รายการการเชื่อมโยง เพียงเพื่อให้ฉันสามารถแบบไดนามิก
เติบโตและหด
>> ดังนั้นลองมาดูสำหรับการค้นหาถ้าฉัน ทำงานสามคำสั่งที่ฉันต้องการที่จะค้นหา
สำหรับการพูด, หมายเลข 43
และไม่มีอะไรที่พบว่าเห็นได้ชัดว่า เพราะผมได้กลับไม่มีการตอบสนอง
ดังนั้นลองทำเช่นนี้อีกครั้ง
ค้นหา
ค้นหา Let 's สำหรับ 50 หรือมากกว่าค้นหา 42 ซึ่งมีสุข
ความหมายที่ลึกซึ้งน้อย
และฉันพบความหมายของชีวิตที่นั่น
Number 42 ถ้าคุณไม่ทราบว่า อ้างอิงมัน Google
ทั้งหมดขวา
ดังนั้นสิ่งที่ได้ทำโปรแกรมนี้สำหรับฉันหรือไม่
มันได้รับอนุญาตเพียงฉันจึงแทรก ไกลและการค้นหาสำหรับองค์ประกอบ
>> Let 's ข้างหน้าอย่างรวดเร็วนั้นไป ฟังก์ชั่นที่เราชำเลืองมอง
ในวันจันทร์ที่เป็นทีเซอร์
ดังนั้นฟังก์ชั่นนี้ผมเรียกร้องการค้นหา องค์ประกอบในรายการเป็นครั้งแรกโดย
หนึ่งกระตุ้นให้ผู้ใช้แล้วโทร getInt ที่จะได้รับ int ที่เกิดขึ้นจริง
ที่คุณต้องการค้นหา
>> แล้วสังเกตเห็นนี้
ฉันจะสร้างตัวแปรชั่วคราว 188 สายในตัวชี้ที่เรียกว่า -
PTR -
อาจจะเรียกมันว่าอะไรก็ตาม
และมันก็เป็นตัวชี้ไปยังโหนด เพราะผมบอกว่า * โหนดมี
และฉันเริ่มต้นมันจะเท่ากับ เป็นครั้งแรกเพื่อที่ฉันจะได้อย่างมีประสิทธิภาพมีของฉัน
นิ้วเพื่อที่จะพูดในสิ่งที่ดี องค์ประกอบแรกของรายการ
ดังนั้นถ้ามือข้างขวาของฉันที่นี่คือ PTR ฉัน ชี้ไปที่สิ่งเดียวกันกับที่แรก
จะชี้ไปที่
>> ดังนั้นตอนนี้กลับมาอยู่ในรหัส เกิดขึ้นต่อไปคืออะไร -
นี้เป็นกระบวนทัศน์ทั่วไปเมื่อ iterating กว่าโครงสร้างเช่น
รายการที่เชื่อมโยง
ฉันจะทำต่อไปในขณะที่ ตัวชี้ไม่เท่ากับโมฆะดังนั้นในขณะที่
นิ้วมือข​​องฉันไม่ได้ชี้ไปที่ null บาง ค่าถ้าตัวชี้ลูกศร n เท่ากับ n
เราจะสังเกตเห็นเป็นครั้งแรกที่ n คืออะไร ผู้ใช้พิมพ์ลงใน GetInts ต่อการโทรที่นี่
>> และตัวชี้ลูกศร n หมายถึงอะไร?
ดีถ้าเรากลับไปยังภาพที่นี่ ถ้าฉันมีนิ้วชี้ไปที่
ที่โหนดแรกที่มีเก้า หลักหมายถึงลูกศรไปที่
โหนดและคว้าค่าที่ n ตั้ง, ในกรณีนี้เขตข้อมูลที่เรียกว่า n
>> เช่นกัน - และเราเห็นคู่นี้ ของสัปดาห์ที่ผ่านมาเมื่อมีคนถาม -
รูปแบบนี้เป็นของใหม่ แต่มันไม่ได้ ทำให้เรามีอำนาจที่เรา
ไม่ได้มีอยู่แล้ว
อะไรวลีเทียบเท่ากับการใช้นี้เป็น จุดสัญกรณ์และดาวคู่
ของสัปดาห์ที่ผ่านมาเมื่อเราปอกเปลือกกลับ ชั้นนี้บิตก่อนกำหนด?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงว่ามันเป็นดาวและ แล้วมันก็เป็นดาราจุด n ด้วย
วงเล็บที่นี่ซึ่งมีลักษณะ, ตรงไปตรงมาผมคิดว่า
คลุมเครือมากขึ้นที่จะอ่าน
แต่ตัวชี้ดาวเป็นเสมอ หมายถึงไปที่นั่น
และเมื่อคุณมีข้อมูลอะไร คุณสาขาต้องการเข้าถึง?
ที่ดีที่คุณใช้สัญกรณ์จุดที่จะเข้าถึง structs ด้านข้อมูลและฉัน
ต้องการเฉพาะ n
>> ตรงไปตรงมาฉันจะยืนยันนี้ เป็นเพียงยากที่จะอ่าน
มันยากที่จะจำที่ ทำวงเล็บไป
ดาวและทุกที่
ดังนั้นโลกนำมาใช้ประโยคบาง น้ำตาลเพื่อที่จะพูด
เพียงวิธีที่เซ็กซี่ของว่า นี้จะเทียบเท่าและ
บางทีอาจจะมากกว่างานง่าย
ถ้าตัวชี้ย่อมเป็นตัวชี้, หมายถึงสัญกรณ์ลูกศรไปที่นั่นและหา
สนามในกรณีนี้เรียกว่า n
>> ดังนั้นถ้าฉันพบว่ามันสังเกตเห็นสิ่งที่ฉันทำ
ฉันก็พิมพ์ออกมาผมพบว่าร้อยละ i, เสียบค่า int ที่
ที่ผมเรียกว่านอนหลับหนึ่งวินาทีเพียงแค่ชนิด สิ่งที่หยุดชั่วคราวบนหน้าจอเพื่อ
ให้ผู้ใช้ที่สองในการดูดซับ สิ่งที่เกิดขึ้นเพียง
แล้วฉันทำลาย
มิฉะนั้นผมจะทำอย่างไร
ผมปรับปรุงตัวชี้ไปที่เท่าเทียมกัน ลูกศรตัวชี้ต่อไป
>> ดังนั้นเพียงแค่ต้องมีความชัดเจนที่นี้หมายถึงไป มีการใช้สัญกรณ์โรงเรียนเก่าของฉัน
ดังนั้นเพียงแค่นี้หมายถึงการที่จะไปกับสิ่งที่ คุณกำลังชี้ไปที่ซึ่งมาก
กรณีแรกคือผมชี้ไปที่ struct กับเก้าในนั้น
ดังนั้นผมจึงได้ไปมี
แล้วจุดสัญกรณ์หมายถึง ได้รับค่าที่ต่อไป
>> แต่ค่าแม้ว่ามันวาด เป็นที่แคบเพียงจำนวนเป็น
มันเป็นตัวเลขที่อยู่
นี้หนึ่งบรรทัดของรหัสดังนั้นไม่ว่า เขียนเช่นนี้เป็นความลับมากขึ้น
วิธีการหรือเช่นนี้ขึ้นอีกเล็กน้อย วิธีการใช้งานง่ายเพียงแค่หมายความว่าย้ายมือของฉัน
จากโหนดแรกไปที่หน้าหนึ่ง, และจากนั้นที่หน้าหนึ่งแล้ว
หน้าหนึ่งและอื่น ๆ
>> ดังนั้นเราจะไม่ได้อาศัยอยู่ในที่อื่น ๆ การใช้งานของแทรกและลบ
และ traversal สองคนแรกของ ซึ่งมีส่วนเกี่ยวข้องอย่างเป็นธรรม
และฉันคิดว่ามันค่อนข้างง่ายที่จะได้รับ หายไปเมื่อทำมันด้วยวาจา
แต่สิ่งที่เราสามารถทำนี่คือ พยายามที่จะกำหนดวิธีการ
ที่ดีที่สุดที่จะทำนี้สายตา
เพราะฉันอยากจะเสนอว่าถ้าเรา ต้องการแทรกองค์ประกอบในนี้
รายการที่มีอยู่ซึ่ง มีห้าองค์ประกอบ -
9, 17, 22, 26, และ 33 -
ถ้าฉันกำลังจะดำเนินการนี​​้ใน รหัสผมต้องพิจารณาวิธีการที่จะไป
เกี่ยวกับการทำเช่นนี้
>> และฉันจะเสนอทำตามขั้นตอนทารก ซึ่งในกรณีนี้ผมหมายถึงสิ่งที่มี
สถานการณ์ที่เป็นไปได้ที่เรา อาจพบในการทั่วไป?
เมื่อการดำเนินการแทรกสำหรับการเชื่อมโยง รายการนี​​้เพิ่งเกิดขึ้นเป็น
ตัวอย่างเฉพาะในห้าของขนาด
ดีถ้าคุณต้องการแทรกหมายเลข, ชอบพูดหมายเลขหนึ่งและ
รักษาความสงบเรียบร้อยเรียงลำดับที่ เห็นได้ชัดว่าจำนวนหนึ่งจำเป็นต้องทำ
ไปในตัวอย่างนี้โดยเฉพาะ?
ชอบที่จุดเริ่มต้น
>> แต่สิ่งที่น่าสนใจนั่นคือ ถ้าคุณต้องการที่จะแทรกเข้ามาในนี้
รายการสิ่งที่ตัวชี้ความต้องการพิเศษ ต้องมีการปรับปรุงที่เห็นได้ชัด?
เป็นครั้งแรก
ดังนั้นผมจะเถียงนี้เป็นกรณีแรก ที่เราอาจต้องการที่จะต้องพิจารณา
สถานการณ์ที่เกี่ยวข้องกับการใส่ที่ จุดเริ่มต้นของรายการ
>> ขอฉีกอาจจะเป็นเรื่องง่ายหรือแม้กระทั่ง กรณีที่ง่ายขึ้นค่อนข้างพูด
สมมติว่าฉันต้องการแทรก 35 จำนวนเรียงลำดับ
มันเห็นได้ชัดว่าเป็นของที่นั่น
ดังนั้นสิ่งที่ชี้ชัดเป็นไป จะต้องมีการปรับปรุงในสถานการณ์ที่?
ตัวชี้ 34 กลายเป็นไม่เป็นโมฆะ แต่ที่อยู่ของ struct
ที่มีจำนวน 35
ดังนั้นว่าทั้งสองกรณีของ
ดังนั้นแล้วผมจัดเรียงของ quantizing วิธีการทำงานมากที่ฉันต้องทำที่นี่
>> และในที่สุดก็กรณีกลางเห็นได้ชัดคือ อันที่จริงในช่วงกลางถ้าผมต้องการ
ใส่บางสิ่งบางอย่างเช่นพูด 23, ที่จะไป ระหว่างที่ 23 และ 26 แต่
ขณะนี้สิ่งที่ได้รับน้อยมาก เพราะสิ่งที่เกี่ยวข้อง
ตัวชี้จะต้องมีการเปลี่ยนแปลงอย่างไร
ดังนั้นเห็นได้ชัด 22 ต้องมีการเปลี่ยนแปลง เพราะเขาไม่สามารถชี้ไปที่ 26 อีกต่อไป
เขาต้องการที่จะชี้ไปยังโหนดใหม่ที่ ฉันจะต้องจัดสรรโดยการเรียก
malloc หรือเทียบเท่าบาง
>> แต่แล้วฉันก็ยังต้องว่าโหนดใหม่, 23 ในกรณีนี้จะมีตัวชี้
ชี้ไปที่ใคร?
26
และมีเป็นไปได้ ลำดับของการดำเนินงานที่นี่
เพราะถ้าฉันทำเช่นนี้โง่และฉัน สำหรับการเริ่มต้นเช่นที่จุดเริ่มต้นของ
รายการและเป้าหมายของฉันคือการแทรก 23
และผมตรวจสอบที่ไม่ได้เป็นส่วนหนึ่งของ ที่นี่ใกล้กับเก้า?
เลขที่
มันเป็นส่วนหนึ่งของที่นี่ต่อไปถึง 17?
เลขที่
มันเป็นของที่นี่ต่อไปถึงวันที่ 22?
ใช่
>> ตอนนี้ถ้าผมโง่ที่นี่และไม่ได้ ความคิดนี้ผ่านทางผมอาจ
จัดสรรโหนดใหม่ของฉัน 23
ฉันอาจจะปรับปรุงตัวชี้จาก โหนดที่เรียกว่า 22 ชี้
ที่โหนดใหม่
และแล้วผมก็ทำในสิ่งที่ต้องปรับปรุง ตัวชี้โหนดใหม่ที่จะเป็น?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงว่า
ชี้ไปที่ 26
แต่ Dammit ถ้าฉันไม่ได้ปรับปรุงแล้ว ตัวชี้ 22 ที่จะชี้ไปที่ผู้ชายคนนี้และ
ตอนนี้ฉันมีเด็กกำพร้าที่เหลือ ของรายการเพื่อที่จะพูด
การสั่งซื้อเพื่อให้การดำเนินงานของที่นี่ เป็นไปได้ที่สำคัญ
>> การทำเช่นนี้ฉันสามารถขโมย, พูดหกอาสาสมัคร
และขอดูว่าเราไม่สามารถทำเช่นนี้ สายตาแทนของรหัสที่ชาญฉลาด
และเรามีบางอย่างที่น่ารักความเครียด ลูกสำหรับคุณในวันนี้
ตกลงเกี่ยวกับวิธีการหนึ่งสองใน กลับ - บนปลายมี
สามสี่ทั้งสองท่าน พวกที่สิ้นสุด
และห้าหก
แน่ใจ
ห้าและหก
ทั้งหมดที่ถูกต้องและเราจะมา ถึงพวกคุณในครั้งต่อไป
สิทธิทั้งหมดมาขึ้น
>> สิทธิทั้งหมดเนื่องจากคุณขึ้นที่นี่เป็นครั้งแรก, คุณอยากจะเป็นหนึ่งอย่างเชื่องช้า
ในแก้ว Google ที่นี่?
ทั้งหมดขวาดังนั้นตกลงแก้ว บันทึกวิดีโอ
ตกลงคุณจะดีไป
>> ขวาทั้งหมดดังนั้นหากพวกคุณสามารถมา ที่นี่ผมได้เตรียมล่วงหน้า
ตัวเลขบางอย่าง
สิทธิทั้งหมดมาที่นี่
และทำไมคุณไม่ไปเล็ก ๆ น้อย ๆ อีกวิธีการที่
และขอดูสิ่งที่ชื่อของคุณ กับแก้ว Google?
>> นักเรียน: เบน
>> 1 SPEAKER: เบน
ตกลงเบนคุณจะเป็นครั้งแรกอย่างแท้จริง
ดังนั้นเรากำลังจะไปส่ง ไปยังจุดสิ้นสุดของเวที
ขวาทั้งหมดและชื่อของคุณ?
>> นักเรียน: เจสัน
>> ลำโพง 1: เจสันตกลงคุณจะ เป็นหมายเลขเก้า
ดังนั้นหากคุณต้องการที่จะทำตามวิธีการที่เบน
>> นักเรียน: จิลล์
>> 1 SPEAKER: จิลล์ที่คุณกำลังจะได้รับ 17 ซึ่งถ้าผมทำขึ้นนี้
อย่างชาญฉลาดที่ผมจะต้อง เริ่มต้นที่ปลายอีกด้านหนึ่ง
คุณไปทางนั้น
22
และคุณคืออะไร?
>> นักเรียน: แมรี่
>> 1 SPEAKER: แมรี่, คุณจะ 22
และชื่อของคุณคืออะไร?
>> นักเรียน: คริส
>> ลำโพง 1: คริส, คุณจะ 26
แล้วสุดท้าย
>> นักเรียน: ไดอาน่า
>> 1 SPEAKER: Diana, คุณจะ 34
ดังนั้นคุณจึงมาที่นี่
>> ทั้งหมดที่เหมาะสมเพื่อให้สมบูรณ์แบบเรียง การสั่งซื้อสินค้าเรียบร้อยแล้ว
และให้ไปข้างหน้าและทำเช่นนี้ เพื่อให้เราสามารถจริงๆ -
เบนคุณเพียงแค่ชนิดของการมอง ออกไปไม่มีที่ไหนมี
OK เพื่อให้เป็นไปข้างหน้าและเห็นภาพนี้ โดยใช้แขนมากเหมือนผมตรง,
สิ่งที่เกิดขึ้น
เพื่อไปข้างหน้าและให้ตัวเอง หรือสองเท้าระหว่างตัวเอง
และไปข้างหน้าและชี้ด้วยมือข้างหนึ่งไป ใครก็ตามที่คุณควรจะชี้ไปที่
บนพื้นฐานนี้
และถ้าคุณเพียงแค่ชี้โมฆะ ตรงลงไปกองกับพื้น
ตกลงที่ดีเพื่อให้
>> ดังนั้นตอนนี้เรามีรายการที่เชื่อมโยงและให้ฉัน เสนอว่าผมจะเล่นบทบาทของ
PTR ดังนั้นฉันจะไม่รำคาญ แบกรอบนี้
และจากนั้น - คนโง่ประชุม - คุณสามารถเรียกสิ่งที่คุณต้องการนี​​้ -
ตัวชี้บรรพบุรุษของตัวชี้ pred -
เป็นเพียงชื่อเล่นเราให้ใน โค้ดตัวอย่างของเราที่จะมือซ้ายของฉัน
มืออื่น ๆ ที่จะได้รับการรักษา ติดตามใครเป็นใครใน
สถานการณ์ต่อไปนี้
>> ดังนั้นคิดว่าครั้งแรกที่ผมต้องการที่จะฉีก ว่าตัวอย่างแรกของการแทรกพูด
20 ลงในรายการ
ดังนั้นฉันจะต้องการใครซักคน รวบรวมจำนวน 20 สำหรับเรา
ดังนั้นผมจึงจำเป็นที่จะต้องมีคน malloc จากผู้ชม
มาขึ้น
คุณชื่ออะไร?
>> นักเรียน: ไบรอัน
>> ลำโพง 1: ไบรอันขวาทั้งหมดเพื่อให้คุณ จะต้องเป็นโหนดที่มี 20
สิทธิทั้งหมดมาที่นี่
และเห็นได้ชัดว่าที่ ไบรอันไม่เป็น?
ดังนั้นในช่วงกลางของ - จริง, เดี๋ยวก่อน
เรากำลังทำเช่นนี้การออกคำสั่ง
เรากำลังทำนี้ยากมาก กว่าที่จะต้องมีในตอนแรก
ตกลงเราจะฟรีไบรอัน และไบรอัน realloc ที่สุดเท่าที่ห้า
>> ตกลงดังนั้นตอนนี้เราต้องการที่จะแทรก ไบรอันที่ห้า
ดังนั้นเมื่อมาที่นี่ต่อไป เบนรอสักครู่
และคุณน่าจะสามารถบอกได้ ซึ่งเรื่องนี้เป็นไป
แต่ขอให้คิดอย่างรอบคอบเกี่ยวกับ การดำเนินงานเพื่อ
และมันก็เป็นอย่างแม่นยำภาพนี้ ที่กำลังจะเริ่มขึ้น
ที่มีรหัสตัวอย่างที่
ดังนั้นที่นี่ฉันมี PTR ชี้แรก ไม่ได้อยู่ที่เบนต่อ se แต่อย่างใด
เขามีค่าซึ่งในกรณีนี้ คือ - ชื่ออะไรของคุณอีกครั้ง?
>> นักเรียน: เจสัน
>> ลำโพง 1: เจสันดังนั้นทั้งเบนและฉันเป็น ชี้ไปที่เจสันในขณะนี้
ดังนั้นตอนนี้ฉันมีที่จะกำหนด ที่ไบรอันไม่เป็น?
ดังนั้นสิ่งเดียวที่ฉันจะสามารถเข้าถึง ตอนนี้ยังไม่มีรายการข้อมูลเป็นของเขา
ดังนั้นฉันจะตรวจสอบคือ ไบรอันน้อยกว่าเจสัน?
คำตอบที่เป็นความจริง
>> ดังนั้นตอนนี้สิ่งที่จะเกิดขึ้น ในลำดับที่ถูกต้อง?
ผมจำเป็นต้องปรับปรุงตัวชี้หลายวิธี ทั้งหมดในเรื่องนี้?
ที่มือของฉันก็ยังคงชี้ไปที่ เจสันและมือของคุณ - ถ้าคุณต้องการ
ใส่มือของคุณเช่นการเรียงลำดับของผม ไม่ทราบว่าเครื่องหมายคำถาม
ตกลงที่ดี
>> ทั้งหมดที่ถูกต้องเพื่อให้คุณมี ผู้สมัครไม่กี่
ทั้งเบนหรือฉันหรือไบรอันหรือเจสัน ทุกคนหรืออื่น ๆ ซึ่ง
ชี้ต้องเปลี่ยน?
วิธีการหลายอย่างในทั้งหมด?
>> ตกลงดังนั้นสอง
ตัวชี้ที่ฉันไม่ได้เรื่องจริงๆอีกต่อไป เพราะฉันเพียงชั่วคราวเท่านั้น
ดังนั้นมันจึงเหล่านี้สองคนสมมุติ ทั้งเบนและไบรอัน
เพื่อให้ฉันเสนอว่าเรา update เบนเขาตั้งแต่แรก
องค์ประกอบแรกของรายการนี​​้ คือตอนนี้จะเป็นไบรอัน
ดังนั้นเบนจุดที่ไบรอัน
ตกลงตอนนี้เป็นอย่างไร
>> ผู้ที่ได้รับชี้ไปที่ใคร?
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: ตกลงเพื่อให้มีไบรอัน ไปยังจุดที่เจสัน
ฉันได้ แต่สูญเสียการติดตามของตัวชี้ว่า
ฉันรู้ว่าเจสันคืออะไร?
>> ลูกศิษย์: [ได้ยิน]
>> ลำโพง 1: I do, ตั้งแต่ฉัน ตัวชี้ชั่วคราว
และสันนิษฐานว่าผมยังไม่ได้เปลี่ยน เพื่อชี้ไปที่โหนดใหม่
ดังนั้นเราก็สามารถมีจุดไบรอัน ที่ใครก็ตามที่ผมชี้ไปที่
และเรากำลังทำ
ดังนั้นกรณีหนึ่งที่แทรก จุดเริ่มต้นของรายการ
มีสองขั้นตอนสำคัญคือ
หนึ่งเราต้องปรับปรุงเบนแล้ว เรายังต้องปรับปรุงไบรอัน
และแล้วฉันไม่ต้องกังวล Traipsing ผ่านส่วนที่เหลือของ
รายการเพราะเรารู้อยู่แล้วว่าของเขา สถานที่เพราะเขาเป็น
ด้านซ้ายขององค์ประกอบแรก
>> ทั้งหมดขวาเพื่อตรงไปตรงสวย
ในความเป็นจริงความรู้สึกเหมือนเราเกือบ การนี​​้ซับซ้อนเกินไป
ดังนั้นตอนนี้ขอถอนปิดท้าย ของรายการและดูว่า
ความซับซ้อนจะเริ่มต้น
ดังนั้นถ้าตอนนี้ฉัน alloc จากผู้ชม
ทุกคนต้องการที่จะเล่น 55?
ทั้งหมดขวาฉันเห็นมือของคุณเป็นครั้งแรก
มาขึ้น
ใช่
คุณชื่ออะไร?
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: Habata
ตกลงมาขึ้น
คุณจะ 55 จำนวน
ดังนั้นคุณแน่นอนไม่ได้เป็นสมาชิก ในตอนท้ายของรายการ
ดังนั้นขอเล่นใหม่จำลองกับฉัน เป็น PTR รอสักครู่
ดังนั้นฉันแรกจะไปจุดที่ สิ่งที่เบนชี้ไปที่
เรากำลังทั้งสองชี้ไปที่ไบรอัน
ดังนั้น 55 มีจำนวนไม่น้อยกว่าห้า
ดังนั้นฉันจะปรับปรุงตัวเองโดย ชี้ไปที่ตัวชี้ต่อไปของไบรอันที่
ขณะนี้เป็นหลักสูตรที่เจสัน
55 ไม่น้อยกว่าเก้าดังนั้น ฉันจะปรับปรุง PTR
ผมจะ update PTR
และฉันจะไป - อืมอะไร ชื่อของคุณอีกครั้ง?
>> นักเรียน: ไดอาน่า
>> ลำโพง 1: ไดอาน่าชี้ของหลักสูตร ที่โมฆะด้วยมือซ้ายของเธอ
เพื่อที่ Habata ไม่จริง เป็นอย่างชัดเจน?
ไปทางซ้ายที่นี่
ดังนั้นฉันจะรู้ว่าเธอจะใส่ที่นี่ ฉันคิดว่าฉันเมาขึ้น
เพราะเป็นสิ่ง PTR ศิลปะ ขณะที่ในเวลานี้?
Null
ดังนั้นแม้ว่าสายตาเราสามารถ เห็นได้ชัดว่าได้เห็นสิ่งเหล่านี้
ผู้ชายที่นี่บนเวที
ฉันไม่ได้เฝ้าติดตามก่อนหน้านี้ คนที่อยู่ในรายชื่อ
ฉันไม่ได้มีนิ้วชี้ออก, ในกรณีนี้จำนวนโหนด 34
>> ดังนั้นขอเริ่มต้นจริงมากกว่านี้
ดังนั้นตอนนี้ที่จริงผมจะต้อง ตัวแปรท้องถิ่นที่สอง
และนี่คือสิ่งที่คุณจะเห็นใน ตัวอย่างรหัสจริง C, ขณะที่ผมไป
เมื่อ update ขวามือของเราที่จะชี้ให้ เจสัน, ไบรอันจึงออกจากที่อยู่เบื้องหลังผม
ดีกว่าเริ่มใช้มือซ้ายของฉันไป ปรับปรุงที่ผมเพื่อให้ผมไป
ผ่านรายการนี​​้ -
มากขึ้นอย่างเชื่องช้ากว่าที่ฉันตั้งใจ ตอนนี้ที่นี่สายตา -
ฉันจะได้รับ ตอนท้ายของรายการ
>> มือนี่ยังคงเป็นโมฆะที่สวย ไร้ประโยชน์อื่น ๆ มากกว่าที่จะแสดงให้เห็นว่า
ฉันได้อย่างชัดเจนในตอนท้ายของรายการ, แต่ตอนนี้อย่างน้อยฉันมีนี้
ตัวชี้บรรพบุรุษชี้ที่นี่ดังนั้น ตอนนี้สิ่งที่มือและสิ่งที่ตัวชี้ต้อง
ได้รับการปรับปรุง?
ที่มีมือที่คุณต้องการ กำหนดค่าเป็นอันดับแรก
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: OK เพื่อให้เจ้าหญิงไดอาน่า
คุณต้องการไปยังจุดที่ ตัวชี้ซ้ายของเจ้าหญิงไดอาน่าที่?
ที่ 55, สันนิษฐานว่าเพื่อให้ เราได้แทรกมี
และสถานที่ที่ 55 ตัวชี้ควรจะไป?
ลงคิดเป็นโมฆะ
และมือของฉันที่จุดนี้ไม่ได้ สำคัญเพราะพวกเขาเพียง
ตัวแปรชั่วคราว
ดังนั้นตอนนี้เรากำลังทำ
>> ดังนั้นซับซ้อนเพิ่มเติมมี - และ มันไม่ยากที่จะดำเนินการ
แต่เราจำเป็นต้องมีตัวแปรรองที่จะทำให้ แน่ใจแล้วหรือว่าก่อนที่ผมจะย้ายไปทางขวาของฉัน
มือผมปรับปรุงค่าของฉันซ้าย มือชี้ pred ในกรณีนี้ดังนั้น
ว่าฉันมีตัวชี้ลาก เพื่อติดตามว่าผมอยู่ที่ไหน
ตอนนี้เป็นกันถ้าคุณคิดว่านี้ ผ่านนี้รู้สึกเหมือนมันเป็น
เล็ก ๆ น้อย ๆ ที่น่ารำคาญที่จะมีการเก็บ ติดตามมือซ้ายนี้
>> สิ่งที่จะแก้ปัญหาอื่น เพื่อแก้ไขปัญหานี้ได้รับ?
หากคุณมีการออกแบบข้อมูล โครงสร้างเรากำลังพูดถึง
ผ่านได้ในขณะนี้?
ถ้าเป็นแค่ความรู้สึกเล็ก ๆ น้อย ๆ ที่น่ารำคาญจะมีเหมือนสองตัวชี้
จะผ่านรายการให้ใครสามารถ ได้ในโลกที่เหมาะการบำรุงรักษา
ข้อมูลที่เราต้อง?
อ้าง?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงว่า
ขวาจึงมีความจริงที่น่าสนใจ เชื้อโรคของความคิด
และความคิดของตัวชี้หน้าที่นี้ ชี้ไปที่องค์ประกอบหน้าที่แล้ว
ถ้าฉันเพียงแค่ว่าเป็นตัวเป็นตน ด้านในของตัวรายการเอง?
และมันจะเป็นเรื่องยากที่จะเห็นภาพ โดยไม่ต้องทั้งหมดกระดาษ
ล้มลงไปที่พื้น
แต่คิดว่าคนเหล่านี้ใช้ทั้ง จากมือของพวกเขาจะมีหน้าที่
ตัวชี้และตัวชี้ต่อไปดังนั้น การดำเนินการสิ่งที่เราจะเรียกเป็นทวีคูณ
รายการที่เชื่อมโยง
ที่จะช่วยให้ผมที่จะจัดเรียงย้อนกลับ มากขึ้นได้อย่างง่ายดายโดยไม่ต้องฉัน
โปรแกรมเมอร์ที่มีให้ ติดตามด้วยตนเอง -
อย่างแท้จริงด้วยตนเอง -
จากที่ผมเคยเป็น ในรายการ
ดังนั้นเราจะไม่ทำอย่างนั้น
เราจะให้มันง่ายเพราะนั่นคือ จะมาในราคาสองเท่า
พื้นที่มากสำหรับตัวชี้, ถ้าคุณต้องการที่หนึ่งที่สอง
แต่ที่จริงที่พบบ่อย โครงสร้างข้อมูลที่เรียกว่า
รายการที่เชื่อมโยงเป็นทวีคูณ
>> ขอทำตัวอย่างสุดท้ายที่นี่และวาง คนเหล่านี้ออกจากความทุกข์ยากของพวกเขา
ดังนั้น 20 malloc
มาขึ้นมาจากทางเดินมี
ขวาทั้งหมด, คุณชื่ออะไร?
>> ลูกศิษย์: [ได้ยิน]
>> ลำโพง 1: ขอโทษ?
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: Demeron
ตกลงมาขึ้น
คุณจะต้องเป็น 20
คุณชัดจะไป อยู่ระหว่าง 17 และ 22
เพื่อให้ฉันเรียนรู้บทเรียนของฉัน
ฉันจะเริ่มต้นชี้ ชี้ไปที่ไบรอัน
และฉันจะมีมือซ้ายของฉัน เพียง แต่ปรับปรุงให้ไบรอันที่ผมย้ายไป
เจสันตรวจสอบไม่น้อยกว่า 20 เก้า?
เลขที่
คือ 20 น้อยกว่า 17?
เลขที่
คือ 20 น้อยกว่า 22?
ใช่
ดังนั้นตัวชี้อะไรหรือมือจำเป็นต้องเปลี่ยน ที่พวกเขากำลังชี้อยู่ตอนนี้
>> ดังนั้นเราจึงสามารถทำ 17 ชี้ไปที่ 20
ดังนั้นที่ดี
เราไม่ต้องการไปยังจุดที่ ตัวชี้ของคุณตอนนี้
วันที่ 22
และเรารู้ว่า 22 คือขอบคุณอีกครั้ง ตัวชี้ชั่วคราวของฉัน
ดังนั้นเราจึงไม่ตกลงมี
เพราะจากการจัดเก็บชั่วคราวนี้ ฉันเฝ้าติดตามที่ทุกคนเป็น
และตอนนี้คุณมองเห็นสามารถไปในที่ที่ คุณอยู่และตอนนี้เราจำเป็นต้อง 1, 2, 3,
4, 5, 6, 7, 8, 9 ลูกความเครียด และรอบปรบมือสำหรับ
คนพวกนี้ถ้าเราทำได้
ทำได้อย่างดี
>> [APPLAUSE]
>> ลำโพง 1: ทั้งหมดขวา
และคุณอาจเก็บชิ้น ของกระดาษที่เป็นของที่ระลึก
>> ทั้งหมดขวาดังนั้นเชื่อฉันมันมาก ง่ายต่อการเดินผ่านว่า
มนุษย์มากกว่าที่เป็นอยู่ด้วยรหัสที่เกิดขึ้นจริง
แต่สิ่งที่คุณจะพบในเวลาเพียงสักครู่ ตอนนี้จะเหมือนกันว่า - โอ้ขอบคุณคุณ
ขอบคุณ -
คือการที่คุณจะพบว่าข้อมูลที่เหมือนกัน โครงสร้างรายการที่เชื่อมโยงสามารถจริง
จะใช้เป็นอาคารตึกไปมากยิ่งขึ้น โครงสร้างข้อมูลที่มีความซับซ้อน
>> และตระหนักเกินไปธีมที่นี่เป็นที่ เราได้รับการแนะนำอย่างมาก
ความซับซ้อนในการดำเนินการ ของขั้นตอนวิธีนี้
แทรกและถ้าเราเดินผ่านมัน การลบและการค้นหาเป็นเล็ก ๆ น้อย ๆ
ซับซ้อนมากขึ้นกว่ามัน เป็นกับอาร์เรย์
แต่เราได้รับบางอย่างแคล่วคล่อง
เราได้รับข้อมูลโครงสร้างการปรับตัว
>> แต่อีกครั้งที่เราจ่ายราคาของการมีบาง ความซับซ้อนที่เพิ่มขึ้นทั้งใน
การดำเนินการนั้น
และเราได้รับการเข้าถึงแบบสุ่ม
และจะซื่อสัตย์มีไม่ดีบางอย่าง ทำความสะอาดสไลด์ที่ฉันสามารถให้คุณว่า
พูดว่าที่นี่ทำไมรายการที่เชื่อมโยงเป็น จะดีกว่าอาร์เรย์
และออกมาว่า
เพราะรูปแบบ reoccurring ตอนนี้แม้ มากขึ้นดังนั้นในสัปดาห์ที่ผ่านมาคือ
ว่ามีไม่จำเป็นต้อง คำตอบที่ถูกต้อง
>> นี่คือเหตุผลที่เรามีแกนแยก ของการออกแบบสำหรับชุดปัญหา
มันจะเป็นบริบทที่สำคัญมาก ไม่ว่าคุณต้องการที่จะใช้ข้อมูลนี้
โครงสร้างหรือการที่หนึ่งและมันจะ ขึ้นอยู่กับสิ่งที่สำคัญกับคุณในแง่
ของทรัพยากรและความซับซ้อน
>> แต่ให้ฉันเสนอว่าเหมาะสำหรับข้อมูลที่ โครงสร้างจอกศักดิ์สิทธิ์จะ
สิ่งที่เวลาคงที่, โดยไม่คำนึงถึงวิธีการที่สิ่งที่เป็นมาก
ภายในนั้นมันจะไม่น่าตื่นตาตื่นใจถ้า โครงสร้างข้อมูลที่ส่งกลับคำตอบใน
เวลาคง
ใช่
คำนี้อยู่ในพจนานุกรมขนาดใหญ่ของคุณ
หรือไม่มีคำนี้ไม่ได้
หรือมีปัญหาดังกล่าว
ดีขอดูว่าเราไม่ได้เป็นอย่างน้อย จะใช้ขั้นตอนต่อว่า
>> ผมขอเสนอโครงสร้างข้อมูลใหม่ที่ สามารถใช้สำหรับสิ่งที่แตกต่าง
ในกรณีนี้เรียกว่าตารางแฮช
และเพื่อให้เราไม่จริงกลับไปแฉลบ ที่อาร์เรย์ในกรณีนี้และ
ค่อนข้างพลฉันวาดนี้ ตารางแฮชเป็นอาร์เรย์ที่มีการเรียงลำดับของ
อาร์เรย์สองมิติ -
หรือมากกว่านั้นที่นี่เป็นภาพสอง อาร์เรย์มิติ - แต่นี้เป็นเพียง
อาร์เรย์ของ 26 ขนาดดังกล่าวว่าถ้าเรา เรียกตารางอาร์เรย์วงเล็บตาราง
ศูนย์เป็นรูปสี่เหลี่ยมผืนผ้าที่ด้านบน
วงเล็บตาราง 25 เป็นรูปสี่เหลี่ยมผืนผ้า ที่ด้านล่าง
และนี่คือวิธีการที่ฉันอาจดึงข้อมูล โครงสร้างในการที่ฉันต้องการเก็บ
ชื่อคน
>> ดังนั้นสำหรับตัวอย่างเช่นและฉันจะไม่วาด สิ่งทั้งหมดที่นี่ค่าใช้จ่ายถ้าฉัน
มีอาร์เรย์นี้ซึ่งตอนนี้ฉันจะไป เรียกตารางแฮชและนี่คืออีกครั้ง
สถานที่ตั้งศูนย์
นี้ที่นี่เป็นที่ตั้ง หนึ่งและอื่น ๆ
ผมอ้างว่าผมต้องการที่จะใช้ข้อมูลนี้ โครงสร้างเพื่อประโยชน์ของการสนทนา,
การจัดเก็บชื่อของผู้คน, Alice และ Bob และชาร์ลีและชื่ออื่น ๆ เช่น
ดังนั้นคิดว่าตอนนี้เป็นจุดเริ่มต้น ของการพูดพจนานุกรม
ที่มีจำนวนมากของคำ
พวกเขาเกิดขึ้นจะเป็นชื่อ ในตัวอย่างของเราที่นี่
และนี่คือทั้งหมดซึ่งเกี่ยวดองกันอย่างใกล้ชิดเกินไปบางที การดำเนินการตรวจสอบการสะกดในขณะที่เรา
สำหรับปัญหาอาจตั้งหก
>> ดังนั้นถ้าเรามีอาร์เรย์ของขนาดรวม 26 เพื่อที่ว่านี้เป็นสถานที่ที่ 25
ที่ด้านล่างและฉันอ้างว่าเป็นอลิซ คำแรกในพจนานุกรมของ
ชื่อที่ผมต้องการแทรกลงใน RAM, เป็นโครงสร้างข้อมูลนี้อยู่ที่ไหน
สัญชาตญาณบอกคุณว่าอลิซ ชื่อควรจะไปในอาร์เรย์นี้
>> เรามี 26 ตัวเลือก
ที่เราต้องการที่จะนำเธอ?
เราต้องการให้เธออยู่ในวงเล็บเป็นศูนย์ใช่มั้ย?
อลิซขอเรียกว่าเป็นศูนย์
และจะเป็นหนึ่ง, และ C จะมีสอง
ดังนั้นเรากำลังจะเขียน ชื่อของอลิซที่นี่
ถ้าเราแล้วใส่บ๊อบของเขา ชื่อจะไปที่นี่
ชาร์ลีจะไปที่นี่
และอื่น ๆ ลงผ่าน นี้โครงสร้างข้อมูล
>> นี้เป็นโครงสร้างข้อมูลที่ยอดเยี่ยม
ทำไม?
ดีเวลาทำงานของเป็นสิ่งที่ ใส่ชื่อของมนุษย์เป็นแบบนี้
โครงสร้างข้อมูลในตอนนี้?
ระบุว่าตารางนี้จะดำเนินการ อย่างแท้จริงเป็นอาร์เรย์
ดีก็ถึงเวลาที่คงที่
มันเป็นคำสั่งของหนึ่ง
ทำไม?
>> ดีอย่างไรคุณกำหนด ที่อลิซเป็น?
คุณดูที่ตัวอักษรของชื่อของเธอ?
เป็นครั้งแรก
และคุณจะได้รับมีถ้ามันสตริง, โดยเพียงแค่มองไปที่สตริง
ศูนย์วงเล็บ
ดังนั้นตัวละคร 0 ของสตริง
ที่ง่าย
เราได้ว่าในการเข้ารหัสลับ สัปดาห์ที่ผ่านมาที่ได้รับมอบหมาย
และแล้วเมื่อคุณรู้ว่าอลิซ ตัวอักษรเป็นเมืองหลวงเราสามารถลบ
ออก 65 หรือเงินทุนตัวเอง ที่จะช่วยให้เราเป็นศูนย์
ดังนั้นตอนนี้เรารู้ว่าอลิซเป็น ที่ศูนย์ที่ตั้ง
>> และได้รับการชี้ไปยังข้อมูลนี้ โครงสร้างของการจัดเรียงบางอย่างนานแค่ไหน
มันพาฉันไปหาสถานที่ เป็นศูนย์ในอาร์เรย์?
เพียงหนึ่งขั้นตอนที่ถูกต้องถึงเวลาที่คงที่ เพราะเข้าถึงโดยสุ่มเรา
ที่นำเสนอเป็นคุณลักษณะของอาร์เรย์
ดังนั้นในระยะสั้น, การหาสิ่งที่ดัชนี ชื่อของอลิซเป็นซึ่งก็คือใน
กรณีนี้หรือให้เพียงแก้ไข ที่เป็นศูนย์ที่ B เป็นหนึ่งและ C คือ
สองการหาที่ออก เป็นเวลาที่คงที่
ผมเพียงแค่ต้องมองไปที่ตัวอักษรตัวแรกของเธอ การหาสถานที่ที่เป็นศูนย์
แถวนี้ยังมีเวลาคง
ดังนั้นในทางเทคนิคที่ เช่นเดียวกับขั้นตอนที่สองในขณะนี้
แต่ที่ยังคงคงที่
ดังนั้นเราจึงเรียกว่า O ใหญ่ของหนึ่งดังนั้นเราได้ อลิซแทรกลงในตารางนี้
เวลาคง
>> แต่แน่นอนว่าผมเป็น ไร้เดียงสาที่นี่ใช่มั้ย?
เกิดอะไรขึ้นถ้ามีแอรอนในชั้นเรียน?
หรือ? อลิเซีย
หรือชื่ออื่น ๆ ที่เริ่มต้นด้วย A. เราจะไปที่ไหนที่จะใส่
คนนั้นใช่มั้ย?
ผมหมายถึงตอนนี้มีเพียงสาม คนบนโต๊ะดังนั้นบางทีเรา
ควรใส่แอรอนที่ตั้ง ศูนย์หนึ่งสองสาม
>> ขวาฉันสามารถวางที่นี่
แต่แล้วถ้าเราพยายามแทรกเข้าไปเดวิด รายการนี​​้ที่ดาวิดไป?
ตอนนี้ระบบของเราจะเริ่มต้นการทำลาย ลงขวา?
เพราะตอนนี้เดวิดจบลงที่นี่ ถ้าแอรอนเป็นจริงที่นี่
และดังนั้นตอนนี้ความคิดทั้งหมดของการมี โครงสร้างข้อมูลที่สะอาดที่จะช่วยให้เรา
แทรกเวลาคงไม่ได้ เวลาคงเพราะฉันต้อง
ตรวจสอบโอ้ Damnit คนที่มีอยู่แล้ว ที่ตั้งของอลิซ
>> ผมขอแสดงความคิดเห็นส่วนที่เหลือของข้อมูลนี้ โครงสร้างที่กำลังมองหาจุดที่จะใส่
ใครบางคนเช่นชื่อของแอรอน
และอื่น ๆ ที่เกินไปจะเริ่มต้น ที่จะใช้เวลาเชิงเส้น
นอกจากนี้หากคุณต้องการที่จะหา แอรอนในนี้โครงสร้างข้อมูลและคุณ
ตรวจสอบและชื่อของแอรอนไม่ได้ที่นี่
เป็นการดีที่คุณเพียงแค่จะบอกว่าแอรอน ไม่ได้อยู่ในโครงสร้างข้อมูล
แต่ถ้าคุณทำเริ่มทำห้องพักสำหรับ แอรอนที่มีควรจะได้รับ D
หรือ E, คุณ, กรณีที่เลวร้ายที่สุดมีการตรวจสอบ โครงสร้างข้อมูลทั้งใน
ซึ่งในกรณีนี้มันเป็นสิ่งที่ devolves เชิงเส้นในขนาดของตาราง
>> ดังนั้นสิทธิทั้งหมดที่ฉันจะแก้ไขปัญหานี้
ปัญหาที่นี่คือที่ฉันมี 26 องค์ประกอบในอาร์เรย์นี้
ผมขอเปลี่ยนเป็น
ขออภัย
ผมขอเปลี่ยนมันเพื่อให้ค่อนข้างเป็นอยู่ของ 26 ขนาดทั้งหมดแจ้งให้ทราบด้านล่าง
ดัชนีจะเปลี่ยนถึง n ลบ 1
ถ้า 26 เห็นได้ชัดว่ามีขนาดเล็กเกินไปสำหรับมนุษย์ ' ชื่อเพราะมีหลายพัน
ชื่อของโลกที่ให้เพียงทำให้ ใน 100 หรือ 1,000 หรือ 10,000
ขอเพียงจัดสรรพื้นที่มากขึ้น
>> ดีว่าไม่จำเป็นต้องลดลง ความน่าจะเป็นว่าเราจะไม่มีสอง
คนที่มีชื่อเริ่มต้นด้วยและ เพื่อให้คุณได้ไปลองใส่
ชื่อที่ศูนย์สถานที่ยังคง
พวกเขายังคงที่จะไปชนกันซึ่ง หมายความว่าเรายังคงต้องแก้ปัญหาที่จะใส่
อลิซและแอรอนและอลิเซียและอื่น ๆ ชื่อที่เริ่มต้นด้วยที่อื่น ๆ
แต่วิธีการที่มากของปัญหานี้คืออะไร?
ความน่าจะเป็นอะไรที่คุณ มีการชนกันในข้อมูล
โครงสร้างเช่นนี้หรือไม่
>> ดีให้ฉัน - เราจะกลับมา คำถามที่นี่ที่
และดูที่วิธีการที่เราอาจจะ แก้มันเป็นครั้งแรก
ผมขอดึงข้อเสนอนี้ที่นี่
สิ่งที่เราเพียงแค่อธิบายเป็นขั้นตอนวิธี, การแก้ปัญหาที่เรียกว่าเส้น
ละเอียดด้วยเหตุนี้ถ้าคุณพยายามที่จะแทรก บางสิ่งบางอย่างที่นี่ในข้อมูลนี้
โครงสร้างซึ่งเรียกว่าตารางแฮช, และมีห้องพักไม่ได้มีคุณ
อย่างแท้จริงการสอบสวนโครงสร้างข้อมูล การตรวจสอบนี้สามารถใช้ได้?
สามารถใช้ได้นี้นี้สามารถใช้ได้?
นี้สามารถใช้ได้?
และเมื่อในที่สุดมันก็คือค​​ุณใส่ ชื่อที่คุณตั้งใจ
ที่อื่น ๆ ที่ตำแหน่งนั้น
แต่ในกรณีที่เลวร้ายที่สุดจุดเดียว อาจจะมีที่ด้านล่างสุดของข้อมูล
โครงสร้างท้ายสุดของอาร์เรย์
>> เชิงเส้นดังนั้นการตรวจสอบในกรณีที่เลวร้ายที่สุด devolves เป็นอัลกอริทึมเชิงเส้นที่
แอรอนถ้าเขาเกิดขึ้นจะแทรกล่าสุด ในโครงสร้างข้อมูลนี้เขาอาจจะ
ชนกับสถานที่นี้เป็นครั้งแรก แต่ แล้วจบลงด้วยความโชคร้ายที่ส่วนท้ายสุด
ดังนั้นนี้ไม่คงที่ เวลาจอกศักดิ์สิทธิ์สำหรับเรา
วิธีการนี​​้ขององค์ประกอบใส่ลงใน โครงสร้างข้อมูลที่เรียกว่ากัญชา
ตารางไม่ได้ดูเหมือนจะเป็นเวลาที่คงที่ อย่างน้อยก็ไม่ใช่ในกรณีทั่วไป
มันสามารถตกทอดเป็นสิ่งที่เป็นเส้นตรง
>> ดังนั้นสิ่งที่ถ้าเราแก้ปัญหาการชนกัน ค่อนข้างแตกต่างกัน?
ดังนั้นนี่คือความซับซ้อนมากขึ้น ใกล้กับสิ่งที่ยังคง
ที่เรียกว่าตารางแฮช
และกัญชาเป็นกันสิ่งที่ ผมหมายถึงคือดัชนีที่
ผมหมายถึงก่อนหน้านี้
เพื่อสิ่งที่กัญชาสามารถ คิดว่าเป็นคำกริยา
>> ดังนั้นหากคุณกัญชาชื่ออลิซ, ฟังก์ชันแฮชเพื่อที่จะพูด,
ควรกลับจำนวน
ในกรณีนี้เป็นศูนย์ถ้าเธอเป็นที่ สถานที่ตั้งศูนย์หนึ่งถ้าเธอเป็นที่
หนึ่งในสถานที่และอื่น ๆ
ดังนั้นฟังก์ชันแฮชของฉันป่านนี้ได้รับ ง่ายสุดเพียงมองหาที่
ตัวอักษรตัวแรกในชื่อของใครบางคน
แต่ฟังก์ชันแฮชจะใช้เวลาเป็น ป้อนชิ้นส่วนบางส่วนของข้อมูล,
สตริง, int สิ่งที่
และมันมักจะถ่มน้ำลายออกมาเป็นจำนวนมาก
และจำนวนที่อยู่ที่ข้อมูลที่ เป็นองค์ประกอบในโครงสร้างข้อมูล
รู้จักที่นี่ในฐานะตารางแฮช
>> ดังนั้นเพียงแค่สังหรณ์ใจนี้เป็น บริบทที่แตกต่างกันเล็กน้อย
นี้ที่จริงหมายถึงตัวอย่าง วันเกิดที่เกี่ยวข้องกับการที่
อาจจะมีมากที่สุดเท่าที่ 31 วันในเดือน
แต่สมาชิกผู้นี้ไม่ว่าสิ่งที่ตัดสินใจที่จะ ในกรณีที่การปะทะกัน?
บริบทในขณะนี้ถูกไม่ได้ปะทะกันของ ชื่อ แต่การปะทะกันของวันเกิด,
ถ้าคนสองคนที่มีวันคล้ายวันเกิดเดียวกัน 2 ของเดือนตุลาคมเช่น
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: Yeah ดังนั้นที่นี่เรามี ใช้ประโยชน์จากการเชื่อมโยงรายการ
ดังนั้นดูเหมือนน้อยแตกต่างกัน กว่าที่เราดึงมันก่อนหน้านี้
แต่เราดูเหมือนจะมีไปยังอาร์เรย์ บนด้านซ้ายมือ
นั่นเป็นดัชนีหนึ่งสำหรับการไม่มี เหตุผลโดยเฉพาะอย่างยิ่ง
แต่ก็ยังคงอาร์เรย์
มันเป็นอาร์เรย์ของตัวชี้
และแต่ละองค์ประกอบเหล่านั้นแต่ละ วงการเหล่านี้หรือ slashes - เฉือน
null แทน - แต่ละเหล่านี้ เห็นได้ชัดว่าเป็นตัวชี้ชี้ไปที่
สิ่งโครงสร้างข้อมูล?
รายการที่เชื่อมโยง
>> ดังนั้นตอนนี้เรามีความสามารถในการ ยากรหัสในโปรแกรมของเรา
ขนาดของตาราง
ในกรณีนี้เรารู้ว่าไม่เคยมี กว่า 31 วันในเดือน
ดังนั้นค่าการเข้ารหัสยากเช่น 31 คือ ที่เหมาะสมในบริบทที่
ในบริบทของชื่อยาก coding 26 ไม่ใช่ไม่มีเหตุผลมันของผู้คน
เฉพาะชื่อเริ่มต้นด้วยตัวอย่างเช่น ที่เกี่ยวข้องกับตัวอักษรถึง Z
>> เราสามารถอัดพวกเขาทั้งหมดเป็นข้อมูลที่ โครงสร้างตราบเท่าที่เมื่อเราได้รับ
การปะทะกันเราไม่ได้ใส่ชื่อที่นี่ เราคิดแทนของเซลล์เหล่านี้
ไม่ได้เป็นสตริงตัวเอง แต่เป็น ตัวชี้ไปยังตัวอย่างเช่นอลิซ
แล้วอลิซสามารถมีตัวชี้อื่น กับชื่อที่เริ่มต้นด้วยอีก
A. และบ๊อบจริงไปกว่าที่นี่
>> และถ้ามีชื่อเริ่มต้นของผู้อื่น ต่อ B เขาสิ้นสุดขึ้นกว่าที่นี่
และเพื่อให้แต่ละองค์ประกอบของการนี​​้ สองตารางถ้าเราออกแบบนี้
เล็ก ๆ น้อย ๆ อย่างชาญฉลาด -
มา -
ถ้าเราได้รับการออกแบบนี้น้อยมาก ชาญฉลาดในขณะนี้จะกลายเป็นข้อมูลการปรับตัว
โครงสร้างที่ไม่มีขีด จำกัด ยาก เกี่ยวกับวิธีการหลายองค์ประกอบคุณสามารถแทรก
เป็นมันเพราะถ้าคุณมี การปะทะกันที่ดี
เพียงแค่ไปข้างหน้าและต่อท้ายไป สิ่งที่เราเห็นบิตที่ผ่านมาคือ
ที่รู้จักกันเป็นรายการที่เชื่อมโยง
>> หยุดดีขอรอสักครู่
น่าจะเป็นของการปะทะกันคืออะไร ในสถานที่แรก?
ขวาบางทีฉันคิดไปอาจจะ ฉันกว่าวิศวกรรมปัญหานี้
เพราะคุณรู้ว่าสิ่งที่?
ใช่ฉันสามารถขึ้นมาโดยพลการ ตัวอย่างที่ปิดด้านบนของหัวของฉันเช่น
แอลลิสันและแอรอน แต่ในความเป็นจริง ได้รับการจัดจำหน่ายเครื่องแบบ
ปัจจัยการผลิตที่มีบางแทรกสุ่ม เป็นโครงสร้างข้อมูลเป็นสิ่งที่เป็นจริง
น่าจะเป็นของการปะทะกัน?
กันจะเปิดออกก็จริง สูงสุด
ให้ฉันพูดคุยนี้ ปัญหาเป็นเช่นนี้
>> ดังนั้นในห้องพักของ n CS50 นักเรียนอะไร ความน่าจะเป็นว่าอย่างน้อย
นักเรียนสองคนในห้อง มีวันคล้ายวันเกิดเดียวกัน
ดังนั้นจึงไม่มีอะไร Hund ไม่กี่ -
200, 300 คนที่นี่และอีกหลายคน ร้อยคนที่บ้านวันนี้
ดังนั้นถ้าคุณต้องการที่จะถามตัวเองว่ามีอะไร ความน่าจะเป็นของคนสองคน
ในห้องที่มีวันคล้ายวันเกิดเดียวกันนี้ เราสามารถคิดออกนี้
และฉันเรียกร้องจริงมีสอง คนที่มีวันคล้ายวันเกิดเดียวกัน
>> ยกตัวอย่างเช่นไม่มีใคร มีวันคล้ายวันเกิดในวันนี้?
เมื่อวานนี้?
วันพรุ่งนี้?
ขวาทั้งหมดจึงรู้สึกเหมือนฉันไป ที่จะมีการทำเช่นนี้ 363 หรือดังนั้นขึ้น
ครั้งที่จริงคิดออก ถ้าเราจะมีการปะทะกัน
หรือเราก็สามารถทำเช่นนี้ในทางคณิตศาสตร์ มากกว่าที่จะเบื่อหน่าย
การทำเช่นนี้
และนำเสนอต่อไปนี้
>> ดังนั้นผมจึงเสนอว่าเราสามารถสร้างแบบจำลอง ความน่าจะเป็นของคนสองคนที่มี
เช่นเดียวกับวันเกิดน่าจะเป็นของ 1 ลบน่าจะเป็นของหนึ่งจะไม่มี
วันเกิดเดียวกัน
เพื่อที่จะได้รับนี้และนี้เป็นเพียง วิธีแฟนซีของการเขียนนี้สำหรับ
คนแรกในห้องที่เขาหรือเธอ สามารถมีหนึ่งที่เป็นไปได้ใด ๆ
สมมติว่าวันเกิด 365 วันในปี, ขอโทษด้วยที่บุคคลที่มี
วันเกิด 29 กุมภาพันธ์
>> ดังนั้นคนแรกในห้องนี้ฟรี จะมีจำนวนวันเกิดใด ๆ
ออกไปได้ 365 เพื่อให้ เราจะทำอย่างนั้น 365 หารด้วย 365
ซึ่งเป็นหนึ่งใน
คนถัดไปในห้องถ้าเป้าหมาย คือการหลีกเลี่ยงการปะทะกัน, เท่านั้น
มีวันเกิดของเธอหรือของเขาเกี่ยวกับวิธีการ จำนวนวันที่เป็นไปได้แตกต่างกันอย่างไร
364
ดังนั้นในระยะที่สองในการแสดงออกนี้ ทำคณิตศาสตร์เป็นหลักว่าสำหรับเรา
โดยการลบออกในวันหนึ่งที่เป็นไปได้
และจากนั้นในวันรุ่งขึ้นในวันถัดไป วันถัดลงไปจำนวน
ของคนที่อยู่ในห้องพัก
>> และถ้าเราพิจารณาแล้วจากนั้นก็คือสิ่งที่ ความน่าจะเป็นของทุกคนไม่ได้มี
วันเกิดไม่ซ้ำกัน แต่อีก 1 ลบ ว่าสิ่งที่เราได้รับคือการแสดงออก
ที่สามารถนึกมาก ลักษณะเช่นนี้
แต่มันก็น่าสนใจมากขึ้น ไปดูที่สายตา
นี่เป็นแผนภูมิที่อยู่ในแกน x คือ จำนวนของคนที่อยู่ในห้องพัก,
จำนวนของวันเกิด
เมื่อแกน y น่าจะเป็น การปะทะกันของคนสองคน
ที่มีวันคล้ายวันเกิดเดียวกัน
>> and Takeaway จากเส้นโค้งนี้คือ ว่าทันทีที่คุณได้รับจะชอบ 40
นักเรียนคุณขึ้นที่ความน่าจะเป็น 90% combinatorically สอง
คนหรือมากกว่านั้นที่มี วันเกิดเดียวกัน
และเมื่อคุณได้รับจะชอบ 58 คนมัน เกือบ 100% ของโอกาสที่สอง
คนที่อยู่ในห้องจะมี วันเกิดเดียวกันแม้ว่าจะมี
365 หรือ 366 ถังเป็นไปได้และ เพียง 58 คนในห้อง
เพียงแค่สถิติที่คุณอาจจะ ได้รับการชนกันซึ่งในระยะสั้น
กระตุ้นการสนทนานี้
ว่าแม้ว่าเราได้รับแฟนซีที่นี่และ เริ่มมีเครือข่ายเหล่านี้เรายังคง
จะมีการชนกัน
>> เพื่อที่ begs คำถามสิ่งที่เป็น ค่าใช้จ่ายในการดำเนินการแทรกและการลบ
เป็นโครงสร้างข้อมูลเช่นนี้หรือไม่
ดีให้ฉันเสนอ -
และแจ้งให้เรากลับไปที่หน้าจอมากกว่า ที่นี่ - ถ้าเรามีองค์ประกอบ n ใน
รายการดังนั้นหากเรากำลังพยายามที่จะแทรก องค์ประกอบ n และเรามี
วิธีการหลายถังทั้งหมด?
สมมติว่า 31 ถังทั้งหมด ในกรณีของการเกิด
ความยาวสูงสุดของหนึ่งอะไร ของเครือข่ายเหล่านี้อาจเกิดขึ้น?
>> ถ้ามีอีกครั้งที่เป็นไปได้ 31 วันเกิดในเดือนที่กำหนด
และเราเพียงแค่การเกาะกลุ่มทุกคน -
จริงที่เป็นตัวอย่างที่โง่
ขอทำแทน 26
ดังนั้นถ้าจะมีคนที่มีรายชื่อ เริ่มต้นด้วยถึง Z จึงให้
เรา 26 ดังกล่าว
และเรากำลังใช้โครงสร้างข้อมูลเช่น หนึ่งที่เราเพิ่งเห็นเหตุนี้เรามี
อาร์เรย์ของตัวชี้ซึ่งแต่ละ ชี้ไปยังรายการการเชื่อมโยงที่
รายการแรกคือทุกคน ที่มีชื่ออลิซ
รายการที่สองคือทุก ชื่อที่เริ่มต้นด้วยเริ่มต้น
กับ B, และอื่น ๆ
>> ระยะเวลาในแนวโน้มของแต่ละอะไร รายการเหล่านั้นถ้าเราคิดดีสะอาด
การกระจายของชื่อถึง Z ข้ามโครงสร้างข้อมูลทั้ง?
มีคน n ในโครงสร้างข้อมูลของ หารด้วย 26 ถ้าพวกเขาเป็นอย่างดี
กระจายออกไปทั้ง โครงสร้างข้อมูล
ดังนั้นความยาวของแต่ละเหล่านี้ โซ่เป็น n หารด้วย 26
แต่ในสัญกรณ์โอใหญ่ว่าคืออะไร?
ที่จริงคืออะไร?
ดังนั้นจึงเป็นจริงๆ n เพียงขวา?
เพราะเราได้กล่าวว่าในอดีตที่ผ่านมา ว่าฮึคุณหารด้วย 26
ใช่ในความเป็นจริงมันจะเร็ว
แต่ในทางทฤษฎีจะไม่ลึกซึ้ง ทั้งหมดที่ได้เร็วขึ้น
>> ดังนั้นเราจึงไม่ได้ดูเหมือนจะเป็นสิ่งที่มาก ใกล้ชิดกับจอกศักดิ์สิทธิ์นี้
ในความเป็นจริงนี้เป็นเพียงเส้นเวลา
Heck, ที่จุดนี้ไม่ได้ว่าทำไมเรา ใช้เพียงหนึ่งรายการที่เชื่อมโยงอย่างมาก?
ทำไมเราไม่ใช้เพียงหนึ่งขนาดใหญ่ อาร์เรย์ในการจัดเก็บชื่อของ
ทุกคนในห้อง?
ดีคือยังคงมีบางสิ่งบางอย่าง ที่น่าสนใจเกี่ยวกับตารางกัญชา?
คือยังคงมีบางสิ่งบางอย่างที่น่าสนใจ เกี่ยวกับโครงสร้างข้อมูล
ที่มีลักษณะเช่นนี้หรือไม่
นี้
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงขวาและอีกครั้งจะเป็นเพียง อัลกอริทึมเวลาเชิงเส้นและ
เวลาโครงสร้างเชิงเส้นข้อมูลทำไมถึงไม่ได้ เพียงแค่เก็บชื่อของทุกคนในขนาดใหญ่
อาร์เรย์หรือในรายการที่เชื่อมโยงใหญ่?
และหยุดการทำ CS ดังนั้นยากมาก กว่าจะต้องมี?
เป็นที่น่าสนใจเกี่ยวกับเรื่องนี้สิ่งที่แม้ แม้ว่าฉันมีรอยขีดข่วนมันออกมา?
>> ลูกศิษย์: [ได้ยิน]
>> 1 SPEAKER: แทรกไม่ได้?
ราคาแพงอีกต่อไป
ดังนั้นการแทรกอาจจะยังคง เป็นเวลาที่คงที่แม้ว่าข้อมูลของคุณ
โครงสร้างลักษณะเช่นนี้, array ของ ตัวชี้แต่ละที่ชี้ไปที่
อาจเป็นรายการที่เชื่อมโยง
วิธีที่คุณสามารถบรรลุคงที่ แทรกเวลาของชื่อ?
ติดในด้านหน้าขวา?
>> ถ้าเราเสียสละเป้าหมายการออกแบบจาก ก่อนหน้านี้ที่เราอยากให้
ชื่อของทุกคนเช่นเรียงลำดับ หรือทั้งหมดของตัวเลขที่อยู่บนเวทีที่เรียงลำดับ
สมมติว่าเรามี รายการที่เชื่อมโยงคัดเลือก
มันเพียงค่าใช้จ่ายเราหนึ่งหรือสองขั้นตอน เช่นเดียวกับในกรณีของเบนและไบรอัน
ก่อนหน้านี้ที่จะแทรกองค์ประกอบที่ จุดเริ่มต้นของรายการ
ดังนั้นหากเราไม่ดูแลเกี่ยวกับการเรียงลำดับทั้งหมด ของชื่อที่เริ่มต้นด้วยส่วนหรือทั้งหมด
ชื่อที่เริ่มต้นด้วย B เราสามารถยังคง บรรลุแทรกตลอดเวลา
ตอนนี้มองขึ้นไปอลิซหรือบ๊อบหรือชื่อใด ๆ มากขึ้นโดยทั่วไปยังคงเป็นอะไร
มัน O ใหญ่ของ N หารด้วย 26 ใน กรณีที่ในฝันที่ทุกคนเหมือนกัน
กระจายที่มีจำนวนมากเป็นของ ที่มีซีซึ่งอาจเป็น
ไม่สมจริง
แต่ที่ยังคงเป็นเส้นตรง
>> แต่ที่นี่เราจะกลับมาที่จุด สัญกรณ์เชิงเป็น
จริงในทางทฤษฎี
แต่ในโลกแห่งความเป็นจริงถ้าผมอ้างว่า โปรแกรมของฉันสามารถทำบางสิ่งบางอย่าง 26 ครั้ง
ได้เร็วขึ้นกว่าของคุณซึ่งมีโปรแกรม ที่คุณจะชอบใช้?
ขอแสดงความนับถือหรือเหมืองซึ่ง เป็นครั้งที่ 26 เร็วขึ้น?
แนบเนียนบุคคลที่มีเป็น 26 ครั้งเร็วแม้ว่าในทางทฤษฎี
อัลกอริทึมของเราทำงานในที่เดียวกัน เวลาการทำงานเชิง
>> ผมขอเสนอที่แตกต่างกัน การแก้ปัญหาทั้งหมด
และถ้านี้ไม่ได้พัดใจของคุณ เราออกจากโครงสร้างข้อมูล
ดังนั้นนี่จึงเป็นคู่ชีวิต -
ชนิดของชื่อโง่
มันมาจากการสืบค้นและคำว่า คือการสะกดคำคู่ชีวิต, T-r-I-e เพราะ
ดึงแน่นอนเสียงเหมือนคู่ชีวิต
แต่ที่ประวัติศาสตร์ จากคำ Trie
>> ดังนั้นคู่ชีวิตย่อมเป็นชนิดของต้นไม้บาง และก็ยังมีการเล่นคำว่า
และถึงแม้ว่าคุณไม่สามารถค่อนข้างจะเห็นมัน กับการสร้างภาพนี้เป็นคู่ชีวิต
ต้นไม้มีโครงสร้างเหมือนต้นไม้ครอบครัวที่มี หนึ่งบรรพบุรุษที่ด้านบนและจำนวนมาก
ของลูกหลานและเหลน เป็นใบที่ด้านล่าง
แต่โหนด Trie ในแต่ละแถว
และมันก็เป็นในอาร์เรย์ - และขอ oversimplify สักครู่ - มัน
อาร์เรย์ในกรณีนี้จาก 26 ขนาดที่ แต่ละโหนดอีกครั้งเป็นอาร์เรย์ขนาด
26 ที่ 0 องค์ประกอบในการที่ อาร์เรย์เป็นตัวแทนและสุดท้าย
องค์ประกอบดังกล่าวในแต่ละ อาร์เรย์แทนซี
>> ดังนั้นผมจึงนำเสนอแล้วว่าข้อมูลนี้ โครงสร้างที่รู้จักกันเป็นคู่ชีวิตสามารถ
นอกจากนี้ยังใช้ในการจัดเก็บคำ
เราเห็นสักครู่ที่ผ่านมาวิธีการที่เราสามารถเก็บ คำหรือในกรณีที่ชื่อนี้และเรา
เห็นก่อนหน้านี้วิธีการที่เราสามารถจัดเก็บตัวเลข แต่ถ้าเรามุ่งเน้นไปที่ชื่อหรือสตริง
ที่นี่แจ้งให้ทราบว่ามีอะไรที่น่าสนใจ
ผมอ้างว่าเป็นชื่อของแมกซ์เวล ภายในของโครงสร้างข้อมูลนี้
คุณจะดูแมกซ์เวลที่ไหน?
>> ลูกศิษย์: [ได้ยิน]
>> 1 ลำโพงด้านซ้าย
ดังนั้นที่น่าสนใจกับข้อมูลนี้สิ่ง โครงสร้างเป็นมากกว่าร้านค้า
สตริง M--X-W-E-L-L เครื่องหมายทับขวาเป็นศูนย์ทั้งหมด ติดกันสิ่งที่คุณทำแทน
คือต่อไปนี้
ถ้าเป็นคู่ชีวิตเช่นโครงสร้างข้อมูล, แต่ละโหนดที่เป็นอีกครั้งที่อาร์เรย์
และคุณต้องการเก็บแมกซ์เวลแรกคุณ ดัชนีและเพื่อให้โหนดรากของดังนั้น
การพูดโหนดบนสุด, ที่ตั้ง M ขวาดังนั้น
ลวกเข้ากลาง
แล้วจากที่นั่นคุณทำตาม ตัวชี้ไปยังโหนดลูกเพื่อที่จะพูด
ดังนั้นในความรู้สึกต้นไม้ครอบครัว, คุณทำตามมันลง
และที่นำคุณไปยังโหนดอื่น ด้านซ้ายมีซึ่งเป็น
เพียงอาร์เรย์อีก
>> แล้วถ้าคุณต้องการที่จะเก็บเวลล์, คุณพบว่าตัวชี้ที่แสดงถึง
ซึ่งเป็นหนึ่งในนี้ที่นี่
แล้วคุณจะไปโหนดถั​​ดไป
และแจ้งให้ทราบล่วงหน้า - นี่คือเหตุผลที่รูปภาพ หลอกลวงน้อย -
โหนดนี้ดูสุดยอดเล็ก
แต่ทางด้านขวาของนี้เป็น Y และ Z. เป็นเพียงผู้เขียนได้ถูกตัดทอน
ภาพเพื่อให้คุณจริง เห็นสิ่งที่
มิฉะนั้นภาพ จะกว้างอย่างมหาศาล
ดังนั้นตอนนี้คุณดัชนีลงในตำแหน่ง X แล้ว W, E นั้นแล้ว L แล้วลิตรแล้วว่ามีอะไร
อยากรู้อยากเห็นนี้
>> ดีถ้าเราใช้การเรียงลำดับของใหม่นี้ ใช้เวลาในวิธีการเก็บสตริงใน
โครงสร้างข้อมูลคุณยังคงต้อง เป็นหลักตรวจสอบออกในข้อมูล
โครงสร้างคำว่าสิ้นสุดที่นี่
ในคำอื่น ๆ แต่ละโหนดเหล่านี้ อย่างใดมีต้องจำไว้ว่าเรา
ตามจริงทั้งหมดของคำแนะนำเหล่านี้ และกำลังจะออกไปเล็กน้อย
เศษขนมปังที่ด้านล่างของที่นี่นี้ โครงสร้างเพื่อแสดง M--X-W-E-L-L คือ
แน่นอนในโครงสร้างข้อมูลนี้
>> ดังนั้นเราอาจจะทำดังต่อไปนี้
แต่ละโหนดในภาพที่เราเพียงแค่ เห็นมีอาร์เรย์ของ 27 ขนาด
และก็ตอนนี้ 27 เพราะใน p ตั้งหก เราจริงจะให้ apostrophe,
เพื่อให้เราสามารถมีชื่อเช่น O'Reilly และอื่น ๆ ที่มี apostrophes
แต่ความคิดเดียวกัน
แต่ละองค์ประกอบเหล่านั้นใน จุดอาร์เรย์ struct
โหนดดังนั้นเพียงโหนด
ดังนั้นนี่คือชวนให้นึกถึงมาก ของรายการที่เชื่อมโยงของเรา
>> และแล้วฉันมีบูลีนซึ่งผมจะ เรียกคำซึ่งเป็นเพียงการไปได้
จริงถ้าคำว่าสิ้นสุดที่นี้ โหนดในต้นไม้
มันมีประสิทธิภาพแสดงเล็ก ๆ น้อย ๆ สามเหลี่ยมที่เราเห็นในช่วงเวลาที่ผ่านมา
ดังนั้นถ้าคำว่าสิ้นสุดที่โหนดในที่ ต้นไม้ฟิลด์คำที่จะเป็นจริง,
ซึ่งมีแนวคิดการตรวจสอบปิดหรือ เรากำลังวาดรูปสามเหลี่ยมนี้ใช่มี
คำที่นี่
>> ดังนั้นนี่คือคู่ชีวิต
และตอนนี้คำถามคือสิ่งที่ กำลังทำงานอยู่ในขณะนี้?
มันเป็น O ใหญ่ของ n?
มันเป็นบางสิ่งบางอย่างอื่นใช่หรือไม่
ดีถ้าคุณได้ n ชื่อในข้อมูลนี้ โครงสร้างแม็กซ์เป็นเพียงหนึ่งใน
พวกเขาเป็นเวลาการทำงานของสิ่งที่ ใส่หรือหาแมกซ์เวล?
เวลาทำงานอะไร ใส่แมกซ์เวล?
ถ้ามีชื่ออื่น ๆ ของ N อยู่ในตารางแล้ว?
อ้าง?
>> ลูกศิษย์: [ได้ยิน]
>> ลำโพง 1: ใช่มันเป็นระยะเวลา ของชื่อใช่มั้ย?
ดังนั้น M--x-w-e-l-l จึงรู้สึกเช่นนี้ อัลกอริทึมคือ O ใหญ่เจ็ด
ตอนนี้แน่นอนชื่อ จะแตกต่างกันในความยาว
บางทีมันอาจจะเป็นชื่อที่สั้น
บางทีมันอาจจะเป็นชื่อที่ยาว
แต่สิ่งที่สำคัญที่นี่คือ มันเป็นจำนวนคงที่
และบางทีมันอาจจะไม่คงที่จริงๆ แต่พระเจ้าถ้าแนบเนียนใน
พจนานุกรมอาจมีข้อ จำกัด บางอย่าง กับจำนวนของตัวอักษรใน
ชื่อของบุคคลในประเทศโดยเฉพาะอย่างยิ่ง
>> และเพื่อให้เราสามารถคิดว่า ค่าคงที่
ผมไม่ทราบว่ามันคืออะไร
มันอาจจะมีขนาดใหญ่กว่า เราคิดว่ามันเป็น
เพราะมีเสมอบางมุม กรณีที่มีชื่อยาวบ้า
ดังนั้นขอเรียกว่า K แต่มันก็ยังคงเป็น สันนิษฐานว่าคงเพราะทุก
ชื่อในโลกอย่างน้อยใน ประเทศใดประเทศหนึ่งเป็นระยะเวลาหรือว่า
สั้นจึงคงที่
แต่เมื่อเราได้กล่าวว่าสิ่งที่มีขนาดใหญ่ O ของค่าคงที่สิ่งที่ว่า
จริงๆเทียบเท่ากับ?
นั่นคือสิ่งเดียวกัน เป็นคำพูดตลอดเวลา
>> ตอนนี้เราชนิดของการโกงใช่มั้ย?
เราใช้ประโยชน์จากชนิดของทฤษฎีบาง ที่นี่เพื่อบอกว่าดีคำสั่งของ k คือ
จริงๆเพียงแค่สั่งซื้อจากหนึ่ง และก็ถึงเวลาที่คงที่
แต่มันคือเรื่องจริง
เพราะข้อมูลเชิงลึกที่สำคัญที่นี่คือ ถ้าเราได้ n ชื่ออยู่แล้วในการนี​​้
โครงสร้างข้อมูลและเราใส่แมกซ์เวล, เป็นระยะเวลาที่จะใช้เวลาที่เราจะ
ใส่แม็กซ์ที่ได้รับผลกระทบทั้งหมด โดยวิธีการหลายคนอื่น ๆ
อยู่ในโครงสร้างข้อมูล?
ไม่ได้ดูเหมือนจะเป็น
ถ้าฉันมีพันล้านองค์ประกอบมากขึ้นในการนี​​้ Trie แล้วใส่แมกซ์เวลเป็น
เขาที่ทุกคนได้รับผลกระทบ?
เลขที่
และที่แตกต่างของข้อมูลใด ๆ วัน โครงสร้างที่เราเคยเห็นป่านนี้ที่
เวลาทำงานของอัลกอริทึมของคุณเป็น อิสระอย่างสมบูรณ์ของเท่าใด
สิ่งที่เป็นหรือไม่ได้เป็นแล้ว ในโครงสร้างข้อมูลที่
>> และอื่น ๆ ที่มีกำบังคุณในขณะนี้คือ โอกาสสำหรับ p ชุดหกซึ่งจะ
อีกครั้งที่เกี่ยวข้องกับการดำเนินการของคุณเอง ตรวจสอบการสะกดในการอ่าน 150,000
คำวิธีการที่ดีที่สุดในการจัดเก็บที่ ไม่ชัดเจนจำเป็นต้อง
และแม้ว่าผมได้แรงบันดาลใจที่จะหา จอกศักดิ์สิทธิ์ที่ฉันทำไม่ได้
ที่อ้างว่าเป็นคู่ชีวิต
ในความเป็นจริงตารางแฮชอาจได้เป็นอย่างดี พิสูจน์ให้เป็นที่มีประสิทธิภาพมากขึ้น
แต่ผู้ที่เป็นเพียง -
นั่นเป็นเพียงหนึ่งในการตัดสินใจการออกแบบ คุณจะต้องทำ
>> แต่ในการปิดลองมา 50 หรือดังนั้น วินาทีที่จะมองที่สิ่งที่อยู่
ไปข้างหน้าต่อไปสัปดาห์และการเปลี่ยนแปลงเกินกว่าเรา จากบรรทัดคำสั่งนี้
โลกถ้าโปรแกรม C ถึงสิ่งที่เว็บ และตามภาษาเช่น PHP และ
JavaScript และอินเทอร์เน็ตของตัวเอง โปรโตคอลเช่น HTTP ซึ่งคุณได้
ที่สำหรับรับเป็นเวลาหลายปี ในขณะนี้และทุกพิมพ์มากที่สุด
วันบางทีหรือเห็น
และเราจะเริ่มต้นในการปอกเปลือกกลับ ชั้นของสิ่งที่เป็นอินเทอร์เน็ต
และรหัสคือสิ่งที่ รองรับเครื่องมือของวันนี้
ดังนั้น 50 วินาทีทีเซอร์นี้ที่นี่
ฉันให้คุณนักรบแห่งสุทธิ
>> [เล่นภาพวิดีโอ]
>> -เขาเดินเข้ามาพร้อมกับข้อความ
กับโปรโตคอลทั้งหมดของเขาเอง
เขามาถึงโลกของไฟร์วอลล์โหดร้าย, เราเตอร์เอาใจใส่และอันตรายไกล
ที่เลวร้ายยิ่งกว่าความตาย
เขาได้อย่างรวดเร็ว
เขาเป็นคนที่แข็งแกร่ง
เขา TCPIP
และเขามีที่อยู่ของคุณ
นักรบแห่งสุทธิ
>> [เล่นวิดีโอจบ]
>> ลำโพง 1: นั่นคือวิธีที่อินเทอร์เน็ต จะทำงานในฐานะของสัปดาห์ต่อไป