Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

1.1. Основные опредепения

Под программным обеспечением ЭВМ понимают совокуп— ность программ, предназначенных как для поддержания должно- го функционирования ЭВМ, так и для выполнения ею полезных функциональных задач некоторой прикладной области. Когда употребляют термин «программа», подразумевают не только по- следовательность операторов некоторого языка программирова— ния, но и набор различных информационных объектов, над кото- рыми выполняют те или иные действия операторы программы. Такие информационные объекты программы называют данны ми.

Существует по крайней мере несколько не противоречащих друг другу определений того, что такое данные. В соответствии с международным стандартом ISO, в наиболее общем виде данные
— это представлений фактов, понятий, инструкций, идей или ка- кой—либо другой информации в формализованном виде, прием- лемом для обработки, интерпретации, общения или передачи как человеком, так и техническими средствами, при помощи некото— рых процессов или алгоритмов.
Данные — непременный атрибут любой программы. Ими могут быть отдельные биты, последовательности независимых битов, числа в разных формах представления (с фиксированной или плавающей точкой, обычной или удвоенной точностью и т.д.), байты и группы независимых байтов, представляющие сим- волы в различных системах кодирования, массивы чисел, инфор- мация хранимая в памяти вычислительной машины в форме свя- занных списков, а также информация на устройствах внешней памяти, организованная в виде отдельных файлов и систем взаи- мосвязанных файлов. Перечисленные примеры иллюстрируют разный уровень сложности, или организованности данных. Ха- рактер этой организованности и является одним из воплощений понятия «структура данны.г».
Термин «структуры данных» может употребляться по крайней мере в двух разных значениях. Во—первых, структура данных — это логическая или математическая модель организа- ции данных. Фактически, структура данных может рассматри-
ваться как представление именно этих данных в памяти ЭВМ ( физическая структура), н является общим свойством любого информационного объекта, с которым имеет дело какая-либо программа.
Во-вторых, структура данных — это собственно реализация логического понятия данных, объект (больший или меньший) в программе и в памяти ЭВМ. Это может быть отдельная перемен- ная, массив или более сложный программный объект, например, список, дерево и т.п. Важно помнить, что любая структура дан- ных размещается в памяти ЭВМ (в первую очередь, в оператив- ной памяти), занимает некоторое, возможно весьма большое, ко- личество ячеек этой памяти и характеризуется начальным адре- сом своего размещения. Для описания этой ситуации использует- ся понятие «месте в п‹zмлтн».
Очень часто структуры данных рассматриваются во взаимо- связи с алгоритмами обработки данных. Одно из распространён- ных определений алгорнтма однозначно определённая конеч- ная последовательность команд (или инструкций, предписаний), задающая порядок выполнения операций для решения задачи. Алгоритмы обработки данных и их структур можно разделить на две группы — алгоритмы обработки собственно данных, напри- мер, подавление шумов, преобразование Фурье, цифровая фильт- рация и т.п. Это именно те алгоритмы, для реализации которых и создаются программы, поэтому такие алгоритмы можно назвать і›сні›sныжи. Вторая группа — это алгоритмы обработки именно структур данных, те, которые уже были перечислены во введении

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

2. 
   Уровни структур данных
   

Структуры данных могут рассматриваться на разных уров- нях. Применяются три уровня структур данных:

1. 
   содержательный,
   
2. 
   логический,
   

9

3. 
   физический.
   

На содержательном уровне структур данных исследуются конкретные объекты обработки, их свойства и отношения между объектами. На этом уровне важны не только значения, но и



На логическом или абстрактном (логические структуры) уровне структура данных считается машинно-независимым логи- ческим понятием, и выделяются следующие задачи: определение массивов данных как объектов исследования, выделение состава массива, определение структуры данных по заданным требовани- ям, разработка количественных методов оценки эффективности
]ЭІ1ЗЛИЧНЫХ ВИДОВ СТ]Э KT ЈЭ ДІІННЫХ.