תיעוד C עם דוגמאות להרצה: מערכים רב-ממדיים

Q: איך מצהירים על מערך דו-ממדי ב-C?

כתבו שני גדלים בסוגריים מרובעים: int grid[3][4]; מצהיר על 3 שורות של 4 עמודות, 12 int בסך הכול. קראו את זה כ"מערך של 3 דברים, שכל אחד מהם הוא מערך של 4 int", וזה ממש האופן שבו C שומרת אותו.

Q: איך מעבירים מערך דו-ממדי לפונקציה ב-C?

הפרמטר חייב להצהיר על מספר העמודות: void print(int grid[][4], int rows) או באופן שקול void print(int (*grid)[4], int rows). אפשר להשמיט את מספר השורות כי המערך דועך למצביע לשורה, אבל בלי גודל העמודות הקומפיילר לא יכול לחשב איפה שורה מתחילה.

Q: אפשר לאתחל מערך דו-ממדי לאפסים בלבד?

כן: int grid[3][4] = {0}; מאפס כל איבר, כי כל איבר שלא מופיע ברשימה מאותחל לאפס. int grid[3][4] = {{1, 2}}; קובע את שתי הרשומות הראשונות של שורה 0 ומשאיר את עשר האחרות באפס.

מערך רב-ממדי הוא מערך שהאיברים שלו הם בעצמם מערכים. int grid[3][4]; הוא לא טיפוס מיוחד של רשת: אלה שלושה איברים, שכל אחד מהם הוא מערך של ארבעה int, שמאוחסנים ברצף. ברגע שזה מתיישב, כל השאר נובע מזה: הפריסה, החשבון של האינדקסים, והכלל שאחרת נראה מבלבל לגבי העברה שלהם לפונקציות.

שני ממדים מכסים כמעט כל שימוש מעשי: רשתות, טבלאות, מטריצות, לוחות משחק, תמונות, ולכן בזה העמוד הזה עוסק.

הצהרה ואתחול

int grid[3][4];        // 3 שורות, 4 עמודות: 12 int

המספר הראשון הוא כמה שורות, השני כמה עמודות. אפשר לכתוב אתחול שטוח או עם סוגריים מסולסלים פנימיים; כדאי להשתמש בסוגריים המסולסלים כי הם מראים את הצורה.

#include <stdio.h>

int main(void) {
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};   // סוגריים לפי שורה: הכי ברור
    int b[2][3] = {1, 2, 3, 4, 5, 6};       // שטוח: אותה תוצאה
    int c[2][3] = {{1, 2}, {4}};            // שורות חלקיות: השאר אפסים
    int d[2][3] = {0};                      // כל האיברים אפס
    int e[][3]  = {{1, 2, 3}, {4, 5, 6}};   // השורות מוסקות, העמודות חובה

    printf("a: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", a[i][j]);
    printf("\nb: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", b[i][j]);
    printf("\nc: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", c[i][j]);
    printf("\nd: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", d[i][j]);
    printf("\ne: "); for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) printf("%d ", e[i][j]);
    printf("\n");

    return 0;
}

הצורה int e[][3] חשובה: אפשר להשאיר ריק את מספר השורות ולתת לאתחול להחליט, אבל מספר העמודות אף פעם לא אופציונלי. החלק הבא מסביר למה.

פריסת row-major

C שומרת מערך דו-ממדי בסדר row-major: כל שורה 0, אחר כך כל שורה 1, וכן הלאה, בבלוק זיכרון רציף אחד. אין מאחורי הקלעים מערך של מצביעים לשורות.

int grid[3][4] = {{ 1, 2, 3, 4},
                  { 5, 6, 7, 8},
                  { 9,10,11,12}};

how you picture it            how it actually sits in memory
+----+----+----+----+
|  1 |  2 |  3 |  4 |   row 0   +--+--+--+--+--+--+--+--+--+--+--+--+
+----+----+----+----+           | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|
|  5 |  6 |  7 |  8 |   row 1   +--+--+--+--+--+--+--+--+--+--+--+--+
+----+----+----+----+            \__ row 0 __/\__ row 1 __/\_ row 2 _/
|  9 | 10 | 11 | 12 |   row 2
+----+----+----+----+           grid[i][j] is at element index i*4 + j

הנוסחה הזו, i * columns + j, היא כל המנגנון, וזו הסיבה שהקומפיילר חייב לדעת את מספר העמודות כדי לגשת לכל איבר. מספר השורות לא נכנס לחישוב אף פעם.

אפשר לראות את הפריסה ישירות על ידי הדפסת כתובות:

#include <stdio.h>

int main(void) {
    int grid[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

    printf("element addresses, in memory order:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            printf("grid[%d][%d] = %2d at %p\n", i, j, grid[i][j], (void *)&grid[i][j]);
        }
    }

    // אותו בלוק, נקרא כרצף שטוח אחד של 12 int
    printf("\nflattened: ");
    int *flat = &grid[0][0];
    for (int k = 0; k < 12; k++) {
        printf("%d ", flat[k]);
    }
    printf("\n");

    return 0;
}

