1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Bagian 6: Kurang Nyaman]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Ini adalah CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Baiklah. Selamat datang ke bagian 6.

5
00:00:11,840 --> 00:00:14,690
Minggu ini, kita akan berbicara tentang struktur data dalam bagian,

6
00:00:14,690 --> 00:00:19,780
terutama karena masalah minggu ini ditetapkan pada spellr

7
00:00:19,780 --> 00:00:24,410
melakukan sejumlah eksplorasi struktur data yang berbeda.

8
00:00:24,410 --> 00:00:26,520
Ada banyak cara yang berbeda Anda dapat pergi dengan sejumlah masalah,

9
00:00:26,520 --> 00:00:31,570
dan struktur data yang Anda tahu tentang, hal-hal yang lebih keren yang dapat Anda lakukan.

10
00:00:31,570 --> 00:00:34,990
>> Jadi mari kita mulai. Pertama kita akan berbicara tentang tumpukan,

11
00:00:34,990 --> 00:00:37,530
tumpukan dan antrian struktur data yang akan kita bicarakan.

12
00:00:37,530 --> 00:00:40,560
Tumpukan dan antrian benar-benar membantu ketika kita mulai berbicara tentang grafik,

13
00:00:40,560 --> 00:00:44,390
yang kita tidak akan melakukan begitu banyak sekarang.

14
00:00:44,390 --> 00:00:52,820
Tapi mereka benar-benar baik untuk memahami salah satu struktur data yang besar fundamental CS.

15
00:00:52,820 --> 00:00:54,880
Deskripsi dalam spesifikasi sejumlah masalah,

16
00:00:54,880 --> 00:00:59,260
jika Anda menarik itu, berbicara tentang tumpukan sebagai mirip dengan

17
00:00:59,260 --> 00:01:05,239
tumpukan nampan makan yang Anda miliki di kantin di ruang makan

18
00:01:05,239 --> 00:01:09,680
di mana ketika staf makan datang dan menempatkan nampan makan keluar setelah mereka telah dibersihkan mereka,

19
00:01:09,680 --> 00:01:12,000
mereka stack mereka satu di atas yang lain.

20
00:01:12,000 --> 00:01:15,050
Dan kemudian ketika anak-anak datang untuk mendapatkan makanan,

21
00:01:15,050 --> 00:01:19,490
mereka menarik nampan off, pertama atas satu, kemudian yang di bawahnya, maka yang di bawah itu.

22
00:01:19,490 --> 00:01:25,190
Jadi, pada dasarnya, baki pertama bahwa staf makan meletakkan adalah yang terakhir yang akan diambil off.

23
00:01:25,190 --> 00:01:32,330
Yang terakhir bahwa staf makan memakai adalah yang pertama yang akan diambil off untuk makan malam.

24
00:01:32,330 --> 00:01:38,100
Dalam spec sejumlah masalah, yang Anda dapat men-download jika Anda belum melakukannya,

25
00:01:38,100 --> 00:01:46,730
kita berbicara tentang pemodelan stucture tumpukan data yang menggunakan jenis struct.

26
00:01:46,730 --> 00:01:51,070
>> Jadi apa yang kita punya di sini, ini mirip dengan apa yang disajikan dalam kuliah,

27
00:01:51,070 --> 00:01:58,120
kecuali dalam kuliah kita disajikan ini dengan ints sebagai lawan s * char.

28
00:01:58,120 --> 00:02:06,250
Ini akan menjadi tumpukan yang menyimpan apa?

29
00:02:06,250 --> 00:02:09,009
Daniel? Apa yang kita menyimpan dalam tumpukan ini?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Kami menyimpan string dalam tumpukan ini, tepatnya.

31
00:02:15,260 --> 00:02:20,950
Semua yang perlu Anda miliki untuk membuat stack adalah array

32
00:02:20,950 --> 00:02:23,920
dari kapasitas tertentu, yang dalam hal ini,

33
00:02:23,920 --> 00:02:28,020
kapasitas akan berada di semua topi karena konstan.

34
00:02:28,020 --> 00:02:36,340
Dan maka selain array, semua yang kita butuhkan untuk melacak adalah ukuran saat array.

35
00:02:36,340 --> 00:02:38,980
Satu hal yang perlu dicatat di sini bahwa agak dingin

36
00:02:38,980 --> 00:02:47,060
adalah bahwa kita sedang menciptakan struktur data yang ditumpuk di atas lain struktur data, array.

37
00:02:47,060 --> 00:02:50,110
Ada berbagai cara untuk mengimplementasikan tumpukan.

38
00:02:50,110 --> 00:02:54,250
Kami tidak akan melakukannya belum cukup, tapi mudah-mudahan setelah melakukan linked-list masalah,

39
00:02:54,250 --> 00:03:00,520
Anda akan melihat bagaimana Anda dapat dengan mudah menerapkan tumpukan di atas linked list juga.

40
00:03:00,520 --> 00:03:02,640
Tetapi untuk sekarang, kita akan tetap ke array.

41
00:03:02,640 --> 00:03:06,350
Jadi sekali lagi, semua yang kita butuhkan adalah array dan kita hanya perlu untuk melacak ukuran array.

42
00:03:06,350 --> 00:03:09,850
[Sam] Maaf, mengapa Anda mengatakan stack adalah di atas senar?

43
00:03:09,850 --> 00:03:13,440
Bagi saya rasanya seperti senar berada dalam stack.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Ya. Kami sedang menciptakan, kami mengambil array kita struktur data -

45
00:03:16,790 --> 00:03:22,130
itu pertanyaan yang bagus. Jadi pertanyaannya adalah mengapa, bagi orang-orang yang menonton secara online ini,

46
00:03:22,130 --> 00:03:24,140
mengapa kita mengatakan bahwa tumpukan di atas senar,

47
00:03:24,140 --> 00:03:27,990
karena di sini sepertinya senar berada di dalam stack?

48
00:03:27,990 --> 00:03:31,050
Yang benar-benar terjadi.

49
00:03:31,050 --> 00:03:34,660
Apa yang saya maksudkan adalah bahwa kita punya sebuah struktur data array.

50
00:03:34,660 --> 00:03:39,290
Kami punya sebuah array char * s, ini array dari string,

51
00:03:39,290 --> 00:03:45,300
dan kami akan menambahkan bahwa dalam rangka menciptakan struktur data yang ditumpuk.

52
00:03:45,300 --> 00:03:48,620
>> Jadi tumpukan adalah sedikit lebih kompleks daripada array.

53
00:03:48,620 --> 00:03:51,890
Kita bisa menggunakan array untuk membangun stack.

54
00:03:51,890 --> 00:03:55,810
Jadi, di sanalah kita mengatakan bahwa tumpukan dibangun di atas sebuah array.

55
00:03:55,810 --> 00:04:02,510
Demikian juga, seperti saya katakan sebelumnya, kita dapat membangun sebuah tumpukan di atas linked list.

56
00:04:02,510 --> 00:04:04,960
Alih-alih menggunakan array untuk memegang elemen kami,

57
00:04:04,960 --> 00:04:10,070
kita bisa menggunakan linked list untuk menahan unsur kami dan membangun tumpukan sekitar itu.

58
00:04:10,070 --> 00:04:12,420
Mari kita berjalan melalui beberapa contoh, melihat beberapa kode,

59
00:04:12,420 --> 00:04:14,960
untuk melihat apa yang sebenarnya terjadi di sini.

60
00:04:14,960 --> 00:04:23,400
Di sebelah kiri, saya telah dilemparkan ke bawah apa yang struct tumpukan akan terlihat seperti dalam memori

61
00:04:23,400 --> 00:04:28,330
jika kapasitas yang # didefinisikan sebagai empat.

62
00:04:28,330 --> 00:04:33,490
Kami punya empat elemen array char * kami.

63
00:04:33,490 --> 00:04:38,110
Kami punya string [0], string [1], string [2], string [3],

64
00:04:38,110 --> 00:04:43,800
dan kemudian bahwa ruang terakhir untuk bilangan bulat ukuran kami.

65
00:04:43,800 --> 00:04:46,270
Apakah ini masuk akal? Oke.

66
00:04:46,270 --> 00:04:48,790
Inilah yang terjadi jika apa yang saya lakukan di sebelah kanan,

67
00:04:48,790 --> 00:04:55,790
yang akan menjadi kode saya, adalah hanya menyatakan struct, struct ditumpuk disebut s.

68
00:04:55,790 --> 00:05:01,270
Ini adalah apa yang kita dapatkan. Hal ini meletakkan jejak di memori.

69
00:05:01,270 --> 00:05:05,590
Pertanyaan pertama di sini adalah apa isi dari struct stack?

70
00:05:05,590 --> 00:05:09,250
Sekarang mereka bukan apa-apa, tapi mereka tidak benar-benar apa-apa.

71
00:05:09,250 --> 00:05:13,300
Mereka ini jenis sampah. Kami tidak tahu apa yang ada di dalamnya.

72
00:05:13,300 --> 00:05:17,000
Ketika kita mendeklarasikan s tumpukan, kami hanya melempar yang turun di atas memori.

73
00:05:17,000 --> 00:05:19,840
Ini semacam seperti mendeklarasikan int i dan tidak menginisialisasi itu.

74
00:05:19,840 --> 00:05:21,730
Anda tidak tahu apa yang ada di sana. Anda dapat membaca apa yang ada di sana,

75
00:05:21,730 --> 00:05:27,690
tapi mungkin tidak super bermanfaat.

76
00:05:27,690 --> 00:05:32,680
Satu hal yang Anda ingin selalu ingat untuk lakukan adalah menginisialisasi apa saja yang perlu diinisialisasi.

77
00:05:32,680 --> 00:05:35,820
Dalam kasus ini, kita akan menginisialisasi ukuran menjadi nol,

78
00:05:35,820 --> 00:05:39,960
karena itu akan berubah menjadi sangat penting bagi kami.

79
00:05:39,960 --> 00:05:43,450
Kita bisa pergi ke depan dan menginisialisasi semua pointer, semua s * char,

80
00:05:43,450 --> 00:05:49,670
menjadi beberapa nilai dimengerti, mungkin nol.

81
00:05:49,670 --> 00:05:58,270
Tapi itu tidak benar-benar penting bahwa kita melakukan itu.

82
00:05:58,270 --> 00:06:04,200
>> Sekarang, dua operasi utama pada tumpukan adalah?

83
00:06:04,200 --> 00:06:07,610
Siapa saja ingat dari kuliah apa yang Anda lakukan dengan tumpukan? Ya?

84
00:06:07,610 --> 00:06:09,700
[Stella] Mendorong dan muncul? >> Tepat.

85
00:06:09,700 --> 00:06:13,810
Mendorong dan muncul adalah dua operasi utama pada tumpukan.

86
00:06:13,810 --> 00:06:17,060
Dan apa yang mendorong lakukan? >> Ini menempatkan sesuatu ke atas

87
00:06:17,060 --> 00:06:19,300
dari tumpukan, dan kemudian popping membawanya pergi.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Tepat. Jadi mendorong mendorong sesuatu di atas tumpukan.

89
00:06:23,150 --> 00:06:27,700
Ini seperti makan staf meletakkan nampan makan di atas meja.

90
00:06:27,700 --> 00:06:33,630
Dan muncul adalah mengambil nampan makan dari tumpukan.

91
00:06:33,630 --> 00:06:36,460
Mari kita berjalan melalui beberapa contoh dari apa yang terjadi

92
00:06:36,460 --> 00:06:39,720
ketika kita mendorong hal-hal ke dalam stack.

93
00:06:39,720 --> 00:06:45,110
Jika kita mendorong string 'halo' ke stack kami,

94
00:06:45,110 --> 00:06:49,760
ini adalah apa diagram kita akan terlihat seperti sekarang.

95
00:06:49,760 --> 00:06:53,410
Lihat apa yang terjadi?

96
00:06:53,410 --> 00:06:56,530
Kami mendorong ke elemen pertama dari array string kami

97
00:06:56,530 --> 00:07:01,420
dan kami menaikkan jumlah ukuran kami untuk menjadi 1.

98
00:07:01,420 --> 00:07:05,340
Jadi jika kita melihat perbedaan antara dua slide, di sini adalah 0, inilah sebelum push.

99
00:07:05,340 --> 00:07:08,690
Berikut adalah setelah push.

100
00:07:08,690 --> 00:07:13,460
Sebelum push, setelah push.

101
00:07:13,460 --> 00:07:16,860
Dan sekarang kita memiliki satu elemen dalam tumpukan kita.

102
00:07:16,860 --> 00:07:20,970
Ini adalah string "hello", dan hanya itu.

103
00:07:20,970 --> 00:07:24,440
Segala sesuatu yang lain dalam array, dalam array string kita, masih sampah.

104
00:07:24,440 --> 00:07:27,070
Kami belum diinisialisasi.

105
00:07:27,070 --> 00:07:29,410
Katakanlah kita mendorong string lain ke stack kami.

106
00:07:29,410 --> 00:07:32,210
Kita akan mendorong "dunia" pada saat ini.

107
00:07:32,210 --> 00:07:35,160
Sehingga Anda dapat melihat "dunia" di sini pergi di atas "halo",

108
00:07:35,160 --> 00:07:40,040
dan jumlah ukuran naik ke 2.

109
00:07:40,040 --> 00:07:44,520
Sekarang kita dapat mendorong "CS50", dan yang akan pergi di atas lagi.

110
00:07:44,520 --> 00:07:51,110
Jika kita kembali, Anda dapat melihat bagaimana kita mendorong hal-hal di atas tumpukan.

111
00:07:51,110 --> 00:07:53,320
Dan sekarang kita bisa pop.

112
00:07:53,320 --> 00:07:58,910
Ketika kita muncul sesuatu dari tumpukan, apa yang terjadi?

113
00:07:58,910 --> 00:08:01,540
Siapa saja melihat perbedaannya? Ini cukup halus.

114
00:08:01,540 --> 00:08:05,810
[Mahasiswa] Ukuran. >> Ya, ukuran berubah.

115
00:08:05,810 --> 00:08:09,040
>> Apa lagi yang akan Anda diharapkan untuk berubah?

