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

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

الطالب: [غير مسموع]. 

سرور 1: ما هذا؟ 

الطالب: [غير مسموع]. 

سرور 1: حجم ثابت. حسنا، لماذا هو حجم ثابت جيد على الرغم من؟ 

الطالب: [غير مسموع]. 

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

ما هو الجانب حتى آخر لصفيف؟ نعم؟ 

الطالب: [غير مسموع]. 

سرور 1: جميع - آسف؟ 

الطالب: [غير مسموع]. 

سرور 1: جميع صناديق في الذاكرة أو بجانب بعضها البعض. وهذا مفيد - لماذا؟ هذا صحيح تماما. ولكن كيف يمكننا استغلال تلك الحقيقة؟ 

الطالب: [غير مسموع]. 

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

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

ولكن هناك بعض الجوانب السلبية ما كان. ما مجموعة لا تفعل بسهولة جدا؟ ما يدور يست جيدة في؟ 

الطالب: [غير مسموع]. 

سرور 1: ما هذا؟ 

الطالب: [غير مسموع]. 

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

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

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

الطالب: [غير مسموع]. 

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

وذلك ما تستخدم المؤشر رغم ما يبدو ل؟ لماذا هذا السهم إضافة الآن عندما كانت صفائف لطيفة جدا ونظيفة وبسيطة؟ ما هو مؤشر تفعل ل لنا في كل من هذه العقد؟ 

الطالب: [غير مسموع]. 

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

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

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

الطالب: [غير مسموع]. 

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

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

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

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

الطالب: [غير مسموع]. 

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

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

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

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

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

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

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

الطالب: [غير مسموع]. 

سرور 1: نعم لذلك هو ملف محلي. حتى لو كان ملف محلي خاص بك هنا على الخط 15، على سبيل المثال، يمكنك استخدام علامة التنصيص بدلا الأقواس الزاوية. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

الطالب: [غير مسموع]. 

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

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

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

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

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

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

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

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

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

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

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

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

الطالب: [غير مسموع]. 

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

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

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

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

الطالب: بن. 

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

الطالب: جايسون. 

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

الطالب: جيل. 

سرور 1: جيل، وأنت تسير لتكون 17، والتي إذا كنت فعلت ذلك أكثر بذكاء، وأود أن بدأت في الطرف الآخر. تذهب بهذه الطريقة. 22. وأنت؟ 

الطالب: مريم. 

سرور 1: ماري، عليك أن تكون 22. واسمك؟ 

الطالب: كريس. 

سرور 1: كريس، عليك أن تكون 26. ثم أخيرا. 

الطالب: ديانا. 

سرور 1: ديانا، عليك أن تكون 34. حتى أتيت على أكثر من هنا. 

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

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

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

الطالب: بريان. 

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

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

الطالب: جايسون. 

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

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

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

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

الذي يحصل أشار في من؟ 

الطالب: [غير مسموع]. 

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

الطالب: [غير مسموع]. 

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

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

الطالب: [غير مسموع]. 

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

الطالب: ديانا. 

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

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

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

الطالب: [غير مسموع]. 

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

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

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

الطالب: [غير مسموع]. 

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

دعونا نفعل المثال النهائي هنا وضعت هؤلاء الرجال من بؤسهم. حتى malloc 20. تأتي على ما يصل من الممر هناك. كل الحق، ما هو اسمك؟ 

الطالب: [غير مسموع]. 

سرور 1: عذرا؟ 

الطالب: [غير مسموع]. 

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

لذلك يمكننا أن نفعل 17 التأشير على 20. بحيث بخير. أين نريد أن نشير المؤشر الآن؟ في 22. ونحن نعرف أين هو 22، ومرة ​​أخرى وذلك بفضل لمؤشر بلدي مؤقت. لذلك نحن موافق هناك. لذلك وبسبب هذا التخزين المؤقت لقد أبقى المسار من حيث الجميع. والآن يمكنك الذهاب إلى حيث بصريا كنت تنتمي، والآن نحن بحاجة 1، 2، 3، 4، 5، 6، 7، 8، 9 كرات الإجهاد، وجولة من التصفيق ل هؤلاء الرجال، إذا استطعنا. عمله بشكل جيد. 

