טיפוס נתונים מופשט הגדרת מבנה נתונים מופשט | קישורים חיצוניים | תפריט ניווטלהרחיב אותו
קצרמר מדעי המחשבמבני נתונים
מדעי המחשבמודל מתמטימבני נתוניםטיפוסי נתוניםשפות תכנותסמנטיקההפשטהסיבוכיותמחסניתאלגוריתמיםאלגוריתם חיפוש לעומקמחסניתLIFOטיפוסי נתוניםמודוליםסריגיםחבורותחוגים
(function()var node=document.getElementById("mw-dismissablenotice-anonplace");if(node)node.outerHTML="u003Cdiv class="mw-dismissable-notice"u003Eu003Cdiv class="mw-dismissable-notice-close"u003E[u003Ca tabindex="0" role="button"u003Eהסתרהu003C/au003E]u003C/divu003Eu003Cdiv class="mw-dismissable-notice-body"u003Eu003Cdiv id="localNotice" lang="he" dir="rtl"u003Eu003Cpu003Eבואו ללמוד איך עורכים בוויקיפדיה. הסדנה תתקיים בספריה הלאומית בירושלים ביום שישי, 05.04.19, בשעה 09:00. להרשמה לחצו u003Ca href="/wiki/%D7%95%D7%99%D7%A7%D7%99%D7%A4%D7%93%D7%99%D7%94:%D7%9E%D7%99%D7%96%D7%9E%D7%99_%D7%95%D7%99%D7%A7%D7%99%D7%A4%D7%93%D7%99%D7%94/%D7%92%D7%9C%D7%90%D7%9D/%D7%94%D7%A1%D7%A4%D7%A8%D7%99%D7%99%D7%94_%D7%94%D7%9C%D7%90%D7%95%D7%9E%D7%99%D7%AA/%D7%90%D7%99%D7%A8%D7%95%D7%A2%D7%99%D7%9D/%D7%A1%D7%93%D7%A0%D7%AA_%D7%A2%D7%A8%D7%99%D7%9B%D7%94_%D7%90%D7%A4%D7%A8%D7%99%D7%9C_2019" title="ויקיפדיה:מיזמי ויקיפדיה/גלאם/הספרייה הלאומית/אירועים/סדנת עריכה אפריל 2019"u003Eכאןu003C/au003E.nu003C/pu003Eu003C/divu003Eu003C/divu003Eu003C/divu003E";());
טיפוס נתונים מופשט
קפיצה לניווט
קפיצה לחיפוש
במדעי המחשב, טיפוס נתונים מופשט (Abstract Data Type או ADT) הוא מודל מתמטי עבור קבוצה מסוימת של מבני נתונים בעלי התנהגות דומה, או עבור טיפוסי נתונים שונים בשפות תכנות להם סמנטיקה דומה, ומאפשר הפשטה שלהם. טיפוס נתונים מופשט מוגדר על ידי הפעולות שניתן לבצע עליו ועל ידי מגבלות שחלות על תוצאות הפעולות האלה (או העלות שלהן מבחינת סיבוכיות זמן ומקום).
לדוגמה, מחסנית היא טיפוס נתונים מופשט הכולל פעולת (Push) שמוסיפה איבר, פעולת (Pop) שמסירה את האיבר האחרון שנוסף למחסנית, ופעולת Peek המאפשרת גישה למידע בראש המחסנית ללא הסרתו. בהקשר של ניתוח סיבוכיות של אלגוריתמים העושים שימוש במחסנית, ניתן להוסיף דרישות המקילות את ניתוח הסיבוכיות: זמן קבוע לכל פעולה, ללא תלות בכמות הנתונים במחסנית, ושטח זיכרון קבוע עבור כל איבר.
מבני נתונים מופשטים הם ישויות מתמטיות, העוזרות לפשט תיאורים של אלגוריתמים, ובפרט לאפשר הוכחת נכונות שלהם, שעשויה להיעזר דווקא בהגבלות על הגישה למידע השמור בהם. למשל, אלגוריתם חיפוש לעומק משתמש בטיפוס הנתונים המופשט מחסנית וכך ניתן להוכיח את נכונותו באופן אלגנטי כיוון שגישה לנתונים מתבצעת אך ורק בסדר LIFO, ואין צורך להתייחס למימוש ספציפי (שעשוי לאפשר או לא לאפשר גישה אל אמצע המחסנית).
כמו כן מאפשרים מבני הנתונים המופשטים לסווג מבני נתונים, ולתאר באופן פורמלי את מערכות הטיפוסים של שפות תכנות. ניתן לממש מבני נתונים בעזרת טיפוסי נתונים או מבני נתונים שונים, בשפות תכנות שונות.
מבני נתונים מופשטים ממומשים לעיתים קרובות על ידי מודולים: ממשק המודול מכריז על הפונקציות המממשות את הפעולות של מבנה הנתונים, לעיתים בתוספת הערות המתארות את המגבלות. כך המימוש של מבנה הנתונים מוסתר מהמשתמש ומאפשר שינוי של המימוש בלי להשפיע על תוכניות המשתמש.
ניתן להתייחס למושג טיפוס נתונים מופשט כהכללה של מבנים אלגבריים כגון סריגים, חבורות וחוגים.
הגדרת מבנה נתונים מופשט |
מבנה נתונים מופשט מוגדר כמודל מתמטי של עצמים של נתונים עם הפעולות המוגדרות עליהם. אין מוסכמות סטנדרטיות להגדרה שלהם. ניתן לחלק באופן בסיסי לשני סגנונות של הגדרה של מבני נתונים: ״אימפרטיבי״ ו-״פונקציונלי״.
מבני נתונים | ||
|---|---|---|
מבנים מופשטים | רשימה • מחסנית • קבוצה • רב קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • טריי X מהיר • טריי y מהיר• [[עץ WAVL]] | |
| הסתברותיים | פילטר בלום | |
קישורים חיצוניים |
מדיה וקבצים בנושא טיפוס נתונים מופשט בוויקישיתוף
ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.קטגוריות:
- קצרמר מדעי המחשב
- מבני נתונים
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.144","walltime":"0.183","ppvisitednodes":"value":744,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":11492,"limit":2097152,"templateargumentsize":"value":6006,"limit":2097152,"expansiondepth":"value":9,"limit":40,"expensivefunctioncount":"value":4,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":0,"limit":5000000,"entityaccesscount":"value":1,"limit":400,"timingprofile":["100.00% 154.152 1 -total"," 40.83% 62.939 1 תבנית:מבני_נתונים"," 37.82% 58.304 1 תבנית:ניווט_קבוצות"," 36.08% 55.619 1 תבנית:קצרמר"," 22.96% 35.399 1 תבנית:ויקישיתוף_בשורה"," 9.41% 14.512 1 תבנית:קצרמר/קוד"," 6.33% 9.756 1 תבנית:שם_הדף_בלי_הסוגריים"," 4.85% 7.482 1 תבנית:בלי_הסוגריים"," 4.20% 6.478 1 תבנית:הודעת_פרמטר_לא_מולא"," 3.52% 5.421 1 תבנית:קצרמר/נושא_נוסף"],"scribunto":"limitreport-timeusage":"value":"0.014","limit":"10.000","limitreport-memusage":"value":814340,"limit":52428800,"cachereport":"origin":"mw1340","timestamp":"20190316164604","ttl":2592000,"transientcontent":false);mw.config.set("wgBackendResponseTime":125,"wgHostname":"mw1324"););
