1
00:00:00,000 --> 00:00:12,350
>> [عزف الموسيقى]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: مرحبا.

3
00:00:13,050 --> 00:00:13,640
أنا روب.

4
00:00:13,640 --> 00:00:16,210
ودعونا من هذا الحل.

5
00:00:16,210 --> 00:00:20,070
حتى هنا ونحن في طريقنا لتنفيذ
جدول عام.

6
00:00:20,070 --> 00:00:24,090
ونحن نرى أن العقدة البنية لدينا
الجدول سوف تبدو هذه.

7
00:00:24,090 --> 00:00:28,710
لذلك ستكون لدينا كلمة شار
مجموعة من حجم الطول + 1.

8
00:00:28,710 --> 00:00:32,259
لا ننسى + 1، حيث الحد الأقصى
كلمة في القاموس هو 45

9
00:00:32,259 --> 00:00:33,130
حرفا.

10
00:00:33,130 --> 00:00:37,070
ثم نحن في طريقنا للحاجة واحدة اضافية
حرف مائل للصفر.

11
00:00:37,070 --> 00:00:40,870
>> ثم hashtable لدينا في كل
دلو يجري لتخزين

12
00:00:40,870 --> 00:00:42,320
قائمة مرتبطة العقد.

13
00:00:42,320 --> 00:00:44,420
ونحن لا نفعل الخطية التحقيق هنا.

14
00:00:44,420 --> 00:00:48,430
وذلك من أجل ربط المقبل
عنصر في دلو، ونحن بحاجة إلى

15
00:00:48,430 --> 00:00:50,390
عقدة البنية * المقبل.

16
00:00:50,390 --> 00:00:51,110
موافق.

17
00:00:51,110 --> 00:00:53,090
وهذا ما يبدو عقدة مثل.

18
00:00:53,090 --> 00:00:56,180
>> الآن هنا هو إعلان
من hashtable لدينا.

19
00:00:56,180 --> 00:00:59,640
انها ستكون لدينا 16834 الدلاء.

20
00:00:59,640 --> 00:01:01,910
ولكن هذا العدد لا يهم حقا.

21
00:01:01,910 --> 00:01:05,450
وأخيرا، ونحن في طريقنا لديها
العالمية hashtable حجم المتغير الذي

22
00:01:05,450 --> 00:01:07,000
سوف تبدأ صفر.

23
00:01:07,000 --> 00:01:10,760
وانه سيكون لتتبع كيف
العديد من الكلمات في قاموسنا.

24
00:01:10,760 --> 00:01:13,710
>> لذلك دعونا نلقي نظرة على الحمل.

25
00:01:13,710 --> 00:01:16,390
تلاحظ أن الحمل، تقوم بإرجاع منطقي.

26
00:01:16,390 --> 00:01:20,530
لك العودة الحقيقية إذا كان بنجاح
تحميل، وكاذبة خلاف ذلك.

27
00:01:20,530 --> 00:01:23,990
ويستغرق شار كانت const * القاموس،
وهو القاموس

28
00:01:23,990 --> 00:01:25,280
أننا نريد لفتح.

29
00:01:25,280 --> 00:01:27,170
ولهذا فإن أول شيء
ونحن في طريقنا للقيام به.

30
00:01:27,170 --> 00:01:29,500
>> ونحن في طريقنا إلى FOPEN و
القاموس للقراءة.

31
00:01:29,500 --> 00:01:31,680
ونحن في طريقنا لديك لجعل
على يقين من أنه نجح في ذلك.

32
00:01:31,680 --> 00:01:35,920
حتى إذا عادت فارغة، ثم أننا لم
بنجاح فتح القاموس.

33
00:01:35,920 --> 00:01:37,440
ونحن بحاجة إلى عودة كاذبة.

34
00:01:37,440 --> 00:01:41,580
ولكن على افتراض أن فعلت بنجاح
مفتوحة، ثم نريد أن قراءة

35
00:01:41,580 --> 00:01:42,400
القاموس.

36
00:01:42,400 --> 00:01:46,450
حتى تبقى حلقات حتى نجد بعض
السبب للخروج من هذه الحلقة،

37
00:01:46,450 --> 00:01:47,570
الذي سنرى.

38
00:01:47,570 --> 00:01:48,920
حتى تبقى حلقات.

39
00:01:48,920 --> 00:01:51,780
>> والآن ونحن في طريقنا ل
malloc عقدة واحدة.

40
00:01:51,780 --> 00:01:54,020
وبطبيعة الحال نحن بحاجة
في الهواء التحقق مرة أخرى.

41
00:01:54,020 --> 00:01:58,680
حتى إذا mallocing لم تنجح، ثم
نحن نريد لتفريغ أي عقدة أننا

42
00:01:58,680 --> 00:02:02,590
حدث لmalloc قبل، إغلاق
القاموس وعودة كاذبة.

43
00:02:02,590 --> 00:02:06,830
ولكن تجاهل ذلك، على افتراض أننا
نجحت، ثم نريد أن استخدام fscanf

44
00:02:06,830 --> 00:02:12,400
لقراءة كلمة واحدة من وجهة نظرنا
القاموس في عقدة لدينا.

45
00:02:12,400 --> 00:02:17,940
حتى أن نتذكر أن دخول> كلمة هو شار
كلمة عازلة من حجم LENGHTH + 1

46
00:02:17,940 --> 00:02:20,300
أننا ذاهبون لتخزين كلمة فيه.

47
00:02:20,300 --> 00:02:25,070
>> حتى fscanf يجري في العودة 1، طالما
كما كان قادرا على بنجاح

48
00:02:25,070 --> 00:02:26,750
قراءة كلمة من الملف.

