Как изобразить файловую структуру в виде дерева


Как нарисовать древовидную файловую структуру?

Я использую программу командной строки под названием "Точка" для рисования древовидных структур. Для этого создается текстовый файл, определяющий каждый файл или папку как уникальный узел и связи между ними (от родителя к потомку)

точка-это часть инструментария, программ, документация, онлайн на сайте: http://www.graphviz.org/pdf/dotguide.pdf

оно может вывести наружу чертеж как PDF, SVG, PNG, JPG, etc.

вот пример входного файла для программы "Точка" (имя файла "испытание.dot"):

digraph "My File Tree Drawing" { /* paper size in inches */ size="11.0,8.5"; /* locate label at top of drawing */ labelloc=t; label="My File Tree Drawing"; /* no directional arrow on connectors */ edge [dir=none]; /* nodes below are boxes (folders) */ node [shape=box]; folder1 [label="Folder 1 Name"]; folder2 [label="Folder 2 Name"]; folder3 [label="Folder 3 Name"]; /* nodes below are ellipses (files) */ node [shape=ellipse]; file1 [label="File 1 Name"]; file2 [label="File 2 Name"]; file3 [label="File 3 Name"]; file4 [label="File 4 Name"]; /* parent -> child, to draw the tree */ folder1 -> folder2; folder1 -> folder3; folder1 -> file1; folder2 -> file2; folder3 -> file3; folder3 -> file4; } 

сделать это в PDF-файл, выполните команду:

dot -T pdf test.dot > test.pdf 

эта программа делает отличные рисунки деревьев файлов (или любой структуры дерева / графика). Часть, которая требует наибольшей работы, делает ввод *.точечный файл. Обычно я пишу сценарий, чтобы просмотреть дерево файлов и вывести текстовый файл, отформатированный аналогично " test.точка" выше. Убедитесь, что все имена узлов уникальны (даже если имя метки / файла / папки совпадает). Еще одна полезная вещь знать, каждая строка в *.файл точка может прийти практически в любом порядке - если есть дубликаты, последний будет перекрывать предыдущие.

дополнительная "точка" документация доступна на http://www.graphviz.org/Documentation.php

Файлы и файловые структуры






§11. О файлах и файловых структурах

Основные темы параграфа:

- что такое файл;
- имя файла;
- логические диски;
- файловая структура диска;
- путь к файлу; полное имя файла;
- просмотр файловой структуры.

Изучаемые вопросы:

- Файл – информация, хранящаяся на внешнем носителе и объединенная общим именем.
- Файловая система как часть ОС.
- Имя файла, правила формирования имени.
- Понятие логического диска.
- Файловая структура диска, понятие каталога.
- Путь к файлу – координата местоположения файла на диске.
- Назначение таблицы размещения файлов


Что такое файл

Информация на внешних носителях хранится в виде файлов.

Файл — это именованная область внешней памяти, предназначенная для хранения информации.

Работа с файлами является очень важным видом работы на компьютере. В файлах хранится все: и программное обеспечение, и информация, необходимая для пользователя. С файлами, как с деловыми бумагами, постоянно приходится что-то делать: переписывать их с одного носителя на другой, уничтожать ненужные, создавать новые, разыскивать, переименовывать, раскладывать в том или другом порядке и пр.

Для прояснения смысла понятия файла удобно воспользоваться следующей аналогией: сам носитель информации (например, диск) подобен книге. Мы говорили о том, что книга — это внешняя память человека, а магнитный диск — внешняя память компьютера. Книга состоит из глав (рассказов, разделов), каждая из которых имеет название. Также и файлы имеют свои названия. Их называют именами файлов. В начале или в конце книги обычно присутствует оглавление — список названий глав. На диске тоже есть такой список-каталог, содержащий имена хранимых файлов.

Каталог можно вывести на экран, чтобы узнать, есть ли на данном диске нужный файл.

В каждом файле хранится отдельный информационный объект: документ, статья, числовой массив, программа и пр. Заключенная в файле информация становится активной, т. е. может быть обработана компьютером, только после того, как она будет загружена в оперативную память.

