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

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

وطلبنا في السؤال 0، لنفترض أن النسخة 1 هي تجميعها وتنفيذها. لماذا قد سوف segfault البرنامج؟ للوهلة الأولى، أي اقتراحات لماذا؟ نعم. 

الحضور: وهكذا أتذكر رؤية هذا في والمثال السابق في النظر إلى شار * ق ورؤية الفحص من ليالي و رؤية لأنها مؤشر، كيف أنها لم تؤثر على ما الممسوحة ضوئيا في؟ هي ليالي أو عنوان من ليالي؟ 

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

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

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

الحضور: إذا كنت تستخدم هذا المدخل في سلسلة هذا هو أطول من 49 حرفا. 

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

ولكن بالضبط، إذا كنت تقرأ سلسلة وهذا أطول من 49 حرفا، 49 لأنك تحتاج للغرفة مائل 0، وأنت تسير لتجاوز هذا المخزن. وكنت قد تحصل على الحظ وتكون قادرة على كتابة حرف 51، 52، 53. ولكن في مرحلة ما، ونظام التشغيل وأريد أن أقول، لا. هذا هو بالتأكيد ليست الذاكرة كنت يسمح للمس. والبرنامج هو الذهاب الى سوف segfault. 

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

الحضور: وهكذا من أجل حل ذلك، هل يمكن أن وكان بيان التحقق في الواقع هو أكبر طول من أو أقل من؟ 

DAVID J. مالان: بالتأكيد. أنت فقط لديك حالة أن يقول، إذا كان - أو بالأحرى كنت لا تعرف بالضرورة مقدما كيف العديد من الشخصيات و المستخدم هو الذهاب الى الكتابة، لأن لديك الدجاج والبيض. لا حتى كنت قد قرأت في مع scanf يمكنك معرفة متى هو. ولكن في هذه النقطة، فوات الاوان، لأنك قد قرأت بالفعل في بعض كتلة من الذاكرة. ذلك جانبا، ويتجنب مكتبة CS50 هذه المسألة تماما، وأذكر باستخدام fgetc. ويقرأ حرف واحد في وقت واحد، جنبا إلى جنب، مع العلم يغرد-غيض التي لا يمكن تجاوز حرف إذا تقرأ في وقت واحد. 

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

لذلك يسأل السؤال 2، افترض أن الإصدار 3 يتم تجميعها وتنفيذها. لماذا قد سوف segfault هذا البرنامج؟ لذلك هذا واحد هو في الواقع نفس الإجابة، على الرغم من أنها يبدو مربي الحيوانات قليلا. نستخدمه malloc، الذي يشعر وكأنه منحنا أنفسنا المزيد من الخيارات. ثم نحن تحرير تلك ذاكرة في نهاية المطاف. انها لا تزال على بعد 50 بايت من الذاكرة. ولذا فإننا قد لا تزال في محاولة لقراءة في 51، 52، 1،000 بايت. انها سوف سوف segfault ل بالضبط نفس السبب. 

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

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

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

ROB BOWDEN: إذن المشكلة 4. هذا هو واحد حيث كان لديك لملء في عدد من وحدات البايت من جميع هذه الأنواع المختلفة المستخدمة. أولا حتى نرى الشيء. تفترض بنية 32 بت، مثل هذه الأجهزة CS50. لذلك واحدة من الأشياء الأساسية حول أبنية 32 بت، وهذا يخبرنا بالضبط كيف كبيرة مؤشر يجري أن تكون في الهندسة المعمارية. 

لذلك على الفور، ونحن نعلم أن أي مؤشر نوع هو 32 بت أو 4 بايت. حتى النظر في هذا الجدول، و * عقدة هو نوع المؤشر. التي ستكون 4 بايت. عقدة البنية *، وهذا حرفيا مطابقة للنجمة العقدة. وبحيث ستكون 4 بايت. سلسلة، حتى لا تبدو وكأنها الماوس للبعد، ولكن الرموز المميزة ل typedef، و سلسلة هو مجرد شار *، والتي هو نوع المؤشر. بحيث ستكون 4 بايت. 

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

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

