Posts Tagged اساسيات البرمجة

15- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Binary Search
الخوارزميات وبنى المعطيات – البحث الثنائي

اليوم سنتحدث عن خوارزمية البحث الثنائي Binary search

البحث الثنائي عبارة عن خوارزمية بحث سريع مع تعقيد زمن تشغيل Ο (log n) – تم شرح موضوع التعقيد في درس سابق

خوارزمية البحث هذه تعمل على مبدأ فرق تسد divide and conquer – تم شرحه في درس سابق. لكي تعمل هذه الخوارزمية بشكل صحيح ، يجب أن تكون البيانات مرتبة – تم فرزها بشكل سابق

تقوم خوارزمية البحث الثنائي بالبحث عن عنصر معين من خلال مقارنة هذا العنصر بالعنصر الوسطي ضمن المجموعة. في حالة حدوث مطابقة ، فسيتم إرجاع فهرس العنصر الوسطي item index. أما اذا كان العنصر الوسطي أكبر من عنصر البحث، فسيتم البحث عن هذا العنصر ضمن المصفوفة الجزئية الواقعة الى يسار العنصر الأوسط. بخلاف ذلك ، يتم البحث عن العنصر في المصفوفة الجزئية الواقعة إلى يمين العنصر الأوسط. تستمر هذه العملية على المصفوفة الجزئية أيضًا حتى يتناقص حجم المصفوفات الجزئية إلى الصفر.

binary-search1.png

كيف تعمل خوارزمية البحث الثنائي binary search

من احد اهم الشروط للبحث الثنائي, ان تكون المعطيات مفروزة – مرتبة.

سنتعلم خوارزمية البحث الثنائي عن طريق مثال عملي.

فيما يلي مصفوفة مرتبة, وسنقوم بالبحث عن العنصر ذو القيمة 31 باستخدام البحث الثنائي.

binary_search_0

في البداية يجب ان نحدد منتصف هذه المصفوفة باستخدام المعادلة التالية:

middle formula.JPG

0+(9-0)/2 = 4

حيث ان 4 يمثل القيمة الصحيحة من 4.5, اذن 4 عبارة عن فهرس منتصف المصفوفة

binary_search_1

سنقارن الان القيمة الموجودة في الدليل – فهرس index – رقم 4, مع القيمة التي يتم البحث عنها = 31.

نجد بأن القيمة 27 اصغر من القيمة التي يتم البحث عنها. اذن لا يوجد تطابق, وسيتم البحث من جديد ضمن المصفوفة الجزئية الواقعة الى يمين الفهرس الوسطي الحالي.

binary_search_2.jpg

ستتغير الفهارس  كالتالي

Low = mid +1  اذ ان بداية المصفوفة الجزئية – الواقعة على اليمين – يبدأ من الفهرس الوسطي للمصفوفة الكلية , ويمثل الحد الادنى للفهرس

middle formula 2

سنبحث عن الفهرس الوسطي للمصفوفة الجزئية من جديد

الفهرس الجديد = 7.

سنقارن القيمة 31 بالقيمة الموجودة ضمن الفهرس 7

binary_search_3.jpg

نجد بان القيمة 34 اكبر من القيمة 31 التي يتم البحث عنها. بالتالي سيتم البحث ضمن المصفوفة الجزئية الواقعة على يسار القيمة عند الفهرس الحالي.

binary_search_4.jpg

نقوم بحساب الفهرس الوسطي من جديد = 5

صورة

نقارن القيمة عن الفهرس index = 5  بقيمة البحث, نجد تطابق 31!

binary_search_6.jpg

بالتالي فإن القيمة التي نبحث عنها ضمن هذه المصفوفة واقعة ضمن الفهرس رقم 5

 

تقوم خوارزمية البحث الثنائي بتقسيم فضاء البحث الى نصفين في كل مرة, وبالتالي تقلل عدد المقارات التي من المطلوب اجرائها من اجل البحث عن عنصر ما.

بسودوكود الخوارزمية Pseudocode

pseudocode.JPG

الان حاول برمجة خوارزمية البحث الثنائي باحد لغات البرمجة التي تتقنها!

 

والى لقاء في حلقة جديدة نشرح فيها باللغة العربية خوارزمية البحث بالاستيفاء interpolation search

