1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
داگ لوید: بنابراین در CS50، ما تحت پوشش ام
بسیاری از ساختمان های داده مختلف،

3
00:00:08,300 --> 00:00:09,180
درست؟

4
00:00:09,180 --> 00:00:11,420
ما آرایه دیده ام، و در ارتباط
لیست ها، و جداول هش،

5
00:00:11,420 --> 00:00:15,210
و تلاش می کند، پشته و صف.

6
00:00:15,210 --> 00:00:17,579
ما همچنین یک کمی یاد بگیرند
در مورد درختان و انبوه،

7
00:00:17,579 --> 00:00:20,120
اما واقعا این همه فقط پایان
تا که تغییرات در یک موضوع.

8
00:00:20,120 --> 00:00:22,840
واقعا وجود دارد این
نوع از چهار ایده های اساسی

9
00:00:22,840 --> 00:00:25,190
که هر چیز دیگری می تواند به جوش پایین.

10
00:00:25,190 --> 00:00:28,150
آرایه ها، لیست های پیوندی،
جداول هش، و تلاش می کند.

11
00:00:28,150 --> 00:00:30,720
و مثل من گفت، وجود دارد
تغییرات بر روی آنها،

12
00:00:30,720 --> 00:00:32,720
اما این است که بسیار
بسیار رفتن به طور خلاصه

13
00:00:32,720 --> 00:00:38,140
همه چیز ما قصد داریم به بحث
درباره در این کلاس در شرایط زبان C

14
00:00:38,140 --> 00:00:40,140
>> اما چگونه این همه را اندازه گیری تا، درست است؟

15
00:00:40,140 --> 00:00:44,265
ما در مورد جوانب مثبت و منفی صحبت کردیم
هر فیلم جداگانه در بر روی آنها،

16
00:00:44,265 --> 00:00:46,390
اما بسیاری از اعداد وجود دارد
گشتن پرتاب می شود.

17
00:00:46,390 --> 00:00:48,723
در بسیاری از کلی وجود دارد
افکار گشتن پرتاب می شود.

18
00:00:48,723 --> 00:00:51,950
بیایید امتحان کنید و تحکیم
آن را به یک مکان.

19
00:00:51,950 --> 00:00:55,507
بیایید وزن جوانب مثبت در برابر
منفی، و در نظر گرفتن

20
00:00:55,507 --> 00:00:57,340
که ساختار داده
ممکن است داده های سمت راست

21
00:00:57,340 --> 00:01:01,440
ساختار برای وضعیت خاص خود،
هر نوع از داده های شما در حال ذخیره سازی.

22
00:01:01,440 --> 00:01:06,625
شما لزوما همیشه نیاز به
استفاده از فوق العاده سریع درج، حذف،

23
00:01:06,625 --> 00:01:10,761
و مراجعه از یک درخت پیشوندی اگر شما واقعا
در مورد قرار دادن و حذف اهمیتی نمی

24
00:01:10,761 --> 00:01:11,260
خیلی زیاد.

25
00:01:11,260 --> 00:01:13,968
اگر شما نیاز به فقط به سرعت به صورت تصادفی
دسترسی، شاید یک آرایه بهتر است.

26
00:01:13,968 --> 00:01:15,340
بنابراین اجازه دهید که تقطیر.

27
00:01:15,340 --> 00:01:18,530
اجازه دهید در مورد هر یک از چهار صحبت
انواع عمده ای از ساختمان داده

28
00:01:18,530 --> 00:01:21,720
که ما در مورد صحبت کردیم، و
فقط زمانی که آنها ممکن است خوب،

29
00:01:21,720 --> 00:01:23,340
و زمانی که آنها ممکن است خیلی خوب است.

30
00:01:23,340 --> 00:01:24,610
بنابراین با آرایه شروع کنیم.

31
00:01:24,610 --> 00:01:27,300
بنابراین درج، که این نوع از بد است.

32
00:01:27,300 --> 00:01:31,350
>> درج در پایان یک آرایه خوب است،
اگر ما در حال ساخت یک آرایه به عنوان ما به.

33
00:01:31,350 --> 00:01:33,570
اما اگر ما نیاز به وارد کردن
عناصر را به وسط،

