1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid در: گاهی اوقات، زمانی که ساختمان
برنامه، در صورت تمایل به استفاده از یک

3
00:00:10,890 --> 00:00:13,190
ساختمان داده شناخته شده به عنوان یک فرهنگ لغت.

4
00:00:13,190 --> 00:00:17,960
نقشه فرهنگ لغت کلید، که
معمولا رشته ها، به ارزش ها، نوع داده int،

5
00:00:17,960 --> 00:00:21,900
کاراکتر، یک اشاره گر به برخی از شیء،
هر آنچه که ما می خواهیم.

6
00:00:21,900 --> 00:00:26,510
درست مثل واژه نامه عادی
کلماتی را که نقشه را از طریق تعاریف.

7
00:00:26,510 --> 00:00:29,440
>> واژهنامهها ما با ارائه
توانایی ذخیره اطلاعات

8
00:00:29,440 --> 00:00:32,750
مرتبط با چیزی
و آن نگاه کنید تا بعد.

9
00:00:32,750 --> 00:00:36,620
پس چگونه ما در واقع پیاده سازی یک
فرهنگ لغت را، مثلا، کد C که ما می توانیم

10
00:00:36,620 --> 00:00:38,460
استفاده از در یکی از برنامه های ما؟

11
00:00:38,460 --> 00:00:41,790
خوب، هستند بسیاری از راه های وجود دارد که
ما می تواند یک فرهنگ لغت پیاده سازی.

12
00:00:41,790 --> 00:00:45,930
>> برای نمونه، ما می تواند یک آرایه استفاده کنید که به ما
به صورت پویا دوباره اندازه و یا ما می تواند استفاده

13
00:00:45,930 --> 00:00:49,150
لیست پیوندی، جدول هش
و یا یک درخت دودویی.

14
00:00:49,150 --> 00:00:52,250
اما هر چه که ما را انتخاب کنید، ما باید
و آگاه از بهره وری است و

15
00:00:52,250 --> 00:00:54,300
عملکرد از پیاده سازی.

16
00:00:54,300 --> 00:00:57,930
ما باید در مورد الگوریتم استفاده می شود فکر می کنم
برای وارد کردن و نگاه کردن آیتم ها به

17
00:00:57,930 --> 00:00:59,120
ساختار داده است.

18
00:00:59,120 --> 00:01:03,060
>> در حال حاضر، اجازه دهید فرض کنیم که ما
مایل به استفاده از رشته به عنوان کلید.

19
00:01:03,060 --> 00:01:07,290
بیایید در مورد یک امکان صحبت می کنید،
یک ساختمان داده به نام یک درخت پیشوندی.

20
00:01:07,290 --> 00:01:11,210
بنابراین در اینجا از نمایش تصویری است
از یک درخت پیشوندی.

21
00:01:11,210 --> 00:01:14,590
>> همانطور که در تصویر نشان می دهد، یک درخت پیشوندی
ساختمان داده درخت است

22
00:01:14,590 --> 00:01:16,050
گره ها با هم در ارتباط است.

23
00:01:16,050 --> 00:01:19,420
ما می بینیم که به وضوح ریشه وجود دارد
گره با برخی از لینک ها گسترش به

24
00:01:19,420 --> 00:01:20,500
گره های دیگر.

25
00:01:20,500 --> 00:01:23,040
اما آنچه هر گره تشکیل شده است؟

26
00:01:23,040 --> 00:01:26,700
اگر ما فرض کنیم که ما در حال ذخیره سازی کلید
تنها با حروف و

27
00:01:26,700 --> 00:01:30,150
ما در مورد سرمایه مهم نیست،
در اینجا تعریفی از یک گره که

28
00:01:30,150 --> 00:01:31,100
کفایت می کند.

29
00:01:31,100 --> 00:01:34,130
>> جسمی که نوع ساختار است
گره دارای دو بخش است

30
00:01:34,130 --> 00:01:35,740
به نام داده ها و کودکان.

31
00:01:35,740 --> 00:01:39,200
ما بخشی از داده به عنوان یک نظر را ترک کرده ام
به یک جزء جایگزین