والى ذلك الحين استودعكم  الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
البحث الخطي Linear Search
البحث الثنائي Binary Search
دليل – فهرس Index
 البحث بالاستيفاء interpolation Search
المؤشر الأمامي Front Pointer
المؤشر الخلفي Rear Pointer
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case
البحث الثنائي Binary Search

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

Advertisements

, , , , , , , , ,

أضف تعليق

14- الخوارزميات وبنى المعطيات – البحث الخطي Algorithms and Data Structure – Linear Search

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Linear Search
الخوارزميات وبنى المعطيات – البحث الخطي

ننتقل بدروسنا الى بحث اخر, الا وهو خوارزميات البحث, فبعد ان تعرفنا على بنى المعطيات الاساسية, حان الوقت للتعرف على احد اهم العمليات على هذه البنى, الا وهو البحث search
linear_search

ضمن هذه الحلقة سنتعرف على خوازرمية البحث الخطي Linear search

تعتبر خوارزمية البحث الخطي Linear search احد اسهل الخوارزميات!
ضمن هذا النوع من خوارزميات البحث, يتم اجراء عملية بحث متتالي مرورا بكل العناصر واحدا تلو الاخر.

يتم التحقق من كل عنصر فيما اذا كان يطابق مواصفات البحث, الا ان يتم ايجاد العنصر المطلوب وارجاعه كنتيجة للبحث, والا يستمر البحث بالمرور على كل العناصر وصولا الى اخر عنصر ضمن بنية المعطيات التي يتم البحث ضمنها.

الخوارزمية

algorithm.JPG

فيما يلي “بسودوكود Pseudocode” الخورازمية

pdoducode.JPG

نعم, فإن خوارزمية البحث الخطي على هذا القدر من البساطة!

حاولوا الان برمجة الخوارزمية باحد لغات البرمجة

الى اللقاء في حلقة قادمة نتحدث فيها عن نوع اخر من الخوارزميات, الا وهي خوارزمية البحث الثنائي Binary search

والى ذلك الحين استودعكم  الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
البحث الخطي Linear Search
عملية Operation
رتل Queue
المكدس Stack
المؤشر الأمامي Front Pointer
المؤشر الخلفي Rear Pointer
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case
البحث الثنائي Binary Search

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

, , , , , , , ,

أضف تعليق

13- الخوارزميات وبنى المعطيات – الرتل Algorithms and Data Structure – Queue

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Queue
الخوارزميات وبنى المعطيات – الرتل

نتابع حديثنا في هذه الحلقة عن احد بنى المعطيات المهمة جدا, الا وهي الرتل queue

الرتل عبارة عن بنية بيانات مجردة ، تشبه إلى حد ما المكدس stack .  ولكن على عكس المكدس ، فان الرتل queue عبارة عن قائمة انتظار مفتوحة على طرفيها. يتم دائمًا استخدام أحد الطرفين لإدراج البيانات (enqueue) ويستخدم الآخر لإزالة البيانات (dequeue). يتبع الرتل منهجية First-In-First-Out ، أي انه يتم الوصول الى عناصر البيانات المخزنة اولا. الأولوية للمدخلات الاولى.

queue_example

احد الامثلة الواقعية على بنية المعطيات هذه هي طابور السيارات – رتل – حيث ان السيارة التي تدخل اولا تخرج اولا من الرتل.

هنالك العديد من الامثلة الواقعية في الحياة على بنية المعطيات هذه.

تمثيل الرتل Queue Representation

الان وبعد ان فهمنا المبدأ الاساسي للرتل, يحاول الرسم التوضيحي ادناه ان يوضح تمثل الرتل كبنية معطيات

queue_diagram.jpg

كما هو الحال في المكدس ، يمكن أيضًا تنفيذ الرتل queue باستخدام المصفوفات ، والقوائم المتصلة LinkedList  ، والمؤشرات Pointers والبنى. من أجل البساطة ، سنقوم بتنفيذ الرتل باستخدام مصفوفة أحادية البعد.

العمليات الاساسية Basic Operations

