טיפוס נתונים מופשט

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במדעי המחשב, טיפוס נתונים מופשט (Abstract Data Type או ADT) הוא מודל מתמטי עבור קבוצה מסוימת של מבני נתונים בעלי התנהגות דומה, או עבור טיפוסי נתונים שונים בשפות תכנות להם סמנטיקה דומה, ומאפשר הפשטה שלהם. טיפוס נתונים מופשט מוגדר על ידי הפעולות שניתן לבצע עליו ועל ידי מגבלות שחלות על תוצאות הפעולות האלה (או העלות שלהן מבחינת סיבוכיות זמן ומקום).

לדוגמה, מחסנית היא טיפוס נתונים מופשט הכולל פעולת (Push) שמוסיפה איבר, פעולת (Pop) שמסירה את האיבר האחרון שנוסף למחסנית, ופעולת Peek המאפשרת גישה למידע בראש המחסנית ללא הסרתו. בהקשר של ניתוח סיבוכיות של אלגוריתמים העושים שימוש במחסנית, ניתן להוסיף דרישות המקילות את ניתוח הסיבוכיות: זמן קבוע לכל פעולה, ללא תלות בכמות הנתונים במחסנית, ושטח זיכרון קבוע עבור כל איבר.

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

כמו כן מאפשרים מבני הנתונים המופשטים לסווג מבני נתונים, ולתאר באופן פורמלי את מערכות הטיפוסים של שפות תכנות. ניתן לממש מבני נתונים בעזרת טיפוסי נתונים או מבני נתונים שונים, בשפות תכנות שונות.

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

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

הגדרת מבנה נתונים מופשט[עריכת קוד מקור | עריכה]

מבנה נתונים מופשט מוגדר כמודל מתמטי של עצמים של נתונים עם הפעולות המוגדרות עליהם. אין מוסכמות סטנדרטיות להגדרה שלהם. ניתן לחלק באופן בסיסי לשני סגנונות של הגדרה של מבני נתונים: ״אימפרטיבי״ ו-״פונקציונלי״.


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