Занятие №15. Часть 1: Динамические структуры данных: указатели и списки

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

• размер динамических данных заранее неизвестен;
• память под них выделяется во время исполнения программы;
• динамические данные, как правило, не имеют идентификаторов (имени в стандартном понимании статических данных), но имеют адрес в памяти;
• обращение к динамическим данным осуществляется по их адресу в памяти.

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

Указатели

• Указатели в Паскале необходимы при работе с динамической памятью.
• Переменная типа «указатель» в качестве своего значения содержит адрес участка динамической памяти, с которой связан этот указатель.

• Типизированные указатели:



• Универсальные нетипизированные указатели могут хранить адрес переменной любого типа:

Таким образом, указатель может находиться в одном из трех состояний:

• пока не инициализирован;
• содержит адрес размещения;
• содержит значение константы NIL; такой указатель называется пустым, то есть не указывает ни на какую переменную.

1
2
3
4
5
6
7
8
9
10

var n, k: integer;
    pI: ^integer;
begin
  n := 4;
  pI := @n;
  writeln('Адрес n ='  , pI); 
  writeln('n = ', pI^); 
  k := 4*(7 - pI^);     // k = 4*(7 - 4) = 12 
  pI^ := 4*(k - n);     // n = 4*(12 – 4) = 32
end.

Другой вариант присваивания значений — использование служебного слова NEW:

1
2
3
4
5
6
7

var pI: ^integer;
begin
  new(pI);
  pI^ := 4;
  writeln('Адрес  ='  , pI); 
  writeln('Значение = ', pI^); 
end.

1
2
3
4
5
6
7
8
9
10
11

Type rec = Record
          Name   : string[30];
          Surname:  string[30];
end;
var
	P: ^rec;
begin
new(P);
P^.Name:='Иван';
write(P^.Name); // Иван
end.

Списки

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

Каждый элемент списка организован следующим образом:

• содержит поля с полезной информацией;
• содержит специальное поле (или несколько полей), которое хранит адрес другого элемента списка.

type ukazatel = ^elem_spiska;
elem_spiska = record
  znach:integer;
  next: ukazatel;
 end;
...

Рассмотрим потребность использования динамических структур — списков на примере:

Алгоритм выполнения программы:

1. создать список;
2. если слова в файле закончились, то остановка;
3. считать слово и искать его в списке;
4. если слово найдено, то увеличить счетчик повторов слов, иначе добавить слово в список;
5. перейти к шагу 2.

• Список состоит из начального узла — головы — и связанного с ним списка.
• Каждый элемент списка содержит информационную и ссылочную части. Т.е. каждый элемент имеет информационное поле (поля) — полезная информация — и ссылку (ссылки), то есть адрес на другой элемент списка.
• Односвязный (линейный) список: структура, каждый элемент которой «знает» адрес только следующего за ним элемента.

type PNode = ^Node;   { указатель на узел }   
     Node = record    { структура узла }
       word: string[40]; { слово }
       count: integer;   { счетчик повторов слов }
       next: PNode;      { ссылка на следующий }
     end;

Для доступа к списку достаточно необходимо знать адрес его головного элемента:

var Head: PNode;
...
Head := nil;

Для решения нашей задачи запрограммируем функцию для создания узла. На вход функции подается новое слово, возвращает функция адрес нового узла, созданного в памяти.

function CreateNode(NewWord: string): PNode;
var NewNode: PNode;
begin
  New(NewNode);
  NewNode^.word := NewWord;
  NewNode^.count := 1;
  NewNode^.next := nil;
  Result := NewNode;
end;

Добавить узел можно:

• в начало списка;
• в конец списка;
• после заданного узла;
• до заданного узла.

Чтобы добавить узел в начало списка:

1. Установить ссылку нового узла на голову списка:

NewNode^.next := Head;

NewNode^.next := Head;



2. Обозначить новый узел как голову списка:

Head := NewNode;

Head := NewNode;

Выполним добавление узла списка на Паскале в виде процедуры:

procedure AddFirst ( var Head: PNode; NewNode: PNode );
begin
  NewNode^.next := Head;
  Head := NewNode;
end;

Чтобы добавить узел после заданного:

1. Установить ссылку нового узла на узел, следующий за конкретным (p):

NewNode^.next = p^.next;

NewNode^.next = p^.next;



2. Установить ссылку узла p на новый узел:

p^.next = NewNode;

p^.next = NewNode;

Для добавления узла в конец списка или перед заданным узлом необходимо уметь перемещаться по списку.

Алгоритм выполнения:

• устанавливаем дополнительный указатель pp на голову списка;
• в случае когда дошли до конца списка, т.е.если указатель pp равен значению nil, то делаем остановку;
• производим необходимые действия над узлом с адресом pp;
• делаем переход к следующему узлу — pp^.next.

