[Powered by Google Translate] [الأسبوع 6، تابع] [ديفيد J. مالان] [جامعة هارفارد] [هذا CS50.] [CS50.TV] هذا هو CS50 وهذا هو نهاية الأسبوع 6. CS50x ذلك، واحدة من الدورات في جامعة هارفارد اول مشاركة في مبادرة EDX لاول مرة هذا الواقع يوم الاثنين الماضي. إذا كنت ترغب في الحصول على لمحة عما الآخرين على الإنترنت نتابع الآن مع، يمكنك التوجه إلى x.cs50.net. وأن إعادة توجيه إلى المكان المناسب على edx.org، الذي كان فيه هذه وغيرها من الدورات من معهد ماساتشوستس للتكنولوجيا وبيركلي يعيش الآن. سيكون لديك للتسجيل للحصول على حساب؛ ستجد أن المواد هو في حد ذاته كما كنت قد هذا الفصل الدراسي، ولو تأخر بضعة أسابيع، كما حصلنا على كل شيء جاهزا. ولكن ما طالب في CS50x سوف نرى الآن هو واجهة تماما مثل هذا واحد. هذا، على سبيل المثال، هو Zamyla قيادة تجول لمجموعة مشكلة 0. عند تسجيل الدخول إلى edx.org، وهو طالب CS50x يرى أنواع الأشياء هل نتوقع أن نرى في الدورة: المحاضرة ل الإثنين، محاضرة ليوم الأربعاء، والسراويل مختلفة، ومجموعات المشكلة، وكثروو، ملفات PDF. وبالإضافة إلى ذلك، كما ترون هنا ترجمة الآلة، النصوص الإنجليزية إلى اللغة الصينية واليابانية والإسبانية والإيطالية، ومجموعة كاملة من اللغات الأخرى التي ستكون بالتأكيد ناقصة ونحن نقوم بنشرها برمجيا باستخدام شيء يسمى API، أو واجهة برمجة التطبيقات، من جوجل أن يسمح لنا لتحويل الإنجليزية إلى هذه اللغات الأخرى. ولكن بفضل روح رائعة من بعض المتطوعين بالإضافة إلى مائة، عشوائية الناس على شبكة الإنترنت الذين تكرمت على المشاركة في هذا المشروع، سنقوم تدريجيا أن تحسين نوعية تلك الترجمات من خلال وجود البشر تصحيح الأخطاء التي جعلت أجهزة الكمبيوتر لدينا. 

لذلك تبين كان لدينا عدد قليل من أكثر الطلاب تظهر يوم الاثنين مما كنا نتوقع في البداية. في الواقع، والآن لديها 100،000 شخص CS50x بعد طول في المنزل. لذلك أنت تدرك كلها جزء من هذه الفئة الافتتاحية لجعل هذه الدورة في علوم الكمبيوتر التعليم بشكل عام، على نطاق أوسع، يمكن الوصول إليها. والواقع الآن، مع بعض من الدورات على الانترنت هذه واسع، أن تبدأ مع كل هذه الأرقام عالية جدا، ويبدو أننا قد فعلت هنا. لكن الهدف في نهاية المطاف، هو في الحقيقة لCS50x للحصول على الناس ما يصل إلى خط النهاية ممكن. حسب التصميم، CS50x ستكون هذه المقدمة من يوم الاثنين الماضي على طول الطريق من خلال 15 أبريل 2013، بحيث الناس الذين لديهم التزامات المدرسة في مكان آخر، العمل، والأسرة، وصراعات أخرى مثل، لديها مرونة أكثر قليلا التي ليغوص في هذه الدورة، والتي، ويكفي ان نقول، وطموح جدا القيام به إلا إذا على مدى ثلاثة أشهر فقط خلال الفصل الدراسي المعتاد. ولكن هؤلاء الطلاب أن معالجة مجموعات نفس المشكلة، وعرض نفس المحتوى، بعد الوصول إلى نفس السراويل وما شابه ذلك. بحيث يدرك في الواقع كلنا في هذا معا. وأحد الأهداف نهاية CS50x ليس فقط للحصول على ما يصل الناس الى خط النهاية ومنحهم هذا الفهم المكتشف حديثا في علوم الحاسب الآلي والبرمجة ولكن أيضا ليكون لهم خوض هذه التجربة المشتركة. واحدة من الخصائص المميزة من 50 في الحرم الجامعي، ونحن نأمل، وكان هذا النوع من الخبرة الجماعية، للأفضل أو للأسوأ، في بعض الأحيان، ولكن وجود هؤلاء الناس إلى اللجوء إلى إلى اليسار وإلى اليمين، ساعات العمل وhackathon والمعرض و. انها قليلا من الصعب القيام بذلك في شخص مع الناس عبر الإنترنت، ولكن سوف تختتم في أبريل CS50x مع أول معرض CS50 من أي وقت مضى، والتي سوف يكون التكيف على شبكة الإنترنت من فكرتنا للمعرض وحيث كل هذه الآلاف من الطلاب أن يدعى أن يقدم 1 - ل2-دقائق الفيديو، إما سكرينكست من مشروعهم النهائي أو الفيديو منهم يلوحون مرحبا والحديث عن المشروع وdemoing ذلك، لقد فعلت الكثير مثل أسلافكم هنا في الحرم الجامعي في المعرض، بحيث في نهاية الفصل الدراسي، فإن الأمل هو أن يكون لها معرض عالمي مشاريع الطلاب CS50x 'النهائي، مثل الكثير من ما ينتظرك في كانون الاول هنا في الحرم الجامعي. أكثر من ذلك على أنه في الأشهر القادمة. 

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

علوم الحاسب الآلي المقررات في جامعة هارفارد لديها قليلا من التقليد، CS50 من بينها، وجود بعض الملابس، وبعض الملابس، التي يمكنك ارتداء بفخر في نهاية الفصل الدراسي، قائلا بفخر جدا التي انتهت CS50 واستغرق CS50 وما شابه ذلك، ونحن دائما في محاولة لإشراك الطلاب في هذه العملية إلى أقصى حد ممكن، حيث ندعو، حول هذا الوقت من الفصل الدراسي، والطلاب لتقديم التصاميم باستخدام برنامج فوتوشوب، أو أيا كان الأداة المفضلة كنت ترغب في استخدام إذا كنت مصمم، لتقديم تصاميم للقمصان وبلوزات-T والمظلات وعصابات صغيرة للكلاب لدينا الآن وما شابه ذلك. وبعد ذلك كل شيء - ثم يتم عرض الفائزين كل عام على الموقع الإلكتروني للدورة لفي store.cs50.net. كل شيء يباع بسعر التكلفة هناك، لكن الموقع يعمل فقط في حد ذاته ويتيح للناس لاختيار الألوان والتصاميم التي يحلو لهم. حتى ظننت أننا سوف تشارك سوى بعض من التصاميم العام الماضي وذلك على الموقع الإلكتروني إلى جانب هذا واحد هنا، وهو تقليد سنوي. "كل يوم أنا SEG Faultn" كان واحدا من التقارير العام الماضي، التي لا تزال متاحة للخريجين هناك. كان لدينا هذا واحد، "CS50، التي تأسست عام 1989." كان واحدا من Bowdens لدينا، روب، بشعبية كبيرة في العام الماضي. "فريق بودين" ولدت، وقدم هذا التصميم، من بين الأكثر مبيعا. كما كان هذا واحد هنا. كان كثير من الناس "حمى بودين" وفقا لسجلات المبيعات. ندرك أن هذا يمكن أن يكون هناك الآن التصميم الخاص بك، حتى على الإنترنت. مزيد من التفاصيل حول هذه المشكلة القادمة في مجموعات قادمة. 

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

لذلك نحن على قدم style50 اليوم الآخر، الذي هو أداة سطر الأوامر قصيرة الذي يحاول أسلب التعليمات البرمجية قليلا أكثر نظافة مما كنت، والإنسان، قد فعلت. ولكن هذا، أيضا، هو في الحقيقة مجرد شيء الجمالية. ولكن تبين أن هناك أداة أخرى تسمى هذه Valgrind وهذا هو أكثر من ذلك بقليل غامضة للاستخدام. هو خفي انتاجها حشية للوهلة الأولى. ولكن من المفيد رائعة، خاصة الآن أننا في جزء من مصطلح حيث كنت بدأت لاستخدام malloc ودينامية تخصيص الذاكرة. يمكن تسير الأمور حقا، حقا الخطأ بسرعة. لأنه إذا كنت قد نسيت لتحرير الذاكرة الخاصة بك، أو يمكنك إلغاء مرجعية بعض مؤشر NULL، أو يمكنك إلغاء مرجعية بعض مؤشر القمامة، ما هو عادة أعراض التي تنتج؟ SEG خطأ. وتحصل هذا الملف الأساسية لبعض عدد من كيلو بايت أو ميغابايت الذي يمثل حالة الذاكرة لديك برنامج عندما تحطمت، ولكن في نهاية المطاف برنامج SEG أخطاء، خطأ تجزئة، وهو ما يعني شيئا سيئا حدث دائما تقريبا المرتبطة لخطأ المتعلقة بالذاكرة التي قمت بها في مكان ما. حتى Valgrind يساعدك على العثور على أشياء مثل هذه. انها الأداة التي تقوم بتشغيل، مثل GDB، بعد أن كنت قد جمعت البرنامج الخاص بك، ولكن بدلا من تشغيل البرنامج مباشرة، يمكنك تشغيل Valgrind ويمكنك تمرير إليه البرنامج الخاص بك، تماما كما تفعل مع GDB. الآن، استخدام، للحصول على أفضل نوع من الإخراج، قليلا طويل، لذلك هناك حق على قمة من الشاشة سترى Valgrind-V. "-V" عالميا تقريبا يعني مطول عندما كنت تستخدم برامج على جهاز كمبيوتر لينكس. لذلك يعني بصق المزيد من البيانات مما كنت قد افتراضيا. "- تسرب تسجيل الوصول = كامل." هذا هو الاختيار فقط أقول للجميع الثقوب الذاكرة ممكن، الأخطاء التي كنت قد أجريتها. هذا، أيضا، هو نموذج مشتركة مع برامج لينكس. عموما، إذا كان لديك حجة سطر الأوامر هذا هو "مفتاح"، من المفترض أن يتغير سلوك البرنامج، وانها حرف واحد، انها-V، ولكن اذا كان هذا تحول، فقط من خلال تصميم مبرمج، وكلمة كاملة أو سلسلة من الكلمات، وسيطة سطر الأوامر يبدأ -. هذه ليست سوى الاتفاقيات الإنسان، ولكن عليك رؤيتهم على نحو متزايد. ومن ثم، أخيرا، "a.out" هو اسم التعسفي للبرنامج في هذا المثال بالذات. وهنا بعض الانتاج ممثل. 