34
00:01:33,570 --> 00:01:35,550
فکر می کنم به درج
مرتب سازی بر اساس، بسیاری وجود دارد

35
00:01:35,550 --> 00:01:37,510
از تغییر به تناسب یک عنصر در آن وجود دارد.

36
00:01:37,510 --> 00:01:41,170
و به این ترتیب اگر ما قصد داریم به قرار دادن
در هر نقطه اما در پایان یک آرایه،

37
00:01:41,170 --> 00:01:43,590
که احتمالا آنقدر بزرگ نیست.

38
00:01:43,590 --> 00:01:46,710
>> به طور مشابه، حذف، مگر اینکه ما
حذف از پایان یک آرایه،

39
00:01:46,710 --> 00:01:49,810
است که احتمالا نه چندان بزرگ اگر
ما نمی خواهیم به ترک شکاف خالی،

40
00:01:49,810 --> 00:01:50,790
که معمولا ما نمی کنند.

41
00:01:50,790 --> 00:01:54,700
ما می خواهیم به حذف یک عنصر، و
پس از آن از آن را دوباره گرم و نرم.

42
00:01:54,700 --> 00:01:57,670
و به این ترتیب حذف عناصر
یک آرایه، نیز نه چندان بزرگ است.

43
00:01:57,670 --> 00:01:58,820
>> گرین کارت آمریکا، هر چند، بزرگ است.

44
00:01:58,820 --> 00:02:00,920
در حال حاضر دسترسی تصادفی،
گرین کارت آمریکا زمان ثابت.

45
00:02:00,920 --> 00:02:03,800
ما فقط می گویند هفت، و ما به
به آرایه جابجایی هفت.

46
00:02:03,800 --> 00:02:05,907
ما می گویند 20، با رفتن به
آرایه جابجایی 20.

47
00:02:05,907 --> 00:02:07,240
ما لازم نیست به تکرار در سراسر.

48
00:02:07,240 --> 00:02:08,630
این خیلی خوب است.

49
00:02:08,630 --> 00:02:11,020
>> آرایه نیز نسبتا آسان برای مرتب کردن هستند.

50
00:02:11,020 --> 00:02:14,040
هر بار که ما در مورد یک مرتب سازی صحبت
الگوریتم، مانند مرتب سازی انتخابی،

51
00:02:14,040 --> 00:02:18,820
مرتب سازی بر درج، مرتب سازی حبابی، ادغام
مرتب سازی بر اساس، ما همیشه آرایه استفاده به انجام آن،

52
00:02:18,820 --> 00:02:21,860
چون آرایه ها بسیار آسان برای
مرتب سازی بر اساس، نسبت به ساختارهای داده

53
00:02:21,860 --> 00:02:22,970
ما تا کنون دیده ام.

54
00:02:22,970 --> 00:02:24,320
>> آنها نیز نسبتا کوچک است.

55
00:02:24,320 --> 00:02:25,695
در بسیاری از فضای اضافی وجود ندارد.

56
00:02:25,695 --> 00:02:29,210
شما فقط خود را کنار بگذارند دقیقا به همان اندازه
عنوان شما نیاز به نگه داده های خود،

57
00:02:29,210 --> 00:02:30,320
و تقریبا آن.

58
00:02:30,320 --> 00:02:33,180
به طوری که آنها بسیار کوچک
و کارآمد در آن راه.

59
00:02:33,180 --> 00:02:36,000
اما زیان دیگر، هر چند،
این است که آنها در اندازه ثابت.

60
00:02:36,000 --> 00:02:38,630
ما باید به اعلام دقیقا چگونه
بزرگ ما می خواهیم ما را به عنوان آرایه،

61
00:02:38,630 --> 00:02:39,940
و ما فقط یک شات در آن را دریافت.

62
00:02:39,940 --> 00:02:41,280
ما نمی توانیم رشد و کوچک آن است.

63
00:02:41,280 --> 00:02:44,582
>> اگر ما نیاز به رشد و یا کوچک آن، ما
نیاز به آرایه کاملا جدید،

64
00:02:44,582 --> 00:02:47,750
کپی از تمام عناصر از
اولین آرایه به آرایه دوم.

65
00:02:47,750 --> 00:02:51,410
و اگر ما اشتباه محاسبه است که
زمان، ما نیاز به آن را دوباره.