Все необходимые действия над файлами обеспечивает операционная система.

Чтобы найти нужный файл, пользователю должно быть известно:

а) какое имя у файла;
б) где хранится файл.

Имя файла

Вот пример имени файла *:

myprog.pas

*Последующие примеры ориентированы на правила, принятые в операционных системах фирмы Microsoft: MS-DOS и Windows. Также проиллюстрированы приложения ОС Linux.

Слева от точки находится собственно имя файла (myprog). Следующая за точкой часть имени (pas) называется расширением файла. Обычно в именах файлов употребляются латинские буквы и цифры. Кроме того, имя файла может и не иметь расширения. В операционной системе Microsoft Windows в именах файлов допускается использование русских букв; максимальная длина имени — 255 символов.

Расширение указывает, какого рода информация хранится в данном файле. Например, расширение txt обычно обозначает текстовый файл (содержит текст), расширение рсх — графический файл (содержит рисунок), zip или rаr — архивный файл (содержит архив — сжатую информацию), pas — программу на языке Паскаль.

Файлы, содержащие выполнимые компьютерные программы, имеют расширения ехе или соm. Например, программа игры «Тетрис» может храниться в файле tetris.exe. Инициализация программы происходит путем записи ее в оперативную память и запуска на исполнение.

Логические диски

На одном компьютере может быть несколько дисководов — устройств работы с дисками. Часто на персональном компьютере встроенный в системный блок жесткий диск большой емкости делят на разделы. Каждый из таких разделов называется логическим диском и ему присваивается однобуквенное имя (после которого ставится двоеточие) С:, D:, Е: и т. д. Имена А: и В: обычно относятся к сменным дискам малого объема — гибким дискам (дискетам). Их тоже можно рассматривать как имена логических дисков, каждый из которых полностью занимает реальный (физический) диск *. Следовательно, А:, В:, С:, D: — это всё имена логических дисков.

*На современных моделях ПК гибкие магнитные диски вышли из употребления.

Оптическому дисководу ставится в соответствие следующее по алфавиту имя после имени последнего раздела жесткого диска. Например, если на жестком диске есть разделы С: и D:, то имя Е: будет присвоено оптическому диску. А при подключении флеш-памяти в списке логических дисков появится еще диск F:.

Имя логического диска, содержащего файл, является первой «координатой», определяющей месторасположения файла.

Файловая структура диска

Современные операционные системы поддерживают многоуровневую организацию файлов на дисковых устройствах внешней памяти — иерархическую файловую структуру. Для облегчения понимания этого вопроса воспользуемся аналогией с традиционным «бумажным» способом хранения информации. В такой аналогии файл представляется как некоторый озаглавленный документ (текст, рисунок) на бумажных листах. Следующий элемент файловой структуры называется каталогом. Продолжая «бумажную» аналогию, каталог будем представлять как папку, в которую можно вложить множество документов, т. е. файлов. Каталог также получает собственное имя (представьте, что оно написано на обложке папки).

Каталог сам может входить в состав другого, внешнего по отношению к нему каталога. Это аналогично тому, как папка вкладывается в другую папку большего размера. Таким образом, каждый каталог может содержать внутри себя множество файлов и вложенных каталогов (их называют подкаталогами). Каталог самого верхнего уровня, который не вложен ни в какой другой каталог, называется корневым каталогом.

В операционной системе Windows для обозначения понятия «каталог» используется термин «папка».

Графическое изображение иерархической файловой структуры называется деревом.

На дереве корневой каталог обычно изображается символом \. На рисунке 2.10 имена каталогов записаны прописными буквами, а файлов — строчными. Здесь в корневом каталоге имеются две папки: IVANOV и PETROV и один файл fin.com. Папка IVANOV содержит в себе две вложенные папки PROGS и DATA. Папка DATA пустая; в папке PROGS имеются три файла и т. д.


Путь к файлу

