DAVID مالان: حسنا. نرحب مرة أخرى إلى CS50. هذا هو بداية الاسبوع 8. ونذكر بأن المشكلة انتهت بتعيين 5 مع القليل من التحدي. حتى على افتراض انك تعافى كل الكلمات تدريس الزملاء والصور، CA في في ملف card.raw، كنت مؤهلا لتجد الآن كل من هؤلاء الناس، و الفائز المحظوظ واحد سوف المشي في المنزل مع واحد من هذه الأشياء، وحركة قفزة الجهاز الذي يمكنك استخدامه للنهائي المشاريع، على سبيل المثال. 

هذا، في كل عام، ويؤدي إلى قليلا من القشعريرة. وذلك ما اعتقدت به هو حصة معك بعض الملاحظات التي لديها ذهب ذهابا وإيابا على قائمة الموظفين في وقت متأخر. على سبيل المثال، فقط الليلة الماضية، واقتبس نهاية الاقتباس، من أحد الموظفين أعضاء، "أنا كان مجرد ضربة طالب على بابي لالتقاط صورة معي. الملاحقون، وأنا أقول لك. "كتبت قبالة صفية إلى حد ما ثم انتقلنا على ل، ساعة أو نحو ذلك في وقت لاحق، "كان لي طالب ينتظرني بعد القسم وكان لديه كل من أسمائنا والصور على بعض ورقة من الورق. "حسنا. لذلك نظمت، ولكن ليس كل ما زاحف حتى الآن. 

ثم، وقال "كنت خارج المدينة في نهاية هذا الاسبوع، وعندما عدت، كان هناك واحد في لي غرفة نوم ". [ضحك] DAVID مالان: اقتباس التالي من الموظفين عضو "، وجاء الطالب إلى بيتي في سمرفيل في 04:00 صباح اليوم. "التالي الموظفين، "وصلت إلى فندقي في سان فرانسيسكو وطالب كان ينتظر لي في بهو الفندق مع ثلاثة DSLRS ". نوع الكاميرا. "أنا لست حتى على الموظفين في هذا الفصل الدراسي، ولكن كسرت طالب في بيتي هذا الصباح وسجلت كل شيء مع جوجل الزجاج. "ثم أخيرا، "كان 12 شخصا على الاقل بفارغ الصبر في انتظار بالنسبة لي عندما خرجت من بلدي ليموزين، وبعد ذلك استيقظت. "حسنا. حتى بين الصور، كما كنت قد أذكر، وهذا الزميل هنا، من أنت قد تعرف باسم ميلو الموز، الذي يعيش مع لورين كارفاليو، رؤوسنا تدريس زميل. ميلو، ميلو، وتأتي هنا الصبي. ميلو. ميلو. فتذكروا، وقال انه يرتدي جوجل الزجاج، لذلك سنوضح لك كل هذا بعد. لذلك هذا هو ميلو إذا كنت ترغب في التقاط صورة معه بعد ذلك. إذا كنت ترغب في أن ينظر خارجا في الجمهور هناك. موافق. هذا هو لقطات جيدة. حسنا، ميلو الموز. أوه، لا تفعل ذلك. 

[ضحك] 

موافق. حتى كلمة واحدة ثم على ما ينتظرنا في المستقبل، لأنه كما أن نبدأ في الانتقال، هذا الأسبوع تحديدا، من C في بيئة سطر الأوامر لPHP و جافا سكريبت وSQL و HTML و CSS في بيئة على شبكة الإنترنت، ونحن سوف تكون تجهيز لكم مع كل مزيد من المعرفة ل المشاريع النهائية المحتملة. من اجل هذا الهدف، وبالطبع لديه تقليد عقد الندوات التي هي حول مواضيع عرضية للدورة. تتعلق كثيرا في البرمجة و تطوير التطبيق وهكذا دواليك، ولكن لم تستكشف بالضرورة منهج الدورة الخاصة. 

لذلك إذا كنت قد تكون مهتمة في واحد أو أكثر من الحلقات الدراسية لهذا العام، التسجيل في cs50.net/seminar. هناك ندوات كبار السن في cs50.net/seminars. وعلى القائمة حتى الآن لهذا العام هي تطبيقات ويب مذهلة مع روبي على القضبان، والذي هو بديل لغة PHP. اللسانيات الحاسوبية. مقدمة لدائرة الرقابة الداخلية، والذي هو منصة الذي يتم استخدامه للآيفون و التنمية باد. جافا سكريبت لتطبيقات الويب، سنقوم تغطية ذلك، ولكن في هذه الندوة، عليك أن تذهب في مزيد من التفاصيل. 

قفزة الحركة، لذلك سيكون لدينا فعلا بعض من أصدقائنا من قفزة الحركة، الشركة نفسها، والانضمام إلينا. غدا، في الواقع، لتوفير ندوة التدريب العملي على، إذا ذات فائدة لكم. Meteor.js، وهي تقنية بديلة لل باستخدام جافا سكريبت ليس في المتصفح، ولكن على الخادم. Node.js، والتي هي إلى حد كبير في هذا السياق أيضا. أنيق تصميم الروبوت. الروبوت كونه بديل شعبية جدا لدائرة الرقابة الداخلية ويندوز فون وغيرها من منصات متحركة. والأمن الإنترنت الدفاع بالموقع. 

ذلك في الواقع، إذا كنت ترغب للمشاركة في هذا، اسمحوا لي جعل علما بذلك. نحن سعداء جدا أن أقول أن أصدقائنا في قفزة الحركة، وهو بدء التشغيل - هذا الجهاز حقا خرج للتو من قبل بضعة أشهر - تبرعت تكرم 30 من هذه الأجهزة إلى الفئة للعديد من الطلاب، وإذا كان كنت ترغب في استعارة الأجهزة نحو نهاية الفصل الدراسي واستخدامها ل مشروع النهائي الفعلي. أنها تدعم عددا من اللغات. أيا منها C، فإن أيا منها PHP، لذلك تحقيق واحد أو أكثر من هذه الندوات قد يكون من الفائدة. وجميعهم سوف يتم تصويره في الحدث الذي لم تكن قادرا الحضور شخصيا. يتم الإعلان عن الجدول الزمني عبر البريد الالكتروني ونحن يصلب الغرف. 

وأخيرا، إذا كنت تذهب ل projects.cs.50.net، وهذا هو موقع على شبكة الانترنت نحافظ كل عام أن ندعو الناس من المجتمع وأعضاء هيئة التدريس، الإدارات والموظفين، وعلى حد سواء في خارج CS50 ل اقتراح أفكار المشاريع. الأمور التي تهم الجماعات الطلابية. الأمور التي تهم الإدارات. حتى لا تتحول إلى هناك إذا كنت تناضل مع عدم اليقين بشأن ما كنت نفسك ترغب في التصدي لها. 

مشاركة من الوقت قدمنا ​​ويمكن القول بنية بيانات أكثر تعقيدا مما كنا رأينا في الأسابيع الماضية. كنا تم استخدام المصفوفات جميلة لحسن الحظ باعتباره مفيدا إذا بنية البيانات في التبسيط. ثم قدمنا ​​هذه، التي بالطبع والقوائم المرتبطة. وماذا كان واحدا من الدوافع ل إدخال البيانات هذا الهيكل؟ نعم؟ ما هذا؟ 

الجمهور: حجم الحيوي. 

DAVID مالان: حجم الحيوي. ذلك في حين أنه في مجموعة، لديك ل تعرف حجمها في وقت مبكر عندما كنت تحيله. في قائمة مرتبطة، كنت لا لديك لمعرفة ذلك. يمكنك malloc فقط، أو بصورة أعم، تخصيص مبلغ إضافي العقدة، إذا جاز التعبير، في أي وقت كنت تريد إدراج المزيد من البيانات. وليس لديه عقدة محددة سلفا معنى. انها مجرد مصطلح عام يصف نوع من الحاوية التي نحن استخدام في بنية البيانات لدينا لتخزين بعض بند المصالح، وهو في هذه الحالة يحدث أن تكون صحيحة. 

ولكن هناك دائما المفاضلة. حتى نحصل على أحجام الديناميكي للبيانات هيكل، ولكن ما هو الثمن الذي ندفعه لا؟ ما هو الجانب السلبي من القوائم المرتبطة؟ نعم؟ 

الحضور: يتطلب المزيد من الذاكرة. 

DAVID مالان: إنه يتطلب أكثر الذاكرة، وكيف بالضبط؟ 

الحضور: [غير مسموع]. 

DAVID مالان: بالضبط. حتى الآن لدينا مؤشرات تناول ذاكرة إضافية أننا سابقا لم تكن في حاجة، وذلك لأن ميزة من صفيف، بطبيعة الحال، هو أن كل شيء متجاورة، ومرة ​​أخرى إلى العودة إلى الوراء، والتي يمنحك الوصول العشوائي. لمجرد باستخدام قوس مربع التدوين، أو أكثر من الناحية الفنية المؤشر الحسابي، بالإضافة إلى ذلك بسيط جدا، يمكنك الوصول إلى أي عناصر في وقت ثابت. في واقع الأمر، وهذا النوع من ملمحا إلى آخر سعر أننا ندفع مع قائمة مرتبطة. 

