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

2
00:00:00,500 --> 00:00:03,340
[عزف الموسيقى]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID مالان: هذا هو CS50.

5
00:00:14,010 --> 00:00:18,090
وهذا هو بداية كل من و
end-- مثل نهاية literally-- تقريبا

6
00:00:18,090 --> 00:00:18,825
الأسبوع ستة.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> اعتقدت مشاركة
قليلا من حقيقة متعة.

9
00:00:22,640 --> 00:00:25,370
لقد انسحب هذا الأمر من
مجموعة البيانات الفصل الدراسي المنصرم.

10
00:00:25,370 --> 00:00:29,710
ولعلكم تذكرون أن نسأل لكم على كل
شكل مجموعة ص إذا كنت قد شاهدت على الانترنت

11
00:00:29,710 --> 00:00:31,580
أو إذا كنت قد حضرت شخصيا.

12
00:00:31,580 --> 00:00:33,020
وهنا هو البيانات.

13
00:00:33,020 --> 00:00:34,710
حتى اليوم كان يمكن التنبؤ به كثيرا جدا.

14
00:00:34,710 --> 00:00:37,126
ولكن أردنا أن تنفق قليلا
من الوقت معك ومع ذلك.

15
00:00:37,126 --> 00:00:40,599
أي شخص يود أن نخمن ماذا هذا
الرسم البياني هو جاجي ذلك، يصل إلى أسفل، وتصل إلى أسفل،

16
00:00:40,599 --> 00:00:41,265
هكذا على الدوام؟

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
ماذا تفعل كل القمم
وتمثل أحواض؟

19
00:00:45,130 --> 00:00:46,005
>> الجمهور: [غير مسموع]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID مالان: الواقع.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
وأكثر من ذلك متعجبا، لا سمح الله،
ونحن نحمل محاضرة واحدة يوم الجمعة

24
00:00:55,480 --> 00:00:58,960
في بداية الفصل الدراسي،
وهذا ما نراه يحدث.

25
00:00:58,960 --> 00:01:03,430
حتى اليوم، فإننا مشاركة في قليلا
المزيد حول هياكل البيانات.

26
00:01:03,430 --> 00:01:06,660
وتعطيك أكثر من المواد الصلبة
النموذج العقلي للمشاكل في خمسة،

27
00:01:06,660 --> 00:01:07,450
وهو الآن خارج.

28
00:01:07,450 --> 00:01:10,817
أخطاء إملائية، وسوف نقوم فيه
تسليم لك ملف نصي بعض 100000

29
00:01:10,817 --> 00:01:12,650
بالإضافة إلى الكلمات الإنجليزية، و
وأنت تسير لدينا

30
00:01:12,650 --> 00:01:17,770
لمعرفة كيفية تحميل بذكاء لهم
في الذاكرة، في ذاكرة الوصول العشوائي، وذلك باستخدام بعض البيانات

31
00:01:17,770 --> 00:01:19,330
هيكل من اختيارك.

32
00:01:19,330 --> 00:01:22,470
>> الآن يمكن للمرء مثل هذا الهيكل بيانات
يكون، ولكن ربما لا ينبغي أن يكون،

33
00:01:22,470 --> 00:01:25,630
القائمة المرتبطة الساذجة إلى حد ما،
التي قدمنا ​​في المرة السابقة.

34
00:01:25,630 --> 00:01:29,220
وكانت قائمة مرتبطة على الأقل
ميزة واحدة على صفيف.

35
00:01:29,220 --> 00:01:32,096
ما هي ميزة واحدة من
قائمة مرتبطة جدليا؟

36
00:01:32,096 --> 00:01:32,950
>> الجمهور: الإدراج.

37
00:01:32,950 --> 00:01:33,908
>> DAVID مالان: الإدراج.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
ماذا يعني ذلك؟

40
00:01:35,196 --> 00:01:37,872
>> الجمهور: في أي مكان على طول
قائمة (غير مسموع).

41
00:01:37,872 --> 00:01:38,770
>> DAVID مالان: جيد.

42
00:01:38,770 --> 00:01:42,090
حتى تتمكن من إدراج عنصر في أي مكان
تريد في منتصف القائمة

43
00:01:42,090 --> 00:01:45,490
دون الحاجة إلى خلط أي شيء،
الذي خلصنا، في الفرز دينا

44
00:01:45,490 --> 00:01:47,630
المناقشات، ليس
بالضرورة شيئا جيدا،

45
00:01:47,630 --> 00:01:51,200
لأنه يستغرق وقتا طويلا لتحريك الواقع
كل هؤلاء البشر من اليسار أو اليمين.

46
00:01:51,200 --> 00:01:55,540
وحتى مع قائمة مرتبطة، يمكنك
فقط مع تخصيص malloc، عقدة جديدة،

47
00:01:55,540 --> 00:01:58,385
ثم تحديث بضع
pointers-- اثنين، وثلاث عمليات max--

48
00:01:58,385 --> 00:02:01,480
ونحن قادرون على فتحة شخص
في أي مكان في القائمة.

49
00:02:01,480 --> 00:02:03,550
>> ما هو مفيد آخر
حول قائمة مرتبطة؟

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
نعم؟

52
00:02:05,659 --> 00:02:06,534
>> الجمهور: [غير مسموع]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID مالان: الكمال.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
الكمال.

57
00:02:11,090 --> 00:02:12,070
انها ديناميكية حقا.

58
00:02:12,070 --> 00:02:15,100
وأنك لا يقترفون
في وقت مبكر، لبعض حجم ثابت

59
00:02:15,100 --> 00:02:18,750
جزء من الذاكرة، مثل عملتم
لمع مجموعة والصعود منها

60
00:02:18,750 --> 00:02:22,455
هو أنه يمكنك تخصيص العقد فقط على
الطلب وبالتالي تستخدم فقط بقدر الفضاء

61
00:02:22,455 --> 00:02:23,330
ما تحتاج إليه فعلا.

62
00:02:23,330 --> 00:02:26,830
على النقيض من ذلك مع مجموعة، وكنت قد
قصد تخصيص القليل جدا.

63
00:02:26,830 --> 00:02:28,871
ثم انها مجرد الذهاب
أن يكون الألم في الرقبة

64
00:02:28,871 --> 00:02:32,440
إعادة تخصيص مجموعة أكبر جديدة، نسخ
كل شيء انتهى، سراح مجموعة القديمة،

65
00:02:32,440 --> 00:02:33,990
ومن ثم الانتقال عن عملك.

66
00:02:33,990 --> 00:02:37,479
أو ما هو أسوأ، قد تخصص الطريق
ذاكرة أكبر مما تحتاج في الواقع،

67
00:02:37,479 --> 00:02:40,520
وحتى وأنت تسير أن يكون لها جدا
قليلة السكان، مجموعة، إذا جاز التعبير.

68
00:02:40,520 --> 00:02:44,350
>> حتى قائمة مرتبطة تمنحك هذه
مزايا الديناميكية والمرونة

69
00:02:44,350 --> 00:02:46,080
مع الإدراج والحذف.

70
00:02:46,080 --> 00:02:48,000
ولكن بالتأكيد يجب أن يكون هناك ثمن يدفع.

71
00:02:48,000 --> 00:02:50,000
في الواقع، واحدة من المواضيع
بحثت عن مسابقة الصفر

72
00:02:50,000 --> 00:02:52,430
وكان اثنين من المقايضات
رأيناه حتى الآن.

73
00:02:52,430 --> 00:02:56,161
لذلك ما هو الثمن المدفوع أو
الجانب السلبي من قائمة مرتبطة؟

74
00:02:56,161 --> 00:02:56,660
نعم.

75
00:02:56,660 --> 00:02:57,560
>> الجمهور: لا الوصول العشوائي.

76
00:02:57,560 --> 00:02:58,809
>> DAVID مالان: لا الوصول العشوائي.

77
00:02:58,809 --> 00:02:59,540
ولكن من يهتم؟

78
00:02:59,540 --> 00:03:01,546
وصول عشوائي لا تبدو مقنعة.

79
00:03:01,546 --> 00:03:02,421
>> الجمهور: [غير مسموع]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID مالان: بالضبط.

82
00:03:05,740 --> 00:03:07,580
إذا كنت تريد أن يكون
من المؤكد algorithm--

83
00:03:07,580 --> 00:03:10,170
واسمحوا لي أن أقترح فعلا
البحث الثنائي على وجه الخصوص، والتي

84
00:03:10,170 --> 00:03:12,600
هي واحدة استخدمنا تماما bit--
إذا لم يكن لديك الوصول العشوائي،

85
00:03:12,600 --> 00:03:15,516
لا يمكنك أن تفعل ذلك بعملية حسابية بسيطة
العثور على مثل عنصر الأوسط

86
00:03:15,516 --> 00:03:16,530
والقفز الحق في ذلك.

87
00:03:16,530 --> 00:03:20,239
يمكنك بدلا من ذلك أن تبدأ في أول
والعنصر خطيا البحث من اليسار

88
00:03:20,239 --> 00:03:22,780
إلى اليمين إذا كنت تريد أن تجد
منتصف أو أي عنصر آخر.

89
00:03:22,780 --> 00:03:24,410
>> الجمهور: إنه ربما يأخذ المزيد من الذاكرة.

90
00:03:24,410 --> 00:03:25,040
>> DAVID مالان: يأخذ المزيد من الذاكرة.

91
00:03:25,040 --> 00:03:27,464
حيث أن إضافية
تكلفة قادمة من في الذاكرة؟

92
00:03:27,464 --> 00:03:28,339
>> الجمهور: [غير مسموع]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID مالان: بالضبط.

95
00:03:33,440 --> 00:03:35,679
في هذه الحالة هنا، كان لدينا
قائمة مرتبطة عن الأعداد الصحيحة،

96
00:03:35,679 --> 00:03:37,470
وحتى الان نحن مضاعفة
مقدار الذاكرة

97
00:03:37,470 --> 00:03:39,680
نحتاج أيضا عن طريق تخزين هذه المؤشرات.

98
00:03:39,680 --> 00:03:42,090
الآن أقل من صفقة كبيرة كما
البنيات الخاصة بك الحصول على أكبر

99
00:03:42,090 --> 00:03:45,320
وكنت تخزين عدد لا ولكن
ربما طالب أو بعض وجوه الآخرين.

100
00:03:45,320 --> 00:03:46,880
ولكن النقطة يبقى بالتأكيد.

101
00:03:46,880 --> 00:03:49,421
وذلك في عدد من العمليات
على القوائم المرتبطة كانت تسمى

102
00:03:49,421 --> 00:03:50,570
كان يا كبير من الخطية n--.

103
00:03:50,570 --> 00:03:54,730
أشياء مثل الإدراج أو البحث
أو الحذف في حالة عنصر

104
00:03:54,730 --> 00:03:57,720
حدث ليكون في النهاية من
قائمة بشأن ما إذا كانت مرتبة أم لا.

105
00:03:57,720 --> 00:04:01,167
>> أحيانا قد تحصل على الحظ و
أقل حتى حدود على هذه العمليات

106
00:04:01,167 --> 00:04:04,250
قد يكون أيضا وقتا ثابتا إذا كنت
أبحث دائما في العنصر الأول،

107
00:04:04,250 --> 00:04:05,070
على سبيل المثال.

108
00:04:05,070 --> 00:04:09,360
ولكن في نهاية المطاف، وعدنا
لتحقيق الكأس المقدسة

109
00:04:09,360 --> 00:04:12,630
هياكل البيانات، أو
بعض منه التقريب،

110
00:04:12,630 --> 00:04:14,290
عن طريق وقت ثابت.

111
00:04:14,290 --> 00:04:17,579
يمكن أن نجد العناصر أو إضافة عناصر
أو إزالة العناصر من قائمة؟

112
00:04:17,579 --> 00:04:19,059
سنرى قريبا جدا.

113
00:04:19,059 --> 00:04:21,100
واتضح أن واحدة
آليات نحن

114
00:04:21,100 --> 00:04:23,464
الذهاب الى البدء في استخدام اليوم،
الاستخدام السنوي في ص تعيين خمسة،

115
00:04:23,464 --> 00:04:24,630
هو في الواقع مألوفة جدا.

116
00:04:24,630 --> 00:04:27,430
على سبيل المثال، إذا كان هذا هو حفنة
الكتب الامتحان، كل واحدة منها

117
00:04:27,430 --> 00:04:29,660
لديه الطالب أولا
اسم واسم العائلة على ذلك،

118
00:04:29,660 --> 00:04:31,820
وأنا اعتقالهما من
في نهاية الامتحان، و

119
00:04:31,820 --> 00:04:33,746
وانهم جميعا جميلة
الكثير في ترتيب عشوائي،

120
00:04:33,746 --> 00:04:36,370
ونحن نريد أن تذهب حول فرز
هذه الامتحانات بحيث أنه بمجرد متدرج

