velikol.ru
1 2 3 4

1.Понятие данных. Неструктурированные данные.

Данные — непременный атрибут любой программы. Когда употребляют термин "программа",

подразумевают не только последовательность операторов некоторого языка программирования, но и набор различных информационных объектов (константы, переменные, массивы и т. д.), над которыми выполняются действия, описанные операторами программы. Такие объекты называют данными. В операторе

If а > b[i] Тhеn а:=0;

описаны действия, в которых "участвуют" переменные a, i, элемент массива b[i] и константа 0. Эти информационные объекты и являются данными.

Каждое данное относится к одному из конечного множества типов, допустимых для конкретной версии языка программирования. Программистам хорошо известны данные таких типов как Вуtе (байтовый), Integer (целый), Rеаl (вещественный), Вооlеаn (логический), Сhагасtег (символьный). Данное любого из этих типов логически неразделимо, поэтому такие данные называются неструктурированными (атомарными, примитивными).efримитивные данные} Иногда их называют скалярными, но это название нельзя считать бесспорным. Неструктурированные данные служат для построения структур данных; записей, массивов, деревьев, файлов и т. д.


2.Определение структуры данных. Физическая и логическая структуры данных.

Структурой данных называют совокупность (множес-тво) данных и отношений между ними. Один и тот же набор данных можно представить по разному. Пусть имеется пять данных типа Char: 'А', 'В', 'С', 'D', 'Е'. Этот набор можно представить как линейную последо-вательность элементов как сеть или дерево (см. рис. 1.1 )

Рис. 1.1. а — линейная последовательность; б — сеть; в — древовидная структура.

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

Структурой данных называется множество данных и отношений между данными. Отношения представляются в виде связей. Отношения в определении структуры имеют более важную роль, чем сами данные. Характер отношений определяет способ обработки структуры.

^ Логическая структура – абстрактная схема расположения данных, которые представляет себе программист.

Физическая структура – способ расположения структура в памяти ЭВМ. Обычно физическая и логическая схемы структуры не совпадают.

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

Двумерный массив имеет логическую структуру, представляемую в виде двумерной фигуры (матрицы).

A[1,1] A[1,2] A[1,3]

A[2,1] A[2,2] A[2,3]

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

A[1,1]

A[1,2]

A[1,3]

A[2,1]

A[2,2]

… ячейки ОП

^ 3.Способы формирования адреса данного: «база:смещение», «база/смещение/индекс»

Для хранения адресов процессор персонального компьютера используются 16-битовые регистры. Максимальное значение, которое может храниться в таком регистре, равно 216 - 1 = 65535, т. е. адресоваться могут только 64 Кбайта. Для решения проблемы адресации более чем 64 Кбайт с помощью 16-битового адреса процессор "разбивает" память на сегменты. Под сегментом понимается непрерывная область памяти размером не более 64 Кбайт.

Шина адреса микропроцессора имеет 20 линий, а значит физический адрес должен иметь 20 бит. Для формирования 20-битового адреса используется два компонента — сегмент адреса и смещение адреса, а сам адрес принято записывать парой этих значений, разделенных двоеточием:

segment: offset,

например, $0051:$ОЗА5 (здесь символ $ обозначает, что следующая за ним последовательность символов является шестнадцатеричным кодом некоторого числа). Значение "segment" хранится в специальном сегментном регистре микропроцессора, а смещение "offset" — помещается в один из 16-битовых регистров общего назначения (РОН). Абсолютный физический адрес образуется так;

1) значение сегмента адреса сдвигается на 4 бита влево с заполнением разрядов справа нулями, таким образом из 16-битового значения образуется 20-битовое;

2) к полученному 20-ти битовому значению прибавляется значение смещения адреса, а значение суммы передается на шину адреса.