ما يحدث للوقت تشغيل شيء من هذا القبيل البحث، إذا أريد ل العثور على بعض القيمة وداخل من قائمة مرتبطة؟ ماذا تصبح وقتي تشغيل؟ O كبيرة من ن. إذا فإنه يتم فرز ل؟ ماذا لو تم فرزها بنية البيانات و؟ يمكنني أن أفعل أفضل من الكبيرة O ن للبحث؟ لا، لأنه في أسوأ الحالات فإنه قد بشكل جيد للغاية أن يتم فرز، ولكن عدد كنت تبحث عن قد تكون كبيرة. قد يكون عدد 100، والتي قد يحدث أن تكون جميع الطريق في نهاية المطاف. ولأن يمكنك فقط الوصول مرتبط القائمة في هذا التنفيذ من قبل الطريقة الأولى من عقدة لها، وكنت لا يزال نوع من من الحظ. عليك أن تجتاز كل شيء من أول إلى آخر من أجل إيجاد تلك القيمة الكبيرة مثل 100. أو لتحديد ما اذا كان ولا حتى هناك. 

لذلك لا نستطيع أن نفعل ما الخوارزمية في البيانات هيكل يشبه هذا؟ لا نستطيع أن نفعل البحث الثنائي، ل البحث الثنائية المطلوبة التي كان لدينا الوصول العشوائي. أننا يمكن أن مجرد قفزة من مكان ل موقع دون الحاجة إلى اتباع هذه فتات الخبز في شكل كل هذه المؤشرات. 

الآن، كيف ننفذ هذا؟ حسنا، إذا ذهبنا إلى الشاشة هنا، إذا يمكننا reimplement بسرعة هذه البيانات هيكل - بلدي خط اليد ليست كل ما كبيرة هنا، ولكن سنحاول. البنية الرموز المميزة ل typedef ذلك، وماذا فعلت أنا نريد أن نسمي هذا الشيء هنا؟ العقدة. ولذا فإنني سوف يحصل لنا بدأت. والآن، ما يجب أن يكون داخل بنية البيانات لهذا منفردة قائمة مرتبطة؟ كيف العديد من المجالات؟ 

حتى اثنين. واحدة من السهل جدا. لذلك الباحث ن. ويمكن أن نسميه ن أي شيء نريد، لكن يجب أن يكون عدد صحيح إذا نحن تنفيذ قائمة مرتبطة لرجات. والآن ما يفعله الثاني المجال يجب أن تكون؟ عقدة البنية *. حتى لو كنت تفعل البنية عقدة *، وبعد ذلك يمكن أن نسمي هذا أيضا ما أريد، ولكن مجرد أن تكون واضحة سأتصل فإنه المقبل، كما كنا نفعل. وبعد ذلك سوف يغلق بلدي الأقواس المتعرجة. 

والآن، كما في المرة السابقة، أنا وضعت أسفل العقدة هنا. ولكن إذا أنا أعلن هذا كما هو عقدة، لماذا لم أكن عناء يجري ذلك مطول هنا في اعلان البنية * عقدة المقبل، كما يعارض إلى عقدة فقط * في المرة القادمة؟ نعم؟ 

الحضور: [غير مسموع]. 

DAVID مالان: بالضبط. بالضبط. لأن C يأخذ حقا لكم حرفيا و يرى فقط تعريف العقدة الطريق إلى هنا، لا يمكنك الرجوع إليه هنا. لذلك لدينا هذا النوع من قائية إعلان هنا، والتي هي باعتراف الجميع أكثر مطول. عقدة البنية، وهذا يعني يمكننا الوصول إليه الآن داخل بنية البيانات. 

وبوصفها جانبا، لأن هذا هو أصبحت أكثر قليلا الذاتية الآن، النجم يمكن أن تذهب من الناحية الفنية هنا، يمكن أن تذهب هنا، فإنه يمكن حتى تذهب في الوسط. لقد اعتمدت، في دليل أسلوب ل وبطبيعة الحال، فإن اتفاقية وضع النجم الحق بجانب البيانات الكتابة، وهو في هذه الحالة، سيكون عقدة البنية. ولكن ندرك في الكثير من الكتب و مراجع الانترنت، وكنت قد بالفعل نرى أنه على الجانب الآخر. ولكن مجرد أن ندرك أن كلا سوف الواقع العمل ويجب أن تكون ببساطة متسقة. 

حسنا. لذلك كان هذا الإعلان لدينا من عقدة البنية. ولكن بعد ذلك بدأنا بذل المزيد من الجهد الأمور تعقيدا. على سبيل المثال، قررنا أن نقدم شيء من هذا القبيل جدول تجزئة. حتى هنا هو جدول التجزئة من حجم ن، فهرسة من 0 في أعلى يسار إلى n ناقص 1 في أسفل اليسار. هذا يمكن أن يكون تجزئة الجدول من أجل أي شيء. ولكن ما هي أنواع الأشياء لم نتحدث حول استخدام جدول تجزئة ل؟ تخزين ما؟ 

أسماء. يمكننا القيام به أسماء مثل فعلنا في المرة السابقة. وحقا، يمكنك تخزين أي شيء. وسنرى هذا مرة أخرى في PHP وجافا سكريبت. جدول التجزئة هو نوع جميل من السويسري سكين الجيش الذي يسمح لك لتخزين الى حد كبير كل ما تريد داخل ذلك من خلال ربط مفاتيح مع القيم. مفاتيح مع القيم. 

الآن في هذه الحالة بسيطة، لدينا المفاتيح هي مجرد أرقام. نحن تنفيذ تجزئة الجدول كما صفيف. وبالتالي فإن المفاتيح هي 0، 1، 2، وهكذا دواليك. ولذا فإننا، كما قرر البشر، آخر الأسبوع أن تعرف ما، إذا نحن الذهاب لتخزين أسماء، دعونا فقط تعسفي، ولكن بشكل معقول جدا، نفترض أن أليس، وهو اسم A، وسوف يكون مجرد فهرستها في 0. وبوب، وهو اسم B، سيتم فهرستها في 1، وهكذا دواليك. لذلك كان علينا تعيين بين المدخلات، والتي هي سلاسل، والتجزئة المواقع، التي هي الأرقام. 

لذلك هو أن العملية المعروفة عموما وظيفة تجزئة، ويمكنك حقا تنفيذه في التعليمات البرمجية. إذا أردت أن تنفذ وظيفة تجزئة أن يفعل بالضبط ما كنا وصفه للتو من آخر مرة، وأنا قد تعلن دالة التي تأخذ، و المدخلات على سبيل المثال - ودعونا نفعل ذلك على هذا فحص أكثر من هنا. إذا أردت أن تنفيذ تجزئة وظيفة، وأنا قد يقول شيء من هذا القبيل. 

انها سوف بإرجاع عدد صحيح. انها تسير ليتم استدعاؤها تجزئة، وانها الذهاب لقبول كحجة ل سلسلة، أو أننا يمكن أن يكون أكثر مناسبة الآن، ويقول شار *، ونحن سوف يطلق عليه ق. وبعد ذلك كل هذه الوظيفة لا علاقة له، في نهاية المطاف، هو العودة إلى كثافة العمليات. الآن، وكيف يفعل ذلك القوة لا تكون واضحة جدا. أنا ذاهب لتنفيذ ذلك دون أي شكل خطأ التحقق الآن. أنا فقط أريد أن أقول عمياء، وعودة كل ما هو في قوس ق 0، ناقص، دعنا نقول، عاصمة فاصلة منقوطة. 

كسر تماما. انها ليست مثالية ل واحد، ما إذا ق باطل؟ أشياء سيئة ستحدث. اثنين، ما إذا كان الحرف الأول في هذا اسم ليس حرف؟ التي لن تتحول إما بشكل جيد. قد يكون الحرف الصغير أو ليس إلكتروني على الإطلاق. حتى غرفة تماما للتحسين هنا، ولكن هذه هي الفكرة الأساسية. 

ما وصفنا الأسبوع الماضي، حيث لفظيا مجرد عملية رسم الخرائط أليس ل يمكن التعبير 0 وبوب ان 1 بالتأكيد أكثر formulaically باعتبارها C تعمل هنا. ودعا مرة أخرى التجزئة، كما تأخذ سلسلة المدخلات، ثم على نحو ما يفعل شيئا مع أن المدخلات لإنتاج المخرجات. لا يختلف لدينا وصف الصندوق الأسود أننا قد فعلت طويلة. أنا لا أعرف كيف يمكن أن يكون هذا تعمل تحت غطاء محرك السيارة. 

لمشكلة تعيين 6، واحدة من التحديات هو بالنسبة لك لتقرر ما وسوف تكون دالة البعثرة الخاصة بك؟ ما يحدث أن تكون داخل تلك الأسود مربع، ويفترض، وأنها سوف تكون قليلا أكثر إثارة للاهتمام من هذا، و بالتأكيد أكثر عرضة للخطأ التحقق من ذلك خاصة التنفيذ. 

لكن المشاكل يمكن أن تنشأ، أليس كذلك؟ اذا كان لدينا بنية بيانات مثل هذا واحد، ما هو واحدة من المشاكل يمكنك تشغيل في أكثر من مرة عند إدراج أسماء أكثر وأكثر في تجزئة الجدول؟ تحصل التصادمات، أليس كذلك؟ ماذا لو كان لديك أليس وهارون، اثنين من الناس الذين حصل أسماء لتبدأ مع و؟ أن يطرح السؤال، أين أنت وضع الثاني من نوعه اسم؟ 

