תוכנית דוגמה

 

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

אחר כך, רשימה מקושרת כלל תכליתית זו עוברת תת- חלוקה על מנת לספק שני מבנה מידע יותר מתמחים:

-   תור

-   מחסנית

מבני נתונים שהופקו כך פועלים עם אובייקטים מהסוג הכללי Object  ולכן, ניתן להשתמש בהם על

מנת להתאים לכל סוג של אובייקט ב-JAVA.

 

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

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

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

 

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

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

לכן.

 

הבדיקה שנערכה הייתה תוך שימוש ב- JDK 1.1.3  תחת Win95.

 

 

חלקי קוד מעניינים

 

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

 

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

 

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

 

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

 

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

 

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

 

היא מעניקה בנוסף גרסה מבוטלת של פונקצית ה- toString() בה ניתן להשתמש על מנת להציג מידע דיאגנוסטי מסוכם במכשיר פלט סטנדרטי( או ניתן להשתמש בה בכל מטרה בה ייצוג ה-String של תנאי חריג ייתכן מועיל).

 

class Excep extends Exception{   private String diagnosticData;//put diagnostic data here     Excep(){//NoArg constructor     diagnosticData = "No diagnostic data provided";   }//end NoArg constructor   Excep(String diagnosticData){//parameterized constructor     this.diagnosticData = diagnosticData;   }//end parameterized constructor   public String toString(){//override toString()     return diagnosticData;   }//end overridden toString()       }//end class Excep

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

שים לב שהפרמטר הנכנס לבנאי הוא התייחסות לאובייקט מהסוג הכללי Object והוא מאוחסן בתוך משתנה של האובייקט שהוא משתנה התייחסות של סוגObject .

 

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

 

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

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

 

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

 

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

 

class Node{  Object dataObj;//ref to data object is stored here   Node nextNode;//ref to the next node in the RawList     public Node(Object dataObj){//constructor     this.dataObj = dataObj;    }//end constructor}//end class Node

 

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

 

class RawList{   private Node firstNode;   //reference to first node  private Node lastNode;    //reference to last node

 

 

 

 

 

 

 

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

 

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

 

private Node getNode( Object dataObj)  {     Node newNode = new Node(dataObj);     return newNode;   }//end getNode()

 

 

 

 

 

 

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

פונקציה זו מחזירה פוינטר לקשר החדש.

 

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

(כפי שנראה בדוגמת הרשימה המסודרת בשיעור הבא).

 

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

 

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

 

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

 

boolean isEmpty(){     return firstNode == null;//return true if empty   }//end isEmpty()

 

 

 

 

 

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

 

שים לב שהיא מקבלת אובייקט מידע נכנס כסוג כללי Object כך שתוכל לסגל כל סוג אובייקט.

 

קריאה נעשית לפונקציה המדוברת לעיל המכונה getNode() להביא קשר חדש ולסגור בתוך עצמו את הפוינטר לאובייקט המידע הממשי בתוך קשר זה. הפונקציה המכונה getNode() מחזירה פוינטר לאובייקט הקשר החדש אשר נשמר במשתנה מקומי הנקרא newNode.

 

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

הרשימה נבדקת עבור ריקנות, ואם היא ריקה, ההתייחסות לקשר החדש ניתן למשתנים של אובייקט  ה-RawList  המכונים firstNode  ו- lastNode. במקרה זה, הקשר החדש הופך לקשר הראשון והאחרון ברשימה.

 

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

 

void toFront(Object dataObj){     Node newNode = this.getNode(dataObj);        if(this.isEmpty()) //RawList is empty       firstNode = lastNode = newNode;     else{ //RawList is not empty       newNode.nextNode = firstNode;       firstNode = newNode;     }//end if   }//end toFront()

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

 

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

(אבל לא ObjectPascal, מכיוון שזה ייתכן גרוע באותה מידה).

 

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

 

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

כך, אנו מקצים פוינטר לקשר החדש ל- lastNode.nextNode ו- lastNode.

 

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

 

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

 

void toBack(Object dataObj){     Node newNode = this.getNode(dataObj);        if(this.isEmpty()) //RawList is empty       firstNode = lastNode = newNode;     else { //RawList is not empty       lastNode.nextNode = newNode;       lastNode = newNode;     }//end if  }//end toBack()

 

 

 

 

 

 

 

 

 

 

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

 

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

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

 

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

 

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

(calling method). אובייקט המידע יפסיק להתקיים רק כאשר פונקצית הקריאה מפסיקה מלהצביע אליו עם הפוינטר למשתנה  פעיל.

 

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

 

אחרי שנפטרנו מעוד מקרה נדוש של רשימה ריקה, עלינו לקחת בחשבון עוד מקרה נדוש כמעט: רשימה בעלת קשר אחד בלבד.

 

Object fetchFromFront() throws Excep{     if(this.isEmpty()) //RawList is empty       throw new Excep("Empty list in fetchFromFront");     else { //RawList is not empty       //declare and initialize a local reference variable       Node tempRefToNode = firstNode;         if(firstNode == lastNode)//only one node in the list         firstNode = lastNode = null; //set both to null       else//more than one node in the list        //Wire around the first node and return it         firstNode = firstNode.nextNode;       return tempRefToNode.dataObj;   //fetch successful     }//end else   }//end fetchFromFront()

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

ייתכן ותרצה להסתכל בספר מקוונן, Thinking in Java, של Bruce Eckel  אשר, ע

ד לכתיבה זו ב- 12/17/97 היא זמינה ל-downloading חופשי ב- www.eckelobjects.com .

ל- Eckel יש דברים רבים לומר אודות איסוף זבל ונושאים קשורים.

 

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

 

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

 

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

שוב יש לנו המקרה הנדוש של רשימה ריקה שם פשוט נציג את ה-string "ריק" ונחסל את הפונקציה.

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

 

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

 

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

 

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

 

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

 

void printRawList(){     if(this.isEmpty()){       System.out.println("Empty");       return;     }//end if       //Not empty.  Declare and initialize a local      // reference variable to the first node in the list     Node currentRefToNode = firstNode;     //Use a while loop to traverse the list  displaying     // the data object in each node along the way.     while(currentRefToNode != null){       System.out.println("" + currentRefToNode.dataObj);       currentRefToNode = currentRefToNode.nextNode;     }//end while   }//end printRawList()