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

2
00:00:00,500 --> 00:00:11,137
[เล่นเพลง]

3
00:00:11,137 --> 00:00:12,220
เดวิดเจลัน: ทั้งหมดขวา

4
00:00:12,220 --> 00:00:13,950
นี้เป็น CS50

5
00:00:13,950 --> 00:00:18,560
นี่เป็นสัปดาห์ที่ห้าอย่างต่อเนื่องและเรา
มีบางข่าวที่ดีและบางข่าวที่ไ​​ม่ดี

6
00:00:18,560 --> 00:00:21,140
ดังนั้นข่าวดีก็คือว่า CS50
เปิดตัววันศุกร์นี้

7
00:00:21,140 --> 00:00:24,430
ถ้าคุณต้องการที่จะเข้าร่วมกับเรา
หัวไปยัง URL ปกติท​​ี่นี่

8
00:00:24,430 --> 00:00:28,670
ข่าวที่ดียิ่งขึ้นบรรยายไม่มี
มาจันทร์ที่ 13

9
00:00:28,670 --> 00:00:31,970
น้อยข่าวที่ดีขึ้น
แบบทดสอบศูนย์เป็นวันพุธหน้า

10
00:00:31,970 --> 00:00:33,840
รายละเอียดเพิ่มเติมสามารถ
พบที่ URL ที่นี่

11
00:00:33,840 --> 00:00:36,340
และในอีกสองสามวัน
เราจะเติมในช่องว่าง

12
00:00:36,340 --> 00:00:39,234
ที่มีไปถึงห้องพัก
ว่าเราจะได้ลิขสิทธิ์

13
00:00:39,234 --> 00:00:41,400
ข่าวที่ดีคือว่ามีจะ
จะทบทวนหลักสูตรกว้าง

14
00:00:41,400 --> 00:00:43,570
เซสชั่นนี้มา
วันจันทร์ในช่วงเย็น

15
00:00:43,570 --> 00:00:46,270
ติดตามความคืบหน้าในการเรียนการสอนของ
เว็บไซต์สำหรับสถานที่ตั้งและรายละเอียด

16
00:00:46,270 --> 00:00:49,290
ส่วนถึงแม้ว่ามันจะ
วันหยุดยังจะได้พบเช่นกัน

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
ข่าวที่ดีที่สุด, บรรยายวันศุกร์ถัดไป

19
00:00:52,940 --> 00:00:56,220
ดังนั้นนี่คือเราประเพณี
มีตามหลักสูตร

20
00:00:56,220 --> 00:00:58,100
Just-- มันจะเป็นที่น่าตื่นตาตื่นใจ

21
00:00:58,100 --> 00:01:02,510
คุณจะเห็นสิ่งที่ต้องการ
โครงสร้างข้อมูลเวลาคงที่

22
00:01:02,510 --> 00:01:04,730
และตารางแฮชและต้นไม้และพยายาม

23
00:01:04,730 --> 00:01:07,150
และเราจะพูดคุยเกี่ยวกับปัญหาวันเกิด

24
00:01:07,150 --> 00:01:09,440
ทั้งกลุ่มของสิ่งที่
รอวันศุกร์ถัดไป

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
ตกลง

27
00:01:12,200 --> 00:01:13,190
แต่อย่างใด

28
00:01:13,190 --> 00:01:17,080
>> ดังนั้นจำได้ว่าเราได้รับ
มุ่งเน้นไปที่ภาพของสิ่งนี้

29
00:01:17,080 --> 00:01:18,980
ภายในของหน่วยความจำคอมพิวเตอร์ของเรา

30
00:01:18,980 --> 00:01:22,875
ดังนั้นหน่วยความจำหรือแรมที่โปรแกรม
ที่มีอยู่ในขณะที่คุณกำลังใช้งานพวกเขา

31
00:01:22,875 --> 00:01:25,215
ถ้าคุณคลิกสองครั้ง
ไอคอนเพื่อรันโปรแกรมบางอย่าง

32
00:01:25,215 --> 00:01:27,520
หรือดับเบิลคลิกที่
icon เพื่อเปิดไฟล์บาง

33
00:01:27,520 --> 00:01:30,430
ก็โหลดจากฮาร์ดดิสก์ของคุณ
ไดรฟ์หรือไดรฟ์ของรัฐที่มั่นคง

34
00:01:30,430 --> 00:01:34,190
เป็น RAM, Random Access Memory ที่
มันอาศัยอยู่จนไฟดับลง

35
00:01:34,190 --> 00:01:36,700
แล็ปท็อปฝาปิด
หรือคุณออกจากโปรแกรม

36
00:01:36,700 --> 00:01:38,960
>> ขณะนี้หน่วยความจำที่ของ
ซึ่งคุณอาจจะมี

37
00:01:38,960 --> 00:01:41,950
1 กิกะไบต์วันนี้ 2
กิกะไบต์, หรือแม้กระทั่งมากขึ้น

38
00:01:41,950 --> 00:01:44,420
โดยทั่วไปจะวางออก
สำหรับโปรแกรมที่กำหนด

39
00:01:44,420 --> 00:01:47,170
ในการเรียงลำดับของรูปสี่เหลี่ยมผืนผ้านี้
รูปแบบความคิด

40
00:01:47,170 --> 00:01:50,860
โดยเรามีสแต็คที่ด้านล่าง
และพวงของสิ่งอื่น ๆ ที่ด้านบน

41
00:01:50,860 --> 00:01:53,140
สิ่งที่ส่วนบนสุด
ที่เราได้เห็นในภาพนี้

42
00:01:53,140 --> 00:01:55,670
ก่อน แต่ไม่เคยพูดคุยเกี่ยวกับ
เป็นส่วนข้อความที่เรียกว่า

43
00:01:55,670 --> 00:01:58,419
ส่วนข้อความนี้เป็นเพียงวิธีแฟนซี
พูดว่าศูนย์และคนที่

44
00:01:58,419 --> 00:02:01,150
เขียนโปรแกรมคอมไพล์ที่แท้จริงของคุณ

45
00:02:01,150 --> 00:02:03,910
>> ดังนั้นเมื่อคุณคลิกสองครั้งที่
Microsoft Word บน Mac หรือ PC ของคุณ

46
00:02:03,910 --> 00:02:08,030
หรือเมื่อคุณเรียกจุดเฉือนมาริโอบน
คอมพิวเตอร์ลินุกซ์ที่หน้าต่าง terminal ของคุณ

47
00:02:08,030 --> 00:02:12,460
ศูนย์และคนที่แต่ง
Word หรือมาริโอจะถูกเก็บไว้ชั่วคราว

48
00:02:12,460 --> 00:02:16,610
ในแรมของคอมพิวเตอร์ของคุณในที่เรียกว่า
ส่วนข้อความสำหรับโปรแกรมเฉพาะ

49
00:02:16,610 --> 00:02:19,080
ด้านล่างที่จะไปเริ่มต้น
และเตรียมข้อมูล

50
00:02:19,080 --> 00:02:22,655
นี่คือสิ่งที่ต้องการตัวแปรทั่วโลก
ที่เราได้ไม่ได้ใช้จำนวนมากของ

51
00:02:22,655 --> 00:02:24,910
แต่ในโอกาสที่เราได้
มีตัวแปรทั่วโลก

52
00:02:24,910 --> 00:02:28,819
หรือกำหนดสตริงแบบคงที่
เป็นรหัสที่ยากคำว่า "สวัสดี"

53
00:02:28,819 --> 00:02:31,860
ที่ไม่ได้นำมาจากผู้ใช้
ที่ได้รับการกำหนดค่าตายตัวลงในโปรแกรมของคุณ

54
00:02:31,860 --> 00:02:34,230
>> ตอนนี้ลงที่ด้านล่างเรา
มีที่เรียกว่าสแต็ค

55
00:02:34,230 --> 00:02:37,665
และกองป่านนี้เราได้รับ
ใช้สำหรับสิ่งที่ชนิดของวัตถุประสงค์?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
สิ่งที่สแต็คที่ถูกนำมาใช้ใช่หรือไม่

58
00:02:40,997 --> 00:02:41,160
ใช่?

59
00:02:41,160 --> 00:02:42,070
>> ผู้ชม: ฟังก์ชั่น

60
00:02:42,070 --> 00:02:43,320
>> เดวิดเจลัน: สำหรับฟังก์ชั่น?

61
00:02:43,320 --> 00:02:44,980
ในสิ่งที่เหมาะสมสำหรับฟังก์ชั่น?

62
00:02:44,980 --> 00:02:48,660
>> ผู้ชม: เมื่อคุณเรียกฟังก์ชัน
ข้อโต้แย้งที่จะถูกคัดลอกลงบนสแต็ค

63
00:02:48,660 --> 00:02:49,660
>> เดวิดเจลัน: แน่นอน

64
00:02:49,660 --> 00:02:52,650
เมื่อคุณเรียกฟังก์ชั่นของมัน
ข้อโต้แย้งที่จะถูกคัดลอกลงบนสแต็ค

65
00:02:52,650 --> 00:02:56,330
ดังนั้น X ใด ๆ หรือ Y หรือหรือข
ที่คุณผ่านเข้ามาในฟังก์ชั่น

66
00:02:56,330 --> 00:02:58,680
จะใส่ชั่วคราว
ที่เรียกว่ากอง

67
00:02:58,680 --> 00:03:02,000
เช่นเพียงหนึ่งใน Annenberg
รับประทานอาหารถาดฮอลล์และยังมีสิ่ง

68
00:03:02,000 --> 00:03:03,190
เช่นตัวแปรท้องถิ่น

69
00:03:03,190 --> 00:03:06,290
ถ้าฟังก์ชัน foo หรือแลกเปลี่ยนของคุณ
ฟังก์ชั่นมีตัวแปรท้องถิ่น

70
00:03:06,290 --> 00:03:08,602
เช่นอุณหภูมิ, ทั้งสอง
จบลงในกอง

71
00:03:08,602 --> 00:03:11,560
ตอนนี้เราจะไม่พูดมากเกินไปเกี่ยวกับ
พวกเขา แต่ตัวแปรสภาพแวดล้อมเหล่านี้

72
00:03:11,560 --> 00:03:15,690
ที่ด้านล่างที่เราเห็นในขณะที่ที่ผ่านมาเมื่อ
ผม futzing ที่แป้นพิมพ์หนึ่งวัน

73
00:03:15,690 --> 00:03:20,050
และผมก็เริ่มเข้าถึงสิ่งที่
เช่น argv 100 หรือ argv 1,000

74
00:03:20,050 --> 00:03:22,320
เพียง elements-- ลืม
numbers-- แต่ที่

75
00:03:22,320 --> 00:03:24,330
ไม่ควรที่จะเข้าถึงได้โดยฉัน

76
00:03:24,330 --> 00:03:26,581
เราเริ่มเห็นบาง
ขี้ขลาดสัญลักษณ์บนหน้าจอ

77
00:03:26,581 --> 00:03:28,330
สิ่งเหล่านี้เป็นที่เรียกว่า
ตัวแปรสภาพแวดล้อม

78
00:03:28,330 --> 00:03:32,390
เช่นการตั้งค่าสำหรับโลกของฉัน
หรือโปรแกรมสำหรับเครื่องคอมพิวเตอร์ของฉันไม่

79
00:03:32,390 --> 00:03:37,090
ไม่เกี่ยวข้องกับที่ผ่านมา
ข้อผิดพลาดที่เรากล่าวถึง

80
00:03:37,090 --> 00:03:39,670
ทำพิษ, ที่ได้รับ
รบกวนคอมพิวเตอร์ค่อนข้างน้อย

81
00:03:39,670 --> 00:03:42,960
>> ตอนสุดท้ายในการมุ่งเน้นในวันนี้
เราในท้ายที่สุดจะได้ในกอง

82
00:03:42,960 --> 00:03:44,864
นี้เป็นก้อนของหน่วยความจำอื่น

83
00:03:44,864 --> 00:03:47,030
และพื้นฐานทั้งหมดนี้
หน่วยความจำเป็นสิ่งเดียวกัน

84
00:03:47,030 --> 00:03:48,040
มันเป็นฮาร์ดแวร์เดียวกัน

85
00:03:48,040 --> 00:03:49,956
เราเป็นแค่การจัดเรียงของ
การรักษากลุ่มที่แตกต่างกัน

86
00:03:49,956 --> 00:03:51,460
ของไบต์เพื่อวัตถุประสงค์ที่แตกต่างกัน

87
00:03:51,460 --> 00:03:56,540
กองยังเป็นไปได้ที่
ตัวแปรและหน่วยความจำที่คุณร้องขอ

88
00:03:56,540 --> 00:03:58,810
จากระบบปฏิบัติการ
จะถูกเก็บไว้ชั่วคราว

89
00:03:58,810 --> 00:04:01,890
>> แต่มีชนิดของปัญหา
นี่เป็นภาพที่มีความหมาย

90
00:04:01,890 --> 00:04:05,261
เราเรียงลำดับของการมีสอง
เรือจะชนกัน

91
00:04:05,261 --> 00:04:08,010
เพราะในขณะที่คุณใช้มากขึ้นและมากขึ้น
ของสแต็คและในขณะที่เราเห็นในวันนี้

92
00:04:08,010 --> 00:04:11,800
เป็นต้นในขณะที่คุณใช้มากขึ้นของ
กองแน่นอนสิ่งเลวร้ายที่อาจเกิดขึ้น

93
00:04:11,800 --> 00:04:15,054
และแน่นอนเราสามารถทำให้เกิดการที่
ตั้งใจหรือไม่ตั้งใจ

94
00:04:15,054 --> 00:04:16,970
ดังนั้นที่น่าตื่นเต้นที่ผ่านมา
เวลาเป็นโปรแกรมนี้

95
00:04:16,970 --> 00:04:20,570
ซึ่งไม่ได้ให้บริการการทำงานใด ๆ
นอกเหนือจากวัตถ​​ุประสงค์เพื่อแสดงให้เห็น

96
00:04:20,570 --> 00:04:24,750
วิธีการที่คุณเป็นคนเลวจริงสามารถใช้
ประโยชน์จากข้อบกพร่องในโปรแกรมของใครบางคน

97
00:04:24,750 --> 00:04:28,460
และใช้เวลามากกว่าโปรแกรมหรือแม้แต่
ระบบคอมพิวเตอร์ทั้งหมดหรือเซิร์ฟเวอร์

98
00:04:28,460 --> 00:04:31,660
ดังนั้นเพียงแค่การได้อย่างรวดเร็วในเวลาสั้น ๆ คุณ
สังเกตหลักที่ด้านล่างว่า

99
00:04:31,660 --> 00:04:34,510
จะใช้เวลาในบรรทัดคำสั่ง
ข้อโต้แย้งตาม argv

100
00:04:34,510 --> 00:04:38,480
และมีการเรียกฟังก์ชัน f,
เป็นหลักฟังก์ชันนิรนามที่เรียกว่า

101
00:04:38,480 --> 00:04:40,250
ฉและมันก็ผ่านใน argv [1]

102
00:04:40,250 --> 00:04:43,960
>> ดังนั้นไม่ว่าคำประเภทผู้ใช้ในที่
ให้หลังชื่อของโปรแกรมนี้

103
00:04:43,960 --> 00:04:49,310
แล้วฟังก์ชั่นนี้ขึ้นโดยพลการ
ด้านบน, F, ใช้เวลาในสตริงอาคาถ่าน *

104
00:04:49,310 --> 00:04:51,720
ในขณะที่เราได้เริ่มต้นเพื่อหารือเกี่ยวกับ
และมันก็เรียกมันว่า "บาร์".

105
00:04:51,720 --> 00:04:53,310
แต่เราสามารถเรียกมันว่าอะไร

106
00:04:53,310 --> 00:04:57,470
และจากนั้นจะประกาศภายใน
ของ F, อาร์เรย์ของตัวอักษร

107
00:04:57,470 --> 00:04:59,930
เรียกว่า c-- 12 ตัวอักษรดังกล่าว

108
00:04:59,930 --> 00:05:03,580
>> ตอนนี้จากเรื่องราวที่ผมบอก
ช่วงเวลาที่ผ่านมาที่ในหน่วยความจำ

109
00:05:03,580 --> 00:05:06,720
คือ c หรือเป็นผู้ที่ 12
ตัวอักษรจะจบได้อย่างไร

110
00:05:06,720 --> 00:05:07,570
เพียงเพื่อให้มีความชัดเจน

111
00:05:07,570 --> 00:05:08,070
ใช่?

112
00:05:08,070 --> 00:05:08,590
>> ผู้ชม: บนสแต็ค

113
00:05:08,590 --> 00:05:09,420
>> เดวิดเจลัน: บนสแต็ค

114
00:05:09,420 --> 00:05:10,720
ดังนั้น c คือตัวแปรท้องถิ่น

115
00:05:10,720 --> 00:05:14,079
เราขอ 12 ตัวอักษรหรือ 12 ไบต์

116
00:05:14,079 --> 00:05:16,120
ผู้ที่กำลังจะจบลง
ที่เรียกว่าสแต็ค

117
00:05:16,120 --> 00:05:18,530
ตอนนี้จนเป็นฟังก์ชั่นอื่น ๆ
ที่จริงที่มีประโยชน์สวย

118
00:05:18,530 --> 00:05:20,571
แต่เราไม่ได้ใช้จริงๆ
มันเอง strncopy

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
มันหมายถึงการคัดลอกสตริง แต่
n ตัวอักษร n ตัวอักษรเท่านั้น

121
00:05:25,200 --> 00:05:31,990
ดังนั้นตัวอักษรที่ n จะเป็น
คัดลอกมาจากบาร์ในค

122
00:05:31,990 --> 00:05:32,980
และวิธีการที่หลายคน?

123
00:05:32,980 --> 00:05:34,110
ความยาวของบาร์

124
00:05:34,110 --> 00:05:36,330
ดังนั้นในคำอื่น ๆ ที่
หนึ่งบรรทัด strncopy,

125
00:05:36,330 --> 00:05:39,500
จะคัดลอก
ได้อย่างมีประสิทธิภาพในบาร์ค

126
00:05:39,500 --> 00:05:42,340
>> ตอนนี้เพียงชนิดของการคาดการณ์
คุณธรรมของเรื่องนี้

127
00:05:42,340 --> 00:05:44,750
สิ่งที่เป็นปัญหาที่อาจเกิดขึ้นที่นี่?

128
00:05:44,750 --> 00:05:49,710
แม้ว่าเรากำลังตรวจสอบความยาว
บาร์และผ่านมันลงไปใน strncopy,

129
00:05:49,710 --> 00:05:53,145
สิ่งที่ลำไส้ของคุณบอกคุณเป็น
หักยังคงเกี่ยวกับโปรแกรมนี้?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
ใช่?

132
00:05:55,220 --> 00:05:57,491
>> ผู้ชม: ไม่รวม
ห้องพักสำหรับอักขระ null

133
00:05:57,491 --> 00:05:59,990
เดวิดเจลัน: ไม่รวม
ห้องพักสำหรับอักขระ null

134
00:05:59,990 --> 00:06:02,073
อาจแตกต่างจากใน
การปฏิบัติที่ผ่านมาที่เราทำไม่ได้

135
00:06:02,073 --> 00:06:04,810
มีให้มากที่สุดเท่าบวก 1 ถึง
รองรับว่าอักขระ null

136
00:06:04,810 --> 00:06:06,649
แต่ก็จะยิ่งแย่ไปกว่านั้น

137
00:06:06,649 --> 00:06:07,940
อะไรที่เราไม่สามารถที่จะทำอย่างไร

138
00:06:07,940 --> 00:06:08,432
ใช่?