А теперь представьте, что вам нужно найти определенный документ. Для этого в «бумажном» варианте надо знать ящик, в котором он находится, а также «путь» к документу внутри ящика: всю последовательность папок, которые нужно открыть, чтобы добраться до искомых бумаг.

Чтобы найти файл в компьютере, надо знать логический диск, на котором находится файл, и путь к файлу на диске, определяющий положение файла на этом диске. Путь к файлу — это последовательность, состоящая из имен каталогов, начиная от корневого и заканчивая тем, в котором непосредственно хранится файл. Вот всем знакомая сказочная аналогия понятия «путь к файлу»: «На дубе висит сундук, в сундуке — заяц, в зайце — утка, в утке — яйцо, в яйце — игла, на конце которой смерть Кощеева».

И наконец, необходимо знать имя файла. Последовательно записанные имя логического диска, путь к файлу и имя файла составляют полное имя файла.

Если представленная на рис. 2.10 файловая структура хранится на диске С:, то полные имена некоторых входящих в нее файлов в символике операционной системы Microsoft Windows выглядят так:


C:\fin.com
С: \IV ANOV\PROGS\prog 1. pas
С: \PETROV\DATA\task. dat


Просмотр файловой структуры

Операционная система предоставляет пользователю возможность просматривать на экране содержимое каталогов (папок).

Сведения о файловой структуре диска содержатся на этом же диске в виде таблицы размещения файлов. Используя файловую систему ОС, пользователь может последовательно просматривать на экране содержимое каталогов (папок), продвигаясь по дереву файловой структуры вниз или вверх.

На рисунке 2.11 показан пример отображения на экране компьютера дерева каталогов в ОС Windows.

В правом окне представлено содержимое папки ARCON. Это множество файлов различных типов. Отсюда, например, понятно, что полное имя первого в списке файла следующее:

E:\GAME\GAMES\ARCON\dos4gw.exe

Из таблицы можно получить дополнительную информацию о файлах. Например, файл dos4gw.exe имеет размер 254 556 байтов и был создан 31 мая 1994 года в 2 часа 00 минут.

Найдя в таком списке запись о нужном файле, применяя команды ОС, пользователь может выполнить с файлом различные действия: исполнить программу, содержащуюся в файле; удалить, переименовать, скопировать файл. Выполнять все эти операции вы научитесь на практическом занятии.

Коротко о главном

Файл — это именованная область внешней памяти компьютера.

Все необходимые действия над файлами обеспечивает операционная система.

Имя файла состоит из собственно имени и расширения. Расширение указывает на тип информации в файле (тип файла).

Иерархическая файловая структура — многоуровневая организация файлов на дисках.

Каталог — это поименованный перечень файлов и подкаталогов (вложенных каталогов). Каталог самого верхнего уровня называется корневым. Он не вложен ни в какие каталоги.

Полное имя файла состоит из имени логического диска, пути к файлу на диске и имени файла.

Вопросы и задания

1. Как называется операционная система, используемая в вашем компьютерном классе?

2. Сколько физических дисководов работает на ваших компьютерах? Сколько логических дисков находится на физических дисках и какие имена они имеют в операционной системе?

3. Каким правилам подчиняются имена файлов в вашей ОС?

4. Что такое путь к файлу на диске, полное имя файла?

5. Научитесь (под руководством учителя) просматривать на экране каталоги дисков на ваших компьютерах.

6. Научитесь инициализировать работу программ из программных файлов (типа ехе, соm).

7. Научитесь выполнять основные файловые операции в используемой ОС (копирование, перемещение, удаление, переименование файлов).

Электронное приложение к уроку


Вернуться к материалам урока
Презентации, плакаты, текстовые файлы Ресурсы ЕК ЦОР
Видео к уроку

Cкачать материалы урока


Файловая структура диска. Полное имя файла. Работа с файлами

Урок 18. Информатика 7 класс (ФГОС)

В данном видеоуроке рассказывается, что такое путь к файлу и его полное имя. Рассматриваются различные виды файловых структур и случаи их применения. Рассматриваются различные операции над файлами и способы их выполнения.


Конспект урока "Файловая структура диска. Полное имя файла. Работа с файлами"

Деревья






Практическая работа №10
«Схемы, графы и деревья» (задания 6 - 8).
Проверочная работа


Деревья

Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).

Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчиненности: директор — заместители директора – учителя — ученики.

Иерархическую структуру имеют системы, элементы которых связаны отношением «входит в состав».

На рисунке ниже изображен граф иерархической системы, представляющий состав прикладного программного обеспечения (ПО) компьютера.

Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порожденных вершин, называются листьями.

Древовидными являются схемы отношений «является разновидностью», используемые для наглядного представления классификации объектов:

Иерархию легко изобразить «лесенкой» — в виде многоуровневого списка. Объекты одного уровня иерархии располагаются на одном уровне в списке. Чем ниже уровень иерархии, тем правее находится соответствующий уровень списка:

• Рептилии

• Черепахи

• Крокодилы

• Клювоголовые

• Чешуйчатые

• Ящерицы

• Змеи

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

По иерархическому принципу организована система хранения файлов во внешней памяти.

Вы знаете, что по определенному признаку (принадлежность, назначение, содержимое, время создания и т. д.) файлы целесообразно объединять в папки. Папки, в свою очередь, могут вкладываться в другие папки и т. д. Главная (корневая) вершина этой иерархии соответствует определенному устройству внешней памяти.

Для того чтобы найти файл в иерархической файловой структуре, можно указать путь к файлу. В путь к файлу входят записываемые через разделитель «\» логическое имя диска и последовательность имен вложенных друг в друга папок, в последней из которых находится нужный файл.

Например, пути к файлам можно записать так:


 С:\Проекты\История\
 С:\Проекты\Информатика\
 С:\Рисунки\
 

Путь к файлу вместе с именем файла называют полным именем файла.

Примеры полных имен файлов:


 С:\Проекты\История\Эпоха Возрождения.doc
 С:\Проекты\Информатика\Интернет.doc
 С:\Проекты\Информатика\Компьютерные вирусы.doc
 С:\Рисунки\Закат.jpg
 С:\Рисунки\ Зима.ipg
 

Операционная система позволяет получить на экране компьютера изображение файловой системы в виде дерева:


Использование графов при решении задач

Графы удобно использовать при решении некоторых классов задач.

Задача 1

Сколькими способами можно рассадить в ряд на три стула трех учеников? Выписать все возможные случаи.

Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмем произвольную точку плоскости О.

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

Посадив на первый стул ученика А, на второй стул можно посадить ученика В или С. Если же на первый стул сядет ученик В, то на второй можно посадить А или С. А если на первый стул сядет С, то на второй можно будет посадить А или В. Это соответствует на схеме двум ветвям, исходящим из каждой вершины первого уровня:

Очевидно, что третий стул в каждом случае займет оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на из предыдущих ветвей.

Выпишем все пути от вершин первого уровня к вершинам третьего уровня: А-В-С, А-С-В, В-А-С, В-С-А, С-А-В, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов — 6.

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трех человек, на второй — одного из двух оставшихся, на третий — одного оставшегося: 3 * 2 * 1 = 6.

Задача 2

Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трех дорог старого ворона и вот какие советы от него услышал:


 1. иди сейчас по правой тропинке;
 2. на следующей развилке не выбирай правую тропинку;
 3. на третьей развилке не ходи по левой тропинке.
 

Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?

Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» ребрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией:


Коротко о главном

Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных линиями. Направленная линия называется дугой, ненаправленная — ребром. Линия, выходящая из некоторой вершины и входящая в нее же, называется петлей. Граф называется взвешенным, если его вершины или ребра (дуги) характеризуются некоторой дополнительной информацией — весом вершины или ребра (дуги).

Путь по вершинам и ребрам графа, включающий любое ребро графа не более одного раза, называется цепью. Цепь, начальная и конечная вершины которой совпадают, называется циклом. Разновидность графа, содержащая циклы, называется сетью.

Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).

Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель.

Вопросы и задания

1. Определите сказку, для которой следующий граф определяет отношения между персонажами.

(Курочка Ряба)

2. С разных сторон на холм поднимаются три тропинки и сходятся на вершине. Перечислите множество маршрутов, по которым можно подняться на холм и спуститься с него. Решите ту же задачу, если вверх и вниз надо идти по разным тропинкам.


 (Решение:
 а) Вверх можно подняться по 3-м тропинкам (3 варианта), спуститься также по 3-м (3 варианта). В итоге имеем: 3 • 3 = 9 вариантов.
 б) Вверх можно подняться по 3-м тропинкам (3 варианта), спуститься только по оставшимся 2-м (2 варианта). В итоге имеем: 3 • 2 = 6 вариантов)
 

3. Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5 и 7 при условии, что в записи числа не должно быть одинаковых цифр?


 (Решение:
 Число размещений 4-х элементов по 3: A = 4 • (4-1) • (4-2) • (4-3) = 4 • 3 • 3 • 1 = 24
 Ответ: 24 чисел)
 

4. Для составления цепочек используются бусины, помеченные буквами: А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква согласная, и любая согласная, если первая гласная.

На третьем месте – одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?


 (Решение:
 а) Первая бусинка А, тогда на втором месте может быть 3 варианта бусинок и на третьем месте тоже 3 варианта. Получаем 3 • 3 = 9 вариантов;
 б) Первая бусинка С, тогда на втором месте возможны 2 варианта (2 гласные) и на третьем тоже 2 варианта (Д, Е). Получаем 2 • 2 = 4 варианта;
 в) Первая бусинка Е, тогда на втором месте возможны 3 варианта (3 согласные), а на третьем место — 2 варианта (С, Д) Получаем 3 • 2 = 6 вариантов;
 В итоге получаем: 9 + 4 + 6 = 19 вариантов
 Ответ: 19 вариантов)
 
 

5. В центре дальнего леса находилась большая поляна — самое удивительное место в Стране малышей. На ней были три колодца: один — с газировкой, второй — с молоком, третий — с морсом. Когда-то три друга Фантик, Грибок и Дружок — построили на поляне домики и целое лето жили в лесу. Другим малышам нравилось приходить к ним в гости, попить молока, газировки или морса, погулять по лесным тропинкам. Но однажды бывшие друзья поссорились, и каждый из них решил проложить собственные дорожки к колодцам так, чтобы они не пересекались с дорожками соседей.

Подумайте, почему Знайка, к которому коротышки обратились за помощью, предложил им помириться.

(Задача не имеет решения. Нельзя провести тропинки так, чтобы они не пересекались).

Проверочная работа


Вариант 1

1. Решите задачу табличным способом.

В кафе встретились три друга: художник Черняев, рыбак Беленьков и таксист Рыжиков. «Замечательно, что у одного из нас белые, у другого черные, а у третьего рыжие волосы, но ни у кого цвет волос не соответствует фамилии», – заметил черноволосый. «Ты прав», – сказал Рыжиков. Какого цвета волосы у каждого из друзей.

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


 1. самая высокая работоспособность в понедельник;
 2. работоспособность в среду ниже работоспособности в четверг;
 3. работоспособность во вторник и четверг одинакова;
 4. самый непродуктивный день — суббота;
 5. работоспособность заметно снижается в пятницу;
 6. самая высокая работоспособность в среду;
 7. пик работоспособности – в пятницу;
 8. всю неделю работоспособность одинаковая.
 

3. Для выполнения задания постройте дерево.

Запишите все возможные двузначные числа, при записи которых используются цифры 2, 8 и 5.

4. Какое число получится в результате работы этой блок-схемы, если
А) вводится число 4.
Б) вводится число 5

Вариант 2

1. Решите задачу табличным способом.

