ROB אודן: היי. אני רוב, והחשיש הבה פתרון את זה. אז הנה אנחנו הולכים ליישם שולחן חשיש כללי. אנו רואים כי צומת struct של החשיש השולחן הולך להיראות כך. אז זה הולך להיות מילת char מערך של אורך בתוספת גודל 1. אל תשכח 1 מאז מרבי מילה במילון היא 45 תווים, ולאחר מכן אנחנו הולכים צריך אופי אחד נוסף עבור קו נטוי הפוך 0. 

ולאחר מכן שולחן החשיש שלנו בכל אחד דלי הולך לאחסון רשימה מקושרת של צמתים. אנחנו לא עושים ליניארי חיטוט כאן. וזאת על מנת לקשר למשנהו אלמנט בדלי, שאנחנו צריכים צומת struct * הבא. אז זה מה שצומת נראית. עכשיו, הנה היא ההצהרה משולחן החשיש שלנו. זה הולך לי 16,384 דליים, אבל מספר זה לא ממש משנה. ולבסוף, אנחנו הולכים יש לי hashtable_size משתנה הגלובלי, אשר הוא הולך להתחיל כמו 0, וזה הולך לעקוב אחר כמה מילות היו במילון שלנו. בסדר. 

אז בואו נסתכל על עומס. אז שם לב שעומס, היא מחזירה bool. אתה חוזר נכון אם זה היה בהצלחה טעון ושקר אחר. וזה לוקח * כוכב char const מילון, שהוא המילון כי אנחנו רוצים לפתוח. אז זה הדבר הראשון אנחנו הולכים לעשות. אנחנו הולכים fopen המילון קריאה, ואנחנו הולכים לי כדי לוודא שזה הצליח כל כך אם זה חזר NULL, אז אנחנו לא בהצלחה לפתוח את המילון ואנחנו צריכים לחזור שווא. 

אבל בהנחה שזה עשה בהצלחה פתוח, אז אנחנו רוצים לקרוא במילון. אז לשמור על הלולאה עד שנמצא כמה סיבה לפרוץ את זה לולאה שבו אנו נראה. אז לשמור על לולאות, ועכשיו אנחנו הולכים לmalloc צומת אחת. וכמובן, אנחנו צריכים שגיאת בדיקה שוב כך שאם mallocing לא הצליח ואנחנו רוצים לפרוק את כל צומת שאנחנו קרה לי malloc לפני, סגור את מילון ותמורת שווא. 

אבל התעלמות שאנחנו בהנחה, הצלחנו, אז אנחנו רוצים להשתמש fscanf לקרוא לו מילה אחת משלנו מילון לצומת שלנו. אז לזכור שמילה כניסה-> הוא char מילת חיץ באורך בתוספת גודל אחד שאנחנו הולכים לאחסן את המילה פנימה אז fscanf הולך לחזור 1 עוד כפי שהוא היה מסוגל לקרוא בהצלחה מילה מהקובץ. 

אם אחד שגיאה קורה או שנגיע סוף הקובץ, זה לא יהיה בתמורה 1 ובמקרה זה אם זה לא בתמורה 1, אנחנו סוף סוף הולכים לשבור מתוך לולאה בזמן זה. כך אנו רואים כי ברגע שיש לנו בהצלחה קראת את מילה לתוך כניסה-> מילה, ואז אנחנו הולכים לחשיש מילה שמשתמשת בפונקצית hash שלנו. בואו נסתכל על פונקציית hash. 

אז אתה לא באמת צריך כדי להבין את זה. ובעצם, אנחנו פשוט משכתי את זה חשיש פונקציה מהאינטרנט. הדבר היחיד שאתה צריך להכיר הוא כי זה לוקח מילת char * const, כך שזה לוקח מחרוזת כקלט ו חוזר int חתום כפלט. אז זה כל פונקצית חשיש הוא, האם זה לוקח בקלט, זה נותן לך מדד לשולחן החשיש. שים לב שאנחנו modding ידי NUM_BUCKETS כך חזר את ערך Hash למעשה הוא מדד לשולחן החשיש ולא מעבר למדד גבולות של המערך. 

אז בהתחשב בכך שפונקצית חשיש, אנחנו הולכים חשיש המילה שאנו קוראים מהמילון ולאחר מכן אנחנו הולכים לשימוש, כי יש להכניס את כניסה לשולחן החשיש. עכשיו, חשיש hashtable הוא הנוכחי רשימה מקושרת בטבלת החשיש, ו זה אפשרי מאוד כי הוא פשוט NULL. אנחנו רוצים להכניס את הכניסה שלנו ב התחלה של רשימה מקושרת זה, וכך אנחנו הולכים יש לי הכניסה הנוכחית שלנו תצביע על מה ששולחן החשיש כיום נקודות ולאז אנחנו הולכים לחנות בשולחן החשיש בחשיש הכניסה הנוכחית. 

אז שתי שורות אלה להכניס בהצלחה הכניסה בתחילת רשימה מקושרת במדד בטבלת הגיבוב. ברגע שנסיים עם זה, אנחנו יודעים שמצאנו מילה אחרת ב מילון ולהגדיל שוב. אז אנחנו ממשיכים לעשות את זה עד fscanf לבסוף חוזר משהו שאינו 1 ב שנקודה לזכור שאנחנו צריכים כניסה חופשית, ולכן עד כאן, אנחנו malloced כניסה וניסינו לקרוא משהו מהמילון. ואנחנו לא קראנו בהצלחה משהו מהמילון שבי מקרה אנחנו צריכים לשחרר את הערך שאנו אף פעם לא ממש לשים לשולחן החשיש ולבסוף לשבור. 

