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

שיעור 11: שימוש במצביעים למבני נתונים דינמיים

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

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

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

program samp;  
var    
    p:^integer;  
begin    
    new(p);    
    p^:=10;    
    writeln(p^);    
    dispose(p);  
end.

אותו קוד ב C נראה כך:

#include <stdio.h> 
 
void main()  
{    
    int *p; 
     p=(int *) malloc (sizeof(int));    
    *p=10;    
    printf("%d\n",*p);    
    free(p);  
} 

למעשה קוד זה שימושי רק לשם הדגמת תהליך ההקצאה, השחרור והשימוש של גוש ב C. שורת ה malloc עושה את אותו הדבר שפקודת ה new עושה בפסקל. היא מקצה גוש זיכרון בגודל הנקוב --- במקרה זה, sizeof(int) בתים. פקודת sizeof ב C מחזירה גודל, בבתים, של כל טיפוס. הקוד יכול היה באותה מידה להיות malloc(4) כיוון ש sizeof(int) שווה לארבעה בתים ברוב מכונות ה UNIX. שימוש ב sizeof, בכל אופן, הופך את הקוד להרבה יותר נייד וקריא. פונקצית ה malloc מחזירה מצביע לגוש המוקצה. המצביע הוא כללי. שימוש במצביע ללא הסבת הטיפוס בדרך כלל יוצר אזהרת טיפוס מהמהדר. ההסבה (*int) הופכת את המצביע הכללי הזה שמוחזר על ידי malloc למצביע למספר שלם , שלו p מצפה. פקודת ה dispose בפסקל מוחלפת ב free ב C. היא מחזירה את הגוש המסוים לערימה לשימוש חוזר.

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

program samp;  
type    
    rec=record      
        i:integer;      
        f:real;      
        c:char;    
    end;  
var    
    p:^rec;  
begin    
    new(p);    
    p^.i:=10;    
    p^.f:=3.14;    
    p^.c='a';   
    writeln(p^.i,p^.f,p^.c);    
    dispose(p);  
end.

ב C הקוד נראה כך:

#include <stdio.h> 
 
struct rec 
{ 
    int i; 
    float f; 
    char c; 
}; 
 
void main() 
{ 
    struct rec *p; 
     p=(struct rec *) malloc (sizeof(struct rec)); 
    (*p).i=10; 
    (*p).f=3.14; 
    (*p).c='a'; 
    printf("%d %f %c\n",(*p).i,(*p).f,(*p).c); 
    free(p); 
}

שים לב לשורה הבאה:

(*p).i=10;

רבים תוהים מדוע הכתיבה הבאה לא פועלת:

*p.i=10;

התשובה קשורה בקדימויות אופרטורים ב C. התוצאה של החישוב 5+3*4 היא 17, לא 32, כיוון שהאופרטור * הוא בעל עדיפות גבוהה יותר מאשר + ברוב שפות המחשב. ב C, אופרטור ה . הוא בעל עדיפות גבוהה יותר מ *, כך שסוגריים מכריחים את הקדימות המתאימה. ראה שיעור 14 למידע נוסף על עדיפויות.

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

(*p).i=10;  
p->i=10;

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

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

/* Stack Library -  
   This library offers the minimal stack operations for a  
   stack of integers (easily changeable) */ 
 
typedef int stack_data; 
 
extern void stack_init();  
/* Initializes this library. Call first before calling anything. */ 
 
extern void stack_clear();  
/* Clears the stack of all entries. */ 
 
extern int stack_empty();  
/* Returns 1 if the stack is empty, 0 otherwise. */ 
 
extern void stack_push(stack_data d);  
/* Pushes the value d onto the stack. */ 
 
extern stack_data stack_pop();  
/* Returns the top element of the stack, and removes that element. 
   Returns garbage if the stack is empty. */

קובץ הקוד של הספרייה עוקב:

#include "stack.h"  
#include <stdio.h> 
 
/* Stack Library - This library offers the minimal stack operations  
   for a stack of integers */ 
 
struct stack_rec  
{    
    stack_data data;    
    struct stack_rec *next;  
}; 
 
struct stack_rec *top=NULL; 
 
void stack_init()  
/* Initializes this library. Call before calling anything else. */  
{    
    top=NULL;  
} 
 
void stack_clear()  
/* Clears the stack of all entries. */  
{    
    stack_data x; 
  
    while (!stack_empty())      
    x=stack_pop();  
} 
 
int stack_empty()  
/* Returns 1 if the stack is empty, 0 otherwise. */  
{    
    if (top==NULL)      
        return(1);   
    else      
        return(0);  
} 
 
void stack_push(stack_data d)  
/* Pushes the value d onto the stack. */  
{   
    struct stack_rec *temp; 
     temp=(struct stack_rec *)malloc(sizeof(struct stack_rec)); 
    temp->data=d;    
    temp->next=top;    
    top=temp;  
} 
 
stack_data stack_pop()  
/* Returns the top element of the stack, and removes that element.  
   Returns garbage if the stack is empty. */   
{    
    struct stack_rec *temp;    
    stack_data d=0; 
     if (top!=NULL)    
    {      
        d=top->data;      
        temp=top;      
        top=top->next;      
        free(temp);    
    }    
    return(d);  
}

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

שגיאות ב C מהן יש להימנע:

1. לשכוח לשים סוגריים כאשר מתייחסים לרשומה, כמו ב (*p).i לעיל.

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

3. לשכוח להכליל את stdio.h עם פעולות כלשהן עם מצביעים כך שיש גישה ל NULL.

תרגילים

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

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

לדף הראשון

<< לדף הקודם

לדף הבא >>