הכתובות עולות ב-sizeof(int) בלי רווחים, כולל במקום שבו שורה אחת נגמרת והבאה מתחילה. הלולאה השטוחה מוכיחה את זה: flat[k] עובר על כל שנים עשר האיברים כרצף אחד.

לפריסה הזו יש גם השלכה על ביצועים ששווה להכיר: לולאה על שורות ואז עמודות נוגעת בזיכרון לפי הסדר, וה-cache של המעבד אוהב את זה. החלפת הקינון כך שהלולאה הפנימית יורדת לאורך עמודה קופצת בכל פעם בשורה שלמה ועלולה לרוץ לאט פי כמה על מערך גדול.

לולאות מקוננות

שני ממדים דורשים שתי לולאות for: החיצונית בוחרת את השורה, הפנימית סורקת את העמודות של השורה הזו.

#include <stdio.h>

#define ROWS 3
#define COLS 4

int main(void) {
    int grid[ROWS][COLS];

    // ממלאים בלוח הכפל
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            grid[i][j] = (i + 1) * (j + 1);
        }
    }

    // מדפיסים כטבלה
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%4d", grid[i][j]);
        }
        printf("\n");
    }

    // סכומי שורות וסכום כולל
    int grand = 0;
    printf("\nrow totals: ");
    for (int i = 0; i < ROWS; i++) {
        int rowSum = 0;
        for (int j = 0; j < COLS; j++) {
            rowSum += grid[i][j];
        }
        grand += rowSum;
        printf("%d ", rowSum);
    }
    printf("\ngrand total: %d\n", grand);

    return 0;
}

תנו למונים שמות לפי המשמעות שלהם (i/row לשורות, j/col לעמודות) ושמרו על סדר עקבי: grid[row][col] בכל מקום. חצי מכל הבאגים במערכים דו-ממדיים הם זוג אינדקסים שהתחלף.

הגדלים שהוגדרו עם #define הם גם לא קישוט: גבולות הלולאה וההצהרה כבר לא יכולים להתרחק זה מזה כשמשנים את הצורה.

העברת מערך דו-ממדי לפונקציה

זה הכלל שמכשיל את כולם: הפרמטר של הפונקציה חייב להצהיר על מספר העמודות.

#include <stdio.h>

#define COLS 4

// גודל העמודות חובה; מספר השורות מגיע כארגומנט נפרד
void print_grid(int grid[][COLS], int rows) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%4d", grid[i][j]);
        }
        printf("\n");
    }
}

// בדיוק אותו פרמטר, כתוב כמו המצביע שהוא באמת
void scale_grid(int (*grid)[COLS], int rows, int factor) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < COLS; j++) {
            grid[i][j] *= factor;
        }
    }
}

int main(void) {
    int grid[3][COLS] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

    print_grid(grid, 3);
    scale_grid(grid, 3, 10);
    printf("\nafter scaling:\n");
    print_grid(grid, 3);

    return 0;
}

הסיבה היא דעיכה. העברת grid ממירה אותו למצביע לאיבר הראשון שלו, והאיברים שלו הם שורות, כך שהטיפוס הוא int (*)[4]: מצביע למערך של 4 int. כדי ש-grid[i][j] יהיה בעל משמעות, הקומפיילר חייב לדעת מה האורך של שורה אחת, וזה ה-4. מספר השורות באמת לא נמצא בטיפוס, ולכן הוא עובר כארגומנט נפרד.

שימו לב ש-int (*grid)[COLS] ו-int grid[][COLS] הם אותו פרמטר בשתי צורות כתיבה. הסוגריים הכרחיים, כי int *grid[COLS] היה מערך של מצביעים. ההבחנה הזו מוסברת בעמוד על מצביעים ומערכים.

אם מספר העמודות ידוע רק בזמן ריצה, הפרמטרים עם גודל משתנה של C99 מאפשרים להעביר אותו קודם:

void print_any(int rows, int cols, int grid[rows][cols]);

את rows ואת cols חייבים להצהיר לפני פרמטר המערך שמשתמש בהם. במקומות שבהם זה לא זמין, החלופה הנפוצה היא מערך חד-ממדי שטוח ועוד חשבון אינדקסים ידני:

#include <stdio.h>
#include <stdlib.h>

// מתייחסים לבלוק שטוח כ-rows x cols ועושים את החשבון לבד
void print_flat(const int *data, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%4d", data[i * cols + j]);
        }
        printf("\n");
    }
}

int main(void) {
    int rows = 2, cols = 5;

    int *data = malloc((size_t)rows * cols * sizeof *data);
    if (data == NULL) return 1;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            data[i * cols + j] = i * 10 + j;
        }
    }

    print_flat(data, rows, cols);
    free(data);
    return 0;
}

data[i * cols + j] הוא בדיוק מה שהקומפיילר כותב בשבילכם במקרה של גודל קבוע. לעשות את זה ביד עולה שורה אחת ועובד לכל צורה שנקבעת בזמן ריצה.

