[כתבה]אז איך עובד הפלייליסט?
כך תנצלו את יכולותיהם של הפוינטרים ליצירה של מבנה נתונים קלאסי וחסכוני במיוחד. רשימה מקושרת - מדריך למתכנתים מתחילים
בשבוע שעבר ניסינו, במידת הצלחה שנויה במחלוקת, להסביר מהם פוינטרים (מצביעים). כעת הגיע הזמן להדגים כיצד משתמשים בהם בפועל – ואת זאת נעשה באמצעות מבנה הנתונים הבסיסי שמכונה "רשימה מקושרת".
חישבו לרגע על רשימת ההשמעה שבנגן המדיה במחשב שלכם. לכל שיר או סרט יש רשומה נפרדת, שכוללת את השם, האורך ועוד כמה פרטים עליו. כמה רשומות כאלה יש ברשימה שלכם? עשרות? מאות? אלפים ספורים? כעת חישבו על המתכנת שכותב את תוכנת הנגן. אם הוא יקצה מראש מקום בזכרון למאה אלף רשומות, נניח (ראו דוגמה באיור למטה, מקרה 1), זה יהיה בזבוז עצום עבור הרוב המוחלט של המשתמשים. מצד שני, תמיד יהיה מקרה קיצוני של משתמש עם מאה אלף ואחד שירים, שילכלך בכל פורום על התוכנה מפני שאינה מצליחה להתמודד עם האוסף שלו. מה עושים?
אחסון רשומות: במערך רגיל מוקצה מראש (1), במערך פוינטרים מוקצה מראש (2) או ברשימה מקושרת (3)
למזער את הבזבוז
חלק מהפתרון הוא להשתמש בהקצאה דינמית. במקום לשמור מראש מקום בזכרון לכל הרשומות, אנחנו מחזיקים רק בפוינטרים לרשומות (מקרה 2 באיור). כאשר יש צורך ברשומה חדשה, התוכנה תבקש ממערכת ההפעלה את כמות הזכרון המדויקת הדרושה עבורה ותקבל, בתשובה, את המיקום בזכרון – שיישמר בתוך אחד מהפוינטרים. פוינטר תופס הרבה פחות מקום מרשומה, כך שבמקום מערך קבוע של מיליון רשומות נוכל לשמור מערך חסכוני יותר של מיליון פוינטרים ולנהל את הרשומות בעזרתו. סבבה? (הערה חשובה: מדובר כמובן על הרשומות שמוצגות בזמן ההפעלה של התוכנה. כשהתוכנה כבויה, כל המידע נשמר בדיסק הקשיח ושם יש הרבה פחות מגבלות).
לרוע המזל, גם מערך קבוע של פוינטרים הוא בזבזני להחריד. מי צריך מיליון כאשר 99.9% מהמשתמשים בקושי מגרדים אלפית מזה? כדי לפתור את הבעיה, צריך לזכור שפוינטרים הם משתנים כמו כל משתנה אחר – ואם כך, במקום להחזיק רשימת פוינטרים קבועה, למה לא לצרף לכל רשומת נתונים פוינטר אחד עבור הרשומה הבאה?
כלומר, אנחנו מתחילים בפוינטר אחד ויחיד שלא מצביע לכלום. כשהמשתמש מוסיף שיר ראשון, אנו מקצים בעזרת הפוינטר הזה מקום בזכרון לרשומה החדשה, שכוללת גם פוינטר חדש ריק. בהוספה הבאה, נשתמש בפוינטר החדש כדי להקצות מקום בזכרון לרשומה השניה, שתכיל גם היא פוינטר חדש וריק, וכך הלאה. בשיטה כזו אנו מצליחים להחזיק, פרט לאותו פוינטר ראשוני וחיוני, בדיוק בכמות הזכרון הדרושה לרשומות ולניהולן – לא ביט אחד יותר או פחות מדי (מקרה 3 באיור). איך כל זה נראה בקוד?
הגדרות, הצגה ומחיקת הרשימה
הקוד שיוצג כאן הוא בשפת Object Pascal, והוא נכתב ונבדק בסביבת הפיתוח החינמית לזרוס עליה נדבר בשבוע הבא. אם כן, הפעולה הראשונה שעלינו לעשות היא להגדיר את סוגי המשתנים שלנו – רשומה (Record, שורה 5-8) ומצביע לרשומה (שורה 4, מזוהה כמצביע באמצעות התו "^" שפירושו בפסקל "מצביע על..."). הסיבה לכך שהפוינטר מוגדר לפני הרשומה חשובה, אבל לא לענייננו.
הגדרות סוג (Type) לרשומה ולמצביע לרשומה, והגדרת מצביע עבור הרשימה
כל רשומה שלנו מכילה מחרוזת (String, שורה 6) ומצביע לרשומה הבאה (שורה 7). את הפוינטר הראשוני שלנו נכנה בשם MyList (שורה 11), והוא יהיה הבסיס לרשימה כולה. אבל לפני שניגש לאופן בנייתה, בואו ונעבור על הפרוצדורות הפשוטות יותר: הצגת הרשימה ומחיקתה.
מכיוון שהפוינטר לכל רשומה נוספת נמצא בזאת שלפניה, כל פרוצדורה/פונקציה שנכתוב שתעשה משהו עם הרשימה חייבת לעבור על הרשומות שבה בזו אחר זו. הדרך הבטוחה ביותר לבצע את המעבר הזה היא באמצעות פוינטר זמני – נקרא לו כאן Temp – שיצביע על הרשומה בה אנו נמצאים בזמן נתון. כדי להתקדם לרשומה הבאה, צריך פשוט להעתיק לתוכו את הערך של הפוינטר שנמצא בתוך הרשומה אליה הוא מצביע.
לדוגמה, כדי להציג רשימה, אנו צריכים לבדוק ראשית כל אם יש בה רשומה אחת לפחות, כלומר האם הוקצה זכרון עבור MyList. הפונקציה Assigned נותנת את התשובה לזה – שלילית אם ערך הפוינטר שנשלח אליה הוא nil וחיובית בכל מקרה אחר. זו המשמעות של שורות 60 (הבדיקה) ו-66 (מה קורה כשהתשובה שלילית). בהנחה שהרשימה קיימת (שורות 61-65), אנו מציגים על המסך את הערך שברשומה (63) ומעתיקים לפוינטר הזמני את הכתובת של הרשומה הבאה (64) עד שתנאי הלולאה מזהה את הפוינטר ה"אחרון" שטרם הוקצה.
פרוצדורה להצגת תוכן של רשימה מקושרת (כל הקוד וצילומי המסך: עידו גנדל)
השיטה למחיקת הרשומה דומה מאד להצגתה, אלא שבמקום להציג את התוכן של כל רשומה אנו פשוט משחררים את הזכרון שהוקצה עבורה בעזרת הפרוצדורה Dispose. כמובן, חייבים להעתיק למשתנה זמני את הפוינטר לרשומה הבאה (שורה 77) לפני שאנחנו משחררים את הזכרון (78), אחרת הוא יילך לאיבוד. הפרמטר List מוגדר כ-var (בשורה 70), וזה אומר שאנו משנים בפועל את הרשימה שנשלחת לפרוצדורה – במקרה שלנו, MyList. זה המקרה היחיד בו יש הגיון בשינוי ואיפוס הפוינטר של תחילת הרשימה.
פרוצדורה למחיקה של רשימה מקושרת
הוספת רשומה: האתגר
לעומת השתיים האלה, הפרוצדורה שמוסיפה רשומה לרשימה המקושרת היא קצת יותר מסובכת, מסיבה פשוטה: הפוינטר הראשון הוא לא חלק מרשומה כמו האחרים, ולכן צריך קוד שונה כדי להקצות לו זכרון. זה מה שקורה בפרוצדורה שבתמונה הבאה. אם הרשימה כבר קיימת (שורות 22-24), אנו עוברים על הרשומות בה באמצעות הפוינטר הזמני (22) עד שמגיעים לרשומה האחרונה – ומקצים זכרון לפוינטר שלה (23, עם הפקודה New). לסיום, אנו מכוונים לרשומה הטריה את הפוינטר הזמני (24).
פרוצדורה להוספה של רשומה
אם, לעומת זאת, מדובר ברשימה ריקה (27-28), נקצה זכרון לפוינטר הראשי (27) ונכוון את הפוינטר הזמני אליו (28). כעת יש לנו פוינטר זמני שמכוון לרשומה הכי חדשה ברשימה, ולא משנה איך הוספנו אותה. נעתיק לתוכה את המידע הדרוש (31) ונאפס את הפוינטר שבתוכה (32). אגב, בעולם האמיתי היינו מוסיפים קוד שיוודא שנותר בכלל זכרון במערכת עבור הרשומה החדשה.
בואו ונחשוב קצת יותר לעומק בשביל מה צריך קוד נפרד עבור הפוינטר הראשי ואלה שברשומות. הסיבה היא שאמנם אפשר להעתיק פוינטרים כמה שרוצים – מיליוני פוינטרים יכולים להצביע לאותה כתובת בדיוק – אך כדי לשנות את הערך של פוינטר ספציפי, "פיזי", צריך להגיע ישירות אליו ולא לעותקים שלו. אם זה פוינטר בתוך רשומה (כלומר, המשתנה ששמו Next), הדרך היחידה לכתוב זאת ישירות בקוד התוכנה היא באמצעות ציון X.Next כאשר X היא הרשומה שמכילה אותו. את הפוינטר הראשי, לעומת זאת, שום רשומה לא מכילה ולכן הקוד הנ"ל לא יכול להיות רלוונטי לגביו וצריך משהו אחר.
שני פתרונות
אפשר לבחור בפתרון "ראש בקיר" וליצור, כבר בתחילת התוכנית, רשומה סתמית כלשהי (מה שמכונה Dummy) שה-Next שלה יהיה תחילת הרשימה ה"אמיתית". אם נשנה את הקוד של הפרוצדורות שהראינו בהתאם, זה יכול לעבוד, אבל זה עדיין קצת בזבזני מבחינת קוד וזכרון. פתרון חכם ואלגנטי הרבה יותר יסתמך על העובדה שגם הפוינטר הראשי וגם הפוינטרים שברשומות הם כולם מסוג "פוינטר לרשומה", ולכן אפשר לשנות אותם בצורה זהה בעזרת פוינטר-לפוינטר-לרשומה! הרעיון הזה קצת מורכב ולא נותר לנו הרבה מקום להסבירו, אז קחו את הזמן ונסו להבין אותו מתוך הקוד שבתמונה הבאה. זכרו שהסימן "@" בפסקל פירושו "הכתובת של...", ואילו "^^" הוא כפליים "^" – כלומר, אם "X^" הוא "מה ש-X מצביע עליו", אז "X^^" הוא "הדבר עליו מצביע הפוינטר ש-X מצביע עליו".
פרוצדורה להוספת רשומה לרשימה מקושרת באמצעות פוינטר-לפוינטר
אלגנטי ביותר, נכון? ולסיום, הנה קוד לדוגמה שמשתמש בכל הפרוצדורות הנ"ל ואיך זה נראה על המסך:
עכשיו רק נשאר לכתוב קוד שמנגן mp3
תהנו :]
תודה ל- www.nana10.co.il .
נכתב במקור על ידי אושרי
ציטוט ההודעה
