Záznam (informatika)

Záznam nebo struktura (anglicky record, tuple, structure, struct nebo compound data) je v matematické informatice jedna z nejrozšířenějších a nejjednodušších složených datových struktur.^[1] Záznam se skládá z jiných hodnot, které mají zpravidla pevný počet a pořadí, a které se obvykle rozlišují jménem. Jednotlivé části záznamů se obvykle nazývají položky (anglicky fields), prvky (anglicky element) nebo členy (anglicky member).

Položky záznamu mohou mít na rozdíl od prvků pole různé datové typy, jsou rozlišeny jménem a jejich počet je pevný.

Typ záznam je libovolný datový typ, který popisuje takovéto hodnoty a proměnné (nejedná se o jediný konkrétní typ, ale o celou třídu typů). Většina moderních programovacích jazyků umožňuje definovat nové záznamové typy. Definice obvykle určuje identifikátory (jména nebo návěstí), pomocí kterých lze přistupovat k jednotlivým položkám, a datový typ každé položky.

Příklad

Například datum může být reprezentováno jako záznam obsahující číselnou položku rok, položku měsíc reprezentovanou jako řetězec a číselnou položku den v měsíci. Jiným příkladem může být záznam osoba, který může obsahovat položky jméno, příjem a funkce. Dalším příkladem je záznam kružnice obsahující položky Střed a Poloměr; v tomto případě může být Střed reprezentován záznamem Bod, který se skládá ze dvou položek pro souřadnice x a y.

Objekty v teorii typů

V teorii typů se složeným typům (bez pojmenovaných položek) obecně dává přednost kvůli jejich jednoduchosti, ale vlastní záznamové typy se studují v jazycích jako například System F-sub. Protože záznamy v teorii typů mohou kromě dat obsahovat položky typu funkce první třídy, mohou vyjadřovat mnoho vlastností objektově orientovaného programování.

Použití záznamů

Pro ukládání záznamů se mohou používat různá paměťová média, včetně hlavní paměti a vnějších pamětí, jako je magnetická páska nebo pevný disk. Záznamy jsou stěžejní komponentou většiny datových struktur, zvláště spojových seznamů. Mnoho počítačových souborů má strukturu pole logických záznamů, často sdružených do větších fyzických záznamů nebo bloků pro zvýšení efektivity.

Parametry podprogramů mohou být považovány za položky proměnné typu záznam a argumenty předávané funkci mohou být považovány za záznamovou hodnota, která je přiřazena této proměnné v okamžiku vyvolání funkce. Také v zásobníku volání, který se často používá pro implementaci volání procedur, je každý položka aktivační záznam nebo rámec volání obsahující parametry procedury a lokální proměnné, návratovou adresu a další interní položky.

Objekt v objektově orientovaných jazycích je v zásadě záznam, který kromě datových položek obsahuje procedury a funkce určené pro zpracování tohoto záznamu; objektové typy jsou vlastně rozšířením typu záznam. Ve většině objektově orientovaných jazyků jsou záznamy pouze speciálním případem objektů a často jsou nazývány (anglicky plain old data structures, PODSs) oproti objektům, které používají OO vlastnosti.

Záznam může být považován za počítačovou obdobu matematické uspořádané n-tice. V tomto duchu lze typ záznam považovat za analogii kartézského součinu dvou nebo více matematických množin nebo za implementaci abstraktního součinového typu v příslušném jazyce.

Historie

Koncept záznamů můžeme najít v různých typech tabulek a účetních knih používaných odedávna v účetnictví. Moderní pojem záznamu v matematické informatice, s položkami dobře definovaných typů a velikostí, byly používány už mechanickými kalkulátory v 19. století, jako byl například Analytický stroj Charlese Babbage.

Zpracování záznamů bylo dobře známé již v první polovině 20. století, kdy se většina strojového zpracování dat prováděla pomocí děrných štítků. Každý datový záznam v souboru byl obvykle reprezentován jedním děrným štítkem, na kterém byly vyhrazeny určité sloupce pro jednotlivé položky.

Většina implementací strojových jazyků a raných jazyků symbolických adres neměla speciální syntaxi pro záznamy, ale mohla s nimi pracovat pomocí indexových registrů, nepřímého adresování a samomodifikujícího se kódu. Některé staré počítače, jako například IBM 1620, měly hardwarovou podporu pro oddělování záznamů a položek a speciální instrukce pro kopírování takový záznamů.

Koncept záznamů a položek byl ústřední v některých raných programech pro třídění a tabulaci souborů, jako například RPG (Report Program Generator); první rozšířený programovací jazyk, který podporoval typ záznam, byl COBOL. Jeho prostředky pro práci se záznamy byly na svoji dobu docela pokročilé. Umožňují definovat vnořené záznamy s alfanumerickými, celočíselnými a reálnými položkami libovolné velikosti a přesnosti, a navíc položky, které hodnotu do nich přiřazenou automaticky formátují (například vložením značky měny, desetinné tečky a oddělovačů skupin číslic). V Cobolu ke každému souboru přísluší proměnná typu záznam, pomocí které se data čtou a zapisují. COBOL také poskytuje příkaz MOVE CORRESPONDING, který provádí přiřazení odpovídajících položek dvou záznamů podle jejich jmen.

Naopak první jazyky určené pro numerické výpočty, jako FORTRAN (až po FORTRAN IV) a Algol 60, typ záznam neměly; byl doplněn až do jejich pozdějších verzí (Fortran 77 a Algol 68). Také původní verze jazyka Lisp typ záznam neměla (s výjimkou vestavěných cons-buněk), ale jeho S-výrazy poskytovaly přiměřenou náhradu. Programovací jazyk PL/I vyvinutý firmou IBM poskytoval podobné prostředky pro práci se záznamy jako jazyk COBOL. Jedním z prvních jazyků, které plně integrovaly typ záznam s jinými základními typy do logicky konzistentního systému, byl programovací jazyk Pascal. Ve stejnou dobu vzniklý programovací jazyk C zpočátku zavedl koncept záznamu spíše jako určitou šablonu (struct), která strukturuje data v paměti, než plnohodnotný datový typ. Později zavedená deklarace typedef přiblížila záznam ostatním typům, ale v jazyce jsou stále přítomné oba koncepty. Většina jazyků navržených po Pascalu (jako například Ada, Modula a Java) již typ záznam podporuje.

Operace

Programovací jazyky, které podporují typ záznam obvykle poskytují následující operace:

Deklaraci nových typů záznam, včetně pořadí, typu a (případně) jména každé položky;
Deklaraci proměnných a hodnot typu záznam;
Konstrukce hodnot typu záznamu ze zadaných hodnot položek, někdy s uvedením jmen položek;
Výběr položky záznamu zadané jménem;
Přiřazení hodnoty záznamu do proměnné stejného typu;
Porovnání dvou záznamů na rovnost;
Výpočet standardní hašovací hodnoty záznamu.

Některé jazyky poskytují prostředky, které procházejí všechny položky záznamu nebo alespoň položky, které jsou odkazy. Tyto prostředky jsou potřebné na implementaci určitých služeb jako například debuggery, garbage collectory a pro serializaci a vyžadují určitou míru typového polymorfismu.

Výběrem položky z hodnoty záznamu dostaneme její hodnotu.

Přiřazení a porovnání

Většina jazyků umožňuje provádět přiřazení záznamů (zkopírování hodnot), pokud mají oba přesně stejnou strukturu nebo typ (tj. stejné typy a jména položek, ve stejném pořadí); v některých jazycích (Pascal) jsou dva stejně definované typy záznamu považovány za různé typy, dokonce i když mají přesně stejné položky.

