1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> ลำโพง 1: ทั้งหมดขวาดังนั้นเราจะกลับมา

3
00:00:13,120 --> 00:00:14,480
ยินดีต้อนรับสู่ CS50

4
00:00:14,480 --> 00:00:16,510
นี่คือจุดสิ้นสุดของสัปดาห์ที่เจ็ด

5
00:00:16,510 --> 00:00:20,200
ดังนั้นจำได้ว่าครั้งสุดท้ายที่เราเริ่มต้น
กำลังมองหาที่ซับซ้อนมากขึ้นเล็กน้อย

6
00:00:20,200 --> 00:00:21,100
โครงสร้างข้อมูล

7
00:00:21,100 --> 00:00:25,110
ตั้งแต่จนถึงขณะนี้เรามีทั้งหมดจริงๆ
ในการกำจัดของเรานี้เป็นอาร์เรย์

8
00:00:25,110 --> 00:00:29,340
>> แต่ก่อนที่เราทิ้งแถวที่จะไม่
ทั้งหมดที่น่าสนใจซึ่งแน่นอนมัน

9
00:00:29,340 --> 00:00:33,570
จริงเป็นสิ่งที่บางส่วนของที่มี
pluses ของข้อมูลที่เรียบง่ายนี้

10
00:00:33,570 --> 00:00:34,560
โครงสร้างป่านนี้?

11
00:00:34,560 --> 00:00:36,110
ดีที่มันคืออะไร?

12
00:00:36,110 --> 00:00:39,450
เท่าที่เราเคยเห็น?

13
00:00:39,450 --> 00:00:42,540
คุณทำอะไรได้?

14
00:00:42,540 --> 00:00:44,028
ไม่มีอะไร

15
00:00:44,028 --> 00:00:45,020
>> ลูกศิษย์: [ได้ยิน]

16
00:00:45,020 --> 00:00:45,395
>> 1 SPEAKER: อะไรที่?

17
00:00:45,395 --> 00:00:46,410
>> ลูกศิษย์: [ได้ยิน]

18
00:00:46,410 --> 00:00:47,000
>> 1 ลำโพงขนาดคงที่

19
00:00:47,000 --> 00:00:51,260
OK เพื่อให้ขนาดคงที่คือเหตุผลที่ดีแม้ว่า?

20
00:00:51,260 --> 00:00:53,180
>> ลูกศิษย์: [ได้ยิน]

21
00:00:53,180 --> 00:00:56,240
>> ลำโพง 1: ตกลงดังนั้นจึงมีประสิทธิภาพในการ
ความรู้สึกที่ว่าคุณสามารถจัดสรร

22
00:00:56,240 --> 00:01:00,070
จำนวนคงที่ของพื้นที่ซึ่งหวังว่า
เป็นอย่างแม่นยำเท่า

23
00:01:00,070 --> 00:01:01,180
พื้นที่เท่าที่คุณต้องการ

24
00:01:01,180 --> 00:01:02,720
เพื่อที่ว่าอาจจะเป็นบวกอย่างแน่นอน

25
00:01:02,720 --> 00:01:06,530
>> อีกด้านขึ้นของอาร์เรย์คืออะไร?

26
00:01:06,530 --> 00:01:07,610
อ้าง?

27
00:01:07,610 --> 00:01:08,750
>> ลูกศิษย์: [ได้ยิน]

28
00:01:08,750 --> 00:01:09,550
>> ลำโพง 1: ทั้งหมด - เสียใจ?

29
00:01:09,550 --> 00:01:11,270
>> ลูกศิษย์: [ได้ยิน]

30
00:01:11,270 --> 00:01:13,620
>> 1 SPEAKER: ทั้งหมดในกล่องสี่เหลี่ยมในหน่วยความจำ
หรือถัดจากแต่ละอื่น ๆ

31
00:01:13,620 --> 00:01:15,220
และที่เป็นประโยชน์ - เพราะเหตุใด

32
00:01:15,220 --> 00:01:15,970
ที่จริงค่อนข้าง

33
00:01:15,970 --> 00:01:18,611
แต่วิธีการที่เราสามารถใช้ประโยชน์จากความจริงที่ว่า?

34
00:01:18,611 --> 00:01:21,500
>> ลูกศิษย์: [ได้ยิน]

35
00:01:21,500 --> 00:01:24,490
>> 1 ลำโพงว่าเราสามารถติดตาม
ที่ทุกอย่างเป็นเพียงโดยรู้

36
00:01:24,490 --> 00:01:28,560
หนึ่งที่อยู่คือที่อยู่ของ
ไบต์แรกของหน่วยความจำอันว่า

37
00:01:28,560 --> 00:01:30,420
หรือในกรณีของสตริง,
ที่อยู่ของแรก

38
00:01:30,420 --> 00:01:31,460
ถ่านในสตริงที่

39
00:01:31,460 --> 00:01:33,330
และจากนั้นเราสามารถหา
จุดสิ้นสุดของสตริง

40
00:01:33,330 --> 00:01:35,710
เราสามารถหาองค์ประกอบที่สอง,
องค์ประกอบที่สามและอื่น ๆ

41
00:01:35,710 --> 00:01:38,740
>> และดังนั้นวิธีที่จินตนาการในการอธิบายว่า
คุณลักษณะคืออาร์เรย์ให้เรา

42
00:01:38,740 --> 00:01:40,020
เข้าถึงโดยสุ่ม

43
00:01:40,020 --> 00:01:44,330
โดยใช้เพียงแค่วงเล็บเหลี่ยม
สัญกรณ์และจำนวนคุณสามารถข้ามไปยัง

44
00:01:44,330 --> 00:01:48,070
องค์ประกอบเฉพาะในอาร์เรย์
ในช่วงเวลาคงที่, O ใหญ่

45
00:01:48,070 --> 00:01:49,810
หนึ่งเพื่อที่จะพูด

46
00:01:49,810 --> 00:01:51,080
>> แต่มีข้อเสียบางอย่างที่รับ

47
00:01:51,080 --> 00:01:53,110
อะไรอาร์เรย์ได้ทำมากได้อย่างง่ายดาย?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
มันเป็นสิ่งที่ไม่ดีที่?

50
00:01:57,170 --> 00:01:58,810
>> ลูกศิษย์: [ได้ยิน]

51
00:01:58,810 --> 00:01:59,860
>> 1 SPEAKER: อะไรที่?

52
00:01:59,860 --> 00:02:00,530
>> ลูกศิษย์: [ได้ยิน]

53
00:02:00,530 --> 00:02:01,460
>> 1 ลำโพงขยายขนาด

54
00:02:01,460 --> 00:02:04,800
ดังนั้นข้อเสียของอาร์เรย์เป็น
ได้อย่างแม่นยำตรงข้ามของสิ่ง

55
00:02:04,800 --> 00:02:05,540
upsides เป็น

56
00:02:05,540 --> 00:02:07,610
ดังนั้นหนึ่งในข้อเสียคือ
ว่ามันเป็นขนาดคงที่

57
00:02:07,610 --> 00:02:09,400
ดังนั้นคุณไม่สามารถจริงๆมันเติบโต

58
00:02:09,400 --> 00:02:13,510
คุณสามารถจัดสรรก้อนใหญ่
หน่วยความจำและจากนั้นย้ายองค์ประกอบเก่า

59
00:02:13,510 --> 00:02:14,460
เข้าแถวใหม่

60
00:02:14,460 --> 00:02:18,060
แล้วฟรีอาร์เรย์เก่าสำหรับ
ตัวอย่างเช่นโดยการใช้ malloc หรือคล้ายกัน

61
00:02:18,060 --> 00:02:21,180
ฟังก์ชันที่เรียกว่า realloc ซึ่ง
หน่วยความจำ reallocates

62
00:02:21,180 --> 00:02:25,490
>> realloc เช่นกันพยายามที่จะให้คุณ
หน่วยความจำที่ต่อไปไปยังอาร์เรย์

63
00:02:25,490 --> 00:02:26,610
ที่คุณมีอยู่แล้ว

64
00:02:26,610 --> 00:02:28,740
แต่มันอาจจะย้ายสิ่ง
รอบทั้งหมด

65
00:02:28,740 --> 00:02:30,710
แต่ในระยะสั้นที่มีราคาแพงใช่มั้ย?

66
00:02:30,710 --> 00:02:33,440
เพราะถ้าคุณมีหน่วยความจำอันของ
ขนาดนี้ แต่คุณต้องการจริงๆหนึ่ง

67
00:02:33,440 --> 00:02:36,710
ขนาดนี้และคุณต้องการที่จะรักษา
องค์ประกอบเดิมที่คุณมี

68
00:02:36,710 --> 00:02:40,510
ประมาณเวลากระบวนการเชิงเส้นการคัดลอก
ที่ต้องการที่เกิดขึ้นจาก

69
00:02:40,510 --> 00:02:41,900
อาร์เรย์เก่าไปใหม่

70
00:02:41,900 --> 00:02:44,630
และความเป็นจริงจะขอปฏิบัติการ
ระบบอีกครั้งและอีกครั้งและ

71
00:02:44,630 --> 00:02:48,340
อีกครั้งสำหรับชิ้นใหญ่ของหน่วยความจำที่สามารถเริ่มต้น
เพื่อใช้เวลาของคุณบางส่วนเช่นกัน

72
00:02:48,340 --> 00:02:52,250
ดังนั้นจึงเป็นทั้งพรและสาปใน
ปิดบังความจริงที่ว่าเหล่านี้อาร์เรย์

73
00:02:52,250 --> 00:02:53,860
มีขนาดคงที่

74
00:02:53,860 --> 00:02:56,790
แต่ถ้าเราแนะนำแทนบางสิ่งบางอย่าง
เช่นนี้ซึ่งเราเรียกว่าการเชื่อมโยง

75
00:02:56,790 --> 00:03:00,580
รายการที่เราได้รับไม่กี่ upsides และ
ข้อเสียไม่กี่ที่นี่เช่นกัน

76
00:03:00,580 --> 00:03:05,780
>> ดังนั้นรายการที่เชื่อมโยงเป็นเพียงข้อมูล
โครงสร้างที่สร้างขึ้นจาก structs ใน C นี้

77
00:03:05,780 --> 00:03:09,850
กรณีที่โครงสร้างการเรียกคืนเป็นเพียง
ภาชนะสำหรับหนึ่งหรือเฉพาะเจาะจงมากขึ้น

78
00:03:09,850 --> 00:03:11,100
ประเภทของตัวแปร

79
00:03:11,100 --> 00:03:16,110
ในกรณีนี้สิ่งที่ทำชนิดข้อมูล
ดูเหมือนจะเป็นด้านในของ struct ว่า

80
00:03:16,110 --> 00:03:17,600
ครั้งสุดท้ายที่เราเรียกว่าโหนด?

81
00:03:17,600 --> 00:03:19,380
แต่ละสี่เหลี่ยมเหล่านี้คือโหนด

82
00:03:19,380 --> 00:03:22,660
และแต่ละรูปสี่เหลี่ยมที่มีขนาดเล็ก
ภายในของมันชนิดข้อมูลคือ

83
00:03:22,660 --> 00:03:25,300
เราไม่ประเภทใดบ้างที่บอกว่า
พวกเขาเมื่อวันจันทร์ที่?

84
00:03:25,300 --> 00:03:26,478
อ้าง?

85
00:03:26,478 --> 00:03:27,870
>> ลูกศิษย์: [ได้ยิน]

86
00:03:27,870 --> 00:03:30,721
>> ลำโพง 1: ตัวแปรและตัวชี้หรือ
มากขึ้นโดยเฉพาะ int สำหรับ n,

87
00:03:30,721 --> 00:03:32,180
และตัวชี้ที่ด้านล่าง

88
00:03:32,180 --> 00:03:35,360
ทั้งของผู้ที่เกิดขึ้นจะเป็น 32 บิตที่
อย่างน้อยในคอมพิวเตอร์เช่นนี้ CS50

89
00:03:35,360 --> 00:03:37,980
เครื่องใช้ไฟฟ้าและอื่น ๆ ที่พวกเขากำลัง
วาดอย่างเท่าเทียมกันในขนาดที่

90
00:03:37,980 --> 00:03:42,260
>> ดังนั้นสิ่งที่จะใช้ตัวชี้
แต่สำหรับที่เห็นได้ชัด?

91
00:03:42,260 --> 00:03:47,690
เพิ่มลูกศรนี้ทำไมตอนนี้เมื่อมีอาร์เรย์
ดังนั้นที่ดีและสะอาดและเรียบง่าย?

92
00:03:47,690 --> 00:03:50,460
ตัวชี้กำลังทำอะไรอยู่สำหรับ
เราในแต่ละโหนดเหล่านี้ได้อย่างไร

93
00:03:50,460 --> 00:03:52,160
>> ลูกศิษย์: [ได้ยิน]

94
00:03:52,160 --> 00:03:52,465
>> 1 ลำโพงว่า

95
00:03:52,465 --> 00:03:54,120
มันบอกคุณที่
หนึ่งต่อไปคือ

96
00:03:54,120 --> 00:03:57,350
ดังนั้นผมจึงเรียงลำดับของการใช้การเปรียบเทียบของ
โดยใช้ด้ายจะเรียงลำดับจาก

97
00:03:57,350 --> 00:03:59,180
ด้ายโหนดเหล่านี้ร่วมกัน

98
00:03:59,180 --> 00:04:01,760
และนั่นคือสิ่งที่เรากำลังทำอยู่ด้วย
ชี้เพราะแต่ละเหล่านี้

99
00:04:01,760 --> 00:04:06,360
ชิ้นของหน่วยความจำอาจจะหรืออาจจะไม่
ที่อยู่ติดกันกลับไปกลับไปที่

100
00:04:06,360 --> 00:04:09,500
ภายในของ RAM เพราะทุกครั้งที่คุณ
เรียก malloc บอกให้ฉันพอ

101
00:04:09,500 --> 00:04:12,510
ไบต์สำหรับโหนดใหม่ก็อาจจะ
จะอยู่ที่นี่หรือมันอาจจะเป็นที่นี่

102
00:04:12,510 --> 00:04:13,120
มันอาจจะเป็นที่นี่

103
00:04:13,120 --> 00:04:13,730
มันอาจจะเป็นที่นี่

104
00:04:13,730 --> 00:04:14,640
คุณเพียงแค่ไม่ทราบ

105
00:04:14,640 --> 00:04:17,880
>> แต่การใช้ตัวชี้ในที่อยู่ของ
โหนดที่คุณสามารถปักครอสติพวกเขา

106
00:04:17,880 --> 00:04:22,370
ร่วมกันในวิธีการที่มีลักษณะทางสายตา
เช่นรายการแม้ว่าสิ่งเหล่านี้

107
00:04:22,370 --> 00:04:26,770
ทั้งหมดกระจายออกไปทั่วหนึ่งของคุณหรือ
สองหรือสี่กิกะไบต์ของ RAM ของคุณ

108
00:04:26,770 --> 00:04:28,760
ภายในเครื่องคอมพิวเตอร์ของคุณเอง

109
00:04:28,760 --> 00:04:33,230
>> ข้อเสียเช่นนั้นแล้วของ
รายการที่เชื่อมโยงคืออะไร?

110
00:04:33,230 --> 00:04:34,670
ราคาเท่ากันคืออะไร
เห็นได้ชัดว่าการจ่ายเงิน?

111
00:04:34,670 --> 00:04:36,010
>> ลูกศิษย์: [ได้ยิน]

112
00:04:36,010 --> 00:04:36,920
>> 1 SPEAKER: พื้นที่มากขึ้นใช่มั้ย?

113
00:04:36,920 --> 00:04:39,340
เราได้ในกรณีนี้จำนวนสองเท่า
ของพื้นที่เพราะเราได้ไปแล้ว

114
00:04:39,340 --> 00:04:43,500
จาก 32 บิตสำหรับแต่ละโหนดสำหรับแต่ละ
int ดังนั้นตอนนี้ 64 บิตเพราะเราต้อง

115
00:04:43,500 --> 00:04:45,050
ให้ทั่วตัวชี้เช่นกัน

116
00:04:45,050 --> 00:04:48,860
คุณจะได้รับประสิทธิภาพมากขึ้นถ้า struct ของคุณ
มีขนาดใหญ่กว่าสิ่งที่ง่ายนี้

117
00:04:48,860 --> 00:04:52,020
ถ้าคุณจริงมีนักเรียนภายใน
ซึ่งคู่ของสตริงคือ

118
00:04:52,020 --> 00:04:55,430
ชื่อและที่บ้านอาจจะมีหมายเลขประจำตัว,
บางทีบางสาขาอื่น ๆ โดยสิ้นเชิง

119
00:04:55,430 --> 00:04:59,000
>> ดังนั้นถ้าคุณมีโครงสร้างขนาดใหญ่มากพอ,
แล้วอาจจะเสียค่าใช้จ่ายของตัวชี้คือ

120
00:04:59,000 --> 00:05:00,010
ไม่เช่นใหญ่จัดการ

121
00:05:00,010 --> 00:05:03,570
นี้เป็นบิตของกรณีมุมในการที่
เรากำลังจัดเก็บดังกล่าวที่เรียบง่ายแบบดั้งเดิม

122
00:05:03,570 --> 00:05:04,760
ภายในของรายการที่เชื่อมโยง

123
00:05:04,760 --> 00:05:05,790
แต่ประเด็นก็คือเดียวกัน

124
00:05:05,790 --> 00:05:08,230
คุณกำลังใช้จ่ายมากขึ้นแน่นอน
หน่วยความจำ แต่คุณจะได้รับ

125
00:05:08,230 --> 00:05:08,990
ความยืดหยุ่น

126
00:05:08,990 --> 00:05:12,280
เพราะตอนนี้ถ้าผมต้องการที่จะเพิ่มองค์ประกอบ
ที่จุดเริ่มต้นของรายการนี​​้

127
00:05:12,280 --> 00:05:14,340
ฉันต้องจัดสรรโหนดใหม่

128
00:05:14,340 --> 00:05:17,180
และฉันได้เพียงแค่การปรับปรุงเหล่านั้น
ลูกศรอย่างใดโดยเพียงแค่ย้าย

129
00:05:17,180 --> 00:05:17,980
ชี้บางรอบ

130
00:05:17,980 --> 00:05:20,580
>> ถ้าฉันต้องการแทรกสิ่งที่เป็น
กลางของรายการที่ผมจะได้ไม่ต้อง

131
00:05:20,580 --> 00:05:24,410
ผลักดันให้ทุกคนเหมือนกันที่เราทำใน
อดีตที่ผ่านมาสัปดาห์โดยได้รับอาสาสมัครของเราที่

132
00:05:24,410 --> 00:05:25,700
เป็นตัวแทนของอาร์เรย์

133
00:05:25,700 --> 00:05:29,470
ฉันสามารถจัดสรรโหนดใหม่และ
แล้วก็ชี้ลูกศรใน

134
00:05:29,470 --> 00:05:32,290
ทิศทางที่แตกต่างกันเพราะมันไม่ได้
ต้องยังคงอยู่ในที่เกิดขึ้นจริง

135
00:05:32,290 --> 00:05:35,670
หน่วยความจำเส้นจริงเหมือนที่ผมเคยวาด
ได้ที่นี่บนหน้าจอ

136
00:05:35,670 --> 00:05:38,400
>> แล้วสุดท้ายหากคุณต้องการแทรก
บางสิ่งบางอย่างในตอนท้ายของรายการก็

137
00:05:38,400 --> 00:05:39,210
ง่ายยิ่งขึ้น

138
00:05:39,210 --> 00:05:43,320
นี้จะเรียงลำดับของสัญกรณ์พล
แต่ตัวชี้ 34 ของใช้เดา

139
00:05:43,320 --> 00:05:46,710
ค่าของตัวชี้มากที่สุดคืออะไร
จัดเรียงวาดน่าจะเหมือนเก่า

140
00:05:46,710 --> 00:05:47,700
โรงเรียนมีเสาอากาศ?

141
00:05:47,700 --> 00:05:48,920
>> ลูกศิษย์: [ได้ยิน]

142
00:05:48,920 --> 00:05:49,900
>> 1 ลำโพงมันอาจโมฆะ

