Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
«Мы произвели пескоструйную очистку бетонных и гранитных поверхностей мостов общей площадью более 35 тысяч квадратных метров», — рассказали в ГБУ «Гор...полностью>>
'Программа'
Thapovan Heritage Home 3* (Тапован Херитадж Хом) находится в 18 км от Тривандрума, от аэропорта на пляже Nellikunnu. Большая часть номеров отеля наход...полностью>>
'Документ'
Теперь эту гипотезу надо доказать! Открыл и доказал эту теорему французский ученый математик Франсуа Виет. Домашним заданием вам будет законспектирова...полностью>>
'Анкета'
Название компании на русском или белорусском языке (возможно указать через наклонную черту вариант написания названия на иностранном языке). Название ...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

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

Типы числовых данных Алгола — integer (целое число), real (действительное) — различаются диапазонами изменения, внутренними представлениями и применяемыми командами процессора ЭВМ (соответственно арифметика с фиксированной и плавающей точкой). Нечисловые данные представлены типом boolean — логические, имеющие диапазон значений {true, false}.

Позже появившиеся ЯП (СП) Кобол, ПЛ/1, Паскаль предусматривают новые типы данных:

  • символьные (цифры, буквы, знаки препинания и пр.);

  • числовые символьные для вывода;

  • числовые двоичные для вычислений;

  • числовые десятичные (цифры 0—9) для вывода и вычислений.

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

Уместно привести пример представления числовой информации в различных перечисленных формах. Пусть задано число 13510 = 2078 = 87|16= 1000001112:

  • внутренняя стандартная форма — тип binary — представления для обработки в двоичной арифметике сохраняется (1000001112). Объем — 1 байт, 8 двоичных разрядов;

  • внутренняя форма двоично-десятичного — тип decimal —представления: каждый разряд десятичного числа представляется двоично-десятичной (4 бита) комбинацией. Представление 135 есть 001 011 1012. Объем — 2,5 байта, 12 двоичных разрядов;

  • символьное представление (для вывода)  — тип alphabetic — каждый разряд представляется байтом в соответствии с кодом ASCII.

Представление 135 есть 00110001 00110011 001101012. Объем — 3 байта.

Появление СУБД и СП для разработки ИС приводит к появлению новых типов данных:

Дата и время.

Бинарные (BLOB — Binary Large Object) и текстовые объекты без внутренней структуры (интерпретация возлагается на прикладные программы).

Понятие типа данных ассоциируется также с допустимыми значениями переменной и операциями над ними, например, данные типа время (чч:мм:сс) или дата (гт/мм/дд) предполагают определенные диапазоны значений каждого из разрядов, а также машинные или эмулируемые операции (сложение/вычитание дат и/или моментов времени). Основной причиной «проблемы 2000 года» являлась не столько двухразрядная запись года в базах данных, сколько встроенные в огромное количество программ (часто недокументированных) операции над данными типа date —гт/мм/дд.

Структуры данных. В языке Алгол определены два типа структур — элементарные данные и массивы (векторы, матрицы, тензоры, состоящие из арифметических или логических переменных (рис. 1.2, а, б, в)). Основным нововведением, появившимся первоначально в Коболе (затем ПЛ/1, Паскаль и пр.), являются агрегаты данных (структуры, записи), представляющие собой именованные комплексы переменных разного типа, описывающих некоторый объект или образующих некоторый достаточно сложный документ (рис. 1.2, г).

Термин запись подразумевает наличие множества аналогичных по структуре агрегатов, образующих файл (картотеку), содержащих данные по совокупности однородных объектов, элементы данных образуют поля, среди которых выделяются элементарные и групповые (агрегатные). В языках ПЛ/1, Паскаль появляются массивы записей (рис. 1.2, д).

С появление СУБД и ЛИПС возникают новые разновидности структур:

  • множественные поля данных (рис. 1.2, е);

  • периодические групповые поля (рис. 1.2, ж);

Текстовые объекты (документы), имеющие иерархическую структуру (документ, сегмент, предложение, слово)   — рис. 1.2,

Рис. 1.2. Структуры данных:

а. - одномерный массив (символическое изображение); б — графическое изображение; в — двумерный массив (матрица); г — запись (структура, агрегат данных); д - массив в записи (множественное поле записи); е — массив агрегатов; ж — массив агрегатов в записи (повторяющаяся группа); з — документ библиографической БД IN IS [10]

Рис. 1.2. Структуры данных (окончание)

Некоторые обобщенные представления о структурах данных

Линейные структуры. К линейным структурам относятся массивы и последовательности, таблицы.

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

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

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

Последовательность, так же как и массив, представляет собой совокупность однотипных элементов. Однако число элементов до размещения неизвестно. И, хотя каждая конкретная последовательность имеет конечную длину, до начала обработки (и соответственно размещения) необходимо считать длину последовательности бесконечной. Принципиальность такого предположения выражается в том, что необходимо предусматривать специальную процедуру использования памяти (выделения/освобождения) и, возможно, алгоритм обработки последовательности по частям. Важность рассмотрения такого типа данных обусловлена тем, что именно он превалирует в операциях ввода-вывода с устройствами внешней памяти. Именно последовательный доступ позволяет организовать «потоковые» операции: однородность позволяет рассматривать пересылаемые данные как непрерывный поток. Поток не может быть прерван по контекстно определяемому условию, например, при пересылке текста — по значению кода «перевод строки», и это не заставляет программу анализировать значение каждого очередного элемента. И, кроме того, последовательный доступ — это простота управления памятью и устройством ввода-вывода.