121
00:04:36,370 --> 00:04:38,661
انه من الاسهل مجرد الكثير و
أسرع لتسليمها الى الخلف

122
00:04:38,661 --> 00:04:40,030
للطلاب أبجديا.

123
00:04:40,030 --> 00:04:42,770
ما يمكن أن يكون لديك الغرائز
لكومة من الامتحانات مثل هذا؟

124
00:04:42,770 --> 00:04:45,019
>> حسنا، إذا كنت مثلي، وكنت
قد نرى أن هذا هو م،

125
00:04:45,019 --> 00:04:48,505
لذلك أنا ذاهب إلى نوع من وضع هذا في،
إذا كان هذا هو مائدتي أو بلدي الطابق حيث

126
00:04:48,505 --> 00:04:50,650
أنا نشر الاشياء
out-- أو مجموعة بلدي really--

127
00:04:50,650 --> 00:04:52,210
وأنا قد وضعت كل من السيدة في هناك.

128
00:04:52,210 --> 00:04:52,710
أوه.

129
00:04:52,710 --> 00:04:55,020
وإليك A. لذا ربما أنا
كما وضعت أكثر من هنا.

130
00:04:55,020 --> 00:04:55,520
أوه.

131
00:04:55,520 --> 00:04:57,980
وهنا A. آخر سأشارك
لوضع هذا هنا.

132
00:04:57,980 --> 00:05:02,490
وهنا Z. هنا M. آخر وهكذا
وأود أن تبدأ في وضع أكوام من هذا القبيل.

133
00:05:02,490 --> 00:05:06,620
ثم ربما كنت اذهب في وقت لاحق
ونوع من nitpicky لاي نوع جدا

134
00:05:06,620 --> 00:05:07,710
أكوام الفردية.

135
00:05:07,710 --> 00:05:11,300
ولكن النقطة هي وأود أن ننظر
عند مدخل أنني سلمت

136
00:05:11,300 --> 00:05:14,016
وأود أن جعل احتساب بعض
القرار بناء على تلك المدخلات.

137
00:05:14,016 --> 00:05:15,640
إذا كان يبدأ، ووضعها هناك.

138
00:05:15,640 --> 00:05:18,980
إذا كان يبدأ مع Z، ووضعها فوق
هناك، وبين في كل شيء.

139
00:05:18,980 --> 00:05:22,730
>> لذلك هذا هو الاسلوب الذي ل
المعروف عموما باسم hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
مما يعني عموما اتخاذ ما
إدخال واستخدام هذه المدخلات لحساب

141
00:05:26,550 --> 00:05:30,940
قيمة، عموما عددا، والتي
الرقم هو مؤشر إلى التخزين

142
00:05:30,940 --> 00:05:32,260
الحاويات، مثل صفيف.

143
00:05:32,260 --> 00:05:35,490
لذلك وبعبارة أخرى، وأنا قد يكون لها
دالة تجزئة، كما أفعل أنا في رأسي،

144
00:05:35,490 --> 00:05:37,940
أرى أنه إذا كان شخص ما
الاسم الذي يبدأ مع،

145
00:05:37,940 --> 00:05:40,190
انا ذاهب الى أن الخريطة
إلى الصفر في رأسي.

146
00:05:40,190 --> 00:05:44,160
وإذا رأيت شخص ما مع Z، وأنا
الذهاب إلى الخريطة التي ل25 في رأسي

147
00:05:44,160 --> 00:05:46,220
ثم وضع ذلك في
اخر معظم كومة.

148
00:05:46,220 --> 00:05:50,990
>> الآن، إذا كنت تفكر في عدم ذهني
لكن برنامج C، ما يمكن أن أرقام

149
00:05:50,990 --> 00:05:53,170
كنت تعتمد على تحقيق تلك النتيجة نفسها؟

150
00:05:53,170 --> 00:05:55,594
وبعبارة أخرى، إذا كان ل
كان ASCII حرف A،

151
00:05:55,594 --> 00:05:57,510
كيف يمكنك تحديد
ما دلو لوضعها في؟

152
00:05:57,510 --> 00:05:59,801
ربما كنت لا تريد
وضعها في دلو 65، والتي

153
00:05:59,801 --> 00:06:01,840
سيكون مثل هناك
لا لسبب وجيه.

154
00:06:01,840 --> 00:06:04,320
أين تريد وضع و
من حيث قيمة ASCII لها؟

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
أين تريد القيام به لASCII لها
قيمة إلى الخروج مع دلو ذكاء

157
00:06:08,920 --> 00:06:09,480
لوضعها في؟

158
00:06:09,480 --> 00:06:10,206
>> الجمهور: ناقص أ.

159
00:06:10,206 --> 00:06:10,956
>> DAVID مالان: نعم.

160
00:06:10,956 --> 00:06:13,190
لذلك ناقص أو ناقص
65 تحديدا اذا كان

161
00:06:13,190 --> 00:06:18,240
وA. رأس المال أو 98 إذا
انها صغيرة و.

162
00:06:18,240 --> 00:06:21,300
وذلك من شأنه أن يسمح لنا ل، جدا
ببساطة وحسابيا جدا،

163
00:06:21,300 --> 00:06:23,260
وضع شيء في دلو من هذا القبيل.

164
00:06:23,260 --> 00:06:26,010
لذلك تبين أننا فعلا
هذا فضلا حتى مع مسابقات.

165
00:06:26,010 --> 00:06:29,051
>> لذلك قد أذكر لك حلقت بك
اسم زميل التدريس على الغطاء.

166
00:06:29,051 --> 00:06:32,270
ونظمت أسماء فريق العمل و
في هذه الأعمدة أبجديا،

167
00:06:32,270 --> 00:06:34,400
كذلك، صدقوا أو لا تصدقوا،
عند كل واحد منا زائد 80

168
00:06:34,400 --> 00:06:37,800
حصلت معا ليلة أخرى إلى الصف،
الخطوة الأخيرة في عملية تصنيف لدينا

169
00:06:37,800 --> 00:06:41,830
هو تجزئة في مسابقات كبيرة
مساحة من الأرض في [غير مسموع]

170
00:06:41,830 --> 00:06:45,110
ووضع مسابقات الجميع الخروج
بالضبط في ترتيب TF لمن

171
00:06:45,110 --> 00:06:47,700
أسماء على الغلاف، ل
ثم أنه من الأسهل كثيرا بالنسبة لنا

172
00:06:47,700 --> 00:06:51,290
للبحث من خلال ذلك باستخدام الخطية
بحث أو نوع من الذكاء

173
00:06:51,290 --> 00:06:54,050
لTF لتجد له أو
مسابقات لها الطلاب.

174
00:06:54,050 --> 00:06:56,060
>> لذلك هذه الفكرة من التجزئة
عليك أن ترى

175
00:06:56,060 --> 00:07:00,520
قوية جدا هي جميلة فعلا
شائعا جدا وبديهية،

176
00:07:00,520 --> 00:07:03,000
يشبه إلى حد كبير وربما تقسيم و
كانت تسد في الأسبوع الصفر.

177
00:07:03,000 --> 00:07:05,250
أنا سريع إلى الأمام إلى هاكاثون
بضع سنوات مضت.

178
00:07:05,250 --> 00:07:08,040
كان هذا Zamyla واثنين من
الطلاب الآخرين تحية الموظفين

179
00:07:08,040 --> 00:07:09,030
كما جاء في.

180
00:07:09,030 --> 00:07:12,680
وكان لدينا مجموعة كاملة من للطي
الجداول هناك مع علامات الأسماء.

181
00:07:12,680 --> 00:07:15,380
وكنا قد نظمت علامات الاسم
مع مثل وهناك

182
00:07:15,380 --> 00:07:16,690
وزينب صالح أكثر من هناك.

183
00:07:16,690 --> 00:07:20,350
وذلك واحد من TFS ذكي جدا
كتبت هذا والتعليمات

184
00:07:20,350 --> 00:07:21,030
لهذا اليوم.

185
00:07:21,030 --> 00:07:24,480
و في الأسبوع 12 من الفصل الدراسي هذا
جعل جميع الشعور بالكمال والجميع

186
00:07:24,480 --> 00:07:25,310
أعرف ما يجب القيام به.

187
00:07:25,310 --> 00:07:27,900
ولكن في أي وقت قمت
قائمة الانتظار في نفس الطريق، و

188
00:07:27,900 --> 00:07:30,272
كنت تنفيذ
نفس فكرة تجزئة.

189
00:07:30,272 --> 00:07:31,730
لذلك دعونا إضفاء الطابع الرسمي عليها قليلا.

190
00:07:31,730 --> 00:07:32,890
هنا هو صفيف.

191
00:07:32,890 --> 00:07:36,820
لقد سحبت منه أن يكون قليلا
المرمى لتصوير، بصريا،

192
00:07:36,820 --> 00:07:38,920
أننا قد وضعت السلاسل
في شيء من هذا القبيل.

193
00:07:38,920 --> 00:07:41,970
وهذه المجموعة هي
واضح من حجم 26 المجموع.

194
00:07:41,970 --> 00:07:43,935
ويسمى الشيء
الجدول بشكل تعسفي.

195
00:07:43,935 --> 00:07:48,930
ولكن هذا هو مجرد التسليم فنان
ما قد يكون جدول التجزئة.

196
00:07:48,930 --> 00:07:52,799
>> لذلك جدول تجزئة الآن هو الذهاب الى
يكون هيكل البيانات على مستوى أعلى.

197
00:07:52,799 --> 00:07:54,840
في نهاية اليوم
نحن على وشك أن نرى لك

198
00:07:54,840 --> 00:07:58,700
يمكن تنفيذ جدول التجزئة، والتي
يشبه إلى حد كبير الخط تسجيل الوصول

199
00:07:58,700 --> 00:08:02,059
في هاكاثون مثل الكثير من هذه
استخدم الجدول لفرز الكتب الامتحان.

200
00:08:02,059 --> 00:08:03,850
لكن جدول تجزئة هو
هذا النوع من مستوى عال

201
00:08:03,850 --> 00:08:08,250
المفهوم الذي يمكن استخدام صفيف
تحت غطاء محرك السيارة لتنفيذها،

202
00:08:08,250 --> 00:08:11,890
أو أنها يمكن أن تستخدم قائمة طول، أو حتى
ربما بعض هياكل البيانات الأخرى.

203
00:08:11,890 --> 00:08:15,590
والآن هذا هو أخذ theme--
بعض من هذه المكونات الأساسية

204
00:08:15,590 --> 00:08:18,310
مثل مجموعة وهذا المبنى
منع الآن من قائمة طول

205
00:08:18,310 --> 00:08:21,740
ونرى ماذا يمكننا أن نبني
على رأس هؤلاء، مثل المكونات

206
00:08:21,740 --> 00:08:26,550
في وصفة، مما يجعل أكثر وأكثر
النتائج النهائية مثيرة للاهتمام ومفيدة.

207
00:08:26,550 --> 00:08:28,680
>> حتى مع جدول التجزئة
نحن قد تنفيذه

208
00:08:28,680 --> 00:08:32,540
في الذاكرة بالصور مثل هذا، ولكن
كيف يمكن فعلا أن تكون مشفرة عنه؟

209
00:08:32,540 --> 00:08:33,789
حسنا، ربما ببساطة هو هذا.

210
00:08:33,789 --> 00:08:38,270
وإذا كانت السعة في كل مباراة دولية، هو فقط
بعض constant-- على سبيل المثال 26،

211
00:08:38,270 --> 00:08:42,030
26 الحروف alphabet--
يمكن أن أسميه مائدتي متغير،

212
00:08:42,030 --> 00:08:45,630
وأود أن الادعاء بأن انا ذاهب الى
وضع النجوم في شار هناك، أو سلسلة.

213
00:08:45,630 --> 00:08:49,880
حتى انها بسيطة مثل هذا إذا كنت
تريد تنفيذ جدول تجزئة.

214
00:08:49,880 --> 00:08:51,490
وحتى الان، وهذا هو في الحقيقة مجرد صفيف.

215
00:08:51,490 --> 00:08:53,198
ولكن مرة أخرى، تجزئة
الجدول هو ما سنقوم الآن

216
00:08:53,198 --> 00:08:57,470
استدعاء نوع البيانات مجردة هذا فقط
نوع من الطبقات المفاهيمية على رأس

217
00:08:57,470 --> 00:09:00,780
شيء أكثر دنيوية
أود الآن صفيف.

218
00:09:00,780 --> 00:09:02,960
>> الآن، كيف نذهب
حول حل المشاكل؟

219
00:09:02,960 --> 00:09:06,980
حسنا، كان في وقت سابق أنا ترف
وجود مساحة كافية الجدول هنا

220
00:09:06,980 --> 00:09:09,460
كي أتمكن من وضع
مسابقات في أي مكان أريد.

221
00:09:09,460 --> 00:09:10,620
بحيث قد يذهب هنا.