Описанная схема адресации показана на рис. 2.3. Как известно, сдвиг двоичного числа на 4 бита влево (или, что то же самое, сдвиг шестнадцатиричного кода на одну шестнадцатиричную позицию влево) эквивалентен умножению этого числа на 16. Следовательно, физический адрес А определяется формулой

^ А = 16*segment + offset,

значение В = 16*segment называется базой, а способ адресации называется схемой, использующей базирование и смещение.

Для удобства адресации элементов структуры данных, расположенных через равные промежутки адресов, применяется схема, использующая базирование, смещение и индексирование. В этой схеме используется дополнительный РОН, который называется, индексным, а физический адрес определяется как

А = В + offset + index,




Рис. 2.4. Схема адресации, использующая базирование, смещение и индексирование

где index — содержимое индексного регистра. Данная схема иллюстрируется рис. 2.4. При такой схеме адрес любого элемента одномерного массива можно задать, установив с помощью базы и смещения адрес начального элемента массива, а с помощью индексного регистра — адрес требуемого элемента относительно начала массива. Последовательную адресацию элементов массива удобно осуществлять последовательным приращением содержимого индексного РОНа на одну и ту же величину, которая определяется количеством байтов, занимаемых одним элементом массива.


^ 4. Обобщенная схема ввода-вывода в ОП.

Укрупненно распределение оперативной памяти, выполняемое под управлением DOS, иллюстрируется рис. 8.1, на котором направление снизу вверх соответствует направлению от меньших адресов к большим.

При загрузке ЕХЁ-файла в память операционная система строит так называемый PSP — префикс программного сегмента. Эта область памяти содержит данные, которые служат для реализации управления программой, выполняемой DOS. Доступ к параметрам PSP возможен в режиме "только чтение".

Рис. 8.1. Карта распределения памяти при загрузке ЕХЕ-файла

За участком памяти PSP следует код программы. Далее в порядке, обратном тому, который указан в вызове Uses, располагаются подключаемые модули. На рис. 8.1 показан порядок расположения модулей, соответствующий Uses A, B, C. После области памяти, отводимой для явно подключаемых модулей, размещается модуль System, который не требует специального вызова в пользовательской Паскаль-программе. Модуль System поддерживает динамическое распределение памяти, процедуры ввода-вывода, обработку строк, целочисленную арифметику и арифметику с плавающей точкой; короче говоря, ему отводится ведущая роль при организации программ на Паскале,

За модулем System располагается сегмент данных. Его образуют в Паскале все типизированные константы, объявленные в блоке Const, и все переменные, объявленные в блоке Var уровня головной программы (глобальные переменные). Адрес начала сегмента данных фиксируется в сегментном регистре мнемоники DS, а значение этого адреса можно получить, используя переменную DSeg.

Далее за сегментом данных размещается сегмент стека. Назначение этого сегмента рассматривалось в п. 8.1. Адрес начала этого сегмента (базу) можно получить с помощью переменной Sseg, а приращение адресов (смещение относительно SSeg) определяется значением SPtr (stack pointer). В начале SPtr указывает на ячейку, находящуюся на максимальном удалении от начала стека; другими словами, в момент загрузки программы область памяти, расположенная в диапазоне адресов Sseg : 0000 – Sseg : SPtr, является той областью, в пределах которой будут размещаться элементы стека. При включении в стек очередного элемента указатель вершины SPtr уменьшается, то есть "перемещается" в сторону уменьшения адресов (стек "растет вниз"), при исключении элемента указатель SPtr перемещается к ячейке, имеющей больший, чем до исключения, адрес. Размер памяти, отводимой для стека, можно уменьшить или увеличить (с помощью опций компилятора), но при выполнении программы стек существует всегда, даже если программа его не использует.

Машинный код программы (с кодами используемых компонентов подключаемых модулей), данные и стек образуют в оперативной памяти так называемый загрузочный модуль программы.

Вслед за сегментом стека располагается участок памяти, выделяемый для загрузки оверлейных компонентов программы. При отсутствии оверлеев этот участок не создается.

