[Powered by Google Translate] [القسم 6: أقل راحة] [نيت Hardison] [جامعة هارفارد] [هذا CS50.] [CS50.TV] حسنا. مرحبا بكم في القسم 6. هذا الاسبوع، ونحن ذاهبون الى الحديث عن هياكل البيانات في القسم، في المقام الأول لأن المشكلة هذا الاسبوع تعيين على spellr لا في مجمله مجموعة من مختلف استكشاف بنية البيانات. هناك مجموعة من الطرق المختلفة التي يمكن أن تذهب مع مجموعة المشكلة، وهياكل أكثر البيانات التي يعرفون، أكثر الأشياء باردة يمكنك القيام به. 

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

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

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

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

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

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

الآن، الجزء التالي من هذا وظهرت سلسلة الخروج من المكدس. انا ذاهب الى ان نعطيكم بعض اللاعبين الوقت للعمل على هذا قليلا قليلا. انها اساسا تقريبا عكس ما فعلناه هنا في الدفع. ما قمت به هو في الواقع - عفوا. لقد تمهيد بي الأمر إلى الأجهزة أكثر من هنا، وفي الأجهزة، لقد سحبت عن المشكلة إنشاء 5 المواصفات. إذا كنا تكبير هنا، يمكننا أن نرى أنا في cdn.cs50.net/2012/fall/psets/pset5.pdf. لقد قمت بتحميل هذا الرمز أن الرجال وهو موجود هنا، section6.zip؟ حسنا. إذا لم تكن قد فعلت ذلك، هل هذا الحق الآن، بسرعة حقا. سوف أفعل ذلك في إطار المحطة الطرفية بلدي. فعلت فعلا هنا. نعم. نعم، وسام؟ >> لدي سؤال حول لماذا قلت s.string لشرائح SIZE = شارع؟ ما هو شارع؟ والتي حددت في مكان ما من قبل، أو - أوه، في شارع شار *؟ [Hardison] نعم، بالضبط. هو أن الحجة. >> أوه، حسنا. آسف. [Hardison] نحن تحديد السلسلة لدفع فيها كان السؤال الأخرى التي قد تأتي لأننا لم نتحدث حقا عن هنا اتخذنا من المسلم به أن هذا كان لدينا متغير يسمى ق كان ذلك في نطاق والوصول إلينا. اتخذنا من المسلم به أن هذا كان هذا البنية بنية تخزين العناصر. يبحث ذلك مرة أخرى في دفع هذا الرمز، يمكنك أن ترى أن نقوم به مع الاشياء التي حصلت على هذه السلسلة صدر في ولكن بعد ذلك فجأة، ونحن الحصول على s.size، مثل، أين تأتي من؟ في التعليمات البرمجية التي نحن في طريقنا للبحث في الأرشيف في القسم ومن ثم الاشياء التي عليك أن تفعل في مشكلتك مجموعات، لقد حققنا مكدس لدينا البنية متغير عمومي حتى نتمكن من الحصول على وظائف في مختلف لدينا جميع دون الحاجة إلى تمرير يدويا وتمريرها حول بالرجوع، تفعل كل هذا النوع من الاشياء لذلك. نحن الغش قليلا، اذا صح التعبير، لجعل الامور أجمل. وهذا شيء نقوم به هنا لأنه للمتعة، وأنه من الأسهل. في كثير من الأحيان، سترى الناس هذا إن كان لديهم بنية بيانات كبيرة يجري تشغيلها على أن داخل البرنامج. 

دعونا نعود الى الجهاز. لم يحصل الجميع بنجاح section6.zip؟ الجميع فك الضغط عن الملف باستخدام section6.zip بفك؟ إذا ذهبت إلى الدليل 6 القسم - آآآه، في كل مكان - وأنت ما في قائمة هنا، سترى أن كنت قد حصلت على ثلاثة مختلفة. ملفات ج. كنت قد حصلت على قائمة الانتظار، وSLL، وهو منفردة مرتبطة القائمة، وعلى كومة. إذا كنت تفتح stack.c، يمكنك أن ترى أن لدينا هذه البنية محددة بالنسبة لنا، البنية الدقيقة التي تحدثنا عنها في مجرد الشرائح. لقد وصلنا لدينا متغير عالمي لمكدس، لدينا لدينا وظيفة دفع، ثم لدينا لدينا وظيفة البوب. سوف أضع رمز لدفع احتياطية على الشريحة هنا، ولكن ما أود يا رفاق القيام به هو، بكل ما أوتيت من قدرتك، اذهب وتنفيذ وظيفة البوب. بمجرد تنفيذ ذلك، يمكنك ترجمة هذا مع جعل مكدس، ثم قم بتشغيل الملف التنفيذي الناتجة مكدس، وسوف يتم تشغيل كل هذا لأسفل رمز اختبار هنا في هذا الرئيسي. ويعتني الرئيسي الواقع جعل عملية شد والبوب ​​المكالمات والتأكد من أن كل شيء يمر على ما يرام. فإنه أيضا تهيئة حجم مكدس هنا لذلك لم يكن لديك ما يدعو للقلق تهيئة ذلك. يمكنك أن تفترض انه تم تهيئته بشكل صحيح بحلول الوقت الذي يمكنك الوصول إليه في وظيفة البوب. هل هذا معقول؟ حتى هنا نذهب. هناك رمز الدفع. سأعطيك الرجال 5 أو 10 دقائق. وإذا كان لديك أي أسئلة في هذه الأثناء بينما كنت الترميز، من فضلك اطلب منهم بصوت عال. إذا كان الأمر كذلك لتحصل على نقطة خلاف، فقط أسأل. اسمحوا لي أن أعرف، واسمحوا الجميع يعرف. العمل مع جارك أيضا. [دانيال] نحن فقط البوب ​​تنفيذ في الوقت الحالي؟ >> البوب ​​فقط. على الرغم من يمكنك نسخ تنفيذ دفعة إذا كنت ترغب بحيث اختبار العمل. لأنه من الصعب الحصول على أشياء لاختبار في - أو، فإنه من الصعب لاختبار ما ظهرت من كومة إذا لم يكن هناك أي شيء في كومة لتبدأ. 

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

