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
J. DAVID مالان: حسنا.

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
الأخبار حتى أفضل، لا محاضرة
هذا وقد 13th يوم الاثنين القادم.

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
فقط .. انها سوف تكون مذهلة.

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
أو انقر نقرا مزدوجا فوق
الرمز لفتح بعض الملفات،

33
00:01:27,520 --> 00:01:30,430
انها حملت من الصعب ديك
محرك الأقراص أو محرك أقراص الحالة الصلبة

34
00:01:30,430 --> 00:01:34,190
في RAM، ذاكرة الوصول العشوائي، حيث
أنه يعيش حتى تنقطع الكهرباء،

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
أو عند تشغيل نقطة خفض ماريو على
كمبيوتر لينكس في نافذة محطة الخاص بك،

47
00:02:08,030 --> 00:02:12,460
الأصفار وتلك التي تؤلف
يتم تخزين كلمة أو ماريو مؤقتا

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
>> J. DAVID مالان: بالنسبة للوظائف؟

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
>> J. DAVID مالان: بالضبط.

64
00:02:49,660 --> 00:02:52,650
عند استدعاء دالة، لها
يتم نسخ الحجج إلى المكدس.

65
00:02:52,650 --> 00:02:56,330
حتى في أي X أو Y أو في وأو لB
ان كنت تمر في وظيفة

66
00:02:56,330 --> 00:02:58,680
يتم وضع بشكل مؤقت على
ما يسمى المكدس،

67
00:02:58,680 --> 00:03:02,000
مجرد مثل واحد من أننبرغ
الصواني قاعة الطعام، وأيضا أشياء

68
00:03:02,000 --> 00:03:03,190
مثل المتغيرات المحلية.

69
00:03:03,190 --> 00:03:06,290
إذا ظيفة فو أو المبادلة
وظيفة لها المتغيرات المحلية،

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
Shellshock، وهذا ما كان
التي يعاني منها عدد غير قليل من أجهزة الكمبيوتر.

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
ولها استدعاء دالة و،
أساسا وظيفة مجهول تسمى

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
ثم هذه الوظيفة تعسفية تصل
أعلى، و، ويأخذ في سلسلة، AKA شار *،

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
وبعد ذلك يعلن، داخل
من و، مجموعة من الأحرف

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
ج هو، أو هي تلك 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
>> J. DAVID مالان: في المكدس.

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
فهذا يعني نسخة سلسلة، ولكن
ن فقط خطابات، ن حرفا.

121
00:05:25,200 --> 00:05:31,990
حتى الأحرف ن سيكون
نسخ من شريط في ج.

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
>> الجمهور: لا يشمل
غرفة للحرف فارغة.

133
00:05:57,491 --> 00:05:59,990
J. DAVID مالان: لا يشمل
غرفة للحرف فارغة.

134
00:05:59,990 --> 00:06:02,073
يحتمل، خلافا لما حدث في
الممارسة الماضية وحتى لا

135
00:06:02,073 --> 00:06:04,810
لدينا بقدر ما هو زائد 1 ل
استيعاب هذا الطابع فارغة.

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
J. DAVID مالان: الكمال.

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
وج، بالطبع، هو
أيضا في هذه الصورة.

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
هو ج قوس 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
نقطة نقطة نقطة، 11، ومن ثم
سيئة، 12، 13 إلى 19؟

203
00:09:07,890 --> 00:09:11,820
ما الذي سيحدث هنا،
إذا استنتجنا من ترتيب

204
00:09:11,820 --> 00:09:14,790
أن ج قوس 0 هو على رأس
وج قوس 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
>> الجمهور: حسنا، انه سيكون
للكتابة فوق شار * بار.

208
00:09:19,260 --> 00:09:22,260
>> J. DAVID مالان: نعم، يبدو
وأنت تسير في الكتابة تشار * بار.

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
>> حتى إذا كان كل من هذه
الحروف A يمثل فقط،

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
ليس فقط لتشمل جميع
تلك RFS-RM، ولكن أيضا

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
أسفل على ما يصل، ولكن بعد ذلك العناصر
كنت تدفع إلى المكدس تنمو أعلى إلى أسفل،

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
جافا المناعي، على سبيل المثال،
لهذه المسألة بالذات.

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
وبنية بيانات أنا فقط يعني
وسيلة لتصور الذاكرة

323
00:14:47,804 --> 00:14:50,720
بطريقة تتجاوز مجرد القول،
هذا هو عدد صحيح، وهذا هو شار.

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
، ظهر إلى ظهر أجزاء من
الذاكرة، كل منها

