Похожие презентации:
Лекция_6__Структуры_данных_-_Слайды
1.
Toraighyrov UniversityОСЕННИЙ СЕМЕСТР 2024
ЛЕКЦИЯ
Структуры данных
6
2.
DISCORDhttps://discord.gg/JNBX2Zwksn
3.
4.
Структуры данныхСпособ организации информации в памяти
5.
Абстрактные структуры данныхКонцептуальная модель того, как хранят и организуют данные
6.
Очередьабстрактный тип данных, который организует элементы в
последовательности FIFO
7.
FIFOFirst in — First out
Первым вошёл, первым вышел.
Очередь
абстрактный тип данных, который организует элементы в
последовательности FIFO
8.
9.
10.
11.
12.
13.
14.
Стекабстрактный тип данных, доступ к элементам которых организован по
принципу LIFO
15.
LIFOLast in — First out
Последний вошёл, первым вышел.
Стек
абстрактный тип данных, доступ к элементам которых организован по
принципу LIFO
16.
17.
18.
19.
20.
21.
12
3
22.
12
3
23.
12
3
24.
1o
\0
,
2
3
h
e
l
l
w
o
r
l
d
25.
12
3
26.
11
2
3
27.
12
1
2
3
28.
12
3
1
2
3
29.
12
3
1
2
3
4
30.
12
3
4
31.
Связный списокдинамическая структура данных, в которой элементы хранятся в отдельных
блоках памяти, называемых узлами
32.
10x123
33.
10x123
2
0x456
34.
10x123
2
0x456
3
0x789
35.
10x123
2
0x456
3
0x789
36.
10x123
0x456
2
0x456
3
0x789
37.
10x123
0x456
2
0x456
3
0x789
38.
10x123
0x456
2
0x456
0x789
3
0x789
39.
10x123
0x456
2
0x456
0x789
3
0x789
0x0
40.
10x123
0x456
2
0x456
0x789
3
0x789
NULL
41.
10x123
0x456
2
0x456
0x123
0x789
3
0x789
NULL
42.
12
3
43.
10x123
2
0x456
3
0x789
44.
45.
46.
47.
48.
49.
50.
51.
node *list;52.
node *list;list
53.
node *list = NULL;list
54.
node *list = NULL;list
55.
node *n = malloc(sizeof(node));list
56.
node *n = malloc(sizeof(node));list
n
57.
node *n = malloc(sizeof(node));list
number
n
next
58.
node *n = malloc(sizeof(node));list
number
n
next
59.
(*n).number = 1;list
number
n
next
60.
(*n).number = 1;list
1
n
number
next
61.
62.
63.
64.
65.
66.
67.
68.
n->number = 1;list
1
n
number
next
69.
n->next = NULL;list
1
n
number
next
70.
n->next = NULL;list
1
n
number
next
71.
list = n;list
1
n
number
next
72.
list = n;list
1
n
number
next
73.
list1
74.
node *n = malloc(sizeof(node));list
1
75.
node *n = malloc(sizeof(node));list
1
n
76.
node *n = malloc(sizeof(node));list
1
n
77.
node *n = malloc(sizeof(node));list
1
n
78.
n->number = 2;list
1
n
79.
n->number = 2;list
2
1
n
80.
n->next = NULL;list
2
1
n
81.
n->next = NULL;list
2
1
n
82.
list2
1
n
83.
list = n;list
2
1
n
84.
list = n;list
2
1
n
85.
list = n;list
2
1
n
86.
list2
1
n
87.
n->next = list;list
2
1
n
88.
n->next = list;list
2
1
n
89.
list = n;list
2
1
n
90.
list = n;list
2
1
n
91.
list2
1
92.
2list
3
1
93.
ptr2
list
3
1
94.
ptr2
list
3
1
95.
ptr2
list
3
1
96.
ptr2
list
3
1
97.
2list
3
1
98.
99.
list100.
list1
101.
list2
1
102.
list2
3
1
103.
104.
105.
list106.
list1
107.
2list
1
108.
2list
1
3
109.
110.
list111.
list2
112.
2list
1
113.
42
list
1
114.
42
list
1
3
115.
116.
Деревопредставляет собой иерархическую структуру, где элементы (узлы) связаны
между собой подобно ветвям дерева
117.
12
4
5
6
7
3
8
118.
Другие структуры данных, например, массивы, списки, стеки иочереди, линейные. Это значит, что данные в них хранятся
последовательно.
Когда мы выполняем любую операцию в линейной структуре данных,
временная сложность растет с увеличением размера данных.
119.
Другие структуры данных, например, массивы, списки, стеки иочереди, линейные. Это значит, что данные в них хранятся
последовательно.
Когда мы выполняем любую операцию в линейной структуре данных,
временная сложность растет с увеличением размера данных.
Разные древовидные структуры позволяют быстрее и легче получать
доступ к данным, поскольку дерево — структура нелинейная.
120.
• Узел — это объект, в котором есть ключ или значение иуказатели на дочерние узлы.
• Узлы, у которых нет дочерних узлов, называют листьями или
терминальными узлами.
• Узлы, у которых есть хотя бы один дочерний узел, называются
внутренними.
• Ребро связывает два узла.
• Корень — это самый верхний узел дерева. Его ещё иногда
называют корневым узлом.
121.
12
4
5
3
122.
Корень1
Ребро
Узел
2
3
Лист
4
5
123.
12
4
5
6
7
3
8
124.
Бинарное дерево поискаБинарное дерево, в котором для каждого узла значения в левом поддереве
меньше значения в узле, а значения в правом поддереве больше.
125.
12
3
4
5
6
7
126.
12
3
4
5
6
7
127.
12
3
4
5
6
7
128.
12
3
4
5
6
7
129.
42
1
6
3
5
7
130.
42
1
6
3
5
7
131.
132.
133.
134.
135.
42
1
6
3
5
7
136.
137.
138.
139.
140.
141.
142.
2143.
21
144.
21
3
145.
146.
147.
1148.
12
149.
12
3
150.
Словарьили
Ассоциативный массив
Абстрактный тип данных, в котором элементы доступны по индексам
(ключам) имеющим произвольный тип данных
151.
152.
153.
СловоОпределение
154.
КлючЗначение
155.
namenumber
156.
157.
158.
Хешированиепроцесс преобразования данных произвольной длины в строку
фиксированной длины
159.
Хешированиепроцесс преобразования данных произвольной длины в строку
фиксированной длины
Хеш
160.
Хеш-таблицаструктура данных, которая позволяет очень быстро находить
данные по ключу
161.
162.
01
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
163.
AB
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
164.
165.
Mario166.
LuigiMario
167.
LuigiMario
Peach
168.
BirdoDaisy
Goomba
Isabelle
King Boo
Luigi
Mario
Peach
Rosalina
Shy Guy
Toad
Wario
Yoshi
Zelda
169.
BirdoDaisy
Goomba
Isabelle
King Boo
Luigi
Mario
Peach
Rosalina
Shy Guy
Toad
Wario
Yoshi
Zelda
Lakitu
170.
BirdoBowser
Bowser Jr.
Daisy
Donkoey Kong
Diddy Kong
Goomba
Ganon
Isabelle
King Boo
K. K. Slider
Luigi
Lakitu
Link
Mario
Peach
Peter Piranha
Rosalina
Shy Guy
Spike
Toad
Toadette
Wario
Waluigi
Yoshi
Zelda
Toom Nook
Dry Bones
171.
172.
173.
174.
175.
176.
177.
178.
179.
LaaLab
Lac
Lad
Lae
Laf
Lag
Lah
Lai
Laj
Lak
Lakitu
...
Lim
Lin
Link
Lio
...
Luh
Lui
Luj
Luigi
180.
181.
182.
183.
184.
185.
186.
Структура данныхinsert
remove
find
Array
O(N)
O(N)
O(N)
List
O(1)
O(1)
O(N)
Sorted array
O(N)
O(N)
O(logN)
O(logN)
O(logN)
O(logN)
Бинарное дерево поиска
187.
Структура данныхinsert
remove
find
Array
O(N)
O(N)
O(N)
List
O(1)
O(1)
O(N)
Sorted array
O(N)
O(N)
O(logN)
O(logN)
O(logN)
O(logN)
O(1)
O(1)
O(1)
Бинарное дерево поиска
Хеш-таблица
188.
189.
Префиксное деревоспециализированная структура данных, которая используется для хранения
и поиска строк
190.
Массив191.
МассивСвязный список
192.
МассивСвязный список
Хеш-таблица
193.
МассивСвязный список
Хеш-таблица – массив связных списков
194.
МассивСвязный список
Хеш-таблица – массив связных списков
Префиксное дерево – дерево массивов
195.
196.
A B C D E F G H IJ K L
M N O P Q R S T
U V W X Y Z
197.
T198.
TO
199.
TO
A
200.
TO
A
D
201.
TO
A
D
E
202.
TO
A
D
E
T
203.
TO
A
D
E
T
T
204.
TO
A
D
E
T
T
E
205.
TO
A
M
D
E
T
T
E
206.
207.
208.
TOU CS1016
Структуры данных
Очередь
Стек
Связный список