222
00:09:10,620 --> 00:09:12,100
ZS قد يذهب هنا.

223
00:09:12,100 --> 00:09:13,230
السيدة قد يذهب هنا.

224
00:09:13,230 --> 00:09:14,740
ثم كان لي بعض المساحة الإضافية.

225
00:09:14,740 --> 00:09:18,740
ولكن هذا هو جزء من حق الغش
الآن بسبب هذا الجدول، إذا كنت حقا

226
00:09:18,740 --> 00:09:22,720
فكر في الأمر على النحو صفيف، هو فقط
ستكون بعض حجم ثابت.

227
00:09:22,720 --> 00:09:25,380
>> لذلك من الناحية الفنية، إذا أنا سحب
تصل مسابقة طالب آخر

228
00:09:25,380 --> 00:09:28,490
ونرى، أوه، هذا الشخص
الاسم يبدأ مع وللغاية،

229
00:09:28,490 --> 00:09:30,980
النوع الأول من تريد وضعه هناك.

230
00:09:30,980 --> 00:09:34,740
ولكن بمجرد أن وضعها هناك، وإذا
هذا الجدول يمثل في الواقع مجموعة،

231
00:09:34,740 --> 00:09:37,840
انا ذاهب الى أن تجاوز أو clobbering
مسابقة من هذا الطالب هو.

232
00:09:37,840 --> 00:09:38,340
أليس كذلك؟

233
00:09:38,340 --> 00:09:41,972
إذا كان هذا هو صفيف، يمكن شيء واحد فقط
تذهب في كل من هذه الخلايا أو العناصر.

234
00:09:41,972 --> 00:09:43,680
وذلك نوع من ديك
لانتقاء واختيار.

235
00:09:43,680 --> 00:09:45,735
>> الآن وقت سابق من النوع الأول من
خدع وفعل هذا أو أنا

236
00:09:45,735 --> 00:09:47,526
مجرد نوع من مكدسة
لها فوق بعضها البعض.

237
00:09:47,526 --> 00:09:49,170
ولكن هذا لن يطير في التعليمات البرمجية.

238
00:09:49,170 --> 00:09:52,260
فأين يمكن أن أضع
الطالب الثاني اسمه

239
00:09:52,260 --> 00:09:54,964
هو وإذا كان كل هذا
الجدول الفضاء المتاح؟

240
00:09:54,964 --> 00:09:57,880
ولقد استعملت ثلاث فتحات و
يبدو أن هناك فقط عدد قليل من الآخرين.

241
00:09:57,880 --> 00:09:58,959
ماذا يمكنك أن تفعل؟

242
00:09:58,959 --> 00:09:59,834
الجمهور: [غير مسموع]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID مالان: نعم.

245
00:10:01,315 --> 00:10:02,370
ربما دعونا فقط يبقيه بسيط.

246
00:10:02,370 --> 00:10:02,660
أليس كذلك؟

247
00:10:02,660 --> 00:10:04,243
فإنه لا يصلح حيث كنت تريد وضعه.

248
00:10:04,243 --> 00:10:07,450
لذلك أنا ذاهب لوضعها
من الناحية الفنية حيث ان يذهب باء.

249
00:10:07,450 --> 00:10:09,932
الآن، بالطبع، أنا بدأت
لطلاء نفسي في الزاوية.

250
00:10:09,932 --> 00:10:11,890
إذا كنت تحصل على طالب
اسمه هو في الواقع B،

251
00:10:11,890 --> 00:10:14,840
الآن ب سوف يتم نقلها قليلا
إلى الأمام، كما قد يحدث، نعم،

252
00:10:14,840 --> 00:10:17,530
إذا كان هذا هو B، والآن لديها للذهاب هنا.

253
00:10:17,530 --> 00:10:20,180
>> وحتى هذا بسرعة جدا
يمكن أن تصبح مشكلة،

254
00:10:20,180 --> 00:10:23,850
ولكن هذا الاسلوب الذي فعلا
ويشار إلى سبر الخطية،

255
00:10:23,850 --> 00:10:26,650
حيث كنت مجرد النظر الخاصة بك
مجموعة ليكون على طول الخط.

256
00:10:26,650 --> 00:10:29,680
وكنت مجرد نوع من التحقيق أو
فحص كل عنصر متاح

257
00:10:29,680 --> 00:10:31,360
تبحث عن بقعة المتاحة.

258
00:10:31,360 --> 00:10:34,010
وحالما تجد
واحد، كنت تسقطها في هناك.

259
00:10:34,010 --> 00:10:38,390
>> الآن، وسعر يولى الآن
لهذا الحل ما هو؟

260
00:10:38,390 --> 00:10:41,300
لدينا مجموعة وحجم ثابت،
وعندما أقوم بإدخال أسماء

261
00:10:41,300 --> 00:10:44,059
إلى ذلك، على الأقل في البداية، ما هو
إدارة الوقت من الإدراج

262
00:10:44,059 --> 00:10:46,350
لوضع الطلاب
مسابقات في الدلاء الصحيحة؟

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
يا كبير لماذا؟

265
00:10:50,002 --> 00:10:51,147
>> الجمهور: ن.

266
00:10:51,147 --> 00:10:52,480
DAVID مالان: سمعت يا كبير من ن.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
ليس صحيحا.

269
00:10:54,300 --> 00:10:56,490
ولكننا سوف ندف بعيدا
لماذا في لحظة فقط.

270
00:10:56,490 --> 00:10:57,702
ماذا يمكن أن يكون؟

271
00:10:57,702 --> 00:10:58,755
>> الجمهور: [غير مسموع]

272
00:10:58,755 --> 00:11:00,380
DAVID مالان: واسمحوا لي أن تفعل ذلك بصريا.

273
00:11:00,380 --> 00:11:04,720
ذلك ان هذا هو حرف S.

274
00:11:04,720 --> 00:11:05,604
>> الجمهور: انها واحدة.

275
00:11:05,604 --> 00:11:06,520
DAVID مالان: انها واحدة.

276
00:11:06,520 --> 00:11:06,710
أليس كذلك؟

277
00:11:06,710 --> 00:11:08,950
هذا هو صفيف، الذي
يعني أن علينا الوصول العشوائي.

278
00:11:08,950 --> 00:11:11,790
وإذا كنا نفكر في هذا
كما الصفر، وهذا 25،

279
00:11:11,790 --> 00:11:13,800
ونحن ندرك أنه،
أوه، وهنا بلدي مدخلات S،

280
00:11:13,800 --> 00:11:16,350
يمكنني تحويل بالتأكيد
S، طابعا ASCII،

281
00:11:16,350 --> 00:11:18,540
إلى الرقم المناظر
بين صفر و 25

282
00:11:18,540 --> 00:11:20,910
وبعد ذلك على الفور
وضعها حيث تنتمي.

283
00:11:20,910 --> 00:11:26,120
>> ولكن بطبيعة الحال، بمجرد أن نصل إلى
الشخص الثاني الذي هو الاسم هو A أو B أو C

284
00:11:26,120 --> 00:11:29,300
في النهاية، إذا كنت تستخدم و
الخطية التحقيق كحل بلدي،

285
00:11:29,300 --> 00:11:31,360
وقت تشغيل
الإدراج في أسوأ الحالات

286
00:11:31,360 --> 00:11:33,120
هو في الواقع تتحول الى الذهاب الى ماذا؟

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
وأنا لم أسمع من هنا
بشكل صحيح في وقت مبكر.

289
00:11:36,045 --> 00:11:36,920
الجمهور: [غير مسموع]

290
00:11:36,920 --> 00:11:41,620
DAVID مالان: هكذا هو ن بالفعل مرة واحدة
لديك مجموعة بيانات كبيرة بما فيه الكفاية.

291
00:11:41,620 --> 00:11:44,410
لذلك، من جهة، وإذا كان
مجموعة الخاصة بك كبيرة بما يكفي

292
00:11:44,410 --> 00:11:48,287
والبيانات الخاصة بك هو متفرق بما فيه الكفاية، كنت
الحصول على هذا الوقت الجميل المستمر.

293
00:11:48,287 --> 00:11:50,620
ولكن بمجرد أن تبدأ
الحصول على المزيد والمزيد من العناصر،

294
00:11:50,620 --> 00:11:53,200
ومجرد إحصائية تحصل
المزيد من الناس مع الرسالة

295
00:11:53,200 --> 00:11:56,030
وكما اسمهم أو الحرف
B، ويمكن لها ان

296
00:11:56,030 --> 00:11:57,900
تؤول إلى شيء أكثر الخطية.

297
00:11:57,900 --> 00:11:59,640
لذلك لم يكن مثاليا تماما.

298
00:11:59,640 --> 00:12:00,690
لذلك يمكننا أن نفعل ما هو أفضل؟

299
00:12:00,690 --> 00:12:03,210
>> كذلك، ما كان لدينا
حل قبل عندما كنا

300
00:12:03,210 --> 00:12:06,820
ترغب في الحصول على مزيد من الديناميكية
شيء من هذا القبيل مجموعة سمحت؟

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
الجمهور: [غير مسموع]

303
00:12:08,960 --> 00:12:10,030
DAVID مالان: ماذا نقدم؟

304
00:12:10,030 --> 00:12:10,530
نعم.

305
00:12:10,530 --> 00:12:11,430
حتى قائمة مرتبطة.

306
00:12:11,430 --> 00:12:14,430
حسنا، دعونا نرى ما هو مرتبط
القائمة قد تفعل بالنسبة لنا بدلا من ذلك.

307
00:12:14,430 --> 00:12:17,630
حسنا، اسمحوا لي أن أقترح أن نحن
رسم الصورة كما يلي.

308
00:12:17,630 --> 00:12:19,620
الآن هذا هو مختلفة
صورة من مثال

309
00:12:19,620 --> 00:12:24,750
من نص مختلف، في الواقع، أن
هو في الواقع باستخدام مجموعة من حجم 31.

310
00:12:24,750 --> 00:12:28,220
وهذا الكاتب ببساطة
قررت تجزئة السلاسل

311
00:12:28,220 --> 00:12:32,430
لا تعتمد على أسماء الشخص،
ولكن على أساس تواريخ ميلاد لهم.

312
00:12:32,430 --> 00:12:35,680
بغض النظر عن الشهر، وأحسب
إذا كنت ولدت في الأول من شهر

313
00:12:35,680 --> 00:12:39,580
أو 31 من كل شهر، والكاتب
سوف تجزئة على أساس تلك القيمة،

314
00:12:39,580 --> 00:12:44,154
وذلك لنشر أسماء خارج قليلا
أكثر من مجرد 26 نقاط قد تسمح.

315
00:12:44,154 --> 00:12:47,320
وربما انها أكثر اتساقا الصغير
من الذهاب مع حروف أبجدية،

316
00:12:47,320 --> 00:12:50,236
لأنه بطبيعة الحال هناك على الارجح
المزيد من الناس في العالم مع أسماء

317
00:12:50,236 --> 00:12:54,020
أن تبدأ مع من المؤكد
بعض الحروف الأخرى من الأبجدية.

318
00:12:54,020 --> 00:12:56,380
ولذلك ربما يكون هذا هو قليلا
أكثر تجانسا، على افتراض

319
00:12:56,380 --> 00:12:58,640
توزيع موحد
من الأطفال عبر مدة شهر.

320
00:12:58,640 --> 00:12:59,990
>> ولكن، بطبيعة الحال، هذا لا يزال غير كامل.

321
00:12:59,990 --> 00:13:00,370
أليس كذلك؟

322
00:13:00,370 --> 00:13:01,370
نحن لها الاصطدامات.

323
00:13:01,370 --> 00:13:04,680
العديد من الناس في هذا
هيكل البيانات لا تزال

324
00:13:04,680 --> 00:13:08,432
لها نفس تاريخ الميلاد على الأقل
كنت بغض النظر عن الشهر.

325
00:13:08,432 --> 00:13:09,640
ولكن ما قام به المؤلف؟

326
00:13:09,640 --> 00:13:13,427
حسنا، يبدو أن لدينا مجموعة
على الجانب الأيسر مرسومة عموديا،

327
00:13:13,427 --> 00:13:15,010
ولكن هذا مجرد التسليم فنان.

328
00:13:15,010 --> 00:13:18,009
لا يهم ما هو الاتجاه الذي
رسم صفيف، انها لا تزال صفيف.

329
00:13:18,009 --> 00:13:20,225
ما هذا مجموعة من ما يبدو؟

330
00:13:20,225 --> 00:13:21,500
>> الجمهور: قائمة مرتبطة.

331
00:13:21,500 --> 00:13:21,650
>> DAVID مالان: نعم.

332
00:13:21,650 --> 00:13:23,490
يبدو انها ل
مجموعة من قائمة مرتبطة.

333
00:13:23,490 --> 00:13:26,490
ذلك مرة أخرى، إلى هذه النقطة من نوع
لاستخدام هذه البيانات الهياكل الآن

