1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> ลำโพงที่ 1: สิทธิทั้งหมดดังนั้นนี่คือ
CS50 นี่คือจุดสิ้นสุดของสัปดาห์ห้า

3
00:00:15,860 --> 00:00:19,220
และจำได้ว่าครั้งสุดท้ายที่เรา
เริ่มมองหาข้อมูลนักเล่น

4
00:00:19,220 --> 00:00:22,310
โครงสร้างที่เริ่มต้นที่จะแก้ปัญหา
ปัญหาที่เริ่มต้นที่จะแนะนำ

5
00:00:22,310 --> 00:00:25,640
ปัญหาใหม่ แต่ที่สำคัญไปนี้
คือการจัดเรียงของเกลียวที่เรา

6
00:00:25,640 --> 00:00:27,940
เริ่มต้นที่จะทำจากโหนดไปยังโหนด

7
00:00:27,940 --> 00:00:30,085
ดังนั้นนี่แน่นอน
รายการที่เชื่อมโยงโดยลำพัง

8
00:00:30,085 --> 00:00:31,960
และโดยการเชื่อมโยงโดยลำพัง
ฉันหมายความว่ามีเพียงหนึ่ง

9
00:00:31,960 --> 00:00:33,380
ด้ายระหว่างแต่ละโหนดเหล่านั้น

10
00:00:33,380 --> 00:00:35,890
เปิดออกคุณสามารถทำนักเล่น
สิ่งที่ชอบรายการที่เชื่อมโยงเป็นทวีคูณ

11
00:00:35,890 --> 00:00:38,470
โดยคุณมีลูกศร
ไปในทั้งสองทิศทางซึ่ง

12
00:00:38,470 --> 00:00:40,320
สามารถช่วยให้มีประสิทธิภาพบางอย่าง

13
00:00:40,320 --> 00:00:42,000
แต่ตอนนี้แก้ปัญหาได้หรือไม่

14
00:00:42,000 --> 00:00:43,500
สิ่งที่เป็นปัญหานี้ไม่แก้ปัญหา?

15
00:00:43,500 --> 00:00:46,620
ทำไมเราดูแลในวันจันทร์?

16
00:00:46,620 --> 00:00:49,820
ทำไมในทางทฤษฎีเราไม่ดูแลในวันจันทร์?

17
00:00:49,820 --> 00:00:50,630
มันทำอะไร?

18
00:00:50,630 --> 00:00:51,950
>> ผู้ชม: เราแบบไดนามิกสามารถปรับขนาด

19
00:00:51,950 --> 00:00:53,740
>> ลำโพง 1: ตกลงดังนั้นเราสามารถทำได้
ปรับขนาดแบบไดนามิก

20
00:00:53,740 --> 00:00:54,710
ทำได้ดีทั้งสองท่าน

21
00:00:54,710 --> 00:00:57,560
ดังนั้นคุณจึงสามารถปรับขนาดแบบไดนามิกนี้
โครงสร้างข้อมูลในขณะที่อาร์เรย์

22
00:00:57,560 --> 00:01:00,760
จำที่คุณต้องรู้
เบื้องต้นช่องว่างที่คุณต้องการ

23
00:01:00,760 --> 00:01:03,870
และหากคุณต้องการน้อยมาก
พื้นที่ที่คุณกำลังชนิดของออกจากโชค

24
00:01:03,870 --> 00:01:05,560
คุณต้องสร้างอาร์เรย์ใหม่ทั้งหมด

25
00:01:05,560 --> 00:01:07,893
คุณจะต้องย้ายทั้งหมดของคุณ
ข้อมูลจากที่หนึ่งไปยังที่อื่น ๆ

26
00:01:07,893 --> 00:01:10,600
ในที่สุดก็เป็นอิสระอาร์เรย์เก่า
ถ้าคุณสามารถแล้วดำเนินการต่อ

27
00:01:10,600 --> 00:01:13,891
ซึ่งเพียงแค่รู้สึกมีราคาแพงมากและมาก
ที่ไม่มีประสิทธิภาพและแน่นอนที่จะสามารถ

28
00:01:13,891 --> 00:01:14,890
แต่ตอนนี้ไม่ดี

29
00:01:14,890 --> 00:01:18,180
เราจ่ายราคาเป็นสิ่งที่เป็นหนึ่ง
ของราคาที่เห็นได้ชัดมากขึ้นเรา

30
00:01:18,180 --> 00:01:20,550
โดยการใช้จ่ายรายการที่เชื่อมโยงหรือไม่?

31
00:01:20,550 --> 00:01:22,825
>> ผู้ชม: เราต้องใช้
พื้นที่สองสำหรับแต่ละคน

32
00:01:22,825 --> 00:01:25,200
ลำโพง 1: ใช่เราจึงจำเป็นต้อง
อย่างน้อยสองเท่าของพื้นที่มาก

33
00:01:25,200 --> 00:01:27,700
ในความเป็นจริงผมก็นึกภาพนี้
แม้เพียงเล็กน้อยทำให้เข้าใจผิด

34
00:01:27,700 --> 00:01:32,200
เพราะ IDE CS50 ในจำนวนมากของที่ทันสมัย
คอมพิวเตอร์ตัวชี้หรือที่อยู่

35
00:01:32,200 --> 00:01:33,700
ไม่ได้อยู่ในความเป็นจริงสี่ไบต์

36
00:01:33,700 --> 00:01:36,090
มันมากเหล่านี้มักจะ
วันที่แปดไบต์ซึ่ง

37
00:01:36,090 --> 00:01:38,530
ด้านล่างหมายถึงมากที่สุด
รูปสี่เหลี่ยมมีในความเป็นจริง

38
00:01:38,530 --> 00:01:40,900
เป็นชนิดของสองเท่า
ใหญ่เป็นสิ่งที่ผมเคยวาด

39
00:01:40,900 --> 00:01:44,409
ซึ่งหมายความว่าคุณกำลังใช้สามเท่า
พื้นที่มากที่สุดเท่าที่เราอาจจะมีอย่างอื่น

40
00:01:44,409 --> 00:01:46,700
ตอนนี้ในเวลาเดียวกันเรา
ยังคงพูดคุยไบต์ใช่มั้ย?

41
00:01:46,700 --> 00:01:49,140
เราไม่จำเป็นต้องพูด
เมกะไบต์หรือกิกะไบต์

42
00:01:49,140 --> 00:01:51,000
เว้นแต่โครงสร้างข้อมูลเหล่านี้จะได้รับใหญ่

43
00:01:51,000 --> 00:01:54,510
>> และในวันนี้เราจะเริ่มต้นที่จะต้องพิจารณา
วิธีการที่เราจะสำรวจข้อมูล

44
00:01:54,510 --> 00:01:57,310
มีประสิทธิภาพมากขึ้นถ้าใน
ความเป็นจริงข้อมูลที่ได้รับใหญ่

45
00:01:57,310 --> 00:02:00,360
แต่ลอง canonicalize
การดำเนินงานครั้งแรก

46
00:02:00,360 --> 00:02:02,460
ที่คุณสามารถทำในสิ่งเหล่านี้
ชนิดของโครงสร้างข้อมูล

47
00:02:02,460 --> 00:02:04,790
ดังนั้นสิ่งที่ต้องการเชื่อมโยง
รายการสนับสนุนทั่วไป

48
00:02:04,790 --> 00:02:07,514
การดำเนินงานที่ต้องการลบ
แทรกและค้นหา

49
00:02:07,514 --> 00:02:08,639
และสิ่งที่ผมหมายถึงโดยที่?

50
00:02:08,639 --> 00:02:11,222
นั่นก็หมายความว่าปกติ
ถ้าคนจะใช้รายการที่เชื่อมโยง

51
00:02:11,222 --> 00:02:14,287
พวกเขาหรือคนอื่นได้ดำเนินการ
ฟังก์ชั่นเช่นการลบแทรก

52
00:02:14,287 --> 00:02:16,120
และการค้นหาเพื่อให้คุณสามารถ
จริงทำอะไรบางอย่าง

53
00:02:16,120 --> 00:02:18,030
ที่เป็นประโยชน์กับโครงสร้างข้อมูล

54
00:02:18,030 --> 00:02:20,760
ดังนั้นลองมาดูอย่างรวดเร็ว
วิธีการที่เราจะใช้

55
00:02:20,760 --> 00:02:24,530
รหัสบางอย่างสำหรับรายการที่เชื่อมโยงดังต่อไปนี้

56
00:02:24,530 --> 00:02:27,885
>> ดังนั้นนี้เป็นเพียงบางส่วนรหัสซี
ไม่ได้โปรแกรมที่สมบูรณ์

57
00:02:27,885 --> 00:02:29,260
ที่ผมวิปปิ้งได้อย่างรวดเร็วขึ้น

58
00:02:29,260 --> 00:02:32,300
มันไม่ได้ออนไลน์ในการจัดจำหน่าย
รหัสเพราะมันจะไม่ได้ทำงานจริง

59
00:02:32,300 --> 00:02:33,790
แต่สังเกตเห็นฉันได้เพียงแค่
ที่มีความคิดเห็นกล่าวว่า

60
00:02:33,790 --> 00:02:36,130
dot dot dot มีบางสิ่งบางอย่าง
มีจุดจุดจุดมีบางสิ่งบางอย่าง

61
00:02:36,130 --> 00:02:38,410
และขอเพียงแค่มอง
ส่วนสิ่งที่มีความฉ่ำ

62
00:02:38,410 --> 00:02:40,790
ดังนั้นในบรรทัดที่สาม
จำได้ว่าตอนนี้

63
00:02:40,790 --> 00:02:45,960
เราเสนอประกาศโหนดที่ผ่านมา
เวลาหนึ่งในบรรดาวัตถุทรงสี่เหลี่ยม

64
00:02:45,960 --> 00:02:48,790
มันมี int ว่าเราจะเรียกยังไม่มีข้อความที่
แต่เราจะเรียกมันว่าอะไร

65
00:02:48,790 --> 00:02:51,920
แล้วดาวโหนดโครงสร้างที่เรียกว่าต่อไป

66
00:02:51,920 --> 00:02:55,520
และเพียงเพื่อจะชัดเจนที่สองที่
บรรทัดในบรรทัดหกสิ่งที่เป็นที่?

67
00:02:55,520 --> 00:02:57,930
มันจะทำอะไรสำหรับเรา?

68
00:02:57,930 --> 00:03:01,044
เพราะมันแน่นอนดูเพิ่มเติม
ความลับกว่าตัวแปรตามปกติของเรา

69
00:03:01,044 --> 00:03:02,740
>> ผู้ชม: มันทำให้ย้ายไปหนึ่ง

70
00:03:02,740 --> 00:03:04,650
>> ลำโพงที่ 1: มันทำให้ย้ายไปหนึ่ง

71
00:03:04,650 --> 00:03:08,580
และจะแม่นยำมากขึ้น
มันจะเก็บที่อยู่

72
00:03:08,580 --> 00:03:11,582
ของโหนดที่หมายถึงการเป็น
ความหมายถัดไปใช่มั้ย?

73
00:03:11,582 --> 00:03:13,540
ดังนั้นจึงไม่ได้ไป
จำเป็นต้องย้ายอะไร

74
00:03:13,540 --> 00:03:15,290
มันเป็นเพียงแค่ไป
เก็บค่าซึ่งเป็น

75
00:03:15,290 --> 00:03:17,170
จะเป็นที่อยู่
บางโหนดอื่น ๆ

76
00:03:17,170 --> 00:03:20,810
และนั่นคือเหตุผลที่เราได้กล่าวว่า struct
ดาวโหนดดาวแสดงถึง

77
00:03:20,810 --> 00:03:22,370
ตัวชี้หรือที่อยู่

78
00:03:22,370 --> 00:03:26,390
ตกลงดังนั้นตอนนี้ถ้าคุณคิดว่าเรามี
นี้ยังไม่มีข้อความที่มีให้เราและให้

79
00:03:26,390 --> 00:03:29,490
คิดว่าคนอื่นมี
ใส่ทั้งกลุ่มของจำนวนเต็ม

80
00:03:29,490 --> 00:03:30,400
เป็นรายการที่เชื่อมโยง

81
00:03:30,400 --> 00:03:35,640
และที่เป็นรายการที่เชื่อมโยง
ชี้ไปในบางจุด

82
00:03:35,640 --> 00:03:39,040
รายการที่เรียกว่าตัวแปรที่
ผ่านในที่นี่เป็นพารามิเตอร์

83
00:03:39,040 --> 00:03:43,120
ฉันจะไปเกี่ยวกับสาย
14 การดำเนินการค้นหา?

84
00:03:43,120 --> 00:03:45,990
ในคำอื่น ๆ ถ้าผมกำลังดำเนินการ
ฟังก์ชั่นที่มีจุดมุ่งหมายในชีวิต

85
00:03:45,990 --> 00:03:48,889
คือการใช้ int แล้ว
จุดเริ่มต้นของรายการที่เชื่อมโยง

86
00:03:48,889 --> 00:03:50,430
ที่เป็นตัวชี้ไปยังรายการที่เชื่อมโยง

87
00:03:50,430 --> 00:03:52,992
เช่นเดียวกับครั้งแรกที่ผมคิดว่าเดวิด
เป็นอาสาสมัครของเราในวันจันทร์ที่

88
00:03:52,992 --> 00:03:54,700
เขาได้รับการชี้ไปที่
ทั้งรายการที่เชื่อมโยง

89
00:03:54,700 --> 00:03:57,820
มันเหมือนกับว่าเรากำลังผ่าน
ดาวิดเป็นอาร์กิวเมนต์ของเราที่นี่

90
00:03:57,820 --> 00:03:59,990
เราไม่ไปวิธีการเกี่ยวกับภายในรายการนี​​้

91
00:03:59,990 --> 00:04:04,640
ดีก็ปรากฎว่าแม้ว่า
ตัวชี้ค่อนข้างใหม่ในขณะนี้กับเรา

92
00:04:04,640 --> 00:04:07,010
เราสามารถทำเช่นนี้ค่อนข้าง
ตามตรง

93
00:04:07,010 --> 00:04:09,500
>> ฉันจะไปข้างหน้าและ
ประกาศตัวแปรชั่วคราวที่

94
00:04:09,500 --> 00:04:12,364
โดยการประชุมเป็นเพียงการไป
จะเรียกว่าตัวชี้หรือ PTR,

95
00:04:12,364 --> 00:04:14,030
แต่คุณสามารถเรียกมันว่าสิ่งที่คุณต้องการ

96
00:04:14,030 --> 00:04:16,470
และฉันจะเริ่มต้น
ไปยังจุดเริ่มต้นของรายการ

97
00:04:16,470 --> 00:04:20,050
เพื่อให้คุณสามารถชนิดของการคิดว่านี้
ฉันเป็นครูในวันอื่น ๆ

98
00:04:20,050 --> 00:04:23,580
ชนิดของการชี้ไปที่ใครบางคน
ในหมู่มนุษย์ของเราเป็นอาสาสมัคร

99
00:04:23,580 --> 00:04:26,470
ดังนั้นฉันตัวแปรชั่วคราวที่
เพียงแค่ชี้ไปที่สิ่งเดียวกัน

100
00:04:26,470 --> 00:04:31,390
ที่บังเอิญชื่อของเรา
อาสาสมัครเดวิดก็ยังชี้ให้เห็น

101
00:04:31,390 --> 00:04:35,440
ตอนนี้ในขณะที่ตัวชี้เป็น
ไม่เป็นโมฆะเพราะการเรียกคืน

102
00:04:35,440 --> 00:04:40,350
null ที่บางค่าแมวมองพิเศษ
demarcates ท้ายของรายการ

103
00:04:40,350 --> 00:04:44,280
ดังนั้นในขณะที่ฉันไม่ได้ชี้ไปที่
พื้นดินเช่นอาสาสมัครครั้งสุดท้ายของเรา

104
00:04:44,280 --> 00:04:47,190
ก็ให้เป็นไปข้างหน้า
และทำต่อไปนี้

105
00:04:47,190 --> 00:04:51,820
หาก pointer-- และตอนนี้ฉันต้องการชนิดของ
จะทำในสิ่งที่เราทำกับนักเรียน

106
00:04:51,820 --> 00:04:57,410
structure-- ถ้าตัวชี้จุดต่อไป
equals-- แต่ถ้ายังไม่มีตัวชี้จุดเท่ากับ

107
00:04:57,410 --> 00:05:02,290
เท่ากับตัวแปรยังไม่มีข้อความที่
อาร์กิวเมนต์ที่ถูกส่งผ่านไปใน

108
00:05:02,290 --> 00:05:05,370
แล้วฉันต้องการที่จะไปข้างหน้า
และพูดกลับจริง

109
00:05:05,370 --> 00:05:11,020
ฉันได้พบจำนวนไม่มีข้อความภายในของ
หนึ่งของโหนดของรายการที่เชื่อมโยงของฉัน

110
00:05:11,020 --> 00:05:13,500
แต่จุดไม่
ทำงานในบริบทนี้

111
00:05:13,500 --> 00:05:17,260
เพราะตัวชี้ PTR เป็น
แน่นอนตัวชี้ที่อยู่

112
00:05:17,260 --> 00:05:20,632
เราจริงสามารถที่เยี่ยมยอด
ในที่สุดก็ใช้ชิ้นส่วนของไวยากรณ์

113
00:05:20,632 --> 00:05:22,590
ว่าจะทำให้
ความรู้สึกที่ใช้งานง่ายและจริง

114
00:05:22,590 --> 00:05:27,870
ใช้ลูกศรที่นี่ซึ่งหมายความว่าจะไปจาก
ว่าที่อยู่ที่จะมีจำนวนเต็มใน

115
00:05:27,870 --> 00:05:30,160
ดังนั้นจึงเป็นที่คล้ายกันมากใน
จิตวิญญาณของผู้ประกอบการที่จะจุด,

116
00:05:30,160 --> 00:05:33,860
แต่เป็นเพราะไม่ได้เป็นตัวชี้ตัวชี้
และไม่ได้เป็นโครงสร้างที่เกิดขึ้นจริงของตัวเอง

117
00:05:33,860 --> 00:05:35,380
เราก็ใช้ลูกศร

118
00:05:35,380 --> 00:05:40,620
>> ดังนั้นถ้าโหนดปัจจุบันที่ฉันที่
ตัวแปรชั่วคราวกำลังชี้ไปที่

119
00:05:40,620 --> 00:05:43,060
ไม่มีไม่ได้ทำในสิ่งที่ฉันต้องการจะทำอย่างไร?

120
00:05:43,060 --> 00:05:45,910
ดีกับอาสาสมัครของฉัน
ที่เรามีที่นี่ในวันอื่น ๆ

121
00:05:45,910 --> 00:05:49,710
ถ้ามนุษย์คนแรกของฉันไม่ได้เป็นคนเดียวที่ฉัน
ต้องการและบางทีมนุษย์ที่สองไม่ได้

122
00:05:49,710 --> 00:05:52,660
หนึ่งที่ฉันต้องการและคนที่สามผม
จำเป็นที่จะต้องให้ย้ายร่างกาย

123
00:05:52,660 --> 00:05:54,690
เช่นเดียวกับฉันจะก้าวผ่านรายการ?

124
00:05:54,690 --> 00:05:57,470
เมื่อเรามีอาร์เรย์คุณ
ก็ไม่ได้เหมือนที่ผมบวกบวก

125
00:05:57,470 --> 00:06:03,660
แต่ในกรณีนี้ก็พอเพียงที่จะ
ทำชี้ได้รับตัวชี้ต่อไป

126
00:06:03,660 --> 00:06:07,580
ในคำอื่น ๆ ฟิลด์ต่อไป
เป็นเหมือนทั้งหมดของมือซ้าย

127
00:06:07,580 --> 00:06:10,880
ที่อาสาสมัครของเราในวันจันทร์
ได้ใช้ไปยังจุดที่บางโหนดอื่น ๆ

128
00:06:10,880 --> 00:06:12,890
สิ่งเหล่านี้เป็นเพื่อนบ้านของพวกเขาต่อไป

129
00:06:12,890 --> 00:06:17,060
>> ดังนั้นถ้าผมต้องการที่จะก้าวผ่านรายการนี​​้
ฉันไม่สามารถเพียงแค่ทำผมบวกบวกอีกต่อไป

130
00:06:17,060 --> 00:06:20,120
ฉันแทนที่จะต้องบอกว่า
ผมชี้เป็นไป

131
00:06:20,120 --> 00:06:24,650
เท่ากับสิ่งที่ฟิลด์ถัดไปคือ
สนามต่อไปคือข้อมูลต่อไปคือ

132
00:06:24,650 --> 00:06:28,350
ต่อไปนี้ทุกมือทิ้ง
ที่เรามีอยู่บนเวทีชี้

133
00:06:28,350 --> 00:06:30,000
บางส่วนค่าที่ตามมา

134
00:06:30,000 --> 00:06:32,590
และถ้าฉันได้รับผ่าน
ย้ำว่าทั้ง

135
00:06:32,590 --> 00:06:39,330
และในที่สุดผมตี null ไม่ได้มี
พบว่ายังไม่มี แต่ผมก็กลับเท็จ

136
00:06:39,330 --> 00:06:44,100
ดังนั้นอีกครั้งสิ่งที่เรากำลังทำอะไรที่นี่
ตามภาพช่วงเวลาที่ผ่านมา

137
00:06:44,100 --> 00:06:47,840
จะเริ่มต้นด้วยการชี้ที่
จุดเริ่มต้นของรายการสันนิษฐานว่า

138
00:06:47,840 --> 00:06:50,970
และจากนั้นผมตรวจสอบเป็นค่า
ฉันกำลังมองหาเท่ากับเก้า?

139
00:06:50,970 --> 00:06:52,650
ถ้าฉันกลับจริงและฉันทำ

140
00:06:52,650 --> 00:06:56,450
ถ้าไม่ได้ผมปรับปรุงมือของฉัน
ตัวชี้ AKA เพื่อชี้

141
00:06:56,450 --> 00:06:59,540
ที่ตำแหน่งลูกศรถัดไปและ
แล้วสถานที่ลูกศรถัดไป

