Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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

Несмотря на то что при стандартном (и не совсем стандартном) программировании используется огромное количество разного рода структур данных, большинство из них основаны на одном из двух фундаментальных контейнеров: массив и связный список. Если после прочтения этой книги вы научитесь правильно применять эти два типа структур, цель книги можно будет считать достигнутой. Они важны не только благодаря своей простоте, но и вследствие своей высокой эффективности. Массивы будут подробно рассмотрены в этой главе, а связные списки - в следующей. Кроме того, в главе 3 после связных списков будут описаны некоторые простые типы структур данных, основанные на этих двух фундаментальных типах. В главах 4 и 5, посвященных поиску и сортировке соответственно, мы также коснемся фундаментальных типов структур данных, но под несколько другим углом.

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

Во многих отношениях массивы являются простейшей структурой данных. Проще могут быть только такие базовые типы данных, как integer или Boolean. Массив (array) представляет собой последовательный список определенного количества элементов. Все элементы в массиве принадлежат к одному типу данных, и, как правило, хранятся в одном блоке памяти, т.е. каждый последующий элемент в памяти находится непосредственно после предыдущего. В таком случае говорят, что элементы массива являются смежными в памяти. Если ссылаться на элементы массива по их числовым индексам, то первый элемент будет иметь индекс 0 (или 1, или любое другое число, по крайней мере, в Delphi), значение индекса второго элемента будет больше на единицу и т.д. В коде элемент с индексом i обозначается как А[i], где А - идентификатор массива.

В Delphi имеется большой набор встроенных типов массивов. Кроме того, отдельные удобные типы массивов определены в библиотеке визуальных компонент VCL (Visual Component Library) в виде классов (и не только классов). Для поддержки таких классов, как массивы, разработчики Delphi предусмотрели возможность перегрузки операции массива, [], добавляя к нему новые свойства. Это единственная операция в Delphi, помимо + (сложение и конкатенация строк), которую можно перегружать.

В Delphi имеется три типа поддерживаемых языком массивов. Первый - стандартный массив, который объявляется с помощью ключевого слова array. Второй тип был впервые введен в Delphi 4 в качестве имитации того, что было давным-давно доступно в Visual Basic, - динамический массив, т.е. массив, длина которого может изменяться в процессе выполнения кода.

И последний тип массивов, как правило, не считается массивом, хотя в языке Object Pascal имеется несколько его вариаций. Конечно, мы говорим о строках: однобайтных строках (тип shortstring в 32-разрядной версии Delphi), строках с завершающим нулем (тип Pchar) и длинных строках в 32-разрядных версиях Delphi (которые имеют отдельную вариацию для "широких" символов).

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

Можно даже не сомневаться, что все вы знаете стандартный способ объявления массивов в Delphi. Так, объявление

var

MyIntArray : array [0..9] of integer;

создает массив из 10 элементов типа integer. В языке Object Pascal диапазон изменения индексов элементов можно выбирать любым (в приведенном случае - от 0 до 9). В следующем примере объявляется еще один массив из 10 элементов типа integer, но здесь индексация элементов следует от 1 до 10:

var

MyIntArray : array [1..10] of integer;