Разновидностями последовательностей являются также не рассматриваемые здесь очереди и стеки, которые отличаются тем, что для них устанавливаются особые схемы добавления (размещения в памяти) новых элементов и их выборки. Для очереди порядок размещения/выборки определяется правилом «первым размещен — первым выбран», для стека — «первым размещен — последним выбран». Кроме того, выборка элемента влечет его удаление из последовательности.

Таблица — это последовательности, обычно представляемые строками — совокупностями разнотипных элементов. Или, иначе, таблица — это множество записей, каждая из которых представляет набор поименованных полей.

Однако с точки зрения размещения элементов таблица может быть представлена как одномерный массив (или, в случае БД, последовательность) с однородными композиционными элементами, каждый из которых представляет собой совокупность разнотипных элементов. Именно это позволяет свести ввод-вывод таких типов структур к последовательным элементарным операциям.

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

Нелинейные структуры.

Примерами нелинейных структур являются списки, деревья и сети.

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

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

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

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

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

Деревья. Дерево (рис. 1.3) представляет собой иерархию элементов, называемых узлами. На самом верхнем уровне иерархии имеется только один узел — корень. Каждый узел, кроме корня, связан с одним узлом на более высоком уровне, называемым исходным узлом для данного узла. Каждый элемент имеет только один исходный узел. Каждый элемент может быть связан с одним или несколькими элементами на более низком Уровне, которые называются порожденными. Элементы, расположенные в конце ветви, т. е. не имеющие порожденных, называются листьями.

Рис. 1.3. Пример структуры типа дерево

Существует несколько способов представления структуры дерева. Например, дерево может быть определено как иерархия узлов с попарными связями, в которой:

  • самый верхний уровень иерархии имеет один узел, называемый корнем;

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

Такое определение в части организации связей совпадает со списком, и, в частности, список представляет вырожденный случай дерева, в котором каждая вершина имеет не более одного поддерева.

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

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

Выделяют три метода обхода: сверху вниз, слева направо, снизу вверх.

Регулярность обхода дерева может быть связана с упорядоченными деревьями, к которым относятся сбалансированные (рис. 1.4) и двоичные деревья (рис. 1.5).

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

Двоичные деревья — это особая категория сбалансированных древовидных структур, в которой допускается не более двух ветвей для одного узла. На рис. 1.5 показано несбалансированное двоичное дерево.

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

Если бы были показаны оба родителя, то это была бы более сложная структура.

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

Рис. 1.6. Пример сетевых структур

Так же как и в случае древовидных структур, сетевую структуру можно описать с помощью исходных и порожденных элементов. Удобно представлять ее так, чтобы порожденные элементы располагались ниже исходных. При рассмотрении некоторых сетевых структур естественно говорить об уровнях, так же как и в случае древовидных структур.

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

1.2. Управление данными. Файловые системы

Организация данных на машинных носителях (предварительные соображения)

Накопители на магнитных носителях, файлы, циклы обработки.

Накопители данного типа являются основной средой хранения информации в ЭВМ и разделяются на магнитные ленты

(НМЛ) и магнитные диски (НМД). Появлявшиеся в различное время магнитные барабаны и магнитные карты особого распространения не получили. В настоящее время устоялось следующее представление: НМД используются для оперативного (во время решения задач) хранения информации, НМЛ — для резервного (архивного) хранения (стримеры).

Файл (набор данных на внешнем носителе) рассматривается как совокупность записей одинаковой структуры, каждая из которых представляет собой набор (агрегат) разнородных данных (в языках программирования PL/1, Pascal, Си за подобными объектами так и закрепилось название структура structure).

Понятие файла появляется впервые в операционной системе OS/360 фирмы IBM, причем в ранних версиях системы «настоящим файлом» считался только перфокарточный массив (file = = картотека), данные на МД и МЛ обозначались как DS (Data Set — набор данных). В последующих ОС (RSX, UNIX, MS-DOS) файлами становятся именованные организованные наборы данных на любых носителях и устройствах, за сохранность и обновляемость которых (а также передачу в прикладные программы/из прикладных программ) и несет ответственность ОС ЭВМ.

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

В системе OS/360 основную роль играли два типа файлов:

  • символьные (исходные программы или данные);

  • двоичные (программы в машинных кодах).

В современных системах активно используется значительно большее разнообразие файлов, из которых мы перечислим наиболее типичные (табл. 1.8):

текстовые файлы — обобщенное название для простых и размеченных текстов, ASCII-файлов и других наборов данных символьной информации, которые интерпретируются и обрабатываются текстовыми редакторами, процессорами, анализаторами (Lexicon, Word, TEC, анализаторы SGML, HTML);

