Системное программное обеспечение Таблицы идентификаторов

Содержание

Слайд 2

Любая таблица идентификаторов состоит
из набора полей, количество которых равно числу различных

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

Слайд 3

Логарифмический поиск

Искомый символ сравнивается с элементом в середине таблицы ( (N +

Логарифмический поиск Искомый символ сравнивается с элементом в середине таблицы ( (N
1)/2).
Если этот элемент не является искомым, то просматривается только блок элементов, пронумерованных от 1 до (N + 1)/2 - 1, или блок элементов от (N + 1)/2 + 1 до N в зависимости от того, меньше или больше искомый элемент по сравнению с ранее найденным.
Так продолжается до тех пор, пока либо искомый элемент не будет найден, либо алгоритм дойдет до очередного блока, содержащего один или два элемента (с которыми можно выполнить прямое сравнение искомого элемента).

Слайд 4

Алгоритм бинарного дерева

Первый идентификатор поместить в вершину дерева.
Шаг 1. Выбрать очередной

Алгоритм бинарного дерева Первый идентификатор поместить в вершину дерева. Шаг 1. Выбрать
идентификатор из входного потока данных. Если его нет, построение дерева закончено.
Шаг 2. Сделать текущим узлом дерева корневую вершину.
Шаг 3. Сравнить очередной идентификатор с тем, что содержится в текущем узле дерева.
Шаг 4. Если очередной идентификатор меньше, то перейти к шагу 5, если равен – сообщить об ошибке и прекратить выполнение алгоритма, иначе – перейти к шагу 7.

Слайд 5

Шаг 5. Если у текущего узла существует левая вершина, то сделать ее

Шаг 5. Если у текущего узла существует левая вершина, то сделать ее
текущим узлом и вернуться к шагу 3, иначе перейти к шагу 6.
Шаг 6. Создать новую вершину, поместить в нее очередной идентификатор, сделать эту новую вершину левой вершиной текущего узла, вернуться к шагу 1.
Шаг 7. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе перейти к шагу 8.
Шаг 8. Создать новую вершину, поместить в нее очередной идентификатор, сде­лать эту новую вершину правой вершиной текущего узла и вернуться к шагу 1.

Слайд 6

Пример Gа, D1, M22, Е, А12, ВС, F

Пример Gа, D1, M22, Е, А12, ВС, F

Слайд 8

Поиск нужного элемента в дереве

Шаг 1. Сделать текущим узлом дерева корневую вершину.
Шаг

Поиск нужного элемента в дереве Шаг 1. Сделать текущим узлом дерева корневую
2. Сравнить искомый идентификатор с идентификатором, содержащимся в текущем узле дерева.
Шаг 3. Если идентификаторы совпадают, то искомый идентификатор найден, алгоритм завершен, иначе перейти к шагу 4.

Слайд 9

Шаг 4. Если очередной идентификатор меньше, то перейти к шагу 5, иначе

Шаг 4. Если очередной идентификатор меньше, то перейти к шагу 5, иначе
– к шагу 6.
Шаг 5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм завершен.
Шаг 6. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе искомый идентификатор не найден, алгоритм завершен.

Слайд 10

Хэш-функция

Хэш-функцией F называется некоторое отображение множества входных элементов R на множество целых

Хэш-функция Хэш-функцией F называется некоторое отображение множества входных элементов R на множество
неотрицательных чисел
Хэш-адресация заключается в использовании значения, возвращаемого хэш-функцией, в качестве адреса ячейки из некоторого массива данных.
Тогда размер массива данных должен соответствовать области значений используемой хэш-функции.

Слайд 11

Метод рехэширования

Шаг 1. Вычислить значение хэш-функции n = h(A) для нового

Метод рехэширования Шаг 1. Вычислить значение хэш-функции n = h(A) для нового
элемента А.
Шаг 2. Если ячейка по адресу n пустая, то поместить в нее элемент А и завер­шить алгоритм, иначе i= 1 и перейти к шагу 3.
Шаг 3. Вычислить ni = hi (A). Если ячейка по адресу ni пустая, то поместить в нее элемент А и завершить алгоритм, иначе перейти к шагу 4.
Шаг 4. Если n = ni то сообщить об ошибке и завершить алгоритм, иначе i = i + 1 и вернуться к шагу 3.

Слайд 12

Поиск элемента в таблице идентификаторов

Шаг 1. Вычислить значение хэш-функции n =

Поиск элемента в таблице идентификаторов Шаг 1. Вычислить значение хэш-функции n =
h(A) для искомого элемента А.
Шаг 2. Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе сравнить имя элемента в ячейке n с именем искомого элемента А. Если они совпадают, элемент найден и алгоритм завершен, иначе i= 1, перейти к шагу 3.
Шаг 3. Вычислить ni = hi(A). Если ячейка по адресу ni пустая или n = ni то элемент не найден и алгоритм завершен, иначе сравнить имя элемента в ячейке ni с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i = i + 1 и повторить шаг 3.

Слайд 13

Метод цепочек

Шаг 1. Во все ячейки хэш-таблицы поместить пустое значение, таблица идентификаторов

Метод цепочек Шаг 1. Во все ячейки хэш-таблицы поместить пустое значение, таблица
пуста, переменная FreePtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов; i = 1.
Шаг 2. Вычислить значение хэш-функции ni для нового элемента Аi. Если ячейка хэш-таблицы по адресу ni пуста, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе перейти к шагу 3.
Шаг 3. Положить j=1, выбрать из хэш-таблицы адрес ячейки таблицы идентификаторов mj и перейти к шагу 4.

Слайд 14

Шаг 4. Для ячейки таблицы идентификаторов по адресу mj проверить значение поля

Шаг 4. Для ячейки таблицы идентификаторов по адресу mj проверить значение поля
ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе j= j + 1, выбрать из поля ссылки адрес mj и повторить шаг 4.
Шаг 5. Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента Аi (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе i = i + 1 и перейти к шагу 2.
Имя файла: Системное-программное-обеспечение-Таблицы-идентификаторов.pptx
Количество просмотров: 32
Количество скачиваний: 0