[Powered by Google Translate] [סעיף 6: פחות נוח] [נייט Hardison] [אוניברסיטת הרווארד] [זה CS50.] [CS50.TV] בסדר. ברוכים באים לסעיף 6. השבוע, אנחנו הולכים לדבר על מבני נתונים בסעיף, בעיקר בגלל בעית שבוע זה נקבע על spellr עושה קבוצה שלמה של חקר מבנה נתונים אחר. יש חבורה של דרכים שונות אתה יכול ללכת עם סט הבעיה, וככל שיותר מבני הנתונים אתה יודע עליו, דברים מגניבים יותר שאתה יכול לעשות. 

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

אז מה יש לנו כאן, זה דומה למה שהוצג בהרצאה, למעט בהרצאה הצגנו את זה עם ints לעומת * של char. זה הולך להיות ערימה שחנויות מה? דניאל? מה אנחנו אחסון במחסנית זה? [דניאל] מייתרים? >> אנו אחסון מחרוזות בערימה זה, בדיוק. כל מה שאתה צריך כדי ליצור מחסנית הוא מערך מקיבולת מסוימת, אשר במקרה זה, הקיבולת הולכת להיות בכל הכובעים כי זה קבוע. ואז, בנוסף למערך, כל מה שאנחנו צריכים לעקוב הוא הגודל הנוכחי של המערך. דבר אחד לציין כאן שזה די מגניב הוא שאנו יוצרים את מבנה הנתונים נערם על גבי מבנה נתונים אחרים, המערך. ישנן דרכים שונות ליישום ערימות. אנחנו לא עושים את זה עדיין לא, אבל אני מקווה שאחרי שעושה את הבעיות של הרשימה מקושרת, תראה איך אתה יכול בקלות ליישם ערימה על גבי רשימה מקושרת גם כן. אבל לעת עתה, אנו נשארים עם את המערכים. אז שוב, כל מה שאנחנו צריכים הוא מערך ואנחנו פשוט צריכים לעקוב אחר הגודל של המערך. [סם] סליחה, למה זה שאמרת הערימה של על גבי המייתרים? לי זה נראה כמו המייתרים נמצאים במחסנית. [Hardison] כן. אנחנו יוצרים, אנחנו לוקחים את מבנה נתוני המערך שלנו - זו שאלה גדולה. אז השאלה היא למה, לאנשים שצופים באינטרנט, למה אנחנו אומרים שהערימה היא על גבי המייתרים, כי כאן זה נראה כמו בחוטים נמצאים בתוך הערימה? וזה לגמרי במקרה. מה שהתכוונתי אליו היה שיש לנו מבנה נתוני מערך. יש לנו מערך של char * s, זה מערך של מחרוזות, ואנחנו הולכים להוסיף לזה על מנת ליצור מבנה הנתונים המוערמים. 

כך שהמגדל הוא מעט יותר מורכב ממערך. אנחנו יכולים להשתמש במערך לבנות ערימה. אז זה מה שאנחנו אומרים שהערימה בנויה על גבי מערך. כמו כן, כמו שאמרתי קודם, אנחנו יכולים לבנות ערימה על גבי רשימה מקושרת. במקום להשתמש במערך להחזיק האלמנטים שלנו, אנחנו יכולים להשתמש ברשימה מקושרת להחזיק האלמנטים שלנו ולבנות את הערימה סביב זה. בואו נעבור על כמה דוגמאות, מסתכל על קוד מסוים, כדי לראות מה באמת קורה כאן. בצד השמאל, שזרקתי את מה שstruct המחסנית היה נראה כמו בזיכרון אם קיבולת הוגדרה # להיות ארבעה. יש לנו המערך דמות * ארבעה היסוד שלנו. יש לנו מייתרים [0], מחרוזות [1], מחרוזות [2], מחרוזות [3], ולאחר מכן שהמקום האחרון למספר השלם בגודל שלנו. האם זה הגיוני? אוקיי. זה מה שקורה אם מה שאני עושה בצד ימין, שיהיה הקוד שלי, הוא פשוט להכריז struct, struct נערם בשם זה. זה מה שאנחנו מקבלים. זה מקובע את טביעת רגל זה בזיכרון. השאלה הראשונה כאן היא מה היא התוכן של struct מחסנית זה? נכון לעכשיו הם לא, אבל הם לא לגמרי כלום. הם זה סוג של אשפה. אין לנו מושג מה יש בם. כאשר אנו מצהירים של מחסנית, אנחנו רק לזרוק שעל גבי זיכרון. זה כמו סוג של הכרזה אני int ולא מאתחל אותו. אתה לא יודע מה יש שם. אתה יכול לקרוא מה יש שם, אבל זה לא יכול להיות סופר שימושי. דבר אחד שאתה רוצה תמיד לזכור לעשות הוא לאתחל את כל מה שצריך להיות מאותחל. במקרה זה, אנחנו הולכים לאתחל את הגודל להיות אפס, בגלל זה הולך להתברר חשוב מאוד עבורנו. אנחנו יכולים להמשיך ולאתחל את כל המצביעים, כל S * char, להיות קצת ערך מובן, כנראה ריק. אבל זה לא לגמרי הכרחי שאנחנו עושים את זה. 

עכשיו, שתי פעולות העיקריות שעל ערימות הן? מישהו זוכר מהרצאה מה אתה עושה עם ערימות? כן? [סטלה] דחיפות ופקיעה? >> בדיוק. דוחף ומכניס הם שתי פעולות העיקריות בערימות. ומה דחיפה עושה? >> זה מכניס משהו על הראש מהמחסנית, ולאחר מכן המנקר לוקח אותו. [Hardison] בדיוק. אז דוחף דוחף משהו בראש הערימה. זה כמו צוות האוכל לשים את מגש אוכל על הדלפק. ופקיעה היא לוקחת מגש אוכל מהערימה. הבה תסקור כמה דוגמאות למה שקורה כאשר אנחנו דוחפים דברים לתוך הערימה. אם היינו לדחוף את המחרוזת 'שלום' על המחסנית שלנו, זה מה שהתרשים שלנו היה נראה כמו עכשיו. ראה מה קורה? אנחנו נדחקים לאלמנט הראשון של מערך המחרוזות שלנו ואנחנו העלינו ספירת הגודל שלנו כדי להיות 1. אז אם אנחנו מסתכלים על ההבדל בין שתי שקופיות, כאן היה 0, הנה לפני הדחיפה. הנה היא אחרי הדחיפה. לפני הדחיפה, לאחר הדחיפה. ועכשיו יש לנו יסוד אחד במחסנית שלנו. זה המחרוזת "שלום", וזהו זה. כל דבר אחר במערך, במערך המחרוזות שלנו, הוא עדיין זבל. יש לנו את זה לא אותחל. בואו נגיד שאנחנו דוחפים מחרוזת אחרת על המחסנית שלנו. אנחנו הולכים לדחוף את "עולם" בשלב זה. אז אתה יכול לראות את "העולם" כאן הולך על "שלום", וספירת הגודל הולכת עד 2. עכשיו אנחנו יכולים לדחוף "CS50", ושילכו על דף שוב. אם אחזור, אתה יכול לראות איך אנחנו דוחפים דברים בראש הערימה. ועכשיו אנחנו מגיעים לפופ. כשצצנו משהו מהערימה, מה קרה? מישהו רואה את ההבדל? זה די עדין. [סטודנטים] הגודל. >> כן, הגודל השתנה. 