328
00:14:59,724 --> 00:15:02,765
سيكون من نفس النوع، وكثافة العمليات،
كثافة العمليات، وكثافة العمليات، وكثافة العمليات، أو حرف، حرف، حرف،

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
>> J. DAVID مالان: عذرا؟

345
00:15:31,315 --> 00:15:32,380
>> الجمهور: وضعها على النهاية.

346
00:15:32,380 --> 00:15:33,796
>> J. DAVID مالان: وضعه على النهاية.

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
البحث الثنائي، والتي قمنا
تحدث عن على الشاشة هنا.

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 والتي تمنحك ليس فقط عدد صحيح

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
>> J. DAVID مالان: ما هذا؟

409
00:18:17,360 --> 00:18:17,880
>> الجمهور: هيكل جديد.

410
00:18:17,880 --> 00:18:19,590
>> J. DAVID مالان: نعم، فلماذا
لا نخلق هيكل جديد،

411
00:18:19,590 --> 00:18:20,920
أو في C، البنية؟

412
00:18:20,920 --> 00:18:25,990
رأيناه البنيات قبل، وإذا لفترة وجيزة،
حيث تعاملنا مع هيكل طالب

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
ستانفورد التي أنشئت ل
معلومات عنقودية معا.

416
00:18:34,810 --> 00:18:38,580
فماذا إذا أخذنا هذه الفكرة نفسها من
الكلمات الرئيسية "الرموز المميزة ل typedef" و "البنية"

417
00:18:38,580 --> 00:18:42,890
وبعد ذلك بعض الاشياء طالب محددة،
ويتطور هذا إلى ما يلي:

418
00:18:42,890 --> 00:18:46,210
الرموز المميزة ل typedef البنية node-- والعقدة هي
مجرد علوم الكمبيوتر عام جدا

419
00:18:46,210 --> 00:18:49,980
المدى عن شيء في بنية بيانات،
حاوية في بنية بيانات.

420
00:18:49,980 --> 00:18:53,900
عقدة أزعم ستكون لدينا
ون كثافة العمليات، واضحة تماما،

421
00:18:53,900 --> 00:18:58,810
ثم أكثر من ذلك بقليل بغموض،
هذا الخط الثاني، العقدة البنية * المقبل.

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
J. DAVID مالان: و
مؤشر إلى عقدة أخرى.

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
انها قليلا مطول هذا الوقت،
لكنه من نوع عقدة البنية *.

431
00:19:18,206 --> 00:19:22,960
أي وقت رأيناه شيء نجمة، أن
يعني انها مؤشر إلى أن نوع البيانات.

432
00:19:22,960 --> 00:19:26,810
ذلك هو القادم على ما يبدو
مؤشر إلى العقدة البنية.

433
00:19:26,810 --> 00:19:28,310
>> الآن، ما هو عقدة البنية؟

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
وإذا كنت تشغيل هذا أنا خلقت السوبر
واجهة المستخدم الرسومية بسيطة واجهة المستخدم الرسومية،

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
لذلك أنا هاهنا.

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، العقدة البنية،

503
00:22:20,690 --> 00:22:24,850
ثم لدي الأقواس المعقوفة، ن الباحث، و
ثم 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
اليوم هو هذا التعريف البنية،
وربما بعض الأشياء الأخرى.

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
ثم في مرحلة ما أنا
ستكون لدينا كثافة العمليات، الرئيسية، باطلة.

520
00:23:03,910 --> 00:23:06,530
ثم انا ذاهب الى
لدينا بعض المهام هنا.

521
00:23:06,530 --> 00:23:10,620
انا ذاهب أيضا أن يكون لها
النموذج، مثل باطلة، والبحث، وكثافة العمليات،

522
00:23:10,620 --> 00:23:13,610
ن، والغرض الذي في الحياة هو
للبحث عن عنصر.

523
00:23:13,610 --> 00:23:18,310
ثم إلى هنا أزعم في
كود اليوم، باطلة، والبحث، وكثافة العمليات، ن،

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
في مجموعة من الأحرف
هذا ما منتهية.

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
J. DAVID مالان: مؤشر إلى العقدة.

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
>> J. DAVID مالان: نعم،
ربما مجرد البداية.

555
00:24:31,942 --> 00:24:34,030
وتلاحظ، أول
العقدة هي شكل مختلف.

556
00:24:34,030 --> 00:24:37,690
انها فقط نصف حجم البنية،
لأنها في الواقع مؤشر فقط.

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
لاغية بذلك، مرة أخرى، هو القادمة
في الصورة هنا.

