هياكل البيانات
مقدمة
البرنامج = هيكل بيانات + خوارزمية. تعلمنا كيف ينفذ المعالج التعليمات وكيف يدير نظام التشغيل الموارد. لكن الكائن الأساسي الذي تعالجه البرامج هو البيانات -- معلومات المستخدمين، قوائم المنتجات، العلاقات الاجتماعية... كيف تُنظم هذه البيانات في الذاكرة يحدد مباشرة سرعة البرنامج. الإجابة عادةً في اختيار هيكل البيانات.
ماذا ستتعلم في هذه المقالة؟
- حدس: رؤية متطلب والتفكير تلقائياً في هيكل البيانات المناسب
- منظور الأداء: تشخيص ما إذا كان عنق الزجاجة في الهيكل أم الخوارزمية
- تفكير المقايضة: فهم "مساحة مقابل وقت" و"وقت مقابل مساحة"
- قراءة الكود: HashMap، Stack، Queue لن تكون مصطلحات غريبة بعد الآن
| الفصل | المحتوى | المفهوم الأساسي |
|---|---|---|
| الفصل 1 | نظرة عامة | أربع فئات هياكل البيانات |
| الفصل 2 | الهياكل الخطية | المصفوفات، القوائم المرتبطة، المكدسات، الطوابير |
| الفصل 3 | جداول التجزئة | دالة التجزئة، معالجة التصادم، بحث O(1) |
| الفصل 4 | هياكل الأشجار | الأشجار الثنائية، نظام الملفات، DOM |
| الفصل 5 | هياكل الرسوم البيانية | رسوم موجهة، غير موجهة، خوارزميات الاجتياز |
| الفصل 6 | مقارنة الأداء | التعقيد الزمني والمكاني |
| الفصل 7 | دليل الاختيار | تحليل السيناريوهات |
1. نظرة عامة: ما هي هياكل البيانات؟
تخيل أنك تنظم مجموعة كتب:
- مكدسة على الأرض: البحث كتاباً بكتاب -- تخزين بدائي
- مرقمة على رف: الذهاب مباشرة للموقع -- مصفوفة
- مصنفة في خزائن: تحديد الخزانة أولاً -- جدول تجزئة
- مرتبة على رفوف متعددة: استبعاد النصف كل مرة -- شجرة
هياكل البيانات هي "طريقة تنظيم" البيانات -- تحدد كيف تُخزن وتُبحث وتُعدل.
Data Structure OverviewChoose a data organization model for each scenario
Data structures are like ways to organize a room: clothes in a wardrobe, books on shelves, and small items in drawers.
Linear structures
Data arranged in order, like a row of books
ArrayLinked listStackQueue
Hash structures
Fast lookup through a key
Hash tableDictionarySet
Tree structures
Hierarchy, like a family tree
Binary treeB-treeHeap
Graph structures
Complex relationship networks
Directed graphUndirected graphNetwork graph
Linear structures
Features
One-to-one relationship between elements
A clear before-and-after order
Can use contiguous storage or linked storage
Use Cases
Arrays: list data
Store ordered data such as student scores or product prices
Stacks: undo operations
Text editor undo history, last in first out
Queues: task scheduling
Print queues and task queues, first in first out
Operation Complexity
OperationAverage time
Access elementO(1)
Insert/deleteO(n)
Everyday Analogy
Like train cars connected in order
To find car 5, count directly to it; to insert a new car, you need to break and reconnect links.
جميع الهياكل تُصنف في أربع فئات:
| النوع | العلاقة | أمثلة | تشبيه |
|---|---|---|---|
| خطي | واحد لواحد | مصفوفة، قائمة، مكدس، طابور | عربات القطار |
| تجزئة | مفتاف←قيمة | جدول تجزئة، قاموس | بطاقات فهرس المكتبة |
| شجرة | واحد لكثير | شجرة ثنائية، B-tree | شجرة العائلة |
| رسم بياني | كثير لكثير | رسم موجه، غير موجه | خريطة المترو |
2. الهياكل الخطية: التنظيم الأساسي
Four Forms of Linear StructuresHow arrays, linked lists, stacks, and queues differ
ArrayContiguous memory, indexed access
0
10
1
25
2
33
3
47
4
59
5
62
✓ Contiguous memory | ✓ Fast access (O(1)) | ✗ Slow insert/delete (O(n))
Operation Comparison
| Data structure | Access | Insert | Delete | Feature |
|---|---|---|---|---|
| 📊 Array | O(1) fast | O(n) slow | O(n) slow | Fixed size |
| 🔗 Linked list | O(n) slow | O(1) fast | O(1) fast | Variable size |
| 🥞 Stack | O(n) | O(1) fast | O(1) fast | One-end operations |
| 🚶 Queue | O(n) | O(1) fast | O(1) fast | Two-end operations |
Real-World Uses
List data
Student scores or product price lists
Image processing
Pixel matrix storage
Charts
Data ordered by time
2.1 مصفوفة مقابل قائمة مرتبطة
| البُعد | مصفوفة | قائمة مرتبطة |
|---|---|---|
| الذاكرة | كتلة متصلة | متفرقة، مربوطة بمؤشرات |
| الوصول للعنصر n | مباشر، O(1) | من البداية، O(n) |
| الإدراج في المنتصف | نقل الخلفي، O(n) | تغيير مؤشرات، O(1) |
| الحجم | ثابت عند الإنشاء | ينمو ديناميكياً |
2.2 المكدس والطابور
| الهيكل | القاعدة | تشبيه | أين يظهر؟ |
|---|---|---|---|
| مكدس | LIFO (آخر يدخل، أول يخرج) | كومة صحون | مكدس الاستدعاءات، رجوع المتصفح |
| طابور | FIFO (أول يدخل، أول يخرج) | طابور شراء | طابور المهام، طابور الرسائل |
3. جدول التجزئة: البحث الأسرع
Hash Tables: Super-Fast LookupFind data directly through a key
A hash table is like a library index card: instead of searching shelf by shelf, you use the index to find the book location directly.
Store data
Hashing process
Input key
apple
↓
Hash function
hash(key) % 10
↓
Array index
0
Hash table
0
apple: apple
1
Empty
2
Empty
3
Empty
4
Empty
5
Empty
6
orange: orange
7
Empty
8
Empty
9
banana: banana
Performance Comparison
Hash table lookup
O(1)
Found instantly
Array lookup
O(n)
Requires traversal
Binary search
O(log n)
Requires sorted data
Common Uses
User table (user ID → profile)
Shopping cart (product ID → quantity)
Cache system (URL → page content)
Dictionary (word → definition)
3.1 المبدأ
- تعطي مفتاحاً (مثال: "apple")
- دالة التجزئة تحسب رقماً (مثال:
hash("apple") = 3) - تذهب مباشرة للموضع 3 -- بدون اجتياز
3.2 تصادمات التجزئة
مفتاحان قد يعطيان نفس الفهرس -- هذا تصادم تجزئة.
| الحل | المبدأ |
|---|---|
| التسلسل | قائمة مرتبطة في نفس الموضع |
| العنونة المفتوحة | البحث عن الموضع الفارغ التالي |
4. هياكل الأشجار: التعبير عن التسلسل الهرمي
Tree Structures: Representing HierarchiesAn organization model like a family tree
Choose a tree type:
Tree Structure Features
Hierarchy
Nodes have one-to-many parent-child relationships
Single root node
Except for the root, each node has exactly one parent
Efficient lookup
Binary search tree lookup is O(log n)
Multiple traversals
Preorder, inorder, postorder, and level-order traversal
Use Cases
File systems
Hierarchical organization of folders and files
HTML DOM
Nested structure of web page elements
Organization charts
Company management hierarchy
Decision trees
Classification algorithms in machine learning
4.1 شجرة البحث الثنائية
قاعدة: الأصغر يسار، الأكبر يمين. بحث O(log n).
4.2 الأشجار المتوازنة
| النوع | الاستراتيجية | التطبيق |
|---|---|---|
| AVL | توازن صارم | بحث متكرر |
| أحمر-أسود | توازن تقريبي | Java TreeMap، نواة Linux |
| B-tree | توازن متعدد المسارات | فهارس قواعد البيانات |
5. هياكل الرسوم البيانية: شبكات العلاقات المعقدة
Graph Structures: Representing Complex RelationshipsA network of nodes and edges
Graph properties
Vertices (V)
5
Edges (E)
6
Degree
2.4
Use Cases
Map navigation (shortest path)
Social networks (friend relationships)
Web links (PageRank)
Dependencies (package management)
| النوع | الخاصية | تشبيه |
|---|---|---|
| غير موجه | A→B مثل B→A | أصدقاء وي تشات |
| موجه | A→B ليس B→A | متابعون ويبو |
| مرجح | الحواف لها أوزان | طرق بين المدن |
6. مقارنة الأداء
Data Structures: Containers for DataChoose different storage models for different scenarios
ArrayContiguous memory and fast indexed access
010
120
230
340
450
560
670
780
Access arr[2] = O(1), insert/delete = O(n)
Time Complexity Comparison
| Operation | Array | Linked list | Hash table | Tree |
|---|---|---|---|---|
| Access | O(1) | O(n) | O(1) | O(log n) |
| Search | O(n) | O(n) | O(1) | O(log n) |
| Insert | O(n) | O(1) | O(1) | O(log n) |
| Delete | O(n) | O(1) | O(1) | O(log n) |
Core idea:Data structures are containers for data. Different containers have different tradeoffs. Choosing the right data structure can improve program efficiency by orders of magnitude.
| الهيكل | الوصول | البحث | الإدراج | الحذف |
|---|---|---|---|---|
| مصفوفة | O(1) | O(n) | O(n) | O(n) |
| قائمة | O(n) | O(n) | O(1) | O(1) |
| مكدس/طابور | O(n) | O(n) | O(1) | O(1) |
| جدول تجزئة | -- | O(1) | O(1) | O(1) |
| شجرة BST | -- | O(log n) | O(log n) | O(log n) |
7. دليل الاختيار
| الحاجة | الهيكل | السبب |
|---|---|---|
| وصول بالموقع | مصفوفة | O(1) وصول عشوائي |
| إدراج/حذف متكرر | قائمة مرتبطة | O(1) بدون نقل عناصر |
| LIFO (تراجع، تكرار) | مكدس | دلالات LIFO طبيعية |
| FIFO (طابور مهام) | طابور | دلالات FIFO طبيعية |
| بحث سريع بالمفتاح | جدول تجزئة | O(1) بحث متوسط |
| بيانات مرتبة + بحث سريع | BST | O(log n) ومرتب |
| علاقات كثير لكثير | رسم بياني | يعبر عن اتصالات تعسفية |
القاعدة العملية
- 80% من السيناريوهات: المصفوفات وجداول التجزئة كافية
- تحتاج ترتيب: فكر في الأشجار
- علاقات معقدة: فكر في الرسوم البيانية
- غير متأكد؟ استخدم الأسهل أولاً
قراءة إضافية
| الموضوع | المصدر |
|---|---|
| التصور | VisuAlgo |
| كتاب تمهيدي | "Grokking Algorithms" |
| تعمق | "Data Structures and Algorithm Analysis" |
| ممارسة | LeetCode |
الخطوات التالية
- التفكير الخوارزمي: تعلم حل المشكلات بالخوارزميات
- لغات البرمجة: كيف تنفذ اللغات هذه الهياكل