116
00:08:09,040 --> 00:08:14,280
[Mahasiswa] The string juga. >> Kanan. String juga.

117
00:08:14,280 --> 00:08:17,110
Ternyata bahwa ketika Anda melakukannya dengan cara ini,

118
00:08:17,110 --> 00:08:21,960
karena kita tidak menyalin elemen ke dalam stack kami,

119
00:08:21,960 --> 00:08:24,670
kita sebenarnya tidak perlu melakukan apa-apa, kita hanya bisa menggunakan ukuran

120
00:08:24,670 --> 00:08:28,630
untuk melacak jumlah hal dalam array kita

121
00:08:28,630 --> 00:08:33,780
sehingga ketika kita pop lagi, lagi kita hanya akan memundurkan ukuran kami turun ke 1.

122
00:08:33,780 --> 00:08:39,440
Tidak perlu untuk benar-benar masuk dan menimpa apapun.

123
00:08:39,440 --> 00:08:41,710
Agak funky.

124
00:08:41,710 --> 00:08:46,520
Ternyata bahwa kita biasanya hanya meninggalkan hal-hal sendirian karena itu sedikit pekerjaan untuk kita lakukan.

125
00:08:46,520 --> 00:08:50,060
Jika kita tidak harus kembali dan menimpa sesuatu, lalu mengapa melakukannya?

126
00:08:50,060 --> 00:08:54,150
Jadi ketika kita pop off dua kali dari tumpukan, semua yang dilakukan adalah memundurkan ukuran beberapa kali.

127
00:08:54,150 --> 00:08:59,120
Dan lagi, ini hanya karena kita tidak menyalin sesuatu ke dalam stack kami.

128
00:08:59,120 --> 00:09:01,320
Ya? Silakan.

129
00:09:01,320 --> 00:09:04,460
[Mahasiswa, dipahami] >> Dan kemudian apa yang terjadi ketika Anda mendorong sesuatu lagi?

130
00:09:04,460 --> 00:09:08,570
Ketika Anda mendorong sesuatu lagi, mana pergi?

131
00:09:08,570 --> 00:09:12,390
Mana pergi, Basil? >> Ke string [1]? >> Kanan.

