مفهوم Data Structure أو بنية البيانات أو هياكل البيانات كما يُطلق عليها البعض هو أحد المفاهيم الرئيسية التي تقوم عليها علوم البرمجة، وهو يعبر بشكل مبسط عن الكيفية والقدرة التي يتعامل بها برنامج معين مع البيانات التي تمر منه وإليه. في هذا المقال إن شاء الله سنوفر شرح Data Structure بشكل كامل. سنتعر ف على ما هى هياكل البيانات؟ ما أهميتها؟ أنواع هياكل البيانات، كيف يمكنك تعلم هذا المجال وكذلك ما هي أفضل لغات برمجة يمكن الاعتماد عليها لتعلم بنية البيانات، وأخيرًا سنذكر أفضل كتب ومصادر لتعلم هذا المجال.
ما هى هياكل البيانات؟
- باختصار؛ مفهوم Data Structure يُشير إلى "عملية التصميم الذكي للبرنامج لكي يتمكن من التعامل مع البيانات بكفاءة ويتمكن من تخزينها واستردادها بأقل جهد وفي أسرع وقت". لكي نوضح هذا المفهوم بشكل أفضل دعونا نأخذ مثالًا عمليًا قبل الدخول إلى التوضيح باستخدام البرمجة.
- على هاتفك الجوال تحتفظ بمجموعة من جهات الاتصال؛ وهي معلومات الاتصال بأصدقائك وأقاربك. إذا أردت الاتصال بأحدهم تذهب إلى قائمة جهات الاتصال وتبدأ في البحث باسم الشخص الذي تريد الاتصال به. هنا يمكنك البحث يدويًا في القائمة حتى تصل إلى الرقم، أو يمكنك بسهولة الضغط على زر البحث وكتابة حرفين أو ثلاثة من اسم الشخص وستجد الرقم ظهر أمامك.
- هذا المثال البسيط يوضح لنا أهمية تنظيم البيانات بدلًا من التعامل معها بشكل عشوائي. في حالة قمت بالبحث عن الرقم بشكل يدوي فسيستغرق هذا أضعاف الوقت المستغرق في استخدام البحث الآلي الذي يعتمد على التخزين المنظم للبيانات (جهات الاتصال) من أجل استردادها أو التعديل عليها بأقل استهلاك لموارد الجهاز وفي أسرع وقت ممكن.
ما أهمية هياكل البيانات؟
- ربما يكون تنظيم البيانات في بعض الحالات ليس ضروريًا. مثلًا جريدة مكونة من 10 صفحات لا تحتاج إلى فهرس يسهل البحث عن جزء داخل الجريدة، فيمكن تصفح جميع أوراقها والعثور على المحتوى المطلوب بسرعة، لكن ماذا عن كتاب مكوّن من ألف صفحة؟ هل يمكنك القيام بنفس الأمر؟ بالطبع لا.
- لهذا السبب نجد أن جزء كبير من علوم البرمجة يختص بكيفية التعامل مع البيانات؛ تحديدًا من حيث كيفية التخزين والاسترداد بكفاءة، لأن هذا الأمر يشكل أهمية كبرى في الأنظمة المعقدة التي تتعامل مع كمية ضخمة من البيانات. تخيل كيف أن محركات البحث مثل جوجل الذي يتعامل مع أكثر من 5 مليار عملية بحث يوميًا يستطيع استرداد البيانات بدقة من الفهرس الضخم الخاصّ به في خلال ثانية أو أقل من أجزاء من الثانية نظرًا لوصوله لكفاءة مثلى في تنظيم البيانات.
- لهذا فإن جزء كبير من العبء الذي يقع على المبرمج ليس فقط كتابة برنامج يقوم بغرض معين بشكل ناجح، ولكن أيضًا كيف يتعامل هذا البرنامج مع البيانات، وما مدى كفاءته في تخزين البيانات؛ وما هو معدل سرعة الاسترداد من قواعد البيانات وإجراء التعديلات عليها بدون أخطاء.
هياكل البيانات الخطية
- في هياكل البيانات الخطية Linear Data Structures يتم ترتيب العناصر بشكل تسلسلي أو خطي، حيث يتم ربط كل عنصر بالعناصر السابقة والتالية فيما يسمى بهيكل البيانات الخطي. من السهل تنفيذ هياكل البيانات الخطية لأن ذاكرة الكمبيوتر مرتبة بطريقة خطية. إليكم أبرز أنواع هذه البنية:
1- Arrays
- المصفوفات هي أسهل بنى البيانات وأكثرها استخدامًا. وتوفر عدة مميزات منها إمكانية الوصول إلى عنصر معين داخلها من خلال استخدام رقم الـIndex الخاصّ به، بدون حاجة إلى عمل Iteration على عناصر المصفوفة قبل الوصول إلى لعنصر المطلوب، ويجب تحديد سعة المصفوفة عند إنشائها، ويبدأ العد في المصفوفة من الرقم 0 وليس من الرقم 1.
* مثال على المصفوفات: يمكن اعتبار صفحات الكتاب بمثابة عناصر داخل مصفوفة.
2- Linked Lists
- القوائم المتصلة هي كذلك واحدة من هياكل البيانات الأكثر استخدامًا، وهي تشبه إلى حدٍ ما المصفوفات؛ لكنها تختلف في أن عناصر القائمة تكون متصلة ببعضها البعض، كما أنه لا يمكن الوصول لعنصر مباشرةً من خلال رقم الـIndex الخاصّ به، ولكن يجب عمل Iteration على كل العناصر وصولًا إلى العنصر المطلوب.
- تبدأ القوائم المتصلة بعقدة Node تُسمى الرأس Head وتنتهي بعقدة تُسمى الذيل Tail، وتحتوي كل عُقدة على عنصر أو نوع من البيانات بالإضافة إلى مؤشر Pointer يُشير إلى العُقدة التالية، وفي بعض أنواع القوائم المتصلة يوجد مؤشرين؛ مؤشر للعُقدة السابقة ومؤشر للعقدة التالية. توجد 4 أنواع للقوائم المتصلة وهي:
- Singly Linked list
- Doubly Linked list
- Circular Linked list
- Doubly Circular Linked list
* مثال على القوائم المتصلة: ألبوم صور تقوم بالانتقال منه من صورة لأخرى.
3- Stacks
- بنية الـStacks أو الكومة تُعرف أيضًا باختصار LIFO أو Last In First Out، أي أن آخر عنصر يدخل الكومة يكون في الأعلى، وبالتالي يكون هو أول عنصر يخرج منها.
- يمكن إضافة عنصر للكومة من خلال عمل Push ويمكن إزالته من خلال عمل Pop.
* مثال على الـStack: خيار التراجع عن آخر تعديل على ملف وورد. أول تراجع يكون آخر شيء تم تعديله.
4- Queues
- بنية قوائم الانتظار أو الطابور Queues هي عكس بنية الكومة ويطلق عليها FIFO أو First In First Out، أي أن أول عنصر يدخل الكومة يكون أول عنصر يخرج منها.
- يمكن إضافة عنصر في آخر الطابور من خلال عمل Enqueue ويمكن إزالة أول عنصر منه من خلال عمل Dequeue.
* مثال على الـQueue: عرض توفير محدود على سلعة أون لاين. أول من يدخل للموقع هو أول من يمكنه الشراء.
5- Hash Tables
- جداول التجزئة هي أيضًا من هياكل البيانات الهامّة لأنها توفر إمكانية البحث عن البيانات والوصول إليها بشكل سريع بغض النظر عن حجم البيانات التي يتم البحث فيها.
- تعمل جداول التجزئة من خلال تعيين مفتاح Key لكل قيمة Value، وباستخدام المفتاح يمكن الوصول إلى القيمة المرتبطة به بشكل سريع.
* مثال على الـHash Table: عند البحث عن نتيجة امتحاناتك باستخدام معرّف الهوية أو رقم الجلوس.
هياكل البيانات الغير خطية
- في هياكل البيانات الغير خطية Non-linear Data Structures لا يتم ترتيب العناصر بشكل تسلسلي أو خطي. تستخدم هذه البنية ذاكرة الكمبيوتر بكفاءة مقارنة بهيكل البيانات الخطي. إليكم أنواع هياكل البيانات الغير خطية:
1- Trees
- الأشجار هي نوع من أنواع هياكل البيانات يشبه إلى حدٍ ما القوائم المتصلة Linked Lists، حيث تكون العناصر مرتبطة ببعضها ويمكن التنقل من عنصر لآخر، ولكن هذا الربط يتم بطريقة هرمية؛ كما هو الحال في الشجرة العائلية على سبيل المثال.
- هيكل بيانات الشجرة قد يُطلق عليه أيضا Binary Search Tree، ويتكون من عُقد، كل عقدة تحتوي على بيانات، مؤشر للعقدة الفرعية اليمنى، مؤشر للعقدة الفرعية اليسرى، مؤشر للعقدة الرئيسية.
* مثال على الـTree: الملفات في نظام التشغيل. فنجد ملفات داخل مجلد داخل مجلد آخر وهكذا.
2- Heaps
- هيكل الـHeap قد يشبه في الشكل هيكل الشجرة Tree، لكنه في الحقيقة يختلف عنه، وهو أقرب من حيث الصفات إلى المصفوفات الثنائية. فهي تسمح بالتكرار على عكس الشجرة.
* مثال على الـHeap: الخوارزميات المستخدمة في تطبيقات الخرائط لمعرفة أقصر طريق
- يوجد نوعان من الـHeaps:
- Min Heap: يكون فيها مفتاح العقدة الرئيسية أقل في القيمة أو تساوي العقد الفرعية
- Max Heap: يكون فيها مفتاح العقدة الرئيسية (الأب) أعلى أو يساوي قيمة العقد الفرعية
3- Graphs
- آخر نوع من أنواع هياكل البيانات التي سنذكرها هي الرسوم البيانية. بنية البيانات هذه تتكون في الغالب من عدد محدود من العُقد المتصلة. ويستخدم هذا النوع من هياكل البيانات من أجل تمثيل البيانات بطريقة غير خطية.
* مثال على الـGraph: الخوارزميات المستخدمة في تطبيقات الخرائط لعرض البيانات على شكل طرق مرسومة
هياكل البيانات والخوارزميات
- بالرغم من تركيزنا في هذا المقال على شرح هياكل البيانات والمفاهيم الخاصّة بها؛ لكن لا يمكننا عدم ذكر الخوارزميات لارتباطها الوثيق ببنية البيانات. لذلك سنذكر ما هي الخوارزميات وعلاقتها ببنية البيانات بشكل مختصر، وإن شاء الله في المقال القادم سيتم الحديث بشكل مفصل عن مفهوم الخوارزميات Algorithms وكل ما يتعلق بها.
- الخوارزمية ببساطة هي عبارة عن سلسلة من الخطوات لتنفيذ عملية معين على مجموعة من المدخلات وتقديم مخرجات. مفهوم الخوارزمية ليس حكرًا على مجال البرمجة فحسب؛ بل في أي مجال ستجد مفهوم الخوارزمية مستخدمًا وإن كان بمسمى آخر.
- على سبيل المثال؛ إذا كان لدينا عملية حسابية بسيطة مثل هذه 3*2+1 = ؟ لكي نطبق مفهوم الخوارزمية فإننا نقوم بالتالي:
1- نقوم بعملية الضرب 3*2 = 6
2- نقوم بعملية الجمع 6 + 1 = 7
3- نقوم بعرض الناتج 3*2+1 = 7
أشهر أنواع الخوارزميات
- Binary Search Algorithm
- Breadth First Search (BFS) Algorithm
- Depth First Search (DFS) Algorithm
- Merge Sort Algorithm
- Quicksort Algorithm
- Kruskal’s Algorithm
- Floyd Warshall Algorithm
- Dijkstra’s Algorithm
- Bellman Ford Algorithm
- Kadane’s Algorithm
- Lee Algorithm
- Flood Fill Algorithm
- Floyd’s Cycle Detection Algorithm
- Union Find Algorithm
- Topological Sort Algorithm
- KMP Algorithm
- Insertion Sort Algorithm
- Selection Sort Algorithm
- Counting Sort Algorithm
- Heap Sort Algorithm
- Kahn’s Topological Sort Algorithm
- Huffman Coding Compression Algorithm
- Quickselect Algorithm
- Boyer–Moore Majority Vote Algorithm
- Euclid’s Algorithm
كيف تعمل هياكل البيانات مع الخوارزميات؟
- بنية البيانات والخوارزميات يتكاملان من أجل توفير نظام يعمل بأقصى كفاءة ممكنة. يمكنك اختيار بنية بيانات صحيحة لكن في حالة استخدام خوارزمية خاطئة للتعامل مع البيانات لن يعمل البرنامج بالشكل المثالي، وسيحتاج إلى وقتٍ أطول وموارد أكبر من أجل تقديم المخرجات.
- على سبيل المثال إذا كان لدينا مجموعة أرقام تم وضعهم بشكل عشوائي في بنية بيانات من نوع List. إذا أردنا إجراء عملية ترتيب لهذه الأرقام من الأصغر إلى الأكبر فيمكننا القيام بذلك باستخدام خوارزمية Merge Sort من خلال كتابة برنامج بلغة بايثون أو لغة أخرى مثل هذا:
* ترتيب الأرقام قبل تشغيل الكود: [71,56,93,17,77,38,44,95,20]
def mergeSort(myList):
if len(myList) > 1:
mid = len(myList) // 2
left = myList[:mid]
right = myList[mid:]
#Recursive call on each half
mergeSort(left)
mergeSort(right)
#Two iterators for traversing the two halves
i = 0
j = 0
#Iterator for the main list
k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
# The value from the left half has been used
myList[k] = left[i]
# Move the iterator forward
i += 1
else:
myList[k] = right[j]
j += 1
# Move to the next slot
k += 1
#For all the remaining values
while i < len(left):
myList[k] = left[i]
i += 1
k += 1
while j < len(right):
myList[k]=right[j]
j += 1
k += 1
myList = [71,56,93,17,77,38,44,95,20]
mergeSort(myList)
print(myList)ما هي أفضل لغات برمجة لتعلم Data Structure؟
- في الحقيقة لا توجد إجابة واحدة صحيحة لهذا السؤال. إذا كنت بالفعل بدأت في تعلم لغة برمجة يمكنك تعلم هياكل البيانات باستخدامها، ما دام ذلك متاحًا. لكن إذا أردت ترشيحًا فبالطبع يمكن أن أرشح لك لغة C فهي اللغة الأم التي تطورت منها معظم لغات البرمجة الأكثر استخدامًا، كما أنها ستوفر لك إمكانية معرفة تفاصيل دقيقة عن التعامل مع الذاكرة باحتراف، وكيفية تخصيص وتحرير الذاكرة. ولذلك هي اللغة المستخدم في كورس CS50 وهو كورس علوم الكمبيوتر الأشهر المقدم من جامعة هافارد لشرح بنية البيانات Data Structure.
- لكن تعلم هياكل البيانات والخوارزميات لا يقتصر على لغة سي فقط، فهناك لغات أخرى يمكن الاعتماد عليها، وجميع اللغات تقريبًا تتشارك نفس المبادئ في هذا المجال مع اختلاف طريقة التنفيذ. إليكم قائمة بأفضل لغات برمجة لتعلم Data Structure:
- لغة سي C
- لغة سي بلس بلس ++C
- لغة بايثون Python
- لغة جافا Java
- لغة سي شارب #C
- لغة روبي Ruby
- جافا سكريبت JavaScript
- لغة جو GO
- لغة بي إتش بي PHP
- لغة سويفت Swift
أفضل مصادر تعلم هياكل البيانات Data Structure
- سنوفر لكم الآن مجموعة من المصادر الممتازة لبدء تعلم المجال من خلال مجموعة من الكورسات بالعربية والإنجليزية والتي يمكنكم تصفحها واختيار الشرح الذي تجدونه ملائمًا لكم.
الخوارزميات وهياكل البيانات Algorithms & Data Structures
من أفضل الدورات التي يمكنك البدء بها وهي مقدمة من قناة KMR Script.
Data Structures Full Course
- دورة جيدة باللغة العربية لتعلم كبداية لتعلم المجال بدون التركيز على لغة معينة.
الخوارزميات وهيكلة البيانات
- دورة أخرى يمكن تعلمها مقدمة من قناة TheNewBaghdad.
Data Structures
- دورة حديثة ومتجددة في هذا المجال ولكن باللغة الإنجليزية مقدمة من قناة Neso Academy.
MIT data structure and algorithms
- هذا الكورس تم تدريسه في معهد MIT، وهو أيضًا باللغة الإنجليزية.
**** مصادر ****
- مصدر 1
- مصدر 2