والشيء الآخر القيام به عندما كنت - في البوب، ويجب عليك أن إنقاص الحجم. إذا كنت تتذكر مرة أخرى إلى الرسم البياني لدينا القليل هنا، حقا، الشيء الوحيد الذي شاهدناه يحدث عندما طالبنا البوب هو أن هذا الحجم تراجع، أولا إلى 2، ثم إلى 1. ثم عندما كنا دفعت عنصرا جديدا على، فإنه يذهب على الفور في المناسبة. [باسل] إذا كان s.size 2، ثم لن يذهب إلى العنصر 2، ثم كنت تريد أن عنصر البوب ​​قبالة؟ إذا كان الأمر كذلك ذهبنا إلى - >> لذلك دعونا ننظر إلى هذا مرة أخرى. إذا كان هذا هو مكدس لدينا في هذه المرحلة وندعو البوب، في مؤشر الذي هو العنصر الأكثر الأعلى؟ [باسل] في 2، لكنه سيحتاج لموسيقى البوب ​​3. الحق >>. ذلك حيث ان حجمنا هو 3، لكننا نريد لموسيقى البوب ​​العنصر في الفهرس 2. انها نموذجية من هذا النوع من جانب واحد من أن لديك مع الفهرسة الصفر من المصفوفات. لذلك كنت لا تريد لموسيقى البوب ​​العنصر الثالث، ولكن العنصر الثالث ليست في مؤشر 3. والسبب أننا لا نملك أن نفعل ذلك عندما 1 ناقص أننا ندفع ولأن في الوقت الحالي، لاحظت أن العنصر الأكثر الأعلى، إذا كان لنا أن دفع شيء آخر إلى المكدس في هذه المرحلة، ونحن نريد أن يدفع به في الفهرس 3. ومجرد أن ذلك يحدث لحجم ومؤشرات خط حتى عندما كنت تدفع. 

حصلت منظمة الصحة العالمية تنفيذ العمل المكدس؟ كنت قد حصلت على كومة عمل واحد. هل لديك البوب ​​العمل حتى الآن؟ [دانيال] نعم. أعتقد ذلك. تشغيل البرنامج >> وليس SEG يخطأ، انها طبع؟ هل طباعة "النجاح" عند تشغيله؟ نعم. جعل كومة، تشغيله، إذا كان بطباعة "النجاح"، ولا تذهب الطفرة، ثم كل شيء جيد. حسنا. دعونا نذهب الى الجهاز بسرعة حقا، وسنقوم من خلال هذا السير. إذا نظرنا إلى ما يحدث هنا مع البوب، دانيال، ما هو أول شيء قمت به؟ [دانيال] إذا s.size أكبر من 0. [Hardison] حسنا. ولماذا فعلت ذلك؟ [دانيال] للتأكد من أن هناك شيئا داخل المكدس. [Hardison] الحق. كنت ترغب في اختبار للتأكد من أن s.size أكبر من 0؛ خلاف ذلك، ماذا تريد أن يحدث؟ [دانيال] فارغة العودة؟ العودة >> فارغة، تماما. حتى إذا s.size أكبر من 0. ثم ما نحن فاعلون؟ ماذا نفعل إذا كانت المجموعة ليست فارغة؟ [ستيلا] أنت إنقاص حجم؟ يمكنك إنقاص >> الحجم، حسنا. فكيف فعلت ذلك؟ s.size >>--. [Hardison] الكبرى. ثم ماذا فعلت؟ [ستيلا] ثم قلت s.string العودة [s.size]. [Hardison] الكبرى. إلا أن ترجع فارغة. نعم، وسام؟ [سام] ولماذا لا يجب أن تكون s.size + 1؟ [Hardison] زائد 1؟ نعم >>. حصلت >> ذلك. [سام] فكرت لأنك تتناولين 1 من، ثم كنت على وشك أن العودة ليست واحدة أنهم طلبوا. [Hardison] و كان هذا فقط ما كنا نتحدث عن هذه المسألة برمتها من 0 المؤشرات. حتى إذا كنا إعادة تكبير أكثر من هنا. إذا نظرنا إلى هذا الرجل هنا، يمكنك أن ترى أننا عندما البوب، نحن ظهرت العنصر في الفهرس 2. 