מה עוד היית צפוי להשתנות? [סטודנטים] בחוטים, מדי. >> ימני. המייתרים מדי. מתברר כי כשאתה עושה את זה ככה, כי אנחנו לא מעתיקים את האלמנטים למחסנית שלנו, אנחנו באמת לא צריכים לעשות שום דבר, אנחנו פשוט יכולים להשתמש בגודל כדי לעקוב אחר מספר דברים במערך שלנו כך שכאשר אנו קופצים שוב, ושוב אנחנו רק הפחה את הגודל שלנו 1. אין צורך ממש להיכנס ולהחליף שום דבר. סוג של פאנקי. מתבררים שאנחנו בדרך כלל פשוט להניח לדברים כי זה פחות עבודה עבורנו לעשות. אם אנחנו לא צריכים לחזור ולדרוס משהו, אז למה לעשות את זה? לכן, כאשר אנו קופצים פי שניים משל המחסנית, כל מה שעושה הוא הפחתה בגודל כמה פעמים. ושוב, זה רק בגלל שאנחנו לא מעתיקים דברים למחסנית שלנו. כן? קדימה. [סטודנטים, לא מובן] >> ואז מה קורה כשאתה דוחף משהו שוב? כשאתה דוחף משהו שוב, לאן זה הולך? לאן זה הולך, בזיליקום? >> לתוך מייתרים [1]? >> ימני. למה זה לא נכנס למייתרים [3]? [Basil] כי זה שכח שיש משהו במייתרים [1] ו [2]? [Hardison] בדיוק. המחסנית שלנו, בעצם, "שכחה" כי היא מחזיקה בכל דבר במייתרים [1] או מחרוזות [2], ולכן כאשר אנו דוחפים "woot", זה פשוט מכניס את זה לתוך האלמנט במייתרים [1]. האם יש שאלות על איך זה עובד, ברמה בסיסית? [סם] אז זה לא דינמי בכל דרך, במונחים של כמות או במונחים של גודל המחסנית? [Hardison] בדיוק. זה - העניין הוא שזה לא היה מחסנית באופן דינמי growning. זו מחסנית שיכולה להכיל לכל היותר 4 char * s, ברוב ארבעה דברים. אם היינו מנסה לדחוף את דבר ה ', מה לדעתך צריך לקרות? [סטודנטים], לא ברור, [Hardison] בדיוק. יש מספר דברים שיכולים לקרות. זה יכול צינוק אשמה, תלוי במה שהיינו - איך בדיוק אנחנו מיישמים העורפיים. זה יכול להחליף. זה היה יכול להיות שהצפת המאגר שדברנו עליו בכיתה. מה יהיה הדבר הפשוט ביותר שעשויה להיות מוחלפים אם ניסיתי לדחוף את דבר נוסף במחסנית שלנו? כן, כך ציין לגלישת מאגר. מה יכול להיות הדבר שייכתב מעל או דרכו על אם גלשו בטעות על ידי מנסה לדחוף דבר נוסף? [דניאל, לא מובן] אפשרי. >> אבל תחילה, מה עלול לקרות? מה אם אנסה לדחוף דבר רביעי? זה יכול להחליף את הגודל, לפחות בתרשים הזיכרון הזה שיש לנו. 

במפרט סט הבעיה, וזה מה שאנחנו הולכים להיות יישום היום, מה שאנחנו רוצים לעשות הוא פשוט לחזור שווא. שיטת הדחיפה שלנו הולכת להחזיר ערך בוליאני, וכי הערך בוליאני יהיה נכון אם יצליח לדחוף וכוזב אם אנחנו לא יכולים לדחוף משהו יותר בגלל המחסנית מלאה. בואו נעבור קצת מזה קוד עכשיו. הנה פונקצית הדחיפה שלנו. פונקצית הדחיפה שלנו לערימה הולכת לקחת במחרוזת לשים על הערימה. זה הולך להחזר אמיתי אם המחרוזת נדחפה בהצלחה באופן אחר מחסנית וכוזבת. כל הצעה על מה שעשוי להיות דבר ראשון טוב לעשות כאן? [סם] אם גודל שווה יכולת אז לחזור שווא? [Hardison] בינגו. עבודה יפה. אם הגודל הוא היכולת, אנחנו הולכים לחזור שווא. אנחנו לא יכולים לשים שום דבר יותר במחסנית שלנו. אחרת, אנחנו רוצים לשים משהו על ראש הערימה. מהו "ראש הערימה," בהתחלה? [דניאל] גודל 0? >> גודל 0. מהו ראש הערימה לאחר יש דבר אחד במחסנית? מסים, אתה יודע? [מסים] אחד. גודל >> הוא אחד, בדיוק. אתה כל זמן מוסיף לגודל, ובכל פעם שאתה מכניס אלמנט החדש בגודל האינדקס במערך. אנחנו יכולים לעשות את זה עם סוג כזה של אונייה אחת, אם זה נשמע הגיוני. אז יש לנו מערך המחרוזות שלנו, אנחנו הולכים לגשת אליו במדד הגודל, ואנחנו פשוט הולכים לאחסון * char לשם. שים לב איך אין העתקת מחרוזת הולכת פה, אין הקצאה דינמית של זיכרון? ואז מסים הביאו את מה שיש לנו עכשיו לעשות, משום שעלינו מאוחסנים המחרוזת במקום המתאים במערך, והיא אמרה שיש לנו כדי להגדיל את הגודל על ידי אחד, כך שאנחנו מוכנים לדחיפה הבאה. אז אנחנו יכולים לעשות את זה עם s.size + +. בנקודה זו, יש לנו דחפנו לתוך המערך שלנו. מה הדבר האחרון שאנחנו צריכים לעשות? [סטודנטים] תשואה אמיתית. >> חזרה אמיתי. אז זה די פשוט, קוד די פשוט. לא יותר מדי. לאחר שעטפת את הראש סביב איך המחסנית עובדת, זה די פשוט ליישום. 

