1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> سرور 1: كل الحق، لذلك نحن الى الوراء.

3
00:00:13,120 --> 00:00:14,480
مرحبا بكم في CS50.

4
00:00:14,480 --> 00:00:16,510
هذا هو نهاية الأسبوع السبعة.

5
00:00:16,510 --> 00:00:20,200
لذلك أذكر أن المرة الأخيرة، بدأنا
أبحث في قليلا أكثر تعقيدا

6
00:00:20,200 --> 00:00:21,100
هياكل البيانات.

7
00:00:21,100 --> 00:00:25,110
منذ حتى الآن، وكان كل ما حقا
في حوزتنا كان هذا، صفيف.

8
00:00:25,110 --> 00:00:29,340
>> ولكن قبل أن يتخلص من مجموعة لا
كل ذلك للاهتمام، والتي كانت في الواقع

9
00:00:29,340 --> 00:00:33,570
هو في الواقع، ما هي بعض من
الإيجابيات من هذه البيانات بسيطة

10
00:00:33,570 --> 00:00:34,560
هيكل حتى الآن؟

11
00:00:34,560 --> 00:00:36,110
ما هو جيد في؟

12
00:00:36,110 --> 00:00:39,450
حتى الآن كما رأينا؟

13
00:00:39,450 --> 00:00:42,540
ماذا حصل؟

14
00:00:42,540 --> 00:00:44,028
لا شيء.

15
00:00:44,028 --> 00:00:45,020
>> الطالب: [غير مسموع].

16
00:00:45,020 --> 00:00:45,395
>> سرور 1: ما هذا؟

17
00:00:45,395 --> 00:00:46,410
>> الطالب: [غير مسموع].

18
00:00:46,410 --> 00:00:47,000
>> سرور 1: حجم ثابت.

19
00:00:47,000 --> 00:00:51,260
حسنا، لماذا هو حجم ثابت جيد على الرغم من؟

20
00:00:51,260 --> 00:00:53,180
>> الطالب: [غير مسموع].

21
00:00:53,180 --> 00:00:56,240
>> سرور 1: موافق، لذلك فمن فعالة في
بمعنى أنه يمكنك تخصيص

22
00:00:56,240 --> 00:01:00,070
كمية محددة من الفضاء، والتي من المؤمل
هو بالضبط بقدر

23
00:01:00,070 --> 00:01:01,180
الفضاء على النحو الذي تريد.

24
00:01:01,180 --> 00:01:02,720
بحيث يمكن أن تكون مطلقة زائد.

25
00:01:02,720 --> 00:01:06,530
>> ما هو الجانب حتى آخر لصفيف؟

26
00:01:06,530 --> 00:01:07,610
نعم؟

27
00:01:07,610 --> 00:01:08,750
>> الطالب: [غير مسموع].

28
00:01:08,750 --> 00:01:09,550
>> سرور 1: جميع - آسف؟

29
00:01:09,550 --> 00:01:11,270
>> الطالب: [غير مسموع].

30
00:01:11,270 --> 00:01:13,620
>> سرور 1: جميع صناديق في الذاكرة
أو بجانب بعضها البعض.

31
00:01:13,620 --> 00:01:15,220
وهذا مفيد - لماذا؟

32
00:01:15,220 --> 00:01:15,970
هذا صحيح تماما.

33
00:01:15,970 --> 00:01:18,611
ولكن كيف يمكننا استغلال تلك الحقيقة؟

34
00:01:18,611 --> 00:01:21,500
>> الطالب: [غير مسموع].

35
00:01:21,500 --> 00:01:24,490
>> سرور 1: بالضبط، ونحن يمكن أن تتبع
حيث كل شيء فقط من خلال معرفة

36
00:01:24,490 --> 00:01:28,560
عنوان واحد، وهما عنوان
البايت الأول من أن جزءا من الذاكرة.

37
00:01:28,560 --> 00:01:30,420
أو في حالة من السلسلة،
عنوان أول

38
00:01:30,420 --> 00:01:31,460
شار في هذه السلسلة.

39
00:01:31,460 --> 00:01:33,330
ومن هناك، يمكن أن نجد
نهاية السلسلة.

40
00:01:33,330 --> 00:01:35,710
يمكننا العثور على العنصر الثاني، و
العنصر الثالث، وهكذا دواليك.

41
00:01:35,710 --> 00:01:38,740
>> وبالتالي فإن الطريقة يتوهم من أن تصف
ميزة هي أن تعطينا صفائف

42
00:01:38,740 --> 00:01:40,020
الوصول العشوائي.

43
00:01:40,020 --> 00:01:44,330
فقط باستخدام قوس مربع
التدوين وعدد، ويمكن أن تقفز إلى

44
00:01:44,330 --> 00:01:48,070
عنصر معين في مجموعة
في وقت ثابت يا كبير

45
00:01:48,070 --> 00:01:49,810
من واحد، إذا جاز التعبير.

46
00:01:49,810 --> 00:01:51,080
>> ولكن هناك بعض الجوانب السلبية ما كان.

47
00:01:51,080 --> 00:01:53,110
ما مجموعة لا تفعل بسهولة جدا؟

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
ما يدور يست جيدة في؟

50
00:01:57,170 --> 00:01:58,810
>> الطالب: [غير مسموع].

51
00:01:58,810 --> 00:01:59,860
>> سرور 1: ما هذا؟

52
00:01:59,860 --> 00:02:00,530
>> الطالب: [غير مسموع].

53
00:02:00,530 --> 00:02:01,460
>> سرور 1: التوسع في الحجم.

54
00:02:01,460 --> 00:02:04,800
وبالتالي فإن سلبيات مجموعة هي
بالضبط عكس ما

55
00:02:04,800 --> 00:02:05,540
الإيجابيات هي.

56
00:02:05,540 --> 00:02:07,610
حتى واحد من سلبيات هو
أنه من حجم ثابت.

57
00:02:07,610 --> 00:02:09,400
لذلك لا يمكن أن تنمو حقا.

58
00:02:09,400 --> 00:02:13,510
يمكنك تخصيص جزءا أكبر من
الذاكرة، ثم نقل العناصر القديمة

59
00:02:13,510 --> 00:02:14,460
في مجموعة جديدة.

60
00:02:14,460 --> 00:02:18,060
ثم تحرير مجموعة من العمر، ل
المثال، باستخدام malloc أو مماثلة

61
00:02:18,060 --> 00:02:21,180
وظيفة تسمى realloc، التي
إعادة تخصيص الذاكرة.

62
00:02:21,180 --> 00:02:25,490
>> Realloc، بوصفها جانبا، يحاول أن أعطيك
الذاكرة التي هي الخطوة التالية لمجموعة

63
00:02:25,490 --> 00:02:26,610
أن لديك بالفعل.

64
00:02:26,610 --> 00:02:28,740
لكنها يمكن أن تتحرك الأمور
حول تماما.

65
00:02:28,740 --> 00:02:30,710
ولكن باختصار، وهذا مكلف، أليس كذلك؟

66
00:02:30,710 --> 00:02:33,440
لأنه إذا كان لديك قطعة من الذاكرة
هذا الحجم، ولكن كنت تريد حقا واحدة

67
00:02:33,440 --> 00:02:36,710
من هذا الحجم، وكنت ترغب في الحفاظ على
العناصر الأصلية، لديك

68
00:02:36,710 --> 00:02:40,510
ما يقرب من عملية النسخ الزمن الخطي
التي يجب أن يحدث من

69
00:02:40,510 --> 00:02:41,900
مجموعة القديم إلى الجديد.

70
00:02:41,900 --> 00:02:44,630
والواقع يسأل التشغيل
النظام مرة أخرى ومرة ​​أخرى و

71
00:02:44,630 --> 00:02:48,340
مرة أخرى لمساحات كبيرة من الذاكرة يمكن أن يبدأ
يكلفك بعض الوقت أيضا.

72
00:02:48,340 --> 00:02:52,250
لذلك فمن بمثابة نعمة ونقمة في
تمويه، حقيقة أن هذه المصفوفات

73
00:02:52,250 --> 00:02:53,860
هي من حجم ثابت.

74
00:02:53,860 --> 00:02:56,790
ولكن إذا نحن نقدم بدلا من ذلك شيئا
مثل هذا، وهو ما يسمى مرتبطة

75
00:02:56,790 --> 00:03:00,580
قائمة، وحصلنا على عدد قليل من الإيجابيات و
عدد قليل من سلبيات هنا كذلك.

76
00:03:00,580 --> 00:03:05,780
>> حتى قائمة مرتبطة هو مجرد البيانات
هيكل يتكون من البنيات C في هذا

77
00:03:05,780 --> 00:03:09,850
الحالة، حيث البنية، أذكر، هو مجرد
وعاء لواحد محدد أو أكثر

78
00:03:09,850 --> 00:03:11,100
أنواع المتغيرات.

79
00:03:11,100 --> 00:03:16,110
في هذه الحالة، ما يفعله أنواع البيانات
يبدو أن داخل البنية التي

80
00:03:16,110 --> 00:03:17,600
آخر مرة كنا نسميها عقدة؟

81
00:03:17,600 --> 00:03:19,380
كل من هذه المستطيلات هو العقدة.

82
00:03:19,380 --> 00:03:22,660
ولكل من المستطيلات الصغيرة
داخل منه هو نوع البيانات.

83
00:03:22,660 --> 00:03:25,300
ما هي أنواع لم نقول
كانوا يوم الاثنين؟

84
00:03:25,300 --> 00:03:26,478
نعم؟

85
00:03:26,478 --> 00:03:27,870
>> الطالب: [غير مسموع].

86
00:03:27,870 --> 00:03:30,721
>> سرور 1: متغير ومؤشر، أو
وبشكل أكثر تحديدا، وكثافة العمليات، لن،

87
00:03:30,721 --> 00:03:32,180
والمؤشر في القاع.

88
00:03:32,180 --> 00:03:35,360
كل من هذه يحدث ليكون 32 بت، في
الأقل على جهاز كمبيوتر مثل هذا CS50

89
00:03:35,360 --> 00:03:37,980
الأجهزة، وحتى انهم
رسمها على قدم المساواة في الحجم.

90
00:03:37,980 --> 00:03:42,260
>> وذلك ما تستخدم المؤشر
رغم ما يبدو ل؟

91
00:03:42,260 --> 00:03:47,690
لماذا هذا السهم إضافة الآن عندما كانت صفائف
لطيفة جدا ونظيفة وبسيطة؟

92
00:03:47,690 --> 00:03:50,460
ما هو مؤشر تفعل ل
لنا في كل من هذه العقد؟

93
00:03:50,460 --> 00:03:52,160
>> الطالب: [غير مسموع].

94
00:03:52,160 --> 00:03:52,465
>> سرور 1: بالضبط.

95
00:03:52,465 --> 00:03:54,120
انها تقول لك أين
واحد القادم هو.

96
00:03:54,120 --> 00:03:57,350
لذلك أنا نوع من استخدام تشبيه
باستخدام خيط لفرز من

97
00:03:57,350 --> 00:03:59,180
خيط هذه العقد معا.

98
00:03:59,180 --> 00:04:01,760
وهذا هو بالضبط ما نفعله مع
مؤشرات لأن كل من هذه

99
00:04:01,760 --> 00:04:06,360
قطع من الذاكرة قد تكون أو لا تكون
متجاورة، والعودة إلى العودة إلى الوراء

100
00:04:06,360 --> 00:04:09,500
داخل من ذاكرة الوصول العشوائي، وذلك لأن في كل مرة كنت
استدعاء malloc القول، أعطني ما يكفي

101
00:04:09,500 --> 00:04:12,510
بايت لعقدة جديدة، فإنه قد
يكون هنا أو أنه قد يكون هنا.

102
00:04:12,510 --> 00:04:13,120
قد يكون هنا.

103
00:04:13,120 --> 00:04:13,730
قد يكون هنا.

104
00:04:13,730 --> 00:04:14,640
كنت لا أعرف.

105
00:04:14,640 --> 00:04:17,880
>> ولكن باستخدام المؤشرات في عناوين
تلك العقد، يمكنك غرزة لهم

106
00:04:17,880 --> 00:04:22,370
معا في الطريقة التي تبدو بصريا
مثل قائمة حتى لو كانت هذه الأمور

107
00:04:22,370 --> 00:04:26,770
تنتشر في جميع أنحاء خروج واحد أو الخاص
لديك اثنين أو أربعة غيغابايت الخاص من ذاكرة الوصول العشوائي

108
00:04:26,770 --> 00:04:28,760
داخل جهاز الكمبيوتر الخاص بك.

109
00:04:28,760 --> 00:04:33,230
>> وبالتالي فإن الجانب السلبي، بعد ذلك،
قائمة مرتبطة ما هو؟

110
00:04:33,230 --> 00:04:34,670
ما هو سعر نحن
دفع على ما يبدو؟

111
00:04:34,670 --> 00:04:36,010
>> الطالب: [غير مسموع].

112
00:04:36,010 --> 00:04:36,920
>> سرور 1: مزيد من الفضاء، أليس كذلك؟

113
00:04:36,920 --> 00:04:39,340
قمنا، في هذه الحالة، تضاعف المبلغ
الفضاء لأننا قد ذهبت

114
00:04:39,340 --> 00:04:43,500
من 32 بت لكل عقدة لكل
الباحث، وحتى الآن 64 بت لأن لدينا ل

115
00:04:43,500 --> 00:04:45,050
إبقاء حول مؤشر كذلك.

116
00:04:45,050 --> 00:04:48,860
تحصل على أكثر كفاءة إذا البنية الخاصة بك
هو أكبر من هذا الشيء البسيط.

117
00:04:48,860 --> 00:04:52,020
إذا كان لديك فعلا الطالب داخل
الذي هو بضعة سلاسل لل

118
00:04:52,020 --> 00:04:55,430
اسم والمنزل، وربما رقم معرف،
ربما بعض المجالات الأخرى تماما.

119
00:04:55,430 --> 00:04:59,000
>> حتى إذا كان لديك بنية كبيرة بما فيه الكفاية،
ثم ربما تكلفة المؤشر

120
00:04:59,000 --> 00:05:00,010
لا مثل هذه الصفقة الكبيرة.

121
00:05:00,010 --> 00:05:03,570
هذا هو جزء من قضية الزاوية في ذلك
نحن تخزين مثل هذه بسيطة بدائية

122
00:05:03,570 --> 00:05:04,760
داخل القائمة المرتبطة.

123
00:05:04,760 --> 00:05:05,790
ولكن النقطة هو نفسه.

124
00:05:05,790 --> 00:05:08,230
كنت بالتأكيد انفاق المزيد
الذاكرة، ولكن كنت الحصول على

125
00:05:08,230 --> 00:05:08,990
المرونة.

126
00:05:08,990 --> 00:05:12,280
لأنه الآن إذا كنت تريد أن تضيف عنصرا
في بداية هذه القائمة،

127
00:05:12,280 --> 00:05:14,340
لدي تخصيص عقدة جديدة.

128
00:05:14,340 --> 00:05:17,180
ولدي لمجرد تحديث تلك
السهام بطريقة أو بأخرى من قبل تتحرك فقط

129
00:05:17,180 --> 00:05:17,980
بعض المؤشرات حولها.

130
00:05:17,980 --> 00:05:20,580
>> إذا كنت ترغب في إدراج شيء في
منتصف القائمة، وأنا لم يكن لديك ل

131
00:05:20,580 --> 00:05:24,410
دفع الجميع جانبا كما فعلنا في
الماضي أسابيع مع المتطوعين الذين لدينا

132
00:05:24,410 --> 00:05:25,700
ممثلة صفيف.

133
00:05:25,700 --> 00:05:29,470
يمكنني فقط تخصيص عقدة جديدة و
ثم مجرد نقطة في الأسهم

134
00:05:29,470 --> 00:05:32,290
اتجاهات مختلفة لأنه لا
يجب أن تبقى في الفعلية

135
00:05:32,290 --> 00:05:35,670
الذاكرة خط صحيح وكأنني قد رسمها
هنا على الشاشة.

136
00:05:35,670 --> 00:05:38,400
>> ثم أخيرا، إذا كنت ترغب في إدراج
شيء في نهاية القائمة، انها

137
00:05:38,400 --> 00:05:39,210
حتى أسهل.

138
00:05:39,210 --> 00:05:43,320
هذا هو نوع من التدوين التعسفي،
ولكن المؤشر 34، واتخاذ تخمين.

139
00:05:43,320 --> 00:05:46,710
ما هي قيمة المؤشر الأكثر
من المرجح رسمها نوع من مثل قديمة

140
00:05:46,710 --> 00:05:47,700
هوائي المدرسة هناك؟

141
00:05:47,700 --> 00:05:48,920
>> الطالب: [غير مسموع].

142
00:05:48,920 --> 00:05:49,900
>> سرور 1: انها ربما فارغة.

143
00:05:49,900 --> 00:05:52,710
والواقع أن واحدة البلاغ
تمثيل فارغة.

144
00:05:52,710 --> 00:05:56,310
وانها لاغية لأن كنت على الاطلاق
تحتاج أن تعرف أين نهاية مرتبط

145
00:05:56,310 --> 00:06:00,050
القائمة، لئلا تبقي التالية و
التالية والتالية هذه السهام

