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

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Harvard University]

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

4
00:00:08,000 --> 00:00:12,000
>> Ini adalah CS50, dan ini adalah awal dari Minggu 6,

5
00:00:12,000 --> 00:00:16,000
sehingga beberapa alat baru yang sekarang tersedia bagi Anda untuk mengambil keuntungan dari,

6
00:00:16,000 --> 00:00:19,000
yang pertama disebut CS50 Style.

7
00:00:19,000 --> 00:00:22,000
Kemungkinannya adalah jika Anda seperti saya atau salah satu rekan-rekan mengajar,

8
00:00:22,000 --> 00:00:26,000
Anda mungkin pernah melihat sebuah program yang gaya terlihat sedikit sesuatu seperti ini.

9
00:00:26,000 --> 00:00:30,000
Mungkin Anda mulai memotong beberapa sudut larut malam, atau Anda akan berurusan dengan itu nanti,

10
00:00:30,000 --> 00:00:32,000
dan kemudian TF atau CA datang lebih selama jam kerja.

11
00:00:32,000 --> 00:00:34,000
Maka sulit bagi kita untuk membaca.

12
00:00:34,000 --> 00:00:38,000
Nah, kode ini adalah sintaksis benar, dan itu akan mengkompilasi, dan itu benar-benar akan berjalan.

13
00:00:38,000 --> 00:00:40,000
Tapi itu jelas bukan 5 untuk gaya.

14
00:00:40,000 --> 00:00:45,000
>> Tapi sekarang, jika kita pergi ke direktori ini di sini-

15
00:00:45,000 --> 00:00:48,000
dan perhatikan bahwa saya memiliki-conditions2.c

16
00:00:48,000 --> 00:00:55,000
dan saya menjalankan perintah baru, style50, pada conditions2.c file, Enter,

17
00:00:55,000 --> 00:00:57,000
melihat bahwa itu memberitahu saya bahwa telah bergaya.

18
00:00:57,000 --> 00:01:00,000
Gedit menyadari bahwa file tersebut telah diubah pada disk,

19
00:01:00,000 --> 00:01:08,000
dan jika saya klik ulang, semua masalah Anda sekarang otomatis.

20
00:01:08,000 --> 00:01:15,000
[Tepuk tangan]

21
00:01:15,000 --> 00:01:17,000
Itulah salah satu hal yang kita lakukan akhir pekan ini.

22
00:01:17,000 --> 00:01:20,000
Sadarilah bahwa itu tidak sempurna karena ada beberapa kode

23
00:01:20,000 --> 00:01:23,000
bahwa itu hanya tidak akan mampu untuk menyesuaikan dgn mode sempurna,

24
00:01:23,000 --> 00:01:26,000
tapi menyadari hal ini sekarang menjadi alat yang dapat mengambil keuntungan dari

25
00:01:26,000 --> 00:01:33,000
jika hanya untuk merapikan beberapa kurung kurawal lebih errantly ditempatkan dan sejenisnya.

26
00:01:33,000 --> 00:01:36,000
>> Tapi yang lebih menarik sekarang adalah CS50 Periksa.

27
00:01:36,000 --> 00:01:39,000
Dengan CS50 Cek, Anda benar-benar dapat melakukan tes kebenaran yang sama

28
00:01:39,000 --> 00:01:42,000
pada kode Anda sendiri bahwa rekan-rekan mengajar mampu.

29
00:01:42,000 --> 00:01:44,000
Ini adalah sebuah utilitas baris perintah yang datang sekarang dalam alat

30
00:01:44,000 --> 00:01:46,000
segera setelah Anda melakukan update50 sesuai

31
00:01:46,000 --> 00:01:49,000
pset 4 spesifikasi, dan Anda menggunakannya pada dasarnya seperti ini.

32
00:01:49,000 --> 00:01:51,000
Anda menjalankan perintah check50.

33
00:01:51,000 --> 00:01:56,000
Kemudian Anda lulus dalam argumen baris perintah, atau lebih umum dikenal sebagai switch atau bendera.

34
00:01:56,000 --> 00:01:58,000
Umumnya, hal-hal yang memiliki tanda hubung disebut switch

35
00:01:58,000 --> 00:02:02,000
untuk program baris perintah, sehingga-c menentukan

36
00:02:02,000 --> 00:02:04,000
cek yang ingin Anda jalankan.

37
00:02:04,000 --> 00:02:07,000
>> Tes yang ingin Anda jalankan diidentifikasi secara unik dengan string ini,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Dengan kata lain, itu hanya sebuah string sewenang-wenang tapi unik

40
00:02:13,000 --> 00:02:18,000
yang kita gunakan untuk secara unik mengidentifikasi tes ketepatan 4 pset itu.

41
00:02:18,000 --> 00:02:21,000
Dan kemudian Anda menentukan daftar dipisahkan dengan spasi dari file yang ingin Anda upload

42
00:02:21,000 --> 00:02:24,000
untuk CS50 Periksa analisis.

43
00:02:24,000 --> 00:02:29,000
Misalnya, jika saya pergi ke solusi saya di sini untuk resize.c-

44
00:02:29,000 --> 00:02:31,000
biarkan aku membuka jendela terminal besar-

45
00:02:31,000 --> 00:02:42,000
dan saya pergi ke depan dan menjalankan katakanlah check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
dan kemudian saya pergi ke depan dan menentukan nama-nama file,

47
00:02:46,000 --> 00:02:49,000
resize.c, dan kemudian tekan Enter, maka kompres,

48
00:02:49,000 --> 00:02:53,000
itu upload, mengecek, dan saya hanya gagal sejumlah tes.

49
00:02:53,000 --> 00:02:59,000
Yang merah di sebelah kiri atas mengatakan bahwa resize.c dan bmp ada.

50
00:02:59,000 --> 00:03:01,000
Itu tes. Itulah pertanyaan kita.

51
00:03:01,000 --> 00:03:04,000
Dan itu tidak bahagia karena jawabannya adalah palsu.

52
00:03:04,000 --> 00:03:08,000
Teks putih di bawah itu mengatakan diharapkan bmp.h ada, dan itu hanya salahku.

53
00:03:08,000 --> 00:03:11,000
Aku lupa untuk meng-upload, jadi saya perlu untuk meng-upload kedua file,

54
00:03:11,000 --> 00:03:14,000
resize.c dan bmp.h.

55
00:03:14,000 --> 00:03:17,000
Tapi sekarang perhatikan semua tes lainnya dalam kuning karena mereka tidak menjalankan,

56
00:03:17,000 --> 00:03:21,000
dan sehingga wajah tersenyum adalah vertikal karena dia tidak merasa bahagia ataupun sedih,

57
00:03:21,000 --> 00:03:25,000
tapi kita harus memperbaiki masalah itu dalam warna merah sebelum mereka cek lainnya akan berjalan.

58
00:03:25,000 --> 00:03:27,000
>> Biarkan saya memperbaiki hal ini.

59
00:03:27,000 --> 00:03:30,000
Biarkan saya zoom out dan memutarkan ini, kali ini dengan bmp.h juga

60
00:03:30,000 --> 00:03:34,000
pada baris perintah, Enter, dan sekarang jika semuanya berjalan dengan baik,

61
00:03:34,000 --> 00:03:38,000
itu akan memeriksa dan kemudian kembali hasil dari-tahan napas Anda-

62
00:03:38,000 --> 00:03:42,000
semua hijau, yang berarti saya lakukan dengan sangat baik pada pset 4 sejauh ini.

63
00:03:42,000 --> 00:03:44,000
Anda dapat melihat dan menyimpulkan dari teks deskriptif di sini

64
00:03:44,000 --> 00:03:47,000
persis apa yang kita diuji.

65
00:03:47,000 --> 00:03:49,000
Kami diuji terlebih dahulu melakukan file yang ada?

66
00:03:49,000 --> 00:03:51,000
Kami kemudian diuji apakah kompilasi resize.c?

67
00:03:51,000 --> 00:03:58,000
Kemudian kita diuji apakah itu tidak mengubah ukuran 1x1-pixel BMP jika n, faktor resize, adalah 1.

68
00:03:58,000 --> 00:04:01,000
Sekarang, jika Anda tidak tahu apa n adalah, Anda sekali Anda akan menyelam ke pset 4,

69
00:04:01,000 --> 00:04:04,000
tapi itu hanya merupakan kewarasan periksa untuk memastikan bahwa Anda tidak mengubah ukuran

70
00:04:04,000 --> 00:04:08,000
gambar sama sekali jika faktor resize 1.

71
00:04:08,000 --> 00:04:14,000
Jika, sebaliknya, itu mengubah ukuran piksel 1x1 ke 1x1 pixel BMP untuk 2x2 dengan benar

72
00:04:14,000 --> 00:04:19,000
jika n adalah 2, maka sama, saya membentuk sesuai.

73
00:04:19,000 --> 00:04:22,000
>> Singkatnya, hal ini dimaksudkan untuk, satu, mengambil melintasi jari

74
00:04:22,000 --> 00:04:25,000
dari persamaan tepat sebelum Anda mengirimkan pset Anda.

75
00:04:25,000 --> 00:04:28,000
Anda akan tahu persis apa TF Anda akan segera tahu

76
00:04:28,000 --> 00:04:30,000
ketika Anda pergi tentang mengirimkan beberapa set masalah,

77
00:04:30,000 --> 00:04:34,000
dan juga motivasi pedagogis benar-benar menempatkan

78
00:04:34,000 --> 00:04:37,000
kesempatan di depan Anda sehingga ketika Anda tahu a priori

79
00:04:37,000 --> 00:04:39,000
bahwa ada bug dalam kode Anda dan tes yang tidak lulus,

80
00:04:39,000 --> 00:04:43,000
Anda dapat dimasukkan ke dalam waktu yang lebih efektif di depan untuk memecahkan masalah-masalah

81
00:04:43,000 --> 00:04:45,000
bukannya kehilangan poin, mendapatkan umpan balik dari TF Anda,

82
00:04:45,000 --> 00:04:48,000
dan kemudian pergi, "Ahh," seperti saya harus berpikir bahwa keluar.

83
00:04:48,000 --> 00:04:50,000
Sekarang setidaknya ada alat untuk membantu Anda menemukan bahwa.

84
00:04:50,000 --> 00:04:52,000
Ini tidak akan menunjukkan di mana bug tersebut, tetapi akan memberitahu Anda

85
00:04:52,000 --> 00:04:54,000
apa gejala itu.

86
00:04:54,000 --> 00:04:57,000
>> Sekarang menyadari tes tidak selalu lengkap.

87
00:04:57,000 --> 00:04:59,000
Hanya karena Anda mendapatkan layar penuh hijau wajah smiley

88
00:04:59,000 --> 00:05:02,000
tidak berarti kode Anda sempurna, tetapi tidak berarti

89
00:05:02,000 --> 00:05:06,000
yang telah lulus tes tertentu yang ditentukan oleh spec.

90
00:05:06,000 --> 00:05:08,000
Kadang-kadang kita tidak akan merilis cek.

91
00:05:08,000 --> 00:05:10,000
Misalnya, cerita detektif, salah satu aspek pset 4,

92
00:05:10,000 --> 00:05:15,000
adalah agak mengecewakan jika kita memberikan

93
00:05:15,000 --> 00:05:18,000
jawaban untuk apa itu, dan ada sejumlah cara untuk mengungkapkan

94
00:05:18,000 --> 00:05:21,000
siapa orang itu dalam kebisingan merah.

95
00:05:21,000 --> 00:05:24,000
Spec akan selalu menentukan di masa depan untuk pset 5 seterusnya

96
00:05:24,000 --> 00:05:26,000
apa yang ada untuk memeriksa Anda.

97
00:05:26,000 --> 00:05:28,000
Anda akan melihat ada URL putih di bagian bawah.

98
00:05:28,000 --> 00:05:30,000
Untuk saat ini, ini hanya output diagnostik.

99
00:05:30,000 --> 00:05:33,000
Jika Anda mengunjungi URL tersebut, Anda akan mendapatkan sejumlah besar gila, pesan samar

100
00:05:33,000 --> 00:05:36,000
bahwa Anda dipersilakan untuk melihat melalui, tapi itu sebagian besar untuk staf

101
00:05:36,000 --> 00:05:41,000
sehingga kita dapat mendiagnosa dan debug bug di check50 sendiri.

102
00:05:41,000 --> 00:05:46,000
>> Tanpa basa-basi, mari kita beralih ke tempat kami tinggalkan.

103
00:05:46,000 --> 00:05:48,000
CS50 perpustakaan kami mengambil begitu saja selama beberapa minggu,

104
00:05:48,000 --> 00:05:52,000
tapi kemudian minggu lalu, kami mulai mengupas kembali salah satu lapisan itu.

105
00:05:52,000 --> 00:05:55,000
Kami mulai menyisihkan string dalam mendukung apa bukan?

106
00:05:55,000 --> 00:05:57,000
[Siswa] Char.

107
00:05:57,000 --> 00:05:59,000
Char *, yang telah menjadi char * sepanjang waktu ini,

108
00:05:59,000 --> 00:06:03,000
tapi sekarang kita tidak harus berpura-pura bahwa itu adalah tipe data string yang sebenarnya.

109
00:06:03,000 --> 00:06:06,000
Sebaliknya, itu menjadi sinonim macam untuk char *,

110
00:06:06,000 --> 00:06:09,000
dan string adalah rangkaian karakter,

111
00:06:09,000 --> 00:06:14,000
jadi mengapa tidak masuk akal untuk mewakili string sebagai char * s?

112
00:06:14,000 --> 00:06:20,000
Apa char * mewakili dalam konteks ini konsep string?

113
00:06:20,000 --> 00:06:23,000
Ya >> [Mahasiswa]. Karakter pertama.

114
00:06:23,000 --> 00:06:25,000
Baik, karakter pertama, tetapi tidak cukup karakter pertama.

115
00:06:25,000 --> 00:06:27,000
Ini-[Siswa] Alamat.

116
00:06:27,000 --> 00:06:29,000
Baik, alamat dari karakter pertama.

117
00:06:29,000 --> 00:06:33,000
Semua yang diperlukan untuk mewakili string dalam memori komputer

118
00:06:33,000 --> 00:06:36,000
hanya alamat unik dari byte yang pertama.

119
00:06:36,000 --> 00:06:38,000
Anda bahkan tidak harus tahu berapa lama itu

120
00:06:38,000 --> 00:06:42,000
karena bagaimana Anda bisa mencari tahu secara dinamis?

121
00:06:42,000 --> 00:06:44,000
[Mahasiswa] panjang String.

122
00:06:44,000 --> 00:06:48,000
Anda dapat memanggil panjang string, baik, tapi bagaimana cara kerja panjang string?

123
00:06:48,000 --> 00:06:50,000
Apa yang dilakukannya? Ya.

124
00:06:50,000 --> 00:06:52,000
[Mahasiswa] Terus sampai Anda mendapatkan karakter null.

125
00:06:52,000 --> 00:06:54,000
Ya, tepatnya, itu hanya iterates dengan untuk loop, sementara loop,

126
00:06:54,000 --> 00:06:57,000
apapun dari * sampai akhir, dan akhirnya diwakili

127
00:06:57,000 --> 00:07:01,000
oleh \ 0, karakter yang disebut nul, nul,

128
00:07:01,000 --> 00:07:05,000
tidak harus bingung dengan nol, yang merupakan pointer,

129
00:07:05,000 --> 00:07:07,000
yang akan muncul dalam percakapan lagi hari ini.

130
00:07:07,000 --> 00:07:11,000
>> Kami dikupas kembali lapisan GetInt, dan kemudian kita mengambil melihat GetString,

131
00:07:11,000 --> 00:07:14,000
dan mengingat bahwa kedua fungsi tersebut, atau benar-benar,

132
00:07:14,000 --> 00:07:18,000
GetString, adalah menggunakan fungsi tertentu

133
00:07:18,000 --> 00:07:21,000
untuk benar-benar mengurai, yaitu, membaca atau menganalisis, masukan pengguna.

134
00:07:21,000 --> 00:07:25,000
Dan apa itu fungsi baru?

135
00:07:25,000 --> 00:07:27,000
Scanf atau sscanf. Ini benar-benar datang dalam beberapa rasa yang berbeda.

136
00:07:27,000 --> 00:07:31,000
Ada scanf, ada sscanf, ada fscanf.

137
00:07:31,000 --> 00:07:35,000
Untuk saat ini, meskipun, mari kita fokus pada yang paling mudah digambarkan,

138
00:07:35,000 --> 00:07:38,000
dan biarkan aku pergi ke depan dan terbuka di alat

139
00:07:38,000 --> 00:07:41,000
file seperti ini, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Ini adalah program super sederhana,

141
00:07:43,000 --> 00:07:46,000
tapi yang melakukan sesuatu yang kita belum pernah melakukan

142
00:07:46,000 --> 00:07:48,000
tanpa bantuan dari perpustakaan CS50.

