Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 64152
Модуль Forms 63862
ТЕХНОЛОГИИ ДОСТ... 60743
Пример работы с... 60702
Имитационное мо... 56266
Реклама
Сейчас на сайте
Гостей: 1
На сайте нет зарегистрированных пользователей

Пользователей: 13,080
новичок: setan
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование работы аэропорта на GPSS + Пояснительная записка
База данных электронного документооборота на Delphi + бд Intebase
Расчет размера дохода на одного человека в Turbo Pascal

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
3.2. Списки


Список - довольно широко используемая структура данных в области числового программирования. Список -это упорядоченная последовательность элементов, которая может иметь произвольную длину. Признак упорядоченный указывает на то, что порядок элементов в последовательности является существенным. Элементами списка могут быть любые термы – константы, переменные, структуры, которые включают, конечно, и другие списки. Указанные свойства очень полезны в ситуации, когда мы не в состоянии заранее предсказать, насколько большим должен быть список и какую информацию он будет содержать. Более того, списки позволяют представить практически любой тип структуры, который может потребоваться при символьных вычислениях. Списки широко используются для представления деревьев синтаксического разбора, грамматик, карт городов, программ для ЭВМ и математических объектов, таких как графы, формулы и функции. Существует язык программирования – Лисп, в котором единственными доступными структурами данных являются константа и список. Однако в Прологе список – это просто один из частных видов структуры.
Списки могут быть представлены как специального вида дерево. Список – это любой пустой список, не содержащий ни одного элемента, либо структура, имеющая две компоненты: голову и хвост списка. Конец списка обычно представляют как хвост, который является пустым списком. Пустой список записывают как [] – открывающая квадратная скобка, за которой следует закрывающая квадратная скобка. Голова и хвост списка являются компонентами функтора, обозначаемого точкой '.'. Так, список, состоящий из одного элемента ' а ' есть .(а, []) , а его представление в виде дерева имеет вид
Аналогично список, состоящий из атомов a , b и с , мог бы быть записан как .(а,.(b,.(с,[]))) , что изображается следующим образом:
Иногда функтор точка ('.') определяется как оператор, так что допустимо для Пролога два последних списка записать как а.[] и а.(b.(с.[]))) . Второй список можно было бы записать просто как а.b.с.[] , так как функтор точка – правоассоциативный оператор. Списки являются упорядоченными последовательностями элементов, так что список а.b отличается от списка b.а .
Некоторые любят записывать древовидные диаграммы списков в виде дерева, «растущего» слева направо, ветви которого направлены вниз. Приведенный выше список, представленный диаграммой в виде такой «виноградной лозы» выглядит так:
В этой диаграмме компонента функтора '.', соответствующая голове списка, «свисает» вниз, а компонента, соответствующая хвосту списка, «растет» вправо. Конец списка четко выделен тем, что последняя компонента – хвост списка – является пустым списком. Главное преимущество использования диаграммы для представления списка заключается в том, что она может быть записана справа налево на листе бумаги.
«Виноградная» диаграмма может оказаться удобной для записи списков на бумаге, когда нам необходимо видеть структуру списка, но в программах на Прологе для записи списков такие диаграммы не используются. Так как запись сложных списков с помощью функтора '.' часто оказывается неудобной, то в Прологе предусмотрена другая синтаксическая форма, которая может быть использована для записи списков в программе. Это так называемая скобочная форма записи списка. Она представляет собой заключенную в квадратные скобки последовательность элементов списка, разделенных запятыми. Например, упоминавшиеся выше списки могут быть записаны в скобочной форме в виде [а] и [а, b, с] . Списки могут содержать другие списки или переменные. Например, в Прологе допустимы следующие списки:
[]
[конкретный, человек, [любит, ловить, рыбу]]
[а, V1, b, [X, Y]]



Переменные, входящие в списки, ничем не отличаются от переменных в любой другой структуре. Они в любой момент могут быть конкретизированы, так что умелое использование переменных может обеспечить образование «пустых мест» в списке, которые впоследствии могут быть заполнены данными.
Чтобы продемонстрировать структуру списков, содержащих в качестве элементов другие списки, приведем «виноградную» диаграмму для последнего из рассмотренных списков:
Из приведенной диаграммы ясно видно, что каждый ее горизонтальный уровень является списком, состоящим из некоторого числа элементов. Верхний уровень на приведенной диаграмме представляет список, содержащий четыре элемента, один из которых сам является списком. Второй уровень, содержащий два элемента, представляет четвертый элемент списка верхнего уровня. Работа со списками основана на расщеплении их наголову и хвост списка. Голова списка – это первый аргумент функтора '.', который используется для конструирования списка. Хвост списка – это второй аргумент функтора '.'. В случае когда для записи списка используется скобочная форма записи, головой списка является первый его элемент. Хвост списка представляет список, состоящий из всех элементов исходного списка, за исключением первого его элемента. Следующие примеры демонстрируют расщепление списков на голову и хвост:

Список Голова Хвост
[а, b, с] а [b, с]
[а,] а []
[]
[[эта, кошка], сидела] [эта, кошка] [сидела]
[эта, [кошка, сидела]] эта [кошка, сидела]]
[эта, [кошка, села], на пол] эта [кошка, села], на пол]
[X+Y, х + y] X + Y [x + y]

Заметим, что пустой список не имеет ни головы, ни хвоста. В последнем примере оператор ± используется как функтор для структур +(Х, Y) и +(х,у) .
Так как операция расщепления списка на голову и хвост очень широко используется, то в Прологе введена специальная форма для представления списка с головой X и хвостом Y . Это записывается как [X|Y] , где для разделения X и Y используется вертикальная черта. При конкретизации структуры подобного вида X сопоставляется с головой списка, a Y – с хвостом списка, как это показано в следующем примере:
p([1, 2, 3]).
p([эта, кошка, сидела, [на, этой, подстилке]]).
?- p([X|Y]).
X = 1 Y=[2,3] ;
X=эта Y=[кошка, сидела, [на, этой, подстилке]]
?- p([_,_,_,[_|X]]).
X=[этой, подстилке]



Ниже приведено еще несколько примеров с использованием различных синтаксических возможностей записи списков, показывающих, каким образом производится сопоставление списков. В этих примерах делается попытка сопоставить два заданных списка, конкретизируя переменные, если это возможно.

Список 1 Список 2 Конкретизация
[X, Y, Z] [джону,нравится,рыба] X=джону Y= нравится Z = рыба
[кошка] [X| Y] X= кошка
[X, Y | Z] [мэри,нравится,вино] X = мэри  Y = нравится Z = [вино]
[[этот, Y]|Z] [[X, заяц], [находится, здесь]]  X = этот Y = заяц Z = [[находится_ здесь]]
[X, Y|Z, W] (синтаксически некорректная конструкция списка) 
[золотистый | T] [золотистый, норфолк] T= [норфолк]
[лошадь, X] [белая, лошадь] (сопоставление невозможно)
[белая | Q] [P | лошадь] P = белая Q = лошадь

Как видно из последнего примера, используя скобочную форму записи списков, можно создавать структуры, похожие на списки, но не заканчивающиеся пустым списком. Одна из таких структур, [белая|лошадь], обозначает структуру, головой которой является белая, а хвостом – лошадь. Константа лошадь не является ни списком, ни пустым списком, и, как мы увидим далее, обработка таких структур требует большой осторожности, когда они используются в качестве хвоста списка.
Существует еще одна область применения списков – это представление строк литер. Иногда возникает необходимость в использовании строк литер для печати или ввода текста. Если строка литер заключена в двойные кавычки, то эта строка представляется как список кодов, соответствующих литерам строки. Для кодировки литер используется код ASCII, который обсуждался в разд. 2.2. Например, строка "system" преобразуется в Прологе в следующий список: [115, 121, 115 , 116, 101, 109].

http://www.ecorezina.ru/information/articles/utilizaciya.aspx и дальнейшая переработка в резиновую крошку.
Опубликовал Kest July 09 2009 16:07:54 · 0 Комментариев · 10914 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Х. М. Дейтел, П. ...
ShadelLabel
Шифрование по алг...
Pro-Download Sys...
Пятнашки и крести...
CaptionButton
Панель "Случайное...
EMS QuickExport S...
Добавление к ссы...
Delphi на примерах
С# для профессион...
DeleteEdit
C# в кратком изло...
Delphi. Учимся на...
FreeNet
Клавиатурный трен...
С/C++ Программиро...
База для Allsubmi...
Разработка интерн...
SODA [Исходник на...

Топ загрузок
Приложение Клие... 100455
Delphi 7 Enterp... 86121
Converter AMR<-... 20071
GPSS World Stud... 12522
Borland C++Buil... 11608
Borland Delphi ... 8519
Turbo Pascal fo... 7035
Visual Studio 2... 4992
Калькулятор [Ис... 4744
FreeSMS v1.3.1 3539
Случайные статьи
Что такое Internet...
Про лудоманию
Инвариант на второ...
4.4. Проблемы, св...
Глава 17. Страт...
Слежение
Методы поиска реше...
ВЗЛОМ NT
Манипуляторы
Программирование: ...
Есть ли польза от ...
Сохранение и загру...
Почему многих надо...
Коттеджные поселки...
Топология соединен...
Функция TextWidth ...
Строка -> список
Создание поставщик...
Термин «инфографика»
RESET (СБРОСИТЬ)
Большой радиатор и...
Понятие источника ...
Для добавления кол...
Схема двухступенча...
Получая пакеты, бр...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?