>> ROB สลิง: สวัสดี
ฉันร็อบและกัญชาที่ขอ การแก้ปัญหานี้ออก
ดังนั้นที่นี่เรากำลังจะดำเนินการ ตารางแฮชทั่วไป
เราจะเห็นว่าโครงสร้างของโหนดกัญชาของเรา ตารางจะมีลักษณะเช่นนี้
ดังนั้นมันจะมีคำถ่าน อาร์เรย์ของความยาวขนาดบวก 1
อย่าลืมที่ 1 ตั้งแต่สูงสุด คำในพจนานุกรม 45
ตัวละครแล้วเราจะ จำเป็นต้องใช้ตัวอักษรพิเศษสำหรับ
เครื่องหมาย 0
>> แล้วตารางแฮชของเราในแต่ละ ถังเป็นไปในการจัดเก็บ
รายการที่เชื่อมโยงของโหนด
เราไม่ได้ทำที่นี่ละเอียดเชิงเส้น
และอื่น ๆ เพื่อที่จะเชื่อมโยงไปยังถัดไป องค์ประกอบในถังที่เราต้องการ
โหนด struct * ต่อไป
ดังนั้นนั่นคือสิ่งที่โหนดดูเหมือนว่า
ตอนนี้ที่นี่คือการประกาศ ของตารางแฮชของเรา
มันจะมี 16,384 ถัง แต่ จำนวนที่ไม่ได้เรื่องจริงๆ
และในที่สุดเรากำลังจะมี hashtable_size ตัวแปรทั่วโลกซึ่ง
จะเริ่มออกเป็น 0 และก็ จะติดตามกี่คำ
อยู่ในพจนานุกรมของเรา
ขวาทั้งหมด
>> ดังนั้นลองมาดูที่โหลด
ดังนั้นสังเกตเห็นภาระที่ มันกลับบูล
คุณกลับจริงถ้ามันประสบความสำเร็จ โหลดและเท็จอย่างอื่น
และจะใช้เวลา const char * ดาว พจนานุกรมซึ่งเป็นพจนานุกรม
ที่เราต้องการที่จะเปิด
เพื่อให้เป็นสิ่งแรก เรากำลังจะทำ
เรากำลังจะไป fopen พจนานุกรมสำหรับ การอ่านและการที่เรากำลังจะมี
เพื่อให้แน่ใจว่ามันจะประสบความสำเร็จดังนั้นหาก มันกลับโมฆะแล้วเราไม่ได้
ประสบความสำเร็จในการเปิดพจนานุกรม และเราต้องกลับเท็จ
>> แต่สมมติว่ามันประสบความสำเร็จ เปิดแล้วเราต้องการที่จะอ่าน
พจนานุกรม
เพื่อให้การวนลูปจนกว่าเราจะพบบางส่วน เหตุผลที่จะแยกออกจากนี้
วงที่เราจะเห็น
เพื่อให้การวนลูปและตอนนี้เรากำลังจะ จะ malloc โหนดเดียว
และแน่นอนว่าเราจำเป็นต้องตรวจสอบข้อผิดพลาด อีกครั้งดังนั้นหาก mallocing ไม่ประสบความสำเร็จ
และเราต้องการที่จะยกเลิกการโหลดโหนดที่เรา ๆ ที่เกิดขึ้นกับ malloc ก่อนที่จะปิด
พจนานุกรมและกลับเท็จ
>> แต่ไม่สนใจว่าเราสมมติว่า ประสบความสำเร็จแล้วเราต้องการที่จะใช้ fscanf
การอ่านคำเดียวจากเรา พจนานุกรมเป็นโหนดของเรา
ดังนั้นอย่าลืมว่าคำว่ารายการ> เป็นถ่าน บัฟเฟอร์คำของความยาวขนาดบวก
หนึ่งที่เรากำลังจะ เก็บคำค่ะ
ดังนั้น fscanf จะกลับ 1 เป็นเวลานาน มันก็สามารถที่จะประสบความสำเร็จในการอ่าน
คำจากไฟล์
>> หากมีข้อผิดพลาดอย่างใดอย่างหนึ่งเกิดขึ้นหรือเราถึง ส่วนท้ายของแฟ้มจะไม่
1 คืนในกรณีที่ถ้ามันไม่ได้ 1 คืนเราก็จะไปทำลาย
ออกจากวงในขณะนี้
ดังนั้นเราจะเห็นว่าเมื่อเราประสบความสำเร็จ อ่านคำพูดเป็น
รายการ> คำแล้วเรากำลังจะสับ คำที่ใช้ฟังก์ชันแฮชของเราที่
ลองมาดูที่ ฟังก์ชันแฮช
>> เพื่อให้คุณไม่ได้จริงๆต้อง ที่จะเข้าใจในเรื่องนี้
และที่จริงเราก็ดึงนี้ สับฟังก์ชั่นจากอินเทอร์เน็ต
สิ่งเดียวที่คุณจำเป็นต้องรู้คือ ที่นี้จะใช้เวลา char * คำ const,
จึงสละสตริงเป็น input และ กลับ int ไม่ได้ลงนามเป็นผลผลิต
เพื่อให้ทุกฟังก์ชันแฮชจะเป็นมัน จะใช้เวลาในการป้อนข้อมูลจะช่วยให้คุณ
ดัชนีลงในตารางแฮช
ขอให้สังเกตว่าเรากำลัง modding โดย NUM_BUCKETS ดังนั้นค่าแฮชกลับ
จริงเป็นดัชนีในตารางแฮช และไม่เกินกว่าดัชนี
ขอบเขตของอาร์เรย์
>> ได้รับเพื่อให้การทำงานของกัญชาที่เรากำลังจะ ที่จะสับคำที่เราอ่าน
จากพจนานุกรมแล้วเรากำลังจะ การใช้งานที่มีการแทรก
เข้าสู่ตารางแฮช
ตอนนี้กัญชา hashtable ที่เป็นปัจจุบัน รายการที่เชื่อมโยงในตารางแฮชและ
มันเป็นไปได้มากที่เป็นโมฆะเพียง
เราต้องการที่จะแทรกรายการของเราได้ที่ จุดเริ่มต้นของรายการที่เชื่อมโยงนี้และอื่น ๆ
เรากำลังจะมีรายการของเราในปัจจุบัน ชี้ไปที่สิ่งที่ตารางแฮชในขณะนี้
จุดที่จะต้องแล้วเรากำลังจะเก็บ ในตารางแฮชที่กัญชา
รายการปัจจุบัน
>> ดังนั้นทั้งสองสายที่ประสบความสำเร็จแทรก รายการที่จุดเริ่มต้นของ
รายการที่เชื่อมโยงที่ดัชนีที่ ในตารางแฮช
เมื่อเรากำลังทำกับที่เรารู้ ที่เราพบในคำอื่น
พจนานุกรมและเราเพิ่มขึ้นอีกครั้ง
ดังนั้นเราจึงให้ทำจน fscanf ในที่สุดสิ่งที่ไม่ได้ผลตอบแทนที่ 1
จุดที่จำไว้ว่าเราจำเป็นที่จะต้อง รายการฟรีดังนั้นที่นี่เรา malloced
รายการและเราพยายามที่จะอ่านสิ่งที่ จากพจนานุกรม
และเราไม่ได้อ่านที่ประสบความสำเร็จ บางสิ่งบางอย่างจากพจนานุกรมที่
กรณีที่เราต้องการที่จะเป็นอิสระเข้ามาที่เรา ไม่เคยใส่จริงในตารางแฮช
และในที่สุดก็ทำลาย
>> เมื่อเราแบ่งออกเราจำเป็นต้องดูดี เราได้แบ่งออกเพราะมี
อ่านข้อผิดพลาดจากไฟล์หรือ เราได้แบ่งออกเพราะเรามาถึง
ในตอนท้ายของไฟล์หรือไม่
หากมีข้อผิดพลาดแล้วเราต้องการที่จะ กลับเท็จเพราะการโหลดไม่ได้
ประสบความสำเร็จและในกระบวนการที่เราต้องการ ขนคำทั้งหมดที่เราอ่าน
และปิดแฟ้มพจนานุกรม
สมมติว่าเราไม่ประสบความสำเร็จแล้วเราเพียงแค่ ยังคงต้องปิดพจนานุกรม
ไฟล์และในที่สุดก็กลับจริงตั้งแต่ เราได้ประสบความสำเร็จในการโหลด
พจนานุกรม
และที่มันสำหรับการโหลด
>> ดังนั้นตอนนี้ตรวจสอบให้ตารางแฮชโหลด จะมีลักษณะเช่นนี้
เพื่อตรวจสอบก็จะกลับบูลซึ่ง จะระบุว่า
ผ่านใน char * คำว่า สตริงผ่านไปในอยู่ในพจนานุกรมของเรา
ดังนั้นถ้ามันอยู่ในพจนานุกรมถ้าเป็น ในตารางแฮชของเราเราจะกลับมา
จริงและถ้ามันไม่ได้ เราจะกลับเท็จ
ให้นี้ผ่านคำในเรา จะสับคำ
>> ตอนนี้สิ่งที่สำคัญในการรับรู้เป็น ว่าในการโหลดเรารู้ว่าทุก
คำก็จะเป็นกรณีที่ต่ำกว่า แต่ที่นี่เราไม่แน่ใจว่าดังนั้น
ถ้าเราจะดูที่ฟังก์ชันแฮชของเรา ฟังก์ชันแฮชของเราจริง
เป็น lowercasing ตัวละครแต่ละตัว ของคำว่า
ดังนั้นโดยไม่คำนึงถึงมูลค่าของ คำฟังก์ชันแฮชของเราเป็นไป
กลับดัชนีเดียวกันสำหรับสิ่งที่ มูลค่าเป็นมันจะมี
กลับตัวพิมพ์เล็กอย่างสมบูรณ์ รุ่นของคำว่า
ขวาทั้งหมด
>> เพื่อให้เป็นดัชนีของเรา
มันเป็นตารางแฮชสำหรับคำนี้
ตอนนี้สำหรับวงที่เป็นไป ให้เกินรายการที่เชื่อมโยง
ที่อยู่ในดัชนีที่
ดังนั้นเราจะสังเกตเห็นการเริ่มต้นรายการ ให้ชี้ไปที่ดัชนี
เรากำลังจะดำเนินการต่อไปในขณะที่รายการไม่ ไม่เท่ากับโมฆะและจำไว้ว่า
การปรับปรุงตัวชี้ในรายการที่เชื่อมโยงของเรา รายการเท่ากับรายการ> ต่อไปเพื่อให้มี
จุดเริ่มต้นของเราในปัจจุบันที่ รายการถัดไปในรายการที่เชื่อมโยง
ขวาทั้งหมด
>> ดังนั้นสำหรับแต่ละรายการในรายการที่เชื่อมโยง เรากำลังจะใช้ strcasecmp
มันไม่ได้เป็นเพราะ strcmp อีกครั้งหนึ่งที่เรา ต้องการที่จะทำสิ่งที่ตัวดีกรณี
ดังนั้นเราจึงใช้ strcasecmp เพื่อเปรียบเทียบคำว่า ที่ได้รับการส่งผ่านไปยังฟังก์ชั่นนี้
กับคำว่า ที่อยู่ในรายการนี​​้
ถ้ามันกลับ 0, นั่นหมายความว่ามี การแข่งขันในกรณีที่เราต้องการที่จะ
กลับจริง
เราประสบความสำเร็จพบ คำในตารางแฮชของเรา
>> หากไม่มีการแข่งขันแล้วเรา จะห่วงอีกครั้งและมองไปที่
รายการถัดไป
และเราจะดำเนินการต่อไปในขณะที่มีการวนลูป เป็นรายการในรายการที่เชื่อมโยงนี้
จะเกิดอะไรขึ้นถ้าเราทำลาย จากนี้สำหรับวง?
นั่นหมายความว่าเราไม่พบรายการที่ จับคู่คำนี้ในกรณีที่
เรากลับเท็จเพื่อแสดงว่าเรา ตารางแฮชไม่ได้มีคำนี้
และที่มันสำหรับการตรวจสอบ
ขวาทั้งหมด
>> ดังนั้นลองมาดูที่ขนาด
ตอนนี้ขนาดเป็นไปได้ง่ายสวย ตั้งแต่จำในการโหลดสำหรับแต่ละคำ
เราพบว่าเราเพิ่มขึ้นทั่วโลก hashtable_size ตัวแปร
ดังนั้นฟังก์ชั่นขนาดเป็นเพียง กลับไปที่โลก
ตัวแปรและที่มัน
>> ตอนนี้ในที่สุดเราจำเป็นต้องยกเลิกการโหลด พจนานุกรมเมื่อทุกอย่างเสร็จแล้ว
ดังนั้นเราจึงมีวิธีการที่จะทำเช่นนั้นได้อย่างไร
ที่นี่เรากำลังวนลูปทั้งหมด ถังของตารางแฮชของเรา
จึงมีถัง NUM_BUCKETS เป็น
และสำหรับรายการที่เชื่อมโยงในแต่ละกัญชาของเรา ตารางที่เรากำลังจะไปห่วงกว่า
ความสมบูรณ์ของรายการที่เชื่อมโยง พ้นแต่ละองค์ประกอบ
ตอนนี้เราจะต้องระมัดระวังดังนั้นที่นี่เรา มีตัวแปรชั่วคราวที่
ตัวชี้การจัดเก็บต่อไป องค์ประกอบในรายการที่เชื่อมโยง
แล้วเรากำลังจะไปฟรี องค์ประกอบปัจจุบัน
>> เราต้องให้แน่ใจว่าเราทำเช่นนี้เพราะเรา ก็ไม่สามารถเป็นอิสระองค์ประกอบปัจจุบัน
แล้วพยายามที่จะเข้าถึงตัวชี้ต่อไป ตั้งแต่เมื่อเราปล่อยมัน
หน่วยความจำจะไม่ถูกต้อง
ดังนั้นเราจึงจำเป็นที่จะทำให้รอบตัวชี้ไปยัง องค์ประกอบถัดไปแล้วเราสามารถเป็นอิสระ
องค์ประกอบในปัจจุบันและจากนั้นเราสามารถปรับปรุง องค์ประกอบในปัจจุบันของเราให้ชี้ไปที่
องค์ประกอบถัดไป
>> เราจะห่วงในขณะที่มีองค์ประกอบ ในรายการที่เชื่อมโยงนี้
เราจะทำที่สำหรับรายการเชื่อมโยงทั้งหมดใน ตารางแฮชและเมื่อเราดำเนินการเสร็จแล้ว
กับที่เราได้ถอดสมบูรณ์ ตารางแฮชและเรากำลังทำ
ดังนั้นจึงเป็นไปไม่ได้สำหรับ unloads ที่เคย กลับเท็จและเมื่อเรากำลังทำเรา
เพียงแค่กลับจริง