Логическая структура дека
4.4.1. Логическая структура дека
Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
Операции над деком:
включение элемента справа; включение элемента слева; исключение элемента справа; исключение элемента слева; определение размера; очистка.
Деки в вычислительных системах
4.4.2. Деки в вычислительных системах
Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.
Однако, в качестве примера такой системной поддержки рассмотрим организацию буфера ввода в языке REXX. В обычном режиме буфер ввода связан с клавиатурой и работает как FIFO-очередь. Однако, в REXX имеется возможность назначить в качестве буфера ввода программный буфер и направить в него вывод программ и системных утилит. В распоряжении программиста имеются операции QUEUE - запись строки в конец буфера и PULL - выборка строки из начала буфера. Дополнительная операция PUSH - запись строки в начало буфера - превращает буфер в дек с ограниченным выходом. Такая структура буфера ввода позволяет программировать на REXX весьма гибкую конвейерную обработку с направлением выхода одной программы на вход другой и модификацией перенаправляемого потока.
Логическая структура строки
4.5.1. Логическая структура строки
Строка - это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом.
Строки обладают следующими важными свойствами:
их длина, как правило, переменна, хотя алфавит фиксирован; обычно обращение к символам строки идет с какого-нибудь одного конца последовательности, т.е важна упорядоченность этой последовательности, а не ее индексация; в связи с этим свойством строки часто называют также цепочками; чаще всего целью доступа к строке является на отдельный ее элемент (хотя это тоже не исключается), а некоторая цепочка символов в строке.
Говоря о строках, обычно имеют в виду текстовые строки - строки, состоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов. Действительно, текстовая строка является наиболее универсальной формой представления любой информации: на сегодняшний день вся сумма информации, накопленной человечеством - от Ветхого Завета до нашего учебного пособия - представлена именно в виде текстовых строк. В наших дальнейших примерах этого раздела будем работать именно с текстовыми строками. Однако, следует иметь в виду, что символы, входящие в строку могут принадлежать любому алфавиту. Так, в языке PL/1, наряду с типом данных "символьная строка" - CHAR(n) - существует тип данных "битовая строка" - BIT(n). Битовые строки, составляются из 1-битовых символов, принадлежащих алфавиту: { 0, 1 }. Все строковые операции с равным успехом применимы как к символьным, так и к битовым строкам.
Кодирование символов было рассмотрено в главе 2. Отметим, что в зависимости от особенности задачи, свойств применяемого алфавита и представляемого им языка и свойств носителей информации могут применяться и другие способы кодирования символов. В современных вычислительных системах, однако, повсеместно принята кодировка всего множества символов на разрядной сетке фиксированного размера (1 байт).
Хотя строки рассматриваются в главе, посвященной полустатическим структурам данных, в тех или иных конкретных задачах изменчивость строк может варьироваться от полного ее отсутствия до практически неограниченных возможностей изменения. Ориентация на ту или иную степень изменчивости строк определяет и физическое представление их в памяти и особенности выполнения операций над ними. В большинстве языков программирования (C, PASCASL, PL/1 и др.) строки представляются именно как полустатические структуры.
В зависимости от ориентации языка программирования средства работы со строками занимают в языке более или менее значительное место. Рассмотрим три примера возможностей работы со строками.
Язык C является языком системного программирования, типы данных, с которыми работает язык C, максимально приближены к тем типам, с которыми работают машинные команды. Поскольку машинные команды не работают со строками, нет такого типа данных и в языке C. Строки в C представляются в виде массивов символов. Операции над строками могут быть выполнены как операции обработки массивов или же при помощи библиотечных (но не встроенных!) функций строковой обработки.
В языках универсального назначения обычно строковый тип является базовым в языке: STRING в PASCAL, CHAR(n) в PL/1. (В PASCAL длина строки, объявленной таким образом, может меняться от 0 до n, в PL/1 чтобы длина строки могла меняться, она должна быть объявлена с описателем VARING.) Основные операции над строками реализованы как простые операции или встроенные функции. Возможны также библиотеки, обеспечивающие расширенный набор строковых операций.
Язык REXX ориентирован прежде всего на обработку текстовой информации. Поэтому в REXX нет средств описания типов данных: все данные представляются в виде символьных строк. Операции над данными, не свойственные символьным строкам, либо выполняются специальными функциями, либо приводят к прозрачному для программиста преобразованию типов. Так, например, интерпретатор REXX, встретив оператор, содержащий арифметическое выражение, сам переводит его операнды в числовой тип, вычисляет выражение и преобразует результат в символьную строку. Целый ряд строковых операций является простыми операциями языка, а встроенных функций обработки строк в REXX несколько десятков.
Операции над строками
4.5.2. Операции над строками
Базовыми операциями над строками являются:
определение длины строки; присваивание строк; конкатенация (сцепление) строк; выделение подстроки; поиск вхождения.
Операция определения длины строки имеет вид функции, возвращаемое значение которой - целое число - текущее число символов в строке. Операция присваивания имеет тот же смысл, что и для других типов данных.
Операция сравнения строк имеет тот же смысл, что и для других типов данных. Сравнение строк производится по следующим правилам. Сравниваются первые символы двух строк. Если символы не равны, то строка, содержащая символ, место которого в алфавите ближе к началу, считается меньшей. Если символы равны, сравниваются вторые, третьи и т.д. символы. При достижении одной конца одной из строк строка меньшей длины считается меньшей. При равенстве длин строк и попарном равенстве всех символов в них строки считаются равными.
Результатом операции сцепления двух строк является строка, длина которой равна суммарной длине строк-операндов, а значение соответствует значению первого операнда, за которым непосредственно следует значение второго операнда. Операция сцепления дает результат, длина которого в общем случае больше длин операндов. Как и во всех операциях над строками, которые могут увеличивать длину строки (присваивание, сцепление, сложные операции), возможен случай, когда длина результата окажется большей, чем отведенный для него объем памяти. Естественно, эта проблема возникает только в тех языках, где длина строки ограничивается. Возможны три варианта решения этой проблемы, определяемые правилами языка или режимами компиляции:
никак не контролировать такое превышение, возникновение такой ситуации неминуемо приводит к труднолокализуемой ошибке при выполнении программы; завершать программу аварийно с локализацией и диагностикой ошибки; ограничивать длину результата в соответствии с объемом отведенной памяти;
Операция выделения подстроки выделяет из исходной строки последовательность символов, начиная с заданной позиции n, с заданной длиной l. В языке PASCAL соответствующая функция называется COPY. В языках PL/1, REXX соответствующая функция - SUBSTR - обладает интересным свойством, отсутствующим в PASCAL. Функция SUBSTR может употребляться в левой части оператора присваивания. Например, если исходное значение некоторой строки S - 'ABCDEFG', то выполнение оператора: SUBSTR(S,3,3)='012'; изменит значение строки S на - 'AB012FG'.
При реализации операции выделения подстроки в языке программирования и в пользовательской процедуре обязательно должно быть определено правило получения результата для случая, когда начальная позиция n задана такой, что оставшаяся за ней часть исходной строки имеет длину, меньшую заданной длины l, или даже n превышает длину исходной строки. Возможные варианты такого правила:
аварийное завершение программы с диагностикой ошибки; формирование результата меньшей длины, чем задано, возможно даже - пустой строки.
Операция поиска вхождения находит место первого вхождения подстроки-эталона в исходную строку. Результатом операции может быть номер позиции в исходной строке, с которой начинается вхождение эталона или указатель на начало вхождения. В случае отсутствия вхождения результатом операции должно быть некоторое специальное значение, например, нулевой номер позиции или пустой указатель.
На основе базовых операций могут быть реализованы и любые другие, даже сложные операции над строками. Например, операция удаления из строки символов с номерами от n1 включительно n2 может быть реализована как последовательность следующих шагов:
выделение из исходной строки подстроки, начиная с позиции 1, длиной n1-1; выделение из исходной строки подстроки, начиная с позиции n2+1, длиной длина исходной строки - n2; сцепление подстрок, полученных на предыдущих шагах.
Впрочем, в целях повышения эффективности некоторые вторичные операции также могут быть реализованы как базовые - по собственным алгоритмам, с непосредственным доступом к физической структуре строки.
Представление строк в памяти.
4.5.3. Представление строк в памяти.
Представление строк в памяти зависит от того, насколько изменчивыми являются строки в каждой конкретной задаче, и средства такого представления варьируются от абсолютно статического до динамического. Универсальные языки программирования в основном обеспечивают работу со строками переменной длины, но максимальная длина строки должна быть указана при ее создании. Если программиста не устраивают возможности или эффективность тех средств работы со строками, которые предоставляет ему язык программирования, то он может либо определить свой тип данных "строка" и использовать для его представления средства динамической работы с памятью, либо сменить язык программирования на специально ориентированный на обработку текста (CNOBOL, REXX), в которых представление строк базируется на динамическом управлении памятью.
Связное представление данных в памяти
5.1. Связное представление данных в памяти
Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки. В этом разделе рассмотрены особенности динамических структур, определяемые их первым характерным свойством. Особенности, связанные со вторым свойством рассматриваются в последнем разделе данной главы.
Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Элемент динамической структуры состоит из двух полей:
информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой - вектором, массивом, записью и т.п.; поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;
Когда связное представление данных используется для решения прикладной задачи, для конечного пользователя "видимым" делается только содержимое информационного поля, а поле связок используется только программистом-разработчиком.
Достоинства связного представления данных - в возможности обеспечения значительной изменчивости структур;
размер структуры ограничивается только доступным объемом машинной памяти; при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей.
Вместе с тем связное представление не лишено и недостатков, основные из которых:
работа с указателями требует, как правило, более высокой квалификации от программиста; на поля связок расходуется дополнительная память; доступ к элементам связной структуры может быть менее эффективным по времени.
Последний недостаток является наиболее серьезным и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента и информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных. Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу. Поэтому связное представление практически никогда не применяется в задачах, где логическая структура данных имеет вид вектора или массива - с доступом по номеру элемента, но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, списки, деревья и т.д.).
Машинное представление связных линейных списков
5.2.1. Машинное представление связных линейных списков
На рис. 5.1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.
Реализация операций над связными линейными списками
5.2.2. Реализация операций над связными линейными списками
Ниже рассматриваются некоторые простые операции над линейными списками. Выполнение операций иллюстрируется в общем случае рисунками со схемами изменения связей и программными примерами.
На всех рисунках сплошными линиями показаны связи, имевшиеся до выполнения и сохранившиеся после выполнения операции. Пунктиром показаны связи, установленные при выполнении операции. Значком 'x' отмечены связи, разорванные при выполнении операции. Во всех операциях чрезвычайно важна последовательность коррекции указателей, которая обеспечивает корректное изменение списка, не затрагивающее другие элементы. При неправильном порядке коррекции легко потерять часть списка. Поэтому на рисунках рядом с устанавливаемыми связями в скобках показаны шаги, на которых эти связи устанавливаются.
В программных примерах подразумеваются определенными следующие типы данных:
любая структура информационной части списка:
type data = ...; элемент односвязного списка (sll - single linked list):
type sllptr = ^slltype; { указатель в односвязном списке } slltype = record { элемент односвязного списка } inf : data; { информационная часть } next : sllptr; { указатель на следующий элемент } end;
элемент двухсвязного списка (dll - double linked list):
type dllptr = ^dlltype; { указатель в двухсвязном списке } dlltype = record { элемент односвязного списка } inf : data; { информационная часть } next : sllptr; { указатель на следующий элемент (вперед) } prev : sllptr; { указатель на предыдущий элемент (назад) } end;
Словесные описания алгоритмов даны в виде комментариев к программным примерам.
В общем случае примеры должны были бы показать реализацию каждой операции для списков: односвязного линейного, одсвязного кольцевого, двухсвязного линейного, двухсвязного кольцевого. Объем нашего издания не позволяет привести полный набор примеров, разработку недостающих примеров мы предоставляем читателю.
Применение линейных списков
5.2.3. Применение линейных списков
Линейные списки находят широкое применение в приложениях, где непредсказуемы требования на размер памяти, необходимой для хранения данных; большое число сложных операций над данными, особенно включений и исключений. На базе линейных списков могут строится стеки, очереди и деки. Представление очереди с помощью линейного списка позволяет достаточно просто обеспечить любые желаемые дисциплины обслуживания очереди. Особенно это удобно, когда число элементов в очереди трудно предсказуемо.
В программном примере 5.8 показана организация стека на односвязном линейном списке. Это пример функционально аналогичен примеру 4.1 с той существенной разницей, что размер стека здесь практически неограничен.
Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Процедуры StackPush и StackPop сводятся к включению и исключению элемента в начало списка. Обратите внимание, что при включении элемента для него выделяется память, а при исключении - освобождается. Перед включением элемента проверяется доступный объем памяти, и если он не позволяет выделить память для нового элемента, стек считается заполненным. При очистке стека последовательно просматривается весь список и уничтожаются его элементы. При списковом представлении стека оказывается непросто определить размер стека. Эта операция могла бы потребовать перебора всего списка с подсчета числа элементов. Чтобы избежать последовательного перебора всего списка мы ввели дополнительную переменную stsize, которая отражает текущее число элементов в стеке и корректируется при каждом включении/исключении.
{==== Программный пример 5.8 ====} { Стек на 1-связном линейном списке } unit Stack; Interface type data = ...; { эл-ты могут иметь любой тип } Procedure StackInit; Procedure StackClr; Function StackPush(a : data) : boolean; Function StackPop(Var a : data) : boolean; Function StackSize : integer; Implementation type stptr = ^stit; { указатель на эл-т списка } stit = record { элемент списка } inf : data; { данные } next: stptr; { указатель на следующий эл-т } end; Var top : stptr; { указатель на вершину стека } stsize : longint; { размер стека } {** инициализация - список пустой } Procedure StackInit; begin top:=nil; stsize:=0; end; { StackInit } {** очистка - освобождение всей памяти } Procedure StackClr; var x : stptr; begin { перебор эл-тов до конца списка и их уничтожение } while top<>nil do begin x:=top; top:=top^.next; Dispose(x); end; stsize:=0; end; { StackClr } Function StackPush(a: data) : boolean; { занесение в стек } var x : stptr; begin { если нет больше свободной памяти - отказ } if MaxAvail < SizeOf(stit) then StackPush:=false else { выделение памяти для эл-та и заполнение инф.части } begin New(x); x^.inf:=a; { новый эл-т помещается в голову списка } x^.next:=top; top:=x; stsize:=stsize+1; { коррекция размера } StackPush:=true; end; end; { StackPush } Function StackPop(var a: data) : boolean; { выборка из стека } var x : stptr; begin { список пуст - стек пуст } if top=nil then StackPop:=false else begin a:=top^.inf; { выборка информации из 1-го эл-та списка } { 1-й эл-т исключается из списка, освобождается память } x:=top; top:=top^.next; Dispose(top); stsize:=stsize-1; { коррекция размера } StackPop:=true; end; end; { StackPop } Function StackSize : integer; { определение размера стека } begin StackSize:=stsize; end; { StackSize } END.
Программный пример для организация на односвязном линейном списке очереди FIFI разработайте самостоятельно. Для линейного списка, представляющего очередь, необходимо будет сохранять: top - на первый элемент списка, и bottom - на последний элемент.
Линейные связные списки иногда используются также для представления таблиц - в тех случаях, когда размер таблицы может существенно изменяться в процессе ее существования. Однако, то обстоятельство, что доступ к элементам связного линейного списка может быть только последовательным, не позволяет применить к такой таблице эффективный двоичный поиск, что существенно ограничивает их применимость. Поскольку упорядоченность такой таблицы не может помочь в организации поиска, задачи сортировки таблиц, представленных линейными связными списками, возникают значительно реже, чем для таблиц в векторном представлении. Однако, в некоторых случаях для таблицы, хотя и не требуется частое выполнение поиска, но задача генерации отчетов требует расположения записей таблицы в некотором порядке. Для упорядочения записей такой таблицы применимы любые алгоритмы из описанных нами в разделе 3.9. Некоторые алгоритмы, возможно, потребуют каких-либо усложнений структуры, например, быструю сортировку Хоара целесообразно проводить только на двухсвязном списке, в цифровой сортировке удобно создавать промежуточные списке для цифровых групп и т.д. Мы приведем два простейших примера сортировки односвязного линейного списка. В обоих случаях мы предполагаем, что определены типы данных:
type lptr = ^item; { указатель на элемент списка } item = record { элемент списка } key : integer; { ключ } inf : data; { данные } next: lptr; { указатель на элемент списка } end;
В обоих случаях сортировка ведется по возрастанию ключей. В обоих случаях параметром функции сортировки является указатель на начало неотсортированного списка, функция возвращает указатель на начало отсортированного списка. Прежний, несортированный список перестает существовать.
Пример 5.9 демонстрирует сортировку выборкой. Указатель newh является указателем на начало выходного списка, исходно - пустого. Во входном списке ищется максимальный элемент. Найденный элемент исключается из входного списка и включается в начало выходного списка. Работа алгоритма заканчивается, когда входной список станет пустым. Обратим внимание читателя на несколько особенностей алгоритма. Во-первых, во входном списке ищется всякий раз не минимальный, а максимальный элемент. Поскольку элемент включается в начало выходного списка (а не в конец выходного множества, как было в программном примере 3.7), элементы с большими ключами оттесняются к концу выходного списка и последний, таким образом, оказывается отсортированным по возрастанию ключей. Во-вторых, при поиске во входном списке сохраняется не только адрес найденного элемента в списке, но и адрес предшествующего ему в списке эле- мента - это впоследствии облегчает исключение элемента из списка (вспомните пример 5.4). В-третьих, обратите внимание на то, что у нас не возникает никаких проблем с пропуском во входном списке тех элементов, которые уже выбраны - они просто исключены из входной структуры данных.
{==== Программный пример 5.9 ====} { Сортировка выборкой на 1-связном списке } Function Sort(head : lptr) : lptr; var newh, max, prev, pmax, cur : lptr; begin newh:=nil; { выходной список - пустой } while head<>nil do { цикл, пока не опустеет входной список } begin max:=head; prev:=head; { нач.максимум - 1-й эл-т } cur:=head^.next; { поиск максимума во входном списке } while cur<>nil do begin if cur^.key>max^.key then begin { запоминается адрес максимума и адрес предыдущего эл-та } max:=cur; pmax:=prev; end; prev:=cur; cur:=cur^.next; { движение по списку } end; { исключение максимума из входного списка } if max=head then head:=head^.next else pmax^.next:=max^.next; { вставка в начало выходного списка } max^.next:=newh; newh:=max; end; Sort:=newh; end;
В программном примере 5.10 - иллюстрации сортировки вставками - из входного списка выбирается (и исключается) первый элемент и вставляется в выходной список "на свое место" в соответствии со значениями ключей. Сортировка включением на векторной структуре в примере 3.11 требовала большого числа перемещений элементов в памяти. Обратите внимание на то, что в двух последних примерах пересылок данных не происходит, все записи таблиц остаются на своих местах в памяти, меняются только связи между ними - указатели.
{==== Программный пример 5.10 ====} { Сортировка вставками на 1-связном списке } type data = integer; Function Sort(head : lptr) : lptr; var newh, cur, sel : lptr; begin newh:=nil; { выходной список - пустой } while head <> nil do begin { цикл, пока не опустеет входной список } sel:=head; { эл-т, который переносится в выходной список } head:=head^.next; { продвижение во входном списке } if (newh=nil) or (sel^.key < newh^.key) then begin {выходной список пустой или элемент меньше 1-го-вставка в начало} sel^.next:=newh; newh:=sel; end else begin { вставка в середину или в конец } cur:=newh; { до конца выходного списка или пока ключ следующего эл-та не будет больше вставляемого } while (cur^.next <> nil) and (cur^.next^.key < sel^.key) do cur:=cur^.next; { вставка в выходной список после эл-та cur } sel^.next:=cur^.next; cur^.next:=sel; end; end; Sort:=newh; end;
Связные линейные списки
5.2. Связные линейные списки
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Логические списки мы уже рассматривали в главе 4, но там речь шла о полустатических структурах данных и на размер списка накладывались ограничения. Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами данных.
Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем - nil.
Мультисписки
5.3. Мультисписки
В программных системах, обрабатывающих объекты сложной структуры, могут решаться разные подзадачи, каждая из которых требует, возможно, обработки не всего множества объектов, а лишь какого-то его подмножества. Так, например, в автоматизированной системе учета лиц, пострадавших вследствие аварии на ЧАЭС, каждая запись об одном пострадавшем содержит более 50 полей в своей информационной части. Решаемые же автоматизированной системой задачи могут потребовать выборки, например:
участников ликвидации аварии; переселенцев из зараженной зоны; лиц, состоящих на квартирном учете; лиц с заболеваниями щитовидной железы; и т.д., и т.п.
Основные понятия
5.4.1. Основные понятия
Нелинейным разветвленным списком является список, элементами которого могут быть тоже списки. В разделе 5.2 мы рассмотрели двухсвязные линейные списки. Если один из указателей каждого элемента списка задает порядок обратный к порядку, устанавливаемому другим указателем, то такой двусвязный список будет линейным. Если же один из указателей задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому другим указателем, то такой список будет нелинейным.
В обработке нелинейный список определяется как любая последовательность атомов и списков (подсписков), где в качестве атома берется любой объект, который при обработке отличается от списка тем, что он структурно неделим.
Если мы заключим списки в круглые скобки, а элементы списков разделим запятыми, то в качестве списков можно рассматривать такие последовательности:
(a,(b,c,d),e,(f,g)) ( ) ((a))
Первый список содержит четыре элемента: атом a, список (b,c,d) (содержащий в свою очередь атомы b,c,d), атом e и список (f,g), элементами которого являются атомы f и g. Второй список не содержит элементов, тем не менее нулевой список, в соответствии с нашим определением является действительным списком. Третий список состоит из одного элемента: списка (a), который в свою очередь содержит атом а.
Другой способ представления, часто используемый для иллюстрации списков, - графические схемы, аналогичен способу представления, применяемому при изображении линейных списков. Каждый элемент списка обозначается прямоугольником; стрелки или указатели показывают, являются ли прямоугольники элементами одного и того же списка или элементами подсписка. Пример такого представления дан на рис.5.12.
Представление списковых структур в памяти.
5.4.2. Представление списковых структур в памяти.
В соответствии со схематичным изображением разветвленных списков типичная структура элемента такого списка в памяти должна быть такой, как показано на рис.5.14.
Операции обработки списков
5.4.3. Операции обработки списков
Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom.
Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент). Например:
если X - список (2,6,4,7), то car(X) - атом 2; если X - список ((1,2),6), то car(X) - список (1,2); если X - атом то car(X) не имеет смысла и в действительности не определено.
Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:
если X - (2,6,4), то cdr(X) - (6,4); если X - ((1,2),6,5), то cdr(X) - (6,5); если список X содержит один элемент, то cdr(X) равно nil.
Операция cons имеет два аргумента: указатель на элемент списка и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список. Например:
если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7); если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).
Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение: true - если ее аргумент является атомом или false - если ее аргумент является подсписком.
В программном примере 5.11 приведена реализация описанных операций как функций языка PASCAL. Структура элемента списка, обрабатываемого функциями этого модуля определена в нем как тип litem и полностью соответствует рис.5.16. Помимо описанных операций в модуле определены также функции выделения памяти для дескриптора данных - NewAtom и для элемента списка - NewNode. Реали- зация операций настолько проста, что не требует дополнительных пояснений.
{==== Программный пример 5.11 ====} { Элементарные операции для работы со списками } Unit ListWork; Interface type lpt = ^litem; { указатель на элемент списка } litem = record typeflg : char; { Char(0) - узел, иначе - код типа } down : pointer; { указатель на данные или на подсписок } next: lpt; { указатель на текущем уровне } end; Function NewAtom(d: pointer; t : char) : lpt; Function NewNode(d: lpt) : lpt; Function Atom(l : lpt) : boolean; Function Cdr(l : lpt) : lpt; Function Car(l : lpt) : lpt; Function Cons(l1, l : lpt) : lpt; Function Append(l1,l : lpt) : lpt; Implementation {*** создание дескриптора для атома } Function NewAtom(d: pointer; t : char) : lpt; var l : lpt; begin New(l); l^.typeflg:=t; { тип данных атома } l^.down:=d; { указатель на данные } l^.next:=nil; NewAtom:=l; end; {*** создание элемента списка для подсписка } Function NewNode(d: lpt) : lpt; var l : lpt; begin New(l); l^.typeflg:=Chr(0); { признак подсписка } l^.down:=d; { указатель на начало подсписка } l^.next:=nil; NewNode:=l; end; {*** проверка элемента списка: true - атом, false - подсписок } Function Atom(l : lpt) : boolean; begin { проверка поля типа } if l^.typeflg=Chr(0) then Atom:=false else Atom:=true; end; Function Car(l : lpt) : lpt; {выборка 1-го элемента из списка } begin Car:=l^.down; { выборка - указатель вниз } end; Function Cdr(l : lpt) : lpt;{исключение 1-го элемента из списка} begin Cdr:=l^.next; { выборка - указатель вправо } end; {*** добавление элемента в начало списка } Function Cons(l1,l : lpt) : lpt; var l2 : lpt; begin l2:=NewNode(l1); { элемент списка для добавляемого } l2^.next:=l; { в начало списка } Cons:=l2; { возвращается новое начало списка } end; {*** добавление элемента в конец списка } Function Append(l1,l : lpt) : lpt; var l2, l3 : lpt; begin l2:=NewNode(l1); { элемент списка для добавляемого } { если список пустой - он будет состоять из одного эл-та } if l=nil then Append:=l2 else begin { выход на последний эл-т списка } l3:=l; while l3^.next <> nil do l3:=l3^.next; l3^.next:=l2; { подключение нового эл-та к последнему } Append:=l; { функция возвращает тот же указатель } end; end; END.
В примере 5.11 в модуль базовых операций включена функция Append - добавления элемента в конец списка. На самом деле эта операция не является базовой, она может быть реализована с использованием описанных базовых операций, без обращения к внутренней структуре элемента списка, хотя, конечно, такая реализация будет менее быстродействующей. В программном примере 5.12 приведена реализация нескольких простых функций обработки списков, которые могут быть полезными при решении широкого спектра задач. В функциях этого модуля, однако, не используется внутренняя структура элемента списка.
{==== Программный пример 5.12 ====} { Вторичные функции обработки списков } Unit ListW1; Interface uses listwork; Function Append(x, l : lpt) : lpt; Function ListRev(l, q : lpt) : lpt; Function FlatList(l, q : lpt) : lpt; Function InsList(x, l : lpt; m : integer) : lpt; Function DelList(l : lpt; m : integer) : lpt; Function ExchngList(l : lpt; m : integer) : lpt; Implementation {*** добавление в конец списка l нового элемента x } Function Append(x, l : lpt) : lpt; begin { если список пустой - добавить x в начало пустого списка } if l=nil then Append:=cons(x,l) { если список непустой - взять тот же список без 1-го эл-та - cdr(l); - добавить в его конец эл-т x; - добавить в начало 1-й эл-т списка } else Append:=cons(car(l),Append(x,cdr(l))); end; { Function Append } {*** Реверс списка l; список q - результирующий, при первом вызове он должен быть пустым } Function ListRev(l, q : lpt) : lpt; begin { если входной список исчерпан, вернуть выходной список } if l=nil then ListRev:=q { иначе: - добавить 1-й эл-т вх.списка в начало вых.списка, - реверсировать, имея вх. список без 1-го эл-та, а вых.список - с добавленным эл-том } else ListRev:=ListRev(cdr(l),cons(car(l),q)); end; { Function ListRev } {*** Превращение разветвленного списка l в линейный; список q - результирующий, при первом вызове он должен быть пустым } Function FlatList(l, q : lpt) : lpt; begin { если входной список исчерпан, вернуть выходной список } if l=nil then FlatList:=q else { если 1-й эл-т вх. списка - атом, то - сделать "плоской" часть вх. списка без 1-го эл-та; - добавить в ее начало 1-й эл-т } if atom(car(l)) then FlatList:=cons(car(l),FlatList(cdr(l),q)) { если 1-й эл-т вх. списка - подсписок, то - сделать "плоской" часть вх.списка без 1-го эл-та; - сделать "плоским" подсписок 1-го эл-та } else FlatList:=FlatList(car(l),FlatList(cdr(l),q)); end; { Function FlatList } {*** вставка в список l элемента x на место с номером m ( здесь и далее нумерация эл-тов в списке начинается с 0 ) } Function InsList(x, l : lpt; m : integer) : lpt; begin { если m=0, эл-т вставляется в начало списка } if m=0 then InsList:=cons(x,l) { если список пустой, он и остается пустым } else if l=nil then InsList:=nil { - вставить эл-т x на место m-1 в список без 1-го эл-та; - в начало полученного списка вставить 1-й эл-т } else InsList:=cons(car(l),InsList(x,cdr(l),m-1)); end; { Function InsList } {*** удаление из списка l на месте с номером m } Function DelList(l : lpt; m : integer) : lpt; begin { если список пустой, он и остается пустым } if l=nil then DelList:=nil { если m=0, эл-т удаляется из начала списка } else if m=0 then DelList:=cdr(l) { - удалить эл-т x на месте m-1 в список без 1-го эл-та; - в начало полученного списка вставить 1-й эл-т } else DelList:=cons(car(l),DelList(cdr(l),m-1)); end; { Function DelList } {*** перестановка в списке l эл-тов местах с номерами m и m+1 } Function ExchngList(l : lpt; m : integer) : lpt; begin { если список пустой, он и остается пустым } if l=nil then ExchngList:=nil else if m=0 then {если m=0, а следующего эл-та нет, список остается без изменений} if cdr(l)=nil then ExchngList:=l { если m=0 ( обмен 0-го и 1-го эл-тов): - берется список без двух 1-ых эл-тов - cdr(cdr(l)); - в его начало добавляется 0-й эл-т; - в начало полученного списка добавляется 1-й эл-т - car(cdr(l))} else ExchngList:= cons(car(cdr(l)),cons(car(l),cdr(cdr(l)))) else ExchngList:=cons(car(l),ExchngList(cdr(l),m-1)); end; { Function ExchngList } END.
Для облегчения читателю задачи самостоятельного исследования примера первые две его функции мы разберем подробно. Поскольку в функциях этого примера широко используются вложенные вызовы, в том числе и рекурсивные, в нижеследующих разборах описание каждого следующего вложенного вызова сдвигается вправо.
Функция Append добавляет элемент x в конец списка l. Рассмотрим ее выполнение на примере вызова: Append(4,(1,2,3)).
Поскольку аргумент-список не пустой, выполняется ветвь else. Она содержит оператор:
Append:=cons(car(l),Append(x,cdr(l)));
Важно точно представить себе последовательность действий по выполнению этого оператора:
car(l) = 1; cdr(l) = (2,3); Append(4,(2,3))) - при этом рекурсивном вызове выполнение вновь пойдет по ветви else, в которой:
car(l) = 2; cdr(l) = (3); Append(4,(3))) - выполнение вновь пойдет по ветви else, в которой:
car(l) = 3; cdr(l) = nil; Append(4,nil) - в этом вызове список-аргумент пустой, поэтому выполнится Append:=cons(4,nil) и вызов вернет список: (4); cons(car(l),Append(x,cdr(l))) - значения аргументов функции cons - для этого уровня вызовов: cons(3,(4)) = (3,4); на этом уровне Append возвращает список (3,4); cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(2,(3,4)) = (2,3,4); на этом уровне Append возвращает список (2,3,4); cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(1,(2,3,4)) = (1,2,3,4); на этом уровне Append возвращает список (1,2,3,4).
Функция ListRev выполняет инвертирование списка - изменения порядка следования его элементов на противоположный. При обращении к функции ее второй аргумент должен иметь значение nil. Пример: ListRev(1,(2,3),4),nil).
Входной список не пустой, поэтому выполнение идет по ветви else, где:
ListRev:=ListRev(cdr(l),cons(car(l),q));
Последовательность действий:
cdr(l) = ((2,3),4); car(l) = 1; cons(car(l),q) = (1) - список q при этом - пустой; рекурсивный вызов ListRev( ((2,3),4), (1)):
cdr(l) = (4); car(l) = (2,3); cons(car(l),q) = ((2,3),1) - список q - (1); рекурсивный вызов ListRev((4), ((2,3),1)):
cdr(l) = nil; car(l) = 4; cons(car(l),q) = (4,(2,3),1); рекурсивный вызов ListRev(nil, (4,(2,3),1)):
поскольку исходный список пустой, вызов возвращает список: (4,(2,3),1);
вызов возвращает список: (4,(2,3),1);
вызов возвращает список: (4,(2,3),1);
вызов возвращает список: (4,(2,3),1).
В программном примере 5.13 применение ветвящихся списков показано для решения более прикладной задачи. Представленная здесь программа - калькулятор, она вычисляет значение введенного арифметического выражения, составляющими которого могут быть целые числа, знаки четырех арифметических операций и круглые скобки. Для упрощения примера мы ввели следующие ограничения:
вся арифметика - целочисленная; программа не проверяет правильность исходной записи; в выражении не допускается унарный минус.
{==== Программный пример 5.13 ====} { Калькулятор. Вычисление арифметических выражений } program Calc; Uses ListWork; type cptr = ^char; iptr = ^ integer; const { цифровые символы } digits : set of char = ['0'..'9']; { знаки операций с высоким приоритетом } prty : set of char = ['*','/']; var s : string; { исходная строка } n : integer; { номер текущего символа в исх. строке } {*** Представление исходной строки в списочной форме } Function Creat_Lst : lpt; var lll : lpt; { указатель на начало текущего списка } s1 : char; { текущий символ строки } st : string; { накопитель строки-операнда } {* Создание атома для Integer } Procedure NewInt; var ip : iptr; cc : integer; begin if Length(st) > 0 then begin { если в st накоплено цифровое представление числа, оно переводится в тип integer, для него создается атом и записывается в конец списка } New(ip); Val(st,ip^,cc); lll:=Append(NewAtom(ip,'I'),lll); st:=''; { накопитель строки сбрасывается } end; end; { Procedure NewInt } Procedure NewChar; { Создание атома для Char } var cp : cptr; begin { выделяется память для 1 символа, в ней сохраняется значение s1, для него создается атом, записывается в конец списка} New(cp); cp^:=s1; lll:=Append(NewAtom(cp,'C'),lll); end; { Procedure NewChar } begin { Function Creat_Lst } { исходный список пустой, накопитель строки - пустой } lll:=nil; st:=''; while n nil do begin { до опустошения исходного списка } { выделение знака операции } op:=car(l); l:=cdr(l); { выделение 2-го операнда } op2:=car(l); l:=cdr(l); { если 2-й операнд - подсписок - обработка подсписка } if not atom(op2) then op2:=FormPrty(op2); if cptr(op^.down)^ in prty then { если знак операции приоритетный, то создается подсписок: 1-й операнд, знак, 2-й операнд, этот подсписок далее является 1-ым операндом } op1:=cons(op1,cons(op,cons(op2,nil))) else begin { если знак неприоритетный, 1-й операнд и знак записываются в выходной список, 2-й операнд далее является 1-ым операндом } l2:=Append(op,Append(op1,l2)); op1:=op2; end; end; FormPrty:=Append(op1,l2); { последний операнд добавляется в выходной список } end; { Function FormPrty } {*** Вычисление выражения } Function Eval(l : lpt) : integer; var op1, op, op2 : lpt; begin { выделение 1-го операнда } op1:=car(l); l:=cdr(l); { если 1-й операнд - подсписок - вычислить его выражение } if not atom(op1) then iptr(op1^.down)^:=Eval(op1); while l <> nil do begin { выделение знака операции } op:=car(l); l:=cdr(l); { выделение 2-го операнда } op2:=car(l); l:=cdr(l); { если 2-й операнд - подсписок - вычислить его выражение } if not atom(op2) then iptr(op2^.down)^:=Eval(op2); { выполнение операции, результат - в op1 } case cptr(op^.down)^ of '+' : iptr(op1^.down)^:=iptr(op1^.down)^+iptr(op2^.down)^; '-' : iptr(op1^.down)^:=iptr(op1^.down)^-iptr(op2^.down)^; '*' : iptr(op1^.down)^:=iptr(op1^.down)^*iptr(op2^.down)^; '/' : iptr(op1^.down)^:=iptr(op1^.down)^ div iptr(op2^.down)^; end; end; Eval:=iptr(op1^.down)^; { возврат последнего результата } end; { Function Eval } {*** Главная программа } var l : lpt; begin write('>'); readln(s); { ввод исходной строки } { формирование списка } n:=1; l:=Creat_Lst; { выделение приоритетных операций } l:=FormPrty(l); { вычисление и печать результата } writeln(s,'=',Eval(l)); END.
Выполнение программы состоит во вводе строки, представляющей исходное выражение и последовательных обращений к трем функциям: Creat_Lst, FormPrty и Eval.
Функция Creat_Lst преобразует исходную строку в список. В функции поэлементно анализируются символы строки. Различаемые символы: левая круглая скобка, правая скобка, знаки операций и цифры. Цифровые символы накапливаются в промежуточной строке. Когда встречается символ-разделитель - правая скобка или знак операции накопленная строка преобразуется в число, для него создается атом с типом 'I' и включается в конец списка. Для знака операции создается атом с типом 'C' и тоже включается в конец списка. Левая скобка приводит к рекурсивному вызову Creat_Lst. Этот вызов формирует список для подвыражения в скобках, формирование списка заканчивается при появлении правой скобки. Для сформированного таким образом списка создается узел, и он включается в основной список как подсписок. Так, например, для исходной строки:
5+12/2-6*(11-7)+4
функцией Creat_Lst будет сформирован такой список:
(5,+,12,/,2,-,6,*,(11,-,7),+,4)
Следующая функция - FormPrty - выделяет в отдельные подсписки операции умножения и деления, имеющие более высокий приоритет, и их операнды. Функция просматривает список и выделяет в нем последовательные тройки элементов "операнд-знак-операнд". Если один из операндов является подсписком, то он обрабатывается функцией FormPrty. Если знак является одним из приоритетных знаков, то из тройки формируется подсписок, который становится первым операндом для следующей тройки. Если знак не приоритетный, то второй операнд тройки становится первым для следующей тройки. Список нашего примера после обработки его функцией FormPrty превратится в:
(5,+,(12,/,2),-,(6,*,(11,-,7)),+,4)
Наконец, функция Eval выполняет вычисления. Она во многом похожа на функцию FormPrty: в ней также выделяются тройки "операнд 1- 0знак-операнд". Если один или оба операнда являются подсписками, то сначала вычисляются эти подсписки и заменяются на атомы - результаты вычисления. Если оба операнда - атомы, то над ними выполняется арифметика, задаваемая знаком операции. Поскольку в первую очередь вычисляются подсписки, то подвыражения, обозначен- ные скобками в исходной строке, и операции умножения и деления выполняются в первую очередь. Для нашего примера порядок вычислений будет таков:
12 / 2 = 6; 5 + 6 = 11; 11 - 7 = 4; 6 * 4 = 24; 24 + 4 = 28; 11 - 28 = -17
Язык программирования lisp
5.5. Язык программирования LISP
LISP является наиболее развитым и распространенным языком обработки списков. "Идеология" и терминология этого языка в значительной степени повлияла на общепринятые подходы к обработке списков и использовалась и нами в предыдущем изложении. Все данные в LISP представляются в виде списков, структура элементсписка соответствует рис.5.15. LISP обеспечивает базовые функции обработки списков - car, cdr, cons, atom. Также многие вторичные функции реализованы в языке как базовые - для повышения их эффективности. Помимо чисто списковых операций в языке обеспечиваются операции для выполнения арифметических, логических операций, отношения, присваивания, ввода-вывода и т.д. Операция cond обеспечивает ветвление.
Сама LISP-программа представляется как список, записанный в скобочной форме. Элементами простого программного списка является имя операции/функции и ее параметры. Параметрами могут быть в свою очередь обращения к функциям, которые образуют подсписки. Как правило, вся программа на LISP представляет собой единственное обращение к функции с множеством вложенных обращений - рекурсивных или к другим функциям. Поэтому программирование на языке LISP часто называют "функциональным программированием". Функции, приведенные нами в примере 5.11 являются переложением на язык PASCAL их LISP-реализаций.
Системы программирования LISP строятся и как компиляторы, и как интерпретаторы. Однако, независимо от подхода к построению системы программирования, она обязательно включает в себя "сборку мусора" (см.раздел 5.7). Обратите внимание на то, что в примере 5.11, представляя PASCAL-реализацию операций языка LISP, мы в некоторых функциях выделяли память, но нигде ее не освобождали. Система программирования LISP автоматически следит за использованием памяти и обеспечивает ее освобождение.
Другие языки обработки списков, например IPL-V, COMMIT в большей мере ориентированы на решение прикладных задач, а не на обработку абстрактных списков, хотя использование списковых структур заложено в основы в их реализации.
Управление динамически выделяемой памятью
5.6. Управление динамически выделяемой памятью
Динамические структуры по определению характеризуется непостоянством и непредсказуемостью размера. Поэтому память под отдельные элементы таких структур выделяется в момент, когда они "начинают существовать" в процессе выполнения программы, а не вовремя трансляции. Когда в элементе структуры больше нет необходимости, занимаемая им память освобождается.
В современных вычислительных средах большая часть вопросов, связанных с управлением памятью решается операционными системами или системами программирования. Для программиста прикладных задач динамическое управление памятью либо вообще прозрачно, либо осуществляется через достаточно простой и удобный интерфейс стандартных процедур/функций. Однако, перед системным программистом вопросы управления памятью встают гораздо чаще. Во-первых, эти вопросы в полном объеме должны быть решены при проектировании операционных систем и систем программирования, во-вторых, некоторые сложные приложения могут сами распределять память в пределах выделенного им ресурса, наконец в-третьих, знание того, как в данной вычислительной среде распределяется память, позволит программисту построить более эффективное программное изделие даже при использовании интерфейса стандартных процедур.
В общем случае при распределении памяти должны быть решены следующие вопросы:
способ учета свободной памяти; дисциплины выделения памяти по запросу; обеспечение утилизации освобожденной памяти.
В распоряжении программы обычно имеется адресное пространство, которое может рассматриваться как последовательность ячеек памяти с адресами, линейно возрастающими от 0 до N. Какие-то части этого адресного пространства обычно заняты системными программами и данными, какие-то - кодами и статическими данными самой программы, оставшаяся часть доступна для динамического распределения. Обычно доступная для распределения память представляет собой непрерывный участок пространства с адресными границами от n1 до n2. В управлении памятью при каждом запросе на память необходимо решать, по каким адресам внутри доступного участка будет располагаться выделяемая память.
В некоторых системах программирования выделение памяти автоматизировано полностью: система не только сама определяет адрес выделяемой области памяти, но и определяет момент, когда память должна выделяться. Так, например, выделяется память под элементы списков в языке LISP, под символьные строки в языках SNOBOL и REXX. В других системах программирования - к ним относится большинство универсальных процедурных языков программирования - моменты выделения и освобождения памяти определяются программистом. Программист должен выдать запрос на выделение/освобождение памяти при помощи стандартной процедуры/функции - ALLOCATE/FREE в PL/1, malloc/free в C, New/Dispose в PASCAL и т.п. Система сама определяет размещение выделяемого блока и функция выделения памяти возвращает его адрес. Наконец, в уже названных выше задачах системного программирования программист зачастую должен определить также и адрес выделяемой области.
Память всегда выделяется блоками - т.е. обязательно непрерывными последовательностями смежных ячеек. Блоки могут быть фиксированной или переменной длины. Фиксированный размер блока гораздо удобнее для управления: в этом случае вся доступная для распределения память разбивается на "кадры", размер каждого из которых равен размеру блока, и любой свободный кадр годится для удовлетворения любого запроса. К сожалению, лишь ограниченный круг реальных задач может быть сведен к блокам фиксированной длины.
Одной из проблем, которые должны приниматься во внимание при управлении памятью является проблема фрагментации (дробления) памяти. Она заключается в возникновении "дыр" - участков памяти, которые не могут быть использованы. Различаются дыры внутренние и внешние. Внутренняя дыра - неиспользуемая часть выделенного блока, она возникает, если размер выделенного блока больше запрошенного. Внутренние дыры характерны для выделения памяти блоками фиксированной длины. Внешняя дыра - свободный блок, который в принципе мог бы быть выделен, но размер его слишком мал для удовлетворения запроса. Внешние дыры характерны для выделения блоками переменной длины. Управление памятью должно быть построено таким образом, чтобы минимизировать суммарный объем дыр.
Система управления памятью должна прежде всего "знать", какие ячейки имеющейся в ее распоряжении памяти свободны, а какие - заняты. Методы учета свободной памяти основываются либо на принципе битовой карты, либо на принципе списков свободных блоков.
В методах битовой карты создается "карта" памяти - массив бит, в котором каждый однобитовый элемент соответствует единице доступной памяти и отражает ее состояние: 0 - свободна, 1 - занята. Если считать единицей распределения единицу адресации - байт, то сама карта памяти будет занимать 1/8 часть всей памяти, что делает ее слишком дорогостоящей. Поэтому при применении методов битовой карты обычно единицу распределения делают более крупной, например, 16 байт. Карта, таким образом, отражает состояние каждого 16-байтного кадра. Карта может рассматриваться как строка бит, тогда поиск участка памяти для выделения выполняется как поиск в этой строке подстроки нулей требуемой длины.
В другой группе методов участки свободной памяти объединяются в связные списки. В системе имеется переменная, в которой хранится адрес первого свободного участка. В начале первого свободного участка записывается его размер и адрес следующего свободного участка. В простейшем случае список свободных блоков никак не упорядочивается. Поиск выполняется перебором списка.
Дисциплины выделения памяти решают вопрос: какой из свободных участков должен быть выделен по запросу. Выбор дисциплины распределения не зависит от способа учета свободной памяти. Две основные дисциплины сводятся к принципам "самый подходящий" и "первый подходящий". По дисциплине "самый подходящий" выделяется тот свободный участок, размер которого равен запрошенному или превышает его на минимальную величину. По дисциплине "первый подходящий" выделяется первый же найденный свободный участок, размер которого не меньше запрошенного. При применении любой дисциплины, если размер выбранного для выделения участка превышает запрос, выделяется запрошенный объем памяти, а остаток образует свободный блок меньшего размера. В некоторых системах вводится ограничение на минимальный размер свободного блока: если размер остатка меньше некоторого граничного значения, то весь свободный блок выделяется по запросу без остатка. Практически во всех случаях дисциплина "первый подходящий" эффективнее дисциплины "самый подходящий". Это объясняется во-первых, тем, что при поиске первого подходящего не требуется просмотр всего списка или карты до конца, во-вторых, тем, что при выборе всякий раз "самого подходящего" остается больше свободных блоков маленького размера - внешних дыр.
Когда в динамической структуре данных или в отдельном ее элементе нет больше необходимости, занимаемая ею память должна быть утилизована, т.е. освобождена и сделана доступной для нового распределения. В тех системах, где память запрашивается программистом явным образом, она и освобождена должна быть явным образом. Даже в некоторых системах, где память выделяется автоматически, она освобождается явным образом (например, операция DROP в языке REXX). В таких системах, конечно, задача утилизации решается просто. При представлении памяти на битовой карте достаточно просто сбросить в 0 биты, соответствующие освобожденным кадрам. При учете свободной памяти списками блоков освобожденный участок должен быть включен в список, но одного этого недостаточно. Следует еще позаботиться о том, чтобы при образовании в памяти двух смежных свободных блоков они слились в один свободный блок суммарного размера. Задача слияния смежных блоков значительно упрощается при упорядочении списка свободных блоков по адресам памяти - тогда смежные блоки обязательно будут соседними элементами этого списка.
Задача утилизации значительно усложняется в системах, где нет явного освобождения памяти: тогда на систему ложится задача определения того, какие динамические структуры или их элементы уже не нужны программисту. Один из методов решения этой задачи предполагает, что система не приступает к освобождению памяти до тех пор, пока свободной памяти совсем не останется. Затем все зарезервированные блоки проверяются и освобождаются те из них, которые больше не используются. Такой метод называется "сборкой мусора". Программа, сборки мусора вызывается тогда, когда нет возможности удовлетворить некоторый частный запрос на память, или когда размер доступной области памяти стал меньше некоторой заранее определенной границы. Алгоритм сборки мусора обычно бывает двухэтапным. На первом этапе осуществляется маркировка (пометка) всех блоков, на которые указывает хотя бы один указатель. На втором этапе все неотмеченные блоки возвращаются в свободный список, а метки стираются. Важно, чтобы в момент включения сборщика мусора все указатели были установлены на те блоки, на которые они должны указывать. Если необходимо в некоторых алгоритмах применять методы с временным рассогласованием указателей, необходимо временно отключить сборщик мусора - пока имеется такое рассогласование. Один из самых серьезных недостатков метода сборки мусора состоит в том, что расходы на него увеличиваются по мере уменьшения размеров свободной области памяти.
Другой метод - освобождать любой блок, как только он перестает использоваться. Он обычно реализуется посредством счетчиков ссылок - счетчиков, в которых записывается, сколько указателей на данный блок имеется в данный момент времени. Когда значение счетчика становится равным 0, соответствующий блок оказывается недоступным и, следовательно, не используемым. Блок возвращается в свободный список. Такой метод предотвращает накопление мусора, не требует большого числа оперативных проверок во время обработки данных. Однако и у этого метода есть определенные недостатки. Вопервых, если зарезервированные блоки образуют циклическую структуру, то счетчик ссылок каждого из них не равен 0, когда все связи, идущие извне блоков в циклическую структуру, будут уничтожены. Это приводит к появлению мусора. Существуют различные возможности устранить этот недостаток: запретить циклические и рекурсивные структуры; отмечать циклические структуры флажками, и обрабатывать их особым образом; потребовать, чтобы любая циклическая структура всегда имела головной блок, счетчик циклов которого учитывал бы только ссылки от элементов, расположенных вне цикла, и чтобы доступ ко всем блокам этой структуры осуществлялся только через него. Во-вторых, требуются лишние затраты времен и памяти на ведение счетчиков ссылок.
В некоторых случаях может быть полезен метод восстановления ранее зарезервированной памяти, называемый уплотнением. Уплотнение осуществляется путем физического передвижения блоков данных с целью сбора всех свободных блоков в один большой блок. Преимущество этого метода в том, что после его применения выделение памяти по запросам упрощается. Единственная серьезная проблема, возникающая при использовании метода - переопределение указателей. Механизм уплотнения использует несколько просмотров памяти. Сначала определяются новые адреса всех используемых блоков, которые были отмечены в предыдущем проходе, а затем во время следующего просмотра памяти все указатели, связанные с отмеченными блоками, переопределяются. После этого отмеченные блоки переставляются. Механизма освобождения памяти в методе восстановления совсем нет. Вместо него используется механизм маркировки, который отмечает блоки, используемые в данный момент. Затем, вместо того, чтобы освобождать каждый не отмеченный блок путем введения в действие механизма освобождения памяти, помещающего этот блок в свободный список, используется уплотнитель, который собирает неотмеченные блоки в один большой блок в одном конце области памяти. Недостаток метода в том, что из-за трех просмотров памяти велики затраты времени. Однако повышенная скорость резервирования в определенных условиях может компенсировать этот недостаток.
Практическая эффективность методов зависит от многих параметров, таких как частота запросов, статистическое распределение размеров запрашиваемых блоков, способ использования системы - групповая обработка или стратегия обслуживания при управлении вычислительным центром.
Логическая структура, определения
6.1.1. Логическая структура, определения
Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.
Многосвязная структура обладает следующими свойствами:
1) на каждый элемент (узел, вершину) может быть произвольное количество ссылок; 2) каждый элемент может иметь связь с любым количеством других элементов; 3) каждая связка (ребро, дуга) может иметь направление и вес.
В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.
Граф, все связи которого ориентированные, называется ориентированным графом или орграфом; граф со всеми неориентированными связями - неориентированным графом; граф со связями обоих типов - смешанным графом. Обозначение связей: неориентированных - (A,B), ориентированных - . Примеры изображений графов даны на рис.6.1. Скобочное представление графов рис.6.1:
а).((A,B),(B,A)) и б).(< A,B >,< B,A >).
Машинное представление оpгpафов
6.1.2. Машинное представление оpгpафов
Существуют два основных метода представления графов в памяти ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зависит от природы данных и операций, выполняемых над ними. Если задача требует большого числа включений и исключений узлов, то целесообразно представлять граф связными списками; в противном случае можно применить и матричное представление.
Основные определения
6.2.1. Основные определения
Дерево - это граф, который характеризуется следующими свойствами:
1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ (рис. 6.8, 6.9 - A,G,M - корни). 2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры. 3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.
Название "дерево" проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами)(рис. 6.8, 6.9 - b,k,l,h - листья). Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).
Для ориентированного графа число ребер, исходящих из некоторой начальной вершины V, называется ПОЛУСТЕПЕНЬЮ ИСХОДА этой вершины. Число ребер, для которых вершина V является конечной, называется ПОЛУСТЕПЕНЬЮ ЗАХОДА вершины V, а сумма полустепеней исхода и захода вершины V называется ПОЛНОЙ СТЕПЕНЬЮ этой вершины.
Логическое представление и изображение деревьев.
6.2.2. Логическое представление и изображение деревьев.
Имеется ряд способов графического изображения деревьев. Первый способ заключается в использовании для изображения поддеревьев известного метода диаграмм Венна, второй - метода вкладывающихся друг в друга скобок, третий способ - это способ, применяемый при составлении оглавлений книг. Последний способ, базирующийся на формате с нумерацией уровней, сходен с методами, используемыми в языках программирования. При применении этого формата каждой вершине приписывается числовой номер, который должен быть меньше номеров, приписанных корневым вершинам присоединенных к ней поддеревьев. Отметим, что корневые вершины всех поддереьев данной вершины должны иметь один и тот же номер.
Бинарные деревья.
6.2.3. Бинарные деревья.
Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой вершины в точности равна либо m, либо нулю, то такое дерево называется ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ.
При m=2 такие деревья называются соответственно БИНАРНЫМИ, или ПОЛНЫМИ БИНАРНЫМИ.
На рисунке 6.12(a) изображено бинарное дерево, 6.12(b)- полное бинарное дерево, а на 6.12(c) показаны все четыре возможных расположения сыновей некоторой вершины бинарного дерева.
Представление любого дерева, леса бинарными деревьями.
6.2.4. Представление любого дерева, леса бинарными деревьями.
Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево.
Правило построения бинарного дерева из любого дерева:
1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение); 2. Соединить горизонтальными ребрами всех братьев одного отца; 3. Таким образом перестроить дерево по правилу:
левый сын - вершина, расположенная под данной; правый сын - вершина, расположенная справа от данной (т.е. на одном ярусе с ней).
4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыновей, а горизонтальные - правых.
В результате преобразования любого дерева в бинарное получается дерево в виде левого поддерева, подвешенного к корневой вершине.
В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NIL.
Машинное представление деревьев в памяти эвм.
6.2.5. Машинное представление деревьев в памяти ЭВМ.
Деревья можно представлять с помощью связных списков и массивов (или последовательных списков).
Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от отца к сыновьям. В бинарном дереве имеется два указателя, поэтому удобно узел представить в виде структуры:
где LPTR - указатель на левое поддерево, RPTR - указатель на правое поддерево, DATA - содержит информацию, связанную с вершиной.
Рассмотрим машинное представление бинарного дерева, изображенного на рис. 6.20.
Основные операции над деревьями.
6.2.6. Основные операции над деревьями.
Над деревьями определены следующие основные операции, для которых приведены реализующие их программы.
1) Поиск узла с заданным ключом ( Find ). 2) Добавление нового узла ( Dob ). 3) Удаление узла ( поддерева ) ( Udal ). 4) Обход дерева в определенном порядке:
Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder); Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder); Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).
Приведенные ниже программы процедур и функций могут быть непосредственно использованы при решении индивидуальных задач. Кроме выше указанных процедур приведены следующие процедуры и функции:
процедура включения в стек при нисходящем обходе (Push_st); функция извлечения из стека при нисходящем обходе (Pop_st); процедура включения в стек при восходящем и смешанном обходе (S_Push); функция извлечения из стека при восходящем и смешанном обходе (S_Pop).
Для прошитых деревьев:
функция нахождения сына данного узла ( Inson ); функция нахождения отца данного узла ( Inp ); процедура включения в дерево узла слева от данного (leftIn);
Приложения деревьев.
6.2.7. Приложения деревьев.
Деревья имеют широкое применение при реализации трансляторов таблиц решений, при работе с арифметическими выражениями, при создании и ведении таблиц символов, где их используют для отображения структуры предложений, в системах связи для экономичного кодирования сообщений и во многих других случаях. Рассмотрим некоторые из них.
деревья хаффмена (деревья минимального кодирования)
6.2.8 Деревья Хаффмена (деревья минимального кодирования)
Пусть требуется закодировать длинное сообщение в виде строки битов: А В А С С D А кодом, минимизирующим длину закодированного сообщения.
1) назначим коды:
Символ | Код |
A | 010 |
B | 100 |
C | 000 |
D | 111 |
Каждый символ тремя битами, получим строку :010 100 010 000 000 111 010.
А В А С С D А
7*3=21 всего 21 бит - неэффективно
2) Сделаем иначе: предположим, что каждому символу назначен 2-битовый код
Символ | Код |
A | 00 |
B | 01 |
C | 10 |
D | 11 |
00 01 00 10 10 11 00
А В А С С D А
Тогда кодировка требует лишь 14 бит.
3) Выберем коды, которые минимизируют длину сообщения по частоте вхождений символа в строку: много вхождений - код короткий, мало вхождений - код длинный.
А -3 раза, С -2 раза, В -1 раз, D -1 раз то-есть можно:
1. использовать коды переменной длины. 2. код одного символа не должен совпадать с кодом другого (раскодирование идет слева направо).
Если А имеет код 0 т.к часто встречается, то В, С, D - начинаются с 1, если дальше 0,то это С, следующий может быть 0 или 1: 1 - D , 0 - В; то-есть В и D различаются по последнему биту, А -по первому, С - по второму, B и D - по третьему.
Символ | Код |
A | 0 |
B | 10 |
C | 110 |
D | 111 |
Таким образом, если известны частоты появления символов в сообщении, то метод реализует оптимальную схему кодирования.
Частота появления группы символов равна сумме частот появления каждого символа.
Сообщение АВАССDА кодируется как 0110010101110 и требует лишь 13 бит.
В очень длинных сообщениях, которые содержат символы, встречающиеся очень редко - экономия существенна.
деревья при работе с арифметическими выражениями
6.2.9 Деревья при работе с арифметическими выражениями
Операция объединения двух символов в один использует структуру бинарного дерева. Каждый узел содержит символ и частоту вхождения. Код любого символа может быть определен просмотром дерева снизу вверх, начиная с листа. Каждый раз при прохождении узла приписываем слева к коду 0, если поднимаемся по левой ветви и 1, если поднимаемся по правой ветви. Как только дерево построено код любого символа алфавита может быть определен просмотром дерева снизу вверх, начиная с места, представляющего этот символ. Начальное значение кода пустая строка. Каждый раз, когда мы поднимаемся по левой ветви, к коду слева приписывается ноль, если справа - 1. Часть info узла дерева содержит частоту появления символа представляемого этим узлом. Дерево Хаффмена строго бинарное. Если в алфавите п символов, то дерево Хаффмена может быть представлено массивом узлов размером 2п-1. Поскольку размер памяти, требуемой под дерево известен, она может быть выделена заранее.
формирование таблиц символов.
6.2.10 Формирование таблиц символов.
В качестве примера приложения бинарных деревьев сформулируем алгоритм ведения древовидно-структурированной таблицы символов.
Основной критерий, которому должна удовлетворять программа ведения таблицы символов, состоит в максимальной эффективности поиска в этой таблицы. Это требование возникает на этапе компиляции, когда осуществляется много ссылок на записи таблицы символов. Необходимо, чтобы над таблицей символов можно было бы проверить две операции - включение записей в таблицу и поиск их в ней. Причем, каждая из этих операций содержит операцию просмотра таблицы.
Древовидное представление таблицы выбирают по двум причинам:
1. Записи символов по мере их возникновения равномерно распределяются в соответствии с лексикографическим порядком, то при хранении записей в дереве в таком же порядке табличный просмотр становится почти эквивалентен двоичному просмотру.
2. В древовидной структуре легко поддерживать лексикографический порядок, т.к. при включении в нее новой записи необходимо изменить лишь несколько указателей.
Для простоты предположим, что при ведении таблицы символов используется достаточно развитая система записей, допускающая символьные строки переменной длины.
Кроме того, предположим, что подпрограмма ведения таблицы символов используется при создании дерева данного блока программы. Это предположение ведет к тому, что попытка повторного включения записи вызывает ошибку. В глобальном контексте повторные записи допустимы, если они соответствую разным уровням блочной структуры программы.
В некотором смысле таблица символов представляет собой множество деревьев - по одному для каждого уровня блочной структуры программы.
Вершины бинарного дерева таблицы символов имеют формат:
SYMBOLS - поле символьной строки, задающей идентификатор или имя переменной ( для обеспечения фиксированной длины описания вершин здесь можно хранить не саму строку, а лишь ее описатель ); INFO - некоторое множество полей, содержащих дополнительно информацию об этом идентификаторе, например его тип данных.
Новая вершина создается путем исполнения оператора P при этом ее адрес запоминается в переменной P.
Еще предлагается, что перед любым исполнением программы ведения таблицы символов на некотором чистом уровне блочной структуры уже имеется соответствующая головная вершина дерева, в поле SYMBOLS в которое занесено значение, лексикографически большее, чем любой допустимый идентификатор. Эта вершина адресуется указателем HEAD[n], где n означает номер уровня блочной структуры. Т.е. предполагается, что при входе в блок осуществляется обращение к основной переменной, управляющей созданием головных вершин деревьев.
Операции включения записи в таблицу и операция поиска в таблице содержат значительное количество одинаковых действий ( например, просмотр ), поэтому рассмотрим только алгоритм TABLE, а различать включение или поиск по переменной FLAG. Если FLAG - истинно - то включение глобальной переменной, если - ложно - поиск. DATA - содержит имя идентификатора и дополнительную информацию для него.
Если включение новой записи было выполнено успешно, то FLAG сохраняет свое первоначальное значение противоположное начальному, что указывает на ошибку, означающую, что искомый идентификатор уже присутствует в таблице данного уровня и выполняемый алгоритм завершается. Если FLAG = ложь, то надо выполнить операцию поиска записи. В этом случае переменная NAME содержит имя идентификатора, который необходимо найти, а значение переменной. При успешном поиске переменная DATA устанавливается на поле INFO соответствующее записи таблицы символов. FLAG сохраняет свое значение и осуществляет возврат к вызванной программе. При неудаче операции поиска, FLAG меняет свое значение и выходит из алгоритма. В этом случае основная программа должна осуществлять поиск записи в таблице, более низких уровней. Деревья с головными вершинами HEAD[n-1], HEAD[n-2] b т.д.
Алгоритм формирования машинного представления вещественного числа в памяти эвм
Алгоритм формирования машинного представления вещественного числа в памяти ЭВМ
Алгоритм формирования состоит из следующих пунктов:
1). Число представляется в двоичном коде. 2). Двоичное число нормализуется. При этом для чисел, больших единицы, плавающая точка переносится влево, определяя положительный порядок. Для чисел, меньших единицы, точка переносится вправо, определяя отрицательный порядок. 3). По формуле из таблицы 2.2 с учетом типа вещественного числа определяется характеристика. 4). В отведенное в памяти поле в соответствии с типом числа записываются мантисса, характеристика и знак числа. При этом необходимо отметить следующее:
- для чисел типа real характеристика хранится в младшем байте памяти, для чисел типа single, double, extended - в старших байтах; - знак числа находится всегда в старшем бите старшего байта; - мантисса всегда хранится в прямом коде; - целая часть мантиссы (для нормализованного числа всегда 1) для чисел типа real, single, double не хранится (является скрытой). В числах типа extended все разряды мантиссы хранятся в памяти ЭВМ.
Алгоритм insert_&_balanse включения узла в сбалансированное дерево.
АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево.
Дано: сбалансированное бинарное дерево с корнем ROOT.
Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).
Заданы переменные: ключ - х, информация - INF.
Алгоритм вставляет в дерево новый элемент, сохраняя сбалансированность дерева. Если элемент уже присутствует в дереве, то выводится соответствующее сообщение.
Переменная h используется как флаг, указывающий на то, что было произведено включение элемента. P - текущий указатель при перемещении по дереву, p1 и p2 - вспомогательные указатели. Count - счетчик вставленных элементов.
_Начало . Insert_&_Balanse: 1. Поиск места для вставки: _Если . x < KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 3; _иначе .: p=LPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; _Если . x > KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 5; _иначе .: p=RPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; 2. Совпадение: Напечатать "Элемент уже вставлен" и _конец .. 3. Изменение показателей сбалансированности: (производилась вставка в левое поддерево) _если . BAL(p)=1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то . BAL(p)=-1; { перевеш.-> критическ.} перейти к п. 7 4. Балансировка при возрастании левого поддерева: _если . p=ROOT _то . ROOT=LPTR(p); { перенос корневой вершины } p1=LPTR(); { вводим дополнительный указатель } _если . BAL(p1)=-1 _то .: { однокр. LL-поворот } LPTR(p)=RPTR(p1); RPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=RPTR(p1); { перенос корневой вершины } p2:=RPTR(p1); RPTR(p1)=LPTR(p2); LPTR(p1)=p1; LPTR(p)=RPTR(p2); RPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=-1 _то . BAL(p)=1 _иначе . BAL(p)=0; _если . BAL(p2)=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; перейти к п. 7; 5. Изменение показателей сбалансированности: (производилась вставка в правое поддерево) _если . BAL(p)=-1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то BAL(p)=1; { перевеш.-> критическ.} перейти к п. 7 6. Балансировка при возрастании правого поддерева: _если . p=ROOT _то . ROOT=RPTR(p); { перенос корневой вершины } p1=RPTR(p); { вводим дополнительный указатель } _если . BAL(p1)=1 _то .: { однокр. RR-поворот } RPTR(p)=LPTR(p1); LPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=LPTR(p1); { перенос корневой вершины } p2:=LPTR(p1); LPTR(p1)=RPTR(p2); RPTR(p1)=p1; RPTR(p)=LPTR(p2); LPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=1 _то . BAL(p)=-1 _иначе . BAL(p)=0; _если . BAL(p2)=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; 7. Выход. (Т.к. процедура осуществляет рекурсивный вызов самой себя в п.3, то здесь производится возврат в место предыдущего вызова. Последний выход осуществляется в вызывающую программу). _Конец . Insert_&_Balanse. 8. Алгоритм процедуры ВСТАВИТЬ_ЭЛЕМЕНТ: _Начало .: LPTR(p)=nil; RPT(p)=nil; BAL=0; { обнуление указателей } DATA=INF; KEY=x; { занесение информации } h=true; { установка флага вставки элемента } _если . count=0 { это первый элемент ? } _то . ROOT=p; count=count+1; _Конец ..
Алгоритм процедуры balance_l.
АЛГОРИТМ ПРОЦЕДУРЫ Balance_L.
Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.
Задан: указатель p на место удаленного элемента.
Алгоритм производит балансировку бинарного дерева и корректировку показателей сбалансированности.
P1 и P2 - вспомогательные указатели, b1 и b2 - вспомогательные показатели сбалансированности.
_Начало . Balance_L: 1. Корректировка показателей сбалансированности: _Если . BAL(p)=-1 _то .: BAL(p)=0; { перевеш. -> сбалансир. } _конец _Если . BAL(p)=0 _то .: BAL(p)=1; h=false; { сбалансир. -> перевеш. } _конец p1=RPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. } 2. Однократный RR-поворот : _Если . b1 >= 0 _то .: _Если . p=ROOT _то . ROOT=RPTR(p); _ .{ перенос корня } RPTR(p)=LPTR(p1); LPTR(P1)=p; { корректировка показателей сбалансированности } _если . b1=0 _то .: BAL(p)=1; BAL(p1)=-1; h=false; _иначе .: BAL(p)=0; BAL(p1)=0; p=p1; _конец 2. Двукратный RL-поворот : _если . b1 < 0 _если . p1=ROOT _то . ROOT=RPTR(p); { перенос корня } p2=LPTR(p1); b2=BAL(p2); LPTR(p1)=RPTR(p2); RPTR(p2)=p1; RPTR(p)=LPTR(p2); LPTR(p2)=p; { корректировка показателей сбалансированности } _если . b2=1 _то . BAL(p)=-1 _иначе . BAL(p)=0; _если . b2=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0; p=p2; BAL(p2)=0; _конец _Конец . Balance_L;
Алгоритм процедуры balance_r.
АЛГОРИТМ ПРОЦЕДУРЫ Balance_R.
Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.
Алгоритм, входные данные и вспомогательные переменные аналогичны алгоритму Balance_L, изменены на противоположные только условия выбора и направления указателей.
_Начало . Balance_R: 1. Корректировка показателей сбалансированности: _Если . BAL(p)=1 _то .: BAL(p)=0; { перевеш. -> сбалансированная. } _конец _Если . BAL(p)=0 _то .: BAL(p)=-1; h=false; { сбалансир. -> перевешивающая. } _конец p1=LPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. } 2. Однократный LL-поворот : _если . b1 0 _если . p1=ROOT _то . ROOT=LPTR(p); { перенос корня } p2=RPTR(p1); b2=BAL(p2); RPTR(p1)=LPTR(p2); LPTR(p2)=p1; LPTR(p)=RPTR(p2); RPTR(p2)=p; { корректировка показателей сбалансированности } _если . b2=-1 _то . BAL(p)=1 _иначе . BAL(p)=0; _если . b2=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0; p=p2; BAL(p2)=0; _конец _Конец . Balance_R;
Метод работы аналогичен алгоритму Balance_L.
ТЕКСТЫ ПРОЦЕДУР Delete 1, 0 Del 1, 0Balance_L и Balance_R.
Так как процедуры Del, Balance_L и Balance_R используются только процедурой Delete, то их можно выполнить вложенными в Delete.
{=====Программный пример 6.20 ========} Procedure Delete (x:integer; var p,root:ref; var h:boolean); var q:ref; {h:false} procedure Balance_L ( var p:ref; var h:boolean); {уменьшается высота левого поддерева} var p1,p2:ref; b1,b2:-1..+1; begin { h-true, левая ветвь стала короче } case p^.BAL of -1: p^.BAL:=0; 0: begin p^.BAL:=+1; h:=false; end; 1: begin {балансировка} p1:=p^.right; b1:=p1^.BAL; if b1 >= 0 then begin { однократный RR-поворот } if p=root then root:=p^.right; p^.right:=p1^.left; p1^.left:=p; if b1 = 0 then begin p^.BAL:=+1; p1^.BAL:=-1; h:=false; end else begin p^.BAL:=0; p1^.BAL:=0; end; p:=p1; end else begin { 2-кратный RL-поворот } if p1=root then root:=p1^.right; p2:=p1^.left; b2:=p2^.BAL; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if b2=+1 then p^.BAL:=-1 else p^.BAL:=0; if b2=-1 then p1^.BAL:=+1 else p1^.BAL:=0; p:=p2; p2^.BAL:=0; end; end; { begin 3 } end; { case } end; {Balance_L} procedure Balance_R (var p:ref; var h:boolean); { уменьшается высота правого поддерева } var p1,p2:ref; b1,b2:-1..+1; begin { h-true, правая ветвь стала короче } case p^.BAL of 1: p^.BAL:=0; 0: begin p^.BAL:=-1; h:=false; end; -1: begin { балансировка } p1:=p^.left; b1:=p1^.BAL; if b1 nil then begin Del(r^.right,h); if h then Balance_R(r,h); end else begin q^.key:=r^.key; r:=r^.left; _ .h:=true; end; end;{Del} Begin {Delete} if p=nil then begin TextColor(white); GotoXY(а,b+2); write ('Ключа в дереве нет'); h:=false; end else if x < p^.key then begin Delete(x,p^.left,root,h); if h then Balance_L(p,h); end else if x > p^.key then begin Delete(x,p^.right,root,h); if h then Balance_R(p,h); end else begin { удаление p^ } q:=p; if q^.right=nil then begin p:=q^.left; h:=true; end else if q^.left=nil then begin p:=q^.right; h:=true; end else begin Del(q^.left,h); if h then Balance_L(p,h); end; GotoXY(а,b); writeln(' Узел с ключом ',x,' удален из дерева.'); end; End{Delete};
Алгоритм процедуры del.
АЛГОРИТМ ПРОЦЕДУРЫ Del.
Дано: указатель - r на элемент дерева с двумя поддеревьями.
Алгоритм производит удаление этого элемента, с сохранением связей с нижележащими элементами, и вызов процедуры балансировки.
Используется вспомогательный указатель q, описанный в процедуре Delete.
_Начало . Del. 1. Поиск последнего элемента в правом поддереве _Если . RPTR(r) <> nil { элемент не найден } _то .: r=RPTR(r); вызов процедуры Del; _если . h=true _то . вызов процедуры Balance_R; перейти к п.2; _иначе .: KEY(q)=KEY(r); r=RPTR(r); h=true; 2. Выход. _Конец . Del;
Алгоритм процедуры delete.
АЛГОРИТМ ПРОЦЕДУРЫ Delete.
Дано: сбалансированное бинарное дерево с корнем ROOT. Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).
Задан: ключ - х, информация - INF.
Алгоритм находит удаляемый элемент и вызывает процедуры удаления и последующей балансировки бинарного дерева. Если элемент отсутствует в дереве, выдается соответствующее сообщение.
Переменная h используется как флаг, указывающий на то, что было произведено удаление элемента. P - текущий указатель при перемещении по дереву, q - вспомогательный указатель.
_Начало . Delete 1. Поиск удаляемого элемента _Если . x < KEY(p) _то .: p=LPTR(p); Вызов Delete; _если . h=true _то . Вызов Balance_L; перейти к п.5 _Если . x > KEY(p) _то .: p=RPTR(p); Вызов Delete; _если . h=true _то . вызов Balance_R; перейти к п.5 _Если . p=nil _то .: напечатать "Ключа в дереве нет!"; _конец .; 2. Удаление элемента : (если все предыдущие условия не выполнены, то указатель указывает на элемент, подлежащий удалению). Удаляется элемент с одним поддеревом. q=p; { вводим вспомогательный указатель } _если . RPTR(q)=nil _то .: p=LPTR(q); h=true; перейти к п.4; _если . LPTR(q)=nil _то .: p=RPTR(q); h=true; перейти к п.4; 3. Удаление элемента с двумя поддеревьями: q=LPTR(q); _если . h=true _то .: вызов Balance_L; перейти к п.4 4. Напечатать "Узел удален из дерева". 5. Выход. _Конец . Delete;
Алгоритм search.
АЛГОРИТМ Search.
Дано: ключ - X.
Алгоритм производит рекурсивный обход сбалансированного дерева и находит элемент с заданным ключом, либо сообщает об отсутствии такого элемента.
1. Поиск элемента: _Если . x < key(p) _то .: _если . p=nil _то .: напечатать "Элемент отсутствует" и _конец .. _иначе .: p=LPTR(p) и вызвать процедуру Search; _Если . x > key(p) _то .: _если . p=nil _то .: напечатать "Элемент отсутствует" и _конец .. _иначе .: p=RPTR(p) и вызвать процедуру Search; 2. Совпадение: Напечатать "Элемент найден"; Произвести операции обработки элемента и _конец ..
Алготитм table.
АЛГОТИТМ TABLE.
На вход подается глобальная переменная n, идентифицирующая номер уровня текущего блока и глобальная переменная FLAG, задающая требуемую операцию. Описываемый алгоритм выполняет эту операцию над древовидной структурированной таблицей символов, локальной относительно блока уровня u. Параметры DATA и NAME используются для передачи данных между алгоритмом и от того больше или меньше значение NAME кода исследуемой записи таблицы, осуществляется установка указателя на левый или правый потолок данной вершины и возврат к шагу 2 для дальнейших сравнений. Поскольку дерево упорядочено таким образом, что код каждой вершины левого ( правого ) поддерева лексикографических меньше (больше), чем код корневой вершины, то попытка спуска по пустому дереву означает, что требуемая запись в таблице отсутствует; при этом определяется место, где данная запись расположена.
В этом случае, если требовалось найти запись, то выдается сообщение об ошибке, в противном случае создается новая вершина, в нее заносится нужная информация и она включается в уже существующую древовидную структуру слева или справа от исследуемой вершины.
Блочно - связное представление строк.
БЛОЧНО - СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК.
Это представление позволяет в болшинстве операций избежать затрат, связанных с управлением динамической памятью, но в то же время обеспечивает достаточно эффективное использование памяти при работе со строками переменной длины.
Быстрая сортировка хоара.
Быстрая сортировка Хоара.
Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log2(N)) даже при наихудшем исходном распределении.
Используются два индекса - i и j - с начальными значениями 1 и N соответственно. Ключ K[i] сравнивается с ключом K[j]. Если ключи удовлетворяют критерию упорядоченности, то индекс j уменьшается на 1 и производится следующее сравнение. Если ключи не удовлетворяют критерию, то записи R[i] и R[j] меняются местами. При этом индекс j фиксируется и начинает меняться индекс i(увеличиваться на 1 после каждого сравнения). После следующей перестановки фиксируется i и начинает изменяться j и т.д. Проход заканчивается, когда индексы i и j становятся равными. Запись, находящаяся на позиции встречи индексов, стоит на своем месте в последовательности. Эта запись делит последовательность на два подмножества. Все записи, расположенные слева от нее имеют ключи, меньшие чем ключ этой записи, все записи справа - большие. Тот же самый алгоритм применяется к левому подмножеству, а затем к правому. Записи подмножества распределяются по двум еще меньшим подмножествам и т.д., и т.д. Распределение заканчивается, когда полученное подмножество будет состоять из единственного элемента - такое подмножество уже является упорядоченным.
Процедура сортировки в примере 3.16 рекурсивная. При ее вызове должны быть заданы значения границ сортируемого участка от 1 до N.
{===== Программный пример 3.16 =====} { Быстрая сортировка Хоара } Procedure Sort(var a : Seq; i0,j0 : integer); { i0, j0 - границы сортируемого участка } Var i, j : integer; { текущие индексы в массиве } flag : boolean; { признак меняющегося индекса: если flag=true - уменьшается j, иначе - увеличивается i } x : integer; begin if j0 a[j] then begin x:=a[i]; a[i]:=a[j]; a[j]:=x; { перестановка } { после перестановки меняется изменяемый индекс } flag:= not flag; end; { реально изменяется только один индекс } if flag then j:=j-1 else i:=i+1; end; Sort(a,i0,i-1); { сортировка левого подмассива } Sort(a,i+1,j0); { сортировка правого подмассива } end;
Результаты трассировки примера приведены в таблице 3.10. В каждой строке таблицы показаны текущие положения индексов i и j, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.
Cмешанный обход (inorder, r_inorder).
CМЕШАННЫЙ ОБХОД (Inorder, r_Inorder).
Смешанный обход можно описать следующим образом:
1) Спуститься по левой ветви с запоминанием вершин в стеке; 2) Если стек пуст то перейти к п.5; 3) Выбрать вершину из стека и обработать данные вершины; 4) Если вершина имеет правого сына, то перейти к нему; перейти к п.1. 5) Конец алгоритма.
В программном примере 6.6. реализован алгоритм смешанного обхода дерева.
{=== Программный пример 6.6. Процедура смешанного обхода ===} Procedure Inorder (t: TreePtr); label 1; type Stack=^Zveno; { тип стека } Zveno = record next: Stack; El: pointer; end; Var st: stack; p: TreePtr; (*---------- Процедура занесения в стек указателя ---------*) Procedure Push_st (var st:stack; p:pointer); Var q: stack; begin new(q); q^.el:=p; q^.next:=st; st:=g; end; (*------------ Функция извлечения из стека указателя ------*) Function Pop_st (var st: stack):pointer; Var e,p: stack; begin Pop_st:=st^.el; e:=st; st:=st^.next; dispose(e); end; Begin if t = NIL then begin writeln('Дерево пусто'); exit; end else begin p:=t; st:=nil; end; 1: while p^.left <> nil do begin (* Спуск по левой ветви и заполнение очереди *) Push_st(st,p); p:=p^.left; end; if st = NIL { контроль заполнения стека } then exit; p:=Pop_st(st);{выборка очередного элемента на обработку} (*--------------- Обработка данных звена --------------*) ................................ if p^.right <> nil then begin p:=p^.right; { переход к правой ветви } goto 1; end; End; { Inorder }
Трассировка смешанного обхода приведена в табл. 6.2:
Десятичный тип с фиксированной точкой.
Десятичный тип с фиксированной точкой.
В языке PL/1 десятичный тип с фиксированной точкой описывается в программе, как:
DECIMAL FIXED (m.d) или DECIMAL FIXED (m).
Первое описание означает, что данное представляется в виде числа, состоящего из m десятичных цифр, из которых d цифр расположены после десятичной точки. Второе - целое число из m десятичных цифр. Следует подчеркнуть, что в любом случае число десятичных цифр в числе фиксировано. Внутримашинное представление целых чисел и чисел с дробной частью одинаково. Для последних положение десятичной точки запоминается компилятором и учитывается им при трансляции операций, в которых участвуют десятичные числа с фиксированной точкой.
Внутримашинное представление данного типа носит название десятичного упакованного формата. Примеры представления чисел в таком формате приведены на рис. 2.6.
Добавление нового узла ( dop ).
ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ).
Для включения записи в дерево прежде всего нужно найти в дереве ту вершину, к которой можно "подвести" (присоединить) новую вершину, соответствующую включаемой записи. При этом упорядоченность ключей должна сохраняться.
Алгоритм поиска нужной вершины, вообще говоря, тот же самый, что и при поиске вершины с заданным ключом. Эта вершина будет найдена в тот момент, когда в качестве очередного указателя, определяющего ветвь дерева, в которой надо продолжить поиск, окажется указатель NIL ( случай 2 функции Find ). Тогда процедура вставки записывается так, как в программном примере 6.3.
{=== Программный пример 6.3. Добавление звена ===} Procedure Dob (k:KeyType; var d:TreePtr; zap:data); { k - ключ, d - узел дерева, zap - запись } Var r,s: TreePtr; t: DataPtr; Begin if not Find(k,d,r) then begin (* Занесение в новое звено текста записи *) new(t); t^:=zap; new(s); s^.key:=k; s^.ssil:=t; s^.left:=NIL; s^.right:=NIL; if d = NIL then d:=s (* Вставка нового звена *) else if k < r^.key then r^.left:=s else r^.right:=s; end; End; { Dop }
Двунаправленный линейный список.
ДВУНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК.
В каждый элемент списка добавляется также указатель на предыдущий элемент, как показано на рис.4.8. Двустороннее сцепление допускает двустороннее движение вдоль списка, что может значительно повысить эффективность выполнения некоторых строковых операция. При этом на каждый символ строки необходимо два указателя , т.е. 4-8 байт.
Физическая структура.
Физическая структура.
Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт.
Число байтов, выделяемых для данных типа множество, вычисляется по формуле: ByteSize = (max div 8)-(min div 8) + 1, где max и min - верхняя и нижняя границы базового типа данного множества.
Номер байта для конкретного элемента Е вычисляется по формуле:
ByteNumber = (E div 8)-(min div 8),
номер бита внутри этого байта по формуле:
BitNumber = E mod 8
{===== Программный пример 3.3 =====} const max=255; min=0; E=13; var S : set of byte; ByteSize, ByteNumb, BitNumb : byte; begin S:=[]; { обнуление множества } S:=S+[E]; { запись числа в множество } ByteSize:=(max div 8)-(min div 8)+1; Bytenumb:=(E div 8)-(min div 8); BitNumb:=E mod 8; writeln(bytesize); { на экране 32 } writeln(bytenumb); { на экране 1 } writeln(bitnumb); { на экране 5 } end.
Глубина.
Глубина.
Это максимальный уровень, приписываемый элементам внутри списка или внутри любого подсписка в списке. Уровень элемента предписывается вложенностью подсписков внутри списка, т.е.числом пар круглых скобок, окаймляющих элемент. В списке, изображенном на рис.5.12), элементы a и e находятся на уровне 1, в то время как оставшиеся элементы - b, c, d, f и g имеют уровень 2. Глубина входного списка равна 2. При представлении списков схемами концепции глубины и уровня облегчаются для понимания, если каждому атомарному или списковому узлу приписать некоторое число l. Значение l для элемента x, обозначаемое как l(x), является числом вертикальных стрелок, которое необходимо пройти для того, чтобы достичь данный элемент из первого элемента списка. На рис.5.12 l(a)=0, l(b)=1 и т.д. Глубина списка является максимальным значением уровня среди уровней всех атомов списка.
Длина - это число элементов уровня 1 в списке. Например, длина списка на рис.5.12 равна 3.
Типичный пример применения разветвленного списка - представление последнего алгебраического выражения в виде списка. Алгебраическое выражение можно представить в виде последовательности элементарных двухместных операций вида:
< операнд 1 > < знак операции > < операнд 2 >
Копирование части списка.
Копирование части списка.
При копировании исходный список сохраняется в памяти, и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти. Существенно, что операция копирования предполагает дублирование данных в памяти. Если после создания копии будут изменены данные в исходном списке, то изменение не будет отражено в копии и наоборот.
Л и т е р а т у р а
Ленгсам Й., Огенстайн М., Тененбаум А.
Структуры данных для персональных ЭВМ. М.: Мир, 1989.
Трамбле Ж., Соренсон П.
Введение в структуры данных. М.: Машиностроение, 1982. Дж. Уоркли.
Архитектура и программное обеспечение микро ЭВМ. Том 1. Структуры данных. М.: Мир, 1984. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. Вирт Н.
Алгоритмы + структуры данных = программы. М.:Мир, 1985. Нагао М., Катаяма Т., Уэмура. Структуры и базы данных. М.: Мир, 1984. Костин Е.Е., Шаньгин В.Ф. Организация и обработка стру- ктур данных в вычислительных системах. М.: Высш. школа, 1987. Трофимова И.П.
Системы обработки и хранения информации. М.: Высш. школа, 1989. Замулин А.В. Система программирования баз данных и знаний. Новосибирск : Наука, 1990. Замулин А.В. Типы данных в языках программирования и базах данных. Новосибирск : Наука, 1987. Разумов О.С. Организация данных в вычислительных системах. М.: Статистика, 1978. 184 с. Джонс Ж., Харроу К. Решение задач в системе Турбо-Паскаль. М.: Финансы и статистика, 1991. 718 с. Морс С.П., Альберт Д.Д.
Архитектура микропроцессора 80286. М.: Радио и связь, 1990. Р. Джордейн.
Справочник программиста персональных компьютеров типа IВМ РС, ХТ и АП. М.: Финансы и статистика, 1992. Макаровский Б.Н.
Информационные системы и структуры данных. Учебное пособие вузов. М.: Статистика, 1980. Флорес И.
Структуры и управление данными. М.: Радио и связь, 1982.
17. Холл П. Вычислительные структуры (введение в нечисленное программирование). М.: Мир, 1978. 214 с.
18. Дрибас В.П. Реляционные модели баз данных. Минск : Изд. БГУ, 1982. 192 с. Агафонов В.Н. Типы и абстракция данных в языках программирования. / Данные в языках программирования. М.: Мир, 1982 Брукс Ф.П. Как проектируются и создаются программные комплексы. М.: Наука, 1979 Виноградов М.М.
Модели данных и отображения моделей данных : алгебраический подход. / Теория и приложения систем баз данных. М.: ЦЭМИ АП СССР, 1984. Леман Д., Смит М. Типы данных / Данные в языках программирования. М.: Мир, 1982. Хоор К. О структурной организации данных / Структурное программирование. М.: Мир, 1975. Зайцев В.Ф. Кодирование информации в ЕС ЭВМ. М.: Радио и связь, 1986. Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. М.:Мир, 1976. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. М.:Мир, 1976. Пратт Т. Языки программирования. Разработка и реализация. М.:Мир, 1979.
Данные в языках программирования. / Под ред. В.Н.Агафонова.М.:Мир, 1982. Вирт Н. Систематическое программирование. ВведениеМ.:Мир, 1982. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.:Мир, 1981. Баррон Д. Введение в языки программирования. М.:Мир, 1980. Ахо А., Холкрофт Дж., Ульман Дж.
Построение и анализ вычислительных алгортимов. М.:Мир, 1979. Керниган Б., Ритчи Д. Язык программирования Си. М.:Финансы и статистика, 1992. Фостер Дж. Обработка списков. М.:Мир, 1974.
Логическая структура.
Логическая структура.
Перечислимый тип представляет собой упорядоченный тип данных, определяемый программистом, т.е. программист перечисляет все значения, которые может принимать переменная этого типа. Значения являются неповторяющимися в пределах программы идентификаторами, количество которых не может быть больше 256, например,
type color=(red,blue,green); work_day=(mo,tu,we,th,fr); winter_day=(december,january,february);
Логическая структура.
Один из способов образования новых типов из уже существующих - ограничение допустимого диапазона значений некоторого стандартного скалярного типа или рамок описанного перечислимого типа. Это ограничение определяется заданием минимального и максимального значений диапазона. При этом изменяется диапазон допустимых значений по отношению к базовому типу, но представление в памяти полностью соответствует базовому типу.
Логическая структура.
Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.
Логическая структура.
Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char и производные от них типы.
Манипулирование арифметическими выражениями.
МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ.
Дано выражение а*(-b)+с/d
Операции выполняются над выражениями, представленными в виде бинарных деревьев. Такие выражения можно символьно складывать,
Машинное представление.
Машинное представление.
Для переменной перечислимого типа выделяется один байт, в который записывается порядковый номер присваиваемого значения. Порядковый номер определяется из описаного типа, причЯм нумерация начинается с 0. Имена из списка перечислимого типа являются константами, например,
var B,С:color; begin B:=bluе; (* B=1 *) C:=green; (* С=2 *) Write(ord(B):4,ord(C):4); end.
После выполнения данного фрагмента программы на экран будут выданы цифры 1 и 2. Содержимое памяти для переменных B И C при этом следующее:
В - 00000001; С - 00000010.
Машинное представление.
Данные интервального типа могут храниться в зависимости от верхней и нижней границ интервала независимо от входящего в этот предел количества значений в виде, представленном в таблице 2.4. Для данных интервального типа требуется память размером один, два или четыре байта, например,
var A: 220..250; (* Занимает 1 байт *) В: 2221..2226; (* Занимает 2 байта *) C: 'A'..'K'; (* Занимает 1 байт *) begin A:=240; C:='C'; B:=2222; end.
После выполнения данной программы содержимое памяти будет следующим:
A - 11110000; C - 01000011; B - 10101110 00001000.
Машинное представление. Адресация элементов структур.
Машинное представление. Адресация элементов структур.
Элементы вектора размещаются в памяти в подряд расположенных ячейках памяти. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента этого вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения вектора определяется произведением длины слота на число элементов.
В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида (PASCAL):
< Имя > : array [n..k] of < тип >;
где n-номер первого элемента, k-номер последнего элемента. Представление в памяти вектора будет такое, как показано на рис. 3.1.