143
00:07:48,000 --> 00:07:51,000
Ini mendapat int dari pengguna. Bagaimana cara kerjanya?

144
00:07:51,000 --> 00:07:53,000
Nah, di baris 16 sana,

145
00:07:53,000 --> 00:07:56,000
perhatikan bahwa kita mendeklarasikan x disebut int, dan pada titik ini dalam cerita,

146
00:07:56,000 --> 00:07:58,000
berapakah nilai dari x?

147
00:07:58,000 --> 00:08:00,000
[Respon siswa tidak terdengar]

148
00:08:00,000 --> 00:08:02,000
[David M.] Benar, siapa tahu, beberapa nilai sampah yang berpotensi, sehingga di 17, kami hanya memberitahu pengguna

149
00:08:02,000 --> 00:08:06,000
memberi saya nomor, silahkan, dan langkah 18 adalah di mana ia mulai menarik.

150
00:08:06,000 --> 00:08:11,000
Scanf tampaknya meminjam ide dari printf karena menggunakan kode-kode format yang dalam tanda kutip.

151
00:08:11,000 --> 00:08:13,000
D% tentu saja angka desimal.

152
00:08:13,000 --> 00:08:21,000
Tapi mengapa aku lewat di & x bukan hanya x?

153
00:08:21,000 --> 00:08:24,000
Yang pertama adalah benar. Ya.

154
00:08:24,000 --> 00:08:26,000
[Respon siswa tidak terdengar]

155
00:08:26,000 --> 00:08:31,000
Tepat, jika tujuan dari program ini, seperti GetInt fungsi itu sendiri,

156
00:08:31,000 --> 00:08:34,000
adalah untuk mendapatkan int dari pengguna saya bisa lulus fungsi

157
00:08:34,000 --> 00:08:38,000
semua variabel saya inginkan, tetapi jika aku tidak melewati mereka dengan referensi

158
00:08:38,000 --> 00:08:41,000
atau berdasarkan alamat atau pointer, semua sinonim untuk keperluan hari ini,

159
00:08:41,000 --> 00:08:46,000
maka fungsi yang tidak memiliki kemampuan untuk mengubah isi dari variabel itu.

160
00:08:46,000 --> 00:08:49,000
Hal ini akan lulus dalam salinan seperti versi kereta swap

161
00:08:49,000 --> 00:08:51,000
bahwa kita telah berbicara tentang beberapa kali sekarang.

162
00:08:51,000 --> 00:08:54,000
>> Tapi sebaliknya, dengan melakukan & x, aku benar-benar lewat di apa?

163
00:08:54,000 --> 00:08:57,000
[Mahasiswa] Alamat. >> Alamat dari x.

164
00:08:57,000 --> 00:09:01,000
Ini seperti menggambar peta untuk fungsi yang disebut scanf dan katakan di sini,

165
00:09:01,000 --> 00:09:04,000
ini adalah petunjuk untuk sepotong memori di komputer

166
00:09:04,000 --> 00:09:07,000
bahwa Anda dapat pergi menyimpan bilangan bulat beberapa masuk

167
00:09:07,000 --> 00:09:10,000
Agar sscanf sekarang melakukan itu

168
00:09:10,000 --> 00:09:13,000
apa operator, apa bagian dari sintaks itu akan harus menggunakan

169
00:09:13,000 --> 00:09:19,000
meskipun kita tidak bisa melihatnya karena orang lain menulis fungsi ini?

170
00:09:19,000 --> 00:09:21,000
Dengan kata lain - apa itu?

171
00:09:21,000 --> 00:09:23,000
[Siswa] X dibaca.

172
00:09:23,000 --> 00:09:27,000
Ada akan menjadi beberapa bacaan, tetapi hanya berkaitan dengan x di sini.

173
00:09:27,000 --> 00:09:30,000
Jika scanf sedang melewati alamat dari x,

174
00:09:30,000 --> 00:09:35,000
sintaksis, apa operator pasti akan ada di suatu tempat

175
00:09:35,000 --> 00:09:38,000
dalam pelaksanaan scanf itu sehingga scanf

176
00:09:38,000 --> 00:09:42,000
benar-benar dapat menulis nomor 2 ke alamat tersebut?

177
00:09:42,000 --> 00:09:44,000
Ya, jadi file *.

178
00:09:44,000 --> 00:09:47,000
Ingat bahwa * adalah dereference operator kami, yang pada dasarnya berarti pergi ke sana.

179
00:09:47,000 --> 00:09:50,000
>> Setelah Anda telah menyerahkan alamat, seperti yang terjadi di sini,

180
00:09:50,000 --> 00:09:53,000
scanf mungkin-jika kita benar-benar melihat sekeliling sumbernya kode-

181
00:09:53,000 --> 00:09:59,000
melakukan * x atau setara untuk benar-benar pergi ke alamat tersebut dan menempatkan beberapa nilai di sana.

182
00:09:59,000 --> 00:10:02,000
Sekarang, seperti untuk bagaimana scanf mendapat masukan dari keyboard,

183
00:10:02,000 --> 00:10:04,000
kita akan melambaikan tangan kami keluar untuk hari ini.

184
00:10:04,000 --> 00:10:07,000
Hanya berasumsi bahwa sistem operasi memungkinkan untuk berbicara sscanf

185
00:10:07,000 --> 00:10:11,000
ke keyboard pengguna, tetapi pada titik ini sekarang di baris 19,

186
00:10:11,000 --> 00:10:14,000
ketika kita hanya mencetak x, tampaknya menjadi kasus

187
00:10:14,000 --> 00:10:17,000
bahwa scanf telah menempatkan int di x.

188
00:10:17,000 --> 00:10:19,000
Itulah bagaimana scanf bekerja, dan ingat minggu lalu

189
00:10:19,000 --> 00:10:25,000
itulah bagaimana GetString dan GetInt dan keluarga lainnya dari fungsi

190
00:10:25,000 --> 00:10:28,000
akhirnya bekerja, meskipun dengan sedikit varian seperti sscanf,

191
00:10:28,000 --> 00:10:31,000
yang berarti memindai string bukan keyboard.

192
00:10:31,000 --> 00:10:33,000
Tapi mari kita lihat pada varians sedikit ini.

193
00:10:33,000 --> 00:10:37,000
Pada scanf2, saya benar-benar kacau.

194
00:10:37,000 --> 00:10:42,000
Apa yang salah-dan saya akan menyembunyikan komentar yang menjelaskan sebanyak-

195
00:10:42,000 --> 00:10:47,000
apa yang salah dengan program ini, versi 2?

196
00:10:47,000 --> 00:10:55,000
Jadilah seperti teknis mungkin kali ini.

197
00:10:55,000 --> 00:10:57,000
Ini terlihat cukup baik.

198
00:10:57,000 --> 00:11:03,000
Ini baik indentasi, tapi-

199
00:11:03,000 --> 00:11:07,000
Oke, mari kita bagaimana memangkas itu ke pertanyaan pendek?

200
00:11:07,000 --> 00:11:17,000
Baris 16. Apa baris 16 dilakukan dalam bahasa Inggris yang tepat namun teknis?

201
00:11:17,000 --> 00:11:20,000
Mendapatkan sedikit canggung. Ya, Michael.

202
00:11:20,000 --> 00:11:25,000
[Mahasiswa] Ini menunjuk ke huruf pertama dari string.

203
00:11:25,000 --> 00:11:27,000
>> Oke, dekat. Biarkan saya tweak yang sedikit.

204
00:11:27,000 --> 00:11:33,000
Menunjuk ke huruf pertama dari string, Anda menyatakan buffer disebut variabel

205
00:11:33,000 --> 00:11:36,000
yang akan menunjuk ke alamat pertama dari string,

206
00:11:36,000 --> 00:11:39,000
atau lebih tepatnya, yang akan mengarahkan lebih spesifik ke char.

207
00:11:39,000 --> 00:11:42,000
Perhatikan itu tidak benar-benar menunjuk di mana saja karena tidak ada operator penugasan.

208
00:11:42,000 --> 00:11:46,000
Tidak ada tanda sama, sehingga semua yang kita lakukan adalah mengalokasikan buffer disebut variabel.

209
00:11:46,000 --> 00:11:49,000
Hal ini terjadi menjadi 32 bit karena pointer,

210
00:11:49,000 --> 00:11:52,000
dan isi buffer mungkin akhirnya

211
00:11:52,000 --> 00:11:57,000
akan berisi alamat char, tapi untuk saat ini, apa penyangga mengandung?

212
00:11:57,000 --> 00:11:59,000
Hanya beberapa palsu, siapa tahu, beberapa nilai sampah,

213
00:11:59,000 --> 00:12:03,000
karena kita tidak secara eksplisit diinisialisasi itu, jadi kita tidak boleh berasumsi apa-apa.

214
00:12:03,000 --> 00:12:06,000
Oke, jadi sekarang baris 17 adalah baris-apa 17 lakukan?

215
00:12:06,000 --> 00:12:08,000
Mungkin itu akan menghangatkan ini.

216
00:12:08,000 --> 00:12:10,000
Ini mencetak string, kan?

217
00:12:10,000 --> 00:12:12,000
Mencetak String silahkan.

218
00:12:12,000 --> 00:12:15,000
>> Baris 18 adalah jenis akrab sekarang kita hanya melihat varians ini

219
00:12:15,000 --> 00:12:18,000
tapi dengan kode format yang berbeda, sehingga sejalan 18,

220
00:12:18,000 --> 00:12:23,000
kita mengatakan scanf sini adalah alamat dari sepotong memori.

221
00:12:23,000 --> 00:12:27,000
Saya ingin Anda untuk cincin dalam sebuah string, seperti yang tersirat oleh% s,

222
00:12:27,000 --> 00:12:32,000
tapi masalahnya adalah bahwa kita tidak melakukan beberapa hal di sini.

223
00:12:32,000 --> 00:12:35,000
Apa salah satu masalah?

224
00:12:35,000 --> 00:12:38,000
[Mahasiswa] Ini mencoba untuk dereference pointer null.

225
00:12:38,000 --> 00:12:41,000
Baik, nol atau hanya jika diketahui pointer.

226
00:12:41,000 --> 00:12:45,000
Kau menyerahkan scanf alamat, tapi Anda hanya mengatakan beberapa saat yang lalu

227
00:12:45,000 --> 00:12:49,000
bahwa alamat itu adalah beberapa nilai sampah karena kita tidak benar-benar menetapkan apa-apa,

228
00:12:49,000 --> 00:12:53,000
dan begitu kau mengatakan scanf efektif pergi menempatkan string di sini,

229
00:12:53,000 --> 00:12:56,000
tapi kita tidak tahu di mana di sini namun,

230
00:12:56,000 --> 00:12:59,000
jadi kita belum benar-benar mengalokasikan memori untuk buffer.

231
00:12:59,000 --> 00:13:03,000
Selain itu, apa yang Anda juga bahkan tidak memberitahu scanf?

232
00:13:03,000 --> 00:13:06,000
Misalkan ini adalah sepotong memori, dan itu bukan nilai sampah,

233
00:13:06,000 --> 00:13:09,000
tapi kau masih belum mengatakan scanf sesuatu yang penting.

234
00:13:09,000 --> 00:13:12,000
[Mahasiswa] Dimana sebenarnya, ampersand.

235
00:13:12,000 --> 00:13:15,000
Ampersand, sehingga dalam kasus ini, tidak apa-apa.

236
00:13:15,000 --> 00:13:18,000
Karena buffer sudah dinyatakan sebagai pointer

237
00:13:18,000 --> 00:13:22,000
dengan potongan * sintaksis, kita tidak perlu menggunakan ampersand

238
00:13:22,000 --> 00:13:25,000
karena itu sudah alamat, tapi saya pikir saya dengar di sini.

239
00:13:25,000 --> 00:13:27,000
[Mahasiswa] Seberapa besar itu?

240
00:13:27,000 --> 00:13:29,000
Baik, kita tidak mengatakan scanf seberapa besar penyangga ini,

241
00:13:29,000 --> 00:13:32,000
yang berarti bahkan jika buffer adalah pointer,

242
00:13:32,000 --> 00:13:35,000
kami katakan scanf, menempatkan string di sini,

243
00:13:35,000 --> 00:13:38,000
tapi di sini bisa menjadi 2 byte, bisa 10 byte, bisa jadi satu megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf memiliki tidak tahu, dan karena ini adalah sepotong memori

245
00:13:41,000 --> 00:13:43,000
mungkin, itu bukan string belum.

246
00:13:43,000 --> 00:13:48,000
Ini hanya string sekali Anda menulis karakter dan \ 0 dengan sepotong memori.

247
00:13:48,000 --> 00:13:51,000
Sekarang hanya beberapa potongan memori.

248
00:13:51,000 --> 00:13:55,000
Scanf tidak akan tahu kapan harus berhenti menulis ke alamat tersebut.

249
00:13:55,000 --> 00:13:59,000
>> Jika Anda ingat beberapa contoh di masa lalu di mana saya secara acak mengetik pada keyboard

250
00:13:59,000 --> 00:14:03,000
mencoba untuk buffer overflow, dan kami berbicara pada hari Jumat tentang hal itu.

251
00:14:03,000 --> 00:14:07,000
Jika musuh entah bagaimana menyuntikkan ke dalam program Anda sebuah kata yang jauh lebih besar

252
00:14:07,000 --> 00:14:10,000
atau kalimat atau frase maka Anda mengharapkan Anda dapat dikuasai

253
00:14:10,000 --> 00:14:13,000
sepotong memori, yang dapat memiliki konsekuensi yang buruk,

254
00:14:13,000 --> 00:14:15,000
seperti mengambil alih seluruh program itu sendiri.

255
00:14:15,000 --> 00:14:17,000
Kita harus memperbaiki ini, entah bagaimana.

256
00:14:17,000 --> 00:14:20,000
Biarkan saya zoom out dan masuk ke versi 3 dari program ini.

257
00:14:20,000 --> 00:14:22,000
Itu sedikit lebih baik.

258
00:14:22,000 --> 00:14:24,000
Dalam versi ini, melihat perbedaan.

259
00:14:24,000 --> 00:14:27,000
Sejalan 16, aku lagi menyatakan buffer disebut variabel,

260
00:14:27,000 --> 00:14:29,000
tapi apa sekarang?

261
00:14:29,000 --> 00:14:33,000
Ini sebuah array dari 16 karakter.

262
00:14:33,000 --> 00:14:36,000
Ini bagus karena ini berarti saya sekarang dapat memberitahu scanf

263
00:14:36,000 --> 00:14:39,000
di sini adalah potongan yang sebenarnya memori.

264
00:14:39,000 --> 00:14:42,000
Anda hampir bisa memikirkan array sebagai pointer sekarang,

265
00:14:42,000 --> 00:14:44,000
meskipun mereka tidak benar-benar setara.

266
00:14:44,000 --> 00:14:47,000
Mereka akan berperilaku berbeda dalam konteks yang berbeda.

267
00:14:47,000 --> 00:14:50,000
Tapi pasti terjadi bahwa buffer referensi

268
00:14:50,000 --> 00:14:53,000
16 bersebelahan chars karena itulah array adalah

269
00:14:53,000 --> 00:14:55,000
dan telah berlangsung selama beberapa minggu sekarang.

270
00:14:55,000 --> 00:14:59,000
>> Di sini, saya mengatakan scanf inilah sepotong memori.

271
00:14:59,000 --> 00:15:01,000
Kali ini, itu sebenarnya sepotong memori,

272
00:15:01,000 --> 00:15:07,000
tapi mengapa program ini masih dimanfaatkan?

273
00:15:07,000 --> 00:15:11,000
Apa yang salah masih?

274
00:15:11,000 --> 00:15:14,000
Aku sudah mengatakan memberi saya 16 byte tapi-

275
00:15:14,000 --> 00:15:16,000
[Siswa] Bagaimana jika mereka ketik di lebih dari 16?

276
00:15:16,000 --> 00:15:20,000
Tepat, bagaimana jika pengguna jenis dalam 17 karakter atau karakter 1.700?

277
00:15:20,000 --> 00:15:23,000
Bahkan, mari kita lihat apakah kita tidak bisa tersandung kesalahan ini sekarang.

278
00:15:23,000 --> 00:15:25,000
Lebih baik tetapi tidak sempurna.

279
00:15:25,000 --> 00:15:28,000
Biarkan aku pergi ke depan dan menjalankan make scanf3 untuk mengkompilasi program ini.

280
00:15:28,000 --> 00:15:34,000
Biarkan saya menjalankan scanf3, silahkan String: halo, dan kami tampaknya baik-baik saja.

281
00:15:34,000 --> 00:15:37,000
Biarkan saya mencoba yang sedikit lebih panjang, hello there.

282
00:15:37,000 --> 00:15:42,000
Oke, mari kita lakukan halo ada bagaimana kabarmu hari ini, Enter.

