c# linkedList

[eido300]

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

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

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

[QttP]

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

כדי לבנות רשימה, אפשר להשתמש בשתי דרכים:

* לשנות את הפונקציה ADD כך שכל פעם תסרוק את הרשימה מהתחלתה (FIRSTNODE) עד שתגיע לNULL ותוסיף שם. זה כמובן מאוד לא יעיל כי צריך לעבור על כל האיברים, ואז הוספת איבר לוקחת O(N במקום O(1.

* להחזיק פנימית בתוך LINK גם את האיבר האחרון ברשימה, ולשנות את ADD כך שבמקום לקבל את המקום להוספה תקבל רק את האיבר שיש להוסיף ותוסיף אותו אחרי האיבר האחרון.

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

[eido300]

תודה על התשובה.

כתבתי את זה ככה:

public void add(T Node)
        {
                node<T> newnode = new node<T>(Node);
                newnode.next = this.lastnode.next;
                lastnode.next = newnode;

        }

עכשיו הגעתי לכמה בעיות חדשות...

איך מוחקים? הקוד נמצא כאן, מה אני אמור לכתוב שם (שורה 20)?

כשאני מדפיס זה מדפיס את הראשון ואז את הכל "מהסוף להתחלה", הבנתי שהבעיה היא בשמירה, שהוא לא מוסיף את התא החדש לסוף הרשימה אלא הופך אותו לשני, איך אני מוסיף אותו לסוף?

[QttP]

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

* תצייר את מה שהקוד הנוכחי עושה

* תצייר את מה שהיית רוצה לעשות

* תחשוב איך מתרגמים את הרצוי לקוד, שורה שורה.

[eido300]

לא הצלחתי למצוא פתרון, הבעיה שלי היא כזאת -

כשאני רוצה להוסיף תא באמצע אני פשוט מכניס בnext שלו מה שמופיע בnext של הlastnode >>> מכניס אותו בlastnode.

בשביל להכניס אותו אחרון אני צריך למצוא את התא האחרון האמיתי >>> לעדכן את הnext שלו לlastnode >>> להכניס את התא החדש בlastnode.

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

אשמח אם תיתן לי איזה שהוא כיוון למחשבה.

[QttP]

הlastnode הוא מצביע לתא האחרון. אין שום דבר יותר אמיתי מזה. אם מראש הרשימה נבנתה נכון, זאת אומרת.

תחשוב על זה כך - נאמר שיש לך רשימה תקינה שכבר בנויה, שבה כל התאים משורשרים, firstnode מצביע לראשון וlastnode מצביע לאחרון.

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

[eido300]

חשבתי על זה כך, הבנתי איפה הטעות שלי (הייתי בטוח שlastnode הוא עוד תא נפרד ולא מצביע, מתברר שטעיתי...) שיניתי ויצא אחלה, תודה רבה.

זה הקוד שכתבתי:

public void add(T Node)
        {
            node<T> newnode = new node<T>(Node);
            lastnode.next = newnode;
            lastnode = newnode;
        }

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

תודה רבה.

אגב אני יכול לקצר את זה ולכתוב כך:

public void add(T Node)
        {   
            lastnode =(lastnode.next =new node<T>(Node));  
        }

הקוד עובד, השאלה אם זה נכון מבחינת צורת כתיבה נכונה?

[QttP]

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

[eido300]

זאת אומרת שבשביל למחוק תא אני יכול למחוק אותו רק ע"פ התוכן שלו או ע"פ מיקומו (הכוונה למספר התא אם הוא ראשון, שני וכו')?

אז איך אני כותב את הדרך שמראים כאן?

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

[QttP]

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

[eido300]

איך קיבלת את המצביע? שאלה אחרת.

לשאלה הזאת יש תשובה?

[QttP]

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