# כלל ימין-שמאל ומערכים דו-ממדיים **סדנה בתכנות C ו-C++ — הרצאה 6 — HUJI** --- ## כלל ימין-שמאל טכניקה לפענוח הצהרות מורכבות בשפת C. ### האלגוריתם 1. מצא את ה**מזהה** (שם המשתנה) 2. הסתכל על סמלים **מימין** עד שפוגעים ב-`)`: - `()` פירושו "פונקציה" - `[]` פירושו "מערך" 3. הסתכל על סמלים **משמאל** עד שפוגעים ב-`(` 4. חזור על שלב 2 עד שההצהרה מושלמת ### דוגמאות ```c int x; // an int int *x; // a pointer to an int int x[5]; // an array of 5 ints int x[5][10]; // an array of 5 arrays of 10 ints const int x[5][10]; // an array of 5 arrays of 10 const ints int (*x)[5]; // a pointer to an array of 5 ints int *x[5]; // an array of 5 pointers to int int *const x[5]; // an array of 5 const pointers to int const int *x[5]; // an array of 5 pointers to const int int *(*x[5])[10][13]; // an array of 5 pointers to an array of 10 arrays of 13 pointers to int ``` !!! example "דוגמה: השוואה בין שתי תבניות נפוצות" ```c char (*arr)[5]; // arr is a pointer to an array of 5 chars char *arr[5]; // arr is an array of 5 pointers to char ``` אלו **טיפוסים שונים לחלוטין**! השתמשו ב-[cdecl.org](https://cdecl.org/) לאימות הצהרות מורכבות. --- ## מערכים רב-ממדיים ### שלוש גישות | גישה | הצהרה | זיכרון | יעילות | |-------|--------|--------|--------| | גודל קבוע (סטטי) | `double arr[4][8]` | רציף (מחסנית) | פעולת זיכרון אחת | | חצי-דינמי | `double *arr[4]` או `double (*arr)[8]` | מעורב (מחסנית + ערימה) | שתי פעולות זיכרון | | דינמי לחלוטין | `double **arr` | מפוצל (ערימה) | שלוש פעולות זיכרון | כל שלוש הגישות משתמשות באותו תחביר גישה: `arr[i][j]` --- ## I. מערכים בגודל קבוע ("סטטיים") ```c int arr[4][8]; ``` - **זיכרון רציף** על המחסנית - **יעיל**: פעולת זיכרון אחת לגישה לאיבר - הגודל חייב להיות ידוע ב**זמן קומפילציה** ``` Memory layout (row-major): arr[0][0] arr[0][1] ... arr[0][7] arr[1][0] arr[1][1] ... arr[3][7] ``` ### נוסחת גישה לאיבר ```c int A[R][C]; A[i][j] = 5; // equivalent to: *(*(A + i) + j) = 5 // which means: go to address [&A[0] + (i*C + j) * sizeof(int)] ``` --- ## II. מערכים חצי-דינמיים: `int *arr[4]` **מערך של 4 מצביעים ל-int** (מערך על המחסנית, שורות על הערימה): ```c int *pa[4] = {NULL}; for (int i = 0; i < 4; i++) { pa[i] = malloc(k * sizeof(int)); // k = 8 if (pa[i] == NULL) { /* handle error */ } } ``` ``` STACK HEAP pa: [0x557] ──────────→ [row 0: 8 ints] [0x28f] ──────────→ [row 1: 8 ints] [0x462] ──────────→ [row 2: 8 ints] [0x71c] ──────────→ [row 3: 8 ints] ``` **מאפיינים:** - גמיש: לכל שורה יכול להיות **גודל שונה** - שתי פעולות זיכרון לגישה לאיבר - מספר השורות חייב להיות ידוע בזמן קומפילציה ### אל תשכחו לשחרר! `free()` אחד לכל `malloc()`/`calloc()`: ```c for (int i = 0; i < 4; i++) { free(pa[i]); } ``` !!! warning "מלכודת נפוצה" **לא ניתן** להחזיר מערך בגודל קבוע מפונקציה. פונקציות יכולות להחזיר רק מצביעים, ו-`pa` יומר למצביע לאחסון שלו על המחסנית (שנהרס). --- ## II-b. חלופה: `int (*arr)[8]` **מצביע למערך של 8 ערכי int** (הקצאה רציפה על הערימה): ```c #define DIM1 4 #define DIM2 8 int (*pa)[DIM2] = calloc(DIM1, sizeof(*pa)); pa[1][6] = 10; return pa; // OK! Can pass ownership (heap memory) ``` ``` Stack Heap (contiguous) pa ─────→ [row 0][row 1][row 2][row 3] ^ pa[1][6] = 10 ``` - זיכרון רציף על הערימה - מספר העמודות חייב להיות ידוע בזמן קומפילציה - **ניתן** להחזיר מפונקציה (מוקצה על הערימה) --- ## III. מערכים דינמיים לחלוטין: `int **arr` ```c int **arr; arr = malloc(4 * sizeof(*arr)); // 4 pointers if (arr == NULL) { /* handle error */ } for (int i = 0; i < 4; i++) { arr[i] = malloc(8 * sizeof(**arr)); // 8 ints per row if (arr[i] == NULL) { /* handle error */ } } ``` ``` STACK HEAP arr ────→ [ptr0][ptr1][ptr2][ptr3] │ │ │ │ ▼ ▼ ▼ ▼ [row0] [row1] [row2] [row3] ``` **מאפיינים:** - הגודל יכול להיות לא ידוע בזמן קומפילציה - **שלוש** פעולות זיכרון לגישה לאיבר - הכי גמיש, הכי פחות יעיל !!! info "חשוב" בשימוש ב-`malloc()`, התאים **לא מאותחלים** עם ערכים תקינים. השתמשו ב-`calloc()` לאתחול לאפסים. ### שחרור מערכים דינמיים לחלוטין שחררו ב**סדר הפוך** של ההקצאה -- פנימי קודם, אחר כך חיצוני: ```c for (int i = 0; i < nrows; i++) { free(array[i]); } free(array); array = NULL; ``` !!! warning "מלכודת נפוצה" קריאה רק ל-`free(array)` בלי לשחרר את השורות יוצרת **דליפת זיכרון**. הקצאות השורות אובדות אבל לעולם לא משוחררות. --- ## דוגמה לדליפת זיכרון ```c void create_memory_leak() { int **m = malloc(sizeof(int*) * 3); for (int i = 0; i < 3; i++) { m[i] = malloc(sizeof(int) * 2); for (int j = 0; j < 2; j++) { m[i][j] = i + j; } } // Function returns without freeing! // All allocated memory is leaked. } ``` ### ניקוי נכון ```c // Free rows first, then the pointer array for (int i = 0; i < 3; i++) { free(m[i]); m[i] = NULL; } free(m); m = NULL; ``` --- ## argc ו-argv -- ארגומנטים משורת הפקודה ```c int main(int argc, char *argv[]) { // argc = argument count (including program name) // argv = argument vector (array of strings) for (int i = 0; i < argc; i++) { printf("%s ", argv[i]); } printf("%c", argv[0][0]); // first char of program name } ``` ```bash $ myprog 1 2 3 # argc == 4 # argv[0] -> "myprog" # argv[1] -> "1" # argv[2] -> "2" # argv[3] -> "3" ``` --- ## III-b. מערך דו-ממדי דינמי שטוח גישה יעילה יותר: הקצאה כ**מערך חד-ממדי** וחישוב אינדקסים ידני: ```c int *arr = malloc(5 * 7 * sizeof(int)); // Access: arr[i][j] becomes arr[i * ncols + j] arr[2 * 7 + 3] = 42; // equivalent to arr[2][3] = 42 ``` **יתרונות:** - גישה מהירה יותר לזיכרון (הקצאה רציפה אחת) - מימוש איטרטור קל יותר **חסרונות:** - קוד פחות קריא (ניתן להסתיר חלקית עם מאקרואים) --- ## מצביעים למצביעים ל-... ```c double **mat1 = get_matrix(); double **mat2 = get_matrix(); // Allocate an array of matrices double ***matrices = malloc(n * sizeof(double**)); matrices[0] = mat1; matrices[1] = mat2; ``` --- ## העברת מערכים רב-ממדיים לפונקציות ### תזכורת: מערכים חד-ממדיים מועברים כמצביעים ```c int foo(int *p); int foo(int a[]); // same int foo(int a[NUM]); // same! (NUM ignored) ``` ### מערכים דו-ממדיים עוקבים אחרי אותו כלל השתמשו בכלל ימין-שמאל: אם המשתנה הוא **מערך של \<משהו\>**, הוא מומר ל**מצביע ל-\<משהו\>**. לדוגמה, `int a[4][NUM]` הוא מערך של ארבעה מערכים בגודל NUM, ולכן הוא מועבר כמצביע למערך בגודל NUM. ```c // Passing a fixed-size 2D array (pointer to NUM-sized array): int foo(int (*p)[NUM]); int foo(int p[][NUM]); // same int foo(int p[4][NUM]); // same (4 is ignored) // Passing an array of pointers: int foo(int **p); int foo(int *p[]); // same int foo(int *p[NUM]); // same (NUM ignored) // ERROR: int foo(int p[][]); // 2nd dimension onward must be specified ``` ### התנהגות sizeof() ```c int bar(char arr_b[8]) { sizeof(arr_b); // == sizeof(void*), a pointer sizeof(*arr_b); // == sizeof(char) == 1 } int foo(char arr_a[][8]) { sizeof(arr_a); // == sizeof(void*), a pointer sizeof(*arr_a); // == 8 * sizeof(char) == 8 } ``` ### הממד הראשון הוא תמיד מצביע ```c // All three are equivalent: void func(int x[5][7][3]); // 5 is ignored void func(int x[][7][3]); // clearer void func(int (*x)[7][3]); // most explicit // Inside the function: sizeof(x); // == sizeof(int*) -- a pointer sizeof(*x); // == sizeof(x[0]) == 7 * 3 * sizeof(int) sizeof(x[0][5]); // == 3 * sizeof(int) ```