132
00:09:12,390 --> 00:09:14,530
Kenapa tidak bisa masuk ke string [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Karena lupa bahwa ada sesuatu dalam string [1] dan [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Tepat. Tumpukan kami, pada dasarnya, "lupa" bahwa itu berpegangan pada apa

135
00:09:24,040 --> 00:09:29,480
dalam string [1] atau string [2], jadi ketika kita menekan "woot",

136
00:09:29,480 --> 00:09:36,670
itu hanya menempatkan bahwa ke elemen pada string [1].

137
00:09:36,670 --> 00:09:41,590
Apakah ada pertanyaan tentang bagaimana ini bekerja, pada tingkat dasar?

138
00:09:41,590 --> 00:09:45,160
[Sam] Jadi ini tidak dinamis dengan cara apapun, dalam hal jumlah

139
00:09:45,160 --> 00:09:47,620
atau dalam hal ukuran stack?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Tepat. Ini adalah - intinya adalah bahwa ini bukan tumpukan dinamis growning.

141
00:09:56,750 --> 00:10:02,850
Ini adalah tumpukan yang dapat menampung, paling banyak, empat char * s, paling banyak empat hal.

142
00:10:02,850 --> 00:10:07,580
Jika kita mencoba dan mendorong hal yang kelima, apa yang Anda pikir seharusnya terjadi?

143
00:10:07,580 --> 00:10:11,870
[Mahasiswa, dipahami]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Tepat. Ada beberapa hal yang bisa terjadi.

145
00:10:14,600 --> 00:10:19,330
Ini mungkin bisa seg kesalahan, tergantung pada apa yang kita -

146
00:10:19,330 --> 00:10:22,530
bagaimana tepatnya kita menerapkan back-end.

147
00:10:22,530 --> 00:10:31,740
Ini bisa menimpa. Bisa memiliki buffer overflow yang kita bicarakan di kelas.

148
00:10:31,740 --> 00:10:35,240
Apa yang akan menjadi hal yang paling jelas yang mungkin ditimpa

149
00:10:35,240 --> 00:10:42,370
jika kita mencoba untuk mendorong hal ekstra pada tumpukan kita?

150
00:10:42,370 --> 00:10:44,550
Jadi Anda sebutkan buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Apa yang mungkin menjadi hal yang akan mendapatkan ditulis di atas atau diinjak-injak

152
00:10:47,870 --> 00:10:52,320
jika kita meluap dengan sengaja mencoba untuk mendorong hal ekstra?

153
00:10:52,320 --> 00:10:54,730
[Daniel, dipahami] Kemungkinan >>.

154
00:10:54,730 --> 00:10:58,440
Tapi awalnya, apa yang mungkin terjadi? Bagaimana jika kita mencoba untuk mendorong hal yang keempat?

155
00:10:58,440 --> 00:11:06,220
Ini mungkin menimpa ukuran, setidaknya dengan diagram memori yang kita punya.

156
00:11:06,220 --> 00:11:10,880
>> Dalam spesifikasi sejumlah masalah, yang adalah apa yang kita akan melaksanakan hari,

157
00:11:10,880 --> 00:11:16,030
apa yang kita ingin lakukan adalah hanya kembali palsu.

158
00:11:16,030 --> 00:11:20,030
Metode mendorong kami akan mengembalikan nilai boolean,

159
00:11:20,030 --> 00:11:22,920
dan bahwa nilai boolean akan benar jika push berhasil

160
00:11:22,920 --> 00:11:29,730
dan false jika kita tidak dapat menekan apa-apa lagi karena tumpukan penuh.

161
00:11:29,730 --> 00:11:33,620
Mari kita berjalan melalui sedikit kode yang sekarang.

162
00:11:33,620 --> 00:11:36,400
Berikut fungsi mendorong kami.

163
00:11:36,400 --> 00:11:40,380
Mendorong fungsi kita untuk stack akan mengambil dalam string untuk menempatkan di stack.

164
00:11:40,380 --> 00:11:45,820
Ini akan mengembalikan true jika string berhasil mendorong

165
00:11:45,820 --> 00:11:51,820
pada sebaliknya tumpukan dan palsu.

166
00:11:51,820 --> 00:11:59,740
Ada saran tentang apa yang mungkin menjadi hal pertama yang baik untuk dilakukan di sini?

167
00:11:59,740 --> 00:12:20,630
[Sam] Jika ukuran sama dengan kapasitas kemudian kembali palsu?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Nice job.

169
00:12:23,320 --> 00:12:26,310
Jika ukurannya kapasitas, kita akan kembali palsu.

170
00:12:26,310 --> 00:12:29,270
Kita tidak bisa meletakkan sesuatu yang lebih dalam tumpukan kita.

171
00:12:29,270 --> 00:12:36,900
Jika tidak, kita ingin menempatkan sesuatu di atas tumpukan.

172
00:12:36,900 --> 00:12:41,670
Apa itu "bagian atas tumpukan," awalnya?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Ukuran 0? Ukuran >> 0.

174
00:12:43,650 --> 00:12:49,990
Apa atas tumpukan setelah ada satu hal dalam tumpukan? Missy, kau tahu?

175
00:12:49,990 --> 00:12:52,720
[Missy] Satu. Ukuran >> adalah satu, tepatnya. Kau terus menambah ukuran,

176
00:12:52,720 --> 00:13:01,690
dan setiap kali Anda meletakkan dalam elemen baru pada ukuran indeks dalam array.

177
00:13:01,690 --> 00:13:05,470
Kita bisa melakukannya dengan semacam satu-liner, jika itu masuk akal.

178
00:13:05,470 --> 00:13:11,910
Jadi kita punya berbagai string kita, kita akan mengaksesnya di indeks ukuran,

179
00:13:11,910 --> 00:13:14,780
dan kami hanya akan menyimpan char * kami di sana.

180
00:13:14,780 --> 00:13:19,340
Perhatikan bagaimana ada yang tidak menyalin string yang terjadi di sini,

181
00:13:19,340 --> 00:13:29,680
tidak ada alokasi memori dinamis?

182
00:13:29,680 --> 00:13:34,440
Dan kemudian Missy dibesarkan apa yang sekarang kita lakukan,

183
00:13:34,440 --> 00:13:40,570
karena kita telah disimpan string di tempat yang tepat dalam array,

184
00:13:40,570 --> 00:13:49,230
dan dia berkata bahwa kita harus kenaikan ukuran per satu sehingga kita siap untuk mendorong berikutnya.

185
00:13:49,230 --> 00:13:53,950
Jadi kita bisa melakukan itu dengan s.size + +.

186
00:13:53,950 --> 00:13:59,330
Pada titik ini, kami telah didorong ke array kita. Apa hal terakhir yang harus kita lakukan?

187
00:13:59,330 --> 00:14:10,110
[Mahasiswa] Kembali benar. >> Kembali benar.

188
00:14:10,110 --> 00:14:14,690
Jadi cukup sederhana, kode cukup sederhana. Tidak terlalu banyak.

189
00:14:14,690 --> 00:14:17,070
Setelah Anda membungkus kepala Anda sekitar bagaimana stack bekerja,

190
00:14:17,070 --> 00:14:21,910
ini cukup sederhana untuk diterapkan.

191
00:14:21,910 --> 00:14:26,390
>> Sekarang, bagian selanjutnya dari ini bermunculan string off dari stack.

192
00:14:26,390 --> 00:14:29,410
Aku akan memberi kalian waktu untuk bekerja pada ini sedikit.

193
00:14:29,410 --> 00:14:34,320
Ini hampir dasarnya kebalikan dari apa yang kami lakukan di sini di push.

194
00:14:34,320 --> 00:14:38,510
Apa yang saya lakukan adalah benar - oops.

195
00:14:38,510 --> 00:14:48,160
Saya telah boot up sebuah alat di sini, dan di alat,

196
00:14:48,160 --> 00:14:53,600
Saya sudah berhenti masalah set 5 spesifikasi.

197
00:14:53,600 --> 00:15:02,560
Jika kita tampilannya di sini, kita bisa melihat aku di cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Apakah kalian download kode ini yang terletak di sini, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Baiklah. Jika Anda belum melakukannya, lakukan itu sekarang, benar-benar cepat.

200
00:15:15,030 --> 00:15:22,130
Saya akan melakukannya di jendela terminal saya.

201
00:15:22,130 --> 00:15:25,090
Saya benar-benar melakukannya di sini. Ya.

202
00:15:25,090 --> 00:15:34,730
Ya, Sam? >> Saya punya pertanyaan tentang mengapa Anda mengatakan kurung s.string 's ukuran = str?

203
00:15:34,730 --> 00:15:42,910
Apa str? Apakah itu didefinisikan suatu tempat sebelumnya, atau - oh, di str * char?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ya, tepatnya. Itu adalah argumen. >> Oh, oke. Maaf.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Kami menetapkan string untuk mendorong masuk

206
00:15:49,470 --> 00:15:55,220
Pertanyaan lain yang mungkin akan muncul bahwa kita tidak benar-benar bicarakan di sini adalah

207
00:15:55,220 --> 00:15:58,810
kami mengambil begitu saja bahwa kita memiliki variabel ini disebut s

208
00:15:58,810 --> 00:16:02,710
yang berada di lingkup dan dapat diakses kepada kami.

209
00:16:02,710 --> 00:16:06,960
Kami mengambil begitu saja bahwa s adalah ini struct stack.

210
00:16:06,960 --> 00:16:08,930
Jadi melihat kembali kode push,

211
00:16:08,930 --> 00:16:13,450
Anda dapat melihat bahwa kita sedang melakukan hal-hal dengan string yang mendapat disahkan pada

212
00:16:13,450 --> 00:16:19,210
tapi kemudian tiba-tiba, kita mengakses s.size, seperti, mana s berasal?

213
00:16:19,210 --> 00:16:23,020
Dalam kode yang kita akan melihat dalam arsip bagian

214
00:16:23,020 --> 00:16:27,100
dan kemudian hal-hal yang Anda akan lakukan dalam masalah Anda set,

215
00:16:27,100 --> 00:16:32,440
kami telah membuat tumpukan kami struct variabel global

216
00:16:32,440 --> 00:16:36,380
sehingga kita dapat memiliki akses ke dalam semua fungsi yang berbeda kami

217
00:16:36,380 --> 00:16:40,630
tanpa harus secara manual lulus sekitar dan lulus dengan referensi,

218
00:16:40,630 --> 00:16:44,870
melakukan semua hal semacam itu.

219
00:16:44,870 --> 00:16:52,280
Kami hanya menipu sedikit, jika Anda mau, untuk membuat hal-hal yang lebih baik.

220
00:16:52,280 --> 00:16:57,430
Dan itu adalah sesuatu yang kita lakukan di sini karena itu untuk bersenang-senang, itu lebih mudah.

221
00:16:57,430 --> 00:17:02,800
Seringkali, Anda akan melihat orang-orang melakukan hal ini jika mereka memiliki satu struktur data besar

222
00:17:02,800 --> 00:17:07,750
yang sedang dioperasi dalam program mereka.

223
00:17:07,750 --> 00:17:09,560
>> Mari kita kembali ke alat.

224
00:17:09,560 --> 00:17:15,240
Apakah semua orang berhasil mendapatkan section6.zip tersebut?

225
00:17:15,240 --> 00:17:20,440
Semua orang unzip menggunakan section6.zip unzip?

226
00:17:20,440 --> 00:17:27,200
Jika Anda pergi ke direktori 6 bagian -

227
00:17:27,200 --> 00:17:29,220
aah, seluruh tempat -

228
00:17:29,220 --> 00:17:32,840
dan Anda daftar apa yang ada di sini, Anda melihat bahwa Anda punya tiga file yang berbeda c..

229
00:17:32,840 --> 00:17:38,350
Anda punya antrian, SLL suatu, yang sendiri-linked list, dan stack.

230
00:17:38,350 --> 00:17:44,600
Jika Anda membuka stack.c,

231
00:17:44,600 --> 00:17:47,330
Anda dapat melihat bahwa kita punya struct ini ditetapkan untuk kita,

232
00:17:47,330 --> 00:17:51,330
struct yang tepat bahwa kita hanya berbicara tentang dalam slide.

233
00:17:51,330 --> 00:17:56,340
Kami punya variabel global kami untuk stack,

234
00:17:56,340 --> 00:18:00,110
kita punya fungsi mendorong kami,

235
00:18:00,110 --> 00:18:04,230
dan kemudian kita punya fungsi pop kita.

236
00:18:04,230 --> 00:18:08,320
Aku akan menaruh kode untuk mendorong kembali pada slide di sini,

237
00:18:08,320 --> 00:18:10,660
tapi apa yang saya ingin kalian lakukan adalah, untuk yang terbaik dari kemampuan Anda,

238
00:18:10,660 --> 00:18:13,790
pergi dan melaksanakan fungsi pop.

239
00:18:13,790 --> 00:18:18,480
Setelah Anda telah menerapkan hal itu, Anda dapat mengkompilasi ini dengan membuat tumpukan,

240
00:18:18,480 --> 00:18:22,540
dan kemudian menjalankan executable tumpukan resultan,

241
00:18:22,540 --> 00:18:28,390
dan yang akan menjalankan semua ini kode uji di sini yang ada di utama.

242
00:18:28,390 --> 00:18:31,060
Dan utamanya mengurus benar-benar membuat push dan pop panggilan

243
00:18:31,060 --> 00:18:33,220
dan memastikan bahwa semuanya berjalan baik-baik saja melalui.

244
00:18:33,220 --> 00:18:36,820
Hal ini juga menginisialisasi ukuran stack di sini

245
00:18:36,820 --> 00:18:39,780
sehingga Anda tidak perlu khawatir tentang menginisialisasi itu.

246
00:18:39,780 --> 00:18:42,310
Anda dapat berasumsi bahwa itu diinisialisasi dengan benar

247
00:18:42,310 --> 00:18:48,000
oleh waktu yang Anda mengaksesnya dalam fungsi pop.

248
00:18:48,000 --> 00:18:53,530
Apakah itu masuk akal?

249
00:18:53,530 --> 00:19:00,100
Jadi di sini kita pergi. Ada kode push.

250
00:19:00,100 --> 00:19:13,210
Aku akan memberikan kalian 5 atau 10 menit.

251
00:19:13,210 --> 00:19:15,690
Dan jika Anda memiliki pertanyaan untuk sementara saat Anda sedang coding,

252
00:19:15,690 --> 00:19:17,710
silakan bertanya dengan keras.

253
00:19:17,710 --> 00:19:23,080
Jadi jika Anda mendapatkan ke titik mencuat, hanya bertanya.

254
00:19:23,080 --> 00:19:26,030
Biar saya tahu, biarkan orang lain tahu.

255
00:19:26,030 --> 00:19:28,160
Bekerja dengan tetangga Anda juga.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Kami hanya menerapkan pop sekarang? Hanya >> pop.

257
00:19:30,360 --> 00:19:34,200
Meskipun Anda dapat menyalin pelaksanaan mendorong jika Anda ingin

258
00:19:34,200 --> 00:19:37,780
sehingga pengujian akan bekerja.

259
00:19:37,780 --> 00:19:41,940
Karena sulit untuk menguji hal-hal yang masuk ke -

260
00:19:41,940 --> 00:19:49,030
atau, sulit untuk menguji hal-hal yang muncul keluar dari tumpukan jika tidak ada sesuatu dalam tumpukan untuk mulai dengan.

261
00:19:49,030 --> 00:19:55,250
>> Apa pop seharusnya kembali? Unsur dari atas tumpukan.

262
00:19:55,250 --> 00:20:01,260
Ini seharusnya untuk mendapatkan elemen off dari atas tumpukan

263
00:20:01,260 --> 00:20:05,780
dan kemudian lakukan dengan decrement ukuran stack,

264
00:20:05,780 --> 00:20:07,810
dan sekarang Anda telah kehilangan unsur di atas.

265
00:20:07,810 --> 00:20:11,420
Dan kemudian Anda kembali elemen di atas.

266
00:20:11,420 --> 00:20:20,080
[Mahasiswa, dipahami]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Jadi apa yang terjadi jika Anda melakukan itu? [Mahasiswa, dipahami]

268
00:20:28,810 --> 00:20:34,000
Apa yang akhirnya terjadi adalah Anda mungkin mengakses baik

269
00:20:34,000 --> 00:20:37,350
elemen yang belum diinisialisasi belum, sehingga Anda perhitungan

270
00:20:37,350 --> 00:20:39,990
di mana elemen terakhir adalah mati.

271
00:20:39,990 --> 00:20:46,260
Jadi di sini, jika Anda perhatikan, dalam mendorong, kita mengakses string pada elemen s.size

272
00:20:46,260 --> 00:20:48,560
karena indeks baru.

273
00:20:48,560 --> 00:20:51,460
Ini puncak baru dari stack.

274
00:20:51,460 --> 00:21:01,100
Sedangkan pada pop, s.size akan menjadi ruang berikutnya,

275
00:21:01,100 --> 00:21:05,210
ruang yang di atas semua elemen dalam tumpukan Anda.

276
00:21:05,210 --> 00:21:10,050
Jadi elemen paling atas tidak di s.size,

277
00:21:10,050 --> 00:21:14,930
melainkan, itu di bawahnya.

278
00:21:14,930 --> 00:21:19,640
>> Hal lain yang harus dilakukan ketika Anda - di pop,

279
00:21:19,640 --> 00:21:22,030
adalah Anda harus untuk penurunan ukuran.

280
00:21:22,030 --> 00:21:28,750
Jika Anda ingat kembali ke diagram kecil kami di sini,

281
00:21:28,750 --> 00:21:30,980
benar-benar, satu-satunya hal yang kita lihat terjadi ketika kita disebut pop

282
00:21:30,980 --> 00:21:36,150
adalah bahwa ukuran ini turun, pertama 2, kemudian ke 1.

283
00:21:36,150 --> 00:21:42,620
Kemudian ketika kita mendorong elemen baru, itu akan pergi di tempat yang tepat.

284
00:21:42,620 --> 00:21:49,610
[Basil] Jika s.size adalah 2, maka tidak akan pergi ke elemen 2,

285
00:21:49,610 --> 00:21:54,400
dan kemudian Anda ingin pop elemen yang off?

286
00:21:54,400 --> 00:21:59,510
Jadi jika kita pergi ke - >> Jadi mari kita lihat ini lagi.

287
00:21:59,510 --> 00:22:07,730
Jika ini adalah tumpukan kami di titik ini

288
00:22:07,730 --> 00:22:12,130
dan kita sebut pop,

289
00:22:12,130 --> 00:22:16,150
di mana indeks adalah elemen paling atas?

290
00:22:16,150 --> 00:22:19,300
[Basil] Pada 2, tapi itu akan muncul 3. >> Kanan.

291
00:22:19,300 --> 00:22:24,220
Jadi itulah di mana ukuran kami adalah 3, tapi kami ingin pop elemen pada indeks 2.

292
00:22:24,220 --> 00:22:29,900
Ini semacam khas off dengan salah satu yang Anda miliki dengan pengindeksan nol-array.

293
00:22:29,900 --> 00:22:36,430
Jadi Anda ingin pop elemen ketiga, namun unsur ketiga tidak di indeks 3.

294
00:22:36,430 --> 00:22:39,430
Dan alasan kita tidak perlu melakukan itu minus 1 ketika kita mendorong

295
00:22:39,430 --> 00:22:44,120
adalah karena sekarang, Anda melihat bahwa elemen paling atas,

296
00:22:44,120 --> 00:22:47,600
jika kita mendorong sesuatu yang lain ke stack pada saat ini,

297
00:22:47,600 --> 00:22:50,360
kita ingin mendorong pada indeks 3.

298
00:22:50,360 --> 00:23:03,550
Dan kebetulan bahwa ukuran dan indeks berbaris ketika Anda mendorong.

299
00:23:03,550 --> 00:23:06,960
>> Siapa yang punya implementasi tumpukan bekerja?

300
00:23:06,960 --> 00:23:09,690
Anda punya setumpuk bekerja satu. Apakah Anda memiliki pop bekerja belum?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Ya. Saya kira begitu.

302
00:23:11,890 --> 00:23:14,610
Program >> sedang berjalan dan tidak seg patahan, itu mencetak?

303
00:23:14,610 --> 00:23:17,520
Apakah itu mencetak "sukses" ketika Anda menjalankannya?

304
00:23:17,520 --> 00:23:22,630
Ya. Membuat stack, menjalankannya, jika mencetak "sukses" dan tidak pergi booming,

305
00:23:22,630 --> 00:23:26,000
maka semua bagus.

306
00:23:26,000 --> 00:23:34,070
Baiklah. Mari kita pergi ke alat benar-benar cepat,

307
00:23:34,070 --> 00:23:46,100
dan kami akan berjalan melalui ini.

308
00:23:46,100 --> 00:23:51,110
Jika kita melihat apa yang terjadi di sini dengan pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, apa hal pertama yang Anda lakukan?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Jika s.size lebih besar dari 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Oke. Dan mengapa kau lakukan itu?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Untuk memastikan bahwa ada sesuatu di dalam tumpukan.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Kanan. Anda ingin menguji untuk memastikan bahwa s.size lebih besar dari 0;

314
00:24:10,950 --> 00:24:13,280
jika tidak, apa yang Anda inginkan untuk terjadi?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Kembali nol? Kembali >> nol, tepatnya.

316
00:24:16,630 --> 00:24:20,740
Jadi jika s.size lebih besar dari 0. Lalu apa yang akan kita lakukan?

317
00:24:20,740 --> 00:24:25,890
Apa yang kita lakukan jika stack tidak kosong?

318
00:24:25,890 --> 00:24:31,210
[Stella] Anda akan memundurkan ukuran? >> Anda akan memundurkan ukuran, oke.

319
00:24:31,210 --> 00:24:34,440
Jadi, bagaimana Anda melakukannya? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Besar. Dan kemudian apa yang Anda lakukan?

321
00:24:37,030 --> 00:24:44,140
[Stella] Dan kemudian aku berkata kembali s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Besar.

323
00:24:48,560 --> 00:24:51,940
Jika Anda kembali nol. Ya, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Mengapa tidak perlu s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Ya. >> Got it.

326
00:24:58,430 --> 00:25:00,980
[Sam] Saya pikir karena Anda mengambil keluar 1,

327
00:25:00,980 --> 00:25:04,290
maka Anda akan kembali tidak salah satu yang mereka minta.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Dan ini adalah hanya apa yang kita bicarakan dengan seluruh masalah ini dari 0 indeks.

329
00:25:09,400 --> 00:25:11,380
Jadi jika kita tampilannya kembali ke sini.

330
00:25:11,380 --> 00:25:15,650
Jika kita melihat orang ini di sini, Anda dapat melihat bahwa ketika kita pop,

331
00:25:15,650 --> 00:25:19,340
kita bermunculan elemen pada indeks 2.

332
00:25:19,340 --> 00:25:25,200
>> Jadi kita mengurangi ukuran pertama kami, maka ukuran kami sesuai indeks kami.

333
00:25:25,200 --> 00:25:39,650
Jika kita tidak akan memundurkan ukuran pertama, maka kita harus melakukan ukuran -1 dan kemudian penurunan.

334
00:25:39,650 --> 00:25:45,270
Besar. Semua baik?

335
00:25:45,270 --> 00:25:47,530
Setiap pertanyaan tentang ini?

336
00:25:47,530 --> 00:25:54,050
Ada sejumlah cara yang berbeda untuk menulis ini juga.

337
00:25:54,050 --> 00:26:03,290
Pada kenyataannya, kita bisa melakukan sesuatu yang bahkan - bisa kita lakukan satu-kapal.

338
00:26:03,290 --> 00:26:05,770
Kita bisa melakukan kembali satu baris.

339
00:26:05,770 --> 00:26:12,980
Jadi kita benar-benar dapat memundurkan sebelum kita kembali dengan melakukan itu.

340
00:26:12,980 --> 00:26:18,320
Jadi menempatkan - sebelum s.size tersebut.

341
00:26:18,320 --> 00:26:22,060
Yang membuat garis benar-benar padat.

342
00:26:22,060 --> 00:26:30,940
Dimana perbedaan antara - ukuran s dan. S.size--

343
00:26:30,940 --> 00:26:40,130
adalah bahwa ini postfix - mereka menyebutnya postfix karena - datang setelah s.size--

344
00:26:40,130 --> 00:26:47,430
berarti bahwa s.size dievaluasi untuk tujuan mencari indeks

345
00:26:47,430 --> 00:26:50,410
seperti saat ini ketika baris ini dijalankan,

346
00:26:50,410 --> 00:26:54,290
dan kemudian ini - terjadi setelah baris dijalankan.

347
00:26:54,290 --> 00:27:00,340
Setelah elemen di s.size indeks diakses.

348
00:27:00,340 --> 00:27:07,260
Dan bukan itu yang kita inginkan, karena kita ingin penurunan yang terjadi terlebih dahulu.

349
00:27:07,260 --> 00:27:10,990
Othewise, kita akan mengakses array, efektif, di luar batas.

350
00:27:10,990 --> 00:27:16,850
Kita akan mengakses elemen di atas salah satu yang kita benar-benar ingin mengakses.

351
00:27:16,850 --> 00:27:23,840
Ya, Sam? >> Apakah lebih cepat atau menggunakan RAM kurang untuk membuat dalam satu baris atau tidak?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Jujur, itu benar-benar tergantung.

353
00:27:29,620 --> 00:27:34,220
[Sam, tidak dapat dipahami] >> Ya, itu tergantung. Anda dapat melakukan trik compiler

354
00:27:34,220 --> 00:27:41,580
untuk mendapatkan compiler untuk mengakui bahwa, biasanya, saya bayangkan.

355
00:27:41,580 --> 00:27:44,840
>> Jadi kita telah menyebutkan sedikit tentang hal ini optimasi compiler

356
00:27:44,840 --> 00:27:47,400
yang dapat Anda lakukan dalam menyusun,

357
00:27:47,400 --> 00:27:50,580
dan itulah jenis hal yang kompilator mungkin bisa mengetahui,

358
00:27:50,580 --> 00:27:54,710
seperti oh, hei, mungkin aku bisa melakukan ini semua dalam satu operasi,

359
00:27:54,710 --> 00:27:59,420
sebagai lawan memuat variabel ukuran dari RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing itu, menyimpannya kembali keluar, dan kemudian memuatnya kembali lagi

361
00:28:03,770 --> 00:28:08,000
untuk memproses sisa operasi ini.

362
00:28:08,000 --> 00:28:10,710
Tapi biasanya, tidak, ini bukan semacam hal

363
00:28:10,710 --> 00:28:20,770
yang akan membuat program anda lebih cepat secara signifikan.

364
00:28:20,770 --> 00:28:26,000
Setiap pertanyaan lebih lanjut tentang tumpukan?

365
00:28:26,000 --> 00:28:31,360
>> Jadi mendorong dan muncul. Jika kalian ingin mencoba edisi hacker,

366
00:28:31,360 --> 00:28:33,660
apa yang kami lakukan dalam edisi hacker sebenarnya hilang

367
00:28:33,660 --> 00:28:37,670
dan membuat tumpukan ini tumbuh secara dinamis.

368
00:28:37,670 --> 00:28:43,190
Tantangan ada di sini terutama dalam fungsi push,

369
00:28:43,190 --> 00:28:48,820
untuk mencari tahu bagaimana untuk membuat array yang tumbuh

370
00:28:48,820 --> 00:28:52,450
Anda terus mendorong elemen lebih dan lebih ke stack.

371
00:28:52,450 --> 00:28:56,000
Ini sebenarnya tidak terlalu banyak kode tambahan.

372
00:28:56,000 --> 00:29:00,080
Hanya panggilan untuk - Anda harus ingat untuk mendapatkan panggilan ke malloc di sana benar,

373
00:29:00,080 --> 00:29:03,310
dan kemudian mencari tahu ketika Anda akan menelepon realloc.

374
00:29:03,310 --> 00:29:06,090
Itulah tantangan yang menyenangkan jika Anda tertarik.

375
00:29:06,090 --> 00:29:11,550
>> Tapi untuk saat ini, mari kita lanjutkan, dan mari kita bicara tentang antrian.

376
00:29:11,550 --> 00:29:15,680
Gulir lewat sini.

377
00:29:15,680 --> 00:29:19,340
Antrian adalah saudara dekat dari stack.

378
00:29:19,340 --> 00:29:25,380
Jadi dalam stack, hal-hal yang diletakkan di terakhir

379
00:29:25,380 --> 00:29:28,810
adalah hal pertama untuk kemudian diambil.

380
00:29:28,810 --> 00:29:33,600
Kami punya terakhir ini, keluar pertama, atau LIFO, memesan.

381
00:29:33,600 --> 00:29:38,390
Sedangkan dalam antrian, seperti yang Anda harapkan dari ketika Anda sedang berdiri di garis,

382
00:29:38,390 --> 00:29:41,980
orang pertama untuk masuk baris, hal pertama yang harus masuk ke antrian,

383
00:29:41,980 --> 00:29:47,630
adalah hal pertama yang akan diambil dari antrian.

384
00:29:47,630 --> 00:29:51,490
Antrian juga sering digunakan ketika kita sedang berhadapan dengan grafik,

385
00:29:51,490 --> 00:29:55,560
seperti kita berbicara tentang sebentar dengan tumpukan,

386
00:29:55,560 --> 00:30:00,260
dan antrian juga berguna untuk berbagai hal lainnya.

387
00:30:00,260 --> 00:30:06,180
Satu hal yang muncul sering mencoba untuk mempertahankan, misalnya,

388
00:30:06,180 --> 00:30:12,310
daftar diurutkan dari elemen.

389
00:30:12,310 --> 00:30:17,650
Dan Anda dapat melakukan ini dengan array. Anda dapat menyimpan daftar diurutkan dari hal-hal dalam array,

390
00:30:17,650 --> 00:30:20,650
tapi di mana itu akan sulit maka Anda harus selalu mencari

391
00:30:20,650 --> 00:30:26,160
tempat yang tepat untuk memasukkan hal berikutnya.

392
00:30:26,160 --> 00:30:28,250
Jadi jika Anda memiliki sebuah array dari angka, 1 sampai 10,

393
00:30:28,250 --> 00:30:31,630
dan kemudian Anda ingin memperluas bahwa untuk semua angka 1 sampai 100,

394
00:30:31,630 --> 00:30:33,670
dan Anda mendapatkan angka-angka secara acak dan mencoba untuk menjaga semuanya

395
00:30:33,670 --> 00:30:40,650
diurutkan saat Anda pergi melalui, Anda akhirnya harus melakukan banyak pergeseran.

396
00:30:40,650 --> 00:30:43,910
Dengan beberapa jenis antrian dan beberapa jenis struktur data yang mendasari,

397
00:30:43,910 --> 00:30:46,670
Anda benar-benar bisa tetap cukup sederhana.

398
00:30:46,670 --> 00:30:50,640
Anda tidak harus menambahkan sesuatu dan kemudian Reshuffle semuanya setiap kali.

399
00:30:50,640 --> 00:30:56,770
Anda juga tidak harus melakukan banyak pergeseran dari unsur internal sekitar.

400
00:30:56,770 --> 00:31:02,990
Ketika kita melihat antrian, Anda melihat bahwa - juga di queue.c di kode bagian -

401
00:31:02,990 --> 00:31:10,950
struct bahwa kami telah memberikan Anda benar-benar mirip dengan struct yang kami berikan untuk Anda stack.

402
00:31:10,950 --> 00:31:13,770
>> Ada satu pengecualian untuk ini, dan bahwa satu pengecualian

403
00:31:13,770 --> 00:31:21,700
adalah bahwa kita memiliki bilangan bulat tambahan yang disebut kepala,

404
00:31:21,700 --> 00:31:28,120
dan kepala di sini adalah untuk melacak kepala antrian,

405
00:31:28,120 --> 00:31:32,160
atau elemen pertama dalam antrian.

406
00:31:32,160 --> 00:31:37,470
Dengan tumpukan, kami mampu melacak elemen bahwa kami akan mengambil,

407
00:31:37,470 --> 00:31:40,800
atau atas tumpukan, dengan hanya menggunakan ukuran,

408
00:31:40,800 --> 00:31:44,220
sedangkan dengan antrian, kita harus berurusan dengan ujung-ujung.

409
00:31:44,220 --> 00:31:49,000
Kami sedang berusaha untuk taktik hal-hal di di akhir, tapi kemudian kembali hal-hal dari depan.

410
00:31:49,000 --> 00:31:54,640
Jadi secara efektif, dengan kepala, kita memiliki indeks awal antrian,

411
00:31:54,640 --> 00:31:58,920
dan ukuran memberi kita indeks akhir antrian

412
00:31:58,920 --> 00:32:03,730
sehingga kita bisa mengambil hal-hal dari kepala dan menambahkan hal-hal ke ekor.

413
00:32:03,730 --> 00:32:06,890
Sedangkan dengan stack, kami hanya pernah berurusan dengan bagian atas tumpukan.

414
00:32:06,890 --> 00:32:08,900
Kami tidak pernah mengakses bawah tumpukan.

415
00:32:08,900 --> 00:32:12,220
Kami hanya menambahkan hal-hal ke atas dan mengambil hal off dari atas

416
00:32:12,220 --> 00:32:17,470
sehingga kita tidak perlu bahwa bidang ekstra di dalam struct kami.

417
00:32:17,470 --> 00:32:20,590
Apakah itu umumnya masuk akal?

418
00:32:20,590 --> 00:32:27,670
Baiklah. Ya, Charlotte? [Charlotte, dipahami]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Itu pertanyaan yang bagus, dan itu salah satu yang muncul dalam kuliah.

420
00:32:32,660 --> 00:32:36,290
Mungkin berjalan melalui beberapa contoh akan menggambarkan mengapa

421
00:32:36,290 --> 00:32:41,400
kita tidak ingin menggunakan string [0] sebagai kepala antrian.

422
00:32:41,400 --> 00:32:46,770
>> Jadi bayangkan bahwa kita memiliki antrian kita, kita akan menyebutnya antrian.

423
00:32:46,770 --> 00:32:49,210
Pada awalnya, ketika kita baru saja instantiated itu,

424
00:32:49,210 --> 00:32:53,330
ketika kita baru saja menyatakan hal itu, kami belum diinisialisasi apa-apa.

425
00:32:53,330 --> 00:32:56,790
Ini semua sampah. Jadi tentu saja kami ingin memastikan bahwa kami menginisialisasi

426
00:32:56,790 --> 00:33:00,950
baik ukuran dan bidang kepala menjadi 0, sesuatu yang wajar.

427
00:33:00,950 --> 00:33:05,770
Kita juga bisa pergi ke depan dan nol keluar unsur-unsur dalam antrian kami.

428
00:33:05,770 --> 00:33:09,930
Dan untuk membuat ini cocok diagram, perhatikan bahwa sekarang antrian kami hanya bisa menampung tiga elemen;

429
00:33:09,930 --> 00:33:13,150
sedangkan tumpukan kami bisa menampung empat, antrian kami hanya bisa menampung tiga.

430
00:33:13,150 --> 00:33:18,680
Dan itu hanya untuk membuat diagram fit.

431
00:33:18,680 --> 00:33:26,150
Hal pertama yang terjadi di sini adalah kita enqueue string "hi".

432
00:33:26,150 --> 00:33:30,380
Dan seperti yang kita lakukan dengan tumpukan, tidak ada yang sangat berbeda di sini,

433
00:33:30,380 --> 00:33:39,230
kita membuang string pada string di [0] dan kenaikan ukuran kami oleh 1.

434
00:33:39,230 --> 00:33:42,720
Kami enqueue "bye", itu akan memakai.

435
00:33:42,720 --> 00:33:45,870
Jadi ini terlihat seperti tumpukan untuk sebagian besar.

436
00:33:45,870 --> 00:33:53,230
Kami memulai di sini, elemen baru, elemen baru, ukuran terus naik.

437
00:33:53,230 --> 00:33:56,330
Apa yang terjadi pada saat ini ketika kita ingin dequeue sesuatu?

438
00:33:56,330 --> 00:34:01,280
Ketika kita ingin dequeue, yang merupakan elemen yang ingin kita dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Nol. Tepat, Basil.

440
00:34:04,110 --> 00:34:10,960
Kami ingin menyingkirkan string pertama, yang satu ini, "hi".

441
00:34:10,960 --> 00:34:13,170
Jadi apa hal lain yang berubah?

442
00:34:13,170 --> 00:34:17,010
Perhatikan ketika kita muncul sesuatu dari tumpukan, kita hanya mengubah ukuran,

443
00:34:17,010 --> 00:34:22,080
tapi di sini, kami punya beberapa hal yang berubah.

444
00:34:22,080 --> 00:34:27,440
Tidak hanya melakukan perubahan ukuran, tetapi perubahan kepala.

445
00:34:27,440 --> 00:34:31,020
Ini akan kembali ke titik Charlotte sebelumnya:

446
00:34:31,020 --> 00:34:38,699
mengapa kita memiliki kepala ini juga?

447
00:34:38,699 --> 00:34:42,110
Apakah masuk akal sekarang, Charlotte? >> Jenis.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Jenis? Jadi apa yang terjadi ketika kita dequeued?

449
00:34:47,500 --> 00:34:54,340
Apa kepala melakukan itu sekarang adalah menarik?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, karena berubah - Oke. Oh, begitu.

451
00:34:56,449 --> 00:35:02,090
Karena kepala - di mana kepala menunjuk ke perubahan dalam hal lokasi.

452
00:35:02,090 --> 00:35:07,200
Ini tidak lagi selalu satu indeks nol. >> Ya, tepatnya.

453
00:35:07,200 --> 00:35:17,660
Apa yang terjadi adalah jika dequeueing elemen tinggi

454
00:35:17,660 --> 00:35:20,590
dilakukan dan kita tidak memiliki bidang ini kepala

455
00:35:20,590 --> 00:35:26,880
karena kami selalu memanggil string ini pada 0 indeks kepala antrian kami,

456
00:35:26,880 --> 00:35:30,170
maka kita harus menggeser sisa antrian ke bawah.

457
00:35:30,170 --> 00:35:36,010
Kami harus menggeser "bye" dari dari string [1] ke string [0].

458
00:35:36,010 --> 00:35:38,760
Dan string [2] ke string [1].

459
00:35:38,760 --> 00:35:43,050
Dan kita harus melakukan ini untuk seluruh daftar elemen,

460
00:35:43,050 --> 00:35:45,110
array seluruh elemen.

461
00:35:45,110 --> 00:35:50,490
Dan ketika kita melakukan hal ini dengan sebuah array, yang jadi sangat mahal.

462
00:35:50,490 --> 00:35:53,340
Jadi di sini, itu bukan masalah besar. Kami hanya memiliki tiga elemen dalam array kita.

463
00:35:53,340 --> 00:35:57,230
Tetapi jika kita memiliki antrian seribu atau sejuta elemen elemen,

464
00:35:57,230 --> 00:36:00,060
dan kemudian tiba-tiba, kami mulai membuat sekelompok dequeue memanggil semua dalam satu lingkaran,

465
00:36:00,060 --> 00:36:03,930
hal-hal yang benar-benar akan memperlambat karena menggeser semuanya turun terus-menerus.

466
00:36:03,930 --> 00:36:07,320
Kau tahu, bergeser 1, pergeseran oleh 1, pergeseran oleh 1, pergeseran oleh 1.

467
00:36:07,320 --> 00:36:13,650
Sebaliknya, kita menggunakan kepala ini, kita menyebutnya sebagai "pointer" meskipun itu tidak benar-benar pointer

468
00:36:13,650 --> 00:36:16,430
dalam arti sempit, itu bukan tipe pointer.

469
00:36:16,430 --> 00:36:19,410
Ini bukan * int atau char * atau sesuatu seperti itu.

470
00:36:19,410 --> 00:36:28,930
Tapi itu menunjuk atau menunjukkan kepala antrian kami. Ya?

471
00:36:28,930 --> 00:36:38,800
>> [Mahasiswa] Bagaimana dequeue tahu untuk hanya pop off apa pun di kepala?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Bagaimana dequeue tahu bagaimana pop off apa pun yang di kepala? Kanan >>, yeah.

473
00:36:43,620 --> 00:36:49,050
>> Apa itu melihat hanya apapun bidang kepala diatur ke.

474
00:36:49,050 --> 00:36:52,710
Jadi dalam hal ini kasus pertama, jika kita melihat di sini,

475
00:36:52,710 --> 00:36:55,690
kepala kita adalah 0, indeks 0. >> Kanan.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Jadi itu hanya mengatakan apa-apa, baik, elemen pada indeks 0, string "hi",

477
00:37:00,500 --> 00:37:03,050
adalah elemen di kepala antrian kami.

478
00:37:03,050 --> 00:37:05,570
Jadi kita akan dequeue orang itu.

479
00:37:05,570 --> 00:37:09,800
Dan itu akan menjadi elemen yang akan dikembalikan ke pemanggil.

480
00:37:09,800 --> 00:37:14,540
Ya, Saad? Jadi >> kepala pada dasarnya menetapkan - di mana Anda akan indeks itu?

481
00:37:14,540 --> 00:37:17,750
Itulah awal dari itu? >> Ya. Oke >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Itu menjadi awal baru untuk array kita.

483
00:37:22,900 --> 00:37:28,930
Jadi, ketika Anda dequeue sesuatu, yang harus Anda lakukan adalah mengakses elemen pada indeks q.head,

484
00:37:28,930 --> 00:37:32,240
dan itu akan menjadi elemen yang ingin Anda dequeue.

485
00:37:32,240 --> 00:37:34,930
Anda juga harus untuk penurunan ukuran.

486
00:37:34,930 --> 00:37:39,430
Kita akan melihat di mana sedikit hal mendapatkan sedikit rumit dengan ini.

487
00:37:39,430 --> 00:37:46,520
Kami dequeue, dan sekarang, jika kita enqueue lagi,

488
00:37:46,520 --> 00:37:51,300
di mana kita enqueue?

489
00:37:51,300 --> 00:37:55,000
Mana elemen berikutnya masuk dalam antrian kita?

490
00:37:55,000 --> 00:37:57,980
Katakanlah kita ingin enqueue string "CS".

491
00:37:57,980 --> 00:38:02,240
Ke mana indeks akan pergi? [Siswa] Strings [2]. >> Dua.

492
00:38:02,240 --> 00:38:04,980
Mengapa 2 dan tidak 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Karena sekarang kepala adalah 1, sehingga seperti awal daftar?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Kanan. Dan apa menandai akhir dari daftar?

495
00:38:21,220 --> 00:38:23,290
Apa yang kita gunakan untuk menunjukkan akhir dari antrian kita?

496
00:38:23,290 --> 00:38:25,970
Kepala adalah kepala antrian kami, awal dari antrian kami.

497
00:38:25,970 --> 00:38:29,530
Apa akhir dari antrian kita? [Siswa] Ukuran. >> Ukuran, tepatnya.

498
00:38:29,530 --> 00:38:36,360
Jadi unsur-unsur baru kami masuk pada ukuran, dan unsur-unsur yang kita lepas landas datang dari kepala.

499
00:38:36,360 --> 00:38:45,390
Ketika kita enqueue elemen berikutnya, kita memasukkannya ke dalam pada ukuran.

500
00:38:45,390 --> 00:38:48,530
[Siswa] Sebelum Anda menempatkan bahwa dalam sekalipun, ukuran 1, kan?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Kanan. Jadi tidak cukup pada ukuran. Ukuran +, tidak +1, tetapi kepala +.

502
00:38:55,690 --> 00:38:59,990
Karena kita bergeser segalanya dengan jumlah kepala.

503
00:38:59,990 --> 00:39:14,270
Jadi di sini, sekarang kita punya antrian ukuran 1 yang dimulai pada indeks 1.

504
00:39:14,270 --> 00:39:20,730
Ekor adalah indeks 2. Ya?

505
00:39:20,730 --> 00:39:25,780
>> [Siswa] Apa yang terjadi ketika Anda dequeue string [0], dan string 'slot dalam memori

506
00:39:25,780 --> 00:39:29,420
hanya mendapatkan dikosongkan, pada dasarnya, atau hanya lupa?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Ya. Dalam hal ini, kami hanya melupakan mereka.

508
00:39:34,700 --> 00:39:42,640
Jika kita menyimpan salinan dari mereka untuk -

509
00:39:42,640 --> 00:39:46,310
banyak struktur data akan sering menyimpan salinan mereka sendiri dari unsur-unsur

510
00:39:46,310 --> 00:39:51,760
sehingga orang mengelola struktur data tidak perlu khawatir

511
00:39:51,760 --> 00:39:53,650
tentang di mana semua pointer akan.

512
00:39:53,650 --> 00:39:56,000
Struktur Data berpegang pada segala sesuatu, berpegang pada semua salinan,

513
00:39:56,000 --> 00:39:59,580
untuk memastikan bahwa semuanya tetap tepat.

514
00:39:59,580 --> 00:40:03,140
Namun, dalam kasus ini, struktur data yang baru saja, untuk kesederhanaan,

515
00:40:03,140 --> 00:40:05,580
tidak membuat salinan dari apa pun yang kita menyimpan di dalamnya.

516
00:40:05,580 --> 00:40:08,630
[Mahasiswa] Jadi ini array terus menerus -? >> Ya.

517
00:40:08,630 --> 00:40:14,350
Jika kita melihat kembali apa definisi itu struktur ini, itu.

518
00:40:14,350 --> 00:40:19,110
Ini hanya sebuah array standar seperti yang Anda lihat,

519
00:40:19,110 --> 00:40:24,280
array char * s.

520
00:40:24,280 --> 00:40:26,340
Apakah itu -? >> Ya, aku hanya ingin tahu

521
00:40:26,340 --> 00:40:29,130
jika Anda akhirnya akan kehabisan memori, sampai batas tertentu,

522
00:40:29,130 --> 00:40:32,330
jika Anda memiliki semua tempat kosong dalam array Anda?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ya, itulah titik yang baik.

524
00:40:36,390 --> 00:40:41,530
>> Jika kita melihat apa yang terjadi sekarang di titik ini,

525
00:40:41,530 --> 00:40:46,350
kami telah mengisi antrian kami, sepertinya.

526
00:40:46,350 --> 00:40:50,390
Tapi kita belum benar-benar penuh antrian kami

527
00:40:50,390 --> 00:40:57,710
karena kita memiliki antrian yang ukuran 2, tetapi mulai pada indeks 1,

528
00:40:57,710 --> 00:41:02,160
karena di situlah pointer kepala kita.

529
00:41:02,160 --> 00:41:08,400
Seperti yang Anda katakan, bahwa elemen pada string [0], pada indeks 0, tidak benar-benar ada.

530
00:41:08,400 --> 00:41:10,450
Ini bukan dalam antrian kami lagi.

531
00:41:10,450 --> 00:41:16,460
Kami hanya tidak repot-repot untuk masuk dan menimpanya ketika kita dequeued itu.

532
00:41:16,460 --> 00:41:18,700
Jadi meskipun sepertinya kita sudah kehabisan memori, kita benar-benar belum.

533
00:41:18,700 --> 00:41:23,270
Tempat itu tersedia bagi kita untuk menggunakan.

534
00:41:23,270 --> 00:41:29,310
Perilaku yang tepat, jika kita mencoba dan pertama dequeue sesuatu

535
00:41:29,310 --> 00:41:34,420
seperti "bye", yang akan pop bye off.

536
00:41:34,420 --> 00:41:38,460
Sekarang antrian kami dimulai pada indeks 2 dan ukuran 1.

537
00:41:38,460 --> 00:41:42,240
Dan sekarang jika kita mencoba dan enqueue sesuatu lagi, katakanlah 50,

538
00:41:42,240 --> 00:41:47,880
50 harus pergi di tempat ini pada indeks 0

539
00:41:47,880 --> 00:41:51,270
karena masih tersedia bagi kita. Ya, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Apakah itu terjadi secara otomatis?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Ini tidak terjadi cukup otomatis. Anda harus melakukan matematika

542
00:41:56,150 --> 00:42:00,380
untuk membuatnya bekerja, tapi pada dasarnya apa yang kami lakukan adalah kami baru saja melilit.

543
00:42:00,380 --> 00:42:04,070
[Saad] Dan tidak apa-apa jika ini memiliki lubang di tengah-tengah itu?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Ini adalah jika kita dapat membuat matematika bekerja dengan benar.

545
00:42:08,720 --> 00:42:15,470
>> Dan ternyata itu sebenarnya tidak begitu sulit untuk dilakukan dengan operator mod.

546
00:42:15,470 --> 00:42:20,040
Jadi sama seperti yang kita lakukan dengan Caesar dan hal-hal kripto,

547
00:42:20,040 --> 00:42:25,190
menggunakan mod, kita bisa mendapatkan sesuatu untuk membungkus dan terus

548
00:42:25,190 --> 00:42:28,090
sekitar dan sekitar dan sekitar dengan antrian kami,

549
00:42:28,090 --> 00:42:32,180
menjaga bahwa pointer kepala bergerak.

550
00:42:32,180 --> 00:42:38,840
Perhatikan ukuran yang selalu menghormati jumlah elemen benar-benar dalam antrian.

551
00:42:38,840 --> 00:42:43,110
Dan itu hanya pointer kepala yang terus bersepeda melalui.

552
00:42:43,110 --> 00:42:49,660
Jika kita melihat apa yang terjadi di sini, jika kita kembali ke awal,

553
00:42:49,660 --> 00:42:55,020
dan Anda hanya menonton apa yang terjadi pada kepala

554
00:42:55,020 --> 00:42:58,240
ketika kita enqueue sesuatu, tidak ada yang terjadi di kepala.

555
00:42:58,240 --> 00:43:00,970
Ketika kita enqueued sesuatu yang lain, tidak ada yang terjadi di kepala.

556
00:43:00,970 --> 00:43:04,130
Segera setelah kami dequeued sesuatu, kepala naik per satu.

557
00:43:04,130 --> 00:43:06,600
Kami enqueued sesuatu, tidak ada yang terjadi di kepala.

558
00:43:06,600 --> 00:43:11,060
Ketika kita dequeue sesuatu, tiba-tiba kepala akan bertambah.

559
00:43:11,060 --> 00:43:14,660
Ketika kita enqueue sesuatu, tidak ada yang terjadi di kepala.

560
00:43:14,660 --> 00:43:20,240
>> Apa yang akan terjadi pada saat ini jika kita dequeue sesuatu lagi?

561
00:43:20,240 --> 00:43:23,240
Setiap pikiran? Apa yang akan terjadi ke kepala?

562
00:43:23,240 --> 00:43:27,190
Apa yang harus terjadi pada kepala

563
00:43:27,190 --> 00:43:32,990
jika kita dequeue sesuatu yang lain?

564
00:43:32,990 --> 00:43:35,400
Kepala sekarang adalah di indeks 2,

565
00:43:35,400 --> 00:43:38,920
yang berarti bahwa kepala antrian string [2].

566
00:43:38,920 --> 00:43:44,280
[Mahasiswa] Yang mengembalikan 0? >> Ini harus kembali ke 0. Ini harus membungkus kembali sekitar, tepatnya.

567
00:43:44,280 --> 00:43:48,440
Sejauh ini, setiap kali kita disebut dequeue, kami telah menambahkan satu ke kepala,

568
00:43:48,440 --> 00:43:50,960
menambahkan satu ke kepala, menambahkan satu ke kepala, menambahkan satu ke kepala.

569
00:43:50,960 --> 00:43:58,400
Segera setelah itu pointer kepala sampai ke indeks terakhir dalam array kami,

570
00:43:58,400 --> 00:44:05,650
maka kita harus membungkusnya kembali sekitar ke awal, kembali ke 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Apakah yang menentukan kapasitas antrian dalam tumpukan?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Dalam hal ini, kami baru saja menggunakan sebuah konstanta # didefinisikan. Oke >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Di file c yang sebenarnya., Anda bisa masuk dan kotoran dengan itu sedikit

574
00:44:19,590 --> 00:44:21,710
dan menjadikannya sebagai besar atau sesedikit yang Anda inginkan.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Jadi, ketika Anda membuat antrian, bagaimana Anda membuat komputer tahu

576
00:44:25,310 --> 00:44:29,120
seberapa besar Anda ingin stack menjadi?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Itu pertanyaan yang bagus.

578
00:44:31,700 --> 00:44:34,800
Ada beberapa cara. Salah satunya adalah untuk hanya mendefinisikannya depan

579
00:44:34,800 --> 00:44:42,050
dan mengatakan ini akan menjadi antrian yang memiliki 4 elemen atau 50 elemen atau 10.000.

580
00:44:42,050 --> 00:44:45,430
Cara lain adalah dengan melakukan apa yang orang hacker edisi lakukan

581
00:44:45,430 --> 00:44:52,310
dan membuat fungsi untuk memiliki antrian Anda tumbuh secara dinamis sebagai hal-hal yang lebih akan ditambahkan masuk

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Jadi untuk pergi dengan pilihan pertama, apa sintaks yang Anda gunakan

583
00:44:54,740 --> 00:44:57,830
untuk memberitahu program apa ukuran antrian?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Jadi mari kita keluar dari hal ini.

585
00:45:04,780 --> 00:45:12,650
Aku masih di sini stack.c, jadi aku hanya akan menggulir ke atas sini.

586
00:45:12,650 --> 00:45:17,920
Dapatkah Anda melihat ini di sini? Ini adalah # define kapasitas 10.

587
00:45:17,920 --> 00:45:24,600
Dan ini hampir sintaks yang sama persis yang kita miliki untuk antrian.

588
00:45:24,600 --> 00:45:28,390
Kecuali dalam antrian, kita punya bahwa bidang struct ekstra di sini.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, saya pikir kapasitas berarti kemampuan untuk string.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Bahwa itu adalah panjang maksimum kata. >> Got it.

591
00:45:36,770 --> 00:45:41,180
Ya. Kapasitas di sini - itu adalah titik besar.

592
00:45:41,180 --> 00:45:44,000
Dan ini adalah sesuatu yang rumit

593
00:45:44,000 --> 00:45:49,480
karena apa yang kita telah menyatakan di sini adalah sebuah array dari char * s.

594
00:45:49,480 --> 00:45:52,770
Sebuah array dari pointer.

595
00:45:52,770 --> 00:45:56,690
Ini merupakan array dari karakter.

596
00:45:56,690 --> 00:46:01,690
Ini mungkin apa yang Anda lihat ketika Anda telah menyatakan buffer Anda untuk file I / O,

597
00:46:01,690 --> 00:46:06,840
ketika Anda telah membuat string secara manual pada stack.

598
00:46:06,840 --> 00:46:09,090
Namun, apa yang kita miliki di sini adalah sebuah array dari char * s.

599
00:46:09,090 --> 00:46:13,400
Jadi itu sebuah array dari pointer.

600
00:46:13,400 --> 00:46:18,350
Sebenarnya, jika kita tampilannya kembali keluar dan kami melihat apa yang terjadi di sini

601
00:46:18,350 --> 00:46:23,140
dalam presentasi, Anda melihat bahwa unsur-unsur yang sebenarnya, data karakter

602
00:46:23,140 --> 00:46:26,180
tidak disimpan dalam array itu sendiri.

603
00:46:26,180 --> 00:46:42,690
Apa yang disimpan dalam array kita di sini adalah pointer ke data karakter.

604
00:46:42,690 --> 00:46:52,560
Oke. Jadi kita telah melihat bagaimana ukuran antrian seperti dengan stack,

605
00:46:52,560 --> 00:46:58,670
ukuran selalu menghormati jumlah elemen saat ini dalam antrian.

606
00:46:58,670 --> 00:47:02,720
Setelah membuat 2 enqueues, ukuran 2.

607
00:47:02,720 --> 00:47:07,110
Setelah membuat dequeue ukuran sekarang adalah 1.

608
00:47:07,110 --> 00:47:09,330
Setelah membuat enqueue lain ukurannya kembali ke 2.

609
00:47:09,330 --> 00:47:12,340
Jadi ukuran pasti menghormati jumlah elemen dalam antrian,

610
00:47:12,340 --> 00:47:15,580
dan kemudian kepala hanya terus bersepeda.

611
00:47:15,580 --> 00:47:20,210
It goes dari 0-1-2,, 0-1-2 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Dan setiap kali kita sebut dequeue, pointer kepala akan bertambah dengan indeks berikutnya.

613
00:47:25,620 --> 00:47:29,930
Dan jika kepala adalah tentang untuk pergi ke, itu loop kembali sekitar ke 0.

614
00:47:29,930 --> 00:47:34,870
Maka dengan itu, kita dapat menulis fungsi dequeue.

615
00:47:34,870 --> 00:47:40,200
Dan kita akan meninggalkan fungsi enqueue bagi kalian untuk melaksanakan gantinya.

616
00:47:40,200 --> 00:47:45,880
>> Ketika kita dequeue elemen keluar dari antrian kami,

617
00:47:45,880 --> 00:47:55,490
apa hal pertama yang Daniel lakukan ketika kita mulai menulis fungsi pop untuk tumpukan?

618
00:47:55,490 --> 00:48:00,490
Biarkan aku mendengar dari seseorang yang tidak berbicara lagi.

619
00:48:00,490 --> 00:48:06,710
Mari kita lihat, Saad, apakah Anda ingat apa yang Daniel lakukan sebagai hal pertama ketika ia menulis pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Ada, itu - >> Dia diuji untuk sesuatu.

621
00:48:08,860 --> 00:48:12,140
[Saad] Jika ukuran lebih besar dari 0. >> Tepat.

622
00:48:12,140 --> 00:48:14,390
Dan apa itu pengujian untuk?

623
00:48:14,390 --> 00:48:19,090
[Saad] Yang sedang menguji untuk melihat apakah ada sesuatu di dalam array.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Ya. Tepat. Jadi Anda tidak bisa pop apa pun keluar dari tumpukan jika itu kosong.

625
00:48:23,210 --> 00:48:26,510
Demikian juga, Anda tidak bisa dequeue apa pun dari antrian jika itu kosong.

626
00:48:26,510 --> 00:48:30,420
Apa hal pertama yang harus kita lakukan dalam fungsi dequeue kami di sini, menurut Anda?

627
00:48:30,420 --> 00:48:33,860
[Saad] Jika ukuran lebih besar dari 0? >> Ya.

628
00:48:33,860 --> 00:48:37,710
Dalam hal ini, saya sebenarnya hanya diuji untuk melihat apakah itu adalah 0.

629
00:48:37,710 --> 00:48:42,240
Jika itu adalah 0, kita dapat kembali null.

630
00:48:42,240 --> 00:48:45,280
Tapi logika yang sama persis.

631
00:48:45,280 --> 00:48:49,110
Dan mari kita lanjutkan dengan ini.

632
00:48:49,110 --> 00:48:54,600
Jika ukuran tidak 0, di mana merupakan elemen yang ingin kita dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Pada kepala? >> Tepat.

634
00:48:58,550 --> 00:49:01,720
Kami hanya bisa mengeluarkan elemen pertama dalam antrian kami

635
00:49:01,720 --> 00:49:07,040
dengan mengakses elemen di kepala.

636
00:49:07,040 --> 00:49:14,630
Gila apa-apa.

637
00:49:14,630 --> 00:49:19,620
Setelah itu, apa yang harus kita lakukan? Apa yang telah terjadi?

638
00:49:19,620 --> 00:49:23,740
Apa hal lain yang kita bicarakan di dequeue?

639
00:49:23,740 --> 00:49:28,130
Dua hal yang harus terjadi, karena antrian kami telah berubah.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Mengurangi ukuran. >> Kita harus mengurangi ukuran, dan meningkatkan kepala? Tepat.

641
00:49:35,640 --> 00:49:40,600
Untuk meningkatkan kepala, kita tidak bisa hanya membabi buta meningkatkan kepala, ingat.

642
00:49:40,600 --> 00:49:45,080
Kita tidak bisa hanya melakukan queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Kita harus juga menyertakan mod dengan kapasitas.

644
00:49:51,630 --> 00:49:54,740
Dan mengapa kita mod oleh kapasitas, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Karena itu untuk membungkus sekitar. >> Tepat.

646
00:49:58,680 --> 00:50:04,750
Kami mod oleh kapasitas karena memiliki untuk membungkus kembali sekitar ke 0.

647
00:50:04,750 --> 00:50:07,400
Jadi sekarang, pada titik ini, kita bisa melakukan apa yang dikatakan Daniel.

648
00:50:07,400 --> 00:50:12,700
Kita bisa memundurkan ukuran.

649
00:50:12,700 --> 00:50:29,170
Dan kemudian kami hanya dapat mengembalikan elemen yang berada di bagian atas antrian.

650
00:50:29,170 --> 00:50:34,000
Ini terlihat agak degil pada awalnya. Anda mungkin memiliki pertanyaan. Maaf?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Kenapa pertama di bagian atas antrian? Mana itu pergi?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Ini berasal dari baris keempat dari bawah.

653
00:50:42,480 --> 00:50:46,060
Setelah kita uji untuk memastikan bahwa antrian kita tidak kosong,

654
00:50:46,060 --> 00:50:54,100
kita tarik keluar * char pertama, kita tarik keluar elemen yang duduk di indeks kepala

655
00:50:54,100 --> 00:50:58,680
dari array kita, array kami >> string, dan panggilan yang pertama?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Dan kami menyebutnya pertama. Ya.

657
00:51:04,500 --> 00:51:09,850
Hanya untuk menindaklanjuti itu, mengapa Anda berpikir kami harus melakukan itu?

658
00:51:09,850 --> 00:51:18,270
[Sam] Setiap pertama hanya kembali q.strings [q.head]? >> Ya.

659
00:51:18,270 --> 00:51:23,830
>> Karena kita melakukan ini berubah q.head dengan fungsi mod,

660
00:51:23,830 --> 00:51:27,810
dan tidak ada cara untuk melakukan itu dalam garis kembali juga.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Tepat. Kau tepat. Sam benar-benar spot on.

662
00:51:31,640 --> 00:51:36,800
Alasan kami harus menarik keluar elemen pertama dalam antrian dan menyimpannya ke dalam variabel

663
00:51:36,800 --> 00:51:43,030
karena baris ini di mana kami baru saja q.head,

664
00:51:43,030 --> 00:51:47,030
ada operator mod di sana adalah bukan sesuatu yang bisa kita lakukan

665
00:51:47,030 --> 00:51:51,230
dan telah berlaku pula di kepala tanpa - dalam satu baris.

666
00:51:51,230 --> 00:51:54,480
Jadi kita benar-benar harus menarik keluar elemen pertama, kemudian menyesuaikan kepala,

667
00:51:54,480 --> 00:52:00,430
menyesuaikan ukuran, dan kemudian kembali elemen yang kita ditarik keluar.

668
00:52:00,430 --> 00:52:02,680
Dan ini adalah sesuatu yang kita akan lihat datang kemudian dengan

669
00:52:02,680 --> 00:52:04,920
daftar terhubung, seperti yang kita bermain-main dengan mereka.

670
00:52:04,920 --> 00:52:08,410
Seringkali ketika Anda membebaskan atau membuang daftar link

671
00:52:08,410 --> 00:52:13,500
Anda perlu mengingat elemen berikutnya, pointer berikutnya dari sebuah linked list

672
00:52:13,500 --> 00:52:16,330
sebelum membuang satu saat.

673
00:52:16,330 --> 00:52:23,580
Karena jika tidak, anda membuang informasi apa yang tersisa dalam daftar.

674
00:52:23,580 --> 00:52:34,160
Sekarang, jika Anda pergi ke alat Anda, Anda membuka queue.c--x keluar dari ini.

675
00:52:34,160 --> 00:52:39,390
Jadi jika saya membuka queue.c, biarkan aku zoom di sini,

676
00:52:39,390 --> 00:52:44,970
Anda akan melihat bahwa Anda memiliki file yang sama tampak.

677
00:52:44,970 --> 00:52:49,200
Tampak serupa file apa yang kita punya sebelumnya dengan stack.c.

678
00:52:49,200 --> 00:52:54,690
Kami punya struct kami untuk antrian didefinisikan seperti yang kita lihat pada slide.

679
00:52:54,690 --> 00:52:59,870
>> Kami memiliki fungsi enqueue kami yang untuk Anda lakukan.

680
00:52:59,870 --> 00:53:04,340
Dan kami memiliki fungsi dequeue sini.

681
00:53:04,340 --> 00:53:06,870
Fungsi dequeue dalam file tersebut diimplementasikan,

682
00:53:06,870 --> 00:53:13,230
tapi aku akan meletakkannya kembali pada PowerPoint sehingga Anda dapat mengetik dalam, jika Anda ingin.

683
00:53:13,230 --> 00:53:16,690
Jadi selama 5 menit berikutnya atau lebih, kalian bekerja pada enqueue

684
00:53:16,690 --> 00:53:22,570
yang hampir kebalikan dari dequeue.

685
00:53:22,570 --> 00:53:29,560
Anda tidak harus menyesuaikan kepala ketika Anda enqueueing, tapi apa yang Anda harus menyesuaikan?

686
00:53:29,560 --> 00:53:38,920
Ukuran. Jadi, ketika Anda enqueue, kepala tetap tak tersentuh, ukuran akan berubah.

687
00:53:38,920 --> 00:53:46,920
Tapi itu tidak mengambil sedikit - Anda harus bermain-main dengan mod yang

688
00:53:46,920 --> 00:53:57,560
untuk mencari tahu persis apa indeks elemen baru harus dimasukkan pada.

689
00:53:57,560 --> 00:54:03,080
Jadi saya akan memberikan kalian sedikit, memasang dequeue kembali pada slide,

690
00:54:03,080 --> 00:54:05,200
dan seperti yang kalian punya pertanyaan, berteriak mereka sehingga kita dapat

691
00:54:05,200 --> 00:54:09,220
semua berbicara tentang mereka sebagai kelompok.

692
00:54:09,220 --> 00:54:13,960
Juga, dengan ukuran Anda jangan - ketika Anda menyesuaikan ukuran, Anda dapat selalu hanya -

693
00:54:13,960 --> 00:54:18,720
Anda harus mod ukuran pernah? [Daniel] No >> Anda tidak perlu mod ukuran, benar.

694
00:54:18,720 --> 00:54:24,260
Karena ukuran akan selalu, jika kau - dengan asumsi Anda mengelola hal-hal yang tepat,

695
00:54:24,260 --> 00:54:30,840
ukuran akan selalu berada di antara 0 dan 3.

696
00:54:30,840 --> 00:54:38,680
Di mana Anda harus mod ketika Anda melakukan enqueue?

697
00:54:38,680 --> 00:54:41,060
[Mahasiswa] Hanya untuk kepala. >> Hanya untuk kepala, tepatnya.

698
00:54:41,060 --> 00:54:44,620
Dan mengapa Anda harus mod sama sekali di enqueue?

699
00:54:44,620 --> 00:54:48,830
Ketika adalah situasi di mana Anda harus mod?

700
00:54:48,830 --> 00:54:53,630
[Siswa] Jika Anda memiliki barang-barang di ruang, seperti di ruang 1 dan 2,

701
00:54:53,630 --> 00:54:55,950
dan kemudian Anda perlu menambahkan sesuatu pada 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Ya, tepatnya. Jadi jika pointer kepala Anda di akhir,

703
00:55:02,570 --> 00:55:14,210
atau jika ukuran Anda ditambah kepala Anda lebih besar, atau lebih tepatnya, akan membungkus antrian.

704
00:55:14,210 --> 00:55:17,830
>> Jadi dalam situasi yang kita punya di sini pada slide sekarang,

705
00:55:17,830 --> 00:55:24,370
jika saya ingin enqueue sesuatu sekarang,

706
00:55:24,370 --> 00:55:31,110
kita ingin enqueue sesuatu di indeks 0.

707
00:55:31,110 --> 00:55:35,450
Jadi jika Anda melihat di mana 50 pergi, dan saya sebut enqueue 50,

708
00:55:35,450 --> 00:55:40,840
terbenam ada di bagian bawah. It goes dalam indeks 0.

709
00:55:40,840 --> 00:55:44,160
Ini menggantikan 'hi' yang sudah dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Jangan Anda mengurus hal itu di dequeue sudah?

711
00:55:46,210 --> 00:55:50,550
Mengapa ia melakukan sesuatu dengan kepala di enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, jadi Anda tidak memodifikasi kepala, maaf.

713
00:55:55,770 --> 00:56:02,310
Tapi Anda harus menggunakan operator mod saat Anda mengakses

714
00:56:02,310 --> 00:56:04,250
elemen yang ingin Anda enqueue saat Anda mengakses

715
00:56:04,250 --> 00:56:06,960
elemen berikutnya dalam antrian Anda.

716
00:56:06,960 --> 00:56:10,960
[Basil] saya tidak melakukan itu, dan saya mendapat "sukses" di sana.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, saya mengerti apa yang Anda katakan.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Jadi Anda tidak - Anda hanya lakukan di q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Ya. Saya baru saja mengubah sisi, aku tidak melakukan apa-apa dengan kepala.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Anda tidak benar-benar harus mengatur ulang kepala menjadi apa-apa,

721
00:56:24,300 --> 00:56:31,650
tetapi ketika Anda indeks ke dalam array string,

722
00:56:31,650 --> 00:56:39,500
Anda benar-benar harus pergi ke depan dan menghitung mana elemen berikutnya adalah,

723
00:56:39,500 --> 00:56:44,230
karena withe stack, elemen berikutnya dalam tumpukan Anda selalu

724
00:56:44,230 --> 00:56:48,740
pada indeks yang sesuai dengan ukurannya.

725
00:56:48,740 --> 00:56:55,850
Jika kita melihat kembali pada fungsi mendorong kami tumpukan,

726
00:56:55,850 --> 00:57:03,100
kita selalu bisa memetik dalam elemen baru kami tepat di ukuran indeks.

727
00:57:03,100 --> 00:57:06,710
Sedangkan dengan antrian, kita tidak bisa melakukan itu

728
00:57:06,710 --> 00:57:10,340
karena jika kita berada di situasi ini,

729
00:57:10,340 --> 00:57:18,130
jika kita enqueued 50 string baru kami akan pergi ke kanan di string [1]

730
00:57:18,130 --> 00:57:20,540
yang kita tidak ingin lakukan.

731
00:57:20,540 --> 00:57:41,200
Kami ingin memiliki string baru pergi pada indeks 0.

732
00:57:41,200 --> 00:57:44,320
>> Apakah orang - ya? [Mahasiswa] Saya punya pertanyaan, tapi itu tidak benar-benar berhubungan.

733
00:57:44,320 --> 00:57:48,160
Apa artinya ketika seseorang hanya panggilan sesuatu seperti pointer pred?

734
00:57:48,160 --> 00:57:51,260
Apa nama yang singkat untuk? Aku tahu itu hanya sebuah nama.

735
00:57:51,260 --> 00:57:59,110
[Hardison] pointer Pred? Mari kita lihat. Dalam konteks apa?

736
00:57:59,110 --> 00:58:01,790
[Mahasiswa] Itu untuk insert. Aku bisa meminta Anda nanti jika Anda ingin

737
00:58:01,790 --> 00:58:03,920
karena itu tidak benar-benar berhubungan, tapi aku hanya -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Dari kode insert Daud dari kuliah?

739
00:58:07,300 --> 00:58:10,860
Kita dapat menarik bahwa sampai dan berbicara tentang itu.

740
00:58:10,860 --> 00:58:15,550
Kita akan membicarakannya berikutnya, setelah kami mendapatkan daftar terkait.

741
00:58:15,550 --> 00:58:21,440
>> Jadi mari kita benar-benar cepat melihat apa fungsi enqueue terlihat seperti.

742
00:58:21,440 --> 00:58:26,530
Apa hal pertama yang orang coba lakukan sejalan enqueue Anda? Ke antrian ini?

743
00:58:26,530 --> 00:58:29,960
Mirip dengan apa yang Anda lakukan untuk mendorong tumpukan.

744
00:58:29,960 --> 00:58:32,080
Apa yang Anda lakukan, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, dipahami]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Tepat. Jika (q.size KAPASITAS ==) -

747
00:58:45,700 --> 00:58:54,720
Saya harus menempatkan kawat gigi saya di tempat yang tepat - return false.

748
00:58:54,720 --> 00:59:01,370
Zoom dalam sedikit. Oke.

749
00:59:01,370 --> 00:59:03,800
Sekarang apa hal berikutnya yang harus kami lakukan?

750
00:59:03,800 --> 00:59:11,370
Sama seperti dengan stack, dan dimasukkan di tempat yang tepat.

751
00:59:11,370 --> 00:59:16,010
Dan jadi apa adalah tempat yang tepat untuk memasukkan itu?

752
00:59:16,010 --> 00:59:23,170
Dengan tumpukan itu ukuran indeks, dengan ini itu tidak cukup itu.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Saya memiliki q.head--atau - q.strings >>? >> Ya.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPASITAS]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Kita mungkin ingin menempatkan tanda kurung di sekitar ini

