1
00:00:00,000 --> 00:00:11,856

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

3
00:00:13,050 --> 00:00:16,210
أنا روب، ودعونا التجزئة
هذا الحل للخروج.

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

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

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

7
00:00:28,710 --> 00:00:32,259
لا ننسى 1 منذ الأقصى
كلمة في القاموس هو 45

8
00:00:32,259 --> 00:00:35,110
حرفا، ومن ثم نحن في طريقنا لل
تحتاج حرف إضافي واحد ل

9
00:00:35,110 --> 00:00:37,070
مائل 0.

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

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

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

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

14
00:00:48,430 --> 00:00:51,110
عقدة البنية * المقبل.

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

16
00:00:53,090 --> 00:00:56,180
الآن، وهنا هو إعلان
من جدول التجزئة لدينا.

17
00:00:56,180 --> 00:01:01,910
انها ستكون لدينا 16،384 والدلاء، ولكن
لا هذا العدد لا يهم حقا.

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

19
00:01:05,450 --> 00:01:08,640
سوف تبدأ ك 0، وانها
الذهاب لتتبع كيفية العديد من الكلمات

20
00:01:08,640 --> 00:01:10,080
كانت في قاموسنا.

21
00:01:10,080 --> 00:01:10,760
حسنا.

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

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

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

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

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

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

28
00:01:27,170 --> 00:01:30,420
ونحن في طريقنا إلى FOPEN القاموس ل
القراءة، ونحن في طريقنا لديك

29
00:01:30,420 --> 00:01:34,700
للتأكد من أنه حتى إذا نجحت
عادت فارغة، ثم أننا لم

30
00:01:34,700 --> 00:01:37,440
بنجاح فتح القاموس
ونحن بحاجة إلى عودة كاذبة.

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

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

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

34
00:01:46,210 --> 00:01:47,570
حلقة التي سنرى.

35
00:01:47,570 --> 00:01:51,780
حتى تبقى حلقات، والآن ونحن في طريقنا
لmalloc عقدة واحدة.

36
00:01:51,780 --> 00:01:56,800
وبطبيعة الحال، نحن بحاجة إلى خطأ الاختيار
مرة أخرى حتى إذا لم تنجح mallocing

37
00:01:56,800 --> 00:02:00,660
ونحن نريد لتفريغ أي عقدة أننا
حدث لmalloc قبل، إغلاق

38
00:02:00,660 --> 00:02:02,590
القاموس وعودة كاذبة.

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

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

41
00:02:12,400 --> 00:02:17,310
حتى أن نتذكر أن دخول> كلمة هو شار
كلمة عازلة من طول زائد حجم

42
00:02:17,310 --> 00:02:20,300
أحد أننا في طريقنا لل
تخزين كلمة فيه.

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

44
00:02:25,280 --> 00:02:26,750
كلمة من الملف.

45
00:02:26,750 --> 00:02:31,030
>> إذا حدث أي خطأ أو نصل
في نهاية الملف، وسوف لا

46
00:02:31,030 --> 00:02:34,950
العودة 1 في هذه الحالة إذا لم يحدث ذلك
عودة 1، ونحن في نهاية المطاف الذهاب الى كسر

47
00:02:34,950 --> 00:02:37,280
للخروج من هذه الحلقة حين.

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

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

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

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

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

53
00:02:55,610 --> 00:02:59,460
وفعلا، ونحن مجرد سحب هذه
تجزئة وظيفة من الانترنت.

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

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

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

57
00:03:12,360 --> 00:03:14,490
فهرس في جدول التجزئة.

58
00:03:14,490 --> 00:03:18,530
لاحظ أننا الشعيب بواسطة NUM_BUCKETS
حتى إرجاع قيمة تجزئة

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

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

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

62
00:03:27,855 --> 00:03:31,700
من القاموس ثم نحن في طريقنا
لاستخدام هذا أن إدراج

63
00:03:31,700 --> 00:03:33,750
الدخول إلى جدول التجزئة.

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

65
00:03:38,830 --> 00:03:41,410
فمن الممكن جدا أن هو فقط NULL.

66
00:03:41,410 --> 00:03:45,640
نحن نريد لإدراج دخولنا في
ابتداء من هذه القائمة المرتبطة، وذلك

67
00:03:45,640 --> 00:03:48,910
ونحن في طريقنا لدخول حالتنا الراهنة
إشارة إلى ما جدول التجزئة حاليا

68
00:03:48,910 --> 00:03:54,030
نقاط لثم نحن في طريقنا لتخزين
في جدول التجزئة في التجزئة

69
00:03:54,030 --> 00:03:55,350
الإدخال الحالي.

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

71
00:03:59,320 --> 00:04:02,270
قائمة مرتبطة في ذلك مؤشر
في جدول التجزئة.

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

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

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

75
00:04:13,960 --> 00:04:18,560
هذه النقطة نتذكر أننا في حاجة إلى
الدخول مجانا، لذلك هنا، ونحن لmalloced

76
00:04:18,560 --> 00:04:21,329
الدخول وحاولنا أن نقرأ شيئا
من القاموس.

77
00:04:21,329 --> 00:04:24,110
ونحن لم يقرأ بنجاح
شيء من القاموس الذي

78
00:04:24,110 --> 00:04:27,440
الحالة نحن بحاجة لتحرير دخول أننا
لم يضع فعلا في جدول التجزئة

79
00:04:27,440 --> 00:04:29,110
وكسر في نهاية المطاف.

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

81
00:04:32,750 --> 00:04:35,840
كان يقرأ خطأ من ملف، أو
نحن لم تندلع بسبب وصلنا