[تصفيق] 

سرور 1: حسنا. وكنت قد الحفاظ على القطع من الورق وتذكارات. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

الطالب: [غير مسموع]. 

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

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

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

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

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

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

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

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

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

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

والوجبات الجاهزة من هذا المنحنى هو انه حالما تحصل على مثل 40 الطلاب، وكنت حتى في احتمال 90٪ combinatorically اثنين نسمة أو أكثر وجود في نفس تاريخ الميلاد. وبمجرد الحصول على مثل 58 شخصا انها ما يقرب من 100٪ من فرصة للاثنين الناس في الغرفة ستكون لدينا ل نفس تاريخ الميلاد، على الرغم من هناك 365 أو 366 الدلاء ممكن، و فقط 58 شخصا في الغرفة. فقط إحصائيا أنت من المحتمل أن الحصول على الاصطدامات، التي في القصير يحفز هذا النقاش. أنه حتى لو حصلنا على يتوهم هنا، و بدء وجود هذه السلاسل، ونحن ما زلنا ستكون لدينا الاصطدامات. 

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

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

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

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

الطالب: [غير مسموع]. 

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

الطالب: [غير مسموع]. 

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

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

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

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

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

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

الطالب: [غير مسموع]. 

سرور 1: على اليسار. فما مثيرة للاهتمام مع هذه البيانات هيكل هو بدلا من مخزن سلسلة M-A-X-W-E-L-L مائل الصفر، كل متاخم، ما كنت تفعل بدلا من ذلك فيما يلي. إذا كان هذا هو TRIE مثل هيكل البيانات، كل من العقد الذي هو مرة أخرى صفيف، وتريد تخزين ماكسويل، لأول مرة المؤشر وذلك عقدة الجذر، لذلك في الكلام، وأعلى العقدة، في موقع M، الحق، لذلك تقريبا في الوسط. ثم من هناك، كنت تتبع مؤشر إلى العقد التابعة، إذا جاز التعبير. ذلك بمعنى شجرة العائلة، كنت متابعته النزولي. والتي تقودك إلى عقدة أخرى على اليسار هناك، وهو مجرد مجموعة أخرى. 

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

حسنا، إذا نحن باستخدام هذا النوع من جديدة تأخذ على كيفية تخزين سلسلة في هيكل البيانات، لا تزال تحتاج ل تحقق أساسا قبالة في البيانات هيكل أن كلمة ينتهي هنا. وبعبارة أخرى، كل هذه العقد لديه على نحو ما أن نتذكر أننا يتبع في الواقع كل هذه المؤشرات ويتركون قليلا كسرة خبز في أسفل هنا من هذا هيكل للإشارة إلى M-A-X-W-E-L-L هو بالفعل في هذا الهيكل البيانات. 

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

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

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

الطالب: [غير مسموع]. 

سرور 1: نعم، انها طول من اسم، أليس كذلك؟ حتى M-A-X-W-ه-L-L لذلك يشعر مثل هذا الخوارزمية O كبيرة من سبعة. الآن، بطبيعة الحال، واسم سوف تختلف في الطول. ربما انها اسم قصير. ربما انها اسم لفترة أطول. ولكن ما هو المفتاح هنا هو أن انها رقم ثابت. وربما انها ليست ثابتة حقا، ولكن والله لو واقعيا، في القاموس، هناك على الارجح بعض الحد على عدد من الرسائل في اسم الشخص في بلد معين. 

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

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

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

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

[تشغيل الفيديو] 

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

[END تشغيل الفيديو] 

سرور 1: هذا هو كيف يمكن للإنترنت يجب العمل اعتبارا من الاسبوع المقبل.