142
00:06:59,540 --> 00:07:00,480
และต่อไป

143
00:07:00,480 --> 00:07:03,770
ฉันเพียงแค่เดินผ่านแถวนี้

144
00:07:03,770 --> 00:07:06,010
>> ดังนั้นอีกครั้งที่ใส่ใจ?

145
00:07:06,010 --> 00:07:07,861
ชอบสิ่งนี้เป็นส่วนผสมสำหรับ?

146
00:07:07,861 --> 00:07:10,360
ดีจำได้ว่าเราได้แนะนำ
ความคิดของกองซึ่ง

147
00:07:10,360 --> 00:07:15,400
เป็นข้อมูลนามธรรมพิมพ์ตราบเท่าที่มันเป็น
ไม่ได้เป็นสิ่งซีก็ไม่ได้เป็นสิ่ง CS50,

148
00:07:15,400 --> 00:07:19,430
เป็นความคิดที่เป็นนามธรรมความคิดนี้
สิ่งที่ซ้อนอยู่ด้านบนของอีกคนหนึ่ง

149
00:07:19,430 --> 00:07:21,820
ที่สามารถนำมาใช้ใน
ที่อัดแน่นของวิธีที่แตกต่าง

150
00:07:21,820 --> 00:07:25,600
และเป็นหนึ่งในวิธีที่เรานำเสนอกับ
อาร์เรย์หรือรายการที่เชื่อมโยง

151
00:07:25,600 --> 00:07:29,570
และปรากฎว่า canonically เป็น
สแต็คสนับสนุนอย่างน้อยสองการดำเนินงาน

152
00:07:29,570 --> 00:07:32,320
และคำฉวัดเฉวียนที่มีการผลักดันเพื่อ
ผลักดันบางสิ่งบางอย่างลงบนกอง

153
00:07:32,320 --> 00:07:34,770
เช่นถาดใหม่ใน
ห้องรับประทานอาหารหรือป๊อป

154
00:07:34,770 --> 00:07:39,000
ซึ่งหมายความว่าจะเอาสูงสุด
ถาดจากสแต็คในการรับประทานอาหารที่

155
00:07:39,000 --> 00:07:41,500
ฮอลล์แล้วบางทีบาง
การดำเนินงานอื่น ๆ เช่นกัน

156
00:07:41,500 --> 00:07:45,770
ดังนั้นวิธีที่เราอาจกำหนดโครงสร้าง
ว่าตอนนี้เรากำลังเรียกร้องให้กอง?

157
00:07:45,770 --> 00:07:50,020
>> ดีที่เรามีทั้งหมดของที่จำเป็น
ไวยากรณ์ที่จำหน่ายของเราใน C. ฉันพูดว่า

158
00:07:50,020 --> 00:07:53,830
ให้ฉันกำหนดประเภทของ
โครงสร้างภายในของสแต็คที่

159
00:07:53,830 --> 00:07:58,030
ฉันจะบอกก็คืออาร์เรย์ของ
ทั้งกลุ่มของตัวเลขและขนาดแล้ว

160
00:07:58,030 --> 00:08:00,930
ดังนั้นในคำอื่น ๆ ถ้าฉันต้องการ
ที่จะใช้ในรหัส

161
00:08:00,930 --> 00:08:03,830
ให้ฉันไปและเพียงแค่ชนิดของ
วาดสิ่งที่นี้ไม่ว่าจะเป็น

162
00:08:03,830 --> 00:08:06,317
ดังนั้นไม่ว่าจะเป็นให้ฉัน
โครงสร้างที่มีอาร์เรย์

163
00:08:06,317 --> 00:08:09,400
และผมไม่ทราบว่าสิ่งที่เป็นความจุ
มันเห็นได้ชัดว่าบางส่วนคงที่ที่ฉันได้

164
00:08:09,400 --> 00:08:10,858
ที่กำหนดไว้ที่อื่นและที่ดี

165
00:08:10,858 --> 00:08:15,260
แต่คิดว่ามันเป็นเพียงหนึ่ง
สองสามสี่ห้า

166
00:08:15,260 --> 00:08:16,700
กำลังการผลิตเพื่อให้เป็น 5

167
00:08:16,700 --> 00:08:21,730
องค์ประกอบภายในของฉัน
โครงสร้างจะถูกเรียกว่าตัวเลข

168
00:08:21,730 --> 00:08:24,020
แล้วฉันจำเป็นต้องใช้
ตัวแปรอื่น ๆ ที่เห็นได้ชัด

169
00:08:24,020 --> 00:08:27,814
เรียกว่าขนาดที่เริ่มฉันจะ
เพื่อกำหนดจะเริ่มต้นให้เป็นศูนย์

170
00:08:27,814 --> 00:08:29,730
หากมีอะไรใน
สแต็คขนาดเป็นศูนย์

171
00:08:29,730 --> 00:08:31,420
และเป็นค่าขยะในตัวเลข

172
00:08:31,420 --> 00:08:33,450
ฉันมีความคิดว่ามีอะไรอยู่ในนั้นไม่เพียง แต่

173
00:08:33,450 --> 00:08:36,059
>> ดังนั้นถ้าผมต้องการที่จะผลักดัน
บางสิ่งบางอย่างลงบนกอง

174
00:08:36,059 --> 00:08:40,780
สมมติว่าผมเรียกฟังก์ชั่นการผลักดันและ
ผมบอกว่าจะผลักดัน 50, เช่นหมายเลข 50

175
00:08:40,780 --> 00:08:44,090
ที่คุณจะนำเสนอ
ผมวาดไว้ในอาร์เรย์นี้หรือไม่?

176
00:08:44,090 --> 00:08:47,124
มีคำตอบได้ห้าที่แตกต่างกันคือ

177
00:08:47,124 --> 00:08:48,790
คุณต้องการที่จะผลักดันจำนวน 50 ที่ไหน?

178
00:08:48,790 --> 00:08:51,899
ถ้าเป้าหมายของที่นี่อีกครั้งเรียกว่า
การผลักดันการทำงานผ่านในการโต้แย้ง

179
00:08:51,899 --> 00:08:52,940
50 ที่ฉันจะใส่มันได้หรือไม่

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
ห้าหากเป็นไปได้มีโอกาส 20%
การคาดเดาได้อย่างถูกต้อง

182
00:08:59,052 --> 00:08:59,896
ใช่?

183
00:08:59,896 --> 00:09:00,740
>> ผู้ชม: ขวาสุด

184
00:09:00,740 --> 00:09:01,990
>> ลำโพง 1: ขวาสุด

185
00:09:01,990 --> 00:09:08,359
ขณะนี้มีโอกาส 25%
การคาดเดาได้อย่างถูกต้อง

186
00:09:08,359 --> 00:09:09,650
ดังนั้นที่จริงน่าจะดี

187
00:09:09,650 --> 00:09:12,770
โดยการประชุมผมจะพูดด้วยอาร์เรย์
เรามักจะเริ่มต้นที่ด้านซ้าย

188
00:09:12,770 --> 00:09:14,519
แต่เราจะทำได้อย่างแน่นอน
เริ่มต้นที่เหมาะสม

189
00:09:14,519 --> 00:09:17,478
สปอยเลอร์ดังนั้นนี่จะเป็นฉัน
อาจจะวาดมันด้านซ้าย

190
00:09:17,478 --> 00:09:20,060
เช่นเดียวกับในอาร์เรย์ปกติท​​ี่
ฉันเริ่มจะซ้ายไปขวา

191
00:09:20,060 --> 00:09:21,780
แต่ถ้าคุณสามารถพลิก
เลขคณิตปรับ

192
00:09:21,780 --> 00:09:23,060
มันก็ไม่ธรรมดา

193
00:09:23,060 --> 00:09:24,880
ตกลงฉันจำเป็นต้องทำอย่างใดอย่างหนึ่ง
แม้ว่าการเปลี่ยนแปลงมากขึ้น

194
00:09:24,880 --> 00:09:27,710
ตอนนี้ที่ผมได้ผลักดันบางสิ่งบางอย่าง
ลงบนกองสิ่งต่อไปหรือไม่

195
00:09:27,710 --> 00:09:29,400
>> สิทธิทั้งหมดที่ฉันต้องเพิ่มขนาด

196
00:09:29,400 --> 00:09:32,600
เพื่อให้ฉันไปข้างหน้าและเพียง
อัปเดตนี้ซึ่งเป็นศูนย์

197
00:09:32,600 --> 00:09:35,950
และแทนที่จะตอนนี้ฉันจะ
ที่จะใส่ในค่าหนึ่ง

198
00:09:35,950 --> 00:09:39,460
และตอนนี้คิดว่าฉันจะผลักดันอีก
จำนวนลงบนกองเช่น 51

199
00:09:39,460 --> 00:09:42,680
ดีฉันจะต้องทำอีกหนึ่ง
การเปลี่ยนแปลงซึ่งจะขึ้นอยู่กับขนาดของทั้งสอง

200
00:09:42,680 --> 00:09:46,100
และจากนั้นก็คิดว่าฉันจะผลักดันอีกหนึ่ง
จำนวนลงบนสแต็คเช่น 61,

201
00:09:46,100 --> 00:09:52,530
ตอนนี้ผมจำเป็นต้องปรับปรุงขนาดหนึ่งที่มากขึ้น
เวลาและได้รับ 3 คุ้มค่าในขณะที่ขนาด

202
00:09:52,530 --> 00:09:54,690
และตอนนี้คิดว่าที่ผมเรียกว่าป๊อป

203
00:09:54,690 --> 00:09:57,250
ตอนนี้ปรากฏโดยการประชุม
ไม่ได้ใช้อาร์กิวเมนต์

204
00:09:57,250 --> 00:10:00,430
กับกองทั้ง
จุดของคำอุปมาถาด

205
00:10:00,430 --> 00:10:03,450
คือการที่คุณไม่ได้มีการพิจารณา
จะไปรับถาดว่าสิ่งที่คุณสามารถทำได้

206
00:10:03,450 --> 00:10:06,330
จะปรากฏหนึ่งสูงสุดจาก
สแต็คเพียงเพราะ

207
00:10:06,330 --> 00:10:08,010
นั่นคือสิ่งที่โครงสร้างข้อมูลนี้จะ

208
00:10:08,010 --> 00:10:12,250
>> ดังนั้นโดยตรรกะว่าถ้าผม
ป๊อปบอกว่าสิ่งที่ออกมา?

209
00:10:12,250 --> 00:10:13,080
ดังนั้น 61

210
00:10:13,080 --> 00:10:15,402
ดังนั้นสิ่งที่จริงๆเป็นคอมพิวเตอร์
จะทำในหน่วยความจำ?

211
00:10:15,402 --> 00:10:16,610
รหัสของฉันไม่ต้องทำอะไร

212
00:10:16,610 --> 00:10:20,330
สิ่งที่คุณจะนำเสนอ
เราเปลี่ยนบนหน้าจอ?

213
00:10:20,330 --> 00:10:23,410
สิ่งที่ควรเปลี่ยน?

214
00:10:23,410 --> 00:10:24,960
ขออภัย?

215
00:10:24,960 --> 00:10:26,334
ดังนั้นเราจึงได้รับการกำจัดของ 61

216
00:10:26,334 --> 00:10:27,500
ดังนั้นแน่นอนผมสามารถทำเช่นนั้น

217
00:10:27,500 --> 00:10:28,640
และผมสามารถกำจัด 61

218
00:10:28,640 --> 00:10:30,980
และแล้วสิ่งอื่น ๆ
การเปลี่ยนแปลงความต้องการที่จะเกิดขึ้น?

219
00:10:30,980 --> 00:10:33,160
ขนาดอาจมีการกลับไปที่สอง

220
00:10:33,160 --> 00:10:34,210
และอื่น ๆ ที่ดี

221
00:10:34,210 --> 00:10:36,690
แต่รอสักครู่ขนาด
ช่วงเวลาที่ผ่านมาได้สาม

222
00:10:36,690 --> 00:10:38,240
ขอเพียงทำตรวจสอบอย่างรวดเร็วมีสุขภาพจิตดี

223
00:10:38,240 --> 00:10:41,810
วิธีการที่เรารู้ว่าเรา
ต้องการที่จะกำจัดของ 61?

224
00:10:41,810 --> 00:10:42,760
เพราะเรากำลัง popping

225
00:10:42,760 --> 00:10:46,450
และดังนั้นผมจึงมีขนาดของสถ​​านที่ที่สองนี้

226
00:10:46,450 --> 00:10:48,470
>> รอสักครู่ผม
คิดกลับไปสองสัปดาห์

227
00:10:48,470 --> 00:10:51,660
เมื่อเราเริ่มพูดคุยเกี่ยวกับ
อาร์เรย์ที่นี้เป็นที่ตั้งศูนย์

228
00:10:51,660 --> 00:10:55,920
นี้เป็นที่ตั้งหนึ่งนี้เป็นที่ตั้ง
ทั้งสองนี้เป็นที่ตั้งสามสี่

229
00:10:55,920 --> 00:10:58,460
ดูเหมือนว่า
ความสัมพันธ์ระหว่างขนาด

230
00:10:58,460 --> 00:11:02,780
และองค์ประกอบที่ฉันต้องการที่จะลบ
จากอาร์เรย์ที่ดูเหมือนจะเป็นสิ่งที่เพียง?

231
00:11:02,780 --> 00:11:05,120
ขนาดลบหนึ่ง

232
00:11:05,120 --> 00:11:07,786
และเพื่อให้เป็นวิธีการที่เป็นมนุษย์
เรารู้มาก่อน 61

233
00:11:07,786 --> 00:11:09,160
วิธีที่คอมพิวเตอร์จะรู้หรือไม่?

234
00:11:09,160 --> 00:11:11,701
เมื่อรหัสของคุณที่คุณอาจจะ
ต้องการที่จะทำขนาดลบหนึ่ง

235
00:11:11,701 --> 00:11:14,950
เพื่อให้สามลบหนึ่งสองและที่
หมายความว่าเราต้องการที่จะกำจัดของ 61

236
00:11:14,950 --> 00:11:18,000
และจากนั้นเราแน่นอนสามารถปรับปรุง
ขนาดเพื่อขนาดที่ตอนนี้

237
00:11:18,000 --> 00:11:20,300
ไปจากสามถึงเพียงสอง

238
00:11:20,300 --> 00:11:24,520
และเพียงเพื่อจะอวดความรู้ฉันจะ
ที่จะเสนอว่าฉันทำใช่มั้ย?

239
00:11:24,520 --> 00:11:27,660
คุณเสนอสังหรณ์ใจ
ได้อย่างถูกต้องที่ฉันควรจะได้รับการกำจัดของ 61

240
00:11:27,660 --> 00:11:30,700
แต่ยังไม่ได้ชนิดของฉัน
อากาศการเรียงลำดับของการกำจัดของ 61?

241
00:11:30,700 --> 00:11:33,790
ฉันลืมได้อย่างมีประสิทธิภาพ
ว่ามันเป็นจริงมี

242
00:11:33,790 --> 00:11:37,680
และคิดว่ากลับไป PSET4 ถ้าคุณได้อ่าน
บทความเกี่ยวกับนิติไฟล์ PDF

243
00:11:37,680 --> 00:11:40,780
ที่เรามีพวกคุณอ่านหรือคุณ
จะอ่านในสัปดาห์นี้สำหรับ PSET4

244
00:11:40,780 --> 00:11:44,300
จำได้ว่านี้เป็นจริงที่จะใกล้ชิด
ความคิดทั้งหมดของนิติคอมพิวเตอร์

245
00:11:44,300 --> 00:11:47,820
คอมพิวเตอร์คืออะไรโดยทั่วไปจะเป็น
มันก็ลืมบางสิ่งบางอย่างที่เป็น

246
00:11:47,820 --> 00:11:51,300
แต่ก็ไม่ได้ไปและไม่ชอบ
พยายามที่จะเกามันออกมาหรือแทนที่

247
00:11:51,300 --> 00:11:54,560
บิตผู้ที่มีศูนย์และคน
หรือรูปแบบอื่น ๆ สุ่ม

248
00:11:54,560 --> 00:11:56,690
จนกว่าคุณจะทำเช่นนั้นได้ด้วยตัวคุณเองโดยเจตนา

249
00:11:56,690 --> 00:11:58,930
ดังนั้นสัญชาตญาณของคุณเป็น
สิทธิขอกำจัด 61

250
00:11:58,930 --> 00:12:00,650
แต่ในความเป็นจริงเราไม่ต้องกังวล

251
00:12:00,650 --> 00:12:04,040
เราก็ต้องลืมว่า
มันมีโดยการเปลี่ยนขนาดของเรา

252
00:12:04,040 --> 00:12:05,662
>> ตอนนี้มีปัญหากับสแต็คนี้

253
00:12:05,662 --> 00:12:07,620
ถ้าผมผลักดันให้สิ่งที่
ลงบนกองสิ่งที่

254
00:12:07,620 --> 00:12:11,167
เห็นได้ชัดว่าจะเกิดขึ้น
ในเวลาเพียงไม่กี่ช่วงเวลา?

255
00:12:11,167 --> 00:12:12,500
เรากำลังจะไปทำงานออกจากพื้นที่

256
00:12:12,500 --> 00:12:13,580
และสิ่งที่เราจะทำอย่างไร

257
00:12:13,580 --> 00:12:14,680
เรากำลังเมาชนิดของ

258
00:12:14,680 --> 00:12:19,000
การดำเนินการนี​​้ไม่ได้ให้
เราปรับขนาดอาร์เรย์เพราะใช้

259
00:12:19,000 --> 00:12:21,240
รูปแบบนี้ถ้าคุณ
คิดว่ากลับไปสองสัปดาห์

260
00:12:21,240 --> 00:12:23,520
เมื่อคุณได้ประกาศ
ขนาดของอาร์เรย์

261
00:12:23,520 --> 00:12:26,780
เราไม่ได้เห็นกลไกที่ยัง
คุณสามารถเปลี่ยนขนาดของอาร์เรย์

262
00:12:26,780 --> 00:12:29,020
และแน่นอน C ไม่ได้มีคุณลักษณะที่

263
00:12:29,020 --> 00:12:32,524
ถ้าคุณบอกว่าให้ฉันห้า
NTHS เรียกพวกเขาตัวเลข

264
00:12:32,524 --> 00:12:33,940
นั่นคือทั้งหมดที่คุณกำลังจะได้รับมัน

265
00:12:33,940 --> 00:12:38,790
ดังนั้นเราจึงทำตอนนี้ในวันจันทร์ได้
ความสามารถในการแสดงวิธีการแก้ปัญหา

266
00:12:38,790 --> 00:12:42,480
แต่เราก็ต้องปรับแต่ง
คำนิยามของสแต็คของเรา

267
00:12:42,480 --> 00:12:46,840
เพื่อไม่ให้มีบางอาร์เรย์ตายตัว,
แต่เพียงในการจัดเก็บที่อยู่

268
00:12:46,840 --> 00:12:47,890
>> ตอนนี้ทำไมนี้คืออะไร?

269
00:12:47,890 --> 00:12:51,690
ตอนนี้เราก็จะต้องมีความสะดวกสบายด้วย
ความจริงที่ว่าเมื่อโปรแกรมของฉันทำงาน

270
00:12:51,690 --> 00:12:53,730
ฉันน่าจะไป
ต้องถามมนุษย์

271
00:12:53,730 --> 00:12:55,110
จำนวนตัวเลขที่คุณต้องการในการจัดเก็บ?

272
00:12:55,110 --> 00:12:56,776
ดังนั้นการป้อนข้อมูลได้ที่จะมาจากที่ไหนสักแห่ง

273
00:12:56,776 --> 00:12:59,140
แต่เมื่อฉันรู้ว่า
จำนวนแล้วฉันก็สามารถ

274
00:12:59,140 --> 00:13:02,470
ใช้สิ่งที่ทำงานที่จะให้
ฉันรู้ของหน่วยความจำหรือไม่?

275
00:13:02,470 --> 00:13:03,580
ฉันสามารถใช้ malloc

276
00:13:03,580 --> 00:13:06,710
และผมสามารถพูดได้หมายเลขใด ๆ
ไบต์ฉันต้องการกลับ NTHS เหล่านี้

277
00:13:06,710 --> 00:13:10,910
และทั้งหมดที่ฉันต้องเก็บในตัวเลข
ตัวแปรที่นี่ภายในของโครงสร้างนี้

278
00:13:10,910 --> 00:13:13,480
ควรจะเป็นสิ่งที่?

279
00:13:13,480 --> 00:13:18,440
สิ่งที่จริงจะเข้าสู่
ตัวเลขในสถานการณ์นี้

280
00:13:18,440 --> 00:13:21,300
ใช่ตัวชี้ไปแรก
ไบต์ของก้อนของหน่วยความจำที่

281
00:13:21,300 --> 00:13:24,940
หรือมากขึ้นโดยเฉพาะที่อยู่
ในครั้งแรกของผู้ไบต์

282
00:13:24,940 --> 00:13:27,300
ไม่สำคัญว่าถ้ามันเป็นหนึ่งใน
ไบต์หรือพันล้านไบต์

283
00:13:27,300 --> 00:13:28,890
ฉันต้องดูแลเกี่ยวกับครั้งแรก

284
00:13:28,890 --> 00:13:31,530
เพราะสิ่งที่ค้ำประกัน malloc และ
การค้ำประกันระบบปฏิบัติการของฉัน

285
00:13:31,530 --> 00:13:34,170
คือก้อนของหน่วยความจำฉัน
ได้รับก็เป็นไปได้ที่ต่อเนื่องกัน

286
00:13:34,170 --> 00:13:35,378
มีไม่ได้จะเป็นช่องว่าง

287
00:13:35,378 --> 00:13:38,576
ดังนั้นถ้าฉันถาม 50
ไบต์หรือ 1,000 ไบต์

288
00:13:38,576 --> 00:13:40,450
พวกเขากำลังทั้งหมดไปได้
กลับไปกลับไปกลับ

289
00:13:40,450 --> 00:13:44,500
และตราบใดที่ผมจำได้ว่าใหญ่แค่ไหน
ฉันถามสิ่งที่ผมจำเป็นต้องรู้

