Лекция №10.3: Адреса и указатели. Списочные структуры данных

страницы: 1 2 3 4

Содержание

Структура списков

Итак, каждый элемент создаваемого списка должен содержать:

  1. полезную информацию, которая может иметь любой формат: Integer, Real, array, record и т.п.;
  2. специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.

Приведём примеры различных списочных структур:

  • a) Односвязный (линейный) список: структура, каждый элемент которой «знает» адрес только следующего за ним элемента (см. рис. 10.1 (a)). Очень удобно представлять таким списком стек и очередь (см. лекцию 9).
  • b) Двусвязный линейный список: структура, каждый элемент которой «помнит» адрес не только следующего, но и предыдущего элемента списка (см. рис. 10.1 (b)). Этот список удобен для работы с деками (см. лекцию 9)
  • c) Бинарное дерево (см. лекцию 11) может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков (см. рис. 10.1 (c)). Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трёхсвязным.
  • d) Для представления ориентированного графа (см. лекцию 11) можно использовать иерархические списки — комбинацию из двух различных линейных списков (см. рис. 10.1 (d): вершины задаются структурой, содержащей три поля, а дуги — два; справа показан орграф, представленный приведённой списочной структурой).

Описание списков

Сначала мы рассмотрим только самый простой случай: односвязный список (см. рис. 10.1 (а)). Напомним, что каждый элемент этого списка должен хранить адрес другого элемента из этого же списка.

Примеры списочных структур

Рис. 10.1.  Примеры списочных структур

Логичнее всего было бы дать этой структуре такое описание:

type element_spiska = record
    znachenie : Integer;
    next_element : ^element_spiska;
 end;

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

type ukazatel = ^element_spiska;
  element_spiska = record
    znachenie : Integer;
    next_element : ukazatel;
 end;

Обратите внимание: это единственный случай, когда компилятор согласится принять использование структуры (element_spiska) до её описания.

Замечание: Кажется, что гораздо более естественным было бы отнести поле next_element к типу Pointer: тогда не пришлось бы вводить дополнительный тип данных ukazatel. Однако неудобства, которые непременно возникнут из–за нетипизированности указателей в процессе написания программы, будут гораздо серьёзнее, чем одна лишняя строчка при описании типов.

В качестве примера приведём описания всех четырёх структур, представленных на рис. 10.1 (см. табл. 10.1):

Таблица 10.1. Примеры описаний (списочных структур)

a)Односвязный список
type ukazatel = ^elem_spiska;
  elem_spiska = record
    znach : Integer;
    sled : ukazatel;
 end;
b)Двусвязный линейный список
type point = ^element_spiska;
  list = record
    znachenie : Integer;
    sled : point;
   pred : point;
 end;
с)Бинарное дерево (иерархический список)
type point = ^tree;
  tree = record
    data : Integer;
    left_sibling : point;
    right_sibling: point;
 end;
d)

Ориентированный граф

(двусвязный нелинейный список)

type uk_versh = ^versh;
  uk_duga = ^duga;
  vershina = record
    nomer : Integer;
    sled_versh : uk_versh;
    spisok_dug : uk_duga;
 end;
  duga = record
    konec_dugi : uk_versh;
    sled_duga : uk_duga;
 end;

Оперирование элементами списка

Хранение списка

Для того, чтобы сохранить информацию обо всём списке, достаточно только одной переменной — указателя на первый элемент этого списка. Обычно его называют головой списка. Указатель на голову должен быть выделенным: с ним нельзя производить никаких действий, которые могут стать причиной утери всего списка. Для работы со списком обычно заводят вспомогательный указатель.

Например:

var head, p, q : uk_spisok;

Но, вообще говоря, нет никаких специальных правил, которые обязали бы программиста давать выделенным указателям особые имена. Например, на рис. 10.1 выделенные указатели имеют имена head, tail, tree_root и start.

страницы: 1 2 3 4

Примечания

Код для вставки: :: :: :: ::
Поделиться: // //