Některé jazyky mohou také umožňovat přiřazení mezi záznamy, jejíž položky mají různá jména, přičemž korespondence mezi položkami je dána jejich umístěním v záznamu; například komplexní číslo s položkami nazvanými real a imag může být přiřazeno do proměnné bod v rovině typu záznam s položkami X a Y. V tomto případě je stále požadováno, aby oba operandy měly stejné pořadí typů položek. Některé jazyky mohou také vyžadovat, aby odpovídajícím typy měly také stejnou velikost a kódování, takže celý záznam může být přiřazen jako neinterpretovaný bitový řetězec. Jiné jazyky mohou být v tomto ohledu pružnější a vyžadovat pouze, aby hodnota každé položky mohla být přiřazena do odpovídající položky proměnné; například dvoubytové celé číslo může být přiřazeno do čtyřbytového (nebo i naopak).

Jiné jazyky (jako například COBOL) může při přiřazení párovat položky a hodnoty podle jejich jména místo pozice.

Stejný možnosti platí pro porovnání dvou záznamů na rovnost. Některé jazyky mohou také umožňovat porovnání na pořadí ('<'a '>'), které je založeno na lexikografickém uspořádání jednotlivých položek.

PL/I dovoluje oba výše uvedené typy přiřazení a také dovoluje strukturované výrazy, jako například a=a+1; kde "a" je záznam (v terminologii jazyka PL/I struktura).

Distributivní výběr položky v Algolu 68

Pokud Pts je pole záznamů s celočíselnými položkami X a Y v Algolu 68, je možné psát Pts.Y pro získání pole celých čísel sestávajících z položek Y všech prvků Pts. Díky tomu příkazy Pts[3].Y := 7 a Pts.Y[3] := 7 znamenají totéž.

Pascalovský příkaz with

V jazyce Pascal existuje konstrukce with R do S, která stanovuje, že identifikátory použité v příkazu S se přednostně považují za položky záznamu R; pokud záznam položku příslušného jména nemá, uplatní se obvyklá pravidla pro platnost identifikátoru. To dovoluje psát with Pt do begin X := 5; Y := X + 3 end místo Pt.X := 5; Pt.Y := Pt.X + 3.

Reprezentace v paměti

Přesná reprezentace záznamů v paměti závisí na programovacím jazyku. Jednotlivé položky se obvykle ukládají do paměti za sebou v tom pořadí, v jakém jsou deklarovány v typu záznam. V některých jazycích lze předepsat, že dvě nebo více položek může být ukládáno na stejné místo v paměti; tato vlastnost se často používá v systémovém programování pro přístup k jednotlivým bytům (případně i bitům) slova. Většina překladačů ale vkládá do záznamů prázdné položky, pro programátora obvykle neviditelné, aby další položka byla umístěna na adrese, která vyhovuje omezením procesoru, které často vyžadují, aby vícebytové hodnoty začínaly na sudé adrese nebo adrese dělitelné velikostí hodnoty; např. hodnoty v pohyblivé řádové čárce musí začínat na hranici slova.

Některé jazyky mohou implementovat záznam jako pole adres ukazujících na položky (případně na jejich jména nebo typy). Objekty v objektově orientovaných jazycích jsou často implementovány poměrně složitě, zvláště v jazycích, které umožňují vícenásobnou dědičnost.

Příklady definice záznamu

Následující příklady ukazují definice záznamu v různých programovacích jazycích:

PL/I:

  declare 1 datum,
            2 rok   picture '9999',
            2 mesic picture '99',
            2 den   picture '99';

C:

struct datum {
    int rok;
    int mesic;
    int den;
};

Pascal:

type
    typ_datum = record
        rok: integer;
        mesic: integer;
        den: integer;
    end;

var 
    datum: typ_datum;

Související články

Reference

V tomto článku byl použit překlad textu z článku Record (computer science) na anglické Wikipedii.

↑ Felleisen et al., How To Design Programs, MIT Press, 2001

[1] Felleisen et al., How To Design Programs, MIT Press, 2001

[1]