756
00:59:42,740 --> 00:59:48,830
sehingga kita mendapatkan prioritas yang tepat dan jadi itulah cleart untuk semua orang.

757
00:59:48,830 --> 00:59:55,800
Dan menetapkan bahwa yang sama? >> Untuk str? >> Untuk str. Besar.

758
00:59:55,800 --> 01:00:00,160
Dan sekarang apa hal terakhir yang harus kita lakukan?

759
01:00:00,160 --> 01:00:06,780
Sama seperti yang kami lakukan dalam stack. >> Increment ukuran? >> Increment ukuran.

760
01:00:06,780 --> 01:00:13,830
Boom. Dan kemudian, karena kode pemula saja kembali palsu secara default,

761
01:00:13,830 --> 01:00:27,460
kita ingin mengubah ini menjadi true jika semuanya berjalan melalui dan semuanya berjalan dengan baik.

762
01:00:27,460 --> 01:00:33,050
Baiklah. Itu banyak informasi untuk bagian.

763
01:00:33,050 --> 01:00:39,480
Kami tidak cukup lebih. Kami ingin berbicara sangat cepat tentang sendiri-linked list.

764
01:00:39,480 --> 01:00:44,010
Aku akan menempatkan ini sehingga kita dapat kembali ke sini kelak.