290
00:13:44,500 --> 00:13:46,230
คือที่อยู่ดังกล่าวครั้งแรก

291
00:13:46,230 --> 00:13:48,660
>> ดังนั้นตอนนี้เรามีความสามารถในรหัส

292
00:13:48,660 --> 00:13:51,280
แม้ว่ามันจะพาเรา
มีเวลามากขึ้นที่จะเขียนนี้ขึ้น

293
00:13:51,280 --> 00:13:55,900
ตอนนี้เราสามารถจัดสรรหน่วยความจำที่โดย
เพียงแค่การจัดเก็บที่อยู่ที่แตกต่างกันมี

294
00:13:55,900 --> 00:13:59,060
ถ้าเราต้องการที่ใหญ่กว่าหรือแม้กระทั่ง
เป็นก้อนขนาดเล็กของหน่วยความจำ

295
00:13:59,060 --> 00:14:00,170
ดังนั้นที่นี่เพื่อการค้าปิด

296
00:14:00,170 --> 00:14:01,360
ตอนนี้เราได้รับอย่างแคล่วคล่อง

297
00:14:01,360 --> 00:14:03,350
เรายังคงมี
contiguousness ฉันอ้าง

298
00:14:03,350 --> 00:14:05,881
เพราะ malloc จะให้เรา
ก้อนที่ต่อเนื่องกันของหน่วยความจำ

299
00:14:05,881 --> 00:14:08,630
แต่นี้เป็นไปได้ในความเจ็บปวด
คอสำหรับเราโปรแกรมเมอร์

300
00:14:08,630 --> 00:14:09,770
รหัสขึ้นจริง

301
00:14:09,770 --> 00:14:10,730
มันเป็นเพียงแค่การทำงานมากขึ้น

302
00:14:10,730 --> 00:14:13,930
เราจำเป็นต้องมีรหัสคล้ายกับสิ่งที่ฉันเป็น
ตีตัวออกสักครู่ที่ผ่านมา

303
00:14:13,930 --> 00:14:16,120
doable มาก แต่ก็เพิ่มความซับซ้อน

304
00:14:16,120 --> 00:14:19,520
และเพื่อให้เวลานักพัฒนาโปรแกรมเมอร์
เวลายังเป็นทรัพยากรที่อื่น

305
00:14:19,520 --> 00:14:22,520
ที่เราอาจจำเป็นต้องใช้จ่าย
เวลาที่จะได้รับคุณสมบัติใหม่

306
00:14:22,520 --> 00:14:24,020
และแล้วแน่นอนมีคิว

307
00:14:24,020 --> 00:14:26,227
เราจะไม่เข้าไปนี้
หนึ่งในรายละเอียดมาก

308
00:14:26,227 --> 00:14:27,560
แต่มันก็คล้ายกันมากในจิตวิญญาณ

309
00:14:27,560 --> 00:14:31,220
ฉันสามารถใช้คิวและ
การดำเนินงานที่สอดคล้องกันของ

310
00:14:31,220 --> 00:14:35,660
Enqueue หรือ dequeue เช่นเพิ่มหรือลบ
มันเป็นเพียงวิธีที่นักเล่นบอกว่ามัน

311
00:14:35,660 --> 00:14:38,100
enqueue หรือ dequeue ดังต่อไปนี้

312
00:14:38,100 --> 00:14:41,170
ฉันสามารถให้ตัวเอง struct
อีกครั้งมีอาร์เรย์ของจำนวนที่

313
00:14:41,170 --> 00:14:44,000
อีกครั้งที่มีขนาด
แต่ทำไมตอนนี้ผมต้องการ

314
00:14:44,000 --> 00:14:46,940
เพื่อติดตามด้านหน้าของคิวหรือไม่

315
00:14:46,940 --> 00:14:50,630
ผมไม่จำเป็นต้องรู้
ด้านหน้าของสแต็คของฉัน

316
00:14:50,630 --> 00:14:53,570
ดีถ้าฉันอีกครั้งสำหรับ
queue-- ให้เพียงอย่างหนัก

317
00:14:53,570 --> 00:14:57,870
รหัสมันมีเหมือนห้า
เลขที่อาจเกิดขึ้นที่นี่

318
00:14:57,870 --> 00:15:00,940
ดังนั้นนี่คือศูนย์หนึ่งสองสามสี่

319
00:15:00,940 --> 00:15:03,430
นี้เป็นไปได้
เรียกว่าตัวเลขอีกครั้ง

320
00:15:03,430 --> 00:15:06,940
และสิ่งนี้จะถูกเรียกว่าขนาด

321
00:15:06,940 --> 00:15:10,056
>> ทำไมมันจึงไม่เพียงพอ
จะมีขนาดเพียง?

322
00:15:10,056 --> 00:15:11,680
ดีขอผลักดันตัวเลขเดียวกันผู้ที่อยู่ใน

323
00:15:11,680 --> 00:15:14,220
ดังนั้นผมจึง pushed-- ฉัน enqueued หรือผลักดัน

324
00:15:14,220 --> 00:15:20,150
ตอนนี้ผมจะ enqueue 50 แล้ว
51, 61 แล้วและจุดจุดจุด

325
00:15:20,150 --> 00:15:21,070
ดังนั้นที่กำหนดไว้เป็นลำดับ

326
00:15:21,070 --> 00:15:23,176
ฉัน enqueued 50 แล้ว 51 แล้ว 61

327
00:15:23,176 --> 00:15:25,050
และมีลักษณะที่เหมือนกันว่า
ไปกองป่านนี้

328
00:15:25,050 --> 00:15:27,190
ยกเว้นผมไม่ต้องการที่จะทำให้การเปลี่ยนแปลงอย่างใดอย่างหนึ่ง

329
00:15:27,190 --> 00:15:33,680
ผมจำเป็นต้องปรับปรุงขนาดนี้ดังนั้นฉันไป
จากศูนย์ถึงหนึ่งไป 2-3 ในขณะนี้

330
00:15:33,680 --> 00:15:35,760
ฉันจะ dequeue อย่างไร

331
00:15:35,760 --> 00:15:36,890
ที่เกิดขึ้นกับ dequeue อะไร?

332
00:15:36,890 --> 00:15:41,950
ใครควรจะมาออกรายการนี​​้เป็นครั้งแรก
ถ้าเป็นเส้นที่ร้านแอปเปิ้ล?

333
00:15:41,950 --> 00:15:42,780
ดังนั้น 50

334
00:15:42,780 --> 00:15:44,700
ดังนั้นจึงเป็นชนิดของ trickier เวลานี้

335
00:15:44,700 --> 00:15:47,880
ขณะที่ครั้งที่แล้วมันเป็นซุปเปอร์
เรื่องง่ายที่จะทำขนาดลบหนึ่ง

336
00:15:47,880 --> 00:15:51,440
ฉันได้รับการสิ้นสุดของอาเรย์ของฉันได้อย่างมีประสิทธิภาพ
ที่ตัวเลขที่มีก็เอา 61

337
00:15:51,440 --> 00:15:52,920
แต่ฉันไม่ต้องการที่จะลบ 61

338
00:15:52,920 --> 00:15:55,030
ฉันต้องการที่จะใช้เวลา 50 ที่
มีที่ 05:00

339
00:15:55,030 --> 00:15:56,790
เข้าแถวสำหรับ
iPhone ใหม่หรือ whatnot

340
00:15:56,790 --> 00:16:01,200
และเพื่อที่จะได้รับการกำจัดของ 50 ผม
ก็ไม่สามารถทำเช่นนี้ใช่มั้ย?

341
00:16:01,200 --> 00:16:02,547
ฉันสามารถข้ามออก 50

342
00:16:02,547 --> 00:16:04,380
แต่เราก็บอกว่าเรา
ไม่จำเป็นต้องเป็นทางทวารหนั​​กเพื่อ

343
00:16:04,380 --> 00:16:06,330
เป็นรอยขีดข่วนหรือซ่อนข้อมูล

344
00:16:06,330 --> 00:16:08,090
เราก็สามารถลืมมันอยู่ที่ไหน

345
00:16:08,090 --> 00:16:12,330
>> แต่ถ้าผมเปลี่ยนขนาดของฉันตอนนี้
ทั้งสองนี้เป็นข้อมูลที่เพียงพอ

346
00:16:12,330 --> 00:16:15,711
ที่จะรู้ว่าสิ่งที่เกิดขึ้นในคิวของฉันได้อย่างไร

347
00:16:15,711 --> 00:16:16,680
ไม่ได้จริงๆ

348
00:16:16,680 --> 00:16:19,830
เช่นขนาดของฉันคือสอง แต่
ที่ไม่คิวเริ่มต้น

349
00:16:19,830 --> 00:16:22,980
โดยเฉพาะอย่างยิ่งถ้าฉันยังคงมี
ผู้ที่ตัวเลขเดียวกันในหน่วยความจำ

350
00:16:22,980 --> 00:16:24,260
50, 51, 61

351
00:16:24,260 --> 00:16:27,090
ดังนั้นผมจึงต้องจำไว้
ตอนนี้ที่ด้านหน้าเป็น

352
00:16:27,090 --> 00:16:29,630
และอื่น ๆ ตามที่ผมเสนอขึ้น
ที่นั่นเราจะได้เรียกว่าเพียงแค่

353
00:16:29,630 --> 00:16:33,729
ชับหน้าซึ่งเริ่มต้น
ค่าควรจะได้รับสิ่งที่?

354
00:16:33,729 --> 00:16:35,270
ศูนย์เพียงจุดเริ่มต้นของรายการ

355
00:16:35,270 --> 00:16:40,876
แต่ตอนนี้นอกเหนือไปจาก decrementing
ขนาดเราก็เพิ่มขึ้นด้านหน้า

356
00:16:40,876 --> 00:16:42,000
ตอนนี้ที่นี่เป็นอีกปัญหาหนึ่ง

357
00:16:42,000 --> 00:16:43,030
ดังนั้นเมื่อผมให้ไป

358
00:16:43,030 --> 00:16:47,520
คิดว่านี้คือจำนวนของ
เช่น 121, 124, และจากนั้นซ,

359
00:16:47,520 --> 00:16:48,610
ฉันออกจากพื้นที่

360
00:16:48,610 --> 00:16:50,390
แต่รอสักครู่ฉันไม่

361
00:16:50,390 --> 00:16:55,630
ดังนั้นที่จุดในเรื่องนี้
สมมติว่าขนาดเป็นหนึ่งในสอง

362
00:16:55,630 --> 00:17:00,370
สามสี่จึงคิดว่า
ขนาดสี่ด้านหน้าเป็นหนึ่ง

363
00:17:00,370 --> 00:17:01,621
ดังนั้น 51 ที่ด้านหน้า

364
00:17:01,621 --> 00:17:04,329
ฉันต้องการที่จะนำหมายเลขอื่นที่นี่
แต่บ้าผมออกจากพื้นที่

365
00:17:04,329 --> 00:17:06,710
แต่ฉันไม่ได้จริงๆใช่มั้ย?

366
00:17:06,710 --> 00:17:11,192
ที่ฉันสามารถนำบางส่วน
มูลค่าเพิ่มเช่น 171?

367
00:17:11,192 --> 00:17:13,400
ใช่ฉันทำได้เพียงแค่ชนิดของ
กลับไปที่นั่นใช่มั้ย?

368
00:17:13,400 --> 00:17:18,161
และจากนั้นก็ข้ามออก 50 หรือ
เพียงเขียนทับด้วย 171

369
00:17:18,161 --> 00:17:20,410
และถ้าคุณกำลังสงสัยว่าทำไม
ตัวเลขที่เราได้สุ่มเช่นนั้น

370
00:17:20,410 --> 00:17:24,150
เหล่านี้จะถูกนำทั่วไปคอมพิวเตอร์
หลักสูตรวิทยาศาสตร์ที่ Harvard หลังจาก CS50

371
00:17:24,150 --> 00:17:27,510
แต่นั่นก็เป็นการเพิ่มประสิทธิภาพที่ดี
เพราะตอนนี้ผมไม่ได้สูญเสียพื้นที่

372
00:17:27,510 --> 00:17:30,750
ฉันยังคงต้องจำไว้
วิธีการใหญ่สิ่งนี้รวม

373
00:17:30,750 --> 00:17:31,500
มันเป็นห้ารวม

374
00:17:31,500 --> 00:17:33,375
เพราะผมไม่ต้องการที่จะ
เริ่มต้นการเขียนทับ 51

375
00:17:33,375 --> 00:17:36,260
ดังนั้นตอนนี้ผมยังคงออกจากพื้นที่
เพื่อให้ปัญหาที่เกิดขึ้นเช่นเดียวกับก่อน

376
00:17:36,260 --> 00:17:39,140
แต่คุณสามารถดูวิธีการในขณะนี้
ในรหัสของคุณคุณอาจ

377
00:17:39,140 --> 00:17:41,910
ต้องเขียนเล็ก ๆ น้อย ๆ
ความซับซ้อนที่จะทำให้มันเกิดขึ้น

378
00:17:41,910 --> 00:17:44,510
และในความเป็นจริงสิ่งที่ผู้ประกอบการ
ใน C อาจจะช่วยให้

379
00:17:44,510 --> 00:17:48,110
คุณทำเช่นนี้ได้อย่างน่าอัศจรรย์วัฏจักรหรือไม่

380
00:17:48,110 --> 00:17:50,160
ใช่ผู้ประกอบการโมดูโล,
สัญญาณที่ร้อยละ

381
00:17:50,160 --> 00:17:53,160
ดังนั้นสิ่งที่เป็นชนิดของดีๆเกี่ยวกับคิว
แม้ว่าเราจะเก็บอาร์เรย์การวาดภาพ

382
00:17:53,160 --> 00:17:56,520
เหล่านี้เป็นเส้นตรงเช่นถ้าคุณ
ชนิดของการคิดเกี่ยวกับเรื่องนี้เป็นโค้ง

383
00:17:56,520 --> 00:18:00,341
รอบเป็นวงกลมแล้วก็
สังหรณ์ใจชนิดของมันทำงานจิตใจ

384
00:18:00,341 --> 00:18:01,590
ผมคิดว่าเล็ก ๆ น้อย ๆ อย่างหมดจด

385
00:18:01,590 --> 00:18:05,190
คุณยังจะต้องดำเนินการ
ว่ารูปแบบทางจิตในรหัส

386
00:18:05,190 --> 00:18:07,550
ดังนั้นไม่ยาก
ท้ายที่สุดที่จะใช้

387
00:18:07,550 --> 00:18:12,430
แต่เรายังคงสูญเสีย size-- ค่อนข้างที่
ความสามารถในการปรับขนาด, หากเราทำเช่นนี้

388
00:18:12,430 --> 00:18:15,310
>> เราจะต้องได้รับการกำจัดของอาร์เรย์เรา
แทนที่ด้วยตัวชี้เดียว

389
00:18:15,310 --> 00:18:20,010
แล้วที่ไ​​หนสักแห่งในรหัสของฉันฉันมี
โทรสิ่งที่ทำงานจริงสร้าง

390
00:18:20,010 --> 00:18:23,720
อาร์เรย์ที่เรียกว่าตัวเลข?

391
00:18:23,720 --> 00:18:26,190
malloc หรือบางที่คล้ายกัน
ฟังก์ชั่นว่า

392
00:18:26,190 --> 00:18:30,481
คำถามใด ๆ เกี่ยวกับกองหรือคิว

393
00:18:30,481 --> 00:18:30,980
ใช่?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
คำถามที่ดี.

396
00:18:34,240 --> 00:18:35,830
สิ่งที่โมดูโลที่คุณจะใช้ที่นี่

397
00:18:35,830 --> 00:18:38,520
ดังนั้นโดยทั่วไปเมื่อมีการใช้
สมัยคุณจะทำมัน

398
00:18:38,520 --> 00:18:40,620
ที่มีขนาดของ
โครงสร้างข้อมูลทั้งหมด

399
00:18:40,620 --> 00:18:44,120
ดังนั้นสิ่งที่ต้องการความจุห้าหรือถ้า
ก็คงอาจจะมีส่วนเกี่ยวข้อง

400
00:18:44,120 --> 00:18:47,100
แต่เพียงแค่การทำแบบโมดูโลห้า
อาจจะไม่เพียงพอ

401
00:18:47,100 --> 00:18:51,380
เพราะเราจำเป็นต้องรู้ว่าเราทำ
ห่อรอบที่นี่หรือที่นี่หรือที่นี่

402
00:18:51,380 --> 00:18:54,160
ดังนั้นคุณอาจจะยัง
จะต้องการที่จะมีส่วนร่วม

403
00:18:54,160 --> 00:18:57,220
ขนาดของสิ่งหรือ
ตัวแปรหน้าได้เป็นอย่างดี

404
00:18:57,220 --> 00:19:00,140
ดังนั้นจึงเป็นเพียงแค่นี้ค่อนข้าง
การแสดงออกทางคณิตศาสตร์ที่เรียบง่าย

405
00:19:00,140 --> 00:19:02,000
แต่โมดูโลจะเป็นองค์ประกอบที่สำคัญ

406
00:19:02,000 --> 00:19:03,330
>> หนังสั้นดังนั้นถ้าคุณจะ

407
00:19:03,330 --> 00:19:05,780
ภาพเคลื่อนไหวที่บาง
folks ที่มหาวิทยาลัยอื่น

408
00:19:05,780 --> 00:19:08,060
ใส่กันที่เราได้
เหมาะสำหรับการสนทนานี้

409
00:19:08,060 --> 00:19:12,630
มันเกี่ยวข้องกับแจ็คการเรียนรู้
ข้อเท็จจริงเกี่ยวกับการรอคิวและสถิติ

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> ฟิล์ม: กาลครั้งหนึ่ง,
มีผู้ชายที่ชื่อแจ็ค

412
00:19:21,890 --> 00:19:25,330
เมื่อมันมาถึงการทำเพื่อน
แจ็คไม่ได้มีความสามารถพิเศษ

413
00:19:25,330 --> 00:19:28,220
ดังนั้นแจ็คก็ไปพูดคุยกับ
คนที่นิยมมากที่สุดที่เขารู้

414
00:19:28,220 --> 00:19:30,920
เขาเดินไปที่ลูและถามว่าฉันจะทำอย่างไร?

415
00:19:30,920 --> 00:19:33,400
ลูเห็นว่าเพื่อนของเขา
เป็นทุกข์จริงๆ

416
00:19:33,400 --> 00:19:36,050
ดีเขาเริ่มเพียง
ดูวิธีการที่คุณสวมใส่

417
00:19:36,050 --> 00:19:38,680
คุณไม่มีเสื้อผ้าใด ๆ
ด้วยรูปลักษณ์ที่แตกต่างกันอย่างไร

418
00:19:38,680 --> 00:19:39,660
ใช่แจ็คกล่าวว่า

419
00:19:39,660 --> 00:19:40,840
ผมแน่ใจว่าจะทำอย่างไร

420
00:19:40,840 --> 00:19:43,320
มาที่บ้านของฉันและ
ฉันจะแสดงให้คุณเห็น

421
00:19:43,320 --> 00:19:44,550
ดังนั้นพวกเขาจึงออกไปของแจ็ค

422
00:19:44,550 --> 00:19:47,520
และแสดงให้เห็นว่าแจ็คลูกล่อง
ที่เขาเก็บเสื้อของเขาทั้งหมด

423
00:19:47,520 --> 00:19:49,260
และกางเกงขายาวของเขาและถุงเท้าของเขา

424
00:19:49,260 --> 00:19:52,290
ลูกล่าวว่าผมเห็นคุณมี
เสื้อผ้าของคุณทั้งหมดในกอง

425
00:19:52,290 --> 00:19:54,870
ทำไมคุณไม่สวมใส่บาง
คนอื่น ๆ ครั้งในชั่วขณะ?

426
00:19:54,870 --> 00:19:58,020
>> แจ็คกล่าวว่าดีเมื่อฉัน
เอาเสื้อผ้าและถุงเท้า

427
00:19:58,020 --> 00:20:00,780
ผมล้างพวกเขาและใส่
พวกเขาออกไปในกล่อง

428
00:20:00,780 --> 00:20:03,210
แล้วมาต่อไป
เช้าและฉันกระโดดขึ้น

429
00:20:03,210 --> 00:20:06,380
ฉันไปที่กล่องและได้รับ
เสื้อผ้าของฉันออกด้านบน

430
00:20:06,380 --> 00:20:09,070
ลูตระหนักได้อย่างรวดเร็ว
ปัญหาที่เกิดขึ้นกับแจ็ค

431
00:20:09,070 --> 00:20:12,080
เขาเก็บเสื้อผ้าของซีดี
และหนังสือในกอง

432
00:20:12,080 --> 00:20:14,420
เมื่อเขาไปถึงสำหรับ
บางสิ่งบางอย่างที่จะอ่านหรือการสวมใส่

433
00:20:14,420 --> 00:20:17,100
เขาจะเลือกหนังสือด้านบนหรือชุดชั้นใน

434
00:20:17,100 --> 00:20:19,500
จากนั้นเมื่อเขาทำเขา
จะวางไว้ด้านหลังขวา

435
00:20:19,500 --> 00:20:21,970
กลับมันจะไปที่ด้านบนของสแต็ค

436
00:20:21,970 --> 00:20:24,460
ฉันรู้ว่าการแก้ปัญหา
กล่าวว่าชัยชนะดัง

437
00:20:24,460 --> 00:20:27,090
คุณต้องเรียนรู้ที่จะ
เริ่มใช้คิว

438
00:20:27,090 --> 00:20:29,870
ลูเอาเสื้อผ้าของแจ็คและ
แขวนไว้ในตู้เสื้อผ้า

439
00:20:29,870 --> 00:20:32,710
และเมื่อเขาได้หมด
กล่องเขาก็โยนมัน

440
00:20:32,710 --> 00:20:36,500
>> จากนั้นเขาก็กล่าวว่าตอนนี้แจ็คในตอนท้ายของ
วันที่ใส่เสื้อผ้าของคุณด้านซ้าย

441
00:20:36,500 --> 00:20:37,990
เมื่อคุณใส่พวกเขาออกไป

