1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Тиждень 6, продовження]

2
00:00:02,520 --> 00:00:04,160
[David J. Малан] [Harvard University]

3
00:00:04,160 --> 00:00:08,720
[Це CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Це CS50 і це в кінці тижня 6.

5
00:00:12,970 --> 00:00:17,970
Так CS50x, один з перших курсів Гарвардського університету, що беруть участь в EDX ініціативи

6
00:00:17,970 --> 00:00:20,590
Дійсно дебютував в минулий понеділок.

7
00:00:20,590 --> 00:00:23,460
Якщо ви хочете отримати уявлення про те, що інших в Інтернеті

8
00:00:23,460 --> 00:00:27,180
В даний час наступних разом з, ви можете відправитися на x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Це буде перенаправити вас в потрібне місце на edx.org,

10
00:00:30,350 --> 00:00:34,160
який був, де ця та інші програми навчання в MIT і Берклі зараз живемо.

11
00:00:34,160 --> 00:00:38,140
Ви повинні зареєструватися для облікового запису, ви знайдете, що матеріал є в значній мірі те ж саме

12
00:00:38,140 --> 00:00:42,170
як у вас було в цьому семестрі, хоча і декілька тижнів затримується, оскільки ми отримуємо все готово.

13
00:00:42,170 --> 00:00:46,930
Але те, що студенти в CS50x побачите це інтерфейс, зовсім як цей.

14
00:00:46,930 --> 00:00:50,040
Це, наприклад, є Zamyla провідних покрокове керівництво для завдання набору 0.

15
00:00:50,040 --> 00:00:54,230
При вході в edx.org, CS50x студент бачить різні речі

16
00:00:54,230 --> 00:00:57,170
Ви очікували б побачити в курсі: лекція для понеділка,

17
00:00:57,170 --> 00:01:01,650
Лекція на середу, різні шорти, проблема набору, покрокові керівництва, PDF-файли.

18
00:01:01,650 --> 00:01:04,459
Крім того, як ви тут бачите, переклади машини

19
00:01:04,459 --> 00:01:08,390
з англійського стенограми на китайський, японський, іспанський, італійський,

20
00:01:08,390 --> 00:01:12,810
і ціла купа інших мов, які, безумовно, буде недосконалим

21
00:01:12,810 --> 00:01:15,840
як ми котимося їх програмно, використовуючи так званий API,

22
00:01:15,840 --> 00:01:18,360
або інтерфейс прикладного програмування, від Google

23
00:01:18,360 --> 00:01:21,360
, Що дозволяє нам перетворити англійської на ці інші мови.

24
00:01:21,360 --> 00:01:24,100
Але завдяки чудовому духу деяких сто з гаком добровольців,

25
00:01:24,100 --> 00:01:26,940
випадкових людей в інтернеті, які люб'язно запропонували взяти участь

26
00:01:26,940 --> 00:01:30,180
У цьому проекті, ми будемо поступово покращуючи якість цих перекладів

27
00:01:30,180 --> 00:01:35,790
при наявності людей виправляти помилки, що наші комп'ютери зробили.

28
00:01:35,790 --> 00:01:42,330
>> Ось і виходить, що ми ще кільком студентам показати в понеділок, чим ми спочатку очікували.

29
00:01:42,330 --> 00:01:48,980
У самому справі, тепер CS50x має 100.000 чоловік слідуючи уздовж будинку.

30
00:01:48,980 --> 00:01:54,430
Так розумію, ви всі частини цього першого класу робить цей курс з інформатики

31
00:01:54,430 --> 00:01:57,370
освіти в цілому, більш широко, доступно.

32
00:01:57,370 --> 00:02:00,130
А реальність така тепер, з деякими з цих масштабної онлайн-курси,

33
00:02:00,130 --> 00:02:04,070
всі вони починаються з цих дуже великих кількостях, як ми, здається, зробили тут.

34
00:02:04,070 --> 00:02:08,759
Але мета, в кінцевому рахунку, для CS50x дійсно отримати якомога більше людей до фінішу наскільки це можливо.

35
00:02:08,759 --> 00:02:12,000
За задумом, CS50x збирається бути запропонована з цього в минулий понеділок

36
00:02:12,000 --> 00:02:17,430
на всьому шляху по 15 квітня 2013 року, так що люди, які мають школи зобов'язань в інших місцях,

37
00:02:17,430 --> 00:02:20,990
робота, сім'я, інші конфлікти тощо, є трохи більше гнучкості

38
00:02:20,990 --> 00:02:23,640
, З якої зануритися в цей курс, який, досить сказати,

39
00:02:23,640 --> 00:02:30,540
досить амбіційно зробити, якщо тільки протягом лише трьох місяців протягом звичайного семестру.

40
00:02:30,540 --> 00:02:34,190
Але цих студентів буде вирішувати ті ж безлічі проблем, перегляду того ж змісту,

41
00:02:34,190 --> 00:02:36,350
мають доступ до тих же шорти тощо.

42
00:02:36,350 --> 00:02:38,990
Так розумію, що ми всі дійсно в цьому разом.

43
00:02:38,990 --> 00:02:42,360
І одна з кінцевих цілей CS50x не тільки отримати якомога більше людей

44
00:02:42,360 --> 00:02:45,720
до фінішу і дати їм цю знову знайдену розуміння інформатики

45
00:02:45,720 --> 00:02:49,000
і програмування, але і мати їх у цього поділилися досвідом.

46
00:02:49,000 --> 00:02:52,010
Однією з визначальних характеристик з 50 на території кампусу, ми сподіваємося,

47
00:02:52,010 --> 00:02:56,260
була така комунальна досвід, на краще чи на гірше, інколи,

48
00:02:56,260 --> 00:02:59,480
але мають ці люди звертаються до наліво і направо,

49
00:02:59,480 --> 00:03:01,830
і офісних годин і Hackathon і справедливою.

50
00:03:01,830 --> 00:03:04,560
Це трохи складніше зробити це в обличчя з людьми в Інтернеті,

51
00:03:04,560 --> 00:03:10,580
але CS50x завершиться в квітні з першим CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
, Який буде онлайн адаптації наше уявлення про справедливу

53
00:03:13,630 --> 00:03:18,250
де ці тисячі студентів все буде запропоновано представити 1 - 2-хвилинне відео,

54
00:03:18,250 --> 00:03:22,480
або скрінкасти їх остаточного проекту або відео з них розмахував привіт

55
00:03:22,480 --> 00:03:24,490
і говорити про свій проект і demoing це,

56
00:03:24,490 --> 00:03:27,610
так само, як ваші попередники зробили тут, на території кампусу в ярмарку,

57
00:03:27,610 --> 00:03:31,400
так що до кінця семестру, надія на те, щоб мати глобальні виставки

58
00:03:31,400 --> 00:03:37,080
кінцевих проектів CS50x студентів, як і те, що чекає вас в грудні цього року тут, на території кампусу.

59
00:03:37,080 --> 00:03:39,680
Так про це в найближчі місяці.

60
00:03:39,680 --> 00:03:43,640
>> З 100.000 студентів, проте, приходить необхідність ще кілька центрів сертифікації.

61
00:03:43,640 --> 00:03:47,590
Враховуючи те, що ви, хлопці, прокладає шлях тут і приймаючи CS50

62
00:03:47,590 --> 00:03:51,630
кілька тижнів до випуску цього матеріалу, щоб люди на EDX,

63
00:03:51,630 --> 00:03:55,330
розумію, що ми хотіли б привернути як багато хто з наших студентів, як можливо у цій ініціативі,

64
00:03:55,330 --> 00:03:58,720
як протягом семестру, а також цієї зими, і це майбутньою весною.

65
00:03:58,720 --> 00:04:01,620
Так що, якщо ви хочете взяти участь в CS50x,

66
00:04:01,620 --> 00:04:07,450
Особливо на вступ до CS50x Обговорити, версія EDX з Обговорити CS50,

67
00:04:07,450 --> 00:04:10,140
які багато хто з вас вже використовують на території кампусу, онлайн табло,

68
00:04:10,140 --> 00:04:13,040
будь ласка, зробіть голову, що URL, дайте нам знати, хто ви,

69
00:04:13,040 --> 00:04:16,450
тому що ми хотіли б побудувати команду студентів і співробітників та викладачів, так

70
00:04:16,450 --> 00:04:19,630
на території кампусу, які просто грають разом і допомагати.

71
00:04:19,630 --> 00:04:21,720
І коли вони бачать, що це питання знайомі з ними,

72
00:04:21,720 --> 00:04:25,320
Ви чуєте студент звітності якась помилка десь там, в якійсь країні в Інтернет,

73
00:04:25,320 --> 00:04:27,450
і що дзвонить у дзвін, бо ви теж були в тому ж питанні

74
00:04:27,450 --> 00:04:32,620
в р-залі якийсь час назад, ми сподіваємося, то ви можете дзвонити в і поділитися своїм власним досвідом.

75
00:04:32,620 --> 00:04:37,300
Тому, будь ласка, участь, якщо ви хочете.

76
00:04:37,300 --> 00:04:39,360
>> Інформатика курси у Гарварді є трохи традиції,

77
00:04:39,360 --> 00:04:44,730
CS50 серед них, що має деякий одяг, одяг, який можна носити з гордістю

78
00:04:44,730 --> 00:04:49,090
в кінці семестру, заявивши, що не без гордості, що ви закінчили CS50

79
00:04:49,090 --> 00:04:51,830
і взяв CS50 і тому подібне, і ми завжди намагаємося залучити студентів

80
00:04:51,830 --> 00:04:54,540
У цьому процесі якомога більше, причому ми запрошуємо,

81
00:04:54,540 --> 00:04:56,900
приблизно в цей час семестру, студенти представити проекти

82
00:04:56,900 --> 00:04:59,330
використання Photoshop, або будь-який інший інструмент вибору ви хотіли б використовувати

83
00:04:59,330 --> 00:05:02,330
Якщо ви дизайнер, представити проекти для футболки та толстовки

84
00:05:02,330 --> 00:05:06,100
і парасольками і мало бандани для собак у нас тепер є і тому подібне.

85
00:05:06,100 --> 00:05:09,370
І все це потім - переможці кожного року, потім виставлені

86
00:05:09,370 --> 00:05:12,700
на веб-сайті курсу на store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Все продається за вартістю там, але сайт просто працює собі

88
00:05:15,790 --> 00:05:18,330
і дозволяє людям вибирати кольори та дизайну, що їм подобається.

89
00:05:18,330 --> 00:05:20,420
Таким чином, я думав, що ми просто поділитися деякими з конструкцій останній рік

90
00:05:20,420 --> 00:05:25,130
, Які були на сайті, крім цього тут, який є щорічною традицією.

91
00:05:25,130 --> 00:05:29,410
"Кожен день я Seg Faultn" була однією з представлених в минулому році,

92
00:05:29,410 --> 00:05:32,290
який як і раніше доступні там для випускників.

93
00:05:32,290 --> 00:05:35,820
У нас була одна, "CS50, підстави 1989".

94
00:05:35,820 --> 00:05:39,010
Один з наших Bowdens, Боб, був дуже популярний в минулому році.

95
00:05:39,010 --> 00:05:43,480
"Команда Боуден" народився, цей проект був представлений, серед кращих продавців.

96
00:05:43,480 --> 00:05:49,040
Як це було тут. Багато людей були "Боуден Fever" з продажу журналів.

97
00:05:49,040 --> 00:05:52,650
Зрозумійте, що тепер може бути ваш дизайн там, на Інтернет.

98
00:05:52,650 --> 00:05:57,510
Докладніше про це в наступній проблемою встановлює в майбутньому.

99
00:05:57,510 --> 00:06:00,330
>> Ще один інструмент: Ви мали деякий вплив і, сподіваюсь, тепер

100
00:06:00,330 --> 00:06:02,350
деякий практичний досвід роботи з GDB,

101
00:06:02,350 --> 00:06:04,570
який, звичайно, відладчик і дозволяє маніпулювати

102
00:06:04,570 --> 00:06:09,500
Ваша програма на досить низькому рівні, робити якісь речі?

103
00:06:09,500 --> 00:06:13,030
Що GDB дозволяють вам робити?

104
00:06:13,030 --> 00:06:15,030
Так? Дайте мені що-небудь. [Студент відповідь, нерозбірливо]

105
00:06:15,030 --> 00:06:18,120
Добре. Крок у функції, так що ви не просто повинні ввести працювати

106
00:06:18,120 --> 00:06:22,310
і є програма удар по всій його повноті, роздрукувавши речі на стандартний вивід.

107
00:06:22,310 --> 00:06:25,190
Замість цього, ви можете покроково його рядок за рядком, або ввівши наступну

108
00:06:25,190 --> 00:06:30,300
йти рядок за рядком по лінії чи крок, щоб зануритися в функцію, як правило, той, який ви написали.

109
00:06:30,300 --> 00:06:35,240
Що ще GDB дозволяють вам робити? Так? [Студент відповідь, нерозбірливо]

110
00:06:35,240 --> 00:06:38,100
Друк змінних. Так що якщо ви хочете зробити невеликий самоаналіз усередині вашої програми

111
00:06:38,100 --> 00:06:41,500
, Не вдаючись до написання заяви Printf всюди,

112
00:06:41,500 --> 00:06:44,600
Ви можете просто роздрукувати змінної або відображати змінної.

113
00:06:44,600 --> 00:06:46,710
Що ще можна зробити за допомогою відладчика, як GDB?

114
00:06:46,710 --> 00:06:49,170
[Студент відповідь, нерозбірливо]

115
00:06:49,170 --> 00:06:52,080
Саме так. Ви можете встановити точки зупину, можна сказати, перерва виконання

116
00:06:52,080 --> 00:06:54,020
на основній функції або функції Foo.

117
00:06:54,020 --> 00:06:56,800
Можна сказати, перерва виконання з рядка 123.

118
00:06:56,800 --> 00:06:58,950
І останову є дуже потужною технікою

119
00:06:58,950 --> 00:07:01,110
тому що, якщо у вас є загальне відчуття від того, де ваша проблема

120
00:07:01,110 --> 00:07:05,360
Ймовірно, ви не повинні витрачати час покрокового обсязі програми.

121
00:07:05,360 --> 00:07:08,250
Ви можете істотно стрибати прямо там і тоді почати друкувати -

122
00:07:08,250 --> 00:07:10,970
ступаючи по них з кроком або наступного або тому подібне.

123
00:07:10,970 --> 00:07:14,340
Але зловити щось на зразок GDB є те, що він допомагає вам, людині,

124
00:07:14,340 --> 00:07:16,940
знайти ваші проблеми і знайти свої помилки.

125
00:07:16,940 --> 00:07:19,470
Це не обов'язково знайде їх так багато для вас.

126
00:07:19,470 --> 00:07:23,070
>> Таким чином, ми представили інші style50 день, який знаходиться в декількох хвилинах інструмент командного рядка

127
00:07:23,070 --> 00:07:27,500
, Який намагається стилізувати код трохи чистіше, ніж ви, людина, можливо, доведеться зробити.

128
00:07:27,500 --> 00:07:29,530
Але це теж, насправді просто естетична річ.

129
00:07:29,530 --> 00:07:34,110
Але, виявляється, є цей інший інструмент під назвою Valgrind, що є трохи більш таємницею для використання.

130
00:07:34,110 --> 00:07:36,860
Його вихід звірячому загадкові на перший погляд.

131
00:07:36,860 --> 00:07:39,420
Але це дивно корисні, особливо зараз, коли ми знаходимося в частині терміну

132
00:07:39,420 --> 00:07:43,080
де ви починаєте використовувати Танос і динамічного розподілу пам'яті.

133
00:07:43,080 --> 00:07:45,420
Все може піти дуже, дуже неправильно швидко.

134
00:07:45,420 --> 00:07:49,320
Тому що, якщо ви забули, щоб звільнити пам'ять, або ви разименовать деякі NULL покажчика,

135
00:07:49,320 --> 00:07:55,770
або ви разименовать сміття покажчик, що, як правило, ознака того, що результати?

136
00:07:55,770 --> 00:07:59,470
Seg вина. І ви отримаєте цей файл ядра деякого числа кілобайтах або мегабайтах

137
00:07:59,470 --> 00:08:02,990
, Який представляє стан пам'яті вашої програми, коли він розбився,

138
00:08:02,990 --> 00:08:05,730
але ваша програма в кінцевому рахунку сегментам недоліки, помилки сегментації,

139
00:08:05,730 --> 00:08:08,450
що означає щось погане сталося майже завжди пов'язані

140
00:08:08,450 --> 00:08:11,750
в пов'язаних з пам'яттю помилки, які ви зробили десь.

141
00:08:11,750 --> 00:08:14,100
Так Valgrind допоможе вам знайти такі речі.

142
00:08:14,100 --> 00:08:17,720
Це інструмент, який ви використовуєте, як GDB, після того як ви зібрали ваші програми,

143
00:08:17,720 --> 00:08:20,330
але замість запуску програми безпосередньо, Ви запускаєте Valgrind

144
00:08:20,330 --> 00:08:23,960
і ви передаєте йому свою програму, так само, як ви робите з GDB.

145
00:08:23,960 --> 00:08:26,220
Тепер, використання, щоб отримати кращий вигляд продукції,

146
00:08:26,220 --> 00:08:30,410
це трохи довго, так що тут поверх екрана ви побачите Valgrind-V.

147
00:08:30,410 --> 00:08:35,350
"-V" майже повсюдно означає, докладний, коли ви використовуєте програми на Linux комп'ютер.

148
00:08:35,350 --> 00:08:38,770
Таким чином, це означає, виплюнути більше даних, ніж ви могли б за умовчанням.

149
00:08:38,770 --> 00:08:45,510
»- Витік перевірити = повний". Це просто кажу перевірки для всіх можливих витоків пам'яті,

150
00:08:45,510 --> 00:08:49,430
помилки, які я міг би зробити. Це теж є загальної парадигми з Linux програм.

151
00:08:49,430 --> 00:08:52,710
Взагалі, якщо у вас є аргументи командного рядка, що це «перемикач»,

152
00:08:52,710 --> 00:08:55,830
, Який повинен змінити поведінку програми, і це одна буква,

153
00:08:55,830 --> 00:09:00,310
це-V, але якщо це включається, просто дизайн програміст,

154
00:09:00,310 --> 00:09:05,150
є ціле слово або ряд слів, аргументів командного рядка починається з -.

155
00:09:05,150 --> 00:09:08,190
Це всього лише людина конвенцій, але ви побачите їх все більше і більше.

156
00:09:08,190 --> 00:09:12,410
І ось, нарешті, "a.out" є довільне ім'я програми в цьому конкретному прикладі.

157
00:09:12,410 --> 00:09:14,640
А ось деякі представником продукції.

158
00:09:14,640 --> 00:09:22,890
>> Перш ніж ми подивимося на те, що це може означати, дозвольте мені перейти до фрагмент коду тут.

159
00:09:22,890 --> 00:09:26,390
І дозвольте мені рухатися цим з шляху, найближчим часом,

160
00:09:26,390 --> 00:09:32,120
і давайте поглянемо на memory.c, що цей короткий приклад.

161
00:09:32,120 --> 00:09:36,290
Так що в цій програмі, дозвольте мені збільшити на функції і питання.

162
00:09:36,290 --> 00:09:39,430
У нас є основна функція, яка викликає функцію, F,

163
00:09:39,430 --> 00:09:45,590
і що ж F поступлю, в кілька технічних англійську мову?

164
00:09:45,590 --> 00:09:49,760
Що F продовжити робити?

165
00:09:49,760 --> 00:09:53,680
Як щодо я почну з лінії 20, і розташування зірок не має значення,

166
00:09:53,680 --> 00:09:56,720
але я просто бути послідовним тут з минулого лекції.

167
00:09:56,720 --> 00:09:59,910
Що лінії 20 зробити для нас? На лівій стороні. Ми розбити його далі.

168
00:09:59,910 --> 00:10:02,410
Int * х: що ж це зробити?

169
00:10:02,410 --> 00:10:04,940
Добре. Це оголошення покажчика, а тепер давайте ще більш технічною.

170
00:10:04,940 --> 00:10:10,230
Що це значить, дуже конкретно, оголосити покажчик? Хтось ще?

171
00:10:10,230 --> 00:10:15,050
Так? [Студент відповідь, нерозбірливо] Надто далеко.

172
00:10:15,050 --> 00:10:17,060
Так що ви читаєте в правій частині від знака рівності.

173
00:10:17,060 --> 00:10:20,290
Давайте зосередимося тільки на лівому, тільки на Int * х.

174
00:10:20,290 --> 00:10:24,700
Це "оголосити" покажчик, а тепер давайте поринемо в більш глибоких цьому визначенню.

175
00:10:24,700 --> 00:10:28,330
Що це конкретно, технічно маю на увазі? Так?

176
00:10:28,330 --> 00:10:31,940
[Студент відповідь, нерозбірливо]

177
00:10:31,940 --> 00:10:35,090
Добре. Він готує для збереження адреси в пам'яті.

178
00:10:35,090 --> 00:10:40,680
Добре. І давайте ще один крок, це оголошення змінної х, це 32 біт.

179
00:10:40,680 --> 00:10:44,440
І я знаю, що це 32 біт, тому що -?

180
00:10:44,440 --> 00:10:47,390
Це не тому, що це ціле число, тому що це покажчик в цьому випадку.

181
00:10:47,390 --> 00:10:49,650
Збіг, що це одне і те ж з INT,

182
00:10:49,650 --> 00:10:51,970
Але те, що там є зірки означає, що це покажчик

183
00:10:51,970 --> 00:10:57,300
і в прилад, як і в багатьох комп'ютерах, але не всі, покажчики є 32-бітними.

184
00:10:57,300 --> 00:11:01,850
На більш сучасному устаткуванні, як остання Mac, остання ПК, ви могли б мати 64-розрядні покажчики,

185
00:11:01,850 --> 00:11:04,160
але в прилад, ці речі є 32-бітними.

186
00:11:04,160 --> 00:11:08,380
Таким чином, ми будемо стандартизації на це. Більш конкретно, історія йде наступним чином:

187
00:11:08,380 --> 00:11:10,820
Ми "оголосити" покажчика, що це значить?

188
00:11:10,820 --> 00:11:12,810
Ми готуємо для зберігання адрес пам'яті.

189
00:11:12,810 --> 00:11:15,530
Що це значить?

190
00:11:15,530 --> 00:11:19,810
Ми створюємо змінну звану х, який займає 32 біта

191
00:11:19,810 --> 00:11:23,810
що скоро зберегти адресу цілого числа.

192
00:11:23,810 --> 00:11:26,470
І це, напевно, приблизно так само точно, як ми можемо отримати.

193
00:11:26,470 --> 00:11:31,810
Це нормально рухатися вперед, щоб спростити світ і просто сказати, оголосити покажчик називається х.

194
00:11:31,810 --> 00:11:35,380
Оголосіть покажчик, але і зрозуміти, що відбувається насправді

195
00:11:35,380 --> 00:11:38,490
навіть як раз в тих кількох символів.

196
00:11:38,490 --> 00:11:42,040
>> Тепер, на цей раз майже трохи легше, хоча це більше вираз.

197
00:11:42,040 --> 00:11:48,160
Так що ж це робиш, це підкреслив зараз: "Танос (10 * SizeOf (INT));" Так?

198
00:11:48,160 --> 00:11:52,350
[Студент відповідь, нерозбірливо]

199
00:11:52,350 --> 00:11:58,250
Добре. І я візьму його там. Це виділення блоку пам'яті протягом десяти цілих чисел.

200
00:11:58,250 --> 00:12:02,190
А тепер давайте пірнати в трохи глибше, це виділення блоку пам'яті протягом десяти цілих чисел.

201
00:12:02,190 --> 00:12:05,390
Що Танос потім повертаються?

202
00:12:05,390 --> 00:12:10,390
Адреса цього блоку, або, більш конкретно, адреса першого байта, що шматок.

203
00:12:10,390 --> 00:12:14,080
Як же я, програміст, щоб знати, де що частина пам'яті решт?

204
00:12:14,080 --> 00:12:18,340
Я знаю, що це безперервно. Malloc, за визначенням, дасть Вам безперервний шматок пам'яті.

205
00:12:18,340 --> 00:12:21,240
Ні прогалин у ньому. Ви маєте доступ до кожний байт в тому, що шматок,

206
00:12:21,240 --> 00:12:26,760
спина до спини до спини, але як я можу знати, де в кінці цього шматка пам'яті?

207
00:12:26,760 --> 00:12:28,850
При використанні Танос? [Студент відповідь, нерозбірливо] Добре.

208
00:12:28,850 --> 00:12:30,670
Ви не робите. Ви повинні пам'ятати.

209
00:12:30,670 --> 00:12:35,960
Я повинен пам'ятати, що я використовував значення 10, і я навіть не здається, зробили це тут.

210
00:12:35,960 --> 00:12:41,000
Але відповідальність лежить повністю на мені. STRLEN, що ми стали трохи залежить від рядками,

211
00:12:41,000 --> 00:12:45,860
працює тільки тому, що ця конвенція наявності \ 0

212
00:12:45,860 --> 00:12:48,840
або це спеціальне нульовий символ, NUL, в кінці рядка.

213
00:12:48,840 --> 00:12:51,740
Це не виконується для довільного тільки шматки пам'яті.

214
00:12:51,740 --> 00:12:58,590
Це залежить від вас. Таким чином, рядок 20, то, виділяє блок пам'яті

215
00:12:58,590 --> 00:13:02,590
, Який може зберігати десяти цілих чисел, і він зберігає адресу першого байта

216
00:13:02,590 --> 00:13:05,610
цього блоку пам'яті в змінну х.

217
00:13:05,610 --> 00:13:11,140
Ergo, який є дороговказом. Таким чином, рядок 21, на жаль, була помилкою.

218
00:13:11,140 --> 00:13:16,110
Але перше, що він робить? Це говорить магазину на місці 10, 0 індексуються,

219
00:13:16,110 --> 00:13:19,480
з блоку пам'яті називається х значення 0.

220
00:13:19,480 --> 00:13:21,510
>> Так помітили кілька речей, які відбуваються.

221
00:13:21,510 --> 00:13:25,420
Навіть якщо х є покажчиком, пам'ятаєте з пару тижнів тому

222
00:13:25,420 --> 00:13:29,440
що ви все ще можете використовувати масив в стилі квадратних дужок.

223
00:13:29,440 --> 00:13:36,180
Тому що насправді короткі руки позначень для більш загадковим вид арифметики покажчиків.

224
00:13:36,180 --> 00:13:40,320
, Де ми могли б зробити щось на зразок цього: Візьміть адресу X, перенести на 10 місць,

225
00:13:40,320 --> 00:13:44,550
Потім йдуть туди, щоб будь-яку адресу, зберігаються в цьому місці.

226
00:13:44,550 --> 00:13:48,090
Але, відверто кажучи, це просто звірячий читати і освоїтися з.

227
00:13:48,090 --> 00:13:52,900
Таким чином, світ зазвичай використовуються квадратні дужки тільки тому, що це набагато більш зрозумілі людині читати.

228
00:13:52,900 --> 00:13:55,140
Але ось що відбувається насправді під капотом;

229
00:13:55,140 --> 00:13:58,190
х адресою, а не масив, як такої.

230
00:13:58,190 --> 00:14:02,410
Отже, це зберігання 0 в розташування 10 в х.

231
00:14:02,410 --> 00:14:06,120
Чому це погано? Так?

232
00:14:06,120 --> 00:14:17,370
[Студент відповідь, нерозбірливо] Саме так.

233
00:14:17,370 --> 00:14:21,100
Ми тільки виділив десять цілих чисел, але ми розраховуємо від 0 при програмуванні на C,

234
00:14:21,100 --> 00:14:25,690
так що у вас є доступ до 0 1 2 3 4 5 6 7 8 9, а не 10.

235
00:14:25,690 --> 00:14:30,270
Так що або програма буде сегменті вина або це не так.

236
00:14:30,270 --> 00:14:32,900
Але ми не знаємо, це свого роду недетермінованої поведінки.

237
00:14:32,900 --> 00:14:35,600
Це дійсно залежить від того, нам пощастить.

238
00:14:35,600 --> 00:14:40,650
Якщо з'ясується, що операційна система не заперечуєте, якщо я використовую це додатковий байт,

239
00:14:40,650 --> 00:14:43,360
хоча він не дав його мені, моя програма не може привести до збою.

240
00:14:43,360 --> 00:14:46,780
Це сировина, він помилковий, але ви не можете бачити, що симптом,

241
00:14:46,780 --> 00:14:48,960
або ви могли б бачити його тільки один раз в той час.

242
00:14:48,960 --> 00:14:51,230
Але реальність така, що помилка, насправді, немає.

243
00:14:51,230 --> 00:14:54,320
І це дійсно проблематично, якщо ви написали програму, яку ви хочете бути правильною,

244
00:14:54,320 --> 00:14:58,840
що ви продали програми, які люди використовують, що кожен раз в той час аварій

245
00:14:58,840 --> 00:15:02,450
тому що, звичайно, це не добре. У самому справі, якщо у вас є телефон Android або iPhone

246
00:15:02,450 --> 00:15:05,550
і ви можете завантажити програми в ці дні, якщо ви коли-небудь мали додаток просто кинути палити,

247
00:15:05,550 --> 00:15:10,040
раптом він зникає, це майже завжди результат деякого пов'язаних з пам'яттю проблеми,

248
00:15:10,040 --> 00:15:12,830
причому програміст облажались і разименован покажчик

249
00:15:12,830 --> 00:15:18,670
що він або вона не повинна мати, і результат IOS або Android, щоб просто вбити програму в цілому

250
00:15:18,670 --> 00:15:23,080
ніж ризикувати невизначений поведінку або якийсь компроміс безпеки.

251
00:15:23,080 --> 00:15:25,950
>> Там ще одна помилка в цій програмі, крім цього.

252
00:15:25,950 --> 00:15:30,180
Що ще я облажався в цій програмі?

253
00:15:30,180 --> 00:15:32,740
Я не практикував те, що я проповідував. Так?

254
00:15:32,740 --> 00:15:34,760
[Студент відповідь, нерозбірливо] Добре.

255
00:15:34,760 --> 00:15:36,880
Я не звільнив пам'ять. Таким чином, правило тепер

256
00:15:36,880 --> 00:15:43,150
повинна бути в будь-який час ви дзвоните Танос, ви повинні зателефонувати безкоштовно, коли ви зробили за допомогою цієї пам'яті.

257
00:15:43,150 --> 00:15:45,610
Тепер, коли я хочу, щоб звільнити цю пам'ять?

258
00:15:45,610 --> 00:15:49,780
Мабуть, припускаючи, що це перша лінія була правильною, я хотів би зробити це тут.

259
00:15:49,780 --> 00:15:55,710
Тому що я не могла б, наприклад, зробити це тут. Чому?

260
00:15:55,710 --> 00:15:57,860
Тільки з області видимості. Тому, навіть якщо ми говоримо про покажчиків,

261
00:15:57,860 --> 00:16:04,830
це тижні 2 або 3 питання, де х тільки в сферу всередині фігурних дужок, де вона була оголошена.

262
00:16:04,830 --> 00:16:11,000
Таким чином, ви напевне не може звільнити його там. Мій єдиний шанс, щоб звільнити це приблизно після рядка 21.

263
00:16:11,000 --> 00:16:15,170
Це досить проста програма, це було досить легко, якщо ви вигляд загорнуті вашого розуму

264
00:16:15,170 --> 00:16:17,870
навколо того, що програма робить, де помилки були.

265
00:16:17,870 --> 00:16:20,500
І навіть якщо ви не бачите його в перший, сподіваюся, це трохи очевидним,

266
00:16:20,500 --> 00:16:23,870
що ці помилки досить легко вирішується і легко зробити.

267
00:16:23,870 --> 00:16:28,720
Але коли програма складає більше 12 рядків, це 50 рядків, 100 рядків,

268
00:16:28,720 --> 00:16:31,150
пішки через код рядок за рядком, думаючи, що через нього логічно,

269
00:16:31,150 --> 00:16:35,110
Можливо, але не особливо весело робити, постійно шукає помилки,

270
00:16:35,110 --> 00:16:38,340
і це також важко зробити, і тому такий інструмент, як Valgrind існує.

271
00:16:38,340 --> 00:16:40,900
Дозвольте мені йти вперед і робити цього: нехай мене відкрити вікно терміналу,

272
00:16:40,900 --> 00:16:45,400
і нехай на мене не просто запустити пам'яті, так як пам'ять, здається, добре.

273
00:16:45,400 --> 00:16:49,180
Я отримую пощастило. Переходячи до додаткових байтом, що в кінці масиву

274
00:16:49,180 --> 00:16:51,060
не здаються надто проблематично.

275
00:16:51,060 --> 00:16:56,370
Але дозвольте мені, тим не менш, зробити загальний контроль, який просто означає, що для перевірки

276
00:16:56,370 --> 00:16:58,320
Чи так це насправді правильно.

277
00:16:58,320 --> 00:17:04,690
>> Так давайте зробимо Valgrind-V - витік перевірити = повний,

278
00:17:04,690 --> 00:17:07,520
, А потім назву програми в цьому випадку пам'ять, не a.out.

279
00:17:07,520 --> 00:17:10,760
Отже, дозвольте мені йти вперед і робити це. Натисніть Enter.

280
00:17:10,760 --> 00:17:14,109
Дорогий Бог. Це її виходу, і це те, що я згадав раніше.

281
00:17:14,109 --> 00:17:17,550
Але, якщо ви навчитеся читати через все дурниця тут,

282
00:17:17,550 --> 00:17:20,760
більшості це всього лише діагностичний висновок, що це не так цікаво.

283
00:17:20,760 --> 00:17:24,829
Що ваші очі дійсно хоче, шукає будь-яку згадку про помилку або недійсним.

284
00:17:24,829 --> 00:17:26,800
Слова, які пропонують проблем.

285
00:17:26,800 --> 00:17:29,340
І справді, давайте подивимося, що відбувається не так тут.

286
00:17:29,340 --> 00:17:35,230
У мене є резюме свого роду, "у використанні на виході: 40. Байт в 1 блоків"

287
00:17:35,230 --> 00:17:38,750
Я не зовсім впевнений, що блок поки немає, але 40 байт

288
00:17:38,750 --> 00:17:41,260
насправді відчуває, як я міг зрозуміти, де що йде.

289
00:17:41,260 --> 00:17:45,030
40 байт. Чому 40 байт, використовуваних на виході?

290
00:17:45,030 --> 00:17:48,780
І більш конкретно, якщо ми прокрутити вниз тут,

291
00:17:48,780 --> 00:17:54,520
чому я виразно втратила 40 байт? Так?

292
00:17:54,520 --> 00:17:59,520
[Студент відповідь, нерозбірливо] Perfect. Так, саме так.

293
00:17:59,520 --> 00:18:03,540
Були десяти цілих чисел, і кожен з них є розмір 4 або 32 біт,

294
00:18:03,540 --> 00:18:08,300
так що я втратив саме 40 байт, тому що, як ви запропонували, я не називаються вільними.

295
00:18:08,300 --> 00:18:13,460
Це одна помилка, і тепер давайте подивимося трохи далі і бачити поряд з цим,

296
00:18:13,460 --> 00:18:16,900
"Недійсні запису розміром 4". А що це таке?

297
00:18:16,900 --> 00:18:21,150
Ця адреса виражається те, що база позначення, мабуть?

298
00:18:21,150 --> 00:18:23,640
Це шістнадцятковому, і в будь-який час ви бачите номер, що починається з 0x,

299
00:18:23,640 --> 00:18:29,410
це означає, шістнадцятковій, який ми зробили зворотний шлях, я думаю, розділ PSET 0 'питання,

300
00:18:29,410 --> 00:18:34,090
, Яка була просто робити розминку вправи, перетворюючи десяткової в шістнадцяткову в двійкову і так далі.

301
00:18:34,090 --> 00:18:39,220
Шістнадцяткові, просто людські конвенції, як правило, використовуються для представлення покажчиків

302
00:18:39,220 --> 00:18:41,570
або, більш загально, адреси. Це просто конвенції,

303
00:18:41,570 --> 00:18:45,340
тому що це трохи легше читати, це трохи більш компактний, ніж щось подібне десятковій,

304
00:18:45,340 --> 00:18:47,720
і бінарних марні для більшості людей у ​​використанні.

305
00:18:47,720 --> 00:18:50,840
Так що тепер це значить? Ну, схоже, є недійсним запису

306
00:18:50,840 --> 00:18:54,480
розміром 4 на лінії 21 з memory.c.

307
00:18:54,480 --> 00:18:59,180
Так що давайте повернемося до рядку 21, і дійсно, в тому, що недійсні записи.

308
00:18:59,180 --> 00:19:02,640
Так Valgrind не збирається повністю тримати мене за руку і скажіть, що виправити це,

309
00:19:02,640 --> 00:19:05,520
але виявивши, що я роблю недійсними запису.

310
00:19:05,520 --> 00:19:08,800
Я торкаючись 4 байт, що не повинно бути, і, мабуть, це тому, що,

311
00:19:08,800 --> 00:19:13,960
як ви зазначили, я роблю [10] замість [9] максимально

312
00:19:13,960 --> 00:19:16,660
або [0] або щось між ними.

313
00:19:16,660 --> 00:19:19,690
З Valgrind, розуміють будь-який час Ви зараз пишу програму

314
00:19:19,690 --> 00:19:24,190
, Яка використовує покажчики і використовує пам'ять, і Танос більш конкретно,

315
00:19:24,190 --> 00:19:27,080
Виразно увійти у звичку виконання цього довго

316
00:19:27,080 --> 00:19:30,890
але дуже легко скопіювати і вставити команду Valgrind

317
00:19:30,890 --> 00:19:32,650
, Щоб побачити, якщо є якісь помилки там.

318
00:19:32,650 --> 00:19:34,820
І це буде переважною кожен раз, коли ви бачите вихід,

319
00:19:34,820 --> 00:19:39,430
а просто розібрати через візуально всі вихідні і подивитися, якщо ви бачите згадує помилок

320
00:19:39,430 --> 00:19:43,190
або попередження або недійсним або втрачені.

321
00:19:43,190 --> 00:19:46,200
Будь-які слова, які звучать як ви облажались десь.

322
00:19:46,200 --> 00:19:48,580
Так розумію, що це новий інструмент в ваш інструментарій.

323
00:19:48,580 --> 00:19:51,270
>> Тепер в понеділок, у нас була ціла купа людей приходять сюди

324
00:19:51,270 --> 00:19:53,150
і являють собою поняття, пов'язані списку.

325
00:19:53,150 --> 00:20:00,970
І ми ввели зв'язаний список як рішення якої проблеми?

326
00:20:00,970 --> 00:20:04,590
Так? [Студент відповідь, нерозбірливо] Добре.

327
00:20:04,590 --> 00:20:06,530
Масиви не може мати пам'ять додав до них.

328
00:20:06,530 --> 00:20:09,440
Якщо ви виділити масив розміром 10, от і все у вас вийде.

329
00:20:09,440 --> 00:20:13,690
Ви можете викликати функцію, як перерозподілити, якщо ви спочатку називався Танос,

330
00:20:13,690 --> 00:20:17,580
і що можна спробувати вирощувати масив, якщо є місце до кінця цього

331
00:20:17,580 --> 00:20:21,610
що ніхто не використовує, а якщо ні, то він просто буде знайти вас більший шматок в іншому місці.

332
00:20:21,610 --> 00:20:25,040
Але тоді він буде копіювати всі ці байти в новому масиві.

333
00:20:25,040 --> 00:20:28,310
Це звучить як дуже правильне рішення.

334
00:20:28,310 --> 00:20:34,790
Чому це непривабливо?

335
00:20:34,790 --> 00:20:36,940
Я маю на увазі це працює, люди вирішили цю проблему.

336
00:20:36,940 --> 00:20:40,710
Чому ми повинні вирішити це в понеділок зі зв'язаними списками? Так?

337
00:20:40,710 --> 00:20:44,060
[Студент відповідь, нерозбірливо] Це може зайняти тривалий час.

338
00:20:44,060 --> 00:20:49,260
У самому справі, в будь-який час ви дзвоните Танос або перерозподілити або calloc, який є ще одна,

339
00:20:49,260 --> 00:20:52,470
в будь-який час, програма, говоримо з операційною системою,

340
00:20:52,470 --> 00:20:54,310
Ви схильні уповільнювати програму вниз.

341
00:20:54,310 --> 00:20:57,470
І якщо ви робите такі речі в петлі, ви дійсно уповільнює роботу.

342
00:20:57,470 --> 00:21:00,740
Ви не будете помічати цього для найпростіших "привіт світ" програм типу,

343
00:21:00,740 --> 00:21:04,300
але в набагато більших програм, питаючи, операційна система знову і знову для пам'яті

344
00:21:04,300 --> 00:21:07,520
або даючи йому знову і знову прагне не бути хорошою річчю.

345
00:21:07,520 --> 00:21:11,210
Плюс, це тільки вид інтелектуально - це марна трата часу.

346
00:21:11,210 --> 00:21:16,490
Навіщо виділяти більше і більше пам'яті, ризик копіювання все в новий масив,

347
00:21:16,490 --> 00:21:21,980
якщо у вас є альтернатива, яка дозволяє виділити лише стільки пам'яті, скільки ви насправді потрібно?

348
00:21:21,980 --> 00:21:24,130
Так що є плюси і мінуси тут.

349
00:21:24,130 --> 00:21:26,730
Одним з плюсів є те, що тепер у нас є динамізм.

350
00:21:26,730 --> 00:21:29,100
Не важливо, де шматки пам'яті, які є вільними,

351
00:21:29,100 --> 00:21:32,070
Я можу тільки вид створюють ці хлібні крихти через покажчики

352
00:21:32,070 --> 00:21:34,470
в рядок вся моя зв'язаний список разом.

353
00:21:34,470 --> 00:21:36,470
Але я плачу принаймні одна ціна.

354
00:21:36,470 --> 00:21:40,060
>> Що я повинен відмовити в отриманні пов'язаних списків?

355
00:21:40,060 --> 00:21:42,470
Так? [Студент відповідь, нерозбірливо] Добре.

356
00:21:42,470 --> 00:21:45,650
Вам потрібно більше пам'яті. Тепер мені потрібно місце для цих покажчиків,

357
00:21:45,650 --> 00:21:47,900
і у випадку з цією супер простий зв'язаний список

358
00:21:47,900 --> 00:21:51,410
, Який тільки намагається зберігати цілі числа, які є 4 байти, ми продовжуємо говорити

359
00:21:51,410 --> 00:21:54,240
Ну, покажчик 4 байти, так що тепер я буквально подвоїлися

360
00:21:54,240 --> 00:21:57,290
обсяг пам'яті, мені треба просто зберегти цей список.

361
00:21:57,290 --> 00:21:59,680
Але знову ж, це постійний компроміс в області комп'ютерних наук

362
00:21:59,680 --> 00:22:03,440
між часом і простором і розвитку, зусиль та інших ресурсів.

363
00:22:03,440 --> 00:22:06,630
Що Іншим недоліком використання пов'язаного списку? Так?

364
00:22:06,630 --> 00:22:10,150
[Студент відповідь, нерозбірливо]

365
00:22:10,150 --> 00:22:12,600
Добре. Не так легко отримати доступ. Ми більше не можемо використовувати

366
00:22:12,600 --> 00:22:15,530
Тиждень 0 принципи, як розділяй і володарюй.

367
00:22:15,530 --> 00:22:18,220
І більш конкретно, бінарний пошук. Тому що навіть якщо ми, люди,

368
00:22:18,220 --> 00:22:20,400
бачимо приблизно, де до середини цього списку,

369
00:22:20,400 --> 00:22:25,840
комп'ютер тільки знає, що це зв'язаний список починається з адреси називаються в першу чергу.

370
00:22:25,840 --> 00:22:28,250
І це 0x123 або щось на зразок цього.

371
00:22:28,250 --> 00:22:30,990
І єдиний спосіб, програма може знайти середній елемент

372
00:22:30,990 --> 00:22:33,350
є насправді пошук по всьому списку.

373
00:22:33,350 --> 00:22:35,500
І навіть те, що буквально доводиться шукати весь список, тому що

374
00:22:35,500 --> 00:22:38,950
навіть як тільки ви досягнете середнього елемента, дотримуючись покажчиків,

375
00:22:38,950 --> 00:22:42,380
Ви, програми, поняття не маю, як довго цей список, можливо,

376
00:22:42,380 --> 00:22:45,250
поки ви не потрапили в кінці його, і як ви знаєте, програмно

377
00:22:45,250 --> 00:22:48,600
що ти в кінці зв'язаний список?

378
00:22:48,600 --> 00:22:51,120
Там є спеціальна NULL покажчика, так знову, конвенції.

379
00:22:51,120 --> 00:22:53,870
Замість того, щоб використовувати цей покажчик, ми безумовно не хочемо, щоб це було деяке значення сміття

380
00:22:53,870 --> 00:22:57,750
вказуючи десь за сценою, і ми хочемо, щоб він руку вниз, NULL,

381
00:22:57,750 --> 00:23:01,530
так що у нас є це в кінці цієї структури даних таким чином, ми знаємо, де вона закінчується.

382
00:23:01,530 --> 00:23:03,410
>> Що робити, якщо ми хочемо, щоб маніпулювати цим?

383
00:23:03,410 --> 00:23:05,980
Ми зробили велику частину цього візуально, і з людьми,

384
00:23:05,980 --> 00:23:07,630
Але що, якщо ми хочемо зробити вставки?

385
00:23:07,630 --> 00:23:12,360
Таким чином, в первинному списку було 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Що, якщо ми тоді хотіли Танос простір для номер 55, вузол для нього,

387
00:23:16,730 --> 00:23:20,730
і ми хочемо, щоб вставити 55 в списку так само, як ми зробили в понеділок?

388
00:23:20,730 --> 00:23:23,690
Як ми це робимо? Ну, Аніта підійшла і вона по суті йшов у списку.

389
00:23:23,690 --> 00:23:27,500
Вона почалася з першого елементу, то в наступний, наступний, наступний, наступний, наступний.

390
00:23:27,500 --> 00:23:29,500
Нарешті удар лівою всю дорогу вниз

391
00:23:29,500 --> 00:23:34,480
і зрозуміли, про, це NULL. Так що покажчик маніпуляції потрібно зробити?

392
00:23:34,480 --> 00:23:37,980
Людина, яка була на кінці, № 34, необхідно лівою рукою підняв

393
00:23:37,980 --> 00:23:46,220
, Щоб вказати на 55, 55 потребували їх лівою рукою вказує вниз, щоб стати новим NULL термінатор. Готово.

394
00:23:46,220 --> 00:23:49,540
Досить легко вставити 55 в відсортованому списку.

395
00:23:49,540 --> 00:23:51,800
І як це могло б виглядати?

396
00:23:51,800 --> 00:23:55,690
>> Дозвольте мені йти вперед і відкривати код, наприклад, тут.

397
00:23:55,690 --> 00:23:58,120
Я буду відкривати Gedit, і дозвольте мені відкрити два файли в першу чергу.

398
00:23:58,120 --> 00:24:02,050
Одним з них є list1.h, і дозвольте мені нагадати, що це був шматок коду

399
00:24:02,050 --> 00:24:04,920
, Які ми використовували для представлення вузла.

400
00:24:04,920 --> 00:24:13,040
Вузол має як Int називається п і покажчик називають тепер, що просто вказує на наступну річ у списку.

401
00:24:13,040 --> 00:24:15,450
Тобто в даний час. Файлів годину. Чому?

402
00:24:15,450 --> 00:24:19,090
Там в цю угоду, і ми не скористалися цим величезною кількістю самих себе,

403
00:24:19,090 --> 00:24:22,220
але чоловік, який написав Printf та інші функції

404
00:24:22,220 --> 00:24:27,150
дали в якості подарунка до світу всі ці функції в письмовому вигляді файлу з ім'ям stdio.h.

405
00:24:27,150 --> 00:24:30,950
А тут ще string.h, а там Map.h, і є всі ці файли ч

406
00:24:30,950 --> 00:24:34,410
що ви, можливо, бачили або використовували протягом строку, написані іншими людьми.

407
00:24:34,410 --> 00:24:38,470
Зазвичай в них. Ч файли тільки речі, як ЬурейеЕ

408
00:24:38,470 --> 00:24:42,310
або декларації про користувача типів або декларації констант.

409
00:24:42,310 --> 00:24:47,890
Ви не ставите реалізації функції "в заголовку файлу.

410
00:24:47,890 --> 00:24:50,570
Ви ставите, а не просто їх прототипи.

411
00:24:50,570 --> 00:24:53,050
Ви ставите речі, які ви хочете поділитися зі світом, що їм потрібно

412
00:24:53,050 --> 00:24:55,640
Для компіляції коду. Так, щоб потрапити в цю звичку,

413
00:24:55,640 --> 00:24:59,110
ми вирішили зробити те ж саме. Там не багато в list1.h,

414
00:24:59,110 --> 00:25:02,070
але ми вклали те, що може становити інтерес для людей в світі

415
00:25:02,070 --> 00:25:05,030
які хочуть використовувати нашу пов'язаного реалізації списку.

416
00:25:05,030 --> 00:25:08,040
Тепер, в list1.c, я не буду все це справа

417
00:25:08,040 --> 00:25:11,390
тому що це трохи довго, цю програму, але давайте запустимо це реально швидко в командному рядку.

418
00:25:11,390 --> 00:25:15,720
Дозвольте мені скомпілювати list1, дозвольте мені запустити list1, і те, що ви бачите,

419
00:25:15,720 --> 00:25:18,070
Ми моделювали простенька програма тут

420
00:25:18,070 --> 00:25:20,990
що відбувається, щоб дозволити мені додавати і видаляти номери у список.

421
00:25:20,990 --> 00:25:24,310
Отже, дозвольте мені піти далі і ввести 3 для 3-меню.

422
00:25:24,310 --> 00:25:27,880
Я хочу, щоб вставити номер - давайте зробимо перший номер, який був 9,

423
00:25:27,880 --> 00:25:30,550
і тепер я сказала списку тепер 9.

424
00:25:30,550 --> 00:25:33,760
Дозвольте мені йти вперед і робити інше вставки, так що я вдарив меню 3.

425
00:25:33,760 --> 00:25:36,760
Який номер ви хочете вставити? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. І я зроблю ще одну.

427
00:25:39,220 --> 00:25:41,720
Дозвольте мені вказати число 22.

428
00:25:41,720 --> 00:25:45,850
Отже, ми маємо початок списком, який ми мали у формі слайд хвилину тому.

429
00:25:45,850 --> 00:25:48,740
Як ця вставка відбувається насправді?

430
00:25:48,740 --> 00:25:52,000
Дійсно, 22 в даний час знаходиться в кінці списку.

431
00:25:52,000 --> 00:25:55,050
Так що історія, яку ми розповіли на сцені в понеділок і резюмував зараз

432
00:25:55,050 --> 00:25:57,460
повинно бути насправді відбувається в коді.

433
00:25:57,460 --> 00:25:59,700
Давайте подивимося. Дозвольте мені пальцем прокрутіть в цьому файлі.

434
00:25:59,700 --> 00:26:01,720
Ми будемо замовчувати деякі з функцій,

435
00:26:01,720 --> 00:26:05,630
але ми підемо, скажімо, функції вставки.

436
00:26:05,630 --> 00:26:11,720
>> Давайте подивимося, як ми йдемо про встановлення нового вузла в цій зв'язаний список.

437
00:26:11,720 --> 00:26:14,550
Де список оголошена? Ну, давайте виділіть весь шлях на вершині,

438
00:26:14,550 --> 00:26:19,970
і помітив, що мої зв'язаний список, по суті оголошений як одного покажчика, що це споконвічно NULL.

439
00:26:19,970 --> 00:26:23,180
Так що я за допомогою глобальної змінної тут, що в цілому ми проповідували проти

440
00:26:23,180 --> 00:26:25,280
тому що це робить ваш код трохи брудний підтримувати,

441
00:26:25,280 --> 00:26:29,080
це свого роду ледачий, як правило, але це не лінь, і це не так, і це не погано

442
00:26:29,080 --> 00:26:33,660
якщо єдиною метою вашої програми в життя, щоб моделювати один зв'язаний список.

443
00:26:33,660 --> 00:26:35,460
Які саме те, що ми робимо.

444
00:26:35,460 --> 00:26:39,100
Таким чином, замість заявити про це в основному і потім передати його на кожну функцію

445
00:26:39,100 --> 00:26:42,640
Ми вже писали в цій програмі, ми розуміємо, замість ой, давайте просто зробити його глобальним

446
00:26:42,640 --> 00:26:47,060
тому що вся мета цієї програми полягає в демонстрації одного і тільки одного пов'язаного списку.

447
00:26:47,060 --> 00:26:50,700
Так, що почувається добре. Ось мої прототипи, і ми не будемо пройти через все це,

448
00:26:50,700 --> 00:26:55,800
Але я написав функцію видалення, знайти функції, функції вставки і функції ходу.

449
00:26:55,800 --> 00:26:59,080
Але давайте тепер повернутися вниз до функції вставки

450
00:26:59,080 --> 00:27:01,490
і подивитися, як це працює тут.

451
00:27:01,490 --> 00:27:09,940
Вставити на лінії - тут ми йдемо.

452
00:27:09,940 --> 00:27:12,850
Вставити. Таким чином, він не приймає ніяких аргументів, тому що ми збираємося попросити

453
00:27:12,850 --> 00:27:15,930
Користувач всередині цієї функції числа вони хочуть вставити.

454
00:27:15,930 --> 00:27:19,410
Але, по-перше, ми готуємося, щоб дати їм простір.

455
00:27:19,410 --> 00:27:22,050
Це свого роду копіювання і вставки з інший приклад.

456
00:27:22,050 --> 00:27:25,110
У цьому випадку, ми були виділення Int, на цей раз ми виділенні вузла.

457
00:27:25,110 --> 00:27:27,910
Я дійсно не пам'ятаю, скільки байт вузол, але це нормально.

458
00:27:27,910 --> 00:27:30,460
Sizeof можу зрозуміти, що для мене.

459
00:27:30,460 --> 00:27:33,340
І чому я перевірки на NULL у рядку 120?

460
00:27:33,340 --> 00:27:37,530
Що може піти не так в лінії 119? Так?

461
00:27:37,530 --> 00:27:40,530
[Студент відповідь, нерозбірливо]

462
00:27:40,530 --> 00:27:43,440
Добре. Просто може бути так, що я попросив занадто багато пам'яті

463
00:27:43,440 --> 00:27:47,020
або щось не так і операційна система не вистачає байтів, щоб дати мені,

464
00:27:47,020 --> 00:27:50,640
таким чином, це сигналізує стільки, повертаючи NULL, і якщо я не перевіряють, що

465
00:27:50,640 --> 00:27:54,710
і я просто сліпо продовжувати використовувати адресу повернулася, вона може бути NULL.

466
00:27:54,710 --> 00:27:58,400
Це може бути невідомою вартістю; не дуже хороша річ, якщо я -

467
00:27:58,400 --> 00:28:00,590
насправді не буде невідомого значення. Це може бути NULL, так що я не хочу

468
00:28:00,590 --> 00:28:02,550
зловживати цим і ризикувати разименованія його.

469
00:28:02,550 --> 00:28:07,410
Якщо це відбудеться, я просто повернутися, і ми будемо робити вигляд, що я не повернуся будь-якому пам'яті взагалі.

470
00:28:07,410 --> 00:28:12,270
>> В іншому випадку, я говорю користувач дати мені номер, щоб вставити, я називаю наш старий друг GetInt,

471
00:28:12,270 --> 00:28:15,530
і тоді це був новий синтаксис ми ввели в понеділок.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> N 'означає взяти адресу, яку ви дали Танос

473
00:28:20,320 --> 00:28:23,490
який являє собою перший байт новий об'єкт вузла,

474
00:28:23,490 --> 00:28:26,860
а потім перейдіть до області, званої п.

475
00:28:26,860 --> 00:28:35,270
Трохи дрібниці питання: Це рівносильно тому, що більш загадковим рядки коду?

476
00:28:35,270 --> 00:28:38,110
Як ще я міг би написати це? Хочете прийняти удар?

477
00:28:38,110 --> 00:28:41,480
[Студент відповідь, нерозбірливо]

478
00:28:41,480 --> 00:28:44,870
Добре. Використовуючи. П., але це не так просто, як це.

479
00:28:44,870 --> 00:28:47,090
Що мені в першу чергу необхідно зробити? [Студент відповідь, нерозбірливо]

480
00:28:47,090 --> 00:28:52,730
Добре. Мені потрібно зробити * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Таким чином, це говорить новий покажчик, очевидно, адреса. Чому?

482
00:28:55,610 --> 00:28:59,520
Тому що він був повернутий Танос. * Newptr говорять "туди"

483
00:28:59,520 --> 00:29:02,970
і як тільки ви там, то ви можете використовувати більш звичний. п

484
00:29:02,970 --> 00:29:05,730
але це тільки виглядає трохи потворно, особливо, якщо ми, люди збираються

485
00:29:05,730 --> 00:29:10,360
зробити покажчики зі стрілками весь час в світі є стандартизована на цю стрілку позначення,

486
00:29:10,360 --> 00:29:12,320
, Який робить рівно те ж саме.

487
00:29:12,320 --> 00:29:16,070
Таким чином, ви тільки використовувати -> позначень коли річ зліва покажчик.

488
00:29:16,070 --> 00:29:18,790
В іншому випадку, якщо це фактична структура, використовувати. Н.

489
00:29:18,790 --> 00:29:25,800
І тоді це: Чому я ініціалізації newptr-> поряд з NULL?

490
00:29:25,800 --> 00:29:28,610
Ми не хочемо, обірваних ліву руку від кінця сцени.

491
00:29:28,610 --> 00:29:31,630
Ми хочемо, вказуючи прямо вниз, що означає кінець цього списку

492
00:29:31,630 --> 00:29:34,980
потенційно може бути в цьому вузлі, так що ми краще переконатися, що це NULL.

493
00:29:34,980 --> 00:29:38,460
І, загалом, ініціалізація змінні або елементи даних і структури

494
00:29:38,460 --> 00:29:40,470
щось просто хороша практика.

495
00:29:40,470 --> 00:29:45,170
Якщо просто дозволити сміття існують і продовжують існувати як правило отримує вас в біді

496
00:29:45,170 --> 00:29:48,650
якщо ви забули щось зробити пізніше.

497
00:29:48,650 --> 00:29:51,590
>> Ось кілька випадків. Це, знову ж таки, є функції вставки,

498
00:29:51,590 --> 00:29:54,930
і перше, що я можу перевірити, якщо змінна називається першим,

499
00:29:54,930 --> 00:29:58,240
що глобальна змінна NULL, це означає, що не існує пов'язаного списку.

500
00:29:58,240 --> 00:30:02,460
Ми не вставлені цифри, так це тривіально, щоб вставити цей номер поточної

501
00:30:02,460 --> 00:30:05,240
в список, тому що він просто належить на початку списку.

502
00:30:05,240 --> 00:30:08,100
Так це було, коли Аніта просто стояв тут один, прикидаючись

503
00:30:08,100 --> 00:30:11,390
нікого не було тут, на сцені, поки ми виділили вузла,

504
00:30:11,390 --> 00:30:13,940
Потім вона могла підняти руку в перший раз,

505
00:30:13,940 --> 00:30:17,420
якщо всі інші прийшли на сцену після неї в понеділок.

506
00:30:17,420 --> 00:30:22,900
Тепер ось, це трохи перевірку, де я повинен сказати, що, якщо новий вузла значення п

507
00:30:22,900 --> 00:30:27,370
складає <значення п у поточному першого вузла,

508
00:30:27,370 --> 00:30:29,930
, Що означає, що є зв'язаний список, який почався.

509
00:30:29,930 --> 00:30:32,330
Там, принаймні один вузол у списку, але цей новий хлопець

510
00:30:32,330 --> 00:30:37,230
належить до нього, таким чином, ми повинні рухатися речі.

511
00:30:37,230 --> 00:30:43,450
Іншими словами, якщо в списку почався з просто, скажімо так,

512
00:30:43,450 --> 00:30:48,100
тільки номер 17, це - насправді, ми можемо зробити це більш чітко.

513
00:30:48,100 --> 00:30:56,010
Якщо ми почнемо нашу розповідь з покажчиком тут називають першим,

514
00:30:56,010 --> 00:30:59,870
і спочатку це NULL, і ми вставляємо номер 9,

515
00:30:59,870 --> 00:31:02,510
№ 9, безумовно, належить до початку списку.

516
00:31:02,510 --> 00:31:07,400
Так давайте уявимо, що ми просто malloced адреса або номер 9 і поклав його тут.

517
00:31:07,400 --> 00:31:13,170
Якщо перший 9 за замовчуванням, перший сценарій, який ми обговорювали тільки означає точку давайте цей хлопець тут,

518
00:31:13,170 --> 00:31:15,790
залишити це як NULL; тепер у нас є номер 9.

519
00:31:15,790 --> 00:31:18,280
Наступний номер ми хочемо вставити становить 17.

520
00:31:18,280 --> 00:31:22,420
17 належить тут, так що ми збираємося зробити деякі логічні степпінг через це.

521
00:31:22,420 --> 00:31:26,060
Отже, давайте замість цього, перш ніж зробити це, давайте уявимо, що ми хотіли, щоб вставити номер 8.

522
00:31:26,060 --> 00:31:28,650
>> Так що просто для зручності, я збираюся зробити тут.

523
00:31:28,650 --> 00:31:30,760
Але пам'ятайте, Танос можете покласти його найбільш завгодно.

524
00:31:30,760 --> 00:31:33,460
Але заради креслення, я покладу його тут.

525
00:31:33,460 --> 00:31:38,440
Так прикидатися, що я тільки що виділив вузол номер 8, це NULL за замовчуванням.

526
00:31:38,440 --> 00:31:42,800
Що тепер буде? Кілька речей.

527
00:31:42,800 --> 00:31:47,090
Ми зробили цю помилку на сцену в понеділок, де ми оновили покажчика, як це,

528
00:31:47,090 --> 00:31:51,890
Потім зробив це, і тоді ми заявили - ми сиротами і всі інші на сцені.

529
00:31:51,890 --> 00:31:54,350
Тому що ти не можеш - порядок операцій тут дуже важливо,

530
00:31:54,350 --> 00:31:58,760
тому що тепер ми втратили цей вузол 9, що це тільки вид, плаваючі в просторі.

531
00:31:58,760 --> 00:32:01,150
Так що це був не правильний підхід у понеділок.

532
00:32:01,150 --> 00:32:03,330
Спочатку ми повинні робити щось інше.

533
00:32:03,330 --> 00:32:06,280
Стан світу виглядає наступним чином. Спочатку, 8 були виділені.

534
00:32:06,280 --> 00:32:10,550
Що було б кращим способом вставки 8?

535
00:32:10,550 --> 00:32:14,720
Замість поновлення цього покажчика спочатку просто оновити цей тут замість цього.

536
00:32:14,720 --> 00:32:17,720
Так що ми повинні рядок коду, яка збирається перетворити цей символ NULL

537
00:32:17,720 --> 00:32:22,020
у фактичних покажчик який, вказуючи на вузол 9,

538
00:32:22,020 --> 00:32:27,970
і тоді ми зможемо безпечно змінити в першу чергу, щоб вказати на цей хлопець тут.

539
00:32:27,970 --> 00:32:31,330
Тепер у нас є список, зв'язаний список, з двох елементів.

540
00:32:31,330 --> 00:32:33,580
І що це насправді виглядає тут?

541
00:32:33,580 --> 00:32:36,900
Якщо ми подивимося на код, помітили, що я зробив саме це.

542
00:32:36,900 --> 00:32:41,970
Я сказав newptr, і в цій історії, newptr вказував на цього хлопця.

543
00:32:41,970 --> 00:32:45,520
>> Отже, дозвольте мені зробити ще одну річ, і я повинен був залишити трохи більше місця для цього.

544
00:32:45,520 --> 00:32:48,540
Так що вибачте маленький малюнок.

545
00:32:48,540 --> 00:32:52,140
Цей хлопець називається newptr.

546
00:32:52,140 --> 00:32:57,940
Тобто змінна, яку ми оголосили кілька рядків раніше, в лінію - трохи вище 25.

547
00:32:57,940 --> 00:33:03,430
І це вказує на 8. Тому коли я кажу newptr-> Далі, це означає, що піти на структуру

548
00:33:03,430 --> 00:33:07,910
що буття, на який вказує newptr, тому ми тут, йдіть туди.

549
00:33:07,910 --> 00:33:13,990
Тоді стрілки говорять отримати наступне поле, а потім = говорять покласти те, що значення там?

550
00:33:13,990 --> 00:33:17,280
Значення, яке було в першому, яке значення було в першу чергу?

551
00:33:17,280 --> 00:33:21,930
Перший був спрямований на цьому вузлі, так що означає, що це повинні тепер вказувати на цьому вузлі.

552
00:33:21,930 --> 00:33:25,660
Іншими словами, те, що виглядає хоч і смішно возитися з моїм почерком,

553
00:33:25,660 --> 00:33:28,620
що проста ідея просто переміщення ці стрілки навколо

554
00:33:28,620 --> 00:33:31,560
транслюється в код всього цього лайнера.

555
00:33:31,560 --> 00:33:38,110
Зберігайте те, що в перші в наступному полі, а потім обновити те, що спочатку насправді.

556
00:33:38,110 --> 00:33:40,900
Давайте йти вперед і перемотування вперед через деякі з цього,

557
00:33:40,900 --> 00:33:44,220
і дивитися тільки на цей хвіст вставки на даний момент.

558
00:33:44,220 --> 00:33:51,210
Припустимо, що я дістатися до точки, де я знаходжу, що в наступному полі деякого вузла NULL.

559
00:33:51,210 --> 00:33:53,410
І в цей момент в історії, докладно, що я замазування

560
00:33:53,410 --> 00:33:58,170
є те, що я представив ще один покажчик тут, в лінії 142, попередник покажчик.

561
00:33:58,170 --> 00:34:01,320
По суті, в цей момент в історії, коли список стає довгим,

562
00:34:01,320 --> 00:34:04,800
Я начебто повинні йти він двома пальцями, тому що якщо я йду занадто далеко,

563
00:34:04,800 --> 00:34:08,219
Пам'ятається, в одній довжини списку, ви не можете піти в зворотному напрямку.

564
00:34:08,219 --> 00:34:13,659
Так що ця ідея predptr мій палець лівої руки, і newptr - не newptr.

565
00:34:13,659 --> 00:34:17,199
Іншим покажчиком, що це ось мій другий палець, і я ніби як ходити по списку.

566
00:34:17,199 --> 00:34:22,179
Ось чому, що існує. Але давайте розглядати тільки один з найпростіших випадків тут.

567
00:34:22,179 --> 00:34:26,620
Якщо в наступному полі, яке є покажчиком NULL, що логічного слідування?

568
00:34:26,620 --> 00:34:30,840
Якщо ви обходу цього списку, і ви потрапили NULL покажчика?

569
00:34:30,840 --> 00:34:35,780
Ти в кінці списку, і тому код, щоб потім додати цей один додатковий елемент

570
00:34:35,780 --> 00:34:41,230
є свого роду інтуїтивне буде вважати, що вузол якого наступний покажчик NULL,

571
00:34:41,230 --> 00:34:46,120
так що це в даний час NULL, і змінити його, хоча, як адресу нового вузла.

572
00:34:46,120 --> 00:34:52,260
Так що ми просто малюнок в коді стрілки, що ми звернули на сцену, піднімаючи ліву руку хтось.

573
00:34:52,260 --> 00:34:54,070
>> І так, що я махаю руками на даний момент,

574
00:34:54,070 --> 00:34:58,020
просто тому що я думаю, що це легко заблукати, коли ми робимо це в таке середовище,

575
00:34:58,020 --> 00:35:00,600
перевіряє для вставки в середині списку.

576
00:35:00,600 --> 00:35:03,220
Але тільки інтуїтивно, що має відбутися, якщо ви хочете, щоб з'ясувати

577
00:35:03,220 --> 00:35:06,600
де деяке число повинне стояти в середині, ви повинні йти він

578
00:35:06,600 --> 00:35:09,510
з більш ніж одним пальцем, більше одного покажчика,

579
00:35:09,510 --> 00:35:12,920
з'ясувати, де вона належить по перевірці є елемент <поточний,

580
00:35:12,920 --> 00:35:15,450
> Поточний, і як тільки ви виявите, що місце,

581
00:35:15,450 --> 00:35:20,400
Потім ви повинні робити такого роду оболонки гри, де ви переміщаєте покажчик навколо дуже ретельно.

582
00:35:20,400 --> 00:35:23,850
І ця відповідь, якщо ви хочете, щоб через цю причину у себе вдома на свій власний,

583
00:35:23,850 --> 00:35:28,340
зводиться тільки до цих двох рядків коду, але порядок цих рядків це супер важливо.

584
00:35:28,340 --> 00:35:31,390
Тому що, якщо ви упустите чиюсь руку і підняти чужого не в тому порядку,

585
00:35:31,390 --> 00:35:34,580
знову, ви могли б у кінцевому підсумку сиротами списку.

586
00:35:34,580 --> 00:35:39,500
Підводячи підсумок більш концептуально, вставки в хвіст відносно проста.

587
00:35:39,500 --> 00:35:42,940
Вставки в голову також відносно проста,

588
00:35:42,940 --> 00:35:45,580
але вам необхідно оновити додатковий покажчик на цей раз

589
00:35:45,580 --> 00:35:47,930
вичавити номером 5 у списку тут,

590
00:35:47,930 --> 00:35:51,560
а потім вставка в середині включає в себе ще більше зусиль,

591
00:35:51,560 --> 00:35:56,130
дуже обережно вставити число 20 в правильному місці,

592
00:35:56,130 --> 00:35:58,350
яка знаходиться між 17 і 22.

593
00:35:58,350 --> 00:36:02,700
Так що вам потрібно зробити щось подібне є новий вузол 20 пунктів до 22,

594
00:36:02,700 --> 00:36:08,470
, А потім, покажчик, який вузла повинна бути оновлена ​​в останній раз?

595
00:36:08,470 --> 00:36:10,630
Це 17, насправді його вставити.

596
00:36:10,630 --> 00:36:14,080
Отже, ще раз, я буду відкласти фактичний код для цієї конкретної реалізації.

597
00:36:14,080 --> 00:36:17,280
>> На перший погляд, це трохи переважною, але це дійсно просто нескінченний цикл

598
00:36:17,280 --> 00:36:21,770
яка цикли, цикли, цикли, цикли і порушення, як тільки ви потрапили в NULL покажчика,

599
00:36:21,770 --> 00:36:24,590
в який момент ви можете зробити необхідні вставки.

600
00:36:24,590 --> 00:36:30,960
Це, таким чином, є представником пов'язані перелік кодів вставки.

601
00:36:30,960 --> 00:36:34,590
Це було досить багато, і він відчуває, як ми вирішили одну проблему,

602
00:36:34,590 --> 00:36:36,940
але ми ввели цілий інший. Чесно кажучи, ми витратили весь цей час

603
00:36:36,940 --> 00:36:40,540
на великих O і Ω і час роботи, намагаючись вирішити проблеми швидше,

604
00:36:40,540 --> 00:36:43,270
і тут ми вживаємо великий крок назад, це відчуває.

605
00:36:43,270 --> 00:36:45,380
І все ж, якщо мета для зберігання даних,

606
00:36:45,380 --> 00:36:48,010
він відчуває, як Святий Грааль, як ми вже говорили в понеділок, буде дійсно

607
00:36:48,010 --> 00:36:50,470
для зберігання речей миттєво.

608
00:36:50,470 --> 00:36:53,930
>> У самому справі, припустимо, що ми зробили відкласти в сторону пов'язаного списку на мить

609
00:36:53,930 --> 00:36:56,000
а ми замість цього введено поняття таблиці.

610
00:36:56,000 --> 00:36:59,110
І давайте просто думати про таблиці на мить у вигляді масиву.

611
00:36:59,110 --> 00:37:03,790
Цей масив і цей випадок тут мається близько 26 елементів, від 0 до 25,

612
00:37:03,790 --> 00:37:07,940
і припустимо, що вам потрібно деякий шматок для зберігання імен:

613
00:37:07,940 --> 00:37:10,350
Аліса і Боб і Чарлі тощо.

614
00:37:10,350 --> 00:37:12,880
І вам потрібна структура даних для зберігання цих імен.

615
00:37:12,880 --> 00:37:15,000
Ну, ви можете використовувати щось подібне зв'язаний список

616
00:37:15,000 --> 00:37:20,260
і ви могли йти списку вставки Аліса перед Бобом і Чарлі після того, як Боб і так далі.

617
00:37:20,260 --> 00:37:23,850
І справді, якщо ви хочете, щоб побачити код, як, що, як і в сторону,

618
00:37:23,850 --> 00:37:27,230
Відомо, що в list2.h, ми робимо саме це.

619
00:37:27,230 --> 00:37:30,610
Ми не будемо йти по цьому коду, але це варіант першого прикладу

620
00:37:30,610 --> 00:37:34,640
, Який вводить ще одну структуру ми бачили раніше звана студента,

621
00:37:34,640 --> 00:37:40,330
і те що він насправді зберігаються у зв'язаному списку є покажчиком на структуру студента

622
00:37:40,330 --> 00:37:44,520
а не просто мало числом, с.

623
00:37:44,520 --> 00:37:46,900
Так розумію, що це код там, що включає в себе фактичні рядки,

624
00:37:46,900 --> 00:37:49,940
Але якщо мета під рукою дійсно зараз є вирішення проблеми ефективності,

625
00:37:49,940 --> 00:37:53,380
Не було б непогано, якщо ми цей об'єкт під назвою Alice,

626
00:37:53,380 --> 00:37:56,020
Ми хочемо, щоб помістити її в потрібному місці в структурі даних,

627
00:37:56,020 --> 00:37:58,860
він відчуває, як це було б дуже приємно просто поставити Аліса,

628
00:37:58,860 --> 00:38:01,180
чиє ім'я починається з, в першому місці.

629
00:38:01,180 --> 00:38:05,270
І Боб, чиє ім'я починається з B, у другому місці.

630
00:38:05,270 --> 00:38:09,580
З масивом, або давайте почнемо називати його столом, хеш-таблиці в тому, що

631
00:38:09,580 --> 00:38:13,650
ми можемо зробити саме це. Якщо дано ім'я, як Аліса,

632
00:38:13,650 --> 00:38:16,700
Рядок як Аліса, де поклав ти-л-і-з-е?

633
00:38:16,700 --> 00:38:20,540
Ми повинні hueristic. Нам потрібна функція прийняти деякі вхідні як Аліса

634
00:38:20,540 --> 00:38:24,610
і повернути відповідь: "Поклади Аліса в цьому місці".

635
00:38:24,610 --> 00:38:28,720
І ця функція, це чорний ящик, буде називатися хеш-функції.

636
00:38:28,720 --> 00:38:32,330
>> Хеш-функції є те, що займає вхід, як «Аліса»,

637
00:38:32,330 --> 00:38:38,080
і повертається до вас, як правило, числові місце в деякій структури даних, де Аліса належить.

638
00:38:38,080 --> 00:38:40,830
У цьому випадку наша хеш-функція повинна бути відносно простою.

639
00:38:40,830 --> 00:38:47,510
Наш хеш-функція повинна сказати, що якщо ви отримуєте «Аліса», характер якого я повинен піклуватися про?

640
00:38:47,510 --> 00:38:55,660
Перший. Так що я дивлюся на [0], а потім я кажу, якщо [0] характер, повертається число 0.

641
00:38:55,660 --> 00:39:01,130
Якщо це B, повернути 1. Якщо це C, повернути 2, і так далі.

642
00:39:01,130 --> 00:39:05,940
Всі 0 індексу, і яка дозволила б мені, щоб вставити Алісою і Бобом, то й тоді Чарлі і т. д.

643
00:39:05,940 --> 00:39:10,960
в цю структуру даних. Але є одна проблема.

644
00:39:10,960 --> 00:39:13,060
Що робити, якщо Аніта приходить знову?

645
00:39:13,060 --> 00:39:17,510
Куди покласти Аніта? Її ім'я теж починається з букви А,

646
00:39:17,510 --> 00:39:20,330
і він відчуває, як ми зробили ще більший безлад цієї проблеми.

647
00:39:20,330 --> 00:39:24,380
Тепер у нас є негайне введення, постійне час вставки, в структуру даних

648
00:39:24,380 --> 00:39:27,100
чим гірше справи лінійні,

649
00:39:27,100 --> 00:39:29,510
Але що ми можемо зробити з Анітою в цьому випадку?

650
00:39:29,510 --> 00:39:34,110
Які два варіанти, насправді? Так?

651
00:39:34,110 --> 00:39:37,410
[Студент відповідь, нерозбірливо] Отже, ми могли б мати інший вимір.

652
00:39:37,410 --> 00:39:42,320
Це добре. Таким чином, ми можемо побудувати речі в 3D, як ми говорили про усно в понеділок.

653
00:39:42,320 --> 00:39:46,700
Ми могли б додати ще один доступі тут, але припустимо, що ні, я намагаюся тримати це простим.

654
00:39:46,700 --> 00:39:50,160
Вся мета тут полягає, щоб мати безпосереднє постійне час доступу,

655
00:39:50,160 --> 00:39:52,170
так от додаючи занадто багато складності.

656
00:39:52,170 --> 00:39:55,970
Які інші варіанти, коли намагаюся вставити Аніта в цю структуру даних? Так?

657
00:39:55,970 --> 00:39:58,610
[Студент відповідь, нерозбірливо] Добре. Таким чином, ми могли рухатися всі інші вниз,

658
00:39:58,610 --> 00:40:03,040
як Чарлі поштовхи вниз Боба і Аліси, а потім покласти Аніта, де вона дійсно хоче бути.

659
00:40:03,040 --> 00:40:05,660
>> Звичайно, зараз, є побічний ефект цього.

660
00:40:05,660 --> 00:40:09,000
Ця структура даних, ймовірно, корисно не тому, що ми хочемо вставити люди раз

661
00:40:09,000 --> 00:40:11,250
а тому, що ми хочемо перевірити, якщо вони там пізніше

662
00:40:11,250 --> 00:40:13,600
якщо ми хочемо, щоб роздрукувати всі імена в структурі даних.

663
00:40:13,600 --> 00:40:15,850
Ми збираємося зробити щось з цими даними в кінці кінців.

664
00:40:15,850 --> 00:40:20,810
Отже, тепер ми начебто п'яний за Алісу, яка більше не де вона повинна бути.

665
00:40:20,810 --> 00:40:23,880
Не є Боб, ні Чарлі.

666
00:40:23,880 --> 00:40:26,060
Тому, можливо, це не така вже хороша ідея.

667
00:40:26,060 --> 00:40:28,830
Але насправді, це один варіант. Ми могли зрушити все вниз,

668
00:40:28,830 --> 00:40:32,240
або чорт візьми, Аніта прийшла пізно в грі, чому б нам не просто поставити Anita

669
00:40:32,240 --> 00:40:35,870
Не тут, не тут, не тут, давайте просто покласти її трохи нижче в списку.

670
00:40:35,870 --> 00:40:38,680
Але тоді ця проблема починає переходити знову.

671
00:40:38,680 --> 00:40:41,630
Ви можете бути в змозі знайти Алісу миттєво, заснований на її ім'я.

672
00:40:41,630 --> 00:40:44,320
І Боб миттєво, і Чарлі. Але тоді ви подивіться на Аніту,

673
00:40:44,320 --> 00:40:46,360
і ви побачите, хм, Аліса в путь.

674
00:40:46,360 --> 00:40:48,770
Добре, дозвольте мені перевірити нижче Аліса. Боб не Аніта.

675
00:40:48,770 --> 00:40:51,850
Чарлі не Аніта. О, є Аніта.

676
00:40:51,850 --> 00:40:54,720
І якщо ви будете продовжувати цей поїзд логіці до кінця,

677
00:40:54,720 --> 00:41:00,690
Що найгірший час виконання пошуку або вставки Аніта в цю нову структуру даних?

678
00:41:00,690 --> 00:41:03,280
Це О (п), правильно?

679
00:41:03,280 --> 00:41:06,280
Тому що в гіршому випадку, є Аліса, Боб, Чарлі. . .

680
00:41:06,280 --> 00:41:10,150
Все, аж до якоїсь "Y", тому є тільки одне місце залишилося.

681
00:41:10,150 --> 00:41:13,950
На щастя, у нас ніхто не називав "Z", тому ми помістили Аніта в самому низу.

682
00:41:13,950 --> 00:41:16,040
>> Ми ще не вирішили цю проблему.

683
00:41:16,040 --> 00:41:19,890
Тому, можливо, ми повинні ввести це третій вимір.

684
00:41:19,890 --> 00:41:22,230
А то виходить, якщо ми ввести це третій вимір,

685
00:41:22,230 --> 00:41:25,240
ми не можемо зробити це прекрасно, але Святий Грааль буде отримувати

686
00:41:25,240 --> 00:41:28,370
постійне час вставки та динамічні вставки, так що

687
00:41:28,370 --> 00:41:30,960
Ми не повинні жорстко-коду масив розміру 26.

688
00:41:30,960 --> 00:41:34,400
Ми можемо вставити як багато імен, як ми хочемо, але давайте візьмемо наш 5-хвилинну перерву тут

689
00:41:34,400 --> 00:41:38,790
, А потім зробити це правильно.

690
00:41:38,790 --> 00:41:46,020
Добре. Я поставив історію вгору досить штучно існує

691
00:41:46,020 --> 00:41:48,670
вибравши Аліса і Боб потім і Чарлі, а потім Аніта,

692
00:41:48,670 --> 00:41:51,000
чиє ім'я було очевидно, буде стикатися з Алісою.

693
00:41:51,000 --> 00:41:54,120
Але питання, яке ми закінчили в понеділок тільки, як вірогідне це

694
00:41:54,120 --> 00:41:56,370
що ви отримаєте ці види зіткнень? Іншими словами,

695
00:41:56,370 --> 00:42:00,490
якщо ми почнемо використовувати цю табличну структуру, яка насправді масив,

696
00:42:00,490 --> 00:42:02,460
У цьому випадку з 26 місць,

697
00:42:02,460 --> 00:42:05,740
Що робити, якщо наші входи, а рівномірно розподілена?

698
00:42:05,740 --> 00:42:09,620
Це не штучно Аліса і Боб і Чарлі і Девіда і так далі по алфавіту,

699
00:42:09,620 --> 00:42:12,380
вона рівномірно розподілена по до Z.

700
00:42:12,380 --> 00:42:15,220
>> Може бути, ми просто пощастить, і ми не збираємося мати два або два Б

701
00:42:15,220 --> 00:42:17,640
з дуже високою ймовірністю, але, як хтось вказав,

702
00:42:17,640 --> 00:42:20,730
якщо ми узагальнили цю проблему і не робити від 0 до 25

703
00:42:20,730 --> 00:42:26,060
але, скажімо, від 0 до 364 або 65, часто кількість днів у звичайному році,

704
00:42:26,060 --> 00:42:31,170
і задав питання: "Що ймовірність того, що два з нас в цьому залі є той же день народження?"

705
00:42:31,170 --> 00:42:34,600
Інакше кажучи, те, що ймовірність того, що два з нас є ім'я, що починається з?

706
00:42:34,600 --> 00:42:37,190
Таке питання те ж саме, але це адресний простір,

707
00:42:37,190 --> 00:42:39,940
це простір пошуку, більше в разі народження,

708
00:42:39,940 --> 00:42:42,820
тому що у нас ще дуже багато днів у році, ніж букв в алфавіті.

709
00:42:42,820 --> 00:42:44,910
Яка ймовірність зіткнення?

710
00:42:44,910 --> 00:42:48,410
Ну, ми можемо думати про це, з'ясовуючи, математика навпаки.

711
00:42:48,410 --> 00:42:50,580
Яка ймовірність зіткнення немає?

712
00:42:50,580 --> 00:42:53,970
Ну, це вираз тут говорить, що те, що ймовірність

713
00:42:53,970 --> 00:42:58,770
якщо є тільки одна людина в цій кімнаті, що у них є унікальна день народження?

714
00:42:58,770 --> 00:43:01,190
Це на 100%. Бо якщо є тільки одна людина в кімнаті,

715
00:43:01,190 --> 00:43:03,940
його або її народження може бути будь-який з 365 днів у році.

716
00:43:03,940 --> 00:43:08,650
Таким чином, 365/365 варіантів дає мені значення 1.

717
00:43:08,650 --> 00:43:11,250
Таким чином, ймовірність яких йде мова в даний момент знаходиться всього в 1.

718
00:43:11,250 --> 00:43:13,270
Але якщо є друга людина в кімнаті,

719
00:43:13,270 --> 00:43:16,490
що ймовірність того, що свій день народження по-іншому?

720
00:43:16,490 --> 00:43:20,680
Там тільки 364 можливих днів, без урахування високосних років,

721
00:43:20,680 --> 00:43:23,580
на свій день народження, щоб не зіткнутися з іншими особами.

722
00:43:23,580 --> 00:43:31,920
Таким чином, 364/365. Якщо третя особа приходить, це 363/365, і так далі.

723
00:43:31,920 --> 00:43:35,790
Таким чином, ми розмножуватися разом ці фракції, які стають все менше і менше,

724
00:43:35,790 --> 00:43:40,720
з'ясувати, яка ймовірність того, що у всіх нас є унікальна день народження?

725
00:43:40,720 --> 00:43:43,570
Але тоді ми можемо, звичайно, просто прийняти цю відповідь і перевернути його навколо

726
00:43:43,570 --> 00:43:47,210
і зробити 1 мінус все, що вираз ми в кінці кінців отримаємо

727
00:43:47,210 --> 00:43:51,250
якщо ви пам'ятаєте задню частину книги математика, це виглядає трохи щось на зразок цього,

728
00:43:51,250 --> 00:43:54,590
який набагато легше інтерпретувати графічно.

729
00:43:54,590 --> 00:43:57,820
І це графічне тут має на осі х число народжень,

730
00:43:57,820 --> 00:44:02,030
або кількість людей з народження, а по осі Y є ймовірність матчу.

731
00:44:02,030 --> 00:44:06,060
І що це говорить, що якщо у вас є, скажімо, навіть,

732
00:44:06,060 --> 00:44:10,860
давайте виберемо щось подібне 22, 23.

733
00:44:10,860 --> 00:44:13,160
Якщо є 22 або 23 чоловік у кімнаті,

734
00:44:13,160 --> 00:44:17,100
Імовірність того, що два з тих дуже небагатьох людей будуть мати той же день народження

735
00:44:17,100 --> 00:44:19,560
насправді дуже високо, комбінаторно.

736
00:44:19,560 --> 00:44:23,450
50% шансів, що в класі всього 22 осіб, семінарів, практично,

737
00:44:23,450 --> 00:44:25,790
2 з цих людей будуть мати той же день народження.

738
00:44:25,790 --> 00:44:28,520
Тому що є дуже багато способів, якими ви можете мати той же день народження.

739
00:44:28,520 --> 00:44:31,110
Ще гірше, якщо ви подивитеся на праву частину діаграми,

740
00:44:31,110 --> 00:44:34,040
до того часу, у вас є клас з 58 студентів у ньому,

741
00:44:34,040 --> 00:44:39,270
Імовірність 2 людини свій день народження супер, супер висока, майже 100%.

742
00:44:39,270 --> 00:44:41,880
Так от, це свого роду забавний факт про реальне життя.

743
00:44:41,880 --> 00:44:45,850
>> Але наслідки, тепер, для структур даних і зберігання інформації

744
00:44:45,850 --> 00:44:51,100
означає, що тільки якщо у вас є гарне, чисте, рівномірний розподіл даних

745
00:44:51,100 --> 00:44:53,650
і у вас є досить великий масив, щоб відповідати купу речей

746
00:44:53,650 --> 00:44:59,360
не означає, що ви збираєтеся змусити людей в унікальних місцях.

747
00:44:59,360 --> 00:45:03,810
Ви будете мати зіткнень. Таким чином, це поняття перемішування, як це називається,

748
00:45:03,810 --> 00:45:07,450
приймаючи вхід, як "Аліса" і масажуючи його в деякому роді

749
00:45:07,450 --> 00:45:10,190
, А потім отримати назад відповідь типу 0 або 1 або 2.

750
00:45:10,190 --> 00:45:17,500
Повертаючись деяких виході з цієї функції страждають від цієї вірогідності зіткнення.

751
00:45:17,500 --> 00:45:19,530
Так як ми можемо обробляти ці зіткнення?

752
00:45:19,530 --> 00:45:21,940
Ну, на одному випадку, ми можемо прийняти ідею, що було запропоновано.

753
00:45:21,940 --> 00:45:25,100
Ми можемо просто перекласти всі вниз, або, можливо, трохи простіше,

754
00:45:25,100 --> 00:45:29,870
, А не рух і всі інші, давайте рухатися Anita на дно вільне місце.

755
00:45:29,870 --> 00:45:32,810
Так що, якщо Аліса в 0, Боб знаходиться в 1, Charlie знаходиться в 2,

756
00:45:32,810 --> 00:45:35,260
Ми просто покласти Anita на місці 3.

757
00:45:35,260 --> 00:45:38,860
І це техніка, в даних структурах, званих лінійних зондування.

758
00:45:38,860 --> 00:45:41,310
Лінійна, тому що ви просто ходити цю лінію, і ви роду зондування

759
00:45:41,310 --> 00:45:43,640
доступних місць в структурі даних.

760
00:45:43,640 --> 00:45:46,210
Звичайно, це перетвориться на O (N).

761
00:45:46,210 --> 00:45:49,590
Якщо структура даних дійсно повний, тобто 25 осіб, в ньому вже,

762
00:45:49,590 --> 00:45:54,120
, А потім Аніта приходить, вона закінчується на те, що б розташування Z, і це нормально.

763
00:45:54,120 --> 00:45:56,540
Вона як і раніше підходить, і ми можемо знайти її пізніше.

764
00:45:56,540 --> 00:46:00,100
>> Але це йде врозріз з метою прискорення речі.

765
00:46:00,100 --> 00:46:02,530
Так що, якщо ми замість цього ввів це третій вимір?

766
00:46:02,530 --> 00:46:06,400
Цей метод зазвичай називають окремі ланцюжки, або з ланцюгами.

767
00:46:06,400 --> 00:46:10,030
І те, що хеш-таблицю зараз, це таблична структура,

768
00:46:10,030 --> 00:46:13,450
Ваш стіл це просто масив покажчиків.

769
00:46:13,450 --> 00:46:18,230
Але те, що ці покажчики вказують на те припущення, що?

770
00:46:18,230 --> 00:46:21,970
Зв'язаний список. Так що, якщо взяти найкраще з обох світів?

771
00:46:21,970 --> 00:46:26,500
Ми використовуємо масиви вихідних показників

772
00:46:26,500 --> 00:46:32,070
в структурі даних, тому ми можемо відразу перейти до [0] [1], [30] і так далі,

773
00:46:32,070 --> 00:46:36,480
але так, що у нас є певна гнучкість, і ми можемо підходити Аніта і Еліс і Адам

774
00:46:36,480 --> 00:46:38,630
і будь-які інші назви,

775
00:46:38,630 --> 00:46:43,470
ми замість цього нехай інші осі рости як завгодно.

776
00:46:43,470 --> 00:46:47,340
І ми, нарешті, як в понеділок, є, що виразні можливості з пов'язаного списку.

777
00:46:47,340 --> 00:46:49,530
Ми можемо вирощувати структури даних довільно.

778
00:46:49,530 --> 00:46:52,450
Крім того, ми могли б просто зробити величезний 2-мірний масив,

779
00:46:52,450 --> 00:46:57,190
але це буде жахлива ситуація, якщо один з рядків в 2-мірний масив

780
00:46:57,190 --> 00:47:01,280
не є достатньо великим для додаткового людини, чиє ім'я походить почати з A.

781
00:47:01,280 --> 00:47:04,200
Не дай Бог ми повинні перерозподілити величезний 2-мірної структури

782
00:47:04,200 --> 00:47:06,600
тільки тому, що є дуже багато людей по імені,

783
00:47:06,600 --> 00:47:09,480
Особливо, коли є так мало людей на ім'я Z щось.

784
00:47:09,480 --> 00:47:12,170
Це просто буде дуже рідкісної структурою даних.

785
00:47:12,170 --> 00:47:15,400
Так що це не ідеальний будь-яким способом, але тепер ми принаймні, мати можливість

786
00:47:15,400 --> 00:47:19,090
миттєво знайти, де Аліса і Аніта належить,

787
00:47:19,090 --> 00:47:21,090
принаймні, з точки зору вертикальної осі,

788
00:47:21,090 --> 00:47:25,850
а потім ми просто повинні вирішити, куди помістити Anita або Аліса в країні це зв'язаний список.

789
00:47:25,850 --> 00:47:32,480
Якщо ми не будемо дбати про сортування речей, як швидко ми можемо вставити Аліса в структуру, як це?

790
00:47:32,480 --> 00:47:35,370
Це постійне час. Ми індексу в [0], і якщо ніхто,

791
00:47:35,370 --> 00:47:37,550
Аліса іде на початку, що зв'язаний список.

792
00:47:37,550 --> 00:47:40,000
Але це не величезна угода. Тому що якщо Аніта потім приходить разом

793
00:47:40,000 --> 00:47:42,160
деяка кількість кроків потому, звідки Аніта належать?

794
00:47:42,160 --> 00:47:45,140
Ну, [0]. ООП. Аліса вже в тому, що зв'язаний список.

795
00:47:45,140 --> 00:47:47,760
>> Але якщо ми не дбаємо про сортування ці імена,

796
00:47:47,760 --> 00:47:53,580
ми можемо просто перемістити Аліса більше, вставки Аніта, але навіть це постійне час.

797
00:47:53,580 --> 00:47:57,010
Навіть якщо є Еліс і Адам, і всі ці інші імена,

798
00:47:57,010 --> 00:47:59,410
це дійсно не зрушуючи їх фізично. Чому?

799
00:47:59,410 --> 00:48:04,090
Тому що ми тільки що зробили тут з зв'язаний список, хто знає, чи були ці вузли так чи інакше?

800
00:48:04,090 --> 00:48:06,550
Все, що вам потрібно зробити, це перемістити хлібні крихти.

801
00:48:06,550 --> 00:48:10,930
Переміщення стрілки навколо, ви не повинні фізично переміщати будь-які дані навколо.

802
00:48:10,930 --> 00:48:14,610
Таким чином, ми можемо вставити Аніта, в такому випадку, негайно. Постійна часу.

803
00:48:14,610 --> 00:48:20,250
Отже, ми маємо постійний час пошуку, і постійна часу введення такої людини, як Аніта.

804
00:48:20,250 --> 00:48:22,740
Але вид спрощеного світу.

805
00:48:22,740 --> 00:48:28,510
Що робити, якщо пізніше ми хочемо знайти Алісу?

806
00:48:28,510 --> 00:48:31,050
Що робити, якщо пізніше ми хочемо знайти Алісу?

807
00:48:31,050 --> 00:48:35,690
Скільки кроків є те, що збираєтесь робити?

808
00:48:35,690 --> 00:48:37,850
[Студент відповідь, нерозбірливо]

809
00:48:37,850 --> 00:48:40,950
Саме так. Число людей, перш ніж Аліса в зв'язаному списку.

810
00:48:40,950 --> 00:48:45,420
Так що це не зовсім досконалий, тому що наші структури даних, знову ж таки, це має вертикальну доступу

811
00:48:45,420 --> 00:48:50,240
І тоді він ці зв'язані списки висять - насправді, давайте не будемо малювати масиву.

812
00:48:50,240 --> 00:48:56,020
Він ці зв'язані списки, що висять від цього, що виглядає трохи щось на зразок цього.

813
00:48:56,020 --> 00:48:59,110
Але проблема в тому, якщо Аліса і Адам, і всі ці інші імена

814
00:48:59,110 --> 00:49:01,720
в кінцевому підсумку все більше і більше там,

815
00:49:01,720 --> 00:49:04,810
знайти когось, може в кінцевому підсумку приймає купу кроків,

816
00:49:04,810 --> 00:49:06,670
bcause Ви повинні пройти пов'язаного списку,

817
00:49:06,670 --> 00:49:08,090
, Яка є лінійною операцією.

818
00:49:08,090 --> 00:49:14,270
Так насправді, то, в кінцевому рахунку, час вставки є O (N), де N число елементів у списку.

819
00:49:14,270 --> 00:49:21,780
Розділені, давайте умовно називаємо її, де т число пов'язаних списків

820
00:49:21,780 --> 00:49:24,500
що ми маємо в цій вертикальній осі.

821
00:49:24,500 --> 00:49:27,180
Іншими словами, якщо ми дійсно вважати рівномірним розподілом імен,

822
00:49:27,180 --> 00:49:30,150
абсолютно нереально. Там, очевидно ще деяких букв, ніж інші.

823
00:49:30,150 --> 00:49:32,580
>> Але якщо ми припустимо, на даний момент рівномірний розподіл,

824
00:49:32,580 --> 00:49:37,350
і ми п повних людей, і м загальної ланцюга

825
00:49:37,350 --> 00:49:40,630
наявні у нас, то довжина кожної з цих ланцюгів

826
00:49:40,630 --> 00:49:44,380
достатньо просто буде загальний, п ділиться на кількість ланцюгів.

827
00:49:44,380 --> 00:49:48,900
Таким чином, п / т. Але от де ми можемо бути математично всі розумні.

828
00:49:48,900 --> 00:49:53,030
м є постійним, тому що там фіксоване число з них.

829
00:49:53,030 --> 00:49:54,620
Ви збираєтеся оголосити масив на початку,

830
00:49:54,620 --> 00:49:58,450
і ми не зміна розміру вертикальної осі. За визначенням, яка залишається фіксованою.

831
00:49:58,450 --> 00:50:01,220
Це тільки по горизонтальній осі, так би мовити, все змінюється.

832
00:50:01,220 --> 00:50:04,760
Таким чином, технічно, це константа. Так що тепер, час вставки

833
00:50:04,760 --> 00:50:09,700
в значній мірі O (N).

834
00:50:09,700 --> 00:50:12,410
Так що не відчуває себе все, що набагато краще.

835
00:50:12,410 --> 00:50:14,940
Але те, що тут правда? Ну, все це час, протягом тижнів,

836
00:50:14,940 --> 00:50:20,640
ми говорили O (N ²). О (п), 2 х п ², - я, діленої на 2. . . Чеха.

837
00:50:20,640 --> 00:50:23,580
Це просто п ². Але зараз, в цій частині семестру,

838
00:50:23,580 --> 00:50:25,560
ми можемо почати говорити про реальний світ знову.

839
00:50:25,560 --> 00:50:31,520
А п / т абсолютно швидше, ніж просто п поодинці.

840
00:50:31,520 --> 00:50:35,170
Якщо у вас є тисячі імен, і ви розбити їх на кілька ковшів

841
00:50:35,170 --> 00:50:37,820
так що у вас тільки десять імен у кожній із цих ланцюгів,

842
00:50:37,820 --> 00:50:41,670
Абсолютно пошуку Десять речей, це буде швидше, ніж тисяча речей.

843
00:50:41,670 --> 00:50:43,740
І ось одна з безлічі майбутніх проблема буде вам виклик

844
00:50:43,740 --> 00:50:46,100
думати саме про те, що, хоча, так,

845
00:50:46,100 --> 00:50:49,520
асимптотично і математично, це ще тільки лінійні,

846
00:50:49,520 --> 00:50:51,700
яка всмоктує в цілому, намагаючись знайти речі.

847
00:50:51,700 --> 00:50:54,530
Насправді, це буде швидше, ніж

848
00:50:54,530 --> 00:50:56,520
через це дільника.

849
00:50:56,520 --> 00:50:58,310
І там знову буде цей компроміс

850
00:50:58,310 --> 00:51:01,390
і цей конфлікт між теорією і реальністю,

851
00:51:01,390 --> 00:51:03,550
і одним з регуляторів почне обертатися в цей момент в семестр

852
00:51:03,550 --> 00:51:07,510
Більш реальності один, як ми ніби як готуватися до кінця semster, в

853
00:51:07,510 --> 00:51:09,280
як ми введемо в світі веб-програмування,

854
00:51:09,280 --> 00:51:11,530
де дійсно, продуктивність буде розраховувати, тому що ваші користувачі будуть

855
00:51:11,530 --> 00:51:14,880
починають відчувати і цінувати бідних дизайнерських рішень.

856
00:51:14,880 --> 00:51:19,950
>> Отже, як ви йти про реалізацію пов'язаних - хеш-таблицю з 31 елементами?

857
00:51:19,950 --> 00:51:22,600
А попередній приклад був довільним про дні народження.

858
00:51:22,600 --> 00:51:26,190
Якщо у когось є день народження 1 січня або 1 лютого, ми помістимо їх в цьому відрі.

859
00:51:26,190 --> 00:51:28,960
Якщо це 2 січня, 2 лютого, 2 березня, ми помістимо їх в цьому відрі.

860
00:51:28,960 --> 00:51:32,220
Ось чому він був 31 рік. Як ви оголосите хеш-таблиці?

861
00:51:32,220 --> 00:51:37,480
Це може бути досить простим, вузол таблиці * моє довільне ім'я для нього, [31].

862
00:51:37,480 --> 00:51:42,400
Це дає мені 31 покажчиків на вузли,

863
00:51:42,400 --> 00:51:45,370
і який дозволяє мені є 31 покажчиків на пов'язані списки

864
00:51:45,370 --> 00:51:48,800
навіть якщо ці мережі споконвічно NULL.

865
00:51:48,800 --> 00:51:54,860
Що я хочу поставити, якщо я хочу зберегти "Аліса", "Боб", "Чарлі"?

866
00:51:54,860 --> 00:51:57,010
Ну, нам потрібно, щоб обернути ці речі в структурі

867
00:51:57,010 --> 00:52:00,530
бо нам потрібна Аліса, щоб вказати на Боба, щоб вона вказувала на Чарлі, і так далі.

868
00:52:00,530 --> 00:52:04,940
Ми не можемо просто мають імена в поодинці, тому я міг би створити нову структуру під назвою вузла тут.

869
00:52:04,940 --> 00:52:08,310
>> Що таке фактичне вузла? Що таке вузол у цій новій зв'язаний список?

870
00:52:08,310 --> 00:52:11,840
В першу чергу, називається словом, для імені людини.

871
00:52:11,840 --> 00:52:14,340
ДОВЖИНА, мабуть, відноситься до максимальної довжині імені людини, в

872
00:52:14,340 --> 00:52:18,210
що б це, 20, 30, 40 символів в божевільний випадках кут,

873
00:52:18,210 --> 00:52:22,680
і +1 для чого? Це просто додатковий символ NULL, \ 0.

874
00:52:22,680 --> 00:52:27,410
Таким чином, цей вузол упаковка "щось" усередині себе,

875
00:52:27,410 --> 00:52:29,640
але він також оголошує покажчик називається наступна

876
00:52:29,640 --> 00:52:32,580
так що ми можемо ланцюга Аліси до Боба Чарлі і так далі.

877
00:52:32,580 --> 00:52:36,700
Може бути NULL, але не обов'язково повинні бути.

878
00:52:36,700 --> 00:52:40,110
Будь-які питання по цим хеш-таблиці? Так?

879
00:52:40,110 --> 00:52:46,190
[Студент задаючи питання, нерозбірливо] масиву - хороше питання.

880
00:52:46,190 --> 00:52:50,120
Чому це символ слова в масиві, а не просто символ *?

881
00:52:50,120 --> 00:52:53,830
У цьому кілька довільно, наприклад, я не хочу, щоб вдаватися

882
00:52:53,830 --> 00:52:56,190
в Танос для кожного з оригінальної назви.

883
00:52:56,190 --> 00:52:59,530
Я хотів би оголосити максимальний обсяг пам'яті для рядка

884
00:52:59,530 --> 00:53:06,020
так що я міг скопіювати в структуру Alice \ 0, а не мати справу з Танос і безкоштовні тощо.

885
00:53:06,020 --> 00:53:11,710
Але я можу зробити, якщо я хотів бути більш свідомими використання простору. Хороше питання.

886
00:53:11,710 --> 00:53:14,780
Отже, давайте спробуємо узагальнити від цієї

887
00:53:14,780 --> 00:53:18,350
і зосередитися залишок сьогодні на структури даних в цілому

888
00:53:18,350 --> 00:53:21,170
та інші проблеми, які можна вирішити з використанням тих же засадах

889
00:53:21,170 --> 00:53:24,590
навіть якщо дані структури самі можуть відрізнятися в деталях.

890
00:53:24,590 --> 00:53:27,910
>> Виходить у галузі комп'ютерних наук, дерева дуже поширені.

891
00:53:27,910 --> 00:53:29,760
І ви можете думати про дерево зразок генеалогічного дерева,

892
00:53:29,760 --> 00:53:31,830
де є деякі корені, деякі матріархом або патріарха,

893
00:53:31,830 --> 00:53:34,540
Бабуся або дідусь чи більш ранні назад,

894
00:53:34,540 --> 00:53:38,880
під якою є мама і тато або різні братів і сестер тощо.

895
00:53:38,880 --> 00:53:42,500
Таким чином, структура дерева має вузли і має дітей,

896
00:53:42,500 --> 00:53:45,260
зазвичай 0 або більше дітей, для кожного вузла.

897
00:53:45,260 --> 00:53:47,320
І деякі з жаргону, який ви бачите на цій картинці тут

898
00:53:47,320 --> 00:53:50,630
будь-яка з маленьких дітей чи онуків по краях

899
00:53:50,630 --> 00:53:52,330
, Які не мають стрілки, витікаючі з них,

900
00:53:52,330 --> 00:53:55,070
ті так звані листям, і кожен, на внутрішній

901
00:53:55,070 --> 00:53:58,790
є внутрішнім вузлом, ви можете це назвати уздовж цих ліній.

902
00:53:58,790 --> 00:54:01,430
Але ця структура є досить поширеним явищем. Це одна трохи довільним.

903
00:54:01,430 --> 00:54:04,930
У нас одна дитина на лівій, у нас є троє дітей праворуч,

904
00:54:04,930 --> 00:54:06,830
двоє дітей в лівому нижньому кутку.

905
00:54:06,830 --> 00:54:10,740
Таким чином, ми можемо мати різних розмірів дерев, але якщо ми почнемо по стандартизації речі,

906
00:54:10,740 --> 00:54:15,330
і ви, можливо, пам'ятаєте це з відео Патріка на бінарний пошук від попередньої короткої

907
00:54:15,330 --> 00:54:19,490
Інтернет, бінарний пошук не повинен бути реалізований за допомогою масиву

908
00:54:19,490 --> 00:54:21,410
або шматочки паперу на дошці.

909
00:54:21,410 --> 00:54:25,490
Припустимо, що ви хочете зберегти ваші номери в більш складні структури даних.

910
00:54:25,490 --> 00:54:27,680
Ви можете створити дерево, як це.

911
00:54:27,680 --> 00:54:35,290
Ви могли б вузлом оголошений в C, і що вузол може мати не менше двох елементів усередині нього.

912
00:54:35,290 --> 00:54:39,470
Одним з них є номер, який ви хочете зберегти, а інший - добре, нам потрібен ще один.

913
00:54:39,470 --> 00:54:41,540
Інший своїх дітей.

914
00:54:41,540 --> 00:54:45,150
Так ось інша структура даних. На цей раз, вузол визначається як збереження числа п

915
00:54:45,150 --> 00:54:49,060
, А потім два покажчика, ліва і права дитини дитині.

916
00:54:49,060 --> 00:54:52,100
І вони не довільні. Що цікаво, про це дерево?

917
00:54:52,100 --> 00:55:00,550
>> Що таке шаблон в тому, як ми заклали на це або як Патрік поставив його у своєму відео?

918
00:55:00,550 --> 00:55:02,790
Це свого роду очевидно, що є деякі сортування відбувається тут,

919
00:55:02,790 --> 00:55:04,460
але те, що це просте правило? Так?

920
00:55:04,460 --> 00:55:08,350
[Студент відповідь, нерозбірливо]

921
00:55:08,350 --> 00:55:12,040
Perfect. Якщо поглянути на це, ви побачите невелике число зліва,

922
00:55:12,040 --> 00:55:14,690
великі цифри на лівій, але це вірно для кожного вузла.

923
00:55:14,690 --> 00:55:20,370
Для кожного вузла, його ліва дитини менше, ніж він, і його право дитини більше, ніж він.

924
00:55:20,370 --> 00:55:25,210
Що це означає тепер, якщо я хочу знайти цю структуру даних, скажімо, числа 44,

925
00:55:25,210 --> 00:55:29,320
Я повинен почати з кореня, так як у всіх цих більш складних структур даних зараз,

926
00:55:29,320 --> 00:55:31,910
у нас є тільки покажчик на одному, самому початку.

927
00:55:31,910 --> 00:55:35,010
І в цьому випадку, початок кореня. Це не лівому краю,

928
00:55:35,010 --> 00:55:39,530
це корінь цієї структури. Так що я бачу ось 55, і я шукаю 44.

929
00:55:39,530 --> 00:55:41,430
В якому напрямку ви хочете поїхати?

930
00:55:41,430 --> 00:55:45,680
Ну, я хочу піти наліво, тому що, очевидно, справа буде занадто великим.

931
00:55:45,680 --> 00:55:49,050
Таким чином, помітити тут, ти ніби концептуально рубки дерев в два рази

932
00:55:49,050 --> 00:55:51,700
тому що ви ніколи не спускаючись у праву сторону.

933
00:55:51,700 --> 00:55:55,410
Так що тепер я йду від 55 до 33. Це занадто мале число.

934
00:55:55,410 --> 00:56:01,590
Я шукаю 44 років, але тепер я знаю, якщо 44, в цьому дереві, я можу піти, очевидно, з правого боку.

935
00:56:01,590 --> 00:56:04,460
Отже, ще раз, я обрізку дерев у два рази.

936
00:56:04,460 --> 00:56:06,780
Це в значній мірі ідентичні концептуально в телефонну книгу.

937
00:56:06,780 --> 00:56:09,510
Це ідентично тому, що ми зробили з паперу на дошку,

938
00:56:09,510 --> 00:56:13,940
але це більш складна структура, яка дозволяє нам насправді

939
00:56:13,940 --> 00:56:16,880
це розділяй і володарюй дизайн алгоритму,

940
00:56:16,880 --> 00:56:19,420
і справді, проходячи структури, як це - вигуки.

941
00:56:19,420 --> 00:56:22,870
Обхід структури, як це, де це тільки "йти по цьому шляху або йти по цьому шляху",

942
00:56:22,870 --> 00:56:26,870
означає, що все, що код, який нахилився ваш розум в першу чергу при його здійсненні у розділі

943
00:56:26,870 --> 00:56:31,270
або пішки через неї вдома, для бінарного пошуку, за допомогою рекурсії або ітерації,

944
00:56:31,270 --> 00:56:35,060
це біль в шиї. Знайти середнього елемента, то зробити вашу округлення вгору або вниз.

945
00:56:35,060 --> 00:56:39,230
>> Там в красі цього, тому що тепер ми можемо використовувати рекурсію знову,

946
00:56:39,230 --> 00:56:43,760
але набагато більш акуратно. У самому справі, якщо ви на число 55, і ви хочете, щоб знайти 44,

947
00:56:43,760 --> 00:56:48,450
Ви йдіть наліво в цьому випадку, те, що ви робите? Ви запускаєте той же алгоритм.

948
00:56:48,450 --> 00:56:51,560
Ви перевіряєте значення вузла, то ви йдете вліво або вправо.

949
00:56:51,560 --> 00:56:53,670
Потім ви перевіряєте значення вузла, перейдіть ліворуч чи праворуч.

950
00:56:53,670 --> 00:56:56,710
Це ідеально підходить для рекурсії.

951
00:56:56,710 --> 00:57:00,920
Так що, хоча в минулому ми зробили деякі досить довільні приклади з участю рекурсії

952
00:57:00,920 --> 00:57:03,430
, Які не повинні бути рекурсивними, з даними СТРУКТУР,

953
00:57:03,430 --> 00:57:07,820
Особливо дерева, це ідеальне застосування цієї ідеї з проблемою,

954
00:57:07,820 --> 00:57:12,920
скорочення її, а потім рішення того ж типу, але меншого, програми.

955
00:57:12,920 --> 00:57:14,590
>> Так що є інша структура даних, ми можемо ввести.

956
00:57:14,590 --> 00:57:18,760
Це одна призначена на перший погляд виглядають загадково, але це дивно.

957
00:57:18,760 --> 00:57:25,090
Так що це структури даних, називаної вигляді дерева, Trie, який успадковується від слова пошуку,

958
00:57:25,090 --> 00:57:30,210
які не вимовляються знову спробувати-вал, але це те, що світ називає ці речі. Намагається. Т-т-і-і.

959
00:57:30,210 --> 00:57:35,190
Він являє собою деревоподібну структуру якийсь, але кожен з вузлів у вигляді дерева

960
00:57:35,190 --> 00:57:41,280
здається, що? І це трохи вводить в оману, тому що це свого роду скороченим.

961
00:57:41,280 --> 00:57:45,960
Але, схоже, кожен вузол в цьому Trie насправді є масивом.

962
00:57:45,960 --> 00:57:48,840
І хоча автор цієї схемі не показано це,

963
00:57:48,840 --> 00:57:54,130
В даному випадку, це Trie це структура даних, мета якого в житті, щоб зберігати слова

964
00:57:54,130 --> 00:57:57,330
як-л-і-з-е-або В-О-В.

965
00:57:57,330 --> 00:58:02,480
І те, яким чином ця Аліса сховищ даних і Боб і Чарлі і Аніта і т. д.

966
00:58:02,480 --> 00:58:06,970
воно використовує масив для зберігання яких Аліса в вигляді дерева,

967
00:58:06,970 --> 00:58:09,820
ми починаємо з кореневого вузла, який виглядає як масив,

968
00:58:09,820 --> 00:58:12,080
і це було написано в скороченій формі.

969
00:58:12,080 --> 00:58:15,070
Автор опущені ABCDEFG, тому що не було ніяких імен з цим.

970
00:58:15,070 --> 00:58:19,150
Вони тільки показали М і Р і Т, але в даному випадку,

971
00:58:19,150 --> 00:58:22,780
давайте перейдемо від Аліса і Боб і Чарлі деякі імена, які знаходяться тут.

972
00:58:22,780 --> 00:58:25,670
Максвелл насправді в цій схемі.

973
00:58:25,670 --> 00:58:29,570
Так як же автор магазині M - х-ш-е-л-л?

974
00:58:29,570 --> 00:58:36,990
Він або вона почалася в кореневий вузол, і пішов [M], таким чином, приблизно 13, 13 місце в масиві.

975
00:58:36,990 --> 00:58:40,750
Потім звідти, є покажчик.

976
00:58:40,750 --> 00:58:42,760
Покажчиків, що ведуть до іншої масив.

977
00:58:42,760 --> 00:58:47,880
Звідти автор індексуватися в цей масив на місці, як показано там в лівому верхньому кутку,

978
00:58:47,880 --> 00:58:52,250
і тоді він або вона випливає, що покажчик на інший масив,

979
00:58:52,250 --> 00:58:55,460
і пішов до покажчика на місце X.

980
00:58:55,460 --> 00:58:59,840
Тоді в наступний масив розташування W, E, L, L, і так далі,

981
00:58:59,840 --> 00:59:03,090
І, нарешті, давайте насправді намагаються поставити картину до цього.

982
00:59:03,090 --> 00:59:05,380
Що робить вузол виглядає в коді?

983
00:59:05,380 --> 00:59:11,820
Вузлі у вигляді дерева містить масив покажчиків на кількох вузлах.

984
00:59:11,820 --> 00:59:16,090
Але є і повинен бути свого роду логічне значення, принаймні, в цій реалізації.

985
00:59:16,090 --> 00:59:18,770
Я, трапляється, називають його is_word. Чому?

986
00:59:18,770 --> 00:59:22,670
Тому що, коли ви вставки Максвел, ви не вставляючи

987
00:59:22,670 --> 00:59:25,300
нічого в цій структурі даних.

988
00:59:25,300 --> 00:59:27,480
Ви не пишете M. ви не пишете X.

989
00:59:27,480 --> 00:59:30,240
Все, що ви робите, наступні покажчики.

990
00:59:30,240 --> 00:59:33,360
Покажчик, що представляє М, то покажчик, який представляє,

991
00:59:33,360 --> 00:59:36,310
Потім покажчик, який представляє X, то W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
але те, що вам потрібно зробити, врешті начебто піти, перевірити, я добрався до цього місця.

993
00:59:41,950 --> 00:59:45,560
Існував слово, яке закінчується в структурі даних.

994
00:59:45,560 --> 00:59:48,190
>> Так що Trie дійсно наповнений і автор вибрав в якості представника

995
00:59:48,190 --> 00:59:51,880
ці terminuses з невеликими трикутниками.

996
00:59:51,880 --> 00:59:56,470
Це просто означає, що факт цей трикутник тут, це логічне значення істини

997
00:59:56,470 --> 00:59:59,200
означає, що якщо ви йдете назад в дерево,

998
00:59:59,200 --> 01:00:02,420
, Що означає слово імені Максвелла в цьому.

999
01:00:02,420 --> 01:00:04,870
Але слово Фу, наприклад,

1000
01:00:04,870 --> 01:00:07,970
Не в дереві, тому що якщо я почну в кореневому вузлі тут на вершині,

1001
01:00:07,970 --> 01:00:14,030
Там немає F покажчик, покажчик не про, немає покажчиків о. Foo це не ім'я, в цьому словнику.

1002
01:00:14,030 --> 01:00:22,460
Але на відміну від, Тьюринг, т-у-т-и-н-г. Знову ж таки, я не зберігайте т або й чи г або я або н або р.

1003
01:00:22,460 --> 01:00:29,820
Але я зробив магазин в цю структуру даних значення істинний шлях тут, у цьому вузлі - в дерево

1004
01:00:29,820 --> 01:00:33,030
, Встановивши для цього логічне значення is_word до істини.

1005
01:00:33,030 --> 01:00:35,740
Так Trie це свого роду це дуже цікаво мета структури,

1006
01:00:35,740 --> 01:00:39,810
де ви дійсно не зберігання самих слів для такого роду словник.

1007
01:00:39,810 --> 01:00:45,100
Щоб було ясно, що ви просто зберігати так чи ні, є слово, яке закінчується тут.

1008
01:00:45,100 --> 01:00:46,430
>> Тепер те, що мається на увазі?

1009
01:00:46,430 --> 01:00:51,120
Якщо у вас є 150 тисяч слів у словнику, що ви намагаєтеся зберегти в пам'яті

1010
01:00:51,120 --> 01:00:53,400
використовуючи щось на зразок пов'язаного списку,

1011
01:00:53,400 --> 01:00:56,870
Ви будете мати 150000 вузлів у зв'язаному списку.

1012
01:00:56,870 --> 01:01:00,250
І, знайшовши одне з цих слів в алфавітному порядку може прийняти O (п).

1013
01:01:00,250 --> 01:01:04,370
Лінійне час. Але у випадку тут вигляді дерева,

1014
01:01:04,370 --> 01:01:09,210
що час роботи знайти слова?

1015
01:01:09,210 --> 01:01:17,390
Виявляється, краса тут є те, що навіть якщо у вас уже 149999 слів у цьому словнику,

1016
01:01:17,390 --> 01:01:20,170
як це реалізовано з цією структурою даних,

1017
01:01:20,170 --> 01:01:25,560
Скільки часу потрібно для того, щоб знайти або вставити ще одна людина в тому, як Аліса, Аліса?

1018
01:01:25,560 --> 01:01:30,640
Ну, це тільки 5, може бути 6 кроків для заднього характер.

1019
01:01:30,640 --> 01:01:32,880
Тому що presense інших імен в структурі

1020
01:01:32,880 --> 01:01:35,340
не заважати вставки Аліса.

1021
01:01:35,340 --> 01:01:39,640
Крім того, знаходження Аліса відразу виникають 150000 слів у цьому словнику

1022
01:01:39,640 --> 01:01:41,960
не стояти на шляху знаходження Аліса взагалі,

1023
01:01:41,960 --> 01:01:46,880
тому що Еліс. . . . . тут, тому що я знайшов логічне значення.

1024
01:01:46,880 --> 01:01:50,920
А якщо немає логічне правда, то Аліса не в цій структурі даних слів.

1025
01:01:50,920 --> 01:01:56,220
Іншими словами, час роботи таких речей і вставки речей в цій новій

1026
01:01:56,220 --> 01:02:01,920
Структура даних Trie є O з - це не п.

1027
01:02:01,920 --> 01:02:05,730
Тому що presense з 150.000 чоловік ніяк не впливає на Алісу, здається.

1028
01:02:05,730 --> 01:02:11,560
Отже, давайте називати це до, де до максимальної довжини слова англійською мовою

1029
01:02:11,560 --> 01:02:14,050
які, як правило, не більш ніж 20-те символи.

1030
01:02:14,050 --> 01:02:17,940
Таким чином, до-постійна. Таким чином, Святий Грааль, ми, здається, знайшли зараз

1031
01:02:17,940 --> 01:02:26,000
є те, що у вигляді дерева, постійна часу для вставок, для пошуку, для видалення.

1032
01:02:26,000 --> 01:02:29,170
Оскільки кількість речей вже в структурі,

1033
01:02:29,170 --> 01:02:32,600
які не є навіть фізично там. Знову ж таки, вони тільки вид відзначитися, так чи ні,

1034
01:02:32,600 --> 01:02:35,050
не впливає на його майбутнє час роботи.

1035
01:02:35,050 --> 01:02:37,940
>> Але там повинен бути улову, в іншому випадку ми б не витратили так багато часу

1036
01:02:37,940 --> 01:02:41,460
на всіх цих інших структур даних, просто щоб, нарешті, дістатися до секретної що диву даєшся.

1037
01:02:41,460 --> 01:02:46,410
Так що ціну ми платимо для досягнення цієї величі тут? Простору.

1038
01:02:46,410 --> 01:02:49,010
Ця річ має масовий характер. І причина того, що автор

1039
01:02:49,010 --> 01:02:52,400
не представляли його тут, зауважимо, що всі ці речі, які виглядають як масиви,

1040
01:02:52,400 --> 01:02:55,400
Він не зробив іншу частину дерева, інша частина синтаксичного дерева,

1041
01:02:55,400 --> 01:02:58,060
тому що вони просто не мають відношення до історії.

1042
01:02:58,060 --> 01:03:01,870
Але всі ці вузли є супер широкий, і кожен вузол в дереві займає

1043
01:03:01,870 --> 01:03:07,780
26 або насправді, може бути 27 символів, тому що в цьому випадку я був у тому числі місця для Апостроф

1044
01:03:07,780 --> 01:03:09,980
так що ми могли б апострофом слова.

1045
01:03:09,980 --> 01:03:14,450
У цьому випадку, ці широкі масиви. Тому, навіть якщо вони не picutured,

1046
01:03:14,450 --> 01:03:18,190
це займає величезну кількість оперативної пам'яті.

1047
01:03:18,190 --> 01:03:20,670
Який може бути штраф, especilly в сучасному обладнанні,

1048
01:03:20,670 --> 01:03:25,650
але це компроміс. Ми отримуємо менше часу витрачати більше простору.

1049
01:03:25,650 --> 01:03:28,580
Так де ж це все відбувається?

1050
01:03:28,580 --> 01:03:32,640
Ну, давайте - давайте подивимося тут.

1051
01:03:32,640 --> 01:03:39,510
Давайте зробимо перехід до цього хлопця тут.

1052
01:03:39,510 --> 01:03:43,450
>> Вірте чи ні, як же весело, як C була в протягом деякого часу,

1053
01:03:43,450 --> 01:03:48,130
Ми наближаємося до того часу в семестрі, де цей час до переходу на більш сучасні речі.

1054
01:03:48,130 --> 01:03:50,950
Речі на більш високому рівні. І хоча протягом наступних кількох тижнів

1055
01:03:50,950 --> 01:03:54,580
ми все ще продовжуємо занурюватися у світ покажчики і керування пам'яттю

1056
01:03:54,580 --> 01:03:57,210
щоб отримати це комфорт, з яким ми можемо розвивати,

1057
01:03:57,210 --> 01:04:01,270
В кінці гри, в кінцевому рахунку ввести, за іронією долі, не в цю мову.

1058
01:04:01,270 --> 01:04:03,330
Ми проведемо, як і 10 хвилин говорив про HTML.

1059
01:04:03,330 --> 01:04:05,950
Все це HTML є мовою розмітки, і те, що мова розмітки

1060
01:04:05,950 --> 01:04:10,220
Саме ці серії відкритих і закритих дужки дужки, які говорять, "зробити цей сміливий"

1061
01:04:10,220 --> 01:04:12,000
'Зробити це курсивом "," зробити це по центру. "

1062
01:04:12,000 --> 01:04:14,250
Це ще не все, що інтелектуально цікава, але це супер корисно.

1063
01:04:14,250 --> 01:04:16,650
І це, звичайно, всюдисущий в ці дні.

1064
01:04:16,650 --> 01:04:19,450
Але те, що потужні про світ HTML і веб-програмування в цілому,

1065
01:04:19,450 --> 01:04:25,910
будує динамічні речі, написання коду на мові PHP або як Python або Ruby, або Java або C #.

1066
01:04:25,910 --> 01:04:30,360
Дійсно, незалежно від вашої мови вибір, і генеруючих HTML динамічно.

1067
01:04:30,360 --> 01:04:32,960
Створення так званих CSS динамічно.

1068
01:04:32,960 --> 01:04:35,810
Каскадні таблиці стилів, які також про естетику.

1069
01:04:35,810 --> 01:04:41,360
І тому навіть сьогодні, якщо я йду на сайт як деякі знайомі Google.com,

1070
01:04:41,360 --> 01:04:46,100
і я йду, щоб подивитися, розробник, вид джерела, який, може бути, ви зробили перш,

1071
01:04:46,100 --> 01:04:49,800
але збираюся переглянути вихідний код, цей матеріал, ймовірно, виглядає досить загадково.

1072
01:04:49,800 --> 01:04:55,320
Але це вихідний код, що реалізовує Google.com.

1073
01:04:55,320 --> 01:04:57,940
На передньому кінці. А насправді все це пухнасті речі естетики.

1074
01:04:57,940 --> 01:05:01,740
Це CSS тут. Якщо я буду прокрутки вниз, ми отримаємо деякі кольорові речі.

1075
01:05:01,740 --> 01:05:06,890
Це HTML. Код Google виглядає як безлад, але якщо я насправді відкриває інше вікно,

1076
01:05:06,890 --> 01:05:09,380
ми можемо бачити деякі структури до цього.

1077
01:05:09,380 --> 01:05:12,640
Якби я відкрити це, зауважте, тут, це трохи більш читабельним.

1078
01:05:12,640 --> 01:05:16,850
Ми збираємося, щоб побачити незабаром цей тег, [слово] тег,

1079
01:05:16,850 --> 01:05:23,520
HTML, голови, тіла, DIV, сценарій, текст області, служби по центру, дів.

1080
01:05:23,520 --> 01:05:26,770
І це теж ніби загадкового виду на перший погляд,

1081
01:05:26,770 --> 01:05:30,890
але все це неподобство слід певним зразкам, і повторювані візерунки,

1082
01:05:30,890 --> 01:05:33,850
так що як тільки ми отримаємо основами, ви зможете написати такий код

1083
01:05:33,850 --> 01:05:37,550
, А потім маніпулювати код, як це, використовуючи ще одну мову, званий JavaScript.

1084
01:05:37,550 --> 01:05:40,440
І JavaScript є мовою, який працює всередині браузера

1085
01:05:40,440 --> 01:05:44,380
Сьогодні, яку ми використовуємо на курсах Гарварду, для інструменту курс покупки, які використовують карти Google

1086
01:05:44,380 --> 01:05:48,660
, Щоб дати вам цілу купу динамізм, Facebook дає вам показати миттєві оновлення статусу,

1087
01:05:48,660 --> 01:05:51,430
Twitter використовує це, щоб показати вам, замітки в соціальних мережах миттєво.

1088
01:05:51,430 --> 01:05:53,820
Все це ми почнемо занурюватися дюйма

1089
01:05:53,820 --> 01:05:57,190
Але щоб потрапити туди, ми повинні зрозуміти дещо про Інтернет.

1090
01:05:57,190 --> 01:06:01,130
Цей кліп тут знаходиться всього в хвилині довго, і припустимо, на даний момент це, по суті,

1091
01:06:01,130 --> 01:06:08,380
як працює Інтернет, як дразнилка для того, що ось-ось прийде. Я даю вам "Воїни Мережі".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Повільна музика хор ♫]

1093
01:06:14,720 --> 01:06:20,450
[Чоловік оповідача] Він прийшов із повідомленням.

1094
01:06:20,450 --> 01:06:23,770
З протоколом все своє.

1095
01:06:23,770 --> 01:06:37,270
[♫ швидка електронна музика ♫]

1096
01:06:37,270 --> 01:06:41,330
Він прийшов у світ прохолодно брандмауери, маршрутизатори байдуже,

1097
01:06:41,330 --> 01:06:45,690
і небезпек набагато гірше, ніж смерть.

1098
01:06:45,690 --> 01:06:55,400
Він швидкий. Він сильний. Він TCP / IP, і у нього є свою адресу.

1099
01:06:55,400 --> 01:06:59,250
Воїни в Мережі.

1100
01:06:59,250 --> 01:07:05,290
[Малан] На наступному тижні, то. Інтернет. Веб-програмування. Це CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]