رئيس 1: كل الحق، لذلك هذا هو CS50 هذا هو نهاية الأسبوع الخمسة. وأذكر أن آخر مرة كنا بدأت تبحث في البيانات مربي الحيوانات الهياكل التي بدأت في حل المشاكل، التي بدأت في إدخال مشاكل جديدة، ولكن المفتاح لهذا وكان هذا النوع من خيوط أننا بدأت تفعل من عقدة إلى عقدة. لذلك هذا بالطبع هو قائمة مرتبطة منفردة. وترتبط منفردة، أعني هناك واحد فقط ترابط بين كل من هذه العقد. اتضح يمكنك القيام به مربي الحيوانات أشياء مثل القوائم المرتبطة على نحو مضاعف حيث لديك السهم تسير في كلا الاتجاهين، والتي يمكن أن تساعد مع بعض الكفاءات. ولكن هذا حل المشكلة؟ ما هي المشكلة أن هذا حل؟ لماذا نهتم يوم الاثنين؟ لماذا، من الناحية النظرية، لم نهتم يوم الاثنين؟ ماذا يفعل؟ الحضور: نحن يمكن تغيير حجم بشكل حيوي. رئيس 1: OK، حتى نتمكن من حيوي حجمه. حسنا فعلت كل واحد منكما. حتى تتمكن من تغيير هذا حيوي هيكل البيانات، في حين صفيف، أذكر، عليك أن تعرف بداهة مقدار المساحة التي تريدها وإذا كنت بحاجة إلى القليل من أكثر الفضاء، وكنت نوع من الخروج من الحظ. لديك لإنشاء مجموعة جديدة كاملة. لديك لنقل كافة بك بيانات من واحدة إلى أخرى، في نهاية المطاف سراح مجموعة القديمة إذا كنت تستطيع، ثم المضي قدما. الذي فقط يشعر مكلفة جدا وجدا غير فعالة، بل ويمكن أن يكون. ولكن هذا ليس كل شيء جيد. نحن ندفع ثمنا، ما كان احد أسعار أكثر وضوحا نحن دفع باستخدام قائمة مرتبطة؟ الحضور: لدينا لاستخدام مساحة مزدوج لكل واحد. رئيس 1: نعم، لذلك نحن بحاجة ما لا يقل عن ضعف مساحة كبيرة. في الواقع، أدركت هذه الصورة ل حتى مضللة بعض الشيء، لأنه في IDE CS50 في الكثير من الحديث أجهزة الكمبيوتر، مؤشر أو عنوان ليس في الواقع أربعة بايت. انها في كثير من الأحيان هذه ثمانية أيام بايت، والذي يعني أسفل أكثر المستطيلات هناك في الواقع هي نوع من ضعف كبير مثل ما كنت تعادل مما يعني أنك كنت تستخدم ثلاثة أضعاف مساحة كبيرة كما قد يكون لدينا خلاف ذلك. الآن في الوقت نفسه، ونحن لا يزال الحديث بايت، أليس كذلك؟ نحن لا نتحدث بالضرورة ميغابايت أو غيغابايت، ما لم تكن هذه البيانات الحصول على الهياكل الكبيرة. وحتى اليوم نبدأ في النظر كيف يمكننا استكشاف البيانات أكثر كفاءة إذا كان في حقيقة البيانات يحصل على اكبر. ولكن دعونا نحاول أن canonicalize عمليات أولا التي يمكنك القيام به في هذه أنواع من هياكل البيانات. ذلك شيء من هذا القبيل مرتبط يدعم القائمة عموما عمليات مثل حذف، إدراج والبحث. وماذا يعني ذلك؟ هذا يعني فقط أن عادة، إذا كان الناس يستخدمون قائمة مرتبطة، هم أو شخص آخر نفذت وظائف مثل حذف، إدراج، والبحث، حتى تتمكن من في الواقع تفعل شيئا مفيدة مع بنية البيانات. لذلك دعونا نلقي نظرة سريعة في كيف يمكننا تنفيذ بعض التعليمات البرمجية لقائمة مرتبطة على النحو التالي. لذلك هذا هو فقط بعض التعليمات البرمجية C، ولا حتى برنامج كامل انني حقا جلد بسرعة. انها ليست على الانترنت في التوزيع رمز، لأنه لن يعمل في الواقع. ولكن لاحظ أنني قمت فقط مع ذكر تعليق، نقطة نقطة نقطة، هناك شيء هناك، نقطة نقطة نقطة، شيء هناك. ودعونا ننظر فقط في ما هي أجزاء العصير. هكذا السطر الثالث، نذكر أن هذا هو الآن اقترحنا إعلان العقدة الأخيرة الوقت، واحدة من تلك الأشياء مستطيلة. أنه يحتوي على الباحث أن سنتصل N، لكننا يمكن أن نسميها أي شيء، ثم نجم عقدة بنية تسمى المقبل. ومجرد أن يكون واضحا، أن الثانية الخط، على خط الستة، ما هو؟ ما هو يفعل بالنسبة لنا؟ لأنه يبدو بالتأكيد أكثر خفي من المتغيرات المعتادة لدينا. الحضور: انه يجعل من نقل أكثر من واحد. رئيس 1: فإنه يجعل من نقل أكثر من واحد. وإلى أن تكون أكثر دقة، فإنه سيتم تخزين عنوان من العقدة التي من المفترض أن تكون لغويا بجانبه، أليس كذلك؟ لذلك لن بالضرورة نقل أي شيء. انها مجرد الذهاب الى تخزين قيمة، وهو سيكون عنوان بعض عقدة أخرى، وهذا هو السبب قلنا البنية نجمة عقدة، نجم تدل مؤشر أو عنوان. حسنا، الآن إذا كنت نفترض أن لدينا هذا N المتاحة لنا، ودعونا نفترض أن شخصا آخر قد إدراج مجموعة كاملة من الأعداد الصحيحة في قائمة مرتبطة. وهذه القائمة هي مرتبطة وأشار إلى بعض نقطة ودعا قائمة متغير هذا مرت هنا كمعلمة، كيف يمكنني التوجه نحو الخط 14 تنفيذ البحث؟ وبعبارة أخرى، إذا أنا تنفيذ وظيفة هدفها في الحياة هو اتخاذ عدد صحيح ثم ابتداء من قائمة مرتبطة، هذا هو مؤشر إلى القائمة المرتبطة. مثل أول، الذي أعتقد ديفيد وكان متطوع لدينا اليوم الاثنين، كان لافتا في كلها مرتبطة القائمة، انها كما لو أننا يمر ديفيد في كوسيطة لدينا هنا. كيف يمكننا التوجه نحو تعبر هذه القائمة؟ حسنا، اتضح أنه على الرغم من مؤشرات جديدة نسبيا لنا الآن، يمكننا أن نفعل ذلك نسبيا مباشر. انا ذاهب الى المضي قدما و تعريف متغير مؤقت قبل الاتفاقية هو مجرد الذهاب ليتم استدعاؤها المؤشر، أو PTR، ولكن هل يمكن أن نسميها أي شيء تريده. وانا ذاهب الى تهيئة إلى بداية القائمة. حتى تتمكن من نوع من التفكير في هذا كما لي المعلم في اليوم الآخر، نوع من الإشارة إلى شخص ما بين البشر لدينا كمتطوعين. لذلك أنا متغير مؤقت هذا فقط لافتا في نفس الشيء أن لدينا اسمه من قبيل الصدفة المتطوعين ديفيد كان لافتا أيضا إلى. الآن في حين أن المؤشر غير فارغة، لأن الاستدعاء أن اغية بعض القيمة الحارس خاصة وترسم نهاية القائمة، وذلك في حين أنا لا افتا في الأرض مثل دينا آخر التطوعي كان، دعونا نمضي قدما والقيام بما يلي. إذا pointer-- والآن أنا نوع من تريد أن تفعل ما فعلناه مع الطالب structure-- إذا مؤشر نقطة المقبل equals-- بدلا من ذلك، إذا يساوي مؤشر نقطة N يساوي متغير N، ل الحجة التي تم تمريرها في، ثم أريد أن أذهب إلى الأمام ويقول العودة الحقيقية. لقد وجدت عدد N من الداخل واحدة من عقد من قائمتي المرتبطة. ولكن النقطة لم يعد يعمل في هذا السياق، لأن المؤشر، PTR، هو في الواقع مؤشر، عنوان، ونحن في الواقع يمكن رائعة استخدام أخيرا قطعة من جملة هذا النوع من الانواع بمعنى بديهية والواقع استخدام السهم هنا، وهو ما يعني الانتقال من هذا العنوان إلى عدد صحيح هناك في. لذلك فمن مشابهة جدا في روح للمشغل نقطة، ولكن لمؤشر ليس مؤشر وليس البنية الفعلية نفسها، نحن فقط استخدام السهم. لذلك إذا كانت العقدة الحالية التي أنا، متغير مؤقت، أنا مشيرا في الوقت ذاته لا N، ماذا أريد أن أفعل؟ حسنا، مع بلدي متطوعين من البشر أن كان لدينا هنا في اليوم الآخر، لو كانت لغتي الأول البشرية ليست واحدة I تريد، وربما البشرية الثاني ليست واحد أريد، والثالثة، وأنا بحاجة للحفاظ على جسديا التحرك. مثل كيف يمكنني التنقل خلال قائمة؟ عندما كان لدينا مجموعة، أنت فعلت تماما كما كنت زائد زائد. ولكن في هذه الحالة، فإنه يكفي ل تفعل المؤشر، يحصل، مؤشر، المقبل. وبعبارة أخرى، فإن الحقل التالي مثل كل من أيدي اليسار أن متطوعين من البشر لدينا يوم الاثنين كانت تستخدم للإشارة إلى بعض عقدة أخرى. كانت تلك جيرانهم المقبل. لذلك إذا كنت تريد أن الخطوة من خلال هذه القائمة، أنا لا يمكن أن أقوم زائد زائد بعد الآن، I بدلا من القول I، مؤشر، يجري على قدم المساواة بغض النظر عن المجال التالي هو، الحقل التالي هو، والحقل التالي هو، بعد كل تلك الأيدي اليسار أن كان لدينا على خشبة المسرح لافتا لبعض القيم لاحقة. وإذا كنت من خلال الحصول على هذا التكرار كله، وأخيرا، أنا ضربت اغية عدم وجود وجدت N حتى الآن، والعودة فقط كاذبة. ذلك مرة أخرى، كل ما نقوم به هنا، كما في الصورة قبل لحظة، بدأ بالإشارة في ابتداء من قائمة المفترض. وبعد ذلك تحقق، هو القيمة أنا أبحث عن يساوي تسعة؟ إذا كان الأمر كذلك، أعود الحقيقية وانتهيت. إن لم يكن، I تحديث يدي، مؤشر AKA، أن نشير في مكان السهم المقبل، و ثم موقع السهم المقبل، والقادم. أنا مجرد المشي من خلال هذه المجموعة. ذلك مرة أخرى، من يهتم؟ مثل ما هو هذا عنصر عنه؟ حسنا، أذكر أن قدمنا مفهوم كومة، والتي هو نوع من البيانات مجردة بقدر ما هو لا شيء C، انها ليست شيئا CS50، انها فكرة مجردة، هذه الفكرة ل التراص الأمور على رأس واحد آخر والتي يمكن تنفيذها في باقات من الطرق المختلفة. وكانت طريقة واحدة اقترحنا مع صفيف، أو مع قائمة مرتبطة. واتضح أن قانوني، ل كومة يدعم اثنين على الأقل من العمليات. والعبارات الطنانة هي دفعة، ل دفع شيء إلى المكدس، مثل علبة جديدة في قاعة الطعام، أو البوب، وهو ما يعني لإزالة أسمى علبة من المكدس في تناول الطعام القاعة، وربما بعد ذلك بعض عمليات أخرى كذلك. فكيف يمكن أن نحدد هيكل اننا نطالب الآن كومة؟ حسنا، لدينا كل ما يلزم من جملة في حوزتنا في C. أقول، تعطيني تعريف نوع البنية داخل كومة، انا ذاهب الى القول عبارة عن صفيف، ل مجموعة كاملة من أرقام ومن ثم حجم. لذلك وبعبارة أخرى، إذا أريد لتنفيذ هذا في التعليمات البرمجية، اسمحوا لي ان اذهب ومجرد نوع من رسم ما هذا القول. لذلك هذا هو القول، أعطني الهيكل الذي حصل صفيف، وأنا لا أعرف ما هي القدرات، انها على ما يبدو بعض المستمر الذي لدي معرفة في مكان آخر، وهذا شيء طيب. ولكن لنفترض انها مجرد واحدة، اثنان، ثلاثة، أربعة، خمسة. حتى القدرة هي 5. هذا العنصر داخل بلدي وسوف يطلق هيكل الأرقام. وبعد ذلك تحتاج إلى واحد متغير آخر على ما يبدو دعا الحجم الذي في البداية انا ذاهب يتم تهيئة إلى الصفر اشتراط. إذا كان هناك شيء في مكدس، وحجم هو الصفر، وانها القيم القمامة في الأرقام. ليس لدي أي فكرة ما في هناك فقط حتى الآن. لذلك إذا كنت تريد أن تدفع شيء إلى المكدس، افترض استدعاء الدالة دفع، و أقول دفع 50، مثل العدد 50، حيث أن تقترحون أنا استدراجه في هذه المجموعة؟ هناك خمس إجابات محتملة مختلفة. أين تريد دفع عدد 50؟ إذا كان الهدف هنا، مرة أخرى، استدعاء وظيفة دفعة، تمر في حجة 50، أين وضعه؟ خمسة possible-- فرصة 20٪ من التخمين بشكل صحيح. نعم؟ الحضور: اليمين المتطرف. رئيس 1: اليمين المتطرف. هناك الآن فرصة 25٪ من التخمين بشكل صحيح. بحيث يكون في الواقع على ما يرام. من الاتفاقية، أنا أقول مع صفيف، نحن سوف تبدأ عادة في الجهة اليسرى، لكننا يمكن بالتأكيد تبدأ في الحق. لذلك المفسد هنا سيكون أنا الارجح الى استدراجه على اليسار، مثلما هو الحال في مجموعة طبيعية حيث أبدأ ستذهب اليسار إلى اليمين. ولكن إذا كنت تستطيع الوجه والحساب، ودفع غرامة. انها ليست مجرد التقليدية. OK، ولست بحاجة لجعل واحدة مزيد من التغيير بالرغم من ذلك. والآن، لقد دفعت شيئا إلى المكدس، ما هي الخطوة التالية؟ كل الحق، لا بد لي من زيادة حجم. لذلك اسمحوا لي المضي قدما وفقط تحديث هذه، التي كانت صفرا. وبدلا من ذلك الآن، وانا ذاهب وضعه في قيمة واحدة. ونفترض الآن أنا أدفع آخر عدد إلى المكدس، مثل 51. حسنا، لقد جعل أكثر واحد التغيير، وهو ما يصل الى حجم اثنين. ثم لنفترض أنا أدفع أكثر واحد عدد إلى المكدس مثل 61، الان انا بحاجة لتحديث حجم واحد أكثر الوقت، والحصول على قيمة 3 كحجم. ونفترض الآن أدعو البوب. الآن البوب، من خلال اتفاقية، لا يأخذ حجة. مع كومة، وكلها نقطة من استعارة صينية غير أن لم يكن لديك تقدير للذهاب الحصول على هذا الدرج، ويمكن كل ما عليك فعله والبوب ​​العلوي واحدة من المكدس، لمجرد. هذا ما يفعله هذا الهيكل البيانات. ذلك أن المنطق إذا أنا يقول البوب، ما يأتي من؟ حتى 61. فما هي حقا الكمبيوتر تنوي القيام به في الذاكرة؟ ماذا يكون قانون بلدي أن تفعل؟ ماذا كنت اقتراح نحن تغيير على الشاشة؟ ما الذي يجب تغييره؟ آسف؟ حتى نتخلص من 61. لذلك يمكنني القيام به بالتأكيد ذلك. ويمكنني التخلص من 61. ثم ما غيرها التغيير يجب أن يحدث؟ حجم ربما أن نعود إلى اثنين. وحتى هذا شيء طيب. ولكن انتظر لحظة، وحجم منذ كان لحظة الثلاثة. دعونا لا مجرد الاختيار العقل سريع. كيف نعرف أننا أراد أن يتخلص من 61؟ لأننا ظهرت. وذلك لدي هذا الحجم الممتلكات الثاني. انتظر لحظة، وأنا التفكير في العودة إلى أسبوعين عندما بدأنا نتحدث عن المصفوفات، حيث كان هذا المكان الصفر، وكان هذا مكان واحد، وكان هذا الموقع اثنين، وهذا هو المكان ثلاثة، أربعة، يبدو أن العلاقة بين حجم والعنصر الذي أريد أن يزيل من مجموعة ويبدو أن مجرد ما؟ حجم ناقص واحد. وهكذا هذه هي الطريقة كبشر نحن نعرف 61 يأتي أولا. كيف انها الكمبيوتر سوف تعلم؟ عندما التعليمات البرمجية الخاصة بك، حيث يمكنك على الأرجح تريد أن تفعل حجم ناقص واحد، حتى ثلاثة ناقص واحد هي سنتان، وأنه يعني أننا نريد أن نتخلص من 61. وبعد ذلك يمكننا تحديث الواقع حجم بحيث حجم الآن يذهب من ثلاثة إلى اثنين فقط. ومجرد أن يكون متحذلق، وانا ذاهب أن أقترح أن انتهيت، أليس كذلك؟ كنت المقترح حدسي صحيح أن أتخلص من 61. ولكن لم النوع الأول من نوع من تخلصنا من 61؟ لقد نسيت فعال أنه في الواقع هناك. وبذاكرتي إلى PSET4، إذا كنت قد قرأت المقالة حول الطب الشرعي، وPDF أن كان لدينا يا رفاق قراءة، أو لك سوف تقرأ هذا الاسبوع لPSET4. نذكر أن هذا هو في الواقع ثيق ل الفكرة كلها من علوم الحاسوب. ما هو الكمبيوتر لا عموما هو فإنه ينسى فقط حيث هناك شيئا، ولكنه لا يذهب في ومثل محاولة خدش بها أو التجاوز هذه البتات مع الأصفار ومنها أو بعض نمط عشوائية أخرى إلا إذا كنت نفسك تفعل ذلك عمدا. لذلك كان حدسك الحق، دعونا نتخلص من 61. ولكن في الواقع، نحن لا داعي للقلق. نحتاج فقط أن ننسى أن انه هناك عن طريق تغيير حجم لدينا. الآن هناك مشكلة مع هذا المكدس. إذا كنت الاستمرار في دفع الأمور إلى المكدس، ما هو من الواضح سيحدث في غضون لحظات قليلة الوقت؟ ونحن في طريقنا إلى نفاد الفضاء. وماذا نفعل؟ نحن نوع من مشدود. لا يسمح هذا التطبيق لنا تغيير حجم المصفوفة، لأن استخدام بناء الجملة هذا، إذا كنت بذاكرتي إلى أسبوعين، بمجرد أن أعلن حجم صفيف، لم نر بعد آلية من حيث يمكنك تغيير حجم المصفوفة. والواقع C لا يكون هذا ميزة. إذا كنت أقول أعطني خمس Nths، ودعوة لهم أرقام، هذا كل ما في طريقنا للحصول عليه. لذلك نحن القيام به الآن اعتبارا من يوم الاثنين، لديها القدرة على التعبير عن حل رغم ذلك، نحن بحاجة فقط إلى قرص تعريف كومة دينا أن لا يكون بعض مجموعة الثابت تلوينها، ولكن فقط لتخزين عنوان. الآن لماذا هذا؟ الآن علينا فقط أن تكون مريحة مع حقيقة أن عند تشغيل برنامجي، انا ذاهب يفترض أن عليك أن تسأل الإنسان، كم عدد الأرقام لا تريد تخزين؟ وبالتالي فإن مساهمة يجب أن يأتي من مكان ما. ولكن مرة واحدة وأنا أعلم أن عدد، ثم يمكنني فقط استخدام ما تعمل لإعطاء لي قطعة من الذاكرة؟ يمكنني استخدام malloc. وأستطيع أن أقول أي عدد من بايت أريد العودة لهذه Nths. وكل ما لدي لتخزين في أرقام متغير هنا داخل هذه البنية يجب أن يكون ماذا؟ ما يجري فعلا في الأرقام في هذا السيناريو؟ نعم، مؤشر إلى أول بايت من أن جزءا من الذاكرة، أو بشكل أكثر تحديدا، عنوان من أول من تلك بايت. لا يهم ما اذا كان واحد بايت أو مليار بايت، أنا فقط بحاجة أن نهتم أولا. لأن ما الضمانات malloc و بلدي ضمانات نظام التشغيل، غير أن جزءا من الذاكرة I الحصول عليها، انها سوف تكون متجاورة. ليس هناك لن يكون الثغرات. حتى لو كنت قد طلبت 50 بايت أو 1000 بايت، انهم جميعا سوف يكون العودة إلى الوراء إلى الوراء. وطالما أتذكر كيف كبير، كيف كثيرا سألت عنه، كل ما تحتاج إلى معرفته هو الأول من نوعه العنوان. حتى الآن لدينا القدرة في التعليمات البرمجية. وإن كان، انها سوف تأخذنا المزيد من الوقت لكتابة هذا الأمر، نحن يمكن الآن تخصيص تلك الذاكرة التي فقط تخزين عنوان مختلف هناك إذا كنا نريد أكبر أو حتى قطعة صغيرة من الذاكرة. حتى هنا إلى المفاضلة. الآن نحصل على الدينامية. لا يزال لدينا التلامس أنا مدعيا. لأن malloc سيعطينا قطعة متجاورة من الذاكرة. ولكن هذا سيكون الألم في الرقبة بالنسبة لنا، مبرمج، إلى رمز فعليا. انها مجرد مزيد من العمل. نحن بحاجة إلى رمز أقرب إلى ما كنت ضجيجا من قبل مجرد لحظة. قابلة للتنفيذ للغاية، ولكنه يضيف التعقيد. وحتى الوقت المطور، مبرمج الوقت هو بعد مورد آخر أننا قد نحتاج إلى قضاء بعض الوقت للحصول على الميزات الجديدة. وبعد ذلك بالطبع هناك طابور. ونحن لن نذهب إلى هذا واحد في الكثير من التفاصيل. إلا أنها مشابهة جدا في الروح. أنا يمكن أن تنفذ طابور، و العمليات المقابلة لها، إدراج بقائمة الانتظار أو dequeue، مثل إضافة أو إزالة، انها مجرد وسيلة مربي الحيوانات لقول ذلك، إدراج بقائمة الانتظار أو dequeue، على النحو التالي. يمكنني فقط أعطي نفسي البنية له ذلك مرة أخرى مجموعة عدد و له ذلك مرة أخرى حجم، ولكن لماذا أنا بحاجة الآن لمتابعة الجزء الأمامي من طابور؟ لم أكن في حاجة إلى معرفة وأمام كومة بلدي. حسنا، إذا كنت مرة أخرى ل queue-- دعونا فقط بجد رمز ذلك وجود مثل خمسة الأعداد الصحيحة هنا يحتمل. لذلك هذا هو صفر، واحد، اثنان، ثلاثة، أربعة. هذا سيكون دعا الأرقام مرة أخرى. وهذا سوف يطلق الحجم. لماذا هو غير كافية أن يكون حجم عادل؟ حسنا، دعونا دفع تلك الأرقام نفسها جرا. لذلك أنا pushed-- I enqueued، أو دفع. الآن أنا إدراج بقائمة الانتظار 50، ثم 51، ثم 61، ونقطة نقطة نقطة. ذلك أن إدراج بقائمة الانتظار. I enqueued 50، ثم 51، ثم 61. والتي تبدو متطابقة إلى كومة حتى الآن، إلا أنني لا تحتاج إلى إجراء تغيير واحد. أنا بحاجة إلى تحديث هذا الحجم، لذلك أذهب من صفر إلى واحد إلى 2:58 الآن. كيف يمكنني dequeue؟ ما يحدث مع dequeue؟ الذي يجب أن يأتي من هذه القائمة لأول مرة اذا كان الخط في متجر أبل؟ حتى 50. لذلك نوع من اصعب هذه المرة. في حين أن آخر مرة كان السوبر من السهل القيام به فقط حجم ناقص واحد، أحصل على نهاية مجموعة بلدي فعال حيث الأرقام، فإنه يزيل 61. لكنني لا أريد أن إزالة 61. وأود أن أغتنم 50، الذي كان هناك في 05:00 ليصطف ل اي فون الجديد أو غيرها. وذلك للتخلص من 50، I لا يمكن أن تفعل هذا، أليس كذلك؟ يمكنني شطب 50. ولكن نحن فقط قلنا لم يكن لديك لتكون بذلك الشرج كما تخدش الخروج أو إخفاء البيانات. يمكننا أن ننسى فقط حيث هو. ولكن إذا قمت بتغيير حجم بلدي الآن ل اثنين، وهذا هو ما يكفي من المعلومات لمعرفة ما يجري في طابور بلدي؟ ليس حقا. مثل حجم بلدي اثنين، ولكن أين يبدأ قائمة الانتظار، خاصة إذا كان لا يزال لدي هذه الأرقام نفسها في الذاكرة. 50، 51، 61. لذلك أنا بحاجة إلى أن نتذكر الآن حيث الجبهة. وذلك اقترحت يصل هناك، سنكون قد دعا فقط الجبهة النونية، التي الأولي كان ينبغي أن يكون قيمة ما؟ صفر، مجرد بداية القائمة. ولكن الآن، بالإضافة إلى decrementing حجم، ونحن فقط الاضافة الجبهة. الآن وهنا مشكلة أخرى. ذلك مرة واحدة وأظل الذهاب. ان هذا هو عدد مثل 121، 124، ومن ثم، اللعنة، أنا من الفضاء. ولكن انتظر لحظة، وأنا لست كذلك. حتى في هذه النقطة في القصة، لنفترض أن حجم واحد، اثنان، ثلاثة، أربعة، لذلك نفترض أن حجم الأربعة، وجبهة واحدة، حتى 51 هو في الجبهة. أريد أن أضع رقم آخر هنا، ولكن، اللعنة، أنا من الفضاء. ولكن أنا لا حقا، أليس كذلك؟ أين يمكن أن أضع بعض قيمة إضافية، مثل 171؟ نعم، أنا يمكن أن مجرد نوع من أعود إلى هناك، أليس كذلك؟ ثم شطب 50 أو مجرد الكتابة عليه مع 171. وإذا كنت أتساءل لماذا حصلت أعدادنا عشوائية لذلك، تؤخذ هذه عادة الكمبيوتر دورات العلوم في جامعة هارفارد بعد CS50. ولكن هذا كان الأمثل جيد، لأنه الآن أنا لا إضاعة الفضاء. لا يزال لدي لنتذكر كيف كبيرة هذا الشيء هو مجموع. انها خمس المجموع. لأنني لا أريد بدء الكتابة 51. وحتى الآن ما زلت من الفضاء، لذلك نفس المشكلة كما كان من قبل. ولكن يمكنك أن ترى كيف الآن في التعليمات البرمجية الخاصة بك، وربما كنت لديك لكتابة أكثر من ذلك بقليل تعقد لجعل ذلك يحدث. في واقع الأمر، ما المشغل في C ربما يتيح القيام بذلك على دائرية سحرية؟ نعم المشغل مودولو، النسبة المئوية. فما هو نوع من باردة حول طابور، على الرغم من أننا حفاظ على المصفوفات الرسم كخطوط مثل هذه مستقيمة، إذا كنت نوع من التفكير في هذا الأمر التقويس حول كدائرة، ثم عادل حدسي أنه نوع من يعمل عقليا أعتقد قليلا أكثر نظافة. سيكون لديك لا يزال لتنفيذ هذا النموذج العقلي في التعليمات البرمجية. لذلك ليس من الصعب، في نهاية المطاف، لتنفيذ، ولكن ما زلنا نفقد size-- بدلا من ذلك، القدرة على تغيير حجم، وما لم نفعل ذلك. علينا أن نتخلص من مجموعة، ونحن استبدله مؤشر واحد، ثم في مكان ما في قانون بلدي أنا عندي مكالمة ما تعمل لخلق الواقع مجموعة تسمى الأرقام؟ Malloc، أو بعض مماثلة وظيفة، بالضبط. أي أسئلة على أكوام أو قوائم الانتظار. نعم؟ سؤال جيد. ما مودولو يمكنك استخدام هنا. لذلك عادة، عند استخدام زارة الدفاع، هل تفعل ذلك مع حجم هيكل بيانات كاملة. ذلك شيء من هذا القبيل خمسة أو القدرة، إذا انها ثابتة، وربما المعنية. ولكن مجرد القيام مودولو خمسة ربما ليست كافية، لأننا بحاجة لمعرفة هل نحن التفاف حول هنا أو هنا أو هنا. لذلك ربما كنت أيضا تريد الذهاب الى إشراك حجم الشيء، أو المتغير الجبهة كذلك. حتى انها مجرد هذا نسبيا التعبير الحسابي البسيط، ولكن مودولو سيكون العنصر الرئيسي. فيلم قصير حتى اذا صح التعبير. الرسوم المتحركة أن بعض الناس في جامعة أخرى وضعت معا أن لدينا تكييفها لهذه المناقشة. أنها تنطوي على جاك تعلم حقائق عن الطوابير والإحصائيات. FILM: ذات مرة، كان هناك رجل يدعى جاك. عندما جاء إلى تكوين صداقات، لم جاك يكن لديك موهبة. حتى ذهب جاك لاجراء محادثات مع معظم الرجل شعبية يعرفه. ذهب إلى لو وتساءل: ماذا أفعل؟ رأى لو أن صديقه كان بالأسى حقا. حسنا، بدأ، فقط انظر كيف كنت يرتدي. لا يكون لديك أي ملابس مع نظرة مختلفة؟ نعم، قال جاك. أنا متأكد من ذلك. تعال إلى بيتي و سوف تظهر لهم لكم. حتى أنها انفجرت لجاك. وأظهرت جاك لو مربع حيث احتفظ كل ما قدمه من القمصان، وسرواله، وجواربه. وقال لو، أرى لديك كل ما تبذلونه من الملابس في كومة. لماذا لا يتم ارتداء بعض البعض الآخر مرة واحدة في لحظة؟ وقال جاك، حسنا، عندما كنت إزالة الملابس والجوارب، I غسلها ووضعها بها بعيدا في المربع. ثم يأتي في اليوم التالي صباح اليوم، وحتى أنا هوب. أذهب إلى منطقة الجزاء، والحصول على ملابسي من أعلى. لو أدركت بسرعة المشكلة مع جاك. احتفظ ملابس CD، وكتب في المكدس. عندما وصل ل شيء للقراءة أو للارتداء، عنيدا واختيار الكتاب العلوي أو الملابس الداخلية. ثم عندما تم فعله، وقال انه وضعه الظهير الايمن. مرة أخرى أنه سيذهب، وعلى رأس من المكدس. أنا أعرف الحل، قال منتصر بصوت عال. كنت بحاجة لمعرفة ل بدء استخدام طابور. تولى لو ملابس جاك و علقها في خزانة. وعندما كان يفرغ مربع، وقال انه قذف فقط. ثم قال، والآن جاك، في نهاية اليوم، وضع الملابس الخاصة بك على اليسار عندما كنت وضعت بها بعيدا. ثم صباح الغد عند رؤية الشمس، والحصول على ملابسك على اليمين، من نهاية السطر. لا ترى؟ وقال لو. وسيكون لطيفا. عليك ارتداء كل شيء مرة واحدة قبل ارتداء شيء مرتين. ومع كل شيء في طوابير في خزانته والجرف، التي جاك أن يشعر تأكد تماما من نفسه. كل الشكر للو و طابور رائع له. رئيس 1: كل الحق، انها رائعتين. ذلك ما يجري حقا تحت غطاء محرك السيارة الآن؟ أن لدينا مؤشرات، أن لدينا malloc، أن لدينا القدرة على خلق قطع من الذاكرة لأنفسنا بشكل حيوي. لذلك هذا هو أننا الصورة لمحت فقط في اليوم الآخر. نحن لم يسكن حقا على ذلك، ولكن هذه الصورة وقد استمر الحال على تحت غطاء محرك السيارة لعدة أسابيع الآن. وهكذا فإن هذا يمثل فقط مستطيل أننا قد تعادل ذاكرة الكمبيوتر الخاص بك. وربما جهاز الكمبيوتر الخاص بك، أو CS50 ID، لديها غيغا بايت من ذاكرة RAM أو أو اثنين غيغا بايت أو أربعة. لا يهم حقا. نظام التشغيل الخاص بك ويندوز أو ماك أو لينكس، يسمح أساسا برنامجك لأعتقد أنه لديه حق الوصول على كامل ذاكرة الكمبيوتر الخاص بك، حتى وإن كنت قد تكون قيد التشغيل برامج متعددة في وقت واحد. حتى في الواقع، لم يفلح ذلك حقا. ولكن هذا النوع من الوهم بالنظر إلى كافة البرامج. حتى إذا كان لديك اثنين من العربات من ذاكرة الوصول العشوائي، وهذا هي الطريقة التي قد يظن الكمبيوتر منه. الآن من قبيل الصدفة، واحد من هؤلاء الأشياء، واحد من هذه القطاعات من الذاكرة، يسمى المكدس. والواقع أي وقت حتى الآن في كتابة التعليمات البرمجية ان كنت قد يسمى وظيفة، على سبيل المثال الرئيسي. أذكر أنه في أي وقت لدي ذاكرة الكمبيوتر استخلاصها، و أنا دائما رسم نوع من نصف مستطيل هنا ولا يكلف نفسه عناء الحديث حول ما هو أعلاه. لأنه عندما يتم استدعاء الرئيسية، أنا أطالب أن تحصل على هذه القطعة من الذاكرة أن يذهب إلى هنا. وإذا الرئيسي يسمى وظيفة مثل مبادلة، وأيضا تبادل يذهب هنا. واتضح، وهذا حيث انها تنتهي في. على ما يسمى كومة داخل ذاكرة الكمبيوتر الخاص بك. الآن في نهاية اليوم، هذا هو يتناول فقط. انها مثل صفر بايت، بايت واحد، بايت 2 مليار دولار. ولكن إذا كنت تفكر في ذلك لأن هذا الكائن مستطيل، كل ما تفعلونه كل الوقت نسميه هي وظيفة طبقات شريحة جديدة من الذاكرة. اننا نقدم تلك الوظيفة شريحة من الذاكرة الخاصة به للعمل مع. وأذكر الآن أن هذا هو المهم. لأنه إذا كان لدينا شيء من هذا القبيل مبادلة واثنين من المتغيرات المحلية مثل A و B و نحن تغيير تلك القيم من واحد واثنين إلى اثنين واحد، أذكر أنه عندما يعود المبادلة فهو كما لو أن هذه الشريحة من الذاكرة انتهت للتو. في الواقع، انها لا تزال هناك عدليا. وشيء لا يزال في الواقع هناك. ولكن من الناحية النظرية، فهو كما على الرغم من انها اختفت تماما. وهكذا الرئيسية لا يعرف أي من العمل الذي تم القيام به في تلك الوظيفة المبادلة إلا أنها مرت فعلا في تلك الحجج التي كتبها المؤشر أو بالإشارة. الآن، والحل الجذري لهذه المشكلة مع مبادلة يمر الأشياء من قبل في العنوان. ولكن تبين، أيضا، ما هو تم يدور فوق ذلك الجزء من المستطيل كل هذا الوقت بعد هناك المزيد من الذاكرة هناك. وعند حيوي تخصيص الذاكرة، سواء كان ذلك داخل GetString، التي كنا نقوم به بالنسبة لك في CS50 مكتبة، أو إذا كنت الرجال استدعاء malloc واطلب نظام التشغيل لقطعة من الذاكرة، فإنه لا يأتي من المكدس. انها تأتي من مكان آخر في ذاكرة الكمبيوتر الخاص بك وهذا يسمى الكومة. وهذا ليس مختلفا. انها نفس RAM. انها نفس الذاكرة. انها مجرد ذاكرة الوصول العشوائي التي متروك هناك بدلا من هنا. وهكذا ماذا يعني ذلك؟ حسنا، إذا كان جهاز الكمبيوتر الخاص بك كمية محدودة من الذاكرة وكومة ينمو، حتى في الكلام، وكومة، وفقا لهذا السهم، يتزايد باستمرار. وبعبارة أخرى، كل الوقت استدعاء malloc، كنت يولى شريحة من الذاكرة من فوق، ثم ربما أقل قليلا، ثم قليلا أقل من ذلك، في كل مرة يمكنك استدعاء malloc، الكومة، انها الاستخدام، هو نوع من النمو، تزايد أوثق وأقرب إلى ماذا؟ المكدس. فهل هذا يبدو وكأنه فكرة جيدة؟ أعني، حيث انها ليست واضحة حقا ماذا يمكنك أن تفعل إذا كنت فقط لديك كمية محدودة من الذاكرة. ولكن هذا أمر سيء بالتأكيد. تلك سهمين هي على دورة مكثفة لبعضنا البعض. واتضح أن الرجل سيئة، والناس الذين هي جيدة ولا سيما مع البرمجة، ومحاولة اختراق أجهزة الكمبيوتر، يمكن استغلال هذا الواقع. في الواقع، دعونا النظر يذكر قصاصة. لذلك هذا هو مثال يمكنك أن تقرأ حول بمزيد من التفصيل في ويكيبيديا. سنقوم نقطة لك في المادة اذا غريبة. ولكن هناك هجوم عموما المعروف أن تجاوز سعة المخزن المؤقت وقد وجدت لطالما البشر وقد لديها القدرة على التلاعب ذاكرة الكمبيوتر، وخاصة في C. لذلك هذا هو برنامج التعسفي جدا، ولكن دعونا قراءته من أسفل إلى أعلى. الرئيسية إلى نجمة ARGC شار ARGV. لذلك هو البرنامج الذي يأخذ وسائط سطر الأوامر. وكل الرئيسي لا يبدو هو الدعوة وظيفة، يطلق عليه F لالبساطة. ويمر في ماذا؟ ARGV واحد. لذلك يمر في F أيا كان الكلمة هي أن المستخدم كتابة في موجه بعد اسم البرنامج على الإطلاق. الكثير من مثل قيصر أو Vigenere، التي تذكرون به مع ARGV. فما هو F؟ F يأخذ في سلسلة كما حجتها الوحيدة، AKA نجم شار، نفسه الشيء، كسلسلة. ويطلق عليها تعسفا شريط في هذا المثال. ثم شار ج 12، فقط في شروط للشخص العادي، ما هو شار ج قوس 12 تفعل بالنسبة لنا؟ ما تفعل؟ تخصيص الذاكرة، وتحديدا 12 بايت لمدة 12 حرف. بالضبط. ثم السطر الأخير، وإثارة و نسخة، وربما كنت قد لم أر. هذا هو نسخة سلسلة وظيفة هدفها في الحياة هو نسخة الحجة الثانية في أول حجتها، ولكن فقط ما يصل الى عدد معين من وحدات البايت. هكذا تقول الحجة الثالثة، عدد وحدات البايت يجب نسخ؟ طول شريط، أيا كان المستخدم كتبته. ومحتويات بار، هذه السلسلة، ل نسخ إلى ذاكرة أشار في في C. لذلك يبدو هذا النوع من الغباء، وغير ذلك. انها مثال مفتعلة، ولكن هذا التمثيل من فئة ناقلات الهجوم، وسيلة لمهاجمة البرنامج. كل شيء على ما يرام وجيد إذا كان المستخدم أنواع في كلمة واحدة وهذا هو 11 حرفا أو أقل، بالإضافة إلى مائل الصفر. ماذا لو قام المستخدم بكتابة في أكثر من 11 أو 12 أو 20 أو 50 حرفا؟ ما هو هذا البرنامج تنوي القيام به؟ خطأ SEG يحتمل. انها تسير لنسخ عمياء كل شيء في شريط يصل لطوله، وهو كل شيء حرفيا في شريط، في عنوان أشار في C. ولكن C تمت فقط استباقي نظرا إلى 12 بايت. ولكن ليس هناك فحص إضافي. ليس هناك إذا كانت الظروف. ليس هناك خطأ التحقق من هنا. وحتى ما هو هذا البرنامج تنوي القيام به هو مجرد عمياء نسخ شيء واحد إلى آخر. وحتى إذا وضعنا هذا كصورة، وهنا مجرد شظية من مساحة الذاكرة. لذلك نلاحظ في الجزء السفلي، ونحن لدينا شريط متغير المحلي. بحيث المؤشر الذي يحدث لstore-- بدلا من أن حجة المحلية هذا الذهاب لتخزين شريط السلسلة. ومن ثم لاحظ فقط فوقه في كومة، لأن في كل مرة كنت أسأل للذاكرة على كومة، وغني قليلا فوقه بالصور، لاحظ أن لدينا 12 بايت هناك. رأس واحد الأيسر هو C قوس صفر و واحد حق القول هي C قوس 11. هذه هي الطريقة فقط على أجهزة الكمبيوتر الذهاب الى وضع بها. حتى مجرد حدسي، إذا البار أكثر من 12 حرفا في المجموع، بما في ذلك مائل الصفر، حيث هو 12 أو قوس C 12 سيذهب؟ أو بالأحرى أين ال12 شخصية أو الحرف ال13، الطابع مئة الذهاب في نهاية المطاف في الصورة؟ أعلى أو أقل؟ الحق، لأنه حتى وإن المدخنة نفسها ينمو إلى أعلى، مرة واحدة كنت قد وضعت الاشياء في عليه، لأسباب التصميم، يضع الذاكرة من أعلى إلى أسفل. حتى إذا كنت قد حصلت على أكثر من 12 بايت، وأنت تسير لبدء الكتابة بار. الآن هذا هو الخلل، ولكنها ل ليس حقا صفقة كبيرة. وإنما هو صفقة كبيرة، لأنه لا يوجد المزيد من الأشياء يحدث في الذاكرة. حتى هنا كيف يمكننا وضع مرحبا، لتكون واضحة. لو كنت كتبته في مرحبا في موجه. مائل الصفر H-E-L-L-O، ينتهي داخل تلك بايت 12، ونحن آمنين فائقة. كل شيء على ما يرام. ولكن إذا كنت اكتب شيئا أطول، يحتمل انها الذهاب إلى زحف إلى الفضاء بار. ولكن الأسوأ من ذلك، فإنه يتحول من كل هذا الوقت، على الرغم من أننا قد لا يتحدثون عن ذلك، يتم استخدام المكدس لغيرها من الاشياء. انها ليست المتغيرات المحلية فقط. C هي لغة مستوى منخفض جدا. وذلك النوع من سرا يستخدم كومة أيضا لنتذكر عندما يتم استدعاء الدالة، ما والعنوان هو من وظيفة سابقة، لذلك يمكن أن تقفز إلى تلك الوظيفة. لذلك عندما مبادلة المكالمات الرئيسية، بين الأشياء دفعت إلى المكدس ليست مجرد مقايضة المتغيرات المحلية، أو حججه، كما دفعت سرا إلى المكدس ممثلة بالشريحة الحمراء هنا، هو عنوان رئيسي جسديا في ذاكرة الكمبيوتر الخاص بك، بحيث عندما يتم المبادلة الكمبيوتر يعلم أنني بحاجة إلى العودة إلى الرئيسية والانتهاء من تنفيذ المهمة الرئيسية. لذلك هذا أمر خطير الآن، لأنه إذا أنواع المستخدم في أكثر من جيد مرحبا، بحيث إدخال المستخدم clobbers أو الكتابة فوق هذا الباب الأحمر، منطقيا إذا كان الكمبيوتر مجرد الذهاب الى تحمل عمياء أن وحدات البايت في ذلك شريحة الحمراء العنوان الذي يجب أن تعود، ماذا لو كان الخصم هو ذكي بما فيه الكفاية أو محظوظا بما فيه الكفاية لوضع تسلسل بايت هناك يشبه عنوان، ولكن هذا العنوان من التعليمات البرمجية انه او انها تريد من الكمبيوتر لتنفيذ بدلا من الرئيسي؟ وبعبارة أخرى، إذا ما المستخدم هو كتابة في موجه، ليست مجرد شيء مثل حميدة مرحبا، ولكنها في الواقع رمز هذا يعادل لحذف جميع ملفات هذا المستخدم؟ أو البريد الإلكتروني كلمة المرور الخاصة بهم لي؟ أو بدء تسجيل بهم ضربات المفاتيح، أليس كذلك؟ هل هناك طريقة، دعونا تنص اليوم، أنها يمكن أن اكتب في ليس فقط مرحبا العالم أو باسمهم، وسعهم أساسا تمر في التعليمات البرمجية، الأصفار و منها، أن الكمبيوتر الأخطاء لكل من رمز وعنوان. حتى وإن كان إلى حد ما تجريدي، إذا كان أنواع المستخدم في يكفي كود الخصومة أننا سوف التعميم هنا A. A هو هجوم أو الخصوم. الاشياء حتى مجرد سوء. نحن لا نهتم أرقام أو الأصفار أو تلك اليوم، بحيث ينتهي بك الأمر الكتابة هذا الباب الأحمر، تلاحظ أن تسلسل بايت. O 835 C صفر ثمانية صفر. والآن بما أن المادة ويكيبيديا هنا وقد اقترح، إذا كنت تبدأ الآن في الواقع وصفها بايت في الكمبيوتر الخاص بك الذاكرة، ما هي المادة ويكيبيديا يقترحه هو أنه ما إذا كان العنوان تلك بايت الأيسر العلوي 80 C 0 3508. وبعبارة أخرى، إذا كان الرجل السيئ هو ذكي بما فيه الكفاية مع له أو لها كود فعلا وضع عدد هنا أن يتوافق مع عنوان رمز هو أو هي حقن في الكمبيوتر، يمكن خداع الكمبيوتر إلى القيام بأي شيء. إزالة الملفات، والبريد الإلكتروني الأشياء، استنشاق حركة المرور الخاصة بك، حرفيا أي شيء يمكن أن يكون حقنها في الكمبيوتر. وذلك لتجاوز سعة المخزن المؤقت هجوم في صميمها هو مجرد غبي، غبي الغلابة من صفيف لم يكن لديك حدودها التحقق. وهذا ما هو السوبر خطيرة في وقت واحد سوبر قوية في C هو أن لدينا بالفعل الوصول إلى أي مكان في الذاكرة. والامر متروك لنا، والمبرمجين، الذين يكتبون رمز الأصلي للتحقق من طول الرتق أي صفائف أننا التلاعب. لكي نكون واضحين، ما هو الإصلاح؟ إذا كان لنا أن تتراجع إلى هذا رمز، لا ينبغي لي فقط تغيير طول شريط، ما آخر يجب أن يتم فحص؟ ما الذي يجب أن تقوم به ل منع هذا الهجوم تماما؟ أنا لا أريد أن أقول عمياء التي يجب نسخ العديد من وحدات البايت كما هو طول شريط. أريد أن أقول، كما نسخ العديد من وحدات البايت كما هي في شريط حتى تخصيص الذاكرة، أو 12 الحد الأقصى. لذلك أنا بحاجة إلى نوع من اذا كان الشرط التي لا تحقق طول شريط، ولكن إذا كان يتجاوز 12، ونحن رمز القرص الثابت فقط 12 كما أقصى مسافة ممكنة. وإلا فإن ما يسمى عازلة هجوم تجاوز يمكن أن يحدث. في الجزء السفلي من هذه الشرائح، إذا كنت غريبة لقراءة المزيد هي المادة الأصلية الفعلية إذا كنت ترغب في إلقاء نظرة. ولكن الآن، وبين الأسعار دفعت هنا كان عدم الكفاءة. حتى أن كان سريعة نظرة مستوى منخفض في ما مشاكل يمكن أن تنشأ الآن أننا الحصول على ذاكرة الكمبيوتر. ولكن مشكلة أخرى نحن تعثرت بالفعل يوم الاثنين كان مجرد عدم الكفاءة من قائمة مرتبطة. لقد عدنا الى الزمن الخطي. لم يعد لدينا مجموعة متجاورة. ليس لدينا الوصول العشوائي. لا يمكننا استخدام التدوين قوس مربع. لدينا حرفيا لاستخدام حلقة while مثل واحد كتبته قبل لحظة. ولكن يوم الاثنين، ونحن ادعى ما في وسعنا زحف مرة أخرى إلى عالم الكفاءة تحقيق شيء هذا وغاريتمي ربما، أو الأفضل حتى الآن، ربما شيء أن يكون ما يسمى وقت ثابت. فكيف يمكننا أن نفعل ذلك باستخدام هذا جديدة الأدوات، وهذه العناوين، هذه المؤشرات، وخيوط الأشياء الخاصة بنا؟ حسنا، لنفترض أن هنا، وهذه هي حفنة من الأرقام التي نريد لتخزين في هيكل البيانات والبحث بكفاءة. يمكننا الترجيع تماما لأسبوع اثنين، ورمي هذه في صفيف، وتفتيشها استخدام البحث الثنائية. فرق تسد. في واقع الأمر كتبته البحث الثنائي في PSET3، حيث يمكنك تنفيذ البرنامج البحث. لكن هل تعرف ما. هناك نوع من أكثر طريقة ذكية للقيام بذلك. انها اكثر قليلا متطورة وربما يسمح لنا أن نرى لماذا ثنائي البحث هو أسرع بكثير. أولا، دعونا نقدم مفهوم شجرة. التي وإن كانت في أشجار الواقع نوع من تنمو مثل هذا، في عالم الكمبيوتر العلم أنها نوع من النمو الأسفل مثل شجرة العائلة، حيث لديك أجدادك أو الأجداد كبيرة أو هتنوت في القمة، والبطريرك الأم الحاكمة للأسرة، واحد فقط ما يسمى الجذر، عقدة، أدناه وهي أبنائها، أدناه والتي هي أبنائها، أو أحفاد لها بشكل عام. وأي شخص شنقا الجزء السفلي من العائلة شجرة، إضافة إلى كونه أصغر في الأسرة، يمكن أيضا أن تكون فقط بشكل عام ودعا أوراق الشجرة. لذلك هذا هو مجرد حفنة من الكلمات والتعريفات لما يسمى شجرة في الكمبيوتر العلم، مثل الكثير من شجرة العائلة. ولكن هناك التجسيد مربي الحيوانات الأشجار، واحدة منها يسمى شجرة البحث الثنائية. ويمكنك نوع من ندف وبصرف النظر عما يفعل هذا الشيء. حسنا، انها ثنائي بأي معنى؟ أين ثنائي تأتي من هنا؟ آسف؟ انها ليست كثيرا وإما أو. إنها أكثر أن كل من عقد لا يوجد أكثر من طفلين، وكما نرى هنا. بصفة عامة، وtree-- آبائك وأجدادك يمكن أن يكون أكبر عدد ممكن من الأطفال أو الأحفاد كما يريدون في الواقع، وذلك على سبيل المثال يوجد لدينا ثلاثة الأطفال من تلك العقدة اليد اليمنى، ولكن في شجرة ثنائية، وهي عقدة صفر، واحد، أو اثنين من الأطفال إلى الحد الأقصى. وهذا هو خاصية جميلة، لأنه إذا كان هو توج من قبل اثنين، ونحن في طريقنا لتكون قادرة على الحصول على قاعدة سجل قليلا اثنين العمل يجري هنا في نهاية المطاف. لذلك لدينا شيء لوغاريتمي. ولكن أكثر على ذلك في لحظة. شجرة البحث يعني أن الأرقام ترتيب مثل أن الطفل الأيسر ل قيمة أكبر من جذورها. والطفل الصحيح هو أكبر من جذورها. وبعبارة أخرى، إذا كنت تأخذ أي من العقد، والدوائر في هذه الصورة، وينظر إلى يساره الطفل والطفولة حقها، يجب أن تكون أول أقل من، وينبغي أن يكون ثاني أكبر. حتى التعقل تحقق 55. ويترك الأطفال هو 33. انها أقل من. 55، الطفل الصحيح هو 77. انها أكبر من. وهذا هو تعريف العودية. نتمكن من التحقق من كل واحد من هؤلاء العقد ونفس النمط سوف يعقد. لذلك ما هو جميل في شجرة البحث الثنائية، هو أن واحد، يمكننا تنفيذه مع البنية، تماما مثل هذا. وعلى الرغم من أننا رمي الكثير من الهياكل في الخاص بك، انهم نوعا ما بديهية الآن نأمل. بناء الجملة لا تزال غامضة على وجه اليقين، ولكن محتويات عقدة في هذا context-- ونبقى باستخدام عقدة كلمة، سواء كان ذلك على شكل مستطيل على الشاشة أو دائرة، انها مجرد بعض الحاويات العامة، في هذه الحالة من شجرة، مثل واحد رأينا، نحن بحاجة إلى عدد صحيح في كل من العقد وبعد ذلك تحتاج اثنين من المؤشرات لافتا للطفل الأيسر والطفل الصحيح، على التوالي. ولهذا كيف يمكننا تنفيذ ذلك في البنية. وكيف يمكن لي تنفيذه في التعليمات البرمجية؟ حسنا، دعونا نلقي سريعة ننظر إلى هذا المثال صغير. انها ليست وظيفية، ولكني نسخ ولصق هذا الهيكل. وإذا وظيفتي لثنائي يسمى شجرة البحث البحث، وهذا يأخذ حجتين، وN عدد صحيح ومؤشر إلى عقدة، وذلك مؤشر إلى شجرة أو مؤشر إلى جذر شجرة، كيف أذهب حول البحث عن N؟ حسنا، أولا، لأنني التعامل مع مؤشرات، انا ذاهب الى القيام فحص التعقل. إذا متساوين شجرة يساوي فارغة، غير N في هذه الشجرة أم لا في هذه الشجرة؟ لا يمكن أن يكون، أليس كذلك؟ إذا أنا الماضي لاغية، لا يوجد شيء هناك. أنا قد كذلك فقط يقول عمياء عودة كاذبة. إذا كنت تعطيني شيئا، وأنا بالتأكيد لا يمكن العثور على أي N. عدد لذا ماذا يمكن I تأكد الآن؟ أنا سأقول جيدا إلا إذا N هو أقل من كل ما هو في عقدة شجرة بعد أن كنت قد سلمت N قيمة. وبعبارة أخرى، إذا كان عدد أنا تبحث عنه، N، أقل من العقدة هذا أنا أبحث في. والعقدة أنا أبحث في ما يسمى شجرة، ونذكر من المثال السابق للحصول على قيمة في المؤشر، يمكنني استخدام التدوين الأسهم. حتى إذا N هو أقل من شجرة السهم N، أريد أن أذهب المفهوم اليسار. كيف أعبر عن بحث اليسار؟ أن تكون واضحة، إذا كان هذا هو الصورة المذكورة، ولقد تم تمرير هذا أسمى السهم هذا ما يشير لأسفل. وهذا مؤشر شجرة بلدي. أنا لافتا في جذر الشجرة. وأنا أبحث يقول، ل عدد 44، تعسفا. هو أقل من 44 أو أكثر من 55 اضح؟ لذلك فمن أقل من. وحتى هذا إذا تنطبق الحالة. حتى من الناحية النظرية، ماذا أريد أن بحث المقبل إذا أنا أبحث عن 44؟ نعم؟ بالضبط، أريد أن بحث الطفل الأيسر، أو اليسار شجرة فرعية من هذه الصورة. في واقع الأمر، واسمحوا لي من خلال الصورة أسفل هنا لمجرد لحظة، منذ لا أستطيع أن تخدش ذلك. إذا كنت تبدأ هنا في 55، و وأنا أعلم أن قيمة 44 أنا أبحث عن غير ل اليسار، انها نوع من مثل تمزيق دفتر الهاتف في نصف أو تمزيق الشجرة في النصف. أنا لم يعد لديك لرعاية حول هذا الشوط بأكمله من شجرة. وحتى الآن، الغريب من حيث هيكل، وهذا الشيء هنا أن يبدأ 33، هذا في حد ذاته هي شجرة البحث الثنائية. قلت كلمة العودية قبل ل في الواقع هذا هو بنية البيانات التي بحكم التعريف غير متكررة. قد يكون لديك شجرة هذا هذا كبيرة، ولكن كل واحد من أبنائها تمثل شجرة فقط أصغر قليلا. بدلا من كونها الجد أو الجدة، والآن انها مجرد أمي or-- لا أستطيع أن say-- لا أمي أو أبي، التي من شأنها أن تكون غريبة. بدلا من ذلك اثنين من الأطفال هناك سيكون مثل الأخ والشقيق. هناك جيل جديد من شجرة العائلة. ولكن من الناحية الهيكلية، انها نفس الفكرة. واتضح لدي وظيفة التي يمكنني البحث بحث ثنائي شجرة. ويسمى البحث. أنا ابحث عن N في شجرة السهم اليسار آخر إذا N هو أكبر من قيمة انني حاليا في. 55 في القصة قبل لحظة. لدي وظيفة تسمى البحث أستطيع أن مجرد تمرير N هذا وبحث بشكل متكرر الشجرة الفرعية وعودة عادلة أيا كان هذا الجواب. آخر أنا عندي بعض الحالات قاعدة النهائية هنا. ما هو الحال النهائية؟ شجرة إما فارغة. قيمة أنا إما تبحث عنها غير أقل من ذلك أو أكثر من ذلك أو مساويا له. وأستطيع أن أقول يساوي على قدم المساواة، ولكن منطقيا انها أي ما يعادل فقط أقول آخر هنا. ذلك صحيح هو كيف أجد شيئا. لذلك نأمل هذا هو حتى سبيل المثال أكثر إقناعا من وظيفة سيغما غبية فعلنا بضع محاضرات الوراء، حيث كان مثلما من السهل استخدام حلقة إلى العد حتى جميع الأرقام من واحد لN. هنا مع بنية بيانات هذا في حد ذاته هو متكرر محددة ومرسومة بشكل متكرر، ونحن الآن لديك القدرة على التعبير عن أنفسنا في التعليمات البرمجية التي في حد ذاته هو عودي. لذلك هذا هو نفس رمز بالضبط هنا. لذلك ما هي المشاكل الأخرى التي يمكننا حل؟ لذلك خطوة سريعة بعيدا عن الأشجار لمجرد لحظة. هنا، يقول، العلم الألماني. وهناك بشكل واضح نمط لهذا العلم. وهناك الكثير من الأعلام في العالم هي بسيطة مثل هذا من حيث من الألوان والأنماط. ولكن لنفترض أن هذا يتم تخزين باعتباره . GIF أو JPEG أو نقطية، أو بينغ، أي تنسيق ملف رسومي التي كنت على دراية، والبعض منها نحن اللعب مع في PSET4. لا يبدو هذا جدير بالاهتمام لتخزين بكسل أسود، أسود بكسل، بكسل السوداء، نقطة، نقطة، نقطة، في مجمله مجموعة من بكسل سوداء للscanline للأول، أو صف، ثم مجموعة كاملة من نفس، ثم مجموعة كاملة للنفس، وبعد ذلك مجموعة كاملة من وحدات البكسل الحمراء، بكسل الحمراء، بكسل الحمراء، ثم ككل حفنة من بكسل، الأصفر، أليس كذلك؟ هناك مثل هذه الكفاءة هنا. كيف حدسي ضغط العلم الألماني إذا تنفيذها كملف؟ مثل ما هي المعلومات التي لا يمكننا تهتم تخزين على القرص من أجل لتقليل حجم الملف لدينا من مثل ميغا بايت إلى كيلوبايت، شيء أصغر؟ حيث يكمن التكرار هنا أن يكون واضحا؟ ماذا يمكن أن تفعل؟ نعم؟ بالضبط. لماذا لا بدلا من تذكر لون كل بكسل الرتق تماما مثل تفعلونه في PSET4 مع شكل ملف صورة نقطية، لماذا لا مجرد تمثيل العمود أقصى اليسار من بكسل، على سبيل المثال حفنة من بكسل سوداء، وحفنة من الأحمر، وحفنة من الأصفر، وبعد ذلك فقط بطريقة أو بأخرى ترميز فكرة تكرار هذا 100 مرة أو تكرار هذا 1000 مرات؟ حيث 100 أو 1000 هو فقط عدد صحيح، لذلك أنت يمكن أن تفلت من مجرد رقم واحد بدلا من مئات أو آلاف بكسل إضافية. وبالفعل، هذه هي الطريقة التي يمكن ضغط العلم الألماني. و الآن ماذا عن العلم الفرنسي؟ ونوعا من القليل التمرين الذهني، الذي علم يمكن ضغط أكثر على القرص؟ العلم الألماني أو الفرنسي العلم، وإذا أخذنا هذا النهج؟ العلم الألماني، لأنه لا يوجد المزيد من التكرار الأفقي. وحسب التصميم، العديد من الملفات الرسومية صيغ لا بل تعمل خطوط المسح كما أفقيا. ويمكن أن تعمل عموديا والإنسانية العادلة منذ سنوات قررت أننا سوف أعتقد عموما من الأشياء التوالي بواسطة صف بدلا من عمود بواسطة عمود. حتى لو كنت بالفعل للنظر في الملف حجم العلم الألماني والفرنسي العلم، طالما أن القرار هو نفس، نفس العرض والارتفاع، وهذا واحد هنا ستكون أكبر، لأنك يجب أن تكرر نفسك ثلاث مرات. لديك لتحديد الأزرق، كرر نفسك، والأبيض، تكرر نفسك والأحمر، تكرر نفسك. لا يمكنك اذهبوا جميع الطريق إلى اليمين. وبوصفها جانبا، لجعل مسح ضغط هو في كل مكان، إذا كانت هذه هي أربعة إطارات من video-- لك قد نذكر أن الفيلم أو الفيديو بشكل عام مثل 29 أو 30 لقطة في الثانية الواحدة. انها مثل كتاب الوجه قليلا حيث كنت انظر فقط صورة، صورة، صورة، صورة، مجرد صورة بسرعة فائقة بحيث يبدو مثل الجهات الفاعلة على الشاشة تتحرك. وهنا تلعثم نحلة على أعلى باقة من الزهور. وعلى الرغم من أنه قد يكون نوع من من الصعب أن نرى للوهلة الأولى، الشيء الوحيد الذي يتحرك في هذا الفيلم هو النحل. ما هو البكم حول تخزين فيديو غير مضغوط؟ انها نوع من النفايات لتخزين الفيديو أربعة صور متطابقة تقريبا أن تختلف إلا بقدر فيها النحل. يمكنك رمي بعيدا أكثر تلك المعلومات وتذكر فقط، على سبيل المثال، الإطار الأول والإطار الأخير، الأطر الرئيسية إذا كنت قد سمع كلمة، وتخزن فقط في الوسط حيث النحل. ولم يكن لديك ل تخزين كافة الوردي، والأزرق، و قيم الخضراء كذلك. لذلك هذا هو القول فقط أن ضغط في كل مكان. انها تقنية نحن غالبا ما تستخدم أو أمرا مفروغا منه في هذه الأيام. ولكن كيف يمكنك ضغط النص؟ كيف يمكنك أن تذهب نحو ضغط النص؟ حسنا، كل من الأحرف في أسكي بايت واحد، أو ثمانية بت. وهذا نوع من البكم، أليس كذلك؟ لأن ربما كنت اكتب A وE وI و O و U الكثير في كثير من الأحيان مثل W أو Q أو Z، اعتمادا على اللغة التي كنت تكتب بالتأكيد. وهكذا لماذا نستخدم ثمانية بت لكل حرف، بما في ذلك أقل رسائل شعبية، أليس كذلك؟ لماذا لا تستخدم بت أقل لل الرسائل سوبر شعبية، مثل E، والأشياء التي تخمين لأول مرة في عجلة الحظ، واستخدام أكثر من بت ل الرسائل أقل شعبية؟ لماذا؟ لأننا ذاهبون لمجرد استخدامها أقل كثيرا. حسنا، اتضح أن هناك من كانت محاولات للقيام بذلك. وإذا كنت تذكر من الصف المدرسة أو في المدرسة الثانوية، مورس. مورس ديه النقاط وشرطات التي يمكن أن يكون تنتقل على طول الأسلاك على النحو الأصوات أو إشارات من نوع ما. لكن مورس هو السوبر نظيفة. انها نوع من نظام ثنائي في أن لديك النقاط أو شرطات. ولكن إذا كنت انظر، على سبيل المثال، واثنين من النقاط. أو إذا كنت تعتقد أن يعود إلى المشغل الذي يذهب مثل صفير، صفير، زمارة، زمارة، لتصل إلى الزناد قليلا التي تنقل إشارة، إذا كنت، المتلقي، يتلقى اثنين النقاط، ما هي الرسالة التي تلقيتها؟ تعسفية تماما. أنا؟ أنا؟ أو ما about-- أم أنا؟ ربما كان اثنين فقط الحق في E؟ لذلك هناك هذه المشكلة من decodability مع مورس رمز، حيث ما لم يكن شخص يرسل لك رسالة توقف فعليا حتى تتمكن من فرز لل رؤية أو سماع الفجوات بين الحروف، انها ليست كافية فقط ل إرسال تيار من الآحاد والأصفار و، أو النقاط وشرطات، لأن هناك غموض. E هو نقطة واحدة، حتى إذا كنت نرى اثنين من النقاط أو سماع اثنين من النقاط، ربما انها وهما E أو ربما انها واحدة I. لذلك نحن بحاجة إلى نظام هذا هو قليلا أكثر ذكاء من ذلك. حتى رجل يدعى هوفمان سنوات منذ جاء مع هذا بالضبط. لذلك نحن ذاهبون فقط لنلقي نظرة سريعة في كيفية أشجار مناسبة إلى هذا. لنفترض أن هذا هو بعض رسالة الغبية التي تريد إرسالها، تتألف من مجرد A، B، C وD'الصورة وللE، ولكن هناك الكثير من التكرار هنا. ليس من المفترض أن تكون باللغة الإنجليزية. ليست مشفرة. انها مجرد رسالة غبية مع الكثير من التكرار. لذلك إذا كنت تعول فعلا كل أ، ب، وعلى C، D 'ق، وعلى E، هنا التردد. 20٪ من الرسائل هي أ، 45٪ من الرسائل هي وE، وثلاثة ترددات أخرى. احصينا حتى هناك يدويا وفعلت الرياضيات. هكذا اتضح أن هوفمان، منذ بعض الوقت، أدركت ذلك، كما تعلمون ما، إذا كنت تبدأ بناء شجرة أو غابة من الأشجار، اذا صح التعبير، على النحو التالي، يمكنني القيام بما يلي. انا ذاهب لإعطاء عقدة لكل من الرسائل التي يهمني وانا ذاهب لتخزين داخل تلك العقدة ترددات كنقطة العائمة القيمة، أو هل يمكن استخدامها لN، أيضا، ولكننا سوف مجرد استخدام تعويم هنا. والخوارزمية التي اقترح هو أنك تأخذ هذه الغابة من عقدة واحدة الأشجار، والأشجار حتى فائقة قصيرة، وتبدأ ربطهم مجموعات جديدة، الآباء والأمهات الجدد، اذا صح التعبير. ويمكنك القيام بذلك عن طريق اختيار اثنين من أصغر الترددات في وقت واحد. لذلك أخذت 10٪ و 10٪. I إنشاء عقدة جديدة. وأدعو عقدة جديدة 20٪. التي عقدتين أنا أضم بعد ذلك؟ انها غامضة قليلا. لذلك هناك بعض الحالات الزاوية ل النظر، ولكن للحفاظ على الأشياء جميلة، انا ذاهب الى اختيار 20٪ - أنا الآن تجاهل الأطفال. انا ذاهب الى اختيار 20٪ و 15٪ والتعادل مرتين حواف جديدة. والآن الذي عقدتين أقوم منطقيا الجمع؟ تجاهل جميع الأطفال، وجميع الأحفاد، مجرد إلقاء نظرة على جذور الآن. التي عقدتين يمكنني ربط معا؟ النقطة الثانية و 0.35. لذلك اسمحوا لي رسم الحدين جديدة. ثم أنا عندي واحد فقط اليسار. وحتى هنا شجرة. ولقد تم وضع عمدا للبحث النوع من جميلة، ولكن لاحظ أن حواف لها كما وصفت صفر واحد. لذلك كل من الحواف اليسرى صفر تعسفا، ولكن باستمرار. جميع الحواف اليمنى هي تلك. وماذا في ذلك المقترح هوفمان غير، إذا كنت تريد أن تمثل B، بدلا من تمثيل العدد 66 كما وأسكي وهو ثمانية بت بأكملها، تعلمون ما، مخزن عادل نمط صفر، صفر، صفر، الصفر، لأن هذا هو الطريق من شجرة بلدي، شجرة السيد هوفمان، و على ورقة من جذورها. إذا كنت ترغب في تخزين E، على النقيض من ذلك، لا إرسال ثماني بتات التي تمثل E. بدلا من ذلك، إرسال ما نمط البتات؟ واحدة. وما هو جميل عن هذا أن E هو حرف الأكثر شعبية، وكنت تستخدم أقصر رمز لذلك. في اليوم التالي الأكثر شعبية الرسالة يبدو أنه كان A. وهكذا وكم بت وقال انه لم يقترح استخدام لذلك؟ صفر، واحد. وبسبب انها نفذت كما هذه الشجرة، في الوقت الراهن اسمحوا لي أن تنص هناك أي غموض كما هو الحال في مورس رمز، لأن كل من رسائل يهمك هي في نهاية هذه الحواف. حتى أن واحدة فقط تطبيق شجرة. هذا is-- وسوف موجة يدي في هذه الطريقة التي قد تنفيذ هذا كهيكل C. نحن بحاجة فقط إلى الجمع بين رمز، مثل شار، وتردد في اليسار واليمين. ولكن دعونا ننظر إلى اثنين أمثلة النهائية التي عليك الحصول على دراية تامة مع بعد مسابقة صفر في مشكلة تعيين خمسة. حتى لا يكون هناك بنية البيانات يعرف جدول تجزئة. وجدول تجزئة هو نوع من تهدئة في أن لديها الدلاء. وافترض هناك أربعة دلاء هنا، فقط أربعة مسافات فارغة. وإليك مجموعة من البطاقات، وهنا نادي، الأشياء بأسمائها الحقيقية، النادي، الماس، النادي، الماس، النادي، الماس، clubs-- لذلك هذا هو عشوائي. قلوب، hearts-- لذلك أنا bucketizing كل من المدخلات هنا. والاحتياجات جدول التجزئة للنظر في المدخلات الخاصة بك، ومن ثم وضعها في بعض وضع بناء على ما تراه. انها خوارزمية. وكنت تستخدم عظمى خوارزمية بصرية بسيطة. وكان أصعب جزء منها تذكر ما كانت الصور. وبعد ذلك هناك أربع مجموع الأشياء. الآن مداخن كانت تنمو، والتي هو شيء متعمدا هنا. ولكن ماذا قد أفعل؟ حتى في الواقع لدينا هنا مجموعة من الكتب القديمة امتحان المدرسة. لنفترض أن مجموعة من أسماء الطلاب هم هنا. وفيما يلي جدول تجزئة أكبر. بدلا من أربعة دلاء، لقد، دعنا نقول 26. وأننا لا نريد أن يذهب اقتراض 26 أشياء من الخارج [؟ أننبرغ؟]، لذلك وهنا الخمسة التي تمثل A من خلال Z. وإذا أنا رؤية الطالب الذي يبدأ مع اسم، انا ذاهب الى وضع له أو مسابقة لها هناك. إذا بدأ شخص ما مع C، هناك، A-- في الواقع، لا تريد أن تفعل ذلك. B يذهب أكثر من هنا. حتى أنا عندي ألف وباء وجيم و الآن هنا وهناك طالب آخر. لكن إذا كان هذا هو جدول التجزئة نفذت مع صفيف، انا من النوع مشدود عند هذه النقطة، أليس كذلك؟ النوع الأول من حاجة لوضع هذا في مكان ما. حتى طريقة واحدة أستطيع أن حل هذا هو، كل الحق، A مشغول، B مشغول، C مشغول. انا ذاهب الى وضعه في D. حتى في أولا، أود أن إمكانية الوصول الفوري عشوائي إلى كل من الدلاء للطلاب. ولكن الآن انها نوع من آلت إلى شيء الخطية، لأنه إذا أريد للبحث عن شخص ما اسم الذي يبدأ مع A، I التحقق من هنا. ولكن إذا لم تكن هذه هي A طالب أنا أبحث عن، النوع الأول من أن تبدأ فحص الدلاء، لأن ما فعلته كان نوعا من خطيا تحقيق بنية البيانات. وهناك طريقة غبية لقول ننظر فقط لأول افتتاح المتاحة، وضعت كخطة B، إذا جاز التعبير، أو خطة D في هذه الحالة، فإن القيمة في هذا المكان بدلا من ذلك. هذا هو مجرد بحيث إذا قمت حصلت 26 موقعا وليس الطلاب مع اسم Q أو Z، أو شيء من هذا القبيل هذا، على الأقل كنت تستخدم الفضاء. ولكن رأيناه بالفعل أكثر حلول ذكية هنا، أليس كذلك؟ ماذا كنت ستفعل بدلا إذا كان لديك الاصطدام؟ إذا كان اثنان الناس اسم A، ما من شأنه وقد كان أكثر ذكاء أو أكثر حل بديهية من مجرد وضع A حيث من المفترض D أن تكون؟ لماذا لا اذهب فقط [الخارجي؟ أننبرغ؟]، مثل malloc، عقدة أخرى، ووضعها هنا، ثم وضع هذا الطالب هنا. ذلك أن لدي أساسا نوع من صفيف، أو ربما أكثر أناقة كما نحن بدأنا نرى قائمة مرتبطة. وهكذا جدول تجزئة هو هيكل قد تبدو وكأنها مجرد هذا، ولكن أكثر بذكاء، كنت ما يسمى تسلسل منفصلة، ​​حيث جدول تجزئة بكل بساطة عبارة عن صفيف، كل من عناصره ليس العدد، هو في حد ذاته قائمة مرتبطة. بحيث يمكنك الوصول بسرعة فائقة البت فيها لتجزئة القيمة ل. يشبه إلى حد كبير مع المثال بطاقات، I اتخاذ القرارات سوبر سريعة. قلوب يذهب هنا والماس يذهب هنا. نفسه هنا، A يذهب هنا، D يذهب هنا، B يذهب هنا. لذلك بسرعة فائقة نظرة المنبثقة، وإذا كنت يحدث لتصل الى حالة اصطدام حيث كنت قد حصلت، وهما الناس بنفس الاسم، بالاضافة الى ذلك الحين كنت مجرد بداية ربطها معا. وربما كنت الاحتفاظ بها مرتبة حسب الترتيب الأبجدي، وربما كنت لا. ولكن على الأقل لدينا الآن دينامية. لذلك من جهة لدينا بسرعة فائقة وقت ثابت، ونوع من الزمن الخطي تشارك إذا كانت هذه القوائم المرتبطة تبدأ في الحصول على فترة طويلة بعض الشيء. لذلك هذا النوع من سخيفة، منذ سنوات نكتة العبقري غريب الأطوار. في CS50 الإختراق واحد في ثون، عندما تحقق الطلاب في، بعض TF أو CA سنويا يعتقد انه مضحك لطرح لافتة مثل هذا، حيث أنها مجرد يعني اذا كان اسمك يبدأ مع A، السير في هذا الطريق. إذا يبدأ اسمك مع B، انتقل this-- OK، انه مضحك ربما في وقت لاحق في فصل دراسي. ولكن هناك أخرى طريقة للقيام بذلك أيضا. أعود إلى ذلك. ولذلك لا يوجد هذا الهيكل. وهذا هو موقفنا الأخير هيكل لهذا اليوم، وهو ما يسمى TRIE. T-R-I-E، التي لسبب غير قصيرة لاسترجاع المعلومات، لكنه دعا TRIE. لذلك TRIE هو اهتمام آخر مزيج من الكثير من هذه الأفكار. انها شجرة، والذي رأيناه من قبل. انها ليست شجرة البحث الثنائية. انها شجرة مع أي عدد من الأطفال، ولكن كل واحد من الأطفال في TRIE عبارة عن صفيف. مجموعة من حجم، ويقول، 26 أو ربما 27 إذا كنت تريد أن يعتمد أسماء الواصلة أو apostrophes في أسماء الناس. وحتى هذا هو بنية البيانات. وإذا نظرت من أعلى إلى أسفل، مثل إذا كنت ننظر إلى العقدة العليا هناك، M، هو لافتا إلى أقصى اليسار شيء هناك، وهو بعد ذلك A، X، W، E، L، L. هذا هو مجرد هيكل البيانات التي تعسفا هو تخزين أسماء الناس. ويتم تخزين ماكسويل فقط عن طريق التالية مسار من مجموعة إلى مجموعة إلى مجموعة. ولكن ما هو مدهش عن TRIE هو هذا، في حين أن قائمة مرتبطة، وحتى صفيف، أفضل ما لدينا من أي وقت مضى حصلت هو الزمن الخطي أو الوقت لوغاريتمي أبحث شخص ما. في هذا الهيكل بيانات من TRIE، إذا هيكل البيانات بلدي لديه اسم واحد في ذلك وأنا أبحث عن ماكسويل، وأنا الذهاب للعثور عليه بسرعة كبيرة. أنا مجرد إلقاء نظرة عن M-A-X-W-E-L-L. إذا هذه البنية البيانات، على النقيض من ذلك، إذا هو N مليون، إذا كان هناك مليون الأسماء في هذه البنية البيانات، ماكسويل لا تزال جارية ليكون اكتشاف بعد فقط M-A-X-W-E-L-L الخطوات. والخطوات David-- D-A-V-I-D. وبعبارة أخرى، من خلال بناء بنية بيانات هذا حصلت كل هذه المصفوفات، وكلها أنفسهم دعم الوصول العشوائي، أستطيع أن تبدأ في النظر حتى من الناس اسم باستخدام مقدار الوقت الذي ل لا يتناسب مع عدد من الأشياء في بنية البيانات، مثل ملايين الأسماء الموجودة. مقدار الوقت الذي يستغرقه لي أن تجد M-A-X-W-E-L-L في هذا الهيكل بيانات غير يتناسب ليس ل حجم بنية البيانات، ولكن لطول الاسم. واقعي أسماء نحن نبحث عن ولن تكون مجنون لفترة طويلة. ربما شخص له طابع 10 تسمية 20 حرف الاسم. انها محدود بالتأكيد، أليس كذلك؟ هناك إنسان على وجه الأرض الذي لديه أطول اسم ممكن، ولكن هذا الاسم هو ثابت طول قيمة، أليس كذلك؟ أنها لا تختلف بأي حال من الأحوال. حتى في هذه الطريقة، لدينا حقق بنية البيانات هذا هو وقت ثابت نظرة المتابعة. وهو يفعل اتخاذ عدد من الخطوات اعتمادا على طول المدخلات، ولكن ليس عدد اسم في بنية البيانات. حتى إذا ضاعفنا عدد من الأسماء العام المقبل من مليار إلى ملياري، النتيجة ماكسويل هو ذاهب الى اتخاذ العدد الدقيق نفسه من سبع خطوات للعثور عليه. وهكذا يبدو أننا حققنا لدينا الكأس المقدسة من إدارة الوقت. حتى بضعة إعلانات سريعة. مسابقة الصفر هو الخروج. أكثر على ذلك على الموقع الإلكتروني للدورة ل على مدى اليومين المقبلين. يوم الاثنين lecture-- انها عطلة هنا في جامعة هارفارد يوم الاثنين. انها ليست في نيو هافن، لذلك نحن اتخاذ الطبقة إلى نيو هيفن للمحاضرة يوم الاثنين. وسيتم تصوير كل شيء وبثها كالمعتاد، ولكن دعونا تنتهي اليوم مع 30 مقطع الثاني ودعا "أفكار عميقة" بواسطة Daven فارنهام، التي واستلهم من العام الماضي بنسبة السبت "أفكار عميقة" ليلة لايف جاك هاندي، التي الآن يجب أن يكون له معنى. FILM: والآن، "ديب الأفكار "التي Daven فارنهام. جدول تجزئة. رئيس 1: كل الحق، هذا كل شيء في الوقت الراهن. سنرى في الأسبوع القادم. DOUG: لرؤيتها في العمل. لذلك دعونا نلقي نظرة على ذلك الآن. حتى هنا، لدينا مجموعة غير مصنفة. IAN: دوغ، يمكنك ان تمضي قدما وإعادة التشغيل هذا لثانية واحدة فقط، من فضلك. كل الحق، والكاميرات تدور، لذلك العمل كلما كنت على استعداد، دوغ، OK؟ DOUG: حسنا، فما نحن لدينا هنا هو مجموعة غير مصنفة. ولقد الملونة كل العناصر الأحمر للإشارة إلى أنه هو، في الواقع، لم يتم فرزها. لذلك نذكر أن أول شيء نقوم به غير أننا فرز النصف الأيسر من مجموعة. ثم نحن فرز الحق نصف المصفوفة. ويا دا، يا دا، يا دا، نحن دمجها معا. ونحن لدينا مجموعة وفرزها تماما. لذلك هذه هي الطريقة دمج النوع يعمل. IAN: قف، قف، قف، قطع، قطع، قطع، قطع. دوغ، لا يمكنك فقط يا دا، يا دا، يا دا، في طريقك من خلال دمج النوع. DOUG: فعلت للتو. لا بأس. نحن على ما يرام. دعونا فقط الحفاظ المتداول. على كل حال، IAN: لديك لشرح أكثر من ذلك تماما. هذا فقط لا يكفي. DOUG: إيان، ونحن لا بحاجة إلى أن نعود إلى واحد. لا بأس. لذلك على أي حال، إذا واصلنا مع merge-- إيان، ونحن في منتصف التصوير. IAN: أعرف. ونحن لا نستطيع فقط يا دا، يا دا، يا دا، من خلال العملية برمتها. لديك لشرح كيفية الحصول على دمج الجانبين معا. DOUG: ولكن لدينا بالفعل شرح كيف أن sides-- اثنين IAN: لقد أظهرت فقط لهم مجموعة الدمج. DOUG: إنهم يعرفون هذه العملية. انهم بخير. لقد ذهب أكثر من ذلك عشر مرات. IAN: أنت تخطي مجرد حق أكثر من ذلك. ونحن في طريقنا إلى واحد، كنت لا يمكن لك يا دا، يا دا أكثر من ذلك. كل الحق، والعودة إلى واحد. DOUG: لا بد لي من العودة من خلال كافة الشرائح؟ يا إلاهي. انها مثل للمرة السادسة، إيان. لا بأس. IAN: حسنا. هل انت مستعد؟ رائعة. حركة.