283
00:15:42,000 --> 00:15:54,000
Mendapatkan jenis beruntung di sini, katakanlah halo ada kabar.

284
00:15:54,000 --> 00:15:56,000
Sialan.

285
00:15:56,000 --> 00:16:03,000
Oke, jadi kita beruntung. Mari kita lihat apakah kita tidak bisa memperbaiki ini.

286
00:16:03,000 --> 00:16:06,000
Tidak, itu tidak akan membiarkan saya salin.

287
00:16:06,000 --> 00:16:09,000
Mari kita coba ini lagi.

288
00:16:09,000 --> 00:16:12,000
Baiklah, stand by.

289
00:16:12,000 --> 00:16:20,000
Kita akan melihat berapa lama aku bisa berpura-pura untuk fokus sementara masih melakukan hal ini.

290
00:16:20,000 --> 00:16:23,000
Sialan. Itu agak tepat, sebenarnya.

291
00:16:23,000 --> 00:16:26,000
Di sana kami pergi.

292
00:16:26,000 --> 00:16:30,000
Titik yang dibuat.

293
00:16:30,000 --> 00:16:34,000
>> Hal ini, memalukan meskipun juga, itu juga merupakan salah satu sumber kebingungan besar

294
00:16:34,000 --> 00:16:38,000
ketika menulis program yang memiliki bug karena mereka menampakkan diri

295
00:16:38,000 --> 00:16:40,000
hanya sekali-sekali kadang-kadang.

296
00:16:40,000 --> 00:16:43,000
Kenyataannya adalah bahwa bahkan jika kode Anda benar-benar rusak,

297
00:16:43,000 --> 00:16:46,000
itu hanya mungkin benar-benar rusak sesekali

298
00:16:46,000 --> 00:16:49,000
karena kadang-kadang, pada dasarnya apa yang terjadi adalah mengalokasikan sistem operasi

299
00:16:49,000 --> 00:16:52,000
memori yang lebih sedikit dari yang Anda benar-benar perlu untuk alasan apapun,

300
00:16:52,000 --> 00:16:57,000
sehingga tidak ada orang lain yang menggunakan memori tepat setelah potongan Anda dari 16 karakter,

301
00:16:57,000 --> 00:17:01,000
jadi jika Anda pergi ke 17, 18, 19, apa pun, itu bukan masalah besar.

302
00:17:01,000 --> 00:17:04,000
Sekarang, komputer, bahkan jika tidak crash pada saat itu,

303
00:17:04,000 --> 00:17:09,000
akhirnya bisa menggunakan nomor byte 17 atau 18 atau 19 untuk sesuatu yang lain,

304
00:17:09,000 --> 00:17:14,000
di mana titik data Anda bahwa Anda diletakkan di sana, meskipun terlalu panjang,

305
00:17:14,000 --> 00:17:18,000
akan mendapatkan ditimpa berpotensi oleh beberapa fungsi lainnya.

306
00:17:18,000 --> 00:17:21,000
Ini belum tentu akan tetap utuh,

307
00:17:21,000 --> 00:17:23,000
tapi tidak akan selalu menyebabkan kesalahan seg.

308
00:17:23,000 --> 00:17:26,000
Tapi dalam kasus ini, saya akhirnya disediakan karakter yang cukup

309
00:17:26,000 --> 00:17:29,000
bahwa saya pada dasarnya melebihi segmen memori saya, dan bam,

310
00:17:29,000 --> 00:17:33,000
sistem operasi mengatakan, "Maaf, itu bukan karena kesalahan, segmentasi yang baik."

311
00:17:33,000 --> 00:17:38,000
>> Dan mari kita lihat sekarang jika apa yang tersisa di sini di saya direktori-

312
00:17:38,000 --> 00:17:40,000
melihat bahwa saya memiliki file ini di sini, inti.

313
00:17:40,000 --> 00:17:42,000
Perhatikan bahwa ini lagi disebut core dump.

314
00:17:42,000 --> 00:17:46,000
Ini pada dasarnya adalah sebuah file yang berisi isi dari memori program Anda

315
00:17:46,000 --> 00:17:48,000
pada titik di mana ia jatuh,

316
00:17:48,000 --> 00:17:51,000
dan hanya untuk mencoba contoh kecil di sini biarkan aku pergi di sini

317
00:17:51,000 --> 00:17:57,000
dan menjalankan gdb pada scanf3 dan kemudian menentukan argumen ketiga yang disebut inti,

318
00:17:57,000 --> 00:18:01,000
dan perhatikan di sini bahwa jika saya daftar kode,

319
00:18:01,000 --> 00:18:06,000
kita akan dapat seperti biasa dengan gdb untuk mulai berjalan melalui program ini,

320
00:18:06,000 --> 00:18:10,000
dan saya dapat menjalankannya dan segera setelah aku memukul-seperti dengan perintah langkah dalam gdb-

321
00:18:10,000 --> 00:18:13,000
segera setelah aku memukul garis berpotensi kereta setelah mengetik dalam serangkaian besar,

322
00:18:13,000 --> 00:18:16,000
Aku akan dapat benar-benar mengidentifikasi sini.

323
00:18:16,000 --> 00:18:19,000
Lebih lanjut tentang ini, meskipun, di bagian dalam hal core dumps

324
00:18:19,000 --> 00:18:22,000
dan sejenisnya sehingga Anda dapat benar-benar melihat-dalam core dump

325
00:18:22,000 --> 00:18:27,000
dan melihat apa program baris gagal Anda.

326
00:18:27,000 --> 00:18:32,000
Setiap pertanyaan kemudian pada pointer dan alamat?

327
00:18:32,000 --> 00:18:36,000
Karena hari ini, kita akan mulai mengambil begitu saja bahwa hal-hal ini ada

328
00:18:36,000 --> 00:18:40,000
dan kita tahu persis apa yang mereka.

329
00:18:40,000 --> 00:18:42,000
Ya.

330
00:18:42,000 --> 00:18:46,000
>> [Mahasiswa] Kenapa Anda tidak harus meletakkan ampersand sebelah bagian-

331
00:18:46,000 --> 00:18:48,000
Pertanyaan bagus.

332
00:18:48,000 --> 00:18:51,000
Kenapa saya tidak harus meletakkan ampersand sebelah array karakter seperti yang saya lakukan sebelumnya

333
00:18:51,000 --> 00:18:53,000
dengan sebagian besar contoh kita?

334
00:18:53,000 --> 00:18:55,000
Jawaban singkatnya adalah array yang sedikit istimewa.

335
00:18:55,000 --> 00:18:59,000
Anda hampir dapat berpikir buffer sebagai benar-benar menjadi alamat,

336
00:18:59,000 --> 00:19:03,000
dan kebetulan menjadi kasus bahwa notasi persegi braket

337
00:19:03,000 --> 00:19:06,000
adalah kenyamanan sehingga kita bisa masuk ke braket 0, 1 braket,

338
00:19:06,000 --> 00:19:10,000
braket 2, tanpa harus menggunakan notasi *.

339
00:19:10,000 --> 00:19:13,000
Itu sedikit kebohongan putih karena array dan pointer

340
00:19:13,000 --> 00:19:17,000
adalah, pada kenyataannya, sedikit berbeda, tetapi mereka bisa sering tapi tidak selalu digunakan secara bergantian.

341
00:19:17,000 --> 00:19:21,000
Singkatnya, ketika sebuah fungsi mengharapkan pointer ke sepotong memori,

342
00:19:21,000 --> 00:19:24,000
Anda dapat lulus alamat yang dikembalikan oleh malloc,

343
00:19:24,000 --> 00:19:29,000
dan kita akan melihat malloc lagi sebelum panjang, atau Anda bisa lulus nama array.

344
00:19:29,000 --> 00:19:32,000
Anda tidak perlu melakukan ampersand dengan array karena mereka sudah

345
00:19:32,000 --> 00:19:34,000
dasarnya seperti alamat.

346
00:19:34,000 --> 00:19:36,000
Itulah satu-satunya pengecualian.

347
00:19:36,000 --> 00:19:39,000
Tanda kurung siku membuat mereka istimewa.

348
00:19:39,000 --> 00:19:41,000
>> Bisakah Anda menempatkan sebuah ampersand sebelah buffer?

349
00:19:41,000 --> 00:19:43,000
Tidak dalam kasus ini.

350
00:19:43,000 --> 00:19:46,000
Itu tidak akan bekerja karena, sekali lagi, ini kasus sudut

351
00:19:46,000 --> 00:19:49,000
di mana array tidak cukup sebenarnya alamat.

352
00:19:49,000 --> 00:19:54,000
Tapi kita mungkin akan kembali ke sebelum panjang dengan contoh-contoh lainnya.

353
00:19:54,000 --> 00:19:56,000
Mari kita coba untuk memecahkan masalah di sini.

354
00:19:56,000 --> 00:20:00,000
Kami memiliki struktur data yang kita telah menggunakan untuk beberapa waktu yang dikenal sebagai array.

355
00:20:00,000 --> 00:20:02,000
Kasus di titik, itulah yang kita baru saja.

356
00:20:02,000 --> 00:20:04,000
Tapi array memiliki beberapa keuntungan dan kerugian.

357
00:20:04,000 --> 00:20:06,000
Array adalah mengapa bagus?

358
00:20:06,000 --> 00:20:11,000
Apa satu hal yang Anda sukai-sejauh yang Anda suka array-array tentang?

359
00:20:11,000 --> 00:20:13,000
Apa nyaman tentang mereka? Apa yang menarik?

360
00:20:13,000 --> 00:20:18,000
Mengapa kita memperkenalkan mereka di tempat pertama?

361
00:20:18,000 --> 00:20:20,000
Ya.

362
00:20:20,000 --> 00:20:27,000
[Mahasiswa] Mereka dapat menyimpan banyak data, dan Anda tidak harus menggunakan seluruh hal.

363
00:20:27,000 --> 00:20:29,000
Anda dapat menggunakan bagian.

364
00:20:29,000 --> 00:20:32,000
Baik, dengan array Anda dapat menyimpan banyak data,

365
00:20:32,000 --> 00:20:35,000
dan Anda tidak perlu harus menggunakan semua itu, sehingga Anda dapat overallocate,

366
00:20:35,000 --> 00:20:39,000
yang mungkin nyaman jika Anda tidak tahu sebelumnya berapa banyak dari sesuatu untuk diharapkan.

367
00:20:39,000 --> 00:20:41,000
>> GetString adalah contoh yang sempurna.

368
00:20:41,000 --> 00:20:44,000
GetString, ditulis oleh kami, tidak tahu berapa banyak karakter yang diharapkan,

369
00:20:44,000 --> 00:20:48,000
sehingga fakta bahwa kita dapat mengalokasikan potongan memori yang berdekatan yang baik.

370
00:20:48,000 --> 00:20:51,000
Array juga memecahkan masalah kami melihat beberapa minggu lalu sekarang

371
00:20:51,000 --> 00:20:54,000
di mana kode Anda mulai berpindah ke sesuatu yang sangat buruk dirancang.

372
00:20:54,000 --> 00:20:57,000
Ingat bahwa saya membuat sebuah struktur mahasiswa bernama David,

373
00:20:57,000 --> 00:21:00,000
dan kemudian itu benar-benar alternatif, meskipun,

374
00:21:00,000 --> 00:21:04,000
untuk memiliki nama yang disebut variabel dan variabel lain yang disebut, saya pikir, rumah,

375
00:21:04,000 --> 00:21:08,000
dan variabel lain yang disebut ID karena dalam cerita itu saya kemudian ingin memperkenalkan sesuatu yang lain

376
00:21:08,000 --> 00:21:11,000
seperti Rob ke dalam program, jadi aku memutuskan tunggu dulu,

377
00:21:11,000 --> 00:21:13,000
Saya perlu untuk mengubah nama variabel.

378
00:21:13,000 --> 00:21:16,000
Mari kita sebut tambang name1, ID1, House1.

379
00:21:16,000 --> 00:21:20,000
Mari kita sebut Rob name2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Tapi kemudian tunggu sebentar, bagaimana dengan Tommy?

381
00:21:22,000 --> 00:21:24,000
Kemudian kita memiliki tiga variabel yang lebih.

382
00:21:24,000 --> 00:21:27,000
Kami memperkenalkan orang lain, empat set variabel.

383
00:21:27,000 --> 00:21:30,000
Dunia mulai mendapatkan berantakan sangat cepat,

384
00:21:30,000 --> 00:21:33,000
jadi kami memperkenalkan structs, dan apa yang menarik tentang struct?

385
00:21:33,000 --> 00:21:39,000
Apa struct C membiarkan Anda lakukan?

386
00:21:39,000 --> 00:21:42,000
Ini benar-benar aneh hari ini.

387
00:21:42,000 --> 00:21:44,000
Apa >> [respon siswa tidak terdengar]?

388
00:21:44,000 --> 00:21:47,000
Ya, khusus, typedef memungkinkan Anda untuk membuat tipe data baru,

389
00:21:47,000 --> 00:21:51,000
dan struct, kata kunci struct, memungkinkan Anda untuk merangkum

390
00:21:51,000 --> 00:21:54,000
konseptual terkait potongan data bersama-sama

391
00:21:54,000 --> 00:21:56,000
dan kemudian memanggil mereka seperti mahasiswa.

392
00:21:56,000 --> 00:21:58,000
>> Itu bagus karena sekarang kita dapat model

393
00:21:58,000 --> 00:22:03,000
semacam lebih banyak konseptual konsisten gagasan mahasiswa dalam sebuah variabel

394
00:22:03,000 --> 00:22:07,000
daripada sewenang-wenang memiliki satu untuk string, satu untuk ID, dan sebagainya.

395
00:22:07,000 --> 00:22:10,000
Array yang bagus karena mereka memungkinkan kita untuk mulai membersihkan kode kita.

396
00:22:10,000 --> 00:22:13,000
Tapi apa sisi negatifnya sekarang dari array?

397
00:22:13,000 --> 00:22:15,000
Apa yang dapat Anda lakukan tidak? Ya.

398
00:22:15,000 --> 00:22:17,000
[Mahasiswa] Anda harus tahu seberapa besar itu.

399
00:22:17,000 --> 00:22:19,000
Anda harus tahu seberapa besar itu, sehingga jenis rasa sakit.

400
00:22:19,000 --> 00:22:21,000
Bagi Anda dengan pengalaman pemrograman sebelumnya tahu bahwa dalam banyak bahasa,

401
00:22:21,000 --> 00:22:24,000
seperti Java, Anda dapat meminta sepotong memori, khususnya array,

402
00:22:24,000 --> 00:22:28,000
seberapa besar kau, dengan panjang, properti, sehingga untuk berbicara, dan itu benar-benar nyaman.

403
00:22:28,000 --> 00:22:32,000
Di C, Anda bahkan tidak bisa menyebut strlen pada array generik

404
00:22:32,000 --> 00:22:35,000
karena strlen, sebagai kata menyiratkan, hanya untuk string,

405
00:22:35,000 --> 00:22:39,000
dan Anda dapat mengetahui panjang string karena ini konvensi manusia

406
00:22:39,000 --> 00:22:43,000
dari memiliki \ 0, tapi array, lebih umum, hanya sepotong memori.

407
00:22:43,000 --> 00:22:46,000
Jika itu array ints, ada tidak akan ada beberapa karakter khusus

408
00:22:46,000 --> 00:22:48,000
di akhir menunggu untuk Anda.

409
00:22:48,000 --> 00:22:50,000
Anda harus ingat panjang array.

410
00:22:50,000 --> 00:22:54,000
Kelemahan lain dari array dibesarkan pusat di GetString sendiri.

411
00:22:54,000 --> 00:22:59,000
Apa lagi Kelemahan dari array?

412
00:22:59,000 --> 00:23:01,000
Pak, hanya kau dan aku hari ini.

413
00:23:01,000 --> 00:23:04,000
[Respon siswa terdengar] >> Ini apa?

414
00:23:04,000 --> 00:23:06,000
Ini menyatakan pada stack.

415
00:23:06,000 --> 00:23:09,000
Oke, menyatakan pada stack. Kenapa tidak Anda seperti itu?

416
00:23:09,000 --> 00:23:13,000
[Mahasiswa] Karena itu akan digunakan kembali.

417
00:23:13,000 --> 00:23:15,000
Ini akan digunakan kembali.

418
00:23:15,000 --> 00:23:18,000
Oke, jika Anda menggunakan array untuk mengalokasikan memori,

419
00:23:18,000 --> 00:23:21,000
Anda tidak bisa, misalnya, kembali karena pada stack.

420
00:23:21,000 --> 00:23:23,000
Oke, itu suatu kerugian.

421
00:23:23,000 --> 00:23:25,000
Dan bagaimana yang lain dengan array?

422
00:23:25,000 --> 00:23:28,000
Setelah Anda mengalokasikan itu, kau jenis kacau jika Anda membutuhkan lebih banyak ruang

