קורס:"שפת C"

שיעור 14: טיפוסי נתונים מופשטים (ADT)

[ <<< הקודם ]

[ תוכן עניינים ]

מתוך הספר: C - מדריך מקצועי      

תוכן עניינים   1 טיפוסים מופשטים               1.1 הפרדה בין מימוש לממשק                           1.1.1 הסתרת מידע   2 מדד ליעילות: סיבוכיות               2.1 סיבוכיות כפרמטר ביצועי               2.2 סוגי סיבוכיות                           2.2.1 סיבוכיות זמן                           2.2.2 סיבוכיות מקום               2.3 השוואה בין מערך ורשימה   3 מבנה יישום ADT               3.1 קובץ הגדרות כללי               3.2 טיפוס איבר כללי Data   4 רשימה מקושרת               4.1 קובץ הממשק, list.h               4.2 קובץ המימוש, list.c               4.3 סיבוכיות זמן פעולות על הרשימה המקושרת                           4.3.1 תרגול   5 מחסנית               5.1 פעולות על המחסנית               5.2 מימוש המחסנית ע"י מערך               5.3 מימוש המחסנית ע"י רשימה               5.4 פונקצית הבדיקה               5.5 סיבוכיות זמן פעולות על המחסנית                           5.5.1 תרגיל   6 תור               6.1 פעולות על התור               6.2 פונקצית הבדיקה               6.3 סיבוכיות זמן פעולות על התור                           6.3.1 תרגול   7 עץ בינרי               7.1 פעולות על העץ               7.2 אתחול העץ               7.3 הוספת איבר לעץ                           7.3.1 הקצאת צומת ואתחולו                           7.3.2 הוספה רקורסיבית לעץ               7.4 האם איבר מסוים קיים בעץ               7.5 שחרור זיכרון העץ               7.6 סיורים רקורסיביים בעץ                           7.6.1 סיור Pre-Order                           7.6.2 סיור in-order                           7.6.3 סיור Post-Order                           7.6.4 פונקציה להדפסה כללית של העץ               7.7 פונקצית הבדיקה               7.8 סיבוכיות זמן פעולות על העץ הבינרי               7.9 סוגי עצים נוספים                           7.9.1 תרגיל   8 סיכום   9 תרגילי סיכום

טיפוסים מופשטים

הכרנו את הטיפוסים הבסיסיים הקיימים בשפת C : שלם (int), ממשי (float), תו (char), מחרוזת (char []), מערך וכן תתי-טיפוסים שלהם.

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

לדוגמא, בכדי להגדיר טיפוס מחרוזת נוח, השתמשנו בהוראה typedef :

 
typedef char String[256];
 

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

בדומה, כאשר רצינו לייצג רשימה מקושרת (ראה/י פרק 12, "הקצאת זיכרון דינמית ורשימות מקושרות") הגדרנו טיפוס רשימה ע"י

 
typedef struct 
{
          ListNode  *head;        /* head of the book list */
          ListNode  first;           /* first dummy element */
          Boolean    changed_fl; /* list change flag */
          int              count;
} List;
 

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

טיפוסי נתונים מופשטים (ADT, Abstract Data Types) הם טיפוסים המורכבים מטיפוסים בסיסיים יותר וכוללים גם פונקציונליות לטיפול בנתונים.

אנחנו נכיר בפרק זה את הטיפוסים המופשטים הבאים:

• רשימה מקושרת כללית
• מחסנית
• תור
• עץ בינרי

הפרדה בין מימוש לממשק

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

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

למשל, אם מודול A משתמש במודול B, הוא אינו צריך לדעת כיצד ממומש מודול B:

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

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

כל הבדיקות הן עפ"י קובץ הממשק (B.h) של המודול B (וכמובן גם עפ"י קובץ הממשק של A עצמו, A.h).

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

הסתרת מידע

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

קיימות שפות התומכות באופן מובנה בהסתרת מידע, בעיקר שפות לתכנות מונחה עצמים. לדוגמא, שפות C++ ו- Java מאפשרות להגדיר אילו חלקים הם פרטיים (private) במודול (מחלקה) ואילו ציבוריים (public).

בשפת C האפשרויות מוגבלות יותר, אך ניתן בכל זאת להסתיר מרכיבים מסוימים:

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

כעת למודול A גישה רק לפונקציה g() שב- B, והוא אינו "רואה" את המשתנה הגלובלי x ואת הפונקציה f(), מכיוון שהם פרטיים.

אולם מודול A יכול לבצע ייצוא עצמאי ע"י הוראת extern ובכך לעקוף את קובץ הממשק של B:

הערה: בייצוא פונקציה ההוראה extern היא אופציונלית, כלומר אבטיפוס הפונקציה הוא כשלעצמו ייצוא חוקי.

בדוגמא הנ"ל ניתן לרשום ייצוא עבור הפונקציה f() גם כך:

void f();

• בכדי למנוע את האפשרות של ייצוא עצמאי ע"י extern במודולים האחרים, ניתן לציין משתנים ופונקציות כסטטיים (static) במודול B:

המציין static גורם למשתנה גלובלי או לפונקציה להיות מקושרים באופן פנימי בלבד למודול שבו הוגדרו.

השגיאות במודול A יתקבלו ע"י המקשר (linker) בזמן הקישור של A, והן יהיו "לא נמצא המשתנה הגלובלי x" ו- "לא נמצאה הפונקציה הגלובלית f()".

מדד ליעילות: סיבוכיות

סיבוכיות כפרמטר ביצועי

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

נהוג לציין את הסיבוכיות ע"י האות O (קיצור של Order) בצירוף סדר הסיבוכיות בסוגריים: (<סדר של n>O(.

דוגמאות:

• סיבוכיות לינארית מצויינת ע"י O(n) כקיצור ל-  "Order of n", כאשר n הוא מספר האיברים שבמבנה הנתונים. סדר סיבוכיות זה כולל את הביטויים הלינאריים של n, לדוגמא:

 
 n 
 n/2
3n
4n
23n + 255
2000000n + 60000
 

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

• הסיבוכיות O(n²) מתארת סדר סיבוכיות ריבועי של n, לדוגמא :

 
5n<sup>2</sup>
3n<sup>2 </sup>+ 2n + 5
 

• אם מספר הפעולות שדורש חישוב מסויים אינו תלוי ב- n, הסיבוכיות היא מסדר קבוע והיא מצויינת ע"י O(1). למשל:

 
23
0
1000000000
 

בטבלה שבעמ' 354 מובאים סדרי הסיבוכיות הקיימים.

סוגי סיבוכיות

קיימים שני סוגי סיבוכיות: סיבוכיות זמן וסיבוכיות מקום.

סיבוכיות זמן

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

דוגמאות:

    1. סיבוכיות חיפוש איבר במערך בעל n איברים היא מסדר מספר האיברים במערך O(n). במערך ממויין, ניתן לייעל את הפעולה ל- O(log n) ע"י ביצוע חיפוש בינרי.

    2. הכנסת איבר באמצע מבנה הנתונים - לא כולל חיפוש מיקום ההכנסה - היא מסיבוכיות שונה בין מערך ורשימה: במקרה של מערך היא O(n) מכיוון שמתחייבת הזזה של כל האיברים העוקבים מקום אחד קדימה (בממוצע n/2 איברים), בעוד שעבור רשימה מקושרת הכנסת איבר כוללת מספר קבוע (וקטן) של פעולות קישור הצומת החדש. מציינים סיבוכיות זו ע"י O(1) , כלומר מסדר גודל קבוע.

    3. סיבוכיות הזמן של מיון מערך מגודל n בשיטת מיון בועות היא O(n²): אנו עוברים n פעמים על איברי המערך בחזרה החיצונית, ובחזרה הפנימית על n (פחות אינדקס החזרה החיצונית, שלא משנה את סדר גודל הסיבוכיות) - סה"כ סדר n².

    4. מיון מהיר (Quick Sort) היא שיטה הממיינת באופן רקורסיבי את המערך. סיבוכיות מיון זה היא במקרה הממוצע O(n log n), ובמקרה הגרוע O(n²).

סיבוכיות מקום

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

דוגמאות:

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

    2. סיבוכיות המקום בשיטת מיון מהיר היא O(log n) מכיוון שהיא עושה שימוש במחסנית הקריאות לצורך הרקורסיה.

השוואה בין מערך ורשימה

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

פעולה	מערך	רשימה
גישה אקראית	O(1)	O(n)
הכנסה / הוצאה  באמצע	O(n)	O(1)
הכנסה / הוצאה בסוף או בהתחלה	O(1)	O(1)
חיפוש	O(n)	O(n)
מיון בשיטת בועות	O(n2)	O(n2)
מיון מהיר (Quick sort)	O(n log n)	O(n log n)

מבנה יישום ADT

קובץ הגדרות כללי

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

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

לדוגמא, נגדיר קובץ בשם base.h באופן הבא:

 
/* base.h - basic type and constant definitions */
#ifndef BASE_H
#define BASE_H
 
/**************** TYPES *******************************/
/* a boolean type */
typedef enum {FALSE=0, TRUE=1} Boolean;
 
/* a String type */
typedef char String[256];
 
#endif
 

טיפוס איבר כללי Data

בטיפוסי הנתונים המופשטים נטפל באיבר מסוג כללי שיוגדר כך:

 
/* Data type */
typedef struct
{
          int    ID;
          float value;
} Data;
 
typedef Data *   DataPtr;
 

הטיפוס Data  - המקביל לטיפוס Book מהפרקים הקודמים - ישמש כשם טיפוס כללי לנתונים כלשהם: בדוגמא זו, המבנה Data מכיל שני נתונים - שלם וממשי.

  - השלם מציין מספר מזהה כלשהו והמספר הממשי מציין ערך.

  - כמו כן הגדרנו טיפוס שימושי,  DataPtr , כמצביע לטיפוס Data:

קבצי הממשק והמימוש מובאים בעמ' 356-357.

רשימה מקושרת

בפרק 12, "הקצאת זיכרון דינמית ורשימות מקושרות", הכרנו את מבנה הרשימה המקושרת ומימשנו באמצעותה את רשימת הספרים בתכנית הספרייה.

בסעיף זה נגדיר רשימה מקושרת כללית, המתאימה לא רק לספרים - אלא לטיפול ברשומת Data כללית:

הממשק הנדרש מרשימה מקושרת כללית:

• אתחל רשימה (list_init)
• נקה ושחרר את איברי הרשימה (list_clear)
• האם הרשימה ריקה? (list_is_emty)
• הכנס בסוף (list_push_back)
• הכנס בהתחלה (list_push_front)
• הוצא מהסוף (list_pop_back)
• הוצא מההתחלה (list_pop_front)
• הוסף לרשימה עפ"י פונקצית השוואה של האיבר (list_add)
• האם איבר נתון קיים ברשימה? (list_exist)
• הדפס את הרשימה (list_print)

תרשים פעולות ההכנסה וההוצאה:

קובץ הממשק, list.h

קובץ  הממשק מובא בעמ' 359.

קובץ המימוש, list.c

קובץ המימוש מובא בעמ' 360-363, עפ"י חלוקה לפונקציות פרטיות וציבוריות, כלומר, פונקציות שאינן מיוצאות וכאלו שמיוצאות.

תכנית הבדיקה מובאת בעמ' 363-365.

סיבוכיות זמן פעולות על הרשימה המקושרת

סיבוכיות הרשימה המקושרת היא מסדר גודל קבוע (O(1)) עבור פעולות הכנסה והוצאה בתחילת הרשימה.

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

הכנסת איבר באופן ממוין דורשת, בממוצע, מעבר על n/2 איברים, ולכן גם היא מסיבוכיות O(n).

הטבלה הבאה מציגה את סיבוכיות הפעולות על הרשימה המקושרת:

פעולה	סיבוכיות
אתחול	O(1)
ניקוי	O(n)
הכנסה באופן ממוין	O(n)
הכנסה/הוצאה מתחילת הרשימה	O(1)
הכנסה/הוצאה מסוף הרשימה	O(n)
בדיקה אם הרשימה ריקה	O(1)
האם איבר מסוים קיים ברשימה	O(n)
הדפסה	O(n)

תרגול

קרא/י סעיף זה בספר ובצע/י את תר' 1-3 שבעמ' 366.

מחסנית

מחסנית (Stack) היא מבנה נתונים שאיבריו נשלפים בסדר ההפוך מזה שבו הוכנסו:

• הכנסה - איבר חדש מוכנס בראש המחסנית
• הוצאה - איבר מוצא מראש המחסנית

סדר זה של הכנסת והוצאת נתונים נקרא LIFO (Last In First Out) - האיבר האחרון שהוכנס מוצא ראשון. שימושים נפוצים למחסנית הם ייצוג פונקציות בזמן ריצה (מחסנית הקריאות) וניתוח תחבירי במהדרים.

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

 
#define STACK_MAX_SIZE 500
 
/* stack structure */
typedef struct 
{
          DataPtr    array[STACK_MAX_SIZE];
          int              count;
} Stack;
 

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

פעולות על המחסנית

נגדיר את הפעולות הבאות על המחסנית:

• אתחל מחסנית (stack_init)
• שחרר/נקה את המחסנית (stack_clear)
• הכנס למחסנית (stack_push)
• הוצא מהמחסנית (stack_pop)
• החזר איבר עליון (stack_top)
• האם המחסנית ריקה? (stack_is_empty)
• האם המחסנית מלאה? (stack_is_full)
• הדפס את המחסנית (stack_print)

הפונקציה להחזרת האיבר העליון (stack_top) מחזירה את האיבר שבראש המחסנית מבלי להוציאו.

ממשק הפונקציות:

 
void           stack_init(Stack *pstack);
void           stack_clear(Stack *pstack);
void           stack_push(Stack *pstack, DataPtr pdata);
DataPtr    stack_pop(Stack *pstack);
DataPtr    stack_top(Stack *pstack);
Boolean    stack_is_empty(Stack *pstack);
Boolean    stack_is_full(Stack *pstack);
void           stack_print(Stack *pstack);
 

מימוש המחסנית ע"י מערך

אנו נראה כעת מימוש של פעולות המחסנית תוך שימוש במערך לשמירת האיברים:

בשלב מאוחר יותר נראה מימוש שונה של המחסנית ע"י רשימה מקושרת, וזאת מבלי לשנות את ממשק הפעולות על המחסנית.

הפונקציה stack_init מאתחלת את המחסנית:

 
void stack_init(Stack *pstack)
{
          pstack->count = 0;
}
 

הפונקציה stack_clear מנקה ומשחררת את נתוני המחסנית:

 
void stack_clear(Stack *pstack)
{
          int i;
          for(i=0; i<pstack->count; i++)
                   data_clear(pstack->array[i]);
          pstack->count = 0;
}
 

הפונקציה stack_push דוחפת איבר לראש המחסנית (כולל בדיקה שהמחסנית לא מלאה):

 
void stack_push(Stack *pstack, DataPtr pdata);
 

הפונקציה stack_pop מוציאה איבר מראש המחסנית ומחזירה אותו (אם המחסנית ריקה מוחזר NULL):

 
DataPtr  stack_pop(Stack *pstack);
 

הפונקציה stack_top מחזירה את האיבר שבראש המחסנית, מבלי להוציא אותו (אם המחסנית ריקה מוחזר NULL):

 
DataPtr  stack_top(Stack *pstack);
 

הפונקציה stack_is_empty מחזירה ערך בוליאני - האם המחסנית ריקה?

 
Boolean stack_is_empty(Stack *pstack);
 

הפונקציה stack_is_full מחזירה ערך בוליאני - האם המחסנית מלאה?

 
Boolean stack_is_full(Stack *pstack);
 

הפונקציה stack_print עוברת ומדפיסה את כל איברי המחסנית, החל מהתחתית :

 
void stack_print(Stack *pstack);
 

עיין/י בקוד הפונקציות המלא בעמ' 369-370.

פונקצית הבדיקה מובאת בעמ' 370-372.

מימוש המחסנית ע"י רשימה

מבנה הנתונים מחסנית אינו מחייב מימוש מסוים - בדוגמא הקודמת, מימשנו את המחסנית ע"י מערך בעל גודל קבוע, אך ניתן למשל לממש אותה ע"י רשימה מקושרת:

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

בקובץ הממשק של המחסנית, list_l.h (הסיומת _l מציינת מימוש ע"י רשימה), יוכרז מבנה המחסנית כך:

 
typedef struct 
{
          List list;
} Stack;
 

שים/י לב: ממשק הפונקציות של המחסנית נשאר כפי שהיה - התכנית המשתמשת במחסנית אינה משתנה כתוצאה משינוי המימוש!

נראה כעת מספר פונקציות בקובץ המימוש, stack_l.c :

  - פונקצית הדחיפה למחסנית:

 
void stack_push(Stack *pstack, DataPtr pdata)
{
          if(stack_is_full(pstack))
                   return;
          list_push_front(&pstack->list, pdata);
}
 

  - פונקצית ההוצאה:

 
DataPtr  stack_pop(Stack *pstack)
{
          if(stack_is_empty(pstack))
                   return NULL;
          else
                   return list_pop_front(&pstack->list);
}
 

  - הפונקציה top :

 
DataPtr  stack_top(Stack *pstack)
{
          if(stack_is_empty(pstack))
                   return NULL;
          else
                   return pstack->list.head->next->pdata;
}
 

  - פונקציה לבדיקה אם המחסנית מלאה:

 
Boolean stack_is_full(Stack *pstack)
{
          return FALSE;
}
 

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

פונקצית הבדיקה

פונקצית הבדיקה היא כמו קודם מכיוון שתכנית הבדיקה לא השתנתה כתוצאה משינוי מימוש המחסנית!

סיבוכיות זמן פעולות על המחסנית

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

לכן פעולות ההכנסה וההוצאה מהמחסנית הן בעלות סיבוכיות O(1). הטבלה הבאה מציגה את סיבוכיות הפעולות:

פעולה	סיבוכיות
אתחול	O(1)
ניקוי	O(n)
הכנסה	O(1)
הוצאה	O(1)
איבר עליון	O(1)
בדיקה אם המחסנית ריקה	O(1)
בדיקה אם המחסנית מלאה	O(1)
הדפסת המחסנית	O(n)

תרגיל

קרא/י סעיף זה בספר ובצע/י את תר' 1-3 שבעמ' 375.

תור

תור (Queue) הוא מבנה נתונים בעל מדיניות "נכנס-ראשון-יוצא-ראשון"
(First In First Out), או בקיצור FIFO.

התור, כשמו, שימושי למתן שרות עפ"י סדר הגעה:

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

 
typedef struct 
{
          List           list;
} Queue;
 

תרשים התור ממומש ע"י רשימה:

פעולות על התור

נגדיר את הפעולות הבאות על התור:

• אתחל תור  (queue_init)
• שחרר/נקה את התור(queue_clear)
• הכנס לתור (queue_push)
• הוצא מהתור (queue_pop)
• החזר את האיבר שבראש התור(queue_top)
• האם התור ריק? (queue_is_empty)
• הדפס את התור (queue_print)

הכנסת איבר חדש מבוצעת בסוף הרשימה, והוצאת האיבר הראשון בתור מבוצעת ע"י הוצאת האיבר מתחילתה.

התרשים הבא מציג את כוון ההכנסה וההוצאה מהתור הממומש ע"י רשימה:

הפונקציה להחזרת האיבר העליון (queue_top) מחזירה את האיבר שבראש התור מבלי להוציאו. בתרשים הנ"ל, הפונקציה תחזיר את האיבר 111.

ממשק הפונקציות:

 
void           queue_init(Queue *pqueue);
void           queue_clear(Queue *pqueue);
void           queue_push(Queue *pqueue, DataPtr pdata);
DataPtr    queue_pop(Queue *pqueue);
DataPtr    queue_top(Queue *pqueue);
Boolean    queue_is_empty(Queue *pqueue);
void           queue_print(Queue *pqueue);
 

מימוש הפונקציות:

  - אתחול התור:

 
void queue_init(Queue *pqueue)
{
          list_init(&pqueue->list);
}
 

  - שחרור הזיכרון:

 
void queue_clear(Queue *pqueue)
{
          list_clear(&pqueue->list);
}
 

  - דחיפת איבר לסוף התור:

 
void queue_push(Queue *pqueue, DataPtr pdata)
{
          list_push_back(&pqueue->list, pdata);
}
 

  - הוצאת איבר מראש התור:

 
DataPtr  queue_pop(Queue *pqueue)
{
          if(queue_is_empty(pqueue))
                   return NULL;
          else
                   return list_pop_front(&pqueue->list);
}
 

עיין/י בקוד שאר הפונקציות בהמשך.

פונקצית הבדיקה

פונקצית הבדיקה של התור מובאת בעמ' 378-379.

סיבוכיות זמן פעולות על התור

סיבוכיות ההכנסה בסוף התור, הממומש ע"י רשימה מקושרת, היא O(n). לעומת זאת ההוצאה מראש התור היא מיידית ומסיבוכיות O(1).

פעולות הניקוי וההדפסה הן מסדר גודל של מספר האיברים בתור (O(n)).

הטבלה הבאה מציגה את סיבוכיות הפעולות על התור:

פעולה	סיבוכיות
אתחול	O(1)
ניקוי	O(n)
הכנסה בסוף	O(n)
הוצאה מההתחלה	O(1)
בדיקה אם התור ריק	O(1)
הדפסה	O(n)

תרגול

קרא/י סעיף זה בספר ובצע/י את תר' 1-3 שבעמ' 380.

עץ בינרי

עץ בינרי (Binary Tree) הוא מבנה נתונים הבנוי בצורת עץ הפוך: שורש העץ מצוייר למעלה וה"ענפים" למטה:

כל צומת בעץ מכיל מצביע לנתונים, pdata, ושני מצביעים לשני צמתים בנים: בן שמאלי (left son) ובן ימני (right son). הצומת שבראש העץ הוא צומת השורש (root).

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

מבנה הצומת מוגדר כך:

 
typedef struct BTreeNode_tag
{
          DataPtr    pdata;
          struct                  BTreeNode_tag  *left;
          struct                  BTreeNode_tag  *right;
} BTreeNode;
 

אם לצומת אין בן מסוים, ערך המצביע לבן יהיה NULL. מבנה העץ בכללותו מוגדר כך:

 
typedef struct 
{
          BTreeNode        *root;                        /* root of the binary tree */
          int              count;         /* number of elements in the tree */
} BTree;
 

מבנה העץ מכיל מצביע לצומת שבשורש העץ ומונה מספר האיברים.

פעולות על העץ

נגדיר את הפעולות הבאות על העץ:

• אתחל עץ(btree_init)
• הוספת איבר לעץ (btree_add)
• האם איבר מסוים קיים בעץ? (btree_exist)
• האם העץ ריק? (btree_is_empty)
• הדפס את העץ (btree_print)

אתחול העץ

הפונקציה הבאה מאתחלת מבנה עץ המועבר לה כפרמטר:

 
void btree_init(BTree *pbtree)
{
          pbtree->root = NULL;
          pbtree->count = 0;
}
 

שורש העץ מצביע ל- NULL ומספר האיברים מאופס.

הוספת איבר לעץ

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

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

  - אחרת, עוברים לבן השמאלי וההשוואה מבוצעת איתו.

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

פעולת הרקורסיה נעצרת כאשר אנו מגיעים לנתיב המוביל ל- NULL, כלומר לקצה העץ, ואז פשוט מוסיפים את האיבר החדש ע"י הוספת צומת חדש לעץ וקישורו במקום המתאים.

לדוגמא, בהינתן העץ הקודם, נניח שמוכנס איבר חדש עם ערך 5:

  - משווים את האיבר החדש, 5, עם צומת השורש ומכיוון שהוא קטן ממנו עוברים לבן השמאלי, 7.

  - בהשוואה עם צומת 7 , 5 קטן יותר ואנו עוברים שוב לבן השמאלי, 4.

  - מכיוון ש- 5 גדול מ- 4 עוברים לבן הימני, שהוא NULL.

  - מוסיפים את הצומת החדש לעץ כבן ימני של צומת 4

תרשים העץ לאחר ההוספה:

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

לתזכורת לגבי פונקציות רקורסיביות, ראה/י פרק 6, "פונקציות", סעיף "רקורסיה".

הקצאת צומת ואתחולו

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

 
static BTreeNode *btree_new_node(DataPtr pdata)
{
          BTreeNode *pnode = malloc(sizeof(BTreeNode));
          pnode->pdata = pdata;
          pnode->left = NULL;
          pnode->right = NULL;
          return pnode;
}
 

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

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

הוספה רקורסיבית לעץ

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

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

 
static void btree_add_to_subtree(BTreeNode *root, BTreeNode *pnode)
{
          if(data_compare(pnode->pdata, root->pdata) < 0) /* add as left son */
          {
                   if(root->left == NULL)
                            root->left = pnode;
                   else 
                            btree_add_to_subtree(root->left, pnode);
          }
          else  /* add as right son */
          {
                   if(root->right == NULL)
                            root->right = pnode;
                   else 
                            btree_add_to_subtree(root->right, pnode);
          }
}
 

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

    אם לא (NULL) - מוסיפים את הצומת החדש כבן שמאלי

    אם כן - קוראים באופן רקורסיבי לפונקציה btree_add_to_subtree.

בדיקה מקבילה מבוצעת בצד הימני של העץ.

הפונקציה btree_add_to_subtree קוראת לעצמה באופן רקורסיבי עד להגעה ל"עלה" בעץ - כלומר לצומת שאין לו בן ימני/שמאלי - ומוסיפה את הצומת החדש במקום המתאים.

מודול העץ הבינרי מספק פונקציה ציבורית להוספת נתון לעץ. פונקציה זו קוראת ל- btree_add_to_subtree להוספה רקורסיבית לעץ:

 
void btree_add(BTree *pbtree, DataPtr pdata)
{
          if(btree_is_empty(pbtree))
                   pbtree->root = btree_new_node(pdata);
          else
                   btree_add_to_subtree(pbtree->root, pdata);
          pbtree->count++;
}
 

האם איבר מסוים קיים בעץ

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

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

הפונקציה הפרטית btree_exist_in_subtree מבצעת בדיוק את האלגוריתם הנ"ל באופן רקורסיבי. הפונקציה מקבלת כפרמטר מצביע לתת-עץ ומצביע לנתון.

 
static Boolean btree_exist_subtree(BTreeNode *root, DataPtr pdata);
 

קוד הפונקציה מובא בעמ'  385.

פונקציה זו נקראת ע"י הפונקציה הציבורית, btree_exist, הבודקת קיום של איבר בעץ ע"י קריאה ל- btree_exist_subtree עם מצביע לשורש:

 
Boolean btree_exist(BTree *pbtree, DataPtr pdata)
{
          return btree_exist_subtree(pbtree->root, pdata);
}
 

שחרור זיכרון העץ

גם מחיקת איברי העץ מבוצעת ע"י פונקציה רקורסיבית פרטית:

 
static void btree_del_subtree(BTreeNode *root)
{
          if(root==NULL)
                   return;
          btree_del_subtree(root->left);
          btree_del_subtree(root->right);
          data_clear(root->pdata); /* free the data */
          free(root); /* free the node */
}
 

הסבר: הפונקציה btree_del_subtree היא פונקציה פרטית של המודול, הנקראת ע"י הפונקציה הציבורית btree_clear (להלן). הפונקציה בודקת את תנאי העצירה של הרקורסיה - הגעה לצומת NULL - וחוזרת אם התשובה חיובית:

 
          if(root==NULL)
                   return;
 

בשלב הבא היא מבצעת קריאה רקורסיבית לעצמה למחיקת תת-העץ השמאלי ואח"כ הימני:

 
          btree_del_subtree(root->left);
          btree_del_subtree(root->right);
 

לבסוף משוחררים נתוני הצומת הנוכחי והצומת עצמו:

 
          data_clear(root->pdata); /* free the data */
          free(root); /* free the node */
 

הפונקציה הרקורסיבית brtee_del_subtree נקראת ע"י הפונקציה btree_clear המוחקת את כלל העץ ומאפסת את המבנה ע"י קריאה ל- btree_init:

 
void btree_clear(BTree *pbtree)
{
          btree_del_subtree(pbtree->root);
          btree_init(pbtree);
}
 

סיורים רקורסיביים בעץ

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

• סרוק את השורש, את הבן שמאלי ולבסוף את הבן ימני (Pre-Order)
• סרוק את הבן שמאלי, את השורש ולבסוף את הבן ימני (In-Order)
• סרוק את הבן שמאלי, את הבן ימני ולבסוף את השורש (Post-Order)

סיור Pre-Order

לדוגמא, הפונקציה הרקורסיבית (הפרטית) הבאה מדפיסה תת-עץ נתון ב- pre-order:

 
static void btree_preorder(BTreeNode *root)
{
          if(root)
          {
                   data_output(root->pdata);
                   btree_preorder(root->left);
                   btree_preorder(root->right);
          }
}
 

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

  - נתוני הצומת מודפסים

 
                   data_output(root->pdata);
 

  - מודפס תת-העץ השמאלי של root

 
                   btree_preorder(root->left);
 

  - מודפס תת-העץ הימני של root

 
                   btree_preorder(root->right);
 

תנאי העצירה של הרקורסיה הוא הגעה ל- NULL.

תרשים הסיור:

פלט הפונקציה עבור העץ שבתרשים:

 
    ID=9, value=99.000000
    ID=7, value=77.000000
    ID=4, value=44.000000
    ID=1, value=11.000000
    ID=5, value=55.000000
    ID=8, value=88.000000
    ID=13, value=133.000000
    ID=11, value=111.000000
    ID=10, value=100.000000
    ID=17, value=177.000000
    ID=22, value=222.000000
 

סיור in-order

הפונקציה btree_inorder() סורקת את צמתי העץ ומדפיסה את ערכיהם ב- In-Order:

 
static void btree_inorder(BTreeNode *root)
{
          if(root)
          {
                   btree_inorder(root->left);
                   data_output(root->pdata);
                   btree_inorder(root->right);
          }
}
 

תרשים הסיור:

פלט הפונקציה:

 
ID=1, value=11.000000
ID=4, value=44.000000
ID=5, value=55.000000
ID=7, value=77.000000
ID=8, value=88.000000
ID=9, value=99.000000
ID=10, value=100.000000
ID=11, value=111.000000
ID=13, value=133.000000
ID=17, value=177.000000
ID=22, value=222.000000
 

סיור Post-Order

הפונקציה btree_postorder() מבצעת סיור Post-Order:

 
static void btree_postorder(BTreeNode *root)
{
          if(root)
          {
                    btree_postorder(root->left);
                   btree_postorder(root->right);
                   data_output(root->pdata);
          }
}
 

תרשים הסיור:

פלט הפונקציה:

 
ID=1, value=11.000000
ID=5, value=55.000000
ID=4, value=44.000000
ID=8, value=88.000000
ID=7, value=77.000000
ID=10, value=100.000000
ID=11, value=111.000000
ID=22, value=222.000000
ID=17, value=177.000000
ID=13, value=133.000000
ID=9, value=99.000000
 

פונקציה להדפסה כללית של העץ

הפונקציה הציבורית btree_print() מדפיסה את איברי העץ בכל שלוש הצורות, ע"י קריאה מתאימה לכל אחת מהפונקציות הפרטיות.

קוד הפונקציה מובא בעמ' 390.

פונקצית הבדיקה

פונקצית הבדיקה של העץ הבינרי מובאת בעמ' 391.

סיבוכיות זמן פעולות על העץ הבינרי

סיבוכיות פעולות ההכנסה והחיפוש של איבר בעץ תלויה בגובה העץ, h: בממוצע, בכדי להכניס איבר לעץ או בחיפושו נידרש לעבור על h/2 איברים, ולכן הסיבוכיות היא O(h).

שאלה: מהו גבהו של העץ, h, ביחס למספר האיברים, n?

תשובה: אם נניח שלכל צומת שני בנים והעץ מאוזן, אזי נתונה הנוסחה:

n = 2^h - 1

כלומר, בכל רמה בעץ גדל מספר האיברים פי 2. לדוגמא, עבור עץ בגובה 3:

מספר האיברים הוא:

n = 2³ - 1 = 7

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

n = 2^h

וכעת ניתן לבטא את h ע"י לוגריתם:

h = log n

בסיס הלוגריתם הוא 2, אך נהוג להשמיטו בחישובי סיבוכיות. לכן סיבוכיות הכנסה וחיפוש של איבר בעץ הבינרי היא O(log n).

פעולות הניקוי וההדפסה הן מסיבוכיות O(n) מכיוון שהן מחייבות מעבר על כלל האיברים.

הטבלה הבאה מציגה את סיבוכיות הפעולות על העץ:

פעולה	סיבוכיות
אתחול	O(1)
ניקוי	O(n)
הכנסה	O(log n)
בדיקה אם איבר נתון קיים בעץ	O(log n)
בדיקה אם העץ ריק	O(1)
הדפסה	O(n)

סוגי עצים נוספים

קיימים עצים מסוגים שונים ובוריאציות שונות, בין הנפוצים:

• עץ מאוזן - עץ ששני צידיו מאוזנים. בעץ זה מובטח שגובה העץ יהיה תמיד מסדר גודל  log n. האיזון ממומש ע"י הכנסה באופן מאוזן לעץ, תוך ביצוע "גלגולים" במידת הצורך.
• עץ 2-3  - עץ שכל צומת בו יכול להכיל 2 או שלושה צמתים בנים.
• ערמה - עץ שבו האיבר המקסימלי (או מינימלי) נמצא בשורש, ונגיש בסיבוכיות O(1).

תרגיל

קרא/י סעיף זה בספר ובצע/י את התרגיל שבעמ' 393.

סיכום

• טיפוסי נתונים מופשטים (ADT, Abstract Data Types) הם טיפוסים המורכבים מטיפוסים בסיסיים יותר וכוללים גם פונקציונליות לטיפול בנתונים.

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

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

רמת הסיבוכיות מצוינת ע"י האות האנגלית O בצירוף סדר גודל הסיבוכיות בסוגריים.

• רשימה מקושרת (Linked List) היא מבנה נתונים דינמי המורכב כשרשרת של צמתים. כל צומת מכיל מצביע לנתונים ומצביע לצומת הבא ברשימה.
• מחסנית (Stack) היא מבנה נתונים שאיבריו נשלפים בסדר הפוך לזה שבו הוכנסו, כלומר "נכנס אחרון יוצא ראשון" (FIFO, Last In First Out).

ראינו שניתן לממש את המחסנית הן ע"י מערך והן ע"י רשימה מקושרת, מבלי לשנות את הממשק שלה.

• תור (Queue) הוא מבנה נתונים מופשט המספק פונקציות להכנסת איברים ולהוצאה לפי הכלל "נכנס ראשון יוצא ראשון" (FIFO, First In First Out).
• עץ בינרי (Binary Tree) הוא מבנה נתונים הבנוי בצורת עץ הפוך: שורש העץ מצוייר למעלה וה"ענפים" למטה.

  - כל צומת בעץ מכיל מצביע לנתונים, pdata, ושני מצביעים לשני צמתים בנים: בן שמאלי (left son) ובן ימני (right son).

  - הצומת שבראש העץ הוא צומת השורש (root). 

  - פעולות על העץ מבוצעות בד"כ באופן רקורסיבי.

תרגילי סיכום

בצע/י את תרגילי הסיכום שבסוף פרק זה.

[ <<< הקודם ]

[ תוכן עניינים ]