146
00:06:00,050 --> 00:06:01,170
لبعض القيمة القمامة.

147
00:06:01,170 --> 00:06:06,230
فارغة لذلك سوف يعني أنه لا يوجد
أكثر من العقد إلى يمين الرقم 34،

148
00:06:06,230 --> 00:06:07,200
في هذه الحالة.

149
00:06:07,200 --> 00:06:10,270
>> ولذا فإننا نقترح أن نتمكن من تنفيذ
هذه العقدة في التعليمات البرمجية.

150
00:06:10,270 --> 00:06:12,130
وشاهدنا هذا النوع
من جملة قبل.

151
00:06:12,130 --> 00:06:15,090
typedef ويحدد فقط نوع جديد ل
لنا، يعطينا مثل مرادف

152
00:06:15,090 --> 00:06:17,100
كان لسلسلة شار *.

153
00:06:17,100 --> 00:06:21,030
في هذه الحالة، انها سوف تعطينا
منهج الاختزال بحيث عقدة البنية

154
00:06:21,030 --> 00:06:24,010
يمكن بدلا من مجرد أن يكتب
عقدة، والذي هو الكثير أنظف.

155
00:06:24,010 --> 00:06:25,360
انها أقل كثيرا مطول.

156
00:06:25,360 --> 00:06:30,080
>> داخل عقدة على ما يبدو على كثافة العمليات
دعا ن، ومن ثم عقدة البنية *

157
00:06:30,080 --> 00:06:34,670
وهو ما يعني بالضبط ما كنا نريد
الأسهم ليعني، مؤشر إلى أخرى

158
00:06:34,670 --> 00:06:36,940
عقدة من نفس نوع البيانات المحدد.

159
00:06:36,940 --> 00:06:40,300
وأقترح أن نتمكن من تنفيذ
البحث ظيفة من هذا القبيل، والتي في

160
00:06:40,300 --> 00:06:41,890
قد يبدو أول وهلة
قليلا معقدة.

161
00:06:41,890 --> 00:06:43,330
ولكن دعونا نرى ذلك في السياق.

162
00:06:43,330 --> 00:06:45,480
>> اسمحوا لي أن يذهب أكثر إلى الأجهزة هنا.

163
00:06:45,480 --> 00:06:48,460
اسمحوا لي أن فتح ملف يسمى
قائمة الصفر نقطة ح.

164
00:06:48,460 --> 00:06:53,950
والذي يحتوي فقط على أننا تعريف
فقط رأيت قبل لحظة لهذه البيانات

165
00:06:53,950 --> 00:06:55,390
نوع يسمى عقدة.

166
00:06:55,390 --> 00:06:57,350
ولذا فإننا قد وضعت ذلك في ملف نقطة ح.

167
00:06:57,350 --> 00:07:01,430
>> وبوصفها جانبا، حتى وإن كان هذا
البرنامج الذي كنت على وشك أن ترى

168
00:07:01,430 --> 00:07:05,410
ليس كل ما معقدة، انها حقا
الاتفاقية عند كتابة برنامج ل

169
00:07:05,410 --> 00:07:10,270
وضع أشياء مثل أنواع البيانات، لسحب
الثوابت في بعض الأحيان، داخل الخاص

170
00:07:10,270 --> 00:07:13,210
ملف الرأس وليس بالضرورة في
ملف C الخاص بك، بالتأكيد عندما الخاص بك

171
00:07:13,210 --> 00:07:17,370
برامج الحصول على أكبر وأكبر، بحيث
كنت تعرف أن ننظر فيها على حد سواء ل

172
00:07:17,370 --> 00:07:20,840
الوثائق في بعض الحالات، أو
لأساسيات مثل هذا،

173
00:07:20,840 --> 00:07:22,360
تعريف من نوع ما.

174
00:07:22,360 --> 00:07:25,680
>> إذا أنا الآن فتح قائمة صفر نقطة
ج، لاحظ عدد قليل من الأشياء.

175
00:07:25,680 --> 00:07:29,090
وهو يشتمل على بعض الملفات رأس، ومعظم
من الذي رأيناه من قبل.

176
00:07:29,090 --> 00:07:31,980
ويشمل ملف الرأس الخاص به.

177
00:07:31,980 --> 00:07:35,200
>> وبوصفها جانبا، لماذا هذا مزدوج
ونقلت هنا، بدلا من الزاوية

178
00:07:35,200 --> 00:07:38,340
أقواس على السطر الذي
لقد أبرزت هناك؟

179
00:07:38,340 --> 00:07:39,180
>> الطالب: [غير مسموع].

180
00:07:39,180 --> 00:07:40,460
>> سرور 1: نعم لذلك هو ملف محلي.

181
00:07:40,460 --> 00:07:44,300
حتى لو كان ملف محلي خاص بك هنا
على الخط 15، على سبيل المثال، يمكنك استخدام

182
00:07:44,300 --> 00:07:46,570
علامة التنصيص بدلا
الأقواس الزاوية.

183
00:07:46,570 --> 00:07:48,270
>> الآن هذا هو نوع من اهتمام.

184
00:07:48,270 --> 00:07:51,830
لاحظوا أنني أعلن العالمية
متغير في هذا البرنامج على خط 18

185
00:07:51,830 --> 00:07:55,910
دعا الأولى، والفكرة هي هذا هو
سيكون المؤشر إلى أول

186
00:07:55,910 --> 00:07:59,190
عقدة في قائمتي مرتبطة، ولقد
تهيئة لاغية، لأن لدي

187
00:07:59,190 --> 00:08:02,310
لم تخصص أي الفعلية
العقد فقط حتى الآن.

188
00:08:02,310 --> 00:08:07,570
>> ولذلك فإن هذا يمثل، بالصور، ما كنا
رأى قبل لحظة في الصورة كما

189
00:08:07,570 --> 00:08:10,090
هذا المؤشر على أقصى
الجانب الأيسر.

190
00:08:10,090 --> 00:08:12,260
الآن الحق في ذلك، وهذا مؤشر
لايوجد سهم.

191
00:08:12,260 --> 00:08:14,590
بدلا من ذلك هو مجرد فارغة.

192
00:08:14,590 --> 00:08:17,880
ولكن لأنها تمثل ما سيكون عليه
عنوان أول الفعلي

193
00:08:17,880 --> 00:08:19,480
العقدة في هذه القائمة.

194
00:08:19,480 --> 00:08:22,120
حتى لقد تنفيذه هو عالمي
، لأنه كما سترى، كل هذا

195
00:08:22,120 --> 00:08:25,310
البرنامج لا في الحياة هو تنفيذ
قائمة مرتبطة بالنسبة لي.

196
00:08:25,310 --> 00:08:27,050
>> الآن لقد حصلت على عدد قليل من النماذج هنا.

197
00:08:27,050 --> 00:08:31,190
قررت لتنفيذ ميزات مثل
الحذف، أو الإدراج، والبحث، و

198
00:08:31,190 --> 00:08:31,740
اجتياز -

199
00:08:31,740 --> 00:08:35,210
لمجرد كونها مشاركة مشيا على الأقدام عبر
القائمة، طبع عناصرها.

200
00:08:35,210 --> 00:08:36,750
والآن وهنا بلدي الروتينية الرئيسية.

201
00:08:36,750 --> 00:08:39,890
ونحن لن تنفق الكثير من الوقت على
هذه لأن هذا هو نوع من، ونأمل

202
00:08:39,890 --> 00:08:41,780
قبعة قديمة الآن.

203
00:08:41,780 --> 00:08:45,370
>> انا ذاهب الى القيام بما يلي،
بينما تتعاون المستخدم.

204
00:08:45,370 --> 00:08:47,300
حتى واحد، وانا ذاهب لطباعة
من هذه القائمة.

205
00:08:47,300 --> 00:08:49,420
ولقد تنسيقه كما
نظيفة ما أستطيع.

206
00:08:49,420 --> 00:08:52,240
إذا قام المستخدم بكتابة في واحدة، وهذا يعني
انهم يريدون حذف شيء.

207
00:08:52,240 --> 00:08:54,560
إذا أنواع المستخدم في اثنين، وهذا يعني
انهم يريدون ادخال شيء.

208
00:08:54,560 --> 00:08:55,930
وهكذا دواليك.

209
00:08:55,930 --> 00:08:58,270
انا ذاهب للمطالبة ثم
ثم لأمر.

210
00:08:58,270 --> 00:08:59,300
ثم انا ذاهب الى استخدام GetInt.

211
00:08:59,300 --> 00:09:02,790
>> لذلك هذا هو حقا بسيطة menuing
واجهة حيث لديك فقط لكتابة

212
00:09:02,790 --> 00:09:05,270
تعيين العدد إلى واحد
تلك الأوامر.

213
00:09:05,270 --> 00:09:08,730
والآن لدي التبديل نظيفة جميلة
بيان ان يحدث للتبديل على

214
00:09:08,730 --> 00:09:10,090
كل ما كتبته المستخدم فيها.

215
00:09:10,090 --> 00:09:12,180
وإذا كانت كتابتها واحد، وسوف أكون
استدعاء حذف وكسر.

216
00:09:12,180 --> 00:09:14,380
إذا كانت كتبته اثنين، وسوف أكون
استدعاء إدراج وكسر.

217
00:09:14,380 --> 00:09:16,490
>> والآن لاحظ لقد وضعت كل
هذه على نفس الخط.

218
00:09:16,490 --> 00:09:18,360
هذا هو مجرد قرار الأسلوبية.

219
00:09:18,360 --> 00:09:20,210
عادة ما رأيناه شيء
مثل هذا.

220
00:09:20,210 --> 00:09:23,260
لكنني قررت فقط، وبصراحة، برنامجي
بدا أكثر قابلية للقراءة ل

221
00:09:23,260 --> 00:09:25,980
كان أربعة حالات فقط ل
مجرد سرد مثل هذا.

222
00:09:25,980 --> 00:09:28,360
الاستخدام المشروع تماما من النمط.

223
00:09:28,360 --> 00:09:31,480
وانا ذاهب الى القيام بذلك ما دامت ل
وقد المستخدم لا كتبته الصفر، وهو ما

224
00:09:31,480 --> 00:09:33,910
قررت سيعني أنهم يريدون الإقلاع عن التدخين.

225
00:09:33,910 --> 00:09:36,630
>> وحتى الآن لاحظت ما أنا
تنوي القيام به هنا.

226
00:09:36,630 --> 00:09:38,650
أنا ذاهب لتحرير قائمة على ما يبدو.

227
00:09:38,650 --> 00:09:40,230
ولكن أكثر على ذلك في مجرد لحظة.

228
00:09:40,230 --> 00:09:41,640
دعونا أولا تشغيل هذا البرنامج.

229
00:09:41,640 --> 00:09:45,250
لذلك اسمحوا لي أن أكبر محطة
النافذة، القائمة دوت مائل 0.

230
00:09:45,250 --> 00:09:49,510
انا ذاهب الى المضي قدما وإدراج من قبل
كتابة اثنين، وعدد مثل 50، والآن

231
00:09:49,510 --> 00:09:51,590
سترى قائمة الآن 50.

232
00:09:51,590 --> 00:09:53,380
والنص الذي قدمته تمريره فقط قليلا.

233
00:09:53,380 --> 00:09:55,940
وحتى الآن لاحظت يحتوي على قائمة
عدد 50.

234
00:09:55,940 --> 00:09:58,220
>> دعونا نفعل إدراج أخرى عن طريق اتخاذ اثنين.

235
00:09:58,220 --> 00:10:01,630
دعونا اكتب في عدد مثل واحد.

236
00:10:01,630 --> 00:10:03,940
قائمة الآن واحدة، تليها 50.

237
00:10:03,940 --> 00:10:06,020
لذلك هذا هو تمثيل النصية فقط
من القائمة.

238
00:10:06,020 --> 00:10:10,550
ودعونا إدراج رقم واحد أشبه
عدد 42، والذي هو أمل

239
00:10:10,550 --> 00:10:14,620
الذهاب الى نهاية المطاف في الوسط، ل
هذا البرنامج في أنواع معينة فإنه

240
00:10:14,620 --> 00:10:16,320
العناصر كما يدرج لهم.

241
00:10:16,320 --> 00:10:17,220
حتى لا يكون هناك لدينا ذلك.

242
00:10:17,220 --> 00:10:20,730
برنامج سوبر البسيطة التي يمكن
وقد استخدمت مجموعة على الاطلاق، لكنني

243
00:10:20,730 --> 00:10:23,280
يحدث ليكون باستخدام قائمة مرتبطة
فقط حتى يمكنني حيوي

244
00:10:23,280 --> 00:10:24,610
النمو وتقليص حجمها.

245
00:10:24,610 --> 00:10:28,470
>> لذلك دعونا نلقي نظرة على البحث، وإذا كنت
تشغيل الأوامر الثلاثة، أريد أن بحث

246
00:10:28,470 --> 00:10:31,040
ل، مثلا، عدد 43.

247
00:10:31,040 --> 00:10:34,190
وعلى ما يبدو وجد شيئا،
لأنني حصلت على العودة أي رد.

248
00:10:34,190 --> 00:10:35,010
لذلك دعونا نفعل ذلك مرة أخرى.

249
00:10:35,010 --> 00:10:35,690
البحث.

250
00:10:35,690 --> 00:10:39,520
دعونا بحث عن 50، أو بالأحرى بحث
ل42، التي لديها لطيفة

251
00:10:39,520 --> 00:10:40,850
معنى خفية قليلا.

252
00:10:40,850 --> 00:10:42,610
ولقد وجدت معنى الحياة هناك.

253
00:10:42,610 --> 00:10:44,990
عدد 42، إذا كنت لا تعرف
المرجع، وجوجل عليه.

254
00:10:44,990 --> 00:10:45,350
حسنا.

255
00:10:45,350 --> 00:10:47,130
لذلك ما قام به هذا البرنامج بالنسبة لي؟

256
00:10:47,130 --> 00:10:50,660
لقد سمح لي فقط لانه لإدراج بالتالي
الآن، والبحث عن العناصر.

257
00:10:50,660 --> 00:10:53,650
>> دعونا سريع إلى الأمام، ثم، ل
أن وظيفة ونحن يحملق في

258
00:10:53,650 --> 00:10:55,360
يوم الاثنين مع دعابة.

259
00:10:55,360 --> 00:10:59,620
حتى هذه الوظيفة، أزعم، يبحث ل
عنصر في القائمة التي كتبها الأولى

260
00:10:59,620 --> 00:11:03,830
واحد، مطالبة المستخدم ثم استدعاء
GetInt للحصول على كثافة العمليات الفعلية

261
00:11:03,830 --> 00:11:05,060
الذي تريد البحث عنه.

262
00:11:05,060 --> 00:11:06,460
>> ثم لاحظ هذا.

263
00:11:06,460 --> 00:11:10,690
أنا ذاهب لإنشاء متغير مؤقت
في خط 188 يسمى مؤشر -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
يمكن أن يطلق عليه أي شيء.

266
00:11:12,440 --> 00:11:16,140
وانها مؤشر إلى عقدة
لأنني وقال العقدة * هناك.

267
00:11:16,140 --> 00:11:19,900
وأنا تهيئة ليكون مساويا ل
أولا حتى أن لدي فعال بلدي

268
00:11:19,900 --> 00:11:22,860
الاصبع، إذا جاز التعبير، على جدا
العنصر الأول من القائمة.

269
00:11:22,860 --> 00:11:27,460
إذا كان الأمر كذلك يدي اليمنى هنا هو PTR أنا
مشيرا في نفس الشيء الذي الأولى

270
00:11:27,460 --> 00:11:28,670
ومشيرا في الوقت ذاته.

271
00:11:28,670 --> 00:11:31,430
>> وحتى الآن مرة أخرى في رمز،
ما يحدث بعد ذلك -

272
00:11:31,430 --> 00:11:35,070
هذا هو نموذج شائع عند بالتكرار
على هيكل مثل

273
00:11:35,070 --> 00:11:35,970
قائمة مرتبطة.

274
00:11:35,970 --> 00:11:40,410
انا ذاهب للقيام في حين التالية
مؤشر لا تساوي قيمة خالية حتى حين

275
00:11:40,410 --> 00:11:47,530
إصبعي هو عدم الإشارة في بعض اغية
القيمة، إن مؤشر السهم يساوي ن ن.

276
00:11:47,530 --> 00:11:52,290
نحن ستلاحظ الأولى التي n هو ما
المستعمل في طباعة في GetInts ندعو هنا.

277
00:11:52,290 --> 00:11:54,280
>> ومؤشر السهم ن يعني ماذا؟

278
00:11:54,280 --> 00:11:59,020
كذلك إذا رجعنا إلى الصورة هنا،
إذا كان لدي أصابع الاتهام في

279
00:11:59,020 --> 00:12:02,960
أن العقدة الأولى تحتوي على تسعة، و
يعني أساسا سهم تذهب إلى أن

280
00:12:02,960 --> 00:12:08,860
عقدة والاستيلاء على القيمة في موقع ن،
في هذه الحالة، حقل البيانات دعا ن.

