[Powered by Google Translate] [סעיף 7] [פחות נוח]
[נייט Hardison] [אוניברסיטת הרווארד]
[זה CS50.] [CS50.TV]
>> ברוכים באים לסעיף 7.
תודה להוריקן סנדי,
במקום שיש סעיף רגיל השבוע,
אנחנו עושים את זה ללכת דרך, דרך הקטע של שאלות.
אני הולך להיות בא יחד עם בעית הסט 6 מפרט,
ועובר על כל השאלות ב
סעיף סעיף שאלות.
אם יש שאלות כלשהן,
בבקשה לפרסם את אלה בCS50 לדון בו.
>> אוקיי. בואו נתחיל.
נכון לעכשיו אני מחפש בעמוד 3 במפרט סט הבעיה.
אנחנו הולכים להתחיל קודם מדברים על עצים בינאריים
מאז אלה יש הרבה רלוונטיים לקבוצת בעית שבוע זה -
קידוד עץ האפמן.
אחד ממבני הנתונים הראשונים שדברנו עליו בCS50 היה המערך.
זכור כי מערך הוא רצף של אלמנטים -
כל אותו הסוג - מאוחסן ממש ליד אחד את השני בזיכרון.
אם יש לי מערך שלם שאני יכול לצייר באמצעות סגנון זה תיבות-מספרים שמספרים שלמי -
בואו נגיד שיש לי 5 בתיבה הראשונה, יש לי 7 בשנייה,
אז יש לי 8, 10, ו 20 בתיבה הסופית.
דברים זכרו, 2 ממש טובים על מערך זה
הם שיש לנו גישה מתמדת בזמן זה לכל אלמנט מסוים
במערך אם אנחנו יודעים את האינדקס שלו.
לדוגמה, אם אני רוצה לתפוס את המרכיב השלישי במערך -
באינדקס 2 באמצעות מערכת האינדקס אפס המבוססת שלנו -
אני ממש ממש צריך לעשות חישוב מתמטי פשוט,
לקפוץ למיקום במערך,
לשלוף 8 שמאוחסנים שם,
ואני טוב ללכת.
>> אחד הדברים הרעים על מערך זה - שדברנו על
כששוחחנו על רשימות מקושרות -
הוא שאם אני רוצה להכניס אלמנט לתוך מערך זה,
אני הולך לעשות קצת מייד ליד.
לדוגמה, מערך זה ממש כאן
הוא על מנת למיין - ממוין בסדר עולה -
5, אז 7, אז 8, 10, ולאחר מכן 20 -
אם ברצונך להוסיף את המספר 9 למערך זה, אבל,
אני הולך לעשות כדי להעביר חלק מהאלמנטים על מנת להפוך את החלל.
אנחנו יכולים לצייר את זה כאן.
אני הולך צריך לעבור 5, 7, ולאחר מכן 8;
ליצור פער שבו אני יכול לשים 9,
ולאחר מכן 10 ו 20 יכולים ללכת בצד הימין של 9.
זה סוג של כאב כי בתרחיש הגרוע ביותר -
כשאנחנו כל כך כדי להוסיף או בתחילה או בסוף
של המערך, תלוי איך אנחנו עוברים -
אנו עלולים בסופו של דבר נאלץ להעביר את כל האלמנטים
שאנחנו כרגע אחסון במערך.
>> אז, מה היה דרך לעקוף את זה?
דרך לעקוף את זה היה ללכת לשיטה המקושרת הרשימה שלנו שבו -
במקום לאחסן את אלמנטי 5, 7, 8, 10, ו 20 כל אחד ליד שני בזיכרון -
מה שאנחנו עשינו היו במקום לאחסן אותם סוג של מקום שאנחנו רוצים לאחסן אותם
בצומת מקושרים רשימה אלה שאני מצייר כאן, סוג של אד הוק.
ואז אנחנו מחוברים יחד שימוש במצביעים הקרובים.
אני יכול להיות מצביע מ 5 עד 7,
מצביע מ 7 עד 8,
מצביע מ 8 עד 10,
ולבסוף, מצביע מ 10 עד 20,
ואז מצביע null ב20 המציין כי לא נשאר כלום.
התחלופה שיש לנו כאן
הוא שעכשיו אם ברצונך להוסיף את המספר 9 ברשימה הממוינת שלנו,
כל שעלינו לעשות הוא ליצור צומת חדש עם 9,
תמלכד אותה כדי להצביע על המקום המתאים,
ולאחר מכן מחדש חוט 8 להצביע עד 9.
זה די מהיר, בהנחה שאנחנו יודעים בדיוק לאן אנחנו רוצים להכניס את 9.
אבל התחלופה בתמורה לכך היא שאנחנו עכשיו אבדנו את הגישה מתמדת בזמן
לכל רכיב מסוים במבנה הנתונים שלנו.
לדוגמה, אם אני רוצה למצוא את המרכיב הרביעי ברשימה מקושרת זה,
אני הולך צריך להתחיל ממש בתחילתה של הרשימה
ואת דרך העבודה שלי דרך לספור אחר צומת צומת עד שאני מוצא את הרביעית.
>> על מנת לקבל גישה לביצועים טובים יותר מאשר רשימה מקושרת -
אלא גם לשמור על חלק מההטבות שהיו לנו
במונחים של הכנסה בזמן מרשימה מקושרת -
עץ בינארי הולך צריך להשתמש קצת יותר זיכרון.
בפרט, לא רק שיש מצביע אחד בצומת בעץ בינארי -
כמו הרשימה מקושרת צומת עושה -
אנחנו הולכים להוסיף מצביע שני לצומת בעץ בינארי.
ולא רק שיש מצביע אחד לאלמנט הבא,
אנחנו הולכים לה מצביעים לילד שמאלי וילד נכון.
>> בואו לצייר תמונה כדי לראות מה שבעצם נראה.
שוב, אני הולך להשתמש בתיבות וחצים אלה.
צומת בעץ בינארי יהיה להתחיל עם תיבה פשוטה.
זה הולך להיות מקום לערכים,
ואז זה גם הולך להיות מקום לילד השמאלי והילד הנכון.
אני הולך לתייג אותם כאן.
אנחנו הולכים לקחת את הילד מהשמאל, ואז אנחנו הולכים לקחת את הילד הנכון.
ישנן דרכים רבות ושונות לעשות את זה.
לפעמים למרחב ונוחות,
אני באמת אכין לך שאני עושה כאן בקרקעית
לאן אני הולך יש ערך בחלקו העליון,
ואז הילד ממש על הפינה הימנית תחתון,
והילד השמאלי התחתון.
אם יחזרו לתרשים עליון זו,
יש לנו ערך בחלקו עליון,
אז יש לנו את מצביע שמאל הילד, ולאחר מכן יש לנו את המצביע לילד נכון.
>> במפרט הגדרת הבעיה,
אנחנו מדברים על ציור צומת שיש לו ערך 7,
ולאחר מכן על מצביע ילד השמאלי שהוא ריק, ומצביע לילד זכות שהוא ריק.
אנחנו יכולים לכתוב NULL הון במרחב
גם ילד השמאלי והילד צודק, או שאנחנו יכולים לצייר חתך אלכסוני וזה
דרך כל אחת מהתיבות כדי לציין שזה ריק.
אני הולך לעשות את זה רק בגלל שזה פשוט יותר.
מה שאתה רואה כאן שתי דרכי דיאגרמות צומת בעץ בינארי פשוט מאוד
שם יש לנו את הערך 7 ומצביעי ילד null.
>> חלק השני של שיחות המפרט שלנו על איך עם רשימות מקושרות -
תזכור, היו לנו רק להחזיק במרכיב הראשון ברשימה
לזכור את כל הרשימה -
וכמו כן, עם עץ בינארי, יש לנו רק לשמור על מצביע אחד לעץ
על מנת לשמור על שליטה על מבנה הנתונים כולו.
אלמנט מיוחד זה של העץ נקרא צומת השורש של העץ.
לדוגמה, אם זו צומת אחת - זו צומת שמכילה את הערך 7
עם מצביעי שמאל וימין ילד null -
היו הערך רק בעץ שלנו,
אז זה יהיה צומת השורש שלנו.
זה מאוד תחילת העץ שלנו.
אנחנו יכולים לראות את זה קצת יותר בבהירות ברגע שנתחיל להוסיף עוד צומת לעץ שלנו.
תן לי להכין את הדף חדש.
>> עכשיו אנחנו הולכים לצייר עץ שיש לו 7 בשורש,
ו 3 פנימיים של הילד השמאלי, ו9 הפנימיים של הילד הנכון.
שוב, זה די פשוט.
יש לנו 7, לצייר לצומת 3, צומת עבור 9,
ואני הולך להגדיר את מצביע שמאל הילד של 7 כדי להצביע על הצומת המכילה 3,
והמצביע ימני הילד של הצומת המכילה 7 לצומת המכילה 9.
עכשיו, מאז 3 ו 9 אין לך ילדים,
אנחנו הולכים להגדיר כל המצביעים שהילד שלהם יהיה בטל.
הנה, השורש של העץ שלנו מתאים לצומת המכילה את המספר 7.
אתה יכול לראות שאם כל שיש לנו הוא מצביע שלצומת השורש,
אז אנחנו יכולים ללכת דרך העץ שלנו וגישה לשני בלוטות ילד -
גם 3 ו 9.
אין צורך לשמור מצביעים לצומת כל אחת על העץ.
אוקיי. עכשיו אנחנו הולכים להוסיף צומת אחרת לתרשים זה.
אנחנו הולכים להוסיף צומת המכילה 6,
ואנחנו הולכים להוסיף את זה כילד הימני של הצומת המכילה 3.
כדי לעשות את זה, אני הולך למחוק שמצביע null ב3-הצומת
ותמלכד אותה כדי להצביע על הצומת המכילה 6. אוקיי.
>> בשלב זה, בואו נלך על קצת טרמינולוגיה.
כדי להתחיל, מהסיבה שזה נקרא עץ בינארי בפרט
הוא כי יש שני מצביעי ילד.
ישנם סוגים אחרים של עצים שיש יותר מצביעי ילד.
בפרט, שעשית "ניסיון" בסט הבעיה 5.
תוכל להבחין כי שבניסיון, שהיה 27 מצביעים שונים לילדים שונים -
אחד לכל אחד מ26 האותיות באלפבית האנגלי,
ולאחר מכן 27 לגרש -
לכן, זה דומה לסוג של עץ.
אבל כאן, שכן בינארי זה, יש לנו שני מצביעים היה בן יחיד.
>> בנוסף לצומת השורש הזה שדברנו עליו,
אנחנו גם כבר לזרוק סביב מונח זה 'הילד'.
מה זה אומר לצומת אחד להיות ילד של צומת אחר?
זה פשוטו כמשמעו שצומת ילד היא ילד של צומת אחרת
אם כי הצומת השנייה יש אחד ממצביעי הבנים שלו שנקבעו כדי להצביע שצומת.
כדי לשים את זה במונחים קונקרטיים יותר,
אם 3 הוא הצביעו על ידי אחד ממצביעי הילד של 7, אז 3 הם ילד של 7.
אם היו עלינו להבין מה הם הילדים בגילי 7 -
כן, אנו רואים כי 7 יש מצביע למצביע 3 ועד 9,
כך 9 ו 3 הם ילדיהם של 7.
תשע אין לו ילדים, כי מצביעי הילד שלה הם ריקים,
ו3 יש רק ילד אחד, 6.
שישה גם אין לו ילדים, כי הן של מצביעיה הן אפס, שאנחנו עושים הגרלה עכשיו.
>> בנוסף, אנחנו גם מדברים על ההורים של צומת מסוימת,
וזה, כפי שהיית מצפה, היפוכו של תיאור הילד הזה.
כל צומת יש הורה אחד בלבד - במקום שניים כפי שהיה אפשר לצפות לו עם בני אדם.
לדוגמה, ההורה של 3 הוא 7.
ההורה של 9 הוא גם 7, וההורה של 6 הוא 3. לא הרבה אליו.
יש לנו גם מבחינת לדבר על סבים ונכדים,
ובאופן כללי אנחנו מדברים על האבות
וצאצאיו של צומת מסוימת.
אב הקדמון של צומת - או אבות, אלא מצומת -
הם כל צומת הנמצאים בדרך מהשורש עד שהצומת.
לדוגמה, אם אני מסתכל על 6 הצומת,
אז האבות הולכים להיות גם 3 ו 7.
אבותיהם של 9, למשל, הם - אם אני מסתכל על 9 הצומת -
אז האב הקדמון של 9 הוא רק 7.
וצאצאים הם בדיוק הפוכים.
אם אני רוצה להסתכל על כל צאצאיו של 7,
אז יש לי להסתכל על כל צומת שמתחתיו.
לכן, יש לי 3, 9, ו 6 הכל כצאצאים של 7.
>> הטווח הסופי שנדברנו על זה רעיון של להיות אח.
אחים - סוג של לאחר יחד בתנאי - המשפחה
הם בלוטות שנמצאות באותה הרמה בעץ.
אז, 3 ו 9 הם אחים כי הם נמצאים באותה הרמה בעץ.
לשניהם יש את אותו הורה, 7.
6 אין אחים כי 9 לא היו לו ילדים.
ו 7 אין שום אחים כי זה השורש של העץ שלנו,
ויש רק פעם 1 שורש.
7 ב ליש אחים שם היה צריך להיות צומת מעל 7.
יהיה צורך בלהיות הורה של 7, ובמקרה זה 7 כבר לא יהיה השורש של העץ.
ואז שההורה החדש של 7 היה צריך גם להביא ילד לעולם,
והילד שהיה אז להיות האח של 7.
>> אוקיי. ימשיך הלאה.
כשהתחלנו הדיון בעצים בינאריים שלנו,
דברנו על איך שאנחנו הולכים להשתמש בם כדי
לזכות ביתרון על שני מערכים ורשימות מקושרות.
והדרך שאנחנו הולכים לעשות את זה הוא ברכוש הזמנה זו.
אנחנו אומרים שעץ בינארי הוא הורה, בהתאם למפרט,
אם לכל צומת בעץ שלנו, כל צאצאיה בצד השמאל -
הילד השמאלי וכל צאצאיו של הילד השמאלי -
יש ערכים פחותים, וכל צומת בימין -
הילד הימני וכל צאצאיו של ילד הזכות -
יש צומת גדולים מהערך של הצומת הנוכחית שאנחנו מסתכלים.
רק לשם פשטות, אנחנו הולכים להניח שאין שום צומת כפולים בעץ שלנו.
לדוגמה, בעץ הזה אנחנו לא מתכוונים להתמודד עם המקרה
שם יש לנו את הערך 7 בשורש
ואז יש לנו גם את הערך 7 במקום אחר בעץ.
במקרה זה, תוכל להבחין כי העץ הזה הוא הורה אכן.
יש לנו את הערך 7 בשורש.
כל מה שמהשמאל ל7 -
אם אני לבטל את כל הסימנים הקטנים האלה כאן -
כל מה שמהשמאל ל7 - 3 ו - 6
ערכים אלה הם פחות מ 7, והכילו לימין - שהוא פשוט זה 9 -
גדול מ 7.
>> זה לא רק עץ ההורה המכיל את הערכים הללו,
אבל בואו נצייר עוד כמה מהם.
יש למעשה חבורה שלמה של דרכים שאנחנו יכולים לעשות את זה.
אני הולך להשתמש בקצרנות, רק כדי לשמור על דברים פשוטים שבו -
לא ציור את כל תיבות-and-חצים -
אני פשוט הולך לצייר את המספרים ולהוסיף חצים מחברים אותם.
כדי להתחיל, פשוט אכתוב את העץ המקורי שלנו שוב שבו היינו 7, ולאחר מכן 3,
ואז 3 הצביעו שוב על זכות 6,
ו 7 היו ילד זכות שעמדו על 9.
אוקיי. מה דרך נוספת שאנחנו יכולים לכתוב את העץ הזה?
במקום שיש 3 יהיה הילד השמאלי של 7,
אנחנו גם יכולים להיות 6 יהיו הילד השמאלי של 7,
ואז 3 יהיו הילד השמאלי של 6.
זה היה נראה כמו העץ הזה ממש כאן, במקום יש לי 7,
אז 6, ואז 3, ו9 בצד ימין.
אנחנו גם לא צריכים שנהיה לי 7 כצומת השורש שלנו.
אנחנו גם יכולים להיות 6 כמו צומת השורש שלנו.
מה שנראה לך?
אם אנחנו הולכים לשמור על רכושו ציווה זאת,
כל מה שמהשמאל ל6 צריך להיות פחות מזה.
יש רק אפשרות אחת, וזה 3.
אבל אז כילד הנכון של 6, יש לנו שתי אפשרויות.
ראשית, שנהיה לנו 7 ואז 9,
או שאנחנו יכולים לצייר את זה - כמו שאני עומד לעשות כאן -
שם יש לנו 9 כילד הימני של 6,
ולאחר מכן את מספר 7 ילד השמאלי של 9.
>> כעת, 7 ו 6 הם לא את הערכים האפשריים רק לשורש.
גם אנחנו יכולים להיות לנו 3 בשורש.
מה קורה אם 3 הם בשורש?
הנה, דברים מקבלים קצת מעניינים.
שלוש אין שום ערכים שהם פחות מזה,
כך שכל הצד השמאלי של העץ הוא רק הולך להיות ריק.
יש לא הולך להיות כל דבר שם.
מימין, נוכל לפרט את הדברים בסדר עולה.
יכל להיות לנו 3, אז 6, אז 7, אז 9.
לחלופין, אנו יכולים לעשות 3, ולאחר מכן 6, אז 9, אז 7.
לחלופין, אנו יכולים לעשות 3, ולאחר מכן 7, ולאחר מכן 6, אז 9.
או, 3, 7 - ממש לא, אנחנו לא יכולים לעשות יותר 7.
זה הדבר האחד שלנו שם.
אנחנו יכולים לעשות את 9, ולאחר מכן מ9 אנחנו יכולים לעשות 6 ואז 7.
לחלופין, אנו יכולים לעשות את 3, אז 9, אז 7, ולאחר מכן 6.
>> דבר אחד שיש להסב את תשומת הלב לכאן הוא
שהעצים האלה הם מוזר מעט למראה.
בפרט, אם אנחנו מסתכלים על 4 עצים בצד ימין -
אני עוקף אותם, כאן -
העצים האלה נראים כמעט בדיוק כמו רשימה מקושרת.
כל צומת יש רק ילד אחד,
ולכן אין לנו כל המבנה הזה דמוי עץ שאנו רואים, למשל,
בעץ הזה אחד ויחיד כאן בצד ימין למטה.
העצים האלה ממש נקראים מנוונים עצים בינאריים,
ונדברנו על אלה יותר בעתיד -
במיוחד אם אתה הולך על לקחת קורסים במדעי מחשב אחרים.
עצים אלה הם מנוונים.
הם לא מאוד שימושיים כי, אכן, מבנה זה משאיל את עצמו
לבדיקת זמנים דומים לזה של רשימה מקושרת.
אנחנו לא יכולים לקחת את היתרון של זיכרון הנוסף - מצביע הנוסף הזה -
בגלל המבנה שלנו היית גרוע בדרך זו.
במקום להמשיך ולצייר את העצים בינאריים בעלי 9 בשורש,
שהוא במקרה האחרון שהיינו לנו,
אנחנו במקום, בשלב זה, הולכים לדבר קצת על מונח אחר זה
כי אנו משתמשים כאשר מדברים על עצים, אשר נקראים הגובה.
>> גובו של עץ הוא המרחק מהשורש לצומת הכי הרחוקה,
או לייתר דיוק, מספר הדילוגים שהיית צריך לעשות כדי
להתחיל מהשורש ואז בסופו בצומת הכי הרחוקה בעץ.
אם נסתכל על כמה מהעצים האלה שאנחנו כבר נמשכים ממש כאן,
אנו יכולים לראות שאם ניקח את העץ הזה בפינה השמאלית העליונה ואנחנו מתחילים ב3,
אז אנחנו צריכים לעשות היפ 1 כדי לקבל ל6, הופ 2 כדי להגיע ל7,
והופ שלישי כדי להגיע ל9.
לכן, הגובה של העץ הזה הוא 3.
אנחנו יכולים לעשות את אותו תרגיל לעצים האחרים צוירו בירוק הזה,
ואנחנו רואים שגובה של כל העצים האלה הוא גם אכן 3.
זה חלק ממה שהופך אותם מנוון -
שהגובה שלהם הוא רק אחד פחות ממספר צומת בכל העץ.
אם נסתכל על העץ הזה אחר זה מוקף באדום, מצד השני,
אנו רואים שאת צומת העלים הכי הרחוקים הם 6 ו 9 -
משאיר להיות צומת האלה שאין להם ילדים.
לכן, על מנת להגיע מצומת השורש לאו 6 או 9,
אנחנו צריכים לעשות היפ אחת להגיע ל7 ואז הופ שנייה כדי להגיע ל9,
וכן, רק הופ שנייה מ7 להגיע ל6.
לכן, הגובה של העץ הזה כאן הוא רק 2.
אתה יכול לחזור ולעשות את זה לכל עצים האחרים שדנו בעבר
מתחיל עם 7 ו 6,
ותגלה שגובה של כל העצים האלה הוא גם 2.
>> הסיבה שאנחנו כבר מדברים על הורה עצים בינאריים
ומדוע הם מגניבים בגלל שאתה יכול לחפש דרכם ב
דרך דומה מאוד לחיפוש על מערך ממוין.
זה המקום בו אנחנו מדברים על מקבלים שזמן הבדיקה המשופר
על הרשימה המקושרת הפשוטה.
עם רשימה מקושרת - אם אתה רוצה למצוא את אלמנט מסוים -
אתה בהולך טוב ביותר לעשות איזשהו החיפוש ליניארי
בו אתה מתחיל בתחילת רשימה ודילוג אחד על אחד -
צומת אחד בצומת אחד -
דרך כל הרשימה עד שתמצא את מה שאתה מחפש.
לעומת זאת, אם יש לך עץ בינארי, ששומר בפורמט זה נחמד,
למעשה אתה יכול לקבל יותר מחיפוש בינארי קורה
איפה אתה פרד ומשול
וחיפוש דרך במחצית המתאימה של עץ בכל שלב.
בואו לראות איך זה עובד.
>> אם יש לנו - שוב, לחזור לעץ המקורי שלנו -
אנחנו מתחילים בשעת 7, יש לנו 3 בצד השמאל, 9 בצד ימין,
ומתחת 3 שיש לנו 6.
אם אנחנו רוצים לחפש את המספר 6 בעץ הזה, שנתחיל בשורש.
היינו להשוות את הערך שאנחנו מחפשים, אומרים 6,
לערך המאוחסן בצומת שאנחנו כרגע מסתכלים, 7,
מוצא כי 6 הן אכן פחות מ 7, אז הייתי עוברים לצד השמאל.
אם הערך של 6 היה גדול מ 7, שהיינו במקום עברתי לצד ימין.
מאחר שאנחנו יודעים ש-- בשל המבנה של העץ בינארי ההורה שלנו -
כל הערכים פחות מ 7 הולכים להיות מאוחסן בצד השמאל של 7,
אין צורך אפילו לטרוח לחפש בצד ימין של העץ.
ברגע שאנחנו עוברים לצד השמאל ואנחנו עכשיו בצומת המכילה 3,
אנחנו יכולים לעשות אותו השוואה שוב שבו אנו משווים את 3 ו 6.
ואנו מוצאים כי תוך 6 - הערך שאנחנו מחפשים - הם יותר מ 3,
אנחנו יכולים ללכת לצד ימין של הצומת המכילה 3.
אין כאן צד שמאל, ואז הייתי יכול להתעלם מכך ש.
אבל אנחנו רק יודעים שבגלל שאנחנו מסתכלים על העץ עצמו,
ואנו יכולים לראות כי העץ אין לו ילדים.
>> זה גם די קל להסתכל למעלה 6 בעץ הזה אם אנחנו עושים זאת בעצמנו כבני אדם,
אבל בואו לעקוב אחרי התהליך הזה מכאני כמו מחשב יעשה
כדי באמת להבין את האלגוריתם.
בשלב הזה, אנחנו מסתכלים עכשיו צומת המכילה 6,
ואנחנו מחפשים את הערך 6,
כך, אכן, מצא את הצומת המתאימה.
מצאנו את הערך 6 בעץ שלנו, ואנחנו יכולים להפסיק את החיפוש שלנו.
בשלב זה, תלוי במה שקורה,
אנחנו יכולים לומר, כן, אנחנו צריכים למצוא את הערך 6, זה קיים בעץ שלנו.
או, אם אנחנו מתכננים להוסיף צומת או לעשות משהו, אנחנו יכולים לעשות את זה בשלב זה.
>> בואו נעשה עוד כמה חיפושים רק כדי לראות איך זה עובד.
בואו נסתכל על מה שקורה אם היינו לנסות ולחפש את הערך 10.
אם היו עלינו לחפש את הערך 10, הייתי מתחיל בשורש.
היינו רואה כי 10 הם גדולים מ 7, אז הייתי עובר לימין.
הייתי מגיע ל 9 והשווינו 9 עד 10 ולראות שאכן 9 הן פחות מ 10.
אז שוב, הייתי מנסה לעבור לצד ימין.
אבל בנקודה זו, הייתי שם לב שאנחנו בצומת ריקה.
אין שם כלום. אין שום דבר שבו צריכים להיות 10.
זה המקום בו אנו יכולים לדווח על כישלון - כי אכן לא 10 בעץ.
ולבסוף, בואו נעבור את המקרה שבו אנחנו מנסים לחפש את 1 בעץ.
זה דומה למה שקורה אם אנחנו מרימים 10, רק שבמקום ללכת לצד ימין,
אנחנו הולכים לשמאל.
אנו מתחילים ב7 ולראות כי 1 היא פחות מ 7, אז אנחנו עוברים לצד השמאל.
אנחנו מקבלים ל3 ולראות כי 1 הוא פחות מ 3, אז שוב אנחנו מנסים לעבור לצד השמאל.
בשלב זה יש לנו צומת ריקה, אז שוב אנחנו יכולים לדווח על כישלון.
>> אם אתה רוצה ללמוד יותר על עצים בינאריים,
יש חבורה שלמה של בעיות קטנות כיף שאתה יכול לעשות איתם.
אני מציע תרגול הציור מתוך התרשימים האלה אחד על 1
ובעקבות דרך כל השלבים השונים,
כי זה יבוא בסופר שימושי
לא רק כשאתה עושה את ערכת בעית קידוד האפמן
אלא גם בקורסים עתידיים -
רק לומד איך לצייר את מבני הנתונים האלה ולחשוב דרך הבעיות
עם עט ונייר, או, במקרה זה, אייפד וחרט.
>> בשלב זה אם כי, אנחנו הולכים לעבור על מנת לעשות קצת תרגול קידוד
וממש לשחק עם עצים בינאריים אלה ולראות.
אני הולך לעבור בחזרה אל המחשב שלי.
לחלק זה של הסעיף, במקום להשתמש CS50 הפעלה או CS50 Spaces,
אני הולך להשתמש במכשיר.
>> בעקבות יחד עם מפרט גדר הבעיה,
אני רואה שאני אמור לפתוח את המכשיר,
ללכת לתיקיית ה-Dropbox שלי, ליצור תיקייה בשם הסעיף 7,
ולאחר מכן ליצור קובץ בשם binary_tree.c.
הנה אנחנו מתחילים. יש לי את המכשיר כבר פתוח.
אני הולך למשוך את מסוף.
אני הולך לתיקיית Dropbox, להפוך את ספרייה בשם section7,
ותראה את זה לגמרי ריק.
עכשיו אני הולך לפתוח binary_tree.c.
אוקיי. הנה אנחנו מתחילים - קובץ ריק.
>> בואו נחזור למפרט.
המפרט מבקש ליצור הגדרת סוג חדשה
לצומת בעץ בינארי שמכיל ערכי int -
בדיוק כמו את הערכים שהוצאנו בדיאגרמות שלנו בעבר.
אנחנו הולכים להשתמש בזה boilerplate typedef שעשינו ממש כאן
כי אתה צריך להכיר מסט הבעיה 5 -
אם אתה עשית את דרך שולחן החשיש לכבוש את תכנית האיות.
אתה צריך גם להכיר אותו מהסעיף של השבוע שעבר
שם דברנו על רשימות מקושרות.
יש לנו את זה typedef struct של צומת,
ואנחנו נתנו לי צומת struct זה שמו של צומת struct זה מראש
כדי שאז תוכל להתייחס אליו מאז שנרצה שיהיה לי מצביעי צומת struct
כחלק מstruct שלנו, אבל אז אנחנו כבר הקפנו זה -
או לייתר דיוק, זה סגור - בtypedef
כך, מאוחר יותר בקוד, אנו יכולים להתייחס לזה כפשוט struct צומת במקום צומת struct.
>> זה הולך להיות מאוד דומה להגדרת רשימת ביחידים הצמודה שראינו בשבוע שעבר.
לשם כך, בואו נתחיל על ידי כתיבת הטקסט הסטנדרטי.
אנחנו יודעים שאנחנו צריכים שנהיה לי ערך שלם,
כן אנעל את ערך int, ואז במקום שיש רק מצביע אחד לאלמנט הבא -
כפי שעשינו עם רשימות ביחידים צמודי -
אנחנו הולכים להיות ילד מצביעי שמאל וימין.
זה די פשוט מדי - צומת ילד struct * שמאל;
וצומת * ילד struct נכון;. מגניב.
זה נראה כמו התחלה טובה למדי.
בואו נחזור למפרט.
>> עכשיו אנחנו צריכים להצהיר על משתנים * צומת עולמית לשורש של עץ.
אנחנו הולכים לעשות את זה גלובלי בדיוק כמו שעשינו מצביע ראשון ברשימה המקושרת שלנו גם הגלובלית.
זה היה כך בפונקציות שאנו כותבים
אין לנו לשמור על שהעביר סביב שורש זה -
למרות שאנחנו נראה את זה אם אתה רוצה לכתוב הפונקציות הללו באופן רקורסיבי,
זה יכול להיות טוב יותר אפילו לא עובר אותו סביב כגלובלי במקום הראשון
ובמקום לאתחל אותו באופן מקומי בפונקציה העיקרית שלך.
אבל, אנחנו נעשה את זה באופן גלובלי כדי להתחיל.
שוב, אנו נותנים כמה מקומות, ואני הולך להכריז שורש * צומת.
רק כדי לוודא שאני לא אעזוב את זה שלא אותחל, אני הולך להגדיר אותו שווה ל null.
כעת, בתפקידו העיקרי - שאנחנו באמת לכתוב במהירות ממש כאן -
int הראשי (int argc, const char * argv []) -
ואני הולך להתחיל להכריז מערך argv כconst רק כדי שאדע
שהטיעונים האלה הם טיעונים שאני כנראה לא רוצה לשנות.
אם אני רוצה לשנות אותם אני כנראה צריך להיות יצירת עותקים שלהם.
אתה תראה את זה הרבה בקוד.
זה בסדר בכל המקרה. זה בסדר להשאיר אותו כ-- להשמיט const אם תרצה.
אני בדרך כלל לשים את זה רק כדי שאני מזכיר לעצמי
כי מן הסתם אני לא רוצה לשנות את הטיעונים הללו.
>> כמו תמיד, אני הולך לכולל 0 קו תמורה זו בסופו של ראשי.
הנה, אני יהיה לאתחל צומת השורש שלי.
כפי שהיא עומדת עכשיו, יש לי מצביע אשר מוגדר לnull,
כך שזה מצביע על שום דבר.
על מנת להתחיל בבנייה בפועל את הצומת,
אני קודם צריך להקצות זיכרון לכך.
אני הולך לעשות את זה על ידי יצירת זיכרון על הערמה באמצעות malloc.
אני הולך להגדיר שורש שווה לתוצאה של malloc,
ואני הולכת להשתמש באופרטור sizeof לחשב את גודלו של צומת.
הסיבה שאני משתמש בצומת sizeof לעומת, יניח,
עושה משהו כזה - malloc (4 + 4 +4) או malloc 12 -
הוא כי אני רוצה הקוד שלי כדי להיות תואם ככל האפשר.
אני רוצה להיות מסוגל לקחת. קובץ c זה, לקמפל אותו על המכשיר,
ולאחר מכן לאסוף אותה על המקינטוש שלי 64-bit -
או בארכיטקטורה שונה לחלוטין -
ואני רוצה את כל זה כדי לעבוד אותו הדבר.
>> אם אני עושה הנחות בערך בגודל של משתנים -
הגודל של int או הגודל של מצביע -
אז אני גם עושה הנחות על סוגי ארכיטקטורות
שבקוד שלי יכול לקמפל בהצלחה כאשר לרוץ.
השתמש תמיד sizeof בניגוד לסיכום שדות struct באופן ידני.
הסיבה האחרת היא שיש גם עשויה להיות ריפוד שהמהדר מכניס struct.
אפילו רק סיכום השדות הבודדים הוא לא משהו שאתה בדרך כלל רוצה לעשות,
כך, למחוק את הקו הזה.
עכשיו, כדי באמת לאתחל צומת השורש הזה,
אני הולך צריך לחבר ערכים עבור כל אחד מהתחומים השונים שלה.
לדוגמה, עבור ערך שאני יודע שאני רוצה לאתחל עד 7,
ועכשיו אני הולך להגדיר את הילד השמאלי להיות null
וילד הזכות גם להיות ריק. גדול!
עשינו את אותו חלק מהמפרט.
>> המפרט למטה בתחתית העמוד 3 מבקש ממני ליצור עוד שלושה צומת -
אחד המכיל 3, אחד המכיל 6, ואחת עם 9 -
ואז תעביר אותם, כך זה נראה בדיוק כמו תרשים העץ שלנו
שאנחנו מדברים על עבר.
בואו לעשות את זה די מהר כאן.
אתה תראה מהר מאוד שאני הולך להתחיל לכתוב חבורה של קוד כפול.
אני הולך ליצור * צומת ואני הולך לקרוא לו שלוש.
אני הולך להגדיר אותו שווה לmalloc (sizeof (צומת)).
אני הולך להקים שלוש> ערך = 3.
שלוש -> left_child = NULL; 3 -> זכות _child = NULL; גם כן.
זה נראה די דומה לאתחול השורש, וזה בדיוק מה
אני הולך לעשות אם אני מתחיל אתחול 6 ו 9 גם כן.
אני אעשה את זה ממש מהר כאן - למעשה, אני הולך לעשות העתק ודבק קטנים,
ולוודא שאני - בסדר.
עכשיו, יש לי להעתיק את זה ואני יכול להמשיך ולהגדיר את זה שווה ל 6.
אתה יכול לראות שזה לוקח קצת זמן ולא סופר יעיל.
בקצת, יכתבו פונקציה שתעשה את זה בשבילנו.
אני רוצה להחליף זה עם 9, תחליף את זה עם 6.
>> עכשיו יש לנו את כל צומת שלנו נוצר ואותחל.
יש לנו השורש שלנו מקבל ערך 7, או שמכילים את הערך 7,
הצומת שלנו המכילה 3, צומת המכיל 6, והצומת שלנו המכיל 9.
בשלב זה, כל שעלינו לעשות הוא כל חוט למעלה.
הסיבה שאותחלתי כל המצביעים לnull היא רק כדי שאוכל לוודא כי
אין לי כל מצביעים לא מאותחלים בשם במקרה.
וגם מאז, בשלב זה, יש לי רק בעצם לחבר את צומת זה לזה -
לאלו שהם מחוברים באמת - אני לא צריך לעבור ולעשות
בטוח שכל הערכים null נמצאים שם במקומות המתאימים.
>> החל בשורש, אני יודע שהילד השמאלי של השורש הוא 3.
אני יודע שהילד הימני של השורש הוא 9.
אחרי זה, הילד היחיד שנשאר לי מה לדאוג
הילד הוא זכותה של 3, שעומד על 6.
בשלב זה, את כל זה נראה די טוב.
אנו מחקנו חלק מהקווים הללו.
עכשיו הכל נראה די טוב.
בואו נחזור למפרט שלנו ולראות מה אנחנו צריכים לעשות הלאה.
>> בנקודה זו, יש לנו לכתוב פונקציה שנקראת 'מכילה'
עם אב טיפוס של "כולל bool (int ערך) '.
וזה מכיל פונקציה הולכת להחזר אמיתי
אם העץ שאליו מצביע משתנה השורש הגלובלי שלנו
מכיל את הערך העביר לפונקציה ושקר אחר.
בואו נלך קדימה ולעשות את זה.
זה הולך להיות בדיוק כמו הבדיקה שעשינו ביד על האייפד רק קצת לפני.
בואו נחזור להתמקד במעט ולגלול למעלה.
אנחנו הולכים לשים את הפונקציה הזו בדיוק מעל הפונקציה העיקרית שלנו
כך שאין לנו לעשות כל סוג של אב טיפוס.
אז, bool מכיל (int ערך).
הנה. יש ההצהרה המוכנה מראש שלנו.
רק כדי לוודא שזה יהיה לקמפל,
אני הולך קדימה ופשוט להגדיר אותו שווה לתמורת שווא.
כרגע פונקציה זו פשוט לא לעשות כלום ותמיד מדווחת כי
הערך שאנחנו מחפשים הוא לא בעץ.
>> בשלב זה, זה כנראה רעיון טוב -
מאז שנכתבנו חבורה שלמה של קוד, ואנחנו אפילו לא ניסינו לבדוק את זה עדיין -
כדי לוודא שכל הידור.
יש כמה דברים שאנחנו צריכים לעשות כדי לוודא שזה יהיה ממש לקמפל.
ראשית, לראות אם אנחנו כבר משתמשים בכל פונקציות בכל ספריות שלא נכללו עדיין.
הפונקציות שבם השתמשו עד כה הם malloc,
ואז גם אנחנו משתמשים בסוג זה - הסוג לא הסטנדרטי הזה שנקרא 'bool' -
הנכלל בקובץ כותרת bool הסטנדרטי.
אנחנו בהחלט רוצים לכלול bool.h הסטנדרטי לסוג bool,
ואנחנו גם רוצים # לכלול lib.h הסטנדרטי לספריות הסטנדרטיות
שכולל malloc, וללא תשלום, וכל זה.
לכן, להתרחק, אנחנו מתכוונים לפרוש.
בואו ננסה ולוודא שזה אכן הידור.
אנו רואים שהוא עושה, אז אנחנו בדרך הנכונה.
>> בואו לפתוח binary_tree.c שוב.
זה הידור. בואו נרד ולוודא שאנחנו נכניס כמה שיחות לפונקציה, מכיל -
רק כדי לוודא שזה כל מה שטוב ויפה.
לדוגמה, כשעשינו כמה חיפושים בעץ שלנו קודם לכן,
ניסינו לחפש את הערכים 6, 10, ו 1, וידע שהיו 6 בעץ,
10 לא היו בעץ, ו1 לא היה בעץ אחד.
הבה נשתמש שיחות לדוגמה אלה כדרך להבין אם או לא
הפונקציה, מכיל עובדת.
כדי לעשות את זה, אני הולך להשתמש בפונקצית printf,
ואנחנו הולכים להדפיס את התוצאה של קריאה למכילה.
אני הולך לשים במחרוזת "מכיל (% d) = בגלל
אנחנו הולכים לחבר את הערך שאנחנו הולכים לחפש,
ו=% s \ n "ולהשתמש בו כמחרוזת התבנית שלנו.
אנחנו רק הולכים לראות - ממש להדפיס על המסך -
מה שנראה כמו קריאה לפונקציה.
זה לא ממש קריאה לפונקציה.
זה רק חוט שנועד להיראות כמו קריאה לפונקציה.
>> עכשיו, אנחנו הולכים לחבר את הערכים.
אנחנו הולכים לנסות מכילים על 6,
ואז מה שאנחנו הולכים לעשות כאן הוא משתמשים באותו מפעיל משולש.
בואו נראים - מכיל 6 - כך, עכשיו אני כבר הכלתי 6 ואם מכיל 6 הוא נכון,
המחרוזת שאנחנו הולכים לשלוח לאופי פורמט% s
הולך להיות המחרוזת "האמיתית".
בואו לגלול עליו קצת.
אחרת, אנחנו רוצים לשלוח את המחרוזת "מזויפת" אם מכיל 6 חוזר שווא.
זה קצת דבילי למראה, אבל אני חושב שאולי גם להמחיש
מה המפעיל המשולש נראה כמו מאז לא ראינו אותו לזמן מה.
זו תהיה דרך נחמדה, נוחה להבין אם הפונקציה, מכיל עובדת.
אני הולך לגלול חזרה לצד השמאל,
ואני מתכוון להעתיק ולהדביק את הקו הזה כמה פעמים.
זה שינה כמה מהערכים האלה מסביב,
אז זה הולך להיות 1, וזה הולך להיות 10.
>> בשלב זה יש לנו, מכיל פונקציה נחמדה.
יש לנו כמה בדיקות, ונצטרך לראות אם כל זה עובד.
בנקודה זו אנו כתבנו עוד קצת קוד.
הגיע הזמן להפסיק לצאת ולוודא שהכל עדיין הידור.
צא החוצה, ועכשיו בואו ננסה לעשות את העץ בינארי שוב.
ובכן, זה נראה כאילו יש לנו שגיאה,
ויש לנו את זה במפורש הכריז פונקצית ספריית printf.
זה נראה כמו שאנחנו צריכים להגיע וב# כוללים standardio.h.
ועם זה, כל מה שצריך לקמפל. כולנו טוב.
עכשיו בואו ננסה לרוץ עץ בינארי ולראות מה קורה.
הנה אנחנו,. / Binary_tree,
ואנחנו רואים את זה, כמו שציפינו -
כי אנחנו לא יישמנו עדיין מכילים,
או לייתר דיוק, יש לנו פשוט לשים בתמורת שווא -
אנו רואים שזה פשוט חוזר שווא לכולם,
כך שכל עובד על פי רוב די טוב.
>> בואו נחזור ובבעצם ליישם מכיל בשלב זה.
אני הולך לגלול למטה, להתקרב, ו--
זכור, האלגוריתם שהשתמשנו היה שהתחלנו בצומת השורש
ולאחר מכן בכל צומת שאנו פוגשים, אנו עושים השוואה,
ועל סמך זה אנו השוואה העבירו לילד שמאל או לילד הנכון.
זה הולך להיראות דומה מאוד לקוד בינארי החיפוש שכתבו מוקדם יותר בטווח.
כאשר אנו מתחילים, אנחנו יודעים שאנחנו רוצים להחזיק בצומת הנוכחית
שאנחנו מסתכלים, והצומת הנוכחית הולכת להיות מאותחלת לצומת השורש.
ועכשיו, אנחנו הולכים להמשיך דרך העץ,
ולזכור שמצב העצירה שלנו -
כאשר אנו באמת עבדנו דרך הדוגמא ביד -
היה כשנתקלנו בצומת ריקה,
לא כשהסתכלנו על ילד ריק,
אלא כאשר אנו באמת עברנו לצומת בעץ
ונמצא שאנחנו בצומת ריקה.
אנחנו הולכים לחזר עד נוכ אינו שווה null.
ומה אנחנו הולכים לעשות?
אנחנו הולכים לבדוק אם (נוכ -> ערך == ערך),
אז אנחנו יודעים שאנחנו כבר נמצאים על הצומת שאנחנו מחפשים בעצם.
אז הנה, אנחנו יכולים לחזור אמיתיים.
אחרת, אנחנו רוצים לראות אם הערך הוא נמוך מהשווי.
אם הערך של הצומת הנוכחית הוא פחות מהערך שאנחנו מחפשים,
אנחנו הולכים לעבור לצד ימין.
אז, נוכ = נוכ -> right_child; ואחרת, אנחנו הולכים לעבור לשמאל.
נוכ = נוכ -> left_child;. די פשוט.
>> אתה בטח מכיר את הלולאה שנראית דומה מאוד לזו מ
חיפוש בינארי מוקדם יותר בטווח, רק שאז יש לנו עסק עם נמוך, אמצע וגבוה.
הנה, אנחנו רק צריכים להסתכל על ערך נוכחי,
אז זה נחמד ופשוט.
בואו נוודא שהקוד הזה עובד.
ראשית, לוודא שזה הידור. נראה כמו שהיא עושה.
בואו ננסה להפעיל אותו.
ואכן, זה מדפיס את כל מה שציפינו.
היא מוצאת 6 בעץ, אינו מוצא כי 10 10 זה לא בעץ,
ואינו מוצא 1 או בגלל 1 גם לא בעץ.
דברים מגניבים.
>> אוקיי. בואו נחזור למפרט שלנו ולראות מה הלאה.
עכשיו, הוא רוצה להוסיף עוד כמה צומת לעץ שלנו.
הוא רוצה להוסיף 5, 2 ו 8, ולוודא כי מכיל קוד
עדיין פועל כצפוי.
בואו נלך לעשות את זה.
בשלב זה, ולא עושה זאת העתק ודבק מעצבנים שוב,
בואו נכתוב פונקציה בעצם ליצור צומת.
אם אנחנו לגלול למטה כל הדרך לראשית, אנחנו רואים שאנחנו עושים את זה כבר
קוד דומה מאוד שוב ושוב בכל פעם שאנחנו רוצים ליצור צומת.
>> בואו לכתוב פונקציה שתבנה את הצומת עבורנו ולהחזיר אותו.
אני הולך לקרוא לזה build_node.
אני הולך לבנות את צומת עם ערך מסוים.
להתקרב לכאן.
הדבר הראשון שאני הולך לעשות הוא בעצם ליצור מרחב לצומת בערימה.
אז, צומת * n = malloc (sizeof (צומת)), n -> ערך = ערך;
ואז כאן, אני רק הולך לאתחול כל השדות להיות ערכים מתאימים.
וממש בסוף, תחזרו הצומת שלנו.
אוקיי. דבר אחד שיש לציין הוא שפונקציה זו ממש כאן
הולך להחזיר מצביע לזיכרון שכבר ערימה מוקצה.
מה שיפה בכל זה הוא שזו צומת עכשיו -
אנחנו צריכים להכריז עליו בערימה כי אם הכרזת אותו על הערימה
לא הייתי מסוגל לעשות את זה בפונקציה זו כמו זו.
הזיכרון שהייתי יוצא מההיקף
ויהיה חוקי אם ניסינו לגשת אליו בהמשך.
מאז אנחנו מכריזים זכרון ערימה מוקצה,
אנחנו הולכים לעשות כדי לטפל בשחרורו מאוחר יותר
לתכנית שלנו לא תדלוף ממנו שום זיכרון.
אנחנו כבר חתירה על זה גם לכל דבר אחר בקוד
רק לשם פשטות באותה העת,
אבל אם אי פעם לכתוב פונקציה שנראית כך
שם יש לך - חלק קורא לזה malloc או realloc בפנים -
אתה רוצה לוודא שאתה מכניס איזו תגובה כאן שאומר,
היי, אתה יודע, מחזיר צומת ערימה מוקצה אותחלה עם הערך מחוסר הכרה ב.
ואז אתה רוצה לוודא שאתה מכניס איזה פתק שאומר
המתקשר חייב לשחרר הזיכרון חזר.
באופן זה, אם מישהו אי פעם הולך ומשתמש בפונקציה ש,
הם יודעים שכל מה שהם מקבלים בחזרה מהפונקציה
בשלב מסוים יצטרך להיות משוחרר.
>> בהנחה שכל זה טוב ויפה כאן,
אנחנו יכולים לרדת לקוד שלנו ולהחליף את כל שורות אלה ממש כאן
עם קריאות לפונקצית הצומת לבנות שלנו.
בואו לעשות את זה ממש מהר.
חלק האחד שאנחנו לא הולכים להחליף את החלק הזה כאן למטה
בתחתית שבו אנחנו למעשה נמלכד את הבלוטות להצביע לזה,
בגלל שאנחנו לא יכולים לעשות בתפקוד שלנו.
אבל, בואו נעשה שורש = build_node (7); צומת * 3 = build_node (3);
צומת * 6 = build_node (6); צומת * 9 = build_node (9);.
ועכשיו, אנחנו גם רוצים להוסיף לצומת -
צומת * 5 = build_node (5); צומת * 8 = build_node (8);
ומה הייתה בצומת האחרת? בואו לראות כאן. רצינו גם להוסיף 2 -
צומת * 2 = build_node (2);.
אוקיי. בשלב זה, אנחנו יודעים שיש לנו 7, 3, 9, ו 6
כל קווים למעלה כראוי, אבל מה לגבי 5, 8, ו2?
כדי לשמור על הכל בצו המתאים,
אנו יודעים שזכותה של ילדת 3 היא 6.
לכן, אם אנחנו הולכים להוסיף 5,
5 שייכים גם בצד הימני של העץ ש3 הוא השורש,
כך 5 שייכים כילד השמאלי של 6.
אנחנו יכולים לעשות את זה באומרו, שישה -> left_child = 5;
ולאחר מכן 8 שייכים כילד השמאלי של 9, אז 9 -> left_child = 8;
ואז 2 הם הילד השמאלי של 3, כך שאנו יכולים לעשות את זה כאן - -> left_child = 2;.
אם אתה לא ממש פעלת יחד עם זה, אני מציע לך למשוך את זה בעצמך.
>> אוקיי. בואו נשמור את זה. בואו נצא ולוודא שזה הידור,
ואז אנחנו יכולים להוסיף בשיחות מכילה.
נראה כאילו כל מה שעדיין הידור.
בואו נלך ובאוסיף בחלק מכיל שיחות.
שוב, אני הולך לעשות קצת העתקה והדבקה.
עכשיו בואו לחפש 5, 8, ו 2. אוקיי.
בואו נוודא שכל זה עדיין נראה טוב. גדול! שמור ולהתפטר.
עכשיו בואו נעשה, לקמפל, ועכשיו בואו נרוץ.
מהתוצאות, זה נראה כאילו כל מה שהוא עובד רק נחמד וטוב.
גדול! אז עכשיו יש לנו, מכיל לתפקד בכתב.
בואו לעבור ולהתחיל לעבוד על איך להכניס את צומת בעץ
מאז, כמו שאנחנו עושים את זה עכשיו, דברים הם לא מאוד יפים.
>> אם יחזור למפרט,
הוא מבקש מאתנו לכתוב פונקציה שנקראת להוסיף - שוב, וחזר bool
לשאלה אם אנחנו באמת יכולים להכניס את הצומת לעץ -
ולאחר מכן הערך להכניס לתוך העץ מוגדר כ
הוויכוח רק להוספת הפונקציה שלנו.
אנחנו נחזור אמיתיים אם אנחנו אכן יכולים להכניס את הערך המכיל צומת לעץ,
מה שאומר שאנחנו, אחד, היו מספיק זיכרון,
ואז שתיים, וצומת שלא קיימת כבר בעץ מאז -
נזכור, אנחנו לא הולכים ליש ערכים כפולים בעץ, רק כדי לעשות את הדברים פשוטים.
אוקיי. בחזרה לקוד.
לפתוח אותו. קרב קצת, ואז גלול למטה.
בואו נשים את פונקציית ההוספה ימנית מעל למכיל.
שוב, זה הולך להיקרא להכניס bool (int ערך).
תן לזה קצת יותר מקום, ולאחר מכן, כברירת מחדל,
בואו נשים בתמורת שווא ממש בסוף.
עכשיו למטה בתחתית, בואו נלך קדימה ובמקום לבנות את צומת באופן ידני
בעצמנו וחיווט העיקרי אותם להצביע לזה כמו שאנחנו עושים,
אנחנו מסתמכים על הוספת הפונקציה שלנו לעשות את זה.
אנחנו לא מסתמכים על הוספת הפונקציה שלנו כדי לבנות את כל העץ מהתחלה עדיין,
אלא שאנחנו הולכים להיפטר מהקווים האלה - אנחנו נטפל הערה את השורות אלה -
שבונה את צומת 5, 8, ו 2.
ובמקום זאת, נכניס שיחות להוספת הפונקציה שלנו
כדי לוודא שזה באמת עובד.
הנה אנחנו מתחילים.
>> עכשיו אנחנו כבר הערנו את השורות האלה.
יש לנו 7, 3, 9, ו 6 רק בעץ שלנו בשלב זה.
כדי לוודא שכל זה עובד,
אנחנו יכולים להתרחק, להפוך את העץ בינארי שלנו,
להפעיל אותו, ואנחנו יכולים לראות שמכילים עכשיו אומרים לנו שאנחנו תקועים לגמרי נכונים -
5, 8, ו 2 כבר לא בעץ.
חזור לקוד,
ואיך אנחנו הולכים להכניס?
זכור את מה שעשינו כאשר אנחנו בעצם החדרה 5, 8, ו 2 בעבר.
שחקנו משחק שבו התחיל Plinko בשורש,
ירד עץ אחד על ידי אחד אחד
עד שמצאנו את הפער המתאים,
ואז אנחנו נקווים בצומת בנקודה המתאימה.
אנחנו הולכים לעשות את אותו דבר.
זה בעצם כמו לכתוב הקוד שבו השתמש במכיל פונקציה
כדי למצוא את הנקודה שבה צריכה להיות על הצומת,
ואז אנחנו פשוט הולכים להכניס את הצומת ממש שם.
בואו נתחיל לעשות את זה.
>> אז יש לנו צומת * נוכ = שורש, אנחנו פשוט הולכים לעקוב מכילים קוד
עד שאנחנו מוצאים שזה לא ממש עובד בשבילנו.
אנחנו הולכים לעבור את העץ בזמן האלמנט הנוכחי הוא לא ריק,
ואם אנו מוצאים הערך של נוכ שווה לערך שבו אנו מנסים להוסיף -
כן, זה אחד מהמקרים שבם אנחנו לא יכולים בעצם להכניס את הצומת
לעץ, כי זה אומר שיש לנו ערך כפול.
כאן אנחנו בעצם הולכים תמורת שווא.
עכשיו, אחר אם הערך של נוכ הוא פחות מערך,
עכשיו אנחנו יודעים שאנחנו עוברים לימין
מכיוון שהערך שייך במחצית הימנית של עץ נוכ.
אחרת, אנחנו הולכים לעבור לשמאל.
זה ביסודו מכיל לתפקד ממש שם.
>> בשלב זה, לאחר שנשלים את הלולאה בזמן הזה,
מצביע נוכ הולך להיות הצבעה על null
אם הפונקציה עדיין לא חזרה.
לפיכך, אנו נתקלים נוכ במקום שבו אנחנו רוצים להוסיף את הצומת החדשה.
מה שנותר לעשות הוא בעצם לבנות את הצומת החדשה,
שאנחנו יכולים לעשות די בקלות.
אנחנו יכולים להשתמש בפונקצית הצומת לבנות סופר השימושית שלנו,
ומשהו שלא עשו לפני כן -
אנחנו פשוט סוג של מובן מאליו, אבל עכשיו אנחנו עושים רק כדי לוודא -
שנבדוק כדי לוודא שהערך המוחזר על ידי צומת החדש היה למעשה
לא ריק, כי אנחנו לא רוצים להתחיל גישה לזיכרון שאם זה הוא ריק.
אנחנו יכולים לבדוק כדי לוודא שצומת חדשה היא לא שווה אפס.
או במקום זאת, אנחנו יכולים רק לראות אם זה באמת הוא ריק,
ואם הוא ריק, אז אנחנו יכולים רק לחזור שווא מוקדם.
>> בנקודה זו, יש לנו לחוט צומת חדש למקום הראוי לו בעץ.
אם אנחנו מסתכלים אחורה ובעיקריים שבו היינו ממש בערכי חיווט לפני,
אנו רואים שהדרך שאנחנו עושים את זה כאשר אנחנו רוצים לשים 3 בעץ
היו לגשת לילד השמאלי של שורש.
כאשר אנחנו שמים 9 בעץ, לא היו לנו הגישה לילד הימני של השורש.
היינו זקוק למצביע להורה כדי לשים ערך חדש לתוך העץ.
גלילה מעלה חזרה ללהוסיף, זה לא הולך ממש לעבוד כאן
משום שאין לנו מצביע הורה.
מה שאנחנו רוצים להיות מסוגלים לעשות הוא, בשלב זה,
לבדוק את ערכו של ההורה ולראות - הטוב, אלוהים,
אם הערך של ההורה הוא פחות משוויו הנוכחי,
אז הילד את זכותו של ההורה צריך להיות צומת החדש;
אחרת, הילד השמאלי של ההורה צריך להיות צומת החדש.
אבל, אין לנו מצביע אב זה עדיין לא.
>> על מנת לקבל את זה, אנחנו באמת נצטרך לעקוב אחר זה כמו שאנחנו הולכים דרך העץ
ולמצוא את המקום המתאים בלולאה שלנו לעיל.
אנחנו יכולים לעשות את זה על ידי גלילה חזרה לחלק העליון של הוספת הפונקציה שלנו
ומעקב משתנה מצביע אחר בשם האב.
אנחנו הולכים להגדיר אותו שווים ל null בתחילה,
ולאחר מכן בכל פעם שאנו עוברים את העץ,
אנחנו הולכים להגדיר את מצביע ההורה להתאים את המצביע הנוכחי.
הגדרת הורה שווה לנוכ.
בדרך זו, בכל פעם שאנו עוברים,
אנחנו הולכים לוודא שכמצביע הנוכחי מקבל מוגדל
מצביע ההורה מלווה את זה - פשוט רמה אחת גבוה יותר מהמצביע הנוכחי בעץ.
כי הכל נראה די טוב.
>> אני חושב שהדבר אחד שאנחנו רוצים לשנות את זה הוא לבנות null צומת חוזרת.
על מנת לקבל לבנות צומת בעצם לחזור בהצלחה ריקה,
נצטרך לשנות את הקוד ש,
כי כאן, אנחנו אף פעם לא נבדקנו כדי לוודא שmalloc חזר מצביע תקף.
לכן, אם (n = NULL!), אז -
אם malloc חזר מצביע תקף, ואז תוכל לאתחל אותו;
אחרת, אנחנו פשוט נחזור ושיהיו בסופו חוזר ריק עבורנו.
עכשיו כל מה שנראה די טוב. בואו נוודא שזה באמת הידור.
הפכו עץ בינארי, ואוה, יש לנו כמה דברים שקורים כאן.
>> יש לנו הצהרה המרומזת של פונקציה לבנות צומת.
שוב, עם המהדרים האלה, אנחנו הולכים להתחיל בחלק העליון.
מה משמעות של זה הוא שאני מתקשר לבנות צומת לפני שהכרזתי עליו בפועל.
בואו נחזור לקוד ממש מהר.
לגלול למטה, ואכן, הוספת הפונקציה שלי הכריזה
מעל פונקצית הצומת לבנות,
אבל אני מנסה להשתמש לבנות צומת הפנימית של תותב.
אני מתכוון ללכת ובהעתק - ומדביק את דרך תפקוד הצומת לבנות כאן בחלק העליון.
בדרך זו, אני מקווה שזה יעבוד. בואו לתת את זה עוד ללכת.
עכשיו כל זה הידור. כל טוב.
>> אבל בנקודה זו, יש לנו לא ממש קרא הוספת הפונקציה שלנו.
אנחנו רק יודעים שזה הידור, אז בואו נלך ובלשים כמה שיחות פנימה
בואו לעשות את זה בפונקציה העיקרית שלנו.
כאן, הערנו את 5, 8, ו 2,
ואז אנחנו לא נמלכד אותם כאן למטה.
בואו לעשות כמה שיחות כדי להוסיף,
ובואו גם להשתמש באותו סוג של חומר שבו השתמש
כאשר בצענו שיחות printf אלה כדי לוודא שהכל לא מקבל הוכנס כראוי.
אני מתכוון להעתיק ולהדביק,
ובמקום מכיל אנחנו הולכים לעשות להוסיף.
ובמקום 6, 10, ו 1, אנחנו הולכים להשתמש 5, 8, ו 2.
זה אמור בתקווה להכניס 5, 8, ו 2 לעץ.
Compile. כל טוב. עכשיו אנחנו באמת נרוץ התכנית שלנו.
>> הכל חזר שווא.
אז, 5, ​​8, ו 2 לא הלך, וזה נראה כאילו, מכיל לא מצא אותם.
מה קורה? בואו להקטין את התצוגה.
הבעיה הראשונה הייתה שהוספה נראה לחזור שקר,
וזה נראה כאילו זה בגלל שיצאנו בקריאת שווא חזרתנו,
ואנחנו אף פעם לא ממש חזרנו נכונים.
אנחנו יכולים להגדיר זאת.
הבעיה השנייה היא שעכשיו, גם אם אנחנו עושים - לשמור את זה, תפסיק עם זה,
לרוץ לעשות שוב, יש לו לאסוף, ואז להפעיל אותו -
אנו רואים שמשהו אחר קרה כאן.
5, 8, ו 2 עדיין לא נמצאו בעץ.
אז, מה קורה?
>> בואו נסתכל על זה בקוד.
בואו נראה אם ​​אנחנו יכולים להבין את זה.
אנחנו מתחילים עם ההורה שאינו ריק.
אנו קובעים את המצביע למצביע השווה השורש הנוכחי,
ואנחנו הולכים לעבוד דרכנו במורד העץ.
אם הצומת הנוכחית היא לא ריקה, אז אנחנו יודעים שאנחנו יכולים לעבור אותו קצת.
אנו קובעים המצביע האם שלנו להיות שווה למצביע הנוכחי,
בדקתי את הערך - אם הערכים הזהים חזרנו שווא.
אם הערכים הם פחות עברנו לימין;
אחרת, עברו לצד השמאל.
ואז אנחנו בונים צומת. אני להתקרב קצת.
והנה, אנחנו הולכים לנסות לחווט את הערכים להיות אותו הדבר.
מה קורה? בואו לראות אם אולי Valgrind יכול לתת לנו רמז.
>> אני אוהב להשתמש Valgrind רק בגלל Valgrind ממש מהר ריצות
ואומר לך אם יש שגיאות זיכרון.
כאשר אנו מפעילים Valgrind בקוד,
כפי שאתה יכול לראות את להיט here--Valgrind./binary_tree--and זכות להיכנס.
אתה רואה שלא היה לנו כל שגיאת זיכרון, כך זה נראה כאילו הכול בסדר עד כה.
יש לנו כמה דליפות זיכרון, שאנחנו יודעים, כי אנחנו לא
קורה לשחרור כל צומת שלנו.
בואו ננסה לרוץ GDB כדי לראות מה באמת קורה.
אנחנו נעשה את gdb. / Binary_tree. זה הדליק את בסדר גמור.
בואו נקבענו נקודת הפסקה על הוספה.
בואו לרוץ.
זה נראה כאילו אנחנו מעולם לא קראנו להוסיף בפועל.
זה נראה כמו הבעיה הייתה רק שכשאני השתניתי למטה בעיקרי -
כל השיחות הללו מprintf מכיל -
למעשה, לא השתנה אלה להתקשר להוסיף.
עכשיו בואו לנסות את זה. בואו לקמפל.
הכל נראה טוב שם. עכשיו בואו ננסה להפעיל אותו, לראות מה קורה.
בסדר! הכל נראה די טוב שם.
>> הדבר האחרון שחושבים עליו הוא, האם יש מקרי קצה כדי להכניס את זה?
ומתברר כי, ובכן, מקרה קצה אחד שתמיד מעניין לחשוב על
הוא, מה קורה אם העץ שלך הוא ריק ואתה קורא להוספת פונקציה זו?
האם זה יצליח? ובכן, בואו ננסה את זה.
- Binary_tree ג. -
הדרך שאנחנו הולכים לבדוק את זה, אנחנו הולכים לרדת לפונקציה העיקרית שלנו,
במקום חיווט צומת האלה כמו זה ו,
אנחנו פשוט הולכים להעיר את כל הדבר הזה,
במקום חיווט את עצם וצומת,
אנחנו באמת יכולים פשוט ללכת קדימה ולמחוק את כל זה.
אנחנו הולכים לעשות כל מה ששיחה להוסיף.
אז, בואו נעשה - במקום 5, 8, ו 2, אנחנו הולכים להכניס 7, 3, ו 9.
ואז אנחנו גם רוצים להכניס 6 גם כן.
שמור. צא. הפוך עץ בינארי.
את כל זה הידור.
אנחנו רק יכולים להפעיל אותו כפי שהיא ולראות מה קורים,
אבל זה גם הולך להיות באמת חשוב לוודא כי
אין לנו את כל שגיאות זיכרון,
מאז זה אחד ממקרי הקצה שלנו, כי אנחנו יודעים עליו.
>> בואו נוודא שזה עובד גם תחת Valgrind,
שאנחנו עושים רק על ידי הפעלת Valgrind. / binary_tree.
זה נראה כאילו אנחנו אכן יש שגיאה אחת מהקשר אחד -
יש לנו אשמת פילוח זה.
מה קרה?
Valgrind בעצם אומר לנו איפה זה.
זום החוצה קצת.
זה נראה כמו שזה קורה בהוספת הפונקציה שלנו,
שם יש לנו קריאה לא חוקית בגודל 4 בכנס, קו 60.
בואו נלך אחורה ולראות מה קורה כאן.
זום החוצה ממש מהר.
אני רוצה לוודא שזה לא הולך לקצה של המסך כדי שנוכל לראות את הכל.
משוך כי בקצת. אוקיי.
לגלול למטה, והבעיה היא ממש כאן.
מה קורה אם אנחנו יורדים והצומת הנוכחית שלנו היא כבר ריקה,
צומת אבינו היא ריקה, כך שאם אנחנו מסתכלים על חלקו עליון, ממש כאן -
אם לולאה בזמן זה לא באמת מבצעת
משום שהערך הנוכחי שלנו הוא ריק - השורש שלנו הוא ריק כל כך נוכ הוא ריק -
אז האם שלנו אף פעם לא מקבל מוגדר נוכ או לערך חוקי,
כך, ההורה גם יכול להיות ריק.
אנו צריכים לזכור שכדי לבדוק
עד שהגענו לכאן, ואנחנו מתחילים גישת ערכו של ההורה.
אז, מה קורה? ובכן, אם ההורה הוא ריק -
אם (הורה == NULL) - אז אנחנו יודעים ש
אסור שיהיה שום דבר בעץ.
אנחנו חייבים להיות מנסים להכניס אותו בשורש.
אנחנו יכולים לעשות את זה רק על ידי הגדרת השורש השווה לצומת החדשה.
ואז, בשלב זה, אנחנו לא ממש רוצים לעבור את הדברים אחרים.
במקום זאת, ממש כאן, אנחנו יכולים לעשות גם אחרים, אם-אחרים,
או שאנחנו יכולים לשלב את הכל כאן באחר,
אבל כאן אנחנו פשוט משתמשים אחרים ולעשות את זה ככה.
עכשיו, אנחנו הולכים לבדיקה כדי לוודא שההורים שלנו הם לא ריק
לפני כן בעצם מנסה לגשת לשדותיו.
זה יעזור לנו להימנע מאשמת הפילוח.
לכן, נפרוש, להתרחק, לקמפל, לרוץ.
>> אין שגיאות, אבל עדיין יש לנו חבורה של דליפות זיכרון
בגלל שלא לשחרר את כל צומת שלנו.
אבל, אם אנחנו הולכים לכאן, ואנחנו מסתכלים על התדפיס שלנו,
אנו רואים כי, ובכן, נראים שכולנו היו חוזרים מוסיף אמיתיים, וזה טוב.
מחדיר נכונים כולם,
ולאחר מכן את השיחות מכילה המתאימות הן גם נכונות.
>> עבודה טובה! זה נראה כאילו אנחנו כתבנו להכניס בהצלחה.
זה כל מה שיש לנו למפרט סט בעית השבוע.
אתגר אחד כיף לחשוב עליו הוא איך אתה בעצם ללכת ב
וללא כל צומת בעץ הזה.
אנחנו יכולים לעשות במספר הדרכים שונות, כך,
אבל אני אשאיר את זה תלוי בך כדי ניסוי,
וכאתגר כיף, לנסות ולוודא שאתה יכול לוודא
דו"ח שValgrind זה לא מחזיר שגיאות ואין דליפות.
>> מזל טוב על סט בעיית קידוד האפמן השבוע הזה,
ונתראה בשבוע הבא!
[CS50.TV]