الحضور: هل كان 64 بت الهندسة المعمارية، من شأنه أن مضاعفة كل منهم؟ 

ROB BOWDEN: إنه لن مضاعفة كل منهم. حتى الهندسة المعمارية 64 بت، ذلك، مرة أخرى، التغييرات التي الشيء الأساسي أن المؤشر الآن 64 بت. نعم. لذلك المؤشر هو 8 بايت. لذلك فان هذه التي كانت 4 بايت ستكون 8 بايت. الطالب، الذي كان اثنين من المؤشرات، حسنا، الآن انه سيكون ل يكون 8 بايت و 8 بايت. انها تسير لجعل 16 بايت. 

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

نعم. ذلك شيئا حيال بنجاح طلب مرت. وانهم قادرين على العودة كل ما طلب. لذلك كل شيء على ما يرام. ماذا عن 302 وجدت؟ نعم. 

الحضور: الخادم كان يبحث لماذا أنت المطلوب. ولكن لا يمكن العثور عليه. ولذلك لا يوجد خطأ. 

ROB BOWDEN: هكذا كان الخادم أبحث عن ما تريد. حتى مجرد النظر هنا، وجدت 302، كان قادرا على العثور عليه. 

الجمهور: أنا آسف. وجدت يعني أنها لم تجد ذلك. آسف. 

ROB BOWDEN: حتى 302 وجدت. الملقم غير قادرة على العثور على ما أردت. 

الحضور: ولكن كنه لا يظهر ذلك؟ 

ROB BOWDEN: الفرق بين هذا 302 و 200 هو أنه يعرف ما تريد. ولكنها ليست بالضبط أين كنت أريد أن أطلب. حتى 302 هو إعادة توجيه نموذجي. لذلك يمكنك طلب صفحة. فهو يعرف، يا، أريد للعودة لك هذا. ولكن هذا هو في URL مختلفة. لذلك مهلا، كنت تريد هذا الواقع. 

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

ROB BOWDEN: OK. فكيف 403 ممنوع؟ 

الحضور: اعتقد انه من أن الملقم يقول أساسا أن العميل لا يمكن الوصول إلى الصفحة الرئيسية. 

ROB BOWDEN: لذا نعم. حسنا، كنا الإجابة النموذجية تتوقع هو شيء من هذا القبيل، وملفات لا chmodded مناسب. وهذا ربما تحت أي ظرف من الظروف رأيت منهم. ولكن هناك سبب أن العميل يمكن أن تكون على خطأ هنا. هناك في الواقع رمز حالة أخرى - 401. لذلك فان هذه متشابهة جدا. 

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

DAVID J. مالان: والآلية التي والتي عادة ما تكون هذه المشاكل تحل على الملقم عبر ما الأمر؟ التصريح، لو كان، في الواقع، أذونات إصدار على الملف أو الدليل. 

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

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

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

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

ROB BOWDEN: نعم. 

الحضور: أراد أن الخطأ لا تزال تأتي؟ 

ROB BOWDEN: إذن أنت لن قد حصلت هذا الخطأ لأن كل شيء من وجهة نظر خادم الويب ل على ما يرام تماما. لكنك طلبت index.html و. كنت طلبت shuttle.js وservice.js. وكان قادرا على العودة بنجاح لك كل تلك الأشياء - 200. موافق. انها فقط عندما حاول المتصفح ل تفسير شفرة جافا سكريبت التي انها مثل، الانتظار، وهذا ليس جافا سكريبت خطأ صالحة. أي أسئلة أخرى؟ حسنا. 

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

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

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

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

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

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

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

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

الحضور: في مؤشر السهم [غير مسموع] يساوي فارغة، يفعل ذلك التعامل مع قائمة ل قائمة باطل؟ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

الجمهور: ذلك هو قائمة مماثلة ل يتوجه في الأمثلة السابقة. 

DAVID J. مالان: بالضبط، بالضبط. مجرد اسم آخر لل متغير عمومي. في جميع أنحاء العالم ما؟ 

