>> ROB BOWDEN: مرحبا.
أنا روب، ودعونا التجزئة هذا الحل للخروج.
حتى هنا ونحن في طريقنا لتنفيذ جدول تجزئة عامة.
ونحن نرى أن العقدة البنية من التجزئة لدينا الجدول سوف تبدو هذه.
لذلك ستكون لدينا كلمة شار مجموعة من طول حجم زائد 1.
لا ننسى 1 منذ الأقصى كلمة في القاموس هو 45
حرفا، ومن ثم نحن في طريقنا لل تحتاج حرف إضافي واحد ل
مائل 0.
>> ثم جدول التجزئة لدينا في كل دلو يجري لتخزين
قائمة مرتبطة العقد.
نحن لا نفعل الخطية التحقيق هنا.
وذلك من أجل ربط المقبل عنصر في دلو، ونحن بحاجة إلى
عقدة البنية * المقبل.
وهذا ما يبدو عقدة مثل.
الآن، وهنا هو إعلان من جدول التجزئة لدينا.
انها ستكون لدينا 16،384 والدلاء، ولكن لا هذا العدد لا يهم حقا.
وأخيرا، ونحن في طريقنا لديها hashtable_size المتغير العالمي، والتي
سوف تبدأ ك 0، وانها الذهاب لتتبع كيفية العديد من الكلمات
كانت في قاموسنا.
حسنا.
>> لذلك دعونا نلقي نظرة على الحمل.
لذلك تلاحظ أن الحمل، تقوم بإرجاع منطقي.
لك العودة الحقيقية إذا كان بنجاح تحميل وكاذبة خلاف ذلك.
ويستغرق شار كانت const * نجمة القاموس، والذي هو القاموس
أننا نريد لفتح.
ولهذا فإن أول شيء ونحن في طريقنا للقيام به.
ونحن في طريقنا إلى FOPEN القاموس ل القراءة، ونحن في طريقنا لديك
للتأكد من أنه حتى إذا نجحت عادت فارغة، ثم أننا لم
بنجاح فتح القاموس ونحن بحاجة إلى عودة كاذبة.
>> ولكن على افتراض أن فعلت بنجاح مفتوحة، ثم نريد أن قراءة
القاموس.
حتى تبقى حلقات حتى نجد بعض السبب للخروج من هذا
حلقة التي سنرى.
حتى تبقى حلقات، والآن ونحن في طريقنا لmalloc عقدة واحدة.
وبطبيعة الحال، نحن بحاجة إلى خطأ الاختيار مرة أخرى حتى إذا لم تنجح mallocing
ونحن نريد لتفريغ أي عقدة أننا حدث لmalloc قبل، إغلاق
القاموس وعودة كاذبة.
>> ولكن تجاهل ذلك، على افتراض أننا نجحت، ثم نريد أن استخدام fscanf
لقراءة كلمة واحدة من وجهة نظرنا القاموس في عقدة لدينا.
حتى أن نتذكر أن دخول> كلمة هو شار كلمة عازلة من طول زائد حجم
أحد أننا في طريقنا لل تخزين كلمة فيه.
حتى fscanf يجري في العودة 1 دام كما كان قادرا على قراءة بنجاح
كلمة من الملف.
>> إذا حدث أي خطأ أو نصل في نهاية الملف، وسوف لا
العودة 1 في هذه الحالة إذا لم يحدث ذلك عودة 1، ونحن في نهاية المطاف الذهاب الى كسر
للخروج من هذه الحلقة حين.
لذلك نرى أنه بمجرد أن لدينا بنجاح قراءة في كلمة
دخول> كلمة، ثم نحن في طريقنا للتجزئة تلك الكلمة باستخدام دالة البعثرة لدينا.
دعونا نلقي نظرة على وظيفة التجزئة.
>> لذلك لا تحتاج حقا لفهم هذا.
وفعلا، ونحن مجرد سحب هذه تجزئة وظيفة من الانترنت.
الشيء الوحيد الذي تحتاجه هو الاعتراف أن هذا يأخذ شار كانت const * كلمة،
حتى انها لاتخاذ سلسلة كمدخل و إرجاع صحيح غير الموقعة كإخراج.
بحيث كل وظيفة تجزئة هو، هو يأخذ في المدخلات، وأنه يعطي لك
فهرس في جدول التجزئة.
لاحظ أننا الشعيب بواسطة NUM_BUCKETS حتى إرجاع قيمة تجزئة
هو في الواقع فهرس في جدول التجزئة ومؤشر لا تتجاوز
حدود الصفيف.
>> ذلك بالنظر إلى أن وظيفة تجزئة، ونحن في طريقنا إلى تجزئة الكلمة التي نقرأ
من القاموس ثم نحن في طريقنا لاستخدام هذا أن إدراج
الدخول إلى جدول التجزئة.
الآن، تجزئة hashtable هو الحالي قائمة مرتبطة في جدول التجزئة، و
فمن الممكن جدا أن هو فقط NULL.
نحن نريد لإدراج دخولنا في ابتداء من هذه القائمة المرتبطة، وذلك
ونحن في طريقنا لدخول حالتنا الراهنة إشارة إلى ما جدول التجزئة حاليا
نقاط لثم نحن في طريقنا لتخزين في جدول التجزئة في التجزئة
الإدخال الحالي.
>> حتى هذين الخطين إدراج بنجاح دخول في بداية
قائمة مرتبطة في ذلك مؤشر في جدول التجزئة.
مرة واحدة ننتهي مع هذا، ونحن نعلم أننا وجدنا كلمة أخرى في
القاموس، ونحن زيادة مرة أخرى.
لذلك علينا أن نحافظ يفعل ذلك حتى fscanf أخيرا يعود شيء غير 1 في
هذه النقطة نتذكر أننا في حاجة إلى الدخول مجانا، لذلك هنا، ونحن لmalloced
الدخول وحاولنا أن نقرأ شيئا من القاموس.
ونحن لم يقرأ بنجاح شيء من القاموس الذي
الحالة نحن بحاجة لتحرير دخول أننا لم يضع فعلا في جدول التجزئة
وكسر في نهاية المطاف.
>> بمجرد أن تندلع، ونحن بحاجة الى ان نرى، أيضا، نحن لم تندلع بسبب وجود
كان يقرأ خطأ من ملف، أو نحن لم تندلع بسبب وصلنا
نهاية الملف؟
إذا كان هناك خطأ، ثم نريد أن عودة كاذبة لأن الحمل لم
النجاح، وفي هذه العملية، ونحن نريد ل تفريغ جميع الكلمات التي نقرأ
في وإغلاق ملف القاموس.
على افتراض أننا لم ننجح، فإننا فقط لا تزال بحاجة لإغلاق القاموس
ملف، وأخيرا العودة الحقيقية منذ لقد تحميلها بنجاح
القاموس.
وهذا كل شيء عن الحمل.
>> حتى تحقق الآن، ونظرا لجدول التجزئة تحميلها، سوف تبدو هذه.
حتى تحقق، تقوم بإرجاع منطقي، والتي هو ذاهب لبيان ما إذا كان
مرت في شار * كلمة واحدة، ما إذا كان مرت في السلسلة في قاموسنا.
حتى إذا كان في القاموس، وإذا كان في جدول التجزئة لدينا، وسوف نعود
صحيح، وإذا لم يكن، وسوف نعود كاذبة.
تعطى هذه الكلمة مرت في، نحن الذهاب إلى تجزئة الكلمة.
>> الآن، والشيء المهم هو الاعتراف أنه في الحمل، وكنا نعرف أن كل من
الكلمات ذاهبون إلى أن تكون أقل حدة، ولكن هنا، ونحن لسنا على يقين من ذلك.
إذا كان لنا أن نلقي نظرة على وظيفة التجزئة لدينا، دالة البعثرة لدينا في الواقع
وlowercasing كل حرف للكلمة.
ذلك بغض النظر عن رسملة كلمة، وظيفة تجزئة لدينا هو ذاهب ل
نعود لنفس المؤشر لأيا كان القيمة هو ما سيكون له
عاد لصغيرة تماما نسخة للكلمة.
حسنا.
>> ذلك أن فهرسنا.
انها جدول التجزئة لهذه الكلمة.
الآن، وهذا لحلقة يجري إلى أكثر القائمة المرتبطة
التي كانت في ذلك مؤشر.
حتى إشعار نحن تهيئة الدخول للإشارة إلى أن مؤشر.
ونحن في طريقنا لمواصلة بينما لا دخول لا NULL على قدم المساواة، وتذكر أن
تحديث المؤشر في قائمة مرتبطة لدينا يساوي دخول دخول> المقبل، بحيث يكون
وجهة نظرنا المدخل الحالي لل العنصر التالي في قائمة مرتبطة.
حسنا.
>> لذلك لكل إدخال في القائمة المرتبطة، ونحن في طريقنا لاستخدام strcasecmp.
انها ليست بسبب strcmp مرة أخرى، ونحن تريد أن تفعل أشياء حالة اكتراث.
لذلك نحن نستخدم strcasecmp مقارنة كلمة التي تم تمريرها إلى هذه الوظيفة
ضد الكلمة التي هو في هذا الإدخال.
اذا عاد 0، وهذا يعني أن هناك مباراة، وفي هذه الحالة نريد أن
العودة الحقيقية.
وجدنا بنجاح كلمة في جدول التجزئة لدينا.
>> إذا لم يكن هناك تطابق، ثم نحن الذهاب الى حلقة مرة أخرى وإلقاء نظرة على
الإدخال التالي.
وسوف نستمر في حين أن هناك حلقات هي الإدخالات في هذه القائمة المرتبطة.
ماذا يحدث إذا ما تم كسر للخروج من هذه الحلقة ل؟
وهذا يعني أننا لم نجد أن إدخال يقابل هذه الكلمة، وفي هذه الحالة
نعود كاذبة تشير إلى أن لدينا لم جدول التجزئة لا يحتوي على هذه الكلمة.
وهذا كل شيء عن الاختيار.
حسنا.
>> لذلك دعونا نلقي نظرة على الحجم.
الآن، حجم ستكون بسيطة جدا تذكر منذ ذلك الحين في الحمل، لكل كلمة
وجدنا أننا زيادة عالمي hashtable_size متغير.
وبالتالي فإن وظيفة حجم هو فقط سوف تعود أن العالمية
متغير، وهذا كل شيء.
>> الآن أخيرا، نحن بحاجة إلى تفريغ القاموس مرة واحدة انها فعلت كل شيء.
فكيف نحن ذاهبون للقيام بذلك؟
الحق هنا، ونحن على كل حلقات دلاء من جدول التجزئة لدينا.
لذلك هناك NUM_BUCKETS الدلاء.
ولكل قائمة مرتبطة في تجزئة لدينا الجدول، ونحن في طريقنا للحلقة على مدى
مجمل القائمة المرتبطة تحرير كل عنصر.
الآن، نحن بحاجة إلى أن نكون حذرين، لذلك نحن هنا لديك متغير مؤقت وهذا
تخزين المؤشر إلى القادم عنصر في قائمة مرتبطة.
ثم ونحن في طريقنا إلى الحرة العنصر الحالي.
>> نحن بحاجة للتأكد من أننا نفعل ذلك لأننا لا يمكن فقط تحرير العنصر الحالي
ومن ثم محاولة الوصول إلى مؤشر المقبل منذ بمجرد ان تحريرها و
الذاكرة تصبح غير صالحة.
لذلك نحن بحاجة للحفاظ على حول المؤشر ل العنصر التالي، ثم يمكننا أن تحرير
العنصر الحالي، وبعد ذلك يمكننا تحديث العنصر الحالي لدينا للإشارة إلى
العنصر التالي.
>> سنقوم حلقة في حين أن هناك عناصر في هذه القائمة المرتبطة.
ونحن سوف نفعل ذلك لجميع القوائم المرتبطة في جدول التجزئة، ومرة ​​واحدة ننتهي
مع ذلك، لقد أفرغت تماما جدول التجزئة، وننتهي.
لذلك فمن المستحيل لافرغت من أي وقت مضى عودة كاذبة، وعندما ننتهي، ونحن
مجرد العودة الحقيقية.