3. מבני נתונים

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

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

3.1 מערכים

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

מימוש של אוסף אובייקטים באופן זה נראה כך:

 
/* Array implementation of a collection */
#include <assert.h> /* Needed for assertions */
#include "collection.h" /* import the specification */
 
struct t_collection {
 int item_cnt;
 int max_cnt; /* Not strictly necessary */
 int item_size; /* Needed by FindInCollection */
 void *items[];
 };

נקודות לתשומת לב:

א. אנו ייבאנו את ההגדרות של האובייקטים לתוך היישום - דבר זה מאפשר למהדר לאמת כי היישום וההגדרות תואמות.

למרות שאין זה הכרחי לכלול את ההגדרות.

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

ב. items מסווג כמערך של void * ב- struct. זהו מערך של s'item אשר במקרה זה

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

תוכניתנים רבים בשפת C ישתמשו ב- void ** במקרה זה.

שאלה:

· מדוע הכינוי max_cnt אינו נחוץ בהכרח?

רמז: הדבר קשור לתנאים המקדימים והמאוחרים שהוגדרו למתודות, באובייקטים

כאלה.

היישומים של השיטות הם:

טען את collection.c

נקודות לתשומת לב:

א. ConsCollection עושה שימוש ב- מקצה זיכרון (memory allocator)calloc בכדי להקצות דינאמית זיכרון, מתוך הזיכרון

המוקצה לתוכנית, עבור אוסף הנתונים (collection). שתי דרישות הינן חיוניות - האחת היא הקצאת מקום עבור מבנה

ה- header עצמו, והשניה היא הקצאת מקום עבור מערך המצביעים.

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

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

(de-bugging): אם התנאים המקדימים אינם מסופקים, עדיף לדעת איזה מהתנאים הוא זה שאינו מסופק.

ג. memcmp היא פונקציה המשווה מקטעי זיכרון, בית אחר בית [עמוד ה-man של memcmp].

ד. השימוש ב- memcmp וב- ItemKey יוצר הגבלה על מבנה המפתח, שחייב להיות מחרוזת

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

שדות בתוך ה- item או כאלה המחושבים מה- item. מפתחות אלה מסתמכים על יכולות C אשר

בהן נדון מאוחר יותר.

ה. אין שום טיפול בטעויות, למשל במקרה שאין זיכרון זמין עבור calloc.

זהו חיסרון חמור!

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

טיפול בשגיאות יידון בהמשך.

מושגים

Hacking

יצירת תוכנית מחשב במהירות וללא כל מחשבה.

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