1
00:00:00,000 --> 00:00:03,423
>> [เล่นเพลง]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: ยินดีต้อนรับสู่สัปดาห์ที่ 6 ของส่วน

4
00:00:08,210 --> 00:00:11,620
เราผิดไปจากมาตรฐานของเรา
เวลาส่วนวันอังคาร

5
00:00:11,620 --> 00:00:14,130
ช่วงบ่ายไปเช้าวันอาทิตย์นี้น่ารัก

6
00:00:14,130 --> 00:00:17,330
ขอบคุณสำหรับทุกคนที่
เข้าร่วมฉันในวันนี้ แต่อย่างจริงจัง

7
00:00:17,330 --> 00:00:18,170
รอบของการปรบมือ

8
00:00:18,170 --> 00:00:20,600
>> นั่นเป็นความพยายามที่ใหญ่สวย

9
00:00:20,600 --> 00:00:23,600
ฉันเกือบจะไม่ได้ทำให้มัน
ขึ้นมาในเวลา แต่มันก็ตกลง

10
00:00:23,600 --> 00:00:27,520
ดังนั้นผมจึงรู้ว่าทุกท่าน
ได้ทำเพียงแค่ไปที่การตอบคำถาม

11
00:00:27,520 --> 00:00:30,370
ครั้งแรกของทั้งหมดยินดี
พลิกด้านที่

12
00:00:30,370 --> 00:00:32,917
>> ประการที่สองเราจะพูดคุยเกี่ยวกับเรื่องนี้

13
00:00:32,917 --> 00:00:34,000
เราจะพูดคุยเกี่ยวกับการตอบคำถาม

14
00:00:34,000 --> 00:00:35,700
เราจะพูดคุยเกี่ยวกับวิธีการ
คุณกำลังทำในชั้นเรียน

15
00:00:35,700 --> 00:00:36,550
คุณจะได้รับการปรับ

16
00:00:36,550 --> 00:00:39,080
ฉันมีแบบทดสอบของคุณ
คุณในตอนท้ายของที่นี่

17
00:00:39,080 --> 00:00:42,120
ดังนั้นถ้าพวกคุณต้องการที่จะใช้
ดูที่มันทั้งหมดที่ดี

18
00:00:42,120 --> 00:00:46,590
>> ดังนั้นอย่างรวดเร็วก่อนที่เราจะเริ่มต้นที่
วาระการประชุมในวันนี้มีดังนี้

19
00:00:46,590 --> 00:00:48,430
ที่คุณสามารถดูเรา
ยิงอย่างรวดเร็วโดยทั่วไป

20
00:00:48,430 --> 00:00:52,120
ผ่านทั้งกลุ่มของโครงสร้างข้อมูล
จริงๆจริงๆได้อย่างรวดเร็ว

21
00:00:52,120 --> 00:00:54,380
ดังนั้นเป็นเช่นนี้มันจะไม่เป็น
โต้ตอบสุดในวันนี้

22
00:00:54,380 --> 00:00:59,620
มันก็จะเป็นชนิดของฉันตะโกน
สิ่งที่คุณและถ้าผมสับสนคุณ

23
00:00:59,620 --> 00:01:02,680
ถ้าฉันจะเร็วเกินไปแจ้งให้เราทราบ

24
00:01:02,680 --> 00:01:05,200
พวกเขากำลังเพียงข้อมูลต่างๆ
โครงสร้างและเป็นส่วนหนึ่ง

25
00:01:05,200 --> 00:01:07,070
ของ pset ของคุณสำหรับ
ที่จะเกิดขึ้นในสัปดาห์ที่คุณจะ

26
00:01:07,070 --> 00:01:10,340
ถูกขอให้ดำเนินการอย่างใดอย่างหนึ่งของพวกเขา
บางทีอาจจะเป็นสอง them-- สองของพวกเขา

27
00:01:10,340 --> 00:01:12,319
ใน pset ของคุณ

28
00:01:12,319 --> 00:01:14,610
ตกลงดังนั้นฉันแค่จะไป
เริ่มต้นด้วยการประกาศบางส่วน

29
00:01:14,610 --> 00:01:19,070
เราจะไปกว่ากองและการรอคิวใน
ความลึกกว่าสิ่งที่เราทำก่อนที่จะตอบคำถาม

30
00:01:19,070 --> 00:01:20,990
เราจะไปกว่าการเชื่อมโยง
รายการอีกครั้งอีกครั้งหนึ่ง

31
00:01:20,990 --> 00:01:23,899
เพิ่มเติมในเชิงลึกกว่าสิ่งที่
เรามีก่อนที่จะตอบคำถาม

32
00:01:23,899 --> 00:01:26,440
และจากนั้นเราจะพูดคุยเกี่ยวกับกัญชา
ตารางต้นไม้และพยายามที่

33
00:01:26,440 --> 00:01:28,890
ทั้งหมดที่จำเป็นสำหรับ pset สวยของคุณ

34
00:01:28,890 --> 00:01:32,925
และจากนั้นเราจะไปกว่าบาง
เคล็ดลับที่เป็นประโยชน์สำหรับ pset5

35
00:01:32,925 --> 00:01:37,360
>> ตกลงดังนั้นตอบคำถาม 0

36
00:01:37,360 --> 00:01:41,090
เฉลี่ยเป็น 58%

37
00:01:41,090 --> 00:01:45,370
มันเป็นที่ต่ำมากและเพื่อให้คุณผู้ชายทั้งหมด
ไม่ได้เป็นอย่างดีมากตาม

38
00:01:45,370 --> 00:01:46,510
กับที่

39
00:01:46,510 --> 00:01:49,970
>> สวยมากกฎของหัวแม่มือคือถ้าคุณ
ภายในเบี่ยงเบนมาตรฐานของค่าเฉลี่ย

40
00:01:49,970 --> 00:01:52,990
โดยเฉพาะอย่างยิ่งนับตั้งแต่ที่เราอยู่ในน้อย
ส่วนอุ่นหนาฝาคั่งคุณดีทั้งหมด

41
00:01:52,990 --> 00:01:54,120
คุณกำลังติดตาม

42
00:01:54,120 --> 00:01:55,190
ชีวิตเป็นสิ่งที่ดี.

43
00:01:55,190 --> 00:01:58,952
>> ฉันรู้ว่ามันน่ากลัวที่จะคิดว่า
ฉันได้เหมือน 40% ในการตอบคำถามนี้

44
00:01:58,952 --> 00:02:00,160
ฉันจะล้มเหลวในชั้นนี้

45
00:02:00,160 --> 00:02:02,243
ผมสัญญาว่าคุณคุณไม่ได้
จะล้มเหลวในชั้นเรียน

46
00:02:02,243 --> 00:02:03,680
คุณกำลังดีทั้งหมด

47
00:02:03,680 --> 00:02:06,850
>> สำหรับบรรดาผู้ที่ได้มากกว่า
ค่าเฉลี่ยที่น่าประทับใจที่น่าประทับใจ

48
00:02:06,850 --> 00:02:08,780
เหมือนอย่างจริงจังทำได้ดี

49
00:02:08,780 --> 00:02:09,689
ฉันมีพวกเขากับฉัน

50
00:02:09,689 --> 00:02:11,730
รู้สึกอิสระที่จะมารับพวกเขา
ในตอนท้ายของส่วน

51
00:02:11,730 --> 00:02:14,520
แจ้งให้เราทราบหากคุณมี
ประเด็นคำถามกับพวกเขา

52
00:02:14,520 --> 00:02:17,204
ถ้าเราเพิ่มขึ้นคะแนนของคุณ
ที่ไม่ถูกต้องแจ้งให้เราทราบ

53
00:02:17,204 --> 00:02:21,240
>> ตกลงดังนั้น pset5 นี้เป็นจริง
สัปดาห์ที่แปลกสำหรับเยลในความรู้สึก

54
00:02:21,240 --> 00:02:24,240
ที่ pset ของเราเป็นเพราะ
วันพุธตอนเที่ยงรวมทั้ง

55
00:02:24,240 --> 00:02:27,317
วันปลายดังนั้นจึงเป็นเรื่องจริง
เนื่องจากในทางทฤษฎีวันอังคารเวลาเที่ยง

56
00:02:27,317 --> 00:02:29,150
อาจเป็นหนึ่งในไม่เสร็จ
ในวันอังคารเวลาเที่ยง

57
00:02:29,150 --> 00:02:30,830
ที่ดีทั้งหมด

58
00:02:30,830 --> 00:02:33,700
เรากำลังจะมีเวลาทำงาน
คืนนี้เช่นเดียวกับคืนวันจันทร์

59
00:02:33,700 --> 00:02:36,810
และทุกส่วนในสัปดาห์นี้จะ
จริงจะกลายเป็นการประชุมเชิงปฏิบัติการ

60
00:02:36,810 --> 00:02:38,800
ดังนั้นรู้สึกฟรีที่จะปรากฏใน
ส่วนที่คุณต้องการใด ๆ

61
00:02:38,800 --> 00:02:42,810
และพวกเขาจะเป็นชนิดของมินิ pset
การประชุมเชิงปฏิบัติการเพื่อขอความช่วยเหลือเกี่ยวกับการที่

62
00:02:42,810 --> 00:02:45,620
ดังนั้นเป็นเช่นนี้เป็นเพียงบางส่วน
ที่เรากำลังเรียนการสอนวัสดุ

63
00:02:45,620 --> 00:02:49,220
ทุกส่วนอื่น ๆ จะเน้น
เฉพาะในการช่วยเหลือสำหรับ pset

64
00:02:49,220 --> 00:02:50,146
ใช่?

65
00:02:50,146 --> 00:02:52,000
>> ผู้ชม: อยู่ที่ไหนเวลาทำงาน?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: เวลาทำการ
tonight-- โอ้คำถามที่ดี

67
00:02:56,120 --> 00:03:00,580
ผมคิดว่าคืนนี้เวลาราชการ
อยู่ในน้านหรือคอมมอนส์

68
00:03:00,580 --> 00:03:02,984
หากคุณตรวจสอบออนไลน์ CS50
และคุณจะไปเวลาทำการ

69
00:03:02,984 --> 00:03:05,650
ควรจะมีการกำหนดเวลาที่
จะบอกคุณที่ทั้งหมดของพวกเขา

70
00:03:05,650 --> 00:03:07,954
>> ฉันรู้ว่าทั้งคืน
หรือวันพรุ่งนี้เป็นนกเป็ดน้ำ

71
00:03:07,954 --> 00:03:10,120
และฉันคิดว่าเราอาจจะมี
คอมมอนส์สำหรับคืนอื่น ๆ

72
00:03:10,120 --> 00:03:11,020
ฉันไม่แน่ใจ.

73
00:03:11,020 --> 00:03:11,700
คำถามที่ดี.

74
00:03:11,700 --> 00:03:14,430
ตรวจสอบ CS50

75
00:03:14,430 --> 00:03:18,780
>> เย็นคำถามใด ๆ เกี่ยวกับการ
ระยะเวลาในการต่อไปเช่นวันที่สาม?

76
00:03:18,780 --> 00:03:21,690
ผมสัญญาว่าคุณคนชอบเดวิด
กล่าวมานี้เป็นด้านบนของเนินเขา

77
00:03:21,690 --> 00:03:23,050
พวกคุณเกือบจะมี

78
00:03:23,050 --> 00:03:24,644
เพียงสามวัน

79
00:03:24,644 --> 00:03:26,310
รับมีและจากนั้นเราทุกคนจะลงมา

80
00:03:26,310 --> 00:03:28,114
เราจะมีดีแบ่ง CS-ฟรี

81
00:03:28,114 --> 00:03:28,780
เราจะกลับมา

82
00:03:28,780 --> 00:03:30,779
เราจะดำน้ำในเว็บ
การเขียนโปรแกรมและพัฒนา

83
00:03:30,779 --> 00:03:35,150
สิ่งที่มีความสนุกสนานมากเมื่อเทียบ
บางส่วนของ psets อื่น ๆ

84
00:03:35,150 --> 00:03:37,974
และมันจะเย็นและ
เราจะมีความสนุกสนานมากมาย

85
00:03:37,974 --> 00:03:38,890
เราจะมีขนมอื่น ๆ อีกมากมาย

86
00:03:38,890 --> 00:03:39,730
ขออภัยสำหรับลูกอม

87
00:03:39,730 --> 00:03:40,945
ฉันลืมลูกอม

88
00:03:40,945 --> 00:03:43,310
มันเป็นตอนเช้าที่หยาบกร้าน

89
00:03:43,310 --> 00:03:46,340
ดังนั้นพวกคุณเกือบจะมี
และผมภูมิใจของพวกคุณ

90
00:03:46,340 --> 00:03:49,570
>> ตกลงดังนั้นกอง

91
00:03:49,570 --> 00:03:53,331
ที่รักคำถามเกี่ยวกับแจ็ค
และเสื้อผ้าของเขาในการตอบคำถามหรือไม่

92
00:03:53,331 --> 00:03:53,830
ไม่มีใคร?

93
00:03:53,830 --> 00:03:56,500
โอเคไม่เป็นไร.

94
00:03:56,500 --> 00:04:00,200
>> เพื่อเป็นหลักในขณะที่คุณสามารถ
ภาพแจ็ค, ผู้ชายคนนี้ที่นี่

95
00:04:00,200 --> 00:04:03,350
รักที่จะใช้เสื้อผ้า
ออกจากด้านบนของสแต็ค,

96
00:04:03,350 --> 00:04:05,750
และเขาทำให้มันกลับไปยัง
กองหลังจากที่เขาทำ

97
00:04:05,750 --> 00:04:07,600
ดังนั้นในทางนี้เขาไม่เคย
ดูเหมือนว่าจะได้รับ

98
00:04:07,600 --> 00:04:10,090
ไปที่ด้านล่างของ
สแต็คในเสื้อผ้าของเขา

99
00:04:10,090 --> 00:04:12,600
ดังนั้นนี้ชนิดของการอธิบาย
โครงสร้างข้อมูลพื้นฐาน

100
00:04:12,600 --> 00:04:16,610
ของวิธีการที่สแต็คจะดำเนินการ

101
00:04:16,610 --> 00:04:20,060
>> เป็นหลักคิด
สแต็คเป็นกองของวัตถุใด ๆ

102
00:04:20,060 --> 00:04:24,900
ที่คุณใส่ลงในสิ่งที่ด้านบนและ
แล้วคุณป๊อปพวกเขาออกมาจากด้านบน

103
00:04:24,900 --> 00:04:28,600
ดังนั้น LIFO เป็นตัวย่อที่เราชอบ
เพื่อ use-- ในล่าสุด, First Out

104
00:04:28,600 --> 00:04:32,480
และเพื่อให้มีอายุการใช้งานในด้านบนของ
สแต็คเป็นคนแรกที่ออกมา

105
00:04:32,480 --> 00:04:34,260
และเพื่อให้คำสองคำ
เราชอบที่จะเชื่อมโยง

106
00:04:34,260 --> 00:04:36,190
กับการที่จะเรียกว่าการผลักดันและป๊อป

107
00:04:36,190 --> 00:04:39,790
เมื่อคุณผลักดันบางสิ่งบางอย่างบน
สแต็คและคุณป๊อปมันกลับขึ้น

108
00:04:39,790 --> 00:04:43,422
>> และเพื่อให้ฉันเดานี้เป็นชนิดของ
แนวคิดที่เป็นนามธรรมสำหรับบรรดาของคุณ

109
00:04:43,422 --> 00:04:45,630
ที่ต้องการเห็นเช่น
การปฏิบัติจริงของเรื่องนี้

110
00:04:45,630 --> 00:04:46,740
ในโลกแห่งความจริง

111
00:04:46,740 --> 00:04:50,170
วิธีการหลายท่านได้เขียนเรียงความ
อาจจะเหมือนชั่วโมงก่อนที่จะถูกกำหนด

112
00:04:50,170 --> 00:04:54,510
และคุณตั้งใจลบขนาดใหญ่
ก้อนของมันเหมือนตั้งใจ?

113
00:04:54,510 --> 00:04:58,560
และแล้วสิ่งที่ควบคุมทำ
เราใช้ที่จะนำมันกลับมา?

114
00:04:58,560 --> 00:05:00,030
ควบคุม-Z ใช่?

115
00:05:00,030 --> 00:05:03,640
ควบคุม-Z ดังนั้นจำนวนครั้ง
ที่ควบคุม-Z ได้บันทึกชีวิตของฉัน

116
00:05:03,640 --> 00:05:08,820
มีการบันทึกไว้ตูดของฉันทุกครั้ง
ที่ดำเนินการผ่านกอง

117
00:05:08,820 --> 00:05:13,020
>> เป็นหลักข้อมูลทั้งหมด
ที่อยู่ในเอกสาร Word ของคุณ

118
00:05:13,020 --> 00:05:15,080
จะได้รับการผลักดันและโผล่ที่จะ

119
00:05:15,080 --> 00:05:19,460
และเพื่อให้เป็นหลักเมื่อใดก็ตามที่คุณ
ลบสิ่งที่คุณป๊อปมันสำรอง

120
00:05:19,460 --> 00:05:22,820
และแล้วถ้าคุณต้องการมันกลับมาที่คุณ
ผลักดันมันซึ่งเป็นสิ่งที่ควบคุมไม่-C

121
00:05:22,820 --> 00:05:26,770
และฟังก์ชั่นโลกแห่งความจริงดังนั้น
ของวิธีการที่โครงสร้างข้อมูลง่าย

122
00:05:26,770 --> 00:05:28,690
สามารถช่วยให้มีชีวิตประจำวันของคุณ

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> ดังนั้น struct เป็นวิธีการที่
เราจริงสร้างกอง

125
00:05:40,150 --> 00:05:44,720
เราพิมพ์กำหนด struct แล้ว
เราเรียกว่าสแต็คที่ด้านล่าง

126
00:05:44,720 --> 00:05:47,440
และภายในกอง
เรามีสองพารามิเตอร์

127
00:05:47,440 --> 00:05:51,580
ว่าเราเป็นหลักสามารถจัดการ
เพื่อให้เรามีสายดาวถ่านความจุ

128
00:05:51,580 --> 00:05:55,150
>> สิ่งที่จะทำ
คือการสร้างอาร์เรย์

129
00:05:55,150 --> 00:05:58,835
ที่เราสามารถจัดเก็บสิ่งที่คุณต้องการ
ซึ่งเราสามารถตรวจสอบความสามารถของตน

130
00:05:58,835 --> 00:06:01,990
ความจุเป็นเพียงจำนวนเงินสูงสุด
รายการที่เราสามารถใส่ลงในอาร์เรย์นี้

131
00:06:01,990 --> 00:06:05,660
ขนาด int เป็นเคาน์เตอร์ที่ช่วยให้
การติดตามของจำนวนรายการที่มีอยู่ในปัจจุบัน

132
00:06:05,660 --> 00:06:07,850
ในกอง

133
00:06:07,850 --> 00:06:11,860
ดังนั้นแล้วเราสามารถติดตาม, A,
ทั้งสองวิธีใหญ่สแต็คที่เกิดขึ้นจริงคือ

134
00:06:11,860 --> 00:06:14,850
และ B, วิธีการมากของสแต็คที่
เราเต็มไปเพราะเราไม่ต้องการ

135
00:06:14,850 --> 00:06:18,800
ล้นมากกว่าสิ่งที่เป็นความสามารถของเรา

136
00:06:18,800 --> 00:06:24,340
>> ดังนั้นสำหรับตัวอย่างเช่นนี้น่ารัก
คำถามที่อยู่ในการตอบคำถามของคุณ

137
00:06:24,340 --> 00:06:28,160
เป็นหลักทำอย่างไรเราจะผลักดัน
ไปยังด้านบนของสแต็คที่

138
00:06:28,160 --> 00:06:28,830
สวยเรียบง่าย

139
00:06:28,830 --> 00:06:30,621
ถ้าคุณมองไปที่มัน
เราจะเดินผ่านทางนี้

140
00:06:30,621 --> 00:06:32,640
หาก [ไม่ได้ยิน] size--
จำได้ว่าเมื่อใดก็ตามที่คุณ

141
00:06:32,640 --> 00:06:35,300
ต้องการเข้าถึงใด ๆ
พารามิเตอร์ภายใน struct ที่

142
00:06:35,300 --> 00:06:40,320
คุณทำชื่อของ struct.parameter ที่

143
00:06:40,320 --> 00:06:42,720
>> ในกรณีนี้คือ
ชื่อของสแต็คของเรา

144
00:06:42,720 --> 00:06:46,230
เราต้องการที่จะเข้าถึงขนาด
ของมันดังนั้นเราจึง s.size

145
00:06:46,230 --> 00:06:50,280
ดังนั้นตราบใดที่ขนาดไม่ได้
เท่ากับกำลังการผลิตหรือเป็นเวลานาน

146
00:06:50,280 --> 00:06:52,940
เป็นมันน้อยกว่ากำลังการผลิต
อาจจะทำงานที่นี่

147
00:06:52,940 --> 00:06:57,180
>> คุณต้องการที่จะเข้าถึงภายใน
ของสแต็คของคุณเพื่อให้ s.strings,

148
00:06:57,180 --> 00:07:00,790
และคุณกำลังจะไปใส่ที่หมายเลขใหม่
ที่คุณต้องการแทรกลงในมี

149
00:07:00,790 --> 00:07:05,030
ขอเพียงบอกว่าเราจะต้องการ
ใส่ int n ลงบนกอง

150
00:07:05,030 --> 00:07:08,905
เราสามารถทำ s.strings,
วงเล็บ s.size เท่ากับ n

151
00:07:08,905 --> 00:07:11,030
เพราะขนาดเป็นที่ที่เรา
ขณะนี้อยู่ในกอง

152
00:07:11,030 --> 00:07:14,590
ถ้าเรากำลังจะผลักดัน
มันเกี่ยวกับเราเข้าถึงเพียง

153
00:07:14,590 --> 00:07:17,370
ทุกที่ขนาดคือ
อิ่มปัจจุบันของกอง

154
00:07:17,370 --> 00:07:21,729
และเราจะผลักดัน int n ลงบนมัน

155
00:07:21,729 --> 00:07:24,770
แล้วเราต้องการที่จะให้แน่ใจว่า
เรายังมีการเพิ่มขนาดของ n,

156
00:07:24,770 --> 00:07:27,436
เพื่อให้เราสามารถติดตามเราได้
เพิ่มสิ่งที่พิเศษที่จะสแต็ค

157
00:07:27,436 --> 00:07:29,660
ตอนนี้เรามีขนาดมากขึ้น

158
00:07:29,660 --> 00:07:33,196
ที่นี่ไม่ทำให้รู้สึกถึง
ทุกคนมีเหตุผลว่ามันทำงานอย่างไร

159
00:07:33,196 --> 00:07:34,160
มันเป็นชนิดของอย่างรวดเร็ว

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
ผู้ชม: คุณสามารถไปมากกว่า
s.stringss.strings [การ s.size] อีกครั้งหรือไม่

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: แน่นอนดังนั้นสิ่งที่ไม่
ขณะ s.size ให้เรา?