كذلك، قد بسذاجة وضعه فقط حيث ينتمي بوب، ولكن بعد ذلك بوب نوع من ثمل إذا حاولت إدراج اسمه المقبل و ليس هناك مجال للله. لذلك كنت قد وضعت بوب حيث تشارلي هو، ويمكنك أن تتخيل هذا بسرعة جدا تسند إلى قليلا من الفوضى. شيء خطي في نهاية المطاف، حيث كنت لديك فقط للبحث في كل شيء يبحث عن أليس أو بوب أو هارون أو تشارلي. 

وذلك بدلا اقترحنا، بدلا من مجرد التحقيق خطيا عن المساحات المفتوحة والسقوط أسماء هناك، ونحن اقترح نهجا مربي الحيوانات. جدول تجزئة تنفيذها لا يزال مع مجموعة من المؤشرات، ولكن نوع بيانات كانت تلك المؤشرات المؤشرات الآن. مؤشرات لماذا؟ مؤشرات إلى القوائم المرتبطة. 

لأن نذكر أن قائمة مرتبطة هو في الحقيقة مجرد مؤشر إلى عقدة، و عقدة لديه الحقل التالي، وتلك العقدة لديه الحقل التالي، وهكذا دواليك. بحيث يمكنك الآن التفكير في هذه المجموعة على الجانب الأيسر من جدول تجزئة كما مما أدى إلى قائمة مرتبطة. ميزة وهي إذا كنت تحصل على تصادم بين أليس وهارون، ماذا تفعل مع هذا الشخص الثاني؟ كنت مجرد نعلق له أو لها ل نهاية، أو حتى بداية من تلك القائمة المرتبطة. 

وفعلا، دعونا فقط من خلال المعكرونة أن لثانية واحدة. حيث من شأنه أن يجعل معظم معانيها؟ إذا كنت إدراج أليس وقالت انها ينتهي في الموقع الأول، ثم أحاول أن إدراج اسم هارون، وهناك من الواضح أن الاصطدام، يجب أن أضع له في بداية من قائمة مرتبطة؟ هذا هو الموقع الأول في ذلك، أو في نهاية المطاف؟ 

الحضور: [غير مسموع]. 

DAVID مالان: OK. سمعت تبدأ. لماذا في البداية؟ 

الحضور: [غير مسموع]. 

DAVID مالان: OK. انها الأبجدي، بحيث لطيف. هذا هو خاصية جيدة. سيوفر لي بعض الوقت يحتمل. انها لن تسمح لي أن تفعل البحث الثنائي، ولكن أنا قد تكون قادرة على الخروج على الأقل من حلقة إذا أدرك، جيدا، أنا الطريق وكانت في الماضي من شأنه أن يكون هارون في هذا فرز قائمة مرتبطة. أنا لا لديك لإضاعة وقتي أبحث على طول الطريق حتى النهاية. بحيث المعقول. وإلا لماذا قد ترغب في إدراج اسم اصطدامه في ابتداء من القائمة؟ ما هذا؟ 

الحضور: [غير مسموع]. 

DAVID مالان: إنه يمكن أن يستغرق وقتا طويلا للوصول الى نهاية القائمة. في واقع الأمر، أطول وأطول. أكثر الأسماء التي تضاف التي تبدأ مع A، ويعد ذلك سلسلة هو الذهاب الى الحصول عليها. ويعد أن ترتبط قائمة هو الذهاب الى الحصول عليها. لذلك كنت حقا فقط تهدر وقتك. ربما كنت أفضل حالا المحافظة ثابت وقت الإدراج، يا كبير من 1، بواسطة دائما وضع اسم اصطدامه في بداية القائمة المرتبطة، وليس القلق بقدر حول فرز. 

ما هو أفضل إجابة؟ انها غير واضحة. انها نوع من يعتمد على ما التوزيع هو، ما هو نمط من الأسماء التي يتم إدخالها. انها ليست بالضرورة والجواب واضح. ولكن هنا ل، مرة أخرى، هو فرصة التصميم. 

لذلك نحن ثم نظرت إلى هذا الشيء، الذي هو حقا آخر فرصة كبيرة لمدة 6 تعيين ص. وندرك، إذا كنت لم تقم بذلك بالفعل، Zamyla الغطس في كل من هذه، تجزئة الجداول ويحاول، في مزيد من التفاصيل. وتجول الفيديو جزءا لا يتجزأ في مجموعة ع المواصفات. كان هذا TRIE - T-R-I-E. وما كان مثيرا للاهتمام حول هذا كان أن الوقت تشغيل من البحث عن اسم، مثل ماكسويل آخر مرة، كان يا كبير من ماذا؟ ما هذا؟ 

الحضور: عدد من الرسائل. 

DAVID مالان: عدد من الرسائل. سمعت أمرين. عدد من الرسائل ووقت ثابت. لذلك دعونا نذهب مع هذا أولا. عدد الرسائل. حسنا، هذا بنية البيانات، أذكر، هو مثل شجرة، شجرة العائلة، كل من يتم إجراء العقد التي تتكون من المصفوفات. وتلك هي مؤشرات إلى صفائف العقد مثل غيرها، أو غيرها من مثل هذه صفائف في الشجرة. 

لذلك إذا أردنا أن تحديد ثم سواء في ماكسويل هو هنا، وأنا قد يذهب لمجموعة الأولى، في أعلى جدا من الشجرة، ما يسمى الجذر، أعلى وTRIE، ثم اتبع المؤشر متر، ثم مؤشر، ثم س، ث، ه، ل، ل. وبعد ذلك عندما أرى بعض رمز خاص، يشار هنا كما مثلث. في التعليمات البرمجية سترى نقترح أن لك تنفيذها باعتبارها منطقي، فقط أقول نعم أو لا، كلمة يتوقف هنا. 

حسنا، مرة واحدة لقد ذهب إلى M-A-X-W-E-L-L، يشعر وكأنه سبع، وربما ثمانية إذا ذهبنا واحدة الماضي، وثمانية الخطوات التالية للعثور ماكسويل. أو دعنا نسميها K. لكن أذكر مشاركة الوقت، وجادلت بأن إذا كان هناك واقعيا كحد أقصى على طول كلمة واحدة، مثل 40 بعض الأحرف ونيف، و يعني الحد الأقصى للطول قيمة ثابتة. لذلك حقا، نعم، انها يا كبير تقنيا من 8 أو 7، أو يا كبير حقا ولكن K. إذا كان هناك سقف محدد على ما K يمكن أن يكون، انها ثابتة. ولذا فمن يا كبير من 1 في في نهاية اليوم. 

ليس في العالم الحقيقي. لا عند بدء فعلا مشاهدة كما مدار الساعة لديك تشغيل البرنامج الخاص بك. انها تسير على الاطلاق ليكون قليلا أبطأ من ثابت حقا الوقت مع خطوة واحدة. انها سوف تكون سبع أو ثماني خطوات، ولكن لا يزال هذا هو أفضل بكثير من خوارزمية مثل O كبيرة من ن أن يعتمد على حجم ما هو في هيكل البيانات. 

لاحظ الارتفاع هنا هو أننا يمكن إدراج مليون من الأسماء في هذه هيكل البيانات، ولكن كم من خطوات أكثر هل هو ذاهب الى اتخاذ علينا أن نجد ماكسويل في هذه الحالة؟ لا شيء. انه غير متأثر. وحتى الآن، وأنا لا أعتقد أننا قد رأيت مثال على بنية بيانات أو الخوارزمية التي كان تماما تتأثر الخارجية سلوكيات من هذا القبيل. ولكن هذا لا يمكن أن تكون مذهلة. هذا لا يمكن أن يكون الحل الوحيد لف مجموعة 

وانها ليست. هذا ليس بالضرورة البيانات هيكل يجب أن تنجذب إلى، لأن الجداول التجزئة مثل، المقايضة. ما هو الثمن الذي تدفعه هنا؟ الذاكرة. أعني، هذا هو فظيعة مقدار الذاكرة. وأنت لا يمكن أن نرى تماما هنا ل صاحب هذا الصورة من الواضح اقتطاع كل من المصفوفات، ونحن لا نرى الكثير من A و وباء وجيم وللفي س والخاص ص وZ في هذه المصفوفات. لكنهم هناك. 

كل من هذه العقد هو مجموعة كاملة من نحو 26 بايت أو أكثر، كل من الذي يمثل بريد إلكتروني. 27 في حالتنا، حتى نتمكن من دعم تعيين الفواصل العليا في المشكلة. لذلك هذا هو حقا بنية البيانات، حقا كثيفة واسعة. والتي قد تنتهي وحدها يصل تباطؤ الأمور، أو على الأقل تكلفك أكثر الكثير الفضاء. ولكن مرة أخرى، يمكننا استخلاص المقارنات هنا. 