139
00:06:08,432 --> 00:06:09,307
>> ผู้ชม: [ไม่ได้ยิน]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
เดวิดเจลัน: ที่สมบูรณ์แบบ

142
00:06:16,440 --> 00:06:18,490
เราได้เขียนยาก 12 สวยพล

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
ที่เป็นไม่มาก
ปัญหา แต่ความจริง

145
00:06:21,330 --> 00:06:25,630
ที่เราไม่ได้ตรวจสอบว่า
ความยาวของบาร์จะน​​้อยกว่า 12

146
00:06:25,630 --> 00:06:28,530
ในกรณีที่มันเป็นไปได้
ปลอดภัยที่จะใส่ลงในหน่วยความจำ

147
00:06:28,530 --> 00:06:30,260
เรียกว่าคที่เราได้รับการจัดสรร

148
00:06:30,260 --> 00:06:32,960
แน่นอนถ้าบาร์ก็เหมือน
20 ตัวอักษรยาว

149
00:06:32,960 --> 00:06:39,010
ฟังก์ชั่นนี้จะปรากฏขึ้นที่จะคัดลอก
20 ตัวอักษรจากแถบเป็นคจึง

150
00:06:39,010 --> 00:06:41,310
การไม่น้อยกว่า 8 ไบต​​์
ว่ามันไม่ควรจะเป็น

151
00:06:41,310 --> 00:06:42,690
นั่นคือความหมายที่นี่

152
00:06:42,690 --> 00:06:44,347
>> ดังนั้นในระยะสั้นโปรแกรมหัก

153
00:06:44,347 --> 00:06:45,180
ไม่ได้เป็นเรื่องใหญ่

154
00:06:45,180 --> 00:06:46,360
บางทีคุณอาจจะได้รับความผิดส่วน

155
00:06:46,360 --> 00:06:47,651
เรามีทุกข้อบกพร่องในโปรแกรม

156
00:06:47,651 --> 00:06:50,196
เราทุกคนอาจจะมีข้อบกพร่อง
ในโปรแกรมได้ในขณะนี้

157
00:06:50,196 --> 00:06:51,320
แต่สิ่งที่เป็นความหมายหรือไม่

158
00:06:51,320 --> 00:06:54,390
ดีที่นี่เป็นรุ่นที่ซูมในของ
ภาพของหน่วยความจำของคอมพิวเตอร์ของฉันที่

159
00:06:54,390 --> 00:06:56,230
นี่คือด้านล่างของสแต็คของฉัน

160
00:06:56,230 --> 00:06:59,644
และแน่นอนที่ด้านล่างสุดเป็นสิ่งที่
เรียกว่ากองประจำแม่วิธีแฟนซี

161
00:06:59,644 --> 00:07:00,560
ที่บอกว่าเป็นหลัก

162
00:07:00,560 --> 00:07:03,772
เพื่อให้ใครก็ตามที่เรียกว่าฟังก์ชั่น
ฉนั้นเรากำลังพูดถึง

163
00:07:03,772 --> 00:07:05,230
ดังนั้นนี่คือด้านล่างของสแต็ค

164
00:07:05,230 --> 00:07:06,640
ที่อยู่ผู้ส่งเป็นสิ่งที่ใหม่

165
00:07:06,640 --> 00:07:08,810
มันเป็นเสมอ
ได้เสมอในภาพที่

166
00:07:08,810 --> 00:07:10,440
เราก็ไม่เคยเรียกความสนใจไปที่

167
00:07:10,440 --> 00:07:15,290
เพราะมันจะเปิดออกทางคทำงานเป็น
ว่าเมื่อฟังก์ชั่นหนึ่งเรียกร้องอื่น

168
00:07:15,290 --> 00:07:18,780
ไม่เพียง แต่ทำข้อโต้แย้งที่ว่า
ฟังก์ชั่นได้รับการผลักดันเข้าสู่กอง

169
00:07:18,780 --> 00:07:22,470
ไม่เพียง แต่ทำหน้าที่ของท้องถิ่น
ตัวแปรที่ได้รับการผลักดันเข้าสู่กอง

170
00:07:22,470 --> 00:07:26,820
สิ่งที่เรียกว่าที่อยู่ผู้ส่ง
นอกจากนี้ยังได้รับการวางลงบนสแต็ค

171
00:07:26,820 --> 00:07:33,330
โดยเฉพาะถ้าสายหลักฟูหลักของ
ที่อยู่ในความทรงจำของตัวเองบางสิ่งบางอย่างวัว

172
00:07:33,330 --> 00:07:38,240
ได้อย่างมีประสิทธิภาพได้รับการวางลงบนสแต็ค
เพื่อที่ว่าเมื่อเอฟจะทำรันมัน

173
00:07:38,240 --> 00:07:43,630
รู้ที่จะกระโดดกลับไปในข้อความ
ส่วนในการที่จะดำเนินการต่อการดำเนินงาน

174
00:07:43,630 --> 00:07:47,760
>> ดังนั้นถ้าเราอยู่ที่นี่แนวคิด
ในหลักแล้วฉได้รับเรียกว่า

175
00:07:47,760 --> 00:07:50,200
วิธีการที่ไม่ฉรู้ว่าใคร
กับการควบคุมมือกลับ?

176
00:07:50,200 --> 00:07:52,020
ดีเล็ก ๆ น้อย ๆ นี้
เกล็ดขนมปังสีแดงที่นี่

177
00:07:52,020 --> 00:07:54,978
เรียกว่าที่อยู่ผู้ส่งก็แค่
ตรวจสอบสิ่งที่เป็นที่อยู่ผู้ส่งที่?

178
00:07:54,978 --> 00:07:57,039
โอ้ให้ฉันกระโดดกลับไปที่หลักที่นี่

179
00:07:57,039 --> 00:07:59,080
และที่นิด ๆ หน่อย ๆ
ของเปลือก,

180
00:07:59,080 --> 00:08:00,750
เพราะศูนย์และคนที่
สำหรับหลักในทางเทคนิค

181
00:08:00,750 --> 00:08:01,967
ขึ้นที่นี่ในส่วนของเทคโนโลยี

182
00:08:01,967 --> 00:08:03,800
แต่นั่นเป็นความคิดที่ ฉ
ก็มีที่จะรู้ว่า

183
00:08:03,800 --> 00:08:06,680
ไปยังที่ที่การควบคุมในท้ายที่สุดกลับไป

184
00:08:06,680 --> 00:08:09,790
>> แต่ทางคอมพิวเตอร์
ได้วางยาวออกสิ่ง

185
00:08:09,790 --> 00:08:12,320
เช่นตัวแปรท้องถิ่นและ
ข้อโต้แย้งที่เป็นเช่นนี้

186
00:08:12,320 --> 00:08:17,180
ดังนั้นในด้านบนของภาพนี้
สีฟ้าเป็นกองกรอบสำหรับฉดังนั้นสิ่งที่

187
00:08:17,180 --> 00:08:19,630
ของหน่วยความจำที่ฉ
โดยเฉพาะคือการใช้

188
00:08:19,630 --> 00:08:22,990
ดังนั้นจึงสังเกตเห็นว่า
บาร์ที่อยู่ในภาพนี้

189
00:08:22,990 --> 00:08:23,980
บาร์เป็นอาร์กิวเมนต์

190
00:08:23,980 --> 00:08:27,240
และเราอ้างว่ามีปากเสียงกับ
ฟังก์ชั่นได้รับการผลักดันเข้าสู่สแตก

191
00:08:27,240 --> 00:08:29,910
และ C แน่นอนคือ
ยังอยู่ในภาพนี้

192
00:08:29,910 --> 00:08:33,520
>> และเพียงเพื่อวัตถุประสงค์สัญลักษณ์,
สังเกตเห็นที่มุมซ้ายมือด้านบน

193
00:08:33,520 --> 00:08:37,020
เป็นสิ่งที่จะเป็นควงเล็บ 0 และ
แล้วลดลงเล็กน้อยไปทางขวา

194
00:08:37,020 --> 00:08:38,220
คือ c วงเล็บ 11

195
00:08:38,220 --> 00:08:41,240
ดังนั้นในคำอื่น ๆ ที่คุณสามารถจินตนาการ
ว่ามีตารางของไบต์

196
00:08:41,240 --> 00:08:44,380
นั่นเป็นครั้งแรกที่เป็น
ด้านซ้ายด้านบนด้านล่างซึ่ง

197
00:08:44,380 --> 00:08:48,360
เป็นวันสุดท้ายของผู้ที่ 12 ไบต์

198
00:08:48,360 --> 00:08:49,930
>> แต่ตอนนี้พยายามที่จะไปข้างหน้าอย่างรวดเร็ว

199
00:08:49,930 --> 00:08:55,580
เป็นเรื่องเกี่ยวกับสิ่งที่จะเกิดขึ้นถ้าเราผ่าน
ในแถบสตริงที่ยาวกว่าค?

200
00:08:55,580 --> 00:08:59,130
และเราไม่ได้ตรวจสอบว่า
มันแน่นอนมากกว่า 12

201
00:08:59,130 --> 00:09:03,146
ซึ่งเป็นส่วนหนึ่งของภาพนี้จะ
ได้รับการเขียนทับโดยไบต์ 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, และจากนั้น
ไม่ดี, 12, 13 ผ่าน 19?

203
00:09:07,890 --> 00:09:11,820
สิ่งที่จะเกิดขึ้นที่นี่
ถ้าคุณสรุปจากการสั่งซื้อ

204
00:09:11,820 --> 00:09:14,790
ที่ควงเล็บ 0 อยู่ด้านบน
c และ 11 วงเล็บคือการจัดเรียงของลง

205
00:09:14,790 --> 00:09:15,812
ไปทางขวาหรือไม่

206
00:09:15,812 --> 00:09:16,796
ใช่?

207
00:09:16,796 --> 00:09:19,260
>> ผู้ชม: ดีก็จะ
ที่จะเขียนทับแถบ char *

208
00:09:19,260 --> 00:09:22,260
>> เดวิดเจลัน: ใช่มันดูเหมือนว่า
คุณกำลังจะเขียนทับบาร์ char *

209
00:09:22,260 --> 00:09:26,245
และแย่กว่านั้นถ้าคุณส่งในระยะยาวจริงๆ
สตริงคุณยังอาจเขียนทับอะไร

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
ที่อยู่ผู้ส่ง

212
00:09:28,570 --> 00:09:31,380
ซึ่งอีกครั้งเช่นเดียวกับ
เกล็ดขนมปังที่จะบอกโปรแกรมที่

213
00:09:31,380 --> 00:09:34,060
จะกลับไปเมื่อฉ
จะทำถูกเรียกว่า

214
00:09:34,060 --> 00:09:37,140
>> ดังนั้นสิ่งที่คนเลวมักจะทำ
คือถ้าพวกเขาเจอโปรแกรม

215
00:09:37,140 --> 00:09:41,290
ว่าพวกเขากำลังอยากรู้อยากเห็นไม่ว่าจะเป็น
ใช้ประโยชน์รถในลักษณะดังกล่าว

216
00:09:41,290 --> 00:09:43,550
ที่เขาหรือเธอสามารถใช้
ประโยชน์จากข้อผิดพลาดที่

217
00:09:43,550 --> 00:09:45,720
โดยทั่วไปพวกเขาไม่ได้รับ
เหมาะสมในครั้งแรกนี้

218
00:09:45,720 --> 00:09:48,590
พวกเขาก็เริ่มส่งตัวอย่างเช่น
สตริงสุ่มเข้าไปในโปรแกรมของคุณ

219
00:09:48,590 --> 00:09:50,260
ไม่ว่าจะที่แป้นพิมพ์
หรือตรงไปตรงมาพวกเขาอาจ

220
00:09:50,260 --> 00:09:52,740
เขียนโปรแกรมเล็ก ๆ เพียง
โดยอัตโนมัติสร้างสตริง

221
00:09:52,740 --> 00:09:55,430
และเริ่มต้นการต่อสู้ในโปรแกรมของคุณโดย
ส่งในจำนวนมากของปัจจัยการผลิตที่แตกต่างกัน

222
00:09:55,430 --> 00:09:56,340
ที่มีความยาวที่แตกต่างกัน

223
00:09:56,340 --> 00:09:58,990
>> ทันทีที่เกิดปัญหาโปรแกรมของคุณ
นั่นคือสิ่งที่น่าทึ่ง

224
00:09:58,990 --> 00:10:01,020
เพราะมันหมายความว่าเขา
หรือเธอได้ค้นพบ

225
00:10:01,020 --> 00:10:02,660
สิ่งที่น่าจะเป็นจริงข้อผิดพลาด

226
00:10:02,660 --> 00:10:05,830
และแล้วพวกเขาจะได้รับความคิดสร้างสรรค์มากขึ้น
และเริ่มต้นมุ่งเน้นมากขึ้นอย่างหวุดหวิด

227
00:10:05,830 --> 00:10:07,420
เกี่ยวกับวิธีการใช้ประโยชน์จากข้อผิดพลาดที่

228
00:10:07,420 --> 00:10:11,480
โดยเฉพาะอย่างยิ่งสิ่งที่เขาหรือเธออาจจะ
ทำคือการส่งในกรณีที่ดีที่สุดครับ

229
00:10:11,480 --> 00:10:12,210
ไม่มีเรื่องใหญ่

230
00:10:12,210 --> 00:10:14,750
มันเป็นสตริงที่สั้นพอ

231
00:10:14,750 --> 00:10:18,100
แต่สิ่งที่ถ้าเขาหรือเธอส่ง,
และเราจะพูดคุยมันเป็น

232
00:10:18,100 --> 00:10:20,890
โจมตี code-- ดังนั้นศูนย์
และคนที่ทำสิ่งที่

233
00:10:20,890 --> 00:10:25,150
เช่น RM-RF ที่เอาทุกอย่าง
จากฮาร์ดไดรฟ์หรือส่งสแปม

234
00:10:25,150 --> 00:10:27,000
หรืออย่างใดโจมตีเครื่องหรือไม่

235
00:10:27,000 --> 00:10:29,570
>> ดังนั้นหากแต่ละเหล่านี้
ตัวอักษรเพียงหมายถึง

236
00:10:29,570 --> 00:10:32,380
แนวคิดการโจมตีการโจมตี
การโจมตีการโจมตีบางรหัสที่ไม่ดี

237
00:10:32,380 --> 00:10:36,410
ว่าคนอื่นเขียน แต่
ถ้าเป็นคนที่มีความฉลาดพอที่

238
00:10:36,410 --> 00:10:40,790
ที่ไม่เพียง แต่รวมทั้งหมด
ของผู้ RM RFS แต่ยัง

239
00:10:40,790 --> 00:10:46,100
มีเพียงไม่กี่ไบต์สุดท้ายของเขาหรือเธอ
เป็นตัวเลขที่สอดคล้อง

240
00:10:46,100 --> 00:10:50,540
ไปยังที่อยู่ของเขา
หรือรหัสการโจมตีของเธอเอง

241
00:10:50,540 --> 00:10:53,820
ที่เขาหรือเธอผ่านไปในเวลาเพียง
โดยการให้ที่พรอมต์ที่

242
00:10:53,820 --> 00:10:58,760
คุณมีประสิทธิภาพสามารถหลอกคอมพิวเตอร์
เป็นสังเกตเห็นเมื่อเอฟจะทำรัน

243
00:10:58,760 --> 00:11:02,400
โอ้ก็ถึงเวลาสำหรับผมที่จะกระโดด
กลับไปอยู่กลับสีแดง

244
00:11:02,400 --> 00:11:06,070
แต่เป็นเพราะเขาหรือเธอมีอย่างใด
ซ้อนทับที่อยู่ผู้ส่งว่า

245
00:11:06,070 --> 00:11:09,602
กับจำนวนของตัวเอง
และพวกเขากำลังฉลาดพอ

246
00:11:09,602 --> 00:11:11,560
จะมีการกำหนดค่าที่
จำนวนการอ้างอิงที่คุณ

247
00:11:11,560 --> 00:11:13,740
เห็นในด้านบนสุด
มุมซ้ายมือมี

248
00:11:13,740 --> 00:11:18,020
ที่เกิดขึ้นจริงที่อยู่ในคอมพิวเตอร์ของ
ความทรงจำของบางส่วนของรหัสการโจมตีของพวกเขา

249
00:11:18,020 --> 00:11:21,740
คนเลวสามารถหลอกคอมพิวเตอร์
ในการดำเนินงานของเขาหรือรหัสของตัวเองของเธอ

250
00:11:21,740 --> 00:11:23,700
>> และรหัสที่อีกครั้งสามารถเป็นอะไรก็ได้

251
00:11:23,700 --> 00:11:26,120
มันเรียกว่าโดยทั่วไป
รหัสเปลือกซึ่งเป็นเพียง

252
00:11:26,120 --> 00:11:29,030
วิธีที่บอกว่ามันเป็นไม่ได้
โดยทั่วไปสิ่งที่ง่ายเป็น RM-RF

253
00:11:29,030 --> 00:11:32,340
เป็นจริงอย่างที่ชอบทุบตี
หรือโปรแกรมที่แท้จริงที่ทำให้เขา

254
00:11:32,340 --> 00:11:37,230
หรือการควบคุมการเขียนโปรแกรมของเธอที่จะดำเนินการ
สิ่งอื่นที่พวกเขาต้องการ

255
00:11:37,230 --> 00:11:40,210
ดังนั้นในระยะสั้นนี้ทั้งหมด
เกิดขึ้นจากความเป็นจริงง่ายๆ

256
00:11:40,210 --> 00:11:44,490
ว่าปัญหานี้ไม่ได้เกี่ยวข้องกับการตรวจสอบ
ขอบเขตของอาเรย์ของคุณ

257
00:11:44,490 --> 00:11:47,250
และเนื่องจากทาง
การทำงานของเครื่องคอมพิวเตอร์ก็คือพวกเขา

258
00:11:47,250 --> 00:11:49,430
ใช้สแต็คจาก
ได้อย่างมีประสิทธิภาพแนวคิด

259
00:11:49,430 --> 00:11:54,830
ด้านล่างขึ้น แต่แล้วองค์ประกอบ
คุณผลักดันลง stack เติบโตด้านบนลง

260
00:11:54,830 --> 00:11:56,624
นี้เป็นปัญหาอย่างไม่น่าเชื่อ

261
00:11:56,624 --> 00:11:58,290
ตอนนี้มีวิธีการทำงานรอบนี้

262
00:11:58,290 --> 00:12:00,800
และตรงไปตรงมามีภาษาที่
ด้วยซึ่งในการทำงานรอบนี้

263
00:12:00,800 --> 00:12:03,100
Java เป็นภูมิคุ้มกันเช่น
กับปัญหานี้โดยเฉพาะอย่างยิ่ง

264
00:12:03,100 --> 00:12:04,110
เพราะพวกเขาไม่ให้คำแนะนำ

265
00:12:04,110 --> 00:12:05,943
พวกเขาไม่ให้คุณ
ที่อยู่หน่วยความจำโดยตรง

266
00:12:05,943 --> 00:12:08,560
ดังนั้นด้วยอำนาจที่เรามีนี้
ไปสัมผัสอะไรในหน่วยความจำ

267
00:12:08,560 --> 00:12:11,580
ที่เราต้องการมาเป็นที่ยอมรับความเสี่ยงที่ดี

268
00:12:11,580 --> 00:12:12,430
>> เพื่อให้ตาออก

269
00:12:12,430 --> 00:12:14,596
ถ้าตรงไปตรงมาในเดือน
หรือปีที่ผ่านมาที่ทุกเวลา

270
00:12:14,596 --> 00:12:17,740
คุณอ่านเกี่ยวกับการแสวงหาผลประโยชน์บางอย่าง
ของโปรแกรมหรือเซิร์ฟเวอร์

