Очередь

Программирование в среде Delphi

Динамические структуры данных

Организация связных списков

Очередь

Динамическая память и указатели уже рассматривались в параграфе 1.5 первой части данного учебного пособия «Создание консольных приложений». Эти знания мы будем использовать при изучении организации связных списков.

Связный список – это динамическая структура, в которой отдельные элементы, имеющие тип запись, последовательно связаны друг с другом посредством того, что одно из полей каждого элемента связного списка имеет тип указатель и содержит адрес очередного элемента списка.

Однонаправленный связный список схематически можно представить в виде

Опишем динамическую структуру данных, которая является однонаправленным списком. Каждый элемент этой динамической структуры – это запись, имеющая два поля. Первое поле отводится под целое число (информационное поле), а второе содержит адрес следующего элемента списка.

type link = ^elem;

elem = record

val : integer;

next : link

end;

var L : link;

Переменная L предназначена для указателя на элемент списка. Тогда L^ – это сам элемент списка (динамическая переменная типа запись). Таким образом, L^.val и L^.next – это, соответственно, обозначения для полей этой записи. В Delphi знак разыменования ( ^ ) при обращении к полям динамических структур можно опускать, т.е. к полям данной динамической структуры можно обратиться следующим образом: L.val и L.next

Построим список, информационные поля которого будут содержать целые числа, прочитанные из текстового файла file1.txt.

type link = ^elem;

elem = record

val : integer;

next : link

end;

var L, p, q : link;

begin

assignfile(f, ' file1.txt ');

reset(f);

new(L); {L – указатель на первый элемент списка}

read(f, L.val); {В информационное поле первого элемента записали первое число}

p:=L; {p – указатель на последний созданный элемент списка}

while not eof(f) do

begin

new(q) {q – указатель на очередной элемент списка}

read(f, q.val); {заполнили его информационное поле}

p.next:=q; {записали в ссылочное поле предыдущего элемента адрес q}

p:=q {объявили элемент q последним}

end;

p.next:=nil; {в ссылочное поле последнего элемента записали адрес nil}

closefile(f)

end.

Построенный список называется очередью. Вновь созданные элементы пристраиваются в конец очереди. Работа с элементами очереди начинается с её начала. Для очереди используется обозначение fifo (first in first out – первым пришёл, первым ушёл).

Задача 1. Создать очередь, информационные поля которой содержат числа из текстового файла file1.txt. Вывести значения информационных полей очереди в поле метки. Содержимое файла file1.txt:

14 -9 8 -22 39

-1 -13 0 4 -7

27 5 -2 18 3

Окно работающего приложения:

На форму поместим кнопку button1 с надписью «Создать очередь» и кнопку button2 с надписью «Показать очередь». Для метки Label1 установим свойства

Полный текст модуля:

unit Unit1;

interface

uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Button1: TButton;

Button2: TButton;

Label1: TLabel;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

end;

type link = ^elem;

elem = record

val : integer;

next : link

end;

var Form1: TForm1; L:link;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var p, q : link; f : textfile;

begin

assignfile(f, ' file1.txt '); reset(f);

new(L);

read(f, L.val);

p:=L;

while not eof(f) do

begin

new(q); read(f, q.val); p.next:=q; p:=q

end;

p.next:=nil;

closefile(f); showmessage(' Очередь создана ')

end;

procedure TForm1.Button2Click(Sender: TObject);

var p:link;

begin

label1.Caption:='';

p:=L;

while p<>nil do

begin

label1.Caption:=label1.Caption + inttostr(p.val) + ' '; p:=p.next

end;

end;

end.

Задача 2. Создать очередь, информационные поля которой содержат числа из текстового файла file1.txt. Вставить в список новый элемент с информационным полем d после первого элемента. Содержимое файла file1.txt: 14 -9 8 -22 39

-1 -13 0 4 -7

27 5 -2 18 3

