Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 11
Текст из файла (страница 11)
Следует иметь в виду, что, хотя речь н идет о файлах «с прямым доступом», среднее время нахождения сегмента, так называемое латентное время, равно половине времени полного оборота диска. У индексированных файлов сохраняется также то основное свойство, что запись производится последовательно в их конец. Поэтому они особенно полезны в случаях, когда изменения происходят сравнительно редко, Изменения производятся либо при помощи увеличения файла, либо при помощи копирования и обновления всего файла. Просмотр может осуществляться намного быстрее, если используются индексные указатели. Это типичная ситуация для так называемых банков данных.
1.11. Поеледоеателеемй Файл 59 Системы, которые допускают выборочное изменение фрагментов в середине файла, обычно сложны и пользоваться нми рискованно, поскольку новые порции информации должны быть того же размера, что н старые, на место которых онн записываются.
Кроме того, прн обработке большого объема данных не рекомендуется выборочное изменение, поскольку прн любой неудаче — чем бы она ни была вызвана: ошибкой программы илн сбоем оборудования — по правилам должно существовать некоторое состояние, к которому следует вернуться, с тем чтобы возобновить и повторить прерванную работу. Поэтому обновление обычно происходит целиком: старый файл заменяется новой, измененной копией только после того, как последовательная проверка установит правильность нового файла.
Для обновления последовательная организация является наиболее надежной. Ее следует предпочесть более сложным способам организации данных большого объема. Эти способы могут быть эффективнее, но они часто приводят к полной потере данных при сбое оборудования. 1.11.3. 1енсты Файлы, состоящие нз компонент типа сйаг (символьного), играют особо важную роль в вычислениях и обработке данных: они обеспечивают взаимодействие между вычислительными системамн и пользователями. Читаемый вход, организуемый программистом, так же как читаемый выход, содержащий результаты вычислений, представляют собой последовательности символов. Поэтому таким типам данных присваивается стандартное имя: 1уре1ех1 = Н(е о( айаг В конечном счете взаимодействие между вычислительным процессом и человеком можно представить двумя текстовыми файлами.
Олин из них содержит входную информацию (1при1) для вычислительного процесса, другой — результаты вычисления, называемые выходной информацией (ои1ри1). С этого момента мы будем считать, что каждая программа содержит описания этих двух файлов, имеющие следующий вид: чаг1при1, оп1ри1: 1ех1 Учитывая, что этн файлы соответствуют стандартным средствам ввода н вывода вычислительной системы (таким, как устройство чтения с перфокарт н устройство вывода на печать), мы будем считать, что файл 1при1 можно только читать, а в файл ои1ри1 можно только писать. Поскольку эти два стандартных файла используются очень часто, мы определим, что если первый параметр 1.
Фундаяентакьньи структуры даяяьи процедур геаг( и иг(!е не является файловой переменной, то по умолчанию предполагаются соответственно файлы (прис и ои(рий Кроме того, мы позволим этим двум стандартным процедурам иметь произвольное число аргументов. Суммируем введенные выше обозначения: генг((х1, ..., хи) означает гели(три!, х1, ..., кп) иг(!е(х(, ..., кп) означает иг((е(ои(ри!, х1, ..., кп) гегпЦ, х!, ..., хи) означает йеа!и геац(!, х1); ...; гептил, хп)епд игйе4, х1, ..., кя) означает Ьей!и гегйе(х, х1); ...", игйе((, к(г) епг( Тексты являются типичным примером последовательностей, в которых обнаруживается подструктура.
Принятые единицы этой подструктуры — это главы, абзацы н строки. Обычный способ изображения подструктуры текста — использование специальных разделительных символов. Наиболее известный пример — символ пробела, но -подобные символы могут использоваться н для указания концов строк, абзацев и глав. Например, широко распространенное множество символов 1ЬО, включая его американскую версию АБСП, содержит несколько таких элементов, называемых управляющими символами (см.
приложение Л). В этой книге мы не будем использовать специальные разделительные символы и задавать какой-либо способ представления подструктуры. Вместо этого мы рассмотрим текст как файл, состоящий из символьных последовательностей, представляющих отдельные строки. Кроме того, мы ограничимся одним уровнем подструктуры, а именно строкой. Однако вместо того, чтобы определить тексты как файлы файлов печатаемых символов, мы рассматриваем нх как файлы символов и вводим дополнительные операции и предикаты для управления, т. е. для отметки и распознавания строк.
Их смысл легче понять, если предположить, что строки разделяются (гипотетичесьими) разделительными символамн (не принадлежащими к типу слог), а задача этих операций и предикатов — поиск н распознавание таких символов-разделителей. Дополнительные операции следующие: иг!се!р(1) — добавить признак конца строки к файлу 1. геаг((и()) — пропустить символы файла 1 до символа, который непосредственно следует за очередным символом конца строки. ео1л(!) — булевская функция.
Истинна, если позиция файла указывает на признак конца строки, иначе ложна. Предполагается, что если ео!п(1) истинна, то )'1 =пробел. 1,11. Поеледовател»нвгй файл ген г11е(9; пЬйе- а йв Ьерп пЬ1!е — чг йо Ьерп Я(х); итгге(у',х) евй; ят11е!л(1') евй (1.54) Чтение текста 1: ~ гевег(Д; 1 пЬ|1е —,еоу"(,1) йа Ьея1п вИе — ео1а(у') йо Ьей1п геай(1,х)' о (х) епй: 1'; геав11гг(у') епй (1,55) Бывают случаи, когда построчная структура текста не содержит никакой существенной информации.
Наше соглашение о значении буферной переменной при появлении признака конца строки [см. определение ео1п(1)) позволяет в таких случаях использовать простую схему. Заметим, что в соответствии с определением ео)п каждый конец строки дает добавочный символ пробела. ттЫ!Е гЕО1"(1) йа Ьерп геях)1 Я(х) епй Теперь мы можем привести дне схемы программ для записи и чтения текстов, подобно схемам для «записи» и «чтения» других файлов (см.
(1.52) и (1.53)). В этих схемах участвует текстовый файл 1 и уделяется должное внимание формированию н распознаванию строчной структуры. Пусть й(х) — оператор, прнсваивающнй переменной х (типа айаг) некоторое значение. В нем также определяются условия р и д, означающие «это был последний символ строки» и «это был последний символ файла>.
При чтении файла в начале каждой строки выполняется оператор У, а для каждого символа х выполняется оператор Я(х). В конце каждой строки выполняется оператор Г Запись текста !. Фундалентах»ные структуры данных В большинстве языков программирования принято допускать для процедур чтения и записи аргументы типа !и!еиег нлн геи!. Такое обобщение было бы строгим, если бы типы !пгейег и геа! представлялись как массивы символов, компоненты которых обозначают отдельные цифры числа. Языки, ориентированные только на коммерческие приложения, действительно удовлетворяют такому определеншо: они требуют представления чисел в десятичных цифрах н в десятичной системе счисления. Но введение типов !и!едет и геа! в качестве фундаментальных обладает важным преимуществом: можно опустить подобные детальные спецификации, Прп этом в системе можно использовать такие представления чисел, которые больше ей соответствуют.
В действительности в системах, ориентированных на научные расчеты, всегда выбирают двоичное представление, так как оно почти во всех отношениях имеет преимушества перед десятичным. Но из этого следует, что программист должен понимать, что невозможно читать числа или записывать их в файлы без соответствуюших операций преобразования. Обычно эти операции неявно содержатся в операциях геай и юг!!е с аргументами числовых типов.
Однако профессиональный программист сознает, что такие операции (так называемые !/О-операции) состоят из двух различных действий: обмена даннымн между различными запоминающими устройствами и преобразования представлений данных. Последнее действие может быть довольно сложным и занимать много времени. В последующих главах этой книги операции чтения и записи с 1исловыми аргументами будут использоваться в соответствии с правилами языка программирования Паскаль. Эги правила допускают некоторые спецификации формата для управления процессом преобразования. Спецификации формата указывают число желательных цифр прн операции записи.
Это число символов, называемое также «шириной поля», записывается сразу после аргумента следующим образом: гвг!!е(), к: и) Аргумент х должен записываться в файл (; его значение преобразуется в последовательность из (по крайней мере) и символов. Если необходимо, цифрам предшествует знак и соответствуюшее число пробелов, Для того чтобы понять примеры программ, приводимые далее в этой книге, дальнейшие подробности не нужны. Однако мы включили сюда две подпрограммы (программы 1.3 и 1.4), преобразующие представления чисел, чтобы показать, насколько сложны подобные действия, неявно предполагаюшиеся в операторах записи. Эти процедуры преобразуют ве- ,рюоееааге геад еа1 (чвг у': 1ех1; чае х. 'геа1); (чтение вещественноо числа х из о5айлаг) (далее идупг константы, связанные с отдельной вычислительной системой ) еоавФ 148 = 281474976710656; (= 2чч48) йт1Г = 56294995342131,' (= Г48 д1ч 5) з = 27; (= огй('0') ) 1)т 1 = 322; 1максимальный порядок) йт 2:= — 292; (минимальный порядок) 1урерозтг = 0 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
