החומר המופיע בעמוד זה פורסם לראשונה בכתב העת "הבטים בהוראת מדעי המחשב" גליון יוני 2002, עמודים 49-51

לא ניתן לעשות שימוש מסחרי בחומר זה ללא רשות בכתב מן המחברים או מערכת כתב העת

טיפוסי נתונים מופשטים בשפת C

פרופ' מוטי בן-ארי
המחלקה להוראת המדעים, מכון ויצמן למדע, רחובות

moti.ben-ari@weizmann.ac.il

 
מבוא

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

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

 

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

 

מושגים חשובים בשפת C

 

קובץ אין בשפת C מושג של יחידת תכנה (כגון תכנית, מודול, יחידה) פרט ליחידה הפיזית של הקובץ. ניתן להגדיר פונקציה בשם main באחד הקבצים, ואז פונקציה זו תתבצע כתוצאה מ"הרצת התכנית". הקובץ הוא גם יחידת קומפילציה, ואולם הקומפילציה של קובץ אחד היא בלתי-תלויה לחלוטין בקומפילציה של קובץ אחר. (לשם השוואה: בשפת Turbo Pascal, הפיסקה uses קושרת קומפילציה של יחידה אחת לשניה.) בשפת C, הקשר בין פונקציות ומשתנים בקבצים שונים מתבצע רק בזמן קשירה (link), בהתאם להצהרות הנמצאות בתוך הקבצים השונים.

 

קובץ include כדי להבטיח תאימות בין ההצהרות בקבצים שונים, קיים הסכם להכניס הצהרות המשותפות למספר קבצים, לתוך קובץ מיוחד הנכלל (include) בקבצים בזמן קומפילציה. לפי ההסכם, לקבצים אלה סיומת “h”. שים לב, שאין שום בדיקה האם הקובץ מעודכן, כלומר, אם אתה משנה את הקובץ הנכלל, לא תקבל הודעה שיש לבצע קומפילציה מחדש לכל הקבצים המשתמשים בו. קיימים כלים חיצוניים, כגון make או האופציה project במהדר של Borland C, המפקחים על מצב עדכון קבצי ה- include, ומומלץ מאוד להשתמש באחד מהכלים האלה.

 

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

int incr2 (int i);                 // declaration

int incr2 (int i);                 // declaration

int incr2 (int i) { return i+2; }   // definition

 

תחום (scope) וראות (visibility) להצהרה או להגדרה המופיעה ישירות בתוך הקובץ (כלומר לא בתוך פונקציה) קיימת תכונה הנקראת תחום קובץ (file scope), וניתן לראות אותה ולהשתמש בה בתוך הקובץ ממקום ההצהרה/הגדרה ואילך. אם מצורף המפרט (specifier) extern, ניתן לראות אותה גם מחוץ לקובץ, ואם מצורף המפרט static, אי-אפשר לראות אותה מחוץ לקובץ. ברירות המחדל הן שונות עבור משתנה ופונקציה: למשתנה ברירת המחדל היא static ולפונקציה ברירת המחדל היא extern.  הערה: למפרט static תפקיד אחר ושונה בשפת C. המפרט משמש להגדרת משתנה בתוך פונקציה שיהיה לו רק מופע אחד לכל הזימונים שלה. בדוגמה שלהן, קיים רק משתנה currentkey אחד המשותף לכל הזימונים, כך שעדכון המשתנה בזימון אחד "יישמר" לזימון הבא.

int getkey ( ) {

     static int currentkey = 0;

     return currentkey++;

}

כמובן, שאי-אפשר לראות את המשתנה מחוץ לפונקציה, כל שכן מחוץ לקובץ.

 

מפרט (typedef) לשם נרדף לטיפוס בשפת C ניתן לצרף להצהרה את המפרט typedef. מפרט זה מספק שם נרדף לטיפוס. למשל, typedef *int INTPTR מצהיר על INTPTR כשם נרדף למצביע למספר שלם. לא מדובר ביצירת טיפוס חדש כמו שנוצר בהצהרת type  בשפת Pascal או בהצהרת class בשפות C++  ו- Java. בדוגמה, השם INTPTR יכול להחליף את *int ולהיפך ללא כל שינוי במשמעות התכנית. השימוש במפרט typedef עשויה להקל על קריאות התכנית.

 

כיצד לממש טיפוס נתונים מופשט בשפת C

 

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

 

