    13. Ссылочные реализации на базе вектора 

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

    Воображаемый список; 
    элементов         1	1     «     1	1     В     1	1            1	1      Б    
 |              |. 
    2	3	4	56. 
    Вектор               1	1     =     1	1             '	1	|      3      |     
          |  • 
    2	3	4	а       &     . 

    Рис.	13.1 

избежать не всегда. Для структур, где порядок элементов не важен 
(множество) или не меняется (стек, очередь, дек, последовательность, 
динамический вектор), непрерывная реализация без массовых операций возможна, 
Но при непрерывной реализации, например, ЛЬсписка сдвиги неизбежны, так как в 
Л1-список можно вставить элемент в середину. 
    Массовых операций можно избежать и при реализации спи-сков, но для этого 
надо отдельно хранить элементы имитируемой структуры и отдельно задавать их 
порядок. Для Л1-списка, например, элементы списка можно произвольным образом 
расположить в векторе элементов типа Е с индексом типа 1 ., максинд, а 
информацию о порядке элементов задавать во вспомогательном векторе (назовем 
его вектором ссылок) элементов типа 1 ,. максинд с индексом также типа 1 .. 
максинд. Например, если в компоненте вектора элементов типа Е с индексом 5 
расположен какой-то элемент имитируемого ЛЬсписка, а следующий за ним элемент 
списка расположен в компоненте вектора с индексом 3, то эта информация 
запоминается в векторе ссылок — ссылка с индексом 5 устанавливается в 
состояние 3 (рис. 13,1). 
    Таким образом,  основная  идея  ссылочной реализации состоит вотделении_ 
информации   о   содержимом   влементов   имитируемой,, структуры   (вектор 
_элементрв  типа  Е)   от информации об их  порядке (вектор ссылок). Ссылки 
далее будем изображать стрелками, как показано на рис, 13.2. 

    •Вектор*    I__ Ссылки!	1 
    I  " I 

    Рис.   13.2 

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

    *"КТОМ       J	1    «    I    •    I 

    Рис.   13.3 

    индекс, которые содержали бы индексы начала и конца списка. Мы, однако, 
«того делать не будем, а снова воспользуемся приемом «сиорачивания в 
кольцо»—«свернем» список, введя специаль-. иый воображаемый элемент нил, 
который всегда будем располагать и компоненте вектора с .индексом 1 (рис. 13.3). 
    Заметьте, что теперь ссылки между элементами списка (включая нил) образуют 
кольцо, начинающееся с 1. Таким обра-ном, ссылка с индексом 1 показывает на 
первый элемент, списка, и если очередная ссылка равна 1, то соответствующий 
элемент ииляется в списке последним. Пустому списку соответствует ситуация, 
когда в кольце никаких элементов, кроме нил, нет, т, е, ссылка • индексом 1 
равна 1 (показывает «на себя»), 

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

    Указатель в списке располагается между элементами, поэтому реализуем его в 
виде объекта 
    указатель : запись (@до, <8за : индекс), 
    где поле «@до» содержит индекс элемента до указателя, а пола «@за» — 
индекс элемента за указателем*). Положению указателя в начале списка, таким 
образом, соответствует случай, когда поле «@до» равно 1 (указывает па нил), а 
положению в конце — когда 1 равно поле «®за», 
    Теперь список проимитирован полностью. Неясным остался только вопрос: как 
определять наличие или отсутствие свободного места и как находить свободный 
элемент вектора при имитации добавления элемента к списку? Чтобы не гадать, 
какие элементы вектора свободны, а какие заняты элементами списка, примем ре« 
шение, что свободные элементы вектора также будут соединены в кольцо, 
начинающееся со служебного элемента «нил свободного места» — компоненты 
вектора с индексом 2 (рис. 13.4). 

    Вектор: 
    Ссылки! 

    Рис.   13.4 

    Заметим, что, поскольку элементы с индексами 1 и 2 теперь играют служебную 
роль, в них никогда не попадет никакой элемент имитируемой структуры. 
Следовательно, вектор элементов типа Е, предназначенный для хранения элементов 
списка, может иметь индекс в диапазоне не 1 .. максинд, а 3 .. максинд. 
    С математической точки зрения каждое состояние вектора ссылок определяет 
