Назва роботи: ВИВЧЕННЯ АТД «СЛОВАРЬ», «Фото» І «навантажені ДЕРЕВО»
Предметна область: Інформатика, кібернетика та програмування
Опис: Часом так само виникає необхідність перевірки присутності елемента в цій множині. Словник можна реалізувати трьома способами: 1посредством відсортованих або не сортований пов'язаних списків; 2прі допомоги довічних векторів якщо елементи даної множини цілі числа; 3іспользуя масив фіксованої довжини з покажчиком на останню заповнену комірку цього масиву якщо розмір множини не перевищує задану довжину масиву в іншому випадку використовуються пов'язані списки. Початкове значення сегмента завжди менше значень елементів його.
Розмір файлу: 341 KB
Роботу скачали: 21 чол.
Лабораторна робота № 5
«ВИВЧЕННЯ АТД« СЛОВАРЬ »,« Фото »І« навантажені ДЕРЕВО »»
Мета роботи: дослідити і вивчити АТД «словник», «файл» і «навантажене дерево».
Завдання роботи: оволодіти навичками складання структур АТД «словник», «файл», «навантажене дерево» і написання програм по дослідженню цих структур на будь-якій мові програмування.
- вивчити опис лабораторної роботи;
- за завданням, даним викладачем, розробити одну з структур: АТД «словник», «файл» або «навантажене дерево»;
- написати програму;
- налагодити програму;
- вирішити завдання;
- оформити звіт.
словник # 150; це абстрактний тип множин. Ці безлічі зберігає поточні об'єкти з періодичної вставкою або видаленням деяких з них. Часом так само виникає необхідність перевірки присутності елемента в цій множині.
Словник можна реалізувати трьома способами:
1) за допомогою відсортованих або не сортований пов'язаних списків;
2) за допомогою двійкових векторів, якщо елементи даної множини цілі числа;
3) використовуючи масив фіксованої довжини з покажчиком на останню заповнену комірку цього масиву, якщо розмір множини не перевищує задану довжину масиву, в іншому випадку використовуються пов'язані списки.
Нижче наведемо приклад для реалізації словника за допомогою не відсортованих зв'язкових списків (рис. 5.1). Має місце масив сегментів. Кожен сегмент має початкове значення і покажчик на перший блок, після якого йдуть інші блоки у вигляді списковому структури. Початкове значення сегмента завжди менше значень елементів його блоків. А у наступного сегмента початкове значення більше початкового значення попереднього сегмента. Періодична вставка і видалення елементів словника в прикладах не наводиться. Їх можна буде розібрати самостійно на основі пройденого раніше матеріалу в попередніх лабораторних роботах.
Тип для даної структури «словника» (рис. 5.1) представимо таким чином:
writeln ( 'Введіть елемент блоку');
if q<> nil then q ^ .next: = p;
Для здійснення пошуку заданого елемента в «словнику» необхідно використовувати оператор Poisk. Принцип пошуку в «словнику», реалізованому за допомогою пов'язаних несортованих списків, нагадує індексного-послідовний пошук в таблиці. Спочатку шукається інтервал, в якому може імовірно перебувати шуканий елемент. У разі «словника» # 150; це сегмент. А потім серед елементів цього інтервалу шукається сам шуканий елемент послідовним перебором елементів. Для «словника» # 150; це список з блоків.
if x_element_of_segment then writeln ( 'Елемент знайдений в одному із сегментів!');
if x_in_segment then
if x_in_blok then writeln ( 'Елемент знайдений в блоці!')
else writeln ( 'У блоці шуканого елемента немає!')
В операторі Poisk так само використовуються:
1) оператор x _ element _ of _ segment. який перевіряє, чи є шуканий елемент початковим значенням сегмента
for j: = 0 to B -1 do
if x = s [j] .element then x_element_of_segment: = True;
2) оператор x _ in _ segment. який визначає сегмент, в якому імовірно міг би перебувати шуканий елемент