Záznam (informatika)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 je hodnota složená z jiných hodnot, které mají obvykle pevný počet a pořadí, a které se typicky rozlišují jménem. Složky záznamů se obvykle nazývají položky (anglicky fields), prvky (anglicky element) nebo členy (anglicky member).

Záznamy se liší od polí tím, že obvykle mají pevný počet položek, každá položka má jméno a každá položky může být jiného typu.

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átor (jméno nebo návěstí), pomocí kterého lze k položce přistupovat, a datový typ každé položky.

Příklad[editovat | editovat zdroj]

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ů[editovat | editovat zdroj]

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ů[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 koncept byl dostupný (a široce používaný) pomocí používat indexových registrů, nepřímé adresování a samomodifikující se kód. 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 definici záznamu byly na svoji dobu docela pokročilé. COBOL umožňuje definovat vnořené záznamů s alfanumerickými, celočíselnými a racionálními položkami libovolné velikosti a přesnosti, stejně jako položky, které automaticky formátují libovolnou hodnotu, která je do nich přiřazena (například vložením značky měny, desetinné tečky a oddělovačů skupin číslic). Ke každému souboru přísluší proměnná typu záznam, pomocí které se data čtou nebo 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.

První jazyky určené pro numerické výpočty jako FORTRAN (až po FORTRAN IV) a Algol 60 podporu pro typ záznam neměly; do jejich pozdějších verzí jako Fortran 77 a Algol 68 byla doplněna. Původní verze jazyka Lisp také typ záznam nepodporoval (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. Programovací jazyk Pascal byl jedním z prvních jazyků, které plně integrovaly typ záznam s jinými základní typy do logicky konzistentního systému. Programovací jazyk C zpočátku zavedl koncept záznamu spíše jako určitou šablonu (struct), která může strukturovat data v paměti, než skutečný datový typ záznam. Později došlo k přiblížení záznamu ostatním typům (pomocí deklarace typedef), ale oba koncepty jsou v jazyce stále přítomné. Většina jazyků navržených po Pascalu (jako například Ada, Modula a Java) záznamy podporuje.

Operace[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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í). U některých jazyků (Pascal) mohou být 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Příkaz with R do S v jazyce Pascal provede posloupnost příkazů S jako kdyby všechny položky záznamu R byly deklarovány jako proměnné. 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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

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