Глава 3 Последовательности (массивы)

Алгоритмы и задачи, рассматриваемые в этой главе, являются частью фундамента, на котором строится образование программиста. Нет ни одной проблемной области, в задачах которой не требовались бы массивы. Поэтому задачи, требующие использования массивов появлялись уже в предыдущих главах, появятся они и в последующих. Но здесь мы будем заниматься ими целенаправленно. Аналогичная ситуация имеет место и в учебнике, где массивы появляются буквально в каждой главе, хотя им посвящены и отдельные главы 11 и 12, знание которых несомненно полезно для решения приводимых здесь задач.

Последовательность элементов – a₁, a₂, …. a_n – одна из любимых структур в математике. Последовательность можно рассматривать как функцию a(i), которая по заданному значению индекса элемента возвращает его значение. Эта функция задает отображение integer -> T, где T – это тип элементов последовательности.

В программировании последовательности называются массивами, но от этого они не перестают быть менее любимыми. Массив – это упорядоченная последовательность элементов одного типа. Порядок элементов задается с помощью индексов.

Для программистов важно то, как массивы хранятся в памяти. Массивы занимают непрерывную область памяти, поэтому, зная адрес начального элемента массива, зная, сколько байтов памяти требуется для хранения одного элемента, и, зная индекс (индексы) некоторого элемента, нетрудно вычислить его адрес, а значит и хранимое по этому адресу значение элемента. На этом основана адресная арифметика в языках C, C++, где адрес элемента a(i) задается адресным выражением a+i, в котором имя массива a воспринимается как адрес первого элемента. При вычислении адреса i-го элемента индекс i умножается на длину слова, требуемого для хранения элементов типа T. Адресная арифметика приводит к 0-базируемости элементов массива, когда индекс первого элемента равен нулю, поскольку первому элементу соответствует адресное выражение а+0.

Язык C# сохранил 0-базируемость массивов. Индексы элементов массива в языке C# изменяются в плотном интервале значений от нижней границы, всегда равной 0, до верхней границы, заданной динамически вычисляемым выражением, возможно зависящим от переменных. Массивы C# являются 0-базируемыми динамическими массивами. Это важно понимать с самого начала.

Не менее важно понимать и то, что массивы C# относятся к ссылочным типам. Рассмотрим следующий фрагмент программного кода:

int[] x, y = {1, 2, 3};

double[] z;

int[,] u, v = {{1,3,5},{2,4,6}};

Здесь объявлены пять переменных – x, y, z, u, v. Все они являются массивами, но разных типов. Переменные x и y принадлежат типу T = int[], задающему одномерные массивы с элементами целого типа int. Переменные u и v принадлежат другому типу T1 = int[,]- двумерных массивов с элементами целого типа. Переменная z принадлежит типу T3 –одномерных массивов с элементами вещественного типа double. Все три типа массивов – T1, T2, T3 являются наследниками общего родителя – типа (класса) Array, наследуя от родителя многие полезные свойства и методы. Все пять переменных являются типизированными ссылками. В момент объявления три переменные – x, z и u не инициализированы и потому являются «висячими» ссылками со значением null. Переменные y и v объявлены с инициализацией. При инициализации в динамической памяти создаются два объекта соответственно типов T1 и T3, фактически и задающие реальные массивы. У первого из этих объектов 3 элемента, у второго - 6. Ссылки y и v связываются с этими объектами. При связывании тип ссылки и тип объекта должны быть согласованными. Заметьте, число элементов в массиве является характеристикой объекта, а не типа. Ссылка может быть связана с объектами, содержащими различное число элементов, необходимо лишь выполнение условия согласования типов.

Дополним наш код следующими строчками:

x = new int[10];

z = new double[20];

u = new int[3, 5];

Здесь последовательно вызываются три конструктора типов T1, T2, T3, создающие новые три объекта в памяти и ссылки x, y, z связываются с этими объектами, так что у массива x теперь 10 элементов, z – 20, u -15.

Рассмотрим, что произойдет в результате присваивания:

x = y;

u = v;

Присваивание законно, поскольку переменные в левой и правой части имеют один и тот же (следовательно, согласованный) тип. В результате присваивания переменные порвут связь с теми объектами, с которыми они были связаны, и будут связаны с новыми объектами, так что x теперь имеет 3 элемента, u – 6. Присваивание для объектов – это, если хотите, развод и брак одновременно. Правда, для холостяков - неинициализированных переменных - это первый брак с объектом.

