טוען...
טוען...
שים לב
בכל שאלה שנדרש בה מימוש אתה יכול להשתמש בפעולות של המחלקות תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם אתה משתמש בפעולות נוספות, עליך לממש אותן.
נגדיר רשימה דו־כיוונית כאוסף סדור של חוליות מטיפוס BinNode<Integer> המקושרות כך: לכל זוג חוליות p1, p2 ברשימה, אם מתקיים p1.getRight() == p2 אז מתקיים גם p2.getLeft() == p1. ברשימה דו־כיוונית יש לפחות שתי חוליות.
כלומר: כל חוליה ברשימה — חוץ מהחוליה שבקצה הימני של הרשימה והחוליה שבקצה השמאלי של הרשימה — מצביעה על החוליה שלפניה ועל החוליה שאחריה.
לפניך דוגמה לרשימה דו־כיוונית ומשתנה pos מטיפוס BinNode<Integer> המצביע על חוליה כלשהי ברשימה דו־כיוונית.
הפעולה firstLeft מקבלת מצביע pos שונה מ-null מטיפוס BinNode<Integer> המצביע על חוליה כלשהי ברשימה דו־כיוונית ומחזירה את החוליה השמאלית ביותר ברשימה.
הפעולה firstRight מקבלת מצביע pos שונה מ-null מטיפוס BinNode<Integer> המצביע על חוליה כלשהי ברשימה דו־כיוונית ומחזירה את החוליה הימנית ביותר ברשימה.
// שלד הפעולה firstLeft (להשלמה בסעיף א):
public static BinNode<Integer> firstLeft(BinNode<Integer> pos)
{
while ( ______________ )
pos = ______________ ;
return ______________ ;
}
// הפעולה what (נתונה — למעקב בסעיף ב):
public static boolean what(BinNode<Integer> pos)
{
BinNode<Integer> left = firstLeft(pos);
BinNode<Integer> right = firstRight(pos);
int sum = left.getValue() + right.getValue();
left = left.getRight();
right = right.getLeft();
while ((left != right) && (left.getRight() != right) &&
(left.getValue() + right.getValue() == sum))
{
left = left.getRight();
right = right.getLeft();
}
if (left == right)
return right.getValue() == sum;
if (left.getRight() == right)
return left.getValue() + right.getValue() == sum;
return false;
}לפניך שלד של הפעולה firstLeft. השלם אותו, כך שהפעולה תבצע את הנדרש.
לפניך הפעולה what המקבלת מצביע לחוליה כלשהי ברשימה דו־כיוונית ומחזירה ערך בוליאני. הרשימה הדו־כיוונית מכילה לפחות 3 חוליות.
עקוב אחר ביצוע הפעולה בעבור המשתנה pos והרשימה שבדוגמה המוצגת בתחילת השאלה. במעקב הראה את הרשימה הדו־כיוונית ואת ערכי המשתנים pos, left, right, sum.
לפניך הפעולה what המקבלת מצביע לחוליה כלשהי ברשימה דו־כיוונית ומחזירה ערך בוליאני. הרשימה הדו־כיוונית מכילה לפחות 3 חוליות.
קבע אם אפשר או אי אפשר להחליף את 3 השורות האחרונות שבפעולה — שתי הוראות ה-if וההוראה return false — בהוראה:
java1return left.getValue() + right.getValue() == sum;
נמק את קביעתך.
שים לב
בכל שאלה שנדרש בה מימוש אתה יכול להשתמש בפעולות של המחלקות תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם אתה משתמש בפעולות נוספות, עליך לממש אותן.
נגדיר רשימה דו־כיוונית כאוסף סדור של חוליות מטיפוס BinNode<Integer> המקושרות כך: לכל זוג חוליות p1, p2 ברשימה, אם מתקיים p1.getRight() == p2 אז מתקיים גם p2.getLeft() == p1. ברשימה דו־כיוונית יש לפחות שתי חוליות.
כלומר: כל חוליה ברשימה — חוץ מהחוליה שבקצה הימני של הרשימה והחוליה שבקצה השמאלי של הרשימה — מצביעה על החוליה שלפניה ועל החוליה שאחריה.
לפניך דוגמה לרשימה דו־כיוונית ומשתנה pos מטיפוס BinNode<Integer> המצביע על חוליה כלשהי ברשימה דו־כיוונית.
הפעולה firstLeft מקבלת מצביע pos שונה מ-null מטיפוס BinNode<Integer> המצביע על חוליה כלשהי ברשימה דו־כיוונית ומחזירה את החוליה השמאלית ביותר ברשימה.
הפעולה firstRight מקבלת מצביע pos שונה מ-null מטיפוס BinNode<Integer> המצביע על חוליה כלשהי ברשימה דו־כיוונית ומחזירה את החוליה הימנית ביותר ברשימה.
// שלד הפעולה firstLeft (להשלמה בסעיף א):
public static BinNode<Integer> firstLeft(BinNode<Integer> pos)
{
while ( ______________ )
pos = ______________ ;
return ______________ ;
}
// הפעולה what (נתונה — למעקב בסעיף ב):
public static boolean what(BinNode<Integer> pos)
{
BinNode<Integer> left = firstLeft(pos);
BinNode<Integer> right = firstRight(pos);
int sum = left.getValue() + right.getValue();
left = left.getRight();
right = right.getLeft();
while ((left != right) && (left.getRight() != right) &&
(left.getValue() + right.getValue() == sum))
{
left = left.getRight();
right = right.getLeft();
}
if (left == right)
return right.getValue() == sum;
if (left.getRight() == right)
return left.getValue() + right.getValue() == sum;
return false;
}לפניך שלד של הפעולה firstLeft. השלם אותו, כך שהפעולה תבצע את הנדרש.
לפניך הפעולה what המקבלת מצביע לחוליה כלשהי ברשימה דו־כיוונית ומחזירה ערך בוליאני. הרשימה הדו־כיוונית מכילה לפחות 3 חוליות.
עקוב אחר ביצוע הפעולה בעבור המשתנה pos והרשימה שבדוגמה המוצגת בתחילת השאלה. במעקב הראה את הרשימה הדו־כיוונית ואת ערכי המשתנים pos, left, right, sum.
לפניך הפעולה what המקבלת מצביע לחוליה כלשהי ברשימה דו־כיוונית ומחזירה ערך בוליאני. הרשימה הדו־כיוונית מכילה לפחות 3 חוליות.
קבע אם אפשר או אי אפשר להחליף את 3 השורות האחרונות שבפעולה — שתי הוראות ה-if וההוראה return false — בהוראה:
java1return left.getValue() + right.getValue() == sum;
נמק את קביעתך.