لذلك نحن لدينا انخفاض حجم أولا، ثم حجمنا مباريات فهرسنا. إذا كنا لا إنقاص حجم أولا، ثم علينا أن نفعل حجم -1 و ثم إنقاص. كبيرة. كل شيء جيد؟ أي أسئلة حول هذا؟ هناك عدد من الطرق المختلفة لكتابة هذا أيضا. في الواقع، يمكننا أن نفعل شيئا من ذلك - يمكننا القيام به لاحد الخطوط الملاحية المنتظمة. يمكننا أن نفعل عودة من سطر واحد. حتى نتمكن من إنقاص فعلا قبل أن يعود عن طريق القيام بذلك. وبالتالي فإن وضع - قبل s.size. الذي يجعل خط كثيفة حقا. حيث الفرق بين - حجم الصورة و. s.size-- هو أن هذا POSTFIX - يسمونه POSTFIX لأن - يأتي بعد s.size-- يعني أن يتم تقييم s.size لأغراض العثور على مؤشر كما هو حاليا عند تنفيذ هذا الخط، ثم هذا - يحدث بعد يعدم الخط. بعد الوصول إلى عنصر في المؤشر s.size. وهذا ليس ما نريد، لأننا نريد أن يحدث إنقاص الأولى. Othewise، ونحن في طريقنا إلى أن الوصول إلى مجموعة، على نحو فعال، خارج الحدود. ونحن في طريقنا إلى أن الوصول إلى عنصر واحد أعلاه أننا نريد فعلا الوصول إليها. نعم، وسام؟ هل >> أسرع أو استخدام كميات أقل من RAM لجعل في سطر واحد أم لا؟ [Hardison] بصراحة، انها حقا يتوقف. [سام، غير مفهومة] >> نعم، فإنه يعتمد. يمكنك القيام الحيل مترجم للحصول على الاعتراف بأن المترجم، وعادة، وأتصور. 

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

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

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

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

تخيل حتى يكون لدينا قائمة انتظار لدينا، ونحن في طريقنا أن نسميها قائمة الانتظار. في البداية، عندما كنا مثيل فقط، عندما أعلن لدينا فقط، ونحن لم تهيئة أي شيء. كل شيء القمامة. وذلك بطبيعة الحال نحن نريد أن نتأكد من أننا تهيئة كل من حجم ومجالات الرأس لتكون 0، شيء معقول. يمكن أن نذهب أيضا إلى الأمام وخالية من العناصر في قائمة الانتظار لدينا. ومناسبا لجعل هذا الرسم، لاحظ أن قائمة الانتظار لدينا الآن يمكن أن تعقد سوى ثلاث عناصر؛ في حين لدينا كومة يمكن أن تعقد أربعة، يمكن أن قائمة الانتظار لدينا سوى ثلاث عقد. وهذا فقط لجعل تناسب الرسم التخطيطي. الشيء الأول الذي يحدث هنا هو أننا إدراج بقائمة الانتظار السلسلة "مرحبا". ومثلما فعلنا مع مكدس، لا شيء مختلف هنا بشكل رهيب، نلقي في السلسلة على سلاسل [0] وزيادة حجمنا بمقدار 1. نحن إدراج بقائمة الانتظار "وداعا"، ويحصل على وضعه على. ولذلك فإن هذا يبدو وكأنه كومة بالنسبة للجزء الاكبر. بدأنا هنا، عنصرا جديدا، عنصرا جديدا، حجم يبقي الصعود. ما يحدث في هذه المرحلة عندما نريد أن dequeue شيء؟ عندما نريد أن dequeue، وهو العنصر الذي نريد أن dequeue؟ [باسل] سلاسل [0]. صفر >>. صحيح تماما، باسل. نريد التخلص من السلسلة الأولى، هذا واحد، "مرحبا". فما كان الشيء الآخر الذي تغير؟ إشعارا عند قيامنا برزت شيء الخروج من المكدس، فقط قمنا بتغيير حجم، ولكن هنا، لدينا اثنين من الأشياء التي تغير. لا يقتصر الأمر على تغيير الحجم، ولكن التغييرات الرأس. هذا هو الذهاب مرة أخرى إلى نقطة شارلوت في وقت سابق: لماذا لدينا هذا العنوان أيضا؟ هل يعقل الآن، شارلوت؟ نوع >>. [Hardison] نوع؟ فماذا حدث عندما كنا dequeued؟ ماذا فعل رئيس نفعل ذلك الآن المثير للاهتمام؟ [شارلوت] أوه، لأنه تغير - حسنا. فهمت. لأن الرأس - حيث يتم الإشارة إلى رئيس تغييرات من حيث الموقع. انها لم تعد دائما مؤشر واحد صفر. نعم >>، بالضبط. إذا كان ما حدث dequeueing العنصر عالية وقد تم ولم يكن لدينا هذا المجال الرأس لأننا كانوا ينادون دائما هذه السلسلة في 0 مؤشر رأس قائمة الانتظار لدينا، ثم كنا بد من الانتقال بقية قائمة الانتظار أسفل. كنا بد من الانتقال "وداعا" من سلاسل من [1] إلى سلاسل [0]. والسلاسل [2] إلى أسفل إلى سلاسل [1]. وسوف يترتب علينا أن نفعل ذلك للحصول على قائمة كاملة من العناصر، مجموعة كاملة من العناصر. وعندما نقوم بذلك مع صفيف، أن يحصل مكلفة حقا. حتى هنا، انها ليست صفقة كبيرة. لدينا فقط ثلاثة عناصر في مجموعتنا. ولكن إذا كان لدينا قائمة انتظار لعناصر ألف أو مليون العناصر، ثم فجأة، ونحن نبدأ صنع حفنة من dequeue يدعو جميع في حلقة، الامور تسير حقا أن يتباطأ في وقت تحول فيه كل شيء إلى أسفل باستمرار. تعلمون، والتحول بحلول 1، التحول من التحول، 1 من 1، تحول بمقدار 1. بدلا من ذلك، ونحن نستخدم هذا العنوان، ونحن نسميها "مؤشر" على الرغم من أنها ليست حقا مؤشر بالمعنى الدقيق للكلمة، بل ليست نوع مؤشر. انها ليست * الباحث * أو حرف أو أي شيء من هذا القبيل. لكنه يشير إلى يشير أو رئيس قائمة الانتظار لدينا. نعم؟ 