أذكر حين يعود، ونحن تحقق الكثير أكثر إثارة إدارة الوقت في الفرز عندما نستخدم دمج النوع، ولكن الثمن دفعنا لتحقيق ن ن سجل للدمج مطلوب النوع الذي ننفق أكثر ما الموارد؟ مساحة أكبر. نحن بحاجة إلى مجموعة والثانوية نسخ الناس إلى، تماما مثل فعلنا هنا على خشبة المسرح. ذلك مرة أخرى، لا الفائزين واضحة، ولكن التصميم شخصي فقط قرارات في هذا الشأن. 

حسنا. فكيف هذا؟ أي شخص الذي تعترف D-القاعة؟ موافق. لذلك ثلاثة منا القيام به. ماثر البيت. لذلك هذا هو لتناول الطعام في ماذر. أراهن كل قاعات الطعام ديك أكوام من الصواني من هذا القبيل. وهذا هو في الواقع ممثل شيء قمنا ومن الواضح أن رأينا بالفعل. نحن يطلق عليه حرفيا كومة. والمكدس، من حيث الخاصة بك ذاكرة الكمبيوتر، حيث يذهب البيانات بينما يجري دعا الوظائف. 

على سبيل المثال، ما هي أنواع الأشياء تذهب على المكدس فيما يتعلق تخطيط الذاكرة ناقشناه في الأسابيع الماضية؟ ما هذا؟ 

الجمهور: يدعو إلى وظائف. 

DAVID مالان: أنا آسف. 

الجمهور: يدعو إلى وظائف. 

DAVID مالان: يدعو إلى وظائف، ولكن على وجه التحديد، ما هو داخل كل من تلك الأطر؟ ما أنواع الأشياء؟ نعم. المتغيرات المحلية بذلك. في أي وقت نحن في حاجة الى بعض التخزين المحلية، مثل حجة، أو الباحث الأول، أو الباحث درجة الحرارة، أو أيا كانت محلية المتغير هو، كنا وضع هذا على المكدس. ونحن نسميها كومة ل من هذه الفكرة طبقات. مجرد نوع من المباريات مع الواقع، مفهوم منه. 

ولكن اتضح أن كومة يمكن أيضا أن ينظر إليه باعتباره بنية البيانات، و بديل للصفيف، بديل إلى قائمة مرتبطة. شيء أكثر إثارة للاهتمام من الناحية المفاهيمية التي يمكن أن تكون لا تزال نفذت باستخدام أي من تلك الأشياء، ولكن من نوع مختلف من هيكل البيانات الداعمة، حقا، اثنين فقط من العمليات. ولكن يمكنك إضافة على مربي الحيوانات ملامح من هذه. ولكن هذه هي الأساسيات - دفع والبوب. 

وهذه الفكرة مع كومة هو أنه إذا كنت دينا هنا، مع أو بدون أننبرغ مع العلم، علبة من البيت المجاور مع الرقم 9 على ذلك. حتى مجرد كثافة العمليات. وأريد أن دفع هذا على البيانات هيكل، الذي هو حاليا فارغ. النظر في هذا الجزء السفلي من المكدس. وأود أن دفع هذا الرقم 9 على كومة، والآن حان الحق هناك. 

لكن الشيء المثير للاهتمام حول كومة غير أنه إذا أريد الآن لدفع بعض قيمة أخرى، مثل 17، وأدفع هذا إلى المكدس، وانا ذاهب للقيام الشيء بديهية فقط، سأقوم لوضعها الصحيح حيث نحن البشر سوف تميل إلى وضعه، على القمة. ولكن ما هو مثير للاهتمام الآن هو، كيف يمكنني الحصول على 9؟ كما تعلمون، أنا لا تخلو من بعض الجهد. 

فما مثيرة للاهتمام حول كومة هو أن حسب التصميم، انها بنية بيانات LIFO. طريقة سخيفة لوصف آخر في، أولا خارج. حتى آخر رقم في وكان في هذا الوقت 17. لذلك إذا أريد لموسيقى البوب ​​شيء خارج من المكدس، يمكن أن يكون فقط 17. لذلك هناك أمر إلزامي لل عمليات هنا، حيث العنصر الأخير في أن تكون أول من أصل واحد. وبالتالي اختصار، LIFO. 

فلماذا هذا قد يكون مفيدا؟ وسياقاتها التي كنت نريد بنية بيانات من هذا القبيل؟ حسنا، انها كانت بالتأكيد مفيدة داخل جهاز الكمبيوتر. أنظمة التشغيل وذلك باستخدام هذا بوضوح نوع من بنية بيانات للمداخن. سوف نرى أيضا نفس الفكرة عندما يتعلق الأمر إلى صفحات الويب. لذلك هذا الاسبوع والاسبوع القادم وما بعده، وعندما تبدأ تنفيذ شبكة الإنترنت صفحات بلغة HTML دعا، يمكنك فعلا استخدام بنية بيانات مثل هذا لتحديد ما إذا كانت الصفحة يتم تنسيق بشكل صحيح. لأننا سنرى كل صفحات الويب متابعة نوع من التسلسل الهرمي، والمسافة البادئة هذه الإرادة، في نهاية المطاف، أن يكون هيكل شجرة تحت غطاء محرك السيارة. أكثر من ذلك على أنه في قليلا فقط. 

لكنه الآن، دعونا اقتراح ل لحظة، كيف يمكن أن تذهب نحو تمثل ما هو كومة؟ اسمحوا لي أن أقترح أن ننفذ كومة مع رمز مثل هذا. حتى كومة ستكون لدينا داخل منه أمرين، صفيف، دعا الصواني، لمجرد أن يكون متسقا مع العرض. ولكل من العناصر في هذا الصفيف سوف يكون نوع int. والقدرة هي ما يفترض؟ لأنني لم يكتب ل التعريف الكامل هنا. 

انها على الارجح الأقصى حجم المصفوفة. وانها على الارجح كما أعلن حاد تعريف في الجزء العلوي من الملف، بعض نوع من ثابتة كما تنطوي عليها مجرد الرسملة. في مكان ما بحيث يتم تعريف القدرة كحد أقصى حجم ممكن. وفي الوقت نفسه، داخل بنية البيانات المعروفة باسم كومة سيكون هناك ان يكون عدد صحيح يعرف فقط ببساطة الحجم. 

حتى لو كنت لتمثيل هذا الآن بالصور، دعونا نفترض أن هذا يمثل الصندوق الاسود كله بلدي المكدس. داخل منه هو متغيرين. لذلك أنا ذاهب لرسم أول واحد كما الحجم. والثانية انا ذاهب كما رسم صفيف. 

ولكن فقط لابقاء الامور منظم، عادة أود أن ألفت مجموعة مثل هذا، ولكن هذا النوع من طيف إذا كنا تطابق الواقع، أو تطابق نموذج العقلية. لذلك اسمحوا لي بدلا رسم مجموعة عموديا، الذي هو مجرد، مرة أخرى، التسليم الفنان. لا يهم ما هو حقا هو تحت غطاء محرك السيارة. وسوف نقول ذلك، افتراضيا، القدرة ستكون الثلاثة. لذلك سيكون هذا المكان 0، وهذا سيكون المكان 1، وهذا سيكون المكان 2. 

إذا كنت رشوة مع الكرة الإجهاد، وسوف شخص ترغب في الخروج وتشغيل متن هنا لمجرد لحظة؟ موافق، ورأى يدك أولا. تأتي على ما يصل. حسنا. لذلك أعتقد أنه من ستيفن. تأتي على ما يصل. حسنا. 

ولكن لنفترض الآن أننا الترجيع على التقارير الأولية دولة من العالم حيث أنا وقد أعلنت مجرد كومة، وانها ستكون القدرة الثلاث. ولكن لم يتم بعد تحديد حجم. ولم يتم بعد تحديد الصواني. حتى بضعة أسئلة الأولى. واسمحوا لي أن أقدم لكم هيئة التصنيع العسكري حتى تتمكن من يشاركون بنشاط أكبر في هذا المجال. 

فما هو حجم داخل في هذه اللحظة في الوقت إذا كل ما قاموا به هو أعلن كومة مع سطر واحد من التعليمات البرمجية؟ 

ستيفن: ليس كثيرا. 

DAVID مالان: OK، وليس ذلك بكثير. لا نعرف ما هو داخل الحجم، لا نعرف ما هو داخل من هذه المجموعة هنا؟ 

ستيفن: كود عشوائي فقط، أليس كذلك؟ فقط - 

DAVID مالان: نعم، أنا ذاهب ل يطلق عليه رمز، ولكن العشوائية - 

ستيفن: الأشياء. 

DAVID مالان: أشياء مثل عشوائي 

ستيفن: القطع. 

DAVID مالان: القطع، أليس كذلك؟ حتى القيم القمامة، أليس كذلك؟ لذلك من التباديل و0 1 في. بقايا من الأعراف السابقة من هذه الذاكرة. ونحن لا نعرف حقا ما القيم هي، لذلك نحن عادة رسم لهم كما علامات استفهام. 

وبالتالي فإن أول شيء نحن يفترض تريد الذهاب الى القيام به هنا - واسمحوا لي أن أقدم هذا المجال داخل من هناك اسم - الصواني. ما يجب علينا تهيئة يفترض الحجم إلى إذا كنا نريد أن البدء في استخدام هذا المكدس؟ 

ستيفن: صينية هو دون 3. 

