Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структури даних та алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2004
Тип роботи:
Курсова робота
Предмет:
Програмування
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
НУ „Львівська політехніка”
Кафедра EOM
Курсова робота
„Структури даних та алгоритми”
з дисципліни
Програмування
Анотація
У курсовій роботі досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних.
Розглядається один з багатьох методів сортування. Досліджується основні переваги і недоліки цього методу перед простими методами (вибору, вставки, обміну).
Будується більш складніша задача на основі складних структур даних, а саме стеків, черг, списків, дерев, графів. Розглядаються алгоритми побудови тих чи інших задач, а також методи їх розв’язку. Одним з голових деталей сучасного програмування є використання динамічних структур даних, які дають змогу доцільніше побудувати задачу і знайти її розв’язок.
Зміст
Вступ 4
Завдання на курсову роботу 6
1. Теоретична частина. 7
1.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера. 7
1.1.1. Логічні типи 7
1.1.2. Цілі типи. 7
1.1.3. Дійсні типи. 8
1.1.4. Символьний тип. 10
1.1.5. Рядковий тип. 10
1.1.6. Перелічуваний тип 11
1.1.7. Діапазонний тип 11
1.1.8. Тип масив 11
1.1.9. Тип запис 12
1.1.10. Файловий тип 12
1.2. Задача на сортування. Сортування методом обміну (метод бульбашки). 13
1.3. Задача на створення структури даних „збалансоване дерево” 13
2. Використані алгоритми. 16
2.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера. 16
2.2. Задача на сортування. Сортування методом обміну (метод бульбашки). 19
2.3. Реалізація структури даних збалансоване дерево. 20
3. Тестування. 22
3.1. Дослідження внутрішнього представлення типів даних типів даних. 22
3.1.1. Логічні типи 22
3.1.2. Цілі типи 23
3.1.3. Дійсні типи. 24
3.1.4. Символьний тип 29
3.1.5. Рядковий тип 29
3.1.6. Перелічуваний тип 30
3.1.7. Тип масив 30
3.1.8. Тип запис 31
3.1.9. Файловий тип 32
3.2. Задача на сортування методом обміну. 32
3.3. Структура даних „збалансоване дерево”. 33
Висновки 35
Список літератури 36
Додатки 37
Вступ
Комп’ютер — це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана. Тому, для вивчення дисципліни студенту особливо важливо зрозуміти концепцію організації даних і роботи з ними.
Програма представляє собою в кінцевому рахунку конкретні формулювання абстрактних алгоритмів, що базуються на конкретних представленнях і структурах даних. Зрозуміло, що рішення про структури даних які необхідно застосувати неможливо прийняти без знання алгоритмів, що застосовуються до цих даних, і навпаки, вибір алгоритмів суттєво залежить від вибраних структур даних. Отже, структури програм і структури даних нерозривно пов’язані.
В курсовій роботі спочатку розглядаються фундаментальні структури які складаються з простих даних. Вони представляють собою компоненти, з яких складаються більш складні структури. Змінні фундаментальної структури можуть змінювати тільки своє значення, зберігаючи незмінною свою форму. Таким чином, розмір пам’яті яку вони займають залишається постійним. Навпаки, ускладнені структури характеризуються зміною не тільки значення, але й форми під час виконання програми. Тому для їх реалізації необхідно застосовувати більш складні прийоми. Послідовний файл займає проміжне значення, оскільки хоча його довжина й змінюється, але ця зміна форми є тривіальною. Оскільки послідовний файл грає важливу роль практично у всіх обчислювальних системах, він буде розглядатись разом з фундаментальними структурами.
В першому завданні курсової роботи досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних.
В другому завданні будується один з методів сортування або пошуку. Досліджуються основні характеристики цього метода і проводиться порівняння ефективностей даного метода і класичних методів. Алгоритмам сортування і пошуку приділяється стільки уваги у зв’язку з тим, що за їх допомогою можна проілюструвати багато принципів програмування і ситуацій, що виникають і в інших задачах.
В третьому завданні будується одна з більш складних динамічних структур даних (стеки, черги, списки, дерева, графи), розробляються алгоритми і програмні реалізації роботи з нею і за їх допомогою розв’язується прикладна задача.
Велике значення в курсовій роботі приділяється методиці розробки програмних продуктів і стилю програмування.
Метою курсової роботи є:
систематизувати, закріпити і розширити теоретичні і практичні знання з програмування, навчитися застосовувати різноманітні структури даних та алгоритми при розв'язанні конкретних прикладних задач;
отримати навики розробки більш складних програмних продуктів і оформлення програмної документації.
Завдання на курсову роботу
Дослідити, як в пам’яті комп’ютера представляються змінні цілих, логічних, дійсних, символьного, рядкового, обмеженого, перелічувального типів, а також змінні типу масив, запис та файлові змінні.
Реалізувати метод сортування обміном.
Реалізувати структуру „збалансоване дерево” і набір основних операцій для роботи з ним. Теоретична частина.
Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера.
Логічні типи
У середовищі програмування TurboPascal логічні типи представлені такими типами як Boolean, ByteBool, WordBool, LongBool. Значення, яких можуть набувати змінні
логічного типу, позначаються вбудованими ідентифікаторами констант False і True.
У внутрішньому представленні змінні логічного типу мають певну надлишковість. У таблиці 1 наведено характеристики внутрішнього представлення логічних типів.
Таблиця 1. Вбудовані логічні типи даних
Ідентифікатор
Значенню FALSE відповідає
Значенню TRUE відповідає
Розмір пам’яті
Boolean
0
Довільне число відмінне від 0
1
ByteBool
0
1
WordBool
0 в 2-х байтах
2
LongBool
0 в 4-х байтах
4
Як видно з таблиці 1, якщо значення логічної змінної дорівнює TRUE, то в пам’яті зберігається довільне число відмінне від нуля, якщо ж логічна змінна набула значення FALSE, то у кожному байті, відведеному під зберігання змінної, записане значення 0.
Цілі типи.
Середовище Turbo Pascal містить п’ять вбудованих цілочисельних типів:
Shortint
Integer
Longint
Byte
Word
Кожен з вище наведених типів має свою множину значень, які може набувати змінна даного типу. Ця множина залежить від внутрішнього представлення одного з цілих типів, тобто від кількості байт, що відводиться для зберігання змінних того чи іншого типів. У таблиці 2 подано розмір та діапазон представлення чисел цілих типів.
Всі без винятку числа цілих типів в пам’яті комп’ютера зберігаються побайтно у зворотному порядку. Додатні числа зберігаються у прямому, а від’ємні ( у доповняльному коді.
Інформацію про знак числа містить перший біт. Перший біт додатного числа дорівнює 0, а від’ємного — 1. Нуль завжди має знак "+", тобто перший біт нульового числа дорівнює 0.
Таблиця 2. Вбудовані цілочисельні типи
Назва
Ідентифікатор
Діапазон
Розмір
Коротке ціле зі знаком
ShortInt
-128 … 127
1 байт
Ціле зі знаком
Integer
-32768 … 32767
2 байти
Довге ціле зі знаком
LongInt
-2147483648 … 2147483647
4 байти
Коротке ціле без знаку
Byte
0 … 255
1 байт
Ціле без знаку
Word
0 … 65535
2 байти
Дійсні типи.
У мові програмування Turbo Pascal є п’ять вбудованих дійсних типів: Real, Single, Double, Extended і Comp. Дійсні типи відрізняються діапазоном представлення чисел, розміром пам’яті, а також точністю значень змінних цих типів. У таблиці 3 подано розмір та діапазон представлення чисел дійсних типів:
Таблиця 3. Вбудовані дійсні типи даних
Назва
Ідентифікатор
Діапазон
Розмір
Дійсне одинарної точності
Single
4 байти
Дійсний
Real
6 байт
Дійсний подвійної точності
Double
8 байт
Дійсне підвищеної точності
Extended
10 байт
Ціле в формі дійсного
Comp
8 байт
Зберігаються дійсні числа у зворотному порядку розміщення байтів.
Кожний з дійсних типів має власний внутрішній формат представлення. Нижче розглянуто внутрішній формат кожного з дійсних типів.
Тип Single
s
E
1 біт
8 біт
23 біта
За умовний нуль приймається значення .
У даній і наведених нижче схемах внутрішнього представлення дійсних чисел введено такі позначення: — знак числа (+ або -); — мантиса; — експонента.
Тип Real
s
E
1 біт
39 біт
8 біт
За умовний нуль приймається значення .
Тип Double
s
E
1 біт
11 біт
52 біта
За умовний нуль приймається значення .
Тип Extended
S
E
I
1 біт
15 біт
1 біт
63 біта
За умовний нуль приймається значення .
Поле „i” дорівнює нулю, якщо число є близьке до нуля, в протилежному випадку — 1
Тип Comp
S
1 біт
63 біта
Число, представлене у даному форматі , де - двійкове доповнення 63 бітного значення (тобто число зберігається у доповняльному коді).
Символьний тип.
Ідентифікатором символьного типу на мові програмування Pascal є ідентифікатор char. Значення даного типу ( множина символів таблиці ASCII. Кожному символу відповідає ціле число у діапазоні 0..255.
У пам’яті комп’ютера займають 1 беззнаковий байт. В цей байт записується ASCII-код символу.
Рядковий тип.
Значенням рядкового типу є послідовність символів з динамічним атрибутом довжини (в залежності від дійсної кількості символів при виконанні програми) і константним атрибутом розміру в діапазоні від 1 до 255.
Довжина рядкового типу дорівнює: максимальна довжина рядка +1 байт. Перший байт завжди містить біжучу довжину рядка, а наступні байти - символи рядка. Максимальна кількість символів у рядку - 255. Схематично рядковий тип можна зобразити так:
D
s1
S2
s3
...
sn
де - d - біжуча довжина рядка; - ASCII-коди символів, що входять у рядок.
Перелічуваний тип
Якщо описана змінна перелічуваного типу, то в пам’яті комп’ютера під неї виділяється стільки байт пам’яті, скільки відводиться на відповідне ціле число, яке дорівнює кількості елементів у списку перелічуваного типу. Так, якщо елементів у списку до 256 - то відводиться 1 байт пам’яті; якщо більше 256, але менше 65356 - відводиться 2 байти і т.д.
Значенню змінної в пам’яті відповідає порядковий номер його (починаючи з нуля) у списку ідентифікаторів, що заданий при об’явленні типу.
Діапазонний тип
Діапазонний тип уявляє собою інтервал значень деякого порядкового типу, який називається базовим. При описі діапазонного типу вказується найменше і найбільше значення, розділені "..".
В пам’яті виділяється стільки байт, скільки відводиться під типи даних, що відповідають найменшому і найбільшому значенню діапазону і в них записується значення змінної.
Тип масив
Масив - це однорідна складена структура даних статичної структури. Кожен компонент масиву характеризується своїм індексом. Допустимими типами індексів є всі порядкові типи, за винятком Longint та піддіапазонів цього ж типу. Для доступу до елементів масиву необхідно вказати ідентифікатор масиву з одним чи кількома індексами в дужках.
Розглянемо зберігання масивів у пам’яті комп’ютера. Він зберігається як неперервна послідовність змінних того типу, якого оголошені елементи масиву.
Розмір пам’яті, що відводиться для зберігання масиву, обчислюється за формулою:
Взагалі, масив в пам’яті - це набір послідовних байт, причому адреса -го елементу масиву визначається за формулою: ,
де - адреса першого елементу масиву; - кількість байт, яку займає один елемент масиву.
Елементи масиву з найменшим індексом зберігаються по найменшій адресі пам’яті. Багатовимірні масиви зберігаються так, що найбільш правий індекс збільшується першим.
Тип запис
Запис - це неоднорідна структура даних, яка складається з фіксованого числа компонентів, що називаються полями запису. На відміну від масиву, поля запису можуть бути різного типу.
Розглянемо збереження записів у пам’яті комп’ютера. Компоненти запису у пам’яті комп’ютера зберігаються як неперервна послідовність змінних тих типів, яких об’явлені компоненти запису. Всі компоненти запису зберігаються у послідовності їх описання. Перше поле зберігається по найменшій адресі. Якщо запис містить варіантні частини, то кожна варіантна частина починається з однієї і тієї ж адреси.
Файловий тип
Поняття файл в Паскалі використовується для об’єктів, які складаються з послідовних компонентів одного і того ж типу (у цьому файли подібні на масиви). Але, у випадку файлів, дані зберігаються у зовнішній (вторинній) пам’яті та у іншому периферійному обладнанні.
До компонентів файла існує послідовний доступ, тобто в будь-який момент доступний лише один компонент. Інші компоненти стають доступними по мірі просування по файлу. Число компонентів, які називають довжиною файлу, не фіксується. Цим файли суттєво відрізняються від масивів.
Опис кожної змінної-файла f автоматично вводить буферну змінну f↑ – буфер файла. Цю змінну можна розглядати як деяке вікно, через яке можна переглядати (читати) існуючі компоненти чи додавати (записувати) нові. Вікно автоматично пересувається при деяких операціях над файлами.
Якщо вікно f↑ дійде до кінця файла f, то стандартна функція eof(f)(end of file) видасть значення true, в усіх інших випадках - false.
Файли, компонентами яких є символи, називаються текстовими. Стандартний тип text приблизно відповідає file of char. Проте текст у текстових файлах розбивається на рядки. Отже, можна вважати, що тип text основується на базовому типі char, який містить лише друковані символи, які доповнені символом розділенні рядків.
Задача на сортування. Сортування методом обміну (метод бульбашки).
Сортуванням називається упорядкування послідовності елементів за певним параметром (ключем) за зростанням чи за спаданням. Метод названий методом обміну тому, що елементи просто міняються місцями поки послідовність не буде відсортованою.
Задача на створення структури даних „збалансоване дерево”
Дерево — це структура даних, скінченна множина Т, яка складається з одного або більше вузлів, таких, що
а) Існує один спеціально визначений вузол, який називається коренем даного дерева.
б) Решта вузлів (за виключенням кореня) містяться в m ≥ 0 множинах Т1,……Тm, що попарно не перетинаються, кожна з яких у свою чергу є деревом. Дерева Т1,……Тm називаються піддеревами даного дерева.
Звідси випливає, що кожен вузол дерева є коренем деякого піддерева, яке міститься в цьому дереві. Кількість піддерев даного вузла називається степенем цього вузла. Вузол з нульовим степенем називають кінцевим вузлом. Інколи його ще називають листком. Рівень вузла відносно дерева Т визначається наступним чином: корінь має рівень 1, а всі інші вузли мають рівень на 1 більший їх рівня відносно піддерева Тj, в якому воно міститься, цього кореня. Приклад дерева наведено на рис. 1.
Рис. 1. Дерево.
Бінарне дерево — це таке дерево, в якому кожен вузол може мати максимум два піддерева (оскільки їх тільки два, то вони називаються лівим сином і правим сином, корінь ще називають батьком). Приклад бінарного дерева показаний на рис. 2.
Рис. 2. Бінарне дерево.
Бінарне дерево називається збалансованим, якщо висота лівого піддерева будь-якого вузла відрізняється не більше ніж на ±1 від висоти правого піддерева.
Висотою дерева називається його максимальний рівень, довжина найдовшого шляху від кореня до зовнішнього вузла.
На рис. 3 зображене збалансоване дерево висотою 15 з 17 внутрішніми вузлами; фактор збалансованості позначений всередині кожного вузла знаками „+”, „ · ” та „—” у відповідності з різницею висот правого та лівого піддерев (+1, 0 або -1).
Рис. 3. Збалансоване бінарне дерево.
Використані алгоритми.
Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера.
Під кожен тип даних в оперативній пам’яті комп’ютера виділяється певна кількість байтів, у які записуються дані того чи іншого типу, представлені у двійковій системі числення.
Алгоритм полягає у тому, що на цю виділену пам’ять накладається масив байт. Кількість байтів виділеної оперативної пам’яті і масиву залежить від типу, що розглядається.
На рис. 4, рис. 5 та рис. 6 зображені блок-схеми процедур переведення у двійкову систему числення і навпаки даних типів SHORTINT, REAL та CHAR відповідно.
Рис. 4. Перевід у двійкову систему числення і навпаки (Shotrint).
Рис. 5. Блок-схема процедури до типу Real
Рис. 6. Вивід двійкового представлення даних типу Char.
Задача на сортування. Сортування методом обміну (метод бульбашки).
N-чисел, які потрібно відсортувати, аналізуються. Сортування проводиться за n-1 кроків. Після проходження зовнішнього циклу найбільший елемент послідовності стає на своє місце (якщо по зростанню, то в кінець послідовності). Після цього послідовність розбивається на вихідну та готову. Далі проводиться сортування вихідної послідовності, найбільший елемент якої знову (ніби „бульбашкою”) випливає у кінець послідовності (від цього і назва — сортування методом бульбашки). У внутрішньому циклі елементи вихідної послідовності порівнюються між собою: якщо елемент більший за наступний, то вони міняються місцями.
Рис. 7. Процедура сортування методом бульбашки.
Реалізація структури даних збалансоване дерево.
Розставимо баланси для кожного вузла наступного дерева.
Рис. 8. Дерево з розставленими балансами для кожного вузла.
При вставці елемента в таке дерево в найгіршому випадку, коли висота лівого піддерева більша за висоту правого критерій збалансованості порушується і дерево потрібно трансформувати, щоб відновити критерій збалансованості. Така трансформація називається поворотом.
Поворот мусить задовольняти наступні вимоги:
проходження трансформованого дерева в симетричному порядку повинно бути таким самим, як і попереднього.
нове дерево повинно залишатися збалансованим.
Рис. 9. Лівий та правий повороти дерева.
Одинарний поворот направо відбувається тоді, коли батьківський вузол і його лівий син починають переважувати вліво внаслідок вставки елемента у дерево. В результаті такого повороту лівий син замінює свого батька, який стає його правим сином.
Подвійний поворот вправо відбувається тоді, коли батьківський вузол переважує вліво, а його лівий син переважує вправо.
Процес включення вузла в дерево складається з трьох етапів:
Йти за шляхом пошуку, поки не виявиться, що ключа немає в дереві.
Включити новий вузол і визначити новий показник збалансованості.
Пройтися назад за шляхом пошуку і перевірити показник збалансованості для кожного вузла.
Тестування.
Дослідження внутрішнього представлення типів даних типів даних.
Логічні типи
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу boolean b1 = true.
Оскільки даний тип займає у пам’яті 1 байт, то змінна b1 представляється наступним чином:
0000 00012
1 байт
ОР
01
РВП
01
ППК
0000 0001
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу wordbool b2 = succ(b1).
Змінні даного типу займають у пам’яті 2 байти. Знайдемо вмістиме пам’яті. Функція succ(b1) додає до значення b1 число 12.
0000 0001
+ 0000 0001
0000 0010
Змінна b2 набуде значення TRUE.
Змінна b2 представляється наступним чином:
0000 0010 0000 00002
1 байт
2 байт
ОР
02
00
РВП
02
00
ППК
0000 0010
0000 0000
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу longbool b3 = pred(pred(b1)).
Змінні даного типу займають у пам’яті 4 байти. Знайдемо вмістиме пам’яті враховуючи, що функція pred(b1) зменшує значення b1 на 12.
0000 0000 0000 0000 0000 0000 0000 0001
+1111 1111 1111 1111 1111 1111 1111 1110
1111 1111 1111 1111 1111 1111 1111 1111
Змінна b3 набуде значення true.
Змінна b3 представляється наступним чином:
1111 1111 1111 1111 1111 1111 1111 11112 (= FFFFFFFF16)
1 байт
2 байт
3 байт
4 байт
ОР
FF
FF
FF
FF
РВП
FF
FF
FF
FF
ППК
1111 1111
1111 1111
1111 1111
1111 1111
Цілі типи
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу byte i1 = 110.
Переводимо 110 у 2-у систему числення (спочатку перевівши у 16-ву):
110 = 0000 00012
У пам’яті комп’ютера змінна i1 запишеться наступним чином: 0000 00012=0116
1 байт
ОР
01
РВП
01
ППК
0000 0001
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу shortint i2 = -110.
Переводимо -110 у 2-у систему числення.
110=0000 00012
-110=1111 11112
У пам’яті комп’ютера змінна i2 запишеться наступним чином:
1111 1111=FF16
1 байт
ОР
FF
РВП
FF
ППК
1111 1111
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу word i3 = 12510.
Переводимо 12510 у 2-у систему числення (спочатку перевівши у 16-ву):
12510=7D16
7D16 = 0000 0000 0111 11012
1-ий байт 2-ий байт
У пам’яті комп’ютера змінна i3 запишеться наступним чином:
0000 0001 0111 01012 = 17516
1 байт
2 байт
ОР
00
7D
РВП
00
7D
ППК
0000 0000
0111 1101
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу integer i4 = -12510.
Переводимо -12510 у 2-у систему числення (спочатку перевівши у 16-ву):
12510=7D16
7D16 = 0000 0000 0111 11012
-12510 = -7D16 = 1111 1111 1000 00112 (у доповняльному коді)
1-ий байт 2-ий байт
У пам’яті комп’ютера змінна i4 запишеться наступним чином:
1111 1111 1000 00112 =FF8316
1 байт
2 байт
ОР
FF
83
РВП
FF
83
ППК
1111 1111
1000 0011
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу longint i5 = -12510.
Переводимо -12510 у 2-у систему числення (спочатку перевівши у 16-ву):
12510=7D16
7D16 = 0000 0000 0000 0000 0000 0000 0111 11012
-7D16 = 1111 1111 1111 1111 1111 1111 1000 00112 (у доп. коді)
1-ий байт 2-ий байт 3-ий байт 4-ий байт
У пам’яті комп’ютера змінна i5 запишеться наступним чином:
1111 1111 1111 1111 1111 1111 1000 00112 = FFFFF8316
1 байт
2 байт
3 байт
4 байт
ОР
FF
FF
FF
83
РВП
FF
FF
FF
83
ППК
1111 1111
1111 1111
1111 1111
1000 0011
Дійсні типи.
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу real r1 = 10,198510. Переводимо 10,198510 у 2-у систему числення (спочатку перевівши у 16-ву):
Перевід цілої частини:
1010 = A16
1016 = 10102
Перевід дробової частини:
0,1985 х 16 = 3,176
0,176 х 16 = 2,816
0,816 х 16 = 13,056 (1310 = D16)
0,056 x 16 = 0,896
0,896 x 16 = 14,336 (1410 = E16)
0,336 x 16 = 5,376
0,376 x 16 = 6,016
0,016 x 16 = 0,256
0,256 x 16 = 4,096
0,096 x 16 = 1,536
0,32D0E5604116 =0,0011 0010 1101 0000 1110 0101 0110 0000 0100 0001
10,198510 = 0A,32D16 =
= 1010, 0011 0010 1101 0000 1110 0101 0110 0000 0100 00012
Нормалізація результату:
1010, 0011 0010 1101 0000 1110 0101 0110 0000 0100 0001 =
= 1,010 0011 0010 1101 0000 1110 0101 0110 0000 0100 ·23
1-ий байт 2-ий байт 3-ий байт 4-ий байт 5-ий байт
Визначаємо зміщений порядок: 129 + 3 = 13210 = 8416
Знаковий розряд = 0.
У пам’яті комп’ютера змінна r1 запишеться наступним чином:
1000 0100 0000 0100 0101 0110 0000 1110 0010 1101 0010 0011
(= 8404560E2D2316)
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
ОР
84
04
56
0E
2D
23
РВП
84
04
56
0E
2D
23
ППК
1000 0100
0000 0100
0101 0110
0000 1110
0010 1101
0010 0011
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу single r2 = 1274,812510.
Переводимо 1274,812510 у 2-у систему числення (спочатку перевівши у 16-ву):
Перевід цілої частини:
127410=4FA16
Перевід дробової частини:
0,8125 х 16 = 13 (= D16)
0,812510 = 0,D16
1274,812510 = 4FA,D16 =
= 0100 1111 1010, 1101 0000 0000 0000 00002
Нормалізація результату:
0100 1111 1010, 1101 0000 0000 0000 0000 =
= 1,00 1111 1010 1101 0000 0000 0000 0000 ·210
Визначаємо зміщений порядок: 127 + 10 = 13710 = 8916 = 1000 10012
Знаковий розряд = 0.
Мантиса: 0011 1110 1011 0100 0000 0000
Загальний вигляд даного числа:
0100 0100 1001 1111 0101 1010 0000 0000
У пам’яті комп’ютера змінна r2 запишеться наступним чином:
0000 0000 0101 1010 1001 1111 0100 0100
(= 005A9F4416)
1 байт
2 байт
3 байт
4 байт
ОР
00
5A
9F
44
РВП
00
5A
9F
44
ППК
0000 0000
0101 1010
1001 1111
0100 0100
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу double r3 = -1274,812510.
Переводимо -1274,812510 у 2-у систему числення (спочатку перевівши у 16-ву):
Перевід цілої частини:
127410 = 4FA 16
Перевід дробової частини:
0,8125 х 16 = 13 (= D16)
0,812510 = 0,D16
1274,812510 = 4FA,D16 =
=0100 1111 1010, 1101 (0000)2
Нормалізація результату:
0100 1111 1010, 1101 (0000)=
= 01,00 1111 1010 1101 (0000) ·210
Визначаємо зміщений порядок: 1023 + 10 =103310 =40916=0100 0000 10012
Мантиса: 00 1111 1010 1101 (0000)
Знаковий розряд = 1.
Загальний вигляд даного числа:
1100 0000 1001 0011 1110 1011 0100 (0000)
У пам’яті комп’ютера змінна r3 запишеться наступним чином:
0000 0000 0000 0000 0000 0000 0000 0000 0100 0000 1110 1011 1001 0011 1100 0000 (= 0000000040EB93С016)
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
ОР
00
00
00
00
40
EB
93
C0
РВП
00
00
00
00
40
EB
93
C0
ППК
0000 0000
0000 0000
0000 0000
0000 0000
0100 0000
1110 1011
1001 0011
1100 0000
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу extended r4 = 1274,812510.
Переводимо 1274,812510 у 2-у систему числення (спочатку перевівши у 16-ву):
Перевід цілої частини:
127410 = 4FA 16
Перевід дробової частини:
0,8125 х 16 = 13 (= D16)
0,812510 = 0,D16
1274,812510 =4FA,D16 =
= 0100 1111 1010, 1101 (0000)2
Нормалізація результату:
0100 1111 1010, 1101 (0000)=
= 01,00 1111 1010 1101 (0000) ·210
Визначаємо зміщений порядок: 16383 + 10 = 1639310 = 400916 =
100 0000 0000 10012
Мантиса: 00 1111 1010 1101 (0000)
Число і = 1
Знаковий розряд = 0.
Загальний вигляд даного числа:
0100 0000 0000 1001 1001 1111 0101 1010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
У пам’яті комп’ютера змінна r4 запишеться наступним чином:
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0101 1010 1001 1111 0000 1001 0100 0000 (= 0000000000005A9F094016)
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
9 байт
10 байт
ОР
00
00
00
00
00
00
5A
9F
09
40
РВП
00
00
00
00
00
00
5A
9F
09
40
ППК
0000 0000
0000 0000
0000 0000
0000 0000
0000 0000
0000 0000
0101 1010
1001 1111
0000 1001
0100 0000
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу comp r5 = -12510.
Переводимо -12510 у 2-у систему числення (спочатку перевівши у 16-ву):
12510 = 7D16
7D16 = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0111 11012
-12510 =-7D16 =1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1000 00112 (у доповняльному коді)
Знаковий розряд = 1.
У пам’яті комп’ютера змінна r5 запишеться наступним чином:
1000 0011 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
(= 83FFFFFFFFFFFFFF16)
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
ОР
83
FF
FF
FF
FF
FF
FF
FF
РВП
83
FF
FF
FF
FF
FF
FF
FF
ППК
1000 0011
1111 1111
1111 1111
1111 1111
1111 1111
1111 1111
1111 1111
1111 1111
Символьний тип
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу char ch = ‘С’ {кирилиця}
За таблицею ASCII-кодів визначаємо:
Ord(‘С’) = 9116
1 байт
ОР
91
РВП
91
ППК
1001 0001
Рядковий тип
Досліджуємо, як в пам’яті комп’ютера представляється змінна типу string str = ‘Сікорський’ {кирилиця}
Оскільки str:string[15], то для змінної даного типу в пам’яті комп’ютера виділиться 16 байт. У першому байті буде записано біжучу довжину рядка, а в наступних - символи рядка (тобто їх ASCII-коди).
Ord(’С’) = 9116;
Ord(’с’) = E116;
Ord(’і’) = 6916;
Ord(’ь’) = EC16;
Ord(’к’) = AA16;
Ord(’к’) = AA16;
Ord(’о’) = AE16;
Ord(’и’) = A816.
Ord(’р’) = E016;
Ord(’й’) = A916.
Даний рядок містить 10 символів, отже у першому байті буде записано 0A16.
№
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ОР
0A
91
69
AA
AE
E0
E1
EC
AA
A8
A9
X
X
X
X
X
РВП
0A
91
69
AA
AE
E0
E1
EC
AA
A8
A9
X
X
X
X
X
Примітка: X - довільні 16-ві дворозрядні числа.
Представлення у пам’яті комп’ютера:
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
00001100
10010001
01101001
10101010
10101110
11100000
11100001
11101100
9 байт
10 байт
11 байт
12 байт
13 байт
14 байт
15 байт
16 байт
10101010
10101000
10101001
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
Примітка: X - двійкові 0 або 1.
Перелічуваний тип
p: (Sikorsky, Volodumur, Petrovuch)
За умовою p = Volodumur. Під змінну даного типу буде відведено один байт. Для даного типу у пам’яті буде зберігатися порядковий номер елементу у типі. Номер рахується з нуля, отже, у пам’ять буде поміщено число 1.
1 байт
ОР
10
РВП
10
ППК
0001 0000
Тип масив
m: array [1..2,1..5] of char;
Розмір пам’яті, який відведеться для зберігання масиву дорівнюватиме 10 помножити на розмір пам’яті, який відводиться на зберігання одного елементу масиву. Змінні типу char займають у пам’яті 1 байт, отже, масив займатиме 10 байт.
В комірках пам’яті зберігатимуться коди символів:
змінна
значення
Ord(m[x,y])
m[1,1]
'9'
3916
m[1,2]
'4'
3416
m[1,3]
'0'
3016
m[1,4]
'1'
3116
m[1,5]
'0'
3016
m[2,1]
'0'
3016
m[2,2]
'1'
3116
m[2,3]
'0'
3016
m[2,4]
'8'
3816
m[2,5]
'2'
16
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
9 байт
10 байт
ОР
39
34
30
31
30
30
31
30
38
32
РВП
39
34
30
31
30
30
31
30
38
32
ППК
0011 1001
0011 0100
0011 0000
0011 0001
0011 0000
0011 0000
0011 0001
0011 0000
0011 1000
0011 0010
Тип запис
Поля запису, згідно умови, набувають значень:
Integer
Char
String[15]
rec.c1 = 5
rec.b1 = ’,’
Rec.a1 = ’Львів’
rec.c2 = 611
rec.b2 = ’,’
rec.a2 = ’Лукаша’
rec.b3 = ’/’
Проведемо розрахунок з умови, що перше поле запису зберігається по найменшій адресі. Поля зберігатимуться в порядку опису. У даному випадку порядок полів буде таким: a1, a2, b1, b2, b3, c1, c2.
Розрахуємо представлення кожного з полів.
rec.a1
Біжуча довжина рядка: 0510=0516.
Ord(’Л’) = 8B16;
Ord(’і’) = 6916;
Ord(’ь’) = EC16;
Ord(’в’) = A216;
Ord(’в’) = A216;
Займає в пам’яті 16 байт.
rec.a2
Біжуча довжина рядка: 0616.
Ord(’Л’) = 8B16;
Ord(’ш’) = E816;
Ord(’у’) = E316;
Ord(’а’) = A016;
Ord(’к’) = AA16;
Ord(’а’) = A016;
Займає в пам’яті 16 байт.
rec.b1
У одному байті пам’яті зберігатиметься код змінної. Ord(’,’)=2C16.
rec.b2
У одному байті пам’яті зберігатиметься код змінної. Ord(’,’)=2C16.
rec.b3
У одному байті пам’яті зберігатиметься код змінної. Ord(’/’)=2F16.
rec.c1
Займає в пам’яті 2 байти. 510 = 0516 (05 00 – у пам’яті комп’ютера)
rec.c2
Займає в пам’яті 2 байти. 61110 = 26316 (63 02 – у пам’яті комп’ютера)
Файловий тип
Оскільки файли складаються з послідовних компонентів, то у даному текстовому файлі знаходитимуться ASCII–коди усіх символів по порядку плюс символи переходу на наступний рядок.
What would you like to do?
1.Look at the saved file of text.
2.See general case.
Your choice...
1:The text file consists of 2 lines
Б
М
File of text f is saved in the
following form...
81A0E2EC
lolojjj
2:What would you like to do?
1.Look at the saved file of text.
2.See general case.
Your choice...
2
Enter 2 lines to be saved in a file...
Line1: www
Line2: red
Now please run c:\ff
to check the result
Задача на сортування методом обміну.
Задана послідовність:
44 55 12 42 94 18 10 67 43 23 76 78 46 64 16
Сортуємо послідовність методом бульбашки (перший прохід бульбашки демонструю детально):
44 55 12 42 94 18 10 67 43 23 76 78 46 64 16 — 1)
44 12 55 42 94 18 10 67 43 23 76 78 46 64 16 55 ( 12
44 12 42 55 94 18 10 67 43 23 76 78 46 64 16 55 ( 42
44 12 42 55 18 94 10 67 43 23 76 78 46 64 16 94 ( 18
44 12 42 55 18 10 94 67 43 23 76 78 46 64 16 94 ( 10
44 12 42 55 18 10 67 94 43 23 76 78 46 64 16 94 ( 67
44 12 42 55 18 10 67 43 94 23 76 78 46 64 16 94 ( 43
44 12 42 55 18 10 67 43 23 94 76 78 46 64 16 94 ( 23
44 12 42 55 18 10 67 43 23 76 94 78 46 64 16 94 ( 76
44 12 42 55 18 10 67 43 23 76 78 94 46 64 16 94 ( 78
44 12 42 55 18 10 67 43 23 76 78 46 94 64 16 94 ( 46
44 12 42 55 18 10 67 43 23 76 78 46 64 94 16 94 ( 64
44 12 42 55 18 10 67 43 23 76 78 46 64 16 |94 94 ( 16
Вихідна послідовність ( | ( готова послідовність
12 42 44 18 10 55 43 23 67 76 46 64 16 |78 94
12 42 18 10 44 43 23 55 67 46 64 16 |76 78 94
12 18 10 42 43 23 44 55 46 64 16 |67 76 78 94
12 10 18 42 23 43 44 46 55 16 |64 67 76 78 94
10 12 18 23 42 43 44 46 16 |55 64 67 76 78 94
10 12 18 23 42 43 44 16 |46 55 64 67 76 78 94
10 12 18 23 42 43 16 |44 46 55 64 67 76 78 94
10 12 18 23 42 16 |43 44 46 55 64 67 76 78 94
10 12 18 23 16 |42 43 44 46 55 64 67 76 78 94
10 12 18 16 |23 42 43 44 46 55 64 67 76 78 94
10 12 16 18 23 42 43 44 46 55 64 67 76 78 94
Структура даних „збалансоване дерево”.
В даному випадку зі збалансованим деревом ми можемо виконати такі дії:
Додати елемент у дерево;
Вивести на екран вміст дерева (роздрук елементів дерева);
Знайти суму всіх елементів дерева.
Наприклад, додамо до дерева такі елементи:
12, 43, 23, 65, 54, 76, 56, 87, 90, 95, 39, 19.
Після виведення на екран вмісту дерева на екрані отримаємо:
54
23 87
12 43 65 90
19 39 56 76 95
Знаходимо суму елементів дерева.
На екрані отримаємо:
Сума: 659
Висновки
За допомогою курсової роботи мені вдалося закріпити знання з програмування та основ алгоритмізації. Я дослідив представлення деяких типів даних в пам’яті комп’ютера. Розглянув деякі алгоритми сортування, зокрема метод обміну і найпоширеніший з його видів сортування методом бульбашки. Вдалося дізнатися про різні структури даних і зрозуміти алгоритми, які будуються на їх основі. Курсова робота дала можливість практично засвоїти теоретичні знання.
Список літератури
Кнут Д. Искусство программирования, том 1. Основные алгоритмы. –М.: Изд. дом ”Вильямс”, 2001. – 720 с.
Кнут Д. Искусство программирования, том 3. Сортировка и поиск. –М.: Изд.дом ”Вильямс”, 2001. – 832 с.
Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. –К.:Век+, 1999 - 460 с.
Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі. –К:Либідь, 1993 - 224 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы , построение и анализ. Классические учебники: computer science – 2001. - 860 с.
Ленгсам Й., Огенстайн М., Тененбаум А. Структура данных для персональных ЭВМ. –М.:Мир, 1989 - 560 с.
Матьяш В.А., Путилов В.А., Фильчакрв В.В., Щекин С.В. Структуры и алгоритмы обработки данных. Учебное пособие. – Апатиты, КФ ПетрГУ, 2000
Додатки
program Main;
uses strings,crt,Unit_kur;
var i4:integer;
r2:single;
k,i:integer;
b1:boolean;
begin
{Main window}
TextColor(0);
TextBackground(15);
clrscr;
writeln(' Мiнiстерство освiти i науки України');
writeln(' Нацiональний унiверситет "Львiвська полiтехнiка"');
writeln(' Курсова робрта ');
gotoxy(1,25);
write(' Львiв 2004 ');
{Window to output}
window(2,4,79,24);
TextColor(9);
TextBackground(8);
{Menu}
repeat
clrscr;
writeln(' ГОЛОВНЕ МЕНЮ');
writeln('0: Вихiд;');
writeln('1: Дослiдження типiв даних;');
writeln('2: Зазача на сортування методом обмiну;');
writeln('3: Структура даних "Збалансоване дерево".');
writeln;
write('Ваш вибiр: ');
readln(i);
case i of
1: begin
clrscr;
Writeln (' 0: Вихiд;');
writeln (' 1: Логiчнi типи;');
writeln (' 2: Цiлi типи;');
writeln (' 3: Дiйснi типи;');
writeln (' 4: Символьний тип;');
writeln (' 5: Рядковий тип;');
writeln (' 6: Перелiчувальний тип;');
writeln (' 7: Дiапазонний тип;');
writeln (' 8: Масив;');
writeln (' 9: Запис;');
writeln ('10: Файловий тип;');
writeln;
write('Ваш вибiр: ');
readln(k);
case k of
1: begin
clrscr;
writeln('1: Тип Boolean ; ');
writeln('2: Тип Wordbool; ');
writeln('3: Тип Longbool; ');
writeln;
write('Ваш вибiр: ');
readln(k);
case k of
1: begin clrscr; boolean1;end;
2: begin clrscr; Wordbool1;end;
3: begin clrscr; LongBool1;end;
end;
end;
2: begin
clrscr;
writeln('1: Тип Byte ');
writeln('2: Тип Shortint ');
writeln('3: Тип Word ');
writeln('4: Тип Integer ');
writeln('5: Тип Longint ');
writeln;
write('Ваш вибiр: ');
readln(i);
case i of
1 : begin clrscr; byte1; end;
2 : begin clrscr; TShortint; end;
3 : begin clrscr; word1; end;
4 : begin clrscr; integer1; end;
5 : begin clrscr; longint1; end;
end;
end;
3: begin
clrscr;
writeln('1 : Real ');
writeln('2 : Single ');
writeln('3 : Double ');
writeln('4 : Extended ');
writeln('5 : Comp ');
writeln;
write('Ваш вибiр: ');
readln(i);
case i of
1: begin clrscr; real1; end;
2: begin clrscr; single1; end;
3: begin clrscr; double1; end;
4: begin clrscr; extended1; end;
end;
end;
4: begin clrscr; TChar; end;
5: begin clrscr; string1; end;
6: begin clrscr; per1; end;
7: begin clrscr; diap1; end;
8: begin clrscr; mas1; end;
9: begin clrscr; reczapus1; end;
10: begin clrscr; fltxt1; end;
end;
end;
2: begin clrscr; ObminSort; end;
3: begin clrscr; balance; end;
end;
until i=0;
end.
UNIT Unit_Kur;
INTERFACE
USES crt;
Type
Tinfo=integer;
PTree = ^node;
node = record
info: integer;
Left, right: PTree;
Bal: -1..1;
count:integer;
End;
procedure search(x: integer; var p: PTree; var h: boolean);
procedure Init (Var T:PTree);
Function Empty (T:PTree):boolean;
Function WhoLeft (k:Ptree):ptree;
Function WhoRight (k:Ptree):ptree;
Procedure PrintLevel (T:ptree; k,i,j:byte);
procedure PrintTurningTree (T:ptree; h,n:byte);
Procedure GoStraight (T:Ptree;Var s:integer);
PROCEDURE TShortint;
{PROCEDURE TReal;}
PROCEDURE TChar;
PROCEDURE ObminSort;
PROCEDURE Balance;
PROCEDURE boolean1;
PROCEDURE wordbool1;
PROCEDURE longbool1;
PROCEDURE byte1;
PROCEDURE word1;
PROCEDURE integer1;
PROCEDURE longint1;
PROCEDURE double1;
PROCEDURE...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора