|
Читайте также: |
Program Dinlist;
Type p_stud =^student;
student =record
fam: string[20];
next: p_stud;
End;
Var head: p_stud; {указатель на первый элемент}
curr: p_stud; {указатель на текущий элемент}
s: string[20];
Begin
Repeat
Write (‘vvod fam_’);
Readln (s);
If Length (s) < > 0 then
Begin
new (curr); {создание нового элемента, указатель curr
получает адрес свободной ячейки дин. памяти}
curr ^. fam: = s; {информационное поле fam
принимает знач. s}
curr ^. next: = head; {указатель нового элемента принимает
значение указателя head}
head: = curr; {head принимает значение адреса нового
элемента}
End;
Until length (s) = 0;
writeln (‘vvedenii spisok:’);
curr: = head; { curr принимает значение указателя начала}
while curr < > nil do
Begin
writeln (curr ^. fam); {печатается информационное поле
ячейки по адресу текущего указателя}
curr: = curr ^. next; {текущий указатель принимает значение
адреса следующего элемента}
End;
Readln;
End.
Рассмотрим подробно один шаг цикла формирования списка, т.е. добавления, например, второго элемента в начало списка: в списке есть Иванов, добавляем Петрова.
New (curr);
|
 |
2. curr ^. fam: = s;
Информационное поле fam по новому адресу принимает значение введенной с клавиатуры фамилии (Петров).
curr ^. next: = head;
Указатель нового элемента принимает значение указателя head, т.е. указывает на ячейку, на которую указывает head.
head
 |
3. head: = curr; – head указывает на адрес нового элемента
 |
Рассмотрим результат работы этой программы на экране.
vvod fam - Ivanov
vvod fam - Petrov
vvod fam - Sidorov
vvod fam –
vvedenii spisok: Sidorov
Petrov
Ivanov
Стек
Стек – структура переменной длины, в которой добавление новых элементов и удаление существующих производятся с одного конца, называемого вершиной стека.
LIFO
Занесение данных в стек производится аналогично вставке нового элемента в начало списка. Для извлечения элемента из стека некоторой переменной нужно присвоить значение первого элемента с вершины стека. После этого должно быть изменено значение указателя на вершину стека.
Пример: Создать стек для хранения целых чисел. Предусмотреть создание стека, т.е. добавление новых элементов по порядку. Затем организовать доступ к вершине стека и удаление элементов из стека. Вывести на экран их значения по порядку.
Условимся называть verh - указатель на вершину стека;
у – указатель текущего элемента при создании стека;
х – указатель текущего элемента при извлечении данных из стека;
а – переменная для ввода чисел с клавиатуры;
b – переменная для вывода чисел на экран.
Program st;
Type
Pstack = ^ stack;
Stack = record
Data: integer;
Next: pstack;
End;
Var
x, y, verh: pstack;
a, b, i, n: integer;
Begin
verh: = nil; {стек пуст}
writeln (‘n=’);
Readln (n);
for I:= 1 to n do
Begin
new (y); { создание нового элемента стека – у получает адрес
свободной ячейки}
writeln (‘a=’); readln (a); { ввод с клавиатуры числа}
y^. data: = a; {информационная часть получает значение а, т.е. по
этому адресу в поле data записывается а }
y^. next: = verh; {адресная часть принимает значение указателя
вершины стека}
verh:= y; {указатель вершины принимает значение
адреса нового элемента}
End;
writeln (‘элементы стека:’);
for i: = 1 to n do
Begin
b: = verh ^. data; { b принимает значение информационного поля
верхнего элемента}
writeln (‘b =’, b);
x: = verh; { указателю х присвоено значение указателя вершины
стека}
verh: = verh ^. next; {указатель вершины принимает значение
адреса следующего элемента стека}
dispose (x); {уничтожение указателя х, после чего ячейки,
содержавшие значение х ^ становятся свободными}
End;
Readln;
End.
При выполнении программы указатель verh вначале получает значение nil – стек пуст. Затем в цикле вводятся значения а: 1, 2, 3, 4. Эти значения заносятся в поле data элементов стека. Поле next при этом получает значение, на которое указывает verh.
|
|
 |
3)
При занесении новых элементов в стек указатель verh меняет свое значение и указывает каждый раз на только что введенный элемент.
Во второй части программы удаления элементов из стека указатель verh меняет свое значение в обратном порядке.
Очередь
Очередь – структура переменной длины, в которой добавление новых элементов производится в конец, а удаление существующих – из начала структуры.
FIFO 
Для описания элемента типа очередь нужны две переменные-указатели начала и конца очереди. Определим их как х1 и х2, тогда описание имеет вид:
Type poc = ^ oc;
Oc = record
Data: integer;
Next: poc;
End;
Var x1, x2: poc;
Над очередью определены 2 операции:
1) занесение элемента в конец очереди;
2) извлечение элемента из начала очереди.
Так как очередь может быть представлена списком, то занесение элемента в очередь соответствует занесению элемента в конец списка.
Опишем процедуру занесения элемента в конец очереди.
Procedure Write0 (var x1, x2: poc; c: integer); {здесь х1 и х2 – формальные параметры-переменные-указатели начала и конца очереди, с – новое значение}.
Var u: poc;
Begin
New(u); {указатель u получает адрес свободной ячейки
динамической памяти }
u ^. data: = c; {информационное поле получает значение с }
u ^. next: = nil; {адресная часть получает значение указателя
конца очереди}
If x1 = nil
then x1: = u {если очередь пуста, то указатель начала
х1 принимает значение нового адреса u }
Else
x2 ^. next: = u; {иначе элемент заносится в конец очереди по
адресу указателя х2 конца, далее х2 получает
значение адреса последнего элемента u }
x2: = u;
End;
Процедура извлечения элемента из очереди аналогична извлечению элементов из начала списка.
Т.к. извлечение элемента из пустой очереди осуществить нельзя, то сначала проверяем, есть ли элементы в очереди, т.е. задаем вопрос х1 = nil?
Procedure ReadO (var x1, x2: poc; var c: integer);
Var u: poc;
Begin
If x1 = nil then writeln (‘oсhered pusta’)
Else
Begin
c: = x1^. data;
u: = x1;
x1: = x1^. next;
Dispose(u);
End;
В процедуре ReadO для непустой очереди в статической переменной с сохраняется значение удаленного элемента х1 ^.data. Элемент удаляется из очереди сверху. Для этого переменная-указатель u получает значение х1 – адреса начала очереди; х1 становится значением указателя следующего элемента очереди, т.е. следующий элемент будет теперь в вершине очереди. Из динамической памяти удаляется элемент ранее находившийся в начале очереди, dispose(u).
Задача: создать очередь, содержащую целые числа. Удалить первый элемент из очереди и вывести его значение на экран.
В данной задаче мы будем вводить элементы до тех пор, пока элемент не будет равен нулю.
Дата добавления: 2015-12-08; просмотров: 60 | Нарушение авторских прав