13 רשימות מקושרות (Linked Lists)

בפרקים הקודמים ראינו כיצד יש ביכולתנו לשמור סדרה של נתונים במערך שמוקצה באופן סטטי או בכזה שמוקצה באופן דינמי. בפרק זה, ובבא אחריו, נכיר דרכים נוספות לשמירת סדרת נתונים.

13.1 הצגת הנושא ובניית רשימה מקושרת

תרגול עצמי בסיסי בנושא 'בניית רשימה מקושרת'

כתבו תכנית הקוראת מספרים שלמים עד קליטת הערך אפס. את כל המספרים החיוביים התכנית מכניסה לרשימה מקושרת אחת, ואת כל השליליים לרשימה מקושרת שניה.

עת תלמדו, בסעיף הבא, כיצד מציגים תוכן של רשימה, הוסיפו לתכנית גם פונק' שתציג את תוכנן של כל אחת משתי הרשימות המקושרות.

13.2 הצגת תוכנה של רשימה, והעברת מצביע לראש רשימה כפרמטר ערך

תרגול עצמי בסיסי בנושא 'הצגת רשימה מקושרת'

הוסיפו לתכנית שכתבתם בתרגול העצמי הבסיסי הקודם (בניית שתי רשימות מקושרות, אחת של מספרים חיוביים, ושניה של מספרים שליליים), פונ' אשר מציגה את תוכנן של הרשימות.

בניית רשימה מקושרת בפונ' (תוך הוספת כל איבר חדש לסופה)

תרגול עצמי בסיסי בנושא 'בניית רשימה מקושרת בפונ''

תכנית א'

כתבו תכנית הכוללת פונ' הבונה רשימה מקושרת, ומחזירה מצביע לראש הרשימה. הרשימה תבנה באופן הבא: התכנית תקרא סדרת מספרים שלמים עד קליטת הערך אפס. את המספרים החיוביים בלבד היא תוסיף לרשימה מקושרת שהיא בונה, באופן שכל נתון חדש יתווסף בסוף הרשימה.

התכנית הראשית תזמן פונ' שניה אשר תציג את תוכנה של הרשימה.

תכנית ב'

כתבו תכנית הכוללת פונ' הבונה שתי רשימות מקושרת, ומחזירה (באמצעות פרמטרי הפניה) מצביע לראש הרשימות. הרשימות תבננה באופן הבא: התכנית תקרא סדרת מספרים שלמים עד קליטת הערך אפס. את המספרים החיוביים היא תוסיף לרשימה מקושרת אחת, ואת השליליים לרשימה שנייה, באופן שכל נתון חדש יתווסף בסוף הרשימה.

התכנית הראשית תזמן פעמיים פונ' שניה אשר תציג את תוכנה של כל אחת מהרשימות.

13.3 בניית רשימה מקושרת ממוינת

תרגול עצמי בסיסי בנושא 'בניית רשימה מקושרת ממוינת'

כתבו תכנית הבונה רשימה מקושרת ממוינת, אולם מוסיפה כל ערך לתכנית רק פעם אחת לכל היותר. כלומר עת ערך מוזן לתכנית בפעם השניה ואילך, הוא לא יוסף עוד לרשימה.

הציגו את הרשימה שבניתם.

13.4 מחיקת איבר מרשימה

תרגול עצמי בסיסי בנושא 'מחיקת איבר מרשימה'

כתבו תכנית הקוראת סדרת מספרים שלמים, עד קבלת הערך אפס, ובונה מהם רשימה מקושרת. התכנית מציגה את הנתונים ברשימה שנבנתה.

אחר קוראת התכנית ערך נוסף, ומזמנת פונ' אשר מוחקת את כל מופעיו של הערך מהרשימה.

לבסוף, מציגה התכנית את הרשימה (אחרי הסרת מופעיו של הערך).

13.5 שחרור רשימה מקושרת

תרגול עצמי בסיסי בנושא 'שחרור רשימה מקושרת'

חזרו תכנית הראשונה שכתבתם במסגרת התרגול העצמי הבסיסי בפרק זה (תכנית הקוראת מספרים שלמים עד קליטת הערך אפס. את כל המספרים החיוביים התכנית מכניסה לרשימה מקושרת אחת, ואת כל השליליים לרשימה מקושרת שניה). אחרי הצגת תוכנה של כל אחת מהרשימות, ולפני סיום התכנית, שחררו את איבריה.