قد تتضمن عمليات الرتل تهيئة أو تعريف الرتل ، واستخدامه ، ومن ثم مسحه بالكامل من الذاكرة. هنا سنحاول فهم العمليات الأساسية المرتبطة بالارتال –

     enqueue () – إضافة (تخزينن) عنصر إلى الرتل.

     dequeue () – إزالة (الوصول) عنصر من الرتل.

يلزمنا بضع وظائف لجعل عملية الرتل المذكورة أعلاه فعالة. مثل –

peek () – الحصول على العنصر الموجود في مقدمة الرتل دون إزالته.

isfull () – التحقق فيما إذا كان الرتل ممتلئ.

isempty () – يتحقق إذا كان الرتل فارغ.

في الرتل ، نستطيع دوما ان نضيف بيانات جديدة للرتل عبر عملية enqueuer, وذلك بالاستفادة من المؤشر الخلفي rear pointer الذي يشير الى نهاية الرتل, وبامكاننا الوصول الى العناصر الموجودة في بداية الرتل dequeuer, بالاستفادة من المؤشر الامامي front pointer الذي يؤشر الى بداية الرتل           .

 

دعونا أولا نتعرف على الوظائف المهمة في الرتل –

Peek()

يساعد هذا التابع – الوظيفة – بالوصول الى مقدمة الرتل.

الخوارزمية المستخدمة كالتالي:

peek algorithm.JPG

مثال بلغة C

peek example.JPG

Isfull()

نظرًا لأننا نستخدم مصفوفة البعد الأحادي لتنفيذ الرتل ، فنحن نتحقق فقط من أن يصل المؤشر الخلفي إلى MAXSIZE لتحديد فيما اذا كان الرتل ممتلئ. في حالة تنفيذ الرتل باستخدام circular LinkedList عندها سوف تختلف الخوارزمية بشكل كامل

الخوارزمية المستخدمة كالتالي:

isfull

مثال بلغة C

isfull ex

Isempty()

الخوارزمية المستخدمة كالتالي:

isempty algorithm.JPG

مثال بلغة C

isempty ex.JPG

عملية الاضافة enqueue Operation

يحتفظ قوائم الرتل بمؤشرين بيانات ، أمامي وخلفيfront and rear . ولذلك ، فإن عملياتها صعبة التنفيذ نسبياً من تلك الخاصة المكدسStack

. يجب اتخاذ الخطوات التالية من اجل ادراج (اضافة) البيانات الى الرتل

الخطوة 1 – التحقق من امتلاء الرتل

الخطوة 2 – إذا كان الرتل ممتلئ ، قم بإنشاء خطأ تجاوز يبين تجاوز السعة المسموح بها للاضافة ومن ثم الخروج.

الخطوة 3 – إذا لم يكن الرتل ممتلئ ، قم بزيادة المؤشر الخلفي ليؤشر الى الفراغ التالي

الخطوة 4 – إضافة عنصر البيانات إلى الحيز الموجود ضمن الرتل ، حيث يشير المؤشر الخلفي

الخطوة 5 – نجاح العودة.

queue_enqueue_diagram.jpg

في بعض الاحيان ايضا نقوم بالتحقق فيما اذا كان الرتل مهيئأ ام لا, وذلك لتجنب الحالات الغير متوقعة

خوارزمية الاضافة

Enqueue algorithm

تنفيذ الخوارزمية بلغة C

enqueue example.JPG

عملية الحذف dequeue

اجرائية الوصول إلى البيانات المتواجدة في الرتل عبارة عن عملية مكونة من مهمتين

– الوصول إلى البيانات التي يشير اليها مؤشر البداية front pointer ومن ثم إزالة هذه البيانات بعد الوصول اليها.

يتم اتخاذ الخطوات التالية لتنفيذ عملية الحذف-

الخطوة 1 – تحقق مما إذا كان الرتل فارغ.

الخطوة 2 – إذا كان الرتل فارغًا ، فقم بإخراج الخطأ والخروج.

الخطوة 3 – إذا لم يكن الرتل فارغا ، قم بالوصول إلى البيانات التي يشير اليها مؤشر البداية front pointer.

الخطوة 4 – زيادة مؤشر البداية front pointer للإشارة إلى عنصر البيانات التالي المتاح.

الخطوة 5 – نجاح العودة.

queue_dequeue_diagram.jpg

خوارزمية الازالة dequeuer algorithm

