1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Minggu 6, Sambungan]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Universiti Harvard]

3
00:00:04,160 --> 00:00:08,720
[Ini adalah CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Ini adalah CS50 dan ini adalah akhir 6 minggu.

5
00:00:12,970 --> 00:00:17,970
Jadi CS50x, salah satu kursus pertama Harvard yang terlibat dalam inisiatif EDX

6
00:00:17,970 --> 00:00:20,590
memang memulakan kerjaya pada hari Isnin lalu.

7
00:00:20,590 --> 00:00:23,460
Jika anda ingin mendapatkan gambaran tentang apa yang orang lain di Internet

8
00:00:23,460 --> 00:00:27,180
kini mengikuti bersama-sama dengan, anda boleh menuju kepada x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Itu akan mengarahkan anda ke tempat yang sesuai pada edx.org,

10
00:00:30,350 --> 00:00:34,160
yang mana ini dan kursus-kursus lain dari MIT dan Berkeley kini hidup.

11
00:00:34,160 --> 00:00:38,140
Anda perlu mendaftar untuk akaun, anda akan mendapati bahawa bahan adalah sebahagian besarnya sama

12
00:00:38,140 --> 00:00:42,170
kerana anda telah semester ini, walaupun beberapa minggu ditangguhkan, kerana kita akan mendapat segala-galanya yang bersedia.

13
00:00:42,170 --> 00:00:46,930
Tetapi apa yang pelajar di CS50x sekarang akan melihat adalah satu antara muka agak seperti yang satu ini.

14
00:00:46,930 --> 00:00:50,040
Ini, misalnya, adalah Zamyla memimpin Walkthrough untuk menetapkan masalah 0.

15
00:00:50,040 --> 00:00:54,230
Apabila pembalakan di untuk edx.org, seorang pelajar CS50x melihat pelbagai perkara

16
00:00:54,230 --> 00:00:57,170
anda akan mengharapkan untuk melihat dalam kursus: kuliah untuk Isnin,

17
00:00:57,170 --> 00:01:01,650
ceramah untuk Rabu, seluar pendek, pelbagai set masalah, walkthroughs, PDF.

18
00:01:01,650 --> 00:01:04,459
Di samping itu, seperti yang anda lihat di sini mesin terjemahan,

19
00:01:04,459 --> 00:01:08,390
transkrip bahasa Inggeris ke dalam bahasa Cina, Jepun, Sepanyol, Itali,

20
00:01:08,390 --> 00:01:12,810
dan sekumpulan seluruh bahasa-bahasa lain yang pastinya akan menjadi tidak sempurna

21
00:01:12,810 --> 00:01:15,840
seperti yang kita melancarkan mereka keluar programatik menggunakan sesuatu yang dipanggil API,

22
00:01:15,840 --> 00:01:18,360
atau antara muka pemprograman aplikasi, dari Google

23
00:01:18,360 --> 00:01:21,360
yang membolehkan kita untuk menukar bahasa Inggeris kepada bahasa-bahasa lain.

24
00:01:21,360 --> 00:01:24,100
Tetapi terima kasih kepada semangat indah beberapa sukarelawan yang seratus-campur,

25
00:01:24,100 --> 00:01:26,940
orang rawak di Internet yang telah sila ditawarkan untuk terlibat

26
00:01:26,940 --> 00:01:30,180
dalam projek ini, kita secara beransur-ansur akan meningkatkan kualiti terjemahan mereka

27
00:01:30,180 --> 00:01:35,790
dengan mempunyai manusia membetulkan kesilapan yang komputer kita telah dibuat.

28
00:01:35,790 --> 00:01:42,330
>> Jadi ia bertukar keluar kita telah beberapa ramai pelajar muncul pada hari Isnin daripada kita mulanya dijangka.

29
00:01:42,330 --> 00:01:48,980
Malah, kini CS50x mempunyai 100,000 orang yang mengikuti bersama-sama di rumah.

30
00:01:48,980 --> 00:01:54,430
Jadi menyedari anda semua adalah sebahagian daripada ini kelas sulung membuat kursus ini dalam bidang sains komputer

31
00:01:54,430 --> 00:01:57,370
pendidikan lebih amnya, lebih meluas, diakses.

32
00:01:57,370 --> 00:02:00,130
Dan realitinya kini, dengan beberapa kursus-kursus dalam talian secara besar-besaran,

33
00:02:00,130 --> 00:02:04,070
mereka semua bermula dengan nombor-nombor yang sangat tinggi, seperti yang kita seolah-olah telah dilakukan di sini.

34
00:02:04,070 --> 00:02:08,759
Tetapi matlamat, akhirnya, untuk CS50x adalah benar-benar untuk mendapatkan seberapa banyak orang ke garisan penamat mungkin.

35
00:02:08,759 --> 00:02:12,000
Oleh reka bentuk, CS50x akan ditawarkan daripada ini hari Isnin yang lepas

36
00:02:12,000 --> 00:02:17,430
sepanjang jalan melalui April 15, 2013, supaya orang yang mempunyai komitmen sekolah di tempat lain,

37
00:02:17,430 --> 00:02:20,990
kerja, keluarga, konflik lain dan sebagainya, mempunyai fleksibiliti sedikit lebih

38
00:02:20,990 --> 00:02:23,640
dengan yang menyelam ke dalam kursus ini, yang mencukupi untuk mengatakan,

39
00:02:23,640 --> 00:02:30,540
agak ambitiously dilakukan jika hanya sepanjang hanya tiga bulan pada semester biasa.

40
00:02:30,540 --> 00:02:34,190
Tetapi pelajar-pelajar ini akan menangani set masalah yang sama, melihat kandungan yang sama,

41
00:02:34,190 --> 00:02:36,350
mempunyai akses ke seluar sama dan sebagainya.

42
00:02:36,350 --> 00:02:38,990
Jadi sedar bahawa kita semua adalah benar-benar bersama-sama ini.

43
00:02:38,990 --> 00:02:42,360
Dan salah satu daripada matlamat akhir CS50x tidak hanya untuk mendapatkan seberapa banyak orang

44
00:02:42,360 --> 00:02:45,720
ke garisan penamat dan memberi mereka ini pemahaman barunya sains komputer

45
00:02:45,720 --> 00:02:49,000
dan pengaturcaraan tetapi juga mempunyai mereka mempunyai pengalaman ini bersama.

46
00:02:49,000 --> 00:02:52,010
Salah satu ciri-ciri yang menentukan 50 di kampus, kita berharap,

47
00:02:52,010 --> 00:02:56,260
telah jenis ini pengalaman perkauman, untuk lebih baik atau untuk lebih teruk, kadang-kadang,

48
00:02:56,260 --> 00:02:59,480
tetapi mempunyai orang-orang ini untuk berpaling ke kiri dan ke kanan,

49
00:02:59,480 --> 00:03:01,830
pejabat jam dan dan hackathon dan saksama.

50
00:03:01,830 --> 00:03:04,560
Ia agak sukar untuk berbuat demikian dalam orang dengan orang dalam talian,

51
00:03:04,560 --> 00:03:10,580
tetapi CS50x akan membuat kesimpulan pada bulan April dengan pertama kalinya Ekspo CS50,

52
00:03:10,580 --> 00:03:13,630
yang akan menjadi adaptasi talian idea kami saksama

53
00:03:13,630 --> 00:03:18,250
di mana beribu-ribu pelajar semua akan dijemput untuk mengemukakan 1 - 2-minit video,

54
00:03:18,250 --> 00:03:22,480
sama ada screencast projek akhir mereka atau video mereka melambai hello

55
00:03:22,480 --> 00:03:24,490
dan bercakap tentang projek mereka dan demoing ia,

56
00:03:24,490 --> 00:03:27,610
banyak seperti pendahulunya anda telah dilakukan di sini di kampus adil,

57
00:03:27,610 --> 00:03:31,400
supaya menjelang akhir semester ini, harapan untuk mempunyai pameran global

58
00:03:31,400 --> 00:03:37,080
projek akhir pelajar CS50x ', sama seperti itu yang menanti anda Disember ini di sini di kampus.

59
00:03:37,080 --> 00:03:39,680
Jadi lanjut mengenai bahawa dalam bulan-bulan akan datang.

60
00:03:39,680 --> 00:03:43,640
>> Dengan 100,000 pelajar, walaupun, datang keperluan untuk CA lebih sedikit.

61
00:03:43,640 --> 00:03:47,590
Memandangkan bahawa anda semua terik laluan di sini dan mengambil CS50

62
00:03:47,590 --> 00:03:51,630
beberapa minggu terlebih dahulu melepaskan bahan ini kepada penduduk di EDX,

63
00:03:51,630 --> 00:03:55,330
sedar kita akan suka untuk melibatkan seberapa banyak pelajar kita sendiri yang mungkin dalam inisiatif ini,

64
00:03:55,330 --> 00:03:58,720
semasa semester serta musim sejuk ini dan ini musim bunga akan datang.

65
00:03:58,720 --> 00:04:01,620
Jadi, jika anda mahu untuk mendapatkan terlibat dalam CS50x,

66
00:04:01,620 --> 00:04:07,450
terutamanya menyertai dalam pada Bincangkan CS50x, versi EDX CS50 Bincangkan,

67
00:04:07,450 --> 00:04:10,140
yang ramai daripada anda telah menggunakan di kampus, papan buletin dalam talian,

68
00:04:10,140 --> 00:04:13,040
sila lakukan menuju ke URL yang, marilah kita tahu siapa anda,

69
00:04:13,040 --> 00:04:16,450
kerana kita suka untuk membina satu pasukan pelajar dan kakitangan dan fakulti sama

70
00:04:16,450 --> 00:04:19,630
di kampus yang hanya bermain bersama-sama dan membantu keluar.

71
00:04:19,630 --> 00:04:21,720
Dan apabila mereka melihat satu soalan yang biasa kepada mereka,

72
00:04:21,720 --> 00:04:25,320
anda mendengar seorang pelajar melaporkan pepijat beberapa tempat di luar sana di beberapa negara di Internet,

73
00:04:25,320 --> 00:04:27,450
dan bahawa cincin loceng kerana anda juga mempunyai bahawa isu yang sama

74
00:04:27,450 --> 00:04:32,620
dalam d-dewan sedikit masa lalu, diharapkan maka anda boleh berbunyi di dalam dan berkongsi pengalaman anda sendiri.

75
00:04:32,620 --> 00:04:37,300
Jadi jangan mengambil bahagian jika anda mahu.

76
00:04:37,300 --> 00:04:39,360
>> Kursus sains komputer di Universiti Harvard mempunyai sedikit tradisi,

77
00:04:39,360 --> 00:04:44,730
CS50 kalangan mereka, mempunyai beberapa pakaian, beberapa pakaian, yang anda boleh memakai bangganya

78
00:04:44,730 --> 00:04:49,090
pada akhir semester ini, berkata agak bangganya bahawa anda selesai CS50

79
00:04:49,090 --> 00:04:51,830
dan mengambil CS50 dan sebagainya, dan kami sentiasa cuba untuk melibatkan pelajar

80
00:04:51,830 --> 00:04:54,540
dalam proses ini seberapa banyak yang mungkin, di mana kami menjemput,

81
00:04:54,540 --> 00:04:56,900
sekitar masa ini semester, pelajar untuk mengemukakan reka bentuk

82
00:04:56,900 --> 00:04:59,330
menggunakan Photoshop, atau apa jua alat pilihan anda ingin menggunakan

83
00:04:59,330 --> 00:05:02,330
jika anda seorang pereka, untuk mengemukakan reka bentuk untuk T-shirt dan sweatshirts

84
00:05:02,330 --> 00:05:06,100
dan payung dan bandanas sedikit untuk anjing kita kini mempunyai dan sebagainya.

85
00:05:06,100 --> 00:05:09,370
Dan segala-galanya adalah kemudian - pemenang setiap tahun kemudiannya dipamerkan

86
00:05:09,370 --> 00:05:12,700
di laman web kursus di store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Semuanya dijual pada kos di sana, tetapi laman web hanya berjalan sendiri

88
00:05:15,790 --> 00:05:18,330
dan membolehkan orang ramai untuk memilih warna dan reka bentuk yang mereka suka.

89
00:05:18,330 --> 00:05:20,420
Jadi saya fikir kita hanya akan berkongsi beberapa reka bentuk tahun lepas

90
00:05:20,420 --> 00:05:25,130
yang berada di laman web selain dari yang satu ini di sini, yang merupakan tradisi tahunan.

91
00:05:25,130 --> 00:05:29,410
"Setiap Hari Saya SEG Faultn" adalah salah satu daripada penghujahan tahun lepas,

92
00:05:29,410 --> 00:05:32,290
yang masih ada di sana untuk alumni.

93
00:05:32,290 --> 00:05:35,820
Kami mempunyai satu ini, "CS50, Ditubuhkan 1989."

94
00:05:35,820 --> 00:05:39,010
Salah satu Bowdens kami, Rob, adalah sangat popular pada tahun lepas.

95
00:05:39,010 --> 00:05:43,480
"Pasukan Bowden" dilahirkan, reka bentuk ini telah dikemukakan, antara penjual utama.

96
00:05:43,480 --> 00:05:49,040
Seperti yang satu ini di sini. Ramai orang mempunyai "Demam Bowden" mengikut log jualan.

97
00:05:49,040 --> 00:05:52,650
Sedarlah bahawa kini boleh menjadi reka bentuk anda di sana, di Internet.

98
00:05:52,650 --> 00:05:57,510
Maklumat lanjut mengenai ini dalam masalah seterusnya set datang.

99
00:05:57,510 --> 00:06:00,330
>> Salah satu alat yang lebih: anda mempunyai beberapa pendedahan dan diharapkan kini

100
00:06:00,330 --> 00:06:02,350
beberapa pengalaman hands-on dengan GDB,

101
00:06:02,350 --> 00:06:04,570
yang, sememangnya, penyahpepijat dan membolehkan anda untuk memanipulasi

102
00:06:04,570 --> 00:06:09,500
program anda pada tahap yang agak rendah, melakukan apa jenis perkara?

103
00:06:09,500 --> 00:06:13,030
Apakah GDB membiarkan anda lakukan?

104
00:06:13,030 --> 00:06:15,030
Yeah? Berikan saya sesuatu. [Pelajar jawapan, difahami]

105
00:06:15,030 --> 00:06:18,120
Baik. Langkah ke fungsi, supaya anda tidak hanya perlu menaip menjalankan

106
00:06:18,120 --> 00:06:22,310
dan mempunyai program tamparan menerusi keseluruhannya, mencetak perkara output standard.

107
00:06:22,310 --> 00:06:25,190
Sebaliknya, anda boleh melangkah melalui talian ia demi baris, sama ada menaip seterusnya

108
00:06:25,190 --> 00:06:30,300
untuk pergi baris demi baris demi baris atau langkah untuk menyelam ke dalam fungsi, biasanya satu yang anda menulis.

109
00:06:30,300 --> 00:06:35,240
Apa lagi yang tidak GDB membiarkan anda lakukan? Yeah? [Pelajar jawapan, difahami]

110
00:06:35,240 --> 00:06:38,100
Cetak pembolehubah. Jadi jika anda mahu untuk melakukan introspeksi sedikit dalam program anda

111
00:06:38,100 --> 00:06:41,500
tanpa perlu mengambil jalan untuk menulis pernyataan printf seluruh tempat,

112
00:06:41,500 --> 00:06:44,600
anda hanya boleh mencetak pembolehubah atau memaparkan pembolehubah.

113
00:06:44,600 --> 00:06:46,710
Apa lagi yang anda boleh lakukan dengan penyahpepijat seperti GDB?

114
00:06:46,710 --> 00:06:49,170
[Pelajar jawapan, difahami]

115
00:06:49,170 --> 00:06:52,080
Tepat sekali. Anda boleh menetapkan titik putus, anda boleh mengatakan pelaksanaan rehat

116
00:06:52,080 --> 00:06:54,020
pada fungsi utama atau fungsi foo.

117
00:06:54,020 --> 00:06:56,800
Anda boleh mengatakan pelaksanaan berehat di garisan 123.

118
00:06:56,800 --> 00:06:58,950
Dan titik putus adalah satu teknik yang benar-benar kuat

119
00:06:58,950 --> 00:07:01,110
kerana jika anda mempunyai pemahaman yang umum di mana masalah anda

120
00:07:01,110 --> 00:07:05,360
mungkin, anda tidak perlu membuang masa melangkah melalui keseluruhan program ini.

121
00:07:05,360 --> 00:07:08,250
Anda asasnya boleh melompat di sana dan kemudian mula menaip -

122
00:07:08,250 --> 00:07:10,970
melangkah melaluinya dengan langkah atau seterusnya atau sebagainya.

123
00:07:10,970 --> 00:07:14,340
Tetapi tangkapan dengan sesuatu seperti GDB adalah bahawa ia membantu anda, manusia,

124
00:07:14,340 --> 00:07:16,940
mencari masalah anda dan mencari pepijat anda.

125
00:07:16,940 --> 00:07:19,470
Ia tidak semestinya mencari mereka begitu banyak untuk anda.

126
00:07:19,470 --> 00:07:23,070
>> Jadi kita memperkenalkan style50 hari lain, yang merupakan alat baris arahan pendek

127
00:07:23,070 --> 00:07:27,500
yang cuba untuk menyesuaikan dgn mode kod anda sedikit lebih bersih daripada anda, manusia, mungkin perlu dilakukan.

128
00:07:27,500 --> 00:07:29,530
Tetapi itu juga, adalah benar-benar hanya satu perkara yang estetik.

129
00:07:29,530 --> 00:07:34,110
Tetapi ternyata ada alat ini lain dipanggil Valgrind yang adalah sedikit lebih batin untuk digunakan.

130
00:07:34,110 --> 00:07:36,860
Output adalah atrociously samar pada pandangan pertama.

131
00:07:36,860 --> 00:07:39,420
Tetapi ia adalah hebat berguna, terutama sekarang bahawa kita berada di bahagian istilah

132
00:07:39,420 --> 00:07:43,080
di mana anda mula menggunakan malloc dan peruntukan memori dinamik.

133
00:07:43,080 --> 00:07:45,420
Perkara yang boleh pergi benar-benar, benar-benar salah dengan cepat.

134
00:07:45,420 --> 00:07:49,320
Kerana jika anda lupa untuk membebaskan memori anda, atau anda dereference beberapa penunjuk NULL,

135
00:07:49,320 --> 00:07:55,770
atau anda dereference beberapa penunjuk sampah, apa yang biasanya gejala yang keputusan?

136
00:07:55,770 --> 00:07:59,470
Seg bersalah. Dan anda mendapat fail ini teras bilangan beberapa kilobait atau megabait

137
00:07:59,470 --> 00:08:02,990
yang mewakili negeri memori program anda apabila ia terhempas,

138
00:08:02,990 --> 00:08:05,730
tetapi program anda akhirnya seg kesilapan, kesalahan segmentasi,

139
00:08:05,730 --> 00:08:08,450
yang bermaksud sesuatu yang buruk berlaku hampir sentiasa berkaitan

140
00:08:08,450 --> 00:08:11,750
kepada kesilapan yang berkaitan dengan ingatan bahawa anda membuat suatu tempat.

141
00:08:11,750 --> 00:08:14,100
Jadi Valgrind membantu anda mencari perkara-perkara seperti ini.

142
00:08:14,100 --> 00:08:17,720
Ia adalah satu alat yang anda menjalankan, seperti GDB, selepas anda telah disusun program anda,

143
00:08:17,720 --> 00:08:20,330
tetapi bukannya menjalankan program anda secara langsung, anda menjalankan Valgrind

144
00:08:20,330 --> 00:08:23,960
dan anda lulus program anda, sama seperti anda lakukan dengan GDB.

145
00:08:23,960 --> 00:08:26,220
Kini, penggunaan, untuk mendapatkan jenis pengeluaran terbaik,

146
00:08:26,220 --> 00:08:30,410
sedikit panjang, jadi di sana di atas skrin anda akan melihat Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"V" hampir universal bermakna lantung apabila anda menggunakan program komputer Linux.

148
00:08:35,350 --> 00:08:38,770
Jadi ia bermakna meludah keluar lebih banyak data daripada anda mungkin secara lalai.

149
00:08:38,770 --> 00:08:45,510
"- Kebocoran periksa = penuh." Ini hanya mengatakan cek semua kebocoran memori yang mungkin,

150
00:08:45,510 --> 00:08:49,430
kesilapan yang saya mungkin telah dibuat. Ini juga, adalah satu paradigma yang biasa dengan program-program Linux.

151
00:08:49,430 --> 00:08:52,710
Secara umumnya, jika anda mempunyai hujah baris arahan yang "suis",

152
00:08:52,710 --> 00:08:55,830
yang sepatutnya untuk mengubah tingkah laku program ini, dan ia adalah surat tunggal,

153
00:08:55,830 --> 00:09:00,310
ia-v, tetapi jika itu dihidupkan, hanya dengan reka bentuk pengaturcara,

154
00:09:00,310 --> 00:09:05,150
perkataan penuh atau siri perkataan, hujah baris arahan bermula dengan.

155
00:09:05,150 --> 00:09:08,190
Ini adalah hanya konvensyen manusia, tetapi anda akan melihat mereka semakin.

156
00:09:08,190 --> 00:09:12,410
Dan kemudian, akhirnya, "a.out" adalah nama sewenang-wenangnya untuk program dalam contoh ini tertentu.

157
00:09:12,410 --> 00:09:14,640
Dan di sini adalah beberapa output wakil.

158
00:09:14,640 --> 00:09:22,890
>> Sebelum kita melihat apa yang mungkin bermakna, biarlah saya pergi ke coretan kod di sini.

159
00:09:22,890 --> 00:09:26,390
Dan biarlah saya bergerak ini keluar daripada cara itu, akan datang,

160
00:09:26,390 --> 00:09:32,120
dan mari kita melihat memory.c, yang ini contoh ringkas di sini.

161
00:09:32,120 --> 00:09:36,290
Jadi dalam program ini, izinkan saya mengezum masuk pada fungsi dan soalan.

162
00:09:36,290 --> 00:09:39,430
Kami mempunyai fungsi utama yang memanggil fungsi, f,

163
00:09:39,430 --> 00:09:45,590
dan kemudian apakah f meneruskan untuk berbuat demikian, dalam Bahasa Inggeris sedikit teknikal?

164
00:09:45,590 --> 00:09:49,760
Apakah f meneruskan lakukan?

165
00:09:49,760 --> 00:09:53,680
Bagaimana pula saya akan bermula dengan garis 20, dan lokasi bintang tidak kira,

166
00:09:53,680 --> 00:09:56,720
tetapi saya hanya akan menjadi konsisten sini dengan kuliah terakhir.

167
00:09:56,720 --> 00:09:59,910
Apa garis 20 adakah untuk kita? Pada sebelah kiri. Kami akan memecahkan ia menurunkan lagi.

168
00:09:59,910 --> 00:10:02,410
Int * x: apakah yang lakukan?

169
00:10:02,410 --> 00:10:04,940
Okay. Ia mengisytiharkan penunjuk, dan sekarang mari kita menjadi lebih teknikal.

170
00:10:04,940 --> 00:10:10,230
Apakah ia bermakna, sangat kukuh, untuk mengisytiharkan penunjuk? Orang lain?

171
00:10:10,230 --> 00:10:15,050
Yeah? [Pelajar jawapan, difahami] Terlalu jauh.

172
00:10:15,050 --> 00:10:17,060
Jadi anda membaca untuk sebelah kanan tanda yang sama.

173
00:10:17,060 --> 00:10:20,290
Mari kita memberi tumpuan hanya pada sebelah kiri, hanya pada int * x.

174
00:10:20,290 --> 00:10:24,700
Ini tidak "mengisytiharkan" penunjuk, tetapi sekarang mari menyelam di lebih mendalam kepada takrif itu.

175
00:10:24,700 --> 00:10:28,330
Apakah yang kukuh, teknikal maksudkan? Yeah?

176
00:10:28,330 --> 00:10:31,940
[Pelajar jawapan, difahami]

177
00:10:31,940 --> 00:10:35,090
Okay. Ia bersedia untuk menyelamatkan alamat dalam ingatan.

178
00:10:35,090 --> 00:10:40,680
Baik. Dan mari kita mengambil langkah ini satu lagi, ia mengisytiharkan pembolehubah, x, yang 32-bit.

179
00:10:40,680 --> 00:10:44,440
Dan saya tahu ia adalah 32 bit kerana -?

180
00:10:44,440 --> 00:10:47,390
Ia bukan kerana ia adalah int, kerana ia adalah satu penunjuk dalam kes ini.

181
00:10:47,390 --> 00:10:49,650
Kebetulan bahawa ia adalah satu dan sama dengan int,

182
00:10:49,650 --> 00:10:51,970
tetapi hakikat bahawa terdapat bintang di sana bermakna ini adalah penunjuk

183
00:10:51,970 --> 00:10:57,300
dan perkakas, seperti dengan komputer banyak, tetapi tidak semua, petunjuk adalah 32 bit.

184
00:10:57,300 --> 00:11:01,850
Pada perkakasan yang lebih moden seperti Mac terbaru, PC terbaru, anda mungkin mempunyai petunjuk 64-bit,

185
00:11:01,850 --> 00:11:04,160
tetapi dalam perkakas, perkara-perkara ini adalah 32-bit.

186
00:11:04,160 --> 00:11:08,380
Jadi kita akan menyeragamkan pada itu. Lebih kukuh, cerita pergi seperti berikut:

187
00:11:08,380 --> 00:11:10,820
Kami "mengisytiharkan" penunjuk; apakah itu bermakna?

188
00:11:10,820 --> 00:11:12,810
Kami bersedia untuk menyimpan alamat memori.

189
00:11:12,810 --> 00:11:15,530
Apa maksudnya?

190
00:11:15,530 --> 00:11:19,810
Kami mencipta pembolehubah x dipanggil yang mengambil sehingga 32 bit

191
00:11:19,810 --> 00:11:23,810
yang tidak lama lagi akan menyimpan alamat integer.

192
00:11:23,810 --> 00:11:26,470
Dan itulah mungkin kira-kira sebagai tepat kerana kita boleh mendapatkan.

193
00:11:26,470 --> 00:11:31,810
Ia adalah denda bergerak ke hadapan untuk memudahkan dunia dan hanya mengatakan mengisytiharkan penunjuk dipanggil x.

194
00:11:31,810 --> 00:11:35,380
Isytiharkan penunjuk, tetapi menyedari dan memahami apa yang sebenarnya berlaku di

195
00:11:35,380 --> 00:11:38,490
walaupun dalam beberapa watak.

196
00:11:38,490 --> 00:11:42,040
>> Sekarang, yang satu ini hampir sedikit lebih mudah, walaupun ia adalah satu ungkapan yang lebih lama.

197
00:11:42,040 --> 00:11:48,160
Jadi apa ini lakukan, yang diketengahkan kini: "malloc (10 * sizeof (int));" Ya?

198
00:11:48,160 --> 00:11:52,350
[Pelajar jawapan, difahami]

199
00:11:52,350 --> 00:11:58,250
Baik. Dan saya akan mengambil ia di sana. Ia memperuntukkan sebahagian memori selama sepuluh integer.

200
00:11:58,250 --> 00:12:02,190
Dan sekarang mari kita menyelam di sedikit lebih mendalam, ia memperuntukkan sebahagian memori selama sepuluh integer.

201
00:12:02,190 --> 00:12:05,390
Apa yang malloc kemudian kembali?

202
00:12:05,390 --> 00:12:10,390
Alamat bahawa sebahagian, atau, lebih kukuh, alamat bait pertama sebahagian yang.

203
00:12:10,390 --> 00:12:14,080
Bagaimana pula saya, pengaturcara, tahu di mana bahawa sebahagian berakhir memori?

204
00:12:14,080 --> 00:12:18,340
Saya tahu bahawa ia adalah berdampingan. Malloc, mengikut definisi, akan memberi anda sebahagian memori yang berdampingan.

205
00:12:18,340 --> 00:12:21,240
Tiada jurang di dalamnya. Anda mempunyai akses kepada bait dalam setiap Sebahagian bahawa,

206
00:12:21,240 --> 00:12:26,760
kembali ke belakang ke belakang, tetapi bagaimana saya tahu di mana akhir ini sebahagian daripada memori?

207
00:12:26,760 --> 00:12:28,850
Apabila anda menggunakan malloc? [Pelajar jawapan, difahami].

208
00:12:28,850 --> 00:12:30,670
Anda tidak lakukan. Anda perlu ingat.

209
00:12:30,670 --> 00:12:35,960
Saya perlu ingat bahawa saya menggunakan nilai 10, dan saya tidak seolah-olah telah dilakukan di sini.

210
00:12:35,960 --> 00:12:41,000
Tetapi tanggungjawab sepenuhnya kepada saya. Strlen, yang kita telah menjadi sedikit bergantung pada tali,

211
00:12:41,000 --> 00:12:45,860
hanya berfungsi kerana konvensyen ini mempunyai \ 0

212
00:12:45,860 --> 00:12:48,840
atau ini aksara khas nul, NUL, pada akhir rentetan.

213
00:12:48,840 --> 00:12:51,740
Yang tidak tahan untuk hanya ketulan sewenang-wenangnya memori.

214
00:12:51,740 --> 00:12:58,590
Ia terpulang kepada anda. Jadi line 20, maka, memperuntukkan sebahagian memori

215
00:12:58,590 --> 00:13:02,590
yang boleh menyimpan sepuluh integer, dan ia menyimpan alamat bait pertama

216
00:13:02,590 --> 00:13:05,610
Sebahagian yang memori dalam x ubah dipanggil.

217
00:13:05,610 --> 00:13:11,140
Ergo, yang merupakan penunjuk. Jadi line 21, malangnya, adalah satu kesilapan.

218
00:13:11,140 --> 00:13:16,110
Tetapi pertama, apa yang ia lakukan? Ia mengatakan kedai di lokasi 10, 0 diindeks,

219
00:13:16,110 --> 00:13:19,480
sebahagian memori yang dikenali sebagai x 0 nilai.

220
00:13:19,480 --> 00:13:21,510
>> Jadi notis beberapa perkara yang berlaku.

221
00:13:21,510 --> 00:13:25,420
Walaupun x adalah penunjuk, ingat dari beberapa minggu yang lalu

222
00:13:25,420 --> 00:13:29,440
bahawa anda masih boleh menggunakan pelbagai gaya notasi kurungan persegi.

223
00:13:29,440 --> 00:13:36,180
Kerana itulah sebenarnya trengkas notasi untuk aritmetik penunjuk yang lebih samar-cari.

224
00:13:36,180 --> 00:13:40,320
di mana kita akan melakukan sesuatu seperti ini: Ambil x alamat, bergerak 10 tempat lebih,

225
00:13:40,320 --> 00:13:44,550
kemudian pergi ke sana untuk apa sahaja alamat yang disimpan di lokasi tersebut.

226
00:13:44,550 --> 00:13:48,090
Tetapi terus-terang, ini adalah hanya kejam untuk membaca dan mendapatkan selesa dengan.

227
00:13:48,090 --> 00:13:52,900
Jadi dunia biasanya menggunakan kurungan persegi hanya kerana ia begitu lebih mesra manusia untuk membaca.

228
00:13:52,900 --> 00:13:55,140
Tetapi itulah apa yang benar-benar berlaku di bawah hood;

229
00:13:55,140 --> 00:13:58,190
x adalah alamat, tidak array, per se.

230
00:13:58,190 --> 00:14:02,410
Jadi ini menyimpan 0 di lokasi 10 dalam x.

231
00:14:02,410 --> 00:14:06,120
Mengapa ini buruk? Yeah?

232
00:14:06,120 --> 00:14:17,370
[Pelajar jawapan, difahami] Tepat sekali.

233
00:14:17,370 --> 00:14:21,100
Kami hanya memperuntukkan sepuluh ints, tetapi kita mengira dari 0 apabila pengaturcaraan dalam C,

234
00:14:21,100 --> 00:14:25,690
jadi anda mempunyai akses kepada 0 10 1 2 3 4 5 6 7 8 9, tetapi tidak.

235
00:14:25,690 --> 00:14:30,270
Jadi sama ada program ini akan kesalahan seg atau ia tidak.

236
00:14:30,270 --> 00:14:32,900
Tetapi kita tidak benar-benar tahu; ini adalah jenis tingkah laku nondeterministic.

237
00:14:32,900 --> 00:14:35,600
Ia benar-benar bergantung kepada sama ada kita mendapat bertuah.

238
00:14:35,600 --> 00:14:40,650
Jika ia ternyata bahawa sistem operasi tidak keberatan jika saya menggunakan bahawa bait tambahan,

239
00:14:40,650 --> 00:14:43,360
walaupun ia telah tidak diberikan kepada saya, program saya tidak mungkin kemalangan.

240
00:14:43,360 --> 00:14:46,780
Ia adalah mentah, ia adalah kereta, tetapi anda mungkin tidak melihat gejala yang,

241
00:14:46,780 --> 00:14:48,960
atau anda mungkin melihat ia hanya sekali-sekala.

242
00:14:48,960 --> 00:14:51,230
Tetapi realitinya adalah bahawa pepijat adalah, sebenarnya, ada.

243
00:14:51,230 --> 00:14:54,320
Dan ia adalah benar-benar bermasalah jika anda telah menulis satu program yang anda mahu betul,

244
00:14:54,320 --> 00:14:58,840
bahawa anda telah dijual program yang orang menggunakan bahawa setiap sekali-sekala kemalangan

245
00:14:58,840 --> 00:15:02,450
kerana, sudah tentu, ini tidak baik. Malah, jika anda mempunyai telefon Android atau iPhone

246
00:15:02,450 --> 00:15:05,550
dan anda memuat turun aplikasi pada hari ini, jika anda pernah mempunyai app hanya berhenti,

247
00:15:05,550 --> 00:15:10,040
tiba-tiba ia hilang, yang hampir selalu disebabkan beberapa isu yang berkaitan dengan ingatan,

248
00:15:10,040 --> 00:15:12,830
mana pengaturcara diskrukan sehingga dan dereferenced penunjuk

249
00:15:12,830 --> 00:15:18,670
bahawa dia tidak harus mempunyai, dan hasil daripada IOS atau Android adalah hanya membunuh program ini sama sekali

250
00:15:18,670 --> 00:15:23,080
bukannya kelakuan risiko undefined atau beberapa jenis kompromi keselamatan.

251
00:15:23,080 --> 00:15:25,950
>> Ada satu pepijat lain dalam program ini selain yang satu ini.

252
00:15:25,950 --> 00:15:30,180
Apa lagi yang telah saya diskrukan sehingga dalam program ini?

253
00:15:30,180 --> 00:15:32,740
Saya tidak diamalkan apa yang saya telah diajar. Yeah?

254
00:15:32,740 --> 00:15:34,760
[Pelajar jawapan, difahami].

255
00:15:34,760 --> 00:15:36,880
Saya telah tidak dibebaskan memori. Jadi kemestian sekarang

256
00:15:36,880 --> 00:15:43,150
telah menjadi bila-bila masa anda memanggil malloc, anda mesti menghubungi percuma apabila anda telah selesai menggunakan memori yang.

257
00:15:43,150 --> 00:15:45,610
Kini, apabila saya mahu untuk membebaskan memori ini?

258
00:15:45,610 --> 00:15:49,780
Mungkin andaian ini baris pertama adalah betul, saya mahu untuk melakukannya di sini.

259
00:15:49,780 --> 00:15:55,710
Kerana saya tidak boleh, misalnya, adakah ia turun di sini. Mengapa?

260
00:15:55,710 --> 00:15:57,860
Hanya keluar skop. Jadi, walaupun kita sedang bercakap mengenai petunjuk,

261
00:15:57,860 --> 00:16:04,830
ini adalah seminggu 2 atau 3 isu, di mana x ialah hanya dalam skop di dalam pendakap kerinting yang mana ia telah diisytiharkan.

262
00:16:04,830 --> 00:16:11,000
Jadi, anda pasti tidak dapat membebaskan sana. Satunya peluang saya untuk membebaskan ia adalah kira-kira selepas baris 21.

263
00:16:11,000 --> 00:16:15,170
Ini adalah satu program yang agak mudah, ia adalah agak mudah sebaik sahaja anda jenis dibalut fikiran anda

264
00:16:15,170 --> 00:16:17,870
sekitar apa program lakukan, mana kesilapan.

265
00:16:17,870 --> 00:16:20,500
Dan walaupun jika anda tidak melihat ia pada mulanya, mudah-mudahan ia sedikit jelas sekarang

266
00:16:20,500 --> 00:16:23,870
bahawa kesilapan-kesilapan ini cukup mudah diselesaikan dan mudah dibuat.

267
00:16:23,870 --> 00:16:28,720
Tetapi apabila program adalah lebih daripada 12 baris panjang, ia adalah 50 baris panjang, 100 barisan panjang,

268
00:16:28,720 --> 00:16:31,150
berjalan melalui talian kod anda demi baris, pemikiran melalui logiknya,

269
00:16:31,150 --> 00:16:35,110
adalah mungkin tetapi tidak terutamanya yang menyeronokkan untuk dilakukan, sentiasa mencari pepijat,

270
00:16:35,110 --> 00:16:38,340
dan ia juga sukar untuk berbuat demikian, dan itulah sebabnya alat seperti Valgrind wujud.

271
00:16:38,340 --> 00:16:40,900
Biar saya pergi ke hadapan dan melakukan ini: izinkan saya membuka tetingkap terminal saya,

272
00:16:40,900 --> 00:16:45,400
dan biarlah saya bukan hanya menjalankan memori, kerana memori nampaknya baik.

273
00:16:45,400 --> 00:16:49,180
Saya mendapat bertuah. Melangkah ke bait yang tambahan pada akhir array

274
00:16:49,180 --> 00:16:51,060
nampaknya tidak menjadi terlalu bermasalah.

275
00:16:51,060 --> 00:16:56,370
Tetapi biarlah saya, walau bagaimanapun, melakukan pemeriksaan kewarasan, yang hanya bermakna untuk memeriksa

276
00:16:56,370 --> 00:16:58,320
sama ada atau tidak ini adalah sebenarnya betul.

277
00:16:58,320 --> 00:17:04,690
>> Jadi mari kita buat valgrind-v - bocor menyemak = penuh,

278
00:17:04,690 --> 00:17:07,520
dan kemudian nama program dalam kes ini adalah ingatan, tidak a.out.

279
00:17:07,520 --> 00:17:10,760
Jadi biarlah saya pergi ke hadapan dan melakukan ini. Tekan Enter.

280
00:17:10,760 --> 00:17:14,109
Dear Allah. Ini adalah output, dan ini adalah apa yang saya dirujuk kepada awal.

281
00:17:14,109 --> 00:17:17,550
Tetapi, jika anda belajar untuk membaca melalui semua karut di sini,

282
00:17:17,550 --> 00:17:20,760
kebanyakan ini hanya output diagnostik yang tidak yang menarik.

283
00:17:20,760 --> 00:17:24,829
Apa mata anda benar-benar mahu mencari apa-apa sebutan ralat atau tidak sah.

284
00:17:24,829 --> 00:17:26,800
Perkataan yang mencadangkan masalah.

285
00:17:26,800 --> 00:17:29,340
Dan sesungguhnya, mari kita lihat apa yang berlaku salah turun di sini.

286
00:17:29,340 --> 00:17:35,230
Saya mempunyai ringkasan beberapa jenis, "digunakan pada keluar:. 40 bait dalam 1 blok"

287
00:17:35,230 --> 00:17:38,750
Saya tidak benar-benar pasti apa yang blok lagi, tetapi 40 bytes

288
00:17:38,750 --> 00:17:41,260
sebenarnya berasa seperti saya dapat memikirkan mana yang datang dari.

289
00:17:41,260 --> 00:17:45,030
40 bait. Mengapa 40 bait dalam penggunaan di bahagian keluar?

290
00:17:45,030 --> 00:17:48,780
Dan lebih khusus, jika kita tatal ke sini,

291
00:17:48,780 --> 00:17:54,520
mengapa saya pasti kehilangan 40 bytes? Yeah?

292
00:17:54,520 --> 00:17:59,520
[Pelajar jawapan, difahami] Perfect. Ya, sebenarnya.

293
00:17:59,520 --> 00:18:03,540
Terdapat sepuluh integer, dan setiap orang adalah saiz 4, atau 32 bit,

294
00:18:03,540 --> 00:18:08,300
jadi saya telah hilang tepat 40 bait kerana, seperti yang dicadangkan, saya telah tidak dipanggil percuma.

295
00:18:08,300 --> 00:18:13,460
Itulah satu pepijat, dan sekarang mari kita melihat ke bawah sedikit lagi dan lihat sebelah ini,

296
00:18:13,460 --> 00:18:16,900
"Tidak sah menulis 4 saiz." Sekarang apakah ini?

297
00:18:16,900 --> 00:18:21,150
Alamat ini dinyatakan apa notasi asas, nampaknya?

298
00:18:21,150 --> 00:18:23,640
Ini adalah perenambelasan, dan bila-bila masa anda melihat nombor yang bermula dengan 0x,

299
00:18:23,640 --> 00:18:29,410
ia bermakna perenambelasan, yang kita lakukan perjalanan pulang, saya fikir, seksyen pset 0 soalan,

300
00:18:29,410 --> 00:18:34,090
yang hanya melakukan satu latihan warmup, menukar perpuluhan hex binari dan sebagainya.

301
00:18:34,090 --> 00:18:39,220
Perenambelasan, hanya dengan konvensyen manusia, biasanya digunakan untuk mewakili petunjuk

302
00:18:39,220 --> 00:18:41,570
atau lebih amnya, alamat. Ia hanya konvensyen,

303
00:18:41,570 --> 00:18:45,340
kerana ia sedikit lebih mudah untuk dibaca, ia adalah sedikit lebih padat daripada sesuatu seperti perpuluhan,

304
00:18:45,340 --> 00:18:47,720
dan binari adalah sia-sia bagi kebanyakan manusia untuk menggunakan.

305
00:18:47,720 --> 00:18:50,840
Jadi sekarang apa maknanya? Nah, ia kelihatan seperti ada menulis tidak sah

306
00:18:50,840 --> 00:18:54,480
4 saiz on line 21 daripada memory.c.

307
00:18:54,480 --> 00:18:59,180
Jadi mari kita kembali kepada 21 baris, dan sesungguhnya, di sini adalah bahawa menulis tidak sah.

308
00:18:59,180 --> 00:19:02,640
Jadi Valgrind tidak akan benar-benar memegang tangan saya dan beritahu saya apa yang menetapkan,

309
00:19:02,640 --> 00:19:05,520
tetapi ia mengesan bahawa saya melakukan sesuatu menulis tidak sah.

310
00:19:05,520 --> 00:19:08,800
Saya menyentuh 4 bait bahawa saya tidak perlu, dan nampaknya itulah kerana,

311
00:19:08,800 --> 00:19:13,960
kerana anda berkata, saya lakukan [10] bukan [9] maksima

312
00:19:13,960 --> 00:19:16,660
atau [0] atau sesuatu di antara.

313
00:19:16,660 --> 00:19:19,690
Dengan Valgrind, menyedari bila-bila masa anda sedang menulis program

314
00:19:19,690 --> 00:19:24,190
yang menggunakan petunjuk dan menggunakan memori, dan malloc lebih khusus,

315
00:19:24,190 --> 00:19:27,080
pasti masuk ke dalam tabiat berjalan ini lama

316
00:19:27,080 --> 00:19:30,890
tetapi sangat mudah disalin dan ditampal perintah Valgrind

317
00:19:30,890 --> 00:19:32,650
untuk melihat jika terdapat beberapa kesilapan di sana.

318
00:19:32,650 --> 00:19:34,820
Dan ia akan menjadi hangat setiap kali anda melihat output,

319
00:19:34,820 --> 00:19:39,430
tetapi hanya menghurai melalui visual semua output dan lihat jika anda lihat menyebut kesilapan

320
00:19:39,430 --> 00:19:43,190
atau amaran atau tidak sah atau hilang.

321
00:19:43,190 --> 00:19:46,200
Mana-mana perkataan yang bunyi seperti anda diskrukan sehingga tempat.

322
00:19:46,200 --> 00:19:48,580
Jadi sedar bahawa alat baru dalam Kit anda.

323
00:19:48,580 --> 00:19:51,270
>> Sekarang pada hari Isnin, kami mempunyai sekumpulan keseluruhan orang datang sini

324
00:19:51,270 --> 00:19:53,150
dan mewakili tanggapan senarai berkaitan.

325
00:19:53,150 --> 00:20:00,970
Dan kita memperkenalkan senarai yang dikaitkan sebagai penyelesaian kepada apa masalah?

326
00:20:00,970 --> 00:20:04,590
Yeah? [Pelajar jawapan, difahami].

327
00:20:04,590 --> 00:20:06,530
Tatasusunan tidak boleh mempunyai memori ditambah kepada mereka.

328
00:20:06,530 --> 00:20:09,440
Jika anda memperuntukkan pelbagai bersaiz 10, itu semua yang anda dapatkan.

329
00:20:09,440 --> 00:20:13,690
Anda boleh memanggil fungsi seperti realloc jika anda pada mulanya dipanggil malloc,

330
00:20:13,690 --> 00:20:17,580
dan yang boleh cuba untuk berkembang array jika ada ruang ke arah akhir ia

331
00:20:17,580 --> 00:20:21,610
bahawa tidak ada orang lain menggunakan, dan jika tidak, ia hanya akan mencari anda sebahagian besar di tempat lain.

332
00:20:21,610 --> 00:20:25,040
Tetapi maka ia akan menyalin semua bytes mereka ke array baru.

333
00:20:25,040 --> 00:20:28,310
Ini bunyi seperti penyelesaian yang sangat betul.

334
00:20:28,310 --> 00:20:34,790
Mengapa ini tidak menarik?

335
00:20:34,790 --> 00:20:36,940
Maksud saya ia berfungsi, manusia telah menyelesaikan masalah ini.

336
00:20:36,940 --> 00:20:40,710
Mengapa kita perlu untuk menyelesaikan ia pada hari Isnin dengan senarai yang dikaitkan? Yeah?

337
00:20:40,710 --> 00:20:44,060
[Jawapan Pelajar, difahami] Ia boleh mengambil masa yang lama.

338
00:20:44,060 --> 00:20:49,260
Malah, bila-bila masa yang anda memanggil malloc atau realloc atau calloc, yang lagi satu sama lain,

339
00:20:49,260 --> 00:20:52,470
bila-bila masa anda, program ini, bercakap kepada sistem operasi,

340
00:20:52,470 --> 00:20:54,310
anda cenderung untuk memperlahankan program turun.

341
00:20:54,310 --> 00:20:57,470
Dan jika anda melakukan ini jenis perkara dalam gelung, anda benar-benar melambatkan perkara turun.

342
00:20:57,470 --> 00:21:00,740
Anda tidak akan notis ini mudah "hello dunia" jenis program,

343
00:21:00,740 --> 00:21:04,300
tetapi dalam program-program yang lebih besar, meminta sistem operasi sekali lagi dan sekali lagi untuk ingatan

344
00:21:04,300 --> 00:21:07,520
atau memberikan ia kembali lagi dan lagi cenderung untuk tidak menjadi satu perkara yang baik.

345
00:21:07,520 --> 00:21:11,210
Plus, ia hanya jenis intelektual - ia adalah sisa lengkap masa.

346
00:21:11,210 --> 00:21:16,490
Mengapa memperuntukkan memori lebih dan lebih, risiko menyalin segala-galanya ke array baru,

347
00:21:16,490 --> 00:21:21,980
jika anda mempunyai alternatif yang membolehkan anda memperuntukkan memori hanya sebagai banyak seperti yang anda sebenarnya perlu?

348
00:21:21,980 --> 00:21:24,130
Jadi ada plus dan kemudaratan di sini.

349
00:21:24,130 --> 00:21:26,730
Salah satu plus sekarang adalah bahawa kita mempunyai dinamisme.

350
00:21:26,730 --> 00:21:29,100
Tidak kira di mana ketulan memori yang bebas,

351
00:21:29,100 --> 00:21:32,070
Saya hanya boleh menyusun mencipta serbuk roti melalui petunjuk

352
00:21:32,070 --> 00:21:34,470
rentetan senarai keseluruhan saya dikaitkan bersama-sama.

353
00:21:34,470 --> 00:21:36,470
Tetapi saya membayar sekurang-kurangnya satu harga.

354
00:21:36,470 --> 00:21:40,060
>> Apa yang saya perlu untuk berputus asa dalam mendapatkan dikaitkan senarai?

355
00:21:40,060 --> 00:21:42,470
Yeah? [Pelajar jawapan, difahami].

356
00:21:42,470 --> 00:21:45,650
Anda perlu memori lebih. Sekarang saya perlu ruang bagi petunjuk,

357
00:21:45,650 --> 00:21:47,900
dan dalam kes senarai ini sangat mudah dikaitkan

358
00:21:47,900 --> 00:21:51,410
yang hanya cuba untuk menyimpan integer, yang 4 bait, kita terus katakan

359
00:21:51,410 --> 00:21:54,240
baik, penunjuk 4 bait, jadi sekarang saya telah benar-benar dua kali ganda

360
00:21:54,240 --> 00:21:57,290
jumlah memori yang saya perlukan hanya untuk menyimpan senarai ini.

361
00:21:57,290 --> 00:21:59,680
Tetapi sekali lagi, ini adalah tradeoff yang berterusan dalam bidang sains komputer

362
00:21:59,680 --> 00:22:03,440
antara masa dan ruang dan pembangunan, usaha dan sumber-sumber lain.

363
00:22:03,440 --> 00:22:06,630
Apa lagi Kelemahan menggunakan senarai yang dikaitkan? Yeah?

364
00:22:06,630 --> 00:22:10,150
[Pelajar jawapan, difahami]

365
00:22:10,150 --> 00:22:12,600
Baik. Tidak seperti mudah untuk akses. Kita tidak lagi boleh memanfaatkan

366
00:22:12,600 --> 00:22:15,530
minggu 0 prinsip seperti membahagi dan menakluk.

367
00:22:15,530 --> 00:22:18,220
Dan lebih khusus, carian dedua. Kerana walaupun kita manusia

368
00:22:18,220 --> 00:22:20,400
boleh melihat kira-kira di mana pertengahan senarai ini adalah,

369
00:22:20,400 --> 00:22:25,840
komputer hanya tahu bahawa senarai ini dikaitkan bermula di alamat dipanggil 1.

370
00:22:25,840 --> 00:22:28,250
Dan itulah 0x123 atau sesuatu seperti itu.

371
00:22:28,250 --> 00:22:30,990
Dan satu-satunya cara program ini boleh mencari elemen tengah

372
00:22:30,990 --> 00:22:33,350
sebenarnya adalah untuk mencari senarai keseluruhan.

373
00:22:33,350 --> 00:22:35,500
Dan walaupun itu, ia benar-benar mempunyai untuk mencari senarai keseluruhan kerana

374
00:22:35,500 --> 00:22:38,950
walaupun sekali anda mencapai elemen tengah dengan mengikuti petunjuk,

375
00:22:38,950 --> 00:22:42,380
anda, program ini, tidak mempunyai idea berapa lama senarai ini, berpotensi,

376
00:22:42,380 --> 00:22:45,250
sehingga anda memukul akhir ia, dan bagaimana anda tahu programatik

377
00:22:45,250 --> 00:22:48,600
bahawa anda berada di akhir senarai dikaitkan?

378
00:22:48,600 --> 00:22:51,120
Ada penunjuk khas NULL, jadi lagi, konvensyen.

379
00:22:51,120 --> 00:22:53,870
Bukannya menggunakan penunjuk ini, kita pasti tidak mahu ia menjadi beberapa nilai sampah

380
00:22:53,870 --> 00:22:57,750
menunjukkan dari pentas tempat, kita mahu ia menjadi tangan ke bawah, NULL,

381
00:22:57,750 --> 00:23:01,530
supaya kita mempunyai perhentian ini dalam struktur data ini supaya kita tahu di mana ia berakhir.

382
00:23:01,530 --> 00:23:03,410
>> Bagaimana jika kita ingin memanipulasi ini?

383
00:23:03,410 --> 00:23:05,980
Kami melakukan kebanyakan ini visual, dan dengan manusia,

384
00:23:05,980 --> 00:23:07,630
tetapi apa yang jika kita mahu melakukan kemasukan?

385
00:23:07,630 --> 00:23:12,360
Jadi senarai asal adalah 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Bagaimana jika kita kemudian mahu ruang malloc untuk 55 nombor, nod untuk ia,

387
00:23:16,730 --> 00:23:20,730
dan kemudian kita mahu untuk memasukkan 55 ke dalam senarai hanya seperti yang kita lakukan pada hari Isnin?

388
00:23:20,730 --> 00:23:23,690
Bagaimana kita melakukan ini? Nah, Anita datang dan dia asasnya berjalan senarai.

389
00:23:23,690 --> 00:23:27,500
Beliau memulakan pada unsur pertama, maka seterusnya, seterusnya, seterusnya, seterusnya, seterusnya.

390
00:23:27,500 --> 00:23:29,500
Akhirnya melanda kiri sepanjang jalan turun

391
00:23:29,500 --> 00:23:34,480
dan menyedari oh, ini adalah NULL. Jadi apa manipulasi penunjuk yang perlu dilakukan?

392
00:23:34,480 --> 00:23:37,980
Orang yang berada di akhir, nombor 34, yang diperlukan tangan kirinya dibangkitkan

393
00:23:37,980 --> 00:23:46,220
untuk menunjukkan pada usia 55 tahun, 55 diperlukan lengan kiri mereka menunjuk ke menjadi NULL terminator baru. Selesai.

394
00:23:46,220 --> 00:23:49,540
Cukup mudah untuk memasukkan 55 ke dalam senarai diisih.

395
00:23:49,540 --> 00:23:51,800
Dan bagaimana ini mungkin kelihatan?

396
00:23:51,800 --> 00:23:55,690
>> Biar saya pergi ke hadapan dan membuka beberapa contoh kod di sini.

397
00:23:55,690 --> 00:23:58,120
Saya akan membuka gedit, dan biarlah saya membuka dua fail pertama.

398
00:23:58,120 --> 00:24:02,050
Satu adalah list1.h, dan biarlah saya hanya mengingatkan bahawa ini adalah sebahagian kod

399
00:24:02,050 --> 00:24:04,920
bahawa kita digunakan untuk mewakili nod.

400
00:24:04,920 --> 00:24:13,040
Nod A mempunyai kedua-dua int dipanggil n dan penunjuk dipanggil seterusnya bahawa hanya mata untuk perkara yang seterusnya dalam senarai.

401
00:24:13,040 --> 00:24:15,450
Yang kini dalam fail. H. Mengapa?

402
00:24:15,450 --> 00:24:19,090
Ada konvensyen ini, dan kami tidak mengambil kesempatan ini sejumlah besar diri,

403
00:24:19,090 --> 00:24:22,220
tetapi orang yang menulis fungsi printf dan lain-lain

404
00:24:22,220 --> 00:24:27,150
memberikan sebagai hadiah kepada dunia semua fungsi-fungsi dengan menulis fail dipanggil stdio.h.

405
00:24:27,150 --> 00:24:30,950
Dan kemudian ada string.h, dan kemudian ada map.h, dan ada semua ini h fail

406
00:24:30,950 --> 00:24:34,410
bahawa anda mungkin telah melihat atau digunakan sepanjang jangka yang ditulis oleh orang lain.

407
00:24:34,410 --> 00:24:38,470
Biasanya dalam mereka. Fail h adalah perkara-perkara sahaja seperti typedefs

408
00:24:38,470 --> 00:24:42,310
atau pengisytiharan jenis adat atau pengisytiharan pemalar.

409
00:24:42,310 --> 00:24:47,890
Anda tidak meletakkan pelaksanaan fungsi 'dalam fail header.

410
00:24:47,890 --> 00:24:50,570
Anda meletakkan, sebaliknya, hanya prototaip mereka.

411
00:24:50,570 --> 00:24:53,050
Anda meletakkan perkara yang anda ingin berkongsi dengan dunia apa yang mereka perlukan

412
00:24:53,050 --> 00:24:55,640
dalam usaha untuk menyusun kod mereka. Jadi hanya untuk masuk ke dalam tabiat ini,

413
00:24:55,640 --> 00:24:59,110
kami mengambil keputusan untuk melakukan perkara yang sama. Tidak banyak di list1.h,

414
00:24:59,110 --> 00:25:02,070
tetapi kita telah meletakkan sesuatu yang mungkin menarik minat kepada orang-orang di dunia

415
00:25:02,070 --> 00:25:05,030
yang mahu menggunakan pelaksanaan senarai berpaut kami.

416
00:25:05,030 --> 00:25:08,040
Sekarang, list1.c, saya tidak akan pergi melalui perkara ini keseluruhan

417
00:25:08,040 --> 00:25:11,390
kerana ia agak panjang, program ini, tetapi mari kita berlari ia sebenar cepat di prompt.

418
00:25:11,390 --> 00:25:15,720
Izinkan saya menyusun Senarai1, izinkan saya kemudian berjalan Senarai1, dan apa yang anda akan lihat adalah

419
00:25:15,720 --> 00:25:18,070
kita telah simulasi program mudah sedikit di sini

420
00:25:18,070 --> 00:25:20,990
yang akan membolehkan saya untuk menambah dan membuang nombor ke senarai.

421
00:25:20,990 --> 00:25:24,310
Jadi biarlah saya pergi ke hadapan dan taipkan 3 bagi 3 pilihan menu.

422
00:25:24,310 --> 00:25:27,880
Saya mahu untuk memasukkan nombor - mari kita buat nombor pertama, yang adalah 9,

423
00:25:27,880 --> 00:25:30,550
dan sekarang saya diberitahu senarai kini 9.

424
00:25:30,550 --> 00:25:33,760
Biar saya pergi ke hadapan dan melakukan kemasukan lain, jadi saya melanda pilihan menu 3.

425
00:25:33,760 --> 00:25:36,760
Apakah nombor yang saya mahu untuk memasukkan? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. Dan saya akan melakukan hanya satu lagi.

427
00:25:39,220 --> 00:25:41,720
Biar saya memasukkan nombor 22.

428
00:25:41,720 --> 00:25:45,850
Jadi kita mempunyai permulaan senarai dikaitkan bahawa kita mempunyai dalam bentuk slaid seketika lalu.

429
00:25:45,850 --> 00:25:48,740
Bagaimana kemasukan ini sebenarnya berlaku?

430
00:25:48,740 --> 00:25:52,000
Malah, 22 kini di akhir senarai.

431
00:25:52,000 --> 00:25:55,050
Jadi cerita kita memberitahu di atas pentas pada hari Isnin dan recapped tadi

432
00:25:55,050 --> 00:25:57,460
sebenarnya mesti berlaku dalam kod.

433
00:25:57,460 --> 00:25:59,700
Mari kita lihat. Biarkan saya tatal ke bawah dalam fail ini.

434
00:25:59,700 --> 00:26:01,720
Kami akan menyembunyikan beberapa fungsi,

435
00:26:01,720 --> 00:26:05,630
tetapi kita akan pergi ke, berkata, fungsi insert.

436
00:26:05,630 --> 00:26:11,720
>> Mari kita lihat bagaimana kita pergi tentang memasukkan nod baru ke dalam senarai ini dikaitkan.

437
00:26:11,720 --> 00:26:14,550
Di manakah senarai diisytiharkan? Nah, mari kita tatal sepanjang jalan sehingga di atas,

438
00:26:14,550 --> 00:26:19,970
dan notis bahawa senarai saya dikaitkan asasnya adalah diisytiharkan sebagai penunjuk tunggal yang mulanya NULL.

439
00:26:19,970 --> 00:26:23,180
Jadi saya menggunakan pembolehubah global di sini, yang secara umum kita telah ajarannya menentang

440
00:26:23,180 --> 00:26:25,280
kerana ia membuatkan kod anda kemas sedikit untuk mengekalkan,

441
00:26:25,280 --> 00:26:29,080
ia adalah jenis malas, biasanya, tetapi ia tidak malas dan ia tidak salah dan ia tidak buruk

442
00:26:29,080 --> 00:26:33,660
jika tujuan program anda dalam kehidupan adalah untuk mensimulasikan satu senarai berpaut.

443
00:26:33,660 --> 00:26:35,460
Yang betul-betul apa yang kita lakukan.

444
00:26:35,460 --> 00:26:39,100
Jadi, bukannya mengisytiharkan ini utama dan kemudian perlu lulus untuk setiap fungsi

445
00:26:39,100 --> 00:26:42,640
kita telah ditulis dalam program ini, kita bukannya sedar oh, mari kita hanya membuat ia global

446
00:26:42,640 --> 00:26:47,060
kerana keseluruhan tujuan program ini adalah untuk menunjukkan satu dan hanya satu senarai dikaitkan.

447
00:26:47,060 --> 00:26:50,700
Jadi yang merasakan okay. Berikut adalah prototaip saya, dan kita tidak akan pergi melalui semua ini,

448
00:26:50,700 --> 00:26:55,800
tetapi saya menulis fungsi padam, fungsi mencari, fungsi insert, dan fungsi traverse.

449
00:26:55,800 --> 00:26:59,080
Tetapi mari kita kini kembali turun kepada fungsi memasukkan

450
00:26:59,080 --> 00:27:01,490
dan lihat bagaimana satu ini bekerja di sini.

451
00:27:01,490 --> 00:27:09,940
Sisipan adalah on-line - di sini kita pergi.

452
00:27:09,940 --> 00:27:12,850
Memasukkan. Jadi ia tidak mengambil apa-apa hujah, kerana kita hendak bertanya

453
00:27:12,850 --> 00:27:15,930
dalam pengguna fungsi ini untuk bilangan mereka mahu masukkan.

454
00:27:15,930 --> 00:27:19,410
Tetapi pertama, kita bersedia untuk memberi mereka ruang.

455
00:27:19,410 --> 00:27:22,050
Ini adalah jenis copy dan paste dari contoh lain.

456
00:27:22,050 --> 00:27:25,110
Dalam kes itu, kita telah memperuntukkan int, masa ini kita memperuntukkan nod.

457
00:27:25,110 --> 00:27:27,910
Saya tidak ingat berapa banyak bait nod, tetapi itulah denda.

458
00:27:27,910 --> 00:27:30,460
Sizeof boleh memahami bahawa bagi saya.

459
00:27:30,460 --> 00:27:33,340
Dan mengapa saya memeriksa NULL di baris 120?

460
00:27:33,340 --> 00:27:37,530
Apa yang boleh pergi salah di 119 baris? Yeah?

461
00:27:37,530 --> 00:27:40,530
[Pelajar jawapan, difahami]

462
00:27:40,530 --> 00:27:43,440
Baik. Hanya boleh menjadi kes bahawa saya telah diminta untuk memori yang terlalu banyak

463
00:27:43,440 --> 00:27:47,020
atau sesuatu yang salah dan sistem operasi tidak mempunyai bait yang cukup untuk memberi saya,

464
00:27:47,020 --> 00:27:50,640
jadi ia isyarat sebanyak dengan mengembalikan NULL, dan jika saya tidak mendaftar untuk itu

465
00:27:50,640 --> 00:27:54,710
dan saya hanya membuta tuli meneruskan untuk menggunakan alamat kembali, ia boleh menjadi NULL.

466
00:27:54,710 --> 00:27:58,400
Ia boleh menjadi beberapa nilai yang tidak diketahui; bukan satu perkara yang baik kecuali saya -

467
00:27:58,400 --> 00:28:00,590
sebenarnya tidak akan menjadi nilai yang tidak diketahui. Ia boleh menjadi NULL, jadi saya tidak mahu

468
00:28:00,590 --> 00:28:02,550
penyalahgunaan dan risiko dereferencing ia.

469
00:28:02,550 --> 00:28:07,410
Jika itu berlaku, saya hanya kembali dan kami akan berpura-pura seperti saya tidak mendapatkan kembali memori apa-apa pada semua.

470
00:28:07,410 --> 00:28:12,270
>> Jika tidak, saya memberitahu pengguna memberikan saya nombor untuk memasukkan, saya menyeru kawan lama kami GetInt,

471
00:28:12,270 --> 00:28:15,530
dan maka ini adalah sintaks baru kami memperkenalkan pada hari Isnin.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' bermakna mengambil alamat yang anda telah diberikan oleh malloc

473
00:28:20,320 --> 00:28:23,490
yang mewakili bait pertama objek nod baru,

474
00:28:23,490 --> 00:28:26,860
dan kemudian pergi ke bidang yang dipanggil n.

475
00:28:26,860 --> 00:28:35,270
Satu soalan trivia sedikit: Ini adalah bersamaan kepada barisan lebih samar kod?

476
00:28:35,270 --> 00:28:38,110
Bagaimana lagi boleh saya telah menulis ini? Mahu mengambil menikam?

477
00:28:38,110 --> 00:28:41,480
[Pelajar jawapan, difahami]

478
00:28:41,480 --> 00:28:44,870
Baik. Menggunakan n, tetapi ia tidak cukup semudah ini.

479
00:28:44,870 --> 00:28:47,090
Apa yang saya perlu lakukan? [Pelajar jawapan, difahami]

480
00:28:47,090 --> 00:28:52,730
Baik. Perlu saya lakukan newptr.n *.

481
00:28:52,730 --> 00:28:55,610
Jadi ini mengatakan penunjuk baru jelas alamat. Mengapa?

482
00:28:55,610 --> 00:28:59,520
Kerana ia telah dikembalikan oleh malloc. * Newptr mengatakan "pergi ke sana,"

483
00:28:59,520 --> 00:29:02,970
dan kemudian apabila anda berada di sana, maka anda boleh menggunakan lebih biasa. n,

484
00:29:02,970 --> 00:29:05,730
tetapi ini hanya kelihatan sedikit hodoh, terutamanya jika kita manusia akan

485
00:29:05,730 --> 00:29:10,360
menarik petunjuk dengan anak panah sepanjang masa; dunia mempunyai standard pada notasi arrow ini,

486
00:29:10,360 --> 00:29:12,320
yang tidak perkara yang sama.

487
00:29:12,320 --> 00:29:16,070
Jadi, anda hanya gunakan -> notasi apabila perkara di sebelah kiri adalah penunjuk.

488
00:29:16,070 --> 00:29:18,790
Jika tidak, jika ia adalah satu struct sebenar, menggunakan n..

489
00:29:18,790 --> 00:29:25,800
Dan kemudian ini: Mengapa saya memulakan newptr> di sebelah null?

490
00:29:25,800 --> 00:29:28,610
Kita tidak mahu tangan kiri tergantung kira akhir pentas.

491
00:29:28,610 --> 00:29:31,630
Kami mahu ia menunjuk lurus ke bawah, yang bermaksud akhir senarai ini

492
00:29:31,630 --> 00:29:34,980
berpotensi menjadi di nod ini, jadi kami lebih baik pastikan ia adalah NULL.

493
00:29:34,980 --> 00:29:38,460
Dan, secara amnya, Memulakan pembolehubah anda atau ahli data anda dan structs

494
00:29:38,460 --> 00:29:40,470
kepada sesuatu hanya amalan yang baik.

495
00:29:40,470 --> 00:29:45,170
Hanya membiarkan sampah wujud dan terus wujud secara mendapat anda dalam kesusahan

496
00:29:45,170 --> 00:29:48,650
jika anda terlupa untuk melakukan sesuatu yang kemudian.

497
00:29:48,650 --> 00:29:51,590
>> Berikut adalah beberapa kes. Ini, sekali lagi, adalah fungsi memasukkan,

498
00:29:51,590 --> 00:29:54,930
dan perkara pertama yang saya menyemak adalah jika pembolehubah dipanggil pertama kali,

499
00:29:54,930 --> 00:29:58,240
bahawa pembolehubah global NULL, yang bermaksud tidak ada senarai dikaitkan.

500
00:29:58,240 --> 00:30:02,460
Kami telah tidak dimasukkan apa-apa nombor, jadi ia adalah remeh untuk memasukkan nombor ini semasa

501
00:30:02,460 --> 00:30:05,240
ke dalam senarai, kerana ia hanya tergolong pada permulaan senarai.

502
00:30:05,240 --> 00:30:08,100
Jadi ini adalah apabila Anita hanya berdiri di sini sahaja, berpura-pura

503
00:30:08,100 --> 00:30:11,390
tidak ada orang lain di sini di atas pentas sehingga kita memperuntukkan nod,

504
00:30:11,390 --> 00:30:13,940
maka dia boleh mengangkat tangan beliau untuk kali pertama,

505
00:30:13,940 --> 00:30:17,420
jika orang lain telah tampil di atas pentas selepas itu pada hari Isnin.

506
00:30:17,420 --> 00:30:22,900
Sekarang di sini, ini adalah cek yang sedikit di mana saya katakan jika nilai nod baru n

507
00:30:22,900 --> 00:30:27,370
<nilai n dalam nod pertama semasa,

508
00:30:27,370 --> 00:30:29,930
yang bermakna terdapat senarai yang berkaitan itu bermula.

509
00:30:29,930 --> 00:30:32,330
Terdapat sekurang-kurangnya satu nod dalam senarai, tetapi lelaki ini baru

510
00:30:32,330 --> 00:30:37,230
kepunyaan sebelum ia, jadi kita perlu bergerak perkara di sekeliling.

511
00:30:37,230 --> 00:30:43,450
Dalam erti kata lain, jika senarai telah bermula hanya dengan, katakan,

512
00:30:43,450 --> 00:30:48,100
hanya nombor 17, itulah - sebenarnya, kita boleh melakukan ini dengan lebih jelas.

513
00:30:48,100 --> 00:30:56,010
Jika kita mula cerita kita dengan penunjuk di sini dipanggil 1,

514
00:30:56,010 --> 00:30:59,870
dan pada mulanya ia NULL, dan kita memasukkan nombor 9,

515
00:30:59,870 --> 00:31:02,510
bilangan 9 jelas tergolong pada permulaan senarai.

516
00:31:02,510 --> 00:31:07,400
Jadi mari kita berpura-pura kita hanya malloced alamat atau nombor 9 dan meletakkan ia di sini.

517
00:31:07,400 --> 00:31:13,170
Jika pertama adalah 9 secara lalai, senario pertama kami membincangkan hanya bermaksud titik mari kita lelaki ini di sini,

518
00:31:13,170 --> 00:31:15,790
meninggalkan ini sebagai NULL; kini kita mempunyai bilangan 9.

519
00:31:15,790 --> 00:31:18,280
Nombor seterusnya yang kita mahu memasukkan ialah 17.

520
00:31:18,280 --> 00:31:22,420
17 tergolong di sini, jadi kita akan perlu melakukan beberapa loncatan logik melalui ini.

521
00:31:22,420 --> 00:31:26,060
Jadi mari kita sebaliknya, sebelum kita berbuat demikian, mari kita berpura-pura bahawa kita mahu memasukkan nombor 8.

522
00:31:26,060 --> 00:31:28,650
>> Jadi hanya demi kemudahan ini, saya akan menarik di sini.

523
00:31:28,650 --> 00:31:30,760
Tetapi ingat, malloc boleh meletakkan ia paling mana-mana.

524
00:31:30,760 --> 00:31:33,460
Tetapi demi lukisan ini, saya akan meletakkan ia di sini.

525
00:31:33,460 --> 00:31:38,440
Jadi berpura-pura saya hanya memperuntukkan nod bagi bilangan 8; ini adalah NULL secara lalai.

526
00:31:38,440 --> 00:31:42,800
Apa yang kini telah berlaku? Beberapa perkara.

527
00:31:42,800 --> 00:31:47,090
Kami membuat kesilapan ini di atas pentas pada hari Isnin di mana kita dikemaskini penunjuk seperti ini,

528
00:31:47,090 --> 00:31:51,890
kemudian melakukan ini, dan kemudian kita mendakwa kami yatim orang lain di atas pentas.

529
00:31:51,890 --> 00:31:54,350
Kerana anda can't - perintah operasi di sini adalah penting,

530
00:31:54,350 --> 00:31:58,760
kerana sekarang kita telah hilang 9 ini nod yang hanya jenis terapung di angkasa.

531
00:31:58,760 --> 00:32:01,150
Jadi ini bukanlah pendekatan yang betul pada hari Isnin.

532
00:32:01,150 --> 00:32:03,330
Kita perlu melakukan sesuatu yang lain.

533
00:32:03,330 --> 00:32:06,280
Keadaan dunia kelihatan seperti ini. Pada mulanya, 8 telah diperuntukkan.

534
00:32:06,280 --> 00:32:10,550
Apa yang akan menjadi cara yang lebih baik memasukkan 8?

535
00:32:10,550 --> 00:32:14,720
Sebaliknya mengemaskini penunjuk pertama ini, hanya mengemaskini satu ini di sini sebaliknya.

536
00:32:14,720 --> 00:32:17,720
Jadi kita memerlukan baris kod yang akan menjadikan ini watak NULL

537
00:32:17,720 --> 00:32:22,020
ke penunjuk sebenar yang menunjuk pada nod 9,

538
00:32:22,020 --> 00:32:27,970
dan kemudian kita selamat boleh menukar pertama untuk menunjukkan pada lelaki ini di sini.

539
00:32:27,970 --> 00:32:31,330
Sekarang kita mempunyai senarai, senarai yang berkaitan, daripada dua unsur.

540
00:32:31,330 --> 00:32:33,580
Dan apakah ini sebenarnya kelihatan seperti sini?

541
00:32:33,580 --> 00:32:36,900
Jika kita melihat kod, notis bahawa saya telah melakukan yang tepat.

542
00:32:36,900 --> 00:32:41,970
Saya telah berkata newptr, dan dalam cerita ini, newptr menunjuk pada lelaki ini.

543
00:32:41,970 --> 00:32:45,520
>> Jadi biarlah saya menarik satu lagi perkara, dan perlu saya telah meninggalkan bilik lebih sedikit untuk ini.

544
00:32:45,520 --> 00:32:48,540
Jadi memaafkan lukisan sedikit kecil.

545
00:32:48,540 --> 00:32:52,140
Lelaki ini dipanggil newptr.

546
00:32:52,140 --> 00:32:57,940
Itu adalah pembolehubah kita mengisytiharkan beberapa baris sebelumnya, sejajar - hanya melebihi 25.

547
00:32:57,940 --> 00:33:03,430
Dan ia menunjuk kepada 8. Jadi, apabila saya mengatakan newptr> di sebelah, yang bermakna pergi untuk struct

548
00:33:03,430 --> 00:33:07,910
itu sedang menunjukkan di oleh newptr, jadi di sini kita, pergi ke sana.

549
00:33:07,910 --> 00:33:13,990
Kemudian anak panah mengatakan mendapatkan bidang seterusnya, dan kemudian = mengatakan meletakkan apa nilai di sana?

550
00:33:13,990 --> 00:33:17,280
Nilai yang pertama; apa nilai adalah pertama?

551
00:33:17,280 --> 00:33:21,930
Pertama telah menunjuk pada nod ini, jadi yang bermakna ini kini perlu menunjukkan di nod ini.

552
00:33:21,930 --> 00:33:25,660
Dalam erti kata lain, apa yang kelihatan walaupun keadaan huru-hara yang tidak masuk akal dengan tulisan tangan saya,

553
00:33:25,660 --> 00:33:28,620
apa idea yang mudah hanya bergerak panah ini sekitar

554
00:33:28,620 --> 00:33:31,560
diterjemahkan kepada kod dengan hanya pelapik yang satu ini.

555
00:33:31,560 --> 00:33:38,110
Menyimpan apa yang pertama dalam bidang seterusnya dan kemudian mengemas apa yang sebenarnya adalah 1.

556
00:33:38,110 --> 00:33:40,900
Mari kita pergi ke hadapan dan pantas ke hadapan melalui beberapa ini,

557
00:33:40,900 --> 00:33:44,220
dan kelihatan hanya di sisipan ekor ini buat masa sekarang.

558
00:33:44,220 --> 00:33:51,210
Katakan saya mendapat ke titik di mana saya mendapati bahawa bidang seterusnya nod beberapa NULL.

559
00:33:51,210 --> 00:33:53,410
Dan pada ketika ini dalam cerita, terperinci bahawa saya glossing atas

560
00:33:53,410 --> 00:33:58,170
adalah bahawa saya telah diperkenalkan penunjuk lain di sini di baris 142, penunjuk sebelumnya.

561
00:33:58,170 --> 00:34:01,320
Pada asasnya, pada ketika ini dalam cerita, sekali senarai mendapat lama,

562
00:34:01,320 --> 00:34:04,800
Saya jenis perlu berjalan dengan dua jari kerana jika saya pergi terlalu jauh,

563
00:34:04,800 --> 00:34:08,219
ingat dalam senarai panjang tunggal, anda tidak boleh pergi ke belakang.

564
00:34:08,219 --> 00:34:13,659
Jadi ini idea predptr jari kiri saya, dan newptr - tidak newptr.

565
00:34:13,659 --> 00:34:17,199
Satu lagi penunjuk yang di sini adalah jari saya yang lain, dan saya hanya jenis berjalan senarai.

566
00:34:17,199 --> 00:34:22,179
Itulah mengapa yang wujud. Tetapi mari kita hanya mempertimbangkan salah satu daripada kes-kes yang lebih mudah di sini.

567
00:34:22,179 --> 00:34:26,620
Jika medan seterusnya bahawa penunjuk adalah NULL, apa implikasi logik?

568
00:34:26,620 --> 00:34:30,840
Jika anda sedang menyeberangi senarai ini dan anda memukul penunjuk NULL?

569
00:34:30,840 --> 00:34:35,780
Anda berada di akhir senarai, dan sebagainya kod kemudian melampirkan ini elemen tambahan

570
00:34:35,780 --> 00:34:41,230
jenis intuitif akan mengambil nod yang seterusnya penunjuk adalah NULL,

571
00:34:41,230 --> 00:34:46,120
jadi ini adalah kini NULL, dan mengubahnya, walaupun, untuk menjadi alamat nod baru.

572
00:34:46,120 --> 00:34:52,260
Jadi kita hanya lukisan dalam kod anak panah yang kita menarik di atas pentas dengan mengangkat tangan kiri seseorang.

573
00:34:52,260 --> 00:34:54,070
>> Dan kes yang saya akan melambai tangan saya di buat masa sekarang,

574
00:34:54,070 --> 00:34:58,020
hanya kerana saya fikir ia adalah mudah untuk mendapatkan hilang apabila kita lakukan dalam jenis ini alam sekitar,

575
00:34:58,020 --> 00:35:00,600
memeriksa kemasukan pada pertengahan senarai.

576
00:35:00,600 --> 00:35:03,220
Tetapi hanya intuitif, apa yang perlu berlaku jika anda mahu untuk memikirkan

577
00:35:03,220 --> 00:35:06,600
di mana beberapa beberapa tergolong di tengah-tengah adalah anda tidak perlu berjalan

578
00:35:06,600 --> 00:35:09,510
dengan lebih daripada satu jari, lebih daripada satu penunjuk,

579
00:35:09,510 --> 00:35:12,920
memikirkan di mana ia tergolong oleh semakan adalah elemen <satu semasa,

580
00:35:12,920 --> 00:35:15,450
> Semasa, dan apabila anda mencari tempat itu,

581
00:35:15,450 --> 00:35:20,400
maka anda perlu melakukan ini jenis permainan shell di mana anda menggerakkan petunjuk di sekeliling sangat berhati-hati.

582
00:35:20,400 --> 00:35:23,850
Dan jawapan itu, jika anda ingin sebab melalui ini di rumah anda sendiri,

583
00:35:23,850 --> 00:35:28,340
bisul hanya untuk kedua-dua baris kod, tetapi perintah orang-orang garisan adalah sangat penting.

584
00:35:28,340 --> 00:35:31,390
Kerana jika anda menggugurkan tangan seseorang dan menaikkan orang lain dalam perintah itu salah,

585
00:35:31,390 --> 00:35:34,580
sekali lagi, anda boleh berakhir sehingga anak yatim senarai.

586
00:35:34,580 --> 00:35:39,500
Untuk meringkaskan lebih konsepnya, kemasukan di ekor adalah agak mudah.

587
00:35:39,500 --> 00:35:42,940
Kemasukan di kepala juga agak mudah,

588
00:35:42,940 --> 00:35:45,580
tetapi anda perlu untuk mengemaskini penunjuk tambahan masa ini

589
00:35:45,580 --> 00:35:47,930
memerah nombor 5 ke dalam senarai di sini,

590
00:35:47,930 --> 00:35:51,560
dan kemudian memasukkan di tengah-tengah melibatkan usaha lebih,

591
00:35:51,560 --> 00:35:56,130
sangat berhati-hati memasukkan nombor 20 dalam lokasi yang betul,

592
00:35:56,130 --> 00:35:58,350
yang berumur antara 17 dan 22.

593
00:35:58,350 --> 00:36:02,700
Jadi, anda perlu melakukan sesuatu seperti mempunyai nod baru 20 mata kepada 22,

594
00:36:02,700 --> 00:36:08,470
dan kemudian, penunjuk yang nod ini perlu dikemaskini terakhir?

595
00:36:08,470 --> 00:36:10,630
Ia adalah 17, sebenarnya memasukkan ia.

596
00:36:10,630 --> 00:36:14,080
Jadi sekali lagi, saya akan menangguhkan kod sebenar bagi pelaksanaan yang tertentu.

597
00:36:14,080 --> 00:36:17,280
>> Pada pandangan pertama, ia sedikit hangat, tetapi ia adalah benar-benar hanya gelung tak terhingga

598
00:36:17,280 --> 00:36:21,770
itu gelung, gelung, gelung, gelung, dan berbuka dengan seberapa segera seperti yang anda memukul penunjuk NULL,

599
00:36:21,770 --> 00:36:24,590
di mana titik anda boleh melakukan kemasukan yang diperlukan.

600
00:36:24,590 --> 00:36:30,960
Ini, maka, adalah wakil senarai kemasukan dikaitkan kod.

601
00:36:30,960 --> 00:36:34,590
Itu adalah jenis banyak, dan ia berasa seperti kita telah menyelesaikan satu masalah,

602
00:36:34,590 --> 00:36:36,940
tetapi kita telah memperkenalkan satu lain secara keseluruhan. Terus terang, kami telah menghabiskan semua masa ini

603
00:36:36,940 --> 00:36:40,540
O besar dan Ω dan berjalan masa, cuba untuk menyelesaikan masalah dengan lebih cepat,

604
00:36:40,540 --> 00:36:43,270
dan di sini kita mengambil langkah besar ke belakang, rasanya.

605
00:36:43,270 --> 00:36:45,380
Dan lagi, jika matlamatnya adalah untuk menyimpan data,

606
00:36:45,380 --> 00:36:48,010
rasanya Holy Grail, seperti yang kita berkata pada hari Isnin, benar-benar akan menjadi

607
00:36:48,010 --> 00:36:50,470
untuk menyimpan perkara-perkara serta-merta.

608
00:36:50,470 --> 00:36:53,930
>> Malah, menganggap bahawa kita melakukan senarai yang diketepikan dihubungkan untuk seketika

609
00:36:53,930 --> 00:36:56,000
dan kita bukannya memperkenalkan tanggapan jadual.

610
00:36:56,000 --> 00:36:59,110
Dan mari kita hanya berfikir jadual untuk seketika sebagai array.

611
00:36:59,110 --> 00:37:03,790
Ini pelbagai dan kes ini di sini mempunyai kira-kira 26 unsur, 0 hingga 25,

612
00:37:03,790 --> 00:37:07,940
dan menganggap bahawa anda memerlukan beberapa sebahagian simpanan untuk nama:

613
00:37:07,940 --> 00:37:10,350
Alice dan Bob dan Charlie dan sebagainya.

614
00:37:10,350 --> 00:37:12,880
Dan anda perlu beberapa struktur data untuk menyimpan nama-nama.

615
00:37:12,880 --> 00:37:15,000
Nah, anda boleh menggunakan sesuatu seperti senarai berkaitan

616
00:37:15,000 --> 00:37:20,260
dan anda boleh berjalan senarai memasukkan Alice sebelum Bob dan Charlie selepas Bob dan sebagainya.

617
00:37:20,260 --> 00:37:23,850
Dan, sebenarnya, jika anda mahu untuk melihat kod seperti itu sebagai diketepikan,

618
00:37:23,850 --> 00:37:27,230
tahu bahawa di list2.h, kita lakukan betul-betul bahawa.

619
00:37:27,230 --> 00:37:30,610
Kami tidak akan pergi melalui kod ini, tetapi ini adalah satu varian contoh pertama

620
00:37:30,610 --> 00:37:34,640
yang memperkenalkan satu struct lain kita telah melihat sebelum pelajar dipanggil,

621
00:37:34,640 --> 00:37:40,330
dan kemudian apa yang ia sebenarnya menyimpan dalam senarai berpaut adalah penunjuk kepada struktur pelajar

622
00:37:40,330 --> 00:37:44,520
bukannya mudah integer sedikit, n.

623
00:37:44,520 --> 00:37:46,900
Jadi sedar ada kod sana yang melibatkan rentetan sebenar,

624
00:37:46,900 --> 00:37:49,940
tetapi jika matlamat di tangan benar-benar kini adalah untuk menangani masalah kecekapan,

625
00:37:49,940 --> 00:37:53,380
ia tidak akan menjadi baik jika kita diberi satu objek yang dipanggil Alice,

626
00:37:53,380 --> 00:37:56,020
kita mahu meletakkan beliau ke lokasi yang betul dalam struktur data,

627
00:37:56,020 --> 00:37:58,860
ia berasa seperti ia akan menjadi benar-benar baik untuk hanya meletakkan Alice,

628
00:37:58,860 --> 00:38:01,180
yang namanya bermula dengan A, di lokasi pertama.

629
00:38:01,180 --> 00:38:05,270
Dan Bob, yang namanya bermula dengan B, lokasi kedua.

630
00:38:05,270 --> 00:38:09,580
Dengan pelbagai, atau mari kita mulakan ia memanggil jadual, jadual hash pada itu,

631
00:38:09,580 --> 00:38:13,650
kita boleh melakukan yang tepat. Jika kita diberikan nama seperti Alice,

632
00:38:13,650 --> 00:38:16,700
rentetan seperti Alice, di manakah anda meletakkan A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Kita perlu hueristic. Kita perlu fungsi untuk mengambil beberapa input seperti Alice

634
00:38:20,540 --> 00:38:24,610
dan kembali jawapan, "Letakkan Alice di lokasi ini."

635
00:38:24,610 --> 00:38:28,720
Dan fungsi ini, ini kotak hitam, akan dipanggil fungsi hash.

636
00:38:28,720 --> 00:38:32,330
>> Satu fungsi hash adalah sesuatu yang mengambil input, seperti "Alice",

637
00:38:32,330 --> 00:38:38,080
dan pulangan kepada anda, biasanya, lokasi angka dalam beberapa struktur data mana Alice kepunyaan.

638
00:38:38,080 --> 00:38:40,830
Dalam kes ini, fungsi hash kami harus agak mudah.

639
00:38:40,830 --> 00:38:47,510
Fungsi hash kita harus mengatakan, jika anda diberikan "Alice", watak yang saya harus mengambil berat tentang?

640
00:38:47,510 --> 00:38:55,660
Yang pertama. Jadi saya melihat [0], dan kemudian saya mengatakan jika [0] watak A, kembalikan nombor 0.

641
00:38:55,660 --> 00:39:01,130
Jika ia adalah B, kembali 1. Jika C ia, kembali 2, dan sebagainya.

642
00:39:01,130 --> 00:39:05,940
Semua indeks 0, dan yang akan membolehkan saya untuk memasukkan Alice dan kemudian Bob dan kemudian Charlie dan sebagainya

643
00:39:05,940 --> 00:39:10,960
ke dalam struktur data ini. Tetapi ada masalah.

644
00:39:10,960 --> 00:39:13,060
Bagaimana jika Anita datang bersama-sama lagi?

645
00:39:13,060 --> 00:39:17,510
Di manakah kita meletakkan Anita? Namanya juga, bermula dengan huruf A,

646
00:39:17,510 --> 00:39:20,330
dan ia merasakan seperti yang kita telah membuat keadaan kucar-kacir yang lebih besar daripada masalah ini.

647
00:39:20,330 --> 00:39:24,380
Kami kini mempunyai kemasukan serta-merta, kemasukan pemalar masa, ke dalam struktur data

648
00:39:24,380 --> 00:39:27,100
bukannya teruk kes-linear,

649
00:39:27,100 --> 00:39:29,510
tetapi apa yang kita boleh lakukan dengan Anita dalam kes ini?

650
00:39:29,510 --> 00:39:34,110
Apakah kedua-dua pilihan, benar-benar? Yeah?

651
00:39:34,110 --> 00:39:37,410
[Pelajar jawapan, difahami] Okay, jadi kita boleh mempunyai dimensi lain.

652
00:39:37,410 --> 00:39:42,320
Itulah baik. Jadi kita boleh membina perkara keluar dalam 3D seperti kita bercakap tentang secara lisan pada hari Isnin.

653
00:39:42,320 --> 00:39:46,700
Kita boleh menambah akses lain di sini, tetapi menganggap bahawa tiada, saya cuba untuk menyimpan ini mudah.

654
00:39:46,700 --> 00:39:50,160
Matlamat keseluruhan di sini adalah untuk mempunyai masa malar akses serta-merta,

655
00:39:50,160 --> 00:39:52,170
supaya menambah kerumitan terlalu banyak.

656
00:39:52,170 --> 00:39:55,970
Apakah pilihan lain apabila cuba untuk memasukkan Anita ke dalam struktur data ini? Yeah?

657
00:39:55,970 --> 00:39:58,610
[Pelajar jawapan, difahami]. Jadi, kita boleh menggerakkan orang lain ke bawah,

658
00:39:58,610 --> 00:40:03,040
seperti Charlie nudges turun Bob dan Alice, dan kemudian kita meletakkan Anita mana dia benar-benar mahu menjadi.

659
00:40:03,040 --> 00:40:05,660
>> Sudah tentu, sekarang, terdapat kesan sampingan ini.

660
00:40:05,660 --> 00:40:09,000
Ini struktur data mungkin berguna bukan kerana kita mahu untuk memasukkan orang sekali

661
00:40:09,000 --> 00:40:11,250
tetapi kerana kita mahu untuk memeriksa jika ia berada di sana kemudian

662
00:40:11,250 --> 00:40:13,600
jika kita ingin mencetak keluar semua nama dalam struktur data.

663
00:40:13,600 --> 00:40:15,850
Kami akan melakukan sesuatu dengan data ini akhirnya.

664
00:40:15,850 --> 00:40:20,810
Jadi sekarang kita telah jenis diskru lebih Alice, yang tidak lagi di mana dia sepatutnya.

665
00:40:20,810 --> 00:40:23,880
Nor adalah Bob, mahupun Charlie.

666
00:40:23,880 --> 00:40:26,060
Jadi mungkin ini tidak seperti idea yang baik.

667
00:40:26,060 --> 00:40:28,830
Tetapi sesungguhnya, ini adalah satu pilihan. Kita boleh beralih semua orang turun,

668
00:40:28,830 --> 00:40:32,240
atau palang pintu, Anita datang lewat untuk permainan, mengapa tidak kita hanya meletakkan Anita

669
00:40:32,240 --> 00:40:35,870
bukan di sini, bukan di sini, bukan di sini, mari kita hanya meletakkan beliau sedikit lebih rendah dalam senarai.

670
00:40:35,870 --> 00:40:38,680
Tetapi maka masalah ini mula diturunkan lagi.

671
00:40:38,680 --> 00:40:41,630
Anda mungkin dapat mencari Alice serta-merta, berdasarkan nama pertama beliau.

672
00:40:41,630 --> 00:40:44,320
Dan Bob serta-merta, dan Charlie. Tetapi kemudian anda mencari Anita,

673
00:40:44,320 --> 00:40:46,360
dan anda lihat, hmm, Alice di jalan.

674
00:40:46,360 --> 00:40:48,770
Baiklah, biar saya cek di bawah Alice. Bob bukan Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie tidak Anita. Oh, ada Anita.

676
00:40:51,850 --> 00:40:54,720
Dan jika anda terus bahawa kereta api logik sepanjang jalan,

677
00:40:54,720 --> 00:41:00,690
apa masa kes terburuk berjalan mencari atau memasukkan Anita ke dalam struktur data ini baru?

678
00:41:00,690 --> 00:41:03,280
Ia O (n), betul-betul?

679
00:41:03,280 --> 00:41:06,280
Kerana dalam kes terburuk, ada Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
sepanjang jalan turun kepada seseorang yang bernama "Y", jadi hanya ada satu tempat ke kiri.

681
00:41:10,150 --> 00:41:13,950
Syukurlah, kita tidak mempunyai satu dipanggil "Z", jadi kita meletakkan Anita di bahagian paling bawah.

682
00:41:13,950 --> 00:41:16,040
>> Kami telah tidak benar-benar menyelesaikan masalah itu.

683
00:41:16,040 --> 00:41:19,890
Jadi mungkin kita perlu untuk memperkenalkan dimensi ketiga.

684
00:41:19,890 --> 00:41:22,230
Dan ternyata, jika kita memperkenalkan dimensi ketiga,

685
00:41:22,230 --> 00:41:25,240
kita tidak boleh melakukan ini dengan sempurna, tetapi Holy Grail akan mendapat

686
00:41:25,240 --> 00:41:28,370
kemasukan malar masa dan sisipan dinamik supaya

687
00:41:28,370 --> 00:41:30,960
kita tidak perlu keras kod pelbagai saiz sebanyak 26.

688
00:41:30,960 --> 00:41:34,400
Kita boleh memasukkan sebagai banyak nama seperti yang kita mahu, tetapi mari kita rehat 5-minit kami di sini

689
00:41:34,400 --> 00:41:38,790
dan kemudian lakukan yang betul.

690
00:41:38,790 --> 00:41:46,020
Semua hak. Saya menetapkan cerita sehingga cukup buatan sana

691
00:41:46,020 --> 00:41:48,670
dengan memilih Alice dan Bob dan kemudian kemudian Charlie dan kemudian Anita,

692
00:41:48,670 --> 00:41:51,000
yang namanya telah jelas akan bertembung dengan Alice.

693
00:41:51,000 --> 00:41:54,120
Tetapi soalan yang kita berakhir pada hari Isnin dengan betapa kemungkinan ia

694
00:41:54,120 --> 00:41:56,370
bahawa anda akan mendapat jenis-jenis perlanggaran? Dalam erti kata lain,

695
00:41:56,370 --> 00:42:00,490
jika kita mula menggunakan struktur jadual, yang benar-benar hanya pelbagai,

696
00:42:00,490 --> 00:42:02,460
dalam kes ini, sebanyak 26 lokasi,

697
00:42:02,460 --> 00:42:05,740
apa jika input kami bukannya teragih seragam?

698
00:42:05,740 --> 00:42:09,620
Ia bukan buatan Alice dan Bob dan Charlie dan David dan sebagainya mengikut abjad,

699
00:42:09,620 --> 00:42:12,380
ia teragih seragam A hingga Z.

700
00:42:12,380 --> 00:42:15,220
>> Mungkin kita hanya akan mendapat bernasib baik dan kita tidak akan mempunyai dua A atau dua B

701
00:42:15,220 --> 00:42:17,640
dengan kebarangkalian yang sangat tinggi, tetapi sebagai seseorang menegaskan,

702
00:42:17,640 --> 00:42:20,730
jika kita umum masalah ini dan tidak melakukan 0-25

703
00:42:20,730 --> 00:42:26,060
tetapi, katakan, 0 hingga 364 atau 65, sering bilangan hari dalam tahun yang biasa,

704
00:42:26,060 --> 00:42:31,170
dan bertanya soalan, "Apakah kebarangkalian bahawa dua daripada kita di dalam bilik ini mempunyai ulang tahun yang sama?"

705
00:42:31,170 --> 00:42:34,600
Letakkan ia cara yang lain, apakah kebarangkalian bahawa dua daripada kita mempunyai nama yang bermula dengan A?

706
00:42:34,600 --> 00:42:37,190
Jenis soalan adalah sama, tetapi ini ruang alamat,

707
00:42:37,190 --> 00:42:39,940
ini ruang carian, adalah lebih besar dalam kes hari lahir,

708
00:42:39,940 --> 00:42:42,820
kerana kita mempunyai begitu banyak hari lagi dalam tahun daripada huruf dalam abjad.

709
00:42:42,820 --> 00:42:44,910
Apakah kebarangkalian perlanggaran?

710
00:42:44,910 --> 00:42:48,410
Nah, kita boleh berfikir ini dengan memikirkan matematik dengan cara yang bertentangan.

711
00:42:48,410 --> 00:42:50,580
Apakah kebarangkalian tiada perlanggaran?

712
00:42:50,580 --> 00:42:53,970
Nah, ini ungkapan di sini mengatakan bahawa apa yang kebarangkalian

713
00:42:53,970 --> 00:42:58,770
jika terdapat hanya satu orang di dalam bilik ini, bahawa mereka mempunyai harijadi yang unik?

714
00:42:58,770 --> 00:43:01,190
Ia adalah 100%. Kerana jika terdapat hanya satu orang di dalam bilik,

715
00:43:01,190 --> 00:43:03,940
atau ulang tahun beliau boleh menjadi apa-apa daripada 365 hari daripada tahun.

716
00:43:03,940 --> 00:43:08,650
Jadi pilihan yang 365/365 memberikan saya nilai 1.

717
00:43:08,650 --> 00:43:11,250
Jadi kebarangkalian dalam soalan pada masa ini adalah hanya 1.

718
00:43:11,250 --> 00:43:13,270
Tetapi jika ada orang kedua di dalam bilik,

719
00:43:13,270 --> 00:43:16,490
apakah kebarangkalian bahawa hari lahir mereka adalah berbeza?

720
00:43:16,490 --> 00:43:20,680
Terdapat hanya 364 hari mungkin, mengabaikan tahun lompat,

721
00:43:20,680 --> 00:43:23,580
untuk hari jadi mereka tidak bertembung dengan orang lain.

722
00:43:23,580 --> 00:43:31,920
Jadi 364/365. Jika orang ketiga datang dalam, ia adalah 363/365, dan sebagainya.

723
00:43:31,920 --> 00:43:35,790
Jadi kita menyimpan mendarabkan bersama pecahan ini, yang mendapat lebih kecil dan lebih kecil,

724
00:43:35,790 --> 00:43:40,720
untuk memikirkan apakah kebarangkalian bahawa kita semua mempunyai tarikh lahir yang unik?

725
00:43:40,720 --> 00:43:43,570
Tetapi maka kita boleh, sudah tentu, hanya mengambil jawapan itu dan flip sekeliling

726
00:43:43,570 --> 00:43:47,210
dan melakukan 1 tolak semua itu, satu ungkapan yang akhirnya kita akan mendapat

727
00:43:47,210 --> 00:43:51,250
jika anda ingat kembali buku-buku matematik anda, ia kelihatan sesuatu yang kecil seperti ini,

728
00:43:51,250 --> 00:43:54,590
yang lebih mudah ditafsirkan grafik.

729
00:43:54,590 --> 00:43:57,820
Dan ini grafik sini mempunyai pada paksi x bilangan hari lahir,

730
00:43:57,820 --> 00:44:02,030
atau bilangan orang dengan hari lahir, dan pada paksi y adalah kebarangkalian perlawanan.

731
00:44:02,030 --> 00:44:06,060
Dan apa ini mengatakan adalah bahawa jika anda mempunyai, katakan, walaupun,

732
00:44:06,060 --> 00:44:10,860
mari kita memilih sesuatu seperti 22, 23.

733
00:44:10,860 --> 00:44:13,160
Jika ada 22 atau 23 orang di dalam bilik,

734
00:44:13,160 --> 00:44:17,100
kebarangkalian bahawa dua orang-orang yang sangat sedikit akan mempunyai hari lahir yang sama

735
00:44:17,100 --> 00:44:19,560
sebenarnya tinggi super, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% kemungkinan bahawa dalam kelas hanya 22 orang, seminar, praktikal,

737
00:44:23,450 --> 00:44:25,790
2 orang-orang akan mempunyai hari lahir yang sama.

738
00:44:25,790 --> 00:44:28,520
Kerana terdapat banyak cara di mana anda boleh mempunyai hari lahir yang sama.

739
00:44:28,520 --> 00:44:31,110
Lebih buruk lagi, jika anda melihat di sebelah kanan carta,

740
00:44:31,110 --> 00:44:34,040
pada masa anda mempunyai kelas dengan 58 orang pelajar di dalamnya,

741
00:44:34,040 --> 00:44:39,270
kebarangkalian 2 orang yang mempunyai hari lahir adalah super, tinggi super, hampir 100%.

742
00:44:39,270 --> 00:44:41,880
Sekarang, itulah jenis fakta yang menyeronokkan tentang kehidupan sebenar.

743
00:44:41,880 --> 00:44:45,850
>> Tetapi implikasi, sekarang, untuk struktur data dan menyimpan maklumat

744
00:44:45,850 --> 00:44:51,100
bermakna bahawa hanya menganggap anda mempunyai bagus, bersih, pengagihan seragam data

745
00:44:51,100 --> 00:44:53,650
dan anda mempunyai pelbagai cukup besar untuk memuatkan sejambak perkara

746
00:44:53,650 --> 00:44:59,360
tidak bermakna anda akan mendapatkan orang ramai di lokasi-lokasi yang unik.

747
00:44:59,360 --> 00:45:03,810
Anda akan mempunyai perlanggaran. Jadi ini tanggapan hashing, kerana ia dipanggil,

748
00:45:03,810 --> 00:45:07,450
mengambil input seperti "Alice" dan mengurut ia dalam beberapa cara

749
00:45:07,450 --> 00:45:10,190
dan kemudian mendapatkan kembali jawapan seperti 0 atau 1 atau 2.

750
00:45:10,190 --> 00:45:17,500
Mendapatkan kembali beberapa output dari fungsi yang dibelenggu oleh kebarangkalian ini perlanggaran.

751
00:45:17,500 --> 00:45:19,530
Jadi bagaimana kita boleh mengendalikan orang-orang perlanggaran?

752
00:45:19,530 --> 00:45:21,940
Nah, dalam satu kes, kita boleh mengambil idea yang telah dicadangkan.

753
00:45:21,940 --> 00:45:25,100
Kami hanya boleh beralih ke bawah, atau mungkin, lebih sedikit semata-mata,

754
00:45:25,100 --> 00:45:29,870
bukan daripada orang bergerak lagi, mari kita hanya bergerak Anita ke bawah tempat ada.

755
00:45:29,870 --> 00:45:32,810
Jadi jika Alice adalah dalam 0, Bob adalah dalam 1, Charlie adalah dalam 2,

756
00:45:32,810 --> 00:45:35,260
kita hanya akan meletakkan Anita di lokasi 3.

757
00:45:35,260 --> 00:45:38,860
Dan ini adalah satu teknik dalam struktur data dipanggil linear menyelesaikan sesuatu.

758
00:45:38,860 --> 00:45:41,310
Linear kerana anda hanya berjalan baris ini, dan anda jenis menyelesaikan sesuatu

759
00:45:41,310 --> 00:45:43,640
bintik didapati dalam struktur data.

760
00:45:43,640 --> 00:45:46,210
Sudah tentu, ini turun ke O (n).

761
00:45:46,210 --> 00:45:49,590
Jika struktur data yang benar-benar penuh, terdapat 25 orang di dalamnya sudah,

762
00:45:49,590 --> 00:45:54,120
dan kemudian Anita datang bersama-sama, dia akan berakhir pada apa yang akan menjadi lokasi Z, dan itulah denda.

763
00:45:54,120 --> 00:45:56,540
Dia masih sesuai, dan kita boleh mencari beliau kemudian.

764
00:45:56,540 --> 00:46:00,100
>> Tetapi ini adalah bertentangan dengan matlamat mempercepatkan perkara.

765
00:46:00,100 --> 00:46:02,530
Jadi apa jika kita bukannya memperkenalkan dimensi ketiga?

766
00:46:02,530 --> 00:46:06,400
Bahawa teknik secara umumnya dipanggil chaining berasingan, atau mempunyai rantaian.

767
00:46:06,400 --> 00:46:10,030
Dan apa jadual hash kini, struktur jadual,

768
00:46:10,030 --> 00:46:13,450
jadual anda hanya pelbagai petunjuk.

769
00:46:13,450 --> 00:46:18,230
Tetapi apa yang mereka menunjukkan petunjuk untuk meneka apa?

770
00:46:18,230 --> 00:46:21,970
Satu senarai yang dipautkan. Jadi apa jika kita mengambil yang terbaik daripada kedua-dua dunia ini?

771
00:46:21,970 --> 00:46:26,500
Kami menggunakan tatasusunan untuk indeks awal

772
00:46:26,500 --> 00:46:32,070
ke dalam struktur data supaya kita serta-merta boleh pergi ke [0] [1], [30] atau sebagainya,

773
00:46:32,070 --> 00:46:36,480
tetapi supaya kita mempunyai beberapa fleksibiliti dan kita boleh memuatkan Anita dan Alice dan Adam

774
00:46:36,480 --> 00:46:38,630
dan apa-apa nama lain,

775
00:46:38,630 --> 00:46:43,470
kami bukannya membiarkan paksi lain berkembang secara sewenang-wenangnya.

776
00:46:43,470 --> 00:46:47,340
Dan kita akhirnya, hari Isnin, mempunyai keupayaan yang ekspresif dengan senarai berpaut.

777
00:46:47,340 --> 00:46:49,530
Kita boleh berkembang struktur data dengan sewenang-wenangnya.

778
00:46:49,530 --> 00:46:52,450
Selain itu, kita hanya boleh membuat pelbagai besar 2-dimensi,

779
00:46:52,450 --> 00:46:57,190
tetapi itu akan menjadi situasi yang buruk jika salah satu baris dalam pelbagai 2-dimensi

780
00:46:57,190 --> 00:47:01,280
tidak cukup besar bagi orang tambahan yang namanya berlaku untuk memulakan dengan A.

781
00:47:01,280 --> 00:47:04,200
Dubilah kita perlu mengagihkan semula besar 2-dimensi struktur

782
00:47:04,200 --> 00:47:06,600
hanya kerana terdapat begitu ramai orang yang dinamakan sebagai A,

783
00:47:06,600 --> 00:47:09,480
terutamanya apabila terdapat begitu beberapa orang bernama Z sesuatu.

784
00:47:09,480 --> 00:47:12,170
Ia hanya akan menjadi satu struktur data yang sangat jarang.

785
00:47:12,170 --> 00:47:15,400
Jadi ia tidak sesuai dengan apa-apa cara, tetapi sekarang kita sekurang-kurangnya mempunyai keupayaan

786
00:47:15,400 --> 00:47:19,090
untuk segera mencari mana Alice atau Anita kepunyaan,

787
00:47:19,090 --> 00:47:21,090
sekurang-kurangnya dari segi paksi menegak,

788
00:47:21,090 --> 00:47:25,850
dan kemudian kita hanya perlu untuk membuat keputusan di mana untuk meletakkan Anita atau Alice dalam senarai ini dikaitkan.

789
00:47:25,850 --> 00:47:32,480
Jika kita tidak mengambil berat tentang perkara sorting, berapa cepat kita boleh memasukkan Alice ke dalam struktur seperti ini?

790
00:47:32,480 --> 00:47:35,370
Ia adalah masa yang berterusan. Kami indeks ke [0], dan jika terdapat tiada siapa,

791
00:47:35,370 --> 00:47:37,550
Alice pergi pada permulaan senarai yang dikaitkan.

792
00:47:37,550 --> 00:47:40,000
Tetapi itu bukan satu perjanjian yang besar. Kerana jika Anita kemudian datang bersama-sama

793
00:47:40,000 --> 00:47:42,160
beberapa beberapa langkah kemudian, di mana tidak Anita tergolong?

794
00:47:42,160 --> 00:47:45,140
Nah, [0]. Oop. Alice sudah dalam senarai itu dikaitkan.

795
00:47:45,140 --> 00:47:47,760
>> Tetapi jika kita tidak mengambil berat tentang mengasingkan nama-nama ini,

796
00:47:47,760 --> 00:47:53,580
kita hanya boleh bergerak Alice atas, memasukkan Anita, tetapi walaupun yang pemalar masa.

797
00:47:53,580 --> 00:47:57,010
Walaupun terdapat Alice dan Adam dan semua ini lain nama,

798
00:47:57,010 --> 00:47:59,410
ia tidak benar-benar beralih mereka secara fizikal. Mengapa?

799
00:47:59,410 --> 00:48:04,090
Kerana kita hanya lakukan di sini dengan senarai yang berkaitan, siapa tahu nod ini adalah anyway?

800
00:48:04,090 --> 00:48:06,550
Semua yang anda perlu lakukan adalah menggerakkan serbuk roti.

801
00:48:06,550 --> 00:48:10,930
Gerakkan anak panah di sekeliling, anda tidak mempunyai fizikal bergerak sebarang data di sekeliling.

802
00:48:10,930 --> 00:48:14,610
Jadi kita boleh memasukkan Anita, dalam kes itu, dengan serta-merta. Pemalar masa.

803
00:48:14,610 --> 00:48:20,250
Jadi kita mempunyai masa malar lookup, dan masa malar memasukkan seseorang seperti Anita.

804
00:48:20,250 --> 00:48:22,740
Tetapi jenis oversimplifying dunia.

805
00:48:22,740 --> 00:48:28,510
Apakah jika kita kemudian mahu untuk mencari Alice?

806
00:48:28,510 --> 00:48:31,050
Apakah jika kita kemudian mahu untuk mencari Alice?

807
00:48:31,050 --> 00:48:35,690
Berapa banyak langkah-langkah yang akan mengambil?

808
00:48:35,690 --> 00:48:37,850
[Pelajar jawapan, difahami]

809
00:48:37,850 --> 00:48:40,950
Tepat sekali. Bilangan orang yang sebelum Alice dalam senarai berkaitan.

810
00:48:40,950 --> 00:48:45,420
Jadi ia tidak cukup sempurna, kerana struktur data kami, sekali lagi, mempunyai akses ini menegak

811
00:48:45,420 --> 00:48:50,240
dan kemudian ia mempunyai senarai ini berkaitan tergantung - sebenarnya, mari kita tidak menarik ia pelbagai.

812
00:48:50,240 --> 00:48:56,020
Ia telah senarai ini dikaitkan tergantung kira ia yang kelihatan sesuatu yang sedikit seperti ini.

813
00:48:56,020 --> 00:48:59,110
Tetapi masalahnya ialah jika Alice dan Adam dan semua ini lain nama

814
00:48:59,110 --> 00:49:01,720
akhirnya lebih dan lebih di sana,

815
00:49:01,720 --> 00:49:04,810
mencari seseorang yang boleh berakhir sehingga mengambil sekumpulan langkah-langkah,

816
00:49:04,810 --> 00:49:06,670
bcause anda perlu merentasi senarai berpaut,

817
00:49:06,670 --> 00:49:08,090
yang merupakan operasi linear.

818
00:49:08,090 --> 00:49:14,270
Jadi benar-benar, maka, masa kemasukan akhirnya adalah O (n), di mana n adalah bilangan elemen dalam senarai.

819
00:49:14,270 --> 00:49:21,780
Dibahagikan dengan, mari kita sewenang-wenangnya memanggil ia m, di mana m adalah bilangan senarai berkaitan

820
00:49:21,780 --> 00:49:24,500
bahawa kita mempunyai dalam paksi ini menegak.

821
00:49:24,500 --> 00:49:27,180
Dalam erti kata lain, jika kita benar-benar menganggap pengagihan seragam nama,

822
00:49:27,180 --> 00:49:30,150
sama sekali tidak realistik. Terdapat jelas lebih beberapa surat daripada yang lain.

823
00:49:30,150 --> 00:49:32,580
>> Tetapi jika kita menganggap seketika pengagihan seragam,

824
00:49:32,580 --> 00:49:37,350
dan kami telah n rakyat keseluruhan, dan m rantaian jumlah

825
00:49:37,350 --> 00:49:40,630
ada pada kita, maka panjang setiap rangkaian

826
00:49:40,630 --> 00:49:44,380
agak hanya akan menjadi jumlah, n dibahagikan dengan bilangan rantai.

827
00:49:44,380 --> 00:49:48,900
Jadi n / m. Tetapi di sini adalah di mana kita boleh menjadi semua pandai matematik.

828
00:49:48,900 --> 00:49:53,030
m ialah pemalar, kerana ada beberapa yang tetap ini.

829
00:49:53,030 --> 00:49:54,620
Anda akan mengisytiharkan array anda pada permulaan,

830
00:49:54,620 --> 00:49:58,450
dan kita tidak saiz semula paksi menegak. Dengan definisi, yang tetap tetap.

831
00:49:58,450 --> 00:50:01,220
Ia hanya paksi mendatar, jadi untuk bercakap, yang mengubah.

832
00:50:01,220 --> 00:50:04,760
Jadi secara teknikal, ini adalah satu pemalar. Jadi sekarang, masa kemasukan

833
00:50:04,760 --> 00:50:09,700
adalah cukup banyak O (n).

834
00:50:09,700 --> 00:50:12,410
Supaya tidak merasa semua yang jauh lebih baik.

835
00:50:12,410 --> 00:50:14,940
Tetapi apa kebenaran di sini? Nah, semua masa ini, untuk minggu,

836
00:50:14,940 --> 00:50:20,640
kita telah mengatakan O (n ²). O (n), 2 x n ², - n, dibahagikan dengan 2. . . ECH.

837
00:50:20,640 --> 00:50:23,580
Ia hanya ² n. Tetapi sekarang, dalam bahagian ini semester,

838
00:50:23,580 --> 00:50:25,560
kita boleh mula bercakap tentang dunia sebenar lagi.

839
00:50:25,560 --> 00:50:31,520
Dan n / m sememangnya lebih cepat daripada hanya n sahaja.

840
00:50:31,520 --> 00:50:35,170
Jika anda mempunyai seribu nama, dan anda memecahkan mereka ke dalam baldi pelbagai

841
00:50:35,170 --> 00:50:37,820
supaya anda mempunyai hanya sepuluh nama dalam setiap rangkaian,

842
00:50:37,820 --> 00:50:41,670
benar-benar mencari sepuluh perkara akan menjadi lebih cepat daripada seribu perkara.

843
00:50:41,670 --> 00:50:43,740
Dan sebagainya salah satu set masalah yang akan datang akan mencabar anda

844
00:50:43,740 --> 00:50:46,100
untuk berfikir tentang tepat bahawa walaupun, yeah,

845
00:50:46,100 --> 00:50:49,520
berasimptot dan matematik, ini masih hanya linear,

846
00:50:49,520 --> 00:50:51,700
yang menghisap secara umum apabila cuba untuk mencari perkara-perkara.

847
00:50:51,700 --> 00:50:54,530
Dalam realiti, ia akan menjadi lebih cepat daripada yang

848
00:50:54,530 --> 00:50:56,520
kerana pembahagi ini.

849
00:50:56,520 --> 00:50:58,310
Dan sebagainya ada lagi akan menjadi trade-off ini

850
00:50:58,310 --> 00:51:01,390
dan ini konflik antara teori dan realiti,

851
00:51:01,390 --> 00:51:03,550
dan salah satu tombol akan mula buka pada ketika ini dalam semester

852
00:51:03,550 --> 00:51:07,510
adalah lebih daripada satu realiti seperti yang kita jenis bersedia untuk akhir semster,

853
00:51:07,510 --> 00:51:09,280
seperti yang kita memperkenalkan dunia pengaturcaraan web,

854
00:51:09,280 --> 00:51:11,530
mana benar-benar, prestasi akan untuk dikira kerana pengguna anda akan

855
00:51:11,530 --> 00:51:14,880
mula merasa dan menghargai keputusan reka bentuk yang miskin.

856
00:51:14,880 --> 00:51:19,950
>> Jadi bagaimana anda pergi tentang melaksanakan berkaitan - jadual hash dengan 31 unsur?

857
00:51:19,950 --> 00:51:22,600
Dan contoh sebelumnya adalah sewenang-wenangnya tentang hari lahir.

858
00:51:22,600 --> 00:51:26,190
Jika seseorang mempunyai hari lahir 1 Januari atau Februari 1, kami akan meletakkan mereka dalam baldi ini.

859
00:51:26,190 --> 00:51:28,960
Jika ia Januari 2, February 2, 2 Mac, kami akan meletakkan mereka dalam baldi ini.

860
00:51:28,960 --> 00:51:32,220
Itulah sebabnya ia adalah 31. Bagaimana anda mengisytiharkan jadual hash?

861
00:51:32,220 --> 00:51:37,480
Ia boleh agak mudah, jadual * nod adalah nama saya sewenang-wenangnya untuk itu, [31].

862
00:51:37,480 --> 00:51:42,400
Ini memberikan saya 31 petunjuk untuk nod,

863
00:51:42,400 --> 00:51:45,370
dan yang membolehkan saya untuk mempunyai 31 petunjuk untuk senarai yang dikaitkan

864
00:51:45,370 --> 00:51:48,800
walaupun orang-orang rantaian mulanya NULL.

865
00:51:48,800 --> 00:51:54,860
Apa yang saya ingin meletakkan jika saya mahu menyimpan "Alice," "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Nah, kita perlu untuk membalut perkara-perkara dalam struktur

867
00:51:57,010 --> 00:52:00,530
kerana kita perlu Alice untuk menunjukkan kepada Bob, untuk menunjukkan Charlie, dan sebagainya.

868
00:52:00,530 --> 00:52:04,940
Kita tidak boleh hanya mempunyai nama sahaja, jadi saya boleh mencipta satu struktur baru yang dipanggil nod sini.

869
00:52:04,940 --> 00:52:08,310
>> Apakah nod sebenar? Apakah nod dalam senarai baru ini dikaitkan?

870
00:52:08,310 --> 00:52:11,840
Perkara pertama, dipanggil perkataan, adalah untuk nama orang itu.

871
00:52:11,840 --> 00:52:14,340
LENGTH, mungkin, berkaitan dengan panjang maksimum nama manusia,

872
00:52:14,340 --> 00:52:18,210
apa yang, 20, 30, 40 watak-watak dalam kes sudut gila,

873
00:52:18,210 --> 00:52:22,680
dan +1 adalah untuk apa? Ia hanya watak NULL tambahan, \ 0.

874
00:52:22,680 --> 00:52:27,410
Jadi nod ini membungkus "sesuatu" di dalam sendirinya,

875
00:52:27,410 --> 00:52:29,640
tetapi ia juga mengisytiharkan penunjuk dipanggil seterusnya

876
00:52:29,640 --> 00:52:32,580
supaya kita dapat rantaian Bob Alice Charlie dan sebagainya.

877
00:52:32,580 --> 00:52:36,700
Boleh NULL tetapi tidak semestinya perlu.

878
00:52:36,700 --> 00:52:40,110
Sebarang pertanyaan mengenai jadual ini hash? Yeah?

879
00:52:40,110 --> 00:52:46,190
[Pelajar bertanya soalan, difahami] Pelbagai - soalan yang baik.

880
00:52:46,190 --> 00:52:50,120
Mengapa perkataan ini char dalam pelbagai bukannya hanya * char?

881
00:52:50,120 --> 00:52:53,830
Dalam contoh ini agak sewenang-wenangnya, saya tidak mahu perlu mengambil jalan keluar

882
00:52:53,830 --> 00:52:56,190
malloc untuk setiap nama asal.

883
00:52:56,190 --> 00:52:59,530
Saya mahu mengisytiharkan jumlah maksimum memori untuk tali

884
00:52:59,530 --> 00:53:06,020
supaya saya boleh menyalin ke dalam struktur Alice \ 0 dan tidak perlu berurusan dengan malloc dan bebas dan sebagainya.

885
00:53:06,020 --> 00:53:11,710
Tetapi saya boleh melakukannya jika saya mahu menjadi lebih sedar penggunaan ruang. Soalan yang baik.

886
00:53:11,710 --> 00:53:14,780
Jadi mari kita cuba untuk umum dari ini

887
00:53:14,780 --> 00:53:18,350
dan memberi tumpuan baki hari ini pada struktur data lebih amnya

888
00:53:18,350 --> 00:53:21,170
dan masalah-masalah lain yang kita boleh selesaikan dengan menggunakan asas-asas yang sama

889
00:53:21,170 --> 00:53:24,590
walaupun struktur data sendiri mungkin berbeza dalam butir-butir mereka.

890
00:53:24,590 --> 00:53:27,910
>> Jadi ia ternyata dalam bidang sains komputer, pokok-pokok yang sangat biasa.

891
00:53:27,910 --> 00:53:29,760
Dan anda boleh berfikir apapun pokok seperti pokok keluarga,

892
00:53:29,760 --> 00:53:31,830
di mana terdapat beberapa akar, beberapa ibu pemimpin keluarga atau bapa,

893
00:53:31,830 --> 00:53:34,540
nenek atau datuk atau awal kembali,

894
00:53:34,540 --> 00:53:38,880
yang mengalir di bawahnya adalah ibu dan ayah atau adik-beradik yang pelbagai atau sebagainya.

895
00:53:38,880 --> 00:53:42,500
Jadi struktur pokok mempunyai nod dan ia mempunyai anak-anak,

896
00:53:42,500 --> 00:53:45,260
biasanya 0 atau lebih kanak-kanak untuk setiap nod.

897
00:53:45,260 --> 00:53:47,320
Dan beberapa istilah yang anda lihat dalam gambar ini di sini

898
00:53:47,320 --> 00:53:50,630
adalah mana-mana anak-anak atau grandkids sedikit di tepi

899
00:53:50,630 --> 00:53:52,330
yang tidak mempunyai anak panah yang berpunca daripada mereka,

900
00:53:52,330 --> 00:53:55,070
mereka adalah daun kononnya, dan sesiapa sahaja di dalam

901
00:53:55,070 --> 00:53:58,790
merupakan nod dalaman; anda boleh memanggilnya apa-apa sepanjang mereka baris.

902
00:53:58,790 --> 00:54:01,430
Tetapi struktur ini adalah agak biasa. Satu ini sedikit sewenang-wenangnya.

903
00:54:01,430 --> 00:54:04,930
Kami mempunyai seorang kanak-kanak di sebelah kiri, kita mempunyai tiga kanak-kanak di sebelah kanan,

904
00:54:04,930 --> 00:54:06,830
dua kanak-kanak di bawah kiri.

905
00:54:06,830 --> 00:54:10,740
Supaya kita boleh mempunyai pokok-pokok bersaiz berbeza-, tetapi jika kita mula untuk menyeragamkan perkara,

906
00:54:10,740 --> 00:54:15,330
dan anda mungkin ingat ini dari Patrick video pada carian binari dari pendek sebelumnya

907
00:54:15,330 --> 00:54:19,490
talian, gelintaran perduaan tidak perlu dilaksanakan dengan pelbagai

908
00:54:19,490 --> 00:54:21,410
atau keping kertas di papan hitam.

909
00:54:21,410 --> 00:54:25,490
Katakan yang anda ingin menyimpan nombor anda dalam struktur data yang lebih canggih.

910
00:54:25,490 --> 00:54:27,680
Anda boleh membuat pokok seperti ini.

911
00:54:27,680 --> 00:54:35,290
Anda boleh mempunyai nod yang diisytiharkan dalam C, dan nod yang boleh mempunyai sekurang-kurangnya dua unsur di dalamnya.

912
00:54:35,290 --> 00:54:39,470
Salah satu adalah nombor yang anda mahu untuk menyimpan, dan lain-lain - baik, kita perlu satu lagi.

913
00:54:39,470 --> 00:54:41,540
Yang lain adalah anak-anak itu.

914
00:54:41,540 --> 00:54:45,150
Jadi di sini adalah satu lagi struktur data. Masa ini, nod ditakrifkan sebagai menyimpan nombor n

915
00:54:45,150 --> 00:54:49,060
dan kemudian dua petunjuk; anak kiri dan kanak-kanak yang betul.

916
00:54:49,060 --> 00:54:52,100
Dan mereka tidak sewenang-wenangnya. Apa yang menarik tentang pokok ini?

917
00:54:52,100 --> 00:55:00,550
>> Apakah corak dalam bagaimana kita telah dibentangkan ini keluar atau bagaimana Patrick meletakkan ia keluar dalam video itu?

918
00:55:00,550 --> 00:55:02,790
Ia adalah jenis jelas bahawa terdapat beberapa sorting berlaku di sini,

919
00:55:02,790 --> 00:55:04,460
tetapi apa peraturan yang mudah? Yeah?

920
00:55:04,460 --> 00:55:08,350
[Pelajar jawapan, difahami]

921
00:55:08,350 --> 00:55:12,040
Sempurna. Jika anda pandang pada ini, anda melihat nombor kecil di sebelah kiri,

922
00:55:12,040 --> 00:55:14,690
nombor besar di sebelah kiri, tetapi itulah benar bagi setiap nod.

923
00:55:14,690 --> 00:55:20,370
Bagi setiap nod, anak kiri kurang daripada itu, dan anak kanan lebih besar daripada itu.

924
00:55:20,370 --> 00:55:25,210
Apakah ini bermakna sekarang adalah jika saya ingin mencari struktur data untuk, katakan, bilangan 44,

925
00:55:25,210 --> 00:55:29,320
Saya perlu bermula pada akar, kerana sebagai dengan semua ini struktur data yang lebih kompleks sekarang,

926
00:55:29,320 --> 00:55:31,910
kita hanya mempunyai penunjuk kepada satu perkara, permulaan.

927
00:55:31,910 --> 00:55:35,010
Dan dalam kes ini, permulaan adalah akar. Ia bukan akhir kiri,

928
00:55:35,010 --> 00:55:39,530
ia adalah akar struktur ini. Jadi saya lihat di sini adalah 55, dan saya mencari untuk 44.

929
00:55:39,530 --> 00:55:41,430
Arah mana saya mahu pergi?

930
00:55:41,430 --> 00:55:45,680
Well, saya mahu pergi ke kiri, kerana jelas, ke kanan akan menjadi terlalu besar.

931
00:55:45,680 --> 00:55:49,050
Jadi notis di sini, anda jenis konsep mencincang pokok dalam separuh

932
00:55:49,050 --> 00:55:51,700
kerana anda pernah pergi ke sebelah kanan.

933
00:55:51,700 --> 00:55:55,410
Jadi sekarang saya pergi dari 55 kepada 33. Ia adalah terlalu kecil nombor.

934
00:55:55,410 --> 00:56:01,590
Saya mencari 44, tetapi sekarang saya tahu jika 44 adalah dalam pokok ini, saya boleh pergi jelas ke kanan.

935
00:56:01,590 --> 00:56:04,460
Jadi sekali lagi, saya pemangkasan pokok di separuh.

936
00:56:04,460 --> 00:56:06,780
Ia adalah cukup banyak sama konsepnya kepada buku telefon.

937
00:56:06,780 --> 00:56:09,510
Ia adalah serupa dengan apa yang kita lakukan dengan kertas di papan hitam,

938
00:56:09,510 --> 00:56:13,940
tetapi ia adalah struktur yang lebih canggih yang membolehkan kita untuk benar-benar melakukan

939
00:56:13,940 --> 00:56:16,880
ini membahagi dan menakluk oleh reka bentuk algoritma,

940
00:56:16,880 --> 00:56:19,420
dan pada hakikatnya, menyeberangi satu struktur seperti ini - Oop.

941
00:56:19,420 --> 00:56:22,870
Menyeberangi struktur seperti ini, di mana ia hanya "pergi cara ini atau pergi dengan cara itu,"

942
00:56:22,870 --> 00:56:26,870
ertinya semua bahawa kod yang bengkok fikiran anda pada mulanya apabila melaksanakan dalam seksyen

943
00:56:26,870 --> 00:56:31,270
atau berjalan melalui di rumah, untuk carian binari, menggunakan rekursi atau lelaran,

944
00:56:31,270 --> 00:56:35,060
ia adalah sakit di leher. Cari elemen tengah, kemudian melakukan pembundaran anda ke atas atau ke bawah.

945
00:56:35,060 --> 00:56:39,230
>> Ada kecantikan ini kerana kita kini boleh menggunakan rekursi lagi,

946
00:56:39,230 --> 00:56:43,760
tetapi lebih bersih. Malah, jika anda berada di nombor 55 tahun dan anda ingin mencari 44,

947
00:56:43,760 --> 00:56:48,450
anda pergi kiri dalam kes ini, maka apa yang anda lakukan? Anda menjalankan algoritma yang sama yang tepat.

948
00:56:48,450 --> 00:56:51,560
Anda menyemak nilai nod, maka anda pergi kiri atau kanan.

949
00:56:51,560 --> 00:56:53,670
Kemudian anda memeriksa nilai nod, pergi kiri atau kanan.

950
00:56:53,670 --> 00:56:56,710
Ini amat sesuai untuk rekursi.

951
00:56:56,710 --> 00:57:00,920
Jadi walaupun pada masa lalu kita telah melakukan beberapa contoh yang agak sewenang-wenangnya melibatkan rekursi

952
00:57:00,920 --> 00:57:03,430
yang tidak perlu menjadi rekursi, dengan stuctures data,

953
00:57:03,430 --> 00:57:07,820
terutama pokok, ia adalah satu permohonan sempurna idea ini mengambil masalah,

954
00:57:07,820 --> 00:57:12,920
mengecut, dan kemudian menyelesaikan jenis yang sama, tetapi lebih kecil, program.

955
00:57:12,920 --> 00:57:14,590
>> Jadi ada satu lagi struktur data yang kita boleh memperkenalkan.

956
00:57:14,590 --> 00:57:18,760
Yang satu ini direka pada pandangan pertama kelihatan samar, tetapi yang satu ini menakjubkan.

957
00:57:18,760 --> 00:57:25,090
Jadi ini adalah satu struktur data dipanggil indone, indone, yang diwarisi dari semula perkataan,

958
00:57:25,090 --> 00:57:30,210
yang tidak disebut semula cuba-Val, tetapi itulah apa yang dunia panggilan perkara-perkara ini. Cuba. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Ia merupakan struktur pokok beberapa jenis, tetapi setiap nod dalam indone

960
00:57:35,190 --> 00:57:41,280
muncul untuk menjadi apa? Dan ini adalah agak mengelirukan kerana ia adalah jenis singkatan.

961
00:57:41,280 --> 00:57:45,960
Tetapi ia kelihatan seperti setiap nod di indone ini adalah sebenarnya array.

962
00:57:45,960 --> 00:57:48,840
Dan walaupun pengarang gambarajah ini telah tidak menunjukkan ia,

963
00:57:48,840 --> 00:57:54,130
dalam kes ini, indone ini adalah struktur data yang tujuan dalam kehidupan adalah untuk menyimpan perkataan

964
00:57:54,130 --> 00:57:57,330
seperti A-l-i-c-e atau B-o-b.

965
00:57:57,330 --> 00:58:02,480
Dan cara di mana data ini kedai Alice dan Bob dan Charlie dan Anita dan sebagainya

966
00:58:02,480 --> 00:58:06,970
ia menggunakan array mana untuk menyimpan Alice in indone satu,

967
00:58:06,970 --> 00:58:09,820
kita mula pada nod akar yang kelihatan seperti array,

968
00:58:09,820 --> 00:58:12,080
dan ia telah ditulis dalam notasi trengkas.

969
00:58:12,080 --> 00:58:15,070
Penulis ditinggalkan ABCDEFG kerana tidak ada nama dengan itu.

970
00:58:15,070 --> 00:58:19,150
Mereka hanya menunjukkan M dan P dan T, tetapi dalam kes ini,

971
00:58:19,150 --> 00:58:22,780
mari kita bergerak jauh dari Alice dan Bob dan Charlie untuk beberapa nama-nama yang berada di sini.

972
00:58:22,780 --> 00:58:25,670
Maxwell sebenarnya dalam gambar rajah ini.

973
00:58:25,670 --> 00:58:29,570
Jadi bagaimana pula kedai pengarang M-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Beliau bermula pada nod akar, dan pergi ke [M], jadi kira-kira 13, lokasi ke-13 dalam array.

975
00:58:36,990 --> 00:58:40,750
Kemudian dari situ, terdapat penunjuk.

976
00:58:40,750 --> 00:58:42,760
Satu penunjuk yang membawa kepada pelbagai lain.

977
00:58:42,760 --> 00:58:47,880
Dari situ penulis diindeks ke dalam tatasusunan yang di lokasi A, seperti yang digambarkan terdapat di sebelah kiri atas,

978
00:58:47,880 --> 00:58:52,250
dan kemudian dia diikuti penunjuk bahawa kepada pelbagai yang lain,

979
00:58:52,250 --> 00:58:55,460
dan pergi ke penunjuk di lokasi X.

980
00:58:55,460 --> 00:58:59,840
Kemudian di lokasi array seterusnya W, E, L, L, dan sebagainya,

981
00:58:59,840 --> 00:59:03,090
dan akhirnya, mari kita sebenarnya cuba untuk meletakkan gambar ini.

982
00:59:03,090 --> 00:59:05,380
Apakah lihat nod seperti dalam kod?

983
00:59:05,380 --> 00:59:11,820
Satu nod dalam indone mengandungi pelbagai petunjuk ke nodus lebih.

984
00:59:11,820 --> 00:59:16,090
Tetapi ada juga mendapat menjadi beberapa jenis nilai boolean, sekurang-kurangnya dalam pelaksanaan ini.

985
00:59:16,090 --> 00:59:18,770
Saya berlaku memanggilnya is_word. Mengapa?

986
00:59:18,770 --> 00:59:22,670
Kerana apabila anda memasukkan, Maxwell, anda tidak memasukkan

987
00:59:22,670 --> 00:59:25,300
apa-apa ke dalam struktur data ini.

988
00:59:25,300 --> 00:59:27,480
Anda tidak menulis M. Anda tidak menulis X.

989
00:59:27,480 --> 00:59:30,240
Semua yang anda lakukan adalah mengikuti petunjuk.

990
00:59:30,240 --> 00:59:33,360
Penunjuk yang mewakili M, maka penunjuk yang mewakili A,

991
00:59:33,360 --> 00:59:36,310
maka penunjuk yang mewakili X, maka W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
tetapi apa yang perlu anda lakukan pada akhir adalah jenis pergi, memeriksa, saya sampai ke lokasi ini.

993
00:59:41,950 --> 00:59:45,560
Ada satu perkataan yang berakhir di sini dalam struktur data.

994
00:59:45,560 --> 00:59:48,190
>> Jadi apa indone adalah benar-benar dipenuhi dengan dan penulis memilih untuk mewakili

995
00:59:48,190 --> 00:59:51,880
ini terminuses dengan segitiga sedikit.

996
00:59:51,880 --> 00:59:56,470
Ini hanya bermakna bahawa fakta segitiga ini di sini, ini nilai boolean benar

997
00:59:56,470 --> 00:59:59,200
bermakna jika anda pergi ke belakang di pokok itu,

998
00:59:59,200 --> 01:00:02,420
yang bermaksud perkataan yang bernama Maxwell merupakan dalam hal ini.

999
01:00:02,420 --> 01:00:04,870
Tetapi perkataan foo, misalnya,

1000
01:00:04,870 --> 01:00:07,970
tidak di pokok itu, kerana jika saya bermula pada nod akar sehingga di sini di atas,

1001
01:00:07,970 --> 01:00:14,030
Tiada penunjuk f, tiada penunjuk o, tiada penunjuk o. Foo bukan nama dalam kamus ini.

1002
01:00:14,030 --> 01:00:22,460
Tetapi sebaliknya, kapan, t-u-r-i-n-g. Sekali lagi, saya tidak menyimpan t atau u atau r atau i atau n atau g.

1003
01:00:22,460 --> 01:00:29,820
Tetapi saya tidak kedai dalam struktur data ini nilai jalan yang sebenar turun di sini di nod ini - di pokok itu

1004
01:00:29,820 --> 01:00:33,030
dengan menetapkan nilai boolean ini is_word benar.

1005
01:00:33,030 --> 01:00:35,740
Jadi indone adalah jenis ini struktur meta sangat menarik,

1006
01:00:35,740 --> 01:00:39,810
di mana anda tidak benar-benar menyimpan perkataan diri untuk jenis ini kamus.

1007
01:00:39,810 --> 01:00:45,100
Untuk menjadi jelas, anda hanya menyimpan ya atau tidak, ada satu perkataan yang berakhir di sini.

1008
01:00:45,100 --> 01:00:46,430
>> Sekarang apa implikasinya?

1009
01:00:46,430 --> 01:00:51,120
Jika anda mempunyai 150,000 perkataan dalam kamus yang anda cuba untuk menyimpan dalam ingatan

1010
01:00:51,120 --> 01:00:53,400
menggunakan sesuatu seperti senarai berkaitan,

1011
01:00:53,400 --> 01:00:56,870
anda akan mempunyai 150,000 nod dalam senarai dikaitkan anda.

1012
01:00:56,870 --> 01:01:00,250
Dan mencari salah satu daripada kata-kata abjad boleh mengambil masa O (n).

1013
01:01:00,250 --> 01:01:04,370
Masa linear. Tetapi dalam kes sini indone satu,

1014
01:01:04,370 --> 01:01:09,210
apa masa berjalan mencari perkataan?

1015
01:01:09,210 --> 01:01:17,390
Ia ternyata keindahan di sini adalah bahawa walaupun anda mempunyai 149.999 kata-kata sudah dalam kamus ini,

1016
01:01:17,390 --> 01:01:20,170
seperti yang dilaksanakan dengan struktur data ini,

1017
01:01:20,170 --> 01:01:25,560
berapa banyak masa ia mengambil masa untuk mencari atau memasukkan seseorang yang lebih kepada yang lain, seperti Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Nah, itu hanya 5, mungkin 6 langkah-langkah untuk watak mengekori.

1019
01:01:30,640 --> 01:01:32,880
Kerana presense nama-nama lain dalam struktur

1020
01:01:32,880 --> 01:01:35,340
tidak mendapat dengan cara memasukkan Alice.

1021
01:01:35,340 --> 01:01:39,640
Selain itu, mencari Alice sekali terdapat 150,000 perkataan dalam kamus ini

1022
01:01:39,640 --> 01:01:41,960
tidak mendapat dalam cara anda mencari Alice pada semua,

1023
01:01:41,960 --> 01:01:46,880
kerana Alice. . . . . di sini, kerana saya mendapati nilai boolean.

1024
01:01:46,880 --> 01:01:50,920
Dan jika tiada boolean benar, maka Alice tidak dalam struktur data ini kata-kata.

1025
01:01:50,920 --> 01:01:56,220
Dalam erti kata lain, masa berjalan mencari perkara dan memasukkan sesuatu ke dalam baru ini

1026
01:01:56,220 --> 01:02:01,920
struktur data indone O - ia tidak n.

1027
01:02:01,920 --> 01:02:05,730
Kerana presense 150,000 orang tidak mempunyai kesan ke atas Alice, ia seolah-olah.

1028
01:02:05,730 --> 01:02:11,560
Jadi mari kita memanggilnya k, di mana k adalah panjang maksimum perkataan dalam bahasa Inggeris

1029
01:02:11,560 --> 01:02:14,050
yang biasanya tidak lebih daripada 20-sesuatu watak.

1030
01:02:14,050 --> 01:02:17,940
Jadi k ialah pemalar. Jadi Holy Grail kita seolah-olah telah menemui sekarang

1031
01:02:17,940 --> 01:02:26,000
adalah bahawa masa indone, berterusan untuk memasukkan, untuk lookup, untuk pemotongan.

1032
01:02:26,000 --> 01:02:29,170
Kerana bilangan perkara sudah dalam struktur,

1033
01:02:29,170 --> 01:02:32,600
yang tidak walaupun fizikal sana. Sekali lagi, mereka hanya jenis diperiksa, ya atau tidak,

1034
01:02:32,600 --> 01:02:35,050
tidak mempunyai kesan ke atas masa masa depannya berjalan.

1035
01:02:35,050 --> 01:02:37,940
>> Tetapi ada mendapat menjadi tangkapan, jika tidak, kita tidak akan membazirkan begitu banyak masa

1036
01:02:37,940 --> 01:02:41,460
pada semua struktur data lain hanya untuk akhirnya sampai ke satu rahsia yang menakjubkan.

1037
01:02:41,460 --> 01:02:46,410
Jadi apa harga kita membayar untuk mencapai kebesaran ini di sini? Angkasa.

1038
01:02:46,410 --> 01:02:49,010
Perkara ini adalah besar-besaran. Dan sebab-sebab yang penulis

1039
01:02:49,010 --> 01:02:52,400
tidak hadir di sini, melihat bahawa semua perkara-perkara yang kelihatan seperti tatasusunan,

1040
01:02:52,400 --> 01:02:55,400
dia tidak menarik seluruh pokok itu, seluruh indone yang,

1041
01:02:55,400 --> 01:02:58,060
kerana mereka hanya tidak relevan kepada cerita.

1042
01:02:58,060 --> 01:03:01,870
Tetapi semua ini nod adalah sangat luas, dan setiap nod dalam pokok itu mengambil

1043
01:03:01,870 --> 01:03:07,780
26 atau sebenarnya, boleh menjadi 27 aksara kerana dalam kes ini, saya telah termasuk ruang untuk apostrofi

1044
01:03:07,780 --> 01:03:09,980
supaya kita boleh mempunyai perkataan apostrophized.

1045
01:03:09,980 --> 01:03:14,450
Dalam kes ini, ini adalah array yang luas. Jadi walaupun mereka tidak picutured,

1046
01:03:14,450 --> 01:03:18,190
ini mengambil sejumlah besar RAM.

1047
01:03:18,190 --> 01:03:20,670
Yang mungkin halus, especilly dalam perkakasan moden,

1048
01:03:20,670 --> 01:03:25,650
tetapi itulah tradeoff. Kita mendapat masa yang kurang dengan menghabiskan lebih banyak ruang.

1049
01:03:25,650 --> 01:03:28,580
Jadi di mana ini semua akan?

1050
01:03:28,580 --> 01:03:32,640
Nah, mari kita lakukan - mari kita lihat di sini.

1051
01:03:32,640 --> 01:03:39,510
Mari kita melakukan lompatan kepada lelaki ini di sini.

1052
01:03:39,510 --> 01:03:43,450
>> Percaya atau tidak, seronok dengan C telah untuk beberapa waktu kini,

1053
01:03:43,450 --> 01:03:48,130
kita mencapai titik pada semester di mana ia adalah masa untuk peralihan kepada perkara-perkara yang lebih moden.

1054
01:03:48,130 --> 01:03:50,950
Perkara di tahap yang lebih tinggi. Dan walaupun untuk beberapa minggu akan datang

1055
01:03:50,950 --> 01:03:54,580
kita masih akan terus untuk melibatkan diri dalam dunia petunjuk dan pengurusan ingatan

1056
01:03:54,580 --> 01:03:57,210
untuk mendapatkan keselesaan yang kita boleh membina,

1057
01:03:57,210 --> 01:04:01,270
permainan akhir akhirnya untuk memperkenalkan, ironinya, tidak bahasa ini.

1058
01:04:01,270 --> 01:04:03,330
Kami akan menghabiskan, seperti 10 minit bercakap tentang HTML.

1059
01:04:03,330 --> 01:04:05,950
Semua HTML adalah bahasa markup, dan apa bahasa markup adalah

1060
01:04:05,950 --> 01:04:10,220
-siri kurungan terbuka dan kurungan tertutup yang mengatakan 'membuat ini berani'

1061
01:04:10,220 --> 01:04:12,000
'Membuat ini italik' membuat berpusatkan ini. '

1062
01:04:12,000 --> 01:04:14,250
Ia bukan semua yang intelektual yang menarik, tetapi ia sangat berguna.

1063
01:04:14,250 --> 01:04:16,650
Dan ia sudah tentu kehadiran hari ini.

1064
01:04:16,650 --> 01:04:19,450
Tetapi apa yang berkuasa tentang dunia HTML, dan pengaturcaraan web lebih amnya,

1065
01:04:19,450 --> 01:04:25,910
membina perkara-perkara yang dinamik, menulis kod dalam bahasa seperti PHP atau Python atau Ruby atau Java atau C #.

1066
01:04:25,910 --> 01:04:30,360
Betul, apa bahasa pilihan anda, dan menjana HTML dinamik.

1067
01:04:30,360 --> 01:04:32,960
Menjana sesuatu yang dipanggil CSS dinamik.

1068
01:04:32,960 --> 01:04:35,810
Lembaran gaya Cascading, yang juga tentang estetika.

1069
01:04:35,810 --> 01:04:41,360
Dan sebagainya walaupun, hari ini, jika saya pergi ke beberapa laman web seperti Google.com yang biasa,

1070
01:04:41,360 --> 01:04:46,100
dan saya pergi untuk melihat, pemaju, pandangan sumber, yang mungkin anda telah dilakukan sebelum,

1071
01:04:46,100 --> 01:04:49,800
tetapi akan untuk melihat sumber, barangan ini mungkin kelihatan agak samar-samar.

1072
01:04:49,800 --> 01:04:55,320
Tetapi ini adalah kod asas yang melaksanakan Google.com.

1073
01:04:55,320 --> 01:04:57,940
Pada akhir hadapan. Dan sebenarnya semua ini adalah kembang barangan estetika.

1074
01:04:57,940 --> 01:05:01,740
Ini adalah CSS di sini. Jika saya menyimpan menatal ke bawah, kita akan mendapat beberapa barangan berkod warna.

1075
01:05:01,740 --> 01:05:06,890
Ini adalah HTML. Kod Google kelihatan seperti keadaan kucar-kacir, tetapi jika saya benar-benar membuka tetingkap yang berbeza,

1076
01:05:06,890 --> 01:05:09,380
kita boleh melihat beberapa struktur ini.

1077
01:05:09,380 --> 01:05:12,640
Jika saya membuka ini, notis di sini, ia adalah sedikit lebih mudah dibaca.

1078
01:05:12,640 --> 01:05:16,850
Kita akan lihat sebelum lama tag ini, [perkataan] tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, kepala, badan, span, skrip, kawasan teks, span, tengah, div.

1080
01:05:23,520 --> 01:05:26,770
Dan ini juga menyusun samar-cari pada pandangan pertama,

1081
01:05:26,770 --> 01:05:30,890
tetapi semua keadaan kucar-kacir ini mengikuti corak tertentu, dan corak berulang,

1082
01:05:30,890 --> 01:05:33,850
supaya apabila kita mendapatkan asas-asas ke bawah, anda akan dapat untuk menulis kod seperti ini

1083
01:05:33,850 --> 01:05:37,550
dan kemudian memanipulasi kod seperti ini menggunakan satu lagi bahasa, yang dipanggil JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Dan JavaScript adalah bahasa yang berjalan di dalam pelayar

1085
01:05:40,440 --> 01:05:44,380
hari ini yang kita gunakan pada Harvard kursus, untuk alat membeli-belah kursus bahawa Google maps menggunakan

1086
01:05:44,380 --> 01:05:48,660
untuk memberi anda sekumpulan keseluruhan dinamisme, Facebook memberikan anda untuk menunjukkan kemaskini status segera,

1087
01:05:48,660 --> 01:05:51,430
Twitter menggunakan ia untuk menunjukkan kepada anda tweet serta-merta.

1088
01:05:51,430 --> 01:05:53,820
Semua ini kita akan mula untuk melibatkan diri masuk

1089
01:05:53,820 --> 01:05:57,190
Tetapi untuk sampai ke sana, kita perlu memahami sesuatu yang sedikit tentang Internet.

1090
01:05:57,190 --> 01:06:01,130
Klip ini di sini adalah hanya satu minit panjang, dan mari kita andaikan untuk sekarang ini adalah, sebenarnya,

1091
01:06:01,130 --> 01:06:08,380
bagaimana Internet berfungsi sebagai memujuknya untuk apa yang kira-kira akan datang. Saya memberi anda "Pahlawan Bersih."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ korus muzik perlahan ♫]

1093
01:06:14,720 --> 01:06:20,450
[Perawi Lelaki] Dia datang dengan mesej.

1094
01:06:20,450 --> 01:06:23,770
Dengan protokol semua sendiri.

1095
01:06:23,770 --> 01:06:37,270
[♫ lebih cepat muzik-muzik elektronik ♫]

1096
01:06:37,270 --> 01:06:41,330
Dia datang ke dunia firewall sejuk, peduli router,

1097
01:06:41,330 --> 01:06:45,690
dan bahaya yang jauh lebih buruk daripada kematian.

1098
01:06:45,690 --> 01:06:55,400
Dia cepat. Dia kuat. Dia TCP / IP, dan dia mendapat alamat anda.

1099
01:06:55,400 --> 01:06:59,250
Pahlawan Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Minggu depan, maka. Internet. Pengaturcaraan web. Ini adalah CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]