עכשיו, החלק הבא של זה צץ מחרוזת את הערימה. אני הולך לתת לכם קצת זמן לעבוד על זה קצת. זה כמעט בעצם הפך ממה שעשינו כאן בדחיפה. מה שעשיתי הוא למעשה - אופס. אני כבר מאותחל מכשיר לכאן, ובמכשיר, אני משכתי את הבעיה להגדיר 5 מפרט. אם להתמקד בכאן, אנו יכולים לראות שאני בcdn.cs50.net/2012/fall/psets/pset5.pdf. האם אתם להוריד את הקוד הזה שהוא נמצא כאן, section6.zip? בסדר. אם עדיין לא עשה את זה, לעשות את זה ממש עכשיו, ממש במהירות. אני אעשה את זה בחלון המסוף שלי. אני דווקא עשיתי את זה כאן. כן. כן, סם? >> יש לי שאלה למה אתה אומר סוגריים של s.string של גודל = str? מהו רחוב? האם זה מוגדר איפשהו לפני, או - הו, ברחוב * char? [Hardison] כן, בדיוק. זה היה הוויכוח. >> אה, בסדר. סליחה. [Hardison] אנו מציינים את המחרוזת לדחוף אותו פנימה השאלה האחרת שעלולה לצוץ שאנחנו לא ממש דברנו עליו כאן הייתה אנו לוקחים כמובן מאליו שיש לנו משתנים זה נקרא S שהיה בהיקף ונגיש לנו. אנחנו לקחנו כמובן מאליו שזה היה struct מחסנית זו. אז במבט לאחור על קוד דחיפה זו, אתה יכול לראות שאנחנו עושים את דברים במחרוזת הזאת שיש עבר ב אבל אז פתאום, אנחנו ניגשים s.size, כמו כאשר s לא בא? בקוד שאנחנו הולכים להסתכל בארכיון המדור ואז הדברים שתוכלו לעשות בבעיה שלך קובע, שעשינו המחסנית שלנו struct גלובלי משתנית כך שיכול להיות לנו גישה אליו בכל הפונקציות השונות שלנו מבלי ידני כדי להעביר אותו סביב ולהעביר אותו על ידי הפניה, לעשות את כל דברים כאלה אליו. אנחנו רק מרמים קצת, אם נרצה, כדי לעשות את הדברים יותר נחמד. וזה משהו שאנחנו עושים כאן כי זה בשביל כיף, זה יותר קל. לעתים קרובות, תוכל לראות אנשים עושים את זה אם יש להם מבנה נתונים אחד גדול זה מופעל במסגרת התכנית שלהם. 

בואו נחזור שוב למכשיר. האם כולם מקבלים section6.zip הצלחה? כולם לפתוח אותו באמצעות section6.zip unzip? אם אתה הולך לספריית סעיף 6 - אחח, בכל המקום - ולך לרשום את כל מה שיש פה, אתה רואה שיש לך שלושה קבצים. ג שונים. יש לך תור, SLL, שהיא רשימת ביחידים למדד, ומחסנית. אם אתה פותח את stack.c, אתה יכול לראות שיש לנו struct זה מוגדר עבורנו, struct המדויק שרק דברו עליו בשקופיות. יש לנו משתנים הגלובלי שלנו לערימה, יש לנו פונקצית הדחיפה שלנו, ואז יש לנו הפונקציה הפופ שלנו. אני אשים את הקוד ללדחוף למעלה בחזרה בשקופית כאן, אבל מה שהייתי רוצה שאתם צריכים לעשות זה, למיטב יכולתך, ללכת וליישם את פונקצית פופ. ברגע שהתקנת אותו, אתה יכול לקמפל את זה עם להפוך את הערימה, ולאחר מכן להפעיל את הפעלת ערימת התוצאה, וכי אפעל בכל קוד של בדיקה זו לכאן זה בראשי. והעיקרי דואג לביצוע הדחיפה ופופ שיחות בפועל ומוודא שהכול עובר בסדר. זה גם מאתחל את גודל המחסנית ממש כאן אז אתה לא צריך לדאוג לאתחול ש. אתה יכול להניח שזה אותחל כראוי בזמן שאתה ניגש לזה בתפקוד פופ. האם זה הגיוני? אז הנה זה בא. יש קוד הדחיפה. אני אתן לך חבר 'ה 5 או 10 דקות. ואם יש לך שאלות בביניים בזמן שאתה הקידוד, אנא שאל אותם בקול. אז אם אתם מגיעים לנקודת דבק, פשוט לשאול. תודיע לי, בואו כולם יודעים. עבודה עם השכן שלך מדי. [דניאל] אנחנו רק מיישמים פופ עכשיו? >> רק פופ. למרות שאתה יכול להעתיק את היישום של דחיפה אם תרצה כך שהבדיקה תעבוד. כי קשה לבדוק דברים נכנסים - או, זה קשה לבדוק דברים מציץ מתוך ערימה אם אין שום דבר בערימה כדי להתחיל עם. 

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

הדבר השני לעשות כאשר אתה - בפופ, הוא יש לך להפחתה בגודל. אם אתה זוכר בחזרה לתרשים הקטן שלנו כאן, באמת, הדבר היחיד שראינו קורים כאשר אנו נקראים פופ היה שגודל זה ירד, 1 עד 2, ולאחר מכן ל1. ואז כשדחפנו את אלמנט חדש, זה הייתי הולך על בנקודה הנכונה. [זיל] אם s.size הוא 2, אז האם זה לא ללכת לאלמנט 2, ואז היית רוצה להתפוצץ אלמנט זה? אז אם הלכנו ל-- >> אז בואו נסתכל על זה שוב. אם זו המחסנית שלנו בשלב זה ואנחנו קוראים לפופ, שבמדד הוא עליון ביותר האלמנט? [זיל] בשעת 2, אבל זה פשוט יקפוץ 3. >> ימני. אז זה שבו הגודל שלנו הוא 3, אבל אנחנו רוצים לקפוץ אלמנט בעמוד 2. זה סוג כזה אופייני להנחה על ידי אחד שיש לך עם אפס אינדוקס של מערכים. אז אתה רוצה לפוצץ את המרכיב השלישי, אך האלמנט השלישי הוא לא בשעת 3 מדד. והסיבה שאנחנו לא צריכים לעשות את זה 1 מינוס כאשר אנחנו דוחפים הוא כי כרגע, אתה שם לב שהחלק העליון ביותר האלמנט, אם היינו משהו אחר כדי לדחוף על המחסנית בנקודה זו, היינו רוצה לדחוף אותו בשעת 3 מדד. וזה פשוט כל כך קורה שאת הגודל ואת המדדים בשורה כשאתה דוחף. 

