רשימות מאוחדות (תכנות)

[יאיר של תמר]

רשימות מאוחדות (תכנות) ../images/Emo35.gif

שתי רשימות מקושרות (link lists) מתאחדות מתי שהוא לרשימה אחת (ראה ציור להמחשה).. תכנן אלגוריתם למצוא את האיבר הראשון המשותף (בדוגמא זה H). כל פיתרון יתקבל בברכה, ואולם מי שרוצה לאתגר את עצמו שינסה לעמוד בחלק (או בכל!) ההגבלות הבאות: 1. ביצוע ב O(N) z 2. צריכת זיכרון ב-O(1) z 3. ללא עדכון החצים (כלומר, אין לעדכן את ה-next של האיברים). 4. ללא עדכון האיברים (כלומר, לא ניתן להוסיף/לעדכן את תוכן האיברים) בהצלחה!

 

[Fingertip]

../images/Emo62.gifחידה חמודה

נניח שב-head1 יש את ראש הרשימה הראשונה וב-head2 יש את ראש הרשימה השנייה. 1) בצע מעבר אחד מ-head1 עד לסוף הרשימה ונספור את האברים, נסמן את מספרים ב-k1. 2) כנ"ל ל-head2. נסמן את מספרם ב-k2. 3) כעת נחליף בין המצביעים head1/head2 כך ש-head1 יצביע על ראש הרשימה שעבורה k1 ≥ k2. 4) קדם את המצביע של head1 בדיוק k1 - k2 אברים קדימה (אם k1 = k2 אל תעשה דבר). 5) כל עוד שני המצביעים אינם מצביעים על אותה חוליה ברשימה, בצע: 5.1) קדם את head1 ו-head2 חוליה אחת קדימה. 6) החוליה האחרונה בכל שרשרת נמצאת כרגע ב-headi. סיבוכיות לינארית, צריכת זכרון קבועה (בהנחה שגודל המספרים k1,k2 זניח ביחס לשאר הזכרון. אחרת זה לוגריתמי). לא עדכנו שם איבר או חץ. אהד.

 

[יאיר של תמר]

נכון...מאוד ../images/Emo127.gif../images/Emo70.gif ... ובכל זאת..

פתרת או שהכרת כבר?

 

[יאיר של תמר]

פשוט ... זה היה מהיר ../images/Emo13.gif

 

[Fingertip]

פתרתי

בהחלט חידה חמודה. אהד.

 

[יאיר של תמר]

מעולה ../images/Emo70.gif../images/Emo70.gif - וגם

אני חושב שהיא חמודה ! תודה