קיימת רשימה מקושרת חד-צדדית:

A -> B -> C -> D -> E -> F

מוחקים את איבר C.

איך אפשר לתקן את הרשימה, כך ש-B יצביע על D?

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

אני יודע את זה.

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

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

יכול להיות שמדובר בתשובה מתחכמת או איזשהו טריק.

למישהו יש פתרון?

אני מניח שהדבר הראשון שנשמר הוא המצביע ל-A?

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

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

במקרה הטוב זה יפעל, במקרה הפחות טוב זה יגרום ל-segmentation fault (התכנית תעוף), במקרה הרע זה יגרום לדריכת זכרון.

אז בלי לשמור, אתה פשוט משנה את המצביע...

ראש הרשימה הוא A.

אתם רוצים להגיד לי שאפשר פשוט לקבוע שה-Next של B יצביע על ה-Next->Next של B, כלומר על D?

לא נראה לי שמותר לעשות פעולה כזו.

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

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

אין פתרון אחר?

ץלוי איפה אתה יושב אחרי המחיקה. אם אתה יושב על B, אז אני לא יודע (אני אשאל מישהו שבטוח יודע....), אבל אם אתה יושב על D, אז תאורטית אתה יכול לקרוא ל D->E->F רשימה חדשה (כלומר להוציא אותם מאיפה שאתה נמצא ולשים ברשימת עזר), ואח"כ לאחד את הרשימות.

נראה לי שהוא לא זוכר את השאלה גם.

לדעתי השאלה היא (אני פשוט מכיר שאלה דומה)

בהנתן רשימה (כמו שציינת) ופוינטר ל C (בלבד) כיצד תמחוק את C ושהרשימה לא תתפרק (אגב אין לנו מצביע ל A - רק ל C)

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

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

HEYDADO,

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

במידה ויש לך מצביע לאיבר D, אז זה לא בעיה לאחד את שתי הרשימות, באמצעות הגדרה של מצביע נוסף (אין צורך ברשימת עזר).

לא נראה לי שיש לך מצביע לאיבר D, מכיוון שאז הפתרון פשוט מדי בשביל שאלה בראיון עבודה.

LinkTree,

שכתוב של הפונקציה Free זה פתרון די מופרך, כפי שאמרת.

אם אומרים שיש לך רשימה מקושרת חד-צדדית, אז אתה חייב שיהיה לך מצביע לראש הרשימה (כלומר, ל-A).

איזה פתרון יש לשאלה שהצגת?

בהנתן רשימה (כמו שציינת) ופוינטר ל C (בלבד) כיצד תמחוק את C ושהרשימה לא תתפרק (אגב אין לנו מצביע ל A - רק ל C)

Ghosthunter,

לא הבנתי מה אתה רוצה לעשות עם המערך.

למי מכוונת התגובה שלך?

זו שאלה לגיטימית כי יכול להיות שלמישהו אחר יש את המצביע לראש אבל לך בתוך פונקציה מסויימת אין

ולשכתב את FREE זה לא מופרך - מופרך זה לשכתב את מנגנון השחרור של מערכת ההפעלה. (זה אולי לא טריוואלי אבל עושים כאילו דברים מה גם שבמידה וזה CLASS ב C++ למשל אתה צריך לממש DISRACTOR בכל מיקרה)

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

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

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

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

זה פיתרון שעובד - אבל יש פיתרון יותר יעיל.

LinkTree,

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

הבנתי את הבעיה שהצגת.

במידה ואתה מדבר על פונקציה שמוחקת את C והיא מקבלת רק מצביע ל-C, אז ניתן לעשות את זה בצורה לא אלגנטית (הפונקציה אמורה בעיקרון לקבל מצביע ל-B).

הפתרון הוא שאתה צריך להעתיק ל-C את התוכן של D, לקשר אותו ל-E ולשחרר את D.

יש לך פתרון יותר פשוט?

LinkTree,

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

הבנתי את הבעיה שהצגת.

במידה ואתה מדבר על פונקציה שמוחקת את C והיא מקבלת רק מצביע ל-C, אז ניתן לעשות את זה בצורה לא אלגנטית (הפונקציה אמורה בעיקרון לקבל מצביע ל-B).

הפתרון הוא שאתה צריך להעתיק ל-C את התוכן של D, לקשר אותו ל-E ולשחרר את D.

יש לך פתרון יותר פשוט?

חח זה הפתרון...