בפרקים הקודמים ראינו כיצד יש ביכולתנו לשמור סדרה של נתונים במערך שמוקצה באופן סטטי או בכזה שמוקצה באופן דינמי. בפרק זה, ובבא אחריו, נכיר דרכים נוספות לשמירת סדרת נתונים.
כתבו תכנית הקוראת מספרים שלמים עד קליטת הערך אפס. את כל המספרים החיוביים התכנית מכניסה לרשימה מקושרת אחת, ואת כל השליליים לרשימה מקושרת שניה.
עת תלמדו, בסעיף הבא, כיצד מציגים תוכן של רשימה, הוסיפו לתכנית גם פונק' שתציג את תוכנן של כל אחת משתי הרשימות המקושרות.
הוסיפו לתכנית שכתבתם בתרגול העצמי הבסיסי הקודם (בניית שתי רשימות מקושרות, אחת של מספרים חיוביים, ושניה של מספרים שליליים), פונ' אשר מציגה את תוכנן של הרשימות.
כתבו תכנית הכוללת פונ' הבונה רשימה מקושרת, ומחזירה מצביע לראש הרשימה. הרשימה תבנה באופן הבא: התכנית תקרא סדרת מספרים שלמים עד קליטת הערך אפס. את המספרים החיוביים בלבד היא תוסיף לרשימה מקושרת שהיא בונה, באופן שכל נתון חדש יתווסף בסוף הרשימה.
התכנית הראשית תזמן פונ' שניה אשר תציג את תוכנה של הרשימה.
כתבו תכנית הכוללת פונ' הבונה שתי רשימות מקושרת, ומחזירה (באמצעות פרמטרי הפניה) מצביע לראש הרשימות. הרשימות תבננה באופן הבא: התכנית תקרא סדרת מספרים שלמים עד קליטת הערך אפס. את המספרים החיוביים היא תוסיף לרשימה מקושרת אחת, ואת השליליים לרשימה שנייה, באופן שכל נתון חדש יתווסף בסוף הרשימה.
התכנית הראשית תזמן פעמיים פונ' שניה אשר תציג את תוכנה של כל אחת מהרשימות.
כתבו תכנית הבונה רשימה מקושרת ממוינת, אולם מוסיפה כל ערך לתכנית רק פעם אחת לכל היותר. כלומר עת ערך מוזן לתכנית בפעם השניה ואילך, הוא לא יוסף עוד לרשימה.
הציגו את הרשימה שבניתם.
כתבו תכנית הקוראת סדרת מספרים שלמים, עד קבלת הערך אפס, ובונה מהם רשימה מקושרת. התכנית מציגה את הנתונים ברשימה שנבנתה.
אחר קוראת התכנית ערך נוסף, ומזמנת פונ' אשר מוחקת את כל מופעיו של הערך מהרשימה.
לבסוף, מציגה התכנית את הרשימה (אחרי הסרת מופעיו של הערך).
חזרו תכנית הראשונה שכתבתם במסגרת התרגול העצמי הבסיסי בפרק זה (תכנית הקוראת מספרים שלמים עד קליטת הערך אפס. את כל המספרים החיוביים התכנית מכניסה לרשימה מקושרת אחת, ואת כל השליליים לרשימה מקושרת שניה). אחרי הצגת תוכנה של כל אחת מהרשימות, ולפני סיום התכנית, שחררו את איבריה.
כתבו תכנית המגדירה:
struct Node {
unsigned int _data ;
struct Node *_next, *_next_prime ;
} ;
התכנית תקרא סדרת מספרים טבעיים עד קליטת הערך אפס, ותבנה מהם רשימה מקושרת. ערכו של המצביע _next_prime בכל איבר ייקבע להיות NULL.
זמנו את הפונק' link_primes אשר תשרשר באמצעות המצביע _next_prime את האיברים הכוללים מספרים ראשוניים לכדי רשימה, ותחזיר מצביע לראש הרשימה.
לדוגמה, אם הרשימה כללה את הערכים: 10, 15, 7, 3, 20, 2 (10 ראשון, 2 אחרון) אזי המצביע _next_prime באיבר של 7 יעבור להצביע על האיבר של 3. המצביע _next_prime באיבר של 3 יעבור להצביע על 2 (והמצביעים _next_prime ביתר האיברים, כולל באיבר של 2, יישארו NULL). הפונ' תחזיר מצביע לאיבר של 7.
התכנית תדפיס:
א. את כלל הנתונים ברשימה.
ב. את המספרים הראשוניים בלבד ברשימה
(הערה קטנה: מומלץ לכתוב פונק הדפסה אחת בלבד)
דוגמה זאת ציג רק באמצעות טקסט כתוב. אין בה חידושים עקרוניים.
דוגמה זו דומה מאוד לדוגמה בה ראינו בניה של רשימה מקושרת ממוינת תוך שימוש במצביע למצביע. אני מציג אותה כדי לעזור לכם להפנים את הנושא, באמצעות משימה נוספת.
כתבו תכנית הקוראת סדרת מספרים שלמים, עד קבלת הערך אפס, ובונה מהם רשימה מקושרת. התכנית מציגה את הנתונים ברשימה שנבנתה.
אחר קוראת התכנית ערך נוסף, ומזמנת פונ' אשר מוחקת את כל מופעיו של הערך מהרשימה.
הפונ' למחיקת ערך תקבל מצביע למצביע לראש הרשימה, ותפעל תוך שבלולאה היא מתקדמת לא על אברי הרשימה, אלא על המצביעים לאברי הרשימה.
כלומר, זימון הפונ' יהיה:
rem_val(&head, val) ;
וחתימת הפונ' היא:
void rem_val(struct Node **p2head, int val) ;
לבסוף, מציגה התכנית את הרשימה (אחרי הסרת מופעיו של הערך).
דוגמה זו היא גדולה ומורכבת. היא מציגה לכם אלגוריתם מיון, בשם מיון מיזוג, שראוי שבוגר מדעי המחשב יכיר. חלק מהמיון כולל פעולה שנקראת 'מיזוג' (merge), שגם לה יש חשיבות בפני עצמה. מיון מיזוג הוא אלגוריתם רקורסיבי, וזו תכונה שניה חשובה של הדוגמה. למותר לציין שלא יעלה על הדעת שסטודנט למדעי המחשב לא ישלוט היטב ברקורסיה. לבסוף, אפשר וגם כדאי להשוות את זמן הריצה של מיון מיזוג לזה של מיונים אחרים, בפרט מיון מהיר (Quick Sort).
יש להודות על האמת שמבחינת תכנות עם רשימות מקושרות אין בדוגמה חידושים עקרוניים. מההיבט התכנותי הדוגמה חוזרת על נושאים שכבר ראינו בדוגמות הקודמות.
הצגת מיון מיזוג של רשימות נעשית בארבה סרטונים: הראשון מציג את רעיון המיון, השני והשלישי כוללים את קוד המיון וסימולציית הרצה של הקוד, והרביעי דן בזמן הריצה של האלגוריתם.
השאלות שלפניכם לקוחות מבחינות. אתם מתבקשים לכתוב בהן פונ' אחת מתוך תכנית שלמה, תוך שאתם מניחים שאת מה שצריך היה להכין, טרם זימון הפונ', מישהו כבר הכין, ואת מה שצריך יהיה לעשות עם המידע שהפונ' מחזירה מישהו יעשה. אתם מתבקשים לכתוב 'רק' פונ' אחת, שהינה במידה רבה 'לב התכנית'.
כמובן שהשאלות אינן קלות, אך התמודדות מוצלחת איתן מעידה על השגת שליטה טובה בנושא.