רשימה משורשרת - הוספה והדפסה
new, מכוונת את data למספר ואת next לתחילת הרשימה הקיימת, ואז מכוונת את root לצומת החדש.פרקי ההרצאה: רשימה משורשרת - הוספה והדפסה
תמלול ההרצאה: רשימה משורשרת - הוספה והדפסה
הטקסט המלא של הדקות הראשונות בהרצאה «רשימה משורשרת - הוספה והדפסה» בקורס הווידאו של PracticU – כתוביות בעברית עם זמן התחלה לכל פסקה. כך תוכלו לקרוא ולחפש את הנושאים לפני שמתחילים ללמוד.
טוב היום אנחנו נבנה רשימה משורשרת בואו נפתח visual studio ו-create project יפה זה יהיה כמובן בואו נצמצם זה יהיה באדר לינגוויג'ס c++ 32 ונקרא לזה איך קוראים לזה רשימה לינקט לינקט ליסט ככה קוראים לזה באנגלית ואוקיי יפה באפליקיישן סטינג זה הכל בסדר נגיד לו finish יפה אז מה שאני רוצה זה בסך הכל רשימה משורשרת.
לרשימה משורשרת אני יכול להוסיף פריטים. אז בואו נתחיל ב-add. אז אני רוצה להוסיף פריט. זה תהיה רשימה משורשרת של אינטים. אז איך נראה פריט ברשימה המשורשרת?
פריט זה בעצם סטראקט שמה שיש בו זה int i, וטוב הסטראקט הזה צריך גם שיהיה שם זה יהיה סטראקט נוד בדרך כלל קוראים לזה נוד נוד פירושו צומת צומת ברשימה המשורשרת ואז יש לנו שדה מסוג נוד שנקרא נקסט הנוד הבא עכשיו ב-c וב-c++ וב-c-sharp כשאני מגדיר סטראקט נוד ואני כותב פה נוד נקסט אז נקס הוא לא מצביע
נקס הוא ממש שדה מה שגורם לדבר הזה לפוצץ את המחסנית בזמן קומפילציה זה דבר מטורף בואו תראו איזה f6 בואו נראה בואו נגיד נקס uses node which is being defined טוב כאן הוא היה ממש מפוצץ ממש המחסנית המתפוצצת אוקיי אז הוא מתפוצץ או לא מתפוצץ או באיזה צורך כזה מה אבל זה בדיוק מה שהוא אומר הוא אומר בואו נגיד את זה קצת הוא אומר נקסט של נוד משתמש בנוד שהוא בעצמו
מוגדר כרגע. מה עוד הוא אומר? הוא אומר פה נקודה פסיק חייבים פה לשים נקודה פסיק בוא נעשה שוב F6. יפה אז זו הבעיה היחידה. הוא לא ניסה לקמפל את זה הוא פשוט זיהה שיש פה ריקורסיה בהגדרה בזמן שאני מגדיר את נוד אני משתמש בנוד בטיפוס נוד באתמון זה בלתי אפשרי אבל אני כן יכול להגיד מצביע לנוד הבא F6 ונחכה לו בילד תקציב יפה מאוד אז יש
לנו צומת צומת יודע להצביע על הצומת הבא אולי רגע נצייר את התוכנית עבודה שלנו בואו נגבש איזושהי תוכנית עבודה נגדיל ולו במקצת יפה, אז מה שאני רוצה זה איזושהי רשימה משורשרת שיש בה אינטים.
אז בוא נגיד פה יהיה לנו 6, ואז אני רוצה להוסיף עוד אינט, אז אני מוסיף עוד תא ברשימה המשורשרת, נגיד שבתוכו יהיה המספר 9, ואני ארצה לחבר את הפריטים האלה.
אני רוצה איזשהו חיבור, אז כאן יהיה לי, בוא נגיד שצומת בנויה משני חלקים, משדה, כמו שאצלנו כרגע מופיע, משדה, עושים את זה ככה, אם תאי זה בעצם איי, ושדה נקס זה בעצם נקס.
אז נקס מצביע לתא הבא, מה שיהיה לנו זה איזשהו בסיס, יהיה לנו איזשהו בסיס, אני אגיד כמו שיש לי פה פוינטר כזה, אז יהיה לי שדה שהוא בעצמו יהיה בעצם פוינטר, אנחנו ננסה אותו טיפה יותר קטן, וזה בעצם יהיה כאילו ה-next הראשון, נקרא לזה רוט, אנחנו נקרא לו רוט.
זה יהיה השואה שלנו, בואו נשמור את התמונה הזו על שולחן העבודה, מסתוגי, ונקרא לה לינקדליסט, ועוד אין כאן. יפה.
עכשיו, הרוט הזה, אולי רגע, נמחק את זה, או שנעביר את זה בעצם, נעביר את זה לך, יפה. רות הזה יצביע לתא הראשון, אני אשתמש בכזה, מפה לכאן, קליק אחד פה וקליק אחד כאן, יפה.
אז רות יצביע לתא הראשון, והתא הראשון יצביע לתא השני, וכן הלאה. התא האחרון יצביע לשום דבר, קליק אחד פה וקליק אחד פה, וקליק פה וקליק פה, ואנחנו נסמן את זה שהוא לא מצביע לשום דבר, בעזרת הסמן הזה שאומר בחשמל שהוא מקוצר לאדמה, הוא לא מצביע לשום דבר,
בואו נגיד שהוא מצביע ככה, יפה, יפה. עכשיו כל פעם שאנחנו נרצה להוסיף תא, נוסיף אותו, מבחינתי אני צריך להחליט לאן מוסיפים, או שמוסיפים אותו להתחלה, או שמוסיפים אותו לסוף, או שמוסיפים אותו למקום הנכון.
אז אותה התחלה, אנחנו פשוט נוסיף אותה תמיד להתחלה. בהתחלה הרות יהיה נ"ל, בואו נגדיר אולי את ה-root, אז יהיה לנו מסוג note, טוב אני לא יכול פה, הוא עוד לא מכיר את note, למרות שהוא אומר לי שהוא כן מכיר, אבל הוא לא מכיר, אני אגיד לו פה root ונעשה f6 ותראו שהוא לא מכיר, הוא אומר שמיסינג נקודה
הפסיק לפני ה-identifier root. עושה נקודה הפסיק לפני ה-identifier root. אם יש נקודה הפסיק לפני ה-identifier root זה יעזור לדעתכם?
איך זה יכול לעזור? בקיצור זה לא יעזור, למה לא? כי node הוא לא מוכר. אז או שאני אשים את node לפני או שאני אשים הצהרה, הצהרה על node לפני. אני יכול להעביר את זה לפה על copy, חצי ימינה נקודה פסיק ו-enter. אבל זה בעצם הצהרה על Struct. אני יכול את Struct עצמו
לשים לפני, אבל הנה תלמדו גם כזה. ו-F6, אוקיי? Who'd use undefined Struct node? undefined struct node האמת שבכל מקרה רצינו שזה יהיה פוינטר אבל מה זאת אומרת undefined הוא לא אמור להיות defined הוא לא מקבל את זה root is undefined struct node root מסוג node למה הוא אומר שהוא undefined הרי יש לי הצהרה בהמשך אני מגדיר לא מובנת הבעיה
ואם אני אעביר את זה לאחרי נגיד 1 ונעשה את 6 זה בסדר לא מבין אבל בהזדמנות אחרת ננסה להבין בסדר אז יש לנו את רוט שהוא מסוג לואוד כוכבית רוט יודע להצביע לנוד רוט יודע להצביע לנוד הדבר הזה הוא לואוד כל הדבר הזה הוא לואוד זה לואוד או אם אין גבולה כל זה לואוד יפה מאוד השדה הזה הוא שדה נקסט זה נקרא נקסט יפה מאוד זה
נקסט יפה וזה כמובן איי זה האיי שלנו. רק כדאי שנקרא לזה דאטה, בדרך כלל קוראים לזה דאטה, אז נקרא לזה דאטה וזה יהיה דאטה. יפה מאוד מאוד. אוקיי, ערבות יודע להסביר לדאטה, אז בהתחלה אנחנו רוצים להוסיף נגיד את המספר הראשון שאנחנו מוסיפים, נעשה את ה-9, כי החלטנו שאנחנו כל פעם נדחוף את המספר החדש ראשון ברשימה.
אגב, למה זה טוב רשימה משורשרת? רשימה משורשרת היא חיונית כשאני לא יודע כמה תאים יהיו לי במבנה הנתונים שלי. אני רוצה להיות מסוגל להקצות באופן דינמי מבנים ולהשמיד אותם ולהקצות אותם בצורה חופשית.
אז אני חייב להחזיק רשימה משורשרת כי אני לא יודע כמה תאים יהיו לי. אני יכול להחזיק מערך שמצביע על התאים אבל זה מערך זה סוג של פתרון יש בו יתרונות וחסרות.
רשימה משורשרת זה משהו נורא גמיש. אפשר להחזיק מערך, אפשר להחזיק רשימה משורשרת של מערכים, אפשר פיתור כל מיני פתרונות, אבל בסופו של דבר רשימה משורשרת זה כלי עבודה מאוד נוח למבנה נתונים.
אוקיי, אז אנחנו רוצים להוסיף בהתחלה את 9, 9 יהיה הראשון. אז איך להוסיף את 9? אז צריך דבר ראשון להקצות את המבנה נתונים הזה.
אז איך מקצים? אנחנו יכולים לעשות New Node, אוקיי, אנחנו נחזיק אליו פוינטר זה יהיה מסוג Node כוכבית זה יהיה החדש החדש שאני אקרא לו n, n שווה ל-new Node שימו לב שלא כמו C שם אני לא חייב להפעיל קונסטרקטור אני יכול הוא אומר שיש לי שני קונסטרקטורים יש לו גם קופי קונסטרקטור דיפולט קופי קונסטרקטור נורא
נחמד אבל לא חייב אני חושב שאני לא חייב אני חושב שאני יכול לעשות את זה ככה בואו נעשה קונטרול שיפט בי ובילד סקסיד יפה מאוד ואני יכול לבוא עכשיו ל-n ולהגיד ל-n, n נקודה אין דבר כזה אבל יש n חטא.
אני יכול לבוא ולהגיד ל-n חטא דאטה שהערך שלו יהיה 9 ול-n חטא נקס אנחנו כבר רואים ש-n אחריו שום דבר אז הוא יהיה נל שווה לנל n נל ב-c שער ב-c פלוס פלוס אני יכול להגיד לו נל גדול f12 לראות שהוא בעצם 0 אפס או פשוט נגיד שהוא אפס שווה לאפס זה מקובל מאוד להגיד בסעיף נוסף.
ואז בעצם אני ואז הוא נראה בעצם ככה אוקיי ורות יצביע אל החדש אל n יפה רות שווה לn עכשיו את רות שמתי פה כמשתנה גלובלי אבל למעשה אין לזה הצדקה בשלב זה אין לי בעיה לשים את רות כמשתנה מקומי.
אז מה הרעיון ברות? הרעיון הוא שיש לי איזושהי נקודה התחלה שאני יודע בכל רגע נתון איפה הרשימה מתחילה. כל הזמן אני אוכל להוסיף לפה עוד ועוד ועוד צמתים ברשימה, וכשאני ארצה לעבור על הרשימה אני תמיד אתחיל ברות ואני אעבור על הרשימה.
יפה, אז כרגע הוספנו פריט, הוספנו את תשע, יפה, בואו נוסיף עכשיו עוד אחד, נוסיף אותו בהתחלה. אז איך אני אוסיף עכשיו עוד אחד, בעצם, אה, בעצם לא, בעצם יש לי מאוד טוב, זה קצת מבלבל מה שאני עושה, אולי כדי שפשוט נעשה פונקציה add ופונקציה print, ונקרא ל-ad איך שאנחנו רוצים, ונקרא ל-print מתי שאנחנו רוצים, אז בואו נעשה את זה, אז
נגדיר את void add, add תהיה אחראית להוספה, ונגדיר את void print, print אחראית על הדפסה, יפה, ובעצם הקוד הזה זה קוד שתכף נראה מה אנחנו נעשה איתו, אבל הוא כרגע יותר רלוונטי לאד, תכף נטפל בו כמו שצריך, בואו נעשה ה-Ctrl-Shift-B, יש הכל מתקמפל יפה. מה
שאני רוצה עכשיו לעשות זה לקרוא לאד ולהעביר מספר, אז צריך לקבל פה int i ולהעביר בהתחלה את 9 ואז לקרוא לאד עם 6, מספר שני הוא שש ואז אני רוצה לקרוא לפרינט ולראות שמה שהוא מצפיץ לי מה הוא אמור להצפיץ לי מפני שהצפיץ לי שש תשע זה מה שאני רוצה לראות יפה אז אם אני קורא לעד כל פעם שאני קורא לעד אז אני יכול בקיצור להגדיר לי פה
משתנה גלובלי שזה יהיה השורש שלי אז אני שם את זה כאן יפה delete, חצי למטה ו-enter. אוקיי, אז זה יהיה השורש שלנו, אני משמר אותו כמשתנה גלובלי, כדי שהוא יהיה זמין לי מכל הפונקציות, גם מאד וגם מפרינט.
יפה. אז, אני מקבל את i, אני מקצה node חדש, אני מכוון את הדאטה שלו להיות i, את ה-next שלו אני תמיד, לא, אני לא תמיד עושה את זה, אני תמיד מכוון אותו לאן שהוא עוד מצביע.
אני רוצה להידחף, הנוד החדש שאני דוחף אמור להידחף.