текст без разметки (планарный)  —  файл, содержащий только отображаемые (воспроизводимые на всех печатающих устройствах и терминалах) символы кода ASCII, а так

Таблица 1.8. Основные типы файлов, обрабатываемых в ПЭВМ 

Тип, расширение имени

Вид информации, содержащейся в файле

exe, com

Программа, готовая к исполнению

bat

Текстовый командный файл

sys

Системный файл

ovl, ovr

Оверлейный файл

txt, 1st

Текстовый файл в формате DOS

doc

Документ (чаще всего в формате WinWord)

rtf

Размеченный текстовый файл (Rich Text Format)

dot

Файл формата документа (Document Type)

pdf

Формат документа Adobe Acrobat

wri

Документ редактора Write для Windows;

bak, old

Старая копия файла, создаваемая перед его изменением

arj, rar, zip, lzh, arc

Архивные файлы

bas

Текст программы на языке Basic

pas

Текст программы на языке Pascal

с

Текст программы на ЯП Си

bmp, pcx, gif, tif, jpg

Графические файлы

dbf

Файлы базы данных формата DBase, Foxpro, Cliper

xls

Электронные таблицы EXCEL

lib, dll

Файлы библиотек

hip

Файл справки (подсказки, помощи)

mnu

Файл меню

wav, mid, mp3, mod

Звуковые файлы

avi, mov, mpg

Файлы видеоклипов

же простейшие управляющие символы: возврат каретки (cr); перевод строки (lf); символ табуляции (tab), иногда — новая страница (lf);

текст с разметкой — планарный файл, содержащий бинарную, или символьную, разметку, управляющую отображением информации (программно и/или аппаратурно);

ASCII-файл — содержит только отображаемые коды кодовой  таблицы  ASCII   (латиница  и  служебные  символы), обычно применяется для хранения документов с символьной разметкой (RTF, SGML, HTML);

табличный  файл  —  содержит  форматированные  данные (символьные, численные и  др.), образующие  строки  и столбцы таблиц, создаваемых и обрабатываемых табличными СУБД (FoxPro, Clipper, MS Access) и/или процессорами (SuperCalc, MS Excell и др.);

графический файл — бинарный файл, содержащий графическую информацию. Форматы: tif (Tagged Image File), BMP
(Bit-Mapped Picture), а также ряд других — PCX, pic и т. д.;

мулыпимедиафайлы — бинарные, содержащие оцифрованную аудио- (типы wav или MIDI-Sequencer), видео- (фор­
мат MPEG) или смешанную информацию.

Цикл обработки файла (например, внесение изменений в счета клиентов) включает следующие операции:

открытие файла — занятие устройства, на котором файл размещен (например, МД), создание в ОП управляющего
блока,
в котором записывается справка о состоянии файла и буфера (или набора буферов — буферного пула) для хранения текущей, обрабатываемой записи файла;

организация цикла, управляемого файлом (заканчивается по исчерпании   записей   файла   —   наступлении   состояния EOF — end-of-file), после чего выполняется некоторый оператор, обычно завершения обработки. Цикл должен содержать команду типа read, get (ввод записи), put, write (вывод записи) либо rewrite (обновить запись). Команда read может являться функциональным аналогом заголовка цикла;

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

Адресация, имена, спецификация данных в ОС.



Похожие документы:

  1. V. Оценочные средства 19 Вопросы к экзамену 20

    Вопросы к экзамену
    ... :-608 с., ил. Голицына О.Л., Максимов Н.В., Попов И.И., Базы данных: Учеб. пособие, − М.:ФОРУМ: ... Н.В., Партыка Т.Л., Попов И.И. Системы управления базами данных: Учеб. пособие. М.: ФОРУМ: ИНФРА-М, 2005. - 350 с. Максимов Н.В., Партыка Т.Л., Попов ...
  2. Рабочая программа дисциплины информационные системы специальность

    Рабочая программа
    ... Информационные системы [Text] : учеб. пособие / Голицына, О.Л., Максимов, Н.В., Попов, И.И. - М. : ФОРУМ; ИНФРА-М, 2007. - 496 с. Информационные системы в экономике : Учеб. пособие - 2-е изд ...
  3. Баркалова Н. В.; Левакова И. В. Изд. 3-е, перераб и доп

    Документ
    ... автоматического управления. Нелинейные и оптимальные системы: учеб. пособие для ... Голицына Ольга Леонидовна , Максимов Николай Вениаминович; Партыка Татьяна Леонидовна; Попов ... 2003: практ. разраб. баз данных; учеб. курс / Сеннов Андрей Светозарович ...
  4. Бюллетень новых поступлений сентябрь 2013 год

    Бюллетень
    ... учеб. пособие для вузов по спец. "Менеджмент организации", "Управление ... СИСТЕМЫ 6Ф7.3(075) Г60 Голицына О.Л.    Основы проектирования баз данных [Текст] : учеб. пособие для сред. проф. образования / О. Л. Голицына, Т. Л. Партыка, И. И. Попов ...

Другие похожие документы..