49
00:02:26,750 --> 00:02:30,460
إذا حدث أي خطأ، أو أننا
تصل إلى نهاية الملف، فإنه

50
00:02:30,460 --> 00:02:31,950
لن تعود 1.

51
00:02:31,950 --> 00:02:35,180
وفي هذه الحالة فإنه لا يرجع 1،
نحن في نهاية المطاف الذهاب الى الخروج من

52
00:02:35,180 --> 00:02:37,280
هذه الحلقة من الوقت.

53
00:02:37,280 --> 00:02:42,770
لذلك نرى أنه بمجرد أن لدينا بنجاح
قراءة في كلمة

54
00:02:42,770 --> 00:02:48,270
دخول> كلمة، ثم ونحن في طريقنا إلى أن
الكلمة باستخدام دالة البعثرة لدينا.

55
00:02:48,270 --> 00:02:49,580
>> دعونا نلقي نظرة على
وظيفة التجزئة.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
لذلك لا تحتاج حقا
لفهم هذا.

58
00:02:55,610 --> 00:02:59,460
وفعلا نجحنا فقط هذا التجزئة
تعمل من الإنترنت.

59
00:02:59,460 --> 00:03:04,010
الشيء الوحيد الذي تحتاجه هو الاعتراف
أن هذا يأخذ شار كانت const * كلمة.

60
00:03:04,010 --> 00:03:08,960
حتى انها لاتخاذ سلسلة كمدخل، و
إرجاع صحيح غير الموقعة كإخراج.

61
00:03:08,960 --> 00:03:12,360
بحيث كل وظيفة تجزئة هو، هو
يأخذ في مداخل ويعطيك

62
00:03:12,360 --> 00:03:14,490
الفهرس في hashtable.

63
00:03:14,490 --> 00:03:18,530
>> لاحظ أننا moding بواسطة NUM_BUCKETS،
لذلك عاد تلك القيمة

64
00:03:18,530 --> 00:03:21,730
هو في الواقع فهرس في hashtable
ومؤشر لا تتجاوز

65
00:03:21,730 --> 00:03:24,320
حدود الصفيف.

66
00:03:24,320 --> 00:03:28,060
ذلك بالنظر إلى أن وظيفة، ونحن في طريقنا
إلى تجزئة الكلمة التي قرأنا

67
00:03:28,060 --> 00:03:29,390
القاموس.

68
00:03:29,390 --> 00:03:31,700
ثم نحن في طريقنا للاستخدام
أن تجزئة لإدراج

69
00:03:31,700 --> 00:03:33,750
دخول hashtable.

70
00:03:33,750 --> 00:03:38,520
>> تجزئة الآن hashtable هو الحالي
قائمة مرتبطة في الجدول.

71
00:03:38,520 --> 00:03:41,410
وانه من الممكن جدا
انها مجرد NULL.

72
00:03:41,410 --> 00:03:44,960
نحن نريد لإدراج دخولنا في
ابتداء من هذه القائمة المرتبطة.

73
00:03:44,960 --> 00:03:48,600
وحتى ونحن في طريقنا لدينا الحالي
نقطة الدخول إلى ما hashtable

74
00:03:48,600 --> 00:03:50,380
وتشير حاليا.

75
00:03:50,380 --> 00:03:53,310
ثم ونحن في طريقنا لتخزين و
في hashtable في

76
00:03:53,310 --> 00:03:55,350
التجزئة، الإدخال الحالي.

77
00:03:55,350 --> 00:03:59,320
حتى هذين الخطين إدراج بنجاح
دخول في بداية

78
00:03:59,320 --> 00:04:02,260
قائمة مرتبطة في ذلك مؤشر
في hashtable.

79
00:04:02,260 --> 00:04:04,900
>> مرة واحدة ننتهي مع هذا، ونحن نعلم
أننا وجدنا كلمة أخرى في

80
00:04:04,900 --> 00:04:07,790
القاموس، ونحن زيادة مرة أخرى.

81
00:04:07,790 --> 00:04:13,960
لذلك علينا أن نحافظ يفعل ذلك حتى fscanf
عاد أخيرا شيئا غير 1 في

82
00:04:13,960 --> 00:04:16,950
هذه النقطة أن نتذكر أن
نحن بحاجة إلى تحرير دخول.

83
00:04:16,950 --> 00:04:19,459
لذلك نحن هنا malloced إدخال.

84
00:04:19,459 --> 00:04:21,329
وحاولنا أن نقرأ شيئا
من القاموس.

85
00:04:21,329 --> 00:04:23,910
ونحن لم يقرأ بنجاح
شيء من القاموس، في

86
00:04:23,910 --> 00:04:26,650
هذه الحالة نحتاج لتحرير دخول
أننا في الواقع لم يضع في

87
00:04:26,650 --> 00:04:29,140
hashtable، وكسر في نهاية المطاف.

88
00:04:29,140 --> 00:04:32,750
>> بمجرد ان تندلع نحن بحاجة الى ان نرى، أيضا،
نحن لم تندلع بسبب وجود

89
00:04:32,750 --> 00:04:34,360
كان يقرأ خطأ من الملف؟

90
00:04:34,360 --> 00:04:37,120
أو أننا لم تندلع لأننا
وصلت إلى نهاية الملف؟

91
00:04:37,120 --> 00:04:39,480
إذا كان هناك خطأ، ثم
نحن نريد أن عودة كاذبة.

92
00:04:39,480 --> 00:04:40,930
لأن الحمل لم تنجح.

93
00:04:40,930 --> 00:04:43,890
وفي عملية نريد أن يفرغ
كل الكلمات التي نقرأ في و

94
00:04:43,890 --> 00:04:45,670
إغلاق ملف القاموس.

95
00:04:45,670 --> 00:04:48,740
>> على افتراض أننا لم ننجح، فإننا فقط
لا تزال بحاجة لإغلاق القاموس