некоторое отображение f множества индексов в себя — индексу i ставится в 
соответствие значение элементаi.aejtr •гор_а ссылок с индексом i. Принятые 
нами решения означают, что 6 каждый момент времени отображение f взаимно 
однозначно и имеет ровно две периодические траектории «список» и «свободное 
место». Эти траектории имеют вид     ),... ,нилЛ(нил),,.., 
    *) Символ @ (официальное название — «at» коммерческое, обычно произносится 
«блямба») считается такой же буквой, как а, Ь, с в др. Мы 0удем начинать с 
этого символа имена объектов-ссылок, т. е. если имя объекта начинается с в), 
то состоянием объекта является индекс какого-то ЕЯемента вектора. 

    13. ССЫЛОЧНЫЕ РЕАЛИЗАЦИИ НА БАЗЕ ВЕКТОРА 203 

    не пересекаются, покрывают все множество индексов и начинаются с 1 (нил 
списка) и 2 (нил свободного места). 
    (Траекторией отображения f :Х->Х, изминающейся^с_точки а, мы называем 
множество тех точек хеХ, .которые можно получить из"а7многократно при* Деняя 
f, т. е. {х еХ: 3n<=Z+ : x=fn (а)}, где f0(a)=^aTlr(a)"^f (a)," f"2(a)'^ •= 
f(f(a)), .... fn(a)~=f(f (... f(a) .,,)) (n раз). Траектория называется 
периодичв' ской, если существует п>0 такое, что fn(a) 
    = a.) 
    Таким образом, чтобы определить, есть ли в векторе свободное место, надо 
посмотреть значение ссылки с индексом 2. Если это значение равно 2 (т. е. 
траектория «свободное место» не содержит элементов, отличных от нил свободного 
места), то свободного места нет. В противном случае это значение указывает »а свободный 

    отдельная/ Бусинка 
    свободное место 

    Рио. 13.5 

    элемент вектора, в который можно поместить новый элемент спи» ско при 
имитации его добавления. Заметьте, что в последнем слу« ча» нйд» исключить 
индекс свободного элемента вектора из траек-topini «омпЛодпос место» и 
включить этот индекс в траекторию ^список». Наоборот, при имитации удаления 
элемента из списка необходимо исключить индекс этого элемента из траектории 
«список» и включить его в траекторию «свободное место». 
    включение (или исключение) индекса в ту или иную траекторию оанячпгт 
«стирание» какого-то количества старых и «рисование» никого-то количества 
новых стрелок. В программе стрелкам соот-, потстпуют ссылки (т. е. элементы 
вектора ссылок). «Рисование», ноной стрелки означает изменение состояния 
соответствующей ссыл-. tin и автоматическое «стирание» старой стрелки с тем же началом. 
    Будем представлять элементы вектора бусинками, а стрелки —ч исрсночками. 
Тогда весь вектор распадется на две цепочки бус. (дли элементов имитируемого 
списка и свободного места соответл отш-нио). Переброс бусинки из свободного 
места в список озна* *ш>т, что надо 

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

    а) взять какую-нибудь бусинку из свободного места, т. е. раз-резать 
веревочки справа и слева от бусинки и связать их между/ собой. После этого у 
нас будут две цепочки бус и одна бусинка «сама по себе» (рис. 13.5); 
    б) разрезать веревочку в том месте списка, куда нужно вставлять новую 
бусинку, и связать получившиеся концы с бусинкой (рис. 13.6). Разрезание 
веревочек (или, что что же самое, стирание Стрелок) не более чем аналогия — на 
программном уровне веревочку 

    список 
    Рис.   13.S 

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

    связать <вх ! И1, И2 : индекс) 

    Кроме того, выделим в отдельные программы все действия, связанные с 
траекторией «свободное место». Получение (захват) бу« синки из свободного 
места, т. е. действия пункта а) выше, будем выполнять с помощью программы 
    захватить место <вых : И : индекс) 
    где И-ч» это индекс «бусинки» в векторе, а обратное действие—» включение 
