[عزف الموسيقى] J. DAVID مالان: حسنا. هذا هو CS50. هذا هو استمر خمسة أسابيع، ونحن لدينا بعض الأخبار الجيدة وبعض الأخبار السيئة. حتى الخبر السار هو أن CS50 تطلق هذه الجمعة. إذا كنت ترغب في الانضمام إلينا، التوجه الى URL المعتاد هنا. الأخبار حتى أفضل، لا محاضرة هذا وقد 13th يوم الاثنين القادم. أقل قليلا الأخبار أفضل، مسابقة الصفر هو يوم الأربعاء المقبل. مزيد من التفاصيل يمكن أن يكون وجدت في هذا URL هنا. وعلى مدى اليومين القادمين سنكون ملء الفراغات فيما يتعلق الغرف أن نكون قد محفوظة. أفضل الأخبار هي أن هناك سوف أكون يكون استعراض على نطاق بالطبع تأتي دورة هذا الاثنين في المساء. لا تنزعج لدورة ل موقع لموقع والتفاصيل. أقسام، على الرغم من أنه هو عطلة، سيلتقي أيضا كذلك. أفضل الأخبار، محاضرة يوم الجمعة المقبل. لذلك هذا هو التقليد نحن لديهم، وفقا للمنهج. فقط .. انها سوف تكون مذهلة. سترى أشياء مثل هياكل البيانات في الوقت المستمر والجداول التجزئة والأشجار ومحاولات. وسوف نتحدث عن المشاكل عيد ميلاد. وهناك مجموعة كاملة من الاشياء ينتظر يوم الجمعة المقبل. موافق. على أية حال. لذلك أذكر أن كنا التركيز على هذه الصورة ما هو داخل ذاكرة الكمبيوتر لدينا. حتى الذاكرة أو ذاكرة الوصول العشوائي حيث هي برامج الوجود بينما كنت تشغيلها. إذا نقرت نقرا مزدوجا فوق أيقونة لتشغيل بعض البرامج أو انقر نقرا مزدوجا فوق الرمز لفتح بعض الملفات، انها حملت من الصعب ديك محرك الأقراص أو محرك أقراص الحالة الصلبة في RAM، ذاكرة الوصول العشوائي، حيث أنه يعيش حتى تنقطع الكهرباء، إغلاق غطاء الكمبيوتر المحمول، أو يمكنك إنهاء البرنامج. الآن تلك الذاكرة، من والتي ربما لديك 1 غيغا بايت في هذه الأيام، 2 غيغابايت أكثر، أو حتى بكثير، وضعت عموما خارج لبرنامج معين في هذا النوع من مستطيلة النموذج المفاهيمي حيث لدينا المكدس في القاع وحفنة من غيرها من الاشياء في الأعلى. الشيء في أعلى جدا رأيناه على هذه الصورة. قبل ولكن لم يتكلم عن هو ما يسمى جزء النص. جزء النص هو مجرد وسيلة الهوى لقول الأصفار وتلك التي يؤلف برنامج ترجمة الفعلي. وذلك عند النقر المزدوج Microsoft Word في جهاز Mac أو PC، أو عند تشغيل نقطة خفض ماريو على كمبيوتر لينكس في نافذة محطة الخاص بك، الأصفار وتلك التي تؤلف يتم تخزين كلمة أو ماريو مؤقتا ذاكرة الوصول العشوائي في جهاز الكمبيوتر الخاص بك في ما يسمى قطاع نص لبرنامج معين. دون أن يذهب تهيئة والبيانات غير مهيأ. هذه هي الاشياء مثل المتغيرات العالمية، أننا قد لا تستخدم الكثير من، ولكن في بعض الأحيان قمنا كان المتغيرات العالمية أو محددة بشكل ثابت السلاسل التي ومن الثابت ترميز كلمات مثل "مرحبا" أن لا تؤخذ في من المستخدم التي يتم الثابت تلوينها في البرنامج. الآن، في أسفل نحن لدينا ما يسمى المكدس. والمكدس، حتى الآن، لقد كان باستخدام ما لأنواع من الأغراض؟ ما كومة استخدمت ل؟ نعم؟ الجمهور: وظائف. J. DAVID مالان: بالنسبة للوظائف؟ بأي معنى للوظائف؟ الجمهور: عند استدعاء وظيفة، و يتم نسخ الحجج إلى المكدس. J. DAVID مالان: بالضبط. عند استدعاء دالة، لها يتم نسخ الحجج إلى المكدس. حتى في أي X أو Y أو في وأو لB ان كنت تمر في وظيفة يتم وضع بشكل مؤقت على ما يسمى المكدس، مجرد مثل واحد من أننبرغ الصواني قاعة الطعام، وأيضا أشياء مثل المتغيرات المحلية. إذا ظيفة فو أو المبادلة وظيفة لها المتغيرات المحلية، مثل درجة الحرارة، هذين في نهاية المطاف على المكدس. الآن، نحن لن نتحدث كثيرا عن لهم، ولكن هذه متغيرات البيئة في أسفل رأينا منذ فترة عندما كنت futzing في لوحة المفاتيح يوم واحد وبدأت الوصول إلى الأشياء مثل ARGV 100 أو ARGV 1،000، فقط elements-- أنسى ولكن هذا numbers-- لم يكن من المفترض أن يكون الوصول إليها من قبل لي. بدأنا نشهد بعض حرف غير تقليدي على الشاشة. كانت تلك ما يسمى متغيرات البيئة مثل الإعدادات العمومية لبلدي برنامج أو جهاز الكمبيوتر الخاص بي، وليس لا علاقة لها في الآونة الأخيرة الأخطاء التي ناقشناها، Shellshock، وهذا ما كان التي يعاني منها عدد غير قليل من أجهزة الكمبيوتر. الآن أخيرا، في التركيز اليوم سنكون في نهاية المطاف على الكومة. هذا هو جزء آخر من الذاكرة. وأساسا كل هذا الذاكرة هي نفس الاشياء. انها نفس الأجهزة. نحن مجرد نوع من معالجة مجموعات مختلفة من بايت لأغراض مختلفة. كومة يجري أيضا لتكون حيث المتغيرات والذاكرة التي تطلبها من نظام التشغيل يتم تخزينها مؤقتا. ولكن هناك نوع من مشكلة هنا، كما تشير الصورة. نحن لدينا نوع من اثنين السفن وشك الاصطدام. لأنه كما كنت تستخدم أكثر وأكثر من المكدس، وكما نرى اليوم فصاعدا، كما يمكنك استخدام أكثر وأكثر من كومة، وبالتأكيد أشياء سيئة قد يحدث. وبالفعل، يمكننا أن لحث عن قصد أو عن غير قصد. حتى التشويق الماضي كان الوقت هذا البرنامج، الذي لم يخدم أي ظيفية غرض آخر سوى لإثبات كيف بوصفه الرجل سيئة يمكن أن تتخذ في الواقع الاستفادة من الخلل في البرنامج شخص ما ويتولى برنامج أو حتى نظام الكمبيوتر كله أو الخادم. حتى مجرد لمحة لفترة وجيزة، ل لاحظت أن الرئيسي في أسفل يأخذ في سطر الأوامر الحجج، وفقا ARGV. ولها استدعاء دالة و، أساسا وظيفة مجهول تسمى و، وانها تمر في ARGV [1]. وبغض النظر عن كلمة أنواع المستخدم في في موجه بعد اسم هذا البرنامج، ثم هذه الوظيفة تعسفية تصل أعلى، و، ويأخذ في سلسلة، AKA شار *، كما بدأنا لمناقشة، وتدعو فقط لأنها "شريط". لكننا يمكن أن نسميها أي شيء. وبعد ذلك يعلن، داخل من و، مجموعة من الأحرف تسمى هذه c-- 12 حرفا. الآن، من خلال قصة كنت أقول قبل لحظة، حيث في الذاكرة ج هو، أو هي تلك 12 حرف لن ينتهي؟ مجرد أن تكون واضحة. نعم؟ الجمهور: على المكدس. J. DAVID مالان: في المكدس. لذا c هي متغير محلي. نطلبه 12 حرف أو 12 بايت. تلك هي الذهاب الى نهاية المطاف على ما يسمى المكدس. الآن هي في النهاية هذه وظيفة أخرى هذا هو في الواقع مفيدة جدا، ولكن لدينا لا تستخدم حقا ذلك بأنفسنا، strncopy. فهذا يعني نسخة سلسلة، ولكن ن فقط خطابات، ن حرفا. حتى الأحرف ن سيكون نسخ من شريط في ج. وكم؟ طول العارضة. لذلك وبعبارة أخرى، أن سطر واحد، strncopy، يجري نسخ تمنع بشكل فعال في لج. الآن، فقط لنوع من استباق والمغزى من هذه القصة، ما هو يحتمل أن تكون مشكلة هنا؟ على الرغم من أننا التحقق من طول شريط وتمرير فإنه إلى strncopy، ما أمعائك أقول لك هو لا تزال مقطوعة عن هذا البرنامج؟ نعم؟ الجمهور: لا يشمل غرفة للحرف فارغة. J. DAVID مالان: لا يشمل غرفة للحرف فارغة. يحتمل، خلافا لما حدث في الممارسة الماضية وحتى لا لدينا بقدر ما هو زائد 1 ل استيعاب هذا الطابع فارغة. لكنه أسوأ من ذلك. ماذا نحن فشلها في القيام به؟ نعم؟ الجمهور: [غير مسموع] J. DAVID مالان: الكمال. لقد الثابت ترميز 12 تعسفية جدا. هذا ليس بكثير ل المشكلة، ولكن الحقيقة أننا لا حتى التحقق إذا طول شريط أقل من 12، وفي هذه الحالة ستكون آمنة لوضعها في الذاكرة دعا ج التي قمنا المخصصة. في الواقع، إذا هو مثل شريط 20 حرفا، ويبدو أن هذه الوظيفة لنسخ 20 حرفا من شريط في ج، وبالتالي أخذ 8 بايت على الأقل أنه لا ينبغي أن يكون. هذا هو المعنى الضمني هنا. حتى في برنامج كسر قصيرة. ليس مثل هذه الصفقة الكبيرة. ربما تحصل على خطأ تجزئة. لقد كان كل ما الخلل في البرامج. نحن جميعا قد يكون البق برامج في الوقت الحالي. ولكن ما هي الآثار المترتبة؟ حسنا، هنا نسخة التكبير في ل تلك الصورة من ذاكرة جهاز الكمبيوتر الخاص بي. هذا هو الجزء السفلي من بلدي المكدس. وبالفعل، في أسفل جدا هو ما هو دعا كومة روتيني من الاهالي، الطريق الهوى لقول هذا هو الرئيسي. ذلك أن كل من دعا وظيفة و أننا نتحدث عنه. لذلك هذا هو الجزء السفلي من المكدس. عنوان العودة هو شيء جديد. كان دائما هناك، كان دائما في تلك الصورة. نحن فقط لم الانتباه إلى ذلك. لأنه تبين الطريق ج اعمال أنه عندما تدعو ظيفة بعضها البعض، ليس فقط القيام الحجج على ذلك الحصول على وظيفة دفع إلى المكدس، ليس فقط المحلية والدالة الحصول على المتغيرات دفعت إلى المكدس، ما يسمى عنوان المرسل كما يحصل على وضع إلى المكدس. على وجه التحديد، إذا المكالمات الرئيسية فو، في الرئيسية عنوان الخاص في الذاكرة، ثور شيء، يحصل على وضع فعال إلى المكدس بحيث عندما يتم تنفيذ ذلك و يعرف أين للقفز في العودة إلى النص شريحة من أجل مواصلة تنفيذ. حتى إذا نحن هنا من الناحية النظرية، في الأصل، ثم يحصل دعا جمعة. و كيف نعرف من تسليم السيطرة مرة أخرى؟ حسنا، هذا قليلا التفصيلي باللون الأحمر هنا، دعا على عنوان المرسل، هو فقط الشيكات، ما هو أن عنوان المرسل؟ أوه، اسمحوا لي أن تقفز العودة الى الأصل هنا. وهذا هو قليلا من التبسيط، لأن الأصفار ومنها للرئيسية من الناحية الفنية هنا في قطاع التكنولوجيا. ولكن هذه هي الفكرة. و فقط أن نعرف ما إلى أين يذهب في نهاية المطاف السيطرة الظهر. ولكن الطريقة أجهزة الكمبيوتر وضعت لفترة طويلة من الأمور مثل المتغيرات المحلية و الحجج هي من هذا القبيل. حتى في الجزء العلوي من هذه الصورة في الأزرق هو الإطار المكدس للو، لذلك كل من الذاكرة و هو على وجه التحديد باستخدام. لذلك وفقا لذلك، لاحظ أن شريط هو في هذه الصورة. كان شريط حجتها. ونحن ادعى أن الحجج ل الحصول على وظائف دفع إلى المكدس. وج، بالطبع، هو أيضا في هذه الصورة. وفقط لأغراض تشكيلي، تلاحظ في أعلى الزاوية اليسرى هو ما سيكون ج قوس 0 و ثم انخفض قليلا إلى اليمين هو ج قوس 11. لذلك وبعبارة أخرى، يمكنك أن تتخيل أن هناك شبكة من وحدات البايت هناك، أولها أعلى اليسار، أسفل منها هو آخر من تلك بايت 12. ولكن الآن نحاول أن يصوم إلى الأمام. ما يوشك أن يحدث إذا نحن نمر في حانة سلسلة هذا أطول من ج؟ ونحن لا التحقق إذا انها في الواقع أطول من 12. أي جزء من هذه الصورة هو ذاهب ل الحصول على الكتابة بواسطة بايت 0، 1، 2، 3، نقطة نقطة نقطة، 11، ومن ثم سيئة، 12، 13 إلى 19؟ ما الذي سيحدث هنا، إذا استنتجنا من ترتيب أن ج قوس 0 هو على رأس وج قوس 11 هو نوع من أسفل إلى اليمين؟ نعم؟ الجمهور: حسنا، انه سيكون للكتابة فوق شار * بار. J. DAVID مالان: نعم، يبدو وأنت تسير في الكتابة تشار * بار. والأسوأ من ذلك، إذا كنت ترسل في فترة طويلة حقا سلسلة، حتى أنك قد الكتابة ماذا؟ عنوان العودة. وهو مرة أخرى، هو تماما مثل التفصيلي لقول البرنامج حيث العودة إلى عندما و يتم استدعائه. ذلك ما يفعله الأشرار عادة هو إذا كانت تأتي عبر برنامج انهم الغريب هو ما إذا كان للاستغلال، عربات التي تجرها الدواب في مثل هذه الطريقة أنه أو أنها يمكن أن تتخذ الاستفادة من هذا الخطأ، عموما أنهم لا يحصلون هذا الحق في المرة الأولى. أنها مجرد البدء في إرسال، على سبيل المثال، سلاسل عشوائية في البرنامج، سواء على لوحة المفاتيح، أو بصراحة أنها ربما إرسال برنامج صغير لمجرد تولد سلاسل تلقائيا، وبدء ضجيجا على البرنامج من قبل ارسال في الكثير من المدخلات المختلفة في أطوال مختلفة. بمجرد تعطل البرنامج الخاص بك، هذا شيء مدهش. لأنه يعني أنه أو أنها قد اكتشف ما هو على الارجح في الواقع علة. ومن ثم يمكنهم الحصول على أكثر ذكاء وبدء التركيز أكثر ضيقا حول كيفية استغلال هذا الخطأ. على وجه الخصوص، ما هو أو هي قد القيام به هو إرسال، في أفضل الأحوال، مرحبا. لا صفقة كبيرة. انها سلسلة قصيرة بما فيه الكفاية. ولكن ماذا لو كان هو أو هي يرسل، وسنقوم التعميم أنها، هجوم code-- ذلك الأصفار ومنها أن تفعل أشياء مثل RM-RF، التي تعمل على إزالة كل شيء من القرص الصلب أو إرسال البريد المزعج بطريقة أو بأخرى أو مهاجمة الجهاز؟ حتى إذا كان كل من هذه الحروف A يمثل فقط، من الناحية النظرية، هجوم، هجوم، هجوم، هجوم، بعض سيء أن شخصا ما كتب آخر، ولكن إذا كان هذا الشخص هو ذكي بما فيه الكفاية ليس فقط لتشمل جميع تلك RFS-RM، ولكن أيضا يكون له أو لها مشاركة بايت قليلة يكون الرقم الذي يتوافق إلى عنوان له أو لها شفرة الهجوم الخاصة انه او انها مرت في فقط عن طريق تزويدها في موجه، يمكنك خداع فعال الكمبيوتر في ملاحظة عندما يتم و المنفذة، أوه، لقد حان الوقت بالنسبة لي للقفز العودة إلى عنوان المرسل الأحمر. ولكن لديه أو لديها بطريقة ما تتداخل أن عنوان المرسل مع عدد الخاصة بهم، وانهم ذكي بما فيه الكفاية إلى أن تم تكوينها رقم للإشارة، كما كنت نرى في الجزء العلوي السوبر الزاوية اليسرى هناك، العنوان الفعلي في الكمبيوتر و الذاكرة لبعض من التعليمات البرمجية هجومهم، رجل سيء يمكن خداع الكمبيوتر إلى تنفيذ التعليمات البرمجية حضارته. وهذا الرمز، ومرة ​​أخرى، يمكن أن يكون أي شيء. يسمى عموما كود قذيفة، الذي هو مجرد طريقة للقول أنه ليس عموما شيء بسيط مثل RM-RF. انها في الواقع شيء من هذا القبيل باش، أو برنامج الفعلي الذي يعطيه أو السيطرة عليها البرامجية لتنفيذ أي شيء آخر أنهم يريدون. لذلك باختصار، كل هذا مستمد من حقيقة بسيطة أن هذا الخطأ لا تشارك التدقيق حدود الصفيف الخاص بك. ولأن الطريقة أجهزة الكمبيوتر العمل هو أنها استخدام كومة من على نحو فعال، من الناحية النظرية، أسفل على ما يصل، ولكن بعد ذلك العناصر كنت تدفع إلى المكدس تنمو أعلى إلى أسفل، وهذه مشكلة لا يصدق. الآن، هناك طرق للتغلب على هذه. وبصراحة، هناك لغات التي تعمل معها حول ذلك. جافا المناعي، على سبيل المثال، لهذه المسألة بالذات. لأنها لا تعطيك مؤشرات. أنها لا تعطيك عناوين الذاكرة المباشرة. حتى مع هذه القوة التي لدينا إلى تلمس أي شيء في الذاكرة نريد يأتي، باعتراف الجميع، خطر كبير. حتى تبقي العين. إذا، بصراحة، في الأشهر أو سنوات قادمة، في أي وقت كنت قرأت عن بعض الاستغلال برنامج أو خادم، إذا كنت من أي وقت مضى نرى تلميح من شيء مثل هجوم تجاوز سعة المخزن المؤقت، أو تجاوز سعة مكدس هو نوع آخر من هجوم مماثل من الروح، بقدر يلهم موقع على شبكة الانترنت اسم، إذا كنت تعرف ذلك، انها كل الحديث عن مجرد تفيض حجم بعض الحرف مجموعة أو بعض مجموعة بشكل عام. أي أسئلة، إذن، على هذا؟ لا تحاول ذلك في المنزل. كل الحق. حتى malloc كان حتى الآن لدينا جديد صديق في أننا يمكن تخصيص الذاكرة أننا لا نعرف بالضرورة في التقدم الذي نريده لذلك ليس لدينا إلى رمز الثابت إلى موقعنا أرقام برنامج مثل 12. بمجرد أن يقوم المستخدم يخبرنا كم البيانات انه أو انها تريد المدخلات، يمكننا أن الذاكرة malloc بكثير. malloc ذلك اتضح، ل مدى لقد تم استخدامه، صراحة آخر مرة، ثم تم يا رفاق استخدامه لgetstring تدري ل عدة أسابيع، كل من الذاكرة malloc ل يأتي من ما يسمى كومة. وهذا هو السبب في getstring، على سبيل المثال، يمكن تخصيص ذاكرة حيوي دون معرفة ما كنت سوف اكتب مقدما، تسليم بعودتكم مؤشر إلى أن الذاكرة، وأن الذاكرة ما زالت لك أن تبقي، حتى بعد getstring العوائد. لأن نذكر بعد كل ما كومة يجري باستمرار صعودا وهبوطا، صعودا وهبوطا. وبمجرد أن يذهب أسفل، وهذا يعني أي الذاكرة هذه الوظيفة ينبغي استخدامها لا يتم استخدامها من قبل أي شخص آخر. انها القيم القمامة الآن. ولكن كومة تصل هنا. وما هو لطيف حول malloc هو أن عندما يخصص malloc ذاكرة تصل هنا، انها لا تتأثر، ل جزء الأكبر، من خلال المكدس. وهكذا يمكن الوصول إلى أي وظيفة الذاكرة التي تم malloc'd، حتى من وظيفة مثل getstring، حتى بعد فإنه يتم إرجاعها. الآن، والعكس من malloc مجانا. وبالفعل، فإن القاعدة التي بحاجة للبدء في اعتماد أي، أي، في أي وقت كنت تستخدم malloc يجب استخدام نفسك مجانا، في نهاية المطاف، على أن المؤشر نفسه. كل هذا الوقت كنا الكتابة عربات التي تجرها الدواب، ورمز عربات التي تجرها الدواب، لأسباب عديدة. ولكن واحدة منها كانت باستخدام مكتبة CS50، التي هو نفسه عمدا عربات التي تجرها الدواب، فإنه تسرب الذاكرة. أي وقت كنت قد دعا getstring خلال الأسابيع القليلة الماضية نحن نطلب من التشغيل نظام، لينكس، للذاكرة. وكنت لم تعطى مرة واحدة مرة أخرى. وهذا ليس، في ممارسة، أمر جيد. وValgrind، واحدة من الأدوات التي أدخلت في Pset 4، هو كل شيء عن مساعدتك الآن العثور على البق من هذا القبيل. لكن ومن حسن حظ Pset 4 لا تحتاج لاستخدام المكتبة أو CS50 getstring. لذلك أي البق ذات الصلة الذاكرة هي يذهب في نهاية المطاف أن تكون بنفسك. حتى malloc هو أكثر من مجرد ملائمة لهذا الغرض. يمكننا في الواقع حل الآن مشاكل مختلفة جوهريا، وحل جذري مشاكل أكثر على نحو فعال وفقا لوعد الاسبوع الصفر. حتى الآن هذا هو جاذبية بنية بيانات لقد كان لدينا. وبنية بيانات أنا فقط يعني وسيلة لتصور الذاكرة بطريقة تتجاوز مجرد القول، هذا هو عدد صحيح، وهذا هو شار. يمكننا أن نبدأ لمجموعة الأشياء معا. حتى بدت مجموعة من هذا القبيل. وما كان المفتاح في حوالي مجموعة هو أنه يمنحك ، ظهر إلى ظهر أجزاء من الذاكرة، كل منها سيكون من نفس النوع، وكثافة العمليات، كثافة العمليات، وكثافة العمليات، وكثافة العمليات، أو حرف، حرف، حرف، شار. ولكن هناك عدد قليل من سلبيات. هذا على سبيل المثال، هو مجموعة من حجم ستة. افترض أنك ملء هذه المجموعة برصيد ست أرقام وبعد ذلك، لأي سبب من الأسباب، المستخدم يريد أن يعطي لك عددا السابع. أين وضعه؟ ما هو الحل إذا كان لديك إنشاء مجموعة على المكدس، على سبيل المثال، فقط مع الأسبوع اثنين التدوين التي قدمنا، من الأقواس المعقوفة مع عدد الداخل؟ حسنا، كنت قد حصلت على ستة الأرقام في هذه المربعات. ما يمكن أن غرائزك تكون؟ حيث كنت تريد وضعه؟ الجمهور: [غير مسموع] J. DAVID مالان: عذرا؟ الجمهور: وضعها على النهاية. J. DAVID مالان: وضعه على النهاية. ذلك ما يزيد قليلا إلى اليمين، خارج هذا المربع. الذي من شأنه أن يكون لطيفا، لكنه تبين أنك لا تستطيع أن تفعل ذلك. لأنه إذا كنت لم يطلب هذا جزء من الذاكرة، يمكن أن يكون من قبيل المصادفة أن هذا يتم استخدامه من قبل بعض متغير آخر تماما. بذاكرتي أسبوع أو نحو ذلك عندما وضعنا من أسماء Zamyla ودافين وغابي في الذاكرة. كانوا حرفيا العودة إلى الوراء إلى الوراء. لذلك لا نستطيع بالضرورة نثق أن كل ما في هنا هو متاح بالنسبة لي لاستخدام. لذلك ماذا يمكن أن تفعل؟ حسنا، مرة واحدة كنت تحقيق تحتاج إلى مجموعة من حجم السبعة، هل يمكن أن مجرد خلق مجموعة من حجم سبعة ثم استخدام لحلقة أو حلقة في حين، نسخه إلى مجموعة جديدة، ثم بطريقة أو بأخرى مجرد التخلص من هذه المجموعة أو مجرد التوقف عن استخدامه. ولكن هذا ليس كفاءة خاصة. باختصار، لا تدع صفائف تغيير حجم حيوي. حتى من ناحية تحصل الوصول العشوائي، وهو أمر مدهش. لأنه يتيح لنا القيام بأشياء مثل فرق تسد، البحث الثنائي، والتي قمنا تحدث عن على الشاشة هنا. ولكن يمكنك رسم نفسك في مأزق. بمجرد ضرب نهاية مجموعة الخاصة بك، لديك للقيام جدا عملية مكلفة أو إرسال مجموعة كاملة من التعليمات البرمجية للتعامل مع هذه المشكلة الآن. حتى ما إذا كان لدينا بدلا شيء يسمى قائمة، أو قائمة مرتبطة على وجه الخصوص؟ ماذا لو بدلا من الاضطرار المستطيلات العودة إلى الوراء إلى الوراء، لدينا المستطيلات التي تترك قليلا قليلا من مساحة كبيرة للمناورة بينهما؟ وعلى الرغم من أن رسمتها هذه الصورة أو تكييفها هذه الصورة. من أحد النصوص هنا أن أعود إلى العودة إلى الوراء منظم جدا، في الواقع، واحدة من تلك المستطيلات يمكن أن يكون هنا في الذاكرة. يمكن أن يكون واحد منهم هنا. يمكن أن يكون واحد منهم هنا، أكثر من هنا، وهكذا دواليك. ولكن ماذا لو وضعنا، في هذه الحالة، والسهام التي تصل بطريقة أو بأخرى هذه مستطيلات معا؟ في الواقع، لقد رأيت التقنية تجسيدا للسهم. ما اعتدنا في الآونة الأخيرة الأيام التي، تحت غطاء محرك السيارة، هو ممثل السهم؟ مؤشر، أليس كذلك؟ حتى ما إذا، بدلا من مجرد تخزين الأرقام، مثل 9، 17، 22، 26، 34، ماذا لو أننا لا تخزن سوى عدد لكن مؤشر بجانب كل رقم من هذا القبيل؟ حتى أن الكثير كأنك الخيط الإبرة من خلال مجموعة كاملة من القماش، الأشياء بطريقة أو بأخرى البيع المتلازم معا، يمكن بالمثل نحن مع مؤشرات، و تجسد من قبل السهام هنا، نوع من نسج معا هذه المستطيلات الفردية قبل نحو فعال باستخدام مؤشر بجانب كل عدد أن يشير إلى بعض العدد القادم، أن يشير إلى، بدوره، بعض الرقم التالي؟ لذلك وبعبارة أخرى، ما إذا أردنا فعلا لتنفيذ شيء من هذا القبيل؟ حسنا للأسف، هذه المستطيلات، على الأقل واحد مع 9، 17، 22، وهكذا دواليك، هذه لم تعد الساحات لطيفة مع أرقام احدة. أسفل، مستطيل 9 أدناه، على سبيل المثال، يمثل ما ينبغي يكون المؤشر، 32 بت. الآن، وأنا لست على علم بأي نوع بيانات حتى الآن في C والتي تمنحك ليس فقط عدد صحيح لكن مؤشر تماما. فما هو الحل إذا أردنا لابتكار الإجابة الخاصة بنا إلى هذا؟ نعم؟ الجمهور: [غير مسموع] J. DAVID مالان: ما هذا؟ الجمهور: هيكل جديد. J. DAVID مالان: نعم، فلماذا لا نخلق هيكل جديد، أو في C، البنية؟ رأيناه البنيات قبل، وإذا لفترة وجيزة، حيث تعاملنا مع هيكل طالب مثل هذا، والذي كان له اسم والمنزل. في Pset 3 اندلاع كنت تستخدم ككل مجموعة من GRect structs-- وGOvals ستانفورد التي أنشئت ل معلومات عنقودية معا. فماذا إذا أخذنا هذه الفكرة نفسها من الكلمات الرئيسية "الرموز المميزة ل typedef" و "البنية" وبعد ذلك بعض الاشياء طالب محددة، ويتطور هذا إلى ما يلي: الرموز المميزة ل typedef البنية node-- والعقدة هي مجرد علوم الكمبيوتر عام جدا المدى عن شيء في بنية بيانات، حاوية في بنية بيانات. عقدة أزعم ستكون لدينا ون كثافة العمليات، واضحة تماما، ثم أكثر من ذلك بقليل بغموض، هذا الخط الثاني، العقدة البنية * المقبل. ولكن من الناحية التقنية أقل، ما هو هذا السطر الثاني من التعليمات البرمجية داخل الأقواس المعقوفة؟ نعم؟ الجمهور: [غير مسموع] J. DAVID مالان: و مؤشر إلى عقدة أخرى. حتى باعتراف الجميع، البناء خفي قليلا. ولكن إذا كنت تقرأ حرفيا، هو اسم متغير المقبل. ما هو نوع البيانات الخاصة به؟ انها قليلا مطول هذا الوقت، لكنه من نوع عقدة البنية *. أي وقت رأيناه شيء نجمة، أن يعني انها مؤشر إلى أن نوع البيانات. ذلك هو القادم على ما يبدو مؤشر إلى العقدة البنية. الآن، ما هو عقدة البنية؟ كذلك، لاحظ أن ترى تلك نفس الكلمات في الحق الأعلى. وبالفعل، ترى أيضا كلمة "العقدة" إلى هنا في الجزء السفلي الأيسر. وهذا هو في الواقع مجرد الراحة. لاحظ أن في تعريف طلابنا هناك كلمة "طالب" مرة واحدة فقط. وذلك لأن الطالب كان الكائن يست المرجعي الذاتي. لا يوجد شيء داخل طالبة التي تحتاج للإشارة إلى طالب آخر، persay. قد يكون ذلك نوعا من غريب في العالم الحقيقي. ولكن مع عقدة في ربط قائمة، ونحن نفعل تريد عقدة لتكون مرجعية إلى كائن مماثل. وهكذا تلاحظ التغيير هنا ليس فقط ما هو داخل الأقواس المعقوفة. ولكن نضيف كلمة "عقدة" في الجزء العلوي، فضلا عن إضافته إلى أسفل بدلا من "طالب". وهذه ليست سوى التفاصيل التقنية بحيث، مرة أخرى، بنية البيانات الخاصة بك يمكن أن تكون ذاتية المرجع، بحيث عقدة يمكن أن نشير إلى مثل هذه عقدة أخرى. فما هو هذا نهاية المطاف سوف يعني بالنسبة لنا؟ حسنا، واحد، هذه الاشياء داخل هي محتويات عقدة لدينا. هذا الشيء هنا، أعلى اليمين، هو فقط حتى ذلك، مرة أخرى، يمكننا أن نشير إلى أنفسنا. ثم الاشياء الأبعد، على الرغم من عقدة هو مصطلح جديد، ربما، انها لا تزال في نفس ما طالب و وتحت غطاء محرك السيارة في SPL. لذلك إذا أردنا الآن أن تبدأ تنفيذ هذه القائمة المرتبطة، كيف يمكن أن نترجم شيء من هذا القبيل إلى رمز؟ حسنا، دعونا نرى فقط مثال على البرنامج الذي يستخدم في الواقع قائمة مرتبطة. بين كود التوزيع اليوم هو برنامج يسمى قائمة صفر. وإذا كنت تشغيل هذا أنا خلقت السوبر واجهة المستخدم الرسومية بسيطة واجهة المستخدم الرسومية، لكنها في الحقيقة printf فقط. والآن لقد منحت نفسي القائمة قليلة options-- حذف، إدراج، البحث، وترافيرس. وإنهاء. هذه هي العمليات المشتركة فقط على هيكل البيانات المعروفة باسم القائمة رابط. الآن، يتم الانتقال إلى حذف حذف رقم من القائمة. إدراج يجري لإضافة رقم إلى القائمة. البحث سوف تبدو للحصول على رقم في القائمة. واجتياز هو مجرد وسيلة الهوى من القول، والمشي من خلال القائمة، طباعته، ولكن هذا كل شيء. لا تغييره بأي شكل من الأشكال. لذلك دعونا نحاول هذا. دعونا نمضي قدما واكتب 2. ثم انا ذاهب الى إدراج رقم، ويقول 9. دخول. والآن برنامجي هو فقط مبرمجة لأقول، القائمة الآن 9. الآن، إذا كنت المضي قدما و لا أدخل مرة أخرى، اسمحوا لي المضي قدما وتصغير واكتب في 17. الآن قائمتي 9، ثم 17. إذا كنت تفعل إدراج مرة أخرى، دعونا تخطي واحدة. بدلا من 22، كما في الصورة قمنا تم النظر إلى هنا، اسمحوا لي أن تقفز إلى الأمام وإدراج 26 المقبل. لذلك أنا ذاهب لكتابة 26. والقائمة كما أتوقع. ولكن الآن، فقط لمعرفة ما إذا كان هذا الرمز ستكون مرنة، واسمحوا لي الآن نوع 22، والتي على الأقل من الناحية النظرية، إذا نحن حفظ هذه فرزها، الذي هو في الواقع سيكون هدف آخر في الوقت الراهن، يجب ان تذهب في الفترة بين 17 و 26. لذلك أنا هاهنا. في الواقع، أن يعمل. وحتى الآن اسمحوا لي أن إدراج أخيرا، في الصورة، و34. كل الحق. حتى الآن اسمحوا لي أن تنص على أن حذف وترافيرس وبحث القيام به، في الواقع، والعمل. في الواقع، لو لم تشغيل البحث، دعونا ابحث عن رقم 22، أدخل. وجدت 22. ذلك أن هذا هو ما قائمة برنامج القضاء لا. ولكن ما يحدث في الواقع على أن يطبق هذا؟ حسنا، أولا أود أن يكون، بل و ولدي، ودعا ملف list0.h. وهناك في مكان ما في هذا الخط، والرموز المميزة ل typedef، العقدة البنية، ثم لدي الأقواس المعقوفة، ن الباحث، و ثم struct-- ما هو التعريف؟ عقدة البنية المقبل. لذلك نحن بحاجة النجم. الآن من الناحية الفنية ان نصل الى عادة رسم عليه هنا. قد ترى الكتب المدرسية و المراجع على الانترنت تفعل ذلك هناك. انها معادلة وظيفيا. في الواقع، وهذا هو أكثر قليلا نموذجي. ولكنني سوف تكون متسقة مع ما فعلنا في المرة السابقة وقيام بذلك. ثم أخيرا، وانا ذاهب للقيام بذلك. حتى في ملف رأس في مكان ما، في list0.h اليوم هو هذا التعريف البنية، وربما بعض الأشياء الأخرى. وفي الوقت نفسه هناك في list0c سيكون هناك عدد قليل من الأشياء. ولكن نحن في طريقنا للتو بدء وإنهاء هذا لا. List0.h هو ملف أريد أن تدرج في ملفي C. ثم في مرحلة ما أنا ستكون لدينا كثافة العمليات، الرئيسية، باطلة. ثم انا ذاهب الى لدينا بعض المهام هنا. انا ذاهب أيضا أن يكون لها النموذج، مثل باطلة، والبحث، وكثافة العمليات، ن، والغرض الذي في الحياة هو للبحث عن عنصر. ثم إلى هنا أزعم في كود اليوم، باطلة، والبحث، وكثافة العمليات، ن، لا منقوطة ولكن الأقواس المعقوفة المفتوحة. والآن أريد أن البحث بطريقة أو بأخرى لعنصر في هذه القائمة. ولكن ليس لدينا ما يكفي المعلومات على الشاشة حتى الان. لدي يست في الواقع تمثل القائمة نفسها. حتى طريقة واحدة يمكننا تنفيذ قائمة مرتبطة في برنامج والنوع الأول من تريد أن تفعل شيئا مثل يعلنون قائمة مرتبطة هنا. عن البساطة، وانا ذاهب الى جعل هذا العالمي، على الرغم من أننا في العامه لا ينبغي القيام بذلك كثيرا. ولكنه سوف تبسيط هذا المثال. لذلك أريد أن يعلن قائمة مرتبطة هنا. الآن، كيف يمكن أن أفعل ذلك؟ وهنا صورة لقائمة مرتبطة. وأنا لا حقا تعرف في الوقت الراهن كيف انا ذاهب للذهاب نحو يمثل أشياء كثيرة مع واحد فقط متغير في الذاكرة. لكن بذاكرتي لحظة. كل هذا الوقت لقد كان ل سلاسل، ونحن بعد ذلك كشف النقاب عن أن صفائف الحروف، ونحن بعد ذلك وكشف أن تكون مجرد مؤشر إلى الحرف الأول في مجموعة من الأحرف هذا ما منتهية. ذلك أن المنطق، ومع هذا الصورة نوع من بذر أفكارك، ما تحتاج نكتب فعلا في منطقتنا مدونة لتمثيل قائمة مرتبطة؟ كم من هذه المعلومات نحتاج لالتقاط في التعليمات البرمجية C، وكنت أقول؟ نعم؟ الجمهور: نحن بحاجة إلى مؤشر إلى عقدة. J. DAVID مالان: مؤشر إلى العقدة. على وجه الخصوص، والتي سيكون لديك عقدة الغرائز تكون للحفاظ على مؤشر إلى؟ الجمهور: العقدة الأولى. J. DAVID مالان: نعم، ربما مجرد البداية. وتلاحظ، أول العقدة هي شكل مختلف. انها فقط نصف حجم البنية، لأنها في الواقع مؤشر فقط. ذلك ما يمكنك القيام به حقا هو الإعلان قائمة مرتبطة لتكون من نوع عقدة *. ودعونا ندعو فقط لأول مرة وتهيئة إلى قيمة خالية. لاغية بذلك، مرة أخرى، هو القادمة في الصورة هنا. ليس فقط يستخدم لاغية وكأنها خاصة قيمة مقابل أشياء مثل getstring وmalloc، باطل هو أيضا الصفر المؤشر، لعدم وجود مؤشر، اذا صح التعبير. هذا يعني فقط لا شيء حتى الآن هنا. الآن لأول مرة، أنا يمكن كنت يسمى هذا أي شيء. كان يمكن أن يطلق عليه "قائمة" أو أي عدد من الأشياء الأخرى. ولكن أنا اصفا اياه بانه "أولا" بحيث خطوط هذا الامر مع هذه الصورة. لذلك تماما مثل سلسلة يمكن أن تكون ممثلة مع عنوان أول بايت لها، حتى يمكن قائمة مرتبطة. وسنرى بيانات أخرى تكون ممثلة الهياكل مع مؤشر واحد فقط، 32 بت السهم، مشيرا في العقدة الأولى في هيكل. ولكن الآن دعونا نتوقع مشكلة. إذا أنا تذكر فقط في برنامجي عنوان من العقدة الأولى، الأولى في هذا المستطيل هيكل البيانات، ما كان ليكون الحال عن أفضل تنفيذ بقية قائمتي؟ ما هو تفصيل الرئيسي الذي يجري لضمان يعمل هذا في الواقع؟ و"يعمل فعلا" I يعني، يشبه إلى حد كبير سلسلة، يتيح لنا الانتقال من الحرف الأول في اسم دافين إلى الثانية، إلى الثلث، ل رابعا، حتى النهاية، كيف نعرف عندما نكون في نهاية من قائمة مرتبطة يشبه هذا؟ عندما يكون لاغيا. ولقد تمثل هذا النوع من و مثل مهندس القوة الكهربائية، أسس مع القليل رمز، من نوع ما. ولكن هذا يعني فقط فارغة في هذه الحالة. يمكنك استدراجه أي عدد من الطرق، ولكن هذا الكاتب حدث لاستخدام هذا الرمز هنا. طالما أننا التوتير كل هذه العقد معا، تذكر فقط حيث أول واحد هو، وقتا طويلا كما وضعنا رمز خاص في العقدة الأخيرة جدا في القائمة، وسنستخدم اغية، لأن هذا هو ما لدينا المتاحة لنا، هذه القائمة كاملة. وحتى لو كنت فقط تعطيك مؤشر إلى العنصر الأول، أنت، مبرمج، بالتأكيد يمكن الوصول إلى بقية منه. ولكن دعونا ندع عقولكم يهيمون على وجوههم قليلا، لو لم تكن بالفعل wandered-- تماما ما سيكون وقت تشغيل العثور على أي شيء في هذه القائمة؟ اللعنة، انها يا كبير من ن، وهي ليست سيئة، في الإنصاف. وإنما هو الخطية. لقد تخلت ما ميزة صفائف عن طريق تحريك أكثر نحو هذه الصورة من حيوي المنسوجة معا أو العقد مرتبط؟ لقد تخلت الوصول العشوائي. مجموعة لطيفة ل كل شيء رياضيا هو العودة إلى الوراء إلى العودة إلى الوراء. على الرغم من هذه الصورة. تبدو جميلة، وحتى على الرغم من أنه يبدو هذه العقد متباعدة لطيف على حدة، في واقع أنها يمكن أن تكون في أي مكان. OX1، Ox50، Ox123، Ox99، هذه العقد يمكن أن يكون في أي مكان. بسبب malloc لا تخصيص الذاكرة من كومة، ولكن في أي مكان في الكومة. كنت لا تعرف بالضرورة أنه ستكون العودة إلى الوراء إلى الوراء. وهكذا هذه الصورة في الواقع ل لن تكون هذه جميلة جدا. حتى انها سوف تأخذ قليلا من العمل على تنفيذ هذه المهمة. لذلك دعونا تنفيذ البحث الآن. وسنرى نوع من طريقة ذكية للقيام بذلك. حتى إذا أنا ظيفة البحث و أنا إعطاء متغير، صحيح ن للبحث عن، ولست بحاجة إلى معرفة تركيب جديد ليبحث داخل هيكل هذا وأشار إلى، أن يجد ن. لذلك دعونا نفعل ذلك. لذلك أولا انا ذاهب للذهاب قبل وتعلن عقدة *. وانا ذاهب الى نسميها مؤشر، فقط عن طريق الاتفاقية. وانا ذاهب الى تهيئة إلى أولا. والآن أستطيع أن أفعل ذلك في عدد من الطرق. ولكن انا ذاهب الى اتخاذ نهج مشترك. في حين أن المؤشر لا يساوي لاغية، وهذا جملة صالح. وهذا يعني فقط القيام بما يلي، لذلك طالما أنك لا افتا في شيء. ماذا تريد أن تفعل؟ إذا مؤشر نقطة ن، اسمحوا لي أن أعود إلى ذلك، equals-- يساوي ماذا؟ ما قيمة أنا تبحث عنه؟ ن الفعلية التي تم تمريرها في. حتى هنا ميزة أخرى من C والعديد من اللغات. على الرغم من أن بنية تسمى العقدة لديه ن قيمة وشرعية تماما لدينا أيضا حجة المحلية أو متغير يسمى ن. لأنه حتى نحن، مع العين البشرية، يمكن التمييز ن أن هذا هو المفترض يختلف هذا ن. لأن بناء الجملة مختلفة. كنت قد حصلت على نقطة ومؤشر، في حين أن هذا واحد ليس لديه شيء من هذا القبيل. لذلك هذا هو موافق. وهذا موافق لدعوتهم نفس الأشياء. لو لم تجد هذه، وأنا سوف تريد أن تفعل شيئا كما أعلن أن وجدنا ن. وسنترك أنه نتيجة ل التعليق شبة الكود أو رمز. آخر، وهنا ل الجزء المثير للاهتمام، ما لا أريد أن أفعل إذا كان العقدة الحالية لا يحتوي ن أن ما يهمني؟ كيف يمكنني تحقيق ما يلي؟ إذا إصبعي في اللحظة هو PTR، وانها مشيرا في الوقت ذاته مهما الأول هو لافتا في، كيف أحرك إصبعي إلى العقدة التالية في التعليمات البرمجية؟ حسنا، ما هو التفصيلي نحن سوف اتبع في هذه الحالة؟ الجمهور: [غير مسموع]. J. DAVID مالان: نعم، لذلك القادم. حتى إذا أعود إلى بلدي كود هنا، في الواقع، أنا الذهاب الى المضي قدما ويقول المؤشر، الذي هو مجرد variable-- مؤقتة انها اسم غريب، PTR، ولكن انها مجرد مثل temp-- انا ذاهب الى وضع مؤشر يساوي أيا كان مؤشر is-- ومرة أخرى، هذا سوف يكون عربات التي تجرها الدواب قليلا عن نقطة اللحظات المقبل. وبعبارة أخرى، انا ذاهب الى اتخاذ بلدي إصبع وهذا ما لافتا في هذه العقدة هنا وانا ذاهب الى القول، وانت تعرف ما، نلقي نظرة على الحقل التالي وتحرك إصبعك ل كل ما هو لافتا في. وهذا يحدث ل أكرر، كرر، كرر. ولكن عندما يفعل إصبعي يتوقف عن فعل أي شيء على الإطلاق؟ بمجرد ما سطر من التعليمات البرمجية في ركلات؟ الجمهور: [غير مسموع] J. DAVID مالان: إذا كانت نقطة بينما مؤشر لا تساوي قيمة خالية. في وجهة نظري في بعض إصبع ستكون لافتا في اغية وانا ذاهب لتحقيق هذا هو نهاية هذه القائمة. الآن، وهذا هو قليلا كذبة بيضاء للبساطة. اتضح أنه على الرغم من أننا علمت للتو هذه الرموز نقطة للهياكل، مؤشر ليس البنية. PTR ما هو؟ لمجرد أن يكون أكثر nitpicky. انها مؤشر إلى العقدة. انها ليست العقدة نفسها. إذا لم يكن لدي أي نجم هنا، مؤشر absolutely-- انها عقدة. هذا هو مثل أسبوع واحد إعلان متغير، على الرغم من أن كلمة "عقدة" هي جديدة. ولكن كما في أقرب وقت ونحن نقدم ل نجوم، انها الآن مؤشر إلى العقدة. ولسوء الحظ لا يمكنك استخدام التدوين نقطة للمؤشر. لديك لاستخدام السهم التدوين، والتي، لافت للنظر، هي المرة الأولى أي قطعة من جملة تبدو بديهية. هذا يبدو حرفيا مثل السهم. وهكذا وهذا شيء جيد. وإلى هنا حرفيا يشبه السهم. لذلك أنا أعتقد أن هذا هو la-- أنا لا اعتقد انني الإفراط في ارتكاب here-- I أعتقد أن هذا هو آخر قطعة جديدة من جملة نحن ذاهبون لنرى. ولله الحمد، انها حقا أكثر من ذلك بقليل بديهية. الآن، بالنسبة لأولئك منكم الذين قد تفضل الطريقة القديمة، يمكنك الاستمرار في استخدام التدوين نقطة. ولكن كما في يوم الاثنين المحادثة، علينا أولا تحتاج إلى الذهاب إلى هناك، انتقل إلى أن معالجة، ومن ثم الوصول إلى الميدان. لذلك هذا هو الصحيح أيضا. وبصراحة، وهذا هو قليلا أكثر متحذلق. أنت تقول حرفيا، إلغاء مرجعية مؤشر وتذهب هناك. ثم الاستيلاء .N، ودعا مجال ن. ولكن بصراحة، لا أحد يريد للكتابة أو قراءة هذا. وهكذا اخترع العالم التدوين السهم، الذي ما يعادل، متطابقة، انها السكر النحوي فقط. وذلك على طريقة أخرى للقول هذا تبدو أفضل أو تبدو أكثر بساطة. وحتى الآن أنا ذاهب إلى فعل شيء واحد الآخر. انا ذاهب الى القول "كسر" مرة واحدة لدي وجدت أنه لذلك أنا لا تبقي تبحث عن ذلك. ولكن هذا هو جوهر وظيفة البحث. ولكن من الأسهل كثيرا، في نهاية، وليس على المشي من خلال التعليمات البرمجية. هذا هو في الواقع تنفيذ الرسمي البحث في التعليمات البرمجية التوزيع اليوم. أجرؤ على القول أن إدراج ليس متعة خاصة من خلال المشي بصريا، ولا هو حذف، حتى وإن كان في نهاية اليوم أنها تختزل إلى حد ما الاستدلال بسيطة. لذلك دعونا نفعل ذلك. إذا عليك النكتة لي هنا، لقد فعلت جلب حفنة من الكرات الإجهاد. احضرت مجموعة من الأرقام. ويمكن أن نحصل على مجرد عدد قليل من المتطوعين لتمثل 9، 17، 20، 22، 29، و 34؟ كل ذلك في الأساس الذين هنا اليوم. وهذا واحد، اثنين، ثلاثة، أربعة، خمسة، ستة أشخاص. ولقد طلب مني أن go-- نرى، لا واحد في الجزء الخلفي يثير أيديهم. موافق، واحد، اثنان، ثلاثة، أربعة، five-- اسمحوا لي تحميل balance-- ستة. موافق، ستة تأتي على ما يصل. سنحتاج أشخاص آخرين. جئنا كرات الإجهاد إضافية. وإذا كنت تستطيع، ل مجرد لحظة، خط أنفسكم فقط مثل هذه الصورة هنا. كل الحق. دعونا نرى، ما هو اسمك؟ الجمهور: أندرو. J. DAVID مالان: أندرو، كنت الرقم 9. لطيف لمقابلتك. هنا تذهب. الجمهور: جين. J. DAVID مالان: جين. ديفيد. عدد 17. نعم؟ الجمهور: أنا جوليا. J. DAVID مالان: جوليا، ديفيد. عدد 20. الجمهور: المسيحي. J. DAVID مالان: مسيحي، ديفيد. عدد 22. و؟ الجمهور: JP. J. DAVID مالان: JP. عدد 29. لذلك يذهب قدما والحصول in-- اه اه. اه اه. وضع الاستعداد. 20. هل لديها علامة؟ الجمهور: لقد حصلت على شربي. J. DAVID مالان: حصلت على شربي؟ موافق. وهل لديها قطعة من الورق؟ حفظ المحاضرة. هيا. الجمهور: لقد حصلت عليه. J. DAVID مالان: نحن حصلت عليه؟ كل الحق، شكرا لك. هنا نذهب. كان هذا منك؟ حفظته للتو اليوم. حتى 29. كل الحق. أنا أخطأت 29، ولكن موافق. المضي قدما. حسنا، سأعطيك القلم ظهرك للحظات. لذلك لدينا هؤلاء الناس هنا. دعونا الآخر. غابي، هل تريد أن تلعب العنصر الأول هنا؟ سوف نحتاج منك أن نشير في هؤلاء الناس على ما يرام. حتى 9، 17، 20، 22، نوع من 29، ثم 34. لم نفقد شخص ما؟ لدي 34. حيث did-- OK، الذي يريد أن يكون 34؟ موافق، وتأتي على ما يصل، 34. كل الحق، وهذا سوف يكون تستحق ذروتها. ما اسمك؟ الجمهور: بيتر. J. DAVID مالان: بيتر، وتأتي على ما يصل. كل الحق، لذلك ليس هنا مجموعة كاملة من العقد. كل واحد منكم يمثل الرجال واحد من هذه المستطيلات. وغابي، الغريب قليلا رجل خارج، تمثل أولا. ذلك مؤشر له هو أصغر قليلا على الشاشة من أي شخص آخر. وفي هذه الحالة، كل من يسارك الأيدي سوف نشير إما إلى أسفل، وبالتالي تمثل باطلة، لذلك مجرد غياب مؤشر، أو انها ستكون لافتا في عقدة القادمة لك. حتى الآن إذا كنت تزين أنفسكم مثل الصورة هنا، والمضي قدما ونقطة على بعضهم البعض، مع غابي في إشارة معينة في رقم 9 لتمثيل القائمة. موافق، ورقم 34، يدك اليسرى يجب أن يكون مجرد لافتا في الأرض. حسنا، هذه هي قائمة مرتبطة. لذلك هذا هو السيناريو المذكور. وبالفعل، وهذا هو التمثيل فئة من المشاكل التي قد تحاول حل مع رمز. تريد إدراج في نهاية المطاف عنصر جديد إلى القائمة. في هذه الحالة، نحن ذاهبون ل حاول إدراج رقم 55. ولكن هناك ستكون الحالات المختلفة للنظر فيها. وبالفعل، وهذا سيكون واحد للصورة كبيرة الوجبات السريعة هنا، هو، ما هي الحالات المختلفة. ما هي تختلف إذا كانت الظروف أو الفروع التي قد يكون برنامجك؟ حسنا، الرقم الذي تحاول إدراج، ونحن نعلم الآن أن يكون 55، ولكن إذا كنت لا تعرف مقدما، نحسب يقع في ثلاثة على الأقل الحالات الممكنة. حيث قد يكون عنصرا جديدا؟ الجمهور: والنهاية أو الوسط. J. DAVID مالان: في النهاية، في الوسط أو في البداية. حتى أزعم هناك على الأقل ثلاث مشاكل نحن بحاجة إلى حل. دعونا اختيار ما ربما يمكن القول إن أبسط واحد، حيث العنصر الجديد ينتمي في البداية. لذلك أنا ذاهب لديك رمز تماما مثل البحث الذي كتبته فقط. وانا ذاهب لPTR، التي أنا أمثل هنا مع إصبعي، كالمعتاد. وتذكر، ما قيمة وصلنا إلى تهيئة PTR؟ لذلك نحن لتهيئة فارغة في البداية. ولكن بعد ذلك ماذا نفعل عندما و كانت وظيفة داخل بحثنا؟ نحن تعيينها يساوي أولا، الذي لا يعني القيام بذلك. إذا أنا وضعت PTR يساوي أولا، ما يجب أن يكون حقا يدي لافتا في؟ الحق. حتى إذا غابي وأنا ذاهب أن تكون القيم متساوية هنا، نحن بحاجة إلى كل نقطة في المركز 9. لذلك كان هذا بداية قصتنا. والآن هذا هو مجرد واضحة، على الرغم من أن بناء الجملة الجديد. هذا المفهوم هو البحث الخطي فقط. هو 55 يساوي 9؟ أو بالأحرى، دعونا نقول أقل من 9. لأنني أحاول أن معرفة أين يضع 55. أقل من 9، أي أقل من 17، أقل من 20، أقل من 22، أقل من 29، أقل من 34، لا. حتى الآن نحن في حالة واحد من ثلاثة على الأقل. إذا كنت ترغب في إدراج 55 أكثر من هنا، ما الأسطر من التعليمات البرمجية الحاجة للحصول على تنفيذها؟ كيف هذا صورة البشر بحاجة إلى تغيير؟ ماذا أفعل بيدي اليسرى؟ هذا ينبغي أن يكون لاغيا في البداية، لأنني في نهاية القائمة. وماذا يجب أن يحدث هنا مع بيتر، كان ذلك؟ من الواضح انه ذاهب للإشارة إلى لي. حتى أزعم هناك اثنين على الأقل من خطوط من التعليمات البرمجية في نموذج التعليمات البرمجية من اليوم ما يجري لتنفيذ هذه سيناريو مضيفا 55 في الذيل. ويمكن أن لدي الهيب شخص صعودا وتمثل فقط 55؟ كل الحق، أنتم 55 الجديد. وحتى الآن ما إذا كان المقبل السيناريو يأتي على طول، ونحن نريد أن تدرج في بداية أو رأس هذه القائمة؟ وما هو اسمك، ورقم 55؟ الجمهور: جاك. J. DAVID مالان: جاك؟ حسنا، لطيف لمقابلتك. مرحبا بكم على متن. حتى الآن نحن في طريقنا لل إدراج، فلنقل، عدد 5. هنا الحالة الثانية لل ثلاثة توصلنا مع قبل. حتى إذا كان ينتمي 5 في البداية، دعونا نرى كيف نجد أن بها. أنا تهيئة بلدي PTR مؤشر لعدد 9 مرة أخرى. وأدركت، أوه، 5 هو أقل من 9. حتى إصلاح هذه الصورة بالنسبة لنا. الذي يدين، وغابي أو ديفيد or-- ما اسمك رقم 9 ل؟ الجمهور: جين. J. DAVID مالان: hands-- جين أي من أيدينا تحتاج إلى تغيير؟ حسنا، غابي يشير إلى ما الآن؟ في وجهي. أنا عقدة جديدة. ولذا فإنني سوف مجرد نوع من التحرك هنا لرؤيتها بصريا. وفي الوقت نفسه ما يمكنني أن أشير؟ حيث لا يزال أنا افتا. حتى هذا كل شيء. حتى مجرد حقا سطر واحد من إصلاحات مدونة هذه المسألة بالذات، على ما يبدو. كل الحق، لذلك وهذا جيد. ويمكن للشخص أن يكون نائبا لل5؟ تأتي على ما يصل. ونحن سوف تحصل في المرة القادمة. كل الحق، لذلك now-- و بوصفها جانبا، وأسماء أنا لا يجعل نصا صريحا بحق الآن، مؤشر PRED، مؤشر سلفه والمؤشر الجديد، وهذا مجرد أسماء معينة في نموذج التعليمة البرمجية للمؤشرات أو يدي هذا نوع من الإشارة حولها. ما اسمك؟ الجمهور: كريستين. J. DAVID مالان: كريستين. مرحبا بكم على متن. كل الحق، لذلك دعونا ننظر الآن سيناريو أكثر قليلا مزعج، حيث أريد أن إدراج شيء من هذا القبيل 26 في هذا. 20؟ ماذا؟ هذه are-- شيء جيد لدينا هذا القلم. كل الحق، 20. اذا كان شخص ما يمكن أن تحصل على قطعة أخرى من ورقة جاهزة، فقط في case-- كل الحق. أوه، مثيرة للاهتمام. حسنا هذا مثال لوجود خطأ المحاضرة. OK حتى ما اسمك مرة أخرى؟ الجمهور: جوليا. J. DAVID مالان: جوليا، يمكنك البوب خروج والتظاهر كنت لم تكن هناك؟ حسنا، هذا لم يحدث أبدا. شكرا لك. لذلك لنفترض أننا نريد إدراج جوليا في هذه القائمة المرتبطة. وهي رقم 20. وبالطبع انها سوف تنتمي في begin-- لا تشير في أي شيء حتى الان. حتى يدك يمكن أن يكون نوع من لاغية أسفل أو بعض قيمة القمامة. دعونا نقول للقصة سريعة. أنا لافتا في عدد 5 هذا الوقت. ثم أتحقق 9. ثم أتحقق 17. ثم أتحقق 22. وأنا أدرك، أوه، جوليا يحتاج للذهاب قبل 22. وذلك ما يجب أن يحدث؟ الذي يمسك بحاجة إلى تغيير؟ جوليا، والألغام، or-- ما اسمك مرة أخرى؟ الجمهور: المسيحي. J. DAVID مالان: مسيحي أو؟ الجمهور: اندي. J. DAVID مالان: اندي. مسيحي أو اندي؟ أندي يحتاج إلى نقطة في؟ جوليا. كل الحق. حتى اندي، هل أريد أن أشير في جوليا؟ ولكن انتظر لحظة. في القصة حتى الآن، أنا من النوع واحد المسؤول، بمعنى أن المؤشر هو الشيء هذا تتحرك من خلال القائمة. قد يكون لدينا اسم لاندي، ولكن ليس هناك متغير يسمى اندي. المتغير الآخر الوحيد لدينا هو أولا، من الذي يمثله غابي. لذلك هذا هو في الواقع لماذا هكذا حتى الآن ليس لدينا حاجة إليها. ولكن الآن على الشاشة هناك نذكر مرة أخرى من مؤشر PRED. لذلك اسمحوا لي أن أكون أكثر وضوحا. إذا كان هذا هو المؤشر، كان لي أفضل الحصول على أكثر من ذلك بقليل ذكاء عن بلدي التكرار. إذا كنت لا تمانع ذهابي من هنا مرة أخرى، لافتا هنا، لافتا هنا. ولكن اسمحوا لي أن يكون مؤشر PRED، مؤشر السلف، وهذا نوع من افتا في كنت مجرد عنصر في. حتى عندما أذهب هنا، والآن بلدي التحديثات اليد اليسرى. عندما أذهب هنا بلدي التحديثات اليد اليسرى. والآن لدي ليس فقط مؤشر إلى العنصر الذي يذهب بعد جوليا، لا يزال لدي مؤشر إلى أندي، العنصر من قبل. ولذلك عليك الوصول، أساسا، فتات الخبز، اذا صح التعبير، لجميع المؤشرات المطلوبة. حتى لو كنت أنا لافتا في أندي وانا مشيرا أيضا في المسيحية، الذي يمسك يجب الآن أن أشار في مكان آخر؟ حتى اندي يمكن أن نشير الآن إلى جوليا. جوليا يمكن أن نشير الآن إلى المسيحية. لأنها يمكن نسخ بلدي مؤشر اليد اليمنى ل. والذي يضع بشكل فعال لك العودة الى هذا المكان هنا. هكذا وباختصار، على الرغم من هذا وتدفعنا إلى الأبد نوع من لتحديث الواقع قائمة مرتبطة، وتحقيق ان عمليات هي بسيطة نسبيا. انها واحد، اثنان، ثلاثة الأسطر من التعليمات البرمجية في نهاية المطاف. لكن ملفوفة حول تلك الأسطر من التعليمات البرمجية يفترض قليلا من المنطق أن فعال يسأل السؤال، أين نحن؟ نحن في البداية، منتصف أو نهاية؟ الآن، هناك بالتأكيد بعض الآخر عمليات أننا قد تنفيذها. وهذه الصور هنا تصور فقط ما فعلناه للتو مع البشر. ماذا عن إزالة؟ إذا أردت، على سبيل المثال، إزالة عدد 34 أو 55، كنت قد يكون نفس النوع من التعليمات البرمجية، ولكن انا ذاهب الى حاجة واحدة أو خطوتين. لأن ما هو الجديد؟ إذا يمكنني إزالة شخص ما في النهاية، مثل رقم 55 ثم 34، ما لديها لتغيير كما أفعل أنا ذلك؟ لا بد لي من لا evict-- ما اسمك مرة أخرى؟ الجمهور: جاك. J. DAVID مالان: جاك. لدي ليس فقط evict-- مجانا جاك، لذلك حرفيا دعوة مجانية جاك، أو على الأقل المؤشر هناك أيضا، ولكن الآن ما يحتاج إلى تغيير مع بيتر؟ يده بداية أفضل لافتا إلى أسفل. لأنه بمجرد أن الكلمة الحرة على جاك، إذا بطرس لا يزال لافتا في جاك وأنا بالتالي الحفاظ عبور قائمة وصول هذا المؤشر، وذلك عندما لدينا صديق القديمة تجزئة خطأ قد ركلة في الواقع. لأننا نظرا ل الذاكرة مرة أخرى إلى جاك. يمكنك البقاء هناك برعونة لمجرد لحظة. لأن لدينا بضع عمليات النهائية للنظر فيها. إزالة رأس القائمة، أو beginning-- وهذا واحد مزعج قليلا. لأننا يجب أن نعرف أن غابي هو نوع من خاص في هذا البرنامج. لأنه في الواقع، لديه مؤشر بلده. ليس فقط أن أشار في، ويكاد الجميع هنا. لذلك عندما رأس القائمة هو إزالتها، التي تحتاج إلى تغيير الآن الأيدي؟ ما اسمك مرة أخرى؟ الجمهور: كريستين. J. DAVID مالان: أنا فظيعة في الأسماء، على ما يبدو. حتى كريستين وغابي، التي تحتاج إلى تغيير اليدين عندما نحاول إزالة كريستين، رقم 5، من الصورة؟ موافق، لذلك دعونا نفعل غابي. يجري غابي إلى نقطة، ويفترض، في عدد 9. ولكن ماذا بعد يجب أن يحدث؟ الجمهور: كريستين ينبغي لاغية (غير مسموع). J. DAVID مالان: حسنا، ربما ينبغي لنا أن make-- سمعت "لاغية" في مكان ما. الجمهور: فارغة وخالية لها. J. DAVID مالان: باطل ماذا؟ الجمهور: فارغة وخالية لها. J. DAVID مالان: باطل ولها مجانا. لذلك هذا هو السهل جدا. وانها مثالية أنك الآن نوع من يقف هناك، وليس الانتماء. لأنك قد تم فصله من القائمة. كنت قد تم على نحو فعال اليتامى من القائمة. وهكذا كنا ندعو أفضل مجانا الآن على كريستين لإعطاء تلك الذاكرة إلى الوراء. إلا أننا في كل مرة حذف عقدة من القائمة يمكن نحن جعل القائمة أقصر، ولكن ليس في الواقع انخفاض الحجم في الذاكرة. وحتى إذا ما واصلنا إضافة و مضيفا، إضافة أشياء إلى القائمة، قد تحصل على جهاز الكمبيوتر الخاص بي أبطأ وأبطأ وأبطأ، لأنني نفاد الذاكرة، حتى إذا لم أكن في الواقع باستخدام بايت كريستين من الذاكرة بعد الآن. حتى في نهاية المطاف هناك أخرى سيناريوهات، لإزالة course-- في الوسط، وإزالة في النهاية، كما رأينا. ولكن أكثر إثارة للاهتمام التحدي الآن سيكون للنظر بالضبط ما هو وقت التشغيل. وذلك ليس فقط يمكنك ابق قطعة من الورق، إذا، غابي، وكنت لا تمانع في منح الجميع الكرة الإجهاد. شكرا جزيلا لقائمة مرتبطة لدينا لكم المتطوعين هنا، إذا كنت تستطيع. [تصفيق] J. DAVID مالان: حسنا. حتى بضعة تحليلية الأسئلة ثم، إذا استطعت. لقد رأينا هذه الرموز من قبل، يا كبير وأوميغا، الحدود العليا والسفلى حدود على تشغيل بعض الوقت من الخوارزمية. لذلك دعونا النظر فقط بضعة أسئلة. واحد، وقلنا ذلك قبل، ما هو على التوالي زمن البحث عن القائمة من حيث يا كبير؟ ما هو الحد الأعلى على التوالي الوقت من البحث قائمة مرتبطة كما نفذت من قبل متطوعين لدينا هنا؟ انها يا كبير من ن، الخطية. لأنه في أسوأ الحالات، العنصر، مثل 55، قد نبحث عنه قد يكون فيها كان جاك، وصولا في نهاية المطاف. ولسوء الحظ، على عكس مجموعة لا يمكننا الحصول على يتوهم هذا الوقت. على الرغم من كل البشر كانت لدينا فرزها من عناصر صغيرة، 5، كل وسيلة تصل إلى العنصر أكبر، 55، وهذا عادة ما يكون شيئا جيدا. ولكن ماذا يفعل هذا الافتراض لم تعد تسمح لنا أن نفعل؟ الجمهور: [غير مسموع] J. DAVID مالان: قل مرة أخرى؟ الجمهور: الوصول العشوائي. J. DAVID مالان: الوصول العشوائي. وبالتالي هذا يعني أننا لا يمكن ل يعد استخدام الأصفار ضعيفة، والحدس، والبداهة استخدام ثنائي بحث وفرق تسد. لأنه على الرغم من أننا يمكن البشر من الواضح نرى أن آندي كانت أو مسيحية تقريبا في منتصف القائمة، نعرف فقط أنه نتيجة ل الكمبيوتر القشط قائمة منذ البداية. لذلك قمنا تخلت أن الوصول العشوائي. O كبيرة جدا ن الآن العلوية ملزمة في وقتنا البحث. ماذا عن أوميغا من بحثنا؟ ما هو الأدنى على البحث لبعض العدد في هذه القائمة؟ الجمهور: [غير مسموع] J. DAVID مالان: قل مرة أخرى؟ إستماع: واحد. J. DAVID مالان: واحد. وقت ثابت ذلك. في أفضل الأحوال، كريستين هو بالفعل في بداية القائمة. ونحن نبحث عن رقم 5، لذلك وجدنا لها. لذلك لا صفقة كبيرة. ولكن انها حصلت على أن يكون في بداية القائمة في هذه الحالة. ماذا عن شيء مثل حذف؟ ما إذا كنت تريد حذف عنصر؟ ما هو الحد الأعلى والأدنى على حذف شيء من صلة القائمة؟ الجمهور: [غير مسموع] J. DAVID مالان: قل مرة أخرى؟ الجمهور: ن. J. DAVID مالان: n غير في الواقع الحد الأعلى. لأنه في أسوأ الحالات ونحن نحاول لحذف جاك، كما فعلنا للتو. انه على طول الطريق في نهاية المطاف. يأخذنا إلى الأبد، أو ن الخطوات للعثور عليه. ولهذا على الحد الأعلى. هذا هو الخطية، بالتأكيد. وأفضل حالة تشغيل الوقت، أو الحدود الدنيا في أفضل الأحوال سيكون وقت ثابت. لأنه ربما نحاول حذف كريستين، ونحن مجرد الحصول على محظوظ انها في البداية. الآن انتظر لحظة. وكان غابي أيضا في البداية، وكان لدينا أيضا لتحديث غابي. بحيث لم يكن خطوة واحدة فقط. ذلك هو الواقع المستمر الوقت، في أفضل الأحوال، لإزالة أصغر عنصر؟ هو، على الرغم من أنه قد يكون من اثنين، ثلاثة، أو حتى 100 خطوط للقانون، اذا كان نفس العدد من خطوط، وليس في بعض حلقة، ومستقلة عن حجم من القائمة، تماما. حذف عنصر في في بداية القائمة، حتى لو كان علينا أن نتعامل مع غابي، لا يزال الوقت المستمر. ولذلك فإن هذا يبدو وكأنه خطوة كبيرة إلى الوراء. وما مضيعة للوقت إذا، في أسبوع واحد والاسبوع الصفر كان لدينا ليس فقط كود شبة الكود لكن الرمز الفعلي لتنفيذ شيء وهذا السجل ن قاعدة، أو تسجيل، بالأحرى، ن، قاعدة 2، من حيث وقتها التوالي. فلماذا هيك كنا نريد أن تبدأ باستخدام ما يشبه قائمة مرتبطة؟ نعم. الجمهور: لذا يمكنك إضافة عناصر المصفوفة. J. DAVID مالان: حتى تتمكن من إضافة عناصر إلى الصفيف. وهذا هو أيضا الموضوعي. وسوف نستمر في رؤية هذا، وهذه المفاضلة، والكثير كما شهدنا مفاضلة مع دمج النوع. نحن يمكن تسريع حقا البحث أو الفرز، وبدلا من ذلك، إذا كان لنا أن تنفق مساحة أكبر قليلا و لها قطعة إضافية من الذاكرة أو صفيف لدمج النوع. لكن ننفق أكثر الفضاء، ولكننا توفيرا للوقت. في هذه الحالة، نحن التخلي عن الوقت ولكن نحن اكتساب المرونة، الدينامية اذا صح التعبير، والتي يمكن القول ميزة إيجابية. نحن ننفق أيضا الفضاء. بأي معنى هو مرتبط قائمة أغلى من حيث المساحة من صفيف؟ حيث مساحة إضافية قادمة من؟ نعم؟ الجمهور: [غير مسموع] مؤشر. J. DAVID مالان: نعم، نحن أيضا المؤشر. لذلك هذا هو مزعج minorly في هذا لم أعد أنا فقط تخزين عدد صحيح لتمثيل عدد صحيح. أنا تخزين عدد صحيح و المؤشر، الذي هو أيضا 32 بت. لذلك أنا مضاعفة حرفيا مقدار المساحة المعنية. لذلك هذا هو مفاضلة، ولكن هذا في حالة كثافة العمليات. لنفترض أنك لا تخزين كثافة العمليات، ولكن لنفترض كل من هذه المستطيلات أو كل من هذه البشر كان يمثل كلمة واحدة، وهي الكلمة الإنجليزية التي قد يكون من خمسة أحرف، 10 حرفا، وربما حتى أكثر من ذلك. ثم إضافة 32 فقط أكثر من بت قد يكون أقل من صفقة كبيرة. ماذا لو كان كل من الطلاب في التظاهرة كانت حرفيا البنيات الطلابية التي لها أسماء والمنازل وربما أرقام الهاتف وتويتر يعالج وما شابه ذلك. لذلك كل من الحقول بدأنا الحديث عن اليوم الآخر، أقل بكثير من صفقة كبيرة و العقد لدينا الحصول على أكثر إثارة للاهتمام وكبيرة لقضاء، إيه، إضافي مؤشر فقط لربطها معا. ولكن في الواقع، انها مفاضلة. والواقع، هو رمز أكثر تعقيدا، كما عليك نرى من خلال القشط هذا المثال معين. ولكن ماذا لو كان هناك بعض الكأس المقدسة هنا. ماذا لو لم نتخذ خطوة ولكن إلى الوراء خطوة هائلة إلى الأمام وتنفيذ البيانات عبر هيكل الذي نحن يمكن العثور على عناصر مثل جاك أو كريستين أو أي عناصر أخرى في هذه المجموعة في الوقت الحقيقي المستمر؟ البحث هو ثابت. حذف غير ثابت. إدراج ثابت. كل هذه العمليات مستمرة. ومن شأن ذلك أن يكون لدينا الكأس المقدسة. وهذا هو المكان الذي نحن سوف تلتقط في المرة القادمة. ثم انظر اليكم.