442
00:20:37,990 --> 00:20:41,300
แล้วพรุ่งนี้เช้าเมื่อคุณ
เห็นแสงแดดที่ได้รับเสื้อผ้าของคุณ

443
00:20:41,300 --> 00:20:43,440
ด้านขวาจากจุดสิ้นสุดของเส้น

444
00:20:43,440 --> 00:20:44,880
คุณไม่เห็น? ลูกล่าวว่า

445
00:20:44,880 --> 00:20:46,370
มันจะดีมาก

446
00:20:46,370 --> 00:20:49,770
คุณจะได้สวมใส่ทุกอย่างในครั้งเดียว
ก่อนที่คุณจะสวมใส่สิ่งที่เป็นครั้งที่สอง

447
00:20:49,770 --> 00:20:52,670
และมีทุกอย่างที่อยู่ในคิว
ในตู้เสื้อผ้าและชั้นวางของเขา

448
00:20:52,670 --> 00:20:55,160
แจ็คเริ่มรู้สึก
ค่อนข้างแน่ใจว่าตัวเอง

449
00:20:55,160 --> 00:20:59,720
ขอบคุณทุกลูและ
คิวยอดเยี่ยมของเขา

450
00:20:59,720 --> 00:21:01,220
ลำโพงที่ 1: สิทธิทั้งหมดมันเป็นเรื่องที่น่ารัก

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
ดังนั้นสิ่งที่ได้รับจริงที่เกิดขึ้น
ในใต้ฝากระโปรงตอนนี้?

453
00:21:10,080 --> 00:21:12,370
ว่าเรามีตัวชี้
ที่เรามี malloc,

454
00:21:12,370 --> 00:21:15,680
ว่าเรามีความสามารถในการสร้าง
ชิ้นของหน่วยความจำสำหรับตัวเอง

455
00:21:15,680 --> 00:21:16,344
แบบไดนามิก

456
00:21:16,344 --> 00:21:18,510
ดังนั้นนี่คือภาพที่เรา
เห็นเพียงวันอื่น ๆ

457
00:21:18,510 --> 00:21:21,180
เราไม่ได้จริงๆอาศัยอยู่
ใน แต่ภาพนี้

458
00:21:21,180 --> 00:21:24,180
มีเกิดขึ้นอยู่ภายใต้
เครื่องดูดควันสำหรับสัปดาห์นี้

459
00:21:24,180 --> 00:21:27,050
ดังนั้นนี้เป็นเพียง
สี่เหลี่ยมผืนผ้าที่เราได้วาด,

460
00:21:27,050 --> 00:21:28,180
หน่วยความจำของคอมพิวเตอร์ของคุณ

461
00:21:28,180 --> 00:21:31,850
และบางทีคอมพิวเตอร์ของคุณหรือ CS50
ID มีกิกะไบต์หน่วยความจำหรือแรม

462
00:21:31,850 --> 00:21:33,050
หรือสองหรือสี่กิกะไบต์

463
00:21:33,050 --> 00:21:34,450
มันไม่สำคัญว่าจริงๆ

464
00:21:34,450 --> 00:21:37,240
ระบบปฏิบัติการของคุณ
Windows หรือ Mac OS หรือ Linux

465
00:21:37,240 --> 00:21:41,120
หลักช่วยให้โปรแกรมของคุณ
ที่จะคิดว่ามันมีการเข้าถึง

466
00:21:41,120 --> 00:21:42,982
เพื่อความสมบูรณ์ของ
หน่วยความจำของคอมพิวเตอร์ของคุณ

467
00:21:42,982 --> 00:21:45,440
แม้ว่าคุณอาจจะทำงาน
โปรแกรมหลายครั้ง

468
00:21:45,440 --> 00:21:46,990
ดังนั้นในความเป็นจริงที่ไม่ได้ทำงานจริงๆ

469
00:21:46,990 --> 00:21:49,448
แต่มันเป็นชนิดของภาพลวงตา
มอบให้กับทุกโปรแกรมของคุณ

470
00:21:49,448 --> 00:21:53,110
ดังนั้นถ้าคุณมีสองกิ๊กของแรมนี้
เป็นวิธีการที่เครื่องคอมพิวเตอร์อาจจะคิดว่ามัน

471
00:21:53,110 --> 00:21:57,110
>> ตอนนี้บังเอิญหนึ่งในจำนวนนี้
สิ่งหนึ่งในกลุ่มเหล่านี้ของหน่วยความจำ

472
00:21:57,110 --> 00:21:58,350
เรียกว่ากอง

473
00:21:58,350 --> 00:22:01,680
และแน่นอนทุกเวลา
ป่านนี้ในการเขียนรหัส

474
00:22:01,680 --> 00:22:05,900
ที่คุณได้เรียกว่า
ฟังก์ชั่นเช่นหลัก

475
00:22:05,900 --> 00:22:08,410
จำได้ว่าเวลาใดที่ฉันได้
หน่วยความจำคอมพิวเตอร์วาดของ

476
00:22:08,410 --> 00:22:10,640
ฉันมักจะวาดการเรียงลำดับของ
ครึ่งหนึ่งของรูปสี่เหลี่ยมผืนผ้าที่นี่

477
00:22:10,640 --> 00:22:12,520
และไม่รบกวนการพูดคุย
เกี่ยวกับสิ่งที่กล่าวข้างต้น

478
00:22:12,520 --> 00:22:15,980
เพราะเมื่อหลักที่เรียกว่าผมเรียกร้อง
ที่คุณได้รับเศษไม้จากหน่วยความจำนี้

479
00:22:15,980 --> 00:22:16,970
ที่จะไปลงที่นี่

480
00:22:16,970 --> 00:22:20,650
และถ้าหลักที่เรียกว่าฟังก์ชั่น
เช่นการแลกเปลี่ยนดีแลกเปลี่ยนที่นี่

481
00:22:20,650 --> 00:22:23,720
และปรากฎว่า
ที่มันสิ้นสุด

482
00:22:23,720 --> 00:22:26,277
ในสิ่งที่เรียกว่ากอง
ภายในของหน่วยความจำของคอมพิวเตอร์ของคุณ

483
00:22:26,277 --> 00:22:28,360
ตอนนี้ในตอนท้ายของวัน
นี้เป็นเพียงที่อยู่

484
00:22:28,360 --> 00:22:30,680
มันเหมือนไบต์ศูนย์
ไบต์หนึ่งไบต์ 2 พันล้าน

485
00:22:30,680 --> 00:22:33,130
แต่ถ้าคุณคิดเกี่ยวกับมัน
เป็นวัตถุรูปสี่เหลี่ยมนี้

486
00:22:33,130 --> 00:22:35,130
ทุกสิ่งที่เรากำลังทำทุก
เวลาที่เราเรียกฟังก์ชั่นเป็น

487
00:22:35,130 --> 00:22:37,180
layering ชิ้นใหม่ของหน่วยความจำ

488
00:22:37,180 --> 00:22:41,700
เรากำลังให้ฟังก์ชั่นที่ชิ้น
ของหน่วยความจำของตัวเองในการทำงานกับ

489
00:22:41,700 --> 00:22:44,490
>> และจำได้ว่าตอนนี้นี้เป็นสิ่งสำคัญ

490
00:22:44,490 --> 00:22:46,400
เพราะถ้าหากเราจะมี
สิ่งที่ต้องการแลกเปลี่ยน

491
00:22:46,400 --> 00:22:51,610
และสองตัวแปรท้องถิ่นเช่น A และ B และ
เราเปลี่ยนค่าเหล่านั้นจากที่หนึ่งและสอง

492
00:22:51,610 --> 00:22:55,130
สองและเป็นหนึ่งในการเรียกคืน
ว่าเมื่อผลตอบแทนแลกเปลี่ยน

493
00:22:55,130 --> 00:22:58,330
มันราวกับว่าชิ้นนี้
ของหน่วยความจำจะหายไปเพียง

494
00:22:58,330 --> 00:23:00,080
ในความเป็นจริงก็ยังคง
มี forensically

495
00:23:00,080 --> 00:23:01,940
และสิ่งที่ยังคงเป็นจริงมี

496
00:23:01,940 --> 00:23:05,410
แต่แนวคิดก็เป็น
แม้ว่ามันจะหายไปอย่างสมบูรณ์

497
00:23:05,410 --> 00:23:10,910
และที่สำคัญเพื่อไม่ทราบใด ๆ ของการทำงาน
ที่ได้ทำในฟังก์ชั่นการแลกเปลี่ยนนั้น

498
00:23:10,910 --> 00:23:14,890
เว้นแต่จะผ่านจริงเหล่านั้น
โดยตัวชี้ข้อโต้แย้งหรือการอ้างอิง

499
00:23:14,890 --> 00:23:17,790
ตอนนี้การแก้ปัญหาพื้นฐาน
ในการแก้ไขปัญหาที่มีการแลกเปลี่ยน

500
00:23:17,790 --> 00:23:19,970
จะผ่านสิ่งที่อยู่ในที่อยู่

501
00:23:19,970 --> 00:23:23,250
แต่มันกลับกลายเป็นเหมือนกันว่ามีอะไร
รับไปในข้างต้นเป็นส่วนหนึ่ง

502
00:23:23,250 --> 00:23:26,330
ของสี่เหลี่ยมตลอดเวลานี้
ยังมีหน่วยความจำมากขึ้นมี

503
00:23:26,330 --> 00:23:28,790
และเมื่อคุณแบบไดนามิก
จัดสรรหน่วยความจำ

504
00:23:28,790 --> 00:23:32,020
ไม่ว่าจะเป็นด้านในของ GetString ซึ่ง
เราได้รับการทำสำหรับคุณใน CS50

505
00:23:32,020 --> 00:23:34,710
ห้องสมุดหรือถ้าพวกคุณ
เรียก malloc และขอให้

506
00:23:34,710 --> 00:23:37,950
ระบบปฏิบัติการสำหรับก้อนของ
หน่วยความจำมันไม่ได้มาจากกอง

507
00:23:37,950 --> 00:23:40,960
มันมาจากที่อื่น
ในหน่วยความจำของคอมพิวเตอร์ของคุณ

508
00:23:40,960 --> 00:23:42,220
ที่เรียกว่ากอง

509
00:23:42,220 --> 00:23:43,430
และที่ไม่แตกต่างกัน

510
00:23:43,430 --> 00:23:44,285
มันเป็นแรมเดียวกัน

511
00:23:44,285 --> 00:23:45,160
มันเป็นหน่วยความจำเดียวกัน

512
00:23:45,160 --> 00:23:49,080
มันเป็นเพียงแค่แรมที่ขึ้น
มีแทนที่จะลงที่นี่

513
00:23:49,080 --> 00:23:50,750
>> ดังนั้นสิ่งที่หมายความว่า?

514
00:23:50,750 --> 00:23:53,650
ดีถ้าคอมพิวเตอร์ของคุณมี
จำนวน จำกัด ของหน่วยความจำ

515
00:23:53,650 --> 00:23:57,450
และสแต็คที่มีการเติบโตขึ้นดังนั้น
ที่จะพูดและกองตาม

516
00:23:57,450 --> 00:23:59,349
ไปที่ลูกศรนี้มีการเติบโตลดลง

517
00:23:59,349 --> 00:24:01,140
ในคำอื่น ๆ ทุกคน
ครั้งที่คุณโทร malloc,

518
00:24:01,140 --> 00:24:03,430
คุณกำลังจะได้รับชิ้น
ของหน่วยความจำมาจากเบื้องบน

519
00:24:03,430 --> 00:24:06,630
แล้วอาจจะต่ำกว่าเล็กน้อยแล้วเล็กน้อย
ต่ำกว่าครั้งที่คุณโทร malloc ทุก

520
00:24:06,630 --> 00:24:10,100
กองก็ใช้งาน
เป็นชนิดของการเจริญเติบโต

521
00:24:10,100 --> 00:24:11,950
การเจริญเติบโตใกล้ชิดและใกล้ชิดกับสิ่งที่?

522
00:24:11,950 --> 00:24:13,382
สแต็ค

523
00:24:13,382 --> 00:24:14,840
ดังนั้นนี้ไม่ได้ดูเหมือนเป็นความคิดที่ดี?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
ผมหมายถึงที่มันไม่ชัดเจนจริงๆ
อะไรที่คุณสามารถทำได้ถ้าคุณเพียง

526
00:24:22,140 --> 00:24:23,910
มีจำนวน จำกัด ของหน่วยความจำ

527
00:24:23,910 --> 00:24:25,200
แต่นี้ไม่ดีแน่

528
00:24:25,200 --> 00:24:27,920
ทั้งสองลูกศรที่อยู่บน
ความผิดพลาดแน่นอนสำหรับอีกคนหนึ่ง

529
00:24:27,920 --> 00:24:31,930
>> และปรากฎว่าคนเลว, คนที่
โดยเฉพาะอย่างยิ่งที่ดีกับการเขียนโปรแกรม

530
00:24:31,930 --> 00:24:36,140
และพยายามที่จะตัดเข้าสู่คอมพิวเตอร์
สามารถใช้ประโยชน์ความเป็นจริงนี้

531
00:24:36,140 --> 00:24:38,290
ในความเป็นจริงให้พิจารณา
ตัวอย่างเล็ก ๆ น้อย ๆ

532
00:24:38,290 --> 00:24:41,350
ดังนั้นนี่คือตัวอย่างเช่นคุณสามารถอ่าน
เกี่ยวกับรายละเอียดเพิ่มเติมเกี่ยวกับวิกิพีเดีย

533
00:24:41,350 --> 00:24:43,100
เราจะชี้ให้คุณที่
ถ้าอยากรู้บทความ

534
00:24:43,100 --> 00:24:45,650
แต่มีการโจมตีโดยทั่วไป
ที่รู้จักกันเป็นหน่วยความจำล้นที่

535
00:24:45,650 --> 00:24:49,570
มีชีวิตอยู่ให้นานที่สุดเท่าที่มนุษย์
มีความสามารถในการจัดการ

536
00:24:49,570 --> 00:24:53,120
หน่วยความจำของคอมพิวเตอร์โดยเฉพาะอย่างยิ่งใน C.
ดังนั้นนี้เป็นโปรแกรมใดมาก

537
00:24:53,120 --> 00:24:55,130
แต่ให้อ่านได้จากด้านล่างขึ้น

538
00:24:55,130 --> 00:24:57,650
หลักลงในถ่านดาว argc argv

539
00:24:57,650 --> 00:24:59,830
ดังนั้นจึงเป็นโปรแกรมที่ใช้
อาร์กิวเมนต์บรรทัดคำสั่ง

540
00:24:59,830 --> 00:25:03,620
และที่สำคัญทุกคนไม่เห็นได้ชัดคือการเรียกร้อง
ฟังก์ชั่นที่เรียกว่า F สำหรับความเรียบง่าย

541
00:25:03,620 --> 00:25:04,610
และมันก็ผ่านไปในสิ่งที่?

542
00:25:04,610 --> 00:25:05,490
argv หนึ่ง

543
00:25:05,490 --> 00:25:09,320
ดังนั้นจึงผ่านเข้าไปในสิ่งที่ F
เป็นคำที่ว่าผู้ใช้พิมพ์

544
00:25:09,320 --> 00:25:11,500
ที่พรอมต์หลังจากที่
ชื่อโปรแกรมที่ทุก

545
00:25:11,500 --> 00:25:15,730
มากเช่นซีซาร์หรือ Vigenere ซึ่ง
คุณอาจจำทำกับ argv

546
00:25:15,730 --> 00:25:16,680
>> ดังนั้นสิ่งที่เป็น F?

547
00:25:16,680 --> 00:25:19,760
F ใช้เวลาในสตริง
เป็นอาร์กิวเมนต์ แต่เพียงผู้เดียว

548
00:25:19,760 --> 00:25:22,100
AKA ดาวถ่านเดียวกัน
สิ่งที่เป็นสตริง

549
00:25:22,100 --> 00:25:24,920
และก็เรียกว่าโดยพลการ
บาร์ในตัวอย่างนี้

550
00:25:24,920 --> 00:25:27,710
และแล้วถ่านค 12
เพียง แต่ในแง่ของคนธรรมดา

551
00:25:27,710 --> 00:25:31,750
สิ่งที่เป็นถ่านวงเล็บค 12 ทำสำหรับเรา?

552
00:25:31,750 --> 00:25:33,440
มันเป็นสิ่งที่ทำอย่างไร

553
00:25:33,440 --> 00:25:36,490
จัดสรรหน่วยความจำโดยเฉพาะ
12 ไบต์ 12 ตัวอักษร

554
00:25:36,490 --> 00:25:36,990
ที่แน่นอน

555
00:25:36,990 --> 00:25:40,000
และแล้วบรรทัดสุดท้าย, ผัดและ
คัดลอกคุณอาจไม่เคยเห็น

556
00:25:40,000 --> 00:25:43,360
นี่เป็นสำเนาสตริง
ฟังก์ชั่นที่มีจุดมุ่งหมายในชีวิต

557
00:25:43,360 --> 00:25:48,160
คือการคัดลอกอาร์กิวเมนต์ที่สองของ
โต้เถียงแรก

558
00:25:48,160 --> 00:25:51,190
แต่ขึ้นไป
จำนวนหนึ่งไบต์

559
00:25:51,190 --> 00:25:53,860
ดังนั้นอาร์กิวเมนต์ที่สามกล่าวว่า
จำนวนไบต์คุณควรคัดลอก?

560
00:25:53,860 --> 00:25:56,720
ความยาวของบาร์
สิ่งที่ผู้ใช้พิมพ์ลงใน

561
00:25:56,720 --> 00:25:59,320
และเนื้อหาของ
บาร์, สตริงที่มี

562
00:25:59,320 --> 00:26:02,330
คัดลอกลงในหน่วยความจำที่ชี้ไปที่ซี

563
00:26:02,330 --> 00:26:04,060
>> ดังนั้นนี้ดูเหมือนว่าชนิดของโง่และมันก็เป็น

564
00:26:04,060 --> 00:26:06,300
มันเป็นตัวอย่างที่ประดิษฐ์,
แต่มันก็เป็นตัวแทน

565
00:26:06,300 --> 00:26:10,100
ของชั้นเรียนของเวกเตอร์โจมตี,
วิธีการโจมตีโปรแกรมได้

566
00:26:10,100 --> 00:26:15,050
ทั้งหมดเป็นสิ่งที่ดีและสิ่งที่ดีถ้าผู้ใช้
ชนิดในคำว่า 11 ตัวอักษร

567
00:26:15,050 --> 00:26:18,040
หรือน้อยกว่ารวมทั้งศูนย์ทับขวา

568
00:26:18,040 --> 00:26:22,830
เกิดอะไรขึ้นถ้าผู้ใช้ชนิดในกว่า
11 หรือ 12 หรือ 20 หรือ 50 ตัวอักษร?

569
00:26:22,830 --> 00:26:25,090
โปรแกรมนี้จะทำคืออะไร?

570
00:26:25,090 --> 00:26:29,360
ความผิดพลาดที่อาจเกิด seg มันจะ
สุ่มสี่สุ่มห้าคัดลอกทุกอย่างในแถบขึ้น

571
00:26:29,360 --> 00:26:31,750
ความยาวของซึ่งเป็น
แท้จริงทุกอย่างในบาร์

572
00:26:31,750 --> 00:26:36,307
เข้าไปในที่อยู่ชี้ไปที่ซี แต่ C
มีเพียงได้รับ preemptively 12 ไบต์

573
00:26:36,307 --> 00:26:37,640
แต่ไม่มีการตรวจสอบเพิ่มเติม

574
00:26:37,640 --> 00:26:38,700
ไม่มีถ้าเงื่อนไข

575
00:26:38,700 --> 00:26:40,580
มีข้อผิดพลาดไม่ได้ตรวจสอบที่นี่

576
00:26:40,580 --> 00:26:43,270
>> และเพื่อให้สิ่งที่โปรแกรมนี้คือ
จะทำคือเพียงสุ่มสี่สุ่มห้า

577
00:26:43,270 --> 00:26:45,750
คัดลอกสิ่งที่หนึ่งไปยังอีก

578
00:26:45,750 --> 00:26:47,880
ดังนั้นถ้าเราวาดนี้
เป็นรูปภาพที่นี่

579
00:26:47,880 --> 00:26:49,860
เพียงเศษไม้ของพื้นที่หน่วยความจำ

580
00:26:49,860 --> 00:26:53,470
ดังนั้นสังเกตที่ด้านล่างเรา
มีบาร์ตัวแปรท้องถิ่น

581
00:26:53,470 --> 00:26:57,330
ดังนั้นตัวชี้ว่าจะ store-- ว่า
ค่อนข้างที่โต้แย้งในท้องถิ่นที่

582
00:26:57,330 --> 00:26:58,672
จะเก็บบาร์สตริง

583
00:26:58,672 --> 00:27:00,380
และจากนั้นก็สังเกตเห็นเพียง
ดังกล่าวข้างต้นในกอง

584
00:27:00,380 --> 00:27:02,505
เพราะเวลาที่คุณถามทุก
สำหรับหน่วยความจำบนกอง

585
00:27:02,505 --> 00:27:04,310
มันจะไปนิด ๆ หน่อย ๆ
เหนือ pictorially,

586
00:27:04,310 --> 00:27:06,270
แจ้งให้ทราบว่าเรามี 12 ไบต์มี

587
00:27:06,270 --> 00:27:10,690
หนึ่งบนซ้ายเป็นวงเล็บ C ศูนย์และ
หนึ่งที่เหมาะสมล่างคือยึด C 11

588
00:27:10,690 --> 00:27:12,870
นั่นเป็นเพียงวิธีการที่คอมพิวเตอร์
ไปวางมันออกมา

589
00:27:12,870 --> 00:27:18,300
ดังนั้นเพียงแค่สังหรณ์ใจถ้าแถบมี
กว่า 12 ตัวอักษรในทั้งหมดรวมถึง

590
00:27:18,300 --> 00:27:25,790
เครื่องหมายศูนย์ซึ่งเป็น
12 หรือวงเล็บ C 12 จะไป?

591
00:27:25,790 --> 00:27:28,440
หรือมากกว่าที่เป็นที่ 12
ตัวอักษรหรือตัวอักษรที่ 13

