>> [عزف الموسيقى]
DOUG لويد: حسنا.
لذلك إذا كنت انتهيت للتو من أن الفيديو على القوائم المرتبطة منفردة آسف
تركت لك الخروج على قليلا من التشويق.
ولكن أنا سعيد لأنك هنا لإنهاء قصة القوائم المرتبطة على نحو مضاعف.
>> لذلك إذا كنت أذكر من هذا الفيديو، تحدثنا
حول كيفية ربط منفردة، قوائم تفعل حضور قدرتنا
للتعامل مع المعلومات حيث بلغ عدد العناصر
أو عدد العناصر في قائمة يمكن أن تنمو أو تنكمش.
يمكننا الآن التعامل مع شيء من هذا القبيل، حيث
لم نتمكن من التعامل معها مع المصفوفات.
>> لكنهم يعانون من واحد الحد الحرج الذي
وذلك مع ربط منفردة، القائمة، ونحن يمكن ان تتحرك من أي وقت مضى فقط
في اتجاه واحد من خلال القائمة.
والوضع الحقيقي الوحيد حيث يمكن أن تصبح مشكلة
وعندما كنا نحاول حذف عنصر واحد.
ونحن حتى لم مناقشة كيفية القيام بذلك في قائمة مرتبطة منفردة في شبة الكود.
فمن قابلة للتنفيذ بالتأكيد، ولكن يمكن أن يكون قليلا من المتاعب.
حتى إذا وجدت نفسك في الحالة التي تكون فيها
كنت تحاول حذف عناصر واحدة من القائمة
أو انها سوف تكون هناك حاجة أن عليك أن تكون حذف
عناصر واحدة من القائمة، قد ترغب
في النظر في استخدام مرتبطة مضاعف قائمة بدلا من قائمة مرتبطة منفردة.
لأن القوائم المرتبطة مضاعف تسمح لك لنقل كل الأمام وإلى الوراء
من خلال القائمة بدلا من فقط إلى الأمام من خلال list--
فقط عن طريق إضافة عنصر إضافي واحد لتعريف بنيتنا
للعقدة قائمة مرتبطة على نحو مضاعف.
>> مرة أخرى، إذا كنت لن سيتم حذف العناصر واحدة
من list-- لأننا سنضيف حقل إضافي لبنيتنا
التعريف، فإن العقد أنفسهم لالقوائم المرتبطة مضاعف
ذاهبون إلى أن تكون أكبر.
انهم ذاهبون الى اتخاذ حتى أكثر بايت من الذاكرة.
وحتى إذا كان هذا ليس شيئا كنت بحاجة الى الذهاب الى القيام به،
كنت قد تقرر انها لا يستحق المفاضلة
لديك لقضاء اضافية بايت من الذاكرة المطلوبة
للحصول على قائمة مرتبطة مضاعف إذا كنت لا ستكون حذف العناصر واحدة.
ولكنهم أيضا بارد لأشياء أخرى أيضا.
>> لذلك كما قلت، علينا فقط أن أضيف حقل واحد واحد لبنيتنا
definition-- هذه الفكرة من مؤشر السابق.
حتى مع قائمة مرتبطة منفردة، ونحن لدينا قيمة والمؤشر التالي،
وبالتالي فإن قائمة مرتبطة مضاعف للتو وسيلة للانتقال إلى الخلف أيضا.
>> الآن في ربط منفردة، قائمة الفيديو، تحدثنا
حول هذه خمسة من الأشياء الرئيسية التي تحتاج إلى أن تكون
قادرة على القيام بالعمل مع القوائم المرتبطة.
وبالنسبة لمعظم هذه، حقيقة انه من قائمة مرتبطة مضاعف
ليس حقا قفزة كبيرة.
لا يزال بوسعنا البحث من خلال فقط عن طريق المضي قدما من البداية إلى النهاية.
لا يزال بوسعنا أن إنشاء عقدة من العدم، الى حد كبير بنفس الطريقة.
يمكننا حذف قوائم جميلة بنفس الطريقة أيضا.
الأشياء الوحيدة التي تختلف بمهارة،
حقا، تقوم بإدراج عقد جديدة إلى القائمة،
وسوف نتحدث أخيرا عن حذف عنصر واحد من القائمة كذلك.
مرة أخرى، الى حد كبير الثلاثة الأخرى، ونحن
لن نتحدث عنهم الآن لأنهم فقط
تعديلات صغيرة جدا على الأفكار التي نوقشت في القائمة مقطع الفيديو المرتبط منفردة.
>> لذلك دعونا إدراج عقدة جديدة في قائمة مرتبطة على نحو مضاعف.
تحدثنا عن القيام بذلك ل قوائم منفردة مرتبط ايضا،
ولكن هناك بضعة اضافية أدرك مع القوائم المرتبطة على نحو مضاعف.
كان [؟ يمر؟] في الرأس من قائمة هنا وبعض القيمة التعسفية،
ونريد أن نحصل على رئيس جديد قائمة من هذه الوظيفة.
هذا هو السبب في ذلك يعود نجم dllnode.
فما هي الخطوات؟
هم، مرة أخرى، على غرار جدا إلى القوائم المرتبطة منفردة،
مع واحد بالإضافة اضافية.
نريد أن يخصص مساحة جديدة العقدة وتحقق للتأكد من انها صحيحة.
نحن نريد لملء تلك العقدة يصل مع كل ما المعلومات التي
نريد أن نضع في ذلك.
آخر شيء نحتاج إلى do-- لل شيء إضافي يتعين علينا القيام به، rather--
هو لإصلاح المؤشر السابق من الرأس القديم من القائمة.
تذكر أن ل قوائم مرتبطة على نحو مضاعف،
يمكننا المضي قدما وbackwards-- التي
يعني أن كل عقدة يشير الواقع إلى عقدتين أخرى بدلا من واحد فقط.
ولذا فإننا بحاجة إلى إصلاح رئيس القديم من القائمة
أن نشير إلى الوراء إلى الرئيس الجديد ل القائمة المرتبطة، والتي كان شيئا
لم يكن لدينا لتفعل من قبل.
وكما كان من قبل، ونحن فقط إرجاع المؤشر إلى الرئيس الجديد للقائمة.
>> وحتى هنا قائمة.
نحن نريد لادخال 12 الى هذه القائمة.
لاحظ أن الرسم البياني يختلف قليلا.
تحتوي كل عقدة ثلاثة fields-- البيانات، ومؤشر التالي باللون الأحمر،
والمؤشر السابق في الزرقاء.
لا شيء يأتي قبل العقدة 15، لذلك المؤشر في السابق لاغيا.
انها بداية القائمة.
لا يوجد شيء قبل ذلك.
ولا شيء يأتي بعد عقدة 10، و لذلك فمن المؤشر التالي باطل أيضا.
>> لذلك دعونا نضيف 12 إلى هذه القائمة.
نحتاج [غير مسموع] مساحة للعقدة.
وضعنا 12 داخل منه.
ثم مرة أخرى، ونحن بحاجة إلى أن نكون حقا الحرص على عدم كسر السلسلة.
نحن نريد لإعادة ترتيب مؤشرات بالترتيب الصحيح.
وأحيانا قد يعني- كما سنرى لا سيما
مع delete-- أن لدينا بعض مؤشرات زائدة عن الحاجة، ولكن هذا موافق.
>> وذلك ما نريد أن نقوم به أولا؟
أود أن أوصي الأشياء التي ينبغي على الارجح
تفعل هي لملء مؤشرات من أصل 12 العقدة قبل لمس أي شخص آخر.
فما هو 12 الذهاب للإشارة إلى الخطوة التالية؟
15.
ما يأتي قبل 12؟
لا شى.
الآن لقد ملأت معلومات إضافية في 12
لذلك فقد السابق، التالي، وقيمة.
>> ونحن الآن يمكن أن يكون 15-- هذا اضافية خطوة كنا نتحدث about-- نحن
يمكن أن يكون 15 نقطة إلى 12.
والآن يمكننا نقل رئيس قائمة مرتبطة يكون أيضا 12.
لذلك فمن مشابهة جدا لما نحن كانوا يفعلون مع القوائم المرتبطة منفردة،
باستثناء خطوة اضافية من ربط رئيس القديم من القائمة
إلى الرئيس الجديد للقائمة.
>> الآن دعونا حذف أخيرا عقدة من قائمة مرتبطة.
لذلك دعونا نقول لدينا بعض الوظائف الأخرى التي
تم العثور على عقدة نريد أن حذف وأعطانا مؤشر بالضبط
العقدة التي نريد حذفها.
نحن حتى لا need-- يقول لا يزال أعلن رئيس عالميا.
نحن لسنا بحاجة الرأس هنا.
كل هذه الوظيفة تقوم به هو أننا قمت وجدت مؤشر بالضبط نحن العقدة
يريدون التخلص من.
دعونا نتخلص منه.
انها أسهل كثيرا مع قوائم مضاعف مرتبطة.
First-- انها فعلا فقط بضعة أشياء.
نحن بحاجة فقط لإصلاح المحيطة مؤشرات العقد 'بحيث تجاوز
عقدة نريد حذفه.
ومن ثم يمكننا حذف هذه العقدة.
ذلك مرة أخرى، ونحن مجرد الذهاب من هنا.
لقد قررت على ما يبدو أن نحن نريد لحذف X. العقدة
ومرة أخرى، ما أنا القيام here-- من قبل way--
هو الحالة العامة ل العقدة التي هي في الوسط.
هناك بضع المحاذير الإضافية التي
تحتاج إلى النظر عندما كنت حذف البداية من القائمة
أو النهاية من القائمة.
هناك بضعة الخاصة الحالات الزاوية للتعامل مع وجود.
>> لذلك هذا يعمل لحذف أي عقدة في وسط واحد list-- أن
لديه مؤشر الشرعي إلى الأمام ومؤشر الشرعي الخلف،
الشرعي السابق والتالي المؤشر.
مرة أخرى، إذا كنت تعمل مع نهايات، ل
تحتاج إلى معالجة تلك بشكل مختلف قليلا،
ونحن لن الحديث عن ذلك الآن.
ولكن يمكنك على الأرجح معرفة ما يحتاج
إلى أن يتم فقط من خلال مشاهدة هذا الفيديو.
>> لذلك قمنا معزولة اكس X هو العقدة نريد أن حذف من القائمة.
ماذا نفعل؟
أولا، نحن بحاجة إلى إعادة ترتيب المؤشرات الخارجية.
نحن بحاجة إلى إعادة ترتيب بجوار 9 لتخطي 13
وأشر إلى 10-- التي ما فعلناه للتو.
ونحن بحاجة إلى أيضا إعادة ترتيب السابق 10 ل
للإشارة إلى 9 بدلا من الإشارة إلى 13.
>> ذلك مرة أخرى، وكان هذا الرسم البياني لتبدأ.
كانت هذه السلسلة لدينا.
نحن بحاجة إلى تخطي أكثر من 13، ولكن يتعين علينا أن نحافظ أيضا
سلامة القائمة.
نحن لا نريد أن نخسر أي المعلومات الواردة في أي من الاتجاهين.
لذلك نحن بحاجة إلى إعادة ترتيب مؤشرات بعناية
لذلك نحن لا كسر سلسلة على الإطلاق.
>> لذا يمكننا القول 9 في المؤشر التالي يشير إلى نفس المكان
أن ثلاثة عشر من التالي يشير مؤشر في الوقت الحالي.
لأننا في نهاية المطاف تريد الذهاب الى تخطي أكثر من 13.
لذلك أينما 13 نقطة المقبل، كنت أريد أن أشير تسعة هناك بدلا من ذلك.
حتى أن ذلك.
ثم أينما 13 نقطة العودة ل، كل ما يأتي قبل 13،
نريد أن نشير 10 لأنه بدلا من 13.
لاحظ الآن، إذا كنت تتبع الأسهم، يمكننا إسقاط 13
دون أن تفقد في الواقع أي معلومات.
لقد حافظت على سلامة القائمة، تتحرك إلى الأمام وإلى الخلف.
ومن ثم يمكننا مجرد نوع من تنظيفه قليلا
عن طريق سحب القائمة معا.
لذلك نحن ترتيبها مؤشرات على أي من الجانبين.
وبعد ذلك سراح X ل العقدة التي تحتوي على 13،
ونحن لم يكسر السلسلة.
وهكذا فعلنا جيدة.
>> ملاحظة أخيرة هنا على القوائم المرتبطة.
لذلك كل من singly- وربطها مضاعف القوائم، كما رأينا،
دعم الإدراج فعال حقا وحذف العناصر.
يمكنك القيام الى حد كبير في وقت ثابت.
ماذا علينا أن نفعل لحذف عنصر ثانية فقط قبل؟
انتقلنا مؤشر واحد.
انتقلنا مؤشر آخر.
نحن اطلاق سراح تولى X-- ثلاث عمليات.
أنه يأخذ دائما ثلاث عمليات ل حذف هذا node-- لتحرير عقدة.
>> كيف يمكننا إدراج؟
حسنا، نحن فقط دائما تغير اتجاهها على بداية
إذا نحن إدخال بكفاءة.
لذلك نحن بحاجة إلى rearrange-- اعتمادا على ما اذا كان
وsingly- أو مرتبطة مضاعف القائمة، ونحن قد تحتاج إلى القيام بثلاثة
أو كحد أقصى أربع عمليات.
ولكن مرة أخرى، وانها دائما ثلاثة أو أربعة.
لا يهم كم عدد العناصر هي في قائمتنا،
انها دائما ثلاثة أو أربعة operations-- تماما مثل الحذف دائما
ثلاث أو أربع عمليات.
حان الوقت المستمر.
لذلك هذا أمر عظيم حقا.
>> مع المصفوفات، كنا نفعل شيء من هذا القبيل الإدراج النوع.
وربما كنت أذكر أن الإدراج النوع ليس خوارزمية الوقت ثابتة.
انها في الواقع مكلفة جدا.
لذلك هذا هو أفضل كثيرا لإدراج.
ولكن كما ذكرت في قائمة الفيديو المرتبطة منفردة،
لقد حصلت على الجانب السلبي هنا أيضا، أليس كذلك؟
لقد فقدنا القدرة على الوصول بشكل عشوائي العناصر.
لا نستطيع أن نقول، أريد العنصر رقم أربعة أو العنصر رقم 10 من قائمة مرتبطة
بنفس الطريقة ما في وسعنا تفعل ذلك مع مجموعة
أو نستطيع مجرد مؤشر مباشرة في العنصر لدينا المصفوفة.
>> وذلك في محاولة للعثور على عنصر في list-- مرتبطة
إذا كان البحث هو important-- قد يستغرق وقتا طويلا الآن الخطي.
كما يحصل قائمة لفترة أطول، فإنه قد يستغرق خطوة إضافية واحدة
لكل عنصر واحد في القائمة في أجل العثور على ما نبحث عنه.
ولذلك لا يوجد المفاضلة.
هناك قليلا من مؤيد والعنصر يخدع هنا.
>> والقوائم المرتبطة على نحو مضاعف ليست هي النوع الأخير من مزيج بنية البيانات
التي سنتحدث عنها، اتخاذ جميع المبنى الأساسي
كتل من C إلى وضع معا.
لأنه في الحقيقة، يمكننا حتى نفعل ما هو أفضل من هذا
لإنشاء بنية البيانات التي كنت قد تكون قادرة على البحث عن طريق
في وقت ثابت للغاية.
ولكن أكثر على ذلك في شريط فيديو اخر.
>> أنا دوغ ويد.
هذا هو CS50.