قبل أن ننظر إلى ما قد يعني، اسمحوا لي ان اذهب الى مقتطف من التعليمات البرمجية أكثر من هنا. واسمحوا لي أن نقل هذا للخروج من الطريق، قريبا، ودعونا نلقي نظرة على memory.c، وهو هنا هذا المثال قصيرة. حتى في هذا البرنامج، اسمحوا لي أن التكبير في وظائف والأسئلة. لدينا المهمة الرئيسية التي يستدعي دالة، و، ثم ماذا و الشروع في القيام به، باللغة الإنجليزية التقنية قليلا؟ ماذا المضي قدما و أن تفعل؟ ماذا عن سأبدأ مع خط 20، وموقع النجم لا يهم، ولكن سأكون هنا فقط بما يتفق مع محاضرة الماضي. ما هو خط 20 لا بالنسبة لنا؟ على الجانب الأيسر. سنقوم كسرها نزولا أخرى. * الباحث X: ماذا تفعل ان؟ حسنا. انها اعلان المؤشر، والآن دعونا أن يكون أكثر تقنية. ماذا يعني ذلك، بشكل ملموس جدا، للإعلان عن المؤشر؟ شخص آخر؟ نعم؟ [الجواب طالبة، غير مفهومة] بعيدا جدا. لذلك كنت تقرأ إلى الجانب الأيمن من علامة المساواة. دعونا نركز فقط على اليسار، فقط على X * INT. هذا لا "تعلن" مؤشر، ولكن الآن دعونا الغوص في أعمق لهذا التعريف. ماذا أن ملموس، من الناحية الفنية يعني؟ نعم؟ [الجواب طالبة، غير مفهومة] حسنا. انها تستعد لحفظ عنوان في الذاكرة. جيدة. ودعونا اتخاذ هذه الخطوة واحدة أخرى، بل يعلن متغير، X، وهذا 32 بت. وأنا أعلم أنه 32 بت لأنه -؟ انها ليست بسبب انها الباحث، لأنه مؤشر في هذه الحالة. صدفة أنه من واحدة واحدة مع الباحث، ولكن الحقيقة أن هناك نجم تعني أن هناك هو مؤشر وفي الأجهزة، كما هو الحال مع العديد من أجهزة الكمبيوتر، ولكن ليس كل شيء، هي مؤشرات 32 بت. على الأجهزة أكثر حداثة مثل أحدث أجهزة ماكينتوش، أحدث أجهزة الكمبيوتر، قد يكون لديك 64-بت المؤشرات، ولكن في الأجهزة، وهذه الأمور هي 32 بت. ولذا فإننا سوف توحيد على ذلك. أكثر تحديدا، فإن القصة على النحو التالي: نحن "إعلان" مؤشر؛ ماذا يعني ذلك؟ نحن نستعد لتخزين عنوان ذاكرة. ماذا يعني ذلك؟ نقوم بإنشاء متغير يسمى X أن يستغرق 32 بت والتي تقوم بتخزين عنوان قريبا عدد صحيح. وهذا على الأرجح نحو دقيقة كما يمكننا الحصول عليها. أنه بخير المضي قدما لتبسيط العالم، وأقول فقط أن يعلن مؤشر يسمى X. إعلان المؤشر، ولكن ندرك ونفهم ما يجري في الواقع على حتى في تلك الأحرف قليلة. 

الآن، هذا واحد تقريبا أسهل قليلا، على الرغم من انها تعد التعبير. فما هو هذا العمل، وهذا أبرز الآن: "malloc (10 * sizeof (الباحث))؛" نعم؟ [الجواب طالبة، غير مفهومة] جيدة. وأنا أعتبر هناك. انها قطعة من تخصيص الذاكرة لمدة عشرة أعداد صحيحة. والآن دعونا الغوص أعمق قليلا في، بل تخصيص جزء من الذاكرة لمدة عشرة أعداد صحيحة. ما malloc العودة بعد ذلك؟ عنوان ذلك قطعة، أو، على نحو أكثر تحديدا، عنوان البايت الأول من أن قطعة. فكيف أنا، مبرمج، أن تعرف أين ينتهي ذلك قطعة من الذاكرة؟ وأنا أعلم أنه من متجاورة. Malloc، بحكم تعريفها، وسوف أعطيك قطعة متجاورة من الذاكرة. أي ثغرات فيه. لديك حق الوصول إلى كل بايت في أن قطعة، العودة إلى الوراء لدعم، ولكن كيف أعرف أين نهاية هذا جزء من الذاكرة؟ عند استخدام malloc؟ [الجواب طالبة، غير مفهومة] جيد. كنت لا. عليك أن تتذكر. ولا بد لي من أن نتذكر أن كنت القيمة 10، وأنا لا يبدو حتى فعلت ذلك هنا. ولكن المسؤولية تقع كليا على البيانات. التوابع strlen، والتي أصبحنا تعتمد قليلا على سلاسل، يعمل فقط بسبب وجود هذه الاتفاقية \ 0 أو هذه الشخصية الاستثنائية NUL، NUL، في نهاية سلسلة. أن لا تعقد لمجرد قطع التعسفي من الذاكرة. والامر متروك لك. حتى خط 20، وبعد ذلك، يخصص جزءا من الذاكرة يمكن أن تخزن 10 أعداد صحيحة، وأنه يخزن عنوان البايت الأول هذا جزء من الذاكرة في x متغير يسمى. ولهذا، وهو مؤشر. حتى خط 21، للأسف، كان خطأ. ولكن أولا، ما هو به؟ قائلا انه مخزن في الموقع 10، 0 فهرسة، من قطعة من الذاكرة يسمى X القيمة 0. 

لاحظت ذلك بضع الامور تسير على. على الرغم من أن x هو مؤشر واستدعاء من قبل بضعة أسابيع يمكن أن يزال بإمكانك استخدام مجموعة قوس مربع على غرار تدوين. لأن هذا هو الواقع مختزلة تدوين لأكثر الحسابية مؤشر خفي المظهر. حيث كنا نفعل شيئا مثل هذا: خذ X العناوين، قم بتحريك أكثر من 10 نقاط، ثم انتقل إلى أي عنوان هناك يتم تخزين في ذلك الموقع. ولكن بصراحة، هذا هو فظيعة فقط لقراءة والحصول على مريحة مع. لذلك يستخدم عادة في العالم المعقوفتين فقط لأنها أكثر من ذلك بكثير البشرية صديقة للقراءة. ولكن هذا ما يحدث في الواقع تحت غطاء محرك السيارة؛ X هو عنوان، وليس مجموعة، في حد ذاتها. لذلك هذا هو تخزين 0 في الموقع 10 في العاشر. لماذا هذا سيء؟ نعم؟ [الجواب طالبة، غير مفهومة] بالضبط. ونحن خصصت عشرة فقط رجات، ولكن نحن نعول من 0 عند البرمجة في C، حتى تتمكن من الحصول على 0 10 1 2 3 4 5 6 7 8 9، ولكن لا. إما ذلك البرنامج هو الذهاب الى خطأ SEG أو أنه غير. لكننا لا نعرف حقا، وهذا هو نوع من السلوك غير الحتمي. انها حقا يتوقف على ما إذا كنا محظوظين الحصول على. إذا تبين أن نظام التشغيل لا تمانع في أن استخدام هذه بايت إضافية، على الرغم من أنها لم تعط لي، قد برنامجي لا يتلف. انها الخام، فإنه من عربات التي تجرها الدواب، ولكن قد لا يرى أن أعراض، أو قد تشاهد مرة واحدة فقط في كل حين. ولكن الواقع هو أن الخطأ هو، في الواقع، هناك. وانها حقا مشكلة إذا كنت قد كتبت البرنامج الذي تريد أن يكون صحيحا، لقد بعت لك أن البرنامج الذي تستخدمه الناس أن كل مرة واحدة في حين تعطل لأنه، بطبيعة الحال، هذه ليست جيدة. في الواقع، إذا كان لديك هاتف يعمل بنظام Android أو iPhone على وتقوم بتحميل تطبيقات هذه الأيام، إذا كنت من أي وقت مضى التطبيق إنهاء فقط، فجأة يختفي، وهذا دائما تقريبا نتيجة لبعض المسألة المتعلقة بالذاكرة، حيث مبرمج ثمل وألغى الإشارة القيمة مؤشر انه او انها لا ينبغي أن يكون، ونتيجة لدائرة الرقابة الداخلية أو الروبوت هو قتل للتو البرنامج تماما بدلا من السلوك غير معروف خطر أو نوع من التسوية الأمنية. 

