Skip to content

📊 Двумерни масиви и обработка на таблична информация

📊 Двумерни масиви

Двумерният масив е структура от данни, която позволява съхранение на стойности в табличен формат (редове и колони). Те често се използват за представяне на матрици, таблици, игрални полета и други подобни структури.

Деклариране и инициализация на двумерен масив в C++

В C++ двумерните масиви се декларират чрез два комплекта квадратни скоби: 

int matrix[3][4]; // Декларира двумерен масив с 3 реда и 4 колони
Можем също да го инициализираме със стойности: 
int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};
Ако оставим C++ да определи броя на редовете: 
int matrix[][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

Достъп до елементи в двумерен масив

Достъпът до елементи става чрез индексите за ред и колона: 

int x = matrix[1][2]; // Взима стойността от втория ред, трета колона
matrix[0][1] = 42;   // Променя стойността на първи ред, втора колона

Въвеждане и извеждане на двумерен масив

#include <iostream>
using namespace std;

int main() {
    const int rows = 2, cols = 3;
    int matrix[rows][cols];

    cout << "Въведете стойности за двумерния масив:" << endl;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> matrix[i][j];
        }
    }

    cout << "Въведената матрица:" << endl;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Обработка на таблична информация

Двумерните масиви са полезни за съхраняване и обработка на таблични данни като оценки, резултати, статистики и други.

Пример: Намиране на сумата на всички елементи: 

int sum = 0;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        sum += matrix[i][j];
    }
}
cout << "Сумата на всички елементи е: " << sum << endl;

Пример: Намиране на максималния елемент: 

int maxVal = matrix[0][0];
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        if (matrix[i][j] > maxVal) {
            maxVal = matrix[i][j];
        }
    }
}
cout << "Максималната стойност е: " << maxVal << endl;

🎮 Специални видове матрици

Квадратна матрица

Матрица с еднакъв брой редове и колони (N x N). 

const int N = 4;
int square[N][N];

Главен и страничен диагонал

// Главен диагонал (елементи където i == j)
for (int i = 0; i < N; i++) {
    cout << square[i][i] << " ";
}

// Страничен диагонал (елементи където i + j == N - 1)
for (int i = 0; i < N; i++) {
    cout << square[i][N - 1 - i] << " ";
}

Транспониране на матрица

Размяна на редове и колони. 

void transpose(int matrix[][100], int rows, int cols) {
    int temp[100][100];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            temp[j][i] = matrix[i][j];
        }
    }
    // Копиране обратно
    for (int i = 0; i < cols; i++) {
        for (int j = 0; j < rows; j++) {
            matrix[i][j] = temp[i][j];
        }
    }
}

Матрично умножение

void multiply(int A[][100], int B[][100], int C[][100], int n, int m, int p) {
    // A е n x m, B е m x p, C ще е n x p
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;
            for (int k = 0; k < m; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

🗺️ Двумерни масиви в задачи с лабиринти и графи

Обхождане на съседи (4 посоки)

int dx[] = {-1, 1, 0, 0}; // Горе, долу, ляво, дясно
int dy[] = {0, 0, -1, 1};

for (int dir = 0; dir < 4; dir++) {
    int newX = x + dx[dir];
    int newY = y + dy[dir];

    if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
        // Валидна позиция
    }
}

Обхождане на съседи (8 посоки)

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

for (int dir = 0; dir < 8; dir++) {
    int newX = x + dx[dir];
    int newY = y + dy[dir];

    if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
        // Валидна позиция
    }
}

Flood Fill алгоритъм

Запълване на област с нов цвят (подобно на инструмента "bucket fill" в графични редактори). 

void floodFill(int grid[][100], int x, int y, int rows, int cols, int oldColor, int newColor) {
    if (x < 0 || x >= rows || y < 0 || y >= cols) return;
    if (grid[x][y] != oldColor) return;

    grid[x][y] = newColor;

    floodFill(grid, x-1, y, rows, cols, oldColor, newColor);
    floodFill(grid, x+1, y, rows, cols, oldColor, newColor);
    floodFill(grid, x, y-1, rows, cols, oldColor, newColor);
    floodFill(grid, x, y+1, rows, cols, oldColor, newColor);
}

💾 Динамично алокиране на двумерни масиви

Използване на vector<vector<int>>

#include <vector>
using namespace std;

int main() {
    int rows = 5, cols = 4;
    vector<vector<int>> matrix(rows, vector<int>(cols, 0));

    // Достъп до елементи
    matrix[2][3] = 10;

    // Обхождане
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

📐 Префиксни суми в 2D

Префиксните суми в 2D позволяват бързо изчисляване на сумата на елементите в правоъгълна област.

void buildPrefix2D(int matrix[][100], int prefix[][101], int rows, int cols) {
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            prefix[i][j] = matrix[i-1][j-1] + 
                          prefix[i-1][j] + 
                          prefix[i][j-1] - 
                          prefix[i-1][j-1];
        }
    }
}