66
00:02:51,410 --> 00:02:52,760
نه چندان بزرگ.

67
00:02:52,760 --> 00:02:58,750
بنابراین آرایه به ما انعطاف پذیری را نمی دهد
به شماره متغیر از عناصر.

68
00:02:58,750 --> 00:03:01,320
>> با یک لیست پیوندی،
درج بسیار آسان است.

69
00:03:01,320 --> 00:03:03,290
ما فقط بر روی جلو رویه.

70
00:03:03,290 --> 00:03:04,892
حذف نیز بسیار آسان است.

71
00:03:04,892 --> 00:03:06,100
ما باید برای پیدا کردن عناصر.

72
00:03:06,100 --> 00:03:07,270
که شامل برخی از جستجو.

73
00:03:07,270 --> 00:03:10,270
>> اما هنگامی که شما این عنصر را پیدا کرده ام
شما دنبال آن هستید، همه شما باید انجام دهید

74
00:03:10,270 --> 00:03:12,830
تغییر یک اشاره گر،
احتمالا دو اگر شما

75
00:03:12,830 --> 00:03:15,151
مرتبط list-- مضاعف
لیست پیوندی، rather--

76
00:03:15,151 --> 00:03:16,650
و سپس شما فقط می توانید گره.

77
00:03:16,650 --> 00:03:18,399
شما لازم نیست که به تغییر
همه چیز در اطراف.

78
00:03:18,399 --> 00:03:22,090
شما فقط تغییر دو اشاره گر،
به طوری که خیلی سریع است.

79
00:03:22,090 --> 00:03:23,470
>> گرین کارت آمریکا بد است هر چند، درست است؟

80
00:03:23,470 --> 00:03:26,280
به منظور برای ما برای پیدا کردن یک
عنصر در یک لیست پیوندی،

81
00:03:26,280 --> 00:03:29,154
آیا به تنهایی و یا مضاعف مرتبط،
ما باید به خطی آن را جستجو کنید.

82
00:03:29,154 --> 00:03:32,320
ما باید برای شروع در ابتدا و
حرکت پایان، و یا شروع در پایان حرکت

83
00:03:32,320 --> 00:03:33,860
به ابتدا.

84
00:03:33,860 --> 00:03:35,474
ما با دسترسی تصادفی دیگر ندارد.

85
00:03:35,474 --> 00:03:37,265
بنابراین اگر ما در حال انجام یک
بسیاری از جستجو، شاید

86
00:03:37,265 --> 00:03:39,830
یک لیست پیوندی است
کاملا برای ما خوب.

87
00:03:39,830 --> 00:03:43,750
>> آنها همچنین واقعا
مشکل مرتب سازی بر اساس، درست است؟

88
00:03:43,750 --> 00:03:45,666
تنها راهی که شما می توانید
واقعا مرتب سازی بر اساس یک لیست پیوندی

89
00:03:45,666 --> 00:03:47,870
است برای مرتب کردن آن را به عنوان شما آن را ساخت.

90
00:03:47,870 --> 00:03:50,497
اما اگر شما آن را مرتب به شما به عنوان
ساخت آن شما دیگر

91
00:03:50,497 --> 00:03:51,830
ساخت درج سریع نیست.

92
00:03:51,830 --> 00:03:53,746
شما نه تنها ضمیمه
چیز را بر روی جلو.

93
00:03:53,746 --> 00:03:55,710
شما باید برای پیدا کردن
نقطه سمت راست آن را قرار داده،

94
00:03:55,710 --> 00:03:57,820
و پس از آن خود را درج
می شود فقط در مورد به عنوان بد

95
00:03:57,820 --> 00:03:59,390
به عنوان قرار دادن به یک آرایه.

96
00:03:59,390 --> 00:04:03,130
بنابراین لیست های پیوندی نیست
آنقدر بزرگ برای مرتب سازی داده ها.

97
00:04:03,130 --> 00:04:05,830
>> آنها همچنین بسیار کوچک، اندازه عاقلانه است.

98
00:04:05,830 --> 00:04:08,496
لیست پیوندی مضاعف کمی
بزرگتر از لیست تنهایی مرتبط،

99
00:04:08,496 --> 00:04:10,620
که کمی بزرگتر
از آرایه، اما آن را نمی