DAVID مالان: إذن، حسنا. أن تكون واضحة، وأعلن القدرات في أماكن أخرى الثلاثة. وهذا ما كنت قد استخدمت لتخصيص مجموعة. حجم هو ذاهب للإشارة إلى كيفية العديد من صواني حاليا على المكدس. 

ستيفن: صفر. 

DAVID مالان: لذلك ينبغي أن يكون صفرا. لذلك يذهب إلى الأمام، ومع أي إصبع، رسم الصفر في الحجم. حسنا. وحتى الآن، ما هو داخل هذا هنا، ونحن لا نعرف. هذه هي حقا القيم القمامة فقط. حتى نتمكن من رسم علامات استفهام، ولكن دعونا نحافظ على لوحة نظيفة في الوقت الراهن لأنه لا يهم ما هو هناك. نحن لسنا بحاجة إلى تهيئة مجموعة إلى أي شيء، لأنه إذا علمنا أن حجم المكدس هو صفر، حسنا، نحن لا ينبغي أن تبحث في أي شيء في على أي حال في هذه المجموعة هذه النقطة في الوقت المناسب. 

لذلك لنفترض الآن أنني دفع عدد 9 إلى المكدس. كيف يجب أن نقوم بتحديث بنية البيانات داخل هذا الصندوق الأسود؟ ما هي القيم بحاجة إلى تغيير؟ 

ستيفن: ضمن - حجم؟ 

DAVID مالان: OK. وينبغي أن يصبح حجم ما؟ 

ستيفن: أن الحجم يكون واحدا. 

DAVID مالان: OK. لذلك ينبغي أن يصبح حجم واحد. حتى تتمكن من القيام بذلك في طرق زوجين. اسمحوا لي أن أقدم لكم، الآن لديك الإصبع هو ممحاة. حسنا. ثم الآن إصبعك هو فرشاة. حسنا. والآن ماذا يجب أن يتغير، من الواضح، في بنية البيانات؟ 

ستيفن: ونحن في طريقنا من أسفل إلى أعلى إلى 9. 

DAVID مالان: 9. حسنا، جيد. لذلك لا يزال لا يهم ما هو على موقع واحد أو اثنين لأنهم القيم القمامة، ولكن لا ينبغي لنا أن يكلف نفسه عناء أبحث هناك لأن حجم يقولون لنا أن العنصر الأول فقط هو في الواقع شرعية. وحتى الآن أدفع 17 على القائمة. ما يحدث لهذه الصورة؟ 

ستيفن: حجم لذا ستذهب إلى اثنين. 

DAVID مالان: OK. كنت ممحاة - عفوا. كنت ممحاة. 

ستيفن: ممحاة. 

DAVID مالان: أنت فرشاة. 

ستيفن: فرشاة. 

DAVID مالان: OK. وماذا بعد؟ 

ستيفن: وبعد ذلك - 

DAVID مالان: نحن دفعت 17. 

ستيفن: نحن نتمسك 17 على القمة، وذلك - 

DAVID مالان: موافق، وحسن. 

ستيفن: - أسقطه أسفل. 

DAVID مالان: حسنا. الأمر يزداد سهولة. أنا لا أذهب لمساعدتك هذه المرة. دفع 22. 

ستيفن: تم. أصبحت ممحاة. أنا أصبحت فرشاة. ثم أنا أضع 22. 

DAVID مالان: 22. ممتازة. حتى واحد مزيد من الوقت. أنا الآن ذاهب لدفع إلى المكدس 26. 

ستيفن: أوه. يا إلهي. كنت حقا اشتعلت لي على حين غرة. 

DAVID مالان: أنت لم انظر هذا المقبلة؟ 

ستيفن: لم أكن أرى هذا المقبلة. يمكن أن نعيد الأولية القدرات؟ 

DAVID مالان: هذا سؤال جيد. لذلك قمنا نوع من رسمت أنفسنا في زاوية هنا. هناك حقا ليس جيدا للخروج لستيفن لأننا قد خصصت هذه المجموعة بشكل ثابت، إذا جاز التعبير، في الداخل من بنية البيانات. وقمنا في الأساس الثابت ترميز أن يكون من حجم الثلاثة. لذلك لا يمكننا تخصيص ذلك حقا. 

يمكننا أن إذا عدنا في، ونحن صواني إعادة تعريف ليكون المؤشر الذي نحن بعد ذلك استخدام malloc للذاكرة لناحية. لأنه إذا حصلنا على الذاكرة من كومة عبر malloc، ونحن ويمكن بعد تحريرها. ولكن قبل تخليصه، ونحن يمكن أن إعادة تخصيص قسما أكبر من الذاكرة، تحديث المؤشر، وهكذا دواليك. لكنه الآن، وهذا هو حقا أفضل ما يمكن القيام به. دفعة والبوب ​​تسير يفترض أن يكون للإشارة إلى بعض الخطأ. 

هكذا على سبيل المثال، تنفيذنا من دفع يمكن إرجاع منطقي التي عاد سبق صحيح، صحيح، صحيح. ولكن في المرة الرابعة، وانه ستكون لدينا للعودة كاذبة، على سبيل المثال. حسنا. جيد جدا. التهاني. كنت قد كسبت الكرة الإجهاد اليوم. 

[تصفيق] 

ستيفن: شكرا لك. 

DAVID مالان: شكرا لك. حسنا، يبدو أن هذا ليس كثيرا من خطوة إلى الأمام، أليس كذلك؟ وصفنا هذه البنية البيانات. انها كانت مقنعة، أليس كذلك؟ أنظمة التشغيل مثل ذلك. يبدو أن شبكة الإنترنت يمكن الاستفادة من هذا، وغيرها من التطبيقات لا يزال. ولكن ما هو الحد من الغباء أننا العودة إلى نوع من أسبوعين حدود حيث قمنا الثابتة صفائف الحجم. 

لذلك هناك بالفعل اثنين من طرق نتمكن من حل هذا. يمكننا أن تخصيص حيوي مجموعة، ليس من الصعب الترميز أنها عندي القيام به هنا، ولكن بدلا من ذلك إعادة معلنا- هذا، لمجرد أن يكون واضحا، و شيء من هذا القبيل. * الباحث الصواني، وليس اتخاذ قرار على قدرة حتى الآن. ولكن عندما أعلن مكدس في مكان آخر في قانون بلدي، وأنا يمكن أن ثم استدعاء malloc، الحصول على عنوان قطعة من الذاكرة، وأنا لا يمكن تعيين هذا العنوان إلى الصواني. 

وبعد ذلك، لأنه مجرد قطعة من الذاكرة، وأنا يمكن أن تستمر في استخدام مربع التدوين قوس بالطريقة المعتادة. لأن مرة أخرى، وهناك نوع من هذا المعادل الوظيفي من المصفوفات و قطع من الذاكرة التي تأتي العودة من malloc. يمكننا علاج واحدة عن الأخرى باستخدام مؤشر الحسابية أو مربع التدوين قوس. ذلك أن نهج واحد. 

ولكن كيف يمكن أن ننفذ آخر هذا هيكل البيانات نفسه، يحتمل أن تكون؟ أليس كذلك؟ أشعر أننا مجرد حل هذه مشكلة مثل قبل اسبوع. ما هو الحل لهذه المشكلة أن ستيفن واجهت؟ قوائم ذلك مرتبط، الحق. 

إذا كانت المشكلة هي أننا اللوحة أنفسنا في مأزق من خلال تخصيص مقدما الذاكرة قليلا جدا أننا ثم تضطر إلى التعامل بطريقة أو بأخرى مع، حسنا، لماذا لا تجنب مجرد أن إصدار تماما؟ لماذا لا تعلن فقط الصواني أن يكون مؤشر إلى عقدة، إرجو قائمة مرتبطة، ثم ببساطة تخصيص العقد الجديد في كل مرة ستيفن اللازمة لتناسب رقم في بنية البيانات. 

وبالتالي فإن الصورة سوف تضطر إلى تغيير. انها لن تكون نظيفة وكما بهذه البساطة مجرد مجموعة من ثلاث رجات. الآن انها ستكون مؤشر إلى البنية، والبنية التي هو ذاهب ل لديها كثافة ومؤشر المقبل. انها سوف تؤدي من خلال هذا المؤشر لمثل هذه البنية آخر ل هذه البنية آخر. لذلك فإن الصورة في الواقع الحصول على أكثر فوضى قليلا. وسيكون لدينا السهام ربط كل شيء معا. 

ولكن هذا شيء طيب، والحق، لأن شاهدنا كيفية القيام بذلك. وبمجرد الحصول على راحة تنفيذ شيء من هذا القبيل مرتبط القائمة، والتي سيكون لديك لتفعل لو كنت اختيار لتنفيذ جدول تجزئة مع تسلسل منفصلة لمدة 6 تعيين ع، يمكنك استخدامه بمثابة لبنة في بناء، أو العنصر، أو خدش في الكلام، و الإجراء، وهو الأمر الذي كنت وضعت، ل خلق قطعة اللغز الخاصة بك التي يمكنك ثم إعادة استخدامها. لذلك المفاضلات، ولكن الحلول الممكنة التي شهدناها في الواقع من قبل. 

