Структуры данных — это способ систематической организации данных для эффективного их использования. Различные типы структур данных так или иначе используются почти в каждом корпоративном приложении. Пройдя это руководство, вы получите четкое представление о структурах данных, необходимое для понимания сложности приложений корпоративного уровня.
Базовыми для структуры данных являются следующие термины:
- Интерфейс — это набор поддерживаемых структурой данных операций. Он есть у каждой структуры данных. Интерфейс предоставляет только список поддерживаемых операций, тип принимаемых ими параметров, а также возвращаемый тип этих операций.
- Реализация — она обеспечивает внутреннее представление структуры данных, а также определение алгоритмов, используемых в операциях структуры данных.
Зачем изучать структуры данных и алгоритмы?
С ростом объема данных и сложности современных приложений связаны три основные проблемы:
- Поиск данных. Допустим, нам надо провести инвентаризацию 1 миллиона (1⁰⁶) элементов в хранилище. Если доверить ее приложению, с каждым разом поиск элемента среди такого их количества будет все медленнее, ведь объем данных растет.
- Скорость процессора, хотя и очень высокая, с ростом данных до миллиарда записей оказывается ограниченной.
- Множественные запросы. Если тысячи пользователей будут одновременно искать данные, даже быстрый веб-сервер выйдет из строя.
Решить эти проблемы помогают структуры данных, которые организованы так, что поиск по всем элементам не требуется, а нужные данные находятся почти мгновенно.
С помощью структур данных программно решаются следующие задачи:
- последовательность чисел Фибоначчи;
- задача о ранце;
- ханойская башня;
- поиск кратчайшего пути между всеми парами вершин (алгоритм Флойда-Уоршелла);
- поиск кратчайших путей от одной из вершин графа до всех остальных (алгоритм Дейкстры);
- планирование проектов.
Характеристики структуры данных
- Корректность. Интерфейс структуры данных должен реализовываться корректно.
- Временная сложность. Время выполнения операций структуры данных должно быть как можно меньшим.
- Пространственная сложность. Использование памяти при выполнении операции структуры данных должно быть как можно меньшим.
Случаи времени выполнения
Для сравнения времени выполнения различных структур данных обычно используется три случая:
- Наихудший случай — это сценарий, при котором конкретная операция структуры данных занимает максимально возможное время. Если время операции в наихудшем случае равно ƒ(n), то эта операция займет не более ƒ(n) времени, где ƒ(n) — это функция от n.
- Средний случай — это сценарий, описывающий среднее время выполнения операции структуры данных. Если на выполнение операции уходит ƒ(n) времени, то на m операций уйдет mƒ(n) времени.
- Наилучший случай — это сценарий, описывающий минимально возможное время выполнения операции структуры данных. Если на выполнение операции требуется ƒ(n) времени, то фактическая операция может потребовать время, обозначаемое случайным числом, которое будет максимальным в качестве ƒ(n).
Применение структур данных и алгоритмов
Алгоритм — это пошаговая процедура, которая определяет набор выполняемых в том или ином порядке инструкций для получения желаемого результата. Алгоритмы обычно создаются независимо от базовых языков программирования, т. е. с возможностью реализации на нескольких языках.
С точки зрения структур данных, важны следующие категории алгоритмов:
- Алгоритм поиска элемента в структуре данных.
- Алгоритм сортировки элементов в определенном порядке.
- Алгоритм вставки элемента в структуру данных.
- Алгоритм изменения имеющегося в структуре данных элемента.
- Алгоритм удаления элемента из структуры данных.
Базовая терминология
- Данные — это значения или набор значений.
- Элемент данных — это одиночная единица значений.
- Групповые элементы — это элементы данных, разделенные на подэлементы, называемые групповыми.
- Простейшие элементы — это неделимые элементы данных, которые называются примитивными.
- Атрибут и сущность. Сущность — это то, что содержит определенные атрибуты или свойства, которым могут быть присвоены значения.
- Набор сущностей — это сущности со схожими атрибутами.
- Поле — это одиночная элементарная единица информации, представляющая собой атрибут сущности.
- Запись — это набор значений полей сущности.
- Файл — это совокупность записей сущностей в наборе сущностей.
Необходимые условия
Прежде чем приступать к изучению серии руководства, нужно иметь базовое представление о языке программирования C, текстовом редакторе, выполнении программ и т. д.
Настройка локальной среды
Уже готовы настроить среду для языка программирования C? Тогда вам понадобятся следующие два инструмента: 1. текстовый редактор и 2. компилятор C.
Текстовый редактор
В текстовом редакторе (например, Windows Notepad, OS Edit command, Brief, Epsilon, EMACS, Vim или Vi) будет набираться программа.
Название и версия текстового редактора в разных операционных системах могут различаться. Так, Notepad используется на Windows, а Vim или Vi — на Windows и UNIX.
Файлы, создаваемые с помощью редактора, называются исходными файлами и содержат исходный код программы. Исходные файлы программ на языке С обычно имеют в названии расширение .c.
Чтобы начать программировать, кроме текстового редактора, у вас должно быть достаточно опыта для написания компьютерной программы, сохранения ее в файле, компилирования и выполнения.
Компилятор C
Написанный в исходном файле исходный код является удобным для восприятия человека источником программы. Его нужно скомпилировать, перевести на машинный язык, чтобы процессор мог выполнить программу в соответствии с заданными инструкциями.
Для компиляции исходного кода в конечную исполняемую программу будет использоваться компилятор языка программирования C. Предполагается, что у вас есть о нем базовые знания.
Самый используемый и доступный компилятор — GNU C/C++. Альтернативный вариант — компиляторы от HP или Solaris, если у вас есть соответствующая операционная система (ОС).
А теперь приступим к установке компилятора GNU C/C++ на различные ОС. C и C++ указаны вместе не случайно, ведь компилятор GNU GCC работает на обоих языках программирования.
Установка на UNIX/Linux
Используете ОС UNIX? Тогда проверьте, установлен ли GCC у вас на компьютере, введя в командной строке:
$ gcc -vЕсли компилятор GNU уже установлен, должно появиться похожее сообщение:
Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix = /usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)Если же нет, придется установить GCC самостоятельно (подробные инструкции доступны здесь на англ. яз: https://gcc.gnu.org/install/).
Установка на Mac OS
Проще всего установить GCC, загрузив среду разработки Xcode с сайта Apple и следуя простым инструкциям по установке. После настройки Xcode вы сможете использовать компилятор GNU для C/C++.
Xcode доступен здесь: developer.apple.com/technologies/tools/.
Установка на Windows
Чтобы заполучить GCC на Windows, потребуется установить MinGW. Для этого перейдите на домашнюю страницу MinGW и далее по ссылке на страницу загрузки. Загрузите последнюю версию программы установки MinGW с названием MinGW-<version>.exe.
Обязательный минимум при установке MinWG: gcc-core, gcc-g++, binutils и среда выполнения MinGW — но вы можете не ограничиваться этим и установить что-то еще.
Добавьте подкаталог bin из установки MinGW в переменную среды PATH, чтобы указывать эти инструменты в командной строке по их простым именам.
По завершении установки вы сможете запускать из командной строки Windows gcc, g++, ar, ranlib, dlltool и другие инструменты GNU.
Читайте также:
- Deepnote - новая IDE для специалистов по данным
- 5 ловких приемов Xcode для рефакторинга кода
- 5 алгоритмов, которые изменили мир
Читайте нас в Telegram, VK и Яндекс.Дзен