32
00:01:39,200 --> 00:01:43,190
اعلامیه وقتی که یک ساختار است
ثبت شده در یک برنامه C.

33
00:01:43,190 --> 00:01:47,040
بخش داده ها از یک گره ممکن است یک
مقدار بولی نشان می دهد که آیا

34
00:01:47,040 --> 00:01:51,160
نه گره نشان دهنده تکمیل
یک کلید واژه یا آن را ممکن است

35
00:01:51,160 --> 00:01:54,240
رشته ای تعریف
از یک کلمه در فرهنگ لغت.

36
00:01:54,240 --> 00:01:58,870
>> ما یک صورت خندان را نشان می دهد استفاده از
هنگامی که داده ها در یک گره است.

37
00:01:58,870 --> 00:02:02,310
26 عناصر در وجود ما
آرایه کودکان، یک شاخص

38
00:02:02,310 --> 00:02:03,690
در حرف.

39
00:02:03,690 --> 00:02:06,570
ما اهمیت خواهید دید
از این به زودی.

40
00:02:06,570 --> 00:02:10,759
>> بیایید به بررسی دقیق تر از گره ریشه
در نمودار ما، که هیچ اطلاعات

41
00:02:10,759 --> 00:02:14,740
مرتبط با آن، به عنوان نشان
عدم وجود چهره لبخند در

42
00:02:14,740 --> 00:02:16,110
بخش داده ها.

43
00:02:16,110 --> 00:02:19,910
فلش که از بخش هایی از
آرایه کودکان نشان دهنده غیر گره

44
00:02:19,910 --> 00:02:21,640
اشاره گر به گره های دیگر.

45
00:02:21,640 --> 00:02:25,500
به عنوان مثال، فلش گسترش از
عنصر دوم کودکان

46
00:02:25,500 --> 00:02:28,400
نشان دهنده این نامه B
در یک کلید واژه.

47
00:02:28,400 --> 00:02:31,920
و در نمودار بزرگتر
ما آن را به برچسب با B.

48
00:02:31,920 --> 00:02:35,810
>> توجه داشته باشید که در نمودار بزرگتر، زمانی که ما
رسم یک اشاره گر به گره دیگر، آن

49
00:02:35,810 --> 00:02:39,100
مهم نیست که در آن نوک پیکان
ملاقات گره های دیگر.

50
00:02:39,100 --> 00:02:43,850
نمونه فرهنگ لغت ما درخت شامل
دو واژه، که و زوم.

51
00:02:43,850 --> 00:02:47,040
اجازه دهید به عنوان مثال از راه رفتن
به دنبال داده ها را برای یک کلید.

52
00:02:47,040 --> 00:02:50,800
>> فرض کنید ما می خواستیم برای نگاه کردن به
مقدار متناظر برای حمام کلیدی است.

53
00:02:50,800 --> 00:02:53,610
ما نگاه ما را تا شروع
در گره ریشه.

54
00:02:53,610 --> 00:02:57,870
سپس ما حرف اول ما را
کلید، B، و پیدا کردن مربوطه

55
00:02:57,870 --> 00:03:00,020
نقطه در آرایه فرزندان ما.

56
00:03:00,020 --> 00:03:04,490
توجه داشته باشید که دقیقا 26 نقطه وجود دارد
در آرایه، یکی برای هر حرف از

57
00:03:04,490 --> 00:03:05,330
حروف الفبا.

58
00:03:05,330 --> 00:03:08,800
و ما باید نقاط نشان دهنده
حرف از الفبا را به منظور.

59
00:03:08,800 --> 00:03:13,960
>> ما در شاخص دوم نگاه پس از آن،
شاخص یک، برای B. به طور کلی، اگر ما

60
00:03:13,960 --> 00:03:17,990
برخی از حروف الفبا که ما شخصیت C
می تواند نقطه مربوطه تعیین

61
00:03:17,990 --> 00:03:21,520
در آرایه کودکان با استفاده از
یک محاسبه مانند این.

62
00:03:21,520 --> 00:03:25,140
ما می توانستیم کودکان بزرگتر استفاده کرده اند
آرایه اگر ما می خواستیم برای ارائه نگاه کردن از