Проект для решения задачи 2 будем создавать на основе проекта задачи 1. Добавим на форму приложения задачи 1 кнопку button3 с надписью «Вставка после 1 элемента». Со страницы Additional добавим компонент LabeledEdit1, представляющий собой комбинацию однострочного текстового поля с меткой. Надпись в метке определяет свойство EditLabel (Caption). В модуль Unit1 добавим процедуру обработки события щелчка по кнопке «Вставка после 1 элемента».

procedure TForm1.Button3Click(Sender: TObject);

var r:link; d:integer;

begin

d:=strtoint(LabeledEdit1.Text);

new(r); r.val:=d; r.next:=L.next; L.next:=r;

end;

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

Работа приложения должна начинаться с нажатия на кнопку «Создать очередь». После появления сообщения «Очередь создана», нужно ввести значение d (в данном случае введено число 100) и нажать на кнопку «Вставка после 1 элемента». Для просмотра преобразованного списка нужно нажать кнопку «Показать очередь».

Задача 3. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [-30, 30]. Вставить в список новый элемент с информационным полем 100 за каждым отрицательным числом.

Создание очереди:

procedure TForm1.Button1Click(Sender: TObject);

var p, q : link; i : byte;

begin

randomize;

new(L);

L.val:= -30 + random(61);

p:=L;

for i:=2 to 20 do

begin

new(q);

q.val:= -30 + random(61);

p.next:=q;

p:=q

end;

p.next:=nil;

showmessage('Очередь создана')

end;

Вставка в список нового элемента с информационным полем 100 за каждым отрицательным числом:

procedure TForm1.Button3Click(Sender: TObject);

var w, r : link;

begin

w:=L;

while w<>nil do

begin

if w.val<0 then

begin

new(r); r.val:=100; r.next:=w.next; w.next:=r;

w:=r.next

end

else w:=w.next

end;

end;

Процедура обработки события нажатия на кнопку «Показать очередь» такая же, как в задаче 1.

Работа приложения должна начинаться с нажатия на кнопку «Создать очередь». После появления сообщения «Очередь создана», нужно нажать кнопку «Показать очередь», чтобы увидеть созданный список. Затем нажать кнопку «Вставка элемента». Для просмотра преобразованного списка нужно нажать кнопку «Показать очередь».

Задача 4. Создать очередь, информационные поля которой содержат строки из файла file2.txt . Удалить из списка второй элемент.

Содержимое файла file2.txt: file

edit

search

view

project

run

component

database

tools

window

help

Описание типа динамической структуры будет иметь вид:

type link = ^elem;

elem = record

val : string;

next : link

end;

Создание очереди:

procedure TForm1.Button1Click(Sender: TObject);

var p, q : link; f : textfile;

begin

assignfile(f, ' file2.txt '); reset(f);

new(L);

readln(f, L.val);

p:=L;

while not eof(f) do

begin

new(q); readln(f, q.val); p.next:=q; p:=q

end;

p.next:=nil;

showmessage('Очередь создана')

end;

Выведение информационных полей списка в столбик в метку Label1:

procedure TForm1.Button2Click(Sender: TObject);

var p : link;

begin

label1.Caption:='';

p:=L;

while p<>nil do

begin

label1.Caption:=label1.Caption + p.val + #13; p:=p.next

end;

end;

Удаление второго элемента списка:

procedure TForm1.Button3Click(Sender: TObject);

var z : link;

begin

z:=L.next; L.next:=z.next; dispose(z)

end;

Удаление элемента, осуществляемое этой процедурой, схематически можно изобразить следующим образом:

Задача 5. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [-40, 40]. Удалить из списка все отрицательные числа.

В предыдущей задаче мы научились удалять элемент, стоящий за данным элементом (в задаче 4 мы удаляли 2^ой элемент, как элемент, стоящий за 1^ым элементом списка). Чтобы применить этот алгоритм в задаче 5, мы должны учесть, что отрицательный элемент может стоять в списке первым. Чтобы сделать первый элемент списка не первым, используют метод фиктивного элемента. Этот метод заключается в том, что перед первым элементом списка добавляют элемент с пустым информационным полем и ссылочным полем, содержащим адрес первого элемента списка ( L ).