82
00:04:35,840 --> 00:04:37,120
نهاية الملف؟

83
00:04:37,120 --> 00:04:40,150
إذا كان هناك خطأ، ثم نريد أن
عودة كاذبة لأن الحمل لم

84
00:04:40,150 --> 00:04:43,260
النجاح، وفي هذه العملية، ونحن نريد ل
تفريغ جميع الكلمات التي نقرأ

85
00:04:43,260 --> 00:04:45,670
في وإغلاق ملف القاموس.

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

87
00:04:48,740 --> 00:04:51,970
ملف، وأخيرا العودة الحقيقية منذ
لقد تحميلها بنجاح

88
00:04:51,970 --> 00:04:53,040
القاموس.

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

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

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

92
00:05:02,690 --> 00:05:07,530
مرت في شار * كلمة واحدة، ما إذا كان
مرت في السلسلة في قاموسنا.

93
00:05:07,530 --> 00:05:10,530
حتى إذا كان في القاموس، وإذا كان
في جدول التجزئة لدينا، وسوف نعود

94
00:05:10,530 --> 00:05:13,380
صحيح، وإذا لم يكن،
وسوف نعود كاذبة.

95
00:05:13,380 --> 00:05:17,770
تعطى هذه الكلمة مرت في، نحن
الذهاب إلى تجزئة الكلمة.

96
00:05:17,770 --> 00:05:22,020
>> الآن، والشيء المهم هو الاعتراف
أنه في الحمل، وكنا نعرف أن كل من

97
00:05:22,020 --> 00:05:25,820
الكلمات ذاهبون إلى أن تكون أقل حدة،
ولكن هنا، ونحن لسنا على يقين من ذلك.

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

99
00:05:29,510 --> 00:05:32,700
وlowercasing كل حرف
للكلمة.

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

101
00:05:37,580 --> 00:05:42,270
نعود لنفس المؤشر لأيا كان
القيمة هو ما سيكون له

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

103
00:05:45,280 --> 00:05:45,950
حسنا.

104
00:05:45,950 --> 00:05:47,410
>> ذلك أن فهرسنا.

105
00:05:47,410 --> 00:05:49,790
انها جدول التجزئة لهذه الكلمة.

106
00:05:49,790 --> 00:05:52,940
الآن، وهذا لحلقة يجري
إلى أكثر القائمة المرتبطة

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

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

109
00:05:59,630 --> 00:06:03,480
ونحن في طريقنا لمواصلة بينما لا دخول
لا NULL على قدم المساواة، وتذكر أن

110
00:06:03,480 --> 00:06:08,350
تحديث المؤشر في قائمة مرتبطة لدينا
يساوي دخول دخول> المقبل، بحيث يكون

111
00:06:08,350 --> 00:06:13,840
وجهة نظرنا المدخل الحالي لل
العنصر التالي في قائمة مرتبطة.

112
00:06:13,840 --> 00:06:14,400
حسنا.

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

114
00:06:19,150 --> 00:06:23,780
انها ليست بسبب strcmp مرة أخرى، ونحن
تريد أن تفعل أشياء حالة اكتراث.

115
00:06:23,780 --> 00:06:28,830
لذلك نحن نستخدم strcasecmp مقارنة كلمة
التي تم تمريرها إلى هذه الوظيفة

116
00:06:28,830 --> 00:06:31,860
ضد الكلمة التي
هو في هذا الإدخال.

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

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

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

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

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

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

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

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

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

126
00:07:00,220 --> 00:07:01,910
وهذا كل شيء عن الاختيار.

127
00:07:01,910 --> 00:07:02,540
حسنا.

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

129
00:07:04,790 --> 00:07:09,280
الآن، حجم ستكون بسيطة جدا
تذكر منذ ذلك الحين في الحمل، لكل كلمة

130
00:07:09,280 --> 00:07:12,880
وجدنا أننا زيادة عالمي
hashtable_size متغير.

131
00:07:12,880 --> 00:07:15,830
وبالتالي فإن وظيفة حجم هو فقط
سوف تعود أن العالمية

132
00:07:15,830 --> 00:07:18,150
متغير، وهذا كل شيء.

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

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

135
00:07:25,340 --> 00:07:30,440
الحق هنا، ونحن على كل حلقات
دلاء من جدول التجزئة لدينا.

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

137
00:07:33,240 --> 00:07:37,490
ولكل قائمة مرتبطة في تجزئة لدينا
الجدول، ونحن في طريقنا للحلقة على مدى

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

139
00:07:41,070 --> 00:07:46,070
الآن، نحن بحاجة إلى أن نكون حذرين، لذلك نحن هنا
لديك متغير مؤقت وهذا

140
00:07:46,070 --> 00:07:49,740
تخزين المؤشر إلى القادم
عنصر في قائمة مرتبطة.

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

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

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

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

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

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

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

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

149
00:08:12,770 --> 00:08:16,450
ونحن سوف نفعل ذلك لجميع القوائم المرتبطة في
جدول التجزئة، ومرة ​​واحدة ننتهي

150
00:08:16,450 --> 00:08:20,180
مع ذلك، لقد أفرغت تماما
جدول التجزئة، وننتهي.

151
00:08:20,180 --> 00:08:24,050
لذلك فمن المستحيل لافرغت من أي وقت مضى
عودة كاذبة، وعندما ننتهي، ونحن

152
00:08:24,050 --> 00:08:25,320
مجرد العودة الحقيقية.

153
00:08:25,320 --> 00:08:27,563