Запись (информатика) - Record (computer science)

В информатике , A запись (также называется структура , структура или соединение данных ) является одним из основных структуры данных . Записи в базе данных или электронной таблице обычно называют « строками ».

Запись - это набор полей , возможно, разных типов данных, обычно с фиксированным числом и последовательностью. Поля записи также могут называться членами , особенно в объектно-ориентированном программировании ; поля также могут называться элементами , хотя это может привести к путанице с элементами коллекции .

Например, дата может быть сохранена в виде записи , содержащей числовой год поле, месяц поле , представленное в виде строки, и числовой день-месяца поля. Кадровая запись может содержать имя , зарплату и звание . Запись Circle может содержать центр и радиус - в этом случае сам центр может быть представлен как запись точки, содержащая координаты x и y .

Записи отличаются от массивов тем, что количество полей в них обычно фиксировано, каждое поле имеет имя и каждое поле может иметь свой тип.

Тип записи - это тип данных, который описывает такие значения и переменные. Большинство современных компьютерных языков позволяют программисту определять новые типы записей. Определение включает в себя указание типа данных каждого поля и идентификатора (имени или метки), по которому к нему можно получить доступ. В теории типов , виды продукции (без каких - либо названий полей) , как правило , предпочтительны из - за их простоту, но соответствующие записи типов изучаются в таких языках, как система F-суб . Поскольку теоретико-типовые записи могут содержать поля с функциональным типом первого класса в дополнение к данным, они могут выражать многие особенности объектно-ориентированного программирования .

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

Параметры функции или процедуры часто можно рассматривать как поля переменной записи; и аргументы, переданные этой функции, можно рассматривать как значение записи, которое присваивается этой переменной во время вызова. Кроме того, в стеке вызовов, который часто используется для реализации вызовов процедур, каждая запись является записью активации или кадром вызова , содержащим параметры процедуры и локальные переменные, адрес возврата и другие внутренние поля.

Объект на объектно-ориентированном языке - это, по сути, запись, содержащая процедуры, специализированные для обработки этой записи; а типы объектов - это разработка типов записей. Действительно, в большинстве объектно-ориентированных языков записи - это просто особые случаи объектов и известны как простые старые структуры данных (PODS), в отличие от объектов, использующих объектно-ориентированные функции.

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

Ключи

Запись может иметь ноль или более ключей s. Ключ - это поле или набор полей в записи, которые служат идентификатором. Уникальный ключ часто называют первичным ключом или просто ключом записи . Например, файл сотрудника может содержать номер сотрудника, имя, отдел и зарплату. Номер сотрудника будет уникальным в организации и будет первичным ключом. В зависимости от носителя информации и файловой организации номер сотрудника может быть проиндексирован - он также сохраняется в отдельном файле, чтобы ускорить поиск. Код отдела не может быть уникальным; он также может быть проиндексирован, и в этом случае он будет считаться вторичным ключом или альтернативным ключом . Если он не проиндексирован, придется сканировать весь файл сотрудников, чтобы получить список всех сотрудников в определенном отделе. Поле зарплаты обычно не считается ключевым. Индексирование является одним из факторов, учитываемых при разработке файла.

История

Журнал переписи населения США 1880 года , показывающий табличные данные со строками данных, каждая из которых соответствует одному человеку.

Понятие записи можно проследить до различных типов таблиц и регистров, используемых в бухгалтерском учете с давних времен. Современное понятие записей в информатике, с полями четко определенного типа и размера, уже заложенная в 19 - механических калькуляторов века, таких как Бэббиджа «s Analytical Engine .

Перфокарта Холлерита (1895)

Исходным машиночитаемым носителем, используемым для данных (в отличие от контрольных), была перфокарта, используемая для записей в переписи населения США 1890 года : каждая перфокарта представляла собой отдельную запись. Сравните дневниковую запись 1880 года и перфокарту 1895 года. Записи были хорошо установлены в первой половине 20 века, когда большая часть обработки данных производилась с использованием перфокарт. Обычно каждая запись файла данных записывается на одну перфокарту с определенными столбцами, назначенными определенным полям. Как правило, запись была наименьшей единицей, которую можно было прочитать из внешнего хранилища (например, устройства чтения карт, ленты или диска).

В большинстве реализаций машинного языка и ранних языков ассемблера не было специального синтаксиса для записей, но эта концепция была доступна (и широко использовалась) за счет использования индексных регистров , косвенной адресации и самомодифицирующегося кода . Некоторые ранние компьютеры, такие как IBM 1620 , имели аппаратную поддержку для разграничения записей и полей, а также специальные инструкции для копирования таких записей.

Концепция записей и полей была центральной в некоторых ранних утилит для сортировки и табулирования файлов , таких как IBM Report Program Generator (RPG) .

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

Ранние языки, разработанные для числовых вычислений, такие как FORTRAN (до FORTRAN IV ) и Algol 60 , не поддерживали типы записей; но более поздние версии этих языков, такие как FORTRAN 77 и Algol 68 , добавляли их. В исходном языке программирования Lisp также не хватало записей (за исключением встроенной cons-ячейки ), но его S-выражения обеспечивали адекватный суррогат. Язык программирования Паскаль был одним из первых языков, полностью интегрировавших типы записей с другими базовыми типами в логически согласованную систему типов. Язык программирования PL / I предоставлен для записей в стиле COBOL. Язык программирования C изначально предоставлял концепцию записи как своего рода template ( struct), который можно было бы разместить поверх области памяти, а не как истинный тип данных записи. Последние были предоставлены в конечном итоге ( typedefдекларацией), но эти две концепции все еще различаются в языке. Большинство языков, разработанных после Паскаля (таких как Ада , Модула и Java ), также поддерживают записи.