Три ученицы – Липкина, Яблонева и Черемухина – посадили около школы три дерева: черемуху, яблоню и липу. Причем не одна из них не посадила то дерево, от которого произошла ее фамилия. Узнайте, какое дерево посадила каждая из девочек, если известно, что Липкина посадила не яблоню.

2. Пользуясь диаграммой работоспособности в течение рабочей недели, отметьте только ложные высказывания:


 1. самая высокая работоспособность в понедельник;
 2. работоспособность в среду ниже работоспособности в четверг;
 3. работоспособность во вторник и четверг одинакова;
 4. самый непродуктивный день — суббота;
 5. работоспособность заметно снижается в пятницу;
 6. самая высокая работоспособность в среду;
 7. пик работоспособности – в пятницу;
 8. всю неделю работоспособность одинаковая.
 

3. Для выполнения задания постройте дерево.

Запишите все возможные двузначные числа, при записи которых используются цифры 1, 7 и 4.

4. Какое число получится в результате работы этой блок-схемы, если
А) вводится число 6.
Б) вводится число 5



Практическая работа №10
«Схемы, графы и деревья» (задания 6 - 8)


Задание 6. Наши конкурсы

Работы участников школьных конкурсов по информационным технологиям записаны на диске, файловая структура которого имеет вид:

Средствами текстового процессора Word создайте соответствующую схему.

Сохраните результат работы в собственной папке в файле с именем Конкурсы.

Задание 7. Царство животных

1. Составьте схему но следующему описанию:

Близкие виды объединяются в один род. Например: ворона, ворон, галка и грач объединены в род Ворон. Близкие роды объединяются в семейства: род Ворон, род Сорока, род Сойка, род Кедровка объединены в семейство Вороновые. В свою очередь, близкие семейства объединяются в отряды. Так, семейство Синицевые, семейство Вороновые, семейство Ласточковые принадлежат отряду Воробьинообразные. Близкие отряды составляют класс. Так, отряд Воробьинообразные, отряд Совообразные, отряд Гусеобразные принадлежат к классу Птицы. Близкие классы объединены в типы. Так, класс Птицы, класс Амфибии, класс Млекопитающие входят в тип Хордовые. В настоящее время выделяют до 25 различных типов животных. Все они объединены в царство Животные.

2. Сохраните результат работы в собственной папке в файле с именем Животные.

Задание 8. Творческое задание

Придумайте сами пример объектов, отношения между которыми можно представить с помощью схемы. Создайте соответствующую схему в программе Microsoft Word. Сохраните результат работы в собственной папке в файле с именем Идея5.

Структура информации






Содержание урока

Зачем структурировать информацию?

Знакомые структуры данных

Иерархия (дерево)

Графы

Вопросы и задания

Задачи

Практическая работа № 1 «Оформление документа»

Практическая работа № 2 «Структуризация информации (таблица, списки)»

Практическая работа № 3 «Структуризация информации (деревья)»

Практическая работа № 4 «Графы»


Иерархия (дерево)

Линейных списков и таблиц иногда недостаточно для того, чтобы представить все связи между элементами. Например, в некоторой фирме есть директор, ему подчиняются главный инженер и главный бухгалтер, у каждого из них есть свои подчинённые. Если мы захотим нарисовать схему управления этой фирмы, она получится многоуровневой (рис. 1.11, а).

Такая структура, в которой одни элементы «подчиняются» другим, называется иерархией (от древнегреческого fepap%ta — священное правление). В информатике иерархическую структуру называют деревом. Дело в том, что, если перевернуть схему на рис. 1.11 вверх ногами, она становится похожа на дерево (точнее, на куст, см. рис. 1.11, б).

Рис. 1.11

Дерево состоит из узлов и связей между ними (они называются дугами). Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка-дуга), — это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев, — промежуточные.

Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.

Используются также понятия предок и потомок. Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.

В дереве на рис. 1.12 родитель узла Е — это узел В, а предки узла Е — это узлы А я В, для которых узел Е — потомок. Потомками узла А (корня) являются все остальные узлы.

Рис. 1.12

