שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2017 - רשימות מקושרות

לפניכם המחלקות IntNode ו-IntList. כל אחת בקובץ נפרד, כמובן. ```java public class IntNode { private int _value; private IntNode _next; public IntNode(int value, IntNode node) { _value = value; _next = node; } public IntNode getNext() { return _next; } public void setNext(IntNode node) { _next = node; } public int getValue() { return _value; } public void setValue(int value) { _value = value; } } public class IntList { private IntNode _head; public IntList() { _head = null; } } ``` נתונה רשימה מקושרת של קודקודים מסוג IntNode, כאשר _head מצביע על האיבר הראשון ברשימה: `{4, 2, 2, 5, 1}` השיטות הבאות נמצאות בתוך המחלקה IntList: ```java public static void f(IntNode p, IntNode q) { int tmp = p.getValue(); p.setValue(q.getValue()); q.setValue(tmp); } public int what() { IntNode p = _head, q = _head; int i = 0, j = 0; while (p != null) { if (p.getValue() != 0) { f(p, q); q = q.getNext(); j++; } p = p.getNext(); i++; } return i - j; } ``` (א) הפעילו את השיטה what על הרשימה `{4, 2, 2, 5, 1}`. מה יחזיר ערך what ואיזה ערך היא תחזיר?

רמז: השיטה f מחליפה ערכים בין שני צמתים. עקבו אחרי p ו-q כשעוברים על הרשימה ושימו לב מתי q מתקדם.

פתרון: נעקוב אחרי הביצוע על הרשימה `{4, 2, 2, 5, 1}`: השיטה **f** מחליפה ערכים בין שני צמתים. כל האיברים שונים מ-0, לכן בכל איטרציה f(p, q) מופעלת וq מתקדם: | איטרציה | p->value | q->value | f(p,q) | הרשימה | |---------|----------|----------|--------|--------| | 1 | 4 | 4 | swap(4,4) | {4,2,2,5,1} | | 2 | 2 | 2 | swap(2,2) | {4,2,2,5,1} | | 3 | 2 | 2 | swap(2,2) | {4,2,2,5,1} | | 4 | 5 | 5 | swap(5,5) | {4,2,2,5,1} | | 5 | 1 | 1 | swap(1,1) | {4,2,2,5,1} | $i = 5$, $j = 5$ הרשימה לא משתנה (כי p ו-q מתקדמים באותו קצב כשאין אפסים). השיטה מחזירה: $i - j = 5 - 5 = $ **0**