>> ROB BOWDEN: سلام.
I راب هستم، و هش اجازه در این راه حل است.
بنابراین در اینجا ما قصد داریم به پیاده سازی جدول hash است.
ما می بینیم که گره ساختار از مخلوط ما جدول است که به شبیه به این.
بنابراین آن را به یک کلمه کاراکتر مجموعه ای از طول اندازه به علاوه 1.
فراموش نکنید 1 از حداکثر ندارد کلمه در فرهنگ لغت 45 است
شخصیت، و پس از آن ما قصد داریم به نیاز به یک شخصیت اضافی برای
بک اسلش 0.
>> و پس از آن جدول هش ما در هر سطل است که برای ذخیره
لیست پیوندی از گره.
ما در حال انجام کاوش خطی نیست.
و بنابراین، به منظور پیوند به بعد عنصر در سطل، ما نیاز به یک
گره ساختار * بعدی.
بنابراین این چیزی است که یک گره به نظر می رسد.
در حال حاضر، در اینجا اعلام است جدول هش ما.
آن را به 16384 سطل، اما که تعدادی واقعا مهم نیست.
و در نهایت، ما قصد داریم به hashtable_size متغیر جهانی، که
در حال رفتن به شروع کردن به عنوان 0، و آن را رفتن به پیگیری چه بسیاری از واژه ها
در فرهنگ لغت ما بودند.
بسیار خوب.
>> بنابراین اجازه دهید نگاهی به بار.
بنابراین توجه کنید که بار، آن را می گرداند بولی.
شما به راست اگر آن را با موفقیت بود بارگذاری شده و غیر این صورت false.
و آن را به کاراکتر * ستاره ثابت فرهنگ لغت است که فرهنگ لغت
که ما می خواهیم برای باز کردن.
به طوری که اولین چیزی که است ما قصد داریم برای انجام این کار.
ما قصد داریم به fopen فرهنگ لغت برای خواندن، و ما در حال رفتن به
مطمئن شوید که پس از آن اگر موفق آن NULL بازگشت، پس از آن ما نبود
با موفقیت باز کردن فرهنگ لغت و ما نیاز به بازگشت کاذب.
>> اما فرض کنید که آن را با موفقیت انجام داد باز، پس از آن ما می خواهیم به عنوان خوانده شده
فرهنگ لغت.
بنابراین حلقه را تا زمانی پیدا کنیم و برخی از دلیلی برای گریز از این
حلقه که خواهیم دید.
بنابراین حفظ حلقه، و در حال حاضر ما در حال رفتن به malloc یک گره تک.
و البته، ما نیاز به خطای بررسی دوباره پس اگر mallocing موفق نبود
و ما می خواهیم برای خالی کردن هر گره که ما به malloc اتفاق افتاده است قبل از، نزدیک
فرهنگ لغت و نادرست بازگشت.
>> اما نادیده گرفتن آن، فرض ما موفق شد، پس از آن ما می خواهیم برای استفاده از fscanf
برای خواندن یک کلمه از ما دیکشنری به گره است.
بنابراین به یاد داشته باشید که کلمه ورود و> از کاراکتر است بافر کلمه از طول اندازه به علاوه
که ما قصد داریم به ذخیره کلمه شوید
بنابراین fscanf است که به بازگشت 1 تا زمانی به عنوان آن را قادر به موفقیت به عنوان خوانده شده بود
کلمه از فایل.
>> اگر هر دو خطا رخ می دهد و یا ما به در پایان فایل، آن را نمی
بازگشت 1 که در این صورت اگر آن را نمی کند بازگشت 1، ما در نهایت رفتن به شکستن
از این حلقه در حالی که.
بنابراین ما می بینیم که یک بار ما را با موفقیت خواندن کلمه به
ورود و> کلمه، پس از آن ما قصد داریم به هش آن کلمه را با استفاده از تابع هش ما.
اجازه دهید یک نگاه تابع هش.
>> بنابراین شما واقعا نیاز دارند برای درک این مطلب.
و در واقع، ما فقط این کشیده هش تابع از اینترنت.
تنها چیزی که شما نیاز به شناخت است که این طول می کشد کاراکتر توایع * کلمه،
پس از آن به در نظر گرفتن یک رشته را به عنوان ورودی و بازگشت به یک int بدون علامت به عنوان خروجی.
به طوری که تمام یک تابع هش است، آن را طول می کشد در ورودی، آن را به شما می دهد
شاخص به جدول هش.
توجه داشته باشید که ما در حال هواداران توسط NUM_BUCKETS به طوری که مقدار هش برگشتی
در واقع یک شاخص به جدول هش است و آیا شاخص نیست فراتر از
مرزهای آرایه.
>> بنابراین با توجه به اینکه تابع هش، ما قصد داریم به هش کلمه که ما به عنوان خوانده شده
از فرهنگ لغت و پس از آن ما قصد داریم برای استفاده است که برای وارد کردن
ورود به جدول هش.
در حال حاضر، مخلوط پشته دارید در حال حاضر است لیست پیوندی در جدول هش، و
بسیار ممکن است که فقط NULL.
ما می خواهیم برای وارد کردن ورود ما در ابتدای این لیست پیوندی، و غیره
ما در حال رفتن به ورودی فعلی ما اشاره به آنچه جدول هش در حال حاضر
امتیاز به و پس از آن ما قصد داریم به ذخیره در جدول هش را در مخلوط
ورودی فعلی.
>> بنابراین این دو خط با موفقیت وارد ورود در آغاز از
لیست پیوندی که در آن شاخص در جدول هش.
هنگامی که ما با آن انجام می شود، ما می دانیم که ما کلمه ای دیگر در بر داشت
فرهنگ لغت و ما افزایش دوباره.
بنابراین ما ادامه دهیم تا fscanf در نهایت چیزی غیر 1 در برمی گرداند
که نقطه به یاد داشته باشید که ما نیاز به ورود آزاد، بنابراین تا اینجا، ما malloced
ورود و ما سعی به خواندن چیزی از فرهنگ لغت.
و ما به موفقیت نمی خواند چیزی را از فرهنگ است که در آن
صورت ما نیاز به آزادی از ورود است که ما در واقع هرگز به جدول هش را
و در نهایت شکستن.
>> زمانی که ما از شکستن، ما نیاز به دیدن، خوب، به ما شکستن دلیل وجود دارد
شد خطا در خواندن از فایل و یا به ما شکستن چون ما رسیده است
در پایان فایل؟
اگر خطایی وجود دارد، پس از آن ما به خواهید بازگشت کاذب به دلیل بار نبود
موفقیت، و در این روند، ما به خواهید خالی کردن همه کلمات است که ما به عنوان خوانده شده
در و بستن پرونده فرهنگ لغت.
با فرض اینکه ما موفق شوند، پس ما فقط هنوز هم نیاز به بستن فرهنگ لغت
فایل، و در نهایت بازگشت از واقعی ما با موفقیت لود شده
فرهنگ لغت.
و که آن را برای بار.
>> بنابراین در حال حاضر را بررسی کنید، با توجه به جدول هش لود شده، رفتن به شبیه به این.
بنابراین بررسی کنید، آن را برمی گرداند بولی، که رفتن به نشان می دهد که آیا
گذشت در * کاراکتر کلمه، که آیا گذشت، در رشته در فرهنگ لغت ما است.
بنابراین اگر آن را در فرهنگ لغت است، اگر آن را در جدول هش ما، ما باز خواهد گشت
درست است، و اگر آن را ندارد، ما نادرست باز خواهد گشت.
با توجه به این کلمه گذشت در، ما هستیم رفتن به هش کلمه.
>> در حال حاضر، چیزی که مهم است به رسمیت شناختن است که در بار، ما می دانستیم که همه
کلمات قرار بود به صورت پایین تر، اما در اینجا، ما تا مطمئن نیستید.
اگر ما نگاهی به تابع هش ما، تابع هش ما در واقع
است lowercasing هر یک از شخصیت کلمه.
بنابراین بدون در نظر گرفتن سرمایه از کلمه، تابع هش ما در حال رفتن به
بازگشت به صفحه اول همین کار را برای هر سرمایه است که آن را باید
برای کاملا کوچک بازگشت نسخه از کلمه است.
بسیار خوب.
>> به طوری که شاخص ما است.
این جدول هش برای این کلمه است.
در حال حاضر، این حلقه در جریان است به بیش از لیست پیوندی
که در آن شاخص بود.
بنابراین متوجه ما مقدار دهی اولیه ورود به نقطه را به که شاخص.
ما قصد داریم به ادامه در حالی که ورود می کند نمی NULL برابر، و به یاد داشته باشید که
به روز رسانی اشاره گر در لیست پیوندی ما ورود برابر ورود و> بعد، پس
نقطه ورود فعلی ما به آیتم بعدی در لیست پیوندی.
بسیار خوب.
>> بنابراین برای هر ورودی در لیست پیوندی، ما قصد استفاده از strcasecmp.
این strcmp نمی کند چرا که یک بار دیگر، ما می خواهم به انجام کارهای مورد insensitively.
بنابراین ما استفاده strcasecmp برای مقایسه کلمه که به این تابع به تصویب رسید
در مقابل کلمه ای که در این مطلب می باشد.
اگر آن را می گرداند 0، این بدان معناست که وجود دارد یک بازی، که در این صورت ما به خواهید
بازگشت درست است.
ما با موفقیت در بر داشت کلمه در جدول هش ما.
>> بود اگر یک بازی وجود ندارد، پس ما رفتن به حلقه دوباره و در نگاه
نوشته بعدی.
و ما رو تو حلقه در حالی که وجود دارد ادامه ورودی در این لیست پیوندی می باشد.
اگر ما شکستن چه اتفاقی می افتد از این حلقه؟
این بدان معناست که ما ورود پیدا کند که تطبیق این کلمه، که در این صورت
ما بازگشت کاذب نشان می دهد که ما جدول هش را حاوی این کلمه نیست.
و که آن را برای چک.
بسیار خوب.
>> بنابراین اجازه دهید نگاهی به اندازه.
در حال حاضر، اندازه است برای رفتن به بسیار ساده از آنجا که در بار به یاد داشته باشید، برای هر کلمه
ما در بر داشت ما افزایش جهانی hashtable_size متغیر است.
بنابراین تابع اندازه است فقط رفتن به بازگشت که جهانی
متغیر، و آن نیست.
>> حالا در نهایت، ما نیاز به خالی کردن فرهنگ لغت یک بار همه چیز را انجام می شود.
پس چگونه می خواهیم به انجام این کار؟
در اینجا، ما حلقه بر همه سطل از جدول هش ما.
بنابراین NUM_BUCKETS سطل وجود دارد.
و برای هر یک از لیست پیوندی در مخلوط ما جدول، ما قصد داریم به حلقه در طول
به طور کامل از لیست پیوندی آزاد کردن هر عنصر.
در حال حاضر، ما باید مراقب باشید، بنابراین در اینجا ما یک متغیر موقت که
ذخیره سازی اشاره گر به بعد عنصر در لیست پیوندی.
و پس از آن ما قصد داریم به آزاد عنصر فعلی.
>> ما باید مطمئن شوید که ما این کار را از ما می تواند نه تنها آزاد عنصر فعلی
و سپس سعی کنید برای دسترسی به اشاره گر بعدی از زمانی که ما آن را آزاد
حافظه نامعتبر است.
بنابراین ما نیاز به نگه داشتن حدود یک اشاره گر به عنصر بعدی، پس از آن ما می تواند آزاد
عنصر فعلی، و پس از آن ما می تواند به روز رسانی عنصر فعلی ما به نقطه را به
عنصر بعدی.
>> ما حلقه در حالی که می خواهید عناصر وجود دارد در این لیست در ارتباط است.
ما کار را برای همه لیست های پیوندی در جدول هش، و زمانی که ما در حال انجام
با آن، ما به طور کامل تخلیه کرده ام جدول هش، و ما انجام می شود.
پس از آن غیر ممکن است برای بارگیری نشود تا کنون بازگشت کاذب، و زمانی که ما در حال انجام، ما
فقط به راست.