423
00:23:28,000 --> 00:23:30,000
dari array yang memiliki.

424
00:23:30,000 --> 00:23:34,000
>> Kemudian kami diperkenalkan, ingat, malloc, yang memberi kami kemampuan untuk secara dinamis mengalokasikan memori.

425
00:23:34,000 --> 00:23:37,000
Tapi bagaimana kalau kita mencoba dunia yang berbeda sama sekali?

426
00:23:37,000 --> 00:23:40,000
Bagaimana jika kita ingin memecahkan beberapa masalah tersebut

427
00:23:40,000 --> 00:23:45,000
jadi kita bukannya saya-pena telah tertidur di sini-

428
00:23:45,000 --> 00:23:51,000
bagaimana jika kita bukan ingin dasarnya menciptakan dunia yang tidak lagi seperti ini?

429
00:23:51,000 --> 00:23:56,000
Ini adalah sebuah array, dan, tentu saja, ini semacam memburuk setelah kita memukul akhir array,

430
00:23:56,000 --> 00:24:00,000
dan sekarang saya tidak lagi memiliki ruang untuk yang lain integer atau karakter lain.

431
00:24:00,000 --> 00:24:03,000
Bagaimana jika kita semacam preemptively mengatakan baik, kenapa tidak kita bersantai

432
00:24:03,000 --> 00:24:07,000
ini persyaratan bahwa semua potongan memori akan berdekatan kembali ke belakang,

433
00:24:07,000 --> 00:24:10,000
dan kenapa tidak, ketika saya membutuhkan sebuah int atau char,

434
00:24:10,000 --> 00:24:12,000
hanya memberi saya ruang untuk salah satu dari mereka?

435
00:24:12,000 --> 00:24:14,000
Dan ketika aku butuh yang lain, memberi saya ruang lain,

436
00:24:14,000 --> 00:24:16,000
dan ketika aku butuh yang lain, memberi saya ruang lain.

437
00:24:16,000 --> 00:24:19,000
Keuntungan yang sekarang adalah bahwa jika orang lain

438
00:24:19,000 --> 00:24:21,000
mengambil memori di sini, bukan masalah besar.

439
00:24:21,000 --> 00:24:25,000
Aku akan mengambil sepotong tambahan memori di sini dan kemudian satu ini.

440
00:24:25,000 --> 00:24:28,000
>> Sekarang, hasil tangkapan hanya di sini adalah bahwa ini hampir terasa seperti saya

441
00:24:28,000 --> 00:24:30,000
sejumlah variabel yang berbeda.

442
00:24:30,000 --> 00:24:33,000
Ini terasa seperti lima variabel yang berbeda berpotensi.

443
00:24:33,000 --> 00:24:36,000
Tapi bagaimana kalau kita mencuri ide dari string

444
00:24:36,000 --> 00:24:41,000
dimana kita entah bagaimana menghubungkan hal-hal ini bersama-sama secara konseptual, dan bagaimana jika saya melakukan ini?

445
00:24:41,000 --> 00:24:44,000
Ini adalah panahku sangat buruk ditarik.

446
00:24:44,000 --> 00:24:46,000
Tapi misalkan bahwa masing-masing potongan memori

447
00:24:46,000 --> 00:24:52,000
menunjuk ke yang lain, dan orang ini, yang tidak memiliki saudara di sebelah kanannya,

448
00:24:52,000 --> 00:24:54,000
tidak memiliki panah tersebut.

449
00:24:54,000 --> 00:24:56,000
Ini sebenarnya apa yang disebut linked list.

450
00:24:56,000 --> 00:25:00,000
Ini adalah struktur data baru yang memungkinkan kita untuk mengalokasikan sepotong memori,

451
00:25:00,000 --> 00:25:03,000
kemudian lain, lalu yang lain, lalu yang lain, setiap saat kita inginkan

452
00:25:03,000 --> 00:25:07,000
selama program, dan kita ingat bahwa mereka semua entah bagaimana terkait

453
00:25:07,000 --> 00:25:11,000
oleh harfiah chaining mereka bersama-sama, dan kami melakukan itu pictorially sini dengan panah.

454
00:25:11,000 --> 00:25:15,000
Tapi dalam kode, apa yang akan menjadi mekanisme melalui mana Anda entah bagaimana bisa terhubung,

455
00:25:15,000 --> 00:25:20,000
hampir seperti Scratch, salah satu potongan ke potongan lain?

456
00:25:20,000 --> 00:25:22,000
Kita bisa menggunakan pointer, kan?

457
00:25:22,000 --> 00:25:25,000
Karena benar-benar panah yang pergi dari alun-alun kiri atas,

458
00:25:25,000 --> 00:25:31,000
orang ini di sini untuk yang satu ini, bisa berisi dalam alun-alun ini

459
00:25:31,000 --> 00:25:34,000
bukan hanya beberapa ints, bukan hanya beberapa char, tapi bagaimana jika saya benar-benar dialokasikan

460
00:25:34,000 --> 00:25:37,000
sedikit ruang ekstra sehingga sekarang,

461
00:25:37,000 --> 00:25:41,000
masing-masing potongan memori saya, meskipun ini akan saya biaya,

462
00:25:41,000 --> 00:25:45,000
sekarang terlihat sedikit lebih persegi panjang di mana salah satu potongan memori

463
00:25:45,000 --> 00:25:47,000
digunakan untuk nomor, seperti nomor 1,

464
00:25:47,000 --> 00:25:50,000
dan kemudian jika orang ini menyimpan nomor 2,

465
00:25:50,000 --> 00:25:52,000
ini potongan lain dari memori digunakan untuk panah,

466
00:25:52,000 --> 00:25:54,000
atau lebih konkret, pointer.

467
00:25:54,000 --> 00:25:59,000
Dan kira saya menyimpan nomor 3 di sini sementara aku menggunakan ini untuk menunjuk pada orang itu,

468
00:25:59,000 --> 00:26:02,000
dan sekarang orang ini, mari kita kira saya hanya ingin tiga potongan seperti memori.

469
00:26:02,000 --> 00:26:05,000
Aku akan menarik garis melalui itu, menunjukkan nol.

470
00:26:05,000 --> 00:26:07,000
Tidak ada karakter tambahan.

471
00:26:07,000 --> 00:26:10,000
>> Memang, ini adalah bagaimana kita bisa pergi tentang pelaksanaan

472
00:26:10,000 --> 00:26:12,000
sesuatu yang disebut linked list.

473
00:26:12,000 --> 00:26:18,000
Sebuah linked list adalah struktur data baru, dan itu adalah batu loncatan menuju

474
00:26:18,000 --> 00:26:21,000
jauh lebih menarik struktur data yang mulai memecahkan masalah

475
00:26:21,000 --> 00:26:23,000
sepanjang garis Facebook-jenis masalah dan Google-jenis masalah

476
00:26:23,000 --> 00:26:26,000
di mana Anda memiliki set data yang besar, dan tidak lagi memotong itu

477
00:26:26,000 --> 00:26:29,000
untuk menyimpan segala contiguously dan menggunakan sesuatu seperti pencarian linear

478
00:26:29,000 --> 00:26:31,000
atau bahkan sesuatu seperti pencarian biner.

479
00:26:31,000 --> 00:26:33,000
Anda ingin waktu berjalan lebih baik.

480
00:26:33,000 --> 00:26:37,000
Bahkan, salah satu Grails Kudus kita akan berbicara tentang akhir pekan ini atau berikutnya

481
00:26:37,000 --> 00:26:41,000
adalah algoritma yang berjalan waktu konstan.

482
00:26:41,000 --> 00:26:44,000
Dengan kata lain, selalu mengambil jumlah waktu yang sama tidak peduli

483
00:26:44,000 --> 00:26:47,000
seberapa besar input, dan itu memang akan menarik,

484
00:26:47,000 --> 00:26:49,000
bahkan lebih daripada sesuatu yang logaritmik.

485
00:26:49,000 --> 00:26:51,000
Apa ini di layar di sini?

486
00:26:51,000 --> 00:26:55,000
Setiap persegi panjang adalah apa yang saya hanya menggambar dengan tangan.

487
00:26:55,000 --> 00:26:59,000
Tapi hal sepanjang jalan di sebelah kiri adalah variabel khusus.

488
00:26:59,000 --> 00:27:02,000
Ini akan menjadi pointer tunggal karena satu gotcha

489
00:27:02,000 --> 00:27:04,000
dengan linked list, sebagai hal-hal yang disebut,

490
00:27:04,000 --> 00:27:09,000
adalah bahwa Anda harus menggantung ke salah satu ujung linked list.

491
00:27:09,000 --> 00:27:13,000
>> Sama seperti dengan string, Anda harus tahu alamat char pertama.

492
00:27:13,000 --> 00:27:15,000
Sama kesepakatan untuk daftar terkait.

493
00:27:15,000 --> 00:27:19,000
Anda harus tahu alamat dari potongan pertama dari memori

494
00:27:19,000 --> 00:27:25,000
karena dari sana, Anda dapat mencapai setiap orang lainnya.

495
00:27:25,000 --> 00:27:27,000
Downside.

496
00:27:27,000 --> 00:27:30,000
Berapa harga yang kita bayar untuk fleksibilitas memiliki dinamis

497
00:27:30,000 --> 00:27:34,000
struktur data yang cukup besar bahwa jika kita pernah membutuhkan lebih banyak memori, baik,

498
00:27:34,000 --> 00:27:37,000
hanya mengalokasikan satu potongan lagi dan menarik pointer dari

499
00:27:37,000 --> 00:27:39,000
lama ke ekor baru dari daftar?

500
00:27:39,000 --> 00:27:41,000
Ya.

501
00:27:41,000 --> 00:27:43,000
[Mahasiswa] Dibutuhkan ruang sekitar dua kali lebih banyak.

502
00:27:43,000 --> 00:27:45,000
Dibutuhkan ruang dua kali lebih banyak, sehingga pasti sisi negatifnya, dan kita telah melihat ini

503
00:27:45,000 --> 00:27:48,000
tradeoff sebelumnya antara waktu dan ruang dan fleksibilitas

504
00:27:48,000 --> 00:27:51,000
di mana sekarang, kita tidak perlu 32 bit untuk masing-masing nomor.

505
00:27:51,000 --> 00:27:57,000
Kami benar-benar membutuhkan 64, 32 untuk nomor 32 dan untuk pointer.

506
00:27:57,000 --> 00:27:59,000
Tapi, hei, aku punya 2 gigabyte RAM.

507
00:27:59,000 --> 00:28:02,000
Menambahkan lain 32 bit di sini dan di sini tidak tampak bahwa masalah besar.

508
00:28:02,000 --> 00:28:05,000
Tapi untuk set data yang besar, pasti menambahkan hingga benar-benar dua kali lebih banyak.

509
00:28:05,000 --> 00:28:09,000
Apa downside lain sekarang, atau apa fitur yang kita menyerah,

510
00:28:09,000 --> 00:28:12,000
jika kita mewakili daftar hal-hal dengan linked list dan bukan array?

511
00:28:12,000 --> 00:28:14,000
[Mahasiswa] Anda tidak dapat melintasi itu mundur.

512
00:28:14,000 --> 00:28:16,000
Anda tidak dapat melintasi ke belakang, sehingga Anda jenis kacau jika Anda berjalan

513
00:28:16,000 --> 00:28:19,000
dari kiri ke kanan menggunakan untuk loop atau loop sementara

514
00:28:19,000 --> 00:28:21,000
dan kemudian Anda menyadari, "Oh, aku ingin kembali ke awal daftar."

515
00:28:21,000 --> 00:28:26,000
Anda tidak bisa karena pointer hanya pergi dari kiri ke kanan sebagai panah menunjukkan.

516
00:28:26,000 --> 00:28:29,000
>> Sekarang, Anda bisa mengingat awal daftar dengan variabel lain,

517
00:28:29,000 --> 00:28:31,000
tapi itu kompleksitas yang perlu diingat.

518
00:28:31,000 --> 00:28:35,000
Array, tidak peduli seberapa jauh Anda pergi, Anda selalu dapat melakukan dikurangi, dikurangi, dikurangi, dikurangi

519
00:28:35,000 --> 00:28:37,000
dan kembali dari mana kamu datang.

520
00:28:37,000 --> 00:28:40,000
Apa Kelemahan lain di sini? Ya.

521
00:28:40,000 --> 00:28:43,000
[Pertanyaan siswa tidak terdengar]

522
00:28:43,000 --> 00:28:47,000
Anda bisa, sehingga Anda sudah benar-benar hanya mengusulkan struktur data yang disebut daftar ganda terkait,

523
00:28:47,000 --> 00:28:50,000
dan memang, Anda akan menambahkan pointer lain untuk masing-masing persegi panjang

524
00:28:50,000 --> 00:28:53,000
yang pergi arah lain, terbalik dari yang

525
00:28:53,000 --> 00:28:55,000
kini Anda dapat melintasi bolak-balik,

526
00:28:55,000 --> 00:28:59,000
downside yang sekarang Anda menggunakan tiga kali sebagai memori sebanyak yang kita digunakan untuk

527
00:28:59,000 --> 00:29:04,000
dan juga menambah kompleksitas dalam hal kode Anda harus menulis untuk bisa melakukannya dengan benar.

528
00:29:04,000 --> 00:29:08,000
Tapi ini semua mungkin pengorbanan yang sangat wajar, jika pembalikan yang lebih penting.

529
00:29:08,000 --> 00:29:10,000
Ya.

530
00:29:10,000 --> 00:29:12,000
[Mahasiswa] Anda juga tidak dapat memiliki sebuah linked list 2D.

531
00:29:12,000 --> 00:29:16,000
Baik, Anda tidak bisa benar-benar memiliki linked list 2D.

532
00:29:16,000 --> 00:29:18,000
Anda bisa. Ini tidak semudah array.

533
00:29:18,000 --> 00:29:21,000
Seperti array, Anda melakukan braket terbuka, tertutup braket, braket terbuka, tertutup braket,

534
00:29:21,000 --> 00:29:23,000
dan Anda mendapatkan beberapa struktur 2-dimensi.

535
00:29:23,000 --> 00:29:26,000
Anda bisa menerapkan daftar 2-dimensi terkait

536
00:29:26,000 --> 00:29:29,000
jika Anda melakukan add-seperti yang Anda diusulkan-pointer ketiga untuk masing-masing hal,

537
00:29:29,000 --> 00:29:34,000
dan jika Anda berpikir tentang daftar yang lain datang pada Anda bergaya 3D

538
00:29:34,000 --> 00:29:40,000
dari layar untuk kita semua, yang hanya satu rantai dari beberapa macam.

539
00:29:40,000 --> 00:29:45,000
Kita bisa melakukannya, tapi itu tidak sesederhana mengetik braket terbuka, braket persegi. Ya.

540
00:29:45,000 --> 00:29:48,000
[Pertanyaan siswa tidak terdengar]

541
00:29:48,000 --> 00:29:50,000
Baik, jadi ini adalah kicker nyata.

542
00:29:50,000 --> 00:29:54,000
>> Algoritma ini bahwa kita telah pined lebih, seperti oh, pencarian biner,

543
00:29:54,000 --> 00:29:57,000
Anda dapat mencari berbagai angka di papan

544
00:29:57,000 --> 00:30:01,000
atau buku telepon jauh lebih cepat jika Anda menggunakan membagi dan menaklukkan

545
00:30:01,000 --> 00:30:05,000
dan algoritma pencarian biner, tapi pencarian biner diperlukan dua asumsi.

546
00:30:05,000 --> 00:30:09,000
Satu, bahwa data diurutkan.

547
00:30:09,000 --> 00:30:11,000
Sekarang, kita mungkin bisa menjaga ini diurutkan,

548
00:30:11,000 --> 00:30:14,000
jadi mungkin itu bukan masalah, tapi pencarian biner juga diasumsikan

549
00:30:14,000 --> 00:30:18,000
bahwa Anda memiliki akses acak ke daftar nomor,

550
00:30:18,000 --> 00:30:21,000
dan array memungkinkan Anda untuk memiliki akses acak, dan dengan akses random,

551
00:30:21,000 --> 00:30:24,000
Maksudku jika Anda diberikan sebuah array, berapa lama waktu yang dibutuhkan Anda

552
00:30:24,000 --> 00:30:26,000
untuk sampai ke braket 0?

553
00:30:26,000 --> 00:30:29,000
Satu operasi, Anda hanya menggunakan [0] dan Anda berada di sana.

554
00:30:29,000 --> 00:30:33,000
Berapa banyak langkah yang dibutuhkan untuk sampai ke lokasi 10?

555
00:30:33,000 --> 00:30:36,000
Salah satu langkah, Anda hanya pergi ke [10] dan Anda berada di sana.

556
00:30:36,000 --> 00:30:40,000
Sebaliknya, bagaimana Anda bisa sampai ke bilangan bulat 10 dalam linked list?