שיש לו יישום ערימה עובד? יש לך ערימת עבודה אחד. האם יש לך הפופ פועל? [דניאל] כן. אני חושב שכן. תכנית >> רצה ולא צינוק שגיאה, זה מדפיס את? האם זה להדפיס את "הצלחה", כאשר אתה מפעיל את זה? כן. הפוך לערום, להפעיל אותו, אם זה מדפיס את "הצלחה" ולא ילך בום, אז כל מה שטוב. בסדר. בואו נלך על למכשיר ממש מהר, ונדריך את זה. אם אנחנו מסתכלים על מה שקורה כאן עם פופ, דניאל, מה היה הדבר הראשון שעשה? [דניאל] אם s.size הוא גדול מ 0. [Hardison] אוקיי. ולמה עשה את זה? [דניאל] כדי לוודא שיש משהו בתוך הערימה. [Hardison] ימני. אתה רוצה לבדוק כדי לוודא שs.size גדול מ 0; אחרת, מה אתה רוצה שקורה? [דניאל] null שבות? >> Null שבות, בדיוק. אז אם s.size הוא גדול מ 0. אז מה אנחנו הולכים לעשות? מה עושה אם המחסנית אינה ריקה? [סטלה] אתה הפחת הגודל? >> אתה הפחת הגודל, בסדר. אז איך אתה עשית את זה? >> S.size--. [Hardison] גדול. ואז מה עשה? [סטלה] ואז אמר התמורה s.string [s.size]. [Hardison] גדול. אחרת תחזיר null. כן, סם? [סם] למה זה לא צריך להיות s.size + 1? [Hardison] 1 פלוס? >> כן. >> תפס את זה. [סם] חשב שבגלל שאתה לוקח את 1, ואז אתה הולך להיות חוזר לא אחת שהם בקשו. [Hardison] וזה היה בדיוק מה שאנחנו מדברים על עם כל העניין הזה של 0 מדדים. אז אם אנחנו להתקרב חזרה לכאן. אם אנחנו מסתכלים על הבחור הזה ממש כאן, אתה יכול לראות שכאשר אנו קופצים, אנחנו קופצים אלמנט בעמוד 2. 

אז להקטין את הגודל שלנו ראשון, ואז הגודל שלנו תואם האינדקס שלנו. אם לא הפחת הגודל ראשון, ואז אנחנו צריכים לעשות גודל -1 ולאחר מכן הפחתה ב. גדול. הכל טוב? כל שאלות על זה? ישנן מספר דרכים שונות לכתוב את זה גם כן. למעשה, אנחנו יכולים לעשות משהו אפילו - אנחנו יכולים לעשות-אונייה אחת. אנחנו יכולים לעשות את חזרתו שורה האחת. אז אנחנו בעצם ניתן להפחית לפני שאנחנו חוזרים על ידי עושים את זה. כדי לשים - לפני s.size. זה הופך את הקו ממש צפוף. איפה ההבדל בין -. של הגודל וs.size-- הוא שסיומת זו - הם קוראים לזה postfix משום - מגיע לאחר s.size-- משמעות דבר הוא כי s.size מוערך לצורך מציאת המדד כפי שהוא כיום, כאשר קו זה מופעל, ואז זה - קורה אחרי הקו מקבל להורג. לאחר האלמנט בs.size המדד הוא לגשת. וזה לא מה שאנחנו רוצים, כי אנחנו רוצים ההפחתה בתקרה קודם. Othewise, אנחנו הולכים להיות בגישה למערך, ביעילות, מחוץ לתחום. אנחנו הולכים להיות בגישה לאלמנט מעל אחד שבעצם אנו רוצים לגשת. כן, סם? >> האם זה מהר יותר או להשתמש בפחות זכרון RAM לעשות בקו אחד או לא? [Hardison] בכנות, זה באמת תלוי. [סאם, לא מובן] >> כן, זה תלוי. אתה יכול לעשות טריקי מהדר כדי לקבל את המהדר להכיר בכך, בדרך כלל, אני מתאר לעצמי. 

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

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

אבל לעת עתה, בואו נעבור הלאה, ובואו נדבר על תורים. גלול כאן. התור הוא אח קרוב של הערימה. אז במחסנית, דברים שלא היו מכניסים אחרון היו הדברים הראשונים שלאחר מכן את המקור. יש לנו את זה בפעם האחרונה, לראשונה, או LIFO, הזמנה. בעוד שבתור, כפי שהיית מצפה מכאשר אתה עומד בתור, האדם הראשון שיעמוד בתור, הדבר הראשון להיכנס לתור, זה הדבר הראשון שמקבל אחזור מהתור. תורים גם משמשים לעתים קרובות כאשר יש לנו עסק עם גרפים, כמו שדברנו בקצרה עם ערימות, והתורים הם גם שימושיים עבור חבורה של דברים אחרים. דבר אחד שעולה לעתים קרובות מנסה לשמור, למשל, רשימה ממוינת של אלמנטים. ואתה יכול לעשות את זה עם מערך. אתה יכול לשמור על רשימה ממוינת של דברים במערך, אבל איפה שנהיה מסובך אז תמיד יש לך למצוא המקום המתאים להכניס את הדבר הבא. אז אם יש לך מערך של מספרים, 1 עד 10, ואז אתה רוצה להרחיב את זה לכל המספרים 1 עד 100, ואתה מקבל את המספרים האלה בסדר אקראיים, ומנסה לשמור על הכל מסודר כמו שאתה עובר, אתה בסופו של דבר נאלץ לעשות הרבה משתנה. עם סוגים מסוימים של תורים וסוגים מסוימים של מבני נתונים בסיסיים, אתה באמת יכול לשמור את זה פשוט בצורה הוגנת. אתה לא צריך להוסיף משהו ואז לטרוף את כל העניין בכל פעם. את גם לא צריך לעשות הרבה הסטה של ​​הגורמים הפנימיים בסביבה. כאשר אנו מסתכלים על תור, אתה רואה את זה - גם בqueue.c בקוד החלק - struct שהענקנו לך הוא באמת דומה לstruct שנתנו לך לערימה. 

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