63
00:03:25,140 --> 00:03:28,380
کلید های با طیف وسیع تری از شخصیت ها،
مانند کل

64
00:03:28,380 --> 00:03:29,880
شخصیت ASCII تنظیم شده است.

65
00:03:29,880 --> 00:03:32,630
>> در این مورد، اشاره گر
در آرایه فرزندان ما در

66
00:03:32,630 --> 00:03:34,320
صفحه اول است تهی نیست.

67
00:03:34,320 --> 00:03:36,600
پس ما به دنبال ادامه
تا حمام کلیدی است.

68
00:03:36,600 --> 00:03:40,130
اگر ما همیشه مواجه می شوند یک اشاره گر تهی
در نقطه ای مناسب در کودکان

69
00:03:40,130 --> 00:03:43,230
آرایه در حالی که ما گره صرف،
پس ما باید بگویم که ما

70
00:03:43,230 --> 00:03:45,630
می تواند هر کاری برای آن کلید را پیدا کند.

71
00:03:45,630 --> 00:03:49,370
>> در حال حاضر، ما این نامه دوم را
ما کلید، A، و ادامه زیر

72
00:03:49,370 --> 00:03:52,400
اشاره گر در این راه تا زمانی که ما
رسیدن به پایان کلیدی ما است.

73
00:03:52,400 --> 00:03:56,530
اگر ما رسیدن به پایان کلید بدون
هدف قرار دادن هر گونه به پایان می رسد مرده، اشاره گر تهی،

74
00:03:56,530 --> 00:03:59,730
به عنوان مورد در اینجا این است، پس از آن تنها ما
باید برای بررسی یک چیز بیشتر.

75
00:03:59,730 --> 00:04:02,110
آیا این کلید در واقع
در فرهنگ لغت؟

76
00:04:02,110 --> 00:04:07,660
>> اگر چنین است، ما باید ارزش پیدا کردن، به خوبی
آیکون پذیری در نمودار ما که در آن

77
00:04:07,660 --> 00:04:08,750
کلمه به پایان میرسه.

78
00:04:08,750 --> 00:04:12,270
در صورتی که چیز دیگری ذخیره می شود وجود دارد
داده ها، پس ما می توانیم آن را بازگشت.

79
00:04:12,270 --> 00:04:16,500
به عنوان مثال، باغ وحش مهم این است که در نه
فرهنگ لغت، حتی اگر ما می تواند داشته باشد

80
00:04:16,500 --> 00:04:19,810
در پایان این کلید بدون رسید
هدف قرار دادن اشاره گر تهی، در حالی که ما

81
00:04:19,810 --> 00:04:21,089
تکرار از طریق این درخت به.

82
00:04:21,089 --> 00:04:25,436
>> اگر ما سعی در نگاه کردن به حمام کلیدی،
دوم به صفحه اول آرایه آخرین گره،

83
00:04:25,436 --> 00:04:28,750
مربوط به حرف H، می
یک اشاره گر تهی برگزار شد.

84
00:04:28,750 --> 00:04:31,120
بنابراین حمام در فرهنگ لغت نیست.

85
00:04:31,120 --> 00:04:34,800
و به این ترتیب یک درخت پیشوندی منحصر به فرد در آن کلید است
هرگز به صراحت در ذخیره

86
00:04:34,800 --> 00:04:36,650
ساختار داده ها.

87
00:04:36,650 --> 00:04:38,810
پس چگونه چیزی که ما وارد
به یک درخت پیشوندی؟

88
00:04:38,810 --> 00:04:41,780
>> اجازه دهید به کلید وارد
باغ وحش را به درخت به ما.

89
00:04:41,780 --> 00:04:46,120
به یاد داشته باشید که یک صورت خندان در یک گره
می تواند در کد به ساده دارد

90
00:04:46,120 --> 00:04:50,170
مقدار بولی نشان می دهد که باغ وحش
در فرهنگ لغت یا آن را می

91
00:04:50,170 --> 00:04:53,710
مربوط به اطلاعات بیشتری است که ما
مایل به معاشرت با باغ وحش های کلیدی،

