Make your own free website on Tripod.com

פרופ' אבא אנגלברג

טורבו פסקל. תכנות מבני למתחילים ומתקדמים כולל גרסאות 5.5 ו- 6.0

Проф. Аба Ангельберг

Турбо Паскаль. Структурное программирование для начинающих и продолжающих (включительно версии 5.5 и 6.0)

 

Глава 12. Уточнение(обновление) файлов

12.1. Обработка файлов

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

Обычно хотят осуществить несколько операций с одной записью или с разными записями. Поэтому принято создавать файл изменений(Transactions File), который содержит все операции, которые предполагают проделать с файлом. Уточняемый исходный файл называется файлом-отцом(Master File), выводной уточненный файл называют файлом-сыном или новым файлом-отцом(New Master File). Это - пакетная обработка(Batch) в отличие от линейной обработки(On - Line), в которой каждое движение обрабатывается отдельно по мере его поступления в компьютер.

Предположим, что даны два файла: a).отцовский файл maskorot, который содержит данные сотрудников предприятия; b).файл обновлений(изменений) с записями для исполнения различных действий. Обновления, включаемые в файл изменений:

a).Добавление новой записи в отцовский файл. Символ 'ה' означает добавление записи.

Имя работника

ה

Зарплата

Оценка

Но символ 'ה' не будет помещен в новую запись, заносимую в файл maskoret.

b).Удаление записи из отцовского файла. В такой записи требуется только имя работника, по которому отождествляется искомая запись для ее стирания в файле. Символ 'מ' означает вид этого изменения.

Имя работника

מ

c).Обновление поля в записи отцовского файла. Здесь обслуживается два разных уточнения: чтобы уточнить содержимое поля sachar, надо отметить тип действия буквой 'ש', а для уточнения поля tziyun надо обозначить тип действия буквой 'צ' .

Имя работника

ש

Новая зарплата

 

Имя работника

צ

Новая оценка

 

12.2. Записи изменяемой длины

До сих пор мы работали с файлами, записи которых имели постоянную длину. Но можно соорудить файл с записями переменной длины(Variant Records), как пример записей в файле изменений, описанном выше. Число и тип полей могут быть различными для каждого вида записи.

В следующей программе мы вводим данные с консоли и создаем файл изменений, который содержит записи типов, представленных прежде.

program maskorti; {1}

uses crt,dos; {2}

const orech = 25; {3/4}

type {5}

shem = string[orech]; {6}

transaction = record {7}

shem_oved: shem; {8}

case peula: char of {9}

'ה': (tsachar: real; ttziyun: char); {10/1}

'מ': (); {12}

'ש': (sachar_chadash: real); {13}

'צ': (tziyun_chadash: char); {14}

end; {15}

var {16}

tran_chadash: transaction; {17}

tranfile: file of transaction; {18}

acharon: shem; {19}

{HebSeg: word absolute 0:$42;} {20}

sw,sof: boolean; {21}

ch: char; {22}

 

procedure klot_shem; {23}

begin {24}

repeat {Vvodi zapisi} {25}

sw := false; {26}

write('Vvedi im"a: '); {27}

with tran_chadash do {28}

begin {29}

readln(shem_oved); {30}

if shem_oved < acharon then {31}

begin {32}

writeln(shem_oved,' ne na vernom meste'); {33}

sw := true {34}

end {35}

end {36}

until sw = false; {37}

acharon := tran_chadash.shem_oved {38}

end; {39}

 

procedure klot_peula; {40}

begin {41}

repeat {42}

sw := false; {43}

write('Vvedi vid operacii(צ ,ש ,ה ili מ): '); {44}

with tran_chadash do {45}

begin {46}

readln(peula); {47}

if not ((peula = 'ה') or (peula = 'מ') or {48}

(peula = 'ש') or (peula = 'צ')) then {49}

begin {50}

writeln('Oshibka v tipe! Vvedi ego snova'); {51}

sw := true {52}

end {53}

end {54}

until sw = false {55}

end; {56}

 

procedure klot_sachar(var kelet: real); {57}

var {58}

ezer1{,ezer2}: string[12]; {59}

j: integer; {60}

begin {61}

repeat {62}

sw := false; {63}

write('Vvedi zarplatu: '); {64}

{mem[HebSeg:9] := 2;} {65}

readln(ezer1); {66/9}

{for j := 1 to length(ezer1) do ezer2[j] := ezer1[length(ezer1)-j+1];

ezer2[0] := ezer1[0];}

val(ezer1{2},kelet,j); {70}

if j <> 0 then {71}

begin {72}

writeln('Oshibka v chisle! Vvedi ego snova'); {73}

sw := true {74}

end {75}

until sw = false; {76}

end; {77}

 

procedure klot_tziyun(var kelet: char); {78}

begin {79}

repeat {80}

sw := false; {81}

write('Vvedi ocenku(א , ב ili ג: '); {82}

with tran_chadash do {83}

begin {84}

readln(kelet); {85}

if not ((kelet >= 'א') and (kelet <= 'ג')) then {86}

begin {87}

writeln('Oshibka v ocenke! Vvedi ee snova'); {88}

sw := true {89}

end {90}

end {91}

until sw = false {92}

end; {93}

 