765
01:00:44,010 --> 01:00:50,850
Tapi mari kita kembali ke presentasi kami untuk hanya beberapa slide.

766
01:00:50,850 --> 01:00:53,790
Jadi enqueue adalah TODO, sekarang kita sudah melakukannya.

767
01:00:53,790 --> 01:00:57,430
>> Sekarang mari kita lihat sendiri-linked list.

768
01:00:57,430 --> 01:01:00,040
Kami berbicara tentang ini sedikit lebih dalam kuliah.

769
01:01:00,040 --> 01:01:02,540
Berapa banyak dari kalian melihat demo di mana kita memiliki orang-orang

770
01:01:02,540 --> 01:01:08,220
canggung menunjuk ke tiap nomor lain dan memegang? >> Saya dalam hal itu.

771
01:01:08,220 --> 01:01:16,620
>> Apa yang kalian pikirkan? Apakah itu, mudah-mudahan demystify ini agak sedikit?

772
01:01:16,620 --> 01:01:25,990
Dengan daftar, ternyata kita berurusan dengan tipe ini bahwa kita akan memanggil node.

773
01:01:25,990 --> 01:01:32,520
Sedangkan dengan antrian dan tumpukan kami memiliki struct yang kita sebut antrian di stack,

774
01:01:32,520 --> 01:01:34,860
kami punya ini antrian baru di jenis tumpukan,