281
00:12:08,860 --> 00:12:14,120
>> بوصفها جانبا - ورأينا ذلك زوجين
من قبل أسابيع عندما طلب شخص ما -

282
00:12:14,120 --> 00:12:18,840
بناء الجملة هذا هو الجديد، ولكن لم يحدث ذلك
تعطينا الصلاحيات التي نحن

283
00:12:18,840 --> 00:12:20,040
لم يكن لديك بالفعل.

284
00:12:20,040 --> 00:12:25,325
ما كان يعادل هذه العبارة باستخدام
نقطة تدوين ونجم زوجين

285
00:12:25,325 --> 00:12:29,490
من قبل أسابيع عندما نحن مقشر الظهر
هذه الطبقة قليلا قبل الأوان؟

286
00:12:29,490 --> 00:12:31,780
>> الطالب: [غير مسموع].

287
00:12:31,780 --> 00:12:38,880
>> سرور 1: بالضبط، كان نجوم، و
ثم كان نجم دوت ن، مع

288
00:12:38,880 --> 00:12:41,930
الأقواس هنا، والتي تبدو،
بصراحة، اعتقد ان الكثير

289
00:12:41,930 --> 00:12:43,320
أكثر خفي للقراءة.

290
00:12:43,320 --> 00:12:46,270
ولكن نجم المؤشر، كما هو الحال دائما،
الوسائل الذهاب إلى هناك.

291
00:12:46,270 --> 00:12:49,090
ومرة كنت هناك، ما هي البيانات
الحقل الذي تريد الوصول؟

292
00:12:49,090 --> 00:12:52,730
كذلك يمكنك استخدام نقطة تدوين الوصول إلى
حقل بيانات البنيات، وأنا

293
00:12:52,730 --> 00:12:54,140
نريد على وجه التحديد ن.

294
00:12:54,140 --> 00:12:56,240
>> بصراحة، أنا أزعم هذا
هو مجرد صعوبة في القراءة.

295
00:12:56,240 --> 00:12:58,080
أنه من الصعب أن تتذكر أين
لا تذهب الأقواس، و

296
00:12:58,080 --> 00:12:59,030
ونجم عن ذلك.

297
00:12:59,030 --> 00:13:02,150
لذلك اعتمدت بعض النحوية العالم
السكر، إذا جاز التعبير.

298
00:13:02,150 --> 00:13:04,740
مجرد وسيلة للقول مثير،
وهذا هو ما يعادلها، و

299
00:13:04,740 --> 00:13:05,970
ربما أكثر بديهية.

300
00:13:05,970 --> 00:13:09,600
إذا المؤشر هو في الواقع مؤشر، و
تدوين السهم يعني نذهب الى هناك وتجد

301
00:13:09,600 --> 00:13:11,890
مجال في هذه الحالة تسمى ن.

302
00:13:11,890 --> 00:13:13,660
>> إذا كان الأمر كذلك أجد أنه لاحظ ما أقوم به.

303
00:13:13,660 --> 00:13:17,430
أنا ببساطة طباعة، لقد وجدت في المئة ط،
يسد في قيمة لهذا الباحث.

304
00:13:17,430 --> 00:13:20,730
أدعو النوم لثانية واحدة فقط لنوع
من وقفة الأشياء على الشاشة ل

305
00:13:20,730 --> 00:13:22,900
إعطاء المستخدم الثاني على استيعاب
ما حدث للتو.

306
00:13:22,900 --> 00:13:24,290
وبعد ذلك كسر.

307
00:13:24,290 --> 00:13:26,330
خلاف ذلك، ماذا أفعل؟

308
00:13:26,330 --> 00:13:30,960
أقوم بتحديث مؤشر على قدم المساواة
مؤشر سهم المقبل.

309
00:13:30,960 --> 00:13:35,840
>> حتى مجرد أن يكون واضحا، وهذا يعني ذهاب
هناك، وذلك باستخدام بلدي تدوين المدرسة القديمة.

310
00:13:35,840 --> 00:13:39,580
لذلك هذا يعني فقط أن تذهب إلى أي
كنت مشيرا في الوقت ذاته، وهو في غاية

311
00:13:39,580 --> 00:13:43,660
الحالة الأولى هو أنا لافتا في
البنية مع تسعة في ذلك.

312
00:13:43,660 --> 00:13:44,510
حتى لقد ذهب هناك.

313
00:13:44,510 --> 00:13:47,880
ثم نقطة تدوين يعني،
الحصول على قيمة في القادم.

314
00:13:47,880 --> 00:13:50,470
>> ولكن القيمة، على الرغم من انها مرسومة
باعتبارها الضيقة، هو مجرد رقم.

315
00:13:50,470 --> 00:13:51,720
انها عنوان رقمية.

316
00:13:51,720 --> 00:13:55,670
لذلك هذا سطر واحد من التعليمات البرمجية، سواء
كتابة مثل هذا، وأكثر خفي

317
00:13:55,670 --> 00:14:00,190
الطريق، أو ما شابه ذلك، وأكثر قليلا
طريقة بديهية، يعني مجرد تحريك يدي

318
00:14:00,190 --> 00:14:03,460
من العقدة الأولى إلى المرحلة التالية،
ثم المرحلة التالية، ومن ثم

319
00:14:03,460 --> 00:14:05,320
المرحلة التالية، وهكذا دواليك.

320
00:14:05,320 --> 00:14:09,920
>> لذلك نحن لن أطيل في الحديث عن الآخرين
تطبيقات إدراج وحذف

321
00:14:09,920 --> 00:14:14,030
واجتياز، أول اثنين من
التي تشارك إلى حد ما.

322
00:14:14,030 --> 00:14:17,010
وأعتقد أنه من السهل جدا للحصول على
فقدت عندما يفعلون ذلك لفظيا.

323
00:14:17,010 --> 00:14:19,890
ولكن ما يمكننا القيام به هنا هو
محاولة لتحديد كيفية

324
00:14:19,890 --> 00:14:21,640
أفضل للقيام بذلك بصريا.

325
00:14:21,640 --> 00:14:24,800
لأنني سيقترح أنه إذا كنا
ترغب في إدراج عناصر في هذا

326
00:14:24,800 --> 00:14:26,680
قائمة موجودة، والتي
لديه خمسة عناصر -

327
00:14:26,680 --> 00:14:29,530
9، 17، 22، 26، و 33 -

328
00:14:29,530 --> 00:14:33,300
إذا أنا كانوا في طريقهم لتنفيذ ذلك في
رمز، ولست بحاجة للنظر في كيفية التوجه

329
00:14:33,300 --> 00:14:34,160
القيام بذلك عن.

330
00:14:34,160 --> 00:14:37,720
>> وأود أن أقترح اتخاذ خطوات طفل
حيث، في هذه الحالة أعني، ما هي

331
00:14:37,720 --> 00:14:41,090
السيناريوهات المحتملة أننا
قد تواجهها بشكل عام؟

332
00:14:41,090 --> 00:14:44,120
عند تنفيذ إدراج لربط
قائمة، وهذا يحدث لمجرد أن يكون

333
00:14:44,120 --> 00:14:46,090
مثال محدد من حجم الخمس.

334
00:14:46,090 --> 00:14:50,420
كذلك إذا كنت ترغب في إدراج رقم،
مثل يقول رقم واحد، و

335
00:14:50,420 --> 00:14:53,380
الحفاظ على النظام فرزها، حيث
ومن الواضح أن لا حاجة إلى رقم واحد

336
00:14:53,380 --> 00:14:55,686
تذهب في هذا المثال محددة؟

337
00:14:55,686 --> 00:14:56,840
مثل في البداية.

338
00:14:56,840 --> 00:15:00,030
>> ولكن ما هو مثير للاهتمام هو أن هناك
إذا كنت ترغب في إدراج واحد في هذا

339
00:15:00,030 --> 00:15:04,100
القائمة، ما احتياجات مؤشر خاص
ليتم تحديثه على ما يبدو؟

340
00:15:04,100 --> 00:15:04,610
أولا.

341
00:15:04,610 --> 00:15:07,830
ولذا فإنني أزعم أن هذا هو الحالة الأولى
أننا قد ترغب في النظر، و

342
00:15:07,830 --> 00:15:11,140
السيناريو تشمل إدراج في
في بداية القائمة.

343
00:15:11,140 --> 00:15:15,400
>> دعونا نتف قبالة ربما وسيلة سهلة كما أو حتى
أسهل القضية، نسبيا.

344
00:15:15,400 --> 00:15:18,110
افترض تريد إدراج
عدد 35 من أجل فرزها.

345
00:15:18,110 --> 00:15:20,600
من الواضح أنه ينتمي هناك.

346
00:15:20,600 --> 00:15:25,320
فما المؤشر الواضح هو ذاهب ل
يجب أن يتم تحديثه في هذا السيناريو؟

347
00:15:25,320 --> 00:15:30,060
المؤشر 34 في أن تصبح غير فارغة
ولكن عنوان البنية

348
00:15:30,060 --> 00:15:31,800
تحتوي على عدد 35.

349
00:15:31,800 --> 00:15:32,750
ذلك أن حالة اثنين.

350
00:15:32,750 --> 00:15:36,190
لذلك بالفعل، وأنا نوع من تثبيت قيمة
كيف الكثير من العمل يجب أن أقوم به هنا.

351
00:15:36,190 --> 00:15:39,880
>> وأخيرا، فإن القضية وضوحا هو الوسط
في الواقع، في الوسط، إذا أريد ل

352
00:15:39,880 --> 00:15:45,870
إدراج شيء من هذا القبيل ويقول 23، أن يذهب
بين 23 و 26، ولكن

353
00:15:45,870 --> 00:15:48,680
الآن الأمور أكثر من ذلك بقليل
المشاركة لأن ما

354
00:15:48,680 --> 00:15:52,800
تحتاج إلى تغيير المؤشرات؟

355
00:15:52,800 --> 00:15:56,680
حتى 22 يحتاج إلى تغيير واضح
لأنه لا يمكن أن نشير إلى 26 بعد الآن.

356
00:15:56,680 --> 00:16:00,320
انه يحتاج للإشارة إلى عقدة جديدة
سآخذ على تخصيص من خلال الدعوة

357
00:16:00,320 --> 00:16:01,770
malloc أو بعض ما يعادلها.

358
00:16:01,770 --> 00:16:05,990
>> ولكن بعد ذلك أنا أيضا بحاجة إلى أن عقدة جديدة، 23
في هذه الحالة، أن يكون مؤشر ل

359
00:16:05,990 --> 00:16:07,870
مشيرا في الوقت ذاته لمن؟

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
وهناك سيكون ل
ترتيب العمليات هنا.

362
00:16:10,380 --> 00:16:13,410
لأنه إذا أفعل ذلك بحماقة، وأنا
على سبيل المثال تبدأ في بداية

363
00:16:13,410 --> 00:16:16,040
القائمة، وهدفي هو لادخال 23.

364
00:16:16,040 --> 00:16:18,610
وأتحقق، وأنها لا تنتمي
هنا، بالقرب من تسعة؟

365
00:16:18,610 --> 00:16:18,950
لا.

366
00:16:18,950 --> 00:16:20,670
وأنها لا تنتمي هنا، بجانب 17؟

367
00:16:20,670 --> 00:16:20,940
لا.

368
00:16:20,940 --> 00:16:22,530
وأنها لا تنتمي هنا المقبل إلى 22؟

369
00:16:22,530 --> 00:16:23,300
نعم.

370
00:16:23,300 --> 00:16:26,400
>> الآن إذا أنا أحمق هنا، وليس
التفكير من خلال هذا، وأنا قد

371
00:16:26,400 --> 00:16:28,320
تخصيص بلدي عقدة جديدة ل23.

372
00:16:28,320 --> 00:16:32,080
قد قمت بتحديث المؤشر من
عقدة دعا 22، لافتا

373
00:16:32,080 --> 00:16:33,080
أنه في عقدة جديدة.

374
00:16:33,080 --> 00:16:36,140
ثم ماذا لدي لتحديث
مؤشر عقدة جديدة إلى أن؟

375
00:16:36,140 --> 00:16:38,120
>> الطالب: [غير مسموع].

376
00:16:38,120 --> 00:16:38,385
>> سرور 1: بالضبط.

377
00:16:38,385 --> 00:16:39,710
مشيرا في الوقت ذاته 26.

378
00:16:39,710 --> 00:16:45,590
ولكن اللعنة إذا لم أكن بالفعل تحديث
المؤشر 22 نقطة لفي هذا الرجل، و

379
00:16:45,590 --> 00:16:48,260
الآن لدي الأيتام، والباقي
من القائمة، إذا جاز التعبير.

380
00:16:48,260 --> 00:16:52,140
حتى ترتيب العمليات هنا
ستكون مهمة.

381
00:16:52,140 --> 00:16:55,100
>> للقيام بذلك يمكن أنا أسرق،
ويقول، ستة متطوعين.

382
00:16:55,100 --> 00:16:57,650
ودعونا نرى ما اذا كنا لا نستطيع أن نفعل هذا
بصريا بدلا من رمز الحكمة.

383
00:16:57,650 --> 00:16:59,330
ونحن لدينا بعض الإجهاد جميلة
كرات بالنسبة لك اليوم.

384
00:16:59,330 --> 00:17:02,510
حسنا، ماذا عن واحد أو اثنين، في
دعم - على الطرف هناك.

385
00:17:02,510 --> 00:17:04,530
ثلاثة، أربعة، كل واحد منكما
الرجال في نهاية المطاف.

386
00:17:04,530 --> 00:17:05,579
وخمسة، ستة.

387
00:17:05,579 --> 00:17:05,839
بالتأكيد.

388
00:17:05,839 --> 00:17:06,450
خمسة وستة.

389
00:17:06,450 --> 00:17:08,390
كل الحق، ونحن سوف يأتي
ليا رفاق في المرة القادمة.

390
00:17:08,390 --> 00:17:09,640
كل الحق، وتأتي على ما يصل.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> كل الحق، منذ كنت هنا أولا،
تريد أن تكون واحدة برعونة

393
00:17:14,819 --> 00:17:16,119
في جوجل الزجاج هنا؟

394
00:17:16,119 --> 00:17:19,075
كل الحق، لذلك، موافق، والزجاج،
تسجيل الفيديو.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
موافق، كنت جيدة للذهاب.

397
00:17:24,589 --> 00:17:27,950
>> كل الحق، لذلك إذا يا رفاق يمكن أن يأتي أكثر
هنا، لقد أعدت مقدما

398
00:17:27,950 --> 00:17:30,110
بعض الأرقام.

399
00:17:30,110 --> 00:17:31,240
كل الحق، وتأتي على أكثر من هنا.

400
00:17:31,240 --> 00:17:33,440
ولماذا لا تذهب قليلا
زيادة على هذا النحو.

401
00:17:33,440 --> 00:17:35,520
ودعونا نرى، ما هو اسمك،
مع الزجاج جوجل؟

402
00:17:35,520 --> 00:17:35,910
>> الطالب: بن.

403
00:17:35,910 --> 00:17:36,230
>> سرور 1: بن؟

404
00:17:36,230 --> 00:17:38,380
موافق، بن، سوف تكون الأولى، حرفيا.

405
00:17:38,380 --> 00:17:40,580
لذلك نحن ذاهبون لنرسل لك
إلى نهاية المرحلة.

406
00:17:40,580 --> 00:17:41,670
كل الحق، واسمك؟

407
00:17:41,670 --> 00:17:41,990
>> الطالب: جايسون.

408
00:17:41,990 --> 00:17:44,530
>> سرور 1: جيسون، موافق عليك
يكون رقم تسعة.

409
00:17:44,530 --> 00:17:46,700
حتى إذا كنت تريد أن تتبع بن بهذه الطريقة.

410
00:17:46,700 --> 00:17:47,010
>> الطالب: جيل.

411
00:17:47,010 --> 00:17:49,630
>> سرور 1: جيل، وأنت تسير لتكون
17، والتي إذا كنت فعلت ذلك أكثر

412
00:17:49,630 --> 00:17:51,260
بذكاء، وأود أن
بدأت في الطرف الآخر.

413
00:17:51,260 --> 00:17:52,370
تذهب بهذه الطريقة.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
وأنت؟

416
00:17:53,670 --> 00:17:53,980
>> الطالب: مريم.

417
00:17:53,980 --> 00:17:56,130
>> سرور 1: ماري، عليك أن تكون 22.

418
00:17:56,130 --> 00:17:58,420
واسمك؟

419
00:17:58,420 --> 00:17:58,810
>> الطالب: كريس.

420
00:17:58,810 --> 00:18:00,100
>> سرور 1: كريس، عليك أن تكون 26.

421
00:18:00,100 --> 00:18:00,740
ثم أخيرا.

422
00:18:00,740 --> 00:18:01,400
>> الطالب: ديانا.

423
00:18:01,400 --> 00:18:02,670
>> سرور 1: ديانا، عليك أن تكون 34.

424
00:18:02,670 --> 00:18:03,920
حتى أتيت على أكثر من هنا.

425
00:18:03,920 --> 00:18:06,360
>> كل الحق، حتى الكمال فرزها
طلب بالفعل.

426
00:18:06,360 --> 00:18:09,600
ودعونا نمضي قدما ونفعل هذا
لذلك ما في وسعنا حقا -

427
00:18:09,600 --> 00:18:11,720
بن كنت مجرد نوع من البحث
للخروج الى أي مكان هناك.

428
00:18:11,720 --> 00:18:15,670
حسنا، دعونا نمضي قدما وتصور هذه
استخدام السلاح، مثل الكثير كنت، بالضبط،

429
00:18:15,670 --> 00:18:16,250
ما يحدث.

430
00:18:16,250 --> 00:18:19,540
لذلك يذهب إلى الأمام وإعطاء أنفسكم
قدم أو اثنين من بين أنفسكم.

431
00:18:19,540 --> 00:18:22,900
والمضي قدما والنقطة مع يدا واحدة ل
أيا كان يجب أن تكون لافتا في

432
00:18:22,900 --> 00:18:23,470
بناء على هذا.

433
00:18:23,470 --> 00:18:25,890
وإذا كنت مجرد نقطة فارغة
رأسا إلى أسفل إلى الأرض.

434
00:18:25,890 --> 00:18:27,690
موافق، جيد جدا.

435
00:18:27,690 --> 00:18:32,290
>> حتى الآن لدينا قائمة مرتبطة، واسمحوا لي
أقترح أن سألعب دور

436
00:18:32,290 --> 00:18:35,110
PTR، لذلك أنا لن يكلف نفسه عناء
تحمل هذه حولها.

437
00:18:35,110 --> 00:18:37,830
وبعد ذلك - شخص اتفاقية غبي -
يمكنك استدعاء هذه أي شيء تريده -

438
00:18:37,830 --> 00:18:39,800
مؤشر السلف، مؤشر PRED -

439
00:18:39,800 --> 00:18:43,930
انها مجرد لقب أعطينا في
نموذج التعليمات البرمجية جهدنا ليدي اليسرى.

440
00:18:43,930 --> 00:18:47,240
من ناحية أخرى سيتم حفظ
تتبع من هو الذي في

441
00:18:47,240 --> 00:18:48,400
السيناريوهات التالية.

442
00:18:48,400 --> 00:18:52,390
>> افترض ذلك، أولا، أريد أن نتف من
هذا المثال الأول من الإدراج، ويقول

443
00:18:52,390 --> 00:18:54,330
20، في القائمة.

444
00:18:54,330 --> 00:18:57,160
لذلك أنا ذاهب الى الحاجة شخص ما ل
تجسد رقم 20 بالنسبة لنا.

445
00:18:57,160 --> 00:18:58,950
لذلك أنا بحاجة إلى شخص malloc
من الجمهور.

446
00:18:58,950 --> 00:18:59,380
تأتي على ما يصل.

447
00:18:59,380 --> 00:19:00,340
ما اسمك؟

448
00:19:00,340 --> 00:19:01,300
>> الطالب: بريان.

449
00:19:01,300 --> 00:19:05,270
>> سرور 1: بريان، كل الحق، لذلك كنت
يجب أن تكون العقدة التي تحتوي على 20.

450
00:19:05,270 --> 00:19:06,810
كل الحق، وتأتي على أكثر من هنا.

451
00:19:06,810 --> 00:19:10,025
والواضح، حيث
لا براين تنتمي؟

452
00:19:10,025 --> 00:19:12,190
لذلك، في منتصف - في الواقع،
الانتظار لمدة دقيقة.

453
00:19:12,190 --> 00:19:13,420
نحن نفعل هذا من أجل.

454
00:19:13,420 --> 00:19:17,170
نحن نحقق هذا الكثير من الجهد
مما يجب أن يكون في البداية.

455
00:19:17,170 --> 00:19:21,210
موافق، ونحن في طريقنا لتحرير بريان
وrealloc براين الى خمسة.

456
00:19:21,210 --> 00:19:23,680
>> موافق، وحتى الآن نحن نريد أن إدراج
براين الى خمسة.

457
00:19:23,680 --> 00:19:25,960
ويأتي ذلك على أكثر من هنا بجانب
بن لمجرد لحظة.

458
00:19:25,960 --> 00:19:28,250
ويمكن أن أقول لكم يفترض
حيث هذه القصة هو ذاهب.

459
00:19:28,250 --> 00:19:30,500
ولكن دعونا نفكر مليا
ترتيب العمليات.

460
00:19:30,500 --> 00:19:32,880
وانها هذا بالضبط البصرية
وهذا ما سوف يصطف

461
00:19:32,880 --> 00:19:34,080
مع أن نموذج التعليمات البرمجية.

462
00:19:34,080 --> 00:19:40,120
حتى هنا لا بد لي في البداية PTR تأشير
ليس في بن، في حد ذاته، ولكن في كل ما

463
00:19:40,120 --> 00:19:43,245
قيمة انه يحتوي، وهو في هذه الحالة
هو - ما اسمك مرة أخرى؟

464
00:19:43,245 --> 00:19:43,670
>> الطالب: جايسون.

465
00:19:43,670 --> 00:19:47,350
>> سرور 1: جيسون، لذلك كل من بن وأنا
مشيرا في الوقت ذاته جيسون في هذه اللحظة.

466
00:19:47,350 --> 00:19:49,700
وحتى الآن لا بد لي من تحديد،
أين بريان تنتمي؟

467
00:19:49,700 --> 00:19:53,500
وبالتالي فإن الشيء الوحيد الذي يمكنني الحصول على
الآن هو له ن عنصر البيانات.

468
00:19:53,500 --> 00:19:58,280
لذلك أنا ذاهب للتحقق، هو
براين أقل من جيسون؟

469
00:19:58,280 --> 00:19:59,770
الجواب هو الصحيح.

470
00:19:59,770 --> 00:20:03,680
>> لذلك ما يحتاج الآن أن يحدث،
في الترتيب الصحيح؟

471
00:20:03,680 --> 00:20:07,120
أنا بحاجة إلى تحديث العديد من المؤشرات الكيفية
في المجموع في هذه القصة؟

472
00:20:07,120 --> 00:20:10,720
حيث يدي لا يزال لافتا في
جيسون، ويدك - إذا كنت ترغب في

473
00:20:10,720 --> 00:20:12,930
وضعت يدك مثل، نوعا ما، وأنا
لا أعرف، علامة استفهام.

474
00:20:12,930 --> 00:20:14,070
موافق، وحسن.

475
00:20:14,070 --> 00:20:15,670
>> كل الحق، ولذلك عليك
عدد قليل من المرشحين.

476
00:20:15,670 --> 00:20:20,500
إما أنا أو بن أو براين أو جيسون
أو أي شخص آخر، والتي

477
00:20:20,500 --> 00:20:21,370
مؤشرات بحاجة إلى تغيير؟

478
00:20:21,370 --> 00:20:23,260
وكم في المجموع؟

479
00:20:23,260 --> 00:20:24,080
>> موافق، لذلك اثنين.

480
00:20:24,080 --> 00:20:27,090
مؤشر بلدي لا يهم حقا بعد الآن
لأنني مؤقتة فقط.

481
00:20:27,090 --> 00:20:31,370
لذلك فمن هؤلاء الرجال اثنين، ويفترض،
كلا بن وبريان.

482
00:20:31,370 --> 00:20:34,410
لذلك اسمحوا لي أقترح أن نقوم بتحديث
بن، لأنه هو الأول.

483
00:20:34,410 --> 00:20:36,350
العنصر الأول من هذه القائمة
الآن سيكون بريان.

484
00:20:36,350 --> 00:20:38,070
لذلك نقطة بن في بريان.

485
00:20:38,070 --> 00:20:39,320
حسنا، ماذا نفعل الآن؟

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> الذي يحصل أشار في من؟

488
00:20:43,460 --> 00:20:44,710
>> الطالب: [غير مسموع].

489
00:20:44,710 --> 00:20:46,180
>> سرور 1: OK حتى براين لديه
للإشارة إلى جيسون.

490
00:20:46,180 --> 00:20:48,360
ولكن قد فقدت المسار من هذا المؤشر؟

491
00:20:48,360 --> 00:20:49,980
لا أعرف أين هو جيسون؟

492
00:20:49,980 --> 00:20:50,790
>> الطالب: [غير مسموع].

493
00:20:50,790 --> 00:20:52,620
>> سرور 1: أفعل، أنا منذ
مؤشر مؤقتة.

494
00:20:52,620 --> 00:20:55,110
ويفترض، وأنا لم تتغير
للإشارة إلى عقدة جديدة.

495
00:20:55,110 --> 00:20:58,300
ولذا فإننا يمكن أن يكون مجرد نقطة بريان
في كل من أنا لافتا في.

496
00:20:58,300 --> 00:20:59,000
وننتهي.

497
00:20:59,000 --> 00:21:01,890
حتى حالة واحدة، الإدراج في
بداية القائمة.

498
00:21:01,890 --> 00:21:02,950
كان هناك اثنين من الخطوات الرئيسية.

499
00:21:02,950 --> 00:21:06,750
واحدة، لدينا لتحديث بن، ثم
لدينا أيضا لتحديث بريان.

500
00:21:06,750 --> 00:21:09,230
وبعد ذلك لم يكن لديك لعناء
التمشي من خلال ما تبقى من

501
00:21:09,230 --> 00:21:12,680
قائمة، لأننا وجدنا بالفعل له
الموقع، لأنه ينتمي إلى

502
00:21:12,680 --> 00:21:14,080
تبقى من العنصر الأول.

503
00:21:14,080 --> 00:21:15,400
>> كل الحق، لذلك واضحة جدا.

504
00:21:15,400 --> 00:21:18,110
في الواقع، وكأننا نحن تقريبا
مما يجعل هذه معقدة للغاية.

505
00:21:18,110 --> 00:21:20,240
لذلك دعونا نتف الآن قبالة نهاية
من القائمة، ونرى أين

506
00:21:20,240 --> 00:21:21,380
يبدأ التعقيد.

507
00:21:21,380 --> 00:21:24,560
إذا كان الأمر كذلك الآن، وأنا ALLOC من الجمهور.

508
00:21:24,560 --> 00:21:25,540
أي شخص يريد أن يلعب 55؟

509
00:21:25,540 --> 00:21:26,700
كل الحق، رأيت يدك أولا.

510
00:21:26,700 --> 00:21:29,620
تأتي على ما يصل.

511
00:21:29,620 --> 00:21:30,030
نعم.

512
00:21:30,030 --> 00:21:31,177
ما اسمك؟

513
00:21:31,177 --> 00:21:32,310
>> الطالب: [غير مسموع].

514
00:21:32,310 --> 00:21:33,240
>> سرور 1: Habata.

515
00:21:33,240 --> 00:21:33,890
موافق، وتأتي على ما يصل.

516
00:21:33,890 --> 00:21:35,730
عليك أن تكون عدد 55.

517
00:21:35,730 --> 00:21:37,820
لذلك كنت، بطبيعة الحال، تنتمي
في نهاية القائمة.

518
00:21:37,820 --> 00:21:41,850
لذلك دعونا اعادتها محاكاة معي
كونها PTR لمجرد لحظة.

519
00:21:41,850 --> 00:21:44,050
لذلك أنا ذاهب أول من أشار في
أيا كان لافتا في بن.

520
00:21:44,050 --> 00:21:45,900
نحن على حد سواء مشيرا الآن في بريان.

521
00:21:45,900 --> 00:21:48,420
حتى 55 ليست أقل من خمس سنوات.

522
00:21:48,420 --> 00:21:52,510
لذلك أنا ذاهب لتحديث نفسي
مشيرا إلى مؤشر براين المقبل، الذي

523
00:21:52,510 --> 00:21:54,450
الآن بالطبع جيسون.

524
00:21:54,450 --> 00:21:57,310
55 ليس أقل من تسعة، لذلك
أنا ذاهب لتحديث PTR.

525
00:21:57,310 --> 00:21:58,890
أنا ذاهب لتحديث PTR.

526
00:21:58,890 --> 00:22:02,290
أنا ذاهب لتحديث PTR
أنا ذاهب لتحديث PTR.

527
00:22:02,290 --> 00:22:05,060
وانا ذاهب الى - هم، ما هو
اسمك مرة أخرى؟

528
00:22:05,060 --> 00:22:05,560
>> الطالب: ديانا.

529
00:22:05,560 --> 00:22:09,190
>> سرور 1: ديانا يشير، بطبيعة الحال،
في فارغة مع يدها اليسرى.

530
00:22:09,190 --> 00:22:13,030
حتى أين Habata الواقع
تنتمي بشكل واضح؟

531
00:22:13,030 --> 00:22:15,050
إلى اليسار، هنا.

532
00:22:15,050 --> 00:22:19,460
لذلك كيف لي أن أعرف أن يضع لها هنا
أعتقد أنني ثمل.

533
00:22:19,460 --> 00:22:22,420
لأن ما هو الفن PTR
هذه اللحظة في الوقت المناسب؟

534
00:22:22,420 --> 00:22:23,240
فارغة.

535
00:22:23,240 --> 00:22:25,580
على الرغم من ذلك، بصريا، ما في وسعنا
ومن الواضح أن نرى كل هذه

536
00:22:25,580 --> 00:22:26,610
الرجال هنا على خشبة المسرح.

537
00:22:26,610 --> 00:22:29,680
أنا لم يحتفظ تعقب من السابق
شخص في القائمة.

538
00:22:29,680 --> 00:22:33,210
ليس لدي إصبع مشيرا إلى،
في هذه الحالة، عقدة عدد 34.

539
00:22:33,210 --> 00:22:34,760
>> لذلك دعونا نبدأ هذا الواقع أكثر.

540
00:22:34,760 --> 00:22:37,560
حتى الآن أنا فعلا بحاجة
متغير محلي الثانية.

541
00:22:37,560 --> 00:22:40,980
وهذا ما سترى في
نموذج التعليمات البرمجية C الفعلية، حيث كما ذهبت،

542
00:22:40,980 --> 00:22:45,860
عندما أقوم بتحديث يدي اليمنى إلى نقطة
جيسون، وبالتالي يترك بريان وراء، وأنا

543
00:22:45,860 --> 00:22:51,440
بدء باستخدام أفضل يدي اليسرى ل
تحديث حيث كنت، بحيث كما أذهب

544
00:22:51,440 --> 00:22:52,700
من خلال هذه القائمة -

545
00:22:52,700 --> 00:22:55,040
أكثر برعونة من نويت
الآن هنا بصريا -

546
00:22:55,040 --> 00:22:56,740
انا ذاهب للوصول الى
نهاية القائمة.

547
00:22:56,740 --> 00:23:00,020
>> هذه اليد لا تزال فارغة، وهي جميلة
لا طائل منه، سوى تشير

548
00:23:00,020 --> 00:23:02,980
أنا بوضوح في نهاية القائمة،
ولكن الآن على الأقل لدي هذا

549
00:23:02,980 --> 00:23:08,270
مؤشر السلف لافتا هنا، لذلك
الآن ماذا اليدين ومؤشرات ما تحتاج

550
00:23:08,270 --> 00:23:10,150
ليتم تحديثه؟

551
00:23:10,150 --> 00:23:13,214
الذي بيده تريد
لإعادة تكوين أول؟

552
00:23:13,214 --> 00:23:15,190
>> الطالب: [غير مسموع].

553
00:23:15,190 --> 00:23:16,220
>> سرور 1: موافق، لذلك لديانا.

554
00:23:16,220 --> 00:23:21,110
أين أريد أن أشير
ديانا تركت المؤشر في؟

555
00:23:21,110 --> 00:23:23,620
في 55، ويفترض، بحيث
لقد أدرجت هناك.

556
00:23:23,620 --> 00:23:25,560
وأين يجب أن تذهب 55 مؤشر؟

557
00:23:25,560 --> 00:23:27,000
أسفل، تمثل فارغة.

558
00:23:27,000 --> 00:23:28,890
ويدي، وعند هذه النقطة، لا
يهم لأنهم كانوا فقط

559
00:23:28,890 --> 00:23:30,070
المتغيرات المؤقتة.

560
00:23:30,070 --> 00:23:31,030
وحتى الآن نحن القيام به.

561
00:23:31,030 --> 00:23:34,650
>> وبالتالي فإن هناك تعقيد إضافي - و
انها ليست من الصعب أن تنفذ،

562
00:23:34,650 --> 00:23:38,660
ولكن نحن بحاجة إلى متغير الثانوية لجعل
تأكد من أن قبل أن أنتقل حقي

563
00:23:38,660 --> 00:23:42,140
ناحية، وتحديث قيمة يساري
اليد، مؤشر PRED في هذه الحالة، لذلك

564
00:23:42,140 --> 00:23:45,860
أن لدي مؤشر زائدة
لتتبع مكان وجودي.

565
00:23:45,860 --> 00:23:49,360
الآن بوصفها جانبا، إذا كنت تفكر هذا
من خلال، وهذا يبدو وكأنه انها

566
00:23:49,360 --> 00:23:51,490
قليلا مزعج لديك للحفاظ على
تتبع هذه اليد اليسرى.

567
00:23:51,490 --> 00:23:54,015
>> ما من شأنه حل آخر
لهذه المشكلة حتى الآن؟

568
00:23:54,015 --> 00:23:56,500
إذا كنت حصلت على إعادة تصميم البيانات
هيكل نتحدث