אז תניח שיש לנו התור שלנו, אנחנו הולכים לקרוא לזה תור. בהתחלה, כאשר יש לנו רק מופעיו, כאשר יש לנו רק הכרזתי עליו, יש לנו לא אותחל דבר. זה כל הזבל. אז כמובן שאנחנו רוצים לוודא שאנחנו לאתחל הגודל וגם שדות הראש להיות 0, משהו סביר. כמו כן, אנו יכולים להמשיך וnull את האלמנטים בתורנו. וכדי לעשות את התאמת תרשים זה, שים לב שעכשיו התור שלנו יכול להכיל שלושה מרכיבים בלבד; בעוד שהמחסנית שלנו יכולה להחזיק ארבע, התור שלנו יכול להחזיק רק שלוש. וזה רק כדי להפוך את התאמת השרטוט. הדבר הראשון שקורה כאן הוא שאנחנו Enqueue המחרוזת "היי". ובדיוק כמו שעשינו עם המחסנית, שום דבר שונה מאוד כאן, אנחנו זורקים את המחרוזת במייתרים [0] ולהגדיל הגודל שלנו על ידי 1. אנו Enqueue "שלום", היא מקבלת לשים על. אז זה נראה כמו ערימה על פי רוב. אנחנו התחלנו כאן, אלמנט חדש, רכיב חדש, הגודל ממשיך לעלות. מה קורה בשלב זה כאשר אנו רוצים dequeue משהו? כאשר אנו רוצים dequeue, המהווה את היסוד שאנחנו רוצים dequeue? [זיל] מייתרים [0]. >> זירו. , זיל בדיוק נכון. אנחנו רוצים להיפטר מהמחרוזת הראשונה, אחד זה, "היי". אז מה היה הדבר השני שהשתנה? שים לב כאשר צצו משהו מהערימה, אנחנו פשוט שינינו את הגודל, אבל הנה, יש לנו כמה דברים ששינוי. עושה שינוי הגודל, אבל שינויים לא רק בראש. זה חוזר לנקודה הקודמת של שרלוט: למה אנחנו צריכים את הראש הזה גם כן? האם זה הגיוני עכשיו, שארלוט? סוג של >>. [Hardison] סוג של? אז מה קרה כשdequeued? מה עשה הראש שכרגע הוא מעניין? [שארלוט] אה, כי זה השתנה - בסדר. אני מבין. בגלל הראש - שבו הראש מצביע על שינויים במונחים של המיקום. זה כבר לא תמיד זה המדד אפס. >> כן, בדיוק. מה שקרה הוא אם dequeueing האלמנט הגבוה נעשה ולא היה לנו שדה בראש זה כי אנחנו תמיד היו קוראים את המחרוזת ב 0 ראשי ראש התור שלנו, אז יהיה לנו להעביר את השארית של התור. היינו צריך להעביר "ביי" ממייתרים [1] לחוטים [0]. ומייתרים [2] עד למייתרים [1]. והיינו חייב לעשות את זה לכל הרשימה של רכיבים, המערך השלם של אלמנטים. וכאשר אנחנו עושים את זה עם מערך, שמקבל באמת יקר. אז הנה, זה לא עניין גדול. פשוט יש לנו שלושה אלמנטים במערך שלנו. אבל אם היו לנו תור של אלף אלמנטים או מיליון אלמנטים, ואז פתאום, אנחנו מתחילים לעשות חבורה של dequeue מתקשר בלולאה, דברים באמת הולכים להאט כפי שהוא מסיט את הכל כל זמן. אתה יודע, להסיט 1, משמרת עד ליום 1, משמרת עד ליום 1, משמרת על ידי 1. במקום זאת, אנו משתמשים בראש הזה, אנחנו קוראים לזה "מצביע" למרות שזה לא ממש מצביע במובן הצר, זה לא סוג מצביע. זה לא * int או * או משהו כזה char. אבל זה מצביע או מצביע בראש התור שלנו. כן? 

[סטודנטים] איך dequeue יודע רק כדי להתפוצץ מה שעומד בראש? [Hardison] איך dequeue אינו יודע איך, שיתנדפו כל מה שעומד בראש? עכבר >>, כן. >> מה שהוא מחפש בכל מה שהוא רק ראש התחום מוגדר. אז במקרה הראשון, אם נסתכל ממש כאן, הראש שלנו הוא 0, 0 מדד. >> ימני. [Hardison] אז זה רק אומר שבסדר, טוב, המרכיב במדד 0, המחרוזת "היי", הוא האלמנט בראש התור שלנו. אז אנחנו הולכים לdequeue בחור ש. ושיהיה האלמנט שמקבל חזר למתקשר. כן, סעד? >> אז הראש בעצם קובע - לאן אתה הולך למדד זה? זה תחילתו של עניין? >> כן. >> אוקיי. [Hardison] זה הופך להיות ההתחלה החדשה עבור המערך שלנו. לכן, כאשר אתם dequeue משהו, כל מה שאתה צריך לעשות הוא לגשת לרכיב במדד q.head, ושיהיה האלמנט שברצונך dequeue. יש לך גם להפחתה בגודל. נצטרך לראות בקטע שבו לדברים לקבל קצת מסובכים עם זה. אנו dequeue, ועכשיו, אם אנחנו Enqueue שוב, איפה אנחנו Enqueue? היכן האלמנט הבא ילך בתורנו? אומר שאנחנו רוצים Enqueue המחרוזת "CS". שלמדד זה הולך? [סטודנטים] מייתרים [2]. >> שתיים. למה 2 ולא 0? [זיל] כי עכשיו הראש הוא 1, אז זה כמו ההתחלה של הרשימה? [Hardison] ימני. ומה מסמן את סוף הרשימה? מה אנחנו משתמשים כדי לציין את סוף התור שלנו? הראש הוא ראש תורנו, תחילתו של התור שלנו. מהו הסוף של התור שלנו? [סטודנטים] גודל. >> גודל, בדיוק. אז האלמנטים החדשים שלנו להיכנס בגודל, ואת האלמנטים שאנו לוקחים את יורדים בראש. כאשר אנו Enqueue האלמנט הבא, אנחנו נכניס את זה בגודל. [סטודנטים] לפני שאתה מכניס את זה באף, גודל היה 1, נכון? [Hardison] ימני. אז לא ממש בגודל. + גודל, לא +1, אבל ראש +. בגלל שאנחנו שינינו את סדר דברים בסכום הראש. אז הנה, עכשיו יש לנו תור בגודל 1 שמתחיל ב 1 מדד. הזנב הוא אינדקס 2. כן? 

[סטודנטים] מה קורה כאשר אתה dequeue מייתרים [0], וחריצים של המחרוזות בזיכרון פשוט ללכת לרוקן, בעצם, או סתם שכח? [Hardison] כן. במובן זה, אנחנו פשוט שוכחים אותם. אם הייתי אחסון עותקים שלהם ל-- רבים מבני נתונים לעתים קרובות לאחסן העותקים של האלמנטים שלהם כך שהאדם המנהל את מבנה הנתונים אינו צריך לדאוג לגבי איפה כל המצביעים האלה הולכים. מבנה הנתונים מחזיק על לכל דבר, מחזיק בכל העותקים, כדי לוודא שהכל נמשך כראוי. עם זאת, במקרה זה, מבני נתונים אלה פשוט, לפשטות, לא עושים עותקים של כל דבר שאנחנו מאחסנים בם. [סטודנטים] אז זה מערך רציף של -? >> כן. אם נסתכל אחורה על מה הייתה ההגדרה של מבנה זה, זה הוא. זה פשוט מערך רגיל כמו שראית, מערך של char * s. האם זה -? >> כן, אני רק תוהה אם סופו של דבר נגמר של זיכרון, במידה מסוימת, אם יש לך את כל המקומות הריקים האלה במערך שלך? [Hardison] כן, זה נקודה טובה. 

אם נסתכל על מה שקורה עכשיו, בשלב זה, אנחנו כבר התמלאנו התור שלנו, זה נראה. אבל אנחנו לא באמת מתמלאים תורנו כי יש לנו תור זה גודל 2, אבל זה מתחיל ב 1 מדד, כי שם המצביע בראש שלנו. כמו שאמרתם, אותו האלמנט במייתרים [0], במדד 0, הוא לא באמת שם. זה לא בתורנו יותר. אנחנו פשוט לא טרחנו להיכנס ולהחליף אותו כאשר אנו dequeued. אז למרות שזה נראה כאילו שנגמרנו לנו מהזיכרון, באמת יש לנו לא. זה מקום זמין לשימושנו. ההתנהגות ההולמת, אם היינו לנסות ו1 dequeue משהו כמו "שלום", שהיה קופץ משלום. עכשיו התור שלנו מתחיל בעמוד 2 והוא בגודל 1. ועכשיו, אם אנסה וEnqueue משהו שוב, להגיד 50, 50 צריכים ללכת במקום זה במדד 0 משום שהוא עדיין לא זמין עבורנו. כן, סעד? [סעד] האם זה יקרה באופן אוטומטי? [Hardison] זה לא קורה באופן אוטומטי לגמרי. אתה צריך לעשות את המתמטיקה כדי לגרום לזה לעבוד, אבל בעצם מה שעשינו הוא פשוט אנחנו כבר נכרכים סביבו. [סעד] וזה בסדר אם זה יש לו חור באמצעה? [Hardison] זה אם אנחנו יכולים לעשות את המתמטיקה תסתדר כמו שצריך. 

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