100
00:04:10,620 --> 00:04:13,330
مقدار زیادی از فضای هدر رفته.

101
00:04:13,330 --> 00:04:18,730
بنابراین اگر فضا است در حق بیمه، اما
یک حق بیمه واقعا شدید،

102
00:04:18,730 --> 00:04:22,180
این ممکن است راه حق.

103
00:04:22,180 --> 00:04:23,330
>> جداول هش.

104
00:04:23,330 --> 00:04:25,850
درج در یک جدول هش
نسبتا ساده است.

105
00:04:25,850 --> 00:04:26,980
این یک فرآیند دو مرحله ای است.

106
00:04:26,980 --> 00:04:30,700
در ابتدا ما نیاز به اجرای داده ما را از طریق
یک تابع هش برای دریافت کد هش،

107
00:04:30,700 --> 00:04:37,550
و سپس ما این عنصر به قرار دادن
جدول هش در آن محل کد هش.

108
00:04:37,550 --> 00:04:40,879
>> حذف، شبیه به لیست پیوندی،
آسان است هنگامی که شما پیدا کردن عنصر.

109
00:04:40,879 --> 00:04:43,170
شما باید برای پیدا کردن آن برای اولین بار،
اما پس از آن زمانی که شما آن را حذف کنید،

110
00:04:43,170 --> 00:04:45,128
شما فقط نیاز به تبادل
یک زن و شوهر از اشاره گر،

111
00:04:45,128 --> 00:04:47,250
اگر شما با استفاده زنجیری جداگانه.

112
00:04:47,250 --> 00:04:49,942
اگر شما با استفاده پروبینگ،
و یا اگر شما نیست

113
00:04:49,942 --> 00:04:51,650
با استفاده از زنجیری در همه
در جدول هش خود را،

114
00:04:51,650 --> 00:04:53,040
حذف است که در واقع بسیار آسان است.

115
00:04:53,040 --> 00:04:57,134
همه شما باید انجام دهید این است که مقدار هش
داده، و سپس به آن مکان بروید.

116
00:04:57,134 --> 00:04:58,925
و با فرض شما نمی
هر گونه برخورد،

117
00:04:58,925 --> 00:05:01,650
شما قادر خواهید بود به سرعت حذف کنید.

118
00:05:01,650 --> 00:05:04,930
>> در حال حاضر، مراجعه که در آن همه چیز است
کمی پیچیده تر است.

119
00:05:04,930 --> 00:05:06,910
این به طور متوسط ​​بهتر است
از لیست های پیوندی.

120
00:05:06,910 --> 00:05:09,560
اگر شما با استفاده زنجیری،
شما هنوز هم یک لیست پیوندی،

121
00:05:09,560 --> 00:05:13,170
که بدان معنی است شما هنوز هم
جستجو آسیب بزند یک لیست پیوندی.

122
00:05:13,170 --> 00:05:18,390
اما از آنجا که شما در حال گرفتن خود را در ارتباط
لیست و تقسیم آن بیش از 100 یا 1،000

123
00:05:18,390 --> 00:05:25,380
و یا n عنصر در جدول هش خود را، شما
لیست های پیوندی همه یک n ام به اندازه.

124
00:05:25,380 --> 00:05:27,650
همه آنها قابل ملاحظه ای کوچکتر است.

125
00:05:27,650 --> 00:05:32,080
شما به جای N لیست مرتبط
یک لیست پیوندی با اندازه n.

126
00:05:32,080 --> 00:05:34,960
>> و این در دنیای واقعی ثابت
عامل، که به طور کلی ما

127
00:05:34,960 --> 00:05:39,730
در مورد پیچیدگی زمانی در صحبت نمی کند،
در واقع تفاوت را در اینجا.

128
00:05:39,730 --> 00:05:43,020
بنابراین گرین کارت آمریکا است که هنوز هم خطی
جستجو اگر شما با استفاده زنجیری،

129
00:05:43,020 --> 00:05:46,780
اما طول از لیست
شما در حال جستجو از طریق

130
00:05:46,780 --> 00:05:50,080
بسیار، بسیار در مقایسه کوتاه است.

131
00:05:50,080 --> 00:05:52,995
باز هم، اگر مرتب سازی خود را است
هدف در اینجا، هش جدول