[طالب] كيف تعرف dequeue لموسيقى البوب ​​قبالة كل ما هو على رأس؟ [Hardison] كيف dequeue تعرف كيف انصرف كل ما هو على رأس؟ الحق >>، نعم. ما >> انها تبحث في كل ما هو مجرد مجال من المقرر أن رئيس. حتى في هذه الحالة الأولى، إذا ما نظرنا هنا، رؤوسنا هو 0 0 مؤشر. الحق >>. [Hardison] لذلك يقول فقط حسنا، حسنا، العنصر في الفهرس 0، السلسلة "مرحبا"، هو العنصر على رأس قائمة الانتظار لدينا. لذلك نحن ذاهبون الى dequeue هذا الرجل. وسوف يكون ذلك العنصر الذي يحصل عاد إلى الطالب. نعم، سعد؟ لذا >> يحدد رئيس أساسا - أين أنت ذاهب إلى مؤشر ذلك؟ هذا هو بداية ذلك؟ نعم >>. حسنا >>. [Hardison] وهذا يصبح بداية جديدة لمجموعتنا. حتى عندما كنت dequeue شيء، كل ما عليك القيام به هو الوصول إلى عنصر في المؤشر q.head، وسوف يكون ذلك العنصر الذي تريد dequeue. لديك أيضا لإنقاص الحجم. سنرى في بعض الشيء حيث تصبح الأمور صعبة قليلا مع هذا. نحن dequeue، والآن، إذا كان لنا أن إدراج بقائمة الانتظار مرة أخرى، أين نحن إدراج بقائمة الانتظار؟ أين العنصر التالي في قائمة الانتظار لدينا تذهب؟ ويقول نريد أن إدراج بقائمة الانتظار السلسلة "CS". وإلى ذلك مؤشر الذي تذهب؟ [الطلاب] سلاسل [2]. >> الثانية. لماذا لا 2 و 0؟ [باسل] لأن الرأس هو الآن 1، ذلك أن مثل بداية القائمة؟ [Hardison] الحق. وما يدل على نهاية القائمة؟ ما كنا باستخدام للدلالة على نهاية الطابور لدينا؟ رئيس هو رئيس قائمة الانتظار لدينا، بداية قائمة الانتظار لدينا. ما هي نهاية قائمة الانتظار لدينا؟ [الطلاب] الحجم. الحجم >>، بالضبط. حتى عناصر جديدة لدينا في الذهاب في الحجم، والعناصر التي نتخذها تؤتي ثمارها على الفرار في الرأس. عندما كنا إدراج بقائمة الانتظار العنصر التالي، ونحن في وضعه في الحجم. [طالب] قبل وضع لكم في أن على الرغم من حجم كان 1، أليس كذلك؟ [Hardison] الحق. حتى لا جدا في الحجم. + الحجم، لا +1، ولكن رئيس +. لأن كل شيء تحول ونحن بمقدار الرأس. حتى هنا، ونحن الآن قد حصلت على قائمة الانتظار من حجم 1 أن يبدأ في مؤشر 1. الذيل هو مؤشر 2. نعم؟ 

