>> เควิน SCHMID: บางครั้งเมื่อมีการสร้าง โปรแกรมคุณอาจต้องการที่จะใช้
โครงสร้างข้อมูลที่รู้จักกันในพจนานุกรม
คีย์แผน​​ที่พจนานุกรมซึ่งเป็น มักจะสายไปยังค่า ints,
ตัวอักษรตัวชี้ไปยังวัตถุบางอย่าง สิ่งที่เราต้องการ
ก็เช่นเดียวกับพจนานุกรมสามัญ ว่าคำพูดของแผนที่ผ่านคำจำกัดความ
>> พจนานุกรมให้เราด้วย ความสามารถในการเก็บข้อมูล
ที่เกี่ยวข้องกับสิ่งที่ และมองมันได้ในภายหลัง
ดังนั้นทำอย่างไรเราจริงใช้ ในพจนานุกรมพูดรหัส C ที่เราสามารถทำได้
ใช้ในการอย่างใดอย่างหนึ่งของโปรแกรมของเราหรือไม่
ดีมีหลายวิธีที่ เราสามารถใช้พจนานุกรม
>> สำหรับหนึ่งเราสามารถใช้อาร์เรย์ที่เรา แบบไดนามิกอีกครั้งขนาดหรือเราสามารถใช้
รายการที่เชื่อมโยง, ตารางแฮช หรือต้นไม้ไบนารี
แต่สิ่งที่เราเลือกที่เราควรจะ มีสติในการที่มีประสิทธิภาพและ
ผลการดำเนินงานของการดำเนินการ
เราควรจะคิดเกี่ยวกับขั้นตอนวิธีการที่ใช้ การแทรกและมองหารายการลง
โครงสร้างข้อมูลของเรา
>> สำหรับตอนนี้สมมติว่าเรา ต้องการที่จะใช้สตริงเป็นคีย์
ขอพูดคุยเกี่ยวกับความเป็นไปได้ โครงสร้างข้อมูลที่เรียกว่า Trie ที่
ดังนั้นนี่คือการแสดงออก ของ Trie
>> เป็นภาพที่แสดงให้เห็น, Trie ที่ เป็นโครงสร้างข้อมูลต้นไม้ที่มี
โหนดที่เชื่อมโยงกัน
เราจะเห็นว่ามีรากอย่างชัดเจน โหนดมีการเชื่อมโยงบางส่วนยื่นออกไป
โหนดอื่น ๆ
แต่สิ่งที่ไม่แต่ละโหนดประกอบด้วย?
ถ้าเราคิดว่าเรากำลังจัดเก็บคีย์ ด้วยตัวอักษรตามตัวอักษรเท่านั้นและ
เราไม่สนใจเกี่ยวกับตัวอักษร นี่คือนิยามของโหนดที่
จะพอเพียง
>> วัตถุที่มีชนิดเป็นโครงสร้าง โหนดมีสองส่วน
เรียกว่าข้อมูลและเด็ก
เราได้ทิ้งส่วนข้อมูลเป็นความคิดเห็น จะถูกแทนที่ด้วยองค์ประกอบ
ประกาศเมื่อโหนด struct เป็น ที่จัดตั้งขึ้นในโปรแกรม C
ส่วนข้อมูลของโหนดอาจจะ ค่าบูลีนที่จะระบุหรือ
ไม่ได้แสดงให้เห็นถึงโหนดเสร็จสิ้น คีย์พจนานุกรมหรือมันอาจจะเป็น
สตริงที่แสดงความหมายของ ของคำในพจนานุกรม
>> เราจะใช้ใบหน้าที่ยิ้มเพื่อแสดง เมื่อข้อมูลที่มีอยู่ในโหนด
มี 2​​6 องค์ประกอบในที่ของเรา เด็กแถวหนึ่งดัชนี
ต่อตัวอักษร
เราจะเห็นความสำคัญ ของในไม่ช้านี้
>> ให้ได้รับการมองที่ใกล้ชิดของโหนดราก ในแผนภาพของเราซึ่งมีข้อมูลไม่
ที่เกี่ยวข้องกับมันตามที่ระบุโดย ตัวตนของใบหน้าที่ยิ้มใน
ส่วนข้อมูล
ลูกศรยื่นออกมาจากส่วนของ อาร์เรย์เด็กแทนไม่โหนด
ตัวชี้ไปยังโหนดอื่น ๆ
ตัวอย่างเช่นลูกศรที่ยื่นออกมาจาก องค์ประกอบที่สองของเด็ก
หมายถึงตัวอักษร B ในคีย์พจนานุกรม
และในแผนภาพขนาดใหญ่ เราป้ายกับบี
>> โปรดทราบว่าในแผนภาพขนาดใหญ่เมื่อเรา วาดตัวชี้ไปยังโหนดอื่นก็
ไม่สำคัญที่หัวลูกศร มีคุณสมบัติตรงตามที่โหนดอื่น ๆ
Trie ตัวอย่างพจนานุกรมของเรามี คำสองคำที่และซูม
ลองเดินผ่านตัวอย่างของ เงยหน้าขึ้นมองข้อมูลที่สำคัญ
>> สมมติว่าเราต้องการที่จะเงยหน้าขึ้นมอง ค่าที่สอดคล้องกันสำหรับการอาบน้ำที่สำคัญ
เราจะเริ่มมองของเราขึ้น ที่โหนดราก
จากนั้นเราจะพาตัวอักษรตัวแรกของเรา ที่สำคัญ, B, และหาที่เกี่ยวข้อง
จุดในเด็กแถวของเรา
ขอให้สังเกตว่ามีตรงจุดที่ 26 ในอาร์เรย์หนึ่งสำหรับตัวอักษรของแต่ละ
ตัวอักษร
และเราจะมีจุดที่เป็นตัวแทนของ ตัวอักษรของตัวอักษรในการสั่งซื้อ
>> เราจะดูที่ดัชนีที่สองแล้ว ดัชนีหนึ่งสำหรับบีโดยทั่วไปถ้าเรา
มีบางตัวอักษร C ที่เราตามตัวอักษร สามารถกำหนดจุดที่ตรงกัน
ในอาร์เรย์เด็กใช้ การคำนวณเช่นนี้
เราจะได้ใช้เด็กขนาดใหญ่ อาร์เรย์ถ้าเราต้องการที่จะให้มองขึ้นของ
คีย์ที่มีช่วงกว้างของตัวอักษร เช่นทั้ง
ชุดอักขระ ASCII
>> ในกรณีนี้ชี้ ในอาร์เรย์เด็กของเราได้ที่
ดัชนีหนึ่งที่ไม่เป็นโมฆะ
ดังนั้นเราจะยังคงมองหา ขึ้นอาบน้ำที่สำคัญ
ถ้าเราเคยพบตัวชี้โมฆะ ที่จุดที่เหมาะสมในเด็ก
อาเรย์ในขณะที่เราสำรวจโหนด, แล้วเราจะต้องบอกว่าเราว่า
ไม่สามารถหาอะไรที่สำคัญที่
>> ตอนนี้เราจะพาจดหมายฉบับที่สองของ ที่สำคัญของเราและยังคงดังต่อไปนี้
ชี้วิธีนี้จนกว่าเราจะ ถึงจุดสิ้นสุดของที่สำคัญของเรา
ถ้าเราถึงจุดสิ้นสุดของสำคัญโดยไม่ต้อง ตีปลายตายใด ๆ ตัวชี้โมฆะ
เช่นเดียวกับกรณีที่นี่แล้วเราเท่านั้น มีการตรวจสอบอีกหนึ่งสิ่ง
เป็นกุญแจสำคัญนี้จริง ในพจนานุกรมหรือไม่
>> ถ้าเป็นเช่นนั้นเราควรจะหาค่าดี ไอคอนหน้ายิ้มในแผนภาพของเราที่
คำลงท้าย
หากมีสิ่งอื่นที่เก็บไว้กับ ข้อมูลแล้วเราสามารถส่งคืนได้
ตัวอย่างเช่นสวนสัตว์ที่สำคัญคือไม่ได้อยู่ใน พจนานุกรมแม้ว่าเราอาจจะมี
ถึงจุดสิ้นสุดของคีย์นี้โดยไม่เคย กดปุ่มตัวชี้โมฆะในขณะที่เรา
ย้ำผ่าน Trie ที่
>> ถ้าเราพยายามที่จะมองขึ้นไปอาบน้ำที่สำคัญ สองดัชนีอาร์เรย์โหนดสุดท้ายของ
สอดคล้องกับตัวอักษร H จะ ได้จัดขึ้นชี้โมฆะ
ดังนั้นการอาบน้ำไม่ได้อยู่ในพจนานุกรม
และเพื่อ Trie ที่เป็นเอกลักษณ์ในการที่คีย์ จะไม่ถูกเก็บไว้อย่างชัดเจนใน
โครงสร้างข้อมูล
ดังนั้นทำอย่างไรเราใส่บางสิ่งบางอย่าง ใน Trie?
>> ลองใส่กุญแจ สวนสัตว์ใน Trie ของเรา
โปรดจำไว้ว่าใบหน้าที่ยิ้มที่โหนด สามารถสอดคล้องในรหัสง่าย
ค่าบูลีนเพื่อแสดงให้เห็นว่าสวนสัตว์ อยู่ในพจนานุกรมหรือมันอาจจะ
สอดคล้องกับข้อมูลเพิ่มเติมที่เรา ต้องการที่จะเชื่อมโยงกับสวนสัตว์ที่สำคัญ
เช่นคำนิยามของ คำหรือสิ่งอื่น
ในบางวิธีการที่จะแทรก สิ่งที่เข้ามาใน Trie ที่มีความคล้ายคลึงกับ
กำลังมองหาบางสิ่งบางอย่างใน Trie ที่
>> เราจะเริ่มต้นด้วยโหนดรากอีกครั้ง คำแนะนำดังต่อไปนี้สอดคล้องกับ
จดหมายที่สำคัญของเรา
โชคดีที่เราสามารถที่จะปฏิบัติตามคำแนะนำ ตลอดทางจนกว่าเราจะมาถึง
ในตอนท้ายของคีย์
ตั้งแต่สวนสัตว์เป็นคำนำหน้าของคำว่า ซูมซึ่งเป็นสมาชิกของ
พจนานุกรมเราไม่จำเป็นต้อง จัดสรรโหนดใหม่ ๆ
>> เราสามารถปรับเปลี่ยนโหนดเพื่อบ่งชี้ว่า เส้นทางของตัวอักษรที่นำไปสู่
มันเป็นกุญแจสำคัญในพจนานุกรมของเรา
ตอนนี้ขอลองใส่ บาทสำคัญใน Trie ที่
เราจะเริ่มต้นที่โหนดราก และปฏิบัติตามคำแนะนำอีกครั้ง
แต่ในสถานการณ์นี้เราตีตาย จบก่อนที่เราจะสามารถที่จะได้รับการ
ในตอนท้ายของคีย์
ตอนนี้เราจะต้องจัดสรรบางส่วนใหม่ โหนดจะต้องจัดสรรใหม่
สำหรับแต่ละโหนดที่เหลืออยู่ จดหมายที่สำคัญของเรา
>> ในกรณีนี้เราก็ต้อง ในการจัดสรรหนึ่งโหนดใหม่
แล้วเราจะต้องทำดัชนี H อ้างอิงโหนดใหม่นี้
อีกครั้งหนึ่งที่เราสามารถปรับเปลี่ยนโหนดที่ แสดงให้เห็นว่าเส้นทางของตัวละคร
นำไปสู่​​การที่จะแสดงให้เห็นถึง ที่สำคัญในพจนานุกรมของเรา
ให้เหตุผลเกี่ยวกับซีมโทติ ความซับซ้อนของขั้นตอนของเราเหล่านี้
สองงาน
>> เราสังเกตเห็นว่าในทั้งสองกรณีจำนวน ของขั้นตอนขั้นตอนวิธีการของเราคือการเอา
สัดส่วนกับจำนวนของ ตัวอักษรในคำหลัก
ที่เหมาะสม
เมื่อคุณต้องการที่จะมองหาคำใน Trie ที่คุณเพียงแค่ต้องย้ำผ่าน
ตัวอักษรหนึ่งโดยหนึ่งจนกว่าคุณจะได้ทั้ง ถึงจุดสิ้นสุดของคำหรือ
ตีปลายตายใน Trie ที่
>> และเมื่อคุณต้องการที่จะแทรกที่สำคัญ ค่าคู่เป็น Trie ที่ใช้
ขั้นตอนที่เราได้พูดถึงกรณีที่เลวร้ายที่สุด จะช่วยให้คุณจัดสรรโหนดใหม่
สำหรับแต่ละตัวอักษร
และเราจะถือว่าการจัดสรรที่ เป็นเวลาการดำเนินงานอย่างต่อเนื่อง
ดังนั้นถ้าเราคิดว่าระยะเวลาที่สำคัญคือ จำกัด โดยค่าคงที่คงที่ทั้ง
แทรกและมองขึ้นอย่างต่อเนื่อง เวลาสำหรับการดำเนินงาน Trie ที่
>> ถ้าเราไม่ได้ทำสมมติฐานนี้ว่า ระยะเวลาที่สำคัญเป็นที่สิ้นสุดโดยถาวร
คงที่แล้วแทรกและการมองขึ้น ในกรณีที่เลวร้ายที่สุดที่มีในเชิงเส้น
ความยาวของคีย์
ขอให้สังเกตว่าจำนวนรายการที่เก็บไว้ ใน Trie ที่ไม่ได้ส่งผลกระทบต่อรูปลักษณ์ขึ้น
หรือเวลาที่แทรก
มันเป็นผลกระทบโดยเฉพาะ ความยาวของคีย์
>> ในทางตรงกันข้ามการเพิ่มรายการที่จะพูด ตารางแฮชมีแนวโน้มที่จะทำให้
อนาคตมองขึ้นช้าลง
ขณะนี้อาจจะน่าสนใจในตอนแรก เราควรจะเก็บไว้ในใจว่า
ความซับซ้อนซีมโทติที่ดีไม่ได้ หมายความว่าในทางปฏิบัติข้อมูล
โครงสร้างจำเป็นต้อง เกินประณาม
นอกจากนี้เรายังต้องพิจารณาว่าในการจัดเก็บ คำใน Trie ที่เราต้องการในที่เลวร้ายที่สุด
กรณีจำนวนโหนดสัดส่วน ความยาวของคำที่ตัวเอง
>> พยายามที่มักจะใช้พื้นที่มาก
นั่นคือในทางตรงกันข้ามกับตารางแฮช, ที่เราต้องการเพียงหนึ่งโหนดใหม่
คู่เก็บค่าบางอย่างที่สำคัญ
ตอนนี้อีกครั้งในทฤษฎีพื้นที่ขนาดใหญ่ การบริโภคไม่ได้ดูเหมือนใหญ่
จัดการโดยเฉพาะอย่างยิ่งที่ทันสมัย คอมพิวเตอร์มีกิกะไบต์และ
กิกะไบต์หน่วยความจำ
แต่มันกลับกลายเป็นว่าเรายังคงมี กังวลเกี่ยวกับการใช้งานหน่วยความจำและ
องค์กรเพื่อประโยชน์ของ ผลการดำเนินงานตั้งแต่เครื่องคอมพิวเตอร์ที่ทันสมัย
มีกลไกในสถานที่ภายใต้ เครื่องดูดควันเพื่อเพิ่มความเร็วในการเข้าถึงหน่วยความจำ
>> แต่กลไกเหล่านี้ทำงานได้ดีที่สุดเมื่อ การเข้าถึงหน่วยความจำจะทำในขนาดกะทัดรัด
ภูมิภาคหรือพื้นที่
และโหนดของ Trie สามารถอาศัยอยู่ ที่ใดก็ได้ในกองที่
แต่เหล่านี้จะไม่ชอบการค้า ที่เราจะต้องพิจารณา
>> โปรดจำไว้ว่าเมื่อเลือกข้อมูล โครงสร้างสำหรับงานบางอย่างเรา
ควรคิดเกี่ยวกับสิ่งที่ชนิดของ การดำเนินงานโครงสร้างข้อมูลความต้องการที่จะ
การสนับสนุนและวิธีการที่มีประสิทธิภาพมาก ของแต่ละคน
เรื่องการดำเนินงานของเรา
ดำเนินการเหล่านี้อาจจะได้ ขยายเกินเพียงแค่
ขึ้นมองพื้นฐานและการแทรก
สมมติว่าเราต้องการที่จะใช้ชนิด ของการทำงานอัตโนมัติสมบูรณ์มาก
เช่นเครื่องมือค้นหา Google ไม่
นั่นคือกลับคีย์ทั้งหมดและ ค่าที่อาจเกิดขึ้นซึ่ง
มีคำนำหน้าให้
>> Trie ที่เป็นประโยชน์ที่ไม่ซ้ำกัน สำหรับการดำเนินงานนี้
มันตรงไปตรงมาย้ำผ่าน Trie ที่ตัวละครของแต่ละคน
คำนำหน้า
เช่นเดียวกับการดำเนินงานที่มีลักษณะขึ้น เราจะปฏิบัติตามคำแนะนำ
ตัวอักษรด้วยตัวอักษร
จากนั้นเมื่อเรามาถึงจุดสิ้นสุดของ คำนำหน้าเราสามารถย้ำผ่าน
ส่วนที่เหลือของโครงสร้างข้อมูล ตั้งแต่ปุ่มใด ๆ เกิน
จุดนี้มีคำนำหน้า
>> นอกจากนี้ยังเป็นเรื่องง่ายที่จะได้รับรายชื่อนี้ ตามลำดับตัวอักษรตั้งแต่
องค์ประกอบของอาร์เรย์เด็ก มีคำสั่งตามลำดับตัวอักษร
เพื่อหวังว่าคุณจะพิจารณา ให้พยายามลอง
ฉันเควินชมิดและนี่คือ CS50
>> Ah, นี้เป็นจุดเริ่มต้น การลดลงของ
ฉันขอโทษ
ขอโทษ
>> ตีสี่
ฉันออก
ขอโทษ
ขอโทษนะที่ทำให้คนที่ มีการแก้ไขนี้ไปบ้า
>> ขอโทษ
ขอโทษ
>> ลำโพง 1: ทำดี
ที่ทำดีจริงๆ