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

2
00:00:05,259 --> 00:00:08,300
DOUG لويد: حتى في 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
وبحث من TRIE إذا كنت حقا
لا يهمني حول إدراج وحذف

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 أو 1000

123
00:05:18,390 --> 00:05:25,380
أو ن العناصر في جدول التجزئة الخاصة بك، وكنت
القوائم المرتبطة كلها واحدة نطة الحجم.

124
00:05:25,380 --> 00:05:27,650
انهم جميعا أصغر بكثير.

125
00:05:27,650 --> 00:05:32,080
لقد ن القوائم المرتبطة بدلا
واحدة قائمة مرتبطة حجم ن.

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
ولكن أصغر من TRIE.

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
إدراج في TRIE معقد.

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
على سبيل المثال، كنت تخزين خمسة
سلاسل الأحرف في TRIE الخاص بك،

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
>> شيء آخر هو أن TRIE الخاص بك هو
في الواقع فرز النوع من قبل، أليس كذلك؟

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
عادة، TRIE ينتهي به الأمر
نوع من مرتبة كما كنت بناء عليه.

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
ولكن في بعض المعنى، بك
يتم فرز TRIE كما تذهب.

178
00:07:54,780 --> 00:07:58,630
>> الجانب السلبي، بطبيعة الحال، هو أن
وTRIE يصبح بسرعة هائلة.

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
التي، على IDE CS50، هو 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
يمكن أن العقد الخاص بك الحصول على حقا
كبير، وبالتالي فإن TRIE

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
وTRIE قد لا تكون الطريقة الصحيحة ل
الذهاب، على الرغم من الفوائد الأخرى ل

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