القوائم المرتبطة (Linked lists)
العقد المتصلة بالمؤشرات
- القائمة المرتبطة هي سلسلة من الهياكل الصغيرة تسمى العقد، مبعثرة في الرصيف (heap).
- كل عقدة تحمل قيمة ومؤشراً إلى العقدة التالية. اتبع المؤشرات لتتجول في القائمة.
- على عكس المصفوفة، يمكن للقائمة أن تنمو بعقدة واحدة في كل مرة دون تحريك البقية.
هيكل ذاتي الإرجاع
- العقدة هي هيكل يحتوي على مؤشر إلى نوعها الخاص:
struct Node { int data; struct Node *next; };—dataهي القيمة،nextيشير إلى العقدة التالية.- هذا معطى لك كـ
Nodeفي كل ملف بدء.nextالعقدة الأخيرة هوNULL.
الرأس والنهاية NULL
- مؤشر واحد، الـ رأس، يشير إلى العقدة الأولى. منه تصل إلى الباقي.
- آخر عقدة تشير إلى
NULL، الذي يمثل نهاية القائمة. - القائمة الفارغة هي ببساطة
head == NULL— لا توجد عقد على الإطلاق.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
إضافة عقدة في البداية
- للإضافة في البداية، اصنع عقدة جديدة، وجه
nextالخاص بها نحو الرأس القديم، وأرجع العقدة الجديدة كرأس جديد. - هذا سريع — لا يلمس أي عقدة أخرى.
- بما أن الرأس يتغير، فإن الدالة ترجع الرأس الجديد، والمُدْعِي يحفظه.
أخطاء شائعة
- لا تفقد مؤشر
headأبداً، أو ستصبح القائمة بأكملها غير قابلة للوصول. - قم بإفراغ كل عقدة؛ العقدة الأخيرة تشير إلى
NULL.
الآن جرب بنفسك
- تجول في قائمة باستخدام مؤشر
curوcur = cur->next، متوقفاً عندNULL. - العقد الجديدة تأتي من
malloc(sizeof(Node))؛ الكاشف يحرر القائمة. لا اكتبmain.
العقد والمؤشرات
كل عقدة تشير إلى التالية؛ الإدراج/الحذف يتم عن طريق إعادة الربط.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل int length(const Node *head) لعد العقد في القائمة (0 للقائمة الفارغة). تحرك مع ->next حتى NULL. نوع الـ Node مُعطى. لا تكتب a main.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل int sum_list(const Node *head) لإرجاع مجموع كل data لكل عقدة (0 للقائمة الفارغة). نوع الـ Node مُعطى. لا تكتب a main.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل Node *push_front(Node *head, int value) لإنشاء عقدة جديدة (مع malloc)، وتوجيه next منها نحو الـ head القديم، وإرجاعها كرأس جديد. المتحقق يحرر القائمة. لا تكتب a main.
اضغط تشغيل لرؤية المخرجات هنا.