271
00:12:17,740 --> 00:12:22,370
ถ้าคุณเคยเห็นคำใบ้ของสิ่งที่
เช่นการโจมตีหน่วยความจำล้น

272
00:12:22,370 --> 00:12:25,390
หรือกองล้นเป็นประเภทอื่น
ของการโจมตีที่คล้ายกันในจิตวิญญาณ

273
00:12:25,390 --> 00:12:28,770
มากที่สุดเท่าที่เป็นแรงบันดาลใจที่เว็บไซต์ของ
ชื่อถ้าคุณจะรู้ว่า

274
00:12:28,770 --> 00:12:33,170
มันคือทั้งหมดที่พูดถึงเพียงแค่
ล้นขนาดของตัวอักษรบาง

275
00:12:33,170 --> 00:12:36,200
อาร์เรย์หรือแถวบางมากกว่าปกติ

276
00:12:36,200 --> 00:12:38,822
คำถามใด ๆ แล้วเกี่ยวกับเรื่องนี้?

277
00:12:38,822 --> 00:12:39,780
ไม่ลองนี้ที่บ้าน

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> ขวาทั้งหมด

280
00:12:42,300 --> 00:12:47,270
ดังนั้น malloc จึงห่างไกลได้รับใหม่ของเรา
เพื่อนในการที่เราสามารถจัดสรรหน่วยความจำ

281
00:12:47,270 --> 00:12:50,540
ที่เราไม่จำเป็นต้องรู้
ความก้าวหน้าที่เราต้องการเพื่อให้เราไม่ได้มี

282
00:12:50,540 --> 00:12:52,920
รหัสยากที่เป็นของเรา
หมายเลขโปรแกรมเช่น 12

283
00:12:52,920 --> 00:12:55,550
เมื่อผู้ใช้บอกเราว่า
ข้อมูลที่เขาหรือเธอต้องการที่จะป้อนข้อมูล

284
00:12:55,550 --> 00:12:58,000
เราสามารถ malloc หน่วยความจำมากว่า

285
00:12:58,000 --> 00:13:01,484
>> ดังนั้น malloc มันจะเปิดออกไป
เท่าที่เราได้รับใช้มัน

286
00:13:01,484 --> 00:13:03,900
อย่างชัดเจนเป็นครั้งสุดท้ายแล้ว
พวกคุณได้ใช้มัน

287
00:13:03,900 --> 00:13:08,160
สำหรับ GetString ไม่รู้สำหรับ
หลายสัปดาห์ที่ผ่านมาทั้งหมดของหน่วยความจำ malloc ของ

288
00:13:08,160 --> 00:13:09,820
มาจากการที่เรียกว่ากอง

289
00:13:09,820 --> 00:13:13,852
และนี่คือเหตุผล GetString ตัวอย่างเช่น
สามารถจัดสรรหน่วยความจำแบบไดนามิก

290
00:13:13,852 --> 00:13:16,060
โดยไม่ทราบว่าสิ่งที่คุณกำลัง
จะพิมพ์ล่วงหน้า

291
00:13:16,060 --> 00:13:21,520
มือคุณกลับชี้ไปยังหน่วยความจำที่
และหน่วยความจำที่ยังคงของคุณเพื่อให้,

292
00:13:21,520 --> 00:13:24,080
แม้หลังจาก GetString ผลตอบแทน

293
00:13:24,080 --> 00:13:27,450
เพราะการเรียกคืนหลังจากที่
กองอยู่ตลอดเวลาจะขึ้นและลง

294
00:13:27,450 --> 00:13:27,950
ขึ้นและลง

295
00:13:27,950 --> 00:13:30,230
และเร็วที่สุดเท่าที่มันจะไป
ลงนั่นหมายความว่าหน่วยความจำใด

296
00:13:30,230 --> 00:13:33,030
ฟังก์ชันนี้ใช้ควร
ไม่ได้นำมาใช้โดยคนอื่น

297
00:13:33,030 --> 00:13:34,570
มันเป็นค่าขยะตอนนี้

298
00:13:34,570 --> 00:13:36,120
>> แต่กองขึ้นที่นี่

299
00:13:36,120 --> 00:13:39,360
และสิ่งที่ดีเกี่ยวกับ malloc คือ
เมื่อ malloc จัดสรรหน่วยความจำขึ้นที่นี่

300
00:13:39,360 --> 00:13:42,070
มันไม่ได้ส่งผลกระทบต่อการ
ส่วนใหญ่โดยกอง

301
00:13:42,070 --> 00:13:46,000
และเพื่อให้การทำงานใด ๆ ที่สามารถเข้าถึง
หน่วยความจำที่ได้รับการ malloc'd,

302
00:13:46,000 --> 00:13:49,120
แม้โดยฟังก์ชันเช่น GetString,
แม้กระทั่งหลังจากที่มันจะถูกส่งกลับ

303
00:13:49,120 --> 00:13:51,700
>> ตอนนี้การสนทนาของ malloc ฟรี

304
00:13:51,700 --> 00:13:53,900
และแน่นอนคุณกฎ
จะต้องเริ่มต้นการใช้

305
00:13:53,900 --> 00:13:58,950
เป็นใด ๆ ทุกครั้งที่คุณใช้ malloc ใด ๆ
คุณเองต้องใช้ฟรีในที่สุด

306
00:13:58,950 --> 00:14:00,280
ในตัวชี้เดียวกันกับที่

307
00:14:00,280 --> 00:14:03,289
ทุกครั้งที่เราได้รับการเขียนนี้
รถ, รหัสรถ, ด้วยเหตุผลหลายประการ

308
00:14:03,289 --> 00:14:05,580
แต่คนที่ได้รับ
โดยใช้ห้องสมุด CS50 ซึ่ง

309
00:14:05,580 --> 00:14:09,010
ตัวเองเป็นอย่างจงใจ
รถก็รั่วไหลของหน่วยความจำ

310
00:14:09,010 --> 00:14:11,410
เวลาที่คุณเรียกว่า GetString ใด ๆ
ในช่วงไม่กี่สัปดาห์ที่ผ่านมา

311
00:14:11,410 --> 00:14:13,870
เรากำลังขอให้การดำเนินงานของ
ระบบลินุกซ์สำหรับหน่วยความจำ

312
00:14:13,870 --> 00:14:15,780
และคุณยังไม่เคยได้รับเมื่อมันกลับมา

313
00:14:15,780 --> 00:14:17,730
และนี่คือไม่ได้ใน
การปฏิบัติเป็นสิ่งที่ดี

314
00:14:17,730 --> 00:14:20,330
>> และ Valgrind ซึ่งเป็นหนึ่งใน
เครื่องมือที่นำมาใช้ใน Pset 4

315
00:14:20,330 --> 00:14:22,900
เป็นข้อมูลเกี่ยวกับการช่วยให้คุณ
ขณะนี้พบข้อบกพร่องเช่นนั้น

316
00:14:22,900 --> 00:14:27,060
แต่โชคดีสำหรับ Pset 4 คุณไม่จำเป็นต้อง
การใช้ห้องสมุด CS50 หรือ GetString

317
00:14:27,060 --> 00:14:31,220
ดังนั้นข้อบกพร่องใด ๆ ที่เกี่ยวข้องกับหน่วยความจำ
ในท้ายที่สุดจะเป็นของคุณเอง

318
00:14:31,220 --> 00:14:34,060
>> ดังนั้น malloc เป็นมากกว่าเพียงแค่
สิ่งอำนวยความสะดวกเพื่อการนี​​้

319
00:14:34,060 --> 00:14:37,420
เราสามารถจริงตอนนี้แก้
ปัญหาที่แตกต่างกันโดยพื้นฐาน

320
00:14:37,420 --> 00:14:41,640
และพื้นฐานการแก้ปัญหามากขึ้น
ได้อย่างมีประสิทธิภาพตามสัญญาสัปดาห์ที่ศูนย์ของ

321
00:14:41,640 --> 00:14:44,720
ป่านนี้นี้เป็นที่เซ็กซี่ที่สุด
โครงสร้างข้อมูลที่เราเคยมี

322
00:14:44,720 --> 00:14:47,804
และโครงสร้างข้อมูลฉันหมายถึง
วิธีการของหน่วยความจำ conceptualizing

323
00:14:47,804 --> 00:14:50,720
ในทางที่ไปกว่าเพียงแค่การพูด,
นี้เป็น int นี้เป็นถ่าน

324
00:14:50,720 --> 00:14:52,930
เราสามารถเริ่มต้นที่จะจัดกลุ่มสิ่งต่างๆร่วมกัน

325
00:14:52,930 --> 00:14:54,460
>> ดังนั้นอาร์เรย์มองเช่นนี้

326
00:14:54,460 --> 00:14:57,270
และสิ่งที่เป็นกุญแจสำคัญในการเกี่ยวกับ
อาเรย์ก็คือว่ามันจะช่วยให้คุณ

327
00:14:57,270 --> 00:14:59,724
กลับไปกลับ chunks ของ
หน่วยความจำซึ่งแต่ละ

328
00:14:59,724 --> 00:15:02,765
เป็นไปได้ของประเภทเดียวกัน int,
int, int, int หรือถ่าน, ถ่าน, ถ่าน,

329
00:15:02,765 --> 00:15:03,330
ถ่าน

330
00:15:03,330 --> 00:15:04,496
แต่มีข้อเสียไม่กี่

331
00:15:04,496 --> 00:15:06,570
นี้ตัวอย่างเช่นเป็น
อาร์เรย์ของหกขนาด

332
00:15:06,570 --> 00:15:10,650
สมมติว่าคุณกรอกอาร์เรย์นี้กับหก
หมายเลขแล้วด้วยเหตุผลอะไรก็ตาม

333
00:15:10,650 --> 00:15:13,187
ผู้ใช้ของคุณต้องการที่จะให้
คุณเป็นจำนวนเจ็ด

334
00:15:13,187 --> 00:15:14,020
คุณจะใส่มันได้หรือไม่

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> อะไรคือการแก้ปัญหาหากคุณมี
สร้างอาร์เรย์ในกอง

337
00:15:18,990 --> 00:15:22,030
เช่นเดียวกับสัปดาห์
สองสัญกรณ์ที่เราแนะนำ

338
00:15:22,030 --> 00:15:23,730
ของวงเล็บที่มีจำนวนที่อยู่ภายในหรือไม่

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
ดีที่คุณได้มีหก
ตัวเลขในกล่องเหล่านี้

341
00:15:27,260 --> 00:15:28,530
สิ่งที่สัญชาตญาณของคุณจะเป็นอย่างไร

342
00:15:28,530 --> 00:15:29,973
ที่คุณจะต้องการที่จะนำมันได้หรือไม่

343
00:15:29,973 --> 00:15:30,860
>> ผู้ชม: [ไม่ได้ยิน]

344
00:15:30,860 --> 00:15:31,315
>> เดวิดเจลัน: ขออภัย?

345
00:15:31,315 --> 00:15:32,380
>> ผู้ชม: วางไว้ที่ปลาย

346
00:15:32,380 --> 00:15:33,796
>> เดวิดเจลัน: วางไว้ที่ปลาย

347
00:15:33,796 --> 00:15:35,880
ดังนั้นเพียงแค่ผ่านไปทางขวา
ด้านนอกของกล่องนี้

348
00:15:35,880 --> 00:15:38,710
ซึ่งจะดี แต่ก็
จะเปิดออกคุณไม่สามารถทำเช่นนั้นได้

349
00:15:38,710 --> 00:15:41,350
เพราะถ้าคุณไม่ได้ถาม
สำหรับก้อนของหน่วยความจำนี้

350
00:15:41,350 --> 00:15:44,490
มันอาจจะโดยบังเอิญที่นี้
จะถูกใช้โดยบางตัวแปรอื่น ๆ

351
00:15:44,490 --> 00:15:45,030
โดยสิ้นเชิง

352
00:15:45,030 --> 00:15:49,210
คิดย้อนกลับไปหนึ่งสัปดาห์หรือดังนั้นเมื่อเราวาง
ออก Zamyla และดาวินและเกบชื่อ

353
00:15:49,210 --> 00:15:49,930
ในความทรงจำ

354
00:15:49,930 --> 00:15:51,638
พวกเขาอย่างแท้จริง
หลังการสำรองข้อมูล

355
00:15:51,638 --> 00:15:53,550
ดังนั้นเราจึงไม่สามารถหลีกเลี่ยง
เชื่อว่าของอะไรก็ตาม

356
00:15:53,550 --> 00:15:55,800
ที่นี่สามารถใช้ได้สำหรับผมที่จะใช้

357
00:15:55,800 --> 00:15:56,990
>> ดังนั้นอะไรที่คุณอาจทำอย่างไร

358
00:15:56,990 --> 00:16:00,282
ดีเมื่อคุณตระหนักถึง
ต้องอาร์เรย์ของขนาดเจ็ด,

359
00:16:00,282 --> 00:16:02,490
คุณก็สามารถสร้าง
อาร์เรย์ของขนาดเจ็ดแล้วใช้

360
00:16:02,490 --> 00:16:05,950
สำหรับวงหรือวงในขณะที่
คัดลอกลงในอาร์เรย์ใหม่

361
00:16:05,950 --> 00:16:09,680
แล้วอย่างใดเพียงกำจัด
แถวนี้หรือเพียงแค่หยุดใช้มัน

362
00:16:09,680 --> 00:16:12,130
แต่ที่ไม่ได้มีประสิทธิภาพโดยเฉพาะอย่างยิ่ง

363
00:16:12,130 --> 00:16:15,340
ในระยะสั้นอาร์เรย์จะไม่ปล่อยให้
คุณแบบไดนามิกปรับขนาด

364
00:16:15,340 --> 00:16:17,900
>> ดังนั้นบนมือข้างหนึ่งคุณจะได้รับ
เข้าถึงโดยสุ่มซึ่งเป็นที่น่าตื่นตาตื่นใจ

365
00:16:17,900 --> 00:16:20,108
เพราะมันช่วยให้เราทำในสิ่งที่
เช่นการแบ่งและพิชิต,

366
00:16:20,108 --> 00:16:23,100
ค้นหา binary ทั้งหมดที่เราได้
พูดคุยเกี่ยวกับบนหน้าจอที่นี่

367
00:16:23,100 --> 00:16:24,950
แต่คุณวาดตัวเองเข้าไปในมุม

368
00:16:24,950 --> 00:16:27,810
เร็วที่สุดเท่าที่คุณจะตี
ปลายแถวของคุณ

369
00:16:27,810 --> 00:16:29,980
ที่คุณต้องทำมาก
การดำเนินงานที่มีราคาแพง

370
00:16:29,980 --> 00:16:33,910
หรือเขียนทั้งกลุ่มของรหัส
ถึงตอนนี้จัดการกับปัญหาที่

371
00:16:33,910 --> 00:16:36,680
>> ดังนั้นสิ่งที่ถ้าเรามีแทน
สิ่งที่เรียกว่ารายการ

372
00:16:36,680 --> 00:16:38,820
หรือรายการที่เชื่อมโยงโดยเฉพาะอย่างยิ่ง?

373
00:16:38,820 --> 00:16:41,930
สิ่งที่ถ้าแทนที่จะต้อง
สี่เหลี่ยมกลับไปกลับไปกลับ

374
00:16:41,930 --> 00:16:45,730
เรามีรูปสี่เหลี่ยมที่ออกจากเล็ก ๆ น้อย ๆ
บิตของห้องเลื้อยในระหว่างพวกเขา?

375
00:16:45,730 --> 00:16:49,670
และแม้ว่าฉันได้วาดนี้
รูปภาพหรือดัดแปลงภาพนี้

376
00:16:49,670 --> 00:16:54,696
จากหนึ่งในตำราที่นี่เพื่อจะกลับไป
หลังเป็นระเบียบเรียบร้อยมากในความเป็นจริง

377
00:16:54,696 --> 00:16:56,820
หนึ่งในสี่เหลี่ยมที่
อาจจะขึ้นที่นี่ในความทรงจำ

378
00:16:56,820 --> 00:16:58,028
หนึ่งของพวกเขาอาจจะมีขึ้นที่นี่

379
00:16:58,028 --> 00:17:00,420
หนึ่งของพวกเขาอาจจะมีขึ้นที่นี่
กว่าที่นี่และอื่น ๆ

380
00:17:00,420 --> 00:17:02,910
>> แต่ถ้าเราดึง
ในกรณีนี้ลูกศร

381
00:17:02,910 --> 00:17:05,650
ที่ใดเชื่อมโยงเหล่านี้
รูปสี่เหลี่ยมพร้อมกันไหม

382
00:17:05,650 --> 00:17:08,170
อันที่จริงเราได้เห็นเทคนิค
ชาติของลูกศร

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
สิ่งที่เรานำมาใช้ในเร็ว ๆ นี้
วันที่ใต้กระโปรงหน้ารถ

385
00:17:13,710 --> 00:17:15,210
เป็นตัวแทนของลูกศร?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
ตัวชี้ขวา?

388
00:17:17,349 --> 00:17:19,780
>> ดังนั้นสิ่งที่ถ้าแทน
เพียงแค่การจัดเก็บตัวเลข

389
00:17:19,780 --> 00:17:23,130
เช่น 9, 17, 22, 26, 34,
สิ่งที่ถ้าเราเก็บไว้ไม่ได้

390
00:17:23,130 --> 00:17:27,079
เพียง แต่จำนวน แต่ตัวชี้
ติดกันจำนวนดังกล่าวหรือไม่

391
00:17:27,079 --> 00:17:30,690
เพื่อให้เหมือนที่คุณจะด้าย
เข็มผ่านทั้งกลุ่มของผ้า

392
00:17:30,690 --> 00:17:32,950
สิ่งที่ผูกอย่างใด
เข้าด้วยกันในทำนองเดียวกันสามารถ

393
00:17:32,950 --> 00:17:35,550
เรามีคำแนะนำเป็น
เกิดมาโดยลูกศรที่นี่

394
00:17:35,550 --> 00:17:38,550
ชนิดของสานเข้าด้วยกัน
สี่เหลี่ยมแต่ละบุคคลเหล่านี้

395
00:17:38,550 --> 00:17:41,780
โดยมีประสิทธิภาพการใช้ตัวชี้
ถัดจากแต่ละหมายเลขที่

396
00:17:41,780 --> 00:17:46,065
ชี้ไปที่บางหมายเลขถัดไปที่
ชี้ไปในทางกลับกันบางจำนวนต่อไปหรือไม่

397
00:17:46,065 --> 00:17:47,940
ดังนั้นในคำอื่น ๆ สิ่ง
ถ้าเราต้องการจริง

398
00:17:47,940 --> 00:17:49,820
ในการดำเนินการบางอย่างเช่นนี้ได้อย่างไร

399
00:17:49,820 --> 00:17:53,610
ดี แต่น่าเสียดายที่รูปสี่เหลี่ยมเหล่านี้
ที่หนึ่งอย่างน้อยกับ 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
และอื่น ๆ เหล่านี้จะไม่มีอีกต่อไป
สแควร์มีความสุขกับตัวเลขเดียว

401
00:17:57,040 --> 00:17:59,960
ด้านล่างรูปสี่เหลี่ยมผืนผ้า
ด้านล่าง 9 ตัวอย่างเช่น

402
00:17:59,960 --> 00:18:04,330
แสดงให้เห็นถึงสิ่งที่ควร
เป็นตัวชี้ 32 บิต

403
00:18:04,330 --> 00:18:09,460
ตอนนี้ฉันยังไม่ทราบชนิดของข้อมูลใด ๆ
ใน C ที่ช่วยให้คุณไม่เพียง แต่ int

