|
Страница 3 из 4
Любимая линейная однородная структура данных с прямым доступом — массив Массив – одна из простейших и наиболее широко применяемых в компьютерных программах структур данных. В любом языке программирования массивы имеют несколько общих свойств: - Содержимое массива хранится в непрерывной области памяти.
- Все элементы массива имеют одинаковый тип; поэтому массивы называют однородными (homogeneous) структурами данных.
- Существует пряммой доступ к элементам массива. (В случае других структур данных это необязательно так. Например, в четвертой части этой серии статей будет рассмотрена структура данных скип-список(SkipList). Для доступа к конкретному элементу скип-списка вы должны предварительно осуществить поиск среди других элементов скип-списка, пока не найдете требуемый элемент. В случае с массивами, если вы хотите получить доступ к i-му элементу массива, вы можете сделать это одной операцией: arrayName[i].)
Типичные операции для массивов включают: - Выделение элемента(Allocation)
- Доступ к элементу (Accessing)
- Изменение размеров массива (Redimensioning)
Когда в C# объявляется массив, его значение равняется null. Например,следующая строчка кода просто создает переменную с именем booleanArray , которая равна null: bool [] booleanArray;
Прежде, чем начать работу с массивом, мы должны выделить определенное количество элементов. Синтаксически это выглядит так: booleanArray = new bool[10];
Или более обобщенно: arrayName = new arrayType[allocationSize];
Этой строчкой мы выделяем непрерывный блок памяти в управляемой куче межъязыковой среды исполнения (CLR-managed heap), размер которого равен allocationSize, умноженному на размер элемента типа arrayType. Если arrayType – размерный тип (value type), то создаются allocationSize распакованных (unboxed) экземпляров типа arrayType. Если arrayType – ссылочный тип (reference type), то создаются allocationSize ссылок на объекты типа arrayType. (Если вы незнакомы с различиями между размерными и ссылочными типами CLR и тем, когда переменные размещаются в управляемой куче или стеке – ознакомьтесь со статьей Understanding .NET's Common Type System) Чтобы окончательно разобраться с тем, как в .NET Framework хранится внутреннее содержимое массива, рассмотрим следующий пример: bool [] booleanArray;
FileInfo [] files;
booleanArray = new bool[10];
files = new FileInfo[10];
Здесь, booleanArray – массив элементов размерного типа System.Boolean, а files – это массив элементов ссылочного типа System.IO.FileInfo. На Рисунке 1 показано состояние управляемой кучи CLR после выполнения этих четырех строк кода. Рисунок 1. Содержимое массива выделяется в виде непрерывного блока памяти в управляемой куче CLR Важно помнить, что 10 элементов массива files являются ссылками на экземпляры типа FileInfo. На Рисунке 2 эта ситуация видна особенно четко. На нем показано содержимое памяти, если мы присвоим некоторым элементам массива files экземпляры типа FileInfo. Рисунок 2. Содержимое массива располагается непрервывно в управляемой куче. Все массивы в .NET позволяют как считывать содержимое их элементов, так и записывать в них. Синтаксис для доступа к элементу массива выглядит следующим образом: // Чтение элемента массива
bool b = booleanArray[7];
// Запись в элемент массива
booleanArray[0] = false; Время доступа к элементу массива записывается как O(1) , т.к. оно равно константе. Т.е. независимо от количества элементов в массиве время чтения/записи одного элемента всегда одно и то же. Это время доступа постоянно лишь благодаря тому, что элементы массива хранятся в памяти последовательно и непрерывно, следовательно, для доступа к элементу массива необходимо знать лишь адрес в памяти первого элемента массива, размер каждого элемента массива и номер элемента, к которому необходим доступ. Важно понимать, что в управляемом коде (managed code) нахождение элемента массива(array lookups) происходит немного более сложным образом из-за того, что при каждом доступе к элементу массива CLR проверяет, что запрашиваемый индекс находится в пределах границ массива. Если указанный индекс попадает за границы массива, то происходит исключение IndexOutOfRangeException. Такая проверка гарантирует, что при прохождении массива мы случайно не выйдем за пределы последнего индекса массива и не испортим данные, записанные в этой области памяти. Стоит отметить, что эти проверки не влияют на эффективность массива, поскольку время затрачиваемое на них не увеличивается с увеличением размера массива. Примечание. Такие проверки границ массива лишь немного уменьшают производительность приложений, которые много раз осуществляют доступ к элементам массива. Однако, с помощью объявления кода неуправляемым (unmanaged code), можно обойти проверку границ массива. Об этом подробно написано в Главе 14 книги Дж. Рихтера "Программирование на платформе Microsoft .NET Framework". При работе с массивом вам может понадобиться изменить число элементов, которое этот массив должен содержать. Для этого вам придется создать новый экземпляр массива требуемого размера, а затем скопировать содержимое старого массива в новый массив нового размера. Этот процесс называют изменением размера массива (redimensioning) и его можно осуществить с помощью следующего кода: using System;
using System.Collections;
public class MyClass
{
public static void Main()
{
// создание массива целых чисел из 3 элементов
int [] fib = new int[3];
fib[0] = 1;
fib[1] = 1;
fib[2] = 2;
// Изменение размера до 10 элементов
int [] temp = new int[10];
// Копирование массива fib в temp
fib.CopyTo(temp, 0);
// Присвоим массиву temp значение fib
fib = temp;
}
} После выполнения последней строчки кода, fib ссылается на массив из 10 элементов типа Int32. Элементы с 3-го по 9-й в массиве fib будут иметь значение по умолчанию для типа Int32 – 0. Массивы являются превосходной структурой данных, если мы хотим хранить коллекцию однородных типов, к которым мы хотим иметь прямой доступ. Поиск в неотсортированном массиве занимает линейное от размера массива время. Это приемлемо, если мы работаем с маленькими массивами,или когда нам нужно лишь изредка производить поиск внутри массива. Если же ваше приложение хранит большие массивы, в которых часто производится поиск, то существуют структуры данных гораздо лучше приспособленные к таким ситуациям. Мы рассмотрим некоторые из них в следующих статьях этой серии. (Помните, что если вы производите поиск в массиве по некоторому ключу, а массив отсортирован по этому ключу, вы всегда можете использовать алгоритм двоичного поиска, сложность которого O(log n) , что эквивалентно времени поиска в двоичных деревьях. На самом деле, класс Array содержит статический метод BinarySearch(). Более подробно этот метод описан в более ранней статье автора Efficiently Searching a Sorted Array. Примечание .NET Framework поддерживает также и многомерные массивы. Многомерные массивы, как и одномерные требуют постоянного времени для доступа к своим элементам. Вспомните, что время поиска в n-элементном массиве равно O(n). Для двумерного массива размером nxn время поиска будет равно O(n2), потому что процедура поиска должна будет просмотреть n2 элементов. В более общем случае, время поиска в k-мерном массиве есть O(nk). |