«отдельно висящей» бусинки в свободное место — с по-, мощью программы 
    освободить место <вх i И : индекс) 
    исполнитель Ограниченный Л1 список | на базе вектора , СП: 
    »    1. начать работу ,   2. сделать список пустым 
    .   3. список пуст	: да/нет .   4, есть свободное место                    
                                [да/нет .   б. нет свободного места            
                                     5 да/нет .   6. установить указатель в 
начало списка ,.   7. указатель в конце списка                                 
           ! да/нет ,   8. передвинуть у 
    казатель списка вперед ,   9. добавить элемент (вх; Е) за указателем списка., 


    И. ССЫЛОЧНЫЕ РЕАЛИЗАЦИИ НА БАЗЕ ВЕКТОРА	207 

    . 10. взять элемент списка за указателем в (вых: Е) 
    • 11. элемент списка за указателем	j:E ,12. удалить элемент списка за указателем, 
    "'•у 
    « —   захватить место {вых: И : индекс) ч —  освободить место (вх: И: 
индекс) » . 13. кончить работу 
    . константы: 
    .   максинд = 100 |число элементов в векторе 
    . типы: 
    .   индекс —1.. максинд 
    • 
    . объекты: 
    .   указатель : запись(@до,@за : индекс) 
    • 
    . используемые исполнители: 
    ,   информация:вектор  элементов типа'Е с индексом З..максиня 
    .    (Услсдующин : вектор элементов типа индекс 
    .	с индексом типа индекс 
    § 
    . обозначения: 
    ••   пил списка	"=— 1 .   пил свободного места"==2 
    рслли.шцни: 
    •   Каждой i-01'Toiiiiiic пскторп определяет отображение f 
    •   ("аследующий") множества индексов в себя: 
    • 
    .	f; И -> @следующий(И) 
    • 
    .   Мы   реализуем   список  так,  что в каждый момент времени ото» 
    .    Сражение f взаимно однозначно и имеет равно две периодические 
    .   траектории   ."список"   и    "свободное   место".    Эти   траектории 
    .   имеют вид: 
    t 
    .    ...пил, f (нил), f (f (нил)), f (f (f (пил))),..., нил,... 
    .   не  пересекаются,   покрывают  все  множество  индексов   и  начя-.   
иаются с 1 (нил списка) и 2 (нил свободного места) 
    конец описаний 


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


    программа начать работу 
    , дано        !    максинд > 2 
    . получить: (траектория "список" = нил списка } 
    ,	|траектория "свободное место"  = 
    ,	I                     нил св. места, 3, 4, ..., максинд 
    .   информация.начать работу 
    .   ©следующий.начать работу 
    * 
    .   связать	(нил списка, нил списка) 1 траектория «список» 
    .   указатель := (нил списка, нил списка) 
    .    цикл V И е нил свободного места, .максинд—1 выполнять 
    .    .     связать (И,И + 1) 
    .   конец цикла 
    .   связать {максинд, нил свободного места) 
    конец программы 
    программа сделать список пустым 
    . дано        : 
    > получить: список пуст 
    . установить указатель в начало списка . цикл пока список не пуст 
выполнять . . удалить элемент списка за указателем 
    конец цикла конец программы 
    Программа список пуст: да/нет ==• 
    (@следующий(нил списка) =» нил описка) 
    Программа есть свободное место : да/нет -
    (@следующий(нил свободного места) Ф нил свободного места) программа нет 
свободного места : да/нет -
    (@следующий(нил свободного места) => нил свободного места) программа 
установить указатель в начало списка -•" 
    указатель := (нил списка, @следующий(нил списка)) программа указатель в 
конце списка: да/нет -
    (указатель. @за =нил списка) 
    программа передвинуть указатель списка вперед 
    дано        : указатель не в конце списка л получить: 
    .   указатель.@до := указатель.@за 
    .   указатель. @за : = ©следующий(указатель. @за) 
    конец программы, 


    13. ССЫЛОЧНЫЕ РЕАЛИЗАЦИИ НА БАЗЕ ВЕКТОРА 209 
    

    программа добавить элемент (вх: Е) за указателем списка . дано       : 
есть свободное место . получить: 
    .   захватить место (вых: И)     | из траектории "свободное место" 
    .   связать (указатель. @до, И) (добавить элемент с индексом И .   связать 
(И, указатель.@за) |в траекторию "список". •   указатель.@за := И	(установить 
указатель .   информация(И) := Е             (разместить информацию конец программы 
    программа взять элемент списка за указателем в (вых": Е) . дано       : 
указатель не в конце списка . получить: 
    .    Е := элемент списка за указателем .   удалить элемент списка за 
указателем конец программы 
    программа элемент списка за указателем^:: Е . дано        : указатель не в 
конце списка • получить: 
    .   ответ -= информация(указатель.@за) конец программы 
    программа удалить элемент списка за указателем . дано        : указатель 
не в конце списка . получить) 
    •   ^	" = — -. 
    •    И :=> указатель.@за	(удалить   элемент   век-.   указатель.@за := 
@следующий(И)              (тора   за указателем из .   связать 
(указатель.@до,указатель.@за)   | траектории ^список" ,   оснободить место (вх 
: И)   ( добавить его в свободное место кпигц программы 
    программа связать (вх:И1,И2: индекс) -- @следующий(И1) :== И2 
    программа захватить место (вых: И : индекс) . дано        : есть свободное место 
    • получить: 
    ,   И:= @следующий(нил свободного места) 
    ,   связать (нил свободного места, @следующий(И)) 
    •нмсц программы 


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


    программа освободить место (вх: И: индекс) . дано        I . получить: 
    .   связать (И, @следующий(нил свободного места)) .   связать (нил 
свободного места, И) конец программы 
    программа кончить работу "•" 
    информация.кончить   работу;   ©следующий.кончить 
    работу 
    конец исполнителя 
    | •=-=--" = -=-- = = '=-----= = ---'-= = ===-1="


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

    1. Каково максимальное число элементов ЛЬсписка в приведенной выше реализации? 
    2. Пусть дано, что указатель находится в конце списка, Реализуйте при этом 
условии программу «сделать список пустым» так, чтобы число элементарных 
операций с вектором не зависело ни от числа элементов списка, ни от числа 
элементов вектора (т. е. не пользуясь ни циклами, ни рекурсией). 
    3. Модифицируйте реализацию Л1-списка так, чтобы получить реализацию 
ограниченного Л2-списка. 
    Указание. Введите еще один вектор ссылок «©предыдущий» и реализуйте 
Л2-список так, чтобы отображения «©следующий» и «^предыдущий» были взаимно 
обратны. Постарайтесь, чтобы при реализации Л2-списка как можно большее число 
программ Л1-спи-ска осталось без изменений. 
    4. В рамках реализации Л2-списка (задача 3) реализуйте программу «сделать 
список пустым» так, чтобы 'число операций было константой, т, е. не пользуясь 
ни циклами, ни рекурсией. 
    В задачах 5—8 указанные в задаче структуры требуется реали-зовать 
ссылочным образом на базе одного вектора элементов типа Е и одного или двух 
векторов ссылок. Слова __«ограниченные ^совокупности» означают, что эти 
структуры имеют общие для всех них предписания «начать 
"работу^»/«конч^ть;"ра6оту» и «есть свободное "место»/«нет свободного места». 
Если надо реализовать несколько одноименных структур (три стека, 133 стека, 
100 множеств), то это значит, что во всех предписаниях кроме «есть сво-i 
бодное место»/«нет свободного места» и «начать работу»/«кончить работу» есть 
еще один параметр — номер структуры (аналогично задаче 13 предыдущего 
раздела). Кроме вектора элементов типа Е и одного или двух векторов ссылок, 
как обычно, можно использовать любое количество объектов простых типов и 
записей из них» 

    И. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА     211 

    5. Три стека, ограниченные в совокупности. 
    6. 133 стека, ограниченные в совокупности. 
    7. Стек,   очередь   и   Л2-список,   ограниченные   в   совокупности, 
    8. 100 множеств, ограниченные в совокупности. Указание. Объедините 
элементы отдельных структур в отдельные траектории, а оставшиеся элементы — в 
траекторию «своч бодное место». Другими словами, для реализации п структур 
используйте п + 1 траектории (например, в задаче 6 используйте, .134 
траектории, а в задаче 8—• 101'траекторию), 