569
00:23:56,500 --> 00:23:59,630
خلال الوقت الراهن؟

570
00:23:59,630 --> 00:24:02,690
إذا كان هذا مجرد نوع من يشعر قليلا
مزعج أن يكون، مثل، واثنين من المؤشرات

571
00:24:02,690 --> 00:24:08,430
الذهاب من خلال قائمة، من آخر يمكن أن
و، في عالم مثالي، حافظت

572
00:24:08,430 --> 00:24:10,160
المعلومات التي نحتاجها؟

573
00:24:10,160 --> 00:24:11,360
نعم؟

574
00:24:11,360 --> 00:24:12,610
>> الطالب: [غير مسموع].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> سرور 1: بالضبط.

577
00:24:16,150 --> 00:24:19,130
الحق حتى لا يكون هناك في الواقع مثيرة للاهتمام
جرثومه فكرة.

578
00:24:19,130 --> 00:24:22,470
وهذه الفكرة من مؤشر السابقة،
مشيرا في العنصر السابق.

579
00:24:22,470 --> 00:24:25,580
ماذا لو أنا فقط جسدت
داخل القائمة نفسها؟

580
00:24:25,580 --> 00:24:27,810
وانها سوف يكون من الصعب تصور
هذا من دون كل ورقة

581
00:24:27,810 --> 00:24:28,830
السقوط على الأرض.

582
00:24:28,830 --> 00:24:31,860
ولكن لنفترض أن هؤلاء الرجال استخدامها على حد سواء
من أيديهم لديها السابقة

583
00:24:31,860 --> 00:24:35,950
المؤشر، ومؤشر المقبل، وبالتالي
تنفيذ ما سنقوم استدعاء مضاعف

584
00:24:35,950 --> 00:24:36,830
قائمة مرتبطة.

585
00:24:36,830 --> 00:24:41,090
التي من شأنها أن تسمح لي لفرز من الترجيع،
بسهولة أكبر بكثير دون لي،

586
00:24:41,090 --> 00:24:43,800
مبرمج، الحاجة إلى الاحتفاظ
تتبع يدويا -

587
00:24:43,800 --> 00:24:44,980
يدويا حقا -

588
00:24:44,980 --> 00:24:47,280
من حيث كنت قد سبق
في القائمة.

589
00:24:47,280 --> 00:24:48,110
لذلك نحن لن نفعل ذلك.

590
00:24:48,110 --> 00:24:50,950
سنقوم يبقيه بسيط لأن هذا هو
سوف يأتي في الأسعار، ضعف

591
00:24:50,950 --> 00:24:53,450
مساحة كبيرة للمؤشرات،
إذا كنت ترغب في ثانية واحدة.

592
00:24:53,450 --> 00:24:55,760
ولكن هذا الواقع المشترك
هيكل البيانات المعروفة باسم

593
00:24:55,760 --> 00:24:57,410
قائمة مرتبطة على نحو مضاعف.

594
00:24:57,410 --> 00:25:01,310
>> دعونا نفعل المثال النهائي هنا وضعت
هؤلاء الرجال من بؤسهم.

595
00:25:01,310 --> 00:25:03,270
حتى malloc 20.

596
00:25:03,270 --> 00:25:05,320
تأتي على ما يصل من الممر هناك.

597
00:25:05,320 --> 00:25:06,280
كل الحق، ما هو اسمك؟

598
00:25:06,280 --> 00:25:07,440
>> الطالب: [غير مسموع].

599
00:25:07,440 --> 00:25:07,855
>> سرور 1: عذرا؟

600
00:25:07,855 --> 00:25:08,480
>> الطالب: [غير مسموع].

601
00:25:08,480 --> 00:25:09,410
>> سرور 1: Demeron؟

602
00:25:09,410 --> 00:25:10,230
موافق تأتي على ما يصل.

603
00:25:10,230 --> 00:25:11,910
يجب أن تكون 20.

604
00:25:11,910 --> 00:25:14,720
من الواضح أنك ذاهب ل
تنتمي بين 17 و 22.

605
00:25:14,720 --> 00:25:16,150
لذلك اسمحوا لي تعلم الدرس.

606
00:25:16,150 --> 00:25:18,150
أنا ذاهب لبدء المؤشر
مشيرا في بريان.

607
00:25:18,150 --> 00:25:21,190
وانا ذاهب ليدي اليسرى
تحديث فقط لبراين وأنا الانتقال إلى

608
00:25:21,190 --> 00:25:23,600
جيسون، والتحقق من يفعل 20 أقل من تسعة؟

609
00:25:23,600 --> 00:25:24,060
لا.

610
00:25:24,060 --> 00:25:25,430
20 أقل من 17؟

611
00:25:25,430 --> 00:25:25,880
لا.

612
00:25:25,880 --> 00:25:27,450
20 أقل من 22؟

613
00:25:27,450 --> 00:25:28,440
نعم.

614
00:25:28,440 --> 00:25:34,070
فما مؤشرات أو اليدين بحاجة إلى تغيير
حيث انهم مشيرا الآن؟

615
00:25:34,070 --> 00:25:37,070
>> لذلك يمكننا أن نفعل 17 التأشير على 20.

616
00:25:37,070 --> 00:25:37,860
بحيث بخير.

617
00:25:37,860 --> 00:25:40,080
أين نريد أن نشير
المؤشر الآن؟

618
00:25:40,080 --> 00:25:41,330
في 22.

619
00:25:41,330 --> 00:25:45,410
ونحن نعرف أين هو 22، ومرة ​​أخرى وذلك بفضل
لمؤشر بلدي مؤقت.

620
00:25:45,410 --> 00:25:46,760
لذلك نحن موافق هناك.

621
00:25:46,760 --> 00:25:49,440
لذلك وبسبب هذا التخزين المؤقت
لقد أبقى المسار من حيث الجميع.

622
00:25:49,440 --> 00:25:55,055
والآن يمكنك الذهاب إلى حيث بصريا
كنت تنتمي، والآن نحن بحاجة 1، 2، 3،

623
00:25:55,055 --> 00:25:58,410
4، 5، 6، 7، 8، 9 كرات الإجهاد،
وجولة من التصفيق ل

624
00:25:58,410 --> 00:25:59,770
هؤلاء الرجال، إذا استطعنا.

625
00:25:59,770 --> 00:26:00,410
عمله بشكل جيد.

626
00:26:00,410 --> 00:26:05,320
>> [تصفيق]

627
00:26:05,320 --> 00:26:06,330
>> سرور 1: حسنا.

628
00:26:06,330 --> 00:26:09,860
وكنت قد الحفاظ على القطع
من الورق وتذكارات.

629
00:26:09,860 --> 00:26:15,930
>> كل الحق، لذلك، ثق بي انها الكثير
أسهل على المشي من خلال ذلك مع

630
00:26:15,930 --> 00:26:17,680
البشر مما هو عليه مع رمز الفعلي.

631
00:26:17,680 --> 00:26:22,690
ولكن ما سوف تجد في مجرد لحظة
الآن، هو أن نفس - أوه، شكرا لك.

632
00:26:22,690 --> 00:26:23,630
شكرا لك -

633
00:26:23,630 --> 00:26:29,360
هو أنك سوف تجد أن نفس البيانات
هيكل، قائمة مرتبطة، ويمكن في الواقع

634
00:26:29,360 --> 00:26:33,200
أن تستخدم لبنة لأكثر
هياكل البيانات المعقدة.

635
00:26:33,200 --> 00:26:37,620
>> وندرك أيضا موضوع هنا هو أن
لقد أدخلت على الاطلاق المزيد

636
00:26:37,620 --> 00:26:40,060
التعقيد في التنفيذ
هذه الخوارزمية.

637
00:26:40,060 --> 00:26:43,940
الإدراج، وإذا ذهبنا من خلال ذلك،
الحذف والبحث، وقليلا

638
00:26:43,940 --> 00:26:46,660
أكثر تعقيدا من ذلك
كان مع مجموعة.

639
00:26:46,660 --> 00:26:48,040
ولكن نكتسب بعض الدينامية.

640
00:26:48,040 --> 00:26:50,180
نحصل على بنية البيانات التكيفية.

641
00:26:50,180 --> 00:26:54,010
>> ولكن مرة أخرى، نحن ندفع ثمنا من وجود بعض
تعقيد إضافي، سواء في

642
00:26:54,010 --> 00:26:54,910
تنفيذ ذلك.

643
00:26:54,910 --> 00:26:56,750
ونحن تخلت الوصول العشوائي.

644
00:26:56,750 --> 00:27:00,450
وإلى أن نكون صادقين، ليس هناك بعض لطيفة
شريحة نظيفة وأستطيع أن أعطي لكم أن

645
00:27:00,450 --> 00:27:03,120
يقول هنا هو السبب في قائمة مرتبطة
أفضل من صفيف.

646
00:27:03,120 --> 00:27:04,100
وترك الأمر عند هذا الحد.

647
00:27:04,100 --> 00:27:07,520
لأن تكرار الموضوع الآن، حتى
أكثر من ذلك في الأسابيع المقبلة، هو

648
00:27:07,520 --> 00:27:10,200
أن هناك ليست بالضرورة
الجواب الصحيح.

649
00:27:10,200 --> 00:27:13,830
>> هذا هو السبب لدينا محور منفصلة
من تصميم لمجموعات المشكلة.

650
00:27:13,830 --> 00:27:17,700
سيكون السياق الحساسة جدا
إذا كنت ترغب في استخدام هذه البيانات

651
00:27:17,700 --> 00:27:21,750
هيكل أو أن واحد، وأنه سوف
تعتمد على ما يهم لك من حيث

652
00:27:21,750 --> 00:27:24,620
الموارد والتعقيد.

653
00:27:24,620 --> 00:27:28,830
>> ولكن اسمحوا لي أن أقترح أن البيانات المثالي
هيكل، الكأس المقدسة، سيكون

654
00:27:28,830 --> 00:27:32,200
شيء حان الوقت مستمر،
بغض النظر عن مدى الاشياء

655
00:27:32,200 --> 00:27:36,940
في داخله، لن يكون من المدهش إذا كان
عاد بنية البيانات في إجابات

656
00:27:36,940 --> 00:27:37,920
وقت ثابت.

657
00:27:37,920 --> 00:27:38,330
نعم.

658
00:27:38,330 --> 00:27:40,110
هذه الكلمة هي في القاموس الضخم الخاص بك.

659
00:27:40,110 --> 00:27:41,550
أو لا، هذه الكلمة ليست كذلك.

660
00:27:41,550 --> 00:27:43,270
أو أي مشكلة من هذا النوع هناك.

661
00:27:43,270 --> 00:27:46,360
حسنا دعونا نرى ما اذا كنا نستطيع على الأقل لا
اتخاذ خطوة تجاه ذلك.

662
00:27:46,360 --> 00:27:50,190
>> اسمحوا لي أن أقترح بنية بيانات جديدة
يمكن استخدامها لأشياء مختلفة،

663
00:27:50,190 --> 00:27:52,260
في هذه الحالة يسمى جدول تجزئة.

664
00:27:52,260 --> 00:27:55,590
وهكذا نحن بالفعل إلى نظرة عابرة
في صفيف، في هذه الحالة، و

665
00:27:55,590 --> 00:28:00,550
بشكل تعسفي إلى حد ما، لقد رسمت هذه
تجزئة الجدول كما صفيف مع نوع من

666
00:28:00,550 --> 00:28:02,810
صفيف ثنائي الأبعاد -

667
00:28:02,810 --> 00:28:05,410
أو بالأحرى هو مبين هنا باعتباره اثنين
صفيف الأبعاد - ولكن هذا هو مجرد

668
00:28:05,410 --> 00:28:10,770
مجموعة من حجم 26، بحيث إذا كنا
استدعاء مجموعة الجدول، الجدول قوس

669
00:28:10,770 --> 00:28:12,440
الصفر هو المستطيل في الأعلى.

670
00:28:12,440 --> 00:28:15,090
الجدول قوس 25 هو مستطيل
في الجزء السفلي.

671
00:28:15,090 --> 00:28:18,620
وهذه هي الطريقة التي كنت قد رسم البيانات
هيكل الذي أريد أن تخزين

672
00:28:18,620 --> 00:28:19,790
أسماء الناس.

673
00:28:19,790 --> 00:28:24,370
>> هكذا على سبيل المثال، وأنا لن يوجه
كل شيء هنا على النفقات العامة، وإذا كنت

674
00:28:24,370 --> 00:28:29,160
كان هذا مجموعة، وأنا ذاهب الآن ل
استدعاء جدول التجزئة، وهذا هو مرة أخرى

675
00:28:29,160 --> 00:28:31,360
موقع الصفر.

676
00:28:31,360 --> 00:28:34,840
هذا هو المكان هنا
واحد، وهكذا دواليك.

677
00:28:34,840 --> 00:28:37,880
أزعم أنني أريد أن استخدام هذه البيانات
هيكل، من أجل المناقشة،

678
00:28:37,880 --> 00:28:42,600
لتخزين أسماء الناس، أليس وبوب
وتشارلي وهذه الأسماء الأخرى.

679
00:28:42,600 --> 00:28:46,110
حتى التفكير في هذا الآن باسم البدايات
، ويقول، القاموس

680
00:28:46,110 --> 00:28:47,520
مع الكثير من الكلمات.

681
00:28:47,520 --> 00:28:49,435
حدوثها لتكون أسماء
في مثالنا هنا.

682
00:28:49,435 --> 00:28:52,560
وهذا هو كل شيء وثيق جدا، ربما، ل
تنفيذ المدقق الإملائي، ونحن

683
00:28:52,560 --> 00:28:54,400
القوة لمشكلة تعيين ستة.

684
00:28:54,400 --> 00:28:59,300
>> حتى إذا كان لدينا مجموعة من الحجم الإجمالي 26
ذلك أن هذا هو الموقع 25

685
00:28:59,300 --> 00:29:03,390
في الجزء السفلي، وأزعم أن أليس هو
الكلمة الأولى في قاموس

686
00:29:03,390 --> 00:29:07,260
الأسماء التي أريد أن تضاف إلى ذاكرة الوصول العشوائي،
في هذه البنية البيانات، حيث هي

687
00:29:07,260 --> 00:29:12,480
الغرائز أقول لك أن أليس
يجب ان تذهب الاسم في هذه المجموعة؟

688
00:29:12,480 --> 00:29:13,510
>> لدينا 26 خيارات.

689
00:29:13,510 --> 00:29:14,990
حيث أننا نريد أن نضع لها؟

690
00:29:14,990 --> 00:29:16,200
نريد لها في قوس الصفر، أليس كذلك؟

691
00:29:16,200 --> 00:29:18,280
ألف لأليس، دعونا ندعو أن الصفر.

692
00:29:18,280 --> 00:29:20,110
وسيكون واحدا B، C وسيكون اثنين.

693
00:29:20,110 --> 00:29:22,600
لذلك نحن ذاهبون الى الكتابة
اسم أليس هنا.

694
00:29:22,600 --> 00:29:24,890
إذا كنا ثم إدراج بوب، له
واسم الذهاب هنا.

695
00:29:24,890 --> 00:29:27,280
سوف تشارلي تذهب هنا.

696
00:29:27,280 --> 00:29:30,500
وهكذا دواليك إلى أسفل من خلال
هذه البنية البيانات.

697
00:29:30,500 --> 00:29:32,090
>> هذا هو بنية بيانات رائعة.

698
00:29:32,090 --> 00:29:32,730
لماذا؟

699
00:29:32,730 --> 00:29:37,460
جيدا ما هو الوقت المناسب للتشغيل
إدراج اسم البشري في هذا

700
00:29:37,460 --> 00:29:39,850
هيكل البيانات الآن؟

701
00:29:39,850 --> 00:29:43,702
بالنظر إلى أن يتم تنفيذ هذا الجدول،
حقا، كما صفيف.

702
00:29:43,702 --> 00:29:44,940
كذلك حان الوقت مستمر.

703
00:29:44,940 --> 00:29:45,800
انها أمر واحد.

704
00:29:45,800 --> 00:29:46,360
لماذا؟

705
00:29:46,360 --> 00:29:48,630
>> كذلك كيف يمكن تحديد
حيث ينتمي أليس؟

706
00:29:48,630 --> 00:29:51,000
نظرتم الذي إلكتروني اسمها؟

707
00:29:51,000 --> 00:29:51,490
أول.

708
00:29:51,490 --> 00:29:54,350
ويمكن أن تحصل هناك، إذا كان سلسلة،
من خلال النظر فقط في سلسلة

709
00:29:54,350 --> 00:29:55,200
قوس الصفر.

710
00:29:55,200 --> 00:29:57,110
وبالتالي فإن الطابع الصفري من السلسلة.

711
00:29:57,110 --> 00:29:57,610
أن من السهل.

712
00:29:57,610 --> 00:30:00,350
فعلنا ذلك في التشفير
قبل الاحالة أسابيع.

713
00:30:00,350 --> 00:30:05,310
ثم بمجرد أن تعرف أن أليس
الرسالة هي عاصمة A، يمكننا طرح

714
00:30:05,310 --> 00:30:08,160
إيقاف 65 أو رأس المال A نفسها،
أن يعطينا صفر.