557
00:30:40,000 --> 00:30:42,000
Anda harus mulai dari awal karena Anda hanya mengingat

558
00:30:42,000 --> 00:30:45,000
awal dari sebuah linked list, seperti string sedang diingat

559
00:30:45,000 --> 00:30:48,000
dengan alamat char pertama, dan menemukan bahwa int 10

560
00:30:48,000 --> 00:30:53,000
atau bahwa karakter ke-10 dalam sebuah string, Anda harus mencari hal sialan seluruh.

561
00:30:53,000 --> 00:30:55,000
>> Sekali lagi, kita tidak memecahkan semua masalah kita.

562
00:30:55,000 --> 00:31:00,000
Kami memperkenalkan yang baru, tapi itu benar-benar tergantung pada apa yang Anda mencoba untuk merancang untuk.

563
00:31:00,000 --> 00:31:04,000
Dalam hal pelaksanaan ini, kita dapat meminjam ide dari mahasiswa bahwa struktur.

564
00:31:04,000 --> 00:31:07,000
Sintaksnya sangat mirip, kecuali sekarang, ide ini sedikit lebih abstrak

565
00:31:07,000 --> 00:31:09,000
dari rumah dan nama dan ID.

566
00:31:09,000 --> 00:31:13,000
Tapi saya mengusulkan agar kita bisa memiliki struktur data dalam C

567
00:31:13,000 --> 00:31:17,000
yang disebut node, sebagai kata terakhir pada slide menunjukkan,

568
00:31:17,000 --> 00:31:21,000
dalam sebuah node, dan node adalah hanya sebuah wadah generik dalam ilmu komputer.

569
00:31:21,000 --> 00:31:25,000
Ini biasanya digambarkan sebagai lingkaran atau persegi atau persegi panjang seperti yang kita lakukan.

570
00:31:25,000 --> 00:31:27,000
Dan dalam hal ini struktur data, kita memiliki int, n,

571
00:31:27,000 --> 00:31:29,000
jadi itu nomor saya ingin menyimpan.

572
00:31:29,000 --> 00:31:36,000
Tapi apa ini baris kedua, struct simpul * selanjutnya?

573
00:31:36,000 --> 00:31:40,000
Mengapa hal ini benar, atau apa peran apakah ini bermain hal,

574
00:31:40,000 --> 00:31:42,000
meskipun agak samar pada pandangan pertama?

575
00:31:42,000 --> 00:31:44,000
Ya.

576
00:31:44,000 --> 00:31:46,000
[Respon siswa tidak terdengar]

577
00:31:46,000 --> 00:31:50,000
Tepat, sehingga semacam * dari rampasan bahwa itu adalah pointer dari beberapa macam.

578
00:31:50,000 --> 00:31:53,000
Nama pointer ini sewenang-wenang berikutnya,

579
00:31:53,000 --> 00:32:00,000
tapi kita bisa menyebutnya apa pun yang kita inginkan, tapi apa titik pointer ke?

580
00:32:00,000 --> 00:32:03,000
[Mahasiswa] simpul lain >> Tepat,. Ini menunjuk ke node lain tersebut.

581
00:32:03,000 --> 00:32:05,000
>> Sekarang, ini adalah semacam rasa ingin tahu C.

582
00:32:05,000 --> 00:32:09,000
Ingat bahwa C dibaca oleh compiler atas ke bawah, kiri ke kanan,

583
00:32:09,000 --> 00:32:13,000
yang berarti jika-ini sedikit berbeda dari apa yang kita lakukan dengan siswa.

584
00:32:13,000 --> 00:32:16,000
Ketika kita mendefinisikan mahasiswa, kita benar-benar tidak menaruh kata di sana.

585
00:32:16,000 --> 00:32:18,000
Itu hanya kata typedef.

586
00:32:18,000 --> 00:32:20,000
Kemudian kami memiliki id, nama string int, string rumah,

587
00:32:20,000 --> 00:32:23,000
dan kemudian mahasiswa di bawah struct.

588
00:32:23,000 --> 00:32:26,000
Deklarasi ini sedikit berbeda karena,

589
00:32:26,000 --> 00:32:28,000
lagi, compiler C sedikit bodoh.

590
00:32:28,000 --> 00:32:30,000
Ini hanya akan membaca atas ke bawah,

591
00:32:30,000 --> 00:32:33,000
jadi jika mencapai garis 2 di sini

592
00:32:33,000 --> 00:32:37,000
di mana selanjutnya dinyatakan dan melihat, oh, di sini adalah variabel yang disebut selanjutnya.

593
00:32:37,000 --> 00:32:39,000
Ini adalah pointer ke node struct.

594
00:32:39,000 --> 00:32:42,000
Compiler akan menyadari apa yang node struct?

595
00:32:42,000 --> 00:32:44,000
Aku belum pernah mendengar hal ini sebelumnya,

596
00:32:44,000 --> 00:32:47,000
karena node kata tidak mungkin jika tidak muncul

597
00:32:47,000 --> 00:32:49,000
sampai bagian bawah, sehingga ada redundansi ini.

598
00:32:49,000 --> 00:32:53,000
Anda harus mengatakan simpul struct di sini, yang kemudian dapat mempersingkat nanti

599
00:32:53,000 --> 00:32:56,000
berkat typedef di sini, tapi ini karena

600
00:32:56,000 --> 00:33:02,000
kita referensi struktur itu sendiri dalam struktur.

601
00:33:02,000 --> 00:33:05,000
Itulah satu gotcha di sana.

602
00:33:05,000 --> 00:33:07,000
>> Beberapa masalah yang menarik akan muncul.

603
00:33:07,000 --> 00:33:09,000
Kami punya daftar nomor. Bagaimana kita masukkan ke dalamnya?

604
00:33:09,000 --> 00:33:11,000
Bagaimana kita mencarinya? Bagaimana kita menghapus dari itu?

605
00:33:11,000 --> 00:33:13,000
Apalagi sekarang bahwa kita harus mengelola semua pointer.

606
00:33:13,000 --> 00:33:15,000
Kau pikir pointer adalah semacam pikiran-lipatan

607
00:33:15,000 --> 00:33:17,000
ketika Anda memiliki salah satu dari mereka hanya mencoba untuk membaca sebuah int untuk itu.

608
00:33:17,000 --> 00:33:20,000
Sekarang kita harus memanipulasi senilai seluruh daftar itu.

609
00:33:20,000 --> 00:33:22,000
Kenapa tidak kita mengambil 5 menit istirahat kami di sini, dan kemudian kami akan membawa

610
00:33:22,000 --> 00:33:34,000
beberapa orang di atas panggung untuk melakukan hal itu.

611
00:33:34,000 --> 00:33:36,000
>> C adalah jauh lebih menyenangkan ketika itu bertindak keluar.

612
00:33:36,000 --> 00:33:39,000
Yang secara harfiah ingin menjadi yang pertama?

613
00:33:39,000 --> 00:33:41,000
Oke, ayo naik. Anda pertama kali.

614
00:33:41,000 --> 00:33:44,000
Siapa yang ingin menjadi 9? Oke, 9.

615
00:33:44,000 --> 00:33:46,000
Bagaimana 9? 17?

616
00:33:46,000 --> 00:33:51,000
Sebuah kelompok kecil di sini. 22 dan 26 dalam barisan depan.

617
00:33:51,000 --> 00:33:53,000
Dan lalu bagaimana tentang seseorang di sana yang menunjuk.

618
00:33:53,000 --> 00:33:57,000
Anda 34. Oke, 34, datang ke atas.

619
00:33:57,000 --> 00:33:59,000
Pertama ada di sana. Oke, semua empat dari kalian.

620
00:33:59,000 --> 00:34:01,000
Dan siapa yang kita katakan untuk 9?

621
00:34:01,000 --> 00:34:04,000
Siapa 9 kita?

622
00:34:04,000 --> 00:34:07,000
Yang benar-benar ingin menjadi 9? Baiklah, ayolah, menjadi 9.

623
00:34:07,000 --> 00:34:10,000
Di sini kita pergi.

624
00:34:10,000 --> 00:34:13,000
34, kita akan bertemu Anda di sana.

625
00:34:13,000 --> 00:34:17,000
Bagian pertama adalah membuat dirimu terlihat seperti itu.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, baik.

627
00:34:21,000 --> 00:34:25,000
Jika Anda dapat berdiri ke samping, karena kita akan malloc Anda dalam sekejap.

628
00:34:25,000 --> 00:34:29,000
>> Bagus, bagus.

629
00:34:29,000 --> 00:34:32,000
Oke, baik, jadi mari kita mengajukan beberapa pertanyaan di sini.

630
00:34:32,000 --> 00:34:34,000
Dan sebenarnya, siapa namamu? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, oke, datang ke sini.

632
00:34:37,000 --> 00:34:41,000
Anita akan membantu kita semacam memecahkan salah satu pertanyaan yang cukup sederhana di pertama,

633
00:34:41,000 --> 00:34:44,000
yang adalah bagaimana Anda mengetahui apakah atau tidak nilai dalam daftar?

634
00:34:44,000 --> 00:34:48,000
Sekarang, perhatikan bahwa pertama, diwakili di sini oleh Lucas,

635
00:34:48,000 --> 00:34:52,000
adalah sedikit berbeda, sehingga karyanya kertas yang sengaja samping

636
00:34:52,000 --> 00:34:55,000
karena itu tidak cukup sebagai tinggi dan tidak mengambil banyak bit,

637
00:34:55,000 --> 00:34:58,000
meskipun secara teknis ia memiliki ukuran kertas yang sama hanya diputar.

638
00:34:58,000 --> 00:35:01,000
Tapi dia sedikit berbeda dalam bahwa dia hanya 32 bit untuk pointer,

639
00:35:01,000 --> 00:35:05,000
dan semua orang-orang ini adalah 64 bit, setengah dari yang adalah nomor, setengah dari yang adalah pointer.

640
00:35:05,000 --> 00:35:08,000
Tapi pointer tidak digambarkan, jadi jika kalian bisa agak canggung

641
00:35:08,000 --> 00:35:12,000
menggunakan tangan kiri Anda untuk menunjuk pada orang di sebelah Anda.

642
00:35:12,000 --> 00:35:14,000
Dan kau nomor 34. Siapa nama Anda?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, jadi sebenarnya, memegang kertas di tangan kanan Anda, dan tangan kiri berjalan lurus ke bawah.

645
00:35:19,000 --> 00:35:21,000
Anda mewakili nol di sebelah kiri.

646
00:35:21,000 --> 00:35:24,000
>> Sekarang gambar manusia sangat konsisten.

647
00:35:24,000 --> 00:35:26,000
Ini sebenarnya bagaimana pointer bekerja.

648
00:35:26,000 --> 00:35:29,000
Dan jika Anda bisa mengernyitkan sedikit cara ini jadi saya tidak dengan cara Anda.

649
00:35:29,000 --> 00:35:34,000
Anita sini, menemukan saya nomor 22,

650
00:35:34,000 --> 00:35:40,000
tetapi mengasumsikan kendala tidak manusia memegang potongan kertas,

651
00:35:40,000 --> 00:35:43,000
tapi ini adalah daftar, dan Anda hanya memiliki Lucas untuk memulai dengan

652
00:35:43,000 --> 00:35:46,000
karena ia secara harfiah pointer pertama.

653
00:35:46,000 --> 00:35:51,000
Misalkan Anda sendiri adalah pointer, dan sehingga Anda juga memiliki kemampuan untuk menunjuk sesuatu.

654
00:35:51,000 --> 00:35:56,000
Kenapa tidak Anda mulai dengan menunjuk pada apa Lucas menunjuk?

655
00:35:56,000 --> 00:35:58,000
Baik, dan biarkan aku memberlakukan hal ini di sini.

656
00:35:58,000 --> 00:36:04,000
Hanya demi diskusi, biarkan aku menarik sebuah halaman kosong di sini.

657
00:36:04,000 --> 00:36:06,000
Bagaimana Anda mengeja nama Anda? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Oke, Anita.

659
00:36:08,000 --> 00:36:18,000
Katakanlah simpul * anita = lucas.

660
00:36:18,000 --> 00:36:22,000
Yah, kita tidak harus memanggil Anda lucas. Kita harus menghubungi Anda terlebih dahulu.

661
00:36:22,000 --> 00:36:25,000
Mengapa ini sebenarnya sesuai dengan kenyataan di sini?

662
00:36:25,000 --> 00:36:27,000
Satu, pertama sudah ada.

663
00:36:27,000 --> 00:36:30,000
Pertama telah dialokasikan mungkin di suatu tempat di sini.

664
00:36:30,000 --> 00:36:35,000
Node * pertama, dan itu sudah dialokasikan daftar entah bagaimana.

665
00:36:35,000 --> 00:36:37,000
Saya tidak tahu bagaimana itu bisa terjadi. Itu terjadi sebelum kelas dimulai.

666
00:36:37,000 --> 00:36:40,000
Ini linked list manusia telah diciptakan.

667
00:36:40,000 --> 00:36:44,000
Dan sekarang pada titik ini dalam kisah-ini semua terjadi Facebook rupanya nanti-

668
00:36:44,000 --> 00:36:49,000
pada titik ini dalam cerita, Anita telah diinisialisasi menjadi sama dengan pertama,

669
00:36:49,000 --> 00:36:51,000
yang tidak berarti bahwa Anita poin di Lucas.

670
00:36:51,000 --> 00:36:53,000
Sebaliknya, ia menunjuk pada apa yang ia menunjuk pada

671
00:36:53,000 --> 00:36:57,000
karena alamat yang sama itu dalam 32 Lucas bit -, 1 2, 3 -

672
00:36:57,000 --> 00:37:01,000
sekarang juga dalam 32 Anita bit -, 1 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Sekarang menemukan 22. Bagaimana Anda pergi tentang melakukan ini?

674
00:37:05,000 --> 00:37:07,000
Apa itu Point? >> Apa pun.

675
00:37:07,000 --> 00:37:11,000
Gunanya untuk apa, jadi lanjutkan dan bertindak keluar sebagai yang terbaik Anda dapat di sini.

676
00:37:11,000 --> 00:37:15,000
Bagus, bagus, dan sekarang Anda sedang menunjuk-siapa namamu dengan 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, sehingga Ramon adalah mengangkat 22.

678
00:37:18,000 --> 00:37:20,000
Anda sekarang telah melakukan cek.

679
00:37:20,000 --> 00:37:24,000
Apakah Ramon == 22, dan jika demikian, misalnya, kita bisa kembali benar.

680
00:37:24,000 --> 00:37:26,000
Mari saya-sementara orang-orang ini berdiri di sini agak canggung-

681
00:37:26,000 --> 00:37:32,000
biarkan aku melakukan sesuatu dengan cepat seperti bool menemukan.

682
00:37:32,000 --> 00:37:37,000
Aku akan pergi ke depan dan mengatakan (node ​​* Daftar, int n).

683
00:37:37,000 --> 00:37:39,000
Aku akan segera kembali dengan kalian. Aku hanya harus menulis beberapa kode.

684
00:37:39,000 --> 00:37:45,000
Dan sekarang aku akan pergi ke depan dan melakukan hal ini, simpul * anita list =.

685
00:37:45,000 --> 00:37:51,000
Dan aku akan pergi ke depan dan mengatakan sementara (anita = NULL!).

686
00:37:51,000 --> 00:37:57,000
>> Metafora di sini semakin sedikit membentang, tapi sementara (anita = NULL!), Apa yang ingin saya lakukan?

687
00:37:57,000 --> 00:38:03,000
Aku butuh cara referensi

688
00:38:03,000 --> 00:38:05,000
integer yang Anita menunjuk.

689
00:38:05,000 --> 00:38:08,000
Di masa lalu, ketika kami memiliki struktur, yang simpul adalah,

690
00:38:08,000 --> 00:38:11,000
kami menggunakan notasi titik, dan kita akan mengatakan sesuatu seperti

691
00:38:11,000 --> 00:38:15,000
anita.n, tapi masalah di sini adalah bahwa Anita bukanlah struct per se.

692
00:38:15,000 --> 00:38:17,000
Apa dia?

693
00:38:17,000 --> 00:38:21,000
Dia pointer, sehingga benar-benar, jika kita ingin menggunakan dot notasi-

694
00:38:21,000 --> 00:38:23,000
dan ini akan terlihat sengaja sedikit samar-

695
00:38:23,000 --> 00:38:28,000
kita harus melakukan sesuatu seperti pergi ke tangan kiri apapun Anita menunjuk pada

696
00:38:28,000 --> 00:38:31,000
dan kemudian mendapatkan lapangan disebut n.

697
00:38:31,000 --> 00:38:35,000
Anita pointer, tapi apa * anita?

698
00:38:35,000 --> 00:38:38,000
Apa yang Anda temukan ketika Anda pergi ke apa Anita yang menunjuk?

