רשימה משורשרת - הוספה ומחיקה
delete.פרקי ההרצאה: רשימה משורשרת - הוספה ומחיקה
תמלול ההרצאה: רשימה משורשרת - הוספה ומחיקה
הטקסט המלא של הדקות הראשונות בהרצאה «רשימה משורשרת - הוספה ומחיקה» בקורס הווידאו של PracticU – כתוביות בעברית עם זמן התחלה לכל פסקה. כך תוכלו לקרוא ולחפש את הנושאים לפני שמתחילים ללמוד.
טוב אנחנו ממשיכים עם הרשימה המשורטת נפתח את הוויזואל סטודיו ולינק קליפט יפה אז עשינו את add first שמוסיף ראשון בואו נוסיף את add last שמוסיף אחרון לא זה לא מה שרצינו אה את התמונה היה לך אוקיי התארנו את התמונה יפה אז זו התמונה המקורית אז מה אנחנו רוצים עכשיו לעשות אנחנו רוצים להוסיף את add last ומוסיפה בסוף אז נגיד void add last מקבלת
int i ומוסיפה לסוף איך מוסיפים לסוף? אז האמת היא שהיא מאוד דומה לחלק הזה בואו נעשה או שלא בעצם לפחות החלק הזה יש לו במשותף בואו בואו בואו בואו בואו בואו בואו בואו בואו ליצור נאות חדש צריך לכוון את זה צריך אחרי כשמחזנים צריך ללכת לסוף הרשימה.
בסופו של דבר אפשר תמיד לטייל לסוף הרשימה, אבל אפשר תמיד גם להחזיק פוינטר לסוף הרשימה. יש כל מיני אפשרויות, אבל בואו, שניהם די די מיצינו.
להחזיק פוינטר לסוף הרשימה זה לא אתגר גדול, ולעבור על הרשימה נגיע לפריט האחרון. בואו נעבור על הרשימה, נגיע לפריט האחרון. איך עוברים על הרשימה ומגיעים לפריט האחרון? זה מאוד דומה ללולה הזו, במקום להדפיס אנחנו נוסיף.
נגרור את זה לכאן, נגיד לו קופי חצי מינה ובייד פייס, וכן עד לאט עוברת עד הסוף, סטאס סטאס סטאס סטאס בסוף, בסוף קרן, אוקיי, מה אנחנו עושים?
כל עוד קרן, אני רוצה לעצור שנק כל עוד נק עוד יותר נשאר. אם נק שווה לנ"ל וגם לא צריך אפילו תנאי יציאה, בלי תנאי יציאה אני קורא במשל אם נק עם קורנט נק שווה לאפס אם הוא שווה לאפס אז קורנט הוא האחרון קורנט הוא הלאס קורנט הוא הלאס אני מצביע בעזרת קורנט ללאס ואז
ואז מה ואז אני יכול להוסיף לדחוף אותו פה בסוף בסוף הרשימה ואני אגיד אז אולי נעשה מפרוקציה get last לא צריך למחזר לא צריך לעשות לא צריך אותה פעם נוספת אז לא צריך אז get last עובר עד הסוף עד שcurrent נקסט שווה לאפס וcurrent נקסט שווה לאפס אז מה היא צריכה לעשות היא צריכה להגיד אוקיי נקסט שווה לנוד החדש אז קורנט נקסט שווה לנוד החדש שווה ל-n אז צריך
את זה להביא לכאן אפילו תו תו חצי מילה ונטר ואת ה-next של ה-node החדש נכוון לאפס והוא נהיה המקוצר הבא וה-next של החדש יהיה מקוצר, ה-next של החדש מקוצר יפה ומה?
current next שווה ל-n וזהו וב-root לא נוגעים אז אם אנחנו כל הזמן כל הזמן נקרא ל-adless מה נקרא אם בפעם הראשונה נקרא ל-adless? בואו נגיד שבפעם הראשונה רות שווה לנעל ואני קורא לעד לה אז אני עובר על הרשימה כאן שווה לרות ורות שווה לנעל אז כאן שווה לנעל ואז נעל נקס אני חוטף את זה. זאת אומרת אסור לקרוא לעד לה בפעם הראשונה במים בכות אני קורא לו
אז אם אני מזהה שאני קורא לו אז אני מתוכו אקרא לעד לה כי עד לה היא בעייתית אז אם אני מזהה שכאן שווה נעל או שרות שווה נעל אני פשוט קורא לעד אי רות שווה ל-num שווה ל-0 אז תקרא לעד תשתנו את i.
יאללה ניתן כסף אחרת נמצא את האחרון וככה וככה. כמובן זה לא כלכלי כל פעם לעבור על הרשימה ולהגיע לסוף הרבה יותר כלכלי לשמור פוינטר שמצביע לסוף.
הבעיה היא שלפעמים אנחנו יכולים לקבל עילות ממי שנותן לנו הוראות והוא יגיד לנו אי אפשר להגדיר משתנה גלובלי, אי אפשר להגדיר עוד משתנה גלובלי, יש רק את רות ואי אפשר להגדיר את לאס, נבחר צריך תמיד להגיע ללאס ידנית, אז אין ברירה אז אין ברירה, לפעמים יש כאלה אילוצים.
אוקיי, אז זה היה עד לאס, אז אפשר לקרוא לעד לאס גם בהתחלה, ואפשר לקרוא לעד לאס ולהגיד לו 65, ונשכח את זה, נדחוק את זה פה, אפשר לקרוא לעד לאט פה עם 93 אז בואו נראה את זה בוא נראה אם זה עובד אז יש לנו דיון פונקציונלס כאן אט פארס נמצאת אט פארס אני לא מבין את אט פארס למה לא כי אט פארס נמצאת כאן בואו ניקח אותה קופי עליה לא הצהרנו
ועכשיו בואו נצביע בטריטיז ואני אקבל הפסיק עכשיו בואו נפסיק, ושוב נמצא את הדרך, ובואו נראה מה קורה פה, אז אני קורא ל-add last, או ל-add last, כל מה שאמורה לעשות זה לבדוק ולקרוא ל-add first, ל-add first אנחנו יודעים שהיא עובדת, אז זה לא אמור להיות חידוש, ו-add first אין בעיה, ו-add last בואו נראה
פעם אם היא עושה משהו מועיל לאנושות, אז אם היא ברורת אבל ברורת לא, ואז אנחנו עוברים, ואם קוראים לפני סביבנו עליו בפעם הראשונה הוא לא, הוספנו כרגע שניים.
הוספנו כרגע את שישים וחמש, שהוא בעצם ראשון, זה לא שונה, ואת תשע. אז יש לנו את שישים וחמש ואת תשע, אז ככה זה נראה. שישים וחמש ותשע, זה המצב הנוכחי, ועד לאט אנחנו מוסיפים את תשעים ושלוש בסוף.
אוקיי, שישים וחמש ותשע כבר קיימים, אז זה היה שישים וחמש, עכשיו אנחנו, זה שישים וחמש, מכוונים את עצמנו, אה, תשע האחרון, אדס פרס, טעות שלי, אמטרול שיפטי מחליף בין שתי המילים.
אדס פרס, הוספנו לתשע ראשון, אז זה תשע, שישים וחמש. יפה. קרן, שישים וחמש, הגענו לתא השני והאחרון, הנקס שלו הוא אפס, ניתן, אז נקס שווה לאפס, ואני רואה שזה טרו, יפה מאוד, ואז אני אומר לו,
אקצר לי נו, תכוון את הזה, הנקס שלו אפס, הקרן הוא שישים וחמש, שישים וחמש, נפט שלו הוא אפס, הנפט הזה שווה לנורד החדש, לנורד החדש הנפט שלו הוא אפס. הנורד החדש הוא 93. ופה בעצם סיימנו, ולא אמרנו לו שסיימנו, הוא ימשיך לנצח, כי פה גדולת תמשיך לנצח, כי תמשיך לנצח זה אומר שהוא תכף יתפוצץ.
כי הנפט כרגע, הנפט כרגע עובד בסדר, לא יודע אם זה יתפוצץ, יכול להיות שזו לולאה נצחית, כי הנפט תמיד הוא אפס.
נכנסנו לאחרון, התקדמנו לאחרון, זה פתאום אומר לי תתקדם לאחרון ושוב אנחנו הולכים להוסיף נוד חדש אני לא אתן לזה לקרוא כמובן זו הנקודה שאנחנו איפה אנחנו מוסיפים מהי נקודת ההוספה מוסיפים אחרון ניגש לקלרנד שהוא חלק מהרשימה ואני אומר להתחבר לנוד חדש אני לא אתן לזה לקרוא כמובן כי אני לא רוצה להוסיף עוד פעם ל93 אני חייב תנאי יציאה או
שאחרי שביטלנו את זה, נעשה break, הכי פשוט, נעשה פה break. אז הנה break, ואני חוזר לכאן, הוא אומר לי that it's not match, נו, אולי בכל זאת, בכל זאת אולי לא.
בקיצור, נוציא אותו בכוח, הזרוע, וזה זה זה זה זה זה. טוב, הרי אין זה מחוץ לפונקציה מבחינתו, אני מבין, לצורך התוכן זה ברירה, זה אין ברירה, בואו נשים פה break וניתן לזה לרוץ.
כמו אמרנו, הגיעה הנקודה הזו, ועכשיו הווט יש לנו תשע ואז שישים וחמש ואז תשעים ושלוש תשע שישים וחמש ושישים ושלוש תשע שישים וחמש ואז אנחנו מוסיפים לתשע שישים ושלוש תשע שישים וחמש שישים ושלוש ואז עד פרס שש מוסיפים את שש פה נמצא בפונקציה וצריך להוסיף את שש
אז ניכנס לשש, טוב זה כבר פשוט, זה כבר ראינו, זה לא חידוש ועד פרס תקצור פורקה, בואו נראה את ההדפסה, שלוש, שש, תשע, שבעי, חמישי, שלוש אז היה לנו תשע, שבעי, חמישי, שלוש ועצרנו את שש ושלוש אז שלוש, שש, שלוש, שש, בואו ניקח את זה איתנו שיהיה לנו את זה
ופרינט תשע, יפה מאוד, יפה, זה היה עד לפה, ולאט סיימנו מה עם add shorted, מה עם find. בעצם add shorted אמור לדלג בדילוגים להגיע למקום הנכון ואז להוסיף. לעומת find, find אמור לדלג ולהגיע למקום הנכון.
אז למה שלא נקרא ל-find, נקרא ל-find שהחזיר לנו את ה-node שאחריו אנחנו אמורים להכניס את המקום הנכון. תכף תראו איזה בעיה יפה תהיה לנו ואז נזדקק לפוינטר לפוינטר כדי לפתור אותה.
וואה למה? בגלל השורש הרות לא נוכל להצביע נצטרך להחזיר מצביע למצביע ותמיד להחזיר מצביע למצביע זה יהיה כיף.
יפה אז בקיצור הפתרון הוא בשביל ארץ סואטד נצטרך את פיינד בוא נעשה קודם כל פיינד שוטה פיינד לא מחזירה ווייד נעשה פיינד שמחזירה לואוד תחזיר לנו נאות מוכבית. בואו נעשה פיין שמחזירה נוד פוכבי יפה אז נגדיב אותה פה אז נגיד נוד וויט פיין מה אם פיין מה הייתה פיין מקבלת אם פיין יפה ומה היא עושה היא עושה משהו מאוד דומה ללולה הזו היא עוברת עוברת עוברת עוברת היא צריכה
כבר לעבור באמת עד הסוף היא צריכה להיות זהה בואו נשתמש היא בכלל זהה להתפסה, היא צריכה באמת לעבור על הכל, בואו ניקח את הגוף של הכל של ההתפסה יפה אז אנחנו מתחילים בהתחלה ועוברים ועוברים ועוברים עד הסוף ובכל יתרה עד שאנחנו בודקים אם קוונט חט דלתא שווה ל-i אז אנחנו מה נעשה?
מה נעשה אם דלתא שווה ל-i? זה מצא לו את הנורד הנכון, אז נחזיר, נחזיר את הנורד הנכון. מי הנורד הנכון? נחזיר, את קאנט. קאנט הוא הנורד הנכון, כי הדאטה שלו הוא הנכון, אז זה קוראים לזה פיינד.
אוקיי, פיינד חביבה, בואו נעשה את זה בפיינד, ופיינד, נתון הרווח חובד, אה יפה, פיינד 93, ובואו נחזיר לנו נורד