שאלות תרגיל בית 1

ערעור על הציון של סעיף 1 בחלק היבש

ערעור על הציון של סעיף 1 בחלק היבש

על ידי אוראל אדיבי בתאריך
מספר תגובות: 4

שלום רב,

במסגרת מימוש הפונקציה mergeSortedLists בסעיף 1 של החלק היבש של תרגיל בית 1, בחרנו לממש פונקציית עזר בשם allocateList שתפקידה לטפל בכלל הקצאות הזיכרון הנדרשות ליצירת הרשימה הממוזגת.

 

 allocateList

 

הפונקציה mergeSortedLists פועלת באופן הבא: היא מנסה להקצות רשימה מקושרת באורך נתון length (תוך שמירת המצביע ל־head). היא עושה זאת עד לסיום הקצאת הרשימה, או עד לכישלון הקצאת המקום (הבדיקה נעשית בלולאת ה-for). אם הקצאת הרשימה נכשלה, הפונקציה משחררת את כל הזיכרון שהוקצה ומחזירה NULL, אחרת היא מחזירה את הרשימה המבוקשת.

בבדיקת הסעיף, הורדו לנו 20 נקודות על שלכאורה לא בדקנו שההקצאה בוצעה כראוי ועל שלכאורה לא דאגנו לשחרור הזיכרון שהוקצה, במקרה של שגיאה.

עם זאת, ניתן לראות שהפתרון שהצענו אכן בודק שההקצאה בוצעה כראוי – הבדיקה נעשית הן ל־head והן לשאר החוליות באמצעות התנאי של לולאת ה-for – וכי הזיכרון שהוקצה משוחרר במקרה של כישלון – במקרה זה this יהיה NULL בסיום ניסיונות ההקצאה ולכן לולאת ה-while תפעל לשחרור כל המקום שהוקצה.

לאור זאת, אבקש לתקן את הציון של חלק זה.

בתגובה ל: אוראל אדיבי

תשובה ל: ערעור על הציון של סעיף 1 בחלק היבש

על ידי אורטל כהן בתאריך
היי,

במקרה שתהיה שגיאת הקצאה ויוצב ב-this הערך NULL - מה שיקרה הוא שעדיין תמשיכו בלולאה ואז באיטרציה הבאה אתם תפנו ל-this->next, אבל this הוא בעל הערך NULL ותהיה שגיאת זכרון (פנייה לערך שהוא NULL) ובמקרה הזה הזכרון שהוקצה עד כה לא ישוחרר.
לכן הפתרון הוא לפי הערת הבודק.
בתגובה ל: אורטל כהן

תשובה ל: ערעור על הציון של סעיף 1 בחלק היבש

על ידי אוראל אדיבי בתאריך
היי,

אינני מסכים עם טענתך.

אם באחד השלבים תקרה שגיאת הקצאה (בין אם ל־head ובין אם לחולייה כלשהי במרכז הרשימה), אז malloc יחזיר NULL, ולכן בסיום האיטרציה של לולאת ה-for זה יהיה ערכו של this. לכן, בבדיקה של הכניסה לאיטרציה הבאה של לולאת ה-for, המצביע this (כתנאי בוליאני, לפי כללי התחביר של שפת c) יהיה false, ולכן תנאי הביצוע של האיטרציה לא יתקיים (תנאי הביצוע דורש ששני הערכים הבוליאניים יהיו true). לפיכך, לאחר כישלון הקצאת זיכרון לא יבוצעו עוד איטרציות של הלולאה, בניגוד לנטען.

ולעניין שחרור הזיכרון – במקרה שהמצביע this הוא NULL, כלומר קרתה שגיאת הקצאה, יבוצע שחרור לכלל ההקצאות שבוצעו באמצעות כניסה ל־if (שכן !this הוא true בעבור this=NULL).

ראוי לציין כי כתיבת תנאי מורכב בלולאת for מותרת על פי כללי התחביר של השפה, ואינה נאסרה על פי מסמך מוסכמות הכתיבה של הקורס. כתיבת תנאי מורכב בלולאת for הודגמה בקורס 'מבוא למדעי המחשב' (234114), שהוא קדם לקורס זה.

כמו כן, חשוב לציין שהשמת ערך ה-malloc (כלומר כתובת ההקצאה) בגוף הלולאה אינה מתבצעת ל-this, אלא ל-this->next. במילים אחרות, לא מתבצעת גישה בשום שלב ל־next של NULL.

לאור האמור לעיל, אבקשך לבחון את העניין שוב.
בתגובה ל: אוראל אדיבי

תשובה ל: ערעור על הציון של סעיף 1 בחלק היבש

על ידי אוראל אדיבי בתאריך
אודה להתייחסות סגל הקורס