begin {Glavna"a programma} {94}

acharon := ''; {95}

assign(tranfile,'tran.dat'); {96}

rewrite(tranfile); {97}

clrscr; {DirectVideo := false; mem[HebSeg:8] := 1;} {98/9}

writeln('Najmi ENTER, chtobi nachat" vvod dannih'); {100}

readln; {101}

repeat {102}

klot_shem; {103}

klot_peula; {104}

with tran_chadash do {105}

case peula of {106}

'ה': begin klot_sachar(tsachar); klot_tziyun(ttziyun) end; {107/10}

'ש': klot_sachar(sachar_chadash); {111}

'צ': klot_tziyun(tziyun_chadash) {112}

end; {113}

write(tranfile,tran_chadash); {114/5}

writeln('Najmi klavishu ESC dla zavershenia, lubuu druguu - dla prodolj');

ch := readkey; {116}

sof := ch = #27 {117}

until sof; {118}

close(tranfile); {119}

{mem[HebSeg:8] := 0;}{Vozvrashenie ekrana - sleva napravo} {120}

end. {121}

Объяснение.

{9-15}Объявляется изменяемая часть записи. В изменяемой записи всегда существует общее для всех возможных записей поле, содержимое которого устанавливает, как должно выглядеть продолжение записи, следующее за этим полем. В нашем примере это поле peula, определение которого находится в строке 9 (оно называется символьным полем - Tag Field). В таком случае изменяемое поле содержит постоянную часть(Fixed part) и переменную часть(Variant part). В представленном примере постоянная часть состоит из полей в строках {8} и {9}, а переменная часть - из трех альтернатив: полей в строках {10} и {11}, поля в строке {13} и поля в строке {14}.

В следующем объявлении дается описание полей, которые можно включить в запись после такого поля. (Рис. 1 Имя типа Постоянная Перечень полей).

Постоянная равна одному из значений общего поля peula. К нему возвращаются несколько раз для обработки всех возможных значений поля. Перечень полей выглядит так: (Рис. 2 Имя поля Тип). Огибающая стрелка сверху в перечне полей показывает, что этот перечень может быть пустым, как в поле מ в строке {12}.

Вместо case peula: char of можно написать case char of, но тогда отсутствует символьное поле, которое позволяет нам проверить тип записи.

{106-113}Во время заполнения полей запрашиваются данные, которые соответствует каждому случаю отдельно.

{31-36}Изменения должны быть отсортированы(по именам работников), не допускается ввод данных, нарушающих этот порядок.

 

12.3. Уточнение последовательного файла

Файлы, которыми мы займемся, являются последовательными(Sequential Files). Чтобы такой файл уточнить или добавить запись между существующими записями или даже в его конец, надо скопировать его во второй файл. В ходе копирования можно исправлять существующие записи, добавлять записи или удалять их по необходимости. Записи уточнения в файле исправлений должны быть упорядочены согласно порядка классификации редактируемого файла.

В программе maskorth мы учились создавать отцовский файл, а в maskorti - файл исправлений. Теперь можно написать программу, целью которой будет уточнение отцовского файла согласно данных в файле исправлений(см. блок-схемы). В них maskorot это имя старого_отцовского_файла, nmaskorot - имя нового_отцовского_файла, который получается уточнением старого согласно исправлений из файла tranfile. К записи из файла maskorot будем обращаться по имени mas, к записи из файла nmaskorot будем обращаться по имени nmas, а к записи из tranfile - по имени trn. (idkun - уточнение(исправление), hadpasat hakovetz - печать файла, hataka - копирование, hosafa - добавление). (Рис. 3 Начни Открой файлы Нет Файлы maskorot и tranfile существуют? Сигнал отсутствия файлов Завершение) (Рис. 4 IDKUN Прочти запись из файла maskorot Прочти запись из файла tranfile Достигли конца обоих файлов? Да Вернись) (Рис. 5 HATAKA_HOSAFA Да Имеют место mas.shemoved, trn.shemoved? Нет Да Имеют место ... ? Нет Вернись)

(Рис. 6 HOSAFA Нет Да Сообщение об ошибке Запиши Прочти Вернись) (Рис. 7 HATAKA Спиши nmaskorot из maskorot Прочти Вернись)

(Рис. 8 CASESTRUCTURE Выдай сообщение об ошибке Спиши nmaskorot из maskorot Спиши maskorot из maskorot Точка сбора Прочти Прочти Вернись)

Далее приводится текст программы(согласно блок-схем):

program maskortj; {1}

uses crt; {2}

const orech = 25; {3/4}

type {5}

str = string[127]; {6}

shem = string[orech]; {7}

reshumatoved = record {8}

shem_oved: shem; {9}

sachar: real; {10}

tziyun: char; {11}

end; {12}

transaction = record {13}

shem_oved: shem; {14}

case peula: char of {15}

'ה': (tsachar: real; ttziyun: char); {16/7}

'מ': (); {18}

'ש': (sachar_chadash: real); {19}

'צ': (tziyun_chadash: char); {20}

end; {21}

var {22}

maskorot, nmaskorot: file of reshumatoved; {23}

tranfile: file of transaction; {24}

mas, nmas: reshumatoved; {25}

trn: transaction; {26}

eoft,eofm: boolean; {27}

file_name: str; {28}

m,t: boolean; {29}

{HebSeg: word absolute 0:$42;} {30}

 

function exist1(shem_file: str): boolean; {31}

begin {32}

assign(maskorot,shem_file); {33}

{$i-} {34}

reset(maskorot); {35}

{$i+} {36}

exist1 := IOresult = 0 {37}

end; {38}

 

function exist2(shem_file: str): boolean; {39}

begin {40}

assign(tranfile,shem_file); {41}

{$i-} {42}

reset(tranfile); {43}

{$i+} {44}

exist2 := IOresult = 0 {45}

end; {46}

 

procedure input1; {47}

begin {48}

if eof(maskorot) then {49}

begin eofm := true; mas.shem_oved := 'תתתתתתתתתתת' end {50/3}

else read(maskorot, mas) {54/5}

end; {56}

 

procedure input2; {57}

begin {58}

if eof(tranfile) then {59}

begin eoft := true; trn.shem_oved := 'תתתתתתתתתתת' end {60/3}

else read(tranfile, trn) {64/5}

end; {66}

 

procedure case_structure; {67}

begin {68}

case trn.peula of {69}

'מ': ; {70}

'ש': begin mas.sachar := trn.sachar_chadash; {71/2}

nmas := mas; write(nmaskorot,nmas) end; {73/5}

'צ': begin mas.tziyun := trn.tziyun_chadash; {76/7}

nmas := mas; write(nmaskorot,nmas) end; {78/80}

'ה': writeln('Popitalsa dobavit zapis, kotoraa uje v faile') {81}

end; {82}

input1; {83}

input2 {84}

end; {85}

 

procedure hosafa; {86}

begin {87}

if trn.peula = 'ה' then {88}

begin {89}

nmas.shem_oved := trn.shem_oved; {90}

nmas.sachar := trn.tsachar; {91}

nmas.tziyun := trn.ttziyun; {92}

write(nmaskorot,nmas); {93}

end {94}

else writeln('Nelza ispravit nesushestvuushuu zapis'); {95/6}

input2 {97}

end; {98}

 

procedure hataka; {99}

begin {100}

nmas := mas; {101}

write(nmaskorot,nmas); {102}

input1 {103}

end; {104}

 

procedure hataka_hosafa; {105}

begin {106}

if mas.shem_oved < trn.shem_oved then hataka {107/8}

else if mas.shem_oved = trn.shem_oved then case_structure {109/11}

else hosafa {mas.shem_oved > trn.shem_oved} {112/3}

end; {114}

 

procedure idkun; {115}

begin {116}

input1; {117}

input2; {118}

while not (eoft and eofm) do hataka_hosafa {119/20}

end; {121}

 

procedure hadpasat_hakovetz; {122}

begin {123}

reset(nmaskorot); {124}

writeln; {125}

while not eof(nmaskorot) do {126}

begin {127}

read(nmaskorot,nmas); {128}

with nmas do {129}

begin {130}

write(shem_oved); {131}

{mem[HebSeg:8] := 0;} {132}

gotoxy(60,wherey); {133}

write(sachar:2:2); {134}

{mem[HebSeg:8] := 1;} {135}

gotoxy(25,wherey); {136}

case tziyun of {137}

'א': writeln('מצוין'); {138}

'ב': writeln('טוב'); {139}

'ג': writeln('ממוצע'); {140}

end {141}

end; {142}

writeln {143}

end; {144}

writeln('Najmi >Enter< dla zavershenia programmi'); {145}

readln {146}

end; {147}

 

begin {MAIN PROGRAM} {148}

clrscr; {DirectVideo := false; mem[HebSeg:8] := 1;} {149/51}

assign(nmaskorot,'nmas.dat'); {152}

rewrite(nmaskorot); {153}

file_name := 'mas.ddd'; {154}

eofm := false; eoft := false; {155/6}

m := not exist1(file_name); {157}

file_name := 'tran.dat'; {158}

t := not exist2(file_name); {159}

if not(m or t) then {160}

begin {161}

idkun; {162}

close(tranfile); {163}

close(maskorot); {164}

hadpasat_hakovetz; {165}

writeln('Ispravlenia uspeshno zaversheni'); {166}

end {167}

else {168}

if m then {169}

begin {170}

writeln('Fail mas.ddd ne sushestvuet'); {171}

if not t then close(tranfile) {172/3}

end {174}

else {175}

begin {176}

writeln('Fail tran.dat ne sushestvuet'); {177}

close(maskorot) {178}

end; {179}

close(nmaskorot); {180}

{mem[HebSeg:8] := 0;} {181}

end. {182}

Объяснение.

{148-182}Главная программа.

{154}Внешнее имя файла зарплат. Имя это также можно ввести в переменную file_name и таким образом устанавливать его во время исполнения программы.

{155-156}Переменные eofm и eoft являются флажками, отмечающими наличие или отсутствие записей в файлах зарплат и исправлений, соотвественно.

{157}Логическая функция exist1 открывает файл зарплат(строка {35}). Во избежание ошибки исполнения при отсутствии файла гасится ключ $I, а включается он только после попытки открытия файла. Если эта попытка не удалась, переменная IOresult принимает значение, отличное от нуля, а сама булева функция принимает значение false(строка {37}).

{159}Булева функция exist2 аналогична функции exist1.

{160}Программа может быть продолжена, только если два файла (maskorot и tranfile) существуют. Иначе - пользователь получает соответствующее сообщение (строки {171}, {177}). Ему следует создать эти файлы или выяснить их внешние имена до нового запуска программы. Если файлы существуют, то уточнение совершается, исправленный файл(nmaskorot) печатается и - файлы закрываются.

Процедура idkun(строка {115}). В этой процедуре вводится запись из файла maskorot, а затем запись из файла tranfile. Чтение выполняется посредством процедур input1 и input2. В обеих включается флажок при достижении конца файла и присваивается заведомо большое значение переменной shem_oved. Причина такого присвоения будет дана далее.

{119}Процедура hataka_hosafa выполняется в цикле до исчерпания записей в каждом из файлов (tranfile и maskorot).

Процедура hataka_hosafa(строка {105}). Если отсутствует изменение, относящееся к некоторой записи файла maskorot, то выполняется процедура hataka, которая копирует ее из файла maskorot в файл nmaskorot (строки {101-102}).

Если же имеется уточнение, относящееся к данной записи файла maskorot, то выполняется процедура case_structure.

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

Процедура case_structure. Изменяем значение sachar или tziyun согласно типу операции и читаем следующие записи из файлов maskorot и tranfile.

 

12.4. Файлы прямого доступа (*)

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

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

Когда отцовский файл велик, а число исправлений невелико, стоит исправлять только соответствующие им записи и не читать и переписывать все остальные. Это требование особенно важно при обработке on-line(On Line Processing), где случайно возникают отдельные уточнения файла или обращения к записям. При такой обработке необходимо обеспечивать немедленные уточнения(движения данных).

Доступ к отдельной записи возможен посредством метода прямого доступа (Direct Access Method). Это метод не определен в стандартном Паскале, он определен в Турбо Паскале. Это расширение языка позволяет прямой доступ к любой записи файла по ее порядковому номеру без обработки предшествующих ей записей.

Метод прямого доступа возможен только на запоминающих устройствах прямого доступа - DASD(Direct Access Storage Devices) вроде дискет и магнитных дисков, в то время как последовательный доступ возможен на всех запоминающих устройствах.

Доступ к определенной записи становится возможным благодаря команде поиска SEEK, которая устанавливает головку чтения/записи диска на начало нужной записи: seek(имя_файла, номер_записи);

Пример решения задачи методом прямого доступа. Допустим, что мы создали файл, который содержит данные о сальдо(денежном остатке) на счетах всех клиентов банка. В записи номер 0(первой в файле, т.к. нумерация записей начинается с нуля) находится сальдо счета номер 0, в записи номер 1 находится сальдо счета номер 1 и т.д. Этот файл построим с помощью такой программы(bniyat kovetz - построение файла, cheshbon/-ot - счет/-ы, erech - значение):

program bniyat_kovetz_cheshbon;

var

cheshbonot: file of real;

erech: real;

begin

assign(cheshbonot,'chesh.dat');

rewrite(cheshbonot);

writeln('Najmi ENTER, chtobi nachat');

while not eof do

begin

write('Vvedi ocherednoe saldo(deneg na schete):');

read(erech);

write(cheshbonot,erech)

end; {close(cheshbonot)}

end.

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

program cheshbon; {1}

var {2}

cheshbonot: file of real; {3}

mispar_cheshbon: integer; {4}

erech_kodem,erech_chadash,schum: real; {5}

begin {6}

assign(cheshbonot,'chesh.dat'); {7}

reset(cheshbonot); {8}

writeln('Najmi ENTER, chtobi nachat'); {9}

while not eof do {10}

begin {11}

write('Naberi nomer scheta: '); {12}

readln(mispar_cheshbon); {13}

write('Vvedi summu so znakom(- dla sniatia, + - dla vnesenia: '); {14/5}

read(schum); {16}

seek(cheshbonot,mispar_cheshbon); {17}

read(cheshbonot,erech_kodem); {18}

erech_chadash := erech_kodem + schum; {19}

seek(cheshbonot,mispar_cheshbon); {20}

write(cheshbonot,erech_chadash); {21}

end; {22}

end. {23}

Объяснение

{17-19}Команда seek находит местоположение записи, номер которой равен значению переменной mispar_cheshbon. При выполнении процедуры read в строке {18} в буфер читается эта запись. В строке {19} уточняется сумма.

{20}По выполнении команды read читающая головка переходит к следующей записи. Если же мы хотим записать уточненное сальдо на правильное место, нужно повторить команду seek(строка {20}). Эта команда нацелит головку(записи) диска на то место, где надо поместить запись номер mispar_cheshbon.

Для записи файла прямого доступа открываем его как обычно командой rewrite, а во время чтения и уточнения существующего файла открываем его командой reset. И тогда можно пользоваться командой поиска seek для установления местонахождения записи, чтения и записи на любое место файла. Команда reset позволяет обычно только чтение и только последовательное, начиная с головной записи файла.

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

Если бы в этом примере мы хотели посмотреть содержимое файла после изменений, то в конце программы могли написать:

reset(cheshbonot);

while not eof(cheshbonot) do

begin

read(cheshbonot,erech);

write(erech:8:2)

end;

Команда reset возврашает указатель на файл к его началу. Понятно, что можно с тем же успехом написать вместо reset команду seek(cheshbonot,0);

 

12.5. Индексно-последовательные файлы(*)

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

reshimat_index = record

mispar_reshuma: integer;

mafteach: sug_mafteach

end;

Из таких записей создается массив(или таблица), тип которой определяется так:

tavlat_index = array[-2..n-1] of reshumat_index;

Строение таблицы:

Позиция в таблице

Номер записи

Ключ

 

-2

-1

0

1

2

3

4

5

6

1

6

5

2

7

4

6

1

3

}

}

