סוגי נתונים מ추적 — שורה, תור, רשימה מקושרת
הוצג| English | משמעות |
|---|---|
| queue/kjuː/ | תור |
| push/pʊʃ/ | הכנסה לאגם |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | סוג נתונים מופשט |
| stack/stæk/ | סטק |
| linked list/lɪŋkt lɪst/ | רשימה מקושרת |
| LIFO/ˈlaɪfəʊ/ | אחרון נכנס, אחרון יוצא |
| pop/pɒp/ | הוצאה מאגם |
| pointer/ˈpɔɪntə/ | מצביע |
| FIFO/ˈfaɪfəʊ/ | ראשון נכנס, ראשון יוצא |
| enqueue/enˈkjuː/ | הכנסה לתור |
| dequeue/diːˈkjuː/ | הוצאה מתור |
| node/nəʊd/ | נודה |
| traverse/trəˈvɜːs/ | טיול |
הכפתור 'חזור' ותור הדפסה
- כל עמוד שתבקר בו נדחף לערימה; כפתור החזרה מוריד את העליון. העמוד שאתה עזבת לאחרונה הוא הראשון שתחזור אליו.
- לאורך המסדרון, מדפסת עוברת על משימות בסדר הופעתן. המסמך שנשלח ראשון יוצא ראשון, ללא קשר לגודל של אלו שעומדים מאחוריו.
- שתי מבנים, כללים הפוכים, ומשתמש בהם לפני הבחינה. אף אחד לא אומר כיצד הוא מאוחסן; כל אחד אומר רק מה הפעולות שלו עושות.
- זהו סוג נתונים מ 추상. שיעור זה עוסק בשלושה שנקראים בתוכנית הלימודים, בפעולות על כל אחד, ובאיך להצדיק אחד למצב נתון.
מהו סוג נתונים מופשט (ADT)
- סוג נתונים מופשט (ADT) הוא קבוצת נתונים יחד עם סט של פעולות על הנתונים האלה. משפט זה הוא ההגדרה בשל נקודה אחת.
- הוא מוגדר לפי מה הפעולות עושות, ולא לפי איך הנתונים מאוחזים. היישום מוסתר, כך שהוא יכול להשתנות ללא השפעה על הקוד שמשתמש בו.
- ערימה, תור, רשימה מקשרת, עץ בינארי ומערך הם כולם ADTs.
סוג נתונים אבסטרקטי (ADT) מוגדר על ידי:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ADT קובע את הפעולות (הממשק); האמפלימנטציה מוסתרת וניתנת לשינוי חופשי.
הערימה
- ערימה היא רשימה שבה פריטים נוספים ונמחקים מאותו קצה, ה-עליון, כך שהפריט האחרון שנכנס הוא הראשון שיצא: LIFO.
- פעולות: push מוסיף לעליון, pop מוריד מעליון, peek מסתכל על העליון, ובדוק ריקות ומילוי.
- שימושים: היסטוריית ביטול, כפתור חזור, כתובות החזרה של קריאות פונקציה, בדיקת סוגריים, גילוי שגיאות באמצעות גילוי-חזרה.
הכל קורה בעליון
ערימה פועלת באילו סדר?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ערימה היא LIFO: הפריט שהושתל לאחרונה הוא הראשון שיוצא.
דוגמה פותרת: מעקב אחר הערימה
- ערימה מחזיקה, מהתחתית,
'P' 'N' 'Z' 'X' 'Y' 'W'; מצביט העליון נמצא ב'W'. הפעולותPOP,POP,PUSH 'A',PUSH 'B',POPמבוצעות. מה הערימה מחזיקה, ואين המצביט? - שתי ה-pops מורידות
'W'ואז'Y'. ה-pushes מכניסים'A'ואז'B'במקומם. ה-pop האחרון מוריד'B'. - הערימה מחזיקה
'P' 'N' 'Z' 'X' 'A', עם המצביט ב'A'. הפריט באורך הרב ביותר בערימה הוא התחתון,'P'; אפשר לבצע עוד חמישה pops, ו-sixth would be an error, which is why pop tests for empty first.
ערימה מכילה P N Z X Y W (החלק העליון הוא W). לאחר POP, POP, PUSH 'A', PUSH 'B', POP, איזה פריט נמצא בחלק העליון?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
W ו-Y יוצאים, A ואז B מושתלים, B יוצא. החלק העליון הוא A, מעל X.
התור
- תור הוא רשימה שבה פריטים נוספים בסוף ונמחקים מהתחלה, כך שהפריט הראשון שנכנס הוא הראשון שיצא: FIFO.
- פעולות: enqueue מוסיף בסוף, dequeue מוריד מתחילה, ובדוק ריקות ומילוי.
- שימושים: הוצאת דפוס, בופרים של מקלדת, תזמון, לקוחות בחנות, חיפוש במרחק ראשוני.
הצטרף בסוף, צא מתחילה
שורות, תורים ורשימות מקושרות
LIFO מול FIFO
שורה היא LIFO (אחרון נכנס, ראשון יוצא); הדחיפה וההוצאה מתבצעות באותו קצה (העליון).
תור הוא ראשון שנכנס-ראשון יוצא: פריטים מוסרים מה-______ ומושתלים במונח.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
FIFO: הסרה מהחזית, השחה במונח — כמו תור אנשים.
דוגמה מפורטת: תיאור הוספה והסרה מתור
- הוספה: ודאו שהתור אינו מלא; אחסנו את הפריט במיקום שנתון על ידי המצביע האחורי; הזיזו את המצביע האחורי קדימה (והוסיפו אחד לספירה).
- הסרה: ודאו שהתור אינו ריק; קראו את הפריט במיקום המצביע הקדמי; הזיזו את המצביע הקדמי קדימה (וחסרו אחד מהספירה).
- ציינו את המסורת שאתם משתמשים בה: אם המצביע האחורי מסמן את המקום החופשי הבא, אחסנו תחילה ולאחר מכן הזיזו; אם הוא מסמן את הפריט האחרון, הזיזו תחילה ולאחר מכן אחסנו. שתי הגישות זוכות נקודות, כל עוד אתם עקביים.
סדר את שלבי ההשחה של פריט לתור (איشارת המונח מסמנת את המקום החופשי הבא).
Difficulty 3/5 · 200 coins + a small bonus on first completion today
הבדיקה נעשית תחילה; לאחר מכן שמירה, ואז הזזה לפי המסורת הזו. ציין אילו מסורת משתמש בה.
הרשימה המקושרת
- רשימה מקושרת היא רשימה שבה כל צומת מכיל פריט נתונים ו-מצביע לצומת הבא, עם מצביע התחלה לצומת הראשון. המצביע של הצומת האחרון הוא סנטינל כמו
NULL. - פעולות: הכנסה, מחיקה, חיפוש, ו-מסלול, בעקבות המצביעים מהראש כדי לבקר בכל צומת בסדר.
- יתרון לעומת מערך: ההכנסה או המחיקה זולות, רק יש לשנות את המצביעים, והרשימה גדלה לפי הצורך. חיסרון: אין גישה אקראית; הגעה לצומת העשירי דורשת מעבר על תשעה מצביעים.
ערך וחץ, חוזר על עצמו
רשימה מקושרת: נקודות מחוברות על ידי מצביעים
כל נקודה מאחסנת ערך ומצביע לנקודה הבאה. ההוספה או המחיקה משנות רק את הקישור במצביעים — אין הזזה של פריטים, בניגוד למערך.
כל נקודה ברשימה מקושרת מכילה:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
נקודה מאחסנת את הערך שלה לצד מצביע (יחס) לנקודה הבאה; הראשון מסמן את ההתחלה, NULL את הסוף.
רשימה מקושרת מאפשרת הוספה/מחיקה זולה (רק שינוי מצביעים), אך גישה אקראית איטית (יש לעבור על המצביעים מהראשון).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
זוהי המסחר בין מערכים לרשימות: מערכים נותנים גישה באינדקס O(1); רשימות נותנות הוספה/מחיקה זולה.
דוגמה מפורטת: הוספת צומת בסדר
- תארו כיצד ערך חדש מוכנס לרשימה מקושרת שנשמרת בסדר עולה. [4]
- עברו על הרשימה מהראש, בעקבות המצביעים, עד שמצוי הצומת לפני המיקום הנדרש: הצומת האחרון שערכו קטן מהערך החדש.
- לקחו צומת פנוי ואחסנו בו את הערך החדש. הגדירו את המצביע של הצומת החדש למיקום אליו הצומת הקודם מצביע כעת.
- לאחר מכן הגדירו את המצביע של הצומת הקודם לצומת החדש. אם הערך החדש צריך להיות בראש, זהו מצביע הראש that changes instead.
סדר את שלבי ההוספה של ערך לרשימה מקושרת מסודרת.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
מצוא, מלא, והגדר את מצביע הנקודה החדשה קדימה, ולאחר מכן שנה את חיבור הנקודה הקודמת. הפיכת שני השלבים האחרונים יאבד את שאר הרשימה.
נימוק הבחירה
- הפריטים חייבים לעבור עיבוד בסדר הגעתם, משימות הדפסה, לחיצות מקשים, לקוחות: תור, משום שהוא תהליך FIFO (First In First Out).
- הפריט החדש ביותר חייב לעבור עיבוד קודם, ביטול פעולה, נסיעה אחורה, קריאות פנימיות: אגרת (Stack), משום שהוא תהליך LIFO (Last In First Out).
- פריטים מוסיפים או נמחקים לעיתים קרובות באמצע אסופה מסודרת, והגודל אינו ידוע: רשימה מקושרת, משום שרק השעונים מתחלפים ואין הזזה של נתונים.
- קראו את שם המבנה, ציינו את הכלל שלו, קשרו את הכלל למצב.
התאם כל ADT לכלל ולשימוש נפוץ.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
שורה = אחרון נכנס ראשון יוצא; תור = ראשון נכנס ראשון יוצא; רשימה קשורה מקשרת נודים באמצעות מצביעים.
חייב הדפסת משימות בהתאם לסדר שהן נשלחו. איזה ADT, ולמה?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
סדר ההגעה הוא כלל FIFO. שורה הייתה מדפיסה את המשימה האחרונה תחילה.
ADT לעומת מימוש
- ה-ADT הוא ה-התנהגות: דחיפה ופליטה, הכנסה ותוצאה, הוספה וטיול.
- המימוש הוא האחסון: בקורס זה, מערך פלו כמה משתני שעונים (הפרק הבא).
- שאלה על ה-ADT דורשת פעולות וכללים; שאלה על המימוש דורשת מערכים, שעונים ובדיקות.
סימונים נופלים מהיד
- דחיפה והכנסה לבדוק מלא; פליטה ותוצאה לבדוק רוק. כתבו את הבדיקה בתוך התיאור.
- הוספה לרשימה מקושרת: הגדירו את השעון של הנודה החדשה לפני שינוי השעון של הנודה הקודמת, אחרת שאר הרשימה תאבד.
- האגרה משתנה בקצה אחד, התור בשני קצוות. "הסרה מהחלק העליון של התור" היא תשובה לאגרה.
- הרחיבו את הקיצורים פעם אחת: LIFO, אחרון נכנס ראשון יוצא; FIFO, ראשון נכנס ראשון יוצא.
הבנתך מושלמת
- ADT הוא אסופת נתונים יחד עם סט של פעולות עליה; התנהגות, לא אחסון.
- אגרה: הוספה והסרה בחלק העליון, LIFO, דחיפה ופליטה · תור: הוספה באחור, הסרה בקדמת, FIFO, הכנסה ותוצאה.
- רשימה מקושרת: נודות של ערך + שעון מאגף שעון ראשון; הוספה והסרה זולה, גישה אקראית איטית; טיול על ידי מעבר על השעונים.
- הנמוקו לפי הכלל: סדר הגעה → תור; חדשנים קודמים → אגרה; הוספה תכופה באמצע → רשימה מקושרת.