    ИЕРАРХИЯ СТРУКТУР ДАННЫХ 283 

    18. Иерархия структур данных при разработке программ 

    При ретпгмии практических задач обычно не удается обойтись ||ддцми лишь 
стандартными структурами данных (стек, дек, очередь, список и т, д.), 
перечисленными в разд. 7. Реализация достаточно сложных исполнителей требует 
_введення_ структур данных, максимально отражающих существо выполняемой 
исполнителем задачи,,. Такие специальные структуры данных обычно оформляются 
как вспомогательные исполнители и разрабатываются по техноло-ига «сверху 
вниз», В этом разделе мы реализуем структуру данных, естественно возникающую 
при реализации текстового редактора, 
    При работе на ЭВМ недостаточно уметь записывать информа» пню п файл и 
читать ее из файла. Очень часто возникает задача 1нч)актированая (т. е, 
изменения) текстового файла. Эта задача пЛычпп решается человеком с помощью 
специальной программы—• акряшюто текстового редактора. Хотя к этому моменту 
Вы, на-иерное, достаточно поработали за терминалом и представляете rrflo 
внешний вид и возможности такого редактора, опишем его исконные черты, 
    Мри работе человека с редактором на экране с помощью спе-цшгЛЫюА отметки 
(А-///"'"/"') нлобрпжпетРя некоторое положение ч тексте и умгшштцпиш па экране 
окрестность текста вокруг этого положении (назовем со окном). Набор 
стандартных операций редактирования включает, в частности, вставку, удаление, 
изменение символов и строк. Перемещая курсор по тексту и изменяя текст ними 
курсора, можно внести в текст любые желаемые изменения, 
    Снимемся реализацией структуры данных, соответствующей тексту с отмеченным 
положением и изображаемым окном, т. е, pea-лтугм некоторую чисть якршшого 
токстопого редактора. Для про-«'ТОТМ И» вудем pmTMMipiiiian. операции 
изменения строки и гори» ионтйльмы» перемещения курсора, а ограничимся только 
работой по прртикяли— будем считать отроки элементарными неделимыми оЛьсктлми 
и интересоваться только вертикальной компонентой положении курсора. Удобной и 
отвечающей представлениям человека о тгкгге структурой является список строк — 
вертикальной компонент положения курсора соответствует положение указателя, в 
риПоио указателя можно вставлять и удалять строки. Существуют, «прочем, и 
отличия текста от обычного списка: в тексте должна оыть пыделена постоянно 
изображаемая на экране терминала пкрегпюсть указателя (окно); в начале работы 
текст должен со-дрржнть информацию из изменяемого файла; после окончания 
ра-Лоты новый текст должен записываться куда-то на диск и т. п. 
    Реализованная нами простейшая файловая система (как, впро-яем, и почти все 
«настоящие» файловые системы) не позволяет 

    284 гл. з. СТРУКТУРЫ ДАННЫХ и их РЕАЛИЗАЦИИ 

    вставлять и удалять строки в середине файла. Таким образом, структуру 
текста строк с изображаемым окном и указателем надо как-то реализовывать над 
другими структурами данных и испол» кителями. Среди этих структур и 
исполнителей кроме файловой системы можно сразу выделить исполнителя «Экран», 
который должен попавшие в окно строки текста каким-то образом изобра-жатТГп'а 
экране терминал.а. 
    Мы будем считать, что исполнитель «Экран» с внешней точки )рения является 
вектором элементов типа строка о индексом от О до макс Уэкрана, где 
строки-элементы вектора соответствуют строкам, изображаемым на экране 
терминала. Например, чтобы изменить верхнюю строку на экране терминала, надо 
изменить элемент вектора с индексом 0, а чтобы узнать состояние последней 
(нижней) строки экрана, надо проанализировать элемент вектора с индексом макс 
Тэкрана. Реализация исполнителя «Экран» зависит от конкретной ЭбМ и от 
конкретного терминала. На персональных ЭВМ> например, на экране обычно 
изображается содержимое некоторого фиксированного участка оперативной памяти 
(этот участок называется видеопамятью) 
    . Реализация исполнителя «Экран» при этом сводится к преобразованию 
