Уроки 25 - 26
§16. Списки и деревья
Содержание урока
Списки
Списки
Ключевые слова:
• список • дерево • иерархия • корень • лист • двоичное дерево
Список — это последовательность элементов, в которой важен порядок их расположения. Говорят, что список — это упорядоченная последовательность.
Как можно назвать неупорядоченную последовательность, в которой элементы не повторяются?
Для каждого элемента в списке, кроме первого, можно назвать предыдущий элемент; для каждого элемента, кроме последнего, — следующий (рис. 3.7).
Рис. 3.7
Для списка на рис. 3.7 назовите:
а) первый и последний элементы;
б) предыдущий элемент для «И»;
в) предыдущий элемент для «П»;
г) следующий элемент для «Г»;
д) следующий элемент для «Т».
Списки могут служить моделями для каких-то объектов. Например, список на рис. 3.7 — это модель слова «полиглот». Предложение можно представить в виде списка слов, абзац — в виде списка предложений, текст — в виде списка абзацев.
Используя дополнительные источники, выясните, от какого иностранного слова произошло слово «полиглот» и что оно обозначает.
Структура данных «список» есть во многих языках программирования. Списки обычно записывают в квадратных скобках, перечисляя через запятую их элементы по порядку, с первого до последнего. Например, так:
[’Amicus', ’Socrates', ’sed’, ’magis’, ’arnica’, ’veritas’]
Используя дополнительные источники, выясните значение известной фразы, которую задаёт этот список слов.
Используя дополнительные источники, выясните, название какого языка программирования образовано от слов «обработка списков».
В список можно добавлять новые элементы (до или после заданного элемента), можно также заменять и удалять элементы. Если применять эти операции к словам (спискам букв), то мы можем из одного слова получить другое. Например, слово КОРОНА можно получить из слова КРАН так:
КРАН → КОАН → КОРН → КОРО → КОРОН → КОРОНА
Назовите операции, которые были выполнены на каждом шаге.
Но это не единственный вариант такого преобразования.
Постарайтесь найти самый короткий вариант получения слова КОРОНА из слова КРАН.
Для того чтобы оценить «расстояние» между «словами» при таком преобразовании в виде числа, каждой операции преобразования присваивается своя «цена», например, так (табл. 3.7).
Таблица 3.7
| Операция | Цена |
| Замена гласной буквы на гласную или согласной на согласную | 1 |
| Замена гласной на согласную или согласной на гласную | 2 |
| Вставка или удаление буквы | 5 |
Как можно преобразовать слово СКАНЕР в слово ПРИНТЕР? Определите «стоимость» такого преобразования — «расстояние» между словами.
Подобная задача возникает при исследовании белков человека и животных, этим занимается наука биоинформатика. Белки — это цепочки аминокислот, каждая аминокислота обозначается латинской буквой. Срав нить два белка — это значит определить, как проще всего из одного белка получить другой.
Следующая страница 
Что такое дерево?
Cкачать материалы урока
