Loading AI tools
מבנה נתונים מוויקיפדיה, האנציקלופדיה החופשית
רשימה (באנגלית: List או Sequence) היא מבנה נתונים מופשט שתוכנו בעל סדר חלקי ועשוי להכיל חזרות (כלומר עשויים להימצא בו מספר איברים שקולים). מימוש של רשימה הוא למעשה ייצוג ממוחשב של סדרה מתמטית סופית.
ערך מחפש מקורות | |
על פי רוב, מימוש רשימה במחשב ייעשה על ידי שימוש במערך או ברשימה מקושרת. שפות תכנות רבות כוללות מימוש כלשהו של רשימה, ושפות תכנות פונקציונליות או לוגיות (כמו Haskell או פרולוג) תומכות על פי רוב ברשימה כטיפוס בסיסי בשפה.
רשימה היא מבנה נתונים "חלש", כלומר ניתן להתייחס למבני נתונים אחרים כאל רשימה לה נוספו הגבלות:
רשימה מופשטת L עם איברים מסוג E כל שהוא (רשימה מונומורפית, מוגדרת בעזרת הפונקציות הבאות:
והאקסיומות:
לכל איבר e ברשימה l. יוצא מכך ש:
שימו לב ש-first (nil ())
ו-rest (nil ())
אינם מוגדרים.
האקסימות הללו שקולות לאלו של מבנה הנתונים המופשט של המחסנית.
בתורת הטיפוסים, ההגדרה לעיל מוגדרת בפשטות כהגדרה אינדוקטיבית המוגדרת במונחי הבנאים: nil ו-cons. במונחים אלגבריים, ניתן לייצג זאת כהעתקה 1 + E × L → L. ניתן ליצור את first ו-rest בעזרת תיאום דגמים על בנאי ה-cons, וטיפול נפרד במקרה של nil.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.