תפריט משתמש
|
||||||
קורס:"שפת C"
מתוך הספר: C - מדריך מקצועי 
הקצאות מקום למשתנים ושיקולי צריכת זיכרוןעד עתה טיפלנו במשתנים שמקומם בזיכרון הוקצה ע"י המהדר. לא נדרשה לשם כך התערבות שלנו - לא ביצענו הקצאת זיכרון למשתנים וכן לא טיפלנו בשחרור הזיכרון בתום השימוש. אופן העבודה בו המהדר מטפל בהקצאת המקום למשתנים - ללא הקצאת זיכרון מפורשת ע"י המתכנת - הוא פשוט ונוח מצד אחד, אך בעל חסרון משמעותי מצד שני: כאשר אנו עובדים עם מבני נתונים בגודל שאינו ידוע מראש אנו מקצים את הזיכרון המקסימלי האפשרי ובכך מבזבזים מקום. לדוגמא, את מערך התקליטורים הגדרנו בפרקים הקודמים כך: CD cd_array[ARRAY_SIZE];
אם ARRAY_SIZE הוא 500 למשל, ובתכנית השתמשנו רק ב- 50 רשומות, היא מנצלת בפועל רק 10 אחוזים מהזיכרון שהוקצה עבורה. יתירה מזאת, שדות המבנים עצמם מכילים הקצאות המתייחסות למקסימום: שם התקליטור (name), שם הלהקה (band) והקטגוריה (category) מוגדרים כולם כמחרוזות בעלות אורך מקסימלי אפשרי. דוגמא נוספת: בתכנית לניהול ספרייה (שניתנה כתרגיל בפרקים הקודמים) מחרוזות הכלולות ברשומת "ספר" מוגדרות כמערכים בגודל המקסימלי האפשרי, מטיפוס String : typedef char String[256]; typedef struct { String name; String writer; String publisher; int year; ... } Book;
גם כאן מבזבזים זיכרון ע"י התייחסות ל"מקרה הגרוע ביותר". מנגנון הקצאת זיכרון דינמיתבכדי לשפר את ניצולת הזיכרון בתכניות, הוגדר בשפת C מנגנון להקצאת זיכרון מפורשת ע"י המתכנת במהלך התכנית. הקצאת זיכרון מפורשת נקראת גם הקצאת זיכרון דינמית (dynamic memory allocation). הקצאות זיכרון דינמיות מבוצעת מתוך מאגר שמור של זיכרון הנקרא ערמה (heap). מאגר זיכרון מסוג זה מסופק לכל תכנית בתחילת ריצתה ומאפשר לה יכולת הרחבת משאבי הזיכרון שלה. כפי שראינו בפרק 6, "פונקציות", תהליך יצירת וטעינת התכנית לזכרון נראה כך:
אספקת ערמה לכל תכנית היא באחריות מערכת ההפעלה: מבנה הערמה, גודלה ופרטי מימוש נוספים תלויים בסוג מערכת ההפעלה בה התכנית מורצת. עם זאת, הפונקציות המבצעות את הקצאת הזיכרון ושחרורו בשפת C הן תקניות ואינן תלויות מערכת. קיימות 2 פונקציות עיקריות לטיפול בהקצאה ושחרור דינמיים של זיכרון:
void *malloc( size_t size );
typedef unsigned int size_t;
void free( void *ptr);
תכנית דוגמא: #include <stdio.h> #include <stdlib.h> void main() { char *str; /* allocate 80 chars for str */ str = malloc(80); if( str == NULL ) puts("Insufficient memory available"); else { puts("Enter a string:"); gets(str); puts("The string entered"); puts(str); /* free the allocated memory */ free(str); puts("Memory freed"); } } הסברכדי להשתמש בפונקציות ההקצאה והשחרור של הזיכרון יש להכליל את הספרייה stdlib.h :
#include <stdlib.h>
התכנית מגדירה מצביע לתו בשם str ומקצה לו זיכרון בגודל של 80 תווים: char *str; ... str = malloc(80); הפונקציה malloc() מבצעת הקצאת זיכרון מהערמה בגודל הנדרש ומחזירה את כתובתו, שמוצבת למצביע. תרשים הזיכרון בזמן ההקצאה:
תרשים הזיכרון לאחר ההקצאה:
בלוק הבתים שהוקצו מסומן ע"י מנהל הזיכרון כתפוס. אם הפונקציה malloc נכשלת - כלומר אם אין בנמצא זיכרון להקצאה - מוחזר NULL. הבדיקה מבוצעת ע"י if( str == NULL ) puts("Insufficient memory available");
לאחר הקריאה ל- free() משוחרר הבלוק שהוקצה: free(str); תרשים הזיכרון לאחר השחרור:
דוגמא נוספת - הקצאת זיכרון עבור מבנים: typedef struct { int x; float y; } S; S *ps; ps = malloc(10 * sizeof(S)); בדוגמא זו הקצינו 10 מבנים מסוג S:
ניתן כעת להתייחס אל הזיכרון המוקצה כאל מערך, לדוגמא: for(i=0; i<10; i++) { ps[i].x = i; ps[i].y = i*0.5; }
שחרור הזיכרון: free(ps); תכנית דוגמא: ספרייהבסעיף זה נממש תוכנה לניהול ספרייה כתוכנית המשך לתרגיל הסיכום מפרק 10, "מבנים". התוכנה תאפשר ביצוע פעולות שונות כגון: הוספת ספרים, מחיקה, מיון, הדפסת דו"ח וכו'. דרישות
הקצאה דינמית של מחרוזותראשית נגדיר רשומת ספר - את המחרוזות נגדיר כמצביעים ולא כמערכים: /* Book type */ typedef struct { char *name; char *writer; char *publisher; float cost; int year; int ID; } Book; וכעת רשומת ספר נראית כך בזכרון:
את גדלי המחרוזות נקצה בזמן ביצוע הקלט, עפ"י אורך המחרוזת הנקראת. לדוגמא, בכדי לקלוט את שם הספר (name) לתוך מבנה בשם book נבצע:
String temp;
gets(temp);
book.name = malloc((strlen(temp)+1);
strcpy(book.name, temp); הפונקציה strdupהפעולה שביצענו לעיל היא מסורבלת - אם נצטרך לבצע אותה על כל מחרוזת התכנית תהיה מורכבת ורגישה לשגיאות. בספרייה string.h קיימת פונקציה בשם strdup - תפקידה הוא לבצע את שתי הפעולות האחרונות בבת-אחת ובפשטות: gets(temp); book.name = strdup(temp); הסבר: הפונקציה strdup מוגדרת כך: char *strdup( const char *str); הפונקציה מקבלת כפרמטר מחרוזת, מקצה זיכרון בגודל מתאים, מעתיקה את המחרוזת המקורית לחדשה ומחזירה מצביע למחרוזת החדשה:
מכיוון שבפועל מבוצעת הקצאה דינמית, יש לדאוג לשחרור מתאים בסוף השימוש במחרוזת ע"י: free(book.name); פונקצית הקלט עבור רשומת ספר מובאת בעמ' 300. תרגילקרא/י סעיף זה בספר ובצע/י את התרגיל שבעמ' 301. מערכי מצביעיםהתכנית המטפלת בספרים עדיין אינה יעילה מבחינת הקצאת הזיכרון - המבנים עצמם מוקצים באופן סטטי. נשנה את הגדרת המבנים כך שגם הקצאתם תהיה דינמית. נגדיר מערך מצביעים למבנים: #define ARR_SIZE 1000 Book *array[ARR_SIZE]; int count=0; הקבוע ARR_SIZE מציין את גדלו המקסימלי של המערך. המשתנה מונה את מספר האיברים הנוכחי במערך. לדוגמא, תרשים זיכרון של מערך בגודל 1000 הכולל הקצאות של 4 ספרים:
אופן הוספת רשומה חדשה למערך המצביעים : if(count<ARR_SIZE) { array[count] = malloc(sizeof(Book)); book_input(array[count]); count++; } לצורך הנוחות, ניתן להגדיר טיפוס מצביע לספר באופן הבא: typedef Book* BookPtr; /* a pointer to Book struct */ ואת המערך ניתן כעת להגדיר כך: BookPtr array[ARR_SIZE]; הגדרת מבנה מערך מודולרילצורך מודולריות התכנית, רצוי להגדיר מבנה (struct) המתאר את המערך. מבנה זה יכלול את המצביע array למערך, את מספר האיברים הנוכחי ברשימה ומידע נוסף - לפי הצורך. לדוגמא, עבור רשימת הספרים נגדיר את המבנה: /* array structure */ typedef struct { BookPtr array[ARR_SIZE]; /* pointer to the book array */ int count; /* number of elements in the array */ } Array; המבנה המלא של המערך מוצג בתרשים הבא:
כעת התכנית המשתמשת יכולה להגדיר מערך ע"י Array arr1; אופן זה של הגדרת מערך מאפשר שימוש חוזר באותה תכנית להגדרת מספר מערכים, לדוגמא: Array arr1, arr2, arr3; בעמ' 303-304 מובאות פונקציות לטיפול במערך:
מיון מערך מצביעיםנניח שאנו מעונינים למיין את מערך הספרים. לשם כך נכתוב פונקציה בשם array_sort() הממיינת בשיטת מיון בועות. פונקציה זו נעזרת בפונקציה swap() להחלפה בין שני איברים סמוכים. הפונקציה swap מקבלת כפרמטרים מצביעים למצביעים לרשומות ספר: void swap(BookPtr *ppbook1, BookPtr *ppbook2) { BookPtr temp = *ppbook1; *ppbook1 = *ppbook2; *ppbook2 = temp; } ופונקצית המיון עצמה, array_sort : void array_sort(Array *parray) { int i,j; for(i=0; i < parray->count - 1; i++) for(j=0; j < parray->count- 1 - i; j++) if(parray->array[j]->ID > parray->array[j+1]->ID) swap(&parray->array[j], &parray->array[j+1]); }
מיון ע"י פונקצית הספרייה qsort()כפי שראינו בפרק 8, "מצביעים", הספרייה התקנית של שפת C כוללת פונקצית מיון בשם qsort(), הפועלת בשיטת מיון מהיר (Quick Sort) על מערך איברים מטיפוס כללי. שיטת מיון זו ממיינת את המערך ע"י ביצוע פעולות חלוקה ומיון רקורסיביים, והיא יעילה במרבית המקרים משיטת מיון בועות. אבטיפוס הפונקציה qsort() מוכרז כך בקובץ stdlib.h : void qsort( void *array, size_t count, size_t element_size, int compare(const void *element1, const void *element2 ) );
הפרמטרים שמקבלת הפונקציה :
הפונקציה qsort() תשתמש בפונקציה compare() בעת ביצוע המיון, כדי לבדוק האם להחליף בין איברים במערך. לדוגמא, נכתוב פונקצית השוואה בין שני מצביעים לספרים: /* compare 2 pointers to books and return value: > 0 if book1 > book2 < 0 if book1 < book2 = 0 if book1== book2 */ int book_compare(const void *ppbook1, const void *ppbook2) { BookPtr pbook1 = *(BookPtr *)ppbook1; BookPtr pbook2 = *(BookPtr *)ppbook2; return pbook1->ID - pbook2->ID; } כפי שניתן לראות, הפונקציה מגדירה את המצביעים מסוג const void *, בכדי שהפונקציה תתאים לממשק הכללי שהוגדר ב- qsort(). בתוך הפונקציה מבצעים המרה מפורשת של המצביעים ל- BookPtr * , ומציבים את הנתון המוצבע על ידם (מסוג BookPtr) למשתנים המתאימים בפונקציה: BookPtr pbook1 = *(BookPtr *)ppbook1; BookPtr pbook2 = *(BookPtr *)ppbook2; לבסוף משווים בין שני הנתונים ע"י חיסור שדה ה- ID:
return pbook1->ID - pbook2->ID;
וכעת נוכל לקרוא לפונקציה qsort() מתוך הפונקציה array_sort : void array_sort(Array *parray) { qsort((void *)parray->array, (size_t)parray->count, sizeof(BookPtr), book_compare); } הוספת ממשק למשתמשעד עתה ביצענו את הפעולות בתכנית הראשית באופן שרירותי: הגדרנו מערך מבנים, אתחלנו אותו, מיינו עפ"י שדה מסוים וכו' - כל זאת ללא התערבות המשתמש. בדרך כלל מהלך התכנית כולו מוכתב ע"י המשתמש: על התכנית לספק לו אפשרויות בחירה שונות בכל שלב ולאפשר לו לקבוע את מהלכה. מנגנון מסוג זה נקרא ממשק למשתמש (User Interface). קיימים סוגים רבים של ממשקי משתמש וסגנונות שונים. הם נחלקים ל- 2 קטגוריות עיקריות:
בשפת C אין הגדרה תקנית לספריית ממשקים גרפיים. ספריות אלו הן תלויות במערכת ובסביבת הפיתוח בה עובדים. לעומת זאת קלט/פלט תקני כן מוגדר בשפה (stdio) ובאמצעותו ניתן לבנות ממשק משתמש טקסטואלי. מכיוון שאנו כותבים תכניות לשפת C התקנית (ANSI-C), נבנה ממשק טקסטואלי לתכנית. הממשק למשתמש יבוא לביטוי בדרך כלל בפונקציה שתציג לו את תפריט האפשרויות השונות: void menu() { printf("\n\n\n\n\n"); puts("Book program main menu"); puts("-----------------------------------"); puts("a. Add a book to the array"); puts("d. Delete a book from the array"); puts("i. Find a book by ID"); puts("n. Find a book by name"); puts("s. Sort the book array by ID"); puts("p. Print all books"); puts("x. Exit"); puts("\n\n\n\n\n\n\n\n"); } פונקצית עזר נוספת נדרשת בתכנית: void pause() { puts("\nHit Enter to continue"); getchar(); } בפונקציה main() תופעל הפונקציה menu(), בחירת המשתמש תיקרא ובהתאם תבוצע ההוראה. קוד הפונקציה מובא בעמ' 309. חלוקת התכנית לקבציםתכנית הספרייה הכוללת מחולקת לקבצים באופן הבא:
החלוקה למודולים מתוארת בתרשים המודולים הבא:
קוד התכנית בכללותו במלואו מובא בעמ' 311-316. הרחבת מערך ע"י reallocמערך המצביעים שראינו יעיל יותר, מבחינת הקצאת זיכרון, ממערכים רגילים אולם עדיין קיימת מגבלה רצינית בשימוש בו:
הפתרון לבעיה הוא הגדלת זיכרון המערך לפי הצורך. הרעיון: נקצה את המערך באופן דינמי לגודל התחלתי מסוים. אם נגיע למצב שהתפוסה מלאה ואין מקום להכניס איברים נוספים, נקצה זיכרון גדול יותר - למשל, פי 2 מהקיים - ונעתיק את תוכן המערך הישן לחדש. פונקצית הספרייה realloc עושה בדיוק פעולה זו: היא מקבלת כפרמטר מצביע לזיכרון וגודל הקצאה: void *realloc( void *ptr, size_t size ); realloc פועלת באחת משתי הדרכים:
תרגיליםקרא/י סעיף זה בספר ובצע/י את תר' 1-2 שבעמ' 318. רשימות מקושרותעד עתה השתמשנו במבנה נתונים בעל גודל סטטי: מערך. כפי שראינו, המערך הוא בעל מספר איברים מקסימלי שלא תמיד מנוצל במלואו. בעיה נוספת הקיימת במערכים היא הקושי בהוצאת ובהכנסת איברים חדשים למקום מסוים באמצע. לדוגמא, אם נרצה להכניס איבר חדש למערך ממוין, ונרצה שהוא יוכנס במקום המתאים, נצטרך להזיז את כל האיברים העוקבים לו מקום אחד קדימה - פעולה מאוד לא יעילה. רשימה מקושרת (Linked List) היא מבנה נתונים שגודלו דינמי וגמיש: ניתן להוסיף או להוציא איברים עפ"י הצורך ללא צורך בהכרזה מראש על מספר איברים מקסימלי. כמו כן פעולות הכנסה והוצאה מרשימה מקושרת הן פשוטות ויעילות יותר מאשר במערך. מבנה רשימה מקושרת:
רשימה זו מקושרת בכיוון אחד (singly linked list) : head הוא מצביע לאיבר הראשון ברשימה, וכל איבר ברשימה מכיל מצביע לאיבר הבא. האיבר האחרון מצביע ל- NULL, והוא מסומן בתרשים ע"י חץ לאדמה. כל איבר ברשימה נקרא צומת (Node) והוא מוגדר באופן הבא: struct Node { int data; struct Node *next; }; המשתנה head מוגדר כך:
struct Node *head;
הסבר: צומת מוגדר כרשומה המכילה בנוסף לנתונים גם מצביע מסוג הרשומה עצמה. head הוא מצביע לצומת הראשון ברשימה. המשתנה next שלו יצביע לצומת הבא ברשימה, המצביע next של הצומת הבא יצביע לצומת הבא אחריו ברשימה וכן הלאה.
רשימות מסוגים נוספיםקיימות רשימות מקושרות השונות במבניהן: רשימה מקושרת דו-כוונית:
במקרה זה קיימים שני מצביעים: המצביע head מצביע לתחילת הרשימה והמצביע last מצביע לסופה. כל צומת ברשימה מכיל שני מצביעים - אחד לצומת הקודם ואחד לצומת הבא. צומת הרשימה יוגדר כך: struct Node { int data; struct Node *prev; struct Node *next; }; המצביע prev של הצומת הראשון מצביע ל- NULL (מסומן כמחובר לאדמה), וכך גם המצביע next של הצומת האחרון. רשימה מקושרת חד-כוונית מעגלית:
הרשימה היא חד כוונית, כאשר האיבר האחרון מכיל מצביע לאיבר הראשון ולא ל- NULL. מבנה צומת ברשימה זו הוא כמו ברשימה החד-כוונית שלעיל. מימוש רשימה מקושרת בתכנית הספרייהנראה כעת כיצד מממשים רשימה מקושרת חד-כוונית. לשם כך נחזור לתכנית הספרייה ונחליף את מבנה הנתונים של הספרים - מערך - ברשימה מקושרת. ספר יוכנס לרשימה המקושרת עפ"י מספרו המזהה, כלומר הרשימה תהיה ממוינת תמיד על פיו. ניתן גם להוציא ספרים מהרשימה (תוך שחרור רשומת הספר). תזכורת: רשומת הספר מוגדרת כך /* Book type */ typedef struct { char *name; char *writer; char *publisher; float cost; int year; int ID; } Book; typedef Book* BookPtr; /* a pointer to Book struct */ הגדרת צומת ברשימההגדרת טיפוס צומת, ListNode: /* list node */ typedef struct ListNode_tag { BookPtr pbook; struct ListNode_tag *next; } ListNode; צומת הרשימה מכיל מצביע לרשומת ספר. הספר יוקצה דינמית בהכנסת צומת חדש לרשימה. הגדרת צומת ראשון כצומת דמי (dummy) מפשטת את הפעולות על הרשימה: ListNode first; צומת זה משמש כעוגן הקיים באופן תמידי. הגדרת מצביע לרשימה - head - מצביע ל- first : ListNode *head = &first; התרשים הבא מראה את תמונת הרשימה:
יש לשים לב שברשימה, בניגוד למערך, אין הגבלה (מלבד מגבלת הזיכרון הפיזי של המערכת) על מספר האיברים שבה! הגדרת מבנה הרשימה באופן מודולרילצורך מודולריות התכנית, רצוי להגדיר מבנה המתאר את הרשימה המקושרת. מבנה זה יכלול את המצביע head לתחילתה, את הצומת הראשון, את מספר האיברים הנוכחי ברשימה ומידע נוסף - עפ"י הצורך. לדוגמא, עבור רשימת הספרים נגדיר את המבנה: /* list structure */ typedef struct { ListNode *head; /* head of the book list */ ListNode first; /* first dummy element */ int count; } List; כעת התכנית המשתמשת יכולה להגדיר רשימה ע"י List list; המבנה המלא של הרשימה מוצג בתרשים הבא:
אופן זה של הגדרת הרשימה מאפשר שימוש חוזר באותה תכנית לשימוש במספר רשימות. לדוגמא, ניתן להגדיר מספר רשימות בתכנית אחת: List list1, list2, list3; אתחול הרשימההרשימה המקושרת תאותחל ע"י פונקציה המקבלת מבנה מסוג List כפרמטר: void list_init(List *list) { list->first.next = NULL; list->head = &list->first; list->count = 0; } כעת, מתוך התכנית המשתמשת נוכל להגדיר רשימה ולהעביר את כתובתה כפרמטר לפונקציה לשם אתחולה: void main() { List list; list_init(&list); ... } הוספת רשומת ספר לרשימהפונקציה להכנסת רשומת ספר חדשה לרשימה: void list_add_book(List *plist, BookPtr pbook) { ListNode *new_node, *p; new_node = malloc(sizeof(ListNode)); new_node->pbook = pbook; for(p=plist->head; p->next!=NULL ; p=p->next) if(new_node->pbook->ID < p->next->pbook->ID) break; /* at this point p->next is the place to insert */ new_node->next = p->next; p->next = new_node; plist->count++; }
הסבר: new_node הוא מצביע לצומת החדש המוקצה מפורשות ע"י malloc(). לאחר הקצאתו, מוצב לשדה pbook שבו המצביע לספר: new_node = malloc(sizeof(ListNode)); new_node->pbook = pbook; בשלב הבא עוברים בלולאה על איברי הרשימה עד למציאת המקום המתאים להכנסה - עפ"י מספר הזהות: for(p=list->head; p->next!=NULL ; p=p->next) if(new_node->pbook->ID < p->next->pbook->ID) break; לאחר יציאה מלולאת ה- for האיבר העוקב ל- p צריך להיות האיבר החדש. לדוגמא, אם המספר המזהה של הספר החדש הוא 52, תרשים הרשימה לאחר סיום הלולאה :
בשלב זה מוכנסת הרשומה החדשה למקומה ע"י ההוראות new_node->next = p->next; p->next = new_node; קוד התכנית המשתמשת לאתחול ולהוספת ספר לרשימה ייראה כך: List list; list_init(&list); ... pbook = malloc(sizeof(Book)); book_input(pbook); list_add_book(&list, pbook); הוצאה (מחיקה) מהרשימההוצאת רשומת ספר מהרשימה מבוצעת ע"י הפונקציה list_del_book() עפ"י מספר מזהה נתון של ספר. עיין/י בקוד הפונקציה בעמ' 325-326. פונקצית ההדפסהבפונקציה זו עוברים על כל איברי הרשימה (עד הגעה ל- NULL) ומדפיסים אותם ע"י קריאה לפונקציה book_output() . עיין/י בקוד הפונקציה שבעמ' 327. פונקציות החיפושבמימוש ע"י מערך, פונקציות החיפוש החזירו אינדקס של הרשומה שנמצאה במערך, ואם לא נמצאה החזירו ערך מיוחד (-1). במימוש הנוכחי ע"י רשימה, הפונקציות מחזירות מצביע לרשומה שנמצאה, ואם לא נמצאה מוחזר NULL. פעולות החיפוש:
עיין/י בקוד הפונקציות שבעמ' 327. חלוקת התכנית לקבציםתכנית הספרייה הכוללת מחולקת לקבצים באופן הבא:
תרשים המודולים:
קובץ הממשק של הרשימה booklist.h מובא בעמ' 328-329, כמו גם הפנייה לקבצי המקור של התכנית המלאה. סיכום
תרגילי סיכוםבצע/י את תרגילי הסיכום שבעמ' 330.
|