لذلك في كثير من الأحيان، ترى هذا كل سنة أو سنتين عندما تطلق أبل شيء جديد، وجميع الناس مجنون يصطف خارج أبل تخزين لشراء الهامشية ترقية على الأجهزة. أقول هذا، لا بأس، ل أنا واحد من هؤلاء الناس. حتى أي نوع من هياكل البيانات قد يمثل هذا الواقع؟ 

حسنا، دعنا نسميها قائمة الانتظار، وهو خط. بحيث البريطانية أن نسميها عادة يصطف على أي حال، لذلك هو اسم لطيف. والعمليتين التي طابور يجب دعم سنقوم استدعاء إدراج بقائمة الانتظار عملية وعملية dequeue، والتي تتشابه في روح لدفع والبوب. انها مجرد نوع من مختلف في الاتفاقية، ما نقوم استدعاء هذه. ولكن لإدراج بقائمة الانتظار يعني شيئا لإضافة أو أدخله إلى بنية البيانات. لdequeue سيلة لإزالته. ولكن في حين كان كومة بيانات LIFO هيكل، طابور هو في الأولى، أول من بنية البيانات. 

إذا كنت أول شخص في الخط، سوف تكون أول شخص للحصول على من خط وشراء الجهاز الجديد. تخيل كيف بالضيق هؤلاء الناس سيكون إذا أبل بدلا استخدام المكدس، ل المثال، لتنفيذ قطف حتى من لعبة الجديد الخاص بك. حتى طوابير معنى له، بالتأكيد، و يمكن أن نفكر في كل أنواع التطبيقات، ويفترض، على قوائم الانتظار، وخصوصا عندما كنت تريد الإنصاف. فكيف يمكن لنا تنفيذ هذه كما بنية بيانات؟ 

حسنا، أنا أقترح أننا قد تحتاج إلى أن تفعل ذلك بهذه الطريقة. لذلك أنا ذاهب لدينا الآن الأرقام. ولذا فإننا سوف يبقيه بسيط وليس نتحدث بالضرورة من حيث الصواني. فقط الأرقام التي حصلت من الناس. القدرة هو الذهاب الى، مرة أخرى، وتحديد العدد الإجمالي للأشخاص التي يمكن أن تكون في هذا الخط، وثلاثة أو أي قيمة أخرى. 

ولكن أقترح أن أنا بحاجة للحفاظ على المسار ليس فقط من حجم قائمة الانتظار، وكم الأمور في ذلك. لذلك الحجم هو حجم الحالي، والقدرة هو الحد الأقصى لحجم. فقط مرة أخرى، التسميات قبل الاتفاقية. لماذا أحتاج إلى كثافة إضافية داخل من طابور لتتبع من هو في أمام السطر؟ لماذا يجب أن أفعل في هذه الحالة؟ 

حسنا، كيف هو هذه الصورة سيتغير؟ أنا ربما يمكن إعادة استخدامها أكثر من هذه الصورة. اسمحوا لي أن تمضي قدما ومحو ما هو هنا. وسوف نقدم هذا قليلا اسم مختلف هنا. دعونا نتخلص من 17، دعونا نتخلص من 9، دعونا نتخلص من 3. ودعونا نضيف شيئا واحدا الأخرى. أقترح أن أحتاج لتتبع الجزء الأمامي من القائمة، والذي هو مجرد ستكون عدد صحيح كذلك. ونحن في طريقنا ليبقيه بسيط. لا توجد قائمة مرتبطة في الوقت الراهن. 

سنقوم نعترف بأننا في طريقنا لل يرفعه ضد هذا الحد. ولكن ماذا أريد أن أرى يحدث هذه المرة؟ لذلك افترض المضي قدما وأول شخص يأتي في الخط، و انها رقم 9. لدينا كرات الإجهاد. يمكنني سرقة، مثلا، اثنين أو ثلاثة أشخاص؟ واحد، اثنان، ثلاثة؟ تأتي على ما يصل. الحق من الجبهة، لأن سنقوم جعل هذه واحدة سريعة. 

كل واحد منكم الآن ستكون صبي مروحة في خط أبل. فلن يتم تلقي أجهزة أبل في نهاية هذا على الرغم من. حسنا. لذلك كنت رقم 9، وكنت عدد 17، عدد 22. هذه هي أرقام اعتباطية، مثل معرفات طالب أو غيرها. وفي لحظة فقط، دعونا نبدأ لبدء إضافة أشياء. وسوف تشغيل متن هنا هذه المرة. 

حتى في هذه الحالة، لقد تهيئة الجبهة أن تكون - أنا في الواقع لا يهمني حقا ما الجبهة هو، لأن حجم صفر. ولذلك فإن هذا قد كذلك فقط تكون علامة استفهام. هذه كلها علامات استفهام. لذلك نحن الآن سوف نبدأ في رؤية الواقع بعض الناس يصطفون في المتجر. 

حتى إذا كان رقم 9، وكنت أول واحد هناك في الساعة 5 صباحا، والمضي قدما وأصطف، أو في الليلة السابقة. موافق. وحتى الآن 9 هنا. حتى 9 هو في الجزء الأمامي من القائمة. لذلك انا ذاهب الى المضي قدما وتحديث حجم هذه البيانات الحالية بنية أن لا يكون 0 بعد الآن، ولكن أن تكون 1. انا ذاهب الى وضع 9 في أمام القائمة. اسمحوا لي أن تمضي قدما وتبديل الشاشة حتى يمكننا أن نرى الماضي لنا هنا. 

والآن ماذا أريد لوضع في الجبهة؟ انا ذاهب للحفاظ على المسار الذي و مقدمة قائمة الانتظار الآن هو في موقع 0. لأن ما يجري بجانب يحدث؟ حسنا، لنفترض الآن أنا إدراج بقائمة الانتظار 17 كذلك. حتى قفز في خط هناك. ومرة أخرى، هذا النوع من الباب إلى مخزن ستكون هنا. حتى الآن لقد أضاف 17. وعلى الرغم من أن هؤلاء الرجال يتم حظر الشاشة، وهذا موافق، لأننا يمكن أن نرى ذلك هنا. آسف. 

الحضور: نحن يمكن ان تتحرك - 

DAVID مالان: لا، وهذا موافق. انها ضخمة هناك. حتى الآن 17 داخل قائمة الانتظار. ولست بحاجة للتحديث الذي الحقول الآن على الرغم من؟ موافق، حجم بالتأكيد. وماذا عن الجبهة؟ حسنا، لا. لا ينبغي أن يغير الجبهة، لأن على عكس كومة، ونحن يريدون الحفاظ على الإنصاف. حتى إذا جاء في أول 9، ونحن نريد 9 ليكون من أول السطر وإلى المتجر. 

في الواقع، دعونا نرى ذلك. قبل أن إدراج 22، دعنا المضي قدما وdequeue 9. ما اسمك مرة أخرى؟ 

الجمهور: جيك. 

DAVID مالان: جيك يجري أن dequeued الآن. حتى تحصل على السير في المخزن. وأدعي أن المخزن هو هناك. وحتى الآن ما يحتاج - ديت ديت--ديت! ما يجب أن يحدث الآن؟ قرار التصميم. حتى لا غريزة سيئة، ولكن - ما اسمك مرة أخرى؟ 

الجمهور: ديفيد. 

DAVID مالان: ديفيد. وذلك ما لم ديفيد تفعل؟ كان يحاول إصلاح نوع من البيانات هيكل والانتقال من مكان وجوده في مكان وجيك السابق. وهذا شيء طيب إذا كنا على استعداد لقبول ذلك باعتباره التفاصيل التنفيذ. ولكن أولا، دعونا تحديث البيانات هيكل قبل ان نفعل ذلك. لأنني لا تروق فكرة عن الشعب تحول في هذا الخط. 

انها ليست صفقة كبيرة إذا ديفيد يفعل مع خطوة واحدة، ولكن مرة أخرى، والتفكير مرة أخرى إلى عندما كان لدينا ثمانية متطوعين على تنظيم وفعلناه مثل الإدراج النوع، حيث كان علينا أن نبدأ يتحرك الجميع حولها. التي حصلت مكلفة، أليس كذلك؟ هذا يجعلني ارتد عن كبير O ن، التربيعية يا كبير من ن مرة أخرى. انها ليست مثل شعور نتيجة مثالية. 

لذلك دعونا فقط بتحديث هذا. وبالتالي فإن حجم قائمة الانتظار لم يعد 2. انها الآن مجرد 1. ولكن يمكنني الآن بتحديث شيئا لم أكن تحديث من قبل، و أمام القائمة. ويمكنني أن أقول فقط، هو ذلك الموقع 1؟ حتى الآن لدينا قيمة القمامة هنا، قيمة القمامة هنا، وداود في وسط هذه القمامة. ولكن بنية البيانات لا تزال سليمة. 

في واقع الأمر، وأنا لا تحتاج حتى ل تغيير رقم جيك السابق 9، وذلك لأن الذي يهتم. لدي ما يكفي من المعلومات الآن في حجم وأنا أعلم أن هناك شخص واحد في قائمة الانتظار هذه. وأنا أعلم أن هذا الشخص هو في موقع 1، 0 لا. أنا لا عد. حتى 1 كذلك. وبالتالي فإن بنية البيانات لا تزال موافق. 