var pp: PNode;
...
pp := Head;  // начинаем с головы 
while pp <> nil do begin // цикл пока не достигнут конец 
  ...                   // выполняем действия с pp
  pp := pp^.next;         // переходим к следующему узлу
end;

Чтобы добавить узел в конец списка:

• определить последний узел pp, для которого pp^.next равен nil;
• использовать процедуру AddAfter для добавления узла после узла с адресом pp.

Если список пуст, то алгоритм выполнения изменяется:

procedure AddLast ( var Head: PNode; NewNode: PNode );
var pp: PNode;
begin
  if Head = nil then
    AddFirst ( Head, NewNode ) // добавляем в пустой список
  else begin
    pp := Head;
    while pp^.next <> nil do // поиск последнего узла
      pp := pp^.next;
    AddAfter ( pp, NewNode ); // после узла pp добавляем узел
  end;
end;

Чтобы добавить узел перед заданным:

Для такого случая необходимо знать адрес предыдущего узла, при этом проход назад невозможен.
Поэтому необходимо пройти с начала списка и найти предыдущий узел pp.

procedure AddBefore(var Head: PNode; p, NewNode: PNode);
var pp: PNode;
begin
  pp := Head;
  if p = Head then
    AddFirst ( Head, NewNode )  // добавление в начало списка
  else begin
    while (pp <> nil)  and  (pp^.next <> p) do // поиск узла, за которым следует узел p
      pp := pp^.next;
    if pp <> nil then AddAfter ( pp, NewNode ); // добавляем после узла pp
  end;
end;

Алгоритм выполнения:

Создадим для поиска функцию FindWord, которая принимает слово в качестве параметра, а возвращает адрес узла, который содержит искомое слово либо значение nil, если слово не найдено.

function Find(Head: PNode; NewWord: string): PNode;
var pp: PNode;
begin
  pp := Head;
  // пока не конец списка и слово в просматриваемом узле не равно искомому
  while (pp <> nil) and (NewWord <> pp^.word) do 
    pp := pp^.next;
  Result := pp;
end;

Вставка слова в определенное место списка по алфавиту

Алгоритм выполнения:
Создадим функция для поиска «подходящего» места MakePlace.
На вход функции подается вставляемое слово, возвращает же функция адрес узла, перед которым необходимо добавить слово; возвращается nil, если слово должно быть вставлено в конец списка.

function FindPlace(Head: PNode; NewWord: string): PNode;
var pp: PNode;
begin
  pp := Head;
  while (pp <> nil) and (NewWord > pp^.word) do
    pp := pp^.next;
  Result := pp;
// слово NewWord в алфавитном порядке находится перед pp^.word
end;

Для удаления конкретного узла списка необходимо знать адрес предыдущего узла pp:

Для этого создадим функцию TakeWord().
Будем игнорировать все ненужные символы, код которых <= 32.

function TakeWord ( F: Text ) : string;
var c: char;
begin
  Result := ''; { пустая строка }
  c := ' ';     { пробел – чтобы войти в цикл }  
    { пропускаем спецсимволы и пробелы }
  while not eof(f) and (c <= ' ') do 
    read(F, c);  
    { читаем слово }  
  while not eof(f) and (c > ' ') do begin
    Result := Result + c;
    read(F, c);
  end;
end;

1. Открываем файл в режиме на чтение (var F: Text;)
2. Считывание очередного слова из файла.
3. Если слов больше не осталось (достигнут конец файла), то переходим к шагу номер 7.
4. Слово нашлось — значит, увеличиваем счетчик слов.
5. Если в списке искомого слова не существует, то выполняем:
• создание нового узла с заполнением необходимых полей: функция CreateNode();
• поиск узла, перед которым добавляем слово: функция MakePlace();
• добавление узла: функция AddBefore().
6. Возвращаемся к шагу номер 2.
7. Закрываем рабочий файл.
8. Печатаем на экран список слов: для этого используем алгоритм перемещения по списку.

Двусвязные списки (двунаправленные)

Двусвязный список позволяет двигаться в обоих направлениях.
При работе с двусвязными списками создаются два указателя.

Рассмотрим структуру:

type PNode = ^Node;   { указатель на узел }   
     Node = record    { узел и его структура }
       word: string[40]; { поле для слова }
       count: integer;   { поле - счетчик повторений }
       next: PNode;    { поле - ссылка на следующий узел }
       prev: PNode;    { поле - ссылка на предыдущий узел }         
     end;

«Обнуляем» адреса головы и хвоста:

var Head, Tail: PNode; 
...
Head := nil; 
Tail := nil;