96
00:04:48,740 --> 00:04:53,040
ملف، وأخيرا العودة الحقيقية لأننا
بنجاح تحميل القاموس.

97
00:04:53,040 --> 00:04:54,420
وهذا كل شيء عن الحمل.

98
00:04:54,420 --> 00:04:59,020
حتى تحقق الآن، ونظرا لhashtable تحميل،
سوف تبدو هذه.

99
00:04:59,020 --> 00:05:03,140
حتى تحقق، تقوم بإرجاع منطقي، وهو
الذهاب إلى بيان ما إذا كانت مرت

100
00:05:03,140 --> 00:05:07,530
في شار * كلمة سواء التي تم تمريرها
في السلسلة في قاموسنا.

101
00:05:07,530 --> 00:05:09,890
حتى إذا كان في القاموس،
إذا كان في hashtable لدينا،

102
00:05:09,890 --> 00:05:11,170
وسوف نعود صحيح.

103
00:05:11,170 --> 00:05:13,380
وإذا لم يكن، وسوف نعود كاذبة.

104
00:05:13,380 --> 00:05:17,740
>> ونظرا لهذا مرت في كلمة واحدة، نحن
الذهاب إلى تجزئة الكلمة.

105
00:05:17,740 --> 00:05:22,110
الآن الشيء المهم هو الاعتراف
أنه في الحمل عرفنا أن كل من

106
00:05:22,110 --> 00:05:23,820
الكلمات ونحن في طريقنا إلى أن تكون أقل حدة.

107
00:05:23,820 --> 00:05:25,820
ولكن هنا نحن لسنا على يقين من ذلك.

108
00:05:25,820 --> 00:05:29,510
إذا كان لنا أن نلقي نظرة على وظيفة التجزئة لدينا،
دالة البعثرة لدينا في الواقع

109
00:05:29,510 --> 00:05:32,700
أقل غلاف كل حرف
للكلمة.

110
00:05:32,700 --> 00:05:37,940
ذلك بغض النظر عن رسملة
كلمة، وظيفة تجزئة لدينا هو العودة

111
00:05:37,940 --> 00:05:42,270
نفس المؤشر لأيا كان
القيمة، كما كان يمكن أن يكون

112
00:05:42,270 --> 00:05:45,280
عاد لصغيرة تماما
نسخة للكلمة.

113
00:05:45,280 --> 00:05:46,600
ما يرام.

114
00:05:46,600 --> 00:05:49,790
وهذا مؤشر لدينا هو في
hashtable لهذه الكلمة.

115
00:05:49,790 --> 00:05:52,940
>> الآن هذا للحلقة هو الذهاب الى
تكرار عبر القائمة المرتبطة

116
00:05:52,940 --> 00:05:55,000
التي كانت في ذلك مؤشر.

117
00:05:55,000 --> 00:05:59,610
حتى إشعار نحن تهيئة الدخول
للإشارة إلى أن مؤشر.

118
00:05:59,610 --> 00:06:02,750
ونحن في طريقنا لمواصلة
حين دخول! = NULL.

119
00:06:02,750 --> 00:06:07,770
وتذكر أن تحديث المؤشر
لدينا في إدخال قائمة مرتبطة = الإدخال> المقبل.

120
00:06:07,770 --> 00:06:14,400
بحيث يكون لدينا نقطة دخول الحالي ل
العنصر التالي في القائمة المرتبطة.

121
00:06:14,400 --> 00:06:19,250
>> لذلك لكل إدخال في القائمة المرتبطة،
ونحن في طريقنا لاستخدام strcasecmp.

122
00:06:19,250 --> 00:06:20,330
انها ليست strcomp.

123
00:06:20,330 --> 00:06:23,780
لأن مرة أخرى، ونحن نريد ل
تفعل أشياء حالة اكتراث.

124
00:06:23,780 --> 00:06:27,870
لذلك نحن نستخدم strcasecmp مقارنة
الكلمة التي تم تمريرها من خلال هذا

125
00:06:27,870 --> 00:06:31,860
وظيفة ضد الكلمة
وهذا هو في هذا الإدخال.

126
00:06:31,860 --> 00:06:35,570
اذا عاد الصفر، وهذا يعني أن هناك
مباراة، وفي هذه الحالة نريد أن

127
00:06:35,570 --> 00:06:36,630
العودة الحقيقية.

128
00:06:36,630 --> 00:06:39,590
وجدنا بنجاح
كلمة في hashtable لدينا.

129
00:06:39,590 --> 00:06:43,040
>> إذا لم يكن هناك تطابق، ثم نحن
الذهاب الى حلقة مرة أخرى وإلقاء نظرة على

130
00:06:43,040 --> 00:06:43,990
الإدخال التالي.

131
00:06:43,990 --> 00:06:47,640
وسوف نستمر في حين أن هناك حلقات
هي الإدخالات في هذه القائمة المرتبطة.

132
00:06:47,640 --> 00:06:50,160
ماذا يحدث إذا ما تم كسر
للخروج من هذه الحلقة ل؟

133
00:06:50,160 --> 00:06:55,110
وهذا يعني أننا لم نجد أن إدخال
يقابل هذه الكلمة، وفي هذه الحالة

134
00:06:55,110 --> 00:07:00,220
نعود كاذبة تشير إلى أن لدينا
لم hashtable لا يحتوي على هذه الكلمة.

135
00:07:00,220 --> 00:07:02,540
وهذا هو الاختيار.

136
00:07:02,540 --> 00:07:04,790
>> لذلك دعونا نلقي نظرة على الحجم.

137
00:07:04,790 --> 00:07:06,970
الآن حجم ستكون بسيطة جدا.

138
00:07:06,970 --> 00:07:11,080
تذكر منذ ذلك الحين في الحمل، لكل كلمة
وجدنا، ونحن زيادة عالمي

139
00:07:11,080 --> 00:07:12,880
حجم hashtable متغير.

140
00:07:12,880 --> 00:07:16,480
وبالتالي فإن وظيفة حجم هو مجرد الذهاب
للعودة متغير عمومي.

141
00:07:16,480 --> 00:07:18,150
وهذا كل شيء.

142
00:07:18,150 --> 00:07:22,300
>> الآن أخيرا، نحن بحاجة إلى تفريغ
القاموس مرة واحدة انها فعلت كل شيء.

143
00:07:22,300 --> 00:07:25,340
فكيف نحن ذاهبون للقيام بذلك؟

144
00:07:25,340 --> 00:07:30,440
هنا نحن على حلقات
كل دلاء من جدول أعمالنا.

145
00:07:30,440 --> 00:07:33,240
لذلك هناك NUM_BUCKETS الدلاء.

146
00:07:33,240 --> 00:07:37,410
ولكل قائمة مرتبطة في منطقتنا
hashtable، ونحن في طريقنا إلى حلقة أكثر

147
00:07:37,410 --> 00:07:41,070
مجمل القائمة المرتبطة،
تحرير كل عنصر.

148
00:07:41,070 --> 00:07:42,900
>> الآن نحن بحاجة إلى توخي الحذر.

149
00:07:42,900 --> 00:07:47,910
حتى هنا لدينا متغير مؤقت
وهذا ما تخزين المؤشر إلى القادم

150
00:07:47,910 --> 00:07:49,730
عنصر في قائمة مرتبطة.

151
00:07:49,730 --> 00:07:52,140
ثم ونحن في طريقنا إلى الحرة
العنصر الحالي.

152
00:07:52,140 --> 00:07:55,990
نحن بحاجة للتأكد من أننا نفعل ذلك لأننا
لا يمكن فقط تحرير العنصر الحالي

153
00:07:55,990 --> 00:07:59,180
ومن ثم محاولة الوصول إلى مؤشر المقبل،
منذ مرة واحدة لقد تحريرها،

154
00:07:59,180 --> 00:08:00,870
الذاكرة تصبح غير صالحة.

155
00:08:00,870 --> 00:08:04,990
>> لذلك نحن بحاجة للحفاظ على حول المؤشر ل
العنصر التالي، ثم يمكننا أن تحرير

156
00:08:04,990 --> 00:08:08,360
العنصر الحالي، وبعد ذلك يمكننا تحديث
العنصر الحالي لدينا للإشارة إلى

157
00:08:08,360 --> 00:08:09,550
العنصر التالي.

158
00:08:09,550 --> 00:08:12,800
سنقوم حلقة في حين أن هناك عناصر
في هذه القائمة المرتبطة.

159
00:08:12,800 --> 00:08:15,620
ونحن سوف نفعل ذلك وكلها مرتبطة
القوائم في hashtable.

160
00:08:15,620 --> 00:08:19,460
وبمجرد أن انتهيت مع ذلك، لدينا
أفرغت تماما hashtable، و

161
00:08:19,460 --> 00:08:20,190
ننتهي.

162
00:08:20,190 --> 00:08:23,200
لذلك فمن المستحيل لتفريغ
من أي وقت مضى للعودة كاذبة.

163
00:08:23,200 --> 00:08:26,470
وعندما ننتهي، ونحن
مجرد العودة الحقيقية.

164
00:08:26,470 --> 00:08:29,000
>> دعونا نعطي هذا الحل المحاولة.

165
00:08:29,000 --> 00:08:33,070
لذلك دعونا نلقي نظرة على ما لدينا
سوف تبدو وكأنها عقدة البنية.

166
00:08:33,070 --> 00:08:36,220
وهنا نرى ونحن في طريقنا لديك منطقي
كلمة وعقدة البنية * الأطفال

167
00:08:36,220 --> 00:08:37,470
قوس الأبجدية.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
وبالتالي فإن أول شيء قد يكون
أتساءل، لماذا هو الأبجدية

170
00:08:42,020 --> 00:08:44,660
إد يعرف بأنه 27؟

171
00:08:44,660 --> 00:08:47,900
كذلك، تذكر أننا سنحتاج الى
ليتم التعامل مع اقتباس أحادية.

172
00:08:47,900 --> 00:08:51,910
بحيث ستكون نوعا من
حالة خاصة خلال هذا البرنامج.

173
00:08:51,910 --> 00:08:54,710
>> الآن تذكر كيف TRIE
يعمل فعلا.

174
00:08:54,710 --> 00:08:59,380
دعونا نقول أننا فهرسة كلمة
"القطط". ثم من جذر TRIE،

175
00:08:59,380 --> 00:09:02,610
ونحن في طريقنا لإلقاء نظرة على الأطفال
مجموعة، ونحن في طريقنا للبحث في

176
00:09:02,610 --> 00:09:08,090
المؤشر الذي يتوافق مع رسالة
C. بحيث سيتم فهرستها 2.

177
00:09:08,090 --> 00:09:11,530
ذلك بالنظر إلى أن، أن الإرادة
تعطينا عقدة جديدة.

178
00:09:11,530 --> 00:09:13,820
ومن ثم سنعمل من تلك العقدة.

179
00:09:13,820 --> 00:09:17,770
>> ذلك بالنظر إلى أن عقدة، ونحن مرة أخرى
سوف ننظر في مجموعة الأطفال.

180
00:09:17,770 --> 00:09:22,110
ونحن في طريقنا للبحث في الفهرس الصفر
لتتوافق مع A في القط.