حسنا، ماذا سيحدث بعد ذلك؟ دعونا إدراج بقائمة الانتظار - ما اسمك؟ 

الجمهور: كالين. 

DAVID مالان: كالين. دعونا إدراج بقائمة الانتظار وكالين، و 22 هو الآن في قائمة الانتظار. وحتى الآن ما يجب أن يتغير هنا؟ الجبهة لن تغيير، ومن الواضح. حجم سيتغير ليكون 2 مرة أخرى. و22 ينتهي هنا، 9 لا تزال موجودة، لكنه فعال قيمة القمامة الآن. انها مجرد بقايا جيك الماضية. 

وحتى الآن ماذا يحدث إذا أنا dequeue ديفيد؟ عملية واحدة الماضي، dequeue ديفيد. نحن يمكن أن يتحول، ولكن أقترح السماح لل القيام بعمل أقل قدر ممكن. الآن يذهب بنية البيانات الخاصة بي مرة أخرى في حجم 2-1. ولكن الجزء الأمامي من الطابور يصبح الآن 2. ولست بحاجة لتغيير هذه الأرقام فقط حتى الآن، لأنهم القيم القمامة فقط. 

ولكن ما يحدث الآن؟ افترض إدراج بقائمة الانتظار نفسي، 26؟ أشعر أنني أنتمي إلى هنا. لذلك أنا يجري enqueued. لذلك أنا نوع من ينتمون هنا. وعلى الرغم من أنك لا تماما نقدر هذا بصريا على المسرح، لأن لدينا الكثير من الغرفة، ينبغي لي لا أن يقف هنا، لماذا؟ 

الحضور: أنت خارج الحدود. 

DAVID مالان: الحق. أنا خارج الحدود. لقد فهرستها وراء حدود هذه المجموعة. أنا حقا يجب أن يكون في واحدة من ثلاثة مواقع ممكن. الآن، أين الأكثر طبيعية أن تذهب؟ أقترح أننا الاستدانة أسبوع خدعة واحدة. المشغل وزارة الدفاع، والنسبة المئوية. لأنني أقف من الناحية الفنية في موقع 3، لكنني 3 قدرة وزارة الدفاع، حتى 3، علامة النسبة المئوية، 3 - قدرة 3. ما هذا؟ ما هو الباقي عند قمت بتقسيم 3 بنسبة 3؟ 0. 

بحيث يضع لي كان كان جيك، وهو أمر جيد فعلا. وحتى الآن تنفيذ من يحدث هذا الشيء ل يكون قليلا من الصداع. انها حقا سطر واحد فقط من صداع، من التعليمات البرمجية. ولكن على الأقل الآن هناك القمامة قيمة هنا، ولكن هناك اثنين رجات المشروعة هنا. وأزعم أن الآن قمنا به بالضبط ما يتعين علينا القيام به طالما نغير ما في جيك كانت قيمة أن تكون 26. 

لدينا الآن ما يكفي من المعلومات لا تزال للحفاظ على سلامة هذه البنية البيانات. ما زلنا نوع من الخروج من الحظ عندما كنا تريد إدراج أربعة أو أكثر من مجموع العناصر، لكنني يمكن أن تجعل ما لا يقل عن جميلة كفاءة استخدام هذا الثابت الوقت، في الواقع. أنا لا داعي للقلق حول تحويل كان الجميع، والميل داود. 

أي أسئلة حول مداخن، أو قائمة الانتظار هذه؟ 

الحضور: هل السبب كنت بحاجة إلى حجم حتى تعرف حيث أن يكون الشخص؟ 

DAVID مالان: بالضبط. ولست بحاجة لمعرفة حجم المصفوفة لأنني بحاجة إلى معرفة بالضبط كيف العديد من هذه القيم هي مشروعة، وبحيث يمكنني العثور على مكان لوضع الشخص التالي. بالضبط. حجم هو - في الواقع، لم نكن تحديث هذا الموضوع حتى الآن. وأضاف أنا نفسي في 26. حجم هو الآن، وليس 1، ولكن 2. وحتى الآن وهذا يساعد في الواقع لي العثور على رئيس القائمة، والتي هي ليست 0، وليس 1، ولكن هو 2. الجزء الأمامي من قائمة هو في الواقع عدد 22. لأنه جاء في الأولى، حتى انه ينبغي يسمح في مخزن قبلي، على الرغم من بصريا انا واقفة أقرب إلى المخزن. 

كل الحق؟ جولة من التصفيق لهؤلاء الرجال ونحن سوف تتيح لهم للخروج من هناك. 

[تصفيق] 

DAVID مالان: أنا يمكن أن تسمح عليك أن تبقي الدرج. يمكننا أن نرى ماذا يحدث إذا تريد، ولكن ربما لا. حسنا. حتى الآن ما لا تترك لنا؟ حسنا، اسمحوا لي أن أقترح أن هناك قليل من هياكل البيانات الأخرى التي يمكن البدء في إضافة إلى مجموعة من الأدوات التي من شأنها دينا يكون في الواقع تماما، تماما كما ذات الصلة نحن يغوص في الاشياء على شبكة الإنترنت. والتي مرة أخرى، لديه بعض النوع من الاتصال إلى الأشجار في شكل ما يسمى DOM، وثيقة نموذج كائن. ولكن سنرى أكثر من أن قبل فترة طويلة. 

اسمحوا لي أن أقترح أننا definitionally استدعاء الشجرة الآن ما يمكن أن تعرف باسم أكثر من شجرة العائلة، حيث يمكنك لدينا بعض السلف في جذور شجرة. A الأبوية أو الأم الحاكمة في أعلى جدا من الشجرة. دون أزواجهن، في هذه الحالة. ولكن لدينا الآن ما سنقوم بالاتصال الأطفال، والتي هي العقد التي شنق قبالة الطفل اليسرى أو اليمنى للطفل، الأسهم كما هو مبين هنا. 

وبعبارة أخرى، في بنية البيانات شجرة في الكمبيوتر، وشجرة لديه صفر أو أكثر من العقد. إذا كان لديه عقدة واحدة على الأقل، وهذا ما يسمى الجذر. انها الأشياء بصريا أن نلفت في الأعلى. وتلك العقدة، مثل أي عقدة أخرى، يمكن لديك صفر، واحد، أو اثنين، أو ثلاثة، أو ولكن العديد من الأطفال يدعم هيكل البيانات. في هذه الحالة، الجذر، تخزين قيمة واحدة، لديه طفلان و 2 و 3، لذلك نحن ندعو عموما 2 اليسار الأطفال و3 الطفل الصحيح. 

وبعد ذلك عندما نصل الى 5، 6، و 7، 6 يمكن أن يطلق عليه الطفل الأوسط. إذا كان لديك أربعة أطفال، فإنه يحصل مربكة. ولذا فإننا التوقف عن استخدام هذا النوع من اختصار لفظيا. لكنها في الحقيقة مجرد شجرة العائلة. ويترك هنا العقد التي أنفسهم ليس لديهم أطفال. انهم شنق قبالة الجزء السفلي من الشجرة. 

فكيف يمكن أن ننفذ الشجرة التي فقد اثنين من الأطفال فقط إلى الحد الأقصى؟ سنقوم نسميها شجرة ثنائية. ثنائية يعني مرة أخرى اثنين، في هذا الحالة، كما هو الحال مع ثنائي. ولذا فإنه يمكن أن يكون صفر، واحد، أو طفلين الحد الأقصى. 

أنا أقترح أن ننفذ العقدة لهذا الهيكل مع ن الباحث، ثم اثنين من المؤشرات، واحدة تسمى اليسار، واحد يسمى الحق. ولكن تلك هي لطيفة فقط الاتفاقيات التعسفي. وعلى ما هو جميل الآن، خصوصا إذا كنت نوع من ناضل من الناحية المفاهيمية مع العودية، أو يعتقد أنه لم يكن حقا حل لأي شيء، خاصة إذا كنت قد نفاد الذاكرة. الآن أننا نتحدث عن البيانات الهياكل والخوارزميات التي تسمح لنا لتعبر والتلاعب بها، تبين أن يعود في العودية أكثر إقناعا إن لم يكن بطريقة جميلة. 

لذلك هذا أقترح هو تنفيذ وظيفة البحث. نظرا اثنين من المدخلات - لذلك أعتقد أن هذا بمثابة الصندوق الأسود. نظرا اثنين من المدخلات، ن، وكثافة العمليات، و مؤشر إلى شجرة، مؤشر إلى العقدة، أو حقا جذر شجرة، وأنا يزعمون أن هذه الوظيفة يمكن العودة صحيحة أو خاطئة، أن قيمة ن داخل هذه الشجرة. 

ما داخل هذا المربع الأسود؟ حسنا، أربعة فروع. أول يتحقق فقط. إذا الشجرة هو باطل، والعودة فقط كاذبة. اذا لم يكن هناك عقدة، وليس هناك ن، ليس هناك عدد، والعودة فقط كاذبة. إذا رغم ذلك، ن، القيمة التي تبحث ل، هو أقل من شجرة السهم ن، و لمجرد أن يكون واضحا، ماذا يعني عندما أنا أكتب شجرة ثم السهم التدوين، ن؟ بالضبط. وهو ما يعني إلغاء مرجعية التي دعا مؤشر شجرة. الذهاب إلى هناك، ومن ثم الحصول على داخل ذلك عقدة والحصول على مجالها دعا ن. ثم قارن ن الفعلية التي كان مرت في البحث ضدها. 

