[عزف الموسيقى] 

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

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

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

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

حسنا، مسابقة 0. كان المتوسط ​​على 58٪. كان منخفضا جدا، وحتى تتمكن جميع اللاعبين فعلت جدا، جيد جدا وفقا مع ذلك. 

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

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

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

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

الحضور: أين هي ساعات العمل؟ 

ANDI بنغ: الساعات المكتبية tonight-- أوه، سؤال جيد. أعتقد ساعات العمل الليلة هي في البط البري أو على العموم. إذا قمت بالتدقيق على الانترنت CS50 وتذهب إلى ساعات العمل، ينبغي أن يكون هناك جدول زمني يخبرك فيها كل منهم. 

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

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

OK، مداخن ذلك. الذي أحب سؤال حول جاك وملابسه في هذه المسابقة؟ لا أحد؟ حسنا هذا جيد. 

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

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

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

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

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

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

هكذا على سبيل المثال، وهذا جميل كان السؤال في مسابقة بك. أساسا كيف يمكننا دفع على الجزء العلوي من كومة. بسيطة جدا. إذا نظرتم اليها، سنقوم المشي من خلال ذلك. إذا (غير مسموع) size-- تذكر، كلما تريد الوصول إلى أي المعلمة داخل البنية، لديك اسم struct.parameter. 

في هذه الحالة، هو الصورة اسم كومة دينا. نريد الوصول إلى حجم من ذلك، لذلك نحن لا s.size. ذلك ما دام في حجم ليست يساوي القدرة أو دام كما انها أقل من القدرات، إما أن تعمل هنا. 

تريد الوصول إلى داخل من الكدسة، لذلك s.strings، وأنت تسير لوضع هذا الرقم الجديد ان كنت تريد إدراجه في هناك. دعنا نقول فقط أننا سوف تريد إدراج الباحث ن إلى المكدس، يمكننا أن نفعل s.strings، بين قوسين، s.size يساوي ن. لأن حجم أين نحن حاليا في كومة إذا نحن في طريقنا للدفع عليه، فإننا الوصول فقط أينما وحجم، و الامتلاء الحالي من المكدس، ونحن دفع الباحث ن على ذلك. وبعد ذلك نحن نريد أن نتأكد من أن نحن أيضا تزايد حجم ن، حتى نتمكن من تتبع قمنا وأضاف شيء إضافي إلى المكدس. الآن لدينا حجم أكبر. هل هذا هنا معنى ل الجميع، كيف منطقيا يعمل؟ كان نوع من سريع. الحضور: هل تذهب أكثر وs.stringss.strings [s.size] مرة أخرى؟ ANDI بنغ: بالتأكيد، لذلك ما تفعله s.size تعطي لنا حاليا؟ الجمهور: انها الحجم الحالي. ANDI بنغ: بالضبط، وبالتالي فإن المؤشر الحالي أن حجم لدينا هي في، ولذا فإننا نريد أن نضع العدد الصحيح جديدة أننا نريد أن تضاف إلى s.size. هل هذا منطقي؟ لأن s.strings، كل ذلك هو هو اسم مجموعة. كل ما هو غير الوصول إلى مجموعة داخل البنية لدينا، وهكذا إذا أردنا أن وضع ن إلى أن مؤشر، يمكننا فقط الوصول إليه s.size باستخدام الأقواس. رائع. 

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

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

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

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

ذلك ما نحب أن نطلق على هذا وdequeueing وenqueueing. إذا كنا نريد أن أضيف شيئا إلى قائمة الانتظار لدينا، وإدراج بقائمة الانتظار. إذا كنا نريد أن dequeue، أو اتخاذ شيئا بعيدا، ونحن dequeue. 

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

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

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

الحضور: (غير مسموع) ANDI بنغ: بالضبط، كنت ترغب في إضافة ذلك اعتمادا على هل مكتوب. إما هذا هو فارغ أو التي هي فارغة. لذلك تريد إضافته على الأرجح هنا لأنه إذا كان حجم is-- إذا كانت هذه كلها كاملة، وتريد لإضافتها هنا، أليس كذلك؟ 

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

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

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

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

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

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

حتى في هذا المثال، مؤشر من هو رئيس 1، أليس كذلك؟ مؤشر حجم 0، 1، 2، 3، 4. حتى نتمكن من القيام 1 و 4 معامل بواسطة قدراتنا الذي هو 5. ماذا يعني أن تعطي لنا؟ ما هو الفهرس الذي يخرج من هذا؟ 

الجمهور: 0. 

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

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

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

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

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

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

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

الحضور: لأنهم متصلا كل شيء، ولكنك لا تعرف تماما أين [غير مسموع]. 

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

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

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

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

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

الحضور: (غير مسموع) 

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

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

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

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

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

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

الحضور: إنها ديناميكية، ذلك أنه من الأسهل to-- 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