procedure TForm1.Button3Click(Sender: TObject);

var w, r, z : link;

begin

new(r); r.next:=L;

w:=r;

while w.next<>nil do

if w.next.val<0 then

begin z:=w.next; w.next:=z.next; dispose(z) end

else w:=w.next;

L:=r.next

end;

В данной процедуре r – фиктивный элемент, w очередной элемент списка. Мы просматриваем все элементы w до предпоследнего и проверяем, является ли элемент, стоящий за w (w.next) отрицательным. Если да, то мы его удаляем. В заключение первый элемент нового списка получает имя L (если этого не сделать, список может остаться без ″головы″ в случае, когда первый элемент исходного списка – отрицательное число).

Задачи

Задача 6. Создать очередь, информационные поля которой содержат числа из текстового файла file1.txt. Вставить в конец списка (после последнего элемента) новый элемент с информационным полем d.

Задача 7. Создать очередь, информационные поля которой содержат числа из текстового файла file1.txt. Вставить в начало списка (перед первым элементом) новый элемент с информационным полем d.

Задача 8. Создать очередь, информационные поля которой содержат числа из текстового файла file1.txt. Вставить новый элемент с информационным полем d после 9^ого элемента списка.

Задача 9. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [-50, 50]. Удалить из списка последний элемент.

Задача 10. Создать очередь, информационные поля которой содержат числа из текстового файла file3.txt. Удалить из списка за каждым вхождением элемента с информационным полем, равным d, один элемент, если он отличен от d. Содержимое файла file3.txt:

26 11 -8 34 2

41 -5 11 11 -37

-15 11 29 62 44

Задача 11. Создать очередь, информационные поля которой содержат строки из файла file4.txt (Список фамилий учащихся). Удалить из списка фамилии, начинающиеся с буквы ′ С ′.

Содержимое файла file4.txt: Семёнов

Антонова

Кузнецов

Самойлов

Егорова

Колесников

Сидоров

Смирнова

Петрова

Сафонов

Указание. Использовать метод фиктивного элемента.

Задача 12*. Создать очередь, информационные поля которой содержат строки из файла file4.txt (Список фамилий учащихся). Удалить из списка первую фамилию, начинающуюся с буквы ′ К ′. (Учесть, что такая фамилия может оказаться первой в списке.)

Указание. Использовать метод фиктивного элемента.

Задача 13*. Создать очередь, информационные поля которой содержат строки из файла file5.txt (Список фамилий учащихся, упорядоченный по алфавиту). Вставить в этот список новую фамилию с сохранением порядка.

Провести тестирование проекта для следующих исходных данных:

1) Авдеев 2) Кротов 3) Гаврилов 4) Шмелёв

Содержимое файла file5.txt: Антонова

Воротников

Егорова

Колесников

Кузнецов

Павлов

Петрова

Сафонов

Харитонов

Указание. Использовать метод фиктивного элемента.

Задача 14**. Считалочка. N ребят расположены по кругу. (Каждому присвоен номер по порядку). Начав отсчёт от первого, удаляют каждого k-ого, смыкая при этом круг. Определить номер последнего, оставшегося в круге. ( k£N )

Тест 1: k=3 N=7 Ответ: 4

Тест 2: k=4 N=11 Ответ: 9

Указание. Для решения задачи использовать очередь, в которой ссылочное поле последнего элемента содержит адрес первого элемента.

21

Стек

Однонаправленный список, в котором новый элемент добавляется не в конец, а в начало, впереди предыдущего элемента, называется стек. Элемент, который добавлен в стек последним, называется вершиной стека. С него и начинается обработка элементов стека. Отсюда и обозначение стека – lifo (last in first out – последним пришел, первым ушёл).

Задача 15. Создать стек, информационные поля которого содержат числа из текстового файла file1.txt. Вывести значения информационных полей стека в поле метки. Содержимое файла file1.txt:

14 -9 8 -22 39

-1 -13 0 4 -7

27 5 -2 18 3

Полный текст модуля:

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Button1: TButton;