dequeue.JPG

مثال على تطبيق الخوارزمية بلغة C

dequeue example.JPG

وبهذا نكون قد انتهينا من شرح اهم بنى المعطيات, لننتقل الى موضوع جديد الا وهو خوارزميات وتقنيات البحث, مثل البحث الخطي linear search, البحث الثنائي binary search, الاستيفاءinterpolation search , Hash table.

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
رتل Queue
المكدس Stack
المؤشر الأمامي Front Pointer
المؤشر الخلفي Rear Pointer
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

, , , , , , , , , , ,

أضف تعليق

12- الخوارزميات وبنى المعطيات – المكدس Algorithms and Data Structure – Stack

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Stack
الخوارزميات وبنى المعطيات – المكدس

السلام عليكم ورحمة الله وبركاته

سنتحدث في هذه الحلقة عن احد بنى المعطيات المهمة جدا, الا وهي المكدس Stack

المكدس Stack: هو نمط معطيات مجردabstract data type  (ADT) ، شائع الاستخدام في معظم لغات البرمجة. يدعى المكدس لانه عبارة عن مجموعة من العناصر التي تتكدس فوق بعضها البعض، على سبيل المثال – مجموعة أوراق أو كومة من لوحات مكدسة فوق بعضها البعض ، إلخ.

stack_example

في اي مثال حقيقي للمكدس stack نلاحظ ان العمليات متاحة من نهاية واحدة فقط. على سبيل المثال ، يمكننا وضع أو إزالة بطاقة أو لوحة من الطرف العلوي من المكدس فقط. وبالمثل ، يتيح مفهوم المكدس البرمجي Stack ADT امكانية تنفيذ جميع العمليات من جهة واحدة فقط.  اي انه لا يمكننا الوصول إلا إلى العنصر العلوي للمكدسstack .

هذه الميزة تجعله المكدس من انماط بنية المعطيات التي تدعى باسم LIFO وهي اختصار للعبارة

Last-In-First-Out

اي اخر عنصر تتم اضافته للمكدس, هو اول عنصر يخرج من المكدس

في مصطلحات المكدس ، تدعى عملية الإدراج عملية PUSH وتسمى عملية الإزالة عملية POP.

 

تمثيل المكدس Stack Representation

الشكل ادناه عبارة عن تمثيل لمكدس stack  مع العمليات المتاحة عليه
stack_representation.jpg

يمكن تنفيذ مكدس بواسطة احد بنى المعطيات التالية Array و Structure و Pointer و Linked List.

كما انه يمكن ان يكون حجم المكدس ثابتًا أو متغيرا بشكل ديناميكي

ضمن هذه الدرس, سنقوم بتمثيل وتنفيذ المكدس باستخدام المصفوفات ، مما يجعله مكدس بحجم ثابت.

 

العمليات الاساسية Basic Operations

قد تتضمن العمليات التي يتم اجرائها على المكدس تهئيته قبل استخدامه.

ولكن بشكل عام – اذا تجاوزنا هذه التفاصيل – فإن هنالك عمليتين اساسيتين في المكدس

push () – دفع (تخزين) عنصر في المكدس.

pop () – إزالة (الوصول إلى) عنصر من المكدس.

لكي يتم استخدام المكدس بكفائه ، نحتاج إلى التحقق من حالة المكدس أيضًا. لنفس الغرض ، يتم إضافة الاجرائيات والوظائف التالية إلى المكدس  –

peek () – الحصول على عنصر البيانات العلوي من المكدس ، دون إزالته من المكدس.

isFull () – تحقق مما إذا كان المكدس ممتلئأ.

isEmpty () – تحقق من أن المكدس فارغ.

في كل الاحوال, يتم الاحتفاظ بمؤشر يشير الى اخر عنصر تمت اضافته الى المكدس.
أولا يجب أن نتعلم بعض إجراءات المهمة لوظائف المكدس –

Peek()

خوارزمية هذه الوظيفة كالتالي:

peek.JPG

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

peek-ex

IsFull()

خوارزمية هذه الوظيفة كالتالي:

isfull.JPG

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

isfull-ex

isEmpty()

خوارزمية هذه الوظيفة كالتالي:

isempty

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

isempty-ex.JPG

عملية الاضافة Push Operation