143
00:05:49,900 --> 00:05:52,710
และแน่นอนว่าเป็นหนึ่งของผู้เขียน
เป็นตัวแทนของโมฆะ

144
00:05:52,710 --> 00:05:56,310
และมันก็เป็นโมฆะเพราะคุณอย่างแน่นอน
จำเป็นต้องรู้ว่าจุดสิ้นสุดของการเชื่อมโยง

145
00:05:56,310 --> 00:06:00,050
คือรายการที่เกรงว่าคุณเก็บต่อไปนี้และ
ต่อไปและต่อไปนี้ลูกศรเหล่านี้

146
00:06:00,050 --> 00:06:01,170
ค่าขยะบาง

147
00:06:01,170 --> 00:06:06,230
ดังนั้นโมฆะจะมีความหมายว่าไม่มี
โหนดขึ้นทางด้านขวาของหมายเลข 34,

148
00:06:06,230 --> 00:06:07,200
ในกรณีนี้

149
00:06:07,200 --> 00:06:10,270
>> ดังนั้นเราจึงเสนอว่าเราสามารถใช้
โหนดในรหัสนี้

150
00:06:10,270 --> 00:06:12,130
และเราได้เห็นแบบนี้
ของไวยากรณ์ก่อน

151
00:06:12,130 --> 00:06:15,090
typedef เพียงแค่กำหนดประเภทใหม่สำหรับ
เราทำให้เรามีความหมายเหมือนกันเช่น

152
00:06:15,090 --> 00:06:17,100
สตริงเป็น char *

153
00:06:17,100 --> 00:06:21,030
ในกรณีนี้มันจะให้เรา
สัญกรณ์ชวเลขเพื่อให้โหนด struct

154
00:06:21,030 --> 00:06:24,010
สามารถแทนเพียงแค่จะเขียนเป็น
โหนดซึ่งเป็นมากสะอาด

155
00:06:24,010 --> 00:06:25,360
มันมากน้อย verbose

156
00:06:25,360 --> 00:06:30,080
>> ภายในของโหนดเห็นได้ชัดคือ int
ที่เรียกว่า n แล้​​วโหนด struct *

157
00:06:30,080 --> 00:06:34,670
ซึ่งหมายความว่าสิ่งที่เราต้องการ
ลูกศรจะหมายถึงตัวชี้ไปยังอีก

158
00:06:34,670 --> 00:06:36,940
โหนดของชนิดข้อมูลที่แน่นอนเดียวกัน

159
00:06:36,940 --> 00:06:40,300
และผมเสนอว่าเราสามารถใช้
ฟังก์ชั่นค้นหาเช่นนี้ซึ่งที่

160
00:06:40,300 --> 00:06:41,890
แวบแรกอาจจะดูเหมือน
ที่มีความซับซ้อนน้อย

161
00:06:41,890 --> 00:06:43,330
แต่เรามาดูมันในบริบท

162
00:06:43,330 --> 00:06:45,480
>> ผมขอข้ามไปเครื่องใช้ที่นี่

163
00:06:45,480 --> 00:06:48,460
ผมขอเปิดไฟล์ที่เรียกว่า
รายการชั่วโมงศูนย์จุด

164
00:06:48,460 --> 00:06:53,950
และมีเพียงคำนิยามของเรา
เพิ่งเห็นสักครู่ที่ผ่านมาสำหรับข้อมูลนี้

165
00:06:53,950 --> 00:06:55,390
ประเภทที่เรียกว่าโหนด

166
00:06:55,390 --> 00:06:57,350
ดังนั้นเราจึงได้วางว่าเป็นไฟล์ dot ชั่วโมง

167
00:06:57,350 --> 00:07:01,430
>> และเป็นกันแม้นี้
โปรแกรมที่คุณกำลังจะได้เห็นคือ

168
00:07:01,430 --> 00:07:05,410
ไม่ทั้งหมดที่ซับซ้อนที่มันแน่นอน
การประชุมเมื่อเขียนโปรแกรมเพื่อ

169
00:07:05,410 --> 00:07:10,270
ใส่สิ่งที่ต้องการชนิดข้อมูลที่จะดึง
ค่าคงที่บางครั้งภายในของคุณ

170
00:07:10,270 --> 00:07:13,210
ไฟล์ส่วนหัวและไม่จำเป็นต้องใน
ไฟล์ของคุณ C แน่นอนเมื่อของคุณ

171
00:07:13,210 --> 00:07:17,370
ที่โปรแกรมมีขนาดใหญ่และมีขนาดใหญ่เพื่อให้
คุณรู้จักที่จะมองทั้งสอง

172
00:07:17,370 --> 00:07:20,840
เอกสารในบางกรณีหรือ
สำหรับพื้นฐานเช่นนี้

173
00:07:20,840 --> 00:07:22,360
ความหมายของบางประเภท

174
00:07:22,360 --> 00:07:25,680
>> ถ้าตอนนี้ผมเปิดรายการเป็นศูนย์จุด
คสังเกตเห็นบางสิ่ง

175
00:07:25,680 --> 00:07:29,090
ซึ่งจะรวมถึงส่วนหัวของไฟล์ไม่กี่ส่วนใหญ่
จากที่เราเคยเห็นมาก่อน

176
00:07:29,090 --> 00:07:31,980
ซึ่งจะรวมถึงไฟล์ส่วนหัวของตัวเอง

177
00:07:31,980 --> 00:07:35,200
>> และเป็นกันทำไมที่สอง
คำพูดที่นี่เมื่อเทียบกับมุม

178
00:07:35,200 --> 00:07:38,340
วงเล็บในบรรทัดที่
ผมได้เน้นมี?

179
00:07:38,340 --> 00:07:39,180
>> ลูกศิษย์: [ได้ยิน]

180
00:07:39,180 --> 00:07:40,460
>> ลำโพง 1: Yeah จึงเป็นไฟล์ท้องถิ่น

181
00:07:40,460 --> 00:07:44,300
ดังนั้นถ้ามันเป็นไฟล์ของคุณเองที่นี่
ในบรรทัดที่ 15 ตัวอย่างเช่นคุณใช้

182
00:07:44,300 --> 00:07:46,570
คำพูดคู่แทน
ของวงเล็บมุม

183
00:07:46,570 --> 00:07:48,270
>> ตอนนี้เป็นชนิดของที่น่าสนใจ

184
00:07:48,270 --> 00:07:51,830
ขอให้สังเกตว่าที่ผมเคยประกาศทั่วโลก
ตัวแปรในโปรแกรมนี้อยู่บนเส้น 18

185
00:07:51,830 --> 00:07:55,910
ครั้งแรกเรียกว่าความคิดเป็นนี้คือ
จะเป็นตัวชี้ไปที่แรก

186
00:07:55,910 --> 00:07:59,190
โหนดในรายการที่เชื่อมโยงของฉันและฉันได้
เริ่มต้นให้เป็นโมฆะเพราะฉัน

187
00:07:59,190 --> 00:08:02,310
ไม่ได้รับการจัดสรรตามความเป็นจริงใด ๆ
โหนดเพียง แต่

188
00:08:02,310 --> 00:08:07,570
>> ดังนั้นนี่หมายถึง pictorially สิ่งที่เรา
เห็นช่วงเวลาที่ผ่านมาในภาพ

189
00:08:07,570 --> 00:08:10,090
ตัวชี้ไกลว่า
ด้านซ้ายมือ

190
00:08:10,090 --> 00:08:12,260
ดังนั้นในขณะนี้ชี้ว่า
ไม่ได้มีลูกศร

191
00:08:12,260 --> 00:08:14,590
มันแทนเป็นโมฆะเพียง

192
00:08:14,590 --> 00:08:17,880
แต่มันหมายถึงสิ่งที่จะเป็น
ที่อยู่ของคนแรกที่เกิดขึ้นจริง

193
00:08:17,880 --> 00:08:19,480
โหนดในรายการนี​​้

194
00:08:19,480 --> 00:08:22,120
ดังนั้นผมจึงได้ดำเนินการมันเป็นระดับโลก
เพราะเป็นคุณจะเห็นทั้งหมดนี้

195
00:08:22,120 --> 00:08:25,310
โปรแกรมไม่ในชีวิตคือการดำเนินการ
รายการที่เชื่อมโยงสำหรับฉัน

196
00:08:25,310 --> 00:08:27,050
>> ตอนนี้ฉันมีต้นแบบไม่กี่ที่นี่

197
00:08:27,050 --> 00:08:31,190
ฉันตัดสินใจที่จะใช้คุณสมบัติเช่น
การลบการแทรก, การค้นหาและ

198
00:08:31,190 --> 00:08:31,740
traversal -

199
00:08:31,740 --> 00:08:35,210
เดินเพียงการข้ามล่าสุด
รายการพิมพ์ออกองค์ประกอบ

200
00:08:35,210 --> 00:08:36,750
และตอนนี้ที่นี่เป็นประจำหลักของฉัน

201
00:08:36,750 --> 00:08:39,890
และเราจะไม่ใช้เวลามากเกินไปใน
เหล่านี้ตั้งแต่นี้เป็นจัดเรียงของหวังว่า

202
00:08:39,890 --> 00:08:41,780
หมวกเก่าโดยขณะนี้

203
00:08:41,780 --> 00:08:45,370
>> ฉันจะทำต่อไปนี้,
ขณะที่ผู้ใช้ให้ความร่วมมือ

204
00:08:45,370 --> 00:08:47,300
ดังนั้นหนึ่งผมจะพิมพ์
ออกเมนูนี้

205
00:08:47,300 --> 00:08:49,420
และฉันได้จัดรูปแบบเป็น
เรียบร้อยเท่าที่ฉันสามารถ

206
00:08:49,420 --> 00:08:52,240
ถ้าผู้ใช้ในหนึ่งนั่นหมายความว่า
พวกเขาต้องการที่จะลบบางสิ่งบางอย่าง

207
00:08:52,240 --> 00:08:54,560
ถ้าผู้ใช้ในสองนั่นหมายความว่า
พวกเขาต้องการที่จะแทรกบางสิ่งบางอย่าง

208
00:08:54,560 --> 00:08:55,930
เป็นต้น

209
00:08:55,930 --> 00:08:58,270
ฉันกำลังจะไปแล้วแจ้งให้
แล้วสำหรับคำสั่ง

210
00:08:58,270 --> 00:08:59,300
แล้วฉันจะใช้ GetInt

211
00:08:59,300 --> 00:09:02,790
>> ดังนั้นนี่คือ menuing ง่ายจริงๆ
ติดต่อที่คุณเพียงแค่ต้องพิมพ์

212
00:09:02,790 --> 00:09:05,270
การทำแผนที่จำนวนหนึ่ง
ของคำสั่งเหล่านั้น

213
00:09:05,270 --> 00:09:08,730
และตอนนี้ฉันมีสวิทช์สะอาดดี
คำสั่งที่จะเปิด

214
00:09:08,730 --> 00:09:10,090
สิ่งที่ผู้ใช้พิมพ์นิ้ว

215
00:09:10,090 --> 00:09:12,180
และถ้าพวกเขาพิมพ์หนึ่งฉันจะ
เรียกลบและทำลาย

216
00:09:12,180 --> 00:09:14,380
ถ้าพวกเขาพิมพ์สองนี้ฉันจะ
เรียกแทรกและทำลาย

217
00:09:14,380 --> 00:09:16,490
>> และผมสังเกตเห็นในขณะนี้ได้วางแต่ละ
ของเหล่านี้ในบรรทัดเดียวกัน

218
00:09:16,490 --> 00:09:18,360
นี่เป็นเพียงการตัดสินใจโวหาร

219
00:09:18,360 --> 00:09:20,210
โดยปกติท​​ี่เราเคยเห็นบางสิ่งบางอย่าง
เช่นนี้

220
00:09:20,210 --> 00:09:23,260
แต่ฉันก็ตัดสินใจที่ตรงไปตรงมาโปรแกรมของฉัน
มองที่อ่านได้มากขึ้นเพราะ

221
00:09:23,260 --> 00:09:25,980
มันก็เป็นเพียงสี่กรณีไป
เพียงรายการเช่นนี้

222
00:09:25,980 --> 00:09:28,360
ใช้ที่ถูกต้องทั้งหมดของสไตล์

223
00:09:28,360 --> 00:09:31,480
และฉันจะทำเช่นนี้ตราบเท่าที่
ผู้ใช้ยังไม่ได้พิมพ์เป็นศูนย์ซึ่งผม

224
00:09:31,480 --> 00:09:33,910
ตัดสินใจที่จะหมายถึงการที่พวกเขาต้องการที่จะเลิก

225
00:09:33,910 --> 00:09:36,630
>> ดังนั้นตอนนี้สังเกตเห็นสิ่งที่ฉัน
จะทำที่นี่

226
00:09:36,630 --> 00:09:38,650
ฉันจะเป็นอิสระรายชื่อเห็นได้ชัดว่า

227
00:09:38,650 --> 00:09:40,230
แต่เพิ่มเติมว่าในเวลาเพียงสักครู่

228
00:09:40,230 --> 00:09:41,640
Let 's แรกรันโปรแกรมนี้

229
00:09:41,640 --> 00:09:45,250
ดังนั้นให้ฉันทำขั้วใหญ่
หน้าต่างรายชื่อจุดเฉือน 0

230
00:09:45,250 --> 00:09:49,510
ฉันจะไปข้างหน้าและใส่โดย
การพิมพ์สองเป็นจำนวนมากเช่น 50 และตอนนี้

231
00:09:49,510 --> 00:09:51,590
คุณจะเห็นรายการอยู่ในขณะนี้ 50

232
00:09:51,590 --> 00:09:53,380
และข้อความของฉันเพียงแค่เลื่อนขึ้นเล็กน้อย

233
00:09:53,380 --> 00:09:55,940
ดังนั้นตอนนี้สังเกตเห็นรายการมี
จำนวน 50

234
00:09:55,940 --> 00:09:58,220
>> ขอทำแทรกอื่นโดยการสอง

235
00:09:58,220 --> 00:10:01,630
ประเภทให้อยู่ในจำนวนหนึ่งเช่น

236
00:10:01,630 --> 00:10:03,940
รายชื่อเป็นหนึ่งตามด้วย 50

237
00:10:03,940 --> 00:10:06,020
ดังนั้นนี้เป็นเพียงการแสดงต้นฉบับ
ของรายการ

238
00:10:06,020 --> 00:10:10,550
และให้ใส่หมายเลขหนึ่งมากขึ้นเช่น
หมายเลข 42 ซึ่งเป็นความหวัง

239
00:10:10,550 --> 00:10:14,620
จะจบลงในช่วงกลางเพราะ
โปรแกรมนี้ในทุกประเภทโดยเฉพาะอย่างยิ่งมัน

240
00:10:14,620 --> 00:10:16,320
องค์ประกอบแทรกพวกเขา

241
00:10:16,320 --> 00:10:17,220
จึงมีเรามีมัน

242
00:10:17,220 --> 00:10:20,730
โปรแกรมใช้งานง่ายสุดที่จะทำได้
อย่างที่มีการใช้อาร์เรย์ แต่ฉัน

243
00:10:20,730 --> 00:10:23,280
เกิดขึ้นที่จะใช้รายการการเชื่อมโยง
เพียงเพื่อให้ฉันสามารถแบบไดนามิก

244
00:10:23,280 --> 00:10:24,610
เติบโตและหด

245
00:10:24,610 --> 00:10:28,470
>> ดังนั้นลองมาดูสำหรับการค้นหาถ้าฉัน
ทำงานสามคำสั่งที่ฉันต้องการที่จะค้นหา

246
00:10:28,470 --> 00:10:31,040
สำหรับการพูด, หมายเลข 43

247
00:10:31,040 --> 00:10:34,190
และไม่มีอะไรที่พบว่าเห็นได้ชัดว่า
เพราะผมได้กลับไม่มีการตอบสนอง

248
00:10:34,190 --> 00:10:35,010
ดังนั้นลองทำเช่นนี้อีกครั้ง

249
00:10:35,010 --> 00:10:35,690
ค้นหา

250
00:10:35,690 --> 00:10:39,520
ค้นหา Let 's สำหรับ 50 หรือมากกว่าค้นหา
42 ซึ่งมีสุข

251
00:10:39,520 --> 00:10:40,850
ความหมายที่ลึกซึ้งน้อย

252
00:10:40,850 --> 00:10:42,610
และฉันพบความหมายของชีวิตที่นั่น

253
00:10:42,610 --> 00:10:44,990
Number 42 ถ้าคุณไม่ทราบว่า
อ้างอิงมัน Google

254
00:10:44,990 --> 00:10:45,350
ทั้งหมดขวา

255
00:10:45,350 --> 00:10:47,130
ดังนั้นสิ่งที่ได้ทำโปรแกรมนี้สำหรับฉันหรือไม่

256
00:10:47,130 --> 00:10:50,660
มันได้รับอนุญาตเพียงฉันจึงแทรก
ไกลและการค้นหาสำหรับองค์ประกอบ

257
00:10:50,660 --> 00:10:53,650
>> Let 's ข้างหน้าอย่างรวดเร็วนั้นไป
ฟังก์ชั่นที่เราชำเลืองมอง

258
00:10:53,650 --> 00:10:55,360
ในวันจันทร์ที่เป็นทีเซอร์

259
00:10:55,360 --> 00:10:59,620
ดังนั้นฟังก์ชั่นนี้ผมเรียกร้องการค้นหา
องค์ประกอบในรายการเป็นครั้งแรกโดย

260
00:10:59,620 --> 00:11:03,830
หนึ่งกระตุ้นให้ผู้ใช้แล้วโทร
getInt ที่จะได้รับ int ที่เกิดขึ้นจริง

261
00:11:03,830 --> 00:11:05,060
ที่คุณต้องการค้นหา

262
00:11:05,060 --> 00:11:06,460
>> แล้วสังเกตเห็นนี้

263
00:11:06,460 --> 00:11:10,690
ฉันจะสร้างตัวแปรชั่วคราว
188 สายในตัวชี้ที่เรียกว่า -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
อาจจะเรียกมันว่าอะไรก็ตาม

266
00:11:12,440 --> 00:11:16,140
และมันก็เป็นตัวชี้ไปยังโหนด
เพราะผมบอกว่า * โหนดมี

267
00:11:16,140 --> 00:11:19,900
และฉันเริ่มต้นมันจะเท่ากับ
เป็นครั้งแรกเพื่อที่ฉันจะได้อย่างมีประสิทธิภาพมีของฉัน

268
00:11:19,900 --> 00:11:22,860
นิ้วเพื่อที่จะพูดในสิ่งที่ดี
องค์ประกอบแรกของรายการ

269
00:11:22,860 --> 00:11:27,460
ดังนั้นถ้ามือข้างขวาของฉันที่นี่คือ PTR ฉัน
ชี้ไปที่สิ่งเดียวกันกับที่แรก

270
00:11:27,460 --> 00:11:28,670
จะชี้ไปที่

271
00:11:28,670 --> 00:11:31,430
>> ดังนั้นตอนนี้กลับมาอยู่ในรหัส
เกิดขึ้นต่อไปคืออะไร -

272
00:11:31,430 --> 00:11:35,070
นี้เป็นกระบวนทัศน์ทั่วไปเมื่อ iterating
กว่าโครงสร้างเช่น

273
00:11:35,070 --> 00:11:35,970
รายการที่เชื่อมโยง

274
00:11:35,970 --> 00:11:40,410
ฉันจะทำต่อไปในขณะที่
ตัวชี้ไม่เท่ากับโมฆะดังนั้นในขณะที่

275
00:11:40,410 --> 00:11:47,530
นิ้วมือข​​องฉันไม่ได้ชี้ไปที่ null บาง
ค่าถ้าตัวชี้ลูกศร n เท่ากับ n

276
00:11:47,530 --> 00:11:52,290
เราจะสังเกตเห็นเป็นครั้งแรกที่ n คืออะไร
ผู้ใช้พิมพ์ลงใน GetInts ต่อการโทรที่นี่

277
00:11:52,290 --> 00:11:54,280
>> และตัวชี้ลูกศร n หมายถึงอะไร?

278
00:11:54,280 --> 00:11:59,020
ดีถ้าเรากลับไปยังภาพที่นี่
ถ้าฉันมีนิ้วชี้ไปที่

