قائمة انتظار دائرية في C: كيفية التنفيذ؟

يتم ترتيب البيانات في قائمة انتظار دائرية في نمط دائري حيث يتم توصيل العنصر الأخير بالعنصر الأول. على عكس قائمة الانتظار الخطية حيث يتم تنفيذ المهام على FIFO (First In First Out) ، قد يتغير ترتيب قائمة الانتظار الدائري لتنفيذ المهمة. يمكن إجراء عمليات الإدراج والحذف في أي موضع.

الطابور الدائري أكثر كفاءة من الطابور الخطي. في التمثيل الرسومي لقائمة انتظار دائرية ، يمكنك ملاحظة أن الموضعين الأمامي والخلفي متصلان ، مما يجعله دائرة حيث يتم تنفيذ العمليات دائمًا على أساس ما يرد أولاً يصرف أولاً (FIFO). تتم إضافة كل عنصر جديد في النهاية الخلفية وحذفه من الواجهة الأمامية. قائمة الانتظار الدائرية لها استخدام أفضل ولها تعقيد زمني لـ O (1).

مصدر

تطبيقات قائمة انتظار دائرية

• جدولة وحدة المعالجة المركزية (CPU): تستفيد قوائم الانتظار الدائرية من مساحات الذاكرة الفارغة الموجودة في قوائم الانتظار الخطية.
• نظام المرور: في نظام المرور ، بمساعدة قوائم الانتظار الدائرية ، يتم تشغيل إشارات المرور في الفاصل الزمني المحدد.
• إدارة الذاكرة: تحافظ أنظمة التشغيل بشكل متكرر على مجموعة من العمليات المعدة للتنفيذ أو التي تنتظر حدوث حدث معين.

تعلم: برنامج C لفرز الفقاعات: فرز الفقاعات في C.

نموذج كود مع شرح

السطر 1: // (1) المعالجات المسبقة

السطر 2: // تعيين حد قائمة الانتظار على 5 عناصر

السطر 3: # تضمين <stdio.h>

السطر 4: # تعريف LIM 5

السطر 5: // (2) إقرارات نوع بيانات قائمة الانتظار

السطر 6: // البيانات تحمل البيانات ؛ delPos ، موضع الحذف منه ؛ الطول ، لا. من

السطر 7: // العناصر الموجودة حاليًا في قائمة الانتظار

السطر 8: قائمة انتظار بنية typedef {

السطر 9: int data [LIM]، delPos، length؛

السطر 10:} س ؛

السطر 11: // (3) الإعلانات العالمية

السطر 12: // الوظائف والمتغير العام q لنوع قائمة الانتظار الهيكلية

السطر 13: Q q ؛

السطر 14: void ui_Q_Ops () ، insertQel () ، deleteQel () ، displayQels () ، initQ () ؛

السطر 15: // (4) يستدعي وظيفة UI بعد التهيئة

السطر 16: int main ()

السطر 17: {

السطر 18: initQ () ؛

السطر 19: ui_Q_Ops () ؛

السطر 20: إرجاع 0 ؛

السطر 21:}

السطر 22: // (5) تهيئة قائمة الانتظار

السطر 23: initQ () باطلة

السطر 24: {

السطر 25: q.length = 0 ؛

السطر 26: q.delPos = 0 ؛

السطر 27:}

السطر 28: // (6) تستدعي حلقة قائمة على الوظائف الصحيحة

السطر 29: باطل ui_Q_Ops ()

