2.8 הערות לגבי שפות תיכנות

מבנה נתונים ואלגוריתמים

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

של שפת ה- Ada- אחת משפות התוכנה היותר חשובות.

2.8.1 פונקציות כטיפוסי מידע

2.7.1 פונקציות בשפת C

שפת C מאפשרת להשתמש בפונקציה בפריט מידע. דבר זה מאפשר להעביר פונקציה בארגומנט לפונקציה אחרת.

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

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

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

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

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

כלומר אנו זקוקים לפונקציה:

Int ItemCmp ( void *a, void *b );

אשר תחזיר 1-, 0 או 1+ וזאת בהתאם ליחס בין משתנה a ומשתנה b (גדול, שווה או קטן). (שים לב כי אנו מאפשרים מושג כללי של 'קטן מ': ה-ItemCmp יכולה לסדר פרטים בהתאם לכל כלל אשר עשוי להתאים לפריטים אלו.)

כך, אנו מוספים למבנה אוסף הנתונים שלנו, פונקצית השוואה:

struct t_collection {
 int item_cnt;
 int (*ItemCmp)( void *, void * );
 ....
 };

ItemCmp הוא מצביע לפונקציה אשר אב הטיפוס שלה הינו:

Int ItemCmp ( void *, void * );

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

פונקצית ה-ConsCollection הופכת כעת ל:

 
 collection ConsCollection( int max_items, 
 int (*ItemCmp)( void *, void * ) );

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

#include "widget.h" /* import the ADT for widgets */
 int WidgetComp( widget, widget );
 collection LotsOfWidgets;
 
 LotsOfWidgets = ConsCollection( large_no, WidgetComp );

בגוף ה-ADT, בפונקצית ItemCmpמשתמשים על מנת לבטל את הקשר של המצביע לפונקציה ושימוש בה אופן נורמלי.

ב-FindInCollection, אנו עשויים לקבל:

int FindInCollection( collection c, void *a )
 {
 .....
 if ( (*(c->ItemCmp))( c->items[i], a ) == 0 )
 {
 /* Found match ... */
 ....
 }

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

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

בדוגמאות קוד המקור , פונקצית ה- ItemCmpהוספה לאוסף נתונים במבנה של עץ.

הגדרה חדשה לאוסף נתונים

מימוש חדש לעץ

המשך ל: ADT ה-Ada ;חזור ל: תוכן עניינים