Вставка и замена при представлении слов списочными структурами.
type
pComponent=^tComponent;
tComponent=record Content:
tChar; {содержимое слова/текста}
next:pComponent; {ссылка на следующую компоненту}
end;
pPosition=pComponent;
pWord=pComponent; {ссылка на начало списка}
{область определения( предусловие): тест не пуст » pT<>nil, p<>nil}
procedure Insert {ВставкаПосле}
(var pT {ОсновнойТекст} :pWord; pW {ВставляемоеСлово}: pWord; P {Позиция}:pPosition);
var
pn, {ссылка на новую компоненту}
pi, {ссылка на текущую позицию в W}
pk: pPosition; {ссылка на текущую позиция в T }
begin
pi:=pW;
pk:=P;
while pi<>nil do
begin {вставка i-го символа W}
new(pn); {порождаем новую компоненту}
pn^.Content:=pw.Content; {с содержимым равным символу w[k]}
pn^.next:=pk^.next; {вставляем его перед T[i+1]}
pk^.next:= pn; {и после T[i]}
pw:=pw^.next; {переходим к следующим символам}
pk:=pk^.next;
end;
end;
procedure Exclude {Исключение}
(var pT {ОсновнойТекст}:pWord; var pV { Новое}: pWord; pStart, pFinish {НачалоИсключения,КонецИсключения} : pPosition);
begin
var
pD, {ссылка на уничтожаемый символ}
pN, {ссылка на новый символ V}
pK: pPosition; {ссылка на текущую позицию в T}
begin
new(pV);
pV^.next:=nil; {вводим фиктивный/нулевой символ }
pLast:=pV; {причина - определить ссылку на последний символ}
pK:=pStart;
while pK<>pFinish do
begin {исключение i-го символа W}
{порождаем новый символ = T[k]}
new(pN);
pN^.Content:=pK^.Content;
pN^.next:=nil;
{делаем его последним в V}
pLast^.Next:=pN; pLast:=pN;
{удаляем текущий, переходим к следующему символу в T}
pD:=pK;
pK:=pK^.next; destroy(pD);
end;
{удаляем фиктивный/нулевой символ }
pD:=pV;
pV:=pV^.next; destroy(pD)
end;
§ 15. Формальные вычисления.
См. преамбулу «Алгоритмы символьной обработки». В частности, там определено понятие формального вычисления как нахождение текста (обозначения) результата операции по тексту (обозначениям) аргументов, в некоторой фиксированной системе обозначений.
Очевидно, деление «обозначение(имя)/значение, синтаксис/семантика» является фундаментальным не только в программировании, но и в целом, для нашего мышления (см. § 1 «Основные понятия…»). Но программист обязан понимать и условность этого деления – в реальности, все компьютерные вычисления формальны, реализуясь в конечном счете в алгоритмах символьной обработки последовательностей битов (см. § 8 «Машинно-ориентированное программирование»). Отсюда – очевидная важность рассматриваемой темы.
Рассмотрим ее на простом примере операции сложения натуральных чисел.
Задача. Найти запись (обозначение) суммы двух натуральных чисел по записям аргументов, не прибегая к преобразованиям типов. Обозначения чисел (в традиционной 10-ной системе счисления) представлены массивами.
type
tIndex=1..Len;
tCifer='0'..'9';
tNotation=array[tIndex] of tCifer;
tPair=record
First,Second:tCifer
end; {пара цифр}
{глобальный параметр - таблица сложения}
{PifagorTable: array[tCifer,tCifer] of tPair;}
procedure СложениеСтолбиком(Arg1,Arg2:tNotation; var Sum:tNotation; Error:boolean);
{Error - ошибка переполнения}
var
Um: '0'..'1'; {цифра "в уме"}
Pair:tPair;
i:tIndex;
begin
Um:='0';
for i:=1 to Len do
begin
Pair:= PifagorTable[Arg1[i],Arg2[i]]; {пара цифр от '00' до '18'}
if Um='0'
then begin Sum[i]:=Pair.Second;Um:=Pair.First end
else {Um=1}
if Pair.Second='9' {особый случай}
then { Pair.First='0' } Sum[i]:='0'
else begin Sum[i]:=succ(Pair.Second);Um:=Pair.First end;
end;
Error:=Um='1'
end;
Пример вычисления функции значения и обратной функции.
Задача. Найти запись (обозначение) суммы двух натуральных чисел по записям аргументов, прибегая к преобразованиям типов. Обозначения чисел (в традиционной 10-ной системе счисления) представлены массивами (также, как в предыдущей задаче).
procedure ToValue(cArg:tNotation; var iResult:integer);
var a:0..9; {значение очередной цифры}
begin
iResult:=0;
{вычисление многочлена S {ai 10 Len-i: i Î [1..Len]} по схеме Горнера}
for i:=1 to Len do begin a:= ord(cArg[i]))-ord('0'); iResult:=iResult*10+a; end;
end;
procedure ToName(iArg:integer; var cResult:tNotation; Error:boolean);
var
c:tCifer; {очередная цифра десятичной записи}
a:0..9; {значение очередной цифры}
OrdZero:integer; {номер символа '0' в таблице символов}
begin
OrdZero:=Ord('0'); k:=1;
while (iArg<>0) and (k<=Len) do
begin
a:= iArg mod 10; iArg:=iArg div 10;
cResult[k]:=chr(OrdZero+a);k:=k+1
end;
Error:=k>Len;
while k<=Len do begin cResult[k]:='0';k:=k+1 end;
end;
procedure Sum(cArg1,cArg2:tNotation;var cResult:tNotation;Error:boolean);
var iArg1,iArg2:integer;
begin
toValue(cArg1,iArg1); toValue(cArg2,iArg2); ToName(iArg1+iArg2,cResult,Error);
end;