int rangeSum2D(int prefix[][101], int r1, int c1, int r2, int c2) {
    // Сума на правоъгълника от (r1, c1) до (r2, c2) включително
    // Използваме 1-базирана индексация за prefix
    return prefix[r2+1][c2+1] - 
           prefix[r1][c2+1] - 
           prefix[r2+1][c1] + 
           prefix[r1][c1];
}

🧱 Тип структура в C++. Масиви от структури.

🧱 Структури в C++

Структурите (struct) са потребителски дефинирани типове данни, които позволяват групиране на различни свързани стойности в една логическа единица.

Деклариране на структура

struct Student {
    string name;
    int age;
    double grade;
};
Тук Student е структура, съдържаща три полета: име, възраст и оценка.

Създаване и използване на структури

Student s1 = {"Иван", 20, 5.50};
cout << "Име: " << s1.name << ", Възраст: " << s1.age << ", Оценка: " << s1.grade << endl;

Масиви от структури

Можем да създадем масив от структури за съхранение на множество обекти.

Student students[3] = {
    {"Иван", 20, 5.50},
    {"Мария", 21, 5.80},
    {"Георги", 19, 4.90}
};

Въвеждане и извеждане на масив от структури

#include <iostream>
using namespace std;

struct Student {
    string name;
    int age;
    double grade;
};

int main() {
    const int size = 3;
    Student students[size];

    cout << "Въведете информация за студентите:" << endl;
    for (int i = 0; i < size; i++) {
        cout << "Име: ";
        cin >> students[i].name;
        cout << "Възраст: ";
        cin >> students[i].age;
        cout << "Оценка: ";
        cin >> students[i].grade;
    }

    cout << "Списък на студентите:" << endl;
    for (int i = 0; i < size; i++) {
        cout << students[i].name << " - Възраст: " << students[i].age << ", Оценка: " << students[i].grade << endl;
    }

    return 0;
}

Търсене и обработка на данни в масив от структури

Пример: Намиране на студент с най-висока оценка: 

Student bestStudent = students[0];
for (int i = 1; i < size; i++) {
    if (students[i].grade > bestStudent.grade) {
        bestStudent = students[i];
    }
}
cout << "Студент с най-висока оценка: " << bestStudent.name << " (" << bestStudent.grade << ")" << endl;

Пример: Среден успех на групата: 

double totalGrade = 0;
for (int i = 0; i < size; i++) {
    totalGrade += students[i].grade;
}
double averageGrade = totalGrade / size;
cout << "Среден успех на групата: " << averageGrade << endl;

🎯 Сортиране на структури

Използване на sort с компаратор

#include <algorithm>
#include <vector>

bool compareByGrade(const Student& a, const Student& b) {
    return a.grade > b.grade; // Низходящо по оценка
}

int main() {
    vector<Student> students = {
        {"Иван", 20, 5.50},
        {"Мария", 21, 5.80},
        {"Георги", 19, 4.90}
    };

    sort(students.begin(), students.end(), compareByGrade);

    for (const auto& s : students) {
        cout << s.name << ": " << s.grade << endl;
    }

    return 0;
}

Множествено сортиране

Сортиране по няколко критерия (първо по оценка, после по име). 

bool compareMultiple(const Student& a, const Student& b) {
    if (a.grade != b.grade) {
        return a.grade > b.grade; // По-висока оценка първа
    }
    return a.name < b.name; // При равни оценки - по азбучен ред
}

📊 Задачи за практика

  1. Ротация на матрица: Завъртете квадратна матрица на 90 градуса по часовниковата стрелка.
  2. Спирала: Обходете матрица по спирала (от външните елементи към центъра).
  3. Седловина точка: Намерете елемент, който е минимален в реда си и максимален в колоната си.
  4. Zigzag обхождане: Обходете матрица в зигзаг ред.
  5. Остров: Броене на "острови" в двоична матрица (свързани единици).
  6. База данни студенти: Създайте програма за управление на студенти с търсене, сортиране и филтриране.
  7. Паскалов триъгълник: Генерирайте първите N реда на Паскаловия триъгълник в матрица.

🏁 Заключение

Разбирането на двумерните масиви и структурите в C++ е ключово за ефективната обработка на таблична информация и обекти от реалния свят. Двумерните масиви позволяват работа с големи количества данни в табличен формат, докато структурите предоставят удобен начин за групиране на свързана информация. Масивите от структури комбинират двете концепции, осигурявайки мощен инструмент за програмиране. Префиксните суми в 2D са важна оптимизация за задачи със запитвания върху правоъгълни области. Уверете се, че разбирате индексацията, границите и основните алгоритми за обхождане на двумерни масиви. 🚀