ROB BOWDEN: OK. لذلك هذا هو واحد حيث كنت وكان لكتابة الفقرة. كتب بعض الناس المقالات لهذا السؤال. ولكن تحتاج فقط إلى استخدام هذه المصطلحات ستة لوصف ما يحدث عندما حاولت الاتصال facebook.com. ولذا فإنني سوف مجرد كلام من خلال عملية استخدام جميع هذه الشروط. حتى في المتصفح لدينا، ونحن اكتب facebook.com وهاهنا. حتى يحدث المتصفح لدينا لبناء HTTP طلب أن انها بصدد ارسال من خلال بعض العمليات إلى الفيسبوك ل الفيسبوك للرد لنا مع HTML من الصفحة الخاصة به. 

فما هي العملية التي الذي طلب HTTP يحصل فعلا إلى الفيسبوك؟ لذلك أولا، ونحن بحاجة إلى ترجمة Facebook.com. حتى مجرد إعطاء اسم Facebook.com، أين الواقع على طلب HTTP تحتاج أن تذهب؟ لذلك نحن بحاجة لترجمة Facebook.com إلى عنوان IP، والتي فريد ويحدد الجهاز ما نحن في الواقع تريد إرسال هذا الطلب إلى. الكمبيوتر المحمول لديه عنوان IP. أي شيء متصلا بالإنترنت لديه عنوان IP. 

لذلك DNS، نظام اسم المجال، وهذا هو ما يحدث للتعامل مع الترجمة من facebook.com إلى عنوان IP الذي كنت فعلا تريد الاتصال. لذلك نحن الاتصال خوادم DNS و مثلا، ما هو facebook.com؟ تقول، يا، انها عنوان IP 190،212 شيء ما، شيء ما، شيء ما. حسنا. الآن، وأنا أعلم ما آلة أريد أن الاتصال. 

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

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

وذلك عندما يستقبل جهاز الكمبيوتر الخاص بك بعض البيانات من الإنترنت، وكيف يفعل ذلك نعرف ما التطبيق في الواقع يريد البيانات؟ كيف أنها لا تعرف ما إذا كان هذا خاص والمقصود البيانات ل torrenting تطبيق في مقابل لمتصفح الإنترنت؟ لذلك هذا هو الغرض من الموانئ في تلك كل من هذه التطبيقات لديها ادعى منفذ على جهاز الكمبيوتر الخاص بك. لذلك يقول متصفح الويب الخاص بك، مهلا، أنا الاستماع على منفذ 1000. وبرنامج torrenting الخاص قائلا: أنا الاستماع على منفذ 3000. وتقول سكايب، أنا باستخدام المنفذ 4000. 

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

إذا أرادوا، فإنها يمكن أن تعيينها حتى انه يسرد كما على المنفذ 7000. ثم في متصفح الإنترنت، ويمكنني أن اكتب يدويا Facebook.com: 7000 ل إرسال الطلب إلى الميناء 7000 من خادم الويب في الفيسبوك. 

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

ROB BOWDEN: إذن HTTPS، لأنه الاستماع خصيصا ل مشفرة، انها على المنفذ 4430. 

الحضور: ورسائل البريد الإلكتروني و25، أليس كذلك؟ 

DAVID J. مالان: الصادرة رسائل البريد الإلكتروني، 25، موافق. 

ROB BOWDEN: أنا لا أعرف حتى معظم و- كل من أقل منها تميل إلى أن تكون محفوظة للأشياء. أعتقد أن كل شيء تحت 1024 محجوز. 

الحضور: لماذا تقولون 3 كان عدد خاطئ؟ 

ROB BOWDEN: لأن في عنوان IP، هناك أربع مجموعات من الأرقام. وانهم 0-255. حتى 192.168.2.1 هو مشترك عنوان IP الشبكة المحلية. لاحظ كل من هؤلاء كانوا من أقل من 255. لذلك عندما بدأت مع 300، التي ربما لا يمكن أن يكون كان واحدا من الأرقام. 

DAVID J. مالان: ولكن هذا مقطع سخيفة من - كان CSI، حيث كان لديهم الرقم الذي كان كبير جدا للحصول على عنوان IP. 

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

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