מה יקרה בשלב זה אם היינו dequeue משהו שוב? כל מחשבות? מה היה קורה לראש? מה צריך לקרות בראש אם היינו dequeue משהו אחר? הראש כרגע נמצא בעמוד 2, מה שאומר שראש התור הוא מחרוזות [2]. [סטודנטים] אשר מחזיר 0? >> זה צריך לחזור ל0. זה צריך לעטוף לאחור, נראה בדיוק. עד כה, בכל פעם שקראנו dequeue, אנחנו כבר הוספנו אחד לראש, הוסף אחד לראש, להוסיף אחת לראש, להוסיף אחת לראש. ברגע שראש המצביע מקבל למדד האחרון במערך שלנו, אז אנחנו צריכים לעטוף אותו סביב לנקודת ההתחלה, לחזור ל0. [שארלוט] מה מקובע את יכולתו של התור בערימה? [Hardison] במקרה זה, יש לנו פשוט משתמש בהגדרה קבועה #. >> אוקיי. [Hardison] בעצמו. קובץ c, אתה יכול ללכת בבץ ועם זה קצת ולעשות את זה כמו גדול או קטן כמו שאתה רוצה. [שארלוט] אז כשאתה עושה את זה בתור, איך אתה יודע להפוך את המחשב כמה גדול אתה רוצה להיות הערימה? [Hardison] זאת שאלה גדולה. יש כמה דרכים. אחת היא פשוט להגדיר אותו מול ואומר שזה הולך להיות תור כי יש 4 אלמנטים או 50 אלמנטים או 10,000. הדרך האחרת היא לעשות את מה שחבר 'מהדורת ההאקרים עושים וליצור פונקציות שיש התור שלך לגדול באופן דינמי כדברים יותר לקבל התווספו פנימה 

[שארלוט] אז ללכת עם האפשרות הראשונה, מה תחביר אתה משתמש לספר את התכנית מה הוא בגודל של התור? [Hardison] אה. אז בואו נצא מזה. אני עדיין בstack.c כאן, אז אני פשוט הולך כדי לגלול עד למעלה כאן. אתה יכול לראות זאת כאן? זה # מגדיר קיבולת 10. וזה כמעט אותו התחביר המדויק שיש לנו לתור. למעט בתור, יש לנו שדה struct נוסף בפה. [שארלוט] אה, חשבתי שהתכוונה ליכולת הקיבולת למחרוזת. [Hardison] אה. >> זה זה האורך המקסימאלי של המילה. >> תפס את זה. כן. הקיבולת כאן - זו נקודה מצוינת. וזה משהו שהוא מסובך כי מה שהכרזנו כאן הוא מערך של char * s. מערך של מצביעים. זהו מערך של תווים. זה כנראה מה שראית כשאתה כבר הכרזת המאגרים שלך לקובץ I / O, כשאתה כבר יצירת מחרוזות באופן ידני בערימה. עם זאת, מה יש לנו כאן הוא מערך של char * s. אז זה מערך של מצביעים. למעשה, אם אנחנו זום החוצה ואנחנו מסתכלים על מה שקורים כאן במצגת, אתה רואה שיסודות בפועל, נתוני האופי לא מאוחסן בתוך המערך עצמו. מה מאוחסן בתוך המערך שלנו כאן הם מצביע אל נתוני תווים. אוקיי. אז אנו רואים כיצד בגודל של התור בדיוק כמו עם המחסנית, הגודל תמיד מכבד את מספר הרכיבים כרגע בתור. לאחר ביצוע 2 enqueues, הגודל הוא 2. לאחר ביצוע dequeue הגודל הוא עכשיו 1. לאחר ביצוע Enqueue אחר הגודל הוא חזרה עד 2. אז הגודל בהחלט מכבד את מספר האלמנטים בתור, ואז הראש פשוט ממשיך רכיבה על אופניים. הוא נוסע מ0-1-2, 0-1-2, 0-1-2. ובכל פעם שאנחנו קוראים dequeue, המצביע מקבל ראש המוגדל למדד הבא. ואם הראש עומד ללכת מעל, זה לולאות סביב חזרה ל 0. אז עם זה, אנחנו יכולים לכתוב את פונקצית dequeue. ואנחנו הולכים לעזוב את פונקצית Enqueue בשבילכם ליישם במקום. 

כאשר אנו dequeue אלמנט מתורנו, מה היה הדבר הראשון שדניאל עשה כשהתחלנו לכתוב את פונקצית פופ לערימות? תן לי לשמוע ממישהו שלא דבר עדיין. בואו נראים, סעד, אתה זוכר מה דניאל עשה כדבר הראשון כשהוא כתב פופ? [סעד] היה, זה היה - >> הוא נבדק על משהו. [סעד] אם הגודל הוא גדול מ 0. >> בדיוק. ומה היו בדיקות של? [סעד] זה הייתי בודק לראות אם יש משהו בתוך המערך. [Hardison] כן. בדיוק. אז אתה לא יכול לקפוץ משהו מתוך הערימה אם זה ריק. כמו כן, לא ניתן dequeue דבר מתור אם הוא ריק. מהו הדבר הראשון שאנחנו צריכים לעשות בפונקצית dequeue שלנו כאן, אתה חושב? [סעד] אם הגודל הוא גדול מ 0? >> כן. במקרה זה, שלמעשה רק נבדק כדי לראות אם זה 0. אם זה 0, אנחנו יכולים לחזור ריקים. אותו דבר אבל היגיון מקובל. ובואו נמשיך עם זה. אם הגודל הוא לא 0, שבו הוא האלמנט שאנחנו רוצים dequeue? [סעד] בראש? >> בדיוק. אנחנו רק יכולים לשלוף את הרכיב הראשון בתורנו על ידי גישה לאלמנט בראש. לא בצורה מטורפת. אחרי זה, מה אנחנו צריכים לעשות? מה שצריך לקרות? מה היה הדבר השני שדברנו עליו בdequeue? שני דברים צריכים לקרות, כי התור שלנו השתנה. [דניאל] הקטנת הגודל. >> יש לנו להקטין את הגודל, ולהגדיל את הראש? בדיוק. כדי להגדיל את הראש, אנחנו לא יכולים פשוט עיוורים להגדיל הראש, זוכרים. אנחנו לא יכולים פשוט לעשות queue.head + +. יש לנו גם לכלול mod זה על ידי היכולת. ולמה אנחנו mod על ידי היכולת, סטלה? [סטלה] בגלל זה יש כדי לעטוף. >> בדיוק. אנו mod על ידי היכולת, כי יש לעטוף בחזרה סביב 0. אז עכשיו, בשלב זה, אנחנו יכולים לעשות את מה שאמר דניאל. אנחנו ניתן להפחית את הגודל. ואז אנחנו יכולים פשוט להחזיר את האלמנט שהיה בראש התור. זה נראה סוג של גועל נפש בהתחלה. ייתכן שיש לי שאלה. סליחה? 