تعرف عملية اضافة عنصر بيانات جديد الى المكدس بعمليةPush . تتضمن الخطوات التالية:
الخطوة 1 – التحقق فيما اذا كان المكدس ممتلئ.

الخطوة 2 – إذا كان المكدس ممتلئ ، ينتج عنها خطأ والخروج.

الخطوة 3 – إذا لم يكن المكدس ممتلئ ، قم بزيادة العداد ليؤشر الى المساحة الفارغة التالية.

الخطوة 4 – إضافة عنصر بيانات إلى مؤشر المكدس –  يؤشر الى اعلى المكدس

الخطوة 5 – إرجاع حالة النجاح.

 

خوارزمية عملية الاضافة Algorithm for PUSH operation

فيما يلي مثال على خوارزمية الاضافة

push algorithm.JPG

مثال على تنفيذ هذه العملية بلغة C

push algorithm-ex.JPG

عملية اخراج عنصر من المكدس POP Operation

تعرف عملية الوصول الى العنصر الاخير في المكدس, وازالته من المكدس  باسم عملية Pop

عند تنفيذ وبرمجة هذه العملية باستخدام بنى المعطيات array – مصفوفة – لا تتم إزالة عنصر البيانات فعليًا ، بدلاً من ذلك يتم تقليل عداد المؤشر ليؤشر الى موضع أدنى في المكدس حيث القيمة التالية. ولكن عند  تنفيذ هذه العملية في بنية معطيات مثل القائمة المتصلة Linked List , عندها يقوم التابع  pop () بالفعل بإزالة عنصر البيانات وإلغاء تخصيص مساحة الذاكرة.

قد تتضمن عملية Pop الخطوات التالية –

الخطوة 1 – التحقق من أن المكدس فارغ.

الخطوة 2 – إذا كان المكدس فارغ ، ينتج عنها خطأ وتنتهي.

الخطوة 3 – إذا لم يكن المكدس فارغ، يتم الوصول إلى عنصر البيانات الذي يشير إليه مؤشر المكدس

الخطوة 4 – تقلل عداد مؤشر المكدس بمقدار 1 ليؤشر الى القيمة التالية.

الخطوة 5 – إرجاع حالة النجاح.

خوارزمية عملية pop

خوارزمية هذه الوظيفة كالتالي:

pop algorithm.JPG

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

pop algorithm-ex.JPG

نتابع ان شاء الله حديثا في الحلقة القادمة عن بنى المعطيات الرتل queue

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

, , , , , , , , , , , , , , , ,

أضف تعليق

11- الخوارزميات وبنى المعطيات – القائمة المتصلة الدائرية Algorithms and Data Structure – Circular Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Circular Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة الدائرية

القائمة المرتبطة دائريا circular linked list: عبارة عن نسخة معدلة من القائمة المتصلة linked list بحيث يشير الأول الى العنصر الاخير, وكذلك يشير العنصر الاخير الى العنصر الاول.

يمكن لكلا النوعين: “القائمة المتصلة المفردة singly lined list والقائمة المتصلة مزدوجة الارتباط doubly linked list ان تكونا دائريتان بحسب الوصف السابق.

 

القائمة المتصلة  – الدائرية Singly linked list as circular

في القائمة المتصلة احادية الاتجاه, يجب ان يشير المؤشر التالي للعنصر الاخير next pointer of last item الى اول عنصر – عقدة ضمن القائمة.

singly_circular_linked_list.jpg

القائمة المزدوجة الارتباط الدائرية doubly linked list as circular

يجب ان يشير رابط التالي next link للعنصر الاخير الى العنصر الاول في القائمة, وان يشير رابط السابق prev link للعنصر الاول الى اخر عنصر ضمن القائمة.

doubly_circular_linked_list.jpg

وبذلك نحصل على قائمة متصلة دائرية يمكن التجوال فيها باتجاهين

من الاشكال السابقة, نلاحظ بأن هنالك عدة نقاط مهمة يجب التنويه اليها:

في كلا نوعي القوائم المتصلة – المفردة والمزدوجة: نجد بأن رابط التالي next  للعقدة الاخيرة في القائمة يشير الى العنصر الاول في القائمة.