279
00:11:59,020 --> 00:12:02,960
ที่โหนดแรกที่มีเก้า
หลักหมายถึงลูกศรไปที่

280
00:12:02,960 --> 00:12:08,860
โหนดและคว้าค่าที่ n ตั้ง,
ในกรณีนี้เขตข้อมูลที่เรียกว่า n

281
00:12:08,860 --> 00:12:14,120
>> เช่นกัน - และเราเห็นคู่นี้
ของสัปดาห์ที่ผ่านมาเมื่อมีคนถาม -

282
00:12:14,120 --> 00:12:18,840
รูปแบบนี้เป็นของใหม่ แต่มันไม่ได้
ทำให้เรามีอำนาจที่เรา

283
00:12:18,840 --> 00:12:20,040
ไม่ได้มีอยู่แล้ว

284
00:12:20,040 --> 00:12:25,325
อะไรวลีเทียบเท่ากับการใช้นี้เป็น
จุดสัญกรณ์และดาวคู่

285
00:12:25,325 --> 00:12:29,490
ของสัปดาห์ที่ผ่านมาเมื่อเราปอกเปลือกกลับ
ชั้นนี้บิตก่อนกำหนด?

286
00:12:29,490 --> 00:12:31,780
>> ลูกศิษย์: [ได้ยิน]

287
00:12:31,780 --> 00:12:38,880
>> 1 ลำโพงว่ามันเป็นดาวและ
แล้วมันก็เป็นดาราจุด n ด้วย

288
00:12:38,880 --> 00:12:41,930
วงเล็บที่นี่ซึ่งมีลักษณะ,
ตรงไปตรงมาผมคิดว่า

289
00:12:41,930 --> 00:12:43,320
คลุมเครือมากขึ้นที่จะอ่าน

290
00:12:43,320 --> 00:12:46,270
แต่ตัวชี้ดาวเป็นเสมอ
หมายถึงไปที่นั่น

291
00:12:46,270 --> 00:12:49,090
และเมื่อคุณมีข้อมูลอะไร
คุณสาขาต้องการเข้าถึง?

292
00:12:49,090 --> 00:12:52,730
ที่ดีที่คุณใช้สัญกรณ์จุดที่จะเข้าถึง
structs ด้านข้อมูลและฉัน

293
00:12:52,730 --> 00:12:54,140
ต้องการเฉพาะ n

294
00:12:54,140 --> 00:12:56,240
>> ตรงไปตรงมาฉันจะยืนยันนี้
เป็นเพียงยากที่จะอ่าน

295
00:12:56,240 --> 00:12:58,080
มันยากที่จะจำที่
ทำวงเล็บไป

296
00:12:58,080 --> 00:12:59,030
ดาวและทุกที่

297
00:12:59,030 --> 00:13:02,150
ดังนั้นโลกนำมาใช้ประโยคบาง
น้ำตาลเพื่อที่จะพูด

298
00:13:02,150 --> 00:13:04,740
เพียงวิธีที่เซ็กซี่ของว่า
นี้จะเทียบเท่าและ

299
00:13:04,740 --> 00:13:05,970
บางทีอาจจะมากกว่างานง่าย

300
00:13:05,970 --> 00:13:09,600
ถ้าตัวชี้ย่อมเป็นตัวชี้,
หมายถึงสัญกรณ์ลูกศรไปที่นั่นและหา

301
00:13:09,600 --> 00:13:11,890
สนามในกรณีนี้เรียกว่า n

302
00:13:11,890 --> 00:13:13,660
>> ดังนั้นถ้าฉันพบว่ามันสังเกตเห็นสิ่งที่ฉันทำ

303
00:13:13,660 --> 00:13:17,430
ฉันก็พิมพ์ออกมาผมพบว่าร้อยละ i,
เสียบค่า int ที่

304
00:13:17,430 --> 00:13:20,730
ที่ผมเรียกว่านอนหลับหนึ่งวินาทีเพียงแค่ชนิด
สิ่งที่หยุดชั่วคราวบนหน้าจอเพื่อ

305
00:13:20,730 --> 00:13:22,900
ให้ผู้ใช้ที่สองในการดูดซับ
สิ่งที่เกิดขึ้นเพียง

306
00:13:22,900 --> 00:13:24,290
แล้วฉันทำลาย

307
00:13:24,290 --> 00:13:26,330
มิฉะนั้นผมจะทำอย่างไร

308
00:13:26,330 --> 00:13:30,960
ผมปรับปรุงตัวชี้ไปที่เท่าเทียมกัน
ลูกศรตัวชี้ต่อไป

309
00:13:30,960 --> 00:13:35,840
>> ดังนั้นเพียงแค่ต้องมีความชัดเจนที่นี้หมายถึงไป
มีการใช้สัญกรณ์โรงเรียนเก่าของฉัน

310
00:13:35,840 --> 00:13:39,580
ดังนั้นเพียงแค่นี้หมายถึงการที่จะไปกับสิ่งที่
คุณกำลังชี้ไปที่ซึ่งมาก

311
00:13:39,580 --> 00:13:43,660
กรณีแรกคือผมชี้ไปที่
struct กับเก้าในนั้น

312
00:13:43,660 --> 00:13:44,510
ดังนั้นผมจึงได้ไปมี

313
00:13:44,510 --> 00:13:47,880
แล้วจุดสัญกรณ์หมายถึง
ได้รับค่าที่ต่อไป

314
00:13:47,880 --> 00:13:50,470
>> แต่ค่าแม้ว่ามันวาด
เป็นที่แคบเพียงจำนวนเป็น

315
00:13:50,470 --> 00:13:51,720
มันเป็นตัวเลขที่อยู่

316
00:13:51,720 --> 00:13:55,670
นี้หนึ่งบรรทัดของรหัสดังนั้นไม่ว่า
เขียนเช่นนี้เป็นความลับมากขึ้น

317
00:13:55,670 --> 00:14:00,190
วิธีการหรือเช่นนี้ขึ้นอีกเล็กน้อย
วิธีการใช้งานง่ายเพียงแค่หมายความว่าย้ายมือของฉัน

318
00:14:00,190 --> 00:14:03,460
จากโหนดแรกไปที่หน้าหนึ่ง,
และจากนั้นที่หน้าหนึ่งแล้ว

319
00:14:03,460 --> 00:14:05,320
หน้าหนึ่งและอื่น ๆ

320
00:14:05,320 --> 00:14:09,920
>> ดังนั้นเราจะไม่ได้อาศัยอยู่ในที่อื่น ๆ
การใช้งานของแทรกและลบ

321
00:14:09,920 --> 00:14:14,030
และ traversal สองคนแรกของ
ซึ่งมีส่วนเกี่ยวข้องอย่างเป็นธรรม

322
00:14:14,030 --> 00:14:17,010
และฉันคิดว่ามันค่อนข้างง่ายที่จะได้รับ
หายไปเมื่อทำมันด้วยวาจา

323
00:14:17,010 --> 00:14:19,890
แต่สิ่งที่เราสามารถทำนี่คือ
พยายามที่จะกำหนดวิธีการ

324
00:14:19,890 --> 00:14:21,640
ที่ดีที่สุดที่จะทำนี้สายตา

325
00:14:21,640 --> 00:14:24,800
เพราะฉันอยากจะเสนอว่าถ้าเรา
ต้องการแทรกองค์ประกอบในนี้

326
00:14:24,800 --> 00:14:26,680
รายการที่มีอยู่ซึ่ง
มีห้าองค์ประกอบ -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, และ 33 -

328
00:14:29,530 --> 00:14:33,300
ถ้าฉันกำลังจะดำเนินการนี​​้ใน
รหัสผมต้องพิจารณาวิธีการที่จะไป

329
00:14:33,300 --> 00:14:34,160
เกี่ยวกับการทำเช่นนี้

330
00:14:34,160 --> 00:14:37,720
>> และฉันจะเสนอทำตามขั้นตอนทารก
ซึ่งในกรณีนี้ผมหมายถึงสิ่งที่มี

331
00:14:37,720 --> 00:14:41,090
สถานการณ์ที่เป็นไปได้ที่เรา
อาจพบในการทั่วไป?

332
00:14:41,090 --> 00:14:44,120
เมื่อการดำเนินการแทรกสำหรับการเชื่อมโยง
รายการนี​​้เพิ่งเกิดขึ้นเป็น

333
00:14:44,120 --> 00:14:46,090
ตัวอย่างเฉพาะในห้าของขนาด

334
00:14:46,090 --> 00:14:50,420
ดีถ้าคุณต้องการแทรกหมายเลข,
ชอบพูดหมายเลขหนึ่งและ

335
00:14:50,420 --> 00:14:53,380
รักษาความสงบเรียบร้อยเรียงลำดับที่
เห็นได้ชัดว่าจำนวนหนึ่งจำเป็นต้องทำ

336
00:14:53,380 --> 00:14:55,686
ไปในตัวอย่างนี้โดยเฉพาะ?

337
00:14:55,686 --> 00:14:56,840
ชอบที่จุดเริ่มต้น

338
00:14:56,840 --> 00:15:00,030
>> แต่สิ่งที่น่าสนใจนั่นคือ
ถ้าคุณต้องการที่จะแทรกเข้ามาในนี้

339
00:15:00,030 --> 00:15:04,100
รายการสิ่งที่ตัวชี้ความต้องการพิเศษ
ต้องมีการปรับปรุงที่เห็นได้ชัด?

340
00:15:04,100 --> 00:15:04,610
เป็นครั้งแรก

341
00:15:04,610 --> 00:15:07,830
ดังนั้นผมจะเถียงนี้เป็นกรณีแรก
ที่เราอาจต้องการที่จะต้องพิจารณา

342
00:15:07,830 --> 00:15:11,140
สถานการณ์ที่เกี่ยวข้องกับการใส่ที่
จุดเริ่มต้นของรายการ

343
00:15:11,140 --> 00:15:15,400
>> ขอฉีกอาจจะเป็นเรื่องง่ายหรือแม้กระทั่ง
กรณีที่ง่ายขึ้นค่อนข้างพูด

344
00:15:15,400 --> 00:15:18,110
สมมติว่าฉันต้องการแทรก
35 จำนวนเรียงลำดับ

345
00:15:18,110 --> 00:15:20,600
มันเห็นได้ชัดว่าเป็นของที่นั่น

346
00:15:20,600 --> 00:15:25,320
ดังนั้นสิ่งที่ชี้ชัดเป็นไป
จะต้องมีการปรับปรุงในสถานการณ์ที่?

347
00:15:25,320 --> 00:15:30,060
ตัวชี้ 34 กลายเป็นไม่เป็นโมฆะ
แต่ที่อยู่ของ struct

348
00:15:30,060 --> 00:15:31,800
ที่มีจำนวน 35

349
00:15:31,800 --> 00:15:32,750
ดังนั้นว่าทั้งสองกรณีของ

350
00:15:32,750 --> 00:15:36,190
ดังนั้นแล้วผมจัดเรียงของ quantizing
วิธีการทำงานมากที่ฉันต้องทำที่นี่

351
00:15:36,190 --> 00:15:39,880
>> และในที่สุดก็กรณีกลางเห็นได้ชัดคือ
อันที่จริงในช่วงกลางถ้าผมต้องการ

352
00:15:39,880 --> 00:15:45,870
ใส่บางสิ่งบางอย่างเช่นพูด 23, ที่จะไป
ระหว่างที่ 23 และ 26 แต่

353
00:15:45,870 --> 00:15:48,680
ขณะนี้สิ่งที่ได้รับน้อยมาก
เพราะสิ่งที่เกี่ยวข้อง

354
00:15:48,680 --> 00:15:52,800
ตัวชี้จะต้องมีการเปลี่ยนแปลงอย่างไร

355
00:15:52,800 --> 00:15:56,680
ดังนั้นเห็นได้ชัด 22 ต้องมีการเปลี่ยนแปลง
เพราะเขาไม่สามารถชี้ไปที่ 26 อีกต่อไป

356
00:15:56,680 --> 00:16:00,320
เขาต้องการที่จะชี้ไปยังโหนดใหม่ที่
ฉันจะต้องจัดสรรโดยการเรียก

357
00:16:00,320 --> 00:16:01,770
malloc หรือเทียบเท่าบาง

358
00:16:01,770 --> 00:16:05,990
>> แต่แล้วฉันก็ยังต้องว่าโหนดใหม่, 23
ในกรณีนี้จะมีตัวชี้

359
00:16:05,990 --> 00:16:07,870
ชี้ไปที่ใคร?

360
00:16:07,870 --> 00:16:08,560
26

361
00:16:08,560 --> 00:16:10,380
และมีเป็นไปได้
ลำดับของการดำเนินงานที่นี่

362
00:16:10,380 --> 00:16:13,410
เพราะถ้าฉันทำเช่นนี้โง่และฉัน
สำหรับการเริ่มต้นเช่นที่จุดเริ่มต้นของ

363
00:16:13,410 --> 00:16:16,040
รายการและเป้าหมายของฉันคือการแทรก 23

364
00:16:16,040 --> 00:16:18,610
และผมตรวจสอบที่ไม่ได้เป็นส่วนหนึ่งของ
ที่นี่ใกล้กับเก้า?

365
00:16:18,610 --> 00:16:18,950
เลขที่

366
00:16:18,950 --> 00:16:20,670
มันเป็นส่วนหนึ่งของที่นี่ต่อไปถึง 17?

367
00:16:20,670 --> 00:16:20,940
เลขที่

368
00:16:20,940 --> 00:16:22,530
มันเป็นของที่นี่ต่อไปถึงวันที่ 22?

369
00:16:22,530 --> 00:16:23,300
ใช่

370
00:16:23,300 --> 00:16:26,400
>> ตอนนี้ถ้าผมโง่ที่นี่และไม่ได้
ความคิดนี้ผ่านทางผมอาจ

371
00:16:26,400 --> 00:16:28,320
จัดสรรโหนดใหม่ของฉัน 23

372
00:16:28,320 --> 00:16:32,080
ฉันอาจจะปรับปรุงตัวชี้จาก
โหนดที่เรียกว่า 22 ชี้

373
00:16:32,080 --> 00:16:33,080
ที่โหนดใหม่

374
00:16:33,080 --> 00:16:36,140
และแล้วผมก็ทำในสิ่งที่ต้องปรับปรุง
ตัวชี้โหนดใหม่ที่จะเป็น?

375
00:16:36,140 --> 00:16:38,120
>> ลูกศิษย์: [ได้ยิน]

376
00:16:38,120 --> 00:16:38,385
>> 1 ลำโพงว่า

377
00:16:38,385 --> 00:16:39,710
ชี้ไปที่ 26

378
00:16:39,710 --> 00:16:45,590
แต่ Dammit ถ้าฉันไม่ได้ปรับปรุงแล้ว
ตัวชี้ 22 ที่จะชี้ไปที่ผู้ชายคนนี้และ

379
00:16:45,590 --> 00:16:48,260
ตอนนี้ฉันมีเด็กกำพร้าที่เหลือ
ของรายการเพื่อที่จะพูด

380
00:16:48,260 --> 00:16:52,140
การสั่งซื้อเพื่อให้การดำเนินงานของที่นี่
เป็นไปได้ที่สำคัญ

381
00:16:52,140 --> 00:16:55,100
>> การทำเช่นนี้ฉันสามารถขโมย,
พูดหกอาสาสมัคร

382
00:16:55,100 --> 00:16:57,650
และขอดูว่าเราไม่สามารถทำเช่นนี้
สายตาแทนของรหัสที่ชาญฉลาด

383
00:16:57,650 --> 00:16:59,330
และเรามีบางอย่างที่น่ารักความเครียด
ลูกสำหรับคุณในวันนี้

384
00:16:59,330 --> 00:17:02,510
ตกลงเกี่ยวกับวิธีการหนึ่งสองใน
กลับ - บนปลายมี

385
00:17:02,510 --> 00:17:04,530
สามสี่ทั้งสองท่าน
พวกที่สิ้นสุด

386
00:17:04,530 --> 00:17:05,579
และห้าหก

387
00:17:05,579 --> 00:17:05,839
แน่ใจ

388
00:17:05,839 --> 00:17:06,450
ห้าและหก

389
00:17:06,450 --> 00:17:08,390
ทั้งหมดที่ถูกต้องและเราจะมา
ถึงพวกคุณในครั้งต่อไป

390
00:17:08,390 --> 00:17:09,640
สิทธิทั้งหมดมาขึ้น

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> สิทธิทั้งหมดเนื่องจากคุณขึ้นที่นี่เป็นครั้งแรก,
คุณอยากจะเป็นหนึ่งอย่างเชื่องช้า

393
00:17:14,819 --> 00:17:16,119
ในแก้ว Google ที่นี่?

394
00:17:16,119 --> 00:17:19,075
ทั้งหมดขวาดังนั้นตกลงแก้ว
บันทึกวิดีโอ

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
ตกลงคุณจะดีไป

397
00:17:24,589 --> 00:17:27,950
>> ขวาทั้งหมดดังนั้นหากพวกคุณสามารถมา
ที่นี่ผมได้เตรียมล่วงหน้า

398
00:17:27,950 --> 00:17:30,110
ตัวเลขบางอย่าง

399
00:17:30,110 --> 00:17:31,240
สิทธิทั้งหมดมาที่นี่

400
00:17:31,240 --> 00:17:33,440
และทำไมคุณไม่ไปเล็ก ๆ น้อย ๆ
อีกวิธีการที่

401
00:17:33,440 --> 00:17:35,520
และขอดูสิ่งที่ชื่อของคุณ
กับแก้ว Google?

402
00:17:35,520 --> 00:17:35,910
>> นักเรียน: เบน

403
00:17:35,910 --> 00:17:36,230
>> 1 SPEAKER: เบน

404
00:17:36,230 --> 00:17:38,380
ตกลงเบนคุณจะเป็นครั้งแรกอย่างแท้จริง

405
00:17:38,380 --> 00:17:40,580
ดังนั้นเรากำลังจะไปส่ง
ไปยังจุดสิ้นสุดของเวที

406
00:17:40,580 --> 00:17:41,670
ขวาทั้งหมดและชื่อของคุณ?

407
00:17:41,670 --> 00:17:41,990
>> นักเรียน: เจสัน

408
00:17:41,990 --> 00:17:44,530
>> ลำโพง 1: เจสันตกลงคุณจะ
เป็นหมายเลขเก้า

409
00:17:44,530 --> 00:17:46,700
ดังนั้นหากคุณต้องการที่จะทำตามวิธีการที่เบน

410
00:17:46,700 --> 00:17:47,010
>> นักเรียน: จิลล์

411
00:17:47,010 --> 00:17:49,630
>> 1 SPEAKER: จิลล์ที่คุณกำลังจะได้รับ
17 ซึ่งถ้าผมทำขึ้นนี้

412
00:17:49,630 --> 00:17:51,260
อย่างชาญฉลาดที่ผมจะต้อง
เริ่มต้นที่ปลายอีกด้านหนึ่ง

413
00:17:51,260 --> 00:17:52,370
คุณไปทางนั้น

414
00:17:52,370 --> 00:17:53,030
22

415
00:17:53,030 --> 00:17:53,670
และคุณคืออะไร?

416
00:17:53,670 --> 00:17:53,980
>> นักเรียน: แมรี่

417
00:17:53,980 --> 00:17:56,130
>> 1 SPEAKER: แมรี่, คุณจะ 22

418
00:17:56,130 --> 00:17:58,420
และชื่อของคุณคืออะไร?

419
00:17:58,420 --> 00:17:58,810
>> นักเรียน: คริส

420
00:17:58,810 --> 00:18:00,100
>> ลำโพง 1: คริส, คุณจะ 26

421
00:18:00,100 --> 00:18:00,740
แล้วสุดท้าย

422
00:18:00,740 --> 00:18:01,400
>> นักเรียน: ไดอาน่า

423
00:18:01,400 --> 00:18:02,670
>> 1 SPEAKER: Diana, คุณจะ 34

424
00:18:02,670 --> 00:18:03,920
ดังนั้นคุณจึงมาที่นี่