715
00:30:08,160 --> 00:30:10,940
لذلك نحن نعرف الآن أن أليس ينتمي
في موقع الصفر.

716
00:30:10,940 --> 00:30:14,240
>> ونظرا مؤشر إلى هذه البيانات
هيكل، من نوع ما، وكم

717
00:30:14,240 --> 00:30:18,840
يستغرق مني أن العثور على الموقع
الصفر في مجموعة؟

718
00:30:18,840 --> 00:30:22,080
خطوة واحدة فقط، أليس كذلك حان الوقت ثابت
بسبب أننا الوصول العشوائي

719
00:30:22,080 --> 00:30:23,780
المقترح هو سمة من سمات صفيف.

720
00:30:23,780 --> 00:30:28,570
لذلك باختصار، ومعرفة ما مؤشر
اسم أليس هو، الذي هو، في

721
00:30:28,570 --> 00:30:32,610
هذه الحالة، هي A، أو دعونا لحل فقط
أن إلى الصفر، حيث B و C هو واحد هو

722
00:30:32,610 --> 00:30:34,900
اثنين، والاعتقاد أنه من أصل
هو وقت ثابت.

723
00:30:34,900 --> 00:30:38,510
أنا فقط يجب أن ننظر إلى الحرف الأول لها،
معرفة أين هو الصفر

724
00:30:38,510 --> 00:30:40,460
مجموعة هو أيضا وقت ثابت.

725
00:30:40,460 --> 00:30:42,140
لذلك من الناحية الفنية وهذا
مثل خطوتين الآن.

726
00:30:42,140 --> 00:30:43,330
ولكن هذا لا يزال مستمرا.

727
00:30:43,330 --> 00:30:46,880
لذلك نحن ندعو أن يا كبير واحد، لذلك قمنا
إدراج أليس في هذا الجدول في

728
00:30:46,880 --> 00:30:48,440
وقت ثابت.

729
00:30:48,440 --> 00:30:50,960
>> ولكن بطبيعة الحال، أنا يجري
السذاجة هنا، أليس كذلك؟

730
00:30:50,960 --> 00:30:53,240
ما إذا كان هناك أحد هارون في الصف؟

731
00:30:53,240 --> 00:30:53,990
أو أليسيا؟

732
00:30:53,990 --> 00:30:57,230
أو أي أسماء أخرى بدءا
A. أين نحن ذاهبون لوضع

733
00:30:57,230 --> 00:31:00,800
هذا الشخص، أليس كذلك؟

734
00:31:00,800 --> 00:31:03,420
أعني، الآن هناك ثلاثة فقط
الناس على الطاولة، وربما لذلك نحن

735
00:31:03,420 --> 00:31:07,490
يجب وضع هارون في الموقع
صفر واحد اثنين ثلاثة.

736
00:31:07,490 --> 00:31:09,480
>> الحق، وأنا قد وضعت وهنا.

737
00:31:09,480 --> 00:31:13,350
ولكن بعد ذلك، لو كنا في محاولة لادخال ديفيد في
هذه القائمة، حيث لا يذهب ديفيد؟

738
00:31:13,350 --> 00:31:15,170
الآن نظامنا يبدأ كسر
أسفل، أليس كذلك؟

739
00:31:15,170 --> 00:31:19,210
لأنه الآن ديفيد ينتهي هنا
إذا هارون هو في الواقع هنا.

740
00:31:19,210 --> 00:31:23,060
وحتى الآن هذه الفكرة كلها من وجود
هيكل البيانات النظيفة التي تعطينا

741
00:31:23,060 --> 00:31:28,010
الإدراج وقت ثابت لم يعد
وقت ثابت، لأن لدي ل

742
00:31:28,010 --> 00:31:31,240
تحقق، أوه، اللعنة، شخص بالفعل
في مكان أليس.

743
00:31:31,240 --> 00:31:35,320
>> اسمحوا لي أن تحقيق بقية هذه البيانات
هيكل، وتبحث عن مكان لوضع

744
00:31:35,320 --> 00:31:37,130
شخص مثل اسم هارون.

745
00:31:37,130 --> 00:31:39,390
وحتى هذا ايضا هو بداية
يستغرق وقتا طويلا الخطية.

746
00:31:39,390 --> 00:31:42,710
وعلاوة على ذلك، إذا كنت تريد الآن للعثور على
هارون في هذه البنية البيانات، وكنت

747
00:31:42,710 --> 00:31:45,430
تحقق، واسم هارون ليس هنا.

748
00:31:45,430 --> 00:31:47,960
من الناحية المثالية، وكنت أقول لهارون
ليس في بنية البيانات.

749
00:31:47,960 --> 00:31:51,530
ولكن إذا لم تبدأ افساح المجال لل
هارون حيث كان ينبغي أن يكون هناك D

750
00:31:51,530 --> 00:31:55,600
أو E، أنت، أسوأ الحالات، يجب أن تحقق
بنية البيانات بأكملها، في

751
00:31:55,600 --> 00:31:59,480
هذه الحالة تؤول إلى شيء
الخطية في حجم الجدول.

752
00:31:59,480 --> 00:32:00,920
>> لذلك كل الحق، وأنا سوف تصحيح هذا.

753
00:32:00,920 --> 00:32:04,200
المشكلة هنا هو ان كان لي
26 عناصر في هذه المجموعة.

754
00:32:04,200 --> 00:32:05,000
اسمحوا لي أن تغييره.

755
00:32:05,000 --> 00:32:06,010
يصيح.

756
00:32:06,010 --> 00:32:10,600
اسمحوا لي أن تغييره بحيث بدلا من كونها
حجم 26 في المجموع، لاحظ الجزء السفلي

757
00:32:10,600 --> 00:32:12,720
المؤشر سيتغير إلى n ناقص 1.

758
00:32:12,720 --> 00:32:16,610
إذا 26 ومن الواضح صغيرة جدا بالنسبة للبشر "
أسماء، لأن هناك الآلاف من

759
00:32:16,610 --> 00:32:20,830
أسماء العالم، دعونا جعل مجرد
في 100 أو 1،000 أو 10،000.

760
00:32:20,830 --> 00:32:22,960
دعونا فقط تخصيص الكثير من الفضاء.

761
00:32:22,960 --> 00:32:27,230
>> جيدا أن لا تقلل بالضرورة
احتمال أن لن يكون لدينا اثنين

762
00:32:27,230 --> 00:32:31,510
الناس مع أسماء تبدأ ب A، و
لذلك، كنت ذاهب الى محاولة لوضع A

763
00:32:31,510 --> 00:32:33,120
أسماء في موقع الصفر لا يزال.

764
00:32:33,120 --> 00:32:36,850
انهم لا تزال جارية لتصطدم، والتي
يعني أننا ما زلنا في حاجة الى حل لوضع

765
00:32:36,850 --> 00:32:41,020
أليس وهارون وأليسيا وغيرها
أسماء تبدأ ب A في أماكن أخرى.

766
00:32:41,020 --> 00:32:43,460
ولكن كم من مشكلة هو هذا؟

767
00:32:43,460 --> 00:32:46,870
ما هو احتمال أن كنت
يكون التصادم في البيانات

768
00:32:46,870 --> 00:32:48,240
هيكل من هذا القبيل؟

769
00:32:48,240 --> 00:32:52,570
>> حسنا، اسمحوا لي - سوف نعود
على هذا السؤال هنا.

770
00:32:52,570 --> 00:32:55,530
وننظر في كيفية قد
حلها أولا.

771
00:32:55,530 --> 00:32:58,480
اسمحوا لي سحب ما يصل هذا الاقتراح هنا.

772
00:32:58,480 --> 00:33:02,020
ما وصفنا فقط هو خوارزمية،
ودعا ارشادي الخطية

773
00:33:02,020 --> 00:33:05,030
التحقيق بموجبها، إذا حاولت إدراج
شيء هنا في هذه البيانات

774
00:33:05,030 --> 00:33:08,920
هيكل، وهو ما يسمى جدول تجزئة،
وليس هناك غرفة هناك، وكنت

775
00:33:08,920 --> 00:33:12,000
بحث حقا بنية البيانات
التحقق، وهذا هو المتاح؟

776
00:33:12,000 --> 00:33:13,430
هذا هو المتاح هو هذا المتاحة؟

777
00:33:13,430 --> 00:33:13,980
هل هذا متاح؟

778
00:33:13,980 --> 00:33:17,550
وعندما يكون أخيرا، قمت بإدراج
الاسم الذي أصلا

779
00:33:17,550 --> 00:33:19,370
في مكان آخر في هذا الموقع.

780
00:33:19,370 --> 00:33:23,360
ولكن في أسوأ الحالات، وبقعة فقط
قد يكون الجزء السفلي جدا من البيانات

781
00:33:23,360 --> 00:33:25,090
هيكل، في نهاية جدا من الصفيف.

782
00:33:25,090 --> 00:33:30,130
>> التحقيق الخطي بذلك، في أسوأ الحالات،
تؤول إلى خوارزمية خطية حيث

783
00:33:30,130 --> 00:33:34,500
هارون، إذا كان يحدث لإدراجها مشاركة
في هذا الهيكل البيانات، وقال انه قد

784
00:33:34,500 --> 00:33:39,540
تتصادم مع هذا الموقع الأول، ولكن
ثم تنتهي بسبب سوء الحظ في النهاية.

785
00:33:39,540 --> 00:33:43,940
وهذا ليس ثابت
الوقت الكأس المقدسة بالنسبة لنا.

786
00:33:43,940 --> 00:33:47,650
هذا النهج من إدراج العناصر في
ودعا هيكل تجزئة البيانات

787
00:33:47,650 --> 00:33:52,050
لا يبدو أن يكون جدول وقت ثابت
على الأقل ليس في حالة عامة.

788
00:33:52,050 --> 00:33:54,000
ويمكن ان تتحول الى شيء الخطية.

789
00:33:54,000 --> 00:33:56,970
>> لذلك ماذا لو عقدنا العزم الاصطدامات
بشكل مختلف إلى حد ما؟

790
00:33:56,970 --> 00:34:00,740
لذلك ليس هنا أكثر تطورا
النهج ما زال

791
00:34:00,740 --> 00:34:02,800
دعا جدول تجزئة.

792
00:34:02,800 --> 00:34:05,890
والبعثرة، بوصفها جانبا، ما
أعنيه هو الفهرس الذي

793
00:34:05,890 --> 00:34:07,070
التي أشرت إليها سابقا.

794
00:34:07,070 --> 00:34:09,810
لتجزئة شيء يمكن أن يكون
فكرت في كفعل.

795
00:34:09,810 --> 00:34:13,690
>> لذلك إذا كنت تجزئة أليس اسما،
وظيفة تجزئة، إذا جاز التعبير،

796
00:34:13,690 --> 00:34:14,710
يجب إرجاع الرقم.

797
00:34:14,710 --> 00:34:18,199
في هذه الحالة صفرا إذا كانت تنتمي في
موقع الصفر، واحد إذا كانت تنتمي في

798
00:34:18,199 --> 00:34:20,000
مكان واحد، وهكذا دواليك.

799
00:34:20,000 --> 00:34:24,360
حتى بلدي دالة البعثرة كانت حتى الآن
السوبر بسيطة، وتبحث فقط في

800
00:34:24,360 --> 00:34:26,159
الحرف الأول في اسم شخص ما.

801
00:34:26,159 --> 00:34:29,090
ولكن وظيفة تجزئة يأخذ كما
إدخال بعض قطعة من البيانات،

802
00:34:29,090 --> 00:34:30,210
سلسلة، وكثافة العمليات، أيا كان.

803
00:34:30,210 --> 00:34:32,239
ويبصق عادة عددا.

804
00:34:32,239 --> 00:34:35,739
وهذا العدد هو المكان أن البيانات
عنصر ينتمي في بنية البيانات

805
00:34:35,739 --> 00:34:37,800
المعروف هنا باسم جدول تجزئة.

806
00:34:37,800 --> 00:34:41,400
>> حتى مجرد حدسي، وهذا هو
سياق مختلف قليلا.

807
00:34:41,400 --> 00:34:44,170
هذا الواقع يشير إلى مثال
تشمل أعياد الميلاد، حيث

808
00:34:44,170 --> 00:34:46,850
قد يكون هناك العديد من مثل
31 يوما في الشهر.

809
00:34:46,850 --> 00:34:52,239
ولكن ما لم تقرر لهذا الشخص
القيام به في حالة حدوث تصادم؟

810
00:34:52,239 --> 00:34:55,304
السياق يجري الآن، وليس تصادم
أسماء، ولكن اصطدام أعياد الميلاد،

811
00:34:55,304 --> 00:35:00,760
إذا شخصين لديهم نفس عيد على
في 2 أكتوبر، على سبيل المثال.

812
00:35:00,760 --> 00:35:02,120
>> الطالب: [غير مسموع].

813
00:35:02,120 --> 00:35:05,010
>> سرور 1: نعم، لذلك لدينا هنا
والاستفادة من القوائم المرتبطة.

814
00:35:05,010 --> 00:35:07,830
بحيث يبدو بشكل مختلف قليلا
من نحن وجه في وقت سابق.

815
00:35:07,830 --> 00:35:10,790
ولكن يبدو أننا لدينا لمجموعة
على الجانب الأيسر.

816
00:35:10,790 --> 00:35:13,230
وهذا مؤشر واحد، لا ل
سبب معين.

817
00:35:13,230 --> 00:35:14,630
لكنه ما زال صفيف.

818
00:35:14,630 --> 00:35:16,160
انها مجموعة من المؤشرات.

819
00:35:16,160 --> 00:35:20,670
ولكل من هذه العناصر، كل واحد
هذه الدوائر أو مائلة - الشرطة المائلة

820
00:35:20,670 --> 00:35:23,970
تمثل فارغة - كل من هذه
يبدو المؤشرات يشير إلى

821
00:35:23,970 --> 00:35:25,730
ما بنية البيانات؟

822
00:35:25,730 --> 00:35:26,890
قائمة مرتبطة.

823
00:35:26,890 --> 00:35:30,530
>> حتى الآن لدينا القدرة على
رمز القرص الثابت في برنامجنا

824
00:35:30,530 --> 00:35:32,010
حجم الجدول.

825
00:35:32,010 --> 00:35:35,360
في هذه الحالة، ونحن نعرف أن هناك أبدا
أكثر من 31 يوما في الشهر.

826
00:35:35,360 --> 00:35:38,480
بجد ترميز قيمة مثل 31 هو
معقولة في هذا السياق.

827
00:35:38,480 --> 00:35:42,700
في سياق أسماء، والترميز الصعب
26 أليس كذلك الناس غير معقول

828
00:35:42,700 --> 00:35:46,340
أسماء تبدأ فقط مع، على سبيل المثال،
الأبجدية من A إلى Z. تنطوي

829
00:35:46,340 --> 00:35:50,180
>> يمكننا الالزام لهم جميعا في ذلك البيانات
هيكل طالما، عندما نحصل على

830
00:35:50,180 --> 00:35:55,330
الاصطدام، ونحن لا نضع أسماء هنا،
نحن نفكر بدلا من هذه الخلايا

831
00:35:55,330 --> 00:36:00,270
لا كسلاسل أنفسهم، ولكن كما
مؤشرات ل، على سبيل المثال، أليس.

832
00:36:00,270 --> 00:36:03,660
ثم أليس يمكن أن يكون مؤشر آخر
إلى اسم آخر بدءا

833
00:36:03,660 --> 00:36:06,150
A. وبوب يذهب في الواقع أكثر من هنا.

834
00:36:06,150 --> 00:36:10,850
>> وإذا كان هناك اسم آخر انطلاق
مع B، وقال انه ينتهي هنا.

835
00:36:10,850 --> 00:36:15,070
وهكذا كل من عناصر هذا
الجدول اثنين، إذا قمنا بتصميم هذا

836
00:36:15,070 --> 00:36:17,350
أكثر قليلا بذكاء -

837
00:36:17,350 --> 00:36:18,125
هيا -

838
00:36:18,125 --> 00:36:22,950
إذا قمنا بتصميم هذا أكثر من ذلك بقليل
بذكاء، وتصبح الآن في البيانات التكيفية

839
00:36:22,950 --> 00:36:27,720
الهيكل، حيث لا يوجد حد القرص الثابت
على مدى العديد من العناصر التي يمكن إدراجها

840
00:36:27,720 --> 00:36:30,700
في ذلك لأنه إذا كان لديك
اصطدام، فلا بأس.

841
00:36:30,700 --> 00:36:34,690
اذهبوا الى الامام وإلحاقها
ما رأيناه منذ قليل كان

842
00:36:34,690 --> 00:36:38,290
المعروفة باسم قائمة مرتبطة.

843
00:36:38,290 --> 00:36:39,690
>> حسنا دعونا نتوقف لمجرد لحظة.

844
00:36:39,690 --> 00:36:42,570
ما هو احتمال حدوث تصادم
في المقام الأول؟

845
00:36:42,570 --> 00:36:45,480
الحق، وربما أنا أكثر من التفكير، وربما
أنا أكثر من الهندسة هذه المشكلة،

846
00:36:45,480 --> 00:36:46,370
لأنك تعرف لماذا؟

