Лекция_6__Структуры_данных_-_Слайды

1.

Toraighyrov University
ОСЕННИЙ СЕМЕСТР 2024
ЛЕКЦИЯ
Структуры данных
6

2.

DISCORD
https://discord.gg/JNBX2Zwksn

3.

4.

Структуры данных
Способ организации информации в памяти

5.

Абстрактные структуры данных
Концептуальная модель того, как хранят и организуют данные

6.

Очередь
абстрактный тип данных, который организует элементы в
последовательности FIFO

7.

FIFO
First in — First out
Первым вошёл, первым вышел.
Очередь
абстрактный тип данных, который организует элементы в
последовательности FIFO

8.

9.

10.

11.

12.

13.

14.

Стек
абстрактный тип данных, доступ к элементам которых организован по
принципу LIFO

15.

LIFO
Last in — First out
Последний вошёл, первым вышел.
Стек
абстрактный тип данных, доступ к элементам которых организован по
принципу LIFO

16.

17.

18.

19.

20.

21.

1
2
3

22.

1
2
3

23.

1
2
3

24.

1
o
\0
,
2
3
h
e
l
l
w
o
r
l
d

25.

1
2
3

26.

1
1
2
3

27.

1
2
1
2
3

28.

1
2
3
1
2
3

29.

1
2
3
1
2
3
4

30.

1
2
3
4

31.

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

32.

1
0x123

33.

1
0x123
2
0x456

34.

1
0x123
2
0x456
3
0x789

35.

1
0x123
2
0x456
3
0x789

36.

1
0x123
0x456
2
0x456
3
0x789

37.

1
0x123
0x456
2
0x456
3
0x789

38.

1
0x123
0x456
2
0x456
0x789
3
0x789

39.

1
0x123
0x456
2
0x456
0x789
3
0x789
0x0

40.

1
0x123
0x456
2
0x456
0x789
3
0x789
NULL

41.

1
0x123
0x456
2
0x456
0x123
0x789
3
0x789
NULL

42.

1
2
3

43.

1
0x123
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.

list
1

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.

list
2
1
n

83.

list = n;
list
2
1
n

84.

list = n;
list
2
1
n

85.

list = n;
list
2
1
n

86.

list
2
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.

list
2
1

92.

2
list
3
1

93.

ptr
2
list
3
1

94.

ptr
2
list
3
1

95.

ptr
2
list
3
1

96.

ptr
2
list
3
1

97.

2
list
3
1

98.

99.

list

100.

list
1

101.

list
2
1

102.

list
2
3
1

103.

104.

105.

list

106.

list
1

107.

2
list
1

108.

2
list
1
3

109.

110.

list

111.

list
2

112.

2
list
1

113.

4
2
list
1

114.

4
2
list
1
3

115.

116.

Дерево
представляет собой иерархическую структуру, где элементы (узлы) связаны
между собой подобно ветвям дерева

117.

1
2
4
5
6
7
3
8

118.

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

119.

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

120.

• Узел — это объект, в котором есть ключ или значение и
указатели на дочерние узлы.
• Узлы, у которых нет дочерних узлов, называют листьями или
терминальными узлами.
• Узлы, у которых есть хотя бы один дочерний узел, называются
внутренними.
• Ребро связывает два узла.
• Корень — это самый верхний узел дерева. Его ещё иногда
называют корневым узлом.

121.

1
2
4
5
3

122.

Корень
1
Ребро
Узел
2
3
Лист
4
5

123.

1
2
4
5
6
7
3
8

124.

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

125.

1
2
3
4
5
6
7

126.

1
2
3
4
5
6
7

127.

1
2
3
4
5
6
7

128.

1
2
3
4
5
6
7

129.

4
2
1
6
3
5
7

130.

4
2
1
6
3
5
7

131.

132.

133.

134.

135.

4
2
1
6
3
5
7

136.

137.

138.

139.

140.

141.

142.

2

143.

2
1

144.

2
1
3

145.

146.

147.

1

148.

1
2

149.

1
2
3

150.

Словарь
или
Ассоциативный массив
Абстрактный тип данных, в котором элементы доступны по индексам
(ключам) имеющим произвольный тип данных

151.

152.

153.

Слово
Определение

154.

Ключ
Значение

155.

name
number

156.

157.

158.

Хеширование
процесс преобразования данных произвольной длины в строку
фиксированной длины

159.

Хеширование
процесс преобразования данных произвольной длины в строку
фиксированной длины
Хеш

160.

Хеш-таблица
структура данных, которая позволяет очень быстро находить
данные по ключу

161.

162.

0
1
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.

A
B
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.

Mario

166.

Luigi
Mario

167.

Luigi
Mario
Peach

168.

Birdo
Daisy
Goomba
Isabelle
King Boo
Luigi
Mario
Peach
Rosalina
Shy Guy
Toad
Wario
Yoshi
Zelda

169.

Birdo
Daisy
Goomba
Isabelle
King Boo
Luigi
Mario
Peach
Rosalina
Shy Guy
Toad
Wario
Yoshi
Zelda
Lakitu

170.

Birdo
Bowser
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.

Laa
Lab
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 I
J K L
M N O P Q R S T
U V W X Y Z

197.

T

198.

T
O

199.

T
O
A

200.

T
O
A
D

201.

T
O
A
D
E

202.

T
O
A
D
E
T

203.

T
O
A
D
E
T
T

204.

T
O
A
D
E
T
T
E

205.

T
O
A
M
D
E
T
T
E

206.

207.

208.

TOU CS101
6
Структуры данных
Очередь
Стек
Связный список