[Powered by Google Translate] في البرمجة، ونحن غالبا ما تحتاج لتمثيل قوائم القيم، مثل أسماء الطلاب في قسم أو على درجات عن آخر مسابقة. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تعبر ليست سيئة للغاية، ولكن ماذا عن إدراج؟ دعونا نقول أننا نريد أن إدراج عدد صحيح في موقف 4th في قائمة عدد صحيح. وهذا هو بين العقد الحالي 3rd و 4th. مرة أخرى، علينا أن تجتاز قائمة فقط على الوصول إلى العنصر 3، واحدة بعد ادخال نحن. لذلك، فإننا نخلق مؤشر المجنزرة مرة أخرى لاجتياز القائمة، تحقق مما إذا المؤشر الرئيسي لدينا هو باطل، وإذا لم تكن كذلك، لدينا نقطة مؤشر المجنزرة في عقدة الرأس. لذلك، نحن في العنصر 1. علينا ان نمضي قدما إلى الأمام 2 أكثر العناصر قبل أن نتمكن من إدراج، حتى نتمكن من استخدام حلقة For كثافة العمليات ط = 1، وأنا <3، وأنا + + والتكرار في كل من الحلقة، تقدم مؤشر لدينا حفارات إلى الأمام بمقدار 1 عقدة عن طريق فحص إذا حقل العقدة الحالية القادم باطل، وإذا لم تكن كذلك، حرك المؤشر لدينا حفارات إلى العقدة المقبل من خلال وضع المؤشر عليه يساوي العقدة الحالية القادم. لذلك، لدينا حلقة منذ تقول للقيام بذلك مرتين، لقد وصلنا إلى عقدة 3، ومرة واحدة وصلت لدينا مؤشر المجنزرة عقدة بعد الذي نريد أن إدراج عدد صحيح الجديد، كيف يمكننا فعلا القيام بما إدراج؟ 

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

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

لذلك، لتبسيط هذا، دعنا نقول أن لدينا عقد أول 4 وتسمى A، B، C، D و، مع الأسهم التي تمثل سلسلة من المؤشرات التي تربط العقد. لذلك، نحن بحاجة إلى إدراج عقدة الجديد في العقد بين C و D. من المهم جدا أن نفعل ذلك في حق النظام، وسوف تظهر لك لماذا. 

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

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

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

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

اسمي جاكسون Steinkamp، وهذا هو CS50.