132
00:05:52,995 --> 00:05:54,370
احتمالا راه حق.

133
00:05:54,370 --> 00:05:56,830
فقط یک آرایه استفاده کنید اگر مرتب سازی
که واقعا برای شما مهم است.

134
00:05:56,830 --> 00:05:58,590
>> و آنها می توانند زمینه هایی از اندازه را اجرا کنید.

135
00:05:58,590 --> 00:06:01,640
این سخت است برای گفتن که آیا یک
جدول هش کوچک یا بزرگ است،

136
00:06:01,640 --> 00:06:04,110
چون واقعا بستگی دارد
چقدر بزرگ جدول هش شما است.

137
00:06:04,110 --> 00:06:07,340
اگر شما تنها به ذخیره سازی شود که
پنج عنصر در جدول هش خود را،

138
00:06:07,340 --> 00:06:10,620
و شما باید یک جدول هش
با 10،000 عناصر در آن،

139
00:06:10,620 --> 00:06:12,614
شما احتمالا هدر رفتن مقدار زیادی از فضا.

140
00:06:12,614 --> 00:06:15,030
مقابل شما همچنین می توانید بودن
جداول هش بسیار جمع و جور،

141
00:06:15,030 --> 00:06:18,720
اما کوچکتر جدول هش شما می شود،
دیگر هر یک از این لیست های پیوندی

142
00:06:18,720 --> 00:06:19,220
می شود.

143
00:06:19,220 --> 00:06:22,607
و به این ترتیب واقعا هیچ راه برای تعریف وجود دارد
دقیقا به اندازه یک جدول هش،

144
00:06:22,607 --> 00:06:24,440
اما احتمالا امن
به طور کلی

145
00:06:24,440 --> 00:06:27,990
رفتن به بزرگتر از یک مرتبط
لیست ذخیره سازی داده های مشابه،

146
00:06:27,990 --> 00:06:30,400
اما کوچکتر از یک درخت پیشوندی.

147
00:06:30,400 --> 00:06:32,720
>> و تلاش می کند که چهارمین هستند
از این سازه ها

148
00:06:32,720 --> 00:06:34,070
که ما شده ایم صحبت کردن در مورد.

149
00:06:34,070 --> 00:06:36,450
قرار دادن به یک درخت پیچیده است.

150
00:06:36,450 --> 00:06:38,400
در بسیاری از پویا وجود دارد
تخصیص حافظه،

151
00:06:38,400 --> 00:06:40,780
به خصوص در آغاز،
عنوان شما شروع به ساخت.

152
00:06:40,780 --> 00:06:43,700
اما زمان ثابت آن است.

153
00:06:43,700 --> 00:06:47,690
این تنها عنصر انسانی است
در اینجا است که باعث می شود آن روی حیله و تزویر.

154
00:06:47,690 --> 00:06:53,250
نیاز به برخورد اشاره گر تهی، از malloc
فضا، رفتن وجود دارد، فضای احتمالا از malloc

155
00:06:53,250 --> 00:06:54,490
از آنجا دوباره.

156
00:06:54,490 --> 00:06:58,880
مرتب کردن بر اساس عامل ارعاب
اشاره گرها در تخصیص حافظه پویا

157
00:06:58,880 --> 00:07:00,130
مانع برای روشن است.

158
00:07:00,130 --> 00:07:04,550
اما هنگامی که شما آن را پاک کرده اید، درج
در واقع می آید کاملا ساده است،

159
00:07:04,550 --> 00:07:06,810
و قطعا آن زمان ثابت است.

160
00:07:06,810 --> 00:07:07,680
>> حذف آسان است.

161
00:07:07,680 --> 00:07:11,330
همه شما باید انجام دهید این است که حرکت یک
زن و شوهر از اشاره گرها و رایگان گره،

162
00:07:11,330 --> 00:07:12,420
به طوری که خیلی خوب است.

163
00:07:12,420 --> 00:07:13,930
گرین کارت آمریکا نیز بسیار سریع می باشد.

164
00:07:13,930 --> 00:07:16,780
آن را تنها در بر
طول داده خود را.

165
00:07:16,780 --> 00:07:19,924
بنابراین اگر تمام اطلاعات خود را است
پنج رشته های کاراکتری،

