Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 14. Данные и алгоритмы
Данные и алгоритмы
Программа состоит из алгоритма и обрабатываемых данных:
Программа = Данные + Алгоритм
Разработка программы включает параллельное проектирование этих двух ее компонентов. На каждом этапе проектирования сначала уточняется структура данных, а затем алгоритм, т.е. операции над данными.
Данные - это информация, представленная в форме, воспринимаемой устройствами ЭВМ.
Структура данных - определенным образом организованная совокупность данных. Структура данных состоит из элементов (полей) и определяется правилами, устанавливающими отношения (связи) между элементами. Элемент может состоять из более мелких элементов, т.е. сам может являться структурой данных. Таким образом, возможны иерархические (многоуровневые) структуры данных.
Иногда полем называют наименьший элемент, имеющий определенный смысл. Для этого используют также термины: реквизит, атрибут, терм, признак, скалярный элемент и др.
Пример. Структура данных "адрес человека" включает скалярные элементы: "фамилия", "имя", "отчество" и "домашний адрес", который сам является структурой данных и включает поля: "город", "улица", "дом", "квартира".
Первоначально применение ЭВМ ограничивалось в основном вычислительными задачами, и структуры данных были очень простыми - числа и числовые массивы. Основную трудность в создании программ представляло проектирование алгоритма.
В дальнейшем, сначала при разработке трансляторов и операционных систем, а затем и при создании прикладных программ, особенно систем с элементами искусственного интеллекта, экспертных систем, использовались все более сложные структуры данных и центр тяжести в разработке программ перемещался к данным.
Особенно наглядно это проявилось с появлением автоматизированных систем, построенных на основе концепции базы данных. База данных - это общая структура данных различных пакетов прикладных программ, составляющая основное ядро всей информационной системы.
Проектирование структуры данных является наиболее трудной и ответственной проблемой в создании сложных программ. Выбор структуры данных и способа их представления в памяти компьютера во многом (иногда почти однозначно) определяет структуру алгоритма. Овладение соответствующими методами стало обязательной частью образования не только системных, но и прикладных программистов.
В лекциях рассматриваются методы организации и обработки данных в оперативной памяти компьютера. Аналогичные методы лежат в основе проектирования баз данных во внешней памяти.
Уровни описания данных
В конечном счете, все данные в памяти компьютера хранятся в виде последовательности битов, но такое детальное представление трудно разработать сразу. Кроме того, его трудно корректировать при изменениях программы. Поэтому при проектировании структур данных, так же как и при разработке алгоритмов, используют основной метод борьбы со сложностью больших систем - иерархию, т. е. разбиение системы на уровни.
Часто, например, используют три уровня описания структуры данных: функциональный, логический и физический.
1. На функциональном уровне определяются необходимые для решения задачи операции над структурой данных и их свойства. Получается информационная модель предметной области решаемой задачи.
2. На логическом уровне структура данных разбивается на элементы, а операции над ней выражаются через операции над ее элементами.
3. На физическом уровне определяется способ представления данных и операций в выбранном языке программирования (в конечном итоге - в памяти компьютера). Достаточно выразить данные и операции решаемой задачи через базовые структуры и понятия языка программирования. Более детальное представление в машинном языке определяется транслятором автоматически. Программист имеет дело с абстрактной машиной, "понимающей" язык высокого уровня.
На функциональном и логическом уровнях имеют дело с абстрактными структурами данных, организованными в соответствии с решаемой задачей без детального учета особенностей компьютера (или языка программирования).
Абстрактная структура данных - это структура данных, рассматриваемая с точки зрения применяемых к ней операций без описания способа ее представления в памяти. Она близка к понятию абстрактного типа данных.
Абстрактный тип данных - тип данных, определяемый функционально: только через операции над объектами этого типа без описания способа представления их значений.
На физическом уровне имеют дело со структурами хранения, т. е. структурами данных, легко реализуемыми в языке программирования (или ЭВМ). В качестве базовых структур хранения в учебнике рассматриваются вектор, список и сеть.
Множество абстрактных структур данных бесконечно, т. к. для каждой задачи могут изобретаться свои структуры. В лекциях описаны наиболее распространенные в самых разных задачах абстрактные структуры данных: очередь, стек, дек, строка, граф, дерево, таблица, массив и множество. Они изучаются по единому плану: определение, применение, типовые операции, способы представления данных и реализации операций.
Абстрактную структуру данных можно реализовать разными способами на базе других более простых структур данных. Основными критериями выбора метода реализации являются:
Относительная важность этих критериев зависит от конкретной ситуации. Критерии часто противоречат друг другу, и разработчику приходится искать разумный компромисс между ними.
Методы хранения данных
Возможные методы хранения данных в конечном итоге определяются организацией памяти компьютера.
В большинстве современных компьютеров оперативная память построена по адресному принципу и представляет собой пронумерованную последовательность ячеек одинакового размера. Номер ячейки называется ее адресом, содержимое ячейки - машинным словом. Количество ячеек (объем, емкость памяти) обычно находится в пределах от 103 до 1010, а размер (длина) ячейки – от 8 до 64 бит.
Адресом данных, занимающих несколько соседних ячеек, считают адрес первой из них. В языках программирования адреса называют также указателями или ссылками.
Минимальным элементом хранения является бит - двоичная цифра, принимающая одно из двух значений, например, 0 или 1. Бит используется также как единица количества информации. Количество информации в битах равно минимальному числу двоичных цифр, необходимому для представления этой информации.
Машинное слово представляет собой команду или данные. Первоначально ЭВМ использовались преимущественно для обработки числовой информации. Ячейка памяти содержала одно число и имела длину от 16 до 64 бит. Это неудобно для представления символьной (текстовой) информации, т. к. код символа (байт) в зависимости от размера алфавита содержал от 5 до 8 бит, и в ячейке приходилось размещать несколько символов, что затрудняло доступ к каждому из них.
С повышением роли символьной обработки стали применять байтовую организацию памяти, когда ячейка содержит один байт, равный 8 бит, а для представления числа используются несколько соседних байтов. Байт также рассматривается как единица количества информации, равная одному символу текста.
Таким образом, оперативная память ЭВМ имеет линейную (одномерную) организацию, и для хранения многомерных массивов и других сложных структур данных их необходимо "линеаризовать".
Существуют три основные группы методов хранения структур данных.
1. Последовательное (сплошное) представление данных. Элементы структуры располагаются в памяти друг за другом без промежутков. Наиболее используемой структурой хранения является вектор.
2. Связанное (цепное) представление данных. Элементы структуры могут размещаться в памяти в произвольном порядке не обязательно подряд, причем каждый элемент содержит указатели (адреса) одного или нескольких других элементов, позволяющие отыскивать их в памяти. Основные структуры хранения - список и сеть.
3. Адресная арифметика. Элементы структуры располагаются в памяти в произвольном порядке с возможными промежутками, но существует определенная закономерность, позволяющая вычислять адрес элемента, например, в зависимости от его номера или другого параметра. Адресная арифметика может рассматриваться как обобщение последовательного и связанного представлений, в общем виде используется сравнительно редко.
Вектор - это набор элементов одинакового размера, расположенных в памяти подряд. Под набором в данном пособии понимается конечное множество. Вектор определяется базой (адресом первого элемента), длиной (количеством элементов) и размером элемента. По сути дела, вектор представляет собой одномерный массив. Главное достоинство вектора - прямой доступ к элементу по его порядковому номеру - индексу:
адрес(V[J]) = адрес(V[0])+d*J = адрес(V[1])+d*(J-1), (5.1)
где V[J] - элемент с индексом J, d - размер элемента (количество ячеек, занимаемых одним элементом); для простоты считаем, что d 1, целое.
Элементы вектора одинаково доступны и их можно обрабатывать в любом порядке.
Связанный список (в дальнейшем - список) - это последовательность элементов, каждый из которых, кроме других данных, содержит указатель (адрес) следующего элемента. Графически указатель изображают в виде стрелки, соединяющей элементы списка. На рис. 13.1 показан список, каждый элемент которого содержит один символ. Последний элемент списка содержит пустой указатель, равный нулю ().
Указатель
списка
Рис. 14.1. Список
Сеть (многосвязный список) - это набор элементов, каждый из которых может иметь несколько указателей (ссылок) на другие элементы. В однородной сети все элементы содержат одинаковое количество ссылок, в неоднородной - разное (рис. 14.2).
Рис. 14.2. Однородная (регулярная) сеть из трех элементов
Главное достоинство списков и сетей - простота добавления и удаления элементов; недостатки - дополнительная память для указателей и возможность только последовательного доступа к элементам (допускается движение только по ссылкам).
Программирование операций с сетями аналогично обработке списков.
Наиболее распространенным средством представления структур данных в языках программирования являются массивы. Одномерный массив (вектор), имеется в любом языке высокого уровня и легко реализуется на машинном языке. Поэтому в учебнике он рассматривается как базовая структура хранения, а многомерный массив - как абстрактная (т. е. производная) структура данных.
Современные языки включают понятие "структура" (C, PL/1 и др.) или "запись" (Pascal и др.). Структура (запись) - это совокупность именованных элементов - полей - одного или разных типов. Это понятие очень близко к понятию структуры данных и позволяет его формализовать.
Отсутствие в языке записей до некоторой степени можно компенсировать параллельными массивами. Совокупность (массив) из n однотипных записей заменяется параллельными массивами, количество которых равно количеству полей в записи. Каждый массив содержит n значений соответствующего поля всех записей.
Пример 14.1. Определение массива s из 100 записей (структур) с тремя полями sim, i, x:
struct
{ char sim; /* Символьное поле sim */
int i; /* Целочисленное поле i */
float x[10]; /* Поле x - массив из 10 вещественных чисел */
} s[100];
можно заменить определением трех параллельных массивов по 100 элементов:
char sim[100]; /* Поля sim всех 100 записей */
int i[100]; /* Поля i всех 100 записей */
float x[100][10]; /* Поля x всех 100 записей */
Тогда, например, поле sim 15-й записи
s[15].sim заменится на sim[15],
5-й элемент поля x 20-й записи
s[20].x[5] запишется как x[20][5],
но вся 40-я запись s[40] не имеет аналогичного обозначения в параллельных массивах.
Понятие структуры данных близко к понятию типа данных. Абстрактные структуры данных называют еще абстрактными типами данных. Абстрактные типы данных лежат в основе методики объектно-ориентированного программирования. Их изучение служит, в частности, базой для освоения этой современной технологии.
В языке C++ для объектно-ориентированного программирования понятие структуры обобщается и приближается к концепции абстрактного типа данных: элементами структуры могут быть не только данные, но и допустимые для них операции. Такая структура в C++ называется объектом, тип объектов - классом.
Контрольные вопросы и упражнения
1. Что такое данные, структура данных, поле?
2. Какие значения имеют указатели?
3. Опишите параллельные массивы для хранения массива структур
struct {
int n[20];
float d;
} m[100];
4. Опишите массив структур ST для замены параллельных массивов
int s[100], d[100][10];
float[100];
5. Напишите выражение, равное адресу 10-го элемента массива
int x[50];
145
0
0
0 0
. . .