Переменная HeapOrg указывает на начало Неар-области, в которой располагаются динамические переменные и структуры. Это стекоподобная структура, ее рост происходит от младших адресов к старшим. Текущее значение указателя, разделяющего занятый и свободный участки Неар-области, содержит переменная HearPtr. Этот указатель обслуживает динамические изменения состояния "кучи", передвигаясь вверх-вниз. Общий объем этой области памяти почти всегда превышает 64 Кбайт; обычно это самая большая по объему область памяти.

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

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


^ 5. Адресные пространства ПК

Под адресным пространством ЭВМ понимается множество возможных адресов, которые доступны программисту. Адресное пространство еще называют виртуальным адресным пространством, а элемент этого пространства — виртуальным адресом. Определение "виртуальный", относящееся к техническим средствам или данным, указывает на то, что некоторый элемент представляется прикладному программисту существующим, тогда как фактически в представляемом виде он отсутствует. Например, программист может писать программу в предположении, что основная память бесконечна, хотя на самом деле память ограничена. ЭВМ компенсирует недостаток памяти, используя специальный страничный механизм, организующий обмен блоков данных или программ между основной и внешней памятью.

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

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


^ 6. Основные правила представления неструктурированных данных

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

При рассмотрении представления данных в памяти следует знать следующие правила:

1) Число считается десятичным, если перед ним не записан символ $ или за ним не следует Н (в обоих случаях число считается шестнадцатиричным), за записью двоичного числа указывается символ В. Например, $10 или ЮН — это одно и то же шестнадцатиричное число, 10 — десятичное число, а 10В — двоичное.

2) Биты в байте нумеруются от 0 до 7, где бит с номером 0 является младшим битом.

3) Если в компьютере IBM PC неструктурированное данное занимает 2 или более байтов, то младший байт имеет самый меньший адрес. Например, 2 байта, в которых хранится значение $4АВ8 данного типа Word адресуются так: если адрес байта, содержащего В8, равен $20В1:$001б, то значение 4А будет храниться по адресу $20В1:$0017.

4) Байты, отводимые для хранения неструктурированного данного, смежны и занимают непрерывную область памяти.

5) Адресом данного, занимающего два и более байтов, считается адрес младшего байта.


^ 7. Литерные и логические данные в Паскале. Данные перечисляемого и интервального типов

Литерные данные описываются типом Char (Character). Данное типа Char занимает в памяти 1 байт. Код от 0 до 255, занесенный в этот байт, задает один из 256 возможных символов. Закрепление конкретных символов за кодами осуществляется с помощью кодовых таблиц. Для персональных компьютеров наиболее распространена ASCII-таблица (ASCII — American Standard Code for Information Interchange), которая имеется почти в каждой книге по программированию и потому здесь не приводится.Булевское данное (тип Boolean) может принимать одно из двух значений: True (истина) и False (ложь). Для хранения текущего значения такого данного отводится один байт.

Кроме стандартных типов данных, рассмотренных выше, Паскаль поддерживает два типа неструктурированных данных, определяемые самим пользователем. Тип, называемый перечисляемым, задается простым перечислением входящих в него различных значений, например,Type Metall = (Fe, Co, Na, Cu, Zn);и любое данное этого типа не может принимать никаких других значений, кроме указанных в скобках, Часто приходится сталкиваться с положением, когда присваивается значение некоторого типа, лежащее только внутри определенного интервала значений. Задав при описании интервального (ограниченного) типа две константы, определяющие границы этого интервала, мы тем самым определяем множество возможных значений такой переменной. Пример: Type Year = 1900 .. 1999; Letter = *A'.. 'Z';Данные перечисляемого и интервального типов применяются, в основном, для улучшения наглядности текста программы.

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

Структурой данных называют совокупность данных и отношений между ними.

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

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