[סם] מדוע זה 1 בראש התור? איפה זה הולך? [Hardison] זה מגיע מהשורה הרביעית מלמטה. לאחר שהבדיקה כדי לוודא שהתור שלנו הוא לא ריק, אנחנו נוציא את דמות * 1, אנחנו נוציא את האלמנט שיושב בראש המדד המערך שלנו, של מחרוזות המערך, >> והשיחה הראשונה שלנו ש? [Hardison] ואנחנו קוראים לזה ראשון. כן. רק למעקב על זה, למה אתה חושב שהיינו צריך לעשות את זה? [סם] כל 1 פשוט חוזר q.strings [q.head]? >> כן. >> בגלל שאנחנו עושים זה משתנה מq.head עם פונקצית mod, ואין דרך לעשות זאת בתוך קו התמורה גם. [Hardison] בדיוק. אתה כתם על. סם לגמרי מדייק ב. הסיבה שאנחנו צריכים לשלוף את הרכיב הראשון בתורנו ולאחסן אותו לתוך משתנה בגלל הקו הזה שבו אנחנו היו פשוט q.head, יש מפעיל mod שם הוא לא משהו שאנחנו יכולים לעשות ויש את זה ייכנס לתוקף בראש בלי - בשורה אחת. אז אנחנו באמת צריכים לשלוף את האלמנט הראשון, ולאחר מכן להתאים את הראש, להתאים את הגודל, ולאחר מכן להחזיר את האלמנט שהוצאנו. וזה משהו שנצטרך לראות לבוא מאוחר יותר עם רשימות מקושרות, כמו שאנחנו מתחילים לשחק בם. לעתים קרובות, כאשר אתה משחרר או סילוק של רשימות המקושרים אתה צריך לזכור את האלמנט הבא, המצביע הבא של רשימה מקושרת לפני הסילוק הנוכחי. כי אחרת אתה זורק את המידע של מה שנשאר ברשימה. עכשיו, אם אתה הולך למכשיר שלך, אתה פותח את queue.c-X-מזה. אז אם אני פותח את queue.c, תן לי זום בפה, תראה שיש לך קובץ דומה למראה. קובץ דומה למראה למה שהיה לנו קודם לכן עם stack.c. יש לנו struct לתור המוגדר בדיוק כפי שראינו בשקופיות. 

יש לנו תפקיד Enqueue שהוא בשבילך לעשות. ויש לנו את פונקצית dequeue כאן. פונקצית dequeue בקובץ שאינו מיושמת אבל אני אשים אותו בחזרה על PowerPoint, כך שתוכל להקליד אותו ב, אם תרצה. אז במשך 5 הדקות הבאות או כך, אתם עובדים על Enqueue שזה כמעט בדיוק ההפך מdequeue. אתה לא צריך להתאים את הראש כשאתה enqueueing, אבל מה יש לך להתאים? גודל. לכן, כאשר אתם Enqueue, הראש נשאר ללא שינוי, בגודל משתנה. אבל זה ייקח קצת - יהיה לך לשחק עם שmod כדי להבין בדיוק מה ראשי האלמנט החדש צריך להיות מוכנס ב. אז אני אתן לכם קצת, לשים dequeue לגבות על השקופית, וכפי שיש לכם שאלות, לצעוק אותם, כך שאנו יכולים כל הדיבורים עליהם כקבוצה. כמו כן, עם גודלך אל - העת להתאים את הגודל, אתה תמיד יכול פשוט - אתה צריך מוד הגודל אי פעם? [דניאל] מס >> אתה לא צריך מוד הגודל, נכון. בגלל הגודל יהיה תמיד, אם אתה - בהנחה שאתה מנהל את הדברים כראוי, הגודל תמיד יהיה בין 0 ל 3. איפה אתה צריך מוד כשאתה עושה Enqueue? [סטודנטים] רק לראש. >> רק לראש, בדיוק. ולמה אתה צריך מוד בכלל בEnqueue? כאשר הוא מצב שבו היית צריך מוד? [סטודנטים] אם יש לך חומר ברווחים, כמו במקומות 1 ו 2, ואז אתה צריך להוסיף משהו ב 0. [Hardison] כן, בדיוק. אז אם מצביע הראש שלך הוא ממש בסוף, או אם הגודל שלך בתוספת הראש שלך הוא גדול יותר, או לייתר דיוק, הולך לעטוף את התור. 

אז במצב הזה שיש לנו כאן בשקופית עכשיו, אם אני רוצה משהו Enqueue עכשיו, אנחנו רוצים משהו בEnqueue המדד 0. אז אם אתה מסתכל בו 50 הולך, ואני קורא Enqueue 50, זה הולך שם למטה בתחתית. זה הולך ב0 מדד. הוא מחליף את 'שלום' שכבר dequeued. [דניאל] אתה לא תטפל בזה בdequeue כבר? למה זה לעשות משהו עם הראש בEnqueue? [Hardison] אה, אז אתה לא שינוי בראש, מצטער. אבל אתה צריך להשתמש באופרטור mod כשאתה ניגש האלמנט שברצונך Enqueue כאשר אתה ניגש האלמנט הבא בתורך. [זיל] אני לא עשיתי את זה, ויש לי "הצלחה" שם. [דניאל] אה, אני מבין מה שאתה אומר. [Hardison] אז אתה לא ידע - אתה פשוט עשית בq.size? [זיל] כן. אני רק שיניתי את הצדדים, אני לא עשיתי שום דבר בראש. [Hardison] אתה לא באמת צריך לאפס את הראש כדי להיות כל דבר, אבל כשאתה אינדקס לתוך מערך המחרוזות, אתה באמת צריך ללכת קדימה ולחשב היכן הוא האלמנט הבא, בגלל withe המחסנית, האלמנט הבא במחסנית שלך תמיד היה במדד המקביל לגודל. אם אנחנו מסתכלים אחורה אל פונקצית דחיפת המחסנית שלנו, אנחנו תמיד יכולים plunk באלמנט החדש שלנו נכון בגודל אינדקס. ואילו עם התור, אנחנו לא יכולים לעשות את זה כי אם אנחנו במצב הזה, אם אנחנו enqueued 50 המחרוזת החדשה שלנו הייתי הולכת ממש במייתרים [1] שאנחנו לא רוצים לעשות. אנו רוצים לקבל את המחרוזת החדשה ללכת במדד 0. 

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

