Массив – структура данных, которая представляет собой однородную, фиксированную по размеру и конфигурации совокупность элементов, упорядоченных по номерам. Массив определяется именем (индикацией) и размерностью (координатой) необходимых для указания местонахождения требуемого элемента. Для решения задач используются как правило одномерные, двумерные и трехмерные массивы.
Количество элементов определяет размерность массива. Индексы элементов задаются целочисленным типом данных. Массивы бывают статические и динамические.
Схема представления одномерного массива:
| А |
Синтаксис объявления одномерного массива:
int[] A = new int[6]
Инициализация массива:
int[] A = {2,1,7,4,5,8};
A[0] = 2;
A[1] = 1;
Вывод массива на экран:
for (int i=0; i<6; i++)
Console.Write(A[i] + “_”)
Если элементы массива не задали при объявлении массива, то они либо вычисляются, либо вводятся пользователем. Синтаксис объявления динамических массивов совпадает с объявлением статических массивов. Выражение, задающее количество элементов в динамическом массиве, содержит переменные. Значения этих переменных должны быть заданы до объявления массива.
Пример:
static void Main(string[] args)
{ //объявление массивов
int[] x = { 5, 5, 6, 6, 7 };
int[] A = new int[5], B = new int[5], C = new int[5];
int i, j;
const int N = 5;
Random rand = new Random();
for (i = 0; i < N; i++)
A[i] = rand.Next(10);
for (i = 0; i < N; i++)
Console.Write (A[i]+”_”);
19. Двумерные массивы: прямоугольные и ломаные (зубчатые). Назначение, синтаксис объявления, формы графического представления, пример.
В языке C# поддерживается 2 разновидности многомерных массивов: прямоугольные и ломаные. Прямоугольный массив имеет одинаковое количество столбцов в строке, в отличие от ломаного массива, который в каждой строке может иметь столбцы произвольной длины. Двумерные массивы используются в программировании довольно часто. К примеру, для вычисления матриц.
Схема представления двумерного прямоугольного массива:
| А | ||||||||
Синтаксис объявления:
int[] A = new int[4,5];
Инициализация:
{{1,2,3},{3,4,1},{…}…}
A[0,0] = 1;
A[0,1] = 2;
A[0,2] = 3;
Вывод на экран:
for (int i=0; i<4; i++)
{
for (int j=0; j<5; j++)
Console.Write(A[i,j] + “_”);
Console.WriteLine();
}
Схема представления ломаного массива:
Синтаксис объявления:
int[][] A = new int[4][];
for (int i=0; i<4; i++)
A[i] = new int[i+1]; // для каждой строки в цикле определяем количество столбцов, при этом каждый столбец на 1 элемент больше
Инициализация:
A[0][0] = 1;
A[0][1] = 2;
Вывод на экран:
for (int i=0; i<4; i++)
{
for (int j=0; j<A[i].lenght; j++)
Console.Write A[i][j] + “_”);
Console.WriteLine();
}
Прямые методы сортировки. Принципы методов, примеры сортировки (описать меняющееся состояние массива по итерациям).
Решение задач сортировки обычно выдвигается требованием минимального использования памяти в связи с чем не допускается использование дополнительных массивов.
Все методы условно делят на 2 группы:
- прямые методы сортировки (базовые);
- улучшенные методы (оптимизированные).
Основные базовые методы сортировки:
1) сортировка вставкой;
2) сортировка выбором;
3) сортировка обменом (пузырьковая);
4) быстрая сортировка.
Сортировка вставки
Массив разделяют на 2 части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть, так чтобы не нарушать упорядоченности элементов. В начале работы алгоритма в качестве отсортированной части массива принимается только один – первичный элемент, а в качестве неотсортированной части – все остальные.
Пример:
int cur, j;
for (int i=1; i<n; i++)
{
cur = A[i];
j=0;
while (cur>A[j]) j++;
for (int k=i-1; k>j; k--)
A[k+1] = A[k];
A[j] = cur;
}
Сортировка выбора
Находим (выбираем) в массиве элемент с минимальным значением и меняем его с 1 элементом. Находим элемент с наименьшим значением в шаге (интервале) от 2-го до последнего и ставим его вместо 2 элемента, меняем его и т.д.
…
Пример:
сonst int n=20;
int []A=new int [n];
Random r = new Random();
Console.WriteLine (“Неупоряд массив”);
for (int i=0; i<n; i++)
{
A[i] = r.Next(0,100);
Console.Write (A[i] + ”_”);
{
int Min, pos Min;
for (int i=0; i<n; i++) {
Min = A[i]; posMin=i;
for (int j=i1; j<n; j++) {
if (A[j]< Min) {Min=A[j]; posMin=j;}
}
A[posMin]=A[i]; A[i]=Min;
}
Console.Writeline(“Упоряд массив”);
for (i=0; i<n; i++)
Console.Write (A[i]+”_’);
Console.Read();
Сортировка обмена
Слева-направо поочередно сравниваются 2 последних элемента, если их взаимоположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся 2 следующих соседних элемента и т.д. до конца массива. После 1 такого прохода на последней позиции массива будет стоять максимальный элемент, поскольку макс элемент уже стоит на своей позиции то последующий проход выполняется по n-1 элемента, проходы выполняются до тех пор, пока массив не будет отсортирован, т.е. за проход не будет осуществлен ни одной перестановки.
Пример:
int temp; bool flag =true;
while(flag); {
flag = false;
for (int i=0; i<n-1; i++){
if(A[i]>A[i+1]) {
temp=A[i];
A[i]=A[i+1];
A[i+1]=temp;
flag=true;}}}
