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
I راب هستم، و هش اجازه
در این راه حل است.

4
00:00:16,210 --> 00:00:20,070
بنابراین در اینجا ما قصد داریم به پیاده سازی
جدول hash است.

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
آن را به 16384 سطل، اما
که تعدادی واقعا مهم نیست.

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
شما به راست اگر آن را با موفقیت بود
بارگذاری شده و غیر این صورت false.

25
00:01:20,530 --> 00:01:23,990
و آن را به کاراکتر * ستاره ثابت
فرهنگ لغت است که فرهنگ لغت

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
مطمئن شوید که پس از آن اگر موفق
آن NULL بازگشت، پس از آن ما نبود

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
تنها چیزی که شما نیاز به شناخت است
که این طول می کشد کاراکتر توایع * کلمه،

55
00:03:04,010 --> 00:03:08,960
پس از آن به در نظر گرفتن یک رشته را به عنوان ورودی و
بازگشت به یک int بدون علامت به عنوان خروجی.

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
در حال حاضر، مخلوط پشته دارید در حال حاضر است
لیست پیوندی در جدول هش، و

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 نمی کند چرا که یک بار دیگر، ما
می خواهم به انجام کارهای مورد insensitively.

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