هناك واحد علة أخرى في هذا البرنامج إلى جانب هذا واحد. ماذا وأنا ثمل في هذا البرنامج؟ أنا لم تمارس ما كنت بشر. نعم؟ [الجواب طالبة، غير مفهومة] جيد. أنا لم تحرير الذاكرة. لذلك وبحكم التجربة الآن يجب أن يكون في أي وقت استدعاء malloc، يجب عليك الكلمة الحرة عندما تنتهي باستخدام تلك الذاكرة. الآن، وعندما أريد أن تحرير هذه الذاكرة؟ ربما، على افتراض هذا السطر الأول كان صحيحا، أريد أن نفعل ذلك هنا. لأن لم أستطع، على سبيل المثال، هل عليه هنا. لماذا؟ فقط من النطاق. حتى على الرغم من أننا نتحدث عن مؤشرات، هذا هو الأسبوع 2 أو 3 المسألة، حيث x هو فقط في نطاق داخل الأقواس المتعرجة يعلن فيه. حتى تتمكن من تحرير بالتأكيد ليست هناك. فرصتي الوحيدة لتحريرها هو تقريبا بعد خط 21. هذا هو برنامج بسيط إلى حد ما، بل كان من السهل إلى حد ما بمجرد النوع من عقلك ملفوفة حول ما يفعل البرنامج، حيث كانت الأخطاء. وحتى لو كنت لا ترى ذلك في البداية، ونأمل أنه من الواضح الآن قليلا التي تحل بسهولة جدا هذه الاخطاء وجعل بسهولة. ولكن عندما كان البرنامج أكثر من 12 خطوط طويلة، انها 50 خطوط طويلة، 100 طوابير طويلة، المشي من خلال سطر التعليمات البرمجية الخاصة بك عن طريق الخط، من خلال ذلك التفكير منطقيا، من الممكن ولكن ليس متعة خاصة للقيام، وتبحث باستمرار عن الخلل، وكما انها من الصعب القيام به، وهذا هو السبب أداة مثل Valgrind موجود. اسمحوا لي أن نمضي قدما ونفعل ذلك: اسمحوا لي أن فتح نافذتي المحطة، واسمحوا لي أن لا تعمل فقط الذاكرة، لأن الذاكرة يبدو أن يكون على ما يرام. انني اتلقى محظوظا. الذهاب الى أن البايت إضافية في نهاية الصفيف لا يبدو أن إشكالية للغاية. ولكن اسمحوا لي، مع ذلك، القيام فحص سلامة العقل، مما يعني فقط للتحقق أم لا هذا هو في الواقع الصحيح. 

لذلك دعونا نفعل valgrind-V - تسرب تسجيل الوصول = كامل، وفوق اسم البرنامج في هذه الحالة هو الذاكرة، وليس a.out. لذلك اسمحوا لي نمضي قدما ونفعل ذلك. ضرب أدخل. عزيزي الله. هذا هو انتاجها، وهذا ما ألمح إليها سابقا. ولكن، إذا كنت تعلم القراءة من خلال كل من الهراء هنا، معظم هذه المخرجات مجرد التشخيص التي ليست للاهتمام. ما عينك يريد حقا أن تبحث عن أي ذكر للخطأ أو غير صالحة. الكلمات التي توحي مشاكل. وبالفعل، دعونا نرى ما يحدث خطأ هنا إلى أسفل. لدي ملخص من نوع ما، "المستخدمة في الخروج: 40 بايت في 1 كتل" انا فعلا لست متأكدا ما هو كتلة حتى الآن، ولكن 40 بايت يشعر فعلا وكأنني قد معرفة من أين الذي سيأتي من. 40 بايت. لماذا 40 بايت المستخدمة في الخروج؟ وبشكل أكثر تحديدا، واذا كنا هنا انتقل لأسفل، لماذا فقدت بالتأكيد 40 بايت؟ نعم؟ [الجواب طالبة، غير مفهومة] الكمال. نعم، بالضبط. كان هناك عشرة أعداد صحيحة، وتلك هي كل من حجم 4 أو 32 بت، حتى لقد فقدت بالتحديد 40 بايت، لأنه كما كنت اقترح، وأنا لم يطلق مجانا. هذا واحد علة، والآن دعونا ننظر إلى أسفل أبعد قليلا ونرى بجانب هذا، "غير صالحة للكتابة حجم 4". الآن ما هو هذا؟ ويعبر عن هذا العنوان ما تدوين قاعدة، على ما يبدو؟ هذا هو الأساس السادس عشري، وأي وقت ترى عددا بدءا 0x، فهذا يعني الست عشرية، وهذا ما فعلناه في طريق العودة في القسم pset 0 هذا، كما أعتقد، من الأسئلة، الذي كان فقط للقيام بعملية الاحماء، وتحويل عشري إلى عشري إلى ثنائي وهكذا دواليك. الست عشرية، فقط من خلال اتفاقية الإنسان، وعادة ما يستخدم لتمثيل مؤشرات أو، بشكل أعم، يتناول. انها مجرد الاتفاقية، لأنه أسهل قليلا لقراءة، انها قليلا أكثر إحكاما من شيء من هذا القبيل العشرية، وثنائي لا طائل منه بالنسبة لمعظم البشر للاستخدام. حتى الآن ماذا يعني هذا؟ حسنا، يبدو أن هناك على الكتابة غير صالحة من حجم 4 على خط 21 من memory.c. لذلك دعونا نعود إلى خط 21، والواقع، وهنا أن الكتابة غير صالحة. حتى Valgrind لن يعقد تماما يدي وتقول لي ما هو الإصلاح، ولكنه كشف عن أن أفعله لكتابة صالح. أنا لمس 4 بايت أنني لا ينبغي أن يكون، وذلك لأن ما يبدو، كما كنت أوضح، أنا أفعل [10] بدلا من [9] الحد الأقصى أو [0] أو شيء بين بين. مع Valgrind، وتحقيق أي وقت كنت تكتب الآن برنامج يستخدم المؤشرات ويستخدم الذاكرة، وmalloc بشكل أكثر تحديدا، بالتأكيد الحصول على في العادة من تشغيل هذا طويل ولكن من السهل جدا نسخ ولصق قيادة Valgrind لمعرفة إذا كان هناك بعض الأخطاء في هناك. وأنها سوف تكون ساحقة في كل مرة تشاهد الإخراج، ولكن فقط من خلال تحليل كل بصريا من الانتاج ومعرفة ما اذا كنت ترى يذكر من الأخطاء أو تحذيرات أو غير صالحة أو فقدت أي الكلمات التي يبدو وكأنه ثمل كنت في مكان ما. حتى ندرك أن هذا أداة جديدة في مجموعة أدوات الخاص بك. 

الآن يوم الاثنين، كان لدينا مجموعة كاملة من الناس يأتون إلى هنا وتمثل فكرة وجود قائمة مرتبطة. وقدمنا ​​قائمة مرتبطة كحل لمشكلة ما؟ نعم؟ [الجواب طالبة، غير مفهومة] جيد. يمكن صفائف يكن لديك ذاكرة إضافتها. إذا كنت تخصيص مجموعة من حجم 10، هذا كل ما تحصل عليه. يمكنك استدعاء دالة مثل realloc إذا كنت تسمى في البداية malloc، ويمكن أن تنمو في محاولة لمجموعة إذا كان هناك مساحة نحو نهاية لها أن لا أحد آخر يستخدم، وإذا كان هناك لم يكن كذلك، سوف تجد فقط لأنك أكبر قطعة في مكان آخر. ولكن بعد ذلك سوف نسخ جميع تلك بايت في مجموعة جديدة. هذا يبدو وكأنه الحل الصحيح للغاية. لماذا هذا غير جذابة؟ أعني أنها تعمل، وتحل هذه المشكلة البشر. لماذا نحن بحاجة لحلها يوم الاثنين مع القوائم المرتبطة؟ نعم؟ [الجواب طالبة، غير مفهومة] ويمكن أن يستغرق وقتا طويلا. في الواقع، في أي وقت كنت تتصل malloc أو calloc أو realloc، وهو آخر واحد، أي وقت كنت، برنامج، نتحدث إلى نظام التشغيل، كنت تميل إلى إبطاء البرنامج لأسفل. وإذا كنت تريد ان تفعل مثل هذه الامور في الحلقات، وكنت حقا تباطؤ الأمور. أنت لن تلاحظ هذه لأبسط برامج "مرحبا العالم" النوع، ولكن في برامج أكبر بكثير، وطلب نظام التشغيل مرة أخرى ومرة ​​أخرى للذاكرة أو اعطاء إعادته مرة أخرى ومرة ​​أخرى لا يميل إلى أن يكون شيئا جيدا. بالاضافة الى ذلك، انها مجرد نوع من فكريا - انها مضيعة للوقت. لماذا تخصيص الذاكرة أكثر وأكثر، كل شيء في خطر نسخ مجموعة جديدة، إذا كان لديك بديل يتيح لك تخصيص الذاكرة فقط بقدر ما كنت تحتاج بالفعل؟ ولذلك لا يوجد إيجابيات وسلبيات هنا. واحدة من الإيجابيات الآن أن لدينا دينامية. لا يهم حيث قطع من الذاكرة التي هي حرة، ويمكنني أن مجرد نوع من إنشاء هذه فتات الخبز عن طريق مؤشرات لسلسلة حياتي قائمة مرتبطة معا. لكنني على الأقل دفع سعر واحد. 

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

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

