Структуры и алгоритмы обработки данных

0. Введение
Структуры и алгоритмы обработки данных Лекции - 18 Практика - 8 Лаб. работы - 10 Зачет
0.1.Литература
1.  , Шаньгин и обработка структур данных в вычислительных системах: Учебное пособие для вузов - М. : Высшая Школа., 1987. 2.  Разумов данных в вычислительных системах - М.: Статистика,1978. 3.  Алгоритмы и структуры данных : Пер. с англ. - М. :Мир, 1989. 4.  Алгоритмы + структуры данных = программы : Пер. с англ. - М.: Мир, 1985. 5.  Берзтисс данных : Пер. с англ. - М.: Статистика, 1974. 6.  , Введение в структуры данных : Пер. с англ..- М.: Машиностроение, 1982. 7.  Искусство программирования для ЭВМ. Том 1 : Основные алгоритмы. : Пер. с англ. - М.: Мир, 1976. 8.  Искусство программирования для ЭВМ. Том 3 : Сортировка и поиск : Пер. с англ. - М.: Мир, 1978.
0.2. Программное обеспечение ЭВМ
Это совокупность программ, предназначенных как для поддержания должного функционирования ЭВМ, так и для выполнения ею полезных функциональных задач некоторой прикладной области. Когда употребляют термин "программа ", подразумевают не только последовательность операторов некоторого языка программирования, но и набор различных информационных объектов, над которыми выполняют те или иные действия операторы программы. Такие информационные объекты программы называют данными. Данные - представление фактов и идей в формализованном виде для передачи или обработки их при помощи некоторого процесса (алгоритма). Данные - непременный атрибут любой программы. Ими могут быть отдельные биты, последовательности независимых битов, числа в разных формах представления ( с фиксированной или плавающей точкой, обычной или удвоенной точностью и т. д. ), байты и группы независимых байтов, представляющие символы в различных системах кодирования, массивы чисел, информация хранимая в памяти вычислительной машины в форме связанных списков, а также информация на устройствах внешней памяти, организованная в виде отдельных файлов и систем взаимосвязанных файлов. Данные имеют разный уровень сложности, или организованности, начиная с простейшего информационного элемента - бита и кончая файлами и системами файлов. Характер организованности, множество допустимых значений и набор допустимых операций над данными представляют их структуру. Структура данного - общее свойство любого информационного объекта, с которым имеет дело та или иная программа. Структуры данных – необходимые компоненты любой программы или программного комплекса. Поэтому знание теории структур данных и, в частности, методов представления данных на логическом и машинном уровнях, а также допустимых операций над различными структурами необходимо для глубокого изучения и уяснения таких разделов, как автоматизированные системы управления компиляторы языков программирования, операционные системы, а также системы программного имитационного моделирования, управления базами данных, искусственного интеллекта и т. д. В результате изучения курса будут известны основные типы структур данных – табличные, списковые, древовидные, сетевые, файловые; основные алгоритмы обработки структур - пополнение, удаление, модификация, прохождение, поиск, упорядочивание; будут получены навыки разработки алгоритмов обработки данных. Задача курса создать теоретическую базу для последующих дисциплин: -  Системное программное обеспечение, -  Базы данных. -  Базы знаний и экспертные системы. -  Обработка экспериментальных данных на ЭВМ.
1. Структуры данных
1.1 Уровни структур данных
Применяются три уровня структур данных: 1.  логический, 2.  физический, 3.  содержательный. Логический или абстрактный (логические структуры). На этом уровне структура данных считается машинно независимым логическим понятием, и выделяются следующие задачи: определение массивов данных как объектов исследования, выделение состава массива:, определение структуры данных по заданным требованиям, разработка количественных методов оценки эффективности различных видов структур данных. Физический уровень ( физическая структура). На этом уровне рассматриваются память ЭВМ и представление в ней значений (ячейки, разряды ячеек, их адреса и взаимное расположение значений.), т. е. отображение данных в памяти ЭВМ. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той физической среды, в которой она должна быть отражена. На содержательном уровне структур данных исследуются конкретные объекты обработки, их свойства и отношения между объектами. На этом уровне важны не только значения, но и смысл данных.
1.2 Классификация структур данных
С точки зрения архитектуры выделяются два структурных образования данных. Линейные структуры - структуры, в которых связи между значениями элементами. В зависимости от связей различают: 1.  Несвязные (векторы, массивы, строки, стеки, очереди). 2.  Связные (списки). В зависимости от постоянства различают: 1.  Изменяющиеся. 2.  Статические.
1.3. Информация и ее представление в памяти ЭВМ.
Базовой единицей информации является бит, который может принимать одно из двух взаимоисключающих значений. Для представления двух возможных состояний некоторого бита используются двоичные цифры - нуль и единица [ слово " бит " (английское bit ) есть сокращение от английских слов " двоичная цифра " ( binary digit ) ]. Более крупной единицей информации является байт. Группы смежных битов объединяются в поле. Поле, состоящее из 8 битов называется байтом, причем левый двоичный разряд имеет наибольший вес и считается старшим разрядом, а правый разряд - наименьший вес (младшим разрядом). Нумерация разрядов байтов осуществляется справа налево и начинается с нуля. Кроме 8 информационных битов байт обычно содержит дополнительный контрольный бит четности, невидимый для программиста. Группа смежных байтов образуют поле байтов, характеризующееся длиной поля - числом входящих в него байтов и адресом поля - адресом старшего, самого левого, байта в поле, т. е. байта с наименьшим адресом. В общем случае поле байтов может иметь произвольную длину и адрес. Для некоторых частных видов полей имеются специальные названия: 1.  Полуслово ( для поля, имеющего длину 2 байта). 2.  Слово (4 байта). 3.  Двойное слово ( 8 байт ). Графическое соотношение между битом, байтом, полусловом, словом, двойным словом показано на рис.1. Поле байтов длиной 1024 байт имеет специальное обозначение 1Кбайт. Поле длиной 1024х1024 байт обозначается через 1Мбайт. Поле длиной 1024х1024х1024 через 1Гбайт.
1.3. Адресное пространство. Адресация памяти. Базирование, смещение, индексирование
В наборе команд любой ЭВМ имеются адресные команды, т. е. команды, обеспечивающие доступ в основную память для чтения или записи данных или передачу управления на различные участки программы. Уяснение принципов адресации данных в основной памяти имеет важное значение не только для понимания функционирования вычислительной системы, но и для организации требуемых структур данных и построение рациональных алгоритмов доступа к этим структурам. Введем понятия адресного пространства вычислительной системы и реального адресного пространства. Под адресным пространством вычислительной системы понимается возможных адресов, определяемое адресной структурой, или максимальной длиной адреса. Адресное пространство называют также виртуальным адресным пространством, а элемент этого адресного пространства - виртуальным адресом. Реальное адресное пространство вычислительной системы - множество адресов, определяемое реальной основной памятью данной вычислительной системы. Элемент реального адресного пространства – реальный адрес. Чаще всего реальное адресное пространство - лишь часть адресного пространства вычислительной системы. Логическим адресным пространством называется множество адресов команд и данных в той или иной программе. Следовательно, понятие логического адресного пространства относится к программе и поэтому иногда называется адресным пространством программы. Логическое адресное пространство может быть частью реального адресного пространства или выходить за его пределы. При загрузке, редактировании или в процессе выполнения программы логические адреса преобразуются в реальные адреса основной памяти. Наиболее популярны следующие варианты логического адресного пространства: 1.  Плоское - ( иногда говорят линейное) логическое пространство. Состоит из массива байтов, не имеющего определенной структуры. Трансляция адреса в этом случае не требуется, поскольку логический адрес совпадает с физическим. 2.  Сегментированное - состоит из нескольких или большого числа сегментов, каждый из которых содержит переменное число байтов 3.  Страничное - состоит из большого числа страниц, каждая из которых включает фиксированное число байтов. Логический адрес состоит из номера (идентификатора ) страницы и смещения внутри страницы. Трансляцию осуществляет блок управления памятью. 4.  Сегментно-страничное. Состоит из сегментов, которые в свою очередь состоят из страниц. Логический адрес состоит из идентификатора сегмента и смещения внутри сегмента. БУП производит трансляцию логического адреса в номер страницы и смещение в ней, которые затем транслируются в физический адрес. Процессор автоматически транслирует логические адреса в физические, выдаваемые затем на системную шину. Операционная система 80386 может изменять представление прикладной программы о ее логическом адресном пространстве. Например, она может определить логическое адресное пространство так, как это делается во многих архитектурах, т. е. как простой массив из 2 в 32 степени байт. С другой стороны, она может организовать это пространство, как набор сегментов переменной длины, количество которых будет зависеть от ее представления о логической памяти. Процессор предоставляет ОС возможность определить адресное пространство в виде одного или многих сегментов. Сегменты являются логическими единицами, хорошо приспособленными под программные структуры, имеющие по своей сути переменную длину. Сегмент в 80386 может иметь любой размер - от 1 байта до 4 Гбайт. В случае реализации сегментного механизма, ОС для каждого сегмента обязана поддерживать заданный архитектурой дескриптор, содержащий описание сегмента. Это описание включает 232 - битный адрес и длину ( предел ) сегмента, а также информацию о защите, предотвращающую неправильное использование сегмента. На Рис. 2 представлена упрощенная структура дескриптора. В ЭВМ используется схема адресации основной памяти с помощью базирования и смещения или базирования, смещения и индексирования. В первом случае адрес операнда в основной памяти вычисляется как сумма содержимого определенного общего регистра, номер которого указывается в одном из полей команды и 32 разрядного смещения, также записанного в команде (см. Рис. 3).Регистр, используемый для формирования адреса операнда, называется базовым, а его содержимое - базой.
1.4. Способы адресации
Процессор 80386 обеспечивает регистровую и непосредственную адресацию операндов, содержащихся, соответственно, в регистрах и командах. Эффективный адрес задает смещение ( расстояние ) от начала соответствующего сегмента. Адрес 0 есть адрес первого байта в сегменте, адрес 1 - второго байта и т. д. независимо от физического начального или базового адреса сегмента. Процессор вычисляет смещение логического адреса по следующей формуле: СМЕЩЕНИЕ = БАЗА+(ИНДЕКС * МАСШТАБ)+ОТКЛОНЕНИЕ Для вычисления смещения могут быть использованы все переменные - база, индекс и отклонение. Переменные база и индекс хранятся в общих регистрах, отклонение содержится в команде. Для хранения базы или индекса может быть использован любой общий регистр. Величина индекса может быть умножена на масштабный коэффициент (1,2,4,8) что дает возможность ссылки на элементы массива или записи соответствующей длины. Отклонение может иметь разрядность 8 или 32 бита и интерпретируется процессором как величина со знаком в дополнительном коде. Прямая адресация. Это простейший режим адресации ( он называется также абсолютной адресацией ), т. к. эффективный адрес содержится в самой команде. Местонахождение операнда задается смещением в текущем сегменте, которое следует считать константой. При программировании прямая адресация применяется редко и только для обращения к ячейкам памяти с фиксированным адресом. Базовая адресация. В этом режиме эффективный адрес находится в любом регистре общего назначения. Этот режим относится к косвенной регистровой адресации. Базовая адресация со смещением. Этот режим, называемый еще " база + смещение" предназначен для обращения к соседним ячейкам памяти относительно эффективного адреса в базовом регистре. Он очень удобен для доступа к элементам структур данных и переменных, находящимся в стеке. Смещения считаются целыми двоичными числами со знаком. Их длина может составлять 8, 16, и 32 бита* при необходимости короткие смещения расширяются со знаком. Индексная адресация со смещением. Индексирование реализуется, как и базовая адресация, посредством использования содержимого регистра общего назначения в качестве компоненты эффективного адреса. Индексная адресация наиболее удобна при работе с массивами : прямой адрес определяет начало массива, а индекс – элемент массива. В общем, индексная адресация со смещением очень похожа на базовую адресацию со смещением. Однако индексирование обладает интересной и удобной возможностью, которой нет у базовой адресации. В процессоре 80386 легко производятся операции с массивами, элементы которых имеют размер 1, 2, 4, и 8 байт. Если индексной переменной служит i, то для получения адреса i-го элемента массива, значение i необходимо умножить на размер элемента массива. Например, для массива V двойных слов адрес третьего элемента V[3] равен V+4*3=V+12 . Процессор может автоматически произвести коррекцию индекса для получения адреса памяти. Такая коррекция называется масштабированием. Базовая индексная адресация со смещением. Это наиболее сложный режим адресации. Он применяется для доступа к структурам данных в стеке и к массивам, базовые адреса которых находятся в регистре. Стековая адресация. Во всех современных процессорах аппаратно поддерживается стек, т. е. область оперативной памяти, предназначенная для временного хранения любой информации.