Очередь-список

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

Очередь, отображаемая линейным односвязным списком, задается двумя указателями: на начало очереди (первый элемент списка) и конец очереди (последний элемент списка). В исходном состоянии очередь пуста и оба указателя имеют пустые (NULL) значения (рис. II–28).

Рис. II–7

При записи в очередь первого элемента изменяются оба указателя, так как первый элемент в данной ситуации становится и последним элементом очереди. Последующие операции записи приводят к изменению только указателя на конец очереди (рис. II–28).

При чтении из очереди изменяется указатель на начало очереди. Когда будет прочитан последний элемент, очередь будет пустой и оба указателя (на начало и на конец очереди) должны иметь пустое значение (рис. II–29).

Рис. II–8

При отображении очереди циклическим односвязным списком достаточно иметь один указатель – на последний элемент очереди (last). Первый элемент очереди (циклического списка) будет определяться ее последним элементом; это означает, что указателем на начало очереди будет являться поле next последнего элемента списка, т.е. last->next.

В исходном состоянии очередь пуста, и указатель на конец очереди имеет пустое значение.

При записи в очередь нового элемента будет изменяться указатель на конец очереди – он будет указывать на записываемый элемент. Так как последний элемент очереди служит указателем на начало очереди, в поле next записываемого элемента должно быть записано значение указателя на начало очереди. При записи элемента в пустую очередь, записываемый элемент является и первым, и последним, поэтому данный элемент будет указывать на себя (рис. II–30).

Рис. II–9

При чтении элемента из очереди удаляется первый элемент, поэтому в последнем элементе очереди, на который указывает last, будет меняться значение поля указателя. Когда из очереди будет прочитан последний элемент (перед выполнением операции чтения в очереди находится только один элемент, который является и первым, и последним), указатель на конец очереди должен получить пустое значение (рис. II–31).

Рис. II–10

8. Таблицы: основные определения, классификация таблиц, способы отображения в памяти.

Таблица состоит из множества элементов, в котором с каждым элементом однозначно связано некоторое имя, или ключ. Вообще говоря, каждый элемент состоит из его ключа и некоторой информации, связанной с эти ключом (рис. II–4).

Рис. II–11

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

Можно указать много операций, определенных над таблицами; ниже приведены некоторые из них:

• добавление элемента,

• доступ к элементу,

• удаление элемента.

9. Просматриваемая таблица – вектор: определение, основные операции, особенности их реализации.

В просматриваемой таблице порядок расположения элементов никак не связан со значениями ключей (рис. II–35). Поэтому поиск элемента по ключу осуществляется обычным просмотром всех элементов таблицы, начиная с первого и до искомого (если он есть в таблице; тогда поиск заканчивается успешно), или до конца таблицы (тогда поиск заканчивается неуспешно).

Ключ	Информация
08	. . .
33	. . .
47	. . .
25	. . .
18	. . .

Рис. II–12

Можно определить длину поиска элемента с ключом k_i, находящегося в i-ой позиции таблицы (например, элемент с ключом 47 находится в позиции 3):

S = i.

Очевидно, что для просматриваемой таблицы дольше всего выполняется поиск последнего элемента таблицы; следовательно, максимальная длина поиска

T = n,

где n – размер таблицы.

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

D = ip_i

где i – порядковый номер записи, а p_i – вероятность того, что требуемая запись имеет номер i.

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

Просматриваемая таблица может быть и статической, и динамической; она может быть отображена в памяти и вектором, и списком. Рассмотрим особенности реализации операций для разных способов отображения просматриваемой таблицы.