قائمة (نوع بيانات مجرد)

📅 آخر تحديث: ٢١ يوليو ٢٠٢٦
✍️ نُشر في: ٢١ يوليو ٢٠٢٦
📷 يحتوي على 6 صور
الموسوعة الحرة

في علم الحاسوب ، تُعرَّف القائمة أو المتتالية بأنها مجموعة من العناصر ذات عدد محدود وبترتيب معين . وتُعدّ القائمة تمثيلاً حاسوبياً للمفهوم الرياضي للزوج المرتب أو المتتالية المحدودة .

قد تحتوي القائمة على نفس القيمة أكثر من مرة، ويعتبر كل ظهور عنصرًا مميزًا.

بنية قائمة مرتبطة أحادية، تُنفذ قائمة بثلاثة عناصر عددية صحيحة.

يُستخدم مصطلح " قائمة" أيضًا للإشارة إلى العديد من هياكل البيانات الملموسة التي يمكن استخدامها لتنفيذ القوائم المجردة ، وخاصة القوائم المتصلة والمصفوفات . في بعض السياقات، مثل برمجة لغة ليسب ، قد يشير مصطلح " قائمة " تحديدًا إلى قائمة متصلة بدلًا من مصفوفة. في البرمجة القائمة على الأصناف ، تُقدَّم القوائم عادةً كأمثلة لأصناف فرعية من صنف "قائمة" عام، ويتم اجتيازها عبر مُكرِّرات منفصلة .

تدعم العديد من لغات البرمجة أنواع بيانات القوائم ، ولها قواعد نحوية ودلالات خاصة بالقوائم وعملياتها. يمكن إنشاء القائمة عادةً بكتابة عناصرها بالتسلسل، مفصولة بفواصل أو فواصل منقوطة أو مسافات ، ضمن زوج من المحددات مثل الأقواس () أو الأقواس المربعة ([]) أو المعقوفات المعقوفة ({}) أو الأقواس الزاوية (<>). قد تسمح بعض اللغات بفهرسة أنواع القوائم أو تقسيمها كما هو الحال مع أنواع المصفوفات ، وفي هذه الحالة يُوصف نوع البيانات بدقة أكبر بأنه مصفوفة.

في نظرية الأنواع والبرمجة الوظيفية ، يتم تعريف القوائم المجردة عادةً استقرائيًا من خلال عمليتين: nil التي تنتج قائمة فارغة، و cons التي تضيف عنصرًا في بداية القائمة. [ 1 ]

التيار هو النظير اللانهائي المحتمل للقائمة. [ 2 ] : §3.5

العمليات

قد يوفر تطبيق بنية بيانات القائمة بعضًا من العمليات التالية أو جميعها كعناصر أساسية منخفضة المستوى:

  • أنشئ قائمة فارغة
  • اختبار ما إذا كانت القائمة فارغة
  • أضف عنصرًا إلى القائمة
  • أضف عنصرًا في نهاية القائمة
  • الحصول على العنصر الأول أو الأخير من قائمة
  • احصل على باقي القائمة بعد العنصر الأول أو الأخير
  • احصل على عنصر باستخدام فهرس موقعه في القائمة
  • أنشئ قائمة تحتوي على عنصر واحد محدد
  • أنشئ قائمة تحتوي على العناصر المحددة
  • أضف قائمتين
  • map، flatmap، filter، reduce، إلخ.

التطبيقات

يتم تنفيذ القوائم عادةً إما كقوائم مرتبطة (إما مرتبطة بشكل فردي أو مزدوج) أو كمصفوفات ، وعادةً ما تكون ذات طول متغير أو مصفوفات ديناميكية .

الطريقة القياسية لتنفيذ القوائم، والتي نشأت مع لغة البرمجة ليسب ، هي أن يحتوي كل عنصر من عناصر القائمة على قيمته ومؤشر يُشير إلى موقع العنصر التالي في القائمة. ينتج عن ذلك إما قائمة مرتبطة أو شجرة ، وذلك بحسب ما إذا كانت القائمة تحتوي على قوائم فرعية متداخلة. بعض تطبيقات ليسب القديمة (مثل تطبيق ليسب لجهاز Symbolics 3600) دعمت أيضًا "القوائم المضغوطة" (باستخدام ترميز CDR ) التي كان لها تمثيل داخلي خاص (غير مرئي للمستخدم). يمكن التعامل مع القوائم باستخدام التكرار أو الاستدعاء الذاتي . يُفضل استخدام التكرار غالبًا في لغات البرمجة الإجرائية ، بينما يُعد الاستدعاء الذاتي هو القاعدة في اللغات الوظيفية .

يمكن تنفيذ القوائم كأشجار بحث ثنائية متوازنة ذاتيًا تحتوي على أزواج من الفهرس والقيمة، مما يوفر وصولًا متساويًا لأي عنصر (على سبيل المثال، جميع العناصر الموجودة على الحافة، والعقد الداخلية التي تخزن فهرس العنصر الفرعي الأيمن، والذي يُستخدم لتوجيه البحث)، ويستغرق وقتًا يتناسب لوغاريتميًا مع حجم القائمة، ولكن طالما أنه لا يتغير كثيرًا، فإنه سيوفر وهم الوصول العشوائي ويُمكّن عمليات التبديل والإضافة والإلحاق في وقت لوغاريتمي أيضًا. [ 3 ]

دعم لغات البرمجة

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