425
00:18:03,920 --> 00:18:06,360
>> ทั้งหมดที่เหมาะสมเพื่อให้สมบูรณ์แบบเรียง
การสั่งซื้อสินค้าเรียบร้อยแล้ว

426
00:18:06,360 --> 00:18:09,600
และให้ไปข้างหน้าและทำเช่นนี้
เพื่อให้เราสามารถจริงๆ -

427
00:18:09,600 --> 00:18:11,720
เบนคุณเพียงแค่ชนิดของการมอง
ออกไปไม่มีที่ไหนมี

428
00:18:11,720 --> 00:18:15,670
OK เพื่อให้เป็นไปข้างหน้าและเห็นภาพนี้
โดยใช้แขนมากเหมือนผมตรง,

429
00:18:15,670 --> 00:18:16,250
สิ่งที่เกิดขึ้น

430
00:18:16,250 --> 00:18:19,540
เพื่อไปข้างหน้าและให้ตัวเอง
หรือสองเท้าระหว่างตัวเอง

431
00:18:19,540 --> 00:18:22,900
และไปข้างหน้าและชี้ด้วยมือข้างหนึ่งไป
ใครก็ตามที่คุณควรจะชี้ไปที่

432
00:18:22,900 --> 00:18:23,470
บนพื้นฐานนี้

433
00:18:23,470 --> 00:18:25,890
และถ้าคุณเพียงแค่ชี้โมฆะ
ตรงลงไปกองกับพื้น

434
00:18:25,890 --> 00:18:27,690
ตกลงที่ดีเพื่อให้

435
00:18:27,690 --> 00:18:32,290
>> ดังนั้นตอนนี้เรามีรายการที่เชื่อมโยงและให้ฉัน
เสนอว่าผมจะเล่นบทบาทของ

436
00:18:32,290 --> 00:18:35,110
PTR ดังนั้นฉันจะไม่รำคาญ
แบกรอบนี้

437
00:18:35,110 --> 00:18:37,830
และจากนั้น - คนโง่ประชุม -
คุณสามารถเรียกสิ่งที่คุณต้องการนี​​้ -

438
00:18:37,830 --> 00:18:39,800
ตัวชี้บรรพบุรุษของตัวชี้ pred -

439
00:18:39,800 --> 00:18:43,930
เป็นเพียงชื่อเล่นเราให้ใน
โค้ดตัวอย่างของเราที่จะมือซ้ายของฉัน

440
00:18:43,930 --> 00:18:47,240
มืออื่น ๆ ที่จะได้รับการรักษา
ติดตามใครเป็นใครใน

441
00:18:47,240 --> 00:18:48,400
สถานการณ์ต่อไปนี้

442
00:18:48,400 --> 00:18:52,390
>> ดังนั้นคิดว่าครั้งแรกที่ผมต้องการที่จะฉีก
ว่าตัวอย่างแรกของการแทรกพูด

443
00:18:52,390 --> 00:18:54,330
20 ลงในรายการ

444
00:18:54,330 --> 00:18:57,160
ดังนั้นฉันจะต้องการใครซักคน
รวบรวมจำนวน 20 สำหรับเรา

445
00:18:57,160 --> 00:18:58,950
ดังนั้นผมจึงจำเป็นที่จะต้องมีคน malloc
จากผู้ชม

446
00:18:58,950 --> 00:18:59,380
มาขึ้น

447
00:18:59,380 --> 00:19:00,340
คุณชื่ออะไร?

448
00:19:00,340 --> 00:19:01,300
>> นักเรียน: ไบรอัน

449
00:19:01,300 --> 00:19:05,270
>> ลำโพง 1: ไบรอันขวาทั้งหมดเพื่อให้คุณ
จะต้องเป็นโหนดที่มี 20

450
00:19:05,270 --> 00:19:06,810
สิทธิทั้งหมดมาที่นี่

451
00:19:06,810 --> 00:19:10,025
และเห็นได้ชัดว่าที่
ไบรอันไม่เป็น?

452
00:19:10,025 --> 00:19:12,190
ดังนั้นในช่วงกลางของ - จริง,
เดี๋ยวก่อน

453
00:19:12,190 --> 00:19:13,420
เรากำลังทำเช่นนี้การออกคำสั่ง

454
00:19:13,420 --> 00:19:17,170
เรากำลังทำนี้ยากมาก
กว่าที่จะต้องมีในตอนแรก

455
00:19:17,170 --> 00:19:21,210
ตกลงเราจะฟรีไบรอัน
และไบรอัน realloc ที่สุดเท่าที่ห้า

456
00:19:21,210 --> 00:19:23,680
>> ตกลงดังนั้นตอนนี้เราต้องการที่จะแทรก
ไบรอันที่ห้า

457
00:19:23,680 --> 00:19:25,960
ดังนั้นเมื่อมาที่นี่ต่อไป
เบนรอสักครู่

458
00:19:25,960 --> 00:19:28,250
และคุณน่าจะสามารถบอกได้
ซึ่งเรื่องนี้เป็นไป

459
00:19:28,250 --> 00:19:30,500
แต่ขอให้คิดอย่างรอบคอบเกี่ยวกับ
การดำเนินงานเพื่อ

460
00:19:30,500 --> 00:19:32,880
และมันก็เป็นอย่างแม่นยำภาพนี้
ที่กำลังจะเริ่มขึ้น

461
00:19:32,880 --> 00:19:34,080
ที่มีรหัสตัวอย่างที่

462
00:19:34,080 --> 00:19:40,120
ดังนั้นที่นี่ฉันมี PTR ชี้แรก
ไม่ได้อยู่ที่เบนต่อ se แต่อย่างใด

463
00:19:40,120 --> 00:19:43,245
เขามีค่าซึ่งในกรณีนี้
คือ - ชื่ออะไรของคุณอีกครั้ง?

464
00:19:43,245 --> 00:19:43,670
>> นักเรียน: เจสัน

465
00:19:43,670 --> 00:19:47,350
>> ลำโพง 1: เจสันดังนั้นทั้งเบนและฉันเป็น
ชี้ไปที่เจสันในขณะนี้

466
00:19:47,350 --> 00:19:49,700
ดังนั้นตอนนี้ฉันมีที่จะกำหนด
ที่ไบรอันไม่เป็น?

467
00:19:49,700 --> 00:19:53,500
ดังนั้นสิ่งเดียวที่ฉันจะสามารถเข้าถึง
ตอนนี้ยังไม่มีรายการข้อมูลเป็นของเขา

468
00:19:53,500 --> 00:19:58,280
ดังนั้นฉันจะตรวจสอบคือ
ไบรอันน้อยกว่าเจสัน?

469
00:19:58,280 --> 00:19:59,770
คำตอบที่เป็นความจริง

470
00:19:59,770 --> 00:20:03,680
>> ดังนั้นตอนนี้สิ่งที่จะเกิดขึ้น
ในลำดับที่ถูกต้อง?

471
00:20:03,680 --> 00:20:07,120
ผมจำเป็นต้องปรับปรุงตัวชี้หลายวิธี
ทั้งหมดในเรื่องนี้?

472
00:20:07,120 --> 00:20:10,720
ที่มือของฉันก็ยังคงชี้ไปที่
เจสันและมือของคุณ - ถ้าคุณต้องการ

473
00:20:10,720 --> 00:20:12,930
ใส่มือของคุณเช่นการเรียงลำดับของผม
ไม่ทราบว่าเครื่องหมายคำถาม

474
00:20:12,930 --> 00:20:14,070
ตกลงที่ดี

475
00:20:14,070 --> 00:20:15,670
>> ทั้งหมดที่ถูกต้องเพื่อให้คุณมี
ผู้สมัครไม่กี่

476
00:20:15,670 --> 00:20:20,500
ทั้งเบนหรือฉันหรือไบรอันหรือเจสัน
ทุกคนหรืออื่น ๆ ซึ่ง

477
00:20:20,500 --> 00:20:21,370
ชี้ต้องเปลี่ยน?

478
00:20:21,370 --> 00:20:23,260
วิธีการหลายอย่างในทั้งหมด?

479
00:20:23,260 --> 00:20:24,080
>> ตกลงดังนั้นสอง

480
00:20:24,080 --> 00:20:27,090
ตัวชี้ที่ฉันไม่ได้เรื่องจริงๆอีกต่อไป
เพราะฉันเพียงชั่วคราวเท่านั้น

481
00:20:27,090 --> 00:20:31,370
ดังนั้นมันจึงเหล่านี้สองคนสมมุติ
ทั้งเบนและไบรอัน

482
00:20:31,370 --> 00:20:34,410
เพื่อให้ฉันเสนอว่าเรา update
เบนเขาตั้งแต่แรก

483
00:20:34,410 --> 00:20:36,350
องค์ประกอบแรกของรายการนี​​้
คือตอนนี้จะเป็นไบรอัน

484
00:20:36,350 --> 00:20:38,070
ดังนั้นเบนจุดที่ไบรอัน

485
00:20:38,070 --> 00:20:39,320
ตกลงตอนนี้เป็นอย่างไร

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> ผู้ที่ได้รับชี้ไปที่ใคร?

488
00:20:43,460 --> 00:20:44,710
>> ลูกศิษย์: [ได้ยิน]

489
00:20:44,710 --> 00:20:46,180
>> 1 SPEAKER: ตกลงเพื่อให้มีไบรอัน
ไปยังจุดที่เจสัน

490
00:20:46,180 --> 00:20:48,360
ฉันได้ แต่สูญเสียการติดตามของตัวชี้ว่า

491
00:20:48,360 --> 00:20:49,980
ฉันรู้ว่าเจสันคืออะไร?

492
00:20:49,980 --> 00:20:50,790
>> ลูกศิษย์: [ได้ยิน]

493
00:20:50,790 --> 00:20:52,620
>> ลำโพง 1: I do, ตั้งแต่ฉัน
ตัวชี้ชั่วคราว

494
00:20:52,620 --> 00:20:55,110
และสันนิษฐานว่าผมยังไม่ได้เปลี่ยน
เพื่อชี้ไปที่โหนดใหม่

495
00:20:55,110 --> 00:20:58,300
ดังนั้นเราก็สามารถมีจุดไบรอัน
ที่ใครก็ตามที่ผมชี้ไปที่

496
00:20:58,300 --> 00:20:59,000
และเรากำลังทำ

497
00:20:59,000 --> 00:21:01,890
ดังนั้นกรณีหนึ่งที่แทรก
จุดเริ่มต้นของรายการ

498
00:21:01,890 --> 00:21:02,950
มีสองขั้นตอนสำคัญคือ

499
00:21:02,950 --> 00:21:06,750
หนึ่งเราต้องปรับปรุงเบนแล้ว
เรายังต้องปรับปรุงไบรอัน

500
00:21:06,750 --> 00:21:09,230
และแล้วฉันไม่ต้องกังวล
Traipsing ผ่านส่วนที่เหลือของ

501
00:21:09,230 --> 00:21:12,680
รายการเพราะเรารู้อยู่แล้วว่าของเขา
สถานที่เพราะเขาเป็น

502
00:21:12,680 --> 00:21:14,080
ด้านซ้ายขององค์ประกอบแรก

503
00:21:14,080 --> 00:21:15,400
>> ทั้งหมดขวาเพื่อตรงไปตรงสวย

504
00:21:15,400 --> 00:21:18,110
ในความเป็นจริงความรู้สึกเหมือนเราเกือบ
การนี​​้ซับซ้อนเกินไป

505
00:21:18,110 --> 00:21:20,240
ดังนั้นตอนนี้ขอถอนปิดท้าย
ของรายการและดูว่า

506
00:21:20,240 --> 00:21:21,380
ความซับซ้อนจะเริ่มต้น

507
00:21:21,380 --> 00:21:24,560
ดังนั้นถ้าตอนนี้ฉัน alloc จากผู้ชม

508
00:21:24,560 --> 00:21:25,540
ทุกคนต้องการที่จะเล่น 55?

509
00:21:25,540 --> 00:21:26,700
ทั้งหมดขวาฉันเห็นมือของคุณเป็นครั้งแรก

510
00:21:26,700 --> 00:21:29,620
มาขึ้น

511
00:21:29,620 --> 00:21:30,030
ใช่

512
00:21:30,030 --> 00:21:31,177
คุณชื่ออะไร?

513
00:21:31,177 --> 00:21:32,310
>> ลูกศิษย์: [ได้ยิน]

514
00:21:32,310 --> 00:21:33,240
>> 1 SPEAKER: Habata

515
00:21:33,240 --> 00:21:33,890
ตกลงมาขึ้น

516
00:21:33,890 --> 00:21:35,730
คุณจะ 55 จำนวน

517
00:21:35,730 --> 00:21:37,820
ดังนั้นคุณแน่นอนไม่ได้เป็นสมาชิก
ในตอนท้ายของรายการ

518
00:21:37,820 --> 00:21:41,850
ดังนั้นขอเล่นใหม่จำลองกับฉัน
เป็น PTR รอสักครู่

519
00:21:41,850 --> 00:21:44,050
ดังนั้นฉันแรกจะไปจุดที่
สิ่งที่เบนชี้ไปที่

520
00:21:44,050 --> 00:21:45,900
เรากำลังทั้งสองชี้ไปที่ไบรอัน

521
00:21:45,900 --> 00:21:48,420
ดังนั้น 55 มีจำนวนไม่น้อยกว่าห้า

522
00:21:48,420 --> 00:21:52,510
ดังนั้นฉันจะปรับปรุงตัวเองโดย
ชี้ไปที่ตัวชี้ต่อไปของไบรอันที่

523
00:21:52,510 --> 00:21:54,450
ขณะนี้เป็นหลักสูตรที่เจสัน

524
00:21:54,450 --> 00:21:57,310
55 ไม่น้อยกว่าเก้าดังนั้น
ฉันจะปรับปรุง PTR

525
00:21:57,310 --> 00:21:58,890
ฉันจะปรับปรุง PTR

526
00:21:58,890 --> 00:22:02,290
ฉันจะปรับปรุง PTR
ผมจะ update PTR

527
00:22:02,290 --> 00:22:05,060
และฉันจะไป - อืมอะไร
ชื่อของคุณอีกครั้ง?

528
00:22:05,060 --> 00:22:05,560
>> นักเรียน: ไดอาน่า

529
00:22:05,560 --> 00:22:09,190
>> ลำโพง 1: ไดอาน่าชี้ของหลักสูตร
ที่โมฆะด้วยมือซ้ายของเธอ

530
00:22:09,190 --> 00:22:13,030
เพื่อที่ Habata ไม่จริง
เป็นอย่างชัดเจน?

531
00:22:13,030 --> 00:22:15,050
ไปทางซ้ายที่นี่

532
00:22:15,050 --> 00:22:19,460
ดังนั้นฉันจะรู้ว่าเธอจะใส่ที่นี่
ฉันคิดว่าฉันเมาขึ้น

533
00:22:19,460 --> 00:22:22,420
เพราะเป็นสิ่ง PTR ศิลปะ
ขณะที่ในเวลานี้?

534
00:22:22,420 --> 00:22:23,240
Null

535
00:22:23,240 --> 00:22:25,580
ดังนั้นแม้ว่าสายตาเราสามารถ
เห็นได้ชัดว่าได้เห็นสิ่งเหล่านี้

536
00:22:25,580 --> 00:22:26,610
ผู้ชายที่นี่บนเวที

537
00:22:26,610 --> 00:22:29,680
ฉันไม่ได้เฝ้าติดตามก่อนหน้านี้
คนที่อยู่ในรายชื่อ

538
00:22:29,680 --> 00:22:33,210
ฉันไม่ได้มีนิ้วชี้ออก,
ในกรณีนี้จำนวนโหนด 34

539
00:22:33,210 --> 00:22:34,760
>> ดังนั้นขอเริ่มต้นจริงมากกว่านี้

540
00:22:34,760 --> 00:22:37,560
ดังนั้นตอนนี้ที่จริงผมจะต้อง
ตัวแปรท้องถิ่นที่สอง

541
00:22:37,560 --> 00:22:40,980
และนี่คือสิ่งที่คุณจะเห็นใน
ตัวอย่างรหัสจริง C, ขณะที่ผมไป

542
00:22:40,980 --> 00:22:45,860
เมื่อ update ขวามือของเราที่จะชี้ให้
เจสัน, ไบรอันจึงออกจากที่อยู่เบื้องหลังผม

543
00:22:45,860 --> 00:22:51,440
ดีกว่าเริ่มใช้มือซ้ายของฉันไป
ปรับปรุงที่ผมเพื่อให้ผมไป

544
00:22:51,440 --> 00:22:52,700
ผ่านรายการนี​​้ -

545
00:22:52,700 --> 00:22:55,040
มากขึ้นอย่างเชื่องช้ากว่าที่ฉันตั้งใจ
ตอนนี้ที่นี่สายตา -

546
00:22:55,040 --> 00:22:56,740
ฉันจะได้รับ
ตอนท้ายของรายการ

547
00:22:56,740 --> 00:23:00,020
>> มือนี่ยังคงเป็นโมฆะที่สวย
ไร้ประโยชน์อื่น ๆ มากกว่าที่จะแสดงให้เห็นว่า

548
00:23:00,020 --> 00:23:02,980
ฉันได้อย่างชัดเจนในตอนท้ายของรายการ,
แต่ตอนนี้อย่างน้อยฉันมีนี้

549
00:23:02,980 --> 00:23:08,270
ตัวชี้บรรพบุรุษชี้ที่นี่ดังนั้น
ตอนนี้สิ่งที่มือและสิ่งที่ตัวชี้ต้อง

550
00:23:08,270 --> 00:23:10,150
ได้รับการปรับปรุง?

551
00:23:10,150 --> 00:23:13,214
ที่มีมือที่คุณต้องการ
กำหนดค่าเป็นอันดับแรก

552
00:23:13,214 --> 00:23:15,190
>> ลูกศิษย์: [ได้ยิน]

553
00:23:15,190 --> 00:23:16,220
>> 1 SPEAKER: OK เพื่อให้เจ้าหญิงไดอาน่า

554
00:23:16,220 --> 00:23:21,110
คุณต้องการไปยังจุดที่
ตัวชี้ซ้ายของเจ้าหญิงไดอาน่าที่?

555
00:23:21,110 --> 00:23:23,620
ที่ 55, สันนิษฐานว่าเพื่อให้
เราได้แทรกมี

556
00:23:23,620 --> 00:23:25,560
และสถานที่ที่ 55 ตัวชี้ควรจะไป?

557
00:23:25,560 --> 00:23:27,000
ลงคิดเป็นโมฆะ

558
00:23:27,000 --> 00:23:28,890
และมือของฉันที่จุดนี้ไม่ได้
สำคัญเพราะพวกเขาเพียง

559
00:23:28,890 --> 00:23:30,070
ตัวแปรชั่วคราว

560
00:23:30,070 --> 00:23:31,030
ดังนั้นตอนนี้เรากำลังทำ

561
00:23:31,030 --> 00:23:34,650
>> ดังนั้นซับซ้อนเพิ่มเติมมี - และ
มันไม่ยากที่จะดำเนินการ

562
00:23:34,650 --> 00:23:38,660
แต่เราจำเป็นต้องมีตัวแปรรองที่จะทำให้
แน่ใจแล้วหรือว่าก่อนที่ผมจะย้ายไปทางขวาของฉัน

563
00:23:38,660 --> 00:23:42,140
มือผมปรับปรุงค่าของฉันซ้าย
มือชี้ pred ในกรณีนี้ดังนั้น

564
00:23:42,140 --> 00:23:45,860
ว่าฉันมีตัวชี้ลาก
เพื่อติดตามว่าผมอยู่ที่ไหน

565
00:23:45,860 --> 00:23:49,360
ตอนนี้เป็นกันถ้าคุณคิดว่านี้
ผ่านนี้รู้สึกเหมือนมันเป็น

566
00:23:49,360 --> 00:23:51,490
เล็ก ๆ น้อย ๆ ที่น่ารำคาญที่จะมีการเก็บ
ติดตามมือซ้ายนี้

567
00:23:51,490 --> 00:23:54,015
>> สิ่งที่จะแก้ปัญหาอื่น
เพื่อแก้ไขปัญหานี้ได้รับ?

568
00:23:54,015 --> 00:23:56,500
หากคุณมีการออกแบบข้อมูล
โครงสร้างเรากำลังพูดถึง

