🧮 Едномерен масив в C++
Едномерният масив е фундаментална структура от данни, която се използва за съхраняване на множество стойности от един и същ тип. Това е непрекъсната последователност от елементи, които могат да бъдат достъпвани чрез индекси.
📝 Дефиниция и деклариране на едномерен масив
Едномерният масив се декларира чрез следния синтаксис:
Пример:
Инициализация:
Масивите могат да бъдат инициализирани по време на декларацията.
Ако броят на елементите е пропуснат, компилаторът го изчислява автоматично:
📦 Достъп до елементите на масив
Елементите на масива се достъпват чрез индекс, започващ от 0.
Пример:
#include <iostream>
using namespace std;
int main() {
int numbers[5] = {10, 20, 30, 40, 50};
cout << "Първи елемент: " << numbers[0] << endl;
cout << "Трети елемент: " << numbers[2] << endl;
return 0;
}
🔄 Присвояване и модификация на стойности
Стойностите в масива могат да бъдат променяни чрез индекса:
📚 Основни операции с едномерен масив
- Обхождане на масива
Масивите могат да бъдат обходени чрез цикъл.
Пример:
#include <iostream>
using namespace std;
int main() {
int numbers[5] = {10, 20, 30, 40, 50};
for (int i = 0; i < 5; i++) {
cout << "Елемент " << i << ": " << numbers[i] << endl;
}
return 0;
}
- Намиране на максимална и минимална стойност
#include <iostream> using namespace std; int main() { int numbers[5] = {10, 20, 5, 40, 15}; int max = numbers[0]; int min = numbers[0]; for (int i = 1; i < 5; i++) { if (numbers[i] > max) max = numbers[i]; if (numbers[i] < min) min = numbers[i]; } cout << "Максимум: " << max << endl; cout << "Минимум: " << min << endl; return 0; } - Сумиране на елементите
🧪 Често срещани грешки и решения
- Извън границите на масива
Достъпът до индекс извън валидните граници води до неочаквано поведение.
Решение: Уверете се, че индексът е в диапазона [0, размер - 1].
🚀 Приложения на едномерен масив
- Съхраняване на данни: Например, резултати от тестове, температури за определен период и др.
- Обработване на последователности: Например, изчисляване на средна стойност, филтриране и др.
- Програмни алгоритми: Например, сортиране, търсене и други основни операции.
🔍 Търсене в масив
Линейно търсене
Най-простият метод - проверяваме всеки елемент последователно:
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Връща индекса на намерения елемент
}
}
return -1; // Елементът не е намерен
}
Сложност: O(n) - в най-лошия случай проверяваме всички елементи
Бинарно търсене
Работи само върху сортиран масив. Много по-бързо от линейното търсене:
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Избягваме overflow
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Сложност: O(log n) - всяка стъпка намалява областта на търсене наполовина
🔄 Сортиране на масив
Bubble Sort (Сортиране с мехурчета)
Прост, но бавен алгоритъм. Подходящ за малки масиви:
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
Сложност: O(n²)
Selection Sort (Сортиране чрез избор)
Намираме минималния елемент и го поставяме на правилната позиция:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
Сложност: O(n²)
Използване на STL sort
В реални задачи използвайте вградената функция std::sort:
#include <algorithm>
int arr[100];
sort(arr, arr + n); // Сортиране във възходящ ред
sort(arr, arr + n, greater<int>()); // Низходящ ред
Сложност: O(n log n) - много по-бързо!
📊 Алгоритми за обработка на масиви
Ротация на масив
Премества всички елементи наляво или надясно:
void rotateLeft(int arr[], int n, int k) {
k = k % n; // За случаи когато k > n
reverse(arr, arr + k);
reverse(arr + k, arr + n);
reverse(arr, arr + n);
}
Намиране на втори най-голям елемент
int secondLargest(int arr[], int n) {
int first = INT_MIN, second = INT_MIN;
for (int i = 0; i < n; i++) {
if (arr[i] > first) {
second = first;
first = arr[i];
} else if (arr[i] > second && arr[i] != first) {
second = arr[i];
}
}
return second;
}
Премахване на дубликати от сортиран масив
int removeDuplicates(int arr[], int n) {
if (n == 0) return 0;
int j = 0; // Индекс за уникални елементи
for (int i = 1; i < n; i++) {
if (arr[i] != arr[j]) {
j++;
arr[j] = arr[i];
}
}
return j + 1; // Нов размер на масива
}
Merge на два сортирани масива
void merge(int arr1[], int n1, int arr2[], int n2, int result[]) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// Копиране на останалите елементи
while (i < n1) result[k++] = arr1[i++];
while (j < n2) result[k++] = arr2[j++];
}
🎯 Класически задачи
Задача 1: Kadane's Algorithm (Максимална подсума)
Намиране на максималната сума на последователни елементи:
int maxSubarraySum(int arr[], int n) {
int maxSoFar = arr[0];
int currentMax = arr[0];
for (int i = 1; i < n; i++) {
currentMax = max(arr[i], currentMax + arr[i]);
maxSoFar = max(maxSoFar, currentMax);
}
return maxSoFar;
}
Задача 2: Two Sum (Две числа със зададена сума)
bool twoSum(int arr[], int n, int target) {
sort(arr, arr + n);
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
return true;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return false;
}
Задача 3: Majority Element (Елемент, който се среща повече от n/2 пъти)
int findMajority(int arr[], int n) {
int count = 0, candidate = -1;
// Boyer-Moore Voting Algorithm
for (int i = 0; i < n; i++) {
if (count == 0) {
candidate = arr[i];
count = 1;
} else if (arr[i] == candidate) {
count++;
} else {
count--;
}
}
// Проверка дали кандидатът наистина е мнозинство
count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == candidate) count++;
}
return (count > n / 2) ? candidate : -1;
}
🧮 Работа със std::array (C++11)
Модерен начин за работа с масиви с фиксиран размер:
#include <array>
std::array<int, 5> arr = {1, 2, 3, 4, 5};
// Предимства:
arr.size(); // Винаги знаем размера
arr.at(2); // Проверка на границите
arr.front(); // Достъп до първи елемент
arr.back(); // Достъп до последен елемент
arr.fill(0); // Запълване с 0
💡 Съвети за оптимизация
- Използвайте vector вместо масив: По-гъвкаво и безопасно
- Избягвайте копиране: Подавайте масиви чрез указатели или референции
- Предварително заделяне: Ако знаете размера, заделете памет предварително
- Cache locality: Линейният достъп е по-бърз от произволния
🏁 Заключение
Едномерният масив е фундаментална структура, която е в основата на почти всички алгоритми. Овладяването на основните операции (търсене, сортиране, обработка) е критично за успеха в състезателното програмиране. Практикувайте с различни задачи, експериментирайте с алгоритми и постепенно ще развиете интуиция за ефективно използване на масиви! 🎯