592
00:27:28,440 --> 00:27:30,900
ตัวอักษรที่ร้อยไป
ที่จะจบลงในภาพหรือไม่

593
00:27:30,900 --> 00:27:33,400
สูงหรือต่ำกว่า?

594
00:27:33,400 --> 00:27:36,300
>> ขวาเพราะแม้ว่า
สแต็คของตัวเองเติบโตขึ้น

595
00:27:36,300 --> 00:27:39,590
เมื่อคุณได้นำสิ่งที่อยู่ใน
มันด้วยเหตุผลที่การออกแบบ

596
00:27:39,590 --> 00:27:41,294
ทำให้หน่วยความจำจากบนลงล่าง

597
00:27:41,294 --> 00:27:44,460
ดังนั้นถ้าคุณได้มีมากกว่า 12 ไบต์
คุณกำลังจะเริ่มต้นในการเขียนทับบาร์

598
00:27:44,460 --> 00:27:47,280
ตอนนี้ที่ข้อผิดพลาด แต่มัน
ไม่ได้จริงๆเป็นเรื่องใหญ่

599
00:27:47,280 --> 00:27:51,130
แต่มันเป็นเรื่องใหญ่เพราะมี
สิ่งอื่น ๆ อีกที่เกิดขึ้นในหน่วยความจำ

600
00:27:51,130 --> 00:27:53,074
ดังนั้นนี่คือวิธีการที่เราอาจจะ
ใส่สวัสดีต้องมีความชัดเจน

601
00:27:53,074 --> 00:27:54,490
ถ้าผมพิมพ์ลงในสวัสดีที่พรอมต์

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O เครื่องหมายศูนย์จบลงภายใน
ผู้ที่ 12 ไบต์และเราจะปลอดภัยสุด

603
00:27:59,330 --> 00:28:00,330
ทั้งหมดเป็นอย่างดี.

604
00:28:00,330 --> 00:28:03,020
แต่ถ้าผมพิมพ์บางสิ่งบางอย่าง
อีกต่อไปที่อาจเกิดขึ้นมันเป็น

605
00:28:03,020 --> 00:28:05,860
จะคืบคลานเข้ามาในพื้นที่แถบ

606
00:28:05,860 --> 00:28:08,405
แต่แย่ลงยังก็จะเปิด
ออกทั้งหมดเวลานี้

607
00:28:08,405 --> 00:28:11,530
แม้ว่าเราจะไม่เคยพูดคุยเกี่ยวกับ
มันสแต็คที่ใช้สำหรับสิ่งอื่น ๆ

608
00:28:11,530 --> 00:28:13,560
มันไม่ใช่แค่ตัวแปรท้องถิ่น

609
00:28:13,560 --> 00:28:15,100
>> ซีเป็นภาษาระดับต่ำมาก

610
00:28:15,100 --> 00:28:17,810
และการจัดเรียงของแอบ
ใช้สแต็คยัง

611
00:28:17,810 --> 00:28:21,260
ที่ต้องจำไว้เมื่อ
ฟังก์ชั่นที่เรียกว่าสิ่งที่

612
00:28:21,260 --> 00:28:26,040
ที่อยู่ของการทำงานก่อนหน้านี้
เพื่อที่จะสามารถกระโดดกลับไปที่ฟังก์ชั่นที่

613
00:28:26,040 --> 00:28:29,980
ดังนั้นเมื่อสลับสายหลักหมู่
สิ่งที่ผลักลงบนกอง

614
00:28:29,980 --> 00:28:34,380
ไม่เพียง แต่แลกเปลี่ยนตัวแปรท้องถิ่น
หรือข้อโต้แย้งที่ยังผลักดันแอบ

615
00:28:34,380 --> 00:28:37,510
บนสแต็คเป็นตัวแทน
โดยชิ้นสีแดงที่นี่

616
00:28:37,510 --> 00:28:40,520
เป็นที่อยู่ของหลักทางร่างกาย
ในหน่วยความจำของคอมพิวเตอร์ของคุณ

617
00:28:40,520 --> 00:28:44,180
เพื่อที่ว่าเมื่อแลกเปลี่ยนจะทำคอมพิวเตอร์
รู้ดีว่าฉันต้องการที่จะกลับไปเป็นหลัก

618
00:28:44,180 --> 00:28:46,760
และเสร็จสิ้นการดำเนินการฟังก์ชั่นหลัก

619
00:28:46,760 --> 00:28:51,960
ดังนั้นนี่คืออันตรายในขณะนี้เพราะถ้า
ประเภทของผู้ใช้ในดีกว่าสวัสดี

620
00:28:51,960 --> 00:28:57,030
ดังกล่าวว่าการป้อนข้อมูลของผู้ใช้ clobbers
หรือเขียนทับส่วนที่เป็นสีแดง

621
00:28:57,030 --> 00:28:59,820
ถ้ามีเหตุผลของคอมพิวเตอร์
เพียงแค่จะสุ่มสี่สุ่มห้าถือว่า

622
00:28:59,820 --> 00:29:03,830
ว่าไบต์ในชิ้นที่มีสีแดง
ที่อยู่ที่มันควรจะกลับมา

623
00:29:03,830 --> 00:29:09,020
สิ่งที่ถ้าฝ่ายตรงข้ามจะฉลาดพอหรือ
โชคดีพอที่จะทำให้ลำดับของไบต์

624
00:29:09,020 --> 00:29:13,450
มีที่มีลักษณะเช่นที่อยู่,
แต่มันเป็นเรื่องที่อยู่ของรหัส

625
00:29:13,450 --> 00:29:18,730
ที่เขาหรือเธอต้องการคอมพิวเตอร์
ในการดำเนินการแทนการหลัก?

626
00:29:18,730 --> 00:29:21,670
>> ในคำอื่น ๆ ถ้าสิ่งที่เป็น
ผู้ใช้จะพิมพ์ที่พรอมต์,

627
00:29:21,670 --> 00:29:23,850
ไม่ได้เป็นเพียงแค่สิ่งที่
ไม่มีอันตรายเช่นสวัสดี

628
00:29:23,850 --> 00:29:28,210
แต่มันเป็นเรื่องจริงรหัสที่เทียบเท่า
จะลบไฟล์ทั้งหมดของผู้ใช้นี้หรือไม่?

629
00:29:28,210 --> 00:29:30,060
หรือส่งอีเมลรหัสผ่านของพวกเขากับผมหรือเปล่า

630
00:29:30,060 --> 00:29:31,940
หรือเริ่มต้นการเข้าสู่ระบบของพวกเขา
การกดแป้นพิมพ์ใช่มั้ย?

631
00:29:31,940 --> 00:29:34,920
มีวิธีขอกำหนดวันนี้
ว่าพวกเขาสามารถพิมพ์ไม่ได้เป็นเพียงทักทาย

632
00:29:34,920 --> 00:29:36,711
โลกหรือชื่อของพวกเขา
พวกเขาสามารถเป็นหลัก

633
00:29:36,711 --> 00:29:39,570
รหัสผ่านในศูนย์และ
คนที่ใช้คอมพิวเตอร์

634
00:29:39,570 --> 00:29:43,450
ความผิดพลาดทั้งรหัสและที่อยู่

635
00:29:43,450 --> 00:29:48,950
ดังนั้นแม้จะค่อนข้างเป็นนามธรรมถ้า
ผู้ใช้พิมพ์ในรหัสขัดแย้งพอ

636
00:29:48,950 --> 00:29:52,330
ว่าเราจะคุยที่นี่
A. คือการโจมตีฝ่ายตรงข้ามหรือ

637
00:29:52,330 --> 00:29:53,140
สิ่งที่ไม่ดีดังนั้นเพียงแค่

638
00:29:53,140 --> 00:29:55,306
เราไม่ได้ดูแลเกี่ยวกับ
ตัวเลขหรือค่าศูนย์หรือคน

639
00:29:55,306 --> 00:29:59,470
วันนี้เช่นที่คุณจบลง
เขียนทับส่วนที่เป็นสีแดง

640
00:29:59,470 --> 00:30:01,580
แจ้งให้ทราบลำดับของไบต์ที่

641
00:30:01,580 --> 00:30:05,020
O 835 C ศูนย์แปดศูนย์

642
00:30:05,020 --> 00:30:08,960
และในขณะนี้เป็นบทความวิกิพีเดียที่นี่
ได้เสนอถ้าคุณตอนนี้จะเริ่มต้น

643
00:30:08,960 --> 00:30:12,460
การติดฉลากไบต์ในของเครื่องคอมพิวเตอร์ของคุณ
หน่วยความจำสิ่งที่บทความวิกิพีเดีย

644
00:30:12,460 --> 00:30:19,060
เสนอคือสิ่งที่ถ้าที่อยู่
ที่ด้านบนซ้ายไบต์ 80 C 0 3508

645
00:30:19,060 --> 00:30:22,200
>> ในคำอื่น ๆ ถ้าเป็นคนเลว
ฉลาดพอที่มีรหัสของเขาหรือเธอ

646
00:30:22,200 --> 00:30:26,650
ที่จริงการใส่หมายเลขที่นี่ว่า
ตรงไปยังที่อยู่ของรหัส

647
00:30:26,650 --> 00:30:29,180
เขาหรือเธอฉีด
ลงในคอมพิวเตอร์ของคุณ

648
00:30:29,180 --> 00:30:31,050
สามารถหลอกลวงคอมพิวเตอร์
ในการทำอะไร

649
00:30:31,050 --> 00:30:34,140
การลบไฟล์ที่ส่งอีเมล
สิ่งที่การดมกลิ่นการจราจรของคุณ

650
00:30:34,140 --> 00:30:36,710
สิ่งที่อาจจะเป็นตัวอักษร
ฉีดเข้าไปในคอมพิวเตอร์

651
00:30:36,710 --> 00:30:39,220
และเพื่อให้หน่วยความจำล้น
การโจมตีที่หลักของ

652
00:30:39,220 --> 00:30:43,530
เป็นเพียงโง่โง่
ที่สำคัญของอาร์เรย์ที่

653
00:30:43,530 --> 00:30:45,840
ไม่ได้มีการตรวจสอบขอบเขตของมัน

654
00:30:45,840 --> 00:30:48,850
และนี่คือสิ่งที่เป็นอันตรายสุด
และพร้อมที่มีประสิทธิภาพสุด

655
00:30:48,850 --> 00:30:52,560
ใน C คือการที่เราไม่แน่นอนมี
การเข้าถึงไปยังที่ใดในหน่วยความจำ

656
00:30:52,560 --> 00:30:55,320
มันขึ้นอยู่กับเราโปรแกรมเมอร์,
ที่เขียนรหัสเดิม

657
00:30:55,320 --> 00:30:59,330
เพื่อตรวจสอบความยาวของสาปใด ๆ
อาร์เรย์ที่เรากำลังจัดการกับ

658
00:30:59,330 --> 00:31:00,750
ดังนั้นเพื่อให้มีความชัดเจนสิ่งที่แก้ไขได้หรือไม่?

659
00:31:00,750 --> 00:31:03,190
ถ้าเราย้อนกลับไปนี้
รหัสผมไม่ควรเพียง

660
00:31:03,190 --> 00:31:08,000
เปลี่ยนความยาวของแถบสิ่งที่
อื่นที่ฉันควรจะได้รับการตรวจสอบ?

661
00:31:08,000 --> 00:31:10,620
อะไรที่ฉันควรจะทำเพื่อ
ป้องกันการโจมตีครั้งนี้อย่างสิ้นเชิง?

662
00:31:10,620 --> 00:31:14,110
ฉันไม่ต้องการที่จะเพียงแค่พูดสุ่มสี่สุ่มห้า
ที่คุณควรคัดลอกไบต์เป็นจำนวนมาก

663
00:31:14,110 --> 00:31:16,140
เช่นเดียวกับความยาวของบาร์

664
00:31:16,140 --> 00:31:18,910
ผมอยากจะบอกให้คัดลอกเป็น
จำนวนไบต์เป็นอยู่ในบาร์

665
00:31:18,910 --> 00:31:24,090
ขึ้นไปที่ได้รับการจัดสรร
หน่วยความจำหรือ 12 ที่สุด

666
00:31:24,090 --> 00:31:27,450
ดังนั้นผมจึงต้องชนิดของถ้าเงื่อนไขบางอย่าง
ที่ไม่ตรวจสอบความยาวของบาร์

667
00:31:27,450 --> 00:31:32,800
แต่ถ้ามันเกินกว่า 12 เรารหัสยากเพียง
12 เป็นระยะทางเป็นไปได้สูงสุด

668
00:31:32,800 --> 00:31:35,910
มิฉะนั้นบัฟเฟอร์ที่เรียกว่า
โจมตีล้นสามารถเกิดขึ้นได้

669
00:31:35,910 --> 00:31:38,451
ที่ด้านล่างของภาพนิ่งเหล่านั้น
ถ้าคุณอยากรู้อยากเห็นในการอ่านมากขึ้น

670
00:31:38,451 --> 00:31:41,200
เป็นบทความเดิมที่เกิดขึ้นจริง
ถ้าคุณต้องการที่จะดู

671
00:31:41,200 --> 00:31:44,550
>> แต่ตอนนี้ในหมู่ราคา
การชำระเงินที่นี่เป็นความไร้ประสิทธิภาพ

672
00:31:44,550 --> 00:31:46,680
เพื่อให้เป็นที่รวดเร็ว
ดูในระดับต่ำในสิ่งที่

673
00:31:46,680 --> 00:31:49,709
ปัญหาจะเกิดขึ้นตอนนี้ที่เรา
มีการเข้าถึงหน่วยความจำของคอมพิวเตอร์

674
00:31:49,709 --> 00:31:51,750
แต่ปัญหาที่เราอีก
แล้วสะดุดในวันจันทร์

675
00:31:51,750 --> 00:31:53,800
เป็นเพียงขาดประสิทธิภาพ
ของรายการที่เชื่อมโยง

676
00:31:53,800 --> 00:31:56,019
เราจะกลับไปที่เส้นเวลา

677
00:31:56,019 --> 00:31:57,560
เราไม่ได้มีอาร์เรย์ที่ต่อเนื่องกัน

678
00:31:57,560 --> 00:31:58,980
เราไม่ได้มีการเข้าถึงแบบสุ่ม

679
00:31:58,980 --> 00:32:00,710
เราไม่สามารถใช้เครื่องหมายวงเล็บเหลี่ยม

680
00:32:00,710 --> 00:32:04,590
แท้จริงเราต้องใช้ห่วงในขณะที่
เช่นเดียวกับที่ผมเขียนช่วงเวลาที่ผ่านมา

681
00:32:04,590 --> 00:32:09,740
แต่ในวันจันทร์ที่เราอ้างว่าเราสามารถทำได้
คืบคลานกลับเข้ามาในดินแดนของประสิทธิภาพ

682
00:32:09,740 --> 00:32:13,040
ประสบความสำเร็จในสิ่งที่
ลอการิทึมอาจจะดีที่สุดหรือยัง

683
00:32:13,040 --> 00:32:16,120
แม้กระทั่งสิ่งที่
ที่เรียกว่าเวลาคง

684
00:32:16,120 --> 00:32:19,840
ดังนั้นวิธีที่เราสามารถทำเช่นนั้นโดยใช้ใหม่ ๆ เหล่านี้
เครื่องมือที่อยู่เหล่านี้ตัวชี้เหล่านี้

685
00:32:19,840 --> 00:32:22,210
และเกลียวสิ่งที่เราเอง?

686
00:32:22,210 --> 00:32:23,960
ดีคิดว่า
ที่นี่เหล่านี้เป็นพวง

687
00:32:23,960 --> 00:32:27,170
ของตัวเลขที่เราต้องการที่จะเก็บใน
โครงสร้างข้อมูลและการค้นหาได้อย่างมีประสิทธิภาพ

688
00:32:27,170 --> 00:32:30,960
เราอย่างสามารถย้อนกลับไปในสัปดาห์
สองโยนเหล่านี้ลงในอาร์เรย์

689
00:32:30,960 --> 00:32:33,150
และการค้นหาโดยใช้การค้นหาแบบไบนารี

690
00:32:33,150 --> 00:32:34,040
แบ่งและพิชิต

691
00:32:34,040 --> 00:32:37,720
และในความเป็นจริงที่คุณเขียน
การค้นหาแบบไบนารีใน PSET3,

692
00:32:37,720 --> 00:32:40,100
ที่คุณนำมาใช้โปรแกรมค้นหา

693
00:32:40,100 --> 00:32:40,890
แต่คุณรู้ว่าสิ่งที่

694
00:32:40,890 --> 00:32:45,060
มีชนิดของมากขึ้น
วิธีที่ฉลาดในการดำเนินการนี​​้

695
00:32:45,060 --> 00:32:47,390
มันเป็นเรื่องเล็ก ๆ น้อย ๆ
ที่มีความซับซ้อนและมันอาจจะ

696
00:32:47,390 --> 00:32:50,830
ช่วยให้เราสามารถดูว่าทำไมไบนารี
การค้นหาเป็นไปอย่างรวดเร็วยิ่งขึ้น

697
00:32:50,830 --> 00:32:52,980
ก่อนขอแนะนำ
ความคิดของต้นไม้

698
00:32:52,980 --> 00:32:54,730
ซึ่งแม้ว่าใน
ความเป็นจริงชนิดของต้นไม้

699
00:32:54,730 --> 00:32:57,730
เติบโตเช่นนี้ในโลกของคอมพิวเตอร์
วิทยาศาสตร์พวกเขาชนิดของการเติบโตที่ลดลง

700
00:32:57,730 --> 00:33:00,830
เหมือนต้นไม้ครอบครัวที่คุณมี
ปู่ย่าตายายของคุณหรือปู่ย่าตายายที่ดี

701
00:33:00,830 --> 00:33:04,580
หรือ whatnot ที่ด้านบนและพระสังฆราช
ปูชนียบุคคลของครอบครัวเพียงหนึ่ง

702
00:33:04,580 --> 00:33:07,930
รากที่เรียกว่าโหนดด้านล่าง
ที่เป็นบุตรของตน

703
00:33:07,930 --> 00:33:11,442
ด้านล่างซึ่งเป็นลูกของตนหรือ
ลูกหลานมากขึ้นโดยทั่วไป

704
00:33:11,442 --> 00:33:13,400
และทุกคนที่แขวนปิด
ด้านล่างของครอบครัว

705
00:33:13,400 --> 00:33:16,070
ต้นไม้นอกจากเป็น
ที่อายุน้อยที่สุดในครอบครัว

706
00:33:16,070 --> 00:33:19,520
ยังสามารถเป็นทั่วไป
ที่เรียกว่าใบของต้นไม้

707
00:33:19,520 --> 00:33:21,800
>> ดังนั้นนี้เป็นเพียงพวง
คำพูดและคำจำกัดความ

708
00:33:21,800 --> 00:33:25,790
สำหรับสิ่งที่เรียกว่าต้นไม้ในคอมพิวเตอร์
วิทยาศาสตร์เหมือนต้นไม้ครอบครัว

709
00:33:25,790 --> 00:33:28,770
แต่มีสาขานักเล่น
ของต้นไม้ซึ่งหนึ่งในนั้น

710
00:33:28,770 --> 00:33:30,780
จะเรียกว่าเป็นต้นไม้ค้นหาแบบทวิภาค

711
00:33:30,780 --> 00:33:34,380
และคุณสามารถชนิดของการหยอกล้อ
นอกเหนือสิ่งสิ่งนี้ไม่

712
00:33:34,380 --> 00:33:37,180
ดีก็ไบนารีในสิ่งที่เหมาะสมหรือไม่

713
00:33:37,180 --> 00:33:41,455
ไบนารีมาจากไหนนี่?

714
00:33:41,455 --> 00:33:41,955
ขออภัย?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
มันไม่มากหรือ

717
00:33:47,210 --> 00:33:52,000
มันขึ้นว่าแต่ละโหนดมีใคร
มากกว่าเด็กสองคนที่เราเห็นที่นี่

718
00:33:52,000 --> 00:33:54,990
โดยทั่วไป tree-- และ
พ่อแม่และปู่ย่าตายายของคุณ

719
00:33:54,990 --> 00:33:57,640
จะมีเด็ก ๆ จำนวนมากหรือ
หลานที่พวกเขาต้องการจริง

720
00:33:57,640 --> 00:34:00,820
และอื่น ๆ เช่นมีเรามีสาม
เด็กออกโหนดมือที่ถูกต้อง

721
00:34:00,820 --> 00:34:05,480
แต่ในต้นไม้ไบนารีโหนดมี
ศูนย์หนึ่งหรือสองเด็กที่สุด

722
00:34:05,480 --> 00:34:08,496
และที่เป็นสถานที่ให้บริการที่ดี
เพราะถ้ามันปกคลุมด้วยสอง

723
00:34:08,496 --> 00:34:10,620
เราจะสามารถที่จะ
ได้รับการเข้าสู่ระบบฐานเล็ก ๆ น้อย ๆ สอง

724
00:34:10,620 --> 00:34:11,975
การกระทำที่เกิดขึ้นที่นี่ในที่สุด

725
00:34:11,975 --> 00:34:13,350
ดังนั้นเราจึงมีบางสิ่งบางอย่างเกี่ยวกับลอการิทึม

726
00:34:13,350 --> 00:34:14,558
แต่เพิ่มเติมว่าในช่วงเวลาที่

727
00:34:14,558 --> 00:34:19,810
ค้นหาต้นไม้หมายความว่าตัวเลข
จัดเช่นว่าเด็กซ้าย

728
00:34:19,810 --> 00:34:22,429
ค่ามากกว่าราก

729
00:34:22,429 --> 00:34:26,010
และสิทธิของเด็กคือ
มีขนาดใหญ่กว่าราก

730
00:34:26,010 --> 00:34:29,290
ในคำอื่น ๆ ถ้าคุณใช้ใด ๆ ของ
โหนดวงกลมในภาพนี้

731
00:34:29,290 --> 00:34:31,840
และมองไปที่ด้านซ้ายของ
เด็กและเด็กที่เหมาะสมของตน

732
00:34:31,840 --> 00:34:34,739
ครั้งแรกที่ควรจะน้อยกว่า
ที่สองควรมากกว่า