اما في القائمة مزدوجة الارتباط فإن رابط السابق prev link للعنصر الاول يؤشر الى العنصر الاخير ضمن السلسلة

العمليات الاساسية

فيما يلي عدد من العمليات الاساسية المهمة المدعومة ضمن القوائم المتصلة الدائرية:

  • الاضافة insert : اضافة عنصر عند بداية القائمة.
  • الحذف delete: حذف عنصر من بداية القائمة list .
  • العرض display : عرض عناصر القائمة list .

عملية الاضافة insertion operation

الكود التالي يوضح عملية الاضافة الى بداية القائمة المتصلة الدائرية الاحادية

مثال

insert operation.JPG

عملية الحذف deletion operation

الكود التالي يمثل عملية حذف العنصر الاول من قائمة متصلة احادية الاتجاهsingle linked list

delete operation.JPG

عملية عرض القائمة display list operation

الكود التالي يمثل عملية عرض عناصر قائمة متصلة احادية الاتجاهsingle linked list

display op.JPG

وبهذا ننهي حديثنا عن القوائم المتصلة, لننتقل للحديث عن موضوع شيق الا وهو بنية المطيات المكدس Stack data structure

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

, , , , , , , , , , , , ,

أضف تعليق

10- الخوارزميات وبنى المعطيات – القائمة المتصلة مزدوجة الارتباط Algorithms and Data Structure – Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Doubly Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة المزدوجة الارتباط

القائمة المتصلة المزدوجة الارتباط: عبارة عن نسخة معدلة من القائمة المزودجة, بحيث تمكن التجوال باتجاهين – للامام والخلف – بسهولة التجوال المتواجد ضمن القائمة المتصلة linked list .

فيما يلي قائمة بالمصطلحات المهمة فيما يتعلق بالقائمة المتصلة المزدوجة الارتباط Doubly Linked List:

  • الرابط Link: يمكن لكل رابط – من روابط القائمة المتصلة – ان يخزن المعطيات, وتدعى هذه المعطيات باسم العنصر element.
  • التالي Next: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر التالي مباشرة, ويدعى هذا الرابط باسم التالي Next.
  • التالي Prev: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر السابق مباشرة, ويدعى هذا الرابط باسم التالي Prev.

 

تمثيل القائمة المتصلة المزدوجة الارتباط doubly linked list representation

doubly_linked_list

فيما يلي بعض النقاط الهامة التي يجدر الانتباه اليها في القائمة المتصلة المزدوجة الارتباطdoubly linked list :

  • تحوي على رابط يدعلى الرابط الاول first link, وعلى رابط يدعى الرابط الاخير last link.
  • كل رابط Link يحوي على حقل معطيات – او عدة حقول – وعلى حقلين خاصين بالروابط links يدعيان التالي next والسابق Prev.
  • يحوي العنصر الاخير على رابط next يشير الى القيمة Null معلنا بذلك نهاية القائمة.

العمليات الأساسية:

فيما يلي قائمة بالعمليات الاساسية المدعومة ضمن القائمة المتصلة:

  • الاضافة insertion : اضافة عنصر الى بداية القائمة المتصلة
  • الحذف deletion: حذف عنصر من بداية القائمة المتصلة
  • الاضافة للاخير insert last: اضافة عنصر الى اخر القائمة المتصلة
  • حذف العنصر الاخير delete last: حذف عنصر من نهاية السلسلة.
  • الاضافة بعد عنصر insert after: اضافة عنصر بعد عنصر محدد من القائمة>
  • الحذف delete : حذف عنصر من القائمة باستخدام مفتاح محددkey .
  • العرض قدما Display forward: عرض كامل السلسلة من البداية للنهاية
  • العرض بشكل تراجعي display backward: عرض كامل محتويات السلسلة بشكل تراجعي من النهاية للبداية.

 

عملية الاضافة Insertion Operation

الكود التالي يبين عملية اضافة عنصر الى بداية القائمة المتصلة المزدوجة الارتباط doubly linked list

مثال:

insert begining 1.JPG

عملية الحذف Deletion Operation

الكود التالي يمثل عملية الحذف لعنصر من بداية القائمة المتصلة المزدوجة الارتباط

مثال:

delete example.JPG

الاضافة الى نهاية السلسلة Insertion at the End of an doubly linked list