775
01:01:34,860 --> 01:01:39,240
daftar di sini adalah benar-benar hanya terdiri dari sekelompok node.

776
01:01:39,240 --> 01:01:45,920
Dengan cara yang sama bahwa string adalah hanya sekelompok karakter semua berbaris di samping satu sama lain.

777
01:01:45,920 --> 01:01:50,650
Sebuah linked list hanyalah sebuah node dan node lain dan lain node dan node lain.

778
01:01:50,650 --> 01:01:55,080
Dan bukannya menghancurkan semua node bersama-sama dan menyimpannya contiguously

779
01:01:55,080 --> 01:01:58,090
semua tepat di samping satu sama lain dalam memori,

780
01:01:58,090 --> 01:02:04,470
memiliki pointer ini selanjutnya memungkinkan kita untuk menyimpan node manapun, secara acak.

781
01:02:04,470 --> 01:02:10,500
Dan kemudian jenis kawat mereka semua bersama-sama menunjuk dari satu ke yang berikutnya.

782
01:02:10,500 --> 01:02:15,850
>> Dan apa keuntungan besar bahwa ini memiliki lebih dari array?

783
01:02:15,850 --> 01:02:21,680
Atas segala sesuatu menyimpan contiguously hanya terjebak di samping satu sama lain?