В зависимости от отсутствия или наличия явно заданных связей между отдельными элементами данных следует различать несвязные структуры (векторы, массивы, записи) и связные, или связанные, структуры (связные списки).

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

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

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


^ 9. Основные операции над структурами данных. Запись названий этих операций на английском языке.

К основным операциям над структурами данных относятся следующие:

— формирование;

— просмотр;

— вставка (включение);

— добавление (дополнение);

— извлечение;

— удаление;

— сдвиг;

— изменение содержимого элемента;

— сортировка.

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

Формирование — это создание в памяти компьютера структуры данных, соответствующей ее логическому представлению. При этом различают фазы;

1) первоначального формирования (generation), когда данные размещаются в элементах структуры в порядке их поступления извне, и

2) перегруппирования (regrouping), например, создания древовидной структуры из записей, хранящихся в некоторой таблице; на этапе перегруппирования может быть применена сортировка.

Просмотр (scan, pass) — последовательное выполнение над элементами структуры одной и той же операции, например, сравнение их содержимого с некоторым заданным значением. Просмотр может выполняться с целью контроля содержимого элементов или для подсчета их числа.

Вставка (insertion) — это ввод нового данного в структуру данных. При вставке указываются элементы, между которыми в логической структуре расположится новый элемент; эти элементы определяют "точку вставки (включения)". Хотя на расположение точки вставки иногда могут быть наложены ограничения (например, в очередь включение возможно только со стороны "хвоста"), обычно, употребляя термин "вставка", подразумевают возможность включения нового элемента в любое место исходной структуры. При выполнении вставки в массивах осуществляется сдвиг некоторого количества элементов, чтобы освободить место для вставляемого элемента. Вставка в динамические структуры такого сдвига не требует — просто изменяются адреса связей без физического перемещения данных в памяти.

Под добавлением (store) понимают вставку нового элемента в логический конец корректируемой структуры. В сущности, формирование структуры — это последовательность добавлений элементов данных.

Извлечение (extraction) выполняется с целью передачи содержимого элемента структуры для дальнейшего использования, например, для печати этого содержимого.

Удаление (deletion) — это исключение некоторого элемента из структуры данных. При удалении в массивах удаляемый элемент либо помечают как удаленный (такое удаление без физического

уничтожения называется логическим удалением — logical deletion), либо осуществляют сдвиг некоторого количества элементов, при котором в ячейку с адресом удаляемого элемента заносится значение соседнего сдвигаемого элемента. В динамических структурах просто изменяются адреса связей без физического перемещения данных, а ячейка, в которой размещался удаляемый элемент, включается в список свободных ячеек.

Сдвиг (shift) — это перемещение некоторых элементов данных в одном из направлений: либо от логического начала структуры к ее логическому концу, либо наоборот. При сдвиге сохраняется порядок следования сдвигаемых элементов.

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

Сортировка (sorting) — это распределение элементов некоторого множества с целью их расположения в соответствии с некоторыми правилами. Разновидностью сортировки является упорядочение данных по возрастанию или убыванию значений некоторого признака сортировки. Часто сортировка выполняется как переупорядочение (reordering) ранее упорядоченной последовательности по другому признаку (полю). Сортировка массивов предполагает, что перестановки, приводящие элементы в порядок, должны выполняться "на том же месте". Сортировка динамической структуры предполагает изменение адресов связей.

При рассмотрении конкретной операции необходимо определить уровень абстрагирования. Если операция рассматривается в целом, без учета частных действий, приводящих к ее исполнению, то такая операция называется элементарной (elementary operation). Когда при употреблении термина "операция", принимается во внимание последовательность отдельных этапов, связанных с достижением ее результатов, то при таком подходе операция — это процесс (process). Например, просмотр воспринимается как элементарная операция, если мы принимаем во внимание только его цель. Когда же мы понимаем просмотр как последовательность "переходов" от одного элемента к другому и при этом учитываются действия, выполняемые над каждым элементом, тогда просмотр — это процесс.



следующая страница >>