الكود ادناه يمثل عملية اضافة عنصر الى نهاية قائمة متصلة مزدوجة.

insert at the end of the list.JPG

وبهذا القدر ننتهي من الحديث عن القائمة المتصلة المزدوجة الارتباط

كتمرين, بامانكم كتابة خوارزمية تنفيذ بقية العمليات على هذا النوع من القوائم

نلتقي في الدرس القادم للحديث عن القوائم المتصلة الدائرية

circular linked list

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/index.htm

 

 

 

, , , , , , , , , , , , ,

أضف تعليق

9- الخوارزميات وبنى المعطيات – القائمة المتصلةAlgorithms and Data Structure – Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة

 

ننتقل اليوم بالحديث الى نوع اخر من بنى المعطيات, الا وهو القائمة المتصلة linked list
وسنستمر ضمن الحلقتين القادمتين بالحديث عن الانواع المختلفة من هذه القوائم.

القائمة المتصلة: عبارة عن تتالي لبنى معطيات data structure, التي يتم ربطها مع بعضها البعض عبر مايعرف باسم الروابط Links.

يمكننا القول بأن القائمة المتصلة عبارة عن سلسلة من الروابط Links التي تحوي عناصر items.
كل رابط Link يحوي ايضا وصلة الى رابط اخر another link.
تعتبر القائمة المتصلة ثاني اكثر بنية معطيات مستخدمة بعد المصفوفات.
فيما يلي بعض اهم المصطلحات المستخدمة فيما يتعلق بمفهوم القائمة المتصلة Linked List

  • الرابط Link: يمكن لكل رابط – من روابط القائمة المتصلة – ان يخزن المعطيات, وتدعى هذه المعطيات باسم العنصر element.
  • التالي Next: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر التالي مباشرة, ويدعى هذا الرابط باسم التالي Next.
  • القائمة المتصلةLinkedList : تحوي القائمة المتصلة مايعرف برابط البداية الذي يشير الى اول رابط ضمن القائمة. ويعرف هذا الرابط باسم “الاول”First .

ملاحظة:
من المهم جدا حفظ هذه المصطلحات كما هي باللغة الانكليزية بالاضافة لفهمها باللغة العربية.

تمثيل القائمة المتصلة Linked List Representation

يمكن تمثيل القائمة المتصلة على شكل سلسلة من العقد nodes, حيث تشير كل عقدة node الى العقدة التالية.

linked_list

هنالك بعض النقاط الهامة التي يجدر الانتباه اليها في الشكل السابق:

  • تحوي القائمة المتصلة linked list على عنصر رابط يدعى بالاول “first”
  • يوجد مع كل رابط link حقل معطيات ( او مجموعة حقول), بالاضافة الى رابط للعنصر التالي Next link.
  • يحوي الرابط الاخير last link على رابط يشير الى القيمة null, ليدل بذلك على نهاية القائمة.

انواع القائمة المتصلة Types of Linked List

هنالك عدة انواع من القوائم المتصلة:

  • القائمة المتصلة البسيطة Simple Linked List: بالامكان التجوال داخل هذه القائمة باتجاه واحد
  • القائمة المتصلة على نحو مضاعف double linked list: ويمكن التجوال ضمن هذه القائمة باتجاهين : الامام والخلف
  • القائمة المتصلة الدائرية Circular Linked List: العنصر الاخير يحوي على رابط للعنصر الاول من هذه القائمة, وكذلك يحوي العنصر الاول على رابط يشير الى اخر عنصر من القائمة next link.

العمليات الأساسية:

فيما يلي قائمة بالعمليات الاساسية المدعومة ضمن القائمة المتصلة:

  • الاضافة insertion : اضافة عنصر الى بداية القائمة المتصلة
  • الحذف deletion: حذف عنصر من بداية القائمة المتصلة
  • العرض display: عرض كافة محتويات القائمة المتصلة.
  • البحث search: البحث عن عنصر باستخدام مفتاح معين key ضمن القائمة المتصلة

عملية الاضافة Insertion operation

إن عملية إضافة عقدةnode  جديدة في القائمة المتصلة linked list لا تتم عبر خطوة واحدة. سوف نتعلم هذا مع الرسوم البيانية هنا. أولاً ، قم بإنشاء عقدةnode  باستخدام نفس البنية , ثم ابحث عن الموقع الذي يجب إدراجه فيه.