404
00:18:09,460 --> 00:18:11,630
แต่ชี้ไปโดยสิ้นเชิง

405
00:18:11,630 --> 00:18:15,020
>> ดังนั้นสิ่งที่เป็นวิธีแก้ปัญหาถ้าเราต้องการ
คิดค้นคำตอบของเราเองในการนี​​้หรือไม่?

406
00:18:15,020 --> 00:18:15,760
ใช่?

407
00:18:15,760 --> 00:18:16,640
>> ผู้ชม: [ไม่ได้ยิน]

408
00:18:16,640 --> 00:18:17,360
>> เดวิดเจลัน: มีอะไรที่?

409
00:18:17,360 --> 00:18:17,880
>> ผู้ชม: โครงสร้างใหม่

410
00:18:17,880 --> 00:18:19,590
>> เดวิดเจลัน: ใช่ดังนั้นทำไม
เราไม่สร้างโครงสร้างใหม่

411
00:18:19,590 --> 00:18:20,920
หรือใน C struct?

412
00:18:20,920 --> 00:18:25,990
เราได้เห็น structs ก่อนถ้าสั้น ๆ
ที่เราจัดการกับโครงสร้างของนักเรียน

413
00:18:25,990 --> 00:18:27,780
เช่นนี้ที่มีชื่อและที่บ้าน

414
00:18:27,780 --> 00:18:31,980
ใน Pset 3 แหกคุกที่คุณใช้ทั้ง
พวงของ GRect structs-- และ Govals

415
00:18:31,980 --> 00:18:34,810
Stanford ที่สร้างขึ้นเพื่อ
ข้อมูลกลุ่มเข้าด้วยกัน

416
00:18:34,810 --> 00:18:38,580
ดังนั้นสิ่งที่ถ้าเราใช้เวลานี้ความคิดเดียวกันของ
คำหลัก "typedef" และ "struct"

417
00:18:38,580 --> 00:18:42,890
และแล้วสิ่งที่นักศึกษาที่เฉพาะเจาะจงบางอย่าง
และพัฒนาให้เป็นดังต่อไปนี้

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- และโหนดเป็น
เพียงวิทยาการคอมพิวเตอร์ทั่วไปมาก

419
00:18:46,210 --> 00:18:49,980
คำบางสิ่งบางอย่างในโครงสร้างข้อมูล
ภาชนะในโครงสร้างข้อมูล

420
00:18:49,980 --> 00:18:53,900
โหนดฉันเรียกร้องเป็นไปได้
n int ตรงไปตรงมาโดยสิ้นเชิง

421
00:18:53,900 --> 00:18:58,810
และแล้วความลับเล็ก ๆ น้อย ๆ ,
บรรทัดที่สองนี้ struct โหนด * ต่อไป

422
00:18:58,810 --> 00:19:01,300
แต่ในแง่ทางเทคนิคน้อยกว่า
สิ่งที่เป็นบรรทัดที่สองว่า

423
00:19:01,300 --> 00:19:02,980
ของรหัสภายในวงเล็บปีกกา?

424
00:19:02,980 --> 00:19:03,737
ใช่?

425
00:19:03,737 --> 00:19:04,851
>> ผู้ชม: [ไม่ได้ยิน]

426
00:19:04,851 --> 00:19:06,600
เดวิดเจลัน:
ตัวชี้ไปยังโหนดอื่น

427
00:19:06,600 --> 00:19:09,910
เพื่อให้เป็นที่ยอมรับไวยากรณ์ลับเล็ก ๆ น้อย ๆ

428
00:19:09,910 --> 00:19:13,250
แต่ถ้าคุณอ่านมันอย่างแท้จริง
ต่อไปคือชื่อของตัวแปร

429
00:19:13,250 --> 00:19:14,410
เป็นประเภทของข้อมูลอะไร

430
00:19:14,410 --> 00:19:18,206
มันเป็น verbose น้อยเวลานี้
แต่มันก็เป็นประเภทโหนด struct *

431
00:19:18,206 --> 00:19:22,960
ทุกครั้งที่เราได้เห็นสิ่งที่ดาวที่
หมายความว่ามันเป็นตัวชี้ไปยังชนิดข้อมูลที่

432
00:19:22,960 --> 00:19:26,810
ดังนั้นต่อไปคือเห็นได้ชัด
ตัวชี้ไปยังโหนด struct

433
00:19:26,810 --> 00:19:28,310
>> ตอนนี้สิ่งที่เป็นโหนด struct?

434
00:19:28,310 --> 00:19:31,044
ดีสังเกตเห็นคุณเห็นเหล่านั้น
คำเดียวกันที่ด้านบนขวา

435
00:19:31,044 --> 00:19:33,960
และแน่นอนคุณยังเห็นคำว่า
"โหนด" ลงที่นี่ที่ด้านล่างซ้าย

436
00:19:33,960 --> 00:19:35,640
และนี้เป็นจริงเพียงแค่ความสะดวกสบาย

437
00:19:35,640 --> 00:19:39,930
ขอให้สังเกตว่าในความหมายของเรานักเรียน
มีคำว่า "นักเรียน" เพียงครั้งเดียว

438
00:19:39,930 --> 00:19:42,510
และนั่นเป็นเพราะนักเรียน
วัตถุที่เป็นตัวเองไม่ได้อ้างอิง

439
00:19:42,510 --> 00:19:45,340
ไม่มีอะไรภายในของนักเรียนเป็น
ที่ต้องการให้ชี้ไปที่นักเรียนคนอื่น

440
00:19:45,340 --> 00:19:45,610
persay

441
00:19:45,610 --> 00:19:47,630
ที่จะมีการจัดเรียงของ
แปลกในโลกจริง

442
00:19:47,630 --> 00:19:50,880
>> แต่ด้วยโหนดในการเชื่อมโยง
รายการที่เราทำต้องการโหนด

443
00:19:50,880 --> 00:19:53,970
จะอ้างอิงกับวัตถุที่คล้ายกัน

444
00:19:53,970 --> 00:19:57,900
และเพื่อให้สังเกตเห็นความเปลี่ยนแปลงที่นี่ไม่ได้
เพียงแค่สิ่งที่อยู่ภายในวงเล็บปีกกา

445
00:19:57,900 --> 00:20:00,800
แต่เราจะเพิ่มคำว่า "โหนด"
ที่ด้านบนเช่นเดียวกับที่

446
00:20:00,800 --> 00:20:02,930
เพิ่มที่ด้านล่าง
แทน "นักเรียน".

447
00:20:02,930 --> 00:20:06,000
และนี่เป็นเพียงรายละเอียดทางเทคนิค
เพื่อให้อีกครั้งโครงสร้างข้อมูลของคุณ

448
00:20:06,000 --> 00:20:11,380
สามารถเป็นตัวอ้างอิงเพื่อให้
โหนดสามารถชี้ไปยังอีกโหนดดังกล่าว

449
00:20:11,380 --> 00:20:13,840
>> ดังนั้นสิ่งนี้เป็นที่สุด
จะหมายถึงสำหรับเรา

450
00:20:13,840 --> 00:20:17,560
ดีหนึ่งสิ่งนี้ภายใน
เป็นเนื้อหาของโหนดของเรา

451
00:20:17,560 --> 00:20:19,360
สิ่งนี้ขึ้นที่นี่
ขวาบนเป็นเพียงเพื่อให้

452
00:20:19,360 --> 00:20:20,860
นั้นอีกครั้งเราสามารถอ้างกับตัวเอง

453
00:20:20,860 --> 00:20:23,401
และแล้วสิ่งที่นอกสุด,
แม้ว่าโหนดเป็นคำใหม่

454
00:20:23,401 --> 00:20:25,500
บางทีก็ยังคง
เช่นเดียวกับนักเรียนและสิ่งที่

455
00:20:25,500 --> 00:20:27,520
เป็นใต้เครื่องดูดควันใน SPL

456
00:20:27,520 --> 00:20:31,095
>> ดังนั้นถ้าตอนนี้เราอยากจะเริ่มต้น
การดำเนินรายการที่เชื่อมโยงนี้

457
00:20:31,095 --> 00:20:33,220
วิธีการที่เราอาจจะแปล
บางสิ่งบางอย่างเช่นนี้จะรหัส?

458
00:20:33,220 --> 00:20:35,350
ดีขอเพียงแค่เห็น
ตัวอย่างของโปรแกรมที่

459
00:20:35,350 --> 00:20:36,840
จริงใช้รายการที่เชื่อมโยง

460
00:20:36,840 --> 00:20:40,870
ในรหัสการกระจายของวันนี้
เป็นโปรแกรมที่เรียกว่ารายชื่อศูนย์

461
00:20:40,870 --> 00:20:44,980
และถ้าฉันทำงานนี้ฉันสร้างซุปเปอร์
GUI ง่ายอินเตอร์เฟซผู้ใช้แบบกราฟิก,

462
00:20:44,980 --> 00:20:46,460
แต่มันเป็นความจริงเพียง printf

463
00:20:46,460 --> 00:20:50,930
และตอนนี้ฉันได้รับตัวเองไม่กี่เมนู
options-- ลบแทรกค้นหา

464
00:20:50,930 --> 00:20:51,750
และการสำรวจ

465
00:20:51,750 --> 00:20:52,630
และออกจาก

466
00:20:52,630 --> 00:20:55,970
เหล่านี้เป็นเพียงการดำเนินงานร่วมกันใน
โครงสร้างข้อมูลที่เรียกว่ารายการการเชื่อมโยง

467
00:20:55,970 --> 00:20:58,409
>> ตอนนี้ลบเป็นไปได้
ลบหมายเลขจากรายการ

468
00:20:58,409 --> 00:21:00,200
แทรกที่จะเพิ่ม
จำนวนในรายการ

469
00:21:00,200 --> 00:21:02,181
การค้นหาจะไปดู
สำหรับจำนวนในรายการ

470
00:21:02,181 --> 00:21:04,930
และการสำรวจเป็นเพียงวิธีแฟนซี
พูดว่าเดินผ่านรายการ

471
00:21:04,930 --> 00:21:06,245
พิมพ์ออกมา แต่ที่มัน

472
00:21:06,245 --> 00:21:07,720
อย่าเปลี่ยนในทางใดทางหนึ่ง

473
00:21:07,720 --> 00:21:08,570
>> ดังนั้นเรามาลองนี้

474
00:21:08,570 --> 00:21:10,160
ให้เป็นไปข้างหน้าและพิมพ์ 2

475
00:21:10,160 --> 00:21:12,710
แล้วฉันจะไป
ใส่หมายเลขที่บอกว่า 9

476
00:21:12,710 --> 00:21:13,620
ใส่

477
00:21:13,620 --> 00:21:17,480
และตอนนี้โปรแกรมของฉันเป็นเพียง
โปรแกรมที่จะบอกว่ารายการนี​​้ 9

478
00:21:17,480 --> 00:21:20,190
ตอนนี้ถ้าผมไปข้างหน้าและ
ไม่ใส่อีกครั้งให้

479
00:21:20,190 --> 00:21:23,680
ฉันไปข้างหน้าและซูมออกและพิมพ์ 17

480
00:21:23,680 --> 00:21:25,770
ตอนนี้รายชื่อของฉันคือ 9 แล้ว 17

481
00:21:25,770 --> 00:21:27,750
ถ้าฉันจะใส่อีกครั้งให้ข้ามอย่างใดอย่างหนึ่ง

482
00:21:27,750 --> 00:21:32,400
แทน 22, เป็นต่อรูปเราได้
รับการมองหาที่นี่ให้ฉันกระโดดไปข้างหน้า

483
00:21:32,400 --> 00:21:34,630
และใส่ 26 ต่อไป

484
00:21:34,630 --> 00:21:36,230
ดังนั้นฉันจะต้องพิมพ์ 26

485
00:21:36,230 --> 00:21:37,755
รายการเป็นตามที่ผมคาดหวัง

486
00:21:37,755 --> 00:21:40,630
แต่ตอนนี้เพียงเพื่อดูว่ารหัสนี้
เป็นไปได้ที่มีความยืดหยุ่นให้ฉันตอนนี้

487
00:21:40,630 --> 00:21:43,520
22 ชนิดซึ่งอย่างน้อย
แนวคิดถ้าเรา

488
00:21:43,520 --> 00:21:46,520
รักษานี้แยกซึ่งเป็นที่แน่นอน
จะเป็นเป้าหมายอื่นในขณะนี้

489
00:21:46,520 --> 00:21:48,690
ควรจะไปในระหว่างวันที่ 17 และ 26

490
00:21:48,690 --> 00:21:50,270
ดังนั้นผมจึงกด Enter

491
00:21:50,270 --> 00:21:51,380
อันที่จริงที่ทำงาน

492
00:21:51,380 --> 00:21:54,950
และดังนั้นตอนนี้ให้ฉันใส่
ที่ผ่านมาต่อภาพที่ 34

493
00:21:54,950 --> 00:21:55,450
>> ขวาทั้งหมด

494
00:21:55,450 --> 00:21:58,980
ดังนั้นสำหรับตอนนี้ให้ฉันระบุว่า
ลบและการสำรวจและค้นหาทำ

495
00:21:58,980 --> 00:21:59,760
ในความเป็นจริงการทำงาน

496
00:21:59,760 --> 00:22:04,180
ในความเป็นจริงถ้าฉันจะเรียกใช้การค้นหาให้
ค้นหาหมายเลข 22, ใส่

497
00:22:04,180 --> 00:22:05,010
พบ 22

498
00:22:05,010 --> 00:22:07,580
เพื่อให้เป็นสิ่งนี้
โปรแกรมรายชื่อศูนย์ไม่

499
00:22:07,580 --> 00:22:10,230
>> แต่สิ่งที่เป็นจริงที่เกิด
ว่าการดำเนินการนี​​้

500
00:22:10,230 --> 00:22:14,530
ดีแรกที่ผมอาจจะมีและแน่นอน
ผมมีไฟล์ที่เรียกว่า list0.h

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
และที่ใดที่หนึ่งในนั้นคือ
บรรทัด typedef โหนด struct,

503
00:22:20,690 --> 00:22:24,850
แล้วฉันมีวงเล็บปีกกาของฉัน int n และ
แล้ว struct-- สิ่งที่เป็นความหมายหรือไม่

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
โหนดโครงสร้างต่อไป

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
ดังนั้นเราจึงจำเป็นดาว

508
00:22:31,045 --> 00:22:33,420
ตอนนี้ในทางเทคนิคเราจะได้เป็น
นิสัยของการวาดภาพได้ที่นี่

509
00:22:33,420 --> 00:22:35,670
คุณอาจเห็นตำราและ
อ้างอิงออนไลน์ทำมันมี

510
00:22:35,670 --> 00:22:36,660
มันเป็นหน้าที่เทียบเท่า

511
00:22:36,660 --> 00:22:37,980
ในความเป็นจริงนี้เป็นเรื่องปกติน้อยมาก

512
00:22:37,980 --> 00:22:40,563
แต่ฉันจะมีความสอดคล้องกับสิ่งที่
เราทำครั้งสุดท้ายและจะทำเช่นนี้

513
00:22:40,563 --> 00:22:42,350
แล้วสุดท้ายที่ฉันจะทำเช่นนี้

514
00:22:42,350 --> 00:22:45,550
>> ดังนั้นในไฟล์ส่วนหัว
ที่ไหนสักแห่งใน list0.h

515
00:22:45,550 --> 00:22:49,200
ในวันนี้คือความหมาย struct นี้
และบางทีบางสิ่งอื่น ๆ

516
00:22:49,200 --> 00:22:52,580
ในขณะเดียวกันใน list0c มี
จะเป็นสิ่งที่ไม่กี่

517
00:22:52,580 --> 00:22:54,740
แต่เรากำลังจะไปเพียงแค่
เริ่มต้นและไม่จบนี้

518
00:22:54,740 --> 00:22:59,690
List0.h เป็นไฟล์ที่ฉันต้องการ
จะรวมอยู่ในแฟ้มของฉัน C

519
00:22:59,690 --> 00:23:03,910
แล้วในบางจุดฉัน
จะมี int, หลักเป็นโมฆะ

520
00:23:03,910 --> 00:23:06,530
แล้วฉันจะไป
มีบางสิ่งที่ต้องทำที่นี่

521
00:23:06,530 --> 00:23:10,620
ฉันยังจะมี
ต้นแบบเช่นโมฆะ, ค้นหา, int,

522
00:23:10,620 --> 00:23:13,610
n วัตถุประสงค์ที่มีในชีวิตก็คือ
เพื่อค้นหาองค์ประกอบ

523
00:23:13,610 --> 00:23:18,310
แล้วลงมาที่นี่ฉันเรียกร้องใน
รหัสของวันนี้เป็นโมฆะ, ค้นหา, int, n,

524
00:23:18,310 --> 00:23:21,020
ไม่มีอัฒภาค แต่เปิดวงเล็บปีกกา

525
00:23:21,020 --> 00:23:25,049
และตอนนี้ฉันต้องการที่จะค้นหาอย่างใด
สำหรับองค์ประกอบในรายการนี​​้

526
00:23:25,049 --> 00:23:27,340
แต่เราไม่ได้มีมากพอ
ข้อมูลบนหน้าจอยัง

527
00:23:27,340 --> 00:23:29,800
ฉันไม่ได้จริง
แสดงรายชื่อของตัวเอง

528
00:23:29,800 --> 00:23:33,070
ดังนั้นวิธีหนึ่งที่เราสามารถใช้
รายการที่เชื่อมโยงในโปรแกรม

529
00:23:33,070 --> 00:23:37,520
เป็นชนิดของฉันต้องการที่จะทำอะไรบางอย่าง
เช่นประกาศรายการที่เชื่อมโยงที่นี่

530
00:23:37,520 --> 00:23:40,520
สำหรับความเรียบง่ายผมจะทำให้
นี้ทั่วโลกแม้ว่าในเราทั่วไป

531
00:23:40,520 --> 00:23:41,645
ไม่ควรทำเช่นนี้มากเกินไป

532
00:23:41,645 --> 00:23:43,260
แต่มันจะง่ายตัวอย่างนี้

533
00:23:43,260 --> 00:23:45,890
ดังนั้นผมจึงต้องการที่จะประกาศ
รายการขึ้นเชื่อมโยงที่นี่

534
00:23:45,890 --> 00:23:47,010
ตอนนี้ฉันอาจจะทำเช่นนั้น?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> นี่คือภาพของรายการที่เชื่อมโยง

537
00:23:50,750 --> 00:23:53,030
และฉันไม่ได้จริงๆ
ทราบว่าในขณะนี้ว่า

538
00:23:53,030 --> 00:23:56,710
ฉันจะไปเกี่ยวกับการเป็นตัวแทนของ
หลายสิ่งหลายอย่างที่มีเพียงหนึ่ง

539
00:23:56,710 --> 00:23:58,040
ตัวแปรในหน่วยความจำ

540
00:23:58,040 --> 00:23:59,160
แต่คิดว่ากลับไปสักครู่

541
00:23:59,160 --> 00:24:00,830
ตลอดเวลาที่เราเคยมีนี้
สตริงซึ่งเราแล้ว

542
00:24:00,830 --> 00:24:02,913
เห็นจะเป็นอาร์เรย์ของ
ตัวละครซึ่งเราแล้ว

543
00:24:02,913 --> 00:24:05,740
เผยให้เห็นถึงเพียงแค่เป็นตัวชี้
กับตัวอักษรตัวแรก

544
00:24:05,740 --> 00:24:08,890
ในอาร์เรย์ของตัวอักษร
ที่สิ้นสุด null