334
00:13:26,490 --> 00:13:28,550
كما أن المكونات أكثر
حلول مثيرة للاهتمام،

335
00:13:28,550 --> 00:13:30,862
يمكنك أن تأخذ على الاطلاق
أساسية، مثل صفيف،

336
00:13:30,862 --> 00:13:33,320
ثم تأخذ شيئا أكثر
مثيرة للاهتمام مثل قائمة مرتبطة

337
00:13:33,320 --> 00:13:36,660
وحتى الجمع بينهما إلى حتى
بنية بيانات أكثر إثارة للاهتمام.

338
00:13:36,660 --> 00:13:39,630
وبالفعل، فإن هذا من شأنه أيضا
ان يسمى جدول التجزئة،

339
00:13:39,630 --> 00:13:42,610
حيث المصفوفة هي
حقا جدول التجزئة،

340
00:13:42,610 --> 00:13:45,600
إلا أن لديه جدول التجزئة
سلاسل، إذا جاز التعبير،

341
00:13:45,600 --> 00:13:50,220
التي يمكن أن تنمو أو يتقلص بناء على
عدد من العناصر التي تريد إدراجها.

342
00:13:50,220 --> 00:13:52,990
>> الآن، وفقا لذلك، ما هو
وتعمل الساعة الآن؟

343
00:13:52,990 --> 00:13:58,030
إذا كنت ترغب في إدراج شخص
الذين ميلاده هو 31 أكتوبر

344
00:13:58,030 --> 00:13:59,040
أين هو أو هي تذهب؟

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
حسنا.

347
00:14:01,030 --> 00:14:02,819
في أسفل جدا حيث تقول 31.

348
00:14:02,819 --> 00:14:03,610
وهذا هو الكمال.

349
00:14:03,610 --> 00:14:05,060
كان ذلك الوقت مستمر.

350
00:14:05,060 --> 00:14:08,760
ولكن ماذا إذا وجدنا شخص آخر
الذي هو، دعونا نرى عيد ميلاد،

351
00:14:08,760 --> 00:14:10,950
أكتوبر ونوفمبر، 31 كانون الأول؟

352
00:14:10,950 --> 00:14:12,790
حيث انه أو انها سوف تذهب؟

353
00:14:12,790 --> 00:14:13,290
نفس الشيء.

354
00:14:13,290 --> 00:14:13,970
على الرغم من خطوتين.

355
00:14:13,970 --> 00:14:15,303
وهذا مستمر على الرغم أليس كذلك؟

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
حسنا.

358
00:14:16,860 --> 00:14:17,840
في هذه اللحظة هو عليه.

359
00:14:17,840 --> 00:14:20,570
ولكن في الحالة العامة،
والمزيد من الناس نضيف،

360
00:14:20,570 --> 00:14:23,790
احتماليا، نحن ذاهبون
للحصول على المزيد والمزيد من الاصطدامات.

361
00:14:23,790 --> 00:14:26,820
>> الآن هذا هو قليلا
أفضل لأنه من الناحية التقنية

362
00:14:26,820 --> 00:14:34,580
الآن سلاسل بلدي يمكن أن يكون في
أسوأ الحالات إلى متى؟

363
00:14:34,580 --> 00:14:38,890
إذا كنت أدخل ن الناس إلى هذا أكثر
بنية بيانات متطورة، ن الناس،

364
00:14:38,890 --> 00:14:41,080
في أسوأ الحالات انها ستكون ن.

365
00:14:41,080 --> 00:14:41,815
لماذا؟

366
00:14:41,815 --> 00:14:43,332
>> الجمهور: لأنه إذا كان الجميع
لديه نفس عيد ميلاد،

367
00:14:43,332 --> 00:14:44,545
انهم ذاهبون ليكون سطر واحد.

368
00:14:44,545 --> 00:14:45,420
DAVID مالان: الكمال.

369
00:14:45,420 --> 00:14:47,480
قد تكون مفتعلة قليلا،
ولكن حقا في أسوأ الحالات،

370
00:14:47,480 --> 00:14:50,117
إذا كان الجميع لديه نفس عيد ميلاد،
بالنظر إلى المدخلات لديك،

371
00:14:50,117 --> 00:14:51,950
وأنت تسير لدينا
سلسلة طويلة اسع.

372
00:14:51,950 --> 00:14:54,241
وهكذا، يمكن أن نسميها
تجزئة الجدول، ولكن في الحقيقة انها ل

373
00:14:54,241 --> 00:14:56,810
مجرد قائمة ضخمة مرتبطة
مجموعة كبيرة من مساحة مهدرة.

374
00:14:56,810 --> 00:15:00,460
ولكن بشكل عام، إذا افترضنا أن
على الأقل أعياد الميلاد هي uniform--

375
00:15:00,460 --> 00:15:01,750
وربما لا يكون.

376
00:15:01,750 --> 00:15:02,587
أنا صنع ما يصل.

377
00:15:02,587 --> 00:15:04,420
ولكن لو افترضنا، ل
من أجل مناقشة

378
00:15:04,420 --> 00:15:07,717
أنهم، ثم من الناحية النظرية، إذا
هذا هو التمثيل العمودي

379
00:15:07,717 --> 00:15:11,050
للمجموعة، بالاضافة الى ذلك الحين نأمل كنت
ذاهب للحصول على سلاسل التي هي، كما تعلمون،

380
00:15:11,050 --> 00:15:15,880
تقريبا نفس طول فيها كل من
هذه يمثل يوم من الشهر.

381
00:15:15,880 --> 00:15:19,930
>> الآن إذا كان هناك 31 يوما في الشهر،
وهذا يعني وقتي تشغيل حقا

382
00:15:19,930 --> 00:15:25,230
هو يا كبير من ن أكثر من 31، والتي
يشعر على نحو أفضل من الخطية.

383
00:15:25,230 --> 00:15:27,950
ولكن ما كان أحد لدينا
الالتزامات أسبوعين

384
00:15:27,950 --> 00:15:31,145
منذ متى جاء إلى التعبير عن
وقت التشغيل خوارزمية؟

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
مجرد إلقاء نظرة فقط على المدى ذات الترتيب.

387
00:15:35,190 --> 00:15:35,690
أليس كذلك؟

388
00:15:35,690 --> 00:15:37,400
31 من المفيد بالتأكيد.

389
00:15:37,400 --> 00:15:39,610
ولكن هذا لا يزال يا كبير من ن.

390
00:15:39,610 --> 00:15:41,730
ولكن واحدا من المواضيع
المشكلة تعيين خمسة

391
00:15:41,730 --> 00:15:43,950
سيكون ل
نعترف بأن الاطلاق،

392
00:15:43,950 --> 00:15:47,320
مقارب، نظريا
هذه البنية البيانات

393
00:15:47,320 --> 00:15:50,470
ليس أفضل من مجرد
قائمة واحدة ضخمة مرتبطة.

394
00:15:50,470 --> 00:15:53,550
وبالفعل، في أسوأ الحالات، وهذا
قد تؤول جدول التجزئة إلى ذلك.

395
00:15:53,550 --> 00:15:57,620
>> ولكن في العالم الحقيقي، معنا البشر
أن أجهزة ماكينتوش الخاصة أو أجهزة الكمبيوتر أو أيا كان

396
00:15:57,620 --> 00:16:01,240
وتشغل العالم الحقيقي
برامج على بيانات العالم الحقيقي،

397
00:16:01,240 --> 00:16:03,260
الخوارزمية التي أنت ذاهب لتفضل؟

398
00:16:03,260 --> 00:16:09,180
واحد أن يأخذ خطوات نهاية أو
واحد أن يأخذ مقسمة ن بنسبة 31 خطوات

399
00:16:09,180 --> 00:16:12,900
العثور على بعض قطعة من البيانات أو
للبحث عن بعض المعلومات؟

400
00:16:12,900 --> 00:16:16,580
أعني، بالتأكيد على 31 طرازا
الفرق في العالم الحقيقي.

401
00:16:16,580 --> 00:16:18,540
هو 31 مرات أسرع.

402
00:16:18,540 --> 00:16:20,880
ونحن البشر هي بالتأكيد
سوف نقدر ذلك.

403
00:16:20,880 --> 00:16:23,004
>> حتى ندرك الانقسام
هناك بين الواقع

404
00:16:23,004 --> 00:16:25,920
نتحدث عن الأشياء نظريا
ومقارب التي بالتأكيد

405
00:16:25,920 --> 00:16:28,760
له قيمة كما رأينا،
ولكن في العالم الحقيقي،

406
00:16:28,760 --> 00:16:32,930
إذا كنت تهتم فقط جعل
سعيدة الإنسان للمدخلات العامة،

407
00:16:32,930 --> 00:16:36,010
قد ترغب أيضا جدا لقبول
حقيقة، نعم، هذا هو خطي،

408
00:16:36,010 --> 00:16:38,360
ولكن من 31 مرات أسرع
قد يكون من الخطية.

409
00:16:38,360 --> 00:16:41,610
والأفضل من ذلك، ليس لدينا فقط ل
تفعل شيئا التعسفي مثل تاريخ الميلاد،

410
00:16:41,610 --> 00:16:44,030
نحن يمكن أن تنفق قليلا
المزيد من الوقت والذكاء

411
00:16:44,030 --> 00:16:47,140
ونفكر في ما يمكن القيام به،
أعطيت اسم الشخص وربما

412
00:16:47,140 --> 00:16:50,130
تاريخ الميلاد إلى الجمع بين تلك
المكونات لمعرفة شيء

413
00:16:50,130 --> 00:16:52,720
هذا هو حقا أكثر
موحدة وأقل جاجي،

414
00:16:52,720 --> 00:16:56,250
إذا جاز التعبير من هذه الصورة.
يقترح حاليا قد يكون.

415
00:16:56,250 --> 00:16:57,750
كيف يمكن أن ننفذ هذا في التعليمات البرمجية؟

416
00:16:57,750 --> 00:17:00,280
حسنا، اسمحوا لي أن أقترح أن نحن
مجرد استعارة بعض تركيب قمنا

417
00:17:00,280 --> 00:17:01,799
تستخدم بضع مرات حتى الآن.

418
00:17:01,799 --> 00:17:03,590
وانا ذاهب الى تعريف
عقدة، والذي مرة أخرى

419
00:17:03,590 --> 00:17:06,812
هو مصطلح عام للبعض فقط
حاوية لبعض هياكل البيانات.

420
00:17:06,812 --> 00:17:09,020
انا ذاهب الى أقترح أن
سلسلة يجري في هناك.

421
00:17:09,020 --> 00:17:11,369
ولكن نحن ذاهبون للبدء في اتخاذ
تلك العجلات تدريب حالا الآن.

422
00:17:11,369 --> 00:17:13,230
>> أي مكتبة CS50 المزيد
حقا، إلا إذا كنت تريد

423
00:17:13,230 --> 00:17:15,230
لاستخدامها لنهائي الخاص
المشروع، والتي على ما يرام،

424
00:17:15,230 --> 00:17:18,569
ولكن الآن نحن ذاهبون إلى التراجع و
ستارة ويقولون انها مجرد نجم شار.

425
00:17:18,569 --> 00:17:22,069
لذلك هناك كلمة ستكون
اسم الشخص المعني.

426
00:17:22,069 --> 00:17:25,079
والآن لدي صلة
هنا إلى العقدة التالية

427
00:17:25,079 --> 00:17:28,170
بحيث تمثل هذه
كل من العقد

428
00:17:28,170 --> 00:17:30,950
في سلسلة، ويحتمل،
من قائمة مرتبطة.

429
00:17:30,950 --> 00:17:34,090
>> والآن كيف يمكنني الإعلان
جدول التجزئة نفسها؟

430
00:17:34,090 --> 00:17:36,660
كيف يعلن هذا الهيكل كله؟

431
00:17:36,660 --> 00:17:40,960
حسنا، حقا، مثل الكثير اعتدت مؤشر
لمجرد العنصر الأول من القائمة

432
00:17:40,960 --> 00:17:44,510
من قبل، وبالمثل يمكن أن أقول فقط
أنا فقط بحاجة إلى مجموعة من المؤشرات

433
00:17:44,510 --> 00:17:46,270
لتنفيذ هذا الجدول التجزئة كله.

434
00:17:46,270 --> 00:17:49,484
أنا ذاهب لديها مجموعة
دعا جدول لجدول التجزئة.

435
00:17:49,484 --> 00:17:50,900
انها سوف تكون ذات قدرة الحجم.

436
00:17:50,900 --> 00:17:52,525
هذه هي الطريقة العديد من العناصر يمكن أن يصلح في ذلك.

437
00:17:52,525 --> 00:17:56,180
ولكل من تلك العناصر في هذا
مجموعة سيكون نجم العقدة.

438
00:17:56,180 --> 00:17:56,810
لماذا؟