163
00:07:45,808 --> 00:07:47,440
ผู้ชม: มันเป็นขนาดปัจจุบัน

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: แน่นอนดังนั้น
ดัชนีปัจจุบันว่าขนาดของเราอยู่ที่

165
00:07:50,890 --> 00:07:57,780
และเพื่อให้เราต้องการที่จะนำเลขที่ใหม่
ที่เราต้องการแทรกลงใน s.size

166
00:07:57,780 --> 00:07:58,760
ที่ทำให้รู้สึก?

167
00:07:58,760 --> 00:08:01,110
เพราะ s.strings ทั้งหมดที่
คือเป็นชื่อของอาร์เรย์

168
00:08:01,110 --> 00:08:03,510
ทั้งหมดก็คือค​​ือการเข้าถึง
อาร์เรย์ภายในโครงสร้างของเรา

169
00:08:03,510 --> 00:08:06,030
และดังนั้นหากเราต้องการที่จะ
n วางลงในดัชนีที่

170
00:08:06,030 --> 00:08:09,651
เราก็สามารถเข้าถึงได้
โดยใช้วงเล็บ s.size

171
00:08:09,651 --> 00:08:10,150
เย็น.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> สิ่งที่ถูกต้อง, ป๊อป, ฉัน pseudocode มันออกมา
สำหรับคุณผู้ชาย แต่แนวคิดที่คล้ายกัน

174
00:08:18,916 --> 00:08:19,790
ที่ทำให้รู้สึก?

175
00:08:19,790 --> 00:08:22,310
ถ้ามีขนาดที่ใหญ่กว่า
กว่าศูนย์แล้วคุณ

176
00:08:22,310 --> 00:08:25,350
รู้ว่าคุณต้องการที่จะใช้บางสิ่งบางอย่าง
ออกมาเพราะถ้าขนาดไม่ได้

177
00:08:25,350 --> 00:08:27,620
มากกว่าศูนย์แล้วคุณ
มีอะไรในกอง

178
00:08:27,620 --> 00:08:29,840
>> ดังนั้นคุณเพียงต้องการที่จะดำเนินการ
รหัสนี้ก็สามารถ

179
00:08:29,840 --> 00:08:32,320
ปรากฏว่ามีบางสิ่งบางอย่างที่จะปรากฏ

180
00:08:32,320 --> 00:08:35,830
ดังนั้นถ้ามีขนาดที่ใหญ่กว่า
มากกว่า 0 เราลบขนาด

181
00:08:35,830 --> 00:08:40,020
เราพร่องขนาดแล้วกลับ
สิ่งที่อยู่ภายในของมันเพราะ

182
00:08:40,020 --> 00:08:42,710
โดย popping เราต้องการที่จะ
การเข้าถึงสิ่งที่ถูกเก็บไว้

183
00:08:42,710 --> 00:08:45,694
ในดัชนีของด้านบนของสแต็คที่

184
00:08:45,694 --> 00:08:46,610
ทุกสิ่งที่ทำให้รู้สึก?

185
00:08:46,610 --> 00:08:49,693
ถ้าผมทำพวกคุณเขียนออกนี้
คนที่คุณจะสามารถที่จะเขียนมันออกมา?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
ตกลงพวกคุณสามารถเล่นรอบกับมัน

188
00:08:53,570 --> 00:08:55,252
ไม่ต้องกังวลถ้าคุณไม่ได้รับมัน

189
00:08:55,252 --> 00:08:57,460
เราไม่ได้มีเวลาที่จะรหัส
มันออกมาในวันนี้เพราะเราได้

190
00:08:57,460 --> 00:08:59,959
มีจำนวนมากของโครงสร้างเหล่านี้
ที่จะผ่านไป แต่เป็นหลัก

191
00:08:59,959 --> 00:09:02,214
pseudocode มากคล้ายกันมากที่จะผลักดัน

192
00:09:02,214 --> 00:09:03,380
เพียงแค่ทำตามตรรกะ

193
00:09:03,380 --> 00:09:06,092
ให้แน่ใจว่าคุณกำลังเข้าถึงทั้งหมด
คุณสมบัติของ struct คุณอย่างถูกต้อง

194
00:09:06,092 --> 00:09:06,574
ใช่?

195
00:09:06,574 --> 00:09:09,282
>> ผู้ชม: Will ภาพนิ่งเหล่านี้และ
เรื่องทั้งหมดนี้จะมีขึ้นในวันนี้-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: เสมอครับ

197
00:09:11,586 --> 00:09:13,710
ฉันจะพยายามที่จะนำ
ขึ้นเช่นนี้หนึ่งชั่วโมงหลังจากที่

198
00:09:13,710 --> 00:09:16,626
ฉันจะส่งอีเมลเดวิดเดวิดจะพยายามที่จะ
ใส่มันขึ้นเหมือนชั่วโมงหลังจากนี้

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> ตกลงดังนั้นแล้วเราย้ายเข้าอื่น ๆ
โครงสร้างข้อมูลที่น่ารักที่เรียกว่าคิว

201
00:09:25,470 --> 00:09:30,140
ในฐานะที่พวกคุณสามารถดูที่นี่เป็น
คิวอังกฤษในหมู่พวกเรา

202
00:09:30,140 --> 00:09:32,010
ทั้งหมดมันเป็นเป็นเส้น

203
00:09:32,010 --> 00:09:34,680
ตรงกันข้ามกับดังนั้นสิ่งที่
คุณคิดว่ากองคือ

204
00:09:34,680 --> 00:09:37,750
คิวเป็นสิ่งที่
เหตุผลที่คุณคิดว่ามันเป็น

205
00:09:37,750 --> 00:09:41,914
มันจัดขึ้นตามกฎของ FIFO ที่
ซึ่งเป็นครั้งแรกในครั้งแรกออก

206
00:09:41,914 --> 00:09:43,705
หากคุณเป็นคนแรก
หนึ่งในสายคุณ

207
00:09:43,705 --> 00:09:46,230
คนแรกที่
ออกมาจากเส้น

208
00:09:46,230 --> 00:09:49,680
>> ดังนั้นสิ่งที่เราชอบที่จะเรียกสิ่งนี้
เป็น dequeueing และ enqueueing

209
00:09:49,680 --> 00:09:52,380
ถ้าเราต้องการที่จะเพิ่มบางสิ่งบางอย่าง
คิวของเราเรา enqueue

210
00:09:52,380 --> 00:09:55,690
ถ้าเราต้องการที่จะ dequeue หรือใช้
บางสิ่งบางอย่างออกไปเรา dequeue

211
00:09:55,690 --> 00:10:03,350
>> รู้สึกเดียวกันเพื่อให้เราชนิดของ
การสร้างองค์ประกอบขนาดคงที่เรา

212
00:10:03,350 --> 00:10:06,500
สามารถจัดเก็บบางอย่าง
สิ่ง แต่เรายังสามารถ

213
00:10:06,500 --> 00:10:10,100
เปลี่ยนที่เรากำลังวาง
พารามิเตอร์ภายในของพวกเขา

214
00:10:10,100 --> 00:10:13,140
ขึ้นอยู่กับชนิดของ
ฟังก์ชั่นที่เราต้องการ

215
00:10:13,140 --> 00:10:16,700
ดังนั้นกองเราต้องการที่ผ่านมา
อย่างใดอย่างหนึ่ง, N จะเป็นครั้งแรกหนึ่ง

216
00:10:16,700 --> 00:10:19,800
เป็นคิวที่เราต้องการสิ่งแรก
ในการที่จะเป็นสิ่งแรกที่ออกมา

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> ดังนั้น struct ประเภท
กำหนดในขณะที่คุณสามารถดู

219
00:10:26,710 --> 00:10:29,470
มันเป็นความแตกต่างกันเล็กน้อย
จากสิ่งที่เป็นกอง

220
00:10:29,470 --> 00:10:33,120
เพราะไม่เพียง แต่เราจะต้องเก็บ
ติดตามในขณะนี้ขนาดที่เป็น

221
00:10:33,120 --> 00:10:37,420
เรายังต้องการที่จะติดตามของศีรษะ
เช่นเดียวกับที่เรามีอยู่ในปัจจุบัน

222
00:10:37,420 --> 00:10:39,580
ดังนั้นผมจึงคิดว่ามันง่ายขึ้น
ถ้าผมวาดขึ้นนี้

223
00:10:39,580 --> 00:10:53,270
ดังนั้นลองจินตนาการว่าเรามีคิว
จึงขอบอกว่าหัวเป็นขวาที่นี่

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
หัวของเส้นสมมติ
เพียงแค่บอกว่าขณะนี้มี

226
00:10:58,310 --> 00:11:01,809
และเราต้องการที่จะแทรก
บางสิ่งบางอย่างเข้าไปในคิว

227
00:11:01,809 --> 00:11:04,350
ฉันจะเรียกขนาดเป็นหลัก
เป็นสิ่งเดียวกับหาง

228
00:11:04,350 --> 00:11:06,314
ในตอนท้ายของทุกคิวของคุณคือ

229
00:11:06,314 --> 00:11:07,730
ขอเพียงบอกว่าขนาดถูกต้องที่นี่

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> ดังนั้นวิธีที่จะหนึ่ง feasibly
บางสิ่งบางอย่างใส่ลงในคิวหรือไม่?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
เราทำอะไรดัชนีต้องการวาง
ที่เราต้องการแทรกลงใน

234
00:11:24,130 --> 00:11:29,320
ถ้านี่คือจุดเริ่มต้นของคุณ
คิวและนี่คือจุดสิ้นสุดของมัน

235
00:11:29,320 --> 00:11:31,860
หรือขนาดของมันที่เราทำ
ต้องการที่จะเพิ่มวัตถุต่อไปหรือไม่

236
00:11:31,860 --> 00:11:32,920
>> ผู้ชม: [ไม่ได้ยิน]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: แน่นอนคุณต้องการเพิ่ม
มันขึ้นอยู่กับที่คุณเขียน

238
00:11:35,920 --> 00:11:37,840
ทั้งสองนี้จะว่างเปล่าหรือว่าจะว่างเปล่า

239
00:11:37,840 --> 00:11:42,630
ดังนั้นคุณจึงต้องการที่จะเพิ่มก็อาจ
ที่นี่เพราะถ้าขนาด is--

240
00:11:42,630 --> 00:11:50,540
ถ้าเหล่านี้ทั้งหมดเต็มรูปแบบที่คุณต้องการ
เพื่อเพิ่มที่นี่ใช่มั้ย?

241
00:11:50,540 --> 00:11:57,150
>> และเพื่อให้เป็นในขณะที่มาก
ที่เรียบง่ายไม่มากถูกต้องเสมอ

242
00:11:57,150 --> 00:12:00,690
เพราะความแตกต่างหลัก
ระหว่างคิวและกอง

243
00:12:00,690 --> 00:12:04,350
คือคิวสามารถ
จริงจัดการ

244
00:12:04,350 --> 00:12:06,980
เพื่อให้การเปลี่ยนแปลงหัว
ขึ้นอยู่กับที่คุณต้องการ

245
00:12:06,980 --> 00:12:08,650
จุดเริ่มต้นของคิวของคุณที่จะเริ่มต้น

246
00:12:08,650 --> 00:12:11,900
และเป็นผลให้หางของคุณ
ยังจะมีการเปลี่ยนแปลง

247
00:12:11,900 --> 00:12:14,770
และเพื่อให้ดูที่
รหัสนี้ได้ในขณะนี้

248
00:12:14,770 --> 00:12:18,620
ในฐานะที่พวกคุณยังได้ขอให้
เขียนออกมาในการตอบคำถามที่กำหนดไว้เป็นลำดับ

249
00:12:18,620 --> 00:12:22,580
บางทีเราจะพูดคุยผ่านทำไม
คำตอบก็คือสิ่งที่มันเป็น

250
00:12:22,580 --> 00:12:26,790
>> ฉันไม่สามารถค่อนข้างพอดีกับสายนี้ในหนึ่ง
แต่เป็นหลักชิ้นส่วนของรหัสนี้

251
00:12:26,790 --> 00:12:29,030
ควรจะอยู่ในหนึ่งบรรทัด

252
00:12:29,030 --> 00:12:30,140
การใช้จ่ายเช่น 30 วินาที

253
00:12:30,140 --> 00:12:33,000
ลองดูและดูว่าทำไม
นี้เป็นวิธีที่ว่ามันเป็น

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> มาก struct คล้ายกันมากมาก
โครงสร้างเช่นเดียวกับก่อนหน้านี้

256
00:12:55,420 --> 00:12:58,090
สแต็คยกเว้นบางที
หนึ่งบรรทัดของรหัส

257
00:12:58,090 --> 00:13:01,190
และที่หนึ่งบรรทัดของรหัส
กำหนดฟังก์ชันการทำงาน

258
00:13:01,190 --> 00:13:03,900
และเป็นเรื่องที่แตกต่าง
คิวจากกอง

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> ทุกคนต้องการที่จะใช้แทง
ที่อธิบายว่าทำไมคุณได้

261
00:13:22,010 --> 00:13:24,980
ได้รับนี้สิ่งที่ซับซ้อนในที่นี่?

262
00:13:24,980 --> 00:13:27,845
เราจะเห็นการกลับมาของเรา
โมดูลัสเพื่อนที่ยอดเยี่ยม

263
00:13:27,845 --> 00:13:31,020
ในฐานะที่พวกคุณเร็ว ๆ นี้จะมา
ที่จะรับรู้ในการเขียนโปรแกรม

264
00:13:31,020 --> 00:13:34,910
เกือบตลอดเวลาที่คุณต้องการอะไร
การห่อรอบอะไร

265
00:13:34,910 --> 00:13:36,850
โมดูลัสที่เกิดขึ้นจะเป็นวิธีการที่จะทำมัน

266
00:13:36,850 --> 00:13:40,510
ดังนั้นการรู้ว่าไม่มีใครต้องการ
ที่จะพยายามอธิบายบรรทัดของรหัสที่?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
ใช่คำตอบทั้งหมดที่มี
ได้รับการยอมรับและยินดีต้อนรับ

269
00:13:47,507 --> 00:13:48,840
ผู้ชม: คุณพูดกับผมหรือเปล่า

270
00:13:48,840 --> 00:13:49,506
ANDI เป็ง: ใช่

271
00:13:49,506 --> 00:13:56,200
ผู้ชม: โอ้ไม่เสียใจ

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK จึงขอ
เดินผ่านรห​​ัสนี้

273
00:14:00,250 --> 00:14:03,642
ดังนั้นเมื่อคุณกำลังพยายามที่จะ
เพิ่มสิ่งบนคิว

274
00:14:03,642 --> 00:14:08,510
ในกรณีที่น่ารักที่หัวเกิดขึ้น
จะอยู่ตรงนี้มันเป็นเรื่องง่ายมากสำหรับเรา

275
00:14:08,510 --> 00:14:10,960
เพียงแค่ไปที่สิ้นสุด
ใส่บางสิ่งบางอย่างใช่มั้ย?

276
00:14:10,960 --> 00:14:14,690
แต่จุดรวมของคิวเป็น
ที่หัวสามารถจริงแบบไดนามิก

277
00:14:14,690 --> 00:14:17,280
เปลี่ยนแปลงขึ้นอยู่กับที่เรา
ต้องการเริ่มต้นของคิวของเราที่จะเป็น

278
00:14:17,280 --> 00:14:19,880
และเป็นเช่นหาง
ยังจะมีการเปลี่ยนแปลง

279
00:14:19,880 --> 00:14:31,100
>> ดังนั้นคิดว่านี้ไม่ได้
คิว แต่นี้เป็นคิว

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
สมมติว่าหัวเป็นขวาที่นี่

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
สมมติว่าคิวเรามองเช่นนี้

284
00:14:56,980 --> 00:15:00,190
ถ้าเราต้องการที่จะเปลี่ยนที่
จุดเริ่มต้นของบรรทัดคือ

285
00:15:00,190 --> 00:15:03,400
สมมติว่าเราขยับหัว
ด้วยวิธีนี้และขนาดที่นี่

286
00:15:03,400 --> 00:15:07,100
>> ตอนนี้เราต้องการที่จะเพิ่มสิ่งที่
คิวนี้ แต่เป็นพวกคุณสามารถดู

287
00:15:07,100 --> 00:15:11,150
มันไม่ง่ายที่จะเพียงแค่
เพิ่มสิ่งที่อยู่หลังขนาด

288
00:15:11,150 --> 00:15:13,630
แล้วเพราะเราทำงานออกจาก
ขอบเขตของอาร์เรย์ที่แท้จริงของเรา

289
00:15:13,630 --> 00:15:16,190
ที่เราต้องการจริงๆเพิ่มอยู่ที่นี่

290
00:15:16,190 --> 00:15:18,610
ที่ความงามของคิว
คือว่าให้เรามองเห็นมัน

291
00:15:18,610 --> 00:15:22,380
ดูเหมือนว่าสายไปเช่นนี้
แต่เมื่อเก็บไว้ในโครงสร้างข้อมูล

292
00:15:22,380 --> 00:15:29,370
พวกเขาให้เป็นเหมือนวงจร

293
00:15:29,370 --> 00:15:32,360
ชนิดของมันล้อมรอบ
ไปข้างหน้าด้วยวิธีเดียวกัน

294
00:15:32,360 --> 00:15:34,780
ว่าสายยังสามารถตัด
รอบขึ้นอยู่กับทุกท่าน

295
00:15:34,780 --> 00:15:36,279
ต้องการที่จะเริ่มต้นของบรรทัดที่จะเป็น

296
00:15:36,279 --> 00:15:38,630
ดังนั้นถ้าเราใช้เวลา
มองลงมาที่นี่ขอ

297
00:15:38,630 --> 00:15:40,880
บอกว่าเราต้องการที่จะสร้าง
ฟังก์ชั่นที่เรียกว่า Enqueue

298
00:15:40,880 --> 00:15:43,980
เราต้องการที่จะเพิ่ม int n ลงในคิว

299
00:15:43,980 --> 00:15:49,250
ถ้าเรา q.size q-- จะเรียกได้ว่าข้อมูลของเรา
structure-- ถ้า queue.size ของเราไม่ได้

300
00:15:49,250 --> 00:15:52,520
เท่ากับความจุหรือถ้า
มันน้อยกว่ากำลังการผลิต

301
00:15:52,520 --> 00:15:55,120
q.strings เป็นอาร์เรย์ที่อยู่ในคิวของเรา

302
00:15:55,120 --> 00:15:58,380
เรากำลังจะไปตั้ง
ที่เท่ากับ q.heads,

303
00:15:58,380 --> 00:16:02,730
ซึ่งเป็นสิทธิที่นี่บวก q.size
โมดูลัสโดยกำลังการผลิตที่

304
00:16:02,730 --> 00:16:04,290
ห่อเรากลับมาที่นี่

305
00:16:04,290 --> 00:16:08,040
>> ดังนั้นในตัวอย่างนี้ดัชนี
ของหัว 1 ใช่มั้ย?

306
00:16:08,040 --> 00:16:11,480
ดัชนีของขนาดเป็น 0, 1, 2, 3, 4

307
00:16:11,480 --> 00:16:19,500
ดังนั้นเราจึงสามารถทำ 1 บวก 4 โมดูลัส
โดยความสามารถของเราซึ่งเป็น 5

308
00:16:19,500 --> 00:16:20,920
อะไรที่ทำให้เรา?

309
00:16:20,920 --> 00:16:23,270
ดัชนีคืออะไรที่
ออกมาจากนี้หรือไม่?

310
00:16:23,270 --> 00:16:24,080
>> ผู้ชม: 0

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0 ซึ่ง
ที่จะเกิดขึ้นที่นี่

312
00:16:27,870 --> 00:16:30,640
และเพื่อให้เราต้องการที่จะสามารถ
เพื่อแทรกลงในที่นี่

313
00:16:30,640 --> 00:16:34,730
และเพื่อให้สมการนี​​้ชนิดที่นี่
เพียงทำงานร่วมกับตัวเลขใด ๆ

314
00:16:34,730 --> 00:16:36,750
ขึ้นอยู่กับที่ของคุณ
หัวและขนาดของคุณ

315
00:16:36,750 --> 00:16:38,541
ถ้าคุณรู้ว่าสิ่งเหล่านั้น
สิ่งที่คุณรู้

316
00:16:38,541 --> 00:16:43,170
ตรงที่คุณต้องการแทรก
สิ่งที่อยู่หลังคิวของคุณ

317
00:16:43,170 --> 00:16:44,640
ไม่ว่าทำให้ความรู้สึกที่ทุกคน?

318
00:16:44,640 --> 00:16:48,560
>> ฉันรู้ว่าชนิดของสมอง
ทีเซอร์โดยเฉพาะอย่างยิ่งตั้งแต่นี้

319
00:16:48,560 --> 00:16:50,512
เดินเข้ามาในผลพวงของการตอบคำถามของคุณ

320
00:16:50,512 --> 00:16:52,220
หวังว่าทุกคน แต่
สามารถเข้าใจ

321
00:16:52,220 --> 00:16:57,800
ทำไมการแก้ปัญหานี้หรือนี้
ฟังก์ชั่นเป็นวิธีที่ว่ามันเป็น

322
00:16:57,800 --> 00:16:59,840
ทุกคนบิตไม่มีความชัดเจนในที่?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
ตกลง.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> ดังนั้นตอนนี้ถ้าคุณ
อยากจะ dequeue นี้

327
00:17:09,970 --> 00:17:15,240
คือที่หัวของเราจะขยับ
เพราะถ้าเราจะ dequeue,

328
00:17:15,240 --> 00:17:17,030
เราไม่ได้จะปิดท้ายของคิว

329
00:17:17,030 --> 00:17:19,130
เราต้องการที่จะออกหัวใช่มั้ย?

330
00:17:19,130 --> 00:17:24,260
ดังนั้นเป็นผลให้หัวที่เกิดการเปลี่ยนแปลง
และนั่นคือเหตุผลที่เมื่อคุณ enqueue,

331
00:17:24,260 --> 00:17:26,800
คุณได้มีการติดตาม
ที่หัวของคุณและขนาดของคุณ

332
00:17:26,800 --> 00:17:29,450
จะต้องสามารถที่จะใส่
เข้าไปในตำแหน่งที่ถูกต้อง

333
00:17:29,450 --> 00:17:32,740
>> ดังนั้นเมื่อคุณ dequeue,
ฉันยัง pseudocode มันออกมา

334
00:17:32,740 --> 00:17:35,480
รู้สึกอิสระที่จะถ้าคุณต้องการ
พยายามที่การเข้ารหัสนี้ออก

335
00:17:35,480 --> 00:17:36,980
คุณต้องการที่จะย้ายหัวใช่มั้ย?

336
00:17:36,980 --> 00:17:39,320
ถ้าผมอยากจะ dequeue ผม
จะย้ายหัวมากกว่า

337
00:17:39,320 --> 00:17:40,800
นี้จะเป็นหัว

338
00:17:40,800 --> 00:17:45,617
>> และขนาดของเราในปัจจุบันจะ
ลบเพราะเราไม่ได้