linked_list_insertion_0

تخيل بأننا نقوم باضافة عقدة جديدة باسم B newNode, وذلك بين العقدة A LeftNode ,العقدة C rightNode. ومن ثم نجعل B.next يؤشر على C

insert node 2

linked_list_insertion_1.jpg

الآن, يجب ان توشر القعدة الموجودة على اليسار الى العقدة الجديدة

insert node 3

linked_list_insertion_2

وبهذا تكون قد توضعت العقدة الجديدة بين العقدتين. ويكون الشكل النهائي للقائمة المتصلة كالتالي:

يجب اتخاذ خطوات مشابهه في اضافة العقدة الى بداية القائمة. اما بالنسبة للاضافة الى نهاية القائمة, عندها يجب ان يؤشر رابط التالي next link للعقدة الاخيرة الى العقدة الجديدة, بينما يكون مؤشر رابط التالي next link للعقدة الجديدة يؤشر الى القيمة null كدلالة على نهاية السلسلة.

linked_list_insertion_3.jpg

عملية الحذف Deletion Operation

عملية البحث ايضا لا تتم بخطوة واحدة, كما سنوضح بالصور.

اولا, يجب ايجاد العقدة الهدف – المطلوب ازالتها -, وذلك باستخدام احد خوارزميات البحث.

linked_list_deletion_0.jpg

يجب ان تؤشر العقدة السابقة للعقدة الهدف, على نفس العنصر الذي تؤشر عليه العقدة الهدف كعنصر تالي:

delete 1.JPG

linked_list_deletion_1.jpg

والان نزيل الرابط الذي كان يؤشر على العقدة الهدف. وكذلك نزيل الرابط الذي تؤشر عليه العقدة الهدف كعنصر تالي:

delete 2

linked_list_deletion_2

في حال لم نكن بحاجة الى استخدام العقدة المحذوفة, عندها يجب ازالتها من الذاكرة deallocate – ازالة حجزها من الذاكرة – وبذلك تنتهي هذه العقدة للابد.

linked_list_deletion_3.jpg

عملية العكس Reverse Operation

وتهدف هذه العملية الى عكس اتجاه السير ضمن القائمة المتصلة, بحيث يؤشر رابط نهاية السلسلة الى العنصر قبل الاخير فيها, ويتحول العنصر الاخير الى العنصر الاول, وهكذا

linked_list_reverse_0.jpg

في البداية ننتقل – عبر التجوال ضمن القائمة المتصلة – الى اخر عنصر ضمن القائمة المتصلة. والذي يؤشر مؤشر Next ضمنه الى القيمة null. والآن, يجب ان ندعه يؤشر الى العنصر قبل الاخير ضمن القائمة المتصلة.

linked_list_reverse_1.jpg

يجب ان نتاكد من عدم فقدان العقدة الاخيرة. لذلك سنلجأ الى بعض العقد المؤقته, والتي ستبدو مشاببه للعقدة الرئيسية head node, وتشير الى العقدة الاخيرة last node
يجب علينا الآن جعل كل الروابط التي تشير الى العنصر التالي في القائمة المتصلة, تشير للعنصر السابق previous .

linked_list_reverse_1.jpg

باستثناء العقدة الاولى التي يجب ان تؤشر الى القيمة null.

linked_list_reverse_2.jpg

الآن, يجب ان نجعل عقدة الرأس head node تشير الى اول عقدة وذلك بالاستفادة من العقدة المؤقته

linked_list_reverse_4.jpg

تم عكس القائمة المتصلة الان.

فيما يلي كود عملية العكس باستخدام لغة C

implementation in c

عملية عكس القائمة المتصلة باستخدام لغة سي

العملية ليست بهذا الوضوع وتحتاج الى خيال, وتجريب رسم السلسلة على الورق وفهم العملية بشكل جيد عبر تطبيق الخطوات.

والى لقاء في درس جديد نتحدث فيه عن القائمة المتصلة المضاعفة double linked list

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
http://www.baeldung.com/java-hill-climbing-algorithm

 

 

 

, , , , , , , , , , ,

أضف تعليق