في لغة ليسب ، تُعدّ القوائم نوع البيانات الأساسي، ويمكنها تمثيل كلٍّ من شيفرة البرنامج والبيانات. في معظم لهجات ليسب، يمكن كتابة قائمة الأعداد الأولية الثلاثة الأولى على النحو التالي (list 2 3 5): . في العديد من لهجات ليسب، بما في ذلك سكيم ، تُعرَّف القائمة بأنها مجموعة من الأزواج، تتكون من قيمة ومؤشر إلى الزوج التالي (أو قيمة فارغة)، مما يُشكِّل قائمة مرتبطة أحادية. [ 5 ]

التطبيقات

على عكس المصفوفة ، يمكن للقائمة أن تتوسع وتتقلص.

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

تشكل القوائم أيضًا الأساس لأنواع البيانات المجردة الأخرى بما في ذلك قائمة الانتظار والمكدس وتنوعاتها.

تعريف مجرد

يتم تعريف نوع القائمة المجردة L الذي يحتوي على عناصر من نوع E ( قائمة أحادية الشكل ) بواسطة الدوال التالية:

لا شيء: () → L
السلبيات: E × L → L
أولاً: L → E
راحة: يسار → يسار

مع البديهيات

first (cons ( e , l )) = e
rest (cons ( e , l )) = l

لأي عنصر e وأي قائمة l . من البديهي أن

cons ( e , l ) ≠ l
cons ( e , l ) ≠ e
cons ( e1 , l1 ) = cons ( e2 , l2 ) إذا كان e1 = e2 و l1 = l2​​

لاحظ أن first (nil ()) و rest (nil ()) غير معرفين.

هذه البديهيات تعادل تلك الخاصة بنوع بيانات المكدس المجرد .

في نظرية الأنواع ، يُعتبر التعريف أعلاه ببساطة نوعًا استقرائيًا مُعرَّفًا بدلالة المُنشئين: nil و cons . جبريًا، يُمكن تمثيل ذلك بالتحويل 1 + E × L → L. يتم الحصول على first و rest من خلال مطابقة الأنماط على المُنشئ cons ومعالجة حالة nil بشكل منفصل .

موناد القائمة

يشكل نوع القائمة مونادًا بالوظائف التالية (باستخدام E * بدلاً من L لتمثيل القوائم أحادية الشكل التي تحتوي على عناصر من النوع E ):

يعود:أ→أ*=أ↦سلبياتألا شيء{\displaystyle {\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}}
ربط:أ*→(أ→ب*)→ب*=ل↦و↦{لا شيءلو ل=لا شيءإلحاق(وأ)(ربطل′و)لو ل=سلبياتأل′{\displaystyle {\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}}

حيث يتم تعريف الإلحاق على النحو التالي:

إلحاق:أ*→أ*→أ*=ل1↦ل2↦{ل2لو ل1=لا شيءسلبياتأ(إلحاقل1′ل2)لو ل1=سلبياتأل1′{\displaystyle {\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}}

بدلاً من ذلك، يمكن تعريف الموناد من حيث العمليات return و fmap و join ، مع:

fmap:(أ→ب)→(أ*→ب*)=و↦ل↦{لا شيءلو ل=لا شيءسلبيات(وأ)(fmapول′)لو ل=سلبياتأل′{\displaystyle {\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}}
ينضم:أ**→أ*=ل↦{لا شيءلو ل=لا شيءإلحاقأ(ينضمل′)لو ل=سلبياتأل′{\displaystyle {\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}}

لاحظ أن fmap و join و append و bind محددة جيدًا، لأنها تُطبق على وسائط أعمق تدريجيًا في كل استدعاء متكرر.

نوع القائمة هو أحادي جمعي، مع nil كصفر أحادي و append كمجموع أحادي.

تُشكّل القوائم مجموعة أحادية تحت عملية الإلحاق . العنصر المحايد لهذه المجموعة الأحادية هو القائمة الفارغة، nil . في الواقع، هذه هي المجموعة الأحادية الحرة على مجموعة عناصر القائمة.

انظر أيضاً

  • نوع بيانات المصفوفة – نوع بيانات يمثل مجموعة مرتبة من العناصر (القيم أو المتغيرات). صفحات تعرض أوصافًا مختصرة لأهداف إعادة التوجيه 
  • الطابور – نوع بيانات مجرد 
  • مجموعة - نوع بيانات مجرد لتخزين القيم المميزة 
  • المكدس – نوع بيانات مجرد 
  • التدفق – سلسلة من عناصر البيانات المتاحة بمرور الوقت 

مراجع

  1. ↑ رينغولد، إدوارد؛ نيفيرجيلت، يورغ؛ نارسينغ، ديو (1977). الخوارزميات التوافقية: النظرية والتطبيق . إنجلوود كليفس، نيو جيرسي: برنتيس هول. الصفحات 38-41 . ISBN  0-13-152447-X.
  2. ↑ أبيلسون، هارولد؛ سوسمان، جيرالد جاي (1996). بنية وتفسير برامج الحاسوب . مطبعة معهد ماساتشوستس للتكنولوجيا.
  3. ↑ بارنيت، جرانفيل؛ ديل تونغا، لوكا (2008). "هياكل البيانات والخوارزميات" (ملف PDF) . mta.ca. تم الاطلاع عليه بتاريخ 12 نوفمبر 2014 .
  4. ^ ليروسالمشي ، روبرتو (ديسمبر 2003). البرمجة في لوا (الطبعة الأولى) ( الطبعة الأولى). لوا.org. رقم ISBN  8590379817تم الاطلاع عليه بتاريخ 12 نوفمبر 2014 .
  5. ↑ ستيل، جاي (1990). لغة ليسب الشائعة ( الطبعة الثانية). دار النشر الرقمية. الصفحات 29-31 . ISBN   1-55558-041-6.