действий над строками в дей* ствия над соответствующими фрагментами 
видеопамяти. Мы будем считать исполнителя «Экран» базовым и реализовывать его 
на будем. 
    Итак, пусть стоит задача реализовать исполнителя «Текст строк с 
изображаемым окном и указателем» со следующей системой предписаний: 
    исполнитель Текст строк с изображаемым окном и указателем 
    . СП: 
    .      1. начать работу (вх : ф: ключ) 
    2. установить указатель и окно в начало текста .     3. установить 
указатель и окно в конец текста 
    4. указатель в начале текста      : да/нет 
    5. указатель в конце текста        : да/нет .     6. передвинуть указатель 
назад возможно с окном .     —      роллировать вниз (вх : il,i2 : 0. .макс Уэкрана) 
    7. передвинуть указатель вперед возможно с окном .     —      роллировать 
вверх (вх : il,i2 :0. .макс Уэкрана) 
    8. добавить строку (вх : С : строка) за указателем 
    9. удалить строку за указателем 
    10. строка за указателем :: строка 
    11. Уокна максимальное    :0..макс Уэкрана 
    12. получить положение указателя и окна в (вых: Утекста, Уокна) .   13. 
установить указатель и окно в положение (вх:Утекста,Уокна) 
    14. кончить работу аварийно (вых: ф: ключ) 16. кончить работу (вых : ф : ключ) 
    18. ИЕРАРХИЯ СТРУКТУР ДАННЫХ 283 
    Прглпнсииня 2—10 . образуют, ^ли__можно так выразиться, •Л1.5 пик'ок» — 
возможности по установке и перемещению указа-ТРЛИ смшадают с возможностями 
Л2-списка, однако все действия иршшдятся только за указателем, как в 
Л1-списке. Предписаний, деляющнх список пустым и проверяющих пустоту или 
непустоту, нет imiico. Предписания «роллировать вверх»/«роллировать вниз» 
ИНЛиются локальными и будут объяснены ниже. При попытке о Помощью предписания 
6 или 7 вывести указатель за пределы окна икно смещается в соответствующем 
направлении на ,рдну строку, чгпбы новое положение указателя оказалось в новом 
окне. Таким ивразом, можно представлять себе текст в виде 
    строка 1 
    строка 2 
    ... 
    строка п 
    1 -»	строка п + 1	окно 
    строка п + 2 
    .   строил in 
    строил in 1 1 
    строка m + 2 
    строка k 
    [• конец текста •] 
    НДРСЬ тс-кст состоит из к строк, окно содержит строки с И 4- I ft по пью, 
указатель расположен между строками п -f- 1 и И I '1. 
    Обратите внимание на так называемую холостую строку ниже 'e. Уго строка не 
входит в текст. Дело в том, что, хотя ука

    286 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ   И   ИХ   РЕАЛИЗАЦИИ 

    затель располагается между строками, на экране он изображается в виде 
курсора (заштрихованного прямоугольника) в строке под указателем. Поскольку 
возможных положений указателя на 1 больше, чем строк в тексте, то положение 
указателя после последней Строки текста изображается курсором в следующей за 
ней строке экрана. Чтобы отличить эту строку о* строк текста, изобразим в ней 
текст «[* конец текста *]». Таким образом, возможно, например, следующее 
положение окна и указателя: 

    указатель 
    строка 1 
    строка 2 
    строка j 
    строка j 4- 1	OK 
    строка J + 2 
    
    
    строка k 
    [* конец текста *] 
    »екст 

    Обратите внимание на то, что границы окна, как и положение указателя, 