13.6 היפוך רשימה מקושרת

תרגול עצמי די בסיסי בעקבות 'היפוך רשימה'

כתבו תכנית המגדירה:

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.

התכנית תדפיס:

א. את כלל הנתונים ברשימה.

ב. את המספרים הראשוניים בלבד ברשימה

(הערה קטנה: מומלץ לכתוב פונק הדפסה אחת בלבד)

13.7 בניית רשימה יחידאית מרשימה הכוללת כפילויות

דוגמה זאת ציג רק באמצעות טקסט כתוב. אין בה חידושים עקרוניים.

13.8 בניית רשימה מקושרת ממוינת בשיטת המצביע למצביע (מצביע מדרגה שניה)

13.9 מחיקת איבר מרשימה מקושרת בעזרת מצביע למצביע

דוגמה זו דומה מאוד לדוגמה בה ראינו בניה של רשימה מקושרת ממוינת תוך שימוש במצביע למצביע. אני מציג אותה כדי לעזור לכם להפנים את הנושא, באמצעות משימה נוספת.

תרגול עצמי בסיסי בנושא 'מחיקת איבר מרשימה בעזרת מצביע למצביע'

כתבו תכנית הקוראת סדרת מספרים שלמים, עד קבלת הערך אפס, ובונה מהם רשימה מקושרת. התכנית מציגה את הנתונים ברשימה שנבנתה.

אחר קוראת התכנית ערך נוסף, ומזמנת פונ' אשר מוחקת את כל מופעיו של הערך מהרשימה.

הפונ' למחיקת ערך תקבל מצביע למצביע לראש הרשימה, ותפעל תוך שבלולאה היא מתקדמת לא על אברי הרשימה, אלא על המצביעים לאברי הרשימה.

כלומר, זימון הפונ' יהיה:

rem_val(&head, val) ;

וחתימת הפונ' היא:

void rem_val(struct Node **p2head, int val) ;

לבסוף, מציגה התכנית את הרשימה (אחרי הסרת מופעיו של הערך).

13.10 הערה בעניין const עבור מצביע המועבר כפרמטר

13.11 מיון מיזוג (Merge Sort) של רשימות

דוגמה זו היא גדולה ומורכבת. היא מציגה לכם אלגוריתם מיון, בשם מיון מיזוג, שראוי שבוגר מדעי המחשב יכיר. חלק מהמיון כולל פעולה שנקראת 'מיזוג' (merge), שגם לה יש חשיבות בפני עצמה. מיון מיזוג הוא אלגוריתם רקורסיבי, וזו תכונה שניה חשובה של הדוגמה. למותר לציין שלא יעלה על הדעת שסטודנט למדעי המחשב לא ישלוט היטב ברקורסיה. לבסוף, אפשר וגם כדאי להשוות את זמן הריצה של מיון מיזוג לזה של מיונים אחרים, בפרט מיון מהיר (Quick Sort).

יש להודות על האמת שמבחינת תכנות עם רשימות מקושרות אין בדוגמה חידושים עקרוניים. מההיבט התכנותי הדוגמה חוזרת על נושאים שכבר ראינו בדוגמות הקודמות.

הצגת מיון מיזוג של רשימות נעשית בארבה סרטונים: הראשון מציג את רעיון המיון, השני והשלישי כוללים את קוד המיון וסימולציית הרצה של הקוד, והרביעי דן בזמן הריצה של האלגוריתם.

13.12 תרגילים

13.13 בחן את עצמך

השאלות שלפניכם לקוחות מבחינות. אתם מתבקשים לכתוב בהן פונ' אחת מתוך תכנית שלמה, תוך שאתם מניחים שאת מה שצריך היה להכין, טרם זימון הפונ', מישהו כבר הכין, ואת מה שצריך יהיה לעשות עם המידע שהפונ' מחזירה מישהו יעשה. אתם מתבקשים לכתוב 'רק' פונ' אחת, שהינה במידה רבה 'לב התכנית'.

כמובן שהשאלות אינן קלות, אך התמודדות מוצלחת איתן מעידה על השגת שליטה טובה בנושא.