439
00:17:56,810 --> 00:18:00,160
حسنا، في هذه الصورة، ما أنا
تنفيذ جدول التجزئة كما

440
00:18:00,160 --> 00:18:04,330
بفعالية في بداية هي مجرد
هذه المجموعة التي كانت لدينا رسمها عموديا،

441
00:18:04,330 --> 00:18:06,820
كل المربعات التي
يمثل مؤشر.

442
00:18:06,820 --> 00:18:09,170
أن تلك التي لديها خطوط مائلة
من خلال منهم فقط اغية.

443
00:18:09,170 --> 00:18:11,410
وتلك التي لديها
سهام الذهاب إلى اليمين

444
00:18:11,410 --> 00:18:16,140
هي مؤشرات فعلية إلى العقد الفعلية،
ولهذا بداية لقائمة مرتبطة.

445
00:18:16,140 --> 00:18:19,050
>> حتى هنا، إذن، هو كيف يمكننا
تنفيذ جدول التجزئة التي

446
00:18:19,050 --> 00:18:21,580
تنفذ تسلسل منفصل.

447
00:18:21,580 --> 00:18:22,840
الآن يمكننا أن نفعل أفضل؟

448
00:18:22,840 --> 00:18:25,632
كل الحق عدت المرة الأخيرة التي
نحن يمكن أن يحقق الزمن المستمر.

449
00:18:25,632 --> 00:18:27,381
والنوع الأول من أعطاك
وقت ثابت هنا،

450
00:18:27,381 --> 00:18:29,850
ولكن بعد ذلك قال لا حقا
وقت ثابت لأنه ما زال

451
00:18:29,850 --> 00:18:31,890
تعتمد على مجموعه
عدد من العناصر

452
00:18:31,890 --> 00:18:34,500
كنت في إدخال
بنية البيانات.

453
00:18:34,500 --> 00:18:35,980
ولكن لنفترض فعلنا هذا.

454
00:18:35,980 --> 00:18:39,550
اسمحوا لي أن أعود إلى الشاشة أكثر من هنا.

455
00:18:39,550 --> 00:18:44,520
اسمحوا لي أيضا هذا المشروع هنا، واضحة
الشاشة، وأعتقد أنني فعلت ذلك.

456
00:18:44,520 --> 00:18:49,300
لنفترض أنني أردت أن إدراج اسم
Daven في داخل بنية البيانات الخاصة بي.

457
00:18:49,300 --> 00:18:52,100
>> لذلك أريد أن إدراج سلسلة
Daven في بنية البيانات.

458
00:18:52,100 --> 00:18:54,370
ماذا لو كنت لا تستخدم
تجزئة الجدول، ولكن يمكنني استخدام

459
00:18:54,370 --> 00:18:56,980
شيء أن يكون أكثر شجرة شبيهة
مثل شجرة العائلة، حيث

460
00:18:56,980 --> 00:18:59,670
لديك بعض جذور في
أعلى ثم العقد والأوراق

461
00:18:59,670 --> 00:19:01,440
أن تذهب إلى أسفل وإلى الخارج.

462
00:19:01,440 --> 00:19:04,450
لنفترض إذن أن أنا
تريد إدراجه في Daven

463
00:19:04,450 --> 00:19:06,430
إلى ما هو حاليا قائمة فارغة.

464
00:19:06,430 --> 00:19:09,780
انا ذاهب للقيام بما يلي: أنا
الذهاب الى خلق عقدة في هذه العائلة

465
00:19:09,780 --> 00:19:15,170
شجرة تشبه بنية البيانات التي تبدو
قليلا من هذا القبيل، كل واحدة منها

466
00:19:15,170 --> 00:19:19,640
والمستطيلات، دعنا نقول،
في الوقت الراهن 26 عناصر فيه.

467
00:19:19,640 --> 00:19:21,650
وكل من الخلايا
في هذه المجموعة هو الذهاب

468
00:19:21,650 --> 00:19:23,470
لتمثيل حرف من الأبجدية.

469
00:19:23,470 --> 00:19:28,190
>> على وجه التحديد، وانا ذاهب لعلاج
هذا هو A، ثم B، C بعد ذلك، ثم D،

470
00:19:28,190 --> 00:19:29,310
هذا واحد هنا.

471
00:19:29,310 --> 00:19:32,940
لذلك هذا هو الذهاب الى فعال
تمثل الرسالة د.

472
00:19:32,940 --> 00:19:36,040
ولكن لإدراج كافة في Daven
اسم يجب أن أفعل أكثر قليلا.

473
00:19:36,040 --> 00:19:37,840
لذلك أنا ذاهب أول من البعثرة، إذا جاز التعبير.

474
00:19:37,840 --> 00:19:41,049
انا ذاهب للنظر في الرسالة الأولى
في لDaven التي من الواضح أن D،

475
00:19:41,049 --> 00:19:42,840
وانا ذاهب الى تخصيص
عقدة التي تبدو

476
00:19:42,840 --> 00:19:45,570
مثل this-- مستطيل كبير كبير
بما يكفي لتناسب الأبجدية كلها.

477
00:19:45,570 --> 00:19:47,140
>> الآن يتم التطوير.

478
00:19:47,140 --> 00:19:49,720
الآن A. D-A-V-E-N هو الهدف.

479
00:19:49,720 --> 00:19:51,220
حتى الآن ما أنا ذاهب الى القيام به هو هذا.

480
00:19:51,220 --> 00:19:54,027
وسرعان ما بدأ إشعار D
وليس هناك مؤشر هناك.

481
00:19:54,027 --> 00:19:56,860
انها القيم القمامة في الوقت الراهن،
أو أنني قد تهيئة إلى قيمة خالية.

482
00:19:56,860 --> 00:19:59,630
ولكن اسمحوا لي الاستمرار مع
هذه فكرة بناء شجرة.

483
00:19:59,630 --> 00:20:04,260
اسمحوا لي أن تخصص آخر واحد من هؤلاء
العقد التي لديها 26 عناصر فيه.

484
00:20:04,260 --> 00:20:05,150
>> وأنت تعرف لماذا؟

485
00:20:05,150 --> 00:20:09,130
إذا كان هذا هو مجرد عقدة في الذاكرة
أنا خلقت مع malloc، باستخدام البنية

486
00:20:09,130 --> 00:20:11,240
كما سنرى قريبا،
انا ذاهب الى القيام this--

487
00:20:11,240 --> 00:20:14,450
انا ذاهب الى رسم السهم من
الشيء الذي يمثل D الأسفل

488
00:20:14,450 --> 00:20:15,860
لهذه العقدة الجديدة.

489
00:20:15,860 --> 00:20:19,240
والآن، لأول مرة المقبل
حرف في اسم Daven و

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- انا ذاهب الى المضي قدما
ولفت عقدة أخرى من هذا القبيل،

491
00:20:24,150 --> 00:20:30,150
حيث أن عناصر V هنا، والتي
سنقوم رسم ليصيح instance--.

492
00:20:30,150 --> 00:20:31,020
نحن لن يوجه هناك.

493
00:20:31,020 --> 00:20:31,936
انها سوف تذهب هنا.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> ثم نحن في طريقنا ل
نعتبر هذا V.

496
00:20:35,712 --> 00:20:44,920
ثم إلى هنا ونحن في طريقنا إلى مؤشر
نزولا من الخامس إلى ما نحن سنعتبر E.

497
00:20:44,920 --> 00:20:50,100
ثم من هنا نحن ذاهبون ل
الذهاب لديها واحدة من هذه العقد هنا.

498
00:20:50,100 --> 00:20:52,930
والآن لدينا سؤال للإجابة.

499
00:20:52,930 --> 00:20:57,840
أحتاج إلى حد ما يدل على أن
نحن في نهاية السلسلة Daven.

500
00:20:57,840 --> 00:20:59,490
حتى أتمكن من مجرد ترك الأمر لاغيا.

501
00:20:59,490 --> 00:21:02,670
>> ولكن ماذا لو كان لدينا في Daven
الاسم الكامل أيضا، والتي

502
00:21:02,670 --> 00:21:04,280
هو، كما قلنا، دافنبورت؟

503
00:21:04,280 --> 00:21:06,970
فما هو إذا Daven
في الواقع فرعية،

504
00:21:06,970 --> 00:21:08,960
بادئة سلسلة أطول من ذلك بكثير؟

505
00:21:08,960 --> 00:21:11,450
لا يمكننا فقط بشكل دائم
ناهيك يسير

506
00:21:11,450 --> 00:21:14,410
للذهاب هناك، لأننا يمكن أن
أبدا إدراج كلمة مثل دافنبورت

507
00:21:14,410 --> 00:21:15,840
في هذا الهيكل بيانات

508
00:21:15,840 --> 00:21:19,560
>> وذلك ما يمكن أن نقوم به بدلا من ذلك هو
معالجة كل من هذه العناصر

509
00:21:19,560 --> 00:21:22,170
كما ربما وجود اثنين
عناصر داخل منهم.

510
00:21:22,170 --> 00:21:24,810
واحد هو مؤشر، في الواقع،
كما كنت تفعل.

511
00:21:24,810 --> 00:21:27,100
لذلك كل من هذه الصناديق
ليس من خلية واحدة فقط.

512
00:21:27,100 --> 00:21:29,855
ولكن ماذا لو أعلى
one-- القاع واحد

513
00:21:29,855 --> 00:21:32,230
ستكون باطلة، ل
لا يوجد دافنبورت فقط حتى الآن.

514
00:21:32,230 --> 00:21:34,197
ماذا لو رأس واحد
هي بعض القيمة الخاصة؟

515
00:21:34,197 --> 00:21:36,530
وأنه سيكون قليلا
من الصعب استدراجه هذا الحجم.

516
00:21:36,530 --> 00:21:38,130
ولكن لنفترض انها مجرد علامة الاختيار.

517
00:21:38,130 --> 00:21:38,920
تحقق.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N هو سلسلة
في هذا الهيكل البيانات.

519
00:21:44,230 --> 00:21:48,350
>> وفي الوقت نفسه، إذا كان لدي المزيد من المساحة
هنا، يمكن أن أفعله P-O-R-T،

520
00:21:48,350 --> 00:21:52,650
وأنا قد وضعت الاختيار في العقدة
الذي يحتوي على الحرف T في النهاية.

521
00:21:52,650 --> 00:21:55,460
لذلك هذا هو نطاق واسع
هيكل البيانات المظهر تعقيدا.

522
00:21:55,460 --> 00:21:57,210
وعلى خط اليد بلدي
بالتأكيد لا يساعد.

523
00:21:57,210 --> 00:22:00,043
ولكن إذا أردت أن أدخل شيئا
آخر، والنظر في ما سنفعله.

524
00:22:00,043 --> 00:22:03,370
إذا أردنا أن نضع ديفيد عام،
كنا اتبع نفس المنطق، D-A-V،

525
00:22:03,370 --> 00:22:08,802
ولكن الآن أود أن أشير في القادم
وليس من عنصر E، ولكن من أنا لD.

526
00:22:08,802 --> 00:22:10,760
لذلك هناك ستكون
أكثر من العقد في هذه الشجرة.

527
00:22:10,760 --> 00:22:12,325
نحن ذاهبون الى دعوة malloc أكثر.

528
00:22:12,325 --> 00:22:14,700
لكنني لا تريد أن تجعل من
فوضى كاملة في هذه الصورة.

529
00:22:14,700 --> 00:22:17,710
لذلك دعونا ننظر بدلا من ذلك في واحدة
التي تم صياغتها قبل

530
00:22:17,710 --> 00:22:21,810
مثل هذا لا مع وزارة النقل، وزارة النقل،
النقاط، ولكن المصفوفات يختصر فقط.

531
00:22:21,810 --> 00:22:23,950
ولكن كل من العقد
في هذه الشجرة يصل هنا

532
00:22:23,950 --> 00:22:26,700
يمثل نفسه thing--
مجموعة راي من حجم 26.

533
00:22:26,700 --> 00:22:28,860
>> أو إذا كنا نريد أن نكون
السليم حقا الآن، ما

534
00:22:28,860 --> 00:22:30,790
إذا كان اسم شخص ما باعتباره
الفاصلة العليا، دعونا

535
00:22:30,790 --> 00:22:35,560
نفترض أن كل عقدة لديه في الواقع
مثل 27 الفهارس في ذلك، وليس 26 فقط.

536
00:22:35,560 --> 00:22:42,020
حتى الآن هذه ستكون بيانات
هيكل يسمى trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
وTRIE، التي يفترض
تاريخيا اسم ذكي للشجرة

538
00:22:46,120 --> 00:22:49,040
هذا هو الأمثل ل
استرجاعها، والتي بالطبع،

539
00:22:49,040 --> 00:22:50,870
هو مكتوبة مع I-E لذلك فمن TRIE.

540
00:22:50,870 --> 00:22:52,710
ولكن هذا هو تاريخ TRIE.