На этом закончу краткое представление массивов. Подробные сведения о них содержатся в упомянутых главах учебника 11 и 12.

Ввод – вывод массивов

Как у массивов появляются значения, как они изменяются? Возможны три основных способа:

• Вычисление значений в программе;

• значения вводит пользователь;

• связывание с источником данных.

В задачах этого раздела ограничимся пока рассмотрением первых двух способов. Первый способ более или менее понятен. Простые примеры его применения приводились чуть выше. Приведу некоторые рекомендации по вводу и выводу массивов, ориентированные на работу с конечным пользователем.

Для консольных приложений ввод массива обычно проходит несколько этапов:

• ввод размеров массива;

• создание массива;

• организация цикла по числу элементов массива, в теле которого выполняется:

  • приглашение к вводу очередного элемента;

  • ввод элемента;

  • проверка корректности введенного значения.

Вначале у пользователя запрашиваются размеры массива, затем создается массив заданного размера. В цикле по числу элементов организуется ввод значений. Вводу каждого значения предшествует приглашение к вводу с указанием типа вводимого значения, а при необходимости и диапазона, в котором должно находиться требуемое значение. Поскольку ввод значений – это ответственная операция, а на пользователя никогда нельзя положиться, то после ввода часто организуется проверка корректности введенного значения. При некорректном задании значения элемента ввод повторяется, пока не будет достигнут желаемый результат.

При выводе массива на консоль, обычно вначале выводится имя массива, а затем его элементы в виде пары: <имя> = <значение> (например, f[5] = 77,7). Задача осложняется для многомерных массивов, когда для пользователя важно видеть не только значения, но и структуру массива, например располагая одну строку массива в одной строке экрана. Приведу пример того, как может выглядеть ввод – вывод массива в консольном приложении. На рис. 1 показан экран в процессе работы консольной программы, организующей ввод массива.

Рис. 1 Ввод - вывод массива на консоль

На рис. 2 показана работа программы с контролем ввода, где пользователь повторяет ввод, пока не введет значение, удовлетворяющее типу элемента массива.

Рис. 2 Ввод - вывод массива на консоль с контролем значений

Как организовать контроль ввода? Наиболее разумно использовать для этих целей конструкцию охраняемых блоков – try – catch блоков. Это общий подход, когда все опасные действия, обычно связанные с работой пользователя, внешних устройств, внешних источников данных, размещаются в охраняемых блоках. Вот как может выглядеть ввод элемента массива z[i] типа double, помещенный в охраняемый блок:

bool correct;

do

{

correct = true;

try

{

z[i] = Convert.ToDouble(Console.ReadLine());

}

catch (Exception e)

{

Console.WriteLine

("Значение не корректно. Повторите ввод!");

correct = false;

}

} while (!correct);

Как правило, для ввода- вывода массивов пишутся специальные процедуры, вызываемые в нужный момент.

Ввод - вывод массивов в Windows приложениях

Приложения Windows позволяют построить дружелюбный интерфейс пользователя, облегчающий работу по вводу и выводу массивов. И здесь, когда данные задаются пользователем, заполнение массива проходит через те же этапы, что рассматривались для консольных приложений. Но выглядит все это более красиво, наглядно и понятно. Пример подобного интерфейса, обеспечивающего работу по вводу и выводу одномерного массива, показан на рис. 3.

Рис. 3 Форма для ввода – вывода одномерного массива

Пользователь вводит в текстовое окно число элементов массива и нажимает командную кнопку «Создать массив», обработчик которой создает массив заданной размерности. Затем он может переходить к следующему этапу – вводу элементов массива. Очередной элемент массива вводится в текстовое окно, а обработчик командной кнопки «Ввести элемент» обеспечивает передачу значения в массив. Корректность ввода можно контролировать и здесь, проверяя значение введенного элемента и выводя в специальное окно сообщение в случае его некорректности, добиваясь, в конечном итоге, получения от пользователя корректного ввода.

