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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אז הנה הרשימה המקושרת שלנו. זה במקביל מכיל ארבעה יסודות. ועוד בצורה מושלמת הנה מחסנית המכילה ארבעה מרכיבים. ונניח שעכשיו אנחנו רוצים לדחוף פריט חדש על ערימה זו. ואנחנו רוצים לדחוף חדשים פריט המידע שהערך הוא 12. ובכן מה שאנחנו הולכים לעשות? ובכן ראשון שאנחנו הולכים חלל malloc, דינמי להקצות שטח לצומת חדשה. וכמובן מייד לאחר אנחנו עושים שיחה לmalloc אנחנו תמיד הקפד לבדוק null, כי אם יש לנו אפס בחזרה יש איזה סוג של בעיה. אנחנו לא רוצים dereference null ש מצביע או שאתה תסבול אשמת SEG. זה לא טוב. אז אנחנו כבר malloced של הצומת. אנחנו נניח שהיינו לנו הצלחה כאן. אנחנו הולכים לשים 12 ל שדה הנתונים של הצומת. עכשיו אתה זוכר שהמצביעים שלנו המהלכים הבאים ולכן אנחנו לא לשבור את השרשרת? יש לנו כמה אפשרויות כאן, אבל רק אחד שהולך להיות בטוח הוא להגדיר חדשות הבאות מצביע ל נקודה לראש הרשימה הישנה או מה יהיה בקרוב ראש ישן של הרשימה. ועכשיו שכולנו אלמנטים משורשרים יחד, אנחנו רק יכולים להעביר את הרשימה להצביע לאותו המקום שעושה חדשים. ויש לנו עכשיו ביעילות דחף אלמנט חדש על החלק הקדמי של המחסנית. 

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

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

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

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