רשימה (מבנה נתונים)

מבנה נתונים
ערך מחפש מקורות
רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים.
אנא עזרו לשפר את אמינות הערך באמצעות הבאת מקורות לדברים ושילובם בגוף הערך בצורת קישורים חיצוניים והערות שוליים.
אם אתם סבורים כי ניתן להסיר את התבנית, ניתן לציין זאת בדף השיחה.

רשימהאנגלית: List או Sequence) היא מבנה נתונים מופשט שתוכנו בעל סדר חלקי ועשוי להכיל חזרות (כלומר עשויים להימצא בו מספר איברים שקולים). מימוש של רשימה הוא למעשה ייצוג ממוחשב של סדרה מתמטית סופית.

רשימה חד-כיוונית מקושרת, בעלת 3 איברים המכילים ערכים שלמים

על פי רוב, מימוש רשימה במחשב ייעשה על ידי שימוש במערך או ברשימה מקושרת. שפות תכנות רבות כוללות מימוש כלשהו של רשימה, ושפות תכנות פונקציונליות או לוגיות (כמו Haskell או פרולוג) תומכות על פי רוב ברשימה כטיפוס בסיסי בשפה.

רשימה היא מבנה נתונים "חלש", כלומר ניתן להתייחס למבני נתונים אחרים כאל רשימה לה נוספו הגבלות:

  • קבוצה היא רשימה שמתעלמים בה מהסדר, ושלא מאפשרת חזרות (ייצוג של קבוצה מתמטית).
  • מחסנית היא רשימה בה האיברים מסודרים לפי מועד הוספתם, וניתן לגשת רק לאיבר האחרון שנוסף אליה (LIFO).
  • תור הוא רשימה בה האיברים מסודרים לפי מועד הוספתם, וניתן לגשת רק לפריט הראשון שנוסף אליה (FIFO).
  • רשימה שבין איבריה לא מוגדר סדר היא הכללה של קבוצה ונקראת מולטי קבוצה או "Bag" (שק).

הגדרה מופשטת

עריכה

רשימה מופשטת L עם איברים מסוג E כל שהוא (רשימה מונומורפית, מוגדרת בעזרת הפונקציות הבאות:

nil: () → L
cons: E × LL
first: LE
rest: LL

והאקסיומות:

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) if e1 = e2 and l1 = l2

שימו לב ש-first (nil ()) ו-rest (nil ()) אינם מוגדרים.

האקסימות הללו שקולות לאלו של מבנה הנתונים המופשט של המחסנית.

בתורת הטיפוסים, ההגדרה לעיל מוגדרת בפשטות כהגדרה אינדוקטיבית המוגדרת במונחי הבנאים: nil ו-cons. במונחים אלגבריים, ניתן לייצג זאת כהעתקה 1 + E × LL. ניתן ליצור את first ו-rest בעזרת תיאום דגמים על בנאי ה-cons, וטיפול נפרד במקרה של nil.

לקריאה נוספת

עריכה

קישורים חיצוניים

עריכה
  • רשימה, באתר MathWorld (באנגלית)


  ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.