מבנים לינאריים›רשימות מקושרות

נתונה המחלקה Game – משחק מחשב, ולה שתי תכונות:

• name – שם המשחק, מטיפוס מחרוזת. • price – מחיר המשחק – מספר הגדול מ־0 , מטיפוס שלם. הניחו שיש פעולות get/Get ו־set/Set לתכונות המחלקה. נתונה המחלקה Store – חנות משחקי מחשב, ולה תכונה אחת: • lst – הפניה לשרשרת חוליות שאינה ריקה, מטיפוס Game . כל חוליה בשרשרת מכילה משחק הנמכר בחנות. הערה: המשחקים אינם מסודרים בשרשרת בסדר מסוים, וכל משחק מופיע פעם אחת בלבד.

תרשים 1 (עמוד 2): השרשרת lst הנתונה בדוגמה של סעיף א – שבע חוליות

Store.lst --> [.|*]->[.|*]->[.|*]->[.|*]->[.|*]->[.|*]->[.|null]
each cell's data pointer goes down to a Game box:
1: name: "a", price: 30
2: name: "g", price: 30
3: name: "b", price: 27
4: name: "v", price: 99
5: name: "k", price: 30
6: name: "c", price: 25
7: name: "p", price: 30
(the four price values 30 are printed in bold on the paper)

תרשים 2 (עמוד 2): השרשרת בתום הפעולה remove(3, 30)

Store.lst --> [.|*]->[.|*]->[.|*]->[.|null]
1: name: "b", price: 27
2: name: "v", price: 99
3: name: "c", price: 25
4: name: "p", price: 30  (30 in bold)

תרשים 3 (עמוד 3): השרשרת בתום הפעולה remove(5, 30)

Store.lst --> [.|*]->[.|*]->[.|null]
1: name: "b", price: 27
2: name: "v", price: 99
3: name: "c", price: 25

תרשים 4 (עמוד 3): השרשרת בתום הפעולה removeCheap(5)

Store.lst --> [.|*]->[.|null]
1: name: "v", price: 99
2: name: "p", price: 30

סעיף א

ממשו את הפעולה של ממשק המחלקה Store שלפניכם: Java – public int remove (int n, int pr) C# – public int Remove (int n, int pr) הפעולה תמחק מן השרשרת n משחקים שמחיר כל אחד מהם pr . אם יש יותר מ־n משחקים שמחירם pr , יימחקו רק n המשחקים הראשונים מביניהם. אם יש פחות מ־n משחקים שמחירם pr , רק הם יימחקו. הפעולה תחזיר את כמות המשחקים שנמחקו (כלומר מקסימום n , אך ייתכן שפחות). הניחו ש־n ו־pr גדולים מ־0 . הערה: שאר המשחקים בשרשרת יישארו באותו הסדר. אם אין בשרשרת שום משחק במחיר pr , השרשרת תישאר ללא שום שינוי והפעולה תחזיר 0 . דוגמה: בעבור n = 3 , pr = 30 והשרשרת lst שלפניכם: [תרשים 1 ב-figures] הפעולה תחזיר 3 והשרשרת תיראה כך בתום הפעולה: [תרשים 2 ב-figures] הסבר: יש בשרשרת ארבעה משחקים שמחירם 30 . מכיוון ש־n = 3 , נמחקו שלושת המשחקים הראשונים בשרשרת שמחירם 30 , והפעולה החזירה 3 . דוגמה נוספת: בעבור אותה השרשרת מן הדוגמה המקורית שלעיל ו־n = 5 , pr = 30 , הפעולה תחזיר 4 והשרשרת תיראה כך בתום הפעולה: [תרשים 3 ב-figures] הסבר: יש רק ארבעה משחקים שמחירם 30 . לכן נמחקו מן השרשרת ארבעת המשחקים שמחירם 30 , והפעולה החזירה 4 .

סעיף ב

ממשו את הפעולה של ממשק המחלקה Store שלפניכם: Java – public int removeCheap (int num) C# – public int RemoveCheap (int num) הפעולה תמחק מן השרשרת את num המשחקים הזולים ביותר. הפעולה תחזיר את סכום המחירים הכולל של כל המשחקים שנמחקו. הניחו ש־num גדול מ־0 וקטן מכמות המשחקים בשרשרת. הערות: – המשחקים בשרשרת שלא נמחקו יישארו באותו הסדר. – אם כמות המשחקים שמחירם זהה גדולה מכמות המשחקים שצריך למחוק מהם, אין חשיבות איזה מהם יימחק. – אפשר להשתמש בפעולה שבסעיף א. דוגמה: בעבור אותה השרשרת מן הדוגמה המקורית בסעיף א ו־num = 5 , הפעולה תחזיר 142 , והשרשרת תיראה כך: [תרשים 4 ב-figures] הסבר: חמשת המשחקים הזולים יותר (25+27+30+30+30) נמחקו מן השרשרת וסכום מחירם הכולל הוא 142 . בשרשרת נשאר משחק אחד שמחירו 99 ואחד שמחירו 30 (אפשר להשאיר בשרשרת משחק אחר שעולה 30 , אין חשיבות איזה מהם יישאר).

שאלות ותגובות על השאלה

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה לתכנות עונה כאן — תקבלו מענה מקצועי

לתרגל עוד שאלות — חינם ←