38024

ИЗУЧЕНИЕ АТД «СЛОВАРЬ», «ФАЙЛ» И «НАГРУЖЕННОЕ ДЕРЕВО»

Лабораторная работа

Информатика, кибернетика и программирование

Временами так же возникает необходимость проверки присутствия элемента в этом множестве. Словарь можно реализовать тремя способами: 1посредством сортированных или не сортированных связанных списков; 2при помощи двоичных векторов если элементы данного множества целые числа; 3используя массив фиксированной длины с указателем на последнюю заполненную ячейку этого массива если размер множества не превышает заданную длину массива в противном случае используются связанные списки. Начальное значение сегмента всегда меньше значений элементов его...

Русский

2013-09-25

341 KB

21 чел.

13

Лабораторная работа № 5

«ИЗУЧЕНИЕ АТД «СЛОВАРЬ», «ФАЙЛ» И «НАГРУЖЕННОЕ ДЕРЕВО»»

Цель работы: исследовать и изучить АТД «словарь», «файл» и «нагруженное дерево».

Задача работы: овладеть навыками составления структур АТД «словарь», «файл», «нагруженное дерево» и написания программ по исследованию этих структур на любом языке программирования.

Порядок работы:

  1.  изучить описание лабораторной работы;
  2.  по заданию, данному преподавателем, разработать одну из структур: АТД «словарь», «файл» или «нагруженное дерево»;
  3.  написать программу;
  4.  отладить программу;
  5.  решить задачу;
  6.  оформить отчет.

Краткая теория

Словарь

Словарь – это абстрактный тип множеств. Эти множества хранят текущие объекты с периодической вставкой или удалением некоторых из них. Временами так же возникает необходимость проверки присутствия элемента в этом множестве.

Словарь можно реализовать тремя способами:

1)посредством сортированных или не сортированных связанных списков;

2)при помощи двоичных векторов, если элементы данного множества целые числа;

3)используя массив фиксированной длины с указателем на последнюю заполненную ячейку этого массива, если размер множества не превышает заданную длину массива, в противном случае используются связанные списки.

Ниже приведём пример для реализации словаря посредством не сортированных связных списков (рис. 5.1). Имеет место массив сегментов. Каждый сегмент имеет начальное значение и указатель на первый блок, после которого идут другие блоки в виде списковой структуры. Начальное значение сегмента всегда меньше значений элементов его блоков. А у следующего сегмента начальное значение больше начального значения предыдущего сегмента. Периодическая вставка и удаление элементов словаря в примерах не приводится. Их можно будет разобрать самостоятельно на основе пройденного ранее материала в предыдущих лабораторных работах.

Тип для данной структуры «словаря» (рис. 5.1) представим таким образом:

const

B=2;

{Описание типа для блоков "Словаря". По сути, они являются списковой структурой}

type

SPISOK=^pSPISOK;

pSPISOK=record

element:integer;

next:SPISOK;

end;

{Описание типа АТД "Словарь"}

SLOVAR=array[0..B-1] of record

element:integer;

next:SPISOK;

end;

var s:SLOVAR;

a,x:integer;

p,q,g1,g2:SPISOK;

Для формирования «словаря» необходимо использовать:

1) оператор CREAT_TABLE_SEGMENT, который формирует таблицу сегментов словаря

procedure CREAT_TABLE_SEGMENT;

var i:integer;

begin

for i:=0 to B-1 do

begin

writeln('Введите значение ',i,'-го сегмента словаря');

readln(s[i].element);

{первые элементы блоков ещё отсутствуют}

s[i].next:=nil;

end;

end;

2) оператор CREATE_BLOK_B, который осуществляет заполнение m-того блока n элементами

procedure CREATE_BLOK_B(m:integer);

var b:char;

n:integer;

begin

{Если блок будет заполняться, то определяется число вводимых элементов и производится его заполнение}

if INSERT_OR_NOT(m,b,n) then

begin

{Если нет самого первого элемента в m-ом блоке, то он формируется}

if FIRST_OUT(m) then FIRST(m);

{Далее вводятся и остальные n-1 элементы}

INSERT_n(n);

end;

end;

3) оператор CREAT_SLOVAR, который создает новый «словарь»

