Уровни описания данных

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

Часто, например, используют три уровня описания структуры данных: функциональный, логический и физический.

1. На функциональном уровне определяются необходимые для решения задачи операции над структурой данных и их свойства. Получается информационная модель предметной области решаемой задачи.

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

3. На физическом уровне определяется способ представления данных и операций в выбранном языке программирования (в конечном итоге - в памяти компьютера). Достаточно выразить данные и операции решаемой задачи через базовые структуры и понятия языка программирования. Более детальное представление в машинном языке определяется транслятором автоматически. Программист имеет дело с абстрактной машиной, "понимающей" язык высокого уровня.

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

Абстрактная структура данных - это структура данных, рассматриваемая с точки зрения применяемых к ней операций без описания способа ее представления в памяти. Она близка к понятию абстрактного типа данных.

Абстрактный тип данных - тип данных, определяемый функционально: только через операции над объектами этого типа без описания способа представления их значений.

На физическом уровне имеют дело со структурами хранения, т. е. структурами данных, легко реализуемыми в языке программирования (или ЭВМ). В качестве базовых структур хранения в учебнике рассматриваются вектор, список и сеть.

Множество абстрактных структур данных бесконечно, т. к. для каждой задачи могут изобретаться свои структуры. В лекциях описаны наиболее распространенные в самых разных задачах абстрактные структуры данных: очередь, стек, дек, строка, граф, дерево, таблица, массив и множество. Они изучаются по единому плану: определение, применение, типовые операции, способы представления данных и реализации операций.

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

1) возможность реализации требуемых операций над данными;

2) время выполнения операций;

3) требуемая память;

4) простота программирования.

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