Lista (informatica)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 iulie 2020; verificările necesită 2 modificări .

În informatică , o listă ( listă engleză ) este un tip de date abstracte , care este un set ordonat de valori în care o anumită valoare poate apărea de mai multe ori. O instanță a unei liste este o implementare computerizată a conceptului matematic al unei secvențe finite . Instanțele de valori dintr-o listă sunt numite elemente ale listei ( articol, intrare sau element în limba engleză ); dacă valoarea apare de mai multe ori, fiecare apariție este considerată un element separat.

Termenul listă se referă, de asemenea, la câteva structuri de date specifice care sunt utilizate în implementarea listelor abstracte, în special a listelor legate .

Definiție

Folosind notația metodei de construcție orientată sintactic a lui C. Hoare , definiția unei liste poate fi scrisă după cum urmează:

Listă(A)=NIL+(A\time List(A))

prefix={\text{constructor}}

Lista(A)

head,tail={\text{selectori}}

Lista(A)

null,nonnull={\text{predicate}}

Lista(A)

NIL,nonNIL={\text{parts}}

Lista(A)

Prima linie a acestei definiții înseamnă că lista de elemente de tip (să spunem: „list over ”) este uniunea discriminată a listei goale și produsul cartezian al atomului de tip cu lista peste . Pentru a crea liste, se folosesc doi constructori (a doua linie a definiției), primul dintre care creează o listă goală, iar al doilea - una nevidă, respectiv. Este destul de clar că al doilea constructor primește un atom și o listă ca parametri ca intrare și returnează o listă, primul element al căruia este atomul original, iar restul sunt elementele listei originale. Adică, atomul este prefixat listei, ceea ce este motivul pentru un astfel de nume pentru constructor. Lista goală nu este un atom și, prin urmare, nu poate fi prefixată. Pe de altă parte, o listă goală este elementul nul pentru construirea listelor, deci orice listă conține o listă goală la sfârșit - construcția începe cu ea. $A$ $A$ $A$ $A$ $[]$

A treia linie definește selectoarele pentru listă, adică operațiunile de accesare a elementelor din listă. Selectorul ia o listă ca intrare și returnează primul element al acestei liste, adică tipul rezultatului este tipul . Acest selector nu poate primi o listă goală ca intrare - în acest caz, rezultatul operației este nedefinit. Selectorul returnează lista obținută din intrare ca urmare a tăierii capului acestuia (primul element). De asemenea, acest selector nu poate accepta o listă goală ca intrare, deoarece în acest caz rezultatul operației este nedefinit. Folosind aceste două operații, puteți obține orice element din listă. De exemplu, pentru a obține al treilea element al listei (dacă există unul), trebuie să aplicați selectorul de două ori succesiv și apoi să aplicați selectorul . Cu alte cuvinte, pentru a obține elementul din listă care se află în poziție (începând cu pentru primul element, așa cum este obișnuit în programare), trebuie să aplicați selectorul o dată , apoi să aplicați selectorul . $cap$ $A$ $coadă$ $coadă$ $cap$ $n$ $0$ $n$ $coadă$ $cap$

A patra linie a definiției descrie lista de predicate , adică funcții care returnează o valoare booleană în funcție de anumite condiții. Primul predicat returnează o valoare dacă lista dată este goală. Al doilea predicat funcționează invers. În cele din urmă, a cincea linie descrie părțile listei, care, după cum sa menționat deja, sunt listele goale și nevide. $Adevărat$

Proprietăți

Structura de date definită în acest fel are câteva proprietăți:

Mărimea listei este numărul de elemente din ea, excluzând ultimul element „null”, care este, prin definiție, o listă goală.
Tipul de elemente este același tip peste care este construită lista; toate elementele din listă trebuie să fie de acest tip. $A$
Sortat - lista poate fi sortată în funcție de anumite criterii de sortare (de exemplu, valori întregi crescător, dacă lista este formată din numere întregi).
Accesibilitate - Unele liste, în funcție de implementare, pot oferi programatorului selectoare pentru accesarea directă a elementului numerotat.
Comparabilitate - listele pot fi comparate între ele pentru corespondență, iar în funcție de implementare, operația de comparare a listelor poate folosi tehnologii diferite.

Listele sunt folosite pentru a stoca seturi de elemente de același tip. Astfel de elemente pot fi sortate pentru a fi utilizate în funcțiile de căutare sau funcții pentru inserarea rapidă de elemente noi într-o listă.

Liste în limbaje de programare

Limbi funcționale

Listele în limbaje funcționale sunt o structură fundamentală. Cele mai multe limbaje funcționale au facilități încorporate pentru lucrul cu liste, cum ar fi obținerea lungimii listei, capul (primul element al listei), coada (partea listei care urmează primul element), aplicarea unei funcții fiecărui element al listei ( Hartă ), plierea listei etc.

Limba Haskell Limba Lisp

Limbi imperative

Vezi și

Tipuri de date
Ininterpretabil	Pic Ciuguli octet qubit Trata Trăsătură Cuvânt
Numeric	Întreg punct fix punctul de plutire Raţional Complex Lung interval
Text	Simbolic Şir
Referinţă	Abordare Legătură Indicator Înveliș
Compozit	Tip de date algebrice ( generic ) Clasă Tip produs ( Scrie Tuplu structura ) Un obiect Consolidare ( etichetat ) Pereche comandată
abstract	matrice Listă Întoarce-te Grămadă Matrice asociativă (afișare, hartă ) Multe multiset Tip Grafic
Alte	Logic Inferior Superior Polimorfă Funcţional enumerabil Colectie Excepție Gen ( Metaclasă ) Monadă Semafor curgere gol
subiecte asemănătoare	Tip de date abstracte tip primitiv Structură de date Generic variabilă de tip Interfață Constructor (OOP) Constructor (FP) Constructor de tip Tip turnare Prototip Tip sistem

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă