C/C++ מדריכי
הצגה מזורזת :C++ הבנת
C++ הקדמה להיררכית מחלקות ב C הקדמה לתכנות ב דף הבית

שיעור 5 - ירושה

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

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

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

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

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

יתרונות אלה הם שגורמים לאנשים להתלהב מתכנות מונחה עצמים.

5.1 דוגמא לירושה

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

#include <iostream.h> 

class List{
    int array[100];
    int count;
public:
    List(): count(0) {}
    ~List() {}
    void Insert( int n, int location )
    {
        int i;
        for (i=count; i >= location; i--)
            array[i+1] = array[i];
        array[location]=n;
        count++;
    }
    int  Get( int location ) {return array[location];}
    int Size() { return count; }
};

void main()
{
    List list;
    int i, value;

    for (i=0; i < 10; i++)
        list.Insert(i,i);
    list.Insert(100,5);
    list.Insert(200,7);
    list.Insert(300,0);
    for (i=0; i < list.Size(); i++)
        cout << list.Get(i) << endl;
}

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

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

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

ברור שדרך אחת לעשות זאת היא פשוט לשנות את המחלקה List שהוצגה לעיל. ב ++C משתמשים במקום זאת בירושה על מנת לערוך שינויים. ניצור מחלקת SortedList על ידי ירושת המחלקה List ושינויה. נתחיל בהוספת תכונת ההכנסה הממוינת:

class SortedList: public List
{
public:
    SortedList():List() {}

    void SortedInsert(int n)
    {
        int i,j;

        i=0;
        do
        {
            j = Get(i);
            if (j < n ) i++;
        } while (j < n && i < Size());
        Insert(n, i);
    }
};

המחלקה List היא זהה לחלוטין -- פשוט יצרנו את מחלקת ה SortedList על גביה. מחלקת ה SortedList יורשת את ההתנהגות שלה ממחלקת ה List -- היא נגזרת ממחלקת ה List. המחלקה List היא מחלקת הבסיס ל SortedList.

המחלקה List עוברת בירושה בשורה הראשונה:

class SortedList: public List

הנקודתיים מציינות שאנחנו יורשים משהו. המילה public מציינת שאנחנו רוצים שהפונקציות והמשתנים שהם פומביים ב List יישארו פומביים במחלקה SortedList. יכולנו גם להשתמש ב private או protected. בכל אחד ממקרים אלו כל המשתנים והפונקציות שהם פומביים במחלקה שאנחנו יורשים היו מוחלפים במחלקה הנגזרת. השימוש ב public כאן הוא הסטנדרט.

הדיאגרמה שלהלן מציגה את מה שקורה:

המחלקה SortedList פשוט מרחיבה את המחלקה List. לכל מי שמשתמש במחלקה SortedList יש גישה לפונקציות הזמינות ב List נוסף על הפונקציות החדשות הזמינות ב SortedList.

הבנאי של SortedList הוא גם חדש -- השתמשנו בנקודתיים כאן כדי לקרוא לבנאי של המחלקה אותה יורשים:

SortedList() : List() {}

שורה זו אומרת שיש לקרוא לבנאי שנקרא List ממחלקת הבסיס, ושהבנאי של SortedList לא צריך לעשות שום דבר משל עצמו.

ביתרת המחלקה SortedList אנחנו פשוט מוסיפים פונקצית SortedInsert חדשה למחלקה. פונקציה חדשה זו משתמשת בפונקציות הישנות Get ,Insert, ו Size מהמחלקה List לפי הצורך, אבל היא לא ניגשת לאף אחד מה data members של המחלקה List ישירות כיוון שהיא לא יכולה -- הם פרטיים למחלקה List, כך שלא ניתן לראות אותם במחלקה היורשת.

נניח שאתה רוצה שיהיה לך משתנה או פונקציה שנראית כפרטית למשתמשים מחוץ למחלקה אבל נראית כפומבית למחלקות שיורשות את המחלקה. לדוגמא, נניח שהמחלקה SortedList הייתה צריכה גישה ישירה למשתנה המערך ב List על מנת לשפר את הביצוע שלה, אבל אנחנו עדיין רוצים למנוע ממופעים רגילים של List ו SortedList מלגשת ישירות למערך. ניתן להשתמש במילה :protected באותו אופן כמו :public או :private כדי לציין את ההתנהגות הזו. באמצעות הצהרה על המערך כחבר protected ב List, ניתן יהיה לגשת אליו מהמחלקה הנגזרת SortedList אבל לא ממופעים רגילים של List או SortedList.

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

class SortedList: 
public List{
private:
    int total;
public:
    SortedList():List(), total(0) {}
    void Insert( int n, int location )
    {
        total = total + n;
        List::Insert(n, location);
    }
    int GetTotal() { return total; }
    void SortedInsert(int n)
    {
        int i,j;
        i=0;
        do
        {
            j = Get(i);
            if (j < n ) i++;
        } while (j < n && i < Size());
        Insert(n, i);
    }
};

בגירסה זו של מחלקת ה SortedList הוספנו data member חדש בשם total, פונקציה חברה חדשה GetTotal שמחזירה את הסכום הכולל, ופונקציה חדשה Insert שרומסת את הפונקציה Insert הקיימת. כמו כן שינינו את הבנאי של SortedList כך שהוא מאתחל את total. כעת כל אימת שנעשה שימוש במחלקה SortedList וקוראים לפונקציה Insert, ניגשים לגרסה החדשה של פונקצית ה Insert במקום לגרסה הישנה ב List. אותו הדבר נעשה גם עם פונקצית ה SortedInsert -- כאשר היא קוראת ל Insert היא קוראת לגרסה החדשה.

הקוד לפונקצית ה Insert החדשה הוא ברור:

    void Insert( int n, int location )
    {
        total = total + n;
        List::Insert(n, location);
    }

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

5.2 דוגמא מתקדמת יותר

הבה ניקח את מה שלמדנו לגבי ירושה ונשתמש בו כדי ליצור מחלקה מציאותית לדוגמא. מה שנרצה לעשות זה ליצור מחלקה של מספר חדש בשם "multi-precision integer" (מספר שלם רב דיוק), או "mint". טיפוס מספר שלם זה יפעל כמו מספר שלם רגיל, אבל יהיו לו עד 100 ספרות (לעת עתה -- מאוחר יותר נראה איך הוא מתרחב לכמה ספרות שהזיכרון יכול להחזיק תוך שימוש ברשימות מקושרות). mint מאפשר לך לעשות דברים כמו למצוא את הערך הריאלי של !60, או למצוא את הערך ה 300 בסדרת פיבונצ'י.

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

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

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

כעת הבה נתבונן בחיבור פשוט, כפי שמוצג בתרשים להלן:

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

מדיון זה ועבודתנו הקודמת עם רשימות ניתן לשער שקרוב לודאי שהרשימה תזדקק ליכולות הבאות:

  • בנאי והורס
  • הוספה להתחלה - AddToFront
  • הוספה לסוף - AddToEnd
  • קבלת האיבר הראשון - GetFirst
  • קבלת האיבר האחרון - GetLast
  • קבלת האיבר הקודם - GetPrevios
  • קבלת האיבר הבא - GetNext
  • קבלת הגודל - Size
  • ניקוי - Clear

הקוד להלן מיישם את הרשימה:

class List
{
    int array[100];
    int count;
    int pointer;
public:
    List(): count(0), pointer(0) {}
    ~List() {}
    void AddToFront(int n)
    {
        int i;
        for(i=count; i >= 1; i--)
            array[i]=array[i-1];
        array[0]=n;
        count++;
    }
    void AddToEnd(int n)
    {
        array[count++]=n;
    }
    // &n is a reference - see tutor 2
    int GetFirst(int & n)  
    {
        if (count==0)
            return 1;
        else
        {
            n=array[0];
            pointer=0;
            return 0;
        }
    }
    int GetLast(int & n)
    {
        if (count==0)
            return 1;
        else
        {
            n=array[count-1];
            pointer=count-1;
            return 0;
        }
    }
    int GetPrevious(int & n)
    {
        if (pointer-1 < 0)
            return 1;
        else
        {
            pointer--;
            n=array[pointer];
            return 0;
        }
    }
    int GetNext(int & n)
    {
        if (pointer+1 > count-1)
            return 1;
        else
        {
            pointer++;
            n=array[pointer];
            return 0;
        }
    }
    int Size() { return count; }
    void Clear() { count = 0; }
};

קוד זה אמור להיות די ברור לך בשלב זה. List היא פשוט רשימה כללית של מספרים שלמים. data member בשם pointer מצביע לאחד מהאלמנטים ברשימה ומקודם באמצעות ארבע פונקציות ה Get.... כל אחת מהפונקציות הללו מחזירה 0 בהצלחה ו 1 בכישלון (לדוגמא, אם pointer הוא על האלמנט ה 0 של הרשימה אזי אין אלמנט קודם לקבל והפונקציה GetPrevios תחזיר 0). שתי פונקציות ה Add... מוסיפות בהתחלה ובסוף של הרשימה בהתאמה -- כרגע אין בהן בדיקת שגיאות. הפונקציה AddToFront מכילה אי יעילות פנימית כיוון שעליה להזיז את כל תכולת המערך הצידה באלמנט אחד עבור כל הכנסה.

המחלקה Mint יורשת את List ומשתמשת בה כדי לבנות את טיפוס ה mint הממשי. היא מיישמת שני בנאים (בנאי ברירת מחדל שלא מקבל פרמטרים ובנאי נוסף שמקבל מחרוזת ומשתמש בה כדי למלא את הרשימה), וגם פונקציות שמחברות שני mints ומדפיסות mint. הקוד מוצג להלן:

class Mint: public List
{
public:
    Mint():List() {}
    Mint(char *s):List()
    {
        char *p;
        for (p=s; *p; p++)
            AddToEnd(*p-'0');
    }
    void Add(Mint & a, Mint & b)
    {
        int carry, temp;
        int erra, errb, na, nb;

        carry=0;
        Clear();
        erra=a.GetLast(na);
        errb=b.GetLast(nb);
        while (!erra || !errb)
        {
            if (erra)
                temp=nb+carry;
            else if (errb)
                temp=na+carry;
            else
                temp=na+nb+carry;
            AddToFront(temp%10);
            carry=temp/10;
            erra=a.GetPrevious(na);
            errb=b.GetPrevious(nb);
        }
        if (carry > 0)
            AddToFront(carry);
    }
    void Print()
    {
        int n, err;

        err=GetFirst(n);
        while( !err )
        {
            cout << n;
            err=GetNext(n);
        } 
        cout << endl;
    }
}; 

פונקצית ה main הבאה בודקת את מחלקת ה mint באמצעות חיבור שני מספרים והדפסת הסכום:

void main()
{
    Mint a("1234567");
    Mint b("1234");
    Mint c;

    c.Add(a,b);
    c.Print();
}

הבנאים ופונקצית ה Print הם פשוטים וברורים. פונקצית ה Add עשויה להזכיר לך את ימי בית הספר היסודי, כיוון שהיא מבצעת חיבור בסגנון הישן. היא מתחילה עם הספרות האחרונות של שני המספרים שמחברים, מחברת את הספרות הללו, שומרת את התוצאה ב mint הנוכחי, וזוכרת את ערך הנשא. לאחר מכן היא ממשיכה הלאה ברשימה. כיוון שסביר להניח שלשני מספרים מספר שונה של ספרות, הקוד צריך לבדוק כל הזמן שלא נגמרות לו הספרות באחד ה mints. הוא עושה זאת על ידי שימוש ב erra ו errb. ברגע ששני ה mints נגמרו הוא בודק את carry ושומר ספרה אחרונה אם יש צורך.

על ידי הרצת קוד הבדיקה תראה שהמחלקה Mint פועלת כפי שהסברנו ויכולה לחבר שני מספרים בני עד 100 ספרות כל אחד. לאחר שתשתמש במחלקה Mint זמן מה למרות שתתחיל לראות בעיה עם פונקצית ה Add -- אין כל דרך לומר משהו כמו "m=m+1", או בפורמט הנדרש כאן "m.Add(m,one);" כאשר one אותחל ל "1". הסיבה לכך נעוצה בעובדה ש Add צריכה לנקות את היעד לתוצאה לפני שהיא יכולה לשים בו ערך, וזה גורם לאובדן של נתונים הכרחיים במקרה המוצג כאן.

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

    void Add(Mint & a, Mint & b)
    {
        int carry, temp;
        int erra, errb, na, nb;
        Mint x;

        carry=0;
        erra=a.GetLast(na);
        errb=b.GetLast(nb);
        while (!erra || !errb)
        {
            if (erra)
                temp=nb+carry;
            else if (errb)
                temp=na+carry;
            else
                temp=na+nb+carry;
            x.AddToFront(temp%10);
            carry=temp/10;
            erra=a.GetPrevious(na);
            errb=b.GetPrevious(nb);
        }
        if (carry > 0)
            x.AddToFront(carry);
    *this = x;
    }

בגרסה זו של Add נוצר ערך זמני בשם x. התוצאות של החיבור מוכנסות לתוך x ספרה אחר ספרה. השורה האחרונה של הפונקציה מעתיקה את x לתוך המופע הנוכחי. מצביע ה this זמין בכל מופע של מחלקה ב ++C -- הוא מצביע למופע הנוכחי. כלומר, this הוא מצביע שמצביע ל data members (המבנה) שמרכיבים את המופע הנוכחי. במקרה זה אנחנו משתמשים ב this כיוון שהוא חוסך בקוד. האלטרנטיבה תהיה להחליף את השורה האחרונה ב:

array = x.array;
count = x.count;
pointer = x.pointer;

הערך this* הוא המבנה אליו מצביע this, ויותר יעיל להעתיק את כל המבנה בבת אחת.

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

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

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

    int Equal(Mint & a)
    {
        if (a.Size()!=Size())
            return 0;
        else
        {
            int i, na, nb;
            a.GetFirst(na);
            GetFirst(nb);
            for (i=0; i < a.Size(); i++)
                if (na!=nb)
                    return 0;
                else
                {
                    a.GetNext(na);
                    GetNext(nb);
                }
            return 1;
        }
    }

בהינתן קיום הפונקציה הזו, הקוד הבא ימצא את המספר ה 100 בסדרת פיבונצ'י:

void main()
{
    Mint max("100");
    Mint counter("1"), one("1");
    Mint t1("0"), t2("1");
    Mint d;

    do
    {
        d.Add(t1,t2);
        t1=t2;
        t2=d;
        counter.Add(counter,one);
    } while (!counter.Equal(max));
    d.Print();
}

הקוד משתמש בשני ערכים t1 ו t2 כדי לזכור את שני הערכים הקודמים. הם מחוברים יחד ואז מוזזים במקום אחד. המונה אז מוגדל והלולאה ממשיכה עד שהמונה מגיע לערך הרצוי. באמצעות שימוש בקוד זה נמצא שהמספר ה 100 הוא 354,224,848,179,261,915,075.

5.3 סיכום

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

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




לדף הראשון

<< לדף הקודם

לדף הבא >>