560
00:24:49,910 --> 00:24:53,620
ليس فقط يستخدم لاغية وكأنها خاصة
قيمة مقابل أشياء مثل getstring

561
00:24:53,620 --> 00:24:57,770
وmalloc، باطل هو أيضا الصفر
المؤشر، لعدم وجود مؤشر،

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
و"يعمل فعلا" I
يعني، يشبه إلى حد كبير سلسلة،

578
00:25:39,250 --> 00:25:42,180
يتيح لنا الانتقال من الحرف الأول
في اسم دافين إلى الثانية،

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
اللعنة، انها يا كبير من ن،
وهي ليست سيئة، في الإنصاف.

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
حتى إذا أنا ظيفة البحث و
أنا إعطاء متغير، صحيح ن

618
00:27:24,660 --> 00:27:28,490
للبحث عن، ولست بحاجة إلى معرفة
تركيب جديد ليبحث داخل

619
00:27:28,490 --> 00:27:32,400
هيكل هذا
وأشار إلى، أن يجد ن.

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
في حين أن المؤشر لا يساوي
لاغية، وهذا جملة صالح.

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
>> إذا مؤشر نقطة ن، اسمحوا لي أن أعود
إلى ذلك، 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
ن الفعلية التي تم تمريرها في.

633
00:28:06,590 --> 00:28:09,020
حتى هنا ميزة أخرى
من C والعديد من اللغات.

634
00:28:09,020 --> 00:28:13,705
على الرغم من أن بنية تسمى العقدة
لديه ن قيمة وشرعية تماما

635
00:28:13,705 --> 00:28:17,530
لدينا أيضا حجة المحلية
أو متغير يسمى ن.

636
00:28:17,530 --> 00:28:20,085
لأنه حتى نحن، مع
العين البشرية، يمكن التمييز

637
00:28:20,085 --> 00:28:22,087
ن أن هذا هو المفترض
يختلف هذا ن.

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
كما أعلن أن وجدنا ن.

644
00:28:35,000 --> 00:28:37,930
وسنترك أنه نتيجة ل
التعليق شبة الكود أو رمز.

645
00:28:37,930 --> 00:28:40,190
آخر، وهنا ل
الجزء المثير للاهتمام، ما

646
00:28:40,190 --> 00:28:47,320
لا أريد أن أفعل إذا كان العقدة الحالية
لا يحتوي ن أن ما يهمني؟

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
J. DAVID مالان: نعم، لذلك القادم.

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
انا ذاهب الى وضع مؤشر
يساوي أيا كان مؤشر is--

660
00:29:19,234 --> 00:29:22,150
ومرة أخرى، هذا سوف يكون
عربات التي تجرها الدواب قليلا عن نقطة اللحظات المقبل.

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
J. DAVID مالان: إذا كانت نقطة بينما
مؤشر لا تساوي قيمة خالية.

670
00:29:43,060 --> 00:29:44,900
في وجهة نظري في بعض إصبع
ستكون لافتا في اغية

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
للهياكل، مؤشر ليس البنية.

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-- أنا لا
اعتقد انني الإفراط في ارتكاب here-- I

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
أنت تقول حرفيا، إلغاء مرجعية
مؤشر وتذهب هناك.

700
00:30:56,530 --> 00:30:59,320
ثم الاستيلاء .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
ما يعادل، متطابقة،
انها السكر النحوي فقط.

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
>> J. DAVID مالان: أندرو،
كنت الرقم 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
J. DAVID مالان: جين.

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
>> J. DAVID مالان: جوليا، ديفيد.

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
J. DAVID مالان: مسيحي، ديفيد.

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
J. DAVID مالان: 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
الجمهور: لقد حصلت على شربي.

761
00:32:44,890 --> 00:32:45,660
J. DAVID مالان: حصلت على شربي؟

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
J. DAVID مالان: نحن حصلت عليه؟

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
دعونا الآخر.

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-- OK، الذي يريد أن يكون 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
>> J. DAVID مالان: بيتر، وتأتي على ما يصل.

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
ولكن إذا كنت لا تعرف
مقدما، نحسب

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
J. DAVID مالان: في النهاية، في
الوسط أو في البداية.

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
>> J. DAVID مالان: جاك؟

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
>> J. DAVID مالان: hands-- جين
أي من أيدينا تحتاج إلى تغيير؟

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
حسنا، غابي يشير إلى ما الآن؟

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
>> J. DAVID مالان: كريستين.

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
OK حتى ما اسمك مرة أخرى؟

918
00:38:03,894 --> 00:38:04,560
الجمهور: جوليا.