[طالب] ماذا يحدث عند dequeue سلاسل [0]، وسلاسل "فتحات في الذاكرة مجرد الحصول على تفرغ، في الأساس، أو نسيان للتو؟ [Hardison] نعم. في هذا المعنى، ونحن ننسى منهم فقط. إذا كنا تخزين نسخ منها ل- والعديد من هياكل البيانات تخزين في كثير من الأحيان نسخهم الخاصة من العناصر حتى أن الشخص إدارة بنية بيانات لا داعي للقلق حول أين كل تلك المؤشرات تسير. بنية البيانات يحمل على كل شيء، ويحمل على لنسخ جميع، للتأكد من أن كل شيء استمرت بشكل مناسب. ومع ذلك، في هذه الحالة، هذه الهياكل البيانات فقط، للتبسيط، لا صنع نسخ من أي شيء اننا تخزين فيها. [طالب] لذلك هو هذا مجموعة المستمر لل-؟ نعم >>. إذا نظرنا إلى الوراء في ما كان تعريف هذا الهيكل، هو عليه. انها مجرد مجموعة والقياسية مثل كنت قد رأيت، مجموعة من شار * S. يفعل ذلك -؟ نعم >>، كنت أتساءل فقط إذا عليك تشغيل في نهاية الأمر من الذاكرة، إلى حد ما، إذا كان لديك كل هذه البقع الفارغة في الصفيف الخاص بك؟ [Hardison] نعم، هذا نقطة جيدة. 

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

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

ماذا سيحدث في هذه المرحلة إذا كان لنا أن dequeue شيء مرة أخرى؟ أي أفكار؟ ماذا سيحدث في الرأس؟ ما ينبغي أن يحدث في الرأس إذا كان لنا أن dequeue شيء آخر؟ رئيس الآن هو مؤشر على 2، وهو ما يعني أن رئيس قائمة الانتظار سلاسل [2]. [طالب] والتي ترجع 0؟ وينبغي أن تعود >> إلى 0. ينبغي أن يلتف حول العودة، بالضبط. حتى الآن، في كل مرة كنا نسميها dequeue، كنا إضافة واحدة في الرأس، إضافة واحد في الرأس، إضافة واحد في الرأس، إضافة واحد في الرأس. بمجرد أن يحصل على مؤشر رأس المؤشر في مجموعة مشاركة لدينا، ثم علينا أن التفاف حول إعادته إلى بداية، والعودة إلى 0. [شارلوت] ما الذي يحدد قدرة قائمة الانتظار في كومة؟ [Hardison] في هذه الحالة، لقد تم للتو باستخدام تعريف ثابت #. حسنا >>. [Hardison] في الملف C الفعلية.، يمكنك الذهاب في الوحل ومعها قليلا وجعله كبيرة أو صغيرة كما تريد. [شارلوت] لذلك عندما كنت مما يجعلها قائمة الانتظار، كيف تجعل جهاز الكمبيوتر تعرف كيف كبيرة تريد أن تكون المكدس؟ [Hardison] هذا سؤال كبير. هناك عدة طرق. واحد هو تحديد فقط في خط الهجوم وأقول هذا سيكون طابور لديها 4 عناصر أو 50 أو العناصر 10،000. الطريقة الأخرى هي أن تفعل ما الناس الطبعة القراصنة يفعلون وخلق وظائف لديها قائمة انتظار الخاص بك ينمو بشكل حيوي وأضاف الحصول على المزيد من الأشياء فيها. 

[شارلوت] حتى للذهاب مع الخيار الأول، ما الجملة التي تستخدمها لنقول للبرنامج ما هو حجم قائمة الانتظار؟ [Hardison] آه. لذلك دعونا نخرج من هذا. ما زلت في stack.c هنا، لذلك أنا مجرد الذهاب إلى التمرير لأعلى إلى الأعلى هنا. يمكنك ان ترى هذا الحق هنا؟ هذا هو تعريف # سعة 10. وهذا يكاد يكون بناء الجملة بالضبط نفس التي لدينا لقائمة الانتظار. إلا في قائمة الانتظار، لقد وصلنا هذا المجال إضافية في البنية هنا. [شارلوت] أوه، كنت اعتقد قدرة يعني القدرة على السلسلة. [Hardison] آه. انه >> الحد الأقصى لطول الكلمة. حصلت >> ذلك. نعم. قدرة هنا - وهذا هو نقطة كبيرة. وهذا شيء وهذا صعب لأن ما أعلن لدينا هنا هو مجموعة من شار * S. مجموعة من المؤشرات. هذا هو مجموعة من حرف. وربما هذا هو ما كنت قد رأيت عندما كنت قد تم إعلان مخازن للحصول على ملف I / O، عندما كنت قد تم إنشاء سلاسل يدويا على المكدس. ومع ذلك، ما لدينا هنا هو مجموعة من شار * S. لذلك فمن مجموعة من المؤشرات. في الواقع، إذا كان لنا أن إعادة تكبير بها ونحن ننظر إلى ما يجري هنا في العرض التقديمي، ترى أن العناصر الفعلية، والبيانات الشخصية لا يتم تخزين داخل مجموعة نفسها. ما المخزنة داخل مجموعتنا هنا المؤشرات إلى البيانات الشخصية. حسنا. حتى لقد رأينا كيف أن حجم قائمة الانتظار هو تماما مثل مع مكدس، حجم تحترم دائما عدد من العناصر حاليا في قائمة الانتظار. بعد القرارات 2 enqueues، وحجم هو 2. بعد إجراء dequeue حجم الآن 1. بعد إجراء آخر إدراج بقائمة الانتظار حجم يعود لتصل إلى 2. وبالتالي فإن حجم يحترم بالتأكيد عدد من العناصر في قائمة الانتظار، ثم رئيس وتبقي فقط ركوب الدراجات. وغني عن 0-1-2، 0-1-2، 0-1-2. وفي كل مرة ندعو dequeue، ويحصل على زيادة رأس المؤشر إلى مؤشر المقبل. وإذا كان رئيس على وشك أن يذهب أكثر، فإنه حلقات حول العودة إلى 0. حتى مع ذلك، يمكن أن نكتب وظيفة dequeue. ونحن في طريقنا لمغادرة ظيفة إدراج بقائمة الانتظار لليا رفاق لتنفيذ بدلا من ذلك. 

