ЗАМЕЧАНИЕ
В некоторых языках программирования, например Си, строки реализованы как
одномерные массивы данных символьного типа.
Базовая операция для массива — взятие элемента по индексу. Поэтому
массив представляет собой структуру данных с произвольным доступом —
в любой момент за одинаковое количество времени возможен доступ к
любому месту в нем. Как правило, сравнение массивов одной операцией
60
недопустимо. Некоторые языки программирования, такие как APL и его
потомки K и J, изначально ориентированы на обработку массивов, в них
операции применимы к целому массиву (ко всем элементам). Например,
можно сложить два массива или найти сумму элементов с помощью
операции, записываемой одним знаком.
В некоторых языках программирования помимо обычных массивов
применяются так называемые ассоциативные массивы, в которых в
качестве индекса может использоваться не только целое число, но и
значение произвольного типа данных. Точнее говоря, ассоциативный
массив представляет собой набор пар вида
(ключ, значение) и
поддерживает операции добавления пары, а также поиска и удаления по
ключу (индексу). В некоторых языках поддержка ассоциативных массивов
встроена в язык, в других — нужно использовать стандартную библиотеку.
Примеры описаний ассоциативных массивов:
map book; //объявление язык С++, библиотека STL
$names["Петров"]="Петр"; // обращение в языке PHP, фамилия — ключ
print $hash{'cat'}; # язык Perl
Ассоциативный массив может быть и многомерным. Многомерные
ассоциативные массивы могут содержать несколько ключей,
соответствующих конкретному индексу ассоциативного массива.
Пример многомерного ассоциативного массива на языке PHP:
// Многомерный массив
$
A["Ivanov"] = array("name"=>"Иванов И.И.", "age"=>"25",
"email"=>"ivanov@mail.ru");
$A["Petrov"] = array("name"=>"
Петров П.П.", "age"=>"34",
"email"=>"petrov@mail.ru");
$A["Sidorov"] = array("name"=>"
Сидоров С.С.", "age"=>"47",
"email"=>"sidorov@mail.ru");
?>
Контрольные вопросы
1.
Что такое массив? Приведите примеры объявления в языках
программирования.
2.
Что такое одномерный и многомерный массивы? Приведите примеры
использования.
3.
Что такое статический и динамический массивы? Какие преимущества
и недостатки имеют динамические структуры данных?
4.
В чем заключаются особенности структуры данных с произвольным
доступом?
61
5.
Что такое ассоциативный массив? Приведите пример использования.
Списки
Следующей важнейшей структурой данных являются списки. Такого рода
структуры в языках программирования весьма разнообразны. Простейшей
является линейный односвязный список, реализованный на базовом уровне
в таких языках программирования, как Питон, Лисп и Пролог.
Линейный список представляет собой набор идущих друг за другом
элементов, при записи разделяемых пробелом, запятой или иным знаком,
например:
(Чайник Кастрюля Самовар)
[a,b,c,d,e]
В отличие от массивов, список, как правило, не предполагает возможности
взятия элемента по его номеру. Для взятия элемента из середины можно
начать последовательно перебирать их с первого, пока не будет найден
искомый. В этом смысле список представляет собой структуру
с
последовательным доступом. Для полноты вводится также понятие
пустого списка, или списка, не содержащего элементов, для которого
используется специальное обозначение:
NIL
—
в языке Лисп;
[]
—
одно из обозначений в языке Пролог.
Основными операциями над списками служат:
взятие первого элемента — так называемой головы списка;
взятие остатка списка, также являющегося списком, или его хвоста;
добавление элемента в список;
удаление заданного элемента из списка;
проверка на вхождение элемента в список;
приписывание списка к списку;
подсчет количества элементов списка.
В некоторых языках списки можно сравнивать одной операцией.
Список является динамической структурой данных — его размер может
меняться в ходе исполнения программы. Список является также так
называемой рекурсивной структурой — его понятие может быть
определено рекурсивно следующим образом: пустой список является
списком, кроме этого список — это элемент-голова, за которым идет,
возможно пустой хвост-список. В силу этого для обработки списков
хорошо подходят рекурсивные программы.
62
Во многих языках программирования списки не являются встроенной
структурой (хотя могут быть частью библиотеки, например, для С++
существует мощная библиотека STL), и их поддержка требует
конструирования на основе записей и ссылок (указателей). Это упражнение
весьма популярно при изучении Паскаля или Си. Такую реализацию
списка иллюстрирует рис. 9.
Рис. 9
Элементы подобного списка иногда называют вершинами. Каждая
вершина здесь представляет собой элемент однотипных данных, хотя это
могут быть и данные составного типа, и указатель на следующий элемент
списка. Последний элемент списка содержит пустую ссылку.
В языках программирования, поддерживающих списки на базовом уровне,
часто допускается наличие в списке в качестве элементов данных
различающихся типов. Элементом списка может быть и список — в этом
случае говорят о вложенных списках.
Другие виды списков
Нетрудно заметить, что в линейном односвязном списке возможно лишь
движение от головы к хвосту. Иногда удобно иметь возможность
обратного продвижения по списку. Для этого достаточно налачия в каждой
вершине двух указателей — на предшествующий и последующий
элементы. Графически реализацию двусвязного списка можно представить
следующим образом (рис. 10).
Д
|