דוגמה עם מטריצה

כפל מטריצות מחבר את כל העמוד: שלוש לולאות מקוננות על אחסון row-major.

#include <stdio.h>

#define N 3

void multiply(const int a[][N], const int b[][N], int out[][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int total = 0;
            for (int k = 0; k < N; k++) {
                total += a[i][k] * b[k][j];
            }
            out[i][j] = total;
        }
    }
}

void print_matrix(const char *label, const int m[][N]) {
    printf("%s\n", label);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%5d", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main(void) {
    int a[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int b[N][N] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}};
    int product[N][N] = {0};

    print_matrix("A:", a);
    print_matrix("B:", b);

    multiply(a, b, product);
    print_matrix("A x B:", product);

    // transpose של A במקום
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {     // מתחילים ב-i+1 כדי להחליף כל זוג פעם אחת
            int temp = a[i][j];
            a[i][j] = a[j][i];
            a[j][i] = temp;
        }
    }
    print_matrix("A transposed:", a);

    return 0;
}

שני פרטים ששווה להעתיק. הלולאה הפנימית על k מצמידה את a[i][k] ל-b[k][j]: אינדקס אחד הולך לאורך שורה, השני לאורך עמודה. ופעולת ה-transpose מתחילה את הלולאה הפנימית שלה ב-j = i + 1: התחלה ב-0 הייתה מחליפה כל זוג פעמיים ומשאירה את המטריצה בלי שינוי.

שלושה ממדים ומעבר להם

הדפוס מתרחב, וכך גם הכלל על פרמטרים של פונקציות: כל ממד חוץ מהראשון חייב להיות מוצהר.

#include <stdio.h>

int main(void) {
    // 2 שכבות, 3 שורות, 4 עמודות
    int cube[2][3][4] = {0};

    for (int z = 0; z < 2; z++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 4; j++) {
                cube[z][i][j] = z * 100 + i * 10 + j;
            }
        }
    }

    for (int z = 0; z < 2; z++) {
        printf("layer %d:\n", z);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 4; j++) {
                printf("%5d", cube[z][i][j]);
            }
            printf("\n");
        }
    }

    printf("\ntotal elements: %zu\n", sizeof cube / sizeof cube[0][0][0]);
    return 0;
}

בפועל, בשלושה ממדים מערכים בגודל קבוע מתחילים להרגיש מסורבלים, ורוב הקוד עובר לבלוק שטוח עם אינדקסים מחושבים או למערך של structs שנותן שם למשמעות של כל ציר.

טעויות נפוצות

לכתוב grid[i, j]. אופרטור הפסיק מחשב את i, זורק אותו, וניגש עם j. זה מתקמפל. זה שגוי. השתמשו ב-grid[i][j].
להחליף בין האינדקסים. grid[col][row] קורא איבר אמיתי מהמקום הלא נכון, כך שאין שגיאה שתתפוס את זה. שמרו על הסדר [row][col] בכל מקום.
להשמיט את גודל העמודות בפרמטר. void f(int grid[][]) לא מתקמפל, וזה הקומפיילר שמציל אתכם.
לחרוג מהגבולות. כמו בכל מערך, אין בדיקת גבולות. grid[0][5] ברשת של [3][4] קורא בשקט את grid[1][1], כי הפריסה רציפה והחשבון לא אכפת לו.

שאלות נפוצות

איך מצהירים על מערך דו-ממדי ב-C?

כתבו שני גדלים בסוגריים מרובעים: int grid[3][4]; מצהיר על 3 שורות של 4 עמודות, 12 int בסך הכול. קראו את זה כ"מערך של 3 דברים, שכל אחד מהם הוא מערך של 4 int", וזה ממש האופן שבו C שומרת אותו.

איך מערך דו-ממדי נשמר בזיכרון ב-C?

בסדר row-major: כל האיברים של שורה 0, אחר כך כל האיברים של שורה 1, וכן הלאה, בבלוק רציף אחד. grid[i][j] נמצא בהיסט של i * columns + j איברים מההתחלה, ולכן מספר העמודות הוא המספר שהקומפיילר צריך.

איך מעבירים מערך דו-ממדי לפונקציה ב-C?

הפרמטר חייב להצהיר על מספר העמודות: void print(int grid[][4], int rows) או באופן שקול void print(int (*grid)[4], int rows). אפשר להשמיט את מספר השורות כי המערך דועך למצביע לשורה, אבל בלי גודל העמודות הקומפיילר לא יכול לחשב איפה שורה מתחילה.

אפשר לאתחל מערך דו-ממדי לאפסים בלבד?

כן: int grid[3][4] = {0}; מאפס כל איבר, כי כל איבר שלא מופיע ברשימה מאותחל לאפס. int grid[3][4] = {{1, 2}}; קובע את שתי הרשומות הראשונות של שורה 0 ומשאיר את עשר האחרות באפס.

מושגים קשורים