procedure CREAT_SLOVAR;

var j:integer;

begin

{Создаётся таблица сегментов}

CREAT_TABLE_SEGMENT;

{Заполняются блоки элементами}

for j:=0 to B-1 do

CREATE_BLOK_B(j);

end;

Вместе с оператором CREATE_BLOK_B ещё используются несколько операторов, которые делают код программы более наглядным и универсальным:

1) INSERT_OR_NOT – это оператор, который организует запрос на ввод блоков в m-ый сегмент и определяет количество заносимых блоков за одно обращение к этому сегменту

function INSERT_OR_NOT(m1:integer; var b1:char;

var n1:integer):boolean;

begin

writeln('Вы хотите заполнить блоками сегмент №',m1,'? y/n');

readln(b1);

if b1='y' then

begin

{Элементы будут вводиться в блок}

INSERT_OR_NOT:=True;

writeln('Сколько элементов вы хотите ввести?');

readln(n1);

end

{Блок не будет заполняться}

else INSERT_OR_NOT:=False;

end;

2) FIRST_OUT – это оператор, который проверяет наличие первого блока в сегменте

function FIRST_OUT(m2:integer):boolean;

begin

if s[m2].next=nil

then FIRST_OUT:=True {в блоке нет первого элемента}

else FIRST_OUT:=False; {в блоке есть первый элемент}

end;

3) FIRST – это оператор, который добавляет в сегмент первый блок

procedure FIRST(k:integer);

begin

p:=nil;{Блок ещё пустой}

INSERT;{Добавляем первый элемент}

{Добавляется указатель на первый элемент в поле next m-того сегмента}

s[k].next:=p;

end;

4) INSERT_n – это оператор, который добавляет в сегмент блоки в количестве n-1

procedure INSERT_n(n2:integer);

{n2 – это число вводимых в блок элементов}

var v:integer;{счётчик числа введённых элементов}

begin

{число элементов уже уменьшилось на один из-за добавления в блок первого элемента оператором FIRST(m)}

n2:=n2-1;

v:=0;

while v<>n2 do

begin

v:=v+1;

INSERT;

end;

end;

В двух операторах FIRST и INSERT_n используется ещё один оператор INSERT, который создаёт, заполняет и присоединяет блок, т.е. создаёт списковый элемент.

procedure INSERT;

begin

q:=p;

new(p);

writeln('Введите элемент блока');

readln(p^.element);

{присоединяем, если уже есть первый блок у сегмента}

if q<>nil then q^.next:=p;

p^.next:=nil;

end;

Для осуществления поиска заданного элемента в «словаре» необходимо использовать оператор Poisk. Принцип поиска в «словаре», реализованном посредством связанных несортированных списков, напоминает индексно-последовательный поиск в таблице. Сначала ищется интервал, в котором может предположительно находиться искомый элемент. В случае «словаря» – это сегмент. А потом среди элементов этого интервала ищется сам искомый элемент последовательным перебором элементов. Для «словаря» – это список из блоков.

procedure Poisk;

begin

if x_element_of_segment then writeln('Элемент найден в одном из сегментов!');

if x_in_segment then

if x_in_blok then writeln ('Элемент найден в блоке!')

else writeln('В блоке искомого элемента нет!')

end;

В операторе Poisk так же используются:

1) оператор x_element_of_segment, который проверяет, является ли искомый элемент начальным значением сегмента

function x_element_of_segment:boolean;

var j:integer;

begin

input_element; {вводится элемент для поиска}

{Перед началом поиска считаем, что такого элемента нет}

x_element_of_segment:=False;

for j:=0 to B-1 do

{проверка на наличие искомого элемента в сегменте}

if x=s[j].element then x_element_of_segment:=True;

end;

2) оператор x_in_segment, который определяет сегмент, в котором предположительно мог бы находиться искомый элемент

function x_in_segment:boolean;

var j:integer;

begin

x_in_segment:=False;

{последовательно проверяются значения полей element у всех сегментов "словаря" для нахождения сегмента, в котором предположительно может находиться искомый элемент}

for j:=0 to B-1 do

if x>s[j].element then

begin

x_in_segment:=True;

{Копирует указатель на начало первого блока сегмента, в котором может находиться искомый элемент}