Операции

  • Объявление нового типа записи, включая позицию, тип и (возможно) имя каждого поля;
  • Объявление переменных и значений как имеющих заданный тип записи;
  • Построение значения записи из заданных значений полей и (иногда) с заданными именами полей;
  • Выбор поля записи с явным именем;
  • Присвоение значения записи переменной записи;
  • Сравнение двух рекордов на равенство;
  • Вычисление стандартного хеш-значения для записи.

Выбор поля из значения записи дает значение.

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

В системах с подтипами записей операции со значениями типа записи также могут включать:

  • Добавление нового поля к записи, установка значения нового поля.
  • Удаление поля из записи.

В таких настройках конкретный тип записи подразумевает наличие определенного набора полей, но значения этого типа могут содержать дополнительные поля. Таким образом, запись с полями x , y и z будет принадлежать к типу записей с полями x и y , как и запись с полями x , y и r . Обоснование состоит в том, что передача записи ( x , y , z ) в функцию, которая ожидает запись ( x , y ) в качестве аргумента, должна работать, поскольку эта функция найдет все требуемые поля в записи. Многие способы практической реализации записей на языках программирования не позволили бы допустить такую ​​вариативность, но этот вопрос является центральной характеристикой типов записей в более теоретических контекстах.

Присвоение и сравнение

Большинство языков допускают назначение между записями, имеющими один и тот же тип записи (включая одинаковые типы полей и имена в одном порядке). Однако, в зависимости от языка, два типа данных записи, определенные отдельно, могут рассматриваться как разные типы, даже если они имеют точно такие же поля.

Некоторые языки могут также разрешать назначение между записями, поля которых имеют разные имена, сопоставляя каждое значение поля с соответствующей переменной поля по их положению в записи; так что, например, комплексное число с полями , называемых realи imagмогут быть отнесены к точке 2D переменной записи с полями Xи Y. В этом альтернативном варианте два операнда по-прежнему должны иметь одинаковую последовательность типов полей. Некоторые языки могут также требовать, чтобы соответствующие типы имели одинаковый размер и кодировку, чтобы вся запись могла быть назначена как неинтерпретируемая битовая строка . Другие языки могут быть более гибкими в этом отношении и требуют только, чтобы каждое поле значения могло быть юридически присвоено соответствующему полю переменной; так что, например, короткое целочисленное поле может быть присвоено длинному целочисленному полю или наоборот.

Другие языки (например, COBOL ) могут сопоставлять поля и значения по именам, а не по позициям.

Эти же возможности применимы к сравнению двух значений записи на равенство. Некоторые языки могут также допускать сравнение порядка ('<' и '>'), используя лексикографический порядок, основанный на сравнении отдельных полей.

PL / I допускает оба предыдущих типа присваивания, а также допускает структурные выражения , например, a = a+1;где «a» - это запись, или структура в терминологии PL / I.

Выбор распределительного поля в Алголе 68

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

Утверждение Паскаля "with"

В языке программирования Паскаль команда with R do Sбудет выполнять последовательность команд, Sкак если бы все поля записи Rбыли объявлены как переменные. Итак, вместо того, чтобы писать, Pt.X := 5; Pt.Y := Pt.X + 3можно было писать with Pt do begin X := 5; Y := X + 3 end.

Представление в памяти

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

Некоторые языки могут реализовать запись как массив адресов, указывающих на поля (и, возможно, на их имена и / или типы). Объекты в объектно-ориентированных языках часто реализуются довольно сложным образом, особенно в языках, допускающих множественное наследование классов .

Самоопределяющиеся записи

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

Примеры

Ниже показаны примеры определений записей:

  • PL / I:
      declare 1 date,
            2 year  fixed binary,
            2 month fixed binary,
            2 day   fixed binary;
  • Алгол 68:
  mode date = struct (int year, int month, int day);
  • C:
    struct date {
   int year;
   int month;
   int day;
};
  • Фортран :
    type :: date
   integer :: year, month, day
end type date
  • Перейти :
    type Date struct {
        year  int
        month time.Month
        day   int
}
  • Паскаль :
    type TDate = record
   Year: Integer;
   Month: 1..12;
   Day: 1..31;
end;
  • Ржавчина :
    struct Date {
    year: u32,
    month: u32,
    day: u32,
}
  • Swift :
    struct Date {
    year: Int,
    month: Int,
    day: Int,
}
  • Haskell :
    data Date = Date { year :: Integer
                 , month :: Integer
                 , day :: Integer
                 }
  • Юля :
    struct Date
    year::Int
    month::Int
    day::Int
end
  • Стандартный ML :
    type date = {year:int, month:int, day:int}
  • КОБОЛ :
           01 WS-DATE.
          02 WS-YEAR  PIC 9999.
          02 WS-MONTH PIC 99.
          02 WS-DAY   PIC 99.
  • Java 15 :
    record Date(int year, int month, int day) {
    // this is the minimum required    
}
  • Общий Лисп :
    (defstruct Date
  (year  0 :type integer)
  (month 1 :type (integer 1 12))
  (day   1 :type (integer 1 31)))

Смотрите также

использованная литература