A17

A84

B14

C17

C35

D40

zzz }

Общие данные

 

 

 

 

 

 

 

Отмененная запись

Переменная index определяется так:

var index: tavlat_index;

В примере таблица располагает n+2 элементами. Два первых используются для хранения общих данных, а в n следующих позициях, начиная с третьей, записываются ключи с номерами записей. В элементе таблицы index[-1].mispar_reshuma содержится число задействованных до сих пор в файле записей. Возможно существование еще некоторого числа записей, но они отмечаются как отмененные и к ним не обращаются в ходе обработки.

При отмене записи ее не удаляют из файла, но добавляют знак отмены, чтобы отметить, что она более не действует. В элементе index[-2].mispar_reshuma записывается число таких записей, к которым при необходимости можно все-таки вернуться. Действительное удаление таких записей из файла совершается только в ходе реорганизации индексной таблицы при переписывании файла на новое место того же диска или на другой диск.

В таблице из примера число записей файла равно 7, но действительными являются только 6, поэтому index[-1].mispar_reshuma = 6. Седьмая запись с третьим порядковым номером в файле находится в конце таблицы с ключем zzz, поэтому место записи номер 3 свободно для повторного использования. При добавлении записей в файл можно будет на это место записать новую запись и исправить соответственно индексную таблицу. А пока index[-2].mispar_reshuma = 1.

Описанный в примере файл является индексно-последовательным (Indexed Sequential File), который допускает и последовательную обработку и прямой доступ. Операции, которые можно совершать с таким файлом:

создание файла; исправление записей; отмена записей; добавление записей. a).Создание файла. Файл записывается на диск, а в таблицу заносится порядковые номера записей и их ключи. В конце таблица упорядочивается по значениям ключей.

b).Исправление записей. С помощью индексной таблицы находится порядковый номер исправляемой записи. По команде seek определяем ее местонахождение в файле и с помощью read читаем ее. Уточняем содержимое записи и записываем ее на свое место в файле. Если изменен ключ, надо исправить индексную таблицу и заново ее отсортировать.

c).Отмена записей. Для отмены записи надо совершить такие действия:

1).Найти ее ключ в индексной таблице.

2).Изменить ключ записи на zzz. Номер записи не меняется, т.к. теперь он обозначает место в файле, которое предназначено для повторного использования.

3).Заново отсортировать индексную таблицу. И отмененная(недействительная) запись должна участвовать в сортировке, поскольку index[-1].mispar_reshuma не изменено. Отмененные записи помещаются в конце таблицы, т.к. их ключ равен zzz, и они в фактической сортировке не участвуют.

4).На 1 уменьшить index[-1].mispar_reshuma, поскольку одна запись переведена из состояния действительной в состояние недействительной.

5).Добавить 1 к index[-2].mispar_reshuma, т.к. появилось еще одно свободное место в файле для новой записи.

На каждом этапе число записей в файле равно сумме

index[-2].mispar_reshuma + index[-1].mispar_reshuma.

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

c).Добавление записей. Для добавления записей надо совершить такие действия:

1).Проверить index[-2].mispar_reshuma, чтобы выяснить имеются ли свободные места в файле (таблице).

2).Если есть, то надо поискать первую запись с ключем zzz. Ее адрес в индексной таблице есть index[-1].mispar_reshuma. В этом примере получаем число 6, поэтому соответствующий вход в таблицу будет index[6]. Помещаем новую запись по номеру записи в index[6], в примере - на третье место. Определяем это место на диске посредством команды seek и записываем командой write. Уточняем счетчики на двух первых позициях таблицы с помощью команд:

index[-2].mispar_reshuma := index[-2].mispar_reshuma - 1;

index[-1].mispar_reshuma := index[-1].mispar_reshuma + 1;

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

Команда поиска записи есть seek(index[-1].mispar_reshuma); После нее выполняется read для прочтения этой записи(?). Далее следует команда write для помещения в файл новой записи. В измененной форме(?) можно записать:

seek(shem_kovetz, filesize(shem_kovetz);

В обеих случаях добавляем 1 к индексу index[-1].mispar_reshuma и сортируем (кроме двух первых) элементы таблицы index. Число упорядочиваемых элементов равно index[-1].mispar_reshuma, и в этом случае index[-2].mispar_reshuma = 0.

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

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

var kovetz_index: file of tavlat_index;

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

 

Программа для примера

В идущей ниже программе мы демонстрируем: a).построение индексной таблицы для файла сотрудников по известным правилам; b).прямое извлечение записи сотрудника по запросу оператора (mafteach - ключ, reshumat index - индексная запись, tavlat index - индексная таблица, hadpasat reshimot min hakovetz - печать записей из файла, shem poel - имя работника).

{$R-} {1}

program maskortk; {2}

uses crt; {3}

const orech = 25; {4-5}

type {6}

shem = string[orech]; {7}

reshumat_oved = record {8}

shem_oved: shem; {9}

sachar: real; {10}

tziyun: 'א'..'ג' {11}

end; {12}

reshumat_index = record {13}

mispar_reshuma: integer; {14}

mafteach: shem {15}

end; {16}

tavlat_index = array[-2..100] of reshumat_index; {17}

var {18}

maskorot: file of reshumat_oved; {19}

reshuma_chadasha: reshumat_oved; {20}

{HebSeg: word absolute 0:$42;} {21}

{********************} {22}

index: tavlat_index; {23}

index_file: file of tavlat_index; {24}

i,j: integer; {25}

sw,sof: boolean; {26}

ch: char; {27}

ezer1{,ezer2}: string[10]; {28}

{Deklaracii zaversheni} {29}

 

{Procedura postroenia indeksno-posledovatelnogo faila} {30}

procedure build_index(var k: integer); {31}

begin {32}

index[k].mispar_reshuma := k; {33}

index[k].mafteach := reshuma_chadasha.shem_oved; {34}

k := k + 1 {35}

end; {36}

 

procedure klitat_sachar; {37}

begin {38}

repeat {39}

sw := false; {40}

write('Vvedi zarplatu: '); {41}

{mem[HebSeg:9] := 2;} {PushMode}; {42}

readln(ezer1); {43}

{for j := 1 to length(ezer1) do } {44}

{ezer2[j] := ezer1[length(ezer1)-j+1];} {45}

{ezer2[0] := ezer1[0];} {46}

val(ezer1,reshuma_chadasha.sachar,j); {47}

if j <> 0 then {48}

begin {49}

writeln('Oshibka v chisle! Vvedi ego snova'); {50}

sw := true {51}

end {52}

until sw = false {53}

end; {54}

 

procedure klitat_tziyun; {55}

begin {56}

repeat {57}

sw := false; {58}

write('Vvedi ocenku(א, ב ili ג): '); {59}

with reshuma_chadasha do {60}

begin {61}

readln(tziyun); {62}

if not ((tziyun >= 'א') and (tziyun <= 'ג')) then {63}

begin {64}

writeln('Oshibka v ocenke! Vvedi ee snova'); {65}

sw := true {66}

end {67}

end {68}

until sw = false {69}

end; {70}

 

procedure klitat_reshumot; {71}

begin {72}

rewrite(maskorot); {73}

repeat {Vvodi zapisi} {74}

write('Vvedi imia rabotnika: '); {75}

readln(reshuma_chadasha.shem_oved); {76}

klitat_sachar; {77}

klitat_tziyun; {78}

write(maskorot, reshuma_chadasha); {79}

build_index(i); {80-81}

writeln('Dla prodoljenia najmi na lubuu klavishu, dla zavershenia >Esc<');

ch := readkey; {82}

sof := ch = #27 {83}

until sof {84}

end; {85}

 

procedure hadpasat_reshimot_min_hakovetz; {86}

var {87}

shem_poel: shem; {88}

i: integer; {89}

found: boolean; {90}

begin {91}

reset(maskorot); {92}

reset(index_file); {93}

read(index_file,index); {94}

writeln; {95}

repeat {96}

write('Vvedi imia raboynika, kotorogo nado izvlech: '); {97}

readln(shem_poel); {98}

i := 0; {99}

found := false; {100}

while not found and (i <= index[-1].mispar_reshuma) do {101}

if index[i].mafteach = shem_poel then {102}

begin {103}

found := true; {104}

seek(maskorot, index[i].mispar_reshuma); {105}

read(maskorot,reshuma_chadasha); {106}

with reshuma_chadasha do {107}

begin {108}

write(shem_oved); {109}

{mem[HebSeg:8] := 0;} {110}

gotoxy(60,wherey); {111}

write(sachar:2:2); {112}

{mem[HebSeg:8] := 1;} {113}

gotoxy(25,wherey); {114}

case tziyun of {115}

'א': writeln('Otlichno'); {116}

'ב': writeln('Horosho'); {117}

'ג': writeln('Posredsvenno'); {118}

end {119}

end {120}

end {121}

else i := i + 1; {122/3}

if not found then writeln('Sojaleu,rabotnika s takim imenem net'); {124/6}

writeln('Najmi lubuu klavishu dla prodoljenia ili <Esc> dla zavershenia');

ch := readkey; {127}

sof := ch = #27 {128}

until sof; {129}

close(maskorot); close(index_file) {130/1}

end; {132}

 

begin {Glavnaa programma} {133/4}

clrscr; {DirectVideo := false;} {135/6}

{mem[HebSeg:8] := 1;} {137}

assign(maskorot,'mas.dat'); {138}

i := 0; {139}

assign(index_file,'index.dat'); {140}

rewrite(index_file); {141}

klitat_reshumot; {142}

index[-1].mispar_reshuma := i - 1; {143}

index[-2].mispar_reshuma := 0; {144}

write(index_file, index); {145}

close(index_file); {146}

close(maskorot); {147}

hadpasat_reshimot_min_hakovetz; {148}

{mem[HebSeg:8] := 0;} {Vozvrashenie ekrana - sleva napravo} {149}

end. {150}

Объяснение

{13-17, 23-24}В этих строчках определяется индексная таблица.

{142}Ввод данных, анвалогичный вводу при построении последовательного файла, и в то же время мы строим здесь индексную таблицу(строка {80}). В ней записываем номер записи и значение ее ключа(рассмотри строки {30-36}. В строке {139} для i устанавливается начальное значение, равное 0. Оно возрастает на 1 всякий раз при вводе очередной записи в файл(строка {35}).

{143-144}По завершении построения индексной таблицы в переменную index[-1].mispar_reshuma подставляется число записей, введенных в файл, а в переменную index[-2].mispar_reshuma - значение нуль, т.к. на этом этапе нет отмененных записей, которые можно повторно использовать.

{145}Записываем запись index, содержащую массив tavlat_index в файл index_file(этот файл состоит только из одной записи).

Процедура hadpasat_reshimot_min_hakovetz. В этой процедуре у пользователя программы запрашивается имя работника, данные которого следует извлечь из файла (строки {97-98}). Таблица index просматривается до нахождения искомого ключа(строка {100}) или до безуспешного завершения просмотра(строки {124-125}).

{118-133}Демонстрация остальных свойств избранного файла.

 

12.6.Упражнения

12.6.1.Вопросы

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

(2).Прочти вопрос (1) этой главы. Расширь объявление записи, чтобы включить дополнительные данные. Т.е. добавь дополнительные поля при выполнениии определенных условий в семейном положении. Если холост/незамужем, добавляется булево поле, отмечающее наличие квартиры. Если женат/замужем, добавляется поле даты бракосочетания. Если разведен/а, добавляется поле даты развода. Если вдовец/ва, добавляется поле даты кончины супруга/и. Если брак второй, добавляется поле даты заключения первого брака. Если брак второй, добавляется поле даты прекращения первого брака. Если брак второй, добавляется поле даты заключения второго брака. Если брак второй, добавляется поле имени первой/го супруги/-а.

12.6.2.Программы

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

Напиши программу, которая будет выполнять следующие действия: a).Проверка возможной ошибки в данных - личный номер не находится в файле или имя не соответствует заданному личному номеру. b).Вычисление нового числа часов у каждого студента и новой средней оценки. Например, если перед исправлением у студента было 75 часов и средняя оценка 80, а теперь он занимался 10 часов и получил 100, средняя оценка будет такой: (7580 + 10100).85 = 82.3.

Ввод программы:

Личный номер

Имя

Часы

Оценка

Часы

Оценка

Часы

Оценка

100000

200000

300000

400000

500000

CHAVA LIBERMAN

RUTH HALEVI

BARUCH COCHEN

CHAVA ZALTZMAN