g1:=s[j].next;

end;

end;

3) оператор x_in_blok, который ищет заданный элемент в сегменте среди списка блоков

function x_in_blok:boolean;

begin

{Предварительно считаем, что элемента в блоке нет}

x_in_blok:=False;

repeat

{Искомый элемент сравниваем последовательно с каждым блоком сегмента}

if g1^.element=x then x_in_blok:=True;

g1:=g1^.next;

until g1=nil;

end;

В операторе x_element_of_segment был использован ещё один оператор input_element, который помогает организовать ввод искомого элемента.

procedure input_element;

begin

writeln('------------------------');

write('Введите элемент, который нужно найти в словаре-->');

read(x);

end;

Таким образом, если нам необходимо сформировать словарь и произвести в нём подряд десять раз поиск, то нам необходимо выполнить следующие действия:

begin

CREAT_SLOVAR;

readln;

{осуществим поиск десять раз подряд}

for a:=0 to 9 do Poisk;

readln;

end.

Нагруженное дерево

Нагруженное дерево – это символьное множество и оно имеет такую структуру, которая позволяет использовать его для хранения, поиска, вставки или удаления символьных строк (слов). Каждый узел такого дерева – это префикс из слов множества, т.е. одна буква из слова. Каждый путь от корня к листу соответствует одному слову из множества. Чтобы избежать коллизий слов вводится специальный маркер конца – это символ $, который указывает на окончание любого слова.

Приводим ниже пример такого дерева для слов сад, сан, санки, сок, сокол, сор, сорока (рис. 5.2).

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

Нагруженное дерево можно реализовать двумя способами:

1)через массив указателей на узлы такого же типа;

2)посредством связанных списков.

Самая простая реализация нагруженного дерева – это массив указателей на узлы такого же типа. Узлы дерева – это то же массивы указателей такого же типа. Структура динамическая и может иметь любую степень исхода узла и высоту дерева. Индексами в массиве являются элементы множества {A, B, ..., Z, $} (рис. 5.3).

Запишем тип для данной реализации (рис. 5.2) нагруженного дерева:

type

index={‘A’, ‘B’, ..., ‘Z’, ‘$’}; {Индексы в массиве префиксы}

pTREE=array[index] of ^pTREE;

TREE=^pTREE;

Нагруженное дерево может использоваться так же и для реализации «словаря». В этом случае узлы нагруженного дерева представляются посредством связанных списков (рис. 5.4). Такое представление «словаря» эффективнее, чем его обычная структура, реализованная через связанные списки.

Тип для данной реализации нагруженного дерева (рис. 5.3):

type

SLOVAR=^pSLOVAR;

pSLOVAR=record

prefix: char;

{указатель на первую ячейку списка узла сына}

next1:^SLOVAR;

{указатель на следующую ячейку списка}

next2:^SLOVAR;

end;

Файл

Файл – это последовательность записей, причём каждая запись состоит из одной и той же совокупности полей. Поля могут иметь фиксированную длину – это когда заранее определённо количество байт, или переменную. Файлы с записями фиксированной длины широко используются в системах управления базами данных для хранения данных со сложной структурой. Файлы с записями переменной длины используются для хранения текстовой информации (в Pascal такие файлы не предусмотрены).

Сам «файл» может храниться в виде массива или списка. А различные способы реализации «файла» – это структура быстрого доступа к элементам «файла», т.е. надстройка для удобного поиска среди множества элементов «файла».

Способы доступа к элементам «файла»:

1) через разряженный индекс;

2) через B-дерево.

«Файл», реализованный через разреженный индекс, формируют в отсортированном по значениям ключей порядке (рис. 5.5). При такой организации файл рассматривается как обычный словарь или телефонный справочник, если мы просматриваем лишь заглавные слова или фамилии на каждой странице, т.е. это последовательно расположенные по возрастанию или убыванию данные, хранящиеся в массиве или в списке. Для облегчения поиска можно создать второй файл, который называется разреженным индексом, состоящий из пар (element1, next), где element1 – это значение ключа, а next – это физический адрес блока, в котором значение ключа первой записи равняется element1. Этот разряженный индекс отсортирован по значениям ключей (рис. 5.5).