569
00:23:56,500 --> 00:23:59,630
ผ่านได้ในขณะนี้?

570
00:23:59,630 --> 00:24:02,690
ถ้าเป็นแค่ความรู้สึกเล็ก ๆ น้อย ๆ
ที่น่ารำคาญจะมีเหมือนสองตัวชี้

571
00:24:02,690 --> 00:24:08,430
จะผ่านรายการให้ใครสามารถ
ได้ในโลกที่เหมาะการบำรุงรักษา

572
00:24:08,430 --> 00:24:10,160
ข้อมูลที่เราต้อง?

573
00:24:10,160 --> 00:24:11,360
อ้าง?

574
00:24:11,360 --> 00:24:12,610
>> ลูกศิษย์: [ได้ยิน]

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> 1 ลำโพงว่า

577
00:24:16,150 --> 00:24:19,130
ขวาจึงมีความจริงที่น่าสนใจ
เชื้อโรคของความคิด

578
00:24:19,130 --> 00:24:22,470
และความคิดของตัวชี้หน้าที่นี้
ชี้ไปที่องค์ประกอบหน้าที่แล้ว

579
00:24:22,470 --> 00:24:25,580
ถ้าฉันเพียงแค่ว่าเป็นตัวเป็นตน
ด้านในของตัวรายการเอง?

580
00:24:25,580 --> 00:24:27,810
และมันจะเป็นเรื่องยากที่จะเห็นภาพ
โดยไม่ต้องทั้งหมดกระดาษ

581
00:24:27,810 --> 00:24:28,830
ล้มลงไปที่พื้น

582
00:24:28,830 --> 00:24:31,860
แต่คิดว่าคนเหล่านี้ใช้ทั้ง
จากมือของพวกเขาจะมีหน้าที่

583
00:24:31,860 --> 00:24:35,950
ตัวชี้และตัวชี้ต่อไปดังนั้น
การดำเนินการสิ่งที่เราจะเรียกเป็นทวีคูณ

584
00:24:35,950 --> 00:24:36,830
รายการที่เชื่อมโยง

585
00:24:36,830 --> 00:24:41,090
ที่จะช่วยให้ผมที่จะจัดเรียงย้อนกลับ
มากขึ้นได้อย่างง่ายดายโดยไม่ต้องฉัน

586
00:24:41,090 --> 00:24:43,800
โปรแกรมเมอร์ที่มีให้
ติดตามด้วยตนเอง -

587
00:24:43,800 --> 00:24:44,980
อย่างแท้จริงด้วยตนเอง -

588
00:24:44,980 --> 00:24:47,280
จากที่ผมเคยเป็น
ในรายการ

589
00:24:47,280 --> 00:24:48,110
ดังนั้นเราจะไม่ทำอย่างนั้น

590
00:24:48,110 --> 00:24:50,950
เราจะให้มันง่ายเพราะนั่นคือ
จะมาในราคาสองเท่า

591
00:24:50,950 --> 00:24:53,450
พื้นที่มากสำหรับตัวชี้,
ถ้าคุณต้องการที่หนึ่งที่สอง

592
00:24:53,450 --> 00:24:55,760
แต่ที่จริงที่พบบ่อย
โครงสร้างข้อมูลที่เรียกว่า

593
00:24:55,760 --> 00:24:57,410
รายการที่เชื่อมโยงเป็นทวีคูณ

594
00:24:57,410 --> 00:25:01,310
>> ขอทำตัวอย่างสุดท้ายที่นี่และวาง
คนเหล่านี้ออกจากความทุกข์ยากของพวกเขา

595
00:25:01,310 --> 00:25:03,270
ดังนั้น 20 malloc

596
00:25:03,270 --> 00:25:05,320
มาขึ้นมาจากทางเดินมี

597
00:25:05,320 --> 00:25:06,280
ขวาทั้งหมด, คุณชื่ออะไร?

598
00:25:06,280 --> 00:25:07,440
>> ลูกศิษย์: [ได้ยิน]

599
00:25:07,440 --> 00:25:07,855
>> ลำโพง 1: ขอโทษ?

600
00:25:07,855 --> 00:25:08,480
>> ลูกศิษย์: [ได้ยิน]

601
00:25:08,480 --> 00:25:09,410
>> 1 SPEAKER: Demeron

602
00:25:09,410 --> 00:25:10,230
ตกลงมาขึ้น

603
00:25:10,230 --> 00:25:11,910
คุณจะต้องเป็น 20

604
00:25:11,910 --> 00:25:14,720
คุณชัดจะไป
อยู่ระหว่าง 17 และ 22

605
00:25:14,720 --> 00:25:16,150
เพื่อให้ฉันเรียนรู้บทเรียนของฉัน

606
00:25:16,150 --> 00:25:18,150
ฉันจะเริ่มต้นชี้
ชี้ไปที่ไบรอัน

607
00:25:18,150 --> 00:25:21,190
และฉันจะมีมือซ้ายของฉัน
เพียง แต่ปรับปรุงให้ไบรอันที่ผมย้ายไป

608
00:25:21,190 --> 00:25:23,600
เจสันตรวจสอบไม่น้อยกว่า 20 เก้า?

609
00:25:23,600 --> 00:25:24,060
เลขที่

610
00:25:24,060 --> 00:25:25,430
คือ 20 น้อยกว่า 17?

611
00:25:25,430 --> 00:25:25,880
เลขที่

612
00:25:25,880 --> 00:25:27,450
คือ 20 น้อยกว่า 22?

613
00:25:27,450 --> 00:25:28,440
ใช่

614
00:25:28,440 --> 00:25:34,070
ดังนั้นตัวชี้อะไรหรือมือจำเป็นต้องเปลี่ยน
ที่พวกเขากำลังชี้อยู่ตอนนี้

615
00:25:34,070 --> 00:25:37,070
>> ดังนั้นเราจึงสามารถทำ 17 ชี้ไปที่ 20

616
00:25:37,070 --> 00:25:37,860
ดังนั้นที่ดี

617
00:25:37,860 --> 00:25:40,080
เราไม่ต้องการไปยังจุดที่
ตัวชี้ของคุณตอนนี้

618
00:25:40,080 --> 00:25:41,330
วันที่ 22

619
00:25:41,330 --> 00:25:45,410
และเรารู้ว่า 22 คือขอบคุณอีกครั้ง
ตัวชี้ชั่วคราวของฉัน

620
00:25:45,410 --> 00:25:46,760
ดังนั้นเราจึงไม่ตกลงมี

621
00:25:46,760 --> 00:25:49,440
เพราะจากการจัดเก็บชั่วคราวนี้
ฉันเฝ้าติดตามที่ทุกคนเป็น

622
00:25:49,440 --> 00:25:55,055
และตอนนี้คุณมองเห็นสามารถไปในที่ที่
คุณอยู่และตอนนี้เราจำเป็นต้อง 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 ลูกความเครียด
และรอบปรบมือสำหรับ

624
00:25:58,410 --> 00:25:59,770
คนพวกนี้ถ้าเราทำได้

625
00:25:59,770 --> 00:26:00,410
ทำได้อย่างดี

626
00:26:00,410 --> 00:26:05,320
>> [APPLAUSE]

627
00:26:05,320 --> 00:26:06,330
>> ลำโพง 1: ทั้งหมดขวา

628
00:26:06,330 --> 00:26:09,860
และคุณอาจเก็บชิ้น
ของกระดาษที่เป็นของที่ระลึก

629
00:26:09,860 --> 00:26:15,930
>> ทั้งหมดขวาดังนั้นเชื่อฉันมันมาก
ง่ายต่อการเดินผ่านว่า

630
00:26:15,930 --> 00:26:17,680
มนุษย์มากกว่าที่เป็นอยู่ด้วยรหัสที่เกิดขึ้นจริง

631
00:26:17,680 --> 00:26:22,690
แต่สิ่งที่คุณจะพบในเวลาเพียงสักครู่
ตอนนี้จะเหมือนกันว่า - โอ้ขอบคุณคุณ

632
00:26:22,690 --> 00:26:23,630
ขอบคุณ -

633
00:26:23,630 --> 00:26:29,360
คือการที่คุณจะพบว่าข้อมูลที่เหมือนกัน
โครงสร้างรายการที่เชื่อมโยงสามารถจริง

634
00:26:29,360 --> 00:26:33,200
จะใช้เป็นอาคารตึกไปมากยิ่งขึ้น
โครงสร้างข้อมูลที่มีความซับซ้อน

635
00:26:33,200 --> 00:26:37,620
>> และตระหนักเกินไปธีมที่นี่เป็นที่
เราได้รับการแนะนำอย่างมาก

636
00:26:37,620 --> 00:26:40,060
ความซับซ้อนในการดำเนินการ
ของขั้นตอนวิธีนี้

637
00:26:40,060 --> 00:26:43,940
แทรกและถ้าเราเดินผ่านมัน
การลบและการค้นหาเป็นเล็ก ๆ น้อย ๆ

638
00:26:43,940 --> 00:26:46,660
ซับซ้อนมากขึ้นกว่ามัน
เป็นกับอาร์เรย์

639
00:26:46,660 --> 00:26:48,040
แต่เราได้รับบางอย่างแคล่วคล่อง

640
00:26:48,040 --> 00:26:50,180
เราได้รับข้อมูลโครงสร้างการปรับตัว

641
00:26:50,180 --> 00:26:54,010
>> แต่อีกครั้งที่เราจ่ายราคาของการมีบาง
ความซับซ้อนที่เพิ่มขึ้นทั้งใน

642
00:26:54,010 --> 00:26:54,910
การดำเนินการนั้น

643
00:26:54,910 --> 00:26:56,750
และเราได้รับการเข้าถึงแบบสุ่ม

644
00:26:56,750 --> 00:27:00,450
และจะซื่อสัตย์มีไม่ดีบางอย่าง
ทำความสะอาดสไลด์ที่ฉันสามารถให้คุณว่า

645
00:27:00,450 --> 00:27:03,120
พูดว่าที่นี่ทำไมรายการที่เชื่อมโยงเป็น
จะดีกว่าอาร์เรย์

646
00:27:03,120 --> 00:27:04,100
และออกมาว่า

647
00:27:04,100 --> 00:27:07,520
เพราะรูปแบบ reoccurring ตอนนี้แม้
มากขึ้นดังนั้นในสัปดาห์ที่ผ่านมาคือ

648
00:27:07,520 --> 00:27:10,200
ว่ามีไม่จำเป็นต้อง
คำตอบที่ถูกต้อง

649
00:27:10,200 --> 00:27:13,830
>> นี่คือเหตุผลที่เรามีแกนแยก
ของการออกแบบสำหรับชุดปัญหา

650
00:27:13,830 --> 00:27:17,700
มันจะเป็นบริบทที่สำคัญมาก
ไม่ว่าคุณต้องการที่จะใช้ข้อมูลนี้

651
00:27:17,700 --> 00:27:21,750
โครงสร้างหรือการที่หนึ่งและมันจะ
ขึ้นอยู่กับสิ่งที่สำคัญกับคุณในแง่

652
00:27:21,750 --> 00:27:24,620
ของทรัพยากรและความซับซ้อน

653
00:27:24,620 --> 00:27:28,830
>> แต่ให้ฉันเสนอว่าเหมาะสำหรับข้อมูลที่
โครงสร้างจอกศักดิ์สิทธิ์จะ

654
00:27:28,830 --> 00:27:32,200
สิ่งที่เวลาคงที่,
โดยไม่คำนึงถึงวิธีการที่สิ่งที่เป็นมาก

655
00:27:32,200 --> 00:27:36,940
ภายในนั้นมันจะไม่น่าตื่นตาตื่นใจถ้า
โครงสร้างข้อมูลที่ส่งกลับคำตอบใน

656
00:27:36,940 --> 00:27:37,920
เวลาคง

657
00:27:37,920 --> 00:27:38,330
ใช่

658
00:27:38,330 --> 00:27:40,110
คำนี้อยู่ในพจนานุกรมขนาดใหญ่ของคุณ

659
00:27:40,110 --> 00:27:41,550
หรือไม่มีคำนี้ไม่ได้

660
00:27:41,550 --> 00:27:43,270
หรือมีปัญหาดังกล่าว

661
00:27:43,270 --> 00:27:46,360
ดีขอดูว่าเราไม่ได้เป็นอย่างน้อย
จะใช้ขั้นตอนต่อว่า

662
00:27:46,360 --> 00:27:50,190
>> ผมขอเสนอโครงสร้างข้อมูลใหม่ที่
สามารถใช้สำหรับสิ่งที่แตกต่าง

663
00:27:50,190 --> 00:27:52,260
ในกรณีนี้เรียกว่าตารางแฮช

664
00:27:52,260 --> 00:27:55,590
และเพื่อให้เราไม่จริงกลับไปแฉลบ
ที่อาร์เรย์ในกรณีนี้และ

665
00:27:55,590 --> 00:28:00,550
ค่อนข้างพลฉันวาดนี้
ตารางแฮชเป็นอาร์เรย์ที่มีการเรียงลำดับของ

666
00:28:00,550 --> 00:28:02,810
อาร์เรย์สองมิติ -

667
00:28:02,810 --> 00:28:05,410
หรือมากกว่านั้นที่นี่เป็นภาพสอง
อาร์เรย์มิติ - แต่นี้เป็นเพียง

668
00:28:05,410 --> 00:28:10,770
อาร์เรย์ของ 26 ขนาดดังกล่าวว่าถ้าเรา
เรียกตารางอาร์เรย์วงเล็บตาราง

669
00:28:10,770 --> 00:28:12,440
ศูนย์เป็นรูปสี่เหลี่ยมผืนผ้าที่ด้านบน

670
00:28:12,440 --> 00:28:15,090
วงเล็บตาราง 25 เป็นรูปสี่เหลี่ยมผืนผ้า
ที่ด้านล่าง

671
00:28:15,090 --> 00:28:18,620
และนี่คือวิธีการที่ฉันอาจดึงข้อมูล
โครงสร้างในการที่ฉันต้องการเก็บ

672
00:28:18,620 --> 00:28:19,790
ชื่อคน

673
00:28:19,790 --> 00:28:24,370
>> ดังนั้นสำหรับตัวอย่างเช่นและฉันจะไม่วาด
สิ่งทั้งหมดที่นี่ค่าใช้จ่ายถ้าฉัน

674
00:28:24,370 --> 00:28:29,160
มีอาร์เรย์นี้ซึ่งตอนนี้ฉันจะไป
เรียกตารางแฮชและนี่คืออีกครั้ง

675
00:28:29,160 --> 00:28:31,360
สถานที่ตั้งศูนย์

676
00:28:31,360 --> 00:28:34,840
นี้ที่นี่เป็นที่ตั้ง
หนึ่งและอื่น ๆ

677
00:28:34,840 --> 00:28:37,880
ผมอ้างว่าผมต้องการที่จะใช้ข้อมูลนี้
โครงสร้างเพื่อประโยชน์ของการสนทนา,

678
00:28:37,880 --> 00:28:42,600
การจัดเก็บชื่อของผู้คน, Alice และ Bob
และชาร์ลีและชื่ออื่น ๆ เช่น

679
00:28:42,600 --> 00:28:46,110
ดังนั้นคิดว่าตอนนี้เป็นจุดเริ่มต้น
ของการพูดพจนานุกรม

680
00:28:46,110 --> 00:28:47,520
ที่มีจำนวนมากของคำ

681
00:28:47,520 --> 00:28:49,435
พวกเขาเกิดขึ้นจะเป็นชื่อ
ในตัวอย่างของเราที่นี่

682
00:28:49,435 --> 00:28:52,560
และนี่คือทั้งหมดซึ่งเกี่ยวดองกันอย่างใกล้ชิดเกินไปบางที
การดำเนินการตรวจสอบการสะกดในขณะที่เรา

683
00:28:52,560 --> 00:28:54,400
สำหรับปัญหาอาจตั้งหก

684
00:28:54,400 --> 00:28:59,300
>> ดังนั้นถ้าเรามีอาร์เรย์ของขนาดรวม 26
เพื่อที่ว่านี้เป็นสถานที่ที่ 25

685
00:28:59,300 --> 00:29:03,390
ที่ด้านล่างและฉันอ้างว่าเป็นอลิซ
คำแรกในพจนานุกรมของ

686
00:29:03,390 --> 00:29:07,260
ชื่อที่ผมต้องการแทรกลงใน RAM,
เป็นโครงสร้างข้อมูลนี้อยู่ที่ไหน

687
00:29:07,260 --> 00:29:12,480
สัญชาตญาณบอกคุณว่าอลิซ
ชื่อควรจะไปในอาร์เรย์นี้

688
00:29:12,480 --> 00:29:13,510
>> เรามี 26 ตัวเลือก

689
00:29:13,510 --> 00:29:14,990
ที่เราต้องการที่จะนำเธอ?

690
00:29:14,990 --> 00:29:16,200
เราต้องการให้เธออยู่ในวงเล็บเป็นศูนย์ใช่มั้ย?

691
00:29:16,200 --> 00:29:18,280
อลิซขอเรียกว่าเป็นศูนย์

692
00:29:18,280 --> 00:29:20,110
และจะเป็นหนึ่ง, และ C จะมีสอง

693
00:29:20,110 --> 00:29:22,600
ดังนั้นเรากำลังจะเขียน
ชื่อของอลิซที่นี่

694
00:29:22,600 --> 00:29:24,890
ถ้าเราแล้วใส่บ๊อบของเขา
ชื่อจะไปที่นี่

695
00:29:24,890 --> 00:29:27,280
ชาร์ลีจะไปที่นี่

696
00:29:27,280 --> 00:29:30,500
และอื่น ๆ ลงผ่าน
นี้โครงสร้างข้อมูล

697
00:29:30,500 --> 00:29:32,090
>> นี้เป็นโครงสร้างข้อมูลที่ยอดเยี่ยม

698
00:29:32,090 --> 00:29:32,730
ทำไม?

699
00:29:32,730 --> 00:29:37,460
ดีเวลาทำงานของเป็นสิ่งที่
ใส่ชื่อของมนุษย์เป็นแบบนี้

700
00:29:37,460 --> 00:29:39,850
โครงสร้างข้อมูลในตอนนี้?

701
00:29:39,850 --> 00:29:43,702
ระบุว่าตารางนี้จะดำเนินการ
อย่างแท้จริงเป็นอาร์เรย์

702
00:29:43,702 --> 00:29:44,940
ดีก็ถึงเวลาที่คงที่

703
00:29:44,940 --> 00:29:45,800
มันเป็นคำสั่งของหนึ่ง

704
00:29:45,800 --> 00:29:46,360
ทำไม?

705
00:29:46,360 --> 00:29:48,630
>> ดีอย่างไรคุณกำหนด
ที่อลิซเป็น?

706
00:29:48,630 --> 00:29:51,000
คุณดูที่ตัวอักษรของชื่อของเธอ?

707
00:29:51,000 --> 00:29:51,490
เป็นครั้งแรก

708
00:29:51,490 --> 00:29:54,350
และคุณจะได้รับมีถ้ามันสตริง,
โดยเพียงแค่มองไปที่สตริง

709
00:29:54,350 --> 00:29:55,200
ศูนย์วงเล็บ

710
00:29:55,200 --> 00:29:57,110
ดังนั้นตัวละคร 0 ของสตริง

711
00:29:57,110 --> 00:29:57,610
ที่ง่าย

712
00:29:57,610 --> 00:30:00,350
เราได้ว่าในการเข้ารหัสลับ
สัปดาห์ที่ผ่านมาที่ได้รับมอบหมาย

713
00:30:00,350 --> 00:30:05,310
และแล้วเมื่อคุณรู้ว่าอลิซ
ตัวอักษรเป็นเมืองหลวงเราสามารถลบ

714
00:30:05,310 --> 00:30:08,160
ออก 65 หรือเงินทุนตัวเอง
ที่จะช่วยให้เราเป็นศูนย์

715
00:30:08,160 --> 00:30:10,940
ดังนั้นตอนนี้เรารู้ว่าอลิซเป็น
ที่ศูนย์ที่ตั้ง

