[Powered by Google Translate] [الأسبوع 6] [ديفيد J. مالان] [جامعة هارفارد] [هذا CS50.] [CS50.TV] هذا هو CS50، وهذا هو بداية الأسبوع 6، حتى بضع أدوات جديدة متاحة الآن بالنسبة لك للاستفادة من، يسمى الأول منها CS50 نمط. الاحتمالات هي إذا كنت مثلي أو أي من الزملاء التدريس، ربما كنت قد رأيت برنامج يعكس أسلوبه يبدو شيئا قليلا من هذا القبيل. ربما كنت بدء خفض بعض الزوايا في وقت متأخر من الليل، أو عليك التعامل معها في وقت لاحق، وبعد ذلك TF أو CA يأتي أكثر خلال ساعات الدوام. ثم انه من الصعب بالنسبة لنا للقراءة. حسنا، هذا الرمز صحيحة من حيث التركيب، وتجميع، وسوف، وسوف تشغيل بالفعل. ولكن هذا بالتأكيد ليس 5 لأسلوب. ولكن الآن، إذا ذهبنا إلى هذا الدليل هنا، وتلاحظ أن لدي conditions2.c- وأنا تشغيل هذا الأمر جديد، style50، على هذا conditions2.c الملف، أدخل، لاحظت هذا ما أبلغت لي أنه كان بأسلوب منمق. لاحظت Gedit أنه تم تغيير الملف على القرص، وإذا كنت فوق تحديث، والآن كل المشاكل الآلي الخاص بك. [تصفيق] هذا واحد من الأشياء فعلنا في نهاية هذا الاسبوع. ندرك أنه من الكمال لأن هناك بعض التعليمات البرمجية أنه ببساطة لن تكون قادرة على أسلب تماما، ولكن تحقيق هذا هو الآن أداة يمكنك الاستفادة من إلا إذا كان لترتيب بعض من الأقواس ومجعد أكثر errantly وضع وما شابه ذلك. ولكن أكثر إلحاحا الآن CS50 تحقق. مع CS50 تحقق، يمكنك تنفيذ الاختبارات في الواقع نفس صحة على التعليمات البرمجية الخاصة بك أن الزملاء التدريس قادرة على. هذا هو أداة سطر الأوامر التي تأتي الآن في الأجهزة بمجرد قيام update50 وفقا pset 4 مواصفات، واستخدامه أساسا من هذا القبيل. تشغيل check50 الأمر. ثم يمكنك تمرير في وسيطة سطر الأوامر، أو بصورة أعم يعرف باسم التبديل أو العلم و. عموما، وتسمى الأشياء التي لديها مفتاح الواصلات إلى أمر برنامج الخط، ما يحدد ج والاختبارات التي تريد تشغيلها. يتم تحديد الاختبارات التي تريد تشغيلها بشكل فريد من هذه السلسلة، 2012/pset4/resize. وبعبارة أخرى، هذا مجرد سلسلة فريدة من نوعها ولكن التعسفي التي نستخدمها لتحديد فريد اختبارات صحة و4 pset. ثم قمت بتحديد قائمة الفضائية فصل من الملفات التي تريد تحميلها لCS50 تحقق للتحليل. على سبيل المثال، إذا ذهبت إلى بلدي الحل هنا لresize.c- اسمحوا لي أن تفتح أكبر محطة نافذة وأنا المضي قدما وتشغيل دعنا نقول check50-C 2012/pset4/resize، وبعد ذلك المضي قدما وتحديد أسماء الملفات، resize.c، ثم ضرب أدخل، فإنه يضغط، ذلك تحميل، فإنه يتحقق، وأنا فشلت تماما في مجمله مجموعة من الاختبارات. واحد باللون الأحمر في أعلى اليسار ويقول ان resize.c BMP موجود. كان ذلك الاختبار. هو أن السؤال الذي طلب منها ذلك. وانها غير سعيدة لأن الجواب غير صحيح. النص أدناه بيضاء تقول المتوقع bmp.h في الوجود، وهذا هو ببساطة خطأي. لقد نسيت لتحميله، لذلك لست بحاجة لتحميل كل الملفات، resize.c وbmp.h. ولكن لاحظ الآن كافة الاختبارات الأخرى هي باللون الأصفر لأنها لا تعمل، وهكذا وجه مبتسم رأسيا لانه سعيد ولا حزين، ولكن لدينا لمعالجة هذه المسألة في الحمراء قبل تلك الشيكات الأخرى سيتم تشغيل. اسمحوا لي أن إصلاح هذه. اسمحوا لي التصغير ثم أعد تشغيل هذا، وهذه المرة مع bmp.h أيضا على سطر الأوامر، أدخل، والآن إذا سارت الامور بشكل جيد، انه سيكون للتحقق ومن ثم العودة نتيجة ل-عقد نفسا الخاص بك جميع الخضراء، وهو ما يعني أنا على ما يرام حقا على pset 4 حتى الآن. يمكنك ان ترى ويستنتج من نص وصفي هنا بالضبط ما هو عليه تم اختبار. اختبار علينا أولا لا وجود الملفات؟ ثم تم اختبار الترجمة resize.c لا؟ اختبار فإننا لا لا تغيير حجم BMP-1X1 بكسل عندما ن، عامل تغيير الحجم، هو 1. الآن، إذا كان لديك أي فكرة عما هو ن، سوف يغوص بمجرد pset 4، ولكن هذا هو مجرد التعقل تحقق للتأكد من أنك لا تغيير حجم صورة على الإطلاق إذا كان عامل تغيير الحجم هو 1. إذا، على النقيض من ذلك، فإنه تغيير حجم بكسل 1X1 إلى BMP بكسل 1X1 2X2 بشكل صحيح إلى عندما n هو 2، ثم على نحو مماثل، تشكل الألغام وفقا لذلك. باختصار، هذا هو المقصود ل، واحد، واتخاذ عبور الأصابع من المعادلة الحق قبل أن تقدم pset الخاص بك. وسوف تعرف بالضبط ما TF الخاص بك وسوف نعرف قريبا عندما تذهب عن تقديم بعض هذه المجموعات المشكلة، وأيضا الدافع التربوية في الحقيقة لوضع الفرصة أمامك بحيث عندما تعلم مسبقا أن هناك أخطاء في التعليمات البرمجية والاختبارات التي لا يتم تمريرها، يمكنك وضع في وقت أكثر فعالية في خط الهجوم من أجل حل هذه المشاكل بدلا من فقدان النقاط، والحصول على التغذية المرتدة من TF الخاص بك، ثم انتقل، "آه،" وكأنني يجب أن برزت إلى ذلك. الآن على الأقل هناك أداة لمساعدتك في الحصول على ذلك. انها لن نشير إلى حيث هو علة، ولكن سوف اقول لكم ما هي أعراض منها. ندرك الآن أن الاختبارات الطبية غير يست شاملة بالضرورة. فقط لأنك تحصل على كامل الشاشة من الوجوه المبتسمة الخضراء لا يعني التعليمات البرمجية على ما يرام، ولكن لا يعني ذلك الذي مضى عليه بعض الاختبارات التي يحددها المواصفات. في بعض الأحيان ونحن لن تفرج الشيكات. على سبيل المثال، المجرم، واحدة من جوانب pset 4، هو نوع من خيبة الأمل إذا كنا تعطيك الجواب على ما هو عليه، وهناك عدد من الطرق للكشف عن من هو الشخص في أن الضوضاء الحمراء. فإن تحديد المواصفات دائما في المستقبل للفصاعدا 5 pset ما يتحقق وجود لك. ستلاحظ هناك هذا URL الأبيض في الأسفل. في الوقت الراهن، وهذا هو الإخراج فقط التشخيص. إذا قمت بزيارة هذا العنوان، وستحصل على مجموعة كاملة من الرسائل، مجنون خفي ان كنت موضع ترحيب لننظر من خلال، ولكن في الغالب لموظفي حتى نتمكن من تشخيص وتصحيح الخلل في check50 نفسها. دون اللغط، دعونا ننتقل إلى حيث توقفنا. CS50 مكتبة اتخذنا من المسلمات لبضعة أسابيع، ولكن بعد ذلك في الأسبوع الماضي، بدأنا تقشير مرة أخرى واحدة من طبقات من ذلك. بدأنا نضع جانبا سلسلة لصالح ما بدلا من ذلك؟ [الطلاب] شار. * شار، الذي كان شار * كل هذا الوقت، ولكن الآن ليس لدينا التظاهر أنه من نوع بيانات سلسلة الفعلية. بدلا من ذلك، انها كانت مرادفا من نوع ما ل* شار، وسلسلة هو سلسلة من الأحرف، فلماذا لا يكون من المنطقي أن تمثل السلاسل كما شار * ق؟ * ما هي وظيفة شار تمثل في سياق هذا المفهوم من سلسلة؟ نعم. >> [طالب] الحرف الأول. جيد، الحرف الأول، ولكن ليس تماما الحرف الأول. انها-[طلاب] العنوان. جيد، عنوان الحرف الأول. كل ما هو ضروري لتمثيل سلسلة في الذاكرة للكمبيوتر هو مجرد عنوان فريد من البايت الأول جدا. أنت لا تملك حتى أن تعرف كم من الوقت هو لأن كيف يمكنك هذا الرقم بشكل حيوي؟ [طالب] طول السلسلة. يمكنك استدعاء طول السلسلة، ممتازة، ولكن كيف العمل طول السلسلة؟ ماذا يفعل؟ نعم. [طالب] إستمر ​​حتى تحصل على حرف فارغة. نعم، بالضبط، فإنه يكرر فقط مع لحلقة، في حين حلقة، أيا كان من * الى النهاية، والنهاية يتم تمثيل بواسطة \ 0، الحرف يسمى NUL، NUL، وينبغي عدم الخلط مع NULL، وهو مؤشر، والتي تأتي في المحادثة مرة أخرى اليوم. مقشر عدنا طبقة من GetInt، ومن ثم اتخذنا نظرة على GetString، ويذكر أن كلا من هذه الوظائف، أو حقا، GetString، وكان استخدام وظيفة معينة تحليل الواقع، وهذا هو، وقراءة أو تحليل، ومدخلات المستخدم. وماذا كان ذلك وظيفة جديدة؟ Scanf أو sscanf. يتعلق الأمر في الواقع في النكهات مختلفة قليلة. هناك scanf، وهناك sscanf، وهناك fscanf. في الوقت الراهن، على الرغم من، دعونا نركز على واحد أكثر سهولة مصورة، واسمحوا لي أن تمضي قدما وفتح في الجهاز ملف مثل هذا، scanf1.c. هذا هو برنامج سوبر بسيطة، ولكن هذا لا شيء بعد أن قمنا لم تفعل دون مساعدة من مكتبة CS50. هذا يحصل على الباحث من مستخدم. كيف يعمل؟ حسنا، في السطر 16 هناك، تلاحظ أن نعلن الأشعة الباحث ودعا، وعند هذه النقطة في القصة، ما هي قيمة س؟ [رد الطالب غير مسموع] [ديفيد M.] الحق، من يدري، ربما بعض القيمة القمامة، وذلك في 17، نقول فقط للمستخدم أعطني عدد، من فضلك، والخطوة 18 هي المكان الذي تحصل عليه للاهتمام. Scanf يبدو أن الاقتراض فكرة من printf لأنه يستخدم هذه الرموز تنسيق تهمك. د٪ هو بالطبع رقم عشري. ولكن لماذا أنا في تمرير & X X بدلا من مجرد؟ السابق هو الصحيح. نعم. [رد الطالب غير مسموع] بالضبط، إذا كان الهدف من هذا البرنامج، مثل وظيفة GetInt نفسها، هو الحصول على كثافة العمليات يمكن للمستخدم من أمرر وظائف جميع المتغيرات أريد، ولكن إذا كنت لم تمر عليهم من قبل المرجعية أو حسب العنوان أو عن طريق المؤشر، جميع مرادفا لأغراض اليوم، ثم أن وظيفة ليس لديها القدرة على تغيير محتويات هذا المتغير. هذا من شأنه أن تمر في نسخة تماما مثل الإصدار عربات التي تجرها الدواب من مبادلة أنه قد تحدثنا عن بضع مرات حتى الآن. ولكن بدلا من ذلك، عن طريق القيام & X، وأنا حرفيا في تمرير ما؟ [طالب] >> عنوان. عنوان X. انها تشبه رسم خريطة للدالة يسمى scanf وقوله هنا، هذه هي الاتجاهات إلى قطعة من الذاكرة في الكمبيوتر التي يمكن أن تذهب تخزين عدد صحيح بعض فيها. من أجل sscanf القيام به الآن أن ما المشغل، ما قطعة من جملة الحال لديك لاستخدام على الرغم من أننا لا نستطيع أن نرى ذلك لأن شخص آخر كتب هذه الوظيفة؟ وبعبارة أخرى - ما هذا؟ [طالب] X القراءة. هناك سيكون بعض القراءة، ولكن فقط فيما يتعلق X هنا. إذا كان يتم تمرير scanf عنوان X، بناء جملة، لا بد ما في مكان ما في الوجود المشغل داخل تنفيذ scanf بحيث scanf يمكن أن يكتب في الواقع عددا من 2 إلى هذا العنوان؟ نعم، لذلك *. * أذكر أن لدينا هو المشغل إلغاء مرجعية، وهو ما يعني أساسا ذهاب إلى هناك. بمجرد أن تم تسليم لك عنوان، كما هو الحال هنا، وربما لو نظرنا في الواقع scanf حول مصدره رمز * تقوم X أو ما يعادلها للذهاب إلى هذا العنوان بالفعل وضعت بعض القيمة هناك. الآن، أما عن كيفية scanf يحصل على مدخلات من لوحة المفاتيح، سنقوم موجة من أيدينا لهذا اليوم. مجرد افتراض أن نظام التشغيل يسمح للحديث sscanf لوحة المفاتيح للمستخدم، ولكن في هذه المرحلة الآن في خط 19، عندما كنا ببساطة طباعة X، يبدو أن هذا هو الحال وقد وضع هذا scanf والباحث في العاشر. هذا هو بالضبط كيف يعمل scanf، وأذكر الأسبوع الماضي هذه هي الطريقة بالضبط GetString وGetInt وأهله من وظائف أخرى يعمل في نهاية المطاف، ولكن مع تباين طفيف مثل sscanf، مما يعني مسح سلسلة بدلا من لوحة المفاتيح. ولكن دعونا نلقي نظرة على الفرق قليلا من هذا. في scanf2، I فعليا حتى ثمل. ما هو الخطأ، وأنا سوف إخفاء التعليق الذي يفسر بقدر- ما هو الخطأ في هذا البرنامج، الإصدار 2؟ تكون التقنية ممكن هذا الوقت. أنها تبدو جيدة جدا. انها بادئة لطيف، ولكن، حسنا، كيف تسمح لتقليم حول ذلك وصولا الى أقصر الأسئلة؟ السطر 16. ما هو السطر 16 دقيقة باللغة الإنجليزية تفعل ولكن التقنية؟ الحصول على القليل حرج. نعم، مايكل. [طالب] انها لافتا إلى الحرف الأول من السلسلة. حسنا، على مقربة. اسمحوا لي أن قرص قليلا. مشيرا إلى الحرف الأول من السلسلة، معلنا كنت مخزن مؤقت متغير يسمى والتي تشير إلى العنوان الأول من سلسلة، أو بالأحرى، فإن ذلك يشير بشكل أكثر تحديدا إلى شار. لاحظت انها ليست في الواقع في أي مكان مشيرا لأنه ليس هناك عامل التعيين. ليس هناك علامة المساواة، لذلك كل ما نقوم به هو تخصيص المخزن المؤقت متغير يسمى. يحدث أن يكون 32 بت لأنها مؤشر، ومحتويات المخزن المؤقت في نهاية المطاف يفترض سوف تحتوي على عنوان إحدى شار، لكنه الآن، ماذا تحتوي العازلة؟ فقط بعض همية، من يدري، بعض القمامة القيمة، لأننا لم تهيئة بشكل صريح، لذلك ينبغي لنا أن نفترض أي شيء. حسنا، حتى الآن السطر 17 IS-ماذا تفعل السطر 17؟ ربما من شأنها أن هذا الأمر الحارة. فإنه يطبع سلسلة، أليس كذلك؟ فإنه يطبع سلسلة من فضلك. خط 18 هو نوع من المألوف الآن في رأينا أن مجرد تباين هذه ولكن مع رمز شكل مختلف، وذلك في خط 18، نحن نقول scanf هنا هو عنوان قطعة من الذاكرة. أريدك أن حلقة في سلسلة ما يذهب إليه٪ S، ولكن المشكلة هي أننا لم تفعل بضعة أشياء هنا. ما هو واحدة من المشاكل؟ [طالب] ويحاول إلغاء مرجعية مؤشر فارغة. جيد، مؤشرات خالية أو غير معروفة فقط خلاف ذلك. كنت تسليم scanf عنوان، ولكن قلت قبل لحظة فقط أن هذا العنوان هو بعض القيمة القمامة لأننا لم فعلا تعيين إلى أي شيء، وهكذا كنت أقول scanf تذهب بشكل فعال وضعت سلسلة هنا، لكننا لا نعرف أين هو هنا بعد، لذلك نحن في الواقع لم يخصص الذاكرة لالعازلة. وعلاوة على ذلك، ما أنت أيضا لا يقولون حتى scanf؟ ان هذا كان جزءا من الذاكرة، وأنه لم يكن قيمة القمامة، ولكن كنت لا تزال لا يقول شيئا مهما scanf. [طالب] أين هو عليه في الواقع، والعطف. العطف، لذلك في هذه الحالة، لا بأس. لأنه أعلن بالفعل العازلة كمؤشر مع قطعة من * لغوي، ونحن لسنا بحاجة لاستخدام العطف لأنه بالفعل عنوان، ولكن أعتقد أنني سمعت هنا. [طالب] كيف كبير هو؟ جيد، نحن لا نقول scanf كيف كبيرة هذا المخزن المؤقت، وهو ما يعني حتى لو كانت العازلة مؤشر، نحن نقول scanf، وطرح سلسلة هنا، ولكن هنا يمكن أن يكون 2 بايت، فإنه يمكن أن يكون 10 بايت، يمكن أن يكون ميغا بايت. Scanf ليس لديه فكرة، ولأن هذا هو جزء من الذاكرة يفترض، انها ليست سلسلة حتى الآن. انها فقط سلسلة بمجرد كتابة الأحرف و0 \ لأن جزءا من الذاكرة. الآن انها مجرد قطعة من بعض الذاكرة. سوف Scanf لا تعرف متى يتوقف عن الكتابة إلى هذا العنوان. إذا كنت أذكر بعض الأمثلة في الماضي حيث كتبت على لوحة المفاتيح بشكل عشوائي في محاولة لتجاوز المخزن مؤقت، وتحدثنا عن ذلك يوم الجمعة بالضبط. إذا عدو يضخ نحو ما في البرنامج كلمة أكبر بكثير أو الجملة أو العبارة ثم كنت أتوقع يمكنك تجاوز قطعة من الذاكرة، والتي يمكن أن يكون لها عواقب سيئة، مثل الاستيلاء على كامل البرنامج نفسه. نحن بحاجة إلى إصلاح هذه بطريقة أو بأخرى. اسمحوا لي أن التصغير والخوض في الإصدار 3 من هذا البرنامج. هذا أفضل قليلا. في هذا الإصدار، لاحظ الفرق. في السطر 16، وأنا مرة أخرى معلنا مخزن مؤقت متغير يسمى، ولكن ما هو عليه الآن؟ انها مجموعة من 16 حرف. هذا أمر جيد لأن هذا يعني أستطيع أن أقول الآن scanf هنا هو جزء من الذاكرة الفعلية. يمكنك التفكير تقريبا من صفائف بأنها مؤشرات الآن، على الرغم من أنها لم تكن في الواقع ما يعادل. وأنها سوف تتصرف بشكل مختلف في سياقات مختلفة. ولكن من المؤكد أن يتم الرجوع العازلة 16 حرف متجاورة لأن هذا هو ما صفيف وكان لبضعة أسابيع الآن. هنا، أنا أقول scanf وهنا قطعة من الذاكرة. هذه المرة، انها فعلا قطعة من الذاكرة، ولكن لماذا هذا البرنامج مازال استغلال؟ ما هو الخطأ لا تزال؟ قلت أعطني 16 بايت ولكن- [طالب] ماذا لو اكتب في أكثر من 16؟ بالضبط، ما إذا كان المستخدم في أنواع الأحرف 17 حرفا أو 1700؟ في الواقع، دعونا نرى اذا كنا نستطيع لا يتعثر هذا الخطأ الآن. انها افضل ولكن الكمال لا. اسمحوا لي أن تمضي قدما وجعل تشغيل scanf3 لتجميع هذا البرنامج. اسمحوا لي أن تشغيل scanf3، سلسلة من فضلك: مرحبا، ويبدو أننا على ما يرام. اسمحوا لي أن أحاول واحدة أطول قليلا، مرحبا هناك. حسنا، دعونا نفعل مرحبا هناك كيف حالك اليوم، أدخل. الحصول على نوع من الحظ هنا، دعنا نقول مرحبا كيف حالك هناك. اللعنة. حسنا، حتى وصلنا محظوظ. دعونا نرى ما اذا كنا نستطيع حل هذه لا. لا، انها لن اسمحوا لي نسخه. دعونا نحاول هذا مرة أخرى. كل الحق، والوقوف من قبل. سنرى كم من الوقت يمكنني أن أدعي أن التركيز أثناء القيام لا يزال هذا. اللعنة. أن من المناسب بدلا من ذلك، في الواقع. هناك نذهب. جعل نقطة. هذا، على الرغم من أنه هو إحراج أيضا، كما أنها واحدة من مصادر الارتباك الكبير عند كتابة البرامج التي لها البق لأنها تعبر عن نفسها مرة واحدة فقط في حين في بعض الأحيان. الحقيقة هي أنه حتى إذا ما تم كسر الشفرة تماما، قد لا يمكن كسرها إلا تماما مرة واحدة في حين لأن في بعض الأحيان، أساسا ما يحدث هو يخصص نظام التشغيل ذاكرة أكثر قليلا مما كنت تحتاج بالفعل لأي سبب من الأسباب، وذلك لا أحد آخر يستخدم الذاكرة مباشرة بعد قطعة الخاص بك من 16 حرفا، إذا كان الأمر كذلك تذهب إلى 17، 18، 19، أيا كان، انها ليست مثل هذه الصفقة الكبيرة. الآن، الكمبيوتر، حتى لو كان لا تحطم في تلك المرحلة، قد تستخدم في نهاية المطاف عدد بايت 17 أو 18 أو 19 لشيء آخر، في التي تشير البيانات التي وضعت هناك، ولو بشكل مفرط طويلة، هو الذهاب الى الحصول على الكتابة يحتمل من قبل بعض وظيفة أخرى. انها لن بالضرورة أن تظل سليمة، لكنه لن يؤدي بالضرورة إلى خطأ SEG. لكن في هذه الحالة، وأنا قدمت أخيرا أحرف كافية أنني تجاوزت أساسا بلدي الجزء من الذاكرة، وبام، وقال نظام التشغيل، "عذرا، هذا ليس جيدا خطأ تجزئة." والآن دعونا نرى إذا ما بقي هنا في بلدي دليل، تلاحظ أن لدي هذا الملف هنا، الأساسية. لاحظ استدعاء مرة أخرى هذا تفريغ الأساسية. انها في الأساس ملف الذي يحتوي على المحتوى من الذاكرة البرنامج الخاص بك عند النقطة التي تحطمت، وفقط في محاولة مثال قليلا هنا اسمحوا لي ان اذهب هنا وجدب على تشغيل scanf3 ثم تحديد وسيطة ثالث يسمى الأساسية، وتلاحظ هنا أن أسرد إذا التعليمات البرمجية، سوف نكون قادرين على النحو المعتاد مع GDB لبدء المشي من خلال هذا البرنامج، ويمكنني تشغيله وسرعان ما الكر كما هو الحال مع الأمر خطوة في GDB- بمجرد ضرب I خط عربات التي تجرها الدواب يحتمل بعد كتابة في سلسلة ضخمة، سأكون قادرا على تحديد فعلا هنا. المزيد عن هذا، على الرغم من في القسم من حيث مقالب الأساسية وما شابه ذلك بحيث يمكنك في الواقع كزة حول الداخل من تفريغ الأساسية وانظر على ما خط فشل البرنامج لك. أي أسئلة بعد ذلك على مؤشرات وعلى عناوين؟ لأن اليوم فصاعدا، ونحن في طريقنا للبدء في اتخاذ أمرا مفروغا منه أن هذه الأشياء موجودة ونحن نعرف بالضبط ما هي عليه. نعم. [طالب] كيف ذلك لم يكن لديك لوضع العلامة بجانب بعض سؤال جيد. فكيف لم يكن لدي لوضع العلامة بجانب صفيف حرف كما فعلت سابقا مع معظم الأمثلة لدينا؟ الجواب القصير هو صفائف قليلا الخاصة. يمكنك التفكير تقريبا العازلة بأنها في الواقع عنوان، ويحدث ذلك فقط أن يكون عليه الحال أن تدوين قوس مربع هو الراحة حتى نتمكن من الخوض في قوس 0، قوس 1، قوس 2، دون الحاجة إلى استخدام التدوين *. أن قليلا من كذبة بيضاء لأن المصفوفات والمؤشرات هي، في الواقع، مختلفة قليلا، ولكن في كثير من الأحيان ولكن ليس يمكن أن يكون دائما تستخدم بالتبادل. وباختصار، عندما وظيفة يتوقع مؤشر إلى قطعة من الذاكرة، يمكنك تمرير إما أن عنوان التي تم إرجاعها بواسطة malloc، وسنرى مرة أخرى malloc قبل فترة طويلة، أو يمكنك نقله اسم صفيف. لم يكن لديك للقيام العطف مع المصفوفات لأنها بالفعل مثل عناوين أساسا. هذا هو الاستثناء الوحيد. المعقوفتين جعلها خاصة. هل يمكن وضع العلامة التالية إلى المخزن المؤقت؟ لا في هذه الحالة. ومن شأن ذلك أن لا يعمل لأنه، مرة أخرى، من هذه الحالة الزاوية حيث صفائف ليست في الواقع تماما عناوين. ولكن سوف نأتي مرة أخرى إلى ربما قبل ذلك بوقت طويل مع أمثلة أخرى. دعونا نحاول حل مشكلة هنا. لدينا بنية بيانات التي كنا تستخدم لبعض الوقت والمعروفة باسم صفيف. مثال على ذلك، وهذا ما كان لدينا فقط. ولكن لديك بعض الإيجابيات صفائف وسلبيات. لماذا هي صفائف لطيفة؟ ما هو الشيء الوحيد الذي ترغب إلى حد ترغب صفائف نبذة عن المصفوفات؟ ما هو ملائم عنهم؟ ما هو مقنع؟ لماذا لم نقدم لهم في المقام الأول؟ نعم. [طالب] ويمكن تخزين الكثير من البيانات، وليس لديك لاستخدام الشيء بأكمله. يمكنك استخدام المقطع. جيدة، مع مجموعة يمكنك تخزين الكثير من البيانات، وليس لديك بالضرورة لاستخدام كل ذلك، لذلك كنت overallocate يمكن، والتي قد تكون مريحة إذا كنت لا تعرف مسبقا كم من شيء يمكن توقعه. GetString هو مثال ممتاز. GetString، وكتب من قبلنا، لا يوجد لديه فكرة عن عدد أحرف يمكن توقعه، وبالتالي فإن حقيقة أننا يمكن تخصيص قطع من الذاكرة القريبة جيدة. صفائف أيضا حل مشكلة رأينا قبل بضعة أسابيع الآن حيث يبدأ التعليمات البرمجية لنقل إلى شيء سيئة جدا مصممة. أذكر أنني إنشاء هيكل الطالب دعا ديفيد، وكان بعد ذلك أن الواقع بديلا، على الرغم من إلى وجود اسم متغير يسمى وآخر متغير يسمى، كما أعتقد، المنزل، ومتغير آخر يسمى ID لأنه في هذه القصة أردت أن أعرض ثم شيء آخر مثل روب في البرنامج، حتى ذلك الحين قررت الانتظار لمدة دقيقة، ولست بحاجة لإعادة تسمية هذه المتغيرات. دعونا ندعو الألغام NAME1، ID1، house1. دعونا ندعو لروب NAME2، house2، ID2. ولكن الانتظار لمدة دقيقة ثم، ماذا عن تومي؟ ثم كان لدينا ثلاثة متغيرات. قدمنا ​​شخص آخر، أربع مجموعات من المتغيرات. بدأ العالم للحصول فوضى بسرعة كبيرة، قدم لذلك نحن البنيات، وما هو مقنعة عن البنية؟ ما هي وظيفة البنية C تسمح لك أن تفعل؟ انها حقا محرجا اليوم. ماذا؟ >> [استجابة الطالب غير مسموع] نعم، على وجه التحديد، typedef يسمح لك لخلق نوع بيانات جديدة، والبنية، والبنية الكلمة، ويسمح لك لتغليف من الناحية المفاهيمية المتعلقة قطعة من البيانات معا وندعو لهم شيء من هذا القبيل بعد ذلك طالب. كان ذلك جيدا لأنه الآن يمكننا تصميم نموذج نوع أكثر من ذلك بكثير من حيث المفهوم يتفق مفهوم الطالب في متغير بدلا من الاضطرار بشكل تعسفي واحدة لسلسلة واحدة عن هوية، وهكذا دواليك. صفائف لطيفة لأنها تسمح لنا لبدء تنظيف لدينا قانون. ولكن ما هو الجانب السلبي من الآن مجموعة؟ ماذا يمكنك أن تفعل؟ نعم. [طالب] عليك أن تعرف كيف انها كبيرة. عليك أن تعرف كيف انها كبيرة، لذلك نوع من الألم. تلك التي كنت من ذوي الخبرة يعرفون أن البرمجة السابقة في الكثير من اللغات، مثل جافا، يمكنك أن تطلب جزءا من الذاكرة، وتحديدا مجموعة، كيف حالك كبيرة، مع طول، والملكية، إذا جاز التعبير، وهذا حقا مريحة. في C، لا يمكنك حتى الدعوة الى التوابع strlen على مجموعة عامة لأن التوابع strlen، كما تدل الكلمة، هو فقط للسلاسل، ويمكنك معرفة طول سلسلة بسبب هذه الاتفاقية الإنسان وجود 0 \، ولكن صفيف، أكثر بشكل عام، هو مجرد جزء من الذاكرة. اذا كان مجموعة من رجات، وهناك لن يكون هناك طابع خاص في نهاية انتظاركم. عليك أن تتذكر طول صفيف. تربى آخر الجانب السلبي من مجموعة الرئيسي في GetString نفسها. ما هو الجانب السلبي من آخر مجموعة؟ يا سيدي، فقط أنت وأنا اليوم. [رد الطالب غير مسموع] >> وهذا ما؟ انها اعلنت انها على المكدس. حسنا، أعلن على المكدس. لماذا لا تحب ذلك؟ [طالب] لأن يحصل إعادة استخدامها. يحصل إعادة استخدامها. حسنا، إذا كنت تستخدم مجموعة تخصيص الذاكرة، لا يمكنك، على سبيل المثال، إعادته لأنه على المكدس. حسنا، هذا وضع غير مؤات. وماذا عن الآخر مع مجموعة؟ بمجرد إحالته، كنت نوع من مشدود إذا كنت بحاجة إلى مساحة أكبر من ذلك مجموعة لديها. ثم عرض علينا، استدعاء، malloc، الذي أعطانا القدرة على تخصيص حيوي الذاكرة. ولكن ماذا لو حاولنا عالم مختلف تماما؟ ماذا لو أردنا أن يحل بعض هذه المشاكل لذلك نحن بدلا-بلدي انخفض القلم نائما هنا، ماذا لو كنا نريد لخلق بدلا أساسا عالم لم يعد مثل هذا؟ هذا هو الصفيف، وبطبيعة الحال، هذا النوع من تدهور وبمجرد أن تصل إلى نهاية الصفيف، وأنا الآن لم يعد لدينا مساحة للآخر صحيحا أو حرف آخر. ماذا لو أننا نوع من استباقي يقول حسنا، لماذا لا يتم الاسترخاء هذا الشرط أن كل هذه أجزاء من الذاكرة متجاورة تكون العودة إلى الوراء، ولماذا لا، وعندما أحتاج إلى الباحث أو حرف A، مجرد اعطاء لي مساحة للواحد منهم؟ وعندما كنت في حاجة أخرى، أعطني مساحة أخرى، وعندما كنت في حاجة أخرى، أعطني مساحة أخرى. ميزة الذي هو الآن أنه إذا شخص آخر يأخذ الذاكرة أكثر من هنا، ليست صفقة كبيرة. أنا سآخذ هذا جزء من الذاكرة الإضافية هنا ثم هذا واحد. الآن، الصيد الوحيد هنا هو أن هذا يشعر تقريبا مثل ولدي في مجمله مجموعة من المتغيرات المختلفة. هذا يبدو وكأنه خمسة متغيرات التي قد تكون مختلفة. ولكن ماذا لو أننا سرقة فكرة من السلاسل حيث نربط بطريقة ما هذه الأشياء معا من الناحية النظرية، وماذا لو فعلت هذا؟ هذا هو بلدي سهم سيئة للغاية مرسومة. ولكن لنفترض أن كل من هذه القطع من الذاكرة وأشار إلى أخرى، وهذا الرجل الذي ليس لديه أخ لحقه، لا يوجد لديه مثل هذه الأسهم. هذا هو في الواقع ما يسمى قائمة مرتبطة. هذا هو بنية البيانات الجديدة التي تسمح لنا بتخصيص قطعة من الذاكرة، ثم آخر، ثم آخر، ثم آخر، في أي وقت نريد خلال البرنامج، وعلينا أن نتذكر أن أنهم جميعا على نحو ما ذات صلة بواسطة تسلسل حرفيا فعل بعضهم البعض، ونحن هنا بالصور التي مع سهم. ولكن في التعليمات البرمجية، ما هي الآلية التي يمكن أن عبر الاتصال بطريقة أو بأخرى، تقريبا مثل خدش واحد قطعة قطعة إلى أخرى؟ يمكننا استخدام مؤشر، أليس كذلك؟ لأن حقا السهم الذي يجري من ساحة أعلى اليسار، يمكن هذا الرجل هنا لهذا واحد، تحتوي على داخل هذه الساحة وليس فقط بعض رجات، وليس فقط بعض شار، ولكن ما إذا كنت فعلا المخصصة ومساحة صغيرة إضافية بحيث الآن، كل من بلدي قطع من الذاكرة، حتى وإن كان هذا هو الذهاب الى التكاليف لي، يبدو الآن أكثر قليلا مستطيل حيث واحدة من قطع من الذاكرة يستخدم لعدد، مثل الرقم 1، ثم إذا كان هذا الرجل يخزن عدد 2، يتم استخدام هذه قطعة أخرى من الذاكرة لسهم، أو على نحو أكثر تحديدا، مؤشر. وأفترض تخزين رقم 3 أكثر من هنا بينما أنا استخدم هذا للإشارة إلى أن الرجل، والآن هذا الرجل، دعونا نفترض أريد سوى ثلاث قطع مثل هذه الذاكرة. أنا رسم خط من خلال ذلك، مشيرا إلى فارغة. لا يوجد أي حرف إضافية. في الواقع، هذه هي الطريقة التي يمكن أن تذهب نحو تنفيذ وهو ما يسمى قائمة مرتبطة. قائمة مرتبطة هو بنية البيانات الجديدة، وانها نقطة انطلاق نحو هياكل البيانات مربي الحيوانات بكثير التي تبدأ في حل المشاكل على غرار الفيسبوك من نوع المشاكل ومشاكل من نوع جوجل حيث لديك مجموعات البيانات الضخمة، وأنه لم يعد يقطع عليه كل شيء متاخم لتخزين واستخدام شيء من هذا القبيل ابحث عن الخطية أو شيء من هذا حتى مثل البحث الثنائي. تريد أفضل أوقات التشغيل. في الواقع، واحدة من الكؤوس المقدسة المقدسة سوف نتحدث عن هذا في وقت لاحق الاسبوع او الاسبوع القادم هو خوارزمية التي تشغل وقت ثابت. وبعبارة أخرى، فإنه يأخذ دائما نفس المقدار من الوقت بغض النظر عن كيف كبيرة الإدخال، والتي من شأنها أن تكون في الواقع مقنعة، بل وأكثر من شيء لوغاريتمي. ما هو هذا على الشاشة هنا؟ كل من المستطيلات هو بالضبط ما وجهت فقط باليد. ولكن الشيء على طول الطريق على اليسار هو متغير خاص. انها سوف تكون مؤشر واحد لأن مسكتك 1 مع قائمة مرتبطة، وتسمى هذه الأشياء، هو أن لديك للتشبث واحدة من نهاية القائمة المرتبطة. تماما مثل مع سلسلة، عليك أن تعرف عنوان شار الأولى. نفس الصفقة لقوائم المرتبطة. عليك أن تعرف عنوان قطعة الأولى من الذاكرة لأن من هناك، يمكنك الوصول إلى كل واحد الآخر. الجانب السلبي. ما هو الثمن نحن اشتري هذه براعة وجود حيوي لا بأس به هيكل البيانات أنه إذا نحن بحاجة من أي وقت مضى المزيد من الذاكرة، ودفع غرامة، تخصيص قطعة واحدة فقط أكثر ورسم المؤشر من القديم إلى الجديد من ذيل القائمة؟ نعم. [طالب] ويأخذ مساحة حوالي ضعف ذلك بكثير. فإنه يأخذ مساحة ضعف ما، لذلك هذا هو بالتأكيد الجانب السلبي، وهذا رأيناه المفاضلة بين قبل الزمان والمكان والمرونة حيث حتى الآن، لا نحتاج إلى 32 بت لكل من هذه الأرقام. نحن حقا بحاجة 64، 32 لعدد 32 لوالمؤشر. ولكن مهلا، لقد 2 غيغابايت من ذاكرة الوصول العشوائي. إضافة آخر 32 بت هنا وهنا لا يبدو كبيرا في التوصل الى اتفاق. ولكن لمجموعات البيانات الكبيرة، فإنه يضيف ما يصل الى الكثير بالتأكيد حرفيا مرتين. ما هو الجانب السلبي آخر الآن، أو ما لا ميزة تخلينا، إذا كان لنا أن تمثل قوائم من الأشياء مع قائمة مرتبطة وليس مجموعة؟ [طالب] لا يمكنك اجتياز إلى الخلف. لا يمكنك اجتياز الى الوراء، لذلك كنت نوع من مشدود إذا كنت المشي من اليسار إلى اليمين باستخدام حلقة For أو حلقة في حين ثم كنت أدرك، "أوه، أنا أريد أن أعود إلى بداية القائمة." لا يمكنك لأن هذه المؤشرات تذهب فقط من اليسار إلى اليمين كما تبين الأسهم. الآن، هل يمكن أن تذكر في بداية القائمة مع متغير آخر، ولكن هذا التعقيد أن نأخذ في الاعتبار. صفيف، بغض النظر عن مدى تذهب، يمكنك أن تفعل دائما ناقص، ناقص، ناقص، ناقص والعودة من أين جئت. ما هو الجانب السلبي هنا آخر؟ نعم. [سؤال الطالب غير مسموع] هل يمكن، لذلك كنت قد اقترحت في الواقع مجرد هيكل بيانات تسمى قائمة مرتبطة على نحو مضاعف، وبالفعل، وكنت إضافة آخر مؤشر إلى كل من هذه المستطيلات الذي يذهب في الاتجاه الآخر، الجانب العلوي منها الآن يمكنك اجتياز ذهابا وإيابا، الجانب السلبي منها الآن كنت تستخدم ثلاث مرات قدر الذاكرة كما كنا وأضاف أيضا من حيث التعقيد من قانون عليك أن تكتب للحصول على ذلك الحق. ولكن هذه هي ربما جميع المفاضلات معقولة جدا، وإذا كان عكس ما هو أهم. نعم. [طالب] أنت أيضا لا يمكن أن يكون على قائمة 2D المرتبطة. جيد، لا يمكنك حقا قائمة 2D المرتبطة. يمكن لك. انها ليست سهلة كما تقريبا صفيف. مثل صفيف، لديك قوس فتح، قوس مغلق، قوس فتح، إغلاق قوس، وتحصل بعض هيكل 2-الأبعاد. هل يمكن تنفيذ قائمة 2-الأبعاد مرتبطة إذا كان لديك الوظيفة الإضافية كما كنت اقترحت-مؤشر ثالث لكل من هذه الأشياء، وإذا كنت تفكر في آخر قائمة القادمة في لكم نمط 3D من الشاشة لنا جميعا، والذي هو مجرد سلسلة من نوع ما. يمكننا أن نفعل ذلك، ولكنها ليست بهذه البساطة كتابة قوس فتح، قوس مربع. نعم. [سؤال الطالب غير مسموع] جيدة، لذلك هذا هو كيكر الحقيقي. هذه الخوارزميات التي كانت لدينا أكثر من موهون، مثل أوه، البحث الثنائية، يمكنك البحث مجموعة من الأرقام على لوحة أو دليل الهاتف حتى بسرعة أكبر بكثير إذا كنت تستخدم فرق تسد وتتطلب خوارزمية البحث الثنائي، ولكن البحث الثنائية افتراضين. واحد، التي تم فرز البيانات. الآن، يمكننا الحفاظ على هذا يفترض فرزها، ولذلك ربما يكون هذا ليس مصدر قلق، ولكن يفترض أيضا البحث الثنائية أن كان لديك الوصول العشوائي إلى قائمة الأرقام، ومجموعة يسمح لك أن يكون الوصول العشوائي، والوصول العشوائي، يعني إذا كنت تحصل صفيف، كم من الوقت يستغرق لك للوصول الى شريحة 0؟ عملية واحدة، يمكنك استخدام فقط [0]، وكنت هناك. كم من الوقت يستغرق الخطوات للوصول الى الموقع 10؟ خطوة واحدة، تذهب فقط ل[10] وكنت هناك. على النقيض من ذلك، كيف تحصل على العدد الصحيح 10 في قائمة مرتبطة؟ عليك أن تبدأ في بداية لأنك تذكر فقط ويجري تذكرت بداية قائمة مرتبطة، تماما مثل سلسلة من عنوان شار الأولى، وكثافة العمليات لتجد أن 10 أو ذلك الحرف 10th في سلسلة، لديك للبحث في كل شيء لعنة. مرة أخرى، نحن لا حل كل مشاكلنا. إننا نقدم جديدة، ولكن ذلك يعتمد حقا على ما كنت تحاول تصميم ل. من حيث تنفيذ هذا، يمكننا استعارة فكرة من هذا الهيكل الطلاب. بناء الجملة هي مشابهة جدا، إلا الآن، والفكرة هي قليلا أكثر تجريدا من المنزل واسم ورقم. ولكن أقترح أن أننا يمكن أن يكون بنية بيانات في C الذي يسمى عقدة، والكلمة الأخيرة على الشريحة يوحي، داخل عقدة، وعقدة هو مجرد وعاء عامة في علوم الكمبيوتر. انها تعادل عادة على أنها دائرة أو مربع أو مستطيل كما فعلناه. وفي هذا بنية البيانات، لدينا كثافة العمليات، ن، ذلك أن عدد أريد أن تخزين. ولكن ما هو هذا الخط الثاني، البنية عقدة * في المرة القادمة؟ لماذا هذا صحيح، أو ما هو الدور الذي يلعبه هذا الشيء، على الرغم من انها قليلا خفي للوهلة الأولى؟ نعم. [رد الطالب غير مسموع] بالضبط، لذلك هذا النوع من الغنائم * أنه مؤشر من نوع ما. اسم هذا المؤشر القادمة بشكل تعسفي، ولكن يمكن أن يكون أي شيء كنا نسميها نحن نريد، ولكن ماذا يعني هذا المؤشر إلى نقطة؟ [طالب] عقدة أخرى. >> بالضبط، فإنه يشير إلى عقدة أخرى من هذا القبيل. الآن، وهذا هو نوع من الفضول من C. يذكر أن للقراءة من قبل أحد كبار C مترجم إلى الأسفل، اليسار إلى اليمين، وهو ما يعني إذا، هذا هو مختلفة قليلا عن ما فعلناه مع الطالب. عندما كنا تعريف الطالب، ونحن في الواقع لم يضع كلمة هناك. وقالت typedef فقط. ثم كان لدينا اسم الباحث معرف سلسلة،، سلسلة المنزل، ومن ثم طالب في الجزء السفلي من البنية. هذا الإعلان هو مختلف قليلا لأنه، مرة أخرى، مترجم C قليلا البكم. انها لن يؤدي الا الى قراءة أعلى إلى أسفل، إذا كان الأمر كذلك وصولها إلى خط 2 هنا حيث أعلن المقبل، ويرى أنه، أوه، ها هي متغير يسمى المقبل. انها مؤشر إلى البنية عقدة. المترجم هو الذهاب الى تحقيق ما هو عقدة البنية؟ لم اسمع ابدا من هذا الشيء من قبل، لأنه قد العقدة لا تظهر إلا كلمة حتى القاع، حتى لا يكون هناك هذا التكرار. لديك لتقوله هنا العقدة البنية، والتي يمكنك تقصير ثم في وقت لاحق بفضل typedef إلى هنا، ولكن هل هذا بسبب نحن الرجوع إلى هيكل نفسه داخل الهيكل. هذا هو مسكتك أحد هناك. بعض المشاكل للاهتمام سوف تنشأ. لدينا قائمة من الأرقام. كيف يمكننا إدراجها في ذلك؟ كيف يمكننا البحث عنها؟ كيف يمكننا حذف منه؟ خاصة الآن أن لدينا لإدارة كل من هذه المؤشرات. فكرت المؤشرات كانت نوع من الانحناء العقل عندما كان لديك واحد منهم مجرد محاولة لقراءة الباحث لذلك. الآن لدينا لمعالجة يستحق قائمة بأكمله. لماذا لا نأخذ لدينا 5 دقائق استراحة هنا، ومن ثم سوف نأتي بعض الناس حتى على خشبة المسرح لذلك تماما. C هو متعة أكثر من ذلك بكثير عندما يكون تصرف بها. والذين يحبون أن يكون حرفيا الأول؟ حسنا، وتأتي على ما يصل. كنت الأول. والذي أحب أن أكون 9؟ حسنا، 9. ماذا عن 9؟ 17؟ A زمرة قليلا هنا. 22 و 26 في هذا الصف. ثم ماذا عن شخص ما يجري هناك وأشار في. كنت 34. حسنا، 34، وتأتي على ما يصل. الأول هو هناك. حسنا، كل أربعة من يا رفاق. والذين لم نقول لمدة 9؟ الذي هو 9 لدينا؟ الذي يريد حقا أن تكون 9؟ حسنا، هيا، هو 9. هنا نذهب. 34، سوف نلتقي كنت هناك. الجزء الأول هو جعل أنفسكم ننظر من هذا القبيل. 26، 22، 17، جيدة. إذا كنت تستطيع الوقوف قبالة إلى الجانب، لأننا ذاهبون الى malloc كنت في لحظة. جيد، جيد. حسنا، ممتاز، لذلك دعونا نسأل بضعة أسئلة هنا. وفعلا، ما هو اسمك؟ >> أنيتا. أنيتا، حسنا، هيا أكثر من هنا. أنيتا سوف تساعدنا نوع من حل سؤال واحد بسيط إلى حد ما في الأولى، وهو كيف تجد ما إذا كان أو لم يكن هو قيمة في القائمة؟ الآن، لاحظ أن الأولى، الممثلة هنا لوكاس، هي مختلفة قليلا، وهكذا قطعة من الورق له هو جانبية عمدا لأنه ليس طويل القامة جدا كما ولا تتناول، حسب العديد من معاهدات الاستثمار الثنائية، على الرغم من الناحية الفنية لديه نفس الحجم من الورق تناوب فقط. لكنه مختلف قليلا في أنه فقط 32 بت لمؤشر، وجميع هؤلاء الرجال 64 بت، نصفها هو عدد نصفها هو مؤشر. ولكن لم يتم تصوير المؤشر، لذلك إذا يا رفاق يمكن برعونة إلى حد ما استخدام اليد اليسرى للإشارة إلى الشخص إلى جانبك. وكنت رقم 34. ما هو اسمك؟ آري. آري، في الواقع كذلك، فاضغط الورقة التي في يدك اليمنى، واليد اليسرى يذهب مباشرة إلى الأسفل. أنت ممثل فارغة على اليمين. الآن لدينا صور الإنسان هو متسقة للغاية. هذا هو في الواقع كيف مؤشرات العمل. وإذا كنت تستطيع قطب قليلا بهذه الطريقة لذلك أنا لست في طريقك. أنيتا هنا، تجد لي عدد 22، ولكن تفترض القيد من البشر لا يمسك قطعة من الورق، ولكن هذا هو قائمة، وأنك لا تملك إلا لوكاس لتبدأ لأنه هو حرفيا المؤشر الأول. افترض أنك نفسك هي المؤشر، وحتى يكون لديك أيضا القدرة على الإشارة إلى شيء. لماذا لا تبدأ بالإشارة إلى ما بالضبط لوكاس يشير في؟ جيدة، واسمحوا لي أن تسن من ذلك أكثر من هنا. لمجرد النقاش، اسمحوا لي سحب ما يصل إلى صفحة فارغة هنا. كيف تتهجى اسمك؟ >> أنيتا. حسنا، أنيتا. دعنا نقول عقدة * = أنيتا لوكاس. حسنا، لا ينبغي لنا أن ندعو لكم لوكاس. ينبغي لنا أن ندعو لكم الأولى. لماذا هذا في الواقع يتفق مع الواقع هنا؟ واحد، أولا موجود مسبقا. وقد تم تخصيص مكان ما يفترض أولا حتى هنا. * العقدة الأولى، وانها تم تخصيص قائمة على نحو ما. أنا لا أعرف كيف حدث ذلك. حدث ذلك من قبل الطبقة بدأت. تم إنشاء هذه القائمة مرتبطة من البشر. والآن في هذه المرحلة من القصة، هذا يحدث كل شيء على ما يبدو في وقت لاحق في الفيسبوك- في هذه المرحلة من القصة، تمت تهيئة أنيتا لتكون مساوية لأول، وهذا لا يعني أن نقاط أنيتا في لوكاس. بدلا من ذلك، فإنها تشير إلى ما يشير في لأن نفس العنوان وهذا من داخل 32 بت لوكاس - 1، 2، 3 - الآن داخل أيضا 32 بت أنيتا - 1، 2، 3. الآن العثور على 22. كيف يمكنك أن تذهب نحو القيام بذلك؟ ما هذه النقطة؟ >> لأيا كان. إشارة إلى ما، لذلك يذهب إلى الأمام والعمل بها أفضل ما يمكنك هنا. جيد، جيد، والآن كنت لافتا في، ما هو اسمك مع 22؟ رامون. >> رامون، رامون لذلك هو عقد بزيادة 22. كنت قد فعلت الآن الاختيار. لا رامون == 22، وإذا كان الأمر كذلك، على سبيل المثال، يمكننا العودة الحقيقية. اسمحوا لي، في حين هؤلاء الرجال نقف هنا بعض الشيء مؤلم، اسمحوا لي أن تفعل شيئا بسرعة مثل BOOL العثور عليها. انا ذاهب الى المضي قدما ويقول (عقدة * قائمة، وكثافة العمليات ن). سأعود مع الحق يا رفاق. أنا فقط لكتابة بعض التعليمات البرمجية. والآن انا ذاهب الى المضي قدما ونفعل ذلك، عقدة * قائمة = أنيتا. وانا ذاهب الى المضي قدما ويقول في حين أن (أنيتا! = NULL). استعارة هنا هو الحصول على القليل امتدت، ولكن في حين أن (أنيتا! = NULL)، ماذا أريد أن أفعل؟ انا بحاجة الى بعض طريق الرجوع العدد الصحيح الذي يشير في أنيتا. في الماضي، عندما كان لدينا الهياكل، والتي هي عقدة، استخدمنا نقطة تدوين، وكنا نقول شيء من هذا القبيل anita.n، ولكن المشكلة هنا هي أن أنيتا ليس البنية في حد ذاتها. ما هي؟ انها مؤشر، حقا ذلك، إذا كنا نريد لاستخدام هذه النقطة، تدوين وهذا هو الذهاب الى نظرة عمدا قليلا خفي- علينا أن نفعل شيئا مثل الذهاب الى جهة اليسار مهما كانت أنيتا يشير في وثم الحصول على حقل يسمى ن. أنيتا هو مؤشر، ولكن ما هو * أنيتا؟ ما رأيكم عندما تذهب إلى ما أنيتا يشير في؟ A البنية، عقدة، عقدة والتذكير،، لديها حقل يسمى N لأنه، أذكر، هذه الحقول 2، و n المقبل، أن رأينا قبل لحظة هنا. لتقليد الواقع هذا في التعليمات البرمجية، يمكننا القيام بذلك والقول ما اذا كان ((* أنيتا). == ن ن)، ن أنني أبحث عنه. تلاحظ أن صدر وظيفة في عدد يهمني. بعد ذلك يمكنني أن نمضي قدما ونفعل شيئا مثل العودة الحقيقية. آخر، إذا كان هذا ليس هو الحال، ماذا أريد أن أفعل؟ كيف يمكنني ترجمة لرمز ما فعل حدسي أنيتا ذلك عن طريق المشي خلال قائمة؟ ماذا علي أن أفعل هنا لمحاكاة أنيتا اتخاذ هذه الخطوة إلى اليسار، هذه الخطوة إلى اليسار؟ [رد الطالب غير مسموع] >> ما هذا؟ [رد الطالب غير مسموع] جيدة، ليست فكرة سيئة، ولكن في الماضي، عندما كنا قد فعلت ذلك، لقد فعلنا أنيتا + + لأن ذلك من شأنه أن يضيف الرقم 1 إلى أنيتا، الأمر الذي يشير عادة في الشخص التالي، مثل رامون، أو الشخص التالي له، أو بجانبه شخص على طول الطريق. ولكن هذا ليس جيدا جدا هنا، لأن ما هذا الشيء لا تبدو في الذاكرة؟ لا ذلك. لدينا لتعطيل ذلك. يبدو مثل هذا في الذاكرة، ورغم أنني كنت تعادل 1 و 2 و 3 على مقربة من بعضها البعض، إذا كنا حقا محاكاة هذا CAN-يا رفاق، في حين لا يزال في افتا نفس الأشخاص، يمكن البعض منكم اتخاذ خطوة إلى الوراء عشوائية، البعض منكم خطوة إلى الأمام عشوائية؟ هذه الفوضى لا تزال قائمة مرتبط، ولكن يمكن أن يكون هؤلاء الرجال في أي مكان في الذاكرة، حتى أنيتا + + لن تعمل لماذا؟ ما هو على الموقع أنيتا + +؟ من يدري. انها بعض قيمة أخرى مجرد أن ذلك يحدث أن يكون موسط من بين جميع هذه العقد عن طريق الصدفة لأننا لا تستخدم صفيف. خصصنا لكل من هذه العقد بشكل فردي. حسنا، إذا يا رفاق يمكن تنظيف أنفسكم النسخ الاحتياطي. اسمحوا لي أن أقترح أن أنيتا أنيتا بدلا من +، ونحن نفعل بدلا + يحصل- حسنا، لماذا لا نذهب إلى ما أنيتا يشير في وثم القيام بها في المرة القادمة؟ وبعبارة أخرى، نذهب إلى رامون، الذي هو عقد عدد 22، وبعد ذلك. التالي كما لو أنيتا سيتم نسخ مؤشر يده اليسرى. ولكن قالت إنها لا تذهب أبعد من رامون لأننا وجدنا 22. ولكن ذلك سيكون على هذه الفكرة. الآن، وهذا هو فوضى فظيعة الله. بصراحة، لا أحد من أي وقت مضى تذكر هذه الجملة، ولله الحمد كان الأمر كذلك، انها في الواقع قليلا المتعمد أوه، كنت لا ترى في الواقع ما كتبت. وهذا سيكون أكثر إقناعا لو تفضلتم. فويلا! وراء الكواليس، وكنت حل مشكلة بهذه الطريقة. أنيتا، لاتخاذ هذه الخطوة إلى اليسار، أولا، نحن لا تذهب إلى العنوان الذي يشير في أنيتا وقالت انها سوف تجد فيها ليس فقط ن، والتي بحثنا فقط لغرض المقارنة، ولكن سوف تجد أيضا بجوار - في هذه الحالة، ومن جهة اليسار رامون مشيرا إلى عقدة التالي في القائمة. ولكن هذه هي الفوضى الله فظيعة الذي أشرت إليه في وقت سابق، ولكن تبين C يتيح لنا هذا تبسيط. بدلا من كتابة (* أنيتا)، يمكننا بدلا من ذلك مجرد كتابة أنيتا-> ن، وانها نفس الشيء بالضبط وظيفيا، ولكن الكثير أكثر سهولة، وانها الكثير أكثر اتساقا مع الصورة التي كنا الرسم كل هذا الوقت باستخدام السهام. وأخيرا، ماذا علينا أن نفعل في نهاية هذا البرنامج؟ هناك سطر واحد من التعليمات البرمجية المتبقية. العودة ماذا؟ كاذبة، لأنه إذا كنا من خلال الحصول على كامل بينما حلقة وأنيتا هو، في الواقع، فارغة، وهذا يعني أنها ذهبت على طول الطريق إلى نهاية القائمة حيث كانت لافتا في، ما هو اسم الخاص بك مرة أخرى؟ آري. >> أري في اليد اليسرى، والتي هي فارغة. أنيتا الآن فارغة، وأنا أدرك أنك مجرد الوقوف هنا برعونة في طي النسيان لأنني ذاهب من هنا على المونولوج، ولكن سوف نشرك بك مرة أخرى في لحظة واحدة. أنيتا فارغة عند هذه النقطة في القصة، وبالتالي فإن إنهاء حلقة في حين، وعلينا أن عودة كاذبة لأنه إذا حصلت كل وسيلة لاري في مؤشر فارغة ثم لم يكن هناك عدد بأنها سعت في القائمة. يمكننا بتنظيف هذا أيضا، ولكن هذا هو تطبيق جيد جدا ثم وظيفة اجتياز، وإيجاد وظيفة للحصول على قائمة مرتبطة. ما زال البحث الخطية، ولكنها ليست بهذه البساطة + + مؤشر أو + + متغير لأن أنا الآن لا يمكننا تخمين حيث كل من هذه العقد هي في الذاكرة. علينا أن نتبع حرفيا درب من فتات الخبز أو بشكل أكثر تحديدا، مؤشرات، ليقطع الطريق من عقدة إلى أخرى. الآن دعونا نحاول واحد آخر. أنيتا، هل تريد أن تأتي إلى هنا؟ لماذا لا يتم المضي قدما في تخصيص شخص واحد آخر من الجمهور؟ Malloc، ما اسمك؟ >> ريبيكا. ريبيكا. وقد malloced ريبيكا من الجمهور، وأنها الآن تخزين عدد 55. والهدف في متناول اليد الآن لأنيتا لإدراج ريبيكا في قائمة مرتبطة هنا في مكانها المناسب. تعال هنا للحظة. لقد فعلت شيئا من هذا القبيل. وقد فعلت * العقدة. وما هو اسم الخاص بك مرة أخرى؟ ريبيكا. >> ريبيكا، حسنا. ريبيكا يحصل malloc (sizeof (عقدة)). تماما مثل خصصنا أشياء مثل الطلاب وwhatnot في الماضي، نحن بحاجة إلى حجم العقدة، حتى الآن ريبيكا يتم الإشارة إلى ما؟ ريبيكا حقلين داخل بلدها، واحدة منها هو 55. دعونا نفعل ما، ريبيكا-> = 55. ولكن بعد ذلك ريبيكا-> التالي ينبغي أن تشبه في الوقت الحالي، يدها هو نوع من يدري؟ انها لافتا في بعض القيمة القمامة، لذلك لماذا لا لحسن التدبير نحن على الأقل القيام بذلك بحيث اليد اليسرى الآن في جانبها. أنيتا الآن، أعتبر من هنا. لديك بعد أن تم تخصيص ريبيكا. والمضي قدما في العثور على مكان يجب وضع ريبيكا. جيد، جيد جدا. حسنا، جيد، والآن نحن بحاجة لكم لتوفير قليلا من اتجاه، حتى لقد وصلت إلى آري. يده اليسرى فارغة، ولكن ريبيكا ينتمي بوضوح إلى اليمين، فكيف علينا أن تغيير هذه القائمة مرتبطة من أجل إدراج ريبيكا في المكان المناسب؟ إذا كنت يمكن أن تتحرك حرفيا أيدي الناس في جميع أنحاء اليسرى حسب الحاجة، سنقوم حل المشكلة بهذه الطريقة. حسنا، جيد، وفي الوقت نفسه، ومن ناحية اليسار ريبيكا الآن إلى جانبها. كان من السهل جدا. دعونا نحاول القيام به تخصيص-we're تقريبا، 20. حسنا، وتأتي على ما يصل. وقد تم تخصيص 20، لذلك اسمحوا لي المضي قدما وأقول مرة أخرى هنا لقد فعلنا فقط عقدة سعد *. لدينا malloc (sizeof (عقدة)). ثم نفعل نفس بناء الجملة بالضبط كما فعلنا من قبل لمدة 20، وسوف أفعل بعد ذلك = NULL، والآن الامر متروك أنيتا لإدراج لكم في قائمة مرتبطة، إذا كنت يمكن أن يلعب هذا الدور بالضبط نفس. تنفيذ. حسنا، جيد. أعتقد الآن بعناية قبل بدء التحرك أيدي اليسار حولها. كنت حتى الآن حصلت على دور الأكثر حساسية اليوم. يجب أن يتم نقل اليد التي الأول؟ حسنا، انتظر، أسمع بعض لم يتم. اذا كان بعض الناس يحبون بأدب للمساعدة في حل وضع حرج هنا. يجب أن يتم تحديث اليد اليسرى التي ربما الأول؟ نعم. [طالب] لسعد. حسنا، لسعد، لماذا، على الرغم من؟ [رد الطالب غير مسموع] جيد، لأنه إذا ما انتقلنا-اسمك؟ >> مارشال. مارشال، واذا كنا تحريك يده أول ما نزل إلى فارغة، الآن وقد اليتامى نحن حرفيا أربعة أشخاص في هذه القائمة لأنه كان الشيء الوحيد افتا في رامون والجميع إلى اليسار، تحديث بحيث كان أول مؤشر سيء. دعونا التراجع عن ذلك. جيدة، والآن المضي قدما وتحريك اليد اليسرى المناسبة لافتا في رامون. هذا يشعر زائدة قليلا. الآن هناك شخصين لافتا في رامون، ولكن هذا شيء طيب لأنه الآن وإلا كيف يمكننا تحديث قائمة؟ ومن جهة أخرى ما لديه للانتقال؟ ممتازة، والآن فقدنا أي ذاكرة؟ لا، جيدة جدا، دعونا نرى ما اذا كنا نستطيع كسر هذا لا مرة أخرى. Mallocing للمرة الأخيرة، عدد 5. على طول الطريق في الظهر، هيا. انها مثيرة للغاية. [تصفيق] ما هو اسمك؟ >> رون. رون، حسنا، وmalloced لكم ورقم 5. لقد قمنا بتنفيذ التعليمات البرمجية فقط وهذا مطابق تقريبا لهذه مع اسم واحد فقط مختلفة. ممتازة. الآن، أنيتا، وحسن الحظ إدراج رقم 5 في قائمة الآن. جيدة، و؟ ممتازة، لذلك هذا هو حقا ثالث ثلاثة مجموع الحالات. كان أول شخص ونحن في النهاية، ربيكا. ثم كان لدينا شخص في الوسط. الآن لدينا شخص في البداية، وفي هذا المثال، كان لدينا الآن لتحديث لوكاس لأول مرة لأن العنصر الأول في القائمة لديها الآن أن أشير في عقدة جديدة، الذي، بدوره، يشير في عدد عقدة 9. وكان هذا دليلا محرجا إلى حد كبير، وأنا متأكد، حتى جولة كبيرة من التصفيق لهؤلاء الرجال إذا كنت تستطيع. جيد للقيام به. هذا كل شيء. قد تبقى قطعة من الورق الخاص بك وذاكرة قليلا. وتبين أن القيام بذلك في التعليمات البرمجية ليست واردة بسيطة مثل تحريك اليدين حول وتشير المؤشرات إلى الأمور مختلفة. ولكن ندرك أنه عندما يأتي الوقت لتنفيذ شيء من هذا القبيل قائمة مرتبطة أو البديل من ذلك إذا كنت حقا التركيز على هذه الأسس الأساسية، والمشاكل دغة الحجم لا بد لي من معرفة، هل هو هذه اليد أو اليد هذه، ندرك أن ما هو خلاف ذلك برنامج معقدة إلى حد ما يمكن، في الواقع، يمكن تحويلها إلى كتل بناء بسيطة الى حد كبير مثل هذا. دعونا نأخذ الأمور في اتجاه أكثر تطورا حتى الآن. لدينا الآن فكرة القائمة المرتبطة. لدينا أيضا، وذلك بفضل العودة إلى هناك اقتراح واحد في قائمة مرتبطة على نحو مضاعف، التي تبدو تقريبا نفس، ولكن الآن لدينا اثنين من المؤشرات داخل البنية بدلا من واحدة، ويمكن أن نطلق على الأرجح تلك المؤشرات السابقة والقادمة أو إلى اليسار أو اليمين، ولكننا، في الواقع، تحتاج اثنين منهم. ورمز يكون أكثر من ذلك بقليل المعنية. وكان يتعين على أنيتا لبذل المزيد من العمل هنا على المسرح. ولكن يمكننا بالتأكيد تنفيذ هذا النوع من الهيكل. من حيث إدارة الوقت، رغم ذلك، ما من شأنه أن تكون هذه هي المرة تشغيل لأنيتا لإيجاد ن رقم في قائمة مرتبطة الآن؟ O لا تزال كبيرة من ن، لذلك من الأفضل لا يتجاوز البحث الخطي. لا نستطيع أن نفعل البحث الثنائية، رغم ذلك، مرة أخرى. لماذا كان الأمر كذلك؟ لا يمكنك القفز حولها. على الرغم من أننا نرى بوضوح كل البشر على المسرح، ويمكن أن أنيتا قد eyeballed ذلك، وقال: "هنا هو منتصف القائمة،" وقالت إنها لا تعرف أنها إذا كانت برنامج كمبيوتر لأن الشيء الوحيد الذي كان لتحط على لفي بداية السيناريو كان لوكاس، الذي كان المؤشر الأول. وقالت إنها من الضروري أن تتبع هذه الروابط، عد طريقها حتى وجدت ما يقرب من الوسط، وحتى ذلك الحين، وقالت انها لن تعرف عندما يكون وصلت منتصف ما لم تذهب على طول الطريق حتى النهاية لمعرفة كيفية العديد من هناك، ثم تتراجع، والتي من شأنها أن تكون من الصعب جدا إلا إذا كان لديك قائمة مرتبطة على نحو مضاعف من نوع ما. حل بعض مشاكل اليوم، ولكن إدخال الآخرين. ماذا عن بنية بيانات مختلفة تماما؟ هذا هو صورة من الأدراج في البيت ماثر، وفي هذه الحالة، لدينا بنية بيانات قمنا أيضا نوع من سبق الحديث عنه. تحدثنا عن كومة في سياق الذاكرة، وانها نوع من اسمه عمدا لأن ذلك كومة في شروط الذاكرة هي بالفعل بنية البيانات التي لديه المزيد والمزيد من الاشياء الطبقات على أعلى من ذلك. لكن الشيء المثير للاهتمام حول كومة، كما هو الحال في واقع الأمر، هو أنه نوع خاص من بنية البيانات. انها بنية البيانات حيث العنصر الأول في هو العنصر الأخير بها. إذا كنت علبة أول من وضع إلى المكدس، وأنت تسير أن يكون للأسف درج آخر من يتم سحبه من المكدس، وهذا ليس بالضرورة أمرا جيدا. على العكس من ذلك، يمكنك التفكير في الامر على العكس من ذلك، آخر هو في الخروج أولا. الآن، قم بأي سيناريوهات تتبادر إلى الذهن حيث وجود مكدس بنية البيانات التي لديك تلك الممتلكات من آخر في، انتهت الأولى، هو في الواقع مقنعة؟ هو أن هذا شيء جيد؟ هو أن شيئا سيئا؟ انها بالتأكيد شيئا سيئا إذا لم تكن جميع الصواني متطابقة وكانت جميع الألوان المختلفة أو خاصة غيرها، واللون الذي تريده هو على طول الطريق في الأسفل. بالطبع، لا يمكنك الحصول على ذلك دون بذل جهد كبير. عليك أن تبدأ من أعلى والعمل طريقك إلى أسفل. وبالمثل، ماذا لو كنت واحدا من هؤلاء الأولاد من المعجبين الذي ينتظر كل ليلة محاولة للحصول على اي فون ويصطف في مكان مثل هذا؟ لن يكون ذلك جميلا إذا التفاحة مخزن كانت بنية بيانات المكدس؟ ياي؟ ناي؟ انها جيدة فقط بالنسبة للأشخاص الذين تظهر في اللحظة المحتملة الاخيرة ومن ثم الحصول على التقطه من على قائمة الانتظار. في واقع الأمر، فإن حقيقة أن كان يميل لذلك أنا أقول لقائمة الانتظار ويتسق مع الواقع ما نسميه هذا النوع من هيكل البيانات، واحد في الواقع حيث أمر لا يهم، وتريد أول واحد لتكون أول واحد من إذا فقط من أجل العدالة الإنسانية. سوف نسميه عموما أن بنية بيانات قائمة الانتظار. تبين إلى جانب القوائم المرتبطة، يمكننا البدء في استخدام هذه الأفكار الأساسية نفسها والبدء في إنشاء أنواع جديدة ومختلفة من الحلول للمشاكل. على سبيل المثال، في حالة وجود مكدس، يمكن أن تمثل كومة استخدام بنية بيانات من هذا القبيل، وأقترح. في هذه الحالة، قد أعلن لي البنية، وقلت داخل هذا الهيكل هو مجموعة من الأرقام ومن ثم حجم متغير يسمى، وانا ذاهب لاستدعاء هذا الشيء كومة. الآن، لماذا يعمل هذا في الواقع؟ في حالة وجود مكدس، ويمكنني أن يوجه بذلك على نحو فعال على الشاشة كصفيف. هنا كومة بلدي. تلك هي أرقامي. وسوف نوجه لهم كما هذا، هذا، هذا، هذا، هذا. ثم لدي بعض الأعضاء بيانات أخرى هنا، وهو ما يسمى الحجم، لذلك هذا هو الحجم، وهذا هو الأرقام، وجماعيا، تطلب الشركة بأكملها هنا تمثل واحدة بنية المكدس. الآن، بشكل افتراضي، وحجم وقد حصلت يفترض أن تتم تهيئة إلى 0، وما هو داخل مجموعة من الأرقام في البداية عندما تخصص أولا مجموعة؟ القمامة. من يدري؟ وأنه لا يهم في الواقع. لا يهم إذا كانت هذه هي 1، 2، 3، 4، 5، عشوائيا تماما من سوء الحظ المخزنة في هيكل بلدي لطالما أنا أعلم أن حجم المكدس 0، ثم أنا أعرف برمجيا، لا تبدو في أي من العناصر في الصفيف. لا يهم ما هو هناك. لا ننظر إليها، كما سيكون الآثار المترتبة على حجم 0. ولكن لنفترض الآن أنا والمضي قدما في إدراج شيء في المكدس. أريد أن إدراج رقم 5، لذلك أنا وضعت رقم 5 هنا، ثم ما يمكنني اخماد هنا؟ الآن سوف أضع في الواقع بنسبة 1 لحجم، والآن كومة من حجم 1. ماذا لو ذهبت إلى الأمام وإدراج رقم، دعنا نقول، 7 التالي؟ هذا ثم يتم تحديثها إلى 2، ثم سنفعل 9، ومن ثم يحصل على تحديث هذا إلى 3. ولكن ميزة مثيرة للاهتمام من هذا المكدس الآن هو أن أنا من المفترض أن إزالة العنصر الذي إذا أريد لموسيقى البوب شيء الخروج من المكدس، إذا جاز التعبير؟ و9 يكون أول شيء يجب أن تذهب. كيف ينبغي الصورة تتغير إذا أريد لموسيقى البوب ​​عنصر من المكدس، يشبه إلى حد كبير صينية في ماذر؟ نعم. >> [طالب] حجم مجموعة إلى 2. بالضبط، يتم تعيين كل ما أفعله لحجم 2، وماذا أفعل مع مجموعة؟ ليس لدي لفعل أي شيء. ويمكنني أن، لمجرد أن يكون الشرج، ووضع 0 لا أو -1 أو للدلالة على شيء أن هذه ليست قيمة شرعي، ولكن لا يهم لأن لا أستطيع تسجيل خارج مجموعة نفسها كم من الوقت هو لدرجة أنني أعرف ننظر فقط في العنصرين الأول في هذه المجموعة. الآن، وإذا ذهبت إضافة رقم 8 إلى هذه المجموعة، كيف يمكن للتغيير الصورة القادمة؟ هذا يصبح 8، وهذا يصبح 3. أنا قطع زوايا قليلة هنا. الآن لدينا 5 و 7 و 8، ونعود إلى حجم 3. هذا هو بسيط جدا لتنفيذ، ولكن عندما نحن ذاهبون للأسف هذا القرار التصميم؟ متى تبدأ الامور للذهاب للغاية، خاطئة جدا؟ نعم. [رد الطالب غير مسموع] عندما تريد أن تذهب مرة أخرى والحصول على العنصر الأول كنت وضعت فيه. اتضح هنا على الرغم من كومة عبارة عن صفيف تحت غطاء محرك السيارة، وأيضا هذه الهياكل البيانات بدأنا نتحدث عن المعروفة عموما هياكل البيانات المجردة حيث كنت كيفية تنفيذها تماما إلى جانب هذه النقطة. ويفترض ان بنية البيانات مثل كومة لإضافة دعم مثل عمليات الدفع، الذي يدفع صينية إلى المكدس، والبوب، الذي يزيل عنصر من المكدس، وهذا كل شيء. إذا كانت لك بتحميل كود شخص آخر الذين نفذ بالفعل هذا الشيء يسمى كومة، فإن ذلك الشخص قد كتبت وظيفتين فقط بالنسبة لك، ودفع البوب، هدفها الوحيد في الحياة سيكون لذلك تماما. أنت أو له أو لها تنفيذ هذا البرنامج الذي كان تماما واحدة لاتخاذ قرار بشأن كيفية تنفيذ دلالات دفع وظهرت تحت غطاء محرك السيارة أو وظيفة دفع وظهرت. ولقد جعلت قرار قصير النظر نوعا ما هنا من خلال تنفيذ كومة بلدي مع هذه البنية بيانات بسيطة لماذا؟ عندما يفعل ذلك كسر هيكل البيانات؟ في نقطة ما لا بد لي من العودة خطأ عندما يقوم المستخدم دفع يدعو، على سبيل المثال؟ [طالب] إذا لم يكن هناك مساحة أكبر. بالضبط، إذا كان هناك مساحة لا أكثر، إذا كنت قد تجاوزت القدرات، وهو كل مباراة لأنه يوحي أنه نوع من ثابت العالمية. حسنا، ثم أنا فقط ستكون لدينا ليقول "عذرا، لا أستطيع دفع قيمة أخرى إلى المكدس "، يشبه إلى حد كبير في ماذر. في مرحلة ما، انهم ذاهبون لتصل إلى الجزء العلوي من مجلس الوزراء أن قليلا. ليس هناك مساحة أكبر أو القدرات في المكدس، وعند هذه النقطة هناك نوعا من الخطأ. لديهم لوضع العنصر في مكان آخر، في مكان آخر علبة، أو في أي مكان على الإطلاق. الآن، مع قائمة انتظار، فإننا لا يمكن تنفيذه بشكل مختلف قليلا. A قائمة الانتظار قليلا مختلفة في هذا تحت غطاء محرك السيارة، ويمكن تنفيذه كصفيف، ولكن لماذا، في هذه الحالة، أنا اقتراح أن يكون أيضا عنصرا رئيسا يمثل رئيس القائمة، الجزء الأمامي من القائمة، أول شخص في خط في متجر أبل، بالإضافة إلى حجم؟ لماذا أحتاج إلى قطعة إضافية من البيانات هنا؟ فكر في العودة إلى ما هو الأرقام إذا كنت قد رسمها على النحو التالي. لنفترض الآن هذا طابور بدلا من المكدس، الفرق يكون تماما مثل-قائمة الانتظار للتسوق أبل عادلة. أول شخص في خط في بداية القائمة، الرقم 5 في هذه الحالة، هو أو هي على وشك أن تدع إلى المتجر الأول. دعونا نفعل ذلك. لنفترض أن هذا هو حالة قائمة انتظار بلدي في هذه اللحظة من الزمن، والآن متجر أبل ويفتح ويقود أول شخص، عدد 5، إلى المتجر. كيف يمكنني تغيير الصورة الآن أن أكون قد شطب أول شخص في قائمة الانتظار في الجزء الأمامي من الخط؟ ما هذا؟ >> [طالب] تغيير قائمة الانتظار. تغيير الرأس، حتى 5 يختفي. في الواقع، انها كما لو الفنية أفضل للقيام بذلك؟ في الواقع، انها كما لو يختفي هذا الرجل. ما يمكن أن تفعله في رقم 7 مخزن الفعلية؟ فإنها اتخاذ خطوة كبيرة إلى الأمام. ولكن ما وصلنا إلى نقدر عندما يتعلق الأمر صفائف وتتحرك الامور؟ وهذا النوع من مضيعة للوقت الخاص بك، أليس كذلك؟ لماذا يجب أن تكون الشرج وذلك ليكون أول شخص في بداية السطر في بداية وجسديا من قطعة من الذاكرة؟ وهذا لا لزوم لها تماما. لماذا؟ ما يمكن أن أتذكر فقط بدلا من ذلك؟ >> [استجابة الطالب غير مسموع] بالضبط، يمكن أن أذكر فقط مع هذا الرأس عضو بيانات إضافية الآن أن رئيس القائمة لم يعد 0، والذي كان قبل لحظة. الآن انها في الواقع الرقم 1. وبهذه الطريقة، يمكنني الحصول على التحسين طفيفة. لقد لمجرد قمت بعدم شخص من قائمة الانتظار خط في بداية السطر في متجر أبل لا يعني كل من لديه لتحويل، والتي هي عملية الاستدعاء الخطي. يمكنني قضاء الوقت بدلا الثابت الوحيد وتحقيق ثم استجابة أسرع بكثير. ولكن الثمن أنا ما دفع للحصول على أن أداء إضافية وعدم وجود لتحويل جميع؟ نعم. >> [استجابة الطالب غير مسموع] يمكن إضافة المزيد من الناس، حسنا، هذه المشكلة هو متعامد إلى حقيقة أننا لا يتحول الناس من حولنا. انها لا تزال طائفة، لذلك ما إذا كنا تحول الجميع أو لا، أوه، أرى ما تعنيه، حسنا. في الواقع، وأنا أتفق مع ما تقوله من حيث أنه تقريبا كما الرغم ونحن الآن لا تنوي استخدام بدء هذه المجموعة بعد الآن لأنه إذا أزيل 5، ثم أقوم بإزالة 7. ولكن وضعت فقط الناس إلى اليمين. بدا الامر وكأننا أنا إضاعة الفضاء، وأخيرا قائمة انتظار بلدي يتحلل إلى أي شيء على الإطلاق، لذا فإننا يمكن أن يكون مجرد شخص ملفوف، ويمكن أن نفكر في هذه المجموعة حقا على انها نوع من بنية دائرية، ولكننا نستخدم ما في المشغل C للقيام بذلك النوع من ملفوف؟ [رد الطالب غير مسموع] >> المشغل مودولو. سيكون من مزعج قليلا للتفكير من خلال كيف يمكنك أن تفعل للملفوف، ولكن يمكننا أن نفعل ذلك، ونحن يمكن أن تبدأ في وضع الناس ما كان ليكون واجهة الخط، ولكن علينا أن نتذكر فقط مع هذا المتغير الذي رأسه الرئيس الفعلي للخط هو في الواقع. ماذا لو، بدلا من ذلك، هدفنا في نهاية المطاف، على الرغم من وكان للبحث عن الأرقام، كما فعلنا هنا على خشبة المسرح مع أنيتا، لكننا نريد حقا أفضل من كل هذه العوالم؟ نريد المزيد من التطور من مجموعة يسمح لأننا نريد القدرة على النمو بشكل حيوي بنية البيانات. ولكننا لا نريد أن تضطر إلى اللجوء إلى شيء ما أشرنا في المحاضرة الأولى لم يكن خوارزمية الأمثل، أن من البحث الخطي. اتضح أنه يمكنك، في الواقع، تحقيق أو على الأقل قريبة من الوقت مستمر، حيث شخص مثل أنيتا، إذا كانت بتكوين بنية لها أن تكون البيانات غير قائمة مرتبط، لا أن تكون كومة، لا أن تكون قائمة الانتظار يمكن، في الواقع، الخروج مع هيكل البيانات التي يسمح لها للبحث عن الأشياء، حتى الكلمات، وليس مجرد أرقام، في ما نسميه الوقت سوف ثابتة. في واقع الأمر، التطلع، واحدة من psets في هذه الفئة هو دائما تقريبا تنفيذا لالمدقق الإملائي، حيث نقدم لكم مرة أخرى بعض الكلمات الإنجليزية و150،000 الهدف من ذلك هو تحميل إلى الذاكرة تلك ويكون قادرا على الإجابة بسرعة الأسئلة من النموذج وهذه الكلمة مكتوبة بشكل صحيح؟ وسيكون من تمتص حقا إذا كان لديك لتكرار خلال كل الكلمات 150،000 إلى الإجابة على هذا. ولكن، في الواقع، وسنرى ما يمكن أن نفعله في الوقت المناسب جدا وسريعة جدا. وانه سيكون شيئا لإشراك تنفيذ يسمى جدول التجزئة، وعلى الرغم من وهلة الأولى هذا الشيء يسمى جدول التجزئة هو الذهاب الى دعونا تحقيق هذه الاستجابة السريعة سوبر مرات، اتضح أن هناك في الواقع مشكلة. عندما يأتي الوقت لتنفيذ هذا الشيء يسمى من جديد، أنا أفعل ذلك مرة أخرى. أنا واحد فقط هنا. عندما يتعلق الأمر بتنفيذ الوقت دعا هذا الشيء جدول التجزئة، ونحن في طريقنا لدينا لاتخاذ قرار. كيف ينبغي أن يكون هذا الشيء كبيرة في الواقع؟ وعندما نبدأ بإدراج أرقام في هذا الجدول التجزئة، كيف نحن ذاهبون لتخزينها بطريقة التي يمكن أن نحصل عليها العودة بأسرع ما وصلنا لهم في؟ ولكن سنرى قبل مضي وقت طويل أن هذه المسألة من متى عيد ميلاد الجميع هو أن يكون في الصف ثيق جدا. تبين أن في هذه الغرفة، ونحن قد حصلت على بضع مئات من الناس، وبالتالي فإن احتمالات أن اثنين منا لديه نفس عيد ميلاد هو على الارجح عالية جدا. ماذا لو لم يكن هناك سوى 40 من منا في هذه القاعة؟ ما هي احتمالات وجود شخصين في نفس تاريخ الميلاد؟ [الطلاب] أكثر من 50٪. نعم، أكثر من 50٪. في الواقع، حتى أحضرت مخطط. كما تبين وهذا هو في الحقيقة مجرد معاينة التسلل- إذا كان هناك 58 فقط من منا في هذه القاعة، واحتمال 2 منا عيد ميلاد جود نفس مرتفعة بشكل كبير، ما يقرب من 100٪، وهذا ما سوف يؤدي في مجمله مجموعة من يصب لنا يوم الاربعاء. مع أن قال، دعونا تأجيل هنا. سنرى لك يوم الاربعاء. [تصفيق] [CS50.TV]