عندما كنا dequeue عنصر من قائمة الانتظار لدينا، ما هو أول شيء فعله دانيال عندما بدأنا الكتابة وظيفة البوب ​​لرزمة؟ اسمحوا لي أن نسمع من شخص لم يتحدث حتى الان. دعونا نرى، سعد، هل تذكر ما دانيال كما فعل أول شيء عندما كتب البوب؟ [سعد] وكان هناك، وكان - >> واختبارها عن شيء. [سعد] إذا كان حجم أكبر من 0. بالضبط >>. وماذا كان ذلك اختبار ل؟ [سعد] الذي كان اختبار لمعرفة إذا كان هناك أي شيء داخل الصفيف. [Hardison] نعم. بالضبط. لذلك لا يمكنك البوب ​​أي شيء للخروج من كومة إذا كان فارغا. وبالمثل، لا يمكن dequeue أي شيء من قائمة انتظار ما اذا كان فارغا. ما هو أول شيء يتعين علينا القيام به في وظيفة dequeue لدينا هنا، هل تعتقد؟ [سعد] إذا كان حجم أكبر من 0؟ نعم >>. في هذه الحالة، لقد اختبرت فعلا فقط لمعرفة ما اذا كان هو 0. إذا كان 0، يمكننا العودة فارغة. ولكن المنطق نفسه بالضبط. ودعونا نستمر في هذا. إذا كان حجم غير 0، حيث هو العنصر الذي نريد أن dequeue؟ [سعد] في الرأس؟ بالضبط >>. يمكننا سحب للتو العنصر الأول في قائمة الانتظار لدينا عن طريق الوصول إلى عنصر في الرأس. مجنون لا شيء. بعد ذلك، ماذا علينا ان نفعل؟ ما يجب أن يحدث؟ ما هو الشيء الآخر الذي تحدثنا عنه في dequeue؟ شيئان يجب أن يحدث، لأن لدينا قائمة انتظار قد تغير. [دانيال] تقليل حجم. لدينا >> للحد من حجم، وزيادة رأس؟ بالضبط. لزيادة رأس، يمكننا ليس فقط زيادة رأس عمياء، تذكر. يمكننا القيام به ليس فقط queue.head + +. علينا أن تشمل أيضا هذه من قبل وزارة الدفاع القدرات. ولماذا نحن وزارة الدفاع من قبل القدرات، ستيلا؟ [ستيلا] لانها التفاف حولها. بالضبط >>. نحن وزارة الدفاع على قدرة لأنه يحتوي التفاف حول العودة إلى 0. حتى الآن، في هذه المرحلة، يمكننا أن نفعل ما قال دانيال. يمكننا إنقاص الحجم. ومن ثم يمكن أن نعود فقط العنصر الذي كان في الجزء العلوي من قائمة الانتظار. يبدو نوع من gnarly في البداية. قد يكون لديك السؤال. آسف؟ 

[سام] لماذا هذا أولا في الجزء العلوي من قائمة الانتظار؟ أين أن تذهب؟ [Hardison] انها تأتي من السطر الرابع من أسفل. بعد أن اختبار للتأكد من أن لدينا قائمة انتظار ليست فارغة، انسحبنا * شار الأولى، ونحن سحب العنصر الذي يجلس على رأس مؤشر من مجموعة لدينا، لدينا خيوط >>، ومجموعة المكالمة التي الأول؟ [Hardison] ونحن ندعو لأول مرة. نعم. فقط لمتابعة ذلك، لماذا تعتقد كان علينا أن نفعل ذلك؟ [سام] كل الأول هو العودة فقط q.strings [q.head]؟ نعم >>. لأن >> نقوم به هذا التغير من q.head مع وظيفة وزارة الدفاع، وليس هناك طريقة للقيام بذلك ضمن خط العودة أيضا. [Hardison] بالضبط. كنت على الفور. سام كليا على الفور. السبب كان علينا أن سحب العنصر الأول في قائمة الانتظار لدينا وتخزينه في متغير لأن هذا الخط حيث كنا قد q.head فقط، هناك عامل وزارة الدفاع في وجود شيء لا يمكننا القيام به وأنها قد تصبح نافذة المفعول على الرأس دون - في سطر واحد. لذلك لدينا في الواقع لسحب العنصر الأول، ثم ضبط الرأس، ضبط حجم، ثم يعود العنصر الذي انسحبنا. وهذا هو الشيء الذي سنرى الخروج في وقت لاحق مع القوائم المرتبطة، كما لعبنا في جميع أنحاء معهم. في كثير من الأحيان عندما كنت تحرير أو التخلص من القوائم المرتبطة عليك أن تتذكر العنصر التالي، المؤشر التالي من قائمة مرتبطة قبل التخلص من النظام الحالي. لأن خلاف ذلك لك أن تتخلص من المعلومات من ما تبقى في القائمة. الآن، إذا ذهبت إلى الأجهزة الخاصة بك، يمكنك فتح queue.c-X للخروج من هذا. حتى لو كنت تفتح queue.c، اسمحوا لي تكبير هنا، سترى أن لديك ملف مماثلة المظهر. مماثلة ذات مظهر الملف إلى ما كان لدينا في وقت سابق مع stack.c. لقد وصلنا لدينا قائمة انتظار البنية المحددة فقط كما رأينا على الشرائح. 