716
00:30:10,940 --> 00:30:14,240
>> และได้รับการชี้ไปยังข้อมูลนี้
โครงสร้างของการจัดเรียงบางอย่างนานแค่ไหน

717
00:30:14,240 --> 00:30:18,840
มันพาฉันไปหาสถานที่
เป็นศูนย์ในอาร์เรย์?

718
00:30:18,840 --> 00:30:22,080
เพียงหนึ่งขั้นตอนที่ถูกต้องถึงเวลาที่คงที่
เพราะเข้าถึงโดยสุ่มเรา

719
00:30:22,080 --> 00:30:23,780
ที่นำเสนอเป็นคุณลักษณะของอาร์เรย์

720
00:30:23,780 --> 00:30:28,570
ดังนั้นในระยะสั้น, การหาสิ่งที่ดัชนี
ชื่อของอลิซเป็นซึ่งก็คือใน

721
00:30:28,570 --> 00:30:32,610
กรณีนี้หรือให้เพียงแก้ไข
ที่เป็นศูนย์ที่ B เป็นหนึ่งและ C คือ

722
00:30:32,610 --> 00:30:34,900
สองการหาที่ออก
เป็นเวลาที่คงที่

723
00:30:34,900 --> 00:30:38,510
ผมเพียงแค่ต้องมองไปที่ตัวอักษรตัวแรกของเธอ
การหาสถานที่ที่เป็นศูนย์

724
00:30:38,510 --> 00:30:40,460
แถวนี้ยังมีเวลาคง

725
00:30:40,460 --> 00:30:42,140
ดังนั้นในทางเทคนิคที่
เช่นเดียวกับขั้นตอนที่สองในขณะนี้

726
00:30:42,140 --> 00:30:43,330
แต่ที่ยังคงคงที่

727
00:30:43,330 --> 00:30:46,880
ดังนั้นเราจึงเรียกว่า O ใหญ่ของหนึ่งดังนั้นเราได้
อลิซแทรกลงในตารางนี้

728
00:30:46,880 --> 00:30:48,440
เวลาคง

729
00:30:48,440 --> 00:30:50,960
>> แต่แน่นอนว่าผมเป็น
ไร้เดียงสาที่นี่ใช่มั้ย?

730
00:30:50,960 --> 00:30:53,240
เกิดอะไรขึ้นถ้ามีแอรอนในชั้นเรียน?

731
00:30:53,240 --> 00:30:53,990
หรือ? อลิเซีย

732
00:30:53,990 --> 00:30:57,230
หรือชื่ออื่น ๆ ที่เริ่มต้นด้วย
A. เราจะไปที่ไหนที่จะใส่

733
00:30:57,230 --> 00:31:00,800
คนนั้นใช่มั้ย?

734
00:31:00,800 --> 00:31:03,420
ผมหมายถึงตอนนี้มีเพียงสาม
คนบนโต๊ะดังนั้นบางทีเรา

735
00:31:03,420 --> 00:31:07,490
ควรใส่แอรอนที่ตั้ง
ศูนย์หนึ่งสองสาม

736
00:31:07,490 --> 00:31:09,480
>> ขวาฉันสามารถวางที่นี่

737
00:31:09,480 --> 00:31:13,350
แต่แล้วถ้าเราพยายามแทรกเข้าไปเดวิด
รายการนี​​้ที่ดาวิดไป?

738
00:31:13,350 --> 00:31:15,170
ตอนนี้ระบบของเราจะเริ่มต้นการทำลาย
ลงขวา?

739
00:31:15,170 --> 00:31:19,210
เพราะตอนนี้เดวิดจบลงที่นี่
ถ้าแอรอนเป็นจริงที่นี่

740
00:31:19,210 --> 00:31:23,060
และดังนั้นตอนนี้ความคิดทั้งหมดของการมี
โครงสร้างข้อมูลที่สะอาดที่จะช่วยให้เรา

741
00:31:23,060 --> 00:31:28,010
แทรกเวลาคงไม่ได้
เวลาคงเพราะฉันต้อง

742
00:31:28,010 --> 00:31:31,240
ตรวจสอบโอ้ Damnit คนที่มีอยู่แล้ว
ที่ตั้งของอลิซ

743
00:31:31,240 --> 00:31:35,320
>> ผมขอแสดงความคิดเห็นส่วนที่เหลือของข้อมูลนี้
โครงสร้างที่กำลังมองหาจุดที่จะใส่

744
00:31:35,320 --> 00:31:37,130
ใครบางคนเช่นชื่อของแอรอน

745
00:31:37,130 --> 00:31:39,390
และอื่น ๆ ที่เกินไปจะเริ่มต้น
ที่จะใช้เวลาเชิงเส้น

746
00:31:39,390 --> 00:31:42,710
นอกจากนี้หากคุณต้องการที่จะหา
แอรอนในนี้โครงสร้างข้อมูลและคุณ

747
00:31:42,710 --> 00:31:45,430
ตรวจสอบและชื่อของแอรอนไม่ได้ที่นี่

748
00:31:45,430 --> 00:31:47,960
เป็นการดีที่คุณเพียงแค่จะบอกว่าแอรอน
ไม่ได้อยู่ในโครงสร้างข้อมูล

749
00:31:47,960 --> 00:31:51,530
แต่ถ้าคุณทำเริ่มทำห้องพักสำหรับ
แอรอนที่มีควรจะได้รับ D

750
00:31:51,530 --> 00:31:55,600
หรือ E, คุณ, กรณีที่เลวร้ายที่สุดมีการตรวจสอบ
โครงสร้างข้อมูลทั้งใน

751
00:31:55,600 --> 00:31:59,480
ซึ่งในกรณีนี้มันเป็นสิ่งที่ devolves
เชิงเส้นในขนาดของตาราง

752
00:31:59,480 --> 00:32:00,920
>> ดังนั้นสิทธิทั้งหมดที่ฉันจะแก้ไขปัญหานี้

753
00:32:00,920 --> 00:32:04,200
ปัญหาที่นี่คือที่ฉันมี
26 องค์ประกอบในอาร์เรย์นี้

754
00:32:04,200 --> 00:32:05,000
ผมขอเปลี่ยนเป็น

755
00:32:05,000 --> 00:32:06,010
ขออภัย

756
00:32:06,010 --> 00:32:10,600
ผมขอเปลี่ยนมันเพื่อให้ค่อนข้างเป็นอยู่ของ
26 ขนาดทั้งหมดแจ้งให้ทราบด้านล่าง

757
00:32:10,600 --> 00:32:12,720
ดัชนีจะเปลี่ยนถึง n ลบ 1

758
00:32:12,720 --> 00:32:16,610
ถ้า 26 เห็นได้ชัดว่ามีขนาดเล็กเกินไปสำหรับมนุษย์ '
ชื่อเพราะมีหลายพัน

759
00:32:16,610 --> 00:32:20,830
ชื่อของโลกที่ให้เพียงทำให้
ใน 100 หรือ 1,000 หรือ 10,000

760
00:32:20,830 --> 00:32:22,960
ขอเพียงจัดสรรพื้นที่มากขึ้น

761
00:32:22,960 --> 00:32:27,230
>> ดีว่าไม่จำเป็นต้องลดลง
ความน่าจะเป็นว่าเราจะไม่มีสอง

762
00:32:27,230 --> 00:32:31,510
คนที่มีชื่อเริ่มต้นด้วยและ
เพื่อให้คุณได้ไปลองใส่

763
00:32:31,510 --> 00:32:33,120
ชื่อที่ศูนย์สถานที่ยังคง

764
00:32:33,120 --> 00:32:36,850
พวกเขายังคงที่จะไปชนกันซึ่ง
หมายความว่าเรายังคงต้องแก้ปัญหาที่จะใส่

765
00:32:36,850 --> 00:32:41,020
อลิซและแอรอนและอลิเซียและอื่น ๆ
ชื่อที่เริ่มต้นด้วยที่อื่น ๆ

766
00:32:41,020 --> 00:32:43,460
แต่วิธีการที่มากของปัญหานี้คืออะไร?

767
00:32:43,460 --> 00:32:46,870
ความน่าจะเป็นอะไรที่คุณ
มีการชนกันในข้อมูล

768
00:32:46,870 --> 00:32:48,240
โครงสร้างเช่นนี้หรือไม่

769
00:32:48,240 --> 00:32:52,570
>> ดีให้ฉัน - เราจะกลับมา
คำถามที่นี่ที่

770
00:32:52,570 --> 00:32:55,530
และดูที่วิธีการที่เราอาจจะ
แก้มันเป็นครั้งแรก

771
00:32:55,530 --> 00:32:58,480
ผมขอดึงข้อเสนอนี้ที่นี่

772
00:32:58,480 --> 00:33:02,020
สิ่งที่เราเพียงแค่อธิบายเป็นขั้นตอนวิธี,
การแก้ปัญหาที่เรียกว่าเส้น

773
00:33:02,020 --> 00:33:05,030
ละเอียดด้วยเหตุนี้ถ้าคุณพยายามที่จะแทรก
บางสิ่งบางอย่างที่นี่ในข้อมูลนี้

774
00:33:05,030 --> 00:33:08,920
โครงสร้างซึ่งเรียกว่าตารางแฮช,
และมีห้องพักไม่ได้มีคุณ

775
00:33:08,920 --> 00:33:12,000
อย่างแท้จริงการสอบสวนโครงสร้างข้อมูล
การตรวจสอบนี้สามารถใช้ได้?

776
00:33:12,000 --> 00:33:13,430
สามารถใช้ได้นี้นี้สามารถใช้ได้?

777
00:33:13,430 --> 00:33:13,980
นี้สามารถใช้ได้?

778
00:33:13,980 --> 00:33:17,550
และเมื่อในที่สุดมันก็คือค​​ุณใส่
ชื่อที่คุณตั้งใจ

779
00:33:17,550 --> 00:33:19,370
ที่อื่น ๆ ที่ตำแหน่งนั้น

780
00:33:19,370 --> 00:33:23,360
แต่ในกรณีที่เลวร้ายที่สุดจุดเดียว
อาจจะมีที่ด้านล่างสุดของข้อมูล

781
00:33:23,360 --> 00:33:25,090
โครงสร้างท้ายสุดของอาร์เรย์

782
00:33:25,090 --> 00:33:30,130
>> เชิงเส้นดังนั้นการตรวจสอบในกรณีที่เลวร้ายที่สุด
devolves เป็นอัลกอริทึมเชิงเส้นที่

783
00:33:30,130 --> 00:33:34,500
แอรอนถ้าเขาเกิดขึ้นจะแทรกล่าสุด
ในโครงสร้างข้อมูลนี้เขาอาจจะ

784
00:33:34,500 --> 00:33:39,540
ชนกับสถานที่นี้เป็นครั้งแรก แต่
แล้วจบลงด้วยความโชคร้ายที่ส่วนท้ายสุด

785
00:33:39,540 --> 00:33:43,940
ดังนั้นนี้ไม่คงที่
เวลาจอกศักดิ์สิทธิ์สำหรับเรา

786
00:33:43,940 --> 00:33:47,650
วิธีการนี​​้ขององค์ประกอบใส่ลงใน
โครงสร้างข้อมูลที่เรียกว่ากัญชา

787
00:33:47,650 --> 00:33:52,050
ตารางไม่ได้ดูเหมือนจะเป็นเวลาที่คงที่
อย่างน้อยก็ไม่ใช่ในกรณีทั่วไป

788
00:33:52,050 --> 00:33:54,000
มันสามารถตกทอดเป็นสิ่งที่เป็นเส้นตรง

789
00:33:54,000 --> 00:33:56,970
>> ดังนั้นสิ่งที่ถ้าเราแก้ปัญหาการชนกัน
ค่อนข้างแตกต่างกัน?

790
00:33:56,970 --> 00:34:00,740
ดังนั้นนี่คือความซับซ้อนมากขึ้น
ใกล้กับสิ่งที่ยังคง

791
00:34:00,740 --> 00:34:02,800
ที่เรียกว่าตารางแฮช

792
00:34:02,800 --> 00:34:05,890
และกัญชาเป็นกันสิ่งที่
ผมหมายถึงคือดัชนีที่

793
00:34:05,890 --> 00:34:07,070
ผมหมายถึงก่อนหน้านี้

794
00:34:07,070 --> 00:34:09,810
เพื่อสิ่งที่กัญชาสามารถ
คิดว่าเป็นคำกริยา

795
00:34:09,810 --> 00:34:13,690
>> ดังนั้นหากคุณกัญชาชื่ออลิซ,
ฟังก์ชันแฮชเพื่อที่จะพูด,

796
00:34:13,690 --> 00:34:14,710
ควรกลับจำนวน

797
00:34:14,710 --> 00:34:18,199
ในกรณีนี้เป็นศูนย์ถ้าเธอเป็นที่
สถานที่ตั้งศูนย์หนึ่งถ้าเธอเป็นที่

798
00:34:18,199 --> 00:34:20,000
หนึ่งในสถานที่และอื่น ๆ

799
00:34:20,000 --> 00:34:24,360
ดังนั้นฟังก์ชันแฮชของฉันป่านนี้ได้รับ
ง่ายสุดเพียงมองหาที่

800
00:34:24,360 --> 00:34:26,159
ตัวอักษรตัวแรกในชื่อของใครบางคน

801
00:34:26,159 --> 00:34:29,090
แต่ฟังก์ชันแฮชจะใช้เวลาเป็น
ป้อนชิ้นส่วนบางส่วนของข้อมูล,

802
00:34:29,090 --> 00:34:30,210
สตริง, int สิ่งที่

803
00:34:30,210 --> 00:34:32,239
และมันมักจะถ่มน้ำลายออกมาเป็นจำนวนมาก

804
00:34:32,239 --> 00:34:35,739
และจำนวนที่อยู่ที่ข้อมูลที่
เป็นองค์ประกอบในโครงสร้างข้อมูล

805
00:34:35,739 --> 00:34:37,800
รู้จักที่นี่ในฐานะตารางแฮช

806
00:34:37,800 --> 00:34:41,400
>> ดังนั้นเพียงแค่สังหรณ์ใจนี้เป็น
บริบทที่แตกต่างกันเล็กน้อย

807
00:34:41,400 --> 00:34:44,170
นี้ที่จริงหมายถึงตัวอย่าง
วันเกิดที่เกี่ยวข้องกับการที่

808
00:34:44,170 --> 00:34:46,850
อาจจะมีมากที่สุดเท่าที่
31 วันในเดือน

809
00:34:46,850 --> 00:34:52,239
แต่สมาชิกผู้นี้ไม่ว่าสิ่งที่ตัดสินใจที่จะ
ในกรณีที่การปะทะกัน?

810
00:34:52,239 --> 00:34:55,304
บริบทในขณะนี้ถูกไม่ได้ปะทะกันของ
ชื่อ แต่การปะทะกันของวันเกิด,

811
00:34:55,304 --> 00:35:00,760
ถ้าคนสองคนที่มีวันคล้ายวันเกิดเดียวกัน
2 ของเดือนตุลาคมเช่น

812
00:35:00,760 --> 00:35:02,120
>> ลูกศิษย์: [ได้ยิน]

813
00:35:02,120 --> 00:35:05,010
>> 1 SPEAKER: Yeah ดังนั้นที่นี่เรามี
ใช้ประโยชน์จากการเชื่อมโยงรายการ

814
00:35:05,010 --> 00:35:07,830
ดังนั้นดูเหมือนน้อยแตกต่างกัน
กว่าที่เราดึงมันก่อนหน้านี้

815
00:35:07,830 --> 00:35:10,790
แต่เราดูเหมือนจะมีไปยังอาร์เรย์
บนด้านซ้ายมือ

816
00:35:10,790 --> 00:35:13,230
นั่นเป็นดัชนีหนึ่งสำหรับการไม่มี
เหตุผลโดยเฉพาะอย่างยิ่ง

817
00:35:13,230 --> 00:35:14,630
แต่ก็ยังคงอาร์เรย์

818
00:35:14,630 --> 00:35:16,160
มันเป็นอาร์เรย์ของตัวชี้

819
00:35:16,160 --> 00:35:20,670
และแต่ละองค์ประกอบเหล่านั้นแต่ละ
วงการเหล่านี้หรือ slashes - เฉือน

820
00:35:20,670 --> 00:35:23,970
null แทน - แต่ละเหล่านี้
เห็นได้ชัดว่าเป็นตัวชี้ชี้ไปที่

821
00:35:23,970 --> 00:35:25,730
สิ่งโครงสร้างข้อมูล?

822
00:35:25,730 --> 00:35:26,890
รายการที่เชื่อมโยง

823
00:35:26,890 --> 00:35:30,530
>> ดังนั้นตอนนี้เรามีความสามารถในการ
ยากรหัสในโปรแกรมของเรา

824
00:35:30,530 --> 00:35:32,010
ขนาดของตาราง

825
00:35:32,010 --> 00:35:35,360
ในกรณีนี้เรารู้ว่าไม่เคยมี
กว่า 31 วันในเดือน

826
00:35:35,360 --> 00:35:38,480
ดังนั้นค่าการเข้ารหัสยากเช่น 31 คือ
ที่เหมาะสมในบริบทที่

827
00:35:38,480 --> 00:35:42,700
ในบริบทของชื่อยาก coding
26 ไม่ใช่ไม่มีเหตุผลมันของผู้คน

828
00:35:42,700 --> 00:35:46,340
เฉพาะชื่อเริ่มต้นด้วยตัวอย่างเช่น
ที่เกี่ยวข้องกับตัวอักษรถึง Z

829
00:35:46,340 --> 00:35:50,180
>> เราสามารถอัดพวกเขาทั้งหมดเป็นข้อมูลที่
โครงสร้างตราบเท่าที่เมื่อเราได้รับ

830
00:35:50,180 --> 00:35:55,330
การปะทะกันเราไม่ได้ใส่ชื่อที่นี่
เราคิดแทนของเซลล์เหล่านี้

831
00:35:55,330 --> 00:36:00,270
ไม่ได้เป็นสตริงตัวเอง แต่เป็น
ตัวชี้ไปยังตัวอย่างเช่นอลิซ

832
00:36:00,270 --> 00:36:03,660
แล้วอลิซสามารถมีตัวชี้อื่น
กับชื่อที่เริ่มต้นด้วยอีก

833
00:36:03,660 --> 00:36:06,150
A. และบ๊อบจริงไปกว่าที่นี่

834
00:36:06,150 --> 00:36:10,850
>> และถ้ามีชื่อเริ่มต้นของผู้อื่น
ต่อ B เขาสิ้นสุดขึ้นกว่าที่นี่

835
00:36:10,850 --> 00:36:15,070
และเพื่อให้แต่ละองค์ประกอบของการนี​​้
สองตารางถ้าเราออกแบบนี้

836
00:36:15,070 --> 00:36:17,350
เล็ก ๆ น้อย ๆ อย่างชาญฉลาด -

837
00:36:17,350 --> 00:36:18,125
มา -

838
00:36:18,125 --> 00:36:22,950
ถ้าเราได้รับการออกแบบนี้น้อยมาก
ชาญฉลาดในขณะนี้จะกลายเป็นข้อมูลการปรับตัว

839
00:36:22,950 --> 00:36:27,720
โครงสร้างที่ไม่มีขีด จำกัด ยาก
เกี่ยวกับวิธีการหลายองค์ประกอบคุณสามารถแทรก

840
00:36:27,720 --> 00:36:30,700
เป็นมันเพราะถ้าคุณมี
การปะทะกันที่ดี

841
00:36:30,700 --> 00:36:34,690
เพียงแค่ไปข้างหน้าและต่อท้ายไป
สิ่งที่เราเห็นบิตที่ผ่านมาคือ

842
00:36:34,690 --> 00:36:38,290
ที่รู้จักกันเป็นรายการที่เชื่อมโยง

843
00:36:38,290 --> 00:36:39,690
>> หยุดดีขอรอสักครู่

844
00:36:39,690 --> 00:36:42,570
น่าจะเป็นของการปะทะกันคืออะไร
ในสถานที่แรก?

845
00:36:42,570 --> 00:36:45,480
ขวาบางทีฉันคิดไปอาจจะ
ฉันกว่าวิศวกรรมปัญหานี้

846
00:36:45,480 --> 00:36:46,370
เพราะคุณรู้ว่าสิ่งที่?

