רשימה מקושרת ב-C++

[M a r i n a 8 4]

רשימה מקושרת ב-C++

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

 

[M a r i n a 8 4]

שכחתי לציין שהרשימה היא חד כיוונית

 

[spiritus asper]

אפשרות

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

 

[M a r i n a 8 4]

ובלי לעבור על הרשימה עוד הפעם אי-אפשר?

כאילו משהו בסיבוכיות (1)O?

 

[immortalus]

כעיקרון יש 2 טריקים שאפשר לעשות:

1) node של רשימה דו-כיוונית שהרשימה עצמה לא מאפשרת להשתמש ב-back - ואז זה באמת טריביאלי. 2) טריק מסריח ומסוכן: להעתיק את data של האיבר הבא לאיבר הנוכחי ולמחוק את האיבר הבא. יש עם זה בעיה, כי אם יש איפה שהו בתוכנית עוד מצביע שמצביע כרגע לאיבר הבא, הוא יצביע עכשיו לזיכרון משוחרר... החלטה שלך

 

[M a r i n a 8 4]

אני עשיתי בדיוק את המקרה השני!!

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

 

[immortalus]

יוצרים לתחילת וסוף הרשימה node-ים מיוחדים

שיסמנו את ההתחלה והסוף... למשל DATA שהוא NULL... את ה-Node-ים האלו כמובן שלא מוחקים בשום אופן...

 

[M a r i n a 8 4]

הא.. זה נראה לי כבר קצת יותר מדי..

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

 

[אופסשםמשתמש]

אני ממליץ לך להמשיך ב"התחכמות"

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

 

[דוד המקורי1]

אי אפשר פשוט להציב null לאיבר האחרון ברשימה?

ולפני כן לעשות לו free כמובן. זאת כדי שהאיבר שלפניו יהיה האיבר האחרון החדש. פיתרון נכון?

 

[Desslok of Gamilon]

לא מה זה "להציב לו null"? להציב למי? האיבר הקודם ברשימה עדיין מצביע לאיבר שלך, ואין לך גישה לאיבר הקודם. NULL זה ערך שאפשר להציב למצביע, אי אפשר להפוך אובייקט קיים ל NULL.

 

[דוד המקורי1]

סבבה מסכים איתך

אבל למה זה שמעליי רשם להגדיר node חדש שבו ה-DATA יהיה NULL? איך אפשר לעשות את זה? זה לא סותר את מה שאמרת? שאי אפשר להפוך אובייקט קיים ל-NULL?

 

[immortalus]

כי הכוונה היא שהוא מאותחל בצורה כזו

ולא משתנה מרגע האיתחול. חוץ מזה, לא האובייקט עצמו הוא NULL אלא הוא מחזיק פויינטר ל-NULL.

 

[דוד המקורי1]

הבנתי תודה

 

[selalerer]

אתה צריך לעשות null ל-next של אחד לפניו....

....ואין לך אותו.

 

[רוקמת מציאות]

מה בדיוק הבעיה?

תבדקי אם מדובר באיבר האחרון כשאת מחזיקה כל הזמן מצביע לקודם(כדי לשים לו NULLׂ בפוינטר

 

[Desslok of Gamilon]

הבעיה היא שלא קראת את השאלה זו שאלת ראיון ידועה: למחוק איבר מרשימה, כאשר נתון לך רק האיבר הזה - בלי מצביע לראש הרשימה, בלי דרך לחזור אחורה, בלי כלום. ולעשות את זה ב (O(1. אפשר לעשות את זה, אבל לא לאיבר האחרון ברשימה. לאיבר האחרון אין פתרון.

 

[רוקמת מציאות]

............

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