C.Ю.Соловьев

Методические материалы
по курсу
"Алгоритмы и алгоритмические языки"

Программа курса
Программирование в машинных кодах
Примеры-1
Примеры-2
Пример "большой" программы
Нисходящее программирование
Ссылочные типы
Структуры данных
Очереди и стеки
Деревья поиска
AVL-деревья
Таблицы
Хеш-таблицы
Динамические страницы

Ссылочные типы

(* Пример. Удалить в тексте повторные вхождения строк.            *)
(* Подход: 1. Разместить все строки текста в динамической памяти. *)
(*         2. Отметить вторые, третьи и пр. вхождения строк.      *)
(*         3. Удалить повторные строки, отмеченные на шаге 2.     *)
(*         4. Продолжить обработку текста.                        *)
(*                                                                *)
(* Полагаем, что строка не может содержать более 120 символов.    *)
(* Полагаем, что в тексте не более 2500 строк.                    *)
 
program T183(F);
type  CTPOKA = record  LENG : integer;
                       LIST : array [1..120] of char
               end;
     pCTPOKA = ^CTPOKA;
 
var        F : text;
           T : array [1..2500] of pCTPOKA;
       I,N,K : integer;
(* процедуры *)
begin   Reset(F);
(* Шаг 1: Текст F -> T[1..N]        *)
        N:=0;
        while not eof(F) do begin
           N:=N+1;
           new(T[N]);
           with T[N]^ do begin
              LENG:=0;
              while not eoln(F) do begin
                 LENG:=LENG+1;
                 Read(F,LIST[LENG])
              end
           end;
           Readln(F)
        end;
(* Шаг 2: T[повт]^.LENG:=-1         *)
(* Шаг 3: T[1..N]:= T[I]^.LENG >= 0 *)
        K:=0;
        for I:=1 to N do
        if T[I]^.LENG < 0 then dispose(T[I]) else begin
           K:=K+1;
           T[K]:=T[I]
        end;
        N:=K;
(* Шаг 4.                           *)
end.

(* Шаг 2: T[повт]^.LENG:=-1         *)
(* Шаг 2: T[повт]^.LENG:=-1         *)
        for I:=1 to N do
        if TWC(I) then T[I]^.LENG:=-1;
(* процедуры *)
function TWC(K : integer) : boolean;
   var I,J,M : integer;
           W : boolean;
begin   I:=0;
        W:=false;
        while (I < K-1) and (not W) do begin
           I:=I+1;
           M:=T[I]^.LENG;
           if M = T[K]^.LENG then begin
              for J:=1 to M do
              if T[I]^.LIST[J] = T[K]^.LIST[J] then M:=M-1;
              W:=(M = 0)
           end
        end
end;
(* Окончательный текст программы T183 *)
 
program T183(F);
type  CTPOKA = record  LENG : integer;
                       LIST : array [1..120] of char
               end;
     pCTPOKA = ^CTPOKA;
 
var        F : text;
           T : array [1..2500] of pCTPOKA;
       I,N,K : integer;
 
function TWC(K : integer) : boolean;
   var I,J,M : integer;
           W : boolean;
begin   I:=0;
        W:=false;
        while (I < K-1) and (not W) do begin
           I:=I+1;
           M:=T[I]^.LENG;
           if M = T[K]^.LENG then begin
              for J:=1 to M do
              if T[I]^.LIST[J] = T[K]^.LIST[J] then M:=M-1;
              W:=(M = 0)
           end
        end
end;
 
begin   Reset(F);
(* Шаг 1: Текст F -> T[1..N]        *)
        N:=0;
        while not eof(F) do begin
           N:=N+1;
           new(T[N]);
           with T[N]^ do begin
              LENG:=0;
              while not eoln(F) do begin
                 LENG:=LENG+1;
                 Read(F,LIST[LENG])
              end
           end;
           Readln(F)
        end;
(* Шаг 2: T[повт]^.LENG:=-1         *)
        for I:=1 to N do
        if TWC(I) then T[I]^.LENG:=-1;
(* Шаг 3: T[1..N]:= T[I]^.LENG >= 0 *)
        K:=0;
        for I:=1 to N do
        if T[I]^.LENG < 0 then dispose(T[I]) else begin
           K:=K+1;
           T[K]:=T[I]
        end;
        N:=K;
(* Шаг 4.                           *)
end.
(* Какую задачу решает следующий алгоритм шага 4 ?         *)
 
        Rewrite(F);
        for I:=1 to N do with T^[I] do begin
           for K:=1 to LENG do write(F,LIST[K]);
           writeln(F)
        end;

Вопросы?