יישום ADTs באמצעות מערכים
הוצג| English | משמעות |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | היפל |
| underflow/ˌʌndəˈfləʊ/ | מתחת למינימום |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | מערך מעגלי |
| free list/friː lɪst/ | רשימת פנויים |
אין כזה דבר כאגרה בזיכרון
- פתחו מחשב וחפשו את האגרה. לא תמצאו אותה. הזיכרון הוא מערך עצום של תאים מספרים, וזה כל מה שיש.
- כל אגרה, כל תור, כל רשימה מקושרת הם המערך הזה פלו שניים או שלושה משתני שלמים הזוכרים היכן הדברים נמצאים. דחיפה היא "הוספת אחד למספר ואחסון"; תוצאה היא "קריאת תא והוספת אחד למספר אחר".
- כל הפרק הזה הוא ספירת חשבונות: אילו שעונים, אילו בדיקות, ומה קורה בקצוות.
- המבחן מבקש ממך לתאר את ההצהרות, לעבור על השעונים באמצעות מספר פעולות ולסבר מדוע בדיקות אלו נדרשות.
שורה בעזרת מערך
- אחסון הפריטים ב-
Stack[1:MaxSize]עם שלםTop, כאשר הערך הוא 0 כשהשורה ריקה. - Push(x): אם
Top = MaxSizeהשורה מלאה, מתרחש התמלאות יתר; אחרתTop ← Top + 1וStack[Top] ← x. - Pop(): אם
Top = 0השורה ריקה, מתרחש חוסר תכולה; אחרת החזרStack[Top]ועדכוןTop ← Top − 1.
המערך אינו זז; רק Top משתנה
הזרת פריט לשורה שמלאה כבר גורמת לשורה ______.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
גלישה = הזרה כאשר Top = MaxSize; פריקה משורה ריקה (Top = 0) היא תת-גלישה.
התאם כל תנאי שורה-מערכת למה sheוהיא משמעת.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Top סופר את האלמנטים: 0 = ריק, MaxSize = מלא; שני המקרים של שגיאה הם תחתית ומעל.
דוגמה פותרת: הצהרה והתחלת הערכים לשורה
- תיאור ההצהרות וההתחלה הנדרשים ליישום שורה של עד 50 שלמים באמצעות מערך. [5]
- מערך של 50 אלמנטים מהסוג
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, לאחסון הפריטים. - קבוע או משתנה
MaxSizeהמוגדר ל-50, כדי שהפעולה Push תוכל לבדוק האם השורה מלאה. - שעון שורה עליון (top-of-stack) מהסוג
INTEGER,Top, המוגדר ל-0 כדי להצביע על כך שהשורה ריקה; הפעולה Pop בודקת אותו בחיסור, והפעולה Push משווה אותו ל-MaxSizeבבדיקת התמלאות יתר.
איזה מהבאים שייך להצהרה והתחלה של ערימה המבוססת על מערך? בחר את כולם החל options.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
לערימה נדרש מצביע אחד, Top. מצביע קדמי שייך לאגירה.
תור בעזרת מערך פשוט
- שני שעונים:
Frontעבור הפריט הבא שיצא, ו-Rearעבור המקום הרוקם הבא. הפעלת Enqueue מאחסנת ב-Rearומזזה אותה; הפעלת Dequeue קוראת ב-Frontומזזה אותה. - שני השעונים זזים רק קדימה, ולכן לאחר מספר פעולות הם יוצאים מחוץ לגבולות המערך בעוד התאים בתחילת המערך נשארים ריקים ולא ניתנים לשימוש.
- הפתרון הוא לאפשר לשעונים לעגל סביב המערך.
המערך המעגלי
- במערך מעגלי, שעון חוזר לתא הראשון כאשר הוא עובר את האחרון: עם אינדקסים המתחילים ב-1,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): בדוק שאין מלא;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): בדוק שאין ריק; החזרQueue[Front];Front ← (Front MOD MaxSize) + 1. - שמור על ספן נפרד: כאשר התור מלא לחלוטין וכאשר הוא ריק לחלוטין, לשני השעונים יש אותה יחסית מיקום, ולכן השעונים לבדם אינם יכולים להבדיל בין המצבים.
לאחר התא האחרון בא התא הראשון
יישום ADTs עם מערכים
ראשון נכנס, ראשון יוצא (FIFO)
תור הוא ראשון נכנס ראשון יוצא — הזרקה מהגב, פריקה מהחזית.
מדוע להשתמש במערך מעגלי עבור אגירה?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אגירה ליניארית מבזבזת את התאים בתחילה ככל ש-Front מתקדם; עיגול עם MOD משתמש בהם מחדש.
מאגר תור מעגלי משתמש ב-MOD כך שמצבי החרוף והסוף מתעקפים ומשתמשים מחדש בתאים ששוחררו בקצה האריי.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
(pointer MOD MaxSize) + 1 מחזיר את האינדקס לתא הראשון, ולכן מאגר תור ליניארי אינו מבזבז יותר את התאים שאותם עבר Front.
דוגמה פורסמת: הליכה עם המצביעים
- עם
MaxSize = 6: אםRear = 5, אזי(5 MOD 6) + 1 = 6, ולכן הפריט הבא יכנס לתא 6. אםRear = 6, אזי(6 MOD 6) + 1 = 1: המצביע נעטף לתא 1. - מחשבת חוגגת מוחזקת במערך בגודל 5, אינדקסים 0 עד 4, עם
Front = 3,Rear = 3ופריט אחד מאוחסן. שני פריטים נוספו, ואז שניים הוסרו. עם אינדקסים החל מ-0, כל תנועה היא(pointer + 1) MOD 5. - הוספה כפולה מזיזה את
Rear: 3 → 4, ולאחר מכן 4 → 0, מכיוון ש-(4 + 1) MOD 5 = 0. הסרה כפולה מזיזה אתFront: 3 → 4 → 0. נותר פריט אחד, באינדקס 0, והמחשבה השתמשה מחדש בתאים ששחררו בהתחלת המערך.
מאגר תור מעגלי משתמש בתאים 1 עד 6 ו-Rear = 6. לאחר Rear ← (Rear MOD 6) + 1, היכן ייכנס הפריט הבא?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
6 MOD 6 = 0, ועוד 1 נותן 1. המצביח מתעקף להתחלת האריי.
דוגמה פורסמת: אלגוריתם ההוספה במילים
- תיאר את האלגוריתם להוספת פריט למחשבת חוגגת. [4]
- אם הכמות שווה לגודל, דווח שהמחשבת מלאה ועצור.
- אחרת, הוסף 1 למצביע הרק; אם הוא עכשיו עבר את האינדקס האחרון, הגדר אותו לאינדקס הראשון.
- אחסן את הפריט במצביע הרק והוסף 1 לכמות.
סדרו את שלבי ההוספה למאגר תור מעגלי.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
בדיקה, הזזה, עקיפה, אחסון, ספירה. העקיפה היא מה שהופך את האריי למעגלי.
רשימה מקושרת במערך
- השתמש במערך של רשומות צמתים, כל אחד עם
Nextאינדקס;-1מסמן את הסוף.Headאינדקס מסמן את הצמת הראשון,-1אם הרשימה ריקה. - התאים הלא משמשים מחוברים ברשימת פנויים מ
FreeListHead, בדיוק כמו שרשימת הנתונים מחברת את המשמשים.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- הכנס: קח את התא ב
FreeListHead, הגדר את הValueוהNextשלו, ולאחר מכן חבר מחדש את הNextאו הHeadשל הצמת הקודם. מחק: נתק את הצמת והחזר את תאו לחזית רשימת הפנויים.
שתי רשימות משתפות במערך אחד: רשימת הנתונים ורשימת הפנויים
ברשימה מקשרת המבוססת על אריי, רשימת החופש:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
רשימת החופש מקשרת בין התאים השארתיים, כך שהוספה יכולה לקחת אחד והסרה להחזיר אותו — כמו רשימה מקשרת שנייה של ריקים.
דוגמה פורסמת: הכנסה לרשימה המאוחסת במערך
DataוPointerמערכים מחזיקים את הרשימה 1 → 3 → 4, עםStart = 1; אינדקס 1 מחזיקD40, אינדקס 3 מחזיקD32, אינדקס 4 מחזיקD11עם מצביע null. רשימת הפנויים מתחילה באינדקס 2 וממשיכה 2 → 5. הכנסD6ביןD32לD11.- קח את הצמת הפנוי הראשון, אינדקס 2, והגדר את ה
FreeStartלמצביע שלו, 5. אחסן אתD6בData[2]. - הגדר את
Pointer[2]לערךPointer[3]ששמור, שהוא 4. לאחר מכן הגדר אתPointer[3]ל-2. - הרשימה כעת קוראת 1 → 3 → 2 → 4 ורשימת הפנויים היא 5 → null. היישום, אם נתבקש: מערך עבור הנתונים, מערך מקביל (או שדה רקקורד) עבור הפנויים, פונקציית התחלה ופונקציית רשימת פנויים.
בדוגמה המפורטת, לאחר הכנסת D6, רשימת החלל הפנוי מתחילה באינדקס ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
האינדקס 2 הוסר מהרשימה הפנויה, לכן FreeStart עובר לאינדקס שמצביא עליו 2, והוא היה 5.
בעת ההכנסה לרשימה, יש לשנות את השורה של הצומת הקודם לפני שנקבעת שורת הצומת החדש.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
נקבע תחילה את שורת הצומת החדש לצומת הבא הישן. שינוי שורת הצומת הקודם קודם כן גורם לאובדן כתובת שאר הרשימה.
סימונים נופלים מהיד
- הבדיקות באותות תחילה: מלא לפני הדחיפה או ההכנסה, ריק לפני החילוץ או ההוצאה. תאר אותן; הן מהוות נקודות ציון.
- נוסחת העיגול תלויה במדדים:
(Rear MOD MaxSize) + 1למדד 1-בסיסי,(Rear + 1) MOD Sizeלמדד 0-בסיסי. התאם לגבולות השאלה. - ה-ספירה היא מה שמבדיל בין תור סביבתי מלא לריק. פונקציות בלבד אינן יכולות.
- הגדר את ה-
Nextשל הנוד החדש לפני חידוש הקישורים בנוד הקודם, והחזר מיקום של נוד שנמחק לרשימת הפנויים, אחרת המערך יתמלא לאט בתאים בלתי נגישים.
הבנתך מושלמת
- ערימה במערך:
Stack[1:MaxSize]ופונקצייתTopהמתחילים ב-0;Top = MaxSizeהוא גלישה עליונה,Top = 0הוא גלישה תחתונה - תור סביבתי:
FrontוRearעוברים עיגול עםMOD; ספירה נפרדת מבדילה בין מלא לריק - רשימה מקושרת במערך: רקקורדים של נודים עם מדד
Next,Head, ורשימת פנויים המקשרת את המיקומים הנותרים - כל פעולה היא בדיקה, ולאחר מכן אריתמטיקה בפונקציות, ואחסון או קריאה; התנהגות האבסטרקציה אינה משתנה בהתאם לאופן האחסון שלה