1. Занесение эл-та в очередь.
Алгоритм.
1. создание нового звена;
2. занесание в послед. звено адреса нового звена;
3. занесание nil в поле адреса нового звена;
4. занесание эл-тов в новое звено;
5. созданное звено сделать концом очереди.
{1} new(q);
{2} Right^.adrcled:=q;
{3} q^.adrcled:=nil;
{4} q^.element:=el;
{5} right:=q
2. Выбор эл-та из очереди.
Алгоритм.
1. прочитать значение из начала очереди;
2. запомнить ссылку на начало очереди;
3. исключить 1-е звено из начала очереди;
4. уничтожить 1-е звено.
{1} elem:=Left^.element;
{2} q:=Left;
{3} Left:=Left^.adrcled;
{4} dispose(q);
Вопрос №46.
Очередь LIFO. Объявление. Операции, определенные над очередью LIFO. Организация очереди LIFO.
Очереди и стеки.
Над очередью опр. 2 операции:
- занесение элемнта в очередь,
- выбор элемента (выбранный элемент из очреди исключается).
В очереди доступны 2 позиции: начало и конец, где помещаются заносимый элемент.
Различают 2 вида:
(FIFO) заказ, поступивший в очередь 1-ым, выбирается 1-ым и удаляется;
(LIFO-стек) последний заказ выбирается и удаляется.
Стек (LIFO).
В стеке доступна одна позиция – вершина стека, которая находится последней по времени занесения элемента. Наиболее быстрое выполнени операциинад стеком обеспечивает его представление в виде однонаправленного списка. Загланое звено в стеке не используется. При использовании однонаправленного спискастек задается с помощью описания типа (*). Дополнительно вводится тип указателя, представляющего стек кк единую структуру.
TypeStak=Adres1;
varSt: Stak;
К началу исп-ния стека его нужно сделать пустым.
1. Занесение элемента в стек.
Алгоритм:
1. создание нового звена;
2. занесение в новое звено элемента;
3. занесение в новое звено адреса предыдущей вершины стека;
4. созданное звено сделать вершиной стека.
{1} new(q);
{2} q^.element:=el;
{3} q^.adrcled:=st;
{4} st:=q;
2. Выбор элемена из стека.
Алгоритм.
1. прочитать значение вершины стека;
2. заполнить ссылку на вершину стека;
3. исключить 1-е звено из стека;
4. уничтожить 1-е звено.
{1} a:=st^. element;
{2} q:=st;
{3} st:=st^.adrcled;
{4} dispose(q);
Вопрос №47.
Таблицы.
Основная задача – организация выдачи по запросу любой из записей независимо от того, какая запись выдавалась перед ней.Используются структуры данных (таблицы). Каждой записи соответствует свое имя (ключ записи). Для организации эффективного поиска записи необходимо, чтобы наж ключами м.б. реализовывать операции сравнения, поэтому ключи д.б. упорядоченного типа. Наиболее удобно использовать целые числа или строки символов одинаковой длины. Определены следующие операции: поиск записи с заданным ключом, включение в таблицу записи с заданным ключом, исключение записи.
1й способ: Представление таблицы с помощью однонаправленнго списка. Каждое звено списка д. содержать ключ записи, текст записи и ссылку на следующее звено. Достоинтсва: эффективное использование памяти, простой алгоритм перебора записей, простота включения в таблицу заведомо новой записи, как новое звено в конец списка. Недостаток: большое время поиска нужной инфы.
2й срособ: Однонаправленный список с упорядоченными записями. Достоинтсва: меньшее время поиска записи, недостаток: усложняется включение новой записи в таблицу.
3й способ: цепочка с отдельным хранением текста записи. Для ускорения поиска записи. Тексты записей хранятся отдельно от ключей.
*→| * | → | * | → …
| кл1 | |кл2 |
| * | | * |
↓ ↓
|зап1| |зап2|
4й способ: представление в виде массива.
|кл1| |кл2| …
| * | | * |
↓ ↓
|зап1| |зап2|
typeindex=1..N;
tekst=<тип_текст_зап>;
adr=^tekst;
element=record
kl:integer;
adrzap:adr;
end;
mas=array [index] of element;
vartab1:mas;
Для организации эффективного поиска необходимо, чтобы элементы массива были упорядочены по возрастанию ключей. tab1[i].adrzap^.
Для поиска элемента с заданным ключом используется метод дихотомического поиска: берется средний элемент массива, если искомый ключ меньше ключа в элементе с номером n/2, то требуемый элемент находится в 1й половине массива. На следующем этапе нужная половина массива опять делится пополам. Кол-во шагов: 1+log2N Недостаток: реализация включения и исключения записей.
Вопрос №48.
5й способ: двоичное дерево. Позволяет эффективно реализовать все 3 операции над таблицами. Из каждой вершины выходит не более 2х вертвей. В каждую вершину входит только одна ветвь. Вершина, в которую не входит ни одна ветвь.называется корнем. Вершины, из которых не выходи ни одна ветвь –листья. При представлении таблицы в виде дерева тексты записей храниятся отдельно, каждая вершина дерева является записью, состоящей из 4х полей: ключ записи, ссылка на вершину влево-вниз, вправо-вниз, ссылка на текст записи.
Принцип: первая запись делается корнем дерева. Если ключ следующей записи меньше ключа корня, то этой записи ставится в соответствие левая вершина иначе – правая. Ключ каждой последующей записи сравнивается последовательно с ключом корня, а затем с ключами тех записей, которые находятся на соответствующей вершине дерева.
Typetekst=<тип_записи>
Adrt=^tekst;
Adrzv=^zveno;
Zveno=record
Kl:integer;
Lev,prav:adrzv;
Adr:adrt;
End;
Var dvder:adrzv;
Вопрос №49.
Поиск.
k-ключ искомой записи; d-ссылка на дерево; rez – присваевымая ссылка на найденное звено или ссылка на вершину после обработки которой которой; P-адрес вершины, подлежащей обработке; Q- адрес последней обработанной вершины.
Var P,Q:adrzv;
D,rez:adr;
B:boolean;
K:integer;
Begin........
B:=false;
P:=d;
Q:=nil;
If d<>nil then
repeat
Q:=p;
If p^.kl=k then b:=true else
If k<p^.kl then p:=p^.lev else p:=p^.prav
Until b or (p=nil);
Rez:=q;
Скорость поиска приблизительно равна скорости дихотомии.
Вопрос №50.
Операция включения записи дерево.
Для включения записи в таблицу нужно найти в дереве, к кот. можно присоединить новую вершину, соответствующую включаемой записи.
Алгоритм поиска нужной вершины аналогичен поиску вершины с заданным ключом. Нужная вершина найдена если в кач-ве очередной ссылки, определяющей ветвь продолжения поиска, окажется nil. Для поиска вершины можно исп-ть алгоритм поиска вершины с заданным ключом (т.е. такая вершины найдена, если b=false). В этом случае rez – адрес вершины, к кот. можно присоединить включаемую вершину.
var zap: terst;
s: adrzv;
t: adrt;
begin----
new(t);
t^:=zap;
new(s);
s^.kl:=k;
s^.adr:=t;
s^.adr:=t;
s^.lev:=nil;
s^.prav:=nil;
if d=nil then d:=s
else if k<q^.kl then q^.lev:=s
elseq^.prav:=s;
Вопрос №51.
Операция удаленияния записи дерево.
Если удаляемая вершина явл. листом дерева или из нее выходит только одна ветвь, то для удаления записи достаточно скоректировать соответ. ссылку у вершины предшедствующей удаляемой. В этих случаях в соответств. поле Lev или prav предшественника нужно занести содержимое поля Lev или prav удаляемой вершины.
Если из удаляемой вершины выходит две ветви, то нужно найти подходящее звено, которое можно было бы вставить на мести удаляемого. Таким звеном является:
а) самый правый эл-т левого поддерева.
Для достижения этого звена необходимо перейти в следующую под удаляемой вершину по левой ветви, а затем переходить в очередные вершины только по правой ветви до тех пор, пока очередная такая ссылка не будет равна nil.
б) самый левый элемент правого поддерева.
Для достижения этого звена необходимо перейти в след. под удал. вершину по правой ветви, а затем переходить в очередные вершины только по левой ветви, пока очередная ссылка не будет равна nil.
При исключении из дерева вершины с заданным ключом необходимо учеть:
1. звена с заданным ключом в дереве нет;
2. звено с заданным ключом имеет не более одной ветви;
3. звено с заданным ключом имеет две ветви.
Пример (случ.а).
Procedure Del (var d:adrzv; k:integer);
var q: adrzv;
Procedure Udal (var R:adrzv); begin
if R^.prav=nil then
begin
q^.kl:=R^.kl;
q^.adr:=R^.adr;
q:=R;
R:=q^.lev
end;
else Udal(R^.prav);
end;
begin
if d=nil then writeln (‘звенанет’);
else if k<d^.kl then Del (d^.lev, k);
else if k>d^.kl then Del (d^.prav, k);
else begin
q:=d;
if d^.prav=nil then d:= d^.lev
else if d^.lev=nil then d:= d^.prav
else Udal(q^.lev);
end;
end;
| Вопрос №1. Строковые константы.Это последовательность любых символов, заключенных в апострофы.Правила записи:1) Если в строке необходимо поместить апостроф, то его повторяют 2-жды. При просчете длины строки 2 рядом стоящих апострофа считаются одним.2) При подсчете длины строки учитываются пробелы.3) Допускаются пустые символьные константы. ‘’4) Турбо П. разрешает вставлять в строку управляющие символы. Используется символ # и константа целого знака от 0..255 (#13-возврат каретки, #10-перевод строки). Управляющие символы пишутся вне апострофа.Например,‘TURBO’#13#10’TEKST’Здесь #13#10 – это управляющие символы, осуществляющие переход к началу следующей строки.Строковые переменные постоянной длины: строк. пер. = одномерный массив симв. Обладают всеми свойствами массивов. Возможно обращение к отдельным символам, используя индексы.Форматзадания: Array[1..10] of char;Особенности строк. переменных:1) Строковым переменным могут быть присвоены значения строковых констант, если длина строки равна длине литерала.2) Над значениями строковых переменных одинаковой длины можно выполнять операции сравнения. Сравнение производится посимвольно слева до первого несовпадающего символа.Считается большей та строка, в которой первый несовпадающий символ имеет больший номер в коде обмена информацией (ASCII). | Вопрос №2 Строки переменной длины.<Задание_типа_String> ::=→string→[→<N>→]→ ↓____→___↑С помощью типа String определяются строки переменной длины. N после слова String определяет максимальную длину строки. N должно иметь положительное целочисленное значение, не превышающее 255 (≥1).Если N в определении опущено (по умолчанию), то считается, что максимальная длина строки равна 255 = 28 – 1.Переменной типа String может быть присвоено значение другой строки любой длины. Если длина присваиваемой строки меньше или равна максимальной длине данной строки, то данная переменная типа String имеет текущую (динамическую) длину. Текущая длина строки определяется длиной последнего занесенного в нее значения.Если длина присваиваемого значения превышает указанную в объявлении максимальную длину, то лишние символы справа отсекаются.Переменной типа String выделяется количество байтов памяти на единицу превышающее максимальную длину, указанную в определении типа. В левом байте (с номером 0) хранится текущая длина строки в двоичном коде.Возможен доступ к отдельным символам строки типа String. При этом используются индексные переменные. Правила индексации аналогичны массиву символов с диапазоном индексов.Если при обращении к отдельным символам строки произойдет выход за текущую длину строки, то считанные из строки символы будут случайными, а присваивания элементам строки, находящимся вне текущей длины, не повлияют на значение строковой переменной.Над данными типа String определены операции сравнения (=, <>, >, <, >=, <=) и операция конкатенации (сцепления). Операция конкатенации имеет более высокий приоритет чем операции сравнения.Сравнение производится в соответствии с упорядочением символов в коде ASCII. Сравниваются символы строк последовательно слева направо до первого несовпадающего символа. Большей считается строка, у которой первый несовпадающий символ имеет больший код в таблице ASCII. Если строки имеют разную длину и их символы совпадают в общей части, то более короткая строка считается меньшей. Строки считаются равными, если они имеют одинаковую текущую длину и одни и те же символы.Операция сцепления обозначается символом +. При ее выполнении две строки соединяются в одну результирующую строку. Длина результирующей строки не должна превышать 255 символов.Var ST1 : String [100]; {максимальная длина равна 100}ST3, ST2 : String; {по умолчанию максимальная длина равна 255} L: Boolean; BeginST1 := ‘Ми’; {текущая длина ST1 равна 3} ST2 := ‘н’; {текущая длина ST2 равна 1} ST3 := ‘ск’; {текущая длина ST3 равна 2} ST3 := ST1 + ST2 + ST3; {сцепление (конкатенация) строк: в ST3 значение ‘Минск’; текущая длина равна 4}L := ST3 > ST1; {в Lзапишется True} ST3[2] := ‘e’; {в ST3 значение ‘Менск’} | Вопрос №3 Процедуры и функции, определенные над строками переменной длины.Функции:1) Copy (St, Poz, N) Выделяет из строки St подстроку длиной N символов, начиная с позиции Poz. Если Poz больше длины строки, то результат – пустая строка. Если Poz + N больше текущей длины St, результатом будут последние символы St, начиная с позиции Poz. Если Poz больше 255, возникает ошибка выполнения. 2) Concat (St1[, St2, ..., StN] )Выполняет сцепление строк в том порядке, в каком они указаны в списке параметров: St1 + St2 + ... + StN. S1 ÷ SN – выражения типа String. Длина результирующей строки не должна превышать 255 символов3) Length (St)Возвращает текущую длину строки St. Результат имеет целочисленный тип.4) Pos (St1, St2)Обнаруживает первое появление подстроки St1 в строке St2. Результат имеет целочисленный тип и равен номеру той позиции, где находится первый символ подстроки St1. Если в строке St2 подстроки St1 не найдено, то результат равен нулю.5) UpCase (Ch)Преобразует строчную латинскую букву в прописную. В остальных случаях возвращает аргумент Ch. Параметр и результат имеют тип Char.Процедуры:1) Delete (St, Poz, N)Удаляет N символов строки St, начиная с позиции Poz. Значение Poz не должно превышать 255. Если Poz больше текущей длины строки, строка St не изменяется. Если Poz + N больше текущей длины строки, то удаляется конец строки, начиная с позиции Poz.2) Insert (St1, St2, Poz)Вставляет строку St1 в строку St2, начиная с позиции Poz. Если значение Poz больше текущей длины St2, то результат равен сцеплению строк St2 + St1.3) Str (I, St)Преобразует числовое значение величины I и помещает результат в строку St. Величина I должна иметь целочисленный или вещественный тип.4) Val (St, I, Cod)Преобразует значение St в величину целочисленного или вещественного типа (в зависимости от типа параметра I) и помещает результат в I. Значение St может содержать незначащие пробелы в начале и не может в конце. Cod – целочисленная переменная. Если во время операции преобразования ошибки не обнаружено, то значение Cod равно нулю. Если ошибка обнаружена (например, символьное значение переводится в цифровое), то Cod будет содержать номер позиции первого ошибочного символа, а значение I будет неопределено. |
| Вопрос №4 Оператор CASEЯвляется производным оператором. Относится к группе выбирающих операторов.Используется в разветвляющихся программах, если процесс нужно разветвить более чем по двум возможным направлениям. Является обобщением условного оператора If. Формат оператора Case:→Case→<Выражение>→Of───┐┌───────────────────┘└─┬──┬→<Диапазон>─┬──→:──→<Оператор>─┬──┬─────────────┬┬──↑→End─→ │ └───←─,←──┘ │ └→Else→<Оператор>┘ └→;┘ └───────←──────;←────────────┘Оператор Case позволяет выбрать для исполнения один из входящих в него операторов, в зависимости от значения выражения, расположенного после зарезервированного слова Case. Это выражение называется селектором (переключателем). Оно может иметь любой перенумерованный тип, кроме типов Longint, Word и строкового типа.Каждый оператор помечен списком констант выбора и (или) диапазонов констант выбора: Диапазон::=→<Константа_1>─┬─────────────┬─→ └→..→<Константа_2>┘Последний оператор может быть помечен зарезервированным словом Else (иначе). Если несколько констант выбора относятся к одному и тому же оператору, то они отделяются друг от друга запятой. Константы выбора должны иметь тот же тип, что и селектор. Оператор Case выполняется следующим образом. Сначала вычисляется значение селектора. Затем выполняется тот оператор, для которого значение константы выбора совпадает со значением селектора. Если ни одна константа выбора не совпадает со значением селектора, то будет выполнен оператор, помеченный зарезервированным словом Else. На этом выполнение оператора Case заканчивается.Если значению селектора не соответствует ни один из допустимых вариантов выполнения (ветвь Else отсутствует), то выполняется оператор, следующий за Case.Пример 1.Case 2 * I - KOf{Cелектор целочисленного типа} -100 .. -1: Writeln('<0'); 0: Writeln ('=0'); 1 .. 100: Writeln('>0') EndПример 2.Case A Of 'A' .. 'Z': X := 0; '#', '_', ':': X := 1;селектортипа Char '+': X := 2 Else: X := 3 End | Вопрос №14 Библиотечные модули пользователя.Это результат трансляции в режиме Compileструктурной единицы Unit с установленной директивой Destination=Disk. Введение Tpuфайлов позволяет создавать программы, превышающие 64КБ. Модули являются основой модульного программирования, в отличие от подпрограммы модуль не может быть запущен самостоятельно. Модули компилируются независимо от использующей их программы. Чтобы подключить модуль к программе необходимо указать его в USES.Структура модуля Unit:<Модуль>::=→<заголовок_модуля>;→<интерфейсный_раздел>→<раздел_реализации>→______________________________________________________________________________<раздел_инициализации>→;unit <имя_модуля>;InterfaceUses <спис. используемых_Unit> {описание глоб. перемен.}type... Const…Var…{заголовок подпрог с указанием используемых параметров}procedure … function…Implementation<описание лок. типов, переменных, процедур и функций, описанных в секции interfaceи внутр. проц. и функц.>begin <операторы> end.<Заголовок модуля>::=→Unit→<имя_модуля> Имя должно совпадать с именем файла, где хранится исх. текст модуля.В секции Interfaceописываются внешние элементы (глоб. типы, константы, переменные, подпрогр.)Основная программа и другимодули имеют доступ к элементам описанных в интерфейсной части.<Интерфейсный раздел>::=<раздел_заголовков>::=Описание заголовков в интерфейсной секции является аналогом опережающего описания.Если при объявлении глобальных элементов используются константы или типы введенные в других модулях, то эти модули должны быть перечислены в директиве USESпосле Interface. Здесь рекомендуется указывать только те модули, которые необходимы только в этой секции.Секция Implementation. В этой секции описываются локальные элементы. Здесь же содержаться тела процедур и функций, заголовки которой описаны в секции Interface. Для данных процедур и функций заголовок содержит только имя.<раздел_реализации>::=В секции реализации содержится полное описание внутренних процедур и функций модуля.Внутренние подпрограммы недоступны вызывающей программе или другим модулям. Все элементы, описанные в интерфейсной секции доступны в секции реализации. Если в телах подпрогр., или при объявлениях в разделе реализации испольуются имена, объявленные в других модулях и эти модули не попали в директиву uses раздела interface, то они перечисляются в директиве usesпосле implementation.<раздел инициализации>::=В секции инициализации содержаться операторы, которые выполняются до операторов из тела программы. <раздел_инициал.> ::= →END---------------------------------→begin→<операт.>---- →end→ --------→<раздел_операт.>------- ------- ;←-----.!!!пример см. в вопросе№15!!! | Вопрос №15 Организация связи главной программы с библиотечными модулями пользователя.Если программный модуль использует несколько модулей UNIT, то их части инициализируются в порядке их перечисления в USESпрограммы.Все разделы модуля Unitявляются необязательными, но служебные слова, начинающие модуль UNITдолжны присутствовать обязательно.Unit Hollow; Interface ImplementationEnd.Пример(может быть неточным, писался с моего конспекта -):Unit U1; Interface Uses DOS; Const MyValue=724 ; Type Ned=(pon,vtor...) ; Var D: Ned;Procedure Set_Ned(var den: ned);Function Weekend: Boolean;Implementation Uses U2;Var D1,D2,D3: ned;Procedure set_ned;Begin <телопроцедуры> end;Function weekendBegin <телоф-ции> end;Begin D:=pon;End.Program MAIN;Uses U1;Var x: ned;Begin---------set_ned(x);---------end.Файл U1.pas должен быть скомпилирован с дир. компилятора destination=diskU1.tpuЧтобы найти модуль, указанный в предложении Usesпрограммой компилятор вначале просматривает turbo.tpl . Если нужного модуля здесь нет, то он ищется в текущем каталоге. Затем он ищется в каталоге, заданном Options\directories \units\directoriesЕсли файл модуля находится в другом месте или имя файла не совпадает с именем модуля, то компилятору следует передать нужное имя файла с путем, с помощью дирекивы компилятора {$N<имя_файла>}. Данная директива помещается непосредственно перед именем модуля в предложении Uses. |
| Вопрос №16 Особенности работы с библиотечными модулями.1) Перечисление модулей происходит в порядке их перечисления слева направо, в этом же порядке срабатывают разделы инициализации модулей. Инициализация происходит только при работе программы. При подключении модуля к модулю инициализация не выполняется. Порядок подключения модулей влияет на доступность типов данных, процедур и функций. Чтобы обеспечить доступ к содержимому другого модуля используются составные имена(U1.Ned, U1.D, U1.Set_Ned)Решение проблемы закольцованности: Зависит от того, в каком месте проги наблюдается закольцованность. Если оба модуля подключают друг друга в разделе реализации, то закольцованность автоматически разрешается компилятором.2) Если хотя бы один модуль подключает другой в разделе interface, то проблема закольцованности должна разрешаться самим программистом. В этом случае используется третий модуль, и в него помещаются все типы, переменные, подпроги и затем они удаляются из первых 2-ух модулей и к данным модулям подключается 3-ий.Достоинства: а)Наличие модулей позволяет использовать модульное программирование.б)Модули компилируются независимо друг от друга. При подключении они заново не компилируются.в)Наличие модулей позволяет создавать большие программы с суммарным размером исполняемого кода больше 64кб. |