السطر 30: {

السطر 31: اختيار int = 0 ؛

السطر 32: حرف الإدخال [16] ؛

السطر 33: بينما (الاختيار! = 4) {

السطر 34: printf ("\ n ———————- \ n")؛

السطر 35: printf ("1. إدراج في قائمة الانتظار \ n")؛

السطر 36: printf ("2. حذف من قائمة الانتظار \ n") ؛

السطر 37: printf ("3. عرض عناصر قائمة الانتظار \ n")؛

السطر 38: printf ("4. إنهاء البرنامج \ n") ؛

السطر 39: printf ("أدخل الاختيار:") ؛

السطر 40: إذا (fgets (input، 15، stdin)! = NULL) {

السطر 41: إذا (sscanf (إدخال ، “٪ d” ، & اختيار) == 1) {

السطر 42: التبديل (اختيار) {

السطر 43: الحالة 1: insertQel () ؛

السطر 44: كسر ؛

السطر 45: الحالة 2: deleteQel () ؛

السطر 46: كسر ؛

السطر 47: الحالة 3: displayQels () ؛

السطر 48: استراحة ؛

السطر 49: الحالة 4: إرجاع ؛

السطر 50: الافتراضي: printf ("اختيار غير صالح \ n")؛

السطر 51: تابع ؛

السطر 52:}

السطر 53:} else

السطر 54: printf ("اختيار غير صالح \ n")؛

السطر 55:}

السطر 56:}

السطر 57:}

السطر 58: // (7) إدراج في قائمة الانتظار

سطر 59: // إذا كان الطول هو نفسه حد MAX ، فإن قائمة الانتظار ممتلئة ، وإلا أدخل

السطر 60: // تحقق دائريًا بطول المجموع ومعامل delPos بحد أقصى

السطر 61: // وطول الزيادة

السطر 62: إدخال باطل

السطر 63: {

السطر 64: int el، inspos؛

السطر 65: حرف الإدخال [16] ؛

السطر 66: إذا (q.length == LIM) {

السطر 67: printf ("قائمة الانتظار ممتلئة \ n")؛

السطر 68: العودة ؛

السطر 69:}

السطر 70: inspos = (q.delPos + q.length)٪ LIM ؛

السطر 71: printf ("أدخل عنصرًا لإدراجه:") ؛

السطر 72: إذا (fgets (input، 15، stdin)! = NULL) {

السطر 73: if (sscanf (input، “٪ d”، & el)) {

السطر 74: q.data [inspos] = el ؛

السطر 75: q.length ++ ؛

سطر 76:} else

السطر 77: printf ("إدخال غير صالح \ n") ؛

السطر 78:}

السطر 79:}

السطر 80: // (8) حذف من قائمة الانتظار

السطر 81: // إذا كان الطول 0 ، فإن قائمة الانتظار فارغة ، وإلا احذف في delPos

خط 82: // وطول الإنقاص

السطر 83: void deleteQel ()

السطر 84: {

السطر 85: إذا (q.length == 0) {

السطر 86: printf ("قائمة الانتظار فارغة \ n")؛

السطر 87:} else {

السطر 88: printf ("العنصر المحذوف٪ d \ n" ، q.data [q.delPos])؛

السطر 89: q.delPos = (q.delPos + 1)٪ LIM ؛

السطر 90: q.length– ؛

السطر 91:}

السطر 92:}

سطر 93: // (9) عرض عناصر قائمة الانتظار

السطر 94: // اعرض بطريقة دائرية تدير حلقة تبدأ من delPos

السطر 95: // وإضافة مكرر ومعامل بحد أقصى

السطر 96: عرض باطل

السطر 97: {

السطر 98: int i ؛

السطر 99: إذا (q.length == 0) {

السطر 100: printf ("قائمة الانتظار فارغة \ n")؛

السطر 101:} else {

السطر 102: printf ("عناصر الطابور هي:")؛

السطر 103: لـ (i = 0؛ i <q.length؛ i ++) {

السطر 104: printf ("٪ d" ، q.data [(q.delPos + i)٪ LIM])؛

السطر 105:}

السطر 106: printf (”\ n“) ؛

السطر 107:}

السطر 108:}

خط 109:

المخرجات:

العمليات في قائمة انتظار دائرية

1. insertQel () - إدراج عنصر في قائمة الانتظار الدائري

في قائمة انتظار دائرية ، تُستخدم الدالة enQueue () لإدراج عنصر في قائمة الانتظار الدائرية. في قائمة انتظار دائرية ، يتم دائمًا إدراج الميزة الجديدة في الموضع الخلفي. تأخذ الدالة enQueue () قيمة عدد صحيح كمعامل وتدرجها في قائمة الانتظار الدائرية. يتم تنفيذ الخطوات التالية لإدراج عنصر في قائمة الانتظار الدائرية:

الخطوة 1 - تحقق مما إذا كان الطول مطابقًا للحد الأقصى. إذا كان هذا صحيحًا ، فهذا يعني أن قائمة الانتظار ممتلئة. إذا كانت ممتلئة ، فقم بعرض "قائمة الانتظار ممتلئة" وإنهاء الوظيفة.

الخطوة 2 - إذا لم تكن ممتلئة ، فقم بإدخال القيمة التي تم تحقيقها بشكل دائري مع مجموع الطول ومعامل delPos بحد أقصى وطول الزيادة

2. deleteQel () - حذف عنصر من قائمة الانتظار الدائري

في قائمة انتظار دائرية ، deQueue () هي وظيفة تُستخدم لحذف عنصر من قائمة الانتظار الدائرية. في قائمة انتظار دائرية ، يتم دائمًا حذف العنصر من الموضع الأمامي. لا تأخذ الدالة deQueue () أي قيمة كمعامل. يتم تنفيذ الخطوات التالية لحذف عنصر من قائمة الانتظار الدائرية ...

الخطوة 1 - تحقق مما إذا كانت قائمة الانتظار فارغة. (أمامي == -1 && خلفي == -1)

الخطوة 2 - إذا كانت فارغة ، فقم بعرض "قائمة الانتظار فارغة" وإنهاء الوظيفة.

الخطوة 3 - إذا لم تكن فارغة ، فقم بعرض العناصر المحذوفة وفقًا للمواضع. بعد إضافة كل عنصر ، انتقل إلى الوضع التالي لحد تعديل قائمة الانتظار.

3. displayQels () - تعرض عناصر Queue الموجودة في Circular Queue. يتم تنفيذ الخطوات التالية لعرض عناصر قائمة انتظار دائرية:

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

الخطوة 2 - إذا كان الطول 0 ، فهو فارغ ، ثم اعرض "قائمة الانتظار فارغة" وإنهاء الوظيفة.

الخطوة 3 - إذا لم تكن فارغة ، فحدد متغير عدد صحيح "i".

الخطوة 4 - اضبط i على 0.

الخطوة 5 - مرة أخرى ، اعرض العناصر وفقًا للموضع وقيمة الزيادة بواحد (i ++). كرر الأمر نفسه حتى يصبح "i <q.length" خطأ.

يمكن تطبيق Circular Queue باستخدام القائمة المرتبطة أيضًا. فيما يلي الخوارزميات:

• خوارزمية Enqueue:

إذا (FRONT == NULL) // الإدراج في قائمة انتظار فارغة

الجبهة = الخلفي = العقدة الجديدة

إنهاء إذا

آخر

REAR -> next = newNode // الإدراج بعد العنصر الأخير

الخلفي = عقدة جديدة

نهاية أخرى

الخلفي -> التالي = الجبهة

Enqueue النهاية

• خوارزمية Dequeue:

إذا (FRONT == NULL) // حالة التدفق السفلي

طباعة "قائمة الانتظار Underflow"

نهاية ديكيو

إنهاء إذا

وإلا إذا (FRONT == REAR) // تحتوي قائمة الانتظار على عقدة واحدة فقط

temp = الجبهة -> البيانات

مجاني (درجة الحرارة)

الجبهة = الجبهة -> التالي

الخلفي -> التالي = الجبهة

إنهاء إذا

وإلا إذا (FRONT == N - 1) // إذا كانت FRONT هي العقدة الأخيرة

front = 0 // Make FRONT كعقدة أولى

إنهاء إذا

نهاية ديكيو

اقرأ أيضًا: Python Vs C: مقارنة كاملة جنبًا إلى جنب

خاتمة

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

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

سيساعدك التعرف على عقليتهم وعملية تفكيرهم. وأحد الأشياء الرائعة التي تحصل عليها في upGrad هو أنه يمكنك اختيار خيارات EMI والاسترخاء على جيوبك.

نأمل أن تحظى بفرصة تعليمية ممتازة في تنفيذ مشاريع سي هذه. إذا كنت مهتمًا بمعرفة المزيد وتحتاج إلى إرشاد من خبراء الصناعة ، فراجع دبلوم upGrad & IIIT Banglore PG في تطوير برامج Full-Stack .