Подразделы

Другие разделы

Дата и время

01/04/2025 03:37:44

Авторизация

Зарегистрироваться
Восстановить пароль

Линейные АТД

Список Массив и Строка Стек Очередь Двухсторонняя очередь Очередь с приоритетами Множество Словарь

Массив и Строка

АТД Массив также является представлением математической конечной последовательности, но в отличие от списка обеспечивает произвольный доступ к своим элементам по номеру (индексу).

Различают массивы переменного и фиксированного размера. Базовые операции для массива:

Операция	Эффективность	Вызов
конструктор $n$ элементов	$O(n)$	`std::vector<int> s(10);` `std::array<int,10> s;`
количество элементов	$O(1)$	`auto len=s.size();` или `ssize(s);`
$i$ -й элемент	$O(1)$	`auto x=s[i]; s[i]=x;` или `s.at(i)` с проверкой
получение итератора на первый элемент (конец массива)	$O(1)$	`auto f=s.begin(), e=s.end();`

Итератор массива можно перемещать на произвольное количество элементов за $O(1)$ с помощью операций += и -=.

vector поддерживает интерфейсы АТД Список и АТД Массив.

Так как array имеет фиксированный размер, то он не поддерживает операции вставки, удаления и создания пустого списка (только длину и получение итератора для последовательного доступа). Недостаток: нельзя определить обычную функцию (не шаблон), которой можно передавать аргумент array разных размеров.

После вставки или удалении элементов итераторы для vector становятся недействительными.

Варианты реализации массива:

массив фиксированного размера языка C;
массив фиксированного размера array;
массив переменного размера vector реализуется как структура с полями текущий размер, выделенный размер, указатель на массив выделенного размера;
если требуется быстрые операции вставки и удаления, то через нелинейную структуру данных

В классе vector в случае нехватки выделенного размера для добавления элемента происходит выделение памяти для массива в 2 раза большего размера. Это позволяет обеспечить амортизированную оценку $O(1)$ для операции добавления в конец массива.

Пример нелинейной структуры данных для массива (корневая декомпозиция):

Последовательность из $N$ элементов делится на кусочки по $|~ sqrt(N) ~|$ элементов. В массиве-каталоге размером $|~ sqrt(N) ~|$ записывается количество элементов $C_j$ в каждом куске и указатель на каждый кусок. Так как в кусок могут добавляться новые значения, для куска можно выделить память для $2*|~ sqrt(N) ~|$ элементов.

nsqrtn1

Для получения $i$ -го элемента сначала за $O(sqrt(N))$ действий находим по массиву-каталогу номер куска $k$ и за $O(1)$ берем элемент с номером $(i-sum_{j=0}^k C_j)$ из куска $k$ . При добавлении и удалении изменяем соответствующий кусок последовательности за $O(sqrt(N))$ . На рисунке показано изменение структуры данных после изменения 11-го элемента на -2, удаления 13-го и добавления 2 после 5-го и 0.6 после 9-го. $M$ операций может быть выполнено за $O(M*sqrt(N))$ .

nsqrtn2

Через каждые $O(sqrt(N))$ операций добавления и удаления необходимо обновлять структуру, чтобы размеры кусков снова стали $|~ sqrt(N) ~|$ . Это может быть выполнено за $O(N)$ . Если выполняется $M$ операций, то потребуется $M//sqrt(N)$ обновлений, суммарно $O(N*M//sqrt(N))=O(M*sqrt(N))$ . В сумме $O(M*sqrt(N))$ на выполнение операций и $O(M*sqrt(N))$ на обновления дают эффективность $O(M*sqrt(N))$ .

При размере последовательности $10^6$ элементов операции вставки и удаления будут выполняться в 1000 раз быстрее по сравнению с vector, но операции доступа к элементам выполняются в 1000 раз медленнее. Но если количество операций добавления и удаления составляет хотя 1% от количества операций доступа к элементам, то выгодно использовать именно такую структуру.

В следующем разделе будут рассмотрены структуры данных с эффективностью $O(log N)$ для всех операций.

АТД Строка является массивом переменного размера из символов.

Базовые операции для строк:

Операция	Эффективность	Вызов
конструктор (пустая строка)	$O(1)$	`string s;`
конструктор ( $n$ символов)	$O(n)$	`string s(n,'A');`
длина строки	$O(1)$	`size_t len=s.length();`
$i$ -й символ	$O(1)$	`auto x=s[i]; s[i]=x;` или `s.at(i)` с проверкой
сцепление строк	$O(n)$	`s=s1+s2;`
подстрока	$O(n)$	`s=s1.substr(pos,n);`
замена символов	$O(n)$	`s.replace(pos,n,s1);`
удаление символов	$O(n)$	`s.erase(pos,n);`
вставка символов	$O(n)$	`s.insert(pos,s1); s.insert(pos,k,'A');`

Кроме этого, string обеспечивает интерфейс АТД Список.

В классе string STL используется приём Small String Optimization. Строка длиной до 15 символов хранится в массиве фиксированного размера внутри объекта, и только при превышении этого ограничения выделяется динамическая память. Это позволяет существенно ускорить вычисления, так как коротких строк в программе обычно на порядок больше, чем длинных.