URI HECKEL

3

2

5

2

4

81

61

93

81

75

5

2

2

4

2

88

91

100

62

85

2

3

3

2

3

65

43

88

93

80

(2).Нужны уточнения файла из упражнения 1. Операции уточнения включают: добавление нового ученика(H); удаление действующего ученика(M); исправление числа часов и средней оценки(T). В записи файла исправлений находятся следующие поля: личный номер; код(H, M или T); остальные данные, если нужно.

Напиши программу, которая будет выполнять требуемые исправления. Воспользуйся следующими данными файла исправлений:

1 поле

2 поле

3 поле

4 поле

5 поле

6 поле

000750

200000

288100

555555

900000

H

M

H

T

T

RUTH ZAMIR

 

SHLOMO CARMELI

84

110

N

 

Z

68.3

68.1

25

 

78

 

 

89.5

 

65.4

(3).Отцовский файл в банке состоит из записей, состоящих из номеров счетов клиентов и их сальдо. Файл исправлений состоит из записей с номерами счетов и вкладами(положительные числа) или снимаемыми суммами(отрицательные числа). Возможны несколько действий с одним и тем же счетом. Уточни отцовский файл и напечатай сообщение об ошибках относительно действий со счетами, чьих номеров нет в отцовском файле.

(4).Записи в файле запасов содержат следующие поля: номер предмета; существующий запас; точка заказа; желательный уровень запаса; количество заказанных предметов. Запас предмета пополняется, когда сумма существующего запаса и количества заказанных предметов меньше точки заказа. Количество заказываемых при пополнении запаса предметов равно разнице между суммой запаса и заказа и желательным уровнем запаса.

Структура записи файла исправлений: номер предмета; тип действия(добавление запаса, извлечение из запаса); количество предметов.

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

a).с некоторым предметом операций нет; b).с некоторым предметом возможны операции объединения; c).существуют операции с несуществующим предметом(т.е. имеется ошибка в номере предмета или в отцовском файле).

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

The automatic electronic digital computer is a machine that uses

electronic circuits to manipulate data expressed in a symbolic

form according to specific rules in a predetermined way. Let's

axplain this in detail.

First of all the computer is a machine. This means it can perform

only those activities for which the basic capabilities have been

specifically designed into the machine.

Secondly, the computer is automatic. This means that once started,

it continues to run without outside interference.

Thirdly, it is electronic: that is, it is made up of electronic

circuits and runs on electrical energy.

Fourthly, the computer is a symbol manipulator. It manipulates

data, not phisical energy.

Fifth, the computer can perform only the processes of addition,

subtraction, multiplication, division and comparison, in additio

to data transfer between computers.

Sixth, someone (the programmer) must prepare a finite sequence of

the allowable individual operations (a program) for the computer

to follow.

Finnaly, the computer can store the program within its own memory

and then follow it through under its own direction without further

guidance.

(6).Напиши программу, которая будет считывать на вводе файл, созданнный в предыдущей задаче, и печатать текст строками длиной в N позиций. Длина строки задается на вводе. Первое предложение каждого абзаца следует начинать в пятой позиции строки. Запрещено делить слово между двумя строками.

(7).Напиши программу, которая ищет слова в нашем файле и выдает сообщения о них. Программа вводит некое слово, например, computer, и выдает: a).сколько раз это число появляется в тексте; b).20 символов, предшествующих этому слову, и 20 символов, следующих за ним. Используй ввод абзаца из предыдущей задачи.

Глава 13. Множества

13.1.Определение множества

Множество(Set) определяется в математике как набор объектов(Objets). Обозначим, например, буквой A множество учеников в классе, а буквой B - множество предметов в комнате. Объекты, составляющие множество, называются его элементами (Elements) или элементами множества. Определение множества в Паскале содержит больше ограничений, чем в математике(см. ниже):

a).Все элементы множества должны быть одного типа. Например, они все могут быть символами типа char или целыми числами, но они не могут быть обоих этих типов. Тип элементов называется базисным типом (Base Type).

b).Элементы множества в Паскале должны быть порядковыми (Ordinal) и задаваться в порядке возрастания. Из этого требования следует, что элементами множеств не могут быть массивы и записи, поскольку для пары массивов или записей нельзя установить отношение, которое из них больше, меньше или они равны. Обратимся, например, к двумерным массивам A и B. Пусть A[1,1] < B[1,1], а A[1,2] > B[1,2]. В этом случае нельзя сказать, в каком отношении находятся массивы A и B: или A меньше B, или А больше В или они равны. В аналогичном положении могут оказаться и соответствующие поля записей A и B.

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

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

 

13.2.Объявление и построение множества

Чтобы образовать множество, надо сперва объявить тип элементов, входящих в него: set of простой тип

Простой тип элементов это базисный тип. Он отождествляется с совокупностью элементов множества одним из трех способов: a).ссылкой на определенный заранее тип(например, char или тип, объявленый в декларации type); b).перечислением всех элементов множества; c).установлением подобласти уже определенного типа.

Декларация базисного типа может помещаться в объявлениях typy или var сразу после двоеточия за именем множества.

13.2.1.Объявление множества

Представим некоторые примеры для объяснения определения множества.

Пример первый(цвета)( tzeva rishoni - элементарный цвет, adom - красный, tzahov - голубой, kachol - голубой, kvutzat tzevaim - множество цветов)

type

tzeva_rishoni = (adom, tzahov, kachol);

kvutzat_tzevaim = set of tzeva_rishoni;

var tzevaim: kvutzat_tzevaim;

В этом примере переменная-множество tzevaim определено в три этапа: сначала определяется тип по имени tzeva_rishoni, затем тип kvutzat_tzevaim, как множество,

состоящее из элементов, слагающих tzeva_rishoni. И, наконец, объявляется переменная tzevaim как переменная-множество, которая может принимать любое из возможных значений kvutzat_tzevaim.

Какие значения kvutzat_tzevaim возможны? Опишем множество с помощью детализации его элементов в квадратных скобках. Перечень возможных групп, составленных из элементов tzeva_rishoni приведен ниже. Значение переменной-множества tzevaim может равняться одному из следующих:

множества из трех элементов: [adom, tzahov, kachol] ;

множества из двух элементов: [adom, tzahov], [adom, kachol], [tzahov, kachol];

множества из одного элемента: [adom], [tzahov], [kachol];

множества без элементов: [ ].

Множество с нулем элементов(без элементов) называется пустым(Empty Set). Оно является одним из возможных значений любого переменного-множества.

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

[kachol, adom, tzahov] = [adom, tzahov, kachol] = [kachol, tzahov, adom] =

= [tzahov, kachol, adom] = [tzahov, adom, kachol] = [adom, kachol, tzahov]

Перечень всех множеств, которые можно составить из базисного типа, есть множество мощности(Power Set). Если в базисном типе есть N элементов, то размер множества мощности всегда равен 2N. В нашем примере N равнялось 3, поэтому величина множества мощности есть 23 = 8.

Объявление переменной типа множество tzevaim может выполняться в два этапа или даже в один этап вместо трех, продемонстрированных выше. Объявление переменной-множества в два или три этапа позволяет определять несколько переменных, опираясь на тип, определенный в декларации type.

Декларация в два этапа:

type tzeva_rishoni = [adom, tzahov, kachol] ;

var tzevaim: set of tzeva_rishoni;

Декларация в один этап:

var tzevaim: set of (adom, tzahov, kachol) ;

 

Пример второй(буквы)(ot/otiyot - буква/ы):

type

otiyot = A .. Z;

kvutzat_otiyot = set of otiyot;

var shem, ktovet: kvutzat_otiyot;

В этом примере тип otiyot определен как подмножество больших латинских букв типа char. И здесь можно было сократить объявление переменных shem и ktovet до двух или даже одного этапа. Переменные shem(имя) и ktovet(адрес) есть множества букв, участвующих в некотором имени и некотором адресе соответственно.

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

const otiyot = [A .. Z];

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

Если же хотят изменять значение постоянной в Турбо Паскале, нужно определить типизированную константу (type constant), как показано в примерах ниже:

type otiyot = set of A .. Z;

const

tnuot: otiyot = [A, E, I, O, U]; {1, tnuot - гласные}

sifrot_hexa: set of 0 .. z = [0 .. 9, A ..F, a .. f]; {2, sifrot hexa - 16-ные цифры}

В строке {1} определено множество tnuot как некое подмножество множества otiyot.

В строке {2} мы одновременно указали множество и определили его подмножество.

