Структура (тип даних)

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

Наприклад інформація може зберігатися як запис, що вміщує числове поле року, поле місяця, представлене як рядок та числове поле дня місяця. Запис Персоналу може вміщувати ім'я, платню та посаду. Запис Кола може вміщувати центр та радіус — у цьому прикладі сам центр може бути представлений як запис точки, який містить координати x та у.

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

Тип запису це тип інформації, що описує такі значення та змінні. Найсучасніші комп'ютерні мови дозволяють програмісту визначати нові типи записів. Визначення включає вказання типу інформації кожного поля та ідентифікатор (назва, ярлик, тег, мітка), через який до нього можна отримати доступ. У теорії типів, добуток типів (з відсутніми назвами полів) в загальному переважає через простоту, але належні типи записів вивчаються на мовах таких як система F-sub. Оскільки записи теоретичного типу можуть вміщувати першокласні поля функціонального типу, додатково з інформацією вони можуть виражати багато характеристик об'єктно-орієнтованого програмування

Записи можуть існувати у будь-якому середовищі зберігання, включаючи основну пам'ять та носії даних, такі як магнітна стрічка або жорсткі диски. Записи — це основний компонент більшості структур інформації, особливо пов'язані структури даних.^{[джерело?]} Багато файлів комп'ютеру організовані як масиви логічних записів, часто згруповані у більші фізичні записи або блоки для ефективності. Параметри функції або процедури часто можуть розглядатися як поля перемінного запису; і аргументи, спрямовані на цю функцію можуть розглядатися як значення запису, що призначається до цієї змінної під час запиту. Також у стеку викликів це часто використовується для здійснення процедурних запитів, кожний вхід це активація запиту або конструкція запиту, що містить параметри процедури та місцеві перемінні, зворотню адресу та інші внутрішні поля.

Об'єкт у об'єктно-орієнтованій мові — це обов'язково запис, що містить процедури спеціалізовані для підтримання цього запису; і типи об'єктів — це удосконалення типів записів. Насправді, у найбільш об'єктно-орієнтованій мові записи це лише спеціальні типи об'єктів і відомі як прості структури даних, на відміну від об'єктів, які використовують об'єктно-орієнтовані характеристики.

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

Історія ред.

Поняття запису можна простежити до різних типів таблиць і бухгалтерських книг, що використовуються в бухгалтерському обліку, так як в далекі часи. Сучасне поняття записів в інформатиці, з полями чітко визначеного типу і розміру, вже закладена в 19-му столітті механічними калькуляторами, такими як аналітична машина Беббіджа.

Оригінальним машинозчитуваним носієм, який використовувався для даних була перфокарта, що використовувалась для перепису у Сполучених Штатів в 1890: кожна перфокарта була одним записом. Порівняйте записи журналу з 1880 року і перфокарту з 1895. Записи добре зарекомендували себе в першій половині 20-го століття, коли найбільшу кількість даних було оброблено за допомогою перфокарт. Як правило, кожен запис даних був записаний в одній перфокарті із зазначенням конкретних стовпців, що присвоювалися конкретним назвам. В основному, запис був найменшою одиницею, яка могла бути прочитана з зовнішнього пристрою (наприклад, пристрої читання карт, стрічка або диск).

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

Концепція записів і полів займала центральне місце в деяких ранніх утилітах з сортування і даних та табуляції, таких як RPG (мова програмування) — генератор звітів компанії IBM.

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

Ранні мови, розроблені для простих обчислень, такі як FORTRAN (до FORTRAN IV) і Algol 60, не мають підтримки типів записів; але більш пізні версії цих мов, такі як Fortran 77 і ALGOL 68^[en] підтримують останні. Оригінальна версія мови програмування LISP теж не підтримує записів, але його S-вирази є адекватною заміною. Мова програмування Pascal була одною з перших мов, що повністю інтегрувала типи записів з іншими базовими типами в логічну екосистему.