92
00:04:53,710 --> 00:04:56,860
مانند تعریف از
کلمه یا چیز دیگری.

93
00:04:56,860 --> 00:05:00,350
در برخی از راه، روند به قرار دادن
چیزی را به یک درخت پیشوندی مشابه است

94
00:05:00,350 --> 00:05:02,060
به دنبال چیزی است که در یک درخت پیشوندی.

95
00:05:02,060 --> 00:05:05,720
>> ما با گره ریشه شروع دوباره،
اشاره گر زیر مربوط به

96
00:05:05,720 --> 00:05:07,990
نامه های کلیدی ما است.

97
00:05:07,990 --> 00:05:11,310
خوشبختانه، ما قادر به دنبال اشاره گر بودند
تمام راه را تا زمانی که ما رسیده

98
00:05:11,310 --> 00:05:12,770
در پایان کلید.

99
00:05:12,770 --> 00:05:16,480
از آنجا که باغ وحش یک پیشوند از کلمه است
زوم، که یک عضو از

100
00:05:16,480 --> 00:05:19,440
فرهنگ لغت، ما نیازی به
تخصیص هر گره جدید است.

101
00:05:19,440 --> 00:05:23,140
>> ما می توانیم گره تغییر به نشان می دهد که
مسیر از شخصیت های منجر به

102
00:05:23,140 --> 00:05:25,360
آن را نشان دهنده یک کلید در فرهنگ لغت ما.

103
00:05:25,360 --> 00:05:28,630
در حال حاضر، اجازه دهید سعی کنید از قرار دادن
BATH کلیدی به این درخت.

104
00:05:28,630 --> 00:05:32,260
ما به گره ریشه شروع
و به دنبال اشاره گر دوباره.

105
00:05:32,260 --> 00:05:35,620
اما در این وضعیت، ما به یک مرده
پایان قبل از ما قادر به رسیدن به هستی

106
00:05:35,620 --> 00:05:36,940
پایان کلید.

107
00:05:36,940 --> 00:05:40,980
در حال حاضر، ما نیاز به اختصاص برخی از جدید
گره نیاز به اختصاص یکی از جدید

108
00:05:40,980 --> 00:05:43,660
گره برای هر یک از باقی مانده
نامه کلیدی ما است.

109
00:05:43,660 --> 00:05:46,740
>> در این مورد، ما تنها نیاز داریم
برای تخصیص یک گره جدید است.

110
00:05:46,740 --> 00:05:50,590
سپس ما نیاز به ایجاد شاخص H
مرجع این گره جدید.

111
00:05:50,590 --> 00:05:54,070
یک بار دیگر، ما می توانیم گره را تغییر دهید
نشان می دهد که مسیر از شخصیت های

112
00:05:54,070 --> 00:05:57,120
منجر به آن را نشان دهنده
کلیدی در فرهنگ لغت ما.

113
00:05:57,120 --> 00:06:00,730
اجازه دهید در مورد مجانبی استدلال
پیچیدگی روش ما برای این

114
00:06:00,730 --> 00:06:02,110
دو عملیات.

115
00:06:02,110 --> 00:06:06,420
>> ما می بینیم که در هر دو مورد تعداد
از مراحل الگوریتم ما گرفت

116
00:06:06,420 --> 00:06:09,470
متناسب با تعداد
حرف در کلمه کلیدی.

117
00:06:09,470 --> 00:06:10,220
درست است.

118
00:06:10,220 --> 00:06:13,470
هنگامی که شما می خواهید برای پیدا کردن یک کلمه در یک
درخت شما فقط نیاز به تکرار از طریق

119
00:06:13,470 --> 00:06:17,100
نامه ها را یک به یک تا زمانی که شما یا
رسیدن به پایان کلمه یا

120
00:06:17,100 --> 00:06:19,060
ضربه به بن بست رسیده در این درخت.

121
00:06:19,060 --> 00:06:22,470
>> و هنگامی که شما مایل به قرار دادن یک کلید
جفت ارزش را به یک درخت پیشوندی با استفاده از

