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

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

רשימה בשפת C ליחידת עיצוב תוכנה

יוסף בלאן
בית ספר המשיח האנגליקאני, נצרת

www.kinneret.co.il/byousef

 

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

 

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

כאשר הייצוג  נעשה ע"י שרשרת חוליות.

list.h

#include <alloc.h>

#include <stdio.h>

#include <conio.h>

typedef  int  list_info_type;

מידע הרשימה

typedef struct link_type * pos_type;

מקום ברשימה

typedef struct link_type {

        list_info_type info;

        pos_type next;

        {;

חוליה ברשימה

typedef struct list_type{

        pos_type anchor;

       };

הרשימה

void      list_init(list_type *l)

אתחל-רשימה: פעולה המחזירה רשימה ריקה

pos_type  list_anchor(list_type *l)

עוגן-רשימה (L)

פעולה המחזירה את המקום עוגן רשימה ברשימה L.

הנחה : הרשימה L מאותחלת.

pos_type  list_end(list_type *l);

סוף-רשימה (L)

פעולה המחזירה את המקום סוף רשימה ברשימה L.

הנחה : הרשימה L מאותחלת.

pos_type  list_next(list_type *l,pos_type p);

עוקב-ברשימה (L,p)

פעולה המחזירה את המקום העוקב למקום P ברשימה L.

הנחות: הרשימה L מאותחלת.

P הינו מקום ברשימה L שאינו סוף רשימה L.

pos_type  list_prev(list_type *l,pos_type p);

קודם-ברשימה (L,p)

פעולה המחזירה את המקום הקודם למקום P ברשימה L.

הנחות: הרשימה L מאותחלת.

P הינו מקום ברשימה L שאינו עוגן רשימה L.

void list_insert (list_type *l, pos_type p, list_info_type x);

הכנס-לרשימה (L , P , x)

פעולה המכניסה לרשימה L

את האיבר x מקום אחד אחרי המקום P.

הנחות: הרשימה L מאותחלת.

P הינו מקום ברשימה L שאינו סוף רשימה L.

void      list_delete(list_type *l,pos_type *p);

הוצא-מרשימה (L , P , x)

פעולה המוציאה מרשימה L את האיבר בה נמצא במקום P

לאחר ההוצאה נמצא במקום P את האיבר שהיה עוקב לזה שהוצא מהרשימה.

הנחות: הרשימה L מאותחלת.

P הינו מקום ברשימה L שאינו סוף רשימה או עוגן רשימה L.

void list_update (list_type *l, pos_type p, list_info_type x);

עדכן-רשימה (L , P , x)

פעולה המעדכנת את האיבר הנמצא במקום P  להיות x .

הנחות: הרשימה L מאותחלת.

P הינו מקום ברשימה L שאינו סוף רשימה או עוגן רשימה L.

void list_retrieve (list_type *l, pos_type p, list_info_type *x);

אחזר-מרשימה (L , P)

פעולה המחזירה את האיבר שנמצא במקום P ברשימה L

הנחות: הרשימה L מאותחלת.

P הינו מקום ברשימה L שאינו סוף רשימה או עוגן רשימה L.

int  empty_list (list_type *l);

רשימה-ריקה? (L)

פעולה המחזירה אמת אם הרשימה L היא ריקה ושקר אחרת.

הנחות : הרשימה L מאותחלת.

 

מימוש הממשק בסביבת העבודה :

List.c

#include list.h

 

void    list_init(list_type *l)

{

 pos_type p;

 l->anchor=(link_type *)malloc(sizeof(link_type));

 l->anchor->next=NULL;

{

pos_type  list_anchor(list_type *l)

{

     return l->anchor;

{

 

pos_type  list_end(list_type *l)

}

    return NULL;

{

pos_type  list_next(list_type *l,pos_type p)

}

 return p->next;

{

pos_type  list_prev(list_type *l,pos_type p)

}

pos_type q;

q=list_anchor(l);

while (list_next(l,q)!=p)

 }

  q=list_next(l,q);

}

return q;

{

void      list_insert(list_type *l,pos_type p ,list_info_type x)

}

 pos_type q;

 q=(link_type *)malloc(sizeof(link_type));

 q->info=x;

 q->next=list_next(l,p);

 p->next=q;

{

void      list_delete(list_type *l,pos_type *p)

}

pos_type q;

q=list_prev(l,*p);;

q->next=(*p)->next;

free(*p);

*p=list_next(l,q);//or *p=q->next;

{

 

void      list_update(list_type *l,pos_type p ,list_info_type x)

}

        p->info=x;

{

 

void      list_retrieve(list_type *l,pos_type p ,list_info_type *x)

}

         *x=p->info;

{

int  empty_list(list_type *l)

}

  if ( list_next(l,list_anchor(l))==list_end(l))

  return 1  ;

  return 0;

{

 

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

# include list.c

#include <stdio.h>

#include <conio.h>

 

void main(void)

}

clrscr();

list_info_type z;

z=77;

list_type l1;  

list_init(&l1);

 

pos_type  p;

בניית רשימה:

p=list_anchor(&l1);

for(int i=1;i<=5;i++)

{

    list_insert(&l1,p,z);

    p=list_next(&l1,p);

{

 

הדפסת כל איברי הרשימה:

p=list_next(&l1,list_anchor(&l1));

while(p!=list_end(&l1))

{

list_retrieve(&l1,p,&z);

printf("z=%d\n",z);

p=list_next(&l1,p);

}

מחיקת כל איברי הרשימה:

p=list_next(&l1,list_anchor(&l1));

while( empty_list(&l1)= 0)

{

  list_delete(&l1,&p);

}

}

 

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

אתר הבטים

גליון יוני 2002

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