166
00:07:19,924 --> 00:07:22,590
برای مثال، شما در حال ذخیره سازی پنج
رشته های کاراکتری در درخت خود را،

167
00:07:22,590 --> 00:07:25,439
تنها پنج گام برای رسیدن به طول می کشد
پیدا کردن آنچه شما دنبال آن هستید.

168
00:07:25,439 --> 00:07:28,480
پنج فقط یک ضریب ثابت است، بنابراین
دوباره، درج، حذف، و مراجعه به

169
00:07:28,480 --> 00:07:31,670
در اینجا همه زمان ثابت، به طور موثر.

170
00:07:31,670 --> 00:07:34,880
>> یکی دیگر از چیزی است که درخت خود را است
در واقع نوع طبقه بندی شده اند در حال حاضر، درست است؟

171
00:07:34,880 --> 00:07:36,800
به موجب چگونه ما
عناصر قرار دادن،

172
00:07:36,800 --> 00:07:40,060
با رفتن حروف از
کلیدی، و یا اعداد رقمی از کلید،

173
00:07:40,060 --> 00:07:45,084
به طور معمول، درخت خود را پایان می رسد تا
نوع طبقه بندی شده اند که شما آن را ساخت.

174
00:07:45,084 --> 00:07:47,250
آن را واقعا نمی سازد
حس به فکر می کنم در مورد مرتب سازی

175
00:07:47,250 --> 00:07:49,874
در همان راه ما در مورد فکر می کنم
آن را با آرایه ها، و یا لیست های پیوندی،

176
00:07:49,874 --> 00:07:51,070
و یا جداول هش.

177
00:07:51,070 --> 00:07:54,780
اما در بعضی جهات، خود را
درخت طبقه بندی شده اند که شما بروید.

178
00:07:54,780 --> 00:07:58,630
>> در حرکت نزولی، البته، این است که
یک درخت پیشوندی به سرعت در حال بزرگ می شود.

179
00:07:58,630 --> 00:08:02,970
از هر نقطه اتصال، شما ممکن است
have-- اگر کلید خود را متشکل از رقم،

180
00:08:02,970 --> 00:08:04,880
شما باید 10 دیگر
مکان شما می توانید بروید که

181
00:08:04,880 --> 00:08:07,490
بدان معنی است که هر گره
حاوی اطلاعات

182
00:08:07,490 --> 00:08:11,440
در مورد داده های شما می خواهید برای ذخیره
که در آن گره، به علاوه 10 اشاره گر.

183
00:08:11,440 --> 00:08:14,430
که، در CS50 IDE، 80 بایت است.

184
00:08:14,430 --> 00:08:17,220
پس از آن حداقل 80 بایت برای
هر گره که شما ایجاد می کنید،

185
00:08:17,220 --> 00:08:19,240
و حتی شمارش داده نمی شود.

186
00:08:19,240 --> 00:08:24,950
و اگر گره خود را
حروف به جای رقم،

187
00:08:24,950 --> 00:08:27,825
در حال حاضر شما باید 26 اشاره گر
از هر محل.

188
00:08:27,825 --> 00:08:32,007
و 26 بار 8 است که احتمالا 200
بایت، یا چیزی شبیه به آن.

189
00:08:32,007 --> 00:08:33,840
و شما باید سرمایه
شما می توانید lowercase-- و

190
00:08:33,840 --> 00:08:35,381
ببینید که در آن من قصد دارم با این، درست است؟

191
00:08:35,381 --> 00:08:37,500
گره خود را می توانید واقعا
بزرگ، و این درخت به

192
00:08:37,500 --> 00:08:40,470
به خودی خود، به طور کلی، می توانید
واقعا بزرگی است.

193
00:08:40,470 --> 00:08:42,630
بنابراین اگر فضا به بالا
حق بیمه بر روی سیستم شما،

194
00:08:42,630 --> 00:08:45,830
یک درخت پیشوندی ممکن است راه درست را به نیست
، حتی اگر مزایای دیگر آن

195
00:08:45,830 --> 00:08:47,780
به بازی آمد.

196
00:08:47,780 --> 00:08:48,710
من داگ لوید هستم.

197
00:08:48,710 --> 00:08:50,740
این CS50 است.

198
00:08:50,740 --> 00:08:52,316