اسمحوا لي أن تمضي قدما وفتح بعض التعليمات البرمجية المثال هنا. أنا فتح gedit، واسمحوا لي أن فتح ملفين الأول. واحد هو list1.h، واسمحوا لي أن أذكر فقط أن هذا هو جزء من التعليمات البرمجية أن كنا يمثل عقدة. A عقدة على حد سواء ودعا الباحث ن ومؤشر يسمى المقبل الذي يشير فقط إلى الشيء التالي في القائمة. التي هي الآن في ملف ح. لماذا؟ هناك هذه الاتفاقية، ونحن لم يستفاد من هذه كمية كبيرة أنفسنا، ولكن الشخص الذي كتب ظائف printf وغيرها وقدم كهدية للعالم كل تلك الوظائف من خلال كتابة ملف يسمى stdio.h. وبعد ذلك هناك string.h، وبعد ذلك هناك map.h، وهناك كل هذه الملفات ح قد رأيتم أو المستعملة خلال فترة كتابة من قبل أشخاص آخرين. عادة في تلك ملفات ساعة فقط من الأشياء مثل typedefs أو إعلانات ذات الأنواع المخصصة أو إعلانات من الثوابت. كنت لا تضع تطبيقات المهام "في ملفات الرأس. كنت وضعت، بدلا من ذلك، فقط على النماذج. كنت وضعت الأشياء التي ترغب في مشاركتها مع العالم ما يحتاجون إليه من أجل ترجمة التعليمات البرمجية الخاصة بهم. فقط حتى للوصول الى هذه العادة، قررنا أن تفعل الشيء نفسه. ليس هناك الكثير في list1.h، ولكن لقد وضعنا شيء من الممكن أن تكون ذات فائدة للناس في العالم الذين يريدون استخدام تنفيذنا القائمة المرتبطة. الآن، في list1.c، وأنا لن تذهب من خلال هذا كل شيء لأنها طويلة بعض الشيء، وهذا البرنامج، ولكن دعونا تشغيله بسرعة حقيقية في موجه. اسمحوا لي أن تجميع list1، اسمحوا لي ثم تشغيل list1، وسترى ما هو قمنا محاكاة برنامج بسيط قليلا هنا وهذا سوف اسمحوا لي أن إضافة وإزالة الأرقام إلى القائمة. لذلك اسمحوا لي المضي قدما واكتب 3 لقائمة 3 الخيار. أريد أن إدراج رقم - دعونا نفعل الرقم الأول، الذي كان 9، والآن أنا قلت للقائمة الآن 9. اسمحوا لي أن نمضي قدما ونفعل آخر الإدراج، لذلك أنا ضربت خيار القائمة 3. ما عدد لا أريد أن أدخل؟ 17. دخول. وسأفعل واحد فقط أكثر من ذلك. اسمحوا لي أن إدراج رقم 22. لذلك لدينا بدايات قائمة مرتبطة التي كانت لدينا في شكل الشريحة قبل لحظة. وكيف يتم هذا الإدراج يحدث بالفعل؟ في الواقع، 22 هو الآن في نهاية القائمة. حتى قصة قيل لنا على خشبة المسرح يوم الاثنين وrecapped الآن فقط يجب في الواقع أن يحدث في التعليمات البرمجية. دعونا نلقي نظرة. اسمحوا لي أن انتقل لأسفل في هذا الملف. سنقوم يتستر على بعض الوظائف، ولكن سوف نذهب إلى أسفل، ويقول، إدراج وظيفة. 

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

خلاف ذلك، وأنا أقول للمستخدم أن تعطيني رقم إلى إدراج، أدعو GetInt صديقنا القديم، ومن ثم كان هذا بناء الجملة الجديدة قدمنا ​​يوم الاثنين. 'newptr-> ن' يعني اتخاذ العنوان الذي قدمت لك من قبل malloc وهو ما يمثل البايت الأول من كائن عقدة جديدة، ثم انتقل إلى حقل يسمى ن. A شك التوافه: وهذا يعادل ما خفي الخط أكثر من التعليمات البرمجية؟ كيف يمكن آخر وقد كتبت هذا؟ تريد أن تأخذ طعنة؟ [الجواب طالبة، غير مفهومة] جيدة. باستخدام ن.، ولكنها ليست بهذه البساطة تماما هذا. ما الذي أحتاجه أول من يفعل؟ [الجواب طالبة، غير مفهومة] جيدة. ولست بحاجة للقيام * newptr.n. ولذلك فإن هذا المؤشر الجديد يقول من الواضح عنوان. لماذا؟ لأنه عاد من قبل malloc. وnewptr * قائلا "الذهاب إلى هناك" ثم مرة كنت هناك، ثم يمكنك استخدام أكثر دراية. ن، ولكن هذا يبدو قليلا القبيح، وخاصة إذا نحن البشر تسير على رسم المؤشرات مع السهام في كل وقت، والعالم لديه موحدة على هذا التدوين السهم، والتي لا بالضبط نفس الشيء. لذلك أنت فقط استخدام -> تدوين عندما شيء على اليسار هو المؤشر. وإلا، إذا انها البنية الفعلية، استخدم ن. ثم هذا: لماذا تهيئة newptr-> التالي إلى NULL؟ نحن لا نريد يد التعلق توقفت في نهاية المرحلة. نريد لها على التوالي إلى الانخفاض، مما يعني نهاية هذه القائمة من المحتمل أن تكون في هذه العقدة، لذلك نحن أفضل تأكد من NULL. وبشكل عام، تهيئة المتغيرات الخاصة بك أو أعضاء البيانات والبنيات إلى شيء من الممارسة مجرد جيدة. مجرد السماح القمامة الوجود والاستمرار في الوجود عموما يحصل لك في ورطة إذا كنت قد نسيت أن تفعل شيئا في وقت لاحق. 

وهنا عدد قليل من الحالات. هذا، مرة أخرى، هي وظيفة إدراج، وأول ما تحقق من وجود المتغير هو إذا دعا الأولى، هذا المتغير العالمي NULL، وهذا يعني عدم وجود قائمة مرتبطة. نحن لم تدرج أي أرقام، لذلك فمن تافهة لإدراج هذه العدد الحالي في القائمة، لأنه ينتمي فقط في بداية القائمة. هذا وكان ذلك عندما كان يقف أنيتا فقط هنا وحده، والتظاهر كان أي شخص آخر هنا على خشبة المسرح إلى أن تخصيص عقدة، ثم قالت انها يمكن ان تثير يدها لأول مرة، إذا كان الجميع الخروج على المسرح بعد لها يوم الاثنين. هنا الآن، وهذا هو الاختيار صغيرة حيث يجب أن أقول إذا كانت العقدة الجديدة قيمة n و<قيمة n في أول عقدة الحالي، وهذا يعني وجود قائمة مرتبطة هذا ما بدأت. هناك عقدة واحدة على الأقل في القائمة، ولكن هذا الرجل الجديد ينتمي المعروضة عليها، لذلك نحن بحاجة لتحريك الأمور حولها. وبعبارة أخرى، إذا كان قد بدأ مع قائمة فقط، دعنا نقول، مجرد رقم 17، وهذا هو - في الواقع، يمكننا أن نفعل هذا بشكل أكثر وضوحا. إذا بدأنا قصتنا مع مؤشر أول من دعا هنا، والبداية انها NULL، ونحن إدراج رقم 9، الرقم 9 ينتمي بوضوح في بداية القائمة. لذلك دعونا نتظاهر نحن malloced مجرد عنوان أو رقم 9 ووضعها هنا. إذا الأول هو 9 من الافتراضي، السيناريو الأول ناقشنا يعني فقط نقطة دعونا هذا الرجل هنا، كما ترك هذا NULL، والآن لدينا عدد 9. الرقم التالي نريد لادخال هو 17. 17 ينتمي إلى هنا، لذلك نحن ستكون لدينا للقيام ببعض خطوة منطقية من خلال هذا. لذلك دعونا بدلا من ذلك، قبل ان نفعل ذلك، دعونا نتظاهر اننا نريد لإدراج رقم 8. 

