I способ.
{ввод исходного слова, его представление в виде цепочки}
{формирование заглавного звена}
new(q); p:=q; p^.След:=nil;
read(sym); {чтение первого символа}
while sym <>’.’ do
begin write(sym); {печать введенного символа}
new(p^.След); p:=p^.След;
p^.Элем:=sym; p^.След:=nil;
read(sym);
end;
II способ.
read(sym); write(sym);
new(q); q^.Элем:=sym; q^.След:=nil;
p:=q;
while sym <>’.’ do
begin read(sym); write(sym);
new(p^.След); p:=p^.След;
p^.Элем:=sym; p^.След:=nil;
end;
Первый способ предпочтительнее.
Поиск заданного элемента в строке.
function поиск(st:список; эл:char; var res:связь):boolean;
var q:связь;
begin
поиск:=false;
res:=nil;
q:=st^.След;
while (q<>nil) and (res=nil) do
begin
if q^.Элем=эл then
begin
поиск:=true;
res:=q
end;
q:=q^.След
end
end.
Заметим, что за счет повторных обращений к этой процедуре можно найти все вхождения в строку заданного элемента – для нахождения очередного его вхождения достаточно снова обратиться к процедуре, задав в качестве первого фактического параметра ссылку на звено, которое содержало предыдущее вхождение заданного элемента (другими словами, задав в качестве исследуемой строки ту часть исходной строки, которая следует за этим звеном). Этот процесс следует завершить, когда при очередном обращении к процедуре будет выработано значение функции, равное false.
Удаление из строки заданного элемента. Пусть имеется фрагмент исходной цепочки, в котором представлены звенья с литерами Д, В и А
и пусть требуется исключить из строки литеру, следующую за литерой Д. Учитывая связь звеньев в цепочку с помощью ссылок, звено с литерой В будет исключено из цепочки, если звено с литерой Д будет ссылаться на звено с литерой А, минуя звено с литерой В:
Значит, для исключения из строки элемента В достаточно изменить ссылку у предшествующего ему элемента, причем в качестве новой ссылки у этого элемента надо принять ссылку, содержащуюся в исключаемом элементе.
Таким образом, описание процедуры исключения элемента из строки-цепочки можно описать следующим образом:
procedure удаление1(звено:связь);
begin
звено^.След:=звено^.След^.След
end
При описании этой процедуры сделано предположение, что исключаемое звено в строке существует, т.е. что звено, задаваемое в качестве фактического параметра в операторе процедуры (в виде ссылки на него), не является последним в строке – в противном случае результат выполнения процедуры будет неопределенным. Чтобы избежать такой ситуации, в описании процедуры можно предусмотреть контроль корректности задания фактического параметра и принять, например, решение о том, что если фактический параметр указывает на последнее звено строки, то строка остается без изменения:
procedure удаление2(звено:связь);
begin
if звено^.След<>nil then
звена^.След:=звено^.След^.След
end
Следует обратить внимание на то, что при выполнении каждой из этих процедур исключенное из строки звено тем не менее продолжает существовать и занимать место в памяти машины, хотя это звено и становится недоступным для использования. Такой способ может привести к весьма неэффективному использованию памяти за счет хранения в ней исключенных элементов строк. Для устранения этого недостатка в описании процедуры исключения можно предусмотреть уничтожение исключенного из цепочки звена с помощью процедуры dispose:
procedure удаление(звено: связь);
var q:связь;
begin
q:=звено^.След;
if q<> nil then begin
звено^.След:=звено^.След^.След;
dispose(q)
end
end;
Вставка заданного элемента. Быстрая вставка в строку заданного элемента также основывается на объединении отдельных звеньев в единую цепочку с помощью ссылок. Так, если имеется фрагмент цепочки
то вставка литеры P после литеры T должна привести к следующему изменению этого фрагмента:
Из этой схемы видно, что именно надо сделать для вставки нового звена после заданного:
1. Создать новый динамический объект, которым будет представлено вставляемое звено; этот объект должен иметь тип Звено, т.е. запись.
2. В поле Элем этой записи занести заданный символ.
3. В поле След этой записи занести ссылку, взятую из поля След того звена, за которым должно следовать вставляемое звено.
4. В поле След того звена, за которым должно следовать вставляемое звено, занести ссылку на это вставляемое звено.
Таким образом, описание процедуры вставки в строку заданного элемента может выглядеть следующим образом:
procedure вставка(звено: связь; элемент: char);
var q:Звено;
begin
new(q);
q^.Элем:=элемент;
q^.След:=звено^.След;
звено^.След:=q
end
Еще раз обратим внимание на то обстоятельство, что при описании всех приведенных выше процедур мы исходили из того, что любая строка-цепочка должна иметь заглавное, т.е нулевое звено. Это позволило добиться компактности описания процедур, особенно процедур удаления и вставки, с помощью которых можно производить и удаление первого элемента строки, и вставку перед первым ее элементом – для этого в качестве соответствующего фактического параметра в операторе процедуры надо задать ссылку на заглавное звено цепочки.
Задание 1. Задана непустая последовательность целых чисел. Определить n – количество этих чисел и вывести их в порядке возрастания.
Указание. Для решения этой задачи необходимо построить список, элементы которого упорядочены по возрастанию содержащихся в них целых чисел. Построение выполняется за п шагов. Первый шаг – это создание списка, состоящего из одного элемента, который содержит первое число последовательности. Очевидно, что такой список является упорядоченным. На i -м шаге (i = 2, 3,..., п) переходим от упорядоченного списка, элементы которого содержат числа последовательности с 1-го по i– 1 – ое, к упорядоченному списку, элементы которого содержат числа последовательности с 1-го по i– ое. Для выполнения такого перехода достаточно включить в список новый элемент, содержащий i– ое число последовательности. Его надо вставить непосредственно за последним по порядку элементом, содержащим число, меньшее чем i– ое. Если же все элементы исходного списка содержат числа, не меньшие чем i– ое, то новый элемент должен быть вставлен в начало списка. Для упрощения структуры программы необходимо строить упорядоченный список с заглавным элементом, поле инф которого используется для подсчета исходных чисел.
Данную задачу нельзя решить с помощью построения упорядоченного массива целых чисел, поскольку заранее неизвестно, сколько чисел будет упорядочиваться. Решение же этой задачи с помощью формирования файла, компоненты которого – целые числа, менее эффективно. При включении новой компоненты в файл (и исключении компоненты из файла) его почти всегда приходится переписывать целиком. Исключение составляет случай, когда новые компоненты дописываются в конец файла, открытого для записи.
Во всех рассмотренных примерах информационная часть элементов списка состояла из одного поля типа integer. В общем же случае она может содержать произвольное (фиксированное для данного типа элемента) количество полей разных типов. Ясно, что если значением переменной р является ссылка на элемент списка, то присоединяя к обозначению р^ через точку имя соответствующего поля, можно манипулировать с любым полем информационной части элемента списка.
Задание 2. Заданы два набора натуральных чисел, упорядоченных по возрастанию. Между ними стоит число 0. Вывести все данные натуральные числа в порядке возрастания.
Указание. Вначале построить по исходным данным два упорядоченных списка. Затем слить их в один упорядоченный список, изменяя только значения полей ссылочного типа элементов списков.
Дата добавления: 2015-07-12; просмотров: 86 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Действия над ссылками | | | Продовжте визначення: «Цитата – це…». |