تنفيذ خوارزمياتArrayList
| English | العربية |
|---|---|
| shift/ʃɪft/ | إزاحة |
| delete/dɪˈliːt/ | احذف |
| insert/ˈɪnsɜːt/ | إدراج |
الإزالة المجاورة تكشف عن عنصر تم تجاوزه
- بدءًا من
[0, 0, 5]، قم بإزالة الفهرس 0 ثم زِد i. انتقل الصفر الثاني إلى الفهرس 0، لذلك تتجاهله الحلقة الأمامية وتترك[0, 5]. - بالنسبة لحلقة while الأمامية الموضحة هنا، ابقِ على نفس الفهرس بعد الإزالة وازدد فقط عند الاحتفاظ بعنصر. وبذلك يتم إزالة كلا الصفرين وينتهي مع
[5].
احتفظ بالفهرس الأمامي الحالي بعد الإزالة
- بعد
remove(i)، ينتقل كل عنصر لاحق بمقدار مكان واحد لليسار. إذا كان العنصر يشغل الآن موقع i، فهو لم يتم فحصه بعد؛ افحصه في التكرار التالي. - الحلقة أدناه تقبل قائمة غير فارغة من Integers غير فارغة وتزيل كل صفر في مكانه. تستخدم الحجم الحالي في كل تكرار ولا تقوم باستدعاء get على قائمة فارغة.
import java.util.ArrayList;
public class RemoveZeros {
public static void removeZeros(ArrayList<Integer> list) {
int i = 0;
while (i < list.size()) {
if (list.get(i) == 0) {
list.remove(i);
} else {
i++;
}
}
}
}
اشرح سبب توقف هذه الحلقة
- في كل تكرار إما يتم إزالة عنصر واحد ويقلل الحجم، أو يُحتفظ بعنصر واحد ويزيد i. وبالتالي
size() - i، وهو عدد المواقع المتبقية للفحص، ينقص بمقدار واحد في كل تكرار. - بدءًا من
[0, 0, 5]، تكون الحالات[0, 5]عند i=0،[5]عند i=0، ثم[5]عند i=1. الشرط النهائي يكون خاطئًا، لذا لا يحدث الوصول خارج الحدود.
تتبع الحلقة الخلفية قاعدة مختلفة
- يبدأ الحلقة العكسية من آخر فهارس موجودة:
for (int i = list.size() - 1; i >= 0; i--). أزل العناصر المتطابقة معremove(i)؛ يكون الفهرس i التالي دائمًا أقل بمقدار واحد. - الحذف عند i يُزيح فقط الفهارس اللاحقة، التي تم فحصها بالفعل. العناصر غير المفحوصة السابقة تحتفظ بفهارسها، لذا فإن التناقص بعد الإزالة صحيح هنا؛ "لا تقدم أبدًا بعد الإزالة" ليس قاعدة عالمية.
اختر تحديث فهرس يتوافق مع اتجاه التجول. في حلقة while الأمامية، ابقَ بعد الإزالة؛ في حلقة for العكسية، استمر في التناقص. التغييرات الهيكلية المباشرة أثناء حلقة محسّنة هي نمط غير آمن منفصل، حتى عندما لا يظهر استثناء فشل سريع.
في حلقة while الأمامية الموضحة هنا، قدّم i فقط عندما...
بعد remove(i) ، ينتقل العنصر التالي إلى موقع i — فلا تتخطّه.
حلقة Aمامية بدائية على [0, 0, 5] تقوم بالحذف عند i=0 ثم تزيدها تتخطى الصفر التالي.
ينزلق الصفر المتبقي إلى الفهرس 0، لكن الاختبار التالي يكون عند الفهرس 1. تستخدم الحلقة الخلفية قاعدة فهرس صحيحة مختلفة.
بديل للإزالة في المكان يتجنب الإزاحة هو...
إضافة العناصر المحتفظ بها إلى قائمة فارغة يتجاوز مشكلة الإزاحة.
تعيد خوارزمياتArrayList استخدام أنماط المصفوفة عبر...
استبدل مصفوفة [] وlength بـ get(i) وsize() .
طبيعةArrayList القابلة للتوسع تسمح لك بإدراج وحذف العناصر، بعكس المصفوفة الثابتة.
تغيير add وremove حجم القائمة.
يجب أن تبقى حلقة الإزالة الخلفية التي تبدأ من size()-1 عند نفس الفهرس بعد كل حذف.
خطأ: العناصر التي لم يتم فحصها سابقاً تحتفظ بفهارسها، لذا تنخفض الحلقة الخلفية بشكل طبيعي.
قم بإنشاء قائمة جديدة عندما يجب أن يبقى الأصل
- للحفاظ على القائمة الأصلية، أنشئ نتيجة جديدة وأضف كل عنصر غير صفري أثناء قراءة الأصل. هذا يحافظ على التسلسل الأصلي وحجمه دون تغيير؛ وهو يستخدم مساحة تخزين إضافية للقائمة.
- بالنسبة لقوائم الكائنات القابلة للتغيير، لا يقوم نسخ المراجع المحفوظة بتكرار تلك الكائنات. قد تظل البنية الجديدة للقائمة تشترك في كائنات عناصرها مع الأصل؛ اميز بين هوية القائمة وهوية العناصر.
الإزالة الأمامية تحافظ على الفهرس التالي بعد الحذف.
يتم التحقق من صفرين متجاورين عند الفهرس 0 قبل الاحتفاظ بـ 5.
تحقق من الحالات التي تكشف عن الخوارزمية
- اختبر قائمة فارغة، جميع الأصفار، لا أصفار، أصفار متجاورة وصفر في آخر فهرس. بالنسبة للإزالة الموضعية، تلاحظ المراجع الأخرى لنفس القائمة تغييرها؛ تترك النتيجة الجديدة هذه البنية الأصلية سليمة.
- يمكن لـ ArrayList إدراج أو حذف العناصر؛ يمكن لهذه العمليات أن تزيح الفهارس اللاحقة. قد تُرجع عملية البحث فهرسًا مُجَدَّدًا أو -1 عند الغياب؛ تتطلب القيمة القصوى سياسة صريحة للقوائم الفارغة. يساعد إعادة استخدام أنماط المصفوفات من خلال get/size، لكن كل خوارزمية تحتاج إلى حدودها وعقدها الخاص.
الإزالة تُزيح المؤشرات. اشرح أي العناصر بقيت دون فحص واختر المؤشر التالي بناءً على ذلك. كلتا النمطين مقبولان: الأمامي 'بقاء أو زيادة' والخلفي 'تناقص'. قائمة جديدة من العناصر المحفوظة تحافظ على البنية الأصلية لكنها قد تشترك في نفس الكائنات.
Order the states for the corrected removal loop on [0, 0, 5].
Each removal rechecks the shifted value; keeping 5 finally advances the index.
كم عدد استدعاءات get التي تقوم بها طريقة removeZeros الأمامية الموضحة على قائمة فارغة؟
الشرط الأولي 0 < 0 غير صحيح، لذا لا يحدث أي استدعاء get.