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

בהנתן המבנה, ממשו את הפונקציות הבאות: ```c struct node { int val; struct node* next; }; typedef struct node node; ``` הנחיות כלליות: - אתם מקבלים מצביע לתחילת הרשימה. יש לשמור על הפרמטרים מעודכנים. - אין להשתמש בגלובלים או לשנות את החתימה של הפונקציות. - הכנסת איבר תמיד תהיה לסוף הרשימה. - שימו לב – שאין להקצות זיכרון מעבר לזיכרון שצריך. א. InsertValToList – פונקציית הכנסה לרשימה. (10 נקודות) - אם אין זיכרון, הדפיסו הודעת שגיאה וסיימו את הפונקציה ללא הכנסת איבר לרשימה. ```c void InsertValToList(node** head, int newVal) ``` ב. DeleteNodeFromList – מחיקת איבר מהרשימה. (10 נקודות) - אם המחרוזת לא נמצאת במערך, סיימו את הפונקציה. - אם המחרוזת נמצאת, מחקו אותה. ```c void DeleteNodeFromList(node** head, int val) ``` ג. DeleteList – מחיקת כל הרשימה. (10 נקודות) ```c void DeleteList(node* head) ``` ד. PrintList – הדפסת הרשימה. (5 נקודות) ```c void PrintList(node* head) ```

רמז: ב-InsertValToList: סרקו עד הסוף, צרו צומת חדש, חברו. ב-DeleteNodeFromList: השתמשו ב-node** (מצביע למצביע) כדי למחוק בקלות. ב-DeleteList: סרקו ושחררו כל צומת.

פתרון: **א. InsertValToList:** ```c void InsertValToList(node** head, int newVal) { node *n = (node*)malloc(sizeof(node)); if (!n) { printf("Error: no memory\n"); return; } n->val = newVal; n->next = NULL; if (!*head) { *head = n; return; } node *cur = *head; while (cur->next) cur = cur->next; cur->next = n; } ``` **ב. DeleteNodeFromList:** ```c void DeleteNodeFromList(node** head, int val) { node **cur = head; while (*cur) { if ((*cur)->val == val) { node *tmp = *cur; *cur = (*cur)->next; free(tmp); return; } cur = &(*cur)->next; } } ``` **ג. DeleteList:** ```c void DeleteList(node* head) { while (head) { node *next = head->next; free(head); head = next; } } ``` **ד. PrintList:** ```c void PrintList(node* head) { while (head) { printf("%d ", head->val); head = head->next; } printf("\n"); } ``` $\blacksquare$