ذلك فقط لسهولة التناول، وأنا ذاهب لرسم هنا. ولكن تذكر، ويمكن وضعه malloc أكثر في أي مكان. ولكن لاجل الرسم، وسوف أضع هنا. التظاهر حتى لقد خصصت فقط عقدة لعدد 8، وهذا هو NULL بشكل افتراضي. ما يحدث الآن أن؟ زوجان من الأشياء. حققنا هذا الخطأ على خشبة المسرح يوم الاثنين حيث أننا تحديث مؤشر من هذا القبيل، ثم فعل ذلك، وادعى بعد ذلك نحن - ونحن اليتامى الجميع على خشبة المسرح. لأنك can't - ترتيب العمليات هنا أمر مهم، لأنه الآن فقدنا هذه 9 العقدة التي ليست سوى نوع من العائمة في الفضاء. لذلك كان هذا ليس هو النهج الصحيح يوم الاثنين. علينا أولا أن تفعل شيئا آخر. حالة العالم يبدو مثل هذا. في البداية، تم تخصيص 8. ماذا سيكون أفضل طريقة لإدراج 8؟ بدلا من تحديث هذا المؤشر الأول، هذا واحد فقط تحديث هنا بدلا من ذلك. لذلك نحن بحاجة سطر من التعليمات البرمجية التي يجري تحويل هذه الشخصية NULL في مؤشر الفعلية هذا ما يشير إلى العقدة 9، وبعد ذلك يمكننا تغيير بأمان أول من أشار إلى هذا الرجل هنا. الآن لدينا قائمة، قائمة مرتبطة، من عنصرين. وماذا يعني هذا ننظر في الواقع مثل هنا؟ إذا نظرنا إلى رمز، لاحظ أن فعلت بالضبط. قلت newptr، وفي هذه القصة، كان لافتا في newptr هذا الرجل. 

لذلك اسمحوا لي أن ألفت شيئا، وأنني يجب أن الغرفة لم يقم أكثر من ذلك بقليل لهذا الغرض. فاغفر الرسم الصغير للغاية. ويسمى هذا الرجل newptr. وهذا هو المتغير أعلنا بضعة أسطر في وقت سابق، وذلك تمشيا - فقط فوق 25. وانها لافتا إلى 8. لذلك عندما أقول newptr-> التالي، وهذا يعني الانتقال إلى البنية وأشار أن يجري في newptr من قبل، لذلك نحن هنا، اذهب هناك. ثم سهم يقول حصول على الحقل التالي، ثم يقول = قيمة ما وضع هناك؟ القيمة التي كانت في الأول؛ ما كان في قيمة الأولى؟ وكان أول لافتا في هذه العقدة، وهذا يعني يجب أن يشير هذا الآن في هذه العقدة. وبعبارة أخرى، وإن كان ما يبدو فوضى المضحكه مع الكتابة اليدوية الخاص بي، ما فكرة بسيطة من مجرد الانتقال هذه الأسهم في جميع أنحاء يترجم إلى رمز واحد فقط مع بطانة هذا. تخزين ما هو الاول في الحقل التالي ثم قم بتحديث ما هو فعلا اول. دعونا نمضي قدما إلى الأمام وبسرعة من خلال بعض من هذا، وننظر فقط في هذا الإدراج الذيل في الوقت الراهن. لنفترض أن أحصل على النقطة التي أجد أن الحقل التالي بعض عقدة NULL. وعند هذه النقطة في القصة، وهي التفاصيل التي أنا التغاضي عن هو أنني كنت قد قدمت آخر مؤشر حتى هنا في السطر 142، مؤشر السلف. أساسا، في هذه المرحلة من القصة، وبمجرد أن يحصل على قائمة طويلة، النوع الأول من المشي تحتاج إلى ذلك مع اثنين من الأصابع لأنه إذا ذهبت بعيدا جدا، تذكر في قائمة واحدة ذات طول، لا يمكنك العودة إلى الوراء. لذلك هذا هو فكرة predptr إصبعي اليسار، وnewptr - لا newptr. آخر مؤشر هذا هنا هو إصبعي أخرى، وأنا مجرد نوع من المشي القائمة. هذا هو السبب في ما هو موجود. ولكن دعونا ننظر فقط واحدة من أبسط الحالات هنا. إذا الحقل الذي هو مؤشر NULL المقبل، ما هي الآثار المترتبة منطقية؟ إذا كنت تعبر هذه القائمة وضرب لكم مؤشر NULL؟ كنت في نهاية القائمة، وذلك رمز لإلحاق ثم وهذا عنصر واحد إضافية وسوف النوع من بديهية أن تلك العقدة التي المقبل المؤشر NULL، لذلك هذا هو NULL حاليا، وتغييره، على الرغم من أن عنوان عقدة جديدة. لذلك نحن فقط رسم في قانون السهم الذي وضعنا على خشبة المسرح من خلال رفع اليد اليسرى لشخص ما. 

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

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

في الواقع، لنفترض أننا لم نضع قائمة مرتبطة جانبا للحظة وبدلا من ذلك قدمنا ​​فكرة الجدول. ودعونا مجرد التفكير في جدول للحظة كصفيف. هذه المجموعة لديها وحالة هذه العناصر هنا نحو 26، 0 إلى 25، وافترض أنك في حاجة الى بعض قطعة من التخزين لأسماء: أليس وبوب وتشارلي وما شابه ذلك. وكنت بحاجة الى بعض هياكل البيانات لتخزين هذه الأسماء. حسنا، هل يمكن استخدام شيء من هذا القبيل قائمة مرتبطة ويمكن أن تمشي القائمة إدراج أليس بوب قبل وبعد تشارلي بوب وهكذا دواليك. و، في الواقع، إذا كنت تريد أن ترى رمز من هذا القبيل بوصفها جانبا، نعرف أن في list2.h، ونحن نفعل ذلك بالضبط. ونحن لن نذهب من خلال هذا الرمز، ولكن هذا هو البديل من المثال الأول الذي يقدم البنية 1 الاخرى التي سمعنا قبل الطالب يسمى، ثم يخزن في الواقع ما في القائمة هو مؤشر مرتبط إلى بنية الطالب بدلا من عدد صحيح بسيطة قليلا، ن. حتى ندرك أن هناك رمز ينطوي هناك سلاسل الفعلية، ولكن إذا كان الهدف في متناول اليد الآن حقا هو لمعالجة مشكلة الكفاءة، لن يكون ذلك جميلا لو كنت أعطيت لنا كائن يسمى أليس، ونحن نريد ان نضع لها في الموقع المناسب في بنية البيانات، بدا الامر وكأننا أنه سيكون لطيف وضعت للتو أليس، يبدأ اسمه ب A، في الموقع الأول. وبوب، واسمه يبدأ B، في الموقع الثاني. مع مجموعة، أو لنبدأ اصفا اياه جدول، جدول تجزئة في ذلك، يمكننا أن نفعل ذلك بالضبط. إذا أعطينا اسما مثل أليس، أليس مثل سلسلة، أين كنت وضعت A-L-I-C-E؟ نحن بحاجة إلى hueristic. نحن بحاجة إلى وظيفة اتخاذ بعض المدخلات مثل أليس والعودة جوابا، "ضع أليس في هذا الموقع." وهذه الوظيفة، هذا الصندوق الأسود، هو الذهاب ليتم استدعاؤها دالة تجزئة. 

ودالة البعثرة هو الشيء الذي يأخذ المدخلات، مثل "أليس"، ويعود لكم، عادة، الموقع رقمية في بعض هياكل البيانات حيث ينتمي أليس. في هذه الحالة، يجب أن يكون لدينا وظيفة التجزئة بسيطة نسبيا. ينبغي أن تعمل لدينا التجزئة أقول، إذا ما أتيحت لك "أليس"، والتي ينبغي أن الطابع يهمني؟ أول واحد. لذلك أنظر إلى [0]، وبعد ذلك أقول إذا حرف [0] هو A، إرجاع عدد 0. اذا كان B، والعودة 1. إذا C انها، والعودة 2، وهكذا دواليك. فإن جميع الفهرس 0، والتي تسمح لي لإدراج أليس وبوب ثم ثم تشارلي وهكذا دواليك في هذا الهيكل البيانات. ولكن هناك مشكلة. ماذا لو أنيتا تأتي مرة أخرى؟ أين نضع أنيتا؟ اسمها أيضا، ويبدأ بحرف A، وبدا الامر وكأننا حققنا فوضى أكبر من هذه المشكلة. لدينا الآن الإدراج الفوري، ثابت الإدراج الوقت، إلى بنية بيانات بدلا من حالة أسوأ الخطية، ولكن ماذا يمكننا أن نفعل مع أنيتا في هذه الحالة؟ ما هي الخيارين، حقا؟ نعم؟ [الجواب طالبة، غير مفهومة] حسنا، حتى أننا يمكن أن يكون بعدا آخر. هذا امر جيد. حتى نتمكن من بناء الأشياء في 3D مثل تحدثنا عن شفهيا يوم الاثنين. يمكن أن نضيف آخر وصول هنا، ولكن لنفترض أنه لا يوجد، وأنا أحاول أن إبقاء هذه البسيطة. الهدف كله هنا هو أن يكون على الفور الوصول في الوقت مستمر، بحيث انه اضاف الكثير من التعقيد. ما هي الخيارات الأخرى عند محاولة إدراج أنيتا في هذا الهيكل البيانات؟ نعم؟ [الجواب طالبة، غير مفهومة] جيد. حتى نتمكن من نقل الجميع إلى أسفل، مثل الوكز تشارلي أسفل بوب وأليس، ثم وضعنا أنيتا حيث تريد حقا أن تكون. 

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

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

