[Powered by Google Translate] [שבוע 4]
[הדוד י מלאן] [אוניברסיטת הרווארד]
[זה CS50.] [CS50.TV]
>> בסדר, זה CS50, וזו היא ההתחלה של שבוע 4,
וזה אחד מאלגוריתמי המיון האיטי ביותר האפשריים.
מה זה היה שאנחנו רק הסתכלנו שם?
זה היה סוג של בועה, בהזמנה הגדולה של O (n ^ 2) + סכום,
ואכן אנחנו לא היחידים בעולם הזה להיראות לדעת
מה הוא מיון בועות או זמן הריצה שלו.
ואכן, זה היה ראיון עם אריק שמידט של גוגל
והסנטור לשעבר ברק אובמה רק לפני כמה שנים.
>> עכשיו, סנטור, אתה כאן בגוגל,
ואני רוצה לחשוב על הנשיאות כראיון עבודה.
כעת, קשה למצוא עבודה כנשיא, ואתם עוברים את התלאות היום.
קשה גם לקבל עבודה בגוגל.
יש לנו שאלות, ועלינו לשאול שאלות המועמדים שלנו,
ואת זה הוא מלארי שווימר.
אתם חושבים שאני מתלוצץ? זה ממש כאן.
מה היא הדרך היעילה ביותר כדי למיין מיליון מספרים שלמים של 32-bit?
[שחוק]
ובכן
אני מצטער. >> לא, לא, לא, לא.
אני חושב שמיון הבועות יהיה בדרך הלא הנכונה ללכת.
>> קדימה, שאמר לו את זה?
בשבוע שעבר זוכר שלקחנו הפסקה מקוד, לפחות ליום אחד,
והתחיל להתמקד בכמה רעיונות גבוהים יותר ברמה ופתרון בעיות באופן כללי יותר
בהקשר של חיפוש ומיון,
והצגנו משהו שאנחנו לא סטרנו על שם זה בשבוע שעבר,
אבל סימון אסימפטוטי, ביג O, האומגה הגדולה,
ולפעמים הכיתוב הגדול תטא, ואלה היו פשוט דרכים
לתאר את זמן הריצה של אלגוריתמים,
כמה זמן לוקח לאלגוריתם לרוץ.
>> ואולי זכרו לך שדבר על זמן הריצה במונחים של הגודל
של הקלט, שאנחנו בדרך כלל קוראים n, מה שעשויה להיות הבעיה,
כאשר n הוא מספר האנשים בחדר,
מספר עמודים בספר טלפונים, והתחלנו לכתוב את הדברים
כמו O (n ^ 2) או O (n) או O (n log n),
וגם כאשר המתמטיקה לא ממש הסתדר כל כך מושלמת
וזה היה n ² - n / 2 או משהו כזה
אנחנו במקום פשוט לזרוק כמה מונחים מסדר הנמוכים יותר,
והמוטיבציה שיש שאנחנו באמת רוצים
סוג של דרך אובייקטיבית של הערכה
ביצועים של תוכניות או את הביצועים של אלגוריתמים
כי בסופו של היום יש מה לעשות, למשל,
עם המהירות של המחשב שלך היום.
>> לדוגמה, אם אתה מיישם את מיון בועות,
או שתיישם למזג מיון מיון או בחירה במחשב של היום,
2 GHz מחשב, ואם מפעילים אותו,
וזה לוקח קצת מספר השניות, בשנה הבאה יש 3 GHz
או 4 מחשב GHz, וייתכן שלאחר מכן טוענים כי "וואו, האלגוריתם שלי
עכשיו היא במהירות כפולה, "כאשר במציאות זה כמובן לא המקרה.
זה רק החומרה קבלה מהר יותר, אבל המחשב שלך
לא, ואז אנחנו באמת רוצים לזרוק דברים כמו
כפולות של 2 או כפולות של 3 כשמדובר מתאר
כמה מהר או לאט איך אלגוריתם הוא באמת ולהתמקד רק בי
על n או כל גורם ממנה,
כמה הכח כמו במקרה של המיני משבוע שעבר.
וזוכרים שעם העזרה של מיון מיזוג
היינו יכול לעשות כל כך הרבה יותר טוב ממיון בועות ומיון בחירה
ואפילו סוג כניסה.
>> ירדנו אל n log n, ושוב,
זוכר שהיומן n בדרך כלל מתייחס למשהו שצומח
לאט יותר אז n, אז n log n עד כה היה טוב
כי זה היה פחות מ ² n.
אבל כדי להשיג n להתחבר n עם סוג המיזוג
מה היה החיידק הבסיסי של רעיון שהיו לנו למנף
שגם אנחנו ממונפים לאחור בשבוע 0?
איך הייתי להתמודד עם הבעיה בחוכמה עם סוג מיון מיזוג?
מה הייתה תובנה המרכזית, אולי?
מישהו בכלל.
אוקיי, בואו ניקח צעד אחורה.
תאר למזג מיון במילים שלך.
איך זה עובד?
בסדר, לחתור חזרה ל0 שבוע.
בסדר, כן.
[לא ברור לתלמיד]
אוקיי, טוב, אז אנחנו מתחלקים מערך המספרים לתוך 2 חתיכות.
אנחנו מסודרים כל אחד מהחלקים האלה, ואז מזגו אותם,
ושראינו את הרעיון הזה לפני נטילת בעיה שזה גדול
ותקצוץ אותו לבעיה שזה גדול או בגודל כזה.
>> זוכר את דוגמא ספר טלפונים.
היזכר באלגוריתם עצמו משבועות לפני הספירה,
מין כל כך למזג סכם pseudocode זה כאן.
כאשר אתה נתון אלמנטי n, בהתחלה זה היה שפיות לבדוק.
אם n <2 אז לא עושים שום דבר
כי אם n <2 אז n הוא כמובן 0 או 1,
ולכן אם הוא או 0 או 1 אין מה למיין.
אתה עשית.
הרשימה שלך כבר מסודרת trivially.
אבל חוץ מזה אם יש לך 2 או יותר אלמנטים קדימה ולחלקם
ל 2 חצי, ימין ושמאל.
מיין את כל אחת מהמחציות הללו, ולאחר מכן למזג את החצאים הממוינים.
אבל הבעיה כאן היא שבמבט ראשון זה מרגיש כאילו אנחנו חתירה.
זו הגדרה מעגלית שבאם שאלתי אותך כדי למיין n האלמנטים הללו
ואתה אומר לי "בסדר, בסדר, אנחנו נטפל אלה n / 2 ואלו n / 2 אלמנטים",
אז השאלה הבאה שלי הולכת להיות "בסדר, איך אתה למיין את n / 2 אלמנטים?"
>> בגלל המבנה של התכנית הזו, אבל,
כי יש מקרה בסיס זה, אם אפשר לומר כך,
המקרה המיוחד הזה שאומר שאם n הוא <ערך קבוע מסוים כמו 2 תשואה באופן מיידי.
אל תגיב באותה תשובה מעגלית.
תהליך זה, מחזוריות זו סופו של דבר בסופו.
אם אני שואל אותך "מיין אלמנטי n אלה," ואתה אומר, "בסדר, למיין n / 2 אלה",
אז אתה אומר, ", מיין משובח הללו n / 4, n / 8, n/16"
סופו של דבר תוכל לחלק במספר מספיק גדול
שתהיה לך רק 1 שמאל אלמנט, ובשלב זה ניתן לומר,
"הנה, כאן הוא אלמנט יחיד מסודר".
אז הזוהר של אלגוריתם זה עד כאן הוא נובע מהעובדה
כי ברגע שיש לך את כל הרשימות הללו לחוד,
כל אלה הם בגודל 1, שנראה כחסרים תועלת,
ברגע שתתחיל ממזג אותם וממזג אותם
אתה בונה את סוף הסוף כמו רוב עשה בוידאו רשימה לבסוף מסודרת.
>> אבל הרעיון הזה חורג הרבה מעבר למיון.
יש רעיון זה מוטבע בתכנית זו המכונית רקורסיה,
הרעיון לפיו אתה נמצא תכנית,
כדי לפתור בעיה כלשהי אתה קורא לעצמך ו,
או לשים בהקשר של שפות תכנות אתה פונקציה,
ועל מנת לפתור את הבעיה, אתה קורא לעצמך פונקציה
שוב ושוב ושוב, אבל אתה פונקציה
לא יכול לקרוא לעצמך אינסוף פעמים.
סופו של דבר יש לך למטה אותו, כביכול,
ויש מצב בסיס קבוע בקוד שאומר
בשלב זה להפסיק לקרוא את עצמך כך שהתהליך כולו
סוף הסוף עושה למעשה להפסיק.
מה זה באמת אומר, לרקורסיבית?
>> בואו נראה אם ​​אנחנו יכולים לעשות את דוגמה פשוטה, טריוויאלי, למשל,
3 אנשים עם אותי כאן על במה, אם מישהו נוח.
1, בואו ניכנס, 2 ו 3.
אם אתה רוצה 3 שתבואו לכאן.
אם אתה רוצה לעמוד ממש לידי כאן בשורה, מניח שבעיה ביד
מאוד trivially הוא לספור את מספר האנשים שנמצאים כאן.
אבל בכנות, אני עייף מכל הדוגמות הללו הספירה.
זה הולך לקחת קצת זמן, 1, 2, ונקודה, נקודה, נקודה.
זה הולך להימשך לנצח.
אני מעדיף פשוט דוגית בעיה זו לחלוטין עם העזרה של-מה השם שלך?
שרה. >> שרה, הכל בסדר.
קלי. >> קלי ו?
>> ווילי. >> וילי, שרה, קלי, ווילי.
נכון לעכשיו אני כבר שאלתי את השאלה במישהו
כמה אנשים נמצאים על הבמה הזאת, ואין לי מושג.
זוהי רשימה ארוכה באמת, ואז במקום זה אני הולך לעשות את הטריק הזה.
אני הולך לשאול את האדם לידי לעשות את רוב העבודה,
וברגע שהיא נעשית עושה את רוב העבודה
אני הולך לעשות את הכמות המינימאלית של עבודה האפשרית ופשוט להוסיף 1
לכל התשובה שלה, אז הנה זה באנו.
אני כבר שאלתי כמה אנשים על במה.
כמה אנשים על במה משמאלך?
השמאלי שלי? >> בסדר, אבל לא לרמות.
זה טוב, זה נכון, אבל אם אנחנו רוצים להמשיך את ההגיון הזה
בואו נניח שאתה רוצה באופן דומה דוגית בעיה זו בצד השמאל שלך,
כך, במקום תשובה ישירה קדימה ופשוט להעביר את האחריות.
הו, כמה אנשים נמצאים בצד השמאל שלי?
כמה אנשים מהשמאל?
1.
[שחוק]
אוקיי, אז 0, אז מה עכשיו וילי עשה
הוא שחזר התשובה שלך כיוון זה אומר 0.
עכשיו, מה אתה צריך לעשות? >> 1.
אוקיי, אז אתה 1, כך שאתה אומר, "בסדר, אני הולך להוסיף 1
לכל הספירה של וילי היה, "אז 1 + 0.
כעת אתה 1 אז התשובה שלך לימין היא עכשיו
1. >> ושלי יהיה 2.
טוב, אז אתה לוקח את התשובה הקודמת של 1,
הוספת הכמות המזערית של עבודה שאתה רוצה לעשות, שהוא +1.
כעת יש לך 2, ואז אתה נותן לי ערך ש?
3, אני מתכוון, סליחה, 2.
טוב.
>> ובכן, היו לנו 0 עד השמאל.
ואז היה לנו 1, ולאחר מכן אנו מוסיפים 2,
ועכשיו אתה מסרת לי את המספר 2,
ולכן אני אומרת, בסדר, +1, 3.
יש אכן 3 אנשים שעמדו לידי בשלב זה,
ואז הייתי יכול לעשות את זה מאוד ברור באופן ליניארי,
מאוד באופנה הברורה, אבל מה שאנחנו באמת עשינו?
אנחנו לקחנו את הבעיה של גודל 3 בתחילה.
אז שברנו אותו לבעיה של גודל 2,
אז בעיה של גודל 1, ולבסוף מקרה הבסיס
היה באמת, אוי, אין שם איש,
ובנקודה וילי חזר יעילות תשובה בקוד כמה פעמים,
והשנייה לאחר מכן עלתה ובעבעה, פעפע, בעבע,
ולאחר מכן על ידי הוספה ב1 1 נוסף זה
אנחנו יישמנו הרעיון הבסיסי הזה של רקורסיה.
>> עכשיו, במקרה הזה זה לא באמת לפתור את הבעיה
כל בצורה יעילה יותר ואז שראינו עד כה.
אבל תחשוב על האלגוריתמים שנעשינו איתם על במה עד כה.
היו לנו 8 חתיכות של נייר על הלוח,
בוידאו כאשר היה מסתכל למספר 7, ומה שהוא באמת עשה?
ובכן, הוא לא עשה כל סוג של פרד ומשול.
הוא לא עשה שום סוג של רקורסיה.
במקום זאת, הוא פשוט עשה את האלגוריתם ליניארי זה.
אבל כאשר הצגנו את הרעיון של מספרים ממוינים על במה בהופעה חיה בשבוע שעבר
אז היה לנו האינסטינקט הזה של ללכת לאמצע,
ובשלב זה לא היה לנו רשימה קטנה יותר בגודל 4 או רשימה נוספת של גודל 4,
ואז הייתה לנו באותה הבעיה בדיוק, ולכן אנחנו חוזרים, חזרנו, חזרנו.
במילים אחרות, אנו recursed.
תודה רבה לך ל3 המתנדבים שלנו כאן עבור הוכחת רקורסיה איתנו.
>> בואו נראה אם ​​אנחנו לא יכולים לעשות את זה עכשיו קצת יותר קונקרטי,
פתרון בעיה ששוב אנחנו יכולים לעשות די בקלות,
אבל אנחנו מתכוונים להשתמש בו כקרש קפיצה ליישומו של רעיון בסיסי זה.
אם אני רוצה לחשב את הסיכום של חבורה של מספרים,
למשל, אם אתה עובר במספר 3,
אני רוצה לתת לך את הערך של 3 סיגמא,
כך הסכום של 3 + 2 + 1 + 0.
אני רוצה לקבל בחזרה את התשובה 6,
לכן אנו ליישם פונקציה זו סיגמא, פונקצית סיכום זה
כי, שוב, לוקח בקלט, ולאחר מכן מחזיר את הסיכום
מהמספר הזה את כל הדרך למטה עד 0.
אנחנו יכולים לעשות את זה די פשוט, נכון?
אנחנו יכולים לעשות את זה עם איזה סוג של מבנה מסובב,
אז תן לי להמשיך ולקבל את זה התחיל.
>> כולל stdio.h.
תן לי את עצמי לתוך עיקרי לעבוד עם כאן.
בואו נשמור את זה כsigma.c.
ואז אני הולך לכאן, ואני הולך להכריז n int,
ואני הולך לעשות את הפעולות הבאות בזמן שהמשתמש לא משתף פעולה.
בזמן שהמשתמש לא נתן לי מספר חיובי
תן לי ללכת קדימה ותנחה אותם לGetInt = n,
ולתת לי לתת להם כמה הוראות לגבי מה לעשות,
כך printf ("מספר חיובי בבקשה").
רק משהו פשוט יחסית כמו זה, כך שעד שפגענו בקו 14
כעת יש לנו מספר חיובי ככל הנראה בn.
>> עכשיו בואו נעשה עם זה משהו.
תן לי ללכת קדימה ולחשב את הסיכום, כך int סכום = sigma (n).
סיגמא הוא רק סיכום, אז אני רק כותב את זה בדרך יותר המסובכת.
אנחנו פשוט קוראים לזה סיגמא שם.
זה הסכום, ועכשיו אני הולך להדפיס את התוצאה,
printf ("הסכום הוא% d \ n", הסכום).
ואז אני אחזיר 0 למען סדר טוב.
עשינו כל מה שהתכנית הזו דורשת, פרט לחלק המעניין,
שהוא למעשה ליישם את פונקצית סיגמא.
>> תן לי לרדת לכאן לתחתית, ותנו לי להכריז על הפונקציה סיגמא.
זה חייב לקחת במשתנה זה מסוג שלם,
ומה סוג נתונים אני רוצה לחזור מן הסתם מסיגמא?
Int, כי אני רוצה את זה כדי להתאים את הציפיות שלי בקו 15.
כאן נתן לי ללכת קדימה וליישם את זה
באופן די פשוט.
>> בואו נגיד את סכום int = 0,
ועכשיו אני הולך להיות קצת ללולאה כאן
שיגיד משהו כזה,
עבור (אני int = 0; אני <= מספר; אני + +) סכום + = i.
ואז אני הולך להחזיר סכום.
אני לא הייתי יכול לבצע את זה בכל מיני דרכים.
הייתי יכול להשתמש בלולאת זמן.
הייתי יכול להיחלץ בעזרת משתנה הסכום אם אני באמת רוצה,
אבל בקיצור, אנחנו רק צריכים פונקציה שאם אני לא לפשל מצהיר סכום הוא 0.
אז זה סובב מ 0 על דרך המספר,
ועל כל איטרציה הוא מוסיף כי ערך הנוכחי לסכום ולאחר מכן מחזיר סכום.
>> עכשיו, יש אופטימיזציה קלה כאן.
זה כנראה צעד מבוזבז, אבל ניחא. זה בסדר לעת עתה.
אנחנו לפחות מנסים להיות יסודיים והולכים 0 כל הדרך למעלה.
לא קשה מאוד ודי פשוט,
אבל מסתבר שעם פונקצית סיגמא שיש לנו את אותה ההזדמנות
כפי שעשינו כאן על במה.
על במה, אנחנו ספרנו כמה אנשים היו לידי,
אלא אם אנחנו רוצים לספור את המספר 3 + 2 + 1
על עד 0 שיכולנו בדומה דוגית לפונקציה
שבמקום זאת תתאר כרקורסיבית.
הנה בואו נעשה את השפיות מהירה לבדוק ולוודא שלא עשה טעויות.
>> אני יודע שיש לפחות דבר אחד בתכנית זו שעשיתי לא בסדר.
כשפגעתי להיכנס אני הולך לקבל כל סוג של לצעוק עליי?
מה אני הולך להיות צעקתי עליו?
כן, שכחתי את האבטיפוס, ולכן אני משתמש בפונקציה שנקראת סיגמא ב 15 לקו,
אבל זה לא הצהיר עד 22 בקו, אז הכי טוב ללכת באופן יזום כאן
ולהכריז על אב טיפוס, ואני אגיד את int סיגמא (מספר int), וזהו.
זה מיושם בתחתית.
>> או בדרך אחרת שאני יכול לפתור את זה,
אני יכול להעביר את הפונקציה לשם, וזה לא רע,
אבל לפחות כאשר התוכניות שלך מתחילות לקבל ארוך, כנות,
אני חושב שיש ערך כלשהו בתמיד נתקל ראשי בחלק העליון
כך שאתה בקורא יכול לפתוח את הקובץ ולאחר מכן לראות מייד
מה התכנית עושה מבלי לחפש דרכו
מחפש שתפקידו העיקרי.
בואו נרד לחלון המסוף שלי כאן, נסה לעשות סיגמא להפוך סיגמא,
וגם אני דפוק כאן.
הצהרה המרומזת של GetInt פונקציה אומרת ששכחתי לעשות מה עוד?
[לא ברור לתלמיד]
טוב, אז כנראה טעות נפוצה, אז בואו נשאיר את זה כאן,
cs50.h, ועכשיו בואו נחזור לחלון המסוף שלי.
>> אני לנקות את המסך, ואני אעשה שידור חוזר סיגמא.
נראה שהוא חבר. תן לי עכשיו לרוץ סיגמא.
אני להקליד את המספר 3, ואני לא מקבל 6, אז לא בדיקה קפדנית,
אבל לפחות זה נראה שזה עובד במבט הראשון, אבל עכשיו בואו לקרוע אותו לגזרים,
ובואו בעצם למנף את הרעיון של רקורסיה, שוב,
בהקשר פשוט מאוד כך שבזמן של כמה שבועות
כאשר אנו מתחילים לחקור מבני נתונים יפים ממערכים
יש לנו כלי נוסף בארגז הכלים עם אשר
לתפעל מבני הנתונים האלה כפי שאנו נראים.
זו הגישה איטרטיבי, גישת לולאה המבוססת.
>> תן לי עכשיו במקום לעשות את זה.
תן לי במקום לומר שהסיכום של מספר
על עד 0 הוא באמת אותו הדבר כמו
מספר + סיגמא (מספר - 1).
במילים אחרות, בדיוק כמו שאני על במת בעט לכל אחד מאנשים הקרובים אליי,
והם בתורם המשיכו בעיטה עד שסוף סוף הגיעו לנקודת השפל בווילי,
שהיה צריך להחזיר תשובה בקידוד קשיח כמו 0.
הנה עכשיו אנחנו דומי חתירה לסיגמא
את אותו הדבר כמו שנקרא במקור, אבל תובנה המרכזית כאן
הוא שאנחנו כבר לא קוראים לסיגמא באופן זהה.
אנחנו לא עוברים בn.
אנחנו בבירור אתה עוברים במספר - 1,
אז בעיה קצת יותר קטנה, בעיה קצת יותר קטנה.
>> למרבה הצער, זה לא ממש פתרון, ולפני שאנחנו לתקן
מה שניתן לקופץ החוצה ברגע ברור בכמה מכם
תן לי ללכת קדימה ולהפוך את השידור חוזר.
נראה לי לקמפל בסדר.
תן לי שידור חוזר סיגמא עם 6.
אופס, תן לי שידור חוזר סיגמא עם 6.
ראינו את זה בעבר, אם כי בזמן האחרון בטעות גם כן.
מדוע קבל אשמת הפילוח המסתורי הזה? כן.
[לא ברור לתלמיד]
אין מקרה בסיס, ולייתר דיוק, מה שכנראה קרה?
זה סימפטום של איזו התנהגות?
תגיד את זה בקול רם יותר.
[לא ברור לתלמיד]
זה לולאה אינסופית ביעילות, ובעיה עם לולאות אינסופיות
כאשר הם כרוכים ברקורסיה במקרה זה, פונקציה שקראה לעצמה,
מה שקורה בכל פעם שאתה קורא לפונקציה?
ובכן, תחשוב על איך אנחנו ערוכים הזיכרון במחשב.
אנחנו אמרנו שיש נתח זה של זיכרון נקרא המחסנית זה בתחתית,
וכל פעם שאתה קורא לפונקצית זיכרון קצת יותר תכניס את
על הערימה כביכול הזה מכיל משתנים או פרמטרים המקומיים השל הפונקציה,
כך שאם סיגמא שיחות סיגמא סיגמא קורא סיגמא
קורא סיגמא היכן מסתיים הסיפור הזה?
>> ובכן, זה סופו של דבר הסכום הכולל צפות
זיכרון שיש לך זמין למחשב שלך.
אתה מוצף קטע שאתה אמור להישאר במסגרת,
ואתה מקבל את אשמת פילוח זה, ליבה זרקה,
ומה זרק ליבת משמעות הוא שעכשיו יש לי קובץ שנקרא ליבה
שהוא קובץ המכיל אפסים ואחדים
כי למעשה בעתיד יהיה diagnostically שימושי.
אם זה לא ברור לך איפה הבאג שלך הוא
אתה באמת יכול לעשות קצת ניתוח משפטי, אם אפשר לומר כך,
בקובץ dump ליבה זו, ששוב, היא פשוט כל חבורה של אפסים ואחדים
שבעצם מייצג את המצב של התכנית שלך בזיכרון
ברגע שהתרסק בדרך זו.
>> התיקון כאן הוא שאנחנו לא יכולים פשוט עיוור לחזור סיגמא,
המספר + סיגמא של בעיה קצת יותר קטנה.
אנחנו צריכים שיהיו איזשהו מקרה בסיס כאן,
ומה צריך מקרה הבסיס כנראה יהיה?
[לא ברור לתלמיד]
אוקיי, אז עוד המספר חיובי שצריך להחזיר את זה,
או במילים אחרות, אם מספר הוא, יניח, <= ל 0
אתה יודע מה, אני אמשיך הלאה ולהחזיר 0,
כמו ווילי עשה, ואחר, אני הולך קדימה
ולהחזיר את זה, אז זה לא כל כך הרבה יותר קצר
יותר מהגרסה איטרטיבי שהצלפנו באמצעות ראשון ללולאה,
אבל שם לב שיש סוג כזה של אלגנטיות אליו.
במקום להחזיר חלק מספר וביצוע כל מתמטיקה זה
והוספת דברים עם משתנים מקומיים
אתה במקום אתה אומר "בסדר, אם מדובר בבעית סופר קלה,
כמו המספר הוא <0, הרשה לי להחזיר 0 באופן מיידי ".
>> אנחנו לא הולכים להטריד את המספרים שליליים תומכים,
אז אני הולך לקוד קשה הערך של 0.
אבל חוץ מזה, כדי ליישם את הרעיון הזה של סיכום
כל המספרים האלה יחד אתה יכול למעשה לקחת ביס קטן
מתוך הבעיה, ממש כמו שעשינו פה על במה,
אז דוגית שאר הבעיה לאדם הבא,
אבל במקרה הזה האדם הבא הוא אתה עצמך.
זה פונקציה בשם זהה.
רק להעביר אותו קטנה יותר וקטנה יותר ויותר בעיה בכל פעם,
ולמרות שיש לנו דברים לא פורמלית למדי בקוד כאן
זה בדיוק מה שקרה בשבוע 0 עם ספר טלפונים.
זה בדיוק מה שקורה בשבועות אחרונים עם שון
ועם ההפגנות של חיפוש מספרים שלנו.
זה לקחת בעיה וחלוקתו שוב ושוב.
>> במילים אחרות, יש דרך עכשיו בתרגום
מבנה זה עולם אמיתי, מבנה זה רמה גבוה יותר
של פרד ומשול ועושה משהו שוב ושוב
בקוד, אז זה משהו שאנחנו רואים שוב לאורך זמן.
עכשיו, כמו בצד, אם אתה חדש ברקורסיה אתה צריך לפחות להבין עכשיו
למה זה מצחיק.
אני הולך ל-google.com,
ואני הולך לחפש כמה טיפים וטריקים על רקורסיה, זן.
תגיד אדם שלידך אם הם לא צוחקים רק עכשיו.
האם התכוונת רקורסיה?
האם התכוון ל-אה, יש לנו ללכת.
אוקיי, עכשיו זה המנוחה של כולם.
ביצת פסחא קטנה מוטבעת איפשהו שם בגוגל.
במאמר מוסגר, אחד מהקישורים שאנחנו מעבירים באתר האינטרנט של הקורס
להיום היא רק רשת זו של אלגוריתמי מיון שונים,
חלק בו אנו נראים בשבוע שעבר, אבל מה שיפה זה הדמיה
כפי שאתה מנסה לקלוט את הדברים שונים הקשורים לאלגוריתמים
יודע שאתה יכול מאוד בקלות עכשיו להתחיל עם סוגים שונים של תשומות.
כל הכניסות הפוכות, התשומות מסודרות בעיקר, את התשומות אקראיות וכן הלאה.
כפי שאתה מנסה, שוב, להבדיל את הדברים האלה בראש שלך
מבין שכתובת URL זו באתר האינטרנט של הקורס בדף ההרצאות
עשוי לעזור לך סיבה דרך כמה מאלה.
>> היום אנחנו סוף הסוף לפתור את הבעיה הזו ממזמן,
שהיה שפונקצית swap זה פשוט לא עבדה,
ומה היה הבעיה הבסיסית עם החלפה בפונקציה זו,
שמטרתה הייתה, שוב, להחליף ערך כאן וכאן
כך שזה קורה?
זה ממש לא עבד. למה?
כן.
[לא ברור לתלמיד]
בדיוק, הסבר לזה bugginess
פשוט בגלל שכשאתה קורא פונקציות ב-C
והפונקציות האלה לקחת טיעונים, כמו ב וכאן,
אתה עובר בעותקים של כל ערך שאתה מספק לתפקוד.
אתה לא מספק את הערכים המקוריים עצמם,
כך ראינו את זה בהקשר של buggyc,
buggy3.c, שנראה משהו קטן כזה.
>> זוכר שהיו לנו x ו-y מאותחלים ל 1 ו 2, בהתאמה.
אז הדפיס את מה שהם היו.
אז טענתי שאני מחליף אותם על ידי קריאת החלפה של x, y.
אבל הבעיה הייתה שההחלפה עבדה,
רק בהיקף של ההחלפה אבל פונקציה עצם.
ברגע שפגענו בקו 40 הערכים המוחלפים האלה
הושלכו לפח, וכך דבר
בתפקידו המקורי עיקרי בעצם השתניתי כלל,
כך שאם אתה חושב אז על מה זה נראה כמו במונחים של הזיכרון שלנו
אם צד שמאל של הלוח מייצג-
ואני אעשה את הכי טוב שלי לכולם לראות את זה, אם צד השמאלי של הלוח
מייצג, יניח, זכרון RAM שלך, והערימה הולכת לגדול בעד דרך זו,
ואנחנו קוראים בפונקציה כמו ראשי, וראשיים יש 2 משתנה מקומי, X ו-Y,
בואו נתאר אותם כx כאן, ובואו נתאר אותם כy כאן,
ובואו נשים את ערכי 1 ו 2, אז זה כאן הוא ראשי,
וכשקורא עיקריים של מערכת הפעלת פונקצית ההחלפה
נותן פונקצית החלפת רצועה של זיכרון משלו במחסנית,
המסגרת שלו בערימה, אם אפשר לומר כך.
זה גם מקצה 32 ביטים לints אלה.
זה קורה לקורא להם וb, אבל זה שרירותי לחלוטין.
זה היה יכול להיות כינה אותם מה שהיא רוצה, אבל מה קורה כאשר עיקרית
החלפת שיחות היא זה שלוקח 1, מעביר עותק שם, מעמיד את עותק לשם.
>> יש משתנה מקומי אחר 1 בהחלפה, הנקראת במה? Tmp. >>
Tmp, אז בוא אתן לעצמי עוד 32 סיבי כאן,
ומה שעשיתי בפונקציה זו?
אמרתי tmp int מקבל, ולכן יש 1, אז עשיתי את זה עוד כששחקנו בפעם האחרונה בדוגמה זו.
ואז מקבל ב, ולכן b הוא 2, אז עכשיו זה הופך להיות 2,
ועכשיו ב מקבל זמנית, ולכן טמפ 'הוא 1,
אז עכשיו ב הופך לזה.
זה נהדר. זה עבד.
אבל אז ברגע שיחזור לתפקד
הזיכרון של החלפת יעילות נעלם כך שניתן לעשות שימוש חוזר
על ידי כמה תפקיד אחר בעתיד, ועיקרי הוא ברור ומוחלט ללא שינוי.
אנחנו זקוקים לדרך לפתרון בעיה זו המיסוד,
והיום אנחנו סוף סוף יש דרך לעשות את זה לפי
אנו יכולים להציג משהו שנקרא מצביע.
מתבררים שאנחנו יכולים לפתור את הבעיה הזו
לא על ידי העברה בעותקים של x ו-y
אלא על ידי העברה במה, לדעתך, לפונקצית ההחלפה?
כן, מה עם הכתובת?
אנחנו לא ממש דברנו על כתובות בפירוט רב,
אבל אם לוח זה מייצג את הזיכרון של המחשב שלי
אנחנו בהחלט יכולים להתחיל את מספור הבתים בזכרון RAM שלי
ואומר זה בית המס '1, זה בית המס' 2, בית המס '3,
בית המס '4, בייט # ... 2 מיליארדים אם יש לי 2 ג'יגה בייט של זכרון RAM,
כך שאנחנו בהחלט יכולים לבוא עם איזו תכנית מספור שרירותית
לכל הבתים הבודדים בזיכרון של המחשב שלי.
>> מה אם במקום כשאני מתקשר להחלפה
במקום לעבור בעותקים של x ו-y
למה שאני לא אעבור במקום בכתובת של x כאן,
הכתובת של Y כאן, בעצם הכתובת למשלוח דואר
של x ו-y כי אז להחליף, אם הוא הודיע
של הכתובת בזיכרון של X ו-Y,
אז להחליף, אם היינו מאמנים אותו קצת,
הוא עלול לנהוג לכתובת זו, אם אפשר לומר כך,
x, ולשנות את המספר לשם, ואז לנסוע לכתובת של Y,
לשנות את המספר שם, אפילו שגם אם לא מקבל עותקים של הערכים האלה בעצמו,
אז למרות שדברנו על זה כזיכרון של עיקרי
וזיכרון כשל עסקה זו החזק והחלק המסוכן של C
הוא שכל פונקציה יכולה לגעת בכל מקום בזכרון המחשב,
וזו היא עצמה שבאתה יכול לעשות דברים מאוד מפוארים עם תוכניות מחשב בג
זה מסוכן, כי אתה יכול גם לפשל בקלות רבה.
למעשה, אחת הדרכים הנפוצות ביותר לתוכניות בימים אלה ניתן לנצל
עדיין היא למתכנת שלא מבינה
שהוא או היא המאפשר לנתונים
להיות כתוב במיקום בזיכרון שלא נועד.
>> למשל, הוא או היא מצהיר על מערך בגודל 10
אבל אז מנסה בטעות לשים 11 בתים שבמערך של זיכרון,
ואתה מתחיל לגעת בחלקים של זיכרון שאינם תקפים עוד.
בדיוק לזה קשר, שחלקכם אולי יודע ש
תוכנה תבקש ממך לעתים קרובות למספרים סידוריים או מפתחות רישום,
ו-Word פוטושופ ותוכניות מהסוג הזה.
קיימים סדקים, כפי שחלקכם יודע, באופן מקוון שבו תוכל להפעיל תכנית קטנה,
וזהו, לא יותר בקשה למספר סידורי.
איך זה עובד?
במקרים רבים את הדברים האלה פשוט מוצאים במחשבים
קטעי טקסט באפסים והאחדים בפועל של המחשב
איפה היא פונקציה שבו המספר הסידורי מתבקש,
ואתה לדרוס חלל, או בזמן שהתכנית פועלת
אתה יכול להבין היכן המפתח מאוחסן בפועל
באמצעות משהו שנקרא הבאגים, ואתה יכול לפצח שדרך תוכנה.
זה לא אומר שזה המטרה שלנו לימים הקרובים,
אבל יש לו השלכות מאוד בעולם אמיתי.
כי אחד קורה לערב גניבה של תוכנה,
אבל יש גם פשרה של מכונות שלמות.
>> למעשה, כאשר אתרי אינטרנט בימים אלה מנוצלים
והתפשרתי ונתונים דלפו וסיסמות נגנבו
לעתים קרובות זה קשור לניהול גרוע של הזיכרון שלו,
או, במקרה של מסדי נתונים, כישלון לחזות
קלט יריב, אז עוד על כך בשבועות הקרובים,
אך לעת עתה רק הצגה מקדימה של הסוג של ניזק שאתה יכול לעשות
בכך שלא הבנתי כיצד דברים עובדים מתחת למכסת המנוע.
בואו נלך על הבנה מדוע זה נשבר
עם כלי שהפך יותר ויותר שימושיים
כתוכניות שלנו נעשה יותר מורכבות.
עד כה, כאשר היה לך באג בתכנית שלך
איך יש לך הלך על ניפויו?
מה הטכניקות שלך היו עד כה, אם נלמדו על ידי TF
או סתם אוטודידקט?
[סטודנטים] printf.
Printf, אז printf יש כנראה היה החבר שלך בכך שאם אתה רוצה לראות
מה קורה בתוך התכנית שלך
אתה פשוט לשים printf כאן, printf כאן, printf כאן.
ואז אתה מפעיל את זה, ואתה מקבל כל מיני דברים על המסך
כי אתה יכול להשתמש ואז להסיק מה בעצם השתבש בתכנית שלך.
>> Printf נוטה להיות דבר חזק מאוד,
אבל זה תהליך מאוד ידני.
אתה צריך לשים את printf כאן, printf כאן,
ואם תשים אותו בתוך לולאה אתה יכול לקבל 100 קווים
תפוקה, כי אז אתה צריך לנפות.
זה לא מנגנון ידידותי למשתמש או אינטרקטיווי מאוד לתוכניות איתור באגים,
אבל לשמחתי קיים חלופות.
יש תכנית, למשל, נקראת GDB, גנה Debugger,
שהוא מסתורי קטן בכמה אתה משתמש בו.
זה מורכב קצת, אבל בכנות,
זה אחד מאותם דברים שבו אם אתה שם בשבוע הבא ו
שעה נוספת כדי להבין משהו כמו GDB
זה יחסוך לכם כנראה עשרות שעות בטווח הארוך,
אז עם זה, ייתן לך טיזר של איך הדבר הזה עובד.
>> אני בחלון המסוף שלי.
תן לי ללכת קדימה ולקמפל תכנית זו, buggy3.
זה כבר מעודכן.
תן לי לנהל את זה בדיוק כמו שעשינו חזרה בזמן, ואכן, הוא שבור.
אבל למה זה? אולי אני דפוק פונקצית הדפדוף.
אולי זה ב. אני לא ממש אני נע סביבם בצורה נכונה.
תן לי ללכת קדימה ולעשות את זה.
ולא רק לרוץ buggy3 תן לי במקום לרוץ GDB תכנית זו,
ואני הולך להגיד לו לרוץ buggy3,
ואני מתכוון לכלול טיעון שורת פקודה,-Tui,
ואנחנו נשים את זה בבעיות עתידיות במפרט כדי להזכיר.
ועכשיו ממשק שחור ולבן זה צץ כי, שוב,
הוא קצת מוחץ בהתחלה, כי יש את כל זה
מידע על אחריות לכאן, אבל לפחות יש משהו מוכר.
בחלק העליון של החלון הוא הקוד האמיתי שלי,
ואם אני לגלול עד כאן נתתי לי לגלול לחלקו עליון של התיק שלי,
ואכן, יש buggy3.c, והודעה בחלק התחתון של חלון זה
יש לי GDB הנחיה זו.
>> זה לא אותו הדבר כמו ג'ון הרווארד הפקודה הרגילה שלי.
זו פקודה שהולכת כדי לאפשר לי לשלוט GDB.
GDB הוא הבאגים.
הבאגים הוא תכנית המאפשרת לך ללכת דרך
ביצוע התכנית שלך על ידי שורת שורה אחרת שורה,
לאורך הדרך לעשות מה שאתה רוצה בתכנית,
אפילו קוראים פונקציות, או מחפש, וחשוב יותר,
בערכים של משתנים שונים.
בואו נלך קדימה ולעשות את זה.
אני הולך קדימה, והקלד בשורת הפקודה בטווח של GDB,
כך תבחין בפינה השמאלית התחתונה של מסך הקלדה שבצעתי,
ואני פגעתי להיכנס, ומה זה עשה?
זה ממש רץ את התכנית שלי, אבל בעצם לא רואה הרבה בארץ הזאת
כי אני לא ממש אמרתי לי הבאגים
להפסקתו ברגע נתון בזמן.
פשוט להקליד ריצה מפעילה את התכנית.
אני לא ממש רואה שום דבר. אני לא יכול לטפל בו.
>> במקום לתת לי לעשות את זה.
בGDB הפקודה הזאת נתנה לי במקום להקליד הפסקה, להיכנס.
זה לא מה שהתכוונתי להקליד.
בואו במקום להקליד הפסקה ראשית.
במילים אחרות, אני רוצה להגדיר משהו שנקרא נקודת עצירה,
אשר נקרא על שם צדק, כי זה ישבור או שהייה
ביצוע התכנית שלך באותו מקום מסוים.
העיקרי הוא השם של הפונקציה שלי.
שים לב שGDB הוא די חכם.
זה הבין שקורה עיקרי להתחיל בערך בקו 18
של buggy3.c, ואז מבחין כאן בפינה שמאלית עליונה
ב + הוא ממש ליד קו 18.
זה מזכיר לי שאני צריך להגדיר נקודת עצירה בקו 18.
הפעם, כשאני מקליד ריצה, אני הולך להפעיל את התכנית שלי
עד שזה מכה נקודת עצירה,
לכן התכנית תושהה לי בקו 18.
הנה, לרוץ.
שום דבר לא נראה שקרה, אבל הודעה בפינה שמאלית תחתונה
תכנית מתחילה, buggy3, נקודת עצירה 1 בקו ראשי בbuggy3.c 18.
מה אני יכול לעשות עכשיו?
>> שים לב שאני יכול להתחיל להקליד דברים כמו הדפסה,
לא printf, x הדפסה, וזה הדבר מוזר.
1 $ הם רק סקרנות, כפי שנראים
בכל פעם שאתה מדפיס משהו שאתה מקבל ערך חדש $.
זה כדי שתוכל לחזור ולעיין בערכים קודמים לכל מקרה,
אך לעת עתה מה הדפסה אומרת לי הוא שהערך של x בנקודה זו בסיפור
כנראה 134514032.
מה? איפה עוד זה בא?
[לא ברור לתלמיד]
ואכן, זה מה שאנחנו קוראים ערך אשפה, ואנחנו כבר לא מדברים על זה עדיין,
אבל הסיבה שמאותחל משתנים
ברור, כך שיש להם איזה ערך שאתה רוצה לתת להם.
אבל לתפוס אותו לזכור שאתה יכול להצהיר על משתנה
כמו שעשיתי לפני רגע בדוגמא סיגמא
מבלי לתת להם ממש ערך.
זוכר את מה שעשיתי כאן בסיגמא.
אני הכרזתי n, אבל מה ערך שאני נותן לו?
אף אחד, משום שידעתי כי בשורות הבאות
GetInt ידאג לבעיה של לשים את הערך הפנימי של n.
>> אבל בנקודה זו בסיפורו של קו 11
וקו 12 וקו 13 וקו 14
לאורך כמה השורות האלה הוא מה הערך של n?
ב C אתה פשוט לא יודע.
זה בדרך כלל ערך כלשהו אשפה, חלק המספר אקראי לחלוטין
מה שנשאר על מהותו מתפקיד כלשהו קודם
לאחר שהופעל, כך שהתכנית שלך פועלת
זוכר שפונקציה מקבלת פונקציה, פונקציה, פונקציה.
כל מסגרות אלה לקבל לשים על זיכרון, ואז מי שהחזרת פונקציות,
ובדיוק כמו שהצעתי עם מחק זכרם נעשה שימוש חוזר בסופו של דבר.
ובכן, זה פשוט כל כך קורה כי x משתנה זה בתכנית זו
נראה שהכיל כמה ערך זבל כמו 134514032
מכמה פונקציה קודמת, לא אחד שאני כתבתי.
זה יכול להיות משהו שמגיע בצורה יעילה עם מערכת ההפעלה,
כמה פונקציה מתחת למכסת המנוע.
>> אוקיי, זה בסדר, אבל בואו עכשיו להתקדם לשורה הבאה.
אם אני מקליד "בא" בGDB המהיר ואני מכה להיכנס,
שם לב שהדגשת מהלכים עד לקו 19,
אבל המשמעות הלוגית היא שקו 18
עכשיו סיים הרצה, כך שאם אני שוב להקליד "הדפסת x"
אני צריך עכשיו לראות 1, ואכן, אני עושה.
שוב, דברי $ הם דרך GDB מזכיר לך
מה ההיסטוריה של הדפסים שעשיתם.
עכשיו תן לי ללכת קדימה ולהדפיס את y, ואכן, y הוא ערך כלשהו מטורף, כמו גם,
אבל לא עניין גדול, כי בקו 19 שאנחנו עומדים להקצות את
הערך 2, אז תן לי להקליד "הבא" שוב.
ועכשיו אנחנו בקו printf.
תן לי לעשות x הדפסה.
תן לי לעשות y הדפסה. בכנות, אני מקבל קצת עייף של הדפסה זו.
תן לי במקום להקליד "x התצוגה" ו" התצוגה y "
ועכשיו בכל פעם שאני מקליד פקודה בעתיד
אני להיזכר מה X ו-Y, מה X ו-Y, מה x ו-y.
>> אני יכול גם, כדרך אגב, בסוג "המקומיים מידע".
מידע הוא פקודה מיוחדת.
המקומיים אומרים שזה מראה לי את המשתנים המקומיים.
רק למקרה שאשכח או זו היא פונקציה מטורפת, מסובכת
שאני או מישהו אחר כתבתי המקומיים מידע יגידו לך
מה ערך של כל המשתנים המקומיים בתוך פונקציה מקומית זה
שאולי אכפת לך אם תרצה לחטט.
עכשיו, printf עומד לבצע, אז תן לי ללכת קדימה ופשוט להקליד "הבא".
מכיוון שאנו נמצאים בסביבה זו שאנחנו לא באמת רואים אותו
ביצוע כאן למטה, אבל שם לב לזה נהיה קצת מעווה כאן.
אבל שם לב שזה מבטל את המסך שם,
אז זה לא תכנית מושלמת כאן, אבל זה בסדר, כי אני תמיד יכול לחטט
שימוש בהדפסה אם אני רוצה.
>> תן לי להקליד הבא שוב, ועכשיו הנה חלק המעניין.
בנקודה זו בסיפור y הוא 2, ו-x הוא 1,
כפי שהוצע כאן, ושוב,
מהסיבה זו באופן אוטומטי מציגה כרגע היא בגלל שהשתמשתי בפקודה
התצוגה x ו-y תצוגה, וברגע שאני מהסוג הבא
בתאורית x ו-y צריך להיות מוחלף.
עכשיו, אנחנו כבר יודעים שלא הולכים להיות המקרה,
אבל נראה ברגע איך אנחנו יכולים לצלול עמוק יותר כדי להבין למה זה נכון.
בשלב בא, ולמרבה הצער, y הוא עדיין 2 ו x הוא עדיין 1, ואני יכול לאשר כל כך הרבה.
ההדפסה x, y הדפסה.
אכן, אין החלפה שכבר קרה, אז בואו נתחיל עם זה שוב.
ברור שהחלפה היא שבורה.
בואו במקום להקליד "לרוץ" שוב.
הרשה לי לומר, כן, אני רוצה להפעיל מחדש את זה מההתחלה, זן.
>> עכשיו אני חוזר אל קו 18.
עכשיו שם לב x ו-y הם ערכי אשפה שוב.
בשלב בא, הבא, הבא, הבא.
אם אני משתעמם אני יכול גם פשוט להקליד n לבא.
אתה יכול לקצר אותו לרצף הקצר ביותר האפשרי של תווים.
דפדוף עכשיו נשבר.
בואו לצלול ב, אז במקום להקליד הבא,
עכשיו אני הולך להקליד צעד, כך שאני דורך בתוך פונקציה זו
כך שאני יכול לעבור אותו, ולכן אני מכה צעד ואז להיכנס.
שים לב שקפיצות ההדגשה למטה נמוכות בתכנית שלי לקו 36.
עכשיו, מה הם את המשתנים המקומיים?
המקומיים מידע.
שום דבר לא פשוט כי אנחנו עדיין לא יצאנו לי לאותו קו,
אז בואו נלך קדימה ואומרים "הבא".
עכשיו אנחנו נראים לי tmp, tmp הדפסה.
ערך זבל, נכון? אני חושב שכן.
מה דעתך על להדפיס, הדפסה ב, 1 ו 2?
ברגע, ברגע שאני מקליד הבא שוב
tmp הולך לקחת על ערך של 1, בתקווה,
בגלל tmp הולך להיות מוקצה הערך.
>> עכשיו בואו ניתן להדפיס, ב הדפסה,
אבל עכשיו להדפיס tmp, וזה אכן 1.
תן לי לעשות לי בא. תן לי לעשות לי בא.
אני כבר סיימתי את פונקצית ההחלפה.
אני עדיין בתוכו בקו 40, אז תן לי להדפיס,
הדפסה ב, ולא אכפת לי מה הוא tmp.
זה נראה כמו ההחלפה היא נכונה, כאשר הוא מגיע להחלפה וכן ב.
אבל אם אני עכשיו אקליד בא, אני קופץ חזרה לקו 25,
וכמובן, אם אני מקליד בx ו-y הדפסה
הם עדיין לא השתנו, ולכן אנחנו לא תקנו את הבעיה.
אבל diagnostically עכשיו אולי עם תכנית GDB זה
לפחות לי שהבנו צעד אחד קרוב יותר להבנה
מה השתבש מבלי ללכלך את הקוד שלנו על ידי הצבת printf כאן,
printf כאן, printf כאן ולאחר מכן מפעיל אותו שוב ושוב
מנסה להבין מה השתבש.
>> אני הולך קדימה ולפרוש מזה לגמרי עם לפרוש.
זה הולך אז אמר, "לצאת בכל זאת?" כן.
עכשיו אני שוב בהנחיה הרגילה שלי, ואני עושה שימוש GDB.
כהערת אגב, אתה לא צריך להשתמש בדגל-Tui זה.
למעשה, אם אתה משמיט אותו אתה מקבל בעצם את החצי התחתון של המסך.
אם לאחר מכן הקלד הפסקה ראשית ולאחר מכן להפעיל
אני עדיין יכול להפעיל את התכנית שלי, אבל מה זה יעשה יותר טקסטואלית
רק תראה לי 1 הקו הנוכחי בכל פעם.
-Tui, ממשק המשתמש טקסטואלי,
רק מראה לך יותר מפעם אחת בתכנית, שהוא כנראה קצת יותר קל מושגית.
אבל אכן, אני יכול פשוט לעשות בא, בא, בא,
ואני הולך לראות שורה אחת בכל פעם, ואם אני באמת רוצה לראות מה קורה
אני יכול להקליד רשימה ולראות חבורה שלמה של קווים שכנים.
>> יש וידאו שאנחנו כבר בקשנו שאתה צופה לבעיה קובעת 3
שבה תאט מכסה חלק מהמורכבויות של GDB,
וזה אחד מהדברים האלה, בכנות, שבו אחוז מסוים שאינם טריוויאלי שלך
לעולם לא לגעת GDB, וזה יהיה דבר רע
כי ממש אתה תהיה בסופו של דבר לבלות יותר זמן בהמשך הסמסטר
רודף אחרי חרקים אז היית אם לשים שבחצי שעה / השעה
השבוע והלמידה הבאה כדי לקבל נוח עם GDB.
Printf היה החבר שלך.
GDB צריך עכשיו להיות החבר שלך.
>> כל שאלות על GDB?
והנה רשימה מהירה של חלק מהפקודות השימושיות והחזקות ביותר.
כן. >> האם אתם יכולים להדפיס מחרוזת?
אתה יכול להדפיס את מחרוזת? בהחלט כן.
זה לא חייב להיות רק מספרים שלמים.
אם זה משתנה הוא מחרוזת רק בסוג של הדפסה.
זה ייראה לך מה שמשתנה הוא המחרוזת.
[לא ברור לתלמיד]
זה ייתן לך את הכתובת ואת המחרוזת עוצמה.
זה ייראה גם לך.
ודבר אחד אחרון, פשוט כי אלה טובים לדעת יותר מדי.
Backtrace ומסגרת, בואו לצלול אליי פעם אחת האחרונה,
אותה תכנית מדויקת עם GDB.
תן לי ללכת קדימה ולהפעיל את גרסת ממשק משתמש טקסטואלי,
לשבור ראשי.
תן לי ללכת קדימה ולרוץ שוב. הנה אני.
עכשיו בואו נלך הבא, בא, בא, בא, הבא לי, צעד, להיכנס.
>> ועכשיו יניחו שאני עכשיו בהחלפה במתכוון, אבל אני כמו "לעזאזל, מה היה הערך של x?"
אני לא יכול לעשות x יותר.
אני לא יכול לעשות y בגלל שהם לא בהיקפו.
הם לא בהקשר, אבל אין שום בעיה.
אני יכול להקליד backtrace.
זה מראה לי את כל הפונקציות שבוצעו עד לנקודה זו בזמן.
שים לב ש1 בתחתית, הראשי, שורות עם ראשי
להיות בחלק התחתון של התמונה שלנו כאן.
העובדה שהחלפה היא מעליו קווים עם החלפה להיות מעליו בזיכרון כאן,
ואם אני רוצה לחזור לעיקר זמני אני יכול לומר "מסגרת".
מה מספר? העיקרי הוא מסגרת # 1.
אני הולך קדימה, ואומר "מסגרת 1."
>> עכשיו אני שוב בראשי, ואני יכול להדפיס את x, ואני יכול להדפיס y,
אבל אני לא יכול להדפיס או ב.
אבל אני יכול, אם אני אומר, "בסדר, חכה רגע. איפה הייתה ההחלפה?"
תן לי ללכת קדימה ולומר "0 מסגרת."
עכשיו אני חוזר לשם אני רוצה להיות, וכמו בצד,
יש פקודות אחרות, כמו אם אתה באמת מקבל הקלדה הבאה, הבאה, הבאה, הבאה משועממת,
אתה בדרך כלל יכול להגיד דברים כמו "10 הבאים", וכי יהיה צעד דרך 10 השורות הבאות.
אתה יכול גם לכתוב "המשך" כאשר אתה באמת תימאס דריכה דרכו.
המשך יהיה להפעיל את התכנית ללא הפרעה עד שהוא פוגע נקודת עצירה נוספת,
אם בלולאה או למטה בתכנית שלך.
>> במקרה זה המשכנו עד הסוף, והתכנית יצאה כרגיל.
זו היא דרך מפוארת, תהליך נחות.
רק התכנית שלך יצאה באופן נורמלי.
עוד על כך בוידאו ובניפוי שגיאות מפגשים הבאים.
זה היה הרבה.
בואו ניקח ההפסקה שלנו 5-הדקה פה, ונחזור עם structs וקבצים.
>> אם יש לך צלל לתוך pset השבוע כבר
אתה יודע שאנחנו משתמשים בקוד ההפצה,
את קוד המקור שאנו מספקים לך כנקודת פתיחה, כמה טכניקות חדשות.
בפרט, אנו הצגנו המילה החדשה הזה שנקרא struct, למבנה,
כדי שנוכל ליצור משתנים מותאמים אישית של מינים.
אנחנו גם הצגנו את הרעיון של קובץ קלט / פלט, ופלט לקובץ,
וזה, כדי שנוכל להציל את המדינה
הלוח של המירוץ שלך לקובץ בדיסק
כך שעמיתי ההוראה ואני יכולים להבין
מה קורה בתוך התכנית שלך באופן ידני מבלי לשחק
עשרות משחקים של מירוץ.
אנחנו יכולים לעשות את זה יותר automatedly.
>> רעיון זה של struct פותר בעיה די משכנעת.
תניח שאנחנו רוצים ליישם חלק התכנית
שאיכשהו עוקב אחר מידע על סטודנטים,
ותלמידים יכולים להיות, למשל, תעודת זהות, שם
ובית במקום כמו הרווארד, ולכן אלה הם 3 חתיכות של מידע
אנחנו רוצים לשמור על הסביבה, אז תן לי ללכת קדימה ולהתחיל לכתוב תכנית קטנה כאן,
כולל stdio.h.
תן לי לעשות כולל cs50.h.
ואז תתחיל הפונקציה העיקרית שלי.
אני לא אטרח עם כל הארגומנטים בשורת פקודה,
וכאן אני רוצה להיות תלמיד, אז אני הולך להגיד
סטודנט יש לו שם, אז אני הולך לומר "שם מחרוזת".
ואז אני הולך לומר תלמיד יש גם זהות, זהות כך int,
ותלמיד יש לו בית, אז אני גם הולך לומר "בית מחרוזת".
אז אני הזמנתי את אלה קצת יותר נקיים כזה.
אוקיי, עכשיו יש לי 3 משתנה עם אשר מייצגים תלמיד, ולכן "תלמיד".
>> ועכשיו אני רוצה לאכלס את הערכים הללו, אז תנו לי ללכת קדימה ואומרים משהו כמו:
"Id = 123".
שם הוא הולך לקבל דוד.
בואו נגיד שבית הוא הולך לקבל מאת'ר,
ואז אני הולך לעשות משהו שרירותי כמו printf ("% s,
זהותו היא% d, מתגוררת ב% s.
ועכשיו, מה אני רוצה לחבר כאן, אחד אחרי השני?
שם, שם, בית; תשואה 0.
אוקיי, אלא אם כן אני דפוק איפשהו כאן
אני חושב שיש לנו תכנית די טובה שמאחסנת תלמיד אחד.
כמובן, זה לא כל כך מעניין. מה אם אני רוצה יש לי 2 תלמידים?
זה לא עניין גדול. אני יכול לתמוך 2 אנשים.
תן לי ללכת קדימה ולהבליט זאת ולרדת לכאן,
ואני יכול לומר "id ​​= 456" למישהו כמו רוב המתגורר בקירקלנד.
>> אוקיי, תחכה, אבל אני לא יכול לקרוא להם את אותו הדבר,
וזה נראה כאילו אני הולך צריך להעתיק את זה,
אז הרשה לי לומר כי אלה יהיו המשתנים של הדוד,
ותן לי כמה עותקים של אלה לרוב.
אנחנו קוראים לאלה של רוב אבל זה לא הולך עכשיו לעבודה
כי יש לי לחכות, בואו תחליפו אותי לID1, name1 וhouse1.
רוב יהיו 2, 2.
אני חייב לשנות את זה כאן, כאן, כאן, כאן, כאן, כאן.
חכה, מה עם טומי? בואו נעשה זאת שוב.
ברור שאם אתה עדיין חושב שזו דרך טובה ביותר לעשות זאת, זה לא,
כך העתק / דבק רע.
אבל פתר את זה לפני שבוע.
>> מה היה הפתרון שלנו כאשר אנו רוצים להיות מספר מופעים של אותו סוג הנתונים?
[סטודנטים] מערך.
מערך, אז תן לי לנסות לנקות את זה.
תן לי לעשות קצת מקום לעצמי בראש, ותן לי במקום לעשות את זה כאן.
אנחנו קוראים לאנשים האלה, ובמקום זאת אני הולך לומר "מזהי int",
ואני מתכוון לתמיכה 3 מאתנו לעת עתה.
אני הולך לומר "שמות מייתרים," ואני אתמוך בי 3 מאתנו,
ואז אני הולך לומר "בתי מייתר," ואני הולך לתמוך 3 מאתנו.
עכשיו בפה, במקום דוד מקבל המשתנים המקומיים שלו
אנחנו יכולים להיפטר מאלה.
זה מרגיש טוב שאנחנו מנקים את זה.
אז אני יכול להגיד הדוד הולך להיות [0] ושמות [0]
ובתים [0].
ולאחר מכן לשדוד אנחנו דומים יכולים לשמור על זה.
בואו נשים את זה כאן למטה, כך שהוא הולך באופן שרירותי להיות מזהים [1].
הוא הולך להיות שמות [1],
ואז לבסוף, בתים [1].
>> עדיין קצת משעמם, ועכשיו אני צריך להבין את זה,
אז בואו נאמרתי "שמות [0], שם [0], בתים [0],
ובואו pluralize זה.
מזהה, תארים, תעודות.
ושוב, אני עושה את זה, אז שוב, אני כבר להזדקק העתק / דבק שוב,
אז רוב הסיכויים הם שיש פתרון אחר כאן.
אני כנראה יכול לנקות את זה עוד יותר עם לולאה או משהו כזה,
כך שבקיצור, זה קצת יותר טוב אבל עדיין מרגיש כמו
אני להזדקק העתק / דבק, אבל גם זה, אני טוען,
הוא לא באמת ביסוד הפתרון הנכון משום
מה אם מתישהו נחליט אתם יודעים מה?
אנחנו באמת צריכים לאחסון כתובות דוא"ל לדוד ורוב
וכל אחד אחר בתכנית זו.
אנחנו צריכים גם לאחסן מספרי טלפון.
אנחנו צריכים גם לאחסן מספרי קשר לשעת חירום.
יש לנו את כל החלקים הללו של נתונים שאנו רוצים לאחסן,
אז איך אתה הולך לעשות את זה?
>> אתה מצהיר מערך אחר בראש, ואז אתה להוסיף באופן ידני
כתובת הדוא"ל [0] כתובת, דואר אלקטרוני [1]
לדוד ורוב וכן הלאה.
אבל יש באמת רק הנחה העומדת בבסיס עיצוב זה
כי אני משתמש במערכת הכבוד לדעת כי
[I] בכל אחת מכמה מערכים
פשוט כל כך קורה למתייחס לאותו האדם,
כך [0] בזיהוי הוא המספר 123,
ואני הולך להניח ששמות [0]
השם והבתים [0] של אותו האדם
הוא ביתו של אותו האדם וכן הלאה לכל מערכים השונים שאני יוצר.
אבל שם לב שאין הצמדה בסיסית
בין 3 החלקים האלה של מידע, זיהוי, שם והבית,
למרות שהישות שאנחנו מנסים מודל בתכנית זו היא לא מערכים.
מערכים הם רק דרך תכנותית זה לעשות את זה.
מה שאנחנו באמת רוצים לבנות מודל בתכנית שלנו הוא אדם
כמו דוד, אדם כמו רוב בתוכה
או encapsulating הוא שם ותעודת זהות ובית.
>> יכולים איכשהו אנו מביעים את הרעיון הזה של אנקפסולציה
לפי אדם יש זהות, שם ובית
ולא לנקוט באמת זה גרזן בו אנו פשוט
לסמוך על כך שמשהו הסוגר
מתייחס לאותה הישות אנושית בכל אחד ממערכים השונים אלה?
אנחנו באמת יכולים לעשות את זה.
תן לי ללכת מעל עיקרי לעכשיו, ותנו לי ליצור סוג הנתונים שלי
לבאמת בפעם הראשונה.
אנחנו השתמשנו בשיטה הזאת במירוץ,
אבל כאן אני הולך קדימה וליצור סוג נתונים,
ואתה יודע מה, אני הולך לקרוא לו תלמיד, או אדם,
ואני מתכוון להשתמש לtypedef מגדיר סוג.
אני הולך להגיד שזה מבנה,
ולאחר מכן במבנה הזה הולך להיות של תלמיד סוג, אנחנו נגיד,
למרות שזה קצת יצא עכשיו בשבילי.
אנחנו נגיד "int id".
אנחנו נגיד "שם מחרוזת".
אז אנחנו אומרים "בית מחרוזת"
אז עכשיו עד הסוף כמה השורות האלה של קוד
יש לי רק למדתי את הצלצול כי קיים
סוג נתונים מלבד ints, מלבד מייתרים, מלבד מכפיל, מלבד צף.
>> נכון לרגע זה בקו 11 פעם, יש עכשיו סוג נתונים חדש בשם תלמידים,
ועכשיו אני יכול להצהיר על משתנה תלמיד בכל מקום שאני רוצה,
אז תן לי לגלול למטה כאן לאנשים.
עכשיו אני יכול להיפטר מזה, ואני יכול לרדת בחזרה לדוד כאן,
ודוד אני יכול באמת להגיד שדוד,
אנחנו ממש יכולים שם משתנים אחרי עצמי,
הולך להיות תלמיד של סוג.
זה אולי נראה קצת מוזר, אבל זה לא כל כך שונה
מלהכריז משהו כמו int או מחרוזת או לצוף.
זה פשוט כל כך קורה להיקרא תלמיד עכשיו,
ואם אני רוצה לשים משהו בתוך מבנה זה
עכשיו יש לי להשתמש ביצירה חדשה של תחביר, אבל זה די פשוט,
david.id = 123, david.name = "דוד" בבירת D,
וdavid.house = "ר",
ועכשיו אני יכול להיפטר מהחומר הזה כאן.
שים לב יש לנו עכשיו מחדש בתכנית שלנו באמת דרך הרבה יותר טוב
בתכנית שלנו שעכשיו משקפת את העולם האמיתי.
>> יש מושג בעולם האמיתי של אדם או תלמיד.
כאן יש לנו עכשיו גרסת C של אדם או לייתר דיוק תלמיד.
בתוכו של אותו האדם הם מאפיינים רלוונטיים אלה,
זהות, שם ובית, ולכן רוב למעשה הופך את אותו הדבר כאן למטה,
כך התלמיד לשדוד, ועכשיו rob.id = 456,
rob.name = "רוב".
העובדה שהמשתנה נקראת רוב היא סוג של משמעות.
אנחנו יכולים לקרוא לה X או Y או Z.
אנחנו רק בשמו לשדוד להיות עקבי מבחינה סמנטית,
אבל באמת שם נמצא שמהשדה עצמו,
אז עכשיו יש לי את זה.
זה גם לא מרגיש כמו העיצוב הטוב ביותר, כי אני כבר בקוד קשה דוד.
אני קוד קשה רוב.
ואני עדיין צריך לפנות אל עותק מסוים ולהדביק בכל פעם שאני רוצה משתנים חדשים.
יתר על כן, יש לי כנראה כדי לתת לכל אחד מהמשתנים הללו שם,
למרות שהייתי מעדיף שאתאר המשתנים הללו
יותר הגנרי תלמידים.
>> עכשיו אנחנו יכולים למזג את הרעיונות שכבר עובדים היטב עבורנו
ובמקום לומר: "אתה יודע מה, תן לי תלמידים שנקראו משתנים,
ובואו שזה יצטרך להיות בגודל 3 ", אז עכשיו אני יכול לחדד את זה עוד יותר,
להיפטר מהדוד הכריז באופן ידני,
ואני יכול לומר במקום משהו כמו תלמידים [0] כאן.
אז אני יכול לומר לתלמידים [0] כאן,
תלמידים [0] פה, וכן הלאה, ואני יכולים להסתובב
ולנקות את העסק הזה לרוב.
גם אני יכול ללכת עכשיו והוספתי לולאה אולי
ושימוש GetString וGetInt למעשה לקבל ערכים אלה מהמשתמש.
אני יכול ללכת על הוספה מתמדת בגלל זה הוא בדרך כלל נוהג רע
לקוד קשה קצת מספר שרירותי כמו 3 כאן
ואז רק תזכור שאתה צריך לשים לא יותר מ 3 תלמידים בו.
אני חושב שיהיה טוב יותר לשימוש # להגדיר בראש הקובץ שלי
וגורם שיצא, אז אכן, נתן לי ללכת קדימה ולהכליל זה.
>> בואו תפתחו לי דוגמה שבין היום
דוגמאות מראש, structs1.
זוהי תכנית שלמה יותר המשתמשת להגדיר עד כאן #
ואומר שאנחנו הולכים לנו 3 תלמידים כברירת מחדל.
הנה אני מכריז שווה בכיתה של תלמידים,
כך כיתת תלמידים, ועכשיו אני משתמש בלולאה
רק כדי להפוך את הקוד קצת יותר אלגנטי, לאכלס את הכיתה
עם כניסתו של המשתמש, כך לחזר מi = 0 בעד סטודנטים, שהוא 3.
ואז אני מנחה את המשתמש בגרסה זו
מה זהותו של התלמיד, ואני מקבל את זה עם GetInt.
מה שמו של התלמיד, ואז אני מקבל את זה עם GetString.
איך הבית של התלמיד? אני מקבל את זה עם GetString.
ואז בתחתית כאן אני פשוט החלטתי לשנות
איך אני מדפיס אותם ובעצם להשתמש בלולאה,
ושאני מדפיס?
על פי התגובה אני מדפיס מישהו במאת'ר,
וזהו זה כל כך רוב וטומי וכן הלאה, ולמעשה של טומי במאת'ר.
יהיו כתובים טומי ודוד במקרה הזה, אבל איך זה עובד?
אנחנו לא ראינו את הפונקציה הזו בעבר, אבל ניקח ניחוש על מה זה עושה.
משווה מחרוזות.
>> זה אינו מובן מאליו קצת איך זה בהשוואת מחרוזות כי מסתבר
אם היא מחזירה 0 זה אומר על המייתרים שווים.
אם הוא מחזיר -1 שמשמעותו אחת מגיעה אלפביתי לפני אחר,
ואם הוא חוזר 1 שפירוש המילה האחרת מגיע אלפביתי
לפני אחרים, ואתה יכול לחפש באינטרנט או בדף האדם
כדי לראות בדיוק הדרך שבה היא, אבל כל זה עכשיו עושה הוא זה אומר
אם [אני]. הבית שווה "ר"
אז קדימה להדפיס כך וכך הוא במאת'ר.
אבל הנה משהו שלא ראה לפני כן, ואנחנו נחזור לזה.
לא זכור לי שאצטרך לעשות את זה בכל אחת מהתוכניות שלי.
חינם כנראה מתייחס לזיכרון, לשחרר זיכרון,
אבל מה זיכרון אני כנראה לשחרר בלולאה זה בחלק התחתון של תכנית זו?
זה נראה כאילו אני משחרר את שמו של האדם
וביתו של אדם, אך מדוע זה כך?
>> מתברר כל השבועות האלה שאתה כבר משתמש בGetString
אנחנו כבר מציגים סוג של באג בכל אחת מהתוכניות שלך.
GetString ידי זיכרון מקצה עיצוב, כך שניתן לחזור אליך מחרוזת,
כמו דוד, או רוב, ואז אתה יכול לעשות מה שאתה רוצה
עם מחרוזת בתכנית שלך, כי יש לנו שמור בזיכרון בשבילך.
הבעיה היא כל הזמן הזה בכל פעם שאתה קורא GetString
אנחנו, כותבי GetString, היו מבקשים את מערכת ההפעלה
כדי לתת לנו קצת RAM עבור מחרוזת זו.
תן לנו קצת RAM עבור המחרוזת הבאה.
תן לנו קצת יותר זיכרון RAM למחרוזת הבאה.
מה אתה, המתכנת, מעולם לא הייתי עושה
נותן לנו שיחזור הזיכרון,
כך במשך כמה השבועות האלה את כל התוכניות שכתבת
יש לו את מה שנקרא קפיצת זיכרון לפיה הם ימשיכו להשתמש
יותר ויותר זיכרון בכל פעם שאתה קורא GetString, וזה בסדר גמור.
אנחנו בכוונה לעשות את זה בשבועות הראשונים, כי זה לא כל כך מעניין
צריך לדאוג היכן החוט שממנו מגיע.
כל מה שאתה רוצה הוא המילה Rob לחזור כאשר סוגיו פנימה המשתמש
>> אך אם אתקדם הלאה יש לנו עכשיו כדי להתחיל לקבל יותר מתוחכם בעניין הזה.
בכל פעם שאנו מקצים זכרוננו טוב יותר סופו של דבר למסור אותו בחזרה.
אחרת בעולם האמיתי ב-Mac או במחשב האישי שלך שאולי יש מדי פעם מנוסה
סימפטומים שבו המחשב שלך שנעצר לבסוף
או כדור החוף מסתובב הטיפשי פשוט כובש את המחשב של
כל תשומת לב, ואתה לא יכול לעשות דברים.
זה יכול להיות מוסבר על ידי כל מספר של חרקים, אבל בין אלה אפשריים באגים
הם דברים בשם דליפות זיכרון לפי מישהו שכתב את קטע זה של תוכנה
אתה משתמש לא זכרת לזיכרון פנוי
שהוא או היא שאל את מערכת הפעלה ב,
לא משתמש GetString, כי זה דבר CS50, אבל שימוש בפונקציות דומות
שישאלו את מערכת ההפעלה לזיכרון.
אם אתה או הם מפשל ולא ממש חוזרים זיכרון
סימפטום שיכול להיות שתכנית מאטה ומאטה ומאטה
אלא אם כן אתה לזכור לקרוא בחינם.
>> אנחנו נחזור אל מתי ולמה שאתם מכנים חופשיים,
אבל בואו נלך קדימה רק למען סדר טוב ונסה להפעיל תכנית מסוימת הזאת.
זה נקרא structs1, זן.
תנו לי ללכת קדימה ולהפעיל structs1, 123, הדוד מאת'ר,
456, רוב קירקלנד, 789,
טומי מאת'ר, ואנו רואים בדוד של מאת'ר, טומי של מאת'ר.
זה רק בדיקת שפיות קטנה שהתכנית פועלת.
עכשיו, למרבה הצער, תכנית זו היא קצת מתסכלת שב
אני לא כל העבודה, הקלדתי ב9 מחרוזות שונות, הקש על Enter,
נאמר לי שהייתה במאת'ר, אך ברור שידעתי שהיה במאת'ר כבר כי הקלדתי את זה.
זה יהיה נחמד אם לפחות תכנית זו היא יותר כמו מסד נתונים
וזה בעצם מה שאני זוכר שהקלדתי ב
אז אני לא אצטרך שוב קלט רישומי סטודנטים אלה.
אולי זה כמו מערכת registrarial.
>> אנו יכולים לעשות זאת באמצעות טכניקה זו ידועה כקובץ קלט / פלט, ופלט לקובץ,
דרך כללית מאוד להגיד את כל זמן שאתה רוצה לקרוא קבצים או לכתוב קבצים
אתה יכול לעשות את זה עם קבוצה מסוימת של פונקציות.
תן לי ללכת קדימה ולפתוח structs2.c דוגמה זו,
שהיא כמעט זהה, אבל בואנה נראית מה הוא עושה עכשיו.
בחלק העליון של הקובץ אני מצהיר בכיתה של תלמידים.
אז לאכלס את הכיתה עם הקלט של המשתמש,
כך קווים אלה של קוד הם בדיוק כמו בעבר.
אז אם אני לגלול למטה כאן אני מדפיס כל מי שנמצא במאת'ר שרירותי כמו בעבר,
אבל זו תכונה חדשה ומעניינת.
השורות אלה של קוד הן חדשות, והם מציגים כאן משהו,
כל הקובץ, הכובעים, ויש לה * בכאן גם כן.
תן לי להזיז את זה לכאן, * לכאן גם כן.
>> פונקציה זו שלא ראתה קודם, fopen,
אבל זה אומר שקובץ פתוח, אז בואו לרחף באמצעות אלה,
וזה משהו שאנחנו נחזור לpsets העתידי,
אבל הקו הזה כאן למעשה נפתח קובץ בשם מסד נתונים,
וזה דווקא פותח אותו בצורה כזו שהוא יכול לעשות מה זה?
[לא ברור לתלמיד]
בסדר, אז "w" רק אומר שזה אומר מערכת ההפעלה
לפתוח קובץ זה באופן כזה שאני יכול לכתוב את זה.
אני לא רוצה לקרוא אותו. אני לא רוצה רק להסתכל על זה.
אני רוצה לשנות אותו ולהוסיף דברים שעלולים להיות לזה,
ואת הקובץ הוא הולך להיות שם מסד נתונים.
זה יכול להיות משהו.
זה יכול להיות database.txt. זה יכול להיות. דציבלים.
זו יכולה להיות מילה כמו foo, אבל אני באופן שרירותי בחר לקרוא לנתוני קובץ.
זוהי בדיקת שפיות קטנה שנחזור לפירוט רב לאורך זמן,
אם fp, למצביע קובץ, לא שווה NULL זה אומר שמכיל בסדר.
>> סיפור ארוך קצר, פונקציות כמו fopen לפעמים נכשלות.
אולי הקובץ אינו קיים. אולי אתה מחוץ לשטח דיסק.
אולי אין לך הרשאה לתיקייה,
כך שאם fopen מחזיר משהו ריק קרה רע.
לעומת זאת, אם fopen לא יחזיר null הכל טוב
ואני יכול להתחיל לכתוב בקובץ זה.
הנה טריק חדש.
זה לולאה לזה iterating על כל אחד מהסטודנטים שלי,
וזה נראה כל כך דומה למה שעשינו בעבר,
אבל התפקיד הזה הוא בן דודו של בשם printf fprintf לקובץ printf,
ושים לב שזה שונה בדרכים רק 2.
אחד, זה מתחיל עם F במקום p,
אבל אז הטענה הראשונה שלה היא ככל הנראה מה?
[סטודנטים] קובץ. >> זה קובץ.
הדבר הזה שנקרא FP, שאנחנו בסופו להקניט מלבד מה מצביע קובץ,
אך לעת עתה fp פשוט מייצג את הקובץ שאני פתחתי,
כך fprintf כאן מדבר להדפיס תעודת הזהות של משתמש זה לקובץ, ולא על גבי המסך.
דפס שמו של המשתמש לקובץ, ולא על המסך,
הבית לקובץ, ולא על המסך, ולאחר מכן לכאן, כמובן,
לסגור את התיק, ולאחר מכן לכאן ללא זיכרון.
>> ההבדל היחיד בין גרסה זו 2 וגרסה 1
הוא המבוא של fopen וקובץ זה עם *
והרעיון הזה של fprintf, אז בואו לראות מה התוצאה הסופית היא.
תן לי ללכת לחלון המסוף שלי.
תן לי לרוץ structs2, זן.
נראה כאילו הכל טוב. בואו structs2 שידור חוזר.
123, הדוד מאת'ר, 456, רוב קירקלנד,
789, טומי מאת'ר, זן.
נראה כמו שהוא התנהג אותו הדבר, אבל אם אני עכשיו עושה ls
שים לב למה קובץ הוא כאן בין כל הקוד שלי, מסד נתונים,
אז בואו נפתח את זה, מבט gedit של מסד נתונים, ובאותו.
זה לא סקסי ביותר פורמטים של קבצים.
זה באמת חתיכה אחת של קו נתונים בכל שורה בכל שורה,
אבל אלה מכם שמשתמשים בקבצי Excel או CSV, ערכים מופרדים באמצעות פסיקים,
בהחלט הייתי יכול להיעזר בי fprintf במקום אולי לעשות משהו כזה
כך שאני יכול למעשה ליצור את המקבילה של קובץ Excel
על ידי הפרדת דברים עם פסיקים, לא רק קווים חדשים.
>> במקרה זה אם הייתי משתמש בפסיקים במקום קווים חדשים במקום
אני ממש יכול לפתוח קובץ מסד נתונים זה ב-Excel אם אני במקום גרמתי לזה להיראות ככה.
בקיצור, עכשיו שיש לנו את הכח לכתוב לקבצים
עכשיו אנחנו יכולים להתחיל נתונים מתמשכים, שמירה סביבו על דיסק
כדי שנוכל לשמור את המידע סביב שוב ושוב.
שים לב כמה דברים אחרים שהם עכשיו קצת יותר מוכרים.
בחלק העליון של קובץ C זה יש לנו typedef
מכיוון שרצינו ליצור סוג נתונים שמייצג מילה,
לכן סוג זה נקרא מילה, וחלק פנימי של מבנה זה
זה קצת להשתכלל עכשיו.
מדוע מילה מורכבת מככל הנראה מערך?
מה היא מילה רק באופן אינטואיטיבי?
>> זה מערך של תווים.
זה רצף של תווי גב אל גב אל גב.
האותיות גדולות קורות להיות שרירותי אומרים שהאורך המרבי
של כל מילה במילון שבו אנו משתמשים למירוץ.
למה אני צריך +1?
תו null.
זוכר אותו כשעשינו למשל Bananagrams אנו זקוקים ערך מיוחד
בסוף המילה כדי לעקוב אחר
משם מילים הסתיימו למעשה, וכפי שאומר מפרט סט הבעיה
כאן אנחנו מתחברים עם מילת נתונת ערך בוליאני,
דגל, כביכול, אמת או שקר.
האם מצא את המילה הזו כבר, כי אנחנו מבינים
אנחנו באמת צריכים דרך לזכור לא רק את מה שמילה הוא במירוץ
אבל אם אתה, אנושי, מצאת אותו
כך שאם אתה מוצא את המילה "" אתה לא יכול פשוט להקליד, זן,, זן,, זן
ומקבל 3 נקודות, 3 נקודות, 3 נקודות, 3 נקודות.
אנחנו רוצים להיות מסוגלים לרשימה שחורת מילה שעל ידי הגדרת bool
לאמיתי אם כבר מצאת אותו, ולכן זו הסיבה שאנו
מארז אותו במבנה זה.
>> עכשיו, כאן למטה במירוץ יש struct האחר זה נקרא מילון.
כאן הוא בהיעדר המילה typedef כי במקרה זה
אנחנו צריכים לתמצת את הרעיון של מילון,
ומילון מכיל חבורה שלמה של מילים,
כפי שמשתמע ממערך זה, וכמה מהדברים האלה שם?
ובכן, מה שנקרא גודל משתנה זה אומר.
אבל אנחנו רק צריכים מילון אחד.
אנחנו לא צריכים את טיפוס בשם מילון.
אנחנו פשוט צריכים אחד מהם, כך מתבררים בC
שאם אתה לא אומר typedef, אתה רק אומר struct, אז בתוך הסוגריים המסולסלים
אתה שם את המשתנים שלך, אז אתה מכניס את השם.
זו הכרזת מילון משתנה אחד בשם
שנראה כמו זה.
לעומת זאת, קווים אלה יוצרים מבנה נתונים לשימוש חוזר בשם מילה
כי אתה יכול ליצור עותקים מרובים של, בדיוק כמו שיצרנו
עותקים מרובים של תלמידים.
>> מה זה סופו של דבר יאפשר לנו לעשות?
תן לי לחזור אליו, תניחו, למשל פשוט מזמנים פשוטים יותר,
ותנו לי לפתוח, יניח, compare1.c.
הבעיה כאן, ביד היא למעשה נקלף
השכבה של מחרוזת ולהתחיל לקחת את גלגלי עזר אלה
כי מסתבר שכל הזמן הזה מחרוזת
היא כפי שהבטחנו בשבוע 1 באמת רק כינוי,
מילה נרדפת מCS50 הספרייה למשהו שנראה קצת יותר מסתורי,
* Char, וראינו כוכבים זה בעבר.
ראינו את זה בהקשר של קבצים.
>> עכשיו בואו נראה למה אנחנו כבר מסתירים פרט זה כבר כמה זמן.
הנה קובץ שנקרא compare1.c,
וזה ככל הנראה שואל את המשתמש עבור 2 מחרוזות, s ו t,
ואז הוא מנסה להשוות את המייתרים הללו לשוויון בקו 26,
ואם הם שווים זה אומר, "אתה הקלדת את אותו הדבר"
ואם הם לא שווים שהוא אומר, "אתה הקלדת דברים שונים".
תן לי ללכת קדימה ולהפעיל תכנית זו.
תן לי ללכת לספריית המקור שלי, להפוך את compare1. זה הידור בסדר.
תן לי לרוץ compare1.
אני להתקרב, להיכנס.
תגיד משהו. שלום.
אני אגיד משהו שוב. שלום.
אני בהחלט לא להקליד דברים שונים.
>> תן לי לנסות את זה שוב. ביי ביי.
בהחלט לא שונה, אז מה קורה כאן?
ובכן, מה באמת מושווה בקו 26?
[לא ברור לתלמיד]
כן, כך מתבררת, שהמחרוזת, סוג נתונים, היא סוג של שקר לבן.
מחרוזת היא * char, אבל מה היא * char?
* Char, כמו שאומרים, הוא מצביע,
ומצביע הוא למעשה כתובת,
מיקום סכום בזיכרון, ואם קורים לך שהקליד במילה כמו שלום,
זוכרים מהדיונים האחרונים של מחרוזות
זה כמו המילה שלום.
זכור שמילה כמו שלום יכולה להיות מיוצגת
כמערך של תווים כמו זה
ולאחר מכן עם דמות מיוחדת בסוף נקרא תו null,
כמסמל \.
מה היא בעצם מחרוזת?
שימו לב שזה חתיכות מרובות של זיכרון,
ולמעשה, בסופו של זה ידוע רק פעם אחת אתה מסתכל דרך כל השרשרת
מחפש תו null המיוחד.
אבל אם זה הוא נתח של זיכרון מהזיכרון של המחשב שלי,
בואו שרירותי אומרים שמחרוזת זו פשוט הייתה לו מזל,
והוא הלך לממוקם בתחילה מאוד של זכרון RAM של המחשב שלי.
זה ייט 0, 1, 2, 3, 4, 5, 6 ...
>> כשאני אומר משהו כמו GetString ואני עושה מחרוזת s = GetString
מה שבאמת שחזר?
במשך כמה שבועות האחרונים, מה באמת מאוחסנים בשל
לא זו מחרוזת כשלעצמה, אבל במקרה הזה מה שמאוחסן
0 מספר משום מה GetString עושה בפועל
הוא לא פיזי להחזיר מחרוזת.
זה אפילו לא באמת הגיוני רעיוני.
מה זה עושה החזרה היא מספר.
מספר זה הוא הכתובת של שלום בזיכרון,
ומחרוזת של אז, אם נקלף את השכבה, מחרוזת אינה קיימות באמת.
זה רק בפישוט CS50 הספרייה.
>> זה באמת משהו שנקרא * char.
Char הגיוני משום מה מילה, כמו הלו?
ובכן, מדובר בסדרה של תווים, סדרה של תווים.
* Char פירושו הכתובת של אופי,
אז מה זה אומר לחזור מחרוזת?
, דרך פשוטה נחמדה לחזור מחרוזת
היא במקום לנסות להבין איך אני חוזר ל5 או 6 בתים שונים
בואו תחזירו אותי לכתובת שהבתים?
ראשון.
במילים אחרות, תן לי לתת לך את הכתובת של דמות בזיכרון.
זה מה ש* char מייצג, את הכתובת של תו בודד אחד בזיכרון.
קוראים לזה של משתנה.
חנות בים שכתובת מסוימת, שבו אני באופן שרירותי אמר היא 0,
רק כדי לשמור על דברים פשוטים, אבל במציאות זה בדרך כלל מספר גדול יותר.
>> חכה רגע.
אם אתה רק נותן לי את הכתובת של התו הראשון, איך אני יודע מה כתובתו
בתו השני, השלישי, הרביעי והחמישי?
[לא ברור לתלמיד]
אתה רק יודע איפה סוף המחרוזת הוא בדרך של הטריק השימושי הזה,
לכן כאשר אתה משתמש במשהו כמו printf, מה printf ממש לוקח כטענתה,
זוכר שאנחנו משתמשים מציינים מיקום של% הזה, ואז אתה עובר ב
משתנה זה אחסון מחרוזת.
מה אתה באמת עובר הוא הכתובת של התו הראשון של מחרוזת ש.
Printf אז משתמש ללולאה או לולאה בזמן, עם קבלת כתובת ש,
למשל, 0, אז תן לי לעשות את זה עכשיו,
printf ("% s \ n", הים);
כשאני קורא printf ("% s \ n", הים), מה אני באמת מתן עם printf
היא הכתובת של התו הראשון בים, שבמקרה זה היא שרירותי ח
>> איך printf אינו יודע מה בדיוק כדי להציג על המסך?
מי שיישם יושם לולאה בזמן או ללולאת printf
שאומר אין אופי זה שווה תו null המיוחד?
אם לא, להדפיס אותו. מה דעתך על זה?
אם לא להדפיס אותו, להדפיס אותו, להדפיס אותו, להדפיס אותו.
אה, זה אחד מיוחד. להפסיק את ההדפסה ולחזור למשתמש.
וזה ממש כל מה שקורה מתחת למכסת המנוע,
וזה הרבה לעכל ביום הראשון של כיתה,
אך לעת עתה זה ממש אבן הבניין של כל הבנה
שנמשך כבר בתוך הזיכרון של המחשב שלנו,
וסופו של דבר אנחנו נתגרה זה בנפרד עם קצת עזרה
מאחד מהחברים שלנו בסטנפורד.
>> פרופסור ניק Parlante בסטנפורד עשה רצף וידאו הנפלא הזה
מכל מיני שפות שונות שהציגו
ינקי זה קצת אולפן אופי.
הקול שאתה עומד לשמוע רק כמה לחמוק תצוגה מקדימה 2
הוא זו של פרוף בסטנפורד, ואתה מקבל
רק 5 או 6 שניות של זכות זו עכשיו,
אבל זה בצליל שנוכל להסיק היום
ותתחיל ביום רביעי.
אני נותן לך כיף עם פוינטר בינקי, תצוגה המקדימה.
[♪ מוסיקת ♪] [פרופ Parlante] היי, בינקי.
תתעורר. זה זמן בשביל כיף מצביע.
[ינקי] מה זה? למד על מצביעים?
או, יופי!
>> אנחנו רואים אותך ביום רביעי.
[CS50.TV]