784
01:02:21,680 --> 01:02:24,190
Kau ingat? Ya? >> Alokasi memori dinamis?

785
01:02:24,190 --> 01:02:27,220
>> Alokasi memori dinamis dalam arti apa?

786
01:02:27,220 --> 01:02:31,780
[Siswa] Dalam Anda dapat tetap membuatnya lebih besar dan Anda tidak harus memindahkan seluruh array Anda?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Tepat. Jadi dengan array, bila Anda ingin menempatkan elemen baru ke tengah-tengah itu,

788
01:02:40,940 --> 01:02:45,320
Anda harus menggeser segalanya untuk membuat ruang.

789
01:02:45,320 --> 01:02:47,880
Dan seperti kita bicarakan dengan antrian,

790
01:02:47,880 --> 01:02:50,080
itu sebabnya kita menjaga pointer kepala,

791
01:02:50,080 --> 01:02:52,050
sehingga kita tidak terus-menerus hal pergeseran.

792
01:02:52,050 --> 01:02:54,520
Karena yang mendapat mahal jika Anda punya array besar

793
01:02:54,520 --> 01:02:57,130
dan Anda terus-menerus melakukan hal-sisipan acak.

794
01:02:57,130 --> 01:03:00,820
Sedangkan dengan daftar, yang harus Anda lakukan adalah membuangnya di sebuah node baru,

795
01:03:00,820 --> 01:03:06,330
menyesuaikan pointer, dan Anda sudah selesai.

796
01:03:06,330 --> 01:03:10,940
Apa yang menyebalkan tentang hal ini?

797
01:03:10,940 --> 01:03:16,830
Selain dari fakta bahwa itu tidak mudah untuk bekerja dengan sebagai array? Ya?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Nah, saya kira itu jauh lebih sulit untuk mengakses elemen tertentu dalam linked list?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Anda tidak bisa hanya melompat ke elemen sewenang-wenang di tengah daftar terkait.

800
01:03:30,470 --> 01:03:33,800
Bagaimana Anda harus melakukannya, bukan? >> Anda harus melangkah melalui seluruh hal.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Ya. Anda harus melalui satu per satu waktu, satu per satu.

802
01:03:35,660 --> 01:03:38,480
Ini adalah besar - itu adalah rasa sakit.

803
01:03:38,480 --> 01:03:41,550
Apa yang lain - ada lagi kejatuhan ini.

804
01:03:41,550 --> 01:03:45,340
[Basil] Anda tidak bisa maju dan mundur? Anda harus pergi satu arah?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Ya. Jadi bagaimana kita mengatasi itu, kadang-kadang?

806
01:03:48,570 --> 01:03:53,370
[Basil] Ganda-terkait daftar? >> Tepat. Ada daftar doubly-linked.

807
01:03:53,370 --> 01:03:55,540
Ada juga - maaf?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Apakah itu sama dengan menggunakan hal yang pred -

809
01:03:57,620 --> 01:04:01,090
Aku baru ingat, tidak bahwa apa hal pred adalah untuk?

810
01:04:01,090 --> 01:04:05,850
Bukankah itu di antara ganda dan tunggal?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Mari kita lihat apa sebenarnya yang dia lakukan.

812
01:04:10,020 --> 01:04:15,760
Jadi di sini kita pergi. Berikut daftar kode.

813
01:04:15,760 --> 01:04:25,620
Di sini kita memiliki predptr, di sini. Apakah ini apa yang Anda bicarakan?

814
01:04:25,620 --> 01:04:30,750
Jadi ini - dia membebaskan daftar dan dia mencoba untuk menyimpan pointer untuk itu.

815
01:04:30,750 --> 01:04:35,000
Ini bukan ganda, tunggal dihubungkan-daftar.

816
01:04:35,000 --> 01:04:40,090
Kita bisa bicara lebih lanjut tentang ini nanti karena ini berbicara tentang membebaskan daftar

817
01:04:40,090 --> 01:04:42,900
dan saya ingin menunjukkan beberapa hal lain terlebih dahulu.

818
01:04:42,900 --> 01:04:51,480
tapi itu hanya - itu mengingat nilai ptr

819
01:04:51,480 --> 01:04:54,170
[Mahasiswa] Oh, itu pointer mendahului? >> Ya.

820
01:04:54,170 --> 01:05:04,070
Sehingga kita kemudian dapat kenaikan ptr sendiri sebelum kita kemudian bebas apa predptr adalah.

821
01:05:04,070 --> 01:05:09,130
Karena kita tidak bisa ptr gratis dan kemudian memanggil ptr = ptr berikutnya, kan?

822
01:05:09,130 --> 01:05:11,260
Itu akan menjadi buruk.

823
01:05:11,260 --> 01:05:20,940
Jadi mari kita lihat, kembali ke orang ini.

824
01:05:20,940 --> 01:05:23,900
>> Hal lain yang buruk tentang daftar adalah bahwa sedangkan dengan array

825
01:05:23,900 --> 01:05:26,520
kita hanya memiliki semua elemen sendiri ditumpuk di samping satu sama lain,

826
01:05:26,520 --> 01:05:29,050
disini kami juga telah memperkenalkan pointer ini.

827
01:05:29,050 --> 01:05:34,060
Jadi ada sebuah bongkahan tambahan memori yang kita harus menggunakan

828
01:05:34,060 --> 01:05:37,910
untuk setiap elemen yang kita menyimpan dalam daftar kami.

829
01:05:37,910 --> 01:05:40,030
Kami mendapatkan fleksibilitas, tetapi datang pada biaya.

830
01:05:40,030 --> 01:05:42,230
Muncul dengan biaya waktu,

831
01:05:42,230 --> 01:05:45,270
dan ia datang dengan biaya memori juga.

832
01:05:45,270 --> 01:05:47,800
Waktu dalam arti bahwa kita sekarang harus melalui setiap elemen dalam array

833
01:05:47,800 --> 01:05:58,670
untuk menemukan satu pada indeks 10, atau yang akan menjadi indeks 10 dalam array.

834
01:05:58,670 --> 01:06:01,230
>> Hanya benar-benar cepat, ketika kita keluar diagram daftar ini,

835
01:06:01,230 --> 01:06:05,980
biasanya kita berpegang pada kepala daftar atau pointer pertama daftar

836
01:06:05,980 --> 01:06:08,010
dan perhatikan bahwa ini adalah pointer yang benar.

837
01:06:08,010 --> 01:06:11,100
Ini hanya 4 byte. Ini bukan sebuah simpul yang sebenarnya itu sendiri.

838
01:06:11,100 --> 01:06:17,120
Jadi Anda melihat bahwa itu tidak memiliki nilai int di dalamnya, tidak ada pointer berikutnya di dalamnya.

839
01:06:17,120 --> 01:06:20,790
Ini benar-benar hanya sebuah pointer.

840
01:06:20,790 --> 01:06:23,550
Ini akan menunjukkan sesuatu yang merupakan struct simpul yang sebenarnya.

841
01:06:23,550 --> 01:06:28,480
[Sam] Sebuah pointer yang disebut simpul? >> Ini - tidak ada. Ini adalah pointer ke sesuatu node jenis.

842
01:06:28,480 --> 01:06:32,540
Ini adalah pointer ke struct node. >> Oh, oke.

843
01:06:32,540 --> 01:06:36,870
Diagram pada kode, kiri di sebelah kanan.

844
01:06:36,870 --> 01:06:42,190
Kita dapat mengatur ke nol, yang merupakan cara yang baik untuk memulai.

845
01:06:42,190 --> 01:06:49,850
Bila Anda diagram itu, Anda juga menuliskannya sebagai null atau Anda meletakkan garis melalui itu seperti itu.

846
01:06:49,850 --> 01:06:53,910
>> Salah satu cara termudah untuk bekerja dengan daftar,

847
01:06:53,910 --> 01:06:57,430
dan kami meminta Anda tambahkan baik dan menambahkan untuk melihat perbedaan antara keduanya,

848
01:06:57,430 --> 01:07:01,320
namun mengawali pasti lebih mudah.

849
01:07:01,320 --> 01:07:05,790
Bila Anda tambahkan, ini adalah di mana Anda - ketika Anda tambahkan (7),

850
01:07:05,790 --> 01:07:10,050
Anda pergi dan membuat struct simpul

851
01:07:10,050 --> 01:07:13,870
dan Anda mengatur pertama yang menunjukkan hal itu, karena sekarang, karena kita prepended itu,

852
01:07:13,870 --> 01:07:17,240
itu akan berada di awal daftar.

853
01:07:17,240 --> 01:07:22,540
Jika kita tambahkan (3), yang menciptakan node lain, tapi sekarang 3 datang sebelum 7.

854
01:07:22,540 --> 01:07:31,130
Jadi kita pada dasarnya mendorong hal-hal ke daftar kami.

855
01:07:31,130 --> 01:07:34,720
Sekarang, Anda dapat melihat bahwa tambahkan, kadang-kadang orang menyebutnya mendorong,

856
01:07:34,720 --> 01:07:39,600
karena Anda mendorong elemen baru ke daftar Anda.

857
01:07:39,600 --> 01:07:43,270
Hal ini juga mudah untuk menghapus di depan daftar.

858
01:07:43,270 --> 01:07:45,650
Jadi orang sering akan memanggil pop itu.

859
01:07:45,650 --> 01:07:52,200
Dan dengan cara itu, Anda dapat meniru tumpukan menggunakan linked list.

860
01:07:52,200 --> 01:07:57,880
Whoops. Maaf, sekarang kita masuk ke append. Jadi di sini kita prepended (7), sekarang kita tambahkan (3).

861
01:07:57,880 --> 01:08:02,600
Jika kita prepended sesuatu yang lain ke daftar ini, jika kita prepended (4),

862
01:08:02,600 --> 01:08:06,540
maka kita akan memiliki 4 dan kemudian 3 dan kemudian 7.

863
01:08:06,540 --> 01:08:14,220
Jadi kita bisa pop dan menghapus 4, hapus 3, hapus 7.

864
01:08:14,220 --> 01:08:16,500
Seringkali cara yang lebih intuitif untuk berpikir tentang hal ini adalah dengan append.

865
01:08:16,500 --> 01:08:20,310
Jadi saya sudah digambarkan apa itu akan terlihat seperti dengan menambahkan di sini.

866
01:08:20,310 --> 01:08:23,380
Di sini, ditambahkan (7) tidak terlihat berbeda

867
01:08:23,380 --> 01:08:25,160
karena hanya ada satu elemen dalam daftar.

868
01:08:25,160 --> 01:08:28,620
Dan menambahkan (3) menempatkan itu di akhir.

869
01:08:28,620 --> 01:08:31,020
Mungkin Anda bisa lihat sekarang trik dengan append

870
01:08:31,020 --> 01:08:36,600
adalah karena kita hanya tahu di mana awal daftar ini,

871
01:08:36,600 --> 01:08:39,450
untuk menambahkan ke daftar Anda harus berjalan semua jalan melalui daftar

872
01:08:39,450 --> 01:08:46,500
untuk sampai ke akhir, berhenti, kemudian membangun simpul Anda dan segala sesuatu memetik bawah.

873
01:08:46,500 --> 01:08:50,590
Kawat semua hal atas.

874
01:08:50,590 --> 01:08:55,170
Jadi dengan tambahkan, karena kami hanya merobek ini benar-benar cepat,

875
01:08:55,170 --> 01:08:58,170
ketika Anda tambahkan ke daftar, itu cukup sederhana.

876
01:08:58,170 --> 01:09:02,960
>> Anda membuat simpul baru, melibatkan beberapa alokasi memori dinamis.

877
01:09:02,960 --> 01:09:09,830
Jadi di sini kita membuat struct node menggunakan malloc.

878
01:09:09,830 --> 01:09:14,710
Jadi kita menggunakan malloc karena itu akan menyisihkan memori bagi kita untuk nanti

879
01:09:14,710 --> 01:09:20,350
karena kita tidak ingin hal ini - kami ingin memori ini bertahan untuk waktu yang lama.

880
01:09:20,350 --> 01:09:25,350
Dan kita mendapatkan pointer ke ruang memori yang baru saja kita dialokasikan.

881
01:09:25,350 --> 01:09:29,260
Kami menggunakan ukuran node, kita tidak menjumlahkan bidang.

882
01:09:29,260 --> 01:09:31,899
Kami tidak secara manual menghasilkan jumlah byte,

883
01:09:31,899 --> 01:09:39,750
sebagai gantinya kita menggunakan sizeof sehingga kita tahu kita mendapatkan jumlah yang tepat byte.

884
01:09:39,750 --> 01:09:43,660
Kami pastikan untuk menguji bahwa panggilan malloc kami berhasil.

885
01:09:43,660 --> 01:09:47,939
Ini adalah sesuatu yang ingin Anda lakukan pada umumnya.

886
01:09:47,939 --> 01:09:52,590
Pada mesin modern, kehabisan memori bukanlah sesuatu yang mudah

887
01:09:52,590 --> 01:09:56,610
kecuali Anda mengalokasikan satu ton barang dan membuat daftar besar,

888
01:09:56,610 --> 01:10:02,220
tetapi jika Anda sedang membangun barang-barang untuk, katakanlah, seperti iPhone atau Android,

889
01:10:02,220 --> 01:10:05,230
Anda memiliki sumber daya memori terbatas, terutama jika Anda melakukan sesuatu yang intens.

890
01:10:05,230 --> 01:10:08,300
Jadi ada baiknya untuk masuk ke praktik.

891
01:10:08,300 --> 01:10:10,510
>> Perhatikan bahwa saya telah menggunakan beberapa fungsi yang berbeda di sini

892
01:10:10,510 --> 01:10:12,880
bahwa Anda telah melihat bahwa adalah jenis baru.

893
01:10:12,880 --> 01:10:15,870
Jadi fprintf adalah seperti printf

894
01:10:15,870 --> 01:10:21,320
kecuali argumen pertama adalah aliran yang ingin Anda cetak.

895
01:10:21,320 --> 01:10:23,900
Dalam kasus ini, kita ingin mencetak ke string standard error

896
01:10:23,900 --> 01:10:29,410
yang berbeda dari outstream standar.

897
01:10:29,410 --> 01:10:31,620
Secara default itu muncul di tempat yang sama.

898
01:10:31,620 --> 01:10:34,600
Hal ini juga mencetak keluar ke terminal, tetapi Anda bisa -

899
01:10:34,600 --> 01:10:38,790
menggunakan perintah-perintah tersebut Anda belajar tentang, teknik pengalihan

900
01:10:38,790 --> 01:10:42,290
Anda pelajari dalam video Tommy untuk mengatur masalah 4, Anda dapat langsung

901
01:10:42,290 --> 01:10:47,900
ke daerah yang berbeda, kemudian keluar, di sini, keluar program anda.

902
01:10:47,900 --> 01:10:50,440
Ini dasarnya seperti kembali dari main,

903
01:10:50,440 --> 01:10:53,600
kecuali kita menggunakan keluar karena di sini kembali tidak akan melakukan apa-apa.

904
01:10:53,600 --> 01:10:57,140
Kami tidak dalam utama, sehingga kembali tidak keluar dari program seperti yang kita inginkan.

905
01:10:57,140 --> 01:11:03,020
Jadi kita menggunakan fungsi keluar dan memberikan kode kesalahan.

906
01:11:03,020 --> 01:11:11,890
Maka di sini kita menetapkan bidang nilai node baru, bidang saya untuk menjadi sama dengan i, dan kemudian kita kawat itu.

907
01:11:11,890 --> 01:11:15,530
Kami mengatur pointer berikutnya node baru untuk menunjuk ke pertama,

908
01:11:15,530 --> 01:11:20,460
dan kemudian pertama sekarang akan menunjuk ke simpul baru.

909
01:11:20,460 --> 01:11:25,120
Ini baris pertama dari kode, kita benar-benar membangun node baru.

910
01:11:25,120 --> 01:11:27,280
Bukan yang terakhir dua baris fungsi ini, tetapi yang pertama.

911
01:11:27,280 --> 01:11:30,290
Anda benar-benar dapat menarik keluar ke fungsi, menjadi fungsi pembantu.

912
01:11:30,290 --> 01:11:32,560
Itu sering apa yang saya lakukan adalah, saya menariknya keluar ke fungsi,

913
01:11:32,560 --> 01:11:36,040
Saya menyebutnya sesuatu seperti simpul membangun,

914
01:11:36,040 --> 01:11:40,410
dan yang membuat fungsi tambahkan cukup kecil, itu hanya 3 baris kemudian.

915
01:11:40,410 --> 01:11:48,710
Saya membuat panggilan ke fungsi simpul saya membangun, dan kemudian saya segalanya kawat up.

916
01:11:48,710 --> 01:11:51,970
>> Hal terakhir yang saya ingin menunjukkan kepada Anda,

917
01:11:51,970 --> 01:11:54,030
dan aku akan membiarkan Anda melakukan append dan semua itu sendiri,

918
01:11:54,030 --> 01:11:57,500
adalah bagaimana iterate atas daftar.

919
01:11:57,500 --> 01:12:00,780
Ada banyak cara yang berbeda untuk iterate atas daftar.

920
01:12:00,780 --> 01:12:03,140
Dalam kasus ini, kita akan menemukan panjang daftar.

921
01:12:03,140 --> 01:12:06,570
Jadi kita mulai dengan panjang = 0.

922
01:12:06,570 --> 01:12:11,580
Ini sangat mirip dengan menulis strlen untuk string.

923
01:12:11,580 --> 01:12:17,780
Ini adalah apa yang saya ingin menunjukkan, ini untuk loop di sini.

924
01:12:17,780 --> 01:12:23,530
Ini terlihat agak funky, itu tidak biasa int i = 0, i <apapun, i + +.

925
01:12:23,530 --> 01:12:34,920
Sebaliknya itu menginisialisasi variabel n kami untuk menjadi awal dari daftar.

926
01:12:34,920 --> 01:12:40,620
Dan kemudian sedangkan variabel iterator kami tidak null, kita terus.

927
01:12:40,620 --> 01:12:46,340
Hal ini karena, dengan konvensi, akhir daftar kami akan null.

928
01:12:46,340 --> 01:12:48,770
Dan kemudian untuk kenaikan, daripada melakukan + +,

929
01:12:48,770 --> 01:12:57,010
setara dengan linked list dari + + adalah n = n-> berikutnya.

930
01:12:57,010 --> 01:13:00,410
>> Aku akan membiarkan Anda mengisi kekosongan di sini karena kita kehabisan waktu.

931
01:13:00,410 --> 01:13:09,300
Tapi ingatlah ini saat Anda bekerja pada psets spellr Anda.

932
01:13:09,300 --> 01:13:11,650
Daftar terhubung, jika Anda menerapkan tabel hash,

933
01:13:11,650 --> 01:13:14,010
pasti akan datang sangat berguna.

934
01:13:14,010 --> 01:13:21,780
Dan memiliki idiom ini untuk perulangan atas hal-hal yang akan membuat hidup jauh lebih mudah, mudah-mudahan.

935
01:13:21,780 --> 01:13:25,910
Ada pertanyaan, dengan cepat?

936
01:13:25,910 --> 01:13:28,920
[Sam] Akankah Anda mengirimkan SLL selesai dan sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Ya. Saya akan mengirimkan slide selesai dan menyelesaikan tumpukan SLL dan queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]