181
00:09:22,110 --> 00:09:27,170
حتى ذلك الحين ونحن في طريقنا للذهاب إلى تلك العقدة،
وبالنظر إلى أن عقدة ونحن في طريقنا

182
00:09:27,170 --> 00:09:31,090
أن ننظر إلى نهاية انها يتوافق
لT. والانتقال إلى تلك العقدة،

183
00:09:31,090 --> 00:09:35,530
أخيرا، لقد بدا تماما
من خلال كلمتنا "القط". ومنطقي الآن

184
00:09:35,530 --> 00:09:40,960
ومن المفترض الكلمة للإشارة إلى ما إذا كان
هذه كلمة معينة هو في الواقع كلمة واحدة.

185
00:09:40,960 --> 00:09:43,470
>> فلماذا نحتاج أن حالة خاصة؟

186
00:09:43,470 --> 00:09:47,700
جيدا ما للكلمة "كارثة"
في قاموسنا، ولكن

187
00:09:47,700 --> 00:09:50,150
كلمة "القط" هو لا؟

188
00:09:50,150 --> 00:09:54,580
لذلك، والتطلع إلى معرفة ما إذا كانت كلمة "القط"
يتم في قاموسنا، نحن

189
00:09:54,580 --> 00:09:59,970
سوف ننظر بنجاح من خلال
مؤشرات C-A-T في عقدة المنطقة.

190
00:09:59,970 --> 00:10:04,290
ولكن هذا فقط بسبب كارثة
حدث لإنشاء العقد على الطريق

191
00:10:04,290 --> 00:10:07,190
من C-A-T، وصولا إلى
في نهاية الكلمة.

192
00:10:07,190 --> 00:10:12,020
بحيث يتم استخدام كلمة منطقي للإشارة إلى ما إذا كان
هذا الموقع خاص

193
00:10:12,020 --> 00:10:14,310
يشير في الواقع كلمة.

194
00:10:14,310 --> 00:10:15,140
>> حسنا.

195
00:10:15,140 --> 00:10:19,310
حتى الآن أن نعرف ما هو TRIE
الذهاب لتبدو وكأنها، دعونا ننظر في

196
00:10:19,310 --> 00:10:20,730
تحميل وظيفة.

197
00:10:20,730 --> 00:10:24,610
ذلك الحمل هو الذهاب لإرجاع منطقي
لما إذا كنا بنجاح أو

198
00:10:24,610 --> 00:10:26,720
تحميل دون جدوى القاموس.

199
00:10:26,720 --> 00:10:30,460
وهذا سيكون القاموس
أننا نريد أن يتم تحميلها.

200
00:10:30,460 --> 00:10:33,930
>> أولا حتى شيء نحن القيام به هو فتح
حتى أن القاموس للقراءة.

201
00:10:33,930 --> 00:10:36,160
وعلينا أن نتأكد من
نحن لم تفشل.

202
00:10:36,160 --> 00:10:39,580
حتى إذا كان القاموس لا
افتتح بنجاح، فإنه سيعود

203
00:10:39,580 --> 00:10:42,400
فارغة، في هذه الحالة نحن
سوف تعود كاذبة.

204
00:10:42,400 --> 00:10:47,230
ولكن على افتراض أنه بنجاح
فتح، ثم يمكننا أن نقرأ الواقع

205
00:10:47,230 --> 00:10:48,220
من خلال القاموس.

206
00:10:48,220 --> 00:10:50,880
>> أولا حتى شيء ونحن في طريقنا ل
تريد القيام به هو لدينا هذا

207
00:10:50,880 --> 00:10:52,500
الجذر متغير عمومي.

208
00:10:52,500 --> 00:10:56,190
الآن الجذرية ستكون عقدة *.

209
00:10:56,190 --> 00:10:59,760
انها قمة TRIE لدينا أننا
ستكون بالتكرار عبر.

210
00:10:59,760 --> 00:11:02,660
وبالتالي فإن الشيء الأول الذي نحن ذاهبون
تريد القيام به هو تخصيص

211
00:11:02,660 --> 00:11:04,140
الذاكرة لدينا الجذر.

212
00:11:04,140 --> 00:11:07,980
تلاحظ أن نستخدمه في calloc
وظيفة، والتي هي في الأساس نفسه

213
00:11:07,980 --> 00:11:11,500
كما الدالة malloc، إلا انها
مضمونة للعودة شيء

214
00:11:11,500 --> 00:11:13,180
ركزت تماما.

215
00:11:13,180 --> 00:11:17,290
لذلك إذا كنا malloc، فإننا بحاجة إلى
تذهب من خلال جميع المؤشرات في موقعنا

216
00:11:17,290 --> 00:11:20,160
عقدة، وتأكد من أن
انهم جميعا فارغة.

217
00:11:20,160 --> 00:11:22,710
حتى calloc سوف نفعل ذلك بالنسبة لنا.

218
00:11:22,710 --> 00:11:26,330
>> الآن تماما مثل malloc، ونحن بحاجة للتأكد
التأكد من أن تخصيص كان في الواقع

219
00:11:26,330 --> 00:11:27,520
ناجحة.

220
00:11:27,520 --> 00:11:29,990
إذا كان هذا عاد فارغة، ثم نحن
تحتاج إلى إغلاق أو القاموس

221
00:11:29,990 --> 00:11:32,100
ملف وعودة كاذبة.

222
00:11:32,100 --> 00:11:36,835
حتى على افتراض أن تخصيص و
ناجحة، ونحن في طريقنا إلى استخدام عقدة *

223
00:11:36,835 --> 00:11:40,270
المؤشر إلى تكرار خلال TRIE لدينا.

224
00:11:40,270 --> 00:11:43,890
حتى جذورنا لن تتغير،
ولكن ونحن في طريقنا إلى استخدام المؤشر ل

225
00:11:43,890 --> 00:11:47,875
في الواقع الانتقال من عقدة إلى عقدة.

226
00:11:47,875 --> 00:11:50,940
>> حتى في هذا لأننا حلقة القراءة
من خلال ملف القاموس.

227
00:11:50,940 --> 00:11:53,670
ونستخدمه fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc هو الذهاب الى الاستيلاء على واحد
حرف من الملف.

229
00:11:56,290 --> 00:11:59,370
ونحن في طريقنا لمواصلة الاستيلاء
الأحرف في حين أننا لا تصل إلى

230
00:11:59,370 --> 00:12:01,570
نهاية الملف.

231
00:12:01,570 --> 00:12:03,480
>> هناك نوعان من الحالات التي تحتاج إلى معالجة.

232
00:12:03,480 --> 00:12:06,610
الأولى، إذا كان الحرف
لم يكن سطر جديد.

233
00:12:06,610 --> 00:12:10,450
حتى نعرف ما اذا كان هذا الخط الجديد، ثم
نحن على وشك الانتقال إلى كلمة جديدة.

234
00:12:10,450 --> 00:12:15,240
ولكن على افتراض أنه لم يكن سطر جديد، ثم
هنا نريد أن معرفة

235
00:12:15,240 --> 00:12:18,380
مؤشر نحن في طريقنا للمؤشر في
في مجموعة الأطفال التي

236
00:12:18,380 --> 00:12:19,810
ونحن ننظر في من قبل.

237
00:12:19,810 --> 00:12:23,880
>> لذلك، كما قلت من قبل، نحن بحاجة إلى
حالة خاصة اقتباس أحادية.

238
00:12:23,880 --> 00:12:26,220
لاحظ أننا باستخدام الثلاثي
المشغل هنا.

239
00:12:26,220 --> 00:12:29,580
لذلك نحن ذاهبون لقراءة هذا، إن
كان الطابع نقرأ في

240
00:12:29,580 --> 00:12:35,330
اقتباس أحادية، ثم نحن في طريقنا لتعيين
مؤشر = "الأبجدية" -1، والتي سوف

241
00:12:35,330 --> 00:12:37,680
يكون مؤشر 26.

242
00:12:37,680 --> 00:12:41,130
>> آخر، إذا لم يكن الفاصلة العليا، هناك
ونحن في طريقنا لتعيين المؤشر

243
00:12:41,130 --> 00:12:43,760
تساوي ج - أ.

244
00:12:43,760 --> 00:12:49,030
حتى أن نتذكر مرة أخرى من قبل ف مجموعات،
ج - هو ذاهب لإعطاء لنا

245
00:12:49,030 --> 00:12:53,410
موقف أبجدية حتى إذا C.
C هو حرف A، وهذا سوف

246
00:12:53,410 --> 00:12:54,700
تعطينا مؤشر الصفر.

247
00:12:54,700 --> 00:12:58,120
هذه الرسالة B، فإنه سيعطي
لنا مؤشر 1، وهلم جرا.

248
00:12:58,120 --> 00:13:03,010
>> لذلك هذا يعطينا مؤشر إلى
مجموعة الأطفال التي نريد.

249
00:13:03,010 --> 00:13:08,890
الآن إذا كان هذا المؤشر هو فارغة حاليا في
الأطفال، وهذا يعني أن العقدة

250
00:13:08,890 --> 00:13:11,830
غير موجود حاليا
من هذا الطريق.

251
00:13:11,830 --> 00:13:15,160
لذلك نحن بحاجة إلى تخصيص
عقدة لهذا المسار.

252
00:13:15,160 --> 00:13:16,550
وهذا ما سنقوم به هنا.

253
00:13:16,550 --> 00:13:20,690
>> لذلك نحن ذاهبون الى استخدام مرة أخرى calloc
وظيفة، بحيث لم يكن لدينا ل

254
00:13:20,690 --> 00:13:22,880
صفر خارج كل المؤشرات.

255
00:13:22,880 --> 00:13:27,240
ونحن بحاجة مرة أخرى للتحقق
لم تفشل أن calloc.

256
00:13:27,240 --> 00:13:30,700
إذا لم تفشل calloc، ثم نحن بحاجة
لتفريغ كل شيء، أغلق لدينا

257
00:13:30,700 --> 00:13:32,820
القاموس، وعودة كاذبة.

258
00:13:32,820 --> 00:13:40,050
حتى على افتراض أنه لم يفشل، ثم
هذا سيخلق طفل جديد بالنسبة لنا.

259
00:13:40,050 --> 00:13:41,930
ثم سنذهب الى هذا الطفل.

260
00:13:41,930 --> 00:13:44,960
سيكون المؤشر لدينا تكرار
وصولا الى هذا الطفل.

261
00:13:44,960 --> 00:13:49,330
>> الآن إذا كان هذا غير فارغة لتبدأ،
ثم المؤشر يمكن تكرار فقط

262
00:13:49,330 --> 00:13:52,590
وصولا الى هذا الطفل دون الواقع
الحاجة إلى تخصيص أي شيء.

263
00:13:52,590 --> 00:13:56,730
هذا هو الحال حيث أننا حصل الأول
تخصيص كلمة "القط". و

264
00:13:56,730 --> 00:14:00,330
وهذا يعني عندما نذهب إلى تخصيص
"كارثة" نحن لسنا بحاجة لخلق

265
00:14:00,330 --> 00:14:01,680
العقد ل C-A-T مرة أخرى.

266
00:14:01,680 --> 00:14:04,830
كانت موجودة بالفعل.

267
00:14:04,830 --> 00:14:06,080
>> ما هو هذا آخر؟

268
00:14:06,080 --> 00:14:10,480
هذا هو الشرط حيث كان ج
مائل n، حيث كان ج سطر جديد.