847
00:36:46,370 --> 00:36:49,070
ใช่ฉันสามารถขึ้นมาโดยพลการ
ตัวอย่างที่ปิดด้านบนของหัวของฉันเช่น

848
00:36:49,070 --> 00:36:52,870
แอลลิสันและแอรอน แต่ในความเป็นจริง
ได้รับการจัดจำหน่ายเครื่องแบบ

849
00:36:52,870 --> 00:36:56,990
ปัจจัยการผลิตที่มีบางแทรกสุ่ม
เป็นโครงสร้างข้อมูลเป็นสิ่งที่เป็นจริง

850
00:36:56,990 --> 00:36:58,580
น่าจะเป็นของการปะทะกัน?

851
00:36:58,580 --> 00:37:01,670
กันจะเปิดออกก็จริง
สูงสุด

852
00:37:01,670 --> 00:37:03,850
ให้ฉันพูดคุยนี้
ปัญหาเป็นเช่นนี้

853
00:37:03,850 --> 00:37:08,890
>> ดังนั้นในห้องพักของ n CS50 นักเรียนอะไร
ความน่าจะเป็นว่าอย่างน้อย

854
00:37:08,890 --> 00:37:11,010
นักเรียนสองคนในห้อง
มีวันคล้ายวันเกิดเดียวกัน

855
00:37:11,010 --> 00:37:13,346
ดังนั้นจึงไม่มีอะไร Hund ไม่กี่ -

856
00:37:13,346 --> 00:37:16,790
200, 300 คนที่นี่และอีกหลายคน
ร้อยคนที่บ้านวันนี้

857
00:37:16,790 --> 00:37:20,670
ดังนั้นถ้าคุณต้องการที่จะถามตัวเองว่ามีอะไร
ความน่าจะเป็นของคนสองคน

858
00:37:20,670 --> 00:37:23,930
ในห้องที่มีวันคล้ายวันเกิดเดียวกันนี้
เราสามารถคิดออกนี้

859
00:37:23,930 --> 00:37:26,250
และฉันเรียกร้องจริงมีสอง
คนที่มีวันคล้ายวันเกิดเดียวกัน

860
00:37:26,250 --> 00:37:29,560
>> ยกตัวอย่างเช่นไม่มีใคร
มีวันคล้ายวันเกิดในวันนี้?

861
00:37:29,560 --> 00:37:31,340
เมื่อวานนี้?

862
00:37:31,340 --> 00:37:32,590
วันพรุ่งนี้?

863
00:37:32,590 --> 00:37:35,980
ขวาทั้งหมดจึงรู้สึกเหมือนฉันไป
ที่จะมีการทำเช่นนี้ 363 หรือดังนั้นขึ้น

864
00:37:35,980 --> 00:37:39,500
ครั้งที่จริงคิดออก
ถ้าเราจะมีการปะทะกัน

865
00:37:39,500 --> 00:37:42,350
หรือเราก็สามารถทำเช่นนี้ในทางคณิตศาสตร์
มากกว่าที่จะเบื่อหน่าย

866
00:37:42,350 --> 00:37:43,200
การทำเช่นนี้

867
00:37:43,200 --> 00:37:44,500
และนำเสนอต่อไปนี้

868
00:37:44,500 --> 00:37:48,740
>> ดังนั้นผมจึงเสนอว่าเราสามารถสร้างแบบจำลอง
ความน่าจะเป็นของคนสองคนที่มี

869
00:37:48,740 --> 00:37:55,320
เช่นเดียวกับวันเกิดน่าจะเป็นของ 1
ลบน่าจะเป็นของหนึ่งจะไม่มี

870
00:37:55,320 --> 00:37:56,290
วันเกิดเดียวกัน

871
00:37:56,290 --> 00:37:59,960
เพื่อที่จะได้รับนี้และนี้เป็นเพียง
วิธีแฟนซีของการเขียนนี้สำหรับ

872
00:37:59,960 --> 00:38:03,090
คนแรกในห้องที่เขาหรือเธอ
สามารถมีหนึ่งที่เป็นไปได้ใด ๆ

873
00:38:03,090 --> 00:38:07,370
สมมติว่าวันเกิด 365 วันในปี,
ขอโทษด้วยที่บุคคลที่มี

874
00:38:07,370 --> 00:38:08,760
วันเกิด 29 กุมภาพันธ์

875
00:38:08,760 --> 00:38:13,470
>> ดังนั้นคนแรกในห้องนี้ฟรี
จะมีจำนวนวันเกิดใด ๆ

876
00:38:13,470 --> 00:38:18,280
ออกไปได้ 365 เพื่อให้
เราจะทำอย่างนั้น 365 หารด้วย 365

877
00:38:18,280 --> 00:38:18,990
ซึ่งเป็นหนึ่งใน

878
00:38:18,990 --> 00:38:22,700
คนถัดไปในห้องถ้าเป้าหมาย
คือการหลีกเลี่ยงการปะทะกัน, เท่านั้น

879
00:38:22,700 --> 00:38:26,460
มีวันเกิดของเธอหรือของเขาเกี่ยวกับวิธีการ
จำนวนวันที่เป็นไปได้แตกต่างกันอย่างไร

880
00:38:26,460 --> 00:38:27,610
364

881
00:38:27,610 --> 00:38:31,430
ดังนั้นในระยะที่สองในการแสดงออกนี้
ทำคณิตศาสตร์เป็นหลักว่าสำหรับเรา

882
00:38:31,430 --> 00:38:33,460
โดยการลบออกในวันหนึ่งที่เป็นไปได้

883
00:38:33,460 --> 00:38:36,390
และจากนั้นในวันรุ่งขึ้นในวันถัดไป
วันถัดลงไปจำนวน

884
00:38:36,390 --> 00:38:38,100
ของคนที่อยู่ในห้องพัก

885
00:38:38,100 --> 00:38:41,290
>> และถ้าเราพิจารณาแล้วจากนั้นก็คือสิ่งที่
ความน่าจะเป็นของทุกคนไม่ได้มี

886
00:38:41,290 --> 00:38:45,265
วันเกิดไม่ซ้ำกัน แต่อีก 1 ลบ
ว่าสิ่งที่เราได้รับคือการแสดงออก

887
00:38:45,265 --> 00:38:47,810
ที่สามารถนึกมาก
ลักษณะเช่นนี้

888
00:38:47,810 --> 00:38:50,330
แต่มันก็น่าสนใจมากขึ้น
ไปดูที่สายตา

889
00:38:50,330 --> 00:38:55,120
นี่เป็นแผนภูมิที่อยู่ในแกน x คือ
จำนวนของคนที่อยู่ในห้องพัก,

890
00:38:55,120 --> 00:38:56,180
จำนวนของวันเกิด

891
00:38:56,180 --> 00:38:59,840
เมื่อแกน y น่าจะเป็น
การปะทะกันของคนสองคน

892
00:38:59,840 --> 00:39:01,230
ที่มีวันคล้ายวันเกิดเดียวกัน

893
00:39:01,230 --> 00:39:05,020
>> and Takeaway จากเส้นโค้งนี้คือ
ว่าทันทีที่คุณได้รับจะชอบ 40

894
00:39:05,020 --> 00:39:11,110
นักเรียนคุณขึ้นที่ความน่าจะเป็น 90%
combinatorically สอง

895
00:39:11,110 --> 00:39:13,550
คนหรือมากกว่านั้นที่มี
วันเกิดเดียวกัน

896
00:39:13,550 --> 00:39:18,600
และเมื่อคุณได้รับจะชอบ 58 คนมัน
เกือบ 100% ของโอกาสที่สอง

897
00:39:18,600 --> 00:39:21,310
คนที่อยู่ในห้องจะมี
วันเกิดเดียวกันแม้ว่าจะมี

898
00:39:21,310 --> 00:39:26,650
365 หรือ 366 ถังเป็นไปได้และ
เพียง 58 คนในห้อง

899
00:39:26,650 --> 00:39:29,900
เพียงแค่สถิติที่คุณอาจจะ
ได้รับการชนกันซึ่งในระยะสั้น

900
00:39:29,900 --> 00:39:31,810
กระตุ้นการสนทนานี้

901
00:39:31,810 --> 00:39:35,890
ว่าแม้ว่าเราได้รับแฟนซีที่นี่และ
เริ่มมีเครือข่ายเหล่านี้เรายังคง

902
00:39:35,890 --> 00:39:36,950
จะมีการชนกัน

903
00:39:36,950 --> 00:39:42,710
>> เพื่อที่ begs คำถามสิ่งที่เป็น
ค่าใช้จ่ายในการดำเนินการแทรกและการลบ

904
00:39:42,710 --> 00:39:44,850
เป็นโครงสร้างข้อมูลเช่นนี้หรือไม่

905
00:39:44,850 --> 00:39:46,630
ดีให้ฉันเสนอ -

906
00:39:46,630 --> 00:39:51,570
และแจ้งให้เรากลับไปที่หน้าจอมากกว่า
ที่นี่ - ถ้าเรามีองค์ประกอบ n ใน

907
00:39:51,570 --> 00:39:56,330
รายการดังนั้นหากเรากำลังพยายามที่จะแทรก
องค์ประกอบ n และเรามี

908
00:39:56,330 --> 00:39:58,050
วิธีการหลายถังทั้งหมด?

909
00:39:58,050 --> 00:40:03,450
สมมติว่า 31 ถังทั้งหมด
ในกรณีของการเกิด

910
00:40:03,450 --> 00:40:09,240
ความยาวสูงสุดของหนึ่งอะไร
ของเครือข่ายเหล่านี้อาจเกิดขึ้น?

911
00:40:09,240 --> 00:40:12,670
>> ถ้ามีอีกครั้งที่เป็นไปได้ 31
วันเกิดในเดือนที่กำหนด

912
00:40:12,670 --> 00:40:14,580
และเราเพียงแค่การเกาะกลุ่มทุกคน -

913
00:40:14,580 --> 00:40:15,580
จริงที่เป็นตัวอย่างที่โง่

914
00:40:15,580 --> 00:40:16,960
ขอทำแทน 26

915
00:40:16,960 --> 00:40:20,890
ดังนั้นถ้าจะมีคนที่มีรายชื่อ
เริ่มต้นด้วยถึง Z จึงให้

916
00:40:20,890 --> 00:40:22,780
เรา 26 ดังกล่าว

917
00:40:22,780 --> 00:40:25,920
และเรากำลังใช้โครงสร้างข้อมูลเช่น
หนึ่งที่เราเพิ่งเห็นเหตุนี้เรามี

918
00:40:25,920 --> 00:40:30,210
อาร์เรย์ของตัวชี้ซึ่งแต่ละ
ชี้ไปยังรายการการเชื่อมโยงที่

919
00:40:30,210 --> 00:40:32,360
รายการแรกคือทุกคน
ที่มีชื่ออลิซ

920
00:40:32,360 --> 00:40:35,770
รายการที่สองคือทุก
ชื่อที่เริ่มต้นด้วยเริ่มต้น

921
00:40:35,770 --> 00:40:36,980
กับ B, และอื่น ๆ

922
00:40:36,980 --> 00:40:41,020
>> ระยะเวลาในแนวโน้มของแต่ละอะไร
รายการเหล่านั้นถ้าเราคิดดีสะอาด

923
00:40:41,020 --> 00:40:45,410
การกระจายของชื่อถึง Z
ข้ามโครงสร้างข้อมูลทั้ง?

924
00:40:45,410 --> 00:40:50,210
มีคน n ในโครงสร้างข้อมูลของ
หารด้วย 26 ถ้าพวกเขาเป็นอย่างดี

925
00:40:50,210 --> 00:40:52,110
กระจายออกไปทั้ง
โครงสร้างข้อมูล

926
00:40:52,110 --> 00:40:54,970
ดังนั้นความยาวของแต่ละเหล่านี้
โซ่เป็น n หารด้วย 26

927
00:40:54,970 --> 00:40:57,380
แต่ในสัญกรณ์โอใหญ่ว่าคืออะไร?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
ที่จริงคืออะไร?

930
00:41:02,440 --> 00:41:04,150
ดังนั้นจึงเป็นจริงๆ n เพียงขวา?

931
00:41:04,150 --> 00:41:06,620
เพราะเราได้กล่าวว่าในอดีตที่ผ่านมา
ว่าฮึคุณหารด้วย 26

932
00:41:06,620 --> 00:41:08,710
ใช่ในความเป็นจริงมันจะเร็ว

933
00:41:08,710 --> 00:41:12,720
แต่ในทางทฤษฎีจะไม่ลึกซึ้ง
ทั้งหมดที่ได้เร็วขึ้น

934
00:41:12,720 --> 00:41:16,040
>> ดังนั้นเราจึงไม่ได้ดูเหมือนจะเป็นสิ่งที่มาก
ใกล้ชิดกับจอกศักดิ์สิทธิ์นี้

935
00:41:16,040 --> 00:41:17,750
ในความเป็นจริงนี้เป็นเพียงเส้นเวลา

936
00:41:17,750 --> 00:41:20,790
Heck, ที่จุดนี้ไม่ได้ว่าทำไมเรา
ใช้เพียงหนึ่งรายการที่เชื่อมโยงอย่างมาก?

937
00:41:20,790 --> 00:41:23,510
ทำไมเราไม่ใช้เพียงหนึ่งขนาดใหญ่
อาร์เรย์ในการจัดเก็บชื่อของ

938
00:41:23,510 --> 00:41:25,010
ทุกคนในห้อง?

939
00:41:25,010 --> 00:41:28,280
ดีคือยังคงมีบางสิ่งบางอย่าง
ที่น่าสนใจเกี่ยวกับตารางกัญชา?

940
00:41:28,280 --> 00:41:30,810
คือยังคงมีบางสิ่งบางอย่างที่น่าสนใจ
เกี่ยวกับโครงสร้างข้อมูล

941
00:41:30,810 --> 00:41:33,940
ที่มีลักษณะเช่นนี้หรือไม่

942
00:41:33,940 --> 00:41:35,182
นี้

943
00:41:35,182 --> 00:41:37,050
>> ลูกศิษย์: [ได้ยิน]

944
00:41:37,050 --> 00:41:39,840
>> 1 ลำโพงขวาและอีกครั้งจะเป็นเพียง
อัลกอริทึมเวลาเชิงเส้นและ

945
00:41:39,840 --> 00:41:42,780
เวลาโครงสร้างเชิงเส้นข้อมูลทำไมถึงไม่ได้
เพียงแค่เก็บชื่อของทุกคนในขนาดใหญ่

946
00:41:42,780 --> 00:41:44,210
อาร์เรย์หรือในรายการที่เชื่อมโยงใหญ่?

947
00:41:44,210 --> 00:41:47,010
และหยุดการทำ CS ดังนั้นยากมาก
กว่าจะต้องมี?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
เป็นที่น่าสนใจเกี่ยวกับเรื่องนี้สิ่งที่แม้
แม้ว่าฉันมีรอยขีดข่วนมันออกมา?

950
00:41:53,190 --> 00:41:54,930
>> ลูกศิษย์: [ได้ยิน]

951
00:41:54,930 --> 00:41:57,040
>> 1 SPEAKER: แทรกไม่ได้?

952
00:41:57,040 --> 00:41:58,140
ราคาแพงอีกต่อไป

953
00:41:58,140 --> 00:42:03,390
ดังนั้นการแทรกอาจจะยังคง
เป็นเวลาที่คงที่แม้ว่าข้อมูลของคุณ

954
00:42:03,390 --> 00:42:07,910
โครงสร้างลักษณะเช่นนี้, array ของ
ตัวชี้แต่ละที่ชี้ไปที่

955
00:42:07,910 --> 00:42:09,550
อาจเป็นรายการที่เชื่อมโยง

956
00:42:09,550 --> 00:42:15,220
วิธีที่คุณสามารถบรรลุคงที่
แทรกเวลาของชื่อ?

957
00:42:15,220 --> 00:42:16,280
ติดในด้านหน้าขวา?

958
00:42:16,280 --> 00:42:19,290
>> ถ้าเราเสียสละเป้าหมายการออกแบบจาก
ก่อนหน้านี้ที่เราอยากให้

959
00:42:19,290 --> 00:42:22,650
ชื่อของทุกคนเช่นเรียงลำดับ
หรือทั้งหมดของตัวเลขที่อยู่บนเวทีที่เรียงลำดับ

960
00:42:22,650 --> 00:42:25,020
สมมติว่าเรามี
รายการที่เชื่อมโยงคัดเลือก

961
00:42:25,020 --> 00:42:29,960
มันเพียงค่าใช้จ่ายเราหนึ่งหรือสองขั้นตอน
เช่นเดียวกับในกรณีของเบนและไบรอัน

962
00:42:29,960 --> 00:42:32,750
ก่อนหน้านี้ที่จะแทรกองค์ประกอบที่
จุดเริ่มต้นของรายการ

963
00:42:32,750 --> 00:42:36,090
ดังนั้นหากเราไม่ดูแลเกี่ยวกับการเรียงลำดับทั้งหมด
ของชื่อที่เริ่มต้นด้วยส่วนหรือทั้งหมด

964
00:42:36,090 --> 00:42:39,660
ชื่อที่เริ่มต้นด้วย B เราสามารถยังคง
บรรลุแทรกตลอดเวลา

965
00:42:39,660 --> 00:42:43,900
ตอนนี้มองขึ้นไปอลิซหรือบ๊อบหรือชื่อใด ๆ
มากขึ้นโดยทั่วไปยังคงเป็นอะไร

966
00:42:43,900 --> 00:42:48,100
มัน O ใหญ่ของ N หารด้วย 26 ใน
กรณีที่ในฝันที่ทุกคนเหมือนกัน

967
00:42:48,100 --> 00:42:51,190
กระจายที่มีจำนวนมากเป็นของ
ที่มีซีซึ่งอาจเป็น

968
00:42:51,190 --> 00:42:52,220
ไม่สมจริง

969
00:42:52,220 --> 00:42:53,880
แต่ที่ยังคงเป็นเส้นตรง

970
00:42:53,880 --> 00:42:57,120
>> แต่ที่นี่เราจะกลับมาที่จุด
สัญกรณ์เชิงเป็น

971
00:42:57,120 --> 00:42:58,600
จริงในทางทฤษฎี

972
00:42:58,600 --> 00:43:02,960
แต่ในโลกแห่งความเป็นจริงถ้าผมอ้างว่า
โปรแกรมของฉันสามารถทำบางสิ่งบางอย่าง 26 ครั้ง

973
00:43:02,960 --> 00:43:06,210
ได้เร็วขึ้นกว่าของคุณซึ่งมีโปรแกรม
ที่คุณจะชอบใช้?

974
00:43:06,210 --> 00:43:09,660
ขอแสดงความนับถือหรือเหมืองซึ่ง
เป็นครั้งที่ 26 เร็วขึ้น?

975
00:43:09,660 --> 00:43:14,320
แนบเนียนบุคคลที่มีเป็น 26
ครั้งเร็วแม้ว่าในทางทฤษฎี

976
00:43:14,320 --> 00:43:18,790
อัลกอริทึมของเราทำงานในที่เดียวกัน
เวลาการทำงานเชิง

977
00:43:18,790 --> 00:43:20,940
>> ผมขอเสนอที่แตกต่างกัน
การแก้ปัญหาทั้งหมด

978
00:43:20,940 --> 00:43:24,380
และถ้านี้ไม่ได้พัดใจของคุณ
เราออกจากโครงสร้างข้อมูล

979
00:43:24,380 --> 00:43:27,420
ดังนั้นนี่จึงเป็นคู่ชีวิต -

980
00:43:27,420 --> 00:43:28,520
ชนิดของชื่อโง่

981
00:43:28,520 --> 00:43:32,880
มันมาจากการสืบค้นและคำว่า
คือการสะกดคำคู่ชีวิต, T-r-I-e เพราะ

982
00:43:32,880 --> 00:43:34,450
ดึงแน่นอนเสียงเหมือนคู่ชีวิต

983
00:43:34,450 --> 00:43:36,580
แต่ที่ประวัติศาสตร์
จากคำ Trie

984
00:43:36,580 --> 00:43:40,980
>> ดังนั้นคู่ชีวิตย่อมเป็นชนิดของต้นไม้บาง
และก็ยังมีการเล่นคำว่า