ربما سوف نحصل على مجرد الحظ ونحن لن يكون اثنين أو اثنين في A B لل مع احتمال كبير جدا، ولكن كما أشار شخص ما، إذا كان لنا أن هذه المشكلة عامة وليس القيام 0 حتي 25 ولكن، كما يقول، من 0 إلى 364 أو 65، في كثير من الأحيان عدد الأيام في السنة النموذجية، وطرح السؤال، "ما هو احتمال أن يكون اثنان منا في هذه القاعة يكون في نفس تاريخ الميلاد؟" بعبارة أخرى، ما هو احتمال أن يكون اثنان منا لديه اسم بدءا A؟ هذا النوع من الأسئلة هو نفسه، ولكن هذه المساحة عنوان، هذه المساحة البحث، هو أكبر في حالة أعياد الميلاد، لأن لدينا الكثير من أكثر أيام السنة من الأحرف في الأبجدية. ما هو احتمال حدوث تصادم؟ حسنا، يمكن أن نفكر في ذلك من خلال معرفة الرياضيات في الطريق المعاكس. ما هو احتمال اصطدام لا؟ حسنا، هذا التعبير هنا يقول ان ما هو احتمال إذا كان هناك شخص واحد فقط في هذه الغرفة، أن لديهم عيد ميلاد فريدة من نوعها؟ انها 100٪. لأنه إذا كان هناك شخص واحد فقط في الغرفة، يمكن له أو عيد ميلادها أن يكون أي من 365 يوما من السنة. من الخيارات 365/365 يعطيني قيمة 1. وبالتالي فإن احتمال في المسألة في هذه اللحظة هو فقط 1. ولكن إذا كان هناك شخص ثان في الغرفة، ما هو احتمال أن عيد ميلادهم مختلفة؟ لا يوجد سوى 364 يوما ممكنا، سنة كبيسة تجاهل، في عيد على عدم الاصطدام مع الأشخاص الآخرين. حتى 364/365. إذا كان شخص ثالث يأتي في، انها 363/365، وهكذا دواليك. حتى نحافظ معا بضرب هذه الكسور، والتي يتم الحصول أصغر وأصغر، لمعرفة ما هو احتمال أن يكون كل واحد منا أعياد ميلاد فريدة من نوعها؟ ولكن بعد ذلك يمكننا، بالطبع، أن تأخذ فقط الإجابة والوجه حولها والقيام 1 ناقص كل ذلك، تعبيرا عن أننا سنصل في نهاية المطاف إذا كنت تتذكر الجزء الخلفي من كتب الرياضيات الخاصة بك، يبدو شيئا قليلا من هذا القبيل، وأكثر من ذلك بكثير بسهولة تفسير الذي بيانيا. وهذا الرسم هنا له على المحور X عدد أعياد الميلاد، أو عدد من الناس مع أعياد الميلاد، وعلى محور Y هو احتمال مباراة. وهذا ما يقوله هو أنه إذا كان لديك، دعنا نقول، حتى، دعونا اختيار شيء من هذا القبيل 23، 22. إذا كان هناك 22 أو 23 شخصا في الغرفة، احتمال أن يكون اثنان من هؤلاء الناس عدد قليل جدا ستكون لدينا عيد ميلاد نفس هو في الواقع عالية فائقة، combinatorially. خلاف ذلك 50٪ في فئة من 22 شخصا فقط، حلقة دراسية، من الناحية العملية، 2 من هؤلاء الناس ستكون لدينا عيد ميلاد نفسه. لأن هناك الكثير من الطرق التي يمكن أن يكون في نفس تاريخ الميلاد. أسوأ من ذلك، إذا نظرتم الى الجانب الأيمن من الرسم البياني، بحلول الوقت الذي يكون مع فئة 58 طالبا في ذلك، احتمال من 2 شخص لديه عيد ميلاد السوبر، وارتفاع عظمى، ما يقرب من 100٪. الآن، وهذا نوع من معلومة طريفة عن الحياة الحقيقية. 

ولكن الآثار المترتبة، الآن، لهياكل البيانات وتخزين المعلومات يعني أن افتراض فقط لديك، لطيفة نظيفة، وتوزيع موحد للبيانات وكان لديك مجموعة كبيرة بما يكفي لتناسب مجموعة من الأشياء لا يعني وأنت تسير في الحصول على الناس في أماكن فريدة من نوعها. كنت ستكون لدينا الاصطدامات. لذلك هذا مفهوم التجزئة، كما يطلق عليه، أخذ مدخلا مثل "أليس" وتدليك لها في بعض الطريق ومن ثم الحصول على إجابة مثل العودة 0 أو 1 أو 2. العودة بعض الانتاج من تلك الوظيفة والتي تعاني من هذا احتمال الاصطدام. فكيف يمكننا التعامل مع تلك الاصطدامات؟ حسنا، على حالة واحدة، يمكن أن نأخذ فكرة أن اقترح. يمكننا تحويل كل شخص إلى أسفل، أو ربما، ببساطة أكثر من ذلك بقليل، بدلا من الجميع التحرك آخر، دعنا ننتقل فقط أنيتا إلى أسفل البقعة المتاحة. إذا كان الأمر كذلك أليس هو في 0، بوب في 1، تشارلي في 2، سنقوم فقط وضعت أنيتا في الموقع 3. وهذا هو أسلوب في هياكل البيانات الخطية يسمى التحقيق. الخطية لأنك مجرد المشي هذا الخط، وكنت نوع من التحقيق لبقع متوفرة في بنية البيانات. بطبيعة الحال، هذه تؤول إلى O (N). إذا كانت بنية بيانات مليئة حقا، وهناك 25 شخصا في ذلك بالفعل، ثم يأتي على طول أنيتا، وقالت انها ينتهي في ما يمكن أن يكون Z الموقع، وهذا شيء طيب. وقالت انها لا تزال يناسب، ويمكن أن نجد لها في وقت لاحق. 

ولكن هذا يتعارض مع الهدف من تسريع الامور. ولكن ماذا لو قدمنا ​​هذا البعد الثالث بدلا؟ ويسمى هذا الأسلوب عموما تسلسل منفصلة، ​​أو وجود سلاسل. وما جدول التجزئة الآن، هذا الهيكل جدولي، الجدول الخاص بك هو مجرد مجموعة من المؤشرات. ولكن ما هي هذه المؤشرات تشير إلى تخمين ما هو؟ قائمة مرتبطة. ولكن ماذا لو أخذنا أفضل من كل من هذه العوالم؟ نستخدم المصفوفات الأولية للفهارس في هيكل البيانات بحيث يمكننا أن نذهب على الفور إلى [0] [1]، [30] أو غير ذلك، ولكن حتى يكون لدينا قدر من المرونة، ونحن يمكن أن تناسب أنيتا واليس وآدم وغيرها من أي اسم، تركنا بدلا محور أخرى تنمو بشكل تعسفي. ونحن في نهاية المطاف، وذلك اعتبارا من الاثنين، لديك هذه القدرة التعبيرية مع القائمة المرتبطة. يمكننا تنمو بنية بيانات تعسفية. بدلا من ذلك، يمكن أن تجعل مجرد ضخمة 2-الأبعاد صفيف، ولكن هذا سيكون وضعا مروعا إذا كان أحد الصفوف في مجموعة و2-الأبعاد ليست كبيرة بما يكفي لشخص إضافي اسمه يحدث لتبدأ A. لا سمح الله علينا أن يعيد توزيع ضخمة الأبعاد 2-هيكل لمجرد أن هناك الكثير من الناس اسمه A، خاصة عند وجود عدد قليل جدا من الناس من اسمه Z شيء. انه سيكون مجرد أن يكون بنية بيانات ضئيلة جدا. حتى انها ليست مثالية بأي وسيلة، ولكن الآن نحن على الأقل لديها القدرة للعثور على الفور حيث ينتمي أليس أو أنيتا، على الأقل من حيث المحور الرأسي، ومن ثم علينا فقط أن تقرر أين يضع أنيتا أو أليس في هذه القائمة المرتبطة. إذا كنا لا نهتم فرز الأشياء، وكيف يمكن لنا بسرعة إدراج أليس في هيكل مثل هذا؟ حان الوقت ثابت. نحن في مؤشر [0]، وإذا كان هناك أي واحد، أليس يذهب في بداية تلك القائمة المرتبطة. ولكن هذا ليس مشكلة كبيرة. لأنه إذا أنيتا ثم يأتي على طول بعض عددا من الخطوات في وقت لاحق، حيث لا تنتمي أنيتا؟ حسنا، [0]. OOP. أليس هو بالفعل في تلك القائمة المرتبطة. 