В Турбо Паскале наибольшее число элементов, которое может содержаться в множестве, равно 255.

13.2.2.Построение множеств

Построение множества есть подстановка значения в переменную-множество. Элементы множества записываются в квадратных скобках справа от знака присвоения. Если часть элементов множества принадлежат подножеству базисного типа от Х до У, то можно использовать обозначение Х .. У . Пример(yom - день, rishon - первый (день - воскресенье), sheni - второй(понедельник), shlishi, riviey,chamishi, shishi - третий - шестой(вторник - пятница), shabat - суббота, kvutzat yamim - множество дней(недели), yemai chol - будние дни, sof shavua - конец недели, yemai misrad - приемные дни(дни конторы)):

type

yom = (rishon, sheni, shlishi, riviey,chamishi, shishi, shabat);

kvutzat_yamim = set of yom;

var yemai_chol, sof_ shavua, yemai_misrad: kvtzat_yamim;

Команды подстановки начальных значений в переменные - множества:

yemai_chol := [rishon, sheni, shlishi, riviey,chamishi]; {I}

sof_shavua := [shishi, shabat]; {II}

yemai_misrad := [sheni, succ(sheni)]; {III}

Команду присвоения {I} можно сократить, записав: yemai_chol := [rishon .. chamishi]; Примечание. В Турбо Паскале можно заменять квадратные скобки [ и ] на круглые ( и ), соответственно.

Команду {II} можно записать в виде подобласти, но в этом случае экономии нет.

Команда {III} демонстрирует тот факт, что элементы множества могут появляться в арифметических выражениях или в функциях до тех пор, пока их конечное значение принадлежит базисному типу. Еще один пример тому можно увидеть далее:

var

otiyot: set of A .. Z;

mispar_akrai: 0 .. 25; {mispar akrai - случайное число}

begin

read(mispar_akrai);

otiyot := [chr(ord(A) + mispar_akrai)];

end;

При использовании компьютера, действующего в коде ASCII, сумма кода символа A (т.е. значения ord(A)) и случайного числа от 0 до 25 даст код некоторой буквы между A и Z. Когда над этим кодом задействуется функция char, десятичный код заменится соответствующей буквой, а множество otiyot включит ее.

Пример:

var k: set of 1 .. 50;

..........................

begin

k := [i + 1 .. j, 12, i*j];

............................

Если i = 4, а j = 3, то k будет содержать значение 12.

Если i = 5, а j = 3, то k будет содержать значения 12 и 15.

Если i = 3, а j = 5, то k будет содержать значения 4, 5, 12 и 15.

 

13.3.Сравнение файлов

13.3.1.Операторы отношений и подмножества

С помощью соответствующих операторов (Operators) можно выполнять следующие действия: a).сравнение двух множеств для проверки их тождественности; b).проверку вхождения одного множества в состав другого множества; c).проверку некоторого элемента на его вхождение в определенное множество.

Ниже дается таблица этих операторов:

Оператор

Действие

(1) =

тождество двух множеств

(2) <>

неравенство двух множеств

(3) <=

множество слева от знака содержится в множестве справа от него

(4) >=

множество справа от знака содержится в множестве слева от него

(5) in

принадлежность элемента множеству

Объяснение:

a).Результатом действия операторов из таблицы является булево значение.

b).Значение булева выражения A <= B(проверка вхождения А в В) равно true, только если все элементы А принадлежат В. При выполнении этого условия А согласно математической терминологии называется подмножеством(Subset) множества В. В теории множеств такое отношение обозначается: A <= B.

c).Значение булева выражения A >= B(проверка вхождения В в А) равно true, только если все элементы В принадлежат А. При выполнении этого условия В называется подмножеством множества А .

d).Равенство или тождество множеств А и В существует, когда одновременно выполняется и A <= B, и A >= B. Т.е. каждый элемент А находится в В и наоборот.

e).При использовании оператора in левый операнд должен быть порядковым, принадлежащим базисному типу(назовем его T). Правый операнд должен быть множеством этого типа, т.е. set of T. Булево значение условия будет true, если порядковое значение слева принадлежит множеству справа, иначе - булево значение условия будет false.

Выражения A < B и A > B не определены. См. также примечание в конце стр. 312.

Например, значения условия, приведенного ниже, есть true:

a := 7

a in [1, 3..5, 7]

Можно также написать: [a] <= [1, 3..5,7], но прежнее представление условия яснее и проще. Если хотят проверить одновременно принадлежность элементов a и b (a <> b) множеству, условие можно сформулировать двумя способами:

(a) [a, b] <= [1, 3..5, 7] и (b) (a in [1, 3..5, 7]) and (b in [1, 3..5, 7])

В этом случае первое представление проще и яснее.

Множество [1, 3..5, 7] может появляться в программе без объявления заранее, в этом случае оно считается константой-множеством(Set Constant). Объявление необходимо только переменной, которая в ходе программы может представлять множество в команде присвоения, как, например, в операторе a := [1, 3..5, 7];

Пусть имеет место такое объявление var:

var k1, k2, k3, k4, k5, k6: set of 1..20;

В ходе программы с помощью команд присвоения строятся такие множества:

Имя множества

Содержимое множества

Описание множества

k1

[1..20]

Целые(натуральные) до 20

k2

[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Четные(натуральные) до 20

k3

[3, 6, 9, 12, 15, 18]

Кратные 3-м до 20

k4

[4, 8, 12, 16, 20]

Кратные 4-м до 20

k5

[5, 10, 15, 20]

Кратные 5-и до 20

k6

[6, 12, 18]

Кратные 6-и до 20

13.3.2.Отношения между множествами

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

Оператор 1 - тождество множеств.

a).Значение условия k1 = [1..10, 19, 12, 7..20] равно true. Справа в выражении условия можно писать неупорядоченные значения, а какие-то значения указывать не один раз. Это не влияет на результат поскольку важно, что любое значение от 1 до 20 указано хотя бы раз в квадратных скобках, а другие значения, выходящие за эти пределы, в перечне отсутствуют. Поэтому множество справа на самом деле тождественно k1.

b).Значение условия k1 = [20..1] равно false. Подмножество 20..1 считается пустым, поскольку его нижний предел больше верхнего.

Оператор 2 - неравенство множеств.

a).Значение условия k6 <> [0, 6, 12, 18] равно true, поскольку число 0 не содержится в базисном типе и поэтому его не может быть в k6.

b).Значение выражения k1 <> [9..20, 11, 3..11, 1, 2] равно false. Множество k1 окажется тождественным множеству справа, если в нем убрать повторения и не принимать во внимание порядок элементов.

Операторы 3, 4 - вхождение одного множества в другое.

a).Значение условия k5 <= k1 равно true. Кратные 5-и (от 5 до 20) есть подмножество множества целых от 1 до 20.

b).Значение условия k1 <= k2 равно false. Множество k1 содержит все целые от 1 до 20, а множество k2 содержит только четные числа первого множества. Обратное условие k1 >= k2 есть true, т.е. истинно.

c}.Условие [ ] >= k1 есть false. В множестве k1 имеются элементы, которых нет в пустом множестве. Если в k1 имеется хотя бы один элемент, оно не пусто, и условие не выполняется. С другой стороны условие [ ] <= k есть true для любого множества k, поскольку любой элемент, существующий в пустом множестве(на самом деле в нем нет ни одного элемента), находится и в k.

Оператор 5 - принадлежность множеству. Если целая переменная А равна 1, значение булева выражения A in k1 есть true, а значение выражения A in k2 есть false. Пусть I, J, K, N - переменные одного порядкового типа, а нужно выражение

(I = N) and (J = N) and (K = N) . Это можно сделать в краткой форме: [I, J, K] = N.

Условие (I = N) or (J = N) or (K = N) можно записать так: N in [I, J, K] .

13.3.3.Действия над множествами

В следующей программе продемонстрируем реализацию, основанную на сравнении множеств. Программа представляет реализацию алгоритма нахождения трехбуквенных слов(буквосочетаний), которые можно образовать из слова shalom (piruk mila - разложение слова, ot rishona - первая буква, ot achrona - последняя буква, revach - пробел, milim beshura - слов в строке, mispar milim - число слов).

program piruk_mila; {1}

const {2}

ot_rishona = 'a'; {3}

ot_achrona = 's'; {4}

revach = ' '; {5}

milim_beshura = 15; {6}

type {7}

otiyot = ot_rishona..ot_achrona; {8}

var {9}

ot1,ot2,ot3: otiyot; {10}

