41.Нелинейный двухсвязный список (плекс)

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

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

Рисунок 7.10  Логическая структура нелинейного двухсвязного списка

Ссылки List1 и List2 являются указателями двух отдельных односвязных списков, в каждый из которых одновременно  входят все шесть элементов. Поля Р1 и Р2 всех элементов служат для хранения структурных ссылок, с помощью которых элементы связываются, формируя тем самым каждый из двух списков.

На рисунке 7.10 показано лишь одно из содержательных полей узлов, а именно, поле фамилии абитуриента (объекта предметной области). Из рисунка видно, что в списке, сформированном с помощью ссылки Р1,  установлен следующий порядок следования узлов:

 

Фокин  Лавров  Бойко  Яшина  Власова  Жеглов

В цепном списке, указателем которого является List2,  этот список сформирован с помощью структурной ссылки Р2  элементы располагаются в следующем порядке:

Бойко  Власова  Жеглов  Лавров  Фокин  Яшина

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

Рисунок 7.11  Эквивалентная логическая структура нелинейного
двухсвязного списка, изображенного на рисунке 7.10

Сопоставление рисунков 7.10 и 7.11 показывает, что оба цепных списка двухсвязной структуры, рассматриваемые по отдельности, являются линейными. Вся структура в целом, с учетом обеих связок,   не линейна.

 

 


42.Нелинейный трехсвязный список (плекс)

 

Несложно представить трехсвязный список, содержащий информацию об абитуриентах, в котором две структурных ссылки объединяют узлы так же, как на рисунках 7.10 и 7.11, а третья ссылка Р3 связывает те элементы (в алфавитном порядке), которые относятся к абитуриентам, обладающим правами преимущественного поступления в ВУЗ. Логическая структура такого списка показана на рисунке 7.12. На этом рисунке штриховыми линиями показаны структурные ссылки, объединяющие элементы с помощью поля Р3. Назовем этот цепной список Р3-списком.

В цепном списке, организованном с помощью структурного указателя Р3, очевидно, будет содержать не все элементы. В нашем примере (см. рисунок 7.12) в Р3-списке содержится три элемента, которые упорядочены ссылкой Р3 следующим образом:

Бойко  Фокин  Яшина

Указателем Р3-списка является внешний указатель List3. Этот пример показывает, что необязательно, чтобы каждый элемент общей списковой структуры непременно входил во все цепные списки одновременно.

 

Рисунок 7.12  Логическая структура нелинейного трехсвязного списка

 


43.Определение плекса и его общие признаки 

В общем случае возможно создание многосвязного списка, каждый элемент которого может содержать К полей (К = 2, 3, 4 …) структурных указателей. Как показывают логические структуры нелинейных связных списков, изображенные на рисунках 7.10  7.12, многосвязный список как бы «прошит» в разных направлениях многими указателями. Поэтому такие списки называют прошитыми списками или плексами (plexus  сплетение, переплетение).

Сформулируем общие признаки плексов:

все элементы  такой  структуры  содержат одинаковое количество полей структурных указателей, число которых К  степень связности  является важной характеристикой структуры;

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

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

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

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

 


44.Иерархическая списковая структура. Сетевая структура

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

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

-формируется список (назовем его Main-списком), элементы которого содержат информацию о группах: номер группы, число студентов, староста и т. д.,

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

Очевидно, эта модель предполагает существование такого количества Sub-списков, которое равно числу групп. Каждый Sub-список как бы подчиняется Main-списку.

 Для представления описанной модели в памяти можно использовать следующую структуру. Пусть указатель Faculty адресует начало главного цепного списка, каждый элемент которого, кроме информации о группах факультета, содержит два указателя Main и Sub. Указатель Main связывает элементы главного списка, а указатель Sub каждого элемента главного списка ссылается на начало другого списка, который содержит информацию о студентах соответствующей группы. Такая структура показана на рисунке 7.13.

Как видно из рисунка 7.13, каждый список, адресуемый указателем Sub как бы «подчиняется» элементу главного списка; такой список, «ответвляющий-

ся» от главного списка, называется подсписком (sublist). Очевидно, в каждом подсписке

может располагаться произвольное число элементов, в общем случае не равное для всех

 подсписков. Список, организованный указателем-связкой Main, образует верхний уровень иерархии, а списки, на начало которых указывают указатели Sub  нижний уровень. Такой список называется двухуровневым связным списком. Рисунок 7.13  Двухуровневый иерархический связный список


45.Достоинства и недостатки связных списков

Перечислим преимущества связных списков.

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

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

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

Динамические связные структуры  создаются, хранятся и обрабатываются в самой большой по объему области оперативной памяти  куче (heap). Это дает возможность с помощью таких структур решать серьезные задачи, требующие много памяти.

Основным недостатком связных списков является то, что затраты времени на получение доступа к их элементам зависят от количества элементов. Для получения доступа к некоторому  i-ому элементу необходимо выполнить переходы по ссылкам вплоть до искомого элемента. Чем больше элементов в списке, тем больше переходов придется совершить.

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

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

 


46.Функциональные и свободные списки. Методы формирования свободного списка

 

Общая характеристика

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

 Свободный список формируется из элементов, исключаемых из функционального списка. Операцию исключения можно изобразить с помощью рисунка 7.14, на котором показана операция исключения третьего узла. Если на удаляемом элементе не сохранить указатель (как на рисунке 7.14 6), то его слот перестанет быть адресуемым, то есть в куче появится неадресуемое пространство  «дыра». С целью экономии памяти исключенный элемент следует включить в список, сформированный из других исключенных элементов одинакового формата, то есть в свободный список. В дальнейшем прежде чем добавить в функциональный список новый элемент, следует проверить соответствующий свободный список, и, если в свободном списке есть элементы, то взять элемент из него, а не создавать в памяти новый элемент.

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