всегда располагаются между строками текста. 
    Предписание «Уокна максимальное» вырабатывает в качестве значения .тищцее 
число строк в окне без единицы. Мы будем хранить это" число"ТТлобальном 
объекте' макс Уокна. j3Lmo6in,eM случае макс Уокна совпадает с константой макс 
Уэкрана, Однако в пустом файла, например," макс Уокна будет равно нулю, что 
означает, что в окне находится только одна строка — холостая. Утекста в 
предписаниях получения/установки положения указателя и окна — это число строк 
текста над указателем, Уокна — это число строк PKHJ над указателем. На 
изображенной выше картинке Утекста = k, Уокна = макс, Уокн'а -» k — J. На 
предыдущей картинке Утекс/га «= п + 1, Уокна =« 1, а макс Уокна = m — п — 1, 
    Наконец, кончить работу с исполнителем «Текст» можно двояко — аварийно и 
нормально. При аварийном окончании все внесенные человеком изменения 
аннулируются, исходный текст остается нетронутым и в выходном параметре 
возвращается ключ файла, 

    18. ИЕРАРХИЯ СТРУКТУР ДАННЫХ 28? 

    содержащего исходный нетронутый текст. При нормальном окончании новый 
измененный текст запоминается в некотором файле на диске, старый файл 
уничтожается, а в выходном параметре воз« вращается ключ файла с новым текстом. 
    .   константы: 
    •    число строк на экране = 24 
    .    макс Уэкрана	= число строк на экране — I .    макс длина строки.      
 =132 [символа 
    . типы: 
    .    ключ   = ...	. 
    .   строка = запись (длина: О..макс длина строки, 
    текст: вектор символ П..макс длина строки)) 
    . объекты: 
    .   макс Уокна : —1. .макс Уэкрана   |—1— когда в окне нет ничего, 
    (даже холостой строки .    Уокна	:0..макс Уэкрана      (точнее О..макс Уокна 
    . используемые  исполнители: 
    .    Экран: вектор строка (О..макс Уэкрана), 
    .   Верхний стек, Нижний стек, 
    .   Простейшая файловая система (ФС) 
    конец описаний |
    Идеи реализации. Прежде всего заметим, что редактор дол« жен уметь 
редактировать любые файлы, в том числе и те, размеры которых превышают размеры 
памяти. Таким образом, простейшее решение — реализовать весь текст целиком в 
.памяти, в начале работы считывать в память текст из исходного файла, а и 
конце работы новый текст из памяти записывать в файл на диск — не проходит. 
Поэтому будем действовать по технологии «сверху вниз» — реализуем искомую 
структуру над удобными промежуточными, далее реализуем эти промежуточные 
структуры и т. д., пока не дойдем до базовых. 
    На первом шаге декомпозиции реализуем Текст на базе исполнителей «Нижний 
стек», «Экран» и «Верхний стек» таким образом, что расположенные над окном 
строки текста будут храниться в исполнителе «Верхний стек», строки окна — в 
исполнителе •«Экран», а строки ниже окна — в исполнителе «Нижний стек»: 

    288	ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И ИХ   РЕАЛИЗАЦИЙ 
    
    строка 1 
    строка 2 
    
    
    строка п 
    
    
    указатель 
    Верхний стек 
    -»	строка п + 1	ок 
    строка п + 2 
    ... 
    строка m 
    
    
    строка m + 1 
    строка m + 2 
    
    
    строка k                    ^ 
    1* конец текста »] 
   
    Нижней 

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

    18. ИЕРАРХИЯ СТРУКТУР ДАННЫХ	289 

    чтобы предписание «кончить работу» нижнего стека возвращало ключ исходного 
файла, а «кончить работу» верхнего ч- ключ нового файла, 
    Окно, естественно, может иногда занимать не весь экран, В этом случае (при 
макс 'Уокна < макс Уэкрана) будем размещать строки окна в верхней части экрана: 

    строка J + I 
    строка j + 2 
    строка k 
    [» конец текста •] 
    лкран 

    Мы реализуем исполнителя «Текст» так, что после вызова Сого предписания 
Текста извне этого исполнителя будет выполнено 
    следующее условие (инвариант исполнителя):	,*.-     ; "?" 
    если макс Уокна < макс Уэкрана то Нижний стек.пуст 
    т»  е.  если  нижний  стек  не  пуст,  то окно  полно   (занимает весь 
    •кран). 
    Поскольку положение указателя изображается курсором в строке под 
указателем, то реализуем Текст так, что указатель никогда не будет расположен 
за последней строкой окна. Иными словами, 
    О «^ Уокна ^ макс Уокна = число строк окна — 1. 
    программа начать работу (вх:ф!ключ) 
    • дано       ; 
    • Получить!   указатель в начале текста |а окно имеет максимально .	| 
возможные размеры и прижато к верхнему Краю ,                       |текста 
    Нижний стек.начать работу (вх:ф1ключ) 
    Экран.начать работу 
    Верхний стек.начать работу 
    макс Уокна := —1 
    цикл пока Нижний стек.не пуст и макс Уокна < мако Уэкрана 
    .   выполнять 
    .     макс Уокна.увеличить на I 


    10 А. Г. Кушниренко, Г. В. Лебедев 
    290 гл. з. СТРУКТУРЫ ДАННЫХ и их РЕАЛИЗАЦИИ 
    8. ИЕРАРХИЯ СТРУКТУР ДАННЫХ 291 


    .   .     Нижний стек.взять строку в (вых : Экран (макс Уокиа)) ,   конец 
цикла .   Уокна := О конец программы 
    После  выполнения  этой  программы  макс Уокна  окажется  vtj 
отрицательным, так как цикл хотя бы один раз выполнится: даже jgpjB пустом 
тексте нижний стек содержит холостую строку и, "значит, не пуст. программа 
установить указатель и окно в начало текста 
    . дано        : 
    . получить: указатель в начале текста 
    .   цикл пока указатель не в начале текста выполнять 
    .   .    передвинуть указатель назад возможно с окном 
    ,   конец цикла 
    конец программы 
    программа установить указатель и окно в конец текста 
    . дано        5 
    . получить: указатель в конце текста 
    »    — -
    «   цикл пока указатель не в конце текста выполнять ,   .     передвинуть 
указатель вперед возможно с окном .   конец цикла коиец программы 
    программа указатель в начале текста  : да/нет == 
    (Верхний стек.пуст и Уокна = 0) программа указатель в конце текста: да/нет == 
    (Нижний стек.пуст и Уокна = макс Уокна) программа передвинуть указатель 
назад возможно с окном , дано        : указатель не в начале текста . получить: 
    •     ^ —* ""• ~~ <"— "~ ~~ ~~ 
    .	если Уокна > 0 то Уокна.уменьшить на 1 иначе 
    .	.    если макс Уокна < макс Уэкрана то 
    .	.     .    макс Уокна.увеличить на 1 
    .	,     .   иначе 
    .	.    .     Нижний стек, добавить строку (вх: Экран (макс Уокна)} 
    .    .     конец если 
    .    .    роллировать вниз (0,макс Уокна) 
    .   .    Верхний стек.взять строку в (вых: Экран (0)) 
    .    конец если 
    конец программы 
    Мы воспользовались здесь локальным предписанием «роллировать вниз {вх:П, 
12>», которое сдвигает вниз на одну строку, все Строки окна С il-й по 12-ю 
включительно. При этод. самая нижняя Строка— строка с номером iz— пропадает, 
верхняя строка — стро ка с номером П—становится пустой, а строки с номерами 
вне диапазона П. ,12 не изменяются, например 
    До роллнроаания: 

    После роллировакия: 
    строка А 
    строка В 
    строка С 
    строка D 
    строка Е 
    строка F 
    строка А 
    строка В 
    строка С 
    строка D 
    строка 
    (при П = 12 это просто очистка строки), 

    программа роллировать вниз (вх: 11,12 i 0. .макс Уэкрана} , дано       :   
И < I? 
    . получить: [строки окна в диапазоне П..12 сдвинуты на одну ,	| строку 
вниз. Старая строка с номером 12 пропаЛа, . (новая строка с номером 11 пуста 
    .   цикл V 1 е 11 + I.,i2 реверс выполнять 
    ,   .     Экран (1) := Экран (1 — 1) ,   конец цикла ,    Экран (il).длина 
:= О Конец программы 
    Программа передвинуть указатель вперед возможно с окной , дано        : 
указатель не в конце -текста i получить; 
    .   если Уокна < макс Уокна то Уокна.увеличить на 1 ичач* 
    ,   .     Верхний стек.добавить строку (вх i Экран (0)) 
    ,    .     роллировать вверх (0, макс Уокна) 
    ,   .    Нижний стек.взять строку в (вых; Экран (макс Уокна)} 
    ,   конец если 
    конец программы 

    10* 
    292 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И  ИХ  РЕАЛИЗАЦИИ 

    Программа «роллировать вверх» действует аналогично программе «роллировать 
вниз», но сдвигает строки с 11-й по 12-ю включительно на одну строку вверх. 
При этом старая строка с но« мерой П пропадает, а новая строка о номером 12 
становится пустой: 
    программа роллировать вверх (вх: 11,12:0..макс Уэкрана) 
    . дано        :   11 <| i2 
    , получать: | строки окна в диапазоне 11.. 12 сдвинуты на одну 
    .	(строку вверх. Старая строка с номером 11 пропала, 
    .	| новая строка с номером 12 пуста 
    .   цикл V 1 е 11.Л? —1 выполнять 
    .   .     Экран (1) := Экран (1+1) 
    .   конец цикла 
    .   Экран (12). длина := О 
    конец программы 
    программа добавить строку (вх: С : строка) за указателем , дано       : . получить; 
    .	если макс Уокна = макс Уэкрана то 
    .	.    Нижний стек.добавить строку (вх: Экран (макс Уокна)) 
    .	.   иначе 
    .	.    макс Уокна.увеличить на 1 
    .	конец если 
    .	роллировать вниз (Уокна, макс Уокна) 
    .	Экран (Уокна) :*=• С 
    конец программы 
    программа удалить строку за указателем . дано : указатель не в конце 
текста . получить: 
    .	роллировать вверх {Уокна, макс Уокна) 
    .	если Нижний стек.не пуст то 
    .	.    Нижний стек.взять строку в (вых: Экран (макс Уокна)) 
    .	.   иначе 
    .	.    макс Уокна.уменьшить на 1 
    .	конец если 
    конец программы 
    программа строка за указателем :: строка « дано       : указатель не в 
конце текста 


    18. ИЕРАРХИЯ СТРУКТУР ДАННЫХ 293 


    . получить: 
    .   ответ *==• Экран (Уокна) конец  программы 
    программа Уокна максимальное :0..макс Уэкрана == макс Уокна 
    программа получить положение указателя и окна в (Утекста, Уо) . дано       
 : . получить: 
    ,    Утекста := Верхний стек.число строк + Уокна 
    (    Уо	:«= Уокна 
    конец программы	. 
    программа установить указатель и окно в положение (Утекста,Уо) i дано      
  : . получить: 
    .	dY := Утекста—Уо—Верхний стек.число строк 
    .	выбор 
    .	.   при dY > о *=*• 
    .	.           цикл dY раз выполнять 
    .	.            .     передвинуть указатель вперед возможно с окном 
    .	.           конец цикла 
    .	.   при dY < О =*• 
    .	.           цикл — dY раз выполнять 
    .	.           .     передвинуть указатель назад возможно О окном 
    .	.           конец цикла 
    .	конец выбора 
    .	утв: Утекста—Уо=Верхний стек.число строк и Уо ^мако Уокна 
    ,	Уокна := Уо 
    конец программы 
    программа кончить работу аварийно (вых!ф!ключ) 
    . дано        : 
    . получить: | ф — ключ старого нетронутого файла 
    .   Верхний стек.кончить работу (вых: фв: ключ) 
    .    ФС.удалить файл (вх:фв) 
    .    Экран.кончить работу 
    .   Нижний стек.кончить работу (вых! ф:ключ) 
    конец  программы 
    программа кончить работу (вых:ф: ключ) 
    . дано       : 
    , получить: | ф — ключ нового изменного файла 


    294 ГЛ. 3. СТРУКТУРЫ ДАННЫХ И ИХ РЕАЛИЗАЦИИ 


    .    установить указатель и окно в конец текста 
    ута: Нижний стек.пуст |и холостая строка на экране .    цикл V i е О..макс 
YOKHE— 1 |т. е. без холостой строки 
    .    .   выполнять 
    .    .    Верхний стек.добавить строку (вх: Экран (i)) 
    .    конец цикла 
    , 
    .    Верхний стек.кончить работу (вых:ф:ключ) .    Экран, кончить работу 
    .   Нижний стек.кончить работу (вых: фи i ключ) .    ФС. удалить файл {вх 
! фи) конец программы 
    конец исполнителя 
    1 =.»=-=^ = = = =. = - = = = =. = = = =,======. = e«.-i»i 
    Мы совершили первый шаг декомпозиции и получили реали* вацию структуры 
данных (исполнителя) «Текст строк с изображаемым окном и указателем» на базе 
исполнителей «Экран», «Простейшая файловая система», «Верхний стек» и «Нижний 
стек». Исполнителя «Экран».мы считаем базовым. Простейшая файловая система 
была реализована в предыдущем разделе, Таким образбм, осталось реализовать 
верхний и нижний стеки. 
    Реализация исполнителя «Верхний стек» над файловой систе-i мой тривиальна, 
поэтому приведем ее без каких-либо пояснений: 

    исполнитель Верхний СТРН . СП: 
    1. начать работу 
    2. пуст	i да/нет 
    3. число строк      : Z+ ,  .      4. добавить строку (вх: С : строка) .   
   5. взять строку в (вых: С t строка) 6. кончить работу (вых : фв : ключ) 
    » 
    .   объекты! 
    ф!ключ | ключ файла, на котором имитируется стен n:Z-f-    (число строк в 
имитируемом стеке 
    * 
    .   используемые исполнители: 
    Простейшая файловая система (ФС) конец описаний |-——- — 
______-._-.______-.__-— -.___ 
    программа начать работу === ФС.создать файл (вых : ф : ключ); 
    п :*== О 
    программа пуст,	I да/нет == (пвмО) 


    18. ИЕРАРХИЯ СТРУКТУР ДАННЫХ	SQ5 


    программа число строк: Z+      ===== п программа добавить строку (вх: С : 
строка) ===== 
    ФС.добавить строку в конец файла (вх/вых: ф,вх: С); 
    п ;= п + I 
    программа взять строку'в (вых: С : строка) . дано        : п > О . получить: 
    .   ФС.взять строку из конца файла (вх/вых: ф,вых: С: строка) ,   п := п— 
1 конец программы 
    программа кончить работу (вых: фв : ключ) ===== фв :=• ф 
    конец исполнителя 
    | = = =- ==-= ==- = »===========.== = = ; 

    Осталось реализовать исполнителя «Нижний стек». В отличив от верхнего 
стека, который является более или менев'~6бычйым, нижний стек в момент начала 
работы должен содержать все строки исходного файла."Конечно, можно было бы 
прочесть их все от конца к началу и добавить в таком инвертированном виде в 
новый файл, после чего имитировать нижний стек нановом файле точно так же, как 
имитировали верхний. Однако предварительное инвертирование файла — длительная 
операция, а редактирование должно начинаться мгновенно, (Нйдошук 
_п.сдх,олагически JJOTOB в тому, чтобы нормальное завершение редактирования 
занимадр,„ка.-кое-то время, но абсолютно не готов к этому в начале — когда ,од 
еще" ничего не сделал     .) 
    Поэтому поступим по-другому — проимитируем нижний стек-так, как будто он в 
начальный момент содержит весь исходный файл, но физически никаких строк 
никуда копировать не будем, Для этого кроме исходного файла, который будем 
только последовательно читать, используем .еще один файл, на котором 
.пройми-тируем вспомогательный етек строк, Основная идея 
    реализации за« ключается в том, что содержимое нижнего стека в любой 
момент премени представляется в виде содержимого вспомогательного стека, ,-ia 
которым следует непрочитанная часть исходного файла и, если она еще не взята, 
холостая строка (рис, 18.1): нижний стек = вспомогательный стек+ непрочитанная 
часть исходного файла (+1 быть может, холостая строка) 
    При добавлении строки в нижний стек она всегда добавляется но 
вспомогательный стек. При взятии строки производится анализ: если 
вспомогательный стек не пуст, то строка берется из него, если Жо пуст, то 
читается очередная строка из исходного файла. Таким 

    296	гл. з. СТРУКТУРЫ ДАННЫХ и их РЕАЛИЗАЦИИ 

    образом, в начальный момент времени достаточно сделать вспомо« гательный 
стек пустым и встать в начало исходного файла. 
    Наконец, поскольку нижний стек должен в начальный момент содержать не 
только строки исходного файла, но и еще холостую строку «[» конец текста *]», 
будем имитировать эту строку с по« мощью глобального объекта 
    холостая строка взята : да/нет. 
    В начале работы установим «холостая строка взята t«=> нет» в знак того, 
что за непрочитанной частью исходного файла идет 

    _    холостая строка 
    1 вспомогательный стек 
    конец 
    Н&прочитанная часть 
    исходного файла 
    Исходный 

    Рис. 18.1 

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

    исполнитель Нижний стек . СП: 
    1. начать работу (вх: ф: ключ) .     2. пуст      ! да/нет .      3. 
добавить строку (вх I С : строка) .      4. взять строку в (вых: С : строка) 
    б. кончить работу (вых : ф I ключ) 
    .   объекты: 
    фи: ключ 1 исходного файла 
    .     фв: ключ   | файла для вспомогательного стека холостая строка взята: да/нет 
    . используемые исполнители: 
    .    Простейшая файловая система (ФС) 
    коиец описаний 1. 
    программа начать работу (вх: ф: ключ) . дано       : . получить: 


    18. ИЕРАРХИЯ СТРУКТУР ДАННЫХ 297 


    .   фи := ф 
    .   ФС.встать в начало файла (вх/выхIфи) 
    .    ФС.создать файл (вых:фв) 
    .   холостая строка взята := нет 
    конец программы 
    программа пуст:да/нет == (ФС.файл (фв) пуст и 
    ФС.в конце файла (фи) и холостая строка взята) программа добавить строку 
(вх: С : строка) ==	* 
    ФС.добавить строку в конец файла (вх/вых: фв,вх: С:строка) 
    программа взять строку в (вых: С : строка) . дано        : не пуст . получить: 
    .	выбор 
    ,	.   при ФС.файл (фв) не пуст =*
    .	.       ФС.взять строку из конца файла (вх/вых: фв,вых : С) 
    .	.    при ФС.не в конце файла (фи) •=*• 
    .	.       ФС.прочесть строку вперед (вх/вых: фи,вых: С: строка) 
    .	.   при холостая строка не взята =*• 
    .	.       С.длина                        := 18 |число симв.холостой строки 
    .	.        С.текст (1..С.длина) :•= "[* конец текста »]" 
    .	.       холостая строка взята := да 
    .	,   иначе =*- отказ 
    .	конец выбора 
    конец программы 
    программа кончить работу (вых : ф : ключ) === 
    ФС. удалить файл (вх?фв); ф : = 
    конец исполнителя 
    • фи 
    Мы реализовали исполнителя «Текст строк с изображаемым окном и указателем» 
с использованием реализованного нами в предыдущем разделе исполнителя 
«Простейшая файловая система». Иерархия структур данных в этой реализации 
оказалась достаточно простой (рис. 18.2). 
    Стрелки, идущие вниз от исполнителя, показывают, на базе каких других 
исполнителей он реализован. По сути дела, эта картинка является 
технологической цепочкой программирования «сверху/ 

    298 ГЛ. 3. СТРУКТУРЫ ДАННЫХ И ИХ  РЕАЛИЗАЦИИ 

    вниз» для проекта «Текст строк с изображаемым окном и укаэате-* дем»,   
нарисованной   без   использования   «векторных   обозначений»! 
    Экран   I	[    Верхний стек 
    | Простейшая файловая система I 

    Рис. 18.2 

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

    ____f^	i - ,           
    Нижний стек [     j Экран [    ] 
    Верхний стек 
    Верхний динамический вектор  БЛОКОВ 
    Нижний динамический вектор блоков 

    Рис.   18.3 

    рбычио уже реализуется над файловой системой. Аналогично декомпозируется я 
верхний стек. В итоге иерархия структур данных принимает вид, изображенный на 
рис, 18.3, 

    ЗАДАЧИ И УПРАЖНЕНИЯ 

    1. Может ли при редактировании текста в некоторый момент оказаться, что в 
нем 100 строк, а на экране изображена только холостая строка? 
    8. ИЕРАРХИЯ СТРУКТУР ДАННЫХ! 299 
    2. Модифицируйте проект «Текст строк с изображаемым окном и указателем», 
добавив предписание «внести изменения в файл». Смысл этого предписания состоит 
в том, что аварийное завершение работы должно возвращать ключ файла с тем 
текстом, который был в момент последнего вызова предписания «внести изменения 
в файл». 
    3. Модифицируйте проект «Текст строк с изображаемым окном и указателем», 
'считая, что и в начальный, и в конечный момент времени текст расположен в 
двух стеках (двух файлах) на диска и что аварийного завершения работы нет. При 
этом положение в тексте и в окне должно сохраняться между «кончить» и «нач 
чать» работу, 

    Указание. Введите предписания «добавить число в конец файла <вх/вых: Ф, 
вх: п>» и «взять число из конца файла <вх/вых: Ф, вых: п.)», которые будут 
преобразовывать число а строку символов и наоборот, а также добавлять/брать 
соответствующую строку файла, 

    4. Модифицируйте проект «Текст строк с изображаемым окном и указателем», 
добавив предписание «откатить последнее изменение». По этому предписанию текст 
и положение указателя в нем должны принимать те состояния, в которых они 
находились перед последним удалением или вставкой строки, Вызов этого 
предписания до первого изменения текста не должен вызывать никаких действий. 
    5. Решите задачу 4, считая, что предписание «откатить последнее изменение» 
можно вызывать неоднократно! второй вызов откатывает второе по давности 
изменение и т. д. Другими словами, последовательное применение откатки должно 
восстанавливать предыдущие состояния текста вплоть до исходного состояния 
перед редактированием. 
    Указание. Используйте еще один вспомогательный файл (файл откатки) в 
качестве стека для хранения необходимой для откатки информации. 
    6. В рамках задачи 5 добавьте еще предписание «Откатить от-» кптку», 
которое должно выполнять действия, обратные к «откатить последнее изменение». 
    Указание,   Используйте  два  вспомогательных  файла. 