Можно составить тип для такого способа доступа к «файлу»:

Type

Ffile=^pFile; {тип разреженного индекса}

pFile=record

element: array[0..B-1] of record

element1:integer;

{next1=integer, если данные хранятся в массиве, т.е. в поле будет храниться индекс элемента; next1=SPISOK, если данные хранятся в списке, т.е. в поле будет храниться указатель на элемент}

next:next1;

end;

next2:Ffile; {указатель на следующий элемент разреженного индекса}

end;

Структуры данных, такие как деревья, которые используются для работы с множествами, так же могут быть использованы для представления внешних файлов. Особенно удачно подходит для представления внешней памяти B-дерево. Посредством этого дерева организуются индексы в системах баз данных.

B-дерево – это особый вид сбалансированного m-арного дерева. Оно позволяет выполнять операции поиска, вставки и удаления записей из внешнего файла с заданной производительностью при возможных неблагоприятных условиях.

B-дерево порядка m имеет определённые свойства:

1) корень является листом или имеет двух сыновей; каждый узел, за исключением корня и листьев, имеет от [m/2] до m сыновей;

2) все пути от корня до любого листа имеют одинаковую длину.

B-дерево можно рассматривать как иерархический индекс. Каждый узел в нём занимает блок во внешней памяти (рис. 5.6). Корень B-дерева является индексом первого уровня. Записи основного файла хранятся только в листьях. Каждый лист занимает один блок.

В данной реализации иерархический индекс напоминает бинарный поиск.

Хеширование

Существует два вида хеширования: открытое (внешнее) – это когда множества хранятся в потенциально бесконечном пространстве; и закрытое (внутреннее) – это если используется ограниченное пространство для хранения множеств.

Идея открытого хеширования заключена в следующем. Множество разбивается на конечное число классов. Для B классов, которые пронумерованы от 0 до B-1, строится хеш-функция h(x), принимающая значение из интервала от 0 до B-1, соответствующее классу, которому принадлежит элемент x. Элемент x – это ключ, а h(x) – это хеш-значение x, а классы - сегменты. Организация данных при открытом хешировании имеет вид связных списков. Массив называется таблицей сегментов и проиндексирован номерами сегментов от 0 до B-1 и содержит заголовки для B списков. Реализация словарей посредством открытой хеш-таблицы представлена на рисунке 5.1.

Как видно из рисунка 5.1, таблица сегментов храниться в массиве. Поле element содержит значения, а поле next содержит указатели на следующие элементы сегментов. Другими словами эта конструкция напоминает массив начальных указателей списков, число которых равно числу сегментов.

При закрытом хешировании в таблице сегментов хранятся элементы словаря, а не заголовки списков. В каждом сегменте может храниться только один элемент словаря. При таком хешировании применяется методика повторного хеширования. Сформулируем его принцип. Если возникает попытка поместить элемент x в сегмент с номером h(x), который уже занят другим элементом (коллизия), то выбирается последовательность других номеров сегментов h1(x), h2(x), ..., куда можно поместить элемент x. Местоположения последовательно проверяются, пока не будет найдено свободное. Если свободных мест нет, то таблица уже заполнена, и элемент x вставить нельзя. Структура закрытой хеш-таблицы выполняется с использованием массива большого размера (рис. 5.7), в котором элементы расположены в разнобой. Поиск элемента в хеш-таблице напоминает последовательный поиск среди расположенных в разнобой элементов массива, порядок которых устанавливается полем next. Это поле хранит индекс следующего элемента таблицы.

Метод хеширования широко применяется в реализации словарей.


Задания по вариантам:

Для заданной по варианту структуры (табл. 5.1), которая реализована соответствующим образом (табл. 5.2) выполнить своё задание, которое нужно взять в таблице 5.3.

Таблица 5.1

Выбор структуры для выполнения задания

Вариант

Структура

1, 2, 6, 7, 8, 9, 13, 14, 15, 16, 20, 21, 22, 23, 27, 28, 29, 30, 34, 35, 36, 37, 41, 42, 43, 44, 48, 49, 50

словарь

3, 4, 10, 11, 17, 18, 24, 25, 31, 32, 38, 39, 45, 46