339
00:17:45,617 --> 00:17:46,950
มีสี่องค์ประกอบในอาร์เรย์

340
00:17:46,950 --> 00:17:51,370
เรามีเพียงสามแล้วที่เราต้องการ
ที่จะกลับมาอะไรก็ตามที่เก็บไว้ภายใน

341
00:17:51,370 --> 00:17:56,260
ของหัวเพราะเราต้องการที่จะใช้เวลานี้
ค่าออกเพื่อให้คล้ายกับสแต็ค

342
00:17:56,260 --> 00:17:58,010
เพียงแค่คุณถ่าย
จากสถานที่ที่แตกต่างกัน

343
00:17:58,010 --> 00:18:01,770
และคุณจะต้องกำหนดตัวชี้ของคุณ
ไปยังสถานที่ที่แตกต่างกันเป็นผล

344
00:18:01,770 --> 00:18:03,890
เหตุผลที่ทุกคนทำตาม?

345
00:18:03,890 --> 00:18:05,690
ที่ดี

346
00:18:05,690 --> 00:18:10,156
>> ตกลงดังนั้นเรากำลังจะพูดคุยเล็กน้อย
เพิ่มเติมในเชิงลึกเกี่ยวกับรายการที่เชื่อมโยง

347
00:18:10,156 --> 00:18:13,280
เพราะพวกเขาจะมากที่มีคุณค่ามาก
สำหรับคุณในหลักสูตรของสัปดาห์นี้

348
00:18:13,280 --> 00:18:14,964
psets

349
00:18:14,964 --> 00:18:17,130
รายการที่เชื่อมโยงเป็นพวกคุณ
สามารถจำสิ่งที่พวกเขามี

350
00:18:17,130 --> 00:18:22,570
เป็นโหนดที่มีโหนดของบางอย่าง
ค่านิยมของทั้งมูลค่าและตัวชี้

351
00:18:22,570 --> 00:18:26,290
ที่มีการเชื่อมโยงกัน
โดยคำแนะนำเหล่านั้น

352
00:18:26,290 --> 00:18:29,880
และเพื่อให้โครงสร้างเกี่ยวกับวิธีการ
เราสร้างโหนดที่นี่เป็นที่ที่เรา

353
00:18:29,880 --> 00:18:33,569
มี n int ซึ่งเป็นสิ่งที่
มูลค่าในร้านค้าหรือสตริง n

354
00:18:33,569 --> 00:18:35,610
หรือสิ่งที่คุณต้องการ
เรียกว่าที่ n ดาวถ่าน

355
00:18:35,610 --> 00:18:41,482
ดาวโหนดโครงสร้างซึ่งเป็นตัวชี้
ที่คุณต้องการที่จะมีในแต่ละโหนด

356
00:18:41,482 --> 00:18:43,690
คุณกำลังจะมีที่
จุดที่ชี้ไปทางต่อไป

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
คุณจะมีหัว
ของรายการที่เชื่อมโยงว่า

359
00:18:50,040 --> 00:18:53,140
จะชี้ไปที่ส่วนที่เหลือของ
ค่าอื่น ๆ และอื่น ๆ

360
00:18:53,140 --> 00:18:55,290
จนในที่สุดคุณถึงจุดสิ้นสุด

361
00:18:55,290 --> 00:18:58,040
และโหนดสุดท้ายนี้เป็นเพียง
จะได้มีตัวชี้

362
00:18:58,040 --> 00:18:59,952
มันจะชี้ไปที่
โมฆะและที่ว่าเมื่อ

363
00:18:59,952 --> 00:19:01,910
คุณรู้ว่าคุณเคยตี
ในตอนท้ายของรายการที่เชื่อมโยงของคุณ

364
00:19:01,910 --> 00:19:04,076
คือเมื่อตัวชี้สุดท้ายของคุณ
ไม่ได้ชี้ไปที่ใด

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> ดังนั้นเรากำลังจะไปอีกเล็กน้อยใน
เชิงลึกเกี่ยวกับวิธีการหนึ่งที่จะเป็นไปได้

367
00:19:10,990 --> 00:19:12,400
ค้นหารายการที่เชื่อมโยง

368
00:19:12,400 --> 00:19:15,460
โปรดจำไว้ว่าสิ่งที่เป็นบางส่วนของ
ข้อเสียของรายการที่เชื่อมโยง

369
00:19:15,460 --> 00:19:19,340
โองการอาร์เรย์เกี่ยวกับการค้นหา

370
00:19:19,340 --> 00:19:22,565
อาร์เรย์ที่คุณสามารถค้นหา binary แต่
ทำไมคุณไม่สามารถทำในรายการที่เชื่อมโยงหรือไม่?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> ผู้ชม: เพ​​ราะพวกเขากำลังทั้งหมดที่เชื่อมต่อ
แต่คุณไม่ทราบว่าค่อนข้าง

373
00:19:30,320 --> 00:19:31,330
[ไม่ได้ยิน]

374
00:19:31,330 --> 00:19:34,600
>> ANDI เป็ง: ใช่ว่าเพื่อให้จำ
ที่ความฉลาดของอาร์เรย์

375
00:19:34,600 --> 00:19:37,190
เป็นความจริงที่ว่าเรามี
หน่วยความจำเข้าถึงโดยสุ่มที่

376
00:19:37,190 --> 00:19:41,580
ถ้าผมต้องการค่าจากดัชนี
หกผมก็อาจจะบอกว่าดัชนีหก

377
00:19:41,580 --> 00:19:42,407
ให้ฉันค่าที่

378
00:19:42,407 --> 00:19:45,240
และนั่นเป็นเพราะอาร์เรย์จะถูกจัดเรียง
ในพื้นที่ที่อยู่ติดกันของหน่วยความจำ

379
00:19:45,240 --> 00:19:48,020
ในสถานที่แห่งหนึ่งในขณะที่
ชนิดของรายการที่เชื่อมโยง

380
00:19:48,020 --> 00:19:52,820
มีการสุ่มสลับรอบ ๆ
และวิธีเดียวที่คุณสามารถหาหนึ่ง

381
00:19:52,820 --> 00:19:56,890
ผ่านตัวชี้ที่จะบอกคุณ
ที่อยู่ของโหนดที่ต่อไปคือ

382
00:19:56,890 --> 00:20:00,290
>> และเพื่อให้เป็นผลให้วิธีเดียวที่
การค้นหาผ่านรายการที่เชื่อมโยง

383
00:20:00,290 --> 00:20:01,560
คือการค้นหาเชิงเส้น

384
00:20:01,560 --> 00:20:05,890
เพราะผมไม่ทราบว่าที่
ค่าที่ 12 ในรายการที่เชื่อมโยงเป็น

385
00:20:05,890 --> 00:20:08,780
ฉันมีการสำรวจครบถ้วน
ของรายการที่เชื่อมโยงอย่างใดอย่างหนึ่ง

386
00:20:08,780 --> 00:20:12,450
โดยหนึ่งตั้งแต่หัวโหนดแรก
ไปยังโหนดที่สองไปยังโหนดที่สาม

387
00:20:12,450 --> 00:20:17,690
ตลอดทางลงไปจนในที่สุดผมก็จะได้รับ
ไปยังที่ที่โหนดฉันกำลังมองหาที่

388
00:20:17,690 --> 00:20:22,110
ดังนั้นในแง่นี้การค้นหา
ในรายการที่เชื่อมโยงอยู่เสมอ n

389
00:20:22,110 --> 00:20:23,040
มันเสมอ n

390
00:20:23,040 --> 00:20:25,690
มันมักจะอยู่ในเส้นเวลา

391
00:20:25,690 --> 00:20:28,470
>> และเพื่อให้รหัสที่
เราดำเนินการนี​​้และนี้

392
00:20:28,470 --> 00:20:32,620
เป็นบิตใหม่สำหรับคุณผู้ชายตั้งแต่คุณ
คนไม่ได้พูดคุยมากเกี่ยวกับหรือเคย

393
00:20:32,620 --> 00:20:35,000
เห็นคำแนะนำในวิธีการ
ค้นหาผ่านตัวชี้

394
00:20:35,000 --> 00:20:37,670
ดังนั้นเราจะเดินผ่าน
นี้มากช้ามาก

395
00:20:37,670 --> 00:20:40,200
ดังนั้นการค้นหาบูลขวา
ลองจินตนาการที่เราต้องการ

396
00:20:40,200 --> 00:20:42,820
ในการสร้างฟังก์ชั่นที่เรียกว่า
ค้นหาที่ผลตอบแทนจริง

397
00:20:42,820 --> 00:20:46,820
ถ้าคุณพบว่าค่าภายในที่เชื่อมโยง
รายการและจะกลับเท็จอย่างอื่น

398
00:20:46,820 --> 00:20:50,030
รายการโหนดดาว
ขณะนี้เพียงตัวชี้

399
00:20:50,030 --> 00:20:52,960
ไปที่รายการแรกในรายการที่เชื่อมโยง

400
00:20:52,960 --> 00:20:56,700
n int คือค่าที่คุณเป็น
ค้นหาในรายการว่า

401
00:20:56,700 --> 00:20:58,770
>> ดังนั้นตัวชี้ดาวโหนดเท่ากับรายการ

402
00:20:58,770 --> 00:21:00,970
นั่นหมายความว่าเรากำลังตั้ง
และการสร้างตัวชี้

403
00:21:00,970 --> 00:21:03,592
ที่โหนดแรกภายในของรายการ

404
00:21:03,592 --> 00:21:04,300
ทุกคนกับผมได้ไหม

405
00:21:04,300 --> 00:21:06,530
ดังนั้นถ้าเราจะไป
กลับมาที่นี่ผมจะต้อง

406
00:21:06,530 --> 00:21:13,850
เริ่มต้นที่ตัวชี้ชี้ไปที่
หัวของรายการสิ่งที่เป็น

407
00:21:13,850 --> 00:21:18,600
>> และจากนั้นเมื่อคุณได้รับลงที่นี่
ในขณะที่ตัวชี้ null ไม่เท่ากัน

408
00:21:18,600 --> 00:21:22,160
เพื่อให้เป็นห่วงในการที่เราเป็น
ไปได้ต่อมาภายใน

409
00:21:22,160 --> 00:21:25,940
ส่วนที่เหลือของรายการของเราเพราะสิ่งที่
ที่เกิดขึ้นเมื่อตัวชี้เท่ากับ null?

410
00:21:25,940 --> 00:21:27,550
เรารู้ว่าเรา have--

411
00:21:27,550 --> 00:21:28,450
>> ผู้ชม: [ไม่ได้ยิน]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: แน่นอนดังนั้นเราจึงรู้ว่า
เราได้มาถึงจุดสิ้นสุดของรายการใช่มั้ย?

413
00:21:31,491 --> 00:21:34,470
ถ้าคุณกลับไปที่นี่แต่ละโหนด
ควรจะชี้ไปยังโหนดอื่น

414
00:21:34,470 --> 00:21:36,550
และอื่น ๆ และอื่น ๆ
จนกว่าคุณจะตีในที่สุด

415
00:21:36,550 --> 00:21:41,589
หางของรายการที่เชื่อมโยงของคุณ
ซึ่งมีตัวชี้ว่าเพียงแค่

416
00:21:41,589 --> 00:21:43,130
ไม่ได้ชี้ทุกที่อื่นที่ไม่ใช่ไม่มี

417
00:21:43,130 --> 00:21:47,510
และเพื่อให้คุณรู้ว่าโดยทั่วไป
รายการของคุณยังคงมีขึ้น

418
00:21:47,510 --> 00:21:50,900
จนกว่าตัวชี้ไม่เท่ากับ
null เพราะเมื่อมันเท่ากับโมฆะ

419
00:21:50,900 --> 00:21:53,310
คุณรู้ไหมว่าไม่มีสิ่งอื่น ๆ อีก

420
00:21:53,310 --> 00:21:56,930
>> เพื่อให้เป็นวงที่เรากำลัง
จะมีการค้นหาที่เกิดขึ้นจริง

421
00:21:56,930 --> 00:22:01,690
และถ้า pointer-- คุณเห็น
ชนิดของฟังก์ชั่นที่มีลูกศร?

422
00:22:01,690 --> 00:22:06,930
ดังนั้นถ้าจุดที่ชี้ไปยัง n ถ้า
ชี้ที่ n เท่ากับเท่ากับ n,

423
00:22:06,930 --> 00:22:09,180
เพื่อให้หมายความว่าหาก
ตัวชี้ว่าคุณ

424
00:22:09,180 --> 00:22:13,420
หาที่สิ้นสุดของแต่ละคน
โหนดเป็นจริงเท่ากับค่า

425
00:22:13,420 --> 00:22:15,990
คุณกำลังมองหาแล้ว
คุณต้องการที่จะกลับจริง

426
00:22:15,990 --> 00:22:19,280
ดังนั้นโดยทั่วไปถ้าคุณที่โหนดว่า
มีค่าที่คุณกำลังมองหา

427
00:22:19,280 --> 00:22:23,550
คุณรู้ว่าคุณได้รับ
สามารถที่จะประสบความสำเร็จในการค้นหา

428
00:22:23,550 --> 00:22:27,150
>> มิฉะนั้นคุณต้องการตั้งค่า
ตัวชี้ของคุณไปยังโหนดถั​​ดไป

429
00:22:27,150 --> 00:22:28,850
นั่นคือสิ่งที่สายที่นี่ที่ทำ

430
00:22:28,850 --> 00:22:31,750
ชี้เท่ากับตัวชี้ต่อไป

431
00:22:31,750 --> 00:22:33,360
ทุกคนดูว่าที่ทำงาน?

432
00:22:33,360 --> 00:22:36,580
>> และเป็นหลักที่คุณกำลังจะเพียง
สำรวจความสมบูรณ์ของรายการ

433
00:22:36,580 --> 00:22:41,920
รีเซ็ตตัวชี้ของคุณเวลาจนกว่าแต่ละ
ในที่สุดคุณตีท้ายของรายการ

434
00:22:41,920 --> 00:22:45,030
และคุณรู้ว่าไม่มี
โหนดมากขึ้นในการค้นหาผ่าน

435
00:22:45,030 --> 00:22:47,999
และจากนั้นคุณสามารถกลับเท็จ
เพราะคุณรู้ว่าโอ้ดี

436
00:22:47,999 --> 00:22:50,540
ถ้าฉันได้รับสามารถที่จะค้นหา
ผ่านครบถ้วนของรายการ

437
00:22:50,540 --> 00:22:54,530
ถ้าในตัวอย่างนี้ถ้าผมต้องการ
ที่จะมองหาค่าของ 10

438
00:22:54,530 --> 00:22:57,250
และฉันเริ่มต้นที่หัวและ
ฉันค้นหาทั้งหมดทางลง

439
00:22:57,250 --> 00:23:00,550
และในที่สุดผมก็มาถึงนี้ซึ่ง
ชี้ที่ชี้ให้เป็นโมฆะที่

440
00:23:00,550 --> 00:23:04,415
ฉันรู้ว่าอึผมคิดว่า 10 ไม่ได้อยู่ใน
รายการนี​​้เพราะผมไม่สามารถหาได้

441
00:23:04,415 --> 00:23:06,520
และฉันในตอนท้ายของรายการ

442
00:23:06,520 --> 00:23:11,040
และในกรณีที่คุณรู้
ฉันจะกลับเท็จ

443
00:23:11,040 --> 00:23:12,900
>> ปล่อยให้แช่ในนิด ๆ หน่อย ๆ

444
00:23:12,900 --> 00:23:17,350
นี้จะสวย
สิ่งสำคัญสำหรับ pset ของคุณ

445
00:23:17,350 --> 00:23:21,140
ตรรกะของมันเป็นเรื่องง่ายมากอาจ
syntactically เพียงการดำเนินการนั้น

446
00:23:21,140 --> 00:23:23,365
พวกคุณต้องการที่จะทำให้
แน่ใจว่าคุณเข้าใจ

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
เย็น.

449
00:23:27,650 --> 00:23:32,560
>> ตกลงดังนั้นวิธีการที่เราจะเป็น
แทรกโหนดขวา

450
00:23:32,560 --> 00:23:35,380
ลงในรายการเพราะจำได้ว่า
สิ่งที่เป็นสิ่งที่ของผลประโยชน์

451
00:23:35,380 --> 00:23:39,230
ของการมีรายการที่เชื่อมโยงกับ
อาร์เรย์ในแง่ของการจัดเก็บอยู่แล้ว?

452
00:23:39,230 --> 00:23:41,110
>> ผู้ชม: มันเป็นแบบไดนามิก
ดังนั้นจึงเป็นเรื่องง่ายขึ้น to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: แน่นอน,
ดังนั้นจึงเป็นแบบไดนามิกซึ่ง

454
00:23:43,180 --> 00:23:46,880
หมายความว่ามันสามารถขยายและหดตัว
ขึ้นอยู่กับความต้องการของผู้ใช้

455
00:23:46,880 --> 00:23:56,570
ดังนั้นในแง่นี้เราไม่จำเป็นต้อง
เสียหน่วยความจำที่ไม่จำเป็นเพราะผม

456
00:23:56,570 --> 00:24:00,850
ถ้าฉันไม่ทราบว่าหลายค่าที่ฉันต้องการ
ในการจัดเก็บก็ไม่ได้ทำให้ความรู้สึกของฉัน

457
00:24:00,850 --> 00:24:04,310
เพื่อสร้างอาร์เรย์เพราะ
ถ้าผมต้องการที่จะเก็บค่า 10

458
00:24:04,310 --> 00:24:08,380
และฉันสร้างอาร์เรย์ 1,000 ที่
จำนวนมากของหน่วยความจำที่สูญเสียได้รับการจัดสรร

459
00:24:08,380 --> 00:24:11,180
นั่นเป็นเหตุผลที่เราต้องการที่จะใช้เชื่อมโยง
รายการที่จะสามารถแบบไดนามิก

460
00:24:11,180 --> 00:24:13,860
เปลี่ยนหรือหดขนาดของเรา

461
00:24:13,860 --> 00:24:17,040
>> และเพื่อที่จะทำให้การแทรก
บิตซับซ้อนมากขึ้น

462
00:24:17,040 --> 00:24:20,810
เนื่องจากเราไม่สามารถเข้าถึงองค์ประกอบแบบสุ่ม
วิธีการที่เราจะของอาร์เรย์

463
00:24:20,810 --> 00:24:24,270
ถ้าผมต้องการแทรกองค์ประกอบ
เข้าสู่ดัชนีที่เจ็ด

464
00:24:24,270 --> 00:24:26,930
ฉันสามารถใส่
เข้าสู่ดัชนีที่เจ็ด

465
00:24:26,930 --> 00:24:30,020
ในรายการที่เชื่อมโยงก็ไม่ได้
ค่อนข้างทำงานได้อย่างง่ายดาย

466
00:24:30,020 --> 00:24:34,947
และดังนั้นหากเราต้องการที่จะใส่
ที่นี่หนึ่งในรายการที่เชื่อมโยง

467
00:24:34,947 --> 00:24:36,280
สายตามันเป็นเรื่องง่ายมากที่จะเห็น

468
00:24:36,280 --> 00:24:39,363
เราเพียงแค่ต้องการที่จะใส่ที่นั่น
ที่เหมาะสมในการเริ่มต้นของรายการ

469
00:24:39,363 --> 00:24:40,840
หลังจากที่หัว

470
00:24:40,840 --> 00:24:44,579
>> แต่วิธีการที่เรามีการกำหนด
ชี้เป็นบิตซับซ้อน

471
00:24:44,579 --> 00:24:47,620
หรือเหตุผลที่มันทำให้รู้สึก แต่
คุณต้องการที่จะให้แน่ใจว่าคุณมีมัน

472
00:24:47,620 --> 00:24:50,250
เพราะลงอย่างสมบูรณ์
สิ่งสุดท้ายที่คุณต้องการ

473
00:24:50,250 --> 00:24:52,990
คือการกำหนดตัวชี้ที่
วิธีการที่เรากำลังทำอะไรที่นี่

474
00:24:52,990 --> 00:24:58,170
หากคุณ dereference
ตัวชี้จากหัวถึง 1,

475
00:24:58,170 --> 00:25:01,086
แล้วทั้งหมดในทันที
ส่วนที่เหลือของรายการที่เชื่อมโยงของคุณ

476
00:25:01,086 --> 00:25:04,680
จะหายไปเพราะคุณมีไม่จริง
สร้างอะไรชั่วคราว

477
00:25:04,680 --> 00:25:06,220
ที่ชี้ไปที่ 2

478
00:25:06,220 --> 00:25:10,080
ถ้าคุณกำหนดตัวชี้แล้ว
ส่วนที่เหลือของรายการของคุณจะหายไปโดยสิ้นเชิง

479
00:25:10,080 --> 00:25:13,310
ดังนั้นคุณจึงต้องการที่จะเป็น
มากระวังให้มากที่นี่

480
00:25:13,310 --> 00:25:17,010
ก่อนกำหนด
ตัวชี้จากสิ่งที่คุณ

481
00:25:17,010 --> 00:25:20,150
ต้องการแทรกลงในที่ใดก็ตาม
คุณต้องการและจากนั้นคุณ

482
00:25:20,150 --> 00:25:22,710
สามารถ dereference ส่วนที่เหลือของรายการของคุณ

483
00:25:22,710 --> 00:25:25,250
>> ดังนั้นนี้สำหรับทุกที่
คุณกำลังพยายามที่จะใส่ลงใน

484
00:25:25,250 --> 00:25:27,520
ถ้าคุณต้องการที่จะแทรกที่
หัวถ้าคุณต้องการที่จะตอบที่นี่

485
00:25:27,520 --> 00:25:29,455
ถ้าคุณต้องการที่จะแทรก
ท้ายที่สุดดี, เอ็นฉัน

486
00:25:29,455 --> 00:25:30,910
คิดว่าคุณจะเพียงแค่
มีตัวชี้ไม่มี แต่คุณ

487
00:25:30,910 --> 00:25:33,830
ต้องการที่จะให้แน่ใจว่าคุณทำไม่ได้
สูญเสียส่วนที่เหลือของรายการของคุณ

488
00:25:33,830 --> 00:25:36,640
คุณต้องการให้แน่ใจว่า
โหนดใหม่ของคุณจะชี้

489
00:25:36,640 --> 00:25:39,330
ที่มีต่อสิ่งที่คุณ
ต้องการแทรกลง

490
00:25:39,330 --> 00:25:42,170
และจากนั้นคุณสามารถเพิ่มผูกมัดบน

491
00:25:42,170 --> 00:25:43,330
ทุกคนชัดเจน?

492
00:25:43,330 --> 00:25:45,427
>> นี้เป็นไปได้
หนึ่งในปัญหาที่แท้จริง

493
00:25:45,427 --> 00:25:48,010
หนึ่งในประเด็นที่สำคัญมากที่สุด
คุณกำลังจะมีใน pset ของคุณ

494
00:25:48,010 --> 00:25:51,340
คือการที่คุณกำลังจะพยายามที่จะสร้าง
รายการที่เชื่อมโยงและสิ่งที่แทรก

