Знайте, Intuit, лекции списъци

списък - структурата на данните. определя, както следва:

1. празен списък ([]) е даден списък;
2. структура форма [Н | Т] е даден списък, ако Н - първи елемент (или няколко първите елементи на списъка разделени със запетая.), и Т - списък. състояща се от останалите елементи от първоначалния списък.

Н се нарича списък главата. и Т - опашката на списъка. Имайте предвид, че изборът на променливи, които да показват, главата и опашката не е случайно. На английски език главата - началник. и опашката - опашката.

Всъщност, операцията "|" позволява да се раздели на списъка в главата и опашката (в Lisp има подобни операции кола и ДРК), или, напротив, приписани на обекта (ите) на върха на списъка (минуси в Lisp).

Това определение позволява да организирате рекурсивни списъци за обработка, споделяне не е празен списък глава и опашка а. Опашката, от своя страна. Той е и списък, съдържащ по-малко елементи, отколкото в първоначалния списък. Ако опашката не е празна, тя също може да бъде разделен на глава и опашка. И така, до тогава, докато не стигнем до празен списък, който не разполага с глава.

Например, списъкът [1, 2, 3] е глава елемент 1 и списъка [2, 3] - опашка, т.е. [1, 2, 3] = [1 | [2, 3]].

Имайте предвид, че опашката на списъка [2, 3]. от своя страна. могат да бъдат представени като глава 2 и опашката [3]. и списъка [3] може да се види формата на главата и опашката 3 []. Един празен списък няма да бъде разделена.

В резултат на това, ние откриваме, че списъкът [1, 2, 3] се равнява на списъка [1 | [2, 3]]. който от своя страна. еквивалентни на списъка [1 | [2 | [3]]]. Последно сравнима със списъка [1 | [2 | [3 | []]]].

Същата списък на първите два елемента могат да бъдат разделени и опашката на третия елемент [1,2 | [3]]. И най-накрая, вариантът на дяла на главата на първите три позиции, и празен опашката: [1, 2, 3 | []].

За организиране на списъка на преработка, в съответствие с по-горе рекурсивно определение, е достатъчно да се определи офертата (на закона или факт, който определя какво да прави с празен списък), което ще бъде на базата на рекурсия и рекурсивни правило е от порядъка на прехода от обработката на всички не-празен списък на обработката на опашката си. Понякога основа рекурсия не записва празен, но за една или две елемент списък.

Като обобщение на нашите разсъждения, пишем отново определението на списъка в Бакъс-Nauer:

Вербално може да бъде записано като списък или празен, или представени под формата на трансфер елементи, записани, разделени със запетая, или се състои от глава и опашка, която на свой ред. Той също е в списъка.