733
00:34:34,739 --> 00:34:36,159
ดังนั้นสติกา 55

734
00:34:36,159 --> 00:34:37,780
มันเป็นเด็กซ้าย 33

735
00:34:37,780 --> 00:34:38,620
มันน้อยกว่า

736
00:34:38,620 --> 00:34:40,929
55 เด็กที่เหมาะสมคือ 77

737
00:34:40,929 --> 00:34:41,783
มันเป็นเรื่องที่ยิ่งใหญ่กว่า

738
00:34:41,783 --> 00:34:43,199
และนั่นคือคำนิยาม recursive

739
00:34:43,199 --> 00:34:46,480
เราสามารถตรวจสอบทุกหนึ่งในบรรดา
โหนดและรูปแบบเดียวกันจะถือ

740
00:34:46,480 --> 00:34:49,389
>> ดังนั้นสิ่งที่ดีใน
ต้นไม้ค้นหาแบบทวิภาคเป็น

741
00:34:49,389 --> 00:34:52,204
ว่าเราสามารถใช้มัน
กับ struct เพียงเช่นนี้

742
00:34:52,204 --> 00:34:54,620
และแม้ว่าเรากำลังขว้างปา
จำนวนมากของโครงสร้างที่ของคุณ

743
00:34:54,620 --> 00:34:56,560
พวกเขากำลังค่อนข้าง
ที่ใช้งานง่ายในขณะนี้หวังว่า

744
00:34:56,560 --> 00:35:00,570
ไวยากรณ์ยังคงเป็นความลับเพื่อตรวจสอบว่า
แต่เนื้อหาของโหนดในนี้

745
00:35:00,570 --> 00:35:02,786
context-- และเราให้
โดยใช้โหนดคำ

746
00:35:02,786 --> 00:35:04,910
ไม่ว่าจะเป็นรูปสี่เหลี่ยมผืนผ้า
บนหน้าจอหรือวงกลม

747
00:35:04,910 --> 00:35:08,970
มันเป็นเพียงบางส่วนภาชนะทั่วไป
ในกรณีนี้ของต้นไม้เช่นหนึ่ง

748
00:35:08,970 --> 00:35:11,780
เราเห็นเราต้องเป็นจำนวนเต็ม
ในแต่ละโหนด

749
00:35:11,780 --> 00:35:15,460
แล้วฉันต้องสองตัวชี้ชี้
เพื่อให้เด็กซ้ายและเด็กที่ถูกต้อง

750
00:35:15,460 --> 00:35:16,590
ตามลำดับ

751
00:35:16,590 --> 00:35:20,730
นั่นคือวิธีการที่เราอาจจะ
การดำเนินการว่าใน struct

752
00:35:20,730 --> 00:35:22,315
และวิธีการที่ผมอาจจะใช้มันในรหัส?

753
00:35:22,315 --> 00:35:26,730
ดีขอใช้เวลาที่รวดเร็ว
ดูตัวอย่างเล็ก ๆ นี้

754
00:35:26,730 --> 00:35:29,820
มันไม่ได้ทำงาน แต่ฉันได้
คัดลอกและวางโครงสร้างที่

755
00:35:29,820 --> 00:35:33,510
และถ้าฟังก์ชั่นของฉันสำหรับไบนารี
ค้นหาต้นไม้ที่เรียกว่าการค้นหา

756
00:35:33,510 --> 00:35:36,980
และนี่จะใช้เวลาสองข้อโต้แย้ง
จำนวนเต็ม n และตัวชี้

757
00:35:36,980 --> 00:35:41,400
ไปยังโหนดเพื่อชี้ไปยังต้นไม้
หรือชี้ไปยังรากของต้นไม้ที่

758
00:35:41,400 --> 00:35:43,482
ฉันจะไปเกี่ยวกับการค้นหาไม่มี?

759
00:35:43,482 --> 00:35:45,440
ดีแรกเพราะฉัน
การจัดการกับตัวชี้

760
00:35:45,440 --> 00:35:46,750
ฉันจะทำกาสติ

761
00:35:46,750 --> 00:35:54,279
ถ้าเท่ากับต้นไม้เท่ากับโมฆะคือไม่มี
ในต้นไม้ต้นนี้หรือไม่ในต้นไม้นี้หรือไม่?

762
00:35:54,279 --> 00:35:55,070
เป็นไปไม่ได้ใช่มั้ย?

763
00:35:55,070 --> 00:35:56,870
ถ้าฉันที่ผ่านมาเป็นโมฆะ
ไม่มีอะไรที่มี

764
00:35:56,870 --> 00:35:59,230
ฉันอาจจะดีแค่
สุ่มสี่สุ่มห้าพูดกลับเท็จ

765
00:35:59,230 --> 00:36:04,050
ถ้าคุณให้ฉันไม่มีอะไรผมก็ไม่สามารถ
ค้นหาหมายเลขเอ็นใด ๆ ดังนั้นสิ่งที่คนอื่นอาจจะฉัน

766
00:36:04,050 --> 00:36:04,750
การตรวจสอบตอนนี้หรือไม่

767
00:36:04,750 --> 00:36:12,830
ฉันจะบอกว่าดีอื่นถ้า N คือ
น้อยกว่าสิ่งที่อยู่ในโหนดต้นไม้

768
00:36:12,830 --> 00:36:16,300
ที่ฉันได้รับการส่งมอบมูลค่าที่ยังไม่มี

769
00:36:16,300 --> 00:36:20,270
ในคำอื่น ๆ ถ้าจำนวนฉัน
มองหา N, น้อยกว่าโหนด

770
00:36:20,270 --> 00:36:21,340
ที่ผมกำลังมองหาที่

771
00:36:21,340 --> 00:36:23,190
และโหนดฉันกำลังมองหา
ที่เรียกว่าต้นไม้

772
00:36:23,190 --> 00:36:26,370
และจำได้จากตัวอย่างก่อนหน้านี้
ที่จะได้รับค่าในตัวชี้

773
00:36:26,370 --> 00:36:28,310
ผมใช้สัญกรณ์ลูกศร

774
00:36:28,310 --> 00:36:35,960
ดังนั้นหากยังไม่มีน้อยกว่าลูกศรต้นไม้
N, ฉันต้องการที่จะไปแนวคิดซ้าย

775
00:36:35,960 --> 00:36:38,590
ฉันจะเหลือการค้นหาด่วนอย่างไร

776
00:36:38,590 --> 00:36:41,560
ต้องมีความชัดเจนว่านี่คือ
ภาพในคำถาม

777
00:36:41,560 --> 00:36:44,612
และฉันได้รับการส่งผ่านที่สูงสุด
ลูกศรที่ชี้ลง

778
00:36:44,612 --> 00:36:45,570
นั่นเป็นตัวชี้ต้นไม้ของฉัน

779
00:36:45,570 --> 00:36:48,060
ผมชี้ไปที่รากของต้นไม้

780
00:36:48,060 --> 00:36:52,100
และฉันกำลังมองพูดสำหรับ
หมายเลข 44, พล

781
00:36:52,100 --> 00:36:55,300
44 น้อยกว่าหรือ
มากกว่า 55 เห็นได้ชัด?

782
00:36:55,300 --> 00:36:56,360
ดังนั้นจึงเป็นที่น้อยกว่า

783
00:36:56,360 --> 00:36:58,760
และเพื่อให้สภาพนี้ถ้านำไปใช้

784
00:36:58,760 --> 00:37:03,981
ดังนั้นแนวคิดสิ่งที่ฉันต้องการ
ค้นหาต่อไปถ้าฉันกำลังมองหา 44?

785
00:37:03,981 --> 00:37:04,480
ใช่?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> ว่าผมต้องการที่จะ
ค้นหาเด็กด้านซ้าย

788
00:37:11,100 --> 00:37:12,789
หรือซ้ายย่อยต้นไม้ของภาพนี้

789
00:37:12,789 --> 00:37:14,830
และในความเป็นจริงให้ฉันผ่าน
ภาพที่ลงที่นี่

790
00:37:14,830 --> 00:37:17,770
เพียงช่วงเวลาตั้งแต่
ฉันไม่สามารถเกานี้ออก

791
00:37:17,770 --> 00:37:21,150
ถ้าฉันเริ่มต้นที่นี่ที่ 55 และ
ฉันรู้ว่าค่า 44

792
00:37:21,150 --> 00:37:23,180
ฉันกำลังมองหาคือการ
ด้านซ้ายเป็นชนิด

793
00:37:23,180 --> 00:37:26,010
เช่นฉีกสมุดโทรศัพท์ใน
ครึ่งหนึ่งหรือฉีกขาดต้นไม้ในช่วงครึ่งปี

794
00:37:26,010 --> 00:37:29,660
ฉันไม่ต้องดูแลเกี่ยวกับ
ทั้งหมดนี้ครึ่งหนึ่งของต้นไม้

795
00:37:29,660 --> 00:37:33,270
และยังอยากรู้อยากเห็นในแง่ของ
โครงสร้างสิ่งนี้มากกว่าที่นี่ที่

796
00:37:33,270 --> 00:37:36,682
เริ่มต้นด้วย 33 นั้นเอง
เป็นต้นไม้ค้นหาแบบทวิภาค

797
00:37:36,682 --> 00:37:39,890
ผมบอกว่าคำว่า recursive ก่อนเพราะ
แท้จริงนี้คือโครงสร้างข้อมูลที่

798
00:37:39,890 --> 00:37:41,707
โดยความหมายคือ recursive

799
00:37:41,707 --> 00:37:44,540
คุณอาจมีต้นไม้ที่นี้
ใหญ่ แต่ทุกคนของเด็ก

800
00:37:44,540 --> 00:37:46,870
แสดงให้เห็นถึงต้นไม้ที่มีขนาดเล็กเพียงเล็ก ๆ น้อย ๆ

801
00:37:46,870 --> 00:37:50,910
แทนของมันถูกคุณปู่
หรือยายตอนนี้ก็เพียงแค่แม่

802
00:37:50,910 --> 00:37:54,300
or-- ฉันไม่สามารถ say-- แม่ไม่ได้
หรือพ่อที่จะแปลก

803
00:37:54,300 --> 00:37:59,000
แต่เด็กทั้งสองมี
จะเป็นเหมือนพี่ชายและน้อง

804
00:37:59,000 --> 00:38:01,120
รุ่นใหม่ของต้นไม้ครอบครัว

805
00:38:01,120 --> 00:38:02,900
แต่การก่อสร้างก็เป็นความคิดเดียวกัน

806
00:38:02,900 --> 00:38:06,790
และปรากฎฉันมีฟังก์ชั่น
ที่ฉันสามารถค้นหาการค้นหาแบบไบนารี

807
00:38:06,790 --> 00:38:07,290
ต้นไม้

808
00:38:07,290 --> 00:38:08,680
มันถูกเรียกว่าการค้นหา

809
00:38:08,680 --> 00:38:17,870
ฉันจะค้นหาไม่มีลูกศรซ้ายต้นไม้
อื่นถ้ายังไม่มีข้อความที่มีค่ามากกว่าค่า

810
00:38:17,870 --> 00:38:18,870
ว่าฉันในขณะนี้ที่

811
00:38:18,870 --> 00:38:20,800
55 ในเรื่องช่วงเวลาที่ผ่านมา

812
00:38:20,800 --> 00:38:23,780
ฉันมีฟังก์ชั่นที่เรียกว่า
ค้นหาที่ฉันสามารถทำได้เพียงแค่

813
00:38:23,780 --> 00:38:29,660
ไม่มีข้อความผ่านนี้และค้นหาซ้ำ
ย่อยต้นไม้และการกลับมาเพียง

814
00:38:29,660 --> 00:38:30,620
สิ่งที่ว่าคำตอบ

815
00:38:30,620 --> 00:38:33,530
อื่น ๆ ที่ฉันได้มีกรณีฐานบางส่วนสุดท้ายที่นี่

816
00:38:33,530 --> 00:38:35,310
>> กรณีสุดท้ายคืออะไร?

817
00:38:35,310 --> 00:38:36,570
ต้นไม้เป็นทั้ง null

818
00:38:36,570 --> 00:38:39,980
ค่าฉันทั้งมองหาคือ
น้อยกว่าหรือมากกว่า

819
00:38:39,980 --> 00:38:42,610
หรือเท่ากับมัน

820
00:38:42,610 --> 00:38:44,750
และผมสามารถพูดได้เท่ากัน
เท่ากัน แต่ก็มีเหตุผล

821
00:38:44,750 --> 00:38:46,500
เทียบเท่ากับคำพูดว่าคนอื่นที่นี่

822
00:38:46,500 --> 00:38:49,150
ดังนั้นความจริงเป็นวิธีที่ผมพบสิ่งที่

823
00:38:49,150 --> 00:38:51,710
เพื่อหวังว่านี่คือ
ตัวอย่างเช่นแม้จะน่าสนใจมากขึ้น

824
00:38:51,710 --> 00:38:54,900
มากกว่าฟังก์ชั่นซิกโง่
เราได้บรรยายไม่กี่หลัง

825
00:38:54,900 --> 00:38:58,360
ที่มันเป็นเพียงเป็นเรื่องง่ายที่จะใช้ห่วง
การนับตัวเลขทั้งหมดจากหนึ่ง

826
00:38:58,360 --> 00:39:02,390
เอ็นที่นี่มีโครงสร้างข้อมูล
ที่ตัวเองเป็นซ้ำ

827
00:39:02,390 --> 00:39:07,050
กำหนดและวาดซ้ำตอนนี้เรา
มีความสามารถในการแสดงตัวเอง

828
00:39:07,050 --> 00:39:09,780
ในรหัสที่ตัวเองเป็น recursive

829
00:39:09,780 --> 00:39:12,580
ดังนั้นนี่เป็นรหัสเดียวกันแน่นอนที่นี่

830
00:39:12,580 --> 00:39:14,400
>> ดังนั้นสิ่งที่เป็นปัญหาอื่น ๆ ที่เราสามารถแก้ปัญหา?

831
00:39:14,400 --> 00:39:18,160
ดังนั้นขั้นตอนที่รวดเร็วอยู่ห่างจาก
ต้นไม้เพื่อรอสักครู่

832
00:39:18,160 --> 00:39:20,130
นี่คือการพูด, ธงเยอรมัน

833
00:39:20,130 --> 00:39:22,020
และมีอย่างชัดเจน
รูปแบบการตั้งค่าสถานะนี้

834
00:39:22,020 --> 00:39:23,811
และมีจำนวนมาก
ธงในโลกที่

835
00:39:23,811 --> 00:39:27,560
เป็นที่เรียบง่ายเช่นนี้ในแง่
สีและรูปแบบของพวกเขา

836
00:39:27,560 --> 00:39:31,930
แต่สมมติว่านี้จะถูกเก็บไว้เป็น
.GIF หรือ JPEG หรือบิตแมปหรือปิงที่

837
00:39:31,930 --> 00:39:34,240
รูปแบบไฟล์กราฟิกใด ๆ
ที่คุณคุ้นเคย

838
00:39:34,240 --> 00:39:36,460
บางอย่างที่เรา
เล่นกับใน PSET4

839
00:39:36,460 --> 00:39:41,550
นี้ดูเหมือนจะไม่คุ้มค่าที่จะเก็บ
พิกเซลสีดำพิกเซลสีดำพิกเซลสีดำ

840
00:39:41,550 --> 00:39:44,790
จุดจุดจุดทั้งกลุ่ม
พิกเซลสีดำสำหรับ scanline แรก

841
00:39:44,790 --> 00:39:47,430
หรือแถวแล้วทั้งกลุ่ม
เดียวกันแล้วทั้งกลุ่ม

842
00:39:47,430 --> 00:39:49,530
ของเดียวกันแล้ว
ทั้งกลุ่มของพิกเซลสีแดง

843
00:39:49,530 --> 00:39:53,020
พิกเซลสีแดง, สีพิกเซลสีแดงแล้วทั้งหมด
พวงของพิกเซลสีเหลือง, สีเหลือง, ใช่มั้ย?

844
00:39:53,020 --> 00:39:55,050
>> มีการขาดประสิทธิภาพเช่นที่นี่

845
00:39:55,050 --> 00:39:59,040
คุณจะทำอย่างไรสังหรณ์ใจ
บีบอัดธงเยอรมัน

846
00:39:59,040 --> 00:40:01,320
ถ้าการดำเนินการนั้นเป็นไฟล์?

847
00:40:01,320 --> 00:40:04,940
เช่นเดียวกับข้อมูลที่เราไม่สามารถ
รำคาญการจัดเก็บบนดิสก์ในการสั่งซื้อ

848
00:40:04,940 --> 00:40:08,040
เพื่อลดขนาดไฟล์ของเราจากที่ชอบ
เมกะไบต์เพื่อกิโลไบต์ซึ่งเป็นสิ่งที่

849
00:40:08,040 --> 00:40:09,430
เล็ก?

850
00:40:09,430 --> 00:40:13,130
ประเด็นอยู่ซ้ำซ้อน
ที่นี่จะเป็นที่ชัดเจน?

851
00:40:13,130 --> 00:40:13,880
สิ่งที่คุณจะทำอย่างไร

852
00:40:13,880 --> 00:40:14,380
ใช่?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
ที่แน่นอน

855
00:40:21,970 --> 00:40:24,550
ทำไมไม่จำมากกว่า
สีของทุกพิกเซลยี้

856
00:40:24,550 --> 00:40:28,200
เช่นเดียวกับที่คุณทำใน PSET4
กับรูปแบบไฟล์บิตแมป

857
00:40:28,200 --> 00:40:32,060
ทำไมคุณไม่เพียงแค่เป็นตัวแทนของ
คอลัมน์ซ้ายสุดพิกเซลเช่น

858
00:40:32,060 --> 00:40:35,370
พวงของพิกเซลสีดำพวง
ของสีแดง, และพวงของสีเหลือง

859
00:40:35,370 --> 00:40:39,210
แล้วก็อย่างใดเข้ารหัส
ความคิดของการทำซ้ำนี้ 100 ครั้ง

860
00:40:39,210 --> 00:40:41,020
หรือทำซ้ำนี้ 1,000 ครั้ง?

861
00:40:41,020 --> 00:40:43,430
ที่ไหน 100 หรือ 1,000 เป็น
เพียงจำนวนเต็มเพื่อให้คุณ

862
00:40:43,430 --> 00:40:47,290
จะได้รับไปมีเพียงหมายเลขเดียว
แทนการร้อยหรือหลายพัน

863
00:40:47,290 --> 00:40:48,270
พิกเซลที่เพิ่มขึ้นของ

864
00:40:48,270 --> 00:40:50,990
และแน่นอนที่ว่าเรา
สามารถบีบอัดธงเยอรมัน

865
00:40:50,990 --> 00:40:51,490
และ

866
00:40:51,490 --> 00:40:53,470
ตอนนี้สิ่งที่เกี่ยวกับธงฝรั่งเศส?

867
00:40:53,470 --> 00:40:58,930
และน้อยจัดเรียงของบางอย่าง
ออกกำลังกายทางจิตซึ่งธง

868
00:40:58,930 --> 00:41:01,040
สามารถบีบอัดมากขึ้นบนดิสก์?

869
00:41:01,040 --> 00:41:05,720
ธงเยอรมันหรือฝรั่งเศส
ธงถ้าเราใช้วิธีการที่?

870
00:41:05,720 --> 00:41:08,490
ธงเยอรมันเพราะมี
ความผิดพลาดในแนวนอนมากขึ้น

871
00:41:08,490 --> 00:41:12,190
และโดยการออกแบบกราฟิกหลายไฟล์
รูปแบบที่ไม่แน่นอนทำงานเป็นเส้นสแกน

872
00:41:12,190 --> 00:41:12,830
แนวนอน

873
00:41:12,830 --> 00:41:14,674
พวกเขาสามารถทำงานได้
แนวตั้งเป็นมนุษย์เพียง

874
00:41:14,674 --> 00:41:17,090
ตัดสินใจปีมาแล้วที่เราจะ
มักคิดว่าของแถวสิ่ง

875
00:41:17,090 --> 00:41:18,880
โดยแถวแทนคอลัมน์คอลัมน์

876
00:41:18,880 --> 00:41:20,820
ดังนั้นแน่นอนถ้าคุณมี
ไปดูที่ไฟล์

877
00:41:20,820 --> 00:41:24,670
ขนาดของธงเยอรมันและฝรั่งเศส
ธงตราบใดที่ความละเอียด

878
00:41:24,670 --> 00:41:27,530
เดียวกันความกว้างเท่ากัน
และความสูงหนึ่งนี้

879
00:41:27,530 --> 00:41:31,580
ที่นี่เป็นไปได้ที่ใหญ่กว่าเพราะคุณ
ต้องทำซ้ำตัวเองสามครั้ง

880
00:41:31,580 --> 00:41:35,570
คุณจะต้องระบุสีฟ้าซ้ำ
ด้วยตัวคุณเอง, สีขาว, ซ้ำตัวเอง, สีแดง,

881
00:41:35,570 --> 00:41:36,740
ซ้ำตัวเอง

882
00:41:36,740 --> 00:41:39,000
คุณก็ไม่สามารถไปทั้งหมด
วิธีการที่เหมาะสม

883
00:41:39,000 --> 00:41:41,200
และเป็นกันที่จะทำให้
ล้างอัด

884
00:41:41,200 --> 00:41:43,910
เป็นทุกที่ถ้าเหล่านี้เป็น
เฟรมที่สี่จาก video-- คุณ

885
00:41:43,910 --> 00:41:45,890
อาจจะจำได้ว่าภาพยนตร์
หรือวิดีโอโดยทั่วไป

886
00:41:45,890 --> 00:41:47,286
เช่น 29 หรือ 30 เฟรมต่อวินาที

887
00:41:47,286 --> 00:41:50,410
มันเหมือนพลิกหนังสือเล็ก ๆ น้อย ๆ ที่คุณ
เพียงแค่เห็นภาพภาพภาพภาพ

888
00:41:50,410 --> 00:41:54,410
ภาพเร็วสุดเพียงเพื่อให้ดูเหมือนว่า
นักแสดงบนหน้าจอจะย้าย