OK، لذلك ستكون متاحة هنا. يا رفاق نلقي نظرة بعد القسم. سيكون هناك. 

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

الجمهور: أنه لا يزال تكون عملية مماثلة من مثل تعيين المؤشر و ثم تعيين هذا المؤشر، ولكن سيكون لدينا لتحديد مكان هناك. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

وحتى هنا، إذا أردنا لتخزين الكلمات الإنجليزية، نحن يمكن أن يحتمل فقط، وأنا لا أعرف، وتحويل جميع الأحرف الأولى إلى نوع من رقم. وهكذا، على سبيل المثال، إذا أردت A ليكون مرادفا apple-- أو مع مؤشر 0، و B ليكون مرادفا 1، فإننا يمكن أن يكون 26 إدخالات التي يمكن تخزين فقط كل الحروف الأبجدية التي سنبدأ بها. وبعد ذلك يمكن أن يكون التفاح في الرقم القياسي ل0. فإننا يمكن أن يكون الموز في الرقم القياسي ل 1، والشمام في الرقم القياسي ل2، و هكذا. وبالتالي إذا أردت أن بحث بلدي تجزئة الجدول والوصول التفاح، أنا أعرف يبدأ التفاح مع وA، وأنا أعرف بالضبط أنه يجب أن يكون وتجزئة الجدول في الفهرس 0 ل وظيفة تعيينها مسبقا. 

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

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

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

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

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

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

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

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

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

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

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

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

إذا أردت أن insert-- ما ل الفاكهة التي تبدأ، وأنا لا أعرف، B، ما عدا التوت والموز. 

الحضور: بلاك بيري. 

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

الحضور: (غير مسموع) 

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

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

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

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

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

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

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

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

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

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

جدول تجزئة يشبه الجدول. شجرة تبدو تماما مثل شجرة. كل ما هو غير منفصلة طريقة لتنظيم العقد اعتمادا على ما هي احتياجاتك. 

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

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

حتى هنا، إذا أنا ذاهب للبحث عن قيمة 66، ويمكن أن تبدأ في 55. انها 66 أكبر من 55؟ نعم انها هي، لذلك أنا أعلم أنني المصحف بحث ط ن المؤشر الأيمن من هذه الشجرة. أذهب إلى 77. OK، هو أقل من 66 أو أكبر من 77؟ كان أقل مما كان، حتى تعرف، يا، فلا بد أن يكون عقدة نقاط. 

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

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

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

الحضور: أنت تريد أن تبدو الحق وتبدو اليسار وانظر [غير مسموع] أكبر عدد. 

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

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

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

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

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

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

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

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

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

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

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

وhere-- أوه، القادم رسالة في (غير مسموع) هو A. لذلك نحن ننظر في ذلك مجموعة. نجد قيمة الثامنة، وبعد ذلك ننظر لنرى، أوه، مهلا، هو أن كلمة واحدة، هو B-A كلمة؟ وهي ليست كلمة. لقد وصلنا إلى مواصلة البحث. 

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

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

OK، بارد. حتى B-A-T، وبعد ذلك وأنت تسير للبحث. في المرة القادمة التي تريد الذهاب أن ترى، يا، يا، هذا صحيح، وبالتالي أعرف أن هذا يجب أن يكون كلمة واحدة. 

نفس الشيء لحديقة الحيوان. حتى هنا في شيء الآن، إذا كنا يريد للبحث عن حديقة الحيوان، في الوقت الراهن، حاليا حديقة الحيوان ليست كلمة في قاموسنا لأنه، كما يا رفاق يمكن أن نرى، في المقام الأول أن لدينا منطقية العودة الحقيقية هي في نهاية التكبير. لدينا Z-O-O-M. 

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

الحضور: (غير مسموع) 

ANDI بنغ: بالضبط، ونحن نريد أن نتأكد من أن هذا هنا، أن قيمة منطقية هي التحقق من أن هذا صحيح. Z-O-O، ثم نحن في طريقنا للتحقق من ذلك، حتى نعرف بالضبط، مهلا، حديقة الحيوان هي كلمة. انا ذاهب لنقول لل كمبيوتر انها كلمة حتى أنه عندما يتحقق الكمبيوتر، فهو يعرف ان حديقة الحيوان هي كلمة. 

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

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

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

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

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

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

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

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

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

وحتى الكتل الثلاث البرامج التي سنعطيك ودعا dictionary.c، dictionary.h، وspeller.c. وهكذا كل dictionary.c يفعله هو ما يطلب منك تنفيذ. أنه يحمل الكلمات. هو توضيح الشيكات لهم، وذلك بالتأكد من يتم إدخال أن كل شيء بشكل صحيح. 

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

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

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

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

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

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

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

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

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

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

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

الحضور: هل يمكننا أن نكتفي باستخدام (غير مسموع)؟ 

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

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

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

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

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

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