[Powered by Google Translate] [ביקורת] [חידון 0]
>> [לקסי רוס, טומי MacWilliam, לוקאס פרייטס, יוסף אונג] [אוניברסיטת הרווארד]
>> [זה CS50.] [CS50.TV]
>> היי, כולם.
ברוכים באים לפגישת הביקורת לחידון 0, שמתקיים ביום רביעי הקרוב.
מה אנחנו הולכים לעשות הלילה, אני עם 3 TFS אחר,
ויחד אנחנו הולכים לעבור סקירה של מה שעשינו בקורס עד כה.
זה לא הולך להיות 100% מקיפים, אבל זה אמור לתת לך רעיון טוב יותר
ממה שכבר יש לך את מה שאתה עדיין צריך ללמוד לפני יום רביעי.
ואל תהסס להרים את היד שלך עם שאלות כמו שאנחנו הולכים יחד,
אך יש לזכור שגם תהיה לנו קצת זמן בסוף
אם אנחנו מקבלים דרך עם כמה דקות לחילוף לעשות שאלות כלליות,
כל כך לזכור את זה, ולכן אנחנו מתכוונים להתחיל בתחילת שבוע עם 0.
>> [חידון 0 סקירה!] [חלק 0] [לקסי רוס] אבל לפני שאנחנו עושים את זה בואו נדבר על
הלוגיסטיקה של החידון.
>> [לוגיסטיקה] [החידון מתקיים ביום רביעי 10/10 במקום הרצאה]
>> [(ראה http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf לפרטים נוספים)] זה על יום רביעי 10 באוקטובר.
>> זה ביום רביעי, ואם אתה רוצה ללכת לכתובת אתר זו כאן,
שהוא גם נגיש מCS50.net-שם של קישור אליו,
אתה יכול לראות פרטים על לאן ללכת מבוסס על
השם שלך האחרון או השתייכות בית הספר כמו גם
היא מספרת על מה בדיוק את החידון ויכסה את סוגי שאלות שאתה הולך לקבל.
זכור כי אתה גם תהיה לך הזדמנות לעיין בחידון בסעיף,
כך TFS שלך צריך ללכת על כמה בעיות בפועל,
וזה עוד הזדמנות טובה לראות בו אתה עדיין צריך ללמוד עד לחידון.
בואו נתחיל בהתחלה עם Bytes 'n' Bits.
זכור קצת הוא רק 0 או 1,
ובתים הם אוסף של 8 הביטים האלה.
בואו נסתכל על זה אוסף של ביטים ממש כאן.
אנחנו צריכים להיות מסוגלים להבין כמה ביטים יש.
איפה אנחנו סופרים יש רק 8 מתוכם, 8 0 או 1 יחידות.
וכיוון שיש 8 ביטים, זה בית 1,
ובואו להמיר אותו להקסדצימלי.
הקסאדצימלי הוא 16 בסיס, וזה די קל להמיר
מספר בינארי, וזה מה שהוא, למספר בקסדצימלי.
כל מה שאנחנו עושים הוא שאנחנו מסתכלים על קבוצות של 4,
ולהמיר אותם לספרה ההקסדצימלי המתאימה.
אנחנו מתחילים עם הקבוצה הימנית ביותר מתוך 4, אז 0011.
זה הולך להיות אחד 1 ו 1 2, אז ביחד זה עושה 3.
ואז בואו נסתכל על הבלוק השני של 4.
1101. זה הולך להיות אחד 1, אחד 4, ואחד 8.
ביחד זה הולך להיות 13, מה שהופך את ד
ואנו זוכרים שבהקסדצימלי אנחנו לא הולכים רק 0 עד 9.
אנחנו הולכים 0 עד F, אז אחרי 9, 10, מקביל,
11 ל-B, וכולי כאשר F הוא 15.
הנה הם 13 D,
כך כדי להמיר אותו למספר עשרוני כל מה שאנחנו עושים זה בעצם
להתייחס לכל עמדת כוח של 2.
זה אחד 1, 1 2, אפס 4s, 8s אפס, אחד 16, וכולי,
וזה קצת קשה לחשב בראש שלך, אבל אם נלך לשקופית הבאה
אנו יכולים לראות את התשובה לכך.
>> בעיקרו של דבר אנחנו הולכים מול זכות חזרה לשמאל,
ואנחנו הכפלה כל ספרה על ידי הכח המקביל של 2.
ותזכור, להקסדצימלי נסמן את המספרים האלה עם 0x בהתחלה
ולכן אנחנו לא לבלבל אותו עם מספר עשרוני.
ולהמשיך הלאה, זה טבלת ASCII,
ומה אנו משתמשים לASCII הוא למפות מתווים לערכים מספריים.
זכור בpset קריפטוגרפיה עשינו שימוש נרחב בטבלת ASCII
כדי להשתמש בשיטות שונות של הצפנה,
קיסר וצופן Vigenère, להמיר אותיות שונות
במחרוזת לפי המפתח הנתון על ידי המשתמש.
בואו נסתכל קצת מתמטיקת ASCII.
כאשר מסתכלים על 'P' + 1, בצורת דמות שתהיה ש,
ולזכור ש'5 '≠ 5.
ואיך בדיוק הייתי לנו להמיר בין 2 הצורות האלה?
למען האמת היא לא קשה מדי.
על מנת לקבל 5 נתעלמנו '0 '
משום שיש 5 מקומות בין '0 'ו'5'.
כדי ללכת בדרך האחרת רק תוסיפי 0,
אז זה כמו סוג של חשבון רגיל.
רק תזכור שכאשר משהו יש ציטוטים סביבו זה אופי
ובכך מתאים לערך בטבלת ASCII.
עובר לנושאי מדע כלליים יותר של מחשב.
למדנו מה הוא אלגוריתם וכיצד אנו משתמשים בתכנות
ליישם אלגוריתמים.
כמה דוגמאות של אלגוריתמים הן משהו ממש פשוט כמו
בודק אם מספר הוא גם או מוזר.
בשביל זה אנחנו זוכרים mod המספר ב 2 ובדקו אם התוצאה היא 0.
אם כך, זה אפילו. אם לא, זה מוזר.
וזה דוגמה של אלגוריתם באמת בסיסי.
>> קצת יותר מעורב 1 הוא חיפוש בינארי,
שנלך מעל מאוחר יותר בפגישת הביקורת.
ותכנות הוא המונח שאנו משתמשים ללקיחת אלגוריתם
וממיר אותו לקוד שהמחשב יכול לקרוא.
2 דוגמאות של תכנות היא גרד,
וזה מה שעשינו בשבוע 0.
למרות שאנחנו לא באמת הקלידו את הקוד שזה דרך של יישום
אלגוריתם זה, המדפיס את המספרים 1-10,
וכאן אנחנו עושים את אותו הדבר בשפת תכנות C.
אלה הם פונקציונליים שווים, רק שנכתב בשפות או תחביר שונות.
אז למדנו על ביטויי וליאניות,
ובוליאני הוא ערך זה אמת או שקר,
וביטויים כאן לעתים קרובות וליאניות
להיכנס פנימה של תנאים, כך שאם (x ≤ 5),
טוב, אנחנו כבר להגדיר x = 5, ולכן מצב שהוא הולך להערכה אמיתית.
ואם זה נכון, מה שקוד הוא מתחת למצב
הולך להיות מוערך על ידי המחשב, ולכן המחרוזת כי הוא הולך להיות מודפס
לפלט סטנדרטי, ותנאי הטווח
מתייחס לכל מה שבתוך הסוגריים של אם ההצהרה.
זכור את כל המפעילים.
זכור && של זה ו| | כאשר אנחנו מנסים לשלב 2 או יותר תנאים,
== לא = כדי לבדוק אם 2 דברים שווים.
זכור כי = הוא למשימה ואילו == הוא מפעיל וליאני.
≤, ≥ ולאחר מכן 2 הסופיים הם ברורים מאליו.
סקירה כללית של היגיון בוליאני כאן.
וביטויי וליאניות חשובים גם בלולאות,
שנלך על עכשיו.
למדנו בערך 3 סוגים של לולאות עד כה בCS50, ל, הזמן, ולעשות בזמן.
וזה חשוב שידע שלמרות לרוב מטרות
אנחנו יכולים להשתמש בכל סוג של לולאה בדרך
ישנם סוגים מסוימים של מטרות או דפוסים נפוצים
בתכנות שדווקא קורא לאחת מהלולאות האלה
זה עושה את זה יעיל או אלגנטי שיצפין אותה בדרך זו ביותר.
בואו נלך על מה שכל אחד מהלולאות הללו נוטה לשמש בתדירות הגבוהה ביותר.
>> בלולאה אנחנו בדרך כלל כבר יודעים כמה פעמים אנחנו רוצים לחזר.
זה מה שאנחנו מכניסים למצב.
ל, i = 0, i <10, למשל.
אנחנו כבר יודעים שאנחנו רוצים לעשות משהו 10 פעמים.
עכשיו, ללולאה בזמן, בדרך כלל אנחנו לא בהכרח
יודע כמה פעמים אנחנו רוצים הלולאה לרוץ.
אבל אנחנו יודעים איזה תנאים שאנחנו רוצים שהוא
תמיד להיות נכון או תמיד יהיה שקר.
לדוגמה, בזמן מוגדר.
בואו נגיד שזה משתנה בוליאני.
למרות שזה נכון שאנחנו רוצים את הקוד כדי להעריך,
כך קצת יותר להרחבה, קצת כללי יותר מקטן ללולאה,
אבל כל ללולאה ניתן גם להמיר ללולאה בזמן.
לבסוף, לעשות בזמן לולאות, שעשוי להיות הקשה ביותר להבנה באופן מיידי,
משמש לעתים קרובות כאשר אנו רוצים להעריך את הקוד ראשון
לפני הפעם הראשונה שאנחנו בודקים את מצבו.
שימוש נפוץ ליעשה תוך לולאה
כאשר אתה רוצה לקבל קלט משתמש, ואתה יודע שאתה רוצה לשאול את המשתמש
עבור קלט לפחות פעם אחת, אבל אם הם לא נותנים לך קלט טוב תיכף ומייד
אתה רוצה להמשיך לשאול אותם עד שהם נותנים לך קלט הטוב.
זה השימוש הנפוץ ביותר שלי בזמן לולאה,
ובואו נסתכל על המבנה בפועל של לולאות אלו.
הם בדרך כלל תמיד נוטים ללכת בעקבות דפוסים אלה.
>> בלולאה בתוכך יש 3 מרכיבים:
אתחול, בדרך כלל משהו כמו אני int = 0 שבו אני הוא הדלפק,
מצב, שבו אנו רוצים לומר להפעיל את זה ללולאה כל עוד התנאי הזה תקף,
כמו i <10, ולבסוף, עדכון, וככה אנחנו להגדיל
משתנה דלפק בכל נקודה בלולאה.
דבר שכיח לראות יש רק אני + +,
כלומר להגדיל לי עד ליום 1 בכל פעם.
אתה יכול גם לעשות משהו כמו i + = 2,
כלומר להוסיף 2 ל i כל פעם שאתה עובר את הלולאה.
ואז לעשות את זה פשוט מתייחס לכל קוד שבעצם פועל כחלק מהלולאה.
וללולאה בזמן, הפעם אנחנו באמת צריכים אתחול מחוץ למעגל,
כך לדוגמה, אניח שאנחנו מנסים לעשות את אותו הסוג של לולאה כמו שתארתי.
היינו אומרים אני int = 0 לפני הלולאה מתחיל.
ואז תוכל לומר לי תוך <10 לעשות את זה,
כך באותו הבלוק של קוד כמו קודם,
והפעם עדכון חלק של הקוד, לדוגמה, אני + +,
בעצם הולך בתוך הלולאה.
ולבסוף, ללעשות בזמן, זה דומה ללולאה בזמן,
אבל אנחנו צריכים לזכור שהקוד יהיה להעריך פעם אחת
לפני המצב מסומן, כך שזה עושה הרבה יותר מובן
אם אתה מסתכל עליו בצו של מלמעלה למטה.
בלעשות בעוד לולאת הקוד מעריך עוד לפני שאתה מסתכל על המצב בזמן,
בעוד לולאה בזמן, הוא בודק ראשון.
דוחות ומשתנה.
כאשר אנו רוצים ליצור משתנה חדשים שאנו ראשונים רוצים לאתחל אותו.
>> לדוגמה, בר int מאתחל את הסרגל משתנה,
אבל זה לא נותן לו ערך, אז מה היא שוויו של הבר עכשיו?
אנחנו לא יודעים.
זה יכול להיות איזה שהוא ערך זבל שאוחסן קודם לכן בזיכרון שם,
ואנחנו לא רוצים להשתמש במשתנה ש
עד שלמעשה לתת לו ערך,
כך אנו מצהירים את זה כאן.
אז לאתחל אותו להיות 42 להלן.
עכשיו, כמובן, אנחנו יודעים שזה יכול להיעשות בשורה אחת, int הבר = 42.
אבל רק שיהיה ברורים את השלבים המרובים שהם קורים,
ההצהרה והאתחול קורות בנפרד כאן.
זה קורה בשלב אחד, והבא, ובאז int = בר + 1,
הצהרה זו להלן, שבאז במרווחים, ולכן בסופו של קטע הקוד הזה
אם היינו מדפיס את ערכו של באז זה יהיה 44
משום שאנו מצהירים ולאתחל אותו להיות ברים> 1,
ואז להגדיל אותו עוד פעם אחת עם + +.
ניגשנו לרגע היפה הזה, אבל זה טוב שיש בכלל
הבנה של מה הם נושאים ואירועים.
אנחנו בעיקר עשינו את זה בהתחלה,
כך שאתה יכול לחשוב על נושאים כרצפים מרובים של קוד
פועל באותו הזמן.
בפועל, זה כנראה לא פועל באותו הזמן,
אבל כאילו בצורה מופשטת אנחנו יכולים לחשוב עליו בדרך זו.
>> בלגרד, למשל, היו לנו את השדונים המרובים.
זה יכול להיות ביצוע קוד שונה באותו הזמן.
אחד יכול להיות הליכה ואילו השני אומר משהו
בחלק אחר של המסך.
אירועים הם דרך נוספת להפריד את ההיגיון
בין מרכיבים שונים של הקוד שלך,
ובסריטות שהיינו מסוגל לדמות אירועים באמצעות שידור,
וזה בעצם כשאני מקבל, לא כשאני שומע,
אבל בעיקרו של דבר דרך להעברת מידע
מספרייט אחד למשנו.
לדוגמה, ייתכן שתרצה להעביר את המשחק,
וכאשר ספרייט אחר מקבל משחק נגמר,
הוא מגיב בדרך מסוימת.
זה מודל חשוב להבין לתכנות.
רק לעבור על השבוע הבסיסי 0, מה שאנחנו כבר דברנו על כך הרבה,
בואו נסתכל על תכנית C פשוטה זו.
הטקסט עשוי להיות קצת קטן מכאן, אבל אני אלך על זה ממש מהר.
אנו כוללים את 2 קבצי כותרת בחלק העליון, וcs50.h stdio.h.
אז אנחנו מגדירים את גבול נקרא מתמיד להיות 100.
אז אנחנו מיישמים הפונקציה העיקרית שלנו.
מכיוון שאנחנו לא משתמשים בטיעוני שורת פקודה כאן אנחנו צריכים לשים את הריק
כנימוקים עיקריים.
אנו רואים int לעיל ראשי. זה סוג התמורה, ומכאן להחזיר 0 בתחתית.
ואנחנו משתמשים בפונקצית ספריית CS50 לקבל int
לשאול את המשתמש עבור קלט, ואנחנו מאחסנים אותו במשתנה זה x,
כך אנו מצהירים מעל x, ואנחנו לאתחל אותו עם x = GetInt.
>> לאחר מכן, אנו בודקים אם המשתמש נתן לנו קלט טוב.
אם זה LIMIT ≥ אנחנו רוצים להחזיר קוד שגיאה של 1 ולהדפיס הודעת שגיאה.
ולבסוף, אם קלט המשתמש נתן לנו טוב
אנחנו הולכים ליישב את המספר ולהדפיס את התוצאה.
רק כדי לוודא שכל מי בית הלהיט
אתה יכול לראות את התוויות של חלקים שונים של הקוד כאן.
הזכרתי קבצים קבועים, של כותרות.
אה, int x. ודא שיש לזכור שזה משתנה מקומי.
זאת, בניגודו ממשתנה גלובלי, שנדברנו על
מעט מאוחר יותר בישיבת הביקורת,
ואנחנו קוראים את פונקצית ספריית printf,
כך שאם לא הייתי כלול בקובץ הכותרת stdio.h
לא הייתי מסוגל לקרוא printf.
ואני מאמין שהחץ שנותק, כאן הוא הצביע על ד%,
אשר היא מחרוזת עיצוב בprintf.
זה אומר להדפיס את משתנה זה כמספר, ד%.
וזה אותו שבוע ל0.
עכשיו לוקאס הולך להמשיך.
היי, חבר 'ה. השם שלי הוא לוקאס.
אני בכיתת י 'בבית הטוב ביותר בקמפוס, מאת'ר,
ואני הולך לדבר קצת על שבוע 1 ו 2.1.
[1 שבוע ו -2.1!] [לוקאס פרייטס]
כקסי אמר, כשהתחלנו לתרגם את הקוד שלך מהתחלה כדי C
אחד הדברים שאנו הבחנו הוא שאתה לא יכול פשוט
לכתוב את הקוד שלך ולהפעיל אותו באמצעות דגל ירוק יותר.
למעשה, אתה צריך להשתמש בכמה צעדים כדי להפוך את תכנית C
להפוך קובץ הפעלה.
בעיקרון מה שאתה עושה כשאתה כותב תכנית הוא כי
אתה מתרגם את הרעיון שלך לשפה שמהדר יכול להבין,
לכן כאשר אתה כותב תכנית ב-C
מה שאתה עושה הוא בעצם כותב משהו שהמהדר שלך לא יבין,
ואז המהדר הולך לתרגם קוד ש
למשהו שהמחשב שלך יבין.
>> והעניין הוא, המחשב שלך הוא בעצם מאוד מטומטם.
המחשב שלך יכול להבין 0s ו 1s בלבד,
כך למעשה במחשבים הראשונים שהאנשים בדרך כלל לתכנת
באמצעות 0s ו 1s, אבל לא יותר, תודה לאל.
אנחנו לא צריכים לשנן את הרצפים ל0s ו 1s
עבור ללולאה או ללולאה בזמן וכן הלאה.
זו הסיבה שיש לנו במהדר.
מה מהדר עושה זה בעצם מתרגם את קוד C,
במקרה שלנו, לשפה שהמחשב יבין,
המהווה את קוד האובייקט, ומהדר שאנחנו משתמשים
נקרא להרעיש, ואז זה בעצם הסמל לצלצול.
כאשר יש לך תכנית שלך, אתה צריך לעשות 2 דברים.
ראשית, אתה צריך לקמפל את התכנית שלך, ואז אתה הולך להפעיל את התכנית שלך.
כדי להדר את התכנית שלך יש לך הרבה אפשרויות לעשות זאת.
הראשון הוא לעשות program.c צלצול
בתכנית שבה הוא השם של התכנית שלך.
במקרה זה אתה יכול לראות שהם רק אומרים "היי, לקמפל את התכנית שלי".
אתה לא אומר "אני רוצה את השם הזה לתכנית שלי" או משהו כזה.
>> האפשרות השנייה היא לתת שם לתכנית שלך.
אתה יכול להגיד צלצול-O ולאחר מכן את השם שאתה רוצה
קובץ ההפעלה שייקרא וכאז program.c.
ואתה יכול גם לעשות להפוך את התכנית, ורואה איך ב2 המקרים הראשונים
אני שם. ג, ובשלישי יש לי תוכניות בלבד?
כן, אתה באמת לא צריך לשים. ג כאשר אתה משתמש לעשות.
אחרת המהדר הוא בעצם הולך לצעוק עליך.
וגם, אני לא יודע אם אתם זוכרים,
אבל הרבה פעמים אנחנו משמשים-lcs50 גם או lm.
זה נקרא קישור.
זה פשוט אומר למהדר שתוכל להשתמש בספריות האלה כאן,
כך שאם ברצונך להשתמש cs50.h אתה בעצם צריך להקליד
צלצול program.c-lcs50.
אם אתה לא עושה את זה, המהדר לא הולך לדעת
שאתה משתמש בפונקציות האלה בcs50.h.
וכאשר ברצונך להפעיל את התכנית שלך יש לך 2 אפשרויות.
אם עשית program.c צלצול שלא לתת שם לתכנית שלך.
אתה צריך להפעיל אותו באמצעות. / A.out.
A.out הוא שם סטנדרטי שנותן צלצול התכנית שלך אם אתה לא נותן לו שם.
אחרת אתה הולך לעשות. / תכנית אם נתת שם לתכנית שלך,
וגם אם אתה עושה התכנית עשה שם שתכנית הוא הולך לקבל
כבר הולך לתכנת אותו שם כמו קובץ c.
ואז דברו על סוגי נתונים ונתונים.
>> בעיקרון סוגי נתונים הם אותו דבר כמו קופסות קטנות שהם משתמשים
לאחסון ערכים, ולכן סוגי נתונים הם למעשה בדיוק כמו פוקימונים.
הם באים בכל הגדלים וסוגים.
אני לא יודע אם אנלוגיה זה הגיוני.
גודל הנתונים בפועל תלוי בארכיטקטורת המחשב.
כל גדלי הנתונים שאני הולך להראות כאן
הם למעשה למכונה 32-bit, שהוא במקרה של המכשיר שלנו,
אבל אם אתה בעצם קידוד Mac או בWindows שלך גם
כנראה שאתה הולך יש לי מכונית 64-bit,
כך זוכר שגדלי הנתונים שאני הולך להראות כאן
הם למכונת 32-bit.
הראשונה שראינו הייתה int,
וזה די פשוט.
אתה משתמש int כדי לאחסן מספר שלם.
ראו גם את הדמות, char.
אם אתה רוצה להשתמש באות או סימן קטן אתה כנראה הולך להשתמש char.
דמות יש בית 1, כלומר 8 ביטים, כמו לקסי אמר.
בעיקרון יש לנו טבלת ASCII שיש 256
שילובים אפשריים של 0s ו 1s,
ולאחר מכן בעת ​​הקלדת char זה הולך לתרגם
הדמות שהתשומות לך מספר שיש לך בטבלת ASCII, כמו לקסי אמרה.
יש לנו גם לצוף, בו אנו משתמשים כדי לאחסן מספרים עשרוניים.
אם אתה רוצה לבחור 3.14, לדוגמה, אתה הולך להשתמש במצוף
או כפול שיש לו יותר דיוק.
לצוף יש 4 בתים.
כפול יש 8 בתים, אז ההבדל היחיד הוא הדיוק.
יש לנו גם ארוך המשמש למספרים שלמים,
ואתה יכול לראות במכונה 32-bit int ועוד יש לו גודל,
אז זה לא ממש הגיוני להשתמש בזמן במכונה 32-bit.
>> אבל אם אתה משתמש במחשב Mac ו 64-bit, ממש ארוך יש גודל 8,
כך שזה באמת תלוי באדריכלות.
למכונת 32-bit זה לא הגיוני להשתמש בזמן באמת.
ואז עוד ארוך, לעומת זאת, יש 8 בתים,
אז זה מאוד טוב אם אתה רוצה להיות יותר שלם.
ולבסוף, יש לנו חוט, שהוא בעצם * char,
שהוא מצביע לchar.
זה קל מאוד לחשוב שהגודל של המחרוזת הוא הולך להיות כמו
מספר התווים שיש לך שם,
אבל בעצם * char עצמו
יש את הגודל של מצביע char, שזה 4 בתים.
הגודל של * char הוא 4 בתים.
זה לא משנה אם יש לך מילה קטנה או מכתב או משהו.
זה הולך להיות 4 בתים.
למדו גם קצת על ליהוק,
אז כפי שאתם יכולים לראות, אם יש לך, למשל, תכנית שאומרת
int x = 3 ואז printf ("% d", x / 2)
אתם יודעים מה זה הולך להדפסה על מסך?
>> מישהו? >> [סטודנטים] 2.
1. >> 1, כן.
כאשר אתה עושה 3/2 זה הולך לקבל 1.5,
אבל מכיוון שאתה משתמש במספר שלם זה הולך להתעלם מהחלק העשרוני,
ואתה הולך להיות 1.
אם אתה לא רוצה שזה יקרה מה שאתה יכול לעשות, למשל,
הוא מצהיר לצוף y = x.
אז X שהיו בעבר 3 עכשיו הולך להיות 3.000 בy.
ואז אתה יכול להדפיס את y / 2.
למעשה, אני צריך 2. לשם.
זה הולך לעשות 3.00/2.00,
ואתה הולך לקבל 1.5.
ויש לנו .2 f זה רק כדי לבקש 2 יחידות עשרוניות בחלק העשרוני.
אם יש לך .3 f זה הולך לי 1.500 בפועל.
אם זה 2 שזה הולך להיות 1.50.
יש לנו גם המקרה הזה כאן.
אם אתה עושה את המצוף X = 3.14 ואז אתה x printf
אתה הולך לקבל 3.14.
ואם אתה עושה x = int של x,
מה שאומר שטיפול x כint ואתה מדפיס x עכשיו
אתה הולך להיות 3.00.
האם זה הגיוני?
בגלל שאתה בטיפול 1 x כמספר שלם, אז אתה מתעלם מהחלק העשרוני,
ואז אתה מדפיס x.
ולבסוף, אתה יכול גם לעשות את זה,
int x = 65, ואז אתה מצהיר char c = x,
ואז אם אתה מדפיס ג אתה בעצם הולך לקבל
, אז בעצם מה שאתה עושה כאן
הוא לתרגם את המספר השלם לתוך הדמות,
בדיוק כמו טבלת ASCII עושה.
דברו גם על מפעילי מתמטיקה.
רובם הם די פשוטים, ולכן +, -, *, /,
וגם דברנו על mod, המהווה את שארית חלוקה של 2 מספרים.
אם יש לך 10% 3, למשל,
זה אומר לחלק את 10 על ידי 3, ומה היא השארית?
זה הולך להיות 1, כך שזה באמת מאוד שימושי להרבה מהתוכניות.
לVigenère וקיסר אני די בטוח שכולכם השתמשתי mod.
על מפעילי מתמטיקה, להיות זהיר מאוד כאשר שילוב * ו /.
>> לדוגמה, אם אתה עושה (3/2) * 2 מה אתה הולך לקבל?
[סטודנטים] 2.
כן, 2, כי 3/2 הולך להיות 1.5,
אבל מכיוון שאתה עושה פעילות בין 2 מספרים שלמים
אתה בעצם רק הולך לשקול 1,
ואז * 1 2 הולך להיות 2, ולכן להיות מאוד, מאוד זהיר
כאשר עושים חשבון עם מספרים שלמים בגלל
אתה יכול לקבל כי 2 = 3, במקרה זה.
וגם להיות מאוד זהיר לגבי קדימות.
אתה צריך בדרך כלל להשתמש בסוגריים כדי להיות בטוח שאתה יודע מה אתה עושה.
החלק מקיצורי הדרך שימושיים, כמובן, אחת הם i + + או i + = 1
או שימוש = +.
זה אותו הדבר כמו לעשות i = i + 1.
אתה גם יכול לעשות לי - או שאני - = 1,
שזה אותו דבר כמוני = אני -1,
אתם משהו משתמשים הרבה בלולאות, לפחות.
כמו כן, עבור *, אם אתה משתמש * = ואם אתה עושה, למשל,
i * = 2 הם אותו הדבר כמו לומר אני = i * 2,
ואותו דבר לחלוקה.
אם אתה עושה לי / = 2 זה אותו הדבר כמו i = i / 2.
>> עכשיו על פונקציות.
אתם למדתם שפונקציות הן אסטרטגיה טובה מאוד לשמירת קוד
בזמן שאתה מתכנת, כך שאם אתה רוצה לבצע את אותה המשימה
בקוד שוב ושוב, כנראה שאתה רוצה להשתמש בפונקציה
רק כדי שלא יצטרך להעתיק ולהדביק את הקוד שוב ושוב.
למעשה, היא פונקציה עיקרית, וכשאני מראה אותך את התבנית של פונקציה
אתה הולך לראות את זה שהוא די ברור.
אנחנו גם להשתמש בפונקציות מספריות מסוימות,
לדוגמה, printf, GetIn, שהוא מספריית CS50,
ופונקציות נוספות כמו toupper.
כל הפונקציות הללו הם למעשה מיושמים בספריות אחרות,
וכאשר אתה שם את הקבצים האלה לקשור בתחילת התכנית שלך
שאתה אומר אתה יכול בבקשה לתת לי את הקוד לפונקציות אלה
אז אני לא אצטרך ליישם אותם בעצמי?
ואתה יכול גם לכתוב פונקציות משלך, כך שכאשר אתה מתחיל בתכנות
אתה מבין שאין לי ספריות את כל הפונקציות שאתה צריך.
לpset האחרון, למשל, שכתבנו לצייר, צעקות, ובדיקה,
וזה מאוד מאוד חשוב להיות מסוגל לכתוב פונקציות
משום שהם שימושיים, ואנחנו משתמשים בם כל הזמן בתכנות,
וזה חוסך הרבה קוד.
הפורמט של פונקציה הוא זה אחד.
יש לנו סוג החזרה בהתחלה. מהו סוג התמורה?
זה רק כאשר התפקוד שלך הולך לחזור.
אם יש לך פונקציה, למשל, עצרת,
כי הוא הולך לחישוב עצרת של מספר שלם,
כנראה שזה הולך לחזור גם שלם.
אז סוג ההחזרה הולך להיות int.
Printf למעשה יש חלל סוג החזרה
כי אתה לא חוזר שום דבר.
אתה פשוט להדפיס דברים על המסך
והפסקת התפקוד לאחר מכן.
אז יש לך את השם של הפונקציה שאתה יכול לבחור.
אתה צריך להיות קצת הגיוני, כמו לא בוחר שם כמו xyz
או כמו x2f.
אנסה להמציא שם זה הגיוני.
>> לדוגמה, אם זה עצרת, אומרים עצרת.
אם זה פונקציה שהוא הולך לצייר משהו, שם זה לצייר.
ואז יש לנו את הפרמטרים, שנקראים גם טיעונים,
שהם כמו את המשאבים שהפונקציה שלך צריכה
מהקוד שלך כדי לבצע את המשימה שלו.
אם ברצונך לחשב את העצרת של מספר
כנראה אתה צריך לעבור מספר לחשב עצרת.
אחת הטענות שאתה הולך להיות הוא המספר עצמו.
ואז זה הולך לעשות משהו ולהחזיר את הערך בסוף
אלא אם כן זה פונקציה מבוטלת.
בואו לראות דוגמה.
אם אני רוצה לכתוב פונקציה שמסכמת את כל המספרים במערך של מספרים שלמים,
קודם כל, סוג ההחזרה הולך להיות int
כי יש לי מערך של מספרים שלמים.
ואז אני הולך להיות שם פונקציה כמו sumArray,
ואז זה הולך לקחת את המערך עצמו, לnums int,
ואז האורך של המערך ולכן אני יודע כמה מספרים יש לי לסכם.
ואז אני צריך לאתחל סכום משתנה נקרא, למשל, ל0,
ובכל פעם שאני רואה אלמנט במערך שאני צריך להוסיף אותו לסכום, אז עשיתי ללולאה.
בדיוק כמו לקסי אמר, אתה עושה אני int = 0, i <אורך ואני + +.
ועבור כל רכיב במערך שעשיתי סכום + = nums [i],
ואז החזרתי את הסכום, כך שזה מאוד פשוט, וזה חוסך הרבה קוד
אם אתה משתמש בפונקציה זו הרבה פעמים.
אז לקחנו מבט בתנאים.
יש לנו אם, אחר, ואם אחר.
בואו נראה מה היא ההבדל בין אלה.
תסתכל על 2 קודים אלה. מה ההבדל ביניהם?
1 הראשון, בעצם את הקודים רוצה שתגידו
אם מספר הוא +, -, או 0.
הראשונה אומרת שאם זה> 0 אז זה חיובי.
אם זה = ל 0 אז זה 0, ואם זה <0 אז זה שלילי.
>> והשני עושה אם, אם אחר, אחר.
ההבדל בין השניים הוא שזה דווקא הולך
לבדוק אם> 0, <0 או 0 = שלוש פעמים,
כך שאם יש לך את המספר 2, למשל, זה הולך לבוא לכאן ולומר
אם (x> 0), וזה הולך לומר כן, ולכן אני מדפיס חיובי.
אבל למרות שאני יודע שזה> 0 וזה לא הולך להיות 0 או <0
אני עדיין הולך לעשות את זה הוא 0, הוא אותו <0,
אז בעצם אני הולך בתוך של אילו שלא היה לי ל
כי אני כבר יודע שזה לא הולך כדי לספק את כל התנאים הללו.
אני יכול להשתמש אם, אם אחר, אחר אמירה.
זה בעצם אומר שאם x = 0 אני מדפיס חיובי.
אם זה לא, אני הולך לבדוק את זה גם.
אם זה לא 2 אני הולך לעשות את זה.
בעיקרון, אם היה לי x = 2 היית אומר
אם (x> 0), כן, אז להדפיס את זה.
עכשיו שאני יודע שזה> 0 וכי הוא מרוצה הראשון אם
אני אפילו לא מתכוון לרוץ את הקוד הזה.
הקוד רץ מהר יותר, למעשה, 3 פעמים מהר יותר אם אתה משתמש בזה.
למדו גם על ואו.
אני לא הולך לעבור את זה, כי לקסי כבר דבר עליהם.
זה רק את && ו | | מפעיל.
>> הדבר היחיד שאני יכול לומר הוא להיות זהיר כאשר יש לך 3 תנאים.
השתמש בסוגריים כי זה מאוד מבלבל כאשר יש לך מצב
ועוד אחת או אחד את השני.
השתמש בסוגריים רק כדי להיות בטוח שהתנאים שלך הגיוניים
כי במקרה כזה, לדוגמה, אתה יכול לדמיין את זה
זה יכול להיות התנאי הראשון ואחד או אחר
או את 2 תנאים בשילוב וב
או השלישי, כל כך פשוט להיות זהיר.
ולבסוף, דבר על מתגים.
בורר הוא מאוד שימושי כאשר יש לך משתנה.
בואו נגיד שיש לך משתנה כמו n
שיכול להיות 0, 1 או 2, ועבור כל אחד ממקרים אלה
אתה הולך לבצע משימה.
אתה יכול להגיד לעבור משתנה, והוא מציין כי
אז הערך הוא כמו value1 אני הולך לעשות את זה,
ואז אני שובר, מה שאומר שאני לא הולך להסתכל על כל אחד מהמקרים האחרים
כי אנחנו כבר מרוצים מקרה ש
ולאחר מכן value2 וכן הלאה, ואני גם יכול לקבל מתג ברירת מחדל.
זאת אומרת שאם זה לא מספק את כל אחד מהמקרים שהיו לי
שאני הולך לעשות משהו אחר, אבל זה לא חובה.
זה כל מה שבשבילי. עכשיו בואו יש טומי.
בסדר, זה הולך להיות שבוע 3-ish.
אלה הם חלק מהנושאים שאנו תהיו כיסוי, אנוסים, היקפו, מערכיו, וכולי.
רק כמה מילים על אנוסים. אנחנו לא הולכים לתקוע את זה הביתה.
>> אנחנו עשינו את זה בpset 2, אבל לחידון לוודא שאתה יודע את ההבדל
בין קיסר הצופן וצופן Vigenère,
איך שני אלה צפני העבודה ומה שהיא רוצה להצפין
וטקסט לפענח באמצעות 2 צפנים אלה.
זכור, קיסר הצופן פשוט מסתובב כל תו, באותו הסכום,
וודא שאתה mod במספר האותיות באלף הבית.
וצופן Vigenère, לעומת זאת, מסתובב כל תו
בסכום שונה, אז במקום לומר
כל סיבוב אופי של 3 Vigenère יהיה לסובב כל תו
בסכום שונה בהתאם למילות מפתח מסוים
שבו כל אות במילת המפתח מייצגת שונה במידה מסוימת
כדי לסובב את הטקסט הברור על ידי.
בואו נדבר קודם כל על היקף משתנה.
ישנם 2 סוגים שונים של משתנים.
יש לנו משתנים מקומיים, ואלה הולכים להיות מוגדרים
מחוץ לראשי או מחוץ לכל פונקציה או בלוק,
ואלה יהיו נגישים בכל מקום בתכנית שלך.
אם יש לך פונקציה והפונקציה היא שבלולאה בזמן
המשתנה הגלובלי הגדול נגיש בכל מקום.
משתנה מקומי, לעומת זאת, הוא scoped למקום שבו הוא מוגדר.
>> אם יש לך פונקציה כאן, למשל, יש לנו גרם פונקציה זו,
ובתוך הגר יש כאן משתנה בשם y,
וזה אומר שזה משתנה מקומי.
למרות שמשתנה זה נקרא y
ומשתנה זה נקרא Y 2 הפונקציות האלה
אין לי מושג מה המשתנים המקומיים של זה הם.
מצד השני, עד כאן אנחנו אומרים int x = 5,
וזה הוא מחוץ לתחום של כל אירוע.
זה מחוץ לתחום עיקרי, ולכן זה משתנה גלובלי.
זה אומר שבתוך של 2 פונקציות אלה כשאני אומר x - או x + +
אני ניגש לאותו x לפי y זה y וזה הוא משתנים שונים.
זה הבדל בין משתנה הגלובלי ומשתנה מקומיים.
מבחינת עיצוב הוא מודאג, לפעמים זה כנראה רעיון טוב יותר
כדי לשמור על משתנים מקומיים בכל פעם שאתה אולי יכול
מאז שיש לו חבורה של משתנים הגלובליים יכולה להיות ממש מבלבלת.
אם יש לך חבורה של פונקציות כל שינוי אותו הדבר
אתם עלולים לשכוח מה אם פונקציה זו משנה את הטעות הזו גלובלית,
והפונקציה שנייה לא יודעת על זה,
והוא מגיע די מבלבל כמו שאתה מקבל יותר קוד.
שמירה על משתנים מקומיים בכל פעם שאתה אולי יכול
עיצוב הוא פשוט טוב.
מערכים, יש לזכור, הם פשוט רשימות של אלמנטים מאותו הסוג.
בתוך CI לא יכול יש לי רשימה כמו 1, 2.0, שלום.
אנחנו פשוט לא יכולים לעשות את זה.
>> כאשר אנו מצהירים במערך C כל האלמנטים צריכים להיות מאותו הסוג.
כאן יש לי מערך של 3 מספרים שלמים.
כאן יש לי אורך של המערך, אבל אם אני רק מצהיר על זה בתחביר זה
שבו אני מציין מה כל הרכיבים הם מבחינה טכנית אני לא צריך את זה 3.
המהדר הוא חכם מספיק כדי להבין עד כמה גדול המערך צריך להיות.
עכשיו כשאני רוצה לקבל או להגדיר את ערכו של מערך
זה התחביר כדי לעשות את זה.
זה יהיה למעשה לשנות את האלמנט השני של המערך, כי, כזכור,
המספור מתחיל מ 0, לא ב1.
אם אני רוצה לקרוא ערך שאני יכול לומר משהו כמו int x = מערך [1].
או אם אני רוצה לקבוע ערך זה, כמו שאני עושה כאן,
אני יכול לומר מערך [1] = 4.
זה זמן גישה לאלמנטים במדדם
או העמדה או איפה הם נמצאים במערך שלהם,
והרישום שמתחיל ב 0.
אנחנו יכולים גם מערכים של מערכים,
וזה נקרא מערך רב ממדי.
כאשר יש לנו מערך רב ממדי
זה אומר שאנחנו יכולים להיות משהו כמו שורות ועמודות,
וזו רק דרך אחת לדמיין את זה או לחשוב על זה.
כאשר יש לי מערך רב ממדי שאומר שאני הולך למתחיל להזדקק
מדד יותר מ 1, כי אם יש לי רשת
לומר את מה שאתה בשורה פשוט לא נותן לנו מספר.
זה באמת פשוט הולך לתת לנו רשימה של מספרים.
בואו נגיד שיש לי מערך זה כאן.
יש לי מערך נקרא רשת, ואני אומר 2 שורות ועמודות 3 של זה,
ואז זה הוא דרך אחת לדמיין את זה.
כשאני אומר שאני רוצה לקבל את האלמנט ב[ 1] [2]
זה אומר שבגלל שמדוברות בשורות ראשונות ואז עמודות
אני הולך לקפוץ לשורת 1 מאז שאמרתי 1.
>> ואז אני הולך לבוא לכאן לעמודה 2, ואני הולך לקבל את הערך 6.
הפוך תחושה?
מערכים רבים ממדיים, יש לזכור, הם מבחינה טכנית פשוט מערך של מערכים.
יכול להיות לנו מערכים של מערכים של מערכים.
אנחנו יכולים להמשיך, אבל באמת דרך אחת לחשוב על
איך זה שהניח על השולחן ומה שקורה הוא לדמיין אותו
ברשת כזאת.
כאשר אנו עוברים מערכים לפונקציות, הם הולכים להתנהג
קצת שונה מכאשר אנו עוברים משתנים רגילים לפונקציות
כמו עובר int או לצוף.
כאשר אנו עוברים בint או char או כל נתונים אחרים אלה סוגים
אנחנו פשוט לקחנו להסתכל אם הפונקציה משנה
הערך של אותו משתנה שהשינוי לא הולך להפיץ את
לפונקציה הקוראת.
עם מערך, מצד השני, זה לא יקרה.
אם אני עובר במערך לפונקציה מסוימת והפונקציה שמשנה חלק מהרכיבים,
כשאני חוזר לפונקציה שקראה לה
המערך שלי עכשיו הוא הולך להיות שונה, ואת אוצר מילים של
מערכים הוא מועברים על ידי הפניה, כפי שנראים בהמשך.
זה קשור לאופן עבודה של מצביעים, בי סוגי הנתונים בסיסיים אלה,
מצד השני, מועברים על ידי ערך.
>> אנחנו יכולים לחשוב על זה כיצירת עותק של משתנה מסוים ולאחר מכן עובר בהעתקה.
זה לא משנה מה אנחנו עושים עם זה משתנה.
הפונקציה קוראה לא תהיה מודעת לכך שזה היה שונה.
מערכים הם רק קצת שונה בעניין זה.
לדוגמה, כפי שראינו כרגע, עיקרי הוא פשוט פונקציה
זה יכול לקחת ב2 טיעונים.
הטענה הראשונה לתפקידו העיקרי היא argc, או במספר הטיעונים,
והטענה השנייה נקראת argv,
ואלה הם ערכים האמיתיים של טענות אלה.
בואו נגיד שיש לי תכנית בשם this.c,
ואני אומר לעשות את זה, ואני מתכוון להפעיל את זה בשורת הפקודה.
עכשיו לעבור בטיעונים מסוימים לתכנית שלי בשם הזה,
אני יכול לומר משהו כמו. / זה cs 50.
זה מה שאנו מדמיינים דוד לעשות בכל יום במסוף.
אבל עכשיו בתוך הפונקציה העיקרית של תכנית
יש ערכים אלה, ולכן argc הוא 4.
זה יכול להיות קצת מבלבל, כי באמת שאנחנו רק עוברים בהוא cs 50.
זה רק 3.
אך יש לזכור כי המרכיב הראשון של argv או הטענה הראשונה
הוא שמה של הפונקציה עצם.
אז זה אומר שיש לנו 4 דברים כאן,
והאלמנט הראשון הולך להיות. זה /.
וזה יהיה מיוצג כמחרוזת.
אז האלמנטים שנותרו הם מה שהקלדנו באחרי השם של התכנית.
אז רק כהערת אגב, כפי שבוודאי ראינו בpset 2,
זוכר שהמחרוזת של 50 ≠ 50 מספר השלמים.
אז אנחנו לא יכולים להגיד משהו כמו, 'int x = 3 argv.'
>> זה פשוט לא הולך לעשות את התחושה, כי זו מחרוזת, וזה מספר שלם.
אז אם אתם רוצים להמיר בין 2, תזכרו, אנחנו הולכים
יש פונקצית הקסם הזה שנקרא atoi.
שלוקח מחרוזת ומחזיר את המספר השלם מיוצג בתוכה מחרוזת.
אז זה קל לעשות טעות בחידון,
רק מחשבה שזה יהיה באופן אוטומטי את הסוג הנכון.
אבל רק יודע שתמיד יהיו אלה מחרוזות
גם אם המחרוזת מכילה מספר שלם או תו או מצוף בלבד.
אז עכשיו בואו נדבר על זמן ריצה.
כאשר יש לנו את כל אלגוריתמים אלה שעושים את כל הדברים מטורפים האלה,
זה הופך להיות ממש שימושי לשאול את השאלה, "כמה זמן הם לוקחים?"
אנחנו מייצגים את זה עם משהו שנקרא סימון אסימפטוטי.
אז זה אומר ש-- טוב, בואו נגיד שאנו נותנים האלגוריתם שלנו
קצת קלט ממש, ממש, ממש גדול.
ברצוננו לשאול את השאלה, "כמה זמן זה ייקח לנו?
כמה צעדים ייקח האלגוריתם שלנו לרוץ
כפונקציה של גודל הקלט? "
אז הדרך הראשונה שאנו יכולים לתאר את זמן ריצה היא עם גדול O.
וזה זמן הריצה הגרועה ביותר שלנו.
אז אם אנחנו רוצים למיין מערך, ואנחנו נותנים לאלגוריתם שלנו מערך
זה בסדר יורד כאשר זה צריך להיות בסדר עולה,
זה הולך להיות במקרה הגרוע ביותר.
זה הגבול העליון שלנו באורך המרבי של זמן האלגוריתם שלנו ייקח.
מצד השני, Ω זה הולך לתאר את זמן ריצה הטובה ביותר במקרה.
אז אם אנחנו נותנים מערך כבר ממוין לאלגוריתם מיון,
כמה זמן זה ייקח כדי למיין אותו?
וזו, אם כן, מתארת ​​חסם תחתון על זמן ריצה.
אז הנה רק כמה מילים המתארות כמה פעמים רצופות נפוצות.
אלה הם בסדר עולים.
זמן הריצה המהירה ביותר שיש לנו נקרא מתמיד.
>> זה אומר שלא משנה כמה אלמנטים שאנו נותנים האלגוריתם שלנו,
לא משנה כמה גדול הוא המערך שלנו, מיונו
או לעשות כל מה שאנחנו עושים למערך תמיד ייקח את אותה כמות של זמן.
אז אנחנו יכולים לייצג אותו רק עם 1, שהוא קבוע.
נראו גם בזמן ריצת לוגריתמים.
אז משהו כמו חיפוש בינארי הוא לוגריתמים
איפה אנחנו לחתוך את הבעיה בחצי בכל פעם
ואז דברים פשוט להגיע גבוהים יותר משם.
ואם אי פעם אתה כותב O של כל אלגוריתם עצרת,
אתה כנראה לא צריך לשקול את זה כעבודת היום שלך.
כאשר אנו משווים פעמים רצופות זה חשוב לזכור את הדברים האלה.
אז אם יש לי אלגוריתם זה O (n), ומישהו אחר
יש אלגוריתם של O (2n) אלה הם למעשה asymptotically מקבילים.
אז אם אנחנו מדמיינים n להיות מספר גדול כמו eleventy מיליארדים:
לכן כאשר אנו משווים eleventy מיליארדים למשהו כמו מיליארדים eleventy + 3,
פתאום 3 שלא ממש יעשו הבדל גדול יותר.
זו הסיבה שאנחנו הולכים להתחיל שוקלים את הדברים האלה כדי להיות שווים.
אז דברים כמו בקבועים אלה כאן, יש 2 x זה, או להוסיף 3,
אלה הם רק קבועים, ואלה הולכים טיפה למעלה.
אז בגלל זה כל 3 לרוץ הפעמים האלה הם אותו דבר כמו להגיד שהם O (n).
בדומה לכך, אם יש לנו 2 לרוץ פעמים אחרות, תניח O (n ³ + 2n ²), אנו יכולים להוסיף
+ N, + 7, ולאחר מכן יש לנו זמן אחר לרוץ זה רק O (n ³).
שוב, אלה הם אותו דבר, כי אלה - כל אלה הם לא אותו הדבר.
אלה הם אותם הדברים, מצטער. אז אלו הם אותו הדבר כי
³ n זה הולך לשלוט ² 2n זה.
>> מה היא לא אותו דבר הוא שאם יש לנו לרוץ פעמים כמו O (n ³) ו-O (n ²)
בגלל ³ n זה הרבה יותר גדול מזה n ².
אז אם יש לנו מעריכים, פתאום זה מתחיל משנה,
אבל כאשר אנחנו עוסקים רק בגורמים כמו שאנחנו כאן,
אז זה לא ישן דבר, כי הם פשוט הולכים לנשור.
בואו נסתכל על כמה מהאלגוריתמים שראינו עד כה
ומדבר על זמן הריצה שלהם.
הדרך הראשונה של מחפש מספר ברשימה, שראינו, הייתה החיפוש ליניארי.
ויישום החיפוש ליניארי הוא סופר פשוט.
פשוט יש לנו רשימה, ואנחנו הולכים להסתכל על כל אלמנט יחיד ברשימה
עד שאנחנו מוצאים את המספר שאנחנו מחפשים.
אז זה אומר שבמקרה הגרוע ביותר, זה O (n).
והמקרה הגרוע ביותר יכול להיות כאן אם הרכיב הוא
האלמנט האחרון, ולאחר מכן באמצעות חיפוש יניארי אנחנו צריכים להסתכל על כל אלמנט יחיד
עד שנגיע לזה שעבר כדי לדעת שזה היה בעצם ברשימה.
אנחנו לא יכולים פשוט לוותר באמצע הדרך ולומר: "זה כנראה לא שם."
בחיפוש ליניארי שאנחנו צריכים להסתכל על כל העניין.
זמן הרצת המקרה הטוב, לעומת זאת, הוא מתמיד
כי במקרה הטוב ביותר האלמנט שאנחנו מחפשים הוא רק ראשון ברשימה.
אז זה הולך לקחת לנו בדיוק שלב 1, לא משנה כמה גדול היא הרשימה
אם אנחנו מחפשים את האלמנט הראשון בכל פעם.
>> לכן, כאשר אתה מחפש, יש לזכור, היא אינה דורשת כי הרשימה שלנו תהיה מסודרת.
כי אנחנו פשוט הולכים להסתכל על כל אלמנט יחיד, וזה לא ממש משנה
מה סדר אלה הם המרכיבים פנימה
אלגוריתם חיפוש חכם יותר הוא משהו כמו חיפוש בינארי.
זכור, ביצוע החיפוש בינארי הוא כאשר אתה הולך
להמשיך לחפש באמצע הרשימה.
ומכיוון שאנחנו מחפשים באמצע, אנו דורשים שהרשימה ממוינת
או שאנחנו לא יודעים איפה הוא באמצע, ואנחנו צריכים להסתכל על
כל הרשימה כדי למצוא אותו, ולאחר מכן בשלב זה אנחנו רק מבזבזים את הזמן.
אז אם יש לנו רשימה ממוינת ואנו מוצאים את האמצע, אנחנו הולכים להשוות את האמצע
לאלמנט שאנחנו מחפשים.
אם הוא גבוה מדי, ואז אנחנו יכולים לשכוח את המחצית הימנית
כי אנחנו יודעים שאם האלמנט שלנו הוא כבר גבוה מדי
והכל לזכותו של רכיב זה הוא אף גבוה יותר,
אז אנחנו לא צריכים להסתכל לשם יותר.
איפה מצד השני, אם עיקרון היסוד שלנו הוא נמוך מדי,
אנחנו יודעים הכל בצד השמאל של אלמנט שהוא גם נמוך מדי,
אז זה לא ממש הגיוני להסתכל גם שם.
בדרך זו, בכל צעד ובכל פעם שאנחנו מסתכלים על נקודת האמצע של הרשימה,
אנחנו הולכים לחתוך את הבעיה שלנו בחצי כי פתאום אנחנו יודעים
חבורה שלמה של מספרים שלא יכול להיות זה שאנחנו מחפשים.
>> בpseudocode זה היה נראה משהו כזה,
ובגלל שאנחנו חותכים את הרשימה בחצי בכל פעם,
קפיצותינו מקרה הגרוע ביותר זמן הריצה לינארי מוגריתמית.
אז פתאום יש לנו התחברות בצעדים על מנת למצוא אלמנט ברשימה.
זמן הרצת המקרה הטוב ביותר, אם כי, עדיין מתמיד
כי עכשיו, בואו רק נאמר שהאלמנט שאנחנו מחפשים הוא
תמיד האמצע המדויק של הרשימה המקורית.
אז אנחנו יכולים להגדיל את הרשימה שלנו גדול כמו שאנחנו רוצים, אבל אם היסוד שאנחנו מחפשים הוא באמצע,
אז זה רק הולך לקחת אותנו הצעד 1.
אז זאת הסיבה שאנחנו O (logn) וΩ (1) או קבוע.
בואו למעשה להפעיל חיפוש בינארי ברשימה זו.
אז אניח שאנחנו מחפשים את האלמנט 164.
הדבר הראשון שאנחנו הולכים לעשות הוא למצוא את נקודת האמצע של רשימה זו.
זה פשוט כל כך קורה שנקודת האמצע היא עומדת לנפול בין 2 מספרים אלה,
אז בוא רק תגיד באופן שרירותי, בכל פעם לנקודת האמצע נופל בין 2 מספרים,
בואו רק לעגל כלפי מעלה.
אנחנו רק צריכים לוודא שאנחנו עושים את זה בכל שלב של הדרך.
אז אנחנו הולכים לאסוף, ואנחנו הולכים לומר כי 161 הם אמצע הרשימה שלנו.
אז 161 <164, וכל אלמנט בצד השמאל של 161
גם <164, כך שאנחנו יודעים שזה לא הולך לעזור לנו בכל
להתחיל לחפש כאן, כי הגורם שאנחנו מחפשים לא יכולים להיות שם.
אז מה אנחנו יכולים לעשות הוא פשוט יכולים לשכוח שהמחצית השמאלית של כל הרשימה,
ועכשיו רואים רק מזכותו של ואילך 161.
>> אז שוב, זו היא נקודת האמצע, בואו פשוט לעגל כלפי מעלה.
עכשיו 175 הם גדולים מדי.
אז אנחנו יודעים שזה לא יעזור לנו לחפש כאן או לכאן,
ולכן אנחנו יכולים פשוט לזרוק את הכל, וסופו של דבר אנחנו נפגענו 164.
כל שאלה על החיפוש בינארי?
בואו לעבור מחיפוש דרך רשימה ממוינת כבר
למעשה לוקח רשימה של מספרים בכל סדר
ומה שהופך את הרשימה בסדר עולה.
האלגוריתם הראשון שבדקנו נקרא מיון בועות.
וזה יהיה פשוט יותר מהאלגוריתמים שראינו.
מיון בועות אומר שכאשר כל 2 אלמנטים בתוך הרשימה נמצאים מחוץ למקום,
כלומר יש מספר גבוה יותר מהשמאל למספר נמוך יותר,
אז אנחנו הולכים להחליף אותם, כי זה אומר שהרשימה תהיה
"יותר מסודר" ממה שהיה לפני.
ואנחנו פשוט הולכים להמשיך את התהליך הזה שוב ושוב ושוב
עד סופו של דבר הסוג של בועת האלמנטים למיקומם הנכון ויש לנו רשימה ממוינת.
>> זמן הריצה של זה הולך להיות O (n ²). למה?
ובכן, משום שבמקרה הגרוע ביותר, אנחנו הולכים לקחת את כל אלמנטים, ו
אנחנו הולכים בסופו השווה אותו לכל גורם אחר ברשימה.
אבל במקרה הטוב, יש לנו רשימה כבר ממוינת, סוג של בועה
פשוט הולך לעבור פעם אחת, אומרים "לא. אני לא בצעתי חילופים, כך אני עושה."
אז יש לנו זמן הרצת מקרה הטוב של Ω (n).
בואו לרוץ מיון בועות ברשימה.
או ראשון, בואו פשוט להסתכל pseudocode חלק ממש מהר.
אנחנו רוצים להגיד שאנחנו רוצים לעקוב אחר, בכל איטרציה של הלולאה,
לעקוב אחרי האם או לא שינינו את כל אלמנטים.
אז הסיבה לכך הוא, שאנחנו הולכים לעצור כאשר יש לנו לא החלפנו את כל אלמנטים.
אז בתחילת הלולאה שלנו אנחנו לא החלפנו שום דבר, ולכן אנחנו אומרים שזה שקר.
עכשיו, אנחנו הולכים לעבור על הרשימה והשווה אלמנטי לאלמנט אני + 1
ואם זה המקרה שיש מספר גדול יותר בצד השמאל של מספר קטן יותר,
אז אנחנו פשוט הולכים להחליף אותם.
>> ואז אנחנו הולכים לזכור שאנחנו החלפנו אלמנט.
זה אומר שאנחנו צריכים לעבור את הרשימה לפחות פעם 1 יותר
בגלל המצב שבו עצרנו הוא כאשר כל הרשימה כבר ממוינת,
כלומר יש לנו לא עשו שום עסקות חלף.
אז בגלל זה המצב שלנו כאן הוא "תוך כמה אלמנטים שהוחלפו. '
אז עכשיו בואו נראה את זה רץ על רשימה.
יש לי רשימה 5,0,1,6,4.
מיון בועות עומד להתחיל את כל הדרך בשמאל, וזה הולך להשוות
אלמנטים ש, כך 0 עד ש+ 1, שהוא האלמנט 1.
זה הולך לומר, גם 5> 0, אבל כרגע 5 הם לשמאל,
אז אני צריך להחליף 5 ו 0.
כשאני מחליף אותם, ופתאום אני מקבל רשימה אחרת זה.
עכשיו 5> 1, אז אנחנו הולכים להחליף אותם.
5 הן לא> 6, ולכן אנחנו לא צריכים לעשות שום דבר כאן.
אבל 6> 4, כך שאנחנו צריכים להחליף.
שוב, אנחנו צריכים לרוץ דרך כל רשימת סופו של דבר לגלות
כי אלה הם מחוץ לסדר; להחליף אותם,
ובשלב זה אנחנו צריכים לרוץ דרך הרשימה 1 יותר זמן
כדי לוודא שהכול בשליטתה, ובמיון בועות שלב זה כבר הסתיים.
אלגוריתם שונה ללוקחים כמה אלמנטים ומיונם הוא מיון בחירה.
הרעיון מאחורי מיון בחירה הוא שאנחנו הולכים לבנות את חלק ממוין של הרשימה
אלמנט 1 בכל פעם.
>> והדרך שאנחנו הולכים לעשות את זה היא על ידי בניית הקטע השמאלי של הרשימה.
ובעצם, בכל - בכל שלב, אנחנו הולכים לקחת את היסוד הקטן ביותר שנשארנו לנו
שלא מוין עדיין, ואנחנו הולכים להעביר אותו לאותו מגזר מיון.
זה אומר שאנחנו צריכים ברציפות כדי למצוא את האלמנט הממוין המינימום
ואז לקחת אותו האלמנט מינימאלי ולהחליף אותו עם כל מה
השמאלי ביותר אלמנט שאינו ממוין.
זמן הריצה של זה הולך להיות O (n ²), כי במקרה הגרוע ביותר
אנו צריכים להשוות כל אלמנט בודד לכל גורם אחר.
בגלל שאנחנו אומרים שאם נתחיל במחצית השמאלית של הרשימה, אנחנו צריכים
כדי לעבור את הקטע הנכון כל למצוא את היסוד הקטן ביותר.
ואז, שוב, אנחנו צריכים ללכת על המגזר כולו וזכות
להמשיך ללכת על זה שוב ושוב ושוב.
זה הולך להיות ² n. אנחנו הולכים לצריכים בתוך לולאה אחרת ללולאה
אשר טוען ² n.
במקרה הטוב ביותר המחשבה, אניח שאנחנו נותנים לו רשימה כבר מסודרת;
אנחנו באמת לא עושים יותר טוב מ² n.
בגלל מיון בחירה אין דרך לדעת ש
המרכיב המינימאלי הוא רק אחד אני במקרה מסתכל.
זה עדיין צריך לוודא שזה הוא למעשה המינימום.
>> והדרך היחידה לוודא שזה המינימום, באמצעות אלגוריתם זה,
הוא להסתכל על כל אלמנט בודד שוב.
אז באמת, אם אתה נותן לו - אם אתה נותן לי מיון בחירת רשימה כבר ממוינת,
זה לא הולך לעשות יותר טוב מאשר לתת אותו ברשימה שאינו ממוינת עדיין.
דרך אגב, אם זה קורה להיות המקרה שמשהו הוא O (משהו)
והאומגה של משהו, אנחנו יכולים רק לומר באופן תמציתי יותר שזה θ של משהו.
אז אם אתה רואה שעולה בכל מקום, זה מה שרק אומר.
>> אם משהו הוא תטא של n ², זה גם גדול O (n ²) וΩ (n ²).
אז במקרה הטוב ביותר ומקרה הגרוע ביותר, זה לא עושה את הבדל,
האלגוריתם הוא הולך לעשות את אותו הדבר כל זמן.
אז זה מה שpseudocode למיון בחירה יכולה להיראות כך.
אנו בעצם הולכים להגיד שאני רוצה לחזר על הרשימה
משמאל לימין, ובכל איטרציה של הלולאה, אני הולך לעבור
המרכיב המינימאלי לחלק מסודר זו של הרשימה.
וברגע שאני מזיז שם משהו, אני לא צריך להסתכל על אותו האלמנט שוב.
כי ברגע שאני מחליף אלמנט במגזר השמאל של הרשימה, זה מסודר
בגלל שאנחנו עושים הכל בסדר עולה באמצעות מינימום.
אז אמר, בסדר, אנחנו בעמדתי, ואנחנו צריכים להסתכל על כל האלמנטים
בצד הימין שלי כדי למצוא את המינימום.
אז זה אומר שאנחנו רוצים לראות מאני + 1 לסוף הרשימה.
ועכשיו, אם היסוד שאנחנו כרגע מסתכלים עליה הוא פחות מהמינימום שלנו עד כה,
אשר, יש לזכור, אנחנו מתחילים מהמינימום רק כדי להיות
כל אלמנט שאנחנו כרגע ב; אני מניח שזה המינימום.
אם אני מוצא את אלמנט שהוא קטן יותר מזה, אז אני הולך להגיד, בסדר,
כן, מצאתי מינימום חדש.
אני הולך לזכור היכן שהיה מינימאלי.
>> אז עכשיו, ברגע שעברתי עליי שהקטע הממוין הנכון,
אני יכול להגיד שאני הולך להחליף את האלמנט המינימאלי עם האלמנט שהוא בעמדתי.
זה הולך לבנות את הרשימה שלי, החלק שלי מסודר ברשימה משמאל לימין,
ואנחנו אף פעם לא צריכים להסתכל על אלמנט שוב ​​פעם אחת היה זה באותו חלק.
ברגע שהחלפנו אותה.
אז בואו לרוץ מיון בחירה ברשימה זו.
האלמנט הכחול כאן הולך להיות אני, והאלמנט האדום הולך להיות המרכיב המינימאלי.
אז אני מתחיל את כל הדרך בצד השמאל של הרשימה, כך בשעת 5.
עכשיו אנחנו צריכים למצוא את האלמנט הממוין המינימום.
אז אנחנו אומרים 0 <5, ולכן 0 הם המינימום החדש שלי.
>> אבל אני לא יכול לעצור שם, כי אף על פי שאנו יכולים להכיר בכך ש0 הוא הקטן ביותר,
אנחנו צריכים לרוץ דרך כל אלמנט אחר של הרשימה כדי לוודא.
אז 1 הוא גדול יותר, 6 הם גדולים יותר, 4 הם גדולים יותר.
זה אומר שאחרי שמסתכל על כל המרכיבים האלה, אני כבר נקבעתי 0 הוא קטן ביותר.
אז אני הולך להחליף 5 ו 0.
ברגע שאני מחליף את זה, אני הולך לקבל רשימה חדשה, ואני יודע שאני לא צריך להסתכל על זה שוב 0
כי ברגע שהחלפתי אותה, שאסדיר את זה ואנחנו נעשינו.
עכשיו זה פשוט כל כך קורה כי האלמנט הכחול הוא שוב 5,
ואנחנו צריכים להסתכל על 1, 6 ו 4 כדי לקבוע כי 1
הוא האלמנט המינימאלי הקטן ביותר, ולכן אנחנו להחליף 1 ו 5.
שוב, אנחנו צריכים להסתכל על - להשוות 5 עד 6 ו 4,
ואנחנו הולכים להחליף 4 ו 5, ולבסוף, להשוות
2 המספרים האלה ולהחליף אותם עד שנקבל הרשימה הממוינת שלנו.
כל שאלות על מיון בחירה?
אוקיי. בואו נעבור לנושא האחרון כאן, וזה רקורסיה.
>> רקורסיה, יש לזכור, היא באמת הדבר הזה שבו המטא פונקציה
קורא שוב ושוב את עצמו.
אז בשלב מסוים, בעוד fuction שוב ושוב הוא קורא את עצמו,
צריך שתהיה איזו נקודה שבה אנו קוראים להפסיק את עצמנו.
כי אם אנחנו לא עושים את זה, אז אנחנו פשוט הולכים להמשיך לעשות זאת לנצח,
והתכנית שלנו היא פשוט לא הולכת להפסיק.
אנחנו קוראים למצב זה מקרה הבסיס.
ומקרה הבסיס אומר, ולא קוראים לפונקציה שוב,
אני רק הולך להחזיר ערך כלשהו.
אז ברגע שאנחנו חוזרים ערך, הפסיק לקרוא לעצמנו,
ואת שאר השיחות שעשינו עד כה יכול גם לחזור.
ההפך ממקרה הבסיס הוא המקרה רקורסיבית.
וזה כאשר אנו רוצים לבצע שיחה נוספת לפונקציה שאנחנו כרגע פנימה
ואנחנו כנראה, אם כי לא תמיד, רוצים להשתמש בטיעונים שונים.
>> אז אם יש לנו פונקציה שנקראת f, ו f פשוט נקראת לקחת את הטיעון 1,
ואנחנו רק להמשיך לקרוא f (1), f (1), f (1), וזה פשוט כל כך קורה כי
טענת 1 נופלת לתוך מקרה רקורסיבית, אנחנו עדיין לא מתכוונים לעצור.
גם אם יש לנו מקרה בסיס, אנחנו צריכים לוודא שסופו של דבר אנחנו הולכים להכות מקרה זה בסיס.
אנחנו לא רק לשמור על ההישארות במקרה זה רקורסיבית.
בדרך כלל, כאשר אנו מכנים את עצמנו, אנחנו כנראה הולכים להיות ויכוח שונה בכל פעם.
הנה פונקציה רקורסיבית ממש פשוט.
אז זה יהיה לחשב את העצרת של מספר.
למעלה כאן יש לנו מקרה הבסיס שלנו.
במקרה שn ≤ 1, אנחנו לא מתכוון לקרוא לעצרת שוב.
אנחנו הולכים להפסיק, אנחנו פשוט הולכים להחזיר ערך כלשהו.
אם זה לא נכון, אז אנחנו הולכים להכות המקרה רקורסיבית שלנו.
שימו לב כאן שאנחנו לא רק להתקשר לעצרת (n), בגלל שלא יהיו מאוד מועיל.
אנחנו הולכים לקרוא לעצרת של משהו אחר.
>> וכדי שתוכל לראות, בסופו אם אנחנו עוברים משהו עצרת (5) או,
אנחנו הולכים לקרוא לעצרת (4) וכן הלאה, וסופו של דבר אנחנו הולכים להכות מקרה בסיס זה.
אז זה נראה טוב. בואו נראה מה קורה כאשר אנו למעשה להפעיל את זה.
זה הערימה, ונניח שעיקריים עומד לקרוא בפונקציה זו עם טענה (4).
אז ברגע שרואה את העצרת ו= 4, עצרת תהיה שיחה עוצמה.
עכשיו, פתאום, יש לנו עצרת (3).
אז הפונקציות האלה הולכים להמשיך לגדול עד שלבסוף פגענו מקרה הבסיס שלנו.
בשלב זה, את ערך ההחזרה של זה הוא התשואה (ערך ההחזרה של זה NX),
ערך ההחזרה של זה nx ערך ההחזרה של זה.
סופו של דבר אנחנו צריכים להכות חלק המספר.
בראש כאן, אנחנו אומרים בתמורה 1.
זה אומר שברגע שאנחנו חוזרים מספר זה, אנחנו יכולים לפוצץ זה את המחסנית.
אז זה עצרת (1) נעשה.
כשחוזר 1, (1) חוזר פקטוריאליים זה, ההחזרה ל1.
ערך ההחזרה של זה, יש לזכור, היה nx ערך ההחזרה של זה.
אז פתאום, הבחור הזה יודע שאני רוצה לחזור 2.
>> אז תזכור, להחזיר ערך של זה הוא פשוט nx ערך ההחזרה לכאן.
אז עכשיו אנחנו יכולים להגיד 3 X 2, ולבסוף, כאן אנו יכולים לומר
זה פשוט הולך להיות 4 x 3 x 2.
וברגע שחוזר זה, שניגשנו לבתוך שלם אחד עיקרי.
כל שאלות ברקורסיה?
בסדר. אז יש עוד זמן לשאלות בסוף,
אבל עכשיו יוסף יכסה את הנושאים שנותרו.
>> [יוסף אונג] בסדר. אז עכשיו שאנחנו כבר דברנו על recursions,
בואו נדבר קצת על מה הוא למזג מיון.
סוג המיזוג הוא בעצם דרך נוספת למיון רשימת המספרים.
ואיך זה עובד היא, עם סוג המיזוג יש לך רשימה, ומה שאנחנו עושים הם
אנחנו אומרים, בואו פיצול זה ל 2 חצי.
אנו נפעיל 1 למזג מיון שוב בחלק השמאלי,
אז להפעיל למזג מיון בחצי הימני,
וזה נותן לנו עכשיו 2 חצי הממוינים, ועכשיו אנחנו הולכים לשלב חצאים אלה יחד.
זה קצת קשה לראות בלי דוגמה, אז אצטרך לעבור את התנועות ולראות מה קורה.
אז אתה מתחיל עם רשימה זו, אנו לפצל אותו ל 2 חצי.
אנחנו רצים למזג מיון בחלק השמאלי ראשון.
אז זה את חלקו השמאלי, ועכשיו אנחנו מריצים אותם דרך רשימה זו שוב
אשר מקבל עבר למעין מיזוג, ולאחר מכן אנחנו נראים, שוב,
בצד השמאל של רשימה זו ואנחנו רצים למזג מיון על זה.
עכשיו, אנחנו ניגשים לרשימה של 2 מספרים,
ועכשיו את חלקו השמאלי הוא האלמנט היחיד 1 זמן, ואנחנו לא יכולים
פיצול רשימה שרק 1 גורם למחצית, אז אנחנו פשוט אומרים, ברגע שיש לנו 50,
וזה רק אלמנט 1, זה כבר מסודר.
>> ברגע שנסיים עם זה, אנו יכולים לראות שאנחנו יכולים
לעבור למחצית הימנית של רשימה זו,
ו 3 גם הם מסודר, ואז עכשיו ששני החצאים של רשימה זו מסודרים
אנחנו יכולים להצטרף למספרים האלה בחזרה.
אז אנחנו מסתכלים 50 ו 3; 3 הם קטנים יותר מ 50, כך שהוא נכנס ראשון ולאחר מכן 50 נכנס
עכשיו, שזה נעשה, אנחנו חוזרים לאותה רשימה וסוג זה חצי נכון.
42 הם מספר משלו, כך שזה כבר נפתר.
אז עכשיו אנחנו להשוות אלה 2 ו 3 קטנים מ 42, כך שמקבל לשים בראשון,
היום בן 42 מקבל את שלו ובמקבל 50 מכניסים פנימה
עכשיו, זה מסודר, אנחנו הולכים את כל הדרך חזרה לחלק העליון, 1337 ו 15.
ובכן, עכשיו אנחנו מסתכלים על חיצו השמאלי של רשימה זו; 1337 הן על ידי עצמו, כך שהוא מסודר ואותו דבר עם 15.
אז עכשיו אנחנו משלבים 2 המספרים האלה כדי למיין שרשימה מקורית, 15 <1337,
כך זה ממשיך בראשון, אז 1337 הולכים פנימה
ועכשיו אנחנו מסודרים שני החצאים של הרשימה המקורית למעלה.
וכל מה שאנחנו צריכים לעשות הוא לשלב אלה.
אנחנו מסתכלים על 2 המספרים הראשונים של רשימה זו, 3 <15, כך זה נמשך לתוך מערך הסוג ראשון.
15 <42, כך שזה נכנס עכשיו, 42 <1337, שהולך פנימה
50 <1337, כך שזה נכנס ושמים לב שאנחנו רק לקחנו את 2 מספרים של רשימה זו.
אז אנחנו לא רק לסירוגין בין 2 הרשימות.
אנחנו פשוט מחפשים בהתחלה, ואנחנו לוקחים את האלמנט
זה קטן יותר ולאחר מכן לשים אותו לתוך המערך שלנו.
עכשיו אנחנו כבר התמזגנו כל המחציות ואנחנו נעשינו.
>> שאלות לגבי למזג מיון? כן?
[סטודנטים] אם זה התפצלות לקבוצות שונות, למה הם לא רק לפצל אותו פעם אחת
ויש לך 3 ו 2 בקבוצה? [שאר מובן שאלה]
הסיבה - אז השאלה היא, למה אנחנו לא יכולים פשוט למזג אותם בצעד הראשון שאחרי יש לנו אותם?
הסיבה שאנחנו יכולים לעשות את זה, להתחיל בשמאל רוב האלמנטים של שני הצדדים,
ואז לקחת את אחד הקטן ולשים אותו ב, הוא שאנו יודעים אלה ש
רשימות בודדות הן בהזמנות ממוינות.
אז אם אני מסתכל על שמאל רוב האלמנטים של שני חצי,
אני יודע שהם הולכים להיות האלמנטים הקטנים ביותר של רשימות אלה.
אז אני יכול להכניס אותם לנקודתי היסוד הקטנות ביותר של הרשימה גדולה הזאת.
מצד השני, אם אני מסתכל על 2 הרשימות האלה ברמה השנייה שם,
50, 3, 42, 1337 ו 15, אלה אינם ממוינים.
אז אם אני מסתכל על 50 ו1337, אני הולך לשים 50 לרשימה שלי ראשון.
אבל זה לא ממש הגיוני, כי 3 הם הרכיב הקטן ביותר מתוך כל אלה.
אז הסיבה היחידה שאנחנו יכולים לעשות צעד זה בגלל שילוב של הרשימות שלנו כבר מסודרות.
וזו הסיבה שיש לנו כדי לקבל את כל הדרך עד לתחתית
כי כאשר יש לנו רק מספר אחד, אתה יודע שמספר בודד
בפני עצמו הוא כבר רשימה ממוינת.
>> יש שאלות? לא?
מורכבות? ובכן, אתה יכול לראות את זה בכל שלב יש מספרים סופיים,
ואנחנו יכולים לחלק את רשימה ביומן 1/2 n פעמים,
המקום שבו אנחנו מקבלים יומן זה n x n מורכבות.
ותראה במקרה הטוב לסוג המיזוג הוא n log n, וזה פשוט כל כך קורה
שהמקרה הגרוע ביותר, או Ω שם, גם n log n.
משהו שכדאי לזכור.
ההעברה ב, בואו נלך לחלק הקובץ בסיסי Super I / O.
אם היית מסתכל על מירוץ, תוכל להבחין שיש לנו סוג מסוים של מערכת
שבו אתה יכול לכתוב לקובץ יומן אם אתה קורא את הקוד.
בואו לראות איך אפשר לעשות את זה.
ובכן, יש לנו fprintf, שאתה יכול לחשוב עליו כפשוט printf,
אבל פשוט מדפיס לקובץ במקום, ולכן f בהתחלה.
סוג של קוד זה לכאן, מה שהיא עושה הוא, כפי שאולי ראה במירוץ,
הוא עובר הדפסת המערך 2-הממדית שלכם את השורה אחרת השורה מה המספרים.
במקרה זה, printf מדפיס למסוף שלך או מה שאנו מכנים את הפלט הסטנדרטי של סעיף.
>> ועכשיו, במקרה זה, כל מה שאנחנו צריכים לעשות הוא להחליף את printf עם fprintf,
אומר לו מה קובץ שאתה רוצה להדפיס, ובמקרה הזה זה פשוט מדפיס אותו כדי שהקובץ
במקום להדפיס אותו למסוף שלך.
טוב, אז שמעלה את השאלה: איפה אנחנו מקבלים את זה סוג של קובץ מ, נכון?
עברנו להיכנס לfuction fprintf זה אבל לא היה לנו מושג מהאיפה זה בא.
ובכן, בשלב המוקדם של הקוד, מה שהיינו לנו היה זה נתח של קוד לכאן,
אשר בעצם אומר שפתוח קובץ שיחות Log.Txt.
מה שאנחנו עושים אחרי שיש לנו הוא לוודא שהקובץ נפתח ממש בהצלחה.
אז זה עלול להיכשל מסיבות רבות, אין לך מספיק מקום במחשב שלך, למשל.
אז זה תמיד חשוב לפני שאתה עושה את כל פעולות עם הקובץ
שאנחנו בודקים אם הקובץ שנפתח בהצלחה.
אז מה ש, זה טיעון לfopen, ובכן, אנחנו יכולים לפתוח תיק בדרכים רבות.
מה אנחנו יכולים לעשות, אנחנו יכולים להעביר את זה w, כלומר לעקוף את הקובץ אם יציאתו כבר,
אנחנו יכולים לעבור, שהם יצורפו לסוף של הקובץ במקום דריסתו,
או שאנחנו יכולים לציין r, מה שאומר, בואו לפתוח את הקובץ לקריאה בלבד.
אז אם התכנית מנסה לבצע שינויים בקובץ,
צועק עליהם ולא נותנים להם לעשות את זה.
לבסוף, לאחר שנסיים עם הקובץ, תסיים עושה פעולות עליו,
אנחנו צריכים לוודא שאנחנו סוגרים את הקובץ.
וכך בסוף התכנית שלך, אתה הולך לעבור אותם שוב
זה קובץ שנפתחת, ופשוט לסגור אותו.
אז זה משהו חשוב שאתה צריך לוודא שאתה עושה.
אז זכור שאתה יכול לפתוח את קובץ, ואז אתה יכול לכתוב לקובץ,
לעשות פעולות בתיק, אבל אז אתה צריך לסגור את התיק בסוף.
>> כל שאלות בקובץ בסיסי קלט / פלט? כן?
[שאלת סטודנט, לא מובן]
ממש כאן. השאלה היא, איפה קובץ זה מופיע Log.Txt?
ובכן, אם אתה רק נותן לו Log.Txt, הוא יוצר אותו באותה הספרייה כמו קובץ ההפעלה.
אז אם אתה - >> [שאלת סטודנט, לא מובן]
כן. באותה התיקייה, או באותה ספרייה, כפי שאתה קורא לזה.
עכשיו זיכרון, מחסנית, וערימה.
אז איך הוא זיכרון שהותווה במחשב?
ובכן, אתה יכול לדמיין את הזיכרון כסוג של הבלוק הזה כאן.
ובזיכרון שיש לנו מה שנקרא הגל תקועים שם, והמחסנית שנמצאה שם.
והערימה גדלה כלפי מטה והמחסנית גדלה כלפי מעלה.
אז כפי שהוזכר טומי - הו, כן, ויש לנו 4 מקטעים אלה אחרים שאני אגיע לשני -
כשטומים אמרו קודם, אתה יודע איך קוראים לעצמם התפקידים וקוראים אחד לשני?
הם בונים את המסגרת מסוג כזה מחסנית.
ובכן, אם foo שיחות עיקריות, foo מקבל לשים על הערימה.
Foo קורא בר, בר לקבל נלבשנו את המחסנית, ושמקבל לשים על הערימה לאחר.
וכשהם חוזרים, הם כל אחד מאתנו לקחו את המחסנית.
מה כל אחד מהמקומות הללו וזיכרון להחזיק?
ובכן, העליון, שהנו מגזר הטקסט, מכיל את התכנית עוצמה.
אז את הקוד המכונה, ששם, ברגע שאתה לקמפל את התכנית שלך.
בשלב הבא, כל אותחלו משתנים גלובליים.
>> אז יש לך משתנה גלובלי בתכנית שלך, ואתה אומר כמו, = 5,
שמקבל לשים במגזר זה, וממש מתחת לזה,
יש לך את כל נתונים מאותחלים גלובליים, אשר רק int,
אבל אתה לא אומר שזה שווה משהו.
מבין אלה הם משתנים גלובליים, ולכן הם מחוץ לראשיים.
אז זה אומר שכל משתנים גלובליים שהוכרזו אך לא אותחלו.
אז מה יש בערימה? זיכרון שהוקצה באמצעות malloc, אשר יגיע לקצת.
ולבסוף, עם המחסנית יש לך משתנים מקומיים
וכל פונקציות שאפשר לקרוא בכל הפרמטרים.
הדבר האחרון, אתה לא באמת צריך לדעת מה את משתני הסביבה לעשות,
אבל בכל פעם שאתה מפעיל תכנית, יש משהו הקשור, כמו
זה הוא שם המשתמש של האדם שנהל את התכנית.
וזה הולך להיות סוג של בתחתית.
במונחים של כתובות זיכרון, שהם ערכים הקסדצימליים של,
הערכים בתחילה העליונה ב 0, והם הולכים את כל הדרך עד לתחתית.
במקרה זה, אם אתה על המערכה 32-bit,
הכתובת בתחתית הולכת להיות 0x, ואחרי af, כי זה 32 סיבי,
אשר הם 8 בתים, ובמקרה זה 8 בתים מתאימים ל8 ספרות הקסדצימליים.
אז פה אתה הולך, משהו כמו, 0xffffff, ושם למעלה אתה הולך יש 0.
אז מה הם מצביע? חלק מכם אולי לא כיסה את זה בסעיף קודם.
אבל אנחנו לא נעבור על זה בהרצאה, כך מצביע הוא בדיוק סוג נתונים
אילו חנויות, במקום איזשהו ערך כמו 50, הוא מאחסן את הכתובת של מיקום מסוים בזיכרון.
כמו שהזיכרון [לא מובן].
אז במקרה הזה, מה שיש לנו הוא, שיש לנו מצביע למספר שלם או * int,
והוא מכיל את כתובה הקסדצימלי זה של 0xDEADBEEF.
>> אז מה יש לנו הוא, עכשיו, הצביע מצביע זה במיקום מסוים בזיכרון,
וזה בדיוק, הערך 50 הוא במיקום בזיכרון הזה.
בחלק מהמערכות של 32-bit, בכל המערכות של 32-bit, מצביעים לקחת עד 32 סיביים או 4 בתים.
אבל, לדוגמה, על מערכה 64-bit, מצביעים הם 64 סיביים.
אז זה משהו שאתה רוצה לזכור.
אז בסופו של דבר מערכת סיבית, מצביע הוא פיסות קצה ארוך.
מצביעים הם מסוג שקשה לעכל בלי דברים מיותרים,
אז בואו נעבור על דוגמה של הקצאת זיכרון דינמית.
הקצאת זיכרון דינמית מה עושה לך, או מה שאנו מכנים malloc,
זה מאפשר לך להקצות איזה נתונים מחוץ לסט.
אז נתון זה הוא סוג של יותר קבוע במשך תקופת התכנית.
כי כפי שאתה יודע, אם אתה מצהיר x בתוך של פונקציה והפונקציה שמחזירה,
אין לך יותר גישה לנתונים שאוחסנו בx.
מה מצביעים תנו לנו לעשות הוא שהם נותנים לנו לאחסן ערכי זיכרון או בחנות
בקטע אחר של זיכרון, כלומר הערימה.
עכשיו ברגע שנחזור מפונקציה, כל עוד יש לנו מצביע
למיקום זה בזיכרון, ואז מה שאנחנו יכולים לעשות זה אנחנו יכולים רק להסתכל על הערכים שם.
בואו נסתכל על דוגמה: זוהי פריסת הזיכרון שלנו שוב.
ויש לנו בפונקציה זו, עיקרי.
מה שהוא עושה זה - בסדר, כל כך פשוט, נכון -? Int x = 5, זה רק משתנה במחסנית בראשית.
>> מצד השני, עכשיו אנחנו מצהירים מצביע שקורא את giveMeThreeInts הפונקציות.
ואז עכשיו אנחנו נכנסים לפונקציה זו ואנו יוצרים מסגרת מחסנית חדשה עבורו.
עם זאת, במסגרת מערך זה, אנו מצהירים * int temp,
אשר ב3 מספרים שלמים mallocs עבורנו.
אז הגודל של int ייתן לנו כמה בתי int זה,
וmalloc נותן לנו שבתים רבים של החלל בערמה.
אז במקרה הזה, יצר מספיק מקום עבור 3 מספרים שלמים,
והערימה היא דרך לשם, וזו הסיבה שאני נמשך זה למעלה.
ברגע שנסיים, אנחנו חוזרים לכאן, אתה צריך רק 3 ints חזר,
וזה מחזיר את הכתובת, במקרה זה שבו על זיכרון זה.
ואנו קובעים מצביע = מתג, ושם יש לנו רק מצביע אחר.
אבל מה שמחזיר פונקציה הוא נערם כאן ונעלם.
אז טמפ נעלם, אבל אנחנו עדיין לשמור את הכתובת שבי
3 השלמים האלה הם פנימיים של רשת חשמל.
אז בקבוצה הזאת, המצביעים הם scoped מקומי למסגרת המוערמת,
אבל הזיכרון שאליו הם מתייחסים הוא בערימה.
>> האם זה הגיוני?
[סטודנטים] האם אתה יכול לחזור על זה? >> [יוסף] כן.
אז אם אני חוזר רק קצת, אתה רואה שטמפ הוקצה
כמה זיכרון על הערימה שם למעלה.
לכן, כאשר בפונקציה זו, giveMeThreeInts חזרות, מחסנית זה כאן הולכת להיעלם.
ועם זה אף אחד מהמשתנים, במקרה זה, מצביע זה שהוקצה במסגרת מוערמת.
כי הוא הולך להיעלם, אבל מאז שחזרנו טמפ
ואנו קובעים מצביע = temp, מצביע כעת הולך להושיט אותו הזיכרון של מיקום כזמני היה.
אז עכשיו, למרות שאנחנו מאבדים זמניים, שמצביע מקומי,
אנחנו עדיין שומרים את כתובת הזיכרון של מה שהיה מצביע על חלק פנימי של שהמצביע משתנה.
שאלות? זה יכול להיות סוג של נושא מבלבל אם לא עבר על זה בסעיף.
אנחנו יכולים, TF שלך בהחלט ללכת על זה וכמובן שאנחנו יכולים לענות על שאלות
בסיומה של פגישת הביקורת על כך.
אבל זה סוג של נושא מורכב, ויש לי עוד דוגמאות, כי הם הולכים להופיע
שיעזרו להבהיר את מה שהמצביעים בפועל.
>> במקרה זה, מצביעים הם שווים ערך למערכים,
אז אני פשוט יכול להשתמש בזה כמצביע אותו הדבר כמו מערך int.
אז אני לאינדקס 0, ושינוי המספר השלם הראשון ש1,
שינוי המספר שלם 2 ל 2, והמספר השלם 3 עד 3.
נוסף על כך מצביעים. ובכן, זוכר בינקי.
במקרה זה יש לנו הוקצה מצביע, או שהכרזנו מצביע,
אבל בהתחלה, כשרק הצהרתי מצביע, זה לא מצביע על כל מקום בזיכרון.
זה רק ערכי זבל שבתוכה.
אז אין לי מושג איפה זה מצביע כדי להצביע.
יש כתובת שפשוט מלאה בספרות 0 ו 1 של במקום בו היה מוצהר.
אני לא יכול לעשות שום דבר עם זה עד שאני קורא על זה malloc
ואז זה נותן לי מעט מקום על הערימה שבו אני יכול לשים את הערכים פנימה.
אז שוב, אני לא יודע מה יש בפנים בזיכרון הזה.
אז הדבר הראשון שצריך לעשות הוא לבדוק אם המערכת הייתה מספיק זיכרון
שיחזיר לי שלם 1 במקום הראשון, ולכן אני עושה את זה לבדוק.
אם המצביע הוא ריק, זה אומר שזה לא היה לי מספיק מקום או איזו שגיאה אחרת התרחשה,
אז אני צריך לצאת מהתכנית שלי.
אבל אם זה יצליח, עכשיו אני יכול להשתמש במצביע כי
ומה מצביע * עושה זה כדלקמן בי הכתובת היא
למקום שבו הערך, והיא מגדירה אותו שווה ל 1.
אז הנה, אנחנו בודקים אם זיכרון שהיה קיים.
>> ברגע שאתה יודע שהוא קיים, אתה יכול להשקיע בזה
מה ערך שאתה רוצה להכניס אותו, ובמקרה זה 1.
ברגע שנסיים עם זה, אתה צריך לשחרר שמצביע
כי אנחנו צריכים לחזור למערכת שהזיכרון שבקשת במקום הראשון.
משום שהמחשב לא יודע מתי שנסיים עם זה.
במקרה זה אנחנו במפורש אומרים לה, בסדר, אנחנו גמרנו עם זה זיכרון.
אם חלק תהליך אחר צריך את זה, תכנית אחרת צריכה את זה, ירגיש חופשי ללכת קדימה ולקחת אותו.
מה שאנו כן יכולים לעשות הוא פשוט יכולים לקבל את הכתובת של משתנים מקומיים על הסט.
x אז int הוא בתוך המסגרת של ערמה ראשי.
וכאשר אנו משתמשים אמפרסנד זה, והמפעיל, מה שהוא עושה הוא
זה לוקח x, ו-x הוא רק כמה נתונים בזיכרון, אבל יש לו כתובת.
זה נמצא איפשהו. זאת על ידי הקריאה וx, מה המשמעות של זה הוא שזה נותן לנו את הכתובת של x.
בעשותם זאת, אנחנו עושים את הנקודה מצביעה לכאשר x הוא בזיכרון.
עכשיו אנחנו פשוט משהו כמו * x, אנחנו הולכים לקבל בחזרה 5.
הכוכב נקרא ביטול הפניה זה.
אתה עוקב כתובת ואתה מקבל את הערך שלו מאוחסן שם.
>> יש שאלות? כן?
[סטודנטים] אם אתה לא עושה את הדבר 3-המחודד, זה עדיין לקמפל?
כן. אם אתה לא עושה את הדבר 3-המצביע, זה עדיין הולך להדר,
אבל אני אראה לך מה קורה ברגע אחד, ובלי לעשות את זה,
זה מה שאנו מכנים דליפת זיכרון. את לא נותן למערכת
לגבות את הזיכרון שלה, ולכן לאחר זמן שהתכנית הולכת לצבור
הזיכרון שהוא לא משתמש, ושום דבר אחר לא יכול להשתמש בו.
אם אי פעם ראה אתר על 1.5 מיליון ק"ג במחשב שלך,
במנהל המשימות, זה מה שקורה.
יש לך דליפת זיכרון בתכנית שהם לא מטפלים.
אז איך עושה את מצביע עבודת חשבון?
ובכן, חשבון מצביע הוא סוג של אינדוקס כמו במערך.
במקרה זה, יש לי מצביע, ומה שאני עושה זה להפוך את הנקודה של מצביע על הרכיב הראשון
מזה מערך של 3 מספרים שלמים, כי אני כבר הוקציתי לה.
אז עכשיו מה שאני עושה, מצביע כוכב רק משנה את המרכיב הראשון ברשימה.
כוכב מצביע +1 נקודות כאן.
אז מצביע הוא כאן, המצביע +1 הוא כאן, מצביע 2 נגמר כאן.
>> אז רק מוסיף 1 הוא אותו הדבר כמו נע לאורך מערך זה.
מה שאנחנו עושים הוא, כאשר אנחנו עושים מצביע 1 אתה מקבל את הכתובת לכאן,
וכדי לקבל את הערך לכאן, אתה שם כוכב בכל הביטוי
לdereference.
לכן, במקרה זה, אני מגדיר את המיקום הראשון במערך זה ל1,
מיקום שני ל 2, ומיקום שלישי 3.
אז מה אני עושה כאן הוא שאני מדפיס מצביענו +1,
שרק נותן לי 2.
עכשיו אני הגדלת מצביע, ולכן שווה מצביע מצביע +1,
שמעביר אותו קדימה.
ואז עכשיו אם אני מדפיס את המצביע +1, מצביע +1 הוא כעת 3,
אשר במקרה זה יודפס 3.
וכדי לקבל משהו חינם, המצביע שאני נותן לו
יש הצבעה בתחילת המערך שחזרתי מmalloc.
לכן, במקרה זה, אם היינו קורא 3 ממש כאן, זה לא יהיה נכון,
בגלל שזה באמצע של המערך.
אני צריך לחסר כדי להגיע למיקום המקורי
המקום הראשון הראשוני לפני שאני יכול לשחרר אותו.
אז, הנה דוגמה מורכבת יותר.
במקרה זה, אנחנו הקצאת 7 תווים במערך תווים.
>> ובמקרה הזה מה שאנחנו עושים הוא שאנחנו לולאות מעל 1 6 מהם,
ואנחנו הגדרתם 'עד ת'
לכן, עבור int i = 0, i> 6, אני + +,
אז, מצביע + אני פשוט נותן לנו, במקרה זה,
מצביע, +1 מצביע, +2 מצביע, +3 מצביע, וכן הלאה וכן הלאה בלולאה.
מהו עומד לעשות הוא שהיא מקבלת כתובת ש, dereferences את זה כדי לקבל את הערך,
ושינויים שהערך לצ
אז בסוף תזכור את זה הוא מחרוזת, נכון?
כל המחרוזות יש לסיים עם אופי הסיום הריק.
לכן, מה שאני עושה הוא ב6 מצביע שמתי את אופי השליחות הקטלנית null פנימה
ועכשיו מה בעצם אני עושה כאן הוא יישום printf למחרוזת, נכון?
>> לכן, כאשר אין printf עכשיו כשזה הגיע לסוף המחרוזת?
כאשר הוא פוגע באופי הסיום הריק.
לכן, במקרה זה, הצביע המצביע המקורי שלי לתחילת מערך זה.
אני מדפיס את התו הראשון. אני מזיז אותה מעל אחד.
אני מדפיס את התו. אני עובר את זה.
ואני ממשיך לעשות את זה עד שאני מגיע לסוף.
ועכשיו המצביע * האם תסיים dereference הזה ולקבל את תו הסיום הריק בחזרה.
וכך בעוד לולאתי פועלת רק כאשר הערך שאינו דמות הפסקת null.
אז, עכשיו אני יוצא מהלולאה הזו.
ואז אם אני לחסר 6 מ מצביע זה,
אני חוזר כל הדרך עד להתחלה.
זכור, אני עושה את זה כי אני צריך ללכת להתחלה, על מנת לשחרר אותו.
>> אז, אני יודע שהיה הרבה. האם יש שאלות?
בבקשה, כן?
[לא מובן שאלת סטודנט]
האם אתה יכול לומר שיותר חזק? סליחה.
[סטודנטים] בשקופית האחרונה ממש לפני ששחררת את המצביע,
שבו אתה בעצם שינוי הערך של המצביע?
[יוסף] אז, ממש כאן. >> [סטודנטים] אה, בסדר.
[יוסף] לכן, יש לי מצביע מינוס מינוס, ימינה,
אשר מעביר את הדבר אחורי אחד, ואז לשחרר אותו,
כי מצביע זה יש הצביע על תחילתו של המערך.
[סטודנטים] אבל שלא יהיה צורך שהפסקת לאחר שהשורה.
[יוסף] לכן, אם אני הפסקתי אחרי זה, זה ייחשב דליפת זיכרון,
כי אני לא רצתי חופשי.
[סטודנטים] אני [לא מובן] לאחר השלוש השורות הראשונות שבו הייתה לך מצביע +1 [לא מובן].
[יוסף] אהה. אז מה השאלה שם?
סליחה. לא, לא. תלך, תלך, בבקשה.
[סטודנטים] אז, אתה לא משנה את הערך של מצביעים.
לא היית צריך לעשות מצביע מינוס מינוס.
[יוסף] כן, בדיוק.
לכן, כשאני עושה את המצביע +1 ומצביע +2,
אני לא עושה את המצביע שווה מצביע +1.
אז, המצביע פשוט נשאר מצביע על תחילתו של המערך.
זה רק כשאני עושה את תוספת בתוספת שהיא מגדירה את הערך פנימה את המצביע,
שזה דווקא מרגש את זה יחד.
בסדר.
עוד שאלות?
>> שוב, אם זה סוג של מכריע, זה יהיה מכוסה בפגישה.
שאל בחור ההוראה שלך על זה, ואנחנו יכולים לענות על שאלות בסוף.
ובדרך כלל אנחנו לא אוהבים לעשות דבר מינוס הזה.
זו יש לדרוש השמירה על המסלול שלי עד כמה אני כבר קוזזתי במערך.
אז, באופן כללי, זה רק כדי להסביר כיצד עובד פעולות אריתמטיות על מצביעים.
אבל מה שבדרך כלל אנחנו אוהבים לעשות הוא אנחנו אוהבים ליצור עותק של המצביע,
ואז להשתמש בעותק שכאשר אנחנו מסתובבים במחרוזת.
לכן, במקרה אלה שתשתמשו בעותק להדפיס כל המחרוזת,
אבל אנחנו לא צריכים לעשות כמו מצביע מינוס 6 או לעקוב אחר כמה עברנו בזה,
רק בגלל שאנחנו יודעים שהנקודה המקורית שלנו עדיין הצבעתי על תחילתה של הרשימה
וכל מה שאנחנו שינינו זה היה העתקה.
אז, באופן כללי, לשנות עותקים של המצביע המקורי שלך.
אל תנסה די אוהב - אל תשנה את העותקים מקוריים.
ניסיתי לשנות את העותקים היחידים שלך מקורי.
אז, אתה שם לב כאשר אנחנו מעבירים את המחרוזת לprintf
אתה לא צריך לשים את כוכב לפניו כמו שעשינו עם כל dereferences האחר, נכון?
לכן, אם אתה מדפיס% s המחרוזת כל צופה הוא כתובת,
ובמקרה הזה מצביע או במקרה זה כמו מערך של תווים.
>> תווים, char * s, ומערכים הם אותו הדבר.
מצביע הוא לתווים, ומערכי תווים הם אותו דבר.
וכך, כל שעלינו לעשות הוא לעבור במצביע.
אנחנו לא צריכים לעבור כבמצביע * או משהו כזה.
אז, מערכים ומצביעים הם אותו הדבר.
כשאתה עושה משהו כמו x [Y] הנה למערך,
מה הוא עושה מתחת למכסת המנוע הוא זה אומר, בסדר, זה מערך תווים,
כך שזה מצביע.
וכך x הוא אותו הדבר,
ואז מה שהוא עושה זה שהיא מוסיפה y ל x,
שזה אותו דבר כמו לנוע קדימה בזיכרון כל כך הרבה.
ועכשיו x + y נותן לנו איזו כתובת,
ואנחנו dereference כתובת או פעלו על החץ
לשם מיקום שהוא בזיכרון ואנחנו מקבלים את הערך ממיקום זה בזיכרון.
אז, אז שני אלה הם בדיוק אותו הדבר.
זה רק סוכר תחבירי.
הם עושים את אותו דבר. הם פשוט syntactics שונה זה לזה.
>> אז, מה יכול להשתבש עם מצביעים? כמו, והרבה. אוקיי. לכן, דברים רעים.
כמה דברים רעים שאתה יכול לעשות לא בודקים אם שיחת malloc מחזירה null, נכון?
במקרה זה, אני שואל את המערכת לתת לי - מהו מספר זה?
כמו 2 מיליארדים פעמים 4, בגלל גודלו של מספר שלם הוא 4 בתים.
אני שואל אותו למשהו כמו 8 מליארד בתים.
כמובן שהמחשב שלי לא הולך להיות מסוגל לתת לי שיחזור הזיכרון הרבה.
ולא לבדוק אם זה הוא ריק, ולכן כאשר אנו מנסים dereference אותו לשם -
פעל על החץ למקום שבו הולך - אין לנו זיכרון ש.
זה מה שאנו מכנים ביטול הפנית מצביע null.
וזה בעצם גורם לך segfault.
זוהי האחת הדרכים שאתה יכול segfault.
דברים רעים אחרים שאתה יכול לעשות - נו, טוב.
שביטול הפנית מצביע null. אוקיי.
דברים רעים אחרים - טוב, כדי לתקן את זה אתה פשוט לשים סימון שביש
שבודק אם המצביע הוא ריק
ולצאת מהתכנית אם זה קורה malloc שמחזיר מצביע null.
זה קומיקס xkcd. אנשים מבינים את זה עכשיו. סוג של.
>> לכן, זיכרון. ואני עברתי על זה.
אנחנו קוראים לmalloc בלולאה, אבל בכל פעם שאנו קוראים malloc
אנחנו מאבדים אחר שבו מצביע זה הוא מצביע,
כי אנחנו מחצנו אותו.
אז, בשיחה הראשונית לmalloc נותנת לי זיכרון לכאן.
מצביעי המצביע שלי לזה.
עכשיו, אני לא אשחרר אותו, אז עכשיו אני קורא malloc שוב.
עכשיו הוא מצביע לכאן. עכשיו הזיכרון שלי מצביע לכאן.
מצביע כאן. מצביע כאן.
אבל אני כבר אבדתי את הכתובות של כל הזיכרון מעל כאן שהוקציתי.
ואז עכשיו אין לי כל התייחסות אליהם יותר.
אז, אני לא יכול לשחרר אותם מחוץ למעגל הזה.
ולכן על מנת לתקן משהו כזה,
אם תשכח זיכרון פנוי ואתה מקבל דליפת זיכרון זה,
אתה צריך לשחרר את הזיכרון הפנימי של לולאה זה לאחר שתסיים עם זה.
ובכן, זה מה שקורה. אני מכיר הרבה שאתה שונא את זה.
אבל עכשיו - yay! אתה מקבל כמו 44,000 ק"ג.
אז, אתה תשחרר אותו בסוף הלולאה,
וזה הולך רק כדי לשחרר את הזיכרון בכל פעם.
בעיקרו של דבר, התכנית שלך אין דליפת זיכרון יותר.
>> ועכשיו משהו אחר שאתה יכול לעשות הוא לשחרר קצת זיכרון, כי אתה כבר בקשת פעמים.
במקרה זה, אתה משהו malloc, אתה משנה את הערך שלו.
אתה תשחרר אותו מייד, משום שאמרתם שאתם עושים עם זה.
אבל אז שחררתי אותו שוב.
זה משהו שהוא די גרוע.
זה לא הולך בתחילה לsegfault,
אך לאחר זמן מה שזה עושה הוא משחרר זה משחית כפול מבנה הערימה שלך,
ותלמד קצת יותר על זה, אם תבחר לקחת את כיתה כמו CS61.
אבל בעצם אחרי כמה זמן המחשב שלך עלול להתבלבל
על מיקומי זיכרון הם מה שבו ושבו הוא מאוחסן -
שבו נתונים מאוחסנים בזיכרון.
וכך משחרר את המצביע פעמים היא דבר רע, כי אתה לא רוצה לעשות.
>> דברים אחרים שיכולים להשתבש אינו משתמשים sizeof.
לכן, במקרה זה אתה malloc 8 בתים,
וזה אותו הדבר כמו שני מספרים שלמים, נכון?
אז, זה בטוח לחלוטין, אבל זה?
ובכן, כפי שלוקאס דבר על על ארכיטקטורות שונות,
מספרים שלמים הם באורכים שונים.
אז, על המכשיר שבו אתה משתמש, מספרים שלמים הם כ 4 בתים,
אבל במערכת אחרת שהם עלולים להיות 8 בתים או שהם יכולים להיות 16 בתים.
לכן, אם אני רק להשתמש במספר זה לכאן,
תכנית זו יכולה לעבוד על המכשיר,
אבל זה לא הולך להקצות מספיק זיכרון על מערכת אחרת.
במקרה זה, זה מה שמפעיל sizeof משמש ל.
כאשר אנו קוראים sizeof (int), מה המשמעות של זה הוא
זה נותן לנו את הגודל של מספר שלם במערכת שהתכנית פועלת.
לכן, במקרה זה, sizeof (int) יחזיר 4 במשהו כמו המכשיר,
ועכשיו 4 * זה 2, שהוא 8,
וזה רק את כמות השטח דרוש לשני מספרים שלמים.
במערכת אחרת, אם int הוא כמו 16 בתים או 8 בתים,
זה רק הולך לחזור מספיק בתים כדי לאחסן את הסכום הזה.
>> ולבסוף, structs.
לכן, אם אתה רוצה לאחסן את לוח סודוקו בזיכרון, איך ניתן לעשות זאת?
אתה יכול לחשוב כמו משתנה לדבר הראשון,
משתנה לדבר השני, משתנה לדבר השלישי,
משתנה לדבר הרביעי - רע, נכון?
לכן, שיפור יחיד שאתה יכול לעשות על גבי זה הוא להפוך את מערך x 9 9.
זה בסדר, אבל מה אם אתה רוצה לשייך דברים אחרים עם לוח הסודוקו
אוהבים את מה הקושי של הלוח הוא,
או, למשל, מה הציון שלך הוא, או כמה זמן שלקח לך לפתור מערכת זו?
ובכן, מה שאתה יכול לעשות הוא שאתה יכול ליצור struct.
מה אני בעצם אומר זה שהם מגדירים את המבנה הזה לכאן,
ואני מגדיר את לוח סודוקו אשר מורכב מקרש שהוא 9 9 x.
>> ומה יש לו יש לו מצביעים לשם את הרמה.
כמו כן, יש x ו-y, שהם הקואורדינטות של איפה אני נמצא עכשיו.
זה גם זמן שבילה [לא מובן], ויש לו את המספר הכולל של מהלכים שהוזנתי עד כה.
ולכן במקרה זה, אני יכול לקבץ את כל חבורה של נתונים לתוך רק מבנה אחד
במקום שיש בו כמו מתעופף במשתנים שונים כמו
שאני באמת לא יכול לעקוב אחריו.
וזה מאפשר לנו יש תחביר פשוט נחמד לסוג של התייחסות דברים שונים בתוך struct זה.
אני רק יכול לעשות board.board, ואני מקבל את לוח הסודוקו בחזרה.
Board.level, אני מקבל כמה קשה.
Board.x וboard.y לתת לי את הקואורדינטות של איפה אני יכול להיות במועצת המנהלים.
ואז אני ניגש מה שאנו מכנים בשדות struct.
זה מגדיר sudokuBoard, שהוא סוג שיש לי.
ועכשיו אנחנו כאן. יש לי משתנה בשם "לוח" של sudokuBoard סוג.
ואז עכשיו אני יכול לגשת לכל התחומים המרכיבים את המבנה הזה לכאן.
>> שאלות לגבי structs? כן?
[סטודנטים] לint x, y, שהכרזת גם על קו אחד? >> [יוסף] אהה.
[סטודנטים] אז, אתה יכול פשוט לעשות את זה עם כולם?
כמו בx, y פעמי פסיק שכלל?
[יוסף] כן, אתה בהחלט יכול לעשות את זה, אבל הסיבה ששמתי את X ו-Y על אותו הקו -
והשאלה היא למה אנחנו לא יכולים לעשות את זה באותה השורה?
למה שלא פשוט לשים את כל אלה באותו הקו
x ו-y הם קשורים זה לזה,
וזו רק סגנונית נכונה יותר, במובן מסוים,
כי זה קיבוץ שני דברים באותו הקו
כזה כמו של מתייחס לאותו הדבר.
ואני רק לפצל אלה בנפרד. זה פשוט דבר בסגנון.
זה פונקציונלי לא משנה כלל.
יש עוד שאלות על structs?
באפשרותך להגדיר Pokedex עם struct.
פוקימון יש מספר ויש לה מכתב, בעלים, סוג.
ואז, אם יש לך מערך של פוקימון, אתה יכול לעשות את Pokedex, נכון?
אוקיי, מגניב. לכן, שאלות בstructs. אלה קשורים לstructs.
>> לבסוף, GDB. מה GDB לא ייתן לך לעשות? זה מאפשר לך לדבג את התכנית שלך.
ואם לא השתמש GDB, הייתי מומלץ צופים קצר
ורק עוברים על מה GDB הוא, איך אתה עובד איתו, איך ייתכן שמשתמש בו,
ולבדוק אותו בתכנית.
ואז מה GDB מאפשר לך לעשות זה מאפשר להשהות [לא מובנת] את התכנית שלך
וקו מעשי.
לדוגמה, אני רוצה ביצוע מתעכב ליד כמו קו 3 של התכנית שלי,
ואם אני כבר בשורה 3 אני יכול להדפיס את כל הערכים שנמצאים שם.
וכך מה שאנו מכנים כמו נעצרים בקו
אנחנו קוראים לזה הוא לשים נקודת עצירה באותו קו
ואז אנחנו יכולים להדפיס את המשתנים במצב התכנית באותו זמן.
>> אנחנו יכולים משם לעבור דרך קו אחר קו התכנית.
ואז אנחנו יכולים להסתכל במצב של המחסנית באותו הזמן.
ולכן על מנת להשתמש GDB, מה שאנחנו עושים הם שאנחנו קוראים בצלצול את קובץ C,
אבל אנחנו צריכים לעבור אותו דגל ggdb-.
וברגע שנסיים עם זה אנחנו פשוט להפעיל gdb על קובץ הפלט שנוצר.
ואז אתה מקבל קצת מסה כמו של טקסט כזה,
אבל באמת כל מה שאתה צריך לעשות הוא להקליד פקודות בהתחלה.
העיקרי לפרוץ מעמיד בנקודת עצירה עיקרית.
רשימה 400 מפרטת את שורות קוד סביב קו 400.
ולכן במקרה זה אתה יכול רק להסתכל לאחור ולומר, הו,
אני רוצה להגדיר נקודת עצירה בקו 397, שהוא קו זה,
ואז התכנית שלך פועלת לצעד ושזה הולך להישבר.
זה הולך לעצור שם, ואתה יכול להדפיס, למשל, ערך נמוך או גבוה.
וכך יש חבורה של פקודות שאתם צריכים לדעת,
ושקופיות זה תעלינה באתר האינטרנט,
כך שאם אתה רק רוצה להפנות אותם או רוצה לשים אותם על הגיליונות לרמות שלך, תרגיש חופשי.
>> מגניב. זה היה חידון סקירה 0, ואנחנו נשארים כאן, אם יש לך שאלות.
בסדר.
>> [מחיאות כפות]
>> [CS50.TV]