122
00:06:22,470 --> 00:06:26,250
روش مورد بحث ما، بدترین حالت
خواهد شد که شما تخصیص یک گره جدید

123
00:06:26,250 --> 00:06:27,550
برای هر حرف.

124
00:06:27,550 --> 00:06:31,290
و ما رو تو که تخصیص فرض
عملیات زمان ثابت است.

125
00:06:31,290 --> 00:06:35,850
بنابراین اگر ما فرض کنیم که طول کلید است
محدود شده توسط ثابت ثابت، هر دو

126
00:06:35,850 --> 00:06:39,400
درج و نگاه کردن ثابت می باشد
عملیات زمان برای یک درخت پیشوندی.

127
00:06:39,400 --> 00:06:42,930
>> اگر ما این فرض را ندارد که
طول کلید است که توسط یک ثابت محدود

128
00:06:42,930 --> 00:06:46,650
ثابت، و سپس قرار دادن و نگاه کردن،
در بدترین حالت، در خطی

129
00:06:46,650 --> 00:06:48,240
طول کلید.

130
00:06:48,240 --> 00:06:51,800
توجه داشته باشید که تعدادی از آیتم های ذخیره شده
در این درخت به این نگاه تاثیر نمی گذارد تا

131
00:06:51,800 --> 00:06:52,820
و یا زمان قرار دادن.

132
00:06:52,820 --> 00:06:55,360
این تنها توسط نهفته
طول کلید.

133
00:06:55,360 --> 00:06:59,300
>> در مقابل، اضافه کردن نوشته های به، بگو،
یک جدول هش منجر به

134
00:06:59,300 --> 00:07:01,250
آینده نگاه کردن کندتر است.

135
00:07:01,250 --> 00:07:04,520
در حالی که این ممکن است در ابتدا صدای جذاب،
ما باید به خاطر داشته باشید که یک

136
00:07:04,520 --> 00:07:08,740
پیچیدگی مطلوب مجانبی نمی کند
این معنی است که در عمل داده

137
00:07:08,740 --> 00:07:11,410
ساختار لزوما
فراتر از سرزنش.

138
00:07:11,410 --> 00:07:15,860
ما همچنین باید در نظر بگیرید که برای ذخیره
کلمه را در یک درخت پیشوندی ما نیاز داریم، در بدترین

139
00:07:15,860 --> 00:07:19,700
مورد، تعداد گره متناسب
به طول کلمه خود را.

140
00:07:19,700 --> 00:07:21,880
>> سعی می کند تمایل به استفاده از مقدار زیادی از فضای.

141
00:07:21,880 --> 00:07:25,620
که در مقایسه با یک جدول هش،
که در آن ما فقط نیاز به یک گره جدید به

142
00:07:25,620 --> 00:07:27,940
ذخیره برخی از جفت کلید.

143
00:07:27,940 --> 00:07:31,370
در حال حاضر، دوباره در تئوری، فضای بزرگ
مصرف می کند مانند بزرگ به نظر نمی رسد

144
00:07:31,370 --> 00:07:34,620
معامله، به ویژه آن که مدرن
کامپیوتر گیگابایت و

145
00:07:34,620 --> 00:07:36,180
گیگابایت از حافظه است.

146
00:07:36,180 --> 00:07:39,200
اما معلوم است که ما هنوز
در مورد استفاده از حافظه و نگرانی

147
00:07:39,200 --> 00:07:42,540
سازمان به خاطر
عملکرد، از کامپیوتر های مدرن

148
00:07:42,540 --> 00:07:46,960
مکانیسم در محل زیر
هود برای افزایش سرعت دسترسی به حافظه.

149
00:07:46,960 --> 00:07:51,180
>> اما این ساز و بهترین کار وقتی که
دسترسی به حافظه در جمع و جور ساخته شده

150
00:07:51,180 --> 00:07:52,810
مناطق و یا مناطق.

151
00:07:52,810 --> 00:07:55,910
و گره های یک درخت پیشوندی می تواند اقامت
در هر نقطه که پشته.

