Структура данных — это систематический способ организации данных для их эффективного использования. Следующие термины являются базовыми терминами структуры данных.
-
Интерфейс — каждая структура данных имеет интерфейс. Интерфейс представляет собой набор операций, которые поддерживает структура данных. Интерфейс предоставляет только список поддерживаемых операций, тип параметров, которые они могут принять, и возвращает тип этих операций.
-
Реализация — Реализация обеспечивает внутреннее представление структуры данных. Реализация также обеспечивает определение алгоритмов, используемых в операциях структуры данных.
Интерфейс — каждая структура данных имеет интерфейс. Интерфейс представляет собой набор операций, которые поддерживает структура данных. Интерфейс предоставляет только список поддерживаемых операций, тип параметров, которые они могут принять, и возвращает тип этих операций.
Реализация — Реализация обеспечивает внутреннее представление структуры данных. Реализация также обеспечивает определение алгоритмов, используемых в операциях структуры данных.
Характеристики структуры данных
-
Корректность — реализация структуры данных должна правильно реализовывать свой интерфейс.
-
Сложность времени — время выполнения или время выполнения операций структуры данных должно быть как можно меньше.
-
Сложность пространства — использование памяти операцией структуры данных должно быть как можно меньше.
Корректность — реализация структуры данных должна правильно реализовывать свой интерфейс.
Сложность времени — время выполнения или время выполнения операций структуры данных должно быть как можно меньше.
Сложность пространства — использование памяти операцией структуры данных должно быть как можно меньше.
Потребность в структуре данных
Поскольку приложения становятся сложными и богатыми данными, есть три общие проблемы, с которыми приложения сталкиваются в настоящее время.
-
Поиск данных — Рассмотрите инвентарь 1 миллиона (10 6 ) предметов магазина. Если приложение должно искать элемент, оно должно искать элемент в 1 миллионе (10 6 ) элементов каждый раз, замедляя поиск. По мере роста данных поиск будет замедляться.
-
Скорость процессора. Скорость процессора, хотя и очень высокая, ограничивается, если объем данных увеличивается до миллиарда записей.
-
Многократные запросы. Поскольку тысячи пользователей могут одновременно выполнять поиск данных на веб-сервере, даже быстрый сервер дает сбой при поиске данных.
Поиск данных — Рассмотрите инвентарь 1 миллиона (10 6 ) предметов магазина. Если приложение должно искать элемент, оно должно искать элемент в 1 миллионе (10 6 ) элементов каждый раз, замедляя поиск. По мере роста данных поиск будет замедляться.
Скорость процессора. Скорость процессора, хотя и очень высокая, ограничивается, если объем данных увеличивается до миллиарда записей.
Многократные запросы. Поскольку тысячи пользователей могут одновременно выполнять поиск данных на веб-сервере, даже быстрый сервер дает сбой при поиске данных.
Чтобы решить вышеупомянутые проблемы, структуры данных приходят на помощь. Данные могут быть организованы в структуру данных таким образом, что может не потребоваться поиск всех элементов, а требуемые данные можно искать практически мгновенно.
Случаи выполнения
Есть три случая, которые обычно используются для сравнительного сравнения времени выполнения различной структуры данных.
В худшем случае — это сценарий, в котором конкретная операция со структурой данных занимает максимальное время, которое она может занять. Если время наихудшего случая операции равно ƒ (n), то эта операция не займет больше времени, чем ƒ (n), где ƒ (n) представляет функцию от n.
Средний случай — это сценарий, отображающий среднее время выполнения операции структуры данных. Если на выполнение операции уходит ƒ (n) времени, то m операций займет время mƒ (n).
Наилучший случай — это сценарий, отображающий наименьшее возможное время выполнения операции структуры данных. Если на выполнение операции уходит ƒ (n) времени, то для фактической операции может потребоваться время как случайное число, которое будет максимальным как ƒ (n).
Данные — данные являются значениями или набором значений.
Элемент данных — элемент данных относится к одной единице значений.
Элементы группы — элементы данных, которые разделены на подэлементы, называются элементами группы.
Элементарные элементы — элементы данных, которые нельзя разделить, называются элементарными элементами.
Атрибут и объект. Объект — это объект, который содержит определенные атрибуты или свойства, которым могут быть назначены значения.
Entity Set — Объекты с похожими атрибутами образуют набор объектов .
Поле — Поле — это единая элементарная единица информации, представляющая атрибут объекта.
Запись — Запись — это коллекция значений полей данного объекта.
Файл — Файл представляет собой набор записей сущностей в данном наборе сущностей.