Типичный пример иерархии — различные классификации (животных, растений, минералов, химических соединений). Например, отряд Хищные делится на два подотряда: Псообразные и Кошкообразные. В каждом из них выделяют несколько семейств (рис. 1.13).

Рис. 1.13

Конечно, на рис. 1.13 показаны не все семейства, остальные обозначены многоточиями.

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

Глава 1. Псообразные

1.1. Псовые

1.2. Енотовые

1.3. Медвежьи

...

Глава 2. Кошкоообразные

2.1. Кошачьи

2.2. Гиеновые

2.3. Мангустовые

...

Работая с файлами и папками, мы тоже встречаемся с иерархией: классическая файловая система имеет древовидную структуру 1. Вход в папку — это переход на следующий (более низкий) уровень иерархии (рис. 1.14).


1 В современных файловых системах (NTFS, ext3) файл может «принад¬лежать» нескольким каталогам одновременно. При этом древовидная структура, строго говоря, нарушается.


Рис. 1.14

Алгоритм вычисления арифметического выражения тоже может быть представлен в виде дерева (рис. 1.15).

(а + 3) * 5 - 2 * b

Рис. 1.15

Здесь листья — это числа и переменные, тогда как корень и промежуточные вершины — знаки операций. Вычисления идут «снизу вверх», от листьев — к корню. Показанное дерево можно записать так:

(-(*(+ (а,3),5),*(2,b)))

Самое интересное, что скобки здесь необязательны; если их убрать, то выражение всё равно может быть однозначно вычислено:

* + а35 * 2b

Такая запись, которая называется префиксной (операция записывается перед данными), просматривается с конца. Как только встретится знак операции, эта операция выполняется с двумя значениями, записанными справа. В рассмотренном выражении сначала выполняется умножение:

- * + а 3 5 (2*b)

затем — сложение:

- * (а + 3) 5 (2 * b)

и ещё одно умножение:

- (а + 3) * 5 (2*b)

и наконец, вычитание:

(а + 3) * 5 - (2 * b)

Для получения префиксной записи мы обходили все узлы дерева в порядке «корень — левое поддерево — правое поддерево». Действительно, сначала записана метка корня («-»), затем все метки левого поддерева, а затем — все метки правого поддерева. Для поддеревьев используется тот же порядок обхода. Если же обойти дерево в порядке «левое поддерево — правое поддерево — корень», получается постфиксная форма (операция после данных). Например, рассмотренное выше выражение может быть записано в виде

аЗ+5*2b*-

Для вычисления такого выражения скобки также не нужны, и это очень удобно для автоматических расчётов. Когда программа на языке программирования высокого уровня переводится в машинные коды, часто все выражения записываются в бесскобочной постфиксной форме и именно так и вычисляются. Постфиксная форма для компьютера удобнее, чем префиксная, потому что, когда программа доходит до знака операции, все данные для выполнения этой операции уже готовы.

Следующая страница Графы

Cкачать материалы урока

"Файлы и файловые структуры"

Была в сети 25.10.2020 21:24

Гусейнова Асият Магомедовна

учитель информатики

1 год

c # - как использовать рекурсию для синтаксического анализа текста в древовидной структуре?

Переполнение стека
  1. Около
  2. Товары
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технолог
.

Представление дерева с использованием списка в Python

Переполнение стека
  1. Около
  2. Товары
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
.

java - Структура данных для представления дерева принятия решений

Переполнение стека
  1. Около
  2. Товары
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
  4. Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
.

структур данных - представление дерева в Clojure

Переполнение стека
  1. Около
  2. Товары
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии
.

Как представить двухсторонние отношения в дереве Firebase JSON?

Переполнение стека
  1. Около
  2. Товары
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд
.

массивов - Кучи против двоичных деревьев - Как реализовать?

Переполнение стека
  1. Около
  2. Товары
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
  4. Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
.

Смотрите также

Сайт о Бане - проект, посвященный строительству, эксплуатации и уходу за русской баней. Большой сборник статей, который может быть полезен любому любителю бани

Содержание, карта сайта.