847
00:36:46,370 --> 00:36:49,070
نعم، أنا يمكن أن تأتي مع التعسفي
أمثلة من على قمة رأسي مثل

848
00:36:49,070 --> 00:36:52,870
أليسون وهارون، ولكن في الواقع،
نظرا لتوزيع موحد لل

849
00:36:52,870 --> 00:36:56,990
المدخلات، وهذا هو بعض الملاحق العشوائية
إلى بنية البيانات، ما هو في الحقيقة

850
00:36:56,990 --> 00:36:58,580
احتمال حدوث تصادم؟

851
00:36:58,580 --> 00:37:01,670
كذلك تبين، انها في الواقع
عالية فائقة.

852
00:37:01,670 --> 00:37:03,850
اسمحوا لي أن تعميم هذا
المشكلة هي أن هذا.

853
00:37:03,850 --> 00:37:08,890
>> حتى في غرفة الطلاب ن CS50، ما هو
احتمال أن ما لا يقل عن

854
00:37:08,890 --> 00:37:11,010
اثنين من الطلاب في غرفة
لديهم نفس عيد الميلاد؟

855
00:37:11,010 --> 00:37:13,346
ولذلك لا يوجد ما. قليلة هوندي -

856
00:37:13,346 --> 00:37:16,790
200، 300 شخص والعديد من هنا
مئات من الأشخاص في المنزل اليوم.

857
00:37:16,790 --> 00:37:20,670
لذلك إذا أردت أن نسأل أنفسنا ما هو
احتمال شخصين

858
00:37:20,670 --> 00:37:23,930
في هذه الغرفة لها نفس عيد ميلاد،
يمكننا أن هذا الرقم.

859
00:37:23,930 --> 00:37:26,250
وأزعم في الواقع هناك نوعان من
الناس مع نفس عيد ميلاد.

860
00:37:26,250 --> 00:37:29,560
>> على سبيل المثال، لا أحد
لديك يحتفل اليوم؟

861
00:37:29,560 --> 00:37:31,340
بالأمس؟

862
00:37:31,340 --> 00:37:32,590
غدا؟

863
00:37:32,590 --> 00:37:35,980
كل الحق، لذلك يشعر وكأنني ذاهب
لديك للقيام بذلك 363 أو أكثر من ذلك

864
00:37:35,980 --> 00:37:39,500
مرات لمعرفة فعلا
إذا لدينا تصادم.

865
00:37:39,500 --> 00:37:42,350
أو أننا يمكن أن نفعل ذلك فقط رياضيا
بدلا من مضجر

866
00:37:42,350 --> 00:37:43,200
القيام بذلك.

867
00:37:43,200 --> 00:37:44,500
واقتراح ما يلي.

868
00:37:44,500 --> 00:37:48,740
>> لذلك أقترح أن نتمكن من نموذج ل
احتمال وجود شخصين

869
00:37:48,740 --> 00:37:55,320
عيد الميلاد نفسه بأنه احتمال من 1
ناقص احتمال وجود لا أحد

870
00:37:55,320 --> 00:37:56,290
في نفس تاريخ الميلاد.

871
00:37:56,290 --> 00:37:59,960
لذلك للحصول على هذا، وهذا هو مجرد
طريقة يتوهم كتابة هذا، ل

872
00:37:59,960 --> 00:38:03,090
أول شخص في الغرفة، وقال انه او انها
يمكن أن يكون أي واحد من الممكن

873
00:38:03,090 --> 00:38:07,370
أعياد الميلاد افتراض 365 يوما في السنة،
مع الاعتذار للأشخاص ذوي

874
00:38:07,370 --> 00:38:08,760
عيد ميلاد 29 فبراير.

875
00:38:08,760 --> 00:38:13,470
>> وبالتالي فإن أول شخص في هذه الغرفة هو حر
أن يكون أي عدد من أعياد الميلاد

876
00:38:13,470 --> 00:38:18,280
من الاحتمالات 365 بحيث
سنفعل ذلك 365 مقسوما على 365،

877
00:38:18,280 --> 00:38:18,990
التي هي واحدة.

878
00:38:18,990 --> 00:38:22,700
الشخص القادم في الغرفة، وإذا كان الهدف
هو تجنب الاصطدام، لا يمكن إلا أن

879
00:38:22,700 --> 00:38:26,460
يكون له أو لها عيد ميلاد على كيفية
أيام كثيرة ممكنة مختلفة؟

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
وبالتالي فإن فترة ولاية ثانية في هذا التعبير هو
القيام أساسا أن الرياضيات بالنسبة لنا

882
00:38:31,430 --> 00:38:33,460
عن طريق طرح قبالة يوم واحد ممكن.

883
00:38:33,460 --> 00:38:36,390
ثم في اليوم التالي، في اليوم التالي، و
اليوم التالي وصولا الى العدد الكلي

884
00:38:36,390 --> 00:38:38,100
من الناس في الغرفة.

885
00:38:38,100 --> 00:38:41,290
>> وإذا كنا ثم النظر، ثم ما هو
احتمال عدم وجود الجميع

886
00:38:41,290 --> 00:38:45,265
أعياد ميلاد فريدة من نوعها، ولكن مرة أخرى ناقص 1
ذلك، ما نحصل عليه هو تعبير

887
00:38:45,265 --> 00:38:47,810
التي يمكن أن هميا جدا
تبدو هذه.

888
00:38:47,810 --> 00:38:50,330
لكنه أكثر إثارة للاهتمام
للنظر في البصر.

889
00:38:50,330 --> 00:38:55,120
هذا هو مخطط حيث على المحور x هو
عدد الأشخاص في الغرفة، و

890
00:38:55,120 --> 00:38:56,180
عدد من أعياد الميلاد.

891
00:38:56,180 --> 00:38:59,840
على المحور الصادي هو احتمال
حدوث تصادم، شخصين

892
00:38:59,840 --> 00:39:01,230
لها نفس تاريخ الميلاد.

893
00:39:01,230 --> 00:39:05,020
>> والوجبات الجاهزة من هذا المنحنى هو
انه حالما تحصل على مثل 40

894
00:39:05,020 --> 00:39:11,110
الطلاب، وكنت حتى في احتمال 90٪
combinatorically اثنين

895
00:39:11,110 --> 00:39:13,550
نسمة أو أكثر وجود
في نفس تاريخ الميلاد.

896
00:39:13,550 --> 00:39:18,600
وبمجرد الحصول على مثل 58 شخصا انها
ما يقرب من 100٪ من فرصة للاثنين

897
00:39:18,600 --> 00:39:21,310
الناس في الغرفة ستكون لدينا ل
نفس تاريخ الميلاد، على الرغم من هناك

898
00:39:21,310 --> 00:39:26,650
365 أو 366 الدلاء ممكن، و
فقط 58 شخصا في الغرفة.

899
00:39:26,650 --> 00:39:29,900
فقط إحصائيا أنت من المحتمل أن
الحصول على الاصطدامات، التي في القصير

900
00:39:29,900 --> 00:39:31,810
يحفز هذا النقاش.

901
00:39:31,810 --> 00:39:35,890
أنه حتى لو حصلنا على يتوهم هنا، و
بدء وجود هذه السلاسل، ونحن ما زلنا

902
00:39:35,890 --> 00:39:36,950
ستكون لدينا الاصطدامات.

903
00:39:36,950 --> 00:39:42,710
>> بحيث يطرح السؤال، ما هو
تكلفة ممارسة الإدراج والحذف

904
00:39:42,710 --> 00:39:44,850
في بنية بيانات من هذا القبيل؟

905
00:39:44,850 --> 00:39:46,630
كذلك اسمحوا لي أن أقترح -

906
00:39:46,630 --> 00:39:51,570
واسمحوا لي أن أعود إلى الشاشة أكثر
هنا - اذا كان لدينا العناصر ن في

907
00:39:51,570 --> 00:39:56,330
قائمة، لذلك إذا كنا نحاول أن إدراج
ن العناصر، وليس لدينا

908
00:39:56,330 --> 00:39:58,050
كيف العديد من الدلاء مجموع؟

909
00:39:58,050 --> 00:40:03,450
دعنا نقول 31 مجموع الدلاء
في حالة أعياد الميلاد.

910
00:40:03,450 --> 00:40:09,240
ما هو الحد الأقصى لطول واحد
من المحتمل أن تكون هذه السلاسل؟

911
00:40:09,240 --> 00:40:12,670
>> إذا مرة أخرى هناك 31 ممكن
أعياد الميلاد في شهر معين.

912
00:40:12,670 --> 00:40:14,580
ونحن مجرد التثاقل الجميع -

913
00:40:14,580 --> 00:40:15,580
في الواقع هذا هو مثال غبي.

914
00:40:15,580 --> 00:40:16,960
دعونا نفعل 26 بدلا من ذلك.

915
00:40:16,960 --> 00:40:20,890
لذلك اذا كانت لديك أسماء الأشخاص الذين فعلا
تبدأ من خلال Z، مما يعطي

916
00:40:20,890 --> 00:40:22,780
لنا 26 الاحتمالات.

917
00:40:22,780 --> 00:40:25,920
ونستخدمه بنية بيانات مثل
واحد رأينا للتو، حيث لدينا

918
00:40:25,920 --> 00:40:30,210
مجموعة من المؤشرات، كل منها
نقاط لقائمة مرتبطة حيث

919
00:40:30,210 --> 00:40:32,360
القائمة الأولى هو الجميع
مع اسم أليس.

920
00:40:32,360 --> 00:40:35,770
القائمة الثانية هو كل مع
تسمية تبدأ ب A، بدءا

921
00:40:35,770 --> 00:40:36,980
مع B، وهكذا دواليك.

922
00:40:36,980 --> 00:40:41,020
>> ما هو طول المحتمل لكل من
تلك القوائم إذا افترضنا نظيفة جميلة

923
00:40:41,020 --> 00:40:45,410
توزيع أسماء من A إلى Z
عبر بنية بيانات كاملة؟

924
00:40:45,410 --> 00:40:50,210
هناك ن الناس في بنية البيانات
مقسوما على 26، لو انهم لطيف

925
00:40:50,210 --> 00:40:52,110
انتشرت على كامل
هيكل البيانات.

926
00:40:52,110 --> 00:40:54,970
وبالتالي فإن طول كل من هذه
وتنقسم سلاسل ن بنسبة 26.

927
00:40:54,970 --> 00:40:57,380
ولكن في تدوين يا كبير، ما هو؟

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
ما هو هذا حقا؟

930
00:41:02,440 --> 00:41:04,150
ذلك انها حقا مجرد ن، أليس كذلك؟

931
00:41:04,150 --> 00:41:06,620
لأننا قلنا في الماضي،
هتاف اشمئزاز أن تقوم بتقسيم بنسبة 26.

932
00:41:06,620 --> 00:41:08,710
نعم، في واقع الأمر هو أسرع.

933
00:41:08,710 --> 00:41:12,720
لكن من الناحية النظرية، انها ليست الأساس
كل ذلك بشكل أسرع.

934
00:41:12,720 --> 00:41:16,040
>> لذلك نحن لا يبدو أن كل ذلك بكثير
هذا أقرب إلى الكأس المقدسة.

935
00:41:16,040 --> 00:41:17,750
في الواقع، هذه هي المرة الخطية فقط.

936
00:41:17,750 --> 00:41:20,790
هيك، في هذه المرحلة، لماذا لا نحن
مجرد استخدام لائحة واحدة ضخمة مرتبطة؟

937
00:41:20,790 --> 00:41:23,510
فلماذا لا نستخدم واحدة فقط ضخمة
مجموعة لتخزين أسماء

938
00:41:23,510 --> 00:41:25,010
الجميع في الغرفة؟

939
00:41:25,010 --> 00:41:28,280
حسنا، لا يزال هناك شيء
مقنعة حول جدول التجزئة؟

940
00:41:28,280 --> 00:41:30,810
لا يزال هناك شيء مقنعة
حول بنية بيانات

941
00:41:30,810 --> 00:41:33,940
يشبه هذا؟

942
00:41:33,940 --> 00:41:35,182
هذا.

943
00:41:35,182 --> 00:41:37,050
>> الطالب: [غير مسموع].

944
00:41:37,050 --> 00:41:39,840
>> سرور 1: الحق، ومرة ​​أخرى لو كان مجرد
خوارزمية الزمن الخطي، و

945
00:41:39,840 --> 00:41:42,780
هيكل البيانات في الوقت الخطية، لماذا لا استطيع
مجرد تخزين اسم الجميع في كبيرة

946
00:41:42,780 --> 00:41:44,210
مجموعة، أو في قائمة مرتبطة الكبيرة؟

947
00:41:44,210 --> 00:41:47,010
والتوقف عن CS ذلك أصعب بكثير
مما يجب أن يكون؟

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
ما هو مقنعة حول هذا الموضوع، حتى
على الرغم من أنني خدش بها؟

950
00:41:53,190 --> 00:41:54,930
>> الطالب: [غير مسموع].

951
00:41:54,930 --> 00:41:57,040
>> سرور 1: الإدراج لا؟

952
00:41:57,040 --> 00:41:58,140
لم يعد مكلفا.

953
00:41:58,140 --> 00:42:03,390
لذلك الإدراج المحتمل يمكن أن تزال
يكون الوقت قد حان ثابتة، حتى إذا كانت البيانات الخاصة بك

954
00:42:03,390 --> 00:42:07,910
هيكل يشبه هذا، مجموعة من
مؤشرات، كل منها لافتا في

955
00:42:07,910 --> 00:42:09,550
يحتمل أن تكون قائمة مرتبطة.

956
00:42:09,550 --> 00:42:15,220
كيف يمكن لكم تحقيق مستمر
الوقت الإدراج الأسماء؟

957
00:42:15,220 --> 00:42:16,280
عصا في الجبهة، أليس كذلك؟

958
00:42:16,280 --> 00:42:19,290
>> إذا كنا نضحي هدف التصميم من
في وقت سابق، حيث كنا نريد للحفاظ على

959
00:42:19,290 --> 00:42:22,650
اسم الجميع، على سبيل المثال، فرزها،
أو كل الأرقام على خشبة المسرح فرزها،

960
00:42:22,650 --> 00:42:25,020
لنفترض أن لدينا
قائمة مرتبطة غير مصنفة.

961
00:42:25,020 --> 00:42:29,960
يكلف فقط لنا واحدة أو خطوتين،
مثل في حالة وبن بريان

962
00:42:29,960 --> 00:42:32,750
في وقت سابق، لإدراج عنصر في
في بداية القائمة.

963
00:42:32,750 --> 00:42:36,090
لذلك إذا كنا لا يهتمون فرز جميع
أسماء تبدأ ب A أو كل

964
00:42:36,090 --> 00:42:39,660
أسماء تبدأ ب B، لا يزال في وسعنا
تحقيق مستمر الإدراج الوقت.

965
00:42:39,660 --> 00:42:43,900
أبحث الآن عن أليس أو بوب أو أي اسم
لا يزال أكثر عموما ماذا؟

966
00:42:43,900 --> 00:42:48,100
انها يا كبير من ن مقسوما على 26، في
الحالة المثالية حيث الجميع بشكل موحد

967
00:42:48,100 --> 00:42:51,190
وزعت، حيث هناك العديد من A ل
كما أن هناك Z، والذي هو على الارجح

968
00:42:51,190 --> 00:42:52,220
غير واقعي.

969
00:42:52,220 --> 00:42:53,880
ولكن هذا لا يزال الخطية.

970
00:42:53,880 --> 00:42:57,120
>> ولكن هنا، نعود إلى نقطة
من مقارب تدوين كائن

971
00:42:57,120 --> 00:42:58,600
صحيح من الناحية النظرية.

972
00:42:58,600 --> 00:43:02,960
ولكن في العالم الحقيقي، وإذا كنت تدعي أن
برنامجي تستطيع ان تفعل شيئا 26 مرة

973
00:43:02,960 --> 00:43:06,210
أسرع من يدكم، والذي برنامج
انت ذاهب الى يفضلون استخدام؟

974
00:43:06,210 --> 00:43:09,660
لك أو الألغام، والتي
هو 26 مرات أسرع؟

975
00:43:09,660 --> 00:43:14,320
واقعيا، الشخص الذي هو 26
مرات أسرع، حتى لو كان نظريا

976
00:43:14,320 --> 00:43:18,790
خوارزميات لدينا تعمل في نفس
مقارب الوقت الحالي.

977
00:43:18,790 --> 00:43:20,940
>> اسمحوا لي أن أقترح مختلفة
الحل تماما.

978
00:43:20,940 --> 00:43:24,380
وإذا كان هذا لا ضربة عقلك،
نحن من هياكل البيانات.

979
00:43:24,380 --> 00:43:27,420
لذلك هذا هو عليه TRIE -

980
00:43:27,420 --> 00:43:28,520
نوع من اسم غبي.

981
00:43:28,520 --> 00:43:32,880
انها تأتي من الاسترجاع، وكلمة
هو مكتوبة TRIE، ر، ص، ط، ه، وذلك بسبب

982
00:43:32,880 --> 00:43:34,450
استرجاع بالطبع يبدو وكأنه TRIE.

983
00:43:34,450 --> 00:43:36,580
ولكن هذا التاريخ
من TRIE كلمة.

