بُنى المعطيات - القوائم المرتطبة

تعد القوائم المرتبطة إحدى بُنى المعطيات الشهيرة و لعل أقوى ميزات هذه البنية هي الحريّة المطلقة التي تتيحها في التعامل مع البيانات بأي ترتيب نرغب به , خُذ المثال التالي

لو كان لدينا مصفوفة بحجم 1000 عنصر تحتوي على قيم معينة و في لحظة من لحظات تنفيذ البرنامج احتجنا أن نقوم بإدخال عنصر إضافي في المصفوفة بين العنصر الـ 23 و الـ 24 دون حذفهما فإننا لن نستطيع القيام بذلك ببساطة , و إن أمكننا القيام بذلك فإننا سنحتاج إلى إجرائية طويلة و معقّدة للقيام بهذه العمليّة حيث سنحتاج لاستخدام الذاكرة بشكل ديناميكي و زيادة عدد عناصر المصفوفة بمقدار واحد ثم سنحتاج لإجراء عمليّة إزاحة لكافة العناصر بين الموضع 23 و الموضع الأخير منها و ... و .... و , بينما الأمر أبسط بكثير عند استعمال قائمة مرتبطة .

تعتمد القوائم المرتبطة على مبدأ بسيط جدّاً هو أنّ كل عنصر في هذه القائمة سيقسم إلى قسمين

القسم الأوّل Value : يحتوي على القيمة الفعليّة لهذا العنصر .

القسم الثاني Next : يحتوي على مؤشّر يشير إلى العنصر التالي .

و كما ترى فإنّك تستطيع الآن التلاعب بموضع كل عنصر بسهولة عن طريق القسم Next دون قيود تفرض تسلسل معيّن ; انظر الشكل

لاحظ كيف تشير خانة Next في كل عنصر إلى العنصر الذي يليه ببساطة شديدة , ما سنتعلّمه اليوم هو كيفية بناء بنية المعطيات هذه .

سأستخدم لغة البرمجة C# في الشرح لأسباب أذكرها في نهاية الموضوع .

الآن حجر الأساس الذي سنبني عليه بنية معطياتنا هذه هو العنصر الذي يدعى بالعقدة (Node) و بالتالي نحتاج لبناء صف يمثّل هذه العقدة كما يلي :

class Node
	{
		int value;
		Node next;
		public Node(int v, Node n)
		{
			this.value = v;
			this.next = n;
		}

		public Node(int val)
		{
			this.value = val;
			this.next = null;
		}

		public void setValue(int val)
		{
			this.value = val;
		}
		public int getValue()
		{
			return this.value;
		}
		public void setNext(Node n)
		{
			this.next = n;
		}
		public Node getNext()
		{
			return this.next;
		}
	}

الآن نستطيع القول أن الجزء الشاق من هذا الموضوع قد انتهى و ما تبقّى هو محض بناء لدوال تستفيد من هذا الصف الذي عرفّناه أعلاه .

دالة إضافة عنصر جديد إلى القائمة :

هذه الدالة تقوم ببساطة بأخذ قيمة العنصر الجديد و العقدة التي نريدها أن تمثّل العقدة السابقة له كبارمترات لها و تقوم بإضافة العقدة الجديدة بناءً عليها , و بالتالي سيكون بناؤها كما يلي :

public void insert(Node pos,int val)
{
	Node temp= new Node(val,pos.getNext());
	pos.setNext(temp);
}

دالة حذف عنصر من القائمة :

بكل بساطة ستقوم هذه الدالة بتغيير قيمة next للعنصر الذي قبل العقدة المراد حذفها و تجعلها مساويةً للعقدة التي تلي العقدة المراد حذفها و بالتالي تصبح العقدة المراد حذفها غير موجودة ضمن القائمة , و يمكن تمثيل العملية ببساطة كما يلي :

public void delete(Node pos)
{
	Node temp= new Node(val,pos.getNext());
	if(pos.getNext()!=null && pos.getNext().getNext()!=null)
		pos.setNext(pos.getNext().getNext());
}

دالة طباعة كامل عناصر القائمة :

لطباعة كل عناصر القائمة يكفي أن ندور على هذه العناصر عنصراً عنصراً باستخدام أي نوع من أنواع الحلقات و نقوم بطباعة القيم خُذ مثلاً .

Public void printAll(Node p)
{
	While(p!=null)
	{
		Console.writeLine(p.getValue());
		P=p.getNext();
	}

}

و الآن و بعد أن انتهى درسنا تقريباً يبقى أن أوضّح لماذا استعملت لغة C# هنا و لم أستعمل C++ التي كنت استعملها في الدروس السابقة

كون الدرس تعليمي أولاً و أخيراً لم أرغب في الدخول بتعقيدات استعمال المؤشّرات التي ما كانت إلا لتعقّد الموضوع على الرغم من بساطته ناهيك عن كونها فرصة جيّدة لاكتشاف إحدى أهم مزايا البرمجة غرضيّة التوجه و أعني (إعادة الاستعمال و التغليف) التي تجلّت واضحةً في استعمالنا للصف Node عبر واجهة الاستعمال Set و Get .

هناك ملاحظة أخيرة : مهما كانت العمليات التي ترغب بتطبيقها على بنية المعطيات هذه فإنها لن تتجاوز فكرة دالة الطباعة التي أوردتها هنا .

تم الدرس بحمد الله

لا تنسونا من صالح الدعاء

أخوكم :

مختار السيد صالح