1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID مالان: حسنا. 3 00:00:12,250 --> 00:00:13,860 نرحب مرة أخرى إلى CS50. 4 00:00:13,860 --> 00:00:16,190 هذا هو بداية الاسبوع 8. 5 00:00:16,190 --> 00:00:21,320 ونذكر بأن المشكلة انتهت بتعيين 5 مع القليل من التحدي. 6 00:00:21,320 --> 00:00:25,210 حتى على افتراض انك تعافى كل الكلمات تدريس الزملاء والصور، CA في 7 00:00:25,210 --> 00:00:30,480 في ملف card.raw، كنت مؤهلا لتجد الآن كل من هؤلاء الناس، و 8 00:00:30,480 --> 00:00:34,510 الفائز المحظوظ واحد سوف المشي في المنزل مع واحد من هذه الأشياء، وحركة قفزة 9 00:00:34,510 --> 00:00:37,450 الجهاز الذي يمكنك استخدامه للنهائي المشاريع، على سبيل المثال. 10 00:00:37,450 --> 00:00:39,860 >> هذا، في كل عام، ويؤدي إلى قليلا من القشعريرة. 11 00:00:39,860 --> 00:00:43,480 وذلك ما اعتقدت به هو حصة معك بعض الملاحظات التي لديها 12 00:00:43,480 --> 00:00:47,370 ذهب ذهابا وإيابا على قائمة الموظفين في وقت متأخر. 13 00:00:47,370 --> 00:00:51,110 على سبيل المثال، فقط الليلة الماضية، واقتبس نهاية الاقتباس، من أحد الموظفين 14 00:00:51,110 --> 00:00:55,000 أعضاء، "أنا كان مجرد ضربة طالب على بابي لالتقاط صورة معي. 15 00:00:55,000 --> 00:00:59,020 الملاحقون، وأنا أقول لك. "كتبت قبالة صفية إلى حد ما ثم انتقلنا 16 00:00:59,020 --> 00:01:02,830 على ل، ساعة أو نحو ذلك في وقت لاحق، "كان لي طالب ينتظرني بعد القسم 17 00:01:02,830 --> 00:01:06,080 وكان لديه كل من أسمائنا والصور على بعض ورقة من الورق. "حسنا. 18 00:01:06,080 --> 00:01:09,230 لذلك نظمت، ولكن ليس كل ما زاحف حتى الآن. 19 00:01:09,230 --> 00:01:12,520 >> ثم، وقال "كنت خارج المدينة في نهاية هذا الاسبوع، وعندما عدت، كان هناك واحد في 20 00:01:12,520 --> 00:01:12,630 لي 21 00:01:12,630 --> 00:01:16,740 غرفة نوم ". [ضحك] 22 00:01:16,740 --> 00:01:20,410 DAVID مالان: اقتباس التالي من الموظفين عضو "، وجاء الطالب إلى بيتي في 23 00:01:20,410 --> 00:01:25,330 سمرفيل في 04:00 صباح اليوم. "التالي الموظفين، "وصلت إلى فندقي في سان 24 00:01:25,330 --> 00:01:30,016 فرانسيسكو وطالب كان ينتظر لي في بهو الفندق مع ثلاثة DSLRS ". 25 00:01:30,016 --> 00:01:31,510 نوع الكاميرا. 26 00:01:31,510 --> 00:01:34,980 "أنا لست حتى على الموظفين في هذا الفصل الدراسي، ولكن كسرت طالب في بيتي هذا 27 00:01:34,980 --> 00:01:40,480 الصباح وسجلت كل شيء مع جوجل الزجاج. "ثم أخيرا، 28 00:01:40,480 --> 00:01:43,650 "كان 12 شخصا على الاقل بفارغ الصبر في انتظار بالنسبة لي عندما خرجت من بلدي 29 00:01:43,650 --> 00:01:44,800 ليموزين، وبعد ذلك 30 00:01:44,800 --> 00:01:46,970 استيقظت. "حسنا. 31 00:01:46,970 --> 00:01:57,690 حتى بين الصور، كما كنت قد أذكر، وهذا الزميل هنا، من أنت 32 00:01:57,690 --> 00:02:01,850 قد تعرف باسم ميلو الموز، الذي يعيش مع لورين كارفاليو، رؤوسنا 33 00:02:01,850 --> 00:02:02,905 تدريس زميل. 34 00:02:02,905 --> 00:02:05,170 ميلو، ميلو، وتأتي هنا الصبي. 35 00:02:05,170 --> 00:02:06,320 ميلو. 36 00:02:06,320 --> 00:02:08,650 ميلو. 37 00:02:08,650 --> 00:02:12,230 فتذكروا، وقال انه يرتدي جوجل الزجاج، لذلك سنوضح لك كل هذا بعد. 38 00:02:12,230 --> 00:02:16,190 لذلك هذا هو ميلو إذا كنت ترغب في التقاط صورة معه بعد ذلك. 39 00:02:16,190 --> 00:02:18,240 إذا كنت ترغب في أن ينظر خارجا في الجمهور هناك. 40 00:02:18,240 --> 00:02:19,430 موافق. 41 00:02:19,430 --> 00:02:20,200 هذا هو لقطات جيدة. 42 00:02:20,200 --> 00:02:22,556 حسنا، ميلو الموز. 43 00:02:22,556 --> 00:02:23,941 أوه، لا تفعل ذلك. 44 00:02:23,941 --> 00:02:29,020 >> [ضحك] 45 00:02:29,020 --> 00:02:29,470 >> موافق. 46 00:02:29,470 --> 00:02:34,550 حتى كلمة واحدة ثم على ما ينتظرنا في المستقبل، لأنه كما أن نبدأ في الانتقال، 47 00:02:34,550 --> 00:02:38,410 هذا الأسبوع تحديدا، من C في بيئة سطر الأوامر لPHP و 48 00:02:38,410 --> 00:02:42,720 جافا سكريبت وSQL و HTML و CSS في بيئة على شبكة الإنترنت، ونحن سوف تكون 49 00:02:42,720 --> 00:02:44,490 تجهيز لكم مع كل مزيد من المعرفة ل 50 00:02:44,490 --> 00:02:46,010 المشاريع النهائية المحتملة. 51 00:02:46,010 --> 00:02:49,240 من اجل هذا الهدف، وبالطبع لديه تقليد عقد الندوات التي 52 00:02:49,240 --> 00:02:50,950 هي حول مواضيع عرضية للدورة. 53 00:02:50,950 --> 00:02:54,330 تتعلق كثيرا في البرمجة و تطوير التطبيق وهكذا دواليك، ولكن 54 00:02:54,330 --> 00:02:57,010 لم تستكشف بالضرورة منهج الدورة الخاصة. 55 00:02:57,010 --> 00:03:00,250 >> لذلك إذا كنت قد تكون مهتمة في واحد أو أكثر من الحلقات الدراسية لهذا العام، 56 00:03:00,250 --> 00:03:02,530 التسجيل في cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 هناك ندوات كبار السن في cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 وعلى القائمة حتى الآن لهذا العام هي تطبيقات ويب مذهلة مع روبي على 59 00:03:10,620 --> 00:03:13,580 القضبان، والذي هو بديل لغة PHP. 60 00:03:13,580 --> 00:03:14,900 اللسانيات الحاسوبية. 61 00:03:14,900 --> 00:03:18,710 مقدمة لدائرة الرقابة الداخلية، والذي هو منصة الذي يتم استخدامه للآيفون و 62 00:03:18,710 --> 00:03:19,850 التنمية باد. 63 00:03:19,850 --> 00:03:22,890 جافا سكريبت لتطبيقات الويب، سنقوم تغطية ذلك، ولكن في هذه الندوة، عليك أن تذهب 64 00:03:22,890 --> 00:03:24,070 في مزيد من التفاصيل. 65 00:03:24,070 --> 00:03:27,390 >> قفزة الحركة، لذلك سيكون لدينا فعلا بعض من أصدقائنا من قفزة الحركة، 66 00:03:27,390 --> 00:03:29,160 الشركة نفسها، والانضمام إلينا. 67 00:03:29,160 --> 00:03:31,800 غدا، في الواقع، لتوفير ندوة التدريب العملي على، إذا 68 00:03:31,800 --> 00:03:33,320 ذات فائدة لكم. 69 00:03:33,320 --> 00:03:38,770 Meteor.js، وهي تقنية بديلة لل باستخدام جافا سكريبت ليس في المتصفح، 70 00:03:38,770 --> 00:03:39,970 ولكن على الخادم. 71 00:03:39,970 --> 00:03:42,110 Node.js، والتي هي إلى حد كبير في هذا السياق أيضا. 72 00:03:42,110 --> 00:03:43,650 أنيق تصميم الروبوت. 73 00:03:43,650 --> 00:03:46,990 الروبوت كونه بديل شعبية جدا لدائرة الرقابة الداخلية ويندوز فون 74 00:03:46,990 --> 00:03:48,790 وغيرها من منصات متحركة. 75 00:03:48,790 --> 00:03:51,180 والأمن الإنترنت الدفاع بالموقع. 76 00:03:51,180 --> 00:03:54,590 >> ذلك في الواقع، إذا كنت ترغب للمشاركة في هذا، اسمحوا لي 77 00:03:54,590 --> 00:03:55,840 جعل علما بذلك. 78 00:03:55,840 --> 00:03:57,790 نحن سعداء جدا أن أقول أن أصدقائنا في قفزة 79 00:03:57,790 --> 00:03:59,140 الحركة، وهو بدء التشغيل - 80 00:03:59,140 --> 00:04:01,300 هذا الجهاز حقا خرج للتو من قبل بضعة أشهر - 81 00:04:01,300 --> 00:04:05,960 تبرعت تكرم 30 من هذه الأجهزة إلى الفئة للعديد من الطلاب، وإذا كان 82 00:04:05,960 --> 00:04:08,670 كنت ترغب في استعارة الأجهزة نحو نهاية الفصل الدراسي واستخدامها ل 83 00:04:08,670 --> 00:04:10,390 مشروع النهائي الفعلي. 84 00:04:10,390 --> 00:04:11,890 أنها تدعم عددا من اللغات. 85 00:04:11,890 --> 00:04:16,040 أيا منها C، فإن أيا منها PHP، لذلك تحقيق واحد أو أكثر من هذه الندوات 86 00:04:16,040 --> 00:04:16,899 قد يكون من الفائدة. 87 00:04:16,899 --> 00:04:19,730 وجميعهم سوف يتم تصويره في الحدث الذي لم تكن قادرا 88 00:04:19,730 --> 00:04:21,380 الحضور شخصيا. 89 00:04:21,380 --> 00:04:25,000 يتم الإعلان عن الجدول الزمني عبر البريد الالكتروني ونحن يصلب الغرف. 90 00:04:25,000 --> 00:04:28,460 >> وأخيرا، إذا كنت تذهب ل projects.cs.50.net، وهذا هو موقع على شبكة الانترنت 91 00:04:28,460 --> 00:04:31,450 نحافظ كل عام أن ندعو الناس من المجتمع وأعضاء هيئة التدريس، 92 00:04:31,450 --> 00:04:36,420 الإدارات والموظفين، وعلى حد سواء في خارج CS50 ل 93 00:04:36,420 --> 00:04:37,730 اقتراح أفكار المشاريع. 94 00:04:37,730 --> 00:04:39,050 الأمور التي تهم الجماعات الطلابية. 95 00:04:39,050 --> 00:04:40,600 الأمور التي تهم الإدارات. 96 00:04:40,600 --> 00:04:43,990 حتى لا تتحول إلى هناك إذا كنت تناضل مع عدم اليقين بشأن ما كنت 97 00:04:43,990 --> 00:04:46,700 نفسك ترغب في التصدي لها. 98 00:04:46,700 --> 00:04:51,760 >> مشاركة من الوقت قدمنا ​​ويمكن القول بنية بيانات أكثر تعقيدا مما كنا 99 00:04:51,760 --> 00:04:53,300 رأينا في الأسابيع الماضية. 100 00:04:53,300 --> 00:04:56,550 كنا تم استخدام المصفوفات جميلة لحسن الحظ باعتباره مفيدا إذا 101 00:04:56,550 --> 00:04:58,160 بنية البيانات في التبسيط. 102 00:04:58,160 --> 00:05:00,570 ثم قدمنا ​​هذه، التي بالطبع والقوائم المرتبطة. 103 00:05:00,570 --> 00:05:05,470 وماذا كان واحدا من الدوافع ل إدخال البيانات هذا الهيكل؟ 104 00:05:05,470 --> 00:05:06,930 نعم؟ 105 00:05:06,930 --> 00:05:07,250 ما هذا؟ 106 00:05:07,250 --> 00:05:08,080 >> الجمهور: حجم الحيوي. 107 00:05:08,080 --> 00:05:09,040 >> DAVID مالان: حجم الحيوي. 108 00:05:09,040 --> 00:05:11,890 ذلك في حين أنه في مجموعة، لديك ل تعرف حجمها في وقت مبكر عندما 109 00:05:11,890 --> 00:05:12,740 كنت تحيله. 110 00:05:12,740 --> 00:05:14,380 في قائمة مرتبطة، كنت لا لديك لمعرفة ذلك. 111 00:05:14,380 --> 00:05:17,610 يمكنك malloc فقط، أو بصورة أعم، تخصيص مبلغ إضافي 112 00:05:17,610 --> 00:05:20,720 العقدة، إذا جاز التعبير، في أي وقت كنت تريد إدراج المزيد من البيانات. 113 00:05:20,720 --> 00:05:22,670 وليس لديه عقدة محددة سلفا معنى. 114 00:05:22,670 --> 00:05:25,580 انها مجرد مصطلح عام يصف نوع من الحاوية التي نحن 115 00:05:25,580 --> 00:05:29,610 استخدام في بنية البيانات لدينا لتخزين بعض بند المصالح، وهو في هذه 116 00:05:29,610 --> 00:05:31,750 الحالة يحدث أن تكون صحيحة. 117 00:05:31,750 --> 00:05:33,160 >> ولكن هناك دائما المفاضلة. 118 00:05:33,160 --> 00:05:38,070 حتى نحصل على أحجام الديناميكي للبيانات هيكل، ولكن ما هو الثمن الذي ندفعه لا؟ 119 00:05:38,070 --> 00:05:40,040 ما هو الجانب السلبي من القوائم المرتبطة؟ 120 00:05:40,040 --> 00:05:41,006 نعم؟ 121 00:05:41,006 --> 00:05:41,980 >> الحضور: يتطلب المزيد من الذاكرة. 122 00:05:41,980 --> 00:05:44,240 >> DAVID مالان: إنه يتطلب أكثر الذاكرة، وكيف بالضبط؟ 123 00:05:44,240 --> 00:05:46,440 >> الحضور: [غير مسموع]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID مالان: بالضبط. 125 00:05:47,050 --> 00:05:50,460 حتى الآن لدينا مؤشرات تناول ذاكرة إضافية أننا سابقا 126 00:05:50,460 --> 00:05:53,040 لم تكن في حاجة، وذلك لأن ميزة من صفيف، بطبيعة الحال، هو أن 127 00:05:53,040 --> 00:05:54,860 كل شيء متجاورة، ومرة ​​أخرى إلى العودة إلى الوراء، والتي 128 00:05:54,860 --> 00:05:56,380 يمنحك الوصول العشوائي. 129 00:05:56,380 --> 00:06:00,710 لمجرد باستخدام قوس مربع التدوين، أو أكثر من الناحية الفنية المؤشر 130 00:06:00,710 --> 00:06:03,580 الحسابي، بالإضافة إلى ذلك بسيط جدا، يمكنك الوصول إلى أي 131 00:06:03,580 --> 00:06:05,700 عناصر في وقت ثابت. 132 00:06:05,700 --> 00:06:08,975 في واقع الأمر، وهذا النوع من ملمحا إلى آخر سعر أننا ندفع مع 133 00:06:08,975 --> 00:06:09,760 قائمة مرتبطة. 134 00:06:09,760 --> 00:06:13,890 >> ما يحدث للوقت تشغيل شيء من هذا القبيل البحث، إذا أريد ل 135 00:06:13,890 --> 00:06:17,270 العثور على بعض القيمة وداخل من قائمة مرتبطة؟ 136 00:06:17,270 --> 00:06:20,290 ماذا تصبح وقتي تشغيل؟ 137 00:06:20,290 --> 00:06:21,560 O كبيرة من ن. 138 00:06:21,560 --> 00:06:24,060 إذا فإنه يتم فرز ل؟ 139 00:06:24,060 --> 00:06:25,440 ماذا لو تم فرزها بنية البيانات و؟ 140 00:06:25,440 --> 00:06:28,640 يمكنني أن أفعل أفضل من الكبيرة O ن للبحث؟ 141 00:06:28,640 --> 00:06:31,700 لا، لأنه في أسوأ الحالات فإنه قد بشكل جيد للغاية أن يتم فرز، ولكن عدد 142 00:06:31,700 --> 00:06:32,950 كنت تبحث عن قد تكون كبيرة. 143 00:06:32,950 --> 00:06:35,370 قد يكون عدد 100، والتي قد يحدث أن تكون جميع 144 00:06:35,370 --> 00:06:36,410 الطريق في نهاية المطاف. 145 00:06:36,410 --> 00:06:39,950 ولأن يمكنك فقط الوصول مرتبط القائمة في هذا التنفيذ من قبل 146 00:06:39,950 --> 00:06:42,690 الطريقة الأولى من عقدة لها، وكنت لا يزال نوع من من الحظ. 147 00:06:42,690 --> 00:06:47,450 عليك أن تجتاز كل شيء من أول إلى آخر من أجل إيجاد 148 00:06:47,450 --> 00:06:49,150 تلك القيمة الكبيرة مثل 100. 149 00:06:49,150 --> 00:06:51,350 أو لتحديد ما اذا كان ولا حتى هناك. 150 00:06:51,350 --> 00:06:55,960 >> لذلك لا نستطيع أن نفعل ما الخوارزمية في البيانات هيكل يشبه هذا؟ 151 00:06:55,960 --> 00:06:59,460 لا نستطيع أن نفعل البحث الثنائي، ل البحث الثنائية المطلوبة التي كان لدينا 152 00:06:59,460 --> 00:07:00,740 الوصول العشوائي. 153 00:07:00,740 --> 00:07:04,500 أننا يمكن أن مجرد قفزة من مكان ل موقع دون الحاجة إلى اتباع 154 00:07:04,500 --> 00:07:07,080 هذه فتات الخبز في شكل كل هذه المؤشرات. 155 00:07:07,080 --> 00:07:08,300 >> الآن، كيف ننفذ هذا؟ 156 00:07:08,300 --> 00:07:12,830 حسنا، إذا ذهبنا إلى الشاشة هنا، إذا يمكننا reimplement بسرعة هذه البيانات 157 00:07:12,830 --> 00:07:13,440 هيكل - 158 00:07:13,440 --> 00:07:15,670 بلدي خط اليد ليست كل ما كبيرة هنا، ولكن سنحاول. 159 00:07:15,670 --> 00:07:22,030 البنية الرموز المميزة ل typedef ذلك، وماذا فعلت أنا نريد أن نسمي هذا الشيء هنا؟ 160 00:07:22,030 --> 00:07:22,960 العقدة. 161 00:07:22,960 --> 00:07:24,580 ولذا فإنني سوف يحصل لنا بدأت. 162 00:07:24,580 --> 00:07:27,860 والآن، ما يجب أن يكون داخل بنية البيانات لهذا منفردة 163 00:07:27,860 --> 00:07:28,430 قائمة مرتبطة؟ 164 00:07:28,430 --> 00:07:29,950 كيف العديد من المجالات؟ 165 00:07:29,950 --> 00:07:30,450 >> حتى اثنين. 166 00:07:30,450 --> 00:07:31,570 واحدة من السهل جدا. 167 00:07:31,570 --> 00:07:33,050 لذلك الباحث ن. 168 00:07:33,050 --> 00:07:35,930 ويمكن أن نسميه ن أي شيء نريد، لكن يجب أن يكون عدد صحيح إذا نحن 169 00:07:35,930 --> 00:07:37,660 تنفيذ قائمة مرتبطة لرجات. 170 00:07:37,660 --> 00:07:41,920 والآن ما يفعله الثاني المجال يجب أن تكون؟ 171 00:07:41,920 --> 00:07:43,460 عقدة البنية *. 172 00:07:43,460 --> 00:07:50,570 حتى لو كنت تفعل البنية عقدة *، وبعد ذلك يمكن أن نسمي هذا أيضا ما أريد، 173 00:07:50,570 --> 00:07:53,510 ولكن مجرد أن تكون واضحة سأتصل فإنه المقبل، كما كنا نفعل. 174 00:07:53,510 --> 00:07:55,270 وبعد ذلك سوف يغلق بلدي الأقواس المتعرجة. 175 00:07:55,270 --> 00:08:00,700 >> والآن، كما في المرة السابقة، أنا وضعت أسفل العقدة هنا. 176 00:08:00,700 --> 00:08:03,830 ولكن إذا أنا أعلن هذا كما هو عقدة، لماذا لم أكن عناء يجري ذلك 177 00:08:03,830 --> 00:08:07,320 مطول هنا في اعلان البنية * عقدة المقبل، كما يعارض 178 00:08:07,320 --> 00:08:09,210 إلى عقدة فقط * في المرة القادمة؟ 179 00:08:09,210 --> 00:08:09,904 نعم؟ 180 00:08:09,904 --> 00:08:12,810 >> الحضور: [غير مسموع]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID مالان: بالضبط. 182 00:08:14,050 --> 00:08:14,530 بالضبط. 183 00:08:14,530 --> 00:08:18,320 لأن C يأخذ حقا لكم حرفيا و يرى فقط تعريف العقدة 184 00:08:18,320 --> 00:08:21,230 الطريق إلى هنا، لا يمكنك الرجوع إليه هنا. 185 00:08:21,230 --> 00:08:24,760 لذلك لدينا هذا النوع من قائية إعلان هنا، والتي هي باعتراف الجميع 186 00:08:24,760 --> 00:08:25,390 أكثر مطول. 187 00:08:25,390 --> 00:08:27,810 عقدة البنية، وهذا يعني يمكننا الوصول إليه الآن 188 00:08:27,810 --> 00:08:29,760 داخل بنية البيانات. 189 00:08:29,760 --> 00:08:33,370 >> وبوصفها جانبا، لأن هذا هو أصبحت أكثر قليلا الذاتية الآن، 190 00:08:33,370 --> 00:08:36,230 النجم يمكن أن تذهب من الناحية الفنية هنا، يمكن أن تذهب هنا، فإنه يمكن 191 00:08:36,230 --> 00:08:37,179 حتى تذهب في الوسط. 192 00:08:37,179 --> 00:08:39,890 لقد اعتمدت، في دليل أسلوب ل وبطبيعة الحال، فإن اتفاقية وضع 193 00:08:39,890 --> 00:08:42,299 النجم الحق بجانب البيانات الكتابة، وهو في هذه الحالة، 194 00:08:42,299 --> 00:08:43,460 سيكون عقدة البنية. 195 00:08:43,460 --> 00:08:46,620 ولكن ندرك في الكثير من الكتب و مراجع الانترنت، وكنت قد بالفعل 196 00:08:46,620 --> 00:08:48,450 نرى أنه على الجانب الآخر. 197 00:08:48,450 --> 00:08:52,200 ولكن مجرد أن ندرك أن كلا سوف الواقع العمل ويجب أن تكون ببساطة 198 00:08:52,200 --> 00:08:52,970 متسقة. 199 00:08:52,970 --> 00:08:53,580 >> حسنا. 200 00:08:53,580 --> 00:08:55,630 لذلك كان هذا الإعلان لدينا من عقدة البنية. 201 00:08:55,630 --> 00:08:59,430 ولكن بعد ذلك بدأنا بذل المزيد من الجهد الأمور تعقيدا. 202 00:08:59,430 --> 00:09:03,410 على سبيل المثال، قررنا أن نقدم شيء من هذا القبيل جدول تجزئة. 203 00:09:03,410 --> 00:09:08,160 حتى هنا هو جدول التجزئة من حجم ن، فهرسة من 0 في أعلى يسار إلى n 204 00:09:08,160 --> 00:09:09,690 ناقص 1 في أسفل اليسار. 205 00:09:09,690 --> 00:09:11,640 هذا يمكن أن يكون تجزئة الجدول من أجل أي شيء. 206 00:09:11,640 --> 00:09:15,340 ولكن ما هي أنواع الأشياء لم نتحدث حول استخدام جدول تجزئة ل؟ 207 00:09:15,340 --> 00:09:18,370 تخزين ما؟ 208 00:09:18,370 --> 00:09:18,800 >> أسماء. 209 00:09:18,800 --> 00:09:20,870 يمكننا القيام به أسماء مثل فعلنا في المرة السابقة. 210 00:09:20,870 --> 00:09:22,200 وحقا، يمكنك تخزين أي شيء. 211 00:09:22,200 --> 00:09:24,640 وسنرى هذا مرة أخرى في PHP وجافا سكريبت. 212 00:09:24,640 --> 00:09:28,550 جدول التجزئة هو نوع جميل من السويسري سكين الجيش الذي يسمح لك لتخزين 213 00:09:28,550 --> 00:09:33,690 الى حد كبير كل ما تريد داخل ذلك من خلال ربط مفاتيح مع القيم. 214 00:09:33,690 --> 00:09:34,770 مفاتيح مع القيم. 215 00:09:34,770 --> 00:09:37,800 >> الآن في هذه الحالة بسيطة، لدينا المفاتيح هي مجرد أرقام. 216 00:09:37,800 --> 00:09:40,380 نحن تنفيذ تجزئة الجدول كما صفيف. 217 00:09:40,380 --> 00:09:43,500 وبالتالي فإن المفاتيح هي 0، 1، 2، وهكذا دواليك. 218 00:09:43,500 --> 00:09:47,200 ولذا فإننا، كما قرر البشر، آخر الأسبوع أن تعرف ما، إذا نحن 219 00:09:47,200 --> 00:09:50,410 الذهاب لتخزين أسماء، دعونا فقط تعسفي، ولكن بشكل معقول جدا، 220 00:09:50,410 --> 00:09:54,680 نفترض أن أليس، وهو اسم A، وسوف يكون مجرد فهرستها في 0. 221 00:09:54,680 --> 00:09:58,030 وبوب، وهو اسم B، سيتم فهرستها في 1، وهكذا دواليك. 222 00:09:58,030 --> 00:10:02,490 لذلك كان علينا تعيين بين المدخلات، والتي هي سلاسل، والتجزئة 223 00:10:02,490 --> 00:10:04,560 المواقع، التي هي الأرقام. 224 00:10:04,560 --> 00:10:07,740 >> لذلك هو أن العملية المعروفة عموما وظيفة تجزئة، ويمكنك حقا 225 00:10:07,740 --> 00:10:09,130 تنفيذه في التعليمات البرمجية. 226 00:10:09,130 --> 00:10:12,080 إذا أردت أن تنفذ وظيفة تجزئة أن يفعل بالضبط ما كنا 227 00:10:12,080 --> 00:10:17,070 وصفه للتو من آخر مرة، وأنا قد تعلن دالة التي تأخذ، و 228 00:10:17,070 --> 00:10:18,330 المدخلات على سبيل المثال - 229 00:10:18,330 --> 00:10:22,190 ودعونا نفعل ذلك على هذا فحص أكثر من هنا. 230 00:10:22,190 --> 00:10:26,180 إذا أردت أن تنفيذ تجزئة وظيفة، وأنا قد يقول 231 00:10:26,180 --> 00:10:27,410 شيء من هذا القبيل. 232 00:10:27,410 --> 00:10:29,030 >> انها سوف بإرجاع عدد صحيح. 233 00:10:29,030 --> 00:10:33,600 انها تسير ليتم استدعاؤها تجزئة، وانها الذهاب لقبول كحجة ل 234 00:10:33,600 --> 00:10:38,920 سلسلة، أو أننا يمكن أن يكون أكثر مناسبة الآن، ويقول شار *، ونحن سوف يطلق عليه ق. 235 00:10:38,920 --> 00:10:43,840 وبعد ذلك كل هذه الوظيفة لا علاقة له، في نهاية المطاف، هو العودة إلى كثافة العمليات. 236 00:10:43,840 --> 00:10:45,990 الآن، وكيف يفعل ذلك القوة لا تكون واضحة جدا. 237 00:10:45,990 --> 00:10:49,510 أنا ذاهب لتنفيذ ذلك دون أي شكل خطأ التحقق الآن. 238 00:10:49,510 --> 00:10:55,740 أنا فقط أريد أن أقول عمياء، وعودة كل ما هو في قوس ق 0، ناقص، 239 00:10:55,740 --> 00:10:58,850 دعنا نقول، عاصمة فاصلة منقوطة. 240 00:10:58,850 --> 00:10:59,960 >> كسر تماما. 241 00:10:59,960 --> 00:11:02,620 انها ليست مثالية ل واحد، ما إذا ق باطل؟ 242 00:11:02,620 --> 00:11:04,000 أشياء سيئة ستحدث. 243 00:11:04,000 --> 00:11:07,940 اثنين، ما إذا كان الحرف الأول في هذا اسم ليس حرف؟ 244 00:11:07,940 --> 00:11:09,860 التي لن تتحول إما بشكل جيد. 245 00:11:09,860 --> 00:11:11,970 قد يكون الحرف الصغير أو ليس إلكتروني على الإطلاق. 246 00:11:11,970 --> 00:11:15,520 حتى غرفة تماما للتحسين هنا، ولكن هذه هي الفكرة الأساسية. 247 00:11:15,520 --> 00:11:19,010 >> ما وصفنا الأسبوع الماضي، حيث لفظيا مجرد عملية رسم الخرائط أليس ل 248 00:11:19,010 --> 00:11:23,360 يمكن التعبير 0 وبوب ان 1 بالتأكيد أكثر formulaically باعتبارها C 249 00:11:23,360 --> 00:11:24,320 تعمل هنا. 250 00:11:24,320 --> 00:11:28,630 ودعا مرة أخرى التجزئة، كما تأخذ سلسلة المدخلات، ثم على نحو ما يفعل شيئا 251 00:11:28,630 --> 00:11:31,020 مع أن المدخلات لإنتاج المخرجات. 252 00:11:31,020 --> 00:11:34,130 لا يختلف لدينا وصف الصندوق الأسود أننا قد فعلت طويلة. 253 00:11:34,130 --> 00:11:36,550 أنا لا أعرف كيف يمكن أن يكون هذا تعمل تحت غطاء محرك السيارة. 254 00:11:36,550 --> 00:11:40,120 >> لمشكلة تعيين 6، واحدة من التحديات هو بالنسبة لك لتقرر ما 255 00:11:40,120 --> 00:11:41,920 وسوف تكون دالة البعثرة الخاصة بك؟ 256 00:11:41,920 --> 00:11:45,760 ما يحدث أن تكون داخل تلك الأسود مربع، ويفترض، وأنها سوف تكون 257 00:11:45,760 --> 00:11:50,380 قليلا أكثر إثارة للاهتمام من هذا، و بالتأكيد أكثر عرضة للخطأ 258 00:11:50,380 --> 00:11:53,180 التحقق من ذلك خاصة التنفيذ. 259 00:11:53,180 --> 00:11:54,580 >> لكن المشاكل يمكن أن تنشأ، أليس كذلك؟ 260 00:11:54,580 --> 00:11:57,760 اذا كان لدينا بنية بيانات مثل هذا واحد، ما هو واحدة من المشاكل 261 00:11:57,760 --> 00:12:01,600 يمكنك تشغيل في أكثر من مرة عند إدراج أسماء أكثر وأكثر في 262 00:12:01,600 --> 00:12:02,880 تجزئة الجدول؟ 263 00:12:02,880 --> 00:12:04,630 تحصل التصادمات، أليس كذلك؟ 264 00:12:04,630 --> 00:12:07,560 ماذا لو كان لديك أليس وهارون، اثنين من الناس الذين حصل أسماء 265 00:12:07,560 --> 00:12:08,190 لتبدأ مع و؟ 266 00:12:08,190 --> 00:12:11,660 أن يطرح السؤال، أين أنت وضع الثاني من نوعه اسم؟ 267 00:12:11,660 --> 00:12:15,050 >> كذلك، قد بسذاجة وضعه فقط حيث ينتمي بوب، ولكن بعد ذلك بوب 268 00:12:15,050 --> 00:12:17,300 نوع من ثمل إذا حاولت إدراج اسمه المقبل و 269 00:12:17,300 --> 00:12:18,240 ليس هناك مجال للله. 270 00:12:18,240 --> 00:12:21,400 لذلك كنت قد وضعت بوب حيث تشارلي هو، ويمكنك أن تتخيل هذا بسرعة جدا 271 00:12:21,400 --> 00:12:23,020 تسند إلى قليلا من الفوضى. 272 00:12:23,020 --> 00:12:25,600 شيء خطي في نهاية المطاف، حيث كنت لديك فقط للبحث في كل شيء 273 00:12:25,600 --> 00:12:28,190 يبحث عن أليس أو بوب أو هارون أو تشارلي. 274 00:12:28,190 --> 00:12:33,230 >> وذلك بدلا اقترحنا، بدلا من مجرد التحقيق خطيا عن المساحات المفتوحة 275 00:12:33,230 --> 00:12:36,450 والسقوط أسماء هناك، ونحن اقترح نهجا مربي الحيوانات. 276 00:12:36,450 --> 00:12:41,740 جدول تجزئة تنفيذها لا يزال مع مجموعة من المؤشرات، ولكن نوع بيانات 277 00:12:41,740 --> 00:12:44,500 كانت تلك المؤشرات المؤشرات الآن. 278 00:12:44,500 --> 00:12:47,360 مؤشرات لماذا؟ 279 00:12:47,360 --> 00:12:48,730 مؤشرات إلى القوائم المرتبطة. 280 00:12:48,730 --> 00:12:53,330 >> لأن نذكر أن قائمة مرتبطة هو في الحقيقة مجرد مؤشر إلى عقدة، و 281 00:12:53,330 --> 00:12:57,110 عقدة لديه الحقل التالي، وتلك العقدة لديه الحقل التالي، وهكذا دواليك. 282 00:12:57,110 --> 00:13:00,690 بحيث يمكنك الآن التفكير في هذه المجموعة على الجانب الأيسر من جدول تجزئة كما 283 00:13:00,690 --> 00:13:01,820 مما أدى إلى قائمة مرتبطة. 284 00:13:01,820 --> 00:13:07,000 ميزة وهي إذا كنت تحصل على تصادم بين أليس وهارون، 285 00:13:07,000 --> 00:13:09,300 ماذا تفعل مع هذا الشخص الثاني؟ 286 00:13:09,300 --> 00:13:14,150 كنت مجرد نعلق له أو لها ل نهاية، أو حتى بداية 287 00:13:14,150 --> 00:13:15,490 من تلك القائمة المرتبطة. 288 00:13:15,490 --> 00:13:17,340 >> وفعلا، دعونا فقط من خلال المعكرونة أن لثانية واحدة. 289 00:13:17,340 --> 00:13:18,640 حيث من شأنه أن يجعل معظم معانيها؟ 290 00:13:18,640 --> 00:13:22,060 إذا كنت إدراج أليس وقالت انها ينتهي في الموقع الأول، ثم أحاول أن 291 00:13:22,060 --> 00:13:25,310 إدراج اسم هارون، وهناك من الواضح أن الاصطدام، يجب أن أضع 292 00:13:25,310 --> 00:13:27,400 له في بداية من قائمة مرتبطة؟ 293 00:13:27,400 --> 00:13:30,944 هذا هو الموقع الأول في ذلك، أو في نهاية المطاف؟ 294 00:13:30,944 --> 00:13:31,440 >> الحضور: [غير مسموع]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID مالان: OK. 296 00:13:31,990 --> 00:13:32,490 سمعت تبدأ. 297 00:13:32,490 --> 00:13:33,903 لماذا في البداية؟ 298 00:13:33,903 --> 00:13:34,750 >> الحضور: [غير مسموع]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID مالان: OK. 300 00:13:34,940 --> 00:13:36,520 انها الأبجدي، بحيث لطيف. 301 00:13:36,520 --> 00:13:37,330 هذا هو خاصية جيدة. 302 00:13:37,330 --> 00:13:39,335 سيوفر لي بعض الوقت يحتمل. 303 00:13:39,335 --> 00:13:43,290 انها لن تسمح لي أن تفعل البحث الثنائي، ولكن أنا قد تكون قادرة على الخروج على الأقل 304 00:13:43,290 --> 00:13:47,340 من حلقة إذا أدرك، جيدا، أنا الطريق وكانت في الماضي من شأنه أن يكون هارون في هذا 305 00:13:47,340 --> 00:13:48,310 فرز قائمة مرتبطة. 306 00:13:48,310 --> 00:13:50,360 أنا لا لديك لإضاعة وقتي أبحث على طول الطريق حتى النهاية. 307 00:13:50,360 --> 00:13:51,530 بحيث المعقول. 308 00:13:51,530 --> 00:13:54,710 وإلا لماذا قد ترغب في إدراج اسم اصطدامه في 309 00:13:54,710 --> 00:13:56,660 ابتداء من القائمة؟ 310 00:13:56,660 --> 00:13:57,397 ما هذا؟ 311 00:13:57,397 --> 00:13:58,680 >> الحضور: [غير مسموع]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID مالان: إنه يمكن أن يستغرق وقتا طويلا للوصول الى نهاية القائمة. 313 00:14:00,820 --> 00:14:02,490 في واقع الأمر، أطول وأطول. 314 00:14:02,490 --> 00:14:04,920 أكثر الأسماء التي تضاف التي تبدأ مع A، ويعد ذلك 315 00:14:04,920 --> 00:14:06,280 سلسلة هو الذهاب الى الحصول عليها. 316 00:14:06,280 --> 00:14:07,890 ويعد أن ترتبط قائمة هو الذهاب الى الحصول عليها. 317 00:14:07,890 --> 00:14:09,420 لذلك كنت حقا فقط تهدر وقتك. 318 00:14:09,420 --> 00:14:14,070 ربما كنت أفضل حالا المحافظة ثابت وقت الإدراج، يا كبير من 1، 319 00:14:14,070 --> 00:14:18,470 بواسطة دائما وضع اسم اصطدامه في بداية القائمة المرتبطة، 320 00:14:18,470 --> 00:14:21,230 وليس القلق بقدر حول فرز. 321 00:14:21,230 --> 00:14:22,600 >> ما هو أفضل إجابة؟ 322 00:14:22,600 --> 00:14:23,320 انها غير واضحة. 323 00:14:23,320 --> 00:14:26,140 انها نوع من يعتمد على ما التوزيع هو، ما هو نمط 324 00:14:26,140 --> 00:14:27,850 من الأسماء التي يتم إدخالها. 325 00:14:27,850 --> 00:14:29,430 انها ليست بالضرورة والجواب واضح. 326 00:14:29,430 --> 00:14:33,100 ولكن هنا ل، مرة أخرى، هو فرصة التصميم. 327 00:14:33,100 --> 00:14:37,220 >> لذلك نحن ثم نظرت إلى هذا الشيء، الذي هو حقا آخر فرصة كبيرة 328 00:14:37,220 --> 00:14:38,180 لمدة 6 تعيين ص. 329 00:14:38,180 --> 00:14:41,770 وندرك، إذا كنت لم تقم بذلك بالفعل، Zamyla الغطس في كل من هذه، تجزئة 330 00:14:41,770 --> 00:14:43,260 الجداول ويحاول، في مزيد من التفاصيل. 331 00:14:43,260 --> 00:14:45,630 وتجول الفيديو جزءا لا يتجزأ في مجموعة ع المواصفات. 332 00:14:45,630 --> 00:14:46,590 كان هذا TRIE - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. وما كان مثيرا للاهتمام حول هذا كان أن الوقت تشغيل 334 00:14:51,670 --> 00:14:59,510 من البحث عن اسم، مثل ماكسويل آخر مرة، كان يا كبير من ماذا؟ 335 00:14:59,510 --> 00:15:01,040 ما هذا؟ 336 00:15:01,040 --> 00:15:01,920 >> الحضور: عدد من الرسائل. 337 00:15:01,920 --> 00:15:02,550 >> DAVID مالان: عدد من الرسائل. 338 00:15:02,550 --> 00:15:03,210 سمعت أمرين. 339 00:15:03,210 --> 00:15:04,630 عدد من الرسائل ووقت ثابت. 340 00:15:04,630 --> 00:15:05,540 لذلك دعونا نذهب مع هذا أولا. 341 00:15:05,540 --> 00:15:06,410 عدد الرسائل. 342 00:15:06,410 --> 00:15:10,195 حسنا، هذا بنية البيانات، أذكر، هو مثل شجرة، شجرة العائلة، كل من 343 00:15:10,195 --> 00:15:12,860 يتم إجراء العقد التي تتكون من المصفوفات. 344 00:15:12,860 --> 00:15:16,300 وتلك هي مؤشرات إلى صفائف العقد مثل غيرها، أو غيرها من مثل هذه 345 00:15:16,300 --> 00:15:17,670 صفائف في الشجرة. 346 00:15:17,670 --> 00:15:22,890 >> لذلك إذا أردنا أن تحديد ثم سواء في ماكسويل هو هنا، وأنا قد يذهب 347 00:15:22,890 --> 00:15:26,890 لمجموعة الأولى، في أعلى جدا من الشجرة، ما يسمى الجذر، أعلى 348 00:15:26,890 --> 00:15:30,521 وTRIE، ثم اتبع المؤشر متر، ثم مؤشر، ثم س، 349 00:15:30,521 --> 00:15:31,710 ث، ه، ل، ل. 350 00:15:31,710 --> 00:15:34,910 وبعد ذلك عندما أرى بعض رمز خاص، يشار هنا كما مثلث. 351 00:15:34,910 --> 00:15:38,480 في التعليمات البرمجية سترى نقترح أن لك تنفيذها باعتبارها منطقي، فقط أقول نعم 352 00:15:38,480 --> 00:15:40,540 أو لا، كلمة يتوقف هنا. 353 00:15:40,540 --> 00:15:45,270 >> حسنا، مرة واحدة لقد ذهب إلى M-A-X-W-E-L-L، يشعر وكأنه سبع، وربما 354 00:15:45,270 --> 00:15:48,910 ثمانية إذا ذهبنا واحدة الماضي، وثمانية الخطوات التالية للعثور ماكسويل. 355 00:15:48,910 --> 00:15:53,050 أو دعنا نسميها K. لكن أذكر مشاركة الوقت، وجادلت بأن إذا كان هناك 356 00:15:53,050 --> 00:15:57,540 واقعيا كحد أقصى على طول كلمة واحدة، مثل 40 بعض الأحرف ونيف، و 357 00:15:57,540 --> 00:16:00,810 يعني الحد الأقصى للطول قيمة ثابتة. 358 00:16:00,810 --> 00:16:05,770 لذلك حقا، نعم، انها يا كبير تقنيا من 8 أو 7، أو يا كبير حقا ولكن K. 359 00:16:05,770 --> 00:16:09,420 إذا كان هناك سقف محدد على ما K يمكن أن يكون، انها ثابتة. 360 00:16:09,420 --> 00:16:12,080 ولذا فمن يا كبير من 1 في في نهاية اليوم. 361 00:16:12,080 --> 00:16:13,040 >> ليس في العالم الحقيقي. 362 00:16:13,040 --> 00:16:15,960 لا عند بدء فعلا مشاهدة كما مدار الساعة لديك تشغيل البرنامج الخاص بك. 363 00:16:15,960 --> 00:16:20,690 انها تسير على الاطلاق ليكون قليلا أبطأ من ثابت حقا 364 00:16:20,690 --> 00:16:21,840 الوقت مع خطوة واحدة. 365 00:16:21,840 --> 00:16:25,540 انها سوف تكون سبع أو ثماني خطوات، ولكن لا يزال هذا هو أفضل بكثير 366 00:16:25,540 --> 00:16:30,080 من خوارزمية مثل O كبيرة من ن أن يعتمد على حجم ما هو في 367 00:16:30,080 --> 00:16:31,220 هيكل البيانات. 368 00:16:31,220 --> 00:16:34,970 >> لاحظ الارتفاع هنا هو أننا يمكن إدراج مليون من الأسماء في هذه 369 00:16:34,970 --> 00:16:38,170 هيكل البيانات، ولكن كم من خطوات أكثر هل هو ذاهب الى اتخاذ علينا أن نجد 370 00:16:38,170 --> 00:16:40,480 ماكسويل في هذه الحالة؟ 371 00:16:40,480 --> 00:16:40,780 لا شيء. 372 00:16:40,780 --> 00:16:41,820 انه غير متأثر. 373 00:16:41,820 --> 00:16:45,480 وحتى الآن، وأنا لا أعتقد أننا قد رأيت مثال على بنية بيانات أو 374 00:16:45,480 --> 00:16:48,560 الخوارزمية التي كان تماما تتأثر الخارجية 375 00:16:48,560 --> 00:16:50,040 سلوكيات من هذا القبيل. 376 00:16:50,040 --> 00:16:51,160 ولكن هذا لا يمكن أن تكون مذهلة. 377 00:16:51,160 --> 00:16:52,900 هذا لا يمكن أن يكون الحل الوحيد لف مجموعة 378 00:16:52,900 --> 00:16:53,570 >> وانها ليست. 379 00:16:53,570 --> 00:16:55,980 هذا ليس بالضرورة البيانات هيكل يجب أن تنجذب إلى، 380 00:16:55,980 --> 00:16:58,220 لأن الجداول التجزئة مثل، المقايضة. 381 00:16:58,220 --> 00:17:00,500 ما هو الثمن الذي تدفعه هنا؟ 382 00:17:00,500 --> 00:17:00,940 الذاكرة. 383 00:17:00,940 --> 00:17:02,890 أعني، هذا هو فظيعة مقدار الذاكرة. 384 00:17:02,890 --> 00:17:05,569 وأنت لا يمكن أن نرى تماما هنا ل صاحب هذا الصورة 385 00:17:05,569 --> 00:17:09,420 من الواضح اقتطاع كل من المصفوفات، ونحن لا نرى الكثير من A و 386 00:17:09,420 --> 00:17:12,700 وباء وجيم وللفي س والخاص ص وZ في هذه المصفوفات. 387 00:17:12,700 --> 00:17:13,630 لكنهم هناك. 388 00:17:13,630 --> 00:17:17,660 >> كل من هذه العقد هو مجموعة كاملة من نحو 26 بايت أو أكثر، كل من 389 00:17:17,660 --> 00:17:19,170 الذي يمثل بريد إلكتروني. 390 00:17:19,170 --> 00:17:22,920 27 في حالتنا، حتى نتمكن من دعم تعيين الفواصل العليا في المشكلة. 391 00:17:22,920 --> 00:17:27,030 لذلك هذا هو حقا بنية البيانات، حقا كثيفة واسعة. 392 00:17:27,030 --> 00:17:30,880 والتي قد تنتهي وحدها يصل تباطؤ الأمور، أو على الأقل تكلفك 393 00:17:30,880 --> 00:17:32,240 أكثر الكثير الفضاء. 394 00:17:32,240 --> 00:17:34,020 ولكن مرة أخرى، يمكننا استخلاص المقارنات هنا. 395 00:17:34,020 --> 00:17:39,190 >> أذكر حين يعود، ونحن تحقق الكثير أكثر إثارة إدارة الوقت في الفرز 396 00:17:39,190 --> 00:17:42,880 عندما نستخدم دمج النوع، ولكن الثمن دفعنا لتحقيق ن ن سجل للدمج 397 00:17:42,880 --> 00:17:46,930 مطلوب النوع الذي ننفق أكثر ما الموارد؟ 398 00:17:46,930 --> 00:17:47,690 مساحة أكبر. 399 00:17:47,690 --> 00:17:50,530 نحن بحاجة إلى مجموعة والثانوية نسخ الناس إلى، تماما مثل 400 00:17:50,530 --> 00:17:51,620 فعلنا هنا على خشبة المسرح. 401 00:17:51,620 --> 00:17:55,880 ذلك مرة أخرى، لا الفائزين واضحة، ولكن التصميم شخصي فقط 402 00:17:55,880 --> 00:17:57,710 قرارات في هذا الشأن. 403 00:17:57,710 --> 00:17:58,060 >> حسنا. 404 00:17:58,060 --> 00:17:59,130 فكيف هذا؟ 405 00:17:59,130 --> 00:18:02,050 أي شخص الذي تعترف D-القاعة؟ 406 00:18:02,050 --> 00:18:02,440 موافق. 407 00:18:02,440 --> 00:18:03,170 لذلك ثلاثة منا القيام به. 408 00:18:03,170 --> 00:18:03,750 ماثر البيت. 409 00:18:03,750 --> 00:18:05,070 لذلك هذا هو لتناول الطعام في ماذر. 410 00:18:05,070 --> 00:18:09,650 أراهن كل قاعات الطعام ديك أكوام من الصواني من هذا القبيل. 411 00:18:09,650 --> 00:18:11,950 وهذا هو في الواقع ممثل شيء قمنا 412 00:18:11,950 --> 00:18:13,050 ومن الواضح أن رأينا بالفعل. 413 00:18:13,050 --> 00:18:14,850 نحن يطلق عليه حرفيا كومة. 414 00:18:14,850 --> 00:18:18,970 والمكدس، من حيث الخاصة بك ذاكرة الكمبيوتر، حيث يذهب البيانات 415 00:18:18,970 --> 00:18:20,460 بينما يجري دعا الوظائف. 416 00:18:20,460 --> 00:18:23,410 >> على سبيل المثال، ما هي أنواع الأشياء تذهب على المكدس فيما يتعلق 417 00:18:23,410 --> 00:18:27,420 تخطيط الذاكرة ناقشناه في الأسابيع الماضية؟ 418 00:18:27,420 --> 00:18:28,736 ما هذا؟ 419 00:18:28,736 --> 00:18:29,670 >> الجمهور: يدعو إلى وظائف. 420 00:18:29,670 --> 00:18:30,260 >> DAVID مالان: أنا آسف. 421 00:18:30,260 --> 00:18:31,210 >> الجمهور: يدعو إلى وظائف. 422 00:18:31,210 --> 00:18:33,590 >> DAVID مالان: يدعو إلى وظائف، ولكن على وجه التحديد، ما هو داخل كل من 423 00:18:33,590 --> 00:18:35,340 تلك الأطر؟ 424 00:18:35,340 --> 00:18:37,220 ما أنواع الأشياء؟ 425 00:18:37,220 --> 00:18:37,460 نعم. 426 00:18:37,460 --> 00:18:38,500 المتغيرات المحلية بذلك. 427 00:18:38,500 --> 00:18:43,080 في أي وقت نحن في حاجة الى بعض التخزين المحلية، مثل حجة، أو الباحث الأول، أو الباحث 428 00:18:43,080 --> 00:18:45,940 درجة الحرارة، أو أيا كانت محلية المتغير هو، كنا 429 00:18:45,940 --> 00:18:47,210 وضع هذا على المكدس. 430 00:18:47,210 --> 00:18:49,610 ونحن نسميها كومة ل من هذه الفكرة طبقات. 431 00:18:49,610 --> 00:18:52,940 مجرد نوع من المباريات مع الواقع، مفهوم منه. 432 00:18:52,940 --> 00:18:56,650 >> ولكن اتضح أن كومة يمكن أيضا أن ينظر إليه باعتباره بنية البيانات، و 433 00:18:56,650 --> 00:19:00,110 بديل للصفيف، بديل إلى قائمة مرتبطة. 434 00:19:00,110 --> 00:19:02,770 شيء أكثر إثارة للاهتمام من الناحية المفاهيمية التي يمكن أن تكون لا تزال 435 00:19:02,770 --> 00:19:06,030 نفذت باستخدام أي من تلك الأشياء، ولكن من نوع مختلف من 436 00:19:06,030 --> 00:19:09,140 هيكل البيانات الداعمة، حقا، اثنين فقط من العمليات. 437 00:19:09,140 --> 00:19:11,000 ولكن يمكنك إضافة على مربي الحيوانات ملامح من هذه. 438 00:19:11,000 --> 00:19:12,180 ولكن هذه هي الأساسيات - 439 00:19:12,180 --> 00:19:13,510 دفع والبوب. 440 00:19:13,510 --> 00:19:19,240 >> وهذه الفكرة مع كومة هو أنه إذا كنت دينا هنا، مع أو بدون أننبرغ 441 00:19:19,240 --> 00:19:22,880 مع العلم، علبة من البيت المجاور مع الرقم 9 على ذلك. 442 00:19:22,880 --> 00:19:23,870 حتى مجرد كثافة العمليات. 443 00:19:23,870 --> 00:19:26,990 وأريد أن دفع هذا على البيانات هيكل، الذي هو حاليا فارغ. 444 00:19:26,990 --> 00:19:28,790 النظر في هذا الجزء السفلي من المكدس. 445 00:19:28,790 --> 00:19:33,150 وأود أن دفع هذا الرقم 9 على كومة، والآن حان الحق هناك. 446 00:19:33,150 --> 00:19:36,040 >> لكن الشيء المثير للاهتمام حول كومة غير أنه إذا أريد الآن لدفع 447 00:19:36,040 --> 00:19:40,210 بعض قيمة أخرى، مثل 17، وأدفع هذا إلى المكدس، وانا ذاهب للقيام 448 00:19:40,210 --> 00:19:43,290 الشيء بديهية فقط، سأقوم لوضعها الصحيح حيث نحن البشر 449 00:19:43,290 --> 00:19:45,180 سوف تميل إلى وضعه، على القمة. 450 00:19:45,180 --> 00:19:48,850 ولكن ما هو مثير للاهتمام الآن هو، كيف يمكنني الحصول على 9؟ 451 00:19:48,850 --> 00:19:50,670 كما تعلمون، أنا لا تخلو من بعض الجهد. 452 00:19:50,670 --> 00:19:54,070 >> فما مثيرة للاهتمام حول كومة هو أن حسب التصميم، 453 00:19:54,070 --> 00:19:56,330 انها بنية بيانات LIFO. 454 00:19:56,330 --> 00:19:59,680 طريقة سخيفة لوصف آخر في، أولا خارج. 455 00:19:59,680 --> 00:20:03,280 حتى آخر رقم في وكان في هذا الوقت 17. 456 00:20:03,280 --> 00:20:07,540 لذلك إذا أريد لموسيقى البوب ​​شيء خارج من المكدس، يمكن أن يكون فقط 17. 457 00:20:07,540 --> 00:20:11,890 لذلك هناك أمر إلزامي لل عمليات هنا، حيث العنصر الأخير 458 00:20:11,890 --> 00:20:14,260 في أن تكون أول من أصل واحد. 459 00:20:14,260 --> 00:20:16,440 وبالتالي اختصار، LIFO. 460 00:20:16,440 --> 00:20:19,160 >> فلماذا هذا قد يكون مفيدا؟ 461 00:20:19,160 --> 00:20:22,690 وسياقاتها التي كنت نريد بنية بيانات من هذا القبيل؟ 462 00:20:22,690 --> 00:20:24,810 حسنا، انها كانت بالتأكيد مفيدة داخل جهاز الكمبيوتر. 463 00:20:24,810 --> 00:20:29,050 أنظمة التشغيل وذلك باستخدام هذا بوضوح نوع من بنية بيانات للمداخن. 464 00:20:29,050 --> 00:20:32,800 سوف نرى أيضا نفس الفكرة عندما يتعلق الأمر إلى صفحات الويب. 465 00:20:32,800 --> 00:20:35,890 لذلك هذا الاسبوع والاسبوع القادم وما بعده، وعندما تبدأ تنفيذ شبكة الإنترنت 466 00:20:35,890 --> 00:20:39,490 صفحات بلغة HTML دعا، يمكنك فعلا استخدام بنية بيانات مثل 467 00:20:39,490 --> 00:20:42,690 هذا لتحديد ما إذا كانت الصفحة يتم تنسيق بشكل صحيح. 468 00:20:42,690 --> 00:20:47,170 لأننا سنرى كل صفحات الويب متابعة نوع من التسلسل الهرمي، والمسافة البادئة 469 00:20:47,170 --> 00:20:52,030 هذه الإرادة، في نهاية المطاف، أن يكون هيكل شجرة تحت غطاء محرك السيارة. 470 00:20:52,030 --> 00:20:53,620 أكثر من ذلك على أنه في قليلا فقط. 471 00:20:53,620 --> 00:20:56,560 >> لكنه الآن، دعونا اقتراح ل لحظة، كيف يمكن أن تذهب نحو 472 00:20:56,560 --> 00:20:58,830 تمثل ما هو كومة؟ 473 00:20:58,830 --> 00:21:03,370 اسمحوا لي أن أقترح أن ننفذ كومة مع رمز مثل هذا. 474 00:21:03,370 --> 00:21:07,990 حتى كومة ستكون لدينا داخل منه أمرين، صفيف، دعا الصواني، 475 00:21:07,990 --> 00:21:09,510 لمجرد أن يكون متسقا مع العرض. 476 00:21:09,510 --> 00:21:12,660 ولكل من العناصر في هذا الصفيف سوف يكون نوع int. 477 00:21:12,660 --> 00:21:14,740 والقدرة هي ما يفترض؟ 478 00:21:14,740 --> 00:21:18,796 لأنني لم يكتب ل التعريف الكامل هنا. 479 00:21:18,796 --> 00:21:21,535 >> انها على الارجح الأقصى حجم المصفوفة. 480 00:21:21,535 --> 00:21:25,150 وانها على الارجح كما أعلن حاد تعريف في الجزء العلوي من الملف، بعض 481 00:21:25,150 --> 00:21:28,450 نوع من ثابتة كما تنطوي عليها مجرد الرسملة. 482 00:21:28,450 --> 00:21:32,250 في مكان ما بحيث يتم تعريف القدرة كحد أقصى حجم ممكن. 483 00:21:32,250 --> 00:21:35,590 وفي الوقت نفسه، داخل بنية البيانات المعروفة باسم كومة سيكون هناك 484 00:21:35,590 --> 00:21:38,630 ان يكون عدد صحيح يعرف فقط ببساطة الحجم. 485 00:21:38,630 --> 00:21:43,400 >> حتى لو كنت لتمثيل هذا الآن بالصور، دعونا نفترض أن هذا 486 00:21:43,400 --> 00:21:48,070 يمثل الصندوق الاسود كله بلدي المكدس. 487 00:21:48,070 --> 00:21:50,070 داخل منه هو متغيرين. 488 00:21:50,070 --> 00:21:54,780 لذلك أنا ذاهب لرسم أول واحد كما الحجم. 489 00:21:54,780 --> 00:21:57,420 والثانية انا ذاهب كما رسم صفيف. 490 00:21:57,420 --> 00:22:01,060 >> ولكن فقط لابقاء الامور منظم، عادة أود أن ألفت مجموعة مثل 491 00:22:01,060 --> 00:22:04,910 هذا، ولكن هذا النوع من طيف إذا كنا تطابق الواقع، أو 492 00:22:04,910 --> 00:22:06,230 تطابق نموذج العقلية. 493 00:22:06,230 --> 00:22:12,880 لذلك اسمحوا لي بدلا رسم مجموعة عموديا، الذي هو مجرد، مرة أخرى، 494 00:22:12,880 --> 00:22:13,840 التسليم الفنان. 495 00:22:13,840 --> 00:22:16,610 لا يهم ما هو حقا هو تحت غطاء محرك السيارة. 496 00:22:16,610 --> 00:22:20,350 وسوف نقول ذلك، افتراضيا، القدرة ستكون الثلاثة. 497 00:22:20,350 --> 00:22:23,480 لذلك سيكون هذا المكان 0، وهذا سيكون المكان 1، وهذا 498 00:22:23,480 --> 00:22:25,740 سيكون المكان 2. 499 00:22:25,740 --> 00:22:29,330 >> إذا كنت رشوة مع الكرة الإجهاد، وسوف شخص ترغب في الخروج وتشغيل 500 00:22:29,330 --> 00:22:30,870 متن هنا لمجرد لحظة؟ 501 00:22:30,870 --> 00:22:31,960 موافق، ورأى يدك أولا. 502 00:22:31,960 --> 00:22:33,950 تأتي على ما يصل. 503 00:22:33,950 --> 00:22:36,500 حسنا. 504 00:22:36,500 --> 00:22:38,760 لذلك أعتقد أنه من ستيفن. 505 00:22:38,760 --> 00:22:40,035 تأتي على ما يصل. 506 00:22:40,035 --> 00:22:40,770 حسنا. 507 00:22:40,770 --> 00:22:46,760 >> ولكن لنفترض الآن أننا الترجيع على التقارير الأولية دولة من العالم حيث أنا 508 00:22:46,760 --> 00:22:52,180 وقد أعلنت مجرد كومة، وانها ستكون القدرة الثلاث. 509 00:22:52,180 --> 00:22:54,470 ولكن لم يتم بعد تحديد حجم. 510 00:22:54,470 --> 00:22:56,100 ولم يتم بعد تحديد الصواني. 511 00:22:56,100 --> 00:22:57,300 حتى بضعة أسئلة الأولى. 512 00:22:57,300 --> 00:23:01,310 واسمحوا لي أن أقدم لكم هيئة التصنيع العسكري حتى تتمكن من يشاركون بنشاط أكبر في هذا المجال. 513 00:23:01,310 --> 00:23:05,190 >> فما هو حجم داخل في هذه اللحظة في الوقت إذا كل ما قاموا به هو 514 00:23:05,190 --> 00:23:09,340 أعلن كومة مع سطر واحد من التعليمات البرمجية؟ 515 00:23:09,340 --> 00:23:10,100 >> ستيفن: ليس كثيرا. 516 00:23:10,100 --> 00:23:12,080 >> DAVID مالان: OK، وليس ذلك بكثير. 517 00:23:12,080 --> 00:23:14,410 لا نعرف ما هو داخل الحجم، لا نعرف ما هو داخل 518 00:23:14,410 --> 00:23:16,330 من هذه المجموعة هنا؟ 519 00:23:16,330 --> 00:23:18,630 >> ستيفن: كود عشوائي فقط، أليس كذلك؟ 520 00:23:18,630 --> 00:23:20,220 فقط - 521 00:23:20,220 --> 00:23:23,230 >> DAVID مالان: نعم، أنا ذاهب ل يطلق عليه رمز، ولكن العشوائية - 522 00:23:23,230 --> 00:23:23,820 >> ستيفن: الأشياء. 523 00:23:23,820 --> 00:23:28,290 >> DAVID مالان: أشياء مثل عشوائي 524 00:23:28,290 --> 00:23:28,870 >> ستيفن: القطع. 525 00:23:28,870 --> 00:23:29,530 >> DAVID مالان: القطع، أليس كذلك؟ 526 00:23:29,530 --> 00:23:31,190 حتى القيم القمامة، أليس كذلك؟ 527 00:23:31,190 --> 00:23:33,470 لذلك من التباديل و0 1 في. 528 00:23:33,470 --> 00:23:35,920 بقايا من الأعراف السابقة من هذه الذاكرة. 529 00:23:35,920 --> 00:23:38,150 ونحن لا نعرف حقا ما القيم هي، لذلك نحن عادة رسم لهم 530 00:23:38,150 --> 00:23:38,930 كما علامات استفهام. 531 00:23:38,930 --> 00:23:41,990 >> وبالتالي فإن أول شيء نحن يفترض تريد الذهاب الى القيام به هنا - 532 00:23:41,990 --> 00:23:46,630 واسمحوا لي أن أقدم هذا المجال داخل من هناك اسم - الصواني. 533 00:23:46,630 --> 00:23:49,540 ما يجب علينا تهيئة يفترض الحجم إلى إذا كنا نريد أن 534 00:23:49,540 --> 00:23:51,040 البدء في استخدام هذا المكدس؟ 535 00:23:51,040 --> 00:23:53,070 >> ستيفن: صينية هو دون 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID مالان: إذن، حسنا. 537 00:23:53,910 --> 00:23:56,710 أن تكون واضحة، وأعلن القدرات في أماكن أخرى الثلاثة. 538 00:23:56,710 --> 00:23:58,570 وهذا ما كنت قد استخدمت لتخصيص مجموعة. 539 00:23:58,570 --> 00:24:03,535 حجم هو ذاهب للإشارة إلى كيفية العديد من صواني حاليا على المكدس. 540 00:24:03,535 --> 00:24:03,880 >> ستيفن: صفر. 541 00:24:03,880 --> 00:24:04,460 >> DAVID مالان: لذلك ينبغي أن يكون صفرا. 542 00:24:04,460 --> 00:24:07,760 لذلك يذهب إلى الأمام، ومع أي إصبع، رسم الصفر في الحجم. 543 00:24:07,760 --> 00:24:08,440 حسنا. 544 00:24:08,440 --> 00:24:10,920 وحتى الآن، ما هو داخل هذا هنا، ونحن لا نعرف. 545 00:24:10,920 --> 00:24:12,160 هذه هي حقا القيم القمامة فقط. 546 00:24:12,160 --> 00:24:14,800 حتى نتمكن من رسم علامات استفهام، ولكن دعونا نحافظ على لوحة نظيفة في الوقت الراهن 547 00:24:14,800 --> 00:24:16,300 لأنه لا يهم ما هو هناك. 548 00:24:16,300 --> 00:24:19,130 نحن لسنا بحاجة إلى تهيئة مجموعة إلى أي شيء، لأنه إذا علمنا أن 549 00:24:19,130 --> 00:24:23,100 حجم المكدس هو صفر، حسنا، نحن لا ينبغي أن تبحث في أي شيء في 550 00:24:23,100 --> 00:24:25,590 على أي حال في هذه المجموعة هذه النقطة في الوقت المناسب. 551 00:24:25,590 --> 00:24:29,970 >> لذلك لنفترض الآن أنني دفع عدد 9 إلى المكدس. 552 00:24:29,970 --> 00:24:33,750 كيف يجب أن نقوم بتحديث بنية البيانات داخل هذا الصندوق الأسود؟ 553 00:24:33,750 --> 00:24:35,540 ما هي القيم بحاجة إلى تغيير؟ 554 00:24:35,540 --> 00:24:36,200 >> ستيفن: ضمن - 555 00:24:36,200 --> 00:24:37,400 حجم؟ 556 00:24:37,400 --> 00:24:37,650 >> DAVID مالان: OK. 557 00:24:37,650 --> 00:24:38,770 وينبغي أن يصبح حجم ما؟ 558 00:24:38,770 --> 00:24:39,580 >> ستيفن: أن الحجم يكون واحدا. 559 00:24:39,580 --> 00:24:39,870 >> DAVID مالان: OK. 560 00:24:39,870 --> 00:24:41,110 لذلك ينبغي أن يصبح حجم واحد. 561 00:24:41,110 --> 00:24:42,540 حتى تتمكن من القيام بذلك في طرق زوجين. 562 00:24:42,540 --> 00:24:46,920 اسمحوا لي أن أقدم لكم، الآن لديك الإصبع هو ممحاة. 563 00:24:46,920 --> 00:24:47,260 حسنا. 564 00:24:47,260 --> 00:24:49,960 ثم الآن إصبعك هو فرشاة. 565 00:24:49,960 --> 00:24:50,330 حسنا. 566 00:24:50,330 --> 00:24:52,820 والآن ماذا يجب أن يتغير، من الواضح، في بنية البيانات؟ 567 00:24:52,820 --> 00:24:57,060 >> ستيفن: ونحن في طريقنا من أسفل إلى أعلى إلى 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID مالان: 9. 569 00:24:57,760 --> 00:24:58,420 حسنا، جيد. 570 00:24:58,420 --> 00:25:01,550 لذلك لا يزال لا يهم ما هو على موقع واحد أو اثنين لأنهم 571 00:25:01,550 --> 00:25:04,520 القيم القمامة، ولكن لا ينبغي لنا أن يكلف نفسه عناء أبحث هناك لأن حجم 572 00:25:04,520 --> 00:25:07,540 يقولون لنا أن العنصر الأول فقط هو في الواقع شرعية. 573 00:25:07,540 --> 00:25:10,400 وحتى الآن أدفع 17 على القائمة. 574 00:25:10,400 --> 00:25:11,830 ما يحدث لهذه الصورة؟ 575 00:25:11,830 --> 00:25:14,720 >> ستيفن: حجم لذا ستذهب إلى اثنين. 576 00:25:14,720 --> 00:25:15,300 >> DAVID مالان: OK. 577 00:25:15,300 --> 00:25:16,070 كنت ممحاة - 578 00:25:16,070 --> 00:25:16,810 عفوا. 579 00:25:16,810 --> 00:25:18,026 كنت ممحاة. 580 00:25:18,026 --> 00:25:18,840 >> ستيفن: ممحاة. 581 00:25:18,840 --> 00:25:19,720 >> DAVID مالان: أنت فرشاة. 582 00:25:19,720 --> 00:25:20,560 >> ستيفن: فرشاة. 583 00:25:20,560 --> 00:25:20,920 >> DAVID مالان: OK. 584 00:25:20,920 --> 00:25:21,600 وماذا بعد؟ 585 00:25:21,600 --> 00:25:22,600 >> ستيفن: وبعد ذلك - 586 00:25:22,600 --> 00:25:22,915 >> DAVID مالان: نحن دفعت 17. 587 00:25:22,915 --> 00:25:24,760 >> ستيفن: نحن نتمسك 17 على القمة، وذلك - 588 00:25:24,760 --> 00:25:25,710 >> DAVID مالان: موافق، وحسن. 589 00:25:25,710 --> 00:25:27,040 >> ستيفن: - أسقطه أسفل. 590 00:25:27,040 --> 00:25:27,530 >> DAVID مالان: حسنا. 591 00:25:27,530 --> 00:25:27,940 الأمر يزداد سهولة. 592 00:25:27,940 --> 00:25:29,300 أنا لا أذهب لمساعدتك هذه المرة. 593 00:25:29,300 --> 00:25:30,510 دفع 22. 594 00:25:30,510 --> 00:25:31,720 >> ستيفن: تم. 595 00:25:31,720 --> 00:25:34,870 أصبحت ممحاة. 596 00:25:34,870 --> 00:25:37,340 أنا أصبحت فرشاة. 597 00:25:37,340 --> 00:25:39,340 ثم أنا أضع 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID مالان: 22. 599 00:25:40,100 --> 00:25:40,620 ممتازة. 600 00:25:40,620 --> 00:25:41,380 حتى واحد مزيد من الوقت. 601 00:25:41,380 --> 00:25:44,280 أنا الآن ذاهب لدفع إلى المكدس 26. 602 00:25:44,280 --> 00:25:46,350 >> ستيفن: أوه. 603 00:25:46,350 --> 00:25:50,278 يا إلهي. 604 00:25:50,278 --> 00:25:52,520 كنت حقا اشتعلت لي على حين غرة. 605 00:25:52,520 --> 00:25:53,703 >> DAVID مالان: أنت لم انظر هذا المقبلة؟ 606 00:25:53,703 --> 00:25:55,930 >> ستيفن: لم أكن أرى هذا المقبلة. 607 00:25:55,930 --> 00:25:58,756 يمكن أن نعيد الأولية القدرات؟ 608 00:25:58,756 --> 00:25:59,790 >> DAVID مالان: هذا سؤال جيد. 609 00:25:59,790 --> 00:26:02,360 لذلك قمنا نوع من رسمت أنفسنا في زاوية هنا. 610 00:26:02,360 --> 00:26:06,740 هناك حقا ليس جيدا للخروج لستيفن لأننا قد خصصت هذه المجموعة 611 00:26:06,740 --> 00:26:09,130 بشكل ثابت، إذا جاز التعبير، في الداخل من بنية البيانات. 612 00:26:09,130 --> 00:26:12,170 وقمنا في الأساس الثابت ترميز أن يكون من حجم الثلاثة. 613 00:26:12,170 --> 00:26:14,170 لذلك لا يمكننا تخصيص ذلك حقا. 614 00:26:14,170 --> 00:26:20,020 >> يمكننا أن إذا عدنا في، ونحن صواني إعادة تعريف ليكون المؤشر الذي 615 00:26:20,020 --> 00:26:22,300 نحن بعد ذلك استخدام malloc للذاكرة لناحية. 616 00:26:22,300 --> 00:26:25,050 لأنه إذا حصلنا على الذاكرة من كومة عبر malloc، ونحن 617 00:26:25,050 --> 00:26:26,430 ويمكن بعد تحريرها. 618 00:26:26,430 --> 00:26:29,630 ولكن قبل تخليصه، ونحن يمكن أن إعادة تخصيص قسما أكبر من الذاكرة، 619 00:26:29,630 --> 00:26:31,330 تحديث المؤشر، وهكذا دواليك. 620 00:26:31,330 --> 00:26:33,500 لكنه الآن، وهذا هو حقا أفضل ما يمكن القيام به. 621 00:26:33,500 --> 00:26:36,360 دفعة والبوب ​​تسير يفترض أن يكون للإشارة إلى بعض الخطأ. 622 00:26:36,360 --> 00:26:40,270 >> هكذا على سبيل المثال، تنفيذنا من دفع يمكن إرجاع منطقي التي 623 00:26:40,270 --> 00:26:42,390 عاد سبق صحيح، صحيح، صحيح. 624 00:26:42,390 --> 00:26:48,390 ولكن في المرة الرابعة، وانه ستكون لدينا للعودة كاذبة، على سبيل المثال. 625 00:26:48,390 --> 00:26:48,540 حسنا. 626 00:26:48,540 --> 00:26:49,540 جيد جدا. 627 00:26:49,540 --> 00:26:50,060 التهاني. 628 00:26:50,060 --> 00:26:52,160 كنت قد كسبت الكرة الإجهاد اليوم. 629 00:26:52,160 --> 00:26:53,110 >> [تصفيق] 630 00:26:53,110 --> 00:26:54,382 >> ستيفن: شكرا لك. 631 00:26:54,382 --> 00:26:55,680 >> DAVID مالان: شكرا لك. 632 00:26:55,680 --> 00:26:59,740 حسنا، يبدو أن هذا ليس كثيرا من خطوة إلى الأمام، أليس كذلك؟ 633 00:26:59,740 --> 00:27:01,410 وصفنا هذه البنية البيانات. 634 00:27:01,410 --> 00:27:02,320 انها كانت مقنعة، أليس كذلك؟ 635 00:27:02,320 --> 00:27:03,200 أنظمة التشغيل مثل ذلك. 636 00:27:03,200 --> 00:27:06,360 يبدو أن شبكة الإنترنت يمكن الاستفادة من هذا، وغيرها من التطبيقات لا يزال. 637 00:27:06,360 --> 00:27:10,870 ولكن ما هو الحد من الغباء أننا العودة إلى نوع من أسبوعين حدود 638 00:27:10,870 --> 00:27:12,880 حيث قمنا الثابتة صفائف الحجم. 639 00:27:12,880 --> 00:27:15,010 >> لذلك هناك بالفعل اثنين من طرق نتمكن من حل هذا. 640 00:27:15,010 --> 00:27:18,750 يمكننا أن تخصيص حيوي مجموعة، ليس من الصعب الترميز أنها عندي 641 00:27:18,750 --> 00:27:22,600 القيام به هنا، ولكن بدلا من ذلك إعادة معلنا- هذا، لمجرد أن يكون واضحا، و 642 00:27:22,600 --> 00:27:23,830 شيء من هذا القبيل. 643 00:27:23,830 --> 00:27:29,040 * الباحث الصواني، وليس اتخاذ قرار على قدرة حتى الآن. 644 00:27:29,040 --> 00:27:35,460 ولكن عندما أعلن مكدس في مكان آخر في قانون بلدي، وأنا يمكن أن ثم استدعاء malloc، 645 00:27:35,460 --> 00:27:38,250 الحصول على عنوان قطعة من الذاكرة، وأنا لا يمكن تعيين 646 00:27:38,250 --> 00:27:39,980 هذا العنوان إلى الصواني. 647 00:27:39,980 --> 00:27:43,340 >> وبعد ذلك، لأنه مجرد قطعة من الذاكرة، وأنا يمكن أن تستمر في استخدام مربع 648 00:27:43,340 --> 00:27:45,450 التدوين قوس بالطريقة المعتادة. 649 00:27:45,450 --> 00:27:49,020 لأن مرة أخرى، وهناك نوع من هذا المعادل الوظيفي من المصفوفات و 650 00:27:49,020 --> 00:27:50,820 قطع من الذاكرة التي تأتي العودة من malloc. 651 00:27:50,820 --> 00:27:53,090 يمكننا علاج واحدة عن الأخرى باستخدام مؤشر الحسابية أو 652 00:27:53,090 --> 00:27:54,440 مربع التدوين قوس. 653 00:27:54,440 --> 00:27:55,660 ذلك أن نهج واحد. 654 00:27:55,660 --> 00:28:00,120 >> ولكن كيف يمكن أن ننفذ آخر هذا هيكل البيانات نفسه، يحتمل أن تكون؟ 655 00:28:00,120 --> 00:28:00,280 أليس كذلك؟ 656 00:28:00,280 --> 00:28:04,530 أشعر أننا مجرد حل هذه مشكلة مثل قبل اسبوع. 657 00:28:04,530 --> 00:28:08,860 ما هو الحل لهذه المشكلة أن ستيفن واجهت؟ 658 00:28:08,860 --> 00:28:10,370 قوائم ذلك مرتبط، الحق. 659 00:28:10,370 --> 00:28:13,410 >> إذا كانت المشكلة هي أننا اللوحة أنفسنا في مأزق من خلال تخصيص 660 00:28:13,410 --> 00:28:17,580 مقدما الذاكرة قليلا جدا أننا ثم تضطر إلى التعامل بطريقة أو بأخرى مع، حسنا، 661 00:28:17,580 --> 00:28:19,880 لماذا لا تجنب مجرد أن إصدار تماما؟ 662 00:28:19,880 --> 00:28:26,170 لماذا لا تعلن فقط الصواني أن يكون مؤشر إلى عقدة، إرجو قائمة مرتبطة، 663 00:28:26,170 --> 00:28:30,740 ثم ببساطة تخصيص العقد الجديد في كل مرة ستيفن اللازمة لتناسب 664 00:28:30,740 --> 00:28:32,400 رقم في بنية البيانات. 665 00:28:32,400 --> 00:28:34,200 >> وبالتالي فإن الصورة سوف تضطر إلى تغيير. 666 00:28:34,200 --> 00:28:38,220 انها لن تكون نظيفة وكما بهذه البساطة مجرد مجموعة من ثلاث رجات. 667 00:28:38,220 --> 00:28:42,970 الآن انها ستكون مؤشر إلى البنية، والبنية التي هو ذاهب ل 668 00:28:42,970 --> 00:28:44,830 لديها كثافة ومؤشر المقبل. 669 00:28:44,830 --> 00:28:47,670 انها سوف تؤدي من خلال هذا المؤشر لمثل هذه البنية آخر ل 670 00:28:47,670 --> 00:28:48,600 هذه البنية آخر. 671 00:28:48,600 --> 00:28:50,560 لذلك فإن الصورة في الواقع الحصول على أكثر فوضى قليلا. 672 00:28:50,560 --> 00:28:52,950 وسيكون لدينا السهام ربط كل شيء معا. 673 00:28:52,950 --> 00:28:55,280 >> ولكن هذا شيء طيب، والحق، لأن شاهدنا كيفية القيام بذلك. 674 00:28:55,280 --> 00:28:58,180 وبمجرد الحصول على راحة تنفيذ شيء من هذا القبيل مرتبط 675 00:28:58,180 --> 00:29:01,450 القائمة، والتي سيكون لديك لتفعل لو كنت اختيار لتنفيذ جدول تجزئة مع 676 00:29:01,450 --> 00:29:05,120 تسلسل منفصلة لمدة 6 تعيين ع، يمكنك استخدامه بمثابة لبنة في بناء، أو 677 00:29:05,120 --> 00:29:08,870 العنصر، أو خدش في الكلام، و الإجراء، وهو الأمر الذي كنت وضعت، ل 678 00:29:08,870 --> 00:29:12,560 خلق قطعة اللغز الخاصة بك التي يمكنك ثم إعادة استخدامها. 679 00:29:12,560 --> 00:29:17,090 لذلك المفاضلات، ولكن الحلول الممكنة التي شهدناها في الواقع من قبل. 680 00:29:17,090 --> 00:29:20,560 >> لذلك في كثير من الأحيان، ترى هذا كل سنة أو سنتين عندما تطلق أبل 681 00:29:20,560 --> 00:29:23,060 شيء جديد، وجميع الناس مجنون يصطف خارج أبل 682 00:29:23,060 --> 00:29:27,050 تخزين لشراء الهامشية ترقية على الأجهزة. 683 00:29:27,050 --> 00:29:30,420 أقول هذا، لا بأس، ل أنا واحد من هؤلاء الناس. 684 00:29:30,420 --> 00:29:35,140 حتى أي نوع من هياكل البيانات قد يمثل هذا الواقع؟ 685 00:29:35,140 --> 00:29:36,980 >> حسنا، دعنا نسميها قائمة الانتظار، وهو خط. 686 00:29:36,980 --> 00:29:40,270 بحيث البريطانية أن نسميها عادة يصطف على أي حال، لذلك هو اسم لطيف. 687 00:29:40,270 --> 00:29:44,960 والعمليتين التي طابور يجب دعم سنقوم استدعاء إدراج بقائمة الانتظار 688 00:29:44,960 --> 00:29:48,900 عملية وعملية dequeue، والتي تتشابه في 689 00:29:48,900 --> 00:29:50,120 روح لدفع والبوب. 690 00:29:50,120 --> 00:29:54,060 انها مجرد نوع من مختلف في الاتفاقية، ما نقوم استدعاء هذه. 691 00:29:54,060 --> 00:29:57,680 ولكن لإدراج بقائمة الانتظار يعني شيئا لإضافة أو أدخله إلى بنية البيانات. 692 00:29:57,680 --> 00:29:59,570 لdequeue سيلة لإزالته. 693 00:29:59,570 --> 00:30:05,170 ولكن في حين كان كومة بيانات LIFO هيكل، طابور هو في الأولى، 694 00:30:05,170 --> 00:30:06,740 أول من بنية البيانات. 695 00:30:06,740 --> 00:30:10,050 >> إذا كنت أول شخص في الخط، سوف تكون أول شخص للحصول على 696 00:30:10,050 --> 00:30:12,420 من خط وشراء الجهاز الجديد. 697 00:30:12,420 --> 00:30:18,070 تخيل كيف بالضيق هؤلاء الناس سيكون إذا أبل بدلا استخدام المكدس، ل 698 00:30:18,070 --> 00:30:21,250 المثال، لتنفيذ قطف حتى من لعبة الجديد الخاص بك. 699 00:30:21,250 --> 00:30:24,310 حتى طوابير معنى له، بالتأكيد، و يمكن أن نفكر في كل أنواع 700 00:30:24,310 --> 00:30:27,480 التطبيقات، ويفترض، على قوائم الانتظار، وخصوصا عندما كنت تريد الإنصاف. 701 00:30:27,480 --> 00:30:30,040 فكيف يمكن لنا تنفيذ هذه كما بنية بيانات؟ 702 00:30:30,040 --> 00:30:33,680 >> حسنا، أنا أقترح أننا قد تحتاج إلى أن تفعل ذلك بهذه الطريقة. 703 00:30:33,680 --> 00:30:35,225 لذلك أنا ذاهب لدينا الآن الأرقام. 704 00:30:35,225 --> 00:30:38,190 ولذا فإننا سوف يبقيه بسيط وليس نتحدث بالضرورة من حيث الصواني. 705 00:30:38,190 --> 00:30:40,220 فقط الأرقام التي حصلت من الناس. 706 00:30:40,220 --> 00:30:43,760 القدرة هو الذهاب الى، مرة أخرى، وتحديد العدد الإجمالي للأشخاص التي يمكن أن تكون في 707 00:30:43,760 --> 00:30:46,900 هذا الخط، وثلاثة أو أي قيمة أخرى. 708 00:30:46,900 --> 00:30:50,760 >> ولكن أقترح أن أنا بحاجة للحفاظ على المسار ليس فقط من حجم 709 00:30:50,760 --> 00:30:52,370 قائمة الانتظار، وكم الأمور في ذلك. 710 00:30:52,370 --> 00:30:56,310 لذلك الحجم هو حجم الحالي، والقدرة هو الحد الأقصى لحجم. 711 00:30:56,310 --> 00:30:58,540 فقط مرة أخرى، التسميات قبل الاتفاقية. 712 00:30:58,540 --> 00:31:03,680 لماذا أحتاج إلى كثافة إضافية داخل من طابور لتتبع من هو في 713 00:31:03,680 --> 00:31:05,365 أمام السطر؟ 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 لماذا يجب أن أفعل في هذه الحالة؟ 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> حسنا، كيف هو هذه الصورة سيتغير؟ 718 00:31:16,190 --> 00:31:19,280 أنا ربما يمكن إعادة استخدامها أكثر من هذه الصورة. 719 00:31:19,280 --> 00:31:21,480 اسمحوا لي أن تمضي قدما ومحو ما هو هنا. 720 00:31:21,480 --> 00:31:24,580 وسوف نقدم هذا قليلا اسم مختلف هنا. 721 00:31:24,580 --> 00:31:28,930 دعونا نتخلص من 17، دعونا نتخلص من 9، دعونا نتخلص من 3. 722 00:31:28,930 --> 00:31:30,410 ودعونا نضيف شيئا واحدا الأخرى. 723 00:31:30,410 --> 00:31:34,710 أقترح أن أحتاج لتتبع الجزء الأمامي من القائمة، والذي هو مجرد 724 00:31:34,710 --> 00:31:35,570 ستكون عدد صحيح كذلك. 725 00:31:35,570 --> 00:31:36,550 ونحن في طريقنا ليبقيه بسيط. 726 00:31:36,550 --> 00:31:37,740 لا توجد قائمة مرتبطة في الوقت الراهن. 727 00:31:37,740 --> 00:31:40,900 >> سنقوم نعترف بأننا في طريقنا لل يرفعه ضد هذا الحد. 728 00:31:40,900 --> 00:31:43,720 ولكن ماذا أريد أن أرى يحدث هذه المرة؟ 729 00:31:43,720 --> 00:31:47,240 لذلك افترض المضي قدما وأول شخص يأتي في الخط، و 730 00:31:47,240 --> 00:31:48,560 انها رقم 9. 731 00:31:48,560 --> 00:31:49,680 لدينا كرات الإجهاد. 732 00:31:49,680 --> 00:31:51,330 يمكنني سرقة، مثلا، اثنين أو ثلاثة أشخاص؟ 733 00:31:51,330 --> 00:31:52,690 واحد، اثنان، ثلاثة؟ 734 00:31:52,690 --> 00:31:53,120 تأتي على ما يصل. 735 00:31:53,120 --> 00:31:56,022 الحق من الجبهة، لأن سنقوم جعل هذه واحدة سريعة. 736 00:31:56,022 --> 00:31:59,415 >> كل واحد منكم الآن ستكون صبي مروحة في خط أبل. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 فلن يتم تلقي أجهزة أبل في نهاية هذا على الرغم من. 739 00:32:06,210 --> 00:32:06,500 حسنا. 740 00:32:06,500 --> 00:32:09,430 لذلك كنت رقم 9، وكنت عدد 17، عدد 22. 741 00:32:09,430 --> 00:32:12,130 هذه هي أرقام اعتباطية، مثل معرفات طالب أو غيرها. 742 00:32:12,130 --> 00:32:14,550 وفي لحظة فقط، دعونا نبدأ لبدء إضافة أشياء. 743 00:32:14,550 --> 00:32:16,000 وسوف تشغيل متن هنا هذه المرة. 744 00:32:16,000 --> 00:32:19,570 >> حتى في هذه الحالة، لقد تهيئة الجبهة أن تكون - 745 00:32:19,570 --> 00:32:22,380 أنا في الواقع لا يهمني حقا ما الجبهة هو، لأن حجم صفر. 746 00:32:22,380 --> 00:32:24,480 ولذلك فإن هذا قد كذلك فقط تكون علامة استفهام. 747 00:32:24,480 --> 00:32:26,170 هذه كلها علامات استفهام. 748 00:32:26,170 --> 00:32:29,880 لذلك نحن الآن سوف نبدأ في رؤية الواقع بعض الناس يصطفون في المتجر. 749 00:32:29,880 --> 00:32:33,320 >> حتى إذا كان رقم 9، وكنت أول واحد هناك في الساعة 5 صباحا، والمضي قدما وأصطف، 750 00:32:33,320 --> 00:32:34,210 أو في الليلة السابقة. 751 00:32:34,210 --> 00:32:34,580 موافق. 752 00:32:34,580 --> 00:32:35,940 وحتى الآن 9 هنا. 753 00:32:35,940 --> 00:32:37,940 حتى 9 هو في الجزء الأمامي من القائمة. 754 00:32:37,940 --> 00:32:41,440 لذلك انا ذاهب الى المضي قدما وتحديث حجم هذه البيانات الحالية 755 00:32:41,440 --> 00:32:44,740 بنية أن لا يكون 0 بعد الآن، ولكن أن تكون 1. 756 00:32:44,740 --> 00:32:47,630 انا ذاهب الى وضع 9 في أمام القائمة. 757 00:32:47,630 --> 00:32:51,020 اسمحوا لي أن تمضي قدما وتبديل الشاشة حتى يمكننا أن نرى الماضي لنا هنا. 758 00:32:51,020 --> 00:32:53,220 >> والآن ماذا أريد لوضع في الجبهة؟ 759 00:32:53,220 --> 00:32:56,240 انا ذاهب للحفاظ على المسار الذي و مقدمة قائمة الانتظار الآن 760 00:32:56,240 --> 00:32:58,570 هو في موقع 0. 761 00:32:58,570 --> 00:33:00,510 لأن ما يجري بجانب يحدث؟ 762 00:33:00,510 --> 00:33:03,000 حسنا، لنفترض الآن أنا إدراج بقائمة الانتظار 17 كذلك. 763 00:33:03,000 --> 00:33:04,510 حتى قفز في خط هناك. 764 00:33:04,510 --> 00:33:07,060 ومرة أخرى، هذا النوع من الباب إلى مخزن ستكون هنا. 765 00:33:07,060 --> 00:33:08,700 حتى الآن لقد أضاف 17. 766 00:33:08,700 --> 00:33:10,810 وعلى الرغم من أن هؤلاء الرجال يتم حظر الشاشة، وهذا موافق، 767 00:33:10,810 --> 00:33:12,300 لأننا يمكن أن نرى ذلك هنا. 768 00:33:12,300 --> 00:33:12,910 آسف. 769 00:33:12,910 --> 00:33:13,810 >> الحضور: نحن يمكن ان تتحرك - 770 00:33:13,810 --> 00:33:14,660 >> DAVID مالان: لا، وهذا موافق. 771 00:33:14,660 --> 00:33:16,000 انها ضخمة هناك. 772 00:33:16,000 --> 00:33:18,580 حتى الآن 17 داخل قائمة الانتظار. 773 00:33:18,580 --> 00:33:21,332 ولست بحاجة للتحديث الذي الحقول الآن على الرغم من؟ 774 00:33:21,332 --> 00:33:23,210 موافق، حجم بالتأكيد. 775 00:33:23,210 --> 00:33:26,430 وماذا عن الجبهة؟ 776 00:33:26,430 --> 00:33:27,040 حسنا، لا. 777 00:33:27,040 --> 00:33:30,200 لا ينبغي أن يغير الجبهة، لأن على عكس كومة، ونحن 778 00:33:30,200 --> 00:33:31,370 يريدون الحفاظ على الإنصاف. 779 00:33:31,370 --> 00:33:35,150 حتى إذا جاء في أول 9، ونحن نريد 9 ليكون من أول السطر 780 00:33:35,150 --> 00:33:36,420 وإلى المتجر. 781 00:33:36,420 --> 00:33:37,220 >> في الواقع، دعونا نرى ذلك. 782 00:33:37,220 --> 00:33:42,235 قبل أن إدراج 22، دعنا المضي قدما وdequeue 9. 783 00:33:42,235 --> 00:33:42,970 ما اسمك مرة أخرى؟ 784 00:33:42,970 --> 00:33:43,680 >> الجمهور: جيك. 785 00:33:43,680 --> 00:33:45,440 >> DAVID مالان: جيك يجري أن dequeued الآن. 786 00:33:45,440 --> 00:33:48,050 حتى تحصل على السير في المخزن. 787 00:33:48,050 --> 00:33:49,880 وأدعي أن المخزن هو هناك. 788 00:33:49,880 --> 00:33:51,970 وحتى الآن ما يحتاج - ديت ديت--ديت! 789 00:33:51,970 --> 00:33:53,400 ما يجب أن يحدث الآن؟ 790 00:33:53,400 --> 00:33:54,490 قرار التصميم. 791 00:33:54,490 --> 00:33:56,825 حتى لا غريزة سيئة، ولكن - ما اسمك مرة أخرى؟ 792 00:33:56,825 --> 00:33:57,090 >> الجمهور: ديفيد. 793 00:33:57,090 --> 00:33:57,500 >> DAVID مالان: ديفيد. 794 00:33:57,500 --> 00:33:58,810 وذلك ما لم ديفيد تفعل؟ 795 00:33:58,810 --> 00:34:02,590 كان يحاول إصلاح نوع من البيانات هيكل والانتقال من مكان وجوده 796 00:34:02,590 --> 00:34:04,100 في مكان وجيك السابق. 797 00:34:04,100 --> 00:34:06,740 وهذا شيء طيب إذا كنا على استعداد لقبول ذلك باعتباره 798 00:34:06,740 --> 00:34:08,199 التفاصيل التنفيذ. 799 00:34:08,199 --> 00:34:11,100 ولكن أولا، دعونا تحديث البيانات هيكل قبل ان نفعل ذلك. 800 00:34:11,100 --> 00:34:14,139 لأنني لا تروق فكرة عن الشعب تحول في هذا الخط. 801 00:34:14,139 --> 00:34:17,360 >> انها ليست صفقة كبيرة إذا ديفيد يفعل مع خطوة واحدة، ولكن مرة أخرى، والتفكير مرة أخرى إلى 802 00:34:17,360 --> 00:34:20,360 عندما كان لدينا ثمانية متطوعين على تنظيم وفعلناه مثل الإدراج 803 00:34:20,360 --> 00:34:22,600 النوع، حيث كان علينا أن نبدأ يتحرك الجميع حولها. 804 00:34:22,600 --> 00:34:23,790 التي حصلت مكلفة، أليس كذلك؟ 805 00:34:23,790 --> 00:34:28,330 هذا يجعلني ارتد عن كبير O ن، التربيعية يا كبير من ن مرة أخرى. 806 00:34:28,330 --> 00:34:30,650 انها ليست مثل شعور نتيجة مثالية. 807 00:34:30,650 --> 00:34:32,080 >> لذلك دعونا فقط بتحديث هذا. 808 00:34:32,080 --> 00:34:35,120 وبالتالي فإن حجم قائمة الانتظار لم يعد 2. 809 00:34:35,120 --> 00:34:37,090 انها الآن مجرد 1. 810 00:34:37,090 --> 00:34:40,360 ولكن يمكنني الآن بتحديث شيئا لم أكن تحديث من قبل، و 811 00:34:40,360 --> 00:34:41,130 أمام القائمة. 812 00:34:41,130 --> 00:34:45,420 ويمكنني أن أقول فقط، هو ذلك الموقع 1؟ 813 00:34:45,420 --> 00:34:49,770 حتى الآن لدينا قيمة القمامة هنا، قيمة القمامة هنا، وداود في 814 00:34:49,770 --> 00:34:51,469 وسط هذه القمامة. 815 00:34:51,469 --> 00:34:54,980 ولكن بنية البيانات لا تزال سليمة. 816 00:34:54,980 --> 00:34:58,540 >> في واقع الأمر، وأنا لا تحتاج حتى ل تغيير رقم جيك السابق 817 00:34:58,540 --> 00:35:00,460 9، وذلك لأن الذي يهتم. 818 00:35:00,460 --> 00:35:04,470 لدي ما يكفي من المعلومات الآن في حجم وأنا أعلم أن هناك شخص واحد في 819 00:35:04,470 --> 00:35:05,030 قائمة الانتظار هذه. 820 00:35:05,030 --> 00:35:08,340 وأنا أعلم أن هذا الشخص هو في موقع 1، 0 لا. 821 00:35:08,340 --> 00:35:09,760 أنا لا عد. 822 00:35:09,760 --> 00:35:11,300 حتى 1 كذلك. 823 00:35:11,300 --> 00:35:13,410 وبالتالي فإن بنية البيانات لا تزال موافق. 824 00:35:13,410 --> 00:35:14,330 >> حسنا، ماذا سيحدث بعد ذلك؟ 825 00:35:14,330 --> 00:35:15,010 دعونا إدراج بقائمة الانتظار - 826 00:35:15,010 --> 00:35:15,370 ما اسمك؟ 827 00:35:15,370 --> 00:35:16,160 >> الجمهور: كالين. 828 00:35:16,160 --> 00:35:16,580 >> DAVID مالان: كالين. 829 00:35:16,580 --> 00:35:20,770 دعونا إدراج بقائمة الانتظار وكالين، و 22 هو الآن في قائمة الانتظار. 830 00:35:20,770 --> 00:35:22,300 وحتى الآن ما يجب أن يتغير هنا؟ 831 00:35:22,300 --> 00:35:24,380 الجبهة لن تغيير، ومن الواضح. 832 00:35:24,380 --> 00:35:27,160 حجم سيتغير ليكون 2 مرة أخرى. 833 00:35:27,160 --> 00:35:31,590 و22 ينتهي هنا، 9 لا تزال موجودة، لكنه فعال 834 00:35:31,590 --> 00:35:32,600 قيمة القمامة الآن. 835 00:35:32,600 --> 00:35:35,910 انها مجرد بقايا جيك الماضية. 836 00:35:35,910 --> 00:35:39,200 >> وحتى الآن ماذا يحدث إذا أنا dequeue ديفيد؟ 837 00:35:39,200 --> 00:35:41,560 عملية واحدة الماضي، dequeue ديفيد. 838 00:35:41,560 --> 00:35:46,070 نحن يمكن أن يتحول، ولكن أقترح السماح لل القيام بعمل أقل قدر ممكن. 839 00:35:46,070 --> 00:35:50,280 الآن يذهب بنية البيانات الخاصة بي مرة أخرى في حجم 2-1. 840 00:35:50,280 --> 00:35:53,730 ولكن الجزء الأمامي من الطابور يصبح الآن 2. 841 00:35:53,730 --> 00:35:56,640 ولست بحاجة لتغيير هذه الأرقام فقط حتى الآن، لأنهم 842 00:35:56,640 --> 00:35:58,230 القيم القمامة فقط. 843 00:35:58,230 --> 00:35:59,720 >> ولكن ما يحدث الآن؟ 844 00:35:59,720 --> 00:36:03,280 افترض إدراج بقائمة الانتظار نفسي، 26؟ 845 00:36:03,280 --> 00:36:05,890 أشعر أنني أنتمي إلى هنا. 846 00:36:05,890 --> 00:36:06,890 لذلك أنا يجري enqueued. 847 00:36:06,890 --> 00:36:08,760 لذلك أنا نوع من ينتمون هنا. 848 00:36:08,760 --> 00:36:11,300 وعلى الرغم من أنك لا تماما نقدر هذا بصريا على المسرح، 849 00:36:11,300 --> 00:36:15,075 لأن لدينا الكثير من الغرفة، ينبغي لي لا أن يقف هنا، لماذا؟ 850 00:36:15,075 --> 00:36:16,290 >> الحضور: أنت خارج الحدود. 851 00:36:16,290 --> 00:36:16,370 >> DAVID مالان: الحق. 852 00:36:16,370 --> 00:36:16,940 أنا خارج الحدود. 853 00:36:16,940 --> 00:36:19,330 لقد فهرستها وراء حدود هذه المجموعة. 854 00:36:19,330 --> 00:36:23,420 أنا حقا يجب أن يكون في واحدة من ثلاثة مواقع ممكن. 855 00:36:23,420 --> 00:36:25,150 الآن، أين الأكثر طبيعية أن تذهب؟ 856 00:36:25,150 --> 00:36:27,760 أقترح أننا الاستدانة أسبوع خدعة واحدة. 857 00:36:27,760 --> 00:36:30,150 المشغل وزارة الدفاع، والنسبة المئوية. 858 00:36:30,150 --> 00:36:36,850 لأنني أقف من الناحية الفنية في موقع 3، لكنني 3 قدرة وزارة الدفاع، 859 00:36:36,850 --> 00:36:40,250 حتى 3، علامة النسبة المئوية، 3 - 860 00:36:40,250 --> 00:36:40,970 قدرة 3. 861 00:36:40,970 --> 00:36:41,720 ما هذا؟ 862 00:36:41,720 --> 00:36:43,700 ما هو الباقي عند قمت بتقسيم 3 بنسبة 3؟ 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> بحيث يضع لي كان كان جيك، وهو أمر جيد فعلا. 865 00:36:48,140 --> 00:36:50,370 وحتى الآن تنفيذ من يحدث هذا الشيء ل 866 00:36:50,370 --> 00:36:51,250 يكون قليلا من الصداع. 867 00:36:51,250 --> 00:36:53,740 انها حقا سطر واحد فقط من صداع، من التعليمات البرمجية. 868 00:36:53,740 --> 00:36:56,580 ولكن على الأقل الآن هناك القمامة قيمة هنا، ولكن هناك اثنين 869 00:36:56,580 --> 00:36:57,910 رجات المشروعة هنا. 870 00:36:57,910 --> 00:37:04,160 وأزعم أن الآن قمنا به بالضبط ما يتعين علينا القيام به طالما 871 00:37:04,160 --> 00:37:08,600 نغير ما في جيك كانت قيمة أن تكون 26. 872 00:37:08,600 --> 00:37:12,110 >> لدينا الآن ما يكفي من المعلومات لا تزال للحفاظ على سلامة 873 00:37:12,110 --> 00:37:13,060 هذه البنية البيانات. 874 00:37:13,060 --> 00:37:17,160 ما زلنا نوع من الخروج من الحظ عندما كنا تريد إدراج أربعة أو أكثر من مجموع 875 00:37:17,160 --> 00:37:20,740 العناصر، لكنني يمكن أن تجعل ما لا يقل عن جميلة كفاءة استخدام هذا الثابت 876 00:37:20,740 --> 00:37:21,740 الوقت، في الواقع. 877 00:37:21,740 --> 00:37:27,150 أنا لا داعي للقلق حول تحويل كان الجميع، والميل داود. 878 00:37:27,150 --> 00:37:30,816 >> أي أسئلة حول مداخن، أو قائمة الانتظار هذه؟ 879 00:37:30,816 --> 00:37:32,184 >> الحضور: هل السبب كنت بحاجة إلى حجم حتى تعرف 880 00:37:32,184 --> 00:37:34,010 حيث أن يكون الشخص؟ 881 00:37:34,010 --> 00:37:34,770 >> DAVID مالان: بالضبط. 882 00:37:34,770 --> 00:37:38,230 ولست بحاجة لمعرفة حجم المصفوفة لأنني بحاجة إلى معرفة بالضبط كيف 883 00:37:38,230 --> 00:37:41,940 العديد من هذه القيم هي مشروعة، وبحيث يمكنني العثور على مكان لوضع 884 00:37:41,940 --> 00:37:42,800 الشخص التالي. 885 00:37:42,800 --> 00:37:43,300 بالضبط. 886 00:37:43,300 --> 00:37:44,580 حجم هو - 887 00:37:44,580 --> 00:37:46,360 في الواقع، لم نكن تحديث هذا الموضوع حتى الآن. 888 00:37:46,360 --> 00:37:48,380 وأضاف أنا نفسي في 26. 889 00:37:48,380 --> 00:37:51,760 حجم هو الآن، وليس 1، ولكن 2. 890 00:37:51,760 --> 00:37:57,780 وحتى الآن وهذا يساعد في الواقع لي العثور على رئيس القائمة، والتي هي ليست 0، وليس 891 00:37:57,780 --> 00:37:59,250 1، ولكن هو 2. 892 00:37:59,250 --> 00:38:01,665 الجزء الأمامي من قائمة هو في الواقع عدد 22. 893 00:38:01,665 --> 00:38:05,120 لأنه جاء في الأولى، حتى انه ينبغي يسمح في مخزن قبلي، 894 00:38:05,120 --> 00:38:08,780 على الرغم من بصريا انا واقفة أقرب إلى المخزن. 895 00:38:08,780 --> 00:38:09,220 >> كل الحق؟ 896 00:38:09,220 --> 00:38:12,410 جولة من التصفيق لهؤلاء الرجال ونحن سوف تتيح لهم للخروج من هناك. 897 00:38:12,410 --> 00:38:17,090 >> [تصفيق] 898 00:38:17,090 --> 00:38:18,150 >> DAVID مالان: أنا يمكن أن تسمح عليك أن تبقي الدرج. 899 00:38:18,150 --> 00:38:20,760 يمكننا أن نرى ماذا يحدث إذا تريد، ولكن ربما لا. 900 00:38:20,760 --> 00:38:21,590 حسنا. 901 00:38:21,590 --> 00:38:25,380 حتى الآن ما لا تترك لنا؟ 902 00:38:25,380 --> 00:38:28,900 حسنا، اسمحوا لي أن أقترح أن هناك قليل من هياكل البيانات الأخرى التي يمكن 903 00:38:28,900 --> 00:38:33,810 البدء في إضافة إلى مجموعة من الأدوات التي من شأنها دينا يكون في الواقع تماما، تماما كما ذات الصلة 904 00:38:33,810 --> 00:38:35,270 نحن يغوص في الاشياء على شبكة الإنترنت. 905 00:38:35,270 --> 00:38:38,150 والتي مرة أخرى، لديه بعض النوع من الاتصال إلى الأشجار في شكل 906 00:38:38,150 --> 00:38:40,550 ما يسمى DOM، وثيقة نموذج كائن. 907 00:38:40,550 --> 00:38:42,370 ولكن سنرى أكثر من أن قبل فترة طويلة. 908 00:38:42,370 --> 00:38:46,260 >> اسمحوا لي أن أقترح أننا definitionally استدعاء الشجرة الآن ما يمكن أن تعرف باسم 909 00:38:46,260 --> 00:38:48,820 أكثر من شجرة العائلة، حيث يمكنك لدينا بعض السلف في 910 00:38:48,820 --> 00:38:49,790 جذور شجرة. 911 00:38:49,790 --> 00:38:54,480 A الأبوية أو الأم الحاكمة في أعلى جدا من الشجرة. 912 00:38:54,480 --> 00:38:56,700 دون أزواجهن، في هذه الحالة. 913 00:38:56,700 --> 00:39:00,940 ولكن لدينا الآن ما سنقوم بالاتصال الأطفال، والتي هي العقد التي شنق 914 00:39:00,940 --> 00:39:05,480 قبالة الطفل اليسرى أو اليمنى للطفل، الأسهم كما هو مبين هنا. 915 00:39:05,480 --> 00:39:10,490 >> وبعبارة أخرى، في بنية البيانات شجرة في الكمبيوتر، وشجرة لديه صفر 916 00:39:10,490 --> 00:39:11,480 أو أكثر من العقد. 917 00:39:11,480 --> 00:39:13,500 إذا كان لديه عقدة واحدة على الأقل، وهذا ما يسمى الجذر. 918 00:39:13,500 --> 00:39:15,700 انها الأشياء بصريا أن نلفت في الأعلى. 919 00:39:15,700 --> 00:39:20,280 وتلك العقدة، مثل أي عقدة أخرى، يمكن لديك صفر، واحد، أو اثنين، أو ثلاثة، 920 00:39:20,280 --> 00:39:23,600 أو ولكن العديد من الأطفال يدعم هيكل البيانات. 921 00:39:23,600 --> 00:39:29,150 في هذه الحالة، الجذر، تخزين قيمة واحدة، لديه طفلان و 2 و 3، 922 00:39:29,150 --> 00:39:33,020 لذلك نحن ندعو عموما 2 اليسار الأطفال و3 الطفل الصحيح. 923 00:39:33,020 --> 00:39:36,940 >> وبعد ذلك عندما نصل الى 5، 6، و 7، 6 يمكن أن يطلق عليه الطفل الأوسط. 924 00:39:36,940 --> 00:39:38,940 إذا كان لديك أربعة أطفال، فإنه يحصل مربكة. 925 00:39:38,940 --> 00:39:42,260 ولذا فإننا التوقف عن استخدام هذا النوع من اختصار لفظيا. 926 00:39:42,260 --> 00:39:44,580 لكنها في الحقيقة مجرد شجرة العائلة. 927 00:39:44,580 --> 00:39:48,880 ويترك هنا العقد التي أنفسهم ليس لديهم أطفال. 928 00:39:48,880 --> 00:39:52,540 انهم شنق قبالة الجزء السفلي من الشجرة. 929 00:39:52,540 --> 00:39:56,940 >> فكيف يمكن أن ننفذ الشجرة التي فقد اثنين من الأطفال فقط إلى الحد الأقصى؟ 930 00:39:56,940 --> 00:39:58,410 سنقوم نسميها شجرة ثنائية. 931 00:39:58,410 --> 00:40:00,960 ثنائية يعني مرة أخرى اثنين، في هذا الحالة، كما هو الحال مع ثنائي. 932 00:40:00,960 --> 00:40:04,830 ولذا فإنه يمكن أن يكون صفر، واحد، أو طفلين الحد الأقصى. 933 00:40:04,830 --> 00:40:08,650 >> أنا أقترح أن ننفذ العقدة لهذا الهيكل مع ن الباحث، 934 00:40:08,650 --> 00:40:11,910 ثم اثنين من المؤشرات، واحدة تسمى اليسار، واحد يسمى الحق. 935 00:40:11,910 --> 00:40:14,830 ولكن تلك هي لطيفة فقط الاتفاقيات التعسفي. 936 00:40:14,830 --> 00:40:18,170 وعلى ما هو جميل الآن، خصوصا إذا كنت نوع من ناضل من الناحية المفاهيمية مع 937 00:40:18,170 --> 00:40:21,300 العودية، أو يعتقد أنه لم يكن حقا حل لأي شيء، 938 00:40:21,300 --> 00:40:23,120 خاصة إذا كنت قد نفاد الذاكرة. 939 00:40:23,120 --> 00:40:26,600 الآن أننا نتحدث عن البيانات الهياكل والخوارزميات التي تسمح 940 00:40:26,600 --> 00:40:31,030 لنا لتعبر والتلاعب بها، تبين أن يعود في العودية 941 00:40:31,030 --> 00:40:34,240 أكثر إقناعا إن لم يكن بطريقة جميلة. 942 00:40:34,240 --> 00:40:38,670 >> لذلك هذا أقترح هو تنفيذ وظيفة البحث. 943 00:40:38,670 --> 00:40:39,870 نظرا اثنين من المدخلات - 944 00:40:39,870 --> 00:40:41,570 لذلك أعتقد أن هذا بمثابة الصندوق الأسود. 945 00:40:41,570 --> 00:40:46,560 نظرا اثنين من المدخلات، ن، وكثافة العمليات، و مؤشر إلى شجرة، مؤشر إلى 946 00:40:46,560 --> 00:40:50,020 العقدة، أو حقا جذر شجرة، وأنا يزعمون أن هذه الوظيفة يمكن العودة 947 00:40:50,020 --> 00:40:53,530 صحيحة أو خاطئة، أن قيمة ن داخل هذه الشجرة. 948 00:40:53,530 --> 00:40:55,210 >> ما داخل هذا المربع الأسود؟ 949 00:40:55,210 --> 00:40:57,440 حسنا، أربعة فروع. 950 00:40:57,440 --> 00:40:58,385 أول يتحقق فقط. 951 00:40:58,385 --> 00:41:00,490 إذا الشجرة هو باطل، والعودة فقط كاذبة. 952 00:41:00,490 --> 00:41:04,580 اذا لم يكن هناك عقدة، وليس هناك ن، ليس هناك عدد، والعودة فقط كاذبة. 953 00:41:04,580 --> 00:41:12,330 إذا رغم ذلك، ن، القيمة التي تبحث ل، هو أقل من شجرة السهم ن، و 954 00:41:12,330 --> 00:41:15,180 لمجرد أن يكون واضحا، ماذا يعني عندما أنا أكتب شجرة ثم السهم 955 00:41:15,180 --> 00:41:18,150 التدوين، ن؟ 956 00:41:18,150 --> 00:41:18,690 بالضبط. 957 00:41:18,690 --> 00:41:21,970 وهو ما يعني إلغاء مرجعية التي دعا مؤشر شجرة. 958 00:41:21,970 --> 00:41:26,750 الذهاب إلى هناك، ومن ثم الحصول على داخل ذلك عقدة والحصول على مجالها دعا ن. 959 00:41:26,750 --> 00:41:30,810 ثم قارن ن الفعلية التي كان مرت في البحث ضدها. 960 00:41:30,810 --> 00:41:35,390 >> حتى إذا كان n أقل من، قيمة ن في عقدة الشجرة نفسها، وأيضا، 961 00:41:35,390 --> 00:41:36,720 ماذا يعني ذلك؟ 962 00:41:36,720 --> 00:41:40,690 هذا لا يعني شيئا للوهلة الأولى. 963 00:41:40,690 --> 00:41:40,900 أليس كذلك؟ 964 00:41:40,900 --> 00:41:45,560 تماما مثل عندما يكون لديك مجموعة من القيم، قد ترغب في تطبيق ثنائي 965 00:41:45,560 --> 00:41:48,290 بحث كشكل من أشكال الانقسام وقهر. 966 00:41:48,290 --> 00:41:51,790 ولكن ما لم الافتراض نحن بحاجة لجعل للبحث ثنائي للعمل في جميع 967 00:41:51,790 --> 00:41:54,510 في دفتر الهاتف و أمثلة في وقت سابق؟ 968 00:41:54,510 --> 00:41:55,530 >> كيف يمكن فرز. 969 00:41:55,530 --> 00:41:59,490 لذلك دعونا صقل تعريف شجرة هنا لا يجب أن يكون مجرد شجرة، والتي يمكن 970 00:41:59,490 --> 00:42:00,880 لديك أي عدد من الأطفال. 971 00:42:00,880 --> 00:42:04,700 وليس فقط شجرة ثنائية، والتي يمكن لديك 0، 1، 2 أو الحد الأقصى. 972 00:42:04,700 --> 00:42:09,700 ولكن مثل شجرة البحث الثنائي، أو BST، الذي هو مجرد طريقة أخرى للقول ل 973 00:42:09,700 --> 00:42:15,430 شجرة ثنائية مثل أن كل عقدة الطفل الأيسر، إذا كان موجودا، هو 974 00:42:15,430 --> 00:42:16,830 أقل من العقدة. 975 00:42:16,830 --> 00:42:20,170 والحق طفل كل عقدة، إذا كان موجودا، هو أكبر 976 00:42:20,170 --> 00:42:21,740 من العقدة نفسها. 977 00:42:21,740 --> 00:42:25,200 >> لذلك وبعبارة أخرى، إذا كنت لرسم شجرة خارج، كل من الأرقام 978 00:42:25,200 --> 00:42:30,620 متوازنة بعناية من هذا القبيل بحيث إذا لديك 55 كجذر، 33 يمكن أن تذهب 979 00:42:30,620 --> 00:42:33,090 إلى اليسار لأنها أقل من 55. 980 00:42:33,090 --> 00:42:36,430 77 يمكن أن تذهب إلى اليمين، ذلك لأن انها أكبر من 55. 981 00:42:36,430 --> 00:42:40,750 ولكن الآن لاحظت، ونفس التعريف، انها تعريف العودية لفظيا، 982 00:42:40,750 --> 00:42:42,600 يجب أن تطبق لمدة 33. 983 00:42:42,600 --> 00:42:47,610 يجب أن يكون 33 في الطفل اليسرى أقل من ذلك، و 33 في حق الطفل، 44، يجب أن يكون 984 00:42:47,610 --> 00:42:48,580 أكبر من ذلك. 985 00:42:48,580 --> 00:42:51,670 >> لذلك هذا هو الشجرة البحث الثنائي، و أقترح، وذلك باستخدام قليلا من 986 00:42:51,670 --> 00:42:53,910 العودية، يمكننا الآن العثور ن. 987 00:42:53,910 --> 00:42:59,160 حتى إذا كان n أقل من قيمة ن هذا عقدة الحالي، وانا ذاهب للذهاب 988 00:42:59,160 --> 00:43:04,090 قدما والبونت، إذا جاز التعبير، وعادل العودة مهما كان الجواب من 989 00:43:04,090 --> 00:43:08,470 البحث عن ن على الطفل الشجرة اليسرى. 990 00:43:08,470 --> 00:43:11,370 لاحظ مرة أخرى، هذه الوظيفة فقط وتتوقع نجم عقدة، و 991 00:43:11,370 --> 00:43:12,780 مؤشر إلى العقدة. 992 00:43:12,780 --> 00:43:17,360 ذلك بالتأكيد يمكنني القيام به للتو شجرة سهم اليسار، الأمر الذي سيؤدي 993 00:43:17,360 --> 00:43:18,400 لي إلى عقدة أخرى. 994 00:43:18,400 --> 00:43:19,480 ولكن ما هو تلك العقدة؟ 995 00:43:19,480 --> 00:43:22,820 >> حسنا، وفقا لهذا الإعلان، اليسار هو مجرد مؤشر، بحيث فقط 996 00:43:22,820 --> 00:43:27,090 يعني أنا عابرة إلى وظيفة البحث مؤشر مختلفة، وهي 997 00:43:27,090 --> 00:43:30,750 واحد الذي يمثل شجرة يساري الطفل. 998 00:43:30,750 --> 00:43:36,040 حتى في هذه الحالة، المؤشر إلى 33، إذا هذا هو موقفنا عينة المدخلات وفي الوقت نفسه، إذا 999 00:43:36,040 --> 00:43:40,740 n هو أكبر من قيمة ن في العقدة الحالية في الشجرة، ثم أنا 1000 00:43:40,740 --> 00:43:43,370 ذاهب الى المضي قدما والبونت في الآخر التوجيه ونقول فقط، وأنا لا 1001 00:43:43,370 --> 00:43:47,280 أعرف إذا كان هذا قيمة n هو في شجرة، لكنني أعرف ما إذا كان هو، انها أسفل بلدي 1002 00:43:47,280 --> 00:43:49,090 فرع الحق، إذا جاز التعبير. 1003 00:43:49,090 --> 00:43:53,120 لذلك اسمحوا لي استدعاء متكرر بحث، تمرير ن مرة أخرى، ولكن يمر في 1004 00:43:53,120 --> 00:43:54,580 مؤشر إلى حقي الطفل. 1005 00:43:54,580 --> 00:44:00,020 >> وبعبارة أخرى، إذا أنا حاليا في 55 وأنا أبحث عن 99، وأنا أعرف أن 99 1006 00:44:00,020 --> 00:44:04,270 هو أكبر من 55، وذلك فقط مثل أنا مزقت الأسابيع دفتر الهاتف، ونحن منذ 1007 00:44:04,270 --> 00:44:07,140 ذهب الحق، نحن بالمثل سوف يسير في الاتجاه الصحيح هنا. 1008 00:44:07,140 --> 00:44:11,960 وأنا لا أعرف ما اذا كان في حقي الطفل، وانها ليست، 77 هناك، ولكن 1009 00:44:11,960 --> 00:44:13,210 وأنا أعلم أنه في هذا الاتجاه. 1010 00:44:13,210 --> 00:44:18,770 لذلك أدعو البحث على حقي الطفل، 77، والسماح الرقم الخروج من البحث 1011 00:44:18,770 --> 00:44:24,950 هناك إذا 99 في هذا التعسفي مثال على ذلك هو في الواقع هناك. 1012 00:44:24,950 --> 00:44:26,900 >> آخر، ما هو الحال النهائي؟ 1013 00:44:26,900 --> 00:44:28,620 إذا شجرة باطل هو حالة واحدة. 1014 00:44:28,620 --> 00:44:31,890 إذا كان n أقل من العقدة الحالية القيمة هي قضية أخرى. 1015 00:44:31,890 --> 00:44:35,120 إذا كان n أكبر من الحالية قيمة العقدة هي الحالة الثالثة. 1016 00:44:35,120 --> 00:44:38,250 ما هي الحالة الرابعة والأخيرة؟ 1017 00:44:38,250 --> 00:44:39,480 أعتقد نحن من الحالات، أليس كذلك؟ 1018 00:44:39,480 --> 00:44:44,690 يجب أن يكون ذلك n هو في العقدة الحالية التي أنا على. 1019 00:44:44,690 --> 00:44:49,640 >> حتى إذا أنا في البحث عن 55 في هذه المرحلة في القصة، وهذا فرع من فروع 1020 00:44:49,640 --> 00:44:51,780 أن شجرة العودة الحقيقية. 1021 00:44:51,780 --> 00:44:55,380 فما هو المثير للاهتمام هنا هو أننا في الواقع، على عكس الأسابيع الماضية، نحن نوع 1022 00:44:55,380 --> 00:44:56,740 من لديها حالتين القاعدة. 1023 00:44:56,740 --> 00:44:58,300 وليس لديهم ل يكون كل في الأعلى. 1024 00:44:58,300 --> 00:45:01,390 الأعلى هو الحالة الأساسية لأنه إذا كان شجرة باطل، وهناك شيء للقيام به. 1025 00:45:01,390 --> 00:45:03,410 فقط إرجاع الثابت ترميز قيمة خاطئة. 1026 00:45:03,410 --> 00:45:07,400 >> الفرع السفلي هو نوع من الافتراضي، حيث إذا قمنا فحص ل 1027 00:45:07,400 --> 00:45:11,550 فارغة، لقد فحص ما اذا كان ينبغي أن يكون اليسار، ولكن لا ينبغي أن يكون، لدينا 1028 00:45:11,550 --> 00:45:14,640 فحص إذا كان ينبغي أن يكون على حق، لكنها لا ينبغي أن يكون من الواضح أنه يجب أن يكون 1029 00:45:14,640 --> 00:45:15,870 الحق ما نحن فيه. 1030 00:45:15,870 --> 00:45:16,780 وهذا هو حال القاعدة. 1031 00:45:16,780 --> 00:45:19,920 لذلك هناك حالتين العودية تقع هناك في الوسط. 1032 00:45:19,920 --> 00:45:21,630 ولكن كان بوسعي أن أكتب هذا في أي أمر. 1033 00:45:21,630 --> 00:45:24,520 أنا فقط أعتقد أنه نوع من شعر طبيعي للتحقق أول لخطأ ممكن، 1034 00:45:24,520 --> 00:45:28,340 ثم تحقق اليسار، ثم تحقق الحق، ثم نفترض أن كنت في عقدة 1035 00:45:28,340 --> 00:45:30,630 كنت فعلا تبحث عن. 1036 00:45:30,630 --> 00:45:36,240 >> فلماذا هذا قد يكون مفيدا؟ 1037 00:45:36,240 --> 00:45:37,910 حتى اتضح - 1038 00:45:37,910 --> 00:45:42,110 واسمحوا لي أن تقفز إلى دعابة هنا وهذا في شبكة الإنترنت. 1039 00:45:42,110 --> 00:45:44,920 ونحن في طريقنا للبدء في استخدام ليس لغة البرمجة في البداية، ولكن 1040 00:45:44,920 --> 00:45:46,030 لغة الترميز. 1041 00:45:46,030 --> 00:45:48,740 لغة ترميز كائن واحد وهذا مماثلة للبرمجة 1042 00:45:48,740 --> 00:45:51,715 اللغة، لكنها لا تعطيك القدرة على التعبير عن نفسك منطقيا. 1043 00:45:51,715 --> 00:45:55,070 إلا أنها تعطيك القدرة على التعبير عن نفسك هيكليا. 1044 00:45:55,070 --> 00:45:57,960 >> أين تريد وضع شيء على الصفحة، صفحة الويب؟ 1045 00:45:57,960 --> 00:45:59,200 ما اللون الذي تريد أن تجعل من؟ 1046 00:45:59,200 --> 00:46:00,950 ما حجم الخط هل تريد أن تجعل من؟ 1047 00:46:00,950 --> 00:46:02,970 ما الكلمات هل فعلا تريد على صفحة الويب؟ 1048 00:46:02,970 --> 00:46:04,060 ذلك أن لغة ترميز. 1049 00:46:04,060 --> 00:46:07,690 ولكن بعد ذلك نحن سوف أعرض بشكل سريع جدا جافا سكريبت، وهو العضوية الكاملة 1050 00:46:07,690 --> 00:46:08,560 لغة البرمجة. 1051 00:46:08,560 --> 00:46:12,530 بناء جملة مشابهة جدا في المظهر لC، ولكنه سيكون لديك بعض 1052 00:46:12,530 --> 00:46:15,200 لطيفة، وأكثر قوة، وأكثر ميزات سهلة الاستخدام. 1053 00:46:15,200 --> 00:46:18,050 >> واحدة من الإحباط في هذا نقطة في الفصل الدراسي هو أننا سوف 1054 00:46:18,050 --> 00:46:22,065 قريبا تنفيذ سبيلر في عدد أقل بكثير الأسطر من التعليمات البرمجية باستخدام لغات أخرى 1055 00:46:22,065 --> 00:46:25,580 من C نفسها تسمح، ولكن لسبب و سنقوم فهم قريبا. 1056 00:46:25,580 --> 00:46:27,750 وستكون هذه أول صفحة ويب من هذا القبيل. 1057 00:46:27,750 --> 00:46:30,120 سيكون مخيب تماما، أول واحد التي نتخذها. 1058 00:46:30,120 --> 00:46:31,400 فإنه سيقول ببساطة، مرحبا العالم. 1059 00:46:31,400 --> 00:46:34,010 ولكن إذا كنت لم أر قط ذلك من قبل، وهذا هو HTML، 1060 00:46:34,010 --> 00:46:35,670 لغة توصيف النص التشعبي. 1061 00:46:35,670 --> 00:46:39,310 >> إذا ذهبت إلى خيار القائمة معينة في أكثر من أي متصفح، على أي صفحة على شبكة الإنترنت 1062 00:46:39,310 --> 00:46:43,160 الانترنت، يمكنك أن ترى HTML أن بعض الناس كتب ل 1063 00:46:43,160 --> 00:46:44,400 خلق هذا صفحة ويب. 1064 00:46:44,400 --> 00:46:47,850 وربما لا تبدو كما موجزة أو أنيق مثل هذا. 1065 00:46:47,850 --> 00:46:51,400 ولكنه سوف تتبع نمط من هذه الأقواس المفتوحة ومائلة و 1066 00:46:51,400 --> 00:46:53,660 الرسائل ويحتمل أن تكون الأرقام. 1067 00:46:53,660 --> 00:46:56,770 >> ظننت أنني كنت أعطيك دعابة ما عليك أن تكون قادرا على القيام 1068 00:46:56,770 --> 00:46:57,950 بعد أخذ CS50. 1069 00:46:57,950 --> 00:47:02,620 اسمحوا لي أن انتقل إلى cs.harvard.edu / سرقة، لدينا موقع روب بودين الخاصة. 1070 00:47:02,620 --> 00:47:06,080 الذي أدلى به هذا بالنسبة لنا. 1071 00:47:06,080 --> 00:47:07,490 لذلك عليك أن تكون قادرة على القيام بذلك قريبا. 1072 00:47:07,490 --> 00:47:10,660 وأيضا، ما سمعت هذا الصباح - 1073 00:47:10,660 --> 00:47:12,480 ما سمعت هذا الصباح - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - اختر مربع الطباعة تكون قادرة على جعل هذا. 1076 00:47:15,702 --> 00:47:16,790 التي تنتظرنا يوم الاربعاء. 1077 00:47:16,790 --> 00:47:17,791 سوف نرى لك ذلك الحين. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID مالان: في CS50 المقبل - 1080 00:47:24,300 --> 00:47:31,670