ولكن إذا كنا لا نهتم فرز هذه الأسماء، يمكننا المضي فقط أليس أكثر، إدراج أنيتا، ولكن هذا هو الوقت حتى ثابتة. حتى لو هناك أليس وآدم وجميع هذه أسماء أخرى A، انها ليست حقا لهم تحويل جسديا. لماذا؟ لأننا فقط لم هنا مع قائمة مرتبطة، والذي يعرف هذه العقد هي على أية حال؟ كل ما عليك القيام به هو نقل فتات الخبز. نقل الأسهم حولها؛ لم يكن لديك على التحرك جسديا أية بيانات حولها. حتى نتمكن من إدراج أنيتا، في هذه الحالة، وعلى الفور. ثابت الزمن. لذلك لدينا الوقت ثابت البحث، ومستمرة في الوقت الإدراج شخص مثل أنيتا. ولكن نوع من تبسيط العالم. ماذا لو كنا نريد في وقت لاحق للعثور أليس؟ ماذا لو كنا نريد في وقت لاحق للعثور أليس؟ كم عدد الخطوات التي سوف يتم اتخاذها؟ [الجواب طالبة، غير مفهومة] بالضبط. عدد الأشخاص قبل أليس في القائمة المرتبطة. حتى انها ليست مثالية تماما، وذلك لأن بنيتنا البيانات، مرة أخرى، لديها هذا الوصول العمودي ومن ثم فقد هذه القوائم المرتبطة شنقا - في الواقع، دعونا لا استدراجه إلى صفيف. فقد ربط هذه القوائم تتدلى من أن يبدو شيئا قليلا من هذا القبيل. ولكن المشكلة هي إذا أليس وآدم وجميع هذه أسماء أخرى A في نهاية المطاف أكثر وأكثر هناك، العثور على شخص يمكن أن ينتهي مع حفنة من الخطوات، bcause لديك لاجتياز القائمة المرتبطة، التي هي عملية خطية. ذلك حقا، بعد ذلك، في الوقت الإدراج في نهاية المطاف O (N)، حيث n هو عدد العناصر في القائمة. مقسوما، دعونا ندعو بشكل تعسفي من متر، حيث m هو عدد القوائم المرتبطة التي لدينا في هذا المحور العمودي. وبعبارة أخرى، إذا افترضنا حقا توزيع موحد للأسماء، غير واقعي تماما. هناك أكثر من واضح بعض الحروف من غيرها. 

ولكن إذا افترضنا لحظة توزيع موحد، ولقد ن الناس الكلي، وسلاسل مجموع م المتوفرة لدينا، فإن طول كل من هذه السلاسل إلى حد ما ببساطة سيكون المجموع، ن مقسوما على عدد من سلاسل. حتى ب / م. ولكن هنا هو المكان الذي يمكن أن يكون كل ذكي رياضيا. م هو ثابت، لأنه لا يوجد عدد محدد من هذه. وأنت تسير أن تعلن مجموعة الخاصة بك في البداية، ونحن لسنا تغيير حجم المحور الرأسي. بحكم تعريفها، أن يبقى ثابتة. انها فقط على المحور الأفقي، إذا جاز التعبير، وهذا التغير. من الناحية الفنية كذلك، وهذا هو ثابت. حتى الآن، والوقت الإدراج هو الى حد كبير O (N). بحيث لا يشعر كل ذلك أفضل بكثير. ولكن ما هي الحقيقة هنا؟ حسنا، كل هذا الوقت، لأسابيع، لقد كنا نقول O (ن ²). O (ن)، 2 × ن ²، - ن، مقسوما على 2. . . ECH. انها مجرد ² ن. ولكن الآن، في هذا الجزء من الفصل الدراسي، يمكننا أن نبدأ الحديث عن العالم الحقيقي مرة أخرى. وب / م أسرع من N تماما وحده فقط. إذا كان لديك أسماء ألف، وكنت كسر لهم حتى في الدلاء متعددة بحيث يكون لديك سوى عشرة أسماء في كل من هذه السلاسل، البحث الاطلاق عشرة أشياء ستكون أسرع من الأشياء ألف. وهكذا واحدة من مجموعات المشكلة القادمة سوف تحد لكم لنفكر في ذلك تماما على الرغم من، نعم، ومقارب رياضيا، وهذا لا يزال الخطية فقط، التي تمتص بشكل عام عند محاولة العثور على الأشياء. في الواقع، فإنه سيكون أسرع من ذلك وبسبب هذا المقسوم عليه. ولذا فإن هناك من جديد لتكون هذه المفاضلة وهذا الصراع بين النظرية والواقع، وسوف واحدة من بدء تحول المقابض في هذه المرحلة في الفصل الدراسي هو أكثر من حقيقة واحدة ونحن نوع من الاستعداد لنهاية semster ل، كما نقدم للعالم برمجة الويب، حيث حقا، والأداء هو الذهاب الى الاعتماد الخاص لأن المستخدمين سوف تبدأ في الشعور ونقدر القرارات سوء التصميم. 

فكيف يمكنك أن تذهب نحو تنفيذ مرتبط - مع 31 عناصر جدول التجزئة؟ وكان المثال السابق بشكل تعسفي عن أعياد الميلاد. إذا كان شخص ما لديه عيد ميلاد من 1 يناير أو فبراير 1، سوف نضع لهم في هذا دلو. اذا كان 2 يناير، 2 فبراير، 2 مارس، سوف نضع لهم في هذا دلو. هذا هو السبب في أنه كان 31. كيف قمت بتعريف جدول التجزئة؟ أنها يمكن أن تكون بسيطة جدا، عقدة الجدول * اسمي التعسفي لذلك، [31]. هذا يعطيني 31 مؤشرات إلى العقد، والتي تسمح لي لديه 31 مؤشرات إلى القوائم المرتبطة حتى لو كانت تلك هي سلاسل NULL في البداية. ماذا أريد أن أضع إذا كنت تريد تخزين "أليس"، "بوب"، "تشارلي"؟ حسنا، نحن بحاجة إلى التفاف تلك الأشياء في بنية أليس لأننا في حاجة للإشارة إلى بوب، للإشارة إلى تشارلي، وهكذا دواليك. ونحن لا يمكن أن يكون مجرد أسماء وحدها، لذلك يمكنني أن إنشاء بنية جديدة تسمى العقدة هنا. 

ما هو العقدة الفعلية؟ ما هي عقدة في هذه القائمة الجديدة المرتبطة؟ أول شيء، ودعا الكلمة، هو لاسم الشخص. LENGTH، ويفترض، يتصل الحد الأقصى لطول اسم الانسان، أيا كان ذلك، 20، 30، 40 حرفا في حالات الزاوية مجنون، و +1 هو لماذا؟ انها مجرد حرف NULL إضافية، \ 0. لذلك هذا هو التفاف عقدة "شيء ما" داخل نفسه، ولكنه يعلن أيضا مؤشر يسمى المقبل بحيث نستطيع سلسلة أليس لبوب لتشارلي وهكذا دواليك. يمكن أن يكون NULL ولكن ليس بالضرورة أن يكون. أي أسئلة حول هذه الجداول التجزئة؟ نعم؟ [طالب يسأل السؤال، غير مفهومة] صفيف - سؤال جيد. لماذا هذه الكلمة حرف في صفيف بدلا من مجرد شار *؟ في هذا المثال التعسفي إلى حد ما، لم أكن أريد أن تضطر إلى اللجوء لmalloc لكل من أسماء الأصلي. أردت أن يعلن الحد الأقصى لمقدار الذاكرة لسلسلة بحيث أتمكن من نسخ في هيكل أليس \ 0 وليس لديك للتعامل مع malloc وحرة وما شابه ذلك. ولكن يمكن أن أفعل ذلك إذا أردت أن أكون أكثر وعيا من استخدام الفضاء. سؤال جيد. لذلك دعونا في محاولة لتعميم بعيدا عن هذا وتركز ما تبقى من اليوم على هياكل البيانات بشكل عام وغيرها من المشاكل التي نحن يمكن أن تحل باستخدام نفس الأسس على الرغم من أن هياكل البيانات قد تختلف في التفاصيل نفسها بهم. 

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

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

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

ولذلك لا يوجد هيكل آخر البيانات أن نتمكن من إدخال. تم تصميم هذا واحد لأول وهلة أن ننظر خفي، ولكن هذا واحد لأمر مدهش. لذلك هذا هو بنية بيانات تسمى يحاكم، يحاكم، والذي يورث من استرجاع كلمة، الذي لا ينطق إعادة محاكمة فال، ولكن هذا ما يدعو العالم هذه الأشياء. يحاول. T-R-I-E. وهو هيكل شجرة من نوع ما، ولكن كل واحد من العقد في يحاكم يبدو أن ما؟ وهذا هو قليلا مضللة لانها نوع من اختصار. لكن يبدو كل عقدة في هذا يحاكم هو في الواقع مجموعة. وعلى الرغم من أن مؤلف هذا المخطط لم يظهر ذلك، في هذه الحالة، وهذا هو يحاكم بنية بيانات هدفها في الحياة هو لتخزين الكلمات مثل A-L-I-C-E أو B-O-B. والطريقة التي يخزن هذا البيانات أليس وبوب وتشارلي وأنيتا وهكذا دواليك وأنه يستخدم مجموعة حيث لتخزين أليس في يحاكم، نبدأ في عقدة الجذر الذي يشبه صفيف، وما كان مكتوب في تدوين الاختزال. المؤلف حذف ABCDEFG بسبب عدم وجود أسماء في ذلك. إلا أنها أظهرت وM P وT، ولكن في هذه الحالة، دعونا نبتعد عن أليس وبوب وتشارلي لبعض الأسماء التي هي هنا. ماكسويل هو في الواقع في هذا المخطط. فكيف فعل المخزن المؤلف M-A-X-W-E-L-L؟ بدأ هو أو هي في عقدة الجذر، وذهب إلى [M]، لذلك ما يقرب من 13، موقع 13th في الصفيف. ثم من هناك، وهناك مؤشر. مؤشر آخر مما يؤدي إلى الصفيف. من هناك فهرسة المؤلف إلى أن مجموعة في الموقع A، كما هو مبين هناك في أعلى اليسار، وتابع ثم انه أو انها مؤشر إلى أن مجموعة أخرى، وذهب إلى مكان المؤشر في X. ثم في مجموعة الموقع التالي W، E، L، L، وهكذا دواليك، وأخيرا، دعونا نحاول فعلا لوضع صورة لهذا. ماذا نظرة مثل عقدة في التعليمات البرمجية؟ A عقدة في يحاكم يحتوي على مجموعة من المؤشرات إلى أكثر من العقد. ولكن هناك يجب أيضا أن يكون نوعا من قيمة منطقية، على الأقل في هذا التنفيذ. يحدث لي أن نسميها is_word. لماذا؟ لأنه عندما كنت إدراج ماكسويل، أنت لا إدراج أي شيء في هذا الهيكل البيانات. كنت لا أكتب M. أنت لا أكتب X. كل ما تفعلونه هو بعد المؤشرات. المؤشر الذي يمثل M، ثم المؤشر الذي يمثل A، ثم المؤشر الذي يمثل X، W ثم، E، L، L، وصلت ولكن ما عليك القيام به في نهاية هو نوع من الذهاب، والتحقق، وهذا الموقع. كان هناك الكلمة التي ينتهي هنا في بنية البيانات. 