Рисунок 7.14  Исключение в связном списке

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

Методы формирования свободного списка

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

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

В методе сборки мусора (garbage collection) не требуется при разрыве каждой связки делать проверку элемента и возвращать освободившийся элемент в свободный список. Освободившийся элемент как бы «повисает» до тех пор, пока не будет исчерпан свободный   список.   И  только  после  этого  запускается процедура «сборки мусора», которая отыскивает все освободившиеся к тому времени элементы и включает их в свободный список.  Для  реализации метода сборки мусора в каждом элементе многосвязной структуры резервируется минимально возможное поле памяти для маркера, который используется на этапе поиска освободившегося элемента. С этой целью процедура маркирует все доступные элементы многосвязной структуры, т. е. такие элементы, к которым направлен хотя бы один указатель. Затем просматривается вся область памяти, отведенная для элементов, и в свободный список включаются все элементы, в которых отсутствует маркер.

Диспетчер кучи Delphi создает список свободных областей (free space list) по мере выполнения процедур «уничтожения» динамических переменных, таких, например, как Dispose.

 


47.Векторная организация строки

 

Строка (line, string)  это конечная линейно упорядоченная последовательность данных одного и того же символьного типа, рассматриваемая как единое целое. Элемент строки  некоторый символ, который может быть буквой латинского или русского алфавита, цифрой, математическим или специальным знаком. Каждый символ в памяти представляется 8-битовой (множество ANSI, см. п. 3.3.4) или 16-битовой (множество Unicode) комбинацией двоичных нулей и единиц, т. е. для хранения символа отводится один или два байта.

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

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

1.1.1          Векторная организация строки

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

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

Рисунок 8.1  Дескрипторный метод организации строки

 

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

Рисунок 8.2  Организации строки методом граничных маркеров

 


48.Связное представление строк

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

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

 

Рисунок 8.3  Организации строки в виде односвязного списка

Другим недостатком является несмежность в памяти соседних символов строки; это усложняет доступ к элементам строки по сравнению с доступом при векторном представлении.

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

 

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

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

Примечания: а  строка разбивается на равные группы символов,

  б  строка разбивается на неравные группы символов

Рисунок 8.4  Две разновидности связного представления строки

 


49.Общая характеристика и типы строк в Delphi

 Delphi имеется несколько типов строковых данных. Они перечисляются в таблице 8.1.

Таблица 8.1  Типы строк

 


50 Короткие и длинные строки

 

Родовым является тип String, который имеет разный смысл в зависимости от наличия директивы компилятора $H, которая включена по умолчанию. Если эта директива включена, т. е. {$H+}, то тип String интерпретируется компилятором как тип ANSIString  длинная строка с нулевым символом в конце. Если имеется {$H}, т. е. $H отключена, то String интерпретируется как тип ShortString  короткая строка без нулевого символа в концесли в объявлении типа после слова String следует число символов в скобках, например, String[4], то независимо от директив компилятора, тип трактуется как строка с указанной максимальной длиной без нулевого символа в конце. В этом случае строка организуется по дескрипторному методу, показанному на рисунке 8.1. Строки без нулевого символа хранят текущее количество символов в байте, который имеет индекс 0, а сами символы располагаются в последующих байтах. Поскольку максимальное значение, которое может быть представлено одним байтом, равно 255, именно этим значением ограничено количество символов в строке. Поэтому строки без нулевого символа в конце называют короткими строками настоящее время основным типом строк являются строки с нулевым символом в конце. Этот вид строк поддерживается такими языками программирования, как Си и Си++, а также API-Windows и многими другими системами. Строка с нулевым символом в конце (null-terminated string) представляют собой вектор символов, в котором хранятся символы строки и в конце (после всех символов) добавляется нулевой символ (#0), указывающий на окончание строки. Поскольку число символов в строках с нулевым символом в конце практически не ограничено, то такие строки называются длинными строкамилинная строковая переменная типа ANSIString (или String, когда он ANSIString)  это всего лишь указатель на специальным образом отформатированный блок памяти, который выделяется в куче. Если строка пуста, т. е. ее длина равна 0, то этот указатель равен Nil. В противном случае указатель ссылается на блок памяти, содержащий последовательность символов, составляющих строку. Эта последовательность символов для длинной строки обязательно завершается нулевым символом #0, который заносится автоматически.

-предшествующие четыре байта содержат целое значение, представляющее счетчик ссылок;

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

Предположим, что в памяти существует строка MyString типа ANSIString. При выполнении операции присваивания

MyOtherStr:= MyString;

увеличивается на единицу счетчик ссылок для строки, на которую указывает MyString, а затем указатель MyOtherStr становится равным указателю MyString.

Если переменной MyString  присвоить новое строковое значение, то счетчик ссылок в прежней строке уменьшится на единицу. Как только число ссылок на строку становится равным 0, строка уничтожается, освобождая место в памяти. Если с помощью индексного доступа к строке изменяется один символ, то строка копируется только в том случае, если число ссылок на нее больше 1.

Доступ к отдельным символам строки типа ANSIString осуществляется как к символьному массиву по индексам, причем (внимание !) индексы отсчитываются от 1, хотя в других типах длинных строк индексы отсчитываются от 0. Если, например, в программе имеется оператор

MyString:= ’Параметр = ’;

то  выражение MyString[1] возвратит значение первого символа ’П’, выражение  второго  ’а’ и т. д. 

Для обработки строк ANSIString имеется ряд очень полезных библиотечных функций (Pos, Delete, Insert, Copy и др.). Полный перечень этих функций можно найти в справочнике по Delphi.