889
00:41:54,410 --> 00:41:57,130
นี่เป็นแมลงภู่ในเป็น
ด้านบนของช่อดอกไม้

890
00:41:57,130 --> 00:41:59,790
และแม้ว่ามันอาจจะเป็นชนิดของ
ยากที่จะเห็นได้อย่างรวดเร็วก่อน

891
00:41:59,790 --> 00:42:04,020
สิ่งเดียวที่จะย้ายไปอยู่
หนังเรื่องนี้เป็นผึ้ง

892
00:42:04,020 --> 00:42:06,880
>> อะไรคือสิ่งที่เกี่ยวกับการเก็บใบ้
บีบอัดวิดีโอ?

893
00:42:06,880 --> 00:42:11,420
เป็นชนิดของขยะในการจัดเก็บวิดีโอ
เป็นสี่ภาพที่เหมือนกันเกือบ

894
00:42:11,420 --> 00:42:13,670
แตกต่างกันเฉพาะเท่าที่ผึ​​้งเป็น

895
00:42:13,670 --> 00:42:16,280
คุณสามารถโยนไปมากที่สุด
ของข้อมูลที่

896
00:42:16,280 --> 00:42:20,190
และจำไว้เท่านั้นเช่น
เฟรมแรกและกรอบที่ผ่านมา

897
00:42:20,190 --> 00:42:22,180
เฟรมที่สำคัญถ้าคุณได้
เคยได้ยินคำว่า

898
00:42:22,180 --> 00:42:24,337
และเพียงแค่เก็บใน
กลางที่ผึ​​้งเป็น

899
00:42:24,337 --> 00:42:26,170
และคุณจะได้ไม่ต้อง
เก็บทุกสีชมพู

900
00:42:26,170 --> 00:42:28,330
และสีฟ้าและ
ค่าสีเขียวเช่นกัน

901
00:42:28,330 --> 00:42:31,200
ดังนั้นนี้เป็นเพียงบอกว่า
การบีบอัดมีอยู่ทั่วไป

902
00:42:31,200 --> 00:42:34,900
มันเป็นเทคนิคที่เรามักจะใช้
หรือใช้สำหรับการรับวันนี้

903
00:42:34,900 --> 00:42:38,750
>> แต่คุณจะบีบอัดข้อความ?

904
00:42:38,750 --> 00:42:40,450
คุณไปเกี่ยวกับการบีบอัดข้อความได้อย่างไร

905
00:42:40,450 --> 00:42:45,410
ดีของแต่ละตัวละครใน
ascii เป็นหนึ่งไบต์หรือแปดบิต

906
00:42:45,410 --> 00:42:47,360
และนั่นคือชนิดของใบ้ใช่มั้ย?

907
00:42:47,360 --> 00:42:51,160
เพราะคุณอาจจะเป็นชนิด A
และ E และ I และ O และ U มาก

908
00:42:51,160 --> 00:42:55,270
บ่อยกว่าเช่น W หรือ Q หรือซี
ขึ้นอยู่กับภาษาที่

909
00:42:55,270 --> 00:42:56,610
คุณกำลังเขียนอย่างแน่นอน

910
00:42:56,610 --> 00:42:59,600
ดังนั้นทำไมเราใช้
แปดบิตสำหรับจดหมายทุก

911
00:42:59,600 --> 00:43:02,040
รวมทั้งน้อย
ตัวอักษรที่นิยมใช่มั้ย?

912
00:43:02,040 --> 00:43:05,300
ทำไมไม่ใช้บิตน้อยลงสำหรับ
ตัวอักษรที่นิยมสุด

913
00:43:05,300 --> 00:43:07,760
เช่น E, สิ่งที่คุณคิดว่า
ครั้งแรกในวงล้อแห่งโชคลาภ

914
00:43:07,760 --> 00:43:10,450
และใช้บิตม​​ากขึ้นสำหรับ
ตัวอักษรที่ได้รับความนิยมน้อยลงหรือไม่

915
00:43:10,450 --> 00:43:10,950
ทำไม?

916
00:43:10,950 --> 00:43:13,130
เพราะเรากำลังจะ
ใช้พวกเขาไม่บ่อย

917
00:43:13,130 --> 00:43:15,838
>> ดีก็ปรากฎว่ามีมี
ความพยายามที่รับทำจะทำเช่นนี้

918
00:43:15,838 --> 00:43:18,630
และถ้าคุณจำได้จากเกรด
โรงเรียนหรือโรงเรียนมัธยมรหัสมอร์ส

919
00:43:18,630 --> 00:43:20,400
รหัสมอร์สมีจุด
และรอยขีดข่วนที่สามารถ

920
00:43:20,400 --> 00:43:24,270
ส่งผ่านไปตามสายเป็น
เสียงหรือสัญญาณของการจัดเรียงบาง

921
00:43:24,270 --> 00:43:25,930
แต่รหัสมอร์สเป็นที่สะอาดสุด

922
00:43:25,930 --> 00:43:29,010
เป็นชนิดของระบบดาวคู่ใน
ว่าคุณมีจุดหรือรอยขีดข่วน

923
00:43:29,010 --> 00:43:30,977
แต่ถ้าคุณเห็นเช่นจุดสองจุด

924
00:43:30,977 --> 00:43:33,810
หรือถ้าคุณคิดว่ากลับไปดำเนินการ
ที่ไปเช่นเสียงเตือนเสียงเตือนเสียงเตือน

925
00:43:33,810 --> 00:43:36,760
เสียงเตือนกดปุ่มทริกเกอร์เล็ก ๆ น้อย ๆ
ที่ส่งสัญญาณ

926
00:43:36,760 --> 00:43:40,360
ถ้าคุณผู้รับได้รับสอง
จุดสิ่งที่คุณได้รับข้อความได้?

927
00:43:40,360 --> 00:43:43,490
สมบูรณ์โดยพลการ

928
00:43:43,490 --> 00:43:44,450
>> ผม?

929
00:43:44,450 --> 00:43:45,060
ผม?

930
00:43:45,060 --> 00:43:47,500
หรือสิ่งที่ about-- หรือ I?

931
00:43:47,500 --> 00:43:49,570
บางทีมันอาจจะเป็นเพียงแค่สองขวาอี

932
00:43:49,570 --> 00:43:52,480
จึงมีปัญหานี้
ของ decodability กับมอร์ส

933
00:43:52,480 --> 00:43:54,890
รหัสโดยเว้นแต่
คนที่ส่งข้อความ

934
00:43:54,890 --> 00:43:59,510
จริงหยุดเพื่อให้คุณสามารถเรียงลำดับของ
เห็นหรือได้ยินช่องว่างระหว่างตัวอักษร

935
00:43:59,510 --> 00:44:02,990
มันไม่เพียงพอเพียงเพื่อ
ส่งกระแสของศูนย์และคน,

936
00:44:02,990 --> 00:44:05,610
หรือจุดและขีดกลาง
เพราะมีความคลุมเครือ

937
00:44:05,610 --> 00:44:08,640
E เป็นจุดเดียวดังนั้นหากคุณ
เห็นสองจุดหรือได้ยินสองจุด

938
00:44:08,640 --> 00:44:11,254
บางทีมันอาจจะสอง E หรือบางทีมันอาจจะเป็นหนึ่งในครั้งที่หนึ่ง

939
00:44:11,254 --> 00:44:13,670
ดังนั้นเราจึงจำเป็นต้องมีระบบที่เป็น
เล็ก ๆ น้อย ๆ ที่ฉลาดมากขึ้นกว่าที่

940
00:44:13,670 --> 00:44:16,851
ดังนั้นผู้ชายที่ชื่อปี Huffman
ที่ผ่านมาขึ้นมาตรงนี้

941
00:44:16,851 --> 00:44:18,600
ดังนั้นเราจึงกำลังจะ
ที่จะใช้อย่างรวดเร็ว

942
00:44:18,600 --> 00:44:20,114
ที่วิธีการที่ต้นไม้ใกล้ชิดกับเรื่องนี้

943
00:44:20,114 --> 00:44:22,530
สมมติว่านี่คือบางส่วน
ข้อความโง่คุณต้องการที่จะส่ง

944
00:44:22,530 --> 00:44:26,342
ประกอบด้วยเพียง A, B, C ของ D'และ E ของ
แต่มีจำนวนมากที่มีความซ้ำซ้อนที่นี่

945
00:44:26,342 --> 00:44:27,550
มันไม่ได้หมายความว่าจะเป็นภาษาอังกฤษ

946
00:44:27,550 --> 00:44:28,341
มันไม่ได้เข้ารหัส

947
00:44:28,341 --> 00:44:30,540
มันเป็นเพียงข้อความโง่
มีจำนวนมากของการทำซ้ำ

948
00:44:30,540 --> 00:44:34,010
ดังนั้นถ้าคุณจริงนับออกทั้งหมด
เอบีซีของ D's และ E ของที่นี่

949
00:44:34,010 --> 00:44:34,890
ความถี่

950
00:44:34,890 --> 00:44:37,800
20% ของตัวอักษรที่
เอเอส 45% ของตัวอักษร

951
00:44:37,800 --> 00:44:39,660
เป็น E และสามความถี่อื่น ๆ

952
00:44:39,660 --> 00:44:41,960
เรานับไปอยู่ที่นั่นด้วยตนเอง
และเพียงแค่ไม่คณิตศาสตร์

953
00:44:41,960 --> 00:44:44,579
>> ดังนั้นมันกลับกลายเป็นว่า
Huffman, เวลาที่ผ่านมาบางส่วน

954
00:44:44,579 --> 00:44:46,620
ตระหนักว่าคุณรู้ว่า
สิ่งที่ถ้าผมเริ่มต้นสร้าง

955
00:44:46,620 --> 00:44:51,172
ต้นไม้หรือป่าไม้ของต้นไม้ถ้าคุณจะ
ดังต่อไปนี้ฉันจะทำต่อไปนี้

956
00:44:51,172 --> 00:44:53,880
ฉันจะให้โหนดแต่ละ
ของตัวอักษรที่ฉันดูแลเกี่ยวกับ

957
00:44:53,880 --> 00:44:55,530
และฉันจะเก็บ
ภายในของโหนดที่

958
00:44:55,530 --> 00:44:58,610
ความถี่เป็นจุดลอย
ค่าหรือคุณอาจจะใช้มันยังไม่มีมากเกินไป

959
00:44:58,610 --> 00:45:00,210
แต่เราก็จะใช้ลอยที่นี่

960
00:45:00,210 --> 00:45:03,100
และอัลกอริทึมที่
เขาเสนอคือการที่คุณ

961
00:45:03,100 --> 00:45:07,210
ใช้ป่าโหนดเดียวนี้
ต้นไม้เพื่อต้นไม้สั้นสุด

962
00:45:07,210 --> 00:45:11,920
และคุณจะเริ่มต้นการเชื่อมต่อพวกเขาด้วย
กลุ่มใหม่ผู้ปกครองใหม่ถ้าคุณจะ

963
00:45:11,920 --> 00:45:16,150
และคุณทำเช่นนี้โดยการเลือก
สองความถี่ที่เล็กที่สุดในช่วงเวลาที่

964
00:45:16,150 --> 00:45:18,110
ดังนั้นผมจึงเอา 10% และ 10%

965
00:45:18,110 --> 00:45:19,090
ฉันจะสร้างโหนดใหม่

966
00:45:19,090 --> 00:45:20,910
และที่ผมเรียกว่าโหนดใหม่ 20%

967
00:45:20,910 --> 00:45:22,750
>> ซึ่งสองโหนด I รวมต่อไปหรือไม่

968
00:45:22,750 --> 00:45:23,810
มันเป็นเรื่องเล็ก ๆ น้อย ๆ ที่ไม่ชัดเจน

969
00:45:23,810 --> 00:45:26,643
จึงมีบางกรณีมุม
พิจารณา แต่เพื่อให้สิ่งที่สวย

970
00:45:26,643 --> 00:45:29,300
ฉันจะเลือก 20% -
ตอนนี้ผมไม่สนใจเด็ก

971
00:45:29,300 --> 00:45:33,640
ฉันจะเลือก 20% และ
15% และวาดสองขอบใหม่

972
00:45:33,640 --> 00:45:35,624
และตอนที่สองโหนด
ฉันมีเหตุผลรวม?

973
00:45:35,624 --> 00:45:38,540
ไม่สนใจเด็กทุกคนทุก
หลานเพียงแค่มองไปที่ราก

974
00:45:38,540 --> 00:45:39,070
ตอนนี้

975
00:45:39,070 --> 00:45:42,220
ซึ่งสองโหนดฉันจะผูกกัน?

976
00:45:42,220 --> 00:45:44,530
จุดที่สองและ 0.35

977
00:45:44,530 --> 00:45:45,890
เพื่อให้ฉันวาดสองขอบใหม่

978
00:45:45,890 --> 00:45:47,570
และจากนั้นผมได้มีเพียงคนเดียวที่เหลือ

979
00:45:47,570 --> 00:45:48,650
ดังนั้นนี่คือต้นไม้

980
00:45:48,650 --> 00:45:51,160
และจะได้รับการวาดจงใจ
ที่จะดูชนิดของสวย

981
00:45:51,160 --> 00:45:55,870
แต่สังเกตเห็นว่ามีขอบ
ยังได้รับการติดป้ายชื่อศูนย์และหนึ่ง

982
00:45:55,870 --> 00:45:59,510
ดังนั้นสิ่งที่ขอบด้านซ้ายเป็นศูนย์
โดยพลการ แต่อย่างต่อเนื่อง

983
00:45:59,510 --> 00:46:01,170
ทั้งหมดขอบด้านขวาจะเป็นคน

984
00:46:01,170 --> 00:46:05,070
>> และเพื่อให้สิ่งที่ฮอฟแมนที่นำเสนอมี
ถ้าคุณต้องการที่จะเป็นตัวแทนของ B,

985
00:46:05,070 --> 00:46:10,080
มากกว่าแทนจำนวน 66 เป็น
Ascii ซึ่งเป็นแปดบิตทั้งหมด

986
00:46:10,080 --> 00:46:13,360
คุณรู้ว่าสิ่งที่จัดเก็บเพียง
รูปแบบศูนย์ศูนย์ศูนย์

987
00:46:13,360 --> 00:46:17,030
ศูนย์เนื่องจากว่าเป็นเส้นทาง
จากต้นไม้ของฉันนายต้นไม้ Huffman ของ

988
00:46:17,030 --> 00:46:18,600
ใบจากราก

989
00:46:18,600 --> 00:46:20,970
ถ้าคุณต้องการในการจัดเก็บ
E โดยคมชัดไม่

990
00:46:20,970 --> 00:46:26,290
ส่งแปดบิตที่เป็นตัวแทนของอี
แต่สิ่งที่ส่งรูปแบบของบิต?

991
00:46:26,290 --> 00:46:26,890
หนึ่ง

992
00:46:26,890 --> 00:46:30,410
และสิ่งที่ดีเกี่ยวกับเรื่องนี้คือ
ที่ E เป็นตัวอักษรที่นิยมมากที่สุด

993
00:46:30,410 --> 00:46:32,340
และคุณกำลังใช้
รหัสที่สั้นที่สุดสำหรับมัน

994
00:46:32,340 --> 00:46:34,090
ถัดไปที่นิยมมากที่สุด
ตัวอักษรที่ดูเหมือนว่ามัน

995
00:46:34,090 --> 00:46:37,380
เป็นเอและเพื่อให้วิธีการหลายบิต
เขาเสนอใช้สำหรับที่?

996
00:46:37,380 --> 00:46:38,270
ศูนย์หนึ่ง

997
00:46:38,270 --> 00:46:41,060
>> และเพราะการดำเนินการ
เป็นต้นไม้ต้นนี้สำหรับตอนนี้

998
00:46:41,060 --> 00:46:43,350
กำหนดให้ฉันมี
ความคลุมเครือในขณะที่มอร์สไม่มี

999
00:46:43,350 --> 00:46:46,090
รหัสเพราะทั้งหมดของ
ตัวอักษรที่คุณดูแลเกี่ยวกับ

1000
00:46:46,090 --> 00:46:48,780
อยู่ที่ปลายขอบเหล่านี้

1001
00:46:48,780 --> 00:46:50,580
เพื่อให้เป็นเพียงหนึ่ง
แอพลิเคชันของต้นไม้

1002
00:46:50,580 --> 00:46:52,538
is-- นี้และฉันจะโบก
มือของฉันที่นี้วิธีการที่คุณ

1003
00:46:52,538 --> 00:46:55,570
อาจดำเนินการนี​​้เป็นโครงสร้าง C

1004
00:46:55,570 --> 00:46:58,260
เราก็ต้องรวม
สัญลักษณ์เช่นถ่าน,

1005
00:46:58,260 --> 00:46:59,910
และความถี่ในด้านซ้ายและขวา

1006
00:46:59,910 --> 00:47:02,510
แต่ให้ดูที่สอง
ตัวอย่างสุดท้ายที่คุณจะ

1007
00:47:02,510 --> 00:47:06,070
ได้รับค่อนข้างคุ้นเคยกับหลัง
ศูนย์ในการตอบคำถามปัญหาตั้งห้า

1008
00:47:06,070 --> 00:47:09,210
>> จึงมีโครงสร้างข้อมูล
ที่รู้จักกันเป็นตารางแฮช

1009
00:47:09,210 --> 00:47:12,247
และตารางแฮชเป็นชนิดของ
เย็นในการที่จะมีถัง

1010
00:47:12,247 --> 00:47:14,830
และสมมติว่ามีสี่ถัง
นี่แค่สี่ช่องว่าง

1011
00:47:14,830 --> 00:47:20,830
นี่คือของการ์ด, และนี่คือ
สโมสร, จอบ, สโมสร, เพชร, สโมสร

1012
00:47:20,830 --> 00:47:25,960
เพชรสโมสร, เพชร,
clubs-- ดังนั้นนี้เป็นแบบสุ่ม

1013
00:47:25,960 --> 00:47:30,330
หัวใจ hearts-- ดังนั้นฉัน
bucketizing ทั้งหมดของปัจจัยการผลิตที่นี่

1014
00:47:30,330 --> 00:47:32,430
และตารางแฮชความต้องการ
จะมองไปที่การป้อนข้อมูลของคุณ

1015
00:47:32,430 --> 00:47:34,850
แล้ววางไว้ในบางอย่าง
วางอยู่บนพื้นฐานของสิ่งที่คุณเห็น

1016
00:47:34,850 --> 00:47:35,600
มันเป็นขั้นตอนวิธี

1017
00:47:35,600 --> 00:47:37,980
และผมใช้ซุปเปอร์
อัลกอริทึมภาพอย่างง่าย

1018
00:47:37,980 --> 00:47:40,030
ส่วนที่ยากที่สุดซึ่งเป็น
จดจำสิ่งที่เป็นภาพ

1019
00:47:40,030 --> 00:47:41,590
แล้วมีสี่สิ่งที่รวม

1020
00:47:41,590 --> 00:47:45,440
>> ตอนนี้กองกำลังที่เพิ่มขึ้นซึ่ง
เป็นสิ่งที่ออกแบบโดยเจตนาที่นี่

1021
00:47:45,440 --> 00:47:46,540
แต่อะไรที่ฉันจะทำอย่างไร

1022
00:47:46,540 --> 00:47:49,080
ดังนั้นจริง ๆ แล้วนี่เรามี
พวงของหนังสือสอบโรงเรียนเก่า

1023
00:47:49,080 --> 00:47:51,240
สมมติว่าพวงของ
ชื่อนักเรียนที่นี่

1024
00:47:51,240 --> 00:47:52,570
นี่เป็นตารางแฮชที่ใหญ่กว่าคือ

1025
00:47:52,570 --> 00:47:54,867
แทนที่จะเป็นสี่ถัง
ฉันได้สมมติว่า 26

1026
00:47:54,867 --> 00:47:57,950
และเราไม่ได้ต้องการที่จะไปยืม 26
สิ่งที่มาจากข้างนอก [? Annenberg?] ดังนั้น

1027
00:47:57,950 --> 00:48:00,289
นี่คือห้าที่เป็นตัวแทนของ
ผ่านซีและถ้าฉัน

1028
00:48:00,289 --> 00:48:03,580
เห็นนักเรียนที่มีชื่อขึ้นต้นด้วย A,
ฉันจะใส่การตอบคำถามของเขาหรือเธอมี

1029
00:48:03,580 --> 00:48:08,850
ถ้ามีคนเริ่มต้นด้วยซีที่นั่น
A-- จริงไม่ต้องการที่จะทำเช่นนั้น

1030
00:48:08,850 --> 00:48:10,060
B ไปกว่าที่นี่

1031
00:48:10,060 --> 00:48:13,390
ดังนั้นผมจึงได้มี A และ B และ C และ
ตอนนี้ที่นี่เป็นนักเรียนอีก

1032
00:48:13,390 --> 00:48:16,212
แต่ถ้าตารางแฮชนี้
ดำเนินการกับอาร์เรย์

1033
00:48:16,212 --> 00:48:17,920
ฉันชนิดของเมา
ที่จุดนี้ใช่มั้ย?

1034
00:48:17,920 --> 00:48:19,510
ชนิดของฉันต้องการที่จะนำเรื่องนี้อยู่ที่ไหนสักแห่ง

1035
00:48:19,510 --> 00:48:24,380
>> ดังนั้นหนึ่งวิธีที่ฉันสามารถแก้ปัญหานี้คือทั้งหมด
ที่ถูกต้องคือไม่ว่างไม่ว่าง B, C ไม่ว่าง

1036
00:48:24,380 --> 00:48:28,880
ฉันจะทำให้เขาอยู่ในที่ดีดังนั้น
ครั้งแรกที่ผมสามารถเข้าถึงได้ทันทีแบบสุ่ม

1037
00:48:28,880 --> 00:48:31,064
แต่ละถังสำหรับนักเรียน

1038
00:48:31,064 --> 00:48:33,230
แต่ตอนนี้มันเป็นชนิดของเงินทอง
ลงไปในเชิงเส้นบางสิ่งบางอย่าง

