Федеральне Агентство з освіти РФ
Рязанський радіотехнічний університет
Кафедра «АІТП»
Практична робота
з дисципліни «Програмування та основи алгоритмізації»
Виконали: Рогачик А. Е., Попов Б.С.
Перевірила: Кузьміна О.М
1. Опис процедури вибору структури зберігання даних
Для програмної реалізації завдання №12 ми вибрали лінійну структуру даних фіксованого розміру - одновимірний неоднорідний масив. (вектор)
Кожен елемент масиву - це запис, що складається з полів. При зверненні до елементу вектора в програмі задається значення його індексу i.
=record//Еталон для масиву записів
Number: integer;// номер заліковки
Surename: string [10];// прізвище
NameGroup: string [10];// номер групи
Максимальне число записів в списку 100 - це означає, в пам'яті ЕОМ може зберігатися інформація про 100 студентах.
. Опис структури двійкового дерева
Бінарне дерево можна представити у вигляді динамічної структури даних, що складається з вузлів, кожен з яких містить крім даних не більше двох посилань на праве і ліве бінарне дерево.
На кожен вузол є одне посилання. Початковий вузол називається коренем.
За аналогією з елементами списків, вузли дерева зручно представити у вигляді записів, що зберігають інформацію і два покажчика:
T=Integer; {Це буде номером заліковки}=^ TNode;// покажчик на запис
TNode=record//сама запис
value: T;// значення запису
Left, Right: TTree;// ліві і праві гілки (для дерева)
Тут поля Left, Right (ліві і праві гілки) будуть містити покажчики для наступних полів.
Зобразимо схематично приклад дерева, організованого у вигляді динамічної структури даних:
Дане дерево організовано таким чином, що для кожного вузла всі ключі (значення вузлів) його лівого піддерева менше ключа цього вузла, а всі ключі його правого піддерева більше. Такий спосіб побудови дерева називається деревом пошуку або двійковим впорядкованим деревом.
За допомогою дерева пошуку можна організувати ефективний спосіб пошуку, який значно ефективніше пошуку за списком.
Пошук у впорядкованому дереві виконується за наступним рекурсивному алгоритмом:
· Якщо дерево не порожньо, то потрібно порівняти шуканий ключ з ключем в корені дерева:
якщо ключі збігаються, пошук завершено;
якщо ключ в корені більше шуканого, виконати пошук в лівому поддереве;
якщо ключ в корені менше шуканого, виконати пошук у правому поддереве.
· Якщо дерево порожньо, то шуканий елемент не знайдений.
Словесний опис роботи програми.
Нами був реалізований список студентів, записи якого складаються з наступних полів: номер заліковки, прізвище, і номер групи. Ці дані зчитуються в оперативну пам'ять із зовнішнього файлу (base.txt) при кожному запуску на початку роботи програми. Ці дії виконуються у процедурі ініціалізації, яка так само підраховує кількість записів про студентів.
Далі, проходячи по всіх записах, програма будує двійкове дерево по ключовому полю - номеру заліковки.
Програма включає в себе функції пошуку записи в базі на прізвище, або за номером заліковки, додавання нових записів в базу даних, і пошук елементів у дереві.
Пошук за списком організований шляхом порівняння заданого значення (Прізвища або номера заліковки) з відповідними полями запису при проходженні записи від першого до останнього елементів.
програмний бінарний дерево масив
3. Зміст бази даних (зовнішній файл)
иванов 334
попів 3372
Рогачик 337
орлів 112
. Блок-схеми алгоритмів і тексти програм
Program Kursach; crt;
SimplyRecord=record//Еталон для масиву записів
Number: integer;// номер заліковки
Surename: string [10];// прізвище
NameGroup: str...