545
00:24:08,890 --> 00:24:13,530
ดังนั้นโดยตรรกะที่และกับเรื่องนี้
ชนิดภาพของการเพาะความคิดของคุณ

546
00:24:13,530 --> 00:24:17,964
เราจำเป็นต้องเขียนสิ่งที่จริงในบ้านเรา
รหัสที่จะเป็นตัวแทนของรายการที่เชื่อมโยงหรือไม่

547
00:24:17,964 --> 00:24:21,130
เท่าไหร่ของข้อมูลนี้เราต้อง
ในการจับภาพในรหัส C คุณจะว่าอย่างไร

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
ใช่?

550
00:24:23,154 --> 00:24:24,738
>> ผู้ชม: เราต้องชี้ไปยังโหนด

551
00:24:24,738 --> 00:24:26,237
เดวิดเจลัน: ตัวชี้ไปยังโหนด

552
00:24:26,237 --> 00:24:29,320
โดยเฉพาะอย่างยิ่งที่โหนดจะของคุณ
สัญชาตญาณที่จะให้ตัวชี้ไปยัง?

553
00:24:29,320 --> 00:24:30,026
>> ผู้ชม: โหนดแรก

554
00:24:30,026 --> 00:24:31,942
>> เดวิดเจลัน: ใช่
อาจเป็นเพียงแค่ครั้งแรก

555
00:24:31,942 --> 00:24:34,030
และสังเกตเห็นครั้งแรก
โหนดเป็นรูปร่างที่แตกต่าง

556
00:24:34,030 --> 00:24:37,690
มันเป็นเพียงครึ่งหนึ่งของขนาดของ struct,
เพราะมันเป็นเรื่องจริงเพียงตัวชี้

557
00:24:37,690 --> 00:24:44,650
ดังนั้นสิ่งที่คุณจริงสามารถทำได้คือการประกาศ
รายการที่เชื่อมโยงไปเป็นชนิดโหนด *

558
00:24:44,650 --> 00:24:47,780
และขอเรียกมันเป็นครั้งแรก
และเริ่มต้นมันให้เป็นโมฆะ

559
00:24:47,780 --> 00:24:49,910
ดังนั้น null อีกครั้งเป็นมา
ในภาพที่นี่

560
00:24:49,910 --> 00:24:53,620
ไม่เพียง แต่จะใช้เป็นโมฆะเช่นพิเศษ
ค่าตอบแทนสำหรับสิ่งที่ต้องการ GetString

561
00:24:53,620 --> 00:24:57,770
และ malloc, null ยังเป็นศูนย์
ตัวชี้ขาดของตัวชี้ที่

562
00:24:57,770 --> 00:24:58,430
ถ้าคุณจะ

563
00:24:58,430 --> 00:25:00,309
มันก็ไม่มีความหมายอะไรเป็นอีกที่นี่

564
00:25:00,309 --> 00:25:02,100
ตอนแรกที่ผมจะได้
เรียกว่าอะไรที่นี้

565
00:25:02,100 --> 00:25:04,200
ฉันจะได้เรียกมันว่า "รายการ"
หรือจำนวนของสิ่งอื่นใด

566
00:25:04,200 --> 00:25:06,960
แต่ฉันเรียกมันว่า "ครั้งแรก" เพื่อให้
เส้นมันขึ้นกับภาพนี้

567
00:25:06,960 --> 00:25:10,280
ดังนั้นเช่นเดียวสตริงสามารถแสดง
กับที่อยู่ของไบต์แรกของมัน

568
00:25:10,280 --> 00:25:11,280
เพื่อให้สามารถเชื่อมโยงรายชื่อ

569
00:25:11,280 --> 00:25:13,480
และเราจะเห็นข้อมูลอื่น ๆ
โครงสร้างจะเป็นตัวแทน

570
00:25:13,480 --> 00:25:16,700
ที่มีเพียงหนึ่งตัวชี้
ลูกศร 32 บิตชี้

571
00:25:16,700 --> 00:25:18,740
ที่โหนดแรกมากในโครงสร้าง

572
00:25:18,740 --> 00:25:20,340
>> แต่ตอนนี้เรามาคาดว่าจะมีปัญหา

573
00:25:20,340 --> 00:25:23,230
ถ้าฉันเพียงความทรงจำ
ในโปรแกรมของฉันอยู่

574
00:25:23,230 --> 00:25:27,220
ของโหนดแรกแรก
สี่เหลี่ยมผืนผ้าในโครงสร้างข้อมูลนี้

575
00:25:27,220 --> 00:25:31,760
สิ่งที่ได้ดีกว่าเป็นกรณีที่เกี่ยวกับ
การดำเนินการของส่วนที่เหลือของรายการของฉันได้อย่างไร

576
00:25:31,760 --> 00:25:35,820
สิ่งที่เป็นรายละเอียดสำคัญที่จะ
เพื่อให้แน่ใจว่านี้ใช้งานได้จริง?

577
00:25:35,820 --> 00:25:39,250
และ "ใช้งานได้จริง" ผม
หมายถึงมากเช่นสตริง

578
00:25:39,250 --> 00:25:42,180
ช่วยให้เราไปจากตัวอักษรตัวแรก
ในชื่อ Davin เพื่อที่สอง

579
00:25:42,180 --> 00:25:44,755
สามเพื่อ
ที่สี่จะสิ้นสุดมาก

580
00:25:44,755 --> 00:25:47,880
ทำอย่างไรเราจะรู้ว่าเมื่อเราอยู่ในตอนท้าย
ของรายการที่เชื่อมโยงที่มีลักษณะเช่นนี้หรือไม่?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
เมื่อมันเป็นโมฆะ

583
00:25:50,660 --> 00:25:53,640
และฉันได้เป็นตัวแทนของการจัดเรียงของเช่นนี้
เช่นวิศวกรอาจไฟฟ้า

584
00:25:53,640 --> 00:25:56,420
กับดินเล็ก ๆ น้อย ๆ
สัญลักษณ์แปลก ๆ

585
00:25:56,420 --> 00:25:58,246
แต่นั่นก็หมายความว่าโมฆะในกรณีนี้

586
00:25:58,246 --> 00:26:00,370
คุณสามารถวาดมันหมายเลขใด ๆ
วิธี แต่ผู้เขียนคนนี้

587
00:26:00,370 --> 00:26:02,800
ที่เกิดขึ้นในการใช้สัญลักษณ์นี้ที่นี่

588
00:26:02,800 --> 00:26:06,260
>> ดังนั้นตราบใดที่เรากำลังคบ
ทั้งหมดของโหนดเหล่านี้ร่วมกัน

589
00:26:06,260 --> 00:26:08,600
เพียงความทรงจำที่
คนแรกเป็นเวลานาน

590
00:26:08,600 --> 00:26:11,760
ในขณะที่เราใส่สัญลักษณ์พิเศษที่
โหนดสุดท้ายในรายการ

591
00:26:11,760 --> 00:26:15,130
และเราจะใช้โมฆะเพราะนั่นคือ
สิ่งที่เรามีให้กับเรา

592
00:26:15,130 --> 00:26:16,480
รายการนี​​้เสร็จสมบูรณ์

593
00:26:16,480 --> 00:26:20,190
และแม้ว่าฉันเท่านั้นที่ให้คุณได้ชี้ไปยัง
องค์ประกอบแรกคุณ, โปรแกรมเมอร์

594
00:26:20,190 --> 00:26:22,486
แน่นอนสามารถเข้าถึงส่วนที่เหลือของมัน

595
00:26:22,486 --> 00:26:24,360
แต่ขอให้จิตใจของคุณ
เดินนิด ๆ หน่อย ๆ

596
00:26:24,360 --> 00:26:26,140
ถ้าพวกเขาไม่ได้อยู่แล้ว
ค่อนข้าง wandered-- สิ่งที่

597
00:26:26,140 --> 00:26:28,723
จะเป็นเวลาทำงานของ
หาอะไรในรายการนี​​้หรือไม่?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
ประณามมันก็โอใหญ่ของ n,
ซึ่งไม่เลวในความเป็นธรรม

600
00:26:33,470 --> 00:26:34,800
แต่มันเป็นเส้นตรง

601
00:26:34,800 --> 00:26:37,980
เราได้รับค่าคุณลักษณะสิ่งที่
ของอาร์เรย์โดยการเคลื่อนย้ายมากขึ้น

602
00:26:37,980 --> 00:26:43,130
ต่อภาพของแบบไดนามิกนี้
ทอด้วยกันหรือโหนดที่เชื่อมโยง?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
เราได้รับการเข้าถึงแบบสุ่ม

605
00:26:46,687 --> 00:26:48,770
อาเรย์เป็นสิ่งที่ดีเพราะ
ทุกอย่างทางคณิตศาสตร์

606
00:26:48,770 --> 00:26:50,340
กลับไปกลับไปกลับไปกลับ

607
00:26:50,340 --> 00:26:52,370
แม้ว่าภาพนี้
ดูสวยและแม้แต่

608
00:26:52,370 --> 00:26:55,830
แม้ว่ามันจะดูเหมือนว่าโหนดเหล่านี้
มีระยะห่างออกจากกันเป็นอย่างดีในความเป็นจริง

609
00:26:55,830 --> 00:26:56,830
พวกเขาอาจจะที่ใดก็ได้

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99 เหล่านี้
โหนดอาจจะเป็นที่ใดก็ได้

611
00:27:01,590 --> 00:27:05,960
เพราะ malloc ไม่จัดสรรหน่วยความจำ
จากกอง แต่ที่ใดก็ได้ในกอง

612
00:27:05,960 --> 00:27:09,080
คุณไม่จำเป็นต้องรู้ว่ามันเป็น
จะเป็นหลังการสำรองข้อมูล

613
00:27:09,080 --> 00:27:12,460
และเพื่อให้ภาพในความเป็นจริงนี้
จะไม่ได้ค่อนข้างสวยนี้

614
00:27:12,460 --> 00:27:16,140
>> ดังนั้นมันจะใช้เวลาบิตของ
ทำงานที่จะใช้ฟังก์ชั่นนี้

615
00:27:16,140 --> 00:27:17,880
จึงขอใช้ค้นหาขณะนี้

616
00:27:17,880 --> 00:27:20,250
และเราจะเห็นชนิดของ
วิธีที่ฉลาดของการทำเช่นนี้

617
00:27:20,250 --> 00:27:24,660
ดังนั้นหากผมมีฟังก์ชันการค้นหาและ
ฉันได้รับตัวแปรจำนวนเต็ม n

618
00:27:24,660 --> 00:27:28,490
ที่จะมองหาฉันจำเป็นต้องทราบ
ไวยากรณ์ใหม่สำหรับการมองภายใน

619
00:27:28,490 --> 00:27:32,400
ของโครงสร้างที่
ชี้ไปที่การหา n

620
00:27:32,400 --> 00:27:33,210
ดังนั้นขอให้ทำเช่นนี้

621
00:27:33,210 --> 00:27:36,030
>> ดังนั้นก่อนที่ฉันจะไป
ข้างหน้าและประกาศโหนด *

622
00:27:36,030 --> 00:27:39,400
และฉันจะเรียกมันว่า
ตัวชี้เพียงโดยการประชุม

623
00:27:39,400 --> 00:27:41,710
และฉันจะเริ่มต้นมันไปก่อน

624
00:27:41,710 --> 00:27:43,770
และตอนนี้ฉันสามารถทำเช่นนี้
ในหลายวิธี

625
00:27:43,770 --> 00:27:45,436
แต่ผมจะใช้วิธีการที่พบบ่อย

626
00:27:45,436 --> 00:27:50,180
ในขณะที่ตัวชี้ไม่เท่ากับ
null และที่ไวยากรณ์ที่ถูกต้อง

627
00:27:50,180 --> 00:27:54,550
และมันก็หมายความว่าทำต่อไปเพื่อให้
ตราบใดที่คุณไม่ได้ชี้ไปที่อะไร

628
00:27:54,550 --> 00:27:55,800
สิ่งที่ฉันต้องการจะทำอย่างไร

629
00:27:55,800 --> 00:28:01,939
>> หากตัวชี้จุด n ให้ฉันกลับมา
นั้น equals-- เท่ากับอะไร

630
00:28:01,939 --> 00:28:03,105
สิ่งที่มีค่าที่ฉันกำลังมองหาอยู่

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
n จริงที่ถูกส่งผ่านไปใน

633
00:28:06,590 --> 00:28:09,020
ดังนั้นนี่คือคุณสมบัติอื่น
ของซีและหลายภาษา

634
00:28:09,020 --> 00:28:13,705
แม้ว่าโหนดโครงสร้างที่เรียกว่า
n มีค่าถูกต้องตามกฎหมายทั้งหมด

635
00:28:13,705 --> 00:28:17,530
นอกจากนี้ยังมีการโต้แย้งในท้องถิ่น
หรือที่เรียกว่าตัวแปร n

636
00:28:17,530 --> 00:28:20,085
เพราะแม้เราด้วย
ดวงตาของมนุษย์สามารถแยกแยะความแตกต่าง

637
00:28:20,085 --> 00:28:22,087
ที่ n นี้สันนิษฐานว่า
แตกต่างจาก n นี้

638
00:28:22,087 --> 00:28:23,420
เพราะไวยากรณ์ที่แตกต่างกัน

639
00:28:23,420 --> 00:28:26,211
คุณมีจุดและตัวชี้
ในขณะที่หนึ่งนี้มีไม่มีสิ่งนั้น

640
00:28:26,211 --> 00:28:27,290
ดังนั้นนี่คือตกลง

641
00:28:27,290 --> 00:28:29,120
ที่ตกลงจะเรียกพวกเขาในสิ่งเดียวกัน

642
00:28:29,120 --> 00:28:32,380
>> ถ้าผมคุณจะพบนี้ฉัน
จะต้องการที่จะทำบางสิ่งบางอย่าง

643
00:28:32,380 --> 00:28:35,000
เช่นประกาศว่าเราพบ n

644
00:28:35,000 --> 00:28:37,930
และเราจะออกจากที่เป็น
แสดงความคิดเห็นหรือ pseudocode รหัส

645
00:28:37,930 --> 00:28:40,190
อื่น ๆ และนี่คือ
ส่วนที่น่าสนใจสิ่งที่

646
00:28:40,190 --> 00:28:47,320
ฉันต้องการจะทำอย่างไรถ้าโหนดปัจจุบัน
ไม่ได้มี n ที่ฉันดูแลเกี่ยวกับ?

647
00:28:47,320 --> 00:28:50,700
ผมไม่ประสบความสำเร็จต่อไปได้อย่างไร

648
00:28:50,700 --> 00:28:53,710
ถ้านิ้วของฉันที่
ขณะที่ PTR และก็

649
00:28:53,710 --> 00:28:55,920
ชี้ไปที่สิ่งที่
ก่อนจะชี้ไปที่

650
00:28:55,920 --> 00:28:59,290
ฉันจะย้ายนิ้วของฉัน
ไปยังโหนดถั​​ดไปในรหัส?

651
00:28:59,290 --> 00:29:01,915
ดีสิ่งที่เป็นเกล็ดขนมปังที่เรากำลัง
จะทำตามในกรณีนี้หรือไม่?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
ผู้ชม: [ไม่ได้ยิน]

654
00:29:04,380 --> 00:29:05,630
เดวิดเจลัน: ใช่ดังนั้นต่อไป

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
ดังนั้นถ้าฉันกลับไปของฉัน
รหัสที่นี่จริงฉัน

657
00:29:09,824 --> 00:29:12,990
จะไปข้างหน้าและบอกว่าตัวชี้ที่
เป็นเพียงชั่วคราว variable-- มัน

658
00:29:12,990 --> 00:29:15,320
ชื่อแปลก PTR แต่
ก็เช่นเดียวกับ temp--

659
00:29:15,320 --> 00:29:19,234
ฉันจะตั้งตัวชี้
เท่ากับสิ่งที่ชี้ค่าเท่าใด

660
00:29:19,234 --> 00:29:22,150
และครั้งนี้เป็นไปได้
รถเล็ก ๆ น้อย ๆ สำหรับจุด moment-- ต่อไป

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
ในคำอื่น ๆ ฉันจะใช้เวลาของฉัน
นิ้วที่ชี้ไปที่โหนดนี้

663
00:29:26,550 --> 00:29:31,247
ที่นี่และฉันจะบอกว่าคุณรู้ว่า
สิ่งที่จะดูที่เขตข้อมูลถัดไป

664
00:29:31,247 --> 00:29:33,330
และเลื่อนนิ้วของคุณไปยัง
สิ่งที่มันชี้ไปที่

665
00:29:33,330 --> 00:29:35,163
และสิ่งนี้เป็นไปได้
ซ้ำซ้ำซ้ำ

666
00:29:35,163 --> 00:29:37,630
แต่เมื่อไม่นิ้วของฉัน
หยุดการทำอะไรที่ทั้งหมดหรือไม่

667
00:29:37,630 --> 00:29:40,095
เร็วที่สุดเท่าที่สิ่งที่บรรทัดของรหัสลูกมีอะไรบ้าง?

668
00:29:40,095 --> 00:29:40,970
ผู้ชม: [ไม่ได้ยิน]

669
00:29:40,970 --> 00:29:43,060
เดวิดเจลัน: ถ้าจุดในขณะที่
ชี้ไม่เท่ากับโมฆะ

670
00:29:43,060 --> 00:29:44,900
ในบางจุดที่นิ้วของฉัน
จะชี้ไปที่ null

671
00:29:44,900 --> 00:29:47,070
และฉันจะตระหนักถึง
นั่นคือจุดสิ้นสุดของรายการนี​​้

672
00:29:47,070 --> 00:29:48,910
ตอนนี้เป็นเพียงเล็กน้อย
โกหกสีขาวสำหรับความเรียบง่าย

673
00:29:48,910 --> 00:29:51,580
แต่กลับกลายเป็นว่าแม้ว่าเรา
เพียงแค่เรียนรู้สัญกรณ์จุดนี้

674
00:29:51,580 --> 00:29:55,220
สำหรับโครงสร้างตัวชี้ไม่ struct

675
00:29:55,220 --> 00:29:56,580
PTR คืออะไร?

676
00:29:56,580 --> 00:29:58,350
เพียงเพื่อให้ nitpicky มากขึ้น

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
มันเป็นตัวชี้ไปยังโหนด

679
00:30:01,360 --> 00:30:03,120
มันไม่ได้เป็นโหนดตัวเอง

680
00:30:03,120 --> 00:30:06,650
ถ้าผมมีดาวที่นี่ชี้
absolutely-- ก็โหนด

681
00:30:06,650 --> 00:30:08,650
นี้เป็นเหมือนหนึ่งสัปดาห์
การประกาศตัวแปร

682
00:30:08,650 --> 00:30:10,120
แม้คำว่า "โหนด" เป็นของใหม่

683
00:30:10,120 --> 00:30:13,860
>> แต่ทันทีที่เราแนะนำ
ดาวก็ตอนนี้ตัวชี้ไปยังโหนด

684
00:30:13,860 --> 00:30:17,960
และโชคร้ายที่คุณไม่สามารถใช้
สัญกรณ์จุดสำหรับตัวชี้

685
00:30:17,960 --> 00:30:21,070
คุณต้องใช้ลูกศร
สัญกรณ์ที่ยอดเยี่ยม

686
00:30:21,070 --> 00:30:23,470
เป็นครั้งแรกที่ชิ้นส่วนใด ๆ
ของไวยากรณ์มีลักษณะใช้งานง่าย

687
00:30:23,470 --> 00:30:25,245
นี้อย่างแท้จริงมีลักษณะเหมือนลูกศร

688
00:30:25,245 --> 00:30:26,370
และเพื่อให้เป็นสิ่งที่ดี

