مقدمة عن بنى المعطيات
بنية المعطيات (Data Structure) هي طريقة لـتنظيم وتخزين البيانات في الذاكرة بحيث يمكن الوصول إليها وتعديلها بكفاءة.
ملاحظة هامة: اختيار بنية المعطيات المناسبة يعتمد على طبيعة المشكلة ونوع العمليات التي سنحتاج لتنفيذها.
تصنيف بنى المعطيات الأساسية
| الأنواع البدائية (Primitive) | الأنواع غير البدائية (Non-Primitive) |
|---|---|
| Integer (عدد صحيح) | مصفوفة (Array) |
| Float (عدد عشري) | قائمة (List) |
| Character (حرف) | مكدس (Stack) |
| Pointer (مؤشر) | طابور (Queue) |
| شجرة (Tree) | |
| رسم بياني (Graph) |
التخصيص الديناميكي للذاكرة
الذاكرة في الحاسوب تنقسم إلى عدة أجزاء رئيسية:
Segment التعليمات (Code)
يحتوي على كود البرنامج
Segment البيانات (Data)
المتغيرات العامة والثوابت
المكدس (Stack)
المتغيرات المحلية ومتغيرات الدوال
الكومة (Heap)
التخصيص الديناميكي للذاكرة
أوامر التخصيص والتحرير
// التخصيص الديناميكي في C++
int *p = new int; // إنشاء متغير جديد
*p = 10; // تعيين قيمة
delete p; // تحرير الذاكرة
// التخصيص الديناميكي في C
int *p = (int*)malloc(sizeof(int)); // إنشاء متغير جديد
*p = 10; // تعيين قيمة
free(p); // تحرير الذاكرة
int *p = new int; // إنشاء متغير جديد
*p = 10; // تعيين قيمة
delete p; // تحرير الذاكرة
// التخصيص الديناميكي في C
int *p = (int*)malloc(sizeof(int)); // إنشاء متغير جديد
*p = 10; // تعيين قيمة
free(p); // تحرير الذاكرة
أهمية تحرير الذاكرة
عند استخدام التخصيص الديناميكي، يجب دائمًا تحرير الذاكرة بعد الانتهاء من استخدامها لتجنب تسرب الذاكرة (Memory Leaks).
مقارنة المصفوفات والقوائم المترابطة
| المعيار | المصفوفة (Array) | القائمة المترابطة (Linked List) |
|---|---|---|
| وقت الوصول | O(1) - وصول عشوائي مباشر | O(n) - وصول تسلسلي |
| الحجم | ثابت (يحدد عند التصميم) | ديناميكي (يتغير أثناء التنفيذ) |
| الإدراج والحذف | غير فعال (يتطلب إزاحة العناصر) | فعال (لا يتطلب إزاحة العناصر) |
| تخزين الذاكرة | متجاور (Contiguous) | غير متجاور (Non-Contiguous) |
| هدر المساحة | ممكن (إذا لم تستخدم المساحة بالكامل) | لا يوجد |
| الاستخدام الأمثل | عندما يكون الحجم معروفًا مسبقًا | عندما يكون الحجم متغيرًا وغير معروف |
تمثيل القوائم المترابطة
تتكون القائمة المترابطة من عقد (Nodes) مرتبطة ببعضها بواسطة مؤشرات.
هيكل العقدة (Node Structure)
// هيكل العقدة في القائمة المترابطة
struct Node {
int data; // القيمة المخزنة
Node* next; // مؤشر للعقدة التالية
};
struct Node {
int data; // القيمة المخزنة
Node* next; // مؤشر للعقدة التالية
};
تمثيل القائمة المترابطة
1
→
2
→
3
NULL
Head: مؤشر إلى أول عقدة في القائمة
Tail: مؤشر إلى آخر عقدة في القائمة (اختياري)
العمليات الأساسية على القوائم المترابطة
1. طباعة القائمة (Print)
void SLinkedList::printList() {
Node *curr = head; // بدء من أول عقدة
while (curr != NULL) { // حتى نهاية القائمة
cout << curr->data << " "; // طباعة البيانات
curr = curr->next; // الانتقال للعقدة التالية
}
cout << "\nLength=" << length; // طباعة طول القائمة
}
Node *curr = head; // بدء من أول عقدة
while (curr != NULL) { // حتى نهاية القائمة
cout << curr->data << " "; // طباعة البيانات
curr = curr->next; // الانتقال للعقدة التالية
}
cout << "\nLength=" << length; // طباعة طول القائمة
}
2. البحث في القائمة (Search)
// البحث عن عقدة بحسب القيمة
Node* SLinkedList::findNode(int x) {
Node *curr = head; // بدء من أول عقدة
while (curr != NULL) {
if (curr->data == x) // إذا وجدت القيمة
return curr; // إرجاع العقدة
curr = curr->next; // الانتقال للعقدة التالية
}
return NULL; // القيمة غير موجودة
}
Node* SLinkedList::findNode(int x) {
Node *curr = head; // بدء من أول عقدة
while (curr != NULL) {
if (curr->data == x) // إذا وجدت القيمة
return curr; // إرجاع العقدة
curr = curr->next; // الانتقال للعقدة التالية
}
return NULL; // القيمة غير موجودة
}
طباعة القائمة المترابطة
عملية طباعة القائمة المترابطة تتطلب اجتياز جميع العقد من البداية إلى النهاية.
كود الطباعة الكامل
void SLinkedList::printList() {
if (head == NULL) {
cout << "القائمة فارغة!" << endl;
return;
}
Node *curr = head;
cout << "عناصر القائمة: ";
while (curr != NULL) {
cout << curr->data << " → ";
curr = curr->next;
}
cout << "NULL" << endl;
cout << "طول القائمة: " << length << endl;
}
if (head == NULL) {
cout << "القائمة فارغة!" << endl;
return;
}
Node *curr = head;
cout << "عناصر القائمة: ";
while (curr != NULL) {
cout << curr->data << " → ";
curr = curr->next;
}
cout << "NULL" << endl;
cout << "طول القائمة: " << length << endl;
}
تمثيل مرئي لعملية الطباعة
1
→
2
→
3
NULL
المخرجات: 1 → 2 → 3 → NULL
البحث في القائمة المترابطة
عملية البحث تتطلب اجتياز القائمة حتى العثور على القيمة المطلوبة أو الوصول لنهاية القائمة.
كود البحث الكامل
Node* SLinkedList::search(int value) {
Node *curr = head;
int position = 1;
while (curr != NULL) {
if (curr->data == value) {
cout << "تم العثور على القيمة " << value
<< " في الموضع " << position << endl;
return curr;
}
curr = curr->next;
position++;
}
cout << "القيمة " << value << " غير موجودة في القائمة" << endl;
return NULL;
}
Node *curr = head;
int position = 1;
while (curr != NULL) {
if (curr->data == value) {
cout << "تم العثور على القيمة " << value
<< " في الموضع " << position << endl;
return curr;
}
curr = curr->next;
position++;
}
cout << "القيمة " << value << " غير موجودة في القائمة" << endl;
return NULL;
}
إدراج العناصر في القائمة المترابطة
حالات الإدراج المحتملة:
- الإدراج في قائمة فارغة
- الإدراج في بداية القائمة
- الإدراج في منتصف القائمة
- الإدراج في نهاية القائمة
كود الإدراج الكامل
void SLinkedList::insertNode(int x) {
Node *newNode = new Node(); // إنشاء عقدة جديدة
newNode->data = x; // تعيين القيمة
// الحالة 1: القائمة فارغة
if (head == NULL) {
head = tail = newNode;
newNode->next = NULL;
}
// الحالة 2: الإدراج في البداية
else if (x < head->data) {
newNode->next = head;
head = newNode;
}
// الحالة 3 و 4: الإدراج في الوسط أو النهاية
else {
Node *curr = head, *prev = NULL;
// البحث عن مكان الإدراج
while (curr != NULL && curr->data < x) {
prev = curr;
curr = curr->next;
}
// الإدراج
prev->next = newNode;
newNode->next = curr;
// إذا كانت نهاية القائمة
if (curr == NULL) tail = newNode;
}
length++; // زيادة طول القائمة
}
Node *newNode = new Node(); // إنشاء عقدة جديدة
newNode->data = x; // تعيين القيمة
// الحالة 1: القائمة فارغة
if (head == NULL) {
head = tail = newNode;
newNode->next = NULL;
}
// الحالة 2: الإدراج في البداية
else if (x < head->data) {
newNode->next = head;
head = newNode;
}
// الحالة 3 و 4: الإدراج في الوسط أو النهاية
else {
Node *curr = head, *prev = NULL;
// البحث عن مكان الإدراج
while (curr != NULL && curr->data < x) {
prev = curr;
curr = curr->next;
}
// الإدراج
prev->next = newNode;
newNode->next = curr;
// إذا كانت نهاية القائمة
if (curr == NULL) tail = newNode;
}
length++; // زيادة طول القائمة
}
تمثيل مرئي لعملية الإدراج
1
→
3
→
4
NULL
بعد إدراج القيمة 2:
1
→
2
→
3
→
4
NULL
حذف العناصر من القائمة المترابطة
خطوات الحذف:
- البحث عن العقدة المراد حذفها
- تحديث المؤشرات للعقد المحيطة <3>تحرير الذاكرة الخاصة بالعقدة المحذوفة
كود الحذف الكامل
void SLinkedList::deleteNode(int x) {
if (head == NULL) return; // القائمة فارغة
Node *curr = head, *prev = NULL;
// الحذف من البداية
if (head->data == x) {
head = head->next;
if (head == NULL) tail = NULL; // إذا أصبحت فارغة
delete curr;
}
else {
// البحث عن العقدة المراد حذفها
while (curr != NULL && curr->data != x) {
prev = curr;
curr = curr->next;
}
if (curr != NULL) { // إذا وجدت العقدة
prev->next = curr->next; // تجاوز العقدة المحذوفة
if (curr == tail) tail = prev; // إذا كانت آخر عقدة
delete curr; // تحرير الذاكرة
}
}
length--; // تقليل طول القائمة
}
if (head == NULL) return; // القائمة فارغة
Node *curr = head, *prev = NULL;
// الحذف من البداية
if (head->data == x) {
head = head->next;
if (head == NULL) tail = NULL; // إذا أصبحت فارغة
delete curr;
}
else {
// البحث عن العقدة المراد حذفها
while (curr != NULL && curr->data != x) {
prev = curr;
curr = curr->next;
}
if (curr != NULL) { // إذا وجدت العقدة
prev->next = curr->next; // تجاوز العقدة المحذوفة
if (curr == tail) tail = prev; // إذا كانت آخر عقدة
delete curr; // تحرير الذاكرة
}
}
length--; // تقليل طول القائمة
}
تمثيل مرئي لعملية الحذف
1
→
2
→
3
NULL
بعد حذف القيمة 2:
1
→
3
NULL
القوائم الدائرية (Circular Linked Lists)
في القوائم الدائرية، آخر عقدة تشير إلى أول عقدة بدلاً من NULL.
1
→
2
→
3
↻
الإدراج في القائمة الدائرية
void insertFront(Node *newNode) {
if (tail == NULL) { // القائمة فارغة
newNode->next = newNode; // تشير إلى نفسها
tail = newNode;
}
else {
newNode->next = tail->next; // العقدة الجديدة تشير إلى أول عقدة
tail->next = newNode; // آخر عقدة تشير إلى الجديدة
}
}
if (tail == NULL) { // القائمة فارغة
newNode->next = newNode; // تشير إلى نفسها
tail = newNode;
}
else {
newNode->next = tail->next; // العقدة الجديدة تشير إلى أول عقدة
tail->next = newNode; // آخر عقدة تشير إلى الجديدة
}
}
القوائم المضاعفة (Doubly Linked Lists)
في القوائم المضاعفة، كل عقدة تحتوي على مؤشرين: واحد للعقدة التالية وواحد للعقدة السابقة.
←
1
→
←
2
→
←
3
→
هيكل العقدة في القوائم المضاعفة
struct Node {
int data; // القيمة المخزنة
Node* next; // مؤشر للعقدة التالية
Node* prev; // مؤشر للعقدة السابقة
};
int data; // القيمة المخزنة
Node* next; // مؤشر للعقدة التالية
Node* prev; // مؤشر للعقدة السابقة
};
الخلاصة والتوصيات
متى نستخدم القوائم المترابطة؟
- عندما يكون حجم البيانات غير معروف مسبقًا
- عند الحاجة إلى عمليات إدراج/حذف متكررة وسريعة
- عندما لا نحتاج إلى وصول عشوائي للبيانات
- عند العمل مع كميات كبيرة من البيانات
متى نفضل استخدام المصفوفات؟
- عندما يكون حجم البيانات معروفًا وثابتًا
- عند الحاجة إلى وصول عشوائي سريع (O(1))
- عند العمل مع بيانات حجمها صغير أو متوسط
- عندما تكون الذاكرة المتجاورة مطلوبة
نصيحة أخيرة: اختيار بنية البيانات المناسب يعتمد على متطلبات التطبيق ونوع العمليات التي ستتم على البيانات.