Типовые алгоритмы работы со списками 1 ТИПОВЫЕ АЛГОРИТМЫ РАБОТЫ СО

переменных, используемых в примерах

var
Head : Plist; { Указатель

на голову списка }
Tail : Plist; { Указатель на «хвост» списка }
P : Plist; { Указатель на текущий элемент списка }

TData – тип данных, размещаемых в информационной части элемента списка
{в примерах заменяется в соответствии с конкретной ситуацией}

пустого линейного односвязного списка)
Procedure InitList;
begin
Head := NIL;

Tail := NIL;
end;

А2. Добавить элемент в конец односвязного списка

Var
pnew :PList; {указатель на новый элемент}
begin
new(pnew); {запросить память}
pnew^.data:=indata; {присвоить полю Data значение}
if Head <> nil then {список непустой ?}
Tail^.Next := pnew
else
Head := pnew;
{end if}
pnew^.Next:=nil;
Tail := pnew;
end;

(вернув поле данных)
Procedure OutList(var OutDat:TData);
Var
P:Plist;
begin

OutData := Head^.Data;
p:=Head;
Head:=Head^.Next; {присвоить указателю на голову списка ссылку
на новый первый (бывший второй) элемент}
Dispose(p); {освободить память, занятую элементом}
end;

А4. Удалить элемент из середины списка (с освобождением памяти)

P := Prev^.next;
Prev^.Next := P^.Next;
Dispose(P); {освободить память}

списка
{Для случая односвязного списка}
pnew^.next:=prev^.next;
prev^.next:=pnew;
А6. Обработать каждый

элемент линейного списка

P := Head;
while P <> NIL do begin
Выполнить операцию обработки элемента P^
P := P^.Next; {перейти к следующему элементу}
end;

целое число.
Задача обработки:
Подсчитать количество элементов, значение информационных
полей которых

превышает значение Value

Count := 0;
P := Head;
while P <> NIL do begin
if P^.Data > Value then
Count := Count +1;
{end if}
P := P^.Next;
end;

условию
Var
flagFound : boolean;
begin
P :=

Head;
flagfound := false;
while (P<>NIL) and (not flagfound) do
if (выполнено условие) then
flagfound := true {элемент найден}
else
P := P^.Next;
{end while}
end;

:= Head; {Установить указатель на удаляемый элемент}
while PNIL do begin

Head := P^.Next; {установить ссылку на следующий}
Dispose(P); {освободить память,
занятую удаляемым элементом}
P := Head; {установить новый удаляемый элемент }
end;

список
(сохранив упорядоченность)
Procedure InSortList(indata : integer);
var
p, pnext, pnew

: plist;
begin
new(pnew);
pnew^.data := indata;
if (Head=NIL) or (Head^.data > indata) then begin
{добавить элемент в начало списка}
pnew^.next := Head;
Head := pnew;
end
else begin
p := Head;
pnext := p^.next;
while (pnext <> NIL) and (pnext^.data < indata) do begin
p := p^.next;
pnext := pnext^.next;
end; {включить элемент}
pnew^.next := pnext;
p^.next := pnew;
end;
end;

вернуть указатель на него
function search(indata:integer):plist;
var
p : plist;
begin

p := head;
while (p <> nil) and (p^.data <> indata) do
p := p^.next;
{end}
search := p;
end;

списка
procedure work(head:plist);
var
p : plist;
begin
p

:= head;
while (p^.next <> head) do
begin
Обработать элемент p^
p := p^.next;
end;
end;

procedure work(head:plist);
var
p : plist;
begin
p := head;
while (p <> nil) and (p^.next <> head) do
begin
Обработать элемент p^
p := p^.next;
end;
end;

все подстроки, заключенные в круглые скобки.
Порядок вывода: после строки со

словом «Результат:» вывести в отдельных строках все найденные подстроки.
Если одна подстрока является частью другой, то сначала вывести более короткую.

Задачу решить с использованием списочной структуры типа «стек»:

Примечание. Алгоритм работы со стеком предполагает использование операций:
hush() – занести в вершину стека новую запись
pop() – извлечь запись из вершины стека, освободив занятую ей память

Метод решения

Рассматривая строку как массив, обеспечить последовательный анализ каждого символа, начиная с первого в строке.
В стек загружать позиции открывающих скобок.
Вывод подстроки производить когда встретится парная для нее закрывающая скобка.

Type
PStack = ^TStack;
TStack = record

pos : integer;
next : PStack;
end;
procedure push(var Head:Pstack; nom:integer);
function pop(var Head:Pstack):integer;

Implementation
procedure push(var Head:Pstack; nom:integer);
var
pnew : Pstack;
begin
New(pnew);
pnew^.pos := nom;
pnew^.next := Head;
Head := pnew;
end;

function pop(var Head:Pstack):integer;
var
p : Pstack;
begin
if Head = nil then
pop := 0
else begin
p := Head;
pop := p^.pos;
head := Head^.next;
Dispose(p);
end;
end;
begin
end;

Файл «mystack.pas»

на подстроки}
uses
mystack;
var
st : string;
j,

j1 : integer;
Head : pstack;
begin
st := '';
head := nil; {инициализация стека}
for j:= 1 to Length(st) do
if st[j]='(' then
push(head, j)
else if st[j]=')' then begin
j1 := pop(head);
if (j1<>0) and (j-j1>1) then
writeln(copy(st, j1, (j-j1+1));
{endif}
{endif}
end;
{освободить память, если стек не пустой}
while head<>nil do
j1 := Pop(head);
{end}
end.

Исходная строка: (((4+6)*7)+(6*(8+7))
Результат:
4+6
(4+6)*7
8+7
6*(8+7)

Проверить программу на примере:

и поместить их в список.
Вывести на экран каждый второй элемент

этого списка.
Решить задачу из Тестера – Матрицы - 3