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

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

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

4
00:00:07,320 --> 00:00:11,840
Semua hak. Selamat datang kepada seksyen 6.

5
00:00:11,840 --> 00:00:14,690
Minggu ini, kita akan bercakap mengenai struktur data dalam seksyen,

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

7
00:00:19,780 --> 00:00:24,410
melakukan sekumpulan keseluruhan data penerokaan struktur yang berbeza.

8
00:00:24,410 --> 00:00:26,520
Terdapat sekumpulan cara yang berbeza anda boleh pergi dengan set masalah,

9
00:00:26,520 --> 00:00:31,570
dan data struktur yang lebih anda tahu mengenai, perkara-perkara yang lebih sejuk yang boleh anda lakukan.

10
00:00:31,570 --> 00:00:34,990
>> Jadi mari kita mulakan. Pertama kita akan bercakap tentang susunan,

11
00:00:34,990 --> 00:00:37,530
timbunan dan beratur struktur data yang kita akan bercakap tentang.

12
00:00:37,530 --> 00:00:40,560
Susunan dan beratur adalah benar-benar berguna apabila kita mula bercakap tentang graf,

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

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

15
00:00:52,820 --> 00:00:54,880
Penerangan dalam spesifikasi set masalah,

16
00:00:54,880 --> 00:00:59,260
jika anda tarik, ceramah tentang susunan sebagai serupa dengan

17
00:00:59,260 --> 00:01:05,239
timbunan dulang makan bahawa anda mempunyai di kafeteria di dewan makan

18
00:01:05,239 --> 00:01:09,680
di mana apabila kakitangan makan datang dan meletakkan dulang makan selepas mereka telah dibersihkan mereka,

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

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

21
00:01:15,050 --> 00:01:19,490
mereka tarik dulang, pertama satu atas, maka satu di bawah, maka satu di bawah yang.

22
00:01:19,490 --> 00:01:25,190
Jadi, pada hakikatnya, dulang pertama bahawa kakitangan makan meletakkan adalah yang terakhir yang mendapat diambil kira.

23
00:01:25,190 --> 00:01:32,330
Yang terakhir bahawa kakitangan makan diletakkan di atas adalah yang pertama yang mendapat diambil kira untuk makan malam.

24
00:01:32,330 --> 00:01:38,100
Dalam spec set masalah, yang anda boleh memuat turun jika anda tidak sudah,

25
00:01:38,100 --> 00:01:46,730
kita bercakap mengenai model stuktur timbunan data dengan menggunakan jenis ini struct.

26
00:01:46,730 --> 00:01:51,070
>> Jadi apa yang kita miliki di sini, ini adalah serupa dengan apa yang telah dibentangkan dalam kuliah,

27
00:01:51,070 --> 00:01:58,120
kecuali dalam kuliah kita mempersembahkan dengan ints berbanding char * s.

28
00:01:58,120 --> 00:02:06,250
Ini akan menjadi timbunan bahawa kedai apa?

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

30
00:02:09,009 --> 00:02:15,260
[Daniel] Rentetan? >> Kami akan menyimpan rentetan dalam timbunan ini, sebenarnya.

31
00:02:15,260 --> 00:02:20,950
Semua yang anda perlu untuk mewujudkan timbunan adalah array

32
00:02:20,950 --> 00:02:23,920
kapasiti tertentu, yang dalam kes ini,

33
00:02:23,920 --> 00:02:28,020
kapasiti akan berada dalam semua topi kerana ia adalah pemalar.

34
00:02:28,020 --> 00:02:36,340
Dan kemudian di samping array, semua kita perlu untuk mengesan saiz semasa array.

35
00:02:36,340 --> 00:02:38,980
Satu perkara yang perlu diambil perhatian di sini bahawa jenis sejuk

36
00:02:38,980 --> 00:02:47,060
adalah bahawa kita sedang mewujudkan struktur data disusun pada bahagian atas struktur data yang lain, array.

37
00:02:47,060 --> 00:02:50,110
Terdapat banyak cara yang berbeza untuk melaksanakan susunan.

38
00:02:50,110 --> 00:02:54,250
Kami tidak akan melakukan ia agak lagi, tetapi diharapkan selepas melakukan masalah berkaitan senarai,

39
00:02:54,250 --> 00:03:00,520
anda akan melihat bagaimana anda boleh melaksanakan timbunan di atas senarai berkaitan serta.

40
00:03:00,520 --> 00:03:02,640
Tetapi untuk sekarang, kita akan berpegang kepada tatasusunan.

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

42
00:03:06,350 --> 00:03:09,850
[Sam] Maaf, mengapa ia bahawa anda berkata timbunan di atas tali?

43
00:03:09,850 --> 00:03:13,440
Bagi saya, ia seolah-olah seperti rentetan berada dalam timbunan.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Kami mewujudkan, kami mengambil pelbagai struktur data kami -

45
00:03:16,790 --> 00:03:22,130
itulah persoalan yang besar. Jadi persoalannya ialah mengapa, bagi orang-orang yang menonton talian ini,

46
00:03:22,130 --> 00:03:24,140
mengapa kita mengatakan bahawa timbunan di atas tali,

47
00:03:24,140 --> 00:03:27,990
kerana di sini ia kelihatan seperti tali berada di dalam timbunan?

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

49
00:03:31,050 --> 00:03:34,660
Apa yang saya merujuk kepada adalah bahawa kita telah mendapat struktur data array.

50
00:03:34,660 --> 00:03:39,290
Kami telah mendapat pelbagai char * s, pelbagai rentetan,

51
00:03:39,290 --> 00:03:45,300
dan kita akan menambah bahawa dalam usaha untuk mewujudkan struktur data disusun.

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

53
00:03:48,620 --> 00:03:51,890
Kita boleh menggunakan array untuk membina timbunan.

54
00:03:51,890 --> 00:03:55,810
Jadi itulah di mana kita katakan bahawa timbunan dibina di atas pelbagai.

55
00:03:55,810 --> 00:04:02,510
Begitu juga, seperti saya katakan sebelum ini, kita boleh membina timbunan di atas senarai berkaitan.

56
00:04:02,510 --> 00:04:04,960
Sebaliknya menggunakan array untuk memegang elemen kita,

57
00:04:04,960 --> 00:04:10,070
kita boleh menggunakan senarai berpaut untuk memegang elemen kami dan membina timbunan sekitar itu.

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

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

60
00:04:14,960 --> 00:04:23,400
Di sebelah kiri, saya telah dibuang ke bawah apa yang struct timbunan akan kelihatan seperti dalam ingatan

61
00:04:23,400 --> 00:04:28,330
jika kapasiti telah # ditakrifkan untuk menjadi empat.

62
00:04:28,330 --> 00:04:33,490
Kami telah mendapat pelbagai empat unsur * char kami.

63
00:04:33,490 --> 00:04:38,110
Kami telah mendapat tali [0], rentetan [1], rentetan [2], rentetan [3],

64
00:04:38,110 --> 00:04:43,800
dan kemudian bahawa ruang terakhir bagi integer saiz kami.

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

66
00:04:46,270 --> 00:04:48,790
Ini adalah apa yang berlaku jika apa yang saya lakukan di sebelah kanan,

67
00:04:48,790 --> 00:04:55,790
yang akan menjadi kod saya, adalah untuk hanya mengisytiharkan struct, struct disusun dipanggil s.

68
00:04:55,790 --> 00:05:01,270
Ini adalah apa yang kita dapat. Ia meletakkan jejak ini dalam ingatan.

69
00:05:01,270 --> 00:05:05,590
Soalan pertama di sini ialah apakah kandungan struct timbunan ini?

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

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

72
00:05:13,300 --> 00:05:17,000
Apabila kita mengaku s timbunan, kita hanya membuang yang turun di atas ingatan.

73
00:05:17,000 --> 00:05:19,840
Ia adalah jenis seperti mengisytiharkan int i dan tidak Memulakan ia.

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

75
00:05:21,730 --> 00:05:27,690
tetapi ia tidak mungkin super helpful.

76
00:05:27,690 --> 00:05:32,680
Satu perkara yang anda mahu untuk sentiasa ingat untuk lakukan adalah memulakan apa sahaja yang perlu dimulakan.

77
00:05:32,680 --> 00:05:35,820
Dalam kes ini, kita akan memulakan saiz menjadi sifar,

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

79
00:05:39,960 --> 00:05:43,450
Kita boleh pergi ke hadapan dan memulakan semua petunjuk, semua s * char,

80
00:05:43,450 --> 00:05:49,670
untuk menjadi beberapa nilai yang difahami, mungkin batal.

81
00:05:49,670 --> 00:05:58,270
Tetapi ia tidak benar-benar perlu bahawa kita berbuat demikian.

82
00:05:58,270 --> 00:06:04,200
>> Kini, dua operasi utama pada susunan?

83
00:06:04,200 --> 00:06:07,610
Sesiapa yang ingat dari kuliah apa yang anda lakukan dengan susunan? Ya?

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

85
00:06:09,700 --> 00:06:13,810
Menolak dan pop dua operasi utama pada susunan.

86
00:06:13,810 --> 00:06:17,060
Dan apakah menolak lakukan? >> Ia meletakkan sesuatu ke atas

87
00:06:17,060 --> 00:06:19,300
tindanan, dan kemudian pop mengambil ia dimatikan.

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

89
00:06:23,150 --> 00:06:27,700
Ia adalah seperti kakitangan makan meletakkan dulang makan ke atas kaunter.

90
00:06:27,700 --> 00:06:33,630
Dan muncul mengambil dulang makan luar tindanan.

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

92
00:06:36,460 --> 00:06:39,720
apabila kita menolak perkara-perkara ke dalam tindanan.

93
00:06:39,720 --> 00:06:45,110
Jika kita untuk menolak rentetan 'hello' ke dalam tindanan kami,

94
00:06:45,110 --> 00:06:49,760
ini adalah apa gambarajah kami akan kelihatan seperti sekarang.

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

96
00:06:53,410 --> 00:06:56,530
Kami menolak ke dalam elemen pertama pelbagai rentetan kami

97
00:06:56,530 --> 00:07:01,420
dan kita upped kiraan saiz kami menjadi 1.

98
00:07:01,420 --> 00:07:05,340
Jadi, jika kita melihat perbezaan antara kedua-dua slaid, di sini adalah 0, di sini sebelum menolak.

99
00:07:05,340 --> 00:07:08,690
Berikut adalah selepas menolak.

100
00:07:08,690 --> 00:07:13,460
Sebelum menolak, selepas menolak.

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

102
00:07:16,860 --> 00:07:20,970
Ia adalah rentetan "hello", dan itulah ia.

103
00:07:20,970 --> 00:07:24,440
Segala-galanya dalam array, dalam pelbagai rentetan kami, masih sampah.

104
00:07:24,440 --> 00:07:27,070
Kami telah tidak dimulakan.

105
00:07:27,070 --> 00:07:29,410
Katakan kita menolak tali lain ke dalam tindanan kami.

106
00:07:29,410 --> 00:07:32,210
Kami akan menolak "dunia" pada masa ini.

107
00:07:32,210 --> 00:07:35,160
Jadi anda boleh melihat "dunia" di sini pergi di atas "hello",

108
00:07:35,160 --> 00:07:40,040
dan kiraan saiz pergi sehingga 2.

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

110
00:07:44,520 --> 00:07:51,110
Jika kita kembali, anda boleh melihat bagaimana kita hendak menolak perkara-perkara di atas timbunan.

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

112
00:07:53,320 --> 00:07:58,910
Apabila kita muncul sesuatu yang luar tindanan, apa yang berlaku?

113
00:07:58,910 --> 00:08:01,540
Sesiapa melihat perbezaan? Ia cukup halus.

114
00:08:01,540 --> 00:08:05,810
[Pelajar] Saiz. >> Yeah, saiz berubah.

115
00:08:05,810 --> 00:08:09,040
>> Apa lagi yang anda akan dijangka untuk menukar?

116
00:08:09,040 --> 00:08:14,280
[Pelajar] tali, terlalu. >> Hak. Rentetan terlalu.

117
00:08:14,280 --> 00:08:17,110
Ia ternyata bahawa apabila anda melakukannya dengan cara ini,

118
00:08:17,110 --> 00:08:21,960
kerana kita tidak meniru unsur-unsur ke dalam timbunan kami,

119
00:08:21,960 --> 00:08:24,670
kita sebenarnya tidak perlu berbuat apa-apa, kita hanya boleh menggunakan saiz

120
00:08:24,670 --> 00:08:28,630
untuk menjejaki beberapa perkara dalam pelbagai kami

121
00:08:28,630 --> 00:08:33,780
supaya apabila kita muncul semula, sekali lagi kita hanya penyusutan saiz kami ke 1.

122
00:08:33,780 --> 00:08:39,440
Tidak ada keperluan untuk benar-benar pergi dan overwrite apa-apa.

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

124
00:08:41,710 --> 00:08:46,520
Ia ternyata bahawa kita biasanya hanya meninggalkan perkara sahaja kerana ia adalah kerja yang kurang bagi kita untuk melakukan.

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

126
00:08:50,060 --> 00:08:54,150
Jadi apabila kita muncul dua kali off tindanan, semua yang tidak adalah susutan saiz beberapa kali.

127
00:08:54,150 --> 00:08:59,120
Dan sekali lagi, ini hanya kerana kita tidak menyalin perkara ke dalam tindanan kami.

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

129
00:09:01,320 --> 00:09:04,460
[Pelajar, difahami] >> Dan kemudian apa yang berlaku apabila anda menolak sesuatu lagi?

130
00:09:04,460 --> 00:09:08,570
Apabila anda menolak sesuatu lagi, di mana ia pergi?

131
00:09:08,570 --> 00:09:12,390
Di manakah ia pergi, Basil? >> Ke rentetan [1]? >> Hak.

132
00:09:12,390 --> 00:09:14,530
Mengapa tidak pergi ke rentetan [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Kerana ia terlupa bahawa ada apa-apa dalam rentetan [1] dan [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Tepat sekali. Timbunan kami, pada asasnya, "terlupa" bahawa ia telah berpegang kepada apa-apa

135
00:09:24,040 --> 00:09:29,480
dalam rentetan [1] atau rentetan [2], jadi apabila kita menolak "woot",

136
00:09:29,480 --> 00:09:36,670
ia hanya meletakkan itu ke dalam elemen pada tali [1].

137
00:09:36,670 --> 00:09:41,590
Adakah terdapat apa-apa soalan tentang bagaimana kerja-kerja ini, di peringkat asas?

138
00:09:41,590 --> 00:09:45,160
[Sam] Jadi ini tidak dinamik dalam apa jua cara, dari segi jumlah

139
00:09:45,160 --> 00:09:47,620
atau dari segi saiz tindanan?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Tepat sekali. Ini adalah - titik adalah bahawa ini tidak adalah timbunan yang dinamik growning.

141
00:09:56,750 --> 00:10:02,850
Ini adalah timbunan yang boleh memegang, paling, empat char * s, empat perkara-perkara yang paling.

142
00:10:02,850 --> 00:10:07,580
Jika kita cuba dan menolak satu perkara yang kelima, apa yang anda fikir patut berlaku?

143
00:10:07,580 --> 00:10:11,870
[Pelajar, difahami]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Tepat sekali. Terdapat beberapa perkara yang boleh berlaku.

145
00:10:14,600 --> 00:10:19,330
Ia mungkin seg bersalah, bergantung kepada apa yang kita -

146
00:10:19,330 --> 00:10:22,530
bagaimana sebenarnya kita telah melaksanakan back-end.

147
00:10:22,530 --> 00:10:31,740
Ia boleh overwrite. Ia boleh mempunyai bahawa buffer overflow bahawa kita bercakap tentang di dalam kelas.

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

149
00:10:35,240 --> 00:10:42,370
jika kita cuba untuk menolak satu perkara tambahan pada timbunan kami?

150
00:10:42,370 --> 00:10:44,550
Jadi anda menyebut suatu buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Apa yang mungkin menjadi perkara yang akan mendapat ditulis atau menghentak-hentak pada

152
00:10:47,870 --> 00:10:52,320
jika kita melimpah tidak sengaja dengan cuba untuk menolak satu perkara tambahan?

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

154
00:10:54,730 --> 00:10:58,440
Tetapi pada mulanya, apa yang mungkin berlaku? Bagaimana jika kita cuba untuk menolak satu perkara yang keempat?

155
00:10:58,440 --> 00:11:06,220
Ia mungkin menimpa saiz, sekurang-kurangnya dengan gambarajah memori ini bahawa kita telah mendapat.

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

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

158
00:11:16,030 --> 00:11:20,030
Kaedah menolak kami akan memulangkan nilai boolean,

159
00:11:20,030 --> 00:11:22,920
dan bahawa nilai boolean akan menjadi kenyataan jika menolak berjaya

160
00:11:22,920 --> 00:11:29,730
dan palsu jika kita tidak boleh menolak apa-apa yang lebih kerana timbunan penuh.

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

162
00:11:33,620 --> 00:11:36,400
Berikut adalah fungsi usaha kita.

163
00:11:36,400 --> 00:11:40,380
Fungsi push kami untuk timbunan akan mengambil tali untuk meletakkan pada timbunan.

164
00:11:40,380 --> 00:11:45,820
Ia akan kembali benar jika rentetan telah berjaya ditolak

165
00:11:45,820 --> 00:11:51,820
selainnya timbunan dan palsu.

166
00:11:51,820 --> 00:11:59,740
Apa-apa cadangan mengenai apa yang mungkin menjadi perkara yang baik pertama yang perlu dilakukan di sini?

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

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

169
00:12:23,320 --> 00:12:26,310
Jika saiz kapasiti, kami akan kembali palsu.

170
00:12:26,310 --> 00:12:29,270
Kita tidak boleh meletakkan apa-apa yang lebih dalam timbunan kami.

171
00:12:29,270 --> 00:12:36,900
Jika tidak, kita mahu meletakkan sesuatu di atas timbunan.

172
00:12:36,900 --> 00:12:41,670
Apakah "atas tindanan," pada mulanya?

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

174
00:12:43,650 --> 00:12:49,990
Apakah atas timbunan selepas ada satu perkara dalam tindanan? Missy, adakah anda tahu?

175
00:12:49,990 --> 00:12:52,720
[Missy] Satu. Saiz >> adalah salah, sebenarnya. Anda menyimpan menambah saiz,

176
00:12:52,720 --> 00:13:01,690
dan setiap masa anda meletakkan dalam elemen baru pada saiz indeks dalam array.

177
00:13:01,690 --> 00:13:05,470
Kita boleh melakukannya dengan jenis yang satu-liner, jika yang masuk akal.

178
00:13:05,470 --> 00:13:11,910
Jadi kita telah mendapat pelbagai rentetan kita, kita pergi untuk mengakses pada indeks saiz,

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 tidak ada menyalin rentetan berlaku di sini,

181
00:13:19,340 --> 00:13:29,680
tiada peruntukan memori yang dinamik?

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

183
00:13:34,440 --> 00:13:40,570
kerana kita telah disimpan tali di tempat yang sesuai dalam pelbagai,

184
00:13:40,570 --> 00:13:49,230
dan dia berkata bahawa kita terpaksa untuk menokokkan saiz oleh salah supaya kita sudah bersedia untuk menolak seterusnya.

185
00:13:49,230 --> 00:13:53,950
Jadi kita boleh berbuat demikian dengan s.size + +.

186
00:13:53,950 --> 00:13:59,330
Pada ketika ini, kita telah ditolak ke dalam pelbagai kami. Apakah perkara terakhir yang perlu kita lakukan?

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

188
00:14:10,110 --> 00:14:14,690
Jadi ia adalah agak mudah, kod yang agak mudah. Tidak terlalu banyak.

189
00:14:14,690 --> 00:14:17,070
Sebaik sahaja anda telah dibalut kepala anda sekitar bagaimana timbunan berfungsi,

190
00:14:17,070 --> 00:14:21,910
ini adalah agak mudah untuk melaksanakan.

191
00:14:21,910 --> 00:14:26,390
>> Sekarang, bahagian seterusnya ini adalah pop tali kira timbunan.

192
00:14:26,390 --> 00:14:29,410
Saya akan memberi anda semua sedikit masa untuk bekerja pada sedikit ini sedikit.

193
00:14:29,410 --> 00:14:34,320
Ia hampir asasnya belakang apa yang kita telah dilakukan di sini di tolak.

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

195
00:14:38,510 --> 00:14:48,160
Saya telah boot perkakas di sini, dan di dalam perkakas,

196
00:14:48,160 --> 00:14:53,600
Saya telah ditarik ke atas masalah menetapkan 5 spesifikasi.

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

198
00:15:02,560 --> 00:15:08,590
Pernahkah anda semua turun kod ini yang terletak di sini, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Semua hak. Jika anda tidak pernah dilakukan itu, berbuat demikian sekarang, benar-benar cepat.

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

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

202
00:15:25,090 --> 00:15:34,730
Ya, Sam? >> Saya mempunyai soalan tentang kenapa anda mengatakan 's kurungan s.string saiz = str?

203
00:15:34,730 --> 00:15:42,910
Apakah str? Apakah yang ditakrifkan tempat sebelum ini, atau - oh, str * char?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ya, betul-betul. Itu adalah hujah. >> Oh, okay. Maaf.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Kami menyatakan rentetan untuk menolak masuk

206
00:15:49,470 --> 00:15:55,220
Persoalan lain yang mungkin datang bahawa kita tidak benar-benar bercakap tentang di sini adalah

207
00:15:55,220 --> 00:15:58,810
kita ambil untuk diberikan bahawa kita mempunyai pembolehubah ini dipanggil s

208
00:15:58,810 --> 00:16:02,710
itu adalah dalam skop dan boleh diakses kepada kami.

209
00:16:02,710 --> 00:16:06,960
Kami mengambil untuk diberikan bahawa ini struct timbunan.

210
00:16:06,960 --> 00:16:08,930
Jadi melihat kembali pada kod ini menolak,

211
00:16:08,930 --> 00:16:13,450
anda boleh melihat bahawa kita sedang melakukan barangan dengan rentetan ini yang mendapat diluluskan pada

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

213
00:16:19,210 --> 00:16:23,020
Dalam kod yang kita akan melihat dalam arkib seksyen

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

215
00:16:27,100 --> 00:16:32,440
kita telah membuat timbunan kami struct pembolehubah global

216
00:16:32,440 --> 00:16:36,380
supaya kita boleh mempunyai akses kepada maklumat itu dalam semua fungsi yang berbeza kita

217
00:16:36,380 --> 00:16:40,630
tanpa perlu manual lulus di sekeliling dan lulus dengan rujukan,

218
00:16:40,630 --> 00:16:44,870
melakukan semua yang jenis barangan.

219
00:16:44,870 --> 00:16:52,280
Kami hanya menipu sedikit, jika anda akan, untuk membuat perkara yang lebih bagus.

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

221
00:16:57,430 --> 00:17:02,800
Selalunya, anda akan melihat orang melakukan ini jika mereka mempunyai satu struktur data yang besar

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

223
00:17:07,750 --> 00:17:09,560
>> Mari kita kembali kepada perkakas.

224
00:17:09,560 --> 00:17:15,240
Adakah semua orang berjaya mendapatkan section6.zip?

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

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

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

228
00:17:29,220 --> 00:17:32,840
dan anda menyenaraikan apa yang di sini, anda melihat bahawa anda telah mendapat tiga berbeza. c fail.

229
00:17:32,840 --> 00:17:38,350
Anda telah mendapat giliran, SLL, yang merupakan senarai berseorangan berkaitan, dan timbunan.

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

231
00:17:44,600 --> 00:17:47,330
anda boleh melihat bahawa kita telah mendapat ini struct ditakrifkan untuk kita,

232
00:17:47,330 --> 00:17:51,330
struct tepat bahawa kita hanya bercakap tentang di slaid.

233
00:17:51,330 --> 00:17:56,340
Kami telah mendapat pembolehubah global kami untuk timbunan,

234
00:17:56,340 --> 00:18:00,110
kita telah mendapat fungsi usaha kita,

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

236
00:18:04,230 --> 00:18:08,320
Saya akan meletakkan kod untuk menolak kembali pada slaid di sini,

237
00:18:08,320 --> 00:18:10,660
tetapi apa yang saya ingin anda semua untuk melakukan, dengan sedaya upaya anda,

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

239
00:18:13,790 --> 00:18:18,480
Sebaik sahaja anda telah dilaksanakan, anda boleh menyusun ini dengan membuat timbunan,

240
00:18:18,480 --> 00:18:22,540
dan kemudian menjalankan executable timbunan yang terhasil,

241
00:18:22,540 --> 00:18:28,390
dan yang akan menjalankan semua kod ujian ini turun di sini yang di utama.

242
00:18:28,390 --> 00:18:31,060
Utama dan menjaga sebenarnya membuat menolak dan pop panggilan

243
00:18:31,060 --> 00:18:33,220
dan memastikan bahawa segala-galanya akan melalui semua betul.

244
00:18:33,220 --> 00:18:36,820
Ia juga initializes saiz timbunan di sini

245
00:18:36,820 --> 00:18:39,780
jadi anda tidak perlu risau tentang Memulakan bahawa.

246
00:18:39,780 --> 00:18:42,310
Anda boleh menganggap bahawa ia telah dimulakan dengan betul

247
00:18:42,310 --> 00:18:48,000
oleh masa yang anda mengakses dalam fungsi pop.

248
00:18:48,000 --> 00:18:53,530
Adakah yang masuk akal?

249
00:18:53,530 --> 00:19:00,100
Jadi di sini kita pergi. Terdapat kod menolak.

250
00:19:00,100 --> 00:19:13,210
Saya akan memberikan anda lelaki 5 atau 10 minit.

251
00:19:13,210 --> 00:19:15,690
Dan jika anda mempunyai sebarang soalan dalam interim semasa anda pengekodan,

252
00:19:15,690 --> 00:19:17,710
sila bertanya kepada mereka dengan kuat.

253
00:19:17,710 --> 00:19:23,080
Jadi, jika anda sampai ke titik melekat, hanya meminta.

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

255
00:19:26,030 --> 00:19:28,160
Bekerja dengan jiran anda juga.

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

257
00:19:30,360 --> 00:19:34,200
Walaupun anda boleh menyalin pelaksanaan menolak jika anda ingin

258
00:19:34,200 --> 00:19:37,780
supaya ujian akan berfungsi.

259
00:19:37,780 --> 00:19:41,940
Kerana ia adalah sukar untuk menguji perkara-perkara yang mendapat ke -

260
00:19:41,940 --> 00:19:49,030
atau, ia adalah sukar untuk menguji pop perkara daripada timbunan jika tidak ada apa-apa dalam timbunan untuk memulakan dengan.

261
00:19:49,030 --> 00:19:55,250
>> Apakah pop sepatutnya kembali? Elemen dari atas timbunan.

262
00:19:55,250 --> 00:20:01,260
Ia sepatutnya untuk mendapatkan elemen luar atas timbunan

263
00:20:01,260 --> 00:20:05,780
dan kemudian penyusutan saiz tindanan,

264
00:20:05,780 --> 00:20:07,810
dan kini anda telah hilang elemen 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
[Pelajar, difahami]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Jadi apa yang berlaku jika anda berbuat demikian? [Pelajar, difahami]

268
00:20:28,810 --> 00:20:34,000
Apa yang akhirnya berlaku adalah anda mungkin mengakses sama ada

269
00:20:34,000 --> 00:20:37,350
elemen yang belum dimulakan lagi, jadi pengiraan

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

271
00:20:39,990 --> 00:20:46,260
Jadi di sini, jika anda perasan, di tolak, kita mengakses rentetan pada elemen s.size

272
00:20:46,260 --> 00:20:48,560
kerana ia adalah satu indeks baru.

273
00:20:48,560 --> 00:20:51,460
Ia adalah atas baru timbunan.

274
00:20:51,460 --> 00:21:01,100
Manakala dalam bentuk pop, s.size akan menjadi ruang seterusnya,

275
00:21:01,100 --> 00:21:05,210
ruang yang di atas semua elemen dalam timbunan 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
tetapi sebaliknya, ia adalah di bawahnya.

278
00:21:14,930 --> 00:21:19,640
>> Perkara lain yang perlu dilakukan apabila anda - dalam bentuk pop,

279
00:21:19,640 --> 00:21:22,030
anda perlu untuk penyusutan saiz.

280
00:21:22,030 --> 00:21:28,750
Jika anda ingat kembali kepada gambarajah kecil kami di sini,

281
00:21:28,750 --> 00:21:30,980
benar-benar, satu-satunya yang kita lihat berlaku apabila kita dipanggil pop

282
00:21:30,980 --> 00:21:36,150
adalah bahawa saiz ini menurun, pertama kepada 2, kemudian kepada 1.

283
00:21:36,150 --> 00:21:42,620
Kemudian apabila kita menolak elemen baru pada, ia akan pergi pada tempat yang betul.

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

285
00:21:49,610 --> 00:21:54,400
dan kemudian anda akan mahu pop elemen yang luar?

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

287
00:21:59,510 --> 00:22:07,730
Jika ini adalah timbunan kami pada ketika ini

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

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

290
00:22:16,150 --> 00:22:19,300
[Basil] Pada 2, tetapi ia akan pop 3. >> Hak.

291
00:22:19,300 --> 00:22:24,220
Supaya di mana saiz kami adalah 3, tetapi kita mahu pop elemen pada 2 indeks.

292
00:22:24,220 --> 00:22:29,900
Ia adalah yang jenis tipikal off oleh salah satu yang anda perlu dengan pengindeksan sifar tatasusunan.

293
00:22:29,900 --> 00:22:36,430
Jadi anda tidak mahu untuk pop elemen ketiga, tetapi elemen ketiga tidak adalah pada indeks 3.

294
00:22:36,430 --> 00:22:39,430
Dan sebab kita tidak perlu berbuat demikian 1 tolak apabila kita menolak

295
00:22:39,430 --> 00:22:44,120
kerana sekarang, anda dapati bahawa elemen yang paling atas,

296
00:22:44,120 --> 00:22:47,600
jika kita menolak sesuatu yang lain ke dalam tindanan pada ketika ini,

297
00:22:47,600 --> 00:22:50,360
kita mahu menolak ia pada indeks 3.

298
00:22:50,360 --> 00:23:03,550
Dan ia hanya kebetulan bahawa saiz dan indeks beratur apabila anda menolak.

299
00:23:03,550 --> 00:23:06,960
>> Siapa yang mendapat timbunan pelaksanaan bekerja?

300
00:23:06,960 --> 00:23:09,690
Anda telah mendapat timbunan kerja satu. Adakah anda mempunyai pop bekerja lagi?

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

302
00:23:11,890 --> 00:23:14,610
Program >> berjalan dan tidak seg Sesar, ia mencetak?

303
00:23:14,610 --> 00:23:17,520
Adakah ia mencetak "kejayaan" apabila anda menjalankan?

304
00:23:17,520 --> 00:23:22,630
Yeah. Buat timbunan, jalankan ia, jika ia mencetak keluar "kejayaan" dan tidak pergi ledakan,

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

306
00:23:26,000 --> 00:23:34,070
Semua hak. Mari kita pergi ke perkakas 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 berlaku di sini dengan pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, apakah perkara pertama yang anda lakukan?

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

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okay. Dan kenapa anda berbuat demikian?

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

313
00:24:05,610 --> 00:24:10,950
[Hardison] Hak. Anda mahu untuk menguji untuk memastikan bahawa s.size adalah lebih besar daripada 0;

314
00:24:10,950 --> 00:24:13,280
sebaliknya, apa yang anda mahu telah berlaku?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return batal? >> Kembali null, tepat.

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

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

318
00:24:25,890 --> 00:24:31,210
[Stella] Anda penyusutan saiz? >> Anda penyusutan saiz, okay.

319
00:24:31,210 --> 00:24:34,440
Jadi bagaimana anda berbuat demikian? >> S.size -.

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

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

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

323
00:24:48,560 --> 00:24:51,940
Jika tidak, anda kembali null. Ya, Sam?

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

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

326
00:24:58,430 --> 00:25:00,980
[Sam] Saya fikir kerana anda mengambil 1 daripada,

327
00:25:00,980 --> 00:25:04,290
maka anda akan kembali tidak satu yang mereka meminta.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Dan ini adalah hanya apa yang kita telah bercakap mengenai dengan isu ini keseluruhannya 0 indeks.

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

330
00:25:11,380 --> 00:25:15,650
Jika kita melihat lelaki ini di sini, anda boleh melihat bahawa apabila kita pop,

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

332
00:25:19,340 --> 00:25:25,200
>> Jadi kita mengurangkan saiz kami terlebih dahulu, maka saiz kami sepadan dengan indeks kami.

333
00:25:25,200 --> 00:25:39,650
Jika kita tidak penyusutan saiz pertama, maka kita perlu lakukan saiz -1 dan kemudian susutan.

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

335
00:25:45,270 --> 00:25:47,530
Sebarang pertanyaan mengenai perkara ini?

336
00:25:47,530 --> 00:25:54,050
Terdapat beberapa cara yang berbeza untuk menulis ini juga.

337
00:25:54,050 --> 00:26:03,290
Malah, kita boleh melakukan sesuatu yang - kita boleh melakukan satu-liner.

338
00:26:03,290 --> 00:26:05,770
Kita boleh melakukan pulangan satu line.

339
00:26:05,770 --> 00:26:12,980
Jadi, kita sebenarnya boleh SUSUTAN sebelum kita kembali dengan berbuat demikian.

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

341
00:26:18,320 --> 00:26:22,060
Itu menjadikan garis benar-benar padat.

342
00:26:22,060 --> 00:26:30,940
Jika perbezaan antara - saiz s dan s.size -

343
00:26:30,940 --> 00:26:40,130
adalah bahawa ini Postfix - mereka memanggilnya Postfix kerana datang selepas s.size -

344
00:26:40,130 --> 00:26:47,430
bermakna bahawa s.size dinilai bagi maksud mencari indeks

345
00:26:47,430 --> 00:26:50,410
kerana ia ketika apabila garis ini dilaksanakan,

346
00:26:50,410 --> 00:26:54,290
dan kemudian ini - berlaku selepas baris mendapat dilaksanakan.

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

348
00:27:00,340 --> 00:27:07,260
Dan itu bukan apa yang kita mahu, kerana kita mahu susutan berlaku dahulu.

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

350
00:27:10,990 --> 00:27:16,850
Kami akan mengakses elemen di atas satu bahawa kita benar-benar mahu untuk mengakses.

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

352
00:27:23,840 --> 00:27:29,620
[Hardison] Secara jujur, ia benar-benar bergantung.

353
00:27:29,620 --> 00:27:34,220
[Sam, difahami] >> Ya, ia bergantung. Anda boleh melakukan helah pengkompil

354
00:27:34,220 --> 00:27:41,580
untuk mendapatkan pengkompil untuk menyedari bahawa, biasanya, saya bayangkan.

355
00:27:41,580 --> 00:27:44,840
>> Jadi kita telah sebutkan sedikit tentang barangan ini pengoptimuman pengkompil

356
00:27:44,840 --> 00:27:47,400
yang boleh anda lakukan dalam menyusun,

357
00:27:47,400 --> 00:27:50,580
dan itulah jenis perkara yang pengkompil mungkin dapat memikirkan,

358
00:27:50,580 --> 00:27:54,710
seperti oh, hey, mungkin saya boleh lakukan ini semua dalam satu operasi,

359
00:27:54,710 --> 00:27:59,420
berbanding memuatkan pembolehubah saiz dari RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing, menyimpan ia kembali keluar, dan kemudian memuatkan kembali semula

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

362
00:28:08,000 --> 00:28:10,710
Tetapi biasanya, tidak, ini tidak adalah jenis perkara

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

364
00:28:20,770 --> 00:28:26,000
Sebarang pertanyaan lanjut mengenai susunan?

365
00:28:26,000 --> 00:28:31,360
>> Jadi menolak dan pop. Jika kalian mahu mencuba edisi hacker,

366
00:28:31,360 --> 00:28:33,660
apa yang kita lakukan dalam edisi penggodam sebenarnya pergi

367
00:28:33,660 --> 00:28:37,670
dan membuat timbunan ini berkembang dinamik.

368
00:28:37,670 --> 00:28:43,190
Cabaran terutamanya terdapat di sini dalam fungsi tolak,

369
00:28:43,190 --> 00:28:48,820
untuk memikirkan bagaimana untuk membuat pelbagai yang tumbuh

370
00:28:48,820 --> 00:28:52,450
sebagai anda menyimpan menolak lebih banyak unsur-unsur ke timbunan.

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

372
00:28:56,000 --> 00:29:00,080
Hanya panggilan - anda perlu ingat untuk mendapatkan panggilan ke malloc di sana dengan betul,

373
00:29:00,080 --> 00:29:03,310
dan kemudian memikirkan apabila anda pergi untuk memanggil realloc.

374
00:29:03,310 --> 00:29:06,090
Itulah cabaran yang menyeronokkan jika anda berminat.

375
00:29:06,090 --> 00:29:11,550
>> Tetapi buat masa ini, mari kita beralih, dan mari kita bercakap tentang beratur.

376
00:29:11,550 --> 00:29:15,680
Tatal melalui sini.

377
00:29:15,680 --> 00:29:19,340
Beratur adalah adik-beradik rapat timbunan.

378
00:29:19,340 --> 00:29:25,380
Jadi dalam tindanan, perkara-perkara yang telah dimasukkan ke dalam lepas

379
00:29:25,380 --> 00:29:28,810
adalah perkara pertama yang kemudian diubah.

380
00:29:28,810 --> 00:29:33,600
Kami telah mendapat ini terakhir dalam, mula-mula keluar, atau LIFO, pesanan.

381
00:29:33,600 --> 00:29:38,390
Manakala dalam barisan, seperti yang anda harapkan daripada apabila anda berdiri di barisan,

382
00:29:38,390 --> 00:29:41,980
orang pertama untuk mendapatkan dalam talian, perkara pertama untuk masuk ke dalam barisan,

383
00:29:41,980 --> 00:29:47,630
adalah perkara pertama yang mendapat diambil dari barisan.

384
00:29:47,630 --> 00:29:51,490
Beratur juga sering digunakan apabila kita berurusan dengan graf,

385
00:29:51,490 --> 00:29:55,560
seperti yang kita bercakap tentang secara ringkas dengan susunan,

386
00:29:55,560 --> 00:30:00,260
dan barisan juga berguna untuk sekumpulan perkara-perkara lain.

387
00:30:00,260 --> 00:30:06,180
Salah satu perkara yang datang sehingga sering cuba untuk mengekalkan, sebagai contoh,

388
00:30:06,180 --> 00:30:12,310
senarai disusun unsur.

389
00:30:12,310 --> 00:30:17,650
Dan anda boleh melakukan ini dengan pelbagai. Anda boleh mengekalkan senarai yang disusun perkara dalam pelbagai,

390
00:30:17,650 --> 00:30:20,650
tetapi di mana yang mendapat sukar maka anda sentiasa perlu mencari

391
00:30:20,650 --> 00:30:26,160
tempat yang sesuai untuk memasukkan perkara yang akan datang.

392
00:30:26,160 --> 00:30:28,250
Jadi jika anda mempunyai pelbagai nombor, 1 hingga 10,

393
00:30:28,250 --> 00:30:31,630
dan kemudian anda mahu untuk mengembangkan bahawa kepada semua nombor 1 melalui 100,

394
00:30:31,630 --> 00:30:33,670
dan anda mendapat nombor-nombor dalam susunan rawak dan cuba untuk memastikan segala-galanya

395
00:30:33,670 --> 00:30:40,650
disusun seperti anda pergi melalui, anda akhirnya perlu melakukan banyak berubah.

396
00:30:40,650 --> 00:30:43,910
Dengan jenis tertentu beratur dan jenis tertentu struktur data asas,

397
00:30:43,910 --> 00:30:46,670
anda sebenarnya boleh menyimpan ia agak mudah.

398
00:30:46,670 --> 00:30:50,640
Anda tidak perlu untuk menambah sesuatu dan kemudian rombakan keseluruhan perkara setiap kali.

399
00:30:50,640 --> 00:30:56,770
Nor adakah anda mempunyai untuk melakukan banyak peralihan unsur-unsur dalaman sekitar.

400
00:30:56,770 --> 00:31:02,990
Apabila kita melihat barisan, anda melihat bahawa - juga di queue.c kod seksyen -

401
00:31:02,990 --> 00:31:10,950
struct bahawa kita telah diberikan anda adalah benar-benar serupa dengan struct bahawa kita memberikan anda untuk timbunan.

402
00:31:10,950 --> 00:31:13,770
>> Terdapat satu pengecualian ini, dan bahawa satu pengecualian

403
00:31:13,770 --> 00:31:21,700
adalah bahawa kita ini integer tambahan dipanggil kepala,

404
00:31:21,700 --> 00:31:28,120
dan ketua di sini adalah untuk mengesan kepala barisan,

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

406
00:31:32,160 --> 00:31:37,470
Dengan timbunan, kita dapat menjejaki elemen yang kita kira-kira untuk mendapatkan,

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

408
00:31:40,800 --> 00:31:44,220
sedangkan dengan barisan, kita perlu untuk berurusan dengan hujung yang bertentangan.

409
00:31:44,220 --> 00:31:49,000
Kami cuba untuk jelujur perkara di akhir, tetapi kemudian kembali perkara-perkara dari hadapan.

410
00:31:49,000 --> 00:31:54,640
Jadi dengan berkesan, dengan kepala, kita mempunyai indeks permulaan barisan,

411
00:31:54,640 --> 00:31:58,920
dan saiz memberikan kita indeks akhir barisan

412
00:31:58,920 --> 00:32:03,730
supaya kita boleh mengambil perkara-perkara dari kepala dan menambah perkara yang ke ekor.

413
00:32:03,730 --> 00:32:06,890
Manakala dengan timbunan, kita hanya pernah berurusan dengan bahagian atas tindanan.

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

415
00:32:08,900 --> 00:32:12,220
Kami hanya menambah perkara ke atas dan mengambil sesuatu di luar bahagian atas

416
00:32:12,220 --> 00:32:17,470
jadi kita tidak perlu bahawa bidang tambahan di dalam struct kami.

417
00:32:17,470 --> 00:32:20,590
Adakah yang biasanya masuk akal?

418
00:32:20,590 --> 00:32:27,670
Semua hak. Ya, Charlotte? [Charlotte, difahami]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Itulah persoalan yang besar, dan yang merupakan salah satu yang datang dalam syarahan.

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 mahu menggunakan rentetan [0] sebagai ketua barisan.

422
00:32:41,400 --> 00:32:46,770
>> Jadi bayangkan bahawa kita mempunyai barisan kita, kita akan memanggilnya beratur.

423
00:32:46,770 --> 00:32:49,210
Pada mulanya, apabila kita baru sahaja instantiated,

424
00:32:49,210 --> 00:32:53,330
apabila kita baru sahaja diisytiharkan, kita telah tidak dimulakan apa-apa.

425
00:32:53,330 --> 00:32:56,790
Ia adalah semua sampah. Jadi, sudah tentu kita mahu pastikan bahawa kita memulakan

426
00:32:56,790 --> 00:33:00,950
kedua-dua saiz dan bidang kepala menjadi 0, sesuatu yang munasabah.

427
00:33:00,950 --> 00:33:05,770
Kita juga boleh pergi ke hadapan dan menyeimbangkan unsur-unsur dalam barisan kita.

428
00:33:05,770 --> 00:33:09,930
Dan untuk membuat ini patut gambarajah, notis bahawa kini giliran kami hanya boleh memegang tiga elemen;

429
00:33:09,930 --> 00:33:13,150
manakala timbunan kami boleh memegang empat, barisan kami hanya boleh memegang tiga.

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

431
00:33:18,680 --> 00:33:26,150
Perkara pertama yang berlaku di sini ialah kita enqueue string "hi".

432
00:33:26,150 --> 00:33:30,380
Dan seperti yang kita lakukan dengan timbunan, tiada apa yang sangat berbeza di sini,

433
00:33:30,380 --> 00:33:39,230
kita buang tali di tali [0] dan kenaikan saiz kami dengan 1.

434
00:33:39,230 --> 00:33:42,720
Kami enqueue "bye", ia mendapat diletakkan di atas.

435
00:33:42,720 --> 00:33:45,870
Jadi ini kelihatan seperti timbunan untuk sebahagian besar.

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

437
00:33:53,230 --> 00:33:56,330
Apa yang berlaku pada ketika ini apabila kita hendak dequeue sesuatu?

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

439
00:34:01,280 --> 00:34:04,110
[Basil] Rentetan [0]. >> Zero. Tepat betul, Basil.

440
00:34:04,110 --> 00:34:10,960
Kami mahu menghilangkan rentetan pertama, yang satu ini, "hi".

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

442
00:34:13,170 --> 00:34:17,010
Notis apabila kita muncul sesuatu yang luar tindanan, kita hanya mengubah saiz,

443
00:34:17,010 --> 00:34:22,080
tetapi di sini, kita telah mendapat beberapa perkara bahawa perubahan.

444
00:34:22,080 --> 00:34:27,440
Bukan sahaja melakukan perubahan saiz, tetapi perubahan kepala.

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

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

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

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

449
00:34:47,500 --> 00:34:54,340
Apa yang kepala lakukan yang kini menarik?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, kerana ia berubah - okay. Saya lihat.

451
00:34:56,449 --> 00:35:02,090
Kerana ketua - mana kepala menunjuk kepada perubahan dari segi lokasi.

452
00:35:02,090 --> 00:35:07,200
Ia tidak lagi sentiasa satu indeks sifar. >> Yeah, tepat.

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

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

455
00:35:20,590 --> 00:35:26,880
kerana kita selalu memanggil rentetan ini pada 0 indeks kepala barisan kita,

456
00:35:26,880 --> 00:35:30,170
maka kita akan perlu untuk beralih seluruh barisan ke bawah.

457
00:35:30,170 --> 00:35:36,010
Kami akan perlu untuk beralih "bye" dari rentetan [1] kepada rentetan [0].

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

459
00:35:38,760 --> 00:35:43,050
Dan kita akan mempunyai untuk melakukan ini untuk senarai keseluruhan unsur,

460
00:35:43,050 --> 00:35:45,110
pelbagai keseluruhan unsur.

461
00:35:45,110 --> 00:35:50,490
Dan apabila kita melakukan ini dengan pelbagai, yang mendapat benar-benar mahal.

462
00:35:50,490 --> 00:35:53,340
Jadi di sini, ia bukan masalah besar. Kami hanya mempunyai tiga elemen dalam pelbagai kami.

463
00:35:53,340 --> 00:35:57,230
Tetapi jika kita mempunyai giliran seribu elemen atau satu juta elemen,

464
00:35:57,230 --> 00:36:00,060
dan kemudian tiba-tiba, kami mula membuat sekumpulan dequeue panggilan semua dalam gelung,

465
00:36:00,060 --> 00:36:03,930
perkara-perkara yang benar-benar akan melambatkan kerana ia perubahan segala-galanya di bawah sentiasa.

466
00:36:03,930 --> 00:36:07,320
Anda tahu, beralih sebanyak 1, peralihan anjakan sebanyak 1, oleh 1, anjakan sebanyak 1.

467
00:36:07,320 --> 00:36:13,650
Sebaliknya, kita menggunakan kepala ini, kita panggil ia "penunjuk" walaupun ia tidak benar-benar penunjuk

468
00:36:13,650 --> 00:36:16,430
dalam erti kata yang ketat, ia bukan sejenis penunjuk.

469
00:36:16,430 --> 00:36:19,410
Ia bukan satu * int atau * char atau apa-apa seperti itu.

470
00:36:19,410 --> 00:36:28,930
Tetapi ia menunjuk atau menunjukkan kepala barisan kita. Yeah?

471
00:36:28,930 --> 00:36:38,800
>> [Pelajar] Bagaimanakah dequeue tahu hanya minggat apa yang ada di kepala?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Bagaimanakah dequeue tahu bagaimana untuk minggat apa yang di kepala? >> Hak, yeah.

473
00:36:43,620 --> 00:36:49,050
>> Apakah ia melihat hanya apa jua bidang kepala ditetapkan.

474
00:36:49,050 --> 00:36:52,710
Jadi dalam kes ini pertama, jika kita lihat di sini,

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

476
00:36:55,690 --> 00:37:00,500
[Hardison] Jadi ia hanya berkata okay, baik, unsur pada indeks 0, string "hi",

477
00:37:00,500 --> 00:37:03,050
adalah elemen di kepala barisan kita.

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

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

480
00:37:09,800 --> 00:37:14,540
Ya, Saad? >> Jadi kepala pada dasarnya menetapkan - ke mana anda hendak pergi kepada indeks ia?

481
00:37:14,540 --> 00:37:17,750
Itulah permulaan ia? >> Yeah. >> Okay.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Itulah menjadi permulaan baru untuk pelbagai kami.

483
00:37:22,900 --> 00:37:28,930
Jadi apabila anda dequeue sesuatu, semua yang anda perlu lakukan adalah mengakses elemen di index q.head,

484
00:37:28,930 --> 00:37:32,240
dan yang akan menjadi elemen yang anda mahu dequeue.

485
00:37:32,240 --> 00:37:34,930
Anda juga perlu penyusutan saiz.

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

487
00:37:39,430 --> 00:37:46,520
Kami dequeue, dan kini, 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
Di manakah elemen seterusnya pergi dalam barisan kami?

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

491
00:37:57,980 --> 00:38:02,240
Ke indeks mana ia akan pergi? [Pelajar] Rentetan [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] Kerana kini kepala adalah 1, maka itulah seperti permulaan senarai?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Hak. Dan apa yang menandakan akhir senarai?

495
00:38:21,220 --> 00:38:23,290
Apa yang kita menggunakan untuk menandakan akhir barisan kita?

496
00:38:23,290 --> 00:38:25,970
Kepala adalah ketua barisan kita, permulaan barisan kita.

497
00:38:25,970 --> 00:38:29,530
Apakah akhir barisan kita? [Pelajar] Saiz. >> Saiz, tepat.

498
00:38:29,530 --> 00:38:36,360
Jadi elemen baru kami pergi pada saiz, dan elemen-elemen yang kita mengambil off terkeluar di kepala.

499
00:38:36,360 --> 00:38:45,390
Apabila kita enqueue elemen seterusnya, kami meletakkan ia di saiz.

500
00:38:45,390 --> 00:38:48,530
[Pelajar] Sebelum anda meletakkan bahawa walaupun saiz adalah 1, betul-betul?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Hak. Jadi tidak cukup pada saiz. Saiz +, tidak +1, tetapi kepala +.

502
00:38:55,690 --> 00:38:59,990
Kerana kita beralih segala-galanya dengan jumlah kepala.

503
00:38:59,990 --> 00:39:14,270
Jadi di sini, kini kita telah mendapat giliran saiz 1 yang bermula 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
>> [Pelajar] Apa yang berlaku apabila anda dequeue rentetan [0], dan slot tali 'dalam ingatan

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

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

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

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

510
00:39:46,310 --> 00:39:51,760
supaya orang yang menguruskan struktur data tidak perlu bimbang

511
00:39:51,760 --> 00:39:53,650
kira-kira di mana semua orang penunjuk akan.

512
00:39:53,650 --> 00:39:56,000
Struktur data memegang kepada segala-galanya, memegang kepada semua salinan,

513
00:39:56,000 --> 00:39:59,580
untuk memastikan bahawa segala-galanya berterusan sewajarnya.

514
00:39:59,580 --> 00:40:03,140
Walau bagaimanapun, dalam kes ini, struktur data adil, kesederhanaan,

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

516
00:40:05,580 --> 00:40:08,630
[Pelajar] Jadi ini pelbagai berterusan? >> Ya.

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

518
00:40:14,350 --> 00:40:19,110
Ia hanya pelbagai standard seperti anda telah melihat,

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

520
00:40:24,280 --> 00:40:26,340
Adakah itu? >> Ya, saya hanya tertanya-tanya

521
00:40:26,340 --> 00:40:29,130
jika anda akhirnya akan kehabisan memori, sehingga ke tahap tertentu,

522
00:40:29,130 --> 00:40:32,330
jika anda mempunyai semua tempat kosong dalam pelbagai anda?

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

524
00:40:36,390 --> 00:40:41,530
>> Jika kita melihat apa yang berlaku sekarang pada ketika ini,

525
00:40:41,530 --> 00:40:46,350
kita telah dipenuhi barisan kami, ia kelihatan seperti.

526
00:40:46,350 --> 00:40:50,390
Tetapi kita tidak benar-benar dipenuhi barisan kita

527
00:40:50,390 --> 00:40:57,710
kerana kita mempunyai barisan yang saiz 2, tetapi ia bermula pada indeks 1,

528
00:40:57,710 --> 00:41:02,160
kerana itulah di mana penunjuk kepala kita.

529
00:41:02,160 --> 00:41:08,400
Seperti anda berkata, bahawa elemen pada rentetan [0], pada indeks 0, tidak benar-benar ada.

530
00:41:08,400 --> 00:41:10,450
Ia bukan dalam barisan kita lagi.

531
00:41:10,450 --> 00:41:16,460
Kami hanya tidak mengganggu untuk masuk dan overwrite ia apabila kita dequeued.

532
00:41:16,460 --> 00:41:18,700
Jadi, walaupun ia kelihatan seperti kita telah kehabisan memori, kita benar-benar tidak mempunyai.

533
00:41:18,700 --> 00:41:23,270
Itu spot adalah disediakan untuk kita gunakan.

534
00:41:23,270 --> 00:41:29,310
Tingkah laku yang sesuai, jika kita mencuba dan pertama dequeue sesuatu

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

536
00:41:34,420 --> 00:41:38,460
Sekarang giliran kami bermula pada indeks 2 dan adalah daripada 1 saiz.

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

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

539
00:41:47,880 --> 00:41:51,270
kerana ia masih boleh didapati untuk kita. Ya, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Adakah yang berlaku secara automatik?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Ia tidak berlaku agak secara automatik. Anda perlu lakukan matematik

542
00:41:56,150 --> 00:42:00,380
untuk membuat ia bekerja, tetapi pada dasarnya apa yang kami lakukan adalah kita telah hanya dibalut di sekeliling.

543
00:42:00,380 --> 00:42:04,070
[Saad] Dan ia mengapa jika ini mempunyai lubang di tengah-tengah itu?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Ia adalah jika kita boleh membuat matematik bersenam betul.

545
00:42:08,720 --> 00:42:15,470
>> Dan ternyata bahawa sebenarnya tidak begitu sukar untuk dilakukan dengan operator arena.

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

547
00:42:20,040 --> 00:42:25,190
menggunakan arena, kita boleh mendapatkan perkara untuk membalut di sekitar dan terus pergi

548
00:42:25,190 --> 00:42:28,090
sekitar dan di sekeliling dan sekitar dengan barisan kita,

549
00:42:28,090 --> 00:42:32,180
memastikan bahawa penunjuk kepala bergerak.

550
00:42:32,180 --> 00:42:38,840
Notis saiz yang sentiasa menghormati bilangan unsur sebenarnya dalam barisan.

551
00:42:38,840 --> 00:42:43,110
Dan ia hanya penunjuk kepala yang menyimpan berbasikal melalui.

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

553
00:42:49,660 --> 00:42:55,020
dan anda hanya menonton apa yang berlaku kepada kepala

554
00:42:55,020 --> 00:42:58,240
apabila kita enqueue sesuatu, tiada apa yang berlaku kepada ketua.

555
00:42:58,240 --> 00:43:00,970
Apabila kita enqueued sesuatu yang lain, tiada apa yang berlaku kepada ketua.

556
00:43:00,970 --> 00:43:04,130
Secepat kita dequeued sesuatu, kepala naik demi satu.

557
00:43:04,130 --> 00:43:06,600
Kami enqueued sesuatu, tiada apa yang berlaku kepada ketua.

558
00:43:06,600 --> 00:43:11,060
Apabila kita dequeue sesuatu, tiba-tiba kepala mendapat incremented.

559
00:43:11,060 --> 00:43:14,660
Apabila kita enqueue sesuatu, tiada apa yang berlaku kepada ketua.

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

561
00:43:20,240 --> 00:43:23,240
Mana-mana pemikiran? Apa yang akan berlaku kepada kepala?

562
00:43:23,240 --> 00:43:27,190
Apa yang sepatutnya berlaku kepada kepala

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

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

565
00:43:35,400 --> 00:43:38,920
yang bermaksud bahawa kepala barisan adalah rentetan [2].

566
00:43:38,920 --> 00:43:44,280
[Pelajar] Yang mengembalikan 0? >> Ia harus kembali kepada 0. Ia harus membalut kembali sekitar, betul-betul.

567
00:43:44,280 --> 00:43:48,440
Setakat ini, setiap kali kita dipanggil dequeue, kami telah menambah satu ke kepala,

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

569
00:43:50,960 --> 00:43:58,400
Secepat bahawa penunjuk kepala mendapat indeks terakhir dalam pelbagai kami,

570
00:43:58,400 --> 00:44:05,650
maka kita perlu untuk membalut kembali sekitar ke permulaan, kembali kepada 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Apa yang menentukan kapasiti beratur dalam timbunan?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Dalam kes ini, kita baru sahaja telah menggunakan malar # ditakrifkan. >> Okay.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Dalam fail sebenar c, anda boleh pergi di dalam dan kotoran sedikit

574
00:44:19,590 --> 00:44:21,710
dan menjadikan ia sebagai besar atau sesedikit yang anda mahu.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Jadi apabila anda membuat barisan, bagaimana anda membuat komputer tahu

576
00:44:25,310 --> 00:44:29,120
berapa besar anda mahu timbunan untuk menjadi?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Itulah persoalan yang besar.

578
00:44:31,700 --> 00:44:34,800
Terdapat beberapa cara. Salah satu adalah untuk hanya menentukan ia di depan

579
00:44:34,800 --> 00:44:42,050
dan mengatakan ini akan menjadi barisan yang mempunyai 4 elemen atau 50 elemen atau 10,000.

580
00:44:42,050 --> 00:44:45,430
Cara yang lain adalah untuk melakukan apa yang orang edisi penggodam melakukan

581
00:44:45,430 --> 00:44:52,310
dan mewujudkan fungsi untuk mempunyai baris gilir anda berkembang dinamik kerana lebih banyak perkara ditambah masuk

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Jadi untuk pergi dengan pilihan pertama, Bagaimana sintaks anda menggunakan

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

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

585
00:45:04,780 --> 00:45:12,650
Saya masih dalam stack.c sini, jadi saya hanya akan untuk menatal ke atas di sini.

586
00:45:12,650 --> 00:45:17,920
Bolehkah anda melihat hak ini di sini? Ini adalah # menentukan kapasiti 10.

587
00:45:17,920 --> 00:45:24,600
Dan ini adalah hampir sintaks tepat sama bahawa kita perlu untuk beratur.

588
00:45:24,600 --> 00:45:28,390
Kecuali dalam barisan, kita telah mendapat bahawa bidang struct tambahan di sini.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, saya fikir keupayaan bermakna kapasiti untuk tali.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Bahawa ia adalah panjang maksimum perkataan. >> Got ia.

591
00:45:36,770 --> 00:45:41,180
Yeah. Kapasiti di sini - bahawa adalah titik yang besar.

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

593
00:45:44,000 --> 00:45:49,480
kerana apa yang kita telah diisytiharkan di sini adalah pelbagai char * s.

594
00:45:49,480 --> 00:45:52,770
Pelbagai petunjuk.

595
00:45:52,770 --> 00:45:56,690
Ini adalah pelbagai aksara.

596
00:45:56,690 --> 00:46:01,690
Ini mungkin apa yang anda lihat apabila anda telah mengisytiharkan penampan anda untuk fail I / O,

597
00:46:01,690 --> 00:46:06,840
apabila anda telah mewujudkan rentetan manual pada timbunan.

598
00:46:06,840 --> 00:46:09,090
Walau bagaimanapun, apa yang kita telah mendapat di sini adalah pelbagai char * s.

599
00:46:09,090 --> 00:46:13,400
Jadi ia adalah pelbagai petunjuk.

600
00:46:13,400 --> 00:46:18,350
Sebenarnya, jika kita zum keluar dan kita melihat apa yang berlaku di sini

601
00:46:18,350 --> 00:46:23,140
dalam persembahan, anda lihat bahawa elemen sebenar, data watak

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

603
00:46:26,180 --> 00:46:42,690
Apa yang disimpan dalam pelbagai kami di sini adalah petunjuk untuk data watak.

604
00:46:42,690 --> 00:46:52,560
Okay. Jadi kita telah melihat bagaimana saiz barisan hanya suka dengan timbunan,

605
00:46:52,560 --> 00:46:58,670
saiz sentiasa menghormati bilangan unsur dalam barisan.

606
00:46:58,670 --> 00:47:02,720
Selepas membuat 2 enqueues, saiz ialah 2.

607
00:47:02,720 --> 00:47:07,110
Selepas membuat dequeue saiz kini 1.

608
00:47:07,110 --> 00:47:09,330
Selepas membuat enqueue lain saiz kembali sehingga 2.

609
00:47:09,330 --> 00:47:12,340
Jadi saiz pasti menghormati bilangan unsur dalam barisan,

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

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

612
00:47:20,210 --> 00:47:25,620
Dan setiap kali kita panggil dequeue, penunjuk kepala mendapat incremented ke indeks seterusnya.

613
00:47:25,620 --> 00:47:29,930
Dan jika kepala adalah kira-kira untuk pergi ke, ia gelung kembali sekitar kepada 0.

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

615
00:47:34,870 --> 00:47:40,200
Dan kami akan meninggalkan fungsi enqueue untuk anda semua untuk melaksanakan dan bukannya.

616
00:47:40,200 --> 00:47:45,880
>> Apabila kita dequeue elemen keluar barisan kita,

617
00:47:45,880 --> 00:47:55,490
apakah perkara pertama yang Daniel lakukan apabila kita mula menulis fungsi pop untuk susunan?

618
00:47:55,490 --> 00:48:00,490
Biar saya mendengar dari seseorang yang telah tidak bercakap lagi.

619
00:48:00,490 --> 00:48:06,710
Mari kita lihat, Saad, adakah anda ingat apa yang Daniel lakukan sebagai perkara yang pertama apabila dia menulis pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Terdapat, ia adalah - >> Beliau diuji untuk sesuatu.

621
00:48:08,860 --> 00:48:12,140
[Saad] Jika saiz adalah lebih besar daripada 0. >> Tepat sekali.

622
00:48:12,140 --> 00:48:14,390
Dan apa yang adalah bahawa ujian untuk?

623
00:48:14,390 --> 00:48:19,090
[Saad] Itu adalah ujian untuk melihat jika terdapat apa-apa yang di dalam array.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Tepat sekali. Jadi anda tidak boleh pop apa-apa daripada timbunan jika ia adalah kosong.

625
00:48:23,210 --> 00:48:26,510
Begitu juga, anda tidak boleh dequeue apa-apa daripada barisan jika ia kosong.

626
00:48:26,510 --> 00:48:30,420
Apakah perkara pertama yang kita harus lakukan dalam fungsi dequeue kami di sini, adakah anda fikir?

627
00:48:30,420 --> 00:48:33,860
[Saad] Jika saiz adalah lebih besar daripada 0? >> Yeah.

628
00:48:33,860 --> 00:48:37,710
Dalam kes ini, saya sebenarnya hanya diuji untuk melihat jika ia adalah 0.

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

630
00:48:42,240 --> 00:48:45,280
Tetapi logik yang sama yang tepat.

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

632
00:48:49,110 --> 00:48:54,600
Jika saiz tidak adalah 0, di mana adalah elemen yang kita mahu dequeue?

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

634
00:48:58,550 --> 00:49:01,720
Kami hanya boleh tarik keluar elemen pertama dalam barisan kita

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

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

637
00:49:14,630 --> 00:49:19,620
Selepas itu, apa yang patut kita buat? Apa yang telah berlaku?

638
00:49:19,620 --> 00:49:23,740
Apakah perkara lain yang kita bercakap tentang di dequeue?

639
00:49:23,740 --> 00:49:28,130
Dua perkara perlu berlaku, kerana barisan kita telah berubah.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Kurangkan saiz. >> Kami mempunyai untuk mengurangkan saiz, dan meningkatkan kepala? Tepat sekali.

641
00:49:35,640 --> 00:49:40,600
Untuk meningkatkan kepala, kita tidak boleh hanya membuta tuli meningkatkan kepala, ingat.

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

643
00:49:45,080 --> 00:49:51,630
Kita juga perlu termasuk arena ini oleh kapasiti.

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

645
00:49:54,740 --> 00:49:58,680
[Stella] Kerana ia mempunyai untuk membalut sekitar. >> Tepat sekali.

646
00:49:58,680 --> 00:50:04,750
Kami arena oleh kapasiti kerana ia mempunyai untuk membalut kembali sekitar kepada 0.

647
00:50:04,750 --> 00:50:07,400
Jadi sekarang, pada ketika ini, kita boleh melakukan apa yang Daniel berkata.

648
00:50:07,400 --> 00:50:12,700
Kita boleh penyusutan saiz.

649
00:50:12,700 --> 00:50:29,170
Dan kemudian kita hanya boleh mengembalikan elemen yang berada di atas barisan.

650
00:50:29,170 --> 00:50:34,000
Ia kelihatan jenis monggol pada mulanya. Anda mungkin mempunyai soalan. Maaf?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Mengapa pertama di atas barisan? Di manakah yang pergi?

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

653
00:50:42,480 --> 00:50:46,060
Selepas kita menguji untuk memastikan bahawa barisan 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
array kami, pelbagai rentetan >> kami, dan panggilan yang pertama?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Dan kita memanggilnya pertama. Yeah.

657
00:51:04,500 --> 00:51:09,850
Hanya untuk susulan pada itu, mengapa anda fikir kita terpaksa untuk berbuat demikian?

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

659
00:51:18,270 --> 00:51:23,830
>> Kerana kita lakukan ini berubah q.head itu dengan fungsi arena,

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

661
00:51:27,810 --> 00:51:31,640
[Hardison] Tepat sekali. Anda tempat di. Sam benar-benar tempat di.

662
00:51:31,640 --> 00:51:36,800
Sebab kita terpaksa tarik keluar elemen pertama dalam barisan kita dan menyimpannya ke dalam sebuah pembolehubah

663
00:51:36,800 --> 00:51:43,030
adalah kerana baris ini di mana kita telah hanya q.head,

664
00:51:43,030 --> 00:51:47,030
ada pengendali arena di sana bukan sesuatu yang boleh kita lakukan

665
00:51:47,030 --> 00:51:51,230
dan ia telah mengambil kesan ke atas kepala tanpa - dalam satu baris.

666
00:51:51,230 --> 00:51:54,480
Jadi kita sebenarnya mempunyai untuk menarik keluar elemen pertama, kemudian laraskan kepala,

667
00:51:54,480 --> 00:52:00,430
melaraskan saiz, 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
dikaitkan senarai, seperti yang kita bermain-main dengan mereka.

670
00:52:04,920 --> 00:52:08,410
Selalunya apabila anda membebaskan atau melupuskan senarai yang dipautkan

671
00:52:08,410 --> 00:52:13,500
anda perlu ingat elemen seterusnya, penunjuk seterusnya senarai berkaitan

672
00:52:13,500 --> 00:52:16,330
sebelum melupuskan semasa.

673
00:52:16,330 --> 00:52:23,580
Kerana jika tidak, anda buang maklumat apa yang ditinggalkan dalam senarai.

674
00:52:23,580 --> 00:52:34,160
Sekarang, jika anda pergi ke perkakas anda, anda membuka queue.c-x daripada ini.

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

676
00:52:39,390 --> 00:52:44,970
anda akan melihat bahawa anda mempunyai fail yang sama-cari.

677
00:52:44,970 --> 00:52:49,200
-Cari fail yang serupa dengan apa yang kita telah awal dengan stack.c.

678
00:52:49,200 --> 00:52:54,690
Kami telah mendapat struct kami untuk beratur ditakrifkan hanya seperti yang kita lihat pada slaid.

679
00:52:54,690 --> 00:52:59,870
>> Kami mempunyai fungsi enqueue kami yang adalah untuk anda lakukan.

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

681
00:53:04,340 --> 00:53:06,870
Fungsi dequeue dalam fail tidak disediakan,

682
00:53:06,870 --> 00:53:13,230
tetapi saya akan meletakkan ia kembali pada PowerPoint supaya anda boleh menaip dalam, jika anda ingin.

683
00:53:13,230 --> 00:53:16,690
Jadi untuk 5 minit akan datang atau lebih, anda semua bekerja pada enqueue

684
00:53:16,690 --> 00:53:22,570
yang hampir hanya bertentangan dequeue.

685
00:53:22,570 --> 00:53:29,560
Anda tidak perlu untuk menyesuaikan kepala apabila anda enqueueing, tetapi apa yang anda perlu untuk menyesuaikan diri?

686
00:53:29,560 --> 00:53:38,920
Saiz. Jadi, apabila anda enqueue, kepala kekal tidak disentuh, saiz mendapat berubah.

687
00:53:38,920 --> 00:53:46,920
Tetapi ia mengambil sedikit - anda akan mempunyai untuk bermain-main dengan arena yang

688
00:53:46,920 --> 00:53:57,560
untuk mengetahui dengan tepat apa indeks elemen baru perlu dimasukkan di.

689
00:53:57,560 --> 00:54:03,080
Jadi, saya akan memberikan anda semua sedikit, letakkan dequeue kembali pada slaid,

690
00:54:03,080 --> 00:54:05,200
dan kerana anda semua mempunyai soalan, menjerit mereka keluar supaya kita dapat

691
00:54:05,200 --> 00:54:09,220
semua bercakap tentang mereka sebagai satu kumpulan.

692
00:54:09,220 --> 00:54:13,960
Juga, dengan saiz anda Don 't - apabila anda menyesuaikan saiz, anda boleh sentiasa hanya -

693
00:54:13,960 --> 00:54:18,720
adakah anda mempunyai MOD saiz pernah? [Daniel] No >> Anda tidak perlu untuk MOD saiz, betul.

694
00:54:18,720 --> 00:54:24,260
Kerana saiz akan sentiasa, jika you're - menganggap anda menguruskan perkara sewajarnya,

695
00:54:24,260 --> 00:54:30,840
saiz akan sentiasa menjadi antara 0 dan 3.

696
00:54:30,840 --> 00:54:38,680
Di manakah anda perlu MOD apabila anda melakukan enqueue?

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

698
00:54:41,060 --> 00:54:44,620
Dan mengapa anda perlu MOD pada semua dalam enqueue?

699
00:54:44,620 --> 00:54:48,830
Bilakah adalah satu keadaan di mana anda akan perlu arena?

700
00:54:48,830 --> 00:54:53,630
[Pelajar] Jika anda mempunyai barangan di kawasan, seperti pada ruangan 1 dan 2,

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

702
00:54:55,950 --> 00:55:02,570
[Hardison] Yeah, tepat. Jadi jika penunjuk kepala anda adalah pada akhir sangat,

703
00:55:02,570 --> 00:55:14,210
atau jika saiz anda ditambah kepala anda adalah lebih besar, atau sebaliknya, akan membalut di sekitar barisan.

704
00:55:14,210 --> 00:55:17,830
>> Jadi dalam keadaan ini bahawa kita telah mendapat di sini pada slaid sekarang,

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

706
00:55:24,370 --> 00:55:31,110
kita mahu untuk enqueue sesuatu pada indeks 0.

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

708
00:55:35,450 --> 00:55:40,840
ia pergi bawah sana di bawah. Ia pergi di titik 0 indeks.

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

710
00:55:44,160 --> 00:55:46,210
[Daniel] Jangan anda mengambil penjagaan yang pada dequeue sudah?

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

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

713
00:55:55,770 --> 00:56:02,310
Tetapi anda perlu menggunakan pengendali arena apabila anda mengakses

714
00:56:02,310 --> 00:56:04,250
elemen yang anda mahu untuk enqueue apabila anda mengakses

715
00:56:04,250 --> 00:56:06,960
Elemen seterusnya dalam baris gilir anda.

716
00:56:06,960 --> 00:56:10,960
[Basil] saya tidak berbuat demikian, dan saya mendapat "kejayaan" di sana.

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

718
00:56:13,370 --> 00:56:16,240
[Hardison] Jadi anda didn't - anda hanya lakukan di q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Saya hanya berubah pihak, saya tidak berbuat apa-apa dengan kepala.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Anda tidak benar-benar mempunyai untuk menetapkan semula kepala untuk menjadi apa-apa,

721
00:56:24,300 --> 00:56:31,650
tetapi apabila anda indeks ke pelbagai rentetan,

722
00:56:31,650 --> 00:56:39,500
anda sebenarnya perlu pergi ke hadapan dan mengira di mana elemen seterusnya,

723
00:56:39,500 --> 00:56:44,230
kerana withe timbunan, Elemen seterusnya dalam timbunan anda sentiasa

724
00:56:44,230 --> 00:56:48,740
pada indeks sepadan dengan saiz.

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

726
00:56:55,850 --> 00:57:03,100
kita sentiasa boleh memetik dalam elemen baru kami betul-betul pada saiz indeks.

727
00:57:03,100 --> 00:57:06,710
Manakala dengan barisan, kita tidak boleh berbuat demikian

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

729
00:57:10,340 --> 00:57:18,130
jika kita enqueued 50 rentetan baru kami akan pergi tepat pada rentetan [1]

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

731
00:57:20,540 --> 00:57:41,200
Kami mahu mempunyai rentetan baru pergi pada indeks 0.

732
00:57:41,200 --> 00:57:44,320
>> Sesiapa Adakah - ya? [Pelajar] Saya mempunyai satu soalan tetapi ia tidak benar-benar berkaitan.

733
00:57:44,320 --> 00:57:48,160
Apa maknanya apabila seseorang hanya memerlukan sesuatu seperti penunjuk Pred?

734
00:57:48,160 --> 00:57:51,260
Apakah nama yang singkat? Saya tahu ia adalah sekadar nama.

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

736
00:57:59,110 --> 00:58:01,790
[Pelajar] Ia adalah untuk memasukkan. Saya boleh meminta anda kemudian jika anda mahu

737
00:58:01,790 --> 00:58:03,920
kerana ia tidak benar-benar berkaitan, tetapi saya hanya -

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

739
00:58:07,300 --> 00:58:10,860
Kita boleh tarik bahawa bangun dan bercakap tentang itu.

740
00:58:10,860 --> 00:58:15,550
Kami akan bercakap tentang yang seterusnya, sebaik sahaja kami sampai ke senarai berkaitan.

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

742
00:58:21,440 --> 00:58:26,530
Apakah perkara pertama yang orang cuba untuk melakukan selaras enqueue anda? Ke dalam barisan ini?

743
00:58:26,530 --> 00:58:29,960
Serupa dengan apa yang anda lakukan untuk menolak timbunan.

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

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

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

747
00:58:45,700 --> 00:58:54,720
Saya perlu meletakkan pendakap saya di tempat yang betul - kembali palsu.

748
00:58:54,720 --> 00:59:01,370
Zum ke dalam sedikit. Okay.

749
00:59:01,370 --> 00:59:03,800
Sekarang apa perkara yang akan datang yang kita terpaksa lakukan?

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

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

752
00:59:16,010 --> 00:59:23,170
Dengan timbunan ia adalah saiz indeks, dengan ini ia tidak cukup bahawa.

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

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

755
00:59:40,470 --> 00:59:42,740
[Hardison] Kita mungkin mahu untuk meletakkan kurungan sekitar ini

756
00:59:42,740 --> 00:59:48,830
supaya kita mendapat keutamaan yang sesuai dan sebagainya yang cleart kepada semua orang.

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

758
00:59:55,800 --> 01:00:00,160
Dan kini apa yang perkara terakhir yang perlu kita lakukan?

759
01:00:00,160 --> 01:00:06,780
Sama seperti kita lakukan dalam tindanan. >> Kenaikan saiz? >> Kenaikan saiz.

760
01:00:06,780 --> 01:00:13,830
Ledakan. Dan kemudian, sejak kod starter baru sahaja pulang palsu secara lalai,

761
01:00:13,830 --> 01:00:27,460
kita ingin menukar ini kepada true jika semua berjalan melalui dan semua berjalan lancar.

762
01:00:27,460 --> 01:00:33,050
Semua hak. Itulah banyak maklumat untuk seksyen.

763
01:00:33,050 --> 01:00:39,480
Kita tidak berada agak lebih. Kita mahu bercakap benar-benar cepat mengenai senarai berseorangan berkaitan.

764
01:00:39,480 --> 01:00:44,010
Saya akan meletakkan ini supaya kita boleh kembali kemudian.

765
01:00:44,010 --> 01:00:50,850
Tetapi mari kita kembali kepada persembahan kami untuk hanya beberapa slaid.

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

767
01:00:53,790 --> 01:00:57,430
>> Sekarang mari kita lihat pada senarai secara tunggal berkaitan.

768
01:00:57,430 --> 01:01:00,040
Kita bercakap mengenai lebih sedikit dalam kuliah.

769
01:01:00,040 --> 01:01:02,540
Berapa ramai daripada anda semua melihat demo di mana kita mempunyai orang

770
01:01:02,540 --> 01:01:08,220
canggung menunjuk kepada setiap nombor lain dan pegangan? >> Saya di bahawa.

771
01:01:08,220 --> 01:01:16,620
>> Apa yang anda semua berfikir? Lakukan itu, diharapkan demystify ini sedikit?

772
01:01:16,620 --> 01:01:25,990
Dengan senarai, ia ternyata bahawa kita berurusan dengan jenis ini yang kita akan memanggil nod.

773
01:01:25,990 --> 01:01:32,520
Manakala dengan beratur dan timbunan kita terpaksa structs bahawa kita akan memanggil beratur dalam timbunan,

774
01:01:32,520 --> 01:01:34,860
kita terpaksa ini barisan baru dalam jenis timbunan,

775
01:01:34,860 --> 01:01:39,240
di sini senarai benar-benar hanya terdiri sekumpulan nod.

776
01:01:39,240 --> 01:01:45,920
Dengan cara yang sama bahawa rentetan adalah hanya sekumpulan aksara semua berbaris bersebelahan antara satu sama lain.

777
01:01:45,920 --> 01:01:50,650
Satu senarai yang dikaitkan hanya nod dan nod yang lain dan satu lagi nod dan nod yang lain.

778
01:01:50,650 --> 01:01:55,080
Dan bukannya memecahkan semua nod bersama-sama dan menyimpan mereka contiguously

779
01:01:55,080 --> 01:01:58,090
semua betul-betul bersebelahan antara satu sama lain dalam ingatan,

780
01:01:58,090 --> 01:02:04,470
ini penunjuk seterusnya membolehkan kita untuk menyimpan nod di mana-mana, secara rawak.

781
01:02:04,470 --> 01:02:10,500
Dan kemudian jenis wayar mereka semua bersama-sama untuk menunjukkan dari satu kepada yang seterusnya.

782
01:02:10,500 --> 01:02:15,850
>> Dan apakah kelebihan besar bahawa ini mempunyai lebih array?

783
01:02:15,850 --> 01:02:21,680
Atas segala-galanya menyimpan contiguously hanya terperangkap bersebelahan antara satu sama lain?

784
01:02:21,680 --> 01:02:24,190
Anda ingat? Yeah? >> Peruntukan memori Dinamik?

785
01:02:24,190 --> 01:02:27,220
>> Memori peruntukan Dinamik dalam apa rasa?

786
01:02:27,220 --> 01:02:31,780
[Pelajar] Dalam bahawa anda boleh menyimpan menjadikan ia lebih besar dan anda tidak perlu untuk menggerakkan pelbagai keseluruhan anda?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Tepat sekali. Jadi dengan array, apabila anda mahu untuk meletakkan elemen baru ke tengah-tengah itu,

788
01:02:40,940 --> 01:02:45,320
anda perlu beralih segala-galanya untuk membuat ruang.

789
01:02:45,320 --> 01:02:47,880
Dan seperti yang kita bercakap tentang dengan barisan,

790
01:02:47,880 --> 01:02:50,080
itulah sebabnya kita memastikan bahawa penunjuk kepala,

791
01:02:50,080 --> 01:02:52,050
supaya kita tidak sentiasa berubah perkara-perkara.

792
01:02:52,050 --> 01:02:54,520
Kerana yang mendapat mahal jika anda telah mendapat pelbagai besar

793
01:02:54,520 --> 01:02:57,130
dan anda sentiasa melakukan ini sisipan rawak.

794
01:02:57,130 --> 01:03:00,820
Manakala dengan senarai, semua yang anda perlu lakukan adalah membuang ia pada nod baru,

795
01:03:00,820 --> 01:03:06,330
menyesuaikan petunjuk, dan anda selesai.

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

797
01:03:10,940 --> 01:03:16,830
Selain daripada fakta bahawa ia tidak mudah untuk bekerja dengan sebagai array? Yeah?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Well, saya rasa ia adalah lebih sukar untuk mengakses elemen tertentu dalam senarai dikaitkan?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Anda tidak boleh hanya melompat kepada elemen sewenang-wenangnya di tengah-tengah senarai dikaitkan anda.

800
01:03:30,470 --> 01:03:33,800
Bagaimana anda perlu lakukan ia sebaliknya? >> Anda perlu melangkah melalui perkara keseluruhan.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Anda perlu pergi melalui satu pada satu-satu masa, pada satu masa.

802
01:03:35,660 --> 01:03:38,480
Ia adalah besar - ia 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 boleh pergi ke hadapan dan ke belakang? Anda perlu pergi ke satu arah?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Jadi bagaimana kita menyelesaikan itu, kadang-kadang?

806
01:03:48,570 --> 01:03:53,370
[Basil] duanya adalah terpakai dikaitkan senarai? >> Tepat sekali. Terdapat senarai duanya adalah terpakai dikaitkan.

807
01:03:53,370 --> 01:03:55,540
Terdapat juga - maaf?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Adakah itu sama seperti menggunakan perkara Pred bahawa -

809
01:03:57,620 --> 01:04:01,090
Saya hanya teringat, tidak bahawa apa perkara Pred adalah untuk?

810
01:04:01,090 --> 01:04:05,850
Adakah tidak bahawa di antara duanya adalah terpakai dan berseorangan?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Mari kita melihat apa sebenarnya yang dia lakukan.

812
01:04:10,020 --> 01:04:15,760
Jadi di sini kita pergi. Berikut adalah senarai kod.

813
01:04:15,760 --> 01:04:25,620
Di sini kita mempunyai predptr, di sini. Adakah ini apa yang anda bercakap tentang?

814
01:04:25,620 --> 01:04:30,750
Jadi ini adalah - dia membebaskan senarai dan dia cuba untuk menyimpan penunjuk untuk ia.

815
01:04:30,750 --> 01:04:35,000
Ini bukan duanya adalah terpakai, secara tunggal dikaitkan senarai.

816
01:04:35,000 --> 01:04:40,090
Kita boleh bercakap lebih lanjut tentang perkara ini kemudian kerana ini sedang bercakap tentang membebaskan senarai

817
01:04:40,090 --> 01:04:42,900
dan saya ingin menunjukkan beberapa barangan lain terlebih dahulu.

818
01:04:42,900 --> 01:04:51,480
tetapi ia hanya - ia mengingat nilai ptr

819
01:04:51,480 --> 01:04:54,170
[Pelajar] Oh, ia penunjuk sebelumnya? >> Yeah.

820
01:04:54,170 --> 01:05:04,070
Supaya kita boleh kenaikan ptr sendiri sebelum kita kemudian bebas apa predptr.

821
01:05:04,070 --> 01:05:09,130
Kerana kita tidak boleh bebas ptr dan kemudian memanggil ptr = ptr seterusnya, 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 kepada lelaki ini.

824
01:05:20,940 --> 01:05:23,900
>> Perkara lain yang buruk tentang senarai adalah bahawa manakala dengan pelbagai

825
01:05:23,900 --> 01:05:26,520
kita hanya mempunyai semua unsur-unsur sendiri disusun bersebelahan antara satu sama lain,

826
01:05:26,520 --> 01:05:29,050
di sini kita juga telah diperkenalkan penunjuk ini.

827
01:05:29,050 --> 01:05:34,060
Jadi ada sebahagian tambahan ingatan bahawa kita perlu menggunakan

828
01:05:34,060 --> 01:05:37,910
untuk setiap elemen yang kita sedang menyimpan dalam senarai kami.

829
01:05:37,910 --> 01:05:40,030
Kita mendapat fleksibiliti, tetapi ia datang pada kos.

830
01:05:40,030 --> 01:05:42,230
Ia datang dengan kos masa ini,

831
01:05:42,230 --> 01:05:45,270
dan ia datang dengan kos memori ini juga.

832
01:05:45,270 --> 01:05:47,800
Masa dalam erti kata bahawa kita kini mempunyai untuk pergi melalui setiap elemen dalam array

833
01:05:47,800 --> 01:05:58,670
untuk mencari satu pada indeks 10, atau yang sepatutnya index 10 dalam array.

834
01:05:58,670 --> 01:06:01,230
>> Hanya benar-benar cepat, apabila kita gambarajah keluar senarai ini,

835
01:06:01,230 --> 01:06:05,980
biasanya kita berpegang kepada kepala senarai atau penunjuk pertama senarai

836
01:06:05,980 --> 01:06:08,010
dan ambil perhatian bahawa ini adalah satu penunjuk yang benar.

837
01:06:08,010 --> 01:06:11,100
Ia hanya 4 bait. Ia bukan satu nod sebenar itu sendiri.

838
01:06:11,100 --> 01:06:17,120
Jadi anda lihat bahawa ia tidak mempunyai nilai int di dalamnya, tiada penunjuk seterusnya di dalamnya.

839
01:06:17,120 --> 01:06:20,790
Ia adalah benar-benar hanya penunjuk.

840
01:06:20,790 --> 01:06:23,550
Ia akan menunjukkan kepada sesuatu yang merupakan struct nod sebenar.

841
01:06:23,550 --> 01:06:28,480
[Sam] Satu penunjuk yang dipanggil nod? >> Ini adalah - tidak. Ini adalah penunjuk kepada sesuatu nod jenis.

842
01:06:28,480 --> 01:06:32,540
Ia adalah penunjuk kepada struct nod. >> Oh, okay.

843
01:06:32,540 --> 01:06:36,870
Rajah pada kod kiri, di sebelah kanan.

844
01:06:36,870 --> 01:06:42,190
Kita boleh menetapkan ia untuk batal, yang merupakan cara yang baik untuk memulakan.

845
01:06:42,190 --> 01:06:49,850
Apabila anda gambarajah ia, sama ada anda menulis ia sebagai batal atau anda meletakkan garisan melalui ia seperti itu.

846
01:06:49,850 --> 01:06:53,910
>> Salah satu cara paling mudah untuk bekerja dengan senarai,

847
01:06:53,910 --> 01:06:57,430
dan kami meminta anda Prepend kedua-dua dan melampirkan untuk melihat perbezaan antara kedua-dua,

848
01:06:57,430 --> 01:07:01,320
tetapi prepending memang mudah.

849
01:07:01,320 --> 01:07:05,790
Apabila anda Prepend, ini adalah di mana anda - apabila anda Prepend (7),

850
01:07:05,790 --> 01:07:10,050
anda pergi dan mewujudkan struct nod

851
01:07:10,050 --> 01:07:13,870
dan anda menetapkan pertama untuk menunjukkan kepadanya, kerana kini, kerana kita prepended,

852
01:07:13,870 --> 01:07:17,240
ia akan berada di awal senarai.

853
01:07:17,240 --> 01:07:22,540
Jika kita Prepend (3), yang mencipta nod lain, tetapi sekarang 3 datang sebelum 7.

854
01:07:22,540 --> 01:07:31,130
Jadi, kita pada dasarnya menolak perkara-perkara ke senarai kami.

855
01:07:31,130 --> 01:07:34,720
Kini, anda boleh melihat bahawa Prepend, kadang-kadang orang panggil ia menolak,

856
01:07:34,720 --> 01:07:39,600
kerana anda menolak elemen baru ke senarai anda.

857
01:07:39,600 --> 01:07:43,270
Ia juga mudah untuk memadam di hadapan senarai.

858
01:07:43,270 --> 01:07:45,650
Jadi orang sering akan memanggil pop yang.

859
01:07:45,650 --> 01:07:52,200
Dan dengan cara itu, anda boleh mencontohi susunan menggunakan senarai yang dipautkan.

860
01:07:52,200 --> 01:07:57,880
Oop. Maaf, sekarang kita sedang masuk ke dalam lampiran. Jadi di sini kita prepended (7), sekarang kita Prepend (3).

861
01:07:57,880 --> 01:08:02,600
Jika kita prepended sesuatu yang lain ke senarai ini, jika kita prepended (4),

862
01:08:02,600 --> 01:08:06,540
maka kita akan mempunyai 4 dan kemudian 3 dan kemudian 7.

863
01:08:06,540 --> 01:08:14,220
Jadi maka kita boleh pop dan keluarkan 4, remove 3, keluarkan 7.

864
01:08:14,220 --> 01:08:16,500
Selalunya cara yang lebih intuitif untuk berfikir tentang perkara ini adalah dengan lampiran.

865
01:08:16,500 --> 01:08:20,310
Jadi saya telah diagrammed apa yang ia akan kelihatan seperti dengan melampirkan di sini.

866
01:08:20,310 --> 01:08:23,380
Di sini, dilampirkan (7) tidak melihat apa-apa yang berbeza

867
01:08:23,380 --> 01:08:25,160
kerana ada hanya satu elemen dalam senarai.

868
01:08:25,160 --> 01:08:28,620
Dan appending (3) meletakkan ia pada akhir.

869
01:08:28,620 --> 01:08:31,020
Mungkin anda boleh lihat sekarang helah dengan lampiran

870
01:08:31,020 --> 01:08:36,600
ialah kerana kita hanya tahu di mana permulaan senarai,

871
01:08:36,600 --> 01:08:39,450
untuk menambah kepada senarai anda perlu berjalan sepanjang jalan melalui senarai

872
01:08:39,450 --> 01:08:46,500
untuk sampai ke akhir, berhenti, kemudian membina nod anda dan segala-galanya mengempaskan turun.

873
01:08:46,500 --> 01:08:50,590
Wayar semua barangan atas.

874
01:08:50,590 --> 01:08:55,170
Jadi dengan Prepend, kita hanya mengoyakkan melalui ini benar-benar cepat,

875
01:08:55,170 --> 01:08:58,170
apabila anda Prepend ke senarai, ia agak mudah.

876
01:08:58,170 --> 01:09:02,960
>> Anda membuat nod baru anda, melibatkan beberapa peruntukan memori dinamik.

877
01:09:02,960 --> 01:09:09,830
Jadi di sini kita membuat struct nod menggunakan malloc.

878
01:09:09,830 --> 01:09:14,710
Jadi malloc kita menggunakan kerana yang akan mengetepikan ingatan bagi kita untuk masa lain

879
01:09:14,710 --> 01:09:20,350
kerana kita tidak mahu perkara ini - kami mahu memori ini berterusan untuk jangka masa yang panjang.

880
01:09:20,350 --> 01:09:25,350
Dan kita mendapat penunjuk kepada ruang dalam ingatan bahawa kita hanya diperuntukkan.

881
01:09:25,350 --> 01:09:29,260
Kami menggunakan saiz nod, kita tidak meringkaskannya bidang.

882
01:09:29,260 --> 01:09:31,899
Kami tidak manual menjana bilangan bait,

883
01:09:31,899 --> 01:09:39,750
sebaliknya kita gunakan sizeof supaya kita tahu kita sedang mendapatkan nombor yang sesuai bait.

884
01:09:39,750 --> 01:09:43,660
Kami pastikan untuk menguji bahawa panggilan malloc kami berjaya.

885
01:09:43,660 --> 01:09:47,939
Ini adalah sesuatu yang anda mahu lakukan secara umum.

886
01:09:47,939 --> 01:09:52,590
Pada mesin moden, kehabisan memori bukanlah sesuatu yang mudah

887
01:09:52,590 --> 01:09:56,610
melainkan jika anda memperuntukkan satu tan barangan dan membuat senarai besar,

888
01:09:56,610 --> 01:10:02,220
tetapi jika anda sedang membina barangan untuk, katakan, seperti iPhone atau Android,

889
01:10:02,220 --> 01:10:05,230
anda tidak mempunyai sumber memori yang terhad, terutamanya jika anda sedang melakukan sesuatu yang kuat.

890
01:10:05,230 --> 01:10:08,300
Jadi ia adalah baik untuk masuk ke dalam amalan.

891
01:10:08,300 --> 01:10:10,510
>> Perhatikan bahawa saya telah menggunakan fungsi yang berbeza beberapa di sini

892
01:10:10,510 --> 01:10:12,880
bahawa anda telah melihat bahawa adalah jenis baru.

893
01:10:12,880 --> 01:10:15,870
Jadi fprintf seperti printf

894
01:10:15,870 --> 01:10:21,320
kecuali hujah pertama adalah aliran yang anda mahu untuk mencetak.

895
01:10:21,320 --> 01:10:23,900
Dalam kes ini, kita ingin mencetak rentetan kesilapan standard

896
01:10:23,900 --> 01:10:29,410
yang berbeza dari outstream standard.

897
01:10:29,410 --> 01:10:31,620
Secara lalai ia muncul di tempat yang sama.

898
01:10:31,620 --> 01:10:34,600
Ia juga mencetak keluar ke terminal, tetapi anda boleh -

899
01:10:34,600 --> 01:10:38,790
menggunakan mereka arahan anda belajar tentang, redirection teknik

900
01:10:38,790 --> 01:10:42,290
anda belajar kira-kira dalam video Tommy untuk menetapkan masalah 4, anda boleh mengarahkan

901
01:10:42,290 --> 01:10:47,900
kepada kawasan-kawasan yang berlainan; kemudian keluar, di sini, keluar program anda.

902
01:10:47,900 --> 01:10:50,440
Ia adalah asasnya seperti pulang dari utama,

903
01:10:50,440 --> 01:10:53,600
kecuali kita menggunakan keluar kerana di sini pulangan tidak akan berbuat apa-apa.

904
01:10:53,600 --> 01:10:57,140
Kita tidak berada di utama, jadi kembali tidak keluar dari program seperti kita mahu.

905
01:10:57,140 --> 01:11:03,020
Jadi kita gunakan fungsi keluar dan memberikan kod ralat.

906
01:11:03,020 --> 01:11:11,890
Kemudian di sini kita menetapkan bidang nilai nod baru, bidang i untuk menjadi sama dengan i, dan kemudian kita wayar sehingga ia.

907
01:11:11,890 --> 01:11:15,530
Kami menetapkan penunjuk nod seterusnya baru ke titik pertama,

908
01:11:15,530 --> 01:11:20,460
dan kemudian pertama kini akan menunjukkan kepada nod baru.

909
01:11:20,460 --> 01:11:25,120
Ini baris pertama kod, kita sebenarnya membina nod 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 sebenarnya boleh tarik keluar ke fungsi, ke dalam fungsi pembantu.

912
01:11:30,290 --> 01:11:32,560
Itu sering apa yang saya lakukan adalah, saya tarik ia keluar ke fungsi,

913
01:11:32,560 --> 01:11:36,040
Saya memanggilnya sesuatu seperti membina nod,

914
01:11:36,040 --> 01:11:40,410
dan yang menyimpan fungsi Prepend agak kecil, ia adalah hanya 3 baris kemudian.

915
01:11:40,410 --> 01:11:48,710
Saya membuat panggilan kepada fungsi nod membina saya, dan kemudian saya dawai segala-galanya sehingga.

916
01:11:48,710 --> 01:11:51,970
>> Perkara terakhir yang saya ingin menunjukkan kepada anda,

917
01:11:51,970 --> 01:11:54,030
dan saya akan membiarkan anda melakukan lampiran dan semua yang anda sendiri,

918
01:11:54,030 --> 01:11:57,500
adalah bagaimana untuk melelar senarai.

919
01:11:57,500 --> 01:12:00,780
Terdapat sekumpulan cara yang berbeza untuk melelar atas senarai.

920
01:12:00,780 --> 01:12:03,140
Dalam kes ini, kita akan mendapati panjang senarai.

921
01:12:03,140 --> 01:12:06,570
Jadi kita mulakan dengan = 0 panjang.

922
01:12:06,570 --> 01:12:11,580
Ini adalah amat serupa untuk menulis strlen untuk rentetan.

923
01:12:11,580 --> 01:12:17,780
Ini adalah apa yang saya mahu menunjukkan kepada anda, ini untuk gelung di sini.

924
01:12:17,780 --> 01:12:23,530
Ia kelihatan agak funky; ia tidak biasa int i = 0, i <apa sahaja, i + +.

925
01:12:23,530 --> 01:12:34,920
Sebaliknya, ia yang Memulakan n pembolehubah kita untuk menjadi permulaan senarai.

926
01:12:34,920 --> 01:12:40,620
Dan kemudian manakala pembolehubah iterator kita tidak adalah batal, kita terus pergi.

927
01:12:40,620 --> 01:12:46,340
Ini adalah kerana, mengikut konvensyen, akhir senarai kami akan menjadi batal.

928
01:12:46,340 --> 01:12:48,770
Dan kemudian ke kenaikan, bukannya melakukan + +,

929
01:12:48,770 --> 01:12:57,010
bersamaan senarai bersambung + + n = n-> seterusnya.

930
01:12:57,010 --> 01:13:00,410
>> Saya akan membiarkan anda mengisi jurang di sini kerana kita berada di luar masa.

931
01:13:00,410 --> 01:13:09,300
Tetapi menyimpan ini dalam minda sebagai anda bekerja pada psets spellr anda.

932
01:13:09,300 --> 01:13:11,650
Berkaitan senarai, jika anda sedang melaksanakan jadual hash,

933
01:13:11,650 --> 01:13:14,010
pasti akan datang dalam sangat berguna.

934
01:13:14,010 --> 01:13:21,780
Dan mempunyai ungkapan ini untuk menggelung atas perkara akan menjadikan kehidupan lebih mudah, mudah-mudahan.

935
01:13:21,780 --> 01:13:25,910
Sebarang soalan, cepat?

936
01:13:25,910 --> 01:13:28,920
[Sam] Adakah anda menghantar SLL siap dan sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Saya akan menghantar keluar slaid siap dan SLL siap timbunan dan queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]