[השמעת מוסיקה] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

בואו לתת פתרון זה לנסות. אז בואו נסתכל על מה ששלנו צומת struct תיראה. כאן אנו רואים שאנחנו הולכים יש לי bool מילה וצומת struct * ילדים א"ב סוגר. אז הדבר הראשון שאתה יכול להיות תוהה, מדוע הוא א"ב ed מוגדר כ27? ובכן, זוכר שאנחנו הולכים צריכים לטיפול בגרש. אז זה הולך להיות קצת מקרה מיוחד במהלך תכנית זו. 

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

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

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

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

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

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

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

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

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

אז, כמו שאמרתי קודם, שאנחנו צריכים מקרה מיוחד הגרש. שים לב שאתה משתמש משולש מפעיל כאן. אז אנחנו הולכים לקרוא את זה כמו, אם הדמות שאנו קוראים בהייתה גרש, אז אנחנו הולכים להקים מדד = "אלף" -1, אשר יהיה יהיה המדד 26. 

דבר אחר, אם זה לא היה גרש, יש אנחנו הולכים להגדיר את המדד שווה ג -. אז זוכר בחזרה מהעבר p-סטים, ג - הוא הולך לתת לנו עמדה אלפביתית של ג אז אם C היא האות, זה יהיה לתת לנו מדד אפס. לאות B, זה ייתן לי שלנו המדד 1, וכן הלאה. 

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

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

עכשיו, אם זה לא היה ריק מלכתחילה, לאחר מכן הסמן יכול רק לחזר עד שהילד מבלי יש להקצות כל דבר. זה המקרה שבו אנו קרו ראשון להקצות את המילה "חתול". ו - זה אומר שכאשר אנחנו הולכים להקצות "קטסטרופה", אנחנו לא צריכים ליצור בלוטות לC-A-T שוב. הם כבר קיימים. 

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

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

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

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

אנו רואים כאן, בדיוק כמו בעבר, אנחנו הולכים להשתמש בסמן ללחזר דרך הגיבורים שלנו. עכשיו הנה אנחנו הולכים לחזר על כל המילה שלנו. אז iterating מעל המילה אנחנו בעבר, אנחנו הולכים לקבוע את מדד לתוך מערך שהילדים מתאים לI. סוגריים מילה אז זה הוא הולך להיראות בדיוק כמו עומס, שבו אם מילה [i] הוא גרש, אז אנחנו רוצים להשתמש "אלף" אינדקס - 1. מכיוון שקבענו כי ש מקום שבו אנחנו הולכים לאחסון גרשיים. 

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

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

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

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

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

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

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

[השמעת מוסיקה]