حتى إذا كان n أقل من، قيمة ن في عقدة الشجرة نفسها، وأيضا، ماذا يعني ذلك؟ هذا لا يعني شيئا للوهلة الأولى. أليس كذلك؟ تماما مثل عندما يكون لديك مجموعة من القيم، قد ترغب في تطبيق ثنائي بحث كشكل من أشكال الانقسام وقهر. ولكن ما لم الافتراض نحن بحاجة لجعل للبحث ثنائي للعمل في جميع في دفتر الهاتف و أمثلة في وقت سابق؟ 

كيف يمكن فرز. لذلك دعونا صقل تعريف شجرة هنا لا يجب أن يكون مجرد شجرة، والتي يمكن لديك أي عدد من الأطفال. وليس فقط شجرة ثنائية، والتي يمكن لديك 0، 1، 2 أو الحد الأقصى. ولكن مثل شجرة البحث الثنائي، أو BST، الذي هو مجرد طريقة أخرى للقول ل شجرة ثنائية مثل أن كل عقدة الطفل الأيسر، إذا كان موجودا، هو أقل من العقدة. والحق طفل كل عقدة، إذا كان موجودا، هو أكبر من العقدة نفسها. 

لذلك وبعبارة أخرى، إذا كنت لرسم شجرة خارج، كل من الأرقام متوازنة بعناية من هذا القبيل بحيث إذا لديك 55 كجذر، 33 يمكن أن تذهب إلى اليسار لأنها أقل من 55. 77 يمكن أن تذهب إلى اليمين، ذلك لأن انها أكبر من 55. ولكن الآن لاحظت، ونفس التعريف، انها تعريف العودية لفظيا، يجب أن تطبق لمدة 33. يجب أن يكون 33 في الطفل اليسرى أقل من ذلك، و 33 في حق الطفل، 44، يجب أن يكون أكبر من ذلك. 

لذلك هذا هو الشجرة البحث الثنائي، و أقترح، وذلك باستخدام قليلا من العودية، يمكننا الآن العثور ن. حتى إذا كان n أقل من قيمة ن هذا عقدة الحالي، وانا ذاهب للذهاب قدما والبونت، إذا جاز التعبير، وعادل العودة مهما كان الجواب من البحث عن ن على الطفل الشجرة اليسرى. لاحظ مرة أخرى، هذه الوظيفة فقط وتتوقع نجم عقدة، و مؤشر إلى العقدة. ذلك بالتأكيد يمكنني القيام به للتو شجرة سهم اليسار، الأمر الذي سيؤدي لي إلى عقدة أخرى. ولكن ما هو تلك العقدة؟ 

حسنا، وفقا لهذا الإعلان، اليسار هو مجرد مؤشر، بحيث فقط يعني أنا عابرة إلى وظيفة البحث مؤشر مختلفة، وهي واحد الذي يمثل شجرة يساري الطفل. حتى في هذه الحالة، المؤشر إلى 33، إذا هذا هو موقفنا عينة المدخلات وفي الوقت نفسه، إذا n هو أكبر من قيمة ن في العقدة الحالية في الشجرة، ثم أنا ذاهب الى المضي قدما والبونت في الآخر التوجيه ونقول فقط، وأنا لا أعرف إذا كان هذا قيمة n هو في شجرة، لكنني أعرف ما إذا كان هو، انها أسفل بلدي فرع الحق، إذا جاز التعبير. لذلك اسمحوا لي استدعاء متكرر بحث، تمرير ن مرة أخرى، ولكن يمر في مؤشر إلى حقي الطفل. 

وبعبارة أخرى، إذا أنا حاليا في 55 وأنا أبحث عن 99، وأنا أعرف أن 99 هو أكبر من 55، وذلك فقط مثل أنا مزقت الأسابيع دفتر الهاتف، ونحن منذ ذهب الحق، نحن بالمثل سوف يسير في الاتجاه الصحيح هنا. وأنا لا أعرف ما اذا كان في حقي الطفل، وانها ليست، 77 هناك، ولكن وأنا أعلم أنه في هذا الاتجاه. لذلك أدعو البحث على حقي الطفل، 77، والسماح الرقم الخروج من البحث هناك إذا 99 في هذا التعسفي مثال على ذلك هو في الواقع هناك. 

آخر، ما هو الحال النهائي؟ إذا شجرة باطل هو حالة واحدة. إذا كان n أقل من العقدة الحالية القيمة هي قضية أخرى. إذا كان n أكبر من الحالية قيمة العقدة هي الحالة الثالثة. ما هي الحالة الرابعة والأخيرة؟ أعتقد نحن من الحالات، أليس كذلك؟ يجب أن يكون ذلك n هو في العقدة الحالية التي أنا على. 

حتى إذا أنا في البحث عن 55 في هذه المرحلة في القصة، وهذا فرع من فروع أن شجرة العودة الحقيقية. فما هو المثير للاهتمام هنا هو أننا في الواقع، على عكس الأسابيع الماضية، نحن نوع من لديها حالتين القاعدة. وليس لديهم ل يكون كل في الأعلى. الأعلى هو الحالة الأساسية لأنه إذا كان شجرة باطل، وهناك شيء للقيام به. فقط إرجاع الثابت ترميز قيمة خاطئة. 

الفرع السفلي هو نوع من الافتراضي، حيث إذا قمنا فحص ل فارغة، لقد فحص ما اذا كان ينبغي أن يكون اليسار، ولكن لا ينبغي أن يكون، لدينا فحص إذا كان ينبغي أن يكون على حق، لكنها لا ينبغي أن يكون من الواضح أنه يجب أن يكون الحق ما نحن فيه. وهذا هو حال القاعدة. لذلك هناك حالتين العودية تقع هناك في الوسط. ولكن كان بوسعي أن أكتب هذا في أي أمر. أنا فقط أعتقد أنه نوع من شعر طبيعي للتحقق أول لخطأ ممكن، ثم تحقق اليسار، ثم تحقق الحق، ثم نفترض أن كنت في عقدة كنت فعلا تبحث عن. 

فلماذا هذا قد يكون مفيدا؟ حتى اتضح - واسمحوا لي أن تقفز إلى دعابة هنا وهذا في شبكة الإنترنت. ونحن في طريقنا للبدء في استخدام ليس لغة البرمجة في البداية، ولكن لغة الترميز. لغة ترميز كائن واحد وهذا مماثلة للبرمجة اللغة، لكنها لا تعطيك القدرة على التعبير عن نفسك منطقيا. إلا أنها تعطيك القدرة على التعبير عن نفسك هيكليا. 

أين تريد وضع شيء على الصفحة، صفحة الويب؟ ما اللون الذي تريد أن تجعل من؟ ما حجم الخط هل تريد أن تجعل من؟ ما الكلمات هل فعلا تريد على صفحة الويب؟ ذلك أن لغة ترميز. ولكن بعد ذلك نحن سوف أعرض بشكل سريع جدا جافا سكريبت، وهو العضوية الكاملة لغة البرمجة. بناء جملة مشابهة جدا في المظهر لC، ولكنه سيكون لديك بعض لطيفة، وأكثر قوة، وأكثر ميزات سهلة الاستخدام. 

واحدة من الإحباط في هذا نقطة في الفصل الدراسي هو أننا سوف قريبا تنفيذ سبيلر في عدد أقل بكثير الأسطر من التعليمات البرمجية باستخدام لغات أخرى من C نفسها تسمح، ولكن لسبب و سنقوم فهم قريبا. وستكون هذه أول صفحة ويب من هذا القبيل. سيكون مخيب تماما، أول واحد التي نتخذها. فإنه سيقول ببساطة، مرحبا العالم. ولكن إذا كنت لم أر قط ذلك من قبل، وهذا هو HTML، لغة توصيف النص التشعبي. 

إذا ذهبت إلى خيار القائمة معينة في أكثر من أي متصفح، على أي صفحة على شبكة الإنترنت الانترنت، يمكنك أن ترى HTML أن بعض الناس كتب ل خلق هذا صفحة ويب. وربما لا تبدو كما موجزة أو أنيق مثل هذا. ولكنه سوف تتبع نمط من هذه الأقواس المفتوحة ومائلة و الرسائل ويحتمل أن تكون الأرقام. 

ظننت أنني كنت أعطيك دعابة ما عليك أن تكون قادرا على القيام بعد أخذ CS50. اسمحوا لي أن انتقل إلى cs.harvard.edu / سرقة، لدينا موقع روب بودين الخاصة. الذي أدلى به هذا بالنسبة لنا. لذلك عليك أن تكون قادرة على القيام بذلك قريبا. وأيضا، ما سمعت هذا الصباح - ما سمعت هذا الصباح - 

[HAMSTER DANCE MUSIC] 

- اختر مربع الطباعة تكون قادرة على جعل هذا. التي تنتظرنا يوم الاربعاء. سوف نرى لك ذلك الحين. 

[HAMSTER DANCE MUSIC] DAVID مالان: في CS50 المقبل -