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

אצל הירקן השכונתי מאכסנים ארגזי פירות או ירקות. בכל פעם שמגיע ארגז חדש מהחקלאי – שומרים אותו באזור הפירות או הירקות. בקדמת המכולת שומרים את הפירות, ולאחריהם שומרים את כל הירקות. לכל ארגז יש מאפיינים: סוג הירק/פרי (שם), אם זה פרי או ירק, ומה תאריך הגעת הארגז למכולת (ניתן להניח כערך int, כך שערך גבוה יותר אומר שהארגז יותר חדש). המידע אודות ארגזי הפירות והירקות נשמר ברשימה מקושרת דו כיוונית מסוג BoxItem: עם מצביע לאיבר הבא, ומצביע לאיבר הקודם ברשימה הכללית. בנוסף, אם יש שני ארגזים מאותו הפרי/ירק, הם נשמרים בערמה (stack). לכן בקופסאות נשמרות גם הצבעות לתחילה וסוף רשימת הפירות והירקות (ארגז מסוג כזה, כמאויר בדוגמה למעלה). מסגר מצביע ל-greengrocer, שבו יש מצביעים לתחילה וסוף רשימת הפירות והירקות. נתונות ההגדרות הבאות: ```c typedef enum {FRUIT, VEG} Type; typedef struct { char *name; Type type; int date; } Box; typedef struct BoxItem { Box* myBox; struct BoxItem *prev, *next, *vPrev, *vNext; } BoxItem; typedef struct { BoxItem *firstFruit, *lastFruit, *firstVeg, *lastVeg; int numBoxes; } Greengrocer; ``` א. (2 נק') כתבו פונקציה המאתחלת את מאגר המידע של הירקן. ```c Greengrocer* initGreen(); ``` ב. (3 נק') כתבו פונקציה המדפיסה את כל המידע אודות הארגזים בירקניה. ```c void printGreen(Greengrocer* gg); ``` ג. (6 נק') כתבו פונקציה המקבלת את רשימת הארגזים בירקניה ומצביע לארגז, ומוחקת אותו מהרשימה הכללית. אם הארגז הוא אחד מתוך ערמה של שני ארגזים, היא תשאיר את הארגז החדש יותר ברשימה הכללית. ```c void removeBox(Greengrocer* gg, BoxItem* item); ``` ד. (2 נק') כתבו פונקציה המקבלת מידע אודות ארגז חדש, יוצרת עבורו ארגז חדש, ומחזירה מצביע לארגז. ```c Box* createBox(const char* name, Type type, int date); ``` ה. (10 נק') כתבו פונקציה המקבלת מצביע לארגז, ומוסיפה אותו לירקניה. מטפלת במקרים: ארגז חדש מאותו סוג (ערמה), ארגז מסוג חדש (הוספה לרשימה), עדכון מצביעי firstFruit/lastFruit/firstVeg/lastVeg. ```c int addBox(Greengrocer* gg, Box* box); ``` ו. (8 נק') עושים מכירות חיסול בירקניה: "משטחים" ערמות (flattenGrocery) ומסדרים לפי תאריך הכנסה (BubbleSortBoxes). ```c void flattenGrocery(Greengrocer* gg); void BubbleSortBoxes(Greengrocer* gg); ``` ז. (4 נק') כתבו פונקציה המוחקת את כל הנתונים של הצרכניה. יש לממש פונקציית עזר **רקורסיבית** clearBoxes. ```c void clearGreen(Greengrocer* gg); void clearBoxes(BoxItem* p); ```

רמז: הרשימה דו-כיוונית עם מצביעים נוספים vNext/vPrev לערמות. ב-addBox: חפשו ארגז מאותו סוג; אם נמצא — ערמו (vNext/vPrev); אם לא — הוסיפו לרשימה (פירות בהתחלה, ירקות בסוף). ב-flattenGrocery: הכניסו כל ארגז מערמה לרשימה הראשית. ב-BubbleSortBoxes: bubble sort על הרשימה הדו-כיוונית לפי date.

פתרון: **שאלה מורכבת עם רשימה דו-כיוונית + ערמות (vNext/vPrev).** הפתרונות דומים במבנה לשאלות Q1 בשנים אחרות אך עם מורכבות נוספת של ערמות: **א.** malloc Greengrocer, אפס כל מצביעים ל-NULL, numBoxes=0. **ב.** עבור על הרשימה מ-firstFruit עד NULL, הדפס כל ארגז. אם יש vNext — הדפס גם ערמה. **ג.** removeBox: עדכן prev/next, טפל ב-vPrev/vNext (אם ערמה — השאר חדש יותר), עדכן first/last pointers. **ד.** malloc Box, strcpy name, set type, date. **ה.** addBox: חפש ארגז מאותו type+name. אם נמצא — ערום (vNext). אם לא — הוסף לרשימה (פירות לפני ירקות). עדכן first/last. **ו.** flattenGrocery: עבור על כל ארגז, אם vNext → הכנס לרשימה. BubbleSortBoxes: bubble sort על data pointers לפי date. **ז.** clearBoxes(p): if(!p) return; clearBoxes(p->next); if(p->vNext) free vNext chain; free p->myBox->name, p->myBox, p. clearGreen: clearBoxes(firstFruit); free gg. $\blacksquare$