Вектор и связанный список. Основные структуры данных

Основные структуры данных

Логические струтктуры данных

Часть 3. Типовые структуры данных

Пректирование пользовательского интерфейса

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

Типы.

Процедурно-ориентированные:

а) примитивный – взаимодействие в консольном режиме;

б) меню;

в) со свободной навигацией – графические пользовательские интерфейсы.

Объектно-ориентированные (прямого манипулирования).

Переписать из учебника.

API – интерфейс прикладного программирования (иногда интерфейс программирования приложений) (англ. application programming interface, API [эй-пи-ай])[1] — набор готовых классов, функций, структур и констант, предоставляемых приложением (библиотекой, сервисом) для использования во внешних программных продуктах.

API определяет функциональность, которую предоставляет программа (модуль, библиотека), при этом API позволяет абстрагироваться от того, как именно эта функциональность реализована.

Если программу (модуль, библиотеку) рассматривать как чёрный ящик, то API — это множество «ручек», которые доступны пользователю данного ящика, которые он может вертеть и дёргать.

1. Множества – важен только факт вхождения элемента в структуру; примеры: математические множества, таблицы реляционных баз данных.

2. Массивы – важно местоположение (номер) элемента; пример: массивы различной размерности.

3. Графы – важны связи между элементами; пример: деревья, сети, графы.

Примеры: очередь (FIFO, LIFO (стэк)), множество, дерево, поле указателей.

Под циклической структурой данных понимается набор однотипных элементов (массив). Существуют два принципиально различных способа размещения циклических структур данных в памяти компьютера: вектор и связанный список.

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

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

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

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

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

Вектор: более быстрый доступ к элементу; малые расходы памяти на вспомогательные структуры данных. Список: размер ограничен только объёмом доступной виртуальной памяти; более быстрое добавление и удаление элементов (кроме последнего). Эти достоинства и недостатки проявляются сильнее с увеличением числа элементов.

Итератор - указатель на определенный элемент составной структуры данных.

В связанных списках, как правило, обращение к элементу происходит не через индекс, а через итератор. Итераторы содержат методы перехода к следующему и предыдущему (для двусвязанного списка) элементу.