495
00:25:51,340 --> 00:25:53,340
แต่แล้วก็สูญเสีย
ส่วนที่เหลือของรายการที่เชื่อมโยงของคุณ

496
00:25:53,340 --> 00:25:54,900
และคุณกำลังจะเป็นเหมือนผม
ไม่ทราบว่าทำไมนี้เกิดขึ้น?

497
00:25:54,900 --> 00:25:58,040
และมันก็เป็นความเจ็บปวดที่จะไปผ่าน
และค้นหาทั้งหมดของตัวชี้ของคุณ

498
00:25:58,040 --> 00:26:02,100
>> และฉันก็รับประกันคุณ pset นี้
การเขียนและการวาดภาพโหนดเหล่านี้ออก

499
00:26:02,100 --> 00:26:03,344
จะมีมากที่เป็นประโยชน์มาก

500
00:26:03,344 --> 00:26:06,010
ดังนั้นคุณสมบูรณ์สามารถติดตาม
ของที่ชี้ทั้งหมดของคุณมี

501
00:26:06,010 --> 00:26:08,540
สิ่งที่เกิดขึ้นที่ไม่ถูกต้อง
โหนดทั้งหมดที่คุณมี

502
00:26:08,540 --> 00:26:12,660
สิ่งที่คุณต้องทำเพื่อให้เข้าถึงหรือ
แทรกหรือลบหรือใด ๆ ของพวกเขา

503
00:26:12,660 --> 00:26:14,550
ทุกคนที่ดีกับที่?

504
00:26:14,550 --> 00:26:15,050
เย็น.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> ดังนั้นถ้าเราต้องการที่จะดูรหัส?

507
00:26:22,600 --> 00:26:24,470
โอ้ผมไม่ทราบว่าถ้าเรา
สามารถดูตกลง the-- ดังนั้น

508
00:26:24,470 --> 00:26:27,940
ที่ด้านบนทั้งหมดเป็นเป็นฟังก์ชั่น
แทรกชื่อที่เราต้องการ

509
00:26:27,940 --> 00:26:31,365
แทรก n int ลงในรายการที่เชื่อมโยง

510
00:26:31,365 --> 00:26:32,740
เรากำลังจะเดินผ่านทางนี้

511
00:26:32,740 --> 00:26:34,770
มันมากรหัสจำนวนมากไวยากรณ์ใหม่

512
00:26:34,770 --> 00:26:36,220
เราจะตกลง

513
00:26:36,220 --> 00:26:39,120
>> ดังนั้นขึ้นที่ด้านบนเมื่อใดก็ตามที่
เราต้องการที่จะสร้างอะไร

514
00:26:39,120 --> 00:26:42,380
ทำในสิ่งที่เราต้องทำโดยเฉพาะอย่างยิ่งถ้าคุณ
อยากให้มันไม่ถูกเก็บไว้ในกอง

515
00:26:42,380 --> 00:26:43,920
แต่ในกองหรือไม่

516
00:26:43,920 --> 00:26:45,460
เราไป malloc ใช่มั้ย?

517
00:26:45,460 --> 00:26:48,240
ดังนั้นเรากำลังจะสร้างตัวชี้

518
00:26:48,240 --> 00:26:52,074
โหนดชี้เท่ากับใหม่
malloc ขนาดของโหนด

519
00:26:52,074 --> 00:26:53,740
เพราะเราต้องการโหนดที่ถูกสร้างขึ้น

520
00:26:53,740 --> 00:26:56,720
เราต้องการปริมาณของ
หน่วยความจำที่โหนดจะขึ้น

521
00:26:56,720 --> 00:26:59,300
ที่จะได้รับการจัดสรรสำหรับ
การสร้างโหนดใหม่

522
00:26:59,300 --> 00:27:02,270
>> และจากนั้นเราจะตรวจสอบเพื่อ
ดูว่าเท่ากับใหม่เท่ากับ null

523
00:27:02,270 --> 00:27:03,370
โปรดจำไว้ว่าสิ่งที่เรากล่าวว่า?

524
00:27:03,370 --> 00:27:06,470
สิ่งที่คุณ malloc,
สิ่งที่คุณมักจะต้องทำอย่างไร

525
00:27:06,470 --> 00:27:09,490
คุณต้องตรวจสอบเพื่อดู
หรือไม่ว่าเป็นโมฆะ

526
00:27:09,490 --> 00:27:13,620
>> ตัวอย่างเช่นถ้าปฏิบัติการของคุณ
ระบบเต็มสมบูรณ์

527
00:27:13,620 --> 00:27:17,060
ถ้าคุณมีหน่วยความจำเพิ่มเติมได้ที่
และคุณพยายามที่จะ malloc,

528
00:27:17,060 --> 00:27:18,410
มันจะกลับมา null สำหรับคุณ

529
00:27:18,410 --> 00:27:21,094
ดังนั้นถ้าคุณพยายามที่จะใช้
เมื่อได้มีการชี้ให้เป็นโมฆะ,

530
00:27:21,094 --> 00:27:23,260
คุณจะไม่สามารถ
ในการเข้าถึงข้อมูลที่

531
00:27:23,260 --> 00:27:27,010
และเพื่อให้เป็นเช่นนี้เราต้องการที่จะทำให้
แน่ใจว่าเมื่อใดก็ตามที่คุณกำลัง mallocing,

532
00:27:27,010 --> 00:27:30,500
คุณมักจะตรวจสอบเพื่อดูว่า
หน่วยความจำที่ให้กับคุณเป็นโมฆะ

533
00:27:30,500 --> 00:27:33,670
และถ้ามันไม่ได้แล้วเราสามารถย้าย
กับส่วนที่เหลือของรหัสของเรา

534
00:27:33,670 --> 00:27:36,140
>> ดังนั้นเรากำลังจะไป
เริ่มต้นโหนดใหม่

535
00:27:36,140 --> 00:27:39,050
เรากำลังจะทำใหม่เท่ากับ n n

536
00:27:39,050 --> 00:27:42,390
แล้วเรากำลังจะทำ
กำหนดตัวชี้ใหม่ใหม่

537
00:27:42,390 --> 00:27:46,900
เพื่อ null เพราะตอนนี้เราทำไม่ได้
ต้องการอะไรมันจะชี้ไปที่

538
00:27:46,900 --> 00:27:48,755
เรามีความคิดที่ไม่มี
มันจะทำให้คุณ,

539
00:27:48,755 --> 00:27:50,630
แล้วถ้าเราต้องการ
ใส่ที่ศีรษะ

540
00:27:50,630 --> 00:27:53,820
แล้วเราสามารถกำหนด
ตัวชี้ไปที่หัว

541
00:27:53,820 --> 00:27:58,530
ทุกคนไม่ทำตามตรรกะ
ของการที่ที่เกิดขึ้น?

542
00:27:58,530 --> 00:28:02,502
>> ทั้งหมดที่เรากำลังทำคือการสร้างใหม่
โหนด, การตั้งค่าตัวชี้ให้เป็นโมฆะ,

543
00:28:02,502 --> 00:28:04,210
แล้วกำหนดใหม่
มันไปที่หัวถ้าเรา

544
00:28:04,210 --> 00:28:06,320
รู้ว่าเราต้องการที่จะใส่ที่หัว

545
00:28:06,320 --> 00:28:09,420
และแล้วหัวจะไป
ชี้ไปโหนดใหม่ที่

546
00:28:09,420 --> 00:28:11,060
ทุกคนตกลงกับที่?

547
00:28:11,060 --> 00:28:12,380
>> ดังนั้นจึงเป็นกระบวนการสองขั้นตอน

548
00:28:12,380 --> 00:28:14,760
คุณได้มีการกำหนดเป็นครั้งแรก
สิ่งที่คุณกำลังสร้าง

549
00:28:14,760 --> 00:28:18,260
ตั้งชี้ไปที่
อ้างอิงและจากนั้นคุณ

550
00:28:18,260 --> 00:28:21,400
สามารถชนิดของ dereference
ตัวชี้เป็นครั้งแรก

551
00:28:21,400 --> 00:28:22,972
และชี้ไปที่โหนดใหม่

552
00:28:22,972 --> 00:28:25,680
เมื่อใดก็ตามที่คุณต้องการแทรกมัน
ตรรกะที่จะไปถือเป็นจริง

553
00:28:25,680 --> 00:28:27,530
>> มันเป็นชนิดเช่นการกำหนด
ตัวแปรชั่วคราว

554
00:28:27,530 --> 00:28:28,700
โปรดจำไว้ว่าคุณได้มี
เพื่อให้แน่ใจว่าคุณ

555
00:28:28,700 --> 00:28:30,346
จะไม่สูญเสียการติดตามของถ้าคุณกำลังแลกเปลี่ยน

556
00:28:30,346 --> 00:28:33,470
คุณต้องการที่จะตรวจสอบให้แน่ใจว่าคุณมี
ตัวแปรชั่วคราวที่ชนิดของการเก็บ

557
00:28:33,470 --> 00:28:35,620
ติดตามการที่สิ่งหนึ่งที่
จะถูกเก็บไว้เพื่อให้คุณ

558
00:28:35,620 --> 00:28:41,190
ไม่เสียค่าใด ๆ ในการเรียนการสอน
เช่น messing รอบกับมัน

559
00:28:41,190 --> 00:28:42,710
>> ตกลงดังนั้นรหัสจะอยู่ที่นี่

560
00:28:42,710 --> 00:28:45,020
พวกคุณจะดูหลังจากที่ส่วน

561
00:28:45,020 --> 00:28:48,060
มันจะมี

562
00:28:48,060 --> 00:28:50,280
>> ดังนั้นผมคิดว่าวิธีการที่ไม่
นี้แตกต่างกันถ้าเราต้องการ

563
00:28:50,280 --> 00:28:52,300
เพื่อแทรกลงในกลางหรือปลายหรือไม่

564
00:28:52,300 --> 00:28:57,892
ทุกคนมีความคิดของสิ่งที่
pseudocode เป็นอ้างอิงตรรกะ

565
00:28:57,892 --> 00:29:00,350
ที่เราจะต้องใช้เวลาถ้าเราต้องการ
ที่จะแทรกอยู่ตรงกลาง?

566
00:29:00,350 --> 00:29:03,391
ดังนั้นถ้าเราต้องการที่จะใส่ไว้ที่
หัวทุกสิ่งที่เราทำคือการสร้างโหนดใหม่

567
00:29:03,391 --> 00:29:06,311
เราตั้งตัวชี้ของที่
โหนดใหม่เพื่อสิ่งที่หัว

568
00:29:06,311 --> 00:29:08,310
และจากนั้นเราตั้งหัว
ไปยังโหนดใหม่ใช่มั้ย?

569
00:29:08,310 --> 00:29:11,560
ถ้าเราต้องการที่จะแทรกอยู่ตรงกลาง
ของรายการสิ่งที่เราจะต้องทำอย่างไร

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> ผู้ชม: มันจะยังคง
จะเป็นกระบวนการที่คล้ายกัน

572
00:29:16,110 --> 00:29:19,114
เช่นการกำหนดตัวชี้และ
แล้วการกำหนดตัวชี้ว่า

573
00:29:19,114 --> 00:29:20,530
แต่เราจะต้องมีการค้นหา

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: แน่นอนดังนั้นว่า
กระบวนการเดียวกันยกเว้นคุณ

575
00:29:23,560 --> 00:29:27,820
ต้องค้นหาที่ว่าคุณ
ต้องการที่ชี้ใหม่ที่จะไปลง

576
00:29:27,820 --> 00:29:44,790
ดังนั้นถ้าผมต้องการที่จะใส่ลงใน
ช่วงกลางของการเชื่อมโยง list-- ตกลง

577
00:29:44,790 --> 00:29:46,370
ขอบอกว่าเป็นรายการที่เชื่อมโยงของเรา

578
00:29:46,370 --> 00:29:49,500
ถ้าเราต้องการที่จะใส่ที่นี่
เรากำลังจะสร้างโหนดใหม่

579
00:29:49,500 --> 00:29:50,520
เรากำลังจะไป malloc

580
00:29:50,520 --> 00:29:52,220
เรากำลังจะสร้างโหนดใหม่

581
00:29:52,220 --> 00:29:55,940
เรากำลังจะไปกำหนด
ตัวชี้ของโหนดที่นี่

582
00:29:55,940 --> 00:29:58,335
>> แต่ปัญหาที่แตกต่าง
จากการที่หัวเป็น

583
00:29:58,335 --> 00:30:00,490
คือการที่เรารู้ว่า
ที่หัวเป็น

584
00:30:00,490 --> 00:30:01,930
มันเป็นที่ที่เหมาะสมในครั้งแรกใช่ไหม?

585
00:30:01,930 --> 00:30:04,870
แต่ที่นี่เราได้มีการติดตาม
ของที่เรากำลังใส่ลงใน

586
00:30:04,870 --> 00:30:07,930
ถ้าเราใส่ของเรา
โหนดที่นี่เรามี

587
00:30:07,930 --> 00:30:12,270
เพื่อให้แน่ใจว่า
ก่อนหน้านี้หนึ่งไปยังโหนดนี้

588
00:30:12,270 --> 00:30:14,172
เป็นสิ่งหนึ่งที่ reassigns ตัวชี้

589
00:30:14,172 --> 00:30:16,380
ดังนั้นแล้วคุณจะต้องชนิดของ
ติดตามในสองสิ่ง

590
00:30:16,380 --> 00:30:19,420
ถ้าคุณสามารถติดตามของที่นี้
โหนดปัจจุบันคือการใส่ลงใน

591
00:30:19,420 --> 00:30:23,280
นอกจากนี้คุณยังต้องติดตามการที่
โหนดก่อนหน้านี้ที่คุณกำลังมองหา

592
00:30:23,280 --> 00:30:24,340
ยังอยู่ที่นั่น

593
00:30:24,340 --> 00:30:25,830
ทุกคนที่ดีกับที่?

594
00:30:25,830 --> 00:30:26,500
ตกลง.

595
00:30:26,500 --> 00:30:28,000
>> วิธีการเกี่ยวกับการใส่ลงไปในที่สุด?

596
00:30:28,000 --> 00:30:34,220
ถ้าผมต้องการที่จะเพิ่ม here-- ถ้าผมต้องการ
การเพิ่มโหนดใหม่ที่ส่วนท้ายของรายการที่

597
00:30:34,220 --> 00:30:37,009
วิธีการที่ฉันอาจจะไปเกี่ยวกับการทำเช่นนั้น?

598
00:30:37,009 --> 00:30:39,300
ผู้ชม: ดังนั้นในปัจจุบัน
หนึ่งที่ผ่านมาชี้ให้เป็นโมฆะ

599
00:30:39,300 --> 00:30:40,960
ANDI เป็ง: ใช่

600
00:30:40,960 --> 00:30:43,560
ตรงนี้จึงเป็นหนึ่ง
ในปัจจุบันคือการชี้ให้เห็นที่จะรู้ว่า

601
00:30:43,560 --> 00:30:46,720
และผมคิดว่าในความรู้สึกนี้ก็
ง่ายมากที่จะเพิ่มถึงจุดสิ้นสุดของรายการ

602
00:30:46,720 --> 00:30:51,810
สิ่งที่คุณต้องทำคือการตั้งค่า
เท่ากับเป็นโมฆะแล้วบูม

603
00:30:51,810 --> 00:30:53,070
มีสิทธิที่ง่ายมาก

604
00:30:53,070 --> 00:30:53,960
ง่ายมาก.

605
00:30:53,960 --> 00:30:56,430
>> คล้ายกับ
มุ่ง แต่เหตุผลที่คุณ

606
00:30:56,430 --> 00:30:59,690
ต้องการที่จะให้แน่ใจว่าขั้นตอน
คุณจะใช้เวลาที่มีต่อการดำเนินการใด ๆ ในเรื่องนี้

607
00:30:59,690 --> 00:31:01,500
คุณไปพร้อม

608
00:31:01,500 --> 00:31:04,420
มันง่ายมากที่จะอยู่ตรงกลาง
ของรหัสของคุณได้รับการติดขึ้นบน

609
00:31:04,420 --> 00:31:05,671
โอ้ฉันมีตัวชี้จำนวนมาก

610
00:31:05,671 --> 00:31:07,461
ผมไม่ทราบว่า
สิ่งที่จะชี้ไปที่

611
00:31:07,461 --> 00:31:09,170
ฉันไม่ได้รู้ว่าโหนดซึ่งฉัน

612
00:31:09,170 --> 00:31:11,490
เกิดอะไรขึ้น?

613
00:31:11,490 --> 00:31:13,620
>> ผ่อนคลายสงบลงหายใจลึก

614
00:31:13,620 --> 00:31:15,530
วาดออกรายการที่เชื่อมโยงของคุณ

615
00:31:15,530 --> 00:31:18,800
ถ้าคุณบอกว่าฉันรู้ว่าที่ว่า
ฉันต้องการที่จะแทรกเข้ามาในนี้

616
00:31:18,800 --> 00:31:22,970
และฉันรู้ว่าวิธีการที่กำหนดของฉัน
ตัวชี้มากง่ายมากที่จะถ่ายภาพ

617
00:31:22,970 --> 00:31:27,200
out-- มากง่ายมากที่จะไม่ได้
ได้หายไปในข้อบกพร่องของรหัสของคุณ

618
00:31:27,200 --> 00:31:29,410
ทุกคนตกลงกับที่?

619
00:31:29,410 --> 00:31:31,380
ตกลง.

620
00:31:31,380 --> 00:31:35,120
>> ดังนั้นผมคิดว่าแนวคิดที่เรายังไม่ได้
จริงๆก่อนที่จะพูดคุยเกี่ยวกับตอนนี้

621
00:31:35,120 --> 00:31:38,131
และผมคิดว่าคุณอาจจะ
จะไม่พบ yet-- มาก

622
00:31:38,131 --> 00:31:40,880
มันเป็นชนิดของ concept-- ขั้นสูง
คือการที่เราจะมีข้อมูลที่

623
00:31:40,880 --> 00:31:43,900
โครงสร้างที่เรียกว่ารายการที่เชื่อมโยงเป็นทวีคูณ

624
00:31:43,900 --> 00:31:46,390
ดังนั้นในขณะที่พวกคุณสามารถดู
ทุกสิ่งที่เรากำลังทำคือการสร้าง

625
00:31:46,390 --> 00:31:50,400
ค่าที่เกิดขึ้นจริงเป็นพิเศษ
ตัวชี้ในแต่ละโหนดของเรา

626
00:31:50,400 --> 00:31:52,660
ที่ยังชี้ไปยังโหนดก่อนหน้านี้

627
00:31:52,660 --> 00:31:58,170
ดังนั้นไม่เพียง แต่เรามีของเรา
โหนดชี้ไปที่หน้าหนึ่ง

628
00:31:58,170 --> 00:32:01,430
พวกเขายังชี้ไปที่หนึ่งก่อนหน้านี้

629
00:32:01,430 --> 00:32:04,310
ฉันจะที่จะไม่สนใจทั้งสองได้ในขณะนี้

630
00:32:04,310 --> 00:32:06,740
>> ดังนั้นแล้วคุณมีโซ่
ที่สามารถเคลื่อนที่ได้ทั้งสองวิธี

631
00:32:06,740 --> 00:32:09,630
และจากนั้นก็เป็นบิตง่ายขึ้น
เหตุผลที่จะทำตาม

632
00:32:09,630 --> 00:32:11,896
เช่นเดียวกับที่นี่แทน
ติดตามความเคลื่อนไหวของโอ้ฉัน

633
00:32:11,896 --> 00:32:14,520
ต้องรู้ว่าโหนดนี้คือ
คนที่ฉันต้องกำหนด,

634
00:32:14,520 --> 00:32:17,532
ฉันสามารถไปที่นี่และ
เพียงดึงก่อนหน้านี้

635
00:32:17,532 --> 00:32:19,490
จากนั้นฉันก็รู้ว่าที่
ที่อยู่และจากนั้นคุณ

636
00:32:19,490 --> 00:32:21,130
ไม่ได้มีการสำรวจ
สมบูรณ์ของรายการที่เชื่อมโยง

637
00:32:21,130 --> 00:32:22,180
เป็นบิตง่ายขึ้น

638
00:32:22,180 --> 00:32:24,960
>> แต่เป็นเช่นนี้คุณต้องเป็นทวีคูณ
จำนวนของตัวชี้ที่

639
00:32:24,960 --> 00:32:26,960
ที่สองจำนวนของหน่วยความจำ

640
00:32:26,960 --> 00:32:28,950
มันมากของตัวชี้ที่จะติดตาม

641
00:32:28,950 --> 00:32:32,140
เป็นบิตที่ซับซ้อนมากขึ้น แต่ก็
ผู้ใช้ที่เป็นมิตรอีกเล็กน้อยขึ้นอยู่กับ

642
00:32:32,140 --> 00:32:34,080
กับสิ่งที่คุณกำลังพยายามที่จะประสบความสำเร็จ

643
00:32:34,080 --> 00:32:36,910
>> ดังนั้นชนิดของข้อมูลนี้
โครงสร้างทั้งหมดที่มีอยู่

644
00:32:36,910 --> 00:32:40,280
และโครงสร้างเป็นอย่างมาก
ง่ายยกเว้นสิ่งที่คุณกำลังมีอยู่

645
00:32:40,280 --> 00:32:43,850
แทนเพียงตัวชี้ไปข้างหน้า
คุณยังมีตัวชี้ไปก่อนหน้านี้

646
00:32:43,850 --> 00:32:45,940
นั่นคือทั้งหมดที่แตกต่างกันคือ

647
00:32:45,940 --> 00:32:47,740
ทุกคนที่ดีกับที่?

648
00:32:47,740 --> 00:32:48,240
เย็น.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> สิทธิทั้งหมดดังนั้นตอนนี้ฉัน
จริงๆอาจจะใช้จ่าย

651
00:32:53,280 --> 00:32:56,870
เช่น 15-20 นาทีหรือเป็นกลุ่ม
ส่วนที่เหลือของเวลาในส่วน

652
00:32:56,870 --> 00:32:58,360
พูดคุยเกี่ยวกับตารางแฮช

653
00:32:58,360 --> 00:33:02,590
จำนวนของพวกคุณ
ได้อ่านข้อมูลจำเพาะ pset5?

654
00:33:02,590 --> 00:33:03,620
สิทธิทั้งหมดที่ดี

655
00:33:03,620 --> 00:33:06,160
นั่นคือสูงกว่า 50% ของตามปกติ

656
00:33:06,160 --> 00:33:07,560
ไม่เป็นไร.

657
00:33:07,560 --> 00:33:10,345
>> ดังนั้นในขณะที่พวกคุณจะได้เห็น
คุณความท้าทายในการ pset5

658
00:33:10,345 --> 00:33:16,790
จะได้รับการดำเนินการตามพจนานุกรม
ที่คุณโหลดกว่า 140,000 คำ

659
00:33:16,790 --> 00:33:20,610
ที่เราให้คุณและตรวจสอบการสะกด
มันกับข้อความทั้งหมด