152
00:07:55,910 --> 00:07:58,390
اما این تجارت آف هستند
که ما باید در نظر بگیرند.

153
00:07:58,390 --> 00:08:01,440
>> به یاد داشته باشید که در هنگام انتخاب یک داده
ساختار برای یک کار مشخص، ما

154
00:08:01,440 --> 00:08:04,420
باید در مورد فکر می کنم چه نوع
عملیات ساختار داده ها نیاز به

155
00:08:04,420 --> 00:08:07,140
پشتیبانی و چه مقدار عملکرد
از هر یک از این

156
00:08:07,140 --> 00:08:09,080
عملیات امور به ما.

157
00:08:09,080 --> 00:08:11,300
این عملیات ممکن است حتی
گسترش فراتر از

158
00:08:11,300 --> 00:08:13,430
نگاه کردن پایه و درج.

159
00:08:13,430 --> 00:08:17,010
فرض کنید ما می خواستیم به پیاده سازی یک نوع
از قابلیت خودکار کامل، بسیار

160
00:08:17,010 --> 00:08:18,890
مانند موتور جستجوی گوگل می کند.

161
00:08:18,890 --> 00:08:22,210
که شده است، بازگشت همه کلید ها و
به طور بالقوه ارزش که

162
00:08:22,210 --> 00:08:24,130
یک پیشوند داده شده است.

163
00:08:24,130 --> 00:08:27,050
>> یک درخت پیشوندی منحصر به فرد مفید است
برای این عملیات.

164
00:08:27,050 --> 00:08:29,890
این آسان برای تکرار از طریق
این درخت برای هر شخصیت

165
00:08:29,890 --> 00:08:30,950
پیشوند.

166
00:08:30,950 --> 00:08:33,559
درست مثل یک عمل نگاه کردن،
ما می تواند اشاره گر را دنبال

167
00:08:33,559 --> 00:08:35,400
شخصیت های شخصیت.

168
00:08:35,400 --> 00:08:38,659
سپس، هنگامی که ما به پایان می رسد
پیشوند، ما می تواند از طریق تکرار

169
00:08:38,659 --> 00:08:42,049
بخش باقی مانده از ساختار داده ها
از هر یک از کلید فراتر از

170
00:08:42,049 --> 00:08:43,980
این نقطه دارای پیشوند.

171
00:08:43,980 --> 00:08:47,670
>> آن آسان است برای به دست آوردن این لیست
به ترتیب حروف الفبا از

172
00:08:47,670 --> 00:08:50,970
عناصر آرایه کودکان
ها بر اساس حروف الفبا مرتب می شوند.

173
00:08:50,970 --> 00:08:54,420
پس امیدوارم شما در نظر
دادن تلاش می کند را امتحان کنید.

174
00:08:54,420 --> 00:08:56,085
I کوین Schmid در هستم، و این CS50 است.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> آه، این آغاز است
از کاهش.

177
00:09:00,790 --> 00:09:01,350
من متاسفم.

178
00:09:01,350 --> 00:09:01,870
متأسفم.

179
00:09:01,870 --> 00:09:02,480
متأسفم.

180
00:09:02,480 --> 00:09:03,130
متأسفم.

181
00:09:03,130 --> 00:09:03,950
>> اعتصاب چهار.

182
00:09:03,950 --> 00:09:04,360
من هستم.

183
00:09:04,360 --> 00:09:05,280
متأسفم.

184
00:09:05,280 --> 00:09:06,500
متأسفم.

185
00:09:06,500 --> 00:09:07,490
متأسفم.

186
00:09:07,490 --> 00:09:12,352
با عرض پوزش برای ساخت شخصی که
به ویرایش این دیوانه.

187
00:09:12,352 --> 00:09:13,280
>> متأسفم.

188
00:09:13,280 --> 00:09:13,880
متأسفم.

189
00:09:13,880 --> 00:09:15,080
متأسفم.

190
00:09:15,080 --> 00:09:15,680
متأسفم.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: خوب انجام می شود.

192
00:09:16,280 --> 00:09:17,530
که واقعا به خوبی انجام شد.

193
00:09:17,530 --> 00:09:18,430