Button2: TButton;

Label1: TLabel;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

end;

type link = ^elem;

elem = record

val : integer;

next : link

end;

var Form1: TForm1; p : link;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var q : link; f : textfile;

begin

assignfile(f, ' file1.txt '); reset(f);

p:=nil;

while not eof(f) do

begin new(q); read(f, q.val); q.next:=p; p:=q end;

closefile(f); showmessage('Стек создан')

end;

procedure TForm1.Button2Click(Sender: TObject);

var q : link;

begin

label1.Caption:='';

q:=p;

while q<>nil do

begin

label1.Caption:=label1.Caption + inttostr(q.val) + ' ';

q:=q.next

end;

end;

end.

Задача 16. Написать программу, проверяющую правильность расстановки круглых скобок в арифметическом выражении.

В процессе работы приложения анализируем символы строки, содержащей арифметическое выражение. Если очередной символ – открывающаяся скобка, то она записывается в стек. Если же это закрывающаяся скобка, то находящаяся в вершине стека открывающаяся скобка из стека удаляется при условии, что стек не пуст. Если же стек пуст, то это означает возникновение ошибки в расстановке скобок. Если же такая ошибка не встретилась и по окончании просмотра символов строки стек пуст, то расстановка скобок в выражении сделана правильно. type

TForm1 = class(TForm)

Edit1: TEdit;

Button1: TButton;

Label1: TLabel;

procedure Button1Click(Sender: TObject);

end;

type link = ^elem;

elem = record

val : char;

next : link

end;

var Form1: TForm1;

implementation

{$R *.dfm}

procedure in_stack(var p:link; d:char);

var r:link;

begin new(r); r^.val:=d; r^.next:=p; p:=r end;

procedure del_stack(var p:link);

var r:link;

begin r:=p; p:=p^.next; dispose(r) end;

procedure TForm1.Button1Click(Sender: TObject);

var i:integer; t:boolean; q:link; s, str : string;

begin

s:=edit1.Text; q:=nil; t:=true; i:=1;

while (i<=length(s)) and t do

begin

if s[i] = ' ( ' then in_stack(q, s[i])

else if s[i] = ' ) ' then

if q<>nil then del_stack(q) else t:=false;

inc(i)

end;

t:=t and (q=nil);

if t then str:=' Правильно ' else str:=' Ошибка '; label1.caption:=str;

end;

end.

Задачи

Задача 17. Преобразовать последовательность действительных чисел, записанных в файле file6.txt, расположив сначала отрицательные числа последовательности, а затем неотрицательные. При этом порядок как отрицательных, так и неотрицательных чисел изменяется на обратный. Для отображения содержимого файла на форме использовать компонент Memo1.

Указание. Для решения задачи создать два стека: с отрицательными и с неотрицательными числами последовательности.

Содержимое файла file6.txt: 19.5 8.06 -43.1 14.9 -35.8

-27.02 0 5.17 62.4 -4.7

Задача 18. Даны целые числа a₁, a₂, … a_n (n=20), содержащиеся в текстовом файле file7.txt. Вычислить значение выражения

p₁ × 10 + p₂ × 100 + p₃ × 1000 + … ,

где p₁, p₂ , p₃ , … – встречающиеся в последовательности положительные числа, взятые в обратном порядке (начиная с последнего встретившегося положительного числа). Содержимое файла file7.txt:

5 -26 8 -12 19

-10 -13 0 4 -7

9 1 -2 18 -63

Указание. Для решения задачи сформировать стек из положительных чисел последовательности.

Задача 19**. Написать программу для вычисления значения выражения, представленного в обратной польской записи.

Обычная запись Обратная польская запись

(b + c) * d b c + d *

a + (b + c) * d a b c + d * +

(6 + 8)/2 + 11 6 8 + 2 / 11 +

Указание. Просматривая строку, в которой записано выражение, анализируем очередной символ. Если это число, то записываем его в стек. Если это знак операции, то достаём два элемента из стека, выполняем арифметическую операцию, определяемую этим знаком, и заносим результат в стек.