وبعد ذلك قال أيضا في السؤال نفسه، وتذكر لإغلاق قائمة غير مرتبة العلامة. لذلك نحن بحاجة للخروج من وضع PHP من أجل القيام بذلك. أو أننا يمكن أن ردد إغلاق قائمة غير مرتبة العلامة. 

DAVID J. مالان: أيضا غرامة هنا سوف وقد كان لاستخدام المدرسة القديمة ل حلقة مع ط = $ 0 0 واستخدام التهم ل معرفة طول راي. تماما غرامة للغاية، فقط قليلا wordier. 

الجمهور: حتى لو كنت ذاهب ل [غير مسموع]، كنت ستفعل - أنسى ما حلقة [غير مسموع] هو. هل رباعية $ قوس ط؟ 

DAVID J. مالان: بالضبط. نعم، بالضبط. 

ROB BOWDEN: أي شيء آخر؟ 

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

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

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

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

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

الجمهور: حتى إذا نحن فقط وقال أقل أمنا - 

DAVID J. مالان: [ضحك] هتاف اشمئزاز. تلك هي دائما أصعب منها للفصل. 

ROB BOWDEN: وهذا من شأنه قد قبلت. 

DAVID J. مالان: ماذا؟ 

ROB BOWDEN: أنا خلقت هذه المشكلة. التي من شأنها أن قد قبلت. 

DAVID J. مالان: نعم. 

الحضور: بارد. 

ROB BOWDEN: ولكن لم نقبل لأول واحد - حسنا، ما كنا نبحث عن شيء من هذا القبيل لم يكن لديك ل التواصل مع الخادم. لم نقبل فقط أسرع. 

الحضور: ماذا عن لا إعادة تحميل الصفحة؟ 

ROB BOWDEN: نعم. كان ذلك جوابا مقبولا. 

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

الجمهور: انها خطية. البحث على قائمة مرتبطة بشكل طولي بدلا من ما تقوم بتسجيل الدخول. 

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

الجمهور: الذاكرة غير فعالة؟ 

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

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

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

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

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

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

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

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

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

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

ROB BOWDEN: إذن لسيناريو الصعود، فعلنا لا يقبل من تلقاء نفسها "أسرع". أنت كان يقول شيئا حيال ذلك. حتى لو قال لك نظريا أسرع، كنا نعرف أن لنوع من يفهم انه من 0 1. وجدول التجزئة، من الناحية النظرية، ليس 0 1. يذكر أي شيء عن وقت عموما حصل لك نقطة. ولكن "أسرع"، معظم الحلول على مجلس الكبيرة التي كانت محاولات أبطأ من حلول موضوعية التي كانت الجداول التجزئة. لذلك أسرع في حد ذاته ليس صحيحا حقا. 

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

ROB BOWDEN: كان لي في الواقع أي فكرة. 

DAVID J. مالان: وهي مصنوعة الشعور في رأسي. 

ROB BOWDEN: أنا أفعل هذا واحد. موافق. لذلك هذا هو واحد حيث كان عليك أن رسم مخطط مماثل لك قد وقد شهدت في الامتحانات الماضية. لذلك دعونا ننظر فقط في هذا. لذلك من العقدة HTML، لدينا اثنين الأطفال والرأس والجسم. لذلك نحن فرع - الرأس والجسم. رئيس لديه علامة العنوان. لذلك لدينا عنوان. 

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

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

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

ROB BOWDEN: أسئلة على ذلك؟ يجب أن أفعل واحد القادم؟ 

DAVID J. مالان: بالتأكيد. 

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

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

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

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

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

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

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

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

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

DAVID J. مالان: ليس تماما روح السؤال ولكنها مقبولة فقا ل المواصفات مع ذلك. 

ROB BOWDEN: أسئلة على أي من ذلك؟ الشيء الوحيد الذي كنت على الأقل قد تحتاج إلى ترجمة التعليمات البرمجية. ذلك على الرغم من الناحية الفنية لم تكن الضعيفة إذا التعليمات البرمجية لا تجميع، ونحن لا نقبل ذلك. أي الأسئلة؟ موافق. 