699
00:38:38,000 --> 00:38:42,000
Sebuah struct, node, dan node, recall, memiliki medan disebut n

700
00:38:42,000 --> 00:38:47,000
karena telah, ingat, ini 2 bidang, selanjutnya dan n,

701
00:38:47,000 --> 00:38:50,000
bahwa kita melihat beberapa saat yang lalu di sini.

702
00:38:50,000 --> 00:38:53,000
>> Untuk benar-benar meniru ini dalam kode,

703
00:38:53,000 --> 00:39:02,000
kita bisa melakukan ini dan mengatakan jika ((* anita). n == n), n yang saya cari.

704
00:39:02,000 --> 00:39:04,000
Perhatikan bahwa fungsi disahkan pada nomor saya peduli.

705
00:39:04,000 --> 00:39:10,000
Lalu aku bisa pergi ke depan dan melakukan sesuatu seperti return true.

706
00:39:10,000 --> 00:39:12,000
Lain, jika itu tidak terjadi, apa yang ingin saya lakukan?

707
00:39:12,000 --> 00:39:19,000
Bagaimana cara menerjemahkan untuk kode apa Anita melakukannya secara intuitif dengan berjalan melalui daftar?

708
00:39:19,000 --> 00:39:26,000
Apa yang harus saya lakukan di sini untuk mensimulasikan Anita mengambil langkah yang ke kiri, langkah yang ke kiri?

709
00:39:26,000 --> 00:39:28,000
[Respon siswa terdengar] >> Apa itu?

710
00:39:28,000 --> 00:39:30,000
[Respon siswa tidak terdengar]

711
00:39:30,000 --> 00:39:34,000
Baik, bukan ide yang buruk, namun di masa lalu, ketika kita sudah melakukan ini, kami telah melakukan anita + +

712
00:39:34,000 --> 00:39:37,000
karena itu akan menambahkan angka 1 sampai Anita,

713
00:39:37,000 --> 00:39:40,000
yang biasanya akan menunjuk pada orang berikutnya, seperti Ramon,

714
00:39:40,000 --> 00:39:44,000
atau orang di sampingnya, atau di sampingnya orang di telepon.

715
00:39:44,000 --> 00:39:49,000
Tapi itu tidak cukup baik di sini karena apa hal ini terlihat seperti dalam memori?

716
00:39:49,000 --> 00:39:54,000
Bukan itu. Kita harus menonaktifkan itu.

717
00:39:54,000 --> 00:40:00,000
Ini terlihat seperti ini dalam memori, dan meskipun saya sudah ditarik 1 dan 2 dan 3 dekat satu sama lain,

718
00:40:00,000 --> 00:40:03,000
jika kita benar-benar mensimulasikan ini-bisa kalian, sementara masih menunjuk pada orang yang sama,

719
00:40:03,000 --> 00:40:07,000
dapat beberapa dari Anda mengambil langkah mundur acak, beberapa dari Anda langkah acak maju?

720
00:40:07,000 --> 00:40:10,000
>> Kekacauan ini masih merupakan linked list,

721
00:40:10,000 --> 00:40:13,000
tapi orang-orang bisa di mana saja dalam memori,

722
00:40:13,000 --> 00:40:15,000
jadi anita + + tidak akan bekerja mengapa?

723
00:40:15,000 --> 00:40:19,000
Apa yang ada di lokasi anita + +?

724
00:40:19,000 --> 00:40:21,000
Siapa tahu.

725
00:40:21,000 --> 00:40:24,000
Ini beberapa nilai lain yang kebetulan akan sela

726
00:40:24,000 --> 00:40:28,000
di antara semua node secara kebetulan karena kita tidak menggunakan array.

727
00:40:28,000 --> 00:40:30,000
Kami dialokasikan masing-masing node individual.

728
00:40:30,000 --> 00:40:32,000
Oke, jika kalian dapat membersihkan diri kembali.

729
00:40:32,000 --> 00:40:37,000
Biarkan saya mengusulkan bahwa bukan anita + +, kita bukannya melakukan anita mendapat-

730
00:40:37,000 --> 00:40:42,000
baik, kenapa tidak kita pergi ke apapun Anita yang menunjuk dan kemudian melakukan. selanjutnya?

731
00:40:42,000 --> 00:40:45,000
Dengan kata lain, kita pergi ke Ramon, siapa yang memegang nomor 22,

732
00:40:45,000 --> 00:40:51,000
dan kemudian selanjutnya adalah. seakan Anita akan menyalin pointer tangan kirinya.

733
00:40:51,000 --> 00:40:54,000
Tapi dia tidak akan pergi lebih jauh dari Ramon karena kita menemukan 22.

734
00:40:54,000 --> 00:40:56,000
Tapi itu akan menjadi ide. Sekarang, ini adalah berantakan dewa-mengerikan.

735
00:40:56,000 --> 00:40:59,000
Jujur, tak seorang pun akan mengingat sintaks ini, dan jadi untungnya,

736
00:40:59,000 --> 00:41:04,000
itu sebenarnya disengaja-oh sedikit, Anda tidak benar-benar melihat apa yang saya tulis.

737
00:41:04,000 --> 00:41:08,000
Hal ini akan lebih menarik jika Anda bisa. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Di belakang layar, saya memecahkan masalah dengan cara ini.

739
00:41:10,000 --> 00:41:14,000
Anita, untuk mengambil langkah ke kiri,

740
00:41:14,000 --> 00:41:18,000
pertama, kami pergi ke alamat yang Anita menunjuk

741
00:41:18,000 --> 00:41:23,000
dan di mana dia akan menemukan tidak hanya n, yang kita hanya memeriksa demi perbandingan itu,

742
00:41:23,000 --> 00:41:25,000
tetapi Anda juga akan menemukan berikutnya - dalam hal ini,

743
00:41:25,000 --> 00:41:28,000
Tangan kiri Ramon menunjuk ke node berikutnya dalam daftar.

744
00:41:28,000 --> 00:41:32,000
Tapi ini adalah kekacauan dewa-mengerikan yang saya disebut sebelumnya,

745
00:41:32,000 --> 00:41:34,000
tapi ternyata C memungkinkan kita menyederhanakan ini.

746
00:41:34,000 --> 00:41:40,000
Alih-alih menulis (* anita), kita malah bisa hanya menulis anita-> n,

747
00:41:40,000 --> 00:41:45,000
dan itu hal yang sama persis secara fungsional, tapi itu jauh lebih intuitif,

748
00:41:45,000 --> 00:41:48,000
dan itu jauh lebih konsisten dengan gambar yang kita telah menggambar

749
00:41:48,000 --> 00:41:50,000
selama ini menggunakan panah.

750
00:41:50,000 --> 00:41:57,000
>> Terakhir, apa yang perlu kita lakukan di akhir program ini?

751
00:41:57,000 --> 00:42:00,000
Ada satu baris kode yang tersisa.

752
00:42:00,000 --> 00:42:02,000
Kembali apa?

753
00:42:02,000 --> 00:42:05,000
Salah, karena jika kita melewati keseluruhan sementara loop

754
00:42:05,000 --> 00:42:10,000
dan Anita adalah, pada kenyataannya, nol, itu berarti dia pergi semua jalan ke akhir daftar

755
00:42:10,000 --> 00:42:12,000
di mana dia menunjuk-siapa namamu lagi?

756
00:42:12,000 --> 00:42:15,000
Ari >> Ari. Ini tangan kiri, yang adalah null.

757
00:42:15,000 --> 00:42:18,000
Anita sekarang nol, dan aku sadar kau hanya berdiri di sini canggung dalam limbo

758
00:42:18,000 --> 00:42:21,000
karena aku pergi pada monolog di sini,

759
00:42:21,000 --> 00:42:23,000
namun kami akan melibatkan Anda lagi hanya dalam beberapa saat.

760
00:42:23,000 --> 00:42:27,000
Anita nol pada titik dalam cerita, sehingga loop sementara berakhir,

761
00:42:27,000 --> 00:42:30,000
dan kami harus kembali palsu karena jika dia mendapat semua jalan ke pointer nol Ari

762
00:42:30,000 --> 00:42:34,000
maka tidak ada nomor yang dia mencari dalam daftar.

763
00:42:34,000 --> 00:42:39,000
Kita dapat membersihkan ini juga, tapi ini adalah implementasi yang cukup baik maka

764
00:42:39,000 --> 00:42:43,000
dari fungsi traversal, menemukan fungsi untuk linked list.

765
00:42:43,000 --> 00:42:48,000
Ini masih pencarian linear, tapi tidak sesederhana + + pointer

766
00:42:48,000 --> 00:42:52,000
atau + + variabel i karena sekarang kita tidak bisa menebak

767
00:42:52,000 --> 00:42:54,000
di mana masing-masing node dalam memori.

768
00:42:54,000 --> 00:42:57,000
Kami harus benar-benar mengikuti jejak remah roti atau, lebih khusus,

769
00:42:57,000 --> 00:43:00,000
pointer, untuk mendapatkan dari satu node ke yang lain.

770
00:43:00,000 --> 00:43:02,000
>> Sekarang mari kita coba satu sama lain. Anita, apakah Anda ingin kembali ke sini?

771
00:43:02,000 --> 00:43:06,000
Mengapa kita tidak pergi ke depan dan mengalokasikan satu orang lainnya dari para penonton?

772
00:43:06,000 --> 00:43:08,000
Malloc-siapa namamu? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca telah malloced dari penonton,

774
00:43:10,000 --> 00:43:13,000
dan dia sekarang menyimpan nomor 55.

775
00:43:13,000 --> 00:43:17,000
Dan tujuan yang ada sekarang adalah untuk Anita untuk menyisipkan

776
00:43:17,000 --> 00:43:22,000
Rebecca ke linked list di sini di tempat yang sesuai.

777
00:43:22,000 --> 00:43:24,000
Ayo ke sini sebentar.

778
00:43:24,000 --> 00:43:28,000
Saya telah melakukan sesuatu seperti ini.

779
00:43:28,000 --> 00:43:32,000
Saya telah melakukan * simpul. Dan siapa namamu lagi?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, oke.

781
00:43:34,000 --> 00:43:41,000
Rebecca mendapat malloc (sizeof (node)).

782
00:43:41,000 --> 00:43:44,000
Sama seperti kita telah dialokasikan hal-hal seperti siswa dan yang lainnya di masa lalu,

783
00:43:44,000 --> 00:43:46,000
kita perlu ukuran dari node, jadi sekarang Rebecca

784
00:43:46,000 --> 00:43:49,000
menunjuk pada apa?

785
00:43:49,000 --> 00:43:52,000
Rebecca memiliki dua bidang di dalam dirinya, salah satunya adalah 55.

786
00:43:52,000 --> 00:43:55,000
Mari kita lakukan apa, rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Tapi kemudian rebecca-> berikutnya harus-seperti sekarang, tangannya adalah jenis yang tahu?

788
00:44:00,000 --> 00:44:03,000
Ini menunjuk pada beberapa nilai sampah, jadi mengapa tidak untuk mengukur baik

789
00:44:03,000 --> 00:44:07,000
setidaknya kita melakukan ini sehingga tangan kiri sekarang di sisinya.

790
00:44:07,000 --> 00:44:09,000
Sekarang Anita, mengambilnya dari sini.

791
00:44:09,000 --> 00:44:11,000
Anda memiliki Rebecca yang telah dialokasikan.

792
00:44:11,000 --> 00:44:20,000
Pergi ke depan dan menemukan di mana kita harus meletakkan Rebecca.

793
00:44:20,000 --> 00:44:25,000
Baik, sangat baik.

794
00:44:25,000 --> 00:44:28,000
Oke, baik, dan sekarang kami membutuhkan anda untuk memberikan sedikit arahan,

795
00:44:28,000 --> 00:44:30,000
sehingga Anda telah mencapai Ari.

796
00:44:30,000 --> 00:44:33,000
Tangan kirinya adalah null, tapi Rebecca jelas milik ke kanan,

797
00:44:33,000 --> 00:44:36,000
jadi bagaimana kita harus mengubah ini linked list

798
00:44:36,000 --> 00:44:38,000
dalam rangka untuk memasukkan Rebecca ke tempat yang tepat?

799
00:44:38,000 --> 00:44:42,000
Jika Anda benar-benar bisa menggerakkan tangan kiri masyarakat sekitar yang diperlukan,

800
00:44:42,000 --> 00:44:48,000
kami akan memperbaiki masalah itu.

801
00:44:48,000 --> 00:44:52,000
Oke, baik, dan sementara itu, tangan kiri Rebecca sekarang di sisinya.

802
00:44:52,000 --> 00:44:54,000
>> Itu terlalu mudah.

803
00:44:54,000 --> 00:44:57,000
Mari kita coba mengalokasikan-kita hampir selesai, 20.

804
00:44:57,000 --> 00:44:59,000
Oke, ayo naik.

805
00:44:59,000 --> 00:45:04,000
20 telah dialokasikan, jadi biarkan aku pergi ke depan dan berkata lagi di sini

806
00:45:04,000 --> 00:45:07,000
baru saja kita lakukan saad simpul *.

807
00:45:07,000 --> 00:45:11,000
Kami memiliki malloc (sizeof (node)).

808
00:45:11,000 --> 00:45:16,000
Kami kemudian melakukan sintaks yang tepat sama seperti yang kita lakukan sebelumnya selama 20,

809
00:45:16,000 --> 00:45:20,000
dan saya akan melakukan NULL berikutnya =, dan sekarang terserah kepada Anita

810
00:45:20,000 --> 00:45:23,000
untuk memasukkan Anda ke dalam linked list, jika Anda bisa memainkan peran yang sama persis.

811
00:45:23,000 --> 00:45:30,000
Jalankan.

812
00:45:30,000 --> 00:45:32,000
Oke, baik.

813
00:45:32,000 --> 00:45:38,000
Sekarang pikirkan baik-baik sebelum Anda mulai bergerak tangan kiri sekitar.

814
00:45:38,000 --> 00:45:46,000
Anda sejauh mendapat peran paling canggung saat ini.

815
00:45:46,000 --> 00:45:59,000
Yang tangan harus dipindahkan terlebih dahulu?

816
00:45:59,000 --> 00:46:02,000
Oke, tunggu, aku mendengar beberapa tidak ada itu.

817
00:46:02,000 --> 00:46:07,000
Jika beberapa orang sopan ingin membantu mengatasi situasi yang canggung di sini.

818
00:46:07,000 --> 00:46:11,000
Tangan kiri yang harus diperbarui pertama mungkin? Ya.

819
00:46:11,000 --> 00:46:13,000
[Mahasiswa] itu Saad.

820
00:46:13,000 --> 00:46:15,000
Oke, itu Saad, mengapa, meskipun?

821
00:46:15,000 --> 00:46:17,000
[Respon siswa tidak terdengar]

822
00:46:17,000 --> 00:46:19,000
Baik, karena jika kita bergerak-siapa namamu? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, jika kita menggerakkan tangannya terlebih dahulu turun ke nol,

824
00:46:22,000 --> 00:46:25,000
sekarang kita telah benar-benar yatim empat orang di daftar ini

825
00:46:25,000 --> 00:46:29,000
karena ia adalah satu-satunya menunjuk Ramon dan semua orang ke kiri,

826
00:46:29,000 --> 00:46:31,000
sehingga memperbarui pointer yang pertama adalah buruk.

827
00:46:31,000 --> 00:46:33,000
Mari kita batalkan itu.

828
00:46:33,000 --> 00:46:37,000
Baik, dan sekarang pergi ke depan dan menggerakkan tangan kiri tepat menunjuk Ramon.

829
00:46:37,000 --> 00:46:39,000
Ini terasa berlebihan sedikit.

830
00:46:39,000 --> 00:46:41,000
Sekarang ada dua orang menunjuk Ramon, tapi itu baik-baik saja

831
00:46:41,000 --> 00:46:43,000
karena sekarang bagaimana lagi kita memperbarui daftar?

832
00:46:43,000 --> 00:46:48,000
Apa sisi lain harus bergerak?

833
00:46:48,000 --> 00:46:53,000
Sangat baik, kami sekarang memiliki kehilangan memori apapun?

834
00:46:53,000 --> 00:46:57,000
Tidak, begitu baik, mari kita lihat apakah kita tidak dapat mematahkan ini sekali lagi.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing terakhir kalinya, nomor 5.

836
00:47:00,000 --> 00:47:04,000
Semua jalan di belakang, datang pada turun.

837
00:47:04,000 --> 00:47:08,000
Ini sangat menarik.

838
00:47:08,000 --> 00:47:15,000
[Tepuk tangan]

839
00:47:15,000 --> 00:47:17,000
Siapa nama Anda? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, oke, Anda malloced sebagai nomor 5.

841
00:47:19,000 --> 00:47:23,000
Kami baru saja dieksekusi kode yang hampir identik dengan ini

842
00:47:23,000 --> 00:47:26,000
hanya dengan nama yang berbeda.

