- •Информация
- •Свойства информации
- •Преобразования сигнала
- •Системы счисления
- •Перевод из двоичной и шестнадцатеричной систем счисления в десятичную.
- •Перевод из двоичной системы счисления в шестнадцатеричную:
- •Правила вычитания
- •Правила умножения
- •Кодирование сигнала
- •Сложение по модулю
- •Ascii-коды
- •Коды Грея
- •Коды, учитывающие частоту символов
- •Код Штибица
- •Метод Вижинера
- •Метод Шеннона-Фано
- •Метод Хаффмена
- •Декодирование эффективных кодов
- •Методы эффективного кодирования словарей
- •Кодовое расстояние и корректирующая способность кода
- •Обнаружение ошибки
- •Коды, исправляющие ошибки
- •Комбинаторная мера
- •Аддитивная мера
- •Статистический подход к измерению информации
- •Полезность информации
- •Истинность информации
- •Виды современных компьютеров
- •Персональные компьютеры
- •Устройство управления
- •Арифметико-логическое устройство
- •Формы представления вещественных чисел
- •Коды представления числовых данных в алу
- •Сложение вещественных чисел
- •Поскольку старший числовой разряд мантиссы равен 0, она требует нормализации. Для этого:
- •Офисные пакеты
- •Настольные издательские системы
- •Системы автоматизации проектирования (сапр)
- •Инструментарий технологии программирования
- •Первое поколение эвм
- •Второе поколение эвм
- •Третье поколение эвм
- •Четвертое поколение эвм
- •Технология проектирования программ
- •Формализация задачи
- •Структурно-стилизованный способ
- •Операторный язык
- •Команда комментарии
- •Методы проектирования алгоритмов
- •Модуль Ввод и размещение
- •Модуль Ввод и анализ
- •Модуль Упорядочение
- •Модуль Определение
- •Лексический анализ
- •Синтаксический анализ
- •Семантический анализ
- •Генерация промежуточного кода
- •Оптимизация промежуточного кода
- •Компоновка
- •Выполнение и тестирование программы
- •Эволюция использования компьютеров. Проект эвм пятого поколения
- •Структура информационного процесса
- •Сбор информации
- •Первичное восприятие информации
- •Методы классификации
- •Иерархическая классификация
- •Фасетная классификация
- •Распознавание и кодирование объектов
- •Регистрация информации
- •Запись информации оператором
- •Контроль правильности записи данных
- •Первичное восприятие и измерение информации
- •Анализ результатов первичного восприятия и измерения
- •Распознавание символов
- •Восприятие информации клавиатурой
- •Первичное восприятие и измерение
- •Компьютерные сети
- •Топология сетей
- •Методы передачи данных в сетях
- •Организация обмена информацией в сети
- •Обработка информации
- •Хранение информации
- •Операции над данными
- •Линейные списки
- •Блочный способ
- •Двоичный способ
- •Индексно-последовательный способ
- •Индексно-произвольный способ
- •Размещение элементов в упорядоченном списке
- •Исходный список представлен таблицей 11:
- •Рандомизация
- •Фамилия (ключ) Числовое значение ключа
- •3) Формирование реальных номеров бакетов. Для определения константы с выполним следующие вычисления:
- •Метод квадратов. Распределение элементов по бакетам показано в таблице 20:
- •Сдвиг разрядов. Распределение элементов по бакетам показано в таблице 21:
- •Метод складывания. Распределение элементов по бакетам показано в таблице 22:
- •Оптимизированные цепочки элементов
- •Инвертированные списки
- •Иерархические структуры
- •Множественные ссылки на порожденные элементы
- •Ссылки на подобные и порожденные элементы
- •Кольцевые структуры
- •Справочники
- •Битовые отображения
- •Сетевые структуры
- •Множественные ссылки на порожденные элементы
- •Кольцевые структуры
- •Справочники
- •Битовые отображения
- •Жидкокристаллические мониторы
- •Плазменные мониторы
- •Технология вывода изображений на мониторы, использующие элт
- •Принципы организации текстовых видеорежимов
- •Принципы организации графических видеорежимов
- •Манипуляторы курсора
- •Механическая мышь
- •Устройства вывода на бумажный носитель
- •Матричные принтеры
- •Струйная технология
- •Термическая технология
- •Электрографическая технология
- •Технология формирования цвета
Блочный способ
Элементы линейного списка упорядочены по первичному ключу. Для удобства дальнейшего изложения предположим (здесь и далее по линейным спискам), что упорядочение выполнено по возрастанию значения ключа.
Список разделяется на виртуальные блоки размером √N элементов, где N – число элементов в списке. С ключом доступа Кдоступ сравниваются ключевые поля последних элементов в блоках - Кjблока, начиная с первого блока (j – номер блока). С помощью такого сравнения вначале определяется блок, в котором возможно нахождение элемента доступа, а затем уже, как правило, методом последовательного сканирования - сам элемент в блоке.
Рассмотрим вначале, как выполняется задача просмотра.
Пример 3. Пусть линейный список имеет вид таблицы 3. Надо просмотреть адрес студента по фамилии Скворцов, т.е. qпросмотр = (Фамилия = Скворцов, Домашний адрес), где Кдоступ = Скворцов.
Таблица 3
№ п/п |
Фамилия |
Имя |
Отчество |
Номер зачетной книжки |
Домашний адрес |
1 |
Скворцов |
Олег |
Иванович |
02544 |
пр. Мира, 45 - 3 |
2 |
Соколов |
Юрий |
Кузьмич |
01278 |
ул. Леонова, 23 - 98 |
3 |
Строков |
Иван |
Иванович |
02343 |
ул. Красная, 9 - 2 |
4 |
Супруненко |
Виктор |
Егорович |
02347 |
Каштановая аллея, 23 - 5 |
Очевидно, N = 4. Тогда список разбивается на 2 блока размером по 2 элемента (последние элементы блоков имеют номера 2 и 4).
Для решения задачи выполняются следующие шаги:
выбирается последний элемент первого блока;
ключевое поле сравнивается с ключом доступа: Соколов = Скворцов;
поскольку поля не равны, определяется, принадлежит ли искомый элемент текущему – первому – блоку с помощью условия: Соколов > Скворцов;
условие выполняется, поэтому дальнейший поиск ведется в текущем первом блоке;
выбирается предыдущий элемент;
ключевое поле сравнивается с ключом доступа: Скворцов = Скворцов;
ключи равны, поэтому выводится адрес: пр. Мира, 45 – 3; алгоритм заканчивает работу.
Пример 4. Пусть в линейном списке таблицы 3 надо просмотреть адрес студента по фамилии Сидоров, который, как мы видим, в списке не значится, т.е. qпросмотр = (Фамилия = Сидоров, Домашний адрес), где Кдоступ = Сидоров. Задача решается следующим образом:
выбирается последний элемент первого блока;
ключевое поле сравнивается с ключом доступа: Соколов = Сидоров;
поскольку поля не равны, определяется, принадлежит ли искомый элемент текущему – первому – блоку: Соколов > Сидоров;
условие выполняется, поэтому дальнейший поиск ведется в текущем первом блоке;
выбирается предыдущий элемент;
ключевое поле сравнивается с ключом доступа: Скворцов = Сидоров;
поскольку ключи не равны, а список упорядочен, определяется возможность наличия искомого элемента в данном блоке: Скворцов > Сидоров;
условие выполняется, поэтому делается попытка выбрать предыдущий элемент блока. Однако блок просмотрен полностью. Выводится диагностическое сообщение об отсутствии искомого элемента в данном списке; алгоритм заканчивает работу.
Задача добавления нового элемента решается аналогично способу, рассмотренному ранее для упорядоченного списка.