mila, mila_lepiruk: set of otiyot; {11}

mispar_milim: 1..milim_beshura; {12}

begin {13}

mila_lepiruk := ['s','h','a','l','o','m']; {14}

mispar_milim := 1; {15}

for ot1 := ot_rishona to ot_achrona do {16}

for ot2 := ot_rishona to ot_achrona do {17}

if ot1 <> ot2 then {18}

for ot3 := ot_rishona to ot_achrona do {19}

if not(ot3 in [ot1, ot2]) then {20}

begin {21}

mila := [ot1, ot2, ot3]; {22}

if mila <= mila_lepiruk then {23}

begin {24}

write(ot1, ot2, ot3, revach); {25}

if mispar_milim = milim_beshura then {26}

begin {27}

writeln; {28}

mispar_milim := 1 {29}

end {30}

else {31}

mispar_milim := mispar_milim + 1 {32}

end {33}

end {34}

end. {35}

Объяснение . Программа последовательно пробегает по всем тройкам букв, которые можно составить из латинских букв от a до s, и устанавливает те из них, которые содержатся в слове shalom. При положительном ответе относительно некоторой тройки программа печатает ее. Таким образом извлекаются все трехбуквенные перестановки из 6 букв, составляющих проверяемое слово: s, h, a, l, o, m. Общее число возможных перестановок равно 654 = 120. Это можно видеть на выводе программы:

ahl

ahm

aho

ahs

alh

alm

alo

als

amh

aml

amo

ams

aoh

aol

aom

aos

ash

asl

asm

aso

hal

ham

hao

has

hla

hlm

hlo

hls

hma

hml

hmo

hms

hoa

hol

hom

hos

hsa

hsl

hsm

hso

lah

lam

lao

las

lha

lhm

lho

lhs

lma

lmh

lmo

lms

loa

loh

lom

los

lsa

lsh

lsm

lso

mah

mal

mao

mas

mha

mhl

mho

mhs

mla

mlh

mlo

mls

moa

moh

mol

mos

msa

msh

msl

mso

oah

oal

oam

oas

oha

ohl

ohm

ohs

ola

olh

olm

ols

oma

omh

oml

oms

osa

osh

osl

osm

sah

sal

sam

sao

sha

shl

shm

sho

sla

slh

slm

slo

sma

smh

sml

smo

soa

soh

sol

som

{1}Имя программы piruk_mila указывает на то, что она разбирает слово на различные сочетания.

{3-4}Придание имен первой и последней буквам проверяемого слова shalom согласно латинскому алфавиту. Поэтому ot_achrona равна s, поскольку эта буква слова стоит на последнем месте в латинском алфавите из всех букв слова shalom. Задание буквы s в качестве ot_achrona избавляет программу от проверок тех троек, в которых хотя бы одна буква находится в латинском алфавите после s. Если бы нужно было выделять сочетания из слова, в котором первая по алфавиту буква была e, а последняя, к примеру, y, нам пришлось бы соответственно изменить значения ot_rishona и ot_achrona.

{6}Мы хотим, чтобы в каждой строчке печаталось по 15 буквосочетаний. Каждое слово использует по 4 позиции: три для букв самой тройки и одну для разделяющего пробела. Переменная milim_beshura устанавливает верхний предел числу слов, выводимых в каждой строчке.

{16-22}В этих строках образуются все тройки букв латинского алфавита, которые отвечают двум следующим условиям: a).все буквы - разные; b).буквы, составляющие тройку, в алфавите располагаются между ot_rishona и ot_achrona.

Уже говорилось, что значения ot_rishona и ot_achrona меняются соответственно буквам, входящим в состав проверяемого слова. Если слово содержит некоторую букву больше одного раза, программа все-таки будет образовывать тройки, содержащие ее только один раз.

{23}Проверка: является ли созданная тройка подмножеством исходного разлагаемого слова.

{26-32}Проверка числа слов в печатаемой строчке. Если оно оказывается равным установленному заранее пределу, надо перейти к новой строке.

 

13.4. Алгебра множеств

Возможно исполнение трех разных алгебраических действий над парами множеств. a).Объединение множеств(Set Union). В теории множеств объединение множеств (см. чертеж - рис. 1) обозначают A B. На языке Паскаль такое объединение будем обозначать A + B. Результатом объединения двух множеств A и B является множество, содержащее все элементы, которые находятся в А, в В или в них обоих. Представим это на схеме, которая называется диаграммой Вэна (Venn Diagram).

Из чертежа видно, что выполняется: A B = B A . Выражение A B = A - верно, если В является подмножеством А. Условие X in (A B) проверяет, принадлежит ли Х объединению множеств А и В, т.е. находится ли он в А , в В или в них обоих. Такая принадлежность проверяется также булевым выражением (X in A) or (X in B).

b).Пересечение множеств(Set Intersection). В теории множеств пересечение множеств (см. чертеж - рис. 2) обозначают так: A B. На языке Паскаль будем обозначать пересечение с помощью A*B. Результатом пересечения двух множеств A и B является множество, содержащее только элементы, общие для А и В. Т.е. элемент принадлежит пересечению A B, если он принадлежит и А и В. Схематическое описание пересечения представлено на указанном чертеже. Из него следует выполнение равенства: A B = B A . Также выполняется A B = B, если В является подмножеством А . Если через обозначить пустое множество, получим A B = только, если множества не пересекаются. У непересекающихся множеств (Mutually Exclusive Sets) нет ни одного общего элемента. Описание непересекающихся множеств дано на чертеже(Рис. 3). Условие X in (A*B) проверяет, находится ли Х одновременно в А и В. Эта проверка равносильна условию (X in A) and (X in B).

c).Разность(вычитание) множеств(Set Difference). В теории множеств и в Паскале операция разности множеств обозначается минусом(-). Разность (или относительное дополнение) множеств А и В есть множество, содержащее все элементы А, которых нет в В. Схематическое описание разности множеств А и В представлено на чертеже(рис. 4). Из чертежа можно сделать такие заключения:

А-В не равно В-А. Это возможно только, если А = В, и тогда получается, что А-В = В-А = .

А-В = А, если В = или A B = . В другой формулировке: А-В равно А , если А и В не пересекаются.

А-В = , если A <= B. Выражение A <= B содержит и случай А=В.

Булево выражение X in (A - B) равносильно условию (X in A) and not (X in B).

13.4.1.Применения алгебры множеств

Для разъяснения темы алгебры множеств воспользуемся примером определения множеств k1, k2, ..., k6 из предыдущего параграфа. Это множества чисел от 1 до 20, которые делятся, соответственно на 1, 2, 3, 4, 5, 6.

a).k2 k3 это множество всех целых от 1 до 20, которые делятся на 2, на 3 или на 2 и 3 вместе. Поэтому k2 + k3 = [2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20].

b).k2 + k6 = k2, т.к. k6 <= k2. Поэтому k2 + k6 = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20].

c).k2 можно построить с помощью операции объединения:

k2 := []; (*пустое множество*)

for i := 1 to 20 do

if not odd(i) then k2 := k2 + [i];

d).k2 k3 это множество целых чисел от 1 до 20, которые делятся и на 2 и на 3 одновременно. Оно тождественно множеству k6, т.к. число, которое делится и на 2 и на 3, делится также на 6. Т.е. k2*k3 = k6. Поэтому можно построить множество k6 с помощью команды присвоения k6 := k2*k3; .

e).k3 k6 это множество целых чисел от 1 до 20, которые делятся и на 3 и на 6 одновременно. Оно тождественно множеству k6, т.е. k2*k3 = k6, т.к. k6 <= k3.

f).k4 k6 это множество целых чисел от 1 до 20, которые делятся и на 4, и на 6. Поэтому k4*k6 = [12]; .

g).k5 k6 это множество целых чисел от 1 до 20, которые делятся и на 5, и на 6. Это - пустое множество, т.е. k5 k6 = , т.к. наименьшее целое, делящееся и на 5, и на 6, равно 30. Запишем это так: k5*k6 = [] .

h).k1 - k2 это множество целых от 1 до 20, которые не делятся на 2, т.е. это - нечетные числа. Поэтому k1 - k2 = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]. Это множество можно построить так:

k2 := k1;

for i := 1 to 20 do

if not odd(i) then k2 := k2 - [i];

i).k2 - k1 = [], т.к. дано, что k2 <= k1.

j).Множество k6 - k5 содержит целые от 1 до 20, которые делятся на 6, но не на 5. Поскольку k6 k5 = , получим k6 - k5 = k6.

