שאלה מספר 4 בגרות מדעי המחשב, קיץ תשע"ז, מס' 89938...
שאלה מספר 4 בגרות מדעי המחשב, קיץ תשע"ז, מס' 899381 פתרון מלא
א. מבנה הנתונים שאנו מציעים מורכב משני דברים:
רשימה מקושרת חד כיווניות
מצביע לסוף הרשימה
כיצד נממש את הפעולה insert:
אם הרשימה ריקה, פשוט נכניס את האיבר לראש הרשימה. O(1).
אם ברשימה יש איברים, נחפש מיקום שבו ערכו של האיבר יהיה גדול מימינו וקטן משמאלו.
לדוגמה:
5 → 8→ 10 →null
אנו מעוניינים להכניס את האיבר 6. במקרה זה האיבר מימינו של 6 גדול ממנו, והאיבר משמאלו קטן ממנו.
5 →6→ 8→ 10 →null
נכניס את האיבר במיקום הראשון שבו אחד משני התנאים הללו יתקיימו:
האיבר גדול משמאלו או האיבר קטן מימינו. במקרה הגרוע ביותר נעבור על כל האיברים O(n).
בכל מקרה נדאג לכך שמצביע לסוף הרשימה תמיד יהיה בסוף. במקרה הגרוע O(1).
כיצד נממש את הפעולה getMax:
נחזיר את ערכו של המצביע לסוף הרשימה. O(1).
כיצד נממש את הפעולה showMin:
נחזיר את ערכו של המצביע של תחילת הרשימה. O(1).
כיצד נממש את הפעולה exist:
עוברים על כל האיברים ובודקים האם הערך קיים או לא. O(n).