الدرس 44: الهياكل ذاتية المرجعية (مقدمة في القوائم المرتبطة)

الهيكل ذاتي المرجعية (Self-referential structure) هو هيكل يحتوي على عضو واحد على الأقل هو مؤشر لهيكل آخر من نفس النوع.

تعد هذه الهياكل لبنات البناء لهياكل البيانات الديناميكية مثل القوائم المرتبطة (Linked Lists) والأشجار والرسوم البيانية.

تعريف الهيكل

يجب أن يتضمن الهيكل حقل بيانات وحقل مؤشر.

c struct Node { int data; // البيانات المخزنة في هذه العقدة struct Node *next; // مؤشر للعقدة التالية في القائمة };

ملاحظة: لا يمكن للهيكل أن يحتوي على الهيكل نفسه كعضو (مثل struct Node n;) لأن ذلك سيتطلب ذاكرة لانهائية. يجب أن يكون مؤشراً لنوع الهيكل.

مفهوم القائمة المرتبطة

القائمة المرتبطة هي تسلسل من العقد حيث يتم ربط كل عقدة بالتالية عبر مؤشر.

1. مؤشر خاص (head أو start) يشير إلى العقدة الأولى.
2. كل عقدة تشير إلى العقدة التالية.
3. يتم تعيين المؤشر في العقدة الأخيرة إلى NULL للإشارة إلى نهاية القائمة.

مثال (الربط المفاهيمي)

c struct Node *head, *node1, *node2;

// 1. تخصيص الذاكرة للعقد node1 = (struct Node *)malloc(sizeof(struct Node)); node2 = (struct Node *)malloc(sizeof(struct Node));

// 2. تعيين البيانات node1->data = 10; node2->data = 20;

// 3. ربطهما ببعض node1->next = node2; node2->next = NULL; // نهاية القائمة

head = node1; // البداية من هنا

لقد أنشأنا قائمة: HEAD -> [10 | addr_2] -> [20 | NULL].