985
00:43:40,980 --> 00:43:46,330
และถึงแม้ว่าคุณไม่สามารถค่อนข้างจะเห็นมัน
กับการสร้างภาพนี้เป็นคู่ชีวิต

986
00:43:46,330 --> 00:43:50,790
ต้นไม้มีโครงสร้างเหมือนต้นไม้ครอบครัวที่มี
หนึ่งบรรพบุรุษที่ด้านบนและจำนวนมาก

987
00:43:50,790 --> 00:43:54,530
ของลูกหลานและเหลน
เป็นใบที่ด้านล่าง

988
00:43:54,530 --> 00:43:58,100
แต่โหนด Trie ในแต่ละแถว

989
00:43:58,100 --> 00:44:00,680
และมันก็เป็นในอาร์เรย์ - และขอ
oversimplify สักครู่ - มัน

990
00:44:00,680 --> 00:44:04,600
อาร์เรย์ในกรณีนี้จาก 26 ขนาดที่
แต่ละโหนดอีกครั้งเป็นอาร์เรย์ขนาด

991
00:44:04,600 --> 00:44:09,000
26 ที่ 0 องค์ประกอบในการที่
อาร์เรย์เป็นตัวแทนและสุดท้าย

992
00:44:09,000 --> 00:44:11,810
องค์ประกอบดังกล่าวในแต่ละ
อาร์เรย์แทนซี

993
00:44:11,810 --> 00:44:15,520
>> ดังนั้นผมจึงนำเสนอแล้วว่าข้อมูลนี้
โครงสร้างที่รู้จักกันเป็นคู่ชีวิตสามารถ

994
00:44:15,520 --> 00:44:17,600
นอกจากนี้ยังใช้ในการจัดเก็บคำ

995
00:44:17,600 --> 00:44:21,740
เราเห็นสักครู่ที่ผ่านมาวิธีการที่เราสามารถเก็บ
คำหรือในกรณีที่ชื่อนี้และเรา

996
00:44:21,740 --> 00:44:25,440
เห็นก่อนหน้านี้วิธีการที่เราสามารถจัดเก็บตัวเลข
แต่ถ้าเรามุ่งเน้นไปที่ชื่อหรือสตริง

997
00:44:25,440 --> 00:44:27,460
ที่นี่แจ้งให้ทราบว่ามีอะไรที่น่าสนใจ

998
00:44:27,460 --> 00:44:32,210
ผมอ้างว่าเป็นชื่อของแมกซ์เวล
ภายในของโครงสร้างข้อมูลนี้

999
00:44:32,210 --> 00:44:33,730
คุณจะดูแมกซ์เวลที่ไหน?

1000
00:44:33,730 --> 00:44:35,140
>> ลูกศิษย์: [ได้ยิน]

1001
00:44:35,140 --> 00:44:36,240
>> 1 ลำโพงด้านซ้าย

1002
00:44:36,240 --> 00:44:39,910
ดังนั้นที่น่าสนใจกับข้อมูลนี้สิ่ง
โครงสร้างเป็นมากกว่าร้านค้า

1003
00:44:39,910 --> 00:44:46,200
สตริง M--X-W-E-L-L เครื่องหมายทับขวาเป็นศูนย์ทั้งหมด
ติดกันสิ่งที่คุณทำแทน

1004
00:44:46,200 --> 00:44:46,890
คือต่อไปนี้

1005
00:44:46,890 --> 00:44:50,510
ถ้าเป็นคู่ชีวิตเช่นโครงสร้างข้อมูล,
แต่ละโหนดที่เป็นอีกครั้งที่อาร์เรย์

1006
00:44:50,510 --> 00:44:54,650
และคุณต้องการเก็บแมกซ์เวลแรกคุณ
ดัชนีและเพื่อให้โหนดรากของดังนั้น

1007
00:44:54,650 --> 00:44:57,810
การพูดโหนดบนสุด,
ที่ตั้ง M ขวาดังนั้น

1008
00:44:57,810 --> 00:44:59,160
ลวกเข้ากลาง

1009
00:44:59,160 --> 00:45:03,740
แล้วจากที่นั่นคุณทำตาม
ตัวชี้ไปยังโหนดลูกเพื่อที่จะพูด

1010
00:45:03,740 --> 00:45:06,150
ดังนั้นในความรู้สึกต้นไม้ครอบครัว,
คุณทำตามมันลง

1011
00:45:06,150 --> 00:45:09,030
และที่นำคุณไปยังโหนดอื่น
ด้านซ้ายมีซึ่งเป็น

1012
00:45:09,030 --> 00:45:10,540
เพียงอาร์เรย์อีก

1013
00:45:10,540 --> 00:45:14,710
>> แล้วถ้าคุณต้องการที่จะเก็บเวลล์,
คุณพบว่าตัวชี้ที่แสดงถึง

1014
00:45:14,710 --> 00:45:16,430
ซึ่งเป็นหนึ่งในนี้ที่นี่

1015
00:45:16,430 --> 00:45:17,840
แล้วคุณจะไปโหนดถั​​ดไป

1016
00:45:17,840 --> 00:45:20,100
และแจ้งให้ทราบล่วงหน้า - นี่คือเหตุผลที่รูปภาพ
หลอกลวงน้อย -

1017
00:45:20,100 --> 00:45:21,990
โหนดนี้ดูสุดยอดเล็ก

1018
00:45:21,990 --> 00:45:26,050
แต่ทางด้านขวาของนี้เป็น Y และ Z.
เป็นเพียงผู้เขียนได้ถูกตัดทอน

1019
00:45:26,050 --> 00:45:27,630
ภาพเพื่อให้คุณจริง
เห็นสิ่งที่

1020
00:45:27,630 --> 00:45:30,400
มิฉะนั้นภาพ
จะกว้างอย่างมหาศาล

1021
00:45:30,400 --> 00:45:36,180
ดังนั้นตอนนี้คุณดัชนีลงในตำแหน่ง X แล้ว
W, E นั้นแล้ว L แล้วลิตรแล้วว่ามีอะไร

1022
00:45:36,180 --> 00:45:37,380
อยากรู้อยากเห็นนี้

1023
00:45:37,380 --> 00:45:41,250
>> ดีถ้าเราใช้การเรียงลำดับของใหม่นี้
ใช้เวลาในวิธีการเก็บสตริงใน

1024
00:45:41,250 --> 00:45:44,500
โครงสร้างข้อมูลคุณยังคงต้อง
เป็นหลักตรวจสอบออกในข้อมูล

1025
00:45:44,500 --> 00:45:47,250
โครงสร้างคำว่าสิ้นสุดที่นี่

1026
00:45:47,250 --> 00:45:50,830
ในคำอื่น ๆ แต่ละโหนดเหล่านี้
อย่างใดมีต้องจำไว้ว่าเรา

1027
00:45:50,830 --> 00:45:53,500
ตามจริงทั้งหมดของคำแนะนำเหล่านี้
และกำลังจะออกไปเล็กน้อย

1028
00:45:53,500 --> 00:45:58,370
เศษขนมปังที่ด้านล่างของที่นี่นี้
โครงสร้างเพื่อแสดง M--X-W-E-L-L คือ

1029
00:45:58,370 --> 00:46:00,230
แน่นอนในโครงสร้างข้อมูลนี้

1030
00:46:00,230 --> 00:46:02,040
>> ดังนั้นเราอาจจะทำดังต่อไปนี้

1031
00:46:02,040 --> 00:46:06,810
แต่ละโหนดในภาพที่เราเพียงแค่
เห็นมีอาร์เรย์ของ 27 ขนาด

1032
00:46:06,810 --> 00:46:10,550
และก็ตอนนี้ 27 เพราะใน p ตั้งหก
เราจริงจะให้ apostrophe,

1033
00:46:10,550 --> 00:46:13,590
เพื่อให้เราสามารถมีชื่อเช่น O'Reilly
และอื่น ๆ ที่มี apostrophes

1034
00:46:13,590 --> 00:46:14,820
แต่ความคิดเดียวกัน

1035
00:46:14,820 --> 00:46:17,710
แต่ละองค์ประกอบเหล่านั้นใน
จุดอาร์เรย์ struct

1036
00:46:17,710 --> 00:46:19,320
โหนดดังนั้นเพียงโหนด

1037
00:46:19,320 --> 00:46:21,430
ดังนั้นนี่คือชวนให้นึกถึงมาก
ของรายการที่เชื่อมโยงของเรา

1038
00:46:21,430 --> 00:46:24,550
>> และแล้วฉันมีบูลีนซึ่งผมจะ
เรียกคำซึ่งเป็นเพียงการไปได้

1039
00:46:24,550 --> 00:46:29,120
จริงถ้าคำว่าสิ้นสุดที่นี้
โหนดในต้นไม้

1040
00:46:29,120 --> 00:46:32,870
มันมีประสิทธิภาพแสดงเล็ก ๆ น้อย ๆ
สามเหลี่ยมที่เราเห็นในช่วงเวลาที่ผ่านมา

1041
00:46:32,870 --> 00:46:37,190
ดังนั้นถ้าคำว่าสิ้นสุดที่โหนดในที่
ต้นไม้ฟิลด์คำที่จะเป็นจริง,

1042
00:46:37,190 --> 00:46:41,990
ซึ่งมีแนวคิดการตรวจสอบปิดหรือ
เรากำลังวาดรูปสามเหลี่ยมนี้ใช่มี

1043
00:46:41,990 --> 00:46:44,080
คำที่นี่

1044
00:46:44,080 --> 00:46:45,120
>> ดังนั้นนี่คือคู่ชีวิต

1045
00:46:45,120 --> 00:46:48,540
และตอนนี้คำถามคือสิ่งที่
กำลังทำงานอยู่ในขณะนี้?

1046
00:46:48,540 --> 00:46:49,930
มันเป็น O ใหญ่ของ n?

1047
00:46:49,930 --> 00:46:51,410
มันเป็นบางสิ่งบางอย่างอื่นใช่หรือไม่

1048
00:46:51,410 --> 00:46:57,330
ดีถ้าคุณได้ n ชื่อในข้อมูลนี้
โครงสร้างแม็กซ์เป็นเพียงหนึ่งใน

1049
00:46:57,330 --> 00:47:02,330
พวกเขาเป็นเวลาการทำงานของสิ่งที่
ใส่หรือหาแมกซ์เวล?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
เวลาทำงานอะไร
ใส่แมกซ์เวล?

1052
00:47:09,050 --> 00:47:11,740
ถ้ามีชื่ออื่น ๆ ของ N
อยู่ในตารางแล้ว?

1053
00:47:11,740 --> 00:47:12,507
อ้าง?

1054
00:47:12,507 --> 00:47:15,429
>> ลูกศิษย์: [ได้ยิน]

1055
00:47:15,429 --> 00:47:17,550
>> ลำโพง 1: ใช่มันเป็นระยะเวลา
ของชื่อใช่มั้ย?

1056
00:47:17,550 --> 00:47:24,420
ดังนั้น M--x-w-e-l-l จึงรู้สึกเช่นนี้
อัลกอริทึมคือ O ใหญ่เจ็ด

1057
00:47:24,420 --> 00:47:26,580
ตอนนี้แน่นอนชื่อ
จะแตกต่างกันในความยาว

1058
00:47:26,580 --> 00:47:27,380
บางทีมันอาจจะเป็นชื่อที่สั้น

1059
00:47:27,380 --> 00:47:28,600
บางทีมันอาจจะเป็นชื่อที่ยาว

1060
00:47:28,600 --> 00:47:33,390
แต่สิ่งที่สำคัญที่นี่คือ
มันเป็นจำนวนคงที่

1061
00:47:33,390 --> 00:47:36,810
และบางทีมันอาจจะไม่คงที่จริงๆ
แต่พระเจ้าถ้าแนบเนียนใน

1062
00:47:36,810 --> 00:47:41,570
พจนานุกรมอาจมีข้อ จำกัด บางอย่าง
กับจำนวนของตัวอักษรใน

1063
00:47:41,570 --> 00:47:43,820
ชื่อของบุคคลในประเทศโดยเฉพาะอย่างยิ่ง

1064
00:47:43,820 --> 00:47:46,940
>> และเพื่อให้เราสามารถคิดว่า
ค่าคงที่

1065
00:47:46,940 --> 00:47:47,750
ผมไม่ทราบว่ามันคืออะไร

1066
00:47:47,750 --> 00:47:50,440
มันอาจจะมีขนาดใหญ่กว่า
เราคิดว่ามันเป็น

1067
00:47:50,440 --> 00:47:52,720
เพราะมีเสมอบางมุม
กรณีที่มีชื่อยาวบ้า

1068
00:47:52,720 --> 00:47:56,360
ดังนั้นขอเรียกว่า K แต่มันก็ยังคงเป็น
สันนิษฐานว่าคงเพราะทุก

1069
00:47:56,360 --> 00:48:00,190
ชื่อในโลกอย่างน้อยใน
ประเทศใดประเทศหนึ่งเป็นระยะเวลาหรือว่า

1070
00:48:00,190 --> 00:48:01,780
สั้นจึงคงที่

1071
00:48:01,780 --> 00:48:04,490
แต่เมื่อเราได้กล่าวว่าสิ่งที่มีขนาดใหญ่
O ของค่าคงที่สิ่งที่ว่า

1072
00:48:04,490 --> 00:48:07,760
จริงๆเทียบเท่ากับ?

1073
00:48:07,760 --> 00:48:10,420
นั่นคือสิ่งเดียวกัน
เป็นคำพูดตลอดเวลา

1074
00:48:10,420 --> 00:48:11,530
>> ตอนนี้เราชนิดของการโกงใช่มั้ย?

1075
00:48:11,530 --> 00:48:15,340
เราใช้ประโยชน์จากชนิดของทฤษฎีบาง
ที่นี่เพื่อบอกว่าดีคำสั่งของ k คือ

1076
00:48:15,340 --> 00:48:17,450
จริงๆเพียงแค่สั่งซื้อจากหนึ่ง
และก็ถึงเวลาที่คงที่

1077
00:48:17,450 --> 00:48:18,200
แต่มันคือเรื่องจริง

1078
00:48:18,200 --> 00:48:22,550
เพราะข้อมูลเชิงลึกที่สำคัญที่นี่คือ
ถ้าเราได้ n ชื่ออยู่แล้วในการนี​​้

1079
00:48:22,550 --> 00:48:26,010
โครงสร้างข้อมูลและเราใส่แมกซ์เวล,
เป็นระยะเวลาที่จะใช้เวลาที่เราจะ

1080
00:48:26,010 --> 00:48:29,530
ใส่แม็กซ์ที่ได้รับผลกระทบทั้งหมด
โดยวิธีการหลายคนอื่น ๆ

1081
00:48:29,530 --> 00:48:31,100
อยู่ในโครงสร้างข้อมูล?

1082
00:48:31,100 --> 00:48:31,670
ไม่ได้ดูเหมือนจะเป็น

1083
00:48:31,670 --> 00:48:36,280
ถ้าฉันมีพันล้านองค์ประกอบมากขึ้นในการนี​​้
Trie แล้วใส่แมกซ์เวลเป็น

1084
00:48:36,280 --> 00:48:38,650
เขาที่ทุกคนได้รับผลกระทบ?

1085
00:48:38,650 --> 00:48:39,050
เลขที่

1086
00:48:39,050 --> 00:48:42,950
และที่แตกต่างของข้อมูลใด ๆ วัน
โครงสร้างที่เราเคยเห็นป่านนี้ที่

1087
00:48:42,950 --> 00:48:46,820
เวลาทำงานของอัลกอริทึมของคุณเป็น
อิสระอย่างสมบูรณ์ของเท่าใด

1088
00:48:46,820 --> 00:48:51,430
สิ่งที่เป็นหรือไม่ได้เป็นแล้ว
ในโครงสร้างข้อมูลที่

1089
00:48:51,430 --> 00:48:54,650
>> และอื่น ๆ ที่มีกำบังคุณในขณะนี้คือ
โอกาสสำหรับ p ชุดหกซึ่งจะ

1090
00:48:54,650 --> 00:48:58,310
อีกครั้งที่เกี่ยวข้องกับการดำเนินการของคุณเอง
ตรวจสอบการสะกดในการอ่าน 150,000

1091
00:48:58,310 --> 00:49:01,050
คำวิธีการที่ดีที่สุดในการจัดเก็บที่
ไม่ชัดเจนจำเป็นต้อง

1092
00:49:01,050 --> 00:49:04,030
และแม้ว่าผมได้แรงบันดาลใจที่จะหา
จอกศักดิ์สิทธิ์ที่ฉันทำไม่ได้

1093
00:49:04,030 --> 00:49:05,330
ที่อ้างว่าเป็นคู่ชีวิต

1094
00:49:05,330 --> 00:49:09,810
ในความเป็นจริงตารางแฮชอาจได้เป็นอย่างดี
พิสูจน์ให้เป็นที่มีประสิทธิภาพมากขึ้น

1095
00:49:09,810 --> 00:49:10,830
แต่ผู้ที่เป็นเพียง -

1096
00:49:10,830 --> 00:49:14,620
นั่นเป็นเพียงหนึ่งในการตัดสินใจการออกแบบ
คุณจะต้องทำ

1097
00:49:14,620 --> 00:49:18,920
>> แต่ในการปิดลองมา 50 หรือดังนั้น
วินาทีที่จะมองที่สิ่งที่อยู่

1098
00:49:18,920 --> 00:49:22,190
ไปข้างหน้าต่อไปสัปดาห์และการเปลี่ยนแปลงเกินกว่าเรา
จากบรรทัดคำสั่งนี้

1099
00:49:22,190 --> 00:49:26,220
โลกถ้าโปรแกรม C ถึงสิ่งที่เว็บ
และตามภาษาเช่น PHP และ

1100
00:49:26,220 --> 00:49:30,350
JavaScript และอินเทอร์เน็ตของตัวเอง
โปรโตคอลเช่น HTTP ซึ่งคุณได้

1101
00:49:30,350 --> 00:49:32,870
ที่สำหรับรับเป็นเวลาหลายปี
ในขณะนี้และทุกพิมพ์มากที่สุด

1102
00:49:32,870 --> 00:49:34,440
วันบางทีหรือเห็น

1103
00:49:34,440 --> 00:49:37,420
และเราจะเริ่มต้นในการปอกเปลือกกลับ
ชั้นของสิ่งที่เป็นอินเทอร์เน็ต

1104
00:49:37,420 --> 00:49:40,650
และรหัสคือสิ่งที่
รองรับเครื่องมือของวันนี้

1105
00:49:40,650 --> 00:49:43,230
ดังนั้น 50 วินาทีทีเซอร์นี้ที่นี่

1106
00:49:43,230 --> 00:49:46,570
ฉันให้คุณนักรบแห่งสุทธิ

1107
00:49:46,570 --> 00:49:51,370
>> [เล่นภาพวิดีโอ]

1108
00:49:51,370 --> 00:49:56,764
>> -เขาเดินเข้ามาพร้อมกับข้อความ

1109
00:49:56,764 --> 00:50:00,687
กับโปรโตคอลทั้งหมดของเขาเอง

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
เขามาถึงโลกของไฟร์วอลล์โหดร้าย,
เราเตอร์เอาใจใส่และอันตรายไกล

1112
00:50:19,780 --> 00:50:22,600
ที่เลวร้ายยิ่งกว่าความตาย

1113
00:50:22,600 --> 00:50:23,590
เขาได้อย่างรวดเร็ว

1114
00:50:23,590 --> 00:50:25,300
เขาเป็นคนที่แข็งแกร่ง

1115
00:50:25,300 --> 00:50:27,700
เขา TCPIP

1116
00:50:27,700 --> 00:50:30,420
และเขามีที่อยู่ของคุณ

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
นักรบแห่งสุทธิ

1119
00:50:34,590 --> 00:50:35,290
>> [เล่นวิดีโอจบ]

1120
00:50:35,290 --> 00:50:38,070
>> ลำโพง 1: นั่นคือวิธีที่อินเทอร์เน็ต
จะทำงานในฐานะของสัปดาห์ต่อไป

1121
00:50:38,070 --> 00:50:40,406