Предположим, что в программе piruk_mila, которой мы занимались в предыдущем параграфе, надо образовывать тройки, которые содержат хотя бы одну гласную(Vowel). Для этого нужно, объявив переменную - множество tnuot: set of a..z;

,написать в программе такую команду присвоения: tnuot := [a, e, i, o, u, y].

А перед печатью тройки расширить булево условие в строке {23}:

(mila <= mila_lepiruk) and (mila * tnuot <> [])

В этом расширенном условии содержится требование, чтобы mila было подмножеством mila_lepiruk и одновременно содержало хотя бы одну гласную.

 

13.5.Иерархия операций

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

not

and mod div / *

- +

>= <= <> = in > <

Представим два примера по таблице множеств k1, k2, ..., k6 из параграфа 13.3.1:

a).Множество всех нечетных чисел от 1 до 20, делящихся на 3, запишем так: (k1 -k2)*k3. А не так: k1 - k2*k3. Иерархия пересечения выше, чем у разности, поэтому второе выражение приводит к множеству разности между: множеством целых чисел в интервале 1..20; множеством пересечения целых чисел от 1 до 20, которые делятся и на 2, и на 3. Два указанных выражения дают различные результаты:

(k1 - k2)*k3 = [3, 9, 15]; k1 - k2*k3 = [1,2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20].

b).Множество целых от 1 до 20, которые не делятся ни на 3, ни на 5, дают выражения: k1 - (k3 + k5) или k1 - k3 - k5.

Примечание. Множество k1 называется действительным подмножеством(Proper Subset) множества k2, если k1 <= k2 и при этом k1 <> k2. В Паскале нельзя оценить указанное состояние прямо, например, с помощью записи k1 < k2. Причина этого ограничения состоит в том, что указанная проверка нагружает компилятор непропорционально по отношению к частоте ее использования. Когда хотят проверить или оценить это состояние, нужно использовать булево условие (k1 <= k2)*(k1*k2).

 

13.6.Ввод/вывод множеств

В языке Паскаль нельзя прямо вводить/выводить множество, нужно читать или писать его элементы отдельно, один за другим. Чтобы, например, получить печать всех элементов множества А, нельзя написать write(A); .

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

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

Теперь представим два каркаса программ со сканированием и поиском в множествах. Мы займемся типичным случаем, когда базисный тип есть подобласть типов integer или char. В разделе объявлений программы напишем(gvul tachton - нижний предел, gvul elyon - верхний предел, tat tvach - подобласть, sug kevutzati - множественный тип, kevutza - множество, tipul kevutza - обслуживание множества):

const

gvul_tachton = ... ;

gvul_elyon = ... ;

type

tat_tvach = gvul_tachton..gvul_elyon;

sug_kevutzati = set of tat_tvach;

var kevutza: sug_kevutzati;

Сканирование. Сканирование осуществляется, если хотят задействовать повторяющуюся процедуру над каждым элементом множества. Для этого воспользуемся такой процедурой:

procedure tipul_kevutza(k: sug_kevutzati);

var i: tat_tvach;

begin

for i := gvul_tachton to gvul_elyon do

if i in k then process(i)

end;

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

если речь идет о печати элемента множества, можно заменить process(i) на команду write(i:2);

чтобы установить число элементов в множестве, надо заменить process(i) на команду godel := godel + 1 , где godel(величина) должен быть переменным(var) параметром процедуры tipul_kevutza. Другая возможность заключается в превращении нашей процедуры в целую функцию, которая принимает переменную - множество k и возвращает его размер.

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

Поиск.Этой функцией пользуемся для поиска одного определенного элемента. Поиск завершается при локализации элемента, сканирование оставшихся элементов множества не производится(chipus- поиск, nimtza - присутствует, nigmar - закончено).

function chipus(k: sug_kevutzati): tat_tvach; {1}

var {2}

i: tat_tvach; {3}

nimtza, nigmar: boolean; {4}

begin {5}

nimtza := false; {6}

nigmar := false; {7}

i := gvul_tachton; {8}

while not nigmar and not nimtza do {9}

if (i in k) and tnai(i) then {10}

begin {11}

chipus := i; {12}

nimtza := true {13}

end {14}

else {15}

if i < gvul_elyon then i := succ(i) {16/7}

else nigmar := true; {18/9}

if not nimtza then writeln('Takogo elementa net') {20/1}

end; {22}

Объяснение:

{9}При просмотре всего множества мы пользовались циклом

for i := gvul_tachton to gvul_elyon do

Здесь мы используем цикл while ... do , который позволяет ранний выход из него, когда nimtza принимает значение true.

{10}Выражение tnai(i) будет заменено требованием, устанавливающим, какой элемент мы хотим локализовать. Если ищем наименьшее числовое значение в множестве, то tnai(i) не требуется, достаточно написать if i in k . Цикл завершится при нахождении в подмножестве первого элемента, принадлежащего k. Если ищем наибольшее числовое значение в множестве, то начинаем цикл при подстановке i := gvul_elyon в строке {8}, а в строке {17} пишем i = pred(i) .

В обоих случаях сканирования множества и поиска элемента в множестве желательно добавлять команду, которая указана ниже, чтобы предотвратить излишнюю обработку. Если k - пустое множество, цикл не исполняется и печатается сообщение:

if k = [] then writeln('Mnojestvo pusto')

else (* Ostal"nie komandi funkcii' *)

 

13.7.Применения множеств

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

13.7.1.Сито Eratosthenesа (*)

Цель следующей программы состоит в нахождении простых чисел по методу, который называется сито Eratosthenesа(The Sieve of Eratosthenes). N есть простое число, если его нельзя представить в виде произведения пары целых чисел, кроме как 1 и N.

Для нахождения простых чисел по названному методу используют два множества. Множество muamadim(кандидаты) содержит все целые числа от 2 до 64(подобласть целых чисел), из которых будем выбирать простые. В начальном положении все числа указанной подобласти принадлежат этому множеству. Множество rishonim (простые) будет содержать все найденные простые числа. В начальном положении до получения каких-либо результатов это множество должно быть пустым.

В ходе программы просматриваются числа в muamadim и найденные простые передаются в rishonim. Остальные числа, которые не являются простыми, удаляются из множества muamadim. В конце программы множество rishonim будет содержать все простые числа от 2 до 64, а множество muamadim станет пустым, т.к. простые числа из него были переданы в rishonim, а остальные - удалены.

Программа, которая действует по этому методу, дается ниже(tachton - нижний, elyon - верхний, kevutzat shlemim - множество целых, ktov kevutza - напечатай множество, rishon - простое):

program misparim_rishonim; {1}

const {2}

tachton = 2; {3}

elyon = 64; {4}

type kevutzat_shlemim = set of tachton..elyon; {5/6}

var {7}

muamadim, rishonim: kevutzat_shlemim; {8}

i, j: integer; {9}

procedure ktov_kevutza(k: kevutzat_shlemim); {10}

var {11}

rishon: boolean; {12}

i: tachton..elyon; {13}

begin (* ktov_kevutza *) {14}

write('['); {15}

rishon := true; {16}

for i := tachton to elyon do {17}

if i in k then {18}

begin (* Kogda RISHON = FALSE, pechtaem zap"atuu pered chislom *) {19}

if not rishon then write(',') {20/1}

else rishon := false; (*inache zap"atuu ne pishem,*) {22}

(*a prevrashaem znachenie RISHON v FALSE*) {23}

write(i) {24}

end; {25}

writeln(']') {26}

end; (* ktov_kevutza *) {27}

begin (* Glavna"a programma *) {28}

muamadim := [tachton..elyon]; {29}

rishonim := []; {30}

i := tachton; {31}

while muamadim <> [] do (* Naidi sleduushee prostoe chislo *) {32}

begin {33}

while not (i in muamadim) do i:=i+1;(*Naidi naimenshee v MUAMADIM*){34/5}

rishonim := rishonim + [i]; {36}

j := i; {37}

while j <= elyon do (*Udali ego i kratnie emu*) {38}

begin {39}

muamadim := muamadim - [j]; {40}

j := j + i; {41}

end {42}

end; {43}

write('RISHONIM = '); {44}

ktov_kevutza(rishonim) {45}

end. (* Glavna"a programma *) {46}

Вывод программы: RISHONIM = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61]

Объяснение:

{32}По ходу программы одно за другим извлекаются все числа из множества кандидатов. Если они простые, то переносятся в множество rishonim, а иначе - они удаляются. Процесс прекращается, когда