>> [عزف الموسيقى]
>> DOUG لويد: OK، وذلك في هذه النقطة في الدورة،
لقد غطت الكثير من أساسيات C. نحن نعرف الكثير عن المتغيرات، والمصفوفات،
مؤشرات، كل ما الأشياء الجيدة.
تلك هي كل نوع من المدمج في أن نرى مثل الأساسيات،
لكن يمكننا أن نفعل أكثر من ذلك، أليس كذلك؟
يمكننا الجمع بين الأشياء معا بطرق مثيرة للاهتمام.
>> وذلك دعونا نفعل ذلك، دعونا نبدأ إلى فرع من أصل ما C يعطينا،
والبدء في إنشاء البيانات الخاصة بنا الهياكل باستخدام هذه بناء
كتل معا لنفعل شيئا حقا قيمة ومفيدة.
طريقة واحدة يمكننا أن نفعل هذا هو للحديث عن مجموعات.
لذلك حتى الآن كان لدينا نوع واحد من البيانات هيكل لتمثيل مجموعات
من مثل القيم، قيم متشابهة.
من شأنه أن يكون صفيف.
لدينا مجموعة من الأعداد الصحيحة، أو مجموعات من الشخصيات وهلم جرا.
>> والهياكل فرز أيضا من بيانات هيكل لجمع المعلومات،
ولكنها ليست لجمع مثل القيم.
فإنه عادة ما تختلط أنواع مختلفة من البيانات معا داخل صندوق واحد.
ولكنها ليست في حد ذاتها تستخدم لسلسلة معا
أو الاتصال معا مماثلة البنود، مثل صفيف.
صفائف كبيرة ل عنصر بالبحث، ولكن تذكر
أنه من الصعب جدا لإدراج في صفيف،
إلا أننا إدراج في النهاية من أن مجموعة.
>> وخير مثال لدي لذلك هو الإدراج النوع.
اذا كنت أذكر لدينا شريط فيديو على الإدراج النوع،
كان هناك الكثير من حساب تشارك في وجود
لالتقاط العناصر، وتحويلهم للخروج من الطريق لتناسب شيء
في وسط مجموعة الخاصة بك.
يعاني صفائف أيضا من آخر المشكلة، وهي عدم المرونة.
عندما نعلن صفيف، نحن على طلقة واحدة في ذلك.
نصل الى القول، أريد العديد من هذه العناصر.
قد يكون 100، أنه قد تكون 1000، أنه قد
يكون x حيث x هو الرقم الذي المستخدم قدم لنا في موجه أو في الأمر
الخط.
>> ولكن نحن فقط على طلقة واحدة في ذلك، ونحن لا تحصل على ثم يقول يا، في الواقع أنا
يحتاج 101، أو كنت بحاجة X زائد 20.
في وقت متأخر جدا، ونحن قد أعلن بالفعل مجموعة، وإذا كنا نريد للحصول على 101 أو س
بالإضافة إلى 20، علينا أن نعلن مجموعة مختلفة تماما،
نسخ كافة عناصر المصفوفة أكثر، ثم لدينا ما يكفي.
وماذا لو كنا مخطئين مرة أخرى، ما إذا كنا فعلا بحاجة إلى 102، أو X زائد 40،
علينا أن نفعل ذلك مرة أخرى.
حتى انهم غير مرنة جدا لتغيير حجم البيانات لدينا،
ولكن إذا جمعنا معا بعض من الأساسيات التي قمنا بالفعل
علم مؤشرات والهياكل، على وجه الخصوص باستخدام ذاكرة ديناميكية
تخصيص مع malloc، ونحن يمكن وضع هذه القطع معا
لإنشاء بيانات جديدة structure-- ل قائمة ونحن قد say-- مرتبطة منفردة
الذي يسمح لنا أن تنمو و يتقلص مجموعة من القيم
ولن يكون لدينا أي مساحة مهدرة.
>> ذلك مرة أخرى، فإننا ندعو هذه الفكرة، هذه الفكرة، قائمة مرتبطة.
على وجه الخصوص، في هذا الفيديو نحن نتحدث عن قائمة مرتبطة منفردة،
ثم فيديو آخر سنتحدث قوائم حول ربط مضاعف، والتي
هو مجرد الاختلاف على موضوع هنا.
لكن قائمة مرتبطة منفردة ويتكون من العقد،
العقد كونها مجرد term-- مجردة انها مجرد شيء ادعو
هذا هو نوع من هيكل، في الأساس، وأنا؟
مجرد الذهاب الى نسميها node-- وهذا عقدة عضوين أو اثنين من المجالات.
فقد البيانات، عادة ما يكون صحيح، تعويم حرف،
أو يمكن أن تكون بعض نوع بيانات آخر التي قمت بتحديدها مع نوع مواطنه.
وأنه يحتوي على مؤشر ل عقدة أخرى من نفس النوع.
>> لذلك لدينا اثنين من الأشياء داخل هذه العقدة والبيانات ومؤشر
إلى عقدة أخرى.
وإذا كنت تبدأ تصور هذا، ويمكن كنت تفكر في ذلك
مثل سلسلة من العقد التي ترتبط معا.
لدينا عقدة الأولى، يحتوي على بيانات، ومؤشر
إلى العقدة الثانية، الذي يحتوي على البيانات، ومؤشر إلى العقدة الثالثة.
وولهذا السبب نحن نسميها قائمة مرتبطة، انهم مرتبطة معا.
>> ماذا يعني هذا خاص هيكل العقدة تبدو وكأنها؟
حسنا، إذا كنت تذكر من لدينا شريط فيديو على تحديد الأنواع المخصصة، مع نوع صفر،
يمكننا تعريف structure-- و اكتب تحديد هيكل من هذا القبيل.
tyepdef البنية sllist، ثم أنا باستخدام قيمة الكلمة هنا تعسفا
للإشارة إلى أي نوع بيانات حقا.
هل يمكن أن تمر على عدد صحيح أو عدد عشري، هل يمكن أن يكون كل ما تريد.
ليس يقتصر على مجرد الأعداد الصحيحة، أو أي شيء من هذا القبيل.
لذلك قيمة هو مجرد تعسفيا نوع البيانات، ومن ثم مؤشر
إلى عقدة أخرى من نفس النوع.
>> الآن، هناك القليل من الصيد هنا مع تحديد هيكل
عندما حان بنية مرجعية الذات.
يجب أن يكون لدي مؤقتة اسم لهيكل بلدي.
في نهاية اليوم الأول نريد بوضوح أن نسميها
عقدة SLL، وهذا في نهاية المطاف جديدة تسمية جزء من بلادي نوع تعريف،
ولكن لا يمكنني استخدام عقدة SLL في منتصف هذا.
والسبب، وأنا لم خلق نوع يسمى عقدة SLL
حتى أنا ضربت هذه النقطة الأخيرة هنا.
حتى هذه النقطة، يجب أن يكون لدي طريقة أخرى للإشارة إلى هذا النوع من البيانات.
>> وهذا هو النفس نوع البيانات المرجعية.
عليه؛ ق نوع بيانات ل الهيكل الذي يحتوي على البيانات،
ومؤشر إلى آخر هيكل من نفس النوع.
لذلك أنا بحاجة إلى أن تكون قادرة على الرجوع إلى هذا النوع من البيانات مؤقتا على الأقل،
حتى يعطيها مؤقتة اسم بنية sllist
يتيح لي الفرصة لثم يقول أنا أريد المؤشر إلى sllist البنية آخر،
نجم البنية sllist، ثم بعد لقد أكملت التعريف،
يمكنني الآن نسمي هذا النوع عقدة SLL.
>> ولهذا السبب ترى هناك اسم مؤقت هنا،
ولكن اسم دائم هنا.
في بعض الأحيان قد ترى تعريفات هيكل،
على سبيل المثال، التي لا المرجعية الذاتية، التي
لم يكن لديك اسم محدد هنا.
فإنها يمكن أن تقول فقط typedef والبنية، فتح متعرج ومن ثم تحديد ذلك.
ولكن إذا كنت البنية هي النفس المرجعية، وهذا هو واحد،
تحتاج إلى تحديد اسم نوع مؤقت.
ولكن في نهاية المطاف، والآن أننا قد فعلت ذلك،
يمكن أن نشير فقط إلى هذه العقد، هذه الوحدات،
كما عقد SLL لأغراض ما تبقى من هذا الفيديو.
>> كل الحق، لذلك نحن نعرف كيف إنشاء عقدة قائمة مرتبطة.
نحن نعرف كيفية تعريف عقدة قائمة مرتبطة.
الآن، إذا كنا في طريقنا للبدء استخدامها لجمع المعلومات،
هناك بضع عمليات نحن تحتاج إلى فهم والتعامل معها.
نحن بحاجة إلى معرفة كيفية إنشاء قائمة مرتبطة من العدم.
اذا لم يكن هناك قائمة بالفعل، نحن نريد أن تبدأ واحدة.
لذلك نحن بحاجة إلى أن تكون قادرة لإنشاء قائمة مرتبط،
نحتاج على الأرجح للبحث من خلال القائمة رابط
العثور على العنصر الذي نبحث عنه.
نحن بحاجة إلى أن تكون قادرة على إدراج أشياء جديدة في القائمة،
نريد قائمتنا لتكون قادرة على النمو.
وعلى نحو مماثل، ونحن نريد أن نكون قادرين لحذف الأشياء من قائمتنا،
نريد قائمتنا لتكون قادرة على الانكماش.
وفي نهاية لدينا برامج خاصة
اذا كنت أذكر أننا حيوي تخصيص الذاكرة
لبناء هذه القوائم عادة، نريد الافراج عن كل من تلك الذاكرة
عندما ننتهي العمل معها.
ولذا فإننا بحاجة إلى أن تكون قادرة على حذف قائمة كاملة مرتبطة في واحد تفشل انقضاض.
لذلك دعونا من خلال الذهاب بعض من هذه العمليات
وكيف يمكننا تصور لهم، يتحدث في التعليمات البرمجية شبة الكود على وجه التحديد.
لذلك نحن نريد لخلق قائمة مرتبطة، لذلك ربما نحن
تريد أن تحدد وظيفة مع هذا النموذج.
SLL نجمة عقدة، وخلق، وأنا مارة في حجة واحدة، وبعض البيانات التعسفي
اكتب مرة أخرى، من نوع البيانات التعسفي.
ولكن أنا returning-- هذه الوظيفة يجب أن العودة إلى لي المؤشر، لمنفردة
ربط العقدة القائمة.
مرة أخرى، ونحن نحاول خلق قائمة مرتبطة من العدم،
لذلك أنا بحاجة مؤشر ل هذه القائمة عندما انتهيت.
>> فما هي الخطوات المتبعة هنا؟
حسنا، أول شيء أنا تنوي القيام به هو حيوي
تخصيص مساحة لعقدة جديدة.
مرة أخرى، ونحن خلق من ذلك رقيقة الهواء، لذلك نحن بحاجة إلى مساحة malloc لذلك.
وبطبيعة الحال، فورا بعد أن malloc،
نحن دائما التحقق للتأكد من أن لدينا pointer-- لم نحصل على باطل الظهر.
لأنه إذا حاولنا و إذعان مؤشر فارغة،
ونحن في طريقنا تعاني من segfault ونحن لا نريد ذلك.
>> ثم نريد لملء في الميدان، نريد تهيئة حقل القيمة
وتهيئة الحقل التالي.
ثم نريد to-- في نهاية المطاف باعتبارها وظيفة النموذج indicates-- نريد
للعودة مؤشر إلى عقدة SLL.
وذلك ما جعل هذا تبدو بصريا؟
حسنا، أولا نحن ذاهبون الى حيوي تخصيص مساحة لعقدة SLL الجديدة،
لذلك نحن malloc-- هذا التمثيل البصري
العقدة أنشأنا فقط.
ونحن تحقق للتأكد من انها ليست null-- في هذه الحالة،
ان الصورة ليست لديها أظهرت حتى لو كان باطلا،
كنا قد نفد من الذاكرة، لذلك نحن في حالة جيدة للذهاب الى هناك.
لذلك نحن الآن إلى الخطوة C، تهيئة الحقل قيمة العقد.
حسنا، بناء على هذه الوظيفة استدعاء أنا باستخدام هنا،
يبدو وكأنني أريد أن يمر في 6، لذلك سوف أكون أنا 6 في مجال القيمة.
الآن، تهيئة الحقل التالي.
حسنا، ما أنا ذاهب الى القيام به هناك، لا يوجد شيء المقبل، الحق،
هذا هو الشيء الوحيد في القائمة.
إذن ما هو الشيء التالي في القائمة؟
>> لا ينبغي أن نشير إلى أي شيء، أليس كذلك.
هناك شيء آخر هناك، فما هو مفهوم نعرف من هذا هو nothing--
مؤشرات إلى لا شيء؟
وينبغي أن يكون ربما نريد لوضع مؤشر فارغة هناك،
وسوف تمثل لاغية المؤشر كما مجرد مربع أحمر،
لا نستطيع أن نذهب إلى أبعد من ذلك.
كما سنرى بعد قليل على، سيكون لدينا في نهاية المطاف السلاسل
من السهام التي تربط هذه العقد معا،
ولكن عندما ضرب مربع أحمر، وهذا باطل،
لا نستطيع أن نذهب إلى أبعد من ذلك، هذا هو نهاية القائمة.
>> وأخيرا، نحن نريد فقط أن عودة مؤشر إلى هذه العقدة.
ولذا فإننا سوف يطلق عليه الجديدة، وسيعود جديدة
لذلك يمكن استخدامها في مهما كانت وظيفة إنشائه.
لذلك هناك نذهب، لقد قمنا بإنشاء منفردة ربط العقدة قائمة من العدم،
والآن لدينا قائمة نتمكن من العمل مع.
>> الآن، دعونا نقول أننا بالفعل لدينا سلسلة كبيرة،
ونحن نريد أن تجد شيئا في ذلك.
ونحن نريد وظيفة ما يجري للعودة صحيحة أو خاطئة، اعتمادا
على ما إذا كانت قيمة موجودة في تلك القائمة.
وظيفة النموذج، أو الإعلان عن تلك الوظيفة،
قد تبدو وكأنها this-- منطقي العثور عليها، و ثم نريد أن تمر في حجتين.
>> الأولى، هي مؤشر إلى العنصر الأول من القائمة المرتبطة.
هذا هو في الواقع شيء عليك دائما نريد أن تتبع،
وفعلا قد يكون شيئا حتى كنت وضعت في متغير عمومي.
بمجرد إنشاء قائمة، كنت دائما، ودائما
تريد أن تتبع جدا العنصر الأول من القائمة.
وبهذه الطريقة يمكنك الرجوع إلى كل أخرى العناصر التي كتبها مجرد عقب سلسلة،
دون الحاجة للحفاظ على مؤشرات سليمة إلى كل عنصر واحد.
ما عليك سوى أن تتبع أول واحد لو انهم كل بالسلاسل معا.
>> ثم الشيء الثاني نحن يمر مرة أخرى
غير some-- تعسفا أيا كان نوع البيانات نحن
يبحث عن وجود داخل نأمل احدة من العقد في القائمة.
فما هي الخطوات؟
كذلك، فإن أول شيء نقوم به هو نحن إنشاء مؤشر مستعرضة
مشيرا إلى رأس القوائم.
حسنا، لماذا نفعل ذلك، ونحن بالفعل لدينا مؤشر على رأس القوائم،
لماذا لا يمكننا فقط نقل أن أحد حولها؟
حسنا، كما قلت للتو، من المهم حقا بالنسبة لنا
للحفاظ على المسار دائما ل العنصر الأول جدا في القائمة.
وحتى انها في الواقع أفضل لإنشاء نسخة مكررة من ذلك،
واستخدام هذا التحرك حتى نتمكن أبدا نقل بطريق الخطأ بعيدا، أو أننا دائما
يملك المؤشر في مرحلة ما هو الحق على العنصر الأول من القائمة.
لذلك فمن الأفضل لخلق والثانية التي نستخدمها للتحرك.
>> ثم نحن فقط مقارنة سواء حقل القيمة في تلك العقدة
هو ما نبحث عنه، وإذا كان لا، نحن فقط الانتقال إلى العقدة المقبل.
ونستمر في فعل ذلك أكثر، وأكثر، وأكثر،
حتى ونحن إما أن تجد العنصر، أو أننا ضرب
null-- نحن قد وصلنا إلى نهاية من قائمة وانه ليس هناك.
هذا نأمل أن قرع جرس لك البحث الخطي كما للتو،
نحن فقط تكرار ذلك في هيكل قائمة مرتبطة منفردة
بدلا من استخدام صفيف للقيام بذلك.
>> حتى هنا مثال قائمة مرتبطة منفردة.
يتكون هذا واحد من خمسة العقد، وليس لدينا
مؤشر إلى رئيس القائمة، وهو ما يسمى القائمة.
أول شيء نريد أن نفعله هو مرة أخرى، وخلق هذا المؤشر اجتياز.
لذلك لدينا الآن اثنين من المؤشرات التي تشير إلى نفس الشيء.
>> الآن، لاحظ هنا أيضا، لم أكن يجب أن malloc أي مساحة للبالسفر.
أنا لا أقول بالسفر يساوي malloc شيء، تلك العقدة موجود بالفعل،
هذه المساحة في الذاكرة موجود بالفعل.
لذلك كل ما أفعله هو في الواقع خلق مؤشر آخر على ذلك.
أنا لا mallocing إضافي الفضاء، فقط الآن اثنين من المؤشرات
لافتا إلى نفس الشيء.
>> ذلك هو 2 ما أبحث عنه؟
حسنا، لا، وذلك بدلا أنا الذهاب للانتقال إلى المرحلة التالية.
وذلك أساسا أود أن أقول، بالسفر يساوي بالسفر المقبل.
هو 3 ما أنا أبحث عن، لا.
لذلك أنا لا تزال تسير من خلال، حتى في نهاية المطاف
الحصول على 6 وهو ما أنا أبحث للبناء على استدعاء دالة
لدي في الجزء العلوي هناك، وهكذا انتهيت.
>> الآن، ما إذا كان العنصر أنا تبحث عن يست في القائمة،
وأنه لا يزال الذهاب إلى العمل؟
حسنا، لاحظ أن القائمة هنا يختلف بمهارة،
وهذا هو آخر شيء هذا المهم مع القوائم المرتبطة،
لم يكن لديك للحفاظ على لهم في أي ترتيب معين.
يمكنك إذا كنت تريد، ولكن كنت قد لاحظت بالفعل
اننا لا تتبع ما العنصر رقم نحن في.
>> وهذا النوع من التجارة أحد أننا يكون مع قائمة مرتبطة الآيات المصفوفات،
وذلك ليس لدينا وصول عشوائي بعد الآن.
لا نستطيع أن نقول فقط، أريد للذهاب إلى العنصر 0TH،
أو العنصر 6TH من مجموعة بلدي، الذي يمكنني القيام به في صفيف.
لا أستطيع أن أقول أريد أن أذهب إلى عنصر 0TH، أو العنصر 6TH،
أو العنصر ال25 من قائمتي مرتبط، ليس هناك مؤشر المرتبطة بها.
ولذا فإنه لا يهم حقا إذا كان لنا أن الحفاظ على قائمتنا في النظام.
إذا كنت تريد لك يمكن بالتأكيد، ولكن هناك
لا يوجد سبب لماذا تحتاج إلى يتم الحفاظ عليها في أي أمر.
ذلك مرة أخرى، دعونا نحاول و العثور على 6 في هذه القائمة.
حسنا، نحن نبدأ في بداية، لا نجد 6،
ثم واصلنا عدم العثور على 6، حتى نحن في نهاية المطاف الحصول على هنا.
الحق في ذلك نقاط الآن بالسفر إلى العقدة تحتوي على 8، وستة ليست هناك.
>> لذا فإن الخطوة المقبلة ستكون للذهاب إلى مؤشر المقبل،
أقول ذلك بالسفر يساوي بالسفر المقبل.
حسنا، بالسفر المقبل، وأشار المربع الأحمر هناك، لاغيا.
ولذلك لا يوجد في أي مكان آخر ل تذهب، وحتى في هذه النقطة
يمكننا أن نستنتج أننا وصلنا نهاية القائمة المرتبطة،
و6 ليس في هناك.
وسيتم إعادتها خطأ في هذه الحالة.
>> OK، كيف يمكننا إدراج جديدة عقدة في قائمة مرتبطة؟
لذلك كنا قادرين على خلق قائمة مرتبطة من العدم،
ولكن ربما نحن نريد ل بناء سلسلة وليس
إنشاء مجموعة من قوائم مختلفة.
نحن نريد أن يكون قائمة واحدة أن لديه مجموعة من العقد في ذلك،
ليس حفنة من القوائم مع عقدة واحدة.
لذلك نحن لا يمكن أن تبقي فقط باستخدام إنشاء وظيفة حددنا في وقت سابق، ونحن الآن
تريد إدراج في قائمة موجود بالفعل.
>> حتى هذه الحالة، نحن ذاهبون لتمرير في حجتين،
المؤشر إلى رأس تلك القائمة التي نريد أن نضيف إلى ربط.
مرة أخرى، وهذا هو السبب في أنه من ذلك المهم أننا دائما
تتبع ذلك، ل انها الطريقة الوحيدة التي يمكننا حقا
أن الرجوع إلى قائمة بأكملها فقط عن طريق مؤشر إلى العنصر الأول.
لذلك نحن نريد أن يمر في مؤشر إلى أن العنصر الأول،
ومهما كانت قيمة نحن تريد إضافتها إلى القائمة.
وفي النهاية هذه الوظيفة سوف تعود مؤشر
إلى رئيس جديد للقائمة مرتبطة.
>> ما هي الخطوات المتبعة هنا؟
حسنا، تماما مثل مع خلق، نحن بحاجة إلى تخصيص حيوي
مساحة للعقدة جديدة، وتحقق للتأكد بالتأكيد نحن لا ينفد من الذاكرة، مرة أخرى،
لأننا باستخدام malloc.
ثم نريد أن تعبئة وتضاف العقدة،
ولذلك وضعت الرقم، أيا كان فال هو، في العقدة.
نحن نريد لإدراج عقدة في بداية القائمة المرتبطة.
>> هناك سبب أنني تريد أن تفعل هذا، وذلك
قد يكون من المفيد أخذ الثاني وقفة الفيديو هنا،
ونفكر لماذا أريد أن إدراج في بداية مرتبط
القائمة.
مرة أخرى، ذكرت في وقت سابق أنه لا حقا
يهم إذا علينا الحفاظ عليه في أي أجل، ولذلك ربما يكون هذا هو أدنى فكرة.
ورأيت ما سيحدث لو أننا أراد to-- أو من ثانية واحدة
منذ متى نحن ذاهبون من خلال البحث الذي
يمكن أن نرى ما يمكن يحدث إذا كنا نحاول
لإدراج في نهاية القائمة.
لأننا لم يكن لديك المؤشر إلى نهاية القائمة.
>> لذلك السبب الذي أريد لإدراج في البداية،
لأنني يمكن أن تفعل ذلك على الفور.
لدي المؤشر في البداية، و سنرى هذا في البصرية في الثانية.
ولكن إذا كنت تريد إدراج في النهاية، لدي لبدء في البداية،
اجتياز كل وسيلة ل نهاية، ثم تك عليه.
بحيث يعني أن إدراج في نهاية القائمة
سيصبح س ن العملية، تعود
لمناقشتنا ل التعقيد الحسابي.
انها تريد ان تصبح س العملية n، حيث كما حصلت قائمة أكبر، وأكبر،
وأكبر، وأنها سوف تصبح أكثر و من الصعب تك شيئا
على في نهاية المطاف.
ولكن من السهل دائما حقا ل تك شيئا على في البداية،
كنت دائما في البداية.
>> وسنرى البصرية لهذا مرة أخرى.
ثم بمجرد ان تنتهي من ذلك، مرة واحدة لقد إدراج عقدة جديدة،
نحن نريد أن يعود المؤشر جهدنا ل الرئيس الجديد لقائمة مرتبطة، التي
منذ نحن إدراج في بداية، سوف يكون في الواقع
مؤشر إلى عقدة أنشأنا فقط.
دعونا تصور هذا، لأنني أعتقد أنها سوف تساعد.
>> حتى هنا قائمتنا، وتتكون من أربعة عناصر، وهي العقدة التي تحتوي على 15،
الأمر الذي يشير إلى عقدة تحتوي على 9، والتي
يشير إلى العقدة التي تحتوي على 13، مما يشير إلى العقدة التي تحتوي على
10، والتي لديها لاغية المؤشر كما مؤشر المقبل
لذلك هذا هو نهاية القائمة.
لذلك نحن نريد لإدراج عقدة جديدة بقيمة 12
في بداية هذا القائمة، ماذا نفعل؟
حسنا، أولا نحن malloc الفضاء ل العقدة، ومن ثم وضعنا 12 في هناك.
>> حتى الآن نحن وصلنا الى نقطة اتخاذ القرار، أليس كذلك؟
لدينا بضع المؤشرات التي نستطيع
نقل، التي ينبغي لأحد أن ننتقل أولا؟
وينبغي أن نجعل 12 نقطة ل الرئيس الجديد للlist--
أو عفوا، يجب أن نجعل 12 إشارة إلى رئيس القديم من القائمة؟
أو ينبغي أن نقول أن يبدأ القائمة الآن في 12.
هناك تمييز هناك، ونحن سوف ننظر
على ما يحدث مع كل من في الثانية.
>> ولكن هذا يؤدي إلى موضوع كبير للالشريط الجانبي،
وهو أن واحدة من أصعب الأمور مع القوائم المرتبطة
هو ترتيب المؤشرات في الترتيب الصحيح.
إذا قمت بنقل الأشياء من النظام، يمكنك في نهاية المطاف عن طريق الخطأ
اليتم بقية القائمة.
وهنا مثال على ذلك.
لذلك دعونا نذهب مع فكرة of-- حسنا، لقد خلقت فقط 12.
نحن نعرف 12 سيكون الرئيس الجديد للقائمة،
وهكذا لماذا لا نتحرك فقط مؤشر القائمة إلى نقطة هناك.
>> حسنا، هذا جيد.
وحتى الآن حيث يقوم 12 نقطة في المرة القادمة؟
أعني، بصريا يمكننا أن نرى أنه سوف يشيرون إلى 15،
كبشر من الواضح جدا بالنسبة لنا.
كيف يمكن للكمبيوتر تعلم؟
ليس لدينا أي شيء لافتا الى 15 بعد الآن، أليس كذلك؟
>> لقد فقدت أي قدرة على الرجوع إلى 15.
لا نستطيع أن نقول السهم الجديد يساوي القادمة شيء، لا يوجد شيء هناك.
في الواقع، لقد اليتامى بقية القائمة
بذلك، لدينا كسر عن طريق الخطأ في السلسلة.
ونحن بالتأكيد لا نريد ان نفعل ذلك.
>> لذلك دعونا نعود ونحاول مرة أخرى.
ربما الشيء الصحيح الذي ينبغي القيام به هو وضع 12 في مؤشر المقبل
في الرأس القديم من قائمة البداية، ثم اننا يمكن ان تتحرك لائحة أكثر.
في واقع الأمر، وهذا هو الترتيب الصحيح أننا
تحتاج إلى متابعة عندما نكون العمل مع قائمة مرتبطة منفردة.
نحن دائما نريد لربط عنصر جديد إلى القائمة،
قبل أن نتخذ هذا النوع من خطوة هامة لتغيير
حيث رأس قائمة مرتبطة هو.
مرة أخرى، هذا شيء من هذا القبيل الأساسي، نحن لا نريد أن تفقد مسارها من ذلك.
>> لذلك نحن نريد أن نتأكد من أن يتم ربط كل شيء معا،
قبل أن ننتقل هذا المؤشر.
وحتى هذا سيكون الترتيب الصحيح، الذي هو ربط 12 في القائمة،
ثم يقول أن القائمة تبدأ 12.
إذا كان لنا أن قال وتبدأ القائمة في 12 و ثم حاولت الاتصال 12 إلى القائمة،
لقد رأينا بالفعل ما يحدث.
نفقد القائمة عن طريق الخطأ.
>> OK، لذلك أكثر شيء واحد للحديث عن.
ماذا لو كنا نريد للتخلص من لكامل قائمة ربطت في وقت واحد؟
مرة أخرى، نحن mallocing كل هذا الفضاء، ولذا فإننا
تحتاج إلى تحريرها عندما ننتهي.
حتى الآن نحن نريد أن حذف القائمة المرتبطة بأكملها.
حسنا، ماذا نريد أن نفعل؟
>> إذا كنا قد وصلنا إلى مؤشر فارغة، ونحن تريد أن تتوقف، وإلا، فقط حذف
بقية القائمة ثم يحررني.
حذف بقية القائمة، ثم تحرير العقدة الحالية.
ما هذا الصوت مثل، ما الأسلوب ديك تحدثنا
عن سبق هذا الصوت مثل؟
حذف الجميع، ثم أعود وحذف لي.
>> هذا العودية، لقد حققنا مشكلة أصغر قليلا،
نقوله حذف الجميع آخر، ثم يمكنك حذف لي.
ومزيد من أسفل الطريق، تلك العقدة سيقول، حذف الجميع.
ولكن في نهاية المطاف أننا سنصل إلى النقطة حيث كانت القائمة فارغة،
وهذا هو الحال لدينا قاعدة.
>> لذلك دعونا نلقي نظرة على هذا، وكيف يمكن أن تعمل.
حتى هنا قائمتنا، هو نفسه قائمة كنا نتحدث فقط عن،
وهناك خطوات.
هناك الكثير من النصوص هنا، ولكن نأمل أن التصور سوف تساعد.
>> لذلك نحن have-- وأنا سحبت أيضا حتى لدينا إطارات كومة التوضيح
من لدينا شريط فيديو على أكوام المكالمة، ونأمل كل هذا
معا سوف تظهر لك ما يحدث.
حتى هنا كود شبة الكود لدينا.
اذا وصلنا الى فارغة مؤشر، ووقف، وإلا،
حذف بقية القائمة، ثم تحرير العقدة الحالية.
حتى الآن، list-- مؤشر أننا
يمر في لتدمير النقاط إلى 12.
12 ليس مؤشر فارغة، لذلك نحن الذهاب إلى حذف بقية القائمة.
>> ما هو حذف بقيتنا المعنية؟
كذلك، فهذا يعني اتخاذ دعوة لتدمير قائلا
أن 15 هو بداية لل بقية القائمة نريد التخلص منه.
وبالتالي فإن الدعوة لتدمير 12 هو نوع من معلقة.
المجمدة عليه هناك، والانتظار ل الدعوة إلى تدمير 15، لإنهاء مهمتها.
>> حسنا، 15 ليس مؤشر فارغة، و لذلك يحدث أن أقول، كل الحق،
كذلك، حذف بقية القائمة.
تبدأ بقية القائمة في 9، وذلك سنقوم فقط
الانتظار حتى تقوم بحذف كل ما الاشياء، ثم أعود وحذف لي.
حسنا 9 ذاهب الى القول، أيضا، أنا لست مؤشر فارغة،
لذلك حذف بقية القائمة من هنا.
وذلك في محاولة وتدمير 13.
13 يقول: أنا لست مؤشر فارغة، نفس الشيء، فإنه يمر باك.
10 ليس مؤشر فارغة، 10 يحتوي على مؤشر فارغة،
ولكن 10 ليس في حد ذاته لاغية مؤشر في الوقت الراهن،
وهكذا يمر رهيبة جدا.
>> والآن قائمة نقطة هناك، حقا أن أشير إلى some--
إذا كان لي مساحة أكبر في الصورة، ذلك أن أشير إلى بعض المساحة عشوائي
أننا لا نعرف ما هو عليه.
انها مؤشر فارغة على الرغم من قائمة حرفيا الآن تعيينها من القيم الخالية.
انها لافتا الحق داخل هذا المربع الأحمر.
وصلنا مؤشر فارغة، لذلك نحن يمكن أن تتوقف، وننتهي.
>> وبحيث إطار الأرجواني هو now-- في أعلى stack-- هذا الإطار النشط،
ولكن انها فعلت.
إذا كنا قد وصلت مؤشر فارغة، ووقف.
لم نفعل أي شيء، نحن لا يمكن تحرير مؤشر فارغة،
نحن لم malloc أي الفضاء، وحتى ننتهي.
بحيث إطار وظيفة ودمرت، ونحن
resume-- نلتقط حيث غادرنا قبالة مع المقبل أعلى واحد، والتي
هو هذا الإطار الأزرق الداكن هنا.
لذلك نحن التقاط الحق حيث توقفنا.
حذفنا بقية قائمة بالفعل، لذلك نحن الآن
الذهاب لتحرير العقد الحالي.
وحتى الآن نستطيع أن نحرر هذه العقدة، والآن لقد وصلنا إلى نهاية الدالة.
وهكذا يتم تدمير هذا الإطار وظيفة، ونلتقط في واحدة الأزرق الفاتح.
>> لذلك says-- لقد done-- بالفعل حذف بقية القائمة، لذلك
تحرير العقدة الحالية.
والآن الإطار الأصفر هو مرة أخرى في أعلى المكدس.
وهكذا كما ترون، نحن الآن تدمير القائمة من اليمين إلى اليسار.
>> ماذا كان سيحدث، على الرغم من إذا كان علينا القيام به الأشياء بطريقة خاطئة؟
تماما مثل عندما حاولنا لإضافة عنصر.
إذا كنا افسدت السلسلة، إذا نحن لا ربط مؤشرات
بالترتيب الصحيح، واذا كنا الافراج فقط العنصر الأول،
إذا كان لنا أن تحررت للتو رئيس القائمة، ونحن الآن
ليس هناك طريقة للإشارة إلى بقية القائمة.
وهكذا سيكون لدينا كل شيء اليتامى،
سيكون لدينا ما هو دعا تسرب الذاكرة.
إذا كنت تذكر من لدينا شريط فيديو على تخصيص الذاكرة الديناميكية،
هذا ليس أمرا جيدا للغاية.
>> لذلك كما قلت، هناك هي عدة عمليات
أننا في حاجة إلى استخدامها للعمل مع قائمة مرتبطة على نحو فعال.
وكنت قد لاحظت أنا حذفت واحد، حذف عنصر واحد من مرتبط
القائمة.
السبب في أنني فعلت ذلك هو في الواقع نوع من
صعبة للتفكير في كيفية حذف عنصر واحد من منفردة
قائمة مرتبطة.
نحن بحاجة إلى أن تكون قادرة على تخطي شيء في القائمة التي
يعني نصل إلى أننا point-- تريد حذف هذه node--
ولكن من أجل جعله لذلك نحن لا تفقد أي معلومات،
نحن بحاجة إلى ربط هذه عقدة أكثر من هنا، هنا.
>> لذلك أنا ربما فعلت ذلك خطأ من منظور البصرية.
لذلك نحن في بداية دينا القائمة، ونحن نمضي قدما من خلال،
نحن نريد لحذف هذه العقدة.
إذا كان لنا أن مجرد حذفه، لقد كسر السلسلة.
هذه العقدة هنا يشير إلى شيء آخر،
أنه يحتوي على سلسلة من اليوم فصاعدا.
>> وذلك ما يتعين علينا القيام به في الواقع بعد أن نصل إلى هذه النقطة،
هو أننا بحاجة إلى خطوة واحدة الى الوراء، و ربط هذه العقدة لأكثر من هذه العقدة،
حتى نتمكن من ثم حذف واحد في الوسط.
ولكن القوائم المرتبطة منفردة لا توفر لنا وسيلة للذهاب إلى الوراء.
لذلك نحن بحاجة إلى إما الاحتفاظ اثنين من المؤشرات، ونقلها
نوع من النزول، واحدة خلف البعض ونحن نمضي، أو الحصول على نقطة
وبعد ذلك ترسل مؤشر آخر من خلال.
وكما ترون، فإنه يمكن الحصول على القليل من الفوضى.
لحسن الحظ، لدينا طريقة أخرى لحل ذلك،
عندما نتحدث عن القوائم المرتبطة على نحو مضاعف.
>> أنا دوغ ويد، وهذا هو CS50.