Нагруженное дерево

5, 12, 19, 26, 33, 40, 47

Файл

Таблица 5.2

Выбор способа реализации структуры для выполнения задания

Вариант

Способ реализации

1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46, 50

не отсортированные связанные списки

3, 10, 17, 24, 31, 38, 45

массив указателей на узлы такого же типа

5, 12, 19, 26, 33, 40, 47

разреженный индекс

6, 13, 20, 27, 34, 41, 48

отсортированные связанные списки

7, 14, 21, 28, 35, 42, 49

любой способ из предложенных в теории

Таблица 5.3

Выбор задания, которое нужно выполнить

Вариант

Задание

1, 8, 15, 22, 29, 36, 43, 50

поиск со вставкой элемента

2, 9, 16, 23, 30, 37, 44

поиск с удалением элемента

3, 4, 6, 10, 11, 13, 17, 18, 20, 24, 25, 27, 31, 32, 34, 38, 39, 41, 45, 46, 48

поиск

5, 12, 19, 26, 33, 40, 47

сформировать

7, 14, 21, 28, 35, 42, 49

Осуществить открытое хеширование


 

А также другие работы, которые могут Вас заинтересовать

51463. Строение наружного уха, иннервация, его роль в слуховой функции. Особенности наружного уха у ребенка. Аномалии 15.7 KB
  Ввиду того что функциональное значение ушной раковины невелико, все ее заболевания, а также повреждения и аномалии развития, вплоть до полного отсутствия, не влекут за собой существенного нарушения слуха и имеют в основном лишь косметическое значение.
51464. Устройство и принцип работы трансформатора ТД-500 6.1 MB
  Сварочная дуга как потребитель энергии и источник питания образуют взаимосвязанную энергетическую систему. Дуга представляет собой мощный, длительно существующий электрический разряд, происходящий в атмосфере газов и паров металла между электродом и изделием или между двумя электродами, находящимися под напряжением.
51465. Барабанная полость. Формы, размеры и иннервация, ее содержимое и их роль в слуховой функции. Аномалии 15.4 KB
  Верхняя = передняя стенка пирамиды. Отделяет барабан.пер. от средней черепной ямки, где расположена височная доля мозга. У детей между пирамидой и чешуйчатой костью – щель (воспаление – осложнение отита – менингит).
51467. Средства разработки приложений в Visual Studio.NET 307.06 KB
  Необходимо отметить что процесс написания программ за последние 50 лет прошел путь от программирования в инструкциях процессора программирование в машинных кодах через программирование на низкоуровневых языках ассемблер до программирования на языках высокого уровня.
51468. Создание и выполнение Windowsпроектов с несколькими формами. Стандартные модули и модульная структура приложений в VB 843.34 KB
  Диалоговое окно Добавление нового элемента dd New Item предлагает несколько шаблонов доступных для использования в проектах. Окно Обозреватель решений Solution Explorer в списке компонент проекта содержит модуль который был добавлен в программу.
51469. Объектно-ориентированный подход в программировании. Теоретические основы объектно-ориентированного программирования 435.5 KB
  Теоретические основы объектно-ориентированного программирования Составные части объектного подхода Задачи для самостоятельного решения по теме Теоретические основы объектно-ориентированного программирования Тестовые задания по теме Теоретические основы объектно-ориентированного программирования...
51470. Средства объектно-ориентированного программирования в Visual Basic 187.42 KB
  С классами студенты сталкивались практически во всех предыдущих темах. Объектноориентированное программирование и проектирование построено на классах. Очень важно обратить внимание на то что у класса две различные роли: модуля и типа данных. Вторая роль класса не менее важна.
51471. Отношения между классами. Интерфейсы, делегаты и события 40.52 KB
  Отношения между классами. Понятие отношения между классами. Классы с событиями. Обработчик события: всегда принадлежит классу зажигающему событие; никогда не принадлежит классу зажигающему событие; может принадлежать классу зажигающему событие; принадлежит только одному классу слушающему событие; может принадлежать многим классам слушающим события. Отметьте истинные высказывания: все события имеют одинаковую сигнатуру из двух аргументов с одними и теми же типами; все события имеют сигнатуру из двух аргументов но с...