Структури даних їх характеристика.

Системи типів в мовах високого рівня дозволяють визначати складні, складові типи, так звані структури даних. Як правило, структурні типи даних утворюються як декартово твір базових (атомарних) типів і раніше визначених складових типів.

Основні структури даних (списки, черги, хеш-таблиці, двійкові дерева і пари) часто представлені особливими синтаксичними конструкціями в мовах високого рівня. Такі дані структуруються автоматично.

Під час роботи довільної програми значення деякої статичної змінної може змінюватися, але власне кількість оголошених статичних змінних не змінюється. Це не завжди зручно. Наприклад, якщо програма призначена для введення та обробки даних про учнів класу, а для збереження цих даних використовується звичайний масив, то визначаючи розмір масиву, приходиться орієнтуватися на деяке, як здається програмісту, граничне значення учнів в класі. При цьому якщо реально учнів в класі менше цього граничного значення, то пам’ять ПК використовується неефективно. Якщо ж учнів більше – то таку програму використовувати взагалі не можна.
В таких задачах зручно використовувати структури (подібні до масивів) в яких кількість елементів може змінюватися. Такими структурами є зв’язані список. Зв’язаний список нагадує масив, в якому кількість елементів змінюється під час роботи програми.
Зв’язаний список можна побудувати використовуючи динамічні змінні. Динамічні змінні можна створювати під час роботи програми («на ходу») за допомогою так званих змінних-вказівників.

ЗМІННІ-ВКАЗІВНИКИ
Змінну-вказівник можна уявити як звичайну статичну змінну, але таку, в якій зберігається не деяке конкретне значення (наприклад типу integer, real, …), а адрес іншої змінної. Змінна-вказівник (р) нагадує конверт, який містить лише адресу квартири Петрова, а не її вміст. Можна сказати, що змінна-вказівник р вказує на іншу змінну, яка знаходиться за адресою вул.. 1-го Травня, 58.
Вміст змінної-вказівника р:
Вул. 1 Травня, 58
Вміст змінної за адресою «Вул. 1 Травня, 58» (ця змінна не має імені):
Квартира Петрова
Змінна, що містить значення Квартира Петрова не є звичайною статичною змінною – вона динамічна.
<Ім’я змінної-вказівника>:^тип динамічної змінної

ЗВ’ЯЗАНИЙ СПИСОК. СТЕК

Вказівники та динамічні змінні дозволяють створювати складні динамічні структури.
Найпростішою з них є зв’язаний список.
Елемент списку a1^ – це динамічна змінна (наприклад типу zapis=record), яка в найпростішому випадку складається з двох полів: інформаційного (наприклад, name:string) та змінної-вказівника на наступний елемент списку (next:^zapis). Тобто, динамічна змінна – елемент списку – крім деякого значення містить адресу (змінну-вказівник) наступного елемента списка.

ЗВ’ЯЗАНИЙ СПИСОК. ЧЕРГА.

Формування черги (вставка елементів в кінець списку).
Після створення динамічної змінної s^,поміщаємо в неї «Ільчук». Потім необхідно на цей елемент «напрямити» вказівник елемента sn^ (динамічна змінна sn^ містить вказівник next. А отже, sn^.next:=s;). Після цього елемент «Ільчук» добавиться в кінець списку. Але вказівник sn ще вказує на попередньо останній елемент (тобто на «Сидоров»). Напрямимо його на «Ільчук» (на «Ільчук вказує s. Отже, sn:=s).
ФОРМУВАННЯ ВПОРЯДКОВАНОГО СПИСКУ.
S1 – вказівник на перший елемент списку
S_new – вказівник на новий елемент списку
S_p – вказівник на елемент, після якого необхідно здійснити вставку нового елемента

бінарне дерево тощо

Стандартизація мов програмування

Мова програмування може бути представлена у вигляді набору специфікацій, що визначають його синтаксис і семантику.

Для багатьох широко поширених мов програмування створені міжнародні стандарти. Спеціальні організації проводять регулярне оновлення і публікацію специфікацій і формальних визначень відповідної мови. В рамках таких комітетів продовжується розробка і модернізація мов програмування і вирішуються питання про розширення або підтримки вже існуючих і нових мовних конструкцій.

Типи даних