DAVID J. مالان: هل تريد أن أقول هذا العنوان؟ 

ROB BOWDEN: رقم 

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

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

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

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

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

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

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

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

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

الجمهور: فإنه يحصل على القيمة التي لم يكن المستخدم في HTML أدناه. فإنه يحصل أن ID ثم يجد قيمة لها. 

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

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

ثم أدق التفاصيل هو هذا. لماذا أعود داخل كاذبة هذه الوظيفة المجهول؟ 

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

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

الحضور: لأنه يحدث فقط مرة واحدة. 

DAVID J. مالان: يحدث مرة واحدة فقط. ليس تماما. نعم؟ 

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

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

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

الحضور: وهكذا ابقائها من جانب العميل. 

DAVID J. مالان: حفظ من جانب العميل ذلك. صحيح تماما. يصل المقبل كان لي يا ماي. 

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

الآن، والتوازن، والتفكير مرة أخرى إلى pset7. لذلك نحن تستخدم خصيصا العشرية ل تخزين قيمة الأسهم أو - 

DAVID J. مالان: النقد. 

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

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

ما هو الرقم الذي نقول دائما؟ 2 إلى 32، وهو ما يقرب من؟ لم يكن لديك لمعرفة على وجه التحديد. ولكن من المفيد في الحياة تقريبا. انها تقريبا 4 مليارات. لذلك قلنا أن بضع مرات. أعرف أنني قد قال إن عدة مرات. وذلك هو ما يقرب من 4 مليارات. وهذا هو قاعدة جيدة من الإبهام إلى معرفته. إذا كان لديك 8 بت، 256 هو الرقم السحري. إذا كان لديك 32 بت، 4 مليار يعطي أو يأخذ. لذلك إذا كنت أكتب فقط بانخفاض 4 مليارات، سترى أنه من أرقام أقل من 12، مما يعني أن من الواضح لا التعبير بما يكفي لالتقاط رقم الحساب 12 أرقام. 

ROB BOWDEN: OK. حتى ذهب بعضها الآخر على نحو أفضل. لذلك نفترض أن البنك يفرض 20 دولارا شهريا رسوم الصيانة في جميع الحسابات. مع ما يمكن الاستعلام SQL البنك خصم 20 دولارا عن كل عدد، حتى لو أنه يؤدي في بعض أرصدة سلبية؟ ذلك أساسا، وهناك أربعة أنواع رئيسية من الاستعلامات - إدراج، حدد، تحديث، وحذف. وذلك ما لم نفكر نحن تنوي استخدام هنا؟ تحديث. 

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

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

ROB BOWDEN: تذكر أن الخلية هي لغة منفصلة من PHP. نحن يحدث ليكون كتابة الخلية في PHP. وPHP ثم يتم إرساله لأكثر من خادم MySQL. لكنك لا تحتاج من أجل PHP التواصل مع خادم MySQL. 

DAVID J. مالان: بالضبط. لذلك لا المتغيرات مع علامات الدولار وينبغي أن تكون في هذا السياق. ويمكن ان يفعل كل من الرياضيات ضمن قاعدة البيانات نفسها. 

ROB BOWDEN: OK. ذلك واحد القادم. هل هذا هو واحد في المرة القادمة؟ نعم. ذلك مع ما يمكن الاستعلام SQL البنك استرداد أرقام الحسابات من ل أغنى العملاء، مع تلك أرصدة أكبر من 1،000؟ لذلك أي من الأنواع الأربعة الرئيسية نحن ذاهبون إلى تريد هنا؟ حدد. لذلك نحن نريد لتحديد. ماذا نريد لاختيار؟ ما العمود الذي نريد لاختيار؟ ونحن سوف تريد على وجه التحديد لتحديد العدد. ولكن إذا قلت نجوم، ونحن كما قبلت ذلك. 

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

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

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

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

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

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

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

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

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

الحضور: س يتم تخزين القيم الإيجابية. منذ قمت بتخزين القيم الإيجابية فقط في ف، السلبي هو خطأ. 

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