919
00:38:04,560 --> 00:38:07,559
J. DAVID مالان: جوليا، يمكنك البوب
خروج والتظاهر كنت لم تكن هناك؟

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
>> J. DAVID مالان: مسيحي أو؟

941
00:38:40,060 --> 00:38:40,560
>> الجمهور: اندي.

942
00:38:40,560 --> 00:38:40,905
>> J. DAVID مالان: اندي.

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
ولكن الآن على الشاشة هناك
نذكر مرة أخرى من مؤشر PRED.

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
ولكن اسمحوا لي أن يكون مؤشر PRED،
مؤشر السلف، وهذا

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
>> J. DAVID مالان: جاك.

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
>> J. DAVID مالان: أنا فظيعة
في الأسماء، على ما يبدو.

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
J. DAVID مالان: حسنا، ربما ينبغي لنا أن
make-- سمعت "لاغية" في مكان ما.

1022
00:41:50,244 --> 00:41:51,410
الجمهور: فارغة وخالية لها.

1023
00:41:51,410 --> 00:41:51,855
J. DAVID مالان: باطل ماذا؟

1024
00:41:51,855 --> 00:41:53,074
الجمهور: فارغة وخالية لها.

1025
00:41:53,074 --> 00:41:54,490
J. DAVID مالان: باطل ولها مجانا.

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
>> [تصفيق]

1046
00:42:45,320 --> 00:42:46,700
>> J. DAVID مالان: حسنا.

1047
00:42:46,700 --> 00:42:51,110
حتى بضعة تحليلية
الأسئلة ثم، إذا استطعت.

1048
00:42:51,110 --> 00:42:59,670
لقد رأينا هذه الرموز من قبل،
يا كبير وأوميغا، الحدود العليا

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
زمن البحث عن
القائمة من حيث يا كبير؟

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
انها يا كبير من ن، الخطية.

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
J. DAVID مالان: قل مرة أخرى؟

1065
00:43:40,920 --> 00:43:41,800
الجمهور: الوصول العشوائي.

1066
00:43:41,800 --> 00:43:43,049
J. DAVID مالان: الوصول العشوائي.

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
نعرف فقط أنه نتيجة ل
الكمبيوتر القشط قائمة

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 كبيرة جدا ن الآن العلوية
ملزمة في وقتنا البحث.

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
J. DAVID مالان: قل مرة أخرى؟

1079
00:44:13,040 --> 00:44:13,420
إستماع: واحد.

1080
00:44:13,420 --> 00:44:13,800
J. DAVID مالان: واحد.

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
J. DAVID مالان: قل مرة أخرى؟

1094
00:44:36,420 --> 00:44:37,067
الجمهور: ن.

1095
00:44:37,067 --> 00:44:38,900
J. DAVID مالان: 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
يأخذنا إلى الأبد، أو
ن الخطوات للعثور عليه.

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
الصفر كان لدينا ليس فقط
كود شبة الكود لكن الرمز الفعلي

1119
00:45:30,250 --> 00:45:35,780
لتنفيذ شيء وهذا السجل
ن قاعدة، أو تسجيل، بالأحرى، ن، قاعدة 2،

1120
00:45:35,780 --> 00:45:37,150
من حيث وقتها التوالي.

1121
00:45:37,150 --> 00:45:40,710
فلماذا هيك كنا نريد أن تبدأ
باستخدام ما يشبه قائمة مرتبطة؟

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
J. DAVID مالان: حتى تتمكن من
إضافة عناصر إلى الصفيف.

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
>> J. DAVID مالان: نعم، نحن
أيضا المؤشر.

1143
00:46:23,310 --> 00:46:25,560
لذلك هذا هو مزعج minorly
في هذا لم أعد

1144
00:46:25,560 --> 00:46:27,780
أنا فقط تخزين عدد صحيح
لتمثيل عدد صحيح.

1145
00:46:27,780 --> 00:46:30,990
أنا تخزين عدد صحيح و
المؤشر، الذي هو أيضا 32 بت.

1146
00:46:30,990 --> 00:46:33,470
لذلك أنا مضاعفة حرفيا
مقدار المساحة المعنية.

1147
00:46:33,470 --> 00:46:36,040
لذلك هذا هو مفاضلة، ولكن
هذا في حالة كثافة العمليات.

1148
00:46:36,040 --> 00:46:39,580
لنفترض أنك لا تخزين كثافة العمليات،
ولكن لنفترض كل من هذه المستطيلات

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
كانت حرفيا البنيات الطلابية التي
لها أسماء والمنازل وربما

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
نرى من خلال القشط
هذا المثال معين.

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