Презентация на тему - -Презентация по теме Структуры данных-. Лекция 4 Типы и структуры данных. Фундаментальные типы данных. Массивы, записи, множества

Лекция № 4 : Типы и структуры данных. Фундаментальные типы данных. Массивы, записи, множества.

Кафедра информационных технологий

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

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

Граф

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

Вопрос

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

Состав графа

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1

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

Решение

Решение

Решение

Решение

Задача 2

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

Решение

Задача 3

Решение

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

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

Таблицы

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

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

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

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

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

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

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

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

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

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

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

I этап

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

II этап

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

III этап

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

IV этап

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

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

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

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

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

Название	Лекция 4 Типы и структуры данных. Фундаментальные типы данных. Массивы, записи, множества
Дата	27.09.2022
Размер	453.81 Kb.
Формат файла
Имя файла	Презентация на тему - -Презентация по теме Структуры данных-.pptx
Тип	Лекция #701241

Дисциплина : Алгоритмы, структуры данных и программирование

Старший преподаватель: Джомартов Талгат Амирханович

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

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

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

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

Ответ

D – C – B – E;
D – C – A – B – E.

A

B

E

C

D

А

В

С

петля

ребро

дуга

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

A

B

E

C

D

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

(сеть)

II

I

III

IV

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

1

2

3

4

5

23

18

20

15

14

5

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

Дерево

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

Чемпион

Финалисты

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

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

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

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

ИНТЕРНЕТ

com

ru

edu

ft

ac

psu

pstu

hidra

mail

www

корень

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

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

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

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

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

www.pstu.ac.ru

hidra.psu.ru

mail.psu.ru

O

A

B

C

1 стул

O

A

B

C

1 стул

B

A

A

B

C

C

2 стул

O

A

B

C

1 стул

B

A

A

B

C

C

2 стул

C

C

B

B

A

A

3 стул

O

A

B

C

1 стул

B

A

A

B

C

C

2 стул

C

C

B

B

A

A

3 стул

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

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

3

1

5

7

3

5

3

3

5

5

7

7

7

1

1

1

1

1

1

1

1

5

5

5

5

5

5

1

7

7

7

7

7

7

3

3

3

3

3

3

1 цифра

2 цифра

3 цифра

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

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

C

A

E

B

C

D

E

1 бусина

2 бусина

3 бусина

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

E

E

A

B

C

D

C

D

E

C

D

E

C

D

E

D

E

D

E

C

D

C

D

C

D

1

2

3

4

5

6

7

8

9

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

2

3

4

5

6

7

8

9

1

1

2

5

4

8

9

6

9

5

8

9

8

9

7

9

5

8

9

8

9

7

9

5

8

9

8

9

7

1 ярус

2 ярус

3 ярус

4 ярус

5 ярус

6 ярус

7 ярус

7

5

9

5

3

5

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

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

Число путей 14

9

8

9

9

5

8

7

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

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

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

Строки

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

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

ячейки

ячейки

ячейки

Дата	Осадки	Температура, °С	Давление, мм рт. ст.	Влажность, %
28.11.2011	дождь	+ 4	725	92
29.11.2011	снег	+ 2	744	76
30.11.2011	без осадков	– 2	751	73
1.12.2011	без осадков	0	749	92
2.12.2011	снег	+ 1	750	93

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

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

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

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

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

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

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

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

Таблица 3.4.

A

B

E

C

D

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

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

Поселок	Поселок
	A	B	C	D	E
A	0	1	1	0	1
B	1	0	1	0	0
C	1	1	0	1	0
D	0	0	1	0	0
E	1	0	0	0	0

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

Район состоит из 5 поселков: А,B,C,D,E

Автомобильные дороги проложены между: A и B, A и C, B и C, B и E, C и D.

Граф

Наглядность

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

Таблица

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

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

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

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

сведения о плане приема в университет:

на каких факультетах, какие специальности открыты для поступления,
сколько человек принимается на каждую специальность;

сведения для абитуриентов и родителей:

какие вступительные экзамены сдаются на каждом факультете,
какие экзамены зачисляются по результатам ЕНТ.

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

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

вносятся окончательные результаты приема:

сведения для каждого абитуриента о том, поступил он в университет или нет.

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

Название факультета	Экзамен 1	Экзамен 2	Экзамен 3

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

Название специальности	Название факультета	План приема






…	…	…

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

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

ФАКУЛЬТЕТЫ

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

Экзамен 1

Экзамен 2

Экзамен 3

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

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

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

План приема

АБИТУРИЕНТЫ

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

Фамилия

Имя

Отчество

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

Город

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

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

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

Медаль

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

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

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

Зачисление

Студент

Предметы

Фило-софия

Язык PYTON

Язык СИ

ФАКУЛЬТЕТЫ

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

Экзамен 1

Экзамен 2

Экзамен 3

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

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

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

План приема

АБИТУРИЕНТЫ

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

Фамилия

Имя

Отчество

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

Город

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

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

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

Медаль

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

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

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

Зачисление