660
00:33:20,610 --> 00:33:22,580
เราจะให้คุณแบบสุ่ม
ชิ้นส่วนของวรรณกรรม

661
00:33:22,580 --> 00:33:23,520
เราจะให้คุณโอเดสซี

662
00:33:23,520 --> 00:33:24,561
เราจะให้คุณอีเลียด

663
00:33:24,561 --> 00:33:26,350
เราจะให้คุณออสติน

664
00:33:26,350 --> 00:33:28,220
>> และความท้าทายของคุณ
จะได้รับการตรวจสอบการสะกด

665
00:33:28,220 --> 00:33:31,760
ทุกคำเดียวในทุก
พจนานุกรมเหล่านั้น

666
00:33:31,760 --> 00:33:34,960
เป็นหลักที่มีตรวจสอบการสะกดของเรา

667
00:33:34,960 --> 00:33:38,620
และเพื่อให้มีชิ้นส่วนเพียงไม่กี่
ของการสร้าง pset นี้

668
00:33:38,620 --> 00:33:41,970
แรกที่คุณต้องการที่จะเป็น
สามารถโหลดจริง

669
00:33:41,970 --> 00:33:43,970
ทุกคำของคุณลงใน
พจนานุกรมและจากนั้นคุณ

670
00:33:43,970 --> 00:33:45,530
ต้องการที่จะสามารถที่จะ
ตรวจสอบการสะกดทั้งหมดของพวกเขา

671
00:33:45,530 --> 00:33:48,780
และเพื่อให้เป็นเช่นนี้คุณจะต้อง
โครงสร้างข้อมูลที่สามารถทำอย่างรวดเร็วนี้

672
00:33:48,780 --> 00:33:50,790
และมีประสิทธิภาพและแบบไดนามิก

673
00:33:50,790 --> 00:33:52,900
>> ดังนั้นผมจึงคิดว่าง่ายที่สุด
วิธีการที่จะทำเช่นนี้คุณ

674
00:33:52,900 --> 00:33:55,010
อาจจะสร้างอาร์เรย์ใช่มั้ย?

675
00:33:55,010 --> 00:33:58,910
วิธีที่ง่ายที่สุดในการจัดเก็บที่เป็นคุณ
สามารถสร้างอาร์เรย์ของ 140,000 คำ

676
00:33:58,910 --> 00:34:03,400
และเพียงแค่วางพวกเขาทั้งหมดที่มีและ
จากนั้นพวกเขาโดยการสำรวจค้นหาแบบทวิภาค

677
00:34:03,400 --> 00:34:06,780
หรือโดยการเลือกหรือ not--
ขอโทษที่การเรียงลำดับ

678
00:34:06,780 --> 00:34:10,729
คุณสามารถจัดเรียงพวกเขาแล้วพวกเขาสำรวจ
โดยการค้นหาแบบไบนารีหรือเพียงแค่การค้นหาเชิงเส้น

679
00:34:10,729 --> 00:34:13,730
และเพียงแค่คำพูดสุดท้าย แต่ที่
จะใช้เวลาเป็นจำนวนมากของหน่วยความจำ

680
00:34:13,730 --> 00:34:15,190
และก็ไม่ได้มีประสิทธิภาพมาก

681
00:34:15,190 --> 00:34:18,350
>> และเพื่อที่เรากำลังจะเริ่มต้น
พูดคุยเกี่ยวกับวิธีการทำ

682
00:34:18,350 --> 00:34:20,110
เวลาทำงานของเรามีประสิทธิภาพมากขึ้น

683
00:34:20,110 --> 00:34:23,190
และเป้าหมายของเราคือการได้รับ
เวลาคงที่

684
00:34:23,190 --> 00:34:25,810
มันเกือบจะเหมือนอาร์เรย์ที่
คุณมีการเข้าถึงทันที

685
00:34:25,810 --> 00:34:28,560
ถ้าผมต้องการที่จะค้นหาอะไร
ฉันต้องการที่จะสามารถที่จะเพียงแค่

686
00:34:28,560 --> 00:34:30,810
บูมพบว่ามันตรงและดึงออก

687
00:34:30,810 --> 00:34:34,100
และเพื่อให้โครงสร้างที่
เราจะกลายเป็นความใกล้ชิด

688
00:34:34,100 --> 00:34:37,569
เพื่อให้สามารถเข้าถึงอย่างต่อเนื่อง
เวลานี้ศักดิ์สิทธิ์

689
00:34:37,569 --> 00:34:41,370
ในการเขียนโปรแกรมของอย่างต่อเนื่อง
เวลาที่เรียกว่าตารางแฮช

690
00:34:41,370 --> 00:34:45,370
และเพื่อให้เดวิดกล่าวถึงก่อนหน้านี้
[ไม่ได้ยิน] นิด ๆ หน่อย ๆ ในการบรรยาย

691
00:34:45,370 --> 00:34:49,100
แต่เรากำลังจะไปจริงๆ
ดำน้ำลึกในสัปดาห์นี้

692
00:34:49,100 --> 00:34:51,780
ในส่วนที่เกี่ยวกับการ
วิธีตารางแฮชผลงาน

693
00:34:51,780 --> 00:34:53,949
>> ดังนั้นวิธีการที่แฮช
ตารางงานยกตัวอย่างเช่น

694
00:34:53,949 --> 00:35:00,230
ถ้าผมต้องการที่จะเก็บพวงของคำเป็น
พวงของคำในภาษาอังกฤษ

695
00:35:00,230 --> 00:35:02,940
ผมในทางทฤษฎีสามารถใส่
กล้วยแอปเปิ้ลกีวีมะม่วงคู่

696
00:35:02,940 --> 00:35:04,980
และแคนตาลูปทั้งหมดเพียงอาร์เรย์

697
00:35:04,980 --> 00:35:07,044
พวกเขาอาจจะทั้งหมดพอดีและพบว่า

698
00:35:07,044 --> 00:35:09,210
มันต้องการจะเป็นชนิดของความเจ็บปวดไปยัง
ค้นหาผ่านเข้าถึงและ

699
00:35:09,210 --> 00:35:12,920
แต่วิธีที่ง่ายของการทำเช่นนี้คือ
ที่เราสามารถสร้างโครงสร้างจริง

700
00:35:12,920 --> 00:35:15,680
เรียกว่าตารางแฮชที่เราสับ

701
00:35:15,680 --> 00:35:19,880
เราทำงานทั้งหมดของคีย์ของเราผ่าน
ฟังก์ชั่นแฮช, สมการ,

702
00:35:19,880 --> 00:35:22,600
ที่จะเปลี่ยนพวกเขาทั้งหมดลง
การเรียงลำดับของค่าบางอย่าง

703
00:35:22,600 --> 00:35:28,740
ว่าแล้วเราสามารถจัดเก็บลงบน
หลักอาร์เรย์ของรายการที่เชื่อมโยง

704
00:35:28,740 --> 00:35:32,570
>> และอื่น ๆ ที่นี่ถ้าเราต้องการ
ในการจัดเก็บคำในภาษาอังกฤษ,

705
00:35:32,570 --> 00:35:37,250
ที่อาจเกิดขึ้นเราสามารถทำได้เพียงแค่ฉันทำไม่ได้
รู้ว่าเปิดทุกตัวอักษรตัวแรก

706
00:35:37,250 --> 00:35:39,630
เป็นประเภทของตัวเลขบางอย่าง

707
00:35:39,630 --> 00:35:43,140
และอื่น ๆ ยกตัวอย่างเช่นถ้าผมต้องการ
ที่จะตรงกันกับ apple--

708
00:35:43,140 --> 00:35:47,460
หรือมีค่าดัชนีของ 0 และ
B จะตรงกันกับ 1,

709
00:35:47,460 --> 00:35:51,030
เราสามารถมี 26 รายการ
ที่เพียงแค่สามารถจัดเก็บ

710
00:35:51,030 --> 00:35:53,610
ทุกตัวอักษรของ
ตัวอักษรที่เราจะเริ่มต้นด้วย

711
00:35:53,610 --> 00:35:56,130
และจากนั้นเราจะได้มี
แอปเปิ้ลที่ดัชนีของ 0

712
00:35:56,130 --> 00:35:59,160
เราสามารถมีกล้วยที่ดัชนีของ
1, แคนตาลูปที่ดัชนีของ 2,

713
00:35:59,160 --> 00:36:00,540
และอื่น ๆ และอื่น ๆ.

714
00:36:00,540 --> 00:36:04,460
และทำให้ถ้าผมต้องการที่จะค้นหา
ตารางแฮชของฉันและแอปเปิ้ลการเข้าถึง

715
00:36:04,460 --> 00:36:07,560
ฉันรู้ว่าแอปเปิ้ลจะเริ่มต้นด้วย
ต่อ A และฉันรู้ว่า

716
00:36:07,560 --> 00:36:10,860
ว่ามันจะต้องเป็นและกัญชา
ตารางที่ดัชนี 0 เพราะ

717
00:36:10,860 --> 00:36:13,620
ของการทำงานที่ได้รับมอบหมายก่อนหน้านี้

718
00:36:13,620 --> 00:36:16,572
>> ดังนั้นผมจึงไม่ทราบว่าเรามี
โปรแกรมที่ใช้

719
00:36:16,572 --> 00:36:18,780
คุณจะได้รับค่าใช้จ่ายด้วย
arbitrarily-- ไม่พล

720
00:36:18,780 --> 00:36:22,530
กับความพยายามที่จะคิด
คิดว่าสมการที่ดี

721
00:36:22,530 --> 00:36:25,460
เพื่อให้สามารถที่จะแพร่กระจาย
ออกทั้งหมดของค่าของคุณ

722
00:36:25,460 --> 00:36:29,370
ในทางที่พวกเขาสามารถเข้าถึงได้อย่างง่ายดาย
ได้ในภายหลังด้วยเช่นสมการ

723
00:36:29,370 --> 00:36:31,130
ที่คุณเองรู้

724
00:36:31,130 --> 00:36:35,210
ดังนั้นในแง่ที่ว่าถ้าผมอยากจะไป
มะม่วงฉันรู้ว่าโอ้จะเริ่มต้นด้วยม.

725
00:36:35,210 --> 00:36:37,134
มันจะต้องเป็นที่ดัชนี 12

726
00:36:37,134 --> 00:36:38,800
ฉันไม่ได้มีการค้นหาผ่านอะไร

727
00:36:38,800 --> 00:36:42,080
ฉันรู้ว่า exactly-- ฉันสามารถไปที่
ดัชนี 12 และดึงออก

728
00:36:42,080 --> 00:36:45,520
>> ทุกคนที่ชัดเจนเกี่ยวกับวิธีการที่
ฟังก์ชั่นของตารางแฮชทำงานอย่างไร

729
00:36:45,520 --> 00:36:48,380
เป็นชนิดของเพียงอาร์เรย์ที่ซับซ้อนมากขึ้น

730
00:36:48,380 --> 00:36:50,010
นั่นคือทั้งหมดที่มันเป็น

731
00:36:50,010 --> 00:36:51,630
ตกลง.

732
00:36:51,630 --> 00:36:57,690
>> ดังนั้นผมจึงคิดว่าเราทำงานเป็น
ปัญหาของสิ่งนี้

733
00:36:57,690 --> 00:37:06,390
เกิดขึ้นถ้าคุณมีสิ่งที่หลาย ๆ
ที่ให้คุณดัชนีเดียวกันได้หรือไม่

734
00:37:06,390 --> 00:37:10,570
เพื่อบอกว่าฟังก์ชั่นของเราทั้งหมดก็
ไม่ได้ใช้เวลาที่ตัวอักษรตัวแรก

735
00:37:10,570 --> 00:37:14,490
และเปิดที่เป็น
ที่เกี่ยวข้อง 0 ถึง 25 ดัชนี

736
00:37:14,490 --> 00:37:17,137
นั่นคือทั้งหมดที่ดีถ้า
คุณมีเพียงหนึ่งของแต่ละ

737
00:37:17,137 --> 00:37:18,970
แต่ที่สองคุณเริ่มต้น
มีมากขึ้นคุณ

738
00:37:18,970 --> 00:37:20,910
จะมีสิ่งที่เรียกว่าการปะทะกัน

739
00:37:20,910 --> 00:37:25,580
>> ดังนั้นถ้าผมพยายามที่จะแทรกเข้าไปฝังกัญชา
ตารางที่มีอยู่แล้วกล้วยกับมัน

740
00:37:25,580 --> 00:37:27,870
สิ่งที่จะเกิดขึ้นเมื่อ
คุณพยายามที่จะแทรกที่?

741
00:37:27,870 --> 00:37:30,930
สิ่งที่ไม่ดีเพราะกล้วย
ที่มีอยู่แล้วภายในดัชนี

742
00:37:30,930 --> 00:37:33,800
ที่คุณต้องการเก็บไว้ใน

743
00:37:33,800 --> 00:37:35,560
ชนิดของแบล็กเบอร์เป็นเหมือน ah, สิ่งที่ฉันจะทำอย่างไร

744
00:37:35,560 --> 00:37:37,080
ผมไม่ทราบว่าจะไปที่ไหน

745
00:37:37,080 --> 00:37:38,410
ฉันจะแก้ปัญหานี้ได้อย่างไร?

746
00:37:38,410 --> 00:37:41,150
>> และเพื่อให้พวกคุณจะชนิดของ
เห็นว่าเราทำเช่นนี้สิ่งที่ยุ่งยาก

747
00:37:41,150 --> 00:37:44,810
ที่เราสามารถชนิดของจริง
สร้างรายการเชื่อมโยงในอาร์เรย์ของเรา

748
00:37:44,810 --> 00:37:46,840
ดังนั้นวิธีที่ง่ายที่สุด
ที่จะคิดเกี่ยวกับเรื่องนี้

749
00:37:46,840 --> 00:37:50,830
ตารางแฮชทั้งหมดเป็น
อาร์เรย์ของรายการที่เชื่อมโยง

750
00:37:50,830 --> 00:37:55,670
และอื่น ๆ ในความรู้สึกที่คุณมี
นี้อาร์เรย์ที่สวยงามของตัวชี้

751
00:37:55,670 --> 00:37:58,740
และจากนั้นในแต่ละตัวชี้
ค่าที่อยู่ในดัชนีที่

752
00:37:58,740 --> 00:38:00,740
จริงสามารถชี้ไปที่สิ่งอื่น ๆ

753
00:38:00,740 --> 00:38:05,720
และเพื่อให้คุณมีทั้งหมดเหล่านี้แยกต่างหาก
โซ่ออกมาจากอาเรย์ขนาดใหญ่

754
00:38:05,720 --> 00:38:07,960
>> และอื่น ๆ ที่นี่ถ้าฉัน
อยากจะใส่เบอร์รี่,

755
00:38:07,960 --> 00:38:11,220
ฉันรู้ว่าตกลงฉันจะป้อนข้อมูล
มันผ่านฟังก์ชันแฮชของฉัน

756
00:38:11,220 --> 00:38:15,070
ฉันจะจบลงด้วยดัชนีของ
1 แล้วฉันจะสามารถที่จะมี

757
00:38:15,070 --> 00:38:20,410
เพียงส่วนย่อยที่มีขนาดเล็กนี้
ยักษ์ 140,000 คำพจนานุกรม

758
00:38:20,410 --> 00:38:24,220
แล้วฉันก็สามารถมอง
ผ่าน 1/26 ที่

759
00:38:24,220 --> 00:38:27,910
>> และอื่น ๆ แล้วฉันก็สามารถแทรก
แบล็กเบอร์ก่อนหรือหลังกล้วย

760
00:38:27,910 --> 00:38:28,820
ในกรณีนี้?

761
00:38:28,820 --> 00:38:29,700
หลังจากใช่มั้ย?

762
00:38:29,700 --> 00:38:33,920
และเพื่อให้คุณจะต้องการที่จะ
แทรกโหนดนี้หลังจากที่กล้วย

763
00:38:33,920 --> 00:38:36,667
และเพื่อให้คุณกำลังจะแทรก
ที่หางของรายการที่เชื่อมโยงว่า

764
00:38:36,667 --> 00:38:38,500
ฉันจะกลับไป
ไปยังภาพนิ่งก่อนหน้านี้

765
00:38:38,500 --> 00:38:40,680
เพื่อที่พวกคุณจะได้เห็นว่า
งานฟังก์ชันแฮช

766
00:38:40,680 --> 00:38:43,980
>> ดังนั้นฟังก์ชันแฮชเป็นสมการนี​​้
ว่าคุณกำลังใช้ชนิดของการป้อนข้อมูลของคุณ

767
00:38:43,980 --> 00:38:46,940
ผ่านทางที่จะได้รับสิ่งที่ดัชนี
คุณต้องการที่จะกำหนดต่อ

768
00:38:46,940 --> 00:38:51,130
ดังนั้นในตัวอย่างนี้ทั้งหมดที่เราต้องการ
จะทำคือใช้ตัวอักษรตัวแรก,

769
00:38:51,130 --> 00:38:55,890
เปิดที่เป็นดัชนีแล้วเรา
สามารถจัดเก็บว่าในฟังก์ชันแฮชของเรา

770
00:38:55,890 --> 00:39:00,160
ทั้งหมดที่เรากำลังทำอะไรที่นี่คือเรา
แปลงตัวอักษรตัวแรก

771
00:39:00,160 --> 00:39:04,770
KeyKey ดังนั้น [0] เป็นเพียงตัวอักษรตัวแรก
ของสตริงสิ่งที่เรากำลังมี,

772
00:39:04,770 --> 00:39:05,720
เรากำลังผ่านใน

773
00:39:05,720 --> 00:39:09,740
เรากำลังแปลงที่บนและ
เรากำลังลบโดยพิมพ์ใหญ่ A,

774
00:39:09,740 --> 00:39:11,740
ดังนั้นสิ่งที่จะทำ
จะให้เราเป็นจำนวนมาก

775
00:39:11,740 --> 00:39:13,670
ที่เราสามารถสับลงบนค่านิยมของเรา

776
00:39:13,670 --> 00:39:16,550
>> และจากนั้นเรากำลังจะไป
โมดูลัสกลับขนาดกัญชา

777
00:39:16,550 --> 00:39:19,340
จะมากระวังให้มาก
เพราะเหตุผลที่นี่

778
00:39:19,340 --> 00:39:21,870
ค่าแฮชของคุณอาจจะไม่มีที่สิ้นสุด

779
00:39:21,870 --> 00:39:23,660
มันก็สามารถไปบนและบนและบน

780
00:39:23,660 --> 00:39:26,080
มันอาจจะมีบางจริงๆ
ค่าขนาดใหญ่จริงๆ

781
00:39:26,080 --> 00:39:29,849
แต่เป็นเพราะตารางแฮชคุณที่
คุณได้สร้างมีเพียง 26 ดัชนี

782
00:39:29,849 --> 00:39:31,890
คุณต้องการที่จะให้แน่ใจว่าคุณ
modulusing เพื่อให้คุณ

783
00:39:31,890 --> 00:39:33,848
ไม่ run-- ก็เหมือนกัน
สิ่งที่เป็นของคุณ queue--

784
00:39:33,848 --> 00:39:36,320
เพื่อที่คุณจะไม่ทำงานออก
ด้านล่างของฟังก์ชันแฮชของคุณ

785
00:39:36,320 --> 00:39:39,210
>> คุณต้องการที่จะตัดกลับไปรอบ ๆ
วิธีเดียวกันใน [ไม่ได้ยิน] เมื่อ

786
00:39:39,210 --> 00:39:41,750
คุณมีเหมือนมาก
ตัวอักษรที่มีขนาดใหญ่มากคุณ

787
00:39:41,750 --> 00:39:43,740
ไม่ได้ต้องการที่
เพียงแค่เรียกใช้ปิดท้าย

788
00:39:43,740 --> 00:39:46,948
สิ่งเดียวกันที่นี่คุณต้องการให้แน่ใจว่า
จะไม่ทำงานออกจากปลายโดยตัด

789
00:39:46,948 --> 00:39:48,330
รอบด้านบนของตาราง

790
00:39:48,330 --> 00:39:50,530
ดังนั้นนี่เป็นเพียงมาก
ฟังก์ชันแฮชที่เรียบง่าย

791
00:39:50,530 --> 00:39:56,570
สิ่งที่ไม่ได้ใช้เป็นครั้งแรก
สิ่งที่ตัวอักษรของการป้อนข้อมูลของเราคือ

792
00:39:56,570 --> 00:40:01,660
และเปิดที่เป็นดัชนีที่
เราสามารถใส่ลงไปในตารางแฮชของเรา

793
00:40:01,660 --> 00:40:05,450
>> ใช่และอื่น ๆ ที่ผมกล่าวมาก่อน
วิธีการที่เราแก้ปัญหาการชนกัน

794
00:40:05,450 --> 00:40:09,330
ในตารางแฮชของเรามี,
สิ่งที่เราเรียกผูกมัด

795
00:40:09,330 --> 00:40:13,860
ดังนั้นถ้าคุณพยายามที่จะแทรกหลาย
คำที่ขึ้นต้นด้วยสิ่งเดียวกัน

796
00:40:13,860 --> 00:40:16,145
คุณกำลังจะมีค่าแฮหนึ่ง

797
00:40:16,145 --> 00:40:18,770
อะโวคาโดและแอปเปิ้ลถ้าคุณได้
เรียกใช้ผ่านฟังก์ชันแฮชของเรา

798
00:40:18,770 --> 00:40:21,450
จะไปให้คุณ
หมายเลขเดียวกันจำนวน 0

799
00:40:21,450 --> 00:40:24,550
ดังนั้นวิธีการที่เราแก้ปัญหาที่เป็น
ที่เราสามารถจริงชนิดของการเชื่อมโยงพวกเขา

800
00:40:24,550 --> 00:40:27,010
ร่วมกันผ่านทางรายการที่เชื่อมโยง

801
00:40:27,010 --> 00:40:29,600
>> และในแง่นี้
พวกคุณสามารถดูชนิด

802
00:40:29,600 --> 00:40:32,640
ของวิธีการที่โครงสร้างข้อมูล
เราได้รับการตั้งค่าก่อนหน้านี้

803
00:40:32,640 --> 00:40:35,870
เช่นเดียวกับชนิดรายการลูกเกดเชื่อมโยง
ของสามารถมาร่วมกันเป็นหนึ่ง

804
00:40:35,870 --> 00:40:38,860
และจากนั้นคุณสามารถสร้างให้ห่างไกล
โครงสร้างข้อมูลที่มีประสิทธิภาพมากขึ้น

805
00:40:38,860 --> 00:40:43,350
ที่สามารถจัดการกับจำนวนเงินขนาดใหญ่ของ
ข้อมูลแบบไดนามิกที่ปรับขนาดขึ้นอยู่กับ

806
00:40:43,350 --> 00:40:44,870
ความต้องการของคุณ

807
00:40:44,870 --> 00:40:45,620
ทุกคนชัดเจน?

808
00:40:45,620 --> 00:40:47,580
ชนิดของทุกคนที่ชัดเจน
กับสิ่งที่เกิดขึ้นที่นี่?