269
00:14:10,480 --> 00:14:13,710
وهذا يعني أن لدينا بنجاح
أكمل الكلمة.

270
00:14:13,710 --> 00:14:16,860
الآن ماذا نريد أن نفعل عندما كنا
بنجاح كلمة واحدة؟

271
00:14:16,860 --> 00:14:21,100
نحن ذاهبون الى استخدام هذا الحقل كلمة
داخل البنية عقدة لدينا.

272
00:14:21,100 --> 00:14:23,390
نحن نريد أن تعيين هذا إلى true.

273
00:14:23,390 --> 00:14:27,150
بحيث يشير إلى أن هذه العقدة
يدل على النجاح

274
00:14:27,150 --> 00:14:29,250
كلمة، وهي كلمة الفعلية.

275
00:14:29,250 --> 00:14:30,940
>> الآن تعيين هذا إلى true.

276
00:14:30,940 --> 00:14:35,150
نحن نريد لإعادة المؤشر إلى نقطة دينا
إلى بداية TRIE مرة أخرى.

277
00:14:35,150 --> 00:14:40,160
وأخيرا، زيادة قاموسنا
الحجم، منذ وجدنا عمل آخر.

278
00:14:40,160 --> 00:14:43,230
لذلك نحن في طريقنا للحفاظ على القيام بذلك،
قراءة في حرف بحرف،

279
00:14:43,230 --> 00:14:49,150
بناء العقد الجديد في TRIE لدينا و
لكل كلمة في القاموس، حتى

280
00:14:49,150 --> 00:14:54,020
ونحن في النهاية تصل إلى C! = EOF، الذي
الحالة نحن خروج من الملف.

281
00:14:54,020 --> 00:14:57,050
>> الآن هناك حالتين تحت
التي كنا قد ضرب EOF.

282
00:14:57,050 --> 00:15:00,980
الأول هو إذا كان هناك خطأ
القراءة من ملف.

283
00:15:00,980 --> 00:15:03,470
حتى إذا كان هناك خطأ، ونحن
تحتاج إلى القيام نموذجية.

284
00:15:03,470 --> 00:15:06,460
تفريغ كل شيء، على مقربة
الملف، عودة كاذبة.

285
00:15:06,460 --> 00:15:09,810
على افتراض لم يكن هناك خطأ، وهذا
يعني فقط أننا فعلا ضرب نهاية

286
00:15:09,810 --> 00:15:13,750
ملف، في هذه الحالة، فإننا إغلاق
ملف والعودة الحقيقية لأننا

287
00:15:13,750 --> 00:15:17,330
القاموس تحميلها بنجاح
في TRIE لدينا.

288
00:15:17,330 --> 00:15:20,170
>> حتى الآن دعونا تحقق من الاختيار.

289
00:15:20,170 --> 00:15:25,156
النظر في وظيفة الشيك، ونحن نرى
أن الاختيار هو الذهاب لإرجاع منطقي.

290
00:15:25,156 --> 00:15:29,680
فإنها ترجع صحيح إذا هذه الكلمة أنه
يتم تمريرها في TRIE لدينا.

291
00:15:29,680 --> 00:15:32,110
فإنها ترجع كاذبة خلاف ذلك.

292
00:15:32,110 --> 00:15:36,050
فكيف يتم تحديد ما إذا كان
هذه الكلمة هي في TRIE لدينا؟

293
00:15:36,050 --> 00:15:40,190
>> نرى هنا أنه، تماما مثل من قبل،
ونحن في طريقنا إلى استخدام المؤشر للتنقل

294
00:15:40,190 --> 00:15:41,970
من خلال TRIE لدينا.

295
00:15:41,970 --> 00:15:46,600
الآن هنا ونحن في طريقنا لتكرار
خلال موقعنا على الكلمة بأكملها.

296
00:15:46,600 --> 00:15:50,620
لذلك بالتكرار على كلمة نحن الماضية،
ونحن في طريقنا لتحديد

297
00:15:50,620 --> 00:15:56,400
مؤشر إلى مجموعة الأطفال التي
يقابل كلمة قوس أولا حتى هذا

298
00:15:56,400 --> 00:15:59,670
سوف تبدو تماما مثل
الحمل، حيث إن كلمة [أنا]

299
00:15:59,670 --> 00:16:03,310
والفاصلة العليا، ثم نريد
استخدام مؤشر "الأبجدية" - 1.

300
00:16:03,310 --> 00:16:05,350
لأننا قرر أن أن
هو المكان الذي نحن ذاهبون لتخزين

301
00:16:05,350 --> 00:16:07,100
الفواصل العليا.

302
00:16:07,100 --> 00:16:11,780
>> إلا فإننا ذاهبون إلى استخدام اثنين من أقل كلمة
قوس I. لذا تذكر تلك الكلمة يمكن

303
00:16:11,780 --> 00:16:13,920
يكون رأس المال التعسفي.

304
00:16:13,920 --> 00:16:17,540
ولذا فإننا نريد أن نتأكد من أننا
باستخدام نسخة صغيرة من الأشياء.

305
00:16:17,540 --> 00:16:21,920
ومن ثم طرح من أن 'ا' لمرة واحدة
مرة أخرى تعطينا الأبجدي

306
00:16:21,920 --> 00:16:23,880
موقف تلك الشخصية.

307
00:16:23,880 --> 00:16:27,680
بحيث سيكون لدينا مؤشر
في مجموعة الأطفال.

308
00:16:27,680 --> 00:16:32,420
>> والآن إذا كان هذا المؤشر في الأطفال
مجموعة باطل، وهذا يعني أننا

309
00:16:32,420 --> 00:16:34,990
لم تعد قادرة على الاستمرار بالتكرار
أسفل TRIE لدينا.