Сучасні цифрові комп'ютери є двійковими і дані зберігають у довічним (бінарному) коді (хоча можливі реалізації і в інших системах числення). Ці дані зазвичай відображають інформацію з реального світу (імена, банківські рахунки, вимірювання та ін.), що представляє високорівневі концепції.

Особлива система, за якою дані організовуються в програмі, - це система типів мови програмування.

Розробка та вивчення систем типів відома під назвою теорія типів.

Мови можна поділити на:

- статичну типізацію;

- динамічну типізацію,

- а також безтипові мови (наприклад, Forth).

Статично типізовані мови можуть бути надалі поділені на мови з обов'язковою декларацією, де кожна змінна і оголошення функції має обов'язкове оголошення типу, і мови з виведеними типами.

Системи типів в мовах високого рівня дозволяють визначати складні, складові типи, так звані структури даних. Як правило, структурні типи даних утворюються як декартово твір базових (атомарних) типів і раніше визначених складових типів. Основні структури даних (списки, черги, хеш-таблиці, двійкові дерева і пари) часто представлені особливими синтаксичними конструкціями в мовах високого рівня. Такі дані структуруються автоматично.

Семантика мов програмування

Найбільш широко поширені різновиди наступних трьох: операційного, денотаціонного (математичного) і дериваційного (аксіоматичного).

При описі семантики в рамках операційного підходи звичайно виконання конструкцій мови програмування інтерпретується за допомогою деякої уявної (абстрактної) ЕОМ. Дериваційна семантика описує наслідки виконання конструкцій мови за допомогою мови логіки і завдання перед-і Післяумови. Денотаціона семантика оперує поняттями, типовими для математики - безлічі, відповнідності, а також судження, затвердження та ін Мова програмування будується відповідно до тієї чи іншої базової моделі обчислень і парадигмою програмування.

Незважаючи на те, що більшість мов орієнтоване на імперативну модель обчислень, що задається фоннеймановской архітектурою ЕОМ, існують і інші підходи. Можна згадати мови зі стекової обчислювальної моделлю (Forth, Factor, Postscript та ін), а також функціональне (Лісп, Haskell, ML та ін) і логічне програмування (Пролог) і мова Рефаїл, заснований на моделі обчислень, введеної радянським математиком А. А. Марковим-молодшим.

Концепция языка программирования неотрывно связана с его реализацией. Для того чтобы компиляция одной и той же программы различными компиляторами всегда давала одинаковый результат, разрабатываются стандарты языков программирования. Существует ряд организаций, целенаправленно занимающихся вопросами стандартизации. Это Американский национальный институт стандартов ANSI(American National Standards Institute), Институт инженеров по электротехнике и электронике IEEE (Institute of Electrical and Electronic Engineers), Организация международных стандартов ISO (International Organization for Standardization).

Как правило, при создании языка выпускается частный стандарт, определяемый разработчиками языка. Если язык получает широкое распространение, то со временем появляются различные версии компиляторов, которые не точно следуют частному стандарту. В большинстве случаев идет расширение зафиксированных первоначально возможностей языка. Для приведения наиболее популярных реализаций языка в соответствие друг с другом разрабатывается согласительный стандарт. Очень важным фактором стандартизации языка программирования является своевременность появления стандарта – до широкого распространения языка и создания множестванесовместимых реализаций. В процессе развития языка могут появляться новые стандарты, отражающие современные нововведения. Так, язык FORTRAN первоначально был стандартизирован в 1966 году. В результате был издан стандарт FORTRAN 66. Далее этот стандарт несколько раз пересматривался (в 1977 году был выпущен FORTRAN 77, затем появился и FORTRAN 90).

В процессе развития языка некоторые его конструкции и функции устаревают. Однако с целью обратной совместимости новые версии должны поддерживать и все устаревающие возможности. Это ведет к "разбуханию" компиляторов. В последнее время в реализациях введено понятие не рекомендуемой и устаревшей возможности. В первом случае следующий стандарт еще будет поддерживать не рекомендуемую возможность, но может перевести ее в категорию устаревшей. Во втором случае стандарт может исключить поддержку возможности, объявленной ранее как устаревшая. Введение не рекомендуемых и устаревших возможностей предоставляет разработчикам временнойинтервал, в течение которого они могут модифицировать код в соответствии с новыми требованиями стандарта.