[عزف الموسيقى]
>> DAVID مالان: هذا هو CS50.
وهذا هو بداية كل من و end-- مثل نهاية literally-- تقريبا
الأسبوع ستة.
>> اعتقدت مشاركة قليلا من حقيقة متعة.
لقد انسحب هذا الأمر من مجموعة البيانات الفصل الدراسي المنصرم.
ولعلكم تذكرون أن نسأل لكم على كل شكل مجموعة ص إذا كنت قد شاهدت على الانترنت
أو إذا كنت قد حضرت شخصيا.
وهنا هو البيانات.
حتى اليوم كان يمكن التنبؤ به كثيرا جدا.
ولكن أردنا أن تنفق قليلا من الوقت معك ومع ذلك.
أي شخص يود أن نخمن ماذا هذا الرسم البياني هو جاجي ذلك، يصل إلى أسفل، وتصل إلى أسفل،
هكذا على الدوام؟
ماذا تفعل كل القمم وتمثل أحواض؟
>> الجمهور: [غير مسموع]
DAVID مالان: الواقع.
وأكثر من ذلك متعجبا، لا سمح الله، ونحن نحمل محاضرة واحدة يوم الجمعة
في بداية الفصل الدراسي، وهذا ما نراه يحدث.
حتى اليوم، فإننا مشاركة في قليلا المزيد حول هياكل البيانات.
وتعطيك أكثر من المواد الصلبة النموذج العقلي للمشاكل في خمسة،
وهو الآن خارج.
أخطاء إملائية، وسوف نقوم فيه تسليم لك ملف نصي بعض 100000
بالإضافة إلى الكلمات الإنجليزية، و وأنت تسير لدينا
لمعرفة كيفية تحميل بذكاء لهم في الذاكرة، في ذاكرة الوصول العشوائي، وذلك باستخدام بعض البيانات
هيكل من اختيارك.
>> الآن يمكن للمرء مثل هذا الهيكل بيانات يكون، ولكن ربما لا ينبغي أن يكون،
القائمة المرتبطة الساذجة إلى حد ما، التي قدمنا ​​في المرة السابقة.
وكانت قائمة مرتبطة على الأقل ميزة واحدة على صفيف.
ما هي ميزة واحدة من قائمة مرتبطة جدليا؟
>> الجمهور: الإدراج.
>> DAVID مالان: الإدراج.
ماذا يعني ذلك؟
>> الجمهور: في أي مكان على طول قائمة (غير مسموع).
>> DAVID مالان: جيد.
حتى تتمكن من إدراج عنصر في أي مكان تريد في منتصف القائمة
دون الحاجة إلى خلط أي شيء، الذي خلصنا، في الفرز دينا
المناقشات، ليس بالضرورة شيئا جيدا،
لأنه يستغرق وقتا طويلا لتحريك الواقع كل هؤلاء البشر من اليسار أو اليمين.
وحتى مع قائمة مرتبطة، يمكنك فقط مع تخصيص malloc، عقدة جديدة،
ثم تحديث بضع pointers-- اثنين، وثلاث عمليات max--
ونحن قادرون على فتحة شخص في أي مكان في القائمة.
>> ما هو مفيد آخر حول قائمة مرتبطة؟
نعم؟
>> الجمهور: [غير مسموع]
DAVID مالان: الكمال.
الكمال.
انها ديناميكية حقا.
وأنك لا يقترفون في وقت مبكر، لبعض حجم ثابت
جزء من الذاكرة، مثل عملتم لمع مجموعة والصعود منها
هو أنه يمكنك تخصيص العقد فقط على الطلب وبالتالي تستخدم فقط بقدر الفضاء
ما تحتاج إليه فعلا.
على النقيض من ذلك مع مجموعة، وكنت قد قصد تخصيص القليل جدا.
ثم انها مجرد الذهاب أن يكون الألم في الرقبة
إعادة تخصيص مجموعة أكبر جديدة، نسخ كل شيء انتهى، سراح مجموعة القديمة،
ومن ثم الانتقال عن عملك.
أو ما هو أسوأ، قد تخصص الطريق ذاكرة أكبر مما تحتاج في الواقع،
وحتى وأنت تسير أن يكون لها جدا قليلة السكان، مجموعة، إذا جاز التعبير.
>> حتى قائمة مرتبطة تمنحك هذه مزايا الديناميكية والمرونة
مع الإدراج والحذف.
ولكن بالتأكيد يجب أن يكون هناك ثمن يدفع.
في الواقع، واحدة من المواضيع بحثت عن مسابقة الصفر
وكان اثنين من المقايضات رأيناه حتى الآن.
لذلك ما هو الثمن المدفوع أو الجانب السلبي من قائمة مرتبطة؟
نعم.
>> الجمهور: لا الوصول العشوائي.
>> DAVID مالان: لا الوصول العشوائي.
ولكن من يهتم؟
وصول عشوائي لا تبدو مقنعة.
>> الجمهور: [غير مسموع]
DAVID مالان: بالضبط.
إذا كنت تريد أن يكون من المؤكد algorithm--
واسمحوا لي أن أقترح فعلا البحث الثنائي على وجه الخصوص، والتي
هي واحدة استخدمنا تماما bit-- إذا لم يكن لديك الوصول العشوائي،
لا يمكنك أن تفعل ذلك بعملية حسابية بسيطة العثور على مثل عنصر الأوسط
والقفز الحق في ذلك.
يمكنك بدلا من ذلك أن تبدأ في أول والعنصر خطيا البحث من اليسار
إلى اليمين إذا كنت تريد أن تجد منتصف أو أي عنصر آخر.
>> الجمهور: إنه ربما يأخذ المزيد من الذاكرة.
>> DAVID مالان: يأخذ المزيد من الذاكرة.
حيث أن إضافية تكلفة قادمة من في الذاكرة؟
>> الجمهور: [غير مسموع]
DAVID مالان: بالضبط.
في هذه الحالة هنا، كان لدينا قائمة مرتبطة عن الأعداد الصحيحة،
وحتى الان نحن مضاعفة مقدار الذاكرة
نحتاج أيضا عن طريق تخزين هذه المؤشرات.
الآن أقل من صفقة كبيرة كما البنيات الخاصة بك الحصول على أكبر
وكنت تخزين عدد لا ولكن ربما طالب أو بعض وجوه الآخرين.
ولكن النقطة يبقى بالتأكيد.
وذلك في عدد من العمليات على القوائم المرتبطة كانت تسمى
كان يا كبير من الخطية n--.
أشياء مثل الإدراج أو البحث أو الحذف في حالة عنصر
حدث ليكون في النهاية من قائمة بشأن ما إذا كانت مرتبة أم لا.
>> أحيانا قد تحصل على الحظ و أقل حتى حدود على هذه العمليات
قد يكون أيضا وقتا ثابتا إذا كنت أبحث دائما في العنصر الأول،
على سبيل المثال.
ولكن في نهاية المطاف، وعدنا لتحقيق الكأس المقدسة
هياكل البيانات، أو بعض منه التقريب،
عن طريق وقت ثابت.
يمكن أن نجد العناصر أو إضافة عناصر أو إزالة العناصر من قائمة؟
سنرى قريبا جدا.
واتضح أن واحدة آليات نحن
الذهاب الى البدء في استخدام اليوم، الاستخدام السنوي في ص تعيين خمسة،
هو في الواقع مألوفة جدا.
على سبيل المثال، إذا كان هذا هو حفنة الكتب الامتحان، كل واحدة منها
لديه الطالب أولا اسم واسم العائلة على ذلك،
وأنا اعتقالهما من في نهاية الامتحان، و
وانهم جميعا جميلة الكثير في ترتيب عشوائي،
ونحن نريد أن تذهب حول فرز هذه الامتحانات بحيث أنه بمجرد متدرج
انه من الاسهل مجرد الكثير و أسرع لتسليمها الى الخلف
للطلاب أبجديا.
ما يمكن أن يكون لديك الغرائز لكومة من الامتحانات مثل هذا؟
>> حسنا، إذا كنت مثلي، وكنت قد نرى أن هذا هو م،
لذلك أنا ذاهب إلى نوع من وضع هذا في، إذا كان هذا هو مائدتي أو بلدي الطابق حيث
أنا نشر الاشياء out-- أو مجموعة بلدي really--
وأنا قد وضعت كل من السيدة في هناك.
أوه.
وإليك A. لذا ربما أنا كما وضعت أكثر من هنا.
أوه.
وهنا A. آخر سأشارك لوضع هذا هنا.
وهنا Z. هنا M. آخر وهكذا وأود أن تبدأ في وضع أكوام من هذا القبيل.
ثم ربما كنت اذهب في وقت لاحق ونوع من nitpicky لاي نوع جدا
أكوام الفردية.
ولكن النقطة هي وأود أن ننظر عند مدخل أنني سلمت
وأود أن جعل احتساب بعض القرار بناء على تلك المدخلات.
إذا كان يبدأ، ووضعها هناك.
إذا كان يبدأ مع Z، ووضعها فوق هناك، وبين في كل شيء.
>> لذلك هذا هو الاسلوب الذي ل المعروف عموما باسم hashing-- H-A-S-H--
مما يعني عموما اتخاذ ما إدخال واستخدام هذه المدخلات لحساب
قيمة، عموما عددا، والتي الرقم هو مؤشر إلى التخزين
الحاويات، مثل صفيف.
لذلك وبعبارة أخرى، وأنا قد يكون لها دالة تجزئة، كما أفعل أنا في رأسي،
أرى أنه إذا كان شخص ما الاسم الذي يبدأ مع،
انا ذاهب الى أن الخريطة إلى الصفر في رأسي.
وإذا رأيت شخص ما مع Z، وأنا الذهاب إلى الخريطة التي ل25 في رأسي
ثم وضع ذلك في اخر معظم كومة.
>> الآن، إذا كنت تفكر في عدم ذهني لكن برنامج C، ما يمكن أن أرقام
كنت تعتمد على تحقيق تلك النتيجة نفسها؟
وبعبارة أخرى، إذا كان ل كان ASCII حرف A،
كيف يمكنك تحديد ما دلو لوضعها في؟
ربما كنت لا تريد وضعها في دلو 65، والتي
سيكون مثل هناك لا لسبب وجيه.
أين تريد وضع و من حيث قيمة ASCII لها؟
أين تريد القيام به لASCII لها قيمة إلى الخروج مع دلو ذكاء
لوضعها في؟
>> الجمهور: ناقص أ.
>> DAVID مالان: نعم.
لذلك ناقص أو ناقص 65 تحديدا اذا كان
وA. رأس المال أو 98 إذا انها صغيرة و.
وذلك من شأنه أن يسمح لنا ل، جدا ببساطة وحسابيا جدا،
وضع شيء في دلو من هذا القبيل.
لذلك تبين أننا فعلا هذا فضلا حتى مع مسابقات.
>> لذلك قد أذكر لك حلقت بك اسم زميل التدريس على الغطاء.
ونظمت أسماء فريق العمل و في هذه الأعمدة أبجديا،
كذلك، صدقوا أو لا تصدقوا، عند كل واحد منا زائد 80
حصلت معا ليلة أخرى إلى الصف، الخطوة الأخيرة في عملية تصنيف لدينا
هو تجزئة في مسابقات كبيرة مساحة من الأرض في [غير مسموع]
ووضع مسابقات الجميع الخروج بالضبط في ترتيب TF لمن
أسماء على الغلاف، ل ثم أنه من الأسهل كثيرا بالنسبة لنا
للبحث من خلال ذلك باستخدام الخطية بحث أو نوع من الذكاء
لTF لتجد له أو مسابقات لها الطلاب.
>> لذلك هذه الفكرة من التجزئة عليك أن ترى
قوية جدا هي جميلة فعلا شائعا جدا وبديهية،
يشبه إلى حد كبير وربما تقسيم و كانت تسد في الأسبوع الصفر.
أنا سريع إلى الأمام إلى هاكاثون بضع سنوات مضت.
كان هذا Zamyla واثنين من الطلاب الآخرين تحية الموظفين
كما جاء في.
وكان لدينا مجموعة كاملة من للطي الجداول هناك مع علامات الأسماء.
وكنا قد نظمت علامات الاسم مع مثل وهناك
وزينب صالح أكثر من هناك.
وذلك واحد من TFS ذكي جدا كتبت هذا والتعليمات
لهذا اليوم.
و في الأسبوع 12 من الفصل الدراسي هذا جعل جميع الشعور بالكمال والجميع
أعرف ما يجب القيام به.
ولكن في أي وقت قمت قائمة الانتظار في نفس الطريق، و
كنت تنفيذ نفس فكرة تجزئة.
لذلك دعونا إضفاء الطابع الرسمي عليها قليلا.
هنا هو صفيف.
لقد سحبت منه أن يكون قليلا المرمى لتصوير، بصريا،
أننا قد وضعت السلاسل في شيء من هذا القبيل.
وهذه المجموعة هي واضح من حجم 26 المجموع.
ويسمى الشيء الجدول بشكل تعسفي.
ولكن هذا هو مجرد التسليم فنان ما قد يكون جدول التجزئة.
>> لذلك جدول تجزئة الآن هو الذهاب الى يكون هيكل البيانات على مستوى أعلى.
في نهاية اليوم نحن على وشك أن نرى لك
يمكن تنفيذ جدول التجزئة، والتي يشبه إلى حد كبير الخط تسجيل الوصول
في هاكاثون مثل الكثير من هذه استخدم الجدول لفرز الكتب الامتحان.
لكن جدول تجزئة هو هذا النوع من مستوى عال
المفهوم الذي يمكن استخدام صفيف تحت غطاء محرك السيارة لتنفيذها،
أو أنها يمكن أن تستخدم قائمة طول، أو حتى ربما بعض هياكل البيانات الأخرى.
والآن هذا هو أخذ theme-- بعض من هذه المكونات الأساسية
مثل مجموعة وهذا المبنى منع الآن من قائمة طول
ونرى ماذا يمكننا أن نبني على رأس هؤلاء، مثل المكونات
في وصفة، مما يجعل أكثر وأكثر النتائج النهائية مثيرة للاهتمام ومفيدة.
>> حتى مع جدول التجزئة نحن قد تنفيذه
في الذاكرة بالصور مثل هذا، ولكن كيف يمكن فعلا أن تكون مشفرة عنه؟
حسنا، ربما ببساطة هو هذا.
وإذا كانت السعة في كل مباراة دولية، هو فقط بعض constant-- على سبيل المثال 26،
26 الحروف alphabet-- يمكن أن أسميه مائدتي متغير،
وأود أن الادعاء بأن انا ذاهب الى وضع النجوم في شار هناك، أو سلسلة.
حتى انها بسيطة مثل هذا إذا كنت تريد تنفيذ جدول تجزئة.
وحتى الان، وهذا هو في الحقيقة مجرد صفيف.
ولكن مرة أخرى، تجزئة الجدول هو ما سنقوم الآن
استدعاء نوع البيانات مجردة هذا فقط نوع من الطبقات المفاهيمية على رأس
شيء أكثر دنيوية أود الآن صفيف.
>> الآن، كيف نذهب حول حل المشاكل؟
حسنا، كان في وقت سابق أنا ترف وجود مساحة كافية الجدول هنا
كي أتمكن من وضع مسابقات في أي مكان أريد.
بحيث قد يذهب هنا.
ZS قد يذهب هنا.
السيدة قد يذهب هنا.
ثم كان لي بعض المساحة الإضافية.
ولكن هذا هو جزء من حق الغش الآن بسبب هذا الجدول، إذا كنت حقا
فكر في الأمر على النحو صفيف، هو فقط ستكون بعض حجم ثابت.
>> لذلك من الناحية الفنية، إذا أنا سحب تصل مسابقة طالب آخر
ونرى، أوه، هذا الشخص الاسم يبدأ مع وللغاية،
النوع الأول من تريد وضعه هناك.
ولكن بمجرد أن وضعها هناك، وإذا هذا الجدول يمثل في الواقع مجموعة،
انا ذاهب الى أن تجاوز أو clobbering مسابقة من هذا الطالب هو.
أليس كذلك؟
إذا كان هذا هو صفيف، يمكن شيء واحد فقط تذهب في كل من هذه الخلايا أو العناصر.
وذلك نوع من ديك لانتقاء واختيار.
>> الآن وقت سابق من النوع الأول من خدع وفعل هذا أو أنا
مجرد نوع من مكدسة لها فوق بعضها البعض.
ولكن هذا لن يطير في التعليمات البرمجية.
فأين يمكن أن أضع الطالب الثاني اسمه
هو وإذا كان كل هذا الجدول الفضاء المتاح؟
ولقد استعملت ثلاث فتحات و يبدو أن هناك فقط عدد قليل من الآخرين.
ماذا يمكنك أن تفعل؟
الجمهور: [غير مسموع]
DAVID مالان: نعم.
ربما دعونا فقط يبقيه بسيط.
أليس كذلك؟
فإنه لا يصلح حيث كنت تريد وضعه.
لذلك أنا ذاهب لوضعها من الناحية الفنية حيث ان يذهب باء.
الآن، بالطبع، أنا بدأت لطلاء نفسي في الزاوية.
إذا كنت تحصل على طالب اسمه هو في الواقع B،
الآن ب سوف يتم نقلها قليلا إلى الأمام، كما قد يحدث، نعم،
إذا كان هذا هو B، والآن لديها للذهاب هنا.
>> وحتى هذا بسرعة جدا يمكن أن تصبح مشكلة،
ولكن هذا الاسلوب الذي فعلا ويشار إلى سبر الخطية،
حيث كنت مجرد النظر الخاصة بك مجموعة ليكون على طول الخط.
وكنت مجرد نوع من التحقيق أو فحص كل عنصر متاح
تبحث عن بقعة المتاحة.
وحالما تجد واحد، كنت تسقطها في هناك.
>> الآن، وسعر يولى الآن لهذا الحل ما هو؟
لدينا مجموعة وحجم ثابت، وعندما أقوم بإدخال أسماء
إلى ذلك، على الأقل في البداية، ما هو إدارة الوقت من الإدراج
لوضع الطلاب مسابقات في الدلاء الصحيحة؟
يا كبير لماذا؟
>> الجمهور: ن.
DAVID مالان: سمعت يا كبير من ن.
ليس صحيحا.
ولكننا سوف ندف بعيدا لماذا في لحظة فقط.
ماذا يمكن أن يكون؟
>> الجمهور: [غير مسموع]
DAVID مالان: واسمحوا لي أن تفعل ذلك بصريا.
ذلك ان هذا هو حرف S.
>> الجمهور: انها واحدة.
DAVID مالان: انها واحدة.
أليس كذلك؟
هذا هو صفيف، الذي يعني أن علينا الوصول العشوائي.
وإذا كنا نفكر في هذا كما الصفر، وهذا 25،
ونحن ندرك أنه، أوه، وهنا بلدي مدخلات S،
يمكنني تحويل بالتأكيد S، طابعا ASCII،
إلى الرقم المناظر بين صفر و 25
وبعد ذلك على الفور وضعها حيث تنتمي.
>> ولكن بطبيعة الحال، بمجرد أن نصل إلى الشخص الثاني الذي هو الاسم هو A أو B أو C
في النهاية، إذا كنت تستخدم و الخطية التحقيق كحل بلدي،
وقت تشغيل الإدراج في أسوأ الحالات
هو في الواقع تتحول الى الذهاب الى ماذا؟
وأنا لم أسمع من هنا بشكل صحيح في وقت مبكر.
الجمهور: [غير مسموع]
DAVID مالان: هكذا هو ن بالفعل مرة واحدة لديك مجموعة بيانات كبيرة بما فيه الكفاية.
لذلك، من جهة، وإذا كان مجموعة الخاصة بك كبيرة بما يكفي
والبيانات الخاصة بك هو متفرق بما فيه الكفاية، كنت الحصول على هذا الوقت الجميل المستمر.
ولكن بمجرد أن تبدأ الحصول على المزيد والمزيد من العناصر،
ومجرد إحصائية تحصل المزيد من الناس مع الرسالة
وكما اسمهم أو الحرف B، ويمكن لها ان
تؤول إلى شيء أكثر الخطية.
لذلك لم يكن مثاليا تماما.
لذلك يمكننا أن نفعل ما هو أفضل؟
>> كذلك، ما كان لدينا حل قبل عندما كنا
ترغب في الحصول على مزيد من الديناميكية شيء من هذا القبيل مجموعة سمحت؟
الجمهور: [غير مسموع]
DAVID مالان: ماذا نقدم؟
نعم.
حتى قائمة مرتبطة.
حسنا، دعونا نرى ما هو مرتبط القائمة قد تفعل بالنسبة لنا بدلا من ذلك.
حسنا، اسمحوا لي أن أقترح أن نحن رسم الصورة كما يلي.
الآن هذا هو مختلفة صورة من مثال
من نص مختلف، في الواقع، أن هو في الواقع باستخدام مجموعة من حجم 31.
وهذا الكاتب ببساطة قررت تجزئة السلاسل
لا تعتمد على أسماء الشخص، ولكن على أساس تواريخ ميلاد لهم.
بغض النظر عن الشهر، وأحسب إذا كنت ولدت في الأول من شهر
أو 31 من كل شهر، والكاتب سوف تجزئة على أساس تلك القيمة،
وذلك لنشر أسماء خارج قليلا أكثر من مجرد 26 نقاط قد تسمح.
وربما انها أكثر اتساقا الصغير من الذهاب مع حروف أبجدية،
لأنه بطبيعة الحال هناك على الارجح المزيد من الناس في العالم مع أسماء
أن تبدأ مع من المؤكد بعض الحروف الأخرى من الأبجدية.
ولذلك ربما يكون هذا هو قليلا أكثر تجانسا، على افتراض
توزيع موحد من الأطفال عبر مدة شهر.
>> ولكن، بطبيعة الحال، هذا لا يزال غير كامل.
أليس كذلك؟
نحن لها الاصطدامات.
العديد من الناس في هذا هيكل البيانات لا تزال
لها نفس تاريخ الميلاد على الأقل كنت بغض النظر عن الشهر.
ولكن ما قام به المؤلف؟
حسنا، يبدو أن لدينا مجموعة على الجانب الأيسر مرسومة عموديا،
ولكن هذا مجرد التسليم فنان.
لا يهم ما هو الاتجاه الذي رسم صفيف، انها لا تزال صفيف.
ما هذا مجموعة من ما يبدو؟
>> الجمهور: قائمة مرتبطة.
>> DAVID مالان: نعم.
يبدو انها ل مجموعة من قائمة مرتبطة.
ذلك مرة أخرى، إلى هذه النقطة من نوع لاستخدام هذه البيانات الهياكل الآن
كما أن المكونات أكثر حلول مثيرة للاهتمام،
يمكنك أن تأخذ على الاطلاق أساسية، مثل صفيف،
ثم تأخذ شيئا أكثر مثيرة للاهتمام مثل قائمة مرتبطة
وحتى الجمع بينهما إلى حتى بنية بيانات أكثر إثارة للاهتمام.
وبالفعل، فإن هذا من شأنه أيضا ان يسمى جدول التجزئة،
حيث المصفوفة هي حقا جدول التجزئة،
إلا أن لديه جدول التجزئة سلاسل، إذا جاز التعبير،
التي يمكن أن تنمو أو يتقلص بناء على عدد من العناصر التي تريد إدراجها.
>> الآن، وفقا لذلك، ما هو وتعمل الساعة الآن؟
إذا كنت ترغب في إدراج شخص الذين ميلاده هو 31 أكتوبر
أين هو أو هي تذهب؟
حسنا.
في أسفل جدا حيث تقول 31.
وهذا هو الكمال.
كان ذلك الوقت مستمر.
ولكن ماذا إذا وجدنا شخص آخر الذي هو، دعونا نرى عيد ميلاد،
أكتوبر ونوفمبر، 31 كانون الأول؟
حيث انه أو انها سوف تذهب؟
نفس الشيء.
على الرغم من خطوتين.
وهذا مستمر على الرغم أليس كذلك؟
حسنا.
في هذه اللحظة هو عليه.
ولكن في الحالة العامة، والمزيد من الناس نضيف،
احتماليا، نحن ذاهبون للحصول على المزيد والمزيد من الاصطدامات.
>> الآن هذا هو قليلا أفضل لأنه من الناحية التقنية
الآن سلاسل بلدي يمكن أن يكون في أسوأ الحالات إلى متى؟
إذا كنت أدخل ن الناس إلى هذا أكثر بنية بيانات متطورة، ن الناس،
في أسوأ الحالات انها ستكون ن.
لماذا؟
>> الجمهور: لأنه إذا كان الجميع لديه نفس عيد ميلاد،
انهم ذاهبون ليكون سطر واحد.
DAVID مالان: الكمال.
قد تكون مفتعلة قليلا، ولكن حقا في أسوأ الحالات،
إذا كان الجميع لديه نفس عيد ميلاد، بالنظر إلى المدخلات لديك،
وأنت تسير لدينا سلسلة طويلة اسع.
وهكذا، يمكن أن نسميها تجزئة الجدول، ولكن في الحقيقة انها ل
مجرد قائمة ضخمة مرتبطة مجموعة كبيرة من مساحة مهدرة.
ولكن بشكل عام، إذا افترضنا أن على الأقل أعياد الميلاد هي uniform--
وربما لا يكون.
أنا صنع ما يصل.
ولكن لو افترضنا، ل من أجل مناقشة
أنهم، ثم من الناحية النظرية، إذا هذا هو التمثيل العمودي
للمجموعة، بالاضافة الى ذلك الحين نأمل كنت ذاهب للحصول على سلاسل التي هي، كما تعلمون،
تقريبا نفس طول فيها كل من هذه يمثل يوم من الشهر.
>> الآن إذا كان هناك 31 يوما في الشهر، وهذا يعني وقتي تشغيل حقا
هو يا كبير من ن أكثر من 31، والتي يشعر على نحو أفضل من الخطية.
ولكن ما كان أحد لدينا الالتزامات أسبوعين
منذ متى جاء إلى التعبير عن وقت التشغيل خوارزمية؟
مجرد إلقاء نظرة فقط على المدى ذات الترتيب.
أليس كذلك؟
31 من المفيد بالتأكيد.
ولكن هذا لا يزال يا كبير من ن.
ولكن واحدا من المواضيع المشكلة تعيين خمسة
سيكون ل نعترف بأن الاطلاق،
مقارب، نظريا هذه البنية البيانات
ليس أفضل من مجرد قائمة واحدة ضخمة مرتبطة.
وبالفعل، في أسوأ الحالات، وهذا قد تؤول جدول التجزئة إلى ذلك.
>> ولكن في العالم الحقيقي، معنا البشر أن أجهزة ماكينتوش الخاصة أو أجهزة الكمبيوتر أو أيا كان
وتشغل العالم الحقيقي برامج على بيانات العالم الحقيقي،
الخوارزمية التي أنت ذاهب لتفضل؟
واحد أن يأخذ خطوات نهاية أو واحد أن يأخذ مقسمة ن بنسبة 31 خطوات
العثور على بعض قطعة من البيانات أو للبحث عن بعض المعلومات؟
أعني، بالتأكيد على 31 طرازا الفرق في العالم الحقيقي.
هو 31 مرات أسرع.
ونحن البشر هي بالتأكيد سوف نقدر ذلك.
>> حتى ندرك الانقسام هناك بين الواقع
نتحدث عن الأشياء نظريا ومقارب التي بالتأكيد
له قيمة كما رأينا، ولكن في العالم الحقيقي،
إذا كنت تهتم فقط جعل سعيدة الإنسان للمدخلات العامة،
قد ترغب أيضا جدا لقبول حقيقة، نعم، هذا هو خطي،
ولكن من 31 مرات أسرع قد يكون من الخطية.
والأفضل من ذلك، ليس لدينا فقط ل تفعل شيئا التعسفي مثل تاريخ الميلاد،
نحن يمكن أن تنفق قليلا المزيد من الوقت والذكاء
ونفكر في ما يمكن القيام به، أعطيت اسم الشخص وربما
تاريخ الميلاد إلى الجمع بين تلك المكونات لمعرفة شيء
هذا هو حقا أكثر موحدة وأقل جاجي،
إذا جاز التعبير من هذه الصورة. يقترح حاليا قد يكون.
كيف يمكن أن ننفذ هذا في التعليمات البرمجية؟
حسنا، اسمحوا لي أن أقترح أن نحن مجرد استعارة بعض تركيب قمنا
تستخدم بضع مرات حتى الآن.
وانا ذاهب الى تعريف عقدة، والذي مرة أخرى
هو مصطلح عام للبعض فقط حاوية لبعض هياكل البيانات.
انا ذاهب الى أقترح أن سلسلة يجري في هناك.
ولكن نحن ذاهبون للبدء في اتخاذ تلك العجلات تدريب حالا الآن.
>> أي مكتبة CS50 المزيد حقا، إلا إذا كنت تريد
لاستخدامها لنهائي الخاص المشروع، والتي على ما يرام،
ولكن الآن نحن ذاهبون إلى التراجع و ستارة ويقولون انها مجرد نجم شار.
لذلك هناك كلمة ستكون اسم الشخص المعني.
والآن لدي صلة هنا إلى العقدة التالية
بحيث تمثل هذه كل من العقد
في سلسلة، ويحتمل، من قائمة مرتبطة.
>> والآن كيف يمكنني الإعلان جدول التجزئة نفسها؟
كيف يعلن هذا الهيكل كله؟
حسنا، حقا، مثل الكثير اعتدت مؤشر لمجرد العنصر الأول من القائمة
من قبل، وبالمثل يمكن أن أقول فقط أنا فقط بحاجة إلى مجموعة من المؤشرات
لتنفيذ هذا الجدول التجزئة كله.
أنا ذاهب لديها مجموعة دعا جدول لجدول التجزئة.
انها سوف تكون ذات قدرة الحجم.
هذه هي الطريقة العديد من العناصر يمكن أن يصلح في ذلك.
ولكل من تلك العناصر في هذا مجموعة سيكون نجم العقدة.
لماذا؟
حسنا، في هذه الصورة، ما أنا تنفيذ جدول التجزئة كما
بفعالية في بداية هي مجرد هذه المجموعة التي كانت لدينا رسمها عموديا،
كل المربعات التي يمثل مؤشر.
أن تلك التي لديها خطوط مائلة من خلال منهم فقط اغية.
وتلك التي لديها سهام الذهاب إلى اليمين
هي مؤشرات فعلية إلى العقد الفعلية، ولهذا بداية لقائمة مرتبطة.
>> حتى هنا، إذن، هو كيف يمكننا تنفيذ جدول التجزئة التي
تنفذ تسلسل منفصل.
الآن يمكننا أن نفعل أفضل؟
كل الحق عدت المرة الأخيرة التي نحن يمكن أن يحقق الزمن المستمر.
والنوع الأول من أعطاك وقت ثابت هنا،
ولكن بعد ذلك قال لا حقا وقت ثابت لأنه ما زال
تعتمد على مجموعه عدد من العناصر
كنت في إدخال بنية البيانات.
ولكن لنفترض فعلنا هذا.
اسمحوا لي أن أعود إلى الشاشة أكثر من هنا.
اسمحوا لي أيضا هذا المشروع هنا، واضحة الشاشة، وأعتقد أنني فعلت ذلك.
لنفترض أنني أردت أن إدراج اسم Daven في داخل بنية البيانات الخاصة بي.
>> لذلك أريد أن إدراج سلسلة Daven في بنية البيانات.
ماذا لو كنت لا تستخدم تجزئة الجدول، ولكن يمكنني استخدام
شيء أن يكون أكثر شجرة شبيهة مثل شجرة العائلة، حيث
لديك بعض جذور في أعلى ثم العقد والأوراق
أن تذهب إلى أسفل وإلى الخارج.
لنفترض إذن أن أنا تريد إدراجه في Daven
إلى ما هو حاليا قائمة فارغة.
انا ذاهب للقيام بما يلي: أنا الذهاب الى خلق عقدة في هذه العائلة
شجرة تشبه بنية البيانات التي تبدو قليلا من هذا القبيل، كل واحدة منها
والمستطيلات، دعنا نقول، في الوقت الراهن 26 عناصر فيه.
وكل من الخلايا في هذه المجموعة هو الذهاب
لتمثيل حرف من الأبجدية.
>> على وجه التحديد، وانا ذاهب لعلاج هذا هو A، ثم B، C بعد ذلك، ثم D،
هذا واحد هنا.
لذلك هذا هو الذهاب الى فعال تمثل الرسالة د.
ولكن لإدراج كافة في Daven اسم يجب أن أفعل أكثر قليلا.
لذلك أنا ذاهب أول من البعثرة، إذا جاز التعبير.
انا ذاهب للنظر في الرسالة الأولى في لDaven التي من الواضح أن D،
وانا ذاهب الى تخصيص عقدة التي تبدو
مثل this-- مستطيل كبير كبير بما يكفي لتناسب الأبجدية كلها.
>> الآن يتم التطوير.
الآن A. D-A-V-E-N هو الهدف.
حتى الآن ما أنا ذاهب الى القيام به هو هذا.
وسرعان ما بدأ إشعار D وليس هناك مؤشر هناك.
انها القيم القمامة في الوقت الراهن، أو أنني قد تهيئة إلى قيمة خالية.
ولكن اسمحوا لي الاستمرار مع هذه فكرة بناء شجرة.
اسمحوا لي أن تخصص آخر واحد من هؤلاء العقد التي لديها 26 عناصر فيه.
>> وأنت تعرف لماذا؟
إذا كان هذا هو مجرد عقدة في الذاكرة أنا خلقت مع malloc، باستخدام البنية
كما سنرى قريبا، انا ذاهب الى القيام this--
انا ذاهب الى رسم السهم من الشيء الذي يمثل D الأسفل
لهذه العقدة الجديدة.
والآن، لأول مرة المقبل حرف في اسم Daven و
V-- D-A-V-- انا ذاهب الى المضي قدما ولفت عقدة أخرى من هذا القبيل،
حيث أن عناصر V هنا، والتي سنقوم رسم ليصيح instance--.
نحن لن يوجه هناك.
انها سوف تذهب هنا.
>> ثم نحن في طريقنا ل نعتبر هذا V.
ثم إلى هنا ونحن في طريقنا إلى مؤشر نزولا من الخامس إلى ما نحن سنعتبر E.
ثم من هنا نحن ذاهبون ل الذهاب لديها واحدة من هذه العقد هنا.
والآن لدينا سؤال للإجابة.
أحتاج إلى حد ما يدل على أن نحن في نهاية السلسلة Daven.
حتى أتمكن من مجرد ترك الأمر لاغيا.
>> ولكن ماذا لو كان لدينا في Daven الاسم الكامل أيضا، والتي
هو، كما قلنا، دافنبورت؟
فما هو إذا Daven في الواقع فرعية،
بادئة سلسلة أطول من ذلك بكثير؟
لا يمكننا فقط بشكل دائم ناهيك يسير
للذهاب هناك، لأننا يمكن أن أبدا إدراج كلمة مثل دافنبورت
في هذا الهيكل بيانات
>> وذلك ما يمكن أن نقوم به بدلا من ذلك هو معالجة كل من هذه العناصر
كما ربما وجود اثنين عناصر داخل منهم.
واحد هو مؤشر، في الواقع، كما كنت تفعل.
لذلك كل من هذه الصناديق ليس من خلية واحدة فقط.
ولكن ماذا لو أعلى one-- القاع واحد
ستكون باطلة، ل لا يوجد دافنبورت فقط حتى الآن.
ماذا لو رأس واحد هي بعض القيمة الخاصة؟
وأنه سيكون قليلا من الصعب استدراجه هذا الحجم.
ولكن لنفترض انها مجرد علامة الاختيار.
تحقق.
D-A-V-E-N هو سلسلة في هذا الهيكل البيانات.
>> وفي الوقت نفسه، إذا كان لدي المزيد من المساحة هنا، يمكن أن أفعله P-O-R-T،
وأنا قد وضعت الاختيار في العقدة الذي يحتوي على الحرف T في النهاية.
لذلك هذا هو نطاق واسع هيكل البيانات المظهر تعقيدا.
وعلى خط اليد بلدي بالتأكيد لا يساعد.
ولكن إذا أردت أن أدخل شيئا آخر، والنظر في ما سنفعله.
إذا أردنا أن نضع ديفيد عام، كنا اتبع نفس المنطق، D-A-V،
ولكن الآن أود أن أشير في القادم وليس من عنصر E، ولكن من أنا لD.
لذلك هناك ستكون أكثر من العقد في هذه الشجرة.
نحن ذاهبون الى دعوة malloc أكثر.
لكنني لا تريد أن تجعل من فوضى كاملة في هذه الصورة.
لذلك دعونا ننظر بدلا من ذلك في واحدة التي تم صياغتها قبل
مثل هذا لا مع وزارة النقل، وزارة النقل، النقاط، ولكن المصفوفات يختصر فقط.
ولكن كل من العقد في هذه الشجرة يصل هنا
يمثل نفسه thing-- مجموعة راي من حجم 26.
>> أو إذا كنا نريد أن نكون السليم حقا الآن، ما
إذا كان اسم شخص ما باعتباره الفاصلة العليا، دعونا
نفترض أن كل عقدة لديه في الواقع مثل 27 الفهارس في ذلك، وليس 26 فقط.
حتى الآن هذه ستكون بيانات هيكل يسمى trie-- T-R-I-E.
وTRIE، التي يفترض تاريخيا اسم ذكي للشجرة
هذا هو الأمثل ل استرجاعها، والتي بالطبع،
هو مكتوبة مع I-E لذلك فمن TRIE.
ولكن هذا هو تاريخ TRIE.
>> لذلك هو TRIE هذه البيانات تشبه شجرة هيكل وكأنه شجرة العائلة
أن يتصرف في نهاية المطاف من هذا القبيل.
وهنا هو مجرد مثال آخر ل مجمله مجموعة من أسماء أشخاص آخرين.
ولكن السؤال الآن في جهة ما لديهم
حصلنا عن طريق إدخال يمكن القول أكثر بنية بيانات معقدة، واحدة،
بصراحة، يستخدم الكثير من الذاكرة.
>> لأنه حتى وإن، في هذه اللحظة، أنا فقط
باستخدام مؤشر D'S و ألف والخامس والخانات وم،
أنا إضاعة من هيك الكثير من الذاكرة.
ولكن أين أقضي مورد واحد، أنا أميل إلى لا تستعيد آخر.
حتى إذا أقضي المزيد من المساحة، ما هو على الارجح الأمل؟
أن أقضي أقل ما؟
الجمهور: وقت أقل.
DAVID مالان: الزمان.
الآن ماذا يمكن أن يكون؟
حسنا، ما هو الإدراج الوقت، من حيث يا كبير الآن،
من اسم مثل Daven أو دافنبورت أو ديفيد؟
كذلك، كان Daven خمس خطوات.
سوف تكون دافنبورت تسع خطوات، لذلك سيكون المزيد من الخطوات القليلة.
سوف يكون ديفيد خمس خطوات كذلك.
حتى تلك هي ملموسة أرقام، ولكن بالتأكيد هناك
الحد الأعلى ل طول اسم شخص ما.
وبالفعل، في مشكلة مجموعات من خمس مواصفات،
نحن ذاهبون الى اقتراح أنه شيء
هذا هو حرفا 40-بعض ونيف.
>> واقعيا، لا أحد لديه اسم طويل بلا حدود،
وهو ما يعني أن طول الاسم أو طول سلسلة أننا قد
لدينا يقين دولة هيكل يمكن القول ماذا؟
انها ثابتة.
أليس كذلك؟
قد يكون ثابت كبير مثل 40-شيء، وإنما هو مستمر.
وأنه لا يوجد لديه الاعتماد على كم أسماء أخرى في هذا الهيكل البيانات.
وبعبارة أخرى، إذا أنا أردت أن أدخل الآن
كولتون أو جبريل أو روب أو Zamyla أو أليسون أو بليندا أو أي أسماء أخرى
من الموظفين في هذه البيانات هيكل، هو إدارة الوقت
من إدراج أسماء أخرى سيكون على كل أثر
من قبل كيف العديد من العناصر الأخرى ل في بنية البيانات بالفعل؟
انها ليست.
أليس كذلك؟
لأننا باستخدام فعال هذه البعثرة الجدول متعددة الطبقات.
ووقت تشغيل أي من هذه العمليات
لا تعتمد على عدد من العناصر التي هي في بنية البيانات
أو أن تسير في نهاية المطاف أن تكون في بنية البيانات،
ولكن على طول ما على وجه التحديد؟
>> سلسلة كونه المدرجة، والتي لا تجعل
هذا الثابت مقارب يا كبير time-- واحد.
وبصراحة، فقط في في العالم الحقيقي، وهذا
يعني إدخال يأخذ اسم Daven ل مثل خمس خطوات، أو تسعة دافنبورت
الخطوات، أو ديفيد خمس خطوات.
هذا الرتق صغيرة مرة على التوالي.
و، في الواقع، وهذا هو غاية شيء جيد، وخصوصا عندما
انها لا تعتمد على مجموع عدد العناصر في هناك.
فكيف يمكن أن نطبق هذا نوع من الهيكل في الرمز؟
انها اكثر قليلا مجمع، ولكن لا يزال انها
مجرد تطبيق اللبنات الأساسية.
انا ذاهب الى إعادة تعريف عقدة لنا على النحو التالي:
منطقي يسمى word-- وهذا يمكن أن يسمى أي شيء.
ولكن منطقي يمثل ما وجهت باعتباره علامة الاختيار.
نعم.
هذه هي نهاية سلسلة في هذا الهيكل البيانات.
>> وبطبيعة الحال، نجم العقدة هناك إشارة إلى الأطفال.
وبالفعل، تماما مثل شجرة العائلة، ل
ستنظر العقد التي تتدلى
الجزء السفلي من بعض الوالدين العنصر أن يكون الأطفال.
وحتى الأطفال سوف تكون مجموعة من 27، واحد 27
لمجرد كونها الفاصلة العليا.
ونحن في طريقنا لفرز حالة خاصة من ذلك.
لذلك يمكن أن يكون على يقين أسماء مع الفواصل العليا.
ربما ينبغي حتى اصلة الذهاب إلى هناك، ولكن عليك
نرى في ص 5 نحن مجموعة الرعاية فقط حول الرسائل والفواصل العليا.
>> ثم كيف يمكن تمثيل هيكل البيانات نفسها؟
كيف تمثل الجذر هذا TRIE، إذا جاز التعبير؟
حسنا، تماما مثل مع قائمة مرتبطة، كنت تحتاج مؤشر إلى العنصر الأول.
مع TRIE تحتاج فقط واحد مؤشر إلى جذر هذه TRIE.
ومن هناك يمكنك تجزئة طريقك إلى أسفل أعمق وأعمق
على كل عقدة أخرى في الهيكل.
هكذا ببساطة مع هذا يمكن نمثلها أن البنية.
>> الآن Meanwhile-- أوه، سؤال.
>> الجمهور: ما هي كلمة منطقي؟
>> DAVID مالان: كلمة منطقي ل فقط هذا التجسد C
ما وصفتها في هذا المربع هنا، عندما
بدأت تقسيم كل من عناصر المصفوفة إلى قطعتين.
واحد هو مؤشر إلى عقدة القادمة.
الآخر يجب أن يكون شيء مربع الاختيار مثل
لنقول نعم، هناك كلمة Daven أن ينتهي هنا،
لأننا لا نريد، في هذه اللحظة، ديف.
>> على الرغم من ديف وستكون كلمة المشروعة، وانه ليس في TRIE
حتى الان.
D وليس كلمة واحدة.
وD-A ليست كلمة أو اسما.
حتى علامة الاختيار يشير فقط مرة واحدة لك
ضرب هذه العقدة هي مسار السابق من الحروف
في الواقع سلسلة التي قمت بإدراجه.
ذلك أن جميع منطقي هناك يفعل بالنسبة لنا.
>> أي أسئلة أخرى عن محاولات؟
نعم.
>> الجمهور: ما هو التداخل؟
ماذا لو كان لديك ديف وDaven؟
DAVID مالان: الكمال.
ماذا لو كان لديك ديف وDaven؟
لذلك إذا أردنا إدراج، ويقول كنية، لDavid-- Dave-- D-A-V-E؟
هذا هو في الواقع بسيط السوبر.
لذلك نحن ذاهبون فقط لاتخاذ أربع خطوات.
D-A-V-E. وماذا لدي ل به مرة واحدة أنا ضربت تلك العقدة الرابعة؟
مجرد الذهاب للتحقق.
نحن بالفعل على ما يرام.
القيام به.
أربع خطوات.
وقت ثابت مقارب.
ونحن الآن قد أشارت إلى أن كلا من ديف وDaven والسلاسل في الهيكل.
حتى لا مشكلة.
ولاحظ كيف وجود من Daven لم يجعل
اتخاذ أي المزيد من الوقت أو أقل الوقت لديف والعكس بالعكس.
>> لذلك ماذا يمكننا أن نفعل الآن؟
لقد استخدمت هذا التشبيه قبل من الأدراج تمثل شيئا.
ولكن تبين أن كومة من الأدراج هو في الواقع
بيانية لبيانات مجردة آخر type-- هيكل البيانات على مستوى أعلى
أنه في نهاية اليوم هو فقط مثل صفيف أو قائمة مرتبطة
أو شيء أكثر دنيوية.
بل انها أكثر إثارة للاهتمام المفهوم النظري.
وهناك كومة، مثل هذه الصواني هنا في ماذر،
ويطلق عموما that-- مجرد كومة.
>> وهذا النوع من هياكل البيانات لديك اثنين من operations--
لديك واحد يسمى دفعة ل إضافة شيء إلى المكدس،
مثل وضع علبة أخرى العودة إلى أعلى المكدس.
ثم البوب، مما يعني أنك اتخاذ العلوي صينية قبالة.
ولكن ما هو المفتاح نحو كومة هو أن انها حصلت على هذه الخاصية غريبة.
كما الموظفين قاعة الطعام ل إعادة ترتيب الصواني لالوجبة التالية،
ما سيكون صحيح حول كيفية طلاب
التفاعل مع هذا الهيكل البيانات؟
الجمهور: انهم ذاهبون لموسيقى البوب ​​مرة واحدة.
DAVID مالان: انهم ذاهبون ل البوب ​​مرة واحدة، ونأمل أعلى.
وإلا فإنه مجرد نوع من الغباء ليذهب كل في طريقه إلى أسفل.
أليس كذلك؟
لا بنية البيانات لا تسمح حقا لك للاستيلاء على أسفل الدرج على الأقل
بسهولة.
ولذلك لا يوجد هذا الغريب الملكية إلى كومة
إن العنصر الأخير في ل ستكون أول من أصل واحد.
ويطلق علماء الكمبيوتر هذا LIFO-- تستمر في، لأول مرة.
والواقع أنه لا توجد لديها تطبيقات مثيرة للاهتمام.
انها ليست بالضرورة واضحة مثل بعض الآخرين، ولكن يمكن، في الواقع، أن تكون مفيدة،
ويمكن، في الواقع، أن تنفذ في عدة طرق مختلفة.
>> حتى واحد، وفعلا، والسماح مني عدم الغوص في ذلك.
دعونا نفعل هذا بدلا من ذلك.
دعونا ننظر في واحد وهذا تقريبا نفس الفكرة، ولكن هذا قليلا أكثر عدلا.
أليس كذلك؟
إذا كنت واحدا من هؤلاء الأولاد أو مروحة الفتاة التي يحب حقا منتجات أبل
وكنت استيقظ الساعة 3:00 صباحا ليصطف في بعض متجر
للحصول على أحدث فون جدا، كنت قد اصطفوا من هذا القبيل.
>> الآن يدعى طابور عمدا جدا.
انها خط لأن هناك بعض الإنصاف لها.
أليس كذلك؟
انه نوع من السقوط إذا كنت قد حصلت هناك أولا في متجر أبل
ولكن كنت بشكل فعال bottommost علبة لأن موظفي أبل ثم
البوب ​​آخر شخص حصلت فعلا في الخط.
حتى مداخن وقوائم الانتظار، على الرغم من ظيفيا انهم نوع من same--
انها مجرد هذه المجموعة موارد هذا
سوف تنمو وshrink-- هناك هذا الجانب الإنصاف إليه،
على الأقل في العالم الحقيقي، حيث يمكنك ممارسة عمليات
تختلف جذريا.
وstack-- طابور rather-- يقال لها
عمليتين: ن الانتظار والانتظار د.
أو يمكنك الاتصال بهم أي عدد من الاشياء.
ولكن كنت ترغب فقط في التقاط فكرة أن واحد يضيف
واحد هو طرح في نهاية المطاف.
>> الآن تحت غطاء محرك السيارة، كل من كومة ويمكن تنفيذ طابور كيف؟
نحن لن نذهب إلى رمز لل ذلك لأن مستوى أعلى
الفكرة هي نوع من أكثر وضوحا.
أعني، ماذا يفعل البشر؟
إذا أنا أول شخص في أبل تخزين وهذا هو الباب الأمامي،
كما تعلمون، انا ذاهب الى الوقوف هنا.
والشخص المقبل الذهاب لنقف هنا.
فما بنية البيانات يفسح المجال لطابور؟
>> الجمهور: طابور.
DAVID مالان: حسنا، طابور.
بالتأكيد.
ماذا بعد؟
>> الجمهور: قائمة مرتبطة.
>> DAVID مالان: مرتبط قائمة هل يمكن تنفيذها.
وقائمة مرتبطة هو لطيف لأن ثم أنها يمكن أن تنمو بشكل تعسفي طالما عارضت
إلى وجود بعض عدد ثابت الناس في المخزن.
ولكن ربما عدد ثابت من الأماكن غير مشروعة.
لأنه إذا كان لديهم فقط مثل 20 فون في اليوم الأول، ربما
أنهم بحاجة إلى مجموعة من حجم فقط 20 لتمثيل أن قائمة الانتظار، والتي
هو فقط أن أقول الآن مرة واحدة نبدأ الحديث حول هذه المشاكل مستوى أعلى،
يمكنك تنفيذ ذلك في أي عدد من الطرق.
وهناك على الارجح مجرد الذهاب ل تكون المفاضلة في المكان والزمان
أو فقط في تعقيد كود خاص بك.
>> ماذا عن كومة؟
حسنا، كومة، شهدنا أيضا يمكن أن يكون مجرد هذه الصواني.
ويمكن تطبيق هذا صفيف.
ولكن في مرحلة ما إذا كنت تستخدم صفيف، ما الذي سيحدث لالصواني
كنت في محاولة لاخماد؟
حسنا.
وأنت تسير فقط ل يكون قادرا على الذهاب عالية جدا.
واعتقد انهم في ماثر توقفت فعليا في هذا الافتتاح.
حتى في الواقع، انها تقريبا مثل ماثر هو استخدام
مجموعة من حجم ثابت، لأنك تستطيع فقط
تناسب الكثير من الصواني في هذا الافتتاح في الجدار نزولا تحت الركبتين الناس.
وهكذا يمكن أن يكون وقال لتكون صفيف،
ولكننا بالتأكيد يمكن تنفيذ ذلك بشكل عام مع قائمة مرتبطة.
>> حسنا، ماذا عن هيكل بيانات آخر؟
اسمحوا لي أن تشمر الآخر المرئي هنا.
شيء من هذا القبيل وكيف حول هذا واحد هنا؟
لماذا قد يكون من المفيد أن يكون لا شيء كما يتوهم بأنه TRIE، التي
شهد كان لدينا هذه العقد واسعة جدا، كل منها في مجموعة؟
ولكن ماذا اذا لم نفعل شيئا أكثر ببساطة، وكأنه شجرة العائلة المدرسة القديمة،
كل الذي عقد هنا هو فقط تخزين رقم.
بدلا من اسم أو سليل هو مجرد تخزين عدد من هذا القبيل.
>> كذلك، فإن المصطلحات التي نستخدمها في هياكل البيانات هي كل من يحاول
والأشجار، حيث TRIE، مرة أخرى، هو واحد الذين العقد هي المصفوفات فقط،
لا يزال ما يمكن استخدام من المدارس الابتدائية
عندما قمت بعمل الأسرة tree-- الأوراق والجذر
من شجرة وأطفال الأم والأخوة والأخوات منها.
ونحن قد تنفذ شجرة، على سبيل المثال، ببساطة لأن هذا.
شجرة، إذا أنها عقدة، واحدة من هذه الاوساط التي لديها عدد،
انها ليست ستكون لدينا مؤشر واحد، ولكن اثنين.
وبمجرد إضافة مؤشر الثاني، ل
يمكن في الواقع جعل الآن نوع البيانات ثنائية الأبعاد
هياكل في الذاكرة.
مثل الكثير من ثنائي الأبعاد مجموعة، يمكنك
لديهم نوع من ثنائي الأبعاد ولكن تلك القوائم المرتبطة
ان اتباع نمط حيث لا يوجد دورات.
انها حقا شجرة واحدة طريقة جد هنا وثم
بعض الآباء والأمهات والأطفال و الأحفاد وأبناء الأحفاد.
وهكذا دواليك.
>> ولكن ما هو أنيق حقا عن هذا أيضا، و فقط لندف لكم مع قليل من التعليمات البرمجية،
استدعاء عودية من لحظة العودة، حيث
أن تكتب وظيفة تطلق على نفسها.
هذا هو فرصة جميلة لتنفيذ شيء
مثل العودية، لأن النظر في هذا.
>> هذه هي شجرة.
ولقد كنت الشرج قليلا مع كيف أضع الأعداد الصحيحة إلى الشارع.
لدرجة أن لديها خاصة name-- شجرة البحث الثنائية.
نحن الآن قد سمعت من ثنائي البحث، ولكن يمكنك
العمل الوراء من اسم هذا الشيء في؟
ما هو نمط كيف إدراج الأعداد الصحيحة في هذه الشجرة؟
انها ليست التعسفي.
هناك بعض النمط.
نعم.
>> الجمهور: أصغر على اليسار.
>> DAVID مالان: نعم.
أصغر هي على اليسار.
الاكبر هي على حق.
مثل أن يكون البيان صحيحا هو الأم أكبر من الطفل الأيسر،
ولكن أقل من الطفل الأيمن.
وهذا وحده هو حتى تعريف اللفظي عودي
لأنك يمكن أن تنطبق المنطق نفسه على كل عقدة
والقيعان فقط خارج، وهي قضية قاعدة إذا كنت
سوف، عندما ضرب أحد الأوراق، إذا جاز التعبير،
حيث إجازة لا يوجد لديه أطفال أكثر.
>> الآن كيف يمكن أن تجد عدد 44؟
سوف تبدأ في جذور ويقول صاحب الجلالة.
55 ليس 44 لذا لا أريد أن أذهب احقاق الحق أو أريد أن أذهب اليسار؟
حسنا، من الواضح تريد أن تذهب اليسار.
وحتى انها تماما مثل الهاتف كتاب المثال في البحث ثنائي
أكثر عموما.
لكننا تنفيذها الآن أكثر من ذلك بقليل حيوي
من صفيف قد تسمح.
وفي الواقع، إذا كنت تريد أن تبدو في رمز، للوهلة الأولى بالتأكيد.
يبدو في مجمله مجموعة من الخطوط.
ولكن الامر بسيط جميل.
إذا كنت ترغب في تنفيذ وظيفة ودعا البحث هدفها في الحياة
هو البحث عن قيمة مثل ن، وهو صحيح،
وكنت أصدر في pointer-- واحد مؤشر إلى العقدة من جذورها،
بدلا من تلك الشجرة التي يمكنك الوصول إلى كل شيء آخر،
لاحظ كيف مباشر يمكنك تطبيق المنطق.
إذا شجرة فارغة، من الواضح أنه ليس هناك.
دعونا فقط العودة كاذبة.
أليس كذلك؟
إذا كنت تسليمه شيئا، لا يوجد شيء هناك.
>> آخر، إذا كان n أقل من شجرة n-- السهم السهم الآن ن،
أذكر قدمنا ​​السوبر لفترة وجيزة في اليوم الآخر،
وهذا يعني فقط دي الإسناد و مؤشر وإلقاء نظرة على حقل يسمى ن.
ذلك يعني الذهاب الى هناك و ننظر في حقل يسمى ن.
حتى إذا ن، وقيمة كنت أعطيت، هو أقل من القيمة في صحيح الأشجار،
أين تريد أن تذهب؟
إلى اليسار.
>> لذلك تلاحظ العودية.
أنا returning-- ليس صحيحا.
لا كاذبة.
أعود مهما كانت الإجابة هو من استدعاء نفسي، ويمر
ون مرة أخرى، والتي هي زائدة عن الحاجة، ولكن ما هو مختلف قليلا الآن؟
كيف أنا جعل المشكلة أصغر؟
أنا مارة في كثاني حجة، وليس جذر الشجرة،
ولكن الطفل الأيسر في هذه الحالة.
لذلك أنا مارة في الطفل الأيسر.
>> وفي الوقت نفسه، إذا كان n هو أكبر من عقدة أنا أبحث حاليا في،
أنا ابحث الجهة اليمنى.
آخر، إذا كانت الشجرة ليست فارغة، و إذا كان العنصر ليس إلى اليسار
وانها ليست على حق، ما هي حالة رائعة؟
وجدنا فعلا عقدة في السؤال، ولذا فإننا العودة الحقيقية.
>> لذلك قمنا مجرد خدش السطح الآن بعض من هذه الهياكل البيانات.
مشكلة في تعيين خمسة عليك استكشاف هذه بعد أخرى،
وعليك أن تعطى التصميم الخاص بك اختيار كيفية التوجه نحو ذلك.
ما أود ان تختتم يوم هو مجرد دعابة 30 ثانية
ما ينتظر الأسبوع المقبل وما بعده.
>> ونحن والحمد لله كنت قد begin-- think-- انتقالنا ببطء
من عالم C والدنيا تفاصيل التنفيذ مستوى،
إلى العالم الذي يمكن أن نتخذها ل المسلم به أن شخص آخر لديه أخيرا
نفذت هذه البيانات الهياكل بالنسبة لنا،
وسنبدأ في فهم العالم الحقيقي يعني تنفيذ
البرامج القائمة على الويب و المواقع بشكل عام
وأيضا أمن جدا الآثار التي كانت لدينا فقط
بدأت تخدش سطح.
هنا هو ما ينتظرنا في الأيام القادمة.
>> [تشغيل الفيديو]
>> -He جاء مع الرسالة، مع كل بروتوكول بلده.
وقال انه جاء الى عالم من ضروب الجدران النارية، والموجهات غير مكترثة،
ومخاطر أسوأ بكثير من الموت.
انه سريع.
انه قوي.
انه TCP / IP، وانه حصل على عنوانك.
"ووريورز للنت".
[END تشغيل الفيديو]
DAVID مالان: قادمة الأسبوع المقبل.
سوف نرى لك ذلك الحين.
[تشغيل الفيديو]
-وعلى الآن "، والأفكار العميقة" بواسطة Daven فارنهام.
يبدأ -David دائما محاضرات مع "كل الحق".
لماذا لا "، وإليك الحل لمجموعة مشكلة هذا الأسبوع "
أو "نحن منحنا كل واحد منكم على ألف؟"
[يضحك]
[END تشغيل الفيديو]