لدينا لدينا وظيفة إدراج بقائمة الانتظار الذي هو بالنسبة لك أن تفعل. ونحن لدينا وظيفة dequeue هنا. ودون تنفيذ وظيفة dequeue في الملف، ولكن سوف أضع إعادته على برنامج PowerPoint بحيث يمكنك كتابته، إذا كنت ترغب. ذلك لمدة 5 دقائق القادمة أو نحو ذلك، يا رفاق العمل على إدراج بقائمة الانتظار الذي هو مجرد تقريبا على عكس dequeue. لم يكن لديك لضبط الرأس عندما كنت enqueueing، ولكن ماذا لديك لضبط؟ الحجم. حتى عندما كنت إدراج بقائمة الانتظار، يبقى الرأس لم يمسها، يحصل تغيير الحجم. ولكن الأمر يستغرق قليلا من - سيكون لديك للعب مع حولها أن وزارة الدفاع لمعرفة بالضبط ما يجب أن يتم إدراج مؤشر العنصر الجديد في. لذلك سأعطيك الرجال قليلا، وطرح dequeue احتياطية على الشريحة، وكما يا رفاق لديك أسئلة، يصرخ بها حتى نستطيع كل الكلام عنهم كمجموعة. أيضا، مع الحجم الذي مش - عند ضبط حجم، يمكنك فقط دائما - هل لديك حجم وزارة الدفاع من أي وقت مضى؟ [دانيال] رقم >> ليس لديك إلى وزارة الدفاع حجم والحق. وذلك لأن حجم دائما، إذا أنت الآن - على افتراض أنك إدارة الأمور بشكل مناسب، وسوف يكون حجم دائما بين 0 و 3. أين وزارة الدفاع لديك عندما كنت تفعل إدراج بقائمة الانتظار؟ [طالب] فقط على الرأس. فقط >> لرئيس، بالضبط. ولماذا لديك لوزارة الدفاع على الإطلاق في إدراج بقائمة الانتظار؟ عندما هو الحالة التي كنت قد لوزارة الدفاع؟ [طالب] إذا كان لديك الاشياء في أماكن، مثل مساحات في 1 و 2، وتحتاج بعد ذلك لك أن تضيف شيئا في 0. [Hardison] نعم، بالضبط. إذا كان الأمر كذلك المؤشر الرئيسي هو في النهاية، أو إذا كان حجم زائد رأسك هو أكبر، أو بدلا من ذلك، يتم الانتقال إلى بالالتفاف حول قائمة الانتظار. 

حتى في هذه الحالة أن لدينا هنا على الشريحة في الوقت الراهن، إذا كنت ترغب في إدراج بقائمة الانتظار شيء في الوقت الراهن، نريد أن إدراج بقائمة الانتظار شيء في مؤشر 0. حتى إذا كنت تبحث في ال 50 حيث يذهب، وأدعو إدراج بقائمة الانتظار 50، وتنخفض هناك في الأسفل. وغني عن 0 مؤشر. فإنه يستبدل "مرحبا" الذي dequeued بالفعل. [دانيال] لا تأخذ الرعاية من ذلك في dequeue بالفعل؟ لماذا يفعل أي شيء مع الرأس في إدراج بقائمة الانتظار؟ [Hardison] أوه، حتى أنك لا تعديل الرأس، آسف. ولكن لديك لاستخدام مشغل وزارة الدفاع عندما كنت الحصول على العنصر الذي تريد إدراج بقائمة الانتظار عندما كنت الحصول على العنصر التالي في قائمة الانتظار الخاصة بك. [باسل] لم أفعل ذلك، وأنا حصلت على "النجاح" هناك. [دانيال] أوه، أنا أفهم ما تقوله. [Hardison] لذلك أنت didn't - فعلتم فقط في q.size؟ [باسل] نعم. لم أكن مجرد تغيير الجانبين، أستطيع أن أفعل أي شيء مع الرأس. [Hardison] ليس لديك فعلا لإعادة الرأس إلى أن يكون أي شيء، ولكن عندما كنت في مؤشر مجموعة السلاسل، لديك فعلا على المضي قدما وحساب العنصر التالي حيث هو، وكان العنصر التالي في الكدسة لمجدل المكدس، دائما في مؤشر المقابلة لحجم. إذا كان لنا أن ننظر إلى الوراء حتى في كومة لدينا وظيفة دفع، يمكننا دائما غطس في العنصر الجديد الحق في حجم الفهرس. في حين مع قائمة الانتظار، لا يمكننا أن نفعل ذلك لأنه إذا نحن في هذه الحالة، وإذا كنا enqueued دينا 50 سلسلة جديدة يسير في الاتجاه الصحيح في سلاسل [1] ونحن لا نريد أن نفعل. نحن نريد أن يكون سلسلة جديدة تذهب في مؤشر 0. 

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

