b)dop^.temp:=2.5;{записываем число в информационное поле}
c)dop^.adr:=nil; {в поле «адрес следующего» элемента записываем nil}
d)pred^.adr:=dop;{в поле «адрес следующего» предыдущего элемента записываем адрес нового элемента}
5. Просмотр.Просмотр элементов списка выполняется последовательно с использованием дополнительного указателя:
f:=first;
while f<>nil do
Begin
writeln(f^.temp:4:2,' ');
f:=f^.adr;
end;
6. Удаление элемента из списка.Здесь возможно четыре случая:
a) Удаление единственного элемента
После удаления элемента список становится пустым, следовательно необходимо не только освободить память, выделенную для размещения элемента, но и в указатель списка first занести nill:
a)dispose(first);
b)first:=nill;
b) Удаление первого (не единственного) элемента из списка
Необходимо сохранить адрес следующего элемента в дополнительной переменной, освободить память элемента и записать в указатель списка адрес следующего элемента:
a)x:=first^.adr;
b)dispose(first);
c)first:=x;
с) Удаление элемента, следующего за данным (не последнего)
Необходимо запомнить адрес удаляемого элемента, изменить адресную часть данного элемента и освободить память:
a)x:=pred^.adr;
b)pred^.adr:=x^.adr;
c)Dispose(x);
d)Удаление последнего элемента
a)x:=pred^.adr;
b)pred^.adr:=nil;
c)dispose(x);
Задача 1. Создать программу формирования связанного списка в ходе ввода данных.
program spisok2;
uses crt;
Type
P=^Element;
Element=Record
temp:Real; adr:P;
End;
Var Elem,Beg:P;
X: Real;
Ch: Char;
Begin {Определение адреса начала списка и его сохранение}
clrscr;
NEW(Elem);
Beg:=Elem;
Elem^.adr:=Elem;
{Диалоговый ввод значений с занесением их в список
и организацией связи между элементами}
While Elem^.adr<>Nil Do
Begin
Write('Vvecite chislo:');
ReadLn(Elem^.Temp);
Write('Prodolgit? (Y/N)');
ReadLn(Ch);
If (Ch='n') Or (Ch='N')
Then Elem^.adr:=Nil
Else Begin
NEW(Elem^.adr) ; Elem^.adr:=elem;
End
end;
WriteLn('Ввод данных закончен');
{Вывод полученной числовой последовательности}
WriteLn('Контрольная распечатка');
Elem:=Beg;
Repeat
WriteLn(elem^.temp:8:3) ;
Elem:=Elem^.adr
Until Elem=Nil;
readln
End.
Стек
Стекомназывается динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу: LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым.
Обычно над стеками выполняется три операции:
начальное формирование стека (запись первой компоненты);
добавление компоненты в стек;
выборка компоненты (удаление).
Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная. Пусть описание этих переменных имеет вид:
var pTop, pAux: Pointer;
где pTop - указатель вершины стека;
pAux - вспомогательный указатель.
Пример 2. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея, В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.
Program STACK;uses Crt;type Alfa= String[10]; PComp= ^Comp; Comp= Record sD: Alfa; pNext: PComp end;var pTop: PComp; sC: Alfa; Procedure CreateStack(var pTop: PComp; var sC: Alfa); begin New(pTop); pTop^.pNext:=NIL; pTop^.sD:=sC end;Procedure AddComp(var pTop: PComp; var sC: Alfa); var pAux: PComp; begin NEW(pAux); pAux^.pNext:=pTop; pTop:=pAux; pTop^.sD:=sC end; Procedure DelComp(var pTop: PComp; var sC:ALFA); begin sC:=pTop^.sD; pTop:=pTop^.pNext end; begin Clrscr; writeln(' ВВЕДИ СТРОКУ '); readln(sC); CreateStack(pTop,sC); repeat writeln(' Введите строку '); readln(sC); AddComp(pTop,sC) until sC='END';writeln(' ВЫВОД РЕЗУЛЬТАТОВ '); repeat DelComp(pTop,sC); writeln(sC); until pTop = NIL;readkey; end.
ЗАДАНИЯ ДЛЯ ВЫПОЛНЕНИЯ:
1.В программе имеются описания
Var P, Q:^integer; R:^char;
Какие из следующих оператором неправильные и почему?
a) P:=Q;
b) Q:=R;
c) P:=Nil;
d) R:=Nil;
e) Q:=Р^;
f) R^:=P^;
g) P^:=Nil;
h) Q^:=Ord(R^);
i) If R<>Nil then R^:=Nil^;
j) If Q>Nil then Q^:=P^;
k) If P=Q then Write(Q);
l) If Q<>R then Read(R^).
2.В программе имеются описания
Type A=^Char;
B =Record Fl:Char; F2:A End;
Var P:^B; Q:A;
Определить значения всех указателей и динамических переменных после выполнения следующих операторов:
NEW(Q); Q^:='7';
NEW(P); P^.Fl:=Succ(Q^); P^.F2:=Q;
3.Найти ошибки в следующей программе:
Program Example;
Var А,В: ^Integer;
Begin if A=nil then read(A);
A^:=5; B:=nil; B^:=2;
NEW(B); read(B^); writeLn(B,B^);
NEW(A); B:=A; DISPOSE(A); B^:=4
End.
4.Связанный список представляет собой символьную цепочку из строчных латинских букв. Описать процедуру или функцию, которая:
a.определяет, является ли список пустым;
b.заменяет в списке все вхождения одного символа на вхождения другого;
c.меняет местами первый и последний элементы непустого списка;
d.проверяет, упорядочены ли элементы списка по алфавиту;
e.определяет, какая буква входит в список наибольшее количество раз.
Контрольные вопросы
1.Что такое динамическое выделение памяти? Статическое? Достоинства и недостатки?
2.Что такое указатель? Его описание?
3.Процедуры динамического выделения памяти?
4.Назовите известные вам динамические структуры данных?
5.Какой тип используется при описании элементов списка?
6.Дайте определение понятиям список, стек, очередь?
