Структура данных (информатика)

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

Наиболее часто используемые структуры: 

графы;

иерархические структуры (деревья);

таблицы.

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

Описание местности

Район состоит из 5 поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино.

Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Кошкино и Репкино.

Вопрос

Через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино.

Граф состоит из вершин, связанных линиями.

Направленная линия (со стрелкой) называется дугой.

Линия ненаправленная (без стрелки) называется ребром.

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.

Структуры данных: деревья, сети, графы, таблицы

к урокам информатики в 10 классе

Структуры данных

• упорядоченные данные, используемые в информационной модели.

Наиболее часто используемые структуры:

• графы;
• иерархические структуры (деревья);
• таблицы.

26.12.16

Граф

• это схема, которая наглядно отражает элементарный состав системы и структуру связей объектов системы.

Схема местности

Описание местности

Район состоит из 5 поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино.

Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Кошкино и Репкино.

Ответ

• Р – К – Б – М;
• Р – К – Д – Б – М.

Вопрос

Через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино.

Д

Б

К

М

Р

26.12.16

Состав графа

Граф состоит из вершин , связанных линиями.

Направленная линия (со стрелкой) называется дугой .

Линия ненаправленная (без стрелки) называется ребром .

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей .

ребро

дуга

В

петля

А

С

26.12.16

Разновидности графов

• Неориентированный – граф, вершины которого соединены ребрами.
• Ориентированный – граф, вершины которого соединены дугами.
• Взвешенный – граф, у которого вершины или рёбра ( дуги ) несут дополнительную информацию ( вес ).
• Сеть – граф, в котором возможно несколько различных путей перемещения по ребрам между некоторыми парами вершин. Характерно наличие замкнутых путей ( циклов ).
• Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

26.12.16

Неориентированный граф

(сеть)

Ориентированный граф

26.12.16

Рюрик

15

2

1

Игорь

20

18

14

4

3

Святослав

23

5

5

Владимир

Ярополк

Олег

Дерево

(иерархическая структура)

Взвешенный граф

26.12.16

Состав структуры «Дерево»

Корень – главная вершина дерева.

Предок – объект верхнего уровня.

Потомок – объект нижнего уровня.

Листья – вершины, не имеющие потомков.

Чемпион

Финалисты

Участники ½ финала

Участники ¼ финала

Первоначальные игроки

Олимпийская система спортивных соревнований

26.12.16

Иерархическая система хранения файлов

26.12.16

Иерархическая структура доменных адресов в Интернет

ИНТЕРНЕТ

корень

ft

edu

ru

com

домены 1 уровня

Доменные адреса:

www.pstu.ac.ru

hidra.psu.ru

mail.psu.ru

домены 2 уровня

psu

ac

домен 3 уровня

pstu

mail

hidra

имена компьютеров

www

26.12.16

Домашнее задание

• § 14 (1, 2), № 5-7, 10, 11.

26.12.16

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

по материалам ГИА (9класс)

Задача 1

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

26.12.16

Решение

Представим решение в виде графа:

O

A

B

C

1 стул

26.12.16

Решение

Представим решение в виде графа:

O

C

B

A

1 стул

B

C

C

B

A

A

2 стул

26.12.16

Решение

Представим решение в виде графа:

O

C

B

A

1 стул

C

B

A

A

B

C

2 стул

C

A

A

B

B

C

3 стул

26.12.16

Решение

Представим решение в виде графа:

O

C

B

A

1 стул

C

B

B

A

A

C

2 стул

3 стул

C

A

B

B

C

A

Выпишем все решения:

A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A.

26.12.16

Задача 2

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

26.12.16

Решение

3

7

5

1

1 цифра

1

1

7

7

3

1

3

3

5

5

7

5

2 цифра

3 цифра

3

7

7

3

3

3

3

7

3

7

5

7

7

1

5

5

5

5

5

1

1

1

1

1

Ответ: 24 числа .

26.12.16

Задача 3

Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E . На первом месте в цепочке стоит одна из бусин A, C, E . На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин C, D, E , не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?

26.12.16

Решение

E

C

A

E

E

1 бусина

D

C

B

A

E

D

C

B

2 бусина

3 бусина

D

D

C

D

C

D

C

E

D

E

D

E

D

C

E

D

C

E

C

Ответ: 19 цепочек .

26.12.16

Задача 4. Отыскание пути

На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?

2

3

1

5

6

4

7

9

8

26.12.16

2

1

3

Решение задачи

5

6

4

1

7

8

9

5

5

4

2

1 ярус

5

5

5

5

8

3

7

7

9

2 ярус

8

9

8

9

8

8

6

9

7

7

3 ярус

9

9

5

9

5

9

8

9

8

4 ярус

9

8

9

9

7

5 ярус

Кратчайший путь: 1 5 9. Его длинна 2.

Длина наиболее продолжительного пути 7: 1 2 3 6 5 7 8 9.

Число путей 14

9

8

6 ярус

7 ярус

9

Названия строк

Таблицы

• один из способов организации структуры данных.

Чаще всего используются прямоугольные таблицы.

Номер и заголовок таблицы

ячейки

ячейки

ячейки

Заголовки столбцов

Строки

Графы (столбцы)

26.12.16

Пример таблицы

Таблица 3.1. Погода

Дата

Осадки

28.11.2011

Температура, ° С

дождь

29.11.2011

снег

Давление, мм рт. ст.

30.11.2011

+ 4

без осадков

1.12.2011

+ 2

725

Влажность, %

744

без осадков

– 2

2.12.2011

92

снег

76

0

751

749

73

+ 1

92

750

93

Таблица «объект – свойство»

26.12.16

Пример таблицы

Таблица 3.2. Успеваемость

Ученик

Предметы

Аликин Петр

Русский

4

Алгебра

Ботов Иван

Химия

5

Волков Илья

3

5

5

Физика

Галкина Нина

3

4

5

3

История

4

4

5

3

4

Биология

4

5

5

3

5

3

4

5

5

4

Таблица «объект – объект»

26.12.16

Пример таблицы

Отображает качественную связь

Таблица 3.3. Сдаваемые предметы

Ученик

Предметы

Аликин Петр

Русский

1

Алгебра

Ботов Иван

Химия

Волков Илья

1

1

1

1

Физика

Галкина Нина

1

1

1

0

0

История

0

1

Биология

0

1

0

0

1

1

0

1

0

0

1

0

Таблица «объект – объект»: двоичная матрица

26.12.16

Приведение графа к табличной форме

Граф иерархической структуры

Российская федерация

Северо-Западный округ

Центральный округ

Уральский округ

Приволжский округ

Нижегородская область

Башкирия

Удмуртия

Пермский край

Березники

Пермь

Кунгур

Административная структура Российской Федерации

26.12.16

Приведение графа к табличной форме

Таблица 3.4. Административная структура Российской Федерации

Город

Регион

Березники

Округ

Пермская обл.

Екатеринбург

Свердловская обл.

Приволжский

Кунгур

Пермь

Уральский

Пермская обл.

Пермская обл.

Приволжский

Сергиев Посад

Приволжский

Московская обл.

Центральный

26.12.16

Табличное представление сетей

Описание местности

Район состоит из 5 поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино.

Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Кошкино и Репкино.

Таблица 3.5. Дорожная сеть

Поселок

Поселок

Бабкино

Бабкино

Дедкино

Дедкино

0

1

Кошкино

Кошкино

1

Репкино

1

Репкино

0

1

0

Мышкино

0

1

1

Мышкино

0

0

1

0

1

1

1

0

0

0

0

0

0

0

0

Матрица смежности

26.12.16

Табличное представление ориентированного графа

Таблица 3.6. Переливание крови

Начальная вершина

Конечная вершина

I

I

II

II

1

III

III

1

0

1

IV

IV

1

0

1

0

0

0

1

1

0

1

0

1

26.12.16

Зачем переводить в табличную форму?

Граф

Таблица

Наглядность

Компьютерная обработка

Теоретические модели

Компьютерное моделирование

26.12.16

Домашнее задание

• § 14, № 15-17.

26.12.16

Задания на информационное моделирование в ЕГЭ по информатике

Демоверсия 2012 года

26.12.16

26.12.16

Пример структуры данных

– модели предметной области

Прием в высшее учебное заведение

Предметная область

• работа приемной комиссии университета

Стадии процесса

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

26.12.16

I этап

Информационная модель предоставляет

• сведения о плане приема в университет: на каких факультетах, какие специальности открыты для поступления, сколько человек принимается на каждую специальность; сведения для абитуриентов и родителей: какие вступительные экзамены сдаются на каждом факультете, какие экзамены зачисляются по результатам ЕГЭ.
• сведения о плане приема в университет: на каких факультетах, какие специальности открыты для поступления, сколько человек принимается на каждую специальность;
• на каких факультетах, какие специальности открыты для поступления,
• сколько человек принимается на каждую специальность;
• сведения для абитуриентов и родителей: какие вступительные экзамены сдаются на каждом факультете, какие экзамены зачисляются по результатам ЕГЭ.
• какие вступительные экзамены сдаются на каждом факультете,
• какие экзамены зачисляются по результатам ЕГЭ.

26.12.16

II этап

Приемная комиссия

• получает и обрабатывает информацию, поступающую от абитуриентов, подающих заявления в университет.
• получает и обрабатывает информацию, поступающую от абитуриентов, подающих заявления в университет.

26.12.16

III этап

Приемная комиссия

• заносит в информационную базу результаты вступительных экзаменов (или ЕГЭ) для каждого поступающего.
• заносит в информационную базу результаты вступительных экзаменов (или ЕГЭ) для каждого поступающего.

26.12.16

IV этап

В информационную систему

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

26.12.16

Иерархия данных об университете и абитуриентах

Классический университет

Юридический факультет

Экономический факультет

Исторический факультет

Финансы и кредит

История

Политология

Бухгалтерский учет

Лядова

Кузин

Кротов

Анохин

Волков

Диркс

Яшина

Для каждого уровня создается таблица

26.12.16

Сведение данных в таблицы

Таблица 3.7. Факультеты

Название факультета

Экзамен 1

экономический

математика

исторический

Экзамен 2

юридический

история Отечества

география

Экзамен 3

русский язык

юридический

иностранный язык

…

сочинение

иностранный язык

…

обществознание

…

…

Таблица 3.8. Специальности

Название специальности

финансы и кредит

Название факультета

План приема

бухгалтерский учет

экономический

история

25

экономический

политология

исторический

40

юриспруденция

50

исторический

юридический

социальная работа

25

60

…

юридический

25

…

…

26.12.16

Описание структуры таблицы

• указать имя таблицы; перечислить заголовки столбцов.
• указать имя таблицы;
• перечислить заголовки столбцов.

АБИТУРИЕНТЫ

ФАКУЛЬТЕТЫ

Название факультета

Регистрационный номер

Фамилия

Экзамен 1

Имя

Экзамен 2

Экзамен 3

Отчество

Дата рождения

Город

Законченное учебное заведение

Название специальности

Производственный стаж

Медаль

Оценка за экзамен 1

Оценка за экзамен 2

Оценка за экзамен 3

Зачисление

СПЕЦИАЛЬНОСТИ

Название специальности

Название факультета

План приема

26.12.16

Структура данных: «Приемная кампания в университет»

ФАКУЛЬТЕТЫ

АБИТУРИЕНТЫ

Название факультета

Регистрационный номер

Экзамен 1

Фамилия

Имя

Экзамен 2

Отчество

Экзамен 3

Дата рождения

Город

Законченное учебное заведение

Название специальности

Производственный стаж

Медаль

Оценка за экзамен 1

Оценка за экзамен 2

Оценка за экзамен 3

Зачисление

СПЕЦИАЛЬНОСТИ

Название специальности

Название факультета

План приема

26.12.16

Домашнее задание

• § 15, № 2.

26.12.16