1039
00:48:33,230 --> 00:48:36,750
เพราะถ้าผมต้องการที่จะค้นหาคน
มีชื่อขึ้นต้นด้วยผมตรวจสอบที่นี่

1040
00:48:36,750 --> 00:48:38,854
แต่ถ้านี้ไม่ได้เป็น
นักศึกษาที่ฉันกำลังมองหา

1041
00:48:38,854 --> 00:48:41,520
ชนิดของฉันจะต้องเริ่มต้นการตรวจสอบ
ถังเพราะสิ่งที่ผมทำ

1042
00:48:41,520 --> 00:48:44,530
คือการจัดเรียงของเส้นตรง
ตรวจสอบโครงสร้างข้อมูล

1043
00:48:44,530 --> 00:48:47,710
วิธีที่โง่บอกว่าเพียงแค่มอง
สำหรับการเปิดใช้ได้แรก

1044
00:48:47,710 --> 00:48:51,850
และใส่เป็นแผน B, เพื่อที่จะพูด
หรือวางแผนที่ดีในกรณีนี้ค่า

1045
00:48:51,850 --> 00:48:53,340
ในสถานที่ที่แทน

1046
00:48:53,340 --> 00:48:56,470
นี่เป็นเพียงเพื่อที่ว่าถ้าคุณได้
มี 2​​6 สถานที่และนักเรียนไม่มี

1047
00:48:56,470 --> 00:49:00,600
Q กับชื่อหรือ Z หรือสิ่งที่ต้องการ
ว่าอย่างน้อยคุณใช้พื้นที่

1048
00:49:00,600 --> 00:49:03,140
>> แต่เราได้เห็นแล้ว
โซลูชั่นที่ชาญฉลาดที่นี่ใช่มั้ย?

1049
00:49:03,140 --> 00:49:04,870
คุณจะทำอะไรแทน
ถ้าคุณมีการปะทะกันหรือไม่?

1050
00:49:04,870 --> 00:49:06,670
ถ้าคนสองคนที่มี
ชื่อที่สิ่งที่จะ

1051
00:49:06,670 --> 00:49:09,160
ได้รับอย่างชาญฉลาดหรือมากกว่า
วิธีการแก้ปัญหาที่ใช้งานง่ายกว่าเพียงแค่

1052
00:49:09,160 --> 00:49:12,840
วางที่ดีควรจะเป็น?

1053
00:49:12,840 --> 00:49:14,810
ทำไมฉันจึงไม่เพียงแค่ไป
นอก [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
เช่น malloc โหนดอื่นวางไว้
ที่นี่แล้วใส่ว่านักเรียนที่นี่

1055
00:49:19,960 --> 00:49:22,120
เพื่อที่ฉันเป็นหลักมี
ชนิดของอาร์เรย์

1056
00:49:22,120 --> 00:49:25,590
หรืออาจจะหรูหรามากขึ้นตามที่เรา
เริ่มที่จะเห็นรายการที่เชื่อมโยง

1057
00:49:25,590 --> 00:49:29,520
>> และเพื่อให้ตารางแฮชเป็นโครงสร้าง
ที่จะมีลักษณะเหมือนเพียงแค่นี้

1058
00:49:29,520 --> 00:49:33,900
แต่ชาญฉลาดคุณสิ่งที่เรียกว่า
ผูกมัดที่แยกจากกันโดยตารางแฮช

1059
00:49:33,900 --> 00:49:38,340
ค่อนข้างง่ายเป็นอาร์เรย์แต่ละ
มีองค์ประกอบไม่ได้เป็นตัวเลข

1060
00:49:38,340 --> 00:49:40,470
ตัวเองเป็นรายการที่เชื่อมโยง

1061
00:49:40,470 --> 00:49:45,080
เพื่อที่คุณจะได้รับการเข้าถึงเร็วสุด
การตัดสินใจที่จะสับค่าของคุณไป

1062
00:49:45,080 --> 00:49:48,059
เหมือนตัวอย่างบัตร
ฉันทำตัดสินใจที่รวดเร็วสุด

1063
00:49:48,059 --> 00:49:49,600
หัวใจที่นี่เพชรที่นี่

1064
00:49:49,600 --> 00:49:52,180
เดียวกันที่นี่, A ไปที่นี่
D ที่นี่, B ที่นี่

1065
00:49:52,180 --> 00:49:55,740
ดังนั้นเร็วสุดดูอัพและถ้า
คุณเกิดขึ้นที่จะทำงานเป็นกรณี

1066
00:49:55,740 --> 00:49:59,429
ที่คุณได้มีการชนกันของทั้งสอง
คนที่มีชื่อเดียวกันดีแล้ว

1067
00:49:59,429 --> 00:50:00,970
คุณเพียงแค่เริ่มต้นการเชื่อมโยงเข้าด้วยกัน

1068
00:50:00,970 --> 00:50:03,900
และบางทีคุณอาจให้พวกเขาเรียง
ตัวอักษรอาจจะคุณทำไม่ได้

1069
00:50:03,900 --> 00:50:05,900
แต่อย่างน้อยตอนนี้เรามีชีวิตชีวา

1070
00:50:05,900 --> 00:50:10,250
ดังนั้นในแง่หนึ่งเรามีเร็วสุด
เวลาคงที่และชนิดของเส้นเวลา

1071
00:50:10,250 --> 00:50:14,110
ที่เกี่ยวข้องกับการเชื่อมโยงถ้ารายการเหล่านี้
เริ่มต้นที่จะได้รับเป็นเวลานาน ๆ หน่อย ๆ

1072
00:50:14,110 --> 00:50:16,880
>> ดังนั้นชนิดของโง่นี้
ปีที่ผ่านมาเป็นเรื่องตลก geeky

1073
00:50:16,880 --> 00:50:19,590
ที่ CS50 สับธนบุรี,
เมื่อนักเรียนเช็คอิน

1074
00:50:19,590 --> 00:50:22,040
บาง TF หรือ CA ทุกปี
คิดว่ามันเป็นเรื่องตลกที่จะนำขึ้น

1075
00:50:22,040 --> 00:50:27,772
เข้าสู่ระบบเช่นนี้ซึ่งก็แค่
หมายความว่าชื่อของคุณเริ่มต้นด้วย A,

1076
00:50:27,772 --> 00:50:28,870
ไปทางนี้

1077
00:50:28,870 --> 00:50:31,110
หากชื่อของคุณเริ่มต้น
กับ B ไป this-- ตกลง

1078
00:50:31,110 --> 00:50:33,290
มันตลกหลังจากนั้นอาจอยู่ในภาคการศึกษา

1079
00:50:33,290 --> 00:50:36,420
แต่มีผู้อื่น
วิธีการทำเช่นนี้มากเกินไป

1080
00:50:36,420 --> 00:50:37,410
กลับมาที่

1081
00:50:37,410 --> 00:50:38,600
>> เพื่อให้มีโครงสร้างนี้

1082
00:50:38,600 --> 00:50:40,420
และนี่คือครั้งสุดท้ายของเรา
โครงสร้างสำหรับวันนี้

1083
00:50:40,420 --> 00:50:42,400
ซึ่งเป็นสิ่งที่เรียกว่า Trie

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E ซึ่งด้วยเหตุผลบางอย่างที่เป็นระยะสั้น
สำหรับการเรียก แต่ก็เรียกว่า Trie

1085
00:50:47,140 --> 00:50:51,389
ดังนั้น Trie เป็นที่น่าสนใจอีก
รวมกันของจำนวนมากของความคิดเหล่านี้

1086
00:50:51,389 --> 00:50:52,930
มันเป็นต้นไม้ที่เราเคยเห็นมาก่อน

1087
00:50:52,930 --> 00:50:54,180
มันไม่ได้เป็นต้นไม้ค้นหาแบบทวิภาค

1088
00:50:54,180 --> 00:50:58,410
มันเป็นต้นไม้ที่มีจำนวนของเด็กที่ใด ๆ
แต่แต่ละของเด็กใน Trie ที่

1089
00:50:58,410 --> 00:51:00,090
เป็นอาร์เรย์

1090
00:51:00,090 --> 00:51:04,790
อาร์เรย์ของขนาดบอกว่าอาจจะ 26 หรือ 27
ถ้าคุณต้องการที่จะสนับสนุนชื่อยัติภังค์

1091
00:51:04,790 --> 00:51:06,790
หรือ apostrophes ในชื่อของผู้คน

1092
00:51:06,790 --> 00:51:08,280
>> และเพื่อให้เป็นโครงสร้างข้อมูล

1093
00:51:08,280 --> 00:51:10,290
และถ้าคุณมองจากด้านบน
ไปที่ด้านล่างเช่นถ้าคุณ

1094
00:51:10,290 --> 00:51:13,710
มองไปที่ด้านบนมีโหนด, M, คือ
ชี้ไปที่สิ่งที่ซ้ายสุดมี

1095
00:51:13,710 --> 00:51:17,665
ซึ่งจะแล้ว A, X, W, E, L, แอลนี่คือ
เพียงแค่โครงสร้างข้อมูลที่พล

1096
00:51:17,665 --> 00:51:19,120
มีการจัดเก็บชื่อของผู้คน

1097
00:51:19,120 --> 00:51:25,720
และแมกซ์เวลจะถูกเก็บไว้โดยเพียงแค่ต่อไปนี้
เส้นทางของอาร์เรย์อาร์เรย์อาร์เรย์

1098
00:51:25,720 --> 00:51:30,050
แต่สิ่งที่น่าทึ่งเกี่ยวกับ Trie เป็น
ว่าในขณะที่รายการที่เชื่อมโยงและแม้กระทั่ง

1099
00:51:30,050 --> 00:51:34,520
อาร์เรย์ดีที่สุดที่เราเคยเคยเป็น
เส้นเวลาหรือเวลาลอการิทึมมอง

1100
00:51:34,520 --> 00:51:35,600
คนที่ขึ้น

1101
00:51:35,600 --> 00:51:40,530
ในโครงสร้างข้อมูลของ Trie ถ้า
โครงสร้างข้อมูลของฉันมีชื่ออยู่ในนั้น

1102
00:51:40,530 --> 00:51:43,720
และฉันกำลังมองหาแมกซ์เวลผม
จะไปหาเขาสวยได้อย่างรวดเร็ว

1103
00:51:43,720 --> 00:51:47,910
ฉันเพียงแค่มองหา M-A-X-W-E-L-L หาก
โครงสร้างข้อมูลนี้ตรงกันข้าม

1104
00:51:47,910 --> 00:51:51,830
ถ้า N เป็นล้านถ้ามี
ล้านชื่อในโครงสร้างข้อมูลนี้

1105
00:51:51,830 --> 00:51:57,100
แมกซ์เวลยังคงไปได้
ค้นพบหลังจากนั้นเพียง M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
ขั้นตอน

1107
00:51:58,090 --> 00:52:01,276
และ David-- D-A-V-I-D ขั้นตอน

1108
00:52:01,276 --> 00:52:03,400
ในคำอื่น ๆ โดยการสร้าง
โครงสร้างข้อมูลที่

1109
00:52:03,400 --> 00:52:07,240
มีทั้งหมดของอาร์เรย์เหล่านี้ทั้งหมดที่
ตัวเองสนับสนุนการเข้าถึงแบบสุ่ม

1110
00:52:07,240 --> 00:52:11,090
ฉันจะเริ่มมองขึ้นของผู้คน
ชื่อที่ใช้ระยะเวลาที่เป็น

1111
00:52:11,090 --> 00:52:14,340
ไม่ได้สัดส่วนกับจำนวน
ของสิ่งที่อยู่ในโครงสร้างข้อมูล

1112
00:52:14,340 --> 00:52:16,330
เหมือนล้านชื่อที่มีอยู่

1113
00:52:16,330 --> 00:52:20,135
ปริมาณของเวลาที่ใช้ผมที่จะหา
M-A-X-W-E-L-L ในโครงสร้างข้อมูลนี้

1114
00:52:20,135 --> 00:52:22,260
สัดส่วนไม่ให้
ขนาดของโครงสร้างข้อมูล

1115
00:52:22,260 --> 00:52:25,930
แต่ความยาวของชื่อ

1116
00:52:25,930 --> 00:52:28,440
และแนบเนียน
ชื่อที่เรากำลังมองหา

1117
00:52:28,440 --> 00:52:29,970
ไม่เคยไปจะบ้านาน

1118
00:52:29,970 --> 00:52:32,600
อาจจะมีคนมี 10 ตัวอักษร
ชื่อ 20 ชื่อตัวละคร

1119
00:52:32,600 --> 00:52:33,900
ก็แน่นอนแน่นอนใช่มั้ย?

1120
00:52:33,900 --> 00:52:37,110
มีมนุษย์บนโลกเป็นใคร
มีชื่อที่เป็นไปได้ที่ยาวที่สุด

1121
00:52:37,110 --> 00:52:39,920
แต่ชื่อที่เป็นค่าคงที่
ระยะเวลาค่าใช่มั้ย?

1122
00:52:39,920 --> 00:52:41,980
มันไม่ได้แตกต่างกันในความรู้สึกใด ๆ

1123
00:52:41,980 --> 00:52:45,090
ดังนั้นในวิธีนี้เราได้
ประสบความสำเร็จในโครงสร้างข้อมูล

1124
00:52:45,090 --> 00:52:47,800
ที่มีเวลาคงมองขึ้น

1125
00:52:47,800 --> 00:52:50,670
แต่จะใช้จำนวนของขั้นตอน
ขึ้นอยู่กับระยะเวลาของการป้อนข้อมูล

1126
00:52:50,670 --> 00:52:54,250
แต่ไม่จำนวนของชื่อ
ในโครงสร้างข้อมูล

1127
00:52:54,250 --> 00:52:58,700
ดังนั้นหากเราเพิ่มจำนวนของชื่อ
ปีถัดไปจากพันล้านถึงสองพันล้าน

1128
00:52:58,700 --> 00:53:03,720
การค้นพบแมกซ์เวลจะใช้เวลา
หมายเลขเดียวกันแน่นอนของเจ็ดขั้นตอน

1129
00:53:03,720 --> 00:53:04,650
ไปหาเขา

1130
00:53:04,650 --> 00:53:08,810
และเพื่อให้เราดูเหมือนจะได้ประสบความสำเร็จ
จอกศักดิ์สิทธิ์ของเราในเวลาทำงาน

1131
00:53:08,810 --> 00:53:10,860
>> ดังนั้นคู่ของประกาศอย่างรวดเร็ว

1132
00:53:10,860 --> 00:53:11,850
ศูนย์ทดสอบกำลังจะมาถึง

1133
00:53:11,850 --> 00:53:14,600
เพิ่มเติมเกี่ยวกับที่อยู่บนเว็บไซต์ของหลักสูตร
ในช่วงสองสามวันถัดไป

1134
00:53:14,600 --> 00:53:17,120
วันจันทร์ lecture-- มันเป็นวันหยุด
ที่นี่ที่ฮาร์วาร์เมื่อวันจันทร์ที่

1135
00:53:17,120 --> 00:53:18,850
มันไม่ได้ใน New Haven,
ดังนั้นเราจึงกำลังการเรียน

1136
00:53:18,850 --> 00:53:20,310
การท่าเรือใหม่สำหรับการบรรยายในวันจันทร์

1137
00:53:20,310 --> 00:53:22,550
ทุกอย่างจะได้รับการถ่ายทำ
และมีการถ่ายทอดสดตามปกติ

1138
00:53:22,550 --> 00:53:24,900
แต่ขอให้จบในวันนี้
มี 30 คลิปที่สอง

1139
00:53:24,900 --> 00:53:26,910
ที่เรียกว่า "คิดลึก"
โดย Daven Farnham ซึ่ง

1140
00:53:26,910 --> 00:53:30,850
เป็นแรงบันดาลใจปีที่ผ่านมาวันเสาร์
Night Live ของ "ความคิดลึก"

1141
00:53:30,850 --> 00:53:35,700
โดยแจ็คที่มีประโยชน์ซึ่ง
ขณะนี้ควรให้ความรู้สึก

1142
00:53:35,700 --> 00:53:38,810
>> ฟิล์ม: และตอนนี้ "ลึก
ความคิด "โดย Daven Farnham

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
ตารางแฮช

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> ลำโพงที่ 1: สิทธิทั้งหมดที่มันสำหรับตอนนี้

1147
00:53:47,660 --> 00:53:48,805
เราจะเห็นคุณในสัปดาห์ถัดไป

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: หากต้องการดูในการกระทำ

1150
00:53:56,680 --> 00:53:58,304
ดังนั้นลองมาดูที่ว่าตอนนี้

1151
00:53:58,304 --> 00:53:59,890
ดังนั้นที่นี่เรามีอาร์เรย์ที่ไม่ได้เรียงลำดับ

1152
00:53:59,890 --> 00:54:04,860
>> เอียน: ดั๊กคุณสามารถไปข้างหน้าและเริ่มต้นใหม่
นี้เพียงหนึ่งวินาทีโปรด

1153
00:54:04,860 --> 00:54:08,562
สิทธิทั้งหมดกล้องจะกลิ้งดังนั้น
การดำเนินการเมื่อใดก็ตามที่คุณพร้อมที่ดั๊ก, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG สิทธิทั้งหมดดังนั้นสิ่งที่เรา
มีที่นี่เป็นอาเรย์ไม่ได้เรียงลำดับ

1155
00:54:11,020 --> 00:54:13,960
และฉันได้สีทุกองค์ประกอบ
สีแดงเพื่อแสดงให้เห็นว่ามันเป็นในความเป็นจริง

1156
00:54:13,960 --> 00:54:14,460
ไม่ได้เรียงลำดับ

1157
00:54:14,460 --> 00:54:17,960
ดังนั้นจำได้ว่าสิ่งแรกที่เราทำ
คือเราจัดเรียงครึ่งซ้ายของอาร์เรย์

1158
00:54:17,960 --> 00:54:20,630
จากนั้นเราก็เรียงลำดับที่ถูกต้อง
ครึ่งหนึ่งของอาร์เรย์

1159
00:54:20,630 --> 00:54:22,830
และยาดา, ya-da, ya-ดา
เราผสานเข้าด้วยกัน

1160
00:54:22,830 --> 00:54:24,520
และเรามีอาร์เรย์ที่จัดเรียงอย่างสมบูรณ์

1161
00:54:24,520 --> 00:54:25,360
เพื่อให้เป็นวิธีการผสานการทำงานการจัดเรียง

1162
00:54:25,360 --> 00:54:27,109
>> เอียน: โอ้โฮโอ้โฮโอ้โฮ
ตัดตัดตัดตัด

1163
00:54:27,109 --> 00:54:30,130
ดั๊กคุณไม่สามารถเพียงแค่ยาดา, ya-ดา
ยาดาที่ทางของคุณผ่านการผสานการเรียงลำดับ

1164
00:54:30,130 --> 00:54:31,970
>> ดั๊ก: ผมก็ไม่ได้

1165
00:54:31,970 --> 00:54:32,832
ทุกอย่างปกติดี.

1166
00:54:32,832 --> 00:54:33,540
เราจะดีไป

1167
00:54:33,540 --> 00:54:34,760
ขอเพียงให้กลิ้ง

1168
00:54:34,760 --> 00:54:35,380
ยังไงก็ตาม,

1169
00:54:35,380 --> 00:54:37,800
>> เอียน: คุณต้องอธิบาย
มันมากขึ้นอย่างเต็มที่กว่า

1170
00:54:37,800 --> 00:54:39,999
นั่นเป็นเพียงไม่เพียงพอ

1171
00:54:39,999 --> 00:54:41,790
DOUG: เอียนเราทำไม่ได้
ต้องการที่จะกลับไปอย่างใดอย่างหนึ่ง

1172
00:54:41,790 --> 00:54:42,350
ทุกอย่างปกติดี.

1173
00:54:42,350 --> 00:54:45,690
ดังนั้นต่อไปถ้าเราดำเนินการกับ merge--
เอียนเรากำลังอยู่ในช่วงกลางของการถ่ายทำ

1174
00:54:45,690 --> 00:54:46,612
>> เอียน: ฉันรู้ว่า

1175
00:54:46,612 --> 00:54:49,320
และเราไม่สามารถเพียงแค่ยาดา, ya-ดา
ยาดาผ่านกระบวนการทั้งหมด

1176
00:54:49,320 --> 00:54:52,200
คุณจะต้องอธิบายว่า
ทั้งสองฝ่ายได้รับรวมกัน

1177
00:54:52,200 --> 00:54:53,570
>> ดั๊ก: แต่เราได้แล้ว
อธิบายวิธีการทั้งสอง sides--

1178
00:54:53,570 --> 00:54:55,321
>> เอียน: คุณได้แสดงให้เห็นเพียงแค่
พวกเขาอาร์เรย์ผสาน

1179
00:54:55,321 --> 00:54:56,486
ดั๊ก: พวกเขารู้ว่ากระบวนการ

1180
00:54:56,486 --> 00:54:57,172
พวกเขากำลังดี

1181
00:54:57,172 --> 00:54:58,380
เราได้ไปกว่านั้นสิบครั้ง

1182
00:54:58,380 --> 00:55:00,330
>> เอียน: คุณเพียงแค่ข้ามที่ถูกต้องมากกว่านั้น

1183
00:55:00,330 --> 00:55:03,360
เรากำลังจะกลับไปที่หนึ่งคุณ
คุณไม่สามารถยาดา, ya-da มากกว่านั้น

1184
00:55:03,360 --> 00:55:05,480
สิทธิทั้งหมดกลับไปที่หนึ่ง

1185
00:55:05,480 --> 00:55:07,833
>> ดั๊ก: ผมต้องกลับไป
ผ่านทุกภาพนิ่ง?

1186
00:55:07,833 --> 00:55:08,332
พระเจ้าของฉัน.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
มันเหมือนเป็นครั้งที่หกเอียน

1189
00:55:13,004 --> 00:55:13,940
ทุกอย่างปกติดี.

1190
00:55:13,940 --> 00:55:15,200
>> เอียนสิทธิทั้งหมด

1191
00:55:15,200 --> 00:55:16,590
คุณพร้อม?

1192
00:55:16,590 --> 00:55:17,400
ที่ดี

1193
00:55:17,400 --> 00:55:18,950
การดำเนินการ