809
00:40:47,580 --> 00:40:52,110
>> ถ้าผมอยากจะ insert-- สิ่งที่เป็น
ผลไม้ที่เริ่มต้นด้วยผมไม่ทราบว่า

810
00:40:52,110 --> 00:40:54,726
B, อื่น ๆ นอกเหนือจากเบอร์รี่กล้วย

811
00:40:54,726 --> 00:40:55,710
>> ผู้ชม: Blackberry

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: BlackBerry, ผลไม้ชนิดหนึ่ง

813
00:40:57,910 --> 00:41:00,530
ผลไม้ชนิดไหนไปที่นี่?

814
00:41:00,530 --> 00:41:04,251
ดีเราจริงไม่ได้เรียง
นี้ แต่ในทางทฤษฎี

815
00:41:04,251 --> 00:41:06,250
ถ้าเราต้องการที่จะมีนี้
ตามลำดับตัวอักษร

816
00:41:06,250 --> 00:41:07,944
ผลไม้ชนิดหนึ่งที่ควรจะไป?

817
00:41:07,944 --> 00:41:09,210
>> ผู้ชม: [ไม่ได้ยิน]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: ว่าหลังจากที่นี่ใช่มั้ย?

819
00:41:11,100 --> 00:41:14,950
แต่เนื่องจากมันเป็นเรื่องยากมากที่จะ
reorder-- ผมคิดว่ามันขึ้นอยู่กับพวกคุณ

820
00:41:14,950 --> 00:41:17,920
พวกคุณทั้งหมดสามารถ
ใช้สิ่งที่คุณต้องการ

821
00:41:17,920 --> 00:41:20,730
วิธีที่มีประสิทธิภาพมากขึ้น
การทำเช่นนี้อาจจะเป็น

822
00:41:20,730 --> 00:41:24,570
จะมีการจัดเรียงที่เชื่อมโยง
รายการลงในลำดับตัวอักษร

823
00:41:24,570 --> 00:41:26,520
และอื่น ๆ เมื่อคุณอยู่
ใส่สิ่งที่คุณต้องการ

824
00:41:26,520 --> 00:41:28,632
เพื่อให้แน่ใจว่าพวกเขาจะแทรก
เข้ามาตามลำดับตัวอักษร

825
00:41:28,632 --> 00:41:30,590
เพื่อที่ว่าเมื่อคุณ
พยายามที่จะค้นหาพวกเขา

826
00:41:30,590 --> 00:41:32,410
คุณไม่ได้มีการสำรวจทุกอย่าง

827
00:41:32,410 --> 00:41:35,290
คุณจะรู้ว่าที่
มันเป็นและมันง่าย

828
00:41:35,290 --> 00:41:39,100
>> แต่ถ้าคุณมีชนิดของ
สิ่งที่สลับแบบสุ่ม

829
00:41:39,100 --> 00:41:41,420
คุณยังจะมี
เพื่อสำรวจมันนะ

830
00:41:41,420 --> 00:41:44,990
ดังนั้นถ้าผมต้องการที่จะเพียงแค่
ใส่ผลไม้ชนิดหนึ่งที่นี่

831
00:41:44,990 --> 00:41:47,470
และฉันต้องการที่จะค้นหา
มันฉันรู้ว่าโอ้, BlackBerry

832
00:41:47,470 --> 00:41:52,012
ต้องเริ่มต้นด้วยดัชนีของ 1 ดังนั้นฉัน
รู้ทันทีเพียงค้นหาวันที่ 1

833
00:41:52,012 --> 00:41:53,970
แล้วฉันสามารถชนิดของ
สำรวจรายการที่เชื่อมโยง

834
00:41:53,970 --> 00:41:56,120
จนได้รับการ Blackberry,
และ then-- ใช่?

835
00:41:56,120 --> 00:41:59,550
>> ผู้ชม: ถ้าคุณกำลังพยายามที่จะ create--
ผมคิดเช่นนี้เป็นกัญชาที่ง่ายมาก

836
00:41:59,550 --> 00:42:00,050
ฟังก์ชัน

837
00:42:00,050 --> 00:42:02,835
และถ้าเราอยากจะทำ
หลายชั้นเช่นนั้น

838
00:42:02,835 --> 00:42:05,870
ตกลงเราต้องการที่จะแยกออกเป็น
เช่นเดียวกับตัวอักษรที่เรียงตามตัวอักษร

839
00:42:05,870 --> 00:42:09,040
และหลังจากนั้นอีกจะชอบอีกชุดหนึ่ง
เรียงตามตัวอักษรของตัวอักษรที่อยู่ในนั้น

840
00:42:09,040 --> 00:42:11,715
เราจะวางเช่นกัญชา
ตารางในตารางแฮช

841
00:42:11,715 --> 00:42:13,256
หรือชอบฟังก์ชั่นภายในฟังก์ชั่นหรือไม่?

842
00:42:13,256 --> 00:42:14,880
หรือ that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: ดังนั้นกัญชาของคุณ
function-- ตารางแฮชของคุณ

844
00:42:17,510 --> 00:42:19,360
อาจมีขนาดใหญ่ที่สุดเท่าที่คุณต้องการให้

845
00:42:19,360 --> 00:42:21,930
ดังนั้นในแง่นี้ผมคิดว่า
มันเป็นเรื่องง่ายมาก

846
00:42:21,930 --> 00:42:25,320
ง่ายสำหรับผมที่จะเพียงแค่การจัดเรียงตาม
เกี่ยวกับตัวอักษรของคำแรก

847
00:42:25,320 --> 00:42:28,690
และเพื่อให้มีเพียง 26 ตัวเลือก

848
00:42:28,690 --> 00:42:32,650
ฉันเท่านั้นที่จะได้รับเลือกจาก 26
0-25 เพราะพวกเขาสามารถ

849
00:42:32,650 --> 00:42:36,510
เริ่มต้นจาก A ถึง Z แต่ถ้าคุณต้องการ
เพื่อเพิ่มอาจจะซับซ้อนมากขึ้น

850
00:42:36,510 --> 00:42:39,260
หรือทำงานได้เร็วขึ้นเวลาที่จะของคุณ
ตารางแฮชคุณอย่าง

851
00:42:39,260 --> 00:42:40,760
สามารถทำทุกประเภทของสิ่ง

852
00:42:40,760 --> 00:42:43,330
คุณสามารถทำด้วยตัวเอง
สมการที่ช่วยให้คุณ

853
00:42:43,330 --> 00:42:48,000
มากขึ้นในการจัดจำหน่ายของคุณ
คำแล้วเมื่อคุณค้นหา

854
00:42:48,000 --> 00:42:49,300
มันเป็นไปได้เร็วขึ้น

855
00:42:49,300 --> 00:42:52,100
>> มันทั้งหมดขึ้นอยู่กับพวกคุณ
วิธีที่คุณต้องการที่จะดำเนินการที่

856
00:42:52,100 --> 00:42:55,140
คิดว่ามันเป็นเพียงแค่ถัง

857
00:42:55,140 --> 00:42:57,376
ถ้าผมต้องการที่จะมี
26 ถัง, ฉันจะ

858
00:42:57,376 --> 00:42:59,420
การเรียงลำดับสิ่งที่เป็นถังเหล่านั้น

859
00:42:59,420 --> 00:43:02,980
แต่ฉันจะมีพวง
ของสิ่งที่อยู่ในแต่ละถัง

860
00:43:02,980 --> 00:43:05,890
ดังนั้นหากคุณต้องการที่จะให้มัน
ได้เร็วขึ้นและมีประสิทธิภาพมากขึ้น

861
00:43:05,890 --> 00:43:07,190
ให้ฉันมีร้อยถัง

862
00:43:07,190 --> 00:43:09,290
>> แต่แล้วคุณจะต้องคิดออก
วิธีการเรียงลำดับสิ่งที่เพื่อให้พวกเขา

863
00:43:09,290 --> 00:43:11,040
ในถังที่เหมาะสมที่พวกเขาควรจะอยู่ใน

864
00:43:11,040 --> 00:43:13,331
แต่แล้วเมื่อคุณจริง
ต้องการดูที่ถังนั้น

865
00:43:13,331 --> 00:43:16,410
มันเร็วมากเพราะมี
สิ่งที่น้อยกว่าในถังแต่ละ

866
00:43:16,410 --> 00:43:20,250
ดังนั้นใช่ว่าเป็นจริง
เคล็ดลับสำหรับคุณผู้ชายใน pset5

867
00:43:20,250 --> 00:43:22,360
คือการที่คุณจะ
ความท้าทายที่จะเพียงแค่สร้าง

868
00:43:22,360 --> 00:43:26,170
สิ่งที่มีประสิทธิภาพมากที่สุด
ฟังก์ชั่นที่คุณสามารถคิดที่จะเป็น

869
00:43:26,170 --> 00:43:28,520
สามารถจัดเก็บและตรวจสอบค่าเหล่านี้

870
00:43:28,520 --> 00:43:30,840
>> ทั้งหมดขึ้นอยู่กับพวกคุณ
แต่คุณต้องการที่จะทำมัน

871
00:43:30,840 --> 00:43:32,229
แต่ที่เป็นจุดที่ดีจริงๆ

872
00:43:32,229 --> 00:43:34,520
ชนิดของตรรกะที่คุณ
ต้องการที่จะเริ่มคิดเกี่ยวกับ

873
00:43:34,520 --> 00:43:37,236
คือดีว่าทำไมฉันจึงไม่ทำให้ถังมากขึ้น

874
00:43:37,236 --> 00:43:39,527
แล้วฉันต้องค้นหา
สิ่งที่น้อยแล้วบางทีฉัน

875
00:43:39,527 --> 00:43:41,640
มีฟังก์ชั่นที่แตกต่างกันกัญชา

876
00:43:41,640 --> 00:43:45,500
>> ใช่มีหลายวิธีที่จะทำเช่นนี้
pset บางเร็วกว่าคนอื่น

877
00:43:45,500 --> 00:43:50,630
ฉันจะไปทั้งหมดเพียงแค่ดูว่า
ได้อย่างรวดเร็วเป็นที่เร็วที่สุดที่พวกคุณจะ

878
00:43:50,630 --> 00:43:55,170
จะสามารถที่จะได้รับฟังก์ชั่นการทำงานของคุณ

879
00:43:55,170 --> 00:43:58,176
ตกลงทุกคนที่ดีใน
ผูกมัดและตารางแฮช?

880
00:43:58,176 --> 00:44:00,800
เป็นจริงเหมือนที่ง่ายมาก
แนวคิดถ้าคุณคิดเกี่ยวกับมัน

881
00:44:00,800 --> 00:44:05,160
ทั้งหมดก็คือเป็นสิ่งที่แยก
ปัจจัยการผลิตของคุณลงในถัง

882
00:44:05,160 --> 00:44:10,670
การเรียงลำดับพวกเขาแล้วการค้นหา
แสดงว่ามีการเชื่อมโยงกับ

883
00:44:10,670 --> 00:44:11,852
>> เย็น.

884
00:44:11,852 --> 00:44:18,160
สิทธิทั้งหมดตอนนี้เรามีการจัดเรียงที่แตกต่างกัน
ของโครงสร้างข้อมูลที่เรียกว่าต้นไม้

885
00:44:18,160 --> 00:44:20,850
ลองไปและพยายามพูดคุยเกี่ยวกับ
ซึ่งจะแตกต่างกันอย่างเห็นได้ชัด

886
00:44:20,850 --> 00:44:22,330
แต่ในประเภทเดียวกัน

887
00:44:22,330 --> 00:44:29,010
โดยพื้นฐานแล้วทุกต้นไม้แทน
ในการจัดระเบียบข้อมูลในวิธีการเชิงเส้น

888
00:44:29,010 --> 00:44:32,560
ว่าตารางแฮช does-- คุณ
รู้ว่ามันมีด้านบนและด้านล่าง

889
00:44:32,560 --> 00:44:37,900
และจากนั้นคุณชนิดของการเชื่อมโยงออกจาก it--
ต้นไม้ที่มีด้านบนที่คุณเรียกราก

890
00:44:37,900 --> 00:44:40,220
และจากนั้นก็มีการออกรอบ ๆ ตัวมัน

891
00:44:40,220 --> 00:44:42,390
>> และดังนั้นสิ่งที่คุณได้ที่นี่
เป็นเพียงโหนดบน

892
00:44:42,390 --> 00:44:45,980
ที่ชี้ไปยังโหนดอื่น ๆ ที่จุด
ไปยังต่อมน้ำมากขึ้นและอื่น ๆ และอื่น ๆ

893
00:44:45,980 --> 00:44:48,130
และเพื่อให้คุณเพียงแค่มีสาขาแยก

894
00:44:48,130 --> 00:44:53,255
มันเป็นเพียงวิธีที่แตกต่างในการจัดระเบียบ
ข้อมูลและเพราะเราเรียกมันว่าต้นไม้

895
00:44:53,255 --> 00:44:56,270
พวกคุณ just-- มันเป็นเพียงแค่
รูปแบบออกมาให้มีลักษณะเหมือนต้นไม้

896
00:44:56,270 --> 00:44:57,670
นั่นเป็นเหตุผลที่เราเรียกมันว่าต้นไม้

897
00:44:57,670 --> 00:44:59,370
>> ตารางแฮชดูเหมือนตาราง

898
00:44:59,370 --> 00:45:01,310
ต้นไม้ก็ดูเหมือนต้นไม้

899
00:45:01,310 --> 00:45:03,300
ทั้งหมดก็คือเป็นที่แยกต่างหาก
วิธีการจัดระเบียบของโหนด

900
00:45:03,300 --> 00:45:06,020
ขึ้นอยู่กับความต้องการของคุณ

901
00:45:06,020 --> 00:45:11,810
>> เพื่อให้คุณมีรากและ
แล้วคุณมีใบ

902
00:45:11,810 --> 00:45:15,380
วิธีการที่เราสามารถทำได้โดยเฉพาะอย่างยิ่ง
คิดเกี่ยวกับมันเป็นต้นไม้ไบนารี

903
00:45:15,380 --> 00:45:18,150
ต้นไม้ไบนารีเป็นเพียง
ประเภทที่เฉพาะเจาะจงของต้นไม้

904
00:45:18,150 --> 00:45:22,450
ซึ่งแต่ละโหนดจุดเท่านั้น
ไปที่สูงสุดสองโหนดอื่น ๆ

905
00:45:22,450 --> 00:45:25,434
และเพื่อให้ที่นี่คุณมีที่แตกต่างกัน
สมมาตรในต้นไม้ของคุณ

906
00:45:25,434 --> 00:45:28,600
ที่ทำให้ง่ายต่อการดูชนิดของ
สิ่งที่มีค่าที่คุณอยู่แล้วเพราะคุณ

907
00:45:28,600 --> 00:45:30,150
มีเสมอทางซ้ายหรือขวา

908
00:45:30,150 --> 00:45:33,150
มีไม่เหมือนคนที่สามจากซ้าย
ซ้ายหรือสี่จากซ้าย

909
00:45:33,150 --> 00:45:36,358
มันเป็นเพียงแค่คุณมีด้านซ้ายและขวา
และคุณสามารถค้นหาได้ทั้งของทั้งสอง

910
00:45:36,358 --> 00:45:38,980
และเพื่อเหตุผลนี้เป็นประโยชน์หรือไม่

911
00:45:38,980 --> 00:45:40,980
วิธีที่ว่านี้คือ
ประโยชน์คือถ้าคุณกำลังมองหา

912
00:45:40,980 --> 00:45:42,890
การค้นหาผ่านค่าใช่มั้ย?

913
00:45:42,890 --> 00:45:45,640
แทนที่จะดำเนินการไบนารี
ค้นหาในอาร์เรย์ข้อผิดพลาด

914
00:45:45,640 --> 00:45:49,260
ถ้าคุณต้องการที่จะสามารถที่จะแทรกโหนด
และนำไปโหนดที่จะและยัง

915
00:45:49,260 --> 00:45:52,185
รักษาค้นหา
ขีดความสามารถของการค้นหาแบบไบนารี

916
00:45:52,185 --> 00:45:54,560
ดังนั้นในทางนี้เรากำลังชนิดของ
tricking-- จำได้ว่าเมื่อเรา

917
00:45:54,560 --> 00:45:56,530
กล่าวว่ารายการที่เชื่อมโยงไม่สามารถค้นหา binary?

918
00:45:56,530 --> 00:46:01,700
เรากำลังชนิดของการสร้างโครงสร้างข้อมูล
ว่าเทคนิคที่เข้าทำงาน

919
00:46:01,700 --> 00:46:05,034
>> และอื่น ๆ เพราะรายการที่เชื่อมโยงเป็นเชิงเส้น
พวกเขาเชื่อมโยงเพียงหนึ่งหลังจากที่อื่น ๆ

920
00:46:05,034 --> 00:46:06,950
เราสามารถมีชนิดของ
การจัดเรียงที่แตกต่างกันของตัวชี้

921
00:46:06,950 --> 00:46:09,408
ชี้ไปที่โหนดที่แตกต่างกัน
ที่สามารถช่วยให้เรามีการค้นหา

922
00:46:09,408 --> 00:46:12,590
และอื่น ๆ ที่นี่ถ้าผมต้องการที่จะ
มีต้นไม้ค้นหาไบนารี

923
00:46:12,590 --> 00:46:14,090
ฉันรู้ว่าฉันถ้ากลาง 55

924
00:46:14,090 --> 00:46:18,280
ฉันแค่จะสร้างที่
เป็นกลางของฉันเป็นรากของฉัน

925
00:46:18,280 --> 00:46:20,770
แล้วฉันจะมี
ค่าสปินออกจากมัน

926
00:46:20,770 --> 00:46:25,610
>> ดังนั้นที่นี่ถ้าฉันจะค้นหา
ค่าของ 66 ผมสามารถเริ่มต้นที่ 55

927
00:46:25,610 --> 00:46:27,310
มันเป็น 66 มากกว่า 55?

928
00:46:27,310 --> 00:46:30,970
ใช่มันเป็นดังนั้นฉันรู้ว่าฉัน mus ค้นหา
ฉัน n ตัวชี้ขวาของต้นไม้ต้นนี้

929
00:46:30,970 --> 00:46:32,440
ฉันไปที่ 77

930
00:46:32,440 --> 00:46:35,367
ตกลง 66 น้อยกว่าหรือมากกว่า 77?

931
00:46:35,367 --> 00:46:37,950
มันน้อยกว่าเพื่อให้คุณรู้ว่าโอ้
ที่จะต้องมีโหนดซ้าย

932
00:46:37,950 --> 00:46:41,410
>> และอื่น ๆ ที่นี่เรากำลังชนิดของการรักษา
ทุกสิ่งที่ดีเกี่ยวกับอาร์เรย์

933
00:46:41,410 --> 00:46:44,420
เพื่อต้องการปรับขนาดแบบไดนามิก
ของวัตถุที่เป็น

934
00:46:44,420 --> 00:46:49,530
สามารถแทรกและลบที่จะ,
โดยไม่ต้องกังวลเกี่ยวกับการคงที่

935
00:46:49,530 --> 00:46:50,370
จำนวนของพื้นที่

936
00:46:50,370 --> 00:46:52,820
เรายังคงรักษาทั้งหมดของ
บรรดาสิ่งที่ยอดเยี่ยม

937
00:46:52,820 --> 00:46:57,140
ในขณะที่ยังมีความสามารถในการรักษา
เข้าสู่ระบบและค้นหาเวลาของการค้นหาแบบทวิภาค

938
00:46:57,140 --> 00:47:00,450
ว่าเราเป็นเพียงก่อนหน้านี้
สามารถที่จะได้รับวลี

939
00:47:00,450 --> 00:47:06,310
>> โครงสร้างข้อมูลเย็นชนิดของ
ที่ซับซ้อนในการใช้โหนด

940
00:47:06,310 --> 00:47:08,311
ที่คุณสามารถดูทั้งหมดก็
เป็นโครงสร้างของโหนด

941
00:47:08,311 --> 00:47:10,143
คือการที่คุณมีซ้าย
และตัวชี้ด้านขวา

942
00:47:10,143 --> 00:47:11,044
นั่นคือทั้งหมดที่มันเป็น

943
00:47:11,044 --> 00:47:12,960
ดังนั้นแทนที่จะเป็นเพียง
มี x หรือก่อนหน้า

944
00:47:12,960 --> 00:47:15,920
คุณมีทางซ้ายหรือขวาแล้ว
ชนิดที่คุณสามารถเชื่อมโยงเข้าด้วยกัน

945
00:47:15,920 --> 00:47:16,836
แต่คุณจึงเลือก

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> ตกลงเรากำลังจะเป็นจริง
เพียงแค่ใช้เวลาไม่กี่นาที

948
00:47:24,270 --> 00:47:25,790
ดังนั้นเรากำลังจะไปกลับมาที่นี่

949
00:47:25,790 --> 00:47:28,270
ที่ผมกล่าวว่าก่อนหน้านี้
ชนิดของฉันอธิบาย

950
00:47:28,270 --> 00:47:31,520
ตรรกะที่อยู่เบื้องหลังวิธีการที่เรา
จะค้นหาผ่านทางนี้

951
00:47:31,520 --> 00:47:33,860
เรากำลังจะไปลอง
pseudocoding นี้ออกเพื่อดู

952
00:47:33,860 --> 00:47:38,000
ถ้าเราชนิดสามารถใช้
ตรรกะเดียวกันของการค้นหาแบบไบนารี

953
00:47:38,000 --> 00:47:40,055
จะเป็นชนิดที่แตกต่างกันของโครงสร้างข้อมูล

954
00:47:40,055 --> 00:47:45,049
ถ้าพวกคุณต้องการที่จะใช้เช่นคู่
นาทีที่จะเพียงแค่คิดเกี่ยวกับเรื่องนี้

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
ตกลง.

957
00:48:46,925 --> 00:48:51,407
สิทธิทั้งหมดที่ฉันจะ
จริงเพียงแค่ให้คุณ the-- ไม่มี

958
00:48:51,407 --> 00:48:52,990
เราจะพูดคุยเกี่ยวกับ pseudocode แรก

959
00:48:52,990 --> 00:48:56,580
ดังนั้นไม่มีใครต้องการ
เพื่อให้แทงที่สิ่งที่

960
00:48:56,580 --> 00:49:02,100
สิ่งแรกที่คุณต้องการจะทำอย่างไรเมื่อ
คุณกำลังเริ่มออกค้นหาคืออะไร?

961
00:49:02,100 --> 00:49:04,460
หากเรากำลังมองหา
ค่าของ 66 สิ่งที่

962
00:49:04,460 --> 00:49:07,940
สิ่งแรกที่เราต้องการจะทำอย่างไรถ้า
เราต้องการที่จะค้นหาต้นไม้ไบนารีนี้หรือไม่?

963
00:49:07,940 --> 00:49:10,760
>> ผู้ชม: คุณต้องการที่จะมองขวา
และมองซ้ายและดู [ไม่ได้ยิน]