541
00:22:52,710 --> 00:22:55,860
>> لذلك هو TRIE هذه البيانات تشبه شجرة
هيكل وكأنه شجرة العائلة

542
00:22:55,860 --> 00:22:57,510
أن يتصرف في نهاية المطاف من هذا القبيل.

543
00:22:57,510 --> 00:23:00,890
وهنا هو مجرد مثال آخر ل
مجمله مجموعة من أسماء أشخاص آخرين.

544
00:23:00,890 --> 00:23:03,540
ولكن السؤال الآن
في جهة ما لديهم

545
00:23:03,540 --> 00:23:08,070
حصلنا عن طريق إدخال يمكن القول أكثر
بنية بيانات معقدة، واحدة،

546
00:23:08,070 --> 00:23:09,870
بصراحة، يستخدم الكثير من الذاكرة.

547
00:23:09,870 --> 00:23:11,703
>> لأنه حتى وإن،
في هذه اللحظة، أنا فقط

548
00:23:11,703 --> 00:23:15,050
باستخدام مؤشر D'S و
ألف والخامس والخانات وم،

549
00:23:15,050 --> 00:23:16,700
أنا إضاعة من هيك الكثير من الذاكرة.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
ولكن أين أقضي مورد واحد،
أنا أميل إلى لا تستعيد آخر.

552
00:23:22,660 --> 00:23:26,020
حتى إذا أقضي المزيد من المساحة،
ما هو على الارجح الأمل؟

553
00:23:26,020 --> 00:23:27,407
أن أقضي أقل ما؟

554
00:23:27,407 --> 00:23:28,240
الجمهور: وقت أقل.

555
00:23:28,240 --> 00:23:28,990
DAVID مالان: الزمان.

556
00:23:28,990 --> 00:23:30,320
الآن ماذا يمكن أن يكون؟

557
00:23:30,320 --> 00:23:33,880
حسنا، ما هو الإدراج
الوقت، من حيث يا كبير الآن،

558
00:23:33,880 --> 00:23:37,660
من اسم مثل Daven
أو دافنبورت أو ديفيد؟

559
00:23:37,660 --> 00:23:39,340
كذلك، كان Daven خمس خطوات.

560
00:23:39,340 --> 00:23:42,350
سوف تكون دافنبورت تسع خطوات،
لذلك سيكون المزيد من الخطوات القليلة.

561
00:23:42,350 --> 00:23:44,250
سوف يكون ديفيد خمس خطوات كذلك.

562
00:23:44,250 --> 00:23:47,230
حتى تلك هي ملموسة
أرقام، ولكن بالتأكيد هناك

563
00:23:47,230 --> 00:23:49,550
الحد الأعلى ل
طول اسم شخص ما.

564
00:23:49,550 --> 00:23:52,240
وبالفعل، في مشكلة
مجموعات من خمس مواصفات،

565
00:23:52,240 --> 00:23:54,050
نحن ذاهبون الى اقتراح
أنه شيء

566
00:23:54,050 --> 00:23:55,470
هذا هو حرفا 40-بعض ونيف.

567
00:23:55,470 --> 00:23:58,180
>> واقعيا، لا أحد لديه
اسم طويل بلا حدود،

568
00:23:58,180 --> 00:24:01,542
وهو ما يعني أن طول
الاسم أو طول سلسلة أننا قد

569
00:24:01,542 --> 00:24:03,750
لدينا يقين دولة
هيكل يمكن القول ماذا؟

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
انها ثابتة.

572
00:24:06,250 --> 00:24:06,430
أليس كذلك؟

573
00:24:06,430 --> 00:24:09,310
قد يكون ثابت كبير مثل
40-شيء، وإنما هو مستمر.

574
00:24:09,310 --> 00:24:13,752
وأنه لا يوجد لديه الاعتماد على كم
أسماء أخرى في هذا الهيكل البيانات.

575
00:24:13,752 --> 00:24:15,460
وبعبارة أخرى، إذا أنا
أردت أن أدخل الآن

576
00:24:15,460 --> 00:24:20,540
كولتون أو جبريل أو روب أو Zamyla أو
أليسون أو بليندا أو أي أسماء أخرى

577
00:24:20,540 --> 00:24:23,940
من الموظفين في هذه البيانات
هيكل، هو إدارة الوقت

578
00:24:23,940 --> 00:24:26,750
من إدراج أسماء أخرى
سيكون على كل أثر

579
00:24:26,750 --> 00:24:30,220
من قبل كيف العديد من العناصر الأخرى ل
في بنية البيانات بالفعل؟

580
00:24:30,220 --> 00:24:31,040
انها ليست.

581
00:24:31,040 --> 00:24:31,540
أليس كذلك؟

582
00:24:31,540 --> 00:24:36,150
لأننا باستخدام فعال
هذه البعثرة الجدول متعددة الطبقات.

583
00:24:36,150 --> 00:24:38,280
ووقت تشغيل
أي من هذه العمليات

584
00:24:38,280 --> 00:24:41,510
لا تعتمد على عدد من
العناصر التي هي في بنية البيانات

585
00:24:41,510 --> 00:24:43,090
أو أن تسير في نهاية المطاف
أن تكون في بنية البيانات،

586
00:24:43,090 --> 00:24:44,714
ولكن على طول ما على وجه التحديد؟

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> سلسلة كونه
المدرجة، والتي لا تجعل

589
00:24:49,200 --> 00:24:52,580
هذا الثابت مقارب
يا كبير time-- واحد.

590
00:24:52,580 --> 00:24:54,720
وبصراحة، فقط في
في العالم الحقيقي، وهذا

591
00:24:54,720 --> 00:24:58,380
يعني إدخال يأخذ اسم Daven ل
مثل خمس خطوات، أو تسعة دافنبورت

592
00:24:58,380 --> 00:25:00,100
الخطوات، أو ديفيد خمس خطوات.

593
00:25:00,100 --> 00:25:03,071
هذا الرتق صغيرة مرة على التوالي.

594
00:25:03,071 --> 00:25:05,320
و، في الواقع، وهذا هو غاية
شيء جيد، وخصوصا عندما

595
00:25:05,320 --> 00:25:08,126
انها لا تعتمد على مجموع
عدد العناصر في هناك.

596
00:25:08,126 --> 00:25:10,500
فكيف يمكن أن نطبق هذا
نوع من الهيكل في الرمز؟

597
00:25:10,500 --> 00:25:12,900
انها اكثر قليلا
مجمع، ولكن لا يزال انها

598
00:25:12,900 --> 00:25:15,050
مجرد تطبيق
اللبنات الأساسية.

599
00:25:15,050 --> 00:25:17,830
انا ذاهب الى إعادة تعريف
عقدة لنا على النحو التالي:

600
00:25:17,830 --> 00:25:21,100
منطقي يسمى word-- وهذا
يمكن أن يسمى أي شيء.

601
00:25:21,100 --> 00:25:23,970
ولكن منطقي يمثل
ما وجهت باعتباره علامة الاختيار.

602
00:25:23,970 --> 00:25:24,490
نعم.

603
00:25:24,490 --> 00:25:26,720
هذه هي نهاية سلسلة
في هذا الهيكل البيانات.

604
00:25:26,720 --> 00:25:30,702
>> وبطبيعة الحال، نجم العقدة
هناك إشارة إلى الأطفال.

605
00:25:30,702 --> 00:25:32,410
وبالفعل، تماما مثل
شجرة العائلة، ل

606
00:25:32,410 --> 00:25:34,370
ستنظر العقد
التي تتدلى

607
00:25:34,370 --> 00:25:36,920
الجزء السفلي من بعض الوالدين
العنصر أن يكون الأطفال.

608
00:25:36,920 --> 00:25:40,510
وحتى الأطفال سوف
تكون مجموعة من 27، واحد 27

609
00:25:40,510 --> 00:25:41,680
لمجرد كونها الفاصلة العليا.

610
00:25:41,680 --> 00:25:43,390
ونحن في طريقنا لفرز
حالة خاصة من ذلك.

611
00:25:43,390 --> 00:25:45,400
لذلك يمكن أن يكون على يقين
أسماء مع الفواصل العليا.

612
00:25:45,400 --> 00:25:47,399
ربما ينبغي حتى اصلة
الذهاب إلى هناك، ولكن عليك

613
00:25:47,399 --> 00:25:50,330
نرى في ص 5 نحن مجموعة الرعاية فقط
حول الرسائل والفواصل العليا.

614
00:25:50,330 --> 00:25:52,990
>> ثم كيف يمكن تمثيل
هيكل البيانات نفسها؟

615
00:25:52,990 --> 00:25:56,454
كيف تمثل الجذر
هذا TRIE، إذا جاز التعبير؟

616
00:25:56,454 --> 00:25:59,620
حسنا، تماما مثل مع قائمة مرتبطة، كنت
تحتاج مؤشر إلى العنصر الأول.

617
00:25:59,620 --> 00:26:04,270
مع TRIE تحتاج فقط واحد
مؤشر إلى جذر هذه TRIE.

618
00:26:04,270 --> 00:26:07,290
ومن هناك يمكنك تجزئة
طريقك إلى أسفل أعمق وأعمق

619
00:26:07,290 --> 00:26:10,460
على كل عقدة أخرى في الهيكل.

620
00:26:10,460 --> 00:26:13,440
هكذا ببساطة مع هذا يمكن
نمثلها أن البنية.

621
00:26:13,440 --> 00:26:15,877
>> الآن Meanwhile-- أوه، سؤال.

622
00:26:15,877 --> 00:26:17,220
>> الجمهور: ما هي كلمة منطقي؟

623
00:26:17,220 --> 00:26:20,490
>> DAVID مالان: كلمة منطقي ل
فقط هذا التجسد C

624
00:26:20,490 --> 00:26:22,920
ما وصفتها
في هذا المربع هنا، عندما

625
00:26:22,920 --> 00:26:26,000
بدأت تقسيم كل من
عناصر المصفوفة إلى قطعتين.

626
00:26:26,000 --> 00:26:27,600
واحد هو مؤشر إلى عقدة القادمة.

627
00:26:27,600 --> 00:26:30,280
الآخر يجب أن يكون
شيء مربع الاختيار مثل

628
00:26:30,280 --> 00:26:33,770
لنقول نعم، هناك
كلمة Daven أن ينتهي هنا،

629
00:26:33,770 --> 00:26:35,610
لأننا لا نريد،
في هذه اللحظة، ديف.

630
00:26:35,610 --> 00:26:39,320
>> على الرغم من ديف وستكون
كلمة المشروعة، وانه ليس في TRIE

631
00:26:39,320 --> 00:26:39,830
حتى الان.

632
00:26:39,830 --> 00:26:40,950
D وليس كلمة واحدة.

633
00:26:40,950 --> 00:26:42,770
وD-A ليست كلمة أو اسما.

634
00:26:42,770 --> 00:26:45,020
حتى علامة الاختيار
يشير فقط مرة واحدة لك

635
00:26:45,020 --> 00:26:48,190
ضرب هذه العقدة هي
مسار السابق من الحروف

636
00:26:48,190 --> 00:26:50,700
في الواقع سلسلة التي قمت بإدراجه.

637
00:26:50,700 --> 00:26:53,660
ذلك أن جميع منطقي
هناك يفعل بالنسبة لنا.

638
00:26:53,660 --> 00:26:55,500
>> أي أسئلة أخرى عن محاولات؟

639
00:26:55,500 --> 00:26:56,215
نعم.

640
00:26:56,215 --> 00:26:58,035
>> الجمهور: ما هو التداخل؟

641
00:26:58,035 --> 00:26:59,945
ماذا لو كان لديك ديف وDaven؟

642
00:26:59,945 --> 00:27:00,820
DAVID مالان: الكمال.

643
00:27:00,820 --> 00:27:02,580
ماذا لو كان لديك ديف وDaven؟

644
00:27:02,580 --> 00:27:06,240
لذلك إذا أردنا إدراج، ويقول كنية،
لDavid-- Dave-- D-A-V-E؟

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
هذا هو في الواقع بسيط السوبر.

647
00:27:08,700 --> 00:27:10,325
لذلك نحن ذاهبون فقط لاتخاذ أربع خطوات.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. وماذا لدي ل
به مرة واحدة أنا ضربت تلك العقدة الرابعة؟

650
00:27:15,847 --> 00:27:16,680
مجرد الذهاب للتحقق.

651
00:27:16,680 --> 00:27:18,000
نحن بالفعل على ما يرام.

652
00:27:18,000 --> 00:27:18,840
القيام به.

653
00:27:18,840 --> 00:27:19,750
أربع خطوات.

654
00:27:19,750 --> 00:27:21,590
وقت ثابت مقارب.

655
00:27:21,590 --> 00:27:26,300
ونحن الآن قد أشارت إلى أن كلا من ديف
وDaven والسلاسل في الهيكل.

656
00:27:26,300 --> 00:27:27,710
حتى لا مشكلة.

