Связный список
Cтраница 4
 |
Запись в мультисвязном файле. [46] |
Предположим, что атрибут может принимать ряд различных значений. Каждому значению атрибута соответствует один связный список. На рис. 12.6.1 при построении мультисвязной структуры используются три атрибута: пол, доход и географическое положение. [47]
Поискана больше или равн о. Если требуется добавить запись в упорядоченный связный список, то, используя ключ новой: записи, ищем первую запись, ключ которой больше ключа записи, подлежащей вводу. Применим в данном случае оператор бр-поиск. [48]
Головные ячейки, или указатели на связный список, объединяются в набор, причем размер каждой головной ячейки достаточно мал, так как он ограничивается размером указателя на ячейку, содержащую первую запись подфайла. Теперь для пустого подфайла пустой является только головная ячейка и теряется сравнительно небольшой объем памяти, например одно слово. Фактически это даже не считается потерей, так как должны же мы располагать средствами, указывающими, что подфайл пустой. [49]
 |
Алгоритм замещения страниц часы. [50] |
Хотя алгоритм LRU теоретически реализуем, он не является дешевым. Для полного осуществления алгоритма LRU необходимо поддерживать связный список всех содержащихся в памяти страниц, где последняя использовавшаяся страница находится в начале списка, а та, к которой дольше всего не было обращений, - в конце. Сложность заключается в том, что список должен обновляться при каждом обращении к памяти. [51]
При большом количестве файлов быстродействие снижается. ПОСКОЛЬКУ в системе FAT для поддержания файловой структуры используется связный список. При увеличении объема данных в файле, он может стать фрагментированным. [52]
Программа 3.10 служит реализацией простой задачи обработки списка, состоящей в изменении на обратный порядка следования узлов. Она принимает связный список в качестве аргумента и возвращает связный список, состоящий из тех же узлов, но расположенных в обратном порядке. На рис. 3.7 показано изменение, выполняемое функцией в своем главном цикле для каждого узла. Эта диаграмма упрощает проверку каждого оператора программы на правильность изменения ссылок. Программисты обычно используют подобные диаграммы для осмысления операций обработки списков. [53]
Рассмотренные в разделе 14.1 хеш-функции преобразуют ключи в адреса таблицы; второй компонент алгоритма хеширования - определения способа обработки случая, когда два ключа представляются одним и тем же адресом. Самый прямой метод - построить для каждого адреса таблицы связный список элементов, ключи которых отображаются на этот адрес. Данный подход ведет непосредственно к обобщению метода элементарного поиска в списке ( см. главу 12) из программы 14.3. Вместо поддержки единственного списка поддерживаются М списков. [54]
Две поставленные задачи решаются с помощью процедуры ZEROAP. На вход процедуры поступают массивы, в которых хранится верхний связный список матрицы, а также массив LINZER ( NLIN), в который должны быть помещены номера удаляемых строк и столбцов. [55]
Страницы: 1 2 3 4