843
00:47:26,000 --> 00:47:28,000
Sangat baik.

844
00:47:28,000 --> 00:47:38,000
Sekarang, Anita, keberuntungan memasukkan nomor 5 ke dalam daftar sekarang.

845
00:47:38,000 --> 00:47:43,000
Baik, dan?

846
00:47:43,000 --> 00:47:47,000
Sangat baik, jadi ini benar-benar ketiga dari tiga total kasus.

847
00:47:47,000 --> 00:47:49,000
Kami pertama kali punya seseorang di akhir, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Kami kemudian memiliki seseorang di tengah.

849
00:47:51,000 --> 00:47:53,000
Sekarang kita memiliki seseorang di awal, dan dalam contoh ini,

850
00:47:53,000 --> 00:47:56,000
sekarang kita harus memperbarui Lucas untuk pertama kalinya

851
00:47:56,000 --> 00:48:00,000
karena elemen pertama dalam daftar sekarang harus menunjuk pada node baru,

852
00:48:00,000 --> 00:48:03,000
yang, pada gilirannya, menunjuk pada jumlah node 9.

853
00:48:03,000 --> 00:48:06,000
>> Ini adalah demonstrasi yang sangat canggung, aku yakin,

854
00:48:06,000 --> 00:48:08,000
sehingga tepuk tangan meriah untuk orang-orang jika Anda bisa.

855
00:48:08,000 --> 00:48:11,000
Nicely done.

856
00:48:11,000 --> 00:48:17,000
Itu saja. Anda dapat menyimpan potongan kertas Anda sebagai memori kecil.

857
00:48:17,000 --> 00:48:22,000
Ternyata bahwa melakukan hal ini dalam kode

858
00:48:22,000 --> 00:48:26,000
tidak sesederhana hanya bergerak tangan di sekitar

859
00:48:26,000 --> 00:48:28,000
dan menunjuk pointer pada hal yang berbeda.

860
00:48:28,000 --> 00:48:31,000
Tapi menyadari bahwa ketika tiba saatnya untuk melaksanakan sesuatu seperti

861
00:48:31,000 --> 00:48:34,000
linked list atau varian dari itu jika Anda benar-benar fokus pada

862
00:48:34,000 --> 00:48:38,000
ini dasar fundamental, gigitan-ukuran masalah yang saya harus mencari tahu,

863
00:48:38,000 --> 00:48:43,000
apakah ini tangan atau tangan ini, menyadari bahwa apa yang dinyatakan sebuah program yang cukup kompleks

864
00:48:43,000 --> 00:48:47,000
dapat, pada kenyataannya, dikurangi menjadi blok bangunan yang cukup sederhana seperti ini.

865
00:48:47,000 --> 00:48:51,000
>> Mari kita mengambil hal-hal ke arah yang lebih canggih masih.

866
00:48:51,000 --> 00:48:53,000
Kami sekarang memiliki gagasan linked list.

867
00:48:53,000 --> 00:48:57,000
Kami juga memiliki-berkat usulan kembali ke sana-daftar ganda terkait,

868
00:48:57,000 --> 00:49:01,000
yang terlihat hampir sama, tapi sekarang kita memiliki dua pointer dalam struct

869
00:49:01,000 --> 00:49:05,000
bukan satu, dan kita mungkin bisa menyebut mereka pointer sebelumnya dan berikutnya

870
00:49:05,000 --> 00:49:08,000
atau kiri atau kanan, tetapi kita, pada kenyataannya, membutuhkan dua dari mereka.

871
00:49:08,000 --> 00:49:10,000
Kode akan menjadi sedikit lebih terlibat.

872
00:49:10,000 --> 00:49:12,000
Anita akan harus melakukan pekerjaan lebih lanjut di sini di atas panggung.

873
00:49:12,000 --> 00:49:15,000
Tapi kita pasti bisa menerapkan semacam struktur.

874
00:49:15,000 --> 00:49:19,000
Dalam hal waktu berjalan, meskipun, apa yang akan menjadi waktu berjalan

875
00:49:19,000 --> 00:49:24,000
Anita untuk menemukan a n nomor dalam linked list sekarang?

876
00:49:24,000 --> 00:49:27,000
O masih besar n, jadi tidak lebih baik daripada pencarian linear.

877
00:49:27,000 --> 00:49:29,000
Kita tidak bisa melakukan pencarian biner, meskipun, lagi.

878
00:49:29,000 --> 00:49:34,000
Mengapa bahwa kasus tersebut? Anda tidak bisa melompat-lompat.

879
00:49:34,000 --> 00:49:36,000
Meskipun kita jelas melihat semua manusia di atas panggung,

880
00:49:36,000 --> 00:49:39,000
Anita dan bisa eyeballed itu dan berkata, "Inilah tengah daftar,"

881
00:49:39,000 --> 00:49:42,000
dia tidak akan tahu bahwa jika dia adalah program komputer

882
00:49:42,000 --> 00:49:47,000
karena satu-satunya dia harus kait pada pada awal skenario

883
00:49:47,000 --> 00:49:50,000
adalah Lucas, yang merupakan pointer pertama.

884
00:49:50,000 --> 00:49:53,000
Dia tentu akan harus mengikuti link tersebut,

885
00:49:53,000 --> 00:49:56,000
menghitung cara sampai dia menemukan kira-kira tengah,

886
00:49:56,000 --> 00:49:58,000
dan bahkan kemudian, dia tidak akan tahu kapan dia mencapai tengah

887
00:49:58,000 --> 00:50:01,000
kecuali dia pergi sepanjang jalan sampai akhir untuk mengetahui berapa banyak ada,

888
00:50:01,000 --> 00:50:05,000
maka backtracks, dan itu juga akan sulit kecuali jika Anda memiliki

889
00:50:05,000 --> 00:50:07,000
daftar ganda terkait dari beberapa macam.

890
00:50:07,000 --> 00:50:10,000
>> Memecahkan beberapa masalah saat ini, tapi memperkenalkan orang lain.

891
00:50:10,000 --> 00:50:12,000
Bagaimana struktur data yang berbeda sama sekali?

892
00:50:12,000 --> 00:50:15,000
Ini adalah foto dari nampan di Mather House,

893
00:50:15,000 --> 00:50:19,000
dan dalam kasus ini, kami memiliki struktur data kami juga jenis sudah bicarakan.

894
00:50:19,000 --> 00:50:22,000
Kami berbicara tentang tumpukan dalam konteks memori,

895
00:50:22,000 --> 00:50:26,000
dan itu semacam sengaja bernama karena tumpukan dalam hal memori

896
00:50:26,000 --> 00:50:31,000
secara efektif struktur data yang memiliki lebih banyak barang dan lebih berlapis-lapis di atasnya.

897
00:50:31,000 --> 00:50:35,000
Tetapi hal menarik tentang stack, seperti yang terjadi dalam kenyataan,

898
00:50:35,000 --> 00:50:38,000
adalah bahwa itu adalah jenis khusus dari struktur data.

899
00:50:38,000 --> 00:50:42,000
Ini adalah struktur data dimana elemen pertama dalam

900
00:50:42,000 --> 00:50:46,000
adalah elemen terakhir keluar.

901
00:50:46,000 --> 00:50:50,000
Jika Anda adalah baki pertama untuk diletakkan ke dalam stack,

902
00:50:50,000 --> 00:50:53,000
Anda akan menjadi sayangnya baki terakhir yang diambil dari tumpukan,

903
00:50:53,000 --> 00:50:55,000
dan itu tidak selalu hal yang baik.

904
00:50:55,000 --> 00:50:58,000
Sebaliknya, Anda dapat berpikir tentang hal sebaliknya,

905
00:50:58,000 --> 00:51:02,000
yang terakhir dalam adalah keluar pertama.

906
00:51:02,000 --> 00:51:05,000
>> Sekarang, apakah ada skenario datang ke pikiran di mana memiliki setumpuk

907
00:51:05,000 --> 00:51:08,000
struktur data di mana Anda memiliki properti yang

908
00:51:08,000 --> 00:51:13,000
yang terakhir, keluar pertama, sebenarnya menarik?

909
00:51:13,000 --> 00:51:16,000
Apakah itu hal yang baik? Apakah itu hal yang buruk?

910
00:51:16,000 --> 00:51:19,000
Ini jelas merupakan suatu hal yang buruk jika nampan tidak semua identik

911
00:51:19,000 --> 00:51:21,000
dan mereka semua warna yang berbeda khusus atau entah apa lagi,

912
00:51:21,000 --> 00:51:24,000
dan warna yang Anda inginkan adalah semua jalan di bagian bawah.

913
00:51:24,000 --> 00:51:26,000
Tentu saja, Anda tidak bisa mendapatkan bahwa tanpa usaha yang besar.

914
00:51:26,000 --> 00:51:28,000
Anda harus mulai dari atas dan bekerja dengan cara Anda ke bawah.

915
00:51:28,000 --> 00:51:31,000
Demikian pula, bagaimana jika Anda adalah salah satu dari anak-anak ini fan

916
00:51:31,000 --> 00:51:34,000
yang menunggu sepanjang malam berusaha untuk mendapatkan iPhone dan berbaris

917
00:51:34,000 --> 00:51:36,000
di tempat seperti ini?

918
00:51:36,000 --> 00:51:40,000
Bukankah lebih baik jika Apple store

919
00:51:40,000 --> 00:51:42,000
adalah struktur data stack?

920
00:51:42,000 --> 00:51:44,000
Yay? Nay?

921
00:51:44,000 --> 00:51:47,000
Ini hanya baik untuk orang-orang yang muncul di menit terakhir

922
00:51:47,000 --> 00:51:50,000
dan kemudian mendapatkan dipetik dari antrian.

923
00:51:50,000 --> 00:51:52,000
Dan pada kenyataannya, fakta bahwa aku begitu ingin mengatakan antrian

924
00:51:52,000 --> 00:51:56,000
sebenarnya konsisten dengan apa yang kita sebut semacam ini struktur data,

925
00:51:56,000 --> 00:51:59,000
satu kenyataan dimana urutan tidak peduli,

926
00:51:59,000 --> 00:52:02,000
dan Anda ingin yang pertama untuk menjadi yang pertama keluar

927
00:52:02,000 --> 00:52:04,000
jika hanya demi keadilan manusia.

928
00:52:04,000 --> 00:52:07,000
Kita umumnya akan menyebut bahwa struktur data antrian.

929
00:52:07,000 --> 00:52:11,000
>> Ternyata selain daftar terhubung, kita dapat mulai menggunakan ide-ide dasar yang sama

930
00:52:11,000 --> 00:52:15,000
dan mulai menciptakan jenis baru dan berbeda dari solusi untuk masalah.

931
00:52:15,000 --> 00:52:19,000
Misalnya, dalam kasus tumpukan, kita bisa mewakili stack

932
00:52:19,000 --> 00:52:22,000
menggunakan struktur data seperti ini, saya akan mengusulkan.

933
00:52:22,000 --> 00:52:26,000
Dalam hal ini, saya telah menyatakan struct, dan saya sudah mengatakan dalam struktur ini

934
00:52:26,000 --> 00:52:30,000
adalah array angka dan kemudian ukuran yang disebut variabel,

935
00:52:30,000 --> 00:52:33,000
dan saya akan menelepon hal ini stack.

936
00:52:33,000 --> 00:52:35,000
Sekarang, mengapa hal ini benar-benar bekerja?

937
00:52:35,000 --> 00:52:43,000
Dalam kasus stack, aku bisa menggambar efektif ini pada layar sebagai array.

938
00:52:43,000 --> 00:52:47,000
Berikut ini adalah tumpukan saya. Mereka adalah nomor saya.

939
00:52:47,000 --> 00:52:50,000
Dan kita akan menarik mereka karena hal ini, ini, ini, ini, ini.

940
00:52:50,000 --> 00:52:53,000
Dan kemudian saya memiliki beberapa anggota data lain di sini,

941
00:52:53,000 --> 00:52:58,000
yang disebut ukuran, jadi ini adalah ukuran, dan ini adalah angka,

942
00:52:58,000 --> 00:53:02,000
dan kolektif, iPad penuh di sini merupakan salah satu struktur tumpukan.

943
00:53:02,000 --> 00:53:07,000
Sekarang, secara default, ukuran yang mungkin harus diinisialisasi ke 0,

944
00:53:07,000 --> 00:53:11,000
dan apa yang ada di dalamnya dari array nomor awalnya

945
00:53:11,000 --> 00:53:14,000
ketika saya pertama kali mengalokasikan array?

946
00:53:14,000 --> 00:53:16,000
Sampah. Siapa yang tahu? Dan itu tidak benar-benar peduli.

947
00:53:16,000 --> 00:53:20,000
Tidak masalah jika ini adalah 1, 2, 3, 4, 5, benar-benar acak

948
00:53:20,000 --> 00:53:25,000
oleh nasib buruk yang tersimpan dalam struktur saya karena selama saya tahu bahwa ukuran tumpukan

949
00:53:25,000 --> 00:53:29,000
adalah 0, maka saya tahu pemrograman, tidak melihat salah satu elemen dalam array.

950
00:53:29,000 --> 00:53:31,000
Tidak peduli apa yang ada.

951
00:53:31,000 --> 00:53:34,000
Jangan melihat mereka, seperti yang akan implikasi dari ukuran 0.

952
00:53:34,000 --> 00:53:38,000
>> Tapi rasa sekarang aku pergi ke depan dan memasukkan sesuatu ke dalam stack.

953
00:53:38,000 --> 00:53:42,000
Saya ingin memasukkan nomor 5, jadi saya memasukkan nomor 5 di sini,

954
00:53:42,000 --> 00:53:45,000
dan kemudian apa yang harus saya meletakkan di sini?

955
00:53:45,000 --> 00:53:48,000
Sekarang aku benar-benar akan meletakkan 1 untuk ukuran,

956
00:53:48,000 --> 00:53:50,000
dan sekarang tumpukan adalah ukuran 1.

957
00:53:50,000 --> 00:53:53,000
Bagaimana jika saya pergi ke depan dan masukkan nomor, katakanlah, 7 berikutnya?

958
00:53:53,000 --> 00:53:57,000
Hal ini kemudian akan diperbarui untuk 2, dan kemudian kita akan melakukan 9,

959
00:53:57,000 --> 00:54:02,000
dan kemudian ini akan diperbarui untuk 3.

960
00:54:02,000 --> 00:54:05,000
Tapi fitur menarik sekarang dari tumpukan ini adalah bahwa

961
00:54:05,000 --> 00:54:09,000
Aku harus menghapus elemen yang jika saya ingin pop

962
00:54:09,000 --> 00:54:12,000
sesuatu dari tumpukan, sehingga untuk berbicara?

963
00:54:12,000 --> 00:54:14,000
9 akan menjadi hal pertama untuk pergi.

964
00:54:14,000 --> 00:54:18,000
Bagaimana seharusnya gambar berubah jika saya ingin pop elemen dari tumpukan,

965
00:54:18,000 --> 00:54:20,000
banyak seperti nampan di Mather?

966
00:54:20,000 --> 00:54:22,000
Ya >> [Siswa] Ukuran Set ke 2..

967
00:54:22,000 --> 00:54:27,000
Tepat, semua saya lakukan adalah mengatur ukuran 2, dan apa yang harus saya lakukan dengan array?

968
00:54:27,000 --> 00:54:29,000
Saya tidak perlu melakukan apa-apa.

969
00:54:29,000 --> 00:54:32,000
Aku bisa, hanya untuk menjadi anal, menempatkan 0 ada atau -1 atau sesuatu untuk menandakan

970
00:54:32,000 --> 00:54:34,000
bahwa ini bukan nilai yang legit, tapi itu tidak masalah karena

971
00:54:34,000 --> 00:54:37,000
Saya dapat merekam luar dari array itu sendiri berapa lama

972
00:54:37,000 --> 00:54:41,000
sehingga saya tahu hanya melihat dua elemen pertama dalam array ini.

973
00:54:41,000 --> 00:54:47,000
Sekarang, jika saya pergi dan menambahkan nomor 8 ke array ini, bagaimana mengubah gambar selanjutnya?

974
00:54:47,000 --> 00:54:50,000
Ini menjadi 8, dan ini menjadi 3.

975
00:54:50,000 --> 00:54:52,000
Aku memotong beberapa sudut di sini.

976
00:54:52,000 --> 00:54:56,000
Sekarang kita memiliki 5, 7, 8, dan kami sudah kembali ke ukuran 3.

977
00:54:56,000 --> 00:54:58,000
Ini sangat sederhana untuk menerapkan,

978
00:54:58,000 --> 00:55:06,000
tetapi ketika kita akan menyesali keputusan ini desain?

979
00:55:06,000 --> 00:55:09,000
Ketika melakukan hal-hal mulai pergi sangat, sangat salah? Ya.