657
00:27:27,710 --> 00:27:30,200
ولاحظ كيف وجود
من Daven لم يجعل

658
00:27:30,200 --> 00:27:34,750
اتخاذ أي المزيد من الوقت أو أقل
الوقت لديف والعكس بالعكس.

659
00:27:34,750 --> 00:27:36,000
>> لذلك ماذا يمكننا أن نفعل الآن؟

660
00:27:36,000 --> 00:27:40,680
لقد استخدمت هذا التشبيه قبل
من الأدراج تمثل شيئا.

661
00:27:40,680 --> 00:27:43,380
ولكن تبين أن
كومة من الأدراج هو في الواقع

662
00:27:43,380 --> 00:27:47,187
بيانية لبيانات مجردة آخر
type-- هيكل البيانات على مستوى أعلى

663
00:27:47,187 --> 00:27:49,770
أنه في نهاية اليوم هو فقط
مثل صفيف أو قائمة مرتبطة

664
00:27:49,770 --> 00:27:50,970
أو شيء أكثر دنيوية.

665
00:27:50,970 --> 00:27:53,270
بل انها أكثر إثارة للاهتمام
المفهوم النظري.

666
00:27:53,270 --> 00:27:56,440
وهناك كومة، مثل هذه
الصواني هنا في ماذر،

667
00:27:56,440 --> 00:27:58,750
ويطلق عموما
that-- مجرد كومة.

668
00:27:58,750 --> 00:28:02,540
>> وهذا النوع من هياكل البيانات
لديك اثنين من operations--

669
00:28:02,540 --> 00:28:05,880
لديك واحد يسمى دفعة ل
إضافة شيء إلى المكدس،

670
00:28:05,880 --> 00:28:08,320
مثل وضع علبة أخرى
العودة إلى أعلى المكدس.

671
00:28:08,320 --> 00:28:11,350
ثم البوب، مما يعني أنك
اتخاذ العلوي صينية قبالة.

672
00:28:11,350 --> 00:28:16,210
ولكن ما هو المفتاح نحو كومة هو أن
انها حصلت على هذه الخاصية غريبة.

673
00:28:16,210 --> 00:28:19,560
كما الموظفين قاعة الطعام ل
إعادة ترتيب الصواني لالوجبة التالية،

674
00:28:19,560 --> 00:28:21,380
ما سيكون
صحيح حول كيفية طلاب

675
00:28:21,380 --> 00:28:22,856
التفاعل مع هذا الهيكل البيانات؟

676
00:28:22,856 --> 00:28:24,480
الجمهور: انهم ذاهبون لموسيقى البوب ​​مرة واحدة.

677
00:28:24,480 --> 00:28:26,550
DAVID مالان: انهم ذاهبون ل
البوب ​​مرة واحدة، ونأمل أعلى.

678
00:28:26,550 --> 00:28:28,910
وإلا فإنه مجرد نوع من الغباء
ليذهب كل في طريقه إلى أسفل.

679
00:28:28,910 --> 00:28:29,070
أليس كذلك؟

680
00:28:29,070 --> 00:28:31,620
لا بنية البيانات لا تسمح حقا
لك للاستيلاء على أسفل الدرج على الأقل

681
00:28:31,620 --> 00:28:32,520
بسهولة.

682
00:28:32,520 --> 00:28:35,040
ولذلك لا يوجد هذا الغريب
الملكية إلى كومة

683
00:28:35,040 --> 00:28:39,730
إن العنصر الأخير في ل
ستكون أول من أصل واحد.

684
00:28:39,730 --> 00:28:43,400
ويطلق علماء الكمبيوتر
هذا LIFO-- تستمر في، لأول مرة.

685
00:28:43,400 --> 00:28:45,540
والواقع أنه لا توجد لديها
تطبيقات مثيرة للاهتمام.

686
00:28:45,540 --> 00:28:50,090
انها ليست بالضرورة واضحة مثل بعض
الآخرين، ولكن يمكن، في الواقع، أن تكون مفيدة،

687
00:28:50,090 --> 00:28:54,040
ويمكن، في الواقع، أن تنفذ
في عدة طرق مختلفة.

688
00:28:54,040 --> 00:28:58,550
>> حتى واحد، وفعلا، والسماح
مني عدم الغوص في ذلك.

689
00:28:58,550 --> 00:28:59,860
دعونا نفعل هذا بدلا من ذلك.

690
00:28:59,860 --> 00:29:03,700
دعونا ننظر في واحد وهذا تقريبا
نفس الفكرة، ولكن هذا قليلا أكثر عدلا.

691
00:29:03,700 --> 00:29:04,200
أليس كذلك؟

692
00:29:04,200 --> 00:29:07,560
إذا كنت واحدا من هؤلاء الأولاد أو مروحة
الفتاة التي يحب حقا منتجات أبل

693
00:29:07,560 --> 00:29:10,130
وكنت استيقظ الساعة 3:00 صباحا
ليصطف في بعض متجر

694
00:29:10,130 --> 00:29:14,150
للحصول على أحدث فون جدا، كنت
قد اصطفوا من هذا القبيل.

695
00:29:14,150 --> 00:29:15,800
>> الآن يدعى طابور عمدا جدا.

696
00:29:15,800 --> 00:29:18,190
انها خط لأن هناك
بعض الإنصاف لها.

697
00:29:18,190 --> 00:29:18,690
أليس كذلك؟

698
00:29:18,690 --> 00:29:21,690
انه نوع من السقوط إذا كنت قد
حصلت هناك أولا في متجر أبل

699
00:29:21,690 --> 00:29:25,700
ولكن كنت بشكل فعال bottommost
علبة لأن موظفي أبل ثم

700
00:29:25,700 --> 00:29:28,189
البوب ​​آخر شخص
حصلت فعلا في الخط.

701
00:29:28,189 --> 00:29:31,230
حتى مداخن وقوائم الانتظار، على الرغم من
ظيفيا انهم نوع من same--

702
00:29:31,230 --> 00:29:33,105
انها مجرد هذه المجموعة
موارد هذا

703
00:29:33,105 --> 00:29:36,210
سوف تنمو وshrink-- هناك
هذا الجانب الإنصاف إليه،

704
00:29:36,210 --> 00:29:39,634
على الأقل في العالم الحقيقي،
حيث يمكنك ممارسة عمليات

705
00:29:39,634 --> 00:29:40,800
تختلف جذريا.

706
00:29:40,800 --> 00:29:43,360
وstack-- طابور
rather-- يقال لها

707
00:29:43,360 --> 00:29:45,320
عمليتين: ن الانتظار والانتظار د.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
أو يمكنك الاتصال بهم
أي عدد من الاشياء.

710
00:29:48,090 --> 00:29:50,770
ولكن كنت ترغب فقط في التقاط
فكرة أن واحد يضيف

711
00:29:50,770 --> 00:29:53,230
واحد هو طرح في نهاية المطاف.

712
00:29:53,230 --> 00:29:58,840
>> الآن تحت غطاء محرك السيارة، كل من كومة
ويمكن تنفيذ طابور كيف؟

713
00:29:58,840 --> 00:30:01,390
نحن لن نذهب إلى رمز لل
ذلك لأن مستوى أعلى

714
00:30:01,390 --> 00:30:03,387
الفكرة هي نوع من أكثر وضوحا.

715
00:30:03,387 --> 00:30:04,470
أعني، ماذا يفعل البشر؟

716
00:30:04,470 --> 00:30:07,030
إذا أنا أول شخص في أبل
تخزين وهذا هو الباب الأمامي،

717
00:30:07,030 --> 00:30:08,130
كما تعلمون، انا ذاهب الى الوقوف هنا.

718
00:30:08,130 --> 00:30:09,750
والشخص المقبل
الذهاب لنقف هنا.

719
00:30:09,750 --> 00:30:11,500
والشخص المقبل
الذهاب لنقف هنا.

720
00:30:11,500 --> 00:30:13,792
فما بنية البيانات
يفسح المجال لطابور؟

721
00:30:13,792 --> 00:30:14,542
>> الجمهور: طابور.

722
00:30:14,542 --> 00:30:15,667
DAVID مالان: حسنا، طابور.

723
00:30:15,667 --> 00:30:16,390
بالتأكيد.

724
00:30:16,390 --> 00:30:16,920
ماذا بعد؟

725
00:30:16,920 --> 00:30:17,600
>> الجمهور: قائمة مرتبطة.

726
00:30:17,600 --> 00:30:18,990
>> DAVID مالان: مرتبط
قائمة هل يمكن تنفيذها.

727
00:30:18,990 --> 00:30:22,500
وقائمة مرتبطة هو لطيف لأن ثم
أنها يمكن أن تنمو بشكل تعسفي طالما عارضت

728
00:30:22,500 --> 00:30:24,880
إلى وجود بعض عدد ثابت
الناس في المخزن.

729
00:30:24,880 --> 00:30:27,030
ولكن ربما عدد ثابت
من الأماكن غير مشروعة.

730
00:30:27,030 --> 00:30:30,350
لأنه إذا كان لديهم فقط مثل 20
فون في اليوم الأول، ربما

731
00:30:30,350 --> 00:30:33,930
أنهم بحاجة إلى مجموعة من حجم فقط
20 لتمثيل أن قائمة الانتظار، والتي

732
00:30:33,930 --> 00:30:37,070
هو فقط أن أقول الآن مرة واحدة نبدأ الحديث
حول هذه المشاكل مستوى أعلى،

733
00:30:37,070 --> 00:30:38,890
يمكنك تنفيذ ذلك
في أي عدد من الطرق.

734
00:30:38,890 --> 00:30:42,030
وهناك على الارجح مجرد الذهاب ل
تكون المفاضلة في المكان والزمان

735
00:30:42,030 --> 00:30:43,950
أو فقط في تعقيد كود خاص بك.

736
00:30:43,950 --> 00:30:45,380
>> ماذا عن كومة؟

737
00:30:45,380 --> 00:30:48,190
حسنا، كومة، شهدنا أيضا
يمكن أن يكون مجرد هذه الصواني.

738
00:30:48,190 --> 00:30:50,007
ويمكن تطبيق هذا صفيف.

739
00:30:50,007 --> 00:30:53,090
ولكن في مرحلة ما إذا كنت تستخدم صفيف،
ما الذي سيحدث لالصواني

740
00:30:53,090 --> 00:30:54,173
كنت في محاولة لاخماد؟

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
حسنا.

743
00:30:55,670 --> 00:30:57,490
وأنت تسير فقط ل
يكون قادرا على الذهاب عالية جدا.

744
00:30:57,490 --> 00:31:00,156
واعتقد انهم في ماثر
توقفت فعليا في هذا الافتتاح.

745
00:31:00,156 --> 00:31:01,950
حتى في الواقع، انها تقريبا
مثل ماثر هو استخدام

746
00:31:01,950 --> 00:31:03,783
مجموعة من حجم ثابت،
لأنك تستطيع فقط

747
00:31:03,783 --> 00:31:08,302
تناسب الكثير من الصواني في هذا الافتتاح في
الجدار نزولا تحت الركبتين الناس.

748
00:31:08,302 --> 00:31:10,010
وهكذا يمكن أن يكون
وقال لتكون صفيف،

749
00:31:10,010 --> 00:31:14,300
ولكننا بالتأكيد يمكن تنفيذ ذلك
بشكل عام مع قائمة مرتبطة.

750
00:31:14,300 --> 00:31:16,390
>> حسنا، ماذا عن هيكل بيانات آخر؟

751
00:31:16,390 --> 00:31:18,760
اسمحوا لي أن تشمر الآخر المرئي هنا.

752
00:31:18,760 --> 00:31:24,710
شيء من هذا القبيل وكيف حول هذا واحد هنا؟

753
00:31:24,710 --> 00:31:28,920
لماذا قد يكون من المفيد أن يكون لا
شيء كما يتوهم بأنه TRIE، التي

754
00:31:28,920 --> 00:31:32,370
شهد كان لدينا هذه العقد واسعة جدا،
كل منها في مجموعة؟

755
00:31:32,370 --> 00:31:35,740
ولكن ماذا اذا لم نفعل شيئا أكثر
ببساطة، وكأنه شجرة العائلة المدرسة القديمة،

756
00:31:35,740 --> 00:31:38,110
كل الذي عقد هنا
هو فقط تخزين رقم.

757
00:31:38,110 --> 00:31:42,180
بدلا من اسم أو سليل
هو مجرد تخزين عدد من هذا القبيل.

758
00:31:42,180 --> 00:31:45,250
>> كذلك، فإن المصطلحات التي نستخدمها في
هياكل البيانات هي كل من يحاول

759
00:31:45,250 --> 00:31:49,510
والأشجار، حيث TRIE، مرة أخرى، هو
واحد الذين العقد هي المصفوفات فقط،

760
00:31:49,510 --> 00:31:51,680
لا يزال ما يمكن
استخدام من المدارس الابتدائية

