[Powered by Google Translate] [Walkthrough - סט בעיה 5] [Zamyla צ'אן - אוניברסיטת הרווארד] [זה CS50. - CS50.TV] 

בסדר. שלום לכולם, וברוך הבאים לWalkthrough 5. 

Pset5 הוא שגיאות כתיב, שבו אנחנו יהיו ביצוע של בדק איות. בודקי איות הם מאוד חשובים. האם זה אי פעם קרה לך? אתה עובד מאוד מאוד אוגר על נייר להתנגשות ואז עדיין בסופו של דבר מקבל rade זוהר מאוד כמו D או D = והכול מפני שאתה ספוילר הנקניק הכבד במילה הרחבה הלווייתן. כן, גהת הפלפלים שלך היא עניין של, אימפוטנציה העליונה. זו בעיה שמשפיעה על תלמידים גבריים, גבריים. נאמרתי לי פעם על ידי מענה הכיתה הסית שלעולם לא יצליח להגיע לקולגה טוב. וזה כל מה שאי פעם רציתי, זה כל מה שכל ילד רוצה בגיל שלי, רק כדי להיכנס לעמית טוב. ולא סתם עמית לעבודה. לא, אני רוצה ללכת לקולגה משפטי שנהב. אז אם אני לא עשיתי שיפור, הלך יהיו החלומות שלי ילך לרווארד, Jale, או כלא - אתה יודע, בכלא, ניו ג'רזי. אז יש לי את עצמי בודק איות. זה קטע קטן מאחד האמנים האהובים עליי מילה המדוברים, טיילור Mali. בכל מקרה, כמו שהוא אומר, את החשיבות של בעל בודק איות היא חשובה מאוד. 

אז מוזמן Walkthrough 5, שבו אנו יהיו לדבר על pset5: שגיאות כתיב, שבו אנחנו יהיו ביצוע של בדק האיות שלנו מאוד משלו. ארגז הכלים לשבוע הזה, קוד ההפצה, הוא הולך להיות חשוב להסתכל על רק כדי להבין את הפונקציות השונות שהמילון שלך הולך להיות. אנחנו בעצם הולכים להיות שקבצי c מרובים. שביחד הופכים pset. וכך לעבור על היבטים השונים, למרות שאנחנו ממש לא עריכה אחד מהקבצים, speller.c, לדעת איך זה עובד ביחס לdictionary.c, שיהיה לנו לכתוב, הוא הולך להיות חשוב מאוד. מפרט pset גם מכיל הרבה מידע שימושי במונחים של דברים שאתה יכול להניח, חוקים ודברים כאלה, כדי להיות בטוח כדי לקרוא בעיון את מפרט pset לטיפים. וכאשר יש ספק של כלל או משהו כזה, אז תמיד מתייחס למפרט pset או דיון. pset זה הולך להסתמך בכבדות על מצביעים, לכן אנחנו רוצים לוודא שאנחנו מבינים את ההבדל בין כוכבי הוספה לפני שמו של המצביע והאמפרסנד, איך לשחרר אותם, וכו ' אז להיות אדון של מצביעים הולך להיות מאוד מועיל בסט בעיה זו. אנחנו הולכים לבדוק את הרשימות מקושרות קצת יותר, שם יש לנו אלמנטים שאנו מכנים צומת שיש להם גם ערך וגם כמצביע לצומת הבאה, וכך למעשה מקשר אלמנטים שונים בזה אחר זה. יש כמה אפשרויות שונות של יישום המילון שלך בפועל. אנחנו הולכים לבדוק את שתי שיטות עיקריות, שהיא שולחנות חשיש, ואז מנסה. בשני אלה, הם כרוכים באיזשהו רעיון של רשימה מקושרת שם יש לך אלמנטים קשורים אחד לשנייה. וכך אנחנו הולכים להסתכל על איך אתה יכול להיות מסוגל לפעול בסביבת רשימות מקושרות, ליצור אותם, לנווט במונחים של איך, למשל, להכניס לתוכו צומת או בחינם כל כמו גם את צומת. במונחים של בלוטות לשחרר, זה באמת חשוב כי בכל פעם שאנו זכרון malloc, אחר כך אנו משחררים אותו. אז אנחנו רוצים לוודא שאין מצביע הולך unfreed, שאין לנו כל דליפות זיכרון. אנחנו הולכים להציג את כלי שנקרא Valgrind שמפעיל את התכנית שלך ובודק אם כל הזיכרון שהוקצה אז הוא שוחרר. pset להשלים רק כשזה עובד ויש לו פונקציונליות מלאה, אלא גם, Valgrind אומר לך שלא מצא דליפות זיכרון. לבסוף, לpset זה, אני באמת רוצה להדגיש - אני מתכוון, כרגיל, אני בהחלט תומך בשימוש בעט ונייר לסטי הבעיה שלך, אבל בשביל זה, אני חושב שעט ונייר הולך להיות חשוב במיוחד כשאתה רוצה להיות ציור חצים לדברים ולהבין כיצד דברים עובדים. אז בהחלט תנסה להשתמש בעט ונייר כדי להוציא דברים לפני שאתה מקבל הקידוד בגלל שהוא יכול לקבל קצת מבולגן. 

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

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

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

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

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

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

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

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

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

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

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

שגיאות כתיב יש בקוד ההפצה כמה קבצים בעלי חשיבות. ראשית עלינו להבחין כי יש לנו Makefile זה כאן, שאנחנו לא באמת נתקלנו בעבר. אם נבחן היטב את pset5 התיקייה, היית מבחין שיש לך. קובץ h, אז יש לך שני קבצים. ג. מה המשמעות של זה הוא Makefile לפני, הייתי פשוט הקלד ולאחר מכן להפוך את שם התכנית ואז הייתי רואה את כל הטיעונים והדגלים האלה עברו במהדר. מה Makefile עושה הוא מאפשר לנו לאסוף כמה קבצים בבת אחת ותעבור בדגלים שאנחנו רוצים. כאן אנחנו רואים שיש קובץ כותרת כאן. אז אנחנו ממש יש שני קבצי מקור. יש לנו speller.c וdictionary.c. אתם מוזמנים לערוך את Makefile אם תרצה. שים לב שאם תקליד כאן נקי, אז מה שהוא עושה הוא בעצם מסיר כל דבר שהוא הליבה. אם יש לך תקלת פילוח, בעצם אתה מקבל מזבלת ליבה. אז הקובץ הקטן והמכוער הזה יופיע בספרייה שלך שנקראת ליבה. אתה רוצה להסיר שכדי לעשות את זה נקי. היא מסירה את כל קבצי exe ו. קבצי o. 

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

בואו נסתכל dictionary.c. אנו רואים שזה נראה דומה מאוד לdictionary.h, אלא שעכשיו זה בדיוק יש את כל אלה בטודוס. וכדי שזה התפקיד שלך. סופו של דבר, אתה תהיה מילוי speller.c עם כל הקוד הזה. Dictionary.c, כאשר לרוץ, הוא לא באמת הולך לעשות שום דבר, אז אנחנו מסתכלים לכיוון speller.c לראות ביצוע בפועל של בודק האיות. למרות שאתה לא הולך להיות עורך של כל הקוד הזה, זה חשוב לקרוא, להבין מתי נקרא עומס, כאשר אני קורא סימון, רק כדי להבין, למפות אותו, לראות איך הפונקציה עובדת. אנחנו רואים שזה בדיקה לשימוש הנכון. בעיקרון, כאשר מישהו רץ איות, זה מצביע על כך שזה לא חובה שאעבור בקובץ מילון, כי עומד להיות קובץ מילון ברירת מחדל. ואז הם צריכים לעבור בטקסט להיות איות מסומנת. עסקות rusage עם זמן, כי חלק מpset זה שיתמודדו עם המשך הוא לא רק מקבל תפקוד של בדק איות של עובד אבל בעצם מקבל את זה כדי להיות מהיר. ואם כך זה המקום שבי rusage הולך להיכנס כאן, אנו רואים את השיחה הראשונה לאחד מקבצי dictionary.c, אשר הוא עומס. עומס מחזיר אמת או שקר - אמיתי על הצלחה, שווא בעת התקלה. אז אם המילון לא נטען כראוי, אז speller.c יחזיר 1 ולהתפטר. אבל אם זה עושה עומס כמו שצריך, אז זה הולך להמשיך. אנחנו ממשיכים, ואנו רואים כמה קבצי הקלט / פלט לכאן, איפה זה הולך להיות התמודדות עם פתיחת קובץ הטקסט. הנה, מה המשמעות של זה הוא בודקת איות כל מילה ומילה בטקסט. אז מה עושה ברגע speller.c כאן iterating מעל כל אחת מהמילים בקובץ הטקסט ובדיקתן במילון. הנה, יש לנו בוליאני השגוי שיראו אם השק חוזר נכון או לא. אם המילה היא למעשה במילון, אז הסימון יהיה החזר אמיתי. זה אומר שהמילה אינה שגויה. אז שגוי יהיה שקר, ובגלל זה יש לנו את המפץ שם, האינדיקציה. אנחנו ממשיכים, ואז זה עוקב אחר כמה מילים באיות שגויה יש בקובץ. זה ממשיך ובסוגר את הקובץ. אז הנה, הוא מדווח כמה מילים באיות שגויה שהיה לך. היא מחשבת כמה זמן לקח כדי לטעון מילון, כמה זמן זה לקח כדי לבדוק אותו, כמה זמן זה לקח כדי לחשב את הגודל, אשר, כפי שנמשיך, צריך להיות קטן מאוד, ואז כמה זמן זה לקח לפרוק את המילון. כאן למעלה אנו רואים את השיחה כדי לפרוק כאן. אם תבדקו לגודל כאן, אז אנו רואים שכאן הוא הקריאה לגודל שבו היא קובעת את הגודל של המילון. מדהים. 

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

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

בואו ניכנס לשיטת שולחן החשיש. שולחן חשיש מורכב מרשימה של דליים. כל ערך, כל מילה, הוא הולך להיכנס לאחד דליים אלה. שולחן חשיש באופן אידיאלי באופן שווה מפיץ את כל הערכים האלה שאתה עובר ב ולאחר מכן מאכלס אותם בדלי כזה שכל דלי יש על מספר שווה של ערכים בזה. המבנה לשולחן חשיש, יש לנו מערך של רשימות מקושרות. מה שאנחנו עושים הוא שאנחנו נפגשים בערך, אנחנו בודקים איפה ערך שצריך להיות שייך, הדלי שהוא שייך אליו, ואז למקם אותו לרשימה המקושרת המשויכת לדלי. הנה, מה שיש לי הוא פונקציית hash. זה שולחן חשיש int. אז לדלי הראשון, מספרים שלמים כלשהם מתחת 10 להיכנס לסל הראשון. כל מספרים שלמים מעל 10 אך מתחת 20 להיכנס לשנייה, ואז כן הלאה וכן הלאה. מבחינתי, כל אחד מסלים מייצגים את המספרים האלה. עם זאת, אומר שהיית אמור להעביר ב50, למשל. נראה כאילו שלושה הראשונים מכילים מגוון של 10 מספרים. אבל אני רוצה לאפשר לשולחן החשיש שלי לקחת בכל סוג של מספרים שלמים, כל כך אז הייתי צריך לסנן את כל המספרים מעל 30 לתוך הדלי שעבר. וכך אז שיביא בסוג של שולחן חשיש לא מאוזן. כדי לחזור ולהדגיש, שולחן חשיש הוא רק מערך של דליים איפה כל דלי הוא רשימה מקושרת. וכן לקבוע בו כל ערך עובר, שזה הולך לתוך הדלי, אתה הולך רוצה מה שנקרא פונקציית hash שלוקח את ערך ולאחר מכן אומר שערך זה מתאים לדלי מסוים. למעלה, כך בדוגמה זו, פונקציית hash שלי לקחה את כל ערך. זה בדק אם זה היה פחות מ 10. אם זה היה, זה היה לשים אותו לתוך הדלי הראשון. זה בודק אם זה פחות מ 20, מכניס אותו לתוך 2 אם זה נכון, בודק אם זה פחות מ 30, ואז מכניס אותו לתוך הדלי השלישי, ואז כל שאר פשוט נופל לדלי הרביעי. אז בכל פעם שיש לך ערך, פונקציית hash יציב את הערך שלתוך הדלי המתאים. פונקציית hash בעצם צריכה לדעת כמה דליים יש לך. גודל שולחן החשיש שלך, את מספר הסלים שיש לך, שהולך להיות מספר קבוע שתלוי בך, אתה צריך להחליט, אבל זה הולך להיות מספר קבוע. אז פונקציית hash שלך יהיה להסתמך על זה כדי לקבוע אילו דלי כל מקש נכנס כזה שהוא מופץ באופן שווה. בדומה ליישום שלנו של רשימות מקושרות, עכשיו כל צומת בטבלת החשיש למעשה הוא הולך להיות סוג char. אז יש לנו מערך char בשם מילה ולאחר מכן עוד מצביע לצומת הבאה, וזה הגיוני כי זה הולך להיות רשימה מקושרת. זכור שכאשר אנו מקושרים רשימות, עשיתי * צומת נקראת הראש שהצביע על הצומת הראשונה ברשימה המקושרת. אבל לשולחן החשיש שלנו, כי יש לנו רשימות מקושרות מרובות, מה שאנחנו רוצים הוא שאנחנו רוצים שולחן החשיש להיות כמו, "מה הוא דלי?" דלי הוא רק רשימה של מצביעי צומת, וכן כל אלמנט בדלי הוא למעשה מצביע לרשימה המקושרת המתאימה לו. כדי לחזור לשרטוט זה, אתה רואה שאת הדליים עצמם בחיצים, לא בלוטות בפועל. אחד נכס מהותי של פונקציות hash הוא שהם דטרמיניסטיים. זה אומר שכל פעם שאתה חשיש המספר 2, זה תמיד צריך לחזור באותו הדלי. כל ערך יחיד שנכנס לפונקציית hash, אם חזר, צריך לקבל את אותו המדד. אז פונקציית hash שלך מחזירה את האינדקס של המערך שם ערך ששייך. כפי שציינתי קודם, מספר הסלים קבוע, וכך המדד שלך שאתה חוזר צריך להיות פחות ממספר הסלים אך גדול מ 0. הסיבה שיש לנו פונקציות hash רק במקום אחד רשימה מקושרת אחת או מערך אחד הוא שאנחנו רוצים להיות מסוגלים לקפוץ לקטע מסוים בקלות אם אנחנו יודעים את המאפיין של ערך - במקום שיצטרך לחפש בכל המילון השלם, להיות מסוגל לקפוץ לקטע מסוים שלו. פונקציית hash שלך צריכה לקחת בחשבון שאופן אידיאלי, כל אחד מסלים יש בערך אותו מספר המפתחות. מאז שולחן החשיש הוא סדרה של רשימות מקושרות, אז את הרשימות המקושרים עצמם הולכות להיות צומת אחד או יותר. בדוגמא הקודמת, שני מספרים שונים, למרות שהם לא היו שווים, כשמרוסק, היה חוזר אותו המדד. לכן, כאשר אתם עוסקים במילים, מילה אחת כשמרוסק יהיה אותו ערך Hash כמילה אחרת. זה מה שאנו מכנים התנגשות, כאשר יש לנו צומת, שכאשר מרוסקות, הרשימה המקושרת שבדלי אינה ריקה. הטכניקה שאנו מכנים יש יניארי חיטוט, לאן אתה הולך לרשימה המקושרת ולאחר מכן למצוא בו ברצונך להוסיף צומת כי כי יש לך התנגשות. אתה יכול לראות שאולי יש תחלופה כאן, נכון? אם יש לך שולחן קטן מאוד חשיש, מספר קטן מאוד של דליים, ואז אתה הולך להיות הרבה התנגשויות. אבל אז אם אתה עושה טבלת חשיש גדולה מאוד, אתה כנראה הולך ללמזער התנגשויות, אבל זה הולך להיות מבנה נתונים גדול מאוד. יש הולך להיות פשרות עם זה. אז כשאתה עושה pset, נסה לשחק בין מה שהופך שולחן חשיש קטן אולי אבל אז ידע שזה הולך לקחת קצת יותר זמן לעבור את האלמנטים השונים רשימות המקושרות אלה. 

מה עומס הולך לעשות הוא לחזר על כל מלה במילון. זה עובר במצביע לקובץ המילון. אז אתה הולך לנצל את קובץ I / O פונקציות שאתה שולט בpset4 ולחזר על כל מלה במילון. אתה רוצה שכל מילה במילון כדי להיות צומת חדש, ואתה הולך למקום בכל אחד מצומת פנימיים של מבנה נתוני המילון שלך. בכל פעם שאתה מקבל מילה חדשה, אתה יודע שזה הולך להיות צומת. אז אתה יכול ללכת ישר וmalloc מצביע צומת עבור כל מילה חדשה שיש לך. הנה אני מתקשר new_node מצביע צומתי ואני mallocing מה? גודלו של צומת. ואז לקרוא את המחרוזת בפועל מקובץ, משום שהמילון מאוחסן בפועל על ידי מילה ולאחר מכן קו חדש, מה שאנחנו יכולים לנצל את היתרון של הוא fscanf הפונקציה, לפי קובץ הוא קובץ המילון שאנחנו עוברים ב, אז זה סורק את הקובץ למחרוזת ומקומות שמחרוזת לטענה האחרונה. אם אתה זוכר בחזרה לאחת מההרצאות, כשעלינו על וסוג של קלף את השכבות בחזרה על ספריית CS50, ראינו יישום fscanf שם. כדי לחזור לfscanf, יש לנו את הקובץ שאנחנו קוראים מ, אנחנו מחפשים מחרוזת שבקובץ, ולאחר מכן אנחנו מניחים אותו לתוך כאן יש לי new_node> מילה משום new_node הוא מצביע צומת, לא צומת עצמו. אז אני אומר new_node, אני רוצה ללכת לצומת שזה מצביע על ולאחר מכן להקצות את ערך שלמילה. אנחנו רוצים ואז לקחת את המילה ושלהכניס אותו לתוך שולחן החשיש. להבין שאנחנו עשינו new_node מצביע צומת בגלל שאנחנו הולכים רוצים לדעת מה הכתובת של צומת היא כאשר אנו מכניסים אותה בגלל המבנה של הבלוטות עצמן, של struct, הוא שיש להם מצביעים לצומת חדשה. אז מה הכתובת של צומת שהולכת להצביע ל? כתובת זו הולכת להיות new_node. האם זה הגיוני, למה אנחנו עושים את new_node * צומת בניגוד לצומת? אוקיי. יש לנו מילה. שהערך הוא new_node-> מילה. המכיל את המילה מהמילון שאנחנו רוצים קלט. אז מה שאנחנו רוצים לעשות הוא שאנחנו רוצים לקרוא לפונקציית hash על מייתר כי פונקציית hash שלנו לוקחת במחרוזת ולאחר מכן מחזירה אותנו מספר שלם, שם שלם שהוא המדד בי hashtable שבמדד מייצג דלי ש. אנחנו רוצים לקחת את האינדקס ולאחר מכן ללכת לאותו מדד של שולחן החשיש ולאחר מכן להשתמש ברשימה מקושרת כדי להוסיף את הצומת בnew_node. זכור כי זאת אתם מחליטים להכניס הצומת שלך, בין אם זה באמצע, אם ברצונך למיין אותו או בתחילתו או בסופו של דבר, רק לוודא שהצומת האחרונה שלך תמיד מצביעה על NULL משום שזו הדרך היחידה שאנחנו יודעים איפה את הרכיב האחרון של הרשימה המקושרת שלנו הוא. 

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

אז עכשיו אנחנו מקבלים כדי לבדוק. עכשיו אנחנו עוסקים במילים מקובץ טקסט הקלט, וכך אנחנו הולכים לבדיקה כל אם של המילים האלה הקלט הם למעשה במילון או לא. בדומה למירוץ, אנחנו רוצים לאפשר למקרה חוסר רגישות. אתה רוצה לוודא שכל המילים בעברו, למרות שהם במקרה מעורב, כשהתקשרתי עם compare מחרוזת, הם שווים ערך. את המילים במילון קבצי הטקסט הן למעשה כל האותיות קטנות. דבר נוסף הוא שאתה יכול להניח שכל מילה שעברה בכל מחרוזת, הולך להיות אלפביתי או מכילים גרשיים. גרשיים הולכים להיות תקפות מילים במילון שלנו. אז אם יש לך מילה עם הגרש S, זה מילה לגיטימית בפועל במילון שלך זה הולך להיות אחד מצומת בטבלת החשיש שלך. בדקו אם פועל עם המילה קיימת, אז זה חייב להיות בטבלת החשיש שלנו. אם המילה נמצאת במילון, אז כל מילים שבמילון הוא בשולחן החשיש, אז בואו נחפש את המילה הזאת בטבלת החשיש. אנחנו יודעים שמאז שיישמנו פונקציית hash כך שכל מילה ייחודית תמיד מופיעה באופן חלקי לאותו הערך, אז אנחנו יודעים שבמקום לחפש דרך שולחן החשיש כל כולו שלנו, אנחנו באמת יכולים למצוא את הרשימה המקושרת שהמילה שצריכה להשתייך אליו. אם זה היה במילון, אז זה יהיה בדלי. מה אנחנו יכולים לעשות, אם מילה היא השם של המחרוזת שלנו עברה ב, אנחנו יכולים רק חשיש שמילה ומבט ברשימה המקושרת בשווי של hashtable [החשיש (מילה)]. משם, מה שאנו יכולים לעשות הוא שיש לנו קבוצת משנה קטנה יותר של צמתים כדי לחפש את המילה הזאת, וכדי שנוכל לעבור את הרשימה המקושרת, באמצעות דוגמה מקודם בהדרכה, ואז להתקשר מחרוזת להשוות על המילה בכל מקום שהסמן מצביע על, שמילה, ולראות אם אלה להשוות. בהתאם לאופן שבו לך לארגן את פונקציית hash שלך, אם זה מיון, ייתכן שתוכל לחזור כוזב קצת קודם לכן, אבל אם זה לא ממוין, אז אתה רוצה להמשיך חוצה דרך הרשימה המקושרת שלך עד שתמצא את הרכיב האחרון של הרשימה. ואם אתה עדיין לא מצאת את המילה בזמן שכבר הגיע לסוף הרשימה המקושרת, זה אומר שהמילה שלך לא קיימת במילון, וכן המילה שאינה חוקית, וסימון צריך לחזור שווא. 

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

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

בואו נלך לדוגמה של איירי. ראשית יש לי חדר במשך 27 צומת במערך הזה. אם יש לי מילה ברת - אם יש לי את המילה ברה ואני רוצה להוסיף כי ב, האות הראשונה היא ב ', כך שאם איירי שלי ריק, ב 'הוא האות השנייה של האלפבית, אז אני הולך לבחור לשים את זה כאן במדד זה. אני הולך להיות כאן ב '. B הולך להיות צומת שמצביע למערך נוסף של כל הדמויות האפשריות שיכול לעקוב אחרי המכתב ב ' במקרה זה, אני מתמודד עם המילה הברה, כך ילך כאן. אחרי, יש לי את אות R, אז A נקודות עכשיו כדי השילוב שלה, ואז R יהיה כאן. בר הוא מילה שלמה, אז אני הולך יש נקודת R לצומת אחרת שאומר שמילה שהיא בתוקף. כי צומת היא גם הולך להיות מערך של צמתים, אבל אלה עשויים להיות NULL. אבל בעצם, זה יכול להמשיך ככה. שיהפוך לקצת יותר ברור כאשר אנו הולכים לדוגמה אחרת, אז פשוט תהיה סבלני איתי שם. עכשיו יש לנו בר הפנימי של המילון שלנו. עכשיו אומרים שיש לנו מילה באז. אנחנו מתחילים עם ב ', וכבר יש לנו ב' כאחד מהמכתבים שנמצאו במילון שלנו. אחרי זה עם א 'יש לנו כבר. אבל אז במקום זה, יש לנו בא Z. אז אלמנט במערך שלנו הולך להיות Z, וכך אז שאחד לא הולך להצביע לסיום חוקי אחר של המילה. כך אנו רואים שכאשר אנו ממשיכים דרך B ולאחר מכן, יש שתי אפשרויות שונות כרגע במילון שלנו למילים שמתחילות ב-B וא אומר שאנחנו רוצים להוסיף את המילה foobar. אז אנחנו נעשה את כניסה בפ F הוא צומת שמצביעה על כל מערך. היינו מוצא O, ללכת להו, הו, אז קישורים לכל רשימה. שנהיה לנו ב 'ולאחר מכן נמשיך, נהיה לנו, ואז ר' אז חוצה foobar כל הדרך למטה עד foobar היא מילה נכונה. וכך אז זה יהיה מילה תקפה. עכשיו תגיד את המילה הבאה שלנו במילון היא למעשה המילה FOO. היינו אומר פ 'מה להלן F? אני בעצם כבר יש לך מקום לO, אז אני הולך להמשיך. אני לא צריך לעשות אחת חדשה. המשך. FOO הוא מילה חוקית במילון זה, אז אני הולך להצביע שזה חוקי. אם אני אעצור את הרצף שלי שם, זה יהיה נכון. אבל אם המשכנו הרצף שלנו מFOO למטה ל-B ופשוט הייתה לי FOOB, FOOB היא לא מילה, וזה לא צוין כתקין. באיירי, שכל צומת שמציינת אם זה חוקי או לא מילה, ולאחר מכן בכל צומת יש גם מערך של 27 מצביעי צומת שלאחר מכן צבע על צומת עצמם. 

הנה דרך של איך ייתכן שתרצה להגדיר את זה. עם זאת, בדיוק כמו בדוגמא שולחן החשיש, שבו היה לנו ראש * צומת כדי לציין את תחילתה של הרשימה המקושרת שלנו, אנחנו גם נרצה איזו דרך לדעת לאן תחילת איירי היא. כמה אנשים קוראים מנסה עצים, ושם שורש מגיע מ. אז אנחנו רוצים השורש של העץ שלנו כדי לוודא שאנחנו נישאר מקורקעים לכל המקום שאיירי היא. כבר אנחנו סוג של ניגשנו כפי שאתה יכול לחשוב על כל מילת טעינה למילון. בעיקרו של דבר, לכל מילה שאתה הולך רוצה לחזר דרך איירי וידיעה שכל אלמנט בילדים - שקראנו לו ילדים במקרה זה - מתאים לאות אחרת, אתה הולך רוצה לבדוק ערכים אלה באותו מדד מסוים שמתאים למכתב. אז חשבתי כל הדרך חזרה לקיסר וVigenere, ידיעה שכל אות שאתה יכול מעין המפה חזרה לאינדקס אלפביתי, בהחלט עד Z הולך להיות די קלה למיפוי למכתב אלפביתי, אך למרבה הצער, גרשיים הם גם דמות מקובלת במילים. אני אפילו לא בטוח מה ערך ASCII הוא, כך שלאם אתה רוצה למצוא את אינדקס כדי להחליט אם אתה רוצה את זה כדי להיות ראשון או האחרון, תצטרך לבצע בדיקה מקודדת קשה בשביל זה ואז לשים את זה בעמוד 26, למשל. אז אתה בודק את הערך בילדים [i] שם [i] מקבילה לכל מכתב שאתה. אם זה NULL, זה אומר שאין כרגע כל מכתבים אפשריים נובע מהרצף הקודם, אז אתה הולך רוצה malloc ולהפוך את צומת חדשה ויש לי שילדים [i] צבע עליו כך שאתה יוצר - כאשר הכנסנו מכתב למלבן - קבלת ילדים שאינם ריקה ונקודה שלצומת החדשה. אבל אם זה לא ריק, כמו בדוגמא שלנו FOO כאשר כבר היו לנו foobar, אנחנו ממשיכים, ואנחנו לא תמיד עושים צומת חדש אלא רק הגדרת is_word לאמיתי בסוף של מילה. 

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

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

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

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

חלק מpset זה, זה לא חובה לאתגר את הלוח הגדול. אבל כאשר יש לנו עסק עם מבני נתונים אלה זה סוג של כיף לראות כמה מהר וכמה יעילים מבני הנתונים שלך יכולים להיות. האם תוצאת פונקציית hash בהרבה התנגשויות? או שגודל הנתונים שלך ממש גדול? זה לוקח הרבה זמן לעבור? ביומן של איות, זה פלטים כמה זמן אתה משתמש לטעינה, כדי לבדוק, לנהל גודל, ולפרוק, ולכן אלה מתפרסמים בלוח הגדול, שבו תוכל להתחרות נגד חבריך לכיתת וכמה חברי צוות כדי לראות שיש לו את בודק האיות המהירה ביותר. דבר אחד שהייתי רוצה לציין על שולחנות חשיש הן שיש כמה פונקציות hash די פשוטות שאנחנו יכולים לחשוב עליו. לדוגמה, יש לך 26 דליים, ואז כל דלי מתאים לאות הראשונה במילה, אבל זה הולך לגרום לשולחן חשיש די לא מאוזן כי יש דברים הרבה פחות שמתחילים עם X מהתחלה עם M, למשל. דרך אחת ללכת על אית היא אם אתה רוצה לקבל את כל הפונקציונליות האחרת למטה, אז פשוט להשתמש בפונקציית hash פשוט כדי להיות מסוגל לקבל את הקוד שלך פועל ולאחר מכן לחזור ולשנות את הגודל של שולחן החשיש ואת ההגדרה. יש הרבה משאבים באינטרנט לפונקציות hash, וכן לpset זה אתה רשאי לחקור פונקציות hash באינטרנט לכמה רמזים והשראה, כל עוד אתה מקפיד לצטט איפה קנית אותו מ. אתם מוזמנים לחפש ולפרש חלק פונקציית hash שאתה מוצא באינטרנט. אחזור לזה, ייתכן שתוכל, כדי לראות אם מישהו השתמש איירי אם היישום שלהם הוא מהיר יותר מאשר שולחן החשיש או לא. אתה יכול להגיש ללוח הגדול מספר פעמים. זה יהיה להקליט הכניסה האחרונה שלך. אז אולי תשנה את פונקציית hash שלך ואז אני מבין שבעצם זה הרבה יותר מהר או הרבה יותר איטי מאשר בעבר. זה קצת דרך מהנה. תמיד יש 1 או 2 אנשי צוות שמנסים להפוך את המילון האיטי ביותר האפשרי, כך שתמיד כיף להסתכל עליו. 

השימוש לpset הוא שאתה מפעיל אית עם מילון אופציונלי ואז קובץ טקסט חובה. כברירת מחדל כאשר אתה מפעיל אית רק עם קובץ טקסט ולא תציין מילון, זה הולך להשתמש בקובץ טקסט המילון, אחד הגדול בתיקיית cs50/pset5/dictionaries. אחד שיש מעל 100,000 מילים. יש להם גם מילון קטן שבו יש הרבה פחות מילים שCS50 עשה בשבילך. עם זאת, אתה יכול מאוד בקלות פשוט לעשות מילון משלך אם אתה רק רוצה שזה עובד בדוגמאות קטנות - למשל, אם ברצונך להשתמש gdb ואתה יודע את הערכים הספציפיים שברצונך לשולחן החשיש למפות ל. אז אתה יכול פשוט להפוך את קובץ הטקסט שלך רק עם בר, באז, פ.ו., וfoobar, לעשות את זה בקובץ טקסט, פרד כל אלה עם קו 1, ולאחר מכן להפוך את קובץ הטקסט שלך, פשוטו כמשמעו, שמכיל אולי 1 או 2 מילים בלבד כך שאתה יודע בדיוק מה צריך להיות הפלט. חלק מקבצי הטקסט לדוגמא שעל הלוח הגדול כשאתה מפעיל את האתגר יבדוק הם מלחמה ושלום ורומן אוסטן ג'יין או משהו כזה. לכן, כאשר אתה מתחיל, זה הרבה יותר קל לעשות קבצי טקסט משלך שמכיל רק כמה מילים או אולי 10 כך שאתה יכול לחזות מה יהיה התוצאה צריכה להיות ואז לבדוק את זה מול זה, ולכן יותר מדוגמה מבוקרת. וכך מאז שאנחנו עוסקים בניבוי וציור דברים מסביב, שוב אני רוצה לעודד אותך להשתמש בעט ונייר כי זה באמת הולך לעזור לך עם זה - ציור החצים, איך שולחן החשיש או איך איירי שלך נראית, כשאתה משחרר משהו שבו החצים הולכים, אתה מחזיק במספיק, אתה רואה כל קשר נעלם ונופל לתהום של זיכרון דלף. אז אנא, נסה לצייר אותו עוד לפני שמגיע לכתיבת קוד. לצייר דברים החוצה, כך שאתה מבין איך דברים הולכים לעבוד כי אז אני מבטיח לך לרוץ לתוך מבוכות מצביע פחות שם. 

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

[CS50.TV]