Алгоритмы и структуры данных 62

Конспект лекций по курсу

«АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»

Автор: доцент Шустова Л.И.

2. Структуры данных

   1. Уровни представления информации

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

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

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

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

   1. В иерархическойструктуре можно с той или иной степенью точности выделить отношения подчинения одной части или элемента информации другой.

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

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

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

3. Конкретныеструктуры информации – это способы представления соответствующих абстрактных структур в памяти ЭВМ.

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

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

В дальнейшем будут рассматриваться абстрактные и конкретные структуры данных.