Cunoaște-Intuit, liste de curs

Lista - o structură de date. definite după cum urmează:

1. listă goală ([]) este o listă;
2. formă structura [H | T] este o listă, în cazul în care H - primul element (sau mai multe prime elemente ale listei separate prin virgulă.), și T - listă. constând din elementele rămase ale listei originale.

H se numește capul listei. și T - coada listei. Rețineți că alegerea variabilelor pentru a indica capul și coada nu este intamplatoare. În cap engleză - Cap. și coada - Coada.

De fapt, operațiunea „|“ vă permite să împartă lista în cap și coadă (în Lisp au operațiuni similare auto și CDR) sau, dimpotrivă, de a atribui obiect (e) de la partea de sus a listei (contra în Lisp).

Această definiție vă permite să organizați liste de procesare recursive, schimbul de o listă de cap și coadă care nu este gol. Coada, la rândul său. Este, de asemenea, o listă care conține mai puține elemente decât lista originală. În cazul în care coada nu este gol, de asemenea, poate fi împărțit în cap și coadă. Și așa până atunci, până când vom ajunge la lista goală, care nu are un cap.

De exemplu, lista [1, 2, 3] este un element cap 1, iar lista [2, 3] - coadă, adică [1, 2, 3] = [1 | [2, 3]].

Rețineți că coada listei [2, 3]. la rândul său. poate fi reprezentat ca coada capului 2 și [3]. și lista [3] poate fi văzut sub forma unui cap și o coadă 3 []. O listă goală nu va fi divizat în continuare.

Ca rezultat, constatăm că lista [1, 2, 3] este echivalentă cu lista [1 | [2, 3]]. care, la rândul său. echivalent cu lista [1 | [2 | [3]]]. Ultima comparabilă cu lista [1 | [2 | [3 | []]]].

Aceeași listă primele două elemente pot fi separate și coada treilea element [1,2 | [3]]. În cele din urmă, varianta a partiției pe capul primelor trei elemente, și goale coada: [1, 2, 3 | []].

Pentru a organiza lista de prelucrare, în conformitate cu definiția recursivă de mai sus, este suficient să se stabilească oferta (de drept sau de fapt care determină ce să facă cu o listă goală), care va fi baza recursivitatii și regula recursiv este ordinea tranziției de la prelucrarea tuturor listă care nu este gol la prelucrarea cozii sale. Uneori, baza de recursie nu sunt înregistrate goale, dar pentru o listă de una sau două elemente.

Ca un rezumat pentru raționamentul nostru, vom scrie din nou definiția listei în Backus-Nauer:

Verbal poate fi scris ca o listă sau un martor, sau reprezentate sub forma unor elemente de transfer, înregistrate, separate prin virgulă, sau constă dintr-un cap și o coadă, care, la rândul său. Este, de asemenea, o listă.