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 ที่เคย กลับเท็จและเมื่อเรากำลังทำเรา เพียงแค่กลับจริง