761
00:31:51,680 --> 00:31:53,860
عندما قمت بعمل الأسرة
tree-- الأوراق والجذر

762
00:31:53,860 --> 00:31:57,250
من شجرة وأطفال
الأم والأخوة والأخوات منها.

763
00:31:57,250 --> 00:32:03,670
ونحن قد تنفذ شجرة،
على سبيل المثال، ببساطة لأن هذا.

764
00:32:03,670 --> 00:32:07,420
شجرة، إذا أنها عقدة، واحدة من
هذه الاوساط التي لديها عدد،

765
00:32:07,420 --> 00:32:09,947
انها ليست ستكون لدينا
مؤشر واحد، ولكن اثنين.

766
00:32:09,947 --> 00:32:11,780
وبمجرد إضافة
مؤشر الثاني، ل

767
00:32:11,780 --> 00:32:13,905
يمكن في الواقع جعل الآن نوع
البيانات ثنائية الأبعاد

768
00:32:13,905 --> 00:32:14,780
هياكل في الذاكرة.

769
00:32:14,780 --> 00:32:16,660
مثل الكثير من ثنائي الأبعاد
مجموعة، يمكنك

770
00:32:16,660 --> 00:32:18,904
لديهم نوع من ثنائي الأبعاد
ولكن تلك القوائم المرتبطة

771
00:32:18,904 --> 00:32:20,820
ان اتباع نمط
حيث لا يوجد دورات.

772
00:32:20,820 --> 00:32:24,487
انها حقا شجرة واحدة
طريقة جد هنا وثم

773
00:32:24,487 --> 00:32:27,320
بعض الآباء والأمهات والأطفال و
الأحفاد وأبناء الأحفاد.

774
00:32:27,320 --> 00:32:28,370
وهكذا دواليك.

775
00:32:28,370 --> 00:32:32,390
>> ولكن ما هو أنيق حقا عن هذا أيضا، و
فقط لندف لكم مع قليل من التعليمات البرمجية،

776
00:32:32,390 --> 00:32:35,370
استدعاء عودية من
لحظة العودة، حيث

777
00:32:35,370 --> 00:32:38,220
أن تكتب وظيفة تطلق على نفسها.

778
00:32:38,220 --> 00:32:41,140
هذا هو فرصة جميلة
لتنفيذ شيء

779
00:32:41,140 --> 00:32:42,920
مثل العودية، لأن النظر في هذا.

780
00:32:42,920 --> 00:32:43,860
>> هذه هي شجرة.

781
00:32:43,860 --> 00:32:48,040
ولقد كنت الشرج قليلا مع كيف
أضع الأعداد الصحيحة إلى الشارع.

782
00:32:48,040 --> 00:32:51,020
لدرجة أن لديها خاصة
name-- شجرة البحث الثنائية.

783
00:32:51,020 --> 00:32:53,460
نحن الآن قد سمعت من ثنائي
البحث، ولكن يمكنك

784
00:32:53,460 --> 00:32:55,180
العمل الوراء من اسم هذا الشيء في؟

785
00:32:55,180 --> 00:32:59,280
ما هو نمط كيف
إدراج الأعداد الصحيحة في هذه الشجرة؟

786
00:32:59,280 --> 00:33:00,696
انها ليست التعسفي.

787
00:33:00,696 --> 00:33:01,570
هناك بعض النمط.

788
00:33:01,570 --> 00:33:02,090
نعم.

789
00:33:02,090 --> 00:33:03,370
>> الجمهور: أصغر على اليسار.

790
00:33:03,370 --> 00:33:03,690
>> DAVID مالان: نعم.

791
00:33:03,690 --> 00:33:05,062
أصغر هي على اليسار.

792
00:33:05,062 --> 00:33:06,270
الاكبر هي على حق.

793
00:33:06,270 --> 00:33:12,940
مثل أن يكون البيان صحيحا هو
الأم أكبر من الطفل الأيسر،

794
00:33:12,940 --> 00:33:14,850
ولكن أقل من الطفل الأيمن.

795
00:33:14,850 --> 00:33:17,750
وهذا وحده هو حتى
تعريف اللفظي عودي

796
00:33:17,750 --> 00:33:20,500
لأنك يمكن أن تنطبق
المنطق نفسه على كل عقدة

797
00:33:20,500 --> 00:33:23,080
والقيعان فقط
خارج، وهي قضية قاعدة إذا كنت

798
00:33:23,080 --> 00:33:25,740
سوف، عندما ضرب أحد
الأوراق، إذا جاز التعبير،

799
00:33:25,740 --> 00:33:28,580
حيث إجازة لا يوجد لديه أطفال أكثر.

800
00:33:28,580 --> 00:33:30,614
>> الآن كيف يمكن أن تجد عدد 44؟

801
00:33:30,614 --> 00:33:32,280
سوف تبدأ في جذور ويقول صاحب الجلالة.

802
00:33:32,280 --> 00:33:35,690
55 ليس 44 لذا لا أريد أن أذهب
احقاق الحق أو أريد أن أذهب اليسار؟

803
00:33:35,690 --> 00:33:37,190
حسنا، من الواضح تريد أن تذهب اليسار.

804
00:33:37,190 --> 00:33:40,060
وحتى انها تماما مثل الهاتف
كتاب المثال في البحث ثنائي

805
00:33:40,060 --> 00:33:41,099
أكثر عموما.

806
00:33:41,099 --> 00:33:43,390
لكننا تنفيذها
الآن أكثر من ذلك بقليل حيوي

807
00:33:43,390 --> 00:33:45,339
من صفيف قد تسمح.

808
00:33:45,339 --> 00:33:48,130
وفي الواقع، إذا كنت تريد أن تبدو
في رمز، للوهلة الأولى بالتأكيد.

809
00:33:48,130 --> 00:33:49,671
يبدو في مجمله مجموعة من الخطوط.

810
00:33:49,671 --> 00:33:51,220
ولكن الامر بسيط جميل.

811
00:33:51,220 --> 00:33:54,490
إذا كنت ترغب في تنفيذ وظيفة
ودعا البحث هدفها في الحياة

812
00:33:54,490 --> 00:33:57,290
هو البحث عن قيمة
مثل ن، وهو صحيح،

813
00:33:57,290 --> 00:34:01,756
وكنت أصدر في pointer-- واحد
مؤشر إلى العقدة من جذورها،

814
00:34:01,756 --> 00:34:04,380
بدلا من تلك الشجرة التي
يمكنك الوصول إلى كل شيء آخر،

815
00:34:04,380 --> 00:34:08,850
لاحظ كيف مباشر
يمكنك تطبيق المنطق.

816
00:34:08,850 --> 00:34:10,880
إذا شجرة فارغة،
من الواضح أنه ليس هناك.

817
00:34:10,880 --> 00:34:11,880
دعونا فقط العودة كاذبة.

818
00:34:11,880 --> 00:34:12,000
أليس كذلك؟

819
00:34:12,000 --> 00:34:14,040
إذا كنت تسليمه شيئا،
لا يوجد شيء هناك.

820
00:34:14,040 --> 00:34:17,900
>> آخر، إذا كان n أقل من
شجرة n-- السهم السهم الآن ن،

821
00:34:17,900 --> 00:34:20,670
أذكر قدمنا ​​السوبر
لفترة وجيزة في اليوم الآخر،

822
00:34:20,670 --> 00:34:25,100
وهذا يعني فقط دي الإسناد و
مؤشر وإلقاء نظرة على حقل يسمى ن.

823
00:34:25,100 --> 00:34:27,690
ذلك يعني الذهاب الى هناك و
ننظر في حقل يسمى ن.

824
00:34:27,690 --> 00:34:33,810
حتى إذا ن، وقيمة كنت أعطيت، هو أقل
من القيمة في صحيح الأشجار،

825
00:34:33,810 --> 00:34:35,449
أين تريد أن تذهب؟

826
00:34:35,449 --> 00:34:36,389
إلى اليسار.

827
00:34:36,389 --> 00:34:37,780
>> لذلك تلاحظ العودية.

828
00:34:37,780 --> 00:34:39,860
أنا returning-- ليس صحيحا.

829
00:34:39,860 --> 00:34:40,989
لا كاذبة.

830
00:34:40,989 --> 00:34:45,670
أعود مهما كانت الإجابة
هو من استدعاء نفسي، ويمر

831
00:34:45,670 --> 00:34:50,100
ون مرة أخرى، والتي هي زائدة عن الحاجة،
ولكن ما هو مختلف قليلا الآن؟

832
00:34:50,100 --> 00:34:51,989
كيف أنا جعل المشكلة أصغر؟

833
00:34:51,989 --> 00:34:54,920
أنا مارة في كثاني
حجة، وليس جذر الشجرة،

834
00:34:54,920 --> 00:34:59,616
ولكن الطفل الأيسر في هذه الحالة.

835
00:34:59,616 --> 00:35:00,990
لذلك أنا مارة في الطفل الأيسر.

836
00:35:00,990 --> 00:35:04,720
>> وفي الوقت نفسه، إذا كان n هو أكبر من
عقدة أنا أبحث حاليا في،

837
00:35:04,720 --> 00:35:06,690
أنا ابحث الجهة اليمنى.

838
00:35:06,690 --> 00:35:10,880
آخر، إذا كانت الشجرة ليست فارغة، و
إذا كان العنصر ليس إلى اليسار

839
00:35:10,880 --> 00:35:13,240
وانها ليست على حق،
ما هي حالة رائعة؟

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
وجدنا فعلا عقدة في
السؤال، ولذا فإننا العودة الحقيقية.

842
00:35:18,440 --> 00:35:21,490
>> لذلك قمنا مجرد خدش السطح
الآن بعض من هذه الهياكل البيانات.

843
00:35:21,490 --> 00:35:24,370
مشكلة في تعيين خمسة عليك
استكشاف هذه بعد أخرى،

844
00:35:24,370 --> 00:35:27,250
وعليك أن تعطى التصميم الخاص بك
اختيار كيفية التوجه نحو ذلك.

845
00:35:27,250 --> 00:35:30,250
ما أود ان تختتم يوم
هو مجرد دعابة 30 ثانية

846
00:35:30,250 --> 00:35:32,080
ما ينتظر الأسبوع المقبل وما بعده.

847
00:35:32,080 --> 00:35:35,390
>> ونحن والحمد لله كنت قد begin--
think-- انتقالنا ببطء

848
00:35:35,390 --> 00:35:38,680
من عالم C والدنيا
تفاصيل التنفيذ مستوى،

849
00:35:38,680 --> 00:35:42,090
إلى العالم الذي يمكن أن نتخذها ل
المسلم به أن شخص آخر لديه أخيرا

850
00:35:42,090 --> 00:35:44,010
نفذت هذه البيانات
الهياكل بالنسبة لنا،

851
00:35:44,010 --> 00:35:47,570
وسنبدأ في فهم
العالم الحقيقي يعني تنفيذ

852
00:35:47,570 --> 00:35:50,560
البرامج القائمة على الويب و
المواقع بشكل عام

853
00:35:50,560 --> 00:35:52,910
وأيضا أمن جدا
الآثار التي كانت لدينا فقط

854
00:35:52,910 --> 00:35:54,850
بدأت تخدش سطح.

855
00:35:54,850 --> 00:35:57,320
هنا هو ما ينتظرنا
في الأيام القادمة.

856
00:35:57,320 --> 00:36:00,480
>> [تشغيل الفيديو]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -He جاء مع الرسالة،
مع كل بروتوكول بلده.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
وقال انه جاء الى عالم من ضروب
الجدران النارية، والموجهات غير مكترثة،

861
00:36:30,894 --> 00:36:33,368
ومخاطر أسوأ بكثير من الموت.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
انه سريع.

864
00:36:36,236 --> 00:36:37,980
انه قوي.

865
00:36:37,980 --> 00:36:42,830
انه TCP / IP، وانه حصل على عنوانك.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"ووريورز للنت".

868
00:36:48,074 --> 00:36:49,660
[END تشغيل الفيديو]

869
00:36:49,660 --> 00:36:50,910
DAVID مالان: قادمة الأسبوع المقبل.

870
00:36:50,910 --> 00:36:51,880
سوف نرى لك ذلك الحين.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[تشغيل الفيديو]

873
00:36:56,060 --> 00:36:59,240
-وعلى الآن "، والأفكار العميقة"
بواسطة Daven فارنهام.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
يبدأ -David دائما
محاضرات مع "كل الحق".

876
00:37:05,820 --> 00:37:08,750
لماذا لا "، وإليك الحل
لمجموعة مشكلة هذا الأسبوع "

877
00:37:08,750 --> 00:37:12,180
أو "نحن منحنا كل واحد منكم على ألف؟"

878
00:37:12,180 --> 00:37:13,380
[يضحك]

879
00:37:13,380 --> 00:37:15,530
[END تشغيل الفيديو]