فما يتم تعبئة حقا يحاكم مع والمؤلف اختار لتمثيل هذه terminuses مع مثلثات صغيرة. هذا يعني فقط ان حقيقة هذا المثلث هنا، وهذا صحيح من قيمة منطقية يعني إذا ذهبت إلى الوراء في الشجرة، وهذا يعني اسمه كلمة ماكسويل في ذلك. لكن كلمة فو، على سبيل المثال، ليس في شجرة، لأنه إذا أبدأ في عقدة الجذر هنا حتى في أعلى، ليس هناك مؤشر واو، لا مؤشر س، أي مؤشر س. فو ليست اسما في هذا القاموس. ولكن على النقيض من ذلك، تورينج، T-U-R-I-N-G. مرة أخرى، لم أكن تخزين أو تي يو أو ص أو i أو n أو ز. لكنني في هذا المتجر بنية بيانات قيمة من الطريق الصحيح إلى هنا في هذه العقدة - في شجرة من خلال تحديد هذه القيمة منطقية من is_word إلى true. لذلك يحاكم هو نوع من هذا الهيكل الفوقية مثيرة جدا للاهتمام، حيث كنت لا حقا تخزين الكلمات نفسها لهذا النوع من القاموس. أن تكون واضحة، وكنت تخزين فقط بنعم او لا، هناك الكلمة التي ينتهي هنا. 

الآن ما هو ضمنا؟ إذا كان لديك 150،000 الكلمات في القاموس الذي تحاول لتخزين في الذاكرة باستخدام ما يشبه قائمة مرتبطة، كنت ستكون لدينا 150،000 العقد في قائمة مرتبطة. ويمكن العثور على واحدة من تلك الكلمات أبجديا اتخاذ O (ن) مرة. الخطي الوقت. ولكن في حالة وجود يحاكم هنا، ما هي إدارة الوقت في العثور على كلمة واحدة؟ تبين جمال هنا هو أنه حتى لو كان لديك 149999 الكلمات بالفعل في هذا القاموس، نفذت كما هو الحال مع هذا بنية البيانات، كم من الوقت يستغرق لإيجاد أو إدراج شخص آخر في هذا، أليس مثل، أليس؟ حسنا، انها فقط 5، 6 خطوات ربما للحرف زائدة. لأن presense من الأسماء الأخرى في هيكل لا تحصل في الطريق من إدراج أليس. وعلاوة على ذلك، مرة واحدة يجد أليس هناك 150،000 الكلمات في هذا القاموس لا يحصل في طريقك للعثور أليس في كل شيء، لأن أليس هو. . . . . هنا، وذلك لأن وجدت قيمة منطقية. وإذا لم يكن هناك منطقية صحيحة، أليس في ذلك الوقت ليس في هذا الهيكل بيانات من الكلمات. وبعبارة أخرى، فإن إدارة الوقت في العثور على الأشياء وإدخال أشياء جديدة في هذه هيكل البيانات يحاكم هو يا - ليست ن ذلك. لأن presense من 150،000 شخص ليس له تأثير على أليس، على ما يبدو. لذلك دعونا نسميها ك، حيث ك هو الحد الأقصى لطول كلمة في اللغة الإنجليزية وهو عادة لا يزيد عن 20 حرفا شيء. حتى k ثابت. وبالتالي فإن الكأس المقدسة يبدو أننا قد وجدت الآن هو أن وقت واحد، يحاكم المستمر للإدراج، لعمليات البحث، لالحذف. لأن عدد من الأشياء بالفعل في الهيكل، التي ليست حتى هناك جسديا. مرة أخرى، انهم مجرد نوع من التحقق من، نعم أو لا، ليس له أي تأثير على مستقبله الوقت الحالي. 

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

صدقوا أو لا تصدقوا، ومتعة بقدر ما كان C لبعض الوقت الآن، نحن بلوغ نقطة في الفصل الدراسي حيث ان الوقت قد حان للانتقال إلى أشياء أكثر حداثة. الأشياء على مستوى أعلى. وعلى الرغم من لالاسبوعين المقبلين سنقوم لا تزال مستمرة لتزج أنفسنا في عالم المؤشرات وإدارة الذاكرة للحصول على الراحة مع أن الذي يمكن أن نبني ذلك الحين، نهاية اللعبة هو في نهاية المطاف أن أعرض، ومن المفارقات، وليس هذه اللغة. سوف نقضي، مثل 10 دقيقة يتحدث عن HTML. جميع HTML هي لغة توصيف النص، وما هي لغة توصيف النص هذه هي سلسلة من الأقواس المفتوحة والمغلقة بين قوسين التي تقول "جعل هذا جريئة" "جعل هذا مائل 'تركز على جعل هذا". انها ليست مثيرة للاهتمام بكل ما فكريا، ولكنها لسوبر مفيدة. وانها بالتأكيد منتشرة في كل مكان هذه الأيام. ولكن ما هو قوي حول العالم من HTML، وبرمجة الويب بشكل عام، وبناء الأشياء الحيوية؛ كتابة التعليمات البرمجية في لغات مثل PHP أو Python أو روبي أو جافا أو C #. حقا، مهما اللغة التي تختارها هي، وتوليد HTML بشكل حيوي. توليد ما يسمى CSS بشكل حيوي. أوراق الأنماط المتتالية، والذي هو أيضا عن الجماليات. وعلى الرغم من ذلك، اليوم، إذا ذهبت إلى بعض المواقع مثل Google.com مألوفة، وأذهب لمشاهدة، المطور، عرض المصدر، الذي ربما كنت قد فعلت من قبل، لكن الذهاب الى عرض المصدر، هذه الأشياء ربما تبدو خفي جدا. ولكن هذا هو رمز الأساسية التي تطبق Google.com. على الواجهة الأمامية. والواقع كل هذه الاشياء هو علم الجمال رقيق. هذا هو CSS هنا. إذا أظل التمرير لأسفل سوف نحصل على بعض الاشياء مرمزة. هذا هو HTML. كود جوجل يشبه الفوضى، ولكن إذا كنت فعلا فتح نافذة مختلفة، يمكننا أن نرى بعض هيكل على ذلك. إذا قمت بفتح هذا الأمر، لاحظ هنا، انها قليلا أكثر قابلية للقراءة. ونحن في طريقنا لرؤية هذه العلامة قبل فترة طويلة، [كلمة] هو العلامة، HTML، الرأس، الجسم، DIV، النصي، منطقة نص، تمتد، محورها، DIV. وهذا هو نوع من المظهر أيضا خفي للوهلة الأولى، ولكن كل هذه الفوضى يلي أنماط معينة، وأنماط تكرار، بحيث بمجرد ان نحصل على أساسيات أسفل، عليك أن تكون قادرا على كتابة التعليمات البرمجية مثل هذا والتلاعب ثم رمز مثل هذا باستخدام لغة أخرى حتى الآن، ودعا سكريبت. وجافا سكريبت هي لغة التي يتم تشغيلها داخل متصفح التي نستخدمها اليوم على دورات في جامعة هارفارد، أداة للدورة التسوق التي يستخدم خرائط جوجل لإعطائك مجموعة كاملة من الدينامية، الفيسبوك يتيح لك لإظهار تحديثات فورية، تويتر يستخدم لتظهر لك على الفور تويت. كل هذا سوف نبدأ في تزج أنفسنا فيه. ولكن للوصول إلى هناك، ونحن بحاجة إلى فهم شيئا قليلا عن الانترنت. هذا الكليب هنا هو فقط لمدة دقيقة طويلة، ودعونا نفترض الآن هذا هو، في الواقع، كيف تعمل الإنترنت ودعابة لما هو على وشك أن تأتي. أنا أعطيك "محاربو شبكة الإنترنت." 

[♫ ♫ موسيقى جوقة البطيء] [الراوي ذكر] وقال انه جاء مع الرسالة. مع كل ما قدمه من البروتوكول الخاصة. [♫ ♫ الموسيقى الإلكترونية أسرع] وقال انه جاء إلى عالم من الجدران النارية باردة، غير مكترثة أجهزة التوجيه، والمخاطر أسوأ بكثير من الموت. وأضاف بسرعة. انه قوي. انه TCP / IP، وانه حصل على عنوانك. المحاربين من صافي. [مالان] الأسبوع القادم، ثم. شبكة الإنترنت. برمجة الويب. هذا هو CS50. [CS50.TV]