980
00:55:09,000 --> 00:55:11,000
[Respon siswa tidak terdengar]

981
00:55:11,000 --> 00:55:13,000
Bila Anda ingin kembali dan mendapatkan elemen pertama Anda meletakkan masuk

982
00:55:13,000 --> 00:55:18,000
>> Ternyata di sini meskipun stack adalah array di bawah tenda,

983
00:55:18,000 --> 00:55:21,000
struktur data ini kita sudah mulai berbicara tentang juga umumnya dikenal sebagai

984
00:55:21,000 --> 00:55:25,000
abstrak struktur data dimana bagaimana mereka diimplementasikan

985
00:55:25,000 --> 00:55:27,000
benar-benar selain titik.

986
00:55:27,000 --> 00:55:31,000
Sebuah struktur data seperti tumpukan yang seharusnya untuk menambahkan dukungan

987
00:55:31,000 --> 00:55:35,000
operasi seperti push, yang mendorong baki ke dalam stack,

988
00:55:35,000 --> 00:55:39,000
dan pop, yang menghilangkan elemen dari tumpukan, dan hanya itu.

989
00:55:39,000 --> 00:55:43,000
Jika Anda adalah untuk men-download kode orang lain yang sudah dilaksanakan

990
00:55:43,000 --> 00:55:46,000
Hal ini disebut stack, orang itu akan ditulis

991
00:55:46,000 --> 00:55:49,000
hanya dua fungsi untuk Anda, mendorong dan pop, yang satu-satunya tujuan dalam hidup

992
00:55:49,000 --> 00:55:51,000
akan melakukan hal itu.

993
00:55:51,000 --> 00:55:54,000
Anda atau dia yang melaksanakan program yang

994
00:55:54,000 --> 00:55:58,000
akan menjadi sepenuhnya satu untuk memutuskan bagaimana menerapkan

995
00:55:58,000 --> 00:56:00,000
semantik mendorong dan muncul di bawah tenda

996
00:56:00,000 --> 00:56:03,000
atau fungsi mendorong dan muncul.

997
00:56:03,000 --> 00:56:07,000
Dan aku telah membuat keputusan yang agak rabun sini

998
00:56:07,000 --> 00:56:10,000
dengan menerapkan tumpukan saya dengan struktur data sederhana mengapa?

999
00:56:10,000 --> 00:56:12,000
Ketika hal ini istirahat struktur data?

1000
00:56:12,000 --> 00:56:18,000
Pada titik manakah saya harus kembali kesalahan ketika pengguna memanggil mendorong, misalnya?

1001
00:56:18,000 --> 00:56:20,000
[Siswa] Jika tidak ada lebih banyak ruang.

1002
00:56:20,000 --> 00:56:23,000
Tepat, jika ada ruang lagi, jika saya sudah melebihi kapasitas,

1003
00:56:23,000 --> 00:56:27,000
yang semua topi karena menunjukkan bahwa itu semacam konstanta global.

1004
00:56:27,000 --> 00:56:30,000
Nah, maka aku hanya akan harus mengatakan, "Maaf, saya tidak dapat mendorong nilai lain

1005
00:56:30,000 --> 00:56:32,000
ke stack, "banyak seperti di Mather.

1006
00:56:32,000 --> 00:56:36,000
>> Pada titik tertentu, mereka akan memukul bagian atas lemari kecil itu.

1007
00:56:36,000 --> 00:56:39,000
Tidak ada lebih banyak ruang atau kapasitas dalam stack, di mana titik ada beberapa jenis kesalahan.

1008
00:56:39,000 --> 00:56:42,000
Mereka harus meletakkan elemen di tempat lain, nampan tempat lain,

1009
00:56:42,000 --> 00:56:44,000
atau tidak sama sekali.

1010
00:56:44,000 --> 00:56:47,000
Sekarang, dengan antrian, kita bisa menerapkannya sedikit berbeda.

1011
00:56:47,000 --> 00:56:50,000
Antrian adalah sedikit berbeda dalam bahwa di bawah tenda, dapat dilaksanakan

1012
00:56:50,000 --> 00:56:54,000
sebagai sebuah array, tapi mengapa, dalam kasus ini, saya mengusulkan

1013
00:56:54,000 --> 00:56:59,000
juga memiliki unsur kepala mewakili kepala daftar,

1014
00:56:59,000 --> 00:57:06,000
depan daftar, orang pertama dalam antrean di toko Apple, selain ukurannya?

1015
00:57:06,000 --> 00:57:14,000
Mengapa saya perlu sepotong tambahan data di sini?

1016
00:57:14,000 --> 00:57:16,000
Pikirkan kembali apa angka adalah

1017
00:57:16,000 --> 00:57:18,000
jika saya sudah ditarik sebagai berikut.

1018
00:57:18,000 --> 00:57:21,000
Misalkan sekarang ini adalah antrian bukannya stack,

1019
00:57:21,000 --> 00:57:24,000
perbedaan menjadi-seperti antrian toko-Apple adil.

1020
00:57:24,000 --> 00:57:27,000
Orang pertama dalam antrean di awal daftar, nomor 5 dalam hal ini,

1021
00:57:27,000 --> 00:57:30,000
dia atau dia akan membiarkan ke toko pertama.

1022
00:57:30,000 --> 00:57:32,000
Mari kita lakukan itu.

1023
00:57:32,000 --> 00:57:35,000
Misalkan bahwa ini adalah keadaan antrian saya saat ini dalam waktu, dan sekarang toko Apple

1024
00:57:35,000 --> 00:57:39,000
membuka dan orang pertama, nomor 5, dipimpin ke toko.

1025
00:57:39,000 --> 00:57:43,000
Bagaimana cara mengubah gambar sekarang bahwa saya telah de-antri orang pertama

1026
00:57:43,000 --> 00:57:47,000
di garis depan?

1027
00:57:47,000 --> 00:57:50,000
Apa itu >> [Mahasiswa]? Mengubah antrian.

1028
00:57:50,000 --> 00:57:52,000
Mengubah kepala, sehingga 5 menghilang.

1029
00:57:52,000 --> 00:57:56,000
Pada kenyataannya, itu seolah-olah-cara terbaik untuk melakukan hal ini?

1030
00:57:56,000 --> 00:58:00,000
Pada kenyataannya, itu seolah-olah orang ini menghilang.

1031
00:58:00,000 --> 00:58:03,000
Apa yang akan dilakukan di nomor 7 toko yang sebenarnya?

1032
00:58:03,000 --> 00:58:05,000
Mereka akan mengambil langkah besar ke depan.

1033
00:58:05,000 --> 00:58:08,000
>> Tapi apa yang telah kita datang untuk menghargai ketika datang ke array

1034
00:58:08,000 --> 00:58:10,000
dan bergerak hal-hal di sekitar?

1035
00:58:10,000 --> 00:58:12,000
Itu semacam membuang-buang waktu Anda, kan?

1036
00:58:12,000 --> 00:58:16,000
Kenapa kau harus begitu anal untuk memiliki orang pertama

1037
00:58:16,000 --> 00:58:21,000
pada awal baris pada fisik awal sepotong memori?

1038
00:58:21,000 --> 00:58:23,000
Itu sama sekali tidak perlu. Kenapa?

1039
00:58:23,000 --> 00:58:26,000
Apa yang bisa saya hanya ingat bukan >> [respon siswa tidak terdengar]?

1040
00:58:26,000 --> 00:58:30,000
Tepat, saya hanya bisa mengingat dengan kepala anggota data tambahan

1041
00:58:30,000 --> 00:58:34,000
bahwa sekarang kepala daftar tidak lagi 0, yang itu beberapa saat yang lalu.

1042
00:58:34,000 --> 00:58:39,000
Sekarang sebenarnya nomor 1. Dengan cara ini, saya mendapatkan optimasi sedikit.

1043
00:58:39,000 --> 00:58:44,000
Hanya karena aku sudah de-antri seseorang dari garis pada awal baris di toko Apple

1044
00:58:44,000 --> 00:58:47,000
tidak berarti setiap orang harus bergeser, dimana recall adalah operasi linear.

1045
00:58:47,000 --> 00:58:50,000
Saya malah bisa menghabiskan waktu konstan hanya

1046
00:58:50,000 --> 00:58:53,000
dan mencapai kemudian respon lebih cepat.

1047
00:58:53,000 --> 00:58:56,000
Tapi harga saya membayar adalah apa untuk mendapatkan bahwa kinerja tambahan

1048
00:58:56,000 --> 00:58:58,000
dan tidak harus menggeser semua orang?

1049
00:58:58,000 --> 00:59:01,000
Ya >> [respon siswa tidak terdengar].

1050
00:59:01,000 --> 00:59:04,000
Dapat menambahkan lebih banyak orang, baik, masalah yang ortogonal

1051
00:59:04,000 --> 00:59:07,000
dengan fakta bahwa kita tidak bergeser orang di sekitar.

1052
00:59:07,000 --> 00:59:11,000
Ini masih array, jadi apakah atau tidak kita menggeser orang atau tidak-

1053
00:59:11,000 --> 00:59:13,000
oh, saya melihat apa yang Anda maksud, oke.

1054
00:59:13,000 --> 00:59:16,000
Sebenarnya, saya setuju dengan apa yang Anda katakan dalam sehingga hampir seolah-olah

1055
00:59:16,000 --> 00:59:19,000
kita sekarang tidak akan pernah menggunakan awal dari array ini lagi

1056
00:59:19,000 --> 00:59:22,000
karena jika saya menghapus 5, maka saya menghapus 7.

1057
00:59:22,000 --> 00:59:24,000
Tapi aku hanya menempatkan orang-orang ke kanan.

1058
00:59:24,000 --> 00:59:28,000
>> Rasanya seperti aku menyia-nyiakan ruang, dan akhirnya antrian saya hancur menjadi apa-apa,

1059
00:59:28,000 --> 00:59:31,000
jadi kami hanya bisa memiliki sampul orang,

1060
00:59:31,000 --> 00:59:35,000
dan kita bisa memikirkan array ini benar-benar sebagai semacam struktur melingkar,

1061
00:59:35,000 --> 00:59:38,000
tapi kita menggunakan apa yang operator di C untuk melakukan itu semacam sampul?

1062
00:59:38,000 --> 00:59:40,000
[Respon siswa terdengar] >> Operator modulo.

1063
00:59:40,000 --> 00:59:43,000
Ini akan menjadi sedikit mengganggu untuk memikirkan bagaimana Anda melakukannya sampul tersebut,

1064
00:59:43,000 --> 00:59:46,000
tapi kita bisa melakukannya, dan kita bisa mulai menempatkan orang pada apa yang digunakan untuk menjadi garis depan,

1065
00:59:46,000 --> 00:59:52,000
tapi kita hanya ingat dengan variabel kepala yang kepala sebenarnya garis sebenarnya.

1066
00:59:52,000 --> 00:59:57,000
Bagaimana jika, sebaliknya, tujuan kami pada akhirnya, meskipun,

1067
00:59:57,000 --> 01:00:00,000
adalah untuk mencari nomor, seperti yang kita lakukan di sini di atas panggung dengan Anita,

1068
01:00:00,000 --> 01:00:02,000
tapi kami benar-benar ingin yang terbaik dari semua dunia?

1069
01:00:02,000 --> 01:00:05,000
Kami ingin kecanggihan lebih dari array yang memungkinkan

1070
01:00:05,000 --> 01:00:09,000
karena kami ingin kemampuan untuk secara dinamis menumbuhkan struktur data.

1071
01:00:09,000 --> 01:00:12,000
Tapi kita tidak mau harus resor untuk sesuatu yang kita menunjukkan

1072
01:00:12,000 --> 01:00:15,000
dalam kuliah pertama adalah bukan merupakan algoritma optimal,

1073
01:00:15,000 --> 01:00:17,000
bahwa pencarian linear.

1074
01:00:17,000 --> 01:00:21,000
Ternyata bahwa Anda bisa, pada kenyataannya, mencapai

1075
01:00:21,000 --> 01:00:24,000
atau setidaknya dekat dengan waktu yang konstan, dimana seseorang seperti Anita,

1076
01:00:24,000 --> 01:00:27,000
jika dia mengkonfigurasi struktur data untuk tidak menjadi linked list,

1077
01:00:27,000 --> 01:00:30,000
tidak menjadi stack, tidak menjadi antrian, bisa, pada kenyataannya,

1078
01:00:30,000 --> 01:00:33,000
datang dengan struktur data yang memungkinkan dia untuk melihat hal-hal,

1079
01:00:33,000 --> 01:00:37,000
bahkan kata-kata, bukan hanya angka, dalam apa yang kita akan menelepon waktu yang konstan.

1080
01:00:37,000 --> 01:00:40,000
>> Dan pada kenyataannya, melihat ke depan, salah satu psets di kelas ini hampir selalu

1081
01:00:40,000 --> 01:00:43,000
pelaksanaan pemeriksa ejaan, dimana

1082
01:00:43,000 --> 01:00:46,000
kami memberikan lagi beberapa kata dalam bahasa Inggris 150.000 dan tujuannya adalah untuk

1083
01:00:46,000 --> 01:00:51,000
memuat mereka ke dalam memori dan cepat bisa menjawab pertanyaan-pertanyaan dalam bentuk

1084
01:00:51,000 --> 01:00:54,000
adalah kata ini dieja dengan benar?

1085
01:00:54,000 --> 01:00:58,000
Dan itu benar-benar akan mengisap jika Anda harus iterate melalui semua 150.000 kata untuk menjawab itu.

1086
01:00:58,000 --> 01:01:02,000
Tapi, pada kenyataannya, kita akan melihat bahwa kita dapat melakukannya dalam waktu yang sangat, sangat cepat.

1087
01:01:02,000 --> 01:01:06,000
Dan itu akan melibatkan sesuatu yang menerapkan disebut tabel hash,

1088
01:01:06,000 --> 01:01:09,000
dan meskipun pada pandangan pertama hal ini disebut tabel hash akan

1089
01:01:09,000 --> 01:01:12,000
mari kita mencapai waktu respon yang cepat Super,

1090
01:01:12,000 --> 01:01:18,000
ternyata memang ada masalah.

1091
01:01:18,000 --> 01:01:23,000
Ketika tiba saatnya untuk melaksanakan hal ini disebut-lagi, aku melakukannya lagi.

1092
01:01:23,000 --> 01:01:25,000
Saya satu-satunya di sini.

1093
01:01:25,000 --> 01:01:28,000
Ketika tiba saatnya untuk melaksanakan hal ini disebut tabel hash,

1094
01:01:28,000 --> 01:01:30,000
kita akan harus membuat keputusan.

1095
01:01:30,000 --> 01:01:32,000
Seberapa besar hal ini harus benar-benar menjadi?

1096
01:01:32,000 --> 01:01:36,000
Dan ketika kita mulai memasukkan ke nomor ini tabel hash,

1097
01:01:36,000 --> 01:01:38,000
bagaimana kita akan menyimpannya dalam sedemikian rupa

1098
01:01:38,000 --> 01:01:42,000
bahwa kita bisa mendapatkan mereka kembali secepat yang kita punya mereka di?

1099
01:01:42,000 --> 01:01:45,000
Tapi kita akan lihat sebelum panjang yang pertanyaan ini

1100
01:01:45,000 --> 01:01:48,000
ketika ulang tahun semua orang adalah di kelas akan cukup erat.

1101
01:01:48,000 --> 01:01:51,000
Ternyata bahwa di ruangan ini, kita punya beberapa ratus orang,

1102
01:01:51,000 --> 01:01:56,000
sehingga kemungkinan bahwa dua dari kita memiliki ulang tahun yang sama mungkin cukup tinggi.

1103
01:01:56,000 --> 01:01:58,000
Bagaimana jika hanya ada 40 dari kami di ruangan ini?

1104
01:01:58,000 --> 01:02:02,000
Apa kemungkinan dua orang memiliki ulang tahun yang sama?

1105
01:02:02,000 --> 01:02:04,000
[Siswa] Lebih dari 50%.

1106
01:02:04,000 --> 01:02:06,000
Ya, lebih dari 50%. Bahkan, aku bahkan membawa grafik.

1107
01:02:06,000 --> 01:02:08,000
Ternyata-dan ini benar-benar hanya menyelinap pratinjau-

1108
01:02:08,000 --> 01:02:12,000
jika hanya ada 58 dari kita di ruangan ini, kemungkinan 2 dari kami

1109
01:02:12,000 --> 01:02:16,000
memiliki ulang tahun yang sama adalah sangat tinggi, hampir 100%,

1110
01:02:16,000 --> 01:02:20,000
dan itu akan menyebabkan sejumlah besar terluka bagi kita pada hari Rabu.

1111
01:02:20,000 --> 01:02:24,000
>> Dengan mengatakan bahwa, mari kita menunda sini. Kami akan melihat Anda pada hari Rabu.

1112
01:02:24,000 --> 01:02:28,000
[Tepuk tangan]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]