689
00:30:26,370 --> 00:30:28,995
และลงมาที่นี่อย่างแท้จริง
มีลักษณะเหมือนลูกศร

690
00:30:28,995 --> 00:30:31,870
ดังนั้นผมคิดว่าเป็น la-- ที่ฉันทำไม่ได้
คิดว่าฉันเกินกระทำตรงนี้ฉัน

691
00:30:31,870 --> 00:30:34,120
คิดว่าเป็นชิ้นใหม่ล่าสุด
ของไวยากรณ์ที่เรากำลังจะไปดู

692
00:30:34,120 --> 00:30:36,500
และโชคดีที่มันเป็นจริง
เล็ก ๆ น้อย ๆ ได้ง่ายขึ้น

693
00:30:36,500 --> 00:30:40,090
>> ตอนนี้สำหรับบรรดาของคุณที่
อาจจะชอบวิธีการแบบเก่าที่

694
00:30:40,090 --> 00:30:42,550
คุณยังสามารถใช้สัญกรณ์จุด

695
00:30:42,550 --> 00:30:45,380
แต่เป็นต่อวันจันทร์
การสนทนาครั้งแรกที่เรา

696
00:30:45,380 --> 00:30:50,530
จำเป็นต้องไปที่นั่นไปที่
อยู่แล้วเข้าถึงข้อมูล

697
00:30:50,530 --> 00:30:51,897
ดังนั้นนี้ยังเป็นที่ถูกต้อง

698
00:30:51,897 --> 00:30:53,730
และตรงไปตรงนี้เป็น
เล็ก ๆ น้อย ๆ อวดความรู้มากขึ้น

699
00:30:53,730 --> 00:30:56,530
คุณอย่างแท้จริงกล่าวว่า dereference
ตัวชี้และไปที่นั่น

700
00:30:56,530 --> 00:30:59,320
แล้วคว้า .n ฟิลด์ที่เรียกว่า n

701
00:30:59,320 --> 00:31:01,370
แต่ตรงไปตรงมาไม่มีใครต้องการ
ที่จะพิมพ์หรืออ่านข้อความนี้

702
00:31:01,370 --> 00:31:03,620
และเพื่อโลกที่คิดค้น
สัญกรณ์ลูกศรที่

703
00:31:03,620 --> 00:31:06,980
เป็นเทียบเท่าเหมือนกัน
มันเป็นเพียงน้ำตาล syntactic

704
00:31:06,980 --> 00:31:10,570
ดังนั้นวิธีที่จินตนาการของคำพูดนี้
ดูดีหรือมีลักษณะที่เรียบง่าย

705
00:31:10,570 --> 00:31:12,296
>> ดังนั้นตอนนี้ฉันกำลังจะไปทำสิ่งอื่น ๆ ที่หนึ่ง

706
00:31:12,296 --> 00:31:15,420
ฉันจะบอกว่า "หยุด" เมื่อฉันได้
พบว่ามันดังนั้นผมจึงไม่ให้มองหามัน

707
00:31:15,420 --> 00:31:17,620
แต่นี้เป็นส่วนสำคัญ
ฟังก์ชั่นการค้นหา

708
00:31:17,620 --> 00:31:21,710
แต่มันง่ายมากที่ใน
ท้ายที่สุดไม่ได้ที่จะเดินผ่านรห​​ัส

709
00:31:21,710 --> 00:31:25,570
นี้คือการดำเนินการอย่างเป็นทางการแน่นอน
ของการค้นหาในรหัสการกระจายของวันนี้

710
00:31:25,570 --> 00:31:30,530
ผมกล้าพูดแทรกที่ไม่ได้
สนุกสนานโดยเฉพาะอย่างยิ่งที่จะเดินผ่าน

711
00:31:30,530 --> 00:31:33,180
สายตาไม่เป็นลบได้
แม้ว่าในตอนท้ายของวันที่

712
00:31:33,180 --> 00:31:35,460
พวกเขาต้มลงไปอย่างเป็นธรรม
วิเคราะห์พฤติกรรมง่าย

713
00:31:35,460 --> 00:31:36,330
>> ดังนั้นขอให้ทำเช่นนี้

714
00:31:36,330 --> 00:31:39,250
ถ้าคุณจะขบขันผมมาที่นี่ผมได้
นำพวงของลูกความเครียด

715
00:31:39,250 --> 00:31:40,620
ฉันนำพวงของตัวเลข

716
00:31:40,620 --> 00:31:46,562
และสามารถที่เราได้รับอาสาสมัครเพียงไม่กี่
เพื่อเป็นตัวแทนของ 9, 17, 20, 22, 29, และ 34?

717
00:31:46,562 --> 00:31:48,270
ทุกคนเพื่อเป็นหลัก
คนที่นี่ในวันนี้

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
นั่นคือหนึ่งสองสาม
สี่ห้าหกคน

720
00:31:52,760 --> 00:31:55,740
และฉันได้รับการร้องขอให้ go-- เห็นไม่มี
หนึ่งในด้านหลังยกมือของพวกเขา

721
00:31:55,740 --> 00:32:01,910
ตกลงหนึ่งสองสามสี่
five-- ให้ฉันโหลด balance-- หก

722
00:32:01,910 --> 00:32:03,051
ตกลงคุณหกมาขึ้น

723
00:32:03,051 --> 00:32:04,050
เราจะต้องให้คนอื่น ๆ

724
00:32:04,050 --> 00:32:05,460
เราได้นำลูกความเครียดเพิ่ม

725
00:32:05,460 --> 00:32:08,200
และถ้าคุณสามารถทำได้สำหรับ
เพียงแค่ช่วงเวลาที่สาย

726
00:32:08,200 --> 00:32:10,490
ตัวเองขึ้นเพียง
เช่นภาพนี้ที่นี่

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> ขวาทั้งหมด

729
00:32:15,959 --> 00:32:17,125
ลองมาดูสิ่งที่เป็นชื่อของคุณ?

730
00:32:17,125 --> 00:32:17,550
>> ผู้ชม: แอนดรู

731
00:32:17,550 --> 00:32:18,800
>> เดวิดเจลัน: แอนดรู
คุณมีจำนวน 9

732
00:32:18,800 --> 00:32:19,540
มีความสุขที่ได้พบคุณ

733
00:32:19,540 --> 00:32:20,400
ที่นี่คุณไป

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
ผู้ชม: เจน

736
00:32:22,176 --> 00:32:22,662
เดวิดเจลัน: เจน

737
00:32:22,662 --> 00:32:23,162
เดวิด

738
00:32:23,162 --> 00:32:23,765
เลขที่ 17

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
ใช่?

741
00:32:25,450 --> 00:32:26,400
>> ผู้ชม: ฉันจูเลีย

742
00:32:26,400 --> 00:32:26,980
>> เดวิดเจลัน: จูเลียเดวิด

743
00:32:26,980 --> 00:32:27,545
จำนวน 20

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
ผู้ชม: คริสเตียน

746
00:32:29,340 --> 00:32:30,715
เดวิดเจลัน: คริสเตียนเดวิด

747
00:32:30,715 --> 00:32:31,541
22

748
00:32:31,541 --> 00:32:32,040
และ?

749
00:32:32,040 --> 00:32:32,649
>> ผู้ชม: JP

750
00:32:32,649 --> 00:32:33,440
เดวิดเจลัน: JP

751
00:32:33,440 --> 00:32:34,880
29

752
00:32:34,880 --> 00:32:37,080
เพื่อไปข้างหน้าและได้รับ in-- เอ่อโอ้

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
เอ่อโอ้

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
สแตนด์บาย

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20

759
00:32:42,390 --> 00:32:43,682
ไม่มีใครมีเครื่องหมาย?

760
00:32:43,682 --> 00:32:44,890
ผู้ชม: ฉันมี Sharpie

761
00:32:44,890 --> 00:32:45,660
เดวิดเจลัน: คุณมี Sharpie?

762
00:32:45,660 --> 00:32:46,159
ตกลง

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
และทุกคนจะมีชิ้นส่วนของกระดาษหรือไม่

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
บันทึกการบรรยาย

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
มาใน

769
00:32:55,362 --> 00:32:56,320
ผู้ชม: เราได้รับมัน

770
00:32:56,320 --> 00:32:57,600
เดวิดเจลัน: เรามีมันได้หรือไม่

771
00:32:57,600 --> 00:32:58,577
ขวาทั้งหมดขอขอบคุณ

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
ที่นี่เราไป

774
00:33:02,520 --> 00:33:03,582
เป็นแบบนี้จากคุณ?

775
00:33:03,582 --> 00:33:04,540
คุณเพียงแค่บันทึกวัน

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
ดังนั้น 29

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
ขวาทั้งหมด

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
ผมสะกดผิด 29 แต่ตกลง

782
00:33:14,890 --> 00:33:15,720
ไปข้างหน้า

783
00:33:15,720 --> 00:33:18,114
สิทธิทั้งหมดที่ฉันจะให้คุณ
ปากกาของคุณกลับมาชั่วขณะ

784
00:33:18,114 --> 00:33:19,280
ดังนั้นเราจึงมีคนเหล่านี้ที่นี่

785
00:33:19,280 --> 00:33:20,330
Let 's มีคนอื่น ๆ

786
00:33:20,330 --> 00:33:23,750
เกบ, คุณไม่ต้องการที่จะเล่น
องค์ประกอบแรกที่นี่?

787
00:33:23,750 --> 00:33:25,705
เราจะต้องการให้คุณชี้
ที่คนเหล่านี้ได้ดี

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
ดังนั้น 9, 17, 20, 22, การจัดเรียง
วันที่ 29 และ 34 จากนั้น

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
เราได้สูญเสียใครบางคน?

792
00:33:33,325 --> 00:33:33,950
ฉันจะมี 34

793
00:33:33,950 --> 00:33:36,730
ที่ตกลง did-- ที่อยากจะเป็น 34?

794
00:33:36,730 --> 00:33:37,605
ตกลงมาขึ้น 34

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
สิทธิทั้งหมดนี้จะเป็น
อย่างคุ้มค่าที่สุด

797
00:33:41,220 --> 00:33:41,550
คุณชื่ออะไร?

798
00:33:41,550 --> 00:33:42,040
>> ผู้ชม: ปีเตอร์

799
00:33:42,040 --> 00:33:43,456
>> เดวิดเจลัน: ปีเตอร์มาขึ้น

800
00:33:43,456 --> 00:33:46,810
สิทธิทั้งหมดเพื่อให้ที่นี่เป็น
ทั้งกลุ่มของโหนด

801
00:33:46,810 --> 00:33:49,060
แต่ละพวกคุณแสดงให้เห็นถึง
หนึ่งในสี่เหลี่ยมเหล่านี้

802
00:33:49,060 --> 00:33:51,930
และเกบ, แปลกเล็กน้อย
คนที่ออกมาแสดงเป็นครั้งแรก

803
00:33:51,930 --> 00:33:54,850
ดังนั้นตัวชี้ของเขาเป็นเพียงเล็กน้อยที่มีขนาดเล็ก
บนหน้าจอกว่าคนอื่น

804
00:33:54,850 --> 00:33:58,120
และในกรณีนี้แต่ละด้านซ้ายของคุณ
มือเป็นไปอย่างใดอย่างหนึ่งชี้ลง

805
00:33:58,120 --> 00:34:01,085
จึงเป็นโมฆะดังนั้น
เพียงแค่ขาดของตัวชี้ที่

806
00:34:01,085 --> 00:34:03,210
หรือมันจะได้รับการชี้
ที่โหนดถั​​ดจากคุณ

807
00:34:03,210 --> 00:34:05,440
>> ดังนั้นตอนนี้ถ้าคุณประดับ
ตัวเองเหมือนภาพ

808
00:34:05,440 --> 00:34:07,585
ที่นี่ไปข้างหน้าและจุดที่
ในแต่ละอื่น ๆ ที่มีเกบ

809
00:34:07,585 --> 00:34:11,030
โดยเฉพาะอย่างยิ่งในการชี้ที่
หมายเลข 9 เพื่อเป็นตัวแทนของรายการ

810
00:34:11,030 --> 00:34:14,050
ตกลงและหมายเลข 34, มือซ้ายของคุณ
ควรจะเป็นเพียงการชี้ไปที่พื้น

811
00:34:14,050 --> 00:34:15,750
>> ตกลงดังนั้นนี่คือรายการที่เชื่อมโยง

812
00:34:15,750 --> 00:34:17,580
ดังนั้นนี่คือสถานการณ์ในคำถาม

813
00:34:17,580 --> 00:34:20,210
และแน่นอนนี้เป็นตัวแทน
ของชั้นของปัญหา

814
00:34:20,210 --> 00:34:21,929
ที่คุณอาจพยายามที่จะแก้ปัญหาที่มีรหัส

815
00:34:21,929 --> 00:34:25,020
คุณต้องการที่จะใส่ในท้ายที่สุด
องค์ประกอบใหม่ในรายการ

816
00:34:25,020 --> 00:34:27,494
ในกรณีนี้เรากำลังจะไป
พยายามใส่หมายเลข 55

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
แต่มีจะเป็น
กรณีที่แตกต่างกันที่จะต้องพิจารณา

819
00:34:30,860 --> 00:34:34,409
และแน่นอนนี้จะเป็นหนึ่งใน
ของภาพใหญ่ประเด็นที่นี่คือ

820
00:34:34,409 --> 00:34:35,659
สิ่งที่เป็นกรณีที่แตกต่างกัน

821
00:34:35,659 --> 00:34:39,120
สิ่งที่แตกต่างกันถ้าเงื่อนไขหรือ
สาขาที่โปรแกรมของคุณอาจจะมี?

822
00:34:39,120 --> 00:34:42,024
>> ดีหมายเลขที่คุณกำลังพยายามที่จะ
แทรกซึ่งเรารู้ว่าตอนนี้จะเป็น 55,

823
00:34:42,024 --> 00:34:44,650
แต่ถ้าคุณไม่ทราบ
ล่วงหน้าผม daresay

824
00:34:44,650 --> 00:34:47,840
ตกอยู่ในอย่างน้อยสาม
สถานการณ์ที่เป็นไป

825
00:34:47,840 --> 00:34:49,717
ที่อาจจะเป็นองค์ประกอบใหม่เป็นอย่างไร

826
00:34:49,717 --> 00:34:51,050
ผู้ชม: และสิ้นสุดหรือตรงกลาง

827
00:34:51,050 --> 00:34:54,150
เดวิดเจลัน: ในตอนท้ายใน
กลางหรือที่จุดเริ่มต้น

828
00:34:54,150 --> 00:34:56,650
ดังนั้นผมจึงเรียกร้องว่ามีอย่างน้อย
สามปัญหาที่เราต้องแก้

829
00:34:56,650 --> 00:34:58,691
ลองเลือกสิ่งที่อาจจะ
เนื้อหาที่ง่ายที่สุด

830
00:34:58,691 --> 00:35:01,090
หนึ่งที่องค์ประกอบใหม่
เป็นที่จุดเริ่มต้น

831
00:35:01,090 --> 00:35:04,040
ดังนั้นฉันจะมีรหัสที่ค่อนข้าง
เช่นการค้นหาที่ฉันเพิ่งเขียน

832
00:35:04,040 --> 00:35:07,670
และฉันจะมี PTR ซึ่ง
ผมจะเป็นตัวแทนของที่นี่ด้วยนิ้วของฉัน

833
00:35:07,670 --> 00:35:08,370
ตามปกติ

834
00:35:08,370 --> 00:35:12,430
>> และจำไว้ว่าค่าสิ่งที่
พวกเราเริ่มต้น PTR ไป?

835
00:35:12,430 --> 00:35:15,300
ดังนั้นเราจึงเริ่มต้นมันเป็นโมฆะแรก

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
แต่แล้วสิ่งที่เราทำเมื่อเรา
อยู่ภายในฟังก์ชันการค้นหาของเราหรือไม่

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
เราตั้งค่าเท่ากับครั้งแรก
ซึ่งไม่ได้หมายความว่าการทำเช่นนี้

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
หากฉันตั้ง PTR เท่ากับครั้งแรกสิ่งที่
ควรมือของฉันจริงๆจะชี้ไปที่?

842
00:35:30,570 --> 00:35:31,070
ขวา

843
00:35:31,070 --> 00:35:33,290
ดังนั้นถ้าเกบและฉันจะไป
จะต้องมีค่าเท่ากันที่นี่

844
00:35:33,290 --> 00:35:34,760
เราต้องไปที่จุดทั้งที่บ้านเลขที่ 9

845
00:35:34,760 --> 00:35:36,420
>> ดังนั้นนี่คือจุดเริ่มต้นของเรื่องราวของเรา

846
00:35:36,420 --> 00:35:38,700
และตอนนี้เป็นที่ตรงไปตรงมาเพียง
แม้ว่าไวยากรณ์เป็นของใหม่

847
00:35:38,700 --> 00:35:40,580
แนวคิดนี้เป็นเพียงการค้นหาเชิงเส้น

848
00:35:40,580 --> 00:35:42,750
55 เท่ากับ 9?

849
00:35:42,750 --> 00:35:45,559
หรือมากกว่าสมมุติว่าน้อยกว่า 9

850
00:35:45,559 --> 00:35:47,600
เพราะผมกำลังพยายามที่จะ
คิดออกว่าจะใส่ 55

851
00:35:47,600 --> 00:35:51,270
น้อยกว่า 9, น้อยกว่า 17 น้อย
กว่า 20 น้อยกว่า 22 น้อยกว่า 29

852
00:35:51,270 --> 00:35:52,510
น้อยกว่า 34 ไม่

853
00:35:52,510 --> 00:35:55,080
ดังนั้นตอนนี้เราอยู่ในกรณีที่
หนึ่งในอย่างน้อยสาม

854
00:35:55,080 --> 00:35:59,910
>> ถ้าฉันต้องการแทรก 55 กว่าที่นี่สิ่งที่
บรรทัดของรหัสที่จำเป็นต้องได้รับการดำเนินการ?

855
00:35:59,910 --> 00:36:01,890
อย่างไรภาพนี้
มนุษย์จำเป็นต้องเปลี่ยน?

856
00:36:01,890 --> 00:36:03,181
ฉันจะทำอะไรกับมือซ้ายของฉันได้อย่างไร

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
นี้ควรจะเป็นโมฆะในขั้นต้น
เพราะผมตอนท้ายของรายการ

859
00:36:07,360 --> 00:36:09,318
และสิ่งที่ควรจะเกิดขึ้น
ที่นี่กับปีเตอร์เป็นมันได้หรือไม่

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
เขาก็เห็นได้ชัดว่าจะชี้ให้ฉัน

862
00:36:12,430 --> 00:36:15,580
ดังนั้นผมจึงเรียกร้องว่ามีอย่างน้อยสองบรรทัด
ของรหัสในโค้ดตัวอย่างตั้งแต่วันนี้

863
00:36:15,580 --> 00:36:18,570
ที่จะดำเนินการนี​​้
สถานการณ์ของการเพิ่ม 55 ที่หาง

864
00:36:18,570 --> 00:36:20,950
และอาจจะมีใครบางคนกระโดด
และเพียงแค่แสดง 55?

865
00:36:20,950 --> 00:36:22,200
สิทธิทั้งหมดคุณใหม่ 55

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> ดังนั้นตอนนี้สิ่งที่ถ้าต่อไป
สถานการณ์มาพร้อม

868
00:36:27,054 --> 00:36:29,720
และเราต้องการที่จะแทรกที่
จุดเริ่มต้นหรือหัวของรายการนี​​้หรือไม่

869
00:36:29,720 --> 00:36:31,100
และสิ่งที่ชื่อหมายเลข 55 ของคุณ?

