Комбинаторные алгоритмы для программистов



             

Поиск и другие операции над таблицами - часть 3


В таком типе организации файлов нашему понятию таблицы соответствует указатель или справочник.

Мы рассматриваем только четыре табличные операции: поиск, включение, исключение и распечатка. Подробное определение того, что должны делать эти операции над таблицей

T = \{ x_1,x_2,\ldots,x_n \}
, зависит от структуры данных, использованной для реализации таблицы.

поиск

z
: если
z \in T
, то отметить его указателем, то есть переменной
i
присвоить такое значение, что
z = x_i
; в противном случае указать, что
z \notin T
;

включение

z
: если
z \notin T
, то поместить его на соответствующее место.

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

z
, и затем помещаем z на это место.

включить

z
на
i
-е место: включить
z
сразу после имени
x_{i -1}
. До включения
T = \{ x_1,\ldots,x_{i - 1},\ldots,x_{i - 1} z,x_i,\ldots,x_n \}
.

исключить

z
: если
z \in T
, то исключить его.

Как и включение, исключение иногда реализуется процедурой поиска для получения места

z
и последующей процедурой:

исключить с

i
-го места: исключить
x_i
из
T
.До исключения
T = \{ x_1,\ldots,x_{i - 1},x_i,x_{i + 1},\ldots,x_n \}
\\ & После исключения
T = \{ x_1,\ldots,x_{i - 1},x_{i + 1},\ldots,x_n \}

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

Последней операцией, которую мы будем рассматривать для каждой табличной структуры, является

распечатка: & напечатать все имена из

T
в их естественном порядке

Среди всех операций, которые можно производить над таблицами, четыре, рассматриваемые в этой лекции (поиск, включение, исключение и распечатка), и сортировка (лекции 14, 15) - наиболее важные.




Содержание  Назад  Вперед