JASON هيرشهورن: مرحبا الجميع إلى الفصل السابع. نحن في الأسبوع سبعة من الدورة. ويوم الخميس المقبل هو عيد جميع القديسين لذلك أنا لابسة مثل اليقطين. لم أتمكن من الانحناء ووضع على حذائي، ولهذا السبب أنا مجرد ارتداء الجوارب. أنا أيضا لا يرتدي أي شيء تحت هذا، ولذا فإنني لا يمكن خلعه إذا كان تشتيت لك. أعتذر مقدما لذلك. أنت لا تحتاج إلى تخيل ما يحدث. ارتديته الملاكمين. لذلك كل شيء جيد. لدي قصة طويلة حول لماذا أنا يرتدي زي القرع، ولكن انا ذاهب الى حفظ ذلك في وقت لاحق في هذا القسم لأنني لا أريد أن تبدأ. لدينا الكثير من الأمور المثيرة ليذهب أكثر من هذا الاسبوع. معظمهم تتصل مباشرة الى هذا مجموعة مشكلة الأسبوع، أخطاء إملائية. ونحن في طريقنا إلى أن تسير على ربط القوائم والجداول التجزئة عن القسم بأكمله. أنا وضعت هذه القائمة في كل أسبوع، وقائمة الموارد بالنسبة لك لمساعدتك في المواد على هذا الحال. إذا في حيرة أو إذا تبحث عن بعض مزيد من المعلومات، تحقق من واحدة من هذه الموارد. مرة أخرى، هو pset6 أخطاء إملائية، pset هذا الأسبوع. وتشجع أيضا لك، وأنا نشجعك، لاستخدام بعض الدول الاخرى الموارد خصيصا لهذا pset. على وجه الخصوص، وثلاثة عندي المدرجة على الشاشة - جدب، والتي كنا على دراية وتم استخدام لبعض الوقت الآن، هو ستكون مفيدة للغاية هذا الأسبوع. لذلك أنا وضعت ذلك هنا. ولكن كلما كنت تعمل مع C، يجب عليك دائما أن تستخدم لجدب تصحيح البرامج. هذا الأسبوع أيضا valgrind. لا أحد يعرف ما يفعل valgrind؟ الحضور: ويتحقق من وجود تسرب الذاكرة؟ JASON هيرشهورن: Valgrind الشيكات لتسرب الذاكرة. حتى إذا كنت شيئا في حياتك malloc البرنامج، كنت طالبا للذاكرة. في نهاية البرنامج، لديك لكتابة الحرة على كل شيء قمت malloced لإعطاء الذاكرة مرة أخرى. إذا كنت لا أكتب مجانا في نهاية و ويأتي البرنامج إلى استنتاج، سيكون كل شيء تلقائيا سيتم اطلاق سراحهم. وعن برامج صغيرة، انها ليس كبيرا الى اتفاق. ولكن إذا كنت تكتب لتشغيل أطول برنامج لا استقال، بالضرورة، في بضع دقائق أو بضع ثوان، ثم تسرب الذاكرة يمكن أن تصبح صفقة ضخمة. وذلك لpset6، والتوقع هو أن سيكون لديك صفر تسرب الذاكرة مع البرنامج. للتحقق من وجود تسرب الذاكرة، تشغيل valgrind وسأعطيك بعض لطيفة الانتاج مما يتيح لك معرفة ما إذا كان أو ليس كل شيء كان مجانيا. سنقوم في وقت لاحق مع ممارسة اليوم، ونأمل. أخيرا، الأمر فرق. استخدمته شيء مشابه له في pset5 مع أداة خاطفة. يسمح لك أن ننظر في الداخل. أنت تستخدم أيضا فرق، أيضا، في مشكلة تعيين المواصفات. ولكن في السماح لك ل مقارنة ملفين. هل يمكن المقارنة بين ملف الصورة النقطية و معلومات رؤوس حلا الموظفين و الحل في pset5 إذا اخترت لاستخدامه. وسوف تسمح لك لفرق تفعل ذلك، كذلك. يمكنك مقارنة الإجابة الصحيحة ل مشكلة هذا الأسبوع لتعيين إجابتك ومعرفة ما اذا كان يصطف أو راجع حيث الأخطاء. حتى تلك هي ثلاث أدوات الجيدة التي يجب عليك استخدام لهذا الأسبوع، و بالتأكيد تحقق برنامجك مع هذه الأدوات الثلاث قبل ان يتحول فيه. مرة أخرى، كما ذكرت كل أسبوع، إذا كان لديك أي ردود فعل بالنسبة لي - على حد سواء إيجابية وبناءة - لا تتردد في التوجه الى الموقع في الجزء السفلي من هذه الشريحة والمدخلات هناك. أنا حقا نقدر أي وجميع ردود الفعل. وإذا كنت تعطيني أشياء محددة يمكنني القيام به لتحسين أو أنني بلاء حسنا ان كنت تريد مني أن تواصل، أنا أعتبر أن لقلب و محاولة من الصعب حقا للاستماع لملاحظاتك. لا أستطيع أن أعدكم بأنني ذاهب الى القيام به كل شيء، رغم ذلك، مثل ارتداء اليقطين زي كل أسبوع. لذلك نحن ذاهبون لقضاء الجزء الأكبر من القسم، وكما ذكرت، نتحدث عن القوائم المرتبطة والجداول التجزئة، والتي وسوف تكون قابلة للتطبيق مباشرة إلى مشكلة تعيين هذا الاسبوع. القوائم المرتبطة سنذهب أكثر نسبيا بسرعة لأننا قضيت عادلة قليلا من الوقت في الذهاب أكثر من ذلك في القسم. ولذا فإننا سوف تحصل مباشرة الى الترميز لمشاكل القوائم المرتبطة. ثم في نهاية سنتحدث عن تجزئة الجداول وكيفية تطبيقها لهذا تعيين المشكلة الأسبوع. كنت قد رأيت هذا الرمز من قبل. هذا هو البنية، وأنها تحدد ما يسمى عقدة جديدة. وداخل عقدة هناك عدد صحيح الحق هنا وهناك هو مؤشر ل عقدة أخرى. شاهدنا هذا من قبل. وقد تم هذا الخروج ل بضعة أسابيع حتى الآن. فهو يجمع بين المؤشرات التي كنا العمل مع، والبنيات، والتي تسمح لنا الجمع بين مختلفين الأشياء إلى نوع بيانات واحد. هناك الكثير يجري على الشاشة. ولكن كل ذلك يجب أن يكون نسبيا دراية لك. في السطر الأول، ونحن تعلن عقدة جديدة. ثم داخل هذه عقدة جديدة، أنا وضعت العدد الصحيح في تلك العقدة إلى واحد. نرى على السطر التالي أفعله ل printf الأمر، ولكني جرايد الأمر printf لأن حقا جزء مهم من هذا الخط هنا - new_node.n. ماذا يعني النقطة؟ الجمهور: الذهاب إلى عقدة و تقدير قيمة ن لذلك. JASON هيرشهورن: هذا صحيح تماما. نقطة يعني الوصول إلى جزء ن من هذه العقدة الجديدة. هذا السطر التالي يفعل ماذا؟ مايكل. الجمهور: انه يخلق عقدة أخرى التي من شأنها أن تشير إلى عقدة جديدة. JASON هيرشهورن: لذلك لا إنشاء عقدة جديدة. أنه يخلق ما؟ الجمهور: مؤشر. JASON هيرشهورن: مؤشر إلى عقدة، كما يتبين من هذه العقدة * هنا. لذلك يخلق مؤشر إلى العقدة. والعقدة التي يتم عليها لافتا ل، مايكل؟ الجمهور: عقدة الجديد؟ JASON هيرشهورن: عقدة جديدة. وانها لافتا هناك لأننا نظرا لأنها عنوان عقدة جديدة. والآن في هذا الخط نرى طريقتين مختلفتين ل معربا عن الشيء نفسه. وكنت أرغب في توضيح مدى هذه شيئين هي نفسها. في السطر الأول، ونحن إلغاء مرجعية المؤشر. لذلك نذهب إلى العقدة. وهذا ما يعني هذا النجم. شاهدنا ذلك من قبل مع مؤشرات. تذهب إلى تلك العقدة. هذا هو بين قوسين. ومن ثم الوصول عبر المشغل نقطة العنصر ن من تلك العقدة. بحيث انه أخذ جملة رأينا الحق هنا والآن استخدامه مع مؤشر. بطبيعة الحال، فإنه يحصل نوع من مشغول في حالة كنت تكتب تلك قوسين - هذا النجم وتلك النقطة. يحصل مشغول قليلا. لذلك لدينا بعض السكر النحوية. وهذا الخط هنا - ptr_node-> ن. أن يفعل الشيء نفسه بالضبط. حتى تلك سطرين من التعليمات البرمجية هي وسوف نفعل ما يعادل نفس الشيء بالضبط. ولكن أردت أن أشير من قبل تلك نذهب إلى أبعد من ذلك لفهم حقا أن هذا الشيء هنا هو مجرد السكر النحوية ليعتبر إلغاء مرجعية المؤشر ومن ثم الذهاب الى ن جزءا من تلك البنية. أي أسئلة حول هذه الشريحة؟ موافق. لذلك نحن في طريقنا للذهاب من خلال زوجين العمليات التي يمكنك القيام به على القوائم المرتبطة. قائمة مرتبطة، أذكر، هو عبارة عن سلسلة من العقد التي تشير إلى بعضها البعض. ونبدأ عموما مع مؤشر دعا رئيس، وعموما، يشير إلى أول شيء في القائمة. هكذا السطر الأول هنا، ونحن لدينا L الأصلية الأولى. بحيث شيء يمكن ان يخطر لك - وهذا نص هنا يمكن ان يخطر لك كما مجرد مؤشر قمنا المخزنة أن النقاط في مكان ما إلى العنصر الأول. وفي هذه القائمة مرتبطة لدينا أربعة العقد. كل عقدة هو مربع كبير. مربع أكبر داخل كبيرة المربع هو الجزء صحيحا. ثم لدينا جزء المؤشر. لم يتم رسمها هذه الصناديق ل مقياس لكيفية كبيرة هي عدد صحيح في بايت؟ كيف كبيرة الآن؟ أربعة. وكيف كبيرة هو مؤشر؟ أربعة. ذلك حقا، وإذا كان لنا أن رسم هذا على نطاق مربعي سيكون بنفس الحجم. في هذه الحالة، نريد أن إدراج شيء في القائمة المرتبطة. حتى تتمكن من رؤية أسفل هنا نحن إدراج خمسة ونحن من خلال اجتياز القائمة المرتبطة، تجد فيها خمسة يذهب، ثم أدخله. دعونا كسر ذلك وتذهب أكثر قليلا ببطء. انا ذاهب للإشارة إلى المجلس. لذلك لدينا عقدة لدينا الخمس التي انشأناها في mallocs. لماذا الجميع يضحك؟ مجرد مزاح. موافق. لذلك قمنا malloced الخمسة. قمنا بإنشاء هذه العقدة في مكان آخر. لدينا على استعداد للذهاب. نبدأ في الجزء الأمامي من لدينا قائمة مع اثنين. ونحن نريد أن إدراج بطريقة فرزها. حتى إذا كنا نرى اثنين، ونحن نريد ان نضع في خمسة، ماذا نفعل عندما نرى شيء أقل من لنا؟ ماذا؟ نحن نريد لإدراج خمسة في هذا قائمة مرتبطة، وابقائها فرزها. ونحن نرى عدد اثنين. فماذا نفعل؟ ماركوس؟ الحضور: دعوة المؤشر إلى العقدة المقبل. JASON هيرشهورن: ولماذا تفعل نذهب إلى المرحلة التالية؟ الحضور: لأنه هو عقدة التالي في القائمة. ونحن نعلم فقط أن موقع آخر. JASON هيرشهورن: وخمس أكبر من اثنين، على وجه الخصوص. لأننا نريد أن نحافظ عليها فرزها. حتى خمسة أكبر من اثنين. حتى ننتقل إلى المرحلة التالية. والآن نصل إلى أربعة. وماذا يحدث عندما نصل إلى أربعة؟ خمسة هو أكبر من أربعة. لذلك نحن الاستمرار. ونحن الآن في ستة. وماذا نرى في ستة؟ نعم، كارلوس؟ الحضور: ستة أكبر من خمسة. JASON هيرشهورن: ستة هي أكبر من خمسة. ذلك أن المكان الذي نريد لإدراج خمسة. ومع ذلك، نضع في اعتبارنا أنه إذا كنا لا تملك إلا مؤشر واحد هنا - هذا هو مؤشر اضافي لدينا هذا تعبر من خلال القائمة. ونحن لافتا إلى ستة. فقدنا مسار ما ويأتي قبل ستة. لذلك إذا كنا نريد لادخال شيء في هذه القائمة ابقائها فرزها، ونحن ربما تحتاج كم من المؤشرات؟ الحضور: اثنان. JASON هيرشورن: اثنان. واحد لتتبع التيار واحد واحد لتتبع سابقتها. هذا هو قائمة مرتبطة منفردة فقط. يذهب اتجاه واحد فقط. لو كان لدينا قائمة مرتبطة على نحو مضاعف، حيث كل شيء كان يشير إلى شيء بعد ذلك، والشيء قبل ذلك، ثم ونحن لن تحتاج للقيام بذلك. ولكن في هذه الحالة نحن لا نريد لانقاص تتبع ما سبقونا في حالة نحن بحاجة إلى إدراج خمسة في مكان ما في الوسط. ويقول كنا إدراج تسعة. ما الذي سيحدث عندما وصلنا إلى ثمانية؟ الحضور: كنت قد ل الحصول على تلك النقطة فارغة. بدلا من الاضطرار نقطة فارغة كنت قد لإضافة عنصر ومن ثم يكون ذلك إشارة إلى تسعة. JASON هيرشورن: بالضبط. حتى نحصل على ثمانية. نصل إلى نهاية القائمة ل هذا يشير إلى قيمة خالية. والآن، بدلا من الاضطرار أنها تشير إلى لاغية لدينا ذلك إشارة إلى عقدة جديدة لدينا. وضعنا المؤشر في عقدة لدينا الجديد إلى قيمة خالية. هل لدى أي شخص أي أسئلة حول إدراج؟ ماذا لو كنت لا تبالي الحفاظ على قائمة تم فرزها؟ الجمهور: عصا في بداية أو نهاية. JASON هيرشورن: عصا في بداية أو نهاية. أي واحد يجب أن نفعل؟ بوبي؟ لماذا نهاية؟ الحضور: لأن بداية يتم تعبئة بالفعل. JASON هيرشورن: OK. يتم تعبئة بالفعل البداية. الذي يريد أن يجادل ضد بوبي. ماركوس. الحضور: حسنا ربما كنت ترغب في التمسك بها في البداية ل إلا إذا وضعته في نهاية كنت قد ل تعبر القائمة بأكملها. JASON هيرشورن: بالضبط. حتى إذا نحن نفكر في وقت التشغيل، و وقت التشغيل من إدراج في نهاية سيكون ن، وحجم هذا. ما هو يا وقت كبير من إدراج في البداية؟ وقت ثابت. لذلك إذا كنت لا تبالي حفظ شيء فرزها، أفضل بكثير لمجرد إدراج في بداية هذه القائمة. والذي يمكن القيام به في وقت ثابت. موافق. العملية التالية التي يتم العثور عليها، والتي غيرها - لقد فسر البحث. ولكن ونحن في طريقنا لننظر من خلال قائمة مرتبطة لبعض وجوه. شهدت يا رفاق رمز ل بحث من قبل في المحاضرة. ولكننا نوع من فعل ذلك فقط مع إدراج، أو إدراج ما لا يقل عن شيء فرزها. أنت تنظر من خلال، والذهاب عقدة عقدة من قبل، حتى تجد الرقم الذي كنت تبحث عنه. ماذا يحدث إذا وصلت في نهاية القائمة؟ يقول أنا أبحث عن تسع وأنا تصل إلى نهاية القائمة. ماذا نفعل؟ الجمهور: عودة كاذبة؟ JASON هيرشورن: عودة كاذبة. لم نجد ذلك. إذا وصلت إلى نهاية القائمة و لأنك لم تجد الرقم الذي كنت تبحث عنه، انها ليست في وجود. أي أسئلة حول العثور عليها؟ إذا كانت هذه القائمة المفروزة، ما من شأنه تكون مختلفة عن البحث لدينا؟ نعم. الحضور: وسوف تجد القيمة الأولى هذا هو أكبر من واحد كنت تبحث عن و ثم عودة كاذبة. JASON هيرشورن: بالضبط. حتى لو كان على قائمة فرزها، إذا نصل إلى شيء أن يكون أكبر من ما نحن نبحث عن، ونحن لسنا في حاجة ل الاستمرار إلى نهاية القائمة. يمكننا في هذه النقطة عودة كاذبة لأننا لن تجد ذلك. والآن، تحدثنا على سؤال حول حفظ القوائم المرتبطة فرزها، ابقائها لم يتم فرزها. وهذا ما سوف يكون شيئا كنت ربما ستكون لدينا للتفكير عندما وضعت الترميز المشكلة خمس إذا كنت اختيار جدول تجزئة مع منفصلة تسلسل النهج، الذي سنتحدث عنها لاحقا. ولكن هل هو يستحق كل هذا العناء للحفاظ على قائمة فرزها ومن ثم تكون قادرة على ربما أسرع عمليات البحث؟ أم أنه من الأفضل لادخال بسرعة شيء ما في وقت التشغيل المستمر ولكن بعد ذلك يكون أطول تبحث؟ وهذا هو المقايضة هناك حق لك أن الحصول على لتقرر ما هو أكثر ملاءمة لمشكلة محددة. وهناك ليست بالضرورة واحدة الجواب الصحيح تماما. ولكن من المؤكد أن قرار تحصل لجعل، وربما جيدة للدفاع أنه في، ويقول، تعليقا أو اثنين لماذا اخترت واحد على الآخر. أخيرا، وحذف. رأيناه حذف. انها تشبه الى البحث. نحن نبحث عن العنصر. يقول نحاول حذف ستة. لذلك نجد ستة الحق هنا. الشيء الذي علينا أن نتأكد من أننا القيام به هو أن كل ما يشير إلى ستة - كما نرى في الخطوة اثنين من أسفل هنا - أيا كان لافتا إلى ستة احتياجات ل تخطي ستة من الآن وإلى أن تتغير كل ما يشير إلى ستة. نحن لا نريد من أي وقت مضى إلى اليتيم بقية لدينا قائمة من قبل نسيان لتعيين هذا المؤشر السابق. ثم في بعض الأحيان، وهذا يتوقف على البرنامج، أنها سوف فقط حذف هذه العقدة تماما. أحيانا سترغب في العودة القيمة التي هو في هذه العقدة. ذلك أن كيفية حذف الأشغال. أي أسئلة حول حذف؟ الجمهور: حتى إذا كنت تريد الذهاب لحذف ذلك، وكنت مجرد استخدام مجانا ل يفترض malloced كان ذلك؟ JASON هيرشورن: إذا كنت ترغب في تحرير شيء وهذا صحيح تماما، وكنت malloced ذلك. يقول أردنا أن العودة هذه القيمة. ونحن قد العودة ستة وخالية ثم هذه العقدة والكلمة الحرة على ذلك. أو ربما كنا الكلمة الحرة الأولى ثم العودة الست. موافق. لذلك دعونا ننتقل إلى ممارسة الترميز. ونحن في طريقنا إلى رمز ثلاث وظائف. ويسمى أول واحد insert_node. بحيث يكون لديك التعليمات البرمجية التي لي بالبريد الإلكتروني لك، و إذا كنت أشاهد هذا في وقت لاحق يمكنك الوصول إلى التعليمات البرمجية في linked.c على موقع CS50. ولكن في linked.c، وهناك بعض كود هيكل عظمي وهذا بالفعل قد كتب لك. ثم هناك وظائف زوجين تحتاج إلى كتابة. أولا نحن في طريقنا لل إرسال insert_node. وماذا يفعل insert_node غير إدراج عدد صحيح. وكنت إعطاء عدد صحيح في قائمة مرتبطة. وعلى وجه الخصوص، تحتاج للحفاظ على قائمة تم فرزها من الأصغر إلى الأكبر. أيضا، كنت لا تريد ل إدراج أي التكرارات. أخيرا، وكما ترون insert_node إرجاع منطقي. لذلك كنت من المفترض أن تسمح للمستخدم معرفة إذا كان إدراج أو لا ناجحة من خلال العودة صحيحة أو خاطئة. في نهاية هذا البرنامج - وهذه المرحلة لا تحتاج ما يدعو للقلق تحرير أي شيء. لذلك كل ما نقوم به هو اتخاذ عدد صحيح وإدراجه في قائمة. هذا هو ما أنا أسأل لك أن تفعل الآن. مرة أخرى، في linked.c، والتي جميعا، هو رمز الهيكل العظمي. وسترى نحو القاع العينة وظيفة الإعلان. ولكن، قبل الخوض في ذلك الترميز في C، أشجع بشدة لك أن تذهب من خلال الخطوات كنا ممارسة كل أسبوع. انتقلنا بالفعل من خلال صورة من هذا. لذلك ينبغي أن يكون لديك بعض الفهم كيف يعمل هذا. ولكن أود أن أشجعكم على إرسال بعض شبة الكود قبل الغوص فيها. ونحن في طريقنا للذهاب أكثر شبة الكود كمجموعة. ثم مرة واحدة كنت قد كتبت لكم شبة الكود، ومرة ​​واحدة لدينا كتب لدينا شبة الكود كمجموعة، يمكنك الخوض في الترميز في C. كما رؤساء حتى وظيفة insert_node وربما كان أصعب من ثلاثة ونحن في طريقنا لكتابة لأنني وأضاف بعض القيود الإضافية ل البرمجة الخاصة بك، ولا سيما أن كنت لن إدراج أي التكرارات وأن القائمة ينبغي أن تظل فرزها. لذلك هذا هو برنامج غير تافهة التي تحتاج إلى رمز. ولماذا لا تأخذ 06:55 دقائق فقط للحصول على العمل على شبة الكود والشفرة. ثم سنبدأ الذهاب كمجموعة. مرة أخرى، إذا كان لديك أي أسئلة فقط ارفع يدك وسآتي حولها. . نحن أيضا عموما هذه - أو أنا لا أقول لك صراحة يمكن أن تعمل مع الناس. ولكن من الواضح، وأنا أشجعكم جدا إذا كان لديك أسئلة، أن تطلب من الجار يجلس إلى جانبك أو حتى العمل مع شخص ما آخر إذا كنت ترغب في ذلك. لم يكن هذا ليكون الفرد النشاط صامتة. دعونا نبدأ مع كتابة بعض شبة الكود على متن الطائرة. الذين يمكن أن تعطيني السطر الأول من شبة الكود لهذا البرنامج؟ لهذه المهمة، بدلا - insert_node. ألدين؟ الحضور: لذلك كان أول شيء فعلته إنشاء مؤشر جديد إلى عقدة وأنا تهيئته لافتا إلى نفس الشيء الذي يشير إلى القائمة. JASON هيرشورن: OK. لذلك كنت تقوم بإنشاء مؤشر جديد إلى القائمة، وليس إلى العقدة. الحضور: الحق. نعم. JASON هيرشورن: OK. ثم ماذا نريد أن نفعل؟ ما بعد ذلك؟ ماذا عن العقدة؟ ليس لدينا عقدة. لدينا فقط قيمة. إذا كنا نريد لإدراج عقدة، فماذا نحن تحتاج إلى القيام به أولا قبل أن نتمكن حتى التفكير في إدراج ذلك؟ الحضور: أوه، آسف. نحن بحاجة إلى malloc مساحة للعقدة. JASON هيرشورن: ممتاز. دعونا نفعل - موافق. لا يمكن أن تصل إلى أن ارتفاع. موافق. ونحن في طريقنا للذهاب إلى أسفل، ومن ثم نستخدمه عمودين. لا أستطيع أن أذهب ذلك - موافق. إنشاء عقدة جديدة. يمكنك إنشاء مؤشر آخر إلى القائمة أو يمكنك فقط استخدام قائمة كما هو قائم. لا تحتاج حقا أن تفعل ذلك. لذلك نحن إنشاء عقدة جديدة. عظيم. هذا ما نقوم به أولا. ما هي الخطوة التالية؟ الحضور: انتظر. يجب علينا إنشاء عقدة جديدة الآن أو يجب علينا الانتظار للتأكد من أن ليس هناك نسخ من العقدة على القائمة قبل نخلق ذلك؟ JASON هيرشورن: سؤال جيد. دعونا نرى أن في وقت لاحق لأن معظم الوقت سنكون خلق عقدة جديدة. ولذا فإننا سوف تبقي ذلك هنا. ولكن هذا سؤال جيد. إذا كنا إنشائه ونجد نسخة مكررة، ما ينبغي نفعل قبل أن تعود؟ الجمهور: تحرير ذلك. JASON هيرشورن: نعم. ربما تحريرها. موافق. ماذا نفعل بعد أن إنشاء عقدة جديدة؟ آني؟ الحضور: وضعنا رقم في العقدة؟ JASON هيرشورن: بالضبط. وضعنا رقم - نحن malloc الفضاء. أنا ذاهب إلى ترك ذلك جميع كسطر واحد. ولكن كنت على حق. نحن malloc الفضاء، ومن ثم وضعنا فيها عدد نحن حتى يمكن تعيين المؤشر جزء منه إلى قيمة خالية. هذا صحيح تماما. ثم ماذا عن بعد ذلك؟ وضعنا هذه الصورة على متن الطائرة. فماذا نفعل؟ الجمهور: نذهب من خلال القائمة. JASON هيرشورن: اذهب من خلال القائمة. موافق. وماذا علينا التحقق لفي كل عقدة. كورت، ماذا علينا التحقق لفي كل عقدة؟ الحضور: انظر ما إذا كانت قيمة ن من هذه العقدة هي أكبر من قيمة ن من عقدة لدينا. JASON هيرشورن: OK. انا ذاهب الى القيام به - نعم، حسنا. لذلك فمن ن - انا ذاهب الى القول ما اذا كان قيمة أكبر من هذه العقدة، ثم ماذا نفعل؟ الحضور: حسنا، ثم نحن إدراج الشيء الصحيح قبل ذلك. JASON هيرشورن: OK. حتى لو كان أكبر من ذلك، ثم نريد أن إدراج. لكننا نريد أن أدخله الحق قبل لأننا أيضا في حاجة إلى أن يكون تتبع، بعد ذلك، ما كان من قبل. حتى قبل إدراج. لذلك ربما فاتنا شيء في وقت سابق يوم. أننا ربما تحتاج إلى حفظ تتبع ما يجري. لكننا سنصل إلى هناك. فما قيمة أقل من؟ كورت، ماذا نفعل إذا القيمة هي أقل من؟ الحضور: ثم يمكنك فقط الاستمرار إلا إذا كان واحد آخر. JASON هيرشورن: أحب ذلك. لذلك يذهب إلى العقدة المقبل. إلا إذا كان آخر واحد - نحن ربما التحقق من أن في حيث شرط. ولكن نعم، العقدة المقبل. وهذا ما يحصل منخفضة جدا، ولذا فإننا سوف تتحرك فوق هنا. ولكن إذا - يمكن الجميع رؤية هذا؟ إذا نحن على قدم المساواة ماذا نفعل؟ إذا كانت قيمة نحاول إدراج تساوي قيمة هذه العقدة؟ نعم؟ الحضور: [غير مسموع]. JASON هيرشورن: نعم. ونظرا لهذا - ماركوس هو الصحيح. كان بإمكاننا القيام به ربما شيء مختلف. ولكن نظرا لأننا قد خلقها، وهنا نحن يجب أن يكون حرا وثم العودة. يا صبي. هو أن أفضل؟ كيف هذا؟ موافق. حرة ثم ماذا نحن العودة، [غير مسموع]؟ موافق. نحن في عداد المفقودين أي شيء؟ فأين نحن تتبع العقدة قبل؟ الجمهور: أعتقد أنه سيذهب بعد إنشاء عقدة جديدة. JASON هيرشورن: OK. حتى في بداية سنقوم على الأرجح - نعم، يمكننا خلق مؤشر إلى الجديد العقدة، مثل مؤشر العقدة السابقة و مؤشر العقدة الحالية. لذلك دعونا إدراج ذلك هنا. إنشاء الحالية والسابقة مؤشرات إلى العقد. ولكن عندما لا علينا أن نعدل تلك المؤشرات؟ حيث نفعل ذلك في التعليمات البرمجية؟ جيف؟ الحضور: - الظروف القيمة؟ JASON هيرشورن: أي واحد على وجه الخصوص؟ الجمهور: أنا الخلط فقط. إذا كانت القيمة أكبر من هذه العقدة، لا يعني ذلك أن تريد أن تذهب إلى العقدة المقبل؟ JASON هيرشهورن: حتى إذا قيمة لدينا هو أكبر من قيمة هذه العقدة. الجمهور: نعم، ثم كنت تريد أن تذهب أبعد من أسفل الخط، أليس كذلك؟ JASON هيرشهورن: الحق. لذلك نحن لا أدخله هنا. إذا كانت القيمة أقل من هذه العقدة، ثم نذهب إلى العقدة التالية - أو بعد ذلك نحن إدراج من قبل. الحضور: الانتظار، وهو هذا العقدة والتي هي القيمة؟ JASON هيرشهورن: سؤال جيد. القيمة في هذا التعريف وظيفة هو ما نقوم معين. لذلك القيمة هي عدد أننا معين. لذلك إذا كانت القيمة أقل من ذلك عقدة، ونحن بحاجة الى وقت لإدراج. إذا كانت القيمة أكبر من هذه العقدة، نذهب إلى العقدة المقبل. ونعود إلى السؤال الأصلي، رغم ذلك، حيث - الحضور: إذا القيمة أكبر من هذه العقدة. JASON هيرشهورن: وهكذا ماذا نفعل هنا؟ الحلو. وهذا هو الصحيح. أنا فقط أريد أن أكتب مؤشرات التحديث. ولكن نعم، مع واحد الحالية كنت تحديثه ل نشير إلى المرحلة التالية. أي شيء آخر نفتقده؟ لذلك أنا ذاهب لكتابة هذا رمز في gedit. وحين أفعل هذا، هل يمكن أن يكون أكثر زوجين دقيقة للعمل على الترميز هذا في C. وذلك لدي إدخال شبة الكود. ملاحظة سريعة قبل أن نبدأ. نحن قد لا تكون قادرة على تماما الانتهاء من هذا في جميع ثلاثة من هذه الوظائف. هناك حلول صحيحة لها بأنني سوف البريد الإلكتروني إلى يا رفاق بعد القسم، وأنه سوف توضع على CS50.net. لذلك أنا لا نشجعك على يذهب للبحث في أقسام. أنا أشجعكم على محاولة هذه على الخاص تملك، ومن ثم استخدام هذه الممارسة مشاكل للتحقق إجاباتك. وقد تم تصميم جميع هذه لعن كثب تتصل ونتمسك بما ما عليك القيام به على مجموعة المشكلة. لذلك أنا لا نشجعك على ممارسة هذه لوحدك ومن ثم استخدام رمز ل التحقق من إجاباتك. لأنني لا أريد أن ننتقل إلى بعثرة الجداول في مرحلة ما من هذا الباب. ولذا فإننا قد لا تحصل من خلال كل ذلك. ولكن سنفعل ما في وسعنا من ذلك بكثير الآن. موافق. دعونا نبدأ. الأصم، كيف يمكننا إنشاء عقدة جديدة؟ الحضور: أنت البنية *. JASON هيرشهورن: لذلك نحن يكون هذا الأمر هنا. أوه، آسف. كنت قائلا البنية *. الحضور: وبعد ذلك [؟ نوع؟] عقدة عقدة أو ج. JASON هيرشهورن: OK. أنا ذاهب إلى نسميها new_node حتى نتمكن من البقاء متسقة. الحضور: وأنت تريد تعيين هذا لرئاسة، العقدة الأولى. JASON هيرشهورن: OK. وحتى الآن هذا التأشير ل- وحتى هذا لم يخلق عقدة جديدة حتى الآن. هذا هو مجرد لافتا إلى العقدة الأولى في القائمة. كيف يمكنني إنشاء عقدة جديدة؟ إذا كنت بحاجة إلى مساحة لإنشاء عقدة جديدة. Malloc. وكيف كبيرة؟ الجمهور: حجم البنية. JASON هيرشهورن: و حجم البنية. وما يسمى البنية؟ الجمهور: عقدة؟ JASON هيرشهورن: عقدة. حتى malloc (sizeof (عقدة))؛ يعطينا الفضاء. وهذا الخط هو - شيء واحد غير صحيح على هذا الخط. هو new_node مؤشر إلى البنية؟ هذا هو اسم عام. ما هو عليه - عقدة، بالضبط. انها عقدة *. وماذا نفعل الحق بعد نحن malloc شيء، اسان؟ ما هو أول شيء نقوم به؟ ماذا لو كان لا يعمل؟ الحضور: أوه، معرفة ما اذا كان يشير إلى العقدة؟ JASON هيرشهورن: بالضبط. لذلك إذا كنت new_node يساوي يساوي فارغة، ماذا نفعل؟ هذا بإرجاع منطقي، هذه الوظيفة. بالضبط. تبدو جيدة. لإضافة أي شيء هناك؟ سنقوم بإضافة أشياء في نهاية المطاف. ولكن الذي يبدو حتى الآن جيدة. إنشاء مؤشرات الحالية والسابقة. مايكل، كيف أفعل ذلك؟ الحضور: سيكون لديك للقيام عقدة *. وكنت قد لجعل واحدة لا لnew_node ولكن بالنسبة لل العقد لدينا بالفعل. JASON هيرشهورن: OK. وبالتالي فإن العقدة الحالية نحن على. سأتصل أن بالعملة. حسنا. قررنا أننا نريد الحفاظ على اثنين لأننا بحاجة إلى معرفة ما قبل ذلك. ماذا يحصلون على تهيئة ل؟ الحضور: قيمتها في قائمتنا. JASON هيرشهورن: فما هو أول شيء على قائمتنا؟ أو كيف لنا أن نعرف حيث ابتداء من قائمتنا هو؟ الحضور: أليس مرت في وظيفة؟ JASON هيرشهورن: الحق. صدر في الحق هنا. حتى إذا تم تمريرها إلى الدالة، و بدء من القائمة، ما يجب علينا تعيين الحالي يساوي؟ الحضور: قائمة. JASON هيرشهورن: قائمة. هذا صحيح تماما. والآن لديها عنوان بداية قائمتنا. وماذا عن السابق؟ الحضور: قائمة ناقص واحد؟ JASON هيرشهورن: هناك لا شيء أمامها. ذلك ما يمكن أن نقوم به للدلالة على شيء؟ الجمهور: خالية. JASON هيرشهورن: نعم. هذا يبدو وكأنه فكرة جيدة. الكمال. شكرا لك. تذهب من خلال القائمة. قسنطينة، متى نحن ذاهبون من خلال الذهاب الى القائمة؟ الحضور: حتى نصل فارغة. JASON هيرشهورن: OK. إذا كان الأمر كذلك، في حين، للحلقة. ما الذي نقوم به؟ الحضور: ربما لحلقة؟ JASON هيرشهورن: دعونا نفعل حلقة for. موافق. الحضور: ونحن نقول ل- حتى المؤشر الحالي لا تساوي فارغة. JASON هيرشهورن: حتى إذا كنا نعرف حالة، وكيف يمكن أن نكتب حلقة القائم قبالة هذا الشرط. أي نوع من حلقة يجب أن نستخدم؟ الحضور: على الرغم من. JASON هيرشهورن: نعم. أن أكثر منطقية تستند الخروج من ما قلته. إذا كنا نريد فقط أن تذهب إلى أنه سيكون علينا مجرد معرفة هذا الشيء، من شأنه أن يجعل بمعنى أن تفعل حلقة while. حين يفعل الحالية لاغية وليس على قدم المساواة، إذا كانت القيمة أقل من هذه العقدة. اكشار، أعطني هذا الخط. الحضور: إذا الحالي> ن ن أقل من القيمة. أو عكس ذلك. التبديل أن قوس. JASON هيرشهورن: آسف. الحضور: تغيير قوس. JASON هيرشهورن: حتى لو كان أكبر من القيمة. لأن هذا الخلط مع التعليق الوارد أعلاه، وانا ذاهب للقيام بذلك. ولكن نعم. إذا قيمة لدينا هو أقل من هذا عقدة، ماذا نفعل؟ اه. لدي هنا. إدراج من قبل. موافق. كيف نفعل ذلك؟ الحضور: هل ما زال لي؟ JASON هيرشهورن: نعم. الحضور: أنت - new_node-> المقبل. JASON هيرشهورن: إذن ما هو أن الذهاب إلى تساوي؟ الجمهور: انها سوف الحالية على قدم المساواة. JASON هيرشهورن: بالضبط. وهكذا والآخر - ماذا نحتاج لتحديث؟ الجمهور: معرفة ما اذا كان يساوي الماضية فارغة. JASON هيرشهورن: إذا السابق - حتى إذا المعاينة يساوي فارغة. الحضور: وهذا يعني انه سيكون ليصبح الرأس. JASON هيرشهورن: وهذا يعني أصبح من الرأس. حتى ذلك الحين ماذا نفعل؟ الحضور: نحن نفعل الرأس يساوي new_node. JASON هيرشهورن: رئيس يساوي new_node. ولماذا يتوجه هنا، وليس قائمة؟ الحضور: لأن الرأس هو عالمي متغير، الذي هو مكان الانطلاق. JASON هيرشهورن: الحلو. موافق. و- الحضور: ثم كنت آخر الصفحة السابقة> يساوي المقبل new_node. ومن ثم يمكنك العودة الحقيقية. JASON هيرشهورن: أين وضعنا نهاية new_node؟ الجمهور: أود - أنا وضعت ذلك في البداية. JASON هيرشهورن: فما الخط؟ الحضور: بعد بيان إذا التحقق إذا هو معروف. JASON هيرشهورن: الحق هنا؟ الحضور: كنت تفعل new_node-> ن يساوي قيمة. JASON هيرشهورن: يبدو جيدا. ربما كان من المنطقي - لم نفعل ذلك بحاجة إلى معرفة ما نحن في قائمة لأننا نتعامل فقط مع قائمة واحدة. لذلك أفضل تعريف الدالة ل هذا هو فقط للتخلص من هذه تماما وإدراج فقط قيمة في الرأس. نحن لا تحتاج حتى إلى معرفة ما نحن فيه. قائمة ولكنني لن يبقيه في الوقت الراهن و ثم تغييره عند تحديث الشرائح والتعليمات البرمجية. بحيث تبدو جيدة في الوقت الراهن. إذا كانت القيمة - الذين يمكن أن تفعل هذا الخط؟ إذا - ماذا نفعل هنا، ونوح. الحضور: إذا القيمة أكبر من بالعملة-> ن - JASON هيرشهورن: كيف نذهب إلى العقدة المقبل؟ الجمهور: بالعملة-> n هو يساوي new_node. JASON هيرشهورن: n غير ذلك أي جزء من البنية؟ عدد صحيح. وnew_node هو مؤشر إلى عقدة. وذلك ما ينبغي أن جزءا من بالعملة نقوم بتحديث؟ إن لم يكن ن، ثم ما هو الجزء الآخر؟ نوح، ما هو الجزء الآخر. الحضور: أوه، المقبل. JASON هيرشهورن: بعد ذلك، بالضبط. بالضبط. القادم هو حق واحد. وماذا نحتاج لتحديث ونوح؟ الجمهور: إن المؤشرات. JASON هيرشهورن: إذن قمنا بتحديث الحالية. الجمهور: السابق> المقبل. JASON هيرشهورن: نعم. موافق، ونحن سوف نتوقف. الذين يمكن أن تساعدنا هنا؟ مانو، ماذا علينا أن نفعل؟ الحضور: لقد حصلت على تعيين فإنه يساوي بالعملة-> المقبل. ولكن القيام بذلك قبل السطر السابق. JASON هيرشهورن: OK. أي شيء آخر؟ اكشار. الجمهور: لا أعتقد أن كنت تهدف إلى تغيير بالعملة-> المقبل. أعتقد أنك تعني أن تفعل يساوي بالعملة بالعملة-> التالي للذهاب إلى العقدة المقبل. JASON هيرشهورن: آسف لذلك، وأين؟ على ما الخط؟ هذا الخط؟ الجمهور: نعم. جعل بالعملة يساوي بالعملة-> المقبل. JASON هيرشهورن: هذا هو الصحيح لأن الحالي هو مؤشر إلى العقدة. ونريد أن نشير إلى التالي عقدة ما يحصل حاليا وأشار إلى. بالعملة نفسها لديها المقبل. ولكن إذا كان لنا أن تحديث curr.next، ونحن سيتم تحديث هذه المذكرة الفعلية نفسه، وليس فيها هذا المؤشر كان لافتا. ماذا عن هذا الخط، وإن كان. افي؟ الجمهور: السابق> يساوي بالعملة المقبل. JASON هيرشهورن: وهكذا مرة أخرى، إذا المعاينة هو مؤشر إلى عقدة، المعاينة-> هو القادم المؤشر الفعلي في العقدة. ولذلك فإن هذا سيكون بتحديث المؤشر في عقدة لبالعملة. نحن لا نريد لتحديث مؤشر في عقدة. نحن نريد لتحديث السابقة. فكيف نفعل ذلك؟ الجمهور: أن يكون مجرد والصفحة السابقة. JASON هيرشهورن: الحق. السابق هو مؤشر إلى عقدة. نحن الآن تغييره ل مؤشر جديد لعقدة. موافق دعونا ننتقل إلى أسفل. أخيرا، وهذا الشرط الأخير. جيف، ماذا نفعل هنا؟ الحضور: إذا القيمة يساوي بالعملة-> ن. JASON هيرشهورن: آسف. يا إلهي. ماذا؟ القيمة بالعملة ==> ن. ماذا نفعل؟ الحضور: كنت تحرير new_node لدينا، ثم كنت عودة كاذبة. JASON هيرشهورن: هذا هو ما كتبناه حتى الآن. هل لدى أي شخص أي شيء لإضافة قبل أن نجعل؟ موافق. دعونا نحاول ذلك. التحكم قد تصل إلى نهاية من وظيفة غير باطلة. وافي، ما الذي يحدث؟ الحضور: هل من المفترض أن تضع عودة صحيح خارج حلقة في حين؟ JASON هيرشهورن: أنا لا أعرف. هل تريد مني أن؟ الحضور: لا بأس. لا. JASON هيرشهورن: اكشار؟ الجمهور: أعتقد أنك تعني ل وضعت عودة كاذبة في نهاية الحلقة حين. JASON هيرشهورن: فأين هل تريد أن تذهب؟ الحضور: مثل حلقة خارج الوقت. لذلك إذا كنت الخروج من حلقة في حين أن الوسائل بعد أن كنت قد وصلت إلى نهاية و حدث شيء. JASON هيرشهورن: OK. لذلك ماذا نفعل هنا؟ الحضور: يمكنك العودة كاذبة هناك أيضا. JASON هيرشهورن: أوه، ونحن تفعل ذلك في كل الأماكن؟ الجمهور: نعم. JASON هيرشهورن: OK. يجب ان نذهب؟ يا إلهي. أنا آسف. اعتذر عن الشاشة. انها نوع من ينقط بها علينا. حتى تختار خيارا. الصفر، في الرمز، إنهاء البرنامج. واحد يدرج شيئا. دعونا إدراج ثلاثة. وكان إدراج لم تكن ناجحة. انا ذاهب للطباعة. ليس لدي أي شيء. موافق. ربما كان ذلك مجرد صدفة. إدراج واحد. لم يكن ناجحا. موافق. دعونا من خلال تشغيل GDB بسرعة حقا لمعرفة ما يجري. تذكر جدب. / اسم الخاص برنامج يحصل لنا في GDB. هو أن الكثير للتعامل مع؟ وامض؟ ربما. تغمض عينيك واتخاذ بعض العميقة الأنفاس إذا كنت تتعب للنظر في ذلك. أنا في GDB. ما هو أول شيء أفعله في GDB؟ لقد وصلنا إلى معرفة ما يحدث هنا. دعونا نرى. لدينا ست دقائق على الرقم ما يجري. كسر الرئيسي. ثم ماذا أفعل؟ كارلوس؟ تشغيل. موافق. دعونا اختيار الخيار. وماذا تفعل N؟ المقبل. نعم. الحضور: لم أذكر لكم - لم تقولون بأن رئيس، كان عليه تهيئة لاغية في البداية. ولكن اعتقدت أنك قلت أنه موافق. JASON هيرشهورن: دعونا نذهب - دعونا ننظر في GDB، ومن ثم فإننا سوف نعود. ولكن هذا يبدو وكأنه لديك بالفعل بعض الأفكار حول ما يجري. لذلك نحن نريد لادخال شيء. موافق. قمنا إدراج. الرجاء إدخال عدد صحيح. سنقوم بإدراج ثلاثة. ثم أنا على هذا الخط. كيف أذهب بدء التصحيح إدراج يعرف وظيفة؟ يا إلهي. وهذا هو الكثير. هو أن ينقط بها الكثير؟ الحضور: أوه، أنها توفيت. JASON هيرشهورن: أنا فقط سحبت من ذلك. موافق. الحضور: ربما يكون ل الطرف الآخر من السلك. JASON هيرشهورن: نجاح باهر. وبالتالي فإن خلاصة القول - ماذا قلت؟ الحضور: قلت بسخرية التقنية الصعوبات في هذه الفئة. JASON هيرشهورن: أعرف. ولو كان لي السيطرة على هذا الجزء. [غير مسموع] أن يبدو كبيرا. لماذا لا نبدأ في التفكير في اللاعبين ما كان يمكن أن يأتيه الباطل، وسوف نكون مرة أخرى في 90 ثانية. Avica، وانا ذاهب لأطلب منكم كيفية التوجه insert_node داخل لتصحيح ذلك. لذلك هذا هو المكان الذي توقفت الماضي. كيف أذهب داخل insert_node، Avica، لدراسة ما يحدث؟ ما الأمر GDB؟ سوف كسر لا تأخذني في الداخل. لا أعرف ماركيز؟ الحضور: ماذا؟ JASON هيرشهورن: ما الأمر GDB أنا استخدم للذهاب داخل هذه الوظيفة؟ الجمهور: الخطوة؟ JASON هيرشهورن: الخطوة عبر S. وهذا يأخذ مني في الداخل. موافق. New_node mallocing بعض المساحة. يبدو أن جميع مثل الذهاب لها. دعونا دراسة new_node. انها حصلت على بعض عنوان الذاكرة. دعونا تحقق - هذا هو كل شيء الصحيح. لذلك كل شيء هنا يبدو أن أن تعمل بشكل صحيح. الحضور: ما هو الفرق بين P والعرض؟ JASON هيرشهورن: P تقف على الطباعة. وهكذا كنت طالبا ما هو الفرق بين هذا وهذا؟ في هذه الحالة، لا شيء. ولكن عموما هناك بعض الاختلافات. ويجب أن ننظر في دليل GDB. ولكن في هذه الحالة، لا شيء. ونحن نميل إلى استخدام الطباعة، وذلك لأن نحن لسنا بحاجة لتفعل أكثر بكثير من طباعة قيمة واحدة. موافق. لذلك نحن على خط 80 من التعليمات البرمجية لدينا، وضع العقدة * بالعملة يساوي القائمة. دعونا طباعة بالعملة. فإنه يساوي القائمة. الحلو. الانتظار. فإنه يساوي شيئا. لا يبدو من الصواب. هناك نذهب. انها لأنه في GDB، والحق، إذا انها خط كنت عليه لم تنفذ حتى الآن. لذلك تحتاج إلى كتابة الواقع بجانب تنفيذ السطر قبل رؤية نتائجها. لذلك نحن هنا. نحن فقط تنفيذ هذا الخط، السابقة يساوي فارغة. ذلك مرة أخرى، وإذا كنا طباعة السابقة نحن لن نرى أي شيء غريب. ولكن إذا كنا فعلا تنفيذ ذلك الخط، ثم سنرى ان هذا الخط يعمل. لذلك لدينا بالعملة. تلك هي سواء كانت جيدة. أليس كذلك؟ الآن نحن على هذا الخط هنا. بينما بالعملة لا فارغة متساوية. حسنا، ماذا يفعل بالعملة متساوية؟ رأينا فقط أنه يمثل فارغة. نحن المطبوعة بها. أنا طباعته مرة أخرى. ذلك هو أنه في حين أن حلقة ذاهب لتنفيذ؟ الحضور: رقم JASON هيرشهورن: لذلك عندما كتبت أن الخط، ترى نحن قفز على طول الطريق إلى أسفل، والعودة كاذبة. ثم نحن في طريقنا للعودة كاذبة ونعود إلى برنامجنا و طباعة في نهاية المطاف، كما رأينا، وكان إدراج لم تكن ناجحة. لذلك، أي شخص يحصل على أي أفكار بشأن ما يتعين علينا القيام به لإصلاح هذا؟ انا ذاهب الى الانتظار حتى أرى زوجين من الأيدي ترتفع. لم نكن تنفيذ هذا. نضع في اعتبارنا، وكان هذا أول شيء كنا نفعله. أنا لن تفعل زوجين. انا ذاهب الى القيام ببعض. لأن الزوجين يعني اثنين. سأنتظر لأكثر من عقدين. في الإدراج الأول، بالعملة، افتراضيا يساوي فارغة. وهذه الحلقة ينفذ فقط إذا ليس بالعملة فارغة. فكيف يمكنني الحصول على حول هذا؟ أرى أن هناك ثلاثة اليدين. انا انتظر أكثر من ثلاث. ماركوس، ما رأيك؟ الحضور: حسنا، إذا كنت في حاجة إليها ل تنفيذ أكثر من مرة واحدة، أنت فقط تغييره إلى حلقة افعل حين. JASON هيرشهورن: OK. والتي تساهم في حل مشكلة لدينا، على الرغم من؟ الحضور: في هذه الحالة لا بسبب حقيقة أن القائمة فارغة. لذلك فإنك ربما تحتاج فقط إلى إضافة بيان أنه إذا كان مخارج حلقة ثم عليك أن تكون في نهاية القائمة، وهي النقطة التي يمكن فقط أدخله. JASON هيرشهورن: أحب ذلك. أن من المنطقي. إذا يخرج من حلقة - لأنه سوف عودة كاذبة هنا. إذا كان الأمر كذلك مخارج حلقة، ثم نحن في في نهاية القائمة، أو ربما بدء من قائمة إذا كان هناك شيء في ، والذي هو نفس النهاية. وحتى الآن نحن نريد أن إدراج شيء هنا. لذلك كيف يمكن أن ننظر رمز، ماركوس؟ الحضور: إذا كنت بالفعل حصلت على عقدة malloced، هل يمكن أن نقول فقط new_node-> يساوي القادم باطل لأن فإنه يجب أن يكون في نهاية المطاف. أو new_node-> يساوي المقبل فارغة. JASON هيرشهورن: OK. آسف. New_node-> يساوي المقبل فارغة لأننا في نهاية المطاف. أن لا يضع فيه. كيف يمكننا وضعه في القائمة؟ الحق. هذا مجرد تعيينها يساوي. كيف لا ونحن في الواقع وضعه في القائمة؟ ما يشير إلى نهاية القائمة؟ الحضور: رئيس. JASON هيرشهورن: عذرا؟ الحضور: رئيس يتم الإشارة إلى نهاية القائمة. JASON هيرشهورن: إذا كان هناك أي شيء في قائمة رئيس يشير إلى نهاية القائمة. بحيث سوف تعمل ل الإدراج الأول. ماذا عن إذا كان هناك زوجين الأشياء في القائمة؟ من نحن لا ترغب في تعيين يتوجه يساوي new_node. ماذا نريد أن نفعل هناك؟ نعم؟ السابقة على الأرجح. وسوف تعمل؟ نذكر بأن السابق هو مجرد مؤشر إلى العقدة. والسابق هو متغير محلي. حتى هذا الخط سيتم تعيين متغير محلي، السابقة، أي ما يعادل أو مشيرا إلى هذه العقدة الجديدة. هذا لن وضعها في الواقع في قائمتنا، وإن كان. كيف يمكننا وضعه في قائمتنا؟ Akchar؟ الجمهور: أعتقد أنك القيام الحالي> المقبل. JASON هيرشهورن: OK. بالعملة-> المقبل. ذلك مرة أخرى، والسبب الوحيد اننا أسفل هنا هو، ماذا يفعل الحالية على قدم المساواة؟ الجمهور: يساوي فارغة. JASON هيرشهورن: وماذا في ذلك يحدث اذا لم نفعل خالية> في المرة القادمة؟ ماذا نحن ذاهبون للحصول على؟ وسوف نحصل على خطأ تجزئة. الحضور: هل يساوي بالعملة فارغة. JASON هيرشهورن: هذا هو نفس الشيء كما السابق، على الرغم من أنه لا يوجد متغير محلي نقوم بوضع يساوي هذا عقدة جديدة. دعونا نعود إلى الصورة لدينا ادخال شيء. ويقول نحن إدراج في نهاية من القائمة، لذلك هنا. لدينا مؤشر الحالي هذا مشيرا إلى فارغة والنقطة السابقة وهذا ما يشير إلى 8. لذلك ماذا نحن بحاجة إلى تحديث، آفي؟ الحضور: السابق> في المرة القادمة؟ JASON هيرشهورن: السابق> هو القادم ما نحن نريد لتحديث لأن ذلك سوف أدخله في الواقع نهاية القائمة. لا يزال لدينا علة واحدة، على الرغم من أننا ذاهبون لتشغيل في. ما هو هذا الخطأ؟ نعم؟ الجمهور: انها سوف تعود كاذبة في هذه الحالة؟ JASON هيرشهورن: أوه، هو و سوف تعود كاذبة. ولكن هناك علة أخرى. ولذا فإننا سوف تحتاج لوضع في العودة الحقيقية. الحضور: هل لا تزال متساوية السابقة فارغة في أعلى القائمة؟ JASON هيرشهورن: لا يزال السابقة لذلك يساوي فارغة في البداية. فكيف يمكننا الحصول على أكثر من ذلك؟ نعم؟ الجمهور: أعتقد أنك يمكن أن تفعل الاختيار قبل حلقة في حين لمعرفة ما اذا كان قائمة فارغة. JASON هيرشهورن: OK. لذلك دعونا نذهب هنا. القيام فحص. إذا - الجمهور: حتى إذا كان الرأس يساوي يساوي فارغة. JASON هيرشهورن: إذا الرأس يساوي يساوي فارغة - التي سوف تقول لنا ما اذا كان قائمة فارغة. الحضور: وبعد ذلك كنت قيام رئيس يساوي الجديدة. JASON هيرشهورن: رئيس يساوي new_node؟ وماذا نحتاج أن تفعل؟ الحضور: وبعد ذلك العودة الحقيقية. JASON هيرشهورن: ليس تماما. نفتقده خطوة واحدة. الجمهور: New_node المقبل يجب أن نشير إلى قيمة خالية. JASON هيرشهورن: بالضبط، الدن. وبعد ذلك يمكننا العودة الحقيقية. موافق. لكنه ما زال فكرة جيدة أن تفعل أشياء في نهاية القائمة، أليس كذلك؟ حسنا. ما زلنا قد تحصل في الواقع إلى نهاية القائمة. ذلك هو هذا الرمز يرام إذا نحن في نهاية القائمة، وهناك بعض الأشياء في القائمة؟ أليس كذلك؟ لأننا لا تزال لديها فكرة ماركوس. ونحن قد إنهاء هذه الحلقة ل نحن في نهاية القائمة. لذلك فإننا لا تزال تريد هذه رمز إلى هنا؟ الجمهور: نعم. JASON هيرشهورن: نعم. وماذا نحتاج لتغيير هذا؟ صحيح. يفعل ذلك الصوت جيدة على الجميع حتى الآن؟ أي شخص لديك أي - افي، هل لديك شيء للإضافة؟ الحضور: رقم JASON هيرشهورن: OK. لذلك نحن حققنا بضعة التغييرات. لقد حققنا هذا الاختيار قبل أن ذهب في لائحة فارغة. ولذا فإننا قد اتخذت الرعاية من قائمة فارغة. ونحن هنا اعتنى إدراج شيء في نهاية القائمة. لذلك يبدو مثل هذا أخذ حلقة في حين الرعاية من الأشياء في بين، في مكان ما في قائمة إذا كان هناك أشياء في القائمة. موافق. دعونا تشغيل هذا البرنامج مرة أخرى. لم يكن ناجحا. الحضور: أنت لم يتمكنوا من ذلك. JASON هيرشهورن: أوه، أنا لم يتمكنوا من ذلك. نقطة جيدة، مايكل. دعونا نضيف جعل المرتبطة. خط 87 هناك خطأ. خط 87. الدن، وكان هذا الخط الذي قدمتموه لي. ما هو الخطأ؟ الحضور: يجب ان يكون لاغية. JASON هيرشهورن: ممتاز. صحيح تماما. يجب أن تكون فارغة. دعونا جعل مرة أخرى. ترجمة. موافق. دعونا إدراج ثلاثة. وكان إدراج ناجحة. دعونا طباعته. أوه، إلا إذا كان نتمكن من التحقق. لكننا لم تفعل طباعة وظيفة حتى الآن. دعونا إدخال شيء آخر. ما ينبغي أن ندخل؟ الحضور: سبعة. JASON هيرشهورن: سبعة؟ الجمهور: نعم. JASON هيرشهورن: لدينا خطأ ثوانى. حتى وصلنا واحد، ولكن من الواضح أننا لا يمكن الحصول على اثنين. فمن 05:07. حتى نتمكن من تصحيح هذا لمدة ثلاث دقائق. ولكن أنا ذاهب إلى ترك لنا هنا وننتقل إلى تجزئة الجداول. ولكن مرة أخرى، والأجوبة عن هذا الرمز وسوف ارسل لك في بعض الشيء. نحن قريبون جدا من ذلك. أنا أشجع بشدة لك لمعرفة ما يحدث هنا وإصلاحه. ولذا فإنني سوف ارسل لكم هذا الكود كما كذلك بالإضافة إلى حل - ربما الحل في وقت لاحق. أول هذه التعليمات البرمجية. الشيء الآخر أريد القيام به قبل أن النهاية هو أننا لم سراح أي شيء. لذلك أريد أن تظهر لك ما valgrind يبدو. إذا كنا تشغيل الحدود valgrind على برنامجنا،. / مرتبط. مرة أخرى، وفقا لهذه الشريحة، ونحن يجب تشغيل valgrind مع بعض نوع من الخيار، في هذه الحالة - تسرب الاختيار = الكامل. لذلك دعونا إرسال valgrind - تسرب الاختيار = الكامل. لذلك هذا سيتم تشغيل valgrind على برنامجنا. والآن البرنامج يعمل فعلا. لذلك نحن ذاهبون لتشغيله تماما مثل من قبل، وضع شيء فيها. انا ذاهب الى وضعها في ثلاثة. يعمل. أنا لن أحاول أن أضع في شيء آخر لأننا في طريقنا لل الحصول على كاذبة ثوانى في هذه الحالة. لذلك أنا ذاهب لمجرد الإقلاع عن التدخين. والآن ترى أسفل هنا تسرب وملخص الكومة. هذه هي الأشياء الجيدة التي تريد إنهاء إجراءات المغادرة. وبالتالي فإن ملخص كومة - على حد قولها، في استخدام في الخروج - ثمانية بايت في كتلة واحدة. أن كتلة واحدة هي عقدة نحن malloced. مايكل، وقال لك قبل عقدة ثمانية لدغات لأنه يحتوي على عدد صحيح والمؤشر. ذلك أن لدينا عقدة. وبعد ذلك يقول كنا malloc سبع مرات، ونحن الافراج شيء ست مرات. لكننا أبدا يسمى الحرة، لذلك ليس لدي فكرة هذا ما يتحدث عنه. ولكن يكفي أن نقول أنه عندما الخاص تشغيل البرنامج، يتم استدعاء malloc في بعض الأماكن الأخرى التي نحن لا داعي للقلق حول. لذلك ربما كان يسمى malloc في بعض الأماكن. نحن لا داعي للقلق حيث. ولكن هذا هو حقا لنا. هذا الخط الأول هو لنا. تركنا تلك الكتلة. ويمكنك أن ترى أن هنا في الملخص تسرب. لا تزال قابلة للوصول - ثمانية بايت في كتلة واحدة. وهذا يعني أن الذاكرة - لقد تسربت تلك الذاكرة. خسر بالتأكيد - وفقدت شيئا من أجل الخير. عموما، فلن ترى أي شيء هناك. لا تزال قابلة للوصول بشكل عام حيث سترى الأشياء، حيث سترغب لننظر لنرى ما يجب عليك كود وقد حررت ولكن كنت قد نسيت لتحرير. ثم إذا كان هذا ليس هو الحال، إذا فعلنا كل شيء مجانا، يمكننا التحقق من ذلك. دعونا فقط تشغيل البرنامج عدم وضع أي شيء في. سترى أسفل هنا في استخدامها في الخروج - صفر بايت في كتل الصفر. وهذا يعني أننا قد لا يبقى شيء عندما خرجت هذا البرنامج. حتى قبل ان يتحول في pset6، تشغيل valgrind وتأكد من أنك لم يكن لديك أي ذاكرة تسرب في البرنامج. إذا كان لديك أي أسئلة مع valgrind، لا تتردد في التواصل. ولكن هذا هو كيفية استخدامه. بسيط جدا - معرفة ما اذا كنت يكون قيد الاستخدام في الخروج - أي بايت في أي كتل. لذلك كنا نعمل على إدراج عقدة. كان لي اثنين من وظائف أخرى هنا - طباعة العقد والعقد مجانية. مرة أخرى، وهذه هي الوظائف التي هي ستكون جيدة بالنسبة لك لممارسة لأنها سوف تساعدك ليس فقط مع هذه التمارين عينة ولكن أيضا على المشكلة المحددة. أنها خريطة على نحو وثيق جدا لأشياء وأنت تسير لدينا للقيام في تعيين المشكلة. ولكن أنا لا أريد أن تأكد من ونحن على اتصال على كل شيء. والجداول التجزئة هي أيضا حاسمة ل ما نقوم به في هذا القسم الأسبوع - أو في المجموعة المشكلة. لذلك نحن ذاهبون لإنهاء القسم نتحدث عن الجداول التجزئة. إذا لاحظت أنني ارتكبت جدول التجزئة قليلا. ليس هذا ما كنا نتحدث حول، ولكن. نحن نتحدث عن مختلف نوع من الجداول التجزئة. وفي جوهره، جدول تجزئة لها لا شيء أكثر من مجموعة بالإضافة إلى وظيفة التجزئة. نحن ذاهبون الى الحديث قليلا فقط ل تأكد الجميع يفهم ما دالة تجزئة هو. وأنا أقول لك الآن أنه من لا شيء أكثر من شيئين - مجموعة ودالة تجزئة. وهنا الخطوات من خلال هذا الذي يعمل. هناك مجموعة لدينا. هناك وظيفة لدينا. على وجه الخصوص، بحاجة إلى وظائف التجزئة ل تفعل بضعة أشياء مع هذا. انا ذاهب الى الحديث على وجه التحديد حول تعيين هذه المشكلة. انه سيكون على الارجح ل تأخذ في سلسلة. وماذا تسير الأمور في العودة؟ ما هو نوع البيانات؟ ألدين؟ دالة تجزئة الخاصة بك العودة؟ عدد صحيح. لذلك هذا هو ما التجزئة يتكون جدول - جدول في شكل مجموعة وظيفة تجزئة. كيف يعمل؟ يعمل في ثلاث خطوات. اعطيناها مفتاح. في هذه الحالة، فإننا سوف تعطيه سلسلة. نسميه دالة تجزئة في خطوة واحدة على المفتاح ونحصل على القيمة. على وجه التحديد، ونحن سوف يقول نحصل على عدد صحيح. صحيح أن هناك محددة جدا حدود لما يمكن أن يكون صحيحا أن. في هذا المثال، لدينا مجموعة هي من الحجم الثلاثة. ذلك ما يمكن أن يكون أن أرقام عدد صحيح. ما هو نطاق القيم الصالحة ل أن عدد صحيح، ونوع الإرجاع من هذا تجزئة وظيفة؟ صفر، واحد واثنين. نقطة دالة البعثرة هو معرفة المكان في مجموعة حيث لدينا مفتاح هو ذاهب. هناك ثلاثة فقط ممكن الأماكن هنا - صفر، واحد، أو اثنين. حتى هذه الوظيفة أفضل العودة صفر، واحد، أو اثنين. بعض indice صالح في هذه المجموعة. ومن ثم تبعا للمكان فإنها ترجع، ترون هناك مجموعة مفتوحة قوس القيمة. حيث ان نضع المفتاح. لذلك نحن في رمي اليقطين، نخرج صفر. في مجموعة قوس 0، وضعنا اليقطين. نحن رمي في القطط، وحصلنا على أصل واحد. نضع القط في واحدة. نضع في العنكبوت. نخرج اثنين. نضع العنكبوت في مجموعة قوس اثنين. سيكون لطيفا إذا كان الأمر كذلك انها عملت من هذا القبيل. ولكن للأسف، كما سنرى، انها قليلا أكثر تعقيدا. قبل أن نصل إلى هناك، على أية أسئلة حول هذه الأساسية انشاء جدول التجزئة؟ هذا هو بالضبط صورة ما لفت على متن الطائرة. ولكن بما أننا ووجه ذلك على متن الطائرة، وأنا أنا لن أخوض في ذلك المزيد. مفاتيح أساسا، الصندوق الأسود السحر - أو في هذه الحالة، مربع البط البري - ل دالة تجزئة يضعهم في الدلاء. وفي هذا المثال نحن عدم وضع اسم. نحن نضع الهاتف المرتبطة عدد الاسم في دلو. ولكن هل يمكن بشكل جيد للغاية فقط وضع اسم في دلو. هذا هو مجرد صورة ما تعادلنا على متن الطائرة. لدينا المزالق المحتملة، وإن كان. وهناك نوعان من على وجه الخصوص الشرائح التي أريد أن يذهب أكثر. أول واحد هو حول دالة تجزئة. لذلك أنا طرح السؤال، ما يجعل وظيفة تجزئة جيدة؟ أعطي إجابتين. الأول هو أنه من القطعية. في سياق ظائف التجزئة، ماذا يعني هذا؟ نعم؟ الحضور: ويمكن العثور على الفهرس في وقت ثابت؟ JASON هيرشهورن: هذا ليس هو ما يعنيه. ولكن هذا تخمين جيد. أي شخص آخر لديهم تخمين لماذا يعني هذا؟ أن وظيفة تجزئة جيدة هي حتمية؟ آني؟ الحضور: هذا مفتاح لا يمكن إلا أن يتم تعيين إلى مكان واحد في جدول التجزئة. JASON هيرشهورن: هذا صحيح تماما. في كل مرة كنت وضعت في اليقطين، فإنها ترجع دائما صفر. إذا وضعت في اليقطين والتجزئة الخاصة بك الدالة بإرجاع صفر ولكن لديه احتمال عودته شيء أكبر آخر من الصفر - وربما لذلك فإنه يمكن العودة احدة أحيانا أو مرتين أخرى - ليست وظيفة تجزئة جيدة. أنت على حق تماما. يجب أن تعود وظيفة التجزئة الخاص بك نفس صحيحا بالضبط، في هذه الحالة، ل نفس السلسلة بالضبط. ربما تقوم بإرجاع عدد صحيح بالضبط نفس لنفس السلسلة بالضبط بغض النظر عن القيمة. ولكن في هذه الحالة فإنه لا يزال لأن الأمور القطعية متعددة يتم تعيينها على نفس القيمة. هذا شيء طيب. طالما ليس هناك سوى واحد الناتج عن مدخلات معينة. موافق. الشيء الثاني هو أنه يعود مؤشرات صالحة. أثرنا أنه في وقت سابق. هذه الوظيفة التجزئة - يا صبي - ينبغي دالة تجزئة العودة مؤشرات صالحة. لذلك أقول - دعونا نعود إلى هذا المثال. دالة تجزئة بلدي التهم تصل الحروف في الكلمة. هذا هو دالة تجزئة. ويعود ذلك صحيحا. حتى إذا كان لدي كلمة A، انها سوف تعود واحدة. وانه سيكون لوضع الحق هنا. ماذا لو أنني وضعت في كلمة الخفافيش؟ انها سوف تعود الثلاثة. أين تذهب الخفافيش؟ فإنه لا يصلح. لكنه يحتاج إلى الذهاب إلى مكان. هذا هو جدول التجزئة بلدي بعد كل شيء، و كل شيء يجب أن تذهب في مكان ما. فأين يجب ان تذهب الخفافيش؟ أي أفكار؟ التخمينات؟ التخمينات جيدة؟ الحضور: صفر. JASON هيرشهورن: لماذا الصفر؟ الحضور: لأن ثلاثة نمطية ثلاثة صفرا؟ JASON هيرشهورن: ثلاثة نمطية ثلاثة صفر. وهذا هو تخمين كبيرة، وهذا هو الصحيح. لذلك ينبغي في هذه الحالة ربما تذهب عند مستوى الصفر. لذلك وسيلة جيدة لضمان أن هذه التجزئة الدالة بإرجاع فقط مؤشرات صالحة و لمودولو ذلك حسب حجم الجدول. إذا كنت مودولو مهما كانت هذه العائدات من ثلاثة، وكنت دائما ما تحصل شيء بين صفر، واحد، واثنين. وإذا كان هذا دوما بإرجاع سبعة، و كنت دائما مودولو ثلاثة، وكنت دائما ما تحصل على نفس الشيء. حتى انها لا تزال القطعية إذا كنت مودولو. ولكن من شأنها أن تضمن أن ل لم تحصل على شيء - صناعة غير صالحة. عموما، يجب أن يحدث نمطية داخل دالة تجزئة الخاص بك. لذلك كنت لا داعي للقلق حول هذا الموضوع. يمكنك فقط ضمان هذا هو indice صالحة. أي أسئلة حول هذا شرك المحتملة؟ موافق. وهناك نذهب. شرك المحتملة المقبلة، و هذا هو واحد كبير. ماذا لو مفتاحين الخريطة إلى نفس القيمة؟ لذلك هناك طريقتان للتعامل مع هذا. ويسمى أول واحد خطية التحقيق، الذي أنا لن يذهب أكثر. ولكن يجب أن تكون على دراية بكيفية الذي يعمل وما هو ذلك. ثانية واحدة وانا ذاهب للذهاب أكثر لأن ذلك هو واحد أن العديد من والناس سوف الارجح في نهاية المطاف اتخاذ قرار لاستخدامها في مجموعة مشكلتهم. بطبيعة الحال، لم يكن لديك ل. ولكن بالنسبة للمجموعة مشكلة، كثير من الناس تميل إلى اختيار لإنشاء جدول تجزئة مع تسلسل منفصلة لتنفيذ قاموسهم. لذلك نحن في طريقنا للذهاب أكثر ما يعنيه لإنشاء جدول تجزئة مع تسلسل منفصلة. لذلك أنا وضعت في اليقطين. تقوم بإرجاع صفر. وأضع هنا اليقطين. ثم أضع في - ما هو آخر شيء هالوين تحت عنوان؟ الجمهور: كاندي. JASON هيرشهورن: حلوى! هذا هو واحد كبير. أضع في الحلوى، والحلوى أيضا يعطيني صفر. ماذا أفعل؟ أي أفكار؟ لأنك تعرف كل نوع من ما هو تسلسل منفصلة. لذلك أي أفكار ماذا تفعل؟ نعم. الحضور: وضع السلسلة فعلا في جدول التجزئة. JASON هيرشهورن: لذلك نحن ذاهبون ل رسم فكرة جيدة هنا. موافق. الجمهور: أن يكون لديه hashtable [غير مسموع] المؤشر الذي يشير إلى بداية القائمة. ومن ثم قد يكون اليقطين القيمة الأولى في تلك القائمة المرتبطة والحلوى تكون القيمة الثانية في تلك القائمة المرتبطة. JASON هيرشهورن: OK. ماركوس، التي كانت معلقة. انا ذاهب الى كسر ذلك. يقول ماركوس لا الكتابة اليقطين. من شأنها أن تكون سيئة. لا تضع الحلوى في مكان آخر. ونحن في طريقنا لوضعها سواء في صفر. ولكن ونحن في طريقنا للتعامل مع وضعها في الصفر بحلول إنشاء قائمة في صفر. ونحن في طريقنا لإنشاء قائمة كل ما تعيينه إلى الصفر. وأفضل وسيلة لخلق تعلمنا قائمة التي يمكن أن تنمو وتتقلص هو حيوي ليس ضمن مجموعة أخرى. حتى لا مجموعة متعددة الأبعاد. ولكن لخلق مجرد قائمة مرتبطة. وذلك ما اقترح - انا ذاهب الى الحصول على الجديدة - هو إنشاء صفيف مع مؤشرات، مجموعة من المؤشرات. موافق. أي فكرة أو التلميح ما نوع من هذه المؤشرات ينبغي أن يكون؟ ماركوس؟ الجمهور: مؤشرات ل- JASON هيرشهورن: لأنك وقال قائمة مرتبطة، لذلك - الجمهور: مؤشرات عقدة؟ JASON هيرشهورن: مؤشرات عقدة. إذا كانت الأمور في منطقتنا مرتبط القائمة هي العقد بعد ذلك وينبغي أن تكون مؤشرات العقدة. وماذا كانت تساوي في البداية؟ الجمهور: خالية. JASON هيرشهورن: خالية. ولذلك لا يوجد لدينا شيء فارغ. عوائد اليقطين الصفر. ماذا نفعل؟ المشي لي من خلال ذلك؟ في الواقع، وقدم ماركوس بالفعل لي. شخص آخر المشي لي من خلال ذلك. ما نقوم به عندما كنا - هذه تبدو مشابهة جدا ل ماذا كنا نفعل فقط. افي. الحضور: انا ذاهب الى اتخاذ تخمين. لذلك عندما تحصل الحلوى. JASON هيرشهورن: نعم. حسنا، وصلنا اليقطين. دعونا الحصول على أول واحد لدينا. وصلنا اليقطين. الحضور: OK. عوائد اليقطين الصفر. بحيث يمكنك وضعه في ذلك. أو في الواقع، يمكنك وضعه في القائمة المرتبطة. JASON هيرشهورن: كيف يمكننا وضعه في قائمة مرتبطة؟ الحضور: أوه، بناء الجملة الفعلية؟ JASON هيرشهورن: مجرد المشي - أقول أكثر من ذلك. ماذا نفعل؟ الحضور: أنت فقط ضع أنها العقدة الأولى. JASON هيرشهورن: OK. لذلك نحن لدينا عقدة، اليقطين. والآن كيف يمكنني إدراج ذلك؟ الحضور: يمكنك تعيين إلى المؤشر. JASON هيرشهورن: أي مؤشر؟ الجمهور: المؤشر عند مستوى الصفر. JASON هيرشهورن: فأين لا هذه النقطة؟ الحضور: لاغية الآن. JASON هيرشهورن: حسنا، انها لافتا إلى قيمة خالية. ولكن أنا أضع في اليقطين. فأين ينبغي أن نشير؟ الحضور: لاليقطين. JASON هيرشهورن: لاليقطين. بالضبط. ولذلك فإن هذا يشير إلى اليقطين. وأين هذا المؤشر في نقطة اليقطين؟ إلى الجمهور: خالية. JASON هيرشهورن: لاغية. بالضبط. لذلك نحن للتو بإدراجه شيء في القائمة المرتبطة. كتبنا فقط هذا الرمز للقيام بذلك. تقريبا ونحن تقريبا حصلت عليه تصدع تماما. ونحن الآن إدراج الحلوى. يذهب لدينا الحلوى أيضا إلى الصفر. لذلك ماذا نفعل مع الحلوى؟ الحضور: هذا يعتمد على ما إذا كان أو لا نحاول ترتيب هذا الامر. JASON هيرشهورن: هذا صحيح تماما. ذلك يعتمد على ما إذا كان أو لا نحاول ترتيب هذا الامر. دعونا نفترض أننا لسنا الذهاب لترتيب هذا الامر. الحضور: حسنا بعد ذلك، كما ناقشنا من قبل، هو أبسط هو فقط لوضعها الحق في بداية ذلك المؤشر من نقطة الصفر إلى الحلوى. JASON هيرشهورن: OK. على عقد. اسمحوا لي خلق الحلوى هنا. لذلك هذا المؤشر - الجمهور: نعم، ينبغي الآن مشيرا الى أن الحلوى. ثم يكون المؤشر من نقطة الحلوى لاليقطين. JASON هيرشهورن: أحب ذلك؟ ويقول وصلنا أخرى شيء لتعيين الصفر؟ الحضور: حسنا، أنت فقط تفعل الشيء نفسه؟ JASON هيرشهورن: هل نفس الشيء. حتى في هذه الحالة، إذا لم نفعل ذلك نريد أن نحافظ عليها فرزه يبدو بسيطا نوعا ما. نأخذ المؤشر في indice التي قدمها دالة البعثرة لدينا. لدينا هذه النقطة لدينا عقدة جديدة. ثم كل ما كان لافتا إليها سابقا - في هذه الحالة لاغية، في اليقطين الحالة الثانية - أنه مهما انها لافتا إلى سابقا، ونضيف إلى القادم من عقدة جديدة لدينا. نحن إدراج شيء في البداية. في الواقع هذا هو أبسط بكثير من محاولة للحفاظ على قائمة تم فرزها. ولكن مرة أخرى، سيكون البحث أكثر تعقيدا هنا. سيكون لدينا دائما للذهاب حتى النهاية. موافق. أي أسئلة حول تسلسل منفصلة؟ كيف يعمل؟ من فضلك اطلب منهم الآن. أريد حقا للتأكد من كل فهم هذا قبل أن يخرج. الحضور: لماذا كنت وضعت اليقطين والحلوى في نفس جزء من جدول التجزئة؟ JASON هيرشهورن: سؤال جيد. لماذا وضعنا لهم في نفس جزء من جدول التجزئة؟ حسنا، في هذه الحالة دالة البعثرة لدينا بإرجاع صفر لكلا منهم. لذلك هم بحاجة للذهاب في indice الصفر لأن هذا هو المكان الذي نحن ذاهبون ل تبدو بالنسبة لهم إذا كان لنا أي وقت مضى تريد البحث عنها. مرة أخرى، مع اتباع نهج خطي التحقيق ونحن لن نضع لهم على حد سواء عند مستوى الصفر. ولكن في نهج منفصلة السلسلة، ونحن في طريقنا لوضعها سواء في صفر ثم قم بإنشاء قائمة الخروج من نقطة الصفر. ونحن لا نريد أن الكتابة اليقطين ببساطة لأنه بسبب ذلك سنقوم نفترض أن اليقطين كان لم المدرجة. إذا كان لنا أن تبقي فقط شيء واحد في الموقع الذي سيكون سيئا. ثم لن يكون هناك أي فرصة منا من أي وقت مضى - إذا كان لدينا أي وقت مضى مكررة، ثم نحن لن يمحو فقط القيمة الأولية لدينا. ولهذا السبب نقوم به هذا النهج. أو هذا هو السبب في أننا اخترنا - ولكن مرة أخرى، ونحن اختار نهج تسلسل منفصلة، التي توجد عدة طرق أخرى يمكن للمرء أن يختار. لا أن أجيب على سؤالك؟ موافق. كارلوس. أن الخطية التحقيق تنطوي - إذا وجدنا حادث تصادم عند مستوى الصفر، ونحن ستبحث في بقعة المقبل لمعرفة ما إذا كان مفتوحا ووضعها هناك. ثم ننظر في هذه الرياضة القادمة و معرفة ما إذا كان الذي كان مفتوحا ووضعها هناك. لذلك نجد المتاحة المقبل بقعة مفتوحة وضعت تلك القبل هناك. أي أسئلة أخرى؟ نعم، آفي. الحضور: وكمتابعة لذلك، ماذا تقصد بقعة في المرة القادمة؟ في جدول تجزئة أو في قائمة مرتبطة. JASON هيرشهورن: لخطي البرمجة، لا القوائم المرتبطة. بقعة المقبل على جدول تجزئة. الحضور: OK. وبالتالي فإن جدول التجزئة سيكون تهيئة إلى حجم - مثل عدد من السلاسل التي تم إدخالها؟ JASON هيرشهورن: أنت سوف تريد أن تكون كبيرة حقا. نعم. هنا هو صورة لما نحن مجرد وجه على متن الطائرة. مرة أخرى، لدينا الحق الاصطدام هنا. في 152. وسترى خلقنا قائمة مرتبطة الخروج من ذلك. مرة أخرى، جدول التجزئة تسلسل منفصلة النهج ليس واحد كنت يجب أن تأخذ لمشاكل تعيين ستة ولكن واحد هو أن الكثير من الطلاب تميل إلى أن تأخذ. لذلك على تلك المذكرة، دعونا نتحدث لفترة وجيزة قبل أن يخرج عن ستة المشكلة، وبعد ذلك سوف حصة قصة معك. لدينا ثلاث دقائق. تعيين ستة المشكلة. لديك أربع وظائف - الحمل، والتحقق، والحجم، وتفريغ. تحميل - كذلك، لقد تم الذهاب خلال الحمل فقط الآن. تعادلنا الحمل على متنها. وحتى بدأنا الترميز الكثير من إدراج في قائمة مرتبطة. ذلك الحمل ليست أكثر بكثير من ما كنا للتو به. الاختيار هو مرة واحدة لديك شيء تحميلها. انها نفس العملية لأن هذا. نفس أول جزأين حيث يمكنك رمي شيء في وظيفة تجزئة والحصول على قيمتها. ولكن الآن نحن لا إدراجه. الآن نحن نبحث عن ذلك. لقد نموذج التعليمات البرمجية المكتوبة من أجل إيجاد شيء ما في قائمة مرتبطة. أنا أشجعكم على ممارسة ذلك. ولكن حدسي العثور على شيء و مشابهة جدا لادخال شيء. في الواقع، نحن رسم صورة إيجاد شيء ما في قائمة مرتبطة، والانتقال من خلال حتى وصلت الى نهاية المطاف. وإذا كنت وصلت إلى نهاية لا يمكن و العثور عليه، ثم انها ليست هناك. ولهذا الاختيار، أساسا. التالي هو الحجم. دعونا تخطي الحجم. أخيرا قمت تفريغ. تفريغ هي واحدة أننا لم يوجه على متن الطائرة أو مشفرة حتى الآن. ولكن أنا أشجعكم على محاولة ذلك الترميز في عينة لدينا قائمة مرتبطة سبيل المثال. ولكن تفريغ حدسي يشبه مجانا - أو أعنيه هو مماثل للتحقق. باستثناء الآن في كل مرة وأنت تسير من خلال، وكنت لا مجرد فحص ل معرفة ما إذا كان لديك القيمة الخاصة بك هناك. ولكن كنت تتناولين تلك العقدة و تخليصه، أساسا. هذا ما يطلب منك تفريغ للقيام به. كل شيء مجانا كنت قد malloced. حتى وأنت تسير من خلال اللائحة بأكملها مرة أخرى، والذهاب من خلال تجزئة كله الجدول مرة أخرى. هذه المرة لا تحقق لمعرفة ما هو هناك. مجرد تحرير ما هناك. وأخيرا الحجم. ينبغي أن تنفذ الحجم. إذا كنت لا تنفذ حجم - سأقولها من هذا القبيل. إذا كنت لا تنفذ في حجم بالضبط سطر واحد من التعليمات البرمجية بما في ذلك العودة البيان، كنت القيام الحجم بشكل غير صحيح. لذلك تأكد من حجم، لتصميم كامل نقطة، كنت أفعل ذلك في واحد بالضبط سطر من التعليمات البرمجية، بما في ذلك البيان العودة. وليس حزمة تصل بعد، Akchar. القندس حريصة. أردت أن أقول شكرا يا رفاق على الحضور إلى القسم. لها هالوين سعيد. هذا هو زي بلدي. سأكون ارتداء هذا يوم الخميس إذا أراك في ساعات العمل. وإذا كنت غريبة عن بعض أكثر الخلفية لهذا الزي، ويشعر الحرة للتحقق من القسم 2011 لقصة لماذا أنا يرتدي زي القرع. وأنه هو قصة حزينة. لذا تأكد من لديك بعض الأنسجة المجاورة. ولكن على ذلك، إذا كان لديك أي الأسئلة سوف حول عصا بعد خارج القسم. حظا سعيدا على مشكلة تعيين ستة. وكما هو الحال دائما، إذا كان لديك أي الأسئلة، واسمحوا لي أن أعرف.