Классификация структур данных

Введение. Цели и задачи дисциплины.

“ Целью дисциплины «Структуры и алгоритмы обработки данных» является изучение способов организации данных, разработки и анализа алгоритмов, взаимосвязи алгоритмов и структур данных. Знание этих структур и алгоритмов позволяет осуществлять выбор оптимальных способов решения задач при создании программного обеспечения различного назначения.

Задачи дисциплины:Сформировать базовые теоретические понятия, лежащие в основе процесса разработки алгоритмов и структур данных, знания об основных классах алгоритмов и используемых в них структурах данных, способах оценки алгоритмов и структур обработки данных, общих схемах решения задач на их основе. Научить программной реализации типовых алгоритмов и структур данных и их модификаций .

Требования к уровню освоения дисциплины

В результате изучения дисциплины студенты должны

Знать:основные методы разработки машинных алгоритмов и программ, структуры данных, используемые для представления типовых информационных объектов, основные задачи анализа алгоритмов; основные машинные алгоритмы и характеристики их сложности для типовых задач.

Уметь:разрабатывать алгоритмы, используя типовые схемы, методы и приемы построения алгоритмов, выбирая подходящие структуры данных для представления информационных объектов; доказывать корректность составленного алгоритма и оценивать основные характеристики его сложности;

реализовывать алгоритмы и используемые структуры данных средствами языков программирования высокого уровня

Иметь представление : о классификации алгоритмических задач по их сложности, о сводимости алгоритмических задач к известным задачам определенного класса сложности.

Классификация структур данных, концепция данных

Классификация структур данных

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

Базовые управляющие алгоритмические конструкции: следование, ветвление, цикл с предусловием.

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

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

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

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

По признаку изменчивости различают структуры статические и динамические.

Понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, т. е. константы, переменные, значения функций или выражения, характеризуются своими типами.

Информация по каждому типу однозначно определяет:

- структуру хранения данных указанного типа, т. е. выделение памяти, представление данных в ней и метод доступа к данным;

-множество допустимых значений, которые может иметь тот или иной объект описываемого типа:

- набор допустимых операций, которые применимы к объекту описываемого типа.

Различают простые типы данных и составные (структурированные).

К простым стандартным относят перечисленные ниже типы.

1) Целый.

2) Вещественный.

3) логический;

d) символьный;

4) ссылочный(указатель)

К пользовательским относят:

a) перечисляемый;

b) интервальный (диапазон).

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