الحضور: لقد فشلت لإرجاع عدد صحيح. 

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

حتى مع dequeue، ما كنا يقترح القيام به هو - 

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

DAVID J. مالان: هذا لماذا أنا لم أقل ذلك. 

ROB BOWDEN: ولكن ذلك لم يكن صحيحا أنه لا يمكنك العودة كاذبة. 

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

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

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

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

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

حتى إذا وضعت 34 هنا في الأعلى، ثم أنا وضعت 20 هنا، حتى أن ذلك صحيح الآن، لأن 34 هنا. 20 هو الذهاب الى اليسار. ذلك أن أقل. لكنني لا استطيع ثم وضع 59 هنا، ل على الرغم من أن 59 هو على حق 20، انها لا تزال على الجهة اليسرى من 34. حتى مع هذا القيد في الاعتبار، أسهل طريقة لربما حل هذه المشكلة هي مجرد نوع من هذه الأرقام - حتى 20، 34، 36، 52، 59، 106. ثم إدراج تلك من اليسار إلى اليمين. 

حتى 20 يذهب هنا. 34 يذهب هنا. 36 يذهب هنا. 52، 59، 106. وأنت أيضا يمكن أن أحسب مع بعض يسد في وتحقيق، أوه، الانتظار، وأنا لم يكن لديك ما يكفي من الأرقام لملء هذا في أكثر من هنا. لذلك أنا بحاجة إلى ما reshift بلدي مذكرة الطريق سوف يكون. ولكن لاحظ أنه في الثلاثة الأخيرة، إذا تقرأ من اليسار إلى اليمين، هو في زيادة الطلب. 

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

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

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

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

الجمهور: لدي سؤال على [غير مسموع]. 

ROB BOWDEN: حتى طريقة واحدة لتقترب أي مشكلة العودية هو التفكير فقط حول هذا الموضوع مثل عليك أن تفكر حول جميع القضايا الزاوية. لذلك نعتبر أننا نريد أن طباعة هذه الشجرة بأكملها. لذلك كل نحن ذاهبون الى التركيز على هو هذه العقدة خاص - 36. دعوات متكررة، ونحن نتظاهر تلك مجرد عمل. حتى هنا، هذا النداء عودي إلى اجتياز، ونحن دون حتى التفكير حول هذا الموضوع، مجرد عبور اليسار ثلاثة، تخيل أن يطبع بالفعل 20 و 34 بالنسبة لنا. ثم عندما كنا في نهاية المطاف بشكل متكرر استدعاء اجتياز على الحق، التي ستطبع بشكل صحيح 52، 59، و 106 بالنسبة لنا. 

ذلك بالنظر إلى أن هذا يمكن طباعة 20، 34، و من جهة أخرى يمكن طباعة 52، 59، 108، كل ما نحتاج إليه لتكون قادرة على القيام به هو طباعة بنفسي في منتصف ذلك. لذلك بطباعة كل شيء أمامنا. طباعة بنفسي، وبالتالي فإن العقدة الحالية الطباعة 36، printf العادية، ومن ثم طباعة كل شيء بعدنا. 

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

ROB BOWDEN: في الأسئلة؟ 

DAVID J. مالان: وأسفل قليلا ل الأرقام، لا أحد يعرف أين هذه الأرقام تأتي من؟ 

ROB BOWDEN: لدي أي فكرة حرفيا. 

DAVID J. مالان: وهي تظهر طوال المسابقة. 

الحضور: هل هم نفس الأرقام؟ 

DAVID J. مالان: هذه الأرقام. بيضة عيد الفصح قليلا. حتى بالنسبة لأولئك منكم مشاهدة على الانترنت في المنزل، إذا يمكنك أن تقول لنا عبر البريد الإلكتروني إلى heads@CS50.net ما أهمية من هذه الأرقام الستة المتكررة هي طوال المسابقة 1، ونحن سوف دش لكم مع إيلاء اهتمام مذهلة في المباراة النهائية محاضرة والكرة الإجهاد. لطيفة، وخفية. 

ROB BOWDEN: أي أسئلة مشاركة عن أي شيء على هذه المسابقة؟