870
00:36:31,100 --> 00:36:31,420
>> ผู้ชม: แจ็ค

871
00:36:31,420 --> 00:36:32,295
>> เดวิดเจลัน: แจ็ค?

872
00:36:32,295 --> 00:36:33,585
ตกลงที่ดีที่จะได้พบคุณ

873
00:36:33,585 --> 00:36:34,210
ยินดีต้อนรับบนเรือ

874
00:36:34,210 --> 00:36:36,640
ดังนั้นตอนนี้เรากำลังจะไป
แทรกพูดหมายเลข 5

875
00:36:36,640 --> 00:36:39,840
นี่คือกรณีที่สองของการเป็น
สามเรามาด้วยก่อนที่จะ

876
00:36:39,840 --> 00:36:43,050
ดังนั้นถ้า 5 เป็นที่จุดเริ่มต้น
เรามาดูวิธีการที่เราพบว่า

877
00:36:43,050 --> 00:36:46,310
ฉันเริ่มต้น PTR ของฉัน
ตัวชี้ไปยังหมายเลข 9 อีกครั้ง

878
00:36:46,310 --> 00:36:49,140
และฉันรู้ว่าโอ้, 5 เป็นน้อยกว่า 9

879
00:36:49,140 --> 00:36:50,880
ดังนั้นการแก้ไขปัญหาภาพนี้สำหรับเรา

880
00:36:50,880 --> 00:36:54,820
มีมือเกบหรือเดวิด
or-- ชื่ออะไรหมายเลข 9 หรือไม่

881
00:36:54,820 --> 00:36:55,740
>> ผู้ชม: เจน

882
00:36:55,740 --> 00:36:58,406
>> เดวิดเจลัน: hands-- เจน
ซึ่งจากมือของเราจำเป็นที่จะต้องเปลี่ยน?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK เพื่อให้เกบชี้ในสิ่งที่ตอนนี้หรือไม่

885
00:37:00,970 --> 00:37:01,640
มาที่ฉัน

886
00:37:01,640 --> 00:37:02,750
ผมโหนดใหม่

887
00:37:02,750 --> 00:37:04,870
ดังนั้นฉันจะเพียงชนิดของการย้าย
ที่นี่จะเห็นมันสายตา

888
00:37:04,870 --> 00:37:06,435
และในขณะเดียวกันสิ่งที่ฉันชี้ที่?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
ยังคงที่ฉันชี้

891
00:37:09,020 --> 00:37:10,000
ดังนั้นที่มัน

892
00:37:10,000 --> 00:37:13,717
ดังนั้นเพียงแค่จริงๆหนึ่งบรรทัดของการแก้ไขรหัส
ปัญหานี้โดยเฉพาะอย่างยิ่งก็จะดูเหมือน

893
00:37:13,717 --> 00:37:14,800
สิทธิทั้งหมดเพื่อให้เป็นสิ่งที่ดี

894
00:37:14,800 --> 00:37:17,580
และคนที่สามารถเป็นตัวยึดสำหรับ 5?

895
00:37:17,580 --> 00:37:18,080
มาขึ้น

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
เราจะให้คุณได้รับในครั้งต่อไป

898
00:37:21,320 --> 00:37:24,280
>> ทั้งหมดขวาดังนั้น now-- และ
เช่นกันชื่อ

899
00:37:24,280 --> 00:37:28,510
ผมไม่ได้กล่าวถึงอย่างชัดเจนสิทธิ
ตอนนี้ตัวชี้ pred ตัวชี้บรรพบุรุษ

900
00:37:28,510 --> 00:37:31,260
และตัวชี้ใหม่ที่
เพียงแค่ชื่อที่กำหนด

901
00:37:31,260 --> 00:37:35,280
ในโค้ดตัวอย่างที่จะชี้หรือ
มือของฉันที่ชนิดของการชี้รอบ

902
00:37:35,280 --> 00:37:36,060
คุณชื่ออะไร?

903
00:37:36,060 --> 00:37:36,700
>> ผู้ชม: คริสติน

904
00:37:36,700 --> 00:37:37,100
>> เดวิดเจลัน: คริสติน

905
00:37:37,100 --> 00:37:38,090
ยินดีต้อนรับบนเรือ

906
00:37:38,090 --> 00:37:42,180
สิทธิทั้งหมดเพื่อให้พิจารณาขณะนี้
สถานการณ์ที่น่ารำคาญมากขึ้นเล็กน้อย

907
00:37:42,180 --> 00:37:46,350
โดยผมต้องการที่จะใส่
26 สิ่งที่ต้องการลงในนี้

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
คืออะไร?

910
00:37:47,590 --> 00:37:50,510
เหล่านี้ are-- สิ่งที่ดีเรามีปากกานี้

911
00:37:50,510 --> 00:37:51,955
สิทธิทั้งหมด 20

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
ถ้ามีคนจะได้รับชิ้นส่วนของอื่น
กระดาษพร้อมเพียงใน case-- ขวาทั้งหมด

914
00:37:57,570 --> 00:37:58,370
โอ้ที่น่าสนใจ

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
อย่างนี้เป็นตัวอย่าง
ข้อผิดพลาดของการบรรยาย

917
00:38:02,390 --> 00:38:03,894
ตกลงดังนั้นสิ่งที่เป็นชื่อของคุณอีกครั้งหรือไม่

918
00:38:03,894 --> 00:38:04,560
ผู้ชม: จูเลีย

919
00:38:04,560 --> 00:38:07,559
เดวิดเจลัน: จูเลียคุณสามารถป๊อปอัพ
ออกมาและหลอกคุณไม่เคยมี?

920
00:38:07,559 --> 00:38:09,040
ตกลงนี้ไม่เคยเกิดขึ้น

921
00:38:09,040 --> 00:38:09,680
ขอบคุณ

922
00:38:09,680 --> 00:38:12,180
ดังนั้นสมมติว่าเราต้องการแทรก
จูเลียเป็นรายการที่เชื่อมโยงนี้

923
00:38:12,180 --> 00:38:13,780
เธอคือหมายเลข 20

924
00:38:13,780 --> 00:38:15,530
และแน่นอนเธอ
จะอยู่ที่

925
00:38:15,530 --> 00:38:17,521
begin-- ไม่ได้ชี้ไปที่อะไรยัง

926
00:38:17,521 --> 00:38:20,020
เพื่อให้มือของคุณชนิดของสามารถ
ลงโมฆะหรือค่าขยะบาง

927
00:38:20,020 --> 00:38:21,210
ขอบอกเล่าเรื่องราวได้อย่างรวดเร็ว

928
00:38:21,210 --> 00:38:22,980
ผมชี้ไปที่หมายเลข 5 ในครั้งนี้

929
00:38:22,980 --> 00:38:23,880
แล้วฉันจะตรวจสอบ 9

930
00:38:23,880 --> 00:38:25,130
แล้วฉันจะตรวจสอบ 17

931
00:38:25,130 --> 00:38:26,247
แล้วฉันจะตรวจสอบ 22

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
และฉันตระหนักโอจูเลีย
ต้องไปก่อนวันที่ 22

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
ดังนั้นสิ่งที่ต้องเกิดขึ้น?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
ที่มีอยู่ในมือจะต้องเปลี่ยน?

938
00:38:36,910 --> 00:38:38,360
จูเลียเหมือง or--
สิ่งที่ชื่อของคุณอีกครั้งหรือไม่

939
00:38:38,360 --> 00:38:39,230
>> ผู้ชม: คริสเตียน

940
00:38:39,230 --> 00:38:40,060
>> เดวิดเจลัน: คริสเตียนหรือ?

941
00:38:40,060 --> 00:38:40,560
>> ผู้ชม: แอนดี้

942
00:38:40,560 --> 00:38:40,905
>> เดวิดเจลัน: แอนดี้

943
00:38:40,905 --> 00:38:41,654
คริสเตียนหรือแอนดี้?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
แอนดี้จะต้องชี้ไปที่?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
จูเลีย

948
00:38:47,341 --> 00:38:47,840
ขวาทั้งหมด

949
00:38:47,840 --> 00:38:48,960
ดังนั้นแอนดี้, คุณต้องการที่จะชี้ไปที่จูเลีย?

950
00:38:48,960 --> 00:38:50,120
แต่รอสักครู่

951
00:38:50,120 --> 00:38:53,260
ในเรื่องป่านนี้
ฉันจัดเรียงของหนึ่ง

952
00:38:53,260 --> 00:38:56,800
ในค่าใช้จ่ายในแง่ที่ว่า
ชี้เป็นสิ่งที่เป็น

953
00:38:56,800 --> 00:38:57,850
เคลื่อนที่ผ่านรายการ

954
00:38:57,850 --> 00:39:00,800
เราอาจจะมีชื่อของแอนดี้ แต่
มีตัวแปรที่เรียกว่าแอนดี้ไม่

955
00:39:00,800 --> 00:39:04,320
เพียงตัวแปรอื่น ๆ ที่เรามีคือ
ครั้งแรกที่ได้แสดงโดยเกบ

956
00:39:04,320 --> 00:39:07,690
>> ดังนั้นนี้เป็นจริงทำไมจึง
จนถึงขณะนี้เราได้ไม่จำเป็นต้องนี้

957
00:39:07,690 --> 00:39:10,846
แต่ตอนนี้บนหน้าจอมี
พูดถึงอีกครั้งของตัวชี้ผู้ชนะ

958
00:39:10,846 --> 00:39:11,970
ดังนั้นขอให้ฉันเป็นที่ชัดเจนมากขึ้น

959
00:39:11,970 --> 00:39:14,820
ถ้านี่เป็นตัวชี้ผมได้ดีกว่า
ได้รับน้อยฉลาดมากขึ้น

960
00:39:14,820 --> 00:39:15,950
เกี่ยวกับการย้ำของฉัน

961
00:39:15,950 --> 00:39:19,580
ถ้าคุณไม่คิดจะของฉันผ่านที่นี่
อีกครั้งชี้นี่ชี้ที่นี่

962
00:39:19,580 --> 00:39:22,500
แต่ให้ฉันมีตัวชี้ชนะ,
ตัวชี้บรรพบุรุษที่

963
00:39:22,500 --> 00:39:24,740
ชนิดของชี้ไปที่
องค์ประกอบฉันเป็นเพียงที่

964
00:39:24,740 --> 00:39:27,330
ดังนั้นเมื่อผมไปที่นี่ตอนนี้
การปรับปรุงของฉันมือซ้าย

965
00:39:27,330 --> 00:39:29,370
เมื่อผมไปที่นี่การปรับปรุงทางด้านซ้ายมือของฉัน

966
00:39:29,370 --> 00:39:33,090
และตอนนี้ฉันไม่เพียง แต่มีตัวชี้ไปยัง
องค์ประกอบที่จะไปหลังจากที่จูเลีย

967
00:39:33,090 --> 00:39:36,300
ผมยังมีตัวชี้ไปยัง
แอนดี้องค์ประกอบก่อน

968
00:39:36,300 --> 00:39:39,430
เพื่อให้คุณมีการเข้าถึงเป็นหลัก
สวดมนต์, ถ้าคุณจะ

969
00:39:39,430 --> 00:39:41,500
ทั้งหมดของตัวชี้จำเป็น

970
00:39:41,500 --> 00:39:43,710
>> ดังนั้นหากผมชี้ไปที่
แอนดี้และฉันยังชี้

971
00:39:43,710 --> 00:39:47,105
ที่นับถือศาสนาคริสต์ที่มีอยู่ในมือ
ตอนนี้ควรจะชี้อื่น?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
แอนดี้ดังนั้นตอนนี้สามารถชี้ไปที่จูเลีย

974
00:39:51,960 --> 00:39:54,460
จูเลียขณะนี้สามารถชี้ไปที่นับถือศาสนาคริสต์

975
00:39:54,460 --> 00:39:56,950
เพราะเธอสามารถคัดลอกของฉัน
ชี้มือข้างขวาของ

976
00:39:56,950 --> 00:40:00,044
และที่มีประสิทธิภาพทำให้คุณ
กลับเข้าที่นี่

977
00:40:00,044 --> 00:40:02,460
ดังนั้นในระยะสั้นแม้นี้
คือการให้เราชนิดของตลอดไป

978
00:40:02,460 --> 00:40:04,510
การปรับปรุงจริง
รายการที่เชื่อมโยงตระหนัก

979
00:40:04,510 --> 00:40:06,580
ว่าการดำเนินงาน
มีความง่าย

980
00:40:06,580 --> 00:40:10,030
มันเป็นหนึ่งสองสาม
บรรทัดของรหัสในท้ายที่สุด

981
00:40:10,030 --> 00:40:12,780
แต่พันรอบที่
บรรทัดของรหัสสันนิษฐาน

982
00:40:12,780 --> 00:40:16,350
เป็นบิตของตรรกะที่มีประสิทธิภาพ
ถามคำถามที่เรา?

983
00:40:16,350 --> 00:40:18,970
เราอยู่ที่จุดเริ่มต้นที่
กลางหรือสิ้นสุดหรือไม่

984
00:40:18,970 --> 00:40:21,890
>> ตอนนี้มีแน่นอนอื่น ๆ
การดำเนินงานของเราอาจจะใช้

985
00:40:21,890 --> 00:40:24,880
และภาพเหล่านี้ที่นี่ก็แสดงให้เห็นถึง
สิ่งที่เราได้ทำกับมนุษย์

986
00:40:24,880 --> 00:40:26,080
สิ่งที่เกี่ยวกับการกำจัด?

987
00:40:26,080 --> 00:40:30,650
ถ้าผมอยากจะยกตัวอย่างเช่น
ลบหมายเลข 34 หรือ 55,

988
00:40:30,650 --> 00:40:34,680
ฉันอาจจะมีชนิดเดียวกันของรหัส
แต่ฉันจะต้องหนึ่งหรือสองขั้นตอน

989
00:40:34,680 --> 00:40:36,110
เพราะมีอะไรใหม่?

990
00:40:36,110 --> 00:40:40,460
ถ้าผมเอาคนที่ท้ายที่สุด
เช่นหมายเลข 55 และแล้ว 34,

991
00:40:40,460 --> 00:40:42,995
สิ่งที่ยังมีการเปลี่ยนแปลงที่ผมทำนั้น

992
00:40:42,995 --> 00:40:44,870
ฉันต้องไม่ evict--
สิ่งที่ชื่อของคุณอีกครั้งหรือไม่

993
00:40:44,870 --> 00:40:45,380
>> ผู้ชม: แจ็ค

994
00:40:45,380 --> 00:40:46,255
>> เดวิดเจลัน: แจ็ค

995
00:40:46,255 --> 00:40:49,770
ฉันต้องไม่เพียง แต่ evict-- ฟรีแจ็ค
เพื่อเรียกตัวอักษรฟรีแจ็คหรืออย่างน้อย

996
00:40:49,770 --> 00:40:53,530
ชี้มีเกินไป แต่ตอนนี้
สิ่งที่ต้องเปลี่ยนกับปีเตอร์?

997
00:40:53,530 --> 00:40:55,510
มือของเขาเริ่มดีขึ้นชี้ลง

998
00:40:55,510 --> 00:40:59,300
เพราะทันทีที่ผมเรียกฟรีใน
แจ็คถ้าปีเตอร์ยังคงชี้ไปที่แจ็ค

999
00:40:59,300 --> 00:41:02,530
และฉันจึงเก็บไว้ภายใน
รายการและการเข้าถึงตัวชี้นี้

1000
00:41:02,530 --> 00:41:05,650
ที่เมื่อแบ่งส่วนเพื่อนเก่าของเรา
ความผิดจริงอาจเตะใน

1001
00:41:05,650 --> 00:41:07,860
เพราะเราได้รับ
กลับหน่วยความจำเพื่อแจ็ค

1002
00:41:07,860 --> 00:41:10,760
>> คุณสามารถอยู่ที่นั่น
อย่างเชื่องช้าเพียงสักครู่

1003
00:41:10,760 --> 00:41:13,410
เพราะเรามีเพียงไม่กี่
การดำเนินงานขั้นสุดท้ายที่จะต้องพิจารณา

1004
00:41:13,410 --> 00:41:15,600
ถอดหัวของรายการที่
หรือ beginning-- และเป็นหนึ่งในนี้

1005
00:41:15,600 --> 00:41:16,349
ที่น่ารำคาญเล็ก ๆ น้อย ๆ

1006
00:41:16,349 --> 00:41:19,640
เพราะเราต้องรู้ว่าเกบ
เป็นชนิดพิเศษในโปรแกรมนี้

1007
00:41:19,640 --> 00:41:21,440
เพราะอันที่จริงเขามีตัวชี้ของตัวเอง

1008
00:41:21,440 --> 00:41:24,860
เขาไม่ได้เพียงแค่ถูกชี้ไปที่
เป็นเกือบทุกคนอื่นที่นี่

1009
00:41:24,860 --> 00:41:28,112
>> ดังนั้นเมื่อหัวของรายการเป็น
ออกซึ่งมือต้องเปลี่ยนตอนนี้หรือไม่

1010
00:41:28,112 --> 00:41:29,070
คุณชื่ออะไรอีกครั้งหรือไม่

1011
00:41:29,070 --> 00:41:29,450
>> ผู้ชม: คริสติน

1012
00:41:29,450 --> 00:41:31,408
>> เดวิดเจลัน: ฉันกลัว
ชื่อที่เห็นได้ชัด

1013
00:41:31,408 --> 00:41:34,011
ดังนั้นคริสตินและเกบ
ที่มีอยู่ในมือจะต้องเปลี่ยน

1014
00:41:34,011 --> 00:41:36,510
เมื่อเราพยายามที่จะเอาคริสติน
จำนวน 5 จากภาพหรือไม่

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
ตกลงจึงขอทำเกบ

1017
00:41:38,820 --> 00:41:40,950
เกบจะชี้
สันนิษฐานว่าที่บ้านเลขที่ 9

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
แต่สิ่งที่ควรจะเกิดขึ้นต่อไป?

1020
00:41:44,642 --> 00:41:46,600
ผู้ชม: คริสตินควร
เป็นโมฆะ [ไม่ได้ยิน]

1021
00:41:46,600 --> 00:41:50,244
เดวิดเจลัน: ตกลงเราควรอาจ
make-- ฉันได้ยิน "โมฆะ" อยู่ที่ไหนสักแห่ง

1022
00:41:50,244 --> 00:41:51,410
ผู้ชม: Null และฟรีของเธอ

1023
00:41:51,410 --> 00:41:51,855
เดวิดเจลัน: Null อะไร

1024
00:41:51,855 --> 00:41:53,074
ผู้ชม: Null และฟรีของเธอ

1025
00:41:53,074 --> 00:41:54,490
เดวิดเจลัน: Null และฟรีของเธอ

1026
00:41:54,490 --> 00:41:55,422
ดังนั้นนี้เป็นเรื่องง่ายมาก

1027
00:41:55,422 --> 00:41:58,380
และมันเป็นเรื่องที่สมบูรณ์แบบที่คุณตอนนี้การจัดเรียง
ยืนอยู่ที่นั่นไม่ได้เป็น

1028
00:41:58,380 --> 00:42:00,430
เพราะคุณได้รับ
หลุดพ้นจากรายการ

1029
00:42:00,430 --> 00:42:02,820
คุณได้รับได้อย่างมีประสิทธิภาพ
กำพร้าจากรายการ

1030
00:42:02,820 --> 00:42:07,770
และเพื่อให้เราได้ดีกว่าการโทรฟรีในขณะนี้
คริสตินที่จะให้หน่วยความจำที่กลับมา

