بعد المصفوفات ، ثاني أكثر بنية البيانات شيوعًا هي القائمة المرتبطة. القائمة المرتبطة هي بنية بيانات خطية ، تتكون من سلسلة من العقد تحتوي كل عقدة فيها على قيمة ومؤشر إلى العقدة التالية في السلسلة. في هذه المقالة ، دعونا نرى كيفية تنفيذ قائمة مرتبطة في C.
ما هي القائمة المرتبطة في سي؟
القائمة المرتبطة هي بنية بيانات خطية. تتكون كل قائمة مرتبطة من جزأين ، قسم البيانات وقسم العنوان الذي يحتوي على عنوان العنصر التالي في القائمة ، والذي يسمى العقدة.
حجم القائمة المرتبطة غير ثابت ، ويمكن إضافة عناصر البيانات في أي مواقع في القائمة. العيب هو أنه للوصول إلى عقدة ، يجب أن ننتقل إلى كل الطريق من العقدة الأولى إلى العقدة التي نحتاجها. القائمة المرتبطة تشبه المصفوفة ولكنها على عكس المصفوفة ، لا يتم تخزينها بالتسلسل في الذاكرة.
أكثر أنواع القوائم المرتبطة شيوعًا هي:
مثال على قائمة مرتبطة
التنسيق: [البيانات ، العنوان]
الرأس -> [3،1000] -> [431001] -> [211002]
في المثال ، الرقم 43 موجود في الموقع 1000 والعنوان موجود في العقدة السابقة. هذه هي الطريقة التي يتم بها تمثيل القائمة المرتبطة.
وظائف القائمة المرتبطة الأساسية
هناك العديد من الوظائف التي يمكن تنفيذها في القائمة المرتبطة في C. دعنا نحاول فهمها بمساعدة برنامج مثال.أولاً ، نقوم بإنشاء قائمة ، وعرضها ، وإدراجها في أي مكان ، وحذف موقع. سيوضح لك الكود التالي كيفية إجراء العمليات في القائمة.
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () structure node {int info architecture node * next} Structure node * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3. أدخل في البداية n ') printf (' n 4. أدخل في النهاية n ') printf (' n 5. أدخل في الموضع المحدد n ') printf (' n 6.الحذف من البداية n ') printf (' n 7.حذف من النهاية n ') printf (' n 8.الحذف من الموضع المحدد n ') printf (' n 9.Exit n ') printf (' n ----------------- --------------------- n ') printf (' أدخل اختيارك: t ') scanf ('٪ d '، والاختيار) التبديل (الاختيار) {الحالة 1 : إنشاء () حالة الكسر 2: عرض () حالة الكسر 3: insert_begin () حالة الفاصل 4: insert_end () حالة الفاصل 5: insert_pos () حالة الفاصل 6: delete_begin () حالة الفاصل 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d create () {Struct node * temp، * ptr temp = (عقدة البنية *) malloc (sizeof (عقدة البنية)) إذا (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('n أدخل قيمة البيانات للعقدة: t') scanf ('٪ d'، & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} عرض باطل () {عقدة الهيكل * ptr إذا (البداية == NULL) {printf ('nList فارغة: n ') return} else {ptr = start printf (' n عناصر القائمة هي: n ') while (ptr! = NULL) {printf ('٪ dt '، ptr-> info) ptr = ptr-> next}}} void insert_begin () {Struct node * temp temp = (عقدة البنية *) malloc (sizeof (عقدة البنية)) إذا (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('n أدخل قيمة البيانات للعقدة: t ') scanf ('٪ d '، & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start = temp }} void insert_end () {Struct node * temp، * ptr temp = (عقدة البنية *) malloc (sizeof (عقدة البنية)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} ص rintf ('n أدخل قيمة البيانات للعقدة: t') scanf ('٪ d'، & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {Struct node * ptr، * temp int i، pos temp = (عقدة البنية *) malloc ( sizeof (عقدة الهيكل)) إذا (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('n أدخل موضع العقدة الجديدة المراد إدراجها: t') scanf ('٪ d' ، & pos) printf ('n أدخل قيمة بيانات العقدة: t') scanf ('٪ d'، & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start = temp} else {for (i = 0، ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [التعامل بعناية] n') return}} temp-> next = ptr-> ptr التالي -> التالي = temp}} void delete_begin () {Struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' العنصر المحذوف هو:٪ dt '، ptr-> info) free (ptr)}} void delete_end () {Struct node * temp، * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('n العنصر المحذوف:٪ dt'، ptr-> info) free (ptr)} else {ptr = start while (ptr- > التالي! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('n العنصر المحذوف هو:٪ dt'، ptr-> info) free (ptr)}} void delete_pos () {int i، pos Struct node * temp، * ptr if (start == NULL) {printf ('n The List is Empty: n') exit (0)} else {printf ('n أدخل موضع العقدة المراد حذفها : t ') scanf ('٪ d '، & pos) if (pos == 0) {ptr = start start = start-> next printf (' n العنصر المحذوف هو:٪ dt '، ptr-> info) مجاني (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('n العنصر المحذوف هو: ٪ dt '، ptr-> معلومات) مجانية (ptr)}}}الجزء الأول من هذا الرمز هو إنشاء هيكل. يتم إنشاء بنية قائمة مرتبطة بحيث يمكنها الاحتفاظ بالبيانات والعنوان كما نحتاج إليها. يتم ذلك لإعطاء المترجم فكرة عن الكيفية التي يجب أن تكون بها العقدة.
عقدة البنية {int info Struct node * next}في الهيكل ، لدينا متغير بيانات يسمى info للاحتفاظ بالبيانات ومتغير مؤشر للإشارة إلى العنوان. هناك العديد من العمليات التي يمكن إجراؤها في قائمة مرتبطة ، مثل:
- خلق()
- عرض()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
يتم استدعاء هذه الوظائف من خلال الوظيفة الرئيسية القائمة على القائمة. في الوظيفة الرئيسية ، نأخذ مدخلات من المستخدم بناءً على العملية التي يريد المستخدم القيام بها في البرنامج. ثم يتم إرسال الإدخال إلى حالة التبديل وبناءً على إدخال المستخدم.
بناءً على المدخلات المقدمة ، سيتم استدعاء الوظيفة. بعد ذلك ، لدينا وظائف مختلفة يجب حلها. دعونا نلقي نظرة على كل من هذه الوظائف.
فئة __init__ بيثون
خلق وظيفة
أولاً ، هناك وظيفة إنشاء لإنشاء القائمة المرتبطة. هذه هي الطريقة الأساسية لإنشاء القائمة المرتبطة. دعنا نلقي نظرة على الكود.
إنشاء باطل () {عقدة البنية * درجة الحرارة ، * ptr printf ('n أدخل قيمة البيانات للعقدة: t') scanf ('٪ d'، & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}انتاج |
أولاً ، يتم إنشاء مؤشرين من النوع العقدة و ptr و temp . نحن نأخذ القيمة المطلوبة لإضافتها في القائمة المرتبطة من المستخدم ونخزنها في جزء المعلومات من المتغير المؤقت ونقوم بتعيين درجة الحرارة التالية التي هي جزء العنوان إلى قيمة خالية. يوجد مؤشر بدء يحمل بداية القائمة. ثم نتحقق من بداية القائمة. إذا كانت بداية القائمة فارغة ، فسنقوم بتعيين temp لمؤشر البداية. وإلا فإننا ننتقل إلى النقطة الأخيرة حيث تمت إضافة البيانات.
لهذا ، نقوم بتعيين ptr قيمة البداية والاجتياز حتى ptr-> التالي = فارغ . ثم نقوم بتعيين ptr-> التالي عنوان درجة الحرارة. وبطريقة مماثلة ، يوجد رمز مُعطى للإدخال في البداية ، والإدخال في النهاية والإدخال في مكان محدد.
وظيفة العرض
إليك رمز وظيفة العرض.
عرض باطل () {عقدة البنية * ptr إذا (البداية == NULL) {printf ('nList فارغة: n') إرجاع} آخر {ptr = بدء printf ('n عناصر القائمة هي: n') بينما (ptr! = NULL) {printf ('٪ dt'، ptr-> info) ptr = ptr-> التالي}}}انتاج |
في وظيفة العرض ، نتحقق أولاً مما إذا كانت القائمة فارغة ونعيدها إذا كانت فارغة. في الجزء التالي ، نقوم بتعيين قيمة البداية إلى ptr. نقوم بعد ذلك بتشغيل حلقة حتى يصبح ptr فارغًا ونطبع عنصر البيانات لكل عقدة ، حتى يصبح ptr فارغًا ، مما يحدد نهاية القائمة.
حذف الوظيفة
إليك مقتطف الشفرة لحذف عقدة من القائمة المرتبطة.
void delete_pos () {int i، pos Struct node * temp، * ptr if (start == NULL) {printf ('n The List is Empty: n') exit (0)} else {printf ('n أدخل موضع العقدة المراد حذفها: t ') scanf ('٪ d '، & pos) if (pos == 0) {ptr = start start = start-> next printf (' n العنصر المحذوف هو:٪ dt '، ptr-> info ) free (ptr)} else {ptr = البدء لـ (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe العنصر المحذوف:٪ dt '، ptr-> info) free (ptr)}}}انتاج |
في عملية الحذف ، يتحقق أولاً مما إذا كانت القائمة فارغة أم لا ، إذا كانت موجودة. إذا لم يكن فارغًا ، فإنه يطلب من المستخدم حذف الوظيفة. بمجرد دخول المستخدم إلى المنصب ، فإنه يتحقق مما إذا كان هو الموضع الأول ، وإذا كان الجواب نعم ، فإنه يعين ptr لبدء وتحريك مؤشر البدء إلى الموقع التالي وحذف ptr. إذا كان الموضع ليس صفرًا ، ثم يتم تشغيل حلقة for من 0 إلى نقطة البيع التي أدخلها المستخدم وتخزينها في ملف نقاط البيع متغير. هناك عبارة if لتحديد ما إذا كان المركز الذي تم إدخاله غير موجود. إذا ptr يساوي فارغًا ، إذن فهو غير موجود.
نحن تعيين ptr إلى temp في الحلقة for ، ثم ينتقل ptr إلى الجزء التالي. بعد هذا عندما تم العثور على الموقف. نصنع متغير temp ليحتفظ بقيمة ptr-> التالي وبالتالي تخطي ptr. ثم يتم حذف ptr. وبالمثل ، يمكن القيام بذلك لحذف العنصر الأول والأخير.
قائمة مرتبطة بشكل مضاعف
تسمى القائمة المرتبطة بشكل مضاعف لأن هناك اثنين مؤشرات ، نقطة واحدة إلى العقدة التالية ونقاط أخرى إلى العقدة السابقة. تشبه العمليات التي يتم إجراؤها في حالة الارتباط المزدوج عمليات القائمة المرتبطة بشكل فردي. هذا هو رمز العمليات الأساسية.
#include #include architecture نوع العقدة بنية العقدة * PtrToNode typedef قائمة PtrToNode typedef PtrToNode Position Structure Node {int e Position السابق Position next} void insert (int x، List l، Position p) {Position TmpCell TmpCell = (Struct Node *) malloc (sizeof (Struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} حذف باطل (int x، List l) {Position p، p1، p2 p = Find (x، l) if (p! = NULL) {p1 = p -> السابق p2 = p -> التالي p1 - > التالي = p -> التالي إذا (p2! = NULL) // إذا لم تكن العقدة هي العقدة الأخيرة p2 -> السابقة = p -> السابقة} else printf ('العنصر غير موجود !!! n')} فارغ عرض (قائمة l) {printf ('عنصر القائمة ::') الموضع p = l-> التالي بينما (p! = NULL) {printf ('٪ d ->'، p-> e) p = p- > التالي}} int main () {int x، pos، ch، i List l، l1 l = (Struct Node *) malloc (sizeof (Struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('تنفيذ قائمة مرتبطة بشكل مزدوج لـ L. IST ADTnn ') نفذ {printf (' nn1. إنشاء 2. حذف 3. عرض 4. قم بإدخال الخيار :: ') scanf ('٪ d '، & ch) switch (ch) {case 1: p = l printf (' أدخل العنصر المراد إدراجه :: ') scanf ('٪ d'، & x) printf ('أدخل موضع العنصر ::') scanf ('٪ d'، & pos) لـ (i = 1 inext} أدخل (x، l، p) حالة الكسر 2: p = l printf ('أدخل العنصر المراد حذفه ::') scanf ('٪ d'، & x) حذف (x، p) حالة الفاصل 3: العرض (ل) كسر}} بينما (الفصل<4) } انتاج |
لذا ، كما ترى ، فإن مفهوم العمليات بسيط للغاية. تحتوي القائمة المرتبطة بشكل مضاعف على نفس عمليات القائمة المرتبطة بشكل فردي في لغة البرمجة C. الاختلاف الوحيد هو أن هناك متغير عنوان آخر يساعد في اجتياز القائمة بشكل أفضل في قائمة مرتبطة بشكل مضاعف.
آمل أن تكون قد فهمت كيفية إجراء العمليات الأساسية في قائمة مرتبطة بشكل فردي ومزدوج في C.
إذا كنت ترغب في تعلم القائمة المرتبطة بجافا ، فإليك أ .
إذا صادفت أي أسئلة ، فلا تتردد في طرح جميع أسئلتك في قسم التعليقات في 'قائمة مرتبطة في C' وسيسعد فريقنا بالإجابة.