لذلك دعونا بسرعة حقا ننظر إلى ما وظيفة إدراج بقائمة الانتظار يبدو. ما هو أول شيء أن الناس حاولوا القيام به في الخط الخاص بك إدراج بقائمة الانتظار؟ في قائمة الانتظار هذه؟ على غرار ما فعلت لدفع المكدس. ماذا فعلت، ستيلا؟ [ستيلا، غير مفهومة] [Hardison] بالضبط. إذا كان (q.size == القدرات) - لست بحاجة لوضع الأقواس بلدي في المكان المناسب - عودة كاذبة. تكبير قليلا. حسنا. الآن ما هو الشيء التالي الذي كان علينا أن نفعل؟ تماما مثل مع مكدس، وإدراج في المكان المناسب. وذلك ما كان في المكان المناسب لإدراج ذلك؟ مع مكدس كان حجم المؤشر، مع هذا انها ليست تماما أن. [دانيال] لدي q.head-أو - q.strings >>؟ نعم >>. q.strings [+ q.head q.size وزارة الدفاع CAPACITY]؟ [Hardison] ونحن ربما تريد وضع أقواس حول هذا بحيث نحن نحصل على أسبقية المناسبة وذلك أن cleart للجميع. وتعيين أن المساواة؟ ل>> شارع؟ ل>> شارع. كبيرة. والآن ما هو الشيء الأخير الذي يتعين علينا القيام به؟ مثلما فعلنا في المكدس. >> بزيادة قيمة حجم؟ >> بزيادة قيمة حجم. الازدهار. وبعد ذلك، منذ بداية رمز عاد لتوه كاذبة افتراضيا، نحن نريد تغيير هذا إلى true اذا سارت الامور من خلال وسارت الامور بشكل جيد. حسنا. وهذا هو الكثير من المعلومات عن القسم. نحن لسنا أكثر من غاية. نريد أن نتحدث حقا عن منفردة بسرعة المرتبطة القوائم. سوف أضع هذا الأمر حتى نتمكن من العودة إليها في وقت لاحق. ولكن دعونا نعود إلى العرض الذي قدمناه لمجرد عدد قليل من أكثر الشرائح. إدراج بقائمة الانتظار حتى هو TODO، والآن لقد فعلنا ذلك. 

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

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

[سام] هل هذا هو نفس الشيء باستخدام PRED ذلك - تذكرت للتو، ليست ما هو الشيء PRED عنه؟ ليست في مضاعفة بين ومنفردة؟ [Hardison] دعونا ننظر في بالضبط ما كان يقوم به. حتى هنا نذهب. هنا هو رمز القائمة. هنا لدينا predptr، هنا. هل هذا ما كنت تتحدث عنه؟ لذلك كان هذا - انه تحرير قائمة وانه يحاول تخزين مؤشر إلى ذلك. ليست هذه هي مضاعفة، منفردة مرتبطة قوائم. يمكن أن نتحدث أكثر عن هذا في وقت لاحق لأن هذا هو يتحدث عن تحرير قائمة وأريد أن أثبت بعض الأشياء الأخرى أولا. ولكن هذا فقط - انها تذكر قيمة PTR [طالب] أوه، أنها مؤشر الآنفة الذكر؟ نعم >>. حتى نتمكن من زيادة ثم PTR نفسها قبل أن الحرة ثم ما هو predptr. لأن لا يمكننا PTR حرة وثم استدعاء PTR = PTR المقبل، أليس كذلك؟ من شأنها أن تكون سيئة. لذلك دعونا نرى، مرة أخرى إلى هذا الرجل. 

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

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

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

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

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

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

سادعك سد الثغرات هنا لأننا من الوقت. ولكن يبقى هذا الأمر في الاعتبار أثناء العمل على psets spellr الخاص بك. القوائم المرتبطة، إذا كنت تنفيذ جدول التجزئة، بالتأكيد سوف يأتي في سهل للغاية. وسوف تواجه هذا المصطلح لحلقات أكثر الأشياء التي تجعل الحياة أسهل كثيرا، ونأمل. أي أسئلة، بسرعة؟ [سام] هل ترسل SLL المنجزة والشوري؟ [Hardison] نعم. أنا ترسل الشرائح المنجزة والانتهاء كومة SLL وqueue.cs. [CS50.TV]