310
00:16:34,990 --> 00:16:38,870
إذا كان هذا هو الحال، هذه الكلمة لا يمكن
ربما يكون في TRIE لدينا.

311
00:16:38,870 --> 00:16:42,340
لأنه إذا جاز التعبير، التي من شأنها أن
يعني لن يكون هناك مسار

312
00:16:42,340 --> 00:16:43,510
وصولا الى تلك الكلمة.

313
00:16:43,510 --> 00:16:45,290
وأنك لن تواجه فارغة.

314
00:16:45,290 --> 00:16:47,850
لذلك تواجه فارغة، نعود كاذبة.

315
00:16:47,850 --> 00:16:49,840
كلمة ليست في القاموس.

316
00:16:49,840 --> 00:16:53,660
إذا لم تكن فارغة، ثم نحن
سوف تستمر بالتكرار.

317
00:16:53,660 --> 00:16:57,220
>> لذلك نحن ذاهبون الى هناك مؤشر
للإشارة إلى أن خاصة

318
00:16:57,220 --> 00:16:59,760
العقدة في هذا الفهرس.

319
00:16:59,760 --> 00:17:03,150
ونحافظ على فعل ذلك طوال
الكلمة بأكملها، على افتراض

320
00:17:03,150 --> 00:17:03,950
نحن أبدا ضرب فارغة.

321
00:17:03,950 --> 00:17:07,220
وهذا يعني أننا تمكنا من خلال الحصول على
الكلمة بأكملها والعثور

322
00:17:07,220 --> 00:17:08,920
عقدة في محاولة لدينا.

323
00:17:08,920 --> 00:17:10,770
لكننا لم تفعل تماما حتى الآن.

324
00:17:10,770 --> 00:17:12,290
>> نحن لا نريد فقط أن العودة الحقيقية.

325
00:17:12,290 --> 00:17:14,770
نريد أن نعود المؤشر> الكلمة.

326
00:17:14,770 --> 00:17:18,980
منذ نتذكر مرة أخرى، هو "القط" ليست
في قاموسنا، و "كارثة"

327
00:17:18,980 --> 00:17:22,935
و، فإننا سوف نحصل بنجاح
من خلال كلمة "القط". ولكن المؤشر

328
00:17:22,935 --> 00:17:25,760
وسوف تكون كلمة كاذبة وليس صحيحا.

329
00:17:25,760 --> 00:17:30,930
لذلك نعود للإشارة إلى كلمة المؤشر
إذا كانت هذه العقدة هي في الواقع كلمة واحدة.

330
00:17:30,930 --> 00:17:32,470
وهذا كل شيء عن الاختيار.

331
00:17:32,470 --> 00:17:34,250
>> لذلك دعونا تحقق من حجم.

332
00:17:34,250 --> 00:17:37,350
حتى حجم سيكون من السهل جدا
منذ ذلك الحين، نتذكر في الحمل، ونحن

333
00:17:37,350 --> 00:17:41,430
تزايد حجم القاموس ل
كل كلمة التي نواجهها.

334
00:17:41,430 --> 00:17:45,350
حتى حجم هو مجرد الذهاب الى
العودة القاموس الحجم.

335
00:17:45,350 --> 00:17:47,390
وهذا كل شيء.

336
00:17:47,390 --> 00:17:50,590
>> لذلك قمنا أخيرا تفريغ.

337
00:17:50,590 --> 00:17:55,100
حتى يفرغ، ونحن في طريقنا للاستخدام
وظيفة عودي إلى القيام به في الواقع كل

338
00:17:55,100 --> 00:17:56,530
العمل بالنسبة لنا.

339
00:17:56,530 --> 00:17:59,340
لذلك وظيفة لدينا هو الذهاب الى
أن يطلق على مفرغ.

340
00:17:59,340 --> 00:18:01,650
ما هو مفرغ تنوي القيام به؟

341
00:18:01,650 --> 00:18:06,580
نرى هنا أن يتم الانتقال إلى مفرغ
تكرار عبر جميع الأطفال في

342
00:18:06,580 --> 00:18:08,410
هذه عقدة معينة.

343
00:18:08,410 --> 00:18:11,750
وإذا كان الطفل ليس العقدة
فارغة، ثم نحن في طريقنا لل

344
00:18:11,750 --> 00:18:13,730
تفريغ عقدة الطفل.

345
00:18:13,730 --> 00:18:18,010
>> لذلك هذا هو أنت تفريغ متكرر
جميع أطفالنا.

346
00:18:18,010 --> 00:18:21,080
مرة واحدة ونحن على يقين من أن جميع أطفالنا
تم تفريغها، ثم نحن

347
00:18:21,080 --> 00:18:25,210
يمكن أن نحرر أنفسنا، لذلك
تفريغ أنفسنا.

348
00:18:25,210 --> 00:18:29,460
وهذا العمل بشكل متكرر
تفريغ TRIE بأكمله.

349
00:18:29,460 --> 00:18:32,850
ثم مرة واحدة فعلت ذلك،
يمكننا فقط العودة الحقيقية.

350
00:18:32,850 --> 00:18:34,210
لا يمكن أن تفشل تفريغ.

351
00:18:34,210 --> 00:18:35,710
نحن فقط تحرير الأشياء.

352
00:18:35,710 --> 00:18:38,870
ذلك مرة واحدة ننتهي تحرير
كل شيء، والعودة الحقيقية.

353
00:18:38,870 --> 00:18:40,320
وهذا كل شيء.

354
00:18:40,320 --> 00:18:41,080
اسمي روب.

355
00:18:41,080 --> 00:18:42,426
وكان هذا سبيلر.

356
00:18:42,426 --> 00:18:47,830
>> [عزف الموسيقى]