אז בואו מהר מאוד להסתכל על מה פונקצית Enqueue נראית. מה היה הדבר הראשון שאנשים ניסו לעשות בקו Enqueue? לתור הזה? בדומה למה שעשית עבור מחסנית דוחפת. מה עשה, סטלה? [סטלה, לא מובנת] [Hardison] בדיוק. אם (q.size == תכול) - אני צריך לשים את הפלטה שלי במקום הנכון - בתמורת שווא. זום בקצת. אוקיי. עכשיו, מה הדבר הבא שיש לנו לעשות? בדיוק כמו עם הערימה, והכניס במקום הנכון. וכך מה שהיה במקום הנכון כדי להכניס את זה? עם מחסנית זה היה גודל אינדקס, עם זה שזה לא בדיוק כך. [דניאל] יש לי q.head-או - q.strings >>? >> כן. q.strings [q.head + q.size mod קיבולת]? [Hardison] אנחנו כנראה רוצים לשים סוגריים סביב זה כך שאנו מקבלים קדימות המתאימות ואז זה cleart לכולם. ולהגדיר ששווה? >> כדי str? >> כדי str. גדול. ועכשיו מה זה הדבר האחרון שאנחנו צריכים לעשות? בדיוק כמו שעשינו במחסנית. >> תוספת הגודל? >> תוספת הגודל. בום. ולאחר מכן, שכן קוד המתנע רק חזר שווא כברירת מחדל, אנחנו רוצים לשנות את זה לאמיתי אם כל עובר והכל ילכו כשורה. בסדר. זה הרבה מידע לסעיף. אנחנו לא נסתיימו לגמרי. אנחנו רוצים לדבר ממש מהר על רשימות ביחידים צמודים. אני אשים את זה כדי שנוכל לחזור אליו מאוחר יותר. אבל בואו נחזור למצגת שלנו לרק עוד כמה שקופיות. אז Enqueue הוא TODO, עכשיו אנחנו כבר עשינו את זה. 

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

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

[סם] האם זה כמו שימוש בדבר pred ש-- אני רק זוכר, זה לא מה דבר pred הוא ל? זה לא בכפליים ובין ביחידים? מבט [Hardison] בואו במה בדיוק הוא עושה. אז הנה זה בא. הנה קוד הרשימה. כאן יש לנו predptr, כאן. האם זה מה שאתה מדבר עליו? אז זה היה - הוא משחרר את רשימה והוא מנסה לאחסן מצביע לזה. זה לא את כפליים, לחוד רשימות המקושרות. אנחנו יכולים לדבר על זה יותר מאוחר, משום שזה מדבר על שחרור הרשימה ואני רוצה להראות כמה דברים אחרים קודם. אבל זה פשוט - זה לזכור את הערך של ptr [סטודנטים] הו, זה מצביע קדם? >> כן. כך שלאחר מכן ניתן להגדיל ptr עוצמה לפני שבחינם אז מה predptr הוא. מכיוון שאנו לא יכולים ptr חופשי ואז להתקשר ptr = ptr הבא, נכון? זה יהיה רע. אז בואו נראה, חזרה לבחור הזה. 

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

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

אחת הדרכים הקלות ביותר לעבודה עם רשימות, ואנו מבקשים ממך לעשות את שניהם הקדם זיהוי ולצרף כדי לראות את ההבדלים בין שתיים, אבל prepending הוא בהחלט יותר קל. כשאתה הקדם זיהוי, זה המקום שבך - כשהקדם זיהוי (7), אתה הולך וליצור struct הצומת ולהגדיר תחילה להצביע על זה, כי עכשיו, מאז שprepended, זה הולך להיות בתחילת הרשימה. אם אנחנו הקדם זיהוי (3), שיוצר צומת אחר, אבל עכשיו 3 מגיעים לפני 7. אז בעצם אנחנו אתה דוחף דברים על הרשימה שלנו. עכשיו, אתה יכול לראות שצרף בתחילת השורה, לפעמים אנשים קוראים לזה לדחוף, בגלל שאתה דוחף רכיב חדש לרשימה שלך. זה גם קל למחוק בקדמת רשימה. אז אנשים לעתים קרובות קוראים פופ ש. ובאופן זה, אתה יכול לחקות מחסנית באמצעות רשימה מקושרת. אופס. מצטער, עכשיו אנחנו מגיעים להוספה. אז הנה אנחנו prepended (7), עכשיו אנחנו הקדם זיהוי (3). אם אנחנו prepended משהו אחר על רשימה זו, אם אנחנו prepended (4), אז יהיה לנו 4 ו 7 ואז 3 ואז. אז נוכל להכניס ולהוציא 4, 3 הסירו, הסר 7. לעתים קרובות הדרך אינטואיטיבית יותר לחשוב על זה עם הוספה. אז אני כבר נתחתי את מה שהיה נראה כמו צירוף עם כאן. הנה, צרף (7) לא רואה שום שינוי כי יש רק אלמנט אחד ברשימה. וצירוף (3) מעמיד אותו בסוף. אולי אתה יכול לראות את הטריק עם הוספה עכשיו הם שמכיוון שאנחנו רק יודעים איפה ההתחלה של הרשימה היא, לצרף לרשימה שיש לך ללכת לכל אורך הדרך את הרשימה כדי להגיע לסוף, לעצור, ואז לבנות הצומת שלך וכל מה שתך למטה. חוט כל מיני דברים. אז עם הקדם זיהוי, כפי שאנו פשוט קרענו את זה ממש מהר, כשאתה הקדם זיהוי לרשימה, זה די פשוט. 

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

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

הדבר האחרון שאני רוצה להראות לך, ואני אתן לך לעשות הוספה וכל זה בעצמך, הוא כיצד לחזר על רשימה. יש חבורה של דרכים שונות כדי לחזר על רשימה. במקרה זה, אנחנו הולכים למצוא את אורך רשימה. אז אנחנו מתחילים עם אורך = 0. זה דומה מאוד לכתיבת strlen למחרוזת. זה מה שאני רוצה להראות לך, זה ללולאה ממש כאן. זה נראה די מגניב, זה לא רגיל אני int = 0, i <מה, אני + +. במקום שזה אתחול n המשתנה שלנו להיות ההתחלה של הרשימה. ואז בזמן משתנה איטרטור שלנו הוא לא ריק, שנמשיך. הסיבה לכך היא, למוסכמות, לסוף הרשימה שלנו יהיה בטל. ואז כדי להגדיל, ולא עושה + +, המקבילה של הרשימה המקושרת + + היא n = n-> באה. 

אני אתן לך למלא את הפערים כאן בגלל שאנחנו מחוץ לזמן. אבל לשמור את זה בחשבון כאשר אתם עובדים על psets spellr. רשימות מקושרות, אם אתה יישום שולחן חשיש, בהחלט לבוא שימושי מאוד. ויש להם ביטוי זה ללופים על דברים יעשו את החיים הרבה יותר קל, בתקווה. בכל שאלה, במהירות? [סם] האם תשלח את SLL הושלם וsc? [Hardison] כן. אני שולח לכם שקופיות הושלמו וארובה השלימה SLL וqueue.cs. [CS50.TV]