בשלב ראשון נייצר קובץ include בשם stack.h שישמש כממשק של טיפוס הנתונים המופשט. תחילה נצהיר על תבנית הנתונים של טיפוס הנתונים המופשט, ואחר כך נצהיר על הפעולות המתייחסות אליו. הקובץ מכיל הצהרה של struct עם מפרט typedef המספק את השם STACK כשם נרדף לטיפוס, המוצהר כאן כ- struct עם שני שדות, שדה מטיפוס מערך של שלמים למחסנית ושדה מטיפוס שלם למציין של ראש המחסנית. לאחר מכן, נכתוב הצהרות עבור הפונקציות init, push ו- pop שיהיו הממשק לטיפוס. נצהיר עליהן כ-extern, למרות שזו ברירת המחדל, כדי להדגיש שמדובר בממשק. שים לב שהפרמטר של המחסנית מוגדר כמצביע ל-STACK משתי סיבות: (א) הפונקציות משנות את ערך הפרמטר, (ב) struct לא יכול להיות פרמטר בשפת C.

#define MAX 10

typedef struct {

     int top;

     int data[MAX];

} STACK;

 

extern void push(STACK *s, int x);

extern void pop(STACK *s, int *x);

extern void init(STACK *s);

 

בשלב שני נבנה קובץ  בשם stack.c למימוש טיפוס הנתונים המופשט. בראש הקובץ נרשום את המשפט include שיאפשר שימוש בהצהרות המופיעות בממשק. כדי להדגים את העקרונות של ההסכם, המימוש מלאכותי: הבדיקה האם המחסנית ריקה או לא מתבצעת על ידי  פונקציה מקומית המשתמשת בשני משתנים מקומיים להעברת תוצאת הבדיקה לפונקציות push ו- pop. לישויות אלו מצורף המפרט static כדי למנוע גישה אליהם מחוץ לקובץ זה.

#include "stack.h"

static int isEmpty;

static int isFull;

static void update(STACK *s) {

isFull = s->top == MAX-1;

isEmpty = s->top == 0;

}

 

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

void push(STACK *s, int x) {

             update(s);

     if (!isFull)

                    s->data[s->top++] = x;

}

 

void pop(STACK *s, int *x) {

     update(s);

     if (!isEmpty)

            *x = s->data[--s->top];

}

 

void init(STACK *s) {

     s->top = 0;

}

 

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

 

לאחר מימוש טיפוס הנתונים המופשט, ניתן להשתמש בו בקובץ אחר על ידי הכללת קובץ ה-include:

#include "stack.h"

void main() {

     STACK s;

int x;

     init(&s);

     push(&s, 10);

     pop(&s, &x);

}

 

שים לב ליתרון הקיים בהסכם המוצע שאינו קיים אם מסתמכים על ברירות המחדל של שפת C ללא שימוש בהצהרות נפרדות. אם בטעות נגדיר בתוך קובץ ה"מימוש" את חתימת אחת הפונקציות בצורה שונה ממה שמופיע ב"ממשק", נקבל שגיאת קומפילציה. למשל, אם נשמיט את סימן ה-* מהפרמטר השני בפעולת pop:

void pop(STACK *s, int x) { ... }

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

     pop(&s, x);

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

סיכום

ההסכם המוצע מאפשר הוראת מושגים חשובים (הפרדת ממשק ממימוש, הסתרת נתונים, וכדומה) גם בשפת C שחסרה תמיכה בטיפוסי נתונים מופשטים. צורת הכתיבה, המבוססת על הכנת ממשק ומימוש של טיפוסי נתונים מופשטים, דומה עד כמה שאפשר למה שמקובל עם units בשפת TurboPascal ועם class בשפות C++ ו-Java, ולא בהכרח לצורת הכתיבה הנהוגה על מתכנתי ,C המרבים להשתמש ב- preprocessor בהסכמים שלהם. המאמר מדגים את החשיבות בניסוח הסכמים כדי ללמד עקרונות חשובים במדעי המחשב, ולפתח תכניות בהתאם לעקרונות. מידע נוסף על התמיכה של שפות תכנות בטיפוסי נתונים מופשטים ניתן למצוא בספרי (Ben-Ari, 1996), וכן בספרו של ממציא שפת C++ (Stroustrup, 1994).

מקורות

1.     M. Ben-Ari. Understanding Programming Languages. John Wiley, 1996.

2.     B. Stroustrup. The Design and Evolution of C++. Addison-Wesley, 1994.

 


אתר המרכז הארצי

אתר הבטים

גליון יוני 2002

חזרה לתחילת העמוד