ברגע שאנו לפרוץ החוצה, אנחנו צריכים לראות, טובים, היה לנו לפרוץ החוצה, כי יש הייתה שגיאה בקריאה מהקובץ, או היה לנו לפרוץ החוצה בגלל שאנחנו הגענו סוף הקובץ? אם הייתה טעות, אז אנחנו רוצים בתמורת שווא בגלל עומס לא להצליח, ותוך כדי התהליך, אנחנו רוצים לפרוק את כל הדברים אשר אנו קוראים ובסגור את קובץ המילון. בהנחה שאנחנו לא מצליחים, אז אנחנו פשוט עדיין צריכה לסגור את המילון להגיש, ולבסוף לחזור נכון מאז אנחנו כבר נטענו בהצלחה מילון. וזהו זה לעומס. 

אז עכשיו לבדוק, בהתחשב שולחן חשיש טעון, הוא הולך להיראות כך. אז לבדוק, היא מחזירה bool, אשר הוא הולך לציין אם עבר ב- char מילה *, בין אם מחרוזת חלף-בהיא במילון שלנו. אז אם זה במילון, אם הוא בטבלת הגיבוב שלנו, נחזור נכון, ואם זה לא, אנו בתמורת שווא. בהינתן מילה חלפה-בזה, אנחנו הולך חשיש המילה. 

עכשיו, דבר חשוב להכיר הוא כי בעומס, ידעו שכל המילים הולכות להיות באותיות קטנות, אבל כאן, אנחנו לא כל כך בטוחים. אם נסתכל על פונקציית hash שלנו, פונקציית hash שלנו בעצם הוא lowercasing כל תו של המילה. אז ללא קשר לשווי של מילה, פונקציית hash שלנו הולכת להחזיר את אותו מדד לכל היוון הוא כפי שהוא היה צריך חזרתי לאותיות קטנות לחלוטין גרסה של המילה. בסדר. 

אז זה המדד שלנו. זה שולחן החשיש למילה זו. עכשיו, זה ללולאה הולך לכל רחבי הרשימה המקושרת שהיה במדד זה. אז שמתי לב שאנו מאתחלים כניסה כדי להצביע על מדד זה. אנחנו הולכים להמשיך בזמן שהכניסה עושה לא NULL שווה, ולזכור כי מעדכן את המצביע ברשימה המקושרת שלנו כניסה שווה כניסה-> הבאה, ולכן יש לי נקודת הכניסה הנוכחית שלנו הפריט הבא ברשימה מקושרת. בסדר. 

אז לכל ערך ברשימה המקושרת, אנחנו הולכים להשתמש strcasecmp. זה לא strcmp כי שוב, אנחנו רוצה לעשות דברים בחוסר רגיש מקרה. כך אנו משתמשים strcasecmp להשוות את המילה שהועבר לפונקציה זו נגד המילה ש ברשומה זו. אם היא מחזירה 0, זה אומר שלא היה משחק, ובמקרה כזה אנחנו רוצים החזר אמיתי. מצאנו בהצלחה מילה בטבלת הגיבוב שלנו. 

אם לא היה במשחק, אז אנחנו הולך ללולאה שוב ומסתכלים על הכניסה הבאה. ואנחנו נמשיך לולאות בעוד יש הם ערכים ברשימה מקושר זה. מה קורה אם אנחנו שוברים מתוך זה ללולאה? זה אומר שאנחנו לא מצאנו שכניסה תאם את המילה הזאת, ובמקרה זה אנחנו חוזרים שווא כדי לציין ש שולחן חשיש לא הכיל את המילה הזאת. וזה אותו לבדיקה. בסדר. 

אז בואו נסתכל על גודל. עכשיו, גודל הולך להיות די פשוט מאז לזכור בעומס, לכל מילה גילינו שאנחנו מוגדלים גלובליים hashtable_size משתנה. אז פונקצית הגודל היא רק הולך לחזור כי גלובלי משתנה, וזהו זה. 

עכשיו סוף סוף, אנחנו צריכים לפרוק את מילון פעם אחת את כל מה שעשה. אז איך אנחנו הולכים לעשות את זה? ממש כאן, אנחנו לולאה על כל דליים של טבלת הגיבוב שלנו. אז יש דליי NUM_BUCKETS. ועבור כל רשימה מקושרת בהחשיש שולחן, אנחנו הולכים ללולאה מעל שלמות של הרשימה המקושרת לשחרר את כל רכיב. עכשיו, אנחנו צריכים להיות זהירים, אז הנה לנו יש לי משתנה זמני זה אחסון המצביע למשנהו אלמנט ברשימה המקושרת. ואז אנחנו הולכים לחופשיים האלמנט הנוכחי. 

אנחנו צריכים להיות בטוחים שאנחנו עושים את זה מאז ש לא יכול פשוט לשחרר את האלמנט הנוכחי ולאחר מכן נסה לגשת למצביע הבא מאז רגע ששחררנו אותו זיכרון הופך להיות לא חוקי. אז אנחנו צריכים לשמור על סביב מצביע האלמנט הבא, אז אנחנו יכולים לשחרר את אלמנט הנוכחי, ולאחר מכן אנו יכולים לעדכן האלמנט הנוכחי שלנו כדי להצביע על האלמנט הבא. 

אנחנו לולאה בזמן שיש אלמנטים ברשימה מקושרת זה. אנחנו נעשה את זה בשביל כל הרשימות המקושרות ב שולחן החשיש, וברגע שנסיים עם זה, אנחנו כבר נפרקו לחלוטין שולחן החשיש, ואנחנו נעשו. כך שזה בלתי אפשרי עבור לפרוק אי פעם בתמורת שווא, וכשנסיים, אנחנו רק החזר אמיתי.