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