Для облегчения работы пользователя текстовое окно для ввода элемента сопровождается специальным окном, содержащим информацию, какой именно элемент должен вводить пользователь. В примере возможного интерфейса пользователя, показанного на рис. 3, после того, как все элементы массива введены, окно ввода становится недоступным для ввода элементов. Интерфейс формы позволяет многократно создавать новый массив, повторяя весь процесс.

На рис. 3 форма разделена на две части – для ввода и вывода массива. Крайне важно уметь организовать ввод массива, принимая данные от пользователя. Не менее важно уметь отображать существующий массив в форме, удобной для восприятия пользователя. На рисунке показаны три различных элемента управления, пригодные для этих целей – ListBox, CheckedListBox и ComboBox. Программа, форма которой показана на рис. 3, сделана так, что как только вводится очередной элемент, он немедленно отображается во всех трех списках.

Отображать массив в трех списках конечно не нужно, это сделано только в целях демонстрации возможностей различных элементов управления. Для целей вывода подходит любой из них, выбор зависит от контекста и предпочтений пользователя. Элемент CheckedListBox обладает дополнительными свойствами в сравнении с элементом ListBox, позволяя отмечать некоторые элементы списка (массива). Отмеченные пользователем элементы составляют специальную коллекцию. Эта коллекция доступна, с ней можно работать, что иногда весьма полезно.

Ввод двумерного массива немногим отличается от ввода одномерного массива. Сложнее обстоит дело с выводом двумерного массива, если при выводе пытаться отобразить структуру массива. К сожалению все три элемента управления, хорошо справляющиеся с отображением одномерного массива, плохо приспособлены для показа структуры двумерного массива. Хотя у того же элемента ListBox есть свойство MultiColumn, включение которого позволяет показывать массив в виде строк и столбцов, но это не вполне то, что нужно для наших целей – отображения структуры двумерного массива. Хотелось бы, чтобы элемент имел такие свойства, как Rows и Columns, а их у элемента ListBox нет. Нет их и у элементов ComboBox и CheckedListBox. Приходится обходиться тем, что есть. На рис. 4 показан пример формы, поддерживающей работу по вводу и выводу двумерного массива.

Рис. 4 Форма, поддерживающая ввод и вывод двумерного массива

Интерфейс формы схож с тем, что использовался для организации работы с одномерным массивом. Программная настройка размеров элемента управления ListBox позволила даже отобразить структуру массива. Но в общей ситуации, когда значения, вводимые пользователем, могут колебаться в широком диапазоне, трудно гарантировать отображение структуры двумерного массива. Однако ситуация не безнадежна. Есть и другие, более мощные и более подходящие для наших целей элементы управления. Если на элементах ListBox и подобных ему, я останавливаться не буду, оставляя их для самостоятельного изучения, то об элементе DataGridView расскажу подробнее.

Элемент управления DataGridView и отображение массивов

Элемент управления DataGridView является последней новинкой в серии табличных элементов DataGrid, позволяющих отображать таблицы. Главное назначение этих элементов – связывание с таблицами внешних источников данных, прежде всего с таблицами баз данных. Мы же сейчас рассмотрим другое его применение – в интерфейсе, позволяющем пользователю вводить и отображать матрицы – двумерные массивы.

Рассмотрим классическую задачу умножения прямоугольных матриц C=A*B. Построим интерфейс, позволяющий пользователю задавать размеры перемножаемых матриц, вводить данные для исходных матриц A и B, перемножать матрицы и видеть результаты этой операции. На рис. 5 показан возможный вид формы, поддерживающей работу пользователя. Форма показана в тот момент, когда пользователь уже задал размеры и значения исходных матриц, выполнил умножение матриц и получил результат.

Рис. 5 Форма с элементами DataGridView, поддерживающая работу с матрицами

На форме расположены три текстовых окна для задания размеров матриц, три элемента DataGridView для отображения матриц, три командные кнопки для выполнения операций, доступных пользователю. Кроме того, на форме присутствуют 9 меток (элементов управления label), семь из которых видимы на рис. 5. В них отображается информация, связанная с формой и отдельными элементами управления. Текст у невидимых на рисунке меток появляется тогда, когда обнаруживается, что пользователь некорректно задал значение какого-либо элемента исходных матриц.

А теперь перейдем к описанию того, как этот интерфейс реализован. В классе Form2, которому принадлежит наша форма, зададим поля, определяющие размеры матриц и сами матрицы:

//поля класса Form