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

נתונות שתי הפניות לראשי שרשרות של חוליות (מטיפוס Node<T> הסטנדרטי, עם הפעולות getValue/setValue/getNext/setNext ב-Java, GetValue/SetValue/GetNext/SetNext ב-C#): numHead - הפנייה לשרשרת חוליות של מספרים שלמים. charHead - הפנייה לשרשרת חוליות מטיפוס תו (char), שבה מיוצגות פעולות החשבון חיבור וחיסור ('+','-'). כמות החוליות בשרשרת המספרים גדולה ב-1 מכמות החוליות בשרשרת התווים (אין פעולת חשבון לפני המספר הראשון).

שילוב בין שתי השרשרות מייצג סדרת פעולות חשבון: התו במיקום 1 בשרשרת התווים מתאר את הפעולה שבאה לפני המספר שבמיקום 2 בשרשרת המספרים, התו במיקום 2 מתאר את הפעולה שבאה לפני המספר שבמיקום 3, וכן הלאה עד סוף השרשרות.

דוגמה (המשמשת לאורך השאלה כולה):

numHead:  [1]3 -> [2]5 -> [3]2 -> [4]3 -> [5]7 -> null
charHead: [1]+ -> [2]- -> [3]- -> [4]+ -> null

שרשראות אלה מייצגות את סדרת פעולות החשבון: 3 + 5 − 2 − 3 + 7 (=10).

שתי שרשרות מקושרות חד-כיווניות מקבילות: numHead (חוליות מספרים) ו-charHead (חוליות תווי פעולה).

numHead: [1]3 -> [2]5 -> [3]2 -> [4]3 -> [5]7 -> null
charHead: [1]+ -> [2]- -> [3]- -> [4]+ -> null

סעיף א

ממשו את הפעולה שלפניכם: len הוא כמות המספרים שנדרשה לחשב מתוך שרשרת המספרים (אין פעולת חשבון לפני המספר הראשון ולכן כמות התווים היא len-1 בהתאם). הפעולה תחזיר את תוצאת החישוב ברצף של len מספרים, החל מתחילת שרשרת המספרים ותחילת שרשרת התווים. הניחו ש-len גדול מ-0. אין לשנות את השרשרות שהתקבלו. הערה: אם len גדול מכמות החוליות בשרשרת המספרים, הפעולה תחזיר את תוצאת החישוב של כל המספרים בשרשרת. דוגמה: בעבור שתי השרשרות בדוגמה שלעיל ו-len=1, הפעולה תחזיר 3, כיוון שהוא המספר הראשון בשרשרת המספרים (היות שהוא המספר הראשון והיחיד, אין שום פעולת חשבון שצריך לבצע). דוגמה נוספת: בעבור אותן שתי שרשרות ו-len=3, הפעולה תחזיר 6 (3+5-2=6). דוגמה נוספת: בעבור אותן שתי שרשרות ו-len=8, הפעולה תחזיר 10 (3+5-2-3+7=10). הסבר: מספר החוליות בשרשרת המספרים קטן מ-8, ולכן הפעולה מחזירה את תוצאת החישוב של כל המספרים בשרשרת.

public static int eval (Node<Integer> numHead, Node<Character> charHead, int len)

סעיף ב

ממשו את הפעולה שלפניכם: הפעולה תחזיר true אם קיימת חוליה במיקום כלשהו בשרשרת המספרים וחוליה במיקום זהה בשרשרת התווים, שמהם והלאה יש len מספרים ברצף שתוצאת החישוב שלהם היא val (כלומר אם מתחילים את החישוב מן החוליה השנייה בשרשרת המספרים, גם פעולת החשבון הראשונה תהיה החוליה השנייה בשרשרת התווים). אחרת הפעולה תחזיר false. אפשר להשתמש בפעולה שכתבתם בסעיף א. הניחו ש-len גדול מ-0. אין לשנות את השרשרות שהתקבלו. שימו לב: אין פעולת חשבון לפני המספר הראשון בחישוב (מספר התווים הנדרש הוא len-1). הערה: אם מחוליה כלשהי יש פחות מ-len מספרים עד סוף השרשרת - החישוב מתבצע עד סוף השרשרת. דוגמה: בעבור שתי השרשרות המוצגות בדוגמה שלעיל, ו-len=3 ו-val=0, הפעולה תחזיר true, כי החל מן החוליה השנייה בשרשרת המספרים ומן החוליה השנייה בשרשרת התווים יש 3 מספרים ברצף שתוצאת החישוב שלהם היא 0 (5-2-3=0). דוגמה נוספת: בעבור שתי השרשרות המוצגות בדוגמה שלעיל, ו-len=3 ו-val=10, הפעולה תחזיר true, כי החל מן החוליה הרביעית בשרשרת המספרים ומן החוליה הרביעית בשרשרת התווים ועד סוף שרשרת המספרים תוצאת החישוב היא 10 (3+7=10).

public static boolean match (Node<Integer> numHead, Node<Character> charHead, int len, int val)

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

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

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

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

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