Мова програмування C спочатку підтримувала концепцію запису як свого роду шаблон (struct), ніж повноцінний запис. Останній зрештою був наданий (за допомогою декларації typedef ), але ці два поняття і досі відрізняються. Більшість мов, розроблені після того, як був розроблений Pascal (наприклад, Ada, Modula і Java ) також підтримують записи.

Операції ред.

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

Вибір поля від значення запису дає значення.

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

У системах з записами підтипів, операції на значеннях типу запису можуть також включати в себе:

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

Призначення і порівняння ред.

Більшість мов дозволяють присвоювання між записами, які мають такий самий тип запису (в тому числі тих же типів полів і імен, в тому ж порядку). Проте залежно від мови, два типи запису даних, які були визначені окремо, можуть бути розглянені як окремі види, навіть якщо вони мають одні і ті ж поля. Деякі мови можуть також дозволяти присвоювання між записами, чиї поля мають різні імена, відповідні кожному значенню поля з відповідною змінною поля згідно з їх позиціями в запису; так що, наприклад, комплексне число з полями real і imag можуть бути віднесені до двовимірної точки із полями X і Y . В цьому прикладі потрібні два операнда з метою мати ту ж послідовність типів полів. Деякі мови можуть також вимагати, щоб відповідні типи мали однаковий розмір і кодування, так що весь запис може бути призначений як неінтерпретований бітовий рядок. Інші мови можуть бути більш гнучкими в цьому відношенні, і вимагають тільки, що кожне значення поля може бути абсолютно легально віднесено до відповідної змінної поля; так що, наприклад, short integer поле може бути призначене до long integer поля, або навпаки. Інші мови (наприклад, COBOL) можуть порівнювати поля і значення за їхніми іменами, а не позиціями. Ці ж можливості застосовуються для порівняння двох записів на рівність. Деякі мови можуть також дозволити інші порівняння такі як ('<' і '>'), використовуючи лексикографічний порядок на основі порівняння окремих полів.

Дистрибутивний вибір поля в Algol 68 ред.

У Algol 68, якщо Pts був масив записів, кожен з яких був цілим числом X і Y , можна було б написати Pts.Y , щоб отримати масив цілих чисел, що складається з Y полів всіх елементів Pts . В результаті, оператори Pts[3].Y := 7і Pts.Y[3] := 7 буде мати той самий ефект.

Оператор"with" у Pascal ред.

У мові програмування Pascal, командаwith R do S буде виконувати послідовність команд S , як якщо б все полів запису R були оголошені як змінні. Таким чином, замість того, щоб писати

pt.x := 5;
pt.y := pt.x + 3;

можна написати

with pt do begin
    x := 5;
    y := x + 3;
end

.

Відображення у пам'яті ред.

Відображення записів у пам'яті відрізняється залежно від мови програмування. Зазвичай поля зберігаються у послідовному положенні у пам'яті, в тому ж порядку, в якому вони були оголошені в типі запису. В результаті це може спричинити, що два або більше полів зберігаються в одному й тому ж слові у пам'яті; насправді ця характеристика часто використовується у системному програмуванні, щоб отримати доступ до спеціальних уривків слова. З іншого боку більшість компіляторів будуть додавати перевантажуючі поля, в цілому невидимі для програміста для дотримання групових обмежень накладених машиною, — тоді говорять, що поле числа з рухомою комою має займати лише одне слово. Деякі мови можуть представляти запис як масив адрес, що вказують на поля (і, можливо, на їх назви та\або типи). Об'єкти у об'єктно-орієнтованих мовах часто представлені у здебільшого складний спосіб, особливо у мовах, що дозволяють множинне наслідування класів.

Записи, що визначаються самостійно ред.

Записи, що визначаються самостійно — це тип записів, що вміщують інформацію для визначення типу запису та місце знаходження інформації у записі. Вони можуть вміщувати нащадки елементів; елементи можуть, унаслідок цього, зберігатися у будь-якому порядку або можуть не бути включені. За альтернативою різні елементи запису, в яких кожний включає ідентифікатор елементу, можуть просто наслідувати один одний у будь-якому порядку.