964
00:49:10,760 --> 00:49:11,230
จำนวนมาก

965
00:49:11,230 --> 00:49:12,271
>> ANDI เป็ง: ใช่ว่า

966
00:49:12,271 --> 00:49:15,350
ดังนั้นคุณจะไปดูที่รากของคุณ

967
00:49:15,350 --> 00:49:18,180
มีหลายวิธีที่คุณสามารถเรียกเป็น
มันผู้ปกครองคนโหนดของคุณบอกว่า

968
00:49:18,180 --> 00:49:21,317
ผมชอบที่จะพูดเพราะราก
ที่เหมือนรากของต้นไม้

969
00:49:21,317 --> 00:49:23,400
คุณกำลังจะไปดูที่
โหนดรากของคุณและคุณ

970
00:49:23,400 --> 00:49:26,940
จะไปดู 66 มากขึ้น
มากกว่าหรือน้อยกว่า 55

971
00:49:26,940 --> 00:49:30,360
และถ้ามันมากกว่าดีก็คือ
มากกว่าที่เราจะต้องการที่จะมอง?

972
00:49:30,360 --> 00:49:32,000
ในกรณีที่เราต้องการค้นหาตอนนี้ใช่มั้ย?

973
00:49:32,000 --> 00:49:34,340
เราต้องการที่จะค้นหา
ครึ่งขวาของต้นไม้ต้นนี้

974
00:49:34,340 --> 00:49:38,390
>> ดังนั้นเราจึงมีสิ่งอำนวยความสะดวกที่
ชี้ที่ชี้ไปทางขวา

975
00:49:38,390 --> 00:49:44,325
และอื่น ๆ แล้วเราสามารถตั้งค่า
รากใหม่ของเราจะเป็น 77

976
00:49:44,325 --> 00:49:46,450
เราก็สามารถไปได้ทุกที่
ตัวชี้ชี้

977
00:49:46,450 --> 00:49:49,100
ดีโอ้นี่เรากำลังเริ่มต้น
ที่ 77 และเราก็สามารถ

978
00:49:49,100 --> 00:49:51,172
ทำเช่นนี้ซ้ำอีกครั้งและอีกครั้ง

979
00:49:51,172 --> 00:49:52,880
ด้วยวิธีนี้คุณชนิด
ของมีฟังก์ชั่น

980
00:49:52,880 --> 00:49:57,430
คุณมีวิธีการค้นหาที่คุณ
ก็สามารถทำซ้ำมากกว่าและเหนือและมากกว่า

981
00:49:57,430 --> 00:50:02,720
ขึ้นอยู่กับที่คุณต้องการดู
จนกว่าคุณจะได้รับในที่สุดค่า

982
00:50:02,720 --> 00:50:04,730
ที่คุณกำลังค้นหา

983
00:50:04,730 --> 00:50:05,230
ความรู้สึกให้?

984
00:50:05,230 --> 00:50:07,800
>> ฉันจะแสดงให้คุณเห็นที่เกิดขึ้นจริง
รหัสและก็มากรหัส

985
00:50:07,800 --> 00:50:08,674
ไม่จำเป็นต้องออกนอกลู่นอกทาง

986
00:50:08,674 --> 00:50:09,910
เราจะพูดคุยผ่านมัน

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> อันที่จริงไม่มี

989
00:50:14,020 --> 00:50:15,061
ที่เป็นเพียง pseudocode

990
00:50:15,061 --> 00:50:17,860
ตกลงที่เป็นเพียง pseudocode ที่
ซึ่งมีความซับซ้อนเล็กน้อย

991
00:50:17,860 --> 00:50:19,751
แต่มันเป็นเรื่องที่ดีโดยสิ้นเชิง

992
00:50:19,751 --> 00:50:21,000
ทุกคนไปพร้อมที่นี่?

993
00:50:21,000 --> 00:50:24,260
หากรากเป็นโมฆะกลับ
เท็จเพราะหมายความว่า

994
00:50:24,260 --> 00:50:26,850
คุณไม่ได้มีอะไรที่มี

995
00:50:26,850 --> 00:50:31,376
>> ถ้า n รากเป็นค่าดังนั้นถ้ามัน
เกิดขึ้นเป็นหนึ่งที่คุณกำลังมองหาที่

996
00:50:31,376 --> 00:50:34,000
แล้วคุณจะกลับจริง
เพราะคุณรู้ว่าคุณจะพบว่า

997
00:50:34,000 --> 00:50:36,250
แต่ถ้าค่าน้อย
กว่ารากของ n คุณ

998
00:50:36,250 --> 00:50:38,332
จะค้นหาทางด้านซ้าย
เด็กหรือใบซ้าย

999
00:50:38,332 --> 00:50:39,540
สิ่งที่คุณต้องการที่จะเรียกว่า

1000
00:50:39,540 --> 00:50:41,750
และถ้ามีค่าเป็นมากกว่าราก
คุณกำลังจะไปค้นหาต้นไม้ที่ถูกต้อง

1001
00:50:41,750 --> 00:50:44,610
จากนั้นเพียงแค่ใช้ฟังก์ชั่น
ผ่านการค้นหาอีกครั้ง

1002
00:50:44,610 --> 00:50:48,037
>> และถ้ารากเป็นโมฆะว่า
หมายความว่าคุณได้มาถึงจุดสิ้นสุดหรือไม่

1003
00:50:48,037 --> 00:50:50,120
ซึ่งหมายความว่าคุณไม่มี
ใบมากขึ้นมากขึ้นในการค้นหา

1004
00:50:50,120 --> 00:50:52,230
แล้วคุณจะรู้ว่าโอ้ฉัน
คิดว่ามันไม่ได้อยู่ในที่นี่

1005
00:50:52,230 --> 00:50:55,063
เพราะหลังจากที่ฉันมองผ่าน
สิ่งที่ทั้งและก็ไม่อยู่ที่นี่

1006
00:50:55,063 --> 00:50:56,930
มันก็อาจจะไม่ได้ที่นี่

1007
00:50:56,930 --> 00:50:58,350
>> ไม่ว่าทำให้ความรู้สึกที่ทุกคน?

1008
00:50:58,350 --> 00:51:03,230
ดังนั้นมันก็เหมือนการค้นหาแบบไบนารีรักษา
ความสามารถของรายการที่เชื่อมโยง

1009
00:51:03,230 --> 00:51:09,200
เย็นและอื่น ๆ ประเภทที่สอง
โครงสร้างข้อมูลของพวกคุณ

1010
00:51:09,200 --> 00:51:13,180
สามารถลองการดำเนินการใน pset ของคุณ
คุณจะต้องเลือกวิธีการอย่างใดอย่างหนึ่ง

1011
00:51:13,180 --> 00:51:19,430
แต่บางทีอาจจะเป็นวิธีทางเลือกที่จะ
ตารางแฮชคือสิ่งที่เราเรียก Trie

1012
00:51:19,430 --> 00:51:24,080
>> ทั้งหมดเป็น Trie เป็น
ประเภทเฉพาะของต้นไม้ที่

1013
00:51:24,080 --> 00:51:28,600
มีค่าที่ไปค่าอื่น ๆ

1014
00:51:28,600 --> 00:51:31,450
ดังนั้นแทนที่จะมีไบนารี
ต้นไม้ในแง่ที่ว่ามีเพียงหนึ่ง

1015
00:51:31,450 --> 00:51:35,940
สิ่งที่สามารถชี้ไปที่สองคุณสามารถมี
จุดสิ่งหนึ่งที่หลายหลายสิ่งหลายอย่าง

1016
00:51:35,940 --> 00:51:39,450
คุณเป็นหลักมีอาร์เรย์
ด้านในของที่คุณเก็บ

1017
00:51:39,450 --> 00:51:41,790
ชี้ที่ชี้ไปยังอาร์เรย์อื่น ๆ

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> ดังนั้นโหนดของวิธีการที่พวกเราทุกคน
จะกำหนด Trie

1020
00:51:49,460 --> 00:51:52,590
คือเราต้องการที่จะมี
บูลีนคำคใช่มั้ย?

1021
00:51:52,590 --> 00:51:54,920
ดังนั้นโหนดเป็นแบบบูล
เหมือนจริงหรือเท็จ

1022
00:51:54,920 --> 00:51:58,490
ครั้งแรกของทั้งหมดที่หัวของ
อาร์เรย์ที่นี้เป็นคำ?

1023
00:51:58,490 --> 00:52:03,620
ประการที่สองคุณต้องการที่จะมีคำแนะนำ
สิ่งที่เหลือของพวกเขา

1024
00:52:03,620 --> 00:52:07,470
ซับซ้อนบิตนามธรรมเล็กน้อย แต่
ผมจะอธิบายสิ่งที่หมายถึงทั้งหมด

1025
00:52:07,470 --> 00:52:13,800
>> ดังนั้นที่นี่ที่ด้านบนถ้าคุณ
มีอาร์เรย์ประกาศแล้ว

1026
00:52:13,800 --> 00:52:17,040
โหนดที่คุณต้องบูล
ค่าที่เก็บไว้ที่ด้านหน้า

1027
00:52:17,040 --> 00:52:19,490
ที่จะบอกคุณคือคำ?

1028
00:52:19,490 --> 00:52:20,520
นี้ไม่ได้เป็นคำ?

1029
00:52:20,520 --> 00:52:23,240
แล้วคุณมี
ส่วนที่เหลือของอาเรย์ที่

1030
00:52:23,240 --> 00:52:26,040
เก็บจริงทั้งหมด
ความเป็นไปได้ของสิ่งที่มันอาจจะเป็น

1031
00:52:26,040 --> 00:52:28,660
ดังนั้นสำหรับตัวอย่างเช่น
ที่ด้านบนที่คุณมี

1032
00:52:28,660 --> 00:52:32,140
สิ่งแรกที่บอกว่าจริงหรือ
เท็จใช่หรือไม่นี่คือคำ

1033
00:52:32,140 --> 00:52:38,130
>> แล้วคุณมี 0 ถึง 26
ตัวอักษรที่คุณสามารถจัดเก็บ

1034
00:52:38,130 --> 00:52:42,790
ถ้าผมต้องการที่จะค้นหาที่นี่
สำหรับค้างคาวผมไปด้านบน

1035
00:52:42,790 --> 00:52:49,200
และฉันมองหาฉันพบบีบีของฉัน
อาร์เรย์และเพื่อให้ฉันรู้ว่าตกลงเป็น B คำ?

1036
00:52:49,200 --> 00:52:53,010
B เป็นคำไม่ได้ดังนั้นจึง
ฉันต้องเก็บการค้นหา

1037
00:52:53,010 --> 00:52:56,410
ฉันไปจาก B และผมมองไปที่
ชี้ที่ชี้ไปทาง B

1038
00:52:56,410 --> 00:53:00,900
และฉันเห็นอาร์เรย์ของข้อมูลอื่น
โครงสร้างเดียวกับที่เราเคยมีมาก่อน

1039
00:53:00,900 --> 00:53:05,240
>> และ here-- โอ้ต่อไป
จดหมาย [ไม่ได้ยิน] เป็นเอ

1040
00:53:05,240 --> 00:53:07,210
ดังนั้นเรามองว่าในอาร์เรย์

1041
00:53:07,210 --> 00:53:10,860
เราหาค่าที่แปด
และจากนั้นเราดูเพื่อดูโอ้

1042
00:53:10,860 --> 00:53:12,840
เดี๋ยวก่อนคือคำที่เป็น B-A คำ?

1043
00:53:12,840 --> 00:53:13,807
มันไม่ได้เป็นคำ

1044
00:53:13,807 --> 00:53:14,890
เราได้มีการให้มอง

1045
00:53:14,890 --> 00:53:17,850
>> และอื่น ๆ แล้วเรามองไปที่
ตัวชี้ของจุดที่

1046
00:53:17,850 --> 00:53:21,130
และชี้ไปทางอื่น
ที่เราได้มูลค่ามากขึ้นเก็บไว้

1047
00:53:21,130 --> 00:53:24,150
และในที่สุดเราได้รับ
B-A-T ซึ่งเป็นคำ

1048
00:53:24,150 --> 00:53:25,970
ดังนั้นในครั้งต่อไป
คุณมองไปที่คุณกำลังจะ

1049
00:53:25,970 --> 00:53:30,850
ที่จะมีการตรวจสอบของใช่ที่
ฟังก์ชั่นบูลีนนี้เป็นความจริง

1050
00:53:30,850 --> 00:53:35,450
และอื่น ๆ ในความรู้สึกเราชนิด
ของการมีต้นไม้ที่มีอาร์เรย์

1051
00:53:35,450 --> 00:53:39,890
>> ดังนั้นแล้วคุณสามารถค้นหาชนิดของลง

1052
00:53:39,890 --> 00:53:43,650
แทนที่จะ hashing ฟังก์ชั่นและ
การกำหนดค่าตามรายการที่เชื่อมโยง

1053
00:53:43,650 --> 00:53:49,190
คุณก็สามารถใช้
Trie ที่ค้นหา downwords

1054
00:53:49,190 --> 00:53:50,850
จริงๆสิ่งที่ซับซ้อนมาก

1055
00:53:50,850 --> 00:53:54,060
ไม่ง่ายที่จะคิดเกี่ยวกับเพราะฉันชอบ
คายโครงสร้างข้อมูลจำนวนมากออก

1056
00:53:54,060 --> 00:53:58,710
ที่คุณ แต่ไม่ทุกคนชนิดของ
เข้าใจว่าตรรกะนี้ทำงานอย่างไร

1057
00:53:58,710 --> 00:54:01,920
>> ตกลงเย็น

1058
00:54:01,920 --> 00:54:05,600
ดังนั้น B-A-T แล้ว
คุณกำลังจะค้นหา

1059
00:54:05,600 --> 00:54:07,940
ครั้งต่อไปที่คุณจะ
เพื่อดูโอ้เดี๋ยวก่อนมันเป็นความจริง

1060
00:54:07,940 --> 00:54:09,273
ทำให้ฉันรู้ว่านี้จะต้องเป็นคำ

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> สิ่งที่เหมือนกันสำหรับสวนสัตว์

1063
00:54:13,770 --> 00:54:17,960
ดังนั้นนี่คือสิ่งที่ตอนนี้ถ้าเรา
ต้องการที่จะค้นหาสวนสัตว์ตอนนี้

1064
00:54:17,960 --> 00:54:20,780
สวนสัตว์ในปัจจุบันไม่ได้เป็น
คำในพจนานุกรมของเรา

1065
00:54:20,780 --> 00:54:25,300
เพราะในขณะที่พวกคุณสามารถดูที่
สถานที่แรกที่เรามีแบบบูล

1066
00:54:25,300 --> 00:54:28,590
กลับจริงคือในตอนท้ายของการซูม

1067
00:54:28,590 --> 00:54:30,430
เรามี Z-O-O-M

1068
00:54:30,430 --> 00:54:33,900
>> และอื่น ๆ ที่นี่เราไม่จริงมี
คำว่าสวนสัตว์ในพจนานุกรมของเรา

1069
00:54:33,900 --> 00:54:36,070
เพราะช่องนี้ไม่ได้ตรวจสอบ

1070
00:54:36,070 --> 00:54:39,540
เพื่อให้คอมพิวเตอร์ไม่ได้
รู้ว่าสวนสัตว์เป็นคำ

1071
00:54:39,540 --> 00:54:42,430
เพราะวิธีการที่เราได้
เก็บไว้เพียงซูมที่นี่

1072
00:54:42,430 --> 00:54:44,920
จริงมีค่าบูลีน
ที่ได้รับการเปิดจริง

1073
00:54:44,920 --> 00:54:49,380
ดังนั้นถ้าเราต้องการที่จะใส่
คำว่าสวนสัตว์ลงไปในพจนานุกรมของเรา

1074
00:54:49,380 --> 00:54:51,770
วิธีการที่เราจะไปเกี่ยวกับการทำเช่นนั้น?

1075
00:54:51,770 --> 00:54:55,960
เราจะต้องทำอะไรเพื่อให้แน่ใจว่าเรา
คอมพิวเตอร์รู้ว่า Z-O-O เป็นคำ

1076
00:54:55,960 --> 00:54:58,130
และไม่ได้เป็นคำแรกคือ Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> ผู้ชม: [ไม่ได้ยิน]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: แน่นอนเรา
ต้องการให้แน่ใจว่านี้

1079
00:55:01,450 --> 00:55:07,890
ที่นี่ที่ค่าบูลีนเป็น
การตรวจสอบออกว่ามันเป็นความจริง

1080
00:55:07,890 --> 00:55:13,297
Z-O-O แล้วเรากำลังจะไปตรวจสอบว่า
เพื่อให้เรารู้ว่าเดี๋ยวก่อนสวนสัตว์เป็นคำ

1081
00:55:13,297 --> 00:55:15,380
ฉันจะบอก
คอมพิวเตอร์ว่ามันเป็นคำพูดเพื่อให้

1082
00:55:15,380 --> 00:55:18,000
ว่าเมื่อตรวจสอบคอมพิวเตอร์
มันรู้ว่าสวนสัตว์เป็นคำ

1083
00:55:18,000 --> 00:55:21,269
>> เพราะจำได้ว่าข้อมูลทั้งหมดเหล่านี้
โครงสร้างมันเป็นเรื่องง่ายมากสำหรับเรา

1084
00:55:21,269 --> 00:55:22,310
ที่จะบอกว่าโอ้ค้างคาวเป็นคำ

1085
00:55:22,310 --> 00:55:22,851
สวนสัตว์เป็นคำ

1086
00:55:22,851 --> 00:55:23,611
ซูมเป็นคำ

1087
00:55:23,611 --> 00:55:25,860
แต่เมื่อคุณกำลังสร้างมัน
คอมพิวเตอร์มีความคิด

1088
00:55:25,860 --> 00:55:28,619
>> ดังนั้นคุณต้องบอกว่า
สิ่งที่จุดนี้คือคำ?

1089
00:55:28,619 --> 00:55:29,910
สิ่งที่จุดที่มันไม่ได้คำ?

1090
00:55:29,910 --> 00:55:31,784
และสิ่งที่จุดที่ฉัน
ต้องค้นหาสิ่งที่

1091
00:55:31,784 --> 00:55:34,000
และสิ่งที่จุดที่ฉันจะต้องไปต่อไปหรือไม่

1092
00:55:34,000 --> 00:55:37,010
ทุกคนที่ชัดเจนว่า?

1093
00:55:37,010 --> 00:55:39,540
เย็น.

1094
00:55:39,540 --> 00:55:42,530
>> และเป็นอย่างนั้นมา
ปัญหาของการที่เราจะ

1095
00:55:42,530 --> 00:55:45,560
ไปเกี่ยวกับการใส่บางสิ่งบางอย่าง
ที่จริงไม่ได้มี?

1096
00:55:45,560 --> 00:55:49,090
ถ้าอย่างนั้นเราก็บอกว่าเราต้องการที่จะใส่
คำอาบน้ำลงไปใน Trie ของเรา

1097
00:55:49,090 --> 00:55:53,589
ในฐานะที่เป็นคนที่คุณสามารถเห็นเหมือนในปัจจุบัน
ทั้งหมดที่เรามีตอนนี้คือ B-A-T,

1098
00:55:53,589 --> 00:55:55,630
และโครงสร้างข้อมูลใหม่นี้
ได้มีไพน์ว่า

1099
00:55:55,630 --> 00:55:59,740
ชี้ไป null เพราะเราถือว่า
ว่าโอ้มีคำหลังจาก B-A-T,

1100
00:55:59,740 --> 00:56:02,530
ทำไมเราต้องให้
มีสิ่งทีหลังจากที่

1101
00:56:02,530 --> 00:56:06,581
>> แต่ปัญหาที่เกิดขึ้นถ้าเราทำคุณ
ต้องการที่จะมีคำที่มาหลังจากที่

1102
00:56:06,581 --> 00:56:07,080
เสื้อของ

1103
00:56:07,080 --> 00:56:09,500
หากคุณมีห้องอาบน้ำที่คุณ
จะต้องการสิทธิ H

1104
00:56:09,500 --> 00:56:13,290
ดังนั้นวิธีที่เรากำลังจะทำว่าเป็น
เรากำลังจะสร้างโหนดแยกต่างหาก

1105
00:56:13,290 --> 00:56:16,840
เราไม่ได้จัดสรรจำนวนเงินใด ๆ ก็ตาม
ของหน่วยความจำสำหรับอาร์เรย์ใหม่นี้

1106
00:56:16,840 --> 00:56:20,720
และเรากำลังจะกำหนดตัวชี้

1107
00:56:20,720 --> 00:56:22,947
>> เรากำลังจะไปกำหนด
H, แรกของทั้งหมด null นี้

1108
00:56:22,947 --> 00:56:24,030
เรากำลังจะได้รับการกำจัด

1109
00:56:24,030 --> 00:56:26,590
เรากำลังจะมี
จุด H ลง

1110
00:56:26,590 --> 00:56:30,600
ถ้าเราเห็น H, เราต้องการ
ที่จะไปที่อื่น

1111
00:56:30,600 --> 00:56:33,910
>> ในที่นี่เราก็จะสามารถตรวจสอบการปิดใช่

1112
00:56:33,910 --> 00:56:38,170
ถ้าเราตีหลังจากที่เอชทีโอ้
แล้วเรารู้ว่านี่คือคำ

1113
00:56:38,170 --> 00:56:41,110
บูลีนเป็นไปเพื่อกลับจริง

1114
00:56:41,110 --> 00:56:42,950
ทุกคนที่ชัดเจนเกี่ยวกับวิธีการที่เกิดขึ้น?

1115
00:56:42,950 --> 00:56:45,110
ตกลง.

1116
00:56:45,110 --> 00:56:47,214
>> เพื่อเป็นหลักทั้งหมด
เหล่านี้โครงสร้างข้อมูล

1117
00:56:47,214 --> 00:56:50,130
ที่เราได้ไปกว่าวันนี้ผมได้
ไปเหนือพวกเขาจริงๆได้อย่างรวดเร็ว

1118
00:56:50,130 --> 00:56:52,192
และไม่อยู่ในมาก
รายละเอียดและที่ตกลง

1119
00:56:52,192 --> 00:56:53,900
เมื่อคุณเริ่ม messing
กับมันคุณจะ

1120
00:56:53,900 --> 00:56:55,733
การติดตามที่
ชี้ทั้งหมดที่มี

1121
00:56:55,733 --> 00:56:58,060
สิ่งที่เกิดขึ้นในของคุณ
โครงสร้างข้อมูลและอื่น ๆ

1122
00:56:58,060 --> 00:56:59,810
พวกเขาจะมีประโยชน์มาก
และมันก็ขึ้นอยู่กับคุณ

1123
00:56:59,810 --> 00:57:03,890
คนที่จะคิดออกว่าทั้งหมด
คุณต้องการที่จะใช้สิ่งที่

1124
00:57:03,890 --> 00:57:07,650
>> และเพื่อให้ pset4 ของ 5-- โอ้ว่าเป็นสิ่งที่ผิด

1125
00:57:07,650 --> 00:57:10,140
Pset5 เป็นคำที่สะกดผิด

