Нормативний типи. Динамічні змінні
Курсова робота з дисципліни «інформатика»
Студент групи
Тюменський державний нафтогазовий університет
2007
Анотація
У даній пояснювальній записці містять 65 сторінок, 7
картинок. Програма «Алфавіт» займає 538 байт, «Калькулятор» займає 535
байт. Дана дипломна робота розкриває тему посилальних даних і динамічних
змінних. Містить дві голови. У першому розділі дається теоретичне пояснення
документальний даними і динамічним змінним. У другому розділі дає практичне
пояснення, яке розкрито в двох завданнях.
Федеральне агентство з освіти
державне освітня установа вищої
професійної освіти
Тюменський державний нафтогазовий університет
Тбіліський інститут індустріальний
«Затверджую:»
Завідувач Кафедри
___________________
___________________
«___»________ 200_ р.
Завдання
Курсова робота з дисципліни
інформатика
Студент: група: керівник:
Тема курсової роботи: Нормативний типи. Динамічні
змінні
Технічне завдання
Скласти програму «Калькулятор»
Скласти програму, що містить процедуру яка,
виконує сортування списку за значенням поля містить символьні значення з
набору букв латинського алфавіту
Звітний матеріал курсової роботи
Пояснювальна записка
Дискета з відкладеним версією програми
Рекомендована література
Рапаков Г. Г. і Ржецукая С. Ю.. Turbo Pascal для
студентів та школярів. BHV - С.-Петербург 2004
Меженний О. А. Turbo Pascal: учитель програмування.
Діалектіва 2001.
Культин Н.. Програмування в Turbo Pascal і Delphi.
BHV 2003
Фаронов В. В. Turbo Pascal: навчальний посібник. BHV 2006
Завдання видано «__»_____ 200_ р.
Керівник ______
(підпис)
Відгук керівника
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Руководітель_________
(підпис)
Завдання прийнято «__»_______ 200_ р.
Введення
У будь-якій обчислювальній системі пам'ять відноситься до
таких ресурсів, яких завжди не вистачає. Управління пам'яттю - один з головних
турбот програміста, тому що для нього дуже важливо створювати програми,
ефективно використовують пам'ять, адже під час виконання програми пам'ять
необхідна для наступних елементів програм і даних:
сама програма користувача;
системні програми часу виконання, які
здійснюють допоміжні дії при роботі програми користувача;
визначені користувачем структури даних і
константи;
точки повернення для програм;
тимчасова пам'ять для зберігання проміжних
результатів при обчисленні виразів;
тимчасова пам'ять при передачі параметрів;
буфери вводу-виводу, що використовуються як тимчасові
області пам'яті, в яких зберігаються дані між моментом їх реальної фізичної
передачі з зовнішнього пристрою або на нього і моментом ініціалізації в програмі
операції введення або виведення;
різні системні дані (інформація про статус
пристроїв введення-виведення та ін.)
І статичні і динамічні змінні викликаються по
їх адресами. Без адреси не отримати доступ до потрібної комірці пам'яті, але, використовуючи
статичні змінні, безпосередньо адресу не вказуєте, а звертаєтеся до
змінною по імені. Компілятор розміщує змінні в пам'яті і підставляє
потрібні адреси в коди команд.
Адресація динамічних змінних відбувається через
покажчики. У Паскалі можна визначити змінні, які мають тип покажчик,
їх значення визначають адреса об'єкту. Для роботи з динамічними змінними в
програмі повинні бути передбачені:
виділення пам'яті під динамічну змінну;
присвоєння вказівником на динамічну змінну адреси
виділеної пам'яті (ініціалізація покажчика);
звільнення пам'яті після використання динамічної
змінної.
З цього переліку видно, що управління пам'яттю
стосується широкого класу об'єктів.
Програміст сам повинен резервувати місце під
змінну, визначати значення покажчиків, звільняти пам'ять - видаляти
динамічні змінні. Для використання динамічної змінної десь у
статиці повинен бути вказівник на неї. Компілятор передбачає місце під
покажчик, про ініціалізації покажчика має дбати програміст.
Замість будь-якої статичної змінної можна використовувати
динамічну, але без реальної необхідності цього робити не варто. Змінні
простих типів немає сенсу розміщувати в динамічній області, оскільки вони
займають менше місця, ніж покажчик на них. Наприклад, покажчик на ціле займає
4 байти, саме ціле - 2 байти. Крім того, при динамічному розподілі
пам'яті подовжується текст програми, знижуються наочність і швидкодію. Це
пояснюється тим, що, по-перше, потрібно під час виконання програми визначати
значення покажчиків, а по-друге, ускладнюється доступ до значення змінної.
Глава I. Теоретична
частина
1. Покажчики. Опис
покажчиків
Покажчики - це особливий тип даних. У змінних цього
типу зберігаються адреси інших змінних що містять корисну для програми
інформацію. На перший погляд може здатися, що використання покажчиків
призводить до зайвих витрат пам'яті і до ускладнення програми, а також істоті
ускладнює й сам процес програмування. У цьому розділі ви, наведемо такі
приклади використання покажчиків, з яких стане ясно, що всі
додаткові витрати на їх зберігання та обробку окуповуються в повній мірі.
Робота з вказівниками передбачена не тільки в Pascal, але і в деяких інших
мовах програмування. Наприклад, у мові З покажчики використовуються практично
в будь-якій програмі.
У Pascal роль покажчиків декілька скромніше, і, тим не
менше, починаючим програмістам слід засвоїти базові принципи роботи з
покажчиками, щоб глибше зрозуміти внутрішній механізм обробки та виконання
будь-якої комп'ютерної програми.
1.1. Покажчики та адреси
Відомо, що адресою змінної є адреса
першого байта комірки пам'яті, яка під неї відводиться. Для даних структурних
типів (масивів і записів) їх адресою вважається адресу першого байта першого
елементу.
У Turbo Pascal існує можливість прямого доступу
до будь-якого байту оперативної пам'яті на його адресу за допомогою визначених у
модулі system масивів Mem, MemW і MemL, які дозволяють записати інформацію
або прочитати її безпосередньо з комірок пам'яті (один, два або чотири байти).
Це дуже небезпечні дії, тому вони виключені в 32 - розрядних системах
програмування. Все ж таки дамо короткі пояснення для тих, хто працює в середовищі
Borland (Turbo) Pascal.
Як індексу в цих масивах використовується адреса,
записаний у вигляді, прийнятому в DOS: сегмент: Зсув відносно початку
сегмента. Такий дивний спосіб запису адреси пов'язаний з тим, що в операційній
системі DOS вся пам'ять розбита на сегменти, розміри яких не перевищують 64
Кбайт. Для отримання абсолютної адреси з пари сегмент Зсув система
додає до сегменту справа шістнадцятковий нуль (це чотири нулі в двійковій
системі), а потім складає його зі зміщенням. Таким способом можна адресувати
1 Мбайт пам'яті.
Наприклад, початкова адреса відеобуфера запишеться у вигляді
$ B800: $ 000, а звернутися до самого першу його байту можна так:
Mem [$ В800: $ 0000], до перших двох байтам - MemW [$ B800: $ 0000], до перших чотирьох
байтам - MemL [$ B800: $ 0000]. Абсолютний адреса, що відповідає даній парі, --
$ B8000.
Ще один приклад для допитливих - оператор
mem [0: $ 41C]: = mem [0: $ 41А]; можна застосувати для примусової очищення буфера
клавіатури. Тут адреса маркера кінця буфера клавіатури прирівнюється до адреси
його початку. Звичайно, в даному випадку краще скористатися засобами модуля
crt.
Є ще один спосіб звернення до оперативної пам'яті
- Використання службового слова absolute при описі змінної. У цьому
випадку змінна буде розташовуватись саме за тією адресою в оперативній
пам'яті, який вказаний після absolute. Зрозуміло, використання службового
слова absolute - настільки ж небезпечний спосіб, як і звернення до пам'яті через
зумовлені масиви.
Однак absolute може використовуватися і більше
безпечним способом, дозволяючи поєднувати в пам'яті дві змінні з різними
іменами. У мові Pascal є спеціальна операція отримання вказівника на
змінну (або процедуру) - вона позначається як @. Є також
еквівалентна їй функція addr.
Наприклад, @ x або addr (х) - адреса змінної х.
Є і зворотна операція отримання значення
змінної на її адресу, що позначається знаком ^. Наприклад, р ^ мінлива
з адресою р.
У повсякденній практиці засоби роботи з адресами
використовуються досить рідко. Основне призначення покажчиків полягає в тому,
щоб забезпечити механізм використання у програмі динамічних змінних.
Цей механізм ми і будемо обговорювати докладно в наступних розділах.
1.2. Опис покажчиків
У Pascal є два різних види покажчиків:
типізовані і нетипізовані. Типізований покажчик - це покажчик на
змінну певного типу, наприклад, цілого, строкового або типу масиву
Нетіпізарованний покажчик - це адреса першого байта області пам'яті, в якій
може розміщуватися будь-яка інформація, незалежно від її типу.
Опис двох видів покажчиків виконується по-різному:
var p1: ^ integer; (покажчик на змінну цілого
типу)
p2: ^ string; (вказівник на стоку)
p3 pointer; (нетипізований покажчик)
Зауважимо що тип pointer сумісний з усіма типами
покажчиків. У подальшому викладі для зручності імена всіх покажчиків будемо
починати з букви p (pointer).
Кожен покажчик розміщується в сегменті даних або в
стеку (якщо він оголошений в підпрограмі) і займає там 4 байти. Це
додаткові "накладні витрати 'пам'яті. Тому звичайні змінні дуже
рідко створюють і знищують динамічно, залишаючи цю можливість для великих
сукупностей даних.
Чим більше розмір динамічної змінної, тим менше
частка накладних витрат. Наприклад, при зберіганні у динамічній пам'яті масивів
великих розмірів зайві 4 байти, витрачені на покажчик, несуттєві.
2. Списки
Списки представляють собою спосіб організації структури
даних, при якій елементи деякого типу утворюють ланцюжок. Для зв'язування
елементів у списку використовують систему покажчиків. У мінімальному випадку, будь -
елемент лінійного списку має один покажчик, який вказує на наступний
елемент у списку або є порожнім покажчиком, що інтерпретується як кінець
списку. На рис. 1 наведено понятійне зображення лінійного списку.
2.1 Лінійні
односпрямовані списки
Лінійні односпрямовані списки є динамічною
структурою даних, кожен елемент якої складається з інформативною і посилальної
частини. Нижче представлено опис динамічної рядка символів.
type
TypeOfElem = Char;
Assoc = ^ DynElem;
DynElem = record
Elem: TypeOfElem;
NextElem: Pointer
end;
DynStr = Assoc;
На практиці, для обробки динамічних рядків вводять
два покажчика: на початок і кінець (поточний елемент) ланцюжка.
var HeadOfStr:
Pointer; ElemOfStr: DynStr;
Для створення ланцюжка виконується послідовність
операторів, пов'язана з початковим покажчиком.
new (ElemOfStr);
ElemOfStr ^. Elem: =
