>> ZAMYLA צ'אן: בואו נעשה את בודק איות.
אם אתה פותח speller.c, אז אתה תראה כי רוב פונקציונלי עבור
בדיקת קובץ טקסט נגד מילון הוא כבר עשה בשבילך.
. / איות, עוברת בטקסט מילון להגיש ואז עוד קובץ טקסט,
יבדוק שקובץ הטקסט כנגד המילון.
>> עכשיו, קבצי טקסט מילון יכילו מילות תקפות, אחד בכל שורה.
אז speller.c יקרא טען בקובץ טקסט המילון.
זה יהיה לקרוא לפונקציה שנקראת בדוק על כל מילה בקובץ הטקסט שהוזן,
הדפסה כל המילים באיות שגוי.
>> Speller.c גם יקרא לגודל לקבוע את מספר המילים ב
ביטול טעינת מילון ולקרוא כדי לפנות מקום בזיכרון.
speller.c גם לעקוב אחר כמה הרבה זמן הוא משמש כדי לנהל מאלה
תהליכים, אבל אנחנו תגיע לזה מאוחר יותר.
>> אז מה אנחנו צריכים לעשות?
אנחנו צריכים למלא בdictionary.c.
בdictionary.c, יש לנו את העוזר טען פונקציה, שטוען את
מילון.
עזיבה הפונקציה, שבודקת אם מילת נתונה היא במילון.
גודל הפונקציה מחזיר את המספר של מילות במילון.
ולבסוף, יש לנו לפרוק, אשר משחרר את המילון מזיכרון.
>> אז קודם כל, בואו להתמודד עם עומס.
לכל מילה בטקסט המילון קובץ, עומס יהיה לאחסן את המילים האלה ב
מבנה נתוני מילון על פי הבחירה, גם שלך
חשיש שולחן או הגיבורים.
אני אלך על שניהם ב זה ללכת דרך.
>> ראשית בואו נדבר על שולחנות חשיש.
אומר שהיה לך 10 כדורי ביליארד ו אתה רוצה לאחסן אותם.
אתה יכול לשים את כולם בדלי, וכאשר אתה צורך ספציפי
ממוספר כדור, הייתי לך לקחת את אחד מתוך הדלי בכל פעם
מחפש את הכדור.
ועם רק 10 כדורים, אתה צריך להיות תוכל למצוא את הכדור בסביר
כמות של זמן.
>> אבל מה אם היה לך 20 כדורים?
זה עלול לקחת קצת יותר זמן עכשיו.
מה לגבי 100?
1,000?
עכשיו, זה יהיה הרבה יותר קל אם היו לך דליים מרובים.
אולי דלי אחד לכדורים ממוספרים אפס עד תשע, עוד דלי ל
כדורים ממוספרים 10 דרך 19, וכן הלאה.
>> עכשיו כשאתה צריך לחפש ספציפי כדור, אתה עלול באופן אוטומטי
ללכת לדלי אחד ספציפי ו חיפוש באמצעות דלי ש.
ואם כל אחד מהסלים יש כ 10 כדורים, אז אתה יכול לחפש בקלות
דרכו.
>> עכשיו, עם שכן יש לנו עסק מילונים, דלי אחד ל
את כל המילים במילון יהיה כנראה יהיה הרבה פחות מדי דליים.
אז בואו נסתכל על שולחנות חשיש.
>> תחשוב על זה כמו מערך של דליים.
ובמקרה הזה, הדליים הן הרשימות המקושרות שלנו.
ואנחנו אחלק את כל המילים שלנו בין הרשימות המקושרות אלה מרובים ב
דרך מאורגנת באמצעות פונקצית חשיש, שיגיד לנו ש
דלי מפתח נתון, נתון מילה, שייכת.
>> בואו לייצג את זה באופן סכמטי.
קופסות הכחולות כאן מכילות ערכים ו תיבות אדומות מצביעות על ערך אחר
זוג מצביע.
אנחנו קוראים לצומת זוגות אלה.
עכשיו, כל אחד מהסלים, כפי שאמרתי קודם לכן, היא רשימה מקושרת.
ברשימות מקושרות, יש כל צומת ערך, כמו גם מצביע ל
הערך הבא.
>> עכשיו, העוסק ברשימות מקושרות, זה מאוד חשוב כי אתה
לא לאבד את כל קישורים.
ועובדה נוספת שיש לזכור היא ש צומת שעברה, אם זה לא מצביע על
צומת אחר, מצביע על null.
>> אז איך אנחנו מייצגים את זה ב-C?
אנו מגדירים struct שלנו כאן.
והערך במקרה זה הוא מערך תווים של אורך.
אורך בתוספת 1, שבו אורך הוא אורך מרבי של כל מילה, בתוספת 1 ל
השליחות קטלנית null.
ואז יש לנו מצביע צומת אחר שנקרא על הבא.
>> אז בואו נעשה רשימה מקושרת קטנה.
ראשית, אתה רוצה malloc הצומת שלך, אשר יוצר מקום בזיכרון
גודלו של סוג הצומת שלך.
ולהפוך את צומת אחר, mallocing שוב.
>> עכשיו, אם אתה רוצה להקצות ערך ל מילה, אז אפשר לומר חץ node1
מילה שווה "הלו". מפעיל חץ זה dereferences המצביע ו
כניסות המשתנים של struct.
בדרך זו, אנו לא צריכים להשתמש בשתי הנקודה ומפעיל הכוכב.
>> אז יש לי מילת החץ node2 שווה "עולם". ושם, הערכים
מאוכלס בבלוטות שלי.
כדי להפוך את הקישורים, אני אעבור בnode1 חץ הבא, גישה שלכוכב צומת,
שמצביע הצומת, שווה node2, מצביע node1 לnode2 שתיים.
ויש לנו רשימה מקושרת.
>> אז זה היה רק ​​רשימה מקושרת אחד, אבל שולחן חשיש הוא מערך של כל
רשימות מקושרות.
ובכן, תהיה לנו את אותו צומת מבנה כמו קודם.
אבל אם אנחנו רוצים שולחן חשיש בפועל, אז אנחנו יכולים רק לעשות את מצביע צומת
מערך כאן.
לדוגמא, גודל 500.
>> עכשיו שימו לב, יש הולך להיות מסחרי off בין הגודל שלך
שולחן חשיש והגודל של הרשימות המקושרות שלך.
אם יש לך מספר ממש גבוה של דליים, לדמיין צורך לרוץ חזרה
ושוב בקו ל למצוא הדלי שלך.
אבל אתה גם לא רוצה מספר קטן דליים, כי אז אנחנו חוזרים ל
הבעיה המקורית של איך שיש כדורים רבים מדי בדלי שלנו.
>> בסדר, אבל איפה הכדור שלנו הולך?
ובכן, ראשית עלינו יש כדור, נכון?
אז בואו malloc צומת לכל מילה חדשה שיש לנו.
צומת * שווים new_node malloc (sizeof (צומת)).
>> עכשיו שיש לנו את המבנה הזה, אנחנו ניתן לסרוק ב, באמצעות הפונקציה
fscanf, מחרוזת מהקובץ שלנו, אם זה קובץ מילון, לתוך
מילת חץ new_node, שם new_node מילת חץ היא שלנו
יעד של המילה.
>> בשלב הבא, אנחנו רוצים חשיש ש מילה באמצעות פונקצית חשיש.
פונקציית hash לוקחת מחרוזת ומחזיר את אינדקס.
במקרה זה, המדד צריך להיות פחות ממספר
דליים שיש לך.
>> עכשיו, פונקציות חשיש, כאשר אתה מנסה למצוא אחד וליצור אחד
משלך, יש לזכור כי הם צריך להיות דטרמיניסטי.
זה אומר שאותו הערך צריך המפה לאותו דלי בכל פעם
שהחשיש זה.
>> זה כמו סוג של ספרייה.
כשאתה לוקח ספר, המבוסס על מחבר, אתה יודע איזה מדף הוא צריך
להמשיך, בין אם זה מספר מדף אחד, שתיים, או שלוש.
וספר שתמיד יהיה שייך על אף אחד מן המדף, שתיים, או שלוש.
>> לכן, אם מילת חץ new_node יש מילה מהמילון שלך, אז
מילת חץ new_node ליבון תהיה נותן המדד שלנו
דלי של שולחן החשיש.
ואז אנחנו נכניס את זה לתוך זה רשימה ספציפית קשורה שצוינה על ידי
להחזיר ערך של פונקציית hash שלנו.
>> בואו נסתכל על דוגמא של החדרת צומת אל
התחלה של רשימה מקושרת.
אם הראש הוא מצביע צומת שמצביעה על תחילת מקושרת
הרשימה, וnew_node מציין החדש צומת שאתה רוצה להיכנס ב, רק
הקצאה ועד ראש new_node תאבד הקישור לשאר הרשימה.
אז אנחנו לא רוצים לעשות את זה.
>> במקום זאת, אנו רוצים לוודא שאנחנו נאחזים בכל
צומת יחידה בתכנית שלנו.
שווים הבאים חץ new_node אז פועל ראש ולאחר מכן את הראש שווה new_node
ישמור את כל קישורים ולא לאבד את כל.
>> אבל מה אם אתה רוצה את הרשימה שלך להיות מיון, משום שמסודר מקושר
רשימה עשויה להיות קלה יותר עבור מחפש אותו בשלב מאוחר יותר?
ובכן, בשביל זה, אתה צריך לדעת איך לעבור רשימות מקושרות.
>> לחצות רשימה מקושרת, בואו מצביע צומת, * צומת, לפעול כ
הסמן שלך, המציין איזה צומת שאתה ב, החל
במרכיב הראשון.
הלולאה עד הסמן היא ריקה, אנחנו יכולים לנהל תהליכים מסוימים ולאחר מכן
לקדם את הסמן כאשר אנחנו צריכים באמצעות ערך של חץ סמן.
>> זכרו, זה אותו הדבר כמו אומר סמן כוכב, ביטול הפניה למבנה
סמן, ולאחר מכן באמצעות ערך מפעיל נקודה.
אז לעדכן את הסמן על ידי הקצאה את הסמן לחץ הסמן הבא.
>> אומר לך לקבוע שD הופך ב בין C ו-E כדי להכניס את הצומת,
יש נקודת D new_node ל E צומת, שהוא הסמן הבא.
ואז C, הסמן, יכול לאחר מכן הצבע לד בדרך זו, לשמור על רשימה.
היזהר לא לאבד את הקישורים שלך על ידי הזזת סמן החץ לצד D
מייד.
>> בסדר.
אז ככה אתה יכול להכניס את צמתים, לטעון אותם ב, מילות עומס לאלה
צמתים, ולהכניס אותם לשולחן החשיש שלך.
אז עכשיו בואו נסתכל על ניסיונות.
>> בגיבורים, בכל צומת תכיל מערך של מצביעים לצומת, אחד לכל
מכתב באלפבית בתוספת גרש.
וכל אלמנט במערך יצביע לצומת אחרת.
אם הצומת היא null אז שהמכתב, הוא לא הולך להיות המכתב הבא של
כל מילה ברצף, משום שכל מילה מציינת אם זה אחרון
אופייה של מילה או לא.
>> בואו נסתכל על תרשים.
אני מקווה שדברים יהיו להיות קצת יותר ברור.
בתרשים זה, אנו רואים כי רק אותיות מסוימות ומחרוזות מסוימות
נמצאים ברשימה החוצה.
אז אתה יכול לעקוב אחר נתיבים מסוימים, ו כל השבילים האלה יובילו אותך
מילות שונות.
>> אז איך אנחנו מייצגים את זה ב-C?
ובכן, בכל צומת עכשיו הוא הולכת להיות ערך בוליאני המציין אם
צומת שהיא בסופו של מילה מסוימת או לא.
ואז זה יהיה גם מערך של מצביעי צומת נקראים ילדים, ו
יש הולכים להיות 27 שלהם.
ותזכור, גם אתה תרצה לעקוב אחר הקשר הראשון שלך.
אנחנו הולכים לקרוא לשורש הזה.
>> אז זה המבנה של הגיבורים.
איך אנחנו מייצגים את זה כמילון?
ובכן, כדי לטעון במילים, לכל מילה במילון, אתה הולך רוצה
כדי לחזר דרך הגיבורים.
וכל אלמנט בילדים מתאים לאות אחרת.
>> אז בודק את הערך בילדים i אינדקס, שבו אני מייצג את
מדד ספציפי של המכתב ש אתה מנסה להוסיף.
ובכן, אם זה ריק, אז אתה רוצה malloc צומת חדשה ויש לי ילדים
אני מצביע לצומת.
>> אם זה לא ריק, אז זה אומר ש שענף נתון, שניתן
מחרוזת, כבר קיימת.
אז אתה פשוט לעבור לכי צומת חדשה ולהמשיך.
אם אתה בסוף המילה ש אתה מנסה לטעון ב
מילון, אז אתה יכול להגדיר ש צומת נוכחית שאתה על לנכון.
>> אז בואו נסתכל על דוגמא של החדרה המילה "שועל" לשלנו
מילון.
להעמיד פנים שאנחנו מתחילים עם מילון ריק.
המכתב הראשון, F, יהיה ממוקם במדד חמישה ילדים של השורשים
מערך ילדים.
אז אנחנו הכניסו שבו
>> לאחר מכן האות O יהיה בילדים מדד 15, לאחר שפ ואז X
יהיה אפילו מתחת לזה, הסתעפות את הילדים של O.
ולאחר מכן, כי X הוא האות האחרונה במילה "השועל", ואז אני הולך
צבע ירוק שכדי לציין כי זה הסוף של המילה.
ב-C, שיהיה קביעת האם מילה בוליאנית לערך האמיתי.
>> עכשיו מה אם המילה הבאה שאתה טעינה בהיא המילה "foo"?
ובכן, אתה לא צריך malloc יותר מקום לF או לO, כי
אלו שכבר קיימים.
אבל O האחרון בfoo?
אחד שיהיה לך לmalloc.
הפוך צומת חדשה בשביל זה, הגדרה הוא המילה בוליאנית לנכון.
>> אז עכשיו בואו הכניסו "כלב". כלב תתחיל עם מדד של שלושה השורשים
ילדים, כי D יש לא נוצר עדיין.
ואנו עוקבים אחר תהליך דומה כמו לפני, יצירת כלב המחרוזת,
איפה G הוא בצבע ירוק, כי זה הסוף של מילה.
>> עכשיו, מה אם אנחנו רוצים להכניס "לעשות"?
ובכן, זה הוא מחרוזת של כלב, ולכן אנחנו לא צריכים לmalloc יותר.
אבל אנחנו צריכים לעשות כדי לציין היכן יש לנו הגיע לסוף של המילה.
אז O יהיה בצבע ירוק.
בהמשך תהליך שעל כל אחת מילה במילון שלך, יש לך
העמיס אותם באל או משלך חשיש שולחן או הגיבורים שלך.
>> speller.c יעבור במחרוזות עבור dictionary.c כדי לבדוק אותם.
עכשיו, פונקצית עזיבה יש לפעול תחת מקרה חוסר רגישות.
זה אומר שאותיות גדולות ו אותיות קטנות ושילוב של שניהם
צריך כל שווה ל אמיתי אם בכלל שילוב של שהוא ב
מילון.
ניתן גם להניח שמחרוזות רק הולך להכיל אלפביתי
תווים או גרשיים.
>> אז בואו נסתכל איך אתה יכול לבדוק עם מבנה שולחן חשיש.
ובכן, אם המילה קיימת, אז זה ניתן למצוא בטבלת הגיבוב.
אז אתה יכול לנסות למצוא את זה מילה בדלי הרלוונטי.
>> אז איזה דלי הייתי מילה שתהיה ב?
ובכן, היית מקבל את המספר, מדד ה הדלי, על ידי ליבון מילה ש
ולאחר מכן בחיפוש שברשימה מקושרת, חוצה דרך כל
רשימה מקושרת, תוך שימוש במחרוזת שקלו את הפונקציה.
>> אם בסוף הרשימה המקושרת הוא הגיע, כלומר את הסמן
מגיע ריק, ולאחר מכן את המילה אינה ניתן למצוא במילון.
זה לא יהיה בכל דלי אחר.
אז הנה, אתה עשוי לראות כיצד יש אולי להיות תחלופה בין שיש גם
מסודרים על רשימות מקושרות או ממוינים אלה.
כך או ייקחו יותר זמן במהלך לטעון או יותר זמן במהלך בדיקה.
>> איך אתה יכול לבדוק ב מבנה הגיבורים?
אנחנו הולכים לנסוע כלפי מטה בגיבורים.
לכל אות במילה שהוזן שאנחנו בודקים, נלך לזה
מתאים אלמנט בילדים.
>> אם האלמנט שהוא ריק, אז זה אומר כי אין מחרוזות
המכיל מילת הקלט שלנו, ולכן המילה באיות שגוי.
אם זה לא ריק, אנחנו יכולים לעבור ל האות הבאה של המילה שאנחנו
בדיקה ולהמשיך את התהליך הזה עד שאנחנו מגיעים לסוף
של מילת הקלט.
ואז אנחנו יכולים לבדוק אם הוא המילה נכונה.
אם כן, אז נהדר.
המילה נכונה.
אבל אם לא, אף על פי שמחרוזת קיים בגיבורים, המילה היא
באיות שגוי.
>> כאשר גודל הפונקציה נקרא, גודל צריך להחזיר את מספר המילים ש
נמצא במילון שלך נתון מבנה הנתונים.
אז אם אתה משתמש בשולחן חשיש, אתה יכול גם לעבור בכל אחת
רשימה מקושרת בכל אחת דלי לספור את המספר
מילים נמצאים שם.
אם אתה משתמש בגיבורים, אתה יכול לעבור כל null שאינו
נתיב בגיבורים שלך.
או בזמן שאתה טוען את המילון ב, אולי אתה יכול לעקוב אחר כמה
מילות רבות שאתה מעמיס פנימה
>> ברגע שיסיים את בדיקת speller.c קובץ טקסט נגד המילון, ולאחר מכן
עושה את זה ולכן הוא קורא לפרוק, שבו התפקיד שלך הוא לשחרר את כל דבר
כי אתה כבר malloced.
אז אם אתה משתמש בשולחן חשיש, אז אתה צריך להיות זהיר במיוחד, כדי למנוע
דליפות זיכרון בכך שלא לשחרר שום דבר בטרם עת ומחזיק בכל
קישור אחד לפני שאתה חופשי.
>> אז לכל אלמנט בטבלת החשיש ועבור כל צומת ברשימה המקושרת,
אתה רוצה לשחרר את הצומת.
איך אתה הולך על שחרור רשימה מקושרת?
הגדרת הסמן מצביע הצומת שלך הראש, ועד לתחילת
רשימה מקושרת, אז בזמן שהסמן הוא לא ריק, אתה יכול להגדיר זמני
מצביע צומת לסמן שלך.
לאחר מכן לקדם את הסמן.
ואז אתה יכול לשחרר את זה זמני בזמן שערך עדיין מחזיק ב
כל מה שלאחר מכן.
>> מה אם אתה משתמש בגיבורים?
אז הדרך הטובה ביותר לעשות זאת הוא לפרוק ממאוד
תחתון לעליון.
על ידי נסיעה הנמוכה ביותר האפשרי צומת, אתה יכול לשחרר את כל המצביעים ב
כי ילדים ולאחר מכן לחזור על עקבות כלפי מעלה, לשחרר את כל האלמנטים בכל
של מערכי ילדים, עד אתה מכה צומת השורש העליונה שלך.
כאן המקום רקורסיה יהיה שימושי.
>> כדי לוודא שיש לך כנראה ישוחרר כל מה שיש לך malloced,
אתה יכול להשתמש Valgrind.
פועל Valgrind יהיה להפעיל את התכנית שלך לספור כמה בתים של זיכרון
אתה משתמש ולוודא שיש לך שחרר את כולם, אומר לך
שבו אתה יכול להיות שכחתי חופשי.
אז להריץ את זה וברגע שאומר לך Valgrind ונותן לך ללכת קדימה, ולאחר מכן
שתסיים לפרוק.
>> עכשיו, כמה טיפים לפני שאתה הולך את ולהתחיל ביישום שלך
מילון.
הייתי ממליץ לעבור בקטן יותר מילון כשאתה מנסה לבדוק
דברים החוצה וניפוי שגיאות בתמ"ג.
השימוש באיות הוא. / איות, מילון אופציונלי ולאחר מכן טקסט.
>> כברירת מחדל, הוא טוען ב המילון הגדול.
אז אולי כדאי לך לעבור בקטן מילון, או אולי אפילו לגרום לך
המילון שלו, ההתאמה האישית שלך וקובץ הטקסט שלך.
>> ולבסוף, הייתי גם ממליץ לקחת עט ונייר ולצייר
דברים לפני, במהלך, ואחרי שכתבת את כל הקוד שלך.
רק לוודא שיש לך המצביעים האלה בדיוק.
>> אני מאחל לך את הטוב ביותר של מזל.
וברגע שתסיים, אם תרצה לקרוא תיגר על הלוח וגדול
לראות כמה מהר את התכנית שלך היא לעומת 'החברים לכיתה שלך, אז אני ממליץ
לך לבדוק את זה.
>> עם זה, שתסיים PSet האיות.
השם שלי הוא Zamyla, וזה CS50.