984
00:43:36,580 --> 00:43:40,980
>> لذلك TRIE هو في الواقع نوع من شجرة،
وكما انها تلعب على تلك الكلمة.

985
00:43:40,980 --> 00:43:46,330
وعلى الرغم من أنك لا تستطيع رؤية ذلك تماما
مع هذا التصور، وهو TRIE هو

986
00:43:46,330 --> 00:43:50,790
شجرة منظم، وكأنه شجرة العائلة مع
سلف واحد في الجزء العلوي والكثير

987
00:43:50,790 --> 00:43:54,530
من الأحفاد وأبناء الأحفاد
كما يترك في القاع.

988
00:43:54,530 --> 00:43:58,100
ولكن كل عقدة في TRIE هو صفيف.

989
00:43:58,100 --> 00:44:00,680
وانها في صفيف - ودعونا
تبسيط للحظة واحدة - انها

990
00:44:00,680 --> 00:44:04,600
مجموعة، في هذه الحالة، من حجم 26، حيث
كل عقدة هو مرة أخرى مجموعة من حجم

991
00:44:04,600 --> 00:44:09,000
26، حيث العنصر الصفري في ذلك
يمثل مجموعة A، وآخر

992
00:44:09,000 --> 00:44:11,810
عنصر في كل هذه
يمثل مجموعة Z.

993
00:44:11,810 --> 00:44:15,520
>> لذلك أقترح، إذن، أن هذه البيانات
هيكل، المعروف باسم TRIE، يمكن أن يكون

994
00:44:15,520 --> 00:44:17,600
تستخدم أيضا لتخزين الكلمات.

995
00:44:17,600 --> 00:44:21,740
شاهدنا قبل لحظة كيف يمكننا تخزين
الكلمات، أو في هذه الحالة أسماء، ونحن

996
00:44:21,740 --> 00:44:25,440
ورأى في وقت سابق كيف يمكننا تخزين أرقام،
ولكن إذا ركزنا على أسماء أو سلاسل

997
00:44:25,440 --> 00:44:27,460
هنا، لاحظ ما هو مثير للاهتمام.

998
00:44:27,460 --> 00:44:32,210
أزعم أن الاسم هو ماكسويل
داخل هذه البنية البيانات.

999
00:44:32,210 --> 00:44:33,730
أين ترى ماكسويل؟

1000
00:44:33,730 --> 00:44:35,140
>> الطالب: [غير مسموع].

1001
00:44:35,140 --> 00:44:36,240
>> سرور 1: على اليسار.

1002
00:44:36,240 --> 00:44:39,910
فما مثيرة للاهتمام مع هذه البيانات
هيكل هو بدلا من مخزن

1003
00:44:39,910 --> 00:44:46,200
سلسلة M-A-X-W-E-L-L مائل الصفر، كل
متاخم، ما كنت تفعل بدلا من ذلك

1004
00:44:46,200 --> 00:44:46,890
فيما يلي.

1005
00:44:46,890 --> 00:44:50,510
إذا كان هذا هو TRIE مثل هيكل البيانات،
كل من العقد الذي هو مرة أخرى صفيف،

1006
00:44:50,510 --> 00:44:54,650
وتريد تخزين ماكسويل، لأول مرة
المؤشر وذلك عقدة الجذر، لذلك

1007
00:44:54,650 --> 00:44:57,810
في الكلام، وأعلى العقدة،
في موقع M، الحق، لذلك

1008
00:44:57,810 --> 00:44:59,160
تقريبا في الوسط.

1009
00:44:59,160 --> 00:45:03,740
ثم من هناك، كنت تتبع
مؤشر إلى العقد التابعة، إذا جاز التعبير.

1010
00:45:03,740 --> 00:45:06,150
ذلك بمعنى شجرة العائلة،
كنت متابعته النزولي.

1011
00:45:06,150 --> 00:45:09,030
والتي تقودك إلى عقدة أخرى
على اليسار هناك، وهو

1012
00:45:09,030 --> 00:45:10,540
مجرد مجموعة أخرى.

1013
00:45:10,540 --> 00:45:14,710
>> ثم إذا كنت ترغب في تخزين ماكسويل،
تجد المؤشر الذي يمثل

1014
00:45:14,710 --> 00:45:16,430
A، الذي هو هذا واحد هنا.

1015
00:45:16,430 --> 00:45:17,840
ثم تذهب إلى العقدة المقبل.

1016
00:45:17,840 --> 00:45:20,100
وإشعار - وهذا هو السبب للصورة
قليلا خداع -

1017
00:45:20,100 --> 00:45:21,990
هذه العقدة تبدو فائقة صغيرة.

1018
00:45:21,990 --> 00:45:26,050
ولكن على يمين هذا هو Y وZ.
مجرد واقتطاعها المؤلف

1019
00:45:26,050 --> 00:45:27,630
الصورة بحيث كنت في الواقع
رؤية الأشياء.

1020
00:45:27,630 --> 00:45:30,400
خلاف هذه الصورة
أن تكون واسعة بشكل كبير.

1021
00:45:30,400 --> 00:45:36,180
حتى الآن أنت في مكان المؤشر X، ثم
W، ثم E، ثم لام، ثم لام ثم ما هو

1022
00:45:36,180 --> 00:45:37,380
هذا الفضول؟

1023
00:45:37,380 --> 00:45:41,250
>> حسنا، إذا نحن باستخدام هذا النوع من جديدة
تأخذ على كيفية تخزين سلسلة في

1024
00:45:41,250 --> 00:45:44,500
هيكل البيانات، لا تزال تحتاج ل
تحقق أساسا قبالة في البيانات

1025
00:45:44,500 --> 00:45:47,250
هيكل أن كلمة ينتهي هنا.

1026
00:45:47,250 --> 00:45:50,830
وبعبارة أخرى، كل هذه العقد
لديه على نحو ما أن نتذكر أننا

1027
00:45:50,830 --> 00:45:53,500
يتبع في الواقع كل هذه المؤشرات
ويتركون قليلا

1028
00:45:53,500 --> 00:45:58,370
كسرة خبز في أسفل هنا من هذا
هيكل للإشارة إلى M-A-X-W-E-L-L هو

1029
00:45:58,370 --> 00:46:00,230
بالفعل في هذا الهيكل البيانات.

1030
00:46:00,230 --> 00:46:02,040
>> ولذا فإننا قد نفعل ذلك على النحو التالي.

1031
00:46:02,040 --> 00:46:06,810
كل من العقد في الصورة نحن فقط
رأى واحد، مجموعة من حجم 27.

1032
00:46:06,810 --> 00:46:10,550
وانها الآن 27، وذلك لأن في ع تعيين ستة،
وسوف نقدم في الواقع كنت الفاصلة العليا،

1033
00:46:10,550 --> 00:46:13,590
ولذا فإننا يمكن أن يكون لها أسماء مثل أورايلي
وغيرهم مع الفواصل العليا.

1034
00:46:13,590 --> 00:46:14,820
ولكن نفس الفكرة.

1035
00:46:14,820 --> 00:46:17,710
كل من هذه العناصر في
نقاط صفيف إلى البنية

1036
00:46:17,710 --> 00:46:19,320
عقدة، حتى مجرد عقدة.

1037
00:46:19,320 --> 00:46:21,430
لذلك هذا هو تذكرنا جدا
من قائمة مرتبطة لدينا.

1038
00:46:21,430 --> 00:46:24,550
>> ثم لدي منطقية، والتي سوف أكون
كلمة الدعوة، الذي هو مجرد ستكون

1039
00:46:24,550 --> 00:46:29,120
صحيح إذا كان كلمة ينتهي عند هذا
عقدة في الشجرة.

1040
00:46:29,120 --> 00:46:32,870
أنها تمثل نحو فعال قليلا
مثلث شاهدنا قبل لحظة.

1041
00:46:32,870 --> 00:46:37,190
إذا كان الأمر كذلك كلمة ينتهي عند تلك العقدة في
شجرة، وهذا المجال الكلمة يكون صحيحا،

1042
00:46:37,190 --> 00:46:41,990
الذي هو التحقق من الناحية المفاهيمية، أو
نحن رسم هذا المثلث، نعم هناك

1043
00:46:41,990 --> 00:46:44,080
هي كلمة هنا.

1044
00:46:44,080 --> 00:46:45,120
>> لذلك هذا هو TRIE.

1045
00:46:45,120 --> 00:46:48,540
والسؤال المطروح الآن هو، ما
حان الوقت لتشغيل؟

1046
00:46:48,540 --> 00:46:49,930
هو يا كبير من ن؟

1047
00:46:49,930 --> 00:46:51,410
هو شيء آخر؟

1048
00:46:51,410 --> 00:46:57,330
حسنا، إذا كان لديك ن الأسماء في هذه البيانات
هيكل، ماكسويل كونها واحدة فقط من

1049
00:46:57,330 --> 00:47:02,330
لهم، ما هو وقت تشغيل
إدراج أو إيجاد ماكسويل؟

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
ما هو الوقت تشغيل
ادخال ماكسويل؟

1052
00:47:09,050 --> 00:47:11,740
إذا كان هناك ن أسماء أخرى
بالفعل في الجدول؟

1053
00:47:11,740 --> 00:47:12,507
نعم؟

1054
00:47:12,507 --> 00:47:15,429
>> الطالب: [غير مسموع].

1055
00:47:15,429 --> 00:47:17,550
>> سرور 1: نعم، انها طول
من اسم، أليس كذلك؟

1056
00:47:17,550 --> 00:47:24,420
حتى M-A-X-W-ه-L-L لذلك يشعر مثل هذا
الخوارزمية O كبيرة من سبعة.

1057
00:47:24,420 --> 00:47:26,580
الآن، بطبيعة الحال، واسم
سوف تختلف في الطول.

1058
00:47:26,580 --> 00:47:27,380
ربما انها اسم قصير.

1059
00:47:27,380 --> 00:47:28,600
ربما انها اسم لفترة أطول.

1060
00:47:28,600 --> 00:47:33,390
ولكن ما هو المفتاح هنا هو أن
انها رقم ثابت.

1061
00:47:33,390 --> 00:47:36,810
وربما انها ليست ثابتة حقا،
ولكن والله لو واقعيا، في

1062
00:47:36,810 --> 00:47:41,570
القاموس، هناك على الارجح بعض الحد
على عدد من الرسائل في

1063
00:47:41,570 --> 00:47:43,820
اسم الشخص في بلد معين.

1064
00:47:43,820 --> 00:47:46,940
>> وهكذا يمكننا أن نفترض أن
قيمة ثابت.

1065
00:47:46,940 --> 00:47:47,750
أنا لا أعرف ما هو عليه.

1066
00:47:47,750 --> 00:47:50,440
هو على الأرجح أكبر من
نعتقد أنه هو.

1067
00:47:50,440 --> 00:47:52,720
لأن هناك دائما بعض الزاوية
الحال مع اسم طويل مجنون.

1068
00:47:52,720 --> 00:47:56,360
لذلك دعونا نسميها ك، لكنه ما زال ل
ثابت يفترض، لأن كل

1069
00:47:56,360 --> 00:48:00,190
اسم في العالم، على الأقل في
بلد معين، هو أن طول أو

1070
00:48:00,190 --> 00:48:01,780
أقصر، لذلك فمن ثابتة.

1071
00:48:01,780 --> 00:48:04,490
ولكن عندما قلنا شيء كبير
يا من قيمة ثابتة، ما أن

1072
00:48:04,490 --> 00:48:07,760
أي ما يعادل حقا ل؟

1073
00:48:07,760 --> 00:48:10,420
هذا هو في الحقيقة نفس الشيء
قوله وقت ثابت.

1074
00:48:10,420 --> 00:48:11,530
>> نحن الآن نوع من الغش، أليس كذلك؟

1075
00:48:11,530 --> 00:48:15,340
نحن نوع من الاستفادة من بعض النظريات
هنا لأقول ذلك جيدا، هو أمر ك

1076
00:48:15,340 --> 00:48:17,450
نظام عادل حقا لأحد،
وحان الوقت مستمر.

1077
00:48:17,450 --> 00:48:18,200
ولكنه في الواقع.

1078
00:48:18,200 --> 00:48:22,550
لأن الفكرة الرئيسية هنا هي أن
اذا كان لدينا ن أسماء بالفعل في هذا

1079
00:48:22,550 --> 00:48:26,010
بنية البيانات، ونحن ادخال ماكسويل،
هو مقدار الوقت الذي يستغرقه لنا ل

1080
00:48:26,010 --> 00:48:29,530
إدراج ماكسويل على جميع المتضررين
من قبل كيف العديد من الأشخاص الآخرين

1081
00:48:29,530 --> 00:48:31,100
هي في بنية البيانات؟

1082
00:48:31,100 --> 00:48:31,670
لا يبدو أن يكون.

1083
00:48:31,670 --> 00:48:36,280
إذا كان لدي أكثر من العناصر مليار لهذا
TRIE، ثم قم بإدراج ماكسويل، هو

1084
00:48:36,280 --> 00:48:38,650
وقال انه في كل المتضررين؟

1085
00:48:38,650 --> 00:48:39,050
لا.

1086
00:48:39,050 --> 00:48:42,950
وهذا على عكس أي من البيانات اليوم
هياكل رأيناه حتى الآن، حيث

1087
00:48:42,950 --> 00:48:46,820
وقت تشغيل خوارزمية الخاص بك هو
مستقلة تماما عن كم

1088
00:48:46,820 --> 00:48:51,430
الاشياء هي أو لم تكن
في ذلك بنية البيانات.

1089
00:48:51,430 --> 00:48:54,650
>> وحتى مع هذا يتيح لك الآن هو
فرصة للع مجموعة الست، والتي سوف

1090
00:48:54,650 --> 00:48:58,310
مرة أخرى تنطوي على تنفيذ بنفسك
المدقق الإملائي، والقراءة في 150،000

1091
00:48:58,310 --> 00:49:01,050
الكلمات، وأفضل طريقة لتخزين أن
ليست واضحة بالضرورة.

1092
00:49:01,050 --> 00:49:04,030
وعلى الرغم من أنني كنت تطمح للعثور على
الكأس المقدسة، وأنا لا

1093
00:49:04,030 --> 00:49:05,330
يدعون أن TRIE هو.

1094
00:49:05,330 --> 00:49:09,810
في الواقع، قد جدول تجزئة بشكل جيد للغاية
أن يكون أكثر كفاءة بكثير.

1095
00:49:09,810 --> 00:49:10,830
ولكن تلك ليست سوى -

1096
00:49:10,830 --> 00:49:14,620
هذا مجرد واحد من قرارات التصميم
سيكون لديك لجعل.

1097
00:49:14,620 --> 00:49:18,920
>> ولكن في الختام دعونا نلقي 50 أو نحو ذلك
ثانية لإلقاء نظرة خاطفة على ما الأكاذيب

1098
00:49:18,920 --> 00:49:22,190
قبل الاسبوع المقبل وما بعده ونحن الانتقالية
من سطر الأوامر هذا

1099
00:49:22,190 --> 00:49:26,220
العالم إذا برامج مئوية إلى الأشياء على شبكة الإنترنت
ومقرها لغات مثل PHP و

1100
00:49:26,220 --> 00:49:30,350
جافا سكريبت والإنترنت نفسها،
بروتوكولات HTTP مثل التي كنت قد

1101
00:49:30,350 --> 00:49:32,870
مفروغا منه لسنوات
الآن، وكتابة معظم كل

1102
00:49:32,870 --> 00:49:34,440
اليوم، ربما، أو ينظر إليها.

1103
00:49:34,440 --> 00:49:37,420
ونحن سوف تبدأ في قشر العودة
طبقات من ما هو الانترنت.

1104
00:49:37,420 --> 00:49:40,650
وما هي التعليمات البرمجية التي
وراء الأدوات اليوم.

1105
00:49:40,650 --> 00:49:43,230
حتى 50 ثانية من هذه دعابة هنا.

1106
00:49:43,230 --> 00:49:46,570
أنا أعطيك ووريورز من صافي.

1107
00:49:46,570 --> 00:49:51,370
>> [تشغيل الفيديو]

1108
00:49:51,370 --> 00:49:56,764
>> وقال انه جاء مع-رسالة.

1109
00:49:56,764 --> 00:50:00,687
مع كل بروتوكول بلده.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
وقال انه جاء إلى عالم من الجدران النارية القاسية،
أجهزة التوجيه غير مكترثة، والأخطار بعيدة

1112
00:50:19,780 --> 00:50:22,600
أسوأ من الموت.

1113
00:50:22,600 --> 00:50:23,590
انه سريع.

1114
00:50:23,590 --> 00:50:25,300
انه قوي.

1115
00:50:25,300 --> 00:50:27,700
انه TCPIP.

1116
00:50:27,700 --> 00:50:30,420
وانه حصل على عنوانك.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
المحاربين من صافي.

1119
00:50:34,590 --> 00:50:35,290
>> [END تشغيل الفيديو]

1120
00:50:35,290 --> 00:50:38,070
>> سرور 1: هذا هو كيف يمكن للإنترنت
يجب العمل اعتبارا من الاسبوع المقبل.

1121
00:50:38,070 --> 00:50:40,406