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

На занятии происходит знакомство с понятием динамические структуры данных; будут рассмотрены указатели и списки в паскале

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

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

Указатели

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

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

Присваивание значений

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

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

1

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

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.

Задание 1: Описать целочисленную переменную i. Описать указатель на целочисленную переменную i_ptr. Инициализировать i значением 2. Присвоить i_ptr значение i. Вывести значение, находящееся по адресу i_ptr.

Списки

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

  • содержит поля с полезной информацией;
  • содержит специальное поле (или несколько полей), которое хранит адрес другого элемента списка.
type ukazatel = ^elem_spiska;
elem_spiska = record
  znach:integer;
  next: ukazatel;
 end;
...

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

Пример: В файле расположен текст. Необходимо в другой файл записать все слова из текста в алфавитном порядке и количество повторений для каждого слова (в столбик).

Так как количество слов заранее неизвестно, и определяется оно только в конце программы, то использование статических и динамических массивов невозможно. Необходимо использовать список.

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

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

списки pascal

Объявление:

объявление односвязного списка

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. Установить ссылку нового узла на голову списка:
  2. NewNode^.next := Head;

    добавление узла в начало списка

  3. Обозначить новый узел как голову списка:
  4. Head := NewNode;

    1_11

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

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

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

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

    Добавление узла после заданного

  3. Установить ссылку узла p на новый узел:
  4. p^.next = NewNode;

    4

Перемещение по списку

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

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

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

  • устанавливаем дополнительный указатель 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. Печатаем на экран список слов: для этого используем алгоритм перемещения по списку.

Задание списки 1:
Составить из описанных выше функций программу, реализующую алфавитно-частотный словарь. Вывести на экран количество различных слов, т.е. количество элементов списка.

Задание списки 2:Создать список из десяти элементов и вывести его на экран. Затем вывести только четные элементы списка.

Задание списки 3:Дан односвязный (линейный) список. Найти максимальный и минимальный элементы в списке.

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

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

двусвязные списки

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

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

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

var Head, Tail: PNode; 
...
Head := nil; 
Tail := nil;
Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить