1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:05,120
[เล่นเพลง]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
ลำโพง 1: สิทธิทั้งหมด

5
00:00:12,900 --> 00:00:14,600
ทุกคนยินดีต้อนรับกลับไปยังส่วน

6
00:00:14,600 --> 00:00:18,660
ฉันหวังว่าคุณทุกคนจะประสบความสำเร็จ
หายจากการทดสอบของคุณ

7
00:00:18,660 --> 00:00:19,510
จากสัปดาห์ก่อน

8
00:00:19,510 --> 00:00:22,564
ฉันรู้ว่ามันนิด ๆ หน่อย ๆ บ้าในบางครั้ง

9
00:00:22,564 --> 00:00:25,230
ขณะที่ผมกำลังบอกก่อนถ้าคุณอยู่
ภายในส่วนเบี่ยงเบนมาตรฐาน

10
00:00:25,230 --> 00:00:28,188
ไม่ต้องกังวลเกี่ยวกับเรื่องนี้โดยเฉพาะอย่างยิ่ง
สำหรับส่วนที่สะดวกสบายน้อยกว่า

11
00:00:28,188 --> 00:00:30,230
ที่เกี่ยวกับการที่คุณควรจะ

12
00:00:30,230 --> 00:00:32,850
>> ถ้าคุณไม่ดี, น่ากลัวแล้ว

13
00:00:32,850 --> 00:00:33,650
รุ่งโรจน์เพื่อคุณ

14
00:00:33,650 --> 00:00:36,149
และถ้าคุณรู้สึกว่าคุณต้อง
นิด ๆ หน่อย ๆ ความช่วยเหลือเพิ่มเติมกรุณา

15
00:00:36,149 --> 00:00:38,140
อย่าลังเลที่จะไปให้ถึง
ออกไปใด ๆ ของ TFS

16
00:00:38,140 --> 00:00:40,030
เราทุกคนที่นี่เพื่อช่วย

17
00:00:40,030 --> 00:00:40,960
>> นั่นเป็นเหตุผลที่เราสอน

18
00:00:40,960 --> 00:00:44,550
นั่นเป็นเหตุผลที่ผมมาที่นี่ทุกวันจันทร์สำหรับคุณ
คนและในเวลาทำการในวันพฤหัสบดี

19
00:00:44,550 --> 00:00:48,130
ดังนั้นโปรดอย่าลังเลที่จะแจ้งให้เราทราบ
ถ้าคุณกังวลเกี่ยวกับอะไร

20
00:00:48,130 --> 00:00:52,450
หรือถ้ามีอะไรที่เกี่ยวกับการทดสอบ
ที่คุณต้องการจริงๆชอบที่จะอยู่

21
00:00:52,450 --> 00:00:56,940
>> ดังนั้นวาระการประชุมสำหรับวันนี้เป็น
ทั้งหมดเกี่ยวกับโครงสร้างข้อมูล

22
00:00:56,940 --> 00:01:01,520
บางส่วนของเหล่านี้เป็นเพียงการไปได้เพียงแค่
เพื่อให้ได้คุ้นเคยกับสิ่งเหล่านี้

23
00:01:01,520 --> 00:01:04,870
ที่คุณอาจไม่เคยใช้
พวกเขาในชั้นนี้

24
00:01:04,870 --> 00:01:08,690
บางส่วนของพวกเขาที่คุณจะ
เหมือน pset สะกดของคุณ

25
00:01:08,690 --> 00:01:11,380
>> คุณจะมีตัวเลือกของคุณ
ระหว่างตารางแฮชและพยายาม

26
00:01:11,380 --> 00:01:13,680
ดังนั้นเราจะมั่นเหมาะจะไปกว่านั้น

27
00:01:13,680 --> 00:01:18,690
มันเป็นไปได้แน่นอนมากขึ้นของชนิด
ส่วนในระดับที่สูงในวันนี้แม้ว่า

28
00:01:18,690 --> 00:01:22,630
เพราะมีจำนวนมากของพวกเขาและถ้า
เราเดินเข้าไปในรายละเอียดการดำเนินการ

29
00:01:22,630 --> 00:01:26,490
ในทุกเหล่านี้เราจะไม่
แม้จะได้รับผ่านรายการเชื่อมโยง

30
00:01:26,490 --> 00:01:28,520
และอาจจะนิด ๆ หน่อย ๆ ของตารางแฮช

31
00:01:28,520 --> 00:01:31,200
>> ดังนั้นอดทนกับฉัน

32
00:01:31,200 --> 00:01:33,530
เราไม่ได้จะต้องทำ
เท่าเข้ารหัสเวลานี้

33
00:01:33,530 --> 00:01:36,870
หากคุณมีคำถามใด ๆ เกี่ยวกับเรื่องนี้
หรือคุณต้องการที่จะเห็นมันดำเนินการ

34
00:01:36,870 --> 00:01:39,260
หรือลองด้วยตัวคุณเอง
แน่นอนผมขอแนะนำให้

35
00:01:39,260 --> 00:01:44,250
จะ study.cs50.net ซึ่ง
มีตัวอย่างของสิ่งเหล่านี้

36
00:01:44,250 --> 00:01:46,400
มันจะมี PowerPoints ของฉัน
กับบันทึกที่เรา

37
00:01:46,400 --> 00:01:50,860
มีแนวโน้มที่จะใช้เช่นเดียวกับการเขียนโปรแกรมบางอย่าง
การออกกำลังกายโดยเฉพาะอย่างยิ่งสำหรับสิ่งที่

38
00:01:50,860 --> 00:01:55,250
เช่นรายการเชื่อมโยงและไบนารี
กองต้นไม้และความหมาย

39
00:01:55,250 --> 00:01:59,590
เล็ก ๆ น้อย ๆ ดังนั้นในระดับสูงมากขึ้นซึ่ง
อาจจะดีสำหรับพวกคุณ

40
00:01:59,590 --> 00:02:01,320
>> ดังนั้นด้วยความที่เราจะเริ่มต้น

41
00:02:01,320 --> 00:02:03,060
และยัง yes-- แบบทดสอบ

42
00:02:03,060 --> 00:02:06,550
ผมคิดว่าส่วนใหญ่ของคุณที่อยู่ใน
ส่วนของผมมีแบบทดสอบของคุณ

43
00:02:06,550 --> 00:02:12,060
แต่ทุกคนมาในหรือเหตุผลบางอย่างที่คุณ
ไม่ได้พวกเขาที่นี่ในด้านหน้า

44
00:02:12,060 --> 00:02:12,740
>> รายการเชื่อมโยงดังนั้น

45
00:02:12,740 --> 00:02:15,650
ฉันรู้ว่าแบบนี้ไป
การสำรองข้อมูลก่อนที่จะตอบคำถามของคุณ

46
00:02:15,650 --> 00:02:17,940
นั่นคือเมื่อสัปดาห์ก่อน
ที่เราได้เรียนรู้เกี่ยวกับเรื่องนี้

47
00:02:17,940 --> 00:02:21,040
แต่ในกรณีนี้เราจะเพียงแค่
ไปนิด ๆ หน่อย ๆ เพิ่มเติมในเชิงลึก

48
00:02:21,040 --> 00:02:25,900
>> ดังนั้นทำไมเราจะเลือก
รายการที่เชื่อมโยงมากกว่าอาร์เรย์?

49
00:02:25,900 --> 00:02:27,130
แตกต่างพวกเขาคืออะไร?

50
00:02:27,130 --> 00:02:27,630
ใช่?

51
00:02:27,630 --> 00:02:30,464
>> ผู้ชม: คุณสามารถขยายการเชื่อมโยง
รายการเมื่อเทียบกับขนาดคงอาร์เรย์

52
00:02:30,464 --> 00:02:31,171
ลำโพง 1: ขวา

53
00:02:31,171 --> 00:02:33,970
อาเรย์ได้กำหนดขนาดในขณะที่
รายการที่เชื่อมโยงมีขนาดตัวแปร

54
00:02:33,970 --> 00:02:36,970
ดังนั้นหากเราไม่ทราบว่า
มากที่เราต้องการในการจัดเก็บ

55
00:02:36,970 --> 00:02:39,880
รายการที่เชื่อมโยงจะช่วยให้เราดี
วิธีการที่จะทำอย่างนั้นเพราะเราสามารถทำได้เพียงแค่

56
00:02:39,880 --> 00:02:43,730
เพิ่มในโหนดอื่นและเพิ่ม
โหนดอื่นและเพิ่มในโหนดอื่น

57
00:02:43,730 --> 00:02:45,750
แต่สิ่งที่อาจจะมีการออก?

58
00:02:45,750 --> 00:02:49,521
ไม่มีใครจำได้ว่าการออก
ระหว่างอาร์เรย์และรายการเชื่อมโยง?

59
00:02:49,521 --> 00:02:50,020
mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> ผู้ชม: คุณต้อง
ผ่านไปตลอดทาง

61
00:02:51,460 --> 00:02:53,738
ผ่านรายการที่เชื่อมโยง
หาองค์ประกอบในรายการ

62
00:02:53,738 --> 00:02:55,570
ในอาร์เรย์คุณสามารถ
เพียงแค่หาองค์ประกอบ

63
00:02:55,570 --> 00:02:56,278
>> ลำโพง 1: ขวา

64
00:02:56,278 --> 00:02:57,120
ดังนั้นด้วย arrays--

65
00:02:57,120 --> 00:02:58,500
>> ผู้ชม: [ไม่ได้ยิน]

66
00:02:58,500 --> 00:03:01,090
>> ลำโพง 1: ด้วยอาร์เรย์เรามี
สิ่งที่เรียกว่าการเข้าถึงแบบสุ่ม

67
00:03:01,090 --> 00:03:04,820
หมายความว่าถ้าเราต้องการสิ่งที่เป็น
ที่เคยเป็นจุดที่ห้าของรายการ

68
00:03:04,820 --> 00:03:07,230
หรือจุดที่ห้าของเรา
อาเรย์เราก็สามารถคว้ามัน

69
00:03:07,230 --> 00:03:10,440
หากเป็นรายการที่เชื่อมโยงเรามี
เพื่อย้ำผ่านใช่มั้ย?

70
00:03:10,440 --> 00:03:14,020
ดังนั้นการเข้าถึงองค์ประกอบใน
อาร์เรย์เป็นเวลาที่คงที่

71
00:03:14,020 --> 00:03:19,530
ในขณะที่มีการเชื่อมโยงรายการมันจะ
ส่วนใหญ่จะเป็นเส้นเวลาเพราะอาจจะ

72
00:03:19,530 --> 00:03:21,370
องค์ประกอบของเรามีทุกอย่างในตอนท้าย

73
00:03:21,370 --> 00:03:23,446
เรามีการค้นหาผ่านทุกอย่าง

74
00:03:23,446 --> 00:03:25,320
ดังนั้นด้วยข้อมูลทั้งหมดเหล่านี้
โครงสร้างที่เรากำลังจะ

75
00:03:25,320 --> 00:03:29,330
ที่จะใช้เวลามากขึ้นเล็ก ๆ น้อย ๆ ,
สิ่งที่เป็นบวกและเชิงลบ

76
00:03:29,330 --> 00:03:31,480
เมื่อเราอาจต้องการที่จะ
ใช้หนึ่งในช่วงอื่น ๆ ?

77
00:03:31,480 --> 00:03:34,970
และนั่นคือชนิดของ
สิ่งที่ใหญ่กว่าที่จะไป

78
00:03:34,970 --> 00:03:40,140
>> เพื่อให้เรามีที่นี่
ความหมายของโหนด

79
00:03:40,140 --> 00:03:43,040
มันก็เหมือนกับองค์ประกอบหนึ่งใน
รายการที่เชื่อมโยงของเราใช่มั้ย?

80
00:03:43,040 --> 00:03:46,180
ดังนั้นเราทุกคนคุ้นเคย
กับ structs typedef ของเรา

81
00:03:46,180 --> 00:03:47,980
ที่เราเดินไปในการตรวจสอบครั้งสุดท้าย

82
00:03:47,980 --> 00:03:53,180
มันเป็นเพียงแค่การสร้างพื้น
ชนิดข้อมูลอื่นที่เราสามารถใช้

83
00:03:53,180 --> 00:03:57,930
>> และในกรณีนี้มันเป็นบางโหนด
ที่จะถือจำนวนเต็มบางอย่างใน

84
00:03:57,930 --> 00:04:00,210
และแล้วสิ่งที่เป็นส่วนที่สองที่นี่?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
ใคร?

87
00:04:05,677 --> 00:04:06,680
>> ผู้ชม: [ไม่ได้ยิน]

88
00:04:06,680 --> 00:04:07,020
>> ลำโพง 1: ใช่

89
00:04:07,020 --> 00:04:08,400
มันเป็นตัวชี้ไปยังโหนดถั​​ดไป

90
00:04:08,400 --> 00:04:12,610
ดังนั้นนี้จริงควรจะขึ้นที่นี่

91
00:04:12,610 --> 00:04:18,790
นี้เป็นตัวชี้ประเภท
โหนดสิ่งต่อไปที่

92
00:04:18,790 --> 00:04:22,410
และนั่นคือสิ่งที่พวกเขา
ครอบคลุมโหนดของเรา

93
00:04:22,410 --> 00:04:24,060
เย็น

94
00:04:24,060 --> 00:04:29,390
>> สิทธิทั้งหมดเพื่อให้มีการค้นหาในขณะที่เรามี
เพียงแค่บอกว่าก่อนที่มือถ้าคุณ

95
00:04:29,390 --> 00:04:31,840
จะค้นหาผ่าน,
คุณต้องย้ำจริง

96
00:04:31,840 --> 00:04:33,660
ผ่านรายการที่เชื่อมโยงของคุณ

97
00:04:33,660 --> 00:04:38,530
ดังนั้นหากเรากำลังมองหาตัวเลข
9 เราจะเริ่มต้นที่หัวของเรา

98
00:04:38,530 --> 00:04:41,520
และที่ชี้ให้เราที่จุดเริ่มต้น
ของรายการที่เชื่อมโยงของเราใช่มั้ย?

99
00:04:41,520 --> 00:04:44,600
และเราบอกว่าโอเคไม่นี้
โหนดมีจำนวน 9?

100
00:04:44,600 --> 00:04:45,690
ไม่มี?

101
00:04:45,690 --> 00:04:47,500
>> สิทธิทั้งหมดไปที่หนึ่งต่อไป

102
00:04:47,500 --> 00:04:48,312
ทำตามมัน

103
00:04:48,312 --> 00:04:49,520
มันมีจำนวน 9?

104
00:04:49,520 --> 00:04:50,570
เลขที่

105
00:04:50,570 --> 00:04:51,550
ทำตามอย่างใดอย่างหนึ่งต่อไป

106
00:04:51,550 --> 00:04:55,490
>> ดังนั้นเราต้องย้ำจริง
ผ่านรายการที่เชื่อมโยงของเรา

107
00:04:55,490 --> 00:05:00,070
เราก็ไม่สามารถไปที่ 9 เป็น

108
00:05:00,070 --> 00:05:05,860
และถ้าพวกคุณจริงต้องการ
เห็นบางนามแฝงรหัสขึ้นมี

109
00:05:05,860 --> 00:05:10,420
เรามีฟังก์ชันการค้นหาบางส่วนที่นี่
ที่ใช้เวลา in-- สิ่งที่ไม่ได้ใช้มีอะไรบ้าง?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
คุณคิดอย่างไร?

112
00:05:14,320 --> 00:05:15,960
เพื่อให้ง่ายต่อหนึ่ง

113
00:05:15,960 --> 00:05:17,784
นี่คืออะไร?

114
00:05:17,784 --> 00:05:18,700
ผู้ชม: [ไม่ได้ยิน]

115
00:05:18,700 --> 00:05:20,366
ลำโพง 1: จำนวนที่เรากำลังมองหา

116
00:05:20,366 --> 00:05:20,980
ใช่มั้ย?

117
00:05:20,980 --> 00:05:22,875
และสิ่งนี้จะสอดคล้องกับ?

118
00:05:22,875 --> 00:05:25,020
มันเป็นตัวชี้ไปยัง?

119
00:05:25,020 --> 00:05:26,000
>> ผู้ชม: โหนด

120
00:05:26,000 --> 00:05:28,980
>> ลำโพง 1: โหนดในรายการ
ที่เรากำลังมองหาที่ใช่มั้ย?

121
00:05:28,980 --> 00:05:33,700
ดังนั้นเราจึงมีบางโหนดเป็นตัวชี้ที่นี่

122
00:05:33,700 --> 00:05:37,240
ตรงนี้คือจุดที่จะ
จริงย้ำผ่านรายการของเรา

123
00:05:37,240 --> 00:05:39,630
เราตั้งค่ามันเท่ากันในรายการ
เนื่องจากว่าเป็นเพียง

124
00:05:39,630 --> 00:05:44,380
การตั้งค่าเท่ากับ
จุดเริ่มต้นของรายการที่เชื่อมโยงของเรา

125
00:05:44,380 --> 00:05:50,660
>> และในขณะที่มันไม่ได้เป็นโมฆะขณะที่
เรายังคงมีสิ่งที่อยู่ในรายชื่อของเรา

126
00:05:50,660 --> 00:05:55,580
ตรวจสอบเพื่อดูว่าโหนดที่มี
จำนวนที่เรากำลังมองหา

127
00:05:55,580 --> 00:05:57,740
กลับจริง

128
00:05:57,740 --> 00:06:01,070
มิฉะนั้น update มันใช่มั้ย?

129
00:06:01,070 --> 00:06:04,870
>> ถ้ามันเป็นโมฆะเราออกจากเรา
ในขณะที่วงและกลับเท็จ

130
00:06:04,870 --> 00:06:08,340
เพราะนั่นหมายความว่าเราไม่ได้พบว่ามัน

131
00:06:08,340 --> 00:06:11,048
ทุกคนได้รับว่าทำงานอย่างไร

132
00:06:11,048 --> 00:06:11,548
ตกลง

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> ดังนั้นด้วยการแทรกคุณ
มีสามวิธีที่แตกต่างกัน

135
00:06:20,260 --> 00:06:25,250
คุณสามารถ prepend คุณสามารถผนวก
และคุณสามารถใส่ลงในสารพัน

136
00:06:25,250 --> 00:06:28,215
ในกรณีนี้เราไม่
จะทำย่อหน้า

137
00:06:28,215 --> 00:06:33,380
ไม่มีใครรู้ว่าผู้ที่
สามกรณีอาจแตกต่างกัน?

138
00:06:33,380 --> 00:06:36,920
>> ดังนั้นย่อหน้าหมายความว่าคุณใส่
มันที่ด้านหน้าของรายการของคุณ

139
00:06:36,920 --> 00:06:39,770
เพื่อที่จะหมายถึงว่าไม่ว่า
สิ่งที่โหนดของคุณไม่ว่า

140
00:06:39,770 --> 00:06:43,160
สิ่งที่มีค่าเป็นคุณจะ
ที่จะนำมันที่นี่ในหน้า, OK?

141
00:06:43,160 --> 00:06:45,160
มันจะเป็นครั้งแรก
องค์ประกอบในรายการของคุณ

142
00:06:45,160 --> 00:06:49,510
>> ถ้าคุณผนวกก็จะ
เพื่อไปยังด้านหลังของรายการของคุณ

143
00:06:49,510 --> 00:06:54,010
และใส่ลงในสารพันหมายความว่าคุณ
จะใส่เข้าไปในสถานที่จริง

144
00:06:54,010 --> 00:06:57,700
ที่จะช่วยให้รายการที่เชื่อมโยงที่เรียงลำดับ

145
00:06:57,700 --> 00:07:00,810
อีกวิธีที่คุณใช้
เหล่านั้นและเมื่อคุณใช้

146
00:07:00,810 --> 00:07:02,530
พวกเขาจะแตกต่างกันขึ้นอยู่กับกรณีของคุณ

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
ถ้ามันไม่จำเป็นต้อง
ถูกจัดเรียงย่อหน้ามีแนวโน้มที่

149
00:07:07,750 --> 00:07:10,460
จะเป็นสิ่งที่คนส่วนใหญ่
ใช้เพราะคุณทำไม่ได้

150
00:07:10,460 --> 00:07:15,680
ต้องผ่านรายการทั้งหมด
ที่จะหาจุดสิ้นสุดที่จะเพิ่มในใช่มั้ย?

151
00:07:15,680 --> 00:07:17,720
คุณก็สามารถติดอยู่ใน

152
00:07:17,720 --> 00:07:21,930
>> ดังนั้นเราจะไปถึง
แทรก 1 ได้ในขณะนี้

153
00:07:21,930 --> 00:07:26,360
ดังนั้นสิ่งหนึ่งที่ฉันจะ
ขอแนะนำให้ใน pset นี้

154
00:07:26,360 --> 00:07:29,820
คือการวาดสิ่งที่ออกเช่นเคย

155
00:07:29,820 --> 00:07:35,130
มันเป็นสิ่งสำคัญมากที่คุณอัปเดต
ตัวชี้ของคุณในลำดับที่ถูกต้อง

156
00:07:35,130 --> 00:07:38,620
เพราะถ้าคุณปรับปรุงพวกเขา
เล็กน้อยออกคำสั่ง

157
00:07:38,620 --> 00:07:42,210
คุณกำลังจะจบลง
ส่วนการสูญเสียของรายการของคุณ

158
00:07:42,210 --> 00:07:49,680
>> ดังนั้นสำหรับตัวอย่างเช่นในกรณีนี้เราไม่
บอกหัวเพียงแค่จุดที่ 1

159
00:07:49,680 --> 00:07:56,070
ถ้าเราเพียงแค่ทำอย่างนั้น
โดยไม่บันทึก 1 นี้

160
00:07:56,070 --> 00:07:58,570
เรามีความคิดว่า
1 ควรชี้ไปตอนนี้

161
00:07:58,570 --> 00:08:02,490
เพราะเราได้สูญเสียสิ่งที่
หัวชี้ไปที่

162
00:08:02,490 --> 00:08:05,530
ดังนั้นสิ่งหนึ่งที่ต้องจำไว้
เมื่อคุณกำลังทำย่อหน้า

163
00:08:05,530 --> 00:08:09,630
คือการบันทึกสิ่งที่
มุ่งหน้าไปยังจุดแรก

164
00:08:09,630 --> 00:08:15,210
แล้วกำหนดมันแล้วปรับปรุง
สิ่งที่โหนดใหม่ของคุณควรชี้ไป

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
ในกรณีนี้เป็นวิธีหนึ่งที่จะทำมัน

167
00:08:22,560 --> 00:08:25,440
>> ดังนั้นหากเราได้ทำมันด้วยวิธีนี้
ซึ่งเราก็มีพระราชเสาวนีย์หัว

168
00:08:25,440 --> 00:08:30,320
เราสูญเสียโดยทั่วไปของเรา
รายการทั้งหมดใช่มั้ย?

169
00:08:30,320 --> 00:08:38,000
วิธีหนึ่งที่จะทำก็คือการมี 1 ชี้ไปที่
ถัดไปและจากนั้นมีจุดหัว 1

170
00:08:38,000 --> 00:08:42,650
หรือคุณสามารถทำชนิดเช่น
จัดเก็บชั่วคราวที่ฉันพูดคุยเกี่ยวกับ

171
00:08:42,650 --> 00:08:45,670
>> แต่มอบหมายงานใหม่ของคุณ
ตัวชี้ในลำดับที่ถูกต้อง

172
00:08:45,670 --> 00:08:48,750
เป็นไปได้มาก
สิ่งสำคัญสำหรับ pset นี้

173
00:08:48,750 --> 00:08:53,140
มิฉะนั้นคุณจะต้องกัญชา
ตารางหรือพยายามที่เพียงแค่จะเป็น

174
00:08:53,140 --> 00:08:56,014
เพียงส่วนหนึ่งของคำที่คุณ
ต้องการแล้ว mmhmm you're--?

175
00:08:56,014 --> 00:08:58,930
ผู้ชม: อะไรคือสิ่งที่ชั่วคราว
สิ่งที่จัดเก็บข้อมูลที่คุณกำลังพูดถึง?

176
00:08:58,930 --> 00:09:00,305
ลำโพงที่ 1: การจัดเก็บชั่วคราว

177
00:09:00,305 --> 00:09:02,760
ดังนั้นโดยทั่วไปอีก
วิธีการที่คุณสามารถทำเช่นนี้

178
00:09:02,760 --> 00:09:07,650
มีการเก็บหัวของบางอย่างเช่น
เก็บไว้ตัวแปรชั่วคราว

179
00:09:07,650 --> 00:09:11,250
กำหนดให้ 1 และ
แล้ว update 1 ที่จะชี้

180
00:09:11,250 --> 00:09:13,830
สิ่งที่หัวที่ใช้ในการชี้ไปที่

181
00:09:13,830 --> 00:09:16,920
วิธีนี้จะเห็นได้ชัด
สง่างามมากขึ้นเพราะคุณ

182
00:09:16,920 --> 00:09:20,770
ไม่จำเป็นต้องมีค่าชั่วคราว แต่
เพียงแค่นำเสนอวิธีที่จะทำมันอีก

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
และเราทำจริงได้
รหัสบางอย่างสำหรับการนี​​้

185
00:09:25,790 --> 00:09:28,080
ดังนั้นสำหรับรายการที่เชื่อมโยงเรา
จริงมีโค้ดบางส่วน

186
00:09:28,080 --> 00:09:31,930
ดังนั้นที่นี่ใส่นี้ prepending

187
00:09:31,930 --> 00:09:34,290
ดังนั้นนี่มันเข้าที่หัว

188
00:09:34,290 --> 00:09:38,820
>> ดังนั้นสิ่งแรกที่คุณจะต้อง
สร้างโหนดใหม่ของคุณแน่นอน

189
00:09:38,820 --> 00:09:40,790
และตรวจสอบเป็นโมฆะ

190
00:09:40,790 --> 00:09:43,250
ดีอยู่เสมอ

191
00:09:43,250 --> 00:09:47,840
และจากนั้นคุณต้องกำหนดค่า

192
00:09:47,840 --> 00:09:51,260
เมื่อใดก็ตามที่คุณสร้างโหนดใหม่คุณ
ไม่ทราบว่าสิ่งที่มันชี้ไปข้างหน้า

193
00:09:51,260 --> 00:09:54,560
ดังนั้นคุณจึงต้องการที่จะเริ่มต้นให้ NULL

194
00:09:54,560 --> 00:09:58,760
ถ้ามันไม่จบลงด้วยการชี้ไปที่บางสิ่งบางอย่าง
อื่น ๆ จะได้รับพระราชเสาวนีย์และก็ปรับ

195
00:09:58,760 --> 00:10:00,740
ถ้ามันเป็นสิ่งแรก
ในรายการก็ต้อง

196
00:10:00,740 --> 00:10:04,270
ให้ชี้ไปที่ NULL เพราะ
ที่ตอนท้ายของรายการ

197
00:10:04,270 --> 00:10:12,410
>> ดังนั้นแล้วการใส่เราเห็นที่นี่เรา
มีการกำหนดค่าถัดไปของโหนดของเรา

198
00:10:12,410 --> 00:10:17,380
จะเป็นสิ่งที่หัวคือ
ซึ่งเป็นสิ่งที่เรามีที่นี่

199
00:10:17,380 --> 00:10:19,930
นั่นคือสิ่งที่เราได้ทำ

200
00:10:19,930 --> 00:10:25,820
และจากนั้นเราจะกำหนดหัวไปยังจุด
ไปยังโหนดใหม่ของเราเพราะจำ

201
00:10:25,820 --> 00:10:31,090
ใหม่เป็นตัวชี้บางโหนด
และนั่นคือสิ่งที่เป็นหัว

202
00:10:31,090 --> 00:10:34,370
ที่ว่าทำไมเรา
มีผู้เข้าใช้ลูกศรนี้

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
เย็น?

205
00:10:37,530 --> 00:10:38,130
mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> ผู้ชม: เราต้อง
เริ่มต้นต่อใหม่เพื่อ NULL แรก

207
00:10:41,100 --> 00:10:44,240
หรือเราสามารถเพียงแค่เริ่มต้นมันที่หัว?

208
00:10:44,240 --> 00:10:48,210
>> ลำโพง 1: ใหม่ต่อไป
ความต้องการที่จะเป็นโมฆะในการเริ่มต้น

209
00:10:48,210 --> 00:10:53,760
เพราะคุณไม่ทราบ
ที่มันจะเป็น

210
00:10:53,760 --> 00:10:56,100
นอกจากนี้เป็นชนิดของ
เช่นเดียวกระบวนทัศน์

211
00:10:56,100 --> 00:10:59,900
คุณตั้งค่าเท่ากับเป็นโมฆะเพียงเพื่อให้
แน่ใจหรือว่าฐานของคุณทั้งหมดจะถูกปกคลุม

212
00:10:59,900 --> 00:11:04,070
ก่อนที่จะทำการโอนใด ๆ เพื่อให้
คุณกำลังรับประกันเสมอว่ามันจะ

213
00:11:04,070 --> 00:11:08,880
จะชี้ไปยังค่าที่ระบุ
เมื่อเทียบกับค่าเช่นขยะ

214
00:11:08,880 --> 00:11:12,210
เพราะใช่เรากำหนด
ใหม่ต่อไปโดยอัตโนมัติ

215
00:11:12,210 --> 00:11:15,420
แต่มันก็มากขึ้นเช่นเดียวกับ
การปฏิบัติที่ดีในการเริ่มต้นมัน

216
00:11:15,420 --> 00:11:19,270
ในทางที่กำหนดแล้ว

217
00:11:19,270 --> 00:11:23,420
>> ตกลงเชื่อมโยงอย่างทวีคูณรายการตอนนี้

218
00:11:23,420 --> 00:11:24,601
เราคิดอย่างไร?

219
00:11:24,601 --> 00:11:26,350
สิ่งที่แตกต่างกันด้วย
รายการที่เชื่อมโยงทวีคูณ?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> ดังนั้นในรายการเชื่อมโยงของเราเราสามารถ
เพียงย้ายในทิศทางเดียวใช่มั้ย?

222
00:11:34,300 --> 00:11:35,270
เรามีเพียงต่อไป

223
00:11:35,270 --> 00:11:36,760
เราสามารถก้าวไปข้างหน้า

224
00:11:36,760 --> 00:11:40,300
>> กับรายการที่เชื่อมโยงทวีคูณ
เรายังสามารถย้ายไปข้างหลัง

225
00:11:40,300 --> 00:11:44,810
ดังนั้นเราจึงมีไม่เพียง
ตัวเลขที่เราต้องการในการจัดเก็บ

226
00:11:44,810 --> 00:11:50,110
เรามีที่ชี้ไปยัง
และที่เราเพิ่งมาจาก

227
00:11:50,110 --> 00:11:52,865
ดังนั้นนี้ช่วยให้การ
บางสำรวจเส้นทางที่ดีกว่า

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> ดังนั้นการเชื่อมโยงโหนดทวีคูณ
คล้ายกันมากใช่มั้ย?

230
00:12:01,240 --> 00:12:05,000
เพียง แต่ความแตกต่างก็คือตอนนี้เรา
มีต่อไปและก่อนหน้านี้

231
00:12:05,000 --> 00:12:06,235
มันเป็นเรื่องที่แตกต่าง

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> ดังนั้นถ้าเราจะ prepend หรือเรา append--
ไม่มีรหัสใด ๆ สำหรับการนี​​้ขึ้นตรงนี้

234
00:12:14,790 --> 00:12:17,830
แต่ถ้าคุณได้ลอง
ใส่สิ่งที่สำคัญ

235
00:12:17,830 --> 00:12:19,980
เป็นที่คุณต้องทำ
แน่ใจว่าคุณกำลังกำหนด

236
00:12:19,980 --> 00:12:23,360
ทั้งของคุณก่อนหน้านี้และของคุณ
ตัวชี้ต่อไปได้อย่างถูกต้อง

237
00:12:23,360 --> 00:12:29,010
ดังนั้นในกรณีนี้คุณจะ
ไม่เพียง แต่การเริ่มต้นต่อไป

238
00:12:29,010 --> 00:12:31,820
คุณเริ่มต้นที่ก่อนหน้านี้

239
00:12:31,820 --> 00:12:36,960
ถ้าเราอยู่ที่หัวของรายการเรา
จะไม่เพียง แต่ทำให้หัวเท่ากับใหม่

240
00:12:36,960 --> 00:12:41,750
แต่ควรที่ก่อนหน้าใหม่ของเรา
ชี้ไปที่หัวใช่มั้ย?

241
00:12:41,750 --> 00:12:43,380
>> นั่นคือความแตกต่างเท่านั้น

242
00:12:43,380 --> 00:12:47,200
และถ้าคุณต้องการการปฏิบัติมากยิ่งขึ้นด้วย
เหล่านี้ด้วยรายการที่เชื่อมโยงกับการแทรก

243
00:12:47,200 --> 00:12:49,900
ด้วยการลบด้วยการแทรก
เป็นรายการสารพัน

244
00:12:49,900 --> 00:12:52,670
โปรดตรวจสอบ study.cs50.net

245
00:12:52,670 --> 00:12:54,870
มีพวงของการออกกำลังกายที่ดีคือ

246
00:12:54,870 --> 00:12:55,870
ผมขอแนะนำให้พวกเขา

247
00:12:55,870 --> 00:12:59,210
ฉันหวังว่าเรามีเวลาที่จะไปถึงพวกเขา
แต่มีจำนวนมากของโครงสร้างข้อมูลเป็น

248
00:12:59,210 --> 00:13:01,530
จะได้รับผ่าน

249
00:13:01,530 --> 00:13:02,650
>> ตกลงดังนั้นตารางแฮช

250
00:13:02,650 --> 00:13:07,070
นี่อาจจะเป็นส่วนใหญ่
บิตมีประโยชน์สำหรับ pset ของคุณ

251
00:13:07,070 --> 00:13:11,090
นี่เพราะคุณกำลังจะเป็น
การดำเนินการอย่างใดอย่างหนึ่งเหล่านี้หรือลอง

252
00:13:11,090 --> 00:13:12,200
ฉันชอบตารางแฮช

253
00:13:12,200 --> 00:13:13,110
พวกเขากำลังเย็นสวย

254
00:13:13,110 --> 00:13:17,080
>> ดังนั้นโดยทั่วไปสิ่งที่
ที่เกิดขึ้นคือตารางแฮช

255
00:13:17,080 --> 00:13:22,050
คือเมื่อเราต้องการจริงๆได้อย่างรวดเร็ว
แทรกการลบและการค้นหา

256
00:13:22,050 --> 00:13:25,010
เหล่านี้คือสิ่งที่เรากำลัง
จัดลำดับความสำคัญในตารางแฮช

257
00:13:25,010 --> 00:13:29,500
พวกเขาจะได้รับใหญ่สวย
แต่ที่เราจะเห็นด้วยพยายาม

258
00:13:29,500 --> 00:13:33,040
มีสิ่งที่มีขนาดใหญ่มาก

259
00:13:33,040 --> 00:13:38,330
>> แต่โดยทั่วไปทั้งหมดกัญชา
ตารางฟังก์ชันแฮช

260
00:13:38,330 --> 00:13:47,215
ที่จะบอกคุณซึ่งถังที่จะใส่ในแต่ละ
ข้อมูลของคุณแต่ละองค์ประกอบของคุณใน

261
00:13:47,215 --> 00:13:51,140
วิธีง่ายๆในการคิดของตารางแฮช
ก็คือว่ามันเป็นเพียงถังของสิ่ง

262
00:13:51,140 --> 00:13:51,770
ใช่มั้ย?

263
00:13:51,770 --> 00:13:59,720
ดังนั้นเมื่อคุณมีการเรียงลำดับสิ่งที่โดย
เช่นอักษรตัวแรกของชื่อของพวกเขา

264
00:13:59,720 --> 00:14:01,820
นั่นคือชนิดเช่นตารางแฮช

265
00:14:01,820 --> 00:14:06,180
>> ดังนั้นถ้าผมให้กับกลุ่มพวกคุณเป็น
เป็นกลุ่มของใครก็ตามที่ชื่อเริ่ม

266
00:14:06,180 --> 00:14:11,670
กับที่นี่หรือใครก็ตามที่เป็นวันเกิด
ในเดือนมกราคม, กุมภาพันธ์, มีนาคม

267
00:14:11,670 --> 00:14:15,220
อะไรก็ตามที่เป็นได้อย่างมีประสิทธิภาพ
การสร้างตารางแฮช

268
00:14:15,220 --> 00:14:18,120
มันเป็นเพียงแค่การสร้างถังที่
คุณเรียงลำดับองค์ประกอบของคุณให้เป็น

269
00:14:18,120 --> 00:14:19,520
เพื่อให้คุณสามารถค้นหาได้ง่ายขึ้น

270
00:14:19,520 --> 00:14:22,300
ดังนั้นวิธีที่ฉันต้องการ
ที่จะหาหนึ่งของคุณ,

271
00:14:22,300 --> 00:14:24,680
ฉันไม่ได้มีการค้นหา
ผ่านแต่ละชื่อของคุณ

272
00:14:24,680 --> 00:14:29,490
ฉันจะเป็นเหมือนโอ้ฉันรู้ว่า
วันเกิดของแดเนียลเป็น in--

273
00:14:29,490 --> 00:14:30,240
ผู้ชม: --April

274
00:14:30,240 --> 00:14:30,948
ลำโพง 1: เมษายน

275
00:14:30,948 --> 00:14:33,120
ดังนั้นผมจึงมองในของฉันเมษายน
ถังและมีโชคใด ๆ

276
00:14:33,120 --> 00:14:38,270
เธอจะเป็นเพียงหนึ่งในการมีและ
เวลาของฉันเป็นอย่างต่อเนื่องในความรู้สึกที่

277
00:14:38,270 --> 00:14:41,230
ในขณะที่ถ้าผมต้องมอง
ผ่านทั้งกลุ่มของผู้คน

278
00:14:41,230 --> 00:14:43,090
มันจะใช้เวลานานมาก

279
00:14:43,090 --> 00:14:45,830
ดังนั้นตารางแฮชมีจริงๆเพียงแค่ถัง

280
00:14:45,830 --> 00:14:48,630
วิธีง่ายๆในการคิดว่าพวกเขา

281
00:14:48,630 --> 00:14:52,930
>> ดังนั้นสิ่งที่สำคัญมากเกี่ยวกับ
ตารางแฮชเป็นฟังก์ชันแฮช

282
00:14:52,930 --> 00:14:58,140
ดังนั้นสิ่งที่ฉันเพียงแค่พูดคุยเกี่ยวกับเช่น
ตัวอักษรตัวแรกของชื่อของคุณ

283
00:14:58,140 --> 00:15:01,450
หรือเดือนวันเกิดของคุณ
เหล่านี้เป็นความคิดที่ว่า

284
00:15:01,450 --> 00:15:03,070
จริงๆมีความสัมพันธ์กับฟังก์ชันแฮช

285
00:15:03,070 --> 00:15:08,900
มันเป็นเพียงวิธีการที่จะตัดสินใจซึ่ง
ถังองค์ประกอบคุณกำลังจะเข้าสู่, OK?

286
00:15:08,900 --> 00:15:14,850
ดังนั้นสำหรับ pset นี้คุณสามารถดู
สวยมากฟังก์ชันแฮชที่คุณต้องการ

287
00:15:14,850 --> 00:15:16,030
>> ไม่จำเป็นต้องเป็นของคุณเอง

288
00:15:16,030 --> 00:15:21,140
มีบางคนที่เจ๋งจริงๆจะออก
มีที่ทำทุกประเภทของคณิตศาสตร์บ้า

289
00:15:21,140 --> 00:15:25,170
และถ้าคุณต้องการที่จะทำให้คุณ
เช็คคำสะกดเร็วสุด

290
00:15:25,170 --> 00:15:27,620
ฉันจะแน่นอน
มองเข้าไปในหนึ่งในบรรดา

291
00:15:27,620 --> 00:15:32,390
>> แต่ยังมี
คนที่เรียบง่ายเช่นเดียวกับการคำนวณ

292
00:15:32,390 --> 00:15:39,010
ผลรวมของคำเช่น
ตัวอักษรแต่ละตัวมีจำนวน

293
00:15:39,010 --> 00:15:39,940
คำนวณผลบวก

294
00:15:39,940 --> 00:15:42,230
ที่กำหนดถั​​ง

295
00:15:42,230 --> 00:15:45,430
พวกเขายังมีคนง่ายว่า
ก็เป็นเหมือนทุกคนของที่นี่

296
00:15:45,430 --> 00:15:47,050
ทั้งหมดของ B ที่นี่

297
00:15:47,050 --> 00:15:48,920
หนึ่งในบรรดาการใด ๆ

298
00:15:48,920 --> 00:15:55,770
>> โดยทั่วไปก็แค่จะบอกคุณที่
ดัชนีอาร์เรย์องค์ประกอบของคุณควรจะไปเป็น

299
00:15:55,770 --> 00:15:58,690
เพียงแค่การตัดสินใจ bucket--
มันคือทั้งหมดที่ฟังก์ชันแฮชเป็น

300
00:15:58,690 --> 00:16:04,180
ดังนั้นที่นี่เรามีตัวอย่างซึ่งเป็น
เพียงแค่ตัวอักษรตัวแรกของสตริง

301
00:16:04,180 --> 00:16:05,900
ว่าฉันเป็นเพียงการพูดคุยเกี่ยวกับ

302
00:16:05,900 --> 00:16:11,900
>> เพื่อให้คุณมีกัญชานั่นเป็นเพียงบางส่วน
ตัวอักษรตัวแรกของสตริงลบของคุณ

303
00:16:11,900 --> 00:16:16,090
ซึ่งจะให้คุณบาง
ตัวเลขระหว่าง 0 และ 25

304
00:16:16,090 --> 00:16:20,790
และสิ่งที่คุณต้องการจะทำคือ
ตรวจสอบให้แน่ใจว่าเรื่องนี้แสดงให้เห็นถึง

305
00:16:20,790 --> 00:16:24,110
ขนาดของกัญชาของคุณ table--
กี่ถังมี

306
00:16:24,110 --> 00:16:25,860
มีหลายเหล่านี้
ฟังก์ชันแฮชพวกเขากำลัง

307
00:16:25,860 --> 00:16:31,630
จะได้รับการกลับค่าที่อาจจะ
จะสูงกว่าจำนวนที่เก็บข้อมูล

308
00:16:31,630 --> 00:16:33,610
จริงที่คุณมี
ในตารางแฮชของคุณ

309
00:16:33,610 --> 00:16:37,240
ดังนั้นคุณต้องทำให้
ตรวจสอบและสมัยโดยผู้

310
00:16:37,240 --> 00:16:42,190
มิฉะนั้นก็จะพูดว่า
โอ้มันควรจะเป็นในถัง 5,000

311
00:16:42,190 --> 00:16:46,040
แต่คุณมีเวลา 30 เท่านั้น
ถังในตารางแฮชของคุณ

312
00:16:46,040 --> 00:16:49,360
และแน่นอนเราทุกคนรู้ว่า
จะส่งผลให้เกิดข้อผิดพลาดบางบ้า

313
00:16:49,360 --> 00:16:52,870
เพื่อให้แน่ใจว่าการพอควรโดย
ขนาดของตารางแฮชของคุณ

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
เย็น

316
00:16:58,930 --> 00:17:00,506
ดังนั้นการชน

317
00:17:00,506 --> 00:17:02,620
ทุกคนที่ดีเพื่อให้ห่างไกล?

318
00:17:02,620 --> 00:17:03,120
mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> ผู้ชม: ทำไมมัน
กลับดังกล่าวมีมูลค่าขนาดใหญ่?

320
00:17:05,900 --> 00:17:09,210
>> ลำโพง 1: ขึ้นอยู่กับขั้นตอนวิธี
ว่าฟังก์ชันแฮชของคุณใช้

321
00:17:09,210 --> 00:17:12,270
บางส่วนของพวกเขาจะทำ
คูณบ้า

322
00:17:12,270 --> 00:17:16,270
และมันคือทั้งหมดที่เกี่ยวกับการ
กระจาย,

323
00:17:16,270 --> 00:17:18,490
เพื่อให้พวกเขาทำบางอย่างจริงๆ
สิ่งที่บ้าบางครั้ง

324
00:17:18,490 --> 00:17:20,960
นั่นคือทั้งหมดที่

325
00:17:20,960 --> 00:17:22,140
อะไรอีกหรือไม่

326
00:17:22,140 --> 00:17:22,829
ตกลง

327
00:17:22,829 --> 00:17:24,480
>> ดังนั้นการชน

328
00:17:24,480 --> 00:17:29,270
โดยทั่วไปที่ผมกล่าวว่าก่อนหน้านี้
ในสถานการณ์กรณีที่ดีที่สุด

329
00:17:29,270 --> 00:17:32,040
ถังใด ๆ ที่ฉันมองเข้าไปในเป็น
จะมีสิ่งหนึ่งที่

330
00:17:32,040 --> 00:17:34,160
ดังนั้นผมจึงไม่ต้องมองเลยใช่มั้ย?

331
00:17:34,160 --> 00:17:37,040
ฉันอาจรู้ว่ามันมีหรือเป็น
ไม่ได้และนั่นคือสิ่งที่เราต้องการจริงๆ

332
00:17:37,040 --> 00:17:43,960
แต่ถ้าเรามีนับหมื่นของ
จุดข้อมูลและน้อยกว่าตัวเลขที่

333
00:17:43,960 --> 00:17:48,700
ของถังที่เรากำลังจะมี
ชนที่ท้ายที่สุดสิ่งที่

334
00:17:48,700 --> 00:17:54,210
เป็นไปได้ที่จะจบลงใน
ถังที่มีอยู่แล้วองค์ประกอบ

335
00:17:54,210 --> 00:17:57,390
>> ดังนั้นคำถามคือสิ่งที่
เราจะทำในกรณีที่?

336
00:17:57,390 --> 00:17:58,480
ทำในสิ่งที่เราจะทำอย่างไร

337
00:17:58,480 --> 00:17:59,300
เรามีบางสิ่งบางอย่างที่นั่น?

338
00:17:59,300 --> 00:18:00,060
เราเพียงแค่โยนมันออกมา?

339
00:18:00,060 --> 00:18:00,700
>> เลขที่

340
00:18:00,700 --> 00:18:01,980
เราต้องให้ทั้งสองของพวกเขา

341
00:18:01,980 --> 00:18:06,400
ดังนั้นวิธีการที่เรา
ที่มักจะทำคืออะไร?

342
00:18:06,400 --> 00:18:08,400
เป็นโครงสร้างข้อมูลอะไร
เราก็พูดคุยกันเกี่ยวกับ?

343
00:18:08,400 --> 00:18:09,316
ผู้ชม: รายการที่เชื่อมโยง

344
00:18:09,316 --> 00:18:10,500
ลำโพง 1: รายการที่เชื่อมโยง

345
00:18:10,500 --> 00:18:16,640
ดังนั้นตอนนี้แทนแต่ละเหล่านี้
ถังเพียงแค่มีองค์ประกอบหนึ่ง,

346
00:18:16,640 --> 00:18:24,020
มันจะมีรายการที่เชื่อมโยงของ
องค์ประกอบที่ถูกถกลงไป

347
00:18:24,020 --> 00:18:27,588
ตกลงทุกคนไม่ได้รับชนิดของความคิดที่ว่า?

348
00:18:27,588 --> 00:18:30,546
เพราะเราไม่สามารถมีอาร์เรย์
เพราะเราไม่ทราบว่าหลายสิ่งหลายอย่าง

349
00:18:30,546 --> 00:18:31,730
เป็นไปได้ในการมี

350
00:18:31,730 --> 00:18:36,540
รายการที่เชื่อมโยงช่วยให้เราสามารถ
มีเพียงจำนวนที่แน่นอนว่า

351
00:18:36,540 --> 00:18:38,465
มี hashed ลงในถังที่ใช่มั้ย?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> ดังนั้นเส้นละเอียดเป็น
พื้น idea-- นี้

354
00:18:50,500 --> 00:18:52,300
มันเป็นวิธีหนึ่งที่จะจัดการกับการปะทะกัน

355
00:18:52,300 --> 00:18:58,010
สิ่งที่คุณสามารถทำได้คือถ้าในเรื่องนี้
กรณีที่ถูกแบล็กเบอร์ hashed เป็น 1

356
00:18:58,010 --> 00:19:01,130
และเรามีอยู่แล้ว
สิ่งที่มีคุณเพียงแค่

357
00:19:01,130 --> 00:19:04,840
ให้ไปลงจน
คุณจะพบช่องว่าง

358
00:19:04,840 --> 00:19:06,370
นั่นเป็นวิธีหนึ่งที่จะจัดการกับมัน

359
00:19:06,370 --> 00:19:09,020
วิธีอื่น ๆ ในการจัดการ
มันขึ้นอยู่กับสิ่งที่เราเพียง

360
00:19:09,020 --> 00:19:12,280
called-- ที่เชื่อมโยง
รายการที่เรียกว่าการผูกมัด

361
00:19:12,280 --> 00:19:20,510
>> ดังนั้นความคิดนี้ทำงานถ้า
ตารางแฮชของคุณที่คุณคิดว่า

362
00:19:20,510 --> 00:19:24,150
มีขนาดใหญ่กว่า
ข้อมูลของคุณตั้งค่าหรือถ้าคุณ

363
00:19:24,150 --> 00:19:28,870
ต้องการที่จะลองและลดการผูกมัด
จนกว่าจะมีความจำเป็นอย่างยิ่ง

364
00:19:28,870 --> 00:19:34,050
ดังนั้นสิ่งหนึ่งที่เป็นเส้นตรง
เห็นได้ชัดว่าหมายถึงละเอียด

365
00:19:34,050 --> 00:19:37,290
ว่าฟังก์ชันแฮชของคุณ
ไม่มากที่เป็นประโยชน์

366
00:19:37,290 --> 00:19:42,200
เพราะคุณกำลังจะสิ้นสุดการใช้
ฟังก์ชันแฮชของคุณได้รับไปยังจุดที่

367
00:19:42,200 --> 00:19:46,400
คุณ Linear สอบสวนลงไป
สถานที่ที่มีอยู่บางส่วน

368
00:19:46,400 --> 00:19:49,670
แต่ตอนนี้แน่นอนอะไร
อื่น ๆ ที่จบลงที่นั่น

369
00:19:49,670 --> 00:19:52,050
คุณจะต้อง
ค้นหายิ่งขึ้นลง

370
00:19:52,050 --> 00:19:55,650
>> และมีมากขึ้น
ค่าใช้จ่ายในการค้นหาที่

371
00:19:55,650 --> 00:19:59,820
จะเข้าสู่ป้อนองค์ประกอบ
ในตารางแฮชของคุณตอนนี้ใช่มั้ย?

372
00:19:59,820 --> 00:20:05,640
และตอนนี้เมื่อคุณไปและพยายามหา
เบอร์รี่อีกครั้งคุณกำลังจะสับมัน

373
00:20:05,640 --> 00:20:07,742
และมันจะพูดว่า
โอ้ดูในถังที่ 1

374
00:20:07,742 --> 00:20:09,700
และก็จะไม่ได้
ในถังที่ 1 เพื่อให้คุณ

375
00:20:09,700 --> 00:20:11,970
จะมีการสำรวจ
ส่วนที่เหลือของเหล่านี้

376
00:20:11,970 --> 00:20:17,720
ดังนั้นจึงเป็นเรื่องที่มีประโยชน์บางครั้ง
แต่ในกรณีส่วนใหญ่

377
00:20:17,720 --> 00:20:22,660
เรากำลังจะบอกว่า
ผูกมัดคือสิ่งที่คุณต้องการจะทำ

378
00:20:22,660 --> 00:20:25,520
>> ดังนั้นเราได้พูดคุยเกี่ยวกับเรื่องนี้ก่อนหน้านี้

379
00:20:25,520 --> 00:20:27,812
ผมได้น้อยหน้าของตัวเอง

380
00:20:27,812 --> 00:20:33,560
แต่การผูกมัดเป็นพื้นว่า
ถังในตารางแฮชของคุณในแต่ละ

381
00:20:33,560 --> 00:20:36,120
เป็นเพียงรายการที่เชื่อมโยง

382
00:20:36,120 --> 00:20:39,660
>> ดังนั้นวิธีอื่นหรือทางเทคนิคเพิ่มเติม
วิธีการคิดของตารางแฮช

383
00:20:39,660 --> 00:20:44,490
คือว่ามันเป็นเพียงแค่อาร์เรย์
ของรายการที่เชื่อมโยงซึ่ง

384
00:20:44,490 --> 00:20:49,330
เมื่อคุณกำลังเขียนพจนานุกรมของคุณ
และคุณกำลังพยายามที่จะโหลดมัน

385
00:20:49,330 --> 00:20:52,070
คิดว่ามันเป็น
อาร์เรย์ของรายการเชื่อมโยง

386
00:20:52,070 --> 00:20:54,390
จะทำให้มันง่ายมาก
สำหรับคุณที่จะเริ่มต้น

387
00:20:54,390 --> 00:20:57,680
>> ผู้ชม: ดังนั้นตารางแฮช
มีขนาดที่กำหนดไว้

388
00:20:57,680 --> 00:20:58,980
เช่น [ไม่ได้ยิน] ของถัง?

389
00:20:58,980 --> 00:20:59,220
>> ลำโพง 1: ขวา

390
00:20:59,220 --> 00:21:01,655
ดังนั้นจึงมีจำนวนชุดของ
ถังที่คุณ determine--

391
00:21:01,655 --> 00:21:03,530
ซึ่งพวกคุณควร
อย่าลังเลที่จะเล่นกับ

392
00:21:03,530 --> 00:21:05,269
มันอาจจะเป็นเย็นสวย
เพื่อดูสิ่งที่เกิดขึ้น

393
00:21:05,269 --> 00:21:06,810
ในขณะที่คุณเปลี่ยนจำนวนของถัง

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
แต่ใช่มันมี
กำหนดจำนวนของถัง

396
00:21:11,510 --> 00:21:15,360
สิ่งที่ช่วยให้คุณเพื่อให้พอดีกับเป็น
หลายองค์ประกอบตามที่คุณต้องการ

397
00:21:15,360 --> 00:21:19,350
คือที่กำลังแยกนี้ที่คุณ
มีการเชื่อมโยงรายชื่อในแต่ละถัง

398
00:21:19,350 --> 00:21:22,850
นั่นหมายความว่าตารางแฮชของคุณ
จะตรงขนาด

399
00:21:22,850 --> 00:21:25,440
ที่คุณต้องการให้เป็นใช่มั้ย?

400
00:21:25,440 --> 00:21:27,358
นั่นเป็นจุดรวมของรายการที่เชื่อมโยง

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
เย็น

403
00:21:32,480 --> 00:21:38,780
>> เพื่อให้ทุกคนตกลงที่นั่น?

404
00:21:38,780 --> 00:21:39,801
สิทธิ์ทั้งหมด

405
00:21:39,801 --> 00:21:40,300
อา

406
00:21:40,300 --> 00:21:41,860
สิ่งที่เพิ่งเกิดขึ้น?

407
00:21:41,860 --> 00:21:42,960
จริงๆตอนนี้

408
00:21:42,960 --> 00:21:45,250
คิดว่าคนที่ฆ่าฉัน

409
00:21:45,250 --> 00:21:52,060
>> ตกลงเราจะไปสู่
พยายามที่จะบ้าเล็กน้อย

410
00:21:52,060 --> 00:21:53,140
ฉันชอบตารางแฮช

411
00:21:53,140 --> 00:21:54,460
ผมคิดว่าพวกเขากำลังเย็นจริงๆ

412
00:21:54,460 --> 00:21:56,710
พยายามที่จะเย็นเกินไป

413
00:21:56,710 --> 00:21:59,590
>> เพื่อให้ทุกคนไม่จำสิ่งที่พยายามคืออะไร?

414
00:21:59,590 --> 00:22:01,740
คุณควรจะได้หายไปกว่า
มันสั้นในการบรรยาย?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
คุณจำชนิดของมันทำงานอย่างไร

417
00:22:06,377 --> 00:22:08,460
ผู้ชม: ฉันแค่พยักหน้า
ว่าเราไม่ไปกว่านั้น

418
00:22:08,460 --> 00:22:09,626
ลำโพง 1: เราไม่ไปกว่านั้น

419
00:22:09,626 --> 00:22:13,100
ตกลงเราจริงๆจะไป
กว่าตอนนี้มันคือสิ่งที่เรากำลังจะบอกว่า

420
00:22:13,100 --> 00:22:14,860
>> ผู้ชม: นั่นคือสำหรับการดึงต้นไม้

421
00:22:14,860 --> 00:22:15,280
>> ลำโพง 1: ใช่

422
00:22:15,280 --> 00:22:16,196
มันเป็นต้นไม้ดึง

423
00:22:16,196 --> 00:22:16,960
น่ากลัว

424
00:22:16,960 --> 00:22:23,610
ดังนั้นสิ่งหนึ่งที่จะสังเกตเห็นที่นี่คือเรา
กำลังมองหาที่ตัวละครแต่ละคน

425
00:22:23,610 --> 00:22:24,480
ที่นี่ใช่มั้ย?

426
00:22:24,480 --> 00:22:29,710
>> ดังนั้นก่อนที่จะมีฟังก์ชันแฮชของเราเรา
กำลังหาที่คำพูดโดยรวม

427
00:22:29,710 --> 00:22:32,270
และตอนนี้เรากำลังมองหามากขึ้น
ที่ตัวละครใช่มั้ย?

428
00:22:32,270 --> 00:22:38,380
ดังนั้นเราจึงมีแมกซ์เวลที่นี่และเมนเดล

429
00:22:38,380 --> 00:22:47,840
ดังนั้นโดยทั่วไป try-- วิธีที่จะคิดว่า
เกี่ยวกับเรื่องนี้คือการที่ทุกระดับที่นี่

430
00:22:47,840 --> 00:22:49,000
เป็นอาร์เรย์ของตัวอักษร

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
ดังนั้นนี่คือโหนดรากของคุณที่นี่ใช่มั้ย?

433
00:22:55,790 --> 00:23:01,980
นี้มีตัวอักษรทั้งหมดของ
ตัวอักษรสำหรับการเริ่มต้นของทุกคำ

434
00:23:01,980 --> 00:23:06,480
>> และสิ่งที่คุณต้องการจะทำคือ
กล่าวว่าตกลงเรามีบางคำ M

435
00:23:06,480 --> 00:23:10,590
เรากำลังจะไปมองหาแมกซ์เวลดังนั้น
เราไปที่เอ็มและเอ็มชี้ไปที่ทั้ง

436
00:23:10,590 --> 00:23:14,800
อาร์เรย์อื่น ๆ ที่ทุก
คำตราบใดที่มี

437
00:23:14,800 --> 00:23:17,044
เป็นคำที่มี
เป็นจดหมายฉบับที่สอง,

438
00:23:17,044 --> 00:23:19,460
ตราบใดที่มีคำว่า
มี B เป็นจดหมายฉบับที่สอง,

439
00:23:19,460 --> 00:23:24,630
มันจะมีตัวชี้
จะบางอาร์เรย์ต่อไป

440
00:23:24,630 --> 00:23:29,290
>> มีไม่น่าจะเป็น
คำว่าสิ่งที่ส

441
00:23:29,290 --> 00:23:32,980
ดังนั้นที่ตำแหน่ง P ในครั้งนี้
อาเรย์มันก็จะเป็นโมฆะ

442
00:23:32,980 --> 00:23:38,840
มันจะบอกว่าตกลงมีคำว่าไม่มี
ที่มี M ตามด้วย P, OK?

443
00:23:38,840 --> 00:23:43,100
ดังนั้นหากเราคิดเกี่ยวกับมันแต่ละ
หนึ่งในสิ่งที่มีขนาดเล็กเหล่านี้

444
00:23:43,100 --> 00:23:47,990
เป็นจริงหนึ่งในจำนวนนี้
อาร์เรย์ขนาดใหญ่จากถึง Z

445
00:23:47,990 --> 00:23:55,064
ดังนั้นสิ่งที่อาจจะเป็นหนึ่งในสิ่งที่
ว่าเป็นชนิดของข้อบกพร่องของลอง?

446
00:23:55,064 --> 00:23:56,500
>> ผู้ชม: จำนวนมากของหน่วยความจำ

447
00:23:56,500 --> 00:23:59,940
>> ลำโพง 1: มันเป็นตันของหน่วยความจำใช่มั้ย?

448
00:23:59,940 --> 00:24:08,750
หนึ่งแต่ละบล็อกเหล่านี้ที่นี่
แสดงให้เห็นถึงช่องว่างที่ 26, 26 องค์ประกอบอาร์เรย์

449
00:24:08,750 --> 00:24:13,680
ดังนั้นพยายามที่ได้รับอย่างไม่น่าเชื่อพื้นที่หนัก

450
00:24:13,680 --> 00:24:17,100
>> แต่พวกเขามีความรวดเร็วมาก

451
00:24:17,100 --> 00:24:22,540
อย่างรวดเร็วอย่างไม่น่าเชื่อ แต่
จริงๆพื้นที่ไม่มีประสิทธิภาพ

452
00:24:22,540 --> 00:24:24,810
ชนิดของต้องคิด
ที่หนึ่งที่คุณต้องการ

453
00:24:24,810 --> 00:24:29,470
เหล่านี้จริงๆเย็นสำหรับ pset ของคุณ
แต่พวกเขาจะใช้เวลามากของหน่วยความจำ,

454
00:24:29,470 --> 00:24:30,290
เพื่อให้คุณค้าปิด

455
00:24:30,290 --> 00:24:31,480
ใช่?

456
00:24:31,480 --> 00:24:34,300
>> ผู้ชม: มันจะเป็นไปได้
การตั้งค่าลองแล้ว

457
00:24:34,300 --> 00:24:37,967
เมื่อคุณมีทั้งหมด
ข้อมูลในนั้นที่คุณ need--

458
00:24:37,967 --> 00:24:39,550
ผมไม่ทราบว่าจะทำให้ความรู้สึก

459
00:24:39,550 --> 00:24:42,200
ผมได้รับการกำจัดของทุกคน
ตัวอักษรเป็นโมฆะ แต่แล้ว

460
00:24:42,200 --> 00:24:42,910
คุณจะไม่สามารถที่จะดัชนี them--

461
00:24:42,910 --> 00:24:43,275
>> ลำโพงที่ 1: คุณยังคงต้องให้พวกเขา

462
00:24:43,275 --> 00:24:44,854
>> ผู้ชม: - วิธีการเดียวกันในแต่ละครั้ง

463
00:24:44,854 --> 00:24:45,520
ลำโพง 1: ใช่

464
00:24:45,520 --> 00:24:50,460
คุณจำเป็นต้องมีตัวละครที่เป็นโมฆะที่จะปล่อยให้
คุณทราบว่ามีไม่คำมี

465
00:24:50,460 --> 00:24:52,040
เบนไม่คุณมีสิ่งที่คุณต้องการ?

466
00:24:52,040 --> 00:24:52,540
ตกลง

467
00:24:52,540 --> 00:24:54,581
สิทธิทั้งหมดดังนั้นเราจะ
ที่จะไปนิด ๆ หน่อย ๆ

468
00:24:54,581 --> 00:24:58,920
เป็นรายละเอียดทางเทคนิคที่อยู่เบื้องหลัง
และพยายามทำงานผ่านตัวอย่างเช่น

469
00:24:58,920 --> 00:25:01,490
>> ตกลงดังนั้นนี่คือสิ่งเดียวกัน

470
00:25:01,490 --> 00:25:06,290
ขณะที่ในรายชื่อที่เชื่อมโยงหลักของเรา
ชนิดเเล้สิ่งที่คำที่ฉันต้องการ? -

471
00:25:06,290 --> 00:25:08,350
เช่นการสร้างบล็อกเป็นโหนด

472
00:25:08,350 --> 00:25:12,280
ในลองเรายังมีโหนด
แต่จะกำหนดไว้แตกต่างกัน

473
00:25:12,280 --> 00:25:17,000
>> ดังนั้นเราจึงมีบางอย่างที่บูล
แสดงให้เห็นถึงว่าคำจริง

474
00:25:17,000 --> 00:25:23,530
ที่มีอยู่ในสถานที่นี้แล้ว
เรามีอาร์เรย์บางตรงนี้หรือเปล่า

475
00:25:23,530 --> 00:25:27,840
นี้เป็นตัวชี้ไป
อาร์เรย์ของ 27 ตัวอักษร

476
00:25:27,840 --> 00:25:33,339
และนี่คือสำหรับในกรณีนี้นี้
27-- ผมมั่นใจว่าทุกท่านจะชอบรอ

477
00:25:33,339 --> 00:25:34,880
มี 2​​6 ตัวอักษรในตัวอักษร

478
00:25:34,880 --> 00:25:36,010
เรามี 27 ทำไม?

479
00:25:36,010 --> 00:25:37,870
>> ดังนั้นขึ้นอยู่กับ
วิธีการที่คุณใช้นี้

480
00:25:37,870 --> 00:25:43,240
นี้มาจาก pset ว่า
ได้รับอนุญาตให้เครื่องหมาย

481
00:25:43,240 --> 00:25:46,010
เพื่อที่ว่าทำไมคนพิเศษ

482
00:25:46,010 --> 00:25:50,500
นอกจากนี้คุณยังจะมีในบางส่วน
กรณีที่เทอร์มิ null

483
00:25:50,500 --> 00:25:53,230
จะรวมเป็นหนึ่ง
อักขระที่จะได้รับอนุญาตให้เป็น

484
00:25:53,230 --> 00:25:56,120
และนั่นคือวิธีที่พวกเขาตรวจสอบ
ดูว่าเป็นจุดสิ้นสุดของคำว่า

485
00:25:56,120 --> 00:26:01,340
หากคุณสนใจตรวจสอบ
วิดีโอของเควินใน study.cs50,

486
00:26:01,340 --> 00:26:04,790
เช่นเดียวกับวิกิพีเดียมี
บางแหล่งข้อมูลที่ดีมี

487
00:26:04,790 --> 00:26:09,000
>> แต่เรากำลังจะผ่านไปเพียงชนิด
ว่าคุณสามารถทำงานผ่านลอง

488
00:26:09,000 --> 00:26:11,010
ถ้าคุณได้รับหนึ่ง

489
00:26:11,010 --> 00:26:16,230
ดังนั้นเราจึงมีอย่างใดอย่างหนึ่งที่ง่ายสุดที่นี่
มีคำว่า "ค้างคาว" และ "ซูม" ในพวกเขา

490
00:26:16,230 --> 00:26:18,920
และที่เราเห็นขึ้นที่นี่
พื้นที่เล็ก ๆ นี้ที่นี่

491
00:26:18,920 --> 00:26:22,560
แสดงให้เห็นถึงบูลของเราที่
กล่าวว่าใช่นี้เป็นคำ

492
00:26:22,560 --> 00:26:27,060
และจากนั้นก็มีของเรา
อาร์เรย์ของตัวละครใช่มั้ย?

493
00:26:27,060 --> 00:26:33,480
>> ดังนั้นเรากำลังจะผ่านไป
การหา "ค้างคาว" ในความพยายามนี้

494
00:26:33,480 --> 00:26:38,340
ดังนั้นจะเริ่มต้นที่ด้านบนขวา?

495
00:26:38,340 --> 00:26:46,290
และเรารู้ว่าขสอดคล้องกับ
ดัชนีสององค์ประกอบที่สอง

496
00:26:46,290 --> 00:26:47,840
ในอาร์เรย์นี้เพราะ A และ B

497
00:26:47,840 --> 00:26:51,340
ดังนั้นประมาณหนึ่งวินาที

498
00:26:51,340 --> 00:26:58,820
>> และกล่าวว่า, OK เย็นตามที่เป็น
อาเรย์ต่อไปเพราะถ้าเราจำ

499
00:26:58,820 --> 00:27:02,160
มันไม่ใช่ว่าแต่ละเหล่านี้
จริงมีองค์ประกอบ

500
00:27:02,160 --> 00:27:07,110
หนึ่งในอาร์เรย์แต่ละเหล่านี้
ประกอบด้วยตัวชี้ใช่มั้ย?

501
00:27:07,110 --> 00:27:10,030
มันเป็นความแตกต่างที่สำคัญที่จะทำให้

502
00:27:10,030 --> 00:27:13,450
>> ฉันรู้ว่านี้เป็นไป be-- พยายามที่จะ
ยากมากที่จะได้รับในครั้งแรก

503
00:27:13,450 --> 00:27:15,241
ดังนั้นแม้ว่านี้
ครั้งที่สองหรือสาม

504
00:27:15,241 --> 00:27:18,370
และจะยังคงชนิด
ของที่ดูเหมือนยาก

505
00:27:18,370 --> 00:27:21,199
ฉันสัญญาว่าถ้าคุณไปดู
ในวันพรุ่งนี้สั้นอีกครั้ง

506
00:27:21,199 --> 00:27:22,740
มันอาจจะทำให้รู้สึกมากขึ้น

507
00:27:22,740 --> 00:27:23,890
มันใช้เวลามากในการย่อย

508
00:27:23,890 --> 00:27:27,800
บางครั้งฉันยังคงรู้สึก
เหมือนรออะไรคือลอง?

509
00:27:27,800 --> 00:27:29,080
ฉันจะใช้นี้ได้อย่างไร

510
00:27:29,080 --> 00:27:33,880
>> ดังนั้นเราจึงได้ b ในกรณีนี้
ซึ่งเป็นดัชนีที่สองของเรา

511
00:27:33,880 --> 00:27:40,240
ถ้าเรามีการพูด, C หรือ
งหรือหนังสืออื่น ๆ

512
00:27:40,240 --> 00:27:45,810
เราต้องกลับไปที่แผนที่ดัชนีที่
ของอาร์เรย์ของเราที่ที่สอดคล้องกับ

513
00:27:45,810 --> 00:27:56,930
ดังนั้นเราจะใช้เวลาเช่น rchar และเราก็
ลบออกจากแผนที่ลงใน 0-25

514
00:27:56,930 --> 00:27:58,728
ทุกคนที่ดีวิธีการที่เรา
แผนที่ตัวละครของเรา?

515
00:27:58,728 --> 00:28:00,440
ตกลง

516
00:28:00,440 --> 00:28:05,980
>> ดังนั้นเราจึงไปที่สองและเรา
เห็นว่าใช่มันจะไม่เป็นโมฆะ

517
00:28:05,980 --> 00:28:07,780
เราสามารถย้ายไปยังอาเรย์ต่อไปนี้

518
00:28:07,780 --> 00:28:12,300
ดังนั้นเราจึงไปแถวต่อไปที่นี่

519
00:28:12,300 --> 00:28:15,500
>> และเราบอกว่าโอเคตอนนี้เรา
ต้องดูว่าอยู่ที่นี่

520
00:28:15,500 --> 00:28:18,590
เป็นโมฆะหรือไม่ได้
จริงก้าวไปข้างหน้า?

521
00:28:18,590 --> 00:28:21,880
ดังนั้นย้ายจริง
ส่งต่อในอาร์เรย์นี้

522
00:28:21,880 --> 00:28:24,570
และเราบอกว่าโอเคทีเป็นตัวอักษรสุดท้ายของเรา

523
00:28:24,570 --> 00:28:27,580
ดังนั้นเราจึงไปที่เสื้อที่ดัชนี

524
00:28:27,580 --> 00:28:30,120
แล้วเราก้าวไปข้างหน้า
เพราะมีอีกคนหนึ่ง

525
00:28:30,120 --> 00:28:38,340
และหนึ่งนี้กล่าวว่าโดยทั่วไปว่าใช่
มันบอกว่ามีคำที่ตรงนี้

526
00:28:38,340 --> 00:28:41,750
ว่าถ้าคุณทำตามนี้
เส้นทางที่คุณได้มาถึง

527
00:28:41,750 --> 00:28:43,210
คำพูดที่เราทราบว่าเป็น "ค้างคาว".

528
00:28:43,210 --> 00:28:43,800
ใช่?

529
00:28:43,800 --> 00:28:46,770
>> ผู้ชม: มันเป็นมาตรฐานที่จะมีที่
เป็นดัชนี 0 แล้วมีการเรียงลำดับที่ 1

530
00:28:46,770 --> 00:28:47,660
หรือมีที่สิ้นสุดหรือไม่

531
00:28:47,660 --> 00:28:48,243
>> ลำโพง 1: ฉบับที่

532
00:28:48,243 --> 00:28:55,360
ดังนั้นหากเรามองกลับไปที่ของเรา
ประกาศที่นี่ก็บูล,

533
00:28:55,360 --> 00:28:59,490
ดังนั้นจึงเป็นองค์ประกอบของตัวเองในโหนดของคุณ

534
00:28:59,490 --> 00:29:03,331
ดังนั้นจึงไม่เป็นส่วนหนึ่งของอาร์เรย์

535
00:29:03,331 --> 00:29:03,830
เย็น

536
00:29:03,830 --> 00:29:08,370
ดังนั้นเมื่อเราเสร็จสิ้นคำพูดของเราและเรา
ที่แถวนี้สิ่งที่เราต้องการจะทำ

537
00:29:08,370 --> 00:29:12,807
คือจะตรวจสอบคือคำนี้

538
00:29:12,807 --> 00:29:14,390
และในกรณีนี้ก็จะกลับมาใช่

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> ดังนั้นเมื่อทราบว่าเรารู้ว่า "สวนสัตว์" -
เรารู้ว่าเป็นมนุษย์ที่ "สวนสัตว์" เป็นคำที่

541
00:29:24,090 --> 00:29:24,820
ใช่มั้ย?

542
00:29:24,820 --> 00:29:28,990
แต่จะลองที่นี่
บอกว่าไม่มีก็ไม่ได้

543
00:29:28,990 --> 00:29:33,980
และมันก็จะบอกว่าเพราะเรา
ยังไม่ได้กำหนดว่ามันเป็นคำที่นี่

544
00:29:33,980 --> 00:29:40,440
แม้ว่าเราจะสามารถสำรวจ
ผ่านไปแถวนี้

545
00:29:40,440 --> 00:29:43,890
ลองนี้จะบอกว่าไม่มี
สวนสัตว์ไม่ได้อยู่ในพจนานุกรมของคุณ

546
00:29:43,890 --> 00:29:47,070
เพราะเรายังไม่ได้
กำหนดให้มันเป็นเช่นนั้น

547
00:29:47,070 --> 00:29:52,870
>> ดังนั้นวิธีหนึ่งที่จะทำ that--
โอ้ขอโทษหนึ่งนี้

548
00:29:52,870 --> 00:29:59,450
ดังนั้นในกรณีนี้ "สวนสัตว์" ไม่
คำ แต่มันอยู่ในลองของเรา

549
00:29:59,450 --> 00:30:05,690
แต่ในคนนี้บอกว่าเราอยากให้มันเป็น
แนะนำคำว่า "อาบน้ำ" สิ่งที่เกิดขึ้น

550
00:30:05,690 --> 00:30:08,260
คือเราทำตาม through-- B, A, T

551
00:30:08,260 --> 00:30:11,820
เราอยู่ในแถวนี้และ
เราไปค้นหาชั่วโมง

552
00:30:11,820 --> 00:30:15,220
>> ในกรณีนี้เมื่อเรา
มองไปที่ตัวชี้ไปที่ H,

553
00:30:15,220 --> 00:30:17,890
มันชี้ไปที่ NULL, OK?

554
00:30:17,890 --> 00:30:20,780
ดังนั้นถ้ามันอย่างชัดเจน
ชี้ไปยังอาร์เรย์อื่น

555
00:30:20,780 --> 00:30:25,000
คุณคิดว่าตัวชี้ทั้งหมด
ในอาร์เรย์นี้จะชี้ให้เป็นโมฆะ

556
00:30:25,000 --> 00:30:28,270
ดังนั้นในกรณีนี้, H ชี้
ให้เป็นโมฆะดังนั้นเราจึงไม่สามารถทำอะไร

557
00:30:28,270 --> 00:30:31,540
ดังนั้นมันก็จะกลับมา
เท็จ "อาบน้ำ" ไม่ได้อยู่ในที่นี่

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
ดังนั้นตอนนี้เรากำลังจริง
จะไปผ่าน

560
00:30:35,810 --> 00:30:39,790
วิธีการที่เราจะพูดจริง
ที่ "สวนสัตว์" ที่อยู่ในความพยายามของเรา

561
00:30:39,790 --> 00:30:42,920
เราไม่ใส่ "สวนสัตว์" วิธีในลองของเราหรือไม่

562
00:30:42,920 --> 00:30:47,810
ดังนั้นในทางเดียวกันกับที่เราเริ่มต้นด้วย
รายการที่เชื่อมโยงของเราเราเริ่มต้นที่ราก

563
00:30:47,810 --> 00:30:50,600
เมื่อสงสัยเริ่มต้นที่
รากของสิ่งเหล่านี้

564
00:30:50,600 --> 00:30:53,330
>> และเราจะพูดว่าตกลง Z

565
00:30:53,330 --> 00:30:55,650
Z ที่มีอยู่ในนี้และจะไม่

566
00:30:55,650 --> 00:30:58,370
ดังนั้นคุณจะย้ายไป
อาเรย์ต่อไปของคุณ OK?

567
00:30:58,370 --> 00:31:01,482
และจากนั้นในหน้าหนึ่ง
เราพูดว่าตกลงไม่ o อยู่?

568
00:31:01,482 --> 00:31:03,000
มันไม่

569
00:31:03,000 --> 00:31:04,330
นี้อีกครั้ง

570
00:31:04,330 --> 00:31:08,670
>> และอื่น ๆ หนึ่งต่อไปของเราที่เราได้กล่าวว่า
ตกลง "สวนสัตว์" ที่มีอยู่แล้วที่นี่

571
00:31:08,670 --> 00:31:12,440
ทั้งหมดที่เราต้องทำคือการตั้งเท่านี้
เป็นจริงว่ามีคำมี

572
00:31:12,440 --> 00:31:15,260
ถ้าคุณได้ทำตามทุกอย่าง
ก่อนที่จะถึงจุดนั้น

573
00:31:15,260 --> 00:31:17,030
มันเป็นคำพูดดังนั้นเพียง
ตั้งค่าเท่ากับดังกล่าว

574
00:31:17,030 --> 00:31:17,530
ใช่?

575
00:31:17,530 --> 00:31:22,550
>> ผู้ชม: ดังนั้นแล้วไม่ว่า
หมายความว่า "บริติชแอร์เวย์" เป็นคำที่ยัง?

576
00:31:22,550 --> 00:31:24,120
>> ลำโพง 1: ฉบับที่

577
00:31:24,120 --> 00:31:28,870
ดังนั้นในกรณีนี้ "Ba" เราจะได้รับ
ที่นี่เราจะบอกว่ามันเป็นคำที่

578
00:31:28,870 --> 00:31:31,590
และก็ยังจะไม่มี

579
00:31:31,590 --> 00:31:32,822
OK?

580
00:31:32,822 --> 00:31:33,740
mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> ผู้ชม: ดังนั้นเมื่อคุณเป็นมัน
คำพูดและการที่คุณบอกว่าใช่แล้วมัน

582
00:31:36,360 --> 00:31:38,380
จะมีไป M?

583
00:31:38,380 --> 00:31:42,260
>> ลำโพง 1: ดังนั้นนี้จะทำอย่างไร
with-- คุณโหลดนี้

584
00:31:42,260 --> 00:31:43,640
คุณจะพูดว่า "สวนสัตว์" เป็นคำ

585
00:31:43,640 --> 00:31:47,020
เมื่อคุณไปที่ check--
เช่นสมมติว่าคุณต้องการที่จะพูดว่า

586
00:31:47,020 --> 00:31:49,400
ไม่ "สวนสัตว์" ที่มีอยู่ในพจนานุกรมนี้?

587
00:31:49,400 --> 00:31:54,200
คุณเท่านั้นที่จะไปค้นหา "สวนสัตว์"
แล้วตรวจสอบเพื่อดูว่ามันเป็นคำ

588
00:31:54,200 --> 00:31:57,291
คุณไม่เคยไปที่จะย้าย
ผ่านไปยังม. เพราะไม่ว่า

589
00:31:57,291 --> 00:31:58,290
สิ่งที่คุณกำลังมองหา

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> ดังนั้นหากเราต้องการที่จะเป็นจริง
เพิ่ม "อาบน้ำ" ในความพยายามนี้

592
00:32:08,070 --> 00:32:11,390
เราจะทำในสิ่งเดียวกัน
ในขณะที่เราทำกับ "สวนสัตว์"

593
00:32:11,390 --> 00:32:15,380
ยกเว้นเราจะเห็นว่าเมื่อเรา
ลองและได้รับการชั่วโมงก็ไม่ได้มีอยู่

594
00:32:15,380 --> 00:32:20,090
เพื่อให้คุณสามารถคิดนี้เป็นความพยายามที่
การเพิ่มโหนดใหม่ลงในรายการที่เชื่อมโยง

595
00:32:20,090 --> 00:32:27,210
ดังนั้นเราจะต้องเพิ่มอีก
หนึ่งในอาร์เรย์เหล่านี้เช่นดังนั้น

596
00:32:27,210 --> 00:32:35,670
และแล้วสิ่งที่เราทำคือเราก็ตั้งชั่วโมง
องค์ประกอบของอาร์เรย์นี้ชี้ไปที่นี้

597
00:32:35,670 --> 00:32:39,430
>> และแล้วสิ่งที่เราต้องการจะทำที่นี่?

598
00:32:39,430 --> 00:32:43,110
เพิ่มเท่ากับที่แท้จริง
เพราะมันเป็นคำพูด

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
เย็น

601
00:32:48,150 --> 00:32:48,700
ฉันรู้ว่า

602
00:32:48,700 --> 00:32:51,170
พยายามที่จะไม่เป็นที่น่าตื่นเต้นที่สุด

603
00:32:51,170 --> 00:32:54,250
ความน่าเชื่อถือฉันฉันรู้ว่า

604
00:32:54,250 --> 00:32:58,040
>> ดังนั้นสิ่งหนึ่งที่จะตระหนักถึงกับพยายาม
ผมบอกว่าพวกเขากำลังที่มีประสิทธิภาพมาก

605
00:32:58,040 --> 00:33:00,080
ดังนั้นเราจึงได้เห็นพวกเขา
ใช้เวลาถึงตันของพื้นที่

606
00:33:00,080 --> 00:33:01,370
พวกเขากำลังชนิดของความสับสน

607
00:33:01,370 --> 00:33:03,367
ดังนั้นทำไมเราจะเคยใช้เหล่านี้หรือไม่

608
00:33:03,367 --> 00:33:05,450
เราใช้เหล่านี้เพราะพวกเขากำลัง
ที่มีประสิทธิภาพอย่างไม่น่าเชื่อ

609
00:33:05,450 --> 00:33:08,130
>> ดังนั้นถ้าคุณเคยมอง
คำที่คุณเป็นเพียง

610
00:33:08,130 --> 00:33:10,450
กระโดดจากความยาวของคำ

611
00:33:10,450 --> 00:33:15,210
ดังนั้นหากคุณกำลังมองหา
คำที่มีความยาวห้า

612
00:33:15,210 --> 00:33:20,940
คุณเท่านั้นที่เคยจะต้อง
ทำให้ที่มากที่สุดห้าเปรียบเทียบ OK?

613
00:33:20,940 --> 00:33:25,780
จึงทำให้มันเป็นพื้นอย่างต่อเนื่อง

614
00:33:25,780 --> 00:33:29,150
เช่นเดียวกับการแทรกและการค้นหา
จะใช้เวลาอย่างต่อเนื่องโดยทั่วไป

615
00:33:29,150 --> 00:33:33,750
>> ดังนั้นถ้าคุณเคยได้รับ
บางสิ่งบางอย่างในเวลาที่คงที่

616
00:33:33,750 --> 00:33:35,150
ที่ดีที่สุดเท่าที่จะได้รับ

617
00:33:35,150 --> 00:33:37,990
คุณไม่สามารถรับได้ดีกว่า
เวลาคงที่สำหรับสิ่งเหล่านี้

618
00:33:37,990 --> 00:33:43,150
เพื่อให้เป็นหนึ่งใน
pluses ใหญ่ของการพยายาม

619
00:33:43,150 --> 00:33:46,780
>> แต่มันเป็นพื้นที่จำนวนมาก

620
00:33:46,780 --> 00:33:50,380
เพื่อให้คุณชนิดของต้องตัดสินใจ
สิ่งที่สำคัญมากขึ้นเพื่อคุณ

621
00:33:50,380 --> 00:33:54,700
และบนเครื่องคอมพิวเตอร์ของว​​ันนี้
พื้นที่ที่ลองอาจใช้เวลานาน

622
00:33:54,700 --> 00:33:57,740
อาจจะไม่ได้ส่งผลกระทบต่อ
คุณที่มาก แต่อาจจะ

623
00:33:57,740 --> 00:34:01,350
คุณจัดการกับบางสิ่งบางอย่าง
ที่มีสิ่งที่ไกลมากขึ้น

624
00:34:01,350 --> 00:34:02,810
และพยายามที่เพียงไม่เหมาะสม

625
00:34:02,810 --> 00:34:03,000
ใช่?

626
00:34:03,000 --> 00:34:05,610
>> ผู้ชม: รอเพื่อให้คุณมี 26
ตัวอักษรในทุกหนึ่งเดียว?

627
00:34:05,610 --> 00:34:07,440
>> ลำโพง 1: Mmhmm

628
00:34:07,440 --> 00:34:08,570
ใช่คุณมี 26

629
00:34:08,570 --> 00:34:16,984
คุณมีบางเป็นเครื่องหมายคำพูดแล้ว
คุณมี 26 ตัวชี้ในทุกคน

630
00:34:16,984 --> 00:34:17,775
และพวกเขากำลังจุดลิ

631
00:34:17,775 --> 00:34:20,280
>> ผู้ชม: และทุก 26
พวกเขาแต่ละคนมี 26?

632
00:34:20,280 --> 00:34:21,500
>> ลำโพง 1: ใช่

633
00:34:21,500 --> 00:34:27,460
และนั่นเป็นเหตุผลที่คุณสามารถ
เห็นจะขยายอย่างรวดเร็ว

634
00:34:27,460 --> 00:34:28,130
สิทธิ์ทั้งหมด

635
00:34:28,130 --> 00:34:32,524
ดังนั้นเรากำลังจะได้รับเป็นต้นไม้ซึ่ง
ฉันรู้สึกเหมือนจะง่ายขึ้นและอาจจะ

636
00:34:32,524 --> 00:34:36,150
จะเป็นโทษน้อยดี
จากการพยายามมี

637
00:34:36,150 --> 00:34:39,620
เพื่อหวังว่าส่วนใหญ่ของคุณ
ได้เห็นต้นไม้ก่อน

638
00:34:39,620 --> 00:34:41,820
ไม่ชอบสวย
คนที่อยู่ข้างนอกซึ่งผม

639
00:34:41,820 --> 00:34:44,340
ไม่ทราบว่าใคร
ไปนอกบ้านเมื่อเร็ว ๆ นี้

640
00:34:44,340 --> 00:34:49,230
ผมไปเก็บแอปเปิ้ลวันหยุดสุดสัปดาห์นี้
และโอ้ฉันเอ้ยมันก็สวยงาม

641
00:34:49,230 --> 00:34:52,250
ฉันไม่ทราบว่าใบ
สามารถมองที่สวย

642
00:34:52,250 --> 00:34:53,610
>> ดังนั้นนี้เป็นเพียงต้นไม้ใช่มั้ย?

643
00:34:53,610 --> 00:34:56,790
มันเป็นเพียงโหนดบางและมัน
ชี้ไปที่พวงของโหนดอื่น ๆ

644
00:34:56,790 --> 00:34:59,570
ในขณะที่คุณดูที่นี่นี้เป็น
ชนิดของรูปแบบที่เกิดขึ้นเป็นประจำ

645
00:34:59,570 --> 00:35:03,720
โหนดชี้ไปยังโหนดเป็นชนิดของ
สาระสำคัญของโครงสร้างข้อมูลจำนวนมาก

646
00:35:03,720 --> 00:35:06,670
มันก็ขึ้นอยู่กับวิธีการที่เรา
มีพวกเขาชี้ไปที่คนอื่น ๆ

647
00:35:06,670 --> 00:35:08,600
และวิธีที่เราสำรวจ
ผ่านพวกเขาและวิธีที่เรา

648
00:35:08,600 --> 00:35:14,500
แทรกสิ่งที่เป็นตัวกำหนด
ลักษณะที่แตกต่างกันของพวกเขา

649
00:35:14,500 --> 00:35:17,600
>> ดังนั้นเพียงแค่คำศัพท์บางอย่าง
ซึ่งผมเคยใช้มาก่อน

650
00:35:17,600 --> 00:35:20,010
ดังนั้นรากเป็นสิ่งที่อยู่ที่ส่วนบนสุด

651
00:35:20,010 --> 00:35:21,200
มันเป็นเรื่องที่เรามักจะเริ่มต้น

652
00:35:21,200 --> 00:35:23,610
คุณสามารถคิดว่ามันเป็นหัวยัง

653
00:35:23,610 --> 00:35:28,750
แต่สำหรับต้นไม้ที่เรามักจะ
ดูเป็นราก

654
00:35:28,750 --> 00:35:32,820
>> อะไรที่ตรงนี้ด้านล่าง
ที่มาก bottom-- มาก

655
00:35:32,820 --> 00:35:34,500
ใบพิจารณา

656
00:35:34,500 --> 00:35:37,210
ดังนั้นมันจะไปพร้อมกับ
สิ่งที่ต้นไม้ทั้งใช่มั้ย?

657
00:35:37,210 --> 00:35:39,860
ใบที่ขอบของต้นไม้ของคุณ

658
00:35:39,860 --> 00:35:45,820
>> แล้วเรายังมีคู่ของ
คำที่จะพูดคุยเกี่ยวกับโหนดที่เกี่ยวข้อง

659
00:35:45,820 --> 00:35:46,680
ซึ่งกันและกัน

660
00:35:46,680 --> 00:35:49,700
ดังนั้นเราจึงมีผู้ปกครอง
เด็กและพี่น้อง

661
00:35:49,700 --> 00:35:56,260
ดังนั้นในกรณีนี้, 3
แม่ของ 5, 6, และ 7

662
00:35:56,260 --> 00:36:00,370
ดังนั้นผู้ปกครองเป็นสิ่งที่
หนึ่งในขั้นตอนข้างต้นสิ่งที่คุณกำลัง

663
00:36:00,370 --> 00:36:02,940
หมายถึงดังนั้นเพียง
เหมือนต้นไม้ครอบครัว

664
00:36:02,940 --> 00:36:07,090
หวังว่านี้เป็นสิ่งที่เล็ก ๆ น้อย ๆ
บิตใช้งานง่ายกว่าพยายาม

665
00:36:07,090 --> 00:36:10,970
>> พี่น้องที่ใด ๆ ที่มี
พ่อแม่เหมือนกันใช่มั้ย?

666
00:36:10,970 --> 00:36:13,470
พวกเขาอยู่ในระดับเดียวกับที่นี่

667
00:36:13,470 --> 00:36:16,960
แล้วขณะที่ผมกำลัง
บอกว่าเด็กเป็นเพียง

668
00:36:16,960 --> 00:36:22,630
สิ่งที่เป็นขั้นตอนหนึ่งด้านล่าง
โหนดในคำถาม OK?

669
00:36:22,630 --> 00:36:23,470
เย็น

670
00:36:23,470 --> 00:36:25,610
ดังนั้นต้นไม้ไบนารี

671
00:36:25,610 --> 00:36:31,450
ทุกคนสามารถอันตรายเดาที่หนึ่งใน
ลักษณะของต้นไม้ไบนารี?

672
00:36:31,450 --> 00:36:32,770
>> ผู้ชม: แม็กซ์สองใบ

673
00:36:32,770 --> 00:36:33,478
>> ลำโพง 1: ขวา

674
00:36:33,478 --> 00:36:34,640
ดังนั้นสูงสุดของทั้งสองใบ

675
00:36:34,640 --> 00:36:39,730
ดังนั้นในหนึ่งก่อนหน้านี้เรามีหนึ่งในนี้
ที่มีสาม แต่ในต้นไม้ไบนารี

676
00:36:39,730 --> 00:36:45,000
คุณมีสูงสุดของทั้งสอง
เด็กต่อพ่อแม่ใช่มั้ย?

677
00:36:45,000 --> 00:36:46,970
มีอีก
ลักษณะที่น่าสนใจ

678
00:36:46,970 --> 00:36:51,550
ไม่มีใครรู้ว่า?

679
00:36:51,550 --> 00:36:52,620
ต้นไม้ไบนารี

680
00:36:52,620 --> 00:37:00,350
>> ดังนั้นต้นไม้ไบนารีจะมีทุกอย่าง
ที่ยกกำลังหนึ่งนี้ไม่ได้ sorted--

681
00:37:00,350 --> 00:37:05,320
แต่ในต้นไม้ไบนารีเรียงลำดับ
ทุกอย่างที่อยู่ด้านขวา

682
00:37:05,320 --> 00:37:08,530
มากกว่าแม่
และทุกอย่างที่อยู่ทางซ้าย

683
00:37:08,530 --> 00:37:10,035
น้อยกว่าผู้ปกครอง

684
00:37:10,035 --> 00:37:15,690
และที่ได้รับการทดสอบ
คำถามก่อนที่จะดีเพื่อที่จะรู้ว่า

685
00:37:15,690 --> 00:37:19,500
ดังนั้นวิธีที่เรากำหนดนี้,
อีกครั้งเรามีโหนดอื่น

686
00:37:19,500 --> 00:37:21,880
นี้มีลักษณะคล้ายกับสิ่งที่?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
เป็นทวีคูณ

689
00:37:28,836 --> 00:37:29,320
>> แสดงการเชื่อมโยง: ผู้ชม

690
00:37:29,320 --> 00:37:31,100
>> ลำโพง 1: รายการที่เชื่อมโยงคู่ใช่มั้ย?

691
00:37:31,100 --> 00:37:33,690
ดังนั้นหากเราแทนที่นี้
ที่มีก่อนหน้านี้และต่อไป

692
00:37:33,690 --> 00:37:35,670
นี้จะเป็นรายการที่เชื่อมโยงทวีคูณ

693
00:37:35,670 --> 00:37:40,125
แต่ในกรณีนี้เราจริง
ได้ทางซ้ายและขวาและที่มัน

694
00:37:40,125 --> 00:37:41,500
มิฉะนั้นจะตรงเดียวกัน

695
00:37:41,500 --> 00:37:43,374
เรายังคงมีองค์ประกอบ
คุณกำลังมองหา

696
00:37:43,374 --> 00:37:45,988
และคุณก็มีสองตัวชี้
สิ่งที่จะเป็นต่อไป

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
ใช่ต้นไม้ค้นหาแบบไบนารีเพื่อ

699
00:37:51,870 --> 00:37:57,665
ถ้าเราสังเกตเห็นทุกอย่างบน
ที่นี่เป็น than-- มากขึ้น

700
00:37:57,665 --> 00:37:59,850
หรือทุกอย่างทันที
ไปทางขวาที่นี่

701
00:37:59,850 --> 00:38:02,840
มากกว่าทุกอย่าง
ที่นี่มีค่าน้อยกว่า

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> ดังนั้นถ้าเราจะค้นหาผ่านมัน
ควรมีลักษณะที่ใกล้เคียงกับค้นหาแบบไบนารี

704
00:38:14,000 --> 00:38:14,910
ที่นี่ใช่มั้ย?

705
00:38:14,910 --> 00:38:17,640
ยกเว้นแทนที่จะมอง
ที่ครึ่งอาร์เรย์

706
00:38:17,640 --> 00:38:21,720
เราเพียงแค่มองที่ทั้งซ้าย
ด้านข้างหรือด้านขวาของต้นไม้

707
00:38:21,720 --> 00:38:24,850
ดังนั้นจึงได้รับเพียงเล็กน้อยง่ายผมคิดว่า

708
00:38:24,850 --> 00:38:29,300
>> ดังนั้นถ้ารากของคุณเป็นโมฆะ
เห็นได้ชัดว่ามันเป็นเท็จเพียง

709
00:38:29,300 --> 00:38:33,470
และถ้ามันมีเห็นได้ชัดว่ามันเป็นความจริง

710
00:38:33,470 --> 00:38:35,320
ถ้ามันน้อยกว่าเราค้นหาทางด้านซ้าย

711
00:38:35,320 --> 00:38:37,070
ถ้ามันมากขึ้นกว่า
เราค้นหาทางด้านขวา

712
00:38:37,070 --> 00:38:39,890
มันเหมือนกับการค้นหาแบบไบนารี
เพียงแค่โครงสร้างข้อมูลที่แตกต่างกัน

713
00:38:39,890 --> 00:38:40,600
ที่เรากำลังใช้

714
00:38:40,600 --> 00:38:42,790
แทนที่จะอาร์เรย์
มันเป็นเพียงแค่ต้นไม้ไบนารี

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> ตกลงกอง

717
00:38:48,090 --> 00:38:51,550
และยังดูเหมือนว่าเรา
อาจจะมีนิด ๆ หน่อย ๆ ของเวลา

718
00:38:51,550 --> 00:38:54,460
ถ้าเราทำฉันมีความสุขที่จะไป
กว่าใด ๆ นี้อีกครั้ง

719
00:38:54,460 --> 00:38:56,856
ตกลงดังนั้นกอง

720
00:38:56,856 --> 00:39:02,695
ไม่มีใครจำสิ่งที่ stacks--
ลักษณะของสแต็คที่ใด?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> ตกลงดังนั้นส่วนใหญ่ของเราผมคิดว่า
กินในอาหาร halls--

723
00:39:10,400 --> 00:39:13,100
มากที่สุดเท่าที่เราอาจจะไม่ชอบที่จะ

724
00:39:13,100 --> 00:39:16,900
แต่เห็นได้ชัดว่าคุณสามารถคิดของสแต็ค
ตัวอักษรเช่นเดียวกับสแต็คของถาด

725
00:39:16,900 --> 00:39:18,460
หรือสแต็คในสิ่งที่

726
00:39:18,460 --> 00:39:21,820
และสิ่งที่สำคัญ
ตระหนักคือว่ามันเป็น

727
00:39:21,820 --> 00:39:26,850
บางสิ่งบางอย่างลักษณะ
ที่เราเรียกว่าคูณเป็น LIFO

728
00:39:26,850 --> 00:39:28,450
ไม่มีใครรู้ว่าสิ่งที่ยืนอยู่หรือ?

729
00:39:28,450 --> 00:39:29,070
mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> ผู้ชม: สุดท้ายในครั้งแรกออกมา

731
00:39:30,650 --> 00:39:32,250
>> ลำโพง 1: ขวาสุดท้ายในครั้งแรกออกมา

732
00:39:32,250 --> 00:39:36,585
ดังนั้นหากเรารู้ว่าถ้าเรากำลังซ้อนสิ่งที่
ขึ้นสิ่งที่ง่ายที่สุดที่จะคว้า off--

733
00:39:36,585 --> 00:39:39,570
และอาจจะเป็นสิ่งเดียวที่เราสามารถคว้า
ออกหากสแต็คของเราคือการ enough-- ใหญ่

734
00:39:39,570 --> 00:39:40,850
คือการที่องค์ประกอบด้านบน

735
00:39:40,850 --> 00:39:43,460
ดังนั้นสิ่งที่วางอยู่บน
last-- ที่เราเห็นที่นี่

736
00:39:43,460 --> 00:39:46,370
สิ่งที่ได้รับการผลักดัน
ส่วนใหญ่เป็น recently--

737
00:39:46,370 --> 00:39:51,160
จะเป็นครั้งแรก
สิ่งที่เรา pop ปิด, OK?

738
00:39:51,160 --> 00:39:56,324
>> ดังนั้นสิ่งที่เรามีที่นี่
struct typedef อื่น

739
00:39:56,324 --> 00:39:58,740
นี้เป็นจริงเช่นเดียวกับ
ผิดพลาดแน่นอนในโครงสร้างข้อมูล

740
00:39:58,740 --> 00:40:01,650
เพื่อให้มีจำนวนมากโยนที่พวกคุณเป็น

741
00:40:01,650 --> 00:40:02,540
ฉันรู้ว่า

742
00:40:02,540 --> 00:40:04,970
ดังนั้นยัง struct อื่น

743
00:40:04,970 --> 00:40:06,740
ยายสำหรับโครงสร้าง

744
00:40:06,740 --> 00:40:16,660
>> และในกรณีนี้มันเป็นตัวชี้บางอย่าง
ไปยังอาร์เรย์ที่มีความจุบางส่วน

745
00:40:16,660 --> 00:40:20,830
ดังนั้นนี้เป็นสแต็คของเรา
ที่นี่เช่นเดียวกับอาเรย์ที่แท้จริงของเรา

746
00:40:20,830 --> 00:40:22,520
ที่ถือองค์ประกอบของเรา

747
00:40:22,520 --> 00:40:24,850
แล้วที่นี่เรามีขนาดบาง

748
00:40:24,850 --> 00:40:31,170
>> และโดยทั่วไปแล้วคุณต้องการให้
ติดตามวิธีการใหญ่สแต็คของคุณ

749
00:40:31,170 --> 00:40:36,180
เพราะสิ่งที่มันจะช่วยให้
คุณจะทำคือถ้าคุณทราบขนาด

750
00:40:36,180 --> 00:40:39,170
จะช่วยให้คุณที่จะบอกว่า
ตกลงฉันที่ความจุ?

751
00:40:39,170 --> 00:40:40,570
ฉันสามารถเพิ่มอะไรอีกหรือไม่

752
00:40:40,570 --> 00:40:44,650
และก็ยังจะบอกคุณ
ที่ด้านบนสุดของสแต็คของคุณ

753
00:40:44,650 --> 00:40:48,180
เพื่อให้คุณรู้ว่าสิ่งที่คุณ
จริงสามารถนำออกไป

754
00:40:48,180 --> 00:40:51,760
และที่จริงจะ
มีความชัดเจนน้อยมากที่นี่

755
00:40:51,760 --> 00:40:57,350
>> ดังนั้นสำหรับการผลักดันสิ่งหนึ่งถ้าคุณ
เคยที่จะดำเนินการผลักดัน

756
00:40:57,350 --> 00:41:01,330
ขณะที่ผมก็แค่พูดของคุณ
สแต็คที่มีขนาด จำกัด ใช่มั้ย?

757
00:41:01,330 --> 00:41:03,990
อาเรย์ของเรามีความสามารถบางอย่าง

758
00:41:03,990 --> 00:41:04,910
มันเป็นอาเรย์

759
00:41:04,910 --> 00:41:08,930
มันเป็นขนาดคงที่ดังนั้นเราจึงจำเป็นที่จะต้อง
ให้แน่ใจว่าเราไม่ได้วางมากขึ้น

760
00:41:08,930 --> 00:41:11,950
เป็น array ของเรามากกว่าที่เรา
จริงมีที่ว่างสำหรับ

761
00:41:11,950 --> 00:41:16,900
>> ดังนั้นเมื่อคุณกำลังสร้างการผลักดัน
ฟังก์ชั่น, สิ่งแรกที่คุณทำคือการพูดการตกลง

762
00:41:16,900 --> 00:41:18,570
ฉันจะมีพื้นที่ว่างในกองของฉันได้อย่างไร

763
00:41:18,570 --> 00:41:23,330
เพราะถ้าผมไม่ขอโทษ
ฉันไม่สามารถจัดเก็บองค์ประกอบของคุณ

764
00:41:23,330 --> 00:41:28,980
ถ้าผมทำแล้วคุณต้องการเก็บ
ไว้ที่ด้านบนของสแต็คใช่มั้ย?

765
00:41:28,980 --> 00:41:31,325
>> และนี่คือเหตุผลที่เรามี
เพื่อติดตามขนาดของเรา

766
00:41:31,325 --> 00:41:35,290
ถ้าเราไม่ได้ติดตามขนาดของเรา
เราไม่ทราบว่าจะนำมัน

767
00:41:35,290 --> 00:41:39,035
เราไม่ทราบว่าหลายสิ่งหลายอย่าง
อยู่ในอาเรย์ของเราอยู่แล้ว

768
00:41:39,035 --> 00:41:41,410
เช่นเดียวกับที่เห็นได้ชัดมีวิธีการ
ที่บางทีคุณอาจจะทำมัน

769
00:41:41,410 --> 00:41:44,610
คุณสามารถเริ่มต้นทุกอย่างเพื่อ NULL
แล้วตรวจสอบเป็นโมฆะล่าสุด

770
00:41:44,610 --> 00:41:47,950
แต่เป็นสิ่งที่ง่ายมากที่เป็นเพียง
ที่จะบอกว่าตกลงติดตามขนาด

771
00:41:47,950 --> 00:41:51,840
เหมือนฉันรู้ว่าฉันมีธาตุทั้งสี่
ในอาเรย์ของฉันดังนั้นสิ่งต่อไปที่

772
00:41:51,840 --> 00:41:55,930
ที่เราใส่ในเราไม่
ไปเก็บที่ดัชนี 4

773
00:41:55,930 --> 00:42:00,940
แล้วของหลักสูตรนี้หมายความว่า
คุณได้ผลักดันให้ประสบความสำเร็จในบางสิ่งบางอย่าง

774
00:42:00,940 --> 00:42:03,320
บนสแต็คของคุณคุณ
ต้องการเพิ่มขนาด

775
00:42:03,320 --> 00:42:08,880
เพื่อให้คุณรู้ว่าคุณอยู่ที่ไหนดังนั้น
ที่คุณสามารถผลักดันสิ่งที่เพิ่มเติมเกี่ยวกับ

776
00:42:08,880 --> 00:42:12,730
>> ดังนั้นหากเรากำลังพยายามที่จะป๊อปอัพ
บางสิ่งบางอย่างออกจากสแต็

777
00:42:12,730 --> 00:42:16,072
สิ่งที่อาจจะเป็นสิ่งแรก
ที่เราต้องการตรวจสอบ?

778
00:42:16,072 --> 00:42:18,030
คุณกำลังพยายามที่จะใช้
บางสิ่งบางอย่างออกจากสแต็คของคุณ

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
คุณแน่ใจว่ามี
บางสิ่งบางอย่างในกองของคุณ?

781
00:42:24,781 --> 00:42:25,280
เลขที่

782
00:42:25,280 --> 00:42:26,894
ดังนั้นสิ่งที่เราอาจต้องการตรวจสอบ?

783
00:42:26,894 --> 00:42:27,810
>> ผู้ชม: [ไม่ได้ยิน]

784
00:42:27,810 --> 00:42:29,880
ลำโพง 1: ตรวจสอบขนาด?

785
00:42:29,880 --> 00:42:31,840
ขนาด

786
00:42:31,840 --> 00:42:38,520
ดังนั้นเราจึงต้องการที่จะตรวจสอบเพื่อดูว่า
ขนาดของเรามากกว่า 0, OK?

787
00:42:38,520 --> 00:42:44,970
และถ้าเป็นแล้วเราต้องการที่จะลดลง
ขนาดของเราโดยที่ 0 และผลตอบแทนที่

788
00:42:44,970 --> 00:42:45,840
ทำไม?

789
00:42:45,840 --> 00:42:49,950
>> ในครั้งแรกที่พวกเราอยู่
ผลักดันให้เราผลักดันมัน

790
00:42:49,950 --> 00:42:52,460
บนขนาดและขนาดของการอัปเดตแล้ว

791
00:42:52,460 --> 00:42:57,850
ในกรณีนี้เรากำลัง decrementing ขนาด
แล้วพามันออกไปดึงมัน

792
00:42:57,850 --> 00:42:58,952
จากอาร์เรย์ของเรา

793
00:42:58,952 --> 00:42:59,826
ทำไมเราจะทำเช่นนั้น?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
ดังนั้นถ้าฉันมีสิ่งหนึ่งในกองของฉัน
สิ่งที่จะเป็นขนาดของฉันที่จุดนั้น?

796
00:43:11,811 --> 00:43:13,140
1

797
00:43:13,140 --> 00:43:15,180
>> และสถานที่ที่องค์ประกอบที่ 1 จะถูกเก็บไว้?

798
00:43:15,180 --> 00:43:17,621
สิ่งที่ดัชนี?

799
00:43:17,621 --> 00:43:18,120
ผู้ชม: 0

800
00:43:18,120 --> 00:43:19,060
ลำโพง 1: 0

801
00:43:19,060 --> 00:43:22,800
ดังนั้นในกรณีนี้เรา
มักจะต้องทำให้ sure--

802
00:43:22,800 --> 00:43:27,630
แทนที่จะกลับ
ขนาดลบ 1 เพราะเรา

803
00:43:27,630 --> 00:43:31,730
รู้ว่าองค์ประกอบของเราคือการ
จะถูกเก็บไว้ที่ 1 น้อย

804
00:43:31,730 --> 00:43:34,705
สิ่งที่ขนาดของเรานี้
ใช้เวลาเพียงดูแลมัน

805
00:43:34,705 --> 00:43:36,080
มันเป็นวิธีที่สง่างามมากขึ้นเล็กน้อย

806
00:43:36,080 --> 00:43:41,220
และเราก็พร่องของเรา
ขนาดและขนาดจากนั้นกลับมา

807
00:43:41,220 --> 00:43:42,330
mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> ผู้ชม: ผมคิดว่าเพียงแค่ในทั่วไป
ทำไมจะโครงสร้างข้อมูลนี้

809
00:43:45,300 --> 00:43:47,800
เป็นประโยชน์?

810
00:43:47,800 --> 00:43:50,660
>> ลำโพง 1: มันขึ้นอยู่กับบริบทของคุณ

811
00:43:50,660 --> 00:43:57,420
ดังนั้นสำหรับบางส่วนของทฤษฎี
ถ้าคุณกำลังทำงาน with-- ตกลง

812
00:43:57,420 --> 00:44:02,750
ให้ฉันดูว่ามีประโยชน์อย่างใดอย่างหนึ่ง
ที่เป็นประโยชน์ต่อมากกว่าภายนอก

813
00:44:02,750 --> 00:44:05,420
ของลูกค้า

814
00:44:05,420 --> 00:44:15,780
กับกองเวลาใด ๆ ที่คุณต้องการ
เพื่อติดตามสิ่งที่

815
00:44:15,780 --> 00:44:20,456
มีการเพิ่มมากที่สุดเมื่อเร็ว ๆ นี้คือเมื่อ
คุณจะต้องการที่จะใช้สแต็ค

816
00:44:20,456 --> 00:44:24,770
>> และผมก็ไม่สามารถคิดที่ดี
ตัวอย่างเช่นสิทธิที่ตอนนี้

817
00:44:24,770 --> 00:44:29,955
แต่เมื่อใดก็ตามที่ผ่านมามากที่สุด
สิ่งที่สำคัญที่สุดให้กับคุณ

818
00:44:29,955 --> 00:44:31,705
ที่เมื่อสแต็ค
เป็นไปได้ที่มีประโยชน์

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
ฉันพยายามที่จะคิดว่าถ้า
มีหนึ่งที่ดีสำหรับการนี​​้

821
00:44:39,330 --> 00:44:43,720
ถ้าผมคิดว่าเป็นตัวอย่างที่ดีในครั้งต่อไป
20 นาทีแน่นอนผมจะบอกคุณ

822
00:44:43,720 --> 00:44:49,455
>> แต่โดยรวมแล้วถ้ามีอะไร
เหมือนที่ผมกล่าวว่าส่วนใหญ่เมื่อเร็ว ๆ นี้ที่มากที่สุด

823
00:44:49,455 --> 00:44:52,470
เป็นสิ่งที่สำคัญที่สุดที่
ที่กองเข้ามาในเล่น

824
00:44:52,470 --> 00:44:58,860
ในขณะที่รอคิวเป็นชนิดของตรงข้าม

825
00:44:58,860 --> 00:44:59,870
และสุนัขเล็ก ๆ น้อย ๆ

826
00:44:59,870 --> 00:45:00,890
ไม่ดีนี้ใช่มั้ย?

827
00:45:00,890 --> 00:45:03,299
ฉันรู้สึกเหมือนฉันควร
เพียงแค่มีวิดีโอกระต่าย

828
00:45:03,299 --> 00:45:05,090
ขวาตรงกลางของ
ส่วนสำหรับพวกคุณ

829
00:45:05,090 --> 00:45:08,870
เพราะเป็นส่วนที่รุนแรง

830
00:45:08,870 --> 00:45:10,480
>> ดังนั้นคิว

831
00:45:10,480 --> 00:45:12,710
โดยทั่วไปคิวเป็นเหมือนเส้น

832
00:45:12,710 --> 00:45:15,780
พวกคุณฉันแน่ใจว่าใช้ชีวิตประจำวันนี้
เช่นเดียวกับในห้องอาหารของเรา

833
00:45:15,780 --> 00:45:18,160
ดังนั้นเราจึงต้องไปใน
และได้รับถาดของฉัน

834
00:45:18,160 --> 00:45:21,260
แน่ใจว่าคุณต้องรอในบรรทัด
ที่จะรูดหรือได้รับอาหารของคุณ

835
00:45:21,260 --> 00:45:24,650
>> ดังนั้นความแตกต่างที่นี่
ว่าขณะนี้เป็น FIFO

836
00:45:24,650 --> 00:45:30,090
ดังนั้นหาก LIFO เป็นครั้งสุดท้ายในครั้งแรก
ออก FIFO เป็นครั้งแรกในครั้งแรกออกมา

837
00:45:30,090 --> 00:45:33,400
ดังนั้นนี่คือที่สิ่งที่คุณใส่
ในครั้งแรกเป็นสิ่งที่สำคัญที่สุดของคุณ

838
00:45:33,400 --> 00:45:35,540
ดังนั้นถ้าคุณกำลังรอ
ใน line-- คุณสามารถ

839
00:45:35,540 --> 00:45:39,130
คิดว่าคุณไป
ไปรับ iPhone ใหม่

840
00:45:39,130 --> 00:45:42,800
และมันก็เป็นกองที่
คนสุดท้ายในสายได้มันครั้งแรก

841
00:45:42,800 --> 00:45:44,160
คนจะฆ่ากัน

842
00:45:44,160 --> 00:45:49,800
>> ดังนั้น FIFO เราไม่คุ้นเคยมาก
ที่มีอยู่ในโลกแห่งความจริงที่นี่

843
00:45:49,800 --> 00:45:54,930
และมีทุกอย่างจะทำอย่างไรกับความจริง
ชนิดของสูตรทั้งบรรทัดนี้

844
00:45:54,930 --> 00:45:56,900
และโครงสร้างเข้าคิว

845
00:45:56,900 --> 00:46:02,390
ดังนั้นในขณะที่มีกอง
เรามีการผลักดันและป๊อป

846
00:46:02,390 --> 00:46:06,440
กับคิวที่เรามี
และ enqueue dequeue

847
00:46:06,440 --> 00:46:10,910
ดังนั้น enqueue โดยทั่วไปหมายถึง
วางลงบนด้านหลัง

848
00:46:10,910 --> 00:46:13,680
และวิธีการใช้ dequeue
ออกจากด้านหน้า

849
00:46:13,680 --> 00:46:18,680
ดังนั้นโครงสร้างข้อมูลของเรา
นิด ๆ หน่อย ๆ ที่ซับซ้อนมากขึ้น

850
00:46:18,680 --> 00:46:21,060
เรามีสิ่งที่สองที่จะติดตาม

851
00:46:21,060 --> 00:46:25,950
>> ดังนั้นไม่มีหัวนี้
เป็นสิ่งกองใช่มั้ย?

852
00:46:25,950 --> 00:46:27,900
นี้เป็นโครงสร้างเดียวกันเป็นกอง

853
00:46:27,900 --> 00:46:32,480
สิ่งเดียวที่แตกต่างกันขณะนี้คือเรา
มีหัวนี้ซึ่งสิ่งที่คุณคิด

854
00:46:32,480 --> 00:46:34,272
จะไปติดตาม?

855
00:46:34,272 --> 00:46:35,510
>> ผู้ชม: คนแรก

856
00:46:35,510 --> 00:46:38,685
>> ลำโพง 1: ขวา
สิ่งแรกที่เราใส่ใน

857
00:46:38,685 --> 00:46:41,130
หัวของคิวของเรา

858
00:46:41,130 --> 00:46:42,240
ใครก็ตามที่เป็นครั้งแรกในสาย

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
สิทธิทั้งหมดดังนั้นหากเราทำ enqueue

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
อีกครั้งกับใด ๆ ของ
เหล่านี้โครงสร้างข้อมูล

863
00:46:55,920 --> 00:46:59,760
เนื่องจากเรากำลังติดต่อกับอาร์เรย์
เราจำเป็นต้องตรวจสอบว่าเรามีพื้นที่ว่าง

864
00:46:59,760 --> 00:47:03,290
>> นี้เป็นชนิดของเช่นฉันบอก
พวกคุณถ้าคุณเปิดแฟ้ม

865
00:47:03,290 --> 00:47:04,760
คุณจำเป็นต้องตรวจสอบเป็นโมฆะ

866
00:47:04,760 --> 00:47:08,330
กับใด ๆ ของกองเหล่านี้
และคิวที่คุณต้องการ

867
00:47:08,330 --> 00:47:13,420
เพื่อดูว่ามีพื้นที่เพราะเรา
จัดการกับอาร์เรย์ขนาดคงที่

868
00:47:13,420 --> 00:47:16,030
เหมือนที่เราเห็นตรงนี้ 0, 1 ทั้งหมดถึง 5

869
00:47:16,030 --> 00:47:20,690
ดังนั้นสิ่งที่เราทำในกรณีที่มีการตรวจสอบ
เพื่อดูว่าเรายังคงมีพื้นที่ว่าง

870
00:47:20,690 --> 00:47:23,110
คือขนาดของเราน้อยกว่าความจุ?

871
00:47:23,110 --> 00:47:28,480
>> ถ้าเป็นเช่นนั้นเราจำเป็นต้องเก็บไว้ที่
หางและเราปรับปรุงขนาดของเรา

872
00:47:28,480 --> 00:47:30,250
ดังนั้นสิ่งที่หางอาจจะมีในกรณีนี้หรือไม่?

873
00:47:30,250 --> 00:47:32,360
มันไม่ได้เป็นลายลักษณ์อักษรอย่างชัดเจนออกมา

874
00:47:32,360 --> 00:47:33,380
วิธีการที่เราจะเก็บมันได้หรือไม่

875
00:47:33,380 --> 00:47:34,928
สิ่งที่หางจะเป็นอย่างไร

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> จึงขอเดินผ่านตัวอย่างนี้

878
00:47:40,190 --> 00:47:44,590
ดังนั้นนี่คืออาร์เรย์ของขนาด 6 ใช่มั้ย?

879
00:47:44,590 --> 00:47:49,220
และเรามีตอนนี้ขนาดของเราคือ 5

880
00:47:49,220 --> 00:47:55,240
และเมื่อเราใส่ไว้ในก็จะ
ที่จะเข้าไปในดัชนีที่ห้าใช่มั้ย?

881
00:47:55,240 --> 00:47:57,030
ดังนั้นการจัดเก็บที่หาง

882
00:47:57,030 --> 00:48:05,600
>> อีกวิธีหนึ่งที่จะเขียนหางจะเพียง
เป็นอาร์เรย์ของเราได้ที่ดัชนีของขนาดใช่ไหม?

883
00:48:05,600 --> 00:48:07,560
นี้คือขนาด 5

884
00:48:07,560 --> 00:48:11,490
สิ่งต่อไปที่จะไปเป็น 5

885
00:48:11,490 --> 00:48:12,296
เย็น?

886
00:48:12,296 --> 00:48:13,290
ตกลง

887
00:48:13,290 --> 00:48:16,350
จะได้รับเพียงเล็กน้อยที่ซับซ้อนมากขึ้น
เมื่อเราเริ่มล้อเล่นกับหัว

888
00:48:16,350 --> 00:48:17,060
ใช่?

889
00:48:17,060 --> 00:48:20,090
>> ผู้ชม: ไม่ว่าหมายถึงว่าเรา
จะมีการประกาศอาร์เรย์ที่

890
00:48:20,090 --> 00:48:23,880
เป็นห้าองค์ประกอบยาวและ
แล้วเรากำลังเพิ่มไปยังมันได้หรือไม่

891
00:48:23,880 --> 00:48:24,730
>> ลำโพง 1: ฉบับที่

892
00:48:24,730 --> 00:48:27,560
ดังนั้นในกรณีนี้เป็นกอง

893
00:48:27,560 --> 00:48:31,760
นี้จะมีการประกาศ
เป็นอาร์เรย์ที่มีขนาด 6

894
00:48:31,760 --> 00:48:37,120
และในกรณีนี้เรา
เพียงแค่มีพื้นที่หนึ่งที่เหลือ

895
00:48:37,120 --> 00:48:42,720
>> ตกลงดังนั้นสิ่งหนึ่งที่อยู่ในนี้
กรณีถ้าศีรษะของเราอยู่ที่ 0,

896
00:48:42,720 --> 00:48:45,270
จากนั้นเราก็สามารถเพิ่มขนาด

897
00:48:45,270 --> 00:48:51,020
แต่ได้รับเล็กน้อย trickier
เพราะในความเป็นจริงพวกเขา

898
00:48:51,020 --> 00:48:52,840
จะได้ไม่ต้องเลื่อน
สำหรับเรื่องนี้ดังนั้นฉันจะ

899
00:48:52,840 --> 00:48:56,670
การวาดหนึ่งเพราะมันเป็นไม่ได้
ไม่ง่ายอย่างนั้นเมื่อคุณ

900
00:48:56,670 --> 00:48:59,230
เริ่มต้นการกำจัดสิ่ง

901
00:48:59,230 --> 00:49:03,920
ดังนั้นในขณะที่มีกอง
คุณเคยมี

902
00:49:03,920 --> 00:49:08,920
ที่จะต้องกังวลเกี่ยวกับสิ่งที่มีขนาด
เมื่อคุณกำลังเพิ่มบางสิ่งบางอย่างเกี่ยวกับ

903
00:49:08,920 --> 00:49:15,710
กับคิวที่คุณยังต้องทำให้
แน่ใจว่าหัวของคุณจะคิดเป็น

904
00:49:15,710 --> 00:49:20,760
เพราะสิ่งดีๆเกี่ยวกับการรอคิว
คือว่าถ้าคุณไม่ได้อยู่ที่ความจุ

905
00:49:20,760 --> 00:49:23,040
จริงคุณสามารถทำให้มันห่อรอบ

906
00:49:23,040 --> 00:49:28,810
>> ตกลงดังนั้นหนึ่ง thing-- โอ้
นี่คือชอล์กที่น่ากลัว

907
00:49:28,810 --> 00:49:31,815
สิ่งหนึ่งที่จะต้องพิจารณาเป็นกรณี

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
เราเพียงแค่จะทำห้า

910
00:49:37,140 --> 00:49:41,810
ตกลงดังนั้นเรากำลังจะไป
บอกว่าหัวอยู่ที่นี่

911
00:49:41,810 --> 00:49:46,140
นี้เป็น 0, 1, 2, 3, 4

912
00:49:46,140 --> 00:49:54,210
>> หัวที่นั่นและ
กรุณามีสิ่งที่อยู่ในนั้น

913
00:49:54,210 --> 00:49:58,340
และเราต้องการที่จะเพิ่มบางอย่างใช่มั้ย?

914
00:49:58,340 --> 00:50:01,170
ดังนั้นสิ่งที่เราจำเป็นต้อง
ทราบว่าเป็นที่หัวอยู่เสมอ

915
00:50:01,170 --> 00:50:05,620
จะย้ายด้วยวิธีนี้และ
แล้ววนกลับไปรอบ ๆ OK?

916
00:50:05,620 --> 00:50:10,190
>> ดังนั้นคิวนี้มีพื้นที่ใช่มั้ย?

917
00:50:10,190 --> 00:50:13,950
มันมีช่องว่างในจุดเริ่มต้นมาก
ชนิดของตรงข้ามของนี้

918
00:50:13,950 --> 00:50:17,920
ดังนั้นสิ่งที่เราต้องทำคือเรา
ต้องคำนวณหาง

919
00:50:17,920 --> 00:50:20,530
ถ้าคุณรู้ว่าคุณ
หัวยังไม่ได้ย้ายไปหาง

920
00:50:20,530 --> 00:50:24,630
เป็นเพียงอาร์เรย์ที่
ดัชนีของขนาด

921
00:50:24,630 --> 00:50:30,000
>> แต่ในความเป็นจริงถ้าคุณใช้คิว
หัวของคุณอาจจะถูกปรับปรุง

922
00:50:30,000 --> 00:50:33,890
ดังนั้นสิ่งที่คุณต้องทำคือ
จริงคำนวณหาง

923
00:50:33,890 --> 00:50:39,990
ดังนั้นสิ่งที่เราทำคือสูตรนี้
ที่นี่ซึ่งผมจะให้คุณ

924
00:50:39,990 --> 00:50:42,680
คนคิดเกี่ยวกับและ
แล้วเราจะพูดคุยเกี่ยวกับเรื่องนี้

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
ดังนั้นนี่คือความจุ

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> ดังนั้นนี่จะจริง
ให้คุณวิธีที่จะทำ

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
เพราะในกรณีนี้สิ่งที่?

931
00:51:04,330 --> 00:51:09,205
หัวของเราคือวันที่ 1, ขนาดของเราคือ 4

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
ถ้าเรา mod ที่ 5 เราจะได้ 0,
ซึ่งเป็นที่ที่เราควรใส่มัน

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> ดังนั้นแล้วในกรณีต่อไป
ถ้าเราจะทำเช่นนี้

936
00:51:26,080 --> 00:51:33,390
เราพูดว่าตกลงขอ dequeue บางสิ่งบางอย่าง

937
00:51:33,390 --> 00:51:34,390
เรา dequeue นี้

938
00:51:34,390 --> 00:51:37,740
เราจะออกจากองค์ประกอบนี้ใช่มั้ย?

939
00:51:37,740 --> 00:51:47,930
>> และตอนนี้หัวของเราจะชี้ที่นี่
และเราต้องการที่จะเพิ่มในสิ่งอื่น

940
00:51:47,930 --> 00:51:52,470
นี้เป็นพื้น
ด้านหลังของสายของเราใช่มั้ย?

941
00:51:52,470 --> 00:51:55,450
คิวสามารถห่อรอบอาร์เรย์

942
00:51:55,450 --> 00:51:57,310
นั่นคือหนึ่งในความแตกต่างหลัก

943
00:51:57,310 --> 00:51:58,780
กองคุณไม่สามารถทำเช่นนี้

944
00:51:58,780 --> 00:52:01,140
>> กับคิวที่คุณสามารถ
เพราะเรื่องทั้งหมดที่

945
00:52:01,140 --> 00:52:03,940
คือการที่คุณรู้ว่าสิ่งที่
ถูกเพิ่มเข้ามามากที่สุดเมื่อเร็ว ๆ นี้

946
00:52:03,940 --> 00:52:10,650
เนื่องจากทุกอย่างเป็นไปได้ที่จะเพิ่มขึ้นใน
ทิศทางไปทางซ้ายนี้ในกรณีนี้

947
00:52:10,650 --> 00:52:16,480
แล้วห่อรอบคุณสามารถ
ยังคงวางในองค์ประกอบใหม่

948
00:52:16,480 --> 00:52:18,830
ที่ด้านหน้าของอาร์เรย์
เพราะมันไม่ได้จริงๆ

949
00:52:18,830 --> 00:52:20,640
ด้านหน้าของอาเรย์อีกต่อไป

950
00:52:20,640 --> 00:52:26,320
คุณสามารถคิดว่าจุดเริ่มต้นของ
อาร์เรย์เป็นที่หัวของคุณเป็นจริง

951
00:52:26,320 --> 00:52:29,710
>> ดังนั้นสูตรนี้เป็นวิธีการที่
คุณคำนวณหางของคุณ

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
ไม่ว่าจะทำให้ความรู้สึก?

954
00:52:35,610 --> 00:52:36,110
ตกลง

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
ตกลง dequeue แล้ว
พวกคุณมีเวลา 10 นาที

957
00:52:44,040 --> 00:52:48,840
ที่จะถามฉันคำถาม Clarifying ใด ๆ
คุณต้องการเพราะฉันรู้ว่ามันบ้า

958
00:52:48,840 --> 00:52:51,980
>> สิทธิทั้งหมดดังนั้นใน way-- เดียวกัน
ผมไม่ทราบว่าพวกคุณสังเกตเห็น

959
00:52:51,980 --> 00:52:53,450
แต่ลูกค้าเป็นข้อมูลเกี่ยวกับรูปแบบ

960
00:52:53,450 --> 00:52:57,370
สิ่งที่จะสวยมาก
เดียวกันเพียงกับปรับแต่งเล็ก ๆ

961
00:52:57,370 --> 00:52:58,950
สิ่งเดียวกันดังนั้นที่นี่

962
00:52:58,950 --> 00:53:04,040
เราจำเป็นต้องตรวจสอบเพื่อดูว่าเราจริง
มีบางสิ่งที่อยู่ในคิวของเราใช่มั้ย?

963
00:53:04,040 --> 00:53:05,960
บอกว่าโอเคคือขนาดของเรามากกว่า 0?

964
00:53:05,960 --> 00:53:06,730
เย็น

965
00:53:06,730 --> 00:53:10,690
>> ถ้าเราทำแล้วเราย้ายหัวของเราซึ่ง
คือสิ่งที่ฉันเพียงแค่แสดงให้เห็นที่นี่

966
00:53:10,690 --> 00:53:13,870
เราอัปเดตใหญ่ของเราที่จะเป็นอีกหนึ่ง

967
00:53:13,870 --> 00:53:18,390
แล้วเราพร่องของเรา
ขนาดและองค์ประกอบกลับ

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> นอกจากนี้ที่เป็นรูปธรรมมากขึ้น
โค้ดบน study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
และผมขอแนะนำให้ไป
ผ่านมันถ้าคุณมีเวลา

971
00:53:29,440 --> 00:53:30,980
ถึงแม้ว่ามันจะเป็นเพียงนามแฝงรหัส

972
00:53:30,980 --> 00:53:35,980
และถ้าพวกคุณต้องการที่จะพูดคุยผ่านทาง
ที่อยู่กับฉันแบบหนึ่งต่อหนึ่งโปรดแจ้งให้เรา

973
00:53:35,980 --> 00:53:37,500
รู้

974
00:53:37,500 --> 00:53:38,770
ผมยินดีที่จะ

975
00:53:38,770 --> 00:53:42,720
โครงสร้างข้อมูลถ้า
คุณใช้ CS 124, คุณจะ

976
00:53:42,720 --> 00:53:47,830
รู้ว่าโครงสร้างข้อมูลที่ได้รับมาก
สนุกและเป็นเพียงการเริ่มต้น

977
00:53:47,830 --> 00:53:50,350
>> ดังนั้นผมรู้ว่ามันยาก

978
00:53:50,350 --> 00:53:51,300
ก็ OK

979
00:53:51,300 --> 00:53:52,410
เราต่อสู้

980
00:53:52,410 --> 00:53:53,630
ฉันยังคงทำ

981
00:53:53,630 --> 00:53:56,660
จึงไม่ต้องกังวลมากเกินไปเกี่ยวกับเรื่องนี้

982
00:53:56,660 --> 00:54:02,390
>> แต่ที่เป็นพื้นของคุณ
หลักสูตรความผิดพลาดในโครงสร้างข้อมูล

983
00:54:02,390 --> 00:54:03,400
ฉันรู้ว่ามันเป็นจำนวนมาก

984
00:54:03,400 --> 00:54:06,860
มีอะไรที่เรา
อยากจะไปซ้ำอีก?

985
00:54:06,860 --> 00:54:09,400
สิ่งที่เราต้องการที่จะพูดคุยผ่าน?

986
00:54:09,400 --> 00:54:10,060
ใช่?

987
00:54:10,060 --> 00:54:16,525
>> ผู้ชม: ตัวอย่างเช่นนั้นดังนั้น
หางใหม่อยู่ที่ 0 ในช่วงที่?

988
00:54:16,525 --> 00:54:17,150
ลำโพง 1: ใช่

989
00:54:17,150 --> 00:54:18,230
ผู้ชม: ตกลง

990
00:54:18,230 --> 00:54:24,220
ดังนั้นแล้วจะผ่าน
คุณต้องการมี 1 บวก 4 or--

991
00:54:24,220 --> 00:54:27,671
>> ลำโพง 1: เพื่อให้คุณได้รับการบอกว่า
เมื่อเราต้องการที่จะไปทำเช่นนี้อีกครั้งหรือไม่

992
00:54:27,671 --> 00:54:28,296
ผู้ชม: ใช่

993
00:54:28,296 --> 00:54:38,290
ดังนั้นถ้าคุณกำลังคิดแทนดูอยู่ที่ไหน
คุณคำนวณหางจากในที่?

994
00:54:38,290 --> 00:54:44,260
>> ลำโพง 1: ดังนั้นหาง
เป็น in-- ผมเปลี่ยนนี้

995
00:54:44,260 --> 00:54:52,010
ดังนั้นในตัวอย่างนี้ที่นี่นี้คือ
อาร์เรย์ที่เรากำลังมองหาที่ OK?

996
00:54:52,010 --> 00:54:54,670
ดังนั้นเราจึงมีสิ่งที่ 1, 2, 3 และ 4

997
00:54:54,670 --> 00:55:05,850
ดังนั้นเราจึงมีหัวของเราเท่ากับ 1 ที่
จุดนี้และขนาดของเรามีค่าเท่ากับ 4

998
00:55:05,850 --> 00:55:07,050
ที่จุดนี้ใช่มั้ย?

999
00:55:07,050 --> 00:55:08,960
>> พวกคุณทุกคนยอมรับว่าเป็นกรณี?

1000
00:55:08,960 --> 00:55:14,620
ดังนั้นเราจึงทำหัวขนาดบวกซึ่ง
จะช่วยให้เรา 5 แล้วเรา mod 5

1001
00:55:14,620 --> 00:55:20,690
เราได้รับ 0 ซึ่งบอกเราว่าเป็น 0
ที่เป็นหางที่เรามีพื้นที่ของเรา

1002
00:55:20,690 --> 00:55:22,010
>> ผู้ชม: หมวกอะไร?

1003
00:55:22,010 --> 00:55:23,520
>> ลำโพง 1: ความจุ

1004
00:55:23,520 --> 00:55:24,020
ขอโทษ

1005
00:55:24,020 --> 00:55:29,640
เพื่อให้เป็นขนาดของอาร์เรย์ของคุณ

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
ใช่?

1008
00:55:36,047 --> 00:55:39,210
>> ผู้ชม: [ไม่ได้ยิน] ก่อน
เรากลับองค์ประกอบ?

1009
00:55:39,210 --> 00:55:46,270
>> ลำโพง 1: ดังนั้นเราจึงย้าย
มุ่งหน้าหรือกลับขณะนี้?

1010
00:55:46,270 --> 00:55:52,680
ดังนั้นหากเราย้ายหนึ่งพร่องขนาด?

1011
00:55:52,680 --> 00:55:54,150
ยึดมั่นใน

1012
00:55:54,150 --> 00:55:55,770
แน่นอนผมลืมอีก

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
ใจไม่เคย

1015
00:56:01,990 --> 00:56:04,980
ไม่มีสูตรอื่น

1016
00:56:04,980 --> 00:56:09,980
ใช่คุณต้องการที่จะกลับมา
ศีรษะและจากนั้นย้ายกลับ

1017
00:56:09,980 --> 00:56:13,270
>> ผู้ชม: ตกลงเพราะในตอนนี้
จุดหัวอยู่ที่ 0,

1018
00:56:13,270 --> 00:56:18,452
แล้วคุณต้องการที่จะกลับมา
ดัชนี 0 แล้วทำให้หัว 1?

1019
00:56:18,452 --> 00:56:19,870
>> ลำโพง 1: ขวา

1020
00:56:19,870 --> 00:56:22,820
ผมคิดว่ามีอีก
สูตรชนิดเช่นนี้

1021
00:56:22,820 --> 00:56:26,970
ฉันไม่ได้มีไว้ที่ด้านบนหัวของฉันเป็น
ผมไม่ต้องการให้คุณผิดหนึ่ง

1022
00:56:26,970 --> 00:56:35,470
แต่ผมคิดว่ามันเป็นอย่างสมบูรณ์แบบที่ถูกต้อง
พูดตกลงเก็บ element-- นี้สิ่งที่

1023
00:56:35,470 --> 00:56:40,759
องค์ประกอบของหัวเท่าไหร่พร่องของคุณ
ขนาดย้ายหัวของคุณไปและกลับ

1024
00:56:40,759 --> 00:56:41,800
สิ่งที่เป็นองค์ประกอบ

1025
00:56:41,800 --> 00:56:44,760
ที่ถูกต้องสมบูรณ์

1026
00:56:44,760 --> 00:56:45,260
ตกลง

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
ฉันรู้สึกเช่นนี้ไม่ได้
เช่น most-- คุณไม่ได้

1029
00:56:53,560 --> 00:56:55,740
จะเดินออกจากที่นี่
เหมือนใช่ฉันรู้พยายาม

1030
00:56:55,740 --> 00:56:56,880
ผมได้รับมันทั้งหมด

1031
00:56:56,880 --> 00:56:57,670
ไม่เป็นไร

1032
00:56:57,670 --> 00:57:00,200
ฉันสัญญาว่า

1033
00:57:00,200 --> 00:57:05,240
แต่โครงสร้างข้อมูลเป็นสิ่งที่
มันต้องใช้เวลามากในการรับใช้

1034
00:57:05,240 --> 00:57:10,010
อาจเป็นหนึ่งในที่ยากที่สุด
สิ่งที่ผมคิดว่าในหลักสูตร

1035
00:57:10,010 --> 00:57:15,330
>> จึงแน่นอนใช้เวลา
ซ้ำและมอง at-- ฉัน

1036
00:57:15,330 --> 00:57:20,050
ไม่ทราบจริงๆรายการที่เชื่อมโยง
จนกว่าฉันจะไม่มากเกินไปกับพวกเขา

1037
00:57:20,050 --> 00:57:22,550
ในแบบเดียวกับที่ผมทำไม่ได้
เข้าใจจริงๆตัวชี้

1038
00:57:22,550 --> 00:57:27,040
จนกว่าฉันจะได้มีการสอนสอง
ปีและทำ psets ของตัวเองกับมัน

1039
00:57:27,040 --> 00:57:28,990
มันใช้เวลามากในการย้ำและเวลา

1040
00:57:28,990 --> 00:57:32,600
และในที่สุดก็จะชนิดของคลิก

1041
00:57:32,600 --> 00:57:36,320
>> แต่ในขณะเดียวกันถ้าคุณมีชนิด
ของความเข้าใจในระดับสูงของสิ่งที่

1042
00:57:36,320 --> 00:57:39,321
เหล่านี้ข้อดีของพวกเขา
และ cons-- ซึ่งเป็นสิ่งที่

1043
00:57:39,321 --> 00:57:41,820
เราจริงๆมีแนวโน้มที่จะเน้น
โดยเฉพาะอย่างยิ่งในหลักสูตรบทนำ

1044
00:57:41,820 --> 00:57:45,511
เช่นเดียวกับเหตุผลที่เราจะใช้
พยายามกว่าอาร์เรย์?

1045
00:57:45,511 --> 00:57:48,010
เช่นเดียวกับสิ่งที่เป็นบวก
และเชิงลบของแต่ละเหล่านั้นหรือไม่

1046
00:57:48,010 --> 00:57:51,610
>> และทำความเข้าใจเกี่ยวกับการแลกเปลี่ยน
ระหว่างกันของโครงสร้างเหล่านี้

1047
00:57:51,610 --> 00:57:54,910
เป็นสิ่งที่สำคัญมากขึ้นในขณะนี้

1048
00:57:54,910 --> 00:57:58,140
อาจจะมีคนบ้า
คำถามหรือสองที่

1049
00:57:58,140 --> 00:58:03,710
จะขอให้คุณที่จะดำเนินการผลักดันหรือ
ใช้ POP หรือ enqueue และ dequeue

1050
00:58:03,710 --> 00:58:07,340
แต่ส่วนใหญ่ที่มีที่
ความเข้าใจระดับที่สูงขึ้นและอื่น ๆ

1051
00:58:07,340 --> 00:58:09,710
ของเข้าใจง่ายคือ
สำคัญกว่าความจริง

1052
00:58:09,710 --> 00:58:11,250
ความสามารถในการใช้มัน

1053
00:58:11,250 --> 00:58:14,880
>> มันจะน่ากลัวจริงๆถ้าทุกท่าน
สามารถออกไปและไปใช้ลอง

1054
00:58:14,880 --> 00:58:19,720
แต่เราเข้าใจว่ามันไม่จำเป็นต้องเป็น
สิ่งที่เหมาะสมที่สุดในตอนนี้

1055
00:58:19,720 --> 00:58:23,370
แต่คุณสามารถใน pset ของคุณถ้าคุณต้องการ
เพื่อและจากนั้นคุณจะได้รับการปฏิบัติ

1056
00:58:23,370 --> 00:58:27,200
แล้วบางทีคุณอาจจะ
จริงๆเข้าใจมัน

1057
00:58:27,200 --> 00:58:27,940
ใช่?

1058
00:58:27,940 --> 00:58:30,440
>> ผู้ชม: OK เพื่อให้คนที่มี
เราหมายถึงการใช้ใน pset?

1059
00:58:30,440 --> 00:58:31,916
ฉันจะต้องใช้หนึ่งของพวกเขา?

1060
00:58:31,916 --> 00:58:32,540
ลำโพง 1: ใช่

1061
00:58:32,540 --> 00:58:34,199
เพื่อให้คุณมีทางเลือกของคุณ

1062
00:58:34,199 --> 00:58:36,740
ผมคิดว่าในกรณีนี้เราสามารถทำได้
พูดคุยเกี่ยวกับ pset นิด ๆ หน่อย ๆ

1063
00:58:36,740 --> 00:58:40,480
เพราะผมวิ่งผ่านเหล่านี้

1064
00:58:40,480 --> 00:58:47,779
ดังนั้นใน pset ของคุณคุณมีของคุณ
ทางเลือกของการพยายามหรือตารางแฮช

1065
00:58:47,779 --> 00:58:49,570
บางคนจะพยายาม
และใช้ตัวกรองบาน

1066
00:58:49,570 --> 00:58:51,840
แต่ผู้ที่ไม่ได้ในทางเทคนิคที่ถูกต้อง

1067
00:58:51,840 --> 00:58:55,804
เพราะธรรมชาติของความน่าจะเป็นของพวกเขา
พวกเขาให้ผลบวกปลอมบางครั้ง

1068
00:58:55,804 --> 00:58:57,095
พวกเขากำลังดูเย็นลง แต่

1069
00:58:57,095 --> 00:58:59,030
ขอแนะนำให้มอง
ที่พวกเขาอย่างน้อย

1070
00:58:59,030 --> 00:59:03,260
แต่คุณมีทางเลือกของคุณ
ระหว่างตารางแฮชและลอง

1071
00:59:03,260 --> 00:59:06,660
และบอกว่าเป็นไปได้ที่
คุณโหลดในพจนานุกรมของคุณ

1072
00:59:06,660 --> 00:59:09,230
>> และคุณจะต้องเลือก
ฟังก์ชันแฮชของคุณ

1073
00:59:09,230 --> 00:59:13,420
คุณจะต้องเลือกวิธีที่หลาย ๆ
บุ้งกี๋ที่คุณมีและมันจะแตกต่างกันไป

1074
00:59:13,420 --> 00:59:17,440
เช่นถ้าคุณมีถังมากขึ้น
บางทีมันอาจจะจะทำงานได้เร็วขึ้น

1075
00:59:17,440 --> 00:59:22,790
แต่บางทีคุณอาจจะสูญเสีย
พื้นที่จำนวนมากวิธีการที่ว่า

1076
00:59:22,790 --> 00:59:26,320
คุณมีที่จะคิดออก

1077
00:59:26,320 --> 00:59:27,140
mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> ผู้ชม: คุณบอกว่าก่อนหน้านั้น
เราสามารถใช้ฟังก์ชั่นแฮชอื่น ๆ

1079
00:59:29,875 --> 00:59:31,750
ที่เราจะได้ไม่ต้อง
สร้างฟังก์ชันแฮช?

1080
00:59:31,750 --> 00:59:32,666
>> ลำโพง 1: ใช่ขวา

1081
00:59:32,666 --> 00:59:38,150
ดังนั้นตัวอักษรสำหรับฟังก์ชันแฮชของคุณ
เช่น google "ฟังก์ชันแฮช"

1082
00:59:38,150 --> 00:59:40,770
และมองหาบางคนที่เย็น

1083
00:59:40,770 --> 00:59:43,250
คุณยังไม่ได้คาดหวังว่าจะสร้าง
ฟังก์ชั่นแฮชของคุณเอง

1084
00:59:43,250 --> 00:59:46,100
คนใช้จ่ายของพวกเขา
วิทยานิพนธ์ในสิ่งเหล่านี้

1085
00:59:46,100 --> 00:59:50,250
>> จึงไม่ต้องกังวลเกี่ยวกับการสร้างของคุณเอง

1086
00:59:50,250 --> 00:59:53,350
หาหนึ่งออนไลน์จะเริ่มต้นด้วย

1087
00:59:53,350 --> 00:59:56,120
บางส่วนของพวกเขาที่คุณจะต้อง
จัดการนิด ๆ หน่อย ๆ

1088
00:59:56,120 --> 00:59:59,430
เพื่อให้แน่ใจว่าผลตอบแทนประเภทตรง
และ whatnot ดังนั้นในการเริ่มต้น

1089
00:59:59,430 --> 01:00:02,420
ผมจะแนะนำให้ใช้สิ่งที่
ง่ายจริงๆที่อาจจะแค่

1090
01:00:02,420 --> 01:00:04,680
hashes กับตัวอักษรตัวแรก

1091
01:00:04,680 --> 01:00:08,760
และจากนั้นเมื่อคุณมีการทำงานที่
ผสมผสานฟังก์ชันแฮชเย็น

1092
01:00:08,760 --> 01:00:09,260
mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> ผู้ชม: จะพยายามเป็นหรือ
ที่มีประสิทธิภาพ แต่เพียงยาก, like--

1094
01:00:13,020 --> 01:00:15,880
>> ลำโพง 1: จึงพยายามที่ผมคิดว่า
สังหรณ์ใจเป็นเรื่องยากที่จะดำเนินการ

1095
01:00:15,880 --> 01:00:18,310
แต่เป็นไปอย่างรวดเร็วมาก

1096
01:00:18,310 --> 01:00:20,620
แต่ต้องใช้พื้นที่มากขึ้น

1097
01:00:20,620 --> 01:00:25,270
อีกครั้งคุณสามารถเพิ่มประสิทธิภาพของทั้งสองของผู้ที่อยู่ใน
วิธีที่แตกต่างกันและมีวิธี to--

1098
01:00:25,270 --> 01:00:26,770
ผู้ชม: วิธีการที่เราจัดลำดับเกี่ยวกับเรื่องนี้?

1099
01:00:26,770 --> 01:00:27,540
มัน matter--

1100
01:00:27,540 --> 01:00:29,164
>> ลำโพง 1: วิธีปกติดังนั้นคุณอย่างช้า ๆ

1101
01:00:29,164 --> 01:00:31,330
คุณกำลังจะได้รับการจัดลำดับในการออกแบบ

1102
01:00:31,330 --> 01:00:36,020
วิธีใดก็ตามที่คุณทำคุณต้องการ
ให้แน่ใจว่าเป็นที่สง่างามที่สุดเท่าที่จะสามารถ

1103
01:00:36,020 --> 01:00:38,610
และมีประสิทธิภาพที่สุดเท่าที่จะสามารถ

1104
01:00:38,610 --> 01:00:41,950
แต่ถ้าคุณเลือกลองหรือกัญชา
ตารางตราบใดที่การทำงาน

1105
01:00:41,950 --> 01:00:45,350
เรากำลังมีความสุขกับที่

1106
01:00:45,350 --> 01:00:48,370
และถ้าคุณใช้สิ่งที่ hashes
กับตัวอักษรตัวแรกที่ปรับได้

1107
01:00:48,370 --> 01:00:51,410
เช่นอาจจะเหมือนการออกแบบที่ชาญฉลาด

1108
01:00:51,410 --> 01:00:53,410
เรายังถึง
จุดใน semester-- นี้

1109
01:00:53,410 --> 01:00:55,340
ผมไม่ทราบว่าคุณ
พวก noticed-- ถ้าคุณ

1110
01:00:55,340 --> 01:00:58,780
เกรด pset ลดลงเล็กน้อย
เพราะการออกแบบและ whatnot,

1111
01:00:58,780 --> 01:00:59,900
ที่ดีอย่างสมบูรณ์แบบ

1112
01:00:59,900 --> 01:01:02,960
มันได้รับไปยังจุดที่คุณ
โปรแกรมที่ได้รับความซับซ้อนมากขึ้น

1113
01:01:02,960 --> 01:01:04,830
มีสถานที่มากขึ้น
คุณสามารถปรับปรุง

1114
01:01:04,830 --> 01:01:06,370
>> ดังนั้นจึงเป็นเรื่องปกติอย่างสมบูรณ์

1115
01:01:06,370 --> 01:01:08,810
มันไม่ใช่ว่าคุณ
ทำเลวใน pset ของคุณ

1116
01:01:08,810 --> 01:01:11,885
มันเป็นเพียงแค่เราเป็นหนักขึ้นในขณะนี้คุณ

1117
01:01:11,885 --> 01:01:13,732
เพื่อให้ทุกคนรู้สึกว่า

1118
01:01:13,732 --> 01:01:14,940
ฉันเพียงแค่คะแนน psets ทั้งหมดของคุณ

1119
01:01:14,940 --> 01:01:16,490
ฉันรู้ว่าทุกคนจะรู้สึกว่ามัน

1120
01:01:16,490 --> 01:01:19,600
>> ดังนั้นไม่ต้องกังวลเกี่ยวกับการที่

1121
01:01:19,600 --> 01:01:23,580
และถ้าคุณมีคำถามใด ๆ เกี่ยวกับ
psets ก่อนหรือวิธีที่คุณสามารถปรับปรุง

1122
01:01:23,580 --> 01:01:27,760
ฉันพยายามและแสดงความคิดเห็นที่เฉพาะเจาะจง
สถานที่ แต่บางครั้งมันจะสาย

1123
01:01:27,760 --> 01:01:30,840
และฉันได้รับเบื่อ

1124
01:01:30,840 --> 01:01:34,885
มีสิ่งอื่น ๆ
เกี่ยวกับโครงสร้างข้อมูล?

1125
01:01:34,885 --> 01:01:37,510
ผมมั่นใจว่าพวกคุณไม่ได้จริงๆ
ต้องการพูดคุยเกี่ยวกับพวกเขาอีกต่อไป

1126
01:01:37,510 --> 01:01:42,650
แต่ถ้ามีผมมีความสุขที่จะ
ไปกว่าพวกเขาเช่นเดียวเป็นอะไร

1127
01:01:42,650 --> 01:01:45,580
จากการบรรยายที่ผ่านมานี้
สัปดาห์หรือสัปดาห์ที่ผ่านมา

1128
01:01:45,580 --> 01:01:51,580
>> ฉันรู้ว่าเมื่อสัปดาห์ที่แล้วคือการตรวจสอบทั้งหมดเพื่อ
เราอาจจะข้ามการตรวจสอบบางอย่าง

1129
01:01:51,580 --> 01:01:54,190
จากการบรรยาย

1130
01:01:54,190 --> 01:01:58,230
คำถามอื่น ๆ ใด ๆ ที่ฉันสามารถตอบ?

1131
01:01:58,230 --> 01:01:59,350
ตกลงขวาทั้งหมด

1132
01:01:59,350 --> 01:02:02,400
ดีที่พวกคุณได้รับการออก 15 นาทีก่อน

1133
01:02:02,400 --> 01:02:08,370
>> ฉันหวังว่านี้เป็นกึ่งประโยชน์อย่างน้อย
และผมจะเห็นพวกคุณในสัปดาห์หน้า

1134
01:02:08,370 --> 01:02:12,150
หรือพฤหัสบดีเวลาทำการ

1135
01:02:12,150 --> 01:02:15,285
มีขอขนม
สำหรับสัปดาห์ถัดไปก็คือสิ่งที่?

1136
01:02:15,285 --> 01:02:17,459
เพราะฉันลืมขนมวันนี้

1137
01:02:17,459 --> 01:02:19,750
แล้วเราก็นำขนมที่ผ่านมา
สัปดาห์ แต่มันก็เป็นวันโคลัมบัส,

1138
01:02:19,750 --> 01:02:25,400
จึงมีเป็นเหมือนคนที่หก
มีสี่ถุงขนมกับตัวเอง

1139
01:02:25,400 --> 01:02:28,820
ฉันสามารถนำ starbursts
อีกครั้งถ้าคุณชอบ

1140
01:02:28,820 --> 01:02:29,580
starbursts?

1141
01:02:29,580 --> 01:02:32,250
ตกลงเสียงดี

1142
01:02:32,250 --> 01:02:35,050
มีวันที่ดีพวก

1143
01:02:35,050 --> 01:02:39,510