1031
00:42:07,770 --> 00:42:10,240
มิฉะนั้นทุกครั้งที่เรา
ลบโหนดจากรายการ

1032
00:42:10,240 --> 00:42:14,230
เราอาจจะมีการทำรายการ
สั้นลง แต่ไม่ได้ลดลง

1033
00:42:14,230 --> 00:42:15,096
ขนาดในหน่วยความจำ

1034
00:42:15,096 --> 00:42:17,720
และอื่น ๆ ถ้าเราเก็บเพิ่มและ
เพิ่มเพิ่มสิ่งที่รายการ

1035
00:42:17,720 --> 00:42:19,280
คอมพิวเตอร์ของฉันอาจได้รับช้า
และช้าลงและช้าลง

1036
00:42:19,280 --> 00:42:21,740
เพราะฉันวิ่งออกมาจาก
หน่วยความจำแม้ว่าฉันไม่ได้จริง

1037
00:42:21,740 --> 00:42:25,580
โดยใช้ไบต์คริสติน
ของหน่วยความจำอีกต่อไป

1038
00:42:25,580 --> 00:42:28,500
>> ดังนั้นในที่สุดมีอื่น ๆ
สถานการณ์การกำจัด course--

1039
00:42:28,500 --> 00:42:30,640
ในกลางกำจัด
ในตอนท้ายที่เราเห็น

1040
00:42:30,640 --> 00:42:32,348
แต่ที่น่าสนใจมากขึ้น
ความท้าทายขณะนี้คือ

1041
00:42:32,348 --> 00:42:34,770
จะเป็นที่จะต้องพิจารณาว่า
สิ่งที่เวลาการทำงานเป็น

1042
00:42:34,770 --> 00:42:36,640
ดังนั้นไม่เพียง แต่คุณสามารถเก็บของคุณ
ชิ้นส่วนของกระดาษถ้าเกบ

1043
00:42:36,640 --> 00:42:38,640
คุณจะไม่คิดให้
ทุกคนลูกความเครียด

1044
00:42:38,640 --> 00:42:42,100
ขอบคุณมากที่จะเชื่อมโยงรายการของเรา
ของอาสาสมัครที่นี่ถ้าคุณสามารถทำได้

1045
00:42:42,100 --> 00:42:45,320
>> [APPLAUSE]

1046
00:42:45,320 --> 00:42:46,700
>> เดวิดเจลัน: ทั้งหมดขวา

1047
00:42:46,700 --> 00:42:51,110
ดังนั้นคู่ของการวิเคราะห์
คำถามแล้วถ้าฉันสามารถ

1048
00:42:51,110 --> 00:42:59,670
เราได้เห็นสัญกรณ์เช่นนี้มาก่อน
O ขนาดใหญ่และโอเมก้า, ขอบเขตบน

1049
00:42:59,670 --> 00:43:02,520
และขอบเขตที่ลดลง
ใช้เวลาบางส่วนของขั้นตอนวิธี

1050
00:43:02,520 --> 00:43:04,950
ดังนั้นขอให้พิจารณาเพียงแค่
สองสามคำถาม

1051
00:43:04,950 --> 00:43:07,090
>> หนึ่งและเราบอกว่ามัน
ก่อนที่สิ่งที่ทำงาน

1052
00:43:07,090 --> 00:43:10,647
ช่วงเวลาของการค้นหา
รายการในแง่ของ O ใหญ่?

1053
00:43:10,647 --> 00:43:13,480
อะไรคือขอบเขตบนทำงาน
เวลาของการค้นหารายการที่เชื่อมโยง

1054
00:43:13,480 --> 00:43:16,340
ที่ดำเนินการโดยอาสาสมัครของเราที่นี่?

1055
00:43:16,340 --> 00:43:17,820
มันเป็นเรื่องใหญ่ของ O n เชิงเส้น

1056
00:43:17,820 --> 00:43:20,630
เพราะในกรณีที่เลวร้ายที่สุด
องค์ประกอบเช่น 55,

1057
00:43:20,630 --> 00:43:23,830
เราอาจจะมองหาอาจจะเป็นที่
แจ็คเป็นทุกทางในตอนท้าย

1058
00:43:23,830 --> 00:43:28,250
และโชคไม่ดีที่แตกต่างจากอาร์เรย์
เราไม่สามารถรับแฟนซีเวลานี้

1059
00:43:28,250 --> 00:43:31,820
แม้ว่าทั้งหมดของมนุษย์ของเราได้
เรียงลำดับจากองค์ประกอบขนาดเล็ก, 5,

1060
00:43:31,820 --> 00:43:35,900
ทุกอย่างขึ้นอยู่กับองค์ประกอบที่ใหญ่กว่าที่
55, ที่มักจะเป็นสิ่งที่ดี

1061
00:43:35,900 --> 00:43:38,815
แต่สิ่งที่จะสันนิษฐานว่า
ไม่ได้ช่วยให้เราสามารถทำอย่างไร

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
ผู้ชม: [ไม่ได้ยิน]

1064
00:43:40,650 --> 00:43:40,920
เดวิดเจลัน: พูดอีกครั้งหรือไม่

1065
00:43:40,920 --> 00:43:41,800
ผู้ชม: การเข้าถึงแบบสุ่ม

1066
00:43:41,800 --> 00:43:43,049
เดวิดเจลัน: การเข้าถึงแบบสุ่ม

1067
00:43:43,049 --> 00:43:46,330
และในทางกลับนั่นหมายความว่าเราสามารถไม่มี
ได้ใช้ศูนย์อ่อนแอปรีชา

1068
00:43:46,330 --> 00:43:49,365
และความชัดเจนของการใช้ไบนารี
การค้นหาและการแบ่งและพิชิต

1069
00:43:49,365 --> 00:43:51,240
เพราะถึงแม้เรา
มนุษย์สามารถที่จะเห็นได้ชัด

1070
00:43:51,240 --> 00:43:54,610
เห็นว่าแอนดี้หรือคริสเตียน
ๆ ที่อยู่ตรงกลางของรายการที่

1071
00:43:54,610 --> 00:43:57,670
เราเท่านั้นที่รู้ว่าเป็น
คอมพิวเตอร์โดย skimming รายการ

1072
00:43:57,670 --> 00:43:59,029
จากจุดเริ่มต้นมาก

1073
00:43:59,029 --> 00:44:00,570
ดังนั้นเราจึงได้รับการเข้าถึงแบบสุ่มที่

1074
00:44:00,570 --> 00:44:04,380
>> O ดังนั้นใหญ่ของ n ขณะนี้คือด้านบน
ผูกพันกับเวลาค้นหาของเรา

1075
00:44:04,380 --> 00:44:07,920
สิ่งที่เกี่ยวกับโอเมก้าของการค้นหาของเราหรือไม่

1076
00:44:07,920 --> 00:44:11,535
สิ่งที่ขอบเขตที่ต่ำในการค้นหา
สำหรับจำนวนในรายการนี​​้บาง

1077
00:44:11,535 --> 00:44:12,410
ผู้ชม: [ไม่ได้ยิน]

1078
00:44:12,410 --> 00:44:13,040
เดวิดเจลัน: พูดอีกครั้งหรือไม่

1079
00:44:13,040 --> 00:44:13,420
ผู้ชม: หนึ่ง

1080
00:44:13,420 --> 00:44:13,800
เดวิดเจลัน: หนึ่ง

1081
00:44:13,800 --> 00:44:14,760
เวลาเพื่อให้คงที่

1082
00:44:14,760 --> 00:44:17,020
ในกรณีที่ดีที่สุดคริสตินเป็น
แน่นอนที่จุดเริ่มต้นของรายการ

1083
00:44:17,020 --> 00:44:19,020
และเรากำลังมองหา
จำนวน 5 ดังนั้นเราจึงพบว่าเธอ

1084
00:44:19,020 --> 00:44:19,787
ดังนั้นไม่มีเรื่องใหญ่

1085
00:44:19,787 --> 00:44:22,370
แต่เธอก็เป็นที่
จุดเริ่มต้นของรายการในกรณีนี้

1086
00:44:22,370 --> 00:44:23,745
สิ่งที่เกี่ยวกับสิ่งที่ต้องการลบ?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
ถ้าคุณต้องการที่จะลบองค์ประกอบ?

1089
00:44:26,300 --> 00:44:29,200
อะไรคือขีด จำกัด บนและขีด จำกัด ล่าง
ในการลบอะไรบางอย่างจากการเชื่อมโยง

1090
00:44:29,200 --> 00:44:29,699
รายการ?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
ผู้ชม: [ไม่ได้ยิน]

1093
00:44:36,070 --> 00:44:36,420
เดวิดเจลัน: พูดอีกครั้งหรือไม่

1094
00:44:36,420 --> 00:44:37,067
ผู้ชม: n

1095
00:44:37,067 --> 00:44:38,900
เดวิดเจลัน: n คือ
แน่นอนบนปก

1096
00:44:38,900 --> 00:44:41,700
เพราะในกรณีที่เลวร้ายที่สุดที่เราพยายาม
ลบแจ็คเหมือนเราเพิ่งได้

1097
00:44:41,700 --> 00:44:43,050
เขาเป็นทุกอย่างในตอนท้าย

1098
00:44:43,050 --> 00:44:45,419
จะพาเราตลอดไปหรือ
n ขั้นตอนไปหาเขา

1099
00:44:45,419 --> 00:44:46,460
เพื่อให้บนปก

1100
00:44:46,460 --> 00:44:47,430
นั่นเป็นเชิงเส้นนั่นเอง

1101
00:44:47,430 --> 00:44:50,970
และกรณีที่ดีที่สุดใช้เวลาหรือ
ขอบเขตที่ต่ำกว่าในกรณีที่ดีที่สุด

1102
00:44:50,970 --> 00:44:51,975
จะเป็นเวลาคงที่

1103
00:44:51,975 --> 00:44:54,600
เพราะบางทีเราพยายามที่จะลบ
คริสตินและเราก็โชคดีที่ได้รับ

1104
00:44:54,600 --> 00:44:55,558
เธอเป็นที่จุดเริ่มต้น

1105
00:44:55,558 --> 00:44:56,350
ตอนนี้รอสักครู่

1106
00:44:56,350 --> 00:44:59,370
เกบยังเป็นที่จุดเริ่มต้น
และเรายังมีการอัปเดตเกบ

1107
00:44:59,370 --> 00:45:01,150
เพื่อให้เป็นไม่ได้เป็นเพียงขั้นตอนเดียว

1108
00:45:01,150 --> 00:45:04,210
ดังนั้นจึงเป็นที่แน่นอนคงที่
เวลาในกรณีที่ดีที่สุด

1109
00:45:04,210 --> 00:45:06,345
ในการลบองค์ประกอบที่เล็กที่สุดหรือไม่

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
มันคือแม้ว่ามันอาจจะสอง
สามหรือ 100 สายรหัส

1112
00:45:10,960 --> 00:45:14,000
ถ้าหากมันเป็นหมายเลขเดียวกันของ
เส้นไม่ได้อยู่ในวงบาง

1113
00:45:14,000 --> 00:45:16,577
และเป็นอิสระจากขนาด
ของรายการอย่าง

1114
00:45:16,577 --> 00:45:18,660
การลบองค์ประกอบที่
จุดเริ่มต้นของรายการที่

1115
00:45:18,660 --> 00:45:21,940
แม้ว่าเราจะมีการจัดการกับ
เกบยังคงเป็นเวลาอย่างต่อเนื่อง

1116
00:45:21,940 --> 00:45:24,220
>> ดังนั้นนี้ดูเหมือนว่า
ขั้นตอนใหญ่ไปข้างหลัง

1117
00:45:24,220 --> 00:45:27,000
และสิ่งที่เสียเวลา
ถ้าในหนึ่งสัปดาห์และสัปดาห์

1118
00:45:27,000 --> 00:45:30,250
เป็นศูนย์ที่เรามีไม่เพียง
รหัส pseudocode แต่รหัสที่เกิดขึ้นจริง

1119
00:45:30,250 --> 00:45:35,780
ที่จะใช้สิ่งที่บันทึก
ฐาน n, หรือเข้าสู่ระบบค่อนข้างของ n, ฐานที่ 2

1120
00:45:35,780 --> 00:45:37,150
ในแง่ของเวลาการทำงานของตน

1121
00:45:37,150 --> 00:45:40,710
ดังนั้นทำไม heck เราต้องการที่จะเริ่มต้น
ใช้สิ่งที่ต้องการรายการที่เชื่อมโยงหรือไม่

1122
00:45:40,710 --> 00:45:41,517
ใช่

1123
00:45:41,517 --> 00:45:44,022
>> ผู้ชม: เพ​​ื่อให้คุณสามารถเพิ่ม
องค์ประกอบไปยังอาร์เรย์

1124
00:45:44,022 --> 00:45:46,230
เดวิดเจลัน: คุณสามารถ
เพิ่มองค์ประกอบไปยังอาร์เรย์

1125
00:45:46,230 --> 00:45:47,550
และนี่ก็เป็นใจ

1126
00:45:47,550 --> 00:45:49,740
และเราจะยังคงเห็น
นี้นี้ค้าออกมาก

1127
00:45:49,740 --> 00:45:51,573
เหมือนที่เราเคยเห็น
การปิดด้วยการจัดเรียงเวียน

1128
00:45:51,573 --> 00:45:54,606
จริงๆเราสามารถเพิ่มความเร็ว
ค้นหาหรือเรียงลำดับค่อนข้าง

1129
00:45:54,606 --> 00:45:57,480
ถ้าเราใช้พื้นที่น้อยมากและ
มีก้อนที่เพิ่มขึ้นของหน่วยความจำ

1130
00:45:57,480 --> 00:45:58,760
หรืออาเรย์สำหรับการจัดเรียงเวียน

1131
00:45:58,760 --> 00:46:01,270
แต่เราใช้จ่ายมากขึ้น
พื้นที่ แต่เราประหยัดเวลา

1132
00:46:01,270 --> 00:46:04,820
ในกรณีนี้เราไม่
ให้ขึ้นเวลา แต่เรา

1133
00:46:04,820 --> 00:46:08,170
ดึงดูดความยืดหยุ่น
พลวัตถ้าคุณจะ

1134
00:46:08,170 --> 00:46:10,280
ซึ่งเป็นเนื้อหาที่มีลักษณะเชิงบวก

1135
00:46:10,280 --> 00:46:11,520
>> เรายังใช้พื้นที่

1136
00:46:11,520 --> 00:46:13,710
ในสิ่งที่ความรู้สึกที่เชื่อมโยง
รายการมีราคาแพงกว่า

1137
00:46:13,710 --> 00:46:15,700
ในแง่ของพื้นที่กว่าอาร์เรย์?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
ที่มีการพื้นที่พิเศษมาจากไหน?

1140
00:46:19,920 --> 00:46:20,460
ใช่?

1141
00:46:20,460 --> 00:46:21,800
>> ผู้ชม: ตัวชี้ [ไม่ได้ยิน]

1142
00:46:21,800 --> 00:46:23,310
>> เดวิดเจลัน: ใช่เรา
ยังมีตัวชี้

1143
00:46:23,310 --> 00:46:25,560
ดังนั้นนี้เป็นที่น่ารำคาญ minorly
ในที่ไม่มีฉัน

1144
00:46:25,560 --> 00:46:27,780
ฉันเพียงแค่การจัดเก็บ int
ที่จะเป็นตัวแทน int

1145
00:46:27,780 --> 00:46:30,990
ฉันเก็บ int และ
ตัวชี้ซึ่งเป็น 32 บิต

1146
00:46:30,990 --> 00:46:33,470
ดังนั้นฉันอย่างแท้จริงเสแสร้ง
จำนวนของพื้นที่ที่เกี่ยวข้อง

1147
00:46:33,470 --> 00:46:36,040
นั่นคือการปิด แต่
นั่นคือในกรณีที่ int

1148
00:46:36,040 --> 00:46:39,580
สมมติว่าคุณไม่ได้จัดเก็บ int,
แต่คิดว่าแต่ละสี่เหลี่ยมเหล่านี้

1149
00:46:39,580 --> 00:46:43,290
หรือแต่ละคนเหล่านี้เป็นตัวแทนของ
คำภาษาอังกฤษคำว่า

1150
00:46:43,290 --> 00:46:46,430
อาจจะมีห้าตัวอักษร, 10
ตัวละครอาจจะมากยิ่งขึ้น

1151
00:46:46,430 --> 00:46:49,940
แล้วเพิ่มเพียง 32 บิตมากขึ้น
อาจจะน้อยกว่าเป็นเรื่องใหญ่

1152
00:46:49,940 --> 00:46:52,160
>> สิ่งที่ถ้าแต่ละของนักเรียน
ในการสาธิต

1153
00:46:52,160 --> 00:46:55,107
เป็นตัวอักษร structs นักเรียนที่
มีชื่อและบ้านและอาจจะ

1154
00:46:55,107 --> 00:46:57,065
หมายเลขโทรศัพท์และทวิตเตอร์
จัดการและชอบ

1155
00:46:57,065 --> 00:46:59,564
เพื่อให้ทุกสาขาที่เราเริ่มต้น
พูดคุยเกี่ยวกับวันอื่น ๆ

1156
00:46:59,564 --> 00:47:02,410
มากน้อยของการจัดการที่ใหญ่เป็น
โหนดของเราได้รับน่าสนใจมากขึ้น

1157
00:47:02,410 --> 00:47:05,972
และขนาดใหญ่ที่จะใช้จ่ายใช่มั้ยเพิ่มเติม
ตัวชี้เพียงเพื่อเชื่อมโยงพวกเขาเข้าด้วยกัน

1158
00:47:05,972 --> 00:47:07,180
แต่จริง ๆ แล้วมันเป็นค้าออก

1159
00:47:07,180 --> 00:47:09,560
และแน่นอนรหัสเป็น
ที่ซับซ้อนมากขึ้นในขณะที่คุณจะ

1160
00:47:09,560 --> 00:47:11,770
ดูได้จากการ skimming ผ่าน
ตัวอย่างเช่นโดยเฉพาะอย่างยิ่งที่

1161
00:47:11,770 --> 00:47:14,302
แต่สิ่งที่ถ้ามี
จอกศักดิ์สิทธิ์ที่นี่

1162
00:47:14,302 --> 00:47:17,010
สิ่งที่ถ้าเราไม่ได้ใช้ขั้นตอนที่
หลัง แต่เป็นขั้นตอนใหญ่ไปข้างหน้า

1163
00:47:17,010 --> 00:47:19,180
และใช้ข้อมูลที่
โครงสร้างที่เราผ่านทาง

1164
00:47:19,180 --> 00:47:22,870
สามารถหาองค์ประกอบเช่นแจ็คหรือ
คริสตินหรือองค์ประกอบอื่น ๆ

1165
00:47:22,870 --> 00:47:25,870
ในอาร์เรย์ในเวลาที่คงที่จริงนี้

1166
00:47:25,870 --> 00:47:26,920
ค้นหาเป็นอย่างต่อเนื่อง

1167
00:47:26,920 --> 00:47:28,320
ลบเป็นค่าคงที่

1168
00:47:28,320 --> 00:47:29,570
ใส่เป็นค่าคงที่

1169
00:47:29,570 --> 00:47:32,260
ทั้งหมดของการดำเนินงานเหล่านี้อย่างต่อเนื่อง

1170
00:47:32,260 --> 00:47:33,750
ที่จะเป็นจอกศักดิ์สิทธิ์ของเรา

1171
00:47:33,750 --> 00:47:36,690
และนั่นคือที่ที่เรา
จะรับครั้งต่อไป

1172
00:47:36,690 --> 00:47:38,600
ดูแล้วคุณ

1173
00:47:38,600 --> 00:47:39,371