Стандартные процедуры для работы с динамической памятью
-
| Имя и параметры | Типы параметров | Действие |
| New(p) | p - типизированный указатель | выделяет динамическую память равную размеру типа, на который указывает p, и возвращает указатель на нее в переменной p |
| Dispose(p) | p - типизированный указатель | освобождает динамическую память по указателю p, ранее выделенную процедурой New |
| GetMem(p,n) | p - указатель любого типа, n - integer | выделяет динамическую память размера n байт и возвращает указатель на нее в переменной p |
| FreeMem(p) | p - указатель любого типа | освобождает динамическую память по указателю p, ранее выделенную процедурой GetMem |
Действия с указателями
| Действие | Результат | ||||||||||||||||||||
| 1. Объявление type Plnt= ^ integer; Var a, b: Plnt; |
a ?
b ? | ||||||||||||||||||||
| 2. Выделение памяти New (a); New (b); |
b
| ||||||||||||||||||||
| 3. Занесение информации a^ :=1; b^ :=2; |
a a^
b b^ | ||||||||||||||||||||
| 4. Копирование информации a^ :=b^; |
a a^ a^=b^
b b^ a<>b | ||||||||||||||||||||
| 5.
а) а := b;
b) Dispose (a); a:= b;
|
a a^ a^=b^
b b^ a=b
a a^ b b^ | ||||||||||||||||||||
| 6. Присваивание пустого адреса nil b := nil |
a a^
b b^ |
Линейные списки -это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов, и для которых разрешается добавлять элементы между любыми двумя другими, и удалять любой элемент.
Кольцевые списки -это такие же данные, как и линейные списки, но имеющие дополнительную связь между последним и первым элементами списка.
Стек -это частный случай линейного односвязного списка, для которого разрешено добавлять и удалять элементы только с одного конца списка, который называется вершиной (головой) стека.
Для организации связи между элементами динамической структуры данных требуется, чтобы каждый элемент содержал кроме информационных значений , как минимум один указатель. В качестве элементов таких структур необходимо использовать записи, которые могут объединять в единое целое разнородные элементы.
Схематично такую структуру данных можно показать следующим образом:
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
Rec = record
Inf : integer;
|
|
|
Link : T
End;
Var P , Q : T ;
Создание прямого односвязного списка
В прямом односвязном линейном списке связь устанавливается от i-го элемента к i+1.
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Inf |
| Link |
| Program spisok; Type tt=^elem; Elem=record Inf:char; //информационное поле Next:tt //указательное поле End; Var p,begl,endl:tt; //объявление указателей Value:char; I,n:integer; Begin writeln('введите n') ; readln(n); Begl:=nil; //начальные установки Endl:=nil; // пустого адреса For i:=1 to n do Begin New(p); //выделение динамической памяти Readln(value); P^.inf:=value; //занесение данных в информационное поле P^.next:=nil; //занесение пустого адреса в указательное поле If endl=nil then begl:=p //если создается 1ый элемент списка Else endl^.next:=p; //если создается очередной элемент списка Endl:=p End; P:=begl; //установка р на начало списка While p<>nil do // nil-конец списка Begin Write(p^.inf, ' '); P:=p^.next //перемещение указателя р на следующий элемент списка End; End. | Результат решения задачи: введите n 4 п о л е п о л е |
|
|
|
В список можно добавлять элементы и удалять из списка.
| Действие | Последовательность операторов | |
| 1 | Поиск элемента с заданным значением | P:=begl; While ( p<>nil) and (p^.inf<>задан.значение) do p:=p^.next; |
| 2 | Добавление элемента в начало списка | New(p); P^.inf:=значение; P^.next:= begl; Begl:=p; |
| 3 | Перемещение указателя на элемент с адресом k | P:=begl; While p <>k do p:=p^.next; |
| 4 | Добавление элемента в середину списка после k-ого | New(p); P^.inf:=значение; P^.next:=k^.next; k^.next:=p; |
| 5 | Вставка элемента в середину списка перед k-ым | // вставка после k-го элемента New(p); P^.inf:=значение; P^.next:=k^.next; k^.next:=p; // перестановка информационных полей k ßàp t:=k^.inf; k^.inf:= P^.inf; p^.inf:=t; |
| 6 | Удаление элемента из начала списка | P:=begl; Begl:= P^.next; Dispose(p); |
| 7 | Удаление элемента из конца списка | P:=begl; While p^.next<>endl do //перемещение р на предпоследний элемент p:=p^.next; Dispose(endl); Endl:=p; Endl^.next:=nil; |
| 8 | Удаление элемента после k -го | p:=k^.next; k^.next:= P^.next; Dispose(p); |
| 9 | a) Удаление k–го элемента | p:=k^.next; k^.inf:= p^.inf; k^.next:= p^.next; Dispose(p); |
| б) Удаление k–го элемента | P:=begl; //установка p перед k While p^.next<>k do p:=p^.next; P^.next:= k^.next; Dispose(k); |
Пример1: Создать односвязный линейный список, содержащий числа.
Сложить положительные элементы списка.
| |
|
Program Spisok11;
{создать односвязный линейный список, содержащий числа.
Сложить положительные элементы списка.}
Uses Crt;
Type aa =^spisok;
spisok = record
zn:integer;
next:aa;
end;
Var
s,p:aa;
i,zna,kol, sum:integer;
// процедура добавление элемента в список
Procedure AddSp;
var q:aa;
Begin
if s=nil then //создается первый элемент
Begin
New(p);
s:=p
End
Else begin
q:=p;
New(p);
q^.next:=p;
end;
p^.next:=nil;
Writeln('Введите значение',i,' элемента');
readln(zna);
p^.zn:=zna;
end;
// функция определения конца списка
Function GoNext:boolean;
Begin
if p^.next <> nil then
Begin
p:=p^.next;
GoNext:=true;
End
elseGoNext:=false
end;
//функция освобождения памяти и вывода элементов списка
Function DisposeAll:boolean;
var q:aa;
Begin
p:=s;
while p<>nil do
Begin
q:=p^.next;
write(p^.zn,' ');
Dispose(p);
p:=q;
end ;
writeln;
writeln('Освобождение памяти...');
DisposeAll:=true;
end;
begin //операторы основной программы
s:=nil; // nil- признак конца списка
writeln('Введите количество элементов списка');
readln(kol);
for i:=1 to kol do//создание списка
Addsp;
p:=s; //установка р на начало списка
Repeat
if p^.zn>0 then
sum:=sum+p^.zn; //суммируем положительные элементы
until not gonext;
ifsum=0 then writeln('в списке нет полож. элементов')
else writeln('sum=',sum);
DisposeAll;
End.
Результаты решения задачи:
Введите количество элементов списка
4
Введите значение1 элемента
3
Введите значение2 элемента
5
Введите значение3 элемента
0
Введите значение4 элемента
-56
sum=8
3 5 0 -56
Освобождение памяти...
Дата добавления: 2018-06-01; просмотров: 391; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!