1126
00:57:10,140 --> 00:57:13,710
ที่ผมกล่าวว่าก่อนที่คุณจะไปครั้งเดียว
อีกครั้งดาวน์โหลดซอร์สโค้ดจากเรา

1127
00:57:13,710 --> 00:57:16,210
มีจะมีสามหลัก
สิ่งที่คุณจะได้รับการดาวน์โหลด

1128
00:57:16,210 --> 00:57:18,470
คุณจะดาวน์โหลดพจนานุกรม
KERS และตำรา

1129
00:57:18,470 --> 00:57:21,660
>> ทุกสิ่งเหล่านี้จะเป็น
ทั้งพจนานุกรมของคำ

1130
00:57:21,660 --> 00:57:25,190
ที่เราต้องการให้คุณตรวจสอบ
หรือการทดสอบของข้อมูล

1131
00:57:25,190 --> 00:57:26,930
ที่เราต้องการให้คุณตรวจสอบการสะกด

1132
00:57:26,930 --> 00:57:29,670
และเพื่อพจนานุกรม
เราให้คุณจะ

1133
00:57:29,670 --> 00:57:34,870
เพื่อให้คุณมีคำพูดที่เกิดขึ้นจริงที่เราต้องการ
คุณสามารถจัดเก็บอย่างใดในทางที่เป็น

1134
00:57:34,870 --> 00:57:36,530
มีประสิทธิภาพมากขึ้นกว่าอาร์เรย์

1135
00:57:36,530 --> 00:57:38,470
และจากนั้นจะมีข้อความ
จะเป็นสิ่งที่เรากำลัง

1136
00:57:38,470 --> 00:57:43,900
ขอให้คุณตรวจสอบการสะกดเพื่อให้แน่ใจว่า
ทุกคำที่มีคำพูดจริง

1137
00:57:43,900 --> 00:57:47,970
>> และเพื่อให้สามช่วงตึกของ
โปรแกรมที่เราจะให้คุณ

1138
00:57:47,970 --> 00:57:51,130
จะเรียกว่า dictionary.c,
dictionary.h และ speller.c

1139
00:57:51,130 --> 00:57:56,500
และเพื่อ dictionary.c ทั้งหมดไม่เป็น
สิ่งที่คุณกำลังขอให้ดำเนินการ

1140
00:57:56,500 --> 00:57:57,880
โหลดคำ

1141
00:57:57,880 --> 00:58:02,000
มันสะกดตรวจสอบพวกเขาและมันจะทำให้แน่ใจว่า
ทุกอย่างที่ใส่อย่างถูกต้อง

1142
00:58:02,000 --> 00:58:05,180
>> diction.h เป็นเพียงไฟล์ไลบรารี
ฟังก์ชั่นที่บอกทุกคน

1143
00:58:05,180 --> 00:58:07,650
และ speller.c เรากำลังจะให้คุณ

1144
00:58:07,650 --> 00:58:09,290
คุณไม่จำเป็นต้องปรับเปลี่ยนใด ๆ ของมัน

1145
00:58:09,290 --> 00:58:14,290
speller.c ทั้งหมดไม่สามารถใช้เวลาที่
โหลดมันจะตรวจสอบความเร็วของมัน

1146
00:58:14,290 --> 00:58:19,190
การทดสอบมาตรฐานเช่นวิธีการที่
ได้อย่างรวดเร็วคุณสามารถที่จะทำในสิ่งที่

1147
00:58:19,190 --> 00:58:20,410
>> มันสะกด

1148
00:58:20,410 --> 00:58:23,920
เพียงแค่จะไม่ยุ่งกับมัน แต่ให้
แน่ใจว่าคุณเข้าใจสิ่งที่มันทำ

1149
00:58:23,920 --> 00:58:28,090
เราใช้ฟังก์ชั่นที่เรียกว่า getrusage ว่า
การทดสอบประสิทธิภาพของการสะกดคำของคุณ

1150
00:58:28,090 --> 00:58:28,590
ตรวจสอบ

1151
00:58:28,590 --> 00:58:32,200
ทั้งหมดก็จะเป็นพื้นทดสอบ
ช่วงเวลาของทุกอย่างในพจนานุกรมของคุณ

1152
00:58:32,200 --> 00:58:33,680
เพื่อให้แน่ใจว่าคุณเข้าใจมัน

1153
00:58:33,680 --> 00:58:36,660
โปรดใช้ความระมัดระวังที่จะไม่ยุ่งกับมันหรือ
สิ่งอื่นที่จะไม่ทำงานอย่างถูกต้อง

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> และเป็นกลุ่มของความท้าทายนี้เป็น
พวกคุณที่จะปรับเปลี่ยนจริงๆ dictionary.c

1156
00:58:44,170 --> 00:58:48,526
เราจะให้คุณ
140,000 คำในพจนานุกรม

1157
00:58:48,526 --> 00:58:50,900
เราจะให้คุณข้อความ
แฟ้มที่มีคำพูดเหล่านั้น

1158
00:58:50,900 --> 00:58:54,840
และเราต้องการให้คุณสามารถจัดระเบียบ
พวกเขาเข้าไปในตารางแฮชหรือ Trie

1159
00:58:54,840 --> 00:58:58,140
เพราะเมื่อเราขอให้คุณสะกด
check-- คิดว่าคุณกำลังสะกด

1160
00:58:58,140 --> 00:59:00,690
การตรวจสอบเช่นเดียวกับโอดิสซีของโฮเมอร์

1161
00:59:00,690 --> 00:59:03,010
มันเป็นเช่นนี้มากการทดสอบขนาดใหญ่

1162
00:59:03,010 --> 00:59:05,190
>> ลองคิดดูหากทุกเดียว
คำที่คุณต้องมอง

1163
00:59:05,190 --> 00:59:08,100
ผ่านแถว 140,000 ค่านิยม

1164
00:59:08,100 --> 00:59:10,350
ที่จะใช้ตลอดไป
สำหรับเครื่องของคุณทำงาน

1165
00:59:10,350 --> 00:59:14,490
นั่นคือเหตุผลที่เราต้องการที่จะจัดระเบียบของเรา
ข้อมูลลงในโครงสร้างข้อมูลที่มีประสิทธิภาพมากขึ้น

1166
00:59:14,490 --> 00:59:17,270
เช่นตารางแฮชหรือ Trie

1167
00:59:17,270 --> 00:59:20,700
และแล้วพวกคุณชนิดสามารถ
เมื่อคุณเข้าถึงค้นหา

1168
00:59:20,700 --> 00:59:22,570
สิ่งที่มากขึ้นได้อย่างง่ายดายและรวดเร็วยิ่งขึ้น

1169
00:59:22,570 --> 00:59:24,934
>> และเพื่อให้ระมัดระวังในการแก้ปัญหาการชนกัน

1170
00:59:24,934 --> 00:59:27,350
คุณกำลังจะได้รับพวง
คำพูดของการเริ่มต้นกับเอว่า

1171
00:59:27,350 --> 00:59:29,957
คุณจะได้รับพวงคำ
ที่เริ่มต้นด้วยบีขึ้นอยู่กับคุณ

1172
00:59:29,957 --> 00:59:31,290
คนวิธีที่คุณต้องการที่จะแก้ปัญหาได้

1173
00:59:31,290 --> 00:59:34,144
บางทีอาจจะมีมากขึ้น
ฟังก์ชันแฮชที่มีประสิทธิภาพ

1174
00:59:34,144 --> 00:59:36,810
มากกว่าเพียงแค่ตัวอักษรตัวแรกของ
บางสิ่งบางอย่างและอื่น ๆ ที่ขึ้นอยู่กับคุณ

1175
00:59:36,810 --> 00:59:38,190
ผู้ชายกับชนิดของการทำสิ่งที่คุณต้องการ

1176
00:59:38,190 --> 00:59:40,148
>> บางทีคุณอาจต้องการที่จะเพิ่ม
ตัวอักษรทั้งหมดเข้าด้วยกัน

1177
00:59:40,148 --> 00:59:43,410
บางทีคุณอาจต้องการที่จะชอบทำสิ่งที่แปลก
บัญชีจำนวนตัวอักษรที่

1178
00:59:43,410 --> 00:59:43,970
อะไรก็ตาม

1179
00:59:43,970 --> 00:59:45,386
ขึ้นอยู่กับพวกคุณว่าคุณต้องการที่จะทำ

1180
00:59:45,386 --> 00:59:49,262
หากคุณต้องการที่จะทำตารางแฮชถ้าคุณ
ต้องการที่จะลอง Trie ที่ทั้งหมดขึ้นอยู่กับคุณ

1181
00:59:49,262 --> 00:59:52,470
ฉันจะเตือนคุณก่อนเวลาว่า
Trie ปกติจะเป็นบิตยากขึ้น

1182
00:59:52,470 --> 00:59:54,520
เพียงเพราะมีจำนวนมาก
คำแนะนำเพิ่มเติมในการติดตาม

1183
00:59:54,520 --> 00:59:55,645
แต่ทั้งหมดขึ้นอยู่กับพวกคุณ

1184
00:59:55,645 --> 00:59:58,742
มันไกลมีประสิทธิภาพมากขึ้น
ในกรณีส่วนใหญ่

1185
00:59:58,742 --> 01:00:01,450
คุณต้องการที่จะจริงๆจะสามารถที่จะให้
ติดตามทั้งหมดของตัวชี้ของคุณ

1186
01:00:01,450 --> 01:00:03,850
ชอบทำสิ่งเดียวกัน
ว่าฉันกำลังทำอะไรที่นี่

1187
01:00:03,850 --> 01:00:06,871
เมื่อคุณกำลังพยายามที่จะแทรก
ค่าลงในตารางแฮชหรือลบ

1188
01:00:06,871 --> 01:00:08,620
ตรวจสอบให้แน่ใจว่าคุณ
จริงๆการติดตาม

1189
01:00:08,620 --> 01:00:11,860
ของที่ทุกอย่างเป็นเพราะ
มันเป็นเรื่องง่ายถ้าฉัน

1190
01:00:11,860 --> 01:00:14,727
พยายามที่จะแทรกเช่นคำว่าแอนดี้

1191
01:00:14,727 --> 01:00:16,810
ขอเพียงบอกว่าเป็น
คำจริงคำว่าแอนดี้,

1192
01:00:16,810 --> 01:00:19,640
เป็นรายการยักษ์ของคำ

1193
01:00:19,640 --> 01:00:22,450
>> ถ้าฉันเพิ่งเกิดขึ้นกำหนด
ผิดตัวชี้โอ๊ะ

1194
01:00:22,450 --> 01:00:24,940
ไปมีความสมบูรณ์ของ
ส่วนที่เหลือของรายการที่เชื่อมโยงของฉัน

1195
01:00:24,940 --> 01:00:26,897
ตอนนี้คำเดียวที่ฉัน
มีคือแอนดี้และตอนนี้

1196
01:00:26,897 --> 01:00:29,230
ทั้งหมดของคำอื่น ๆ ใน
พจนานุกรมที่ได้รับการสูญเสีย

1197
01:00:29,230 --> 01:00:31,370
และเพื่อให้คุณต้องการที่จะให้แน่ใจว่าคุณ
ติดตามทั้งหมดของตัวชี้ของคุณ

1198
01:00:31,370 --> 01:00:33,661
หรืออื่น ๆ ที่คุณกำลังจะได้รับ
ปัญหาใหญ่ในรหัสของคุณ

1199
01:00:33,661 --> 01:00:35,840
วาดสิ่งที่ออกอย่างระมัดระวังทีละขั้นตอน

1200
01:00:35,840 --> 01:00:37,870
มันทำให้มันง่ายมากที่จะคิดว่า

1201
01:00:37,870 --> 01:00:40,910
>> และสุดท้ายคุณต้องการที่จะสามารถที่จะ
ทดสอบประสิทธิภาพของคุณโปรแกรมของคุณ

1202
01:00:40,910 --> 01:00:41,618
บนกระดานใหญ่

1203
01:00:41,618 --> 01:00:43,710
ถ้าพวกคุณใช้
ดู CS50 ในขณะนี้

1204
01:00:43,710 --> 01:00:45,210
เรามีสิ่งที่เรียกว่าคณะกรรมการใหญ่

1205
01:00:45,210 --> 01:00:50,200
มันเป็นแผ่นคะแนนได้เร็วที่สุด
ตรวจสอบการสะกดครั้งในทุก CS50

1206
01:00:50,200 --> 01:00:55,720
ตอนนี้ผมคิดว่าด้านบนเช่น 10
ครั้งผมคิดว่าแปดของพวกเขาเป็นพนักงาน

1207
01:00:55,720 --> 01:00:57,960
จริงๆเราต้องการพวกคุณที่จะชนะเรา

1208
01:00:57,960 --> 01:01:00,870
>> ทั้งหมดของเรากำลังพยายามที่จะดำเนินการ
รหัสที่เร็วที่สุดเท่าที่จะทำได้

1209
01:01:00,870 --> 01:01:04,880
เราต้องการให้พวกคุณจะพยายามที่จะท้าทาย
เราและดำเนินการได้เร็วกว่าที่เราทุกคน

1210
01:01:04,880 --> 01:01:05,550
สามารถ.

1211
01:01:05,550 --> 01:01:07,970
ดังนั้นนี้เป็นจริง
ครั้งแรกที่เรา

1212
01:01:07,970 --> 01:01:12,680
ขอให้พวกคุณจะทำ pset ที่
จริงๆคุณสามารถทำในสิ่งที่วิธีการ

1213
01:01:12,680 --> 01:01:13,760
คุณต้องการ.

1214
01:01:13,760 --> 01:01:17,730
>> ฉันมักจะบอกนี้เป็นมากขึ้นคล้าย
เพื่อการแก้ปัญหาในชีวิตจริงใช่มั้ย?

1215
01:01:17,730 --> 01:01:19,550
ผมบอกว่าเดี๋ยวก่อนฉันต้องการให้คุณทำเช่นนี้

1216
01:01:19,550 --> 01:01:21,380
สร้างโปรแกรมที่ไม่นี้สำหรับฉัน

1217
01:01:21,380 --> 01:01:22,630
มันทำ แต่คุณต้องการ

1218
01:01:22,630 --> 01:01:24,271
ผมเพิ่งรู้ว่าที่ฉันต้องการได้อย่างรวดเร็ว

1219
01:01:24,271 --> 01:01:25,770
นั่นคือความท้าทายของคุณในสัปดาห์นี้

1220
01:01:25,770 --> 01:01:27,531
พวกคุณที่เรากำลังจะ
เพื่อให้คุณได้งาน

1221
01:01:27,531 --> 01:01:29,030
เราจะให้คุณท้าทาย

1222
01:01:29,030 --> 01:01:31,559
และจากนั้นก็ขึ้นอยู่กับพวกคุณ
ที่จะสมบูรณ์คิดเพียงแค่ออก

1223
01:01:31,559 --> 01:01:34,100
สิ่งที่เร็วที่สุดและมากที่สุด
วิธีที่มีประสิทธิภาพในการดำเนินการนี​​้

1224
01:01:34,100 --> 01:01:34,600
ใช่?

1225
01:01:34,600 --> 01:01:37,476
>> ผู้ชม: พวกเราจะได้รับอนุญาตให้ถ้า
ต้องการเพื่อการวิจัยวิธีการได้เร็วขึ้น

1226
01:01:37,476 --> 01:01:40,821
ที่จะทำตารางแฮชออนไลน์ที่เราสามารถทำได้
และกล่าวถึงรหัสของคนอื่น?

1227
01:01:40,821 --> 01:01:42,070
ANDI เป็ง: ใช่ดีทั้งหมด

1228
01:01:42,070 --> 01:01:44,320
ดังนั้นถ้าพวกคุณอ่าน
ข้อมูลจำเพาะมีเส้น

1229
01:01:44,320 --> 01:01:48,310
ในสเปคที่ระบุว่าพวกคุณ
เป็นบริการฟรีเพื่อการวิจัยกัญชา

1230
01:01:48,310 --> 01:01:51,070
ฟังก์ชั่นในสิ่งที่บางส่วน
ของฟังก์ชันแฮชได้เร็วขึ้น

1231
01:01:51,070 --> 01:01:54,720
เพื่อให้ทำงานได้เป็นสิ่งที่ผ่าน
ตราบใดที่คุณอ้างว่ารหัส

1232
01:01:54,720 --> 01:01:57,220
ดังนั้นบางคนมีอยู่แล้ว
คิดออกวิธีการได้อย่างรวดเร็ว

1233
01:01:57,220 --> 01:02:00,250
ในการดำเนินการตรวจสอบการสะกดคำของอย่างรวดเร็ว
วิธีการในการเก็บข้อมูล

1234
01:02:00,250 --> 01:02:02,750
ทั้งหมดขึ้นอยู่กับพวกคุณถ้าคุณ
ต้องการเพียงแค่ใช้เวลาที่ใช่มั้ย?

1235
01:02:02,750 --> 01:02:04,045
ให้แน่ใจว่าคุณกำลังอ้างถึง

1236
01:02:04,045 --> 01:02:06,170
ความท้าทายที่นี่จริงๆ
ที่เรากำลังพยายามที่จะทดสอบ

1237
01:02:06,170 --> 01:02:09,750
คือการทำให้แน่ใจว่าคุณรู้ว่า
ทางของรอบตัวชี้

1238
01:02:09,750 --> 01:02:12,700
เท่าที่คุณดำเนินการ
ฟังก์ชั่นแฮชที่เกิดขึ้นจริง

1239
01:02:12,700 --> 01:02:15,070
และขึ้นมาพร้อมกับเช่น
ทางคณิตศาสตร์ที่จะทำอย่างนั้น

1240
01:02:15,070 --> 01:02:17,570
พวกคุณสามารถวิจัยสิ่งที่
วิธีการออนไลน์ที่พวกคุณต้องการ

1241
01:02:17,570 --> 01:02:17,996
ใช่?

1242
01:02:17,996 --> 01:02:19,700
>> ผู้ชม: เราสามารถกล่าวถึงเพียง
โดยใช้ [ไม่ได้ยิน]

1243
01:02:19,700 --> 01:02:20,120
>> ANDI เป็ง: ใช่

1244
01:02:20,120 --> 01:02:22,328
คุณสามารถเพียงแค่ในความคิดเห็นของคุณ
คุณสามารถอ้างเช่นโอ้

1245
01:02:22,328 --> 01:02:26,127
ที่นำมาจากญาดา, ญาดา,
ญาดา, ฟังก์ชันแฮช

1246
01:02:26,127 --> 01:02:27,210
ใครมีคำถามหรือข้อสงสัย

1247
01:02:27,210 --> 01:02:29,694
เราแวะจริง
ผ่านส่วนในวันนี้

1248
01:02:29,694 --> 01:02:31,610
ผมจะขึ้นที่นี่เพื่อ
ตอบคำถามได้เป็นอย่างดี

1249
01:02:31,610 --> 01:02:36,570
>> นอกจากนี้ที่ผมกล่าวว่าสำนักงาน
ชั่วโมงในคืนนี้และวันพรุ่งนี้

1250
01:02:36,570 --> 01:02:40,307
ข้อมูลจำเพาะในสัปดาห์นี้เป็นจริง
ซุปเปอร์ที่ง่ายและสั้นสุดที่จะอ่าน

1251
01:02:40,307 --> 01:02:43,140
ผมจะแนะนำการดูเพียง
อ่านทั้งหมดของมัน

1252
01:02:43,140 --> 01:02:45,730
>> และ Zamyla จริงคุณเดิน
ผ่านแต่ละฟังก์ชั่น

1253
01:02:45,730 --> 01:02:49,796
คุณจำเป็นต้องใช้และเพื่อให้มันเป็น
มากชัดเจนว่าจะทำทุกอย่าง

1254
01:02:49,796 --> 01:02:51,920
เพียงเพื่อให้แน่ใจว่าคุณ
ติดตามความเคลื่อนไหวของตัวชี้

1255
01:02:51,920 --> 01:02:53,650
นี้เป็น pset ที่ท้าทายมาก

1256
01:02:53,650 --> 01:02:56,744
>> มันไม่ได้เป็นสิ่งที่ท้าทายเพราะชอบ
โอ้แนวคิดที่มีมากขึ้น

1257
01:02:56,744 --> 01:02:59,160
ยากหรือคุณต้องเรียนรู้
ไวยากรณ์ใหม่มากทาง

1258
01:02:59,160 --> 01:03:00,650
ที่คุณไม่สำหรับ pset ที่ผ่านมา

1259
01:03:00,650 --> 01:03:03,320
pset นี้เป็นเรื่องยากเพราะ
มีคำแนะนำมากมาย

1260
01:03:03,320 --> 01:03:06,980
และแล้วก็มากง่ายมากที่จะครั้งเดียว
คุณมีข้อผิดพลาดในรหัสของคุณจะไม่สามารถ

1261
01:03:06,980 --> 01:03:08,315
ที่จะหาข้อผิดพลาดที่เป็น

1262
01:03:08,315 --> 01:03:13,200
>> และมีความสมบูรณ์มากและความเชื่อมั่นในตัวคุณที่สุด
คนที่จะสามารถที่จะชนะเรา [ไม่ได้ยิน]

1263
01:03:13,200 --> 01:03:13,700
การสะกดคำ

1264
01:03:13,700 --> 01:03:16,640
ที่จริงผมไม่ได้เขียนใด ๆ เหมือง
แต่ฉันจะเขียนเหมือง

1265
01:03:16,640 --> 01:03:19,070
ดังนั้นในขณะที่คุณกำลังเขียน
คุณผมจะเขียนเหมือง

1266
01:03:19,070 --> 01:03:21,070
ฉันจะพยายามที่จะทำให้
เหมืองเร็วกว่าคุณ

1267
01:03:21,070 --> 01:03:23,940
เราจะดูว่าใครมีหนึ่งที่เร็วที่สุด

1268
01:03:23,940 --> 01:03:27,340
>> และใช่ฉันจะดูทั้งหมดของ
พวกคุณที่นี่ในวันอังคาร

1269
01:03:27,340 --> 01:03:29,510
ฉันจะทำงานชนิดเช่นการประชุมเชิงปฏิบัติการ pset ได้

1270
01:03:29,510 --> 01:03:32,640
ทั้งหมดในส่วนนี้
สัปดาห์การประชุมเชิงปฏิบัติการ pset,

1271
01:03:32,640 --> 01:03:36,690
เพื่อให้คุณผู้ชายที่มีจำนวนมากของโอกาส
เพื่อขอความช่วยเหลือเวลาทำงานเช่นเคย

1272
01:03:36,690 --> 01:03:41,330
และผมหวังว่าจะได้
อ่านทั้งหมดของรหัสพวกคุณ

1273
01:03:41,330 --> 01:03:44,160
ฉันมีแบบทดสอบได้ที่นี่ถ้าคุณ